The Dependency Graph — How Make Decides What to Rebuild

Lesson 4: The Dependency Graph — How Make Decides What to Rebuild

Make's superpower is that it remembers what needs doing. Every prerequisite edge in your Makefile builds a dependency graph — a directed acyclic graph (DAG) of files — and Make's job is to walk that graph and do the minimum work required to bring a target up to date.

The One Rule That Drives Everything

Key idea: Make rebuilds a target if and only if the target is missing, or any of its prerequisites is newer than the target (has a more recent modification time). Otherwise it says "up to date" and does nothing.

That's it. No content hashing, no change detection — just timestamps compared recursively. Simple, fast, and exactly right for most build pipelines. (It's also why Make can be fooled by clock skew or by touching files — more on that below.)

Walking the Graph: A Worked Example

Consider this Makefile:

app: main.o util.o
	cc -o app main.o util.o

main.o: main.c main.h
	cc -c main.c -o main.o

util.o: util.c util.h
	cc -c util.c -o util.o

You edit util.c and run make. Here's the decision process, step by step:

  1. Default goal is app. Is app missing or older than a prerequisite? Check its prerequisites first.
  2. main.o — is it older than main.c or main.h? No. Up to date, skip.
  3. util.o — is it older than util.c? Yes (you just edited it). Rebuild util.o.
  4. Now back to app: util.o is now newer than app. Relink app.
app (relink) main.o ✓ up to date util.o — rebuild main.c main.h util.c ✏️ edited util.h

Only util.o is recompiled; main.o is untouched; app is relinked once. On a huge project this is the difference between a 2-second build and a 30-minute one.

Depth-First, Prerequisites First

Make always builds prerequisites before targets, recursively. This means:

  • You never need to order rules in a Makefile for execution — Make figures out the order from the graph.
  • Each prerequisite is built at most once per invocation, even if several targets share it.
  • If a prerequisite can't be built (rule missing, command fails), Make stops and reports the error.

Why Header Dependencies Matter

Notice in the example that main.o depends on main.h and main.c. If you change a header that many files include, you must list it as a prerequisite of each object file, or Make won't know to recompile them. Hand-maintaining these lists is miserable — Lesson 5 shows how compilers generate dependency lists automatically.

Common failure: the "missing dependency" bug. File foo.c includes foo.h, but the Makefile only lists foo.c. Edit foo.h, run make — nothing rebuilds, and you link stale objects. Symptom: weird runtime behavior after a header edit. Cure: automatic dependency generation (Lesson 5).

Phony Targets Revisited — and .DEFAULT_GOAL

.PHONY targets never correspond to files, so Make always runs them. Two more graph tools you'll use:

.DEFAULT_GOAL := all   # choose which target plain `make` builds

.PHONY: all clean test
all: app
clean:
	rm -f app *.o
test: app
	./app --test

Note that test lists app as a prerequisite — so make test builds the binary first, then runs it. That's the idiom for "action that requires the build."

Debugging the Graph

Make gives you great tools for inspecting its decisions:

CommandWhat it shows
make -nPrint the commands it would run, without running them.
make -dMassive debug output — every file considered, every timestamp compared.
make --debug=bBasic debugging: which targets are considered out of date and why.
make -W filePretend file was just modified — useful to see what a change would trigger.
touch file; makeActually bump a file's timestamp to force a rebuild chain.

Limitations of the Timestamp Model

Timestamps are fast but dumb. Three situations to know about:

  • Clock skew: if a source file's timestamp is in the future (bad NTP, timezone mishap, git checkout quirks), Make may never rebuild it. Fix: make clean or touch the sources.
  • Same-second edits: if you edit a source within the same second as its object was built, Make may see equal timestamps and skip the rebuild. Rare, but make -B forces the issue.
  • Content changes with old timestamps: git checkout old-branch can leave files with identical mtimes. A make clean is the reliable reset.
Pro tip: when in doubt, make clean and rebuild. It's the universal reset button — costs a full build, but eliminates the entire class of timestamp confusion.

🧠 Knowledge Check

1. Make rebuilds a target when...

2. If app: main.o util.o, you edit main.c only, and both objects already exist — what does make do?

3. You change util.h, which util.c includes — but util.o's rule only lists util.c as a prerequisite. What happens?

Further Reading