Index: include/llvm/Analysis/LoopAccessAnalysis.h =================================================================== --- include/llvm/Analysis/LoopAccessAnalysis.h +++ include/llvm/Analysis/LoopAccessAnalysis.h @@ -697,8 +697,12 @@ /// are known to be constant. If that is the case, this returns true, and the /// sorted array is returned in \p Sorted. Otherwise, this returns false, and /// \p Sorted is invalid. +// If \p ShouldFindMask is true, this also returns the \p Mask which represent +// the actual memory access order. bool sortMemAccesses(ArrayRef VL, const DataLayout &DL, - ScalarEvolution &SE, SmallVectorImpl &Sorted); + ScalarEvolution &SE, SmallVectorImpl &Mask, + SmallVectorImpl &Sorted, + bool ShouldFindMask = 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. Index: lib/Analysis/LoopAccessAnalysis.cpp =================================================================== --- lib/Analysis/LoopAccessAnalysis.cpp +++ lib/Analysis/LoopAccessAnalysis.cpp @@ -1059,11 +1059,14 @@ } bool llvm::sortMemAccesses(ArrayRef VL, const DataLayout &DL, - ScalarEvolution &SE, - SmallVectorImpl &Sorted) { + ScalarEvolution &SE, SmallVectorImpl &Mask, + SmallVectorImpl &Sorted, + bool ShouldFindMask) { SmallVector, 4> OffValPairs; OffValPairs.reserve(VL.size()); Sorted.reserve(VL.size()); + if (ShouldFindMask) + Mask.reserve(VL.size()); // Walk over the pointers, and map each of them to an offset relative to // first pointer in the array. @@ -1092,14 +1095,29 @@ OffValPairs.emplace_back(Diff->getAPInt().getSExtValue(), Val); } - std::sort(OffValPairs.begin(), OffValPairs.end(), - [](const std::pair &Left, - const std::pair &Right) { - return Left.first < Right.first; + SmallVector UseOrder; + for (unsigned i = 0; i < VL.size(); i++) { + UseOrder.emplace_back(i); + if (ShouldFindMask) + Mask.emplace_back(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 (ShouldFindMask) + std::sort(Mask.begin(), Mask.end(), + [&UseOrder](unsigned Left, unsigned Right) { + return UseOrder[Left] < UseOrder[Right]; + }); return true; } Index: lib/Transforms/Vectorize/SLPVectorizer.cpp =================================================================== --- lib/Transforms/Vectorize/SLPVectorizer.cpp +++ lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -421,10 +421,8 @@ /// be vectorized to use the original vector (or aggregate "bitcast" to a vector). bool canReuseExtract(ArrayRef VL, unsigned Opcode) const; - /// Vectorize a single entry in the tree. VL icontains all isomorphic scalars - /// in order of its usage in a user program, for example ADD1, ADD2 and so on - /// or LOAD1 , LOAD2 etc. - Value *vectorizeTree(ArrayRef VL, TreeEntry *E); + /// 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 VL); @@ -464,8 +462,8 @@ SmallVectorImpl &Left, SmallVectorImpl &Right); struct TreeEntry { - TreeEntry() : Scalars(), VectorizedValue(nullptr), - NeedToGather(0), NeedToShuffle(0) {} + TreeEntry() + : Scalars(), VectorizedValue(nullptr), NeedToGather(0), ShuffleMask() {} /// \returns true if the scalars in VL are equal to this entry. bool isSame(ArrayRef VL) const { @@ -478,7 +476,8 @@ ScalarEvolution &SE) const { assert(VL.size() == Scalars.size() && "Invalid size"); SmallVector List; - if (!sortMemAccesses(VL, DL, SE, List)) + SmallVector Mask; + if (!sortMemAccesses(VL, DL, SE, Mask, List)) return false; return std::equal(List.begin(), List.end(), Scalars.begin()); @@ -493,19 +492,23 @@ /// Do we need to gather this sequence ? bool NeedToGather; - /// Do we need to shuffle the load ? - bool NeedToShuffle; + /// Records optional suffle mask for jumbled memory accesses in this. + SmallVector ShuffleMask; + }; /// Create a new VectorizableTree entry. TreeEntry *newTreeEntry(ArrayRef VL, bool Vectorized, - bool NeedToShuffle) { + ArrayRef ShuffleMask = None) { VectorizableTree.emplace_back(); int idx = VectorizableTree.size() - 1; TreeEntry *Last = &VectorizableTree[idx]; Last->Scalars.insert(Last->Scalars.begin(), VL.begin(), VL.end()); Last->NeedToGather = !Vectorized; - Last->NeedToShuffle = NeedToShuffle; + if (!ShuffleMask.empty()) + Last->ShuffleMask.insert(Last->ShuffleMask.begin(), ShuffleMask.begin(), + ShuffleMask.end()); + if (Vectorized) { for (int i = 0, e = VL.size(); i != e; ++i) { assert(!ScalarToTreeEntry.count(VL[i]) && "Scalar already in tree!"); @@ -1028,21 +1031,21 @@ if (Depth == RecursionMaxDepth) { DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n"); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } // Don't handle vectors. if (VL[0]->getType()->isVectorTy()) { DEBUG(dbgs() << "SLP: Gathering due to vector type.\n"); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } if (StoreInst *SI = dyn_cast(VL[0])) if (SI->getValueOperand()->getType()->isVectorTy()) { DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n"); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } unsigned Opcode = getSameOpcode(VL); @@ -1059,7 +1062,7 @@ // If all of the operands are identical or constant we have a simple solution. if (allConstant(VL) || isSplat(VL) || !allSameBlock(VL) || !Opcode) { DEBUG(dbgs() << "SLP: Gathering due to C,S,B,O. \n"); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } @@ -1071,7 +1074,7 @@ if (EphValues.count(VL[i])) { DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] << ") is ephemeral.\n"); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } } @@ -1084,7 +1087,7 @@ DEBUG(dbgs() << "SLP: \tChecking bundle: " << *VL[i] << ".\n"); if (E->Scalars[i] != VL[i]) { DEBUG(dbgs() << "SLP: Gathering due to partial overlap.\n"); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } } @@ -1097,7 +1100,7 @@ if (ScalarToTreeEntry.count(VL[i])) { DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] << ") is already in tree.\n"); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } } @@ -1107,7 +1110,7 @@ for (unsigned i = 0, e = VL.size(); i != e; ++i) { if (MustGather.count(VL[i])) { DEBUG(dbgs() << "SLP: Gathering due to gathered scalar.\n"); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } } @@ -1121,7 +1124,7 @@ // Don't go into unreachable blocks. They may contain instructions with // dependency cycles which confuse the final scheduling. DEBUG(dbgs() << "SLP: bundle in unreachable block.\n"); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } @@ -1130,7 +1133,7 @@ for (unsigned j = i+1; j < e; ++j) if (VL[i] == VL[j]) { DEBUG(dbgs() << "SLP: Scalar used twice in bundle.\n"); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } @@ -1145,7 +1148,7 @@ assert((!BS.getScheduleData(VL[0]) || !BS.getScheduleData(VL[0])->isPartOfBundle()) && "tryScheduleBundle should cancelScheduling on failure"); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n"); @@ -1162,12 +1165,12 @@ if (Term) { DEBUG(dbgs() << "SLP: Need to swizzle PHINodes (TerminatorInst use).\n"); BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } } - newTreeEntry(VL, true, false); + newTreeEntry(VL, true); DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n"); for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) { @@ -1189,7 +1192,7 @@ } else { BS.cancelScheduling(VL); } - newTreeEntry(VL, Reuse, false); + newTreeEntry(VL, Reuse); return; } case Instruction::Load: { @@ -1205,7 +1208,7 @@ if (DL->getTypeSizeInBits(ScalarTy) != DL->getTypeAllocSizeInBits(ScalarTy)) { BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); DEBUG(dbgs() << "SLP: Gathering loads of non-packed type.\n"); return; } @@ -1216,7 +1219,7 @@ LoadInst *L = cast(VL[i]); if (!L->isSimple()) { BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); DEBUG(dbgs() << "SLP: Gathering non-simple loads.\n"); return; } @@ -1236,7 +1239,7 @@ if (Consecutive) { ++NumLoadsWantToKeepOrder; - newTreeEntry(VL, true, false); + newTreeEntry(VL, true); DEBUG(dbgs() << "SLP: added a vector of loads.\n"); return; } @@ -1253,7 +1256,8 @@ if (VL.size() > 2 && !ReverseConsecutive) { bool ShuffledLoads = true; SmallVector Sorted; - if (sortMemAccesses(VL, *DL, *SE, Sorted)) { + SmallVector Mask; + if (sortMemAccesses(VL, *DL, *SE, Mask, Sorted, true)) { auto NewVL = makeArrayRef(Sorted.begin(), Sorted.end()); for (unsigned i = 0, e = NewVL.size() - 1; i < e; ++i) { if (!isConsecutiveAccess(NewVL[i], NewVL[i + 1], *DL, *SE)) { @@ -1262,14 +1266,14 @@ } } if (ShuffledLoads) { - newTreeEntry(NewVL, true, true); + newTreeEntry(NewVL, true, makeArrayRef(Mask.begin(), Mask.end())); return; } } } BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); if (ReverseConsecutive) { ++NumLoadsWantToChangeOrder; @@ -1296,12 +1300,12 @@ Type *Ty = cast(Val)->getOperand(0)->getType(); if (Ty != SrcTy || !isValidElementType(Ty)) { BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); DEBUG(dbgs() << "SLP: Gathering casts with different src types.\n"); return; } } - newTreeEntry(VL, true, false); + newTreeEntry(VL, true); DEBUG(dbgs() << "SLP: added a vector of casts.\n"); for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { @@ -1324,13 +1328,13 @@ if (Cmp->getPredicate() != P0 || Cmp->getOperand(0)->getType() != ComparedTy) { BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); DEBUG(dbgs() << "SLP: Gathering cmp with different predicate.\n"); return; } } - newTreeEntry(VL, true, false); + newTreeEntry(VL, true); DEBUG(dbgs() << "SLP: added a vector of compares.\n"); for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { @@ -1362,7 +1366,7 @@ case Instruction::And: case Instruction::Or: case Instruction::Xor: { - newTreeEntry(VL, true, false); + 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 @@ -1391,7 +1395,7 @@ if (cast(Val)->getNumOperands() != 2) { DEBUG(dbgs() << "SLP: not-vectorizable GEP (nested indexes).\n"); BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } } @@ -1404,7 +1408,7 @@ if (Ty0 != CurTy) { DEBUG(dbgs() << "SLP: not-vectorizable GEP (different types).\n"); BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } } @@ -1416,12 +1420,12 @@ DEBUG( dbgs() << "SLP: not-vectorizable GEP (non-constant indexes).\n"); BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); return; } } - newTreeEntry(VL, true, false); + newTreeEntry(VL, true); DEBUG(dbgs() << "SLP: added a vector of GEPs.\n"); for (unsigned i = 0, e = 2; i < e; ++i) { ValueList Operands; @@ -1438,12 +1442,12 @@ for (unsigned i = 0, e = VL.size() - 1; i < e; ++i) if (!isConsecutiveAccess(VL[i], VL[i + 1], *DL, *SE)) { BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); DEBUG(dbgs() << "SLP: Non-consecutive store.\n"); return; } - newTreeEntry(VL, true, false); + newTreeEntry(VL, true); DEBUG(dbgs() << "SLP: added a vector of stores.\n"); ValueList Operands; @@ -1461,7 +1465,7 @@ Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI); if (!isTriviallyVectorizable(ID)) { BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); DEBUG(dbgs() << "SLP: Non-vectorizable call.\n"); return; } @@ -1475,7 +1479,7 @@ getVectorIntrinsicIDForCall(CI2, TLI) != ID || !CI->hasIdenticalOperandBundleSchema(*CI2)) { BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); DEBUG(dbgs() << "SLP: mismatched calls:" << *CI << "!=" << *VL[i] << "\n"); return; @@ -1486,7 +1490,7 @@ Value *A1J = CI2->getArgOperand(1); if (A1I != A1J) { BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); DEBUG(dbgs() << "SLP: mismatched arguments in call:" << *CI << " argument "<< A1I<<"!=" << A1J << "\n"); @@ -1499,14 +1503,14 @@ CI->op_begin() + CI->getBundleOperandsEndIndex(), CI2->op_begin() + CI2->getBundleOperandsStartIndex())) { BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); DEBUG(dbgs() << "SLP: mismatched bundle operands in calls:" << *CI << "!=" << *VL[i] << '\n'); return; } } - newTreeEntry(VL, true, false); + newTreeEntry(VL, true); for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) { ValueList Operands; // Prepare the operand vector. @@ -1523,11 +1527,11 @@ // then do not vectorize this instruction. if (!isAltShuffle) { BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); DEBUG(dbgs() << "SLP: ShuffleVector are not vectorized.\n"); return; } - newTreeEntry(VL, true, false); + newTreeEntry(VL, true); DEBUG(dbgs() << "SLP: added a ShuffleVector op.\n"); // Reorder operands if reordering would enable vectorization. @@ -1551,7 +1555,7 @@ } default: BS.cancelScheduling(VL); - newTreeEntry(VL, false, false); + newTreeEntry(VL, false); DEBUG(dbgs() << "SLP: Gathering unknown instruction.\n"); return; } @@ -1790,7 +1794,7 @@ TTI->getMemoryOpCost(Instruction::Load, ScalarTy, alignment, 0); int VecLdCost = TTI->getMemoryOpCost(Instruction::Load, VecTy, alignment, 0); - if (E->NeedToShuffle) { + if (!E->ShuffleMask.empty()) { VecLdCost += TTI->getShuffleCost( TargetTransformInfo::SK_PermuteSingleSrc, VecTy, 0); } @@ -2356,8 +2360,9 @@ if (ScalarToTreeEntry.count(VL[0])) { int Idx = ScalarToTreeEntry[VL[0]]; TreeEntry *E = &VectorizableTree[Idx]; - if (E->isSame(VL) || (E->NeedToShuffle && E->isFoundJumbled(VL, *DL, *SE))) - return vectorizeTree(VL, E); + if (E->isSame(VL) || + (!E->ShuffleMask.empty() && E->isFoundJumbled(VL, *DL, *SE))) + return vectorizeTree(E); } Type *ScalarTy = VL[0]->getType(); @@ -2368,10 +2373,10 @@ return Gather(VL, VecTy); } -Value *BoUpSLP::vectorizeTree(ArrayRef VL, TreeEntry *E) { +Value *BoUpSLP::vectorizeTree(TreeEntry *E) { IRBuilder<>::InsertPointGuard Guard(Builder); - if (E->VectorizedValue && !E->NeedToShuffle) { + if (E->VectorizedValue && E->ShuffleMask.empty()) { DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n"); return E->VectorizedValue; } @@ -2609,27 +2614,18 @@ // As program order of scalar loads are jumbled, the vectorized 'load' // must be followed by a 'shuffle' with the required jumbled mask. - if (!VL.empty() && (E->NeedToShuffle)) { - assert(VL.size() == E->Scalars.size() && - "Equal number of scalars expected"); + if (!E->ShuffleMask.empty()) { SmallVector Mask; - for (Value *Val : VL) { - if (ScalarToTreeEntry.count(Val)) { - int Idx = ScalarToTreeEntry[Val]; - TreeEntry *E = &VectorizableTree[Idx]; - for (unsigned Lane = 0, LE = VL.size(); Lane != LE; ++Lane) { - if (E->Scalars[Lane] == Val) { - Mask.push_back(Builder.getInt32(Lane)); - break; - } - } - } + for (unsigned Lane = 0, LE = E->ShuffleMask.size(); Lane != LE; + ++Lane) { + Mask.push_back(Builder.getInt32(E->ShuffleMask[Lane])); } - // Generate shuffle for jumbled memory access Value *Undef = UndefValue::get(VecTy); Value *Shuf = Builder.CreateShuffleVector((Value *)LI, Undef, ConstantVector::get(Mask)); + E->VectorizedValue = Shuf; + ++NumVectorInstructions; return Shuf; } @@ -2814,7 +2810,7 @@ } Builder.SetInsertPoint(&F->getEntryBlock().front()); - auto *VectorRoot = vectorizeTree(ArrayRef(), &VectorizableTree[0]); + auto *VectorRoot = vectorizeTree(&VectorizableTree[0]); // If the vectorized tree can be rewritten in a smaller type, we truncate the // vectorized root. InstCombine will then rewrite the entire expression. We Index: test/Transforms/SLPVectorizer/X86/jumbled-load-bug.ll =================================================================== --- /dev/null +++ test/Transforms/SLPVectorizer/X86/jumbled-load-bug.ll @@ -0,0 +1,44 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -S -slp-vectorizer | FileCheck %s + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define <4 x i32> @zot() #0 { +; CHECK-LABEL: @zot( +; CHECK-NEXT: bb: +; CHECK-NEXT: [[P0:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 0 +; CHECK-NEXT: [[P1:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 1 +; CHECK-NEXT: [[P2:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 2 +; CHECK-NEXT: [[P3:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 3 +; CHECK-NEXT: [[TMP0:%.*]] = bitcast i8* [[P0]] to <4 x i8>* +; CHECK-NEXT: [[TMP1:%.*]] = load <4 x i8>, <4 x i8>* [[TMP0]], align 1 +; CHECK-NEXT: [[TMP2:%.*]] = shufflevector <4 x i8> [[TMP1]], <4 x i8> undef, <4 x i32> +; CHECK-NEXT: [[TMP3:%.*]] = extractelement <4 x i8> [[TMP2]], i32 0 +; CHECK-NEXT: [[I0:%.*]] = insertelement <4 x i8> undef, i8 [[TMP3]], i32 0 +; CHECK-NEXT: [[TMP4:%.*]] = extractelement <4 x i8> [[TMP2]], i32 1 +; CHECK-NEXT: [[I1:%.*]] = insertelement <4 x i8> [[I0]], i8 [[TMP4]], i32 1 +; CHECK-NEXT: [[TMP5:%.*]] = extractelement <4 x i8> [[TMP2]], i32 2 +; CHECK-NEXT: [[I2:%.*]] = insertelement <4 x i8> [[I1]], i8 [[TMP5]], i32 2 +; CHECK-NEXT: [[TMP6:%.*]] = extractelement <4 x i8> [[TMP2]], i32 3 +; CHECK-NEXT: [[I3:%.*]] = insertelement <4 x i8> [[I2]], i8 [[TMP6]], i32 3 +; CHECK-NEXT: [[RET:%.*]] = zext <4 x i8> [[I3]] to <4 x i32> +; CHECK-NEXT: ret <4 x i32> [[RET]] +; +bb: + %p0 = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 0 + %p1 = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 1 + %p2 = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 2 + %p3 = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 3 + %v3 = load i8, i8* %p3, align 1 + %v2 = load i8, i8* %p2, align 1 + %v0 = load i8, i8* %p0, align 1 + %v1 = load i8, i8* %p1, align 1 + %i0 = insertelement <4 x i8> undef, i8 %v1, i32 0 + %i1 = insertelement <4 x i8> %i0, i8 %v0, i32 1 + %i2 = insertelement <4 x i8> %i1, i8 %v2, i32 2 + %i3 = insertelement <4 x i8> %i2, i8 %v3, i32 3 + %ret = zext <4 x i8> %i3 to <4 x i32> + ret <4 x i32> %ret +} +