[SLP] Fixes the bug due to absence of in order uses of scalars which needs to be available

for VectorizeTree() API.This API uses it for proper mask computation to be used in shufflevector IR.
The fix is to compute the mask for out of order memory accesses while building the vectorizable tree
instead of actual vectorization of vectorizable tree.

Reviewers: mkuper

Differential Revision: https://reviews.llvm.org/D30159

Change-Id: Id1e287f073fa4959713ba545fa4254db5da8b40d
llvm-svn: 296575

1 files changed, 23 insertions, 8 deletions

diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index a3ed412b738..26470174a48 100644
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -1040,7 +1040,8 @@ static unsigned getAddressSpaceOperand(Value *I) {
 
 bool llvm::sortMemAccesses(ArrayRef<Value *> VL, const DataLayout &DL,
                            ScalarEvolution &SE,
-                           SmallVectorImpl<Value *> &Sorted) {
+                           SmallVectorImpl<Value *> &Sorted,
+                           SmallVectorImpl<unsigned> *Mask) {
   SmallVector<std::pair<int64_t, Value *>, 4> OffValPairs;
   OffValPairs.reserve(VL.size());
   Sorted.reserve(VL.size());
@@ -1050,7 +1051,6 @@ bool llvm::sortMemAccesses(ArrayRef<Value *> VL, const DataLayout &DL,
   Value *Ptr0 = getPointerOperand(VL[0]);
   const SCEV *Scev0 = SE.getSCEV(Ptr0);
   Value *Obj0 = GetUnderlyingObject(Ptr0, DL);
-
   for (auto *Val : VL) {
     // The only kind of access we care about here is load.
     if (!isa<LoadInst>(Val))
@@ -1077,14 +1077,29 @@ bool llvm::sortMemAccesses(ArrayRef<Value *> VL, const DataLayout &DL,
     OffValPairs.emplace_back(Diff->getAPInt().getSExtValue(), Val);
   }
 
-  std::sort(OffValPairs.begin(), OffValPairs.end(),
-            [](const std::pair<int64_t, Value *> &Left,
-               const std::pair<int64_t, Value *> &Right) {
-              return Left.first < Right.first;
+  SmallVector<unsigned, 4> UseOrder(VL.size());
+  for (unsigned i = 0; i < VL.size(); i++)
+    UseOrder[i] = i;
+
+  // Sort the memory accesses and keep the order of their uses in UseOrder.
+  std::sort(UseOrder.begin(), UseOrder.end(),
+            [&OffValPairs](unsigned Left, unsigned Right) {
+              return OffValPairs[Left].first < OffValPairs[Right].first;
             });
 
-  for (auto &it : OffValPairs)
-    Sorted.push_back(it.second);
+  for (unsigned i = 0; i < VL.size(); i++)
+    Sorted.emplace_back(OffValPairs[UseOrder[i]].second);
+
+  // Sort UseOrder to compute the Mask.
+  if (Mask) {
+    Mask->reserve(VL.size());
+    for (unsigned i = 0; i < VL.size(); i++)
+      Mask->emplace_back(i);
+    std::sort(Mask->begin(), Mask->end(),
+              [&UseOrder](unsigned Left, unsigned Right) {
+                return UseOrder[Left] < UseOrder[Right];
+              });
+  }
 
   return true;
 }