Also, they have a ridiculous number of machines dedicated to running automated tests. My tech lead told me "feel free to add as many tests as long as they're under 30 seconds each".
I was super skeptical of perforce before starting at Google, but it works really well, especially in conjunction with the code review tools and processes
How are the dependencies specified? Is this a language-specific tool?
However, that's not enough when you touch a fundamental library and nearly everything is a downstream dependency. Then you really do need to run all the tests, so the build system should be able to run them in parallel on a build farm. Also, test results need to be cached by the build farm so every user doesn't need to run the same tests again for the same change.
See Bazel [1] for how Google does it. (Well, it doesn't provide the build farm, but you can see what the build files look like.)
[1] http://bazel.io/
The notion of zero-config CI is a recent invention, thanks to conventions of small repos with well-known project file names per language/platform ecosystem.