论文精读（补二）

RollBin: Reducing code-size via loop rerolling at binary level

题目和作者

• 关键概念
  • code-size
  • loop rerolling
  • binary level
• 葛天傲师兄

摘要

• 需求：在资源受限设备上，代码大小是一个关系到减少内存占用的重要考量。现在大多数解决方案都在编译层面，缺少二进制层面的减少代码大小的解决方案
• 贡献：提出 RollBin，推进了这个问题
  • 实现步骤和机制：略
• 实验：效果拔群
  • Benchmark：SPEC2006/2017、MiBench
  • 真实应用场景

简介

• 代码大小会影响指令缓存，进而影响内存占用
• 减少代码大小方法很多，通过编译层面的解决方案在一些场景中很受限
  • 二进制代码部署时没有考虑代码大小优化
  • 因为商业原因等没有源代码
  • 较难被反汇编
  • 嵌入式设备更依赖汇编，没有源代码
• RollBin 主要关注循环展开
• 实现步骤和机制：略
• 贡献
  • 强调了二进制级别减少代码大小的重要性，设计了 RollBin 来系统地定义和重卷被展开的循环
  • 和 SOTA 相比引入了更多的循环重卷的机会
  • 实验很有效

背景和动机

• 编译基本流程

循环展开

• 好处
  • 减少分支判断开销
  • 有利于后续一些 Pass
• 关键概念
  • 展开因子：循环被展开的次数
  • 重卷循环：即优化前的原循环
• 例子

重卷减少代码大小

• 分析例子
• 挑战
  • 二进制代码信息支离破碎，没有 IR 或者源代码的结构
  • 指令调度使得重复的循环体指令被打乱
  • 循环间可能有依赖，阻碍迭代的恢复
• 对于挑战一，有工作已经解决了，但对于挑战二三，当前的工作效果不够

二进制级循环重卷

识别循环

• 定位分支跳转指令
• 找到循环变量
• 利用循环变量回溯找到循环中的相关地址操作
  • 这些地址形式只有偏移不同
  • 偏移通常是成序列的 e.g.，0x4，0x8…
  • 还原指令顺序
• 确定展开因子

锚定迭代

• 遍历所有和展开因子相关的内存操作
• 确定指令所属的迭代次数

聚合指令

• 根据数据依赖传播指令所属的迭代
• 如果一条指令根据手机依赖推断同时属于两个迭代，则应该属于较大的迭代

转化代码

• 确定迭代重建是否是同构的
  • 指令数一样
  • 对应指令 op 一样
  • 只包含跳转指令或者和循环变量相关的指令
• 重卷循环
• 广泛的循环重卷可能使性能剧烈下降，所以 RollBin 提供了性能分析来指导循环重卷
  • 阈值启发式

实现

• 工具
  • LLVM
  • BOLT
  • Linux Perf
• 改了 BOLT 的二进制重写

评估方法论

实验环境

• 指标：CPU（频率，L1/L2/L3），系统（内核版本），Perf 版本，LLVM 版本

• Benchmarks

  • SPEC2006
  • SPEC2017
  • MiBench
  • TSVC
  • TFLite
  • BLASFEO

• 编译参数选择

设计和指标

• Baseline：LLVM
• 对比：SubDDG、SuffixTree、RoLAG、RollBin
• 指标
  • 代码大小：减少比例
  • 性能：减速比
  • 可执行文件大小

结果和分析

• 代码大小

• 对比 IR 级别重卷

• 真实应用

• 可执行文件大小

• 性能

• 性能和代码大小间的权衡可以进一步研究

相关工作

• 代码大小优化
• 二进制优化

结论

• 基本同摘要
• 未来方向：处理多层循环