Colloquium Speaker

Speaker: David Whalley
Florida State University
Topic: Merging Conditional Branches
Date:Thursday, September 20, 2001
Time:11:00 AM
Place:Gould-Simpson, Room 701

Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 10:45 AM


Conditional branches are expensive. Branches require a significant percentage of the execution cycles since they occur frequently and can cause pipeline stalls. In addition, the presence of conditional branches can inhibit other code-improving transformations from being applied. I will present techniques for replacing the execution of a set of two or more branches with a single branch. First, profile information is gathered to determine the frequently executed paths in a program. Second, sets of conditional branches that can be merged together are detected. Third, the benefit of merging each set of branches is estimated. Finally, the control flow is restructured to perform the merging. The preliminary results show that merging conditional branches can reduce both the number of instructions executed and the conditional branches performed.