TL;DR
GraphPass explores using Graph Neural Networks (GNNs) to automatically select the best sequence of compiler optimization passes for a given program. While the models achieve high accuracy on a synthetic benchmark, an "edge ablation" study reveals a surprising twist: most of the predictive power comes from individual basic-block features rather than the structural connections of the control-flow graph.
What Problem Does This Paper Address?
Modern compilers like LLVM offer dozens of optimization "passes" (e.g., inlining, loop unrolling, dead code elimination). Usually, developers rely on standard, one-size-fits-all flags like -O2 or -O3. However, the "optimal" sequence of passes is highly dependent on the specific program structure.
Finding this optimal sequence is traditionally a choice between two extremes:
- Fixed Heuristics: Fast but often suboptimal.
- Iterative Compilation: Compiling and running the program hundreds of times to find the best version—effective but prohibitively slow for production use.
The authors investigate whether GNNs can bridge this gap by "looking" at a program's Control-Flow Graph (CFG) and predicting the best pass sequence in a single, fast inference step.
Methods
The authors developed GraphPass, a framework that treats compiler pass selection as a graph classification problem.
- The Input: A program is represented as a CFG where nodes are "basic blocks" (sequences of instructions with no jumps in or out). Each node is assigned an 8-dimensional feature vector (e.g., instruction count, loop depth, arithmetic density).
- The Models: They tested two primary GNN architectures:
- Graph Attention Networks (GAT): Uses attention mechanisms to weigh the importance of neighboring nodes.
- Graph Convolutional Networks (GCN): Aggregates features from a node's immediate neighborhood.
- The Architecture: Two graph layers are followed by a "readout" layer (concatenating mean and max pooling) and a multi-layer perceptron (MLP) head that classifies the program into one of five candidate pass sequences.
Datasets
Because real-world "ground truth" for optimal passes is difficult to obtain, the authors created a synthetic benchmark:
- 5,000 procedurally generated CFGs divided into five "families": simple, loop-heavy, call-heavy, branch-heavy, and compute-heavy.
- Each family is mapped to a specific "ideal" pass sequence (e.g., the loop-heavy family is assigned a sequence containing
loop-unrollandlicm). - The task for the GNN is essentially "family recognition"—identifying which category a graph belongs to so it can assign the corresponding sequence.
Key Insights and Ideas
- The Edge Paradox: The most striking finding is the "edge ablation" study. When the authors removed all edges from the graph (leaving just a "bag of blocks"), the GCN's accuracy actually increased from 92.2% to 95.0%. This suggests that for this benchmark, the relational structure of the code matters less than the statistical distribution of what's inside the blocks.
- Implicit Topology: Part of the reason edges seemed redundant is that the node features themselves (like "successor count" or "loop-header indicator") already encode local topological information. The GNN might be "cheating" by reading the graph structure through the node attributes.
- Efficiency is King: The GNN approach is extremely fast. Inference takes about 1.7 ms for a typical program. Even for a massive graph with 100,000 blocks, it finishes in under a second on a single CPU core, making it orders of magnitude faster than iterative compilation.
Key Results
- Accuracy: Both GAT and GCN reached ~92% accuracy on held-out programs.
- Baselines: GraphPass significantly outperformed a hand-written rule-based heuristic (68.4%) and a flat MLP that only saw the average of all block features (85%).
- Generalization: The models showed strong "size-generalization," maintaining high accuracy even when trained on small programs and tested on larger ones.
- Complexity: Inference cost scales linearly with the number of nodes and edges ($O(|V| + |E|)$).
Limitations and Future Work
- Synthetic vs. Real: The primary limitation is the data. The labels are deterministic functions of the program generator, not measured speedups on real hardware. The model is learning to recognize a generator's patterns rather than the underlying physics of hardware execution.
- Small Action Space: The model only chooses between 5 fixed sequences. Real compilers have a near-infinite space of possible pass orderings.
- No Real Speedup Data: The paper does not measure how much faster a "real" program would run using these predicted sequences.
- Future Directions: The authors suggest that moving to real LLVM-IR inputs and using actual execution times as labels is the necessary next step to prove GNNs can provide a "real-world" advantage in compiler design.
Summary updated