Source-linked AI summary
Profile Guided Optimization without Profiles: A Machine Learning Approach
Nadav Rotem, Chris Cummins
TL;DR
Collecting training data for compiler optimization can be prohibitively expensive, and performance-based tuning is difficult amid noise and unclear causality. This paper trains a model on branch information and static program features to predict probabilities for unseen branches without profiles. It reports significant gains on some open-source benchmarks with negligible compilation overhead.
Problem
Method
A supervised model trained on profiled branch information predicts branch probabilities for unseen branches using static program features.
Source: §1 · pp. 1–2Results
Without profile information, the new pass yields significant performance gains on some open-source benchmarks with negligible compilation overhead.
Source: §1 · p. 2Takeaways & Limitations
The LLVM pass annotates branches in uninstrumented programs so predicted probabilities can inform compiler optimization decisions.
Source: §1 · p. 2The authors identify opportunities for improvement at every stage and tradeoffs that remain to be explored.
Source: §6 · p. 6
Abstract
from arXiv · showhide
Profile guided optimization is an effective technique for improving the optimization ability of compilers based on dynamic behavior, but collecting profile data is expensive, cumbersome, and requires regular updating to remain fresh. We present a novel statistical approach to inferring branch probabilities that improves the performance of programs that are compiled without profile guided optimizations. We perform offline training using information that is collected from a large corpus of binaries that have branch probabilities information. The learned model is used by the compiler to predict the branch probabilities of regular uninstrumented programs, which the compiler can then use to inform optimization decisions. We integrate our technique directly in LLVM, supplementing the existing human-engineered compiler heuristics. We evaluate our technique on a suite of benchmarks, demonstrating some gains over compiling without profile information. In deployment, our technique requires no profiling runs and has negligible effect on compilation time.
1 Introduction
The paper replaces parts of LLVM’s hand-engineered branch-probability heuristics with learned predictions from static program features, avoiding profile collection at deployment. Its evaluation reports gains on some workloads without profile information and with negligible compilation overhead.
1 Introduction
- Automatically constructed decision trees replace hundreds of human-written BPI rules and can combine more inputs with complex thresholds.The generated rules need not be expressed in human language, unlike LLVM’s existing heuristics.Source: §1 · pp. 1–2
- Performance-based compiler tuning is difficult because system noise and lack of causality complicate measurement, while recorded branch probabilities provide deterministic labels for supervised learning.The target is to predict branch probabilities as recorded in program metadata.Source: §1 · p. 1
- The approach predicts branch probabilities for unseen branches from static program features, using a model trained on information collected from profiled programs.The proposed LLVM implementation includes feature extraction and embeds a model trained from a corpus of profiles.Source: §1 · p. 2
- Without profile information, the new pass yields significant performance gains on some open-source benchmarks with negligible compilation overhead.The comparison is against compiling without profile guided optimization.Source: §1 · p. 2
2 Prediction Guided Optimization
The system learns branch probabilities offline from profiled programs, then applies the learned model to branches during regular compilation. It collects static features, trains gradient-boosted trees, and uses their predictions to provide branch probabilities to LLVM.
2.1 Overview of our Approach
- Offline training uses PGO-compiled programs to collect branch features and profiled probabilities, then builds a model embedded in the compiler for online use.Online, the compiler extracts features from unprofiled files and the model predicts their branch probabilities.Source: §2.1 · p. 2
2.2 Feature Collection
- The feature pass collects 54 branch and program features, using more than a million branches from programs across multiple domains and excluding branches with too few samples.The training corpus spans benchmark suites and projects including LLVM tests, bash, clang, Python, and SQLite.Source: §2.2 · pp. 2–3
2.3 Training a Model
- Training converts branch probabilities into 11 classes, uses a 10:1 training-to-testing split, and fits gradient-boosted trees with XGBoost.The stated training time is under a minute for datasets with millions of samples.Source: §2.3 · p. 3
2.4 Code generation
- At inference, the generated code runs each tree on a branch’s feature vector, accumulates predictions across the 11 labels, and selects the highest-probability label.The trees are converted into flat vectors and traversed by a small interpreter.Source: §2.4 · p. 3
2.5 Inference
- During regular compilation, a new analysis collects each branch’s features and passes them to the offline-generated inference method, which returns a left-to-right branch probability ratio.The resulting branch probabilities are intended to inform compiler decisions.Source: §2.5 · p. 4
3 Implementation
The implementation keeps the embedded model and inference overhead small, while exposing a tradeoff between prediction accuracy and speed.
3 Implementation
- The trained model runs 250,000 inference requests per second on one x86 core, while the 3-label model runs 1,600,000 per second.Inference speed depends on decision-tree depth and tree count, trading off accuracy against performance.Source: §3 · p. 4
- The training system compresses a database of around 200MB into a model of around 2MB.The model’s decision-tree tables are stored in read-only memory and do not increase dynamic compiler memory usage.Source: §3 · p. 4
- The inference code added to LLVM is less than one kilobyte, and the overall inference time is described as very low.The paper attributes the low inference time to small trees and efficient traversal.Source: §3 · p. 4
4 Evaluation
The evaluation tests branch-weight prediction and compilation performance, then examines the accuracy and coverage of LLVM’s existing BPI heuristics.
4 Evaluation
- The evaluation has two parts: predictive performance of the branch-weight model and runtime performance against compilation without profile information and with ground-truth profiles.The runtime benchmark used regular compilation without PGO or LTO, with the new pass flag as the only difference between runs.Source: §4 · p. 4, §4.2 · p. 4
4.2 Compilation Performance
- 1.016 geometric mean speedup over compilation without profile guided optimization; the pass improved 6 of 10 workloads, from −7% for bzip2 to +16% for Python.Neither compilation used profile information.Source: Figure 4 · p. 4, §4.2 · p. 4
4.1 Predicting Branch Weights
- 75% of unseen branches received the correct predicted probability weight class across 11 discretized bins.The held-out test set comprised 10% of branches.Source: §4.1 · p. 4
4.3 Heuristics Accuracy
- Figure 5 reports the effectiveness of four BPI heuristics and the portion of branches each handles, comparing isHot outcomes for first successors with profile metadata.The evaluation used PGO to collect branch probabilities and report metadata alongside heuristic outcomes.Source: §4.3 · p. 5, Figure 5 · p. 5
5 Related work
Related work motivates learned compiler decisions as an alternative to costly profile collection and explores challenges in training data and feature design. This paper’s approach predicts branch weights as shared metadata for compiler optimizations.
5 Related work
- Profile guided optimization improves compiler decisions, but collecting profiles is cumbersome to integrate and requires substantial engineering infrastructure.Profile data collected by instrumentation or sampling applies only to the executable on which it was trained.Source: §5 · p. 5
- Prior supervised-learning work spans loop unrolling, instruction scheduling, partitioning, device mapping, inlining, and optimization heuristics [14]; reinforcement learning and neural approaches target other compiler decisions [21] [22] [27].ESP is an earlier effort to predict branch probabilities.Source: §5 · p. 5
- Traditional compiler optimization spaces can make labeled training data prohibitively expensive to collect, while branch probabilities provide ground-truth labels from program measurements.The approach also identifies noise in runtime measurement as a challenge and contrasts its noise-free ground-truth measurements with proxy metrics and noisy targets [19],, [21] [22].Source: §5 · p. 5
- The feature-design approach pairs many LLVM static-analysis values with automatic feature ranking and pruning to balance engineering cost and interpretability.Prior work used hand-crafted numeric vectors [17, 21, 12], grammar-based feature search, or deep learning representations that are harder to interpret [14] [24].Source: §5 · p. 5
- Unlike approaches aimed at individual optimizations, the learned branch-weight metadata is available to all optimization passes.Related approaches include decision trees for branch likelihood and VESPA, which extends BOLT for branch prediction and binary optimizations.Source: §5 · p. 6
6 Conclusions
The conclusion presents a fast, simple gradient-boosted-tree system for branch probabilities in uninstrumented programs, with performance wins and remaining design trade-offs.
6 Conclusions
- The gradient-boosted-tree system produced significant performance wins on several important workloads, with very low compile times and zero additional memory overhead.The conclusion describes the system as fast and simple.Source: §6 · p. 6
- The system is characterized as easy to train and integrate and as a possible first step toward applying data science to compiler engineering.Source: §6 · p. 6
- The design space remains large, with opportunities for improvement at every stage and trade-offs still to explore.Source: §6 · p. 6
A Feature list
The feature extraction code converts information from each branch and its current, left, and right basic blocks into floating-point vectors.
A Feature list
- Feature extraction collects values from each branch and the current, left, and right basic blocks, then converts them into a vector of floating-point numbers.Source: A Feature list · p. 6