Moving loop vectorization pass before loop-unroller.

[laxmansole]

Summary

Loop with constant trip count get unrolled first due to which it does not get vectorized. Hence moving loop-vectorizer before loop unroller. It will fix the following bugs with 2-5% performance improvement on 300.twolf, 253.perlbmk, 256.bzip2, 176.gcc and 1-2% regression on 175.vpr and 252.eon while running on AArch64:

https://llvm.org/bugs/show_bug.cgi?id=25748
https://llvm.org/bugs/show_bug.cgi?id=28090

Benchmarks %improvement (lower is better) compared to llvm-trunk(4dfe58af9)
External/SPEC/CFP2000/177.mesa/177.mesa_secs 0.51
External/SPEC/CFP2000/179.art/179.art_secs 0.73
External/SPEC/CFP2000/183.equake/183.equake_secs 0.72
External/SPEC/CFP2000/188.ammp/188.ammp_secs 0.14
External/SPEC/CINT2000/164.gzip/164.gzip_secs -1.48
External/SPEC/CINT2000/175.vpr/175.vpr_secs 2.04
External/SPEC/CINT2000/176.gcc/176.gcc_secs -2.18
External/SPEC/CINT2000/181.mcf/181.mcf_secs -0.54
External/SPEC/CINT2000/186.crafty/186.crafty_secs 0.34
External/SPEC/CINT2000/197.parser/197.parser_secs 0.61
External/SPEC/CINT2000/252.eon/252.eon_secs 1.80
External/SPEC/CINT2000/253.perlbmk/253.perlbmk_secs -3.65
External/SPEC/CINT2000/254.gap/254.gap_secs -0.91
External/SPEC/CINT2000/255.vortex/255.vortex_secs 0.21
External/SPEC/CINT2000/256.bzip2/256.bzip2_secs -3.35
External/SPEC/CINT2000/300.twolf/300.twolf_secs -5.65

Worked in collaboration with Aditya Kumar and Sebastian Pop.

[sebpop]

llvm/test/Transforms/LoopVectorize/LoopWithConstTripCount1.ll

19

Misspell CHECK-LABLE.

llvm/test/Transforms/LoopVectorize/LoopWithConstTripCount2.ll

25

Misspell CHECK-LABEL.

[hfinkel]

This is not the right solution to this problem. Loop vectorization is not a canonicalization pass, but a lowering pass, and should not be moved into the canonicalization part of the pipeline.

Should these loops be fully unrolled at all? The targets can influence the thresholds used for unrolling, and perhaps those need better tuning. After a loop is fully unrolled, if we're missing vectorization opportunities, why is the SLP vectorizer not catching them?

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addFunctionSimplificationPasses(
   addInstructionCombiningPass(MPM);
   MPM.add(createIndVarSimplifyPass());        // Canonicalize indvars
   MPM.add(createLoopIdiomPass());             // Recognize idioms like memset.
   MPM.add(createLoopDeletionPass());          // Delete dead loops
   if (EnableLoopInterchange) {
     MPM.add(createLoopInterchangePass()); // Interchange loops
     MPM.add(createCFGSimplificationPass());
   }
+
+  MPM.add(createLoopVectorizePass(DisableUnrollLoops, LoopVectorize));
+
   if (!DisableUnrollLoops)
     MPM.add(createSimpleLoopUnrollPass());    // Unroll small loops
   addExtensionsToPM(EP_LoopOptimizerEnd, MPM);
 
   if (OptLevel > 1) {
     if (EnableMLSM)
       MPM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds
     MPM.add(createGVNPass(DisableGVNLoadPRE));  // Remove redundancies
void PassManagerBuilder::populateModulePassManager(
   MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
 
   // Distribute loops to allow partial vectorization.  I.e. isolate dependences
   // into separate loop that would otherwise inhibit vectorization.  This is
   // currently only performed for loops marked with the metadata
   // llvm.loop.distribute=true or when -enable-loop-distribute is specified.
   MPM.add(createLoopDistributePass(/*ProcessAllLoopsByDefault=*/false));
 
-  MPM.add(createLoopVectorizePass(DisableUnrollLoops, LoopVectorize));
 
   // Eliminate loads by forwarding stores from the previous iteration to loads
   // of the current iteration.
   if (EnableLoopLoadElim)
     MPM.add(createLoopLoadEliminationPass());
 
   // FIXME: Because of #pragma vectorize enable, the passes below are always
   // inserted in the pipeline, even when the vectorizer doesn't run (ex. when

llvm/test/Other/pass-pipelines.ll

 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Combine redundant instructions
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NOT: Manager
 ; FIXME: It isn't clear that we need yet another loop pass pipeline
 ; and run of LICM here.
 ; CHECK-O2-NOT: Manager
+; CHECK-O2: Loop Vectorization
+; CHECK-O2-NOT: Manager
+; CHECK-O2: Loop Pass Manager
+; Check-O2-NEXT: Unroll loops
 ; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NEXT: Loop Invariant Code Motion
 ; CHECK-O2-NOT: Manager
 ; Next we break out of the main Function passes inside the CGSCC pipeline with
 ; a barrier pass.
 ; CHECK-O2: A No-Op Barrier Pass
 ; Reduce the size of the IR ASAP after the inliner.
 ; CHECK-O2-NEXT: Eliminate Available Externally
 ; Inferring function attribute should be right after the CGSCC pipeline, before
 ; any other optimizations/analyses.
 ; CHECK-O2-NEXT: CallGraph
 ; CHECK-O2-NEXT: Deduce function attributes in RPO
 ; CHECK-O2-NOT: Manager
 ; Next is the late function pass pipeline.
 ; CHECK-O2: FunctionPass Manager
 ; CHECK-O2-NOT: Manager
 ; We rotate loops prior to vectorization.
 ; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NEXT: Rotate Loops
 ; CHECK-O2-NOT: Manager
-; CHECK-O2: Loop Vectorization
-; CHECK-O2-NOT: Manager
 ; CHECK-O2: SLP Vectorizer
 ; CHECK-O2-NOT: Manager
 ; After vectorization we do partial unrolling.
 ; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NEXT: Unroll loops
 ; CHECK-O2-NOT: Manager
 ; After vectorization and unrolling we try to do any cleanup of inserted code,
 ; including a run of LICM. This shouldn't run in the same loop pass manager as

llvm/test/Transforms/LoopVectorize/LoopWithConstTripCount1.ll

+; RUN: opt < %s -O3 -S | FileCheck %s
+
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+;This is test is to verify the loop with constant trip count is getting vectorize.
+;original C code:
+;int a[32];
+;int reduce_add() {
+;  int s = 0;
+;  for (int i = 0; i < 32; ++i)
+;    s = s + a[i];
+;  return s;
+;}
+;
+;https://llvm.org/bugs/show_bug.cgi?id=25748
+;
+;CHECK-LABEL:@_Z6reduceR1V
+;CHECK:load <4 x i16>
+;CHECK:zext <4 x i16>
+;CHECK:add <4 x i32>
+;CHECK:extractelement <4 x i32>
+
+%struct.V = type { [32 x i16] }
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z6reduceR1V(%struct.V* dereferenceable(64) %v) #0 {
+entry:
+  %v.addr = alloca %struct.V*, align 8
+  %sum = alloca i32, align 4
+  %i = alloca i32, align 4
+  store %struct.V* %v, %struct.V** %v.addr, align 8
+  store i32 0, i32* %sum, align 4
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32, i32* %i, align 4
+  %1 = load %struct.V*, %struct.V** %v.addr, align 8
+  %cmp = icmp slt i32 %0, 32
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %2 = load i32, i32* %i, align 4
+  %idxprom = sext i32 %2 to i64
+  %3 = load %struct.V*, %struct.V** %v.addr, align 8
+  %data = getelementptr inbounds %struct.V, %struct.V* %3, i32 0, i32 0
+  %arrayidx = getelementptr inbounds [32 x i16], [32 x i16]* %data, i64 0, i64 %idxprom
+  %4 = load i16, i16* %arrayidx, align 2
+  %conv = zext i16 %4 to i32
+  %5 = load i32, i32* %sum, align 4
+  %add = add nsw i32 %5, %conv
+  store i32 %add, i32* %sum, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %6 = load i32, i32* %i, align 4
+  %inc = add nsw i32 %6, 1
+  store i32 %inc, i32* %i, align 4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  %7 = load i32, i32* %sum, align 4
+  ret i32 %7
+}
+

llvm/test/Transforms/LoopVectorize/LoopWithConstTripCount2.ll

+; RUN: opt < %s -O3 -S | FileCheck %s
+
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+;This test is to verify that loop with constant trip count is getting vectorize.
+;original code:
+;struct V {
+;  static constexpr int length = 32;
+;  unsigned short data[32];
+;};
+;
+;int reduce(V &v) {
+;  int sum = 0;
+;  for (int i = 0; i < v.length; ++i) {
+;    sum += static_cast<int>(v.data[i]);
+;  }
+;  return sum;
+;}
+;
+;https://llvm.org/bugs/show_bug.cgi?id=28090
+
+;CHECK-LABEL: @reduce_add
+;CHECK:load <4 x i32>
+;CHECK:add <4 x i32>
+;CHECK:extractelement <4 x i32>
+
+@a = common global [32 x i32] zeroinitializer, align 16
+
+define i32 @reduce_add() #0 {
+entry:
+  %s = alloca i32, align 4
+  %i = alloca i32, align 4
+  store i32 0, i32* %s, align 4
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32, i32* %i, align 4
+  %cmp = icmp slt i32 %0, 32
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %1 = load i32, i32* %s, align 4
+  %2 = load i32, i32* %i, align 4
+  %idxprom = sext i32 %2 to i64
+  %arrayidx = getelementptr inbounds [32 x i32], [32 x i32]* @a, i64 0, i64 %idxprom
+  %3 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %1, %3
+  store i32 %add, i32* %s, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %4 = load i32, i32* %i, align 4
+  %inc = add nsw i32 %4, 1
+  store i32 %inc, i32* %i, align 4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  %5 = load i32, i32* %s, align 4
+  ret i32 %5
+}
+