Skip to main content
Article
Branch Elimination via Multi-Variable Condition Merging
Lecture Notes in Computer Science
  • William Kreahling, Florida State University
  • David Whalley, Florida State University
  • Mark Bailey, Hamilton College
  • Xin Yuan, Florida State University
  • Gang-Ryung Uh, Boise State University
  • Robert van Engelen, Florida State University
Document Type
Conference Proceeding
Publication Date
8-1-2003
Disciplines
Abstract
Conditional 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 Information
William 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/