PGO如何插桩

[lfeng14]

• PGOInstrumentation.cpp 插桩逻辑梳理

1. 整体架构

这个文件实现了基于 MST (Minimum Spanning Tree) 的 PGO (Profile-Guided Optimization) 插桩，基于 Knuth & Stevenson 1973 年的论文。

核心思想：对于每个节点（除入口和出口外），入边计数之和等于出边计数之和。只需对不在生成树上的边进行插桩，树上的边计数可推导得出。

两个主要 Pass：

• PGOInstrumentationGen：插桩生成阶段，插入代码收集边缘计数和间接调用 profiling
• PGOInstrumentationUse：配置使用阶段，读取 profile 并注解分支权重

---

2. 核心插桩流程 (FunctionInstrumenter::instrument(), L932-1089)

步骤 1: 准备阶段

// 拆分间接分支的关键边
SplitIndirectBrCriticalEdges(F, /IgnoreBlocksWithoutPHI=/false, BPI, BFI);

步骤 2: 初始化 FuncPGOInstrumentation

FuncPGOInstrumentation<PGOEdge, PGOBBInfo> FuncInfo(
F, TLI, ComdatMembers, /CreateGlobalVar=/!IsCtxProf, BPI, BFI, LI,
InstrumentationType == PGOInstrumentationType::CSFDO,
shouldInstrumentEntryBB(), shouldInstrumentLoopEntries(),
PGOBlockCoverage);
这里构建 CFG 的最小生成树（MST）。

步骤 3: 函数入口覆盖模式（可选）

if (PGOFunctionEntryCoverage) {
// 只在入口块插入 llvm.instrprof.cover
Builder.CreateIntrinsic(Intrinsic::instrprof_cover, {...});
return;
}

步骤 4: 收集需要插桩的基本块

std::vector<BasicBlock *> InstrumentBBs;
FuncInfo.getInstrumentBBs(InstrumentBBs);

步骤 5: 上下文敏感 profiling 插桩（CTXPROF）

if (IsCtxProf) {
// 先统计调用点数量，再插入 llvm.instrprof.callsite
Visit([&TotalNumCallsites](auto *) { ++TotalNumCallsites; });
Visit([&](auto *CB) {
Builder.CreateCall(CSIntrinsic, {...});
});
}

步骤 6: 时间戳插桩（可选）

if (PGOTemporalInstrumentation) {
Builder.CreateIntrinsic(Intrinsic::instrprof_timestamp, {...});
}

步骤 7: 对每个选中的 BB 插入计数增量

for (auto *InstrBB : InstrumentBBs) {
IRBuilder<> Builder(InstrBB, InstrBB->getFirstNonPHIOrDbgOrAlloca());
Builder.CreateIntrinsic(
PGOBlockCoverage ? Intrinsic::instrprof_cover
: Intrinsic::instrprof_increment,
{NormalizedNamePtr, CFGHash, Builder.getInt32(NumCounters),
Builder.getInt32(I++)});
}

步骤 8: 插桩 select 指令

FuncInfo.SIVisitor.instrumentSelects(&I, NumCounters, Name, FuncInfo.FunctionHash);

步骤 9: 值 profiling (Value Profiling)

// 对间接调用目标、内存操作大小等进行插桩
for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) {
for (VPCandidateInfo Cand : FuncInfo.ValueSites[Kind]) {
Builder.CreateCall(Intrinsic::instrprof_value_profile, {...});
}
}

---

3. 关键辅助逻辑

select 指令插桩 (instrumentOneSelectInst, L1767-1780)

void SelectInstVisitor::instrumentOneSelectInst(SelectInst &SI) {
// 插入 llvm.instrprof.increment_step
// Step 是条件值的零扩展
auto *Step = Builder.CreateZExt(SI.getCondition(), Int64Ty);
Builder.CreateIntrinsic(Intrinsic::instrprof_increment_step, {...});
}

如何选择插桩位置 (getInstrBB, L843-893)

• 假边：插桩在真实 BB
• SrcBB 有单一后继：插桩在 SrcBB
• DestBB 有单一前驱：插桩在 DestBB
• 关键边：必须先拆分，然后在新 BB 插桩

---

4. 插桩的 Intrinsic 函数

┌───────────────────────────────┬────────────────────────────┐
│           Intrinsic           │            用途            │
├───────────────────────────────┼────────────────────────────┤
│ llvm.instrprof.increment      │ 标准计数增量               │
├───────────────────────────────┼────────────────────────────┤
│ llvm.instrprof.increment_step │ select 指令的条件计数      │
├───────────────────────────────┼────────────────────────────┤
│ llvm.instrprof.cover          │ 覆盖模式（单字节计数）     │
├───────────────────────────────┼────────────────────────────┤
│ llvm.instrprof.value_profile  │ 值 profiling（间接调用等） │
├───────────────────────────────┼────────────────────────────┤
│ llvm.instrprof.timestamp      │ 时间戳                     │
├───────────────────────────────┼────────────────────────────┤
│ llvm.instrprof.callsite       │ 上下文敏感 profiling       │
└───────────────────────────────┴────────────────────────────┘

---

5. 配置使用阶段 (PGOInstrumentationUse)

对应流程：

1. getRecord() - 从 profile 读取记录
2. setInstrumentedCounts() - 设置已插桩 BB 的计数值
3. populateCounters() - 从已插桩的边推导所有 BB 的计数
4. setBranchWeights() - 设置分支权重元数据
5. annotateValueSites() - 注解值 profiling 站点

• 示例代码：

cat example.c
int func() { 
   for (int i = 0; i <100; i++) {
        if (i % 2 == 0) {
          return 1;
        }
    }
   return 0;
}

clang -O0 -fprofile-generate  -S  -emit-llvm example.c -o pgo.exe  
clang -O0  -S  -emit-llvm example.c -o nopgo.exe  

opt   -passes=dot-cfg pgo.exe
dot .main.dot -Tpng -o cfg.png

further reading

- Knuth & Stevenson 1973