MiCOMP：利用机器学习和优化子序列的自动编译优化框架

论文原文：MiCOMP: Mitigating the Compiler Phase-Ordering Problem Using Optimization Sub-Sequences and Machine Learning

现代编译器的多层级优化中，寻找优化的最佳排序（即 Phase-ordering）是一个极其复杂和困难的问题。 启发式方法无法处理为应用程序中每个代码段选择正确优化顺序的巨大复杂性。因此本文提出了
MiCOMP 自动优化框架 —— 利用机器学习和优化子序列。

优化子序列 (Optimization Sub-Sequences)： 将 LLVM -O3 设置中的优化 Pass 聚类到不同的簇中，对所有优化簇的完整序列的加速比进行推理。

应用程序表征

我们使用基于 PIN 的动态插桩框架。

  • 特征提取： 不使用静态语法分析，而是使用 MICA 这种微架构无关的方式表征应用程序。
  • 指标： MICA 框架参考 99 种不同的指标（特征），例如指令类型、内存寄存器访问模式、潜在的指令级并行性、动态控制流分析等。
  • 降维 (PCA)：
    • 这 99 个特征中有些是强相关的，使用全部特征会增加噪声，且模型过于复杂会极大增加时间复杂度。
    • 使用主成分分析 (PCA) 将 99 个相关特征转换成一组不相关的变量（主成分）。
    • 结果： 我们只使用 前 k=5k=5 个主成分，这已经捕获了所有训练数据中超过 98% 的总方差。

构建编译器子序列

优化依赖图

  • 背景： -O3 中有 157 个 Pass（超过 60 个唯一的 Pass）。
    • 分析 Pass (如 basicaa, memdep)：不直接转换代码，提供分析信息。
    • 转换 Pass (如 adce, licm, loop-rotate)：对代码执行优化。
  • 图构建： 用有向图 G=(V,E)G = (V, E) 表示优化级别 -O3 中的优化。
    • VV：表示优化的节点集。
    • EE：边集。如果一对优化在 -O3 序列中连续出现，则添加有向边。
    • 权重： 每对优化在序列中连续出现的次数。

聚类算法

  • 使用了 凝聚聚类 (Agglomerative Clustering) 算法。
  • 这是一种自动化的迭代方法，根据图的连接紧密程度，将相关的优化合并在一起，而不是依靠人工手动分组或随机分组。
  • 最终生成了 5 个优化簇 (Clusters)。

优化簇详情

子序列 (Sub-seq)包含的编译器 Passes
A-ipssccp -globalopt -deadargelim -simplycfg -functionattrs -argpromotion -sroa -jump-threading -reassociate -indvars -mldst-motion -lcssa -rpo-functionattrs -bdce -dse -inferattrs -prune-eh -alignment-from-assumptions -barrier -block-freq -loop-unswitch -branch-prob -demanded-bits -float2int -forceattrs -loop-idiom -globals-aa -gvn -loop-accesses -loop-deletion -loop-unroll -loop-vectorize -sccp -strip-dead-prototypes -inline -globaldce -constmerge
B-licm -mem2reg
C-loop-rotate -instcombine -loop-simplify
D-memcpyopt
E-loop-unswitch -adce -slp-vectorize -tailcallelim

Encoder

对于长度可变的优化序列，采用 独热编码 (One-Hot Encoding) 和 零填充 (Zero Padding) 的方法。

例如，对于 N=5,M=6N=5, M=6 的情况：

(A,B,B,D)→((1,0,0,0,0),(0,1,0,0,0),(0,1,0,0,0),(0,0,0,1,0),(0,0,0,0,0),(0,0,0,0,0))(A, B, B, D) \rightarrow ((1,0,0,0,0), (0,1,0,0,0), (0,1,0,0,0), (0,0,0,1,0), (0,0,0,0,0), (0,0,0,0,0))

预测建模

训练预测模型

  • 输入： (F,T)(F, T)
    • FF：将要优化的程序的特征向量。
    • TT：预测在该程序上表现良好的几个可能的编译器优化序列之一。
  • 输出： 预测 TT 应用于原始代码时应该实现的加速比。
  • 验证： 使用留一法交叉验证 (LOOCV) 避免过拟合。

特定于应用程序的预测

对待优化程序进行一次表征，再将特征与成千上万个候选序列组合，输入模型，快速预测哪些序列可能跑得快，从而进行筛选。

推荐系统启发式算法

仅仅按照模型预测的加速比排名来选择序列是不够的（容易陷入局部最优，因为前几名序列行为往往非常相似）。我们优先测试那些 预测分高，且与已测试过的序列不太相似 的序列。

  • 相似度计算： 使用 调整余弦相似度 (Adjusted Cosine Similarity)，相比余弦相似度能更好地排除评分标准带来的差异。

sim(i,j)=∑p∈P(Sp,i−Sˉp)(Sp,j−Sˉp)∑p∈P(Sp,i−Sˉp)2∑p∈P(Sp,j−Sˉp)2\text{sim}(i, j) = \frac{\sum_{p \in P}(S_{p,i} - \bar{S}_p)(S_{p,j} - \bar{S}_p)}{\sqrt{\sum_{p \in P}(S_{p,i} - \bar{S}_p)^2} \sqrt{\sum_{p \in P}(S_{p,j} - \bar{S}_p)^2}}

其中 Sp,iS_{p,i} 是序列 ii 应用于所有程序集 PP 中的程序 pp 时实现的加速比。

实验结果

实验设置

  • 硬件与基准： Intel Xeon 架构，CBench 套件（32 个应用程序）。
  • 编译器： LLVM v3.8。
  • 子序列： 将 -O3 的优化 Pass 聚类为 5 个子序列。
  • 特征： 使用 PCA 降维后的 5 维动态特征向量。

编译基线的选择

编译基线指的是，在应用 MiCOMP 推荐的优化序列之前，预先对代码应用的默认优化。结论： 相比预先运行任何的 -Ox 优化，不运行任何优化可以使 MiCOMP 的效果最好。

序列长度

长度增加能提升潜在加速比（长度 7 时最高达 1.45 倍）。但长度 6 既能保证优于 -O3，又避免了搜索空间过度膨胀（保持在可控范围内）。结论： 最大序列长度设为 66 是最佳平衡点。

预测准确性

  • 误差测量方法： 平均绝对误差 (MAE) 和 近似误差 (Approximation Error)。
  • K-Star 算法表现最好，平均误差率仅为 5%5\%。

运行效率和时间开销

  • 对比随机迭代 (RIC)：纯随机搜索需要 1.9 万次迭代才能穷尽空间找到最优解。
  • MiCOMP 效率：仅需测试 1 到 5 个预测结果就能超越 -O3。
    • 在 5 个预测内，平均比 -O3 提升 5%5\%。
    • 在 10 个预测内，平均提升 9%9\%。
  • 用户端开销极低，推理阶段（特征收集 + 模型预测 + 推荐算法） ≈16s+2s+12s\approx 16s + 2s + 12s。这仅相当于编译和运行程序 2 次的时间，完全在可接受范围内。

与中间序列预测的比较

中间序列预测是一种旧方法，它对每一步优化预测中间加速比。它的成本高（序列长度局限在 44 以内），且是贪心算法，易陷入局部最优。MiCOMP 的方法平均比旧的“中间预测”方法带来了 11%11\% 的加速比增益。