# 004 — HIR 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 HIR optimizer is the **discovery and small-fold** stage. It validates frontend-suggested traits,
derives attributes and relationships, evaluates compile-time expressions, runs cheap folds to a
fixpoint, and expands `defer`. Its output is annotated HIR whose traits are complete and
epoch-valid, and which hands VIR a "dictionary" of facts.

The HIR optimizer **MUST NOT** perform heavy transformations. In particular, it **MUST NOT** inline
code (see the "HIR never inlines" requirement below).

## 2. Scope

In scope: the HIR pass framework, triggers, the worklist scheduler and cascade-to-fixpoint, per-
function parallelism and the module-level fixpoint, epoch-based staleness, the comptime evaluator,
`defer` expansion, optimization-level behavior, and default budgets.

Out of scope: the trait vocabulary (see [002 — Traits](002-traits.md)), the node model and builder
contract (see [003 — HIR](003-hir.md)), and the HIR-to-VIR translation (see
[005 — Lowering](005-lowering.md)).

## 3. Definitions

| Term | Definition |
|---|---|
| **Pass** | A unit of discovery or folding over one function's HIR. |
| **Trigger** | A record that a rewrite succeeded and may enable further work. |
| **Worklist** | The deduplicated queue of `(pass, node)` work items. |
| **Cascade** | The chain of rewrites triggered by one fold. |
| **Fixpoint** | The state in which the worklist drains with no new work. |
| **Epoch** | The per-node generation counter that invalidates stale traits. |
| **Step budget** | The bounded amount of work allowed before the scheduler stops. |

## 4. Pass framework

A pass is a named unit with the following shape:

```d
interface HirPass {
    string name();
    void run(HirFunction fn, HirContext ctx);
}
```

Normative requirements:

1. A pass **MUST** mutate the annotated AST **in place**. It **MUST NOT** rebuild the tree or
   return a replacement.
2. A pass **MUST** be deterministic: for a fixed input and epoch, it produces the same mutations in
   the same order regardless of thread count.
3. A pass **MUST** emit a **trigger** for every successful rewrite (see the triggers section).
4. A pass **MUST** respect the step budgets in the budgets section. On exhaustion it **MUST** stop
   and leave the tree in a consistent, verifiable state.
5. A pass **MUST NOT** read a trait whose epoch is not the node's current epoch (see the
   epoch-based staleness section).

## 5. Triggers

Successful rewrites emit triggers, which the scheduler uses to enqueue dependent work:

| Trigger | Meaning |
|---|---|
| `ConstantUnfolded` | A node's value became compile-time known. |
| `UsesReplaced` | Uses of a node were replaced, potentially making the node or its users constant or dead. |
| `NodeDeleted` | A node was removed; its former users may now be foldable. |
| `TraitChanged` | A trait changed and dependent traits may be stale. |
| `StaticDiscovered` | A frontend `is_static` claim was confirmed or a new compile-time value was found. |

A rewrite that changes no fact **MUST NOT** emit a trigger. Emitting a trigger for a no-op risks a
non-terminating cascade and is a correctness defect.

## 6. Worklist scheduler and cascade

### 6.1 Scheduler

1. The scheduler collects `(pass, node)` pairs into a **worklist**, **deduplicates** them, and runs
   until the worklist drains to a **fixpoint**: a state in which no scheduled work produces a new
   trigger.
2. Order of processing within one function **MUST** be deterministic, so cascade order is
   reproducible.
3. A **per-function step budget** guarantees termination even if triggers keep firing. When the
   budget is exhausted the scheduler **MUST** stop scheduling further passes for that function and
   report the exhaustion.
4. The scheduler **MUST NOT** schedule work for a node whose governing function is not yet ready in
   the current phase.

### 6.2 Canonical cascade

The reference cascade for a fold:

```
4 * 16
  -> const 64
  -> mark is_comptime / is_constant / const_value = 64
  -> prove not addressed / not runtime-mutable
  -> replace all uses with literal 64
  -> node dead -> delete
  -> downstream nodes now constant -> enqueue
```

Each hop emits a trigger. The worklist drains until nothing new is provable. The cascade is the
mechanism by which one fold can make a whole subtree constant; it **MUST** reach the same fixpoint
regardless of the order in which independent items are processed.

## 7. Parallelism and determinism

1. HIR passes **MUST** parallelize **per function**. Independent function trees may be processed
   concurrently.
2. Within one function, passes **MUST** run **sequentially**, so cascade order is deterministic.
3. Cross-function effects, such as cross-module constant propagation and requests that depend on
   callees, **MUST** use a **module-level fixpoint**:
   - run per-function passes in parallel;
   - run a deterministic module phase;
   - re-enqueue only the functions whose inputs changed.
4. The module phase **MUST** be deterministic: it processes functions in a stable order and folds
   their results in a stable order.
5. The determinism guarantee of [000 — Overview](000-overview.md) binds the HIR optimizer: for a
   fixed `Config` and input, output **MUST** be byte-identical independent of thread count and of
   `-j`.

## 8. Epoch-based staleness

1. Each node carries an epoch counter. A trait is valid only for the node's **current epoch**.
2. A rewrite that changes a trait **MUST** advance the affected node's epoch.
3. A rewrite that can affect a related node **MUST** mark the relationship dirty and propagate
   invalidation along the relationship edge.
4. A pass in a parallel worker **MUST NOT** consume a trait that became stale after the worker read
   it. Epoch checks **MUST** detect this.
5. A stale derived trait **MUST** be recomputed before it is consumed. Recomputing it **MUST** be
   part of the cascade, not a silent fallback to a default.

This model is what makes parallel HIR passes safe without a global lock.

## 9. Comptime evaluator

The comptime evaluator is an interpreter over HIR subgraphs. It computes compile-time values and
marks them on the nodes.

### 9.1 Eligibility

An HIR subgraph is eligible for comptime evaluation **only if** all of the following hold:

1. It has **no side effects**.
2. It involves **primitives only** (no aggregate or opaque operations that cannot be evaluated
   element-wise).
3. It performs **no global mutation**.
4. It performs **no I/O**.
5. It stays within the loop and recursion budgets (see the budgets section below).

If any condition fails, the evaluator **MUST** bail out cleanly and defer the computation to VIR.
A bailout **MUST NOT** mark any partial result as compile-time known.

### 9.2 Outputs

On successful evaluation, the evaluator writes, in order:

1. `const_value`: the computed value.
2. `is_comptime` and `is_constant`: the proven properties.

`const_value` **MUST** be present if and only if `is_comptime` holds.

### 9.3 Seeding

The frontend `is_static` attribute (the frontend-facing `static` concept) **seeds** the evaluator:
HIR treats `is_static` as the claim "this is compile-time" and **MUST** validate the claim before
setting `is_comptime`. A false `is_static` claim is handled by the attribute validation rule of
[002 — Traits](002-traits.md): warning, overwrite, mark derived.

## 10. `defer` expansion

1. When HIR optimization is enabled, the optimizer **MUST** expand every `defer` body at every
   scope-exit path and erase the `defer` marker. This leaves zero runtime residue.
2. Expansion **MUST** obey the ordering and determinism rules of [003 — HIR](003-hir.md).
3. When HIR optimization is disabled (`-O0`), the optimizer does not expand `defer`; lowering
   performs the same expansion. Either way, no `Defer` node reaches VIR.

## 11. Optimization-level behavior

| Level | HIR behavior | VIR |
|---|---|---|
| `-O0` | Traits validated only. | off |
| `-O1` | Builtin folds and discovery. | off |
| `-O2` | Full cascade plus comptime evaluation. | **on** |
| `-O3` | `-O2` plus special AST transforms (loop-unfold/vectorize, then constant-unfold, then comptime). | on |
| `-Ofast` | `-O3` plus `-march=native` and fast-math. | on |
| `-Oz` | Size-tuned discovery and folds. | on |

Compiler-friendly C is emitted at **all** optimization levels. `-O3` only adds more aggressive AST
transforms; it does not change the trait contract.

## 12. HIR never inlines

HIR **MUST NOT** inline code. It proves that a call is small and eligible, then issues an `Inline`
request (see [002 — Traits](002-traits.md)). Inlining is a VIR/IPA transform (see
[007 — VIR Optimizer](007-vir-optimizer.md)). This separation keeps HIR's work cheap and
parallelizable.

## 13. Default budgets

All budgets are configurable through the API and CLI. The defaults are:

| Budget | Default |
|---|---|
| `comptime.max_iterations` | `4096` |
| `comptime.max_recursion_depth` | `256` |
| `comptime.max_steps` | `1000000` |
| `comptime.max_aggregate_elements` | `65536` |
| `hir.max_rewrites_per_function` | `100000` |
| `hir.max_rewrites_per_module` | `1000000` |

A budget exhaustion is a normal, reported outcome; it **MUST NOT** be treated as a crash and
**MUST NOT** produce partially annotated output that lowering would accept as complete.

## 14. Invariants

- The worklist drains to a fixpoint or stops at an explicit budget: the scheduler never loops
  forever.
- Every successful rewrite emits exactly the triggers needed to re-enqueue affected work.
- A no-op rewrite emits no trigger.
- Every pass validates the epochs of traits it reads.
- After HIR optimization, every trait consumed by lowering is complete and epoch-valid.
- HIR performs no inlining.
- No `Defer` node survives HIR optimization when HIR optimization is enabled.
- Output is deterministic for a fixed `Config` and input, independent of thread count.

## 15. Example

For `y = x + 4` with `x = 4`:

1. The comptime evaluator folds `x` to `const_value = 4`, marking `is_comptime` and `is_constant`.
2. `ConstantUnfolded` triggers the fold of `y` to `8`.
3. `foo(x, y)` is proven small; HIR issues a soft `Inline` request instead of inlining it.
4. The `sqrt` call folds to a floating-point constant.
5. The worklist drains; the module reaches a fixpoint with `println` left as the only real call.

The normative end-to-end walkthrough is [014 — Worked Example](014-worked-example.md).

## 16. Cross-references

- [000 — Overview](000-overview.md)
- [001 — Architecture](001-architecture.md)
- [002 — Traits](002-traits.md)
- [003 — HIR](003-hir.md)
- [005 — Lowering](005-lowering.md)
- [007 — VIR Optimizer](007-vir-optimizer.md)
- [011 — Diagnostics](011-diagnostics.md)
- [013 — Build & Packaging](013-build-packaging.md)
- [014 — Worked Example](014-worked-example.md)