Actually, the compilers do not and you are doing less than half of the job there. They don't emit information about the non-existent files that would change the build if they were to suddenly exist, such as an "x.h" in one of several standard search directories in that example.
Also they don't add an empty rule for the source file (like they can do for headers), so if you rename from e.g. foo.c to foo.cpp, which still produces a foo.o, your incremental build fails because the dep file still has the dep on foo.c which doesn't exist anymore.
The original sin here is generating the dependencies from the source files in the same step that was used to generate the object files. The only way to ensure that Make observes structural changes in the dependency DAG is if the graph is rebuilt.
* http://jdebp.uk./FGA/introduction-to-redo.html#CompilerDefic...