Fix PR19657 : SLP vectorization doesn't combine scalar load to vector loads

[karthikthecool]

Summary

Hi Nadav,Hal,Arnold,
This patch fixes PR19657. As Arnold pointed out the reason we miss to vectorize these loads is we are processing the smaller subtree before the larger subtree. This patch calculates the depth of the subtress before calling buildTree_rec and calls the buildTree_rec for the larger subtree before calling it for smaller subtree.

This seems to fix the problem and there are no regressions.
But I'm not sure if there is any easier and more efficient way to check this than actually traversing the subtrees and calculating their depth before we call buildTree_rec. It would be great if you could suggest improvements to this patch.

Thanks
Karthik Bhat

[nadav]

I am sorry but this is the wrong approach. You copy a ton of code that we will need to maintain if we want to add support to new instructions.

You also increase the compile time by scanning the tree twice. In the SLP vectorizer there are a bunch of features we did not implement because we did not want to increase compile time. Remember that we run this pass on all optimization levels.

[karthikthecool]

Thanks Nadav for the review. Yes i agree this increases the compile time as we will be scanning the tree multiple times. That is the reason i was not that sure and wanted to know if there is any better way to implement this? Or should we leave this as it is?
Thanks
Karthik

[echristo]

Any reason we don't want to check opt level when running to see how
aggressive we should be and how much we should spend compile time? Is
there some other approach you'd like to get optimizations like this?

-eric

[nadav]

Hi Eric,

[karthikthecool]

Hi Nadav,
I went through your suggestion but unfortunetly modification in consecutive memory address tests is not resulting in vectorization of these load instruction the reason being when the build_tree sees the user of load it has not processed the larger subtree and hence doesn't know that this user is part of the larger subtree which will get vectorized and hence assume we need to extract and concludes that can't schedule extractelement.

Checking for a larger subtree and processing it first avoids the above mentioned problem as we are able to conclude that the user of load is part of vectorizable subtree.
I added flag as suggested by Eric so that this vectorization runs only when slp-vectorize-load-aggressive is specified.

In order to avoid duplication we can roughly calculate the depth of the tree without being concerned if the tree gets vectorized or not. This is anyhow checked by buildTree_rec. The TreeDepth will now just traverse the tree till leaf node or till depth limit is reached and calculate the max depth of the tree. Please if you could let me know your inputs on this.

Thanks
Karthik Bhat

[rsilvera]

Is it really the depth of the subtrees that is the fundamental issue? Or is it really the relative depths of the common uses? If the latter, this patch wouldn't be addressing the general case.

Without looking too deeply, would it be feasible to defer the insertion of the extractions after the whole tree has been vectorized? If that sounds potentially fruitful I can dig a bit more on that direction.

[aschwaighofer]

It is the relative depth of common uses.

Without looking too deeply, would it be feasible to defer the insertion of the extractions after the whole tree has been vectorized? If that sounds potentially fruitful I can dig a bit more on that direction.

No because we would give up vectorization the tree at the scheduling conflict (that really is none but the algorithm we use can't tell because it uses program order).

But, I think we should get away (for this scheduling problem where the order we pick matters for the algorithm we use) of picking the subtree traversal based on basic block numbering (because the earlier user has to come in between the common use and the later user, so look at the later one first which will have a greater common depth if there is one). At least according to my on the back of the napkin reasoning ...

if (getLatestBBNumber(Left) > getLatestBBNumber(Right)) {

buildTree_rec(Left, depth+1)
buildTree_rec(Right, depth+1)

} else {

buildTree_rec(Right, depth+1)
 buildTree_rec(Left, depth+1)

}

[karthikthecool]

Hi Arnold,Nadav,Raul,
Thanks for the review. Using basic block numbering to decide which subtree to process seems to work in these cases. A larger subtree will have larger getLastIndex we can use the same to decide which subtree to process first. Updated the patch accordingly.
Does this approach look good?
I am still relatively new to this module so thanks for the patience and clarifications.
Regards
Karthik Bhat

[nadav]

Hi Karthik,

Can you please measure the effects of this patch on the LLVM test suite? It would be interesting to see if other workloads are affected by this change and if they improve or regress.

Thanks,
Nadav

[rsilvera]

I agree this is an improvement, but this approach is still failing to catch
cases where the common uses are not on separate paths on the tree. In those
cases no matter which order we take there will be a common use that can't
be scheduled.

Here is a sample case where we still fail to schedule a common load:

void foo(double *x, double C) {

x[0] = x[0]*C + x[0] * x[0];
x[1] = x[1]*C + x[1] * x[1];
}

Any ideas on how to get those cases? It would seem to me we'd need either a
prepass or deferral of the decisions until the whole tree is inspected.
Thoughts?

Raúl E Silvera | SWE | [e-mail] | *408-789-2846*

[rsilvera]

Typo: "the common uses *are *on separate paths..."

Raúl E Silvera | SWE | [e-mail] | *408-789-2846*

[karthikthecool]

Hi Nadav,
Please find the performance result with and without patch. I dont see large regression in compilation time though execution time of one test case improved greatly. The baseline is without patch and current is with patch.

Hi Raul,Arnold
I agree that the current patch will not handle the case mentioned. I was thinking of handling unschedulable loads again after buildTree_rec was completed but as arnold mentioned i'm not sure if this would be worth the ovehead.

For now do you think we can move ahead with this approach as we are able to vectorize loads similar to one's mentioned in the PR without much overhead?

Thanks for all the comments and review.

Regards
Karthik Bhat

[rsilvera]

Karthik, I do not have any objections to this patch. I think longer term we
should try to pursue the other cases but this is a good short-term step.

I'll let others provide their approval.

Raúl E Silvera | SWE | [e-mail] | *408-789-2846*

[nadav]

Karthik,

Please document the code that you are adding to the vectorization of binary operators.

+ buildTree_rec(Left, Depth + 1);
+ }
+ else {

Please format your patch properly.

Also, would it be better to swap Right and Left instead of duplicating the calls to buildTree_rec?

The performance numbers look okay. Do you know why we see a nice gain in the one workloads that wins?

Thanks,
Nadav

[karthikthecool]

Hi Nadav, I have a quick question. In case of commutative operation like the one we are handling here is it guaranteed that that right subtree height >= left subtree height always?
It seems so. I tried few examples -

void foo(double *x) {
  x[0] = x[0] * x[0] + x[0];
  x[1] = x[1] * x[1] + x[1];
  x[2] = x[2] * x[2] + x[2];
  x[3] = x[3] * x[3] + x[3];
}

and

void foo(double *x) {
  x[0] = x[0] + x[0] * x[0];
  x[1] = x[1] + x[1] * x[1];
  x[2] = x[2] + x[2] * x[2];
  x[3] = x[3] + x[3] * x[3];
}

The IR in both these cases are same and it seems we are reordering the IR so that the instructions for which the larger subtree will be constructed will always be on right side in case of commutative operations.
If this is guaranteed to do so we might be able to skip the getLastIndex check as well and directly call -

buildTree_rec(Right, Depth + 1);
buildTree_rec(Left, Depth + 1);

Thanks for the clarification.
Regards
Karthik Bhat

[karthikthecool]

Hi Nadav, Arnold,
Clang format code as per review comments. I think we cannot swap the right and left in buildTree_rec as we need to process the larger subtree before the smaller one and in case were Left subtree is larger we need to process it first hence we will need the check.

Does this look good to commit? I'm also looking into a generic solution for this problem as Raul suggested but it might need more time and benchmarking to make sure the benifit outweighs the overhead.

Thanks for your time.
Regards
Karthik Bhat

[karthikthecool]

Hi Nadav,
Thanks for your time and inputs.
Added documentation for the patch as per suggession.

Yes we had run llvm lit test cases with/without patch.
The results were submitted previously on phabricator you can have a look at the results on
http://reviews.llvm.org/file/data/s6jdoxcsfh2d5pog2a6x/PHID-FILE-lfpzyswqkebd2fj36nu6/performance.png
There were no considerable regressions and we saw one test case performance was improved.

Thanks once again for spending time on this patch.
Regards
Karthik Bhat

[nadav]

LGTM. Please commit.

[karthikthecool]

Comitted as r210310.
Thanks Nadav,Arnold,Raul and Eric for the review.

lib/Transforms/Vectorize/SLPVectorizer.cpp

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);
 
+  /// This is a recursive function to calculate the depth of a Tree
+  int getTreeDepth(ArrayRef<Value *> VL, unsigned Depth);
+
   /// Vectorize a single entry in the tree.
   Value *vectorizeTree(TreeEntry *E);
 
   /// Vectorize a single entry in the tree, starting in \p VL.
   Value *vectorizeTree(ArrayRef<Value *> VL);
 
   /// \returns the pointer to the vectorized value if \p VL is already
   /// vectorized, or NULL. They may happen in cycles.
for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
               Lane << " from " << *Scalar << ".\n");
         ExternalUses.push_back(ExternalUser(Scalar, U, Lane));
       }
     }
   }
 }
 
 
+int BoUpSLP::getTreeDepth(ArrayRef<Value *> VL, unsigned Depth) {
+
+  if (Depth == RecursionMaxDepth)
+    return Depth;
+
+  // Don't handle vectors return the current depth
+  if (VL[0]->getType()->isVectorTy()) {
+    return Depth;
+  }
+
+  if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) {
+    if (SI->getValueOperand()->getType()->isVectorTy()) {
+      return Depth;
+    }
+  }
+
+  if (allConstant(VL) || isSplat(VL) || !getSameBlock(VL) ||
+      !getSameOpcode(VL)) {
+    return Depth;
+  }
+
+  Instruction *VL0 = cast<Instruction>(VL[0]);
+  unsigned Opcode = getSameOpcode(VL);
+
+  switch (Opcode) {
+    case Instruction::PHI: {
+      PHINode *PH = dyn_cast<PHINode>(VL0);
+
+      // Check for terminator values (e.g. invoke).
+      for (unsigned j = 0; j < VL.size(); ++j)
+        for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
+          TerminatorInst *Term = dyn_cast<TerminatorInst>(
+              cast<PHINode>(VL[j])->getIncomingValueForBlock(PH->getIncomingBlock(i)));
+          if (Term) {
+             return Depth;
+          }
+        }
+      unsigned maxDepth = Depth;
+      for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
+        ValueList Operands;
+        for (unsigned j = 0; j < VL.size(); ++j)
+          Operands.push_back(cast<PHINode>(VL[j])->getIncomingValueForBlock(
+              PH->getIncomingBlock(i)));
+
+       unsigned depth = getTreeDepth(Operands, Depth + 1);
+       if(depth > maxDepth)
+         maxDepth = depth;
+      }
+      return maxDepth;
+    }
+    case Instruction::ExtractElement: {
+       return Depth;
+    }
+    case Instruction::Load: {
+       return Depth;
+    }
+    case Instruction::ZExt:
+    case Instruction::SExt:
+    case Instruction::FPToUI:
+    case Instruction::FPToSI:
+    case Instruction::FPExt:
+    case Instruction::PtrToInt:
+    case Instruction::IntToPtr:
+    case Instruction::SIToFP:
+    case Instruction::UIToFP:
+    case Instruction::Trunc:
+    case Instruction::FPTrunc:
+    case Instruction::BitCast: {
+      Type *SrcTy = VL0->getOperand(0)->getType();
+      for (unsigned i = 0; i < VL.size(); ++i) {
+        Type *Ty = cast<Instruction>(VL[i])->getOperand(0)->getType();
+        if (Ty != SrcTy || Ty->isAggregateType() || Ty->isVectorTy()) {
+          return Depth;
+        }
+      }
+      unsigned maxDepth = Depth;
+      for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
+        ValueList Operands;
+        for (unsigned j = 0; j < VL.size(); ++j)
+          Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
+
+        unsigned depth = getTreeDepth(Operands, Depth+1);
+        if(depth > maxDepth)
+          maxDepth = depth;
+      }
+      return maxDepth;
+    }
+    case Instruction::ICmp:
+    case Instruction::FCmp: {
+      CmpInst::Predicate P0 = dyn_cast<CmpInst>(VL0)->getPredicate();
+      Type *ComparedTy = cast<Instruction>(VL[0])->getOperand(0)->getType();
+      for (unsigned i = 1, e = VL.size(); i < e; ++i) {
+        CmpInst *Cmp = cast<CmpInst>(VL[i]);
+        if (Cmp->getPredicate() != P0 ||
+            Cmp->getOperand(0)->getType() != ComparedTy) {
+          return Depth;
+        }
+      }
+      unsigned maxDepth = Depth;
+      for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
+        ValueList Operands;
+        for (unsigned j = 0; j < VL.size(); ++j)
+          Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
+
+        unsigned depth = getTreeDepth(Operands, Depth+1);
+        if(depth > maxDepth)
+          maxDepth = depth;
+      }
+      return maxDepth;
+    }
+    case Instruction::Select:
+    case Instruction::Add:
+    case Instruction::FAdd:
+    case Instruction::Sub:
+    case Instruction::FSub:
+    case Instruction::Mul:
+    case Instruction::FMul:
+    case Instruction::UDiv:
+    case Instruction::SDiv:
+    case Instruction::FDiv:
+    case Instruction::URem:
+    case Instruction::SRem:
+    case Instruction::FRem:
+    case Instruction::Shl:
+    case Instruction::LShr:
+    case Instruction::AShr:
+    case Instruction::And:
+    case Instruction::Or:
+    case Instruction::Xor: {
+      unsigned maxDepth = Depth;
+      for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
+        ValueList Operands;
+        for (unsigned j = 0; j < VL.size(); ++j)
+          Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
+
+        unsigned depth = getTreeDepth(Operands, Depth+1);
+        if(depth > maxDepth)
+          maxDepth = depth;
+      }
+      return maxDepth;
+    }
+    case Instruction::Store: {
+      for (unsigned i = 0, e = VL.size() - 1; i < e; ++i)
+        if (!isConsecutiveAccess(VL[i], VL[i + 1])) {
+          return Depth;
+        }
+      unsigned maxDepth = Depth;
+      ValueList Operands;
+      for (unsigned j = 0; j < VL.size(); ++j)
+        Operands.push_back(cast<Instruction>(VL[j])->getOperand(0));
+
+      unsigned depth = getTreeDepth(Operands, Depth + 1);
+      if(depth > maxDepth)
+        maxDepth = depth;
+      return maxDepth;
+    }
+    case Instruction::Call: {
+      // Check if the calls are all to the same vectorizable intrinsic.
+      CallInst *CI = cast<CallInst>(VL[0]);
+      unsigned maxDepth = Depth;
+      // Check if this is an Intrinsic call or something that can be
+      // represented by an intrinsic call else we dont vectorize
+      // return the current depth.
+      Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
+      if (!isTriviallyVectorizable(ID)) {
+        return Depth;
+      }
+
+      Function *Int = CI->getCalledFunction();
+
+      for (unsigned i = 1, e = VL.size(); i != e; ++i) {
+        CallInst *CI2 = dyn_cast<CallInst>(VL[i]);
+        if (!CI2 || CI2->getCalledFunction() != Int ||
+            getIntrinsicIDForCall(CI2, TLI) != ID) {
+          return Depth;
+        }
+      }
+
+      for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) {
+        ValueList Operands;
+        for (unsigned j = 0; j < VL.size(); ++j) {
+          CallInst *CI2 = dyn_cast<CallInst>(VL[j]);
+          Operands.push_back(CI2->getArgOperand(i));
+        }
+        unsigned depth = getTreeDepth(Operands, Depth + 1);
+        if(depth > maxDepth)
+          maxDepth = depth;
+      }
+      return maxDepth;
+    }
+    default:
+      return Depth;
+  }
+
+}
+
 void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth) {
   bool SameTy = getSameType(VL); (void)SameTy;
   assert(SameTy && "Invalid types!");
 
   if (Depth == RecursionMaxDepth) {
     DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n");
     newTreeEntry(VL, false);
     return;
case Instruction::Xor: {
       newTreeEntry(VL, true);
       DEBUG(dbgs() << "SLP: added a vector of bin op.\n");
 
       // Sort operands of the instructions so that each side is more likely to
       // have the same opcode.
       if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) {
         ValueList Left, Right;
         reorderInputsAccordingToOpcode(VL, Left, Right);
+        unsigned leftSubTreeDepth = getTreeDepth(Left, 1);
+        unsigned rightSubTreeDepth = getTreeDepth(Right, 1);
+
+
+        if(leftSubTreeDepth >= rightSubTreeDepth) {
           buildTree_rec(Left, Depth + 1);
           buildTree_rec(Right, Depth + 1);
+        }
+        else {
+          buildTree_rec(Right, Depth + 1);
+          buildTree_rec(Left, Depth + 1);
+        }
         return;
       }
 
       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
         for (unsigned j = 0; j < VL.size(); ++j)
           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));

test/Transforms/SLPVectorizer/X86/pr19657.ll

+; RUN: opt < %s -O1 -basicaa -slp-vectorizer -dce -S -mtriple=x86_64-unknown-linux-gnu -mcpu=corei7-avx | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+;CHECK: load <2 x double>*
+;CHECK: fadd <2 x double>
+;CHECK: store <2 x double>
+
+; Function Attrs: nounwind uwtable
+define void @foo(double* %x) #0 {
+  %1 = alloca double*, align 8
+  store double* %x, double** %1, align 8
+  %2 = load double** %1, align 8
+  %3 = getelementptr inbounds double* %2, i64 0
+  %4 = load double* %3, align 8
+  %5 = load double** %1, align 8
+  %6 = getelementptr inbounds double* %5, i64 0
+  %7 = load double* %6, align 8
+  %8 = fadd double %4, %7
+  %9 = load double** %1, align 8
+  %10 = getelementptr inbounds double* %9, i64 0
+  %11 = load double* %10, align 8
+  %12 = fadd double %8, %11
+  %13 = load double** %1, align 8
+  %14 = getelementptr inbounds double* %13, i64 0
+  store double %12, double* %14, align 8
+  %15 = load double** %1, align 8
+  %16 = getelementptr inbounds double* %15, i64 1
+  %17 = load double* %16, align 8
+  %18 = load double** %1, align 8
+  %19 = getelementptr inbounds double* %18, i64 1
+  %20 = load double* %19, align 8
+  %21 = fadd double %17, %20
+  %22 = load double** %1, align 8
+  %23 = getelementptr inbounds double* %22, i64 1
+  %24 = load double* %23, align 8
+  %25 = fadd double %21, %24
+  %26 = load double** %1, align 8
+  %27 = getelementptr inbounds double* %26, i64 1
+  store double %25, double* %27, align 8
+  %28 = load double** %1, align 8
+  %29 = getelementptr inbounds double* %28, i64 2
+  %30 = load double* %29, align 8
+  %31 = load double** %1, align 8
+  %32 = getelementptr inbounds double* %31, i64 2
+  %33 = load double* %32, align 8
+  %34 = fadd double %30, %33
+  %35 = load double** %1, align 8
+  %36 = getelementptr inbounds double* %35, i64 2
+  %37 = load double* %36, align 8
+  %38 = fadd double %34, %37
+  %39 = load double** %1, align 8
+  %40 = getelementptr inbounds double* %39, i64 2
+  store double %38, double* %40, align 8
+  %41 = load double** %1, align 8
+  %42 = getelementptr inbounds double* %41, i64 3
+  %43 = load double* %42, align 8
+  %44 = load double** %1, align 8
+  %45 = getelementptr inbounds double* %44, i64 3
+  %46 = load double* %45, align 8
+  %47 = fadd double %43, %46
+  %48 = load double** %1, align 8
+  %49 = getelementptr inbounds double* %48, i64 3
+  %50 = load double* %49, align 8
+  %51 = fadd double %47, %50
+  %52 = load double** %1, align 8
+  %53 = getelementptr inbounds double* %52, i64 3
+  store double %51, double* %53, align 8
+  ret void
+}
+
+attributes #0 = { nounwind }