#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/PtrUseVisitor.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
STATISTIC(NumAllocasAnalyzed, "Number of allocas analyzed for replacement");
STATISTIC(NumAllocaPartitions, "Number of alloca partitions formed");
-STATISTIC(MaxPartitionsPerAlloca, "Maximum number of partitions");
-STATISTIC(NumAllocaPartitionUses, "Number of alloca partition uses found");
-STATISTIC(MaxPartitionUsesPerAlloca, "Maximum number of partition uses");
+STATISTIC(MaxPartitionsPerAlloca, "Maximum number of partitions per alloca");
+STATISTIC(NumAllocaPartitionUses, "Number of alloca partition uses rewritten");
+STATISTIC(MaxUsesPerAllocaPartition, "Maximum number of uses of a partition");
STATISTIC(NumNewAllocas, "Number of new, smaller allocas introduced");
STATISTIC(NumPromoted, "Number of allocas promoted to SSA values");
STATISTIC(NumLoadsSpeculated, "Number of loads speculated to allow promotion");
}
namespace {
-/// \brief A partition of an alloca.
+/// \brief A used slice of an alloca.
///
-/// This structure represents a contiguous partition of the alloca. These are
-/// formed by examining the uses of the alloca. During formation, they may
-/// overlap but once an AllocaPartitioning is built, the Partitions within it
-/// are all disjoint. The partition also contains a chain of uses of that
-/// partition.
-class Partition {
+/// This structure represents a slice of an alloca used by some instruction. It
+/// stores both the begin and end offsets of this use, a pointer to the use
+/// itself, and a flag indicating whether we can classify the use as splittable
+/// or not when forming partitions of the alloca.
+class Slice {
/// \brief The beginning offset of the range.
uint64_t BeginOffset;
/// \brief The ending offset, not included in the range.
uint64_t EndOffset;
- /// \brief Storage for both the use of this partition and whether it can be
+ /// \brief Storage for both the use of this slice and whether it can be
/// split.
- PointerIntPair<Use *, 1, bool> PartitionUseAndIsSplittable;
+ PointerIntPair<Use *, 1, bool> UseAndIsSplittable;
public:
- Partition() : BeginOffset(), EndOffset() {}
- Partition(uint64_t BeginOffset, uint64_t EndOffset, Use *U, bool IsSplittable)
+ Slice() : BeginOffset(), EndOffset() {}
+ Slice(uint64_t BeginOffset, uint64_t EndOffset, Use *U, bool IsSplittable)
: BeginOffset(BeginOffset), EndOffset(EndOffset),
- PartitionUseAndIsSplittable(U, IsSplittable) {}
+ UseAndIsSplittable(U, IsSplittable) {}
uint64_t beginOffset() const { return BeginOffset; }
uint64_t endOffset() const { return EndOffset; }
- bool isSplittable() const { return PartitionUseAndIsSplittable.getInt(); }
- void makeUnsplittable() { PartitionUseAndIsSplittable.setInt(false); }
+ bool isSplittable() const { return UseAndIsSplittable.getInt(); }
+ void makeUnsplittable() { UseAndIsSplittable.setInt(false); }
- Use *getUse() const { return PartitionUseAndIsSplittable.getPointer(); }
+ Use *getUse() const { return UseAndIsSplittable.getPointer(); }
bool isDead() const { return getUse() == 0; }
- void kill() { PartitionUseAndIsSplittable.setPointer(0); }
+ void kill() { UseAndIsSplittable.setPointer(0); }
/// \brief Support for ordering ranges.
///
/// always increasing, and within equal start offsets, the end offsets are
/// decreasing. Thus the spanning range comes first in a cluster with the
/// same start position.
- bool operator<(const Partition &RHS) const {
+ bool operator<(const Slice &RHS) const {
if (beginOffset() < RHS.beginOffset()) return true;
if (beginOffset() > RHS.beginOffset()) return false;
if (isSplittable() != RHS.isSplittable()) return !isSplittable();
}
/// \brief Support comparison with a single offset to allow binary searches.
- friend LLVM_ATTRIBUTE_UNUSED bool operator<(const Partition &LHS,
+ friend LLVM_ATTRIBUTE_UNUSED bool operator<(const Slice &LHS,
uint64_t RHSOffset) {
return LHS.beginOffset() < RHSOffset;
}
friend LLVM_ATTRIBUTE_UNUSED bool operator<(uint64_t LHSOffset,
- const Partition &RHS) {
+ const Slice &RHS) {
return LHSOffset < RHS.beginOffset();
}
- bool operator==(const Partition &RHS) const {
+ bool operator==(const Slice &RHS) const {
return isSplittable() == RHS.isSplittable() &&
beginOffset() == RHS.beginOffset() && endOffset() == RHS.endOffset();
}
- bool operator!=(const Partition &RHS) const { return !operator==(RHS); }
+ bool operator!=(const Slice &RHS) const { return !operator==(RHS); }
};
} // end anonymous namespace
namespace llvm {
template <typename T> struct isPodLike;
-template <> struct isPodLike<Partition> {
+template <> struct isPodLike<Slice> {
static const bool value = true;
};
}
namespace {
-/// \brief Alloca partitioning representation.
+/// \brief Representation of the alloca slices.
///
-/// This class represents a partitioning of an alloca into slices, and
-/// information about the nature of uses of each slice of the alloca. The goal
-/// is that this information is sufficient to decide if and how to split the
-/// alloca apart and replace slices with scalars. It is also intended that this
-/// structure can capture the relevant information needed both to decide about
-/// and to enact these transformations.
-class AllocaPartitioning {
+/// This class represents the slices of an alloca which are formed by its
+/// various uses. If a pointer escapes, we can't fully build a representation
+/// for the slices used and we reflect that in this structure. The uses are
+/// stored, sorted by increasing beginning offset and with unsplittable slices
+/// starting at a particular offset before splittable slices.
+class AllocaSlices {
public:
- /// \brief Construct a partitioning of a particular alloca.
- ///
- /// Construction does most of the work for partitioning the alloca. This
- /// performs the necessary walks of users and builds a partitioning from it.
- AllocaPartitioning(const DataLayout &DL, AllocaInst &AI);
+ /// \brief Construct the slices of a particular alloca.
+ AllocaSlices(const DataLayout &DL, AllocaInst &AI);
/// \brief Test whether a pointer to the allocation escapes our analysis.
///
- /// If this is true, the partitioning is never fully built and should be
+ /// If this is true, the slices are never fully built and should be
/// ignored.
bool isEscaped() const { return PointerEscapingInstr; }
- /// \brief Support for iterating over the partitions.
+ /// \brief Support for iterating over the slices.
/// @{
- typedef SmallVectorImpl<Partition>::iterator iterator;
- iterator begin() { return Partitions.begin(); }
- iterator end() { return Partitions.end(); }
+ typedef SmallVectorImpl<Slice>::iterator iterator;
+ iterator begin() { return Slices.begin(); }
+ iterator end() { return Slices.end(); }
- typedef SmallVectorImpl<Partition>::const_iterator const_iterator;
- const_iterator begin() const { return Partitions.begin(); }
- const_iterator end() const { return Partitions.end(); }
+ typedef SmallVectorImpl<Slice>::const_iterator const_iterator;
+ const_iterator begin() const { return Slices.begin(); }
+ const_iterator end() const { return Slices.end(); }
/// @}
/// \brief Allow iterating the dead users for this alloca.
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void print(raw_ostream &OS, const_iterator I, StringRef Indent = " ") const;
- void printPartition(raw_ostream &OS, const_iterator I,
- StringRef Indent = " ") const;
+ void printSlice(raw_ostream &OS, const_iterator I,
+ StringRef Indent = " ") const;
void printUse(raw_ostream &OS, const_iterator I,
StringRef Indent = " ") const;
void print(raw_ostream &OS) const;
- void LLVM_ATTRIBUTE_NOINLINE LLVM_ATTRIBUTE_USED dump(const_iterator I) const;
- void LLVM_ATTRIBUTE_NOINLINE LLVM_ATTRIBUTE_USED dump() const;
+ void dump(const_iterator I) const;
+ void dump() const;
#endif
private:
template <typename DerivedT, typename RetT = void> class BuilderBase;
- class PartitionBuilder;
- friend class AllocaPartitioning::PartitionBuilder;
+ class SliceBuilder;
+ friend class AllocaSlices::SliceBuilder;
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
/// \brief Handle to alloca instruction to simplify method interfaces.
AllocaInst &AI;
#endif
- /// \brief The instruction responsible for this alloca having no partitioning.
+ /// \brief The instruction responsible for this alloca not having a known set
+ /// of slices.
///
/// When an instruction (potentially) escapes the pointer to the alloca, we
- /// store a pointer to that here and abort trying to partition the alloca.
- /// This will be null if the alloca is partitioned successfully.
+ /// store a pointer to that here and abort trying to form slices of the
+ /// alloca. This will be null if the alloca slices are analyzed successfully.
Instruction *PointerEscapingInstr;
- /// \brief The partitions of the alloca.
+ /// \brief The slices of the alloca.
///
- /// We store a vector of the partitions over the alloca here. This vector is
- /// sorted by increasing begin offset, and then by decreasing end offset. See
- /// the Partition inner class for more details. Initially (during
- /// construction) there are overlaps, but we form a disjoint sequence of
- /// partitions while finishing construction and a fully constructed object is
- /// expected to always have this as a disjoint space.
- SmallVector<Partition, 8> Partitions;
+ /// We store a vector of the slices formed by uses of the alloca here. This
+ /// vector is sorted by increasing begin offset, and then the unsplittable
+ /// slices before the splittable ones. See the Slice inner class for more
+ /// details.
+ SmallVector<Slice, 8> Slices;
/// \brief Instructions which will become dead if we rewrite the alloca.
///
- /// Note that these are not separated by partition. This is because we expect
- /// a partitioned alloca to be completely rewritten or not rewritten at all.
- /// If rewritten, all these instructions can simply be removed and replaced
- /// with undef as they come from outside of the allocated space.
+ /// Note that these are not separated by slice. This is because we expect an
+ /// alloca to be completely rewritten or not rewritten at all. If rewritten,
+ /// all these instructions can simply be removed and replaced with undef as
+ /// they come from outside of the allocated space.
SmallVector<Instruction *, 8> DeadUsers;
/// \brief Operands which will become dead if we rewrite the alloca.
return 0;
}
-/// \brief Builder for the alloca partitioning.
+/// \brief Builder for the alloca slices.
///
-/// This class builds an alloca partitioning by recursively visiting the uses
-/// of an alloca and splitting the partitions for each load and store at each
-/// offset.
-class AllocaPartitioning::PartitionBuilder
- : public PtrUseVisitor<PartitionBuilder> {
- friend class PtrUseVisitor<PartitionBuilder>;
- friend class InstVisitor<PartitionBuilder>;
- typedef PtrUseVisitor<PartitionBuilder> Base;
+/// This class builds a set of alloca slices by recursively visiting the uses
+/// of an alloca and making a slice for each load and store at each offset.
+class AllocaSlices::SliceBuilder : public PtrUseVisitor<SliceBuilder> {
+ friend class PtrUseVisitor<SliceBuilder>;
+ friend class InstVisitor<SliceBuilder>;
+ typedef PtrUseVisitor<SliceBuilder> Base;
const uint64_t AllocSize;
- AllocaPartitioning &P;
+ AllocaSlices &S;
- SmallDenseMap<Instruction *, unsigned> MemTransferPartitionMap;
+ SmallDenseMap<Instruction *, unsigned> MemTransferSliceMap;
SmallDenseMap<Instruction *, uint64_t> PHIOrSelectSizes;
/// \brief Set to de-duplicate dead instructions found in the use walk.
SmallPtrSet<Instruction *, 4> VisitedDeadInsts;
public:
- PartitionBuilder(const DataLayout &DL, AllocaInst &AI, AllocaPartitioning &P)
- : PtrUseVisitor<PartitionBuilder>(DL),
- AllocSize(DL.getTypeAllocSize(AI.getAllocatedType())),
- P(P) {}
+ SliceBuilder(const DataLayout &DL, AllocaInst &AI, AllocaSlices &S)
+ : PtrUseVisitor<SliceBuilder>(DL),
+ AllocSize(DL.getTypeAllocSize(AI.getAllocatedType())), S(S) {}
private:
void markAsDead(Instruction &I) {
if (VisitedDeadInsts.insert(&I))
- P.DeadUsers.push_back(&I);
+ S.DeadUsers.push_back(&I);
}
void insertUse(Instruction &I, const APInt &Offset, uint64_t Size,
DEBUG(dbgs() << "WARNING: Ignoring " << Size << " byte use @" << Offset
<< " which has zero size or starts outside of the "
<< AllocSize << " byte alloca:\n"
- << " alloca: " << P.AI << "\n"
+ << " alloca: " << S.AI << "\n"
<< " use: " << I << "\n");
return markAsDead(I);
}
if (Size > AllocSize - BeginOffset) {
DEBUG(dbgs() << "WARNING: Clamping a " << Size << " byte use @" << Offset
<< " to remain within the " << AllocSize << " byte alloca:\n"
- << " alloca: " << P.AI << "\n"
+ << " alloca: " << S.AI << "\n"
<< " use: " << I << "\n");
EndOffset = AllocSize;
}
- P.Partitions.push_back(Partition(BeginOffset, EndOffset, U, IsSplittable));
+ S.Slices.push_back(Slice(BeginOffset, EndOffset, U, IsSplittable));
}
void visitBitCastInst(BitCastInst &BC) {
DEBUG(dbgs() << "WARNING: Ignoring " << Size << " byte store @" << Offset
<< " which extends past the end of the " << AllocSize
<< " byte alloca:\n"
- << " alloca: " << P.AI << "\n"
+ << " alloca: " << S.AI << "\n"
<< " use: " << SI << "\n");
return markAsDead(SI);
}
if (!II.isVolatile())
return markAsDead(II);
- return insertUse(II, Offset, Size, /*IsSplittable=*/false);;
+ return insertUse(II, Offset, Size, /*IsSplittable=*/false);
}
// If we have seen both source and destination for a mem transfer, then
bool Inserted;
SmallDenseMap<Instruction *, unsigned>::iterator MTPI;
llvm::tie(MTPI, Inserted) =
- MemTransferPartitionMap.insert(std::make_pair(&II, P.Partitions.size()));
+ MemTransferSliceMap.insert(std::make_pair(&II, S.Slices.size()));
unsigned PrevIdx = MTPI->second;
if (!Inserted) {
- Partition &PrevP = P.Partitions[PrevIdx];
+ Slice &PrevP = S.Slices[PrevIdx];
// Check if the begin offsets match and this is a non-volatile transfer.
// In that case, we can completely elide the transfer.
insertUse(II, Offset, Size, /*IsSplittable=*/Inserted && Length);
// Check that we ended up with a valid index in the map.
- assert(P.Partitions[PrevIdx].getUse()->getUser() == &II &&
- "Map index doesn't point back to a partition with this user.");
+ assert(S.Slices[PrevIdx].getUse()->getUser() == &II &&
+ "Map index doesn't point back to a slice with this user.");
}
// Disable SRoA for any intrinsics except for lifetime invariants.
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
+ // the same offset to be a viable use for slicing purposes. These uses
// are considered unsplittable and the size is the maximum loaded or stored
// size.
SmallPtrSet<Instruction *, 4> Visited;
// for address sanitization.
if ((Offset.isNegative() && (-Offset).uge(PHISize)) ||
(!Offset.isNegative() && Offset.uge(AllocSize))) {
- P.DeadOperands.push_back(U);
+ S.DeadOperands.push_back(U);
return;
}
else
// Otherwise the operand to the select is dead, and we can replace it
// with undef.
- P.DeadOperands.push_back(U);
+ S.DeadOperands.push_back(U);
return;
}
// for address sanitization.
if ((Offset.isNegative() && Offset.uge(SelectSize)) ||
(!Offset.isNegative() && Offset.uge(AllocSize))) {
- P.DeadOperands.push_back(U);
+ S.DeadOperands.push_back(U);
return;
}
}
};
-namespace {
-struct IsPartitionDead {
- bool operator()(const Partition &P) { return P.isDead(); }
-};
-}
-
-AllocaPartitioning::AllocaPartitioning(const DataLayout &DL, AllocaInst &AI)
+AllocaSlices::AllocaSlices(const DataLayout &DL, AllocaInst &AI)
:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
AI(AI),
#endif
PointerEscapingInstr(0) {
- PartitionBuilder PB(DL, AI, *this);
- PartitionBuilder::PtrInfo PtrI = PB.visitPtr(AI);
+ SliceBuilder PB(DL, AI, *this);
+ SliceBuilder::PtrInfo PtrI = PB.visitPtr(AI);
if (PtrI.isEscaped() || PtrI.isAborted()) {
// FIXME: We should sink the escape vs. abort info into the caller nicely,
- // possibly by just storing the PtrInfo in the AllocaPartitioning.
+ // possibly by just storing the PtrInfo in the AllocaSlices.
PointerEscapingInstr = PtrI.getEscapingInst() ? PtrI.getEscapingInst()
: PtrI.getAbortingInst();
assert(PointerEscapingInstr && "Did not track a bad instruction");
return;
}
+ Slices.erase(std::remove_if(Slices.begin(), Slices.end(),
+ std::mem_fun_ref(&Slice::isDead)),
+ Slices.end());
+
// Sort the uses. This arranges for the offsets to be in ascending order,
// and the sizes to be in descending order.
- std::sort(Partitions.begin(), Partitions.end());
-
- Partitions.erase(
- std::remove_if(Partitions.begin(), Partitions.end(), IsPartitionDead()),
- Partitions.end());
-
- // Record how many partitions we end up with.
- NumAllocaPartitions += Partitions.size();
- MaxPartitionsPerAlloca = std::max<unsigned>(Partitions.size(), MaxPartitionsPerAlloca);
-
- NumAllocaPartitionUses += Partitions.size();
- MaxPartitionUsesPerAlloca =
- std::max<unsigned>(Partitions.size(), MaxPartitionUsesPerAlloca);
+ std::sort(Slices.begin(), Slices.end());
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-void AllocaPartitioning::print(raw_ostream &OS, const_iterator I,
- StringRef Indent) const {
- printPartition(OS, I, Indent);
+void AllocaSlices::print(raw_ostream &OS, const_iterator I,
+ StringRef Indent) const {
+ printSlice(OS, I, Indent);
printUse(OS, I, Indent);
}
-void AllocaPartitioning::printPartition(raw_ostream &OS, const_iterator I,
- StringRef Indent) const {
+void AllocaSlices::printSlice(raw_ostream &OS, const_iterator I,
+ StringRef Indent) const {
OS << Indent << "[" << I->beginOffset() << "," << I->endOffset() << ")"
- << " partition #" << (I - begin())
+ << " slice #" << (I - begin())
<< (I->isSplittable() ? " (splittable)" : "") << "\n";
}
-void AllocaPartitioning::printUse(raw_ostream &OS, const_iterator I,
- StringRef Indent) const {
+void AllocaSlices::printUse(raw_ostream &OS, const_iterator I,
+ StringRef Indent) const {
OS << Indent << " used by: " << *I->getUse()->getUser() << "\n";
}
-void AllocaPartitioning::print(raw_ostream &OS) const {
+void AllocaSlices::print(raw_ostream &OS) const {
if (PointerEscapingInstr) {
- OS << "No partitioning for alloca: " << AI << "\n"
+ OS << "Can't analyze slices for alloca: " << AI << "\n"
<< " A pointer to this alloca escaped by:\n"
<< " " << *PointerEscapingInstr << "\n";
return;
}
- OS << "Partitioning of alloca: " << AI << "\n";
+ OS << "Slices of alloca: " << AI << "\n";
for (const_iterator I = begin(), E = end(); I != E; ++I)
print(OS, I);
}
-void AllocaPartitioning::dump(const_iterator I) const { print(dbgs(), I); }
-void AllocaPartitioning::dump() const { print(dbgs()); }
+LLVM_DUMP_METHOD void AllocaSlices::dump(const_iterator I) const {
+ print(dbgs(), I);
+}
+LLVM_DUMP_METHOD void AllocaSlices::dump() const { print(dbgs()); }
#endif // !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
SmallVector<DbgValueInst *, 4> DVIs;
public:
- AllocaPromoter(const SmallVectorImpl<Instruction*> &Insts, SSAUpdater &S,
+ AllocaPromoter(const SmallVectorImpl<Instruction *> &Insts, SSAUpdater &S,
AllocaInst &AI, DIBuilder &DIB)
- : LoadAndStorePromoter(Insts, S), AI(AI), DIB(DIB) {}
+ : LoadAndStorePromoter(Insts, S), AI(AI), DIB(DIB) {}
void run(const SmallVectorImpl<Instruction*> &Insts) {
- // Remember which alloca we're promoting (for isInstInList).
+ // Retain the debug information attached to the alloca for use when
+ // rewriting loads and stores.
if (MDNode *DebugNode = MDNode::getIfExists(AI.getContext(), &AI)) {
for (Value::use_iterator UI = DebugNode->use_begin(),
UE = DebugNode->use_end();
}
LoadAndStorePromoter::run(Insts);
- AI.eraseFromParent();
+
+ // While we have the debug information, clear it off of the alloca. The
+ // caller takes care of deleting the alloca.
while (!DDIs.empty())
DDIs.pop_back_val()->eraseFromParent();
while (!DVIs.empty())
virtual bool isInstInList(Instruction *I,
const SmallVectorImpl<Instruction*> &Insts) const {
+ Value *Ptr;
if (LoadInst *LI = dyn_cast<LoadInst>(I))
- return LI->getOperand(0) == &AI;
- return cast<StoreInst>(I)->getPointerOperand() == &AI;
+ Ptr = LI->getOperand(0);
+ else
+ Ptr = cast<StoreInst>(I)->getPointerOperand();
+
+ // Only used to detect cycles, which will be rare and quickly found as
+ // we're walking up a chain of defs rather than down through uses.
+ SmallPtrSet<Value *, 4> Visited;
+
+ do {
+ if (Ptr == &AI)
+ return true;
+
+ if (BitCastInst *BCI = dyn_cast<BitCastInst>(Ptr))
+ Ptr = BCI->getOperand(0);
+ else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Ptr))
+ Ptr = GEPI->getPointerOperand();
+ else
+ return false;
+
+ } while (Visited.insert(Ptr));
+
+ return false;
}
virtual void updateDebugInfo(Instruction *Inst) const {
private:
friend class PHIOrSelectSpeculator;
- friend class AllocaPartitionRewriter;
- friend class AllocaPartitionVectorRewriter;
-
- bool rewritePartitions(AllocaInst &AI, AllocaPartitioning &P,
- AllocaPartitioning::iterator B,
- AllocaPartitioning::iterator E,
- int64_t BeginOffset, int64_t EndOffset,
- ArrayRef<AllocaPartitioning::iterator> SplitUses);
- bool splitAlloca(AllocaInst &AI, AllocaPartitioning &P);
+ friend class AllocaSliceRewriter;
+
+ bool rewritePartition(AllocaInst &AI, AllocaSlices &S,
+ AllocaSlices::iterator B, AllocaSlices::iterator E,
+ int64_t BeginOffset, int64_t EndOffset,
+ ArrayRef<AllocaSlices::iterator> SplitUses);
+ bool splitAlloca(AllocaInst &AI, AllocaSlices &S);
bool runOnAlloca(AllocaInst &AI);
void deleteDeadInstructions(SmallPtrSet<AllocaInst *, 4> &DeletedAllocas);
bool promoteAllocas(Function &F);
INITIALIZE_PASS_END(SROA, "sroa", "Scalar Replacement Of Aggregates",
false, false)
-/// Walk a range of a partitioning looking for a common type to cover this
-/// sequence of partition uses.
-static Type *findCommonType(AllocaPartitioning::const_iterator B,
- AllocaPartitioning::const_iterator E,
+/// Walk the range of a partitioning looking for a common type to cover this
+/// sequence of slices.
+static Type *findCommonType(AllocaSlices::const_iterator B,
+ AllocaSlices::const_iterator E,
uint64_t EndOffset) {
Type *Ty = 0;
- for (AllocaPartitioning::const_iterator I = B; I != E; ++I) {
+ bool IgnoreNonIntegralTypes = false;
+ for (AllocaSlices::const_iterator I = B; I != E; ++I) {
Use *U = I->getUse();
if (isa<IntrinsicInst>(*U->getUser()))
continue;
continue;
Type *UserTy = 0;
- if (LoadInst *LI = dyn_cast<LoadInst>(U->getUser()))
+ if (LoadInst *LI = dyn_cast<LoadInst>(U->getUser())) {
UserTy = LI->getType();
- else if (StoreInst *SI = dyn_cast<StoreInst>(U->getUser()))
+ } else if (StoreInst *SI = dyn_cast<StoreInst>(U->getUser())) {
UserTy = SI->getValueOperand()->getType();
- else
- return 0; // Bail if we have weird uses.
+ } else {
+ IgnoreNonIntegralTypes = true; // Give up on anything but an iN type.
+ continue;
+ }
if (IntegerType *ITy = dyn_cast<IntegerType>(UserTy)) {
// If the type is larger than the partition, skip it. We only encounter
- // this for split integer operations where we want to use the type of
- // the
- // entity causing the split.
- if (ITy->getBitWidth() / 8 > (EndOffset - B->beginOffset()))
+ // this for split integer operations where we want to use the type of the
+ // entity causing the split. Also skip if the type is not a byte width
+ // multiple.
+ if (ITy->getBitWidth() % 8 != 0 ||
+ ITy->getBitWidth() / 8 > (EndOffset - B->beginOffset()))
continue;
// If we have found an integer type use covering the alloca, use that
- // regardless of the other types, as integers are often used for a
- // "bucket
- // of bits" type.
+ // regardless of the other types, as integers are often used for
+ // a "bucket of bits" type.
+ //
+ // NB: This *must* be the only return from inside the loop so that the
+ // order of slices doesn't impact the computed type.
return ITy;
+ } else if (IgnoreNonIntegralTypes) {
+ continue;
}
if (Ty && Ty != UserTy)
- return 0;
+ IgnoreNonIntegralTypes = true; // Give up on anything but an iN type.
Ty = UserTy;
}
if (!NewTy->isSingleValueType() || !OldTy->isSingleValueType())
return false;
+ // We can convert pointers to integers and vice-versa. Same for vectors
+ // of pointers and integers.
+ OldTy = OldTy->getScalarType();
+ NewTy = NewTy->getScalarType();
if (NewTy->isPointerTy() || OldTy->isPointerTy()) {
if (NewTy->isPointerTy() && OldTy->isPointerTy())
return true;
/// inttoptr, and ptrtoint casts. Use the \c canConvertValue predicate to test
/// two types for viability with this routine.
static Value *convertValue(const DataLayout &DL, IRBuilderTy &IRB, Value *V,
- Type *Ty) {
- assert(canConvertValue(DL, V->getType(), Ty) &&
- "Value not convertable to type");
- if (V->getType() == Ty)
+ Type *NewTy) {
+ Type *OldTy = V->getType();
+ assert(canConvertValue(DL, OldTy, NewTy) && "Value not convertable to type");
+
+ if (OldTy == NewTy)
return V;
- if (IntegerType *OldITy = dyn_cast<IntegerType>(V->getType()))
- if (IntegerType *NewITy = dyn_cast<IntegerType>(Ty))
+
+ if (IntegerType *OldITy = dyn_cast<IntegerType>(OldTy))
+ if (IntegerType *NewITy = dyn_cast<IntegerType>(NewTy))
if (NewITy->getBitWidth() > OldITy->getBitWidth())
return IRB.CreateZExt(V, NewITy);
- if (V->getType()->isIntegerTy() && Ty->isPointerTy())
- return IRB.CreateIntToPtr(V, Ty);
- if (V->getType()->isPointerTy() && Ty->isIntegerTy())
- return IRB.CreatePtrToInt(V, Ty);
- return IRB.CreateBitCast(V, Ty);
+ // See if we need inttoptr for this type pair. A cast involving both scalars
+ // and vectors requires and additional bitcast.
+ if (OldTy->getScalarType()->isIntegerTy() &&
+ NewTy->getScalarType()->isPointerTy()) {
+ // Expand <2 x i32> to i8* --> <2 x i32> to i64 to i8*
+ if (OldTy->isVectorTy() && !NewTy->isVectorTy())
+ return IRB.CreateIntToPtr(IRB.CreateBitCast(V, DL.getIntPtrType(NewTy)),
+ NewTy);
+
+ // Expand i128 to <2 x i8*> --> i128 to <2 x i64> to <2 x i8*>
+ if (!OldTy->isVectorTy() && NewTy->isVectorTy())
+ return IRB.CreateIntToPtr(IRB.CreateBitCast(V, DL.getIntPtrType(NewTy)),
+ NewTy);
+
+ return IRB.CreateIntToPtr(V, NewTy);
+ }
+
+ // See if we need ptrtoint for this type pair. A cast involving both scalars
+ // and vectors requires and additional bitcast.
+ if (OldTy->getScalarType()->isPointerTy() &&
+ NewTy->getScalarType()->isIntegerTy()) {
+ // Expand <2 x i8*> to i128 --> <2 x i8*> to <2 x i64> to i128
+ if (OldTy->isVectorTy() && !NewTy->isVectorTy())
+ return IRB.CreateBitCast(IRB.CreatePtrToInt(V, DL.getIntPtrType(OldTy)),
+ NewTy);
+
+ // Expand i8* to <2 x i32> --> i8* to i64 to <2 x i32>
+ if (!OldTy->isVectorTy() && NewTy->isVectorTy())
+ return IRB.CreateBitCast(IRB.CreatePtrToInt(V, DL.getIntPtrType(OldTy)),
+ NewTy);
+
+ return IRB.CreatePtrToInt(V, NewTy);
+ }
+
+ return IRB.CreateBitCast(V, NewTy);
}
-/// \brief Test whether the given partition use can be promoted to a vector.
+/// \brief Test whether the given slice use can be promoted to a vector.
///
/// This function is called to test each entry in a partioning which is slated
-/// for a single partition.
-static bool isVectorPromotionViableForPartitioning(
- const DataLayout &DL, AllocaPartitioning &P,
- uint64_t PartitionBeginOffset, uint64_t PartitionEndOffset, VectorType *Ty,
- uint64_t ElementSize, AllocaPartitioning::const_iterator I) {
- // First validate the partitioning offsets.
+/// 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) {
+ // First validate the slice offsets.
uint64_t BeginOffset =
- std::max(I->beginOffset(), PartitionBeginOffset) - PartitionBeginOffset;
+ std::max(I->beginOffset(), SliceBeginOffset) - SliceBeginOffset;
uint64_t BeginIndex = BeginOffset / ElementSize;
if (BeginIndex * ElementSize != BeginOffset ||
BeginIndex >= Ty->getNumElements())
return false;
uint64_t EndOffset =
- std::min(I->endOffset(), PartitionEndOffset) - PartitionBeginOffset;
+ std::min(I->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 *PartitionTy =
+ Type *SliceTy =
(NumElements == 1) ? Ty->getElementType()
: VectorType::get(Ty->getElementType(), NumElements);
if (LI->isVolatile())
return false;
Type *LTy = LI->getType();
- if (PartitionBeginOffset > I->beginOffset() ||
- PartitionEndOffset < I->endOffset()) {
+ if (SliceBeginOffset > I->beginOffset() ||
+ SliceEndOffset < I->endOffset()) {
assert(LTy->isIntegerTy());
LTy = SplitIntTy;
}
- if (!canConvertValue(DL, PartitionTy, LTy))
+ if (!canConvertValue(DL, SliceTy, LTy))
return false;
} else if (StoreInst *SI = dyn_cast<StoreInst>(U->getUser())) {
if (SI->isVolatile())
return false;
Type *STy = SI->getValueOperand()->getType();
- if (PartitionBeginOffset > I->beginOffset() ||
- PartitionEndOffset < I->endOffset()) {
+ if (SliceBeginOffset > I->beginOffset() ||
+ SliceEndOffset < I->endOffset()) {
assert(STy->isIntegerTy());
STy = SplitIntTy;
}
- if (!canConvertValue(DL, STy, PartitionTy))
+ if (!canConvertValue(DL, STy, SliceTy))
return false;
+ } else {
+ return false;
}
return true;
}
-/// \brief Test whether the given alloca partition can be promoted to a vector.
+/// \brief Test whether the given alloca partitioning and range of slices can be
+/// promoted to a vector.
///
/// This is a quick test to check whether we can rewrite a particular alloca
/// partition (and its newly formed alloca) into a vector alloca with only
/// 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, AllocaPartitioning &P,
- uint64_t PartitionBeginOffset, uint64_t PartitionEndOffset,
- AllocaPartitioning::const_iterator I, AllocaPartitioning::const_iterator E,
- ArrayRef<AllocaPartitioning::iterator> SplitUses) {
+static bool
+isVectorPromotionViable(const DataLayout &DL, Type *AllocaTy, AllocaSlices &S,
+ uint64_t SliceBeginOffset, uint64_t SliceEndOffset,
+ AllocaSlices::const_iterator I,
+ AllocaSlices::const_iterator E,
+ ArrayRef<AllocaSlices::iterator> SplitUses) {
VectorType *Ty = dyn_cast<VectorType>(AllocaTy);
if (!Ty)
return false;
ElementSize /= 8;
for (; I != E; ++I)
- if (!isVectorPromotionViableForPartitioning(
- DL, P, PartitionBeginOffset, PartitionEndOffset, Ty, ElementSize,
- I))
+ if (!isVectorPromotionViableForSlice(DL, S, SliceBeginOffset,
+ SliceEndOffset, Ty, ElementSize, I))
return false;
- for (ArrayRef<AllocaPartitioning::iterator>::const_iterator
- SUI = SplitUses.begin(),
- SUE = SplitUses.end();
+ for (ArrayRef<AllocaSlices::iterator>::const_iterator SUI = SplitUses.begin(),
+ SUE = SplitUses.end();
SUI != SUE; ++SUI)
- if (!isVectorPromotionViableForPartitioning(
- DL, P, PartitionBeginOffset, PartitionEndOffset, Ty, ElementSize,
- *SUI))
+ if (!isVectorPromotionViableForSlice(DL, S, SliceBeginOffset,
+ SliceEndOffset, Ty, ElementSize, *SUI))
return false;
return true;
}
-/// \brief Test whether a partitioning slice of an alloca is a valid set of
-/// operations for integer widening.
+/// \brief Test whether a slice of an alloca is valid for integer widening.
///
/// This implements the necessary checking for the \c isIntegerWideningViable
-/// test below on a single partitioning slice of the alloca.
-static bool isIntegerWideningViableForPartitioning(
- const DataLayout &DL, Type *AllocaTy, uint64_t AllocBeginOffset,
- uint64_t Size, AllocaPartitioning &P, AllocaPartitioning::const_iterator I,
- bool &WholeAllocaOp) {
+/// test below on a single slice of the alloca.
+static bool isIntegerWideningViableForSlice(const DataLayout &DL,
+ Type *AllocaTy,
+ uint64_t AllocBeginOffset,
+ uint64_t Size, AllocaSlices &S,
+ AllocaSlices::const_iterator I,
+ bool &WholeAllocaOp) {
uint64_t RelBegin = I->beginOffset() - AllocBeginOffset;
uint64_t RelEnd = I->endOffset() - AllocBeginOffset;
/// promote the resulting alloca.
static bool
isIntegerWideningViable(const DataLayout &DL, Type *AllocaTy,
- uint64_t AllocBeginOffset, AllocaPartitioning &P,
- AllocaPartitioning::const_iterator I,
- AllocaPartitioning::const_iterator E,
- ArrayRef<AllocaPartitioning::iterator> SplitUses) {
+ uint64_t AllocBeginOffset, AllocaSlices &S,
+ AllocaSlices::const_iterator I,
+ AllocaSlices::const_iterator E,
+ ArrayRef<AllocaSlices::iterator> SplitUses) {
uint64_t SizeInBits = DL.getTypeSizeInBits(AllocaTy);
// Don't create integer types larger than the maximum bitwidth.
if (SizeInBits > IntegerType::MAX_INT_BITS)
bool WholeAllocaOp = (I != E) ? false : DL.isLegalInteger(SizeInBits);
for (; I != E; ++I)
- if (!isIntegerWideningViableForPartitioning(DL, AllocaTy, AllocBeginOffset,
- Size, P, I, WholeAllocaOp))
+ if (!isIntegerWideningViableForSlice(DL, AllocaTy, AllocBeginOffset, Size,
+ S, I, WholeAllocaOp))
return false;
- for (ArrayRef<AllocaPartitioning::iterator>::const_iterator
- SUI = SplitUses.begin(),
- SUE = SplitUses.end();
+ for (ArrayRef<AllocaSlices::iterator>::const_iterator SUI = SplitUses.begin(),
+ SUE = SplitUses.end();
SUI != SUE; ++SUI)
- if (!isIntegerWideningViableForPartitioning(DL, AllocaTy, AllocBeginOffset,
- Size, P, *SUI, WholeAllocaOp))
+ if (!isIntegerWideningViableForSlice(DL, AllocaTy, AllocBeginOffset, Size,
+ S, *SUI, WholeAllocaOp))
return false;
return WholeAllocaOp;
}
namespace {
-/// \brief Visitor to rewrite instructions using a partition of an alloca to
-/// use a new alloca.
+/// \brief Visitor to rewrite instructions using p particular slice of an alloca
+/// to use a new alloca.
///
/// Also implements the rewriting to vector-based accesses when the partition
/// passes the isVectorPromotionViable predicate. Most of the rewriting logic
/// lives here.
-class AllocaPartitionRewriter : public InstVisitor<AllocaPartitionRewriter,
- bool> {
+class AllocaSliceRewriter : public InstVisitor<AllocaSliceRewriter, bool> {
// Befriend the base class so it can delegate to private visit methods.
- friend class llvm::InstVisitor<AllocaPartitionRewriter, bool>;
- typedef llvm::InstVisitor<AllocaPartitionRewriter, bool> Base;
+ friend class llvm::InstVisitor<AllocaSliceRewriter, bool>;
+ typedef llvm::InstVisitor<AllocaSliceRewriter, bool> Base;
const DataLayout &DL;
- AllocaPartitioning &P;
+ AllocaSlices &S;
SROA &Pass;
AllocaInst &OldAI, &NewAI;
const uint64_t NewAllocaBeginOffset, NewAllocaEndOffset;
// integer type will be stored here for easy access during rewriting.
IntegerType *IntTy;
- // The offset of the partition user currently being rewritten.
+ // The offset of the slice currently being rewritten.
uint64_t BeginOffset, EndOffset;
bool IsSplittable;
bool IsSplit;
Use *OldUse;
Instruction *OldPtr;
+ // Output members carrying state about the result of visiting and rewriting
+ // the slice of the alloca.
+ bool IsUsedByRewrittenSpeculatableInstructions;
+
// Utility IR builder, whose name prefix is setup for each visited use, and
// the insertion point is set to point to the user.
IRBuilderTy IRB;
public:
- AllocaPartitionRewriter(const DataLayout &DL, AllocaPartitioning &P,
- SROA &Pass, AllocaInst &OldAI, AllocaInst &NewAI,
- uint64_t NewBeginOffset, uint64_t NewEndOffset,
- bool IsVectorPromotable = false,
- bool IsIntegerPromotable = false)
- : DL(DL), P(P), Pass(Pass), OldAI(OldAI), NewAI(NewAI),
+ AllocaSliceRewriter(const DataLayout &DL, AllocaSlices &S, SROA &Pass,
+ AllocaInst &OldAI, AllocaInst &NewAI,
+ uint64_t NewBeginOffset, uint64_t NewEndOffset,
+ bool IsVectorPromotable = false,
+ bool IsIntegerPromotable = false)
+ : DL(DL), S(S), Pass(Pass), OldAI(OldAI), NewAI(NewAI),
NewAllocaBeginOffset(NewBeginOffset), NewAllocaEndOffset(NewEndOffset),
NewAllocaTy(NewAI.getAllocatedType()),
VecTy(IsVectorPromotable ? cast<VectorType>(NewAllocaTy) : 0),
DL.getTypeSizeInBits(NewAI.getAllocatedType()))
: 0),
BeginOffset(), EndOffset(), IsSplittable(), IsSplit(), OldUse(),
- OldPtr(), IRB(NewAI.getContext(), ConstantFolder()) {
+ OldPtr(), IsUsedByRewrittenSpeculatableInstructions(false),
+ IRB(NewAI.getContext(), ConstantFolder()) {
if (VecTy) {
assert((DL.getTypeSizeInBits(ElementTy) % 8) == 0 &&
"Only multiple-of-8 sized vector elements are viable");
IsVectorPromotable != IsIntegerPromotable);
}
- bool visit(AllocaPartitioning::const_iterator I) {
+ bool visit(AllocaSlices::const_iterator I) {
bool CanSROA = true;
BeginOffset = I->beginOffset();
EndOffset = I->endOffset();
return CanSROA;
}
+ /// \brief Query whether this slice is used by speculatable instructions after
+ /// rewriting.
+ ///
+ /// These instructions (PHIs and Selects currently) require the alloca slice
+ /// to run back through the rewriter. Thus, they are promotable, but not on
+ /// this iteration. This is distinct from a slice which is unpromotable for
+ /// some other reason, in which case we don't even want to perform the
+ /// speculation. This can be querried at any time and reflects whether (at
+ /// that point) a visit call has rewritten a speculatable instruction on the
+ /// current slice.
+ bool isUsedByRewrittenSpeculatableInstructions() const {
+ return IsUsedByRewrittenSpeculatableInstructions;
+ }
+
private:
// Make sure the other visit overloads are visible.
using Base::visit;
assert(EndIndex > BeginIndex && "Empty vector!");
unsigned NumElements = EndIndex - BeginIndex;
assert(NumElements <= VecTy->getNumElements() && "Too many elements!");
- Type *PartitionTy
- = (NumElements == 1) ? ElementTy
- : VectorType::get(ElementTy, NumElements);
- if (V->getType() != PartitionTy)
- V = convertValue(DL, IRB, V, PartitionTy);
+ Type *SliceTy =
+ (NumElements == 1) ? ElementTy
+ : VectorType::get(ElementTy, NumElements);
+ if (V->getType() != SliceTy)
+ V = convertValue(DL, IRB, V, SliceTy);
// Mix in the existing elements.
Value *Old = IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(),
assert(EndOffset > NewAllocaBeginOffset);
uint64_t NewBeginOffset = std::max(BeginOffset, NewAllocaBeginOffset);
uint64_t NewEndOffset = std::min(EndOffset, NewAllocaEndOffset);
- uint64_t PartitionOffset = NewBeginOffset - NewAllocaBeginOffset;
+ uint64_t SliceOffset = NewBeginOffset - NewAllocaBeginOffset;
// If this doesn't map cleanly onto the alloca type, and that type isn't
// a single value type, just emit a memset.
Constant *Size = ConstantInt::get(SizeTy, NewEndOffset - NewBeginOffset);
CallInst *New = IRB.CreateMemSet(
getAdjustedAllocaPtr(IRB, NewBeginOffset, II.getRawDest()->getType()),
- II.getValue(), Size, getOffsetAlign(PartitionOffset),
- II.isVolatile());
+ II.getValue(), Size, getOffsetAlign(SliceOffset), II.isVolatile());
(void)New;
DEBUG(dbgs() << " to: " << *New << "\n");
return false;
APInt RelOffset(IntPtrWidth, NewBeginOffset - BeginOffset);
unsigned Align = II.getAlignment();
- uint64_t PartitionOffset = NewBeginOffset - NewAllocaBeginOffset;
+ uint64_t SliceOffset = NewBeginOffset - NewAllocaBeginOffset;
if (Align > 1)
- Align = MinAlign(
- RelOffset.zextOrTrunc(64).getZExtValue(),
- MinAlign(II.getAlignment(), getOffsetAlign(PartitionOffset)));
+ Align =
+ MinAlign(RelOffset.zextOrTrunc(64).getZExtValue(),
+ MinAlign(II.getAlignment(), getOffsetAlign(SliceOffset)));
// For unsplit intrinsics, we simply modify the source and destination
// pointers in place. This isn't just an optimization, it is a matter of
// as local as possible to the PHI. To do that, we re-use the location of
// the old pointer, which necessarily must be in the right position to
// dominate the PHI.
- IRBuilderTy PtrBuilder(cast<Instruction>(OldPtr));
+ IRBuilderTy PtrBuilder(OldPtr);
PtrBuilder.SetNamePrefix(Twine(NewAI.getName()) + "." + Twine(BeginOffset) +
".");
deleteIfTriviallyDead(OldPtr);
// Check whether we can speculate this PHI node, and if so remember that
- // fact and return that this alloca remains viable for promotion to an SSA
- // value.
+ // fact and queue it up for another iteration after the speculation
+ // occurs.
if (isSafePHIToSpeculate(PN, &DL)) {
Pass.SpeculatablePHIs.insert(&PN);
+ IsUsedByRewrittenSpeculatableInstructions = true;
return true;
}
deleteIfTriviallyDead(OldPtr);
// Check whether we can speculate this select instruction, and if so
- // remember that fact and return that this alloca remains viable for
- // promotion to an SSA value.
+ // remember that fact and queue it up for another iteration after the
+ // speculation occurs.
if (isSafeSelectToSpeculate(SI, &DL)) {
Pass.SpeculatableSelects.insert(&SI);
+ IsUsedByRewrittenSpeculatableInstructions = true;
return true;
}
/// 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::rewritePartitions(AllocaInst &AI, AllocaPartitioning &P,
- AllocaPartitioning::iterator B,
- AllocaPartitioning::iterator E,
- int64_t BeginOffset, int64_t EndOffset,
- ArrayRef<AllocaPartitioning::iterator> SplitUses) {
+bool SROA::rewritePartition(AllocaInst &AI, AllocaSlices &S,
+ AllocaSlices::iterator B, AllocaSlices::iterator E,
+ int64_t BeginOffset, int64_t EndOffset,
+ ArrayRef<AllocaSlices::iterator> SplitUses) {
assert(BeginOffset < EndOffset);
- uint64_t PartitionSize = EndOffset - BeginOffset;
+ uint64_t SliceSize = EndOffset - BeginOffset;
// Try to compute a friendly type for this partition of the alloca. This
// won't always succeed, in which case we fall back to a legal integer type
// or an i8 array of an appropriate size.
- Type *PartitionTy = 0;
+ Type *SliceTy = 0;
if (Type *CommonUseTy = findCommonType(B, E, EndOffset))
- if (DL->getTypeAllocSize(CommonUseTy) >= PartitionSize)
- PartitionTy = CommonUseTy;
- if (!PartitionTy)
+ if (DL->getTypeAllocSize(CommonUseTy) >= SliceSize)
+ SliceTy = CommonUseTy;
+ if (!SliceTy)
if (Type *TypePartitionTy = getTypePartition(*DL, AI.getAllocatedType(),
- BeginOffset, PartitionSize))
- PartitionTy = TypePartitionTy;
- if ((!PartitionTy || (PartitionTy->isArrayTy() &&
- PartitionTy->getArrayElementType()->isIntegerTy())) &&
- DL->isLegalInteger(PartitionSize * 8))
- PartitionTy = Type::getIntNTy(*C, PartitionSize * 8);
- if (!PartitionTy)
- PartitionTy = ArrayType::get(Type::getInt8Ty(*C), PartitionSize);
- assert(DL->getTypeAllocSize(PartitionTy) >= PartitionSize);
+ BeginOffset, SliceSize))
+ SliceTy = TypePartitionTy;
+ if ((!SliceTy || (SliceTy->isArrayTy() &&
+ SliceTy->getArrayElementType()->isIntegerTy())) &&
+ DL->isLegalInteger(SliceSize * 8))
+ SliceTy = Type::getIntNTy(*C, SliceSize * 8);
+ if (!SliceTy)
+ SliceTy = ArrayType::get(Type::getInt8Ty(*C), SliceSize);
+ assert(DL->getTypeAllocSize(SliceTy) >= SliceSize);
bool IsVectorPromotable = isVectorPromotionViable(
- *DL, PartitionTy, P, BeginOffset, EndOffset, B, E, SplitUses);
+ *DL, SliceTy, S, BeginOffset, EndOffset, B, E, SplitUses);
bool IsIntegerPromotable =
!IsVectorPromotable &&
- isIntegerWideningViable(*DL, PartitionTy, BeginOffset, P, B, E,
- SplitUses);
+ isIntegerWideningViable(*DL, SliceTy, BeginOffset, S, B, E, SplitUses);
// 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
// case, re-use the existing alloca, but still run through the rewriter to
// perform phi and select speculation.
AllocaInst *NewAI;
- if (PartitionTy == AI.getAllocatedType()) {
+ if (SliceTy == AI.getAllocatedType()) {
assert(BeginOffset == 0 &&
"Non-zero begin offset but same alloca type");
NewAI = &AI;
Alignment = MinAlign(Alignment, BeginOffset);
// If we will get at least this much alignment from the type alone, leave
// the alloca's alignment unconstrained.
- if (Alignment <= DL->getABITypeAlignment(PartitionTy))
+ if (Alignment <= DL->getABITypeAlignment(SliceTy))
Alignment = 0;
- NewAI = new AllocaInst(PartitionTy, 0, Alignment,
- AI.getName() + ".sroa." + Twine(B - P.begin()), &AI);
+ NewAI = new AllocaInst(SliceTy, 0, Alignment,
+ AI.getName() + ".sroa." + Twine(B - S.begin()), &AI);
++NumNewAllocas;
}
unsigned PPWOldSize = PostPromotionWorklist.size();
unsigned SPOldSize = SpeculatablePHIs.size();
unsigned SSOldSize = SpeculatableSelects.size();
+ unsigned NumUses = 0;
- AllocaPartitionRewriter Rewriter(*DL, P, *this, AI, *NewAI, BeginOffset,
- EndOffset, IsVectorPromotable,
- IsIntegerPromotable);
+ AllocaSliceRewriter Rewriter(*DL, S, *this, AI, *NewAI, BeginOffset,
+ EndOffset, IsVectorPromotable,
+ IsIntegerPromotable);
bool Promotable = true;
- for (ArrayRef<AllocaPartitioning::iterator>::const_iterator
- SUI = SplitUses.begin(),
- SUE = SplitUses.end();
+ for (ArrayRef<AllocaSlices::iterator>::const_iterator SUI = SplitUses.begin(),
+ SUE = SplitUses.end();
SUI != SUE; ++SUI) {
DEBUG(dbgs() << " rewriting split ");
- DEBUG(P.printPartition(dbgs(), *SUI, ""));
+ DEBUG(S.printSlice(dbgs(), *SUI, ""));
Promotable &= Rewriter.visit(*SUI);
+ ++NumUses;
}
- for (AllocaPartitioning::iterator I = B; I != E; ++I) {
+ for (AllocaSlices::iterator I = B; I != E; ++I) {
DEBUG(dbgs() << " rewriting ");
- DEBUG(P.printPartition(dbgs(), I, ""));
+ DEBUG(S.printSlice(dbgs(), I, ""));
Promotable &= Rewriter.visit(I);
+ ++NumUses;
}
- if (Promotable && (SpeculatablePHIs.size() > SPOldSize ||
- SpeculatableSelects.size() > SSOldSize)) {
- // If we have a promotable alloca except for some unspeculated loads below
- // PHIs or Selects, iterate once. We will speculate the loads and on the
- // next iteration rewrite them into a promotable form.
- Worklist.insert(NewAI);
- } else if (Promotable) {
+ NumAllocaPartitionUses += NumUses;
+ MaxUsesPerAllocaPartition =
+ std::max<unsigned>(NumUses, MaxUsesPerAllocaPartition);
+
+ if (Promotable && !Rewriter.isUsedByRewrittenSpeculatableInstructions()) {
DEBUG(dbgs() << " and queuing for promotion\n");
PromotableAllocas.push_back(NewAI);
- } else if (NewAI != &AI) {
+ } else if (NewAI != &AI ||
+ (Promotable &&
+ Rewriter.isUsedByRewrittenSpeculatableInstructions())) {
// If we can't promote the alloca, iterate on it to check for new
// refinements exposed by splitting the current alloca. Don't iterate on an
// alloca which didn't actually change and didn't get promoted.
+ //
+ // Alternatively, if we could promote the alloca but have speculatable
+ // instructions then we will speculate them after finishing our processing
+ // of the original alloca. Mark the new one for re-visiting in the next
+ // iteration so the speculated operations can be rewritten.
+ //
// FIXME: We should actually track whether the rewriter changed anything.
Worklist.insert(NewAI);
}
}
namespace {
- struct IsPartitionEndLessOrEqualTo {
- uint64_t UpperBound;
+struct IsSliceEndLessOrEqualTo {
+ uint64_t UpperBound;
- IsPartitionEndLessOrEqualTo(uint64_t UpperBound) : UpperBound(UpperBound) {}
+ IsSliceEndLessOrEqualTo(uint64_t UpperBound) : UpperBound(UpperBound) {}
- bool operator()(const AllocaPartitioning::iterator &I) {
- return I->endOffset() <= UpperBound;
- }
- };
+ bool operator()(const AllocaSlices::iterator &I) {
+ return I->endOffset() <= UpperBound;
+ }
+};
}
-static void removeFinishedSplitUses(
- SmallVectorImpl<AllocaPartitioning::iterator> &SplitUses,
- uint64_t &MaxSplitUseEndOffset, uint64_t Offset) {
+static void
+removeFinishedSplitUses(SmallVectorImpl<AllocaSlices::iterator> &SplitUses,
+ uint64_t &MaxSplitUseEndOffset, uint64_t Offset) {
if (Offset >= MaxSplitUseEndOffset) {
SplitUses.clear();
MaxSplitUseEndOffset = 0;
size_t SplitUsesOldSize = SplitUses.size();
SplitUses.erase(std::remove_if(SplitUses.begin(), SplitUses.end(),
- IsPartitionEndLessOrEqualTo(Offset)),
+ IsSliceEndLessOrEqualTo(Offset)),
SplitUses.end());
if (SplitUsesOldSize == SplitUses.size())
return;
// Recompute the max. While this is linear, so is remove_if.
MaxSplitUseEndOffset = 0;
- for (SmallVectorImpl<AllocaPartitioning::iterator>::iterator
+ for (SmallVectorImpl<AllocaSlices::iterator>::iterator
SUI = SplitUses.begin(),
SUE = SplitUses.end();
SUI != SUE; ++SUI)
MaxSplitUseEndOffset = std::max((*SUI)->endOffset(), MaxSplitUseEndOffset);
}
-/// \brief Walks the partitioning of an alloca rewriting uses of each partition.
-bool SROA::splitAlloca(AllocaInst &AI, AllocaPartitioning &P) {
- if (P.begin() == P.end())
+/// \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())
return false;
+ unsigned NumPartitions = 0;
bool Changed = false;
- SmallVector<AllocaPartitioning::iterator, 4> SplitUses;
+ SmallVector<AllocaSlices::iterator, 4> SplitUses;
uint64_t MaxSplitUseEndOffset = 0;
- uint64_t BeginOffset = P.begin()->beginOffset();
+ uint64_t BeginOffset = S.begin()->beginOffset();
- for (AllocaPartitioning::iterator PI = P.begin(), PJ = llvm::next(PI),
- PE = P.end();
- PI != PE; PI = PJ) {
- uint64_t MaxEndOffset = PI->endOffset();
+ for (AllocaSlices::iterator SI = S.begin(), SJ = llvm::next(SI), SE = S.end();
+ SI != SE; SI = SJ) {
+ uint64_t MaxEndOffset = SI->endOffset();
- if (!PI->isSplittable()) {
- // When we're forming an unsplittable region, it must always start at he
- // first partitioning use and will extend through its end.
- assert(BeginOffset == PI->beginOffset());
+ if (!SI->isSplittable()) {
+ // When we're forming an unsplittable region, it must always start at the
+ // first slice and will extend through its end.
+ assert(BeginOffset == SI->beginOffset());
- // Rewrite a partition including all of the overlapping uses with this
- // unsplittable partition.
- while (PJ != PE && PJ->beginOffset() < MaxEndOffset) {
- if (!PJ->isSplittable())
- MaxEndOffset = std::max(MaxEndOffset, PJ->endOffset());
- ++PJ;
+ // Form a partition including all of the overlapping slices with this
+ // unsplittable slice.
+ while (SJ != SE && SJ->beginOffset() < MaxEndOffset) {
+ if (!SJ->isSplittable())
+ MaxEndOffset = std::max(MaxEndOffset, SJ->endOffset());
+ ++SJ;
}
} else {
- assert(PI->isSplittable()); // Established above.
+ assert(SI->isSplittable()); // Established above.
- // Collect all of the overlapping splittable partitions.
- while (PJ != PE && PJ->beginOffset() < MaxEndOffset &&
- PJ->isSplittable()) {
- MaxEndOffset = std::max(MaxEndOffset, PJ->endOffset());
- ++PJ;
+ // Collect all of the overlapping splittable slices.
+ while (SJ != SE && SJ->beginOffset() < MaxEndOffset &&
+ SJ->isSplittable()) {
+ MaxEndOffset = std::max(MaxEndOffset, SJ->endOffset());
+ ++SJ;
}
- // Back up MaxEndOffset and PJ if we ended the span early when
- // encountering an unsplittable partition.
- if (PJ != PE && PJ->beginOffset() < MaxEndOffset) {
- assert(!PJ->isSplittable());
- MaxEndOffset = PJ->beginOffset();
+ // Back up MaxEndOffset and SJ if we ended the span early when
+ // encountering an unsplittable slice.
+ if (SJ != SE && SJ->beginOffset() < MaxEndOffset) {
+ assert(!SJ->isSplittable());
+ MaxEndOffset = SJ->beginOffset();
}
}
// Check if we have managed to move the end offset forward yet. If so,
// we'll have to rewrite uses and erase old split uses.
if (BeginOffset < MaxEndOffset) {
- // Rewrite a sequence of overlapping partition uses.
- Changed |= rewritePartitions(AI, P, PI, PJ, BeginOffset,
- MaxEndOffset, SplitUses);
+ // Rewrite a sequence of overlapping slices.
+ Changed |=
+ rewritePartition(AI, S, SI, SJ, BeginOffset, MaxEndOffset, SplitUses);
+ ++NumPartitions;
removeFinishedSplitUses(SplitUses, MaxSplitUseEndOffset, MaxEndOffset);
}
- // Accumulate all the splittable partitions from the [PI,PJ) region which
+ // Accumulate all the splittable slices from the [SI,SJ) region which
// overlap going forward.
- for (AllocaPartitioning::iterator PII = PI, PIE = PJ; PII != PIE; ++PII)
- if (PII->isSplittable() && PII->endOffset() > MaxEndOffset) {
- SplitUses.push_back(PII);
- MaxSplitUseEndOffset = std::max(PII->endOffset(), MaxSplitUseEndOffset);
+ for (AllocaSlices::iterator SK = SI; SK != SJ; ++SK)
+ if (SK->isSplittable() && SK->endOffset() > MaxEndOffset) {
+ SplitUses.push_back(SK);
+ MaxSplitUseEndOffset = std::max(SK->endOffset(), MaxSplitUseEndOffset);
}
// If we're already at the end and we have no split uses, we're done.
- if (PJ == PE && SplitUses.empty())
+ if (SJ == SE && SplitUses.empty())
break;
// If we have no split uses or no gap in offsets, we're ready to move to
- // the next partitioning use.
- if (SplitUses.empty() || (PJ != PE && MaxEndOffset == PJ->beginOffset())) {
- BeginOffset = PJ->beginOffset();
+ // the next slice.
+ if (SplitUses.empty() || (SJ != SE && MaxEndOffset == SJ->beginOffset())) {
+ BeginOffset = SJ->beginOffset();
continue;
}
- // Even if we have split uses, if the next partitioning use is splittable
- // and the split uses reach it, we can simply set up the beginning offset
- // to bridge between them.
- if (PJ != PE && PJ->isSplittable() && MaxSplitUseEndOffset > PJ->beginOffset()) {
+ // Even if we have split slices, if the next slice is splittable and the
+ // split slices reach it, we can simply set up the beginning offset of the
+ // next iteration to bridge between them.
+ if (SJ != SE && SJ->isSplittable() &&
+ MaxSplitUseEndOffset > SJ->beginOffset()) {
BeginOffset = MaxEndOffset;
continue;
}
- // Otherwise, we have a tail of split uses. Rewrite them with an empty
- // range of partitioning uses.
+ // Otherwise, we have a tail of split slices. Rewrite them with an empty
+ // range of slices.
uint64_t PostSplitEndOffset =
- PJ == PE ? MaxSplitUseEndOffset : PJ->beginOffset();
+ SJ == SE ? MaxSplitUseEndOffset : SJ->beginOffset();
- Changed |= rewritePartitions(AI, P, PJ, PJ, MaxEndOffset,
- PostSplitEndOffset, SplitUses);
- if (PJ == PE)
+ Changed |= rewritePartition(AI, S, SJ, SJ, MaxEndOffset, PostSplitEndOffset,
+ SplitUses);
+ ++NumPartitions;
+
+ if (SJ == SE)
break; // Skip the rest, we don't need to do any cleanup.
removeFinishedSplitUses(SplitUses, MaxSplitUseEndOffset,
PostSplitEndOffset);
// Now just reset the begin offset for the next iteration.
- BeginOffset = PJ->beginOffset();
+ BeginOffset = SJ->beginOffset();
}
+ NumAllocaPartitions += NumPartitions;
+ MaxPartitionsPerAlloca =
+ std::max<unsigned>(NumPartitions, MaxPartitionsPerAlloca);
+
return Changed;
}
/// \brief Analyze an alloca for SROA.
///
/// This analyzes the alloca to ensure we can reason about it, builds
-/// a partitioning of the alloca, and then hands it off to be split and
+/// the slices of the alloca, and then hands it off to be split and
/// rewritten as needed.
bool SROA::runOnAlloca(AllocaInst &AI) {
DEBUG(dbgs() << "SROA alloca: " << AI << "\n");
AggLoadStoreRewriter AggRewriter(*DL);
Changed |= AggRewriter.rewrite(AI);
- // Build the partition set using a recursive instruction-visiting builder.
- AllocaPartitioning P(*DL, AI);
- DEBUG(P.print(dbgs()));
- if (P.isEscaped())
+ // Build the slices using a recursive instruction-visiting builder.
+ AllocaSlices S(*DL, AI);
+ DEBUG(S.print(dbgs()));
+ if (S.isEscaped())
return Changed;
// Delete all the dead users of this alloca before splitting and rewriting it.
- for (AllocaPartitioning::dead_user_iterator DI = P.dead_user_begin(),
- DE = P.dead_user_end();
+ for (AllocaSlices::dead_user_iterator DI = S.dead_user_begin(),
+ DE = S.dead_user_end();
DI != DE; ++DI) {
Changed = true;
(*DI)->replaceAllUsesWith(UndefValue::get((*DI)->getType()));
DeadInsts.insert(*DI);
}
- for (AllocaPartitioning::dead_op_iterator DO = P.dead_op_begin(),
- DE = P.dead_op_end();
+ for (AllocaSlices::dead_op_iterator DO = S.dead_op_begin(),
+ DE = S.dead_op_end();
DO != DE; ++DO) {
Value *OldV = **DO;
// Clobber the use with an undef value.
}
}
- // No partitions to split. Leave the dead alloca for a later pass to clean up.
- if (P.begin() == P.end())
+ // No slices to split. Leave the dead alloca for a later pass to clean up.
+ if (S.begin() == S.end())
return Changed;
- Changed |= splitAlloca(AI, P);
+ Changed |= splitAlloca(AI, S);
DEBUG(dbgs() << " Speculating PHIs\n");
while (!SpeculatablePHIs.empty())
}
}
+static void enqueueUsersInWorklist(Instruction &I,
+ SmallVectorImpl<Instruction *> &Worklist,
+ SmallPtrSet<Instruction *, 8> &Visited) {
+ for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE;
+ ++UI)
+ if (Visited.insert(cast<Instruction>(*UI)))
+ Worklist.push_back(cast<Instruction>(*UI));
+}
+
/// \brief Promote the allocas, using the best available technique.
///
/// This attempts to promote whatever allocas have been identified as viable in
DEBUG(dbgs() << "Promoting allocas with SSAUpdater...\n");
SSAUpdater SSA;
DIBuilder DIB(*F.getParent());
- SmallVector<Instruction*, 64> Insts;
+ SmallVector<Instruction *, 64> Insts;
+
+ // We need a worklist to walk the uses of each alloca.
+ SmallVector<Instruction *, 8> Worklist;
+ SmallPtrSet<Instruction *, 8> Visited;
+ SmallVector<Instruction *, 32> DeadInsts;
for (unsigned Idx = 0, Size = PromotableAllocas.size(); Idx != Size; ++Idx) {
AllocaInst *AI = PromotableAllocas[Idx];
- for (Value::use_iterator UI = AI->use_begin(), UE = AI->use_end();
- UI != UE;) {
- Instruction *I = cast<Instruction>(*UI++);
+ Insts.clear();
+ Worklist.clear();
+ Visited.clear();
+
+ enqueueUsersInWorklist(*AI, Worklist, Visited);
+
+ while (!Worklist.empty()) {
+ Instruction *I = Worklist.pop_back_val();
+
// FIXME: Currently the SSAUpdater infrastructure doesn't reason about
// lifetime intrinsics and so we strip them (and the bitcasts+GEPs
// leading to them) here. Eventually it should use them to optimize the
// scalar values produced.
- if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I)) {
- assert(onlyUsedByLifetimeMarkers(I) &&
- "Found a bitcast used outside of a lifetime marker.");
- while (!I->use_empty())
- cast<Instruction>(*I->use_begin())->eraseFromParent();
- I->eraseFromParent();
- continue;
- }
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
assert(II->getIntrinsicID() == Intrinsic::lifetime_start ||
II->getIntrinsicID() == Intrinsic::lifetime_end);
continue;
}
- Insts.push_back(I);
+ // Push the loads and stores we find onto the list. SROA will already
+ // have validated that all loads and stores are viable candidates for
+ // promotion.
+ if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
+ assert(LI->getType() == AI->getAllocatedType());
+ Insts.push_back(LI);
+ continue;
+ }
+ if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
+ assert(SI->getValueOperand()->getType() == AI->getAllocatedType());
+ Insts.push_back(SI);
+ continue;
+ }
+
+ // For everything else, we know that only no-op bitcasts and GEPs will
+ // make it this far, just recurse through them and recall them for later
+ // removal.
+ DeadInsts.push_back(I);
+ enqueueUsersInWorklist(*I, Worklist, Visited);
}
AllocaPromoter(Insts, SSA, *AI, DIB).run(Insts);
- Insts.clear();
+ while (!DeadInsts.empty())
+ DeadInsts.pop_back_val()->eraseFromParent();
+ AI->eraseFromParent();
}
PromotableAllocas.clear();
projects / oota-llvm.git / blobdiff