[LoopVectorizer] Refine loop vectorizer's register usage calculator by ignoring specific instructions.

[congh]

Summary

LoopVectorizationCostModel::calculateRegisterUsage() is used to estimate the register usage for specific VFs. However, it takes into account many instructions that won't be vectorized, such as induction variables, GetElementPtr instruction, etc.. This makes the loop vectorizer too conservative when choosing VF. In this patch, the induction variables that won't be vectorized plus GetElementPtr instruction will be added to ValuesToIgnore set so that their register usage won't be considered any more.

[jmolloy]

Hi Cong,

Thanks for doing this. I have a bunch of comments below.

Cheers,

James

lib/Transforms/Vectorize/LoopVectorize.cpp

1526

Everything else has a (pointless) comment - let's add a (pointless) comment here for consistency's sake.

5175

Why this change?

5656

This is not the right way to determine which user (if any) updates the PHI. In fact, it could be a chain of users, and they could be in any order.

The right way is to check the incoming value of the induction PHI from the loop latch.

5668

Redefining this variable is confusing - it should be given a unique name.

5681

I can't help but feel this is all a bit long-winded. Something like this should work and is a lot shorter (if you don't suffer from STL allergies):

for (auto &Induction : *Legal->getInductionVars()) {
  auto *PN = KV.first;
  auto *UpdateV = PN->getIncomingValueForBlock(L->getLoopLatch());

  // Check that the PHI is only used by the induction increment (UpdateV) or
  // by GEPs.
  // Then, check that UpdateV is only used by a compare instruction or the loop
  // header PHI.
  if (std::all_of(PN->user_begin(), PN->user_end(), [&](const User *U) {
        return U == UpdateV || isa<GetElementPtrInst>(U);
      }) &&
      std::all_of(UpdateV->user_begin(), UpdateV->user_end(), [&](const User *U) {
        return U == PN || isa<ICmpInst>(U);
      })) {
    ValuesToIgnore.insert(PN);
    ValuesToIgnore.insert(UpdateV);
  }
}

5688

Surely this isn't right - GEPs can be vectorized if they have pointer type, right? as in scatter gather?

test/Transforms/LoopVectorize/X86/vector_max_bandwidth.ll

19

I don't understand why your changes should affect the VF being selected. It should affect the UF only, right?

[congh]

Thank you very much for the review, James! Please check my inline replies.

lib/Transforms/Vectorize/LoopVectorize.cpp

1526

OK.

5175

This is actually fixing a previous bug: we need to update OpenIntervals by removing instructions that end at the current location, even when we ignore values in ValuesToIgnore. Those instructions to remove won't be considered later.

5681

Thank you very much for the suggested code. I love STL. I have applied your code in this patch.

5688

I have added the check and now we only ignore this instruction if its last operand is an induction var. Do you have better implementation suggestion here?

BTW, does LLVM support scatter/gather now? It seems that vectorizeBlockInLoop doesn't vectorize this operation.

test/Transforms/LoopVectorize/X86/vector_max_bandwidth.ll

19

With the patch http://reviews.llvm.org/D8943, VF is also determined by register usage when -vectorizer-maximize-bandwidth is turned on (as is in this test file).

[congh]

Update the patch according to James's comments.

[RKSimon]

Sorry but I don't know enough about the vectorizers to review.

[hfinkel]

lib/Transforms/Vectorize/LoopVectorize.cpp

5634

You need to have a different behavior here for VF == 1 vs. VF > 1. The VF == 1 case is important because it is used to control the interleave factor (calculateRegisterUsage is called from LoopVectorizationCostModel::selectInterleaveCount). For the VF == 1 case, a number of these exclusions don't apply.

5647

Aren't these also used by add or sub by a constant?

5675

Typo: inductoin

5678

dyn_cast -> cast (it is known not to fail here)

5680

I suspect you want to use getGEPInductionOperand (from include/llvm/Analysis/VectorUtils.h) to pick the operand index so that you ignore trailing zero operands.

[congh]

Update the patch based on Hal's comments.

[congh]

lib/Transforms/Vectorize/LoopVectorize.cpp

5634

Good catch! I have created a new set to store values to ignore when VF > 1 and only add my newly added values to ignore to this new set. This set is then used to calculate register usages for VF > 1.

5647

Yes, induction variables can participate in arithmetic operations. But I still have to follow the def-use chain and check if the value that is defined directly/indirectly is stored (it seems that the reduction with an induction variable cannot be vectorized now). Do you have any idea except doing it in a DFS manner?

5680

I think getGEPInductionOperand is what I want here. I have updated this part. Thanks!

[hfinkel]

lib/Transforms/Vectorize/LoopVectorize.cpp

5643

Shouldn't this be VecValuesToIgnore? These casts are not vectorized, but they are scalar instructions that maintain a live value in a register.

(Is this the only contributor to ValuesToIgnore?)

[congh]

lib/Transforms/Vectorize/LoopVectorize.cpp

5643

OK. This is actually from previous code that I didn't change, which is used in all cases no matter what VF is. Updated.

[congh]

Update the patch according to Hal's comment.

[congh]

lib/Transforms/Vectorize/LoopVectorize.cpp

5643

Now the only contributor are ephemeral values that are added above.

[hfinkel]

LGTM.

lib/Transforms/Vectorize/LoopVectorize.cpp

5643

That makes sense.

lib/Transforms/Vectorize/LoopVectorize.cpp

 class LoopVectorizationCostModel {
 public:
   LoopVectorizationCostModel(Loop *L, ScalarEvolution *SE, LoopInfo *LI,
                              LoopVectorizationLegality *Legal,
                              const TargetTransformInfo &TTI,
                              const TargetLibraryInfo *TLI, DemandedBits *DB,
                              AssumptionCache *AC, const Function *F,
                              const LoopVectorizeHints *Hints,
-                             SmallPtrSetImpl<const Value *> &ValuesToIgnore,
                              SCEVUnionPredicate &Preds)
       : TheLoop(L), SE(SE), LI(LI), Legal(Legal), TTI(TTI), TLI(TLI), DB(DB),
-        TheFunction(F), Hints(Hints), ValuesToIgnore(ValuesToIgnore) {}
+        AC(AC), TheFunction(F), Hints(Hints) {}
 
   /// Information about vectorization costs
   struct VectorizationFactor {
     unsigned Width; // Vector width with best cost
     unsigned Cost; // Cost of the loop with that width
   };
   /// \return The most profitable vectorization factor and the cost of that VF.
   /// This method checks every power of two up to VF. If UserVF is not ZERO
struct RegisterUsage {
     unsigned NumInstructions;
   };
 
   /// \return Returns information about the register usages of the loop for the
   /// given vectorization factors.
   SmallVector<RegisterUsage, 8>
   calculateRegisterUsage(const SmallVector<unsigned, 8> &VFs);
 
+  /// Collect values we want to ignore in the cost model.
+  void collectValuesToIgnore();
+
 private:
   /// Returns the expected execution cost. The unit of the cost does
   /// not matter because we use the 'cost' units to compare different
   /// vector widths. The cost that is returned is *not* normalized by
   /// the factor width.
   unsigned expectedCost(unsigned VF);
 
   /// Returns the execution time cost of an instruction for a given vector
public:
   /// Loop Info analysis.
   LoopInfo *LI;
   /// Vectorization legality.
   LoopVectorizationLegality *Legal;
   /// Vector target information.
   const TargetTransformInfo &TTI;
   /// Target Library Info.
   const TargetLibraryInfo *TLI;
-  /// Demanded bits analysis
+  /// Demanded bits analysis.
   DemandedBits *DB;
+  /// Assumption cache.
+  AssumptionCache *AC;
   const Function *TheFunction;
-  // Loop Vectorize Hint.
+  /// Loop Vectorize Hint.
   const LoopVectorizeHints *Hints;
-  // Values to ignore in the cost model.
-  const SmallPtrSetImpl<const Value *> &ValuesToIgnore;
+  /// Values to ignore in the cost model.
+  SmallPtrSet<const Value *, 16> ValuesToIgnore;
 };
 
 /// \brief This holds vectorization requirements that must be verified late in
 /// the process. The requirements are set by legalize and costmodel. Once
 /// vectorization has been determined to be possible and profitable the
 /// requirements can be verified by looking for metadata or compiler options.
 /// For example, some loops require FP commutativity which is only allowed if
 /// vectorization is explicitly specified or if the fast-math compiler option
#endif /* NDEBUG */
     LoopVectorizationLegality LVL(L, SE, DT, TLI, AA, F, TTI, LAA,
                                   &Requirements, &Hints, Preds);
     if (!LVL.canVectorize()) {
       DEBUG(dbgs() << "LV: Not vectorizing: Cannot prove legality.\n");
       emitMissedWarning(F, L, Hints);
       return false;
     }
 
-    // Collect values we want to ignore in the cost model. This includes
-    // type-promoting instructions we identified during reduction detection.
-    SmallPtrSet<const Value *, 32> ValuesToIgnore;
-    CodeMetrics::collectEphemeralValues(L, AC, ValuesToIgnore);
-    for (auto &Reduction : *LVL.getReductionVars()) {
-      RecurrenceDescriptor &RedDes = Reduction.second;
-      SmallPtrSetImpl<Instruction *> &Casts = RedDes.getCastInsts();
-      ValuesToIgnore.insert(Casts.begin(), Casts.end());
-    }
-
     // Use the cost model.
     LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, TLI, DB, AC, F, &Hints,
-                                  ValuesToIgnore, Preds);
+                                  Preds);
+    CM.collectValuesToIgnore();
 
     // Check the function attributes to find out if this function should be
     // optimized for size.
     bool OptForSize = Hints.getForce() != LoopVectorizeHints::FK_Enabled &&
                       F->optForSize();
 
     // Compute the weighted frequency of this loop being executed and see if it
     // is less than 20% of the function entry baseline frequency. Note that we
auto GetRegUsage = [&DL, WidestRegister](Type *Ty, unsigned VF) {
     return std::max<unsigned>(1, VF * TypeSize / WidestRegister);
   };
 
   for (unsigned int i = 0; i < Index; ++i) {
     Instruction *I = IdxToInstr[i];
     // Ignore instructions that are never used within the loop.
     if (!Ends.count(I)) continue;
 
-    // Skip ignored values.
-    if (ValuesToIgnore.count(I))
-      continue;
-
     // Remove all of the instructions that end at this location.
     InstrList &List = TransposeEnds[i];
     for (unsigned int j = 0, e = List.size(); j < e; ++j)
       OpenIntervals.erase(List[j]);
 
+    // Skip ignored values.
+    if (ValuesToIgnore.count(I))
+      continue;
+
     // For each VF find the maximum usage of registers.
     for (unsigned j = 0, e = VFs.size(); j < e; ++j) {
       if (VFs[j] == 1) {
         MaxUsages[j] = std::max(MaxUsages[j], OpenIntervals.size());
         continue;
       }
 
       // Count the number of live interals.
bool LoopVectorizationCostModel::isConsecutiveLoadOrStore(Instruction *Inst) {
 
   // Check for a load.
   if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
     return Legal->isConsecutivePtr(LI->getPointerOperand()) != 0;
 
   return false;
 }
 
+void LoopVectorizationCostModel::collectValuesToIgnore() {
+  // Ignore ephemeral values.
+  CodeMetrics::collectEphemeralValues(TheLoop, AC, ValuesToIgnore);
+
+  // Ignore type-promoting instructions we identified during reduction
+  // detection.
+  for (auto &Reduction : *Legal->getReductionVars()) {
+    RecurrenceDescriptor &RedDes = Reduction.second;
+    SmallPtrSetImpl<Instruction *> &Casts = RedDes.getCastInsts();
+    ValuesToIgnore.insert(Casts.begin(), Casts.end());
+  }
+
+  // Ignore induction phis that are only used in either GetElementPtr or ICmp
+  // instruction to exit loop. Induction variables usually have large types and
+  // can have big impact when estimating register usage.
+  for (auto &Induction : *Legal->getInductionVars()) {
+    auto *PN = Induction.first;
+    auto *UpdateV = PN->getIncomingValueForBlock(TheLoop->getLoopLatch());
+
+    // Check that the PHI is only used by the induction increment (UpdateV) or
+    // by GEPs. Then check that UpdateV is only used by a compare instruction or
+    // the loop header PHI.
+    if (std::all_of(PN->user_begin(), PN->user_end(),
+                    [&](const User *U) -> bool {
+                      return U == UpdateV || isa<GetElementPtrInst>(U);
+                    }) &&
+        std::all_of(UpdateV->user_begin(), UpdateV->user_end(),
+                    [&](const User *U) -> bool {
+                      return U == PN || isa<ICmpInst>(U);
+                    })) {
+      ValuesToIgnore.insert(PN);
+      ValuesToIgnore.insert(UpdateV);
+    }
+  }
+
+  // Ignore instructions that will not be vectorized.
+  for (auto bb = TheLoop->block_begin(), be = TheLoop->block_end(); bb != be;
+       ++bb) {
+    for (auto &Inst : **bb) {
+      switch (Inst.getOpcode()) {
+      case Instruction::GetElementPtr: {
+        // Ignore GEP if its last operand is an inductoin variable so that it is
+        // a consecutive load/store and won't be vectorized as scatter/gather
+        // pattern.
+        GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(&Inst);
+        unsigned NumOperands = Gep->getNumOperands();
+        if (Legal->isInductionVariable(Gep->getOperand(NumOperands - 1)))
+          ValuesToIgnore.insert(&Inst);
+        break;
+      }
+      }
+    }
+  }
+}
 
 void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr,
                                              bool IfPredicateStore) {
   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
   // Holds vector parameters or scalars, in case of uniform vals.
   SmallVector<VectorParts, 4> Params;
 
   setDebugLocFromInst(Builder, Instr);
 

test/Transforms/LoopVectorize/X86/vector_max_bandwidth.ll

 @v = global [1000 x i32] zeroinitializer, align 16
 @w = global [1000 x i32] zeroinitializer, align 16
 
 ; Tests that the vectorization factor is determined by the smallest instead of
 ; widest type in the loop for maximum bandwidth when
 ; -vectorizer-maximize-bandwidth is indicated.
 ;
 ; CHECK-label: foo
-; CHECK: LV: Selecting VF: 16.
+; CHECK: LV: Selecting VF: 32.
 define void @foo() {
 entry:
   br label %for.body
 
 for.cond.cleanup:
   ret void
 
 for.body:

test/Transforms/LoopVectorize/reg-usage.ll

+; RUN: opt < %s -mtriple=x86_64-unknown-unknown -mattr=+sse2 -debug-only=loop-vectorize -loop-vectorize -vectorizer-maximize-bandwidth 2>&1 | FileCheck %s
+
+
+@a = global [1024 x i8] zeroinitializer, align 16
+@b = global [1024 x i8] zeroinitializer, align 16
+
+define i32 @foo() {
+; This function has a loop of SAD pattern. Here we check when VF = 16 the
+; register usage doesn't exceed 16.
+;
+; CHECK-LABEL: foo
+; CHECK:      LV(REG): VF = 4
+; CHECK-NEXT: LV(REG): Found max usage: 4
+; CHECK:      LV(REG): VF = 8
+; CHECK-NEXT: LV(REG): Found max usage: 7
+; CHECK:      LV(REG): VF = 16
+; CHECK-NEXT: LV(REG): Found max usage: 13
+
+entry:
+  br label %for.body
+
+for.cond.cleanup:
+  %add.lcssa = phi i32 [ %add, %for.body ]
+  ret i32 %add.lcssa
+
+for.body:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %s.015 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds [1024 x i8], [1024 x i8]* @a, i64 0, i64 %indvars.iv
+  %0 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %0 to i32
+  %arrayidx2 = getelementptr inbounds [1024 x i8], [1024 x i8]* @b, i64 0, i64 %indvars.iv
+  %1 = load i8, i8* %arrayidx2, align 1
+  %conv3 = zext i8 %1 to i32
+  %sub = sub nsw i32 %conv, %conv3
+  %ispos = icmp sgt i32 %sub, -1
+  %neg = sub nsw i32 0, %sub
+  %2 = select i1 %ispos, i32 %sub, i32 %neg
+  %add = add nsw i32 %2, %s.015
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+define i64 @bar(i64* nocapture %a) {
+; CHECK-LABEL: bar
+; CHECK:       LV(REG): VF = 2
+; CHECK:       LV(REG): Found max usage: 4
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:
+  %add2.lcssa = phi i64 [ %add2, %for.body ]
+  ret i64 %add2.lcssa
+
+for.body:
+  %i.012 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
+  %s.011 = phi i64 [ 0, %entry ], [ %add2, %for.body ]
+  %arrayidx = getelementptr inbounds i64, i64* %a, i64 %i.012
+  %0 = load i64, i64* %arrayidx, align 8
+  %add = add nsw i64 %0, %i.012
+  store i64 %add, i64* %arrayidx, align 8
+  %add2 = add nsw i64 %add, %s.011
+  %inc = add nuw nsw i64 %i.012, 1
+  %exitcond = icmp eq i64 %inc, 1024
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}