2014/09/26 by Roberto Castañeda Lozano, Lozano, Roberto Castañeda, Christian Schulte +1 · 2 voices · 1 citation
Computer Science · #FOS: Computer and information sciences #Programming Languages (cs.PL) #cs.PL
paper · pdf · doi:10.48550/arxiv.1409.7628
arxiv published 2014/09/26 · arxiv updated 2019/06/07
Register allocation (mapping variables to processor registers or memory) and instruction scheduling (reordering instructions to increase instruction-level parallelism) are essential tasks for generating efficient assembly code in a compiler. In the last three decades, combinatorial optimization has emerged as an alternative to traditional, heuristic algorithms for these two tasks. Combinatorial optimization approaches can deliver optimal solutions according to a model, can precisely capture trade-offs between conflicting decisions, and are more flexible at the expense of increased compilation time. This paper provides an exhaustive literature review and a classification of combinatorial optimization approaches to register allocation and instruction scheduling, with a focus on the techniques that are most applied in this context: integer programming, constraint programming, partitioned Boolean quadratic programming, and enumeration. Researchers in compilers and combinatorial optimization can benefit from identifying developments, trends, and challenges in the area; compiler practitioners may discern opportunities and grasp the potential benefit of applying combinatorial optimization.