[RFC][Pipeline] Avoid running transform passes that have just been run

IR & Optimizations
1

Consider the following pipeline:

InstCombinePass (made changes)
OtherPasses... (no change)
InstCombinePass (no change)
OtherPasses... (no change)
InstCombinePass (no change)

The second and third run of InstCombinePass are redundant since we already converged in the first run and didn’t make any changes in other passes.
Formally, if a transform pass P satisfies P(P(x)) == P(x), we can avoid running P iff there is no change between current point and the last time P was run, despite whether the last run of P made changes or not.

I believe most of canonicalization/cleanup passes (they are executed multiple times in the optimization pipeline) satisfy this property.

I did some experiments on 956 files of my llvm-opt-benchmark dataset by checking the output of opt -print-changed. The result looks promising: ~60% of InstCombine runs and ~50% of SimplifyCFG runs can be avoided. I will update the experiment results on the full dataset in a couple of days.

Pass Name Redundant Runs Total Runs Ratio
InstCombinePass 761349 1276416 59.65%
LCSSAPass 439604 773397 56.84%
LoopSimplifyPass 439601 773397 56.84%
SimplifyCFGPass 735056 1472907 49.91%
PostOrderFunctionAttrsPass 216891 465050 46.64%
GlobalDCEPass 756 1912 39.54%
InferAlignmentPass 28614 75570 37.86%
CorrelatedValuePropagationPass 119291 465218 25.64%
JumpThreadingPass 118603 465218 25.49%
SROAPass 117015 737279 15.87%
GlobalOptPass 159 1912 8.32%
VectorCombinePass 990 270394 0.37%
TailCallElimPass 943 270394 0.35%
CoroAnnotationElidePass 100 232709 0.04%
CoroSplitPass 35 232525 0.02%
ArgumentPromotionPass 24 232525 0.01%
OpenMPOptCGSCCPass 24 232525 0.01%
EarlyCSEPass 35 466885 0.01%
InlinerPass 15 232525 0.01%

You can reproduce the experiment with llvm-tools/duppass.py at main · dtcxzyw/llvm-tools · GitHub. Module/loop passes are handled carefully. If I don’t miss something, it is a good opportunity to save the compile time.

If this optimization makes sense, I’d like to introduce a new function/module analysis pass LastRunTrackingAnalysis to track the last run of some passes we are interested in. For other passes which are only executed once, we just preserve/invalidate the analysis result. For interesting passes, check if we can avoid running them.

PreservedAnalyses InstCombinePass::run(Function &F,
                                       FunctionAnalysisManager &AM) {
  auto &LRT = AM.getResult<LastRunTrackingAnalysis>(F);
  if (LRT.shouldSkipPass<InstCombinePass>())
    return PreservedAnalyses::all();

  ...

  LRT.markLastRun<InstCombinePass>(Changed);
  PA.preserve<LastRunTrackingAnalysis>();
  return PA;
}

Looking for your input on this idea. Thx.

8 Likes
2

I like the idea. We generally have a problem with cleanup passes being scheduled more often than is useful for most code, but we also can’t easily remove them because they do solve specific phase ordering issues. This seems like an easy way to save on some of them.

Two notes: First, keep in mind that some passes are run with different parameters. InstCombine runs are always the same, but SimplifyCFG runs have a lot of variation in parameters across the pipeline. So runs with different parameters may not be redundant.

Second, there are some transforms that commonly introduce spurious changes. For example, it’s very common that LCSSA will add some phi nodes, then InstCombine will drop them, then LCSSA will add them again, and then InstCombine drop them again. Similarly, LoopSimplify might add a block, SimplifyCFG drop it again, etc. I think this back and forth will make this less approach less effective in cases involving loops.

3

Nice idea! I tried your script on some Vulkan graphics shaders compiled with LLPC and the AMDGPU backend and got:

SimplifyCFGPass 32901 165509 19.88%
InstCombinePass 20690 144924 14.28%
LoopSimplifyPass 3482 82984 4.20%
LCSSAPass 3482 82984 4.20%
SROAPass 1380 83706 1.65%
LoopUnrollPass 634 41492 1.53%
CorrelatedValuePropagationPass 494 41492 1.19%
AlwaysInlinerPass 136 31341 0.43%

Incidentally there may be passes that report that they changed something even if they didn’t, because in some cases return true is a lot simpler than working out whether anything really changed.

4

I use -print-changed to avoid false positive reports. It detects IR changes by comparing textual IR.

5

Oh, I did not know that it compares textual IR.

6

Great idea, similar to ⚙ D113947 [NewPM] Add option to prevent rerunning function pipeline on functions in CGSCC adaptor.

To address passes like SimplifyCFG with different pass parameters, we’ll need different tracking analyses per-pass, e.g.

struct SimplifyCFGLastRunTrackingAnalysis {
  SimplifyCFGOptions Options;
  bool shouldSkipPass(SimplifyCFGOptions Opts) { return Options == Opts; }
};

There’s probably a way to templatize LastRunTrackingAnalysis to do this, although not sure if it’s worth it.

1 Like
7

note InstCombine was changed to not always satisfy P(P(x)) == P(x):

8

The intent is still that instcombine is idempotent, and cases where it is not are rare and likely not very important. So we should still do this for instcombine.

1 Like
9

Experiment results on the full dataset (40499 - 3891 = 36608 files)

Pass Name Redundant Runs Total Runs Ratio
InstCombinePass 21293068 37845070 56.26%
LCSSAPass 12802693 22937471 55.82%
LoopSimplifyPass 12802548 22937471 55.81%
SimplifyCFGPass 20427289 43507860 46.95%
PostOrderFunctionAttrsPass 6150380 13629504 45.13%
GlobalDCEPass 30242 73216 41.31%
InferAlignmentPass 919733 2475320 37.16%
CorrelatedValuePropagationPass 3267082 13641434 23.95%
JumpThreadingPass 3243405 13641434 23.78%
SROAPass 3239392 21779544 14.87%
GlobalOptPass 8796 73216 12.01%
VectorCombinePass 81896 8058377 1.02%
TailCallElimPass 78193 8058377 0.97%
CoroAnnotationElidePass 9566 6830253 0.14%
EarlyCSEPass 9576 13721167 0.07%
ArgumentPromotionPass 2730 6814837 0.04%
OpenMPOptCGSCCPass 2730 6814837 0.04%
CoroSplitPass 2636 6814667 0.04%
InlinerPass 2280 6814837 0.03%
ReassociatePass 221 6820717 0.00%
ConstraintEliminationPass 221 6820717 0.00%
ADCEPass 214 6820717 0.00%
MergedLoadStoreMotionPass 210 6820717 0.00%
MemCpyOptPass 209 6820717 0.00%
GVNPass 207 6820717 0.00%
SCCPPass 207 6820717 0.00%
BDCEPass 207 6820717 0.00%
DSEPass 203 6820717 0.00%
MoveAutoInitPass 203 6820717 0.00%
CoroElidePass 203 6820717 0.00%
AggressiveInstCombinePass 25 6820717 0.00%
LibCallsShrinkWrapPass 25 6820717 0.00%
SpeculativeExecutionPass 3 6820717 0.00%
1 Like
10

I am working on a prototype. Thank you guys!

1 Like
11

See PR [Analysis] Avoid running transform passes that have just been run by dtcxzyw · Pull Request #112092 · llvm/llvm-project · GitHub
Current implementation only skips redundant InstCombine runs.

CTMark result (-0.52% ~ -0.78%):
http://llvm-compile-time-tracker.com/compare.php?from=76007138f4ffd4e0f510d12b5e8cad529c21f24d&to=84cdd4b6fe5a4639371bb9e8255f3f0048b10638&stat=instructions:u

llvm-opt-benchmark:

Compilation time result (by files):
Top 5 improvements:
  wolfssl/sha.c.ll 802964464 -> 519192205 -35.34%
  ruby/sha1.ll 871884600 -> 587655744 -32.60%
  linux/siphash.ll 910384904 -> 615089093 -32.44%
  redis/sha1.ll 879656483 -> 595406457 -32.31%
  llvm/SHA256.cpp.ll 1569147162 -> 1072219354 -31.67%
Top 5 regressions:
  ncnn/innerproduct_x86_avx512.cpp.ll 18097943059 -> 18318801906 +1.22%
  openblas/dgghd3.c.ll 582708263 -> 584383010 +0.29%
  slurm/event_functions.ll 324222875 -> 324932150 +0.22%
  postgres/qsort_arg_srv.ll 216430984 -> 216820681 +0.18%
  openblas/dsytri_3x.c.ll 455573297 -> 456355018 +0.17%

Overall: -2.63345329%

Compilation time result (by projects):
Top 5 improvements:
  libsodium 27402217010 -> 25066814878 -8.52%
  libphonenumber 59034991613 -> 55556895439 -5.89%
  luau 707463405901 -> 672048616005 -5.01%
  simdjson 7560346805 -> 7185494120 -4.96%
  tokio-rs 47968469729 -> 45619134921 -4.90%
Top 5 regressions:

Overall: -2.55514840%

I have checked the final outputs of opt -O3 with this patch on my dataset. Most of IR changes are semantic-preserving.

4 Likes
12

https://github.com/llvm/llvm-project/pull/112092 has been landed.
Compile-time improvement: LLVM Compile-Time Tracker

stage1-O3: -0.52%
stage1-ReleaseThinLTO: -0.65%
stage1-ReleaseLTO-g: -0.77%
stage2-O3: -0.45%
clang build: -0.52%

On llvm-opt-benchmark: Update diff November 7th 2024, 12:30:11 am · Issue #1643 · dtcxzyw/llvm-opt-benchmark · GitHub

Compilation time result (by files):
Top 5 improvements:
  wolfssl/sha.c.ll 747273441 -> 466520829 -37.57%
  ruby/sha1.ll 815291067 -> 533417096 -34.57%
  redis/sha1.ll 822586458 -> 540707573 -34.27%
  linux/siphash.ll 850097798 -> 559252027 -34.21%
  cmake/sha1.c.ll 873353378 -> 581701163 -33.39%
Top 5 regressions:
  faiss/IVFlib.cpp.ll 1381996653 -> 1408844620 +1.94%
  postgres/unicode_norm_srv.ll 794295001 -> 803304242 +1.13%
  nghttp2/llhttp.c.ll 2510789055 -> 2536611884 +1.03%
  faiss/IndexHNSW.cpp.ll 2536496845 -> 2560607916 +0.95%
  lightgbm/linear_tree_learner.cpp.ll 9514599098 -> 9566374847 +0.54%

Overall: -2.93141799%

Compilation time result (by projects):
Top 5 improvements:
  libsodium 25170190046 -> 22830280757 -9.30%
  libphonenumber 57142027725 -> 53698357257 -6.03%
  simdjson 7547001847 -> 7172027215 -4.97%
  luau 697118135706 -> 662553940036 -4.96%
  tokio-rs 45590254109 -> 43342169337 -4.93%
Top 5 regressions:

Overall: -2.60876711%

  instcombine.NumOneIteration 88233854 -> 41165020 -53.35%
  instcombine.NumWorklistIterations 105403289 -> 58331312 -44.66%
  instcombine.NegatorTotalNegationsAttempted 21211408 -> 17663397 -16.73%
  instcombine.NegatorNumValuesVisited 22048954 -> 18414447 -16.48%
  instsimplify.NumExpand 151855 -> 142001 -6.49%
  instsimplify.NumReassoc 354528 -> 342353 -3.43%
  instcombine.NegatorNumNegationsFoundInCache 4150 -> 4042 -2.60%
  instcombine.NegatorNumInstructionsCreatedTotal 49919 -> 49249 -1.34%
  instcombine.NumGlobalCopies 134278 -> 134130 -0.11%
  last-run-tracking.NumLRTQueries 0 -> 105403225
  last-run-tracking.NumSkippedPasses 0 -> 47067181
6 Likes