Create Register_Allocation.py

Register allocation problem: The task is to formalize the register allocation done as a part of a programming language compiler as a constraint satisfaction problem.  Register allocation is the process of allocating CPU registers to a set of temporaries, which are either usual variables in the language or temporary variables used to compute expressions etc. The input to a register allocator is a liveness graph (V, E) with a set of temporaries V and a set of edges E.  The edges     (s, t) ∈ E represent that temporaries s and t are live (used) at the same time, and thus should not be allocated the same CPU register. Note that, over the time, multiple temporaries can be allocated the same register.

 

Problem: We are given a set of temporaries V (e.g., V = {a, b, c, d, e}), a set of available CPU registers R (e.g., R = {1, 2, 3} and a liveness graph (V,E) where V is the set of temporaries and E is the following edges, each edge representing the relation “live at the same time”. (e.g., E = {(a, b), (a, c), (b, c), (c, d), (d, a), (d, e), (e, a)}).

Assignment: Formalize a CSP that represents the problem instance above, and where the solutions represent assignments of all temporaries to CPU registers, such that no temporaries are adjacent in E.

Program input format: A text file, where:

Line 1: Number of registers (registers are identified by integers, e.g., 1, 2, 3 …)

Line 2: Number of temporaries (identified by characters, a, b, c, d …)

Line 3: Number of edges in the liveness graph

Every line after line 3: One edge of the liveness graph (e.g., a, b)

 

Program output format: A text file, where:

Column 1: temporaries identifiers

Column 2: allocated register identifiers

If no solution exists: Print “No solution exists.”

Strategies to be implemented: DFS, Forward checking, Most constrained variable heuristic, Arc consistency checks, Back jumping (as many of these and any other you might design).