Technical Summary: MileStone – A Multi-Objective Compiler Phase Ordering Framework

1. Problem Definition

The paper addresses the compiler phase ordering problem, which involves determining the optimal sequence of optimization passes to transform a program's Intermediate Representation (IR) into efficient machine code. While standard compiler optimization levels (e.g., LLVM's -O1, -O2, -O3) provide fixed sequences, they represent only a small subset of the vast search space and fail to balance conflicting performance objectives.

The core challenge identified is the need to simultaneously optimize for execution time, code size, and energy consumption. These objectives are inherently conflicting; for instance, aggressive loop unrolling may reduce execution time but increase code size and energy usage. Traditional approaches often rely on fixed heuristics or single-objective optimization, failing to capture the necessary trade-offs (Pareto-optimal solutions) required for diverse deployment environments, such as energy-constrained embedded systems or high-performance computing. Furthermore, exhaustive search is computationally infeasible, and existing learning-based methods often lack support for multi-objective constraints or rely heavily on dynamic profiling.

2. Methodology: The MileStone Framework

MileStone is a modular, learning-driven framework that models compiler phase ordering as a Constrained Multi-Objective Optimization (CMOO) problem. It integrates Graph Neural Networks (GNNs) for static performance prediction with Reinforcement Learning (RL) for adaptive exploration. The framework consists of four tightly integrated modules:

2.1 Graph Generator (GG)

The GG extracts Control and Data Flow Graphs (CDFGs) from LLVM IR after the front-end compilation stage. Unlike syntactic representations, CDFGs capture the structural and semantic relationships of the program. Each node in the CDFG is represented by a 10-dimensional binary feature vector encoding node types (basic block vs. instruction) and specific instruction opcodes (e.g., memory operations, arithmetic, control flow).

2.2 GNN-Based Performance Predictor (GNNPP)

GNNPP utilizes a Graph Convolutional Network (GCN) to predict post-compilation metrics (execution time, code size, and energy consumption) directly from CDFG representations without executing the code.

• Architecture: The model employs a two-layer GCN to aggregate node features and capture multi-hop dependencies, followed by mean pooling to generate graph-level embeddings.
• Training: It is trained as a regression model using Mean Squared Logarithmic Error (for energy and code size) and Mean Absolute Error (for execution time).
• Role: GNNPP serves as a surrogate model, providing rapid performance estimates to guide the RL agent, thereby eliminating the need for repeated physical execution during the search process.

2.3 RL-Based Multi-Objective Explorer (RLMOE)

RLMOE treats the selection of optimization passes as a sequential decision-making process modeled as a Markov Decision Process (MDP).

• State: Includes the CDFG graph embedding, current node identifier, CDFG metadata, and user-defined energy constraints.
• Action: Determines whether to apply a specific optimization directive to the current node.
• Reward: A sparse reward function is applied only at the final step ($T$), calculated as a weighted sum of predicted code size, execution time, and the deviation from the target energy consumption. Intermediate rewards are zero.
• Algorithms: The framework supports both Deep Q-Network (DQN) and Proximal Policy Optimization (PPO). PPO generally demonstrates superior stability and performance, particularly for large-scale programs, by utilizing a clipped surrogate objective and Generalized Advantage Estimation (GAE).

2.4 RL-Based Database Generator (RLDBG)

RLDBG is a self-evolving knowledge base that automates the collection of training data. It iteratively invokes RLMOE to explore diverse pass sequences, compiles the resulting configurations, and profiles them using an Evaluator to obtain ground-truth metrics. These CDFG–metric pairs are stored to train and refine GNNPP, creating a feedback loop that improves prediction accuracy and exploration efficiency over time.

3. Key Contributions

The paper outlines four primary contributions:

1. Unified Framework: Introduction of MileStone, a framework that formulates compiler phase ordering as a multi-objective optimization problem balancing execution time, code size, and energy consumption under user-defined constraints.
2. Graph-Based Neural Model: Development of a GNN model that learns structural and semantic properties from IR graphs to accurately predict program performance metrics.
3. RL-Based Exploration: Implementation of an RL-based approach (DQN/PPO) to explore pass sequences and identify Pareto-optimal trade-offs among multiple objectives.
4. Self-Improving Mechanism: Incorporation of a self-evolving data collection mechanism (RLDBG) that enhances both predictive accuracy and exploration efficiency by aggregating diverse optimization outcomes.

4. Experimental Results

Experiments were conducted on standard benchmarks (PolyBench: gemm, 3mm, floyd-warshall) using an NVIDIA RTX 3090TI GPU. The framework was compared against LLVM optimization levels (-O1 to -O3), heuristic search methods (Genetic Algorithm, Particle Swarm Optimization), and standalone RL agents.

• Pareto-Optimal Solutions: RLMOE (using both DQN and PPO) consistently outperformed baselines, finding solutions that occupied regions of the solution space with lower energy consumption and smaller code sizes while maintaining competitive execution times.
• Constraint Satisfaction: Under user-specified energy constraints, RLMOE achieved significantly higher matching rates (90–93%) compared to standalone RL agents (83–85%) and traditional optimization levels (3–9%).
• Execution Time Reduction: Under identical energy budgets, MileStone reduced execution time by up to 45% compared to LLVM -O3. Specifically, RLMOE-PPO showed reductions of 15–45% across different benchmarks.
• Architecture Analysis: The study determined that a two-layer GCN architecture provided the best balance between prediction accuracy and the avoidance of the oversmoothing problem.

5. Significance and Claims

The paper claims that MileStone provides an effective and scalable solution for multi-objective compiler phase ordering. Its significance lies in:

• Moving Beyond Single-Objective Optimization: It successfully navigates the trade-off surface between execution time, code size, and energy, allowing compilers to adapt to specific hardware and workload requirements (e.g., prioritizing energy efficiency in IoT devices).
• Efficiency: By combining GNN-based static prediction with RL, the framework avoids the prohibitive costs of exhaustive search and repeated dynamic profiling.
• Adaptability: The self-evolving database allows the system to improve over time, capturing diverse Pareto-efficient configurations that static heuristics miss.

The authors conclude that integrating static graph learning with reinforcement-based search offers a robust path forward for optimizing complex compiler pipelines, particularly in scenarios where multiple, conflicting performance metrics must be balanced. Future work is proposed to extend the framework to larger industrial workloads, incorporate detailed microarchitectural models, and support dynamic optimization scenarios.