betaFeedback

WorksComputer Science

GraphPass: A Study of Graph Neural Networks for Compiler Pass Selection

Abstract

Compiler pass selection is usually governed by fixed pipelines (-O2, -O3) or hand-written heuristics. We study whether a graph neural network (GNN) over a program's control-flow graph (CFG) can select among a fixed menu of five pass sequences in a single forward pass. GraphPass encodes each CFG with a graph attention (GAT) or graph convolutional (GCN) encoder and classifies it into one of the five sequences. On a synthetic benchmark of 5,000 generated CFGs in five program families, both encoders agree with the benchmark's reference label on about 92% of held-out programs, versus 68.4% for a hand-written rule-based heuristic and 85% for a flat MLP. An edge ablation indicates that this gain comes from per-block processing rather than from CFG edges: a GCN given the same basic-block features with all edges removed scores 95.0%, versus 92.2% with the true CFG. In this benchmark the label is determined by the program family, so the task amounts to family recognition. Real-compiler speedup is not measured. Inference costs O(|V| + |E|) per CFG, measured at 1.7 ms for a typical program and about 0.8 s for a 100,000-block graph on one CPU core.

Introduction

Modern optimizing compilers such as LLVM [1] expose dozens of analysis and transformation passes that can be applied in many different orders. The standard approach, a fixed sequence such as -O2 or -O3, applies the same ordering to every program, although the best ordering is program dependent [2]. Iterative compilation [3] searches for good orderings by repeatedly compiling and running a program, which is expensive, and existing machine learning approaches [4] often summarize a program as a flat feature vector. Graph representations of programs [5, 6] and graph-based pass-ordering methods [7] instead keep relational structure.

A natural hypothesis is that the control-flow graph (CFG) carries information about which passes help, and that GNNs [8, 9] can use it. This paper tests that hypothesis on a synthetic benchmark. On this benchmark, most of the accuracy comes from processing basic-block features rather than from the edges between them.

Contributions.

  1. We cast pass selection as KK-way graph classification over CFGs with an explicit, fixed output space of K=5K=5 pass sequences (§ 4), and give its inference cost as O(∣V∣+∣E∣)O(\lvert V\rvert+ \lvert E\rvert), measured empirically (§ 5.5).

  2. We present GraphPass with two interchangeable encoders, a GAT (GraphPass-GAT) and a GCN (GraphPass-GCN), which reach statistically indistinguishable accuracy.

  3. We run an edge ablation (true edges vs. no edges vs. random edges, identical node features) and a size-generalization test.

  4. We characterize the benchmark: labels are a deterministic function of the generator’s program family, so accuracy measures agreement with a synthetic reference rule.

Preprint.

GraphPass pipeline

Figure 1. GraphPass pipeline (GAT variant shown; the GCN variant replaces the two GAT layers with two GCN layers and uses a 128–128–5 head). A CFG whose nodes are basic blocks with 8-dimensional features is encoded by two graph layers, pooled by concatenating mean and max readouts, and classified by an MLP into one of five pass sequences.

Background and Related Work

Compiler pass ordering. MILEPOST GCC [2] used machine-learned models over features extracted from the compiler’s internal representation. Surveys of ML-based autotuning [4] cover flag selection and phase ordering at length. Deep learning has been used to learn optimization heuristics directly from source [10], and reinforcement learning has been used for phase ordering in high-level synthesis, for example AutoPhase [11]. Closest to our setting, Liang et al. [7] learn LLVM pass orders with a coreset-based dataset and normalized value prediction. The TpuGraphs dataset [12] provides graph-level performance-prediction targets for tensor computation graphs. GraphPass targets a small, fixed menu of pass sequences on synthetic CFGs.

GNNs for program analysis. ProGraML [5] introduced a graph representation of programs for data-flow-style compiler tasks. Brauckmann et al. [6] evaluated compiler-derived graph representations (ASTs and control/data-flow graphs) with GNNs for heterogeneous device mapping and thread coarsening. Our setting differs in that the target is a pass-sequence choice, and in that we explicitly test whether the edges, rather than the node features, carry the signal.

Method: GraphPass

Output Space

The model does not generate arbitrary pass orderings. We define ten LLVM-style passes (mem2reg, instcombine, simplifycfg, loop-unroll, gvn, licm, dce, inline, sccp, reassociate) and hand-design K=5K=5 fixed sequences over them (Table 1). The model is a KK-way graph classifier with a softmax over these five classes, so its output is always exactly one non-empty sequence (each has at least four passes) and chance accuracy is 20%. Sequences are not compiled or executed in this study.

ClassFamilyPass sequence
Lightsimplemem2reg, instcombine, simplifycfg, dce
Inline-Firstcall-heavymem2reg, inline, instcombine, simplifycfg, dce
ValueNumbranch-heavymem2reg, gvn, sccp, instcombine, simplifycfg, dce
LoopOptloop-heavymem2reg, licm, loop-unroll, instcombine, simplifycfg, dce
Fullcompute-heavymem2reg, inline, gvn, licm, loop-unroll, instcombine, simplifycfg, dce

Table 1. The five candidate pass sequences (output classes) and the program family whose reference label they are.

Program Graphs

A program is a CFG G=(V,E)G = (V, E) whose nodes are basic blocks and whose directed edges are possible control transfers. Each node has d=8d = 8 features: a node-type code (entry, exit, loop header, call site, branch, normal), normalized instruction count, ϕ\phi-node count, a memory-operation flag, successor count, a loop-depth proxy, a call count and an arithmetic-density flag. Note that three of these (successor count, ϕ\phi count, loop-header indicator) are computed from the CFG edges, so a model that never sees edges still receives a local summary of topology; we return to this in § 5.3.

Encoders and Readout

The GAT encoder [9] updates node vv at each layer as

hv′=∥k=1KhELU⁡(∑u∈N(v)∪{v}αuvkWkhu)(1)\mathbf{h}'_v = \mathop{\Vert}_{k=1}^{K_h} \operatorname{ELU}\left(\sum_{u \in\mathcal{N}(v)\cup\{v\}} \alpha^k_{uv}\mathbf{W}^k\mathbf{h}_u\right) \tag*{(1)}

with attention coefficients αuvk\alpha^k_{uv} from a single-layer feed-forward scorer, where ∥\Vert is head concatenation. Layer 1 uses Kh=4K_h=4 heads of width 64 (256 dimensions), followed by batch normalization, ELU and dropout. Layer 2 uses one head of width 64, batch normalization, and a residual connection from a linear projection of the input features. The readout concatenates mean and max pooling over nodes (R128\mathbb{R}^{128}), followed by an MLP 128→128→64→5128\to128\to64\to5 with ReLU and dropout 0.3. The GAT model has 45,701 parameters. GraphPass-GCN replaces the GAT layers by two 64-wide GCN layers [8] with batch normalization and ReLU, and uses a 128–128–5 head.

Training

We use cross-entropy loss and Adam (learning rate 3×10−33\times10^{-3}, weight decay 10−410^{-4}), batch size 64, a cosine schedule, gradient-norm clipping at 1.0 (GAT) and checkpoint selection by validation accuracy. GraphPass-GAT trains for 80 epochs; for the GCN and MLP we report both 40 epochs and the same 80-epoch budget as the GAT. The 5,000 graphs are split randomly 70/15/15 (3,500 / 750 / 750). Classes are exactly balanced overall (1,000 each); the split is random, not stratified. Results are mean ±\pm std over five training seeds unless stated. Models are implemented in PyTorch Geometric [13].

Experiments

Benchmark and Baselines

The benchmark consists of 5,000 procedurally generated CFGs, 1,000 in each of five families (simple, loop-heavy, call-heavy, branch-heavy, compute-heavy), with 8–49 basic blocks (mean 23.5) and on average 39.6 edges. Family-specific parameters (block-count range, back-edge rate, call rate, branch rate, arithmetic density) shape each graph; block-count ranges are simple 8–19, loop-heavy 15–39, call-heavy 20–49, branch-heavy 10–29 and compute-heavy 12–34. Labels are not obtained from a compiler cost model. Each family is assigned one fixed class (Table 1); the label is a deterministic function of the family. Accuracy therefore measures agreement with this reference mapping, and the learning problem is, in effect, recognizing the generator’s family from a graph. We discuss consequences in § 6.

Baselines: Random, Always-Full (always the heaviest sequence, a stand-in for -O3) and Always-Light (a stand-in for -O1); a rule-based heuristic, a hand-written decision list over mean loop-depth, call count, fraction of branch nodes and arithmetic density; a flat MLP on the mean-pooled node features (no graph, no per-node processing); and a GCN (GraphPass-GCN). The heuristic was written on the same features with untuned thresholds (§ 6).

Main Results

Table 2 shows both GraphPass encoders at about 92%, 23.6 points above the heuristic (68.4%) and about 7 points above the flat MLP. These are accuracy differences against a synthetic reference label; speedup is not measured. GCN and 4-head GAT are statistically indistinguishable at equal budget (92.4 ±\pm 0.4 vs. 92.0 ±\pm 0.8); a single GAT head is about two points lower. Per-class accuracy (seed 0 GAT, 93.3% overall): loop-heavy 100%, branch-heavy 99.3%, compute-heavy 96.2%, simple 94.2% Table 2: Test accuracy (750 programs). Mean ±\pm std over 5 seeds; baselines without training are a single evaluation. “Ep.” is the number of training epochs. Chance is 20%.

MethodEp.Accuracy (%)
Random—19.9
Always-Full (≈\approx−O3)—21.1
Always-Light (≈\approx−O1)—20.8
Rule-based heuristic—68.4
Flat MLP (mean-pooled features)4085.0±0.285.0 \pm0.2
Flat MLP (mean-pooled features)8085.3±0.485.3 \pm0.4
GraphPass-GCN4091.8±0.791.8 \pm0.7
GraphPass-GCN8092.4±0.492.4 \pm0.4
GraphPass-GAT, 1 head8090.1±0.790.1 \pm0.7
GraphPass-GAT, 4 heads8092.0±0.892.0 \pm0.8

Table 2.

Table 3: Edge ablation, identical node features. Test accuracy (%), mean ±\pm std over nn seeds (GCN: n=5n=5, GAT: n=3n=3). Values come from a separate run from Table 2 (different random streams), so compare only within this table.

and call-heavy 75.2%, with most errors assigned to the Light class (30 of 137). The heuristic reaches 93–99% on simple, loop-heavy and compute-heavy programs and 26.3% and 18.8% on call-heavy and branch-heavy ones, where its fixed thresholds rarely fire.

Do CFG Edges Matter? An Edge Ablation

Comparing a GNN with a flat MLP confounds two factors: the GNN sees every node’s features, whereas the flat MLP sees only their mean. We hold the node features fixed and vary only the edges: the true CFG, no edges (each block sees only itself), or random edges with the same edge count but random endpoints. Features are unchanged in all three conditions.

Table 3 gives a mixed answer. Corrupting the topology (random edges) hurts both encoders relative to the true CFG, so the models do use edges when they are present. But removing edges entirely does not hurt the GCN, which improves to 95.0%, the best result in this paper, while the GAT loses six points without edges. Whether true CFG edges add information beyond the blocks’ own features therefore depends on the encoder. Two caveats apply: the successor-count, ϕ\phi-count and loop-header features are derived from the edges, so a no-edge model still receives a local topology summary; and the GAT and GCN differ in other respects (activation, residual, head depth). A per-node GCN without edges is 9.7 points above the flat MLP (85.3%), so the gain of the GNNs over the flat baseline comes mostly from processing individual blocks and max-pooling rather than from graph relations.

EncoderTrue CFGNo edgesRandom edges
GraphPass-GCN92.2±0.492.2 \pm0.495.0±0.395.0 \pm0.386.5±0.786.5 \pm0.7
GraphPass-GAT93.1±0.493.1 \pm0.487.0±1.387.0 \pm1.389.5±1.089.5 \pm1.0

Table 3.

Program Size

Table 4 bins the 750 test programs by block count (seed 0 GAT, 93.3%). Accuracy rises with size rather than staying flat, and the heuristic is non-monotone rather than steadily degrading. Size is confounded with family (e.g. only call-heavy programs reach 49 blocks while simple programs stop at 19), so size and family effects are intertwined. The benchmark has at most 49 blocks.

Blocks8–1415–2122–2930–49
# programs162193187208
GraphPass-GAT84.091.296.3100.0
Heuristic75.364.260.474.0

Table 4. Test accuracy (%) by number of basic blocks (seed 0).

As a size-generalization test we train only on programs with at most 22 blocks (1,791 graphs) and test on test programs with more than 22 blocks (374 graphs, no simple programs). GAT reaches 98.0 ±\pm 0.1% (3 seeds), GCN 97.6 ±\pm 0.5%, flat MLP 94.6 ±\pm 0.7% and the heuristic 68.2%. This subset is dominated by the families that are easiest to separate.

Inference Cost

For a fixed model, inference is linear in graph size: each GNN layer costs O(∣V∣dd′+∣E∣d′)O(\lvert V\rvert d d^{\prime} + \lvert E\rvert d^{\prime}) per head, so the forward pass is O(∣V∣+∣E∣)O(\lvert V\rvert+ \lvert E\rvert). Constructing the CFG is also at least O(∣V∣+∣E∣)O(\lvert V\rvert+ \lvert E\rvert). It is constant only in the number of candidate sequences and in the number of compilations, in contrast to iterative compilation, which needs on the order of KK compile-and-run cycles. We measured the GAT forward pass (batch size one, one CPU thread) in Table 5. Programs from our benchmark take 1.7 ms (median; p95 2.0 ms). Synthetic chain-like graphs with average degree two show the expected growth: latency is about 8.3 μ\mus per block at 100,000 blocks. Extrapolating linearly, a graph with a million blocks would take on the order of 8 s on this core (an extrapolation, not a measurement). CFG-extraction time from real LLVM-IR and the fraction of real compile time are not measured.

Blocks251001,00010,000100,000
Latency (ms)1.62.17.164.7827

Table 5. GAT forward-pass latency vs. graph size (median, one thread).

Learned Representations

Figure 2 shows embeddings that cluster by family. Clustering by family is expected, since the training label is in one-to-one correspondence with the family. The moderate silhouette (0.20 in the embedding space) agrees with the confusion between call-heavy and simple programs.

t-SNE projection of GraphPass-GAT graph embeddings colored by program family

Figure 2. t-SNE [14] of GraphPass-GAT graph embeddings (500 test programs, seed 0), colored by program family. Silhouette score by family: 0.46 in the 2-D projection, 0.20 in the original embedding space.

Discussion and Limitations

On this benchmark, GNN encoders classify the generator’s family more accurately than a hand-written heuristic and a flat feature baseline, and inference is cheap for function-sized CFGs. A GAT and a GCN perform equally well, so we name both as GraphPass variants.

Scope of the results. (i) The edge ablation attributes the accuracy mainly to per-block processing (§ 5.3). (ii) Because labels are a function of the family, the model may be learning family-specific feature statistics; separating these from factors that govern optimization outcomes requires labels from real compilation. (iii) The natural evaluation metric is the speedup (or code size) obtained by running the chosen sequence, ideally with regret for wrong choices rather than 0/1 accuracy; neither is measured here. (iv) The heuristic baseline is hand-written, so the margin over it is not a margin over a tuned production heuristic or over -O3. The “Always-Full” row is a label-agreement baseline, not measured -O3 performance.

Limitations. All data are synthetic, with only 5 candidate sequences, 8–49 blocks, a single CPU, function-level CFGs, no real LLVM-IR parsing, and no interprocedural information. GAT ablations use three seeds. Real LLVM-IR inputs, labels obtained by compiling and timing the candidate sequences on benchmark suites, and larger action spaces are outside the scope of this study.

Conclusion

We built GraphPass, a GNN pass selector over CFGs with an explicit five-sequence output space, and evaluated it on a synthetic benchmark. Both GAT and GCN encoders reach about 92% agreement with the reference label and inference is O(∣V∣+∣E∣)O(\lvert V\rvert+ \lvert E\rvert) at 1.7 ms per typical program. An edge ablation attributes the gain mainly to per-block processing rather than to CFG edges, and the benchmark labels are determined by program family. Labels from measured speedups on real programs are outside the scope of this study.

References

  1. [1]C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In Proc. CGO, 2004.
  2. [2]G. Fursin et al. MILEPOST GCC: machine learning enabled self-tuning compiler. Int. J. Parallel Program., 39(3):296–327, 2011.DOI
  3. [3]Y. Chen, S. Fang, Y. Huang, L. Eeckhout, G. Fursin, O. Temam, and C. Wu. Deconstructing iterative optimization. ACM Trans. Archit. Code Optim., 9(3):21, 2012, doi:10.1145/2355585.2355594.
  4. [4]A. H. Ashouri, W. Killian, J. Cavazos, G. Palermo, and C. Silvano. A survey on compiler autotuning using machine learning. ACM Comput. Surv., 51(5):96, 2018.DOI
  5. [5]C. Cummins, Z. V. Fisches, T. Ben-Nun, T. Hoefler, M. F. P. O’Boyle, and H. Leather. ProGraML: A graph-based program representation for data flow analysis and compiler optimizations. In ICML, 2021.
  6. [6]A. Brauckmann, A. Goens, S. Ertel, and J. Castrillon. Compiler-based graph representations for deep learning models of code. In Proc. CC, 2020.DOI
  7. [7]Y. Liang, K. Stone, A. Shameli, C. Cummins, M. Elhoushi, J. Guo, B. Steiner, X. Yang, P. Xie, H. Leather, and Y. Tian. Learning compiler pass orders using coreset and normalized value prediction. In ICML, 2023.arxiv.org/abs/2301.05104
  8. [8]T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.arxiv.org/abs/1609.02907
  9. [9]P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In ICLR, 2018.arxiv.org/abs/1710.10903
  10. [10]C. Cummins, P. Petoumenos, Z. Wang, and H. Leather. End-to-end deep learning of optimization heuristics. In Proc. PACT, 2017.DOI
  11. [11]Q. Huang, A. Haj-Ali, W. Moses, J. Xiang, I. Stoica, K. Asanovic, and J. Wawrzynek. AutoPhase: Juggling HLS phase orderings in random forests with deep reinforcement learning. In Proc. MLSys, 2020.arxiv.org/abs/2003.00671
  12. [12]P. M. Phothilimthana et al. TpuGraphs: A performance prediction dataset on large tensor computational graphs. In NeurIPS Datasets and Benchmarks Track, 2023.arxiv.org/abs/2308.13490
  13. [13]M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.arxiv.org/abs/1903.02428
  14. [14]L. van der Maaten and G. Hinton. Visualizing data using t-SNE. J. Mach. Learn. Res., 9:2579–2605, 2008.

Paper details

vlnc:W_n7aw5dtb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents