Branch Elimination via Multi-Variable Condition MergingLecture Notes in Computer Science
Document TypeConference Proceeding
AbstractConditional branches are expensive. Branches require a significant percentage of execution cycles since they occur frequently and cause pipeline flushes when mispredicted. In addition, branches result in forks in the control flow, which can prevent other code-improving transformations from being applied. In this paper we describe profile-based techniques for replacing the execution of a set of two or more branches with a single branch on a conventional scalar processor. First, we gather profile information to detect the frequently executed paths in a program. Second, we detect sets of conditions in frequently executed paths that can be merged into a single condition. Third, we estimate the benefit of merging each set of conditions. Finally, we restructure the control flow to merge the sets that are deemed beneficial. The results show that eliminating branches by merging conditions can significantly reduce the number of conditional branches performed in non-numerical applications.
Citation InformationWilliam Kreahling, David Whalley, Mark Bailey, Xin Yuan, et al.. "Branch Elimination via Multi-Variable Condition Merging" Lecture Notes in Computer Science (2003)
Available at: http://works.bepress.com/gang-ryung_uh/11/