Proposal: use LLVM AAHeapToStack for escape analysis

[MeteorsLiu]

Proposal: AAHeapToStack escape analysis for LLGo

Status: proposed

1. Summary

LLGo should use Attributor's AAHeapToStack implementation to recover stack allocation opportunities that golang.org/x/tools/go/ssa does not classify precisely.

LLGo's existing x/tools SSA builder mode and lifting behavior remain unchanged. The Go frontend continues to lower retained heap allocations and preserve their source identity. LLVM remains responsible for deciding whether a concrete heap allocation is safe to replace with an alloca. The compiler records successful LLVM conversions and may use them for positive -m diagnostics.

This proposal is deliberately narrower than Go's escape analysis. It does not produce parameter leak summaries or classify every allocation. A conversion is proof that a candidate did not escape; a missed conversion remains unknown.

2. Motivation

The x/tools SSA builder uses a conservative Alloc.Heap decision. For example, new(T) starts as a heap allocation, and taking the address of a local in a potentially escaping context marks that local as heap allocated. It does not use Go compiler-style interprocedural parameter summaries to reconsider that decision.

At the same time, reproducing cmd/compile/internal/escape in LLGo would require maintaining a second source-language escape analysis and adapting its AST-based location graph to x/tools SSA.

LLVM already sees the final pointer operations and call graph available within each module. Attributor can follow a recognized allocation through loads, stores, GEPs, casts, phi nodes, selects, and calls whose arguments are known not to capture or free the pointer.

Consider:

func local() int {
	p := new(int)
	*p = 1
	return *p
}

LLGo currently lowers new(int) according to the conservative Alloc.Heap value. With the proposed allocator attributes, Attributor can replace the resulting runtime.AllocZ call with a stack slot.

By contrast:

func escapes() *int {
	return new(int)
}

The returned pointer is visible in LLVM IR, so Attributor leaves the allocation on the heap without requiring a Go-specific escape root.

3. Current behavior

Heap *ssa.Alloc instructions lower to runtime.AllocZ. Closure records, interface boxing, and several compiler temporaries lower directly to runtime.AllocU or runtime.AllocZ.

LLGo currently runs LLVM's selected default<O*> pipeline without an explicit Attributor stage, so AAHeapToStack does not currently run.

runtime.AllocU and runtime.AllocZ also lack LLVM allocation attributes. Without those attributes, LLVM does not recognize the calls as removable heap allocations.

4. Goals

• Use the AAHeapToStack implementation provided by LLGo's LLVM toolchain; do not maintain a fork of Go escape analysis or LLVM.
• Keep LLGo's existing x/tools SSA builder mode and lifting behavior unchanged.
• Convert eligible direct runtime.AllocU and runtime.AllocZ calls to stack allocations.
• Derive positive does not escape diagnostics from successful conversions.
• Honor //go:noescape for external functions where a Go parameter maps directly to an LLVM pointer parameter.
• Keep every missed or unsupported case conservative.

5. Out of scope

• Full compatibility with Go's -m output.
• Go parameter leak levels or heap/result/mutator/callee summaries.
• Heap-to-stack conversion for allocations executed in a loop.
• Dynamic-sized allocations or changes to the size limits enforced by AAHeapToStack.
• Allocation hidden inside MakeSlice, MakeMap, or NewChan runtime helpers in non-LTO builds.
• //go:noescape propagation through aggregate LLVM parameters such as slice, string, interface, and closure values.
• //go:uintptrescapes, uintptr keepalive behavior, or pointer information lost through uintptr conversion.

6. Proposed design

6.1 Pipeline

The optimizing pipeline becomes:

go/ssa (existing builder mode)
    -> LLVM lowering with allocator attributes and source allocation IDs
    -> attributor
    -> collect heap-to-stack results
    -> default<O*>

Attributor analyzes the concrete heap allocations produced by LLGo's existing x/tools SSA lowering. The proposal does not change the x/tools SSA builder mode or disable its lifting pass. The normal LLVM pipeline remains responsible for subsequent scalarization, dead code elimination, and target optimization.

Retained heap *ssa.Alloc instructions already carry Go source positions and lower through Builder.Alloc(elem, v.Heap). LLGo can associate those candidates with LLVM results during the existing lowering step without reconstructing allocations removed by x/tools SSA lifting.

6.2 Recognizing LLGo allocators

The declaration of both allocation functions receives a return noalias attribute and an allocsize(0) attribute.

Eligible individual call sites receive an allockind attribute:

; runtime.AllocZ(size)
call ptr @runtime.AllocZ(i64 %size) allockind("alloc,zeroed")

; runtime.AllocU(size)
call ptr @runtime.AllocU(i64 %size) allockind("alloc,uninitialized")

The allockind attribute is intentionally attached to candidate call sites, not globally to every call through the function declaration. This lets LLGo exclude unsafe policy cases, notably allocations in cyclic SSA blocks, while still using the stock Attributor pass.

AAHeapToStack's existing size and alignment checks remain authoritative. LLGo does not override the conversion limits provided by its LLVM toolchain.

AllocRoot is not an eligible allocator. It has different lifetime and GC-root semantics.

6.3 Candidate selection

A direct AllocU or AllocZ call is a candidate when all of the following are true:

• The call represents compiler-generated Go heap storage, not a user-requested uncollectable root.
• The source SSA instruction belongs to an acyclic basic block.
• The call has a stable source allocation ID.

Candidate selection does not attempt to decide escape. Return, global storage, unknown calls, and other escape roots remain entirely LLVM's responsibility.

Allocations in cyclic blocks remain heap allocations in this increment. LLVM can otherwise create an alloca inside the loop, which preserves pointer identity but can grow stack use on every iteration until the function returns.

6.4 Recording LLVM decisions

Each candidate call receives an internal LLVM name derived from a compilation-local allocation ID:

llgo.alloc.42

The current AAHeapToStack implementation names the replacement alloca by appending .h2s:

llgo.alloc.42.h2s

LLGo runs Attributor as a separate pass stage and scans the module immediately afterward. The source allocation table records which IDs acquired an .h2s alloca and which allocator calls remain.

This name is an internal AAHeapToStack integration detail, not part of LLGo's IR or command-line compatibility surface. A focused integration test must detect if the LLVM toolchain changes it.

No LLVM optimization-diagnostic text is parsed. The current Go LLVM bindings do not expose the diagnostic-handler setup needed to consume optimization remarks, and textual remarks are not a stable compiler interface.

6.5 //go:noescape

LLGo adopts Go's placement rule for the directive: //go:noescape is valid only on a function declaration without a Go body. Using it on a function with a body is a compile-time error.

For each Go pointer parameter that maps directly to an LLVM pointer parameter, LLGo adds parameter-level attributes:

ptr nocapture nofree

nocapture states that the external implementation does not retain the pointer or return it through another value. Parameter-level nofree states that the implementation does not deallocate that pointer. Mutation remains allowed; the parameter is not marked readonly.

The nofree promise is necessary for HeapToStack because a stack address cannot be passed to an implementation that might deallocate it. This interpretation is consistent with LLGo's Go-managed allocation contract: pointers returned by AllocU and AllocZ are owned by the GC and must not be manually freed by an external implementation.

If a //go:noescape parameter lowers to an LLVM aggregate containing pointers, LLGo emits no capture/free attribute for that parameter in this increment. The LLVM parameter attributes used here cannot describe the individual data pointer inside the aggregate without changing the ABI or adding a separate summary mechanism.

Without //go:noescape, a bodyless external function remains conservative. Passing a candidate allocation to it normally prevents HeapToStack conversion.

6.6 Diagnostics

The structured allocation table is the source of diagnostics:

LLVM result	Diagnostic meaning
Candidate became .h2s	The allocation does not escape and was moved to the stack
Allocator call remains	Unknown; emit no escape conclusion
Site was not a candidate	Unsupported or excluded; emit no escape conclusion

This proposal adds positive allocation diagnostics only. It must not print leaking param, moved to heap, or escapes to heap merely because LLVM did not convert a call.

//go:noescape pointer parameters may be reported as does not escape because that result comes from the source directive contract rather than failure-based inference.

7. Module boundaries

• cl owns the relationship between x/tools SSA instructions and Go source positions. It supplies a stable allocation ID and the acyclic-block fact to the LLVM lowering layer. It also validates //go:noescape and supplies the affected direct-pointer parameter indices.
• ssa owns LLVM allocation-call construction. It materializes allocator declaration attributes, candidate call-site attributes, and allocation names.
• internal/build owns pass ordering and result collection. It does not infer escape from Go syntax or interpret individual LLVM uses.
• cmd/internal/compile formats requested -m diagnostics from structured results. It does not inspect LLVM IR or parse pass output.
• The runtime keeps the existing AllocU and AllocZ implementations. Stack conversion removes their heap-profile accounting exactly because no heap allocation occurs.

No new exported Go package API, command-line flag, persistent file format, or runtime protocol is introduced.

8. Safety and fallback behavior

HeapToStack is an optimization. Every unsupported or uncertain case keeps the existing heap allocation.

The following cases remain heap allocated:

• the pointer is returned;
• the pointer is stored into externally visible memory;
• the pointer reaches a call without sufficient capture/free information;
• LLVM cannot track one of its uses;
• the size or alignment is unsupported;
• the allocation occurs in a cyclic SSA block;
• the allocation is hidden behind an unsupported runtime helper.

Misusing //go:noescape is a source-contract violation. As with Go, LLGo cannot verify the behavior of the external implementation.

9. Compatibility

The proposal changes optimization decisions but not valid Go program behavior. Programs may observe fewer heap allocations through allocation statistics or profiles, matching the effect of ordinary stack allocation.

Unoptimized builds remain eligible to keep their current behavior. Enabling analysis-only -m reporting for an unoptimized build is a separate integration detail and must not silently enable code-generation optimizations.

The design has no persistent migration cost. Removing the explicit Attributor stage and call-site allocator attributes restores the previous allocation behavior.

10. Alternatives considered

Port Go escape analysis

Rejected for this increment. The solver can be adapted, but most of the Go implementation constructs a location graph from cmd/compile/internal/ir and would need to be rewritten for x/tools SSA.

Use x/tools Alloc.Heap as the final answer

Rejected because the value is intentionally conservative and lacks interprocedural summaries.

Parse LLVM optimization remarks

Rejected because it adds a textual interface and requires LLVM diagnostic plumbing that the current Go bindings do not expose. The separate pass stage and allocation ID table are smaller and deterministic.