I worked on optimising lots of builds from Symbian to Android and other proprietary ones. C++ compiler choice is very important - gcc might seem slow but it is a speed demon compared to the old ARM compilers.
There are a lot of tricks based on trying not to do the same work twice like pre-compiled headers which might help massively (since headers can be much bigger than your code) but quite often these are also very fragile because changing one #define in one central header file might invalidate everything. It's not that easy to be sure that you are truly handling all dependencies. Hence one tends to have to regularly build from scratch to be certain that everything is done properly. If we really could handle it all perfectly then nobody would ever bother to build from clean.
It's also very important to be able to see how your build tool is scheduling tasks and making use of your CPUs - often some odd dependencies force most of your cores to sit idle while something gets done. There aren't good visualisation tools for this that aren't proprietary imo. I have cobbled together something for gmake which can output something you can visualise in chrome's profiler but it's crap compared to the best commercial tool I've used. You can remember the previous build times of various objects and use them to try to schedule large tasks as early as possible so they don't extend the build time by randomly getting started towards the end and then leaving the build going on and on just to get them finished.
The structure of your code matters too - a simple optimisation for C/C++ is just to have much larger source files rather than splitting everything up into many small ones. This acts to reduce the number of repeated includes.
If I was thinking about how to get fast builds it would force the language to change - header files would be banned and that means macros and the whole idea of preprocessing. That means a different approach to multi-platform support. Android benefits from having a java layer where you can pretty much build once and run anywhere and that is very good.
Eventually, on one big project, we got to the point where it was the packaging that was the slowest component and that was being done by the CI system .... for no good reason other than organisational inertia. Another team was responsible and didn't want to take advice. Since we couldn't bring it into the build and use all our tricks to optimise and redesign it we hit a wall where all our efforts to improve build performance had little impact.
The best tricks for improvement, of course, are the ones which always work and don't need a lot of maintenance to keep them functioning properly.
I think we need builds to be integrated with source control. Getting new versions of source and new binaries is all far too "separate" a process. Checking in 5 files should result in a very accurate rebuild of only the dependencies and a subsequent checkout should be able to get me those binaries. Developers should never really have to build all of Android just to work on some small part and they shouldn't really have to do more than one checkout to get everything they need including binaries.