Index: include/llvm/Analysis/LoopAccessAnalysis.h =================================================================== --- include/llvm/Analysis/LoopAccessAnalysis.h +++ include/llvm/Analysis/LoopAccessAnalysis.h @@ -690,6 +690,11 @@ const ValueToValueMap &StridesMap = ValueToValueMap(), bool Assume = false, bool ShouldCheckWrap = true); +/// \brief Returns the sorted memory accesses after sorting the jumbled memory +/// access. +SmallVector SortMemAccess(ArrayRef VL, const DataLayout &DL, + ScalarEvolution &SE); + /// \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. bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL, Index: lib/Analysis/LoopAccessAnalysis.cpp =================================================================== --- lib/Analysis/LoopAccessAnalysis.cpp +++ lib/Analysis/LoopAccessAnalysis.cpp @@ -1015,6 +1015,35 @@ return -1; } +/// Returns the sorted memory accesses after sorting it. +SmallVector llvm::SortMemAccess(ArrayRef VL, + const DataLayout &DL, + ScalarEvolution &SE) { + std::multimap offValPair; + for (unsigned i = 0; i < VL.size(); i++) { + Value *Ptr = getPointerOperand(VL[i]); + unsigned AS = getAddressSpaceOperand(VL[i]); + unsigned PtrBitWidth = DL.getPointerSizeInBits(AS); + Type *Ty = cast(Ptr->getType())->getElementType(); + APInt Size(PtrBitWidth, DL.getTypeStoreSize(Ty)); + APInt Offset(PtrBitWidth, 0); + Ptr = Ptr->stripAndAccumulateInBoundsConstantOffsets(DL, Offset); + const SCEV *OffsetSCEV = SE.getConstant(Offset); + const SCEVConstant *OffsetC = dyn_cast(OffsetSCEV); + const APInt &constOffset = OffsetC->getAPInt(); + offValPair.insert(std::make_pair(constOffset.getSExtValue(), VL[i])); + } + + SmallVector list; + ArrayRef newVL; + for (std::multimap::iterator it = offValPair.begin(), + e = offValPair.end(); + it != e; it++) { + list.push_back(it->second); + } + return list; +} + /// 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) { Index: lib/Transforms/Vectorize/SLPVectorizer.cpp =================================================================== --- lib/Transforms/Vectorize/SLPVectorizer.cpp +++ lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -411,7 +411,7 @@ bool canReuseExtract(ArrayRef VL, unsigned Opcode) const; /// Vectorize a single entry in the tree. - Value *vectorizeTree(TreeEntry *E); + Value *vectorizeTree(ArrayRef VL, TreeEntry *E); /// Vectorize a single entry in the tree, starting in \p VL. Value *vectorizeTree(ArrayRef VL); @@ -452,7 +452,7 @@ SmallVectorImpl &Right); struct TreeEntry { TreeEntry() : Scalars(), VectorizedValue(nullptr), - NeedToGather(0) {} + NeedToGather(0), NeedToShuffle(0) {} /// \returns true if the scalars in VL are equal to this entry. bool isSame(ArrayRef VL) const { @@ -460,6 +460,21 @@ return std::equal(VL.begin(), VL.end(), Scalars.begin()); } + /// \returns true if the scalars in VL are found in this entry. + bool isJumbled(ArrayRef VL) const { + assert(VL.size() == Scalars.size() && "Invalid size"); + for (unsigned i = 0; i < VL.size(); i++) { + bool Found = false; + for (unsigned j = 0; j < Scalars.size(); j++) { + if (Scalars[j] == VL[i]) + Found = true; + } + if (!Found) + return false; + } + return true; + } + /// A vector of scalars. ValueList Scalars; @@ -468,15 +483,19 @@ /// Do we need to gather this sequence ? bool NeedToGather; + + /// Do we need to shuffle the load ? + bool NeedToShuffle; }; /// Create a new VectorizableTree entry. - TreeEntry *newTreeEntry(ArrayRef VL, bool Vectorized) { + TreeEntry *newTreeEntry(ArrayRef VL, bool Vectorized, bool NeedToShuffle) { 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 (Vectorized) { for (int i = 0, e = VL.size(); i != e; ++i) { assert(!ScalarToTreeEntry.count(VL[i]) && "Scalar already in tree!"); @@ -980,21 +999,21 @@ if (Depth == RecursionMaxDepth) { DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n"); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); return; } // Don't handle vectors. if (VL[0]->getType()->isVectorTy()) { DEBUG(dbgs() << "SLP: Gathering due to vector type.\n"); - newTreeEntry(VL, false); + newTreeEntry(VL, false, 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); + newTreeEntry(VL, false, false); return; } unsigned Opcode = getSameOpcode(VL); @@ -1011,7 +1030,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); + newTreeEntry(VL, false, false); return; } @@ -1023,7 +1042,7 @@ if (EphValues.count(VL[i])) { DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] << ") is ephemeral.\n"); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); return; } } @@ -1036,7 +1055,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); + newTreeEntry(VL, false, false); return; } } @@ -1049,7 +1068,7 @@ if (ScalarToTreeEntry.count(VL[i])) { DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] << ") is already in tree.\n"); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); return; } } @@ -1059,7 +1078,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); + newTreeEntry(VL, false, false); return; } } @@ -1073,7 +1092,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); + newTreeEntry(VL, false, false); return; } @@ -1082,7 +1101,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); + newTreeEntry(VL, false, false); return; } @@ -1097,7 +1116,7 @@ assert((!BS.getScheduleData(VL[0]) || !BS.getScheduleData(VL[0])->isPartOfBundle()) && "tryScheduleBundle should cancelScheduling on failure"); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); return; } DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n"); @@ -1114,12 +1133,12 @@ if (Term) { DEBUG(dbgs() << "SLP: Need to swizzle PHINodes (TerminatorInst use).\n"); BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); return; } } - newTreeEntry(VL, true); + newTreeEntry(VL, true, false); DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n"); for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) { @@ -1141,7 +1160,7 @@ } else { BS.cancelScheduling(VL); } - newTreeEntry(VL, Reuse); + newTreeEntry(VL, Reuse, false); return; } case Instruction::Load: { @@ -1157,7 +1176,7 @@ if (DL->getTypeSizeInBits(ScalarTy) != DL->getTypeAllocSizeInBits(ScalarTy)) { BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); DEBUG(dbgs() << "SLP: Gathering loads of non-packed type.\n"); return; } @@ -1168,7 +1187,7 @@ LoadInst *L = cast(VL[i]); if (!L->isSimple()) { BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); DEBUG(dbgs() << "SLP: Gathering non-simple loads.\n"); return; } @@ -1190,11 +1209,29 @@ if (Consecutive) { ++NumLoadsWantToKeepOrder; - newTreeEntry(VL, true); + newTreeEntry(VL, true, false); DEBUG(dbgs() << "SLP: added a vector of loads.\n"); return; } + if (VL.size() > 2) { + SmallVector list; + auto newVL = (ArrayRef)0; + bool shuffledLoads = true; + + list = SortMemAccess(VL, *DL, *SE); + newVL = makeArrayRef(list.begin(), list.end()); + for (unsigned i = 0, e = newVL.size() - 1; i < e; ++i) { + if (!isConsecutiveAccess(newVL[i], newVL[i + 1], *DL, *SE)) { + shuffledLoads = false; + } + } + if (shuffledLoads) { + newTreeEntry(newVL, true, true); + return; + } + } + // If none of the load pairs were consecutive when checked in order, // check the reverse order. if (ReverseConsecutive) @@ -1205,7 +1242,7 @@ } BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); if (ReverseConsecutive) { ++NumLoadsWantToChangeOrder; @@ -1232,12 +1269,12 @@ Type *Ty = cast(VL[i])->getOperand(0)->getType(); if (Ty != SrcTy || !isValidElementType(Ty)) { BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); DEBUG(dbgs() << "SLP: Gathering casts with different src types.\n"); return; } } - newTreeEntry(VL, true); + newTreeEntry(VL, true, false); DEBUG(dbgs() << "SLP: added a vector of casts.\n"); for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { @@ -1260,13 +1297,13 @@ if (Cmp->getPredicate() != P0 || Cmp->getOperand(0)->getType() != ComparedTy) { BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); DEBUG(dbgs() << "SLP: Gathering cmp with different predicate.\n"); return; } } - newTreeEntry(VL, true); + newTreeEntry(VL, true, false); DEBUG(dbgs() << "SLP: added a vector of compares.\n"); for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { @@ -1298,7 +1335,7 @@ case Instruction::And: case Instruction::Or: case Instruction::Xor: { - newTreeEntry(VL, true); + newTreeEntry(VL, true, false); DEBUG(dbgs() << "SLP: added a vector of bin op.\n"); // Sort operands of the instructions so that each side is more likely to @@ -1327,7 +1364,7 @@ if (cast(VL[j])->getNumOperands() != 2) { DEBUG(dbgs() << "SLP: not-vectorizable GEP (nested indexes).\n"); BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); return; } } @@ -1340,7 +1377,7 @@ if (Ty0 != CurTy) { DEBUG(dbgs() << "SLP: not-vectorizable GEP (different types).\n"); BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); return; } } @@ -1352,12 +1389,12 @@ DEBUG( dbgs() << "SLP: not-vectorizable GEP (non-constant indexes).\n"); BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); return; } } - newTreeEntry(VL, true); + newTreeEntry(VL, true, false); DEBUG(dbgs() << "SLP: added a vector of GEPs.\n"); for (unsigned i = 0, e = 2; i < e; ++i) { ValueList Operands; @@ -1374,12 +1411,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); + newTreeEntry(VL, false, false); DEBUG(dbgs() << "SLP: Non-consecutive store.\n"); return; } - newTreeEntry(VL, true); + newTreeEntry(VL, true, false); DEBUG(dbgs() << "SLP: added a vector of stores.\n"); ValueList Operands; @@ -1397,7 +1434,7 @@ Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI); if (!isTriviallyVectorizable(ID)) { BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); DEBUG(dbgs() << "SLP: Non-vectorizable call.\n"); return; } @@ -1411,7 +1448,7 @@ getVectorIntrinsicIDForCall(CI2, TLI) != ID || !CI->hasIdenticalOperandBundleSchema(*CI2)) { BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); DEBUG(dbgs() << "SLP: mismatched calls:" << *CI << "!=" << *VL[i] << "\n"); return; @@ -1422,7 +1459,7 @@ Value *A1J = CI2->getArgOperand(1); if (A1I != A1J) { BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); DEBUG(dbgs() << "SLP: mismatched arguments in call:" << *CI << " argument "<< A1I<<"!=" << A1J << "\n"); @@ -1435,14 +1472,14 @@ CI->op_begin() + CI->getBundleOperandsEndIndex(), CI2->op_begin() + CI2->getBundleOperandsStartIndex())) { BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); DEBUG(dbgs() << "SLP: mismatched bundle operands in calls:" << *CI << "!=" << *VL[i] << '\n'); return; } } - newTreeEntry(VL, true); + newTreeEntry(VL, true, false); for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) { ValueList Operands; // Prepare the operand vector. @@ -1459,11 +1496,11 @@ // then do not vectorize this instruction. if (!isAltShuffle) { BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); DEBUG(dbgs() << "SLP: ShuffleVector are not vectorized.\n"); return; } - newTreeEntry(VL, true); + newTreeEntry(VL, true, false); DEBUG(dbgs() << "SLP: added a ShuffleVector op.\n"); // Reorder operands if reordering would enable vectorization. @@ -1487,7 +1524,7 @@ } default: BS.cancelScheduling(VL); - newTreeEntry(VL, false); + newTreeEntry(VL, false, false); DEBUG(dbgs() << "SLP: Gathering unknown instruction.\n"); return; } @@ -2280,8 +2317,8 @@ if (ScalarToTreeEntry.count(VL[0])) { int Idx = ScalarToTreeEntry[VL[0]]; TreeEntry *E = &VectorizableTree[Idx]; - if (E->isSame(VL)) - return vectorizeTree(E); + if (E->isSame(VL) || (E->NeedToShuffle && E->isJumbled(VL))) + return vectorizeTree(VL, E); } Type *ScalarTy = VL[0]->getType(); @@ -2292,10 +2329,10 @@ return Gather(VL, VecTy); } -Value *BoUpSLP::vectorizeTree(TreeEntry *E) { +Value *BoUpSLP::vectorizeTree(ArrayRef VL, TreeEntry *E) { IRBuilder<>::InsertPointGuard Guard(Builder); - if (E->VectorizedValue) { + if (E->VectorizedValue && !E->NeedToShuffle) { DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n"); return E->VectorizedValue; } @@ -2533,6 +2570,32 @@ LI->setAlignment(Alignment); E->VectorizedValue = LI; ++NumVectorInstructions; + + // As program order of scalar loads are jumbled, the vectorized 'load' + // must be followed by a 'shuffle' with the required jumbled mask. + if (E->NeedToShuffle && (VL.size() == E->Scalars.size())) { + SmallVector Mask; + for (unsigned i = 0; i < VecTy->getNumElements(); ++i) { + if (ScalarToTreeEntry.count(VL[i])) { + int Idx = ScalarToTreeEntry[VL[i]]; + TreeEntry *E = &VectorizableTree[Idx]; + for (unsigned Lane = 0, LE = VL.size(); Lane != LE; ++Lane) { + if (E->Scalars[Lane] == VL[i]) { + Mask.push_back(Builder.getInt32(Lane)); + break; + } + } + } + } + // Generate shuffle for jumbled memory access + Value *Undef = UndefValue::get(VecTy); + Value *shuf = Builder.CreateShuffleVector((Value *)LI, Undef, + ConstantVector::get(Mask)); + if (Instruction *I = dyn_cast(shuf)) + return propagateMetadata(I, VL); + return shuf; + } + return propagateMetadata(LI, E->Scalars); } case Instruction::Store: { @@ -2708,7 +2771,7 @@ } Builder.SetInsertPoint(&F->getEntryBlock().front()); - auto *VectorRoot = vectorizeTree(&VectorizableTree[0]); + auto *VectorRoot = vectorizeTree(nullptr, &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.ll =================================================================== --- /dev/null +++ test/Transforms/SLPVectorizer/X86/jumbled-load.ll @@ -0,0 +1,34 @@ +; RUN: opt < %s -basicaa -S -mtriple=x86_64-unknown -mattr=+avx -slp-vectorizer | FileCheck %s + + +; CHECK-LABEL: @jumbled-load +; CHECK: [[CAST:%.*]] = bitcast i32* %in.addr to <4 x i32>* +; CHECK: [[LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[CAST]], align 4 +; CHECK: [[SHUF:%.*]] = shufflevector <4 x i32> [[LOAD]], <4 x i32> undef, <4 x i32> +; CHECK: mul <4 x i32> , [[SHUF]] + +define i32 @jumbled-load(i32* noalias nocapture %in, i32* noalias nocapture %out) { + + %in.addr = getelementptr inbounds i32, i32* %in, i64 0 + %1 = load i32, i32* %in.addr, align 4 + %2 = getelementptr inbounds i32, i32* %in.addr, i64 3 + %3 = load i32, i32* %2, align 4 + %4 = getelementptr inbounds i32, i32* %in.addr, i64 1 + %5 = load i32, i32* %4, align 4 + %6 = getelementptr inbounds i32, i32* %in.addr, i64 2 + %7 = load i32, i32* %6, align 4 + %8 = mul i32 %5, 13 + %9 = mul i32 %3, 7 + %10 = mul i32 %7, 9 + %11 = mul i32 %1, 11 + %12 = getelementptr inbounds i32, i32* %out, i64 0 + store i32 %8, i32* %12, align 4 + %13 = getelementptr inbounds i32, i32* %out, i64 1 + store i32 %9, i32* %13, align 4 + %14 = getelementptr inbounds i32, i32* %out, i64 2 + store i32 %10, i32* %14, align 4 + %15 = getelementptr inbounds i32, i32* %out, i64 3 + store i32 %11, i32* %15, align 4 + + ret i32 undef +} Index: test/Transforms/SLPVectorizer/X86/reduction_loads.ll =================================================================== --- test/Transforms/SLPVectorizer/X86/reduction_loads.ll +++ test/Transforms/SLPVectorizer/X86/reduction_loads.ll @@ -3,7 +3,8 @@ ; CHECK-LABEL: @test ; CHECK: [[CAST:%.*]] = bitcast i32* %p to <8 x i32>* ; CHECK: [[LOAD:%.*]] = load <8 x i32>, <8 x i32>* [[CAST]], align 4 -; CHECK: mul <8 x i32> , [[LOAD]] +; CHECK: [[SHUF:%.*]] = shufflevector <8 x i32> [[LOAD]], <8 x i32> undef, <8 x i32> +; CHECK: mul <8 x i32> , [[SHUF]] define i32 @test(i32* nocapture readonly %p) { entry: