4

我一直在阅读各种编译器的功能，并且遇到了据报道许多编译器执行的术语“积极优化”。例如，LLVM 引用了以下编译时优化功能：

  • 内存/指针特定
  • 循环变换
  • 数据流
  • 算术
  • 死码消除
  • 内联

这具体是什么意思？假设您有以下代码片段，您如何优化生成的字节码以比编译器生成的代码运行得更快？我对优化 JIT 驱动的运行时（如 C#、Java 和 Flash）的字节码特别感兴趣。这很棘手，因为 JIT 仅支持处理器通常执行的操作码的子集，这限制了您可以执行的优化量。尽管如此，我还是很想知道什么是可能的，以及究竟是什么转换可以推动 VM 的极限。

虚构的代码块：

for (i = 0; i < 100; i++){
    in = dataIn[i];
    if ((in % 5) == 0){
        out = ((in / 2) >> 16) - 10;
    }else{
        out = ((in << 5) / 2) * 50 + 10;
    }
    dataOut[i] = out;
}

编译器生成的近似伪代码，用于基于堆栈的 JIT VM，例如 Flash Player：（请原谅我的任何错误，这完全是手写的！）

// i = 0
label: "forInit"
   push 0
   writeTo "i"

// while i < 100
label: "forStart"
   push "i"
   push 100
   jumpIfMoreThan "forEnd"

       // in = dataIn[i];
       push "i"
       push "dataIn"
       readProp
       saveTo "in"

       // if ((in % 5) == 0)
       push "in"
       push 5
       mod
       push 0
       jumpIfNotEquals "ifPart2"
       label: ifPart1

           // out = ((in / 2) >> 16) - 10;
           push "in"
           push 2
           divide
           push 16
           rightshift
           push 10
           minus
           writeTo "out"
           goto "ifEnd"

       // else
       label: ifPart2

           // out = ((in << 5) / 2) * 50 + 10;
           push "in"
           push 5
           leftshift
           push 2
           divide
           push 50
           multiply
           push 10
           add
           writeTo "out"

       // dataOut[i] = out;
       label: ifEnd
           push "out"
           push "i"
           push "dataOut"
           writeProp

       // i++
       push "i"
       increment
       writeTo "i"

   // while i < 100
   goto "forStart"
label: "forEnd"
4

3 回答 3

6

我也一直在研究这个，LLVM 执行的转换的完整列表，在标题下组织：

  • 死代码删除
    • 积极的死代码消除
    • 死代码消除
    • 死论点消除
    • 死型消除
    • 死指令消除
    • 死店消除
    • 死亡全球消除
    • 删除死循环
  • 不需要的数据删除
    • 从模块中删除所有符号
    • 去除未使用符号的调试信息
    • 剥离未使用的函数原型
    • 剥离所有 llvm.dbg.declare 内在函数
    • 从模块中去除所有符号，除了 dbg 符号
    • 合并重复的全局常量
    • 删除未使用的异常处理信息
  • 内联函数
    • 合并函数
    • 部分内联
    • 功能集成/内联
  • 循环优化
    • 闭环 SSA 表单传递
    • 循环不变代码运动
    • 将循环提取到新函数中
    • 最多将一个循环提取到一个新函数中
    • 循环强度降低
    • 旋转循环
    • 规范化自然循环
    • 展开循环
    • 取消切换循环
  • 杂项
    • 将“通过引用”参数提升为标量
    • 组合指令以在基本块内形成向量指令
    • 轮廓引导的基本块放置
    • 打破 CFG 中的关键边
    • 优化代码生成
    • 简单的常数传播
    • 推导函数属性
    • 全局变量优化器
    • 全局值编号
    • 规范化归纳变量
    • 插入用于边缘轮廓分析的仪器
    • 为边缘轮廓插入最佳仪器
    • 合并冗余指令
    • 内部化全局符号
    • 过程间常数传播
    • 过程间稀疏条件常数传播
    • 跳线程
    • 降低非原子形式的原子内在特性
    • 较低的调用和展开，用于展开的代码生成器
    • 将 SwitchInst 降低到分支
    • 提升内存注册
    • MemCpy 优化
    • 统一功能出口节点
    • 重新关联表达式
    • 将所有值降级到堆栈槽
    • 聚合的标量替换 (DT)
    • 稀疏条件常数传播
    • 简化众所周知的库调用
    • 简化 CFG
    • 代码下沉
    • 将 sret 参数提升为多个 ret 值
    • 尾声消除
    • 尾部复制
于 2012-06-17T16:02:53.457 回答
2

尽管这不能回答您的问题，但我遇到了 C++ 编译器为优化生成的机器代码而执行的以下转换：

  • 强度减少--- 用作数据索引的迭代变量以与数据单元大小匹配的速率递增
  • 隐藏参数--- 返回结构的函数实际上将其写入隐藏参数指向的区域
  • 整数除法--- 在已知除数的情况下，某些公式可用于更有效地评估整数除法
  • Floating Conditions --- 将浮点条件转化为复杂的指令序列设置和查询浮点状态
  • 复杂数学 --- 复杂的乘法或除法转换为库调用
  • 本机例程--- memcpy()、memset()、strcmp() 或 strlen() 操作转换为 rep mov、rep sto、rep zcmp 或 rep zscas
  • 短路--- 在基本块树中评估复杂条件
  • 工会歧义--- 关于工会成员的信息丢失
  • Copy Fragmentation --- 大的双精度值或聚合值逐字复制
  • 测试碎片——长整数值的条件由对该值的各个单词的单独测试组成
  • Switch Fragmentation --- switch 语句被值上的条件嵌套替换
  • Loop Header Copy --- 一个循环增加了一个决定是否进入循环的条件
  • 循环展开--- 循环被循环体的复制副本替换
  • 函数内联 ---函数调用被函数体的副本替换
于 2012-06-17T15:39:49.170 回答
1

以下是编译器可以进行的两个简单优化：

out = ((i / 2) >> 16) - 10;

可以简化为

out = (i >> 17) - 10;

和

out = ((i << 5) / 2) * 50 + 10;

可以简化为

out = (i << 4) * 50 + 10;

要回答您的问题“您如何优化生成的字节码以比编译器生成的字节码运行得更快？” 这是另一个经过优化的字节码版本。

// i = 0
label: "forInit"
   push 0
   writeTo "i"

// while i < 100
label: "forStart"
   push "i"
   push 100
   jumpIfMoreThan "forEnd"

       // in = dataIn[i];
       push "i"
       push "dataIn"
       readProp
       saveTo "in"

       // if ((in % 5) == 0)
       push "in"
       push 5
       mod
       push 0
       jumpIfNotEquals "ifPart2"
       label: ifPart1
           // optimization: remove unnecessary /2
           // out = ((in / 2) >> 16) - 10;
           push "in"
           push 17
           rightshift
           push 10
           minus
           // optimization: don't need out var since value on stack
           // dataOut[i] = out;
           push "i"
           push "dataOut"
           writeProp
           // optimization: avoid branch to common loop end 
           // i++
           push "i"
           increment
           writeTo "i"
           goto "forStart"

       // else
       label: ifPart2
           // optimization: remove unnecessary /2
           // out = ((in << 5) / 2) * 50 + 10;
           push "in"
           push 4
           leftshift
           push 50
           multiply
           push 10
           add
           // optimization: don't need out var since value on stack
           // dataOut[i] = out;
           push "i"
           push "dataOut"
           writeProp
           // optimization: avoid branch to common loop end 
           // i++
           push "i"
           increment
           writeTo "i"
           goto "forStart"
label: "forEnd"
于 2012-06-17T15:57:47.760 回答