Compiler Project

OLLIR Code Generation

Overview

OLLIR (Optimized Low-Level Intermediate Representation) is a low-level intermediate representation used in compiler design. It serves as a bridge between the Abstract Syntax Tree (AST) and the final machine code or bytecode. OLLIR simplifies the translation process by providing a structured and optimized representation of the program.

Key Components

1. OllirExprResult

The OllirExprResult class encapsulates the result of an expression during OLLIR code generation. It contains:

• Code: The generated OLLIR code for the expression.
• Computation: Any additional computation required for the expression.

2. OllirRegisterAllocation

This class handles register allocation for OLLIR code. It:

• Builds Control Flow Graphs (CFGs) and Variable Tables for methods.
• Performs data flow analysis to compute in, out, def, and use sets.
• Uses graph coloring to allocate registers efficiently.
• Updates the variable table with the new register assignments.

3. OllirGeneratorVisitor

The OllirGeneratorVisitor traverses the AST and generates OLLIR code for various constructs, including:

• Program Structure: Classes, methods, and fields.
• Statements: Assignments, conditionals (if, if-else), loops (while), and return statements.
• Expressions: Literals, method calls, and array accesses.

Features

• Control Flow Analysis: Constructs CFGs and performs data flow analysis for optimization.
• Register Allocation: Efficiently maps variables to registers using graph coloring.
• Code Generation: Converts high-level AST nodes into OLLIR code, ensuring type correctness and optimization.

Example Workflow

1. AST Traversal: The OllirGeneratorVisitor visits each node in the AST and generates corresponding OLLIR code.
2. Register Allocation: The OllirRegisterAllocation class optimizes variable usage by allocating registers.
3. Output: The final OLLIR code is ready for translation into machine code or bytecode.

---

Constant Propagation and Folding Optimization

This repository contains implementations of Constant Propagation and Constant Folding optimizations for an Abstract Syntax Tree (AST) in Javamm. These optimizations are part of a compiler optimization phase aimed at improving runtime performance by simplifying and reducing computations in the code.

Constant Propagation

The ConstantPropagationVisitor class implements the Constant Propagation optimization. This technique replaces variables with their constant values when possible, reducing runtime variable lookups and simplifying the AST.

Key Features:

• Tracks variables assigned constant values using a Map<String, String>.
• Replaces variable references with their constant values in the AST.
• Handles control flow constructs like if-else and while to ensure correctness.
• Avoids propagating constants modified inside conditional blocks.

Constant Folding

The ConstantFoldingVisitor class implements the Constant Folding optimization. This technique evaluates constant expressions at compile time, reducing runtime computations and simplifying the AST.

Key Features:

• Precomputes constant expressions (e.g., 5 + 3 becomes 8).
• Simplifies logical, relational, and arithmetic expressions.
• Replaces constant conditions in control flow statements (e.g., if (3 < 5) becomes if (true)).
• Handles constructs like binary expressions, negations, and return statements.

---

Graph Coloring Register Allocation

Overview

Register allocation is a critical step in compiler optimization. It assigns variables (or virtual registers) to a limited number of physical registers available in the target architecture. The Graph Coloring algorithm models this problem as a graph, where:

• Nodes: Represent virtual registers.
• Edges: Represent conflicts (i.e., two registers that cannot share the same physical register).

The algorithm ensures that no two conflicting registers are assigned the same physical register.

Key Steps

1. Graph Construction

• Builds a conflict graph based on live variable analysis using the in, out, and def sets of operands for each instruction.
• Methods:
  • edgesBuild(): Initializes the graph by creating nodes for virtual registers.
  • edgesCompute(): Adds edges between conflicting registers based on def and out sets.

2. Simplification Phase

• Simplifies the graph by removing nodes with fewer neighbors than the number of available registers (numReg).
• Pushes removed nodes onto a stack for later processing.
• Method:
  • stackbuild(Map<Integer, Set<Integer>> edgesCopy): Implements the simplification phase.

3. Coloring Phase

• Assigns colors (physical registers) to nodes by processing the stack.
• Ensures no two conflicting nodes share the same color.
• Method:
  • colorGraph(Map<Integer, Set<Integer>> edges): Implements the coloring phase.

4. Register Allocation

• Combines graph construction, simplification, and coloring to allocate registers.
• Reports an error if the graph is not colorable with the given number of registers.
• Method:
  • allocateRegisters(int numReg): Performs the entire allocation process.

5. Table Update

• Updates the variable table with the new physical register assignments.
• Ensures fields and parameters retain their original registers.
• Method:
  • updateTable(Map<Integer, Integer> coloring): Updates the variable table.

---

How It Works

1. Input:

   • in, out, and def sets for each instruction.
   • A method's variable table (VarTable).
   • The number of available physical registers (numReg).

2. Process:

   • Graph Construction: Builds a conflict graph based on live variable analysis.
   • Simplification: Removes nodes with fewer neighbors than numReg.
   • Coloring: Assigns physical registers to virtual registers using the stack.

3. Output:

   • A mapping of virtual registers to physical registers.
   • An updated variable table with the new register assignments.

CP3

Jasmin is an assembler for the Java Virtual Machine (JVM). It takes human-readable assembly language and converts it into Java bytecode. In our compiler pipeline, the Jasmin backend transforms the OLLIR intermediate representation into JVM-compatible bytecode that can be executed by the Java Virtual Machine.

Key Components

1. JasminBackendImpl

The entry point for the Jasmin code generation pipeline. It:

• Implements the JasminBackend interface
• Creates a JasminGenerator instance to perform the transformation
• Returns a JasminResult containing the generated Jasmin bytecode and any reports

2. JasminGenerator

The core class responsible for transforming OLLIR code into Jasmin assembly. It:

• Traverses the OLLIR nodes and generates corresponding Jasmin instructions
• Maintains stack state information during code generation
• Optimizes code patterns where possible (e.g., iinc for incrementing)
• Handles complex translation of control flow structures

3. JasminUtils

A utility class that provides helper methods for the Jasmin generator, including:

• Access modifier conversion between OLLIR and Jasmin formats
• Type transformation utilities
• Code Generation Process
• The Jasmin code generation follows these steps:

Class Structure Generation

• Creates class declarations with proper access modifiers
• Adds inheritance information (extends clauses)
• Generates default constructor when needed

Method Generation

• Generates method signatures with proper parameters and return types
• Sets appropriate method access modifiers and specifiers (static, final)
• Computes stack and local variable limits

Instruction Generation

• Transforms OLLIR instructions into equivalent Jasmin bytecode
• Handles control flow instructions (conditionals, loops)
• Manages stack operations to ensure correct execution

Register Allocation

• Maps OLLIR virtual registers to Jasmin local variables
• Optimizes register usage for methods

Key Features

• Stack Management:
  • Tracks stack size during code generation to determine maximum stack depth
  • Ensures correct stack balance for operations and method calls
• Control Flow Translation:
  • Handles conditional branches by converting to appropriate Jasmin jump instructions
  • Generates labels for control flow targets
  • Manages complex boolean expression evaluation
• Optimizations:
  • Increment Optimization: Detects patterns like i = i + 1 and generates efficient iinc instructions
  • Zero Comparison: Special handling for comparisons with zero to generate more compact bytecode
  • Method Invocation: Differentiates between static, virtual, and special invocations for efficiency
• Type Handling:
  • Converts OLLIR types to JVM type descriptors
  • Special handling for primitive types, arrays, and objects
  • Proper generation of type signatures for method calls

Extras Implemented

• if sem else
• ==, !=, >, >=, <=

Members

• Bruno Fortes up202209730 33%
• João Parada up201405280 33%
• Rodrigo Ribeiro up202206396 33%