[SLP] Avoid signed integer overflow

[mssimpso]

Summary

The test case included with r279125 exposed an existing signed integer overflow. Since getTreeCost can return INT_MAX, we have to be careful to avoid undefined behavior when summing it with other costs, such as getReductionCost.

This patch removes the possibility of assigning a cost INT_MAX. Since we were previously using INT_MAX as an indicator for "should not vectorize", we now explicitly check this condition with "canVectorizeTree" before computing a cost.

This patch adds a run-line to the test case used for r279125 that ensures we don't vectorize it. Previously, this line would vectorize the test case because of an undefined cost.

[mkuper]

Using SaturatingAdd here seems right, but:

a) I'd prefer it if the test did check something beyond "don't crash".
b) It would be better it if one of the language lawyers looked at the SaturatingAdd implementation. In particular, I'm not sure casting an out-of-range unsigned to signed is well-defined.

[mssimpso]

In D23723#521236, @mkuper wrote:

Using SaturatingAdd here seems right, but:

a) I'd prefer it if the test did check something beyond "don't crash".

Yeah, I agree. The difficulty now is that the total cost will be computed as INT_MAX (correctly), which will prevent vectorization in the first place. This really obfuscates the original problem. INT_MAX is set because of the depth < 3 check. The best thing to do might be to add a new command line option specifying the depth at which we declare the tree completely unprofitable to vectorize (instead of hard-coding it to 3). We can then raise the threshold in one run-line to avoid INT_MAX and re-enable vectorization. Another run-line can use the default threshold and ensure the cost doesn't wrap.

b) It would be better it if one of the language lawyers looked at the SaturatingAdd implementation. In particular, I'm not sure casting an out-of-range unsigned to signed is well-defined.

Sure, I'll add more folks to the review.

[mssimpso]

Daniel,

Would you mind taking a look at the signed version of SaturatingAdd I added when you have a chance. I think you added the existing unsigned version. Thanks!

[mssimpso]

Hi Michael,

According to @gberry, the signed SaturatingAdd implementation I added isn't well-defined as you guessed. I started rewriting it, but I think a better solution might be to avoid INT_MAX all together. We're using INT_MAX to essentially indicate "do not vectorize". I think it makes better sense to put the INT_MAX logic in a function that returns a bool.

I've updated the patch to do this. I've also kept the existing test case intact, and added a new run-line checking for no vectorization. The test was being vectorized by chance due to the undefined behavior.

[mkuper]

This LGTM except for the name. :-)

I think the name shouldVectorizeTree() implies that if true, we will vectorize - while in fact, we still need to pass the cost check.
I'd say either (a) rename it to something more explicit (something that references the fact we're checking whether the tree is tiny), or (b) have a single function to perform both the "tininess" check and the cost check.

[mssimpso]

Thanks, Michael! I'll rewrite the function as isTreeTinyAndNotFullyVectorizable.

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

unsigned getMinVecRegSize() const {
     return MinVecRegSize;
   }
 
   /// \brief Check if ArrayType or StructType is isomorphic to some VectorType.
   ///
   /// \returns number of elements in vector if isomorphism exists, 0 otherwise.
   unsigned canMapToVector(Type *T, const DataLayout &DL) const;
 
+  /// \returns True if the VectorizableTree is both tiny and not fully
+  /// vectorizable. We do not vectorize such trees.
+  bool isTreeTinyAndNotFullyVectorizable();
+
 private:
   struct TreeEntry;
 
   /// \returns the cost of the vectorizable entry.
   int getEntryCost(TreeEntry *E);
 
   /// This is the recursive part of buildTree.
   void buildTree_rec(ArrayRef<Value *> Roots, unsigned Depth);
bool BoUpSLP::isFullyVectorizableTinyTree() {
 
   // Gathering cost would be too much for tiny trees.
   if (VectorizableTree[0].NeedToGather || VectorizableTree[1].NeedToGather)
     return false;
 
   return true;
 }
 
+bool BoUpSLP::isTreeTinyAndNotFullyVectorizable() {
+
+  // We can vectorize the tree if its size is greater than or equal to the
+  // minimum size specified by the MinTreeSize command line option.
+  if (VectorizableTree.size() >= MinTreeSize)
+    return false;
+
+  // If we have a tiny tree (a tree whose size is less than MinTreeSize), we
+  // can vectorize it if we can prove it fully vectorizable.
+  if (isFullyVectorizableTinyTree())
+    return false;
+
+  assert(VectorizableTree.empty()
+             ? ExternalUses.empty()
+             : true && "We shouldn't have any external users");
+
+  // Otherwise, we can't vectorize the tree. It is both tiny and not fully
+  // vectorizable.
+  return true;
+}
+
 int BoUpSLP::getSpillCost() {
   // Walk from the bottom of the tree to the top, tracking which values are
   // live. When we see a call instruction that is not part of our tree,
   // query TTI to see if there is a cost to keeping values live over it
   // (for example, if spills and fills are required).
   unsigned BundleWidth = VectorizableTree.front().Scalars.size();
   int Cost = 0;
 
int BoUpSLP::getSpillCost() {
   return Cost;
 }
 
 int BoUpSLP::getTreeCost() {
   int Cost = 0;
   DEBUG(dbgs() << "SLP: Calculating cost for tree of size " <<
         VectorizableTree.size() << ".\n");
 
-  // We only vectorize tiny trees if it is fully vectorizable.
-  if (VectorizableTree.size() < MinTreeSize && !isFullyVectorizableTinyTree()) {
-    if (VectorizableTree.empty()) {
-      assert(!ExternalUses.size() && "We should not have any external users");
-    }
-    return INT_MAX;
-  }
-
   unsigned BundleWidth = VectorizableTree[0].Scalars.size();
 
   for (TreeEntry &TE : VectorizableTree) {
     int C = getEntryCost(&TE);
     DEBUG(dbgs() << "SLP: Adding cost " << C << " for bundle that starts with "
                  << *TE.Scalars[0] << ".\n");
     Cost += C;
   }
for (unsigned i = 0, e = ChainLen; i < e; ++i) {
     if (hasValueBeenRAUWed(Chain, TrackValues, i, VF))
       continue;
 
     DEBUG(dbgs() << "SLP: Analyzing " << VF << " stores at offset " << i
           << "\n");
     ArrayRef<Value *> Operands = Chain.slice(i, VF);
 
     R.buildTree(Operands);
+    if (R.isTreeTinyAndNotFullyVectorizable())
+      continue;
+
     R.computeMinimumValueSizes();
 
     int Cost = R.getTreeCost();
 
     DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n");
     if (Cost < CostThreshold) {
       DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n");
       R.vectorizeTree();
if (allowReorder && R.shouldReorder()) {
       // reorder a larger list. In fact, we do exactly this when vectorizing
       // reductions. However, at this point, we only expect to get here from
       // tryToVectorizePair().
       assert(Ops.size() == 2);
       assert(BuildVectorSlice.empty());
       Value *ReorderedOps[] = { Ops[1], Ops[0] };
       R.buildTree(ReorderedOps, None);
     }
+    if (R.isTreeTinyAndNotFullyVectorizable())
+      continue;
+
     R.computeMinimumValueSizes();
     int Cost = R.getTreeCost();
 
     if (Cost < -SLPCostThreshold) {
       DEBUG(dbgs() << "SLP: Vectorizing list at cost:" << Cost << ".\n");
       Value *VectorizedRoot = R.vectorizeTree();
 
       // Reconstruct the build vector by extracting the vectorized root. This
bool tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI) {
     unsigned i = 0;
 
     for (; i < NumReducedVals - ReduxWidth + 1; i += ReduxWidth) {
       auto VL = makeArrayRef(&ReducedVals[i], ReduxWidth);
       V.buildTree(VL, ReductionOps);
       if (V.shouldReorder()) {
         SmallVector<Value *, 8> Reversed(VL.rbegin(), VL.rend());
         V.buildTree(Reversed, ReductionOps);
-      }      
+      }
+      if (V.isTreeTinyAndNotFullyVectorizable())
+        continue;
+
       V.computeMinimumValueSizes();
 
       // Estimate cost.
       int Cost = V.getTreeCost() + getReductionCost(TTI, ReducedVals[i]);
       if (Cost >= -SLPCostThreshold)
         break;
 
       DEBUG(dbgs() << "SLP: Vectorizing horizontal reduction at cost:" << Cost

llvm/trunk/test/Transforms/SLPVectorizer/AArch64/gather-root.ll

 ; RUN: opt < %s -slp-vectorizer -S | FileCheck %s --check-prefix=DEFAULT
 ; RUN: opt < %s -slp-schedule-budget=0 -slp-min-tree-size=0 -slp-threshold=-30 -slp-vectorizer -S | FileCheck %s --check-prefix=GATHER
+; RUN: opt < %s -slp-schedule-budget=0 -slp-threshold=-30 -slp-vectorizer -S | FileCheck %s --check-prefix=MAX-COST
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64--linux-gnu"
 
 @a = common global [80 x i8] zeroinitializer, align 16
 
 ; DEFAULT-LABEL: @PR28330(
 ; DEFAULT: %tmp17 = phi i32 [ %tmp34, %for.body ], [ 0, %entry ]

 ; GATHER: %[[R0:.+]] = shufflevector <8 x i32> %[[I7]], <8 x i32> undef, <8 x i32> <i32 4, i32 5, i32 6, i32 7, i32 undef, i32 undef, i32 undef, i32 undef>
 ; GATHER: %[[R1:.+]] = add <8 x i32> %[[I7]], %[[R0]]
 ; GATHER: %[[R2:.+]] = shufflevector <8 x i32> %[[R1]], <8 x i32> undef, <8 x i32> <i32 2, i32 3, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
 ; GATHER: %[[R3:.+]] = add <8 x i32> %[[R1]], %[[R2]]
 ; GATHER: %[[R4:.+]] = shufflevector <8 x i32> %[[R3]], <8 x i32> undef, <8 x i32> <i32 1, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
 ; GATHER: %[[R5:.+]] = add <8 x i32> %[[R3]], %[[R4]]
 ; GATHER: %[[R6:.+]] = extractelement <8 x i32> %[[R5]], i32 0
 ; GATHER: %tmp34 = add i32 %[[R6]], %tmp17
+;
+; MAX-COST-LABEL: @PR28330(
+; MAX-COST-NOT: shufflevector
 
 define void @PR28330(i32 %n) {
 entry:
   %tmp0 = load i8, i8* getelementptr inbounds ([80 x i8], [80 x i8]* @a, i64 0, i64 1), align 1
   %tmp1 = icmp eq i8 %tmp0, 0
   %tmp2 = load i8, i8* getelementptr inbounds ([80 x i8], [80 x i8]* @a, i64 0, i64 2), align 2
   %tmp3 = icmp eq i8 %tmp2, 0
   %tmp4 = load i8, i8* getelementptr inbounds ([80 x i8], [80 x i8]* @a, i64 0, i64 3), align 1