Proposal: Semantic Pruning of Unreachable Methods from a Global Graph

[luoliwoshang]

Status

• Status: Proposed
• Scope: define LLGo's link-time semantic method pruning scheme for executable builds
• Current rollout scope: prioritize the exe build path
• Background: the design is inspired by Go's link-time deadcode approach, but this document defines only LLGo's own semantic model, input contract, and implementation direction

Abstract

LLGo needs a link-time method pruning mechanism that is specifically designed for Go semantics. Ordinary call/ref reachability can only see direct symbol references, but in Go, whether a method must be kept often also depends on extra semantics such as interface conversions, interface method calls, name-based method lookup, and reflection. Because of that, ordinary DCE alone cannot correctly express which types have entered the dynamic dispatch semantic domain and which method-table slots are actually demanded.

The proposed scheme is to model those Go semantics explicitly under a whole-program view and analyze them together with ordinary reachability in one unified multi-round propagation process, ultimately producing a stable result of type symbol -> live method indexes. For interface method demands, the matching rule is no longer just "method name + method type"; it additionally requires that the concrete type fully implement the target interface, preventing methods on concrete types that do not actually satisfy the interface from being kept by mistake.

This is not a problem that can be solved by relying on the ordinary reference graph alone; it requires explicit modeling of Go semantics at link time and a dedicated method-liveness analysis.

Problem Definition

Why ordinary gc-sections, ordinary linker DCE, and ordinary IR DCE are not enough

Ordinary linkers and ordinary IR DCE rely on explicit reference relationships:

• one function calls another function
• one global constant references another global symbol
• one initializer contains an ordinary reference to a symbol

That model is not enough for Go, because method invocation in Go is not a purely direct-reference model.

In Go, whether a method must be kept often depends on semantic events such as:

1. whether a concrete type may enter interface dispatch
2. whether a specific interface method slot is actually called
3. whether a method name is requested by MethodByName
4. whether reflection forces the analysis into a conservative mode

If the compiler does not encode those events explicitly, the linker only sees a pile of "type constants reference method symbols," and the result degenerates into:

• as long as the type descriptor is live, methods are likely to stay live with it
• it cannot distinguish "listed in a method table" from "actually dynamically callable"
• it cannot precisely delete some methods while keeping others at link time

A Minimal Example

Consider the following simplified Go program:

package main

type Reader interface {
	Read([]byte) (int, error)
}

type Writer interface {
	Write([]byte) (int, error)
}

type stringReader struct{}

func (*stringReader) Len() int                       { return 0 }
func (*stringReader) Read([]byte) (int, error)      { return 0, nil }
func (*stringReader) Close() error                  { return nil }
func (*stringReader) WriteTo(Writer) (int64, error) { return 0, nil }

func ReadAll(r Reader) {
	_, _ = r.Read(nil)
}

func main() {
	ReadAll(&stringReader{})
}

The program is semantically simple:

1. the Reader interface requires only one method: Read([]byte) (int, error)
2. the concrete type stringReader still has other methods such as Len, Close, and WriteTo
3. the program boxes stringReader into Reader and calls Read through the interface

One point needs to be stated up front: these are not a bunch of irrelevant references artificially inserted by the compiler. They are capabilities that the Go runtime actually needs.

Once a concrete type may participate in interface-based dynamic dispatch, the runtime must be able to answer:

1. what methods this concrete type has
2. what each method is called
3. what the signature of each method is
4. which function entry point to jump to for interface calls
5. which function entry point to jump to for direct method calls

As a result, types with method sets naturally carry an abi.Method table inside abi.Type / abi.UncommonType.
Each entry in that table carries the method name, the method type, and the corresponding IFn / TFn. In IR, IFn / TFn are real function addresses.

In current LLGo v0.13.0, this method table is still emitted at compile time as the complete method set in one shot.
The current implementation lives in ssa/abitype.go:

1. abiType builds the overall layout abi.Type + abi.UncommonType + [N]abi.Method for types with methods
2. abiUncommonMethods walks the full method set via mset.Len(), constructs [N]abi.Method entry by entry, and writes every Name / MType / IFn / TFn

So if the program above is compiled to current LLGo LLVM IR, you will see that although the only semantically demanded slot is Reader.Read, the pointer type descriptor of stringReader still carries the full method table:

@"*_llgo_github.com/goplus/llgo/cl/_testgo/reader.stringReader" = weak_odr constant
  { %"github.com/goplus/llgo/runtime/abi.PtrType",
    %"github.com/goplus/llgo/runtime/abi.UncommonType",
    [10 x %"github.com/goplus/llgo/runtime/abi.Method"] } {
    ...,
    [10 x %"github.com/goplus/llgo/runtime/abi.Method"] [
      { ..., ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).Len",     ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).Len" },
      { ..., ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).Read",    ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).Read" },
      { ..., ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).ReadAt",  ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).ReadAt" },
      ...,
      { ..., ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).WriteTo", ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).WriteTo" }
    ]
  }

At the same time, in an ordinary function body you can also see that the interface boxing directly references that type descriptor:

%2 = call ptr @"github.com/goplus/llgo/runtime/internal/runtime.NewItab"(
  ptr @"_llgo_iface$uycIKA3bbxRhudEjW1hHKWKdLqHQsCVy8NdW1bkQmNw",
  ptr @"*_llgo_github.com/goplus/llgo/cl/_testgo/reader.stringReader")

From the perspective of ordinary gc-sections or ordinary lld, this is a very direct strong reference chain:

main / ReadAll
  -> stringReader's abi.Type
  -> abi.UncommonType / [10 x abi.Method]
  -> Name / MType / IFn / TFn inside each abi.Method
  -> Len / Read / ReadAt / ... / WriteTo

That is the problem:

1. the linker only sees "a live global constant containing real function pointers and type pointers"
2. it does not know that semantically the only demanded slot is Reader.Read
3. therefore, once @"*_llgo_github.com/goplus/llgo/cl/_testgo/reader.stringReader" becomes reachable, all methods in the table are kept together
4. this is not an lld bug; ordinary reference graphs simply cannot express "only some slots in the same method table actually need to be kept"

That is exactly why LLGo needs extra semantic analysis:

1. first determine which types actually enter the interface semantic domain under a whole-program view
2. then determine which interface slots are actually demanded
3. finally retain only the corresponding method indexes instead of keeping the whole abi.Method table alive

The Core Problem

There is only one question we really want to answer:

For a given type's method table, which methods are actually required by runtime semantics?

The example above already shows the problem:

1. once a concrete type descriptor becomes reachable, the ordinary reference graph sees the entire abi.Method table as reachable
2. but what we really need is not "the type is live, therefore all its methods are live"
3. what we really need is: the type itself may stay live, while the method table must be partially prunable according to runtime semantics

In other words, link time must support "keep the type, prune the method table partially," and the ordinary reference graph cannot express that capability.

Go's existing link-time deadcode design already demonstrates that this problem cannot be solved by pushing harder on an ordinary reference graph. Go solves it by making the linker understand extra semantics related to types, interfaces, and reflection, and then running a dedicated method-liveness analysis under a whole-program view.

LLGo will follow the same direction: it will not try to keep forcing this problem back into the ordinary reference graph. Instead, it will introduce a separate link-time semantic analysis model.

Relation to Go's Design

This proposal is explicitly inspired by Go's link-time deadcode approach, but it does not aim to reproduce Go's internal implementation details.

What LLGo wants to absorb falls into two categories:

1. the direction of the solution: bring interface conversions, interface method calls, name-based method lookup, and conservative reflection mode into link-time analysis
2. the analysis method itself: perform semantic reachability analysis under a whole-program view with repeated propagation until convergence, rather than depending only on the ordinary reference graph

What LLGo does not want to copy is:

1. Go's object format and loader structure
2. Go's internal relocation encoding
3. the exact layering of Go's linker implementation

The biggest engineering difference between the two schemes is where the semantic input is carried:

1. Go stores related semantic information in its goobj / relocation / type data / symbol attribute system, such as "type enters interface semantics," interface method demands, name-based method lookup, and conservative reflection markers
2. LLGo emits that semantic information explicitly into named metadata on llvm.Module, then reads it back uniformly during the link build stage

At a higher semantic level, however, the two are aligned:

1. both collect ordinary reachability edges and semantic events under a global view
2. both perform repeated propagation until convergence at whole-program scope
3. both attempt to answer the same question: which slots in a given concrete type's method table must ultimately be retained

LLGo's current design also explicitly adopts and improves one conservative point in Go:

1. interface demands must not be matched by "method name + method type" alone
2. the concrete type must also fully implement the target interface

This avoids keeping methods on partially implementing types just because their signatures happen to match.

Based on this common direction and these differences, LLGo will use an architecture of "per-package semantic emission, global unified analysis, and result rewrite."

Analysis Architecture

The core characteristics of this design are:

1. when compiling a single package, emit only the semantic information that is already statically knowable inside that package
2. do not decide at per-package compile time whether a method is ultimately retained
3. wait until the whole-program []llvm.Module set is available, then analyze method reachability from a global view

Exactly which semantics must be marked during per-package compilation, and how the global stage consumes those semantics to decide method liveness, are described later. Here we first present the overall architecture.

The pipeline can be summarized as:

flowchart TD
    A["Package A<br/>ssa/cl compile<br/>module A + metadata"]
    B["Package B<br/>ssa/cl compile<br/>module B + metadata"]
    C["Package C<br/>ssa/cl compile<br/>module C + metadata"]
    A --> D["Build-stage aggregation<br/>whole-program LLVM modules"]
    B --> D
    C --> D
    D --> E["graph<br/>extract ordinary edges<br/>and semantic input"]
    E --> F["analyze<br/>global method reachability analysis"]
    F --> G["result<br/>live method indexes by type symbol"]
    G --> H["rewrite<br/>copy and prune strong abi.Type"]

Loading

More concretely:

1. ssa/cl still compiles packages independently, but additionally writes semantics such as interface conversions, interface method demands, name-based method lookup, conservative reflection markers, and method-slot information into the current package's llvm.Module
2. once the build stage has collected all package []llvm.Module values, graph scans ordinary reference edges and those metadata rows across all packages and aggregates them into a single whole-program input
3. analyze runs repeated propagation under a whole-program view and produces only one stable result:

type symbol -> live method indexes

4. once that result is computed, the analysis itself is finished; rewrite merely consumes the result, copies weak abi.Type definitions, prunes method tables, emits strong definitions, and lets final linking override the originals

This separation has two important layers:

1. ordinary reference edges still come from ordinary IR content such as function bodies, global initializers, and constant expressions
2. extra semantics related to interfaces, reflection, and method tables are emitted explicitly during per-package compilation and consumed uniformly during the global stage

Goals and Boundaries

The goals of this proposal are:

1. define an official link-time semantic method-pruning scheme for LLGo
2. stably produce type symbol -> live method indexes during analysis
3. rewrite pruned strong abi.Type definitions from that result

This proposal does not currently include:

1. reproducing Go's internal object / relocation / loader structure
2. covering every build mode in one go
3. discussing generic IR optimizations such as SCCP, CFG DCE, or constant propagation at the same time

Whole-Program Information Model

This section defines the normalized whole-program information required by the algorithm itself, denoted as WholeProgramInfo.

Here, whole-program does not mean "the information model of one package." It means the final aggregate input after combining all packages that participate in the link.
In other words, every field in WholeProgramInfo should be understood as the result of merging all per-package contributions of ordinary edges, type propagation edges, interface information, method-slot information, and semantic demands.

The boundary of analyze is not LLVM IR, nor metadata themselves, but this normalized WholeProgramInfo.
As long as the outside world can provide equivalent information, the algorithm does not care which object format, scanning process, or intermediate carrier produced it.

In the current LLGo implementation, this WholeProgramInfo is aggregated by the build stage from all package LLVM modules.
That also means the algorithm itself would not need to change if, in the future, pre-extracted per-package semantic information were cached and then assembled directly into WholeProgramInfo during the whole-program stage.
That kind of caching is not part of the current implementation. The current baseline still extracts uniformly from ssa -> llvm.Module outputs.

Therefore, the keys and values in the definitions below describe whole-program aggregated semantics, not the local view of any single package.

Its shape is:

type Symbol = string

type MethodSig struct {
	Name  string
	MType Symbol
}

type MethodSlot struct {
	Index int
	Sig   MethodSig
	IFn   Symbol
	TFn   Symbol
}

type IfaceMethodDemand struct {
	Target Symbol
	Sig    MethodSig
}

type WholeProgramInfo struct {
	OrdinaryEdges  map[Symbol]map[Symbol]struct{}
	TypeChildren   map[Symbol]map[Symbol]struct{}
	InterfaceInfo  map[Symbol][]MethodSig
	UseIface       map[Symbol][]Symbol
	UseIfaceMethod map[Symbol][]IfaceMethodDemand
	MethodInfo     map[Symbol][]MethodSlot
	UseNamedMethod map[Symbol][]string
	ReflectMethod  map[Symbol]struct{}
}

Here, MethodSig is not a top-level input item. It is the shared method-signature representation used by both MethodInfo and InterfaceInfo.
Under the current baseline:

1. Name must be the normalized method name
2. exported methods use the plain method name directly, for example Read
3. unexported methods use a normalized name that includes the full package path
4. MType is the symbol of the method type descriptor

OrdinaryEdges

OrdinaryEdges is the ordinary symbol reachability graph.

What the outside world needs to provide here is the ordinary reference graph formed by ordinary call/ref.

For example:

func helper() {}

func main() {
	helper()
}

In this example:

1. main -> helper goes into OrdinaryEdges
2. this is a direct ordinary call
3. it is not interface semantics and needs no extra metadata

That means:

1. the key is the source symbol
2. the value is the set of target symbols directly reachable from that symbol through ordinary call/ref

Likewise, direct struct-method calls also belong to OrdinaryEdges. For example:

type S struct{}

func (*S) M() {}
func (S) N() {}

func main() {
	var s S
	s.M()
	s.N()
}

In this example:

1. main -> (*S).M and main -> S.N are still ordinary edges
2. because IR can already see the concrete method symbols directly
3. although the source says s.M(), s is addressable, so it eventually lowers to (*S).M

Using the symbol shapes that current LLGo actually emits, the structured form is:

OrdinaryEdges = map[Symbol]map[Symbol]struct{}{
	"github.com/goplus/llgo/doc/tt.main": {
		"github.com/goplus/llgo/doc/tt.(*S).M": {},
		"github.com/goplus/llgo/doc/tt.S.N":    {},
	},
}

Interface method calls are different. For example:

type I interface{ M() }

func call(i I) {
	i.M()
}

Here we do not record call -> some concrete implementation of M directly in OrdinaryEdges, because the IR does not contain a unique concrete target symbol.
This kind of call is expressed separately later through extra semantic input.

TypeChildren

TypeChildren records direct propagation edges between types.

Its meaning is:

1. if a source type has entered the interface/reflection-related analysis domain
2. then child types observable through runtime type data must enter the same analysis domain as well

Note:

1. the recorded edges are direct propagation edges, not a pre-expanded transitive closure
2. the recursive closure is expanded during analysis by following these edges

This is needed because:

1. once a type may continue to be observed through interface values or reflection
2. the program may later obtain child types that appear inside it
3. the method tables of those child types may also affect which dynamic methods must ultimately be kept
4. therefore the analyzer must know about this child-type propagation relationship

For example:

type Inner struct{}

func (Inner) M() {}

type Outer struct {
	F Inner
}

func main() {
	var x any = Outer{}
	_ = x
}

In structured form:

TypeChildren = map[Symbol]map[Symbol]struct{}{
	"_llgo_github.com/goplus/llgo/demo.Outer": {
		"_llgo_github.com/goplus/llgo/demo.Inner": {},
	},
}

MethodInfo

MethodInfo describes the method-slot table of a concrete type.
It is not "the set of already demanded methods." It is "the set of candidate slots that the analyzer may mark live." When a slot is matched for the first time, the analyzer continues by pulling in its MType/IFn/TFn.
If a type has no methods, it may simply be absent from MethodInfo.

For example, consider demo/file.go:

package demo

type File struct{}

func (*File) Read([]byte) (int, error) { return 0, nil }
func (*File) Close() error             { return nil }

Assuming the compiled package path is github.com/goplus/llgo/demo, its corresponding MethodInfo can be understood as:

MethodInfo["_llgo_github.com/goplus/llgo/demo.File"] = []MethodSlot{
	{
		Index: 0,
		Sig: MethodSig{
			Name:  "Read",
			MType: "_llgo_func$A1...",
		},
		IFn: "github.com/goplus/llgo/demo.(*File).Read",
		TFn: "github.com/goplus/llgo/demo.File.Read",
	},
	{
		Index: 1,
		Sig: MethodSig{
			Name:  "Close",
			MType: "_llgo_func$B2...",
		},
		IFn: "github.com/goplus/llgo/demo.(*File).Close",
		TFn: "github.com/goplus/llgo/demo.File.Close",
	},
}

Where:

1. the key is the concrete type symbol
2. the value is the []MethodSlot array ordered exactly like the type's abi.Method table
3. each entry is one MethodSlot, and its Sig is a MethodSig
4. Index must exactly match the final slot index in the abi.Method table
5. under the current baseline, IFn and TFn always exist, though they may be equal for some methods

InterfaceInfo

InterfaceInfo describes the method set of an interface.

For example, consider demo/reader.go:

package demo

type Reader interface {
	Read([]byte) (int, error)
	Close() error
}

Assuming the compiled package path is github.com/goplus/llgo/demo, its corresponding InterfaceInfo can be understood as:

InterfaceInfo["_llgo_github.com/goplus/llgo/demo.Reader"] = []MethodSig{
	{
		Name:  "Read",
		MType: "_llgo_func$A1...",
	},
	{
		Name:  "Close",
		MType: "_llgo_func$B2...",
	},
}

Where:

1. the key is the interface type symbol
2. the value is the set of method signatures required by that interface, expressed here as []MethodSig
3. semantically, it means "which methods this interface requires in full"; the adaptation layer is responsible for deduplication and normalization

UseIface

UseIface is grouped by Owner. The value is the set of concrete types that must enter UsedInIface once that Owner becomes reachable.

For example, consider demo/reader.go:

package demo

type Reader interface {
	Read([]byte) (int, error)
}

type File struct{}

func (*File) Read([]byte) (int, error) { return 0, nil }

func main() {
	var r Reader = &File{}
	_ = r
}

Assuming the compiled package path is github.com/goplus/llgo/demo, the corresponding UseIface can be understood as:

UseIface = map[Symbol][]Symbol{
	"github.com/goplus/llgo/demo.main": []Symbol{
		"*_llgo_github.com/goplus/llgo/demo.File",
	},
}

UseIfaceMethod

UseIfaceMethod is grouped by Owner. The value is the set of interface method demands produced once that Owner becomes reachable.

For example, consider demo/reader.go:

package demo

type Reader interface {
	Read([]byte) (int, error)
}

func consume(r Reader, p []byte) {
	_, _ = r.Read(p)
}

Assuming the compiled package path is github.com/goplus/llgo/demo, the corresponding UseIfaceMethod can be understood as:

UseIfaceMethod = map[Symbol][]IfaceMethodDemand{
	"github.com/goplus/llgo/demo.consume": []IfaceMethodDemand{
		{
			Target: "_llgo_github.com/goplus/llgo/demo.Reader",
			Sig: MethodSig{
				Name:  "Read",
				MType: "_llgo_func$A1...",
			},
		},
	},
}

UseNamedMethod

UseNamedMethod is grouped by Owner. The value is the set of method-name demands produced once that Owner becomes reachable.
Only when the method name is statically known at compile time does a MethodByName-like operation go here. If the name is not a compile-time constant, the case degrades to ReflectMethod described later.

For example, consider demo/lookup.go:

package demo

func lookup(v any) {
	_, _ = reflect.TypeOf(v).MethodByName("ServeHTTP")
}

Assuming the compiled package path is github.com/goplus/llgo/demo, the corresponding UseNamedMethod can be understood as:

UseNamedMethod = map[Symbol][]string{
	"github.com/goplus/llgo/demo.lookup": []string{
		"ServeHTTP",
	},
}

ReflectMethod

ReflectMethod is a set of owners. Once any Owner in that set becomes reachable, the analysis must enter conservative reflection mode.
Typical sources include reflect.Type.Method, reflect.Value.Method, and MethodByName when the method name cannot be determined statically at compile time.

For example, consider demo/value.go:

package demo

func valueByIndex(v any) {
	_ = reflect.ValueOf(v).Method(0)
}

Assuming the compiled package path is github.com/goplus/llgo/demo, the corresponding ReflectMethod can be understood as:

ReflectMethod = map[Symbol]struct{}{
	"github.com/goplus/llgo/demo.valueByIndex": {},
}

Once this input is hit, the current baseline semantics are: for all concrete types in UsedInIface, retain the slots corresponding to exported methods.

Core Algorithm

Input

The algorithm takes two inputs:

1. a whole-program WholeProgramInfo
2. a set of link roots

Where:

1. WholeProgramInfo is the aggregate result of merging semantic information from all packages participating in the current link
2. roots are the starting points of ordinary reachability, such as main, _start, and __main_argc_argv

Output Shape

The analyzer outputs:

type Result map[string]map[int]struct{}

Semantically:

1. the key is a concrete type symbol
2. the value is the set of method-slot indexes that must be retained for that type

This is the final result of the analysis stage.
Once this result is available, the algorithm stops. It does not continue into ABI type rewriting or strong-symbol generation; those belong to the later rewrite stage.

Liveness Loop

The core logic can be summarized as a loop of "ordinary flood + semantic-demand propagation + method-slot marking":

1. start from roots and propagate ordinary reachability along OrdinaryEdges
2. whenever an owner becomes reachable, read its semantic demands from UseIface, UseIfaceMethod, UseNamedMethod, and ReflectMethod
3. UseIface adds concrete types into UsedInIface and continues propagation along TypeChildren
4. UseIfaceMethod accumulates interface method demands for interfaces; UseNamedMethod accumulates exact method-name demands; ReflectMethod turns on conservative reflection mode
5. then, for all concrete types already in UsedInIface, inspect their MethodInfo slots and decide which ones should be kept
6. the most important rule is: an interface method demand is allowed to match a slot on a concrete type only when that concrete type fully implements the target interface; identical method name and method type are not enough on their own
7. once a slot becomes live for the first time, its MType, IFn, and TFn are reinserted into the ordinary reachability graph
8. repeat until there are no new ordinary reachable symbols, no new semantic demands, and no new live method slots

The final result is:

type symbol -> live method indexes

Examples

Example 1: Interface Calls Keep Only Truly Demanded Methods

Consider:

type Reader interface {
	Read([]byte) (int, error)
}

type File struct{}

func (File) Read([]byte) (int, error) { return 0, nil }
func (File) Close() error             { return nil }

func consume(r Reader, p []byte) {
	_, _ = r.Read(p)
}

func main() {
	consume(File{}, nil)
}

Before analysis starts, the whole-program input for this example can be approximated as:

roots := []Symbol{
	"github.com/goplus/llgo/demo.main",
}

OrdinaryEdges = map[Symbol]map[Symbol]struct{}{
	"github.com/goplus/llgo/demo.main": {
		"github.com/goplus/llgo/demo.consume": {},
	},
}

UseIface = map[Symbol][]Symbol{
	"github.com/goplus/llgo/demo.main": {
		"_llgo_github.com/goplus/llgo/demo.File",
	},
}

UseIfaceMethod = map[Symbol][]IfaceMethodDemand{
	"github.com/goplus/llgo/demo.consume": {
		{
			Target: "_llgo_github.com/goplus/llgo/demo.Reader",
			Sig: MethodSig{
				Name:  "Read",
				MType: "_llgo_func$readsig",
			},
		},
	},
}

InterfaceInfo = map[Symbol][]MethodSig{
	"_llgo_github.com/goplus/llgo/demo.Reader": {
		{
			Name:  "Read",
			MType: "_llgo_func$readsig",
		},
	},
}

MethodInfo = map[Symbol][]MethodSlot{
	"_llgo_github.com/goplus/llgo/demo.File": {
		{
			Index: 0,
			Sig: MethodSig{
				Name:  "Read",
				MType: "_llgo_func$readsig",
			},
			IFn: "github.com/goplus/llgo/demo.(*File).Read",
			TFn: "github.com/goplus/llgo/demo.File.Read",
		},
		{
			Index: 1,
			Sig: MethodSig{
				Name:  "Close",
				MType: "_llgo_func$closesig",
			},
			IFn: "github.com/goplus/llgo/demo.(*File).Close",
			TFn: "github.com/goplus/llgo/demo.File.Close",
		},
	},
}

Here TypeChildren, UseNamedMethod, and ReflectMethod are empty.

The global analysis proceeds as follows:

1. the initial root is main, so the analyzer first places github.com/goplus/llgo/demo.main into the reachable set
2. the first flood propagates along OrdinaryEdges, making github.com/goplus/llgo/demo.consume reachable as well
3. during semantic activation, UseIface[main] matches, so _llgo_github.com/goplus/llgo/demo.File enters UsedInIface
4. in the same round, UseIfaceMethod[consume] also matches, producing one interface method demand: Reader.Read
5. the analysis then enters the method-marking phase; it checks only concrete types already in UsedInIface, which here is File
6. File has two slots in MethodInfo: Read and Close
7. for the Read slot, its MethodSig matches the current interface demand Reader.Read, and File fully implements Reader, so the slot becomes live
8. once the Read slot becomes live for the first time, the result records File -> [0], and the slot's MType/IFn/TFn are put back into ordinary reachability propagation
9. the Close slot matches no interface demand, no name demand, and no conservative-reflection condition, so it is not kept
10. the next round runs flood again to process the newly added MType/IFn/TFn; if those newly reachable symbols trigger more semantic events, the loop continues
11. when ordinary flood, semantic activation, and method marking all stop producing new information, the analysis converges

The final result is:

_llgo_github.com/goplus/llgo/demo.File: [0]

Where 0 is the slot index of Read.

Example 2: Partially Implementing Types Must Not Be Kept by Mistake

Consider:

type A struct{}

func (*A) Foo() {}
func (*A) Bar() {}

type B struct{}

func (*B) Foo() {}
func (*B) Bar() {}
func (*B) Car() {}

type BI interface {
	Foo()
	Bar()
	Car()
}

func callBI(x BI) {
	x.Foo()
	x.Bar()
}

func main() {
	var _ any = &A{}
	callBI(&B{})
}

In this example:

1. A does enter the interface semantic domain, because main contains a conversion &A{} -> any
2. B also enters the interface semantic domain, because main passes &B{} to BI
3. however, the actual interface calls happen only inside callBI, and they only call Foo and Bar

From the algorithm's point of view, the whole-program input can be approximated as:

roots := []Symbol{
	"github.com/goplus/llgo/demo.main",
}

OrdinaryEdges = map[Symbol]map[Symbol]struct{}{
	"github.com/goplus/llgo/demo.main": {
		"github.com/goplus/llgo/demo.callBI": {},
	},
}

UseIface = map[Symbol][]Symbol{
	"github.com/goplus/llgo/demo.main": {
		"*_llgo_github.com/goplus/llgo/demo.A",
		"*_llgo_github.com/goplus/llgo/demo.B",
	},
}

UseIfaceMethod = map[Symbol][]IfaceMethodDemand{
	"github.com/goplus/llgo/demo.callBI": {
		{
			Target: "_llgo_github.com/goplus/llgo/demo.BI",
			Sig: MethodSig{
				Name:  "Foo",
				MType: "_llgo_func$foosig",
			},
		},
		{
			Target: "_llgo_github.com/goplus/llgo/demo.BI",
			Sig: MethodSig{
				Name:  "Bar",
				MType: "_llgo_func$barsig",
			},
		},
	},
}

InterfaceInfo = map[Symbol][]MethodSig{
	"_llgo_github.com/goplus/llgo/demo.BI": {
		{Name: "Foo", MType: "_llgo_func$foosig"},
		{Name: "Bar", MType: "_llgo_func$barsig"},
		{Name: "Car", MType: "_llgo_func$carsig"},
	},
}

MethodInfo = map[Symbol][]MethodSlot{
	"*_llgo_github.com/goplus/llgo/demo.A": {
		{Index: 0, Sig: MethodSig{Name: "Foo", MType: "_llgo_func$foosig"}, IFn: "github.com/goplus/llgo/demo.(*A).Foo", TFn: "github.com/goplus/llgo/demo.(*A).Foo"},
		{Index: 1, Sig: MethodSig{Name: "Bar", MType: "_llgo_func$barsig"}, IFn: "github.com/goplus/llgo/demo.(*A).Bar", TFn: "github.com/goplus/llgo/demo.(*A).Bar"},
	},
	"*_llgo_github.com/goplus/llgo/demo.B": {
		{Index: 0, Sig: MethodSig{Name: "Foo", MType: "_llgo_func$foosig"}, IFn: "github.com/goplus/llgo/demo.(*B).Foo", TFn: "github.com/goplus/llgo/demo.(*B).Foo"},
		{Index: 1, Sig: MethodSig{Name: "Bar", MType: "_llgo_func$barsig"}, IFn: "github.com/goplus/llgo/demo.(*B).Bar", TFn: "github.com/goplus/llgo/demo.(*B).Bar"},
		{Index: 2, Sig: MethodSig{Name: "Car", MType: "_llgo_func$carsig"}, IFn: "github.com/goplus/llgo/demo.(*B).Car", TFn: "github.com/goplus/llgo/demo.(*B).Car"},
	},
}

The global analysis proceeds as follows:

1. the initial root is main, so the analyzer first places github.com/goplus/llgo/demo.main into the reachable set
2. the first flood propagates along OrdinaryEdges, making github.com/goplus/llgo/demo.callBI reachable as well
3. during semantic activation, UseIface[main] matches, so both *_llgo_github.com/goplus/llgo/demo.A and *_llgo_github.com/goplus/llgo/demo.B enter UsedInIface
4. in the same round, UseIfaceMethod[callBI] also matches, producing two interface method demands: BI.Foo and BI.Bar
5. the analysis then enters the method-marking phase; it inspects all concrete types already in UsedInIface, namely A and B
6. if we matched only by Name + MType, then A.Foo, A.Bar, B.Foo, and B.Bar would all satisfy the demand; this is exactly the false positive we want to avoid
7. the current design does not do that directly; it first uses InterfaceInfo[BI] to decide whether a concrete type fully implements BI
8. for A, its own method set contains only Foo and Bar, while InterfaceInfo[BI] requires Foo, Bar, and Car; therefore A does not fully implement BI
9. therefore, even though A.Foo and A.Bar both have matching MethodSig, they cannot satisfy the interface demands BI.Foo or BI.Bar, and they are not kept
10. for B, its method set completely covers InterfaceInfo[BI], so B is judged to fully implement BI
11. under that condition, B.Foo and B.Bar are now allowed to satisfy the current demands, so those two slots become live and their MType/IFn/TFn are pushed back into ordinary reachability propagation
12. B.Car is one of the methods needed for B to fully implement BI, but the program never issues a BI.Car demand, so it is not kept merely because it participated in interface-implementation checking
13. later rounds continue running flood -> semantic activation -> method marking until all three phases stop producing new information

The final result contains only the Foo and Bar slots on B. It does not contain partial methods on A, and it does not keep B.Car merely because B fully implements BI.

In other words, the matching rule here is:

1. first check whether the concrete type fully covers InterfaceInfo[target]
2. only if it does, a slot on that type is eligible to satisfy the interface method demand
3. then check whether that slot's own MethodSig actually matches the current demand

So the real keep condition is not "method name and method type happen to match." It is:

the concrete type fully implements the target interface
AND
the slot corresponds exactly to the currently demanded interface method

Example 3: MethodByName Produces Exact Name Demands

Consider:

func lookup(v any) {
	_, _ = reflect.TypeOf(v).MethodByName("ServeHTTP")
}

If "ServeHTTP" is a compile-time constant, then:

1. the compiler emits UseNamedMethod(owner, "ServeHTTP")
2. once owner becomes reachable
3. every slot named ServeHTTP on types in UsedInIface must be kept

This is more precise than conservative reflection mode, because:

1. the demand is triggered by an exact name
2. rather than "all exported methods must be kept"

Example 4: Conservative Reflection Mode Expands the Live Set

Consider:

func valueByIndex(v any) {
	_ = reflect.ValueOf(v).Method(0)
}

Here the target method name cannot be known statically at compile time, so:

1. the compiler emits ReflectMethod(owner)
2. once owner becomes reachable, the analysis enters conservative reflection mode
3. for all types in UsedInIface, slots corresponding to exported methods must be kept

This is a conservative but necessary degradation.

Example 5: UsedInIface Propagates Along Child Types

Consider a type Outer whose runtime type data can continue to reach a child type Inner.

If:

1. Outer enters UsedInIface

Then:

1. Inner must also enter UsedInIface
2. otherwise methods on Inner that may later be reached via reflection or further interface conversion would be missed

Therefore, TypeChildren exists not for ordinary graph traversal, but to express this semantic propagation explicitly.

Current Realization

In the current branch, the realization is split into two stages:

1. analysis stage
2. rewrite stage

Analysis Stage

The goal of the analysis stage is to aggregate whole-program input and compute:

type symbol -> live method indexes

In the current branch, the analyzer input is not produced by one standalone file. It is aggregated during the build stage from two sources.

The first source is the llgo.xxx named metadata explicitly emitted by ssa/cl during per-package compilation.

Among them, llgo.interfaceinfo and llgo.methodinfo are currently encoded as "one method / one slot per row" rather than packing a whole group into one row. This makes parsing in graph more direct.

1. llgo.useiface
   row shape: { owner, concrete type }
2. llgo.useifacemethod
   row shape: { owner, interface type, normalized method name, mtype }
3. llgo.interfaceinfo
   row shape: { interface type, method name, mtype }
4. llgo.methodinfo
   row shape: { concrete type, index, method name, mtype, ifn, tfn }
   if a type has no methods, it emits no llgo.methodinfo rows
5. llgo.usenamedmethod
   row shape: { owner, normalized method name }
6. llgo.reflectmethod
   row shape: { owner }

These metadata express interface conversions, interface method demands, complete interface method sets, concrete-type method slots, name-based method lookup, and conservative reflection mode.

The second source is not emitted through llgo.xxx. It is extracted directly by the build stage from ordinary contents of each package's llvm.Module:

1. OrdinaryEdges
   scanned from ordinary LLVM IR contents such as function bodies, global initializers, and constant operands
2. TypeChildren
   scanned recursively from ABI type globals in each package

After collecting all package llvm.Module values, the build stage merges those two parts into one whole-program WholeProgramInfo and then feeds it into the liveness algorithm defined above.

Rewrite Stage

Once the analysis stage finishes, the answer to "which methods must be kept" is already stable.
The rewrite stage no longer performs any semantic reasoning. It only turns that answer into final link artifacts.

Concretely, the rewrite stage needs to:

1. find all ABI types that need pruning
2. copy each original weak definition into a new strong definition
3. prune its method-table array according to Result[type]
4. place the new definitions into a separate module
5. override the original weak definitions with the strong ones during final linking

This split has three direct benefits:

1. the algorithm definition stays clean, and the analysis result does not get mixed with rewrite engineering
2. the analyzer can be tested independently, without depending on strong-symbol generation
3. the rewrite stage can be validated independently as long as Result is correct

---

package semantic metadata emit #1728

[luoliwoshang]

Proposal: LLGo 引入 Go linktime-like 的不可达方法清除

状态

• 状态：Proposed
• 性质：定案方向提案，定义 LLGo 后续应采用的语义方向
• 当前关联工作：PR #1618 主要用于验证 proposal 中的局部语义与流水线，不等同于 proposal 本身

摘要

本提案定义 LLGo 的正式 deadcode 架构方向：在支持的可执行构建路径中，引入一种 Go linktime-like 的 whole-program deadcode 机制，重点解决普通链接器无法表达的 Go 语义依赖，尤其是：

• 类型元数据中的方法表引用
• 接口转换与接口方法调用
• MethodByName 一类按名字触发的方法保活
• 反射导致的保守导出方法保活

本文当前只讨论 不可达方法裁剪。
像 SCCP、普通 DCE、控制流上的不可达分支删除、常量传播这类通用优化，不属于本提案的讨论范围。

提案的核心不是“复刻 Go linker 的对象格式”，而是：

• 语义目标向 Go linker 对齐
• 由 LLGo 自己定义一套可表达 Go 语义依赖的链接语义模型
• 将“不可达方法清除”定义为 LLGo 正式链接语义的一部分，而不是可有可无的附加优化
• 在支持的 exe 构建路径上，最终作为默认链接语义启用，而不是长期停留在实验开关后面

正式语义方向包含以下核心要素：

• 计算 whole-program 可达性
• 将普通 call/ref 与 Go 语义 semantic reloc 分层建模
• 找出必须保留的方法条目
• 确保不可达方法不会仅因类型元数据可达而被错误保活

目标

• 为 exe 构建模式提供 whole-program 的 Go 语义可达性分析。
• 对齐 Go linker deadcode 的关键语义，而不是仅依赖普通 call/ref。
• 允许接口、反射、按名字查找方法等场景在“保守正确”的前提下参与方法保活。
• 将“不可达方法清除”纳入 LLGo 的正式链接语义，而不是一次性优化实验。
• 在支持的 exe 构建路径上最终默认启用该能力，并保留 -nodce 作为逃生开关。
• 将讨论范围明确限定在“不可达方法裁剪”，不扩展到通用 IR 优化。

非目标

• 不要求 1:1 复刻 Go cmd/link 的 object 格式、loader、或内部数据结构。
• 不要求在本提案落地时同时覆盖 c-archive / c-shared / plugin / shared library 的全部 build mode 细节。
• 不要求在 proposal 中预先锁定每张 metadata table 的低层编码细节、回写策略或内部 pass 组织方式。
• 不讨论 SCCP、普通 DCE、控制流不可达分支删除、常量传播等通用优化问题。

背景

普通链接器对 direct call / direct ref 工作良好，但对 Go 特有语义不够。

这里讨论的问题也不是“通用优化做得不够”。
即便已经有 SCCP、普通 DCE 或其他 IR 级别清理，ABI type 方法表导致的保活问题依然单独存在。

典型问题是 ABI type 中的方法表。一个具体类型如果带有方法集，其类型描述符中通常会间接或直接出现：

• 方法名
• 方法函数类型
• Ifn
• Tfn

对普通链接器来说，这些都是“真实引用”。一旦类型描述符可达，方法体就容易被整体保活，导致：

• 从未通过接口动态调用的方法也无法被裁掉
• 仅仅因为类型元数据可达，就把全部方法链路带进最终二进制

Go linker 之所以能做得更细，是因为它不把这类关系简单视作普通强引用，而是引入了一套 deadcode-aware 的标记与状态机。

Go linker 的可借鉴语义

基于本地 GOROOT/src/cmd/link/internal/ld/deadcode.go 的阅读，可以把 Go linker 的关键点概括为：

根集合

Go linker 的 deadcode 从一组入口根出发，例如：

• main / main.main
• main..inittask
• runtime.unreachableMethod
• 动态导出符号
• wasm export

也就是说，deadcode 不是“扫描所有定义”，而是“从入口根向外做 flood”。

特殊状态

Go linker 在 reachability 之外还维护了额外状态：

• UsedInIface
• reflectSeen
• ifaceMethod
• genericIfaceMethod
• markableMethods

这里最关键的是：

• 类型是否 UsedInIface
• 哪些接口方法签名已经被真正用到
• 是否出现了无法静态精确分析的反射方法查找

特殊 relocation 与 attr

Go linker 不只看普通引用，还特别处理：

• R_USEIFACE
• R_USEIFACEMETHOD
• R_USENAMEDMETHOD
• R_METHODOFF

其中：

• R_USEIFACE 表示“某个具体类型被当成接口使用过”
• R_USEIFACEMETHOD 表示“某个接口方法槽位被调用过”
• R_USENAMEDMETHOD 表示“某个方法名被按名字请求过”
• R_METHODOFF 表示“类型方法表中的方法条目”

这类 relocation 的共同点，不是“像普通引用一样直接表达可达边”，而是都附着在某个 owner 符号上，作为 deadcode 分析要消费的语义标记。它们可以进一步分成两类：

• 需求侧标记：R_USEIFACE、R_USEIFACEMETHOD、R_USENAMEDMETHOD
• 供给侧标记：R_METHODOFF

在普通代码路径里，需求侧标记的 owner 往往就是当前函数，因此直觉上可以把它们理解为：

• “这个函数中发生过哪些与接口/按名方法相关的语义事件”
• “如果这个函数可达，后续 deadcode 状态机需要据此更新哪些状态”

其中，R_USEIFACE 表达的是：如果该 owner 可达，那么其 target，也就是对应的具体 type symbol，会被视为在这段代码路径中曾被转换成接口使用过。

proposal 需要强调两个边界：

• 它标记的不是“该函数里出现过的所有类型”，而只是那些对 deadcode 的接口语义有意义的类型
• 它表达的也不是“该函数普通引用了这个 type”，而是“如果该 owner 可达，则 target type 应进入 UsedInIface 语义状态”

因此，R_USEIFACE 以及同类需求侧标记，更接近语义事件，而不是普通引用边。对 linker 来说，它们的作用不是立即保活某个方法体，而是把对应的类型、方法名或接口方法需求纳入后续方法裁剪所需的状态机中。

一个典型的 Go 例子是：

type I interface{ M() }
type T struct{}

func (T) M() {}

func f() {
	var x I = T{}
	_ = x
}

在这段代码里，R_USEIFACE 可以近似理解成下面这条语义标记：

• owner: f 对应的函数符号
• target: T 对应的 type symbol
• meaning: 如果 f 可达，则 T 应被视为在 f 的代码路径中曾被转换成接口使用过

它表达的不是“f 普通引用了 T 的全部方法”，而是“f 这条可达路径把 T 带入了接口语义域”，因此 T 后续需要进入接口语义相关的方法裁剪流程。

R_USEIFACEMETHOD 的语义与之类似，但它描述的不是“哪个具体类型进入了接口语义”，而是“哪个接口方法需求被真正使用过”。

一个典型的 Go 例子是：

type I interface{ M() }

func f(x I) {
	x.M()
}

在这段代码里，R_USEIFACEMETHOD 可以近似理解成下面这条语义标记：

• owner: f 对应的函数符号
• target: I 对应的接口 type symbol
• meaning: 如果 f 可达，则 I 上的某个方法需求被真正使用过

需要特别说明的是，这里的 target 是接口类型，不是运行时的某个 iface 值。Go 的原始表示会继续依赖接口类型描述符中的方法槽偏移，linker 在消费这条 relocation 时，再从该接口类型的布局中解码出方法名与方法类型，并将其归一化为后续匹配使用的方法签名需求。

R_USENAMEDMETHOD 则更进一步。它描述的不是某个接口方法槽位，而是“某个方法名被按名字请求过”。

一个典型的 Go 例子是：

func f(v any) {
	_, _ = reflect.TypeOf(v).MethodByName("M")
}

在这段代码里，R_USENAMEDMETHOD 可以近似理解成下面这条语义标记：

• owner: f 对应的函数符号
• target: 方法名 "M" 对应的名字符号
• meaning: 如果 f 可达，则后续方法裁剪需要把名为 "M" 的方法视为已被按名字请求过

与 R_USEIFACEMETHOD 相比，R_USENAMEDMETHOD 不直接提供方法签名，而是只提供名字层面的需求，因此它天然比接口方法匹配更保守。Go 在一些无法稳定获得完整方法签名的场景下，也会退化到这一层语义。

R_METHODOFF 与前三者不同。它不描述“哪里产生了方法需求”，而是描述“某个具体类型提供了哪些候选方法项”。

一个典型的 Go 例子是：

type T struct{}

func (T) M() {}
func (T) N(int) {}

对这类带方法集的具体类型，Go 会把方法表写进 T 的类型描述符中。对于 deadcode 来说，可以把 R_METHODOFF 近似理解成下面这类供给侧信息：

• owner: T 对应的 concrete type symbol
• candidates: T 的方法候选集合
• meaning: 如果 T 已进入接口相关分析范围，那么这些候选方法项可以参与后续匹配

在 Go 当前实现中，一个方法项会物化成 3 个连续的 R_METHODOFF relocation，分别对应 mtyp、ifn、tfn。这种表示与 Go 当前的 runtime.Method 布局和链接期写回路径直接耦合，因此 linker 会把这 3 条连续 relocation 视为同一个 methodref。

但从语义上看，deadcode 在做“方法是否命中需求”的判断时，真正使用的主键是：

• name
• mtyp

其中，mtyp 表示不带 receiver 的方法类型。ifn 和 tfn 更像是在候选方法命中后需要一并保留或回写的实现载荷，而不是决定方法匹配是否成立的分析主键。

这一区分对 LLGo 很重要：proposal 需要借鉴 Go 的语义，但不必照搬 Go 当前 object/layout 中“每个方法项对应 3 个连续 relocation”的低层表示。

除了这些 relocation，Go linker 还依赖一个专门的语义 attr：AttrReflectMethod。

它描述的不是某个精确的方法需求，而是：某个可达函数中出现了无法静态精确分析的反射方法查找。

一个典型的 Go 例子是：

func f(v any, name string) {
	_, _ = reflect.TypeOf(v).MethodByName(name)
}

在这段代码里，编译器无法在编译期确定被请求的方法名，因此不会产生精确的 R_USENAMEDMETHOD，而是给 f 对应的函数符号打上 AttrReflectMethod。它可以近似理解成下面这条语义标记：

• owner: f 对应的函数符号
• meaning: 如果 f 可达，则方法裁剪不能再依赖静态精确匹配，而应转入保守策略

对 Go 来说，这个 attr 的效果是：一旦在 reachable 路径上观察到它，linker 就会放弃继续做精确的反射方法名分析。对当前非 dynlink 的基线语义而言，应当保守保留 reachable type 上可能经由反射观察到的导出方法；若处于 dynlink / plugin / shared 一类无法静态穷尽最终使用方的构建模式，则保守边界再进一步放宽。

方法保活不是一次 flood 就结束

Go linker 的方法保活逻辑不是“看到类型就保留所有方法”，而是：

1. flood 收集普通可达性与语义状态
2. 从可达类型里找出“候选方法”
3. 将候选方法与接口方法需求、名字需求、反射保守条件进行匹配
4. 只把匹配成功的方法真正标记可达
5. 若产生了新可达符号，再继续 flood，直到收敛

这个“状态收集 + 候选筛选 + 迭代收敛”的结构，是本提案最值得借鉴的部分。

本提案的定位

本提案不是在讨论“LLGo 是否要做这件事”，而是在定义：

• LLGo 的 Go 风格 deadcode 最终应采用什么语义模型
• LLGo 的正式链接语义应满足什么性质
• 当前验证 PR 与最终架构之间是什么关系

换句话说：

• PR 可以是验证性的
• proposal 必须是定案方向

因此，本文的重点不是分阶段实现细节，而是先定义最终应成立的语义边界与分析模型。

从 Go linker 到 LLGo 的对应关系

1. Go：从 roots 沿普通 reloc 做 flood

Go linker 的 deadcode 基础，不是“先枚举所有定义”，而是：

• 从入口 roots 出发
• 沿普通 relocation 扩展可达性
• 把得到的 reachable 结果作为后续方法筛选的基础

因此，对 LLGo 来说，ordinary call/ref 直接基于当前程序内容来分析，是合理而且自然的对应关系。
在 LLVM 世界里，这部分信息就应当来自当前真实存在的 call/ref，而不是再额外复制到另一套 semantic metadata 里。

2. Go：特殊语义靠特殊 reloc，不等于普通可达边

Go linker 并不是把所有 relocation 一视同仁地 flood。
像 R_USEIFACE、R_USEIFACEMETHOD、R_USENAMEDMETHOD、R_METHODOFF 这些特殊 relocation，本质上是在：

• 改变分析状态
• 收集候选方法
• 为后续的方法筛选提供语义上下文

因此，对 LLGo 来说也应保持同样的边界：

• ordinary call/ref 表示普通可达性
• semantic metadata 只承载普通引用关系无法充分表达的 Go 语义边

3. Go：方法裁剪是状态机 + fixpoint，不是单次遍历

Go linker 的方法保活不是“flood 一遍就结束”，而是：

1. 先跑普通可达性
2. 再根据接口、反射、按名字查找等语义收集状态
3. 从可达类型的方法里选出真正需要保留的方法
4. 若产生新的 reachable，再继续 flood，直到收敛

因此，对 LLGo 来说，ordinary call/ref 和 semantic 信息虽然在记录层应当分离，但在分析层必须合流，进入同一个 whole-program 图、同一个状态机和同一个 fixpoint 过程。

4. 对 LLGo 的直接设计结论

综合上面的对应关系，本提案主张 LLGo 采用下面这组原则：

• 记录层分离
• 分析层合流

也就是：

• ordinary call/ref 的权威来源是当前程序里已经显式存在的引用关系
• semantic metadata 只记录 Go 特有的语义边
• 但两者在方法裁剪分析时必须汇总到同一个图里统一消费

这样设计的原因是，ordinary call/ref 本来就是可导出的显式信息，重复塞进 metadata 会制造双份真相。
一旦后续发生方法裁剪、函数删除或初始化器改写，真实程序内容里的 ordinary edge 和 metadata 中的副本就都需要同步删减；这会把“可达性分析”问题变成“维护两套引用事实一致性”的问题。相反，如果 ordinary call/ref 始终以当前程序内容为准，而 metadata 只记录额外语义边，那么每次分析都可以直接从当前状态获取普通边，避免 semantic edge 与 real edge 互相污染。

除此之外，尽量基于当前 LLVM symbols 本身来做分析，还有几个直接优势：

• 这一路径本来就更贴近 Go deadcode 的基本形态，即“从真实可达符号出发，沿当前程序中的引用关系做 flood”，而不是先人为抽象出一套脱离程序实体的完整语义图
• 这也更符合编译器逐步 lowering 的处理方式：随着前端语义一步步落到具体的函数、全局、stub、wrapper 和类型符号上，分析可以直接消费这些已经落地的程序实体，而不必在 lowering 之外再人为重建一套平行语义表示
• LLGo 因而只需要补充分析真正缺失的 Go 语义信息，而不必把本已存在于 IR 中的关系再次编码一遍；像间接调用 stub、wrapper 或其他实际出现在当前模块中的辅助符号，也可以直接作为当前程序内容的一部分参与分析，而不需要为它们再设计额外的专门语义

LLGo 的语义模型

1. 图模型

LLGo 的方法裁剪分析需要统一消费两类信息：

• 当前 LLVM module 中已经显式存在的 ordinary call/ref
• semantic markers
  • useiface
  • useifacemethod
  • usenamedmethod
  • reflectmethod
  • methodoff

其中：

• ordinary call/ref 负责表达 LLVM module 层面的普通可达性
• semantic markers 负责表达 Go 特有的链接语义，既可以产生额外的语义边，也可以直接改变分析状态

这两类信息在分析时必须汇总到最终参与链接的 whole-program 全局调用图 / 可达性图 中统一消费，而不是由每个模块各自独立地完成局部方法裁剪。

这些 semantic markers 在模块中的承载形式，proposal 推荐采用 module-level named metadata tables，而不是散挂到各个 owner 上，或再额外生成一份独立 summary 文件。按当前语义边界，比较自然的分表方式例如：

• !llgo.useiface
• !llgo.useifacemethod
• !llgo.usenamedmethod
• !llgo.methodoff
• !llgo.reflectmethod

这些表在语义上分别承载：

• !llgo.useiface：owner + concrete type target
• !llgo.useifacemethod：owner + interface type target + method name + method signature id
• !llgo.usenamedmethod：owner + normalized method name
• !llgo.methodoff：concrete type owner + method index + normalized method name + mtyp
• !llgo.reflectmethod：owner

这样设计的原因是：

• 每类 marker 的 schema 更清晰，不需要在一张“大一统总表”里混合多种结构
• 分析阶段更容易按种类统一扫描和汇总
• 仍然保持这些语义信息和 llvm.Module 同生共存，符合 LLVM 的编译姿势

当前 proposal 对这些语义 marker 的边界可进一步整理为三类：

需求侧 marker

• useiface
  Go 对应：R_USEIFACE。
  owner：需求侧 symbol，普通路径里通常是当前函数。
  target：具体 type symbol。
  语义：若该 owner 可达，则该 target type 进入接口可观察语义，而不应退化成普通 directref。
  LLGo 推荐表示：owner + concrete type target。

• useifacemethod
  Go 对应：R_USEIFACEMETHOD。
  owner：需求侧 symbol，普通路径里通常是当前函数。
  target：接口 type symbol，而不是运行时 iface 值。
  其他信息：Go 当前实现还会借助接口方法槽位信息来解码方法需求。
  语义：若该 owner 可达，则该接口类型上的某个方法需求被真正使用过。
  LLGo 推荐表示：owner + interface type target + method name + method signature id。

• usenamedmethod
  Go 对应：R_USENAMEDMETHOD。
  owner：需求侧 symbol，普通路径里通常是当前函数。
  target：按名字请求的方法名；在 LLGo 里应使用规范化后的方法名。
  语义：若该 owner 可达，则该方法名已被按名字请求过。
  LLGo 推荐表示：owner + normalized method name。

供给侧 marker

• methodoff
  Go 对应：R_METHODOFF。
  owner：concrete type symbol。
  target：从语义上看不是单个 target symbol，而是该 concrete type 上的一组方法候选。
  其他信息：Go 当前实现里，一个方法项会物化成与 runtime.Method 布局耦合的 3 个连续 relocation；LLGo 不需要把这一低层表示上升为语义约束。
  语义：当该 concrete type 已进入接口相关分析范围时，这些方法候选可参与后续方法匹配。
  LLGo 推荐表示：owner + method candidates，其中每个 candidate 的分析身份由 {name, mtyp} 决定，ifn/tfn 作为命中后回写或保活时需要关联的实现载荷。
  额外约束：若分析结果最终以 (type, method index) 形式输出，则这里的 method index 必须就是最终 abi.Method 表中的 canonical slot index；分析阶段与回写阶段必须基于同一套方法顺序解释它，不能在两阶段之间重新排序或重编号。

保守标记与传播规则

• reflectmethod
  Go 对应：AttrReflectMethod。
  owner：需求侧 symbol，普通路径里通常是当前函数。
  target：无精确 target。
  语义：若该 owner 可达，则分析应放弃继续做精确的反射方法名匹配，并转入保守保留策略。
  LLGo 推荐表示：owner 上的保守语义标记。

• UsedInIface 下的 child-type 传播
  对 Go 而言，从一个 UsedInIface type 到其 child type 的传播并不是一个单独的前端 marker，而是分析过程中的传播规则：当某个 type 已进入 UsedInIface 状态后，应沿其 type descriptor 中对其他 Go type 的引用继续闭包传播这一状态。LLGo 也应采用同样的规则，而不必为此额外生成与前述几类并列的独立 metadata。

进一步说：

• useifacemethod 中的接口 type target 仍然应保留，因为它保留了“这条需求来自哪个接口类型”的语义上下文；但后续方法匹配的主依据，应是 method name + method signature，而不是某个低层布局偏移。
• methodoff 在 Go 中虽然表现为与 runtime.Method 布局耦合的 3 个连续 relocation，但 LLGo 的语义模型不应把这一点上升为必须复刻的结构约束；proposal 只要求它能稳定表达“某个 concrete type 拥有哪些方法候选，以及这些候选如何与需求侧方法信息匹配”。
• reflectmethod 的目标不是提供新的精确匹配键，而是在必要时明确触发“保守但正确”的退化路径。

方法匹配时的方法身份规范化也应与 LLGo 当前 runtime 语义保持一致：

• 导出方法使用其原始方法名
• 未导出方法需要带上包路径，以 abi.FullName(pkg, name) 的规范化形式参与匹配
• 方法类型使用不带 receiver 的函数类型标识，也就是当前 ABI 中的 _llgo_func$...

因此，对 LLGo 来说，name + mtyp 中的 name 并不是简单的源码字面量方法名，而是已经过导出性处理后的规范化名字；这样才能与当前 runtime 中 Name_ + Mtyp_/Typ_ 的匹配规则保持一致，避免不同包中的同名未导出方法在 deadcode 分析阶段被错误合并。

2. 节点与状态

分析节点至少包括：

• function symbol
• global symbol
• ABI type symbol
• method entry related symbol

除普通的 Reachable 外，分析过程还需要维护与 Go linker deadcode 类似的额外语义状态，例如：

• 哪些 concrete type 已进入接口可观察语义
• 哪些接口方法需求或按名方法需求已经出现
• 是否已经进入反射相关的保守保留路径
• 哪些方法候选最终被判定为需要保留

其中 ABI type 节点是首要关注对象，因为不可达方法清除主要围绕方法表展开。

3. 根集合

正式语义首先覆盖可执行构建：

• host target：main / _start
• wasm 无 _start 路径：__main_argc_argv

后续可以扩展：

• dynamic export
• wasm export
• plugin / shared roots

4. 分析过程

本提案在分析过程上应尽可能参考 Go linker deadcode 的整体算法；这里仅给出高层语义描述，不试图预先锁定内部实现细节：

1. 从 roots 开始做第一轮 flood
2. ordinary call/ref 直接扩展 reachable
3. semantic markers 改变语义状态，或生成候选方法
4. 根据已经收集到的方法需求、按名方法需求以及反射保守条件，从候选方法中筛选真正应保留的方法
5. 如果发现了新的 reachable，再继续 flood，直到收敛

换句话说，本 proposal 要求的是“分析语义与 Go 的收敛过程尽量对齐”，而不是要求 LLGo 必须逐行复刻 Go 当前的内部组织方式。

就当前 LLGo 的整体 pipeline 而言，可以将其概括为：

1. 在 llssa lowering 阶段，将 Go 语义所需的 marker 信息发出到各个 llvm.Module
2. 在最终连接前，汇总所有参与链接的 module，做一次 whole-program 的统一可达性分析
3. 输出 deadcode 分析结果，例如 (type, method index) 这一类后续可直接消费的结果形式
4. 再由后续 IR 回写阶段根据分析结果修改类型元数据

这条 pipeline 与本 proposal 的语义边界是一致的：前端/SSA 阶段负责把 Go 特有语义补充进 module，连接前分析阶段负责统一求解 whole-program 可达性，而回写阶段只负责把已经确定的分析结果落到 IR 上。

最终分析架构可以概括为：

flowchart TD
    A["llssa lowering"] --> B["Per-module LLVM IR"]
    B --> C["Ordinary call/ref<br/>from current LLVM module"]
    B --> D["Module-level named metadata tables<br/>useiface / useifacemethod / usenamedmethod / methodoff / reflectmethod"]
    C --> E["Whole-program global reachability graph"]
    D --> E
    E --> F["Go-like deadcode analysis<br/>flood + semantic state + method candidate filtering"]
    F --> G["Pass output:<br/>(concrete type, method index)"]
    G --> H["IR rewrite / abi.Type override"]
    H --> I["Final codegen / link"]

Loading

其中，第 1 步中提到的 marker 信息，proposal 主张应落在各个 llvm.Module 自身携带的 metadata 中，而不是额外生成一份单独的 summary 文件。这样设计的原因是：

• 它更符合 LLVM 的编译姿势，即语义信息随着 module 一起被逐步 lowering、传递和消费
• 它避免再引入一套脱离 module 本体的平行摘要格式
• 它也更符合本 proposal 一贯的边界：ordinary call/ref 来自当前 module，本提案只为 Go 特有语义补充最必要的额外信息

更具体地说，本 proposal 更倾向于把这些信息放在 module-level named metadata tables 中，而不是写成一张模块外部 summary 文件；前者既能保持 schema 清晰，也能让连接前的 whole-program 分析直接从各个 module 读取并汇总这些语义标记。

5. 保守边界

下列场景在当前 proposal 中以 Go linker 的保守语义作为基线：

• MethodByName 的参数不是编译期常量
• 动态反射方法查找，例如 reflect.Value.Method(i)、reflect.Type.Method(i) 一类无法静态确定方法名的访问
• plugin / shared / dynlink 等无法静态穷尽最终使用方的构建模式

对这些场景，本提案要求的语义是：

• 一旦无法静态精确确定目标方法，就放弃精确方法筛选
• 对反射相关的保守路径，当前基线明确为：保留 reachable type 上可能经由反射观察到的导出方法
• 对 dynlink / plugin / shared 一类无法静态穷尽最终使用方的构建模式，再按更保守的边界放宽

更具体地说：

• MethodByName 参数为编译期常量时，可以按名字做精确匹配
• MethodByName 参数不是编译期常量时，当前基线应像 Go 一样放弃按名字精确裁剪
• 发现动态反射方法查找时，当前基线应像 Go 一样放弃静态方法名分析，并保守保留 reachable type 上可能经由反射观察到的导出方法
• 对 plugin / shared / dynlink，一旦当前编译单元无法确定最终谁会使用这些类型或方法，就应在上述基线之上进一步按更保守的边界保留，而不是继续尝试激进裁剪

需要特别说明的是：

• MethodByName 的非常量参数
• 动态反射方法查找

这两类情况代表的是 Go 当前实现的保守边界，不必被理解为 LLGo 的永久上限。
只要后续能够提出在语义上可证明正确的更精细分析，LLGo 可以在保持兼容性的前提下扩展这两类场景的裁剪精度；但在本 proposal 采纳时，基线仍以 Go 当前的保守行为为准。

6. 语义结果

本提案要求分析结果至少满足一个条件：

• 不可达方法不得再仅仅因为类型元数据可达而被视为必须保留
• 不可达方法一旦仍可经由方法表被观察到，其行为应回写到 runtime.unreachableMethod，与 Go 保持一致

换句话说，proposal 关心的是“哪些方法在最终语义上必须存活”，以及“不可达方法在保留方法表形状时应表现成什么语义”。在这一点上，基线应与 Go 一致，而不是让被裁掉的方法槽位落成未定义行为。

对 LLGo 来说，这个分析 pass 的输出可以进一步收敛为：

• 哪些 concrete type 进入了方法裁剪范围
• 以及这些 concrete type 上哪些 method index 被判定为可达

也就是说，分析结果不必直接表现成低层函数指针集合；输出为“某个 concrete type 的第几个 method slot 可达”即可。这样设计的好处是：

• 它与当前实验性 PR 的验证方向一致
• 它与后续 IR 回写方式解耦
• 不论最终采用复制 abi.Type 还是直接改写 abi.Method，都可以统一地按 method index 回写

因此，本 proposal 可以把“输出 (type, method index) 集合”视为 deadcode 分析 pass 的一个合理目标形式。

这里需要额外强调的是：method index 不是一个临时分析编号，而必须与最终 abi.Method 表中的 canonical slot index 保持一致。也就是说，deadcode 分析、IR 回写、override 路径以及未来 ThinLTO 前回写路径，必须共享同一套方法槽顺序；否则即使分析结果正确，后续也可能把错误的方法槽位裁掉。

7. 可接受的回写方向

本 proposal 的重点首先是分析出 Go-like 的不可达方法集合。一旦 whole-program 分析已经稳定得出“哪些方法可达、哪些方法不可达”，后续在 IR 层面如何把这一结果回写到类型元数据，属于工程落地问题，而不是 proposal 的核心语义难点。

在不改变上述语义目标的前提下，当前可以接受两类工程回写路线：

• 复制并重建裁剪后的 abi.Type 常量定义
• 在 whole-program IR 的后期阶段，直接重写指定 abi.Method 的 IFn/TFn

这两条路线的共同点是：

• deadcode 先决定“哪些方法需要保留”
• 再把结果回写到类型元数据里
• 让后续优化和代码生成看到的，已经是裁剪后的方法表
• 对不可达方法，其回写目标应当是 runtime.unreachableMethod，以保持与 Go 一致的 fail-fast 语义

其中：

• 复制裁剪后的 abi.Type 更适合作为当前工程阶段的过渡方案，落地更稳；它可以先在单独 IR 中生成裁剪后的类型定义，以兼容当前的两种构建路径
• 在 whole-program IR 后期直接改 abi.Method 常量，更贴近长期方向，也更容易与未来 ThinLTO 路径对齐

如果后续引入 ThinLTO，这一回写动作也仍然可以放在进入 ThinLTO 编译流程之前完成。换句话说，ThinLTO 的引入不会改变 proposal 的核心语义要求，只会改变“分析结果最终在何时写回 IR”这一工程落点。

当前阶段，可以先采用 PR #1618 中已经验证过的回写路线：根据 deadcode 分析输出的 (type, method index) 结果，在单独 IR 中生成裁剪后的 abi.Type/override 定义，并据此清理不可达方法槽位中的 IFn/TFn。这一路线并不是 proposal 的唯一长期实现，但作为当前工程阶段的已验证方案，它足以承接前述分析结果，并兼容现有构建路径。

因此，proposal 在语义上要求“必须存在方法表回写”，但不要求当前版本立即锁死这两条路线中的某一种。

与当前验证 PR 的关系

当前 PR 的价值在于验证 proposal 中部分语义假设的可行性。

• proposal 定义的是 LLGo 应收敛到的正式实现方向
• 当前 PR 只是这个方向上的一次 验证材料
• proposal 的成立不应绑定到某一个验证 PR 的具体写法

需要明确避免的设计

不建议把 semantic reloc 伪装成 ordinary directref

如果 ABI type global initializer 直接把所有方法体都表现为普通 directref，会带来两个后果：

• 方法筛选逻辑失效
• 死方法可能在 flood 早期就把更多符号保活

这与本提案的目标相冲突，因此应被明确排除。

不建议把 ordinary call/ref 再重复记录进 semantic metadata

这样做会带来三个直接问题：

• ordinary edge 会在程序本体和 metadata 中同时存在，形成双份真相
• 一旦发生裁剪或改写，两份信息都需要同步维护
• ordinary edge 与 semantic edge 混装后，后续分析更容易误把普通可达性和 Go 语义状态混为一谈

因此，proposal 的推荐边界应当是：

• ordinary call/ref 始终从当前程序内容直接获取
• metadata 只承载 Go 语义边
• 但两者在分析时应汇总到同一个 whole-program 图里统一消费

结论

本提案主张 LLGo 正式引入一种 Go linktime-like 的不可达方法清除机制，其关键不在于复刻 Go linker 的 object 实现，而在于吸收以下语义：

• ordinary reachability 不足以描述 Go 方法保活
• semantic reloc 需要单独建模
• UsedInIface / interface method / named method / reflect state 需要参与 fixpoint 分析
• 不可达方法不能仅因类型元数据可达而被整体保活

这一定义只覆盖“方法是否需要保留”的语义问题，不覆盖 SCCP、普通 DCE 或一般控制流裁剪。

当前验证 PR 证明了这个方向具备可行性，但 proposal 定义的正式路线应当是：

• LLGo 应当把这种 Go linktime-like deadcode 机制作为正式架构方向
• 后续实现围绕本文定义的语义模型、graph 分层和状态机展开

这样既定义了 LLGo 的最终语义方向，也避免了 proposal 过早绑定到某一种内部实现。

[luoliwoshang]

状态

• 状态：Proposed
• 范围：定义 LLGo 在可执行构建路径上的链接期语义方法裁剪方案
• 当前落地范围：优先覆盖 exe 构建路径
• 背景：方案受 Go 链接期 deadcode 思路启发，但本文只定义 LLGo 自己的语义模型、输入契约与实现方向

摘要

LLGo 需要一套专门面向 Go 语义的链接期方法裁剪机制。当前普通的 call/ref reachability 只能看到直接符号引用，但 Go 中方法是否必须保留，往往还取决于接口转换、接口方法调用、按名字取方法以及反射等额外语义，因此仅靠普通 DCE 无法正确表达“哪些类型进入了动态分派语义域、哪些方法槽位真的被需求”。

本文提出的方案是：在 whole-program 视角下显式建模这些 Go 语义，并将其与普通可达性放入同一套多轮传播分析中，最终稳定产出 type symbol -> live method indexes。对于接口方法需求，判定条件也不再只是“方法名 + 方法类型”匹配，而是进一步要求具体类型完整实现目标接口，从而避免把实际上并不满足接口的结构体方法误保活。

这不是单纯依赖普通引用图就能解决的问题，而是需要在链接期额外建模 Go 语义并进行专门的方法判活分析。

问题定义

为什么普通 gc-sections、普通链接器 DCE、普通 IR DCE 不够

普通链接器和普通 IR DCE 依赖的是显式引用关系：

• 某个函数调用了另一个函数
• 某个全局常量引用了另一个全局符号
• 某个 initializer 里出现了对某个符号的普通引用

这套模型对 Go 不够，因为 Go 的方法调用能力本身不是纯粹的 direct reference 模型。

在 Go 里，一个方法是否必须保留，往往取决于以下语义事件：

1. 某个具体类型是否会进入接口动态分派世界。
2. 某个接口上的某个方法槽位是否真正被调用过。
3. 某个方法名是否通过 MethodByName 被按名字请求。
4. 是否出现了必须进入保守模式的反射调用。

这些事件如果不由编译器显式编码出来，链接阶段就只能看到一堆“类型常量引用了方法符号”，最终结果只能是：

• 只要类型描述符活着，方法很容易一起活下来。
• 无法区分“方法表里列出来”和“这个方法真的会被动态调用”。
• 无法在链接期精确删除一部分方法而保留另一部分方法。

一个最小化例子

可以先看下面这个简化后的 Go 程序：

package main

type Reader interface {
	Read([]byte) (int, error)
}

type Writer interface {
	Write([]byte) (int, error)
}

type stringReader struct{}

func (*stringReader) Len() int                       { return 0 }
func (*stringReader) Read([]byte) (int, error)      { return 0, nil }
func (*stringReader) Close() error                  { return nil }
func (*stringReader) WriteTo(Writer) (int64, error) { return 0, nil }

func ReadAll(r Reader) {
	_, _ = r.Read(nil)
}

func main() {
	ReadAll(&stringReader{})
}

这个程序的语义很简单：

1. 接口 Reader 只要求一个方法：Read([]byte) (int, error)。
2. 具体类型 stringReader 却还带了别的方法，例如 Len、Close、WriteTo。
3. 程序里会把 stringReader 装箱成 Reader，并通过接口去调用 Read。

这里需要先强调一点：这并不是编译器额外塞进去的一堆“无关引用”，而是 Go 运行时本来就需要的能力。

当一个具体类型可能参与接口动态调用时，运行时必须能回答下面这些问题：

1. 这个具体类型有哪些方法。
2. 每个方法的名字是什么。
3. 每个方法的类型签名是什么。
4. 通过接口调用时应该跳到哪个函数入口。
5. 通过普通方法入口调用时应该跳到哪个函数入口。

因此，在带方法集的类型上，abi.Type / abi.UncommonType 本来就会带一张 abi.Method 表。
这张表里的每一项都会携带方法名、方法类型，以及对应的 IFn / TFn。而 IFn / TFn 在 IR 里最终就是实打实的函数地址。

在当前 LLGo v0.13.0 中，这张方法表仍然是在编译期按完整 method set 一次性全量产出的。
当前实现位置就在 ssa/abitype.go：

1. abiType 会为带方法集的类型生成 abi.Type + abi.UncommonType + [N]abi.Method 这种整体布局。
2. abiUncommonMethods 会按 mset.Len() 遍历完整方法集，逐项构造 [N]abi.Method，并把每个方法的 Name / MType / IFn / TFn 全部写进去。

所以，如果把上面这个程序编译成当前 LLGo 的 LLVM IR，就会看到：虽然语义上真正被需求的只是 Reader.Read，但 stringReader 的 pointer type descriptor 仍然会带着完整的方法表：

@"*_llgo_github.com/goplus/llgo/cl/_testgo/reader.stringReader" = weak_odr constant
  { %"github.com/goplus/llgo/runtime/abi.PtrType",
    %"github.com/goplus/llgo/runtime/abi.UncommonType",
    [10 x %"github.com/goplus/llgo/runtime/abi.Method"] } {
    ...,
    [10 x %"github.com/goplus/llgo/runtime/abi.Method"] [
      { ..., ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).Len",     ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).Len" },
      { ..., ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).Read",    ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).Read" },
      { ..., ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).ReadAt",  ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).ReadAt" },
      ...,
      { ..., ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).WriteTo", ptr @"github.com/goplus/llgo/cl/_testgo/reader.(*stringReader).WriteTo" }
    ]
  }

同时，在普通函数体里还能看到这次接口装箱会把这个 type descriptor 直接引用进来：

%2 = call ptr @"github.com/goplus/llgo/runtime/internal/runtime.NewItab"(
  ptr @"_llgo_iface$uycIKA3bbxRhudEjW1hHKWKdLqHQsCVy8NdW1bkQmNw",
  ptr @"*_llgo_github.com/goplus/llgo/cl/_testgo/reader.stringReader")

从普通 gc-sections 或普通 lld 的视角看，这是一条非常直接的强引用链：

main / ReadAll
  -> stringReader 的 abi.Type
  -> abi.UncommonType / [10 x abi.Method]
  -> 每个 abi.Method 里的 Name / MType / IFn / TFn
  -> Len / Read / ReadAt / ... / WriteTo

问题就在这里：

1. 链接器看到的只是“一个活着的全局常量里含有真实函数指针和类型指针”。
2. 它并不知道语义上真正被需求的其实只是 Reader.Read 这个接口槽位。
3. 因此，只要 @"*_llgo_github.com/goplus/llgo/cl/_testgo/reader.stringReader" 变成可达，整个方法表里的所有方法都会跟着被保留。
4. 这不是 lld 的 bug，而是 ordinary reference graph 本身无法表达“同一个方法表里只有某几个槽位真的需要保留”。

这正是 LLGo 必须额外做语义分析的根本原因：

1. 先在 whole-program 视角上判断哪些类型真的进入了接口语义域。
2. 再判断哪些接口槽位真的被需求。
3. 最后只留下对应的 method indexes，而不是整张 abi.Method 表一起保活。

当前的核心问题

我们真正想回答的问题其实只有一个：

某个类型的方法表里，哪些方法在运行时语义上真的需要保留。

上面的例子已经说明了当前问题：

1. 某个具体类型的 type descriptor 一旦可达，普通引用图看到的就是“整张 abi.Method 表都跟着可达”。
2. 但我们真正需要的不是“类型活着，所以这个类型的方法全部都活着”。
3. 我们真正需要的是：类型本身可以保留，但方法表应该允许按运行时语义进行部分裁剪。

也就是说，链接期必须支持“类型保留、方法表部分裁剪”这件事，而 ordinary reference graph 本身表达不了这个能力。

从 Go 链接期 deadcode 的既有设计可以看出，这类问题并不是继续依赖普通引用图就能解决的。Go 的做法是让链接阶段显式理解与类型、接口、反射相关的额外语义，再在 whole-program 视角下执行专门的方法判活。

因此，LLGo 在方向上会采用类似思路：不试图把这个问题继续塞回 ordinary reference graph 里解决，而是引入一套单独的链接期语义分析模型。

与 Go 方案的关系

本方案明确受 Go 链接期 deadcode 思路启发，但并不打算复刻 Go 的内部实现细节。

LLGo 想吸收的是两类东西：

1. 处理问题的方向：把接口转换、接口方法调用、按名字取方法、反射保守模式等语义事件纳入链接期分析。
2. 分析方法本身：在 whole-program 视角上做多轮传播直至结果稳定的语义可达性分析，而不是仅依赖普通引用图。

LLGo 不打算照搬的是：

1. Go 的 object 格式与 loader 结构。
2. Go 的内部 relocation 编码方式。
3. Go 链接器的具体实现分层。

这两套方案最大的工程差异是语义输入的承载位置不同：

1. Go 把相关语义信息落在 goobj / relocation / type data / symbol attribute 体系里，例如类型进入接口语义域、接口方法需求、按名字取方法、反射保守标记等。
2. LLGo 则把这些语义信息显式发射到 llvm.Module 的 named metadata 中，再在链接构建阶段统一读取。

但两者在更高层语义上是一致的：

1. 都是在全局视角下收集普通可达边与语义事件。
2. 都会在 whole-program 范围上做多轮传播和收敛。
3. 都试图回答同一个问题：某个具体类型的方法表里，哪些槽位最终必须保留。

LLGo 当前方案还明确吸收并改进了一个 Go 现有保守点：

1. 不能只按“方法名 + 方法类型”去命中接口需求。
2. 还必须额外检查：这个具体类型是否完整实现了对应接口。

这样可以避免“未完整实现接口的结构体方法，只因为签名碰巧命中需求就被保活”的问题。

基于这层共性与差异，LLGo 的整体实现会采用“单包产出语义、全局统一分析、结果回写”的架构。

分析架构

本方案的核心特点是：

1. 单独编译某个包时，只额外产出这个包内部已经能够静态确定的语义信息。
2. 不在单包阶段提前决定某个方法最终是否保留。
3. 等 whole-program 的 []llvm.Module 都准备好之后，再从全局视角统一分析方法可达性。

单包阶段究竟需要额外标记哪些语义，全局阶段又如何消费这些语义并完成方法判活，后文会分别详细展开；这里先给出整体架构。

这条链路可以概括为：

flowchart TD
    A[包 A<br/>ssa/cl 编译<br/>module A + metadata]
    B[包 B<br/>ssa/cl 编译<br/>module B + metadata]
    C[包 C<br/>ssa/cl 编译<br/>module C + metadata]
    A --> D[构建阶段聚合<br/>whole-program LLVM modules]
    B --> D
    C --> D
    D --> E[graph<br/>提取 ordinary edges<br/>与语义输入]
    E --> F[analyze<br/>全局方法可达性分析]
    F --> G[result<br/>live method indexes by type symbol]
    G --> H[rewrite<br/>复制并裁剪强 abi.Type]

Loading

具体来说：

1. ssa/cl 阶段继续按包编译，但会额外把接口转换、接口方法需求、按名字取方法、反射保守标记、方法槽位信息等语义写进当前包的 llvm.Module。
2. 构建阶段拿到所有包的 []llvm.Module 之后，graph 统一扫描所有 package 的普通引用边和这些 metadata，把它们聚合成一份 whole-program 输入。
3. analyze 在 whole-program 视角上执行多轮传播，最终只产出一份稳定结果：

type symbol -> live method indexes

4. 一旦这份结果算出，分析行为本身就结束了。后续 rewrite 只负责消费结果，复制弱 abi.Type 定义、裁剪方法表、生成强符号，并在最终链接时覆盖原定义。

这里有两个关键分层：

1. 普通引用边仍然来自函数体、全局 initializer、常量表达式等 ordinary IR 内容。
2. 与接口、反射、方法表相关的额外语义，则由单包编译阶段显式产出，再在全局阶段统一消费。

目标与边界

本方案的目标是：

1. 为 LLGo 定义一套正式的链接期语义方法裁剪方案。
2. 在分析阶段稳定产出 type symbol -> live method indexes。
3. 基于该结果回写裁剪后的强 abi.Type 定义。

本方案当前不包含：

1. 复刻 Go 内部 object/relocation/loader 结构。
2. 一次性覆盖所有 build mode。
3. 同时讨论 SCCP、CFG DCE、常量传播等通用 IR 优化。

Whole-program 信息模型

本节定义算法本身要求外部提供的一份归一化 whole-program 信息，记为 WholeProgramInfo。

这里的 whole-program 不是“某一个包的信息模型”，而是“所有参与本次链接的 package 信息聚合之后”的总输入。
也就是说，WholeProgramInfo 的每个字段都应理解为：把所有 package 各自贡献出来的 ordinary edges、类型传播边、接口信息、方法槽位信息和语义需求统一合并后的结果。

analyze 的边界不是 LLVM IR，也不是 metadata 本身，而是这份已经整理好的 WholeProgramInfo。
只要外部能够提供等价的信息，算法就不关心这些信息最终来自哪种对象格式、哪种扫描过程或哪种中间承载方式。

LLGo 当前实现中，这份 WholeProgramInfo 由构建阶段从所有 package 的 LLVM modules 聚合得到。
这也意味着：后续如果为了加速构建过程，希望缓存某个包已经提取好的语义信息，再在 whole-program 阶段直接组装成 WholeProgramInfo，算法本身并不需要改变。
不过本期实现不涉及这种缓存；当前基线仍然是基于 ssa -> llvm.Module 的产物统一提取。

因此，下面各项定义中的 key 和 value，描述的都是 whole-program 聚合后的语义，而不是某个单独 package 的局部视图。

它的定义如下：

type Symbol = string

type MethodSig struct {
	Name  string
	MType Symbol
}

type MethodSlot struct {
	Index int
	Sig   MethodSig
	IFn   Symbol
	TFn   Symbol
}

type IfaceMethodDemand struct {
	Target Symbol
	Sig    MethodSig
}

type WholeProgramInfo struct {
	OrdinaryEdges  map[Symbol]map[Symbol]struct{}
	TypeChildren   map[Symbol]map[Symbol]struct{}
	InterfaceInfo  map[Symbol][]MethodSig
	UseIface       map[Symbol][]Symbol
	UseIfaceMethod map[Symbol][]IfaceMethodDemand
	MethodInfo     map[Symbol][]MethodSlot
	UseNamedMethod map[Symbol][]string
	ReflectMethod  map[Symbol]struct{}
}

其中，MethodSig 不是一级输入项，而是 MethodInfo 与 InterfaceInfo 共用的方法签名表示。
当前基线下：

1. Name 必须是规范化的方法名。
2. 导出方法直接使用方法名，例如 Read。
3. 非导出方法使用带完整包路径的规范化名字。
4. MType 是方法类型描述符的 symbol。

OrdinaryEdges

OrdinaryEdges 表示普通可达边，也就是 ordinary symbol reachability graph。

外部需要提供的就是 ordinary call/ref 所形成的普通引用图。

例如：

func helper() {}

func main() {
	helper()
}

在这个例子里：

1. main -> helper 会进入 OrdinaryEdges。
2. 这是普通 direct call。
3. 它不属于接口语义，也不需要额外 metadata。

也就是说：

1. key 是源符号。
2. value 是这个符号通过 ordinary call/ref 能直接到达的目标符号集合。

同样地，直接的结构体方法调用也属于 OrdinaryEdges。例如，下面这段代码：

type S struct{}

func (*S) M() {}
func (S) N() {}

func main() {
	var s S
	s.M()
	s.N()
}

在这个例子里：

1. main -> (*S).M 和 main -> S.N 都仍然是 ordinary edge。
2. 因为 IR 里已经能直接看到具体的方法符号。
3. s.M() 虽然源码里写的是 value 调用，但因为 s 可寻址，最终会落到 (*S).M。

按当前 LLGo 实际生成出来的符号形状，结构化后可以直接写成：

OrdinaryEdges = map[Symbol]map[Symbol]struct{}{
	"github.com/goplus/llgo/doc/tt.main": {
		"github.com/goplus/llgo/doc/tt.(*S).M": {},
		"github.com/goplus/llgo/doc/tt.S.N":    {},
	},
}

但接口方法调用不是这样。例如：

type I interface{ M() }

func call(i I) {
	i.M()
}

这里不会把 call -> 某个具体实现的 M 直接记进 OrdinaryEdges，因为 IR 里并没有一个唯一的具体目标符号。
这类调用会在后文通过额外语义信息单独表达。

TypeChildren

TypeChildren 记录类型之间的直接传播边。

它的含义是：

1. 如果某个源类型已经进入接口/反射相关分析范围，
2. 那么沿着 runtime type data 能继续观察到的子类型，也必须继续进入同一分析范围。

注意：

1. 这里记录的是直接传播边，不是预先展开的传递闭包。
2. 递归闭包是在分析阶段沿这些边继续展开。

之所以需要它，是因为：

1. 一个类型一旦可能通过接口值和反射路径被继续观察，
2. 程序就有可能进一步拿到它内部涉及到的子类型，
3. 这些子类型的方法表同样可能影响最终哪些动态方法必须保留，
4. 因此分析器必须知道这种子类型传播关系。

例如：

type Inner struct{}

func (Inner) M() {}

type Outer struct {
	F Inner
}

func main() {
	var x any = Outer{}
	_ = x
}

结构化地看，可以表达为：

TypeChildren = map[Symbol]map[Symbol]struct{}{
	"_llgo_github.com/goplus/llgo/demo.Outer": {
		"_llgo_github.com/goplus/llgo/demo.Inner": {},
	},
}

MethodInfo

MethodInfo 描述某个具体类型的方法槽位表。
它不是“已经被需求的方法集合”，而是“分析器可判活的候选槽位集合”；当某个槽位首次命中时，分析器会从该槽位继续拉活 MType/IFn/TFn。
如果某个类型没有方法，那么它可以完全不出现在 MethodInfo 里。

例如，考虑 demo/file.go：

package demo

type File struct{}

func (*File) Read([]byte) (int, error) { return 0, nil }
func (*File) Close() error             { return nil }

假设它编译后的包路径是 github.com/goplus/llgo/demo，则它对应的 MethodInfo 可以直接理解为：

MethodInfo["_llgo_github.com/goplus/llgo/demo.File"] = []MethodSlot{
	{
		Index: 0,
		Sig: MethodSig{
			Name:  "Read",
			MType: "_llgo_func$A1...",
		},
		IFn: "github.com/goplus/llgo/demo.(*File).Read",
		TFn: "github.com/goplus/llgo/demo.File.Read",
	},
	{
		Index: 1,
		Sig: MethodSig{
			Name:  "Close",
			MType: "_llgo_func$B2...",
		},
		IFn: "github.com/goplus/llgo/demo.(*File).Close",
		TFn: "github.com/goplus/llgo/demo.File.Close",
	},
}

其中：

1. key 是具体类型 symbol。
2. value 是该类型按 abi.Method 槽位顺序排列的 []MethodSlot。
3. 每一项都是一个 MethodSlot，其中 Sig 又是一个 MethodSig。
4. Index 必须与最终 abi.Method 表中的槽位索引完全一致。
5. IFn 和 TFn 在当前基线下都存在，但对某些方法它们可能相同。

InterfaceInfo

InterfaceInfo 描述接口的方法集合。

例如，考虑 demo/reader.go：

package demo

type Reader interface {
	Read([]byte) (int, error)
	Close() error
}

假设它编译后的包路径是 github.com/goplus/llgo/demo，则它对应的 InterfaceInfo 可以直接理解为：

InterfaceInfo["_llgo_github.com/goplus/llgo/demo.Reader"] = []MethodSig{
	{
		Name:  "Read",
		MType: "_llgo_func$A1...",
	},
	{
		Name:  "Close",
		MType: "_llgo_func$B2...",
	},
}

其中：

1. key 是接口类型 symbol。
2. value 是该接口的方法签名集合，这里使用 []MethodSig 表达。
3. 语义上它表示“这个接口完整要求哪些方法”；适配层需要负责去重和规范化。

UseIface

UseIface 按 Owner 分组，value 是该 Owner 可达后需要进入 UsedInIface 的具体类型集合。

例如，考虑 demo/reader.go：

package demo

type Reader interface {
	Read([]byte) (int, error)
}

type File struct{}

func (*File) Read([]byte) (int, error) { return 0, nil }

func main() {
	var r Reader = &File{}
	_ = r
}

假设它编译后的包路径是 github.com/goplus/llgo/demo，则它对应的 UseIface 可以直接理解为：

UseIface = map[Symbol][]Symbol{
	"github.com/goplus/llgo/demo.main": []Symbol{
		"*_llgo_github.com/goplus/llgo/demo.File",
	},
}

UseIfaceMethod

UseIfaceMethod 按 Owner 分组，value 是该 Owner 可达后产生的接口方法需求集合。

例如，考虑 demo/reader.go：

package demo

type Reader interface {
	Read([]byte) (int, error)
}

func consume(r Reader, p []byte) {
	_, _ = r.Read(p)
}

假设它编译后的包路径是 github.com/goplus/llgo/demo，则它对应的 UseIfaceMethod 可以直接理解为：

UseIfaceMethod = map[Symbol][]IfaceMethodDemand{
	"github.com/goplus/llgo/demo.consume": []IfaceMethodDemand{
		{
			Target: "_llgo_github.com/goplus/llgo/demo.Reader",
			Sig: MethodSig{
				Name:  "Read",
				MType: "_llgo_func$A1...",
			},
		},
	},
}

UseNamedMethod

UseNamedMethod 按 Owner 分组，value 是该 Owner 可达后产生的方法名需求集合。
只有当方法名在编译期可静态确定时，MethodByName 这类调用才会进入这里；如果方法名不是编译期常量，则会退化为后文的 ReflectMethod。

例如，考虑 demo/lookup.go：

package demo

func lookup(v any) {
	_, _ = reflect.TypeOf(v).MethodByName("ServeHTTP")
}

假设它编译后的包路径是 github.com/goplus/llgo/demo，则它对应的 UseNamedMethod 可以直接理解为：

UseNamedMethod = map[Symbol][]string{
	"github.com/goplus/llgo/demo.lookup": []string{
		"ServeHTTP",
	},
}

ReflectMethod

ReflectMethod 是一个 owner 集合；当其中任意一个 Owner 可达时，分析必须进入保守的反射模式。
典型来源包括 reflect.Type.Method、reflect.Value.Method，以及方法名无法在编译期静态确定的 MethodByName。

例如，考虑 demo/value.go：

package demo

func valueByIndex(v any) {
	_ = reflect.ValueOf(v).Method(0)
}

假设它编译后的包路径是 github.com/goplus/llgo/demo，则它对应的 ReflectMethod 可以直接理解为：

ReflectMethod = map[Symbol]struct{}{
	"github.com/goplus/llgo/demo.valueByIndex": {},
}

一旦命中这类输入，当前基线语义就是：对所有 UsedInIface 的具体类型，保留其导出方法对应的槽位。

核心算法

输入

算法输入有两部分：

1. 一份 whole-program 级别的 WholeProgramInfo
2. 一组链接入口 roots

其中：

1. WholeProgramInfo 是把所有参与本次链接的 package 语义信息聚合后的结果。
2. roots 是 ordinary reachability 的起点，例如 main、_start、__main_argc_argv 这类最终链接入口。

输出形式

分析器输出：

type Result map[string]map[int]struct{}

语义是：

1. key 是具体类型 symbol。
2. value 是该类型最终保留的方法槽位索引集合。

这就是分析阶段的最终结果。
算法在得到这份结果后即停止，不再继续处理 ABI type 重写或强符号生成；这些工作属于后续回写阶段。

判活循环

核心逻辑可以直接概括为一个“普通 flood + 语义需求传播 + 方法槽位判活”的循环：

1. 先从 roots 出发，沿 OrdinaryEdges 做普通可达性传播。
2. 每当某个 owner 变为可达，就读取它在 UseIface、UseIfaceMethod、UseNamedMethod、ReflectMethod 里的语义需求。
3. UseIface 会把具体类型加入 UsedInIface，并沿 TypeChildren 继续传播。
4. UseIfaceMethod 会为某个接口积累方法需求；UseNamedMethod 会积累按名字的需求；ReflectMethod 会打开保守反射模式。
5. 然后对所有已经进入 UsedInIface 的具体类型，检查它们的 MethodInfo 槽位，判断哪些槽位应该保活。
6. 其中最关键的一点是：接口方法需求只有在“该具体类型完整实现了对应接口”时，才允许命中这个类型上的槽位；不能只靠方法名和方法类型相同就直接保活。
7. 某个槽位一旦首次保活，就把该槽位对应的 MType、IFn、TFn 重新加入普通可达图。
8. 如此反复，直到没有新的 ordinary reachable symbol、没有新的语义需求、也没有新的 live method slot 为止。

最终得到的就是：

type symbol -> live method indexes

例子

例子一：接口调用只保留真正被需求的方法

考虑：

type Reader interface {
	Read([]byte) (int, error)
}

type File struct{}

func (File) Read([]byte) (int, error) { return 0, nil }
func (File) Close() error             { return nil }

func consume(r Reader, p []byte) {
	_, _ = r.Read(p)
}

func main() {
	consume(File{}, nil)
}

分析开始前，这个例子对应的 whole-program 输入可以近似理解为：

roots := []Symbol{
	"github.com/goplus/llgo/demo.main",
}

OrdinaryEdges = map[Symbol]map[Symbol]struct{}{
	"github.com/goplus/llgo/demo.main": {
		"github.com/goplus/llgo/demo.consume": {},
	},
}

UseIface = map[Symbol][]Symbol{
	"github.com/goplus/llgo/demo.main": {
		"_llgo_github.com/goplus/llgo/demo.File",
	},
}

UseIfaceMethod = map[Symbol][]IfaceMethodDemand{
	"github.com/goplus/llgo/demo.consume": {
		{
			Target: "_llgo_github.com/goplus/llgo/demo.Reader",
			Sig: MethodSig{
				Name:  "Read",
				MType: "_llgo_func$readsig",
			},
		},
	},
}

InterfaceInfo = map[Symbol][]MethodSig{
	"_llgo_github.com/goplus/llgo/demo.Reader": {
		{
			Name:  "Read",
			MType: "_llgo_func$readsig",
		},
	},
}

MethodInfo = map[Symbol][]MethodSlot{
	"_llgo_github.com/goplus/llgo/demo.File": {
		{
			Index: 0,
			Sig: MethodSig{
				Name:  "Read",
				MType: "_llgo_func$readsig",
			},
			IFn: "github.com/goplus/llgo/demo.(*File).Read",
			TFn: "github.com/goplus/llgo/demo.File.Read",
		},
		{
			Index: 1,
			Sig: MethodSig{
				Name:  "Close",
				MType: "_llgo_func$closesig",
			},
			IFn: "github.com/goplus/llgo/demo.(*File).Close",
			TFn: "github.com/goplus/llgo/demo.File.Close",
		},
	},
}

这里 TypeChildren、UseNamedMethod 和 ReflectMethod 都为空。

全局分析过程如下：

1. 初始 root 是 main，分析器先把 github.com/goplus/llgo/demo.main 放进 reachable 集合。
2. 第一轮 flood 沿 OrdinaryEdges 传播，于是 github.com/goplus/llgo/demo.consume 也变成 reachable。
3. 进入语义激活阶段时，UseIface[main] 命中，所以 _llgo_github.com/goplus/llgo/demo.File 进入 UsedInIface。
4. 同一轮里，UseIfaceMethod[consume] 也命中，因此分析器得到一个接口方法需求：Reader.Read。
5. 接着进入方法判活阶段。分析器只检查已经进入 UsedInIface 的具体类型，这里就是 File。
6. File 的 MethodInfo 里有两个槽位：Read 和 Close。
7. 对 Read 槽位来说，它的 MethodSig 命中了当前接口需求 Reader.Read，而且 File 又完整实现了 Reader，所以这个槽位被判活。
8. 一旦 Read 槽位首次判活，结果里会记录 File -> [0]，同时这个槽位对应的 MType/IFn/TFn 也会重新放回 ordinary reachability 图里继续传播。
9. Close 槽位没有命中任何接口需求、名字需求或反射保守条件，所以不会被保活。
10. 下一轮分析会先再次执行 flood，处理上一轮新加入的 MType/IFn/TFn；如果这些新可达符号又触发新的语义事件，就继续进入下一轮。
11. 当 ordinary flood、语义激活和方法判活三步都不再产生新信息时，分析收敛。

最终结果是：

_llgo_github.com/goplus/llgo/demo.File: [0]

其中 0 表示 Read 所在槽位。

例子二：不完整实现接口的类型不会被误保活

考虑：

type A struct{}

func (*A) Foo() {}
func (*A) Bar() {}

type B struct{}

func (*B) Foo() {}
func (*B) Bar() {}
func (*B) Car() {}

type BI interface {
	Foo()
	Bar()
	Car()
}

func callBI(x BI) {
	x.Foo()
	x.Bar()
}

func main() {
	var _ any = &A{}
	callBI(&B{})
}

这个例子里：

1. A 确实会进入接口语义域，因为 main 里有一次 &A{} -> any 的转换。
2. B 也会进入接口语义域，因为 main 里有一次 &B{} -> BI 的调用传参。
3. 但真正的接口方法调用只发生在 callBI 里，而且只调用了 Foo 和 Bar。

在算法视角下，它对应的 whole-program 输入可以近似理解为：

roots := []Symbol{
	"github.com/goplus/llgo/demo.main",
}

OrdinaryEdges = map[Symbol]map[Symbol]struct{}{
	"github.com/goplus/llgo/demo.main": {
		"github.com/goplus/llgo/demo.callBI": {},
	},
}

UseIface = map[Symbol][]Symbol{
	"github.com/goplus/llgo/demo.main": {
		"*_llgo_github.com/goplus/llgo/demo.A",
		"*_llgo_github.com/goplus/llgo/demo.B",
	},
}

UseIfaceMethod = map[Symbol][]IfaceMethodDemand{
	"github.com/goplus/llgo/demo.callBI": {
		{
			Target: "_llgo_github.com/goplus/llgo/demo.BI",
			Sig: MethodSig{
				Name:  "Foo",
				MType: "_llgo_func$foosig",
			},
		},
		{
			Target: "_llgo_github.com/goplus/llgo/demo.BI",
			Sig: MethodSig{
				Name:  "Bar",
				MType: "_llgo_func$barsig",
			},
		},
	},
}

InterfaceInfo = map[Symbol][]MethodSig{
	"_llgo_github.com/goplus/llgo/demo.BI": {
		{Name: "Foo", MType: "_llgo_func$foosig"},
		{Name: "Bar", MType: "_llgo_func$barsig"},
		{Name: "Car", MType: "_llgo_func$carsig"},
	},
}

MethodInfo = map[Symbol][]MethodSlot{
	"*_llgo_github.com/goplus/llgo/demo.A": {
		{Index: 0, Sig: MethodSig{Name: "Foo", MType: "_llgo_func$foosig"}, IFn: "github.com/goplus/llgo/demo.(*A).Foo", TFn: "github.com/goplus/llgo/demo.(*A).Foo"},
		{Index: 1, Sig: MethodSig{Name: "Bar", MType: "_llgo_func$barsig"}, IFn: "github.com/goplus/llgo/demo.(*A).Bar", TFn: "github.com/goplus/llgo/demo.(*A).Bar"},
	},
	"*_llgo_github.com/goplus/llgo/demo.B": {
		{Index: 0, Sig: MethodSig{Name: "Foo", MType: "_llgo_func$foosig"}, IFn: "github.com/goplus/llgo/demo.(*B).Foo", TFn: "github.com/goplus/llgo/demo.(*B).Foo"},
		{Index: 1, Sig: MethodSig{Name: "Bar", MType: "_llgo_func$barsig"}, IFn: "github.com/goplus/llgo/demo.(*B).Bar", TFn: "github.com/goplus/llgo/demo.(*B).Bar"},
		{Index: 2, Sig: MethodSig{Name: "Car", MType: "_llgo_func$carsig"}, IFn: "github.com/goplus/llgo/demo.(*B).Car", TFn: "github.com/goplus/llgo/demo.(*B).Car"},
	},
}

全局分析过程如下：

1. 初始 root 是 main，分析器先把 github.com/goplus/llgo/demo.main 放进 reachable 集合。
2. 第一轮 flood 沿 OrdinaryEdges 传播，于是 github.com/goplus/llgo/demo.callBI 也变成 reachable。
3. 进入语义激活阶段时，UseIface[main] 命中，所以 *_llgo_github.com/goplus/llgo/demo.A 和 *_llgo_github.com/goplus/llgo/demo.B 都进入 UsedInIface。
4. 同一轮里，UseIfaceMethod[callBI] 也命中，因此分析器得到两个接口方法需求：BI.Foo 和 BI.Bar。
5. 接着进入方法判活阶段。分析器会检查所有已经进入 UsedInIface 的具体类型，也就是这里的 A 和 B。
6. 如果只按 Name + MType 直接匹配，那么 A.Foo、A.Bar、B.Foo、B.Bar 都会命中需求；这正是我们要避免的误判。
7. 当前方案不会直接这么做，而是先用 InterfaceInfo[BI] 去判断某个具体类型是否完整实现了 BI。
8. 对 A 来说，它自己的方法集合只有 Foo 和 Bar；而 InterfaceInfo[BI] 里要求的是 Foo、Bar、Car。因此 A 不完整实现 BI。
9. 于是即使 A.Foo 和 A.Bar 的 MethodSig 都与需求命中，它们也不能满足 BI.Foo 或 BI.Bar 这两个接口调用需求，所以不会被保活。
10. 对 B 来说，它自己的方法集合完整覆盖了 InterfaceInfo[BI]，因此 B 被判定为完整实现 BI。
11. 在这个前提下，B.Foo 和 B.Bar 才能真正命中当前需求，于是这两个槽位被保活，并把各自的 MType/IFn/TFn 放回 ordinary reachability 图继续传播。
12. B.Car 虽然是 B 完整实现 BI 所必需的方法之一，但当前程序里并没有出现 BI.Car 的接口调用需求，所以它不会仅仅因为“参与了接口实现判定”就被保活。
13. 后续轮次继续执行 flood -> 语义激活 -> 方法判活，直到三步都不再产生新信息为止。

最终结果只会包含 B 上对应的 Foo 和 Bar 槽位，不会包含 A 的部分方法，也不会因为 B 完整实现了 BI 就把 B.Car 顺带保活。

换句话说，这里的判定逻辑是：

1. 先看某个具体类型是否完整覆盖 InterfaceInfo[target]。
2. 只有完整覆盖时，该类型上的某个槽位才有资格去满足这个接口方法需求。
3. 然后再看这个槽位自己的 MethodSig 是否真的命中了当前 demand。

因此，真正的保活条件不是“方法名和方法类型碰巧一致”，而是：

具体类型完整实现目标接口
AND
该槽位正好对应当前被调用的那个接口方法

例子三：MethodByName 触发精确名字需求

考虑：

func lookup(v any) {
	_, _ = reflect.TypeOf(v).MethodByName("ServeHTTP")
}

如果 "ServeHTTP" 是编译期常量，那么：

1. 编译器发射 UseNamedMethod(owner, "ServeHTTP")
2. 当 owner 可达时，
3. 所有 UsedInIface 类型中方法名为 ServeHTTP 的槽位都需要保活

这里的精确度高于保守反射模式，因为：

1. 需求是按精确名字触发的，
2. 而不是“所有导出方法都要保活”。

例子四：反射保守模式会扩大保活范围

考虑：

func valueByIndex(v any) {
	_ = reflect.ValueOf(v).Method(0)
}

这里无法在编译期精确知道目标方法名，因此：

1. 编译器发射 ReflectMethod(owner)。
2. 当 owner 可达时，分析进入保守反射模式。
3. 对所有 UsedInIface 类型，导出方法对应槽位都要保活。

这是一种保守但必要的退化。

例子五：UsedInIface 会沿子类型传播

考虑一个类型 Outer，其 runtime type data 中可继续到达某个子类型 Inner。

如果：

1. Outer 进入 UsedInIface，

那么：

1. Inner 也必须进入 UsedInIface，
2. 否则 Inner 上可能通过反射或后续接口转换访问到的方法表就会漏判。

因此 TypeChildren 的存在不是为了普通图遍历，而是为了显式表达这种语义传播。

当前落地方式

以当前分支实现为例，整个落地路径分为两个阶段：

1. 分析阶段
2. 回写阶段

分析阶段

分析阶段的目标是聚合 whole-program 输入，并计算出：

type symbol -> live method indexes

以当前分支实现为例，算法输入不是一次性由某个单独文件直接产出，而是由两部分信息在构建阶段聚合得到。

第一部分是 ssa/cl 在单包编译阶段显式发射的 llgo.xxx named metadata：

其中，llgo.interfaceinfo 与 llgo.methodinfo 当前实现选择“一个方法/槽位一行”的编码，而不是把整组信息拼进一行；这样 graph 阶段解析会更直接。

1. llgo.useiface
   行格式：{ owner, concrete type }
2. llgo.useifacemethod
   行格式：{ owner, interface type, normalized method name, mtype }
3. llgo.interfaceinfo
   行格式：{ interface type, method name, mtype }
4. llgo.methodinfo
   行格式：{ concrete type, index, method name, mtype, ifn, tfn }
   如果某个类型没有方法，则不发射任何 llgo.methodinfo 行。
5. llgo.usenamedmethod
   行格式：{ owner, normalized method name }
6. llgo.reflectmethod
   行格式：{ owner }

这些 metadata 负责表达接口转换、接口方法需求、接口完整方法集、具体类型方法槽位、按名字取方法以及反射保守模式等语义信息。

第二部分不是通过 llgo.xxx 发射的，而是构建阶段直接从每个包的 llvm.Module 普通内容中提取：

1. OrdinaryEdges
   从函数体、全局 initializer、常量操作数等 ordinary LLVM IR 内容里扫描得到普通引用边。
2. TypeChildren
   从每个包里的 ABI type globals 递归扫描得到直接子类型传播边。

构建阶段拿到所有 package 的 llvm.Module 之后，会把这两部分信息统一聚合成一份 whole-program WholeProgramInfo，再交给前文定义的判活算法。

回写阶段

分析阶段结束后，“哪些方法需要保留”已经有了稳定答案。
回写阶段不再参与任何语义判断，它只负责把这个答案转成最终链接产物。

具体来说，回写阶段需要做的是：

1. 找到所有需要被裁剪的 ABI type。
2. 从原始弱定义复制出一份新的强定义。
3. 根据 Result[type] 裁剪其方法表数组。
4. 把新定义放进单独模块。
5. 在最终链接时用强定义覆盖原弱定义。

这样分层有三个直接好处：

1. 算法定义清晰，分析结果与工程回写不会互相污染。
2. 分析器可以单独测试，不依赖强符号生成逻辑。
3. 回写器可以单独验证，只要输入 Result 正确即可。

[luoliwoshang]

缓存在

[luoliwoshang]

Rust 将编译产物和元数据分离得非常优雅，它的核心文件扩展名主要有两个：

.rmeta (Rust Metadata 纯元数据文件)
这正是我们之前讨论的方案一！.rmeta 文件非常轻量，里面包含了：库的导出符号、类型定义、Trait 的实现关系、甚至一些用于内联的 AST/MIR（中级中间表示）。它不包含任何机器码。

.rlib (Rust Library 静态库)
这其实就是一个标准的 Unix ar 压缩包。如果你把它解压，你会发现里面装的是一堆 .o 机器码文件加上一个 .rmeta 文件。

[luoliwoshang]

LLGo Go linktime-like 全图方法裁剪与包级摘要缓存提案

摘要

本提案定义 LLGo 面向 Go 语义的全图方法裁剪方案，以及与之配套的包级摘要缓存方案。该方案面向可执行构建路径，借鉴 Go 在全图视角下整合程序语义输入并求解方法可达性的设计思路，并在 LLGo 的构建链路中正式建立一段全局分析与改写能力。当前仅依赖普通引用关系的删除无法精确表达类型元数据、接口调用、按名字取方法和反射带来的方法需求，因此许多语义上不可达的方法仍会被保活。该方案的核心目标是在 whole-program 视角下稳定判定哪些具体类型上的哪些方法槽位在语义上必须保留，并输出可供后续回写与裁剪阶段消费的 type symbol -> live method indexes 结果。

本提案同时定义全图方法可达性分析所需的正式输入，包括普通符号可达关系、类型之间的关联关系、接口转换与接口方法调用带来的语义需求、按名字取方法与反射带来的方法保活需求，以及具体类型的方法槽位信息；并在现有设计基础上引入包级摘要缓存模型，在单包粒度上保存这些分析事实，使后续全局汇总阶段能够直接恢复 whole-program 分析输入，并为这些分析事实提供可复用、可缓存的正式载体。

在该设计下，LLGo 的正式链路为：单包构建阶段生成 package summary，全局汇总阶段合并 package summary 构造 whole-program 输入，迭代传播相关语义直到结果收敛，得到稳定的“具体类型到存活方法槽位集合”结果，最后由后续阶段消费该结果完成方法裁剪。该提案的范围同时覆盖分析输入模型、缓存边界、结果表达形式以及全局分析与后续消费阶段的职责分层。

背景

本章说明 Go 方法可达性问题为什么不能退化为普通 symbol reachability，以及 LLGo 为什么需要建立一套独立于平台链接器的全图分析能力。

当前状态

本章描述 LLGo 当前尚未具备哪些正式能力，包括稳定的分析输入协议、单包摘要产物以及面向该输入的全局方法可达性分析器。

问题陈述

本章定义当前需要解决的核心问题：普通 gc-sections 与普通 IR DCE 无法精确表达 Go 方法可达性语义，而每次重新扫描 llvm.Module 也不适合作为长期正式边界。

设计目标

本章列出本提案希望正式建立的能力，包括分析输入模型、分析结果形式以及包级摘要缓存的职责边界。

非目标

本章明确本文不试图解决的问题，包括复刻 Go cmd/link 的 object/loader 细节、锁定唯一回写方案以及一次覆盖全部 build mode。

提案概览

本章给出整体处理流程：单包阶段产出摘要，全局阶段汇总摘要并完成方法可达性分析，再由后续阶段消费分析结果执行裁剪。

正式分析输入

本章定义分析器必须消费的逻辑输入集合，以及这些输入各自表达的语义、生产边界和最小字段要求。

包级摘要缓存

本章定义 package summary 的职责、内容边界、组合方式以及版本、失效和兼容性要求。

全局分析规则

本章定义 whole-program 视角下的方法可达性传播规则，包括 ordinary symbol 可达性、接口相关需求、按名字取方法以及反射保守边界。

结果形式与消费边界

本章定义分析阶段的正式输出形式，并区分分析结果本身与后续回写/裁剪阶段的工程职责。

取舍

本章说明本提案在分析输入载体、缓存边界以及全局汇总路径上的主要取舍。

为什么不把分析输入长期绑定在 llvm.Module 上

当前工程中，即使 Go 构建缓存命中，也还不能省略 llvm.Module 的生成。因此，从工程现实看，在 llvm.Module 中发射和读取相关语义信息并非不可行，第一阶段实现也完全可以复用这一路径。

本提案选择将类型相关元信息与 ordinary edges 一并纳入 package summary，而不是把它们长期绑定在 llvm.Module 上。原因有两点。其一，后续构建链路可能具备在缓存命中时减少甚至省略 llvm.Module 生成的能力，此时 package summary 可以作为更稳定的分析输入载体。其二，在 MVP 实践中，从 llvm.Module 读取指令并恢复 ordinary edges 是相对昂贵的操作；编译速度又是当前 LLGo 的重要目标之一，因此这部分分析事实应进入缓存。将这部分信息在首次编译时写入 package summary，可以把主要成本集中在首次产出阶段，并让后续缓存命中路径直接恢复分析输入，从而带来更直接的提速收益。

实施路径与开放问题

本章记录从当前实验状态过渡到正式实现的落地步骤，以及仍需进一步决策的问题。