Advanced Auto-Dependency Generation


One of the most important, and yet potentially frustrating, tasks that is required to allow any make-based build environment to function properly is the correct listing of dependencies in the makefile.

This document describes a very useful method for having make itself create and maintain these dependencies completely automatically.

The advanced method below was invented by Tom Tromey <tromey@cygnus.com>, I merely wrote it down here. Credits for the method go to him; problems with the explanation belong to me.


All make programs must know, with great accuracy, what files a particular target is dependent on in order to ensure that it is rebuilt when (and only when) necessary.

Keeping this list up-to-date by hand is not only tedious, but quite error prone. Most systems of any size prefer to provide automated tools for extracting this information. The most commonly used method is probably the makedepend program, which reads C source files and generates a list of the header files in a target-dependency format suitable for inclusion in (or appending to) a makefile.

Another popular solution, for those using suitably enlightened compilers or preprocessors (such as GCC), is to have the compiler or preprocessor generate this information.

The purpose of this document isn't primarily to discuss ways in which this dependency information can be obtained, although I will discuss some methods in the last section.

What it does do is offer some useful ways to combine the invocation and output of these tools with GNU make to ensure that dependency information is always accurate and up-to-date, as seamlessly (and efficiently) as possible.

As described here, these methods work only with GNU make. It may be possible to modify them to work with other versions of make which support at least include directives; that's left as an exercise to the reader. However, before undertaking that exercise please review Paul's First Rule of Makefiles :).

Traditional make depend Method

The time-honored method of handling dependency generation is to provide a special target in your makefiles, typically depend, which can be invoked to create dependency information. The command for this target will invoke some kind of dependency tracking tool on all the relevant files in the directory.

With less capable make programs, this usually also involves some shell hackery to append the list of dependencies generated to the end of the makefile itself. With GNU make, of course, we have the include directive so this, at least, is unnecessary.

Although it's simple, there are serious problems with this method. First and foremost is that dependencies are only rebuilt when the user explicitly requests it; if the user doesn't run make depend regularly they could become badly out-of-date and make will not properly rebuild targets. Thus, we cannot say this is seamless and accurate.

Another problem is that it is inefficient to run make depend the second and subsequent times. Since it modifies makefiles, you typically must do it as a separate build step, which means an extra invocation of every make in every subdirectory, etc., in addition to the overhead of the dependency-generation tool itself. Also, it rechecks every file, even if it hasn't changed.

So, we'll see how we can do better.

The GNU make include Directive

All of the methods described below rely on GNU make's special include preprocessing statement. Unsurprisingly, this allows one makefile to include other makefiles, as if they had been entered there.

One can immediately see how this would be useful, simply to avoid appending dependency information to a makefile as in the step above. However, there is a more interesting feature to GNU make's handling of included makefiles: just as with the normal makefile, GNU make will attempt to rebuild the included makefile. If it can be rebuilt, make will re-execute itself to read the new version.

This auto-rebuild feature can be harnessed to avoid requiring a separate "make depend" step, which would build the dependencies, before the "normal" make which builds the application. For example, if you listed all the source files as prerequisites to the dependency output file, it would be rebuilt every time a file changed. Thus, the dependency information would always be up-to-date and the user wouldn't need to run make depend explicitly. Of course, this means dependency information is recalculated for all files every time any file changes, which is unfortunate.

For a detailed description of GNU make's automatic rebuild feature, see the GNU make User's Manual, section ``How Makefiles Are Remade''.

Basic Auto-Dependencies

The GNU make User's Manual describes one way of handling auto-dependencies; see section ``Generating Dependencies Automatically''.

In this method, one ``dependency'' file is created for each source file (in our examples we'll use a .P suffix on the base filename). This dependency file contains the dependency statement for the target that is created from just that one source file.

These dependency files are then all included by the makefile, to obtain dependency info. An implicit rule is provided that describes how the dependency files are to be created. In short, something like this:

  SRCS = foo.c bar.c ...

  %.P : %.c
          $(MAKEDEPEND)
          @sed 's/\($*\)\.o[ :]*/\1.o $@ : /g' < $*.d > $@; \
             rm -f $*.d; [ -s $@ ] || rm -f $@

  include $(SRCS:.c=.P)

In these examples I'll simply use variables such as $(MAKEDEPEND) to stand for whatever method you choose for creating dependency files. Some possible values for this variable are described below.

In this case, the output is written to a temporary file and post-processed. The post-processing changes the normal target specification:

  foo.o: foo.c foo.h bar.h baz.h
to also contain the .P file itself, like this:
  foo.o foo.P: foo.c foo.h bar.h baz.h

Whenever GNU make reads this makefile, before it does anything else it will look into rebuilding the included makefiles, in this case the .P files. We have a rule to build them, and we have a list of prerequisites which is the same as the list for the .o file itself. So, if any file changes that would cause the original target to appear out-of-date, it will also cause the .P file to be rebuilt.

Thus, when source files or an included file changes, make will rebuild the .P file(s), re-execute itself to read in the new makefiles, then continue with builds as usual, now with an updated and accurate dependency list.

Here we solve the two problems with the earlier solutions. First, the user doesn't have to do anything special to ensure accurate dependency lists; make will take care of it. Second, we are only updating dependency lists for those file which have actually changed, not all the files in the directory.

We have three new problems with this method, however. The first is still efficiency. Although we only re-examine changed files we still will re-exec make if anything changes, which could be slow for large build systems.

The second problem is merely annoying: when you add a new file or build for the first time, no .P file will exist. When make tries to include it and discovers it doesn't exist, it will generate a warning. This isn't fatal because make will then proceed on to rebuild the .P file and re-invoke itself; nevertheless it's somewhat unsightly.

The third problem is more serious: if you remove or rename a prerequisite file (say a C .h file), make will stop with a fatal error, complaining that the target doesn't exist:

  make: *** No rule to make target `bar.h', needed by `foo.P'.  Stop.
This is because the .P file has a dependency on a file make can't find. It can't rebuild the .P file until all the prerequisites are there, and it won't realize it doesn't need the prerequisite until it rebuilds the .P file. Catch-22.

The only solution here is to go in by hand and remove any .P file that refers to the missing file--typically it's simpler to remove all of them than try to find the proper ones. You can even create a clean-deps target or similar to do it automatically (investigate the MAKECMDGOALS variable to see how you can write this target while still avoiding the rebuild attempt on the .P files). This is annoying to be sure, but given that files aren't removed or renamed all that often in a typical environment perhaps it's not fatal.

Advanced Auto-Dependencies

The method described here was engineered by Tom Tromey <tromey@cygnus.com>, who invented it as the standard dependency generation method for the FSF's automake tool. I consider it quite ingenious.

Avoiding Re-exec of make

Let's address the first problem above: the re-invocation of make. If you think about it, this re-invocation is really unneeded. Since we know some prerequisite of the target changed, we don't really need the updated prerequisite list in this build. We already know that we're going to rebuild the target, and having a more up-to-date list won't affect that decision. What we really need is to ensure that the prerequisite list is up-to-date for the next invocation of make, when we need to decide whether to update it again.

Since we don't need the up-to-date prerequisite list in this build, we can actually avoid re-invoking make at all: we can simply have the prerequisite list built at the same time as the target is rebuilt. In other words, we can change the build rule for our target to add in commands to update the dependency file. Also, in this case we must be very careful that we don't provide rules to build the dependencies automatically: if we do make will still try to rebuild them and re-exec: we don't want that.

Now that we don't care about dependency files that don't exist, solving the second problem (superfluous warnings) is easy: we can just use GNU make's -include directive to include them, which doesn't display any message if they don't exist.

Let's take a look at an example so far:

  SRCS = foo.c bar.c ...

  %.o : %.c
          @$(MAKEDEPEND)
          $(COMPILE.c) -o $@ $<

  -include $(SRCS:.c=.P)

Avoiding ``No rule to make target ...'' Errors

This one is a little trickier. However, it turns out we can convince make to not fail merely by mentioning the file explicitly as a target in the makefile. If a target exists, but has no commands (either implicit or explicit) or prerequisites, then make simply always considers it up-to-date. That's the normal case, and it behaves as we'd expect.

In the case where the above error occurs, the target doesn't exist. According to the GNU make User's Manual section ``Rules without Commands or Prerequisites'':

If a rule has no prerequisites or commands, and the target of the rule is a nonexistent file, then `make' imagines this target to have been updated whenever its rule is run. This implies that all targets depending on this one will always have their commands run.

Perfect. It ensures make won't throw an error since it knows how to handle that non-existent file, and it ensures that any file depending on that target is rebuilt, which is exactly what we want.

So, all we need to do is post-process the original dependency file and turn all the prerequisites into targets with no commands or prerequisites. Something like this [1]:

  SRCS = foo.c bar.c ...

  %.o : %.c
          @$(MAKEDEPEND); \
            cp $*.d $*.P; \
            sed -e 's/#.*//' -e 's/^[^:]*: *//' -e 's/ *\\$$//' \
                -e '/^$$/ d' -e 's/$$/ :/' < $*.d >> $*.P; \
            rm -f $*.d
          $(COMPILE.c) -o $@ $<

  -include $(SRCS:.c=.P)

Briefly, this creates a .P file with the original prerequisites list, then adds targets to it by taking each line, removing any existing target information and any line continuation (\) characters, then adding a target separator (:) to the end. This works with the values for MAKEDEPEND I suggest below; it's possible you will need to modify the translation for other dependency generators you might use.

Placement of Output Files

You may decide you don't like all those .P files cluttering up your source directory. You can easily have your makefile put them somewhere else. Here's an example of doing that for the advanced method; you can extrapolate to the other methods:

  DEPDIR = .deps
  df = $(DEPDIR)/$(*F)

  SRCS = foo.c bar.c ...

  %.o : %.c
          @$(MAKEDEPEND); \
            cp $(df).d $(df).P; \
            sed -e 's/#.*//' -e 's/^[^:]*: *//' -e 's/ *\\$$//' \
                -e '/^$$/ d' -e 's/$$/ :/' < $(df).d >> $(df).P; \
            rm -f $(df).d
          $(COMPILE.c) -o $@ $<

  -include $(SRCS:%.c=$(DEPDIR)/%.P)

Replace any references to $*.d in the MAKEDEPEND script with $(df).d.

Defining MAKEDEPEND

Here I'll discuss some possible ways to define the MAKEDEPEND variable I've blithely been using above.

MAKEDEPEND = /usr/lib/cpp

The most basic way to generate dependencies is by using the C preprocessor itself. This requires a bit of knowledge about the output format of your preprocessor--luckily most UNIX preprocessors have similar output for our purposes. In order to preserve line number information for the compiler's error messages and debugging information, the output of the preprocessor must provide line number and filename information for each jump to an #include file and each return from one. These lines can be used to figure out what files were included.

Most UNIX preprocessors insert special lines in the output with this format:

  # lineno "filename" extra

All we care about is the filename value. If your preprocessor generates output like the above, a definition like this for MAKEDEPEND should work:

  MAKEDEPEND = $(CPP) $(CPPFLAGS) $< \
                 | sed -n 's/^\# *[0-9][0-9]* *"\([^"]*\)".*/$*.o: \1/p' \
                 | sort | uniq > $*.d

If you're using the advanced method, you can replace the $*.o in the sed script with $@. If you have a modern version of sort, you can also replace sort | uniq with just sort -u.

And, of course, if you go this route you might as well combine the post-processing involved with the method you're using right into this script.

MAKEDEPEND = makedepend

The X Windowing System source tree comes with a program called makedepend. This program examines C source and header files and generates make dependency lines. It's geared towards adding those dependencies to the bottom of an existing makefile, so to use it the way we want we need to be a little tricky. For example, some versions fail if the output file doesn't already exist.

This definition should suffice:

  MAKEDEPEND = touch $*.d && makedepend $(CPPFLAGS) -f $*.d $<

MAKEDEPEND = gcc -M

The GNU Compiler Collection contains a C preprocessor that can generate make dependency files. This definition should suffice:

  MAKEDEPEND = gcc -M $(CPPFLAGS) -o $*.d $<

Combining Compilation and Dependency Generation

If you're using GCC you can save yourself a lot of time during the build by combining the dependency generation and the object file generation. If you have a fairly recent version of GCC, you can use the -MD option to have it generate dependency information. This option always puts the dependency information in a file.d output file. Therefore, you could replace the compilation rule in the advanced method above with this, which should be a good bit faster:

  %.o : %.c
          $(COMPILE.c) -MD -o $@ $<
          @cp $*.d $*.P; \
            sed -e 's/#.*//' -e 's/^[^:]*: *//' -e 's/ *\\$$//' \
                -e '/^$$/ d' -e 's/$$/ :/' < $*.d >> $*.P; \
            rm -f $*.d

You can do this in some older versions of GCC by using an environment variable. You can also specify an alternate filename for the output file by passing options through GCC directly to the preprocessor, with an option sequence, something like this: -Wp,-MD,$*.xx. This is especially useful if you want the output dependency files in a different directory. See the manual for your compiler and/or your preprocessor for more information.

Dependencies For Non-C Files

In general you need some way of producing dependency files in order to use these methods. If you're working with files that aren't C files you'll need to discover or write your own method. Anything that generates make dependency files will do. This usually isn't too difficult.

An interesting idea has been proposed by Han-Wen Nienhuys <hanwen@cs.uu.nl> and he has a small "proof of concept" implementation, although it currently only works on Linux. He suggests using the LD_PRELOAD environment to insert special shared library that contains a replacement for the open(2) system call. This version of open() would actually write out make dependency information for every file the commands read during operation. This would give you completely reliable dependency information for every kind of command without needing any special dependency extraction tools at all. In his proof-of-concept implementation you can control the output file and exclude some kinds of files (shared libraries, maybe) via environment variables.


[1] Note I have modified the post-processing sed scripts here from what Tom uses in automake, in order to allow various styles of MAKEDEPEND output to work.

Paul D. Smith <psmith@gnu.org>
Last modified: Fri Jun 23 18:16:05 EDT 2000

Copyright © 1999 Paul D. Smith --- Verbatim copying and distribution is permitted in any medium, provided this notice is preserved.