Lesson 20.6 — Attribute inference and signature transformations: FunctionAttrs, dead arguments, argument promotion, GlobalOpt

Techniques: attribute inference as an SCC-based fixed point — memory effects (memory(none)/readnone, memory(read)/readonly), norecurse, nounwind, nofree, willreturn, argument captures(none)/nocapture — as in LLVM's FunctionAttrs (side-effect analysis after Banning 1979 and Cooper & Kennedy 1988); dead-argument and dead-return-value elimination (deadargelim); argument promotion (argpromotion); global optimization (globalopt: constant globals, stored-once globals, scalar replacement of aggregate globals, dead globals) · Pebble implements: pebble-funcattrs — memory(none)/memory(read) and norecurse, bottom-up over SCCs (E3) · Drill: funcattrs-fixpoint · Prerequisites: Lesson 20.2 (bottom-up summaries, Theorem 20.2.10); lattices (Ch 14); escape analysis (Ch 19) · Time: 6–8 hours

The transformations of this lesson are individually small and collectively important. Attributes such as memory(none) or norecurse are facts about a function that every caller's optimizer can use without seeing the body — a call to a memory(none) function does not clobber any load, can be hoisted out of a loop and deleted if its result is unused. The signature transformations change a function's interface when all its callers are known: drop parameters nobody uses, pass a value instead of a pointer to it. The running example of attribute inference is a small module in the drill's notation (a function, the memory effect of its own instructions, its callees):

main  [write]: parse eval
parse [read]:  next
next  [none]:
eval  [none]:  apply sqrt
apply [none]:  eval
declare sqrt readnone norecurse

1. Problem and motivation

Attribute inference

The question "may this call read or write memory the caller can see?" appears everywhere in the optimizer: alias analysis asks it for every call, LICM before hoisting across one, DSE before deleting a store. Answering it at every call by re-analyzing the callee is too slow; the answer is a function summary, and LLVM stores summaries as attributes in the IR. Banning's 1979 side-effect analysis and Cooper and Kennedy's linear-time MOD/REF computation established the interprocedural problem [Ban79, CK88]; LLVM's FunctionAttrs computes memory effects, norecurse, nounwind, nofree, nosync, willreturn and per-argument attributes (captures(none), readonly, returned, nonnull) bottom-up over the SCCs of the call graph (Lesson 20.2), treating each SCC optimistically [LLVM-FunctionAttrs]. pebble-funcattrs (E3) infers the memory attribute and norecurse the same way; tests/ch20/lit/funcattrs-vs-llvm.test checks that it never claims more than LLVM proves.

Dead-argument elimination

A parameter that the body never uses still costs a register (and code to compute the argument) at every call; a return value no caller uses still keeps the computation alive in the callee. When all call sites are known — internal linkage, address not taken — deadargelim rewrites the function's type and every call [LLVM-DAE]. It is the interprocedural analogue of dead-code elimination; it often cleans up after IPSCCP, which leaves constant arguments that the callee no longer reads (Lesson 20.5).

Argument promotion

Passing a small structure or a scalar by pointer forces it into memory in the caller and a load in the callee, and hides the value from both functions' scalar optimizations. When a pointer argument is only loaded from (never stored through, never escaping) and every caller is known, argpromotion passes the loaded values instead [LLVM-ArgPromotion]. After it, SROA in the caller can remove the stack slot entirely.

Global optimization

A global variable is, to the optimizer, memory anyone may write. globalopt looks at all uses of internal globals in the module: a global never stored to is a constant (its initializer); a global only ever stored to is dead; a structure global whose fields are only accessed with constant indices can be split into one global per field (scalar replacement of aggregates for globals, the global version of SROA); a global stored once with a known value, or only ever holding two values, can be simplified further [LLVM-GlobalOpt].

2. Definitions and algorithms

Definition 20.6.1 (Memory-effect lattice)

\(\mathcal{M} = \{\mathrm{none} \sqsubset \mathrm{read} \sqsubset \mathrm{write}\}\) with join \(\sqcup\) = maximum. For a function \(f\), an effect \(m \in \mathcal{M}\) is sound if no execution of \(f\) (including its callees) writes memory visible to the caller when \(m \ne \mathrm{write}\), and none reads such memory when \(m = \mathrm{none}\). Memory visible to the caller is everything except \(f\)'s own stack slots (allocas), which do not survive the activation. LLVM's memory(...) attribute refines \(\mathcal{M}\) per location kind (argument memory, inaccessible memory, other); \(\mathrm{none}\) is memory(none) (formerly readnone), \(\mathrm{read}\) is memory(read) (formerly readonly).

Definition 20.6.2 (Local effect)

The local effect \(\mathrm{loc}(f)\) is the join over \(f\)'s instructions of: \(\mathrm{read}\) for a simple load whose underlying object is not an alloca of \(f\); \(\mathrm{write}\) for a store to such an object, for any volatile or atomic access, and for any other instruction that may write memory; the call site's own attributes for a call to a declaration or through a pointer (an unknown callee: \(\mathrm{write}\)); and nothing for calls to defined functions, whose effect enters through the equation below.

Definition 20.6.3 (Effect equations)

For every defined function \(f\): \(\mathrm{eff}(f) = \mathrm{loc}(f) \sqcup \bigsqcup_{g \in \mathrm{callees}(f)} \mathrm{eff}(g)\), where a declaration \(g\) contributes its declared attribute (none: \(\mathrm{write}\)). The inferred effect is the least solution. Its SCC form: for an SCC \(X\) in bottom-up order, \(\mathrm{eff}(X) = \bigsqcup_{f \in X} \big(\mathrm{loc}(f) \sqcup \bigsqcup_{g \in \mathrm{callees}(f) \setminus X} \mathrm{eff}(g)\big)\) and \(\mathrm{eff}(f) = \mathrm{eff}(X)\) for \(f \in X\).

Definition 20.6.4 (norecurse)

\(f\) is norecurse if no execution has two activations of \(f\) on the stack at once. The bottom-up sufficient condition: \(f\)'s SCC is \(\{f\}\), \(f\) has no self-call, and every call in \(f\) is a direct call to a function that is norecurse (or a declaration marked nocallback, which cannot call back into the module).

Algorithm 20.6.5 (SCC-based attribute inference, as in FunctionAttrs and pebble-funcattrs)

• Input: a module; its SCCs in bottom-up order (Algorithm 20.2.3, all functions).
• Output: memory(none) / memory(read) and norecurse added where Definitions 20.6.3–20.6.4 allow.
• Precondition: callee attributes of earlier SCCs are final when an SCC is processed; declarations carry their declared attributes; functions that are optnone or may be replaced at link time (no exact definition) are not analyzed, and an SCC containing one is skipped.
• Postcondition: every attribute added is sound (Theorem 20.6.6) and equals the least solution of Definition 20.6.3 on the analyzed functions (Theorem 20.2.10).
• Invariant: when SCC \(X\) is processed, every call leaving \(X\) reads a final attribute.

function InferAttributes(M):
    for X in SCCs of M, bottom-up:
        if some f ∈ X is a declaration, optnone or not an exact definition: continue
        e ← none
        for f in X:
            for each instruction I of f:
                if I is a call to g ∈ X (no operand bundles): continue       # optimistic inside the SCC
                if I is a call:  e ← e ⊔ EffectOfCall(I)                        # callee / call-site attributes
                else if I is a simple load:  if not LocalAlloca(I.ptr): e ← e ⊔ read
                else if I is a simple store: if not LocalAlloca(I.ptr): e ← write
                else if I may write memory (volatile, atomic, …): e ← write
                else if I may read memory: e ← e ⊔ read
        if e ≠ write: for f in X: f.memory ← f.memory ∩ (e = none ? none : read)
        if X = {f} and f has no self-call and every call in f is direct to a norecurse function
           (or to a nocallback declaration): mark f norecurse
function LocalAlloca(p): return underlying object of p is an alloca of this function

Theorem 20.6.6 (Attribute inference is sound)

Assume the attributes of declarations are sound, that a declaration marked norecurse or nocallback never calls a function defined in the module (true of library functions such as sqrt; LLVM makes the same assumption), and that a defined function that already carries norecurse satisfies it in the LangRef's sense — no possible call path leads from it back to itself — so, if \(f\) calls it, no call path leads from it to \(f\). Then every memory and norecurse attribute Algorithm 20.6.5 adds is sound (Definitions 20.6.1 and 20.6.4).

Proof

Memory. Let \(\mathrm{eff}^{\ast}\) be the least solution of Definition 20.6.3, which Algorithm 20.6.5 computes (Theorem 20.2.10: the lattice has height 3 and \(\mathrm{eff}(f)\) is a monotone join of its callees'; joining over the whole SCC at once gives the same value, because all members of an SCC reach each other and so have equal effects in the least solution). By induction on the length of an execution of \(f\), every visible-memory access it makes is allowed by \(\mathrm{eff}^{\ast}(f)\). An access made by an instruction of \(f\) itself is allowed by \(\mathrm{loc}(f) \sqsubseteq \mathrm{eff}^{\ast}(f)\) — accesses to \(f\)'s own allocas are not visible (Definition 20.6.1). An access made inside a call to a defined \(g\) is allowed by \(\mathrm{eff}^{\ast}(g) \sqsubseteq \mathrm{eff}^{\ast}(f)\) (induction hypothesis: a shorter execution); inside a declaration, by its sound declared attribute; an unknown callee is \(\mathrm{write}\), which allows everything. The optimistic start inside an SCC is not an assumption about executions: it is the start of a Kleene iteration, whose limit is a fixed point, and every fixed point satisfies the inequalities used.

norecurse. First, a lemma by induction on the bottom-up order: if \(g\) is marked norecurse by the rule, every chain of calls that starts in an activation of \(g\) only enters functions of \(\mathrm{Reach}(g)\), the functions reachable from \(g\) in the call graph. Indeed all of \(g\)'s calls are direct, to functions marked norecurse earlier (whose chains stay in their own \(\mathrm{Reach}\), a subset of \(\mathrm{Reach}(g)\)), to declarations that call nothing in the module, or to functions that carried norecurse already (whose chains, by assumption, never reach a caller of theirs — in particular never \(f\) below). Now let \(f\) be marked, and suppose an activation \(A\) of \(f\) leads to a second activation of \(f\). The chain leaves \(A\)'s body through some direct call to \(g_1 \neq f\) (no self-call), and from then on stays in \(\mathrm{Reach}(g_1)\), so \(f \in \mathrm{Reach}(g_1)\). With \(f \to g_1\) this puts \(g_1\) in \(f\)'s SCC, contradicting \(X = \{f\}\).

Definition 20.6.7 (Dead argument, dead return value)

Let \(f\) have local linkage and no address-taken use, so its call sites are exactly the direct calls in the module. Parameter \(p_i\) is live if it is used by an instruction of \(f\) other than (a) passing it as argument \(j\) to a call of an internal function \(g\) whose \(p_j\) is dead, or (b) returning it from \(f\) when \(f\)'s return value is dead; otherwise it is dead. \(f\)'s return value is dead if every call site's result is unused (or only passed to dead arguments / returned from functions with dead returns). Liveness is the least fixed point of these mutually recursive rules (start with everything dead, mark live on real uses).

Algorithm 20.6.8 (Dead-argument elimination)

• Input: a module.
• Output: internal functions without their dead parameters and dead return values; call sites rewritten.
• Precondition: only functions whose every call site is known are changed (local linkage, no address taken, no musttail users, not varargs with a va_start).
• Postcondition: every removed parameter/return value was dead (Definition 20.6.7); semantics preserved.
• Invariant: the Live set only grows; a use recorded as "live if \(X\) is live" is resolved when \(X\) becomes live.

function DeadArgElim(M):
    Live ← ∅;  Uses ← {}                                     # Uses[X]: values that are live if X is
    for f in M with all call sites known:
        for each parameter p of f and the return value R(f):
            for each use u of p:
                if u is an argument of a call to internal g at position j: Uses[(g, j)] += p
                else if u is `ret p` and f's return is not yet known live: Uses[R(f)] += p
                else: MarkLive(p)
            for each call site c of f whose result is used by something other than the above: MarkLive(R(f))
    for f with all call sites known:
        NF ← f with the dead parameters and (if dead) the return value removed
        for each call c of f: replace by a call of NF without the dead arguments; if R(f) was dead,
            replace uses of c's result (only in dead positions) by poison
function MarkLive(X): if X ∉ Live: Live ∪= {X}; for Y in Uses[X]: MarkLive(Y)

Algorithm 20.6.9 (Argument promotion)

• Input: an internal function \(f\), not address-taken; a pointer parameter \(p\).
• Output: \(f'\) taking the loaded values \(v_1, \dots, v_k\) (one per distinct offset/type loaded from \(p\)) instead of \(p\).
• Precondition: (1) every use of \(p\) in \(f\) is a load at a constant offset (or a GEP to one); (2) no store in \(f\) (or in its callees) may write those locations before the loads (checked with alias analysis and the callee attributes of this lesson); (3) each loaded location is guaranteed dereferenceable at every call site (the argument has dereferenceable, or \(f\) loads it unconditionally in its entry block), so loading it early in the caller cannot trap; (4) at most max-elements (3) values.
• Postcondition: \(f'\) computes what \(f\) computed; each call site loads \(v_1, \dots, v_k\) just before the call.
• Invariant: the call graph is unchanged except that \(f\) is replaced by \(f'\) (a CGSCC-level transformation).

function PromoteArgument(f, p):
    parts ← { (offset, type) of each load from p }             # fail on any other use of p
    if not NoClobberBetweenEntryAndLoads(f, parts) or not SafeToLoadAtCallSites(f, parts): return
    f' ← f with parameter p replaced by one parameter per part
    in f': replace each load from p at (offset, type) by the corresponding parameter
    for each call site c of f:
        before c: load each part from the actual argument at its offset
        replace c by a call of f' with the loaded values

Algorithm 20.6.10 (GlobalOpt's main rules)

• Input: a module; for each internal global \(G\), the list of its uses.
• Output: the simplified module.
• Precondition: \(G\) has local linkage (every access is in the module) and its address does not escape (every use is a load, a store to \(G\), or a GEP with constant indices feeding those).
• Postcondition: each rule applied preserves every load's value in every execution.
• Invariant: the rules are applied until none applies (a fixed point: each rule removes or simplifies a use).

function GlobalOpt(M):
    repeat
        for each internal global G whose address does not escape:
            if G is never stored to:            mark G constant; fold loads to its initializer
            else if G is never loaded:          delete the stores and G                       # dead global
            else if G is an aggregate accessed only via constant-index GEPs:
                                                split G into one global per accessed field (SRA)
            else if G is stored only with one value V besides its initializer:
                                                turn G into an i1 flag "has been stored" and fold loads (shrink to bool)
            else if G is only used in main, which is norecurse: replace G by an alloca in main (localize)
    until nothing changes

3. Worked example

Attribute inference

Algorithm 20.6.5 on the running module (generated by ./course drill funcattrs-fixpoint, whose oracle is ipo.infer_attrs). The call graph's SCCs bottom-up: {next}, {parse}, {apply, eval} (the declaration sqrt is a leaf with its declared readnone norecurse), {main}:

step	SCC	effects joined	memory	recursive?	norecurse
1	{next}	nothing	none	no	yes
2	{parse}	parse's own loads: read; next: none	read	no	yes (calls only next)
3	{apply, eval}	their own: none; sqrt: none; the calls between eval and apply are skipped (optimistic)	none	yes	no
4	{main}	main's own stores: write; parse: read; eval: none	write	no	no: it calls eval, which is not norecurse

main never recurses in any execution, but the bottom-up rule cannot show it (a callee may recurse); a top-down pass can, if main itself is known to be norecurse (Lesson 20.2, rpo-function-attrs). Compare with iterating Definition 20.6.3 function by function from ⊥ in the order main, parse, next, eval, apply: pass 1 gives main = write, parse = read, next = none, eval = none (apply still ⊥), apply = none; pass 2 changes nothing — the same least fixed point, reached here in two passes only because the example is tiny (infer_attrs_iterative, the test oracle, checks the equality on 500 random modules).

Try it

./course drill funcattrs-fixpoint --seed 2 --difficulty hard --solution — eight functions with indirect calls and library declarations.

Dead-argument elimination

On dae.c (box in §7): clamp(x, lo, hi, unused_flag) never reads unused_flag, and api ignores sum_len's result. Liveness: x, lo, hi are used by compares (live); unused_flag has no uses (dead); sum_len's parameters are used by the loop (live), its return value has one call site whose result is unused (dead). After the rewrite clamp takes three parameters and sum_len returns void.

Argument promotion

On ap.c: norm1(const struct pt *p, const long *scale) only loads p->x, p->y and *scale, all in its entry block, and stores nothing. Parts: \((p, 0, \mathtt{i64})\), \((p, 8, \mathtt{i64})\), \((scale, 0, \mathtt{i64})\) — three values, within the limit. The caller api loads them before the call; SROA then sees that the struct p and the local k are only stored and loaded, and the call becomes norm1(a, b, 3) with no memory in the caller at all.

Global optimization

On go.c: mode (internal, initializer 2, never stored) becomes the constant 2, so k % mode becomes k % 2; debug is only stored to: deleted with its stores; stats is a struct accessed as stats.hits and stats.misses with constant indices: split into @stats.0 and @stats.1.

4. Invariants and correctness

Theorem 20.6.6 covers attribute inference. The signature transformations are correct under their preconditions:

Theorem 20.6.11 (Dead-argument elimination, argument promotion and GlobalOpt preserve semantics)

Under the preconditions of Algorithms 20.6.8–20.6.10, each transformation preserves the observable behavior of the module.

Proof

DAE. All call sites are in the module (local linkage, no address taken), so rewriting every call together with the definition keeps the calls well-typed. A dead parameter's value influences no instruction of \(f\) except by flowing into other dead positions (Definition 20.6.7); by induction on the fixed point, removing all dead positions together removes only computations whose results are never observed. A dead return value is replaced by poison only where it was unused or flowed into dead positions. Argument expressions at call sites are kept if they have side effects (only the argument slot is removed).

Argument promotion. By (1) the callee only reads \(p\)'s memory at the promoted parts. By (2) the values it reads equal the values in memory at the call, since nothing writes them between the call and the loads. By (3) loading them in the caller just before the call cannot trap where the original did not. So each promoted parameter carries the value the load would have produced, and \(f'\) computes what \(f\) computed.

GlobalOpt. Every access to an internal, non-escaping global is visible in the module. A never-stored global holds its initializer in every execution, so its loads may be folded. A never-loaded global's stores are unobservable. SRA: accesses to distinct constant fields never overlap, so splitting the aggregate preserves each field's history. Localizing into a norecurse main: exactly one activation of main exists, so a stack slot has the same lifetime as the global during the execution.

External visibility defeats all four

A dso_local external function may be called from another module with any arguments and its address may be taken there; an external global may be written by any other module. deadargelim and argpromotion only touch internal functions, globalopt only internal globals — which is why LTO (Lesson 20.9), which internalizes everything the linker says is not exported, makes these passes much more effective.

5. Complexity

\(n\) = instructions, \(e\) = call edges, \(F\) = functions, \(U\) = uses of globals.

Technique	Time (worst)	Time (typical)	Space	Justification
Attribute inference (memory, norecurse)	\(O(n + e)\)	linear	one attribute set per function	one scan of every instruction; one join per SCC (Algorithm 20.6.5 joins all members at once, no local iteration)
Argument captures / escape	\(O(n \cdot a)\) for \(a\) pointer arguments	linear with the SCC argument graph	per-argument graph	each use visited once per argument; SCCs of the argument graph handle recursion
Dead-argument elimination	\(O(n + e)\)	linear	uses map	each use recorded once; MarkLive visits each dependency once
Argument promotion	\(O(n \cdot AA)\)	cheap; limited to 3 parts per argument	—	alias queries for the no-clobber check
GlobalOpt	\(O(U)\) per round, rounds bounded by the rewrites	linear	use lists	each rule removes or simplifies uses of one global

Pathological family. For iterative (non-SCC) attribute inference, the ring of Lesson 20.2 §5: \(k\) functions in a cycle, visited in the wrong order, need \(k\) passes. Algorithm 20.6.5 avoids it by joining over the whole SCC in one step — exact because every member of an SCC gets the same effect in the least solution (all members reach each other, so each one's effect includes all the others'). For DAE: a chain \(f_1 \to f_2 \to \dots \to f_k\) where each passes its parameter to the next, and only \(f_k\) uses it: the parameter is live everywhere, discovered by one MarkLive walk of length \(k\); if \(f_k\) does not use it, all \(k\) parameters are dead, and no function had to be revisited.

At scale. On the lab's C corpus plus the feature file, pebble-funcattrs adds 43 memory and 29 norecurse attributes to 65 functions, all of them also proved by LLVM's function-attrs (tests/ch20/lit/funcattrs-vs-llvm.test).

6. Variants and refinements

• Location-precise memory effects (LLVM memory(argmem: read), inaccessiblemem): separate argument memory from other memory; a function that only reads through its pointer arguments is memory(argmem: read) — needed to hoist calls whose arguments are local.
• The Attributor (LLVM attributor, Doerfert et al.): a general fixed-point framework over abstract attributes (per function, argument, call site, return) with optimistic and pessimistic states, deducing dozens of attributes jointly; more precise, more expensive, not in the default pipeline.
• Top-down norecurse and internalization (rpo-function-attrs, Lesson 20.2): propagates from main; and LTO internalization makes more functions eligible.
• Argument promotion of byval and structs / SROA of arguments: pass structure fields separately; GCC's IPA-SRA (ipa-sra.cc) also removes unused parameters and splits aggregates across calls.
• GlobalOpt with constant inference across modules (ThinLTO's read-only/write-only global flags in the index, Lesson 20.9): the same reasoning over the whole program's summary.
• Pure/const in front ends (GCC __attribute__((const, pure))): user-declared effects the compiler trusts — sound only if the programmer is right.

7. In real compilers

Attribute inference

LLVM: llvm/lib/Transforms/IPO/FunctionAttrs.cpp — deriveAttrsInPostOrder runs per SCC; addMemoryAttrs (via checkFunctionMemoryAccess) is Definition 20.6.2 with location kinds; addNoRecurseAttrs is Definition 20.6.4's rule (mayHaveRecursiveCallee); addArgumentAttrs computes captures/readonly for arguments over an argument graph with its own SCCs [LLVM-FunctionAttrs]. GCC: ipa-pure-const.cc (pure/const/nothrow/noreturn) and ipa-modref.cc (Lesson 20.5) [GCC-Modref].

FunctionAttrs on a small module

Reproduce (clang 23.1.2, opt 23.1.2):

cat > fa.c <<'EOF'
int g;
int table[4] = {1, 2, 3, 4};
static int pure(int x) { return x * 2 + 1; }
int reader(int i) { return table[i & 3] + pure(i); }
void writer(int v) { g = v; }
int local(int n) { int a[8]; for (int i = 0; i < 8; i++) a[i] = n + i; return a[n & 7]; }
static int even(int n);
static int odd(int n) { return n == 0 ? 0 : even(n - 1); }
static int even(int n) { return n == 0 ? 1 : odd(n - 1); }
int evenodd(int n) { return even(n) + reader(n); }
int calls_ext(int n) { extern int ext(int); return ext(n); }
int indirect(int (*f)(int), int n) { return f(n); }
EOF
clang-23 -O1 -Xclang -disable-llvm-passes -fno-discard-value-names -S -emit-llvm fa.c -o - | opt -passes=sroa -S -o fa.ll
opt -passes=function-attrs -S fa.ll | grep -E '^define|^attributes #[0-7] ' | sed -E 's/ "min-legal.*//; s/ uwtable//'

Output:

define dso_local i32 @reader(i32 noundef %i) #0 {
define internal i32 @pure(i32 noundef %x) #1 {
define dso_local void @writer(i32 noundef %v) #2 {
define dso_local i32 @local(i32 noundef %n) #3 {
define dso_local i32 @evenodd(i32 noundef %n) #5 {
define internal i32 @even(i32 noundef %n) #6 {
define dso_local i32 @calls_ext(i32 noundef %n) #7 {
define dso_local i32 @indirect(ptr nofree noundef readonly captures(none) %f, i32 noundef %n) #7 {
define internal i32 @odd(i32 noundef %n) #6 {
attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(read, argmem: none, inaccessiblemem: none, target_mem: none)
attributes #1 = { mustprogress nofree norecurse nosync nounwind willreturn memory(none)
attributes #2 = { mustprogress nofree norecurse nosync nounwind willreturn memory(write, argmem: none, inaccessiblemem: none, target_mem: none)
attributes #3 = { nofree norecurse nosync nounwind memory(none)
attributes #4 = { nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
attributes #5 = { nofree nosync nounwind memory(read, inaccessiblemem: none, target_mem: none)
attributes #6 = { nofree nosync nounwind memory(none)
attributes #7 = { nounwind

What to notice: local stores only into its own array: memory(none) (Definition 20.6.1). The recursive SCC {even, odd} gets memory(none) but not norecurse; evenodd reads (through reader) and is not norecurse because even is not. local has no willreturn because its loop was not proved finite. LLVM's location kinds are finer than \(\mathcal{M}\): writer is memory(write, argmem: none, …), i.e. write-only, which the course lattice folds into write. pebble-funcattrs on the same file gives memory(read) to reader and evenodd, memory(none) to pure, local, even and odd, and norecurse to reader, pure, writer and local — never more than this.

Dead-argument elimination

LLVM: llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp — DeadArgumentEliminationPass::surveyFunction records uses and liveness dependencies, removeDeadStuffFromFunction rewrites the signature and the calls [LLVM-DAE]. GCC: IPA-SRA (ipa-sra.cc) removes unused parameters as part of splitting.

deadargelim drops an unused parameter and an unused return value

Reproduce (clang 23.1.2, opt 23.1.2):

cat > dae.c <<'EOF'
static int clamp(int x, int lo, int hi, int unused_flag) {
  return x < lo ? lo : x > hi ? hi : x;
}
static int sum_len(const int *p, int n) {        /* return value never used */
  int s = 0;
  for (int i = 0; i < n; i++) s += p[i];
  return s;
}
int api(const int *p, int n) {
  sum_len(p, n);
  return clamp(n, 0, 100, 42) + clamp(n * 2, 5, 50, 7);
}
EOF
clang-23 -O1 -Xclang -disable-llvm-passes -fno-discard-value-names -S -emit-llvm dae.c -o - | opt -passes=sroa -S -o dae.ll
opt -passes=deadargelim -S dae.ll | grep -E '^define|call '

Output:

define dso_local i32 @api(ptr noundef %p, i32 noundef %n) #0 {
  call void @sum_len(ptr noundef %p, i32 noundef %n)
  %call1 = call i32 @clamp(i32 noundef %n, i32 noundef 0, i32 noundef 100)
  %call2 = call i32 @clamp(i32 noundef %mul, i32 noundef 5, i32 noundef 50)
define internal void @sum_len(ptr noundef %p, i32 noundef %n) #0 {
define internal i32 @clamp(i32 noundef %x, i32 noundef %lo, i32 noundef %hi) #0 {

What to notice: clamp lost its fourth parameter (and the constants 42 and 7 at the calls), sum_len returns void — the two cases of Definition 20.6.7. Both are internal; the same code in an exported function would be left alone (the pitfall of §4).

Argument promotion

LLVM: llvm/lib/Transforms/IPO/ArgumentPromotion.cpp — promoteArguments checks the preconditions (findArgParts, the dereferenceability and no-clobber checks), doPromotion rewrites [LLVM-ArgPromotion]. It is a CGSCC pass that runs in the inliner pipeline right after the inliner.

argpromotion passes a struct's fields by value

Reproduce (clang 23.1.2, opt 23.1.2):

cat > ap.c <<'EOF'
struct pt { long x, y; };
static long norm1(const struct pt *p, const long *scale) {
  return (p->x < 0 ? -p->x : p->x) * *scale + (p->y < 0 ? -p->y : p->y);
}
long api(long a, long b) {
  struct pt p = {a, b};
  long k = 3;
  return norm1(&p, &k);
}
EOF
clang-23 -O1 -Xclang -disable-llvm-passes -fno-discard-value-names -S -emit-llvm ap.c -o - | opt -passes=sroa -S -o ap.ll
opt -passes='cgscc(argpromotion),function(sroa)' -S ap.ll | grep -E '^define|call '

Output:

define dso_local i64 @api(i64 noundef %a, i64 noundef %b) #0 {
  %call = call i64 @norm1(i64 %a, i64 %b, i64 3)
define internal i64 @norm1(i64 %p.0.val, i64 %p.8.val, i64 %scale.0.val) #0 {

What to notice: three parts, p at offsets 0 and 8 and scale at 0 (Algorithm 20.6.9); after SROA the caller has no stack slots left and passes a, b and the constant 3 in registers.

Global optimization

LLVM: llvm/lib/Transforms/IPO/GlobalOpt.cpp — optimizeGlobalsInModule drives the rules; SRAGlobal splits aggregates, optimizeOnceStoredGlobal and tryToShrinkGlobalToBoolean handle stored-once globals [LLVM-GlobalOpt]. GCC: ipa-visibility.cc and ipa-reference.cc compute which statics are read-only or write-only.

globalopt: a constant, a dead global and a split struct

Reproduce (clang 23.1.2, opt 23.1.2):

cat > go.c <<'EOF'
static int mode = 2;                 /* never written: a constant */
static struct { int hits, misses; } stats;   /* only stored/loaded field-wise */
static int debug;                    /* only ever stored to: dead */
int lookup(int k) {
  debug = k;
  if (k % mode) { stats.misses++; return -1; }
  stats.hits++;
  return stats.hits - stats.misses;
}
EOF
clang-23 -O1 -Xclang -disable-llvm-passes -fno-discard-value-names -S -emit-llvm go.c -o - | opt -passes=sroa -S -o go.ll
grep '^@' go.ll
opt -passes=globalopt -S go.ll | grep -E '^@|^define|load|store|srem' | sed 's/, !tbaa.*//'

Output:

@debug = internal global i32 0, align 4
@mode = internal global i32 2, align 4
@stats = internal global %struct.anon zeroinitializer, align 4
@stats.0 = internal unnamed_addr global i32 0, align 4
@stats.1 = internal unnamed_addr global i32 0, align 4
define dso_local i32 @lookup(i32 noundef %k) local_unnamed_addr #0 {
  %rem = srem i32 %k, 2
  %0 = load i32, ptr @stats.1, align 4
  store i32 %inc, ptr @stats.1, align 4
  %1 = load i32, ptr @stats.0, align 4
  store i32 %inc1, ptr @stats.0, align 4
  %2 = load i32, ptr @stats.0, align 4
  %3 = load i32, ptr @stats.1, align 4

What to notice: the three rules of §3 in one pass: mode folded into srem i32 %k, 2 and deleted, debug and its store deleted, stats split into @stats.0 (hits) and @stats.1 (misses).

Find where LLVM does it. Open llvm/lib/Transforms/IPO/FunctionAttrs.cpp and find the helper that addNoRecurseAttrs calls to decide whether any call in the function may lead back to it. What is its name? (Quiz llvm-where-norecurse.)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Attribute inference	Sound summaries (Theorem 20.6.6); SCC-optimistic; bottom-up norecurse is conservative	\(O(n + e)\) · negligible	Attributes in the IR, readable and checkable (-S)	Low per attribute; high for the full set (captures, willreturn)	LLVM function-attrs (3× in default<O2>), GCC ipa-pure-const, pebble-funcattrs
Dead-argument elimination	Removes unused parameters/returns of internal functions	linear · cheap	New signatures; unchanged behavior	Medium (rewriting all calls)	LLVM deadargelim (module simplification, LTO); GCC IPA-SRA
Argument promotion	By-pointer → by-value for read-only, dereferenceable arguments of internal functions	linear + alias queries	Parameters named %p.0.val	Medium (safety checks)	LLVM argpromotion in the CGSCC pipeline
Global optimization	Constant, dead, split, shrunk and localized internal globals	linear per round	Fewer/simpler globals	Medium (many rules)	LLVM globalopt (twice in default<O2>, and in LTO)

Choose attribute inference when you want every later pass to reason across calls cheaply: always. Choose dead-argument elimination and argument promotion when functions are internal (or LTO internalized them): they turn interprocedural knowledge into cheaper calling conventions. Choose GlobalOpt when the module has internal globals: static configuration becomes constants, state structs become scalars.

9. Assessment

• Quiz (./course quiz 20): funcattrs-memory, llvm-where-norecurse (tag funcattrs); dae-dead-args, dae-conditions (tag deadargelim); argpromotion-conditions, argpromotion-parts (tag argpromotion); globalopt-rules, globalopt-sra (tag globalopt).
• Drill: ./course drill funcattrs-fixpoint (easy: memory; medium: norecurse too; hard: indirect calls and declarations). DAE, argument promotion and GlobalOpt have no drill: their analyses are single use-list scans; the quiz questions compute them on small programs.
• Flashcards: tags funcattrs, deadargelim, argpromotion, globalopt.
• Exercises: E3 pebble-funcattrs.

References

See the chapter references.