From 667d787c0a21cf3f5dfcde03ca471162ba35b614 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Fri, 26 Jun 2009 22:53:46 +0000 Subject: [PATCH] Incorporate the insertion point into the key of SCEVExpander's CSE map. This helps it avoid reusing an instruction that doesn't dominate all of the users, in cases where the original instruction was inserted before all of the users were known. This may result in redundant expansions of sub-expressions that depend on loop-unpredictable values in some cases, however this isn't very common, and it primarily impacts IndVarSimplify, so GVN can be expected to clean these up. This eliminates the need for IndVarSimplify's FixUsesBeforeDefs, which fixes several bugs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74352 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../llvm/Analysis/ScalarEvolutionExpander.h | 48 ++--- lib/Analysis/ScalarEvolutionExpander.cpp | 33 ++-- lib/Transforms/Scalar/IndVarSimplify.cpp | 164 +++++------------- 3 files changed, 78 insertions(+), 167 deletions(-) diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 730c97fff4d..90dba8bcc04 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -28,7 +28,8 @@ namespace llvm { /// memory. struct SCEVExpander : public SCEVVisitor { ScalarEvolution &SE; - std::map > InsertedExpressions; + std::map, AssertingVH > + InsertedExpressions; std::set InsertedValues; BasicBlock::iterator InsertPt; @@ -43,48 +44,18 @@ namespace llvm { /// different places within the same BasicBlock can do so. void clear() { InsertedExpressions.clear(); } - /// isInsertedInstruction - Return true if the specified instruction was - /// inserted by the code rewriter. If so, the client should not modify the - /// instruction. - bool isInsertedInstruction(Instruction *I) const { - return InsertedValues.count(I); - } - - /// isInsertedExpression - Return true if the the code rewriter has a - /// Value* recorded for the given expression. - bool isInsertedExpression(const SCEV *S) const { - return InsertedExpressions.count(S); - } - /// getOrInsertCanonicalInductionVariable - This method returns the /// canonical induction variable of the specified type for the specified /// loop (inserting one if there is none). A canonical induction variable /// starts at zero and steps by one on each iteration. Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty); - /// addInsertedValue - Remember the specified instruction as being the - /// canonical form for the specified SCEV. - void addInsertedValue(Value *V, const SCEV *S) { - InsertedExpressions[S] = V; - InsertedValues.insert(V); - } - - void setInsertionPoint(BasicBlock::iterator NewIP) { InsertPt = NewIP; } - - BasicBlock::iterator getInsertionPoint() const { return InsertPt; } - - /// expandCodeFor - Insert code to directly compute the specified SCEV - /// expression into the program. The inserted code is inserted into the - /// SCEVExpander's current insertion point. If a type is specified, the - /// result will be expanded to have that type, with a cast if necessary. - Value *expandCodeFor(const SCEV* SH, const Type *Ty = 0); - /// expandCodeFor - Insert code to directly compute the specified SCEV /// expression into the program. The inserted code is inserted into the /// specified block. Value *expandCodeFor(const SCEV* SH, const Type *Ty, BasicBlock::iterator IP) { - setInsertionPoint(IP); + InsertPt = IP; return expandCodeFor(SH, Ty); } @@ -111,6 +82,19 @@ namespace llvm { Value *expand(const SCEV *S); + /// expandCodeFor - Insert code to directly compute the specified SCEV + /// expression into the program. The inserted code is inserted into the + /// SCEVExpander's current insertion point. If a type is specified, the + /// result will be expanded to have that type, with a cast if necessary. + Value *expandCodeFor(const SCEV* SH, const Type *Ty = 0); + + /// isInsertedInstruction - Return true if the specified instruction was + /// inserted by the code rewriter. If so, the client should not modify the + /// instruction. + bool isInsertedInstruction(Instruction *I) const { + return InsertedValues.count(I); + } + Value *visitConstant(const SCEVConstant *S) { return S->getValue(); } diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index 6d7abc02ebe..4cc5ebc2953 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -468,13 +468,13 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { const SCEV* Step = SE.getAnyExtendExpr(S->getStepRecurrence(SE), CanonicalIV->getType()); Value *V = expand(SE.getAddRecExpr(Start, Step, S->getLoop())); - BasicBlock::iterator SaveInsertPt = getInsertionPoint(); + BasicBlock::iterator SaveInsertPt = InsertPt; BasicBlock::iterator NewInsertPt = next(BasicBlock::iterator(cast(V))); while (isa(NewInsertPt)) ++NewInsertPt; V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), 0, NewInsertPt); - setInsertionPoint(SaveInsertPt); + InsertPt = SaveInsertPt; return V; } @@ -652,16 +652,10 @@ Value *SCEVExpander::expandCodeFor(const SCEV* SH, const Type *Ty) { } Value *SCEVExpander::expand(const SCEV *S) { - // Check to see if we already expanded this. - std::map >::iterator I = - InsertedExpressions.find(S); - if (I != InsertedExpressions.end()) - return I->second; + BasicBlock::iterator SaveInsertPt = InsertPt; // Compute an insertion point for this SCEV object. Hoist the instructions // as far out in the loop nest as possible. - BasicBlock::iterator InsertPt = getInsertionPoint(); - BasicBlock::iterator SaveInsertPt = InsertPt; for (Loop *L = SE.LI->getLoopFor(InsertPt->getParent()); ; L = L->getParentLoop()) if (S->isLoopInvariant(L)) { @@ -677,12 +671,23 @@ Value *SCEVExpander::expand(const SCEV *S) { while (isInsertedInstruction(InsertPt)) ++InsertPt; break; } - setInsertionPoint(InsertPt); + // Check to see if we already expanded this here. + std::map, + AssertingVH >::iterator I = + InsertedExpressions.find(std::make_pair(S, InsertPt)); + if (I != InsertedExpressions.end()) { + InsertPt = SaveInsertPt; + return I->second; + } + + // Expand the expression into instructions. Value *V = visit(S); - setInsertionPoint(SaveInsertPt); - InsertedExpressions[S] = V; + // Remember the expanded value for this SCEV at this location. + InsertedExpressions[std::make_pair(S, InsertPt)] = V; + + InsertPt = SaveInsertPt; return V; } @@ -696,8 +701,8 @@ SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, assert(Ty->isInteger() && "Can only insert integer induction variables!"); const SCEV* H = SE.getAddRecExpr(SE.getIntegerSCEV(0, Ty), SE.getIntegerSCEV(1, Ty), L); - BasicBlock::iterator SaveInsertPt = getInsertionPoint(); + BasicBlock::iterator SaveInsertPt = InsertPt; Value *V = expandCodeFor(H, 0, L->getHeader()->begin()); - setInsertionPoint(SaveInsertPt); + InsertPt = SaveInsertPt; return V; } diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index ec4be9b905d..d2ba25637e0 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -101,15 +101,13 @@ namespace { BasicBlock *ExitingBlock, BranchInst *BI, SCEVExpander &Rewriter); - void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount); + void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount, + SCEVExpander &Rewriter); void RewriteIVExpressions(Loop *L, const Type *LargestType, - SCEVExpander &Rewriter, - BasicBlock::iterator InsertPt); + SCEVExpander &Rewriter); - void SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter); - - void FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter); + void SinkUnusedInvariants(Loop *L); void HandleFloatingPointIV(Loop *L, PHINode *PH); }; @@ -170,12 +168,10 @@ ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L, CmpIndVar = IndVar; } - // Expand the code for the iteration count into the preheader of the loop. + // Expand the code for the iteration count. assert(RHS->isLoopInvariant(L) && "Computed iteration count is not loop invariant!"); - BasicBlock *Preheader = L->getLoopPreheader(); - Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), - Preheader->getTerminator()); + Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), BI); // Insert a new icmp_ne or icmp_eq instruction before the branch. ICmpInst::Predicate Opcode; @@ -217,31 +213,13 @@ ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L, /// able to brute-force evaluate arbitrary instructions as long as they have /// constant operands at the beginning of the loop. void IndVarSimplify::RewriteLoopExitValues(Loop *L, - const SCEV *BackedgeTakenCount) { + const SCEV *BackedgeTakenCount, + SCEVExpander &Rewriter) { // Verify the input to the pass in already in LCSSA form. assert(L->isLCSSAForm()); - BasicBlock *Preheader = L->getLoopPreheader(); - - // Scan all of the instructions in the loop, looking at those that have - // extra-loop users and which are recurrences. - SCEVExpander Rewriter(*SE); - - // We insert the code into the preheader of the loop if the loop contains - // multiple exit blocks, or in the exit block if there is exactly one. - BasicBlock *BlockToInsertInto; - BasicBlock::iterator InsertPt; SmallVector ExitBlocks; L->getUniqueExitBlocks(ExitBlocks); - if (ExitBlocks.size() == 1) { - BlockToInsertInto = ExitBlocks[0]; - InsertPt = BlockToInsertInto->getFirstNonPHI(); - } else { - BlockToInsertInto = Preheader; - InsertPt = BlockToInsertInto->getTerminator(); - } - - std::map ExitValues; // Find all values that are computed inside the loop, but used outside of it. // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan @@ -291,11 +269,7 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L, Changed = true; ++NumReplaced; - // See if we already computed the exit value for the instruction, if so, - // just reuse it. - Value *&ExitVal = ExitValues[Inst]; - if (!ExitVal) - ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), InsertPt); + Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst); DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << " LoopVal = " << *Inst << "\n"; @@ -315,6 +289,15 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L, break; } } + if (ExitBlocks.size() != 1) { + // Clone the PHI and delete the original one. This lets IVUsers and + // any other maps purge the original user from their records. + PHINode *NewPN = PN->clone(); + NewPN->takeName(PN); + NewPN->insertBefore(PN); + PN->replaceAllUsesWith(NewPN); + PN->eraseFromParent(); + } } } } @@ -352,10 +335,12 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { // transform them to use integer recurrences. RewriteNonIntegerIVs(L); - BasicBlock *Header = L->getHeader(); BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null const SCEV* BackedgeTakenCount = SE->getBackedgeTakenCount(L); + // Create a rewriter object which we'll use to transform the code with. + SCEVExpander Rewriter(*SE); + // Check to see if this loop has a computable loop-invariant execution count. // If so, this means that we can compute the final value of any expressions // that are recurrent in the loop, and substitute the exit values from the @@ -363,7 +348,7 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { // the current expressions. // if (!isa(BackedgeTakenCount)) - RewriteLoopExitValues(L, BackedgeTakenCount); + RewriteLoopExitValues(L, BackedgeTakenCount, Rewriter); // Compute the type of the largest recurrence expression, and decide whether // a canonical induction variable should be inserted. @@ -394,9 +379,6 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { NeedCannIV = true; } - // Create a rewriter object which we'll use to transform the code with. - SCEVExpander Rewriter(*SE); - // Now that we know the largest of of the induction variable expressions // in this loop, insert a canonical induction variable of the largest size. Value *IndVar = 0; @@ -414,7 +396,7 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { OldCannIV = 0; } - IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType); + IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType); ++NumInserted; Changed = true; @@ -440,20 +422,14 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { ExitingBlock, BI, Rewriter); } - BasicBlock::iterator InsertPt = Header->getFirstNonPHI(); - // Rewrite IV-derived expressions. Clears the rewriter cache. - RewriteIVExpressions(L, LargestType, Rewriter, InsertPt); + RewriteIVExpressions(L, LargestType, Rewriter); - // The Rewriter may only be used for isInsertedInstruction queries from this - // point on. + // The Rewriter may not be used from this point on. // Loop-invariant instructions in the preheader that aren't used in the // loop may be sunk below the loop to reduce register pressure. - SinkUnusedInvariants(L, Rewriter); - - // Reorder instructions to avoid use-before-def conditions. - FixUsesBeforeDefs(L, Rewriter); + SinkUnusedInvariants(L); // For completeness, inform IVUsers of the IV use in the newly-created // loop exit test instruction. @@ -468,8 +444,7 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { } void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType, - SCEVExpander &Rewriter, - BasicBlock::iterator InsertPt) { + SCEVExpander &Rewriter) { SmallVector DeadInsts; // Rewrite all induction variable expressions in terms of the canonical @@ -504,6 +479,14 @@ void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType, if (!AR->isLoopInvariant(L) && !Stride->isLoopInvariant(L)) continue; + Instruction *InsertPt = User; + if (PHINode *PHI = dyn_cast(InsertPt)) + for (unsigned i = 0; ; ++i) + if (PHI->getIncomingValue(i) == Op) { + InsertPt = PHI->getIncomingBlock(i)->getTerminator(); + break; + } + // Now expand it into actual Instructions and patch it into place. Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt); @@ -538,19 +521,20 @@ void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType, /// If there's a single exit block, sink any loop-invariant values that /// were defined in the preheader but not used inside the loop into the /// exit block to reduce register pressure in the loop. -void IndVarSimplify::SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter) { +void IndVarSimplify::SinkUnusedInvariants(Loop *L) { BasicBlock *ExitBlock = L->getExitBlock(); if (!ExitBlock) return; - Instruction *NonPHI = ExitBlock->getFirstNonPHI(); + Instruction *InsertPt = ExitBlock->getFirstNonPHI(); BasicBlock *Preheader = L->getLoopPreheader(); BasicBlock::iterator I = Preheader->getTerminator(); while (I != Preheader->begin()) { --I; - // New instructions were inserted at the end of the preheader. Only - // consider those new instructions. - if (!Rewriter.isInsertedInstruction(I)) + // New instructions were inserted at the end of the preheader. + if (isa(I)) break; + if (I->isTrapping()) + continue; // Determine if there is a use in or before the loop (direct or // otherwise). bool UsedInLoop = false; @@ -577,75 +561,13 @@ void IndVarSimplify::SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter) { --I; else Done = true; - ToMove->moveBefore(NonPHI); + ToMove->moveBefore(InsertPt); if (Done) break; + InsertPt = ToMove; } } -/// Re-schedule the inserted instructions to put defs before uses. This -/// fixes problems that arrise when SCEV expressions contain loop-variant -/// values unrelated to the induction variable which are defined inside the -/// loop. FIXME: It would be better to insert instructions in the right -/// place so that this step isn't needed. -void IndVarSimplify::FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter) { - // Visit all the blocks in the loop in pre-order dom-tree dfs order. - DominatorTree *DT = &getAnalysis(); - std::map NumPredsLeft; - SmallVector Worklist; - Worklist.push_back(DT->getNode(L->getHeader())); - do { - DomTreeNode *Node = Worklist.pop_back_val(); - for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I) - if (L->contains((*I)->getBlock())) - Worklist.push_back(*I); - BasicBlock *BB = Node->getBlock(); - // Visit all the instructions in the block top down. - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { - // Count the number of operands that aren't properly dominating. - unsigned NumPreds = 0; - if (Rewriter.isInsertedInstruction(I) && !isa(I)) - for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); - OI != OE; ++OI) - if (Instruction *Inst = dyn_cast(OI)) - if (L->contains(Inst->getParent()) && !NumPredsLeft.count(Inst)) - ++NumPreds; - NumPredsLeft[I] = NumPreds; - // Notify uses of the position of this instruction, and move the - // users (and their dependents, recursively) into place after this - // instruction if it is their last outstanding operand. - for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); - UI != UE; ++UI) { - Instruction *Inst = cast(UI); - std::map::iterator Z = NumPredsLeft.find(Inst); - if (Z != NumPredsLeft.end() && Z->second != 0 && --Z->second == 0) { - SmallVector UseWorkList; - UseWorkList.push_back(Inst); - BasicBlock::iterator InsertPt = I; - if (InvokeInst *II = dyn_cast(InsertPt)) - InsertPt = II->getNormalDest()->begin(); - else - ++InsertPt; - while (isa(InsertPt)) ++InsertPt; - do { - Instruction *Use = UseWorkList.pop_back_val(); - Use->moveBefore(InsertPt); - NumPredsLeft.erase(Use); - for (Value::use_iterator IUI = Use->use_begin(), - IUE = Use->use_end(); IUI != IUE; ++IUI) { - Instruction *IUIInst = cast(IUI); - if (L->contains(IUIInst->getParent()) && - Rewriter.isInsertedInstruction(IUIInst) && - !isa(IUIInst)) - UseWorkList.push_back(IUIInst); - } - } while (!UseWorkList.empty()); - } - } - } - } while (!Worklist.empty()); -} - /// Return true if it is OK to use SIToFPInst for an inducation variable /// with given inital and exit values. static bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV, -- 2.34.1