I'll second the suggestion to take a look at tup -- it is based on some really good, clear-headed foundational thinking about how to make incremental builds fast, plus the implementation looks good (though I have only tried it out on experimental toy setups, and it is still pretty new, so who knows).

Regarded the specifically cited point of including dependencies on compilation flags, unless I am confused, I believe it can be done much more quickly in standard make, in one of two ways:

First way: make the build path of the object file dependent on the build flags. This has zero performance penalty, and also has the nice side-effect that when changing flags (e.g., from release to debug build and back again), you don't have to recompile everything, because you still have the previous build sitting around.

Second way: store the build flags in a separate makefile snippet (which you can either include or get the value of using $(shell)), and add that as a dependency of the object files. This has minimal performance impact since it's just another normal dependency for the object files. (This second trick is from one of the articles linked to about redo posted a few days ago; sadly I don't recall exactly which.)