- // Check for an unsafe use of the PHI node.
- if (Instruction *UnsafeI = hasUnsafePHIOrSelectUse(&SI, SelectInfo.first))
- return PI.setAborted(UnsafeI);
-
- insertUse(SI, Offset, SelectInfo.first);
- }
-
- /// \brief Disable SROA entirely if there are unhandled users of the alloca.
- void visitInstruction(Instruction &I) {
- PI.setAborted(&I);
- }
-};
-
-/// \brief Use adder for the alloca partitioning.
-///
-/// This class adds the uses of an alloca to all of the partitions which they
-/// use. For splittable partitions, this can end up doing essentially a linear
-/// walk of the partitions, but the number of steps remains bounded by the
-/// total result instruction size:
-/// - The number of partitions is a result of the number unsplittable
-/// instructions using the alloca.
-/// - The number of users of each partition is at worst the total number of
-/// splittable instructions using the alloca.
-/// Thus we will produce N * M instructions in the end, where N are the number
-/// of unsplittable uses and M are the number of splittable. This visitor does
-/// the exact same number of updates to the partitioning.
-///
-/// In the more common case, this visitor will leverage the fact that the
-/// partition space is pre-sorted, and do a logarithmic search for the
-/// partition needed, making the total visit a classical ((N + M) * log(N))
-/// complexity operation.
-class AllocaPartitioning::UseBuilder : public PtrUseVisitor<UseBuilder> {
- friend class PtrUseVisitor<UseBuilder>;
- friend class InstVisitor<UseBuilder>;
- typedef PtrUseVisitor<UseBuilder> Base;
-
- const uint64_t AllocSize;
- AllocaPartitioning &P;
-
- /// \brief Set to de-duplicate dead instructions found in the use walk.
- SmallPtrSet<Instruction *, 4> VisitedDeadInsts;
-
-public:
- UseBuilder(const DataLayout &TD, AllocaInst &AI, AllocaPartitioning &P)
- : PtrUseVisitor<UseBuilder>(TD),
- AllocSize(TD.getTypeAllocSize(AI.getAllocatedType())),
- P(P) {}
-
-private:
- void markAsDead(Instruction &I) {
- if (VisitedDeadInsts.insert(&I))
- P.DeadUsers.push_back(&I);
- }
-
- void insertUse(Instruction &User, const APInt &Offset, uint64_t Size) {
- // If the use has a zero size or extends outside of the allocation, record
- // it as a dead use for elimination later.
- if (Size == 0 || Offset.isNegative() || Offset.uge(AllocSize))
- return markAsDead(User);
-
- uint64_t BeginOffset = Offset.getZExtValue();
- uint64_t EndOffset = BeginOffset + Size;
-
- // Clamp the end offset to the end of the allocation. Note that this is
- // formulated to handle even the case where "BeginOffset + Size" overflows.
- assert(AllocSize >= BeginOffset); // Established above.
- if (Size > AllocSize - BeginOffset)
- EndOffset = AllocSize;
-
- // NB: This only works if we have zero overlapping partitions.
- iterator B = std::lower_bound(P.begin(), P.end(), BeginOffset);
- if (B != P.begin() && llvm::prior(B)->EndOffset > BeginOffset)
- B = llvm::prior(B);
- for (iterator I = B, E = P.end(); I != E && I->BeginOffset < EndOffset;
- ++I) {
- PartitionUse NewPU(std::max(I->BeginOffset, BeginOffset),
- std::min(I->EndOffset, EndOffset), U);
- P.use_push_back(I, NewPU);
- if (isa<PHINode>(U->getUser()) || isa<SelectInst>(U->getUser()))
- P.PHIOrSelectOpMap[U]
- = std::make_pair(I - P.begin(), P.Uses[I - P.begin()].size() - 1);
- }
- }
-
- void handleLoadOrStore(Type *Ty, Instruction &I, const APInt &Offset) {
- uint64_t Size = DL.getTypeStoreSize(Ty);
-
- // If this memory access can be shown to *statically* extend outside the
- // bounds of of the allocation, it's behavior is undefined, so simply
- // ignore it. Note that this is more strict than the generic clamping
- // behavior of insertUse.
- if (Offset.isNegative() || Size > AllocSize ||
- Offset.ugt(AllocSize - Size))
- return markAsDead(I);
-
- insertUse(I, Offset, Size);
- }
-
- void visitBitCastInst(BitCastInst &BC) {
- if (BC.use_empty())
- return markAsDead(BC);
-
- return Base::visitBitCastInst(BC);
- }
-
- void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
- if (GEPI.use_empty())
- return markAsDead(GEPI);
-
- return Base::visitGetElementPtrInst(GEPI);
- }
-
- void visitLoadInst(LoadInst &LI) {
- assert(IsOffsetKnown);
- handleLoadOrStore(LI.getType(), LI, Offset);
- }
-
- void visitStoreInst(StoreInst &SI) {
- assert(IsOffsetKnown);
- handleLoadOrStore(SI.getOperand(0)->getType(), SI, Offset);
- }
-
- void visitMemSetInst(MemSetInst &II) {
- ConstantInt *Length = dyn_cast<ConstantInt>(II.getLength());
- if ((Length && Length->getValue() == 0) ||
- (IsOffsetKnown && !Offset.isNegative() && Offset.uge(AllocSize)))
- return markAsDead(II);
-
- assert(IsOffsetKnown);
- insertUse(II, Offset, Length ? Length->getLimitedValue()
- : AllocSize - Offset.getLimitedValue());
- }
-
- void visitMemTransferInst(MemTransferInst &II) {
- ConstantInt *Length = dyn_cast<ConstantInt>(II.getLength());
- if ((Length && Length->getValue() == 0) ||
- (IsOffsetKnown && !Offset.isNegative() && Offset.uge(AllocSize)))
- return markAsDead(II);
-
- assert(IsOffsetKnown);
- uint64_t Size = Length ? Length->getLimitedValue()
- : AllocSize - Offset.getLimitedValue();
-
- MemTransferOffsets &Offsets = P.MemTransferInstData[&II];
- if (!II.isVolatile() && Offsets.DestEnd && Offsets.SourceEnd &&
- Offsets.DestBegin == Offsets.SourceBegin)
- return markAsDead(II); // Skip identity transfers without side-effects.
-
- insertUse(II, Offset, Size);
- }
-
- void visitIntrinsicInst(IntrinsicInst &II) {
- assert(IsOffsetKnown);
- assert(II.getIntrinsicID() == Intrinsic::lifetime_start ||
- II.getIntrinsicID() == Intrinsic::lifetime_end);
-
- ConstantInt *Length = cast<ConstantInt>(II.getArgOperand(0));
- insertUse(II, Offset, std::min(Length->getLimitedValue(),
- AllocSize - Offset.getLimitedValue()));
- }
-
- void insertPHIOrSelect(Instruction &User, const APInt &Offset) {
- uint64_t Size = P.PHIOrSelectSizes.lookup(&User).first;
-