AutoPhase: Juggling HLS Phase Orderings in Random Forests with Deep Reinforcement Learning

• Applying inlining before LICM can prevent LICM from moving the internal loop, unlike applying the passes in the opposite order.Source: §1 · pp. 1–2
• Phase order can change runtime from Θ(n^2) to Θ(n), while finding an optimal sequence is NP-hard and exhaustive search is infeasible.Source: §1 · pp. 1–2
• The RL state may represent program features, prior optimization passes, or both; the next pass is the action and circuit-performance improvement is the reward.Source: §1 · p. 2
• AutoPhase integrates deep RL with HLS infrastructure and uses random forests to identify useful features and passes, reducing state and action spaces.Source: §1 · p. 2
• AutoPhase improves circuit performance by 28% over -O3 for nine real benchmarks.Source: §1 · p. 2
• Deep RL shows potential to generalize to thousands of programs after training on a hundred programs.Source: §1 · p. 2

2.1 Compiler Phase-ordering

• Optimization levels are handpicked and often benefit particular benchmark groups; prior work also selects optimizations per program or target.Source: §2.1 · p. 2

2.2 Reinforcement Learning Algorithms

• PPO supports multiple minibatch-update epochs to improve sample complexity while its surrogate objective limits deviation from the previous policy.The paper also focuses on A3C, whose actor receives action evaluations from a critic.Source: §2.2 · p. 4

2.3 Evolutionary Algorithms

• Evolutionary algorithms search through populations of candidate solutions, with genetic algorithms using selection, crossover, and mutation.Evolution strategies instead encode solutions and self-adapting hyperparameters as real numbers.Source: §2.3 · p. 4

3 AUTOPHASE FRAMEWORK FOR AUTOMATIC PHASE ORDERING

• AutoPhase explores pass sequences for input programs, using LegUp for hardware generation and a profiler-based simulator environment to train its reinforcement-learning agent.Source: §3 · p. 4, Figure 4 · p. 5

3.1 HLS Compiler

• AutoPhase compiles programs to LLVM IR and invokes LegUp to transform the IR into hardware modules.Source: §3.1 · pp. 4–5

3.2 Clock-cycle Profiler

• The LegUp profiler estimates circuit cycle counts from software traces 20× faster than hardware simulation; experiments target 200MHz.The authors report similar improvements at lower target frequencies, although cycle counts differ.Source: §3.2 · p. 5

3.3 IR Feature Extractor

• AutoPhase extracts 56 static program features, including counts of basic blocks, branches, and instruction types, as partially observable RL states.Source: §3.3 · p. 5

3.4 Random Program Generator

• Synthetic training programs are generated with CSmith, then filtered out if they exceed five minutes of CPU runtime or fail HLS compilation.Source: §3.4 · p. 5

3.5 Overall Flow of AutoPhase

• The workflow iterates through feature extraction, cycle profiling, and pass selection until convergence, using program features or pass histograms and clock-cycle improvement as training inputs.Source: §3.5 · p. 5

4 CORRELATION OF PASSES AND PROGRAM FEATURES

• For each pass, two random forests predict whether applying it improves circuit performance, using either program features or a histogram of previously applied passes.Training data came from PPO with a high exploration parameter on 100 randomly generated programs, producing feature–action–reward tuples.Source: §4 · p. 6

4.1 Importance of Program Features

• Figure 5 relates program features to pass decisions; numberof-critical-edges strongly informs whether -loop-rotate should run, plausibly reflecting loop structure.The pass can improve circuit performance by reducing the number of FSM states in a loop.Source: §4.1 · p. 6, Figure 5 · p. 7
• Other learned feature–pass correlations include branches with -loop-simplify and -lowerswitch, constant operands with -functionattrs, and memory instructions with -sink.-instcombine can reduce loads and stores involving bitcasts, while -deadargelim can remove unused constant-zero arguments.Source: §4.1 · pp. 6–7
• Feature usefulness varies by benchmark, and total instruction count is not a reliable indicator of whether applying a pass will help.More instructions can help through loop unrolling, while eliminating unnecessary code can also improve performance.Source: §4.1 · p. 7

4.2 Importance of Previously Applied Passes

• Figure 6 shows that the impact of a prior pass on the next-pass decision varies, with -loop-rotate especially influential regardless of its position in the trajectory.The figure identifies -loop-rotate followed by -loop-unroll as more useful than the reverse order.Source: §4.2 · p. 7, Figure 6 · p. 7
• Applying -loop-rotate twice consecutively is reported as not harmful, whereas repeating it with intervening passes is sometimes harmful.Examination of thousands of programs found that -loop-rotate reduces cycle count significantly.Source: §4.2 · p. 7

5.1 The RL Environment Definition

• The search space contains sequences of N passes selected from K transform passes, and the agent seeks actions that minimize long-term circuit cycle count.The state is partially observable because the M program features cannot capture every property of a program.Source: §5.1 · p. 7
• Each action selects one transform pass from the K available passes.The action space is the set of integer pass indices from 0 to K−1.Source: §5.1 · p. 7
• The observation can use program features, a histogram of previously applied passes, or both.After a pass is applied, the feature extractor refreshes program features and increments that pass's histogram count.Source: §5.1 · pp. 7–8
• The reward is the previous circuit cycle count minus the current count, though other objectives or combinations of objectives can define alternative rewards.Examples include optimizing area alone or co-optimizing area, execution time, and power.Source: §5.1 · p. 8

5.2 Applying Multiple Passes per Action

• An alternative formulation updates a complete N-pass sequence, with each pass index changed by −1, 0, or 1 at each step.The agent predicts updates for all N passes together, reducing the steps needed to traverse pass indices.Source: §5.2 · p. 8

5.3 Normalization Techniques

• To support use on new programs, the approach tests logarithmic transformation of features or rewards and normalization by input-program size.The size proxy is the input program's total instruction count.Source: §5.3 · p. 8
• Taking logarithms changes how the neural network relates features: a weighted sum of logged features corresponds to a log of their weighted product.Thus, this transformation makes the network learn feature products rather than a linear combination.Source: §5.3 · p. 8

6.1 Performance

• The evaluation compares circuit performance and sample efficiency against random search, greedy algorithms, OpenTuner, and genetic algorithms.The real-benchmark evaluation uses a 200 MHz frequency constraint and HLS-profiler clock cycles as its performance metric.Source: §6.1 · p. 8, §6 · p. 8
• RL-PPO2 achieves 50× more sample efficiency than OpenTuner at a 4% lower speedup, while program-feature methods with more samples achieve slightly higher speedup.RL-PPO3's multiple action updates achieve higher speedup than the other deep RL algorithms with a single action; the evaluation uses nine real HLS benchmarks.Source: §6.1 · pp. 8–9

6.2 Generalization

• The generalization evaluation trains PPO on 100 randomly generated programs and tests deep RL on nine real CHStone benchmarks.Black-box methods instead search on the 100 random programs and apply their selected sequences to the real-benchmark test set.Source: §6.2 · pp. 9–10
• Filtered-norm1 and filtered-norm2 converge faster and achieve higher episode reward means than original-norm2, even when it trains for 20 times more steps.The filtered approaches reach high reward at roughly 8,000 steps; all three approaches learn to apply -loop-rotate before -loop-unroll.Source: §6.2 · pp. 9–10
• After training on 100 randomly generated programs, deep RL inference achieves higher speedup than black-box algorithms' predetermined sequences on new programs.The real-benchmark test set comprises nine CHStone benchmarks, and Figure 9 compares speedup over -O3 and samples per inference.Source: §6.2 · p. 10, Figure 9 · p. 10
• 6% speedup over -O3 on 12,874 randomly generated test programs with filtered-norm2 shows generalization beyond the nine real benchmarks.Normalization technique 2 achieved 4% speedup versus 3% for technique 1 on the generalization evaluation; Genetic-DEAP had -24% on unseen programs.Source: §6.2 · p. 10

7 CONCLUSIONS

• 28% better performance than -O3 after training for a few minutes is reported for the RL-based approach.The conclusion also reports a 24% improvement after training for less than a minute, without specifying its comparison baseline in the supplied passage.Source: §7 · p. 10
• Random forests analyze relationships between program features and optimization passes to identify likely beneficial phases and reduce the search space.Source: §7 · p. 10
• The authors report potential generalization to a variety of programs and envision applying deep RL to software compilation and optimization.Source: §7 · p. 10