huntedbytheirs/libvct-spec
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
libvct-spec/spec/007-vir-optimizer.md
T

17 KiB
Raw Permalink Blame History

007 — VIR Optimizer

  • Status: Draft
  • Normative language: MUST, MUST NOT, SHOULD, SHOULD NOT, and MAY are to be interpreted as described in RFC 2119.

1. Purpose

The VIR optimizer is the heavy-transformation half of libVCT. It consumes lowered VIR and applies large, whole-function and whole-module transformations: inlining, scalar and memory optimization, loop transformation, vectorization, control-flow cleanup, and code-generation preparation. It is where the design's codegen-quality goal is realized.

The VIR optimizer is a strict trait consumer. It discovers nothing. Every fact that enables or forbids a transform is an attribute or relationship left by HIR, or a Request that HIR issued. When a fact is not present in a trait, the optimizer MUST assume the conservative answer and move on.

2. Scope

This file specifies the optimizer contract, the pass framework, the analysis set and its invalidation discipline, the default -O2 pipeline, request handling, alias analysis, region barriers, budgets, and the rules that relate optimization level to aggression.

It does not specify VIR itself (see 006 — VIR), how VIR was produced (see 005 — Lowering), or how optimized VIR is emitted (see 008 — C Backend, 009 — LLVM Backend).

3. Definitions and model

Term Meaning
VIR pass A named transform over a function or a module.
Pass manager The driver that schedules passes and owns analyses.
Analysis A derived fact about a function or module, cached and invalidated.
Preserved set The analyses a pass declares it does not invalidate.
Request An attribute-derived suggestion from HIR, with a strength (see 002 — Traits).
Action request A Request that asks for a transform (Inline, Unroll(factor), LICM, ...). It yields a RequestResult when the responsible pass runs.
Property request A proven property the optimizer MAY exploit (LoopInvariant, Range, Assume, ...). It is consumed as a fact and does not by itself produce a RequestResult.
DenyReason The machine-readable reason a request was declined.
Region barrier An opaque region produced by lowering for complex/NoOptimize code.
Remark A per-decision record emitted for diagnostics.

4. Normative requirements

4.1 Contract

  • O-1. The input MUST be well-formed VIR (see 006 — VIR) with complete, epoch-valid traits.
  • O-2. The output MUST be well-formed VIR that is still in SSA form. The optimizer MUST NOT break any invariant in 006 — VIR.
  • O-3. The optimizer MUST be a strict trait consumer. A transform MUST be enabled by an attribute, a relationship, or a Request. The optimizer MUST NOT assume a fact that is absent from traits, and MUST NOT infer one from program structure.
  • O-4. The optimizer MUST run only at -O2, -O3, -Ofast, and -Oz. At -O0 and -O1 it MUST NOT run at all (see §4.9).
  • O-5. The optimizer MUST be deterministic. For fixed input and Config, it MUST produce byte-identical output regardless of thread count, per 000 — Overview. Where a pass has a choice that affects output (for example, the order of two independent transforms), the pass MUST fix the order deterministically.
  • O-6. The optimizer MUST preserve the observable behavior of the program. A transform that would change behavior is legal only when the traits license that change (for example, fast-math flags).
  • O-7. The optimizer MUST terminate on every input. Budgets under §4.8 guarantee this.

4.2 Pass framework

A pass is a named unit of work. A function pass runs on one function; a module (IPA) pass runs on the whole module. Passes mutate VIR in place.

interface VirPass {
    string name();
    void run(VirModule m, PassContext ctx);   // module pass
}
  • O-8. Every pass MUST expose a stable name. The name MUST be usable as a -f<name> / -fno-<name> toggle (see §4.9).
  • O-9. A pass MUST declare the analyses it preserves before it runs. The pass manager uses the declaration to invalidate only the analyses the pass might destroy (see §4.3).
  • O-10. A pass MUST update the def-use graph for every operand it rewrites (see 006 — VIR).
  • O-11. A pass MUST NOT run when a required analysis cannot be built, when a region barrier forbids it (see §4.7), or when a request that gates it is denied.
  • O-12. A pass that reads a trait MUST ensure the trait is epoch-valid. If the epoch advanced since it read the trait, it MUST re-read rather than reuse the stale value.

4.3 Analyses and invalidation

The pass manager owns a cache of analyses. Analyses are built lazily on first request and reused until invalidated.

Analysis Subject
DominatorTree Immediate dominators and the dominator tree of each function.
PostDominatorTree Immediate post-dominators, used by control-flow transforms.
LoopInfo Natural loops, headers, latches, preheaders, and nesting.
AliasInfo May-alias answers synthesized from traits (§4.6).
DefUse The def-use graph over SSA values.
CallGraph Caller/callee edges and call-site metadata.
RangeInfo Lightweight value ranges, seeded by Range/Assume traits.
  • O-13. Invalidation MUST be fine-grained. The pass manager MUST invalidate exactly the analyses that a pass does not declare preserved. It MUST NOT invalidate all analyses as a default. An invalidated analysis is rebuilt lazily on next request.
  • O-14. A pass MUST NOT read an analysis after the pass manager has invalidated it; it MUST request a fresh build.
  • O-15. An analysis whose result depends on traits MUST be invalidated when a trait epoch advances in a way that can change that result. The epoch counter is the mechanism (see 002 — Traits).
  • O-16. RangeInfo MUST be lightweight. It MUST be seeded by Range and Assume traits and MUST NOT implement a full scalar-evolution analysis. A pass MUST NOT expect exact ranges.
  • O-17. AliasInfo MUST NOT guess. Its answers are defined in §4.6.

4.4 Default -O2 pipeline

At -O2 the pass manager runs the following canonical pipeline. The order is fixed; the pipeline is not reordered adaptively by requests. Requests gate and parameterize passes, they do not resequence them.

Stage Passes
1. Canonicalize mem2reg, SROA, instcombine, simplifyCFG, early-CSE, DCE
2. Scalar GVN, SCCP, LICM, indvars, reassociation
3. IPA inliner (gated by Inline/AlwaysInline/NoInline/ColdCall/LikelyCall), global DCE, IPSCCP, function-attribute propagation
4. Loops unroll/interleave/peel/rotate/unswitch/distribute/fuse/jam, each gated by its Request
5. Vectorize loop and SLP vectorization, gated by Vectorize, LoopInvariant, Range, NoAlias, Restrict
6. Memory alias-driven DSE, GEP simplification, load widening
7. Control flow block layout (HotPath/ColdPath), tail-call formation (TailCall/MustTail/NoTail), unreachable pruning, jump threading
8. Codegen prep backend-directed canonicalization; output remains SSA
  • O-18. At -O2 the optimizer MUST run all eight stages in the order shown, subject to pass toggles, region barriers, and request denials.
  • O-19. Stage 3 (IPA) MUST be driven by the call-edge requests. A callee carrying AlwaysInline MUST be inlined where legal. A callee carrying NoInline MUST NOT be inlined.
  • O-20. Stage 4 loop transforms MUST each be gated by their own Request. For example, unroll runs only under an Unroll(factor) request, and LICM hoists only under an LICM request or when a LoopInvariant property licenses it.
  • O-21. Stage 5 vectorization MUST be gated by Vectorize and MUST consult NoAlias, Restrict, Range, and LoopInvariant before reordering memory operations.
  • O-22. Stage 8 MUST NOT perform out-of-SSA translation and MUST NOT lower Phi instructions. Out-of-SSA is a backend concern (see 008 — C Backend).

4.5 Request handling

Every action request that the responsible pass evaluates MUST produce a RequestResult.

struct RequestResult {
    Request    req;
    bool       accepted;
    DenyReason reason;
    string     note;    // one-line human-readable explanation
}

A denial MUST carry a DenyReason and a one-line note.

DenyReason Meaning
CostModel Profitable only under a different cost model.
Illegality The transform would be incorrect.
AlreadyDone No-op; the goal already holds.
Unsupported The optimizer does not implement it yet.
ContradictsTrait Conflicts with a stronger fact.
TooLarge Exceeds a size or count budget.
NoTargetSupport The backend or target cannot express the result.
  • O-23. When a pass evaluates a request, it MUST record a RequestResult with a DenyReason and a one-line note on denial. It MUST NOT deny silently.
  • O-24. A Soft request MAY be denied for any DenyReason. A denied Soft request MUST NOT produce an error; it SHOULD produce a remark.
  • O-25. A Strong request denied with Illegality or ContradictsTrait MUST raise an internal-compiler-error diagnostic (see 011 — Diagnostics). A Strong request should be legally satisfiable; failing to satisfy it indicates a compiler inconsistency. This rule applies only when the target is capable of the transform; a capability gap MUST instead be reported as NoTargetSupport.
  • O-26. A Strong request denied with Unsupported or NoTargetSupport MUST produce a warning, not an error, unless the target genuinely cannot express semantics the request requires for correctness or ABI. Such a semantic-capability failure (for example, MustTail on GCC; see 008 — C Backend) MUST be a hard error.
  • O-27. A Strong request denied for any other reason (CostModel, AlreadyDone, TooLarge) MUST NOT be a hard error and SHOULD produce a warning.
  • O-28. The optimizer MUST NOT drop a request without a RequestResult, and MUST NOT flip a request to accepted when it did not perform the transform.
  • O-29. LoopInvariant is a proven property and LICM is an explicit hoist request. Both MUST be retained and handled distinctly: a pass MAY exploit LoopInvariant without an LICM request, and a pass MUST attempt the hoist when LICM is requested.
  • O-30. NoRead/NoWrite are access-edge primitives; ReadOnly/WriteOnly are region-level facts. A pass MUST respect the scope difference when it consumes either form.

4.6 Alias analysis

AliasInfo answers may-alias queries. It is synthesized from traits and provenance only.

  • O-31. AliasInfo MUST derive its answers from NoAlias, Restrict, NoCapture, Dereferenceable, ReadOnly, and WriteOnly traits, together with the provenance relationships HIR left on the values.
  • O-32. When no trait establishes a relationship between two memory references, AliasInfo MUST answer MayAlias. It MUST NOT infer NoAlias from program structure, from the fact that two allocas are distinct, or from any fact not present in traits.
  • O-33. A pass MAY use a NoAlias answer only for the exact pair and scope the trait licenses. It MUST NOT generalize an answer to other pairs.
  • O-34. A region barrier is an alias barrier: no reference inside one is known not to alias a reference outside it unless a trait says so (see §4.7).

4.7 Region barriers

  • O-35. Lowering marks complex/NoOptimize code with a region-level barrier (see 005 — Lowering). VIR passes MUST treat the region as opaque.
  • O-36. A pass MUST NOT rewrite, reorder, delete, hoist, or sink an instruction across a region barrier. It MUST NOT propagate a value or a fact into or out of the region.
  • O-37. Memory and alias analyses MUST model a barrier region as a single opaque, side-effecting operation.
  • O-38. A pass that cannot make progress because of a barrier MUST skip the affected code without error and MUST NOT force a transform through it.

4.8 Budgets and termination

  • O-39. The optimizer MUST honor vir.max_iterations (per-pass or per-analysis iteration cap) and vir.max_pipeline_rounds (number of times the pipeline may re-run). Both MUST be configurable through the API and CLI and MUST have finite defaults.
  • O-40. When a budget is exhausted, the optimizer MUST stop and return the current, well-formed VIR. It MUST NOT loop indefinitely and MUST NOT return malformed VIR.
  • O-41. Budget exhaustion SHOULD be reported as a warning and MAY be reported as a remark. It MUST NOT be an internal compiler error.

The default budgets are:

Budget Default
vir.max_iterations 100000
vir.max_pipeline_rounds 4

An implementation MUST use these defaults unless the caller overrides them through the API or CLI. The values are finite (O-39) and are chosen at the same order of magnitude as the HIR budgets (see 004 — HIR Optimizer); vir.max_pipeline_rounds bounds how many times the eight-stage pipeline of §4.4 may be re-run.

4.9 Optimization levels and pass toggles

Level VIR optimization Behavior
-O0 off None. Only lowering's own translation.
-O1 off None. HIR folds only.
-O2 on The eight-stage default pipeline of §4.4.
-O3 on The -O2 pipeline with raised aggression (see below).
-Ofast on -O3 plus fast-math and -march=native.
-Oz on The -O2 pipeline tuned for size.
  • O-42. The optimizer MUST be entirely disabled at -O0 and -O1. In particular, mem2reg, SROA, and DCE MUST NOT run at those levels.
  • O-43. -O3 MUST raise aggression relative to -O2: higher inlining thresholds, larger unroll/interleave factors, and wider vectorization factors, all still gated by their requests.
  • O-44. -Ofast MUST enable fast-math flags and -march=native. Fast-math flags MUST NOT be set at any lower level unless the caller explicitly configured them.
  • O-45. -Oz MUST be size-first: most unrolling and vectorization MUST be disabled, inlining limited to very small callees, while canonicalization and dead-code elimination remain enabled.
  • O-46. Every pass MUST be individually controllable through a -f<name> / -fno-<name> toggle. A disabled pass MUST be omitted from the pipeline rather than run and then reversed.

4.10 Diagnostics and remarks

  • O-47. A pass MUST emit its decisions through the diagnostics service; it MUST NOT print directly (see 011 — Diagnostics).

  • O-48. Remarks MUST be off by default and MUST be enabled by --remarks; they MUST be enabled automatically at -O3.

  • O-49. A remark that reports a request decision SHOULD include the request, the subject, the outcome, and the one-line note. Example:

    VIR: denied Inline on @foo, CostModel (callee 2.4x size budget)

5. Invariants

The output of the optimizer MUST satisfy all of the following.

  1. Well-formed VIR. All invariants in 006 — VIR hold after every pass.
  2. Still SSA. The output is in SSA form; Phi instructions remain; no out-of-SSA lowering happens here.
  3. Trait fidelity. No transform may invent a fact. Every fact used is traceable to a trait.
  4. Barrier respect. No transform crosses a region barrier.
  5. Request accountability. Every evaluated action request has a RequestResult.
  6. Termination. The pipeline terminates within its configured budgets.
  7. Determinism. Fixed input and Config produce byte-identical output.

6. Example

Given a callee annotated AlwaysInline and a call site annotated NoInline:

  • The call-edge requests conflict. HIR resolves strong conflicts before lowering (see 002 — Traits), so lowering should not present both to the optimizer. If a contradiction still reaches the optimizer, the inliner denies the Strong request with ContradictsTrait, which is an internal compiler error under O-25.

Given a callee with a ColdCall request and a size estimate above the inline threshold:

  • The inliner denies Inline with CostModel and records a RequestResult with the note callee 3.1x size budget. No error is raised; a remark is emitted when remarks are enabled.

7. Cross-references

Reference in New Issue View Git Blame Copy Permalink