Also be sure to have a look at tup, which operates vastly more efficient by simply walking the DAG in the opposite direction:
That is, instead of looking what you want to build and checking all timestamps of dependency files, it can use e.g. inotify, then know exactly which files changed, and rebuilds everything that depends on those files.
Moreover, it performs the modification check only once, at the beginning. During the build, it doesn't need to re-check everything, because it already knows which files were recreated.