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.