[LoopAccessAnalysis] Recognize geps that include s/zexts as consecutive memory accesses.

[bmakam]

Summary

We have two versions of isConsecutiveAccess() in tree. The instance in the LoopAccessAnalysis is used to drive the SLP vectorizer
and to some degree the Loop Idiom Recognition pass. The other instance was recently committed with the LoadStoreVectorizer,
which has additional logic to deal with gep patterns that include zexts and sexts. This is useful to figure out that accesses
A[3*i], A[3*i+1] and A[3*i+2] are consecutive which SCEV currently fails to recognize.

This patch ports the additional logic from the LoadStoreVectorizer and merges the two versions into the LoopAccessAnalysis version.

Contributed-by: Chad Rosier <[e-mail]>

[mssimpso]

Balaram,

Here's a quick question before I start looking at the details. Won't we still have two implementations of isConsecutiveAccess after this change? Is something preventing us from replacing LoadStoreVectorizer::isConsecutiveAccess with llvm::isConsecutiveAccess?

[bmakam]

In D23854#525217, @mssimpso wrote:

Balaram,

Here's a quick question before I start looking at the details. Won't we still have two implementations of isConsecutiveAccess after this change? Is something preventing us from replacing LoadStoreVectorizer::isConsecutiveAccess with llvm::isConsecutiveAccess?

No. I will remove the implementation in LoadStoreVectorizer as a follow up patch if this looks good.

[mssimpso]

The logic looks fine, but I'm wondering if it makes sense to add this functionality directly into SCEV? It might be beneficial to transformations other than SLP and LoopIdiom. What do you think?

lib/Analysis/LoopAccessAnalysis.cpp

1112

It's probably not a big deal, but this part makes me wonder about compile-time a little. In SLP, for example, we can call isConsecutiveAccess in an N^2 algorithm (e.g., when we try and sort a set of stores). Is computeKNownBits smart about caching results or does it always traverse the expression tree?

It may be rare that we ever reach this code, though.

[bmakam]

Merge the two versions of isConsecutiveAccess into LoopAccessAnalysis and remove the implementation in LoadStoreVectorizer.

[bmakam]

In D23854#526264, @mssimpso wrote:

The logic looks fine, but I'm wondering if it makes sense to add this functionality directly into SCEV? It might be beneficial to transformations other than SLP and LoopIdiom. What do you think?

Matt, I agree with you in principle but I do not have enough understanding of how SCEV works and after my first time reading through SCEV analysis I do not know how involved it is to add this functionality directly into SCEV.

[bmakam]

lib/Analysis/LoopAccessAnalysis.cpp

1112

I think it is very rare we ever reach this code. In my testing on spec2k* I did not find any instance.

[mcrosier]

In D23854#528967, @bmakam wrote:

In D23854#526264, @mssimpso wrote:

The logic looks fine, but I'm wondering if it makes sense to add this functionality directly into SCEV? It might be beneficial to transformations other than SLP and LoopIdiom. What do you think?

Matt, I agree with you in principle but I do not have enough understanding of how SCEV works and after my first time reading through SCEV analysis I do not know how involved it is to add this functionality directly into SCEV.

I'm not opposed to leaving this as is (i.e., not enhancing SCEV). My main goal was to remove the redundant code in the LoadStoreVectorizer.

lib/Analysis/LoopAccessAnalysis.cpp

1112

Balaram,
Do you mean you added an assertion to make sure we never hit this code or that you didn't see any codegen changes for SPEC200X?

[bmakam]

lib/Analysis/LoopAccessAnalysis.cpp

1112

What I meant was I did not see any codegen changes but in retrospect I added assertion and it hits almost all of SPEC200x, so this might impact compile time.

[mcrosier]

lib/Analysis/LoopAccessAnalysis.cpp

1112

Alternatively, you might be able to add a statistic (or two) to determine how often we actually hit this code.

[bmakam]

lib/Analysis/LoopAccessAnalysis.cpp

1112

6417 accesses were analyzed using computeKnownBits in Spec2kX with several benchmarks hitting between 500-1000 times.

[bmakam]

I am abandoning this patch because of the additional complexity involved for very minimal performance gain. Please feel free to revisit if you think otherwise.

[mcrosier]

In D23854#531472, @bmakam wrote:

I am abandoning this patch because of the additional complexity involved for very minimal performance gain. Please feel free to revisit if you think otherwise.

SGTM. Regardless, thanks for taking a look, Balaram.

include/llvm/Analysis/LoopAccessAnalysis.h

 /// to \p PtrToStride and therefore add further predicates to \p PSE.
 /// The \p Assume parameter indicates if we are allowed to make additional
 /// run-time assumptions.
 int64_t getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr, const Loop *Lp,
                      const ValueToValueMap &StridesMap = ValueToValueMap(),
                      bool Assume = false);
 
 /// \brief Returns true if the memory operations \p A and \p B are consecutive.
-/// This is a simple API that does not depend on the analysis pass. 
+/// This is a simple API that does not depend on the analysis pass.
 bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
-                         ScalarEvolution &SE, bool CheckType = true);
+                         ScalarEvolution &SE, DominatorTree *DT,
+                         bool CheckType = true, bool CheckSizeType = false);
 
 /// \brief This analysis provides dependence information for the memory accesses
 /// of a loop.
 ///
 /// It runs the analysis for a loop on demand.  This can be initiated by
 /// querying the loop access info via LAA::getInfo.  getInfo return a
 /// LoopAccessInfo object.  See this class for the specifics of what information
 /// is provided.

lib/Analysis/LoopAccessAnalysis.cpp

if (LoadInst *L = dyn_cast<LoadInst>(I))
     return L->getPointerAddressSpace();
   if (StoreInst *S = dyn_cast<StoreInst>(I))
     return S->getPointerAddressSpace();
   return -1;
 }
 
 /// Returns true if the memory operations \p A and \p B are consecutive.
 bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
-                               ScalarEvolution &SE, bool CheckType) {
+                               ScalarEvolution &SE, DominatorTree *DT,
+                               bool CheckType, bool CheckSizeType) {
   Value *PtrA = getPointerOperand(A);
   Value *PtrB = getPointerOperand(B);
   unsigned ASA = getAddressSpaceOperand(A);
   unsigned ASB = getAddressSpaceOperand(B);
 
   // Check that the address spaces match and that the pointers are valid.
   if (!PtrA || !PtrB || (ASA != ASB))
     return false;
 
   // Make sure that A and B are different pointers.
   if (PtrA == PtrB)
     return false;
 
   // Make sure that A and B have the same type if required.
-  if(CheckType && PtrA->getType() != PtrB->getType())
-      return false;
+  if (!CheckSizeType && CheckType && PtrA->getType() != PtrB->getType())
+    return false;
+
+  // Make sure that A and B have the same size type if required.
+  Type *PtrATy = PtrA->getType()->getPointerElementType();
+  Type *PtrBTy = PtrB->getType()->getPointerElementType();
+  if (CheckSizeType &&
+      (DL.getTypeStoreSize(PtrATy) != DL.getTypeStoreSize(PtrBTy) ||
+       DL.getTypeStoreSize(PtrATy->getScalarType()) !=
+           DL.getTypeStoreSize(PtrBTy->getScalarType())))
 
   unsigned PtrBitWidth = DL.getPointerSizeInBits(ASA);
   Type *Ty = cast<PointerType>(PtrA->getType())->getElementType();
   APInt Size(PtrBitWidth, DL.getTypeStoreSize(Ty));
 
   APInt OffsetA(PtrBitWidth, 0), OffsetB(PtrBitWidth, 0);
   PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA);
   PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB);
bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
   // BaseDelta = Size - OffsetDelta;
   const SCEV *SizeSCEV = SE.getConstant(Size);
   const SCEV *BaseDelta = SE.getMinusSCEV(SizeSCEV, OffsetDeltaSCEV);
 
   // Otherwise compute the distance with SCEV between the base pointers.
   const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
   const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
   const SCEV *X = SE.getAddExpr(PtrSCEVA, BaseDelta);
-  return X == PtrSCEVB;
+  if (X == PtrSCEVB)
+    return true;
+
+  // Sometimes even this doesn't work, because SCEV can't always see through
+  // patterns that look like (gep (ext (add (shl X, C1), C2))). Try checking
+  // things the hard way.
+
+  // Look through GEPs after checking they're the same except for the last
+  // index.
+  GetElementPtrInst *GEPA = dyn_cast<GetElementPtrInst>(getPointerOperand(A));
+  GetElementPtrInst *GEPB = dyn_cast<GetElementPtrInst>(getPointerOperand(B));
+  if (!GEPA || !GEPB || GEPA->getNumOperands() != GEPB->getNumOperands())
+    return false;
+  unsigned FinalIndex = GEPA->getNumOperands() - 1;
+  for (unsigned i = 0; i < FinalIndex; i++)
+    if (GEPA->getOperand(i) != GEPB->getOperand(i))
+      return false;
+
+  Instruction *OpA = dyn_cast<Instruction>(GEPA->getOperand(FinalIndex));
+  Instruction *OpB = dyn_cast<Instruction>(GEPB->getOperand(FinalIndex));
+  if (!OpA || !OpB || OpA->getOpcode() != OpB->getOpcode() ||
+      OpA->getType() != OpB->getType())
+    return false;
+
+  // Only look through a ZExt/SExt.
+  if (!isa<SExtInst>(OpA) && !isa<ZExtInst>(OpA))
+    return false;
+
+  bool Signed = isa<SExtInst>(OpA);
+
+  OpA = dyn_cast<Instruction>(OpA->getOperand(0));
+  OpB = dyn_cast<Instruction>(OpB->getOperand(0));
+  if (!OpA || !OpB || OpA->getType() != OpB->getType())
+    return false;
+
+  // Now we need to prove that adding 1 to OpA won't overflow.
+  bool Safe = false;
+  // First attempt: if OpB is an add with NSW/NUW, and OpB is 1 added to OpA,
+  // we're okay.
+  if (OpB->getOpcode() == Instruction::Add &&
+      isa<ConstantInt>(OpB->getOperand(1)) &&
+      cast<ConstantInt>(OpB->getOperand(1))->getSExtValue() > 0) {
+    if (Signed)
+      Safe = cast<BinaryOperator>(OpB)->hasNoSignedWrap();
+    else
+      Safe = cast<BinaryOperator>(OpB)->hasNoUnsignedWrap();
+  }
+
+  unsigned BitWidth = OpA->getType()->getScalarSizeInBits();
+
+  // Second attempt:
+  // If any bits are known to be zero other than the sign bit in OpA, we can
+  // add 1 to it while guaranteeing no overflow of any sort.
+  if (!Safe && DT) {
+    APInt KnownZero(BitWidth, 0);
+    APInt KnownOne(BitWidth, 0);
+    computeKnownBits(OpA, KnownZero, KnownOne, DL, 0, nullptr, OpA, DT);
+    KnownZero &= ~APInt::getHighBitsSet(BitWidth, 1);
+    if (KnownZero != 0)
+      Safe = true;
+  }
+
+  if (!Safe)
+    return false;
+
+  OffsetSCEVA = SE.getSCEV(OpA);
+  OffsetSCEVB = SE.getSCEV(OpB);
+  const SCEV *One = SE.getConstant(APInt(BitWidth, 1));
+  const SCEV *X2 = SE.getAddExpr(OffsetSCEVA, One);
+  return X2 == OffsetSCEVB;
 }
 
 bool MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
   switch (Type) {
   case NoDep:
   case Forward:
   case BackwardVectorizable:
     return true;

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

for (auto &k : IndexQueue) {
       if (ForMemset)
         SecondSplatValue = isBytewiseValue(SecondStoredVal);
       else
         SecondPatternValue = getMemSetPatternValue(SecondStoredVal, DL);
 
       assert((SecondSplatValue || SecondPatternValue) &&
              "Expected either splat value or pattern value.");
 
-      if (isConsecutiveAccess(SL[i], SL[k], *DL, *SE, false)) {
+      if (isConsecutiveAccess(SL[i], SL[k], *DL, *SE, nullptr, false)) {
         if (ForMemset) {
           if (FirstSplatValue != SecondSplatValue)
             continue;
         } else {
           if (FirstPatternValue != SecondPatternValue)
             continue;
         }
         Tails.insert(SL[k]);

lib/Transforms/Vectorize/LoadStoreVectorizer.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
private:
   unsigned getAlignment(StoreInst *SI) const {
     unsigned Align = SI->getAlignment();
     if (Align != 0)
       return Align;
 
     return DL.getABITypeAlignment(SI->getValueOperand()->getType());
   }
 
-  bool isConsecutiveAccess(Value *A, Value *B);
-
   /// After vectorization, reorder the instructions that I depends on
   /// (the instructions defining its operands), to ensure they dominate I.
   void reorder(Instruction *I);
 
   /// Returns the first and the last instructions in Chain.
   std::pair<BasicBlock::iterator, BasicBlock::iterator>
   getBoundaryInstrs(ArrayRef<Instruction *> Chain);
 

 unsigned Vectorizer::getPointerAddressSpace(Value *I) {
   if (LoadInst *L = dyn_cast<LoadInst>(I))
     return L->getPointerAddressSpace();
   if (StoreInst *S = dyn_cast<StoreInst>(I))
     return S->getPointerAddressSpace();
   return -1;
 }
 
-// FIXME: Merge with llvm::isConsecutiveAccess
-bool Vectorizer::isConsecutiveAccess(Value *A, Value *B) {
-  Value *PtrA = getPointerOperand(A);
-  Value *PtrB = getPointerOperand(B);
-  unsigned ASA = getPointerAddressSpace(A);
-  unsigned ASB = getPointerAddressSpace(B);
-
-  // Check that the address spaces match and that the pointers are valid.
-  if (!PtrA || !PtrB || (ASA != ASB))
-    return false;
-
-  // Make sure that A and B are different pointers of the same size type.
-  unsigned PtrBitWidth = DL.getPointerSizeInBits(ASA);
-  Type *PtrATy = PtrA->getType()->getPointerElementType();
-  Type *PtrBTy = PtrB->getType()->getPointerElementType();
-  if (PtrA == PtrB ||
-      DL.getTypeStoreSize(PtrATy) != DL.getTypeStoreSize(PtrBTy) ||
-      DL.getTypeStoreSize(PtrATy->getScalarType()) !=
-          DL.getTypeStoreSize(PtrBTy->getScalarType()))
-    return false;
-
-  APInt Size(PtrBitWidth, DL.getTypeStoreSize(PtrATy));
-
-  APInt OffsetA(PtrBitWidth, 0), OffsetB(PtrBitWidth, 0);
-  PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA);
-  PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB);
-
-  APInt OffsetDelta = OffsetB - OffsetA;
-
-  // Check if they are based on the same pointer. That makes the offsets
-  // sufficient.
-  if (PtrA == PtrB)
-    return OffsetDelta == Size;
-
-  // Compute the necessary base pointer delta to have the necessary final delta
-  // equal to the size.
-  APInt BaseDelta = Size - OffsetDelta;
-
-  // Compute the distance with SCEV between the base pointers.
-  const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
-  const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
-  const SCEV *C = SE.getConstant(BaseDelta);
-  const SCEV *X = SE.getAddExpr(PtrSCEVA, C);
-  if (X == PtrSCEVB)
-    return true;
-
-  // Sometimes even this doesn't work, because SCEV can't always see through
-  // patterns that look like (gep (ext (add (shl X, C1), C2))). Try checking
-  // things the hard way.
-
-  // Look through GEPs after checking they're the same except for the last
-  // index.
-  GetElementPtrInst *GEPA = dyn_cast<GetElementPtrInst>(getPointerOperand(A));
-  GetElementPtrInst *GEPB = dyn_cast<GetElementPtrInst>(getPointerOperand(B));
-  if (!GEPA || !GEPB || GEPA->getNumOperands() != GEPB->getNumOperands())
-    return false;
-  unsigned FinalIndex = GEPA->getNumOperands() - 1;
-  for (unsigned i = 0; i < FinalIndex; i++)
-    if (GEPA->getOperand(i) != GEPB->getOperand(i))
-      return false;
-
-  Instruction *OpA = dyn_cast<Instruction>(GEPA->getOperand(FinalIndex));
-  Instruction *OpB = dyn_cast<Instruction>(GEPB->getOperand(FinalIndex));
-  if (!OpA || !OpB || OpA->getOpcode() != OpB->getOpcode() ||
-      OpA->getType() != OpB->getType())
-    return false;
-
-  // Only look through a ZExt/SExt.
-  if (!isa<SExtInst>(OpA) && !isa<ZExtInst>(OpA))
-    return false;
-
-  bool Signed = isa<SExtInst>(OpA);
-
-  OpA = dyn_cast<Instruction>(OpA->getOperand(0));
-  OpB = dyn_cast<Instruction>(OpB->getOperand(0));
-  if (!OpA || !OpB || OpA->getType() != OpB->getType())
-    return false;
-
-  // Now we need to prove that adding 1 to OpA won't overflow.
-  bool Safe = false;
-  // First attempt: if OpB is an add with NSW/NUW, and OpB is 1 added to OpA,
-  // we're okay.
-  if (OpB->getOpcode() == Instruction::Add &&
-      isa<ConstantInt>(OpB->getOperand(1)) &&
-      cast<ConstantInt>(OpB->getOperand(1))->getSExtValue() > 0) {
-    if (Signed)
-      Safe = cast<BinaryOperator>(OpB)->hasNoSignedWrap();
-    else
-      Safe = cast<BinaryOperator>(OpB)->hasNoUnsignedWrap();
-  }
-
-  unsigned BitWidth = OpA->getType()->getScalarSizeInBits();
-
-  // Second attempt:
-  // If any bits are known to be zero other than the sign bit in OpA, we can
-  // add 1 to it while guaranteeing no overflow of any sort.
-  if (!Safe) {
-    APInt KnownZero(BitWidth, 0);
-    APInt KnownOne(BitWidth, 0);
-    computeKnownBits(OpA, KnownZero, KnownOne, DL, 0, nullptr, OpA, &DT);
-    KnownZero &= ~APInt::getHighBitsSet(BitWidth, 1);
-    if (KnownZero != 0)
-      Safe = true;
-  }
-
-  if (!Safe)
-    return false;
-
-  const SCEV *OffsetSCEVA = SE.getSCEV(OpA);
-  const SCEV *OffsetSCEVB = SE.getSCEV(OpB);
-  const SCEV *One = SE.getConstant(APInt(BitWidth, 1));
-  const SCEV *X2 = SE.getAddExpr(OffsetSCEVA, One);
-  return X2 == OffsetSCEVB;
-}
-
 void Vectorizer::reorder(Instruction *I) {
   OrderedBasicBlock OBB(I->getParent());
   SmallPtrSet<Instruction *, 16> InstructionsToMove;
   SmallVector<Instruction *, 16> Worklist;
 
   Worklist.push_back(I);
   while (!Worklist.empty()) {
     Instruction *IW = Worklist.pop_back_val();
bool Vectorizer::vectorizeInstructions(ArrayRef<Instruction *> Instrs) {
   // Do a quadratic search on all of the given stores and find all of the pairs
   // of stores that follow each other.
   for (int i = 0, e = Instrs.size(); i < e; ++i) {
     ConsecutiveChain[i] = -1;
     for (int j = e - 1; j >= 0; --j) {
       if (i == j)
         continue;
 
-      if (isConsecutiveAccess(Instrs[i], Instrs[j])) {
+      if (isConsecutiveAccess(Instrs[i], Instrs[j], DL, SE, &DT, true, true)) {
         if (ConsecutiveChain[i] != -1) {
           int CurDistance = std::abs(ConsecutiveChain[i] - i);
           int NewDistance = std::abs(ConsecutiveChain[i] - j);
           if (j < i || NewDistance > CurDistance)
             continue; // Should not insert.
         }
 
         Tails.insert(j);

lib/Transforms/Vectorize/SLPVectorizer.cpp

case Instruction::Load: {
       }
 
       // Check if the loads are consecutive, reversed, or neither.
       // TODO: What we really want is to sort the loads, but for now, check
       // the two likely directions.
       bool Consecutive = true;
       bool ReverseConsecutive = true;
       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i) {
-        if (!isConsecutiveAccess(VL[i], VL[i + 1], *DL, *SE)) {
+        if (!isConsecutiveAccess(VL[i], VL[i + 1], *DL, *SE, DT)) {
           Consecutive = false;
           break;
         } else {
           ReverseConsecutive = false;
         }
       }
 
       if (Consecutive) {
         ++NumLoadsWantToKeepOrder;
         newTreeEntry(VL, true);
         DEBUG(dbgs() << "SLP: added a vector of loads.\n");
         return;
       }
 
       // If none of the load pairs were consecutive when checked in order,
       // check the reverse order.
       if (ReverseConsecutive)
         for (unsigned i = VL.size() - 1; i > 0; --i)
-          if (!isConsecutiveAccess(VL[i], VL[i - 1], *DL, *SE)) {
+          if (!isConsecutiveAccess(VL[i], VL[i - 1], *DL, *SE, DT)) {
             ReverseConsecutive = false;
             break;
           }
 
       BS.cancelScheduling(VL);
       newTreeEntry(VL, false);
 
       if (ReverseConsecutive) {
case Instruction::GetElementPtr: {
 
         buildTree_rec(Operands, Depth + 1);
       }
       return;
     }
     case Instruction::Store: {
       // Check if the stores are consecutive or of we need to swizzle them.
       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i)
-        if (!isConsecutiveAccess(VL[i], VL[i + 1], *DL, *SE)) {
+        if (!isConsecutiveAccess(VL[i], VL[i + 1], *DL, *SE, DT)) {
           BS.cancelScheduling(VL);
           newTreeEntry(VL, false);
           DEBUG(dbgs() << "SLP: Non-consecutive store.\n");
           return;
         }
 
       newTreeEntry(VL, true);
       DEBUG(dbgs() << "SLP: added a vector of stores.\n");
void BoUpSLP::reorderAltShuffleOperands(ArrayRef<Value *> VL,
 
   // Reorder if we have a commutative operation and consecutive access
   // are on either side of the alternate instructions.
   for (unsigned j = 0; j < VL.size() - 1; ++j) {
     if (LoadInst *L = dyn_cast<LoadInst>(Left[j])) {
       if (LoadInst *L1 = dyn_cast<LoadInst>(Right[j + 1])) {
         Instruction *VL1 = cast<Instruction>(VL[j]);
         Instruction *VL2 = cast<Instruction>(VL[j + 1]);
-        if (VL1->isCommutative() && isConsecutiveAccess(L, L1, *DL, *SE)) {
+        if (VL1->isCommutative() && isConsecutiveAccess(L, L1, *DL, *SE, DT)) {
           std::swap(Left[j], Right[j]);
           continue;
         } else if (VL2->isCommutative() &&
-                   isConsecutiveAccess(L, L1, *DL, *SE)) {
+                   isConsecutiveAccess(L, L1, *DL, *SE, DT)) {
           std::swap(Left[j + 1], Right[j + 1]);
           continue;
         }
         // else unchanged
       }
     }
     if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) {
       if (LoadInst *L1 = dyn_cast<LoadInst>(Left[j + 1])) {
         Instruction *VL1 = cast<Instruction>(VL[j]);
         Instruction *VL2 = cast<Instruction>(VL[j + 1]);
-        if (VL1->isCommutative() && isConsecutiveAccess(L, L1, *DL, *SE)) {
+        if (VL1->isCommutative() && isConsecutiveAccess(L, L1, *DL, *SE, DT)) {
           std::swap(Left[j], Right[j]);
           continue;
         } else if (VL2->isCommutative() &&
-                   isConsecutiveAccess(L, L1, *DL, *SE)) {
+                   isConsecutiveAccess(L, L1, *DL, *SE, DT)) {
           std::swap(Left[j + 1], Right[j + 1]);
           continue;
         }
         // else unchanged
       }
     }
   }
 }
void BoUpSLP::reorderInputsAccordingToOpcode(ArrayRef<Value *> VL,
   // such as-
   // add a[0],c[0]  load b[0]
   // add a[1],c[2]  load b[1]
   // b[2]           load b[2]
   // add a[3],c[3]  load b[3]
   for (unsigned j = 0; j < VL.size() - 1; ++j) {
     if (LoadInst *L = dyn_cast<LoadInst>(Left[j])) {
       if (LoadInst *L1 = dyn_cast<LoadInst>(Right[j + 1])) {
-        if (isConsecutiveAccess(L, L1, *DL, *SE)) {
+        if (isConsecutiveAccess(L, L1, *DL, *SE, DT)) {
           std::swap(Left[j + 1], Right[j + 1]);
           continue;
         }
       }
     }
     if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) {
       if (LoadInst *L1 = dyn_cast<LoadInst>(Left[j + 1])) {
-        if (isConsecutiveAccess(L, L1, *DL, *SE)) {
+        if (isConsecutiveAccess(L, L1, *DL, *SE, DT)) {
           std::swap(Left[j + 1], Right[j + 1]);
           continue;
         }
       }
     }
     // else unchanged
   }
 }
for (unsigned i = 0, e = Stores.size(); i < e; ++i) {
     // candidate create the best chance to find slp vectorization opportunity.
     unsigned j = 0;
     for (j = i + 1; j < e; ++j)
       IndexQueue.push_back(j);
     for (j = i; j > 0; --j)
       IndexQueue.push_back(j - 1);
 
     for (auto &k : IndexQueue) {
-      if (isConsecutiveAccess(Stores[i], Stores[k], *DL, *SE)) {
+      if (isConsecutiveAccess(Stores[i], Stores[k], *DL, *SE, DT)) {
         Tails.insert(Stores[k]);
         Heads.insert(Stores[i]);
         ConsecutiveChain[Stores[i]] = Stores[k];
         break;
       }
     }
   }
 

test/Transforms/SLPVectorizer/X86/consecutive-access.ll

 ; RUN: opt < %s -basicaa -slp-vectorizer -S | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.9.0"
 
 @A = common global [2000 x double] zeroinitializer, align 16
 @B = common global [2000 x double] zeroinitializer, align 16
 @C = common global [2000 x float] zeroinitializer, align 16
 @D = common global [2000 x float] zeroinitializer, align 16
 
 ; Currently SCEV isn't smart enough to figure out that accesses
-; A[3*i], A[3*i+1] and A[3*i+2] are consecutive, but in future
-; that would hopefully be fixed. For now, check that this isn't
-; vectorized.
+; A[3*i], A[3*i+1] and A[3*i+2] are consecutive, but llvm::isConsecutiveAccess
+; can catch this. Check that this is now vectorized.
 ; CHECK-LABEL: foo_3double
-; CHECK-NOT: x double>
+; CHECK: x double>
 ; Function Attrs: nounwind ssp uwtable
 define void @foo_3double(i32 %u) #0 {
 entry:
   %u.addr = alloca i32, align 4
   store i32 %u, i32* %u.addr, align 4
   %mul = mul nsw i32 %u, 3
   %idxprom = sext i32 %mul to i64
   %arrayidx = getelementptr inbounds [2000 x double], [2000 x double]* @A, i32 0, i64 %idxprom