[Zurück]

G. Barany:
"Optimal and Heuristic Global Code Motion for Minimal Spilling";
Vortrag: POPL 2013: 40th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Rom; 23.01.2013 - 25.01.2013.

The interaction of register allocation and instruction scheduling is a well-studied problem: Certain ways of arranging instructions within basic blocks reduce overlaps of live ranges, leading to the insertion of less costly spill code. However, there is little previous research on the extension of this problem to global code motion, i.e., the motion of instructions between blocks. We present an algorithm that models global code motion as an optimization problem with the goal to minimize overlaps between live ranges in order to minimize spill code.

Our approach analyzes the program to identify the live range overlaps for all possible placements of instructions in basic blocks, and all orderings of instructions within blocks. Using this information, we formulate an optimization problem to determine code motions and partial local schedules that minimize the overall cost of live range overlaps. We evaluate solutions of this optimization problem using integer linear programming, where feasible, and a simple greedy heuristic.

We conclude that performing global code motion with the sole goal of avoiding spills rarely leads to performance improvements because code is placed too conservatively. On the other hand, purely local optimal instruction scheduling for minimal spilling is effective at improving performance when compared to a heuristic scheduler for minimal register use.

compilers, code generation, register allocation, instruction scheduling, code motion

Projektleitung Andreas Krall:
Optimale Code Erzeugung für explizit parallele Prozessoren