链接时优化：LTO 与 ThinLTO

// math_util.c
int square(int x) { return x * x; }        // 三行，理想情况下应被内联

// main.c
int square(int x);                          // 只有声明，没有定义
int compute(int n) { return square(n) + 1; }

# GCC 全程序 LTO
gcc -O2 -flto -o app main.o util.o math.o
# 链接时可以看到 LTO 阶段: lto1 进程把 GIMPLE 全部读进来

阶段一: 编译 (并行)
  每个 .c  ->  .o (含 LLVM IR) + .o.summary (函数摘要)

阶段二: thin link (轻量, 单进程)
  读取所有 summary，构建全局摘要索引
  对每个模块决定: 应该导入哪些外部函数 (import list)
  输出: 每个模块的导入清单 (imports file)

阶段三: 后端 (并行)
  对每个模块: 读入自己的 IR + 按 import list 导入函数体
             -> 内联、优化、代码生成 -> 机器码 .o

阶段四: 常规链接

# Clang + lld 的 ThinLTO 构建
clang -O2 -flto=thin -c main.c -o main.o
clang -O2 -flto=thin -c util.c -o util.o
clang -fuse-ld=lld -flto=thin -o app main.o util.o \
      -Wl,--thinlto-cache-dir=/tmp/thinlto-cache

class FunctionSummary:
    def __init__(self, name):
        self.name = name
        self.instruction_count = 0        # 函数体规模，用于判断内联收益
        self.is_inlinable = True          # 是否允许被导入 (noinline / optnone 会置 False)
        self.linkage = "external"         # 外部可见性，internal 才容易被导入
        self.callees = []                 # 调用的其他函数 (带 profile 计数)
        self.callers = []                 # 被谁调用
        self.aliasee = None               # 别名目标
        self.profile_count = 0            # PGO 计数，决定热冷
        self.import_depth = 0             # 已导入的深度，防止无限递归导入

def should_import(caller, callee, caller_summary, callee_summary):
    """导入决策的启发式: 只有「被内联后大概率有收益」才导入"""
    if not callee_summary.is_inlinable:
        return False
    if callee_summary.instruction_count > INLINE_THRESHOLD:   # 太大，导入不划算
        return False
    # 只有「调用点被实际执行」才值得导入
    if callee_summary.profile_count == 0 and has_pgo(caller_summary):
        return False
    # 调用者没有引用它，就不导入
    if callee not in caller_summary.callees:
        return False
    return True

def compute_imports(index, module, max_depth=1):
    """为单个模块计算导入集合"""
    imports = set()
    frontier = list(module.defined_functions)

    for depth in range(max_depth):
        next_frontier = []
        for fn in frontier:
            for callee in index.summaries[fn].callees:
                if callee in imports or callee in module.defined_functions:
                    continue
                if should_import(fn, callee,
                                 index.summaries[fn],
                                 index.summaries[callee]):
                    imports.add(callee)
                    next_frontier.append(callee)   # 仅当允许更深导入时才有用
        frontier = next_frontier
    return imports

# 缓存命中率的观察: 连续两次构建，第二次应大量命中
clang -flto=thin -Wl,--thinlto-cache-dir=/tmp/tc -o app *.o
ls /tmp/tc | head
# 缓存键 = 模块 IR 哈希 + 导入清单哈希 + 优化选项

def stable_import_order(imports):
    """按 (优先级, 函数名) 稳定排序，保证同一输入产出同一结果"""
    return sorted(imports, key=lambda f: (-f.hotness, f.name))

# Clang: 调整 ThinLTO 并行度与优化级别
clang -flto=thin -Wl,--thinlto-jobs=16 \
      -Wl,--lto-O2 \
      -Wl,--thinlto-cache-dir=/tmp/tc -o app *.o

# GCC: 自动选择分区数与并行度
gcc -O2 -flto=auto -flto-partition=balanced -o app *.o

// 无 LTO: 只能走虚表，无法内联
  vptr = load [obj]
  fn   = load [vptr + 16]
  call fn              ; 间接调用，分支预测不友好

// ThinLTO: 摘要索引证明该类型全程序唯一实现
  call Shape::area     ; 直接调用，可继续内联

def cross_module_devirtualize(index, call_site):
    """跨模块去虚化: 借助全局类型层次摘要判断唯一实现"""
    base = call_site.receiver_type
    impls = index.vtable_implementations.get(base, [])
    if len(impls) == 1 and not index.type_is_extensible(base):
        # 全程序只有唯一实现，且类型不可被外部扩展
        return impls[0]              # 可改写为直接调用
    return None                      # 保持间接调用

# Cargo.toml: 发布构建启用 ThinLTO
[profile.release]
lto = "thin"          # fat 对应 Full LTO，off 关闭
codegen-units = 1     # 与 LTO 配合可获得最佳跨单元优化，代价是并行度下降
opt-level = 3

# 排查: 确认 LTO 是否真的生效
clang -flto=thin -Wl,--plugin-opt=-print-imports -o app *.o 2>&1 | head
# 输出示例:
#   Importing square from math.o into main.o
#   Importing fast_path from util.o into main.o