Lesson 20.2 — SCCs and traversal orders: Tarjan, bottom-up and top-down, the CGSCC pass manager

Techniques: Tarjan's strongly connected components (Tarjan 1972) as LLVM's scc_iterator runs it on the call graph; bottom-up (callee-first) and top-down (caller-first) traversal for summary-based and context-propagating analyses; LLVM's CGSCC pass manager over the LazyCallGraph (Carruth et al., LLVM 3.x–23) and its invariants under call-graph mutation · Pebble implements: the SCC list of print<pebble-callgraph> (E1), which must match scc_iterator exactly; bottom-up order in pebble-inline and pebble-funcattrs (E2, E3) · Drill: scc-order · Prerequisites: Lesson 20.1; DFS, pre/postorder (Ch 15); the new pass manager and its CGSCC adaptor (Lesson 12.1) · Time: 5–7 hours

A call graph is a directed graph with cycles (recursion). Interprocedural passes want to visit it in an order in which every function comes after its callees (so a summary of each callee is ready) or before them (so the facts of every caller are known). Cycles make both impossible for individual functions; they become possible for strongly connected components (SCCs), which is why LLVM's interprocedural pipeline is a CGSCC pipeline. The running example is a recursive-descent calculator, calc.c:

int printf(const char *, ...);
static const char *p;
static int next(void) { return *p ? *p++ : 0; }
static int peek(void) { return *p; }
static long expr(void);
static long factor(void) {
  if (peek() == '(') { next(); long v = expr(); next(); return v; }
  return next() - '0';
}
static long term(void) {
  long v = factor();
  while (peek() == '*') { next(); v *= factor(); }
  return v;
}
static long expr(void) {
  long v = term();
  while (peek() == '+') { next(); v += term(); }
  return v;
}
long calc(const char *s) { p = s; return expr(); }
static long power(long b, int e) { return e == 0 ? 1 : b * power(b, e - 1); }
int main(void) { printf("%ld\n", calc("2*(3+4)") + power(2, 5)); return 0; }

Its call graph in the notation of the scc-order drill (functions in LLVM's module order after clang-23 -O1 -Xclang -disable-llvm-passes + sroa; static = internal linkage; declare = a declaration):

calc: expr
static expr: term peek next term
main: calc power printf
declare printf
static power: power
declare llvm.lifetime.start.p0
static term: factor peek next factor
static peek:
static next:
declare llvm.lifetime.end.p0
static factor: peek next expr next next

flowchart TD
  ROOT{{external calling node}} --> calc([calc])
  ROOT --> main([main])
  ROOT --> printf([printf])
  calc --> expr[expr]
  expr --> term[term]
  term --> factor[factor]
  factor --> expr
  factor --> peek[peek]
  factor --> next[next]
  term --> peek
  expr --> next
  main --> calc
  main --> power[power]
  power --> power
  main --> printf

1. Problem and motivation

Tarjan's SCC algorithm

Two functions are in the same SCC when each can reach the other through calls; collapsing SCCs turns the call graph into a DAG, the condensation. Tarjan's 1972 algorithm finds all SCCs in one depth-first search, in linear time, and — the property compilers exploit — emits them in reverse topological order of the condensation: an SCC comes out only after every SCC it calls [Tar72]. LLVM's scc_iterator is an iterative version of it, used by print-callgraph-sccs and by passes on the legacy CallGraph [LLVM-SCCIt]; the LazyCallGraph computes the same components (and "RefSCCs", §2) incrementally [LLVM-LCG]. Your print<pebble-callgraph> (E1) must reproduce scc_iterator's order exactly, which means reproducing its DFS.

Bottom-up and top-down traversal

A summary-based analysis describes each function by a summary — "reads memory only", "never recurses", "returns its second argument plus one" — computed from its body and its callees' summaries. It needs callees first: bottom-up (the order Tarjan emits). Inside a recursive SCC the summaries depend on each other and are solved together by a local fixed point. A context-propagating transformation pushes facts from callers to callees — "every caller passes 4", "every caller is norecurse", "this call site is hot" — and needs callers first: top-down, the reverse order. Sharir and Pnueli's functional approach [SP81] is the theory behind summaries; LLVM runs its inliner, function-attrs, argpromotion and the function simplification pipeline bottom-up in one CGSCC walk, and rpo-function-attrs and IPSCCP's argument propagation top-down [LLVM-Pipelines].

The CGSCC pass manager

A CGSCC pass changes the call graph it is iterating over: the inliner removes call edges and copies the callee's calls into the caller; dead-argument elimination and function specialization create or delete functions; devirtualization turns an indirect call into a direct one. Chandler Carruth's new pass manager therefore walks a LazyCallGraph whose SCCs are updated after every pass, re-queueing the SCCs a pass split or merged, so the walk stays bottom-up for the graph as it is now [LLVM-CGSCC, LLVM-NPM]. Lesson 12.1 introduced the adaptor; this lesson states its invariants.

2. Definitions and algorithms

Definition 20.2.1 (SCC, condensation, recursive SCC)

Let \(G = (V, E)\) be a directed graph. \(u \sim v\) iff \(u \to^{*} v\) and \(v \to^{*} u\); \(\sim\) is an equivalence relation and its classes are the strongly connected components. The condensation \(G/{\sim}\) has one node per SCC and an edge \([u] \to [v]\) for every \(u \to v\) with \([u] \neq [v]\); it is acyclic. An SCC is recursive if it has two or more members or its single member has a self-edge.

Definition 20.2.2 (Bottom-up and top-down orders)

A sequence \(X_1, \dots, X_k\) of all SCCs is bottom-up if every edge of the condensation goes from a later SCC to an earlier one (\(X_i \to X_j\) implies \(j < i\)): callees before callers. Its reverse is top-down.

Algorithm 20.2.3 (Tarjan's SCC algorithm, as scc_iterator runs it)

• Input: a graph with an ordered successor list per node and an ordered list of roots.
• Output: the SCCs reachable from the roots, in the order they are completed; each SCC's members in the order they are popped (its root last).
• Precondition: none.
• Postcondition: the output is exactly the set of SCCs of the reachable subgraph, in bottom-up order (Theorem 20.2.9).
• Invariant: (I1) the stack holds exactly the visited nodes whose SCC has not been emitted, in visiting order; (I2) \(\mathrm{low}(v) = \min(\{\mathrm{idx}(v)\} \cup \{\mathrm{idx}(w) \mid w\) on the stack and reachable from \(v\) by tree edges followed by at most one non-tree edge\(\})\) once \(v\) finishes.

function Tarjan(roots, succs):
    counter ← 0; stack ← []; out ← []
    for r in roots: if r not visited: Visit(r)
    return out

function Visit(v):
    idx(v) ← low(v) ← counter; counter ← counter + 1
    push v; onStack(v) ← true
    for w in succs(v), in order:
        if w not visited:
            Visit(w)
            low(v) ← min(low(v), low(w))            # tree edge
        else if onStack(w):
            low(v) ← min(low(v), idx(w))            # back or cross edge into the current path
        # else: w's SCC was already emitted; ignore
    if low(v) = idx(v):                              # v is the root of an SCC
        scc ← []
        repeat: w ← pop; onStack(w) ← false; append w to scc
        until w = v
        append scc to out

Definition 20.2.4 (LLVM's call-graph traversal)

scc_iterator<CallGraph *> runs Algorithm 20.2.3 on the graph of Algorithm 20.1.3 with the single root \(\mathit{ext}_{in}\), whose successors are the functions that are not local or whose address is taken, in module order; each function's successors are its call sites in instruction order (duplicates kept), an indirect call and a declaration's body leading to \(\mathit{ext}_{out}\) (a sink). Functions that \(\mathit{ext}_{in}\) cannot reach are never visited. print-callgraph-sccs prints the result, including the two pseudo-nodes as external node; print<pebble-callgraph> prints the same SCCs without them (E1).

Algorithm 20.2.5 (Bottom-up summary computation over SCCs)

• Input: a call graph; a lattice \((L, \sqsubseteq)\) of summaries of finite height; a monotone \(\mathrm{body}_f : (F \to L) \to L\) per function (its summary given its callees' summaries); a value \(\mathrm{sum}(g)\) for every function without a body.
• Output: \(\mathrm{sum} : F \to L\), the least fixed point of \(\mathrm{sum}(f) = \mathrm{body}_f(\mathrm{sum})\).
• Precondition: SCCs in bottom-up order (Algorithm 20.2.3).
• Postcondition: Theorem 20.2.10.
• Invariant: when SCC \(X_i\) is processed, \(\mathrm{sum}\) is final on \(X_1 \cup \dots \cup X_{i-1}\) and on external functions.

function BottomUp(SCCs X1 … Xk in bottom-up order):
    for i = 1 … k:
        for f in Xi: sum(f) ← ⊥                     # optimistic start inside the SCC
        repeat                                       # local fixed point (one pass if Xi is not recursive)
            changed ← false
            for f in Xi:
                new ← body_f(sum)                     # callees outside Xi are already final
                if new ≠ sum(f): sum(f) ← new; changed ← true
        until not changed
    return sum

Top-down propagation is the mirror image: visit the SCCs in reverse, and compute each function's context (e.g. the join of the argument values its callers pass) from the contexts of its callers.

Definition 20.2.6 (LazyCallGraph: call and ref edges, RefSCCs)

LazyCallGraph has two kinds of edges: a call edge \(f \to g\) for a direct call, and a ref edge \(f \to g\) when \(f\) merely references \(g\) (stores @g somewhere, passes it as an argument). SCCs are computed over call edges; RefSCCs are the SCCs of call ∪ ref edges, each a DAG of call-SCCs. A ref edge may become a call edge (devirtualization: a later pass turns call %p into call @g); keeping ref edges in the graph guarantees that such a promotion never creates a cycle between two RefSCCs already visited. The CGSCC walk visits RefSCCs in postorder and, inside each, its SCCs in postorder.

Algorithm 20.2.7 (The CGSCC walk with updates, as in ModuleToPostOrderCGSCCPassAdaptor)

• Input: a module, a CGSCC pass pipeline \(P\).
• Output: the module after running \(P\) on every SCC.
• Precondition: each pass reports its graph changes through updateCGAndAnalysisManagerForCGSCCPass.
• Postcondition: every SCC that exists when it is reached has been visited, after every SCC it calls that exists at that time (Proposition 20.2.11).
• Invariant: the worklist holds SCCs in bottom-up order of the current graph; visited SCCs are never reached again from the worklist except when an update splits or merges them.

function CGSCCWalk(M, P):
    LCG ← LazyCallGraph(M)
    for RC in postorder RefSCCs of LCG:
        W ← postorder SCCs of RC                    # a worklist, front = next
        while W ≠ []:
            C ← pop front of W
            if C was invalidated by an update: continue
            for pass in P:
                run pass on C
                UR ← the edges the pass added / removed / promoted
                C ← Update(LCG, C, UR)              # may split C into C1 … Cm (in postorder),
                                                    # re-queue the parts not yet visited in front of W,
                                                    # and invalidate cached analyses of changed SCCs
            if pass structure is devirt<N> and a call became direct: rerun P on C (at most N times)

3. Worked example

Tarjan's SCC algorithm

Algorithm 20.2.3 on calc.c with Definition 20.2.4's root order: the external calling node reaches calc, main, printf and the two intrinsic declarations (every non-static function), in module order. The calls-external node is a sink and is left out of the table. Generated by ./course drill scc-order (its oracle is tarjan in tools/course/lib/ipo.py):

step	event	idx / low	stack (bottom → top)
1	visit calc	idx = low = 0	calc
2	calc → expr: tree edge		calc
3	visit expr	1	calc expr
4	expr → term: tree edge		calc expr
5	visit term	2	calc expr term
6	term → factor: tree edge		calc expr term
7	visit factor	3	calc expr term factor
8	factor → peek: tree edge; visit peek	4	… factor peek
9	low(peek) = idx(peek): pop {peek}		calc expr term factor
10	factor → next: tree edge; visit next	5	… factor next
11	low(next) = idx(next): pop {next}		calc expr term factor
12	factor → expr: on the stack	low(factor) = 1	calc expr term factor
13	factor → next, next: finished, ignored
14	back in term: low(term) = min(2, low(factor)) = 1		calc expr term factor
15	term → peek, next: finished; term → factor: on the stack, idx 3 > 1
16	back in expr: low(expr) = min(1, 1) = 1; expr → peek, next finished; expr → term on the stack
17	low(expr) = idx(expr): pop {factor, term, expr}		calc
18	low(calc) = idx(calc): pop {calc}		—
19	visit main	6	main
20	main → calc: finished, ignored		main
21	main → power: tree edge; visit power	7	main power
22	power → power: on the stack (self-loop)	low stays 7	main power
23	low(power) = idx(power): pop {power}		main
24	main → printf: tree edge; visit printf; pop {printf}	8	main
25	pop {main}		—
26	visit and pop {llvm.lifetime.start.p0}, then {llvm.lifetime.end.p0}	9, 10	—

The emission order — {peek}, {next}, {factor, term, expr}, {calc}, {power}, {printf}, {main}, then the two intrinsics — is bottom-up: main comes after everything it calls, and the parser's mutual recursion is one recursive SCC, as is power's self-call. Members are listed in pop order, factor term expr, with the SCC's root expr last — the order LLVM prints (§7).

Try it

./course drill scc-order --seed 4 --difficulty hard --solution prints this table for a random module with internal, address-taken and declared functions; --difficulty medium also asks which functions are recursive.

Bottom-up and top-down traversal

Bottom-up (Algorithm 20.2.5) with the summary "may write memory" (the lattice \(\{\mathrm{none} \sqsubset \mathrm{read} \sqsubset \mathrm{write}\}\) of Lesson 20.6): peek reads *p: read. next writes p (p++): write. The SCC {factor, term, expr} starts at ⊥ = none for all three; one pass joins their own effects (none) with their callees outside the SCC (peek: read, next: write): all three become write; a second pass changes nothing. calc writes p: write. power has no memory access; its SCC is recursive, so the local fixed point runs: pass 1 gives none (the self-call contributes the optimistic ⊥), pass 2 confirms: none. main calls printf (a declaration: write): write. LLVM's function-attrs agrees: power gets memory(none) (§7).

Top-down, the other direction, with the context "every caller is norecurse" (the rule of rpo-function-attrs, §7): visit {main}, {printf}, {power}, {calc}, {factor, term, expr}, …; a non-recursive SCC \(\{f\}\) whose callers are all norecurse cannot be re-entered, so \(f\) is norecurse even if it calls unknown code that cannot call it back (internal, address not taken). In calc.c nothing new follows, because main itself is not known to be norecurse; in the td.c box of §7 it is, and two helpers that call an unknown external function become norecurse.

The CGSCC pass manager

Running cgscc(inline) on calc.c (box in §7): the walk visits {peek}, {next}, then {expr, term, factor}. There the inliner (its remarks, -pass-remarks=inline) inlines term into expr twice, peek and next into factor and expr, and then factor into expr three times. Afterwards term and factor have no callers left (both are internal, and are deleted), and expr calls itself through the inlined copies of factor's call to expr. The old SCC has become {expr} with a self-loop: updateCGAndAnalysisManagerForCGSCCPass recomputes the SCCs of the old component, re-queues the new one, and invalidates the cached analyses of the functions that changed — the log shows InlinerPass on (expr) as a separate visit. Then {calc}, {power}, {main} follow, and calc is inlined into main. Seven SCC visits for eight defined functions.

4. Invariants and correctness

Lemma 20.2.8 (The SCC root is the first visited member, and pops exactly its SCC)

In Algorithm 20.2.3, let \(r\) be the node of an SCC \(X\) with the smallest \(\mathrm{idx}\). Then every member of \(X\) is a DFS descendant of \(r\), \(\mathrm{low}(v) < \mathrm{idx}(v)\) for every \(v \in X \setminus \{r\}\), \(\mathrm{low}(r) = \mathrm{idx}(r)\), and when \(r\) finishes the nodes above \(r\) on the stack are exactly \(X \setminus \{r\}\).

Proof sketch (full proof: [Tar72, §3])

Descendants. When \(r\) is visited, every other \(v \in X\) is unvisited and reachable from \(r\) along a path inside \(X\) (all its nodes are in \(X\) and unvisited); by the white-path theorem of DFS, \(v\) becomes a descendant of \(r\). Low values. For \(v \in X \setminus \{r\}\) there is a path \(v \to^{+} r\); follow it until the first edge leaving \(v\)'s DFS subtree: its target is on the stack (it is in \(X\), and \(X\) has not been popped because \(r\) has not finished), with a smaller index, so \(\mathrm{low}(v) < \mathrm{idx}(v)\) by the two update rules. For \(r\): any node on the stack reachable from \(r\) with a smaller index would be in \(X\) (it reaches \(r\) through the stack's tree path) and would contradict the minimality of \(\mathrm{idx}(r)\). Popping. Nodes above \(r\) on the stack were visited after \(r\) and not popped; each is either in \(X\), or in an SCC whose root is a descendant of \(r\) that has already finished — and that root would have popped it. So exactly \(X \setminus \{r\}\) remains above \(r\).

Theorem 20.2.9 (Tarjan: correctness, order, cost)

Algorithm 20.2.3 emits every SCC of the subgraph reachable from the roots exactly once, and in bottom-up order (Definition 20.2.2). It runs in \(O(n + e)\) time for \(n\) nodes and \(e\) edges.

Proof sketch (full proof: [Tar72, §3])

Each SCC exactly once. By Lemma 20.2.8 an SCC is emitted when its root finishes, and the pop removes exactly its members; every node is visited once and popped once, so no SCC is emitted twice or split.

Order. Tarjan's stack invariant [Tar72, §3]: every node on the stack reaches, in \(G\), the node currently being visited (its SCC root is on the current DFS path, and the path is made of tree edges). Let \(X \to Y\) be a condensation edge through \(u \to w\), \(u \in X\), \(w \in Y\), and consider the moment \(X\)'s root \(r_X\) finishes. All nodes reachable from \(r_X\) are visited by then (a DFS property), in particular \(w\). If \(Y\) had not been emitted, its members would still be on the stack (invariant I1), below \(r_X\) (the nodes above \(r_X\) are \(X \setminus \{r_X\}\) by Lemma 20.2.8). By the stack invariant, \(r_Y\) reaches \(r_X\); and \(r_X\) reaches \(w\), which reaches \(r_Y\). Then \(r_X \sim r_Y\) and \(X = Y\), a contradiction. So \(Y\) was emitted before \(X\).

Cost. Each node is visited once; each edge is examined once, with \(O(1)\) work; each node is pushed and popped once.

Theorem 20.2.10 (Bottom-up summaries compute the least fixed point)

Let every \(\mathrm{body}_f\) be monotone on a lattice of finite height and depend only on the summaries of \(f\)'s callees. Algorithm 20.2.5 returns the least fixed point of the whole system \(\mathrm{sum}(f) = \mathrm{body}_f(\mathrm{sum})\) for \(f \in F\).

Proof

Let \(\mathrm{sum}^{\ast}\) be the least fixed point (it exists by Knaster–Tarski; Kleene iteration from ⊥ reaches it in finitely many steps, Lesson 14.1). Induction on \(i\): after processing \(X_i\), \(\mathrm{sum} = \mathrm{sum}^{\ast}\) on \(X_1 \cup \dots \cup X_i\). Base: nothing processed. Step: by Definition 20.2.2 every callee of a function in \(X_i\) lies in \(X_i\) or in some \(X_j\), \(j < i\), where \(\mathrm{sum} = \mathrm{sum}^{\ast}\) by the hypothesis. So the equations restricted to \(X_i\), with the other summaries fixed to their final values, form a monotone system in the variables of \(X_i\) alone. The local loop is Kleene iteration of that system from ⊥ (round-robin, which reaches the same least fixed point); it terminates by finite height. Its least solution \(\ell\) equals \(\mathrm{sum}^{\ast}\) restricted to \(X_i\). (\(\le\)) \(\mathrm{sum}^{\ast}\) restricted to \(X_i\) is a local solution, so the least one is below it. (\(\ge\)) Let \(P = X_1 \cup \dots \cup X_i\). The equations of \(P\) read only summaries in \(P\) (Definition 20.2.2), so the Kleene iterates of the whole system, restricted to \(P\), are the Kleene iterates of the subsystem on \(P\), and \(\mathrm{sum}^{\ast}\) restricted to \(P\) is the least solution of that subsystem. The vector equal to \(\mathrm{sum}^{\ast}\) on \(X_1 \cup \dots \cup X_{i-1}\) and to \(\ell\) on \(X_i\) is also a solution of it (the earlier SCCs' equations do not read \(X_i\); \(\ell\) solves \(X_i\)'s equations with those values). So \(\mathrm{sum}^{\ast} \le \ell\) on \(X_i\). Hence equality. For a non-recursive SCC \(\{f\}\), \(\mathrm{body}_f\) does not read \(\mathrm{sum}(f)\) and one evaluation suffices.

Proposition 20.2.11 (Inlining keeps the walk bottom-up)

Let the CGSCC walk visit SCC \(X\) and inline into \(f \in X\) a call to a function \(g\) that is either in an SCC \(Y\) visited earlier or in \(X\) itself. The call edges this adds go from \(f\) to callees of \(g\), all in \(X\) or in SCCs visited before \(X\); so no two SCCs merge, and the SCCs not yet visited keep a bottom-up order. Only when \(g \in X\) can the removed edge \(f \to g\) split \(X\); visiting the parts of \(X\) in their own bottom-up order (Algorithm 20.2.7's Update) restores the invariant.

Proof

After inlining, \(f\) contains copies of \(g\)'s calls, so each new edge is \(f \to h\) with \(g \to h\). If \(g \in Y\), then \(h\) lies in \(Y\) or in an SCC emitted before \(Y\) (Theorem 20.2.9); if \(g \in X\), then \(h \in X\) or \(h\) lies in an SCC emitted before \(X\). In every case \(h\) is in \(X\) or already visited, and a visited SCC cannot reach \(X\) (bottom-up order), so the new edge closes no cycle outside \(X\): no SCCs merge, and no unvisited SCC gains a callee it did not have before, so the order of the rest of the worklist stays bottom-up. Removing edges never merges SCCs. Removing \(f \to g\) with \(g \in Y \neq X\) leaves \(X\)'s internal edges unchanged; removing it with \(g \in X\) may split \(X\), and the parts are computed by Tarjan on \(X\)'s members, whose output is bottom-up (Theorem 20.2.9). Inlining inside \(X\) can repeat without end (a copy of a recursive call can be inlined again), which is why inliners refuse recursive calls or bound them with an inline history (Lesson 20.3); the walk of §3 splits {expr, term, factor} exactly this way.

Adding a call edge to an unvisited SCC breaks the walk

A pass that turns an indirect call into call @h where \(h\) is in an SCC not yet visited (a caller of the current SCC, say) creates a cycle the walk has already passed. LLVM prevents this with ref edges (Definition 20.2.6): @h was already referenced, so \(h\) is in the same or an earlier RefSCC, and the promotion is handled by merging SCCs inside the RefSCC (RefSCC::switchInternalEdgeToCall).

5. Complexity

\(n\) = functions, \(e\) = call sites (edges), \(h\) = height of the summary lattice, \(k_X\) = size of an SCC.

Technique	Time (worst)	Time (typical)	Space	Justification
Tarjan	\(O(n + e)\)	linear, one DFS	\(O(n)\) stack and indices	Theorem 20.2.9; scc_iterator is iterative, so no recursion depth limit
Bottom-up summaries	\(O(\sum_X h \cdot k_X \cdot \mathrm{cost}(X))\)	one evaluation per non-recursive function	one summary per function	each summary in \(X\) rises at most \(h\) times, each round re-evaluates \(k_X\) bodies
CGSCC walk	\(O(\text{passes} \times (n + e))\) plus updates	near-linear; devirt repeats ≤ \(N\) (4 in default<O2>)	analyses cached per SCC and function	each SCC visited once, plus the parts of every split SCC; devirt<N> bounds re-runs

Pathological family. For summaries: a recursive SCC of \(k\) functions in a ring \(f_1 \to f_2 \to \dots \to f_k \to f_1\) (\(f_i\) calls \(f_{i+1}\)), where only \(f_1\) writes memory, and a round-robin loop that visits \(f_1, f_2, \dots, f_k\) in that order. Round 1 makes \(f_1\) and \(f_k\) (which calls \(f_1\)) write; each further round moves the fact one function backwards, to \(f_{k-1}\), then \(f_{k-2}\), …, so the local fixed point takes \(k - 1\) rounds plus a confirming one: \(\Theta(k^2)\) body evaluations. LLVM's FunctionAttrs avoids it by joining the effects of all members at once (Lesson 20.6, Algorithm 20.6.5), which is exact for any analysis whose summary is shared by the whole SCC. For the CGSCC walk: an SCC that the inliner splits one function at a time is revisited once per split — \(O(k)\) extra visits for \(k\) members.

At scale. LLVM builds the lazy call graph once per module and updates it incrementally; -debug-pass-manager on the calc example shows seven SCC visits for eight defined functions (the re-visit of the split-off {expr} included, §7).

6. Variants and refinements

• Kosaraju / Sharir's two-pass algorithm [Sha81]: two DFS passes (the second on the reverse graph) — simpler to explain, twice the traversals, and it emits SCCs in topological (top-down) order.
• Pearce's space-efficient Tarjan [Pea16]: one index array instead of index + low + on-stack flags — the same order, less memory.
• Nuutila–Soisalon-Soininen [NS94]: avoids pushing trivial (single-node) SCCs on the stack; faster on call graphs, which are mostly trivial SCCs.
• Incremental SCC maintenance (LazyCallGraph): updates the components on edge insertion and deletion instead of recomputing; it trades a complex implementation for a walk that can mutate the graph (Algorithm 20.2.7).
• Top-down with a global fixed point (GCC's IPA passes): compute summaries bottom-up at compile time, propagate top-down at "link" time over the whole program's call graph (ipa-cp, ipa-modref propagation), then transform per function — the model ThinLTO also uses (Lesson 20.9).

7. In real compilers

Tarjan's SCC algorithm

LLVM: llvm/include/llvm/ADT/SCCIterator.h — scc_iterator::DFSVisitOne, DFSVisitChildren and GetNextSCC are Algorithm 20.2.3 with an explicit stack of (node, next child) pairs; a visited node whose SCC was emitted gets the visit number ~0U, so the min ignores it (the "else" branch of Visit) [LLVM-SCCIt]. CallGraphSCCsPrinterPass in llvm/lib/Analysis/CallGraph.cpp prints it [LLVM-CG]. GCC orders its IPA passes with ipa_reduced_postorder (ipa-utils.cc), which also collapses SCCs.

scc_iterator on the calculator

Reproduce (clang 23.1.2, opt 23.1.2; calc.c as in the introduction):

clang-23 -O1 -Xclang -disable-llvm-passes -fno-discard-value-names -S -emit-llvm calc.c -o - | opt -passes=sroa -S -o calc.ll
opt -passes=print-callgraph-sccs -disable-output calc.ll

Output:

SCCs for the program in PostOrder:
SCC #1: peek
SCC #2: next
SCC #3: factor, term, expr
SCC #4: calc
SCC #5: power (Has self-loop).
SCC #6: external node
SCC #7: printf
SCC #8: main
SCC #9: llvm.lifetime.start.p0
SCC #10: llvm.lifetime.end.p0
SCC #11: external node

What to notice: exactly the emission order of the §3 trace, members in pop order (expr, the root, last). The two external node lines are the pseudo-nodes of Definition 20.2.4: #6 is \(\mathit{ext}_{out}\), first reached from printf (a declaration may call anything), #11 is the root \(\mathit{ext}_{in}\), which finishes last. print<pebble-callgraph> must print #1–#5 and #7–#10 in this order (E1; tests/ch20/lit/callgraph-vs-llvm.test).

Bottom-up and top-down traversal

LLVM: llvm/lib/Transforms/IPO/FunctionAttrs.cpp — PostOrderFunctionAttrsPass::run derives attributes bottom-up per SCC (deriveAttrsInPostOrder), and ReversePostOrderFunctionAttrsPass::run propagates norecurse top-down (addNoRecurseAttrsTopDown) [LLVM-FunctionAttrs]; llvm/lib/Passes/PassBuilderPipelines.cpp — buildInlinerPipeline wraps the bottom-up passes in one CGSCC adaptor [LLVM-Pipelines]. GCC: ipa-modref.cc computes summaries bottom-up and propagates them over the IPA call graph [GCC-Modref].

Bottom-up memory effects, top-down norecurse

Reproduce (clang 23.1.2, opt 23.1.2; calc.ll from the previous box):

opt -passes='cgscc(function-attrs)' -debug-pass-manager -disable-output calc.ll 2>&1 | grep 'Running pass: PostOrder'
opt -passes='cgscc(function-attrs)' -S calc.ll | grep -E '^define internal i64 @power|^attributes #3' | sed 's/ uwtable .*/ uwtable … }/'
cat > td.ll <<'EOF'
declare void @log_it(i32)
define internal i32 @helper(i32 %x) {
  call void @log_it(i32 %x)
  %r = add i32 %x, 1
  ret i32 %r
}
define internal i32 @driver(i32 %n) {
  %a = call i32 @helper(i32 %n)
  %b = call i32 @helper(i32 %a)
  ret i32 %b
}
define i32 @main() norecurse {
  %r = call i32 @driver(i32 3)
  ret i32 %r
}
EOF
opt -passes='rpo-function-attrs' -S td.ll | grep -E '^define|^attributes'

Output:

Running pass: PostOrderFunctionAttrsPass on (peek) (1 node)
Running pass: PostOrderFunctionAttrsPass on (next) (1 node)
Running pass: PostOrderFunctionAttrsPass on (expr, term, factor) (3 nodes)
Running pass: PostOrderFunctionAttrsPass on (calc) (1 node)
Running pass: PostOrderFunctionAttrsPass on (power) (1 node)
Running pass: PostOrderFunctionAttrsPass on (main) (1 node)
define internal i64 @power(i64 noundef %b, i32 noundef %e) #3 {
attributes #3 = { nofree nosync nounwind memory(none) uwtable … }
define internal i32 @helper(i32 %x) #0 {
define internal i32 @driver(i32 %n) #0 {
define i32 @main() #0 {
attributes #0 = { norecurse }

What to notice: the new pass manager walks the LazyCallGraph's SCCs bottom-up (its member order differs from scc_iterator's; only the SCC order is specified), and the recursive power gets memory(none) from the optimistic start inside its SCC, as in §3. In td.ll, helper calls the unknown @log_it, so no bottom-up rule can make it norecurse; top-down, both of its callers' callers are norecurse and helper is internal and not address-taken, so nothing can re-enter it.

The CGSCC pass manager

LLVM: llvm/lib/Analysis/CGSCCPassManager.cpp — ModuleToPostOrderCGSCCPassAdaptor::run (the walk), updateCGAndAnalysisManagerForCGSCCPass (the update after a function pass changed calls), DevirtSCCRepeatedPass::run (re-running when an indirect call became direct); llvm/lib/Analysis/LazyCallGraph.cpp — RefSCC::switchInternalEdgeToRef splits SCCs, RefSCC::switchInternalEdgeToCall merges them [LLVM-CGSCC, LLVM-LCG]. GCC has no CGSCC manager: its IPA passes analyze the whole call graph, then each function is optimized in a fixed order.

The inliner splits an SCC, and the walk revisits the part

Reproduce (opt 23.1.2; calc.ll from the first box):

opt -passes='cgscc(inline)' -debug-pass-manager -disable-output calc.ll 2>&1 | grep -E 'Running pass: InlinerPass'
opt -passes=print-lcg -disable-output calc.ll 2>&1 | sed -n '/RefSCC/,$p' | head -n 14

Output:

Running pass: InlinerPass on (peek) (1 node)
Running pass: InlinerPass on (next) (1 node)
Running pass: InlinerPass on (expr, term, factor) (3 nodes)
Running pass: InlinerPass on (expr) (1 node)
Running pass: InlinerPass on (calc) (1 node)
Running pass: InlinerPass on (power) (1 node)
Running pass: InlinerPass on (main) (1 node)
  RefSCC with 1 call SCCs:
    SCC with 1 functions:
      peek

  RefSCC with 1 call SCCs:
    SCC with 1 functions:
      next

  RefSCC with 1 call SCCs:
    SCC with 3 functions:
      expr
      term
      factor

What to notice: after inlining term and factor into expr (§3), the updated graph has a new SCC {expr} (Proposition 20.2.11), which is visited in its own right before calc. print-lcg shows the RefSCC/SCC nesting of Definition 20.2.6 before any pass ran (the first three RefSCCs of its postorder).

Find where LLVM does it. Open llvm/include/llvm/ADT/SCCIterator.h and find how scc_iterator marks a node whose SCC has already been emitted, so that later min computations ignore it. What value does it store? (Quiz llvm-where-scc-done.)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Tarjan's SCC algorithm	All SCCs, bottom-up order, one pass	\(O(n + e)\) · one DFS	Deterministic given successor order (matters for reproducible pipelines)	Low (iterative version: medium)	scc_iterator, LazyCallGraph, GCC ipa_reduced_postorder, print<pebble-callgraph>
Bottom-up / top-down traversal	Least fixed point of summary systems (Theorem 20.2.10); top-down for caller contexts	one evaluation per non-recursive function	Summaries are reusable (ThinLTO, caching)	Low given SCCs	FunctionAttrs, inliner, modref (bottom-up); IPSCCP args, rpo-function-attrs, ipa-cp (top-down)
CGSCC pass manager	Bottom-up order under mutation (Proposition 20.2.11)	near-linear, bounded devirt repeats	Pass-level interleaving: each SCC fully simplified before its callers see it	High (incremental SCCs, analysis invalidation)	LLVM's default<O2> inliner pipeline

Choose Tarjan when you need SCCs or a bottom-up order at all: it is the standard. Choose bottom-up traversal when the analysis summarizes callees (attributes, side effects, inline costs); top-down when facts flow from callers (constant arguments, hotness, norecurse of callers). Choose a CGSCC pass manager when transformations that change the call graph (inlining, devirtualization) must interleave with per-function simplification, so each caller sees simplified callees.

9. Assessment

• Quiz (./course quiz 20): scc-order-calc, llvm-where-scc-done (tag scc-tarjan); bottomup-summary, topdown-norecurse (tag traversal); cgscc-split, cgscc-ref-edges (tag cgscc).
• Drill: ./course drill scc-order (easy: the SCC order; medium: also recursion; hard: also the lowlinks). The traversal lessons are practiced by funcattrs-fixpoint (a bottom-up summary, Lesson 20.6); the CGSCC walk's updates have no drill — they are the SCC computation re-run on the changed component — and are assessed by cgscc-split.
• Flashcards: tags scc-tarjan, traversal, cgscc.
• Exercises: E1 (the SCC order must equal scc_iterator's); the bottom-up order is used by E2 and E3.

References

See the chapter references.