diff options
Diffstat (limited to 'lib/Transforms/Scalar/SROA.cpp')
| -rw-r--r-- | lib/Transforms/Scalar/SROA.cpp | 539 |
1 files changed, 306 insertions, 233 deletions
diff --git a/lib/Transforms/Scalar/SROA.cpp b/lib/Transforms/Scalar/SROA.cpp index 8c7f253..6135114 100644 --- a/lib/Transforms/Scalar/SROA.cpp +++ b/lib/Transforms/Scalar/SROA.cpp @@ -28,6 +28,7 @@ #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AssumptionTracker.h" #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/PtrUseVisitor.h" #include "llvm/Analysis/ValueTracking.h" @@ -224,36 +225,26 @@ public: /// \brief Support for iterating over the slices. /// @{ typedef SmallVectorImpl<Slice>::iterator iterator; + typedef iterator_range<iterator> range; iterator begin() { return Slices.begin(); } iterator end() { return Slices.end(); } typedef SmallVectorImpl<Slice>::const_iterator const_iterator; + typedef iterator_range<const_iterator> const_range; const_iterator begin() const { return Slices.begin(); } const_iterator end() const { return Slices.end(); } /// @} - /// \brief Allow iterating the dead users for this alloca. - /// - /// These are instructions which will never actually use the alloca as they - /// are outside the allocated range. They are safe to replace with undef and - /// delete. - /// @{ - typedef SmallVectorImpl<Instruction *>::const_iterator dead_user_iterator; - dead_user_iterator dead_user_begin() const { return DeadUsers.begin(); } - dead_user_iterator dead_user_end() const { return DeadUsers.end(); } - /// @} + /// \brief Access the dead users for this alloca. + ArrayRef<Instruction *> getDeadUsers() const { return DeadUsers; } - /// \brief Allow iterating the dead expressions referring to this alloca. + /// \brief Access the dead operands referring to this alloca. /// /// These are operands which have cannot actually be used to refer to the /// alloca as they are outside its range and the user doesn't correct for /// that. These mostly consist of PHI node inputs and the like which we just /// need to replace with undef. - /// @{ - typedef SmallVectorImpl<Use *>::const_iterator dead_op_iterator; - dead_op_iterator dead_op_begin() const { return DeadOperands.begin(); } - dead_op_iterator dead_op_end() const { return DeadOperands.end(); } - /// @} + ArrayRef<Use *> getDeadOperands() const { return DeadOperands; } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void print(raw_ostream &OS, const_iterator I, StringRef Indent = " ") const; @@ -324,6 +315,15 @@ static Value *foldSelectInst(SelectInst &SI) { return nullptr; } +/// \brief A helper that folds a PHI node or a select. +static Value *foldPHINodeOrSelectInst(Instruction &I) { + if (PHINode *PN = dyn_cast<PHINode>(&I)) { + // If PN merges together the same value, return that value. + return PN->hasConstantValue(); + } + return foldSelectInst(cast<SelectInst>(I)); +} + /// \brief Builder for the alloca slices. /// /// This class builds a set of alloca slices by recursively visiting the uses @@ -334,7 +334,7 @@ class AllocaSlices::SliceBuilder : public PtrUseVisitor<SliceBuilder> { typedef PtrUseVisitor<SliceBuilder> Base; const uint64_t AllocSize; - AllocaSlices &S; + AllocaSlices &AS; SmallDenseMap<Instruction *, unsigned> MemTransferSliceMap; SmallDenseMap<Instruction *, uint64_t> PHIOrSelectSizes; @@ -343,14 +343,14 @@ class AllocaSlices::SliceBuilder : public PtrUseVisitor<SliceBuilder> { SmallPtrSet<Instruction *, 4> VisitedDeadInsts; public: - SliceBuilder(const DataLayout &DL, AllocaInst &AI, AllocaSlices &S) + SliceBuilder(const DataLayout &DL, AllocaInst &AI, AllocaSlices &AS) : PtrUseVisitor<SliceBuilder>(DL), - AllocSize(DL.getTypeAllocSize(AI.getAllocatedType())), S(S) {} + AllocSize(DL.getTypeAllocSize(AI.getAllocatedType())), AS(AS) {} private: void markAsDead(Instruction &I) { - if (VisitedDeadInsts.insert(&I)) - S.DeadUsers.push_back(&I); + if (VisitedDeadInsts.insert(&I).second) + AS.DeadUsers.push_back(&I); } void insertUse(Instruction &I, const APInt &Offset, uint64_t Size, @@ -361,7 +361,7 @@ private: DEBUG(dbgs() << "WARNING: Ignoring " << Size << " byte use @" << Offset << " which has zero size or starts outside of the " << AllocSize << " byte alloca:\n" - << " alloca: " << S.AI << "\n" + << " alloca: " << AS.AI << "\n" << " use: " << I << "\n"); return markAsDead(I); } @@ -379,12 +379,12 @@ private: if (Size > AllocSize - BeginOffset) { DEBUG(dbgs() << "WARNING: Clamping a " << Size << " byte use @" << Offset << " to remain within the " << AllocSize << " byte alloca:\n" - << " alloca: " << S.AI << "\n" + << " alloca: " << AS.AI << "\n" << " use: " << I << "\n"); EndOffset = AllocSize; } - S.Slices.push_back(Slice(BeginOffset, EndOffset, U, IsSplittable)); + AS.Slices.push_back(Slice(BeginOffset, EndOffset, U, IsSplittable)); } void visitBitCastInst(BitCastInst &BC) { @@ -485,7 +485,7 @@ private: DEBUG(dbgs() << "WARNING: Ignoring " << Size << " byte store @" << Offset << " which extends past the end of the " << AllocSize << " byte alloca:\n" - << " alloca: " << S.AI << "\n" + << " alloca: " << AS.AI << "\n" << " use: " << SI << "\n"); return markAsDead(SI); } @@ -535,7 +535,7 @@ private: if (Offset.uge(AllocSize)) { SmallDenseMap<Instruction *, unsigned>::iterator MTPI = MemTransferSliceMap.find(&II); if (MTPI != MemTransferSliceMap.end()) - S.Slices[MTPI->second].kill(); + AS.Slices[MTPI->second].kill(); return markAsDead(II); } @@ -558,10 +558,10 @@ private: bool Inserted; SmallDenseMap<Instruction *, unsigned>::iterator MTPI; std::tie(MTPI, Inserted) = - MemTransferSliceMap.insert(std::make_pair(&II, S.Slices.size())); + MemTransferSliceMap.insert(std::make_pair(&II, AS.Slices.size())); unsigned PrevIdx = MTPI->second; if (!Inserted) { - Slice &PrevP = S.Slices[PrevIdx]; + Slice &PrevP = AS.Slices[PrevIdx]; // Check if the begin offsets match and this is a non-volatile transfer. // In that case, we can completely elide the transfer. @@ -579,7 +579,7 @@ private: insertUse(II, Offset, Size, /*IsSplittable=*/Inserted && Length); // Check that we ended up with a valid index in the map. - assert(S.Slices[PrevIdx].getUse()->getUser() == &II && + assert(AS.Slices[PrevIdx].getUse()->getUser() == &II && "Map index doesn't point back to a slice with this user."); } @@ -639,64 +639,47 @@ private: } for (User *U : I->users()) - if (Visited.insert(cast<Instruction>(U))) + if (Visited.insert(cast<Instruction>(U)).second) Uses.push_back(std::make_pair(I, cast<Instruction>(U))); } while (!Uses.empty()); return nullptr; } - void visitPHINode(PHINode &PN) { - if (PN.use_empty()) - return markAsDead(PN); - if (!IsOffsetKnown) - return PI.setAborted(&PN); - - // See if we already have computed info on this node. - uint64_t &PHISize = PHIOrSelectSizes[&PN]; - if (!PHISize) { - // This is a new PHI node, check for an unsafe use of the PHI node. - if (Instruction *UnsafeI = hasUnsafePHIOrSelectUse(&PN, PHISize)) - return PI.setAborted(UnsafeI); - } - - // For PHI and select operands outside the alloca, we can't nuke the entire - // phi or select -- the other side might still be relevant, so we special - // case them here and use a separate structure to track the operands - // themselves which should be replaced with undef. - // FIXME: This should instead be escaped in the event we're instrumenting - // for address sanitization. - if (Offset.uge(AllocSize)) { - S.DeadOperands.push_back(U); - return; - } - - insertUse(PN, Offset, PHISize); - } + void visitPHINodeOrSelectInst(Instruction &I) { + assert(isa<PHINode>(I) || isa<SelectInst>(I)); + if (I.use_empty()) + return markAsDead(I); - void visitSelectInst(SelectInst &SI) { - if (SI.use_empty()) - return markAsDead(SI); - if (Value *Result = foldSelectInst(SI)) { + // TODO: We could use SimplifyInstruction here to fold PHINodes and + // SelectInsts. However, doing so requires to change the current + // dead-operand-tracking mechanism. For instance, suppose neither loading + // from %U nor %other traps. Then "load (select undef, %U, %other)" does not + // trap either. However, if we simply replace %U with undef using the + // current dead-operand-tracking mechanism, "load (select undef, undef, + // %other)" may trap because the select may return the first operand + // "undef". + if (Value *Result = foldPHINodeOrSelectInst(I)) { if (Result == *U) // If the result of the constant fold will be the pointer, recurse - // through the select as if we had RAUW'ed it. - enqueueUsers(SI); + // through the PHI/select as if we had RAUW'ed it. + enqueueUsers(I); else - // Otherwise the operand to the select is dead, and we can replace it - // with undef. - S.DeadOperands.push_back(U); + // Otherwise the operand to the PHI/select is dead, and we can replace + // it with undef. + AS.DeadOperands.push_back(U); return; } + if (!IsOffsetKnown) - return PI.setAborted(&SI); + return PI.setAborted(&I); // See if we already have computed info on this node. - uint64_t &SelectSize = PHIOrSelectSizes[&SI]; - if (!SelectSize) { - // This is a new Select, check for an unsafe use of it. - if (Instruction *UnsafeI = hasUnsafePHIOrSelectUse(&SI, SelectSize)) + uint64_t &Size = PHIOrSelectSizes[&I]; + if (!Size) { + // This is a new PHI/Select, check for an unsafe use of it. + if (Instruction *UnsafeI = hasUnsafePHIOrSelectUse(&I, Size)) return PI.setAborted(UnsafeI); } @@ -707,11 +690,19 @@ private: // FIXME: This should instead be escaped in the event we're instrumenting // for address sanitization. if (Offset.uge(AllocSize)) { - S.DeadOperands.push_back(U); + AS.DeadOperands.push_back(U); return; } - insertUse(SI, Offset, SelectSize); + insertUse(I, Offset, Size); + } + + void visitPHINode(PHINode &PN) { + visitPHINodeOrSelectInst(PN); + } + + void visitSelectInst(SelectInst &SI) { + visitPHINodeOrSelectInst(SI); } /// \brief Disable SROA entirely if there are unhandled users of the alloca. @@ -857,23 +848,18 @@ public: else return false; - } while (Visited.insert(Ptr)); + } while (Visited.insert(Ptr).second); return false; } void updateDebugInfo(Instruction *Inst) const override { - for (SmallVectorImpl<DbgDeclareInst *>::const_iterator I = DDIs.begin(), - E = DDIs.end(); I != E; ++I) { - DbgDeclareInst *DDI = *I; + for (DbgDeclareInst *DDI : DDIs) if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) ConvertDebugDeclareToDebugValue(DDI, SI, DIB); else if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) ConvertDebugDeclareToDebugValue(DDI, LI, DIB); - } - for (SmallVectorImpl<DbgValueInst *>::const_iterator I = DVIs.begin(), - E = DVIs.end(); I != E; ++I) { - DbgValueInst *DVI = *I; + for (DbgValueInst *DVI : DVIs) { Value *Arg = nullptr; if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { // If an argument is zero extended then use argument directly. The ZExt @@ -890,8 +876,8 @@ public: continue; } Instruction *DbgVal = - DIB.insertDbgValueIntrinsic(Arg, 0, DIVariable(DVI->getVariable()), - Inst); + DIB.insertDbgValueIntrinsic(Arg, 0, DIVariable(DVI->getVariable()), + DIExpression(DVI->getExpression()), Inst); DbgVal->setDebugLoc(DVI->getDebugLoc()); } } @@ -924,6 +910,7 @@ class SROA : public FunctionPass { LLVMContext *C; const DataLayout *DL; DominatorTree *DT; + AssumptionTracker *AT; /// \brief Worklist of alloca instructions to simplify. /// @@ -983,14 +970,14 @@ private: friend class PHIOrSelectSpeculator; friend class AllocaSliceRewriter; - bool rewritePartition(AllocaInst &AI, AllocaSlices &S, + bool rewritePartition(AllocaInst &AI, AllocaSlices &AS, AllocaSlices::iterator B, AllocaSlices::iterator E, int64_t BeginOffset, int64_t EndOffset, ArrayRef<AllocaSlices::iterator> SplitUses); - bool splitAlloca(AllocaInst &AI, AllocaSlices &S); + bool splitAlloca(AllocaInst &AI, AllocaSlices &AS); bool runOnAlloca(AllocaInst &AI); void clobberUse(Use &U); - void deleteDeadInstructions(SmallPtrSet<AllocaInst *, 4> &DeletedAllocas); + void deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas); bool promoteAllocas(Function &F); }; } @@ -1003,6 +990,7 @@ FunctionPass *llvm::createSROAPass(bool RequiresDomTree) { INITIALIZE_PASS_BEGIN(SROA, "sroa", "Scalar Replacement Of Aggregates", false, false) +INITIALIZE_PASS_DEPENDENCY(AssumptionTracker) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_END(SROA, "sroa", "Scalar Replacement Of Aggregates", false, false) @@ -1148,10 +1136,12 @@ static void speculatePHINodeLoads(PHINode &PN) { PHINode *NewPN = PHIBuilder.CreatePHI(LoadTy, PN.getNumIncomingValues(), PN.getName() + ".sroa.speculated"); - // Get the TBAA tag and alignment to use from one of the loads. It doesn't + // Get the AA tags and alignment to use from one of the loads. It doesn't // matter which one we get and if any differ. LoadInst *SomeLoad = cast<LoadInst>(PN.user_back()); - MDNode *TBAATag = SomeLoad->getMetadata(LLVMContext::MD_tbaa); + + AAMDNodes AATags; + SomeLoad->getAAMetadata(AATags); unsigned Align = SomeLoad->getAlignment(); // Rewrite all loads of the PN to use the new PHI. @@ -1172,8 +1162,8 @@ static void speculatePHINodeLoads(PHINode &PN) { InVal, (PN.getName() + ".sroa.speculate.load." + Pred->getName())); ++NumLoadsSpeculated; Load->setAlignment(Align); - if (TBAATag) - Load->setMetadata(LLVMContext::MD_tbaa, TBAATag); + if (AATags) + Load->setAAMetadata(AATags); NewPN->addIncoming(Load, Pred); } @@ -1238,12 +1228,15 @@ static void speculateSelectInstLoads(SelectInst &SI) { IRB.CreateLoad(FV, LI->getName() + ".sroa.speculate.load.false"); NumLoadsSpeculated += 2; - // Transfer alignment and TBAA info if present. + // Transfer alignment and AA info if present. TL->setAlignment(LI->getAlignment()); FL->setAlignment(LI->getAlignment()); - if (MDNode *Tag = LI->getMetadata(LLVMContext::MD_tbaa)) { - TL->setMetadata(LLVMContext::MD_tbaa, Tag); - FL->setMetadata(LLVMContext::MD_tbaa, Tag); + + AAMDNodes Tags; + LI->getAAMetadata(Tags); + if (Tags) { + TL->setAAMetadata(Tags); + FL->setAAMetadata(Tags); } Value *V = IRB.CreateSelect(SI.getCondition(), TL, FL, @@ -1468,7 +1461,7 @@ static Value *getAdjustedPtr(IRBuilderTy &IRB, const DataLayout &DL, Value *Ptr, break; Offset += GEPOffset; Ptr = GEP->getPointerOperand(); - if (!Visited.insert(Ptr)) + if (!Visited.insert(Ptr).second) break; } @@ -1505,7 +1498,7 @@ static Value *getAdjustedPtr(IRBuilderTy &IRB, const DataLayout &DL, Value *Ptr, break; } assert(Ptr->getType()->isPointerTy() && "Unexpected operand type!"); - } while (Visited.insert(Ptr)); + } while (Visited.insert(Ptr).second); if (!OffsetPtr) { if (!Int8Ptr) { @@ -1621,39 +1614,43 @@ static Value *convertValue(const DataLayout &DL, IRBuilderTy &IRB, Value *V, /// /// This function is called to test each entry in a partioning which is slated /// for a single slice. -static bool isVectorPromotionViableForSlice( - const DataLayout &DL, AllocaSlices &S, uint64_t SliceBeginOffset, - uint64_t SliceEndOffset, VectorType *Ty, uint64_t ElementSize, - AllocaSlices::const_iterator I) { +static bool +isVectorPromotionViableForSlice(const DataLayout &DL, uint64_t SliceBeginOffset, + uint64_t SliceEndOffset, VectorType *Ty, + uint64_t ElementSize, const Slice &S) { // First validate the slice offsets. uint64_t BeginOffset = - std::max(I->beginOffset(), SliceBeginOffset) - SliceBeginOffset; + std::max(S.beginOffset(), SliceBeginOffset) - SliceBeginOffset; uint64_t BeginIndex = BeginOffset / ElementSize; if (BeginIndex * ElementSize != BeginOffset || BeginIndex >= Ty->getNumElements()) return false; uint64_t EndOffset = - std::min(I->endOffset(), SliceEndOffset) - SliceBeginOffset; + std::min(S.endOffset(), SliceEndOffset) - SliceBeginOffset; uint64_t EndIndex = EndOffset / ElementSize; if (EndIndex * ElementSize != EndOffset || EndIndex > Ty->getNumElements()) return false; assert(EndIndex > BeginIndex && "Empty vector!"); uint64_t NumElements = EndIndex - BeginIndex; - Type *SliceTy = - (NumElements == 1) ? Ty->getElementType() - : VectorType::get(Ty->getElementType(), NumElements); + Type *SliceTy = (NumElements == 1) + ? Ty->getElementType() + : VectorType::get(Ty->getElementType(), NumElements); Type *SplitIntTy = Type::getIntNTy(Ty->getContext(), NumElements * ElementSize * 8); - Use *U = I->getUse(); + Use *U = S.getUse(); if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U->getUser())) { if (MI->isVolatile()) return false; - if (!I->isSplittable()) + if (!S.isSplittable()) return false; // Skip any unsplittable intrinsics. + } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(U->getUser())) { + if (II->getIntrinsicID() != Intrinsic::lifetime_start && + II->getIntrinsicID() != Intrinsic::lifetime_end) + return false; } else if (U->get()->getType()->getPointerElementType()->isStructTy()) { // Disable vector promotion when there are loads or stores of an FCA. return false; @@ -1661,8 +1658,7 @@ static bool isVectorPromotionViableForSlice( if (LI->isVolatile()) return false; Type *LTy = LI->getType(); - if (SliceBeginOffset > I->beginOffset() || - SliceEndOffset < I->endOffset()) { + if (SliceBeginOffset > S.beginOffset() || SliceEndOffset < S.endOffset()) { assert(LTy->isIntegerTy()); LTy = SplitIntTy; } @@ -1672,8 +1668,7 @@ static bool isVectorPromotionViableForSlice( if (SI->isVolatile()) return false; Type *STy = SI->getValueOperand()->getType(); - if (SliceBeginOffset > I->beginOffset() || - SliceEndOffset < I->endOffset()) { + if (SliceBeginOffset > S.beginOffset() || SliceEndOffset < S.endOffset()) { assert(STy->isIntegerTy()); STy = SplitIntTy; } @@ -1695,39 +1690,113 @@ static bool isVectorPromotionViableForSlice( /// SSA value. We only can ensure this for a limited set of operations, and we /// don't want to do the rewrites unless we are confident that the result will /// be promotable, so we have an early test here. -static bool -isVectorPromotionViable(const DataLayout &DL, Type *AllocaTy, AllocaSlices &S, +static VectorType * +isVectorPromotionViable(const DataLayout &DL, Type *AllocaTy, uint64_t SliceBeginOffset, uint64_t SliceEndOffset, - AllocaSlices::const_iterator I, - AllocaSlices::const_iterator E, + AllocaSlices::const_range Slices, ArrayRef<AllocaSlices::iterator> SplitUses) { - VectorType *Ty = dyn_cast<VectorType>(AllocaTy); - if (!Ty) - return false; + // Collect the candidate types for vector-based promotion. Also track whether + // we have different element types. + SmallVector<VectorType *, 4> CandidateTys; + Type *CommonEltTy = nullptr; + bool HaveCommonEltTy = true; + auto CheckCandidateType = [&](Type *Ty) { + if (auto *VTy = dyn_cast<VectorType>(Ty)) { + CandidateTys.push_back(VTy); + if (!CommonEltTy) + CommonEltTy = VTy->getElementType(); + else if (CommonEltTy != VTy->getElementType()) + HaveCommonEltTy = false; + } + }; + CheckCandidateType(AllocaTy); + // Consider any loads or stores that are the exact size of the slice. + for (const auto &S : Slices) + if (S.beginOffset() == SliceBeginOffset && + S.endOffset() == SliceEndOffset) { + if (auto *LI = dyn_cast<LoadInst>(S.getUse()->getUser())) + CheckCandidateType(LI->getType()); + else if (auto *SI = dyn_cast<StoreInst>(S.getUse()->getUser())) + CheckCandidateType(SI->getValueOperand()->getType()); + } + + // If we didn't find a vector type, nothing to do here. + if (CandidateTys.empty()) + return nullptr; - uint64_t ElementSize = DL.getTypeSizeInBits(Ty->getScalarType()); + // Remove non-integer vector types if we had multiple common element types. + // FIXME: It'd be nice to replace them with integer vector types, but we can't + // do that until all the backends are known to produce good code for all + // integer vector types. + if (!HaveCommonEltTy) { + CandidateTys.erase(std::remove_if(CandidateTys.begin(), CandidateTys.end(), + [](VectorType *VTy) { + return !VTy->getElementType()->isIntegerTy(); + }), + CandidateTys.end()); + + // If there were no integer vector types, give up. + if (CandidateTys.empty()) + return nullptr; - // While the definition of LLVM vectors is bitpacked, we don't support sizes - // that aren't byte sized. - if (ElementSize % 8) - return false; - assert((DL.getTypeSizeInBits(Ty) % 8) == 0 && - "vector size not a multiple of element size?"); - ElementSize /= 8; + // Rank the remaining candidate vector types. This is easy because we know + // they're all integer vectors. We sort by ascending number of elements. + auto RankVectorTypes = [&DL](VectorType *RHSTy, VectorType *LHSTy) { + assert(DL.getTypeSizeInBits(RHSTy) == DL.getTypeSizeInBits(LHSTy) && + "Cannot have vector types of different sizes!"); + assert(RHSTy->getElementType()->isIntegerTy() && + "All non-integer types eliminated!"); + assert(LHSTy->getElementType()->isIntegerTy() && + "All non-integer types eliminated!"); + return RHSTy->getNumElements() < LHSTy->getNumElements(); + }; + std::sort(CandidateTys.begin(), CandidateTys.end(), RankVectorTypes); + CandidateTys.erase( + std::unique(CandidateTys.begin(), CandidateTys.end(), RankVectorTypes), + CandidateTys.end()); + } else { +// The only way to have the same element type in every vector type is to +// have the same vector type. Check that and remove all but one. +#ifndef NDEBUG + for (VectorType *VTy : CandidateTys) { + assert(VTy->getElementType() == CommonEltTy && + "Unaccounted for element type!"); + assert(VTy == CandidateTys[0] && + "Different vector types with the same element type!"); + } +#endif + CandidateTys.resize(1); + } - for (; I != E; ++I) - if (!isVectorPromotionViableForSlice(DL, S, SliceBeginOffset, - SliceEndOffset, Ty, ElementSize, I)) - return false; + // Try each vector type, and return the one which works. + auto CheckVectorTypeForPromotion = [&](VectorType *VTy) { + uint64_t ElementSize = DL.getTypeSizeInBits(VTy->getElementType()); - for (ArrayRef<AllocaSlices::iterator>::const_iterator SUI = SplitUses.begin(), - SUE = SplitUses.end(); - SUI != SUE; ++SUI) - if (!isVectorPromotionViableForSlice(DL, S, SliceBeginOffset, - SliceEndOffset, Ty, ElementSize, *SUI)) + // While the definition of LLVM vectors is bitpacked, we don't support sizes + // that aren't byte sized. + if (ElementSize % 8) return false; + assert((DL.getTypeSizeInBits(VTy) % 8) == 0 && + "vector size not a multiple of element size?"); + ElementSize /= 8; - return true; + for (const auto &S : Slices) + if (!isVectorPromotionViableForSlice(DL, SliceBeginOffset, SliceEndOffset, + VTy, ElementSize, S)) + return false; + + for (const auto &SI : SplitUses) + if (!isVectorPromotionViableForSlice(DL, SliceBeginOffset, SliceEndOffset, + VTy, ElementSize, *SI)) + return false; + + return true; + }; + for (VectorType *VTy : CandidateTys) + if (CheckVectorTypeForPromotion(VTy)) + return VTy; + + return nullptr; } /// \brief Test whether a slice of an alloca is valid for integer widening. @@ -1737,23 +1806,26 @@ isVectorPromotionViable(const DataLayout &DL, Type *AllocaTy, AllocaSlices &S, static bool isIntegerWideningViableForSlice(const DataLayout &DL, Type *AllocaTy, uint64_t AllocBeginOffset, - uint64_t Size, AllocaSlices &S, - AllocaSlices::const_iterator I, + uint64_t Size, + const Slice &S, bool &WholeAllocaOp) { - uint64_t RelBegin = I->beginOffset() - AllocBeginOffset; - uint64_t RelEnd = I->endOffset() - AllocBeginOffset; + uint64_t RelBegin = S.beginOffset() - AllocBeginOffset; + uint64_t RelEnd = S.endOffset() - AllocBeginOffset; // We can't reasonably handle cases where the load or store extends past // the end of the aloca's type and into its padding. if (RelEnd > Size) return false; - Use *U = I->getUse(); + Use *U = S.getUse(); if (LoadInst *LI = dyn_cast<LoadInst>(U->getUser())) { if (LI->isVolatile()) return false; - if (RelBegin == 0 && RelEnd == Size) + // Note that we don't count vector loads or stores as whole-alloca + // operations which enable integer widening because we would prefer to use + // vector widening instead. + if (!isa<VectorType>(LI->getType()) && RelBegin == 0 && RelEnd == Size) WholeAllocaOp = true; if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType())) { if (ITy->getBitWidth() < DL.getTypeStoreSizeInBits(ITy)) @@ -1768,7 +1840,10 @@ static bool isIntegerWideningViableForSlice(const DataLayout &DL, Type *ValueTy = SI->getValueOperand()->getType(); if (SI->isVolatile()) return false; - if (RelBegin == 0 && RelEnd == Size) + // Note that we don't count vector loads or stores as whole-alloca + // operations which enable integer widening because we would prefer to use + // vector widening instead. + if (!isa<VectorType>(ValueTy) && RelBegin == 0 && RelEnd == Size) WholeAllocaOp = true; if (IntegerType *ITy = dyn_cast<IntegerType>(ValueTy)) { if (ITy->getBitWidth() < DL.getTypeStoreSizeInBits(ITy)) @@ -1782,7 +1857,7 @@ static bool isIntegerWideningViableForSlice(const DataLayout &DL, } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U->getUser())) { if (MI->isVolatile() || !isa<Constant>(MI->getLength())) return false; - if (!I->isSplittable()) + if (!S.isSplittable()) return false; // Skip any unsplittable intrinsics. } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(U->getUser())) { if (II->getIntrinsicID() != Intrinsic::lifetime_start && @@ -1803,9 +1878,8 @@ static bool isIntegerWideningViableForSlice(const DataLayout &DL, /// promote the resulting alloca. static bool isIntegerWideningViable(const DataLayout &DL, Type *AllocaTy, - uint64_t AllocBeginOffset, AllocaSlices &S, - AllocaSlices::const_iterator I, - AllocaSlices::const_iterator E, + uint64_t AllocBeginOffset, + AllocaSlices::const_range Slices, ArrayRef<AllocaSlices::iterator> SplitUses) { uint64_t SizeInBits = DL.getTypeSizeInBits(AllocaTy); // Don't create integer types larger than the maximum bitwidth. @@ -1831,18 +1905,17 @@ isIntegerWideningViable(const DataLayout &DL, Type *AllocaTy, // promote due to some other unsplittable entry (which we may make splittable // later). However, if there are only splittable uses, go ahead and assume // that we cover the alloca. - bool WholeAllocaOp = (I != E) ? false : DL.isLegalInteger(SizeInBits); + bool WholeAllocaOp = + Slices.begin() != Slices.end() ? false : DL.isLegalInteger(SizeInBits); - for (; I != E; ++I) + for (const auto &S : Slices) if (!isIntegerWideningViableForSlice(DL, AllocaTy, AllocBeginOffset, Size, - S, I, WholeAllocaOp)) + S, WholeAllocaOp)) return false; - for (ArrayRef<AllocaSlices::iterator>::const_iterator SUI = SplitUses.begin(), - SUE = SplitUses.end(); - SUI != SUE; ++SUI) + for (const auto &SI : SplitUses) if (!isIntegerWideningViableForSlice(DL, AllocaTy, AllocBeginOffset, Size, - S, *SUI, WholeAllocaOp)) + *SI, WholeAllocaOp)) return false; return WholeAllocaOp; @@ -1991,12 +2064,18 @@ class AllocaSliceRewriter : public InstVisitor<AllocaSliceRewriter, bool> { typedef llvm::InstVisitor<AllocaSliceRewriter, bool> Base; const DataLayout &DL; - AllocaSlices &S; + AllocaSlices &AS; SROA &Pass; AllocaInst &OldAI, &NewAI; const uint64_t NewAllocaBeginOffset, NewAllocaEndOffset; Type *NewAllocaTy; + // This is a convenience and flag variable that will be null unless the new + // alloca's integer operations should be widened to this integer type due to + // passing isIntegerWideningViable above. If it is non-null, the desired + // integer type will be stored here for easy access during rewriting. + IntegerType *IntTy; + // If we are rewriting an alloca partition which can be written as pure // vector operations, we stash extra information here. When VecTy is // non-null, we have some strict guarantees about the rewritten alloca: @@ -2010,12 +2089,6 @@ class AllocaSliceRewriter : public InstVisitor<AllocaSliceRewriter, bool> { Type *ElementTy; uint64_t ElementSize; - // This is a convenience and flag variable that will be null unless the new - // alloca's integer operations should be widened to this integer type due to - // passing isIntegerWideningViable above. If it is non-null, the desired - // integer type will be stored here for easy access during rewriting. - IntegerType *IntTy; - // The original offset of the slice currently being rewritten relative to // the original alloca. uint64_t BeginOffset, EndOffset; @@ -2038,25 +2111,25 @@ class AllocaSliceRewriter : public InstVisitor<AllocaSliceRewriter, bool> { IRBuilderTy IRB; public: - AllocaSliceRewriter(const DataLayout &DL, AllocaSlices &S, SROA &Pass, + AllocaSliceRewriter(const DataLayout &DL, AllocaSlices &AS, SROA &Pass, AllocaInst &OldAI, AllocaInst &NewAI, uint64_t NewAllocaBeginOffset, - uint64_t NewAllocaEndOffset, bool IsVectorPromotable, - bool IsIntegerPromotable, + uint64_t NewAllocaEndOffset, bool IsIntegerPromotable, + VectorType *PromotableVecTy, SmallPtrSetImpl<PHINode *> &PHIUsers, SmallPtrSetImpl<SelectInst *> &SelectUsers) - : DL(DL), S(S), Pass(Pass), OldAI(OldAI), NewAI(NewAI), + : DL(DL), AS(AS), Pass(Pass), OldAI(OldAI), NewAI(NewAI), NewAllocaBeginOffset(NewAllocaBeginOffset), NewAllocaEndOffset(NewAllocaEndOffset), NewAllocaTy(NewAI.getAllocatedType()), - VecTy(IsVectorPromotable ? cast<VectorType>(NewAllocaTy) : nullptr), - ElementTy(VecTy ? VecTy->getElementType() : nullptr), - ElementSize(VecTy ? DL.getTypeSizeInBits(ElementTy) / 8 : 0), IntTy(IsIntegerPromotable ? Type::getIntNTy( NewAI.getContext(), DL.getTypeSizeInBits(NewAI.getAllocatedType())) : nullptr), + VecTy(PromotableVecTy), + ElementTy(VecTy ? VecTy->getElementType() : nullptr), + ElementSize(VecTy ? DL.getTypeSizeInBits(ElementTy) / 8 : 0), BeginOffset(), EndOffset(), IsSplittable(), IsSplit(), OldUse(), OldPtr(), PHIUsers(PHIUsers), SelectUsers(SelectUsers), IRB(NewAI.getContext(), ConstantFolder()) { @@ -2065,8 +2138,7 @@ public: "Only multiple-of-8 sized vector elements are viable"); ++NumVectorized; } - assert((!IsVectorPromotable && !IsIntegerPromotable) || - IsVectorPromotable != IsIntegerPromotable); + assert((!IntTy && !VecTy) || (IntTy && !VecTy) || (!IntTy && VecTy)); } bool visit(AllocaSlices::const_iterator I) { @@ -2413,6 +2485,7 @@ private: if (!VecTy && !IntTy && (BeginOffset > NewAllocaBeginOffset || EndOffset < NewAllocaEndOffset || + SliceSize != DL.getTypeStoreSize(AllocaTy) || !AllocaTy->isSingleValueType() || !DL.isLegalInteger(DL.getTypeSizeInBits(ScalarTy)) || DL.getTypeSizeInBits(ScalarTy)%8 != 0)) { @@ -2535,10 +2608,11 @@ private: // If this doesn't map cleanly onto the alloca type, and that type isn't // a single value type, just emit a memcpy. - bool EmitMemCpy - = !VecTy && !IntTy && (BeginOffset > NewAllocaBeginOffset || - EndOffset < NewAllocaEndOffset || - !NewAI.getAllocatedType()->isSingleValueType()); + bool EmitMemCpy = + !VecTy && !IntTy && + (BeginOffset > NewAllocaBeginOffset || EndOffset < NewAllocaEndOffset || + SliceSize != DL.getTypeStoreSize(NewAI.getAllocatedType()) || + !NewAI.getAllocatedType()->isSingleValueType()); // If we're just going to emit a memcpy, the alloca hasn't changed, and the // size hasn't been shrunk based on analysis of the viable range, this is @@ -2697,7 +2771,10 @@ private: // the old pointer, which necessarily must be in the right position to // dominate the PHI. IRBuilderTy PtrBuilder(IRB); - PtrBuilder.SetInsertPoint(OldPtr); + if (isa<PHINode>(OldPtr)) + PtrBuilder.SetInsertPoint(OldPtr->getParent()->getFirstInsertionPt()); + else + PtrBuilder.SetInsertPoint(OldPtr); PtrBuilder.SetCurrentDebugLocation(OldPtr->getDebugLoc()); Value *NewPtr = getNewAllocaSlicePtr(PtrBuilder, OldPtr->getType()); @@ -2784,7 +2861,7 @@ private: /// This uses a set to de-duplicate users. void enqueueUsers(Instruction &I) { for (Use &U : I.uses()) - if (Visited.insert(U.getUser())) + if (Visited.insert(U.getUser()).second) Queue.push_back(&U); } @@ -3104,7 +3181,7 @@ static Type *getTypePartition(const DataLayout &DL, Type *Ty, /// appropriate new offsets. It also evaluates how successful the rewrite was /// at enabling promotion and if it was successful queues the alloca to be /// promoted. -bool SROA::rewritePartition(AllocaInst &AI, AllocaSlices &S, +bool SROA::rewritePartition(AllocaInst &AI, AllocaSlices &AS, AllocaSlices::iterator B, AllocaSlices::iterator E, int64_t BeginOffset, int64_t EndOffset, ArrayRef<AllocaSlices::iterator> SplitUses) { @@ -3130,12 +3207,16 @@ bool SROA::rewritePartition(AllocaInst &AI, AllocaSlices &S, SliceTy = ArrayType::get(Type::getInt8Ty(*C), SliceSize); assert(DL->getTypeAllocSize(SliceTy) >= SliceSize); - bool IsVectorPromotable = isVectorPromotionViable( - *DL, SliceTy, S, BeginOffset, EndOffset, B, E, SplitUses); + bool IsIntegerPromotable = isIntegerWideningViable( + *DL, SliceTy, BeginOffset, AllocaSlices::const_range(B, E), SplitUses); - bool IsIntegerPromotable = - !IsVectorPromotable && - isIntegerWideningViable(*DL, SliceTy, BeginOffset, S, B, E, SplitUses); + VectorType *VecTy = + IsIntegerPromotable + ? nullptr + : isVectorPromotionViable(*DL, SliceTy, BeginOffset, EndOffset, + AllocaSlices::const_range(B, E), SplitUses); + if (VecTy) + SliceTy = VecTy; // Check for the case where we're going to rewrite to a new alloca of the // exact same type as the original, and with the same access offsets. In that @@ -3161,8 +3242,9 @@ bool SROA::rewritePartition(AllocaInst &AI, AllocaSlices &S, // the alloca's alignment unconstrained. if (Alignment <= DL->getABITypeAlignment(SliceTy)) Alignment = 0; - NewAI = new AllocaInst(SliceTy, nullptr, Alignment, - AI.getName() + ".sroa." + Twine(B - S.begin()), &AI); + NewAI = + new AllocaInst(SliceTy, nullptr, Alignment, + AI.getName() + ".sroa." + Twine(B - AS.begin()), &AI); ++NumNewAllocas; } @@ -3178,21 +3260,19 @@ bool SROA::rewritePartition(AllocaInst &AI, AllocaSlices &S, SmallPtrSet<PHINode *, 8> PHIUsers; SmallPtrSet<SelectInst *, 8> SelectUsers; - AllocaSliceRewriter Rewriter(*DL, S, *this, AI, *NewAI, BeginOffset, - EndOffset, IsVectorPromotable, - IsIntegerPromotable, PHIUsers, SelectUsers); + AllocaSliceRewriter Rewriter(*DL, AS, *this, AI, *NewAI, BeginOffset, + EndOffset, IsIntegerPromotable, VecTy, PHIUsers, + SelectUsers); bool Promotable = true; - for (ArrayRef<AllocaSlices::iterator>::const_iterator SUI = SplitUses.begin(), - SUE = SplitUses.end(); - SUI != SUE; ++SUI) { + for (auto & SplitUse : SplitUses) { DEBUG(dbgs() << " rewriting split "); - DEBUG(S.printSlice(dbgs(), *SUI, "")); - Promotable &= Rewriter.visit(*SUI); + DEBUG(AS.printSlice(dbgs(), SplitUse, "")); + Promotable &= Rewriter.visit(SplitUse); ++NumUses; } for (AllocaSlices::iterator I = B; I != E; ++I) { DEBUG(dbgs() << " rewriting "); - DEBUG(S.printSlice(dbgs(), I, "")); + DEBUG(AS.printSlice(dbgs(), I, "")); Promotable &= Rewriter.visit(I); ++NumUses; } @@ -3230,14 +3310,10 @@ bool SROA::rewritePartition(AllocaInst &AI, AllocaSlices &S, // If we have either PHIs or Selects to speculate, add them to those // worklists and re-queue the new alloca so that we promote in on the // next iteration. - for (SmallPtrSetImpl<PHINode *>::iterator I = PHIUsers.begin(), - E = PHIUsers.end(); - I != E; ++I) - SpeculatablePHIs.insert(*I); - for (SmallPtrSetImpl<SelectInst *>::iterator I = SelectUsers.begin(), - E = SelectUsers.end(); - I != E; ++I) - SpeculatableSelects.insert(*I); + for (PHINode *PHIUser : PHIUsers) + SpeculatablePHIs.insert(PHIUser); + for (SelectInst *SelectUser : SelectUsers) + SpeculatableSelects.insert(SelectUser); Worklist.insert(NewAI); } } else { @@ -3275,17 +3351,15 @@ removeFinishedSplitUses(SmallVectorImpl<AllocaSlices::iterator> &SplitUses, // Recompute the max. While this is linear, so is remove_if. MaxSplitUseEndOffset = 0; - for (SmallVectorImpl<AllocaSlices::iterator>::iterator - SUI = SplitUses.begin(), - SUE = SplitUses.end(); - SUI != SUE; ++SUI) - MaxSplitUseEndOffset = std::max((*SUI)->endOffset(), MaxSplitUseEndOffset); + for (AllocaSlices::iterator SplitUse : SplitUses) + MaxSplitUseEndOffset = + std::max(SplitUse->endOffset(), MaxSplitUseEndOffset); } /// \brief Walks the slices of an alloca and form partitions based on them, /// rewriting each of their uses. -bool SROA::splitAlloca(AllocaInst &AI, AllocaSlices &S) { - if (S.begin() == S.end()) +bool SROA::splitAlloca(AllocaInst &AI, AllocaSlices &AS) { + if (AS.begin() == AS.end()) return false; unsigned NumPartitions = 0; @@ -3293,9 +3367,10 @@ bool SROA::splitAlloca(AllocaInst &AI, AllocaSlices &S) { SmallVector<AllocaSlices::iterator, 4> SplitUses; uint64_t MaxSplitUseEndOffset = 0; - uint64_t BeginOffset = S.begin()->beginOffset(); + uint64_t BeginOffset = AS.begin()->beginOffset(); - for (AllocaSlices::iterator SI = S.begin(), SJ = std::next(SI), SE = S.end(); + for (AllocaSlices::iterator SI = AS.begin(), SJ = std::next(SI), + SE = AS.end(); SI != SE; SI = SJ) { uint64_t MaxEndOffset = SI->endOffset(); @@ -3333,8 +3408,8 @@ bool SROA::splitAlloca(AllocaInst &AI, AllocaSlices &S) { // we'll have to rewrite uses and erase old split uses. if (BeginOffset < MaxEndOffset) { // Rewrite a sequence of overlapping slices. - Changed |= - rewritePartition(AI, S, SI, SJ, BeginOffset, MaxEndOffset, SplitUses); + Changed |= rewritePartition(AI, AS, SI, SJ, BeginOffset, MaxEndOffset, + SplitUses); ++NumPartitions; removeFinishedSplitUses(SplitUses, MaxSplitUseEndOffset, MaxEndOffset); @@ -3373,8 +3448,8 @@ bool SROA::splitAlloca(AllocaInst &AI, AllocaSlices &S) { uint64_t PostSplitEndOffset = SJ == SE ? MaxSplitUseEndOffset : SJ->beginOffset(); - Changed |= rewritePartition(AI, S, SJ, SJ, MaxEndOffset, PostSplitEndOffset, - SplitUses); + Changed |= rewritePartition(AI, AS, SJ, SJ, MaxEndOffset, + PostSplitEndOffset, SplitUses); ++NumPartitions; if (SJ == SE) @@ -3437,38 +3512,34 @@ bool SROA::runOnAlloca(AllocaInst &AI) { Changed |= AggRewriter.rewrite(AI); // Build the slices using a recursive instruction-visiting builder. - AllocaSlices S(*DL, AI); - DEBUG(S.print(dbgs())); - if (S.isEscaped()) + AllocaSlices AS(*DL, AI); + DEBUG(AS.print(dbgs())); + if (AS.isEscaped()) return Changed; // Delete all the dead users of this alloca before splitting and rewriting it. - for (AllocaSlices::dead_user_iterator DI = S.dead_user_begin(), - DE = S.dead_user_end(); - DI != DE; ++DI) { + for (Instruction *DeadUser : AS.getDeadUsers()) { // Free up everything used by this instruction. - for (Use &DeadOp : (*DI)->operands()) + for (Use &DeadOp : DeadUser->operands()) clobberUse(DeadOp); // Now replace the uses of this instruction. - (*DI)->replaceAllUsesWith(UndefValue::get((*DI)->getType())); + DeadUser->replaceAllUsesWith(UndefValue::get(DeadUser->getType())); // And mark it for deletion. - DeadInsts.insert(*DI); + DeadInsts.insert(DeadUser); Changed = true; } - for (AllocaSlices::dead_op_iterator DO = S.dead_op_begin(), - DE = S.dead_op_end(); - DO != DE; ++DO) { - clobberUse(**DO); + for (Use *DeadOp : AS.getDeadOperands()) { + clobberUse(*DeadOp); Changed = true; } // No slices to split. Leave the dead alloca for a later pass to clean up. - if (S.begin() == S.end()) + if (AS.begin() == AS.end()) return Changed; - Changed |= splitAlloca(AI, S); + Changed |= splitAlloca(AI, AS); DEBUG(dbgs() << " Speculating PHIs\n"); while (!SpeculatablePHIs.empty()) @@ -3490,7 +3561,7 @@ bool SROA::runOnAlloca(AllocaInst &AI) { /// /// We also record the alloca instructions deleted here so that they aren't /// subsequently handed to mem2reg to promote. -void SROA::deleteDeadInstructions(SmallPtrSet<AllocaInst*, 4> &DeletedAllocas) { +void SROA::deleteDeadInstructions(SmallPtrSetImpl<AllocaInst*> &DeletedAllocas) { while (!DeadInsts.empty()) { Instruction *I = DeadInsts.pop_back_val(); DEBUG(dbgs() << "Deleting dead instruction: " << *I << "\n"); @@ -3515,9 +3586,9 @@ void SROA::deleteDeadInstructions(SmallPtrSet<AllocaInst*, 4> &DeletedAllocas) { static void enqueueUsersInWorklist(Instruction &I, SmallVectorImpl<Instruction *> &Worklist, - SmallPtrSet<Instruction *, 8> &Visited) { + SmallPtrSetImpl<Instruction *> &Visited) { for (User *U : I.users()) - if (Visited.insert(cast<Instruction>(U))) + if (Visited.insert(cast<Instruction>(U)).second) Worklist.push_back(cast<Instruction>(U)); } @@ -3537,7 +3608,7 @@ bool SROA::promoteAllocas(Function &F) { if (DT && !ForceSSAUpdater) { DEBUG(dbgs() << "Promoting allocas with mem2reg...\n"); - PromoteMemToReg(PromotableAllocas, *DT); + PromoteMemToReg(PromotableAllocas, *DT, nullptr, AT); PromotableAllocas.clear(); return true; } @@ -3619,6 +3690,7 @@ bool SROA::runOnFunction(Function &F) { DominatorTreeWrapperPass *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); DT = DTWP ? &DTWP->getDomTree() : nullptr; + AT = &getAnalysis<AssumptionTracker>(); BasicBlock &EntryBB = F.getEntryBlock(); for (BasicBlock::iterator I = EntryBB.begin(), E = std::prev(EntryBB.end()); @@ -3662,6 +3734,7 @@ bool SROA::runOnFunction(Function &F) { } void SROA::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired<AssumptionTracker>(); if (RequiresDomTree) AU.addRequired<DominatorTreeWrapperPass>(); AU.setPreservesCFG(); |