[Zurück]

G. Barany:
"Balancing Global Code Motion and Register Allocation";
Vortrag: Gastvortrag IBM Research, Yorktown Heights, NY, USA (eingeladen); 13.11.2014.

Optimizing compilers for modern out-of-order architectures are careful to schedule instructions within basic blocks such that register pressure is not too large. This is the result of much past research into how to trade off scheduling against spilling and register allocation. However, such scheduling is only performed within basic blocks and does not take possibilities of moving instructions between blocks into account.

We present the first study that investigates the trade-off between spilling and global code motion. It is based on an integrated formulation of the global code motion and spilling problems. The algorithm can be tuned with a parameter that captures the trade-off between these subproblems: How much emphasis should be placed on avoiding spills, and how much on freedom of global code motion?

We vary the trade-off parameter to study its influence on the efficiency of the generated code. An evaluation on a suite of benchmark programs shows that the best results in most cases are obtained when the algorithm focuses on reducing spills even at the cost of global code motion potential; that is, loop invariant code motion is often not an optimization in practice. However, the trade-off is complex, and some programs perform better if freedom of code motion is preferred over avoiding spills. Exploring this trade-off can be useful in tuning applications for a given system.

compilers, code motion, instruction scheduling, register allocation