Collaborative Research: Branch Elimination by Condition Merging

条件分支的成本很高。分支需要相当大比例的执行周期，因为它们频繁出现并取消流水线停顿。此外，分支会导致控制流中的分叉，这可能会阻止应用其他代码改进转换。我们计划开发基于路径配置文件的技术，在传统的标量处理器上用单个分支来取代两个或更多分支的执行。我们建议通过将两个或多个分支的条件合并为一个条件来提高性能。以前的方法已经完成了这样的条件合并，这些条件要么只涉及一个变量，要么需要特殊的硬件来将多个条件合并在一起。将开发技术来产生涉及多个变量的合并条件，该合并条件可用于绕过在传统处理器上测试原始条件集的代码。合并条件可能非常适合运行时优化系统，其在程序执行期间优化频繁执行的路径。

Conditional branches are expensive. Branches require a significantpercentage of the execution cycles since they occur frequently and cancause pipeline stalls. In addition, branches result in forks in thecontrol flow, which can prevent other code-improving transformationsfrom being applied. We plan to develop path profile-based techniquesfor replacing the execution of a set of two or more branches with asingle branch on a conventional scalar processor. We propose toimprove performance by merging the conditions of two or more branchesinto a single condition. Previous approaches have accomplishedsuch merging of conditions that have either only involved a singlevariable or have required special hardware to merge multipleconditions together. Techniques will be developed to produce a mergedcondition involving multiple variables that can be used to bypass thecode testing the original set of conditions on a conventional processor.Merging conditions may be very good fit for run-time optimizationsystems, which optimize frequently executed paths during the executionof a program.