312 lines
17 KiB
Markdown
312 lines
17 KiB
Markdown
# 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](006-vir.md)), how VIR was produced (see
|
|
[005 — Lowering](005-lowering.md)), or how optimized VIR is emitted (see
|
|
[008 — C Backend](008-c-backend.md), [009 — LLVM Backend](009-llvm-backend.md)).
|
|
|
|
## 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](002-traits.md)). |
|
|
| **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](006-vir.md)) 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](006-vir.md).
|
|
- **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](000-overview.md). 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](006-vir.md)).
|
|
- **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](002-traits.md)).
|
|
- **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](008-c-backend.md)).
|
|
|
|
### 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](011-diagnostics.md)). 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](008-c-backend.md)) 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](005-lowering.md)). 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](004-hir-optimizer.md)); `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](011-diagnostics.md)).
|
|
- **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](006-vir.md) 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](002-traits.md)), 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
|
|
|
|
- [000 — Overview](000-overview.md): determinism guarantee and conformance.
|
|
- [001 — Architecture](001-architecture.md): `vct.vir.opt` module boundary.
|
|
- [002 — Traits](002-traits.md): requests, strengths, conflict rules, epochs.
|
|
- [004 — HIR Optimizer](004-hir-optimizer.md): who produces the traits the optimizer consumes.
|
|
- [005 — Lowering](005-lowering.md): who produces the VIR and the region barriers.
|
|
- [006 — VIR](006-vir.md): the IR and its invariants.
|
|
- [008 — C Backend](008-c-backend.md), [009 — LLVM Backend](009-llvm-backend.md): out-of-SSA on the C path and 1:1 mapping on the LLVM path.
|
|
- [011 — Diagnostics](011-diagnostics.md): internal-compiler-error policy and remarks.
|
|
- [012 — Testing](012-testing.md): verifier and differential testing.
|