A Novel Technique for Orchestration of Compiler Optimization Functions Using Branch and Bound Strategy

Code optimization involves the application of rules and algorithms to program code, with the goal of making it faster, smaller, more efficient, and so on. Applying the right compiler optimizations to a particular program can have a significant impact on program performance. The effectiveness of compiler optimizations is determined by the combination of target architectures, target application, and the compilation environment, which is defined by the setting of the compiler optimizations and compiler heuristics. Finding a compiler setting which is optimal requires a delicate tradeoff between these factors. Due to the non-linear interaction of compiler optimizations, however, determining the best setting is nontrivial. The trivial solution of trying all combinations of techniques would be infeasible, as it is of complexity O (2n) even for "n" on-off optimizations. There have been several proposed techniques that search the space of compiler options to find good solutions; however such approaches can be expensive. In current compilers, through command line arguments, the user must decide which optimizations are to be applied in a given compilation run. Clearly, this is not a long-term solution. As compiler optimizations get increasingly numerous and complex, this problem must find an automated solution. In this paper, a new technique is suggested, which prunes the large search space using branch and bound technique, so that only the area in search space which is most beneficial is given higher priority for further exploration whereas the least promising regions are straightaway pruned off, thus saving time by not exploring those regions which give a handful or negligible benefits. Also further probes of the search space tree are halted, once it is determined that the relative improvement in the time is not considerable as compared to the cost incurred for further probes. The time complexity of proposed method under worst case is found to be of O (n2) and under best case it can be even O (n).