Proposal: Single-file conditional macro analysis using sparse data-flow propagation

This is a design proposal, not a scoped change. Start by reading emitMacroConst in cl/preprocessor.go and the loadFiles traversal in cl/compile.go to see how macro values are currently stored in macroVals. Done means the maintainers agree on the analysis node representation and the environment join, which this thread has not yet settled.

Proposal

Add single-file conditional macro analysis to llcppg. Analyze a header's preprocessing directives in source order, evaluate its conditions using the macro environment at each source position, and propagate the resulting information through nested branches and joins. Base the propagation algorithm on sparse data-flow propagation, adapted to preprocessing directives without requiring SSA or variable renaming.

This proposal covers one physical file and its supplied entry environment. Following includes, discovering prerequisite headers, and propagating environments across files are separate work. It does not define a new public API or configuration option.

Motivation and current behavior

A common header pattern is a condition that selects a macro definition, followed by another condition that uses that definition:

#define SCALE 2

#if defined(ENABLE_EXT) && API_LEVEL >= 2
#define LIMIT (SCALE * 4)
#else
#define LIMIT SCALE
#endif

#if LIMIT >= 8
#define FAST 1
#else
#define FAST 0
#endif

With an entry environment in which ENABLE_EXT is defined and API_LEVEL is 2, the analysis should determine that LIMIT expands to 8 and FAST expands to 1. If ENABLE_EXT is known to be undefined, the corresponding results are 2 and 0. Defining ENABLE_EXT as 0 still makes defined(ENABLE_EXT) true.

Today, emitMacroConst tokenizes a macro-definition cursor, calls evalConstExpr, emits a Go constant on success, and stores its value in macroVals. This supports arithmetic and references to already evaluated constants. It does not represent the complete conditional structure or an environment at every source position. Clang has already selected branches for its concrete parsing configuration before loadFiles visits those cursors.

Existing generation can rely on Clang's chosen configuration and manual preprocessing inputs. What is missing is analysis of the source-level conditions and their effects on macro definitions. Temporary define/undef sequences in #1000 illustrate why a macro's lifetime cannot be represented by one final value per name. The prerequisite-header problem in #1138 is related motivation, but resolving that cross-file problem is outside this proposal.

Scope and semantic rules

Analyze #define, #undef, #if, #ifdef, #ifndef, #elif, #else, and #endif, including nested groups and definitions in branches that were inactive in the original TU. Ordinary C declarations do not need to become analysis nodes.

Case	Required interpretation
Definition and use	Keep the replacement tokens. Expand them using the environment at the use position. A definition is not an eager assignment of its currently computed numeric value.
Source order	A later definition must not affect an earlier condition. #undef changes subsequent positions only.
Definedness	Undefined, defined with an empty body, and defined as 0 are different states. Function-like and self-referential macros are also defined macros.
ifdef / ifndef / defined	Query definedness without expanding the tested name.
if / elif	Apply preprocessing expansion rules, then evaluate the integer expression. Remaining ordinary identifiers become 0 under the relevant language rules; this does not define those names.
Branch selection	Process an elif only after the earlier alternatives fail. Definitions in an inactive branch do not change the environment. Preserve lexical nesting.
Expression semantics	Use C precedence, target integer width and signedness, character-literal semantics, and the selected language mode. Do not use Go expression precedence or host int semantics.
Short-circuit evaluation	Parse the entire expression, including syntax in an unevaluated operand. Suppress value-dependent evaluation failures in the unevaluated part. Skipping an entire preprocessing branch is a separate operation.
Errors	An invalid expression is not a false condition or an undefined macro. Preserve that distinction.

For example, #if A == 0 is true when A is known to be undefined, but #ifdef A is false. With an empty #define A, #ifdef A is true while a standalone #if A is invalid.

Macro expansion must preserve token substitution semantics. Given #define X 1 + 2, the condition X * 3 == 7 expands to 1 + 2 * 3 == 7; replacing X by a cached numeric 3 would change its meaning. Similarly, #define ALIAS N must observe the definition of N at each later use. Function-like macros, argument prescan, #, ##, and recursion suppression belong to this expansion boundary; unsupported preparation must remain visible rather than being treated as false.

Collecting the single-file input

Use the existing TU's source buffer and raw tokenization to collect the file's preprocessing directives, rather than assuming VisitChildren supplies a complete conditional tree. A concrete candidate is whole-file Tokenize followed by the existing libclang AnnotateTokens: Clang's implementation annotates preprocessing directives with a PreprocessingDirective cursor and source range. Classify the directive keyword and pair conditional groups with a stack.

The cursor of a macro name inside a condition can be MacroExpansion, so collection must use the directive's source range rather than require all of its tokens to have the same annotation. Validate this route with the supported LLVM version, including inactive branches, continuation lines, comments, and nested directives. This is a collection strategy to verify, not a claim that the new analysis is implemented.

A TU can identify an analysis context, but it cannot identify an individual condition. Conditions need identities within the file. The concrete node representation remains an implementation decision.

Conditional evaluation

Follow the semantics of Clang's Preprocessor::EvaluateDirectiveExpression in PPExpressions.cpp: obtain expanded tokens while protecting operands of defined, parse operands and operators by C precedence, retain integer width and signedness, and return the condition's truth value separately from diagnostics.

Clang uses a ValueLive flag for short-circuit evaluation. For example, 0 && (1 / 0) is valid and false, while 0 && (1 + ) still has a syntax error. Its conditional operator also determines the result's signedness from both result operands: (1 ? -1 : 0U) < 0 is false. These semantics are part of the evaluation contract, not worklist scheduling.

The numeric evaluator, macro expansion, and directive traversal have different responsibilities. The exact function signature and how the expansion layer supplies defined, compiler queries, character values, and target information remain open. The existing macro-value table is not a complete replacement-token environment.

Algorithm: adapting sparse data-flow propagation

The reference is SSA-based Compiler Design, Chapter 8, especially Section 8.2.2 and Algorithms 8.1/8.2 (printed pages 104-105; PDF pages 120-121). The book also describes a non-SSA worklist formulation in Section 8.1.1. We adopt propagation triggered by information changes, feasible control-flow edges, and joins. We cannot directly reuse the SSA algorithm's definition-to-use edges because macros have neither SSA names nor unique reaching definitions.

Build the flow representation from preprocessing operations and conditional structure. It is sparse at the directive level: ordinary C statements through which the macro environment is unchanged are omitted. This does not claim SSA-level def-use sparsity or its complexity bound. An equivalent traversal of the structured directive tree is possible; a separate stored CFG is not required by the semantics.

Analysis state

IN[n] is the macro environment entering operation n; OUT[n] is the environment after applying that operation. Reachability is separate from macro definedness and value information.

For evaluated values, use the familiar constant-propagation categories:

Category	Meaning
Unknown	No propagated value information yet.
Constant(c)	A single known value, including its relevant integer semantics.
Overdefined	The current abstraction cannot represent the value as one constant.

The value join obeys Unknown join Constant(c) = Constant(c), equal constants remain constant, different constants join to Overdefined, and Overdefined remains so when joined with another value. An unreachable predecessor contributes no state. A genuinely unconstrained input must not be mistaken for an unvisited value or for a known-undefined macro.

These categories alone are not a macro environment: preserve definedness and replacement tokens independently. In particular, an empty definition is still defined, and alternative replacement bodies must not be collapsed merely because they happen to evaluate equally at one position. The precise representation and join of conflicting replacement definitions remain open.

Mapping preprocessing directives to the analysis

In IN[A], A identifies an analysis node, not a macro name. IN[A] contains the macro environment before that operation. The following mapping connects preprocessing semantics to the propagation algorithm:

Algorithm concept	Preprocessing counterpart
Node	An operation that changes the macro environment or tests a condition.
Control-flow edge	Source-order execution or a conditional's true/false continuation.
IN[n]	Macro definition information before operation n.
OUT[n]	Macro definition information after operation n.
Transfer	Establish a definition, cancel a definition, or evaluate a condition and select possible outgoing edges.
Join	Combine the environments arriving from feasible predecessor branches.
Value lattice	Describe an evaluation result as Unknown, Constant, or Overdefined; this is not the complete macro environment.
Worklist	Reprocess a node when its incoming information changes.

#else and #endif establish branch and join structure; they need not each become a separate computational node. Consider this file:

#define BASE 2             /* N0 */

#ifdef ENABLE              /* N1 */
#define SIZE (BASE * 4)    /* N2 */
#else
#define SIZE BASE          /* N3 */
#endif                     /* join J */

#if SIZE >= 8              /* N4 */
/* ... */
#endif

Assume the entry environment defines ENABLE as 1, with the other names in this example known to be undefined. Quoted text below denotes replacement tokens.

N0: establish a definition.

IN[N0]  = {ENABLE: "1"}
OUT[N0] = {ENABLE: "1", BASE: "2"}

The source-order edge transfers OUT[N0] to IN[N1].

N1: query definedness and select an edge.

IN[N1] = {ENABLE: "1", BASE: "2"}
defined(ENABLE) = true
OUT[N1] = IN[N1]

true edge  -> N2, carrying this environment
false edge -> N3, unreachable

The query does not expand ENABLE's replacement body. In this example it changes reachability, not the macro definitions.

N2: store the replacement body.

IN[N2] = {ENABLE: "1", BASE: "2"}
OUT[N2] = {
    ENABLE: "1",
    BASE:   "2",
    SIZE:   "(BASE * 4)"
}

SIZE is not frozen to numeric 8 at this definition. A later redefinition of BASE before a use of SIZE must affect that use.

J: merge the feasible inputs.

IN[J]  = join(OUT[N2], OUT[N3])
OUT[J] = OUT[N2]               // N3 contributes no reachable state

N4: expand and evaluate using the incoming environment.

IN[N4] = OUT[J]

SIZE >= 8
    -> (BASE * 4) >= 8
    -> (2 * 4) >= 8
    -> true

The condition result determines N4's possible successors. The information carried along the flow edges is the macro environment; evaluating a condition reads that environment and produces value information used to select edges.

Now consider the same file with ENABLE's entry definedness explicitly unresolved by the analysis, rather than known to be undefined. Both N2 and N3 can contribute at J. The result has three distinct aspects:

Aspect	Information at J
Definedness	SIZE is defined on every feasible incoming branch.
Replacement body	The possible definitions have bodies (BASE * 4) and BASE.
Numeric value at this position	With BASE equal to 2, the possible values are 8 and 2; the simple constant lattice represents this as Overdefined.

Consequently, defined(SIZE) is still definitely true even though the numeric value is not one constant. An Overdefined value must not erase known definedness or replace all replacement-token information needed for later use-position expansion. The exact representation of alternative replacement bodies remains an open question; this example establishes the facts that the representation must preserve.

Transfer and scheduling

• #define establishes the replacement definition in the outgoing environment; it does not freeze an alias's numeric value.
• #undef establishes that the macro is undefined in the outgoing environment.
• A conditional evaluates against its incoming environment and identifies the possibly selected successors. A known result selects the corresponding edge; information that does not determine a result must not eliminate a possible branch.
• #elif represents the false continuation of preceding alternatives; nested groups reconnect at their own joins.
• At a join, combine the environments from feasible predecessors conservatively.
• Revisit a successor when its incoming information changes. Do not update every occurrence of a macro name through one global table: source positions can legitimately see different definitions.

Conceptual worklist algorithm; the operations below are pseudocode, not proposed public functions:

IN[entry] = supplied entry environment
IN[other nodes] = unreachable
worklist = [entry]

while worklist is not empty:
    n = remove one node
    OUT[n] = apply n to IN[n]

    for each successor edge (n, s):
        contribution = state allowed by this edge
        if contribution is unreachable:
            continue
        merged = join(IN[s], contribution)
        if merged differs from IN[s]:
            IN[s] = merged
            enqueue s if it is not already queued

The transfer functions and joins must be monotone and converge. For one file's structured conditionals, the control-flow graph has no loop, so a topological/structured traversal can avoid repeated visits. The worklist specifies the propagation behavior without requiring a full compiler CFG framework, SSA construction, or a SAT/SMT dependency.

Worked nested-branch trace

For this abstract-analysis example, A and B are explicitly unresolved entry inputs, not names known to be undefined. N is initially undefined.

#if A                  /* node A */
# if B                 /* node B */
#  define N 2          /* node C */
# else
#  define N 8          /* node D */
# endif                /* join J1 */
#else
# define N 5           /* node E */
#endif                 /* join J2 */
#if N == 5             /* query Q */
#endif

Using a FIFO worklist, scheduling true successors before false successors, and suppressing duplicate queue entries:

Step	Process	Update	Queue afterward
1	A	Both successors are possible.	B, E
2	B	Both inner successors are possible.	E, C, D
3	E	J2 first receives the definition N = 5.	C, D, J2
4	C	J1 first receives N = 2.	D, J2, J1
5	D	J1 also receives N = 8; its numeric value information becomes Overdefined. J1 is already queued.	J2, J1
6	J2	Its current input gives Q N = 5.	J1, Q
7	J1	Its merged information changes J2, so J2 is queued again.	Q, J2
8	Q	With the information received so far, the condition is provisionally true.	J2
9	J2	Propagates the updated information to Q.	Q
10	Q	The condition is no longer provably constant; true and false remain possible.	empty

The provisional result at step 8 must not be committed as the final analysis result. With a complete concrete environment where A is true and B is false, only C's sibling D contributes, N is 8, and Q is false. With A known to be undefined, it becomes 0 at its #if use, only E contributes, and Q is true.

Integration and boundaries

loadFiles is the candidate integration point for per-file analysis, reusing its outer TU iteration and existing token access. Raw directive collection supplies the information absent from the existing cursor walk. Binding-output filters such as MacroIgnore, package ownership, and declaration deduplication must not be mistaken for preprocessing semantics.

The analysis observes source-level conditions and macro facts. Running it after Clang has built a TU does not retroactively add declarations from inactive branches to that TU. Any later use of its results to choose another parsing configuration is a separate integration decision.

Cross-file include traversal, prerequisite-header discovery, injecting guard macros, shared state across independent TUs, and generation of every alternative configuration are outside this proposal. An include-dependent input cannot silently be assumed absent or treated as having no effect; the source of the required external facts must be specified at the input boundary.

Validation

Compare concrete single-file results and error cases against Clang with the same target, language mode, and preprocessing inputs. Test the propagation layer separately using explicit abstract inputs. Run implementation tests with llgo test, including the affected cl/tool fixtures.

Cover undefined versus empty versus zero definitions; defined and ifdef; source-order redefinitions and alias expansion; nested if/elif/else; inactive definitions; macro substitution precedence; function-like expansion and recursion; integer suffixes and signed conversions; short-circuit syntax versus evaluation errors; ternary association and result type; complete directive collection; and isolation between two independent analyses of the same file.

Open questions before implementation

1. What concrete input contract supplies compiler/target facts and identifies complete versus unresolved entry macro information? How should an include-dependent condition be represented without doing cross-file analysis?
2. How are alternative replacement definitions and their definedness represented at joins? Do we need only constant/nonconstant results, or also retained conditional values? The three-state value lattice does not decide this by itself.
3. Where does macro expansion end and numeric condition evaluation begin, particularly for defined, function-like macros, compiler queries, and character literals? No new callable interface is fixed here.
4. Is a structured directive traversal sufficient for the first implementation, or should the directive CFG and worklist be stored explicitly? Both must obey the same propagation semantics.
5. How are invalid/unsupported conditions surfaced to callers, and at what generation boundary does an error stop processing? They must not be silently converted into false conditions.

References

• SSA-based Compiler Design, 2018 draft, Sections 8.1.1 and 8.2.2, Algorithms 8.1/8.2.
• Clang preprocessing expression evaluator.
• libclang tokenization and annotation.
• GCC preprocessor condition rules and defined.