From 204494149b6f846e8f173f525b129f5508076049 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Tue, 11 Oct 2011 02:28:51 +0000 Subject: [PATCH] Move replaceCongruentIVs into SCEVExapander and bias toward "expanded" IVs. Indvars previously chose randomly between congruent IVs. Now it will bias the decision toward IVs that SCEVExpander likes to create. This was not done to fix any problem, it's just a welcome side effect of factoring code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141633 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../llvm/Analysis/ScalarEvolutionExpander.h | 23 +++- lib/Analysis/ScalarEvolutionExpander.cpp | 100 ++++++++++++++++++ lib/Transforms/Scalar/IndVarSimplify.cpp | 93 ++-------------- .../IndVarSimplify/no-iv-rewrite.ll | 1 + 4 files changed, 129 insertions(+), 88 deletions(-) diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index f7bab308367..1080580c960 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -72,6 +72,10 @@ namespace llvm { typedef IRBuilder BuilderType; BuilderType Builder; +#ifndef NDEBUG + const char *DebugType; +#endif + friend struct SCEVVisitor; public: @@ -79,7 +83,15 @@ namespace llvm { explicit SCEVExpander(ScalarEvolution &se, const char *name) : SE(se), IVName(name), IVIncInsertLoop(0), IVIncInsertPos(0), CanonicalMode(true), LSRMode(false), - Builder(se.getContext(), TargetFolder(se.TD)) {} + Builder(se.getContext(), TargetFolder(se.TD)) { +#ifndef NDEBUG + DebugType = ""; +#endif + } + +#ifndef NDEBUG + void setDebugType(const char* s) { DebugType = s; } +#endif /// clear - Erase the contents of the InsertedExpressions map so that users /// trying to expand the same expression into multiple BasicBlocks or @@ -96,6 +108,15 @@ namespace llvm { /// starts at zero and steps by one on each iteration. PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty); + /// hoistStep - Utility for hoisting an IV increment. + static bool hoistStep(Instruction *IncV, Instruction *InsertPos, + const DominatorTree *DT); + + /// replaceCongruentIVs - replace congruent phis with their most canonical + /// representative. Return the number of phis eliminated. + unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, + SmallVectorImpl &DeadInsts); + /// expandCodeFor - Insert code to directly compute the specified SCEV /// expression into the program. The inserted code is inserted into the /// specified block. diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index d0825b7eb52..81f4db1c7d2 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -1465,3 +1465,103 @@ SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, return V; } + +/// hoistStep - Attempt to hoist an IV increment above a potential use. +/// +/// To successfully hoist, two criteria must be met: +/// - IncV operands dominate InsertPos and +/// - InsertPos dominates IncV +/// +/// Meeting the second condition means that we don't need to check all of IncV's +/// existing uses (it's moving up in the domtree). +/// +/// This does not yet recursively hoist the operands, although that would +/// not be difficult. +/// +/// This does not require a SCEVExpander instance and could be replaced by a +/// general code-insertion helper. +bool SCEVExpander::hoistStep(Instruction *IncV, Instruction *InsertPos, + const DominatorTree *DT) { + if (DT->dominates(IncV, InsertPos)) + return true; + + if (!DT->dominates(InsertPos->getParent(), IncV->getParent())) + return false; + + if (IncV->mayHaveSideEffects()) + return false; + + // Attempt to hoist IncV + for (User::op_iterator OI = IncV->op_begin(), OE = IncV->op_end(); + OI != OE; ++OI) { + Instruction *OInst = dyn_cast(OI); + if (OInst && !DT->dominates(OInst, InsertPos)) + return false; + } + IncV->moveBefore(InsertPos); + return true; +} + +/// replaceCongruentIVs - Check for congruent phis in this loop header and +/// replace them with their most canonical representative. Return the number of +/// phis eliminated. +/// +/// This does not depend on any SCEVExpander state but should be used in +/// the same context that SCEVExpander is used. +unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT, + SmallVectorImpl &DeadInsts) { + unsigned NumElim = 0; + DenseMap ExprToIVMap; + for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) { + PHINode *Phi = cast(I); + if (!SE.isSCEVable(Phi->getType())) + continue; + + PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)]; + if (!OrigPhiRef) { + OrigPhiRef = Phi; + continue; + } + + // If one phi derives from the other via GEPs, types may differ. + // We could consider adding a bitcast here to handle it. + if (OrigPhiRef->getType() != Phi->getType()) + continue; + + if (BasicBlock *LatchBlock = L->getLoopLatch()) { + Instruction *OrigInc = + cast(OrigPhiRef->getIncomingValueForBlock(LatchBlock)); + Instruction *IsomorphicInc = + cast(Phi->getIncomingValueForBlock(LatchBlock)); + + // If this phi is more canonical, swap it with the original. + if (!isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L, + OrigPhiRef->getType()) + && isExpandedAddRecExprPHI(Phi, IsomorphicInc, L, Phi->getType())) { + std::swap(OrigPhiRef, Phi); + std::swap(OrigInc, IsomorphicInc); + } + // Replacing the congruent phi is sufficient because acyclic redundancy + // elimination, CSE/GVN, should handle the rest. However, once SCEV proves + // that a phi is congruent, it's often the head of an IV user cycle that + // is isomorphic with the original phi. So it's worth eagerly cleaning up + // the common case of a single IV increment. + if (OrigInc != IsomorphicInc && + OrigInc->getType() == IsomorphicInc->getType() && + SE.getSCEV(OrigInc) == SE.getSCEV(IsomorphicInc) && + hoistStep(OrigInc, IsomorphicInc, DT)) { + DEBUG_WITH_TYPE(DebugType, dbgs() + << "INDVARS: Eliminated congruent iv.inc: " + << *IsomorphicInc << '\n'); + IsomorphicInc->replaceAllUsesWith(OrigInc); + DeadInsts.push_back(IsomorphicInc); + } + } + DEBUG_WITH_TYPE(DebugType, dbgs() + << "INDVARS: Eliminated congruent iv: " << *Phi << '\n'); + ++NumElim; + Phi->replaceAllUsesWith(OrigPhiRef); + DeadInsts.push_back(Phi); + } + return NumElim; +} diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index 489289d8a04..3d4603c01ee 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -119,8 +119,6 @@ namespace { void SimplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LPPassManager &LPM); - void SimplifyCongruentIVs(Loop *L); - void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter); @@ -920,40 +918,6 @@ Instruction *WidenIV::CloneIVUser(NarrowIVDefUse DU) { llvm_unreachable(0); } -/// HoistStep - Attempt to hoist an IV increment above a potential use. -/// -/// To successfully hoist, two criteria must be met: -/// - IncV operands dominate InsertPos and -/// - InsertPos dominates IncV -/// -/// Meeting the second condition means that we don't need to check all of IncV's -/// existing uses (it's moving up in the domtree). -/// -/// This does not yet recursively hoist the operands, although that would -/// not be difficult. -static bool HoistStep(Instruction *IncV, Instruction *InsertPos, - const DominatorTree *DT) -{ - if (DT->dominates(IncV, InsertPos)) - return true; - - if (!DT->dominates(InsertPos->getParent(), IncV->getParent())) - return false; - - if (IncV->mayHaveSideEffects()) - return false; - - // Attempt to hoist IncV - for (User::op_iterator OI = IncV->op_begin(), OE = IncV->op_end(); - OI != OE; ++OI) { - Instruction *OInst = dyn_cast(OI); - if (OInst && !DT->dominates(OInst, InsertPos)) - return false; - } - IncV->moveBefore(InsertPos); - return true; -} - /// No-wrap operations can transfer sign extension of their result to their /// operands. Generate the SCEV value for the widened operation without /// actually modifying the IR yet. If the expression after extending the @@ -1084,9 +1048,9 @@ Instruction *WidenIV::WidenIVUse(NarrowIVDefUse DU) { // Reuse the IV increment that SCEVExpander created as long as it dominates // NarrowUse. Instruction *WideUse = 0; - if (WideAddRec == WideIncExpr && HoistStep(WideInc, DU.NarrowUse, DT)) { + if (WideAddRec == WideIncExpr + && SCEVExpander::hoistStep(WideInc, DU.NarrowUse, DT)) WideUse = WideInc; - } else { WideUse = CloneIVUser(DU); if (!WideUse) @@ -1259,54 +1223,6 @@ void IndVarSimplify::SimplifyAndExtend(Loop *L, } } -/// SimplifyCongruentIVs - Check for congruent phis in this loop header and -/// replace them with their chosen representative. -/// -void IndVarSimplify::SimplifyCongruentIVs(Loop *L) { - DenseMap ExprToIVMap; - for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) { - PHINode *Phi = cast(I); - if (!SE->isSCEVable(Phi->getType())) - continue; - - const SCEV *S = SE->getSCEV(Phi); - std::pair::const_iterator, bool> Tmp = - ExprToIVMap.insert(std::make_pair(S, Phi)); - if (Tmp.second) - continue; - PHINode *OrigPhi = Tmp.first->second; - - // If one phi derives from the other via GEPs, types may differ. - if (OrigPhi->getType() != Phi->getType()) - continue; - - // Replacing the congruent phi is sufficient because acyclic redundancy - // elimination, CSE/GVN, should handle the rest. However, once SCEV proves - // that a phi is congruent, it's almost certain to be the head of an IV - // user cycle that is isomorphic with the original phi. So it's worth - // eagerly cleaning up the common case of a single IV increment. - if (BasicBlock *LatchBlock = L->getLoopLatch()) { - Instruction *OrigInc = - cast(OrigPhi->getIncomingValueForBlock(LatchBlock)); - Instruction *IsomorphicInc = - cast(Phi->getIncomingValueForBlock(LatchBlock)); - if (OrigInc != IsomorphicInc && - OrigInc->getType() == IsomorphicInc->getType() && - SE->getSCEV(OrigInc) == SE->getSCEV(IsomorphicInc) && - HoistStep(OrigInc, IsomorphicInc, DT)) { - DEBUG(dbgs() << "INDVARS: Eliminated congruent iv.inc: " - << *IsomorphicInc << '\n'); - IsomorphicInc->replaceAllUsesWith(OrigInc); - DeadInsts.push_back(IsomorphicInc); - } - } - DEBUG(dbgs() << "INDVARS: Eliminated congruent iv: " << *Phi << '\n'); - ++NumElimIV; - Phi->replaceAllUsesWith(OrigPhi); - DeadInsts.push_back(Phi); - } -} - //===----------------------------------------------------------------------===// // LinearFunctionTestReplace and its kin. Rewrite the loop exit condition. //===----------------------------------------------------------------------===// @@ -1848,6 +1764,9 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { // Create a rewriter object which we'll use to transform the code with. SCEVExpander Rewriter(*SE, "indvars"); +#ifndef NDEBUG + Rewriter.setDebugType(DEBUG_TYPE); +#endif // Eliminate redundant IV users. // @@ -1875,7 +1794,7 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { // Eliminate redundant IV cycles. if (!EnableIVRewrite) - SimplifyCongruentIVs(L); + NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts); // Compute the type of the largest recurrence expression, and decide whether // a canonical induction variable should be inserted. diff --git a/test/Transforms/IndVarSimplify/no-iv-rewrite.ll b/test/Transforms/IndVarSimplify/no-iv-rewrite.ll index 79485837d5f..9c2abd0f31c 100644 --- a/test/Transforms/IndVarSimplify/no-iv-rewrite.ll +++ b/test/Transforms/IndVarSimplify/no-iv-rewrite.ll @@ -281,6 +281,7 @@ return: ; CHECK-NOT: phi ; CHECK: add i32 ; CHECK: add i32 +; CHECK: add i32 ; CHECK-NOT: add ; CHECK: return: ; -- 2.34.1