Proposal: LLGo LLVM-IR escape analysis and heap-to-stack transform

[MeteorsLiu]

LLGo LLVM-IR escape analysis and heap-to-stack transform

Status: proposal

Summary

LLGo should implement its own escape-analysis and heap-to-stack transformation pass over the complete LLVM module produced by LLGo. The pass should be integrated at the same architectural boundary as internal/cabi: frontend lowering first emits the complete package module, then an LLGo-owned module transformer analyzes and rewrites that module before the generic LLVM optimization pipeline runs.

The proposed default pipeline is:

Go source
    -> go/ssa
    -> cl lowers the complete package to LLVM IR
    -> LLGo escape analysis and heap-to-stack rewrite
    -> LowerLargeAggregates and C ABI rewrite
    -> generic LLVM optimization passes

The escape analyzer operates on LLVM SSA def-use chains, not on Go AST or x/tools go/ssa. It starts from LLGo allocation calls and LLVM function parameters, follows their transitive uses, computes allocation escape decisions and parameter leak summaries, and then rewrites proven-local heap allocations into stack allocations.

The work has two phases:

1. Implement a conservative LLVM-SSA use analysis and heap-to-stack rewrite. Unknown uses escape. This phase produces structured -m summaries but applies only generic pointer-flow rules.
2. Add LLGo-specific Go semantic rules for channels, maps, interfaces, closures, slices, goroutines, defers, panic/recover, typed memory copies, C declarations, and pointer/uintptr contracts. These rules make the LLGo pass more precise than generic LLVM AAHeapToStack.

When detailed diagnostics are requested, the analysis may retain predecessor edges as an explanation graph. That graph exists only to explain the computed -m result; it is not the analysis solver.

Why LLGo needs its own pass

There are three independent reasons.

1. Go's escape analyzer is AST/Go-compiler-IR based and tightly coupled

The Go compiler's escape analyzer is not a reusable SSA pass. It walks cmd/compile IR, constructs a location graph, and depends on Go compiler concepts including expression nodes, assignment holes, loop depth, closures, pragmas, inlining state, result parameters, and export tags.

Porting it to LLGo would require recreating a large part of cmd/compile's frontend-specific environment and continuously tracking internal Go compiler changes. The analysis difficulty and coupling are disproportionate to LLGo's needs.

2. LLVM AAHeapToStack cannot produce the required -m summaries

AAHeapToStack answers a narrow optimization question: can a recognized allocation call be replaced by an alloca? A successful rewrite is evidence that one allocation is local. A failed rewrite is only unknown.

It does not expose the source-level information LLGo needs for -m, including:

• p does not escape;
• leaking param: p;
• leaking param content: p;
• p flowing to result N at dereference level K;
• mutator and called-function effects needed for summary composition;
• an explanation path tied to Go source positions.

These summaries must be computed and retained by LLGo itself.

3. LLVM AAHeapToStack cannot optimize according to Go semantics

Generic LLVM sees calls, pointers, aggregates, byte copies, and opaque runtime helpers. It does not know LLGo's language/runtime contracts. For example:

• the pointer passed to runtime.ChanSend is a temporary transport address borrowed until the call returns, while pointer-containing bytes copied from that address may remain in channel storage;
• a slice value contains a backing-store pointer whose behavior under append depends on capacity and possible reallocation;
• an interface payload may be represented directly or copied into an indirect box according to LLGo's ABI classification;
• a closure environment contains captured Go values and escapes according to the closure value's uses;
• goroutine startup data must outlive the caller even when the callee does not retain an argument after startup;
• typed memory moves preserve Go pointer fields in ways that an untyped byte-copy model cannot recover safely;
• //go:noescape and uintptr keepalive are Go compiler contracts, not generic LLVM pointer attributes.

An LLGo-owned pass can model these semantics explicitly and conservatively.

Verified current pipeline

The current repository already has the required transformation boundary.

internal/build/build.go calls cl.NewPackageExWithEmbedMeta, which returns the generated package and its live llvm.Module. For a cache miss, the current order is:

cl.NewPackageExWithEmbedMeta
    -> ModuleHook observes the complete module
    -> llabi.LowerLargeAggregates
    -> cabi.Transformer.TransformModule
    -> LLVM VerifyModule
    -> Module.RunPasses(default<O*>)

internal/cabi/cabi.go demonstrates the intended implementation shape. TransformModule walks LLVM functions, basic blocks, and call instructions, gathers rewrite candidates, and then rewrites function signatures and call sites directly in the completed module.

The escape pass should use the same module-transform pattern. It should not be implemented inside individual cl lowering cases and should not require changes to xgo-dev/llvm merely to define a normal LLGo pass.

The pass should run before LowerLargeAggregates and C ABI rewriting by default. At that point the module is complete, but Go aggregate/function relationships have not yet been obscured by ABI signature changes. The implementation must verify this ordering with C ABI and large-aggregate tests; if a specific rewrite requires a later position, that dependency must be explicit rather than silently inferred from transformed IR.

Goals

• Analyze the complete LLVM module emitted for one LLGo package.
• Recognize LLGo heap-allocation sites and prove when their result is frame-local.
• Produce parameter heap/result summaries with dereference levels for -m and direct-call composition.
• Rewrite proven-local runtime.AllocZ and runtime.AllocU calls into equivalent stack allocations.
• Preserve allocation size, alignment, initialization, lifetime, pointer identity, and target restrictions.
• Treat every unsupported use conservatively.
• Add Go semantic transfer rules independently from the generic pointer-flow engine.
• Export the minimum summaries needed by separately compiled importing packages.
• Keep analysis facts independent of the selected GC implementation.

Out of scope

• Porting cmd/compile/internal/escape.
• Using x/tools go/ssa as the final analysis IR.
• Enabling all of LLVM Attributor or depending on unstable debug output from AAHeapToStack.
• Parsing LLVM optimization remarks as a compiler interface.
• Stack allocation of maps, channels, goroutine startup records, or other runtime-owned objects before their complete lifetime contracts are modeled.
• A context-sensitive whole-program pointer analysis in Phase 1.
• Byte-for-byte compatibility with every Go -m message in the first implementation.
• Choosing a persistent summary wire layout before the in-memory summary and its consumers are validated.

Module boundary and pass position

Input

The pass consumes the complete LLVM package module immediately after cl generation. It sees:

• all LLVM functions defined in the package;
• direct calls to package functions, imported declarations, runtime helpers, and C declarations;
• LLVM parameters, return instructions, loads, stores, GEPs, casts, phi/select nodes, aggregate operations, intrinsics, and globals;
• LLGo allocation calls generated by ssa/memory.go and other lowering helpers;
• source/debug metadata already emitted by LLGo;
• additional minimal LLGo semantic/source metadata required by this proposal.

The pass does not consume the original Go AST. It may receive immutable type/source facts recorded during lowering, but the analysis graph and rewrite operate on LLVM values and instructions.

Output

The pass returns:

• a rewritten LLVM module;
• per-allocation decisions and reasons;
• per-function parameter summaries;
• source-positioned structured diagnostics when requested;
• package summary facts for later metadata transport.

The transformer should mutate the live module synchronously, as cabi.TransformModule does. Analysis data should be released after diagnostics and package metadata have consumed it.

Ordering

The initial order should be:

complete cl-generated module
    -> escape analysis fixed point
    -> heap-to-stack rewrite
    -> VerifyModule
    -> LowerLargeAggregates
    -> C ABI TransformModule
    -> existing LLVM optimization pipeline

Running before generic LLVM optimization preserves allocation/runtime helper identities and source associations. Later LLVM passes remain free to optimize the rewritten allocas.

Required lowering metadata

LLVM SSA contains pointer flow, but it does not retain every Go source concept required for summaries and Go-specific transfer rules. LLGo lowering should provide only the minimum facts that cannot be reconstructed reliably.

The pass needs stable associations for:

• Go function identity and source position;
• LLVM parameter to Go receiver/parameter index and source name;
• LLVM result component to Go result index;
• heap allocation call to Go source allocation position and display name;
• pointer-carrying components of lowered Go aggregates when LLVM layout alone is insufficient;
• semantic identity of compiler-generated operations when a runtime symbol name is not a stable contract.

The exact representation may be an in-memory side table, LLVM metadata, or a combination. It must survive until this pass and must not become part of the runtime ABI. A symbol-name heuristic is acceptable only for symbols that LLGo already treats as a compiler/runtime contract and covers with focused tests.

No speculative source metadata should be added. Each field must have a demonstrated analysis or diagnostic consumer.

Analysis basis

Analysis units and cached results

The analysis has two root kinds:

• an eligible LLGo allocation call, whose result is local, returned, heap, or unknown;
• a pointer-carrying formal parameter, whose NoCapture state is cached for heap-to-stack and whose flows may also be recorded in locationGraph for summaries.

Only formal-parameter NoCapture facts are used as the interprocedural optimization cache. The cache key identifies a defined LLVM function and one formal parameter. An allocation remains a caller-local root; when it crosses a direct call, the caller queries the cached callee-parameter NoCapture fact. Parameter leak summaries are derived separately from locationGraph and never feed an allocation decision.

The dependency direction is one-way: LLVM use traversal may write locationGraph for -m, but NoCapture, allocation decisions, and rewrite logic never read locationGraph or imported diagnostic summaries.

The pass creates allocation roots for direct calls to eligible LLGo allocation helpers and parameter roots for pointer-carrying Go receivers and parameters represented in the LLVM signature. Pointer-carrying closure components may become parameter roots when lowering metadata identifies them. runtime.AllocRoot is excluded because its scanned-root and cross-goroutine lifetime contract is not an ordinary heap allocation contract.

Per-root LLVM use traversal

The function-local walker should use the same shape as LLVM Attributor::checkForAllUses, which is used by AAHeapToStackFunction::UsesCheck. It starts with every LLVM use of the root value, processes a worklist of uses, and follows the users of derived values. When the tracked pointer is stored as a value, the walker applies the same AAPointerInfo-backed exact-copy query as LLVM getPotentialCopiesOfStoredValue(..., OnlyExact=true): proven load copies are added to the existing use worklist, while an incomplete proof makes the root escape. At a direct call, heap-to-stack queries the callee parameter's cached NoCapture fact. Phase 1 does not build a NoFree cache; bodyless, runtime, C, indirect, and unresolved calls remain capturing.

The heap-to-stack traversal state is:

use          exact LLVM Use, including its operand position

Each evaluation owns a fresh visited map keyed by this state. If insertion reports that the state was already visited, that path stops. Use rather than Instruction is required because the same instruction can use a root in different operand roles. Following a phi, select, GEP, cast, or loop-carried value eventually reaches the same use state and terminates without CFG traversal, loop decomposition, liveness analysis, or call-graph SCC construction.

Conceptually:

walk(root):
    worklist <- every use of root.value
    visited  <- empty map
    local    <- true

    while worklist is not empty:
        state <- pop worklist
        if state is already in visited:
            continue
        add state to visited
        if detailed diagnostics are requested:
            locationGraph.add(state)  // write-only; never queried by this walk

        switch exact user and operand role:
        case load address:
            stop this path
        case store address:
            stop this path; the address itself is not retained
        case store value:
            if every potential copy is proven exact:
                add every use of every copied load result to worklist
            else:
                local <- false
        case GEP, pointer-preserving cast, phi, or select:
            add every use of the derived result to worklist
        case return value:
            local <- false
        case direct call argument:
            local <- local && NoCapture[callee, parameter]
        case bodyless, runtime, C, indirect, or unresolved call argument:
            local <- false
        case verified LLGo semantic operation:
            apply its transfer rule
        default:
            local <- false

    return local

Exact-copy forwarding

User story and motivation

An unoptimized module may preserve local pointer assignments as memory operations:

define void @local_copy() {
entry:
  %object = call ptr @runtime.AllocU(i64 8)
  %p.addr = alloca ptr
  store ptr %object, ptr %p.addr
  %p = load ptr, ptr %p.addr
  %q.addr = alloca ptr
  store ptr %p, ptr %q.addr
  %q = load ptr, ptr %q.addr
  store i8 1, ptr %q
  ret void
}

The allocation does not outlive @local_copy. A plain def-use walker nevertheless stops at store ptr %object, ptr %p.addr, because the allocation pointer has crossed into memory. Treating that store as an immediate escape would make HeapToStack depend on an earlier mem2reg-style optimization and would miss ordinary local assignments whenever their slots remain in the input IR.

Exact-copy forwarding proves that the first store can produce %p, that the second store can produce %q, and then resumes the existing use walk at %q.uses(). The final store i8 1, ptr %q writes through the allocation rather than publishing its address, so the allocation remains eligible for stack conversion.

The same mechanism must preserve the escaping case:

@sink = external global ptr

define void @escaping_copy() {
entry:
  %object = call ptr @runtime.AllocU(i64 8)
  %slot = alloca ptr
  store ptr %object, ptr %slot
  %copy = load ptr, ptr %slot
  store ptr %copy, ptr @sink
  ret void
}

The local slot query returns %copy, so the root-use walker reaches store ptr %copy, ptr @sink. Because an externally visible mutable global cannot provide a complete set of exact load copies, that second query fails and the store remains a capturing use. The allocation therefore stays on the heap.

The required rule is: crossing a store/load boundary is safe only when the analysis returns the complete may-set of exact load copies and the ordinary use walker proves every returned copy local. An empty complete set is safe; an incomplete set is an escape.

Exact-copy forwarding is the only Phase 1 rule that crosses a store/load memory boundary. Its implementation follows LLVM 19.1.7 Attributor::checkForAllUses and AA::getPotentialCopiesOfStoredValue(..., OnlyExact=true). The responsibilities remain separate:

1. pointerInfo reproduces the required AAPointerInfo behavior for an underlying memory object. It follows address-preserving uses and records accesses relative to that object.
2. getPotentialCopiesOfStoredValue queries those access records for one store and either returns the complete conservative set of possible load copies or fails without returning a partial set.
3. The shared checkForAllUses engine consumes the returned copies. In the allocation walk it follows copied allocation values; while constructing pointerInfo, it follows copied addresses and preserves their offset state. The per-analysis predicate still owns instruction classification.

The generic store-copy interception runs before the caller's predicate. A successful query substitutes uses of the returned loads for the original store-value use. A failed query falls through to the predicate, where storing the tracked value invalidates HeapToStack or pointerInfo as appropriate.

pointerInfo starts the associated object at offset zero. GEPs add target-layout byte offsets. Pointer-preserving casts retain offsets. Selects and returns pass offsets through. Phis merge offsets and apply LLVM's explicit recurrence rule: an invariant recurrence keeps its offsets, while a non-invariant recurrence becomes unknown. Constant-expression casts and GEPs follow the same rules. Loads record reads. Stores through the tracked address record writes and their content lattice value. Atomic RMW and cmpxchg record their LLVM read/write roles but invalidate the state when the tracked address is used as a published value operand. Calls translate the callee or call-site-argument pointerInfo; memory intrinsics record their source and destination ranges. Any use not handled by LLVM's AAPointerInfoFloating::updateImpl invalidates the state rather than receiving an LLGo-specific rule.

Each access contains the local instruction, the actual remote memory instruction for an imported callee access, all possible {offset, size} ranges, read/write and may/must bits, content in LLVM's undetermined / unknown / value lattice, and the accessed type. Sizes come from the module data layout. Multiple possible ranges turn a must-access into a may-access. Unknown offsets or sizes overlap every range. Accesses with the same local and remote instruction are merged exactly as AAPointerInfo::State::addAccess merges them and are indexed by their ranges and remote instruction.

The generic walker consumes a stored-value query as follows:

checkForAllUses(root, predicate, equivalentUse):
    worklist <- every use of root

    while worklist is not empty:
        use <- pop worklist

        if use.user is Store and use is store.operand[0]:
            copies, complete <- getPotentialCopiesOfStoredValue(store, OnlyExact=true)
            if complete:
                for each copy in copies:
                    for each newUse in copy.uses:
                        require equivalentUse(oldUse=use, newUse=newUse)
                        append newUse to worklist
                continue  // the predicate does not see the original store

        follow <- false
        require predicate(use, &follow)
        if follow:
            append use.user.uses to worklist

The stored-value query is:

getPotentialCopiesOfStoredValue(store, OnlyExact=true):
    destination <- store.pointerOperand
    objects, complete <- underlyingObjects(destination)
    if not complete:
        return failure

    pendingCopies <- empty ordered set
    pendingInfos  <- empty list

    for each object in objects:
        if object is undef:
            continue

        if object is null:
            if null dereference is undefined in this function and
               destination simplifies exactly to null:
                continue
            return failure

        if object is not an alloca, supported global, or noalias call result:
            return failure

        info <- pointerInfo(object)
        if info is missing or invalid:
            return failure

        nullOnly     <- true
        nullRequired <- false

        checkReader(access, isExact):
            if access is not a read:
                return success

            update nullOnly and nullRequired from access.content

            if OnlyExact and not isExact and
               content is neither consistently null nor undef:
                return failure

            if nullRequired and a possible non-null or unknown content exists:
                return failure

            if OnlyExact and access.remoteInstruction is not Load:
                return failure

            pendingCopies.add(access.remoteInstruction)
            return success

        complete <- info.forAllInterferingAccesses(
            query                   = store,
            findInterferingWrites   = false,
            findInterferingReads    = true,
            check                  = checkReader,
            threadingAndReachabilityGate,
            exactMustWriteBlockers)
        if not complete:
            return failure

        pendingInfos.append(info)

    // Do not expose partial copies or dependencies before every object succeeds.
    record dependencies on pendingInfos
    return success with pendingCopies

Situation	Result
Underlying objects cannot be enumerated completely	Fail without returning partial copies
Underlying object is undef	Ignore that object
Destination simplifies exactly to null and null dereference is undefined	Ignore that object because the access is undefined
Null is a valid address, or the destination is an offset from null	Fail
Object is an alloca	Query its pointerInfo
Global has local linkage	Query its pointerInfo
Global is constant and has an initializer	Query its pointerInfo
Global is externally visible and mutable	Fail
Object is a recognized noalias call result	Query its pointerInfo
Any other underlying object	Fail
pointerInfo is unavailable, incomplete, or invalid	Fail
Access does not read the queried range	Ignore it
Read range is disjoint from the store range	Ignore it
Threading gate permits reachability reasoning and no unblocked path reaches the read	Ignore it
An exact must-write overwrites the complete stored range before a read on every path	Treat that write as a blocker; the old value does not reach that read
Exact overlapping ordinary load	Add the load result to pendingCopies
Exact load uses a different LLVM value type but reads the same byte range	Add the load result; exactness is range-based
Multiple loads may read the value	Add every load result; the result is a complete may-set
No load may read the value	Succeed with an empty copy set
Non-exact read is proven consistently null or undef	Permit only LLVM's null/undef exception; the remote reader must still be a load
Non-exact read has unknown or possibly non-null content	Fail
A previous non-exact read requires null-only content and another read may be non-null	Fail
Interfering remote access is a direct-callee load translated to this call site	Add the remote load result
Interfering remote access is a memory intrinsic, unresolved call, or any non-load instruction	Fail when OnlyExact=true
Any underlying object or reader fails after earlier copies were collected	Discard all pending copies and fail
Every object and reader succeeds	Commit dependencies and return the deduplicated copy set
equivalentUse rejects a returned copy because offsets or thread visibility are incompatible	checkForAllUses fails; the caller cannot treat the store as forwarded

locationGraph is diagnostics-only. It may record a flow from the original store value to the already-returned load results after this algorithm succeeds, but it cannot provide underlying objects, ranges, accesses, reachability, copies, or an optimization decision.

Parameter traversal updates the finite NoCapture map and may record diagnostic flows after exact-copy forwarding succeeds. Allocation traversal cannot conclude local until that map reaches its fixed point. Neither traversal reads locationGraph.

Direct calls and NoCapture cache

When a tracked value is direct argument I of a call to a function defined in the current LLVM module, the analyzer queries a boolean map keyed by (callee, formal parameter I). Pointer parameters of analyzable definitions begin optimistically as true. A capturing or unsupported use changes the value to false; values never change back to true.

initialize:
    NoCapture[defined pointer parameter] <- true

repeat:
    changed <- false
    for each true NoCapture entry:
        if any use captures the parameter under current callee facts:
            entry <- false
            changed <- true
until changed is false

This is a finite optimistic fixed point, matching the role AANoCapture plays for LLVM heap-to-stack without reproducing the complete Attributor framework. Mutual recursion with no capturing sink remains true; if any member finds a capturing sink, later iterations propagate false to callers. With N entries, at most N boolean state changes are possible. No call-graph SCC, dereference level, or recursive parameter-summary composition is involved.

Function declarations and unresolved callees have no analyzable entry and are capturing in Phase 1. Current LLGo C and runtime declarations do not receive nocapture automatically, so deallocation calls remain capturing without a separate NoFree analysis. No allocation is analyzed for rewrite until the boolean map reaches its fixed point.

Diagnostic summary recording

locationGraph may separately record the flows needed to derive Go diagnostics:

• parameter flow to heap at level K records a heap leak;
• parameter flow to result N at level K records a result summary;
• mutator and callee flows are retained for diagnostic summaries;
• an unrepresentable result mapping or dereference level becomes unknown.

These facts are diagnostic data only. Heap-to-stack never reads locationGraph, never composes these summaries into an allocation walk, and never changes its decision when diagnostics are disabled. A function declaration has no NoCapture entry, so pointer-carrying arguments escape; this already covers ordinary C and runtime declarations. An indirect call or unresolved interface dispatch is also unknown in Phase 1.

Examples

A callee that only reads its pointer parameter has an empty leak summary:

declare ptr @malloc(i64)

define void @read(ptr %p) {
entry:
  %v = load i32, ptr %p
  ret void
}

define void @caller() {
entry:
  %p = call ptr @malloc(i64 4)
  store i32 42, ptr %p
  call void @read(ptr %p)
  ret void
}

The NoCapture entry for (@read, parameter 0) remains true because its only use is a load address. Walking %p in caller accepts the call after the boolean map reaches its fixed point, so the allocation remains local.

An exact local store/load copy stays in the same use worklist:

define void @caller_with_slot() {
entry:
  %p = call ptr @malloc(i64 4)
  %slot = alloca ptr
  store ptr %p, ptr %slot
  %q = load ptr, ptr %slot
  call void @read(ptr %q)
  ret void
}

When traversal reaches store ptr %p, ptr %slot, the OnlyExact query proves that %q is the complete load-copy set. The walker adds %q.uses() to its existing worklist and reaches call @read. If %slot has a non-exact alias, an unsupported reader, an unknown clobber, or escapes to another function, the exact-copy query fails and %p escapes.

A callee that stores the pointer into a global produces a heap fact:

@escaped = global ptr null
declare ptr @malloc(i64)

define void @save(ptr %p) {
entry:
  store ptr %p, ptr @escaped
  ret void
}

define void @caller() {
entry:
  %p = call ptr @malloc(i64 4)
  call void @save(ptr %p)
  ret void
}

Evaluating (@save, parameter 0) changes its NoCapture entry to false. The caller therefore rejects the call use and does not rewrite the allocation. locationGraph may separately retain the store-to-global path for diagnostics.

A result fact is diagnostic only for Phase 1 heap-to-stack:

declare ptr @malloc(i64)

define ptr @identity(ptr %p) {
entry:
  ret ptr %p
}

define i32 @caller() {
entry:
  %p = call ptr @malloc(i64 4)
  store i32 42, ptr %p
  %q = call ptr @identity(ptr %p)
  %v = load i32, ptr %q
  ret i32 %v
}

Returning %p makes NoCapture[identity, 0] false, so Phase 1 heap-to-stack does not rewrite this caller allocation. locationGraph records the parameter-to-result flow for diagnostics, but that result summary does not participate in optimization.

Recursion uses the finite NoCapture map, not summary composition or the uses visited map:

@escaped = global ptr null

define void @recursive(ptr %p) {
entry:
  call void @recursive(ptr %p)
  store ptr %p, ptr @escaped
  ret void
}

The entry starts as true. The global store changes it to false; the next map iteration observes false at the recursive call and reaches the same fixed point. No dereference-indexed recursive fact is created.

Dynamic calls

An indirect function call or unresolved interface dispatch is unknown in Phase 1:

• pointer-carrying arguments escape;
• a function-valued parameter records a callee effect;
• pointer-carrying results have unknown provenance;
• closure context reachable from an unresolved callee escapes.

A later sound possible-target analysis may join several summaries. Target discovery is separate from escape analysis and must remain conservative under reflection, C callbacks, and function pointers.

Imported summary transport

Per-package compilation requires caller-visible summaries to cross package boundaries. The minimum facts are function identity, Go parameter index, sink kind, result index when applicable, dereference level, and summary version.

internal/meta already owns LLGo package metadata and cache transport. The concrete encoding should be added only after the in-memory summary is tested. Missing, stale, or incompatible data must use the unknown-call rule.

In Phase 1, imported summaries are diagnostic transport only. They never create a NoCapture entry and are never read by allocation traversal or rewrite.

Phase 1 LLVM instruction rules

Every LLVM instruction that can use a pointer root must have an explicit operand-role rule. An unclassified instruction is an analyzer implementation error in tests and an unknown escape in production until classified.

Transparent pointer derivations

LLVM use	Phase 1 rule
getelementptr base	Follow the result with an appended bounded component path.
bitcast or pointer-preserving addrspacecast	Follow the result. Unsupported address-space lifetime changes are unknown.
phi incoming value	Follow the phi result. Visited state terminates cycles.
select pointer arm	Follow the select result.
freeze pointer operand	Follow the result.
extractvalue aggregate operand	Follow the selected component if metadata/layout maps it to the root. Otherwise unknown.
insertvalue inserted operand	Follow the resulting aggregate component.
insertvalue base aggregate	Follow preserved components; overwrite of the tracked component stops that path.
extractelement/insertelement/shufflevector with pointer elements	Track a constant bounded lane; dynamic or merged lanes become unknown.

Loads, stores, and atomics

LLVM use	Phase 1 rule
pointer used as load address	Safe for an allocation root. For a Go parameter root, a pointer-valued load may be followed at dereference level +1.
pointer stored as store value	A global, TLS, non-local, or unknown destination is a heap sink. Otherwise run the OnlyExact potential-copy query: follow every proven load result, and use heap/unknown if the proof is incomplete.
pointer used as store address	Safe for allocation identity; record mutator effect for a parameter root.
atomic load address	Same lifetime rule as load; ordering does not retain the address.
atomic store value	Apply the same destination-lifetime rule. A local copy is followed only when the exact-copy proof covers the atomic and thread-visibility constraints; otherwise use heap/unknown.
atomic store address	Mutator/address use.
cmpxchg address	Mutator/address use.
cmpxchg replacement value carrying root	A global, TLS, non-local, or unknown destination is a heap sink. A local replacement remains unknown in Phase 1 because the store-only exact-copy query does not prove its copies.
atomicrmw address	Mutator/address use; a pointer-valued operand is unknown unless the operation is explicitly modeled.
volatile memory access	Volatility alone does not retain an address, but it prevents removing/reordering required operations during rewrite.

Phase 1 follows a root through a local slot only when the exact-copy query proves the complete copy set. It does not construct general memory def-use chains, scan the CFG, or reason about partial and may-alias stores. Any non-exact access, unsupported reader, unknown clobber, or unresolved destination makes the root escape.

Returns and externally visible storage

LLVM use	Phase 1 rule
ret operand, allocation root	Returned, therefore not stack-rewritable.
ret operand, parameter root	Record result index/component and dereference level.
store into global, TLS, externally visible aggregate, or unknown memory	Heap sink.
global initializer	Not a function-local allocation candidate. Any referenced local root is invalid/unknown.

Calls and invokes

LLVM use	Phase 1 rule
direct call argument to a defined function	Accept only when the corresponding NoCapture map entry is true. Record diagnostic flow separately in locationGraph.
direct Go/runtime helper with semantic rule	Apply the LLGo semantic rule.
direct declaration without summary	Unknown/capturing argument.
indirect call argument	Unknown/capturing argument.
root used as indirect callee	Record callee effect and treat unknown closure context conservatively.
invoke	Same call rules; normal/unwind control edges do not change capture classification.
callbr	Unknown unless the complete target and operand contract is modeled.
inline assembly operand	Unknown unless a specific constraint is proven non-capturing and covered by tests.
LLVM lifetime/debug/assume intrinsic	Safe terminal use when the intrinsic contract does not capture the pointer.
unknown intrinsic	Unknown.

Phase 1 uses the internal NoCapture map only for defined functions. Bodyless C and runtime declarations remain capturing; a separate NoFree analysis is not part of this phase. Generic attributes still do not describe Go aggregate components or provide Go result leak levels.

Integer and pointer conversions

LLVM use	Phase 1 rule
ptrtoint	Unknown/escaping in Phase 1. Pointer identity and GC visibility are lost.
inttoptr derived from a tracked round trip	Unknown in Phase 1.
integer arithmetic on a pointer-derived integer	Unknown.
pointer comparison	Safe terminal observation.

A Phase 2 uintptr rule may preserve identity through a verified local round trip, but arithmetic, storage, calls, or untracked merges terminate it conservatively.

Memory intrinsics

LLVM use	Phase 1 rule
allocation pointer as memset destination	Safe mutating address use when size is within the allocation.
allocation pointer as memcpy/memmove destination	Safe address use for the allocation itself; copied pointer content needs typed semantics.
allocation pointer as copy source	Safe borrowed address use for allocation identity.
root stored inside bytes being copied	Unknown unless LLGo type metadata proves the pointer-containing fields and destination lifetime.
object size, lifetime, invariant, and debug intrinsics	Apply the documented LLVM intrinsic contract; otherwise unknown.

Control-only and exceptional instructions

Branches, switches, indirect-branch addresses, landing-pad values, resume, cleanup, and unreachable do not retain an unrelated pointer merely by controlling execution. If a root is itself an operand to an exceptional or control instruction not covered above, classify that operand explicitly; do not assume it is safe from opcode category alone.

Deallocation

LLGo GC allocations are not manually freed through ordinary Go code. A call that may free an allocation is not stack-rewritable unless the pass has a verified matched-allocation/deallocation contract. AllocRoot/FreeRoot remain excluded from Phase 1 heap-to-stack conversion.

Phase 2 Go semantic rules

Phase 2 replaces conservative call/instruction boundaries with verified LLGo semantics. Rules should be represented as transfer functions owned near the lowering/runtime contract, not scattered string comparisons inside the generic walker.

Channels and select

• The address passed to runtime.ChanSend is borrowed until the helper returns.
• Pointer-containing element content may be copied into channel-owned storage and therefore escapes.
• Buffered send copies into the channel buffer.
• Unbuffered send may queue the temporary address while blocked, but ChanSend does not return until the transfer no longer needs it.
• Receive copies element content into caller-provided storage.
• Select joins every possible send/receive state and preserves the same address-versus-content distinction.
• close, len, and cap do not retain the channel handle.

Maps

• MapAssign borrows key lookup data for the call but stores key/value content in map-owned storage.
• Map lookup borrows the map handle and may return/copy stored value content.
• Iterators retain the map according to their runtime lifetime and expose key/value content.
• delete and clear do not require a flow-sensitive strong deletion; retaining prior content facts is conservative.
• Proving a map handle local does not by itself authorize stack allocation of the runtime map representation.

Slices, arrays, strings, append, and copy

• A slice carries backing-storage identity independently from length/capacity scalars.
• Slice and slice-to-array-pointer operations preserve backing identity.
• append may reuse existing storage or allocate new storage; capacity information controls whether either case can be excluded.
• Appended pointer content flows into the result backing storage.
• copy, SliceCopy, Typedmemmove, memcpy, and memmove propagate Go pointer fields only with verified type/layout information.
• Untyped copies involving possible Go pointers remain unknown.
• String/byte/rune conversions must be classified from LLGo lowering as borrow, copy, allocation, or unknown.

Interfaces and type assertions

• Use the same ABI classification as ssa/interface.go to distinguish direct and indirect payloads.
• Direct pointer payloads preserve pointer identity.
• Indirect payloads are copied into an interface box, so pointer-bearing fields flow into that box.
• Interface-to-interface changes preserve payload facts.
• Concrete type assertions recover the modeled payload.
• Interface dispatch uses callee summaries only when all possible targets are soundly known.

Closures and method values

• Closure lowering must identify the environment allocation and captured components.
• A closure environment escapes when the closure value is returned, stored, passed to unknown code, or started as a goroutine.
• An immediately called known closure composes the closure body summary with captured values.
• Bound method values apply the same rule to the receiver.
• A bare function code pointer has no environment lifetime.

Goroutines

ssa/goroutine.go copies function and argument data into an AllocRoot startup record. The new goroutine may outlive the caller, so every current-frame allocation reachable from those values escapes even if the callee does not retain the parameter after startup. The startup root allocation itself is excluded from ordinary heap-to-stack conversion.

Defers, panic, and recover

• A normal defer retains arguments until the current function exits, which may still be frame-bounded.
• Conditional and loop defers must follow LLGo's actual save/drain representation.
• A deferred closure retains captured values to its execution point.
• A panic value may be recovered by an older frame and crosses the current frame lifetime.
• Recover results remain unknown unless a sound context relation is introduced.

External calls, C, and directives

• A bodyless declaration without a trusted contract remains unknown.
• //go:noescape establishes non-retention only for the declared parameter contract; it does not imply readonly memory or a result relationship.
• //go:uintptrescapes and implicit uintptr keepalive require explicit summary effects.
• LLVM nocapture, nofree, readonly, and memory-effect attributes may be consumed only according to their documented meanings.
• C ABI transformation may change parameter representation, which is why Go summaries should be computed before C ABI rewriting.
• Callbacks and function pointers require callee effects and conservative lifetime handling.

GC/runtime variants

The pointer lifetime proof is independent of BDWGC, TinyGo-derived GC support, or non-GC targets. The rewrite mechanism may differ by target/runtime, but no implementation may retain a pointer into a reclaimed stack frame. Semantic helper rules must be valid for every runtime implementation to which they are applied.

Heap-to-stack rewrite

Eligible allocations

Phase 1 initially recognizes direct LLGo allocation calls whose contracts are fully known:

• runtime.AllocZ(size) for zero-initialized GC allocation;
• runtime.AllocU(size) for uninitialized GC allocation, if all existing uses permit replacement.

AllocRoot and helpers with ownership, finalization, profiling, identity, or runtime registration semantics remain excluded until explicitly proven equivalent.

Rewrite requirements

A local candidate is rewritten only when:

• the allocation size is known and within LLGo's stack policy;
• required alignment is known and representable;
• the call is not in a loop/cyclic region whose alloca placement would merge identities or grow stack unboundedly;
• every transitive use is classified local at the fixed point;
• no use may free, publish, return, or retain the pointer;
• zero initialization for AllocZ is reproduced exactly;
• target address space and pointer representation permit an alloca replacement.

The transformer creates the alloca at a verified placement, reproduces initialization, replaces allocation-call uses, and deletes the call. The module is verified immediately after rewriting.

Loop allocations

An allocation instruction inside a loop represents a fresh object per dynamic execution. Hoisting one alloca to entry may merge identities; creating dynamic allocas in the loop may grow stack until function return. Phase 1 skips these candidates. A later optimization requires an explicit lifetime/placement proof.

Zero-sized allocations

LLGo has existing zero-sized allocation behavior. The pass must preserve permitted pointer-identity behavior and may not replace a shared/sentinel heap representation with a distinct stack address without verifying semantic equivalence.

Diagnostics reflect final lowering

Analysis locality is not enough to print that an object moved to stack. If size, alignment, loop, target, or ABI policy rejects the rewrite, diagnostics must report the final heap decision and reason.

Diagnostic path graph

The optimization solver needs only allocation use states and the boolean NoCapture map. A separate locationGraph may retain pointer-flow edges and one predecessor per diagnostic fact improvement:

allocation or Go parameter source
    -> LLVM instruction and operand role
    -> derived LLVM SSA value
    -> direct-call or Go semantic transfer
    -> result/heap/unknown sink

This explanation graph must satisfy:

• disabled unless detailed diagnostics are requested;
• no influence on traversal, the NoCapture fixed point, or rewrite decisions;
• deterministic tie-breaking by source position and LLVM instruction order;
• cycle detection and bounded output;
• source positions resolved through LLGo lowering metadata;
• deletion of all explanation state leaves results unchanged.

Concise reports are formatted from structured facts:

p does not escape
leaking param: p
leaking param content: p
leaking param: p to result ~r0 level=0
moved to heap: x

Exact wording and column compatibility are formatter work, not solver logic.

Failure and fallback behavior

Unknown real program behavior makes only the affected root escape. An unclassified LLVM opcode/operand role is a pass implementation gap and must fail focused exhaustive tests; production handling remains conservative until classification exists.

An internal inconsistency must not produce a partial optimistic result. Resource limits, missing metadata, unavailable imported summaries, unsupported address spaces, and failed rewrite preconditions all retain the heap allocation.

Imported summaries must be versioned with compiler/cache inputs before being reported. They do not affect Phase 1 heap-to-stack decisions; a callee without a local NoCapture entry remains capturing.

Module ownership

• A new internal escape-transform package owns LLVM use traversal, the NoCapture fixed point, diagnostic locationGraph, Go semantic transfer dispatch, rewrite planning, and structured results.
• internal/build invokes the transformer at the post-generation module boundary and owns ordering with llabi, cabi, verification, caching, and diagnostics collection.
• cl emits only the minimum source/Go semantic associations that cannot be recovered from LLVM IR. It does not perform escape analysis.
• ssa continues to lower Go operations and owns runtime helper contracts used by semantic rules. It does not own the analysis worklist.
• internal/meta transports stable imported summaries after the format is approved.
• cmd/internal/compile formats -m output from structured results.
• Generic LLVM passes remain independent consumers of the rewritten module.

The package API should remain unexported. The transform should accept the live module plus the minimum immutable LLGo facts it actually consumes.

Performance

The base cost is proportional to transitive LLVM use paths visited for each allocation and parameter root, plus boolean NoCapture fixed-point rescans. This repeats some instruction visits across roots but keeps the analysis local, conservative, and independently testable.

Optional statistics should include:

• allocation and parameter root count;
• visited LLVM uses per root;
• exact-copy queries, successful forwarded copies, and conservative rejection reasons;
• early allocation rejection reasons;
• NoCapture state changes and fixed-point rescans;
• unknown call, store, cast, intrinsic, and semantic-helper boundaries;
• bound-triggered fallbacks;
• successful rewrite count and rejected-local policy reasons;
• explanation nodes only when detailed diagnostics are enabled;
• total time and retained memory.

The pass runs when optimization or escape diagnostics consume its results. A diagnostics-only request must not enable unrelated LLVM optimization pipelines.

Testing strategy

LLVM traversal tests

Construct focused LLVM modules and test:

• load and store-address safe uses;
• pointer stored as value with a successful exact local copy;
• exact-copy rejection for global, non-local, aliased, clobbered, and unsupported readers;
• GEP, cast, phi, select, aggregate, and vector propagation;
• pointer/int conversions;
• atomic and volatile uses;
• direct, indirect, invoke, intrinsic, and inline-assembly calls;
• return and global sinks;
• cycles and resource bounds;
• every supported LLVM opcode/operand role;
• deterministic explanation paths.

Summary tests

• direct heap and result summary composition;
• dereference levels 0, 1, and saturation;
• mutator and callee facts;
• a callee NoCapture entry changing after its caller was first analyzed;
• direct and mutual recursion with and without a real sink;
• imported, missing, stale, dynamic, and external summaries;
• mapping LLVM aggregate parameters/results back to Go indices.

Rewrite tests

• AllocZ becomes an alloca plus equivalent zero initialization;
• AllocU becomes an uninitialized alloca;
• escaping allocation calls remain;
• size, alignment, loop, zero-size, address-space, and target rejection;
• LLVM verifier success after rewrite;
• compatibility with LowerLargeAggregates and all C ABI modes;
• compatibility with debug metadata and later default LLVM passes.

Go semantic tests

Each semantic rule needs a local and an escaping neighbor:

• channel temporary transport address versus sent pointer content;
• map handle versus stored key/value content;
• direct versus boxed interface payload;
• immediately called versus returned closure;
• slice alias/reallocation and typed copy;
• goroutine startup lifetime;
• frame-bounded defer and cross-frame panic;
• noescape, uintptr, C, and callback contracts.

Differential -m tests

Compare structured facts with focused go tool compile -m cases:

allocation: local / returned / heap
parameter -> heap at level N
parameter -> result R at level N
parameter -> mutator at level N
parameter -> callee at level N

Go output is an oracle for Go language semantics, not proof that an LLGo runtime helper has the same implementation contract.

During development, run focused package/pass tests and the exact GOROOT errorcheck cases affected by each change. Broader suites belong at integration milestones.

Staged implementation

Phase 1A: post-generation LLVM analyzer

• Add the internal module transformer and invoke it after cl emits the complete module.
• Recognize eligible AllocZ/AllocU calls and Go parameter roots.
• Implement LLVM use traversal, operand-role classification, OnlyExact copy forwarding, visited state, bounds, and structured results.
• Do not rewrite yet.

Phase 1B: NoCapture and parameter summaries

• Compute the boolean per-function-parameter NoCapture map to a finite fixed point for direct-call heap-to-stack decisions.
• Record heap, result, mutator, and callee flows in locationGraph for summaries without feeding them back into optimization.
• Add minimal lowering/source associations needed for -m.
• Keep dynamic, imported-without-summary, and external calls conservative.

Phase 1C: heap-to-stack rewrite

• Plan and apply AllocZ/AllocU to alloca rewrites.
• Preserve size, alignment, initialization, loop, zero-size, target, and address-space constraints.
• Verify the module after rewriting.
• Test ordering with large-aggregate and C ABI transforms.

Phase 1D: diagnostics and imported summaries

• Format concise -m output from structured facts.
• Add optional explanation predecessors.
• Add versioned package summary transport through the existing metadata/cache boundary.

Phase 2: Go semantics

Land each family independently:

1. typed memory operations and basic slice aliases;
2. closures and immediately called function values;
3. interfaces and assertions;
4. append/copy and string conversions;
5. channels and select;
6. maps and iterators;
7. frame-bounded defers and panic/recover;
8. external summaries, //go:noescape, and uintptr contracts;
9. sound dynamic-call target sets;

Each change removes one named conservative boundary and includes a nearby retaining case that must still escape.

Alternatives considered

Port Go's escape analysis

Rejected because the implementation is centered on cmd/compile AST/compiler IR and is tightly coupled to Go frontend concepts. Porting it would be large, difficult to validate, and costly to maintain.

Use LLVM AAHeapToStack alone

Rejected as the complete solution because it cannot produce LLGo's required parameter leak summaries and cannot apply Go/runtime-specific semantics. It may remain a later generic optimization for allocation opportunities outside the LLGo pass's modeled source/runtime contracts.

Analyze x/tools go/ssa

Rejected as the final analysis layer. It would make the escape result depend on a pre-lowering representation and then require a separate mapping to the complete LLVM module for transformation. LLGo already needs an LLVM rewrite pass; analyzing the final module keeps the proof and rewrite on the same SSA values while semantic metadata supplies only facts LLVM cannot express.

Parse LLVM diagnostics or debug logs

Rejected because pass text is not a stable API, failed conversions carry no complete explanation, and the required Go summaries do not exist in the output.

Implement the pass in xgo-dev/llvm

Rejected initially. The logic is LLGo-specific and can be implemented as an ordinary Go module transformer using the existing LLVM bindings, following internal/cabi. Binding changes are justified only if a concrete required LLVM API is missing.

Open questions

• What is the minimal lowering side table/metadata needed to map LLVM parameters, results, allocations, and semantic helpers back to Go concepts?
• Should the pass run strictly before LowerLargeAggregates, or are any allocation shapes introduced later that require a second narrow scan?
• Which allocation helpers beyond AllocZ and AllocU have contracts safe for Phase 1 rewriting?
• What component/dereference/use-state limits fit LLGo's largest current packages?
• Which summary facts must be transported in the first cross-package release?
• How should generic instantiations and wrappers be identified in summaries?
• Which LLVM attributes are sufficient to consume external noescape facts without misrepresenting Go aggregates?
• Can any loop allocation be rewritten without identity merging or unbounded stack growth?
• What narrow pass boundary should expose LLVM's OnlyExact potential-copy query to LLGo without enabling all of Attributor?
• Should LLGo still enable AAHeapToStack after its own pass to recover generic IR-level opportunities?

Acceptance criteria

Phase 1 is complete when:

• the analyzer runs on the complete cl-generated LLVM module at the post-generation transform boundary;
• every relevant LLVM opcode and operand role has a focused tested classification;
• exact local copies remain in the use worklist, while every incomplete exact-copy proof remains conservative;
• unknown uses and failed rewrite preconditions retain heap allocation;
• direct and recursive calls reach stable heap/result summaries;
• summaries distinguish direct leaks, content leaks, result indices, and dereference levels;
• proven-local eligible allocation calls are rewritten to equivalent allocas;
• module verification and later large-aggregate/C ABI/default LLVM transforms succeed;
• detailed explanation recording can be disabled without changing any result;
• focused differential tests document every remaining conservative Go-semantic mismatch.

Phase 2 is incremental. A semantic family is complete only when its previous unknown boundary is removed, its LLGo lowering/runtime contract is tested, and a nearby escaping case remains conservative.

[MeteorsLiu]

Research note: Go 1.26.5 escape analysis, from frontend IR to parameter tags

This note describes the implementation shipped in Go 1.26.5. It separates mechanisms that are often discussed as if they were one algorithm:

1. call-graph SCC scheduling;
2. frontend-IR traversal and location-graph construction;
3. weighted graph solving and lifetime policy;
4. parameter-summary encoding and call-site composition;
5. escape decisions, diagnostics, and later Go-specific optimizations.

The central point is that Go's location graph is the actual escape-analysis IR and solver input. It is not merely an explanation graph. SCCs schedule interprocedural batches; they do not solve pointer flow. Parameter tags transport selected graph results to later batches and importing packages.

The LLGo proposal deliberately uses a different optimizer: sparse LLVM def-use traversal plus a finite NoCapture map. LLGo may borrow Go's summary vocabulary and explanation ideas without making the diagnostic graph part of heap-to-stack decisions.

1. Source map

Source	Role
cmd/compile/internal/ir/scc.go	Tarjan-style bottom-up function batching
escape/escape.go	batch lifecycle, closure capture decision, final escape state, parameter tags
escape/graph.go	location, edge, hole, special sinks, graph construction primitives
escape/stmt.go	statement-specific transfer rules and loop depth
escape/assign.go	destination holes, indirect mutation, assignments
escape/expr.go	expression-specific transfer rules and storage-producing expressions
escape/call.go	static/mutual/imported calls, builtins, go/defer, uintptr directives
escape/solve.go	weighted graph walk, attributes, lifetime checks, explanation predecessor
escape/leaks.go	compact heap/result/mutator/callee summary representation
escape/alias.go	Go 1.26 FreeGC slice-alias analysis, separate from the core location solver

2. End-to-end pipeline

Funcs(all functions)
    -> VisitFuncsBottomUp(static call graph)
    -> for each bottom-up SCC batch:
         Batch(functions)
           -> initFunc: create locations for names/parameters/results
           -> walkFunc: translate Go compiler IR to weighted edges
           -> flowClosure: decide capture-by-value/reference and add closure edges
           -> HeapAllocReason: add forced-heap edges
           -> walkAll: solve locations and parameter flows
           -> finish:
                encode parameter tags
                set EscHeap/EscNone/EscNever
                print -m diagnostics
                apply zero-copy/transient consequences
           -> optional Go 1.26 FreeGC alias analysis

There are two interprocedural modes at a static call:

• if the callee is in the same not-yet-tagged batch, connect caller actuals directly to callee formal/result locations in the shared graph;
• if the callee was already analyzed, parse its compact parameter tags and recreate only the summarized flows in the caller graph.

3. SCC scheduling: why it exists and what it does not do

ir.VisitFuncsBottomUp computes minimal strongly connected components of the static call graph in reverse topological order. A callback receives a batch only after all statically visible callees outside that batch were already delivered to earlier callbacks.

The implementation is a Tarjan adaptation with two notable rules:

1. A closure cannot become its own component root. It is forced into the same component as its outer function, which lets capture and result relationships be analyzed in one graph.
2. Each function is represented by two virtual visit numbers. This distinguishes a non-recursive singleton plus closures from a self-recursive component.

Conceptually:

VisitFuncsBottomUp(functions):
    nodeID = map[function]visitNumber
    stack  = []

    for each non-closure function not visited:
        visit(function)

visit(fn):
    assign fn two virtual visit numbers
    push fn
    min = search-number

    walk fn's frontend IR for static function, method, and closure references:
        min = min(min, visit(referenced function))

    if fn is a non-closure SCC root:
        pop minimal component
        analyze(component, recursive flag)

    return min

The SCC graph is a scheduling graph only. It does not contain local variables, allocations, dereference weights, heap sinks, or lifetime facts.

3.1 Acyclic calls

func leaf(p *int) int { return *p }
func caller(p *int) int { return leaf(p) }

leaf is analyzed first and tagged. When caller is analyzed, the call reads leaf's tag. The location graphs are separate.

3.2 Mutual recursion

func a(p *int) { b(p) }
func b(p *int) { a(p) }

a and b share one batch and one location graph. tagHole detects inMutualBatch and returns the actual formal-parameter location rather than reading a tag that does not exist yet. The calls add zero-dereference flow in both directions.

If neither function has a heap sink, both parameters have no heap leak. If either function adds global = p, the shared graph gives both parameters a path to the heap during the same solve.

4. Graph data model

4.1 batch

One batch owns:

allLocs       every ordinary location in the batch
closures      closures waiting for capture-by-value/reference decision
heapLoc       special sink: escapes + persists + mutates + calls
mutatorLoc    special sink: indirectly mutates reachable memory
calleeLoc     special sink: may invoke a reachable closure
blankLoc      discard sink; no edge is retained

Go 1.26 also keeps a lazily populated ReassignOracle cache. That supports literal rewriting before HeapAllocReason; it is not the location-graph solver.

4.2 location

A location represents one abstract Go storage location or allocating expression. Important fields are:

n             represented frontend IR node, if any
curfn         owning function
edges         incoming assignment edges
loopDepth     declaration/allocation loop depth
resultIndex   one-based result parameter index
attrs         Escapes | Persists | Mutates | Calls
paramEsc      compact parameter leak set
derefs        best distance during one root walk
walkgen       generation that owns derefs/predecessor
dst/edgeIndex predecessor selected for explanation
param         ordinary input parameter marker
paramOut      result parameter marker
captured/reassigned/addrtaken closure-capture inputs

The analysis is intentionally insensitive to many fields and paths. For example:

var x struct{ f, g *int }
var u []*int
x.f = u[0]

is approximated as:

x <- *u

It does not create independent locations for x.f, x.g, or each slice element, but it retains the implicit slice dereference.

4.3 edge

Edges are stored on their destination:

edge {
    src     source location
    derefs  number of dereferences minus address operations
    notes   optional source explanation chain
}

An edge means:

destination <- operation(source)

Examples:

p = q       p <- q       weight  0
p = *q      p <- q       weight +1
p = **q     p <- q       weight +2
p = &q      p <- q       weight -1

Weights cannot be less than -1 because Go cannot take the address of a non-addressable address expression.

4.4 hole

A hole is a destination context used while recursively evaluating an expression:

hole {
    dst       destination location
    derefs    current edge weight
    notes     source explanation chain
    addrtaken whether this evaluation takes the source address
}

For an assignment dst = expr, the walker first constructs a hole for dst, then evaluates expr into it.

hole.addr(...)   derefs -= 1
hole.deref(...)  derefs += 1
hole.note(...)   preserves source-level reason

For example, when evaluating x = **p, the destination hole begins as (x, 0), two dereference operations produce (x, +2), and flow adds x <- p with weight 2.

4.5 flow

flow(hole k, location src):
    if k takes the address:
        src.addrtaken = true

    if destination is blank:
        return

    if dst == src and derefs >= 0:
        return

    if dst already escapes and derefs < 0:
        mark src Escapes|Persists|Mutates|Calls immediately
        retain explanation when requested
        return

    dst.edges.append(src, derefs, notes)

The immediate escaping-address case is an optimization and diagnostic shortcut for facts such as {heap} <- &x.

4.6 spill

Storage-producing expressions use spill:

spill(destinationHole, expression):
    storage = new location for expression
    flow(destinationHole.addr, storage)
    return hole(storage)

For p = new(int) this creates a storage location for new(int) and adds:

p <- &storage(new(int))    weight -1

The returned storage hole lets composite elements or captured values flow into the allocated object.

4.7 teeHole and later

teeHole combines multiple non-negative destination contexts through a temporary location. It is used when one argument must flow to several sinks, for example a result plus mutator or heap-content sink.

later creates a persistent temporary between a source and destination. A top-level defer uses it to keep arguments live until deferred execution without automatically sending them to the heap.

5. Constructing the graph from Go compiler IR

Graph construction is where Go language semantics enter. The solver is generic over locations and weights; stmt.go, assign.go, expr.go, and call.go decide which holes represent each construct.

5.1 Function initialization

initFunc creates locations for declared names, hidden parameters, and closure variables. Result parameter locations get result indices 1..N, later converted to zero-based summary result slots.

All ordinary declared locations begin with attrPersists: their storage lasts beyond one expression evaluation. Allocating expression locations created by spill begin non-persistent and gain persistence/escape only through graph solving.

5.2 Loop depth

Function analysis begins at loop depth 1. Entering a for, range, or backward-goto label increases depth. A declaration records the active depth.

This is not CFG liveness. It is a lifetime approximation used by outlives: a location declared outside a loop may retain the address of a fresh object created inside the loop across iterations.

5.3 Assignment destinations

addr(dst) returns the correct destination hole:

Destination	Hole/side effect
local name	that name's location
global name	heap hole
struct field	containing object's hole
array element	containing array hole
slice element	mutator flow from slice
*p or p.f through pointer	mutator flow from pointer
map index	key to heap; map/value handled by map assignment semantics

assignList builds destination holes, evaluates every source including side effects, filters proven self-assignment, and records reassignment state for closure capture decisions.

5.4 Selected expression rules

Expression	Graph rule
name	flow name location into current hole
&x	evaluate x into hole.addr
*p	evaluate p into hole.deref
pointer field	dereference receiver before flowing
array index	preserve array location
slice index	add one implicit dereference from slice
slice expression	preserve backing-pointer flow from source slice
slice-to-array value	add dereference
slice-to-array pointer	preserve pointer flow
new, make-slice, map allocation, slice literal, closure, method value	create storage with spill as appropriate
interface conversion of indirect value	spill interface box, then flow payload into it
direct interface payload	preserve payload flow
unsafe pointer/uintptr conversion	special unsafeValue or heap rule under checkptr/ASan
map literal key/value	both content values flow to heap-owned storage
string/byte/rune allocating conversion	spill result storage; source content usually discarded/copied according to rule

5.5 Selected statement and builtin rules

Construct	Rule
ch <- value	sent value flows to heap
receive	channel handle is discarded; received result flows through assignment destinations
panic(value)	value flows to heap
copy(dst, src)	dst flows to mutator; pointer-bearing src content flows to heap at one dereference
append(dst, elems...)	dst flows to result and mutator; pointer content may flow to heap; Go 1.26 models possible new backing storage separately
map assignment/literal	key/value content flows to heap
clear	operand flows to mutator
len/cap/close/print	relevant operands are evaluated/discarded without pointer retention
unsafe slice/string/data operations	base pointer flows to result; scalar length/capacity is discarded

These are frontend-IR rules, not conclusions derived later from SSA calls.

6. Calls and interprocedural composition

6.1 Static callee discovery

For direct function calls, Go attempts to recover a static callee name. Interface calls and unresolved function values remain dynamic. The known function type supplies receiver/parameter identities.

6.2 Same mutual batch

If the static callee has started but is not yet tagged:

• each actual argument flows directly into the callee formal parameter location;
• if call results have caller destinations, each callee result location flows directly into the corresponding caller hole.

This creates one graph across recursive functions.

6.3 Previously tagged callee

tagHole parses the formal parameter's encoded leaks and creates one destination hole per fact:

if heap level K exists:     heapHole.shift(K)
if mutator level K exists:  mutatorHole.shift(K)
if callee level K exists:   calleeHole.shift(K)
if result i level K exists: callerResultHole[i].shift(K)

return teeHole(all destinations)

The caller argument is evaluated once into this combined hole. Thus a summary is not a prose annotation; it reconstructs caller-side graph edges.

6.4 Dynamic calls

If the callee is unknown, tagHole returns the heap hole for arguments. If call results flow somewhere and the function value itself is unknown, the function value flows to the callee sink so reachable closures are marked as potentially invoked with untracked results.

6.5 Compiler-inserted KeepAlive

Go 1.26 treats compiler VarLive/KeepAlive call arguments as discarded for escape analysis. The operation extends liveness but does not publish the pointer.

6.6 Bodyless declarations

Bodyless functions are tagged without graph analysis:

• scalar parameters need no pointer tag;
• pointer-bearing parameters default to heap leak level 0;
• //go:noescape removes the heap leak but adds mutator and callee level 0, because noescape does not mean readonly and does not mean a reachable closure cannot be called;
• bodyless uintptr parameters cause the function to receive UintptrKeepAlive behavior;
• //go:uintptrescapes causes pointer-to-uintptr arguments to flow to heap and/or be retained according to the pragma rewrite.

7. Weighted graph solving

7.1 Why walks run backward

Edges are stored on destinations, so the solver starts at a root such as heap or result and follows incoming edges backward toward sources. This directly asks:

Which source locations can reach this root, and with how many dereferences?

7.2 walkAll

walkAll initially queues every ordinary location plus mutator, callee, and heap. A location is requeued when it gains a new attribute. Escape and persistence each transition at most once, so the outer fixed point is finite.

Go 1.26 uses a deque and favors escaping roots at the front to propagate heap facts sooner. This changes work ordering, not semantics.

walkAll:
    queue = all locations + mutator + callee + heap
    walkGeneration = 0

    while queue not empty:
        root = pop front
        root.queued = false
        walkGeneration++
        walkOne(root, walkGeneration, enqueueChangedRoot)

7.3 walkOne

One root walk computes the minimum dereference distance from every reachable source to that root.

walkOne(root, generation):
    root.distance = 0
    root.predecessor = none
    worklist = [root]

    while worklist not empty:
        loc = pop front
        d = loc.distance
        newAttrs = none

        if d < 0:
            # &loc reaches root. Do not let the address operation
            # incorrectly propagate to values stored inside loc.
            d = 0

            if outlives(root, loc):
                newAttrs += Escapes | Persists | Mutates | Calls
            else if root has Persists:
                newAttrs += Persists

        if d == 0:
            newAttrs += root.(Mutates | Calls)

        if loc is an input parameter:
            if outlives(root, loc):
                record minimum heap/result leak distance d
            if root has Mutates:
                record mutator distance d
            if root has Calls:
                record callee distance d

        if newAttrs adds bits to loc:
            loc.attrs |= newAttrs
            enqueue loc as a future root
            if loc now Escapes:
                continue

        for incoming edge src -> loc with weight w:
            candidate = d + w
            if src was not reached in this generation
               or candidate < src.distance:
                src.distance = candidate
                src.predecessor = this edge
                queue src if not already queued in this generation

The source calls this Bellman-Ford because address operations introduce negative edges and distances may improve after a location is first discovered.

7.4 Why negative cycles terminate

When a negative distance is popped, the solver interprets it as "the address of this location reaches the root" and clamps the distance to zero before following the location's incoming edges. Therefore an address edge cannot repeatedly reduce distance around a cycle without bound.

The clamp also has semantic meaning. In:

root <- &l
l    <- x

the address of l reaches root; that does not imply the address of value source x reaches root.

7.5 outlives

outlives(root, other) is lifetime policy, not graph reachability:

1. a root already marked escaping outlives everything;
2. mutator and callee pseudo-locations do not outlive ordinary storage;
3. a result parameter is assumed to outlive the callee;
4. exception: a closure result does not force an outer-function location to heap while all closure call sites remain statically known;
5. within one function, a location declared at shallower loop depth outlives storage created at deeper loop depth;
6. a location in an outer function outlives storage created in a nested closure.

The graph answers whether an address reaches a root. outlives answers whether that reachability violates stack lifetime.

7.6 Explanation paths

Whenever a shorter path is found, the solver stores the destination and edge index as predecessor state. explainPath follows those predecessors from source to root, emits edge weights and source notes, and stops on cycles. These predecessors explain the solver's chosen minimum path; unlike LLGo's proposed diagnostic-only graph, Go's explanation path is attached to the same graph that decided escape.

8. Parameter summaries

8.1 Layout

Go uses eight bytes:

Byte	Fact
0	minimum dereference level to heap
1	minimum dereference level to mutator
2	minimum dereference level to callee
3	minimum dereference level to result 0
4	minimum dereference level to result 1
5	minimum dereference level to result 2
6	minimum dereference level to result 3
7	minimum dereference level to result 4

Internally a byte stores derefs + 1:

0     means absent and decodes to -1
1     means level 0
2     means level 1
...
255   is the saturated maximum

Only the first five results fit. A flow to a later result is conservatively recorded as a heap leak.

8.2 Minimum and dominance

Adding a fact keeps the minimum dereference level. Before encoding, Optimize removes every result/mutator/callee path whose distance is greater than or equal to an existing heap distance. Such a path cannot improve any caller decision because the same or less-indirect value already reaches heap.

8.3 Encoding

• Heap level 0 encodes as an empty string for export-data compactness.
• Any string without the esc: prefix parses as heap level 0, preserving the conservative default for missing/old tags.
• Other summaries encode as esc: followed by the non-trailing-zero bytes.
• An unused pointer parameter encodes a real empty fact set (esc:), which differs from the missing-tag conservative default.

8.4 Diagnostic formatting

Without escapemutationscalls, Go reports heap/result facts:

p does not escape
leaking param: p
leaking param content: pp
leaking param: p to result ~r0 level=0

With -d=escapemutationscalls=1, it also reports:

mutates param: pp derefs=0
calls param: f derefs=0

9. Worked examples verified with Go 1.26.5

The outputs below were checked with the Go 1.26.5 compiler using compile -m=2 -l; mutator/callee examples also used -d=escapemutationscalls=1.

9.1 Parameter to result

func identity(p *int) *int {
    return p
}

Graph construction:

result0 <- p    weight 0

Solve from result0:

distance[result0] = 0
edge reaches p with distance 0
result0 outlives input parameter p
p.paramEsc.Result(0) = 0

Finish prints:

parameter p leaks to ~r0 with derefs=0
flow: ~r0 <- p
leaking param: p to result ~r0 level=0

At a later caller, tagHole routes the actual argument to the caller's destination for result 0. It does not automatically route the argument to heap.

9.2 Parameter value directly to heap

var global *int

func save(p *int) {
    global = p
}

The global assignment destination is the heap hole:

heap <- p    weight 0

The heap root reaches p at distance 0, so:

p.paramEsc.Heap = 0
leaking param: p

A caller passing &x applies heap level 0 to the actual argument. Evaluating &x shifts the heap hole by -1, giving heap <- &x; x must move to heap.

9.3 Parameter content to heap

var global *int

func saveContent(pp **int) {
    global = *pp
}

Expression traversal dereferences pp once:

heap <- *pp    weight +1

The heap root reaches pp at distance 1. Go records:

parameter pp leaks to {heap} with derefs=1
flow: {heap} <- *pp
leaking param content: pp

The pointer value pp itself is not stored. Pointer content reachable through it is.

9.4 Read-only parameter and a local address

func read(p *int) int { return *p }

func localRead() int {
    x := 1
    return read(&x)
}

read's result is an integer, so *p carries no pointer into any result or heap hole. Its parameter summary has no heap/result flow and Go reports:

p does not escape

At localRead, applying the empty summary does not connect &x to heap. Taking the address still marks x.addrtaken, but no outliving root is reachable, so x remains stack allocated.

This distinction matters: "address taken" is graph-construction information; "escapes" is a solved lifetime result.

9.5 Loop depth forces fresh storage to heap

func loopReuse(n int) {
    var p *int
    for i := 0; i < n; i++ {
        p = new(int)
    }
    _ = p
}

Locations:

p                 loopDepth 1, persistent
storage(new(int)) loopDepth 2

Edge:

p <- &storage(new(int))    weight -1

Walking from root p reaches the new storage with negative distance. outlives(p, storage) is true because 1 < 2: p can retain one iteration's pointer into a later iteration, while a single reused stack slot would merge logically distinct allocations.

Go prints:

new(int) escapes to heap
flow: p <- &{storage for new(int)}

This is loop lifetime policy, not CFG liveness and not SCC processing.

9.6 Recursive batch without and with a sink

func recursiveA(p *int) { recursiveB(p) }
func recursiveB(p *int) { recursiveA(p) }

Both functions are in one SCC batch. Actual/formal zero-weight edges form a cycle, but no heap root reaches either parameter. Go reports both parameters do not escape.

Now add a sink:

func recursiveSinkA(p *int) { recursiveSinkB(p) }

func recursiveSinkB(p *int) {
    recursiveSinkA(p)
    global = p
}

The global store adds heap <- recursiveSinkB.p. Backward solving crosses the call-parameter edges and reaches recursiveSinkA.p too. Go reports leaking param: p for both.

SCC batching made the shared graph available. The weighted solver propagated the heap fact.

9.7 Immediately called versus returned closure

func immediateClosure() int {
    x := 1
    p := func() *int { return &x }()
    return *p
}

The closure captures x by reference, but its result call site is statically known and the closure itself does not escape. The outlives result-parameter exception for contained closures prevents the closure result location from forcing outer x to heap. Go reports:

immediateClosure capturing by ref: x
func literal does not escape

Now return the closure:

func returnedClosure() func() *int {
    x := 1
    return func() *int { return &x }
}

Graph paths include:

result0 <- &closureStorage
closureStorage <- &x

The returned closure storage escapes, and its capture edge makes x escape. Go prints:

func literal escapes to heap
moved to heap: x

9.8 Goroutine versus top-level defer

func goRead(p *int) {
    go read(p)
}

The frontend has already built a zero-argument wrapper closure that captures p. goDeferStmt evaluates a go wrapper into the heap hole. The wrapper storage escapes, so captured p leaks to it and then to heap:

func literal escapes to heap
leaking param: p

For a top-level defer:

func deferRead(p *int) {
    defer read(p)
}

At loop depth 1 with no special DeferAt, Go uses later(discardHole) rather than heap. The wrapper/arguments persist until function exit but do not outlive the frame. Go reports:

p does not escape

This is why Persists and Escapes are separate attributes.

9.9 Mutator and callee facts

func mutate(pp **int) {
    *pp = nil
}

The indirect assignment destination calls mutate(pp), which evaluates pp into the mutator hole at distance 0. With extra diagnostics:

mutates param: pp derefs=0

For a closure/function parameter whose result matters:

func callResult(f func() *int) *int {
    return f()
}

The callee is dynamic and its result flows to the function result. Go evaluates f into the callee hole and reports:

calls param: f derefs=0

A call with no used results may not need the callee fact because losing its result cannot affect caller pointer flow. This is a summary/optimization fact, not a statement that the machine call did not occur.

9.10 Bodyless declaration and //go:noescape

For an ordinary bodyless declaration:

func external(p *int)

Go cannot analyze a body, so paramTag records heap level 0. The empty export tag is intentionally interpreted as that conservative leak.

With:

//go:noescape
func external(p *int)

the heap leak is removed, but mutator and callee level 0 are recorded. //go:noescape promises that the pointer value is not retained beyond the call; it does not promise that reachable memory is readonly or that a reachable closure cannot be invoked.

Bodyless uintptr parameters additionally participate in keepalive behavior because converted pointers must remain live across syscall-like calls even when the integer value itself has no Go pointer type.

10. Go 1.26.5 additions that are not the core solver

Go 1.26.5 contains several newer mechanisms. They must not be mistaken for changes to the fundamental weighted location solver.

10.1 ReassignOracle and literal allocation rewriting

Before applying HeapAllocReason, the batch may prove that selected non-literal allocation sizes, notably make-slice length/capacity expressions, have a static literal value. This can allow an otherwise-local allocation to satisfy stack-size policy. The rewrite preserves side effects through temporary assignments.

This changes the frontend IR/policy input; it is not a new graph-solving algorithm.

10.2 Append backing-store location

OAPPEND now creates a spill location representing a possible newly allocated backing store and flows its address to the append result. Its loop depth is set to 0 because runtime reuse/selection is guarded separately. Consumers can use the append node's escape result when choosing backing-store allocation.

10.3 Compiler KeepAlive special case

Compiler-inserted VarLive/KeepAlive arguments are evaluated into the discard hole so liveness extension is not confused with retention.

10.4 internal/abi.EscapeNonString

The call walker recognizes this compiler/runtime contract for generic hashing/cloning cases. Non-string pointer content is forced to heap when required; pure string content can be discarded because hashing/cloning depends on content rather than a movable stack address.

10.5 FreeGC slice alias analysis

When the RuntimeFreegc experiment is enabled, alias.go runs a separate conservative frontend walk after core escape finishing. It proves selected append operations use an unaliased slice so later code can safely free backing arrays. It has its own candidate-slice and loop state. It neither replaces nor feeds the location-graph solver described above.

11. What LLGo should and should not copy

Reusable concepts

• Keep scheduling, pointer-flow solving, lifetime policy, summary transport, and diagnostics as distinct mechanisms.
• Represent summary facts structurally before formatting text.
• Distinguish parameter value leak from parameter-content leak by dereference level.
• Keep result, mutator, and callee facts instead of collapsing everything to heap.
• Apply imported/callee summaries by reconstructing caller-side flows, not by parsing diagnostic text.
• Retain deterministic predecessor paths only for explanation.
• Treat absent or stale summaries conservatively.

Concepts not adopted by LLGo's optimizer

• LLGo does not port Go frontend IR or its location graph as the heap-to-stack solver.
• LLGo does not need Go's SCC batching for the current boolean local-module NoCapture fixed point.
• LLGo does not use Go loop depth as the generic LLVM use walker; it independently rejects allocation blocks in CFG cycles.
• LLGo does not infer runtime-helper semantics merely because Go has a transfer rule for the source-language construct.
• LLGo's diagnostic locationGraph never feeds optimization.

12. References

• Go 1.26.5 SCC scheduling: https://github.com/golang/go/blob/go1.26.5/src/cmd/compile/internal/ir/scc.go
• Go 1.26.5 batch pipeline and parameter tags: https://github.com/golang/go/blob/go1.26.5/src/cmd/compile/internal/escape/escape.go
• Go 1.26.5 locations, holes, and edges: https://github.com/golang/go/blob/go1.26.5/src/cmd/compile/internal/escape/graph.go
• Go 1.26.5 weighted solver and outlives: https://github.com/golang/go/blob/go1.26.5/src/cmd/compile/internal/escape/solve.go
• Go 1.26.5 call-site tag composition: https://github.com/golang/go/blob/go1.26.5/src/cmd/compile/internal/escape/call.go
• Go 1.26.5 leak encoding: https://github.com/golang/go/blob/go1.26.5/src/cmd/compile/internal/escape/leaks.go
• Go 1.26.5 expression transfers: https://github.com/golang/go/blob/go1.26.5/src/cmd/compile/internal/escape/expr.go
• Go 1.26.5 statement transfers: https://github.com/golang/go/blob/go1.26.5/src/cmd/compile/internal/escape/stmt.go
• Go 1.26.5 FreeGC alias analysis: https://github.com/golang/go/blob/go1.26.5/src/cmd/compile/internal/escape/alias.go

[MeteorsLiu]

Research note: LLVM AAHeapToStack and its supporting analyses

This note describes LLVM 19.1.7. AAHeapToStack is not a general escape-summary algorithm. It is an Attributor abstract attribute that recognizes removable allocation calls, asks other abstract attributes for facts such as AANoCapture and AANoFree, proves one allocation convertible, and manifests an alloca rewrite.

It is clearer to separate three mechanisms: AANoCapture, the heap-to-stack decision, and the final rewrite.

1. AANoCapture: optimistic pointer-use classification

AANoCapture tracks three components: capture through memory, through integer/address information, and through return. Attributor starts from optimistic assumed bits, records dependencies between attributes, and repeatedly updates them to a fixed point.

initialize NoCapture(value) optimistically

update NoCapture(value):
    state = {notCapturedInMemory, notCapturedInInteger, notCapturedInReturn}
    worklist = uses(value)
    visited = {}

    while worklist not empty:
        use = pop(worklist)
        if use is dead or droppable:
            continue

        kind = DetermineUseCaptureKind(use)
        if kind == NO_CAPTURE:
            continue
        if kind == PASSTHROUGH:
            push uses(resultOf(use))
            continue

        if use returns the pointer from the analyzed function:
            clear notCapturedInReturn
        else if use is ptrtoint or stores the pointer as a value:
            clear all three components conservatively
        else if use passes it as call argument i:
            depend on NoCapture(callee, i)
            keep the bits only while the callee fact remains true
        else:
            clear all applicable bits conservatively

    intersect the attribute state with the newly computed bits
    let Attributor reschedule dependents until no state changes

Pass-through uses include GEP, bitcast, phi, select, and address-space cast. Loads and address operands of ordinary non-volatile stores are terminal non-capturing uses. General pointer comparisons are conservative MAY_CAPTURE because the boolean can expose pointer identity; selected null comparisons are special-cased. Querying the callee argument attribute is what permits direct and mutually recursive functions to converge without manually building call-graph SCCs inside AANoCapture.

This produces facts such as nocapture or an internal "no-capture-maybe-returned" state. It does not produce Go-style leaking param content or dereference-level result summaries.

2. AAHeapToStack: sparse allocation-use proof

Initialization scans call-like instructions. A call becomes an allocation candidate only when LLVM recognizes it as a removable allocation and can reproduce its initial memory state. Recognized deallocation calls are recorded separately.

initialize(function):
    for each call in function:
        if call is a recognized deallocation:
            record deallocation and its freed operand
        else if call is a removable allocation
             and its initial byte state is known:
            record allocation candidate

update(candidate):
    reject if required allocation alignment is unknown, invalid, or unsupported
    if max-heap-to-stack-size is enabled:
        reject if size is unknown or exceeds the limit

    if allUsesAreLocal(candidate):
        status = STACK_DUE_TO_USE
    else if uniqueMustExecuteFreeBoundsLifetime(candidate):
        status = STACK_DUE_TO_FREE
    else:
        status = INVALID

    if size is unknown or allocation is in a loop:
        place future alloca at the original call site
    else:
        permit placement in the entry block

LLVM 19.1.7 defaults max-heap-to-stack-size to 128 bytes. -1 disables that size limit. There is a special path for OpenMP shared allocations, omitted from this simplified pseudocode.

The core use proof is a sparse def-use worklist:

allUsesAreLocal(allocation):
    worklist = uses(allocation)
    visited = {}

    while worklist not empty:
        use = pop(worklist)
        if use is dead or droppable:
            continue

        if pointer is stored into a local slot
           and OnlyExact proves every copied value:
            push uses(each exact load/copy)
            continue

        switch use:
        case load from pointer:
            continue
        case store through pointer:
            continue
        case store pointer as value:
            return false
        case recognized free:
            record free
        case call argument:
            require AANoCapture(argument) and AANoFree(argument)
        case GEP, bitcast, phi, select:
            push uses(derived pointer)
        default:
            return false

    return true

The OnlyExact branch is important: storing the pointer into a local slot is not automatically safe. Attributor asks for the complete set of exact copies and follows those values. If aliasing, clobbers, unsupported readers, or thread visibility prevent an exact proof, the original store remains a capturing/unknown use.

If the use proof fails, upstream LLVM has a second free-based proof. It requires a uniquely associated free, excludes unknown freed objects, checks that the free must execute in the allocation's context, and applies stack/thread-access constraints. This is why upstream AAHeapToStack also consults AANoFree; LLGo Phase 1 intentionally does not implement this second proof.

3. Manifesting the rewrite

manifest(candidate):
    remove matched free calls
    size = proven allocation size
    alignment = max(return alignment, recognized allocation alignment, 1)
    insertionPoint = entry block or original allocation call
    stack = alloca i8, size, alignment
    cast stack if allocation result uses another pointer/address-space type
    replace allocation result with stack
    reproduce the initial memory state (for example, memset zero for calloc)
    remove the allocation call

Upstream LLVM does not reject every loop allocation. It keeps MoveAllocaIntoEntry false and emits the alloca at the original allocation call. LLGo's current Phase 1 policy is intentionally more conservative: it rejects loop/cyclic-region allocation candidates.

Examples verified with LLVM 19.1.7

Safe direct uses and a nocapture nofree call:

define void @safe() {
  %p = call noalias ptr @malloc(i64 8)
  store i64 1, ptr %p, align 8
  call void @read(ptr %p) ; @read is nocapture nofree
  %v = load i64, ptr %p, align 8
  call void @free(ptr %p)
  ret void
}

Attributor rewrites the allocation to %p.h2s = alloca i8, i64 8 and removes the matched free.

An escaping store:

@escaped = global ptr null

define void @global_sink() {
  %p = call noalias ptr @malloc(i64 8)
  store ptr %p, ptr @escaped
  ret void
}

The allocation remains because %p is stored as a value into externally visible memory.

An exact local copy:

%p = call noalias ptr @malloc(i64 8)
%slot = alloca ptr
store ptr %p, ptr %slot
%q = load ptr, ptr %slot
call void @read(ptr %q)
call void @free(ptr %p)

OnlyExact proves %q is the complete local copy, follows %q to @read, and permits the rewrite. LLVM's resulting IR directly passes %p.h2s to @read after later simplification.

What this means for LLGo

The directly reusable core is the sparse uses + worklist + visited + OnlyExact copies proof. LLGo's finite NoCapture[(function, parameter)] map substitutes for the subset of Attributor facts needed by Phase 1. A diagnostic locationGraph can record source-oriented heap/result/mutator/callee flows, but it should not feed back into that proof. The remaining deliberate differences are LLGo's 64 KiB policy, loop rejection, recognized AllocZ/AllocU contracts, and omission of LLVM's free-based AANoFree path.

Sources: AAHeapToStack, AANoCapture, and the 128-byte default, checkForAllUses and OnlyExact copy following, DetermineUseCaptureKind, and upstream heap-to-stack tests.