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.