DSA数据结构与算法工程实践
关于
LLVM/Sample profile inference · profi

用最小费用流修复采样执行计数

LLVM 的 profi 将采样执行计数转成最小费用流问题，用 Moore–Bellman–Ford 的队列松弛变体寻找增广路，再还原基本块与分支的执行次数。

llvmorg-19.1.0图处理与编译核验 2026-10-12
相关概念
Bellman–Ford图队列

工程问题#

采样可能遗漏基本块，也可能使一个块的执行次数与流入、流出分支的计数不一致。编译器需要符合控制流约束的计数，用于后续优化，同时尽量减少对已采样数值的调整。

实际实现#

profi 为增加或减少采样计数设置费用，建立带容量的流网络。最小费用流求解器在残量网络中反复寻找增广路：距离变小时更新前驱，并把目标节点加入待处理队列。反向边的费用与正向边相反，允许撤回先前分配的流量，因此路径搜索必须处理负费用边。这里的最短路径用于求解计数修正问题，并不是寻找程序执行时经过的最短分支。

处理流程#

  1. 采样 profile 加载器在启用 profi 时收集基本块计数，调用推断器
  2. 把控制流与计数修正代价编码为带容量、费用及反向边的网络
  3. 通过队列松弛寻找最小费用增广路，沿路径或候选 DAG 推送流量
  4. 从流网络提取基本块和分支计数，随后进行孤立分量连接等后处理

源码片段#

固定版本 · 原文摘录
llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.hllvmorg-19.1.0 · L924–L937
查看原文件
924template <typename BT>925void SampleProfileLoaderBaseImpl<BT>::propagateWeights(FunctionT &F) {926  // Flow-based profile inference is only usable with BasicBlock instantiation927  // of SampleProfileLoaderBaseImpl.928  if (SampleProfileUseProfi) {929    // Prepare block sample counts for inference.930    BlockWeightMap SampleBlockWeights;931    for (const auto &BI : F) {932      ErrorOr<uint64_t> Weight = getBlockWeight(&BI);933      if (Weight)934        SampleBlockWeights[&BI] = Weight.get();935    }936    // Fill in BlockWeights and EdgeWeights using an inference algorithm.937    applyProfi(F, Successors, SampleBlockWeights, BlockWeights, EdgeWeights);
SampleProfileLoaderBaseImpl::propagateWeights

加载器在启用 profi 时收集采样计数，并把基本块和边权交给推断器；这是算法进入编译优化流程的实际调用点。

CPPApache-2.0 WITH LLVM-exception
llvm/lib/Transforms/Utils/SampleProfileInference.cppllvmorg-19.1.0 · L1346–L1356
查看原文件
1346  // Create and apply an inference network model1347  auto InferenceNetwork = MinCostMaxFlow(Params);1348  initializeNetwork(Params, InferenceNetwork, Func);1349  InferenceNetwork.run();13501351  // Extract flow values for every block and every edge1352  extractWeights(Params, InferenceNetwork, Func);13531354  // Post-processing adjustments to the flow1355  auto Adjuster = FlowAdjuster(Params, Func);1356  Adjuster.run();
llvm::applyFlowInference

推断器建立最小费用流网络、运行求解、提取计数，然后调用后处理；最短路径是这条计数修正流程中的求解步骤。

CPPApache-2.0 WITH LLVM-exception
llvm/lib/Transforms/Utils/SampleProfileInference.cppllvmorg-19.1.0 · L137–L152
查看原文件
137    Edge SrcEdge;138    SrcEdge.Dst = Dst;139    SrcEdge.Cost = Cost;140    SrcEdge.Capacity = Capacity;141    SrcEdge.Flow = 0;142    SrcEdge.RevEdgeIndex = Edges[Dst].size();143144    Edge DstEdge;145    DstEdge.Dst = Src;146    DstEdge.Cost = -Cost;147    DstEdge.Capacity = 0;148    DstEdge.Flow = 0;149    DstEdge.RevEdgeIndex = Edges[Src].size();150151    Edges[Src].push_back(SrcEdge);152    Edges[Dst].push_back(DstEdge);
MinCostMaxFlow::addEdge

每条正向边都配有费用取反的反向边。增广后反向边可以获得残量容量，因此后续路径搜索不能假定所有边权非负。

CPPApache-2.0 WITH LLVM-exception
llvm/lib/Transforms/Utils/SampleProfileInference.cppllvmorg-19.1.0 · L270–L291
查看原文件
270      for (uint64_t EdgeIdx = 0; EdgeIdx < Edges[Src].size(); EdgeIdx++) {271        auto &Edge = Edges[Src][EdgeIdx];272        if (Edge.Flow < Edge.Capacity) {273          uint64_t Dst = Edge.Dst;274          int64_t NewDistance = Nodes[Src].Distance + Edge.Cost;275          if (Nodes[Dst].Distance > NewDistance) {276            // Update the distance and the parent node/edge277            Nodes[Dst].Distance = NewDistance;278            Nodes[Dst].ParentNode = Src;279            Nodes[Dst].ParentEdgeIndex = EdgeIdx;280            // Add the node to the queue, if it is not there yet281            if (!Nodes[Dst].Taken) {282              Queue.push(Dst);283              Nodes[Dst].Taken = true;284            }285          }286        }287      }288    }289290    return Nodes[Target].Distance != INF;291  }
MinCostMaxFlow::findAugmentingPath

只处理仍有残量容量的边；发现更小费用时更新距离和前驱，并将节点加入队列继续传播。该函数通过这种队列松弛执行 Moore–Bellman–Ford 变体。

CPPApache-2.0 WITH LLVM-exception

四段原文依次给出工程入口、求解与后处理、反向边以及松弛操作。队列初始化和网络特定剪枝位于同一函数 233–268 行，增广迭代及流量更新在相邻函数中；摘录没有包含完整求解器。

收益与取舍#

工程分析

带来的收益

  • 以流量守恒约束统一修正基本块与分支计数，并用费用表达哪些调整应尽量避免
  • 负费用反向边允许撤回先前的流量分配，支持最小费用流的迭代求解

付出的代价

  • 需要额外构建残量网络并多次搜索增广路；原文件给出的最坏界为 O(FVE)，F 为最大流值，V、E 为网络顶点和边数，而非原始代码行数
  • 剪枝依赖该网络没有负权环等不变量；这个函数不是通用图的负权环检测接口
  • 得到的是遵循模型与费用参数的估计计数，不能补回未采集的真实执行轨迹

可比较的选择

基于已知计数逐轮传播同一加载器保留了传播分支，可根据已知块和边推断未知计数；它不使用这里的最小费用流模型来统一选择修正代价。

Dijkstra 配合势函数重标权最小费用流也可先维护势函数，使可用残量边的重标权费用非负后采用 Dijkstra；不能把含负费用反向边的当前网络直接交给普通 Dijkstra。

版本与适用范围#

对应 LLVM llvmorg-19.1.0 的采样 profile 推断路径，需启用 SampleProfileUseProfi。算法属于用于最小费用流的 Moore–Bellman–Ford 变体，采用队列、网络特定剪枝和可选的 DAG 增广；不等同于教科书中固定 V−1 轮扫描所有边的实现。流求解后还有调整步骤，不能把整个 profi 的最终结果简单称作未改动的最小费用流解。

参考来源#

源码、官方文档与原始论文
01
采样 profile 加载器的 profi 入口

llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h · SampleProfileLoaderBaseImpl::propagateWeights

源码llvmorg-19.1.0
02
基本块与分支计数的转换和回填

llvm/include/llvm/Transforms/Utils/SampleProfileInference.h · SampleProfileInference::apply

源码llvmorg-19.1.0
03
Moore–Bellman–Ford 实现说明

llvm/lib/Transforms/Utils/SampleProfileInference.cpp · MinCostMaxFlow

源码llvmorg-19.1.0
04
残量网络的队列松弛与剪枝约束

llvm/lib/Transforms/Utils/SampleProfileInference.cpp · MinCostMaxFlow::findAugmentingPath

源码llvmorg-19.1.0
05
流网络求解与后处理调用链

llvm/lib/Transforms/Utils/SampleProfileInference.cpp · llvm::applyFlowInference

源码llvmorg-19.1.0

相关实现与比较#

4 个相关案例
↑↓ 选择 Enter 打开Esc 关闭
6 个匹配案例