The CSE302 Compilers final project.

Our team is composed of:

• Natali Gogishvili
• Victor Lasocki
• Romain Poggi

We are implementing the project on Register Allocation.

python3 bxc.py "bxfile.bx

You can use different options here:

-test: runs the tests we have built (not recently updated for later parts.)

-tac : generates a tac file too

-uce : performs uce optimization

-jthreading: performs the jthreading optimization

-regcoal : performs the register coalescing stretch goal

-verbose/ -v: makes the program verbose (shows options)

-all: runs all options except test

You have to either give a bx file as input, or the -test tag. You cannot turn on both at the same time.

The project focuses on implementing register allocation for TAC (Three Address Code) in the custom compiler. The key objectives include Crude SSA generation and minimization, construction of the interference graph, register allocation by graph coloring using max cardinality search, and optional register coalescing as a stretch goal.

We have managed to implement every but the "ETAC to x64" stretch goal. However, we have included our attempt at it at the end of the bxasmgen file. We have left detailed comments on what we have tried to do for it, and what was working.

We added a new Reporter so that we could print errors in color so that they stand out.

We also added some testing routines, although they were mostly to visualize the cfg, and other things. It was not updated to test later parts of the project.

Relevant Functions:

• compute_livein_sets(cfg: CFG) -> Dict[str, Set[str]]
• initialize_dicts() -> None
• algo_node(name: str) -> list
• get_successors(block: CFGNode) -> list
• def_inst(instr: TAC) -> set
• use_inst(instr: TAC | Tuple) -> set[str] | None
• are_equal(d_sets1, d_sets2) -> bool
• are_equal_lists(l1, l2) -> bool

Overview: The compute_livein_sets function computes the LiveIn set for a given CFG. It initializes dictionaries for livein sets and local definitions per block. The iterative algorithm is employed with the help of functions like initialize_dicts and algo_node. Helper functions like get_successors, def_inst, and use_inst assist in liveness analysis. The are_equal and are_equal_lists functions are utility functions for comparing dictionaries and lists, respectively. This subsection aims to perform crude SSA generation by analyzing the liveness of temporaries within each block and across the CFG.

Relevant Functions:

• set_phi_generic(cfg: CFG) -> None
• version_defs(cfg: CFG) -> None
• version_args_and_complete_phi(cfg: CFG) -> None
• extract(input_string: str) -> Tuple

Overview: The set_phi_generic function introduces phi TAC instructions for each livein temporary, initializing the 'arguments' field. version_defs uniquely versions each definition of a temporary across the entire CFG. version_args_and_complete_phi updates uses within blocks and fills in phi function arguments for CFG edges. The extract function is a utility to parse versioned temporaries. This subsection aims to minimize the SSA form by introducing phi functions and uniquely versioning temporaries.

Relevant Classes and Functions:

• InterferenceGraph
• compute_interference_graph(cfg: CFG) -> InterferenceGraph

Overview: The InterferenceGraph class represents an undirected interference graph where each node is a temporary, and an edge between two nodes signifies interference. The compute_interference_graph function constructs the interference graph from the Control Flow Graph (CFG) in minimal SSA form. It analyzes live-outs, live-ins, and instructions to establish interference edges between temporaries. This graph is essential for subsequent steps in the register allocation process.

Relevant Functions:

• max_cardinality_search(graph: InterferenceGraph) -> list

Overview: The max_cardinality_search function, utilizing max-cardinality search, returns a list of nodes sorted by decreasing cardinality. This ordering is vital for subsequent stages of the register allocation process, contributing to a simplified elimination order.

Relevant Functions:

• greedy_coloring(G:InterferenceGraph, elim_ordering:list[str],col:dict[str,int])-> dict[str,int]

Overview: The greedy_coloring function uses a maximal cardinality search and greedy coloring approach. Given an interference graph, elimination ordering, and a pre-colored dictionary, it assigns colors to temporaries. The output is a dictionary mapping temporaries to colors.

Relevant Functions:

• alt_register_allocation(cfg:CFG,pre_coloring:dict[str,str|int],spilled:list[str],reg_coal:bool=False)-> CFG

Overview: The alt_register_allocation function performs register allocation using maximal cardinality search and greedy coloring. It iteratively spills variables until less than 13 colors are used. It handles pre-coloring, spilled variables, and register coalescing based on specified conditions.

Overview: The allocation record is generated by the alt_register_allocation function, providing information about stack space for spilled temporaries and the mapping of registers to temporaries.

Relevant Functions:

• register_coalescing(cfg:CFG,IntGraph:InterferenceGraph,col:dict[str,int])-> CFG

Overview: The register_coalescing function performs register coalescing based on an interference graph (IntGraph) and a coloring (col) of temporaries. It processes the instruction sequence generated from the interference graph, identifying copy instructions for potential coalescing. If the source and destination of a copy instruction have the same color, the instruction is removed. If conditions allow, a new temporary is introduced with a different color, connected to the neighbors of the source and destination in the interference graph. The source and destination are then replaced with the new temporary in the instruction sequence.

Relevant Functions:

• ssa_destruction(cfg:CFG) -> None
• compute_liveout_sets(cfg: CFG) -> Dict[str, Set[str]]

Overview:

The ssa_destruction function performs SSA destruction on the provided CFG. It traverses each basic block, looking for phi instructions, and replaces them with copy instructions based on the set of versions. This step is crucial for moving from SSA form to a more conventional form.

Relevant Function:

• compute_liveout_sets(cfg: CFG) -> Dict[str, Set[str]]

Overview: The compute_liveout_sets function computes the LiveOut set for each block in a given CFG. It initializes dictionaries for LiveIn and LiveOut sets based on block structure and iteratively updates these sets. The process considers uses, conditional jumps, and jumps to accurately determine LiveOut sets.