Collaborative Research: Branch Elimination by Condition Merging

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

• 批准号: 0208892
• 负责人: David Whalley
• 金额: $ 18万
• 依托单位: Florida State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2006-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0208892&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.

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