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");
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
}
};
-namespace {
-struct IsSliceDead {
- bool operator()(const Slice &S) { return S.isDead(); }
-};
-}
-
AllocaSlices::AllocaSlices(const DataLayout &DL, AllocaInst &AI)
:
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
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(Slices.begin(), Slices.end());
-
- Slices.erase(std::remove_if(Slices.begin(), Slices.end(), IsSliceDead()),
- Slices.end());
-
- // Record how many slices we end up with.
- NumAllocaPartitions += Slices.size();
- MaxPartitionsPerAlloca =
- std::max<unsigned>(Slices.size(), MaxPartitionsPerAlloca);
-
- NumAllocaPartitionUses += Slices.size();
- MaxPartitionUsesPerAlloca =
- std::max<unsigned>(Slices.size(), MaxPartitionUsesPerAlloca);
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
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;
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");
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;
// 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);
+ Pass.Worklist.insert(&NewAI);
+ 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);
+ Pass.Worklist.insert(&NewAI);
+ IsUsedByRewrittenSpeculatableInstructions = true;
return true;
}
unsigned SPOldSize = SpeculatablePHIs.size();
unsigned SSOldSize = SpeculatableSelects.size();
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
+ unsigned NumUses = 0;
+#endif
+
AllocaSliceRewriter Rewriter(*DL, S, *this, AI, *NewAI, BeginOffset,
EndOffset, IsVectorPromotable,
IsIntegerPromotable);
DEBUG(dbgs() << " rewriting split ");
DEBUG(S.printSlice(dbgs(), *SUI, ""));
Promotable &= Rewriter.visit(*SUI);
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
+ ++NumUses;
+#endif
}
for (AllocaSlices::iterator I = B; I != E; ++I) {
DEBUG(dbgs() << " rewriting ");
DEBUG(S.printSlice(dbgs(), I, ""));
Promotable &= Rewriter.visit(I);
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
+ ++NumUses;
+#endif
}
- 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) {
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
+ NumAllocaPartitionUses += NumUses;
+ MaxUsesPerAllocaPartition =
+ std::max<unsigned>(NumUses, MaxUsesPerAllocaPartition);
+#endif
+
+ if (Promotable && !Rewriter.isUsedByRewrittenSpeculatableInstructions()) {
DEBUG(dbgs() << " and queuing for promotion\n");
PromotableAllocas.push_back(NewAI);
} else if (NewAI != &AI) {
if (S.begin() == S.end())
return false;
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
+ unsigned NumPartitions = 0;
+#endif
+
bool Changed = false;
SmallVector<AllocaSlices::iterator, 4> SplitUses;
uint64_t MaxSplitUseEndOffset = 0;
// Rewrite a sequence of overlapping slices.
Changed |=
rewritePartition(AI, S, SI, SJ, BeginOffset, MaxEndOffset, SplitUses);
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
+ ++NumPartitions;
+#endif
removeFinishedSplitUses(SplitUses, MaxSplitUseEndOffset, MaxEndOffset);
}
Changed |= rewritePartition(AI, S, SJ, SJ, MaxEndOffset, PostSplitEndOffset,
SplitUses);
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
+ ++NumPartitions;
+#endif
+
if (SJ == SE)
break; // Skip the rest, we don't need to do any cleanup.
BeginOffset = SJ->beginOffset();
}
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
+ NumAllocaPartitions += NumPartitions;
+ MaxPartitionsPerAlloca =
+ std::max<unsigned>(NumPartitions, MaxPartitionsPerAlloca);
+#endif
+
return Changed;
}