I'm surprised to see no mention of Tup [1] in the discussion. Verifying the dependency graph for maximizing parallelism is its major feature.
To rebuild, it will rerun the script, except that it knows which file it reads (and which mustn't exist), so if nothing is changed, it can skip that stage. There is no inherent difference between the compiler binary (say, /usr/bin/gcc), the system include (/usr/include/stdio.h), and the project source.
It makes for a super simple build script, which, after one successful build, gives tup enough information about dependencies and parallelization opportunities, while at the same time also tracks toolchains better than you can manually (does /usr/bin/gcc shell to /usr/bin/x86-gcc or /usr/bin/amd64-gcc ? did one of them change but not the other? was it the one we need? tup knows)
Unfortunately, it is nontrivial; it can uses ptrace or fuse to trace file access on Linux, IIRC has some other hack on Windows - and little to no support for other systems. Also, the overhead is in the single digit % last time I checked.