One solution is to make PrefetchService start at startup and DependsOn the GCMProfileService.  This has a few downsides:
* GCMProfileService would always be created at startup, instead of lazily, when the feature is enabled (Not sure this is necessarily bad)
* Starting GCMProfileService earlier may exacerbate problems with other app handlers being added a bit later in profile initialization
* PrefetchService doesn't /need/ to be created at startup per se, but would be required to for this purpose.

Another solution is to chage GCMProfileService to:
* Have a registry of app handlers
* Create and take ownership of all app handlers at GCMDriver creation time
* App handlers create their respective services on demand when a message or other event arrives.

I think we should delay start the core of GCMDriver. Different features could call GCMDriver::AddAppHandler to register a handler at browser startup time. The core of GCMDriver will not start at that time. Only some seconds after the browser finishes the startup, the core of GCMDriver will start to run and the GCM messages get received and dispatched.

For Android, we need to figure out a way to delay start ChromeGcmListenerService. Perhaps we can use AlarmManager to send a pending intent to start this service.

I think the best one is the "Another solution" from comment #1.

Here indeed we have a two-way 'dependency':
1. Prefetch [sometimes] needs to call methods from GCM
2. GCM needs to call Prefetch if it has a hot message to pass to Prefetch's AppHandler.

The mentioned solution splits this the right way: GCM might not depend on Prefetch as a service, but it has to at least collect AppHandlers which can be simple listeners. AppHandlers may fetch/create their respective services if and when they receive the actual message from GCMDriver.

I think this will allow to not use any calls to DependsOn as they become simply unnecessary.

WRT #3: I am not sure we can delay-start GCMDriver, because if the actual GCM message was received by core GCM code in GMS, it'll invoke Chrome on intent with that message and we must process that intent, is this correct?

For #5, we can choose not to add the intent to Android manifest. Instead, we can use AlarmManager to setup the intent at a later time. This is what I found from search. The Android expert please comments on the feasibility of this approach.