PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Compiler Autotuning using Machine Learning

Amir H. Ashouri, William Killian, John Cavazos, Gianluca Palermo, Cristina Silvano

arXiv:1801.04405v5cs.PLcs.LG

TL;DR

Compiler autotuning faces a growing optimization space in which selecting optimizations and ordering their application remain difficult. This survey synthesizes and classifies machine-learning approaches across characterization, models, prediction, exploration, platforms, and applications. Reported results include methods outperforming standard compiler settings and achieving over 90% of available speedup, while dynamic characterization remains constrained across architectures.

  • Problem

    Growing hardware, software, and optimization complexity makes it difficult to choose effective optimizations and their order for application-specific compilation.

  • Method

    The survey synthesizes and classifies compiler-autotuning research using machine learning across characterization techniques, models, prediction types, exploration strategies, target domains, and applications.

  • Results

    Reported approaches include Bayesian-network iterative compilation outperforming GCC -O2 and -O3 by around 50%, while MiCOMP achieves over 90% of available speedup and outperforms -O3 using a few predictions.

  • Takeaways & Limitations

    Machine learning provides a broad set of approaches for compiler autotuning, including optimization selection and phase ordering, and the survey identifies research avenues for future work.

  • Takeaways & Limitations

    Dynamic characterization can be inaccurate across target architectures, and architecture-dependent performance counters cannot be used cross-platform.

Abstract

from arXiv · show

Since the mid-1990s, researchers have been trying to use machine-learning based approaches to solve a number of different compiler optimization problems. These techniques primarily enhance the quality of the obtained results and, more importantly, make it feasible to tackle two main compiler optimization problems: optimization selection (choosing which optimizations to apply) and phase-ordering (choosing the order of applying optimizations). The compiler optimization space continues to grow due to the advancement of applications, increasing number of compiler optimizations, and new target architectures. Generic optimization passes in compilers cannot fully leverage newly introduced optimizations and, therefore, cannot keep up with the pace of increasing options. This survey summarizes and classifies the recent advances in using machine learning for the compiler optimization field, particularly on the two major problems of (1) selecting the best optimizations and (2) the phase-ordering of optimizations. The survey highlights the approaches taken so far, the obtained results, the fine-grain classification among different approaches and finally, the influential papers of the field.

1 INTRODUCTION

Compiler autotuning addresses increasingly difficult optimization choices as hardware, software, and compiler complexity expand. This survey organizes machine-learning approaches around selecting optimizations and ordering optimization phases, while reviewing their methods and applications.

  • 1 INTRODUCTION: Compiler optimization must bridge high-level software and increasingly diverse hardware, but compiler improvements lag the pace of hardware development.The survey identifies CPUs, GPUs, and FPGAs, alongside evolving programming models, as sources of growing compilation challenges.
  • 1 INTRODUCTION: Optimization parameters can affect execution time, code size, and power consumption, making holistic trade-off exploration challenging.Examples include loop unrolling and register allocation.
  • 1 INTRODUCTION: Selecting compiler optimizations is difficult because their effects depend on the programming language, application, and target architecture.Hundreds of interacting optimizations may be applied across compilation phases, and aggressive transformations can degrade performance.
  • 1 INTRODUCTION: The phase-ordering problem concerns choosing the sequence of compiler optimizations, while optimization selection concerns choosing which optimizations to apply.Both problems remain open, and kernel optimization sequences are often constructed manually with limited insight into pass interactions.
  • 1 INTRODUCTION: Machine-learning prediction models are a central approach for finding application-specific optimizations beyond predefined compiler optimization passes.The survey highlights machine-learning methods that predict effective optimizations for a given application.
  • 1 INTRODUCTION: The survey covers more than 200 papers from roughly 25 years and classifies them by characterization, models, objectives, platforms, and related features.Its organization selectively elaborates notable works within multiple possible classification schemes.

§ 5 Prediction Types

The survey’s prediction-related organization lists several predictor families before the subsequent optimization-space exploration section. It presents this material as part of a broader survey intended for researchers and technical professionals.

  • § 5 Prediction Types: The prediction-types material lists clustering/downsampling, speedup, sequence, tournament/intermediate, and feature predictors.These categories appear together in the survey organization.
  • § 5 Prediction Types: Figure 1 organizes the survey into sections, including prediction types and optimization-space exploration.The caption identifies the figure as an overview of the survey’s section organization.
  • § 5 Prediction Types: The survey is intended for computer architects, compiler developers, researchers, and technical professionals.The stated audience spans both research and applied technical roles.

2 COMPILER OPTIMIZATIONS

Compiler optimization problems involve selecting which optimizations to apply and ordering their phases, with interactions making both choices difficult. Autotuning frameworks use application features, measured objectives, and predictive models to guide optimization decisions across large search spaces.

  • 2.1 A Note on Terminology and Metrics: Compiler optimization is discussed under varying terms, but this survey uses “optimizing compilers” and “compiler autotuning” for clarity.
  • 2.3 Compiler Optimization Problems: Optimization selection represents enable/disable choices for compiler optimizations, while phase ordering represents changing the order in which those optimizations are applied.
  • 2.3.1 The Problem of Selecting the Best Compiler Optimizations.: Selection has an exponential upper-bound, while fixed-length phase ordering has factorial complexity because it enumerates permutations.
  • 2.3.2 The Phase-ordering Problem.: There is no ideal phase ordering because one optimization can hinder or enable opportunities for another, depending on their order.
  • 2.3.2 The Phase-ordering Problem.: More than 11 billion optimization sequences arise when n and m are both 10, and unbounded sequence lengths remove a deterministic upper bound.
  • 2.3.2 The Phase-ordering Problem.: A machine-learning autotuning framework extracts and reduces application features, trains a predictive model from measured objectives, and applies it to test applications.The test phase produces a predicted outcome that can be compared with a known outcome for evaluation.

3 APPLICATION CHARACTERIZATION TECHNIQUES

Application characterization supplies machine-learning models with program representations, using static, dynamic, or hybrid features. The survey emphasizes that feature quality, dimensionality, and platform dependence affect autotuning effectiveness.

  • Feature design and reduction: Feature vectors should represent applications distinctly without becoming so large that they slow learning or reduce precision.The survey also discusses graph representations, dimension reduction, and shortest-path graph kernels for constructing useful representations.
  • Static characterization: Static characterization extracts non-functional source, IR, or backend features without executing the code.Features may describe functions, compiler parameters, or optimization-pass ordering.
  • Dynamic characterization: Dynamic characterization collects runtime performance counters that expose execution behavior, bottlenecks, and resource use.Counters can describe cache hits, misses, memory footprints, and floating-point-unit utilization.
  • Dynamic characterization: Architecture-dependent counters can accurately characterize applications but limit reuse across platforms because measurements depend on target hardware.Instrumentation offers a more portable alternative across systems sharing the same ISA.
  • Hybrid characterization: Hybrid characterization combines extraction techniques and can capture application behavior more accurately by considering multiple feature levels.HERCULES was used to build models that select good compiler optimization sequences for an application.

4 MACHINE LEARNING MODELS

The survey classifies machine-learning models for compiler autotuning into supervised, unsupervised, and other methods. It uses this classification to organize methods and notable related work.

  • Classification: The survey groups compiler-autotuning machine-learning methods into supervised learning, unsupervised learning, and other methods.The third category includes reinforcement learning, graph-based techniques, and statistical methods.

4.1 Supervised learning

Supervised-learning approaches learn from labeled compiler or application data to predict optimization choices and related outcomes. The surveyed examples include Bayesian networks, linear models, decision trees, graph kernels, and other predictive methods.

  • Foundations: Supervised learning learns a function from labeled examples and predicts outcomes for unseen points.It commonly supports classification, regression, and ranking.
  • Bayesian networks: Bayesian networks combine application features and optimization interdependencies to infer suitable optimization sequences.Ashouri et al. trained on sequences in the best 15% by speedup relative to GCC -O3.
  • Bayesian networks: Around 50% improvement over GCC’s -O2 and -O3 was reported for Bayesian networks with iterative compilation on Cbench and Polybench.The evaluation concerned an embedded-processor optimization-selection approach.
  • Trees and ensembles: Decision trees and random forests partition feature spaces or combine multiple trees for regression and classification.Applications included code compression and learning loop-unrolling heuristics for UltraSPARC and IA-64.
  • Graph-based methods: Graph kernels represent application similarity directly, allowing control-flow graphs to feed an SVM without flattening them into fixed-length vectors.The shortest-path graph kernel produces similarity scores between graphs.
  • Other supervised methods: At least 90% of scheduling improvement was obtained for every block while using at most 25% of the needed effort with induced binary heuristics.The approach used supervised learning to predict which blocks should schedule in a JIT Java compiler.
  • Other supervised methods: A statistical model found one compiler sequence that performed better on average than GCC’s standard optimization set across SPECint95 benchmarks.The method reduced the optimization search space before exploration.
  • Other supervised methods: Machine-learning-based mapping made better, more scalable, and more practical decisions across architectures in profile-driven parallelism detection.The method identified and located more application parallelism, with user feedback required at the final stage.

4.2 Unsupervised learning

Unsupervised and evolutionary methods reduce or explore compiler-optimization spaces without relying solely on labeled examples. The surveyed work uses clustering, statistical filtering, genetic algorithms, and related models for search reduction and optimization selection.

  • Unsupervised learning: Unsupervised learning infers hidden structure from unlabeled data without an error or reward signal.Clustering can group related optimization passes and downsample the search space.
  • Clustering: A clustering method reduced machine-learning autotuning training time by a factor of seven on EEMBCv2.Gustafson Kessel clustering was applied after dimension reduction.
  • Clustering: Clustering and statistical filtering jointly narrowed hardware/software co-design to four good VLIW architectures and promising compiler optimizations.The process used the Kruskal-Wallis test and Pareto-optimal filtering.
  • Phase-ordering and search reduction: Clustering-based methods grouped similar functions or optimization sequences to address phase-ordering and reduce exploration effort.Approaches used DNA encoding, distance matrices, tree construction, and sequence similarity.
  • Evolutionary methods: Evolutionary algorithms evaluate candidate optimization solutions with fitness functions and evolve populations through repeated selection and mutation.NSGA-II is presented as a faster approach for multi-objective optimization than classic genetic algorithms.
  • Other search-guidance methods: NEAT, nearest-neighbor models, Markov-chain oracles, and feature grammars were used to guide optimization selection or iterative-compilation exploration.These methods target compiler-pass selection, unseen applications, or improved machine-learning feature spaces.
  • Evolutionary methods: Genetic algorithms produced new fixed optimization sequences that generally reduced binary code size compared with iterative and random-frequency baselines.Cooper et al. targeted code-size optimization in generated binaries.

4.3 Reinforcement Learning

Reinforcement learning applies reward-driven interaction to compiler optimization, including instruction scheduling and placement. Reported studies found RL-based approaches could outperform established alternatives on evaluated benchmarks.

  • 4.3 Reinforcement Learning: Reinforcement learning uses rewards or penalties while an agent interacts with an environment to maximize cumulative reward.Its training and testing phases are intertwined, and it uses Markov decision processes to adapt to environments.
  • 4.3 Reinforcement Learning: A combined reinforcement-learning and rollout approach outperformed the commercial Compaq scheduler on evaluated SPEC95 benchmarks.
  • 4.3 Reinforcement Learning: NEAT-based reinforcement learning outperformed simulated annealing for finding instruction placements on an EDGE architecture.

5 PREDICTION TYPES

The survey classifies prediction methods by what they predict, including optimization choices, speedups, features, rankings, and reduced search spaces. It reviews clustering, sequence prediction, speedup prediction, and feature-sensitive models for compiler autotuning.

  • 5 PREDICTION TYPES: Prediction types include optimization-set selection, sequence-speedup prediction, feature selection, tournament prediction, and optimization-space downsampling.
  • 5 PREDICTION TYPES: Downsampling reduces the enormous optimization space by orders of magnitude, making exploration more tractable.
  • 5 PREDICTION TYPES: Ashouri et al.’s clustered full-sequence speedup predictor reduced LLVM -O3 phase-ordering space to an explorable space and outperformed standard optimization levels and other predictors.The approach used subsequences formed by clustering available LLVM -O3 optimization passes and required only a few predictions.
  • 5 PREDICTION TYPES: Compiler sequence predictors use application characterization to select optimization passes or sequences for objectives such as performance, code size, or energy.
  • 5 PREDICTION TYPES: Dynamic-characteristic logistic regression outperformed static-feature techniques and rapidly reached achievable speedup for optimization selection.
  • 5 PREDICTION TYPES: Bayesian-network models using static, dynamic, or hybrid application characterization, combined with iterative compilation, outperformed state-of-the-art models.
  • 5 PREDICTION TYPES: NEAT-based intermediate speedup prediction selected phase orders iteratively and produced average speedups of 5-10% in Java Jikes dynamic compilers.
  • 5 PREDICTION TYPES: Feature selection is crucial because prediction accuracy depends heavily on the features and characterization collected from the application.Large, inefficient feature vectors can slow or halt machine-learning processes and reduce precision.

6 OPTIMIZATION SPACE EXPLORATION TECHNIQUES

Compiler autotuning requires exploration strategies for the large space of optimization combinations. The survey distinguishes iterative, adaptive, genetic, non-iterative, and other search approaches, including methods that use feedback or parallelism.

  • 6 OPTIMIZATION SPACE EXPLORATION TECHNIQUES: Design-space exploration defines policies for generating candidates across some or all of the compiler optimization space.Different applications may impose different energy and performance requirements.
  • 6 OPTIMIZATION SPACE EXPLORATION TECHNIQUES: Adaptive optimization explores configurations using fitness-function outcomes such as execution time, then dynamically modifies or recompiles application segments.
  • 6 OPTIMIZATION SPACE EXPLORATION TECHNIQUES: Iterative compilation repeatedly applies approximate procedures and is among the most commonly used compiler optimization exploration techniques.It appears alone, with machine learning, or with search and meta-heuristic methods.
  • 6 OPTIMIZATION SPACE EXPLORATION TECHNIQUES: Iterative compilation can be practical for embedded applications when fabrication and distribution costs repay exploration effort and parameter counts remain small.One study used execution-time feedback and downsampled restricted passes while exploring unrolling, tiling, and padding.
  • 6 OPTIMIZATION SPACE EXPLORATION TECHNIQUES: Optimization-Space Exploration used compiler-writer knowledge to prune configuration parameters and iteratively select the next optimization based on the current state.
  • 6 OPTIMIZATION SPACE EXPLORATION TECHNIQUES: Non-iterative approaches seek global solutions for a class of compiler optimization problems and have received less recent attention.The survey connects approximation methods such as iterative compilation and machine learning with difficulty addressing phase ordering directly.

7 TARGET DOMAIN

Compiler autotuning must account for dependencies among the compiler, target architecture, application, and platform. The survey therefore compares work across desktop, embedded, and high-performance computing settings, including parallel and input-aware approaches.

  • 7 TARGET DOMAIN: Optimization choices depend heavily on the compiler, target processor architecture, and target platform being tuned.Machine-learning frameworks are intended to adapt to a given application or platform rather than rely solely on generic optimizations.
  • 7 TARGET DOMAIN: Embedded processors include architectures such as VLIW and ARM big.LITTLE, spanning devices including cars, phones, appliances, and consumer electronics.
  • 7 TARGET DOMAIN: Compiler autotuning research has increasingly shifted from desktop and workstation systems toward embedded and high-performance computing platforms.
  • 7 TARGET DOMAIN: Parallel search in the CHiLL framework enabled scalable exploration of the search space and rapid discovery of better-transformed kernels.
  • 7 TARGET DOMAIN: Petabricks’ two-level input-aware framework clusters inputs, identifies configurations per class, and classifies inputs to choose an optimization.
  • 7 TARGET DOMAIN: IODC addressed iterative-compilation cost in data centers by launching many optimization jobs across workers and collecting performance results at a master node.

7.2 Target Compiler

The survey covers autotuning across diverse compiler frameworks and target domains, with particular attention to GCC and LLVM and their optimization passes. It also discusses JIT, Java, polyhedral, Fortran, and other compiler settings.

  • Target Compiler: Compiler autotuning research spans front-end, IR, and backend concerns, with compiler heuristics shaping performance, energy efficiency, and power trade-offs.The survey groups target compilers and platforms across general-purpose, embedded, HPC, and heterogeneous architectures.
  • GCC: GCC is widely studied because it supports many languages and processor architectures, although its internal compiler phases are not directly tunable out of the box.Its broad support and open-source nature make GCC a central platform for autotuning research.
  • LLVM: LLVM provides a common LLVM-IR representation in SSA form, reusable compiler technologies, and backends for x86-64, ARM, FPGA, and GPU targets.LLVM’s modular structure and research ecosystem support experimentation with optimization passes, including those inside -O3.
  • Other Compiler Frameworks: The survey also includes Intel ICC, JIT and Java compilers, polyhedral compilation, Fortran compilers, and other frameworks such as SUIF and Cosy.These settings cover processor-specific optimization, dynamic compilation, loop-nest optimization, and parallelizing compiler research.

8 MOST INFLUENTIAL PAPERS

The survey identifies influential advances in compiler autotuning, from early learning and genetic-algorithm methods to phase ordering, hybrid characterization, and collaborative infrastructure. Reported results include substantial speedups, reduced search, and improved performance over established baselines.

  • Introducing Learning Methods: Early influential work introduced machine learning for predicting unroll sizes, constructing instruction schedules, optimization selection, and phase ordering.Subsequent efforts combined learning with genetic algorithms, adaptive compilation, and iterative compilation.
  • Iterative compilation: Up to 40% speedup was achieved using Markov-chain-guided iterative optimization trained on 145 configurations and tested on 8020 configurations.Other iterative-compilation work explored less than 2% of the total space in a non-linear search space.
  • Practical and Collaborative Autotuning: MILEPOST GCC enabled practical on-the-fly autotuning and crowdsourcing, exposing reproducibility, metadata, data-representation, model, and dataset challenges.Large benchmark analyses and Bayesian learners further explored optimization groups using static, dynamic, and hybrid features.
  • Optimization Clustering and Full-sequence Predictors: Over 90% of available speedup was achieved by MiCOMP, which clustered LLVM -O3 passes and used a full-sequence speedup predictor with only a few predictions.MiCOMP also outperformed existing approaches by 5% and 11%, respectively, in the survey’s comparison.
  • The Selection Problem: 22% and 27% performance improvements were reported on Texas Instruments and AMD architectures using static features and a Markov oracle for optimization selection.Later approaches reported approximately 7%, 6%, and 11% improvements over earlier methods using dynamic, tournament, and hybrid Bayesian techniques.
  • The Phase-ordering Problem: Up to 49% speedup was reported for adaptive genetic-algorithm phase ordering, while another genetic algorithm reduced search time by up to 65%.A neural-network predictor for Java Jikes achieved up to 20% speedup on applications.
  • Code Size and Area: A genetic-algorithm method reduced code size by 14.5% against a default fixed sequence, while other studies explored performance, intensity, and Pareto trade-offs.The survey notes that evaluating reported performance is difficult because studies use different speedup definitions and averaging methods.

9 DISCUSSION & CONCLUSION

The survey concludes that machine-learning-based compiler autotuning covers a broad range of optimization problems, techniques, platforms, and evaluation suites. It points toward continued work on parallelism, security, reliability, reproducibility, energy efficiency, and collaborative experimentation.

  • Discussion and Conclusion: Future compilation research is positioned to address auto-parallelization, security, many-core processors, reliability, reproducibility, and energy efficiency.The survey emphasizes exploiting large-scale parallelism and power-aware hardware through compiler optimization.
  • Discussion and Conclusion: The survey’s influence analysis classifies the top 16 influential papers by citation count, while the cited data were extracted from Google Scholar in July 2018.Citation counts are therefore subject to change.
  • Discussion and Conclusion: The Collective Knowledge framework supports cross-platform sharing of reusable artifacts, portable workflows, automated tuning, crowdsourcing, and reproducible experiments.It is also used to support open ACM ReQuEST tournaments on reproducibility.
  • Discussion and Conclusion: Deep-learning methods require large training datasets, making new benchmarks and larger datasets important for applying them to compiler autotuning.The survey presents this as a direction associated with the growth of deep neural networks.
  • Discussion and Conclusion: The survey synthesizes research across application characterization, machine-learning models, prediction types, search spaces, target domains, benchmarks, and influential work.Its stated aim is to benefit computer architects, researchers, and application developers while inspiring further research.
Loading 1801.04405v5…