Eliminating false phase interactions to reduce optimization phase order search space

Compiler optimization phase ordering is a longstanding problem, and is of particular relevance to the performance-oriented and cost-constrained domain of embedded systems applications. Optimiza-tion phases are known to interact with each other, enabling and disabling opportunities for successive phases. Therefore, varying the order of applying these phases often generates distinct out-put codes, with different speed, code-size and power consumption characteristics. Most current approaches to address this issue fo-cus on developing innovative methods to selectively evaluate the vast phase order search space to produce a good (but, potentially suboptimal) representation for each program. In contrast, the goal of this work is to study and identify com-mon causes of optimization phase interactions across all phases, and then devise techniques to eliminate them, if and when possi-ble. We observe that several phase interactions are caused by false register dependence during many optimization phases. We further find that depending on the implementation of optimization phases, even an increased availability of registers may not be able to sig-nificantly reduce such false register dependences. We explore the potential of cleanup phases, such as register remapping and copy propagation, at reducing false dependences. We show that innova-tive implementation and application of these phases to reduce false register dependences not only reduces the size of the phase order search space substantially, but can also improve the quality of code generated by optimizing compilers