Extended Abstract Submission for PLDI’97 Near-optimal Intraprocedural Branch Alignment

Branch alignment reorders the basic blocks of a program to minimize pipeline penalties due to control-transfer instructions. Prior work in branch alignment has produced useful heuristic methods. We identify lower bounds on the run-time costs from aligned code and present an intraprocedural branch alignment algorithm that approaches the bound. We compare the control penalties and running times of our algorithm to older approaches and observe that both the greedy method and our method are close to the lower bound on control penalties, suggesting that greedy is good enough. Surprisingly, in actual execution our method produces programs that run noticeably faster than the greedy method. We also report results from training and testing on different data sets, validating that our results can be achieved in realworld usage. Training and testing on different data sets slightly reduced the benefits from branch alignment, but not enough to change the ranking of algorithms, and not enough to completely erase the benefits from branch alignment.