Turns out BrowserInstantController and InstantController already aren't built on Android, but some other things are (and don't need to be):
InstantService
NewTabPageInterceptorService
NTPUserDataLogger
SearchIPCRouter
SearchTabHelper

Pending CL that removes all of the above: https://crrev.com/c/790511

Some more things I came across:
- InstantUI (can probably be removed on all platforms)
- SearchBouncer
- InstantIOContext
- IframeSource/MostVisitedIframeSource
- SearchEngineBaseURLTracker

The remaining potential binary size savings are likely small though.

https://crrev.com/c/790511 now removes everything except InstantUI (which I'll separately remove for all platforms) and InstantIOContext (::ShouldServiceRequest is referenced in lots of places, so might be worth pulling out first).

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/7895941d3755d38b377e190a38792d2ea479e247

commit 7895941d3755d38b377e190a38792d2ea479e247
Author: Marc Treib <treib@chromium.org>
Date: Tue Nov 28 12:37:02 2017

Cleanup: Don't build search/instant code on Android

There's a lot of search/instant code which isn't used on Android, but
was still built and shipped. This CL moves most of it to the
non-Android sections of the build files (and #ifdef's out access points
where necessary), for the following classes:
- InstantService
- NTPUserDataLogger
- NewTabPageInterceptorService
- SearchIPCRouter
- SearchTabHelper
- [MostVisited]IframeSource
- SearchBouncer
- SearchEngineBaseURLTracker

This saves almost 50kB of binary size on Android:
tools/binary_size/diagnose_bloat.py --reference-rev=master HEAD -v
MonochromePublic.apk_Breakdown (-49,152 bytes)
   -23,820 bytes Native resources (no l10n) size
      -328 bytes Zip Overhead
      -422 bytes Native resources (l10n) size
   -24,576 bytes Native code size
        -6 bytes Package metadata size
MonochromePublic.apk_Specifics
   -49,502 bytes normalized apk size
   -24,576 bytes main lib size

Bug:  787830 
Change-Id: I1cf914863e0bd75cc2fa15356fe072beb961368c
Reviewed-on: https://chromium-review.googlesource.com/790511
Reviewed-by: Jochen Eisinger <jochen@chromium.org>
Commit-Queue: Marc Treib <treib@chromium.org>
Cr-Commit-Position: refs/heads/master@{#519661}
[modify] https://crrev.com/7895941d3755d38b377e190a38792d2ea479e247/chrome/browser/BUILD.gn
[modify] https://crrev.com/7895941d3755d38b377e190a38792d2ea479e247/chrome/browser/chrome_content_browser_client.cc
[modify] https://crrev.com/7895941d3755d38b377e190a38792d2ea479e247/chrome/browser/profiles/chrome_browser_main_extra_parts_profiles.cc
[modify] https://crrev.com/7895941d3755d38b377e190a38792d2ea479e247/chrome/browser/profiles/profile_io_data.cc
[modify] https://crrev.com/7895941d3755d38b377e190a38792d2ea479e247/chrome/browser/search/search.cc
[modify] https://crrev.com/7895941d3755d38b377e190a38792d2ea479e247/chrome/browser/ui/BUILD.gn
[modify] https://crrev.com/7895941d3755d38b377e190a38792d2ea479e247/chrome/browser/ui/tab_helpers.cc
[modify] https://crrev.com/7895941d3755d38b377e190a38792d2ea479e247/chrome/renderer/BUILD.gn
[modify] https://crrev.com/7895941d3755d38b377e190a38792d2ea479e247/chrome/renderer/chrome_content_renderer_client.cc
[modify] https://crrev.com/7895941d3755d38b377e190a38792d2ea479e247/chrome/renderer/chrome_content_renderer_client_unittest.cc
[modify] https://crrev.com/7895941d3755d38b377e190a38792d2ea479e247/chrome/test/BUILD.gn

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/c365e1fb592eb3e9d9b1dcc06dafad8de41f98f8

commit c365e1fb592eb3e9d9b1dcc06dafad8de41f98f8
Author: Marc Treib <treib@chromium.org>
Date: Wed Nov 29 12:03:17 2017

Fix Android build failure due to missing search.mojom.h

This fixes an intermittent build problem introduced by crrev.com/790511:
metrics_render_frame_observer.cc included search_bouncer.h which in turn
included search.mojom.h, which is now not generated on Android anymore.
This CL removes that include, since it's unused anyway.
It also moves chrome/common:search_mojom back into chrome/renderer's
non-OS-specific deps, since it appears to be needed there for unknown
reasons.

TBRing since it's a trivial change, and this is causing active build
pain.
TBR=csharrison

Bug:  787830 ,  789270 , 789403
Change-Id: Ie49cb63b3ef23a3d76fc2cd1cddbc8faa4fa41f7
Reviewed-on: https://chromium-review.googlesource.com/795729
Reviewed-by: Marc Treib <treib@chromium.org>
Commit-Queue: Marc Treib <treib@chromium.org>
Cr-Commit-Position: refs/heads/master@{#520080}
[modify] https://crrev.com/c365e1fb592eb3e9d9b1dcc06dafad8de41f98f8/chrome/renderer/BUILD.gn
[modify] https://crrev.com/c365e1fb592eb3e9d9b1dcc06dafad8de41f98f8/chrome/renderer/page_load_metrics/metrics_render_frame_observer.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/409320b6e384953333d460883fe7a04ace75f546

commit 409320b6e384953333d460883fe7a04ace75f546
Author: Marc Treib <treib@chromium.org>
Date: Thu Nov 30 14:30:42 2017

Cleanup: Remove InstantUI, i.e. chrome://instant

Most of its functionality had been removed already. The only thing
remaining was overriding a pref that isn't used at all.

Bug:  627747 ,  787830 
Cq-Include-Trybots: master.tryserver.chromium.linux:closure_compilation
Change-Id: Icf09d46b98331e47a419f85ade034b889a60b66c
Reviewed-on: https://chromium-review.googlesource.com/793510
Reviewed-by: Dominic Battré <battre@chromium.org>
Reviewed-by: calamity <calamity@chromium.org>
Commit-Queue: Marc Treib <treib@chromium.org>
Cr-Commit-Position: refs/heads/master@{#520537}
[modify] https://crrev.com/409320b6e384953333d460883fe7a04ace75f546/chrome/browser/browser_resources.grd
[modify] https://crrev.com/409320b6e384953333d460883fe7a04ace75f546/chrome/browser/prefs/browser_prefs.cc
[delete] https://crrev.com/c721c7cddaa61e28a360f5942682d7417fc7c5c9/chrome/browser/resources/instant/instant.css
[delete] https://crrev.com/c721c7cddaa61e28a360f5942682d7417fc7c5c9/chrome/browser/resources/instant/instant.html
[delete] https://crrev.com/c721c7cddaa61e28a360f5942682d7417fc7c5c9/chrome/browser/resources/instant/instant.js
[modify] https://crrev.com/409320b6e384953333d460883fe7a04ace75f546/chrome/browser/ui/BUILD.gn
[modify] https://crrev.com/409320b6e384953333d460883fe7a04ace75f546/chrome/browser/ui/webui/chrome_web_ui_controller_factory.cc
[delete] https://crrev.com/c721c7cddaa61e28a360f5942682d7417fc7c5c9/chrome/browser/ui/webui/instant_ui.cc
[delete] https://crrev.com/c721c7cddaa61e28a360f5942682d7417fc7c5c9/chrome/browser/ui/webui/instant_ui.h
[modify] https://crrev.com/409320b6e384953333d460883fe7a04ace75f546/chrome/common/pref_names.cc
[modify] https://crrev.com/409320b6e384953333d460883fe7a04ace75f546/chrome/common/pref_names.h
[modify] https://crrev.com/409320b6e384953333d460883fe7a04ace75f546/chrome/common/webui_url_constants.cc
[modify] https://crrev.com/409320b6e384953333d460883fe7a04ace75f546/chrome/common/webui_url_constants.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/7d467b79bfad9d104e5775e8c652a47ae3f9d93c

commit 7d467b79bfad9d104e5775e8c652a47ae3f9d93c
Author: Marc Treib <treib@chromium.org>
Date: Mon Dec 04 13:31:03 2017

Remove more search/instant code on Android

This CL #ifdef's out a bunch of Instant-process-related functions in
chrome/search/search.h/cc on Android. This code was never used on
Android and doesn't make sense there; let's make that obvious.

Bug:  787830 
Change-Id: I74d51009010df4633631102bacf051a5d1a52583
Reviewed-on: https://chromium-review.googlesource.com/803443
Commit-Queue: Marc Treib <treib@chromium.org>
Reviewed-by: Chris Pickel <sfiera@chromium.org>
Cr-Commit-Position: refs/heads/master@{#521327}
[modify] https://crrev.com/7d467b79bfad9d104e5775e8c652a47ae3f9d93c/chrome/browser/chrome_content_browser_client.cc
[modify] https://crrev.com/7d467b79bfad9d104e5775e8c652a47ae3f9d93c/chrome/browser/search/search.cc
[modify] https://crrev.com/7d467b79bfad9d104e5775e8c652a47ae3f9d93c/chrome/browser/search/search.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/9028a6ad96cb6f471b608e1fddacb2398d0a9dba

commit 9028a6ad96cb6f471b608e1fddacb2398d0a9dba
Author: Marc Treib <treib@chromium.org>
Date: Wed Dec 06 16:21:51 2017

Cleanup: Remove Android-specific #ifdef's etc from search/instant code

As of https://crrev.com/c/790511, this code isn't built on Android
anymore.
This also adds compile-time checks to many Instant headers to make sure
they're not accidentally built on Android.

Bug:  787830 
Change-Id: I88026ce703158ac5b1580f02e621dea325a6fd64
Reviewed-on: https://chromium-review.googlesource.com/803280
Commit-Queue: Marc Treib <treib@chromium.org>
Reviewed-by: Chris Pickel <sfiera@chromium.org>
Cr-Commit-Position: refs/heads/master@{#522101}
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/BUILD.gn
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/search/iframe_source.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/search/instant_service.cc
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/search/instant_service.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/search/instant_service_factory.cc
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/search/instant_service_factory.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/search/instant_service_observer.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/search/local_files_ntp_source.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/search/local_ntp_source.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/search/most_visited_iframe_source.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/ui/browser_instant_controller.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/ui/search/instant_controller.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/ui/search/ntp_user_data_logger.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/ui/search/search_ipc_router.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/ui/search/search_ipc_router_policy_impl.h
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/ui/search/search_tab_helper.cc
[modify] https://crrev.com/9028a6ad96cb6f471b608e1fddacb2398d0a9dba/chrome/browser/ui/search/search_tab_helper.h