I think reading strace's output was a great experiment, but I don't think it's really that necessary. Most programs have some way of spitting out the dependencies, and some others follow pretty standard rules for file generation. For instance, ocaml optional interface files generate a .cmi file from a .mli file, and implementation files generate a .cmo file from a .ml file. However, if no .mli file exists, compiling the .ml file will also generate a .cmi file.

It can be a pain, but it's really not that hard to handle if your build system provides a way to abstract out build patterns.