Necessary Conditions for Constraint-based Register Allocation and Instruction Scheduling

Sammanfattning: Compilers translate code from a source language to a target language. Generating optimal code is thereby considered as infeasible due to the runtime overhead. A rather new approach is the implementation of a compiler by using Constraint Programming: in a constraint-based system, a problem is modeled by defining variables and relations among these variables (that is, constraints) that have to be satisfied. The application of a constraint-based compiler offers the potential of generating robust and optimal code. The performance of the system depends on the modeling choices and constraints that are enforced. One way of refining a constraint model is the addition of implied constraints. Implied constraints model logically redundant relations among variables, but provide distinct perspectives on the problem that might help to cut down the search effort. The actual impact of implied constraints is difficult to foresee, as they are tightly connected with the modeling choices made otherwise.This thesis investigates and evaluates a set of implied constraints that address register allocation (decision where to store data) and instruction scheduling (decision when to execute instructions) within an existing constraint-based compiler back-end. It provides insights into the impact on the code generation problem and discusses assets and drawbacks of the set of introduced constraints