From b2d98c29170d99fb43de0244a7f4f93a8893c208 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Thu, 4 Oct 2012 12:33:50 +0000 Subject: [PATCH] Fix PR13969, a mini-phase-ordering issue with the new SROA pass. Currently, we re-visit allocas when something changes about the way they might be *split* to allow better scalarization to take place. However, we weren't handling the case when the *promotion* is what would change the behavior of SROA. When an address derived from an alloca is stored into another alloca, we consider the first to have escaped. If the second is ever promoted to an SSA value, we will suddenly be able to run the SROA pass on the first alloca. This patch adds explicit support for this form if iteration. When we detect a store of a pointer derived from an alloca, we flag the underlying alloca for reprocessing after promotion. The logic works hard to only do this when there is definitely going to be promotion and it might remove impediments to the analysis of the alloca. Thanks to Nick for the great test case and Benjamin for some sanity check review. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165223 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/SROA.cpp | 73 +++++++++++++++++++++---------- test/Transforms/SROA/basictest.ll | 24 ++++++++++ 2 files changed, 74 insertions(+), 23 deletions(-) diff --git a/lib/Transforms/Scalar/SROA.cpp b/lib/Transforms/Scalar/SROA.cpp index 11b8d2e0215..54a08e68e77 100644 --- a/lib/Transforms/Scalar/SROA.cpp +++ b/lib/Transforms/Scalar/SROA.cpp @@ -1316,6 +1316,16 @@ class SROA : public FunctionPass { /// uses as dead. Only used to guard insertion into DeadInsts. SmallPtrSet DeadSplitInsts; + /// \brief Post-promotion worklist. + /// + /// Sometimes we discover an alloca which has a high probability of becoming + /// viable for SROA after a round of promotion takes place. In those cases, + /// the alloca is enqueued here for re-processing. + /// + /// Note that we have to be very careful to clear allocas out of this list in + /// the event they are deleted. + SetVector > PostPromotionWorklist; + /// \brief A collection of alloca instructions we can directly promote. std::vector PromotableAllocas; @@ -2379,6 +2389,13 @@ private: if (IntPromotionTy) return rewriteIntegerStore(IRB, SI); + // Strip all inbounds GEPs and pointer casts to try to dig out any root + // alloca that should be re-examined after promoting this alloca. + if (SI.getValueOperand()->getType()->isPointerTy()) + if (AllocaInst *AI = dyn_cast(SI.getValueOperand() + ->stripInBoundsOffsets())) + Pass.PostPromotionWorklist.insert(AI); + Value *NewPtr = getAdjustedAllocaPtr(IRB, SI.getPointerOperand()->getType()); SI.setOperand(1, NewPtr); @@ -3119,11 +3136,16 @@ bool SROA::rewriteAllocaPartition(AllocaInst &AI, << "[" << PI->BeginOffset << "," << PI->EndOffset << ") to: " << *NewAI << "\n"); + // Track the high watermark of the post-promotion worklist. We will reset it + // to this point if the alloca is not in fact scheduled for promotion. + unsigned PPWOldSize = PostPromotionWorklist.size(); + AllocaPartitionRewriter Rewriter(*TD, P, PI, *this, AI, *NewAI, PI->BeginOffset, PI->EndOffset); DEBUG(dbgs() << " rewriting "); DEBUG(P.print(dbgs(), PI, "")); - if (Rewriter.visitUsers(P.use_begin(PI), P.use_end(PI))) { + bool Promotable = Rewriter.visitUsers(P.use_begin(PI), P.use_end(PI)); + if (Promotable) { DEBUG(dbgs() << " and queuing for promotion\n"); PromotableAllocas.push_back(NewAI); } else if (NewAI != &AI) { @@ -3132,6 +3154,12 @@ bool SROA::rewriteAllocaPartition(AllocaInst &AI, // alloca which didn't actually change and didn't get promoted. Worklist.insert(NewAI); } + + // Drop any post-promotion work items if promotion didn't happen. + if (!Promotable) + while (PostPromotionWorklist.size() > PPWOldSize) + PostPromotionWorklist.pop_back(); + return true; } @@ -3165,13 +3193,6 @@ bool SROA::runOnAlloca(AllocaInst &AI) { TD->getTypeAllocSize(AI.getAllocatedType()) == 0) return false; - // First check if this is a non-aggregate type that we should simply promote. - if (!AI.getAllocatedType()->isAggregateType() && isAllocaPromotable(&AI)) { - DEBUG(dbgs() << " Trivially scalar type, queuing for promotion...\n"); - PromotableAllocas.push_back(&AI); - return false; - } - bool Changed = false; // First, split any FCA loads and stores touching this alloca to promote @@ -3339,23 +3360,29 @@ bool SROA::runOnFunction(Function &F) { // the list of promotable allocas. SmallPtrSet DeletedAllocas; - while (!Worklist.empty()) { - Changed |= runOnAlloca(*Worklist.pop_back_val()); - deleteDeadInstructions(DeletedAllocas); - - // Remove the deleted allocas from various lists so that we don't try to - // continue processing them. - if (!DeletedAllocas.empty()) { - Worklist.remove_if(IsAllocaInSet(DeletedAllocas)); - PromotableAllocas.erase(std::remove_if(PromotableAllocas.begin(), - PromotableAllocas.end(), - IsAllocaInSet(DeletedAllocas)), - PromotableAllocas.end()); - DeletedAllocas.clear(); + do { + while (!Worklist.empty()) { + Changed |= runOnAlloca(*Worklist.pop_back_val()); + deleteDeadInstructions(DeletedAllocas); + + // Remove the deleted allocas from various lists so that we don't try to + // continue processing them. + if (!DeletedAllocas.empty()) { + Worklist.remove_if(IsAllocaInSet(DeletedAllocas)); + PostPromotionWorklist.remove_if(IsAllocaInSet(DeletedAllocas)); + PromotableAllocas.erase(std::remove_if(PromotableAllocas.begin(), + PromotableAllocas.end(), + IsAllocaInSet(DeletedAllocas)), + PromotableAllocas.end()); + DeletedAllocas.clear(); + } } - } - Changed |= promoteAllocas(F); + Changed |= promoteAllocas(F); + + Worklist = PostPromotionWorklist; + PostPromotionWorklist.clear(); + } while (!Worklist.empty()); return Changed; } diff --git a/test/Transforms/SROA/basictest.ll b/test/Transforms/SROA/basictest.ll index b6d08ba8c8a..a58eb4786cd 100644 --- a/test/Transforms/SROA/basictest.ll +++ b/test/Transforms/SROA/basictest.ll @@ -926,3 +926,27 @@ bb3: bb4: unreachable } + +define double @PR13969(double %x) { +; Check that we detect when promotion will un-escape an alloca and iterate to +; re-try running SROA over that alloca. Without that, the two allocas that are +; stored into a dead alloca don't get rewritten and promoted. +; CHECK: @PR13969 + +entry: + %a = alloca double + %b = alloca double* + %c = alloca double +; CHECK-NOT: alloca + + store double %x, double* %a + store double* %c, double** %b + store double* %a, double** %b + store double %x, double* %c + %ret = load double* %a +; CHECK-NOT: store +; CHECK-NOT: load + + ret double %ret +; CHECK: ret double %x +} -- 2.34.1