Collaborative Research: Branch Elimination by Condition Merging

协作研究：通过条件合并进行分支消除

• 批准号: 0208606
• 负责人: Mark Bailey
• 金额: $ 7万
• 依托单位: Hamilton College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0208606&HistoricalAwards=false
• 关键词: Collaborative; Research; Branch; Elimination; Condition

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.

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