- return true;
- }
-
- return markAsEscaping(II);
- }
-
- Instruction *hasUnsafePHIOrSelectUse(Instruction *Root, uint64_t &Size) {
- // We consider any PHI or select that results in a direct load or store of
- // the same offset to be a viable use for partitioning purposes. These uses
- // are considered unsplittable and the size is the maximum loaded or stored
- // size.
- SmallPtrSet<Instruction *, 4> Visited;
- SmallVector<std::pair<Instruction *, Instruction *>, 4> Uses;
- Visited.insert(Root);
- Uses.push_back(std::make_pair(cast<Instruction>(*U), Root));
- // If there are no loads or stores, the access is dead. We mark that as
- // a size zero access.
- Size = 0;
- do {
- Instruction *I, *UsedI;
- llvm::tie(UsedI, I) = Uses.pop_back_val();
-
- if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
- Size = std::max(Size, TD.getTypeStoreSize(LI->getType()));
- continue;
- }
- if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
- Value *Op = SI->getOperand(0);
- if (Op == UsedI)
- return SI;
- Size = std::max(Size, TD.getTypeStoreSize(Op->getType()));
- continue;
- }
-
- if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
- if (!GEP->hasAllZeroIndices())
- return GEP;
- } else if (!isa<BitCastInst>(I) && !isa<PHINode>(I) &&
- !isa<SelectInst>(I)) {
- return I;
- }
-
- for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE;
- ++UI)
- if (Visited.insert(cast<Instruction>(*UI)))
- Uses.push_back(std::make_pair(I, cast<Instruction>(*UI)));
- } while (!Uses.empty());
-
- return 0;
- }
-
- bool visitPHINode(PHINode &PN) {
- // See if we already have computed info on this node.
- std::pair<uint64_t, bool> &PHIInfo = P.PHIOrSelectSizes[&PN];
- if (PHIInfo.first) {
- PHIInfo.second = true;
- insertUse(PN, Offset, PHIInfo.first);
- return true;
- }
-
- // Check for an unsafe use of the PHI node.
- if (Instruction *EscapingI = hasUnsafePHIOrSelectUse(&PN, PHIInfo.first))
- return markAsEscaping(*EscapingI);
-
- insertUse(PN, Offset, PHIInfo.first);
- return true;
- }
-
- bool visitSelectInst(SelectInst &SI) {
- if (Value *Result = foldSelectInst(SI)) {
- 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, Offset);
-
- return true;
- }
-
- // See if we already have computed info on this node.
- std::pair<uint64_t, bool> &SelectInfo = P.PHIOrSelectSizes[&SI];
- if (SelectInfo.first) {
- SelectInfo.second = true;
- insertUse(SI, Offset, SelectInfo.first);
- return true;
- }
-
- // Check for an unsafe use of the PHI node.
- if (Instruction *EscapingI = hasUnsafePHIOrSelectUse(&SI, SelectInfo.first))
- return markAsEscaping(*EscapingI);
-
- insertUse(SI, Offset, SelectInfo.first);
- return true;
- }
-
- /// \brief Disable SROA entirely if there are unhandled users of the alloca.
- bool visitInstruction(Instruction &I) { return markAsEscaping(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 BuilderBase<UseBuilder> {
- friend class InstVisitor<UseBuilder>;
-
- /// \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)
- : BuilderBase<UseBuilder>(TD, AI, P) {}
-
- /// \brief Run the builder over the allocation.
- void operator()() {
- // Note that we have to re-evaluate size on each trip through the loop as
- // the queue grows at the tail.
- for (unsigned Idx = 0; Idx < Queue.size(); ++Idx) {
- U = Queue[Idx].U;
- Offset = Queue[Idx].Offset;
- this->visit(cast<Instruction>(U->getUser()));
- }
- }
-
-private:
- void markAsDead(Instruction &I) {
- if (VisitedDeadInsts.insert(&I))
- P.DeadUsers.push_back(&I);
- }
-
- void insertUse(Instruction &User, int64_t 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 || (uint64_t)Offset >= AllocSize ||
- (Offset < 0 && (uint64_t)-Offset >= Size))
- return markAsDead(User);
-
- // Clamp the start to the beginning of the allocation.
- if (Offset < 0) {
- Size -= (uint64_t)-Offset;
- Offset = 0;
- }
-
- uint64_t BeginOffset = Offset, 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);