Reducing the Cost of Comparisons within Conditional Transfers of Control

A significant percentage of execution cycles are devoted to performing conditional transfers of control, which occur frequently, cause pipeline flushes when mis-predicted and can prevent other code improving transformations from being applied. The work required for each conditional transfer of control can be broken into three portions: the comparison, the calculation of the branch target address and the actual transfer of control. Most of the research investigating the reduction of costs associated with these instructions have focused on the calculation of the branch target address or the actual transfer of control, overlooking the comparison portion. In this dissertation we propose several techniques to reduce the costs associated with the comparison portion of conditional transfers of control. The first technique attempts to merge multiple conditions, avoiding the execution of comparison and branch instructions. The other two methods decouple the definition of the values to be compared with the actual comparison itself. In the second technique the comparison becomes an effect that implicitly occurs whenever specified registers are assigned values, avoiding the execution of a separate comparison instruction. The third technique uses a similar concept, but instead of implicit comparisons, it uses a single comparison and branch instruction in conjunction with a comparison specification. This technique attempts to capture the advantages of common branching techniques used today, without the traditional disadvantages of using a single instruction to perform both the comparison and branch.