libvct-spec/spec/002-traits.md

002 — Traits

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

1. Purpose

The trait model is the vocabulary libVCT uses to describe facts about IR nodes. It is the contract between the two optimization halves of the library: HIR discovers and derives traits, and VIR reads them and transforms accordingly. VIR performs no discovery of its own. Everything VIR may rely on is an attribute, a request, or a relationship defined here.

2. Scope

This file specifies:

• the Trait union of an Attribute, a set of Requests, and a set of Relationships;
• the complete v1 attribute set and request catalog;
• relationship flags and relation attributes;
• the query API semantics a trait consumer may assume;
• the trait representation and staleness model;
• request conflict resolution.

Out of scope: how HIR derives attributes (see 004 — HIR Optimizer), how lowering copies traits onto VIR entities (see 005 — Lowering), and how the VIR optimizer acts on requests (see 007 — VIR Optimizer).

Traits are public. Frontends embed trait vocabulary; frontends are not required to derive traits themselves.

3. Definitions

Term	Definition
Node	An arena-owned HIR entity carrying one Trait.
Attribute	A fact about a node (its type, value, mutability, and so on).
Request	An attribute-derived suggestion from HIR to VIR. Never ad-hoc.
Relationship	A directed, traceable edge from a node to another node.
Suggested	An attribute or request set by the frontend at build time.
Derived	A trait produced by the HIR optimizer. Authoritative.
Epoch	A monotonically increasing generation counter used to invalidate stale traits.
Consumer	Any component that reads traits. VIR is the primary consumer.

The Trait is the union of the three sub-structures:

struct Trait {
    Attribute  attr;
    Request[]  reqs;
    Relation[] rels;
}

A trait attaches to exactly one node. Trait values are per-node and, after HIR optimization, are complete for every node that lowering consumes.

4. Attribute model

Attributes are facts about a node. They share one namespace with two origins:

• Suggested: set by the frontend at build time through the builder API.
• Derived: produced by the HIR optimizer during the cascade. Derived attributes are authoritative.

Every attribute carries an attr_source marker recording whether its current value is suggested or derived.

4.1 Attribute validation rule

This rule is normative and applies to every suggested attribute:

1. When the frontend suggests an attribute, HIR MUST validate the suggestion against what it can prove.
2. If the suggested value is wrong or unprovable-in-the-suggested-direction, HIR MUST emit a warning, MUST overwrite the attribute with the correct value, and MUST mark attr_source = derived.
3. The warning MUST be promoted to an error under -Werror. A frontend MAY opt out for a specific category with -Wno-error=<category>, or for every category with a bare -Wno-error.
4. A correct suggestion MUST be preserved and continue to report attr_source = suggested until HIR derives a replacement value.

HIR MUST NOT silently accept a wrong suggestion. A consumer MUST treat derived attributes as authoritative and MUST NOT re-derive them.

4.2 v1 attribute set

Attribute	Meaning	Typical source
ty	The node's VIR type.	Both
const_value	Present if and only if the value is known at compile time.	Derived
is_static	Frontend-declared compile-time value (the frontend-facing static concept). Seeds the comptime evaluator.	Suggested
is_comptime	HIR-proven compile-time value.	Derived
is_constant	Value is constant; not necessarily compile-time-evaluable.	Derived
is_used	Node has at least one use.	Derived
is_mutably_used	Node is mutated through at least one use.	Derived
is_addressed	Address taken via pointer or reference.	Derived
escapes	Value escapes its defining scope.	Derived
is_runtime_mutable	Storage is written at runtime.	Derived
may_change_at_runtime	The observable value may differ between reads or executions (external state). Distinct from is_runtime_mutable.	Derived
is_volatile	Accesses are volatile: not eliminated, not reordered, and not promoted to SSA.	Suggested
is_atomic	Accesses are atomic and carry a declared memory ordering.	Suggested
complex	Frontend-provided; gates the NoOptimize request.	Suggested
layout	Pinned aggregate ABI: field offsets, total size, and alignment.	Suggested

is_runtime_mutable describes storage writes; may_change_at_runtime describes externally observable value change. They are independent and both MUST be tracked.

is_static is trusted by HIR as "this intends to be compile-time", but it is still validated: HIR MUST verify the claim before marking is_comptime.

is_volatile and is_atomic force a value to memory; lowering and later passes MUST NOT promote such a value to SSA (see 005 — Lowering). The layout attribute pins an aggregate's ABI; the C backend MUST emit explicit padding and static assertions for a layout-pinned aggregate (see 008 — C Backend).

5. Request model

Requests are attribute-derived suggestions. A frontend suggesting a request that no attribute supports is invalid and HIR MUST reject it with a diagnostic.

Each request has a strength:

• Soft: a suggestion VIR MAY decline.
• Strong: violating it is likely a bug. A capable consumer MUST honor it or report an error with a DenyReason of Illegality or ContradictsTrait (see 007 — VIR Optimizer).

Every attempted request produces 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. On acceptance, reason is unspecified and note MAY be empty.

5.1 DenyReason

Enumerator	Meaning
CostModel	Profitable only under a different cost model.
Illegality	The transform would be incorrect.
AlreadyDone	No-op; the goal already holds.
Unsupported	VIR does not implement it yet.
ContradictsTrait	Conflicts with a stronger fact.
TooLarge	Exceeds a size budget.
NoTargetSupport	The backend or target cannot express it.

6. Request catalog

The v1 catalog contains 42 requests. Requests marked Strong are noted; all others are Soft.

6.1 Inlining and call edges (10)

Request	Strength	Meaning
Inline	Soft	Callee is a candidate for inlining.
AlwaysInline	Strong	Callee must be inlined.
NoInline	Strong	Callee must not be inlined.
TailCall	Soft	Prefer tail-call formation.
MustTail	Strong	Tail-call formation is required.
NoTail	Strong	Tail-call formation must not occur.
Devirtualize	Soft	Call target is expected to resolve to one target.
ColdCall	Soft	Call is unlikely; optimize for size.
LikelyCall	Soft	Call is likely executed.
UnlikelyCall	Soft	Call is unlikely executed.

6.2 Loops (12)

Request	Strength	Meaning
Vectorize	Soft	Vectorize the loop.
Unroll(factor)	Soft	Unroll by factor.
Interleave(count)	Soft	Interleave count iterations.
Peel(count)	Soft	Peel count iterations.
Distribute	Soft	Distribute loop bodies.
Fuse	Soft	Fuse adjacent loops.
Jam	Soft	Fuse loops by jamming.
Unswitch	Soft	Unswitch loop-invariant conditions.
Rotate	Soft	Rotate the loop.
LICM	Soft	Explicit request to hoist loop-invariant code (an action).
LoopInvariant	Soft	A proven invariant property VIR may exploit (a property).
MustProgress	Soft	The loop is guaranteed to make progress.

LICM and LoopInvariant are distinct: one requests an action, the other asserts a property. Both MUST be retained by HIR.

6.3 Memory effects (13)

Request	Strength	Meaning
NoAlias	Soft	The value aliases no other relevant value.
Restrict	Soft	The value may be marked restrict.
NonNull	Soft	The value is not null.
Align(n)	Soft	The value is aligned to n.
ReadOnly	Soft	Region-level read-only fact.
WriteOnly	Soft	Region-level write-only fact.
NoRead	Soft	Primitive fact on an access edge: no read occurs.
NoWrite	Soft	Primitive fact on an access edge: no write occurs.
NoCapture	Soft	The value is not captured by a callee.
Dereferenceable(n)	Soft	At least n bytes are dereferenceable.
Constant	Soft	The value is immutable.
NoUndef	Soft	Reserved; meaningful only on the LLVM path.
Prefetch	Soft	Insert a prefetch hint.

NoRead/NoWrite are primitives on an access edge; ReadOnly/WriteOnly are region-level facts derived from them. All four are retained, and their scope difference is part of their meaning.

6.4 Control flow, assumptions, and optimization control (7)

Request	Category	Strength	Meaning
HotPath	Control flow	Soft	Block is likely executed.
ColdPath	Control flow	Soft	Block is unlikely executed.
Unreachable	Control flow	Soft	Execution never reaches this point.
NoReturn	Control flow	Soft	The call never returns.
Assume(pred)	Assumptions	Soft	pred holds at this point.
Range(lo, hi)	Assumptions	Soft	The value lies in [lo, hi].
NoOptimize	Optimization control	Strong	The region must not be rewritten. Requested only when the frontend sets complex.

HIR MUST NOT issue NoOptimize unless complex is set on the node. The resulting region is an optimization barrier (see 005 — Lowering).

7. Relationships

Relationships are directed edges that HIR leaves for the non-constant world. They are traceable up and down to a terminal node.

7.1 Relationship flags

Flag	Meaning
is_offspring	The edge cannot be traced up.
is_ancestor	The edge cannot be traced down.
is_common	Branch point; a consumer must choose a direction.
has_siblings	The node connects down to two or more nodes.
is_apex	The node participates in a cycle (a → b → c → d → a), usually from polymorphism.

An apex SHOULD normally be ironed out by HIR. A residual apex after the HIR cascade typically arises from polymorphism, and a consumer that walks into one MUST handle the cycle rather than loop forever.

7.2 Relation attributes

Each relationship edge carries a small attribute set:

Attribute	Meaning
was_changed	The related value changed since the relationship was recorded.
is_mutable	The related value is mutable.
is_pointer	The relationship passes through a pointer.

8. Query API semantics

The trait query interface is the only channel through which VIR obtains facts. Its guaranteed semantics are:

1. A query MUST return the trait values valid for the node's current epoch. A query against a node whose trait is stale for the current epoch MUST fail rather than return stale data.
2. A query MUST NOT trigger analysis or re-derivation. It is a read of already-derived facts.
3. Reading const_value when absent MUST be reported as "not compile-time known" and MUST NOT be interpreted as zero or any other value.
4. Walking a relationship in the available direction(s) MUST terminate at a terminal node or report that the walk hit an apex cycle.
5. A consumer MUST NOT invent, weaken, or generalize a fact absent from the trait. VIR must not assume a property that no trait states.
6. Query results MUST be deterministic: for a fixed module and epoch, the same query returns the same result regardless of thread count.

9. Representation

Representation has two parts: an embedded dense Trait struct on every node is primary, so common attributes are read without indirection; an optional sparse side-channel holds rare or frontend-extensible attributes and MAY be absent. A consumer MUST observe the same logical trait regardless of which part carries it. The dense struct is the reference representation; the side-channel is an optimization, not a semantic difference.

10. Staleness

Traits are annotated in place, so a rewrite can invalidate dependent traits. Staleness is resolved with epoch/generation counters:

1. Each node carries an epoch. 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 that relationship dirty and propagate the invalidation along the relationship edge.
4. A derived trait computed from a node whose epoch has advanced MUST be recomputed before it is consumed.
5. Epoch counters MUST be sufficient to keep parallel HIR workers from reading stale traits. This is why the model survives parallel passes.

11. Request conflict resolution

Requests from independent attributes can conflict. Resolution is normative:

1. Strength ordering. Strong beats Soft. When a Strong and a Soft request conflict, the Strong request wins and the Soft request is discarded without a diagnostic.
2. Conflicting Strongs. When two Strong requests conflict, HIR MUST emit a diagnostic and MUST reject the frontend suggestion. The derived, authoritative request wins.
3. Canonical opposing pairs are {Inline, AlwaysInline} against {NoInline}, and {TailCall, MustTail} against {NoTail}. In the named pairs Inline/NoInline and TailCall/NoTail, the No* member is Strong, so those resolve by rule 1; the corresponding Strong-versus-Strong pairs (AlwaysInline/NoInline, MustTail/NoTail) resolve by rule 2.
4. A rejected suggestion MUST NOT silently disappear; the diagnostic and a remark MUST record the rejection.

12. Invariants

• Every node carries exactly one Trait.
• Every RequestResult denial carries both a DenyReason and a non-empty note.
• A derived attribute is authoritative; consumers MUST NOT re-derive it.
• const_value is present if and only if is_comptime holds for the node.
• No consumer reads a trait whose epoch is not the node's current epoch.
• The trait vocabulary is versioned independently of the textual IR format (see 013 — Build & Packaging).

13. Example

For y = x + 4 where HIR proves x is compile-time 4, the node x carries is_comptime, is_constant, and const_value = 4 with attr_source = derived; the fold marks downstream nodes is_comptime and issues an Inline request when the call is proven small. A frontend that had suggested is_comptime = false on x receives a warning and sees HIR overwrite it. The full walkthrough is normative in 014 — Worked Example.

14. Cross-references

• 000 — Overview
• 001 — Architecture
• 003 — HIR
• 004 — HIR Optimizer
• 005 — Lowering
• 007 — VIR Optimizer
• 011 — Diagnostics
• 013 — Build & Packaging
• 014 — Worked Example