[Passes] Run peeling as part of simple/full loop unrolling.

[fhahn]

Summary

Loop peeling removes conditions from loop bodies that become invariant
after a small number of iterations. When triggered, this leads to fewer
compares and possibly PHIs in loop bodies, enabling further
optimizations. The current cost-model of loop peeling should be quite
conservative/safe, i.e. only peel if a condition in the loop becomes
known after peeling.

For example, see PR47671, where loop peeling enables vectorization by
removing a PHI the vectorizer does not understand. Granted, the
loop-vectorizer could also be taught about constant PHIs, but loop
peeling is likely to enable other optimizations as well.

This has an impact on quite a few benchmarks from
MultiSource/SPEC2000/SPEC2006 on X86 with -O3 -flto, for example

Same hash: 186 (filtered out)
Remaining: 51
Metric: loop-vectorize.LoopsVectorized

Program                                        base   patch  diff
 test-suite...ve-susan/automotive-susan.test     8.00   9.00 12.5%
 test-suite...nal/skidmarks10/skidmarks.test    35.00  31.00 -11.4%
 test-suite...lications/sqlite3/sqlite3.test    41.00  43.00  4.9%
 test-suite...s/ASC_Sequoia/AMGmk/AMGmk.test    25.00  26.00  4.0%
 test-suite...006/450.soplex/450.soplex.test    88.00  89.00  1.1%
 test-suite...TimberWolfMC/timberwolfmc.test   120.00 119.00 -0.8%
 test-suite.../CINT2006/403.gcc/403.gcc.test   215.00 216.00  0.5%
 test-suite...006/447.dealII/447.dealII.test   957.00 958.00  0.1%
 test-suite...ternal/HMMER/hmmcalibrate.test    75.00  75.00  0.0%

Same hash: 186 (filtered out)
Remaining: 51
Metric: loop-vectorize.LoopsAnalyzed

Program                                        base    patch   diff
 test-suite...ks/Prolangs-C/agrep/agrep.test   440.00  434.00  -1.4%
 test-suite...nal/skidmarks10/skidmarks.test   312.00  308.00  -1.3%
 test-suite...marks/7zip/7zip-benchmark.test   6399.00 6323.00 -1.2%
 test-suite...lications/minisat/minisat.test   134.00  135.00   0.7%
 test-suite...rks/FreeBench/pifft/pifft.test   295.00  297.00   0.7%
 test-suite...TimberWolfMC/timberwolfmc.test   1879.00 1869.00 -0.5%
 test-suite...pplications/treecc/treecc.test   689.00  691.00   0.3%
 test-suite...T2000/300.twolf/300.twolf.test   1593.00 1597.00  0.3%
 test-suite.../Benchmarks/Bullet/bullet.test   1394.00 1392.00 -0.1%
 test-suite...ications/JM/ldecod/ldecod.test   1431.00 1429.00 -0.1%
 test-suite...6/464.h264ref/464.h264ref.test   2229.00 2230.00  0.0%
 test-suite...lications/sqlite3/sqlite3.test   2590.00 2589.00 -0.0%
 test-suite...ications/JM/lencod/lencod.test   2732.00 2733.00  0.0%
 test-suite...006/453.povray/453.povray.test   3395.00 3394.00 -0.0%

Note the -11% regression in number of loops vectorized for skidmarks. I
suspect this corresponds to the fact that those loops are gone now (see
the reduction in number of loops analyzed by LV).

[lebedev.ri]

The patch doesn't seem to apply for me:

llvm-project$ arc patch --nobranch D88471 --skip-dependencies
You have untracked files in this working copy.

  Working copy: /repositories/llvm-project/

  Untracked changes in working copy:
  (To ignore these 4 change(s), add them to ".git/info/exclude".)
    llvm/CMakeLists.txt.user.4.9-pre1
    llvm/CMakeLists.txt.user.old
    llvm/lib/Transforms/IPO/PassManagerBuilder.cpp.rej
    llvm/utils/compare-stats.py

    Ignore these 4 untracked file(s) and continue? [y/N] y

 INFO  Base commit is not in local repository; trying to fetch.


    This diff is against commit 6c1ce7e277624882c6139b978f90a489d638aff8, but
    the commit is nowhere in the working copy. Try to apply it against the
    current working copy state? (0be51c09131f92651e5bad9ca0e3fb8fdc37d84a)
    [Y/n] y

Checking patch llvm/test/Transforms/PhaseOrdering/X86/peel-before-lv-to-enable-vectorization.ll...
error: llvm/test/Transforms/PhaseOrdering/X86/peel-before-lv-to-enable-vectorization.ll: does not exist in index
Checking patch llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp...
Checking patch llvm/lib/Transforms/IPO/PassManagerBuilder.cpp...
error: while searching for:
  if (EnableLoopInterchange)
    MPM.add(createLoopInterchangePass()); // Interchange loops

  // Unroll small loops
  MPM.add(createSimpleLoopUnrollPass(OptLevel, DisableUnrollLoops,
                                     ForgetAllSCEVInLoopUnroll));
  addExtensionsToPM(EP_LoopOptimizerEnd, MPM);

error: patch failed: llvm/lib/Transforms/IPO/PassManagerBuilder.cpp:445
error: while searching for:
  if (EnableLoopInterchange)
    PM.add(createLoopInterchangePass());

  // Unroll small loops
  PM.add(createSimpleLoopUnrollPass(OptLevel, DisableUnrollLoops,
                                    ForgetAllSCEVInLoopUnroll));
  PM.add(createLoopVectorizePass(true, !LoopVectorize));

error: patch failed: llvm/lib/Transforms/IPO/PassManagerBuilder.cpp:1036
Checking patch llvm/include/llvm/Transforms/Scalar/LoopUnrollPass.h...
Checking patch llvm/include/llvm/Transforms/Scalar.h...
Hunk #1 succeeded at 184 (offset 6 lines).
Applied patch llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp cleanly.
Applying patch llvm/lib/Transforms/IPO/PassManagerBuilder.cpp with 2 rejects...
Rejected hunk #1.
Rejected hunk #2.
Applied patch llvm/include/llvm/Transforms/Scalar/LoopUnrollPass.h cleanly.
Applied patch llvm/include/llvm/Transforms/Scalar.h cleanly.

 Patch Failed! 
Usage Exception: Unable to apply patch!

[fhahn]

In D88471#2308260, @lebedev.ri wrote:

The patch doesn't seem to apply for me:

Rebased, should apply now.

In terms of runtime impact, I measured the following impact on SPEC2006 on ARM64 with -O3 -flto, outside the noise:

test-suite...006/450.soplex/450.soplex.test   -2.4%
test-suite...6/464.h264ref/464.h264ref.test    1.3%
test-suite...T2006/473.astar/473.astar.test   -0.9%

Presumably the h264ref regression is related to wrong decisions in the cost modeling and probably warrants some further analysis.

[lebedev.ri]

In D88471#2308297, @fhahn wrote:

In D88471#2308260, @lebedev.ri wrote:

The patch doesn't seem to apply for me:

Rebased, should apply now.

It does, thank you.

In terms of runtime impact, I measured the following impact on SPEC2006 on ARM64 with -O3 -flto, outside the noise:

test-suite...006/450.soplex/450.soplex.test   -2.4%
test-suite...6/464.h264ref/464.h264ref.test    1.3%
test-suite...T2006/473.astar/473.astar.test   -0.9%

Presumably the h264ref regression is related to wrong decisions in the cost modeling and probably warrants some further analysis.

[lebedev.ri]

This looks good to me FWIW, on the code i have checked this on,
this is a win, causing small perf improvement and apparently no regressions.

Not sure if other reviewers have other comments.

[xbolva00]

Are you gonna land this patch?

[fhahn]

In D88471#2441745, @xbolva00 wrote:

Are you gonna land this patch?

Yes I plan to land this soon. I'd just like to make sure to land this after addressing some perf regression we are seeing internally (unrelated to this patch), so it is easy to see whether this introduces any new ones.

[xbolva00]

Do you mean issues solved by D94232?

[fhahn]

rebase

[sanwou01]

Hey, we've run into a case where this patch causes a dead loop to appear which doesn't subsequently get removed. It's not a huge deal (we're seeing some great speed-ups from this patch too!), but a niggle that might be nice to address. Reproducer:

unroll-into-dead-loop.ll4 KBDownload

opt -O3 -mtriple=aarch64 ~/tmp/unroll-into-dead-loop.ll -S -o - results in this silly little loop:

vector.body:                                      ; preds = %vector.body, %vector.ph
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %index.next = add i64 %index, 2
  %0 = icmp eq i64 %index.next, %n.vec
  br i1 %0, label %middle.block, label %vector.body, !llvm.loop !1

llvm/include/llvm/Transforms/Scalar.h

 //
 // LoopUnroll - This pass is a simple loop unrolling pass.
 //
 Pass *createLoopUnrollPass(int OptLevel = 2, bool OnlyWhenForced = false,
                            bool ForgetAllSCEV = false, int Threshold = -1,
                            int Count = -1, int AllowPartial = -1,
                            int Runtime = -1, int UpperBound = -1,
                            int AllowPeeling = -1);
-// Create an unrolling pass for full unrolling that uses exact trip count only.
+// Create an unrolling pass for full unrolling that uses exact trip count only
+// and also does peeling.
 Pass *createSimpleLoopUnrollPass(int OptLevel = 2, bool OnlyWhenForced = false,
                                  bool ForgetAllSCEV = false);
 
 //===----------------------------------------------------------------------===//
 //
 // LoopUnrollAndJam - This pass is a simple loop unroll and jam pass.
 //
 Pass *createLoopUnrollAndJamPass(int OptLevel = 2);

llvm/include/llvm/Transforms/Scalar/LoopUnrollPass.h

 namespace llvm {
 
 extern cl::opt<bool> ForgetSCEVInLoopUnroll;
 
 class Function;
 class Loop;
 class LPMUpdater;
 
-/// Loop unroll pass that only does full loop unrolling.
+/// Loop unroll pass that only does full loop unrolling and peeling.
 class LoopFullUnrollPass : public PassInfoMixin<LoopFullUnrollPass> {
   const int OptLevel;
 
   /// If false, use a cost model to determine whether unrolling of a loop is
   /// profitable. If true, only loops that explicitly request unrolling via
   /// metadata are considered. All other loops are skipped.
   const bool OnlyWhenForced;
 

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addFunctionSimplificationPasses(
   MPM.add(createLoopIdiomPass());             // Recognize idioms like memset.
   MPM.add(createIndVarSimplifyPass());        // Canonicalize indvars
   addExtensionsToPM(EP_LateLoopOptimizations, MPM);
   MPM.add(createLoopDeletionPass());          // Delete dead loops
 
   if (EnableLoopInterchange)
     MPM.add(createLoopInterchangePass()); // Interchange loops
 
-  // Unroll small loops
+  // Unroll small loops and perform peeling.
   MPM.add(createSimpleLoopUnrollPass(OptLevel, DisableUnrollLoops,
                                      ForgetAllSCEVInLoopUnroll));
   addExtensionsToPM(EP_LoopOptimizerEnd, MPM);
   // This ends the loop pass pipelines.
 
   // Break up allocas that may now be splittable after loop unrolling.
   MPM.add(createSROAPass());
 
void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
   PM.add(createIndVarSimplifyPass());
   PM.add(createLoopDeletionPass());
   if (EnableLoopInterchange)
     PM.add(createLoopInterchangePass());
 
   if (EnableConstraintElimination)
     PM.add(createConstraintEliminationPass());
 
-  // Unroll small loops
+  // Unroll small loops and perform peeling.
   PM.add(createSimpleLoopUnrollPass(OptLevel, DisableUnrollLoops,
                                     ForgetAllSCEVInLoopUnroll));
   PM.add(createLoopDistributePass());
   PM.add(createLoopVectorizePass(true, !LoopVectorize));
   // The vectorizer may have significantly shortened a loop body; unroll again.
   PM.add(createLoopUnrollPass(OptLevel, DisableUnrollLoops,
                               ForgetAllSCEVInLoopUnroll));
 

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

return new LoopUnroll(
       Runtime == -1 ? None : Optional<bool>(Runtime),
       UpperBound == -1 ? None : Optional<bool>(UpperBound),
       AllowPeeling == -1 ? None : Optional<bool>(AllowPeeling));
 }
 
 Pass *llvm::createSimpleLoopUnrollPass(int OptLevel, bool OnlyWhenForced,
                                        bool ForgetAllSCEV) {
   return createLoopUnrollPass(OptLevel, OnlyWhenForced, ForgetAllSCEV, -1, -1,
-                              0, 0, 0, 0);
+                              0, 0, 0, 1);
 }
 
 PreservedAnalyses LoopFullUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
                                           LoopStandardAnalysisResults &AR,
                                           LPMUpdater &Updater) {
   // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
   // pass. Function analyses need to be preserved across loop transformations
   // but ORE cannot be preserved (see comment before the pass definition).
PreservedAnalyses LoopFullUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
   std::string LoopName = std::string(L.getName());
 
   bool Changed = tryToUnrollLoop(&L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, ORE,
                                  /*BFI*/ nullptr, /*PSI*/ nullptr,
                                  /*PreserveLCSSA*/ true, OptLevel,
                                  OnlyWhenForced, ForgetSCEV, /*Count*/ None,
                                  /*Threshold*/ None, /*AllowPartial*/ false,
                                  /*Runtime*/ false, /*UpperBound*/ false,
-                                 /*AllowPeeling*/ false,
+                                 /*AllowPeeling*/ true,
                                  /*AllowProfileBasedPeeling*/ false,
                                  /*FullUnrollMaxCount*/ None) !=
                  LoopUnrollResult::Unmodified;
   if (!Changed)
     return PreservedAnalyses::all();
 
   // The parent must not be damaged by unrolling!
 #ifndef NDEBUG

llvm/test/Transforms/PhaseOrdering/X86/peel-before-lv-to-enable-vectorization.ll

 ; RUN: opt -O2 -S %s | FileCheck %s
 ; RUN: opt -passes='default<O2>' -S %s | FileCheck %s
 
 target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx"
 
 ; The loop below needs to be peeled first to eliminate the constant PHI %first
 ; before loop vectorization.
 ;
 ; Test case from PR47671.
 
 define i32 @test(i32* readonly %p, i32* readnone %q) {
 ; CHECK-LABEL: define i32 @test(
-; CHECK-NOT: vector.body
+; CHECK: vector.body:
+; CHECK:   %index.next = add i64 %index, 8
+; CHECK: middle.block:
 ;
 entry:
   %cmp.not7 = icmp eq i32* %p, %q
   br i1 %cmp.not7, label %exit, label %loop.ph
 
 loop.ph:
   br label %loop