Premium
Branch elimination by condition merging
Author(s) -
Kreahling William C.,
Whalley David,
Bailey Mark W.,
Yuan Xin,
Uh GangRyung,
van Engelen Robert
Publication year - 2005
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.627
Subject(s) - computer science , control flow , profiling (computer programming) , parallel computing , algorithm , pipeline (software)
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. These sets of branches can include tests of multiple variables. For instance, the test if (p1 != 0 && p2 != 0) , which is testing for NULL pointers, can be replaced with if (p1 & p2 != 0) . Program profiling is performed to target condition merging along frequently executed paths. The results show that eliminating branches by merging conditions can significantly reduce the number of conditional branches executed in non‐numerical applications. Copyright © 2004 John Wiley & Sons, Ltd.