Avoiding Conditional Branches by Code Replication

Abstract

On-chip instruction caches are increasing in size.Compiler writers are exploiting this fact by applying a variety of optimization that improve the execution performance of a program at the expense of increasing its code size.This paper describes a new optimization that can be used to avoid conditional branches by replicating code.The central idea is to determine if there are paths where the result of a conditional branch will be known and to replicate code to exploit it.Algorithms are described for detecting when branches are avoidable, for restructuring the control flow to avoid these branches, and for positioning the replicated blocks in the restructured code.The results indicate that the optimization can be frequently applied with reductions in both the number of instructions executed and total instruction cache work.