How REX Cut Cxx_Grammar Translation From 28 Minutes to Under 3 Minutes

A compiler can stop timing out and still be much too slow.

An earlier REX frontend repair stopped ordinary translation from eagerly materializing an unnecessary universe of system-header namespaces and templates. That changed Cxx_Grammar.C from an opaque timeout into a test that completed. It was the right ownership fix, and it is documented in the earlier traversal-boundary post.

But “completes” was not a satisfying performance result.

Three full-size tests still took between 25 and 28 minutes each. They were doing real work on one of the largest translation units in REX, and the resulting Sage AST really did need declarations, types, scopes, symbols, parents, source positions, preprocessing information, and validation. The tests could not be made fast by translating less of the program or checking less of the result.

The optimization therefore started with a stricter question:

1
2

How much of this time is necessary AST construction, and how much is the same
invariant being rediscovered by repeatedly scanning growing containers?

The answer led to REX issue #847 and the implementation in PR #849. The final change made the three workloads roughly ten times faster without deleting tests, weakening AST contracts, or adding a Cxx_Grammar.C special case.

The Problem

Cxx_Grammar.C is generated by ROSETTA and implements a large part of the Sage IR. In the measured build it was:

1
2

248,330 lines
9,263,281 bytes

This is legitimately heavy compiler input. It contains the generated classes, accessors, traversal support, memory-pool machinery, type relationships, and other implementation details behind the Sg* node hierarchy.

The three slow tests share that source file, but they are not redundant:

• rose_example_src_frontend_SageIII_Cxx_Grammar_C exercises the representative translator path over the generated grammar.
• astQuery_test3_cxx_grammar builds the AST and then exercises the AST query consumer.
• merge_traversal_cxx_grammar runs the merge-traversal suite’s traversalArray consumer over the same large AST.

Their most recent pre-optimization full-suite measurements were:

Each process reached roughly 5.7 GiB of resident memory. That memory footprint was acceptable for the RAM-rich local machine intended to run the complete suite. The wall time was the problem. A few long-tail tests could dominate local validation and would be poor candidates for a normal hosted pull-request job.

The wrong responses were easy to list:

• increase the timeout;
• skip or shrink the tests;
• replace the generated grammar with a toy source file;
• avoid translating bodies, templates, preprocessing information, or semantic dependencies;
• weaken the exact ownership assertions;
• special-case the filename or test names;
• accept a partial Sage AST and hope later passes repair it.

Every item would improve a dashboard while making the compiler less trustworthy.

Motivation

Large generated inputs are useful because they amplify complexity mistakes.

A linear operation that takes a few microseconds per declaration may be fine on a small specimen and still visible on Cxx_Grammar.C. A scan of every prior declaration after every append is different: doubling the number of declarations can approach four times the work. When several such paths compose during on-demand translation and AST finalization, the result is measured in tens of minutes.

The performance goals were deliberately staged:

1. get every test comfortably below five minutes;
2. then make every test pass a strict local limit of less than 180 seconds.

The second target mattered because it was low enough to reject a merely cosmetic improvement. It also forced the implementation to address the ownership and lookup structures that caused the scaling problem instead of polishing one benchmark-specific path.

Correctness remained the first constraint. The goal was:

1
2
3

same complete AST contracts
+ same hard failures for malformed state
+ much less repeated work

Analysis: Is The Source Simply Expensive?

The first control was LLVM/Clang 22 itself.

Using the exact compiler arguments from REX’s compile_commands.json, the same translation unit produced these measurements on the same host:

These are not direct substitutes for a REX test. Clang is not building Sage, attaching preprocessing records to Sage nodes, publishing Sage symbols, running Sage postprocessing, querying the Sage tree, or exercising a merge traversal. REX should take longer.

But a 5.61-second parse and a 1,600-second REX test also made one conclusion unavoidable: input size alone did not explain the result.

REX’s phase trace made the boundary sharper:

1
2
3
4
5
6
7

0.049  clang_main.parse.begin
13.837 clang_main.parse.end
13.838 clang_main.translation_unit.begin

clang_main.HandleTranslationUnit.late_templates.begin
clang_main.HandleTranslationUnit.late_templates.end
clang_main.HandleTranslationUnit.traverse.begin

Repeated runs reached Traverse after about 14 seconds. The missing 25-plus minutes came after Clang parsing, in Clang-to-Sage translation, Sage AST finalization, preprocessing attachment, and the downstream test consumer.

Analysis: Necessary Work Implemented As Repeated Scans

The profiling and source audit did not find one magic 1,500-second function. It found several independently expensive patterns that compounded.

Exact Declaration Attachment Became Quadratic

REX must know that a declaration is attached exactly once to its owning global, class, or auxiliary declaration list. “Present” is not enough. A duplicate is a malformed AST and must fail.

The frontend already had a membership set, but the exact-cardinality path did not use it. containsExactly scanned the authoritative declaration list. Normal construction appended a declaration and immediately asked the exactness question again.

For a scope that grows to N declarations, that shape approaches:

1

1 + 2 + 3 + ... + N = N(N + 1) / 2

One scan is harmless. One scan after every mutation is quadratic. Large global scopes and generated classes paid that cost repeatedly.

An ordinary unordered_set was not sufficient because it cannot distinguish one occurrence from two. The right index needed a count per declaration, not a boolean membership bit.

Clang Declaration Contexts Were Rescanned Per Member

Access publication for record members repeatedly walked clang::RecordDecl::decls() to reconstruct the same effective access state. Typed-owner and embedded-field checks similarly scanned enclosing declaration contexts or record fields for each translated tag.

The information was stable. The frontend was paying to derive it again for each consumer.

Translation Cache Cleanup Searched The Wrong Direction

One Sage node may be the translated value for several Clang declaration keys. During placeholder replacement and cleanup, the old implementation knew the Sage value but searched the forward Clang-to-Sage map to find every alias.

That is a reverse-lookup problem implemented as repeated forward scans. It was especially expensive in function-template completion, where on-demand translation amplified the number of cache operations.

Preprocessing Ownership Was Recomputed

Preprocessing attachment repeatedly rediscovered:

• which physical file and include occurrence owned a record;
• which source interval contained it;
• which declaration, parameter, expression, or initializer boundary could own it;
• whether a path represented application or external ownership.

Those are exact source-identity questions. Rewalking trees and renormalizing paths did not make the answer more correct.

Sorting Performed Filesystem Work Inside Its Comparator

Comment ordering normalized filesystem paths inside the sort comparator. A sort performs roughly O(N log N) comparisons, so an expensive normalization was multiplied even though each record’s normalized path was invariant during the sort.

Downstream Consumers Revisited Stable State

AST query classification, merge traversal, and qualification publication also contained paths that recalculated stable relationships. They were not the first cause to fix, but they mattered after the frontend’s largest quadratic paths were removed.

The overall shape looked like this:

1
2
3
4
5
6

on-demand declaration translation
  -> repeated declaration-list scans
  -> repeated context/access scans
  -> repeated source/preprocessor searches
  -> repeated alias cleanup scans
  -> finalization and consumer passes over the result

No single step needed to be catastrophically slow. Their product was enough.

The Solution: Exact Producer-Owned Indexes

The central design change was to compute stable relationships at their producer, update them at every mutation, and audit them against the authoritative containers at transaction boundaries.

This distinction matters:

1
2
3

the AST remains authoritative
the index makes repeated questions cheap
the final audit proves AST and index still agree

Count Exact Declaration Attachments

DeclAttachmentSession now owns an occurrence map for each declaration list. Insertion, erasure, and replacement operations update that map and reject duplicates or missing entries immediately. Exact-membership queries read the count instead of scanning the list.

At the end of construction, validateAll() independently rebuilds the expected state from the real declaration lists and compares it with the stored index. A missed mutation therefore remains a hard invariant failure; it cannot silently produce a fast but stale answer.

Index Record Access And Typed Ownership Once

The frontend builds exact per-record indexes for direct members and effective access. It also indexes physical source intervals for embedded tags and typed owners. Per-member publication becomes an indexed lookup, while construction of the index validates null members, duplicate identities, and malformed access state.

Give The Translation Cache A Reverse Map

The declaration translation cache now owns both directions:

1
2

Clang declaration -> Sage node
Sage node -> exact set of Clang aliases

Every cache mutation goes through an encapsulated operation that keeps the maps in agreement. Replacing or erasing every alias for a Sage node no longer scans the complete forward cache. Final validation checks the forward/reverse bijection and rejects empty, null, stale, or foreign alias families.

Index Physical Preprocessing Coordinates

Recorded directives and includes are indexed by physical file and source offset. Where the same header can be included more than once, the physical file occurrence is part of the identity. That prevents a fast lookup from confusing two textual inclusions of the same path.

Normalized include-ownership paths are cached once. Comment sort entries precompute their normalized path before sorting, so the comparator compares strings rather than touching filesystem normalization repeatedly.

The final attachment pass builds focused anchor and boundary indexes for the remaining records. It still requires one exact typed owner for every record.

Reuse Stable Consumer State

The query, merge, and name-qualification paths cache classifications that are stable for the current invocation. The cache lifetime is intentionally bounded; it does not become cross-invocation global state with unclear invalidation.

This is the broader rule behind the optimization:

If a relationship is stable within one compiler transaction, publish it at the producer, mutate it through one owned API, and audit it once instead of rediscovering it at every consumer.

Correctness Work Exposed By The Optimization

Performance work on ownership code can reveal correctness bugs. That happened here, especially around preprocessing boundaries.

Once preprocessing attachment used exact indexed source identities, several old ambiguous cases could no longer hide inside broad searches:

• a multiline declaration group needed a comment attached to the exact following initialized-name boundary;
• each initialized name needed its own declarator range while the owning declaration retained the shared group range;
• a function-definition boundary transfer had to stay inside the physical gap after the declarator and before the body;
• a declaration and body produced at the same macro expansion site had no source-written physical gap to own;
• directives between parameters needed an exact following or preceding typed parameter boundary;
• directives inside an empty parameter list needed the typed SgFunctionParameterList owner;
• repeated includes of the same header needed distinct physical occurrence identities;
• inactive conditional declarators needed a structural skipped-token witness and an exact typed boundary even when Clang exposed only active declarators.

These were fixed in the frontend and covered structurally and by round-trip compilation with relevant conditions enabled and disabled. The unparser’s old unsafe-parameter suppression was removed. If preprocessing ownership is malformed, REX now rejects it instead of omitting it from the output.

The optimization also left REX’s OpenMP boundary unchanged. OpenMP pragmas remain source records for the REX OpenMP AST constructor; -fopenmp is not forwarded to Clang to replace that design.

That is an important part of the result. The speedup did not come from moving semantic responsibility to a different frontend or making the backend more forgiving.

A Local-Only Performance Contract

The three workloads are too heavy and machine-sensitive to use as an ordinary hosted pull-request timing benchmark. They remain part of the complete CTest campaign, but the strict timing harness is intentionally local-only.

scripts/measure-cxx-grammar-performance.py does not duplicate test commands. It asks CTest for each registered test’s JSON contract, then preserves the exact:

• command;
• working directory;
• environment.

It runs the tests sequentially so they do not contend with one another, measures wall time with a monotonic clock, and enforces a strict per-test upper bound. A timeout terminates the complete process group, first with SIGTERM and then with SIGKILL if descendants do not exit.

The normal command is:

1
2
3

python3 scripts/measure-cxx-grammar-performance.py \
  --build-dir build \
  --limit-seconds 180

This is a performance contract, not a correctness substitute. The focused, retained, pre-push, and complete CTest gates still run separately.

Evaluation

The controlled before/after measurements were:

Sequentially, those three observations total about 80 minutes 55 seconds before the optimization and 8 minutes 11 seconds after it. The aggregate reduction is about 9.9x.

All three met the strict <180s contract in that controlled run. Those exact times were recorded before the final review-only conditional-separator follow-up. That follow-up strengthened preprocessing correctness rather than changing the indexed design, but later strict reruns after a full suite showed that the 180-second threshold did not yet have a comfortable noise margin. The astQuery result above had only 2.95 seconds to spare.

The honest conclusion is therefore not that every loaded machine is guaranteed to reproduce the same margin. The durable result is the order-of-magnitude improvement and the removal of the quadratic design. The harness remains strict precisely so later changes must keep earning the target rather than inheriting it as an assumption.

The Clang comparison also remains useful after the fix. A 145-177 second REX test is still much slower than a 5.61-second Clang syntax/Sema pass. Some gap is expected because REX constructs and validates a second compiler IR and each test has its own downstream consumer. The remaining gap is future profiling room, not evidence that Sage construction can be skipped.

The final correctness evidence for the merged change was:

No test was deleted, renamed, skipped, or weakened. Malformed ownership and stale index state still fail hard.

What Actually Produced The Speedup

It is tempting to summarize this as “use hash maps.” That misses the design.

Hashing helped, but an unchecked cache can make a compiler fast and wrong. The important changes were:

1. identify stable relationships that hot consumers were repeatedly deriving;
2. move ownership of each relationship to its producer;
3. make every mutation update the authoritative state and its exact index;
4. reject duplicate, missing, stale, foreign, or inconsistent state immediately;
5. rebuild and compare indexes in final linear audits;
6. retain full-size workloads and the complete regression suite as independent evidence.

This changes complexity without changing the compiler contract.

The declaration-attachment example is the clearest one. The old code answered an exact-cardinality question correctly by scanning a list. The new code answers the same question from an occurrence count, then proves the count against the list at the end. Correctness did not become optional. It became cheaper to ask for repeatedly.

Conclusion

Cxx_Grammar.C was heavy for two different reasons.

First, it is genuinely large and exercises a wide Sage surface. That is why the three tests should remain. They are valuable compiler-scale contracts, not a pile of redundant small specimens accidentally concatenated together.

Second, the large input exposed algorithms that repeatedly scanned stable state. That part was not inherent to Clang-to-Sage translation. Exact declaration ownership, access, aliases, preprocessing coordinates, symbol identity, and query classifications can be indexed at their producers and audited at clear boundaries.

The result was not a timeout increase or a smaller test. It was the same large input, the same complete Sage responsibilities, stronger preprocessing ownership, and roughly one tenth of the wall time.

That is the kind of compiler performance improvement worth keeping: faster because the invariants have better data structures, not because the compiler is doing less of its job.