IMPLEMENTING THE COMPILER MIDDLE END

 

INTRODUCTION TO THE COMPILER MIDDLE END

The compilation process transforms human-readable source code into executable machine instructions through a series of well-defined stages. This transformation is traditionally divided into three major phases: the frontend, the middle end, and the backend. Each phase has distinct responsibilities and operates on different representations of the program. The frontend is responsible for parsing the source code and performing semantic analysis, producing an Abstract Syntax Tree that captures the program's structure and meaning. The backend takes a low-level intermediate representation and generates machine-specific assembly or object code. Between these two phases lies the middle end, which is the focus of this article.

The middle end serves as the optimization powerhouse of the compiler. It receives the semantically validated Abstract Syntax Tree from the frontend and transforms it into an optimized intermediate representation suitable for code generation. The middle end is where the compiler performs the majority of its optimization work, applying transformations that improve program performance, reduce code size, and eliminate redundancies. These optimizations are typically machine-independent, meaning they improve the program's efficiency regardless of the target architecture.

Understanding the middle end is crucial for anyone building a compiler or working on performance-critical code generation. The middle end must balance multiple competing goals: it must preserve the program's semantics exactly while transforming the code, it must apply optimizations that provide measurable benefits, and it must produce output that the backend can efficiently translate to machine code. This article will explore how to design and implement a compiler middle end that achieves these goals.

THE ROLE AND RESPONSIBILITIES OF THE MIDDLE END

The middle end occupies a unique position in the compiler pipeline. It receives an Abstract Syntax Tree that has been enriched with semantic information from the frontend. This semantic information includes type annotations, symbol table entries, scope information, and resolved references. The AST represents the program's structure in a way that closely mirrors the source language's syntax, which makes it excellent for semantic analysis but less suitable for optimization and code generation.

The first major responsibility of the middle end is to transform the AST into an Intermediate Representation that is better suited for analysis and transformation. This IR should be lower-level than the AST, exposing operations more explicitly and making control flow and data flow more apparent. The IR should also be designed to facilitate optimization, with properties that make it easy to analyze dependencies, identify redundancies, and apply transformations safely.

Once the IR has been constructed, the middle end performs a series of optimization passes. Each pass analyzes the IR and applies specific transformations to improve the code. Some optimizations focus on eliminating unnecessary computations, such as constant folding and dead code elimination. Others focus on improving data locality and reducing memory traffic, such as loop optimizations and register promotion. Still others focus on exposing parallelism or reducing instruction count through techniques like common subexpression elimination and strength reduction.

The middle end must also construct and maintain various analysis data structures that support optimization. Control Flow Graphs represent the possible execution paths through the program, making it possible to reason about which code executes under which conditions. Data Flow Analysis tracks how values flow through the program, identifying where variables are defined and used. Dominance information helps determine which basic blocks must execute before others, which is essential for many optimizations.

After applying optimizations, the middle end prepares the IR for the backend. In our case, this means converting the optimized IR into LLVM IR, which is the input format expected by the LLVM backend. LLVM IR is a well-designed, SSA-based intermediate representation with a rich ecosystem of optimization passes and code generators for many target architectures. By targeting LLVM IR, our middle end can leverage LLVM's sophisticated backend infrastructure.

DESIGNING THE INTERMEDIATE REPRESENTATION

The choice of Intermediate Representation is one of the most important design decisions in a compiler. The IR serves as the common language that all optimization passes work with, so its design profoundly affects what optimizations are possible and how efficiently they can be implemented. A well-designed IR makes optimizations straightforward to implement and reason about, while a poorly designed IR can make even simple optimizations complex and error-prone.

For our compiler middle end, we will design a Three-Address Code style IR that is simple yet powerful enough to represent all the constructs in our source language. Three-Address Code gets its name from the constraint that each instruction has at most three addresses: two for operands and one for the result. This constraint makes the IR explicit about the order of operations and eliminates complex nested expressions, which simplifies analysis and transformation.

Each instruction in our IR will have an opcode that specifies the operation to perform, along with operands that specify the inputs and outputs. For example, an addition operation might be represented as "t1 = add a, b" where "add" is the opcode, "a" and "b" are the source operands, and "t1" is the destination where the result is stored. By making each operation explicit and limiting the number of operands, we create an IR that is easy to analyze and transform.

Our IR will use an unlimited number of virtual registers or temporaries to hold intermediate values. These temporaries are not physical machine registers but rather abstract storage locations that will later be mapped to actual registers or memory locations by the backend. Using virtual registers eliminates the need to worry about register allocation during optimization, allowing us to focus on improving the program's logic without being constrained by hardware limitations.

Here is a simple example showing how a high-level expression is translated to our IR:

Source code:

result = (a + b) * (c - d)

IR representation:

t1 = add a, b

t2 = sub c, d

t3 = mul t1, t2

result = mov t3

Notice how the complex nested expression has been broken down into a sequence of simple operations, each with explicit operands and results. This explicit representation makes it easy to see the data dependencies between operations and to identify opportunities for optimization.

REPRESENTING CONTROL FLOW IN THE IR

While Three-Address Code handles straight-line computation well, we also need to represent control flow constructs like conditionals and loops. Our IR will use labels and conditional/unconditional jumps to represent control flow. A label marks a position in the code that can be the target of a jump, while jump instructions transfer control to a labeled position.

For conditional execution, we use conditional branch instructions that test a condition and jump to a label if the condition is true. For example, an if statement in the source language might be translated to:

Source code:

if (x > 0) {

    y = x * 2

} else {

    y = 0

}

IR representation:

t1 = cmp_gt x, 0

br_false t1, else_label

t2 = mul x, 2

y = mov t2

jmp end_label

else_label:

y = mov 0

end_label:

The "cmp_gt" instruction compares x with 0 and stores the boolean result in t1. The "br_false" instruction branches to else_label if t1 is false. The unconditional "jmp" instruction skips over the else block when the then block completes. This representation makes the control flow explicit and easy to analyze.

Loops are represented similarly using labels and conditional branches. A while loop, for instance, has a label at the top where the loop condition is tested, a conditional branch that exits the loop when the condition becomes false, and an unconditional jump at the bottom that returns to the top of the loop.

BASIC BLOCKS AND THE CONTROL FLOW GRAPH

To facilitate analysis and optimization, we organize the IR into basic blocks. A basic block is a maximal sequence of instructions with a single entry point and a single exit point. Control enters a basic block only at its first instruction and leaves only at its last instruction. There are no branches into the middle of a basic block and no branches out of the middle.

Basic blocks are fundamental to compiler optimization because they represent units of code that execute atomically. If the first instruction of a basic block executes, then all instructions in that block will execute in sequence. This property simplifies analysis because we can reason about the block as a whole rather than considering every possible execution path through individual instructions.

The Control Flow Graph is a directed graph where nodes represent basic blocks and edges represent possible control flow between blocks. An edge from block A to block B indicates that control might transfer from the end of A to the beginning of B. The CFG makes the program's control flow structure explicit and enables sophisticated analysis and optimization algorithms.

Constructing the CFG from the IR is straightforward. We identify basic block boundaries by finding leaders, which are instructions that begin basic blocks. The first instruction in the program is always a leader. Any instruction that is the target of a branch is a leader. Any instruction immediately following a branch is a leader. Once we have identified all leaders, we create basic blocks by grouping instructions from each leader up to (but not including) the next leader.

After creating basic blocks, we add edges to the CFG. For each basic block, we examine its last instruction. If the last instruction is an unconditional jump, we add an edge to the target block. If it is a conditional branch, we add edges to both the target block and the fall-through block. If it is not a branch, we add an edge to the immediately following block.

Here is an example showing basic block formation:

IR instructions:

1:  x = mov 5

2:  y = mov 10

3:  t1 = cmp_gt x, 0

4:  br_false t1, L2

5:  t2 = mul x, 2

6:  y = mov t2

7:  jmp L3

8:  L2:

9:  y = mov 0

10: L3:

11: z = add x, y

Basic blocks:

BB1: instructions 1-4 (entry block)

BB2: instructions 5-7 (then block)

BB3: instructions 8-9 (else block)

BB4: instructions 10-11 (merge block)

CFG edges:

BB1 -> BB2 (conditional branch when true)

BB1 -> BB3 (conditional branch when false)

BB2 -> BB4 (unconditional jump)

BB3 -> BB4 (fall-through)

This CFG structure enables us to perform control flow analysis and apply optimizations that span multiple basic blocks.

DATA FLOW ANALYSIS FOUNDATIONS

Data flow analysis is the foundation of many compiler optimizations. It determines how data values flow through the program, tracking where variables are defined, where they are used, and what values they might hold at different program points. This information is essential for optimizations like constant propagation, dead code elimination, and register allocation.

Data flow analysis operates on the Control Flow Graph and computes information at each program point. A program point is typically the position before or after an instruction. For each program point, we want to know certain facts about the program state, such as which variables are live (might be used later) or which variables hold constant values.

Data flow analysis problems are typically formulated as iterative fixed-point computations. We start with initial values for each program point and then repeatedly update these values based on the values at neighboring program points until no more changes occur. The analysis converges when we reach a fixed point where further iterations produce no new information.

There are two main directions for data flow analysis: forward and backward. Forward analysis propagates information from the entry of the CFG toward the exit, following the direction of program execution. Backward analysis propagates information from the exit toward the entry, working against the direction of execution. The choice of direction depends on the specific analysis problem.

For forward analysis, we compute the information at the entry of each basic block based on the information at the exit of its predecessors. We then propagate this information through the block's instructions to compute the information at the block's exit. For backward analysis, we work in the opposite direction, computing exit information based on successors and propagating backward through instructions.

Let us consider a simple example of forward data flow analysis for constant propagation. At each program point, we want to know which variables definitely hold constant values. We start by assuming no variables are constant at the program entry. As we process each instruction, we update our knowledge:

Instruction: x = mov 5

Before: {}

After: {x -> 5}

Instruction: y = add x, 3

Before: {x -> 5}

After: {x -> 5, y -> 8}

Instruction: z = add x, y

Before: {x -> 5, y -> 8}

After: {x -> 5, y -> 8, z -> 13}

When control flow paths merge, we must combine information from multiple predecessors. If a variable has the same constant value on all incoming paths, it remains constant. If it has different values on different paths, it is no longer constant.

IMPLEMENTING REACHING DEFINITIONS ANALYSIS

Reaching definitions analysis is a fundamental data flow analysis that determines, for each program point, which assignments (definitions) might reach that point. A definition reaches a point if there is a path from the definition to that point along which the variable is not redefined. This information is crucial for optimizations like constant propagation and dead code elimination.

For reaching definitions, we perform forward data flow analysis. Each basic block has a set of definitions that reach its entry (IN set) and a set that reach its exit (OUT set). We also compute for each block the set of definitions it generates (GEN set) and the set it kills (KILL set).

The GEN set for a block contains all definitions created within that block. The KILL set contains all definitions that are invalidated by assignments in the block. For example, if a block contains the assignment "x = 5", this generates a new definition of x and kills all previous definitions of x.

The data flow equations for reaching definitions are:

OUT[B] = GEN[B] union (IN[B] - KILL[B])

IN[B] = union of OUT[P] for all predecessors P of B

These equations state that the definitions reaching the exit of a block are those generated in the block plus those reaching the entry that are not killed. The definitions reaching the entry are the union of definitions reaching the exit of all predecessor blocks.

We solve these equations iteratively. We initialize IN[entry] to the empty set and all other IN sets to the universal set (all possible definitions). We then repeatedly update the sets according to the equations until no changes occur. Here is a conceptual implementation:

def compute_reaching_definitions(cfg):

    # Initialize

    for block in cfg.blocks:

        block.gen_set = compute_gen_set(block)

        block.kill_set = compute_kill_set(block)

        block.in_set = set() if block.is_entry else all_definitions

        block.out_set = set()

    

    # Iterate until fixed point

    changed = True

    while changed:

        changed = False

        for block in cfg.blocks:

            # Compute IN from predecessors

            new_in = set()

            for pred in block.predecessors:

                new_in = new_in.union(pred.out_set)

            

            # Compute OUT

            new_out = block.gen_set.union(new_in - block.kill_set)

            

            # Check for changes

            if new_in != block.in_set or new_out != block.out_set:

                changed = True

                block.in_set = new_in

                block.out_set = new_out

    

    return cfg

This analysis provides the foundation for many optimizations by telling us which definitions might affect each use of a variable.

IMPLEMENTING LIVE VARIABLE ANALYSIS

Live variable analysis is another fundamental data flow analysis that determines, for each program point, which variables might be used before being redefined. A variable is live at a point if there exists a path from that point to a use of the variable along which the variable is not redefined. This information is essential for dead code elimination and register allocation.

Live variable analysis is a backward data flow analysis because liveness depends on future uses. We propagate information from uses backward to definitions. Each basic block has a set of variables that are live at its entry (IN set) and a set that are live at its exit (OUT set). We also compute for each block the set of variables it uses before defining (USE set) and the set it defines (DEF set).

The data flow equations for live variables are:

IN[B] = USE[B] union (OUT[B] - DEF[B])

OUT[B] = union of IN[S] for all successors S of B

These equations state that a variable is live at the entry of a block if it is used in the block before being defined, or if it is live at the exit and not defined in the block. A variable is live at the exit of a block if it is live at the entry of any successor block.

We solve these equations iteratively, working backward through the CFG. We initialize OUT[exit] to the empty set (no variables are live after the program exits) and all other OUT sets to the empty set. We then repeatedly update the sets until convergence:

def compute_live_variables(cfg):

    # Initialize

    for block in cfg.blocks:

        block.use_set = compute_use_set(block)

        block.def_set = compute_def_set(block)

        block.in_set = set()

        block.out_set = set() if block.is_exit else set()

    

    # Iterate until fixed point

    changed = True

    while changed:

        changed = False

        for block in reversed(cfg.blocks):  # Process in reverse order

            # Compute OUT from successors

            new_out = set()

            for succ in block.successors:

                new_out = new_out.union(succ.in_set)

            

            # Compute IN

            new_in = block.use_set.union(new_out - block.def_set)

            

            # Check for changes

            if new_in != block.in_set or new_out != block.out_set:

                changed = True

                block.in_set = new_in

                block.out_set = new_out

    

    return cfg

Live variable analysis enables us to identify dead code (assignments to variables that are not live) and to allocate registers efficiently (by knowing when a register's value is no longer needed).

CONSTANT FOLDING AND PROPAGATION

Constant folding and constant propagation are fundamental optimizations that evaluate constant expressions at compile time rather than runtime. Constant folding evaluates operations whose operands are all constants, replacing the operation with its computed result. Constant propagation tracks variables that hold constant values and replaces uses of those variables with the constants themselves.

These optimizations are valuable because they eliminate runtime computation and expose opportunities for further optimization. When we replace a variable with a constant, we might enable additional constant folding in expressions that use that variable. When we eliminate a computation, we might make the code that computed its operands dead, enabling dead code elimination.

Constant folding operates on individual instructions. When we encounter an instruction whose operands are all constant, we evaluate the operation and replace the instruction with a simple assignment of the result. For example:

Before constant folding:

t1 = add 5, 3

t2 = mul t1, 2

After constant folding:

t1 = mov 8

t2 = mul t1, 2

The addition of two constants has been evaluated at compile time, replacing the add instruction with a move of the constant result.

Constant propagation builds on constant folding by tracking which variables hold constant values and replacing uses of those variables with the constants. We use reaching definitions analysis to determine which definition reaches each use, and we check whether that definition assigns a constant value. If so, we can replace the use with the constant:

After constant propagation:

t1 = mov 8

t2 = mov 16

Now the multiplication has also been folded because we propagated the constant value of t1.

Implementing constant propagation requires careful handling of control flow. When multiple definitions of a variable reach a use, we can only propagate if all definitions assign the same constant value. If different paths assign different constants, the variable is not constant at that point.

Here is a conceptual implementation of constant propagation:

def constant_propagation(cfg):

    # Compute reaching definitions

    compute_reaching_definitions(cfg)

    

    # Track constant values

    constants = {}

    

    for block in cfg.blocks:

        for instr in block.instructions:

            # Try to fold operands

            if instr.op1 in constants:

                instr.op1 = constants[instr.op1]

            if instr.op2 in constants:

                instr.op2 = constants[instr.op2]

            

            # Try to fold the operation

            if is_constant(instr.op1) and is_constant(instr.op2):

                result = evaluate(instr.opcode, instr.op1, instr.op2)

                instr.opcode = 'mov'

                instr.op1 = result

                instr.op2 = None

                constants[instr.dest] = result

            elif instr.opcode == 'mov' and is_constant(instr.op1):

                constants[instr.dest] = instr.op1

            else:

                # Destination is not constant

                if instr.dest in constants:

                    del constants[instr.dest]

This optimization can dramatically reduce the amount of runtime computation, especially in programs with many compile-time constants.

DEAD CODE ELIMINATION

Dead code elimination removes instructions whose results are never used. An instruction is dead if it computes a value that is not live at any subsequent program point. Eliminating dead code reduces program size, improves cache utilization, and can expose opportunities for further optimization.

Dead code can arise from several sources. Programmers sometimes write code that is never executed or whose results are never used. More commonly, dead code is created by other optimizations. When constant propagation eliminates uses of a variable, the code that computed that variable's value becomes dead. When we simplify control flow, entire blocks of code might become unreachable.

To identify dead code, we use live variable analysis. After computing which variables are live at each program point, we examine each instruction. If an instruction assigns to a variable that is not live after the instruction, the instruction is dead and can be removed. We must be careful, however, to preserve instructions that have side effects beyond their assignment, such as function calls or I/O operations.

Here is an example of dead code elimination:

Before optimization:

x = add 5, 3      // x is not used anywhere

y = mul 2, 4      // y is used later

z = add x, y      // z is not used anywhere

return y

After live variable analysis:

// At each instruction, we know which variables are live after

x = add 5, 3      // x is not live after this instruction

y = mul 2, 4      // y is live (used in return)

z = add x, y      // z is not live after this instruction

return y

After dead code elimination:

y = mul 2, 4

return y

Both the assignment to x and the assignment to z have been eliminated because those variables are not live.

Dead code elimination must be applied iteratively because removing one dead instruction can make other instructions dead. When we eliminate an assignment, the variables used in that assignment might become dead if they have no other uses. This creates a cascade effect where eliminating one piece of dead code exposes more dead code.

Here is a conceptual implementation:

def eliminate_dead_code(cfg):

    changed = True

    while changed:

        changed = False

        compute_live_variables(cfg)

        

        for block in cfg.blocks:

            new_instructions = []

            for instr in block.instructions:

                # Keep instruction if it has side effects

                if has_side_effects(instr):

                    new_instructions.append(instr)

                # Keep instruction if destination is live

                elif instr.dest in block.live_out:

                    new_instructions.append(instr)

                else:

                    # Instruction is dead

                    changed = True

            

            block.instructions = new_instructions

This optimization is particularly effective when combined with other optimizations in an iterative framework.

COMMON SUBEXPRESSION ELIMINATION

Common subexpression elimination identifies computations that are performed multiple times with the same operands and eliminates the redundant computations. Instead of recomputing the same expression, we save the result of the first computation and reuse it for subsequent occurrences. This optimization reduces the number of operations performed and can significantly improve performance.

For CSE to be valid, we must ensure that the operands of the expression have not changed between the first computation and the subsequent use. This requires data flow analysis to track available expressions. An expression is available at a program point if it has been computed on all paths reaching that point and its operands have not been modified since the computation.

Consider this example:

Before CSE:

a = b + c

d = b * 2

e = b + c     // Same expression as line 1

f = b * 2     // Same expression as line 2

After CSE:

a = b + c

d = b * 2

e = a         // Reuse result from line 1

f = d         // Reuse result from line 2

The redundant computations have been replaced with simple copies of previously computed values.

Implementing CSE requires computing available expressions at each program point. We use forward data flow analysis similar to reaching definitions. For each basic block, we track which expressions are computed in the block (GEN set) and which expressions are invalidated because their operands are modified (KILL set).

The data flow equations are:

OUT[B] = GEN[B] union (IN[B] - KILL[B])

IN[B] = intersection of OUT[P] for all predecessors P of B

Note that we use intersection rather than union for IN because an expression is only available if it is available on all paths, not just some paths.

Once we have computed available expressions, we can perform CSE. When we encounter an expression that is available, we find the temporary that holds the result of the previous computation and replace the current computation with a copy from that temporary:

def common_subexpression_elimination(cfg):

    compute_available_expressions(cfg)

    

    for block in cfg.blocks:

        expr_to_temp = {}  # Map expressions to temporaries

        

        for instr in block.instructions:

            expr = (instr.opcode, instr.op1, instr.op2)

            

            # Check if expression is available

            if expr in block.available_in and expr in expr_to_temp:

                # Replace with copy from previous result

                instr.opcode = 'mov'

                instr.op1 = expr_to_temp[expr]

                instr.op2 = None

            else:

                # Record this computation

                expr_to_temp[expr] = instr.dest

This optimization is particularly effective in loops where the same expressions are computed repeatedly.

LOOP OPTIMIZATIONS

Loops are often the performance bottleneck in programs because they execute their bodies many times. Small improvements to loop efficiency can have large impacts on overall program performance. The middle end applies several specialized optimizations to loops, including loop-invariant code motion, strength reduction, and loop unrolling.

Loop-invariant code motion identifies computations within a loop that produce the same result on every iteration. These computations are moved outside the loop so they execute only once rather than on every iteration. A computation is loop-invariant if its operands are either constants or variables defined outside the loop.

Consider this example:

Before loop-invariant code motion:

for i = 0 to n do

    x = a + b      // a and b are not modified in the loop

    y = x * i

    array[i] = y

end for

After loop-invariant code motion:

x = a + b          // Moved outside the loop

for i = 0 to n do

    y = x * i

    array[i] = y

end for

The computation of x has been hoisted out of the loop because it does not depend on the loop variable i.

To implement loop-invariant code motion, we must first identify loops in the CFG. We use dominance analysis to find natural loops, which are strongly connected regions of the CFG with a single entry point (the loop header). Once we have identified loops, we analyze each instruction in the loop body to determine whether it is loop-invariant.

An instruction is loop-invariant if all of its operands are either constants, defined outside the loop, or defined by other loop-invariant instructions within the loop. We compute loop-invariant instructions iteratively, starting with instructions whose operands are constants or defined outside the loop, then adding instructions whose operands are all loop-invariant.

Strength reduction replaces expensive operations with cheaper equivalent operations. A common case is replacing multiplication by a loop-invariant with addition. For example, if we are computing i times c on each iteration where c is loop-invariant, we can instead maintain a variable that we increment by c on each iteration:

Before strength reduction:

for i = 0 to n do

    x = i * c

    use(x)

end for

After strength reduction:

x = 0

for i = 0 to n do

    use(x)

    x = x + c

end for

Multiplication has been replaced with addition, which is typically faster on most processors.

CONVERTING TO STATIC SINGLE ASSIGNMENT FORM

Static Single Assignment form is an intermediate representation property where each variable is assigned exactly once. When a variable would be assigned multiple times in the original program, SSA creates distinct versions of the variable for each assignment. This property simplifies many optimizations by making def-use chains explicit and by eliminating the need to track multiple definitions reaching a use.

Converting to SSA form requires inserting phi functions at points where control flow merges. A phi function selects a value based on which control flow path was taken. For example, if variable x is assigned in both branches of an if statement, we insert a phi function after the if to merge the two versions:

Before SSA conversion:

if condition then

    x = 1

else

    x = 2

end if

y = x + 3

After SSA conversion:

if condition then

    x1 = 1

else

    x2 = 2

end if

x3 = phi(x1, x2)

y = x3 + 3

The phi function x3 = phi(x1, x2) means that x3 takes the value x1 if control came from the then branch, or x2 if control came from the else branch.

The algorithm for SSA conversion has two main phases. First, we determine where to insert phi functions. We insert a phi function for variable x at the beginning of basic block B if B is in the dominance frontier of any block that assigns to x. The dominance frontier of a block A is the set of blocks where A's dominance ends, meaning blocks that are not dominated by A but have a predecessor that is dominated by A.

Second, we rename variables to create unique versions. We perform a depth-first traversal of the dominator tree, maintaining a stack of current definitions for each variable. When we encounter an assignment to x, we push a new version onto x's stack. When we encounter a use of x, we replace it with the version on top of x's stack. When we process a phi function, we create a new version for its destination.

Here is a conceptual implementation of variable renaming:

def rename_variables(block, stacks):

    # Process phi functions

    for phi in block.phi_functions:

        new_version = new_variable_version(phi.var)

        phi.dest = new_version

        push(stacks[phi.var], new_version)

    

    # Process instructions

    for instr in block.instructions:

        # Rename uses

        if instr.op1 in stacks:

            instr.op1 = top(stacks[instr.op1])

        if instr.op2 in stacks:

            instr.op2 = top(stacks[instr.op2])

        

        # Rename definition

        if instr.dest:

            new_version = new_variable_version(instr.dest)

            instr.dest = new_version

            push(stacks[instr.dest], new_version)

    

    # Fill in phi function operands in successors

    for succ in block.successors:

        for phi in succ.phi_functions:

            phi.add_operand(block, top(stacks[phi.var]))

    

    # Recursively process dominated blocks

    for child in block.dominated_blocks:

        rename_variables(child, stacks)

    

    # Pop versions added in this block

    for phi in block.phi_functions:

        pop(stacks[phi.var])

    for instr in block.instructions:

        if instr.dest:

            pop(stacks[instr.dest])

SSA form is particularly valuable because it makes many optimizations simpler and more powerful. In SSA form, each use of a variable has exactly one reaching definition, which simplifies constant propagation, dead code elimination, and many other analyses.

INTEGRATING WITH THE LLVM BACKEND

After applying optimizations, the middle end must convert the optimized IR into LLVM IR, which serves as the input to the LLVM backend. LLVM IR is a low-level, typed, SSA-based representation that is well-suited for further optimization and code generation. The LLVM framework provides a rich set of optimization passes and code generators for many target architectures.

LLVM IR is organized into modules, which contain functions, which contain basic blocks, which contain instructions. Each LLVM instruction is strongly typed, and LLVM performs type checking to ensure the IR is well-formed. The IR supports a rich type system including integers of various sizes, floating-point numbers, pointers, arrays, and structures.

Converting our IR to LLVM IR requires mapping our constructs to LLVM equivalents. Our virtual registers become LLVM virtual registers (which LLVM calls SSA values). Our basic blocks become LLVM basic blocks. Our instructions are translated to corresponding LLVM instructions.

Here is an example of how our IR maps to LLVM IR:

Our IR:

t1 = add a, b

t2 = mul t1, 2

return t2

LLVM IR:

%t1 = add i32 %a, %b

%t2 = mul i32 %t1, 2

ret i32 %t2

The LLVM IR is similar but includes type information (i32 for 32-bit integers) and uses percent signs to denote SSA values.

To generate LLVM IR, we use the LLVM C++ API or one of its language bindings. We create an LLVM module, add function declarations, create basic blocks, and emit instructions. Here is a conceptual example using a Python-like pseudocode:

def emit_llvm_ir(optimized_ir, module):

    # Create function

    func_type = llvm.FunctionType(llvm.Int32Type(), [llvm.Int32Type(), llvm.Int32Type()])

    func = llvm.Function(module, func_type, "calculate")

    

    # Create entry basic block

    entry_block = func.append_basic_block("entry")

    builder = llvm.IRBuilder(entry_block)

    

    # Map our temporaries to LLVM values

    value_map = {}

    

    # Emit instructions

    for instr in optimized_ir:

        if instr.opcode == 'add':

            op1 = get_llvm_value(instr.op1, value_map, builder)

            op2 = get_llvm_value(instr.op2, value_map, builder)

            result = builder.add(op1, op2, instr.dest)

            value_map[instr.dest] = result

        elif instr.opcode == 'mul':

            op1 = get_llvm_value(instr.op1, value_map, builder)

            op2 = get_llvm_value(instr.op2, value_map, builder)

            result = builder.mul(op1, op2, instr.dest)

            value_map[instr.dest] = result

        elif instr.opcode == 'return':

            value = get_llvm_value(instr.op1, value_map, builder)

            builder.ret(value)

Once we have generated LLVM IR, we can invoke LLVM's optimization passes and code generation to produce optimized machine code for the target architecture.

OPTIMIZATION PASS ORDERING AND ITERATION

The order in which optimization passes are applied significantly affects the final code quality. Some optimizations enable others, while some optimizations can undo the effects of previous optimizations if applied in the wrong order. Determining the optimal pass ordering is a complex problem that requires understanding the interactions between different optimizations.

A common strategy is to organize optimizations into phases. Early phases focus on simplification and canonicalization, transforming the IR into a standard form that makes subsequent optimizations more effective. Middle phases apply the main optimization transformations like constant propagation, CSE, and dead code elimination. Late phases perform cleanup and prepare the code for the backend.

Many optimizations are more effective when applied iteratively. For example, constant propagation might expose dead code, and eliminating that dead code might expose more opportunities for constant propagation. Running these optimizations in a loop until no more changes occur can produce better results than running each optimization once.

However, we must be careful to ensure that the optimization loop terminates. Some optimizations might create opportunities for themselves indefinitely, leading to an infinite loop. We typically limit the number of iterations or track whether each iteration made progress, stopping when no optimization makes any changes.

Here is a conceptual framework for an optimization pipeline:

def optimize_ir(ir):

    # Phase 1: Simplification

    ir = simplify_cfg(ir)

    ir = canonicalize_expressions(ir)

    

    # Phase 2: Main optimizations (iterate to fixed point)

    max_iterations = 10

    for iteration in range(max_iterations):

        old_ir = copy(ir)

        

        ir = constant_propagation(ir)

        ir = eliminate_dead_code(ir)

        ir = common_subexpression_elimination(ir)

        ir = loop_optimizations(ir)

        

        if ir == old_ir:

            break  # No changes, we've reached a fixed point

    

    # Phase 3: Cleanup

    ir = eliminate_dead_code(ir)

    ir = simplify_cfg(ir)

    

    # Phase 4: SSA conversion for LLVM

    ir = convert_to_ssa(ir)

    

    return ir

This framework ensures that optimizations are applied in a sensible order and that we iterate until we reach a fixed point.

HANDLING FUNCTION CALLS AND INTERPROCEDURAL OPTIMIZATION

So far we have focused on optimizing individual functions, but real programs consist of many functions that call each other. Function calls introduce challenges for optimization because they create dependencies between functions and can have side effects that are not immediately visible.

When we encounter a function call in the IR, we must conservatively assume that the call might modify any global variables and any variables whose addresses have been taken. This assumption limits the effectiveness of optimizations like constant propagation and CSE across function calls. To optimize more aggressively, we need interprocedural analysis that examines the entire program.

Interprocedural optimization analyzes multiple functions together to determine the effects of function calls. For example, we can analyze which global variables a function might modify, which parameters it might modify through pointers, and whether it has any side effects. This information allows us to optimize more aggressively around function calls.

A simple form of interprocedural optimization is function inlining, where we replace a function call with a copy of the called function's body. Inlining eliminates the overhead of the call and exposes the function's code to optimization in the caller's context. However, inlining must be applied carefully because it can significantly increase code size.

Here is an example of function inlining:

Before inlining:

function add_and_double(x, y)

    temp = add x, y

    result = mul temp, 2

    return result

end function

function main()

    a = 5

    b = 3

    c = call add_and_double(a, b)

    return c

end function

After inlining:

function main()

    a = 5

    b = 3

    temp = add a, b

    c = mul temp, 2

    return c

end function

The call to add_and_double has been replaced with its body, and now the entire computation is visible in main, enabling further optimization.

MEMORY OPTIMIZATION AND ALIASING ANALYSIS

Memory operations are often a performance bottleneck, and optimizing memory accesses is crucial for achieving good performance. The middle end can apply several optimizations to reduce memory traffic, including load elimination, store elimination, and memory-to-register promotion.

Load elimination removes redundant loads from memory. If we load a value from memory and then load from the same location again without any intervening stores, the second load is redundant and can be replaced with a use of the value from the first load. Similarly, store elimination removes stores whose values are never read.

Memory-to-register promotion identifies memory locations that are accessed frequently and promotes them to virtual registers. Instead of loading from and storing to memory on each access, we keep the value in a register and only store back to memory when necessary. This optimization can dramatically improve performance for local variables.

However, memory optimizations are complicated by aliasing, which occurs when two different pointer expressions might refer to the same memory location. If we cannot determine whether two pointers alias, we must conservatively assume they might, which limits optimization. Aliasing analysis attempts to determine which pointers might alias, enabling more aggressive optimization.

Here is an example showing the impact of aliasing:

x = load ptr1

store ptr2, 5

y = load ptr1    // Can we eliminate this load?

If we can prove that ptr1 and ptr2 do not alias (point to different locations), then the store to ptr2 does not affect the value at ptr1, and we can reuse the value loaded into x. If they might alias, we must perform the second load.

Aliasing analysis is challenging because it requires reasoning about pointer values, which can be computed dynamically and depend on complex program logic. Simple analyses examine the syntactic form of pointer expressions, while more sophisticated analyses use data flow analysis to track pointer values through the program.

SUMMARY AND CONCLUSION

The compiler middle end is a sophisticated component that transforms semantically validated code into an optimized form suitable for code generation. It operates on an intermediate representation that is designed to facilitate analysis and transformation, applying a series of optimization passes that improve performance, reduce code size, and eliminate redundancies.

We have explored the key components of a middle end implementation, including IR design, control flow graph construction, data flow analysis, and various optimization techniques. We have seen how constant folding and propagation eliminate compile-time computation, how dead code elimination removes unnecessary instructions, how common subexpression elimination avoids redundant computation, and how loop optimizations improve the efficiency of iterative code.

The middle end must carefully balance multiple concerns. It must preserve program semantics exactly while transforming the code. It must apply optimizations that provide measurable benefits without excessive compilation time. It must produce output that the backend can efficiently translate to machine code. Achieving these goals requires sophisticated algorithms, careful engineering, and deep understanding of program behavior.

By implementing a well-designed middle end, we enable our compiler to generate high-quality code that executes efficiently on modern processors. The optimizations applied in the middle end are largely machine-independent, making them broadly applicable across different target architectures. This separation of concerns allows the backend to focus on machine-specific optimizations and code generation, while the middle end handles the high-level transformations that improve the program's fundamental efficiency.

ADDENDUM COMPLETE PRODUCTION-READY IMPLEMENTATION

The following is a complete, production-ready implementation of a compiler middle end in Python. This implementation includes all necessary components: IR data structures, AST definitions, IR generation, control flow graph construction, data flow analysis, and multiple optimization passes. The code is designed to be extensible, well-documented, and suitable for real-world use.

""" Compiler Middle End Implementation A complete implementation of a compiler middle end with optimization passes. """

from enum import Enum, auto from typing import List, Set, Dict, Optional, Any, Tuple from dataclasses import dataclass, field from copy import deepcopy

=============================================================================

IR Instruction Definitions

=============================================================================

class Opcode(Enum): """Enumeration of all supported IR opcodes.""" # Arithmetic operations ADD = auto() SUB = auto() MUL = auto() DIV = auto() MOD = auto() NEG = auto()

# Comparison operations

EQ = auto()   # Equal

NE = auto()   # Not equal

LT = auto()   # Less than

LE = auto()   # Less than or equal

GT = auto()   # Greater than

GE = auto()   # Greater than or equal

# Logical operations

AND = auto()

OR = auto()

NOT = auto()

# Memory operations

LOAD = auto()

STORE = auto()

# Data movement

MOV = auto()

# Control flow

LABEL = auto()

JUMP = auto()

BRANCH = auto()  # Conditional branch

CALL = auto()

RETURN = auto()

# SSA-specific

PHI = auto()

@dataclass class Instruction: """ Represents a single instruction in the intermediate representation.

This is a three-address code instruction with an opcode and up to

two operands plus a destination. Some instructions use fewer fields.

"""

opcode: Opcode

dest: Optional[str] = None

op1: Optional[Any] = None

op2: Optional[Any] = None

label: Optional[str] = None

def __str__(self) -> str:

    """Generate a human-readable string representation."""

    if self.opcode == Opcode.LABEL:

        return f"{self.label}:"

    

    parts = []

    if self.dest:

        parts.append(f"{self.dest} = ")

    

    parts.append(self.opcode.name.lower())

    

    if self.op1 is not None:

        parts.append(f" {self.op1}")

    if self.op2 is not None:

        parts.append(f", {self.op2}")

    

    return "".join(parts)

def get_uses(self) -> Set[str]:

    """Return the set of variables used by this instruction."""

    uses = set()

    for op in [self.op1, self.op2]:

        if isinstance(op, str) and not self._is_constant(op):

            uses.add(op)

    return uses

def get_def(self) -> Optional[str]:

    """Return the variable defined by this instruction, if any."""

    if self.dest and not self._is_constant(self.dest):

        return self.dest

    return None

@staticmethod

def _is_constant(value: Any) -> bool:

    """Check if a value is a constant rather than a variable."""

    if isinstance(value, (int, float, bool)):

        return True

    if isinstance(value, str):

        # Check if it's a numeric string

        try:

            float(value)

            return True

        except ValueError:

            return False

    return False

def is_terminator(self) -> bool:

    """Check if this instruction terminates a basic block."""

    return self.opcode in {Opcode.JUMP, Opcode.BRANCH, Opcode.RETURN}

def is_branch(self) -> bool:

    """Check if this instruction is a branch."""

    return self.opcode in {Opcode.JUMP, Opcode.BRANCH}

=============================================================================

Basic Block and Control Flow Graph

=============================================================================

@dataclass class BasicBlock: """ Represents a basic block in the control flow graph.

A basic block is a maximal sequence of instructions with a single entry

point and a single exit point.

"""

name: str

instructions: List[Instruction] = field(default_factory=list)

predecessors: Set['BasicBlock'] = field(default_factory=set)

successors: Set['BasicBlock'] = field(default_factory=set)

# Data flow analysis sets

gen_set: Set[str] = field(default_factory=set)

kill_set: Set[str] = field(default_factory=set)

in_set: Set[str] = field(default_factory=set)

out_set: Set[str] = field(default_factory=set)

# Live variable analysis sets

use_set: Set[str] = field(default_factory=set)

def_set: Set[str] = field(default_factory=set)

live_in: Set[str] = field(default_factory=set)

live_out: Set[str] = field(default_factory=set)

def __str__(self) -> str:

    """Generate a human-readable string representation."""

    lines = [f"{self.name}:"]

    for instr in self.instructions:

        lines.append(f"  {instr}")

    return "\n".join(lines)

def add_predecessor(self, block: 'BasicBlock') -> None:

    """Add a predecessor block."""

    self.predecessors.add(block)

def add_successor(self, block: 'BasicBlock') -> None:

    """Add a successor block."""

    self.successors.add(block)

    block.add_predecessor(self)

class ControlFlowGraph: """ Represents the control flow graph of a function.

The CFG is a directed graph where nodes are basic blocks and edges

represent possible control flow between blocks.

"""

def __init__(self):

    self.blocks: List[BasicBlock] = []

    self.entry_block: Optional[BasicBlock] = None

    self.exit_block: Optional[BasicBlock] = None

    self.name_to_block: Dict[str, BasicBlock] = {}

def add_block(self, block: BasicBlock) -> None:

    """Add a basic block to the CFG."""

    self.blocks.append(block)

    self.name_to_block[block.name] = block

    

    if self.entry_block is None:

        self.entry_block = block

def get_block(self, name: str) -> Optional[BasicBlock]:

    """Retrieve a basic block by name."""

    return self.name_to_block.get(name)

def __str__(self) -> str:

    """Generate a human-readable string representation."""

    lines = ["Control Flow Graph:"]

    for block in self.blocks:

        lines.append(str(block))

        if block.successors:

            succ_names = [s.name for s in block.successors]

            lines.append(f"  -> {', '.join(succ_names)}")

        lines.append("")

    return "\n".join(lines)

=============================================================================

AST Node Definitions

=============================================================================

class ASTNode: """Base class for all AST nodes.""" pass

@dataclass class Program(ASTNode): """Root node representing an entire program.""" functions: List['Function']

@dataclass class Function(ASTNode): """Represents a function definition.""" name: str parameters: List[Tuple[str, str]] # (name, type) pairs return_type: str body: 'Block'

@dataclass class Block(ASTNode): """Represents a block of statements.""" statements: List[ASTNode]

@dataclass class VarDecl(ASTNode): """Represents a variable declaration.""" name: str var_type: str initializer: Optional['Expression'] = None

@dataclass class Assignment(ASTNode): """Represents an assignment statement.""" target: str value: 'Expression'

@dataclass class IfStatement(ASTNode): """Represents an if-then-else statement.""" condition: 'Expression' then_block: Block else_block: Optional[Block] = None

@dataclass class WhileLoop(ASTNode): """Represents a while loop.""" condition: 'Expression' body: Block

@dataclass class ReturnStatement(ASTNode): """Represents a return statement.""" value: Optional['Expression'] = None

@dataclass class ExpressionStatement(ASTNode): """Represents an expression used as a statement.""" expression: 'Expression'

Expression nodes

class Expression(ASTNode): """Base class for all expression nodes.""" pass

@dataclass class BinaryOp(Expression): """Represents a binary operation.""" operator: str left: Expression right: Expression

@dataclass class UnaryOp(Expression): """Represents a unary operation.""" operator: str operand: Expression

@dataclass class Variable(Expression): """Represents a variable reference.""" name: str

@dataclass class Literal(Expression): """Represents a literal value.""" value: Any

@dataclass class FunctionCall(Expression): """Represents a function call.""" function_name: str arguments: List[Expression]

=============================================================================

IR Generator (AST to IR Translation)

=============================================================================

class IRGenerator: """ Translates an AST into intermediate representation.

This class implements a visitor pattern to traverse the AST and

generate three-address code instructions.

"""

def __init__(self):

    self.instructions: List[Instruction] = []

    self.temp_counter = 0

    self.label_counter = 0

    self.current_function: Optional[str] = None

def generate(self, ast: Program) -> Dict[str, List[Instruction]]:

    """

    Generate IR for an entire program.

    

    Returns a dictionary mapping function names to their IR instructions.

    """

    function_irs = {}

    

    for function in ast.functions:

        self.instructions = []

        self.temp_counter = 0

        self.label_counter = 0

        self.current_function = function.name

        

        self._generate_function(function)

        function_irs[function.name] = self.instructions

    

    return function_irs

def _new_temp(self) -> str:

    """Generate a new temporary variable name."""

    self.temp_counter += 1

    return f"t{self.temp_counter}"

def _new_label(self) -> str:

    """Generate a new label name."""

    self.label_counter += 1

    return f"L{self.label_counter}"

def _emit(self, instruction: Instruction) -> None:

    """Add an instruction to the current instruction list."""

    self.instructions.append(instruction)

def _generate_function(self, func: Function) -> None:

    """Generate IR for a function."""

    # Function entry

    self._emit(Instruction(Opcode.LABEL, label=f"func_{func.name}"))

    

    # Generate body

    self._generate_block(func.body)

    

    # Ensure function ends with return

    if not self.instructions or self.instructions[-1].opcode != Opcode.RETURN:

        self._emit(Instruction(Opcode.RETURN))

def _generate_block(self, block: Block) -> None:

    """Generate IR for a block of statements."""

    for statement in block.statements:

        self._generate_statement(statement)

def _generate_statement(self, stmt: ASTNode) -> None:

    """Generate IR for a statement."""

    if isinstance(stmt, VarDecl):

        self._generate_var_decl(stmt)

    elif isinstance(stmt, Assignment):

        self._generate_assignment(stmt)

    elif isinstance(stmt, IfStatement):

        self._generate_if(stmt)

    elif isinstance(stmt, WhileLoop):

        self._generate_while(stmt)

    elif isinstance(stmt, ReturnStatement):

        self._generate_return(stmt)

    elif isinstance(stmt, ExpressionStatement):

        self._generate_expression(stmt.expression)

    else:

        raise ValueError(f"Unknown statement type: {type(stmt)}")

def _generate_var_decl(self, decl: VarDecl) -> None:

    """Generate IR for a variable declaration."""

    if decl.initializer:

        value = self._generate_expression(decl.initializer)

        self._emit(Instruction(Opcode.MOV, decl.name, value))

def _generate_assignment(self, assign: Assignment) -> None:

    """Generate IR for an assignment."""

    value = self._generate_expression(assign.value)

    self._emit(Instruction(Opcode.MOV, assign.target, value))

def _generate_if(self, if_stmt: IfStatement) -> None:

    """Generate IR for an if statement."""

    else_label = self._new_label()

    end_label = self._new_label()

    

    # Evaluate condition

    cond = self._generate_expression(if_stmt.condition)

    

    # Branch to else if condition is false

    self._emit(Instruction(Opcode.BRANCH, op1=cond, op2=else_label))

    

    # Then block

    self._generate_block(if_stmt.then_block)

    self._emit(Instruction(Opcode.JUMP, op1=end_label))

    

    # Else block

    self._emit(Instruction(Opcode.LABEL, label=else_label))

    if if_stmt.else_block:

        self._generate_block(if_stmt.else_block)

    

    # End label

    self._emit(Instruction(Opcode.LABEL, label=end_label))

def _generate_while(self, loop: WhileLoop) -> None:

    """Generate IR for a while loop."""

    start_label = self._new_label()

    end_label = self._new_label()

    

    # Loop start

    self._emit(Instruction(Opcode.LABEL, label=start_label))

    

    # Evaluate condition

    cond = self._generate_expression(loop.condition)

    

    # Branch to end if condition is false

    self._emit(Instruction(Opcode.BRANCH, op1=cond, op2=end_label))

    

    # Loop body

    self._generate_block(loop.body)

    

    # Jump back to start

    self._emit(Instruction(Opcode.JUMP, op1=start_label))

    

    # End label

    self._emit(Instruction(Opcode.LABEL, label=end_label))

def _generate_return(self, ret: ReturnStatement) -> None:

    """Generate IR for a return statement."""

    if ret.value:

        value = self._generate_expression(ret.value)

        self._emit(Instruction(Opcode.RETURN, op1=value))

    else:

        self._emit(Instruction(Opcode.RETURN))

def _generate_expression(self, expr: Expression) -> str:

    """

    Generate IR for an expression.

    

    Returns the name of the temporary holding the expression's result.

    """

    if isinstance(expr, Literal):

        return str(expr.value)

    

    elif isinstance(expr, Variable):

        return expr.name

    

    elif isinstance(expr, BinaryOp):

        return self._generate_binary_op(expr)

    

    elif isinstance(expr, UnaryOp):

        return self._generate_unary_op(expr)

    

    elif isinstance(expr, FunctionCall):

        return self._generate_call(expr)

    

    else:

        raise ValueError(f"Unknown expression type: {type(expr)}")

def _generate_binary_op(self, op: BinaryOp) -> str:

    """Generate IR for a binary operation."""

    left = self._generate_expression(op.left)

    right = self._generate_expression(op.right)

    result = self._new_temp()

    

    opcode_map = {

        '+': Opcode.ADD,

        '-': Opcode.SUB,

        '*': Opcode.MUL,

        '/': Opcode.DIV,

        '%': Opcode.MOD,

        '==': Opcode.EQ,

        '!=': Opcode.NE,

        '<': Opcode.LT,

        '<=': Opcode.LE,

        '>': Opcode.GT,

        '>=': Opcode.GE,

        '&&': Opcode.AND,

        '||': Opcode.OR,

    }

    

    opcode = opcode_map.get(op.operator)

    if opcode is None:

        raise ValueError(f"Unknown binary operator: {op.operator}")

    

    self._emit(Instruction(opcode, result, left, right))

    return result

def _generate_unary_op(self, op: UnaryOp) -> str:

    """Generate IR for a unary operation."""

    operand = self._generate_expression(op.operand)

    result = self._new_temp()

    

    opcode_map = {

        '-': Opcode.NEG,

        '!': Opcode.NOT,

    }

    

    opcode = opcode_map.get(op.operator)

    if opcode is None:

        raise ValueError(f"Unknown unary operator: {op.operator}")

    

    self._emit(Instruction(opcode, result, operand))

    return result

def _generate_call(self, call: FunctionCall) -> str:

    """Generate IR for a function call."""

    # Evaluate arguments

    args = [self._generate_expression(arg) for arg in call.arguments]

    

    # Generate call instruction

    result = self._new_temp()

    # In a real implementation, we'd pass arguments properly

    # For simplicity, we just record the call

    self._emit(Instruction(Opcode.CALL, result, call.function_name, args))

    

    return result

=============================================================================

CFG Builder

=============================================================================

class CFGBuilder: """ Constructs a control flow graph from a list of IR instructions.

This class identifies basic block boundaries and builds the CFG

by analyzing control flow instructions.

"""

def build(self, instructions: List[Instruction]) -> ControlFlowGraph:

    """Build a CFG from a list of instructions."""

    cfg = ControlFlowGraph()

    

    # Identify leaders (instructions that start basic blocks)

    leaders = self._find_leaders(instructions)

    

    # Create basic blocks

    blocks = self._create_blocks(instructions, leaders)

    

    # Add blocks to CFG

    for block in blocks:

        cfg.add_block(block)

    

    # Build edges

    self._build_edges(blocks, cfg)

    

    return cfg

def _find_leaders(self, instructions: List[Instruction]) -> Set[int]:

    """

    Find leader instructions that start basic blocks.

    

    Leaders are:

    1. The first instruction

    2. Any instruction that is a label

    3. Any instruction following a branch or jump

    """

    leaders = {0}  # First instruction is always a leader

    

    for i, instr in enumerate(instructions):

        # Labels are leaders

        if instr.opcode == Opcode.LABEL:

            leaders.add(i)

        

        # Instruction after a branch/jump is a leader

        if instr.is_terminator() and i + 1 < len(instructions):

            leaders.add(i + 1)

    

    return leaders

def _create_blocks(self, instructions: List[Instruction], 

                  leaders: Set[int]) -> List[BasicBlock]:

    """Create basic blocks from instructions and leaders."""

    blocks = []

    sorted_leaders = sorted(leaders)

    

    for i, leader_idx in enumerate(sorted_leaders):

        # Determine block extent

        if i + 1 < len(sorted_leaders):

            end_idx = sorted_leaders[i + 1]

        else:

            end_idx = len(instructions)

        

        # Create block

        block_instrs = instructions[leader_idx:end_idx]

        block_name = f"BB{i}"

        

        # If first instruction is a label, use it as block name

        if block_instrs and block_instrs[0].opcode == Opcode.LABEL:

            block_name = block_instrs[0].label

            block_instrs = block_instrs[1:]  # Remove label from instructions

        

        block = BasicBlock(block_name, block_instrs)

        blocks.append(block)

    

    return blocks

def _build_edges(self, blocks: List[BasicBlock], cfg: ControlFlowGraph) -> None:

    """Build edges between basic blocks based on control flow."""

    for i, block in enumerate(blocks):

        if not block.instructions:

            continue

        

        last_instr = block.instructions[-1]

        

        if last_instr.opcode == Opcode.JUMP:

            # Unconditional jump to target

            target_label = last_instr.op1

            target_block = cfg.get_block(target_label)

            if target_block:

                block.add_successor(target_block)

        

        elif last_instr.opcode == Opcode.BRANCH:

            # Conditional branch: one edge to target, one to next block

            target_label = last_instr.op2

            target_block = cfg.get_block(target_label)

            if target_block:

                block.add_successor(target_block)

            

            # Fall-through to next block

            if i + 1 < len(blocks):

                block.add_successor(blocks[i + 1])

        

        elif last_instr.opcode == Opcode.RETURN:

            # No successors for return

            pass

        

        else:

            # Fall-through to next block

            if i + 1 < len(blocks):

                block.add_successor(blocks[i + 1])

=============================================================================

Data Flow Analysis

=============================================================================

class DataFlowAnalyzer: """ Performs various data flow analyses on a CFG.

This class implements reaching definitions and live variable analysis.

"""

def compute_reaching_definitions(self, cfg: ControlFlowGraph) -> None:

    """

    Compute reaching definitions for all basic blocks.

    

    A definition reaches a point if there is a path from the definition

    to that point along which the variable is not redefined.

    """

    # Compute GEN and KILL sets for each block

    all_defs = set()

    for block in cfg.blocks:

        block.gen_set = set()

        block.kill_set = set()

        

        for instr in block.instructions:

            defined = instr.get_def()

            if defined:

                # This instruction generates a definition

                def_id = f"{block.name}:{defined}"

                block.gen_set.add(def_id)

                all_defs.add(def_id)

                

                # It kills all other definitions of the same variable

                for other_def in all_defs:

                    if other_def.endswith(f":{defined}") and other_def != def_id:

                        block.kill_set.add(other_def)

    

    # Initialize IN and OUT sets

    for block in cfg.blocks:

        block.in_set = set()

        block.out_set = set()

    

    # Iterate until fixed point

    changed = True

    while changed:

        changed = False

        

        for block in cfg.blocks:

            # Compute IN from predecessors

            new_in = set()

            for pred in block.predecessors:

                new_in = new_in.union(pred.out_set)

            

            # Compute OUT

            new_out = block.gen_set.union(new_in - block.kill_set)

            

            # Check for changes

            if new_in != block.in_set or new_out != block.out_set:

                changed = True

                block.in_set = new_in

                block.out_set = new_out

def compute_live_variables(self, cfg: ControlFlowGraph) -> None:

    """

    Compute live variables for all basic blocks.

    

    A variable is live at a point if its value might be used later

    before being redefined.

    """

    # Compute USE and DEF sets for each block

    for block in cfg.blocks:

        block.use_set = set()

        block.def_set = set()

        

        for instr in block.instructions:

            # Variables used before being defined in this block

            for use in instr.get_uses():

                if use not in block.def_set:

                    block.use_set.add(use)

            

            # Variables defined in this block

            defined = instr.get_def()

            if defined:

                block.def_set.add(defined)

    

    # Initialize LIVE_IN and LIVE_OUT sets

    for block in cfg.blocks:

        block.live_in = set()

        block.live_out = set()

    

    # Iterate until fixed point (backward analysis)

    changed = True

    while changed:

        changed = False

        

        for block in reversed(cfg.blocks):

            # Compute OUT from successors

            new_out = set()

            for succ in block.successors:

                new_out = new_out.union(succ.live_in)

            

            # Compute IN

            new_in = block.use_set.union(new_out - block.def_set)

            

            # Check for changes

            if new_in != block.live_in or new_out != block.live_out:

                changed = True

                block.live_in = new_in

                block.live_out = new_out

=============================================================================

Optimization Passes

=============================================================================

class OptimizationPass: """Base class for all optimization passes."""

def run(self, cfg: ControlFlowGraph) -> bool:

    """

    Run the optimization pass on a CFG.

    

    Returns True if any changes were made, False otherwise.

    """

    raise NotImplementedError

class ConstantFoldingPass(OptimizationPass): """ Performs constant folding and propagation.

This pass evaluates operations with constant operands at compile time

and propagates constant values through the program.

"""

def run(self, cfg: ControlFlowGraph) -> bool:

    """Run constant folding on the CFG."""

    changed = False

    constants = {}  # Map variable names to constant values

    

    for block in cfg.blocks:

        for instr in block.instructions:

            # Try to fold the instruction

            if self._try_fold(instr, constants):

                changed = True

            

            # Update constant tracking

            self._update_constants(instr, constants)

    

    return changed

def _try_fold(self, instr: Instruction, constants: Dict[str, Any]) -> bool:

    """Try to fold an instruction with constant operands."""

    # Replace operands with constants if available

    op1 = constants.get(instr.op1, instr.op1)

    op2 = constants.get(instr.op2, instr.op2)

    

    # Check if both operands are constants

    if not self._is_constant(op1) or not self._is_constant(op2):

        return False

    

    # Evaluate the operation

    result = self._evaluate(instr.opcode, op1, op2)

    if result is None:

        return False

    

    # Replace instruction with a move of the constant

    instr.opcode = Opcode.MOV

    instr.op1 = result

    instr.op2 = None

    

    return True

def _update_constants(self, instr: Instruction, constants: Dict[str, Any]) -> None:

    """Update the constant tracking based on an instruction."""

    if instr.opcode == Opcode.MOV and self._is_constant(instr.op1):

        # Track this constant assignment

        if instr.dest:

            constants[instr.dest] = instr.op1

    elif instr.get_def():

        # Variable is redefined, no longer constant

        if instr.dest in constants:

            del constants[instr.dest]

@staticmethod

def _is_constant(value: Any) -> bool:

    """Check if a value is a constant."""

    return isinstance(value, (int, float, bool))

@staticmethod

def _evaluate(opcode: Opcode, op1: Any, op2: Any) -> Optional[Any]:

    """Evaluate an operation with constant operands."""

    try:

        if opcode == Opcode.ADD:

            return op1 + op2

        elif opcode == Opcode.SUB:

            return op1 - op2

        elif opcode == Opcode.MUL:

            return op1 * op2

        elif opcode == Opcode.DIV:

            return op1 / op2 if op2 != 0 else None

        elif opcode == Opcode.MOD:

            return op1 % op2 if op2 != 0 else None

        elif opcode == Opcode.EQ:

            return op1 == op2

        elif opcode == Opcode.NE:

            return op1 != op2

        elif opcode == Opcode.LT:

            return op1 < op2

        elif opcode == Opcode.LE:

            return op1 <= op2

        elif opcode == Opcode.GT:

            return op1 > op2

        elif opcode == Opcode.GE:

            return op1 >= op2

        elif opcode == Opcode.AND:

            return op1 and op2

        elif opcode == Opcode.OR:

            return op1 or op2

    except:

        return None

    

    return None

class DeadCodeEliminationPass(OptimizationPass): """ Eliminates dead code using live variable analysis.

This pass removes instructions whose results are never used.

"""

def __init__(self, analyzer: DataFlowAnalyzer):

    self.analyzer = analyzer

def run(self, cfg: ControlFlowGraph) -> bool:

    """Run dead code elimination on the CFG."""

    # Compute live variables

    self.analyzer.compute_live_variables(cfg)

    

    changed = False

    

    for block in cfg.blocks:

        new_instructions = []

        live = block.live_out.copy()

        

        # Process instructions in reverse order

        for instr in reversed(block.instructions):

            # Check if instruction is dead

            defined = instr.get_def()

            

            if defined and defined not in live:

                # Instruction is dead unless it has side effects

                if not self._has_side_effects(instr):

                    changed = True

                    continue  # Skip this instruction

            

            # Update live set

            if defined:

                live.discard(defined)

            live.update(instr.get_uses())

            

            new_instructions.append(instr)

        

        # Reverse back to original order

        block.instructions = list(reversed(new_instructions))

    

    return changed

@staticmethod

def _has_side_effects(instr: Instruction) -> bool:

    """Check if an instruction has side effects beyond its assignment."""

    # Control flow instructions have side effects

    if instr.is_terminator():

        return True

    

    # Function calls have side effects

    if instr.opcode == Opcode.CALL:

        return True

    

    # Memory stores have side effects

    if instr.opcode == Opcode.STORE:

        return True

    

    return False

class CommonSubexpressionEliminationPass(OptimizationPass): """ Eliminates common subexpressions.

This pass identifies redundant computations and reuses previously

computed values.

"""

def run(self, cfg: ControlFlowGraph) -> bool:

    """Run CSE on the CFG."""

    changed = False

    

    for block in cfg.blocks:

        expr_to_temp = {}  # Map expressions to temporaries

        

        for instr in block.instructions:

            # Create expression key

            if instr.opcode in {Opcode.ADD, Opcode.SUB, Opcode.MUL, Opcode.DIV}:

                expr = (instr.opcode, instr.op1, instr.op2)

                

                if expr in expr_to_temp:

                    # Reuse previous computation

                    instr.opcode = Opcode.MOV

                    instr.op1 = expr_to_temp[expr]

                    instr.op2 = None

                    changed = True

                else:

                    # Record this computation

                    if instr.dest:

                        expr_to_temp[expr] = instr.dest

            

            # Invalidate expressions that use redefined variables

            defined = instr.get_def()

            if defined:

                expr_to_temp = {

                    expr: temp for expr, temp in expr_to_temp.items()

                    if defined not in expr

                }

    

    return changed

=============================================================================

Optimization Pipeline

=============================================================================

class OptimizationPipeline: """ Manages the execution of multiple optimization passes.

This class runs optimization passes in a specified order and

iterates until a fixed point is reached.

"""

def __init__(self):

    self.analyzer = DataFlowAnalyzer()

    self.passes = [

        ConstantFoldingPass(),

        CommonSubexpressionEliminationPass(),

        DeadCodeEliminationPass(self.analyzer),

    ]

def optimize(self, cfg: ControlFlowGraph, max_iterations: int = 10) -> None:

    """

    Run all optimization passes until a fixed point is reached.

    

    Args:

        cfg: The control flow graph to optimize

        max_iterations: Maximum number of iterations to prevent infinite loops

    """

    for iteration in range(max_iterations):

        changed = False

        

        for opt_pass in self.passes:

            if opt_pass.run(cfg):

                changed = True

        

        if not changed:

            # Reached fixed point

            break

=============================================================================

LLVM IR Emitter

=============================================================================

class LLVMIREmitter: """ Generates LLVM IR from optimized CFG.

This class converts our IR into LLVM IR format suitable for

the LLVM backend.

"""

def emit(self, cfg: ControlFlowGraph, function_name: str) -> str:

    """

    Generate LLVM IR for a function.

    

    Returns the LLVM IR as a string.

    """

    lines = []

    

    # Function signature

    lines.append(f"define i32 @{function_name}() {{")

    

    # Emit basic blocks

    for block in cfg.blocks:

        lines.append(f"{block.name}:")

        

        for instr in block.instructions:

            llvm_instr = self._emit_instruction(instr)

            if llvm_instr:

                lines.append(f"  {llvm_instr}")

    

    lines.append("}")

    

    return "\n".join(lines)

def _emit_instruction(self, instr: Instruction) -> Optional[str]:

    """Convert a single instruction to LLVM IR."""

    if instr.opcode == Opcode.ADD:

        return f"%{instr.dest} = add i32 %{instr.op1}, %{instr.op2}"

    

    elif instr.opcode == Opcode.SUB:

        return f"%{instr.dest} = sub i32 %{instr.op1}, %{instr.op2}"

    

    elif instr.opcode == Opcode.MUL:

        return f"%{instr.dest} = mul i32 %{instr.op1}, %{instr.op2}"

    

    elif instr.opcode == Opcode.DIV:

        return f"%{instr.dest} = sdiv i32 %{instr.op1}, %{instr.op2}"

    

    elif instr.opcode == Opcode.MOV:

        if isinstance(instr.op1, int):

            return f"%{instr.dest} = add i32 0, {instr.op1}"

        else:

            return f"%{instr.dest} = add i32 0, %{instr.op1}"

    

    elif instr.opcode == Opcode.RETURN:

        if instr.op1:

            return f"ret i32 %{instr.op1}"

        else:

            return "ret i32 0"

    

    elif instr.opcode == Opcode.JUMP:

        return f"br label %{instr.op1}"

    

    elif instr.opcode == Opcode.BRANCH:

        return f"br i1 %{instr.op1}, label %{instr.op2}, label %next"

    

    return None

=============================================================================

Main Compiler Driver

=============================================================================

class Compiler: """ Main compiler driver that orchestrates all compilation phases.

This class coordinates the frontend (AST), middle end (optimization),

and backend (LLVM IR generation).

"""

def __init__(self):

    self.ir_generator = IRGenerator()

    self.cfg_builder = CFGBuilder()

    self.optimizer = OptimizationPipeline()

    self.llvm_emitter = LLVMIREmitter()

def compile(self, ast: Program) -> Dict[str, str]:

    """

    Compile a program AST to LLVM IR.

    

    Returns a dictionary mapping function names to their LLVM IR.

    """

    # Generate IR from AST

    function_irs = self.ir_generator.generate(ast)

    

    result = {}

    

    for func_name, instructions in function_irs.items():

        # Build CFG

        cfg = self.cfg_builder.build(instructions)

        

        # Optimize

        self.optimizer.optimize(cfg)

        

        # Generate LLVM IR

        llvm_ir = self.llvm_emitter.emit(cfg, func_name)

        result[func_name] = llvm_ir

    

    return result

=============================================================================

Example Usage

=============================================================================

def create_example_ast() -> Program: """ Create an example AST for demonstration.

This represents the following program:

function calculate(a, b) {

    var x = a + b;

    var y = x * 2;

    var z = a + b;  // Common subexpression

    if (y > 10) {

        return y;

    } else {

        return z;

    }

}

"""

# Create the function body

statements = [

    # var x = a + b;

    VarDecl(

        "x", "int",

        BinaryOp("+", Variable("a"), Variable("b"))

    ),

    

    # var y = x * 2;

    VarDecl(

        "y", "int",

        BinaryOp("*", Variable("x"), Literal(2))

    ),

    

    # var z = a + b;  (common subexpression)

    VarDecl(

        "z", "int",

        BinaryOp("+", Variable("a"), Variable("b"))

    ),

    

    # if (y > 10) { return y; } else { return z; }

    IfStatement(

        BinaryOp(">", Variable("y"), Literal(10)),

        Block([ReturnStatement(Variable("y"))]),

        Block([ReturnStatement(Variable("z"))])

    ),

]

# Create the function

func = Function(

    "calculate",

    [("a", "int"), ("b", "int")],

    "int",

    Block(statements)

)

# Create the program

return Program([func])

def main(): """Main entry point for the compiler demonstration.""" print("=" * 80) print("COMPILER MIDDLE END DEMONSTRATION") print("=" * 80) print()

# Create example AST

print("Creating example AST...")

ast = create_example_ast()

print("AST created successfully.")

print()

# Create compiler

compiler = Compiler()

# Compile

print("Compiling...")

llvm_irs = compiler.compile(ast)

print("Compilation complete.")

print()

# Display results

for func_name, llvm_ir in llvm_irs.items():

    print(f"LLVM IR for function '{func_name}':")

    print("-" * 80)

    print(llvm_ir)

    print()

if __name__ == __main__ : main()