From ee98aa87434d9d49a8e4dab41d873888ac9c4805 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Sat, 7 Jan 2012 01:12:09 +0000 Subject: [PATCH] Extended replaceCongruentPhis to handle mixed phi types. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147707 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../llvm/Analysis/ScalarEvolutionExpander.h | 5 +- lib/Analysis/ScalarEvolutionExpander.cpp | 74 +++++++++++++++---- lib/Transforms/Scalar/LoopStrengthReduce.cpp | 4 +- .../IndVarSimplify/no-iv-rewrite.ll | 4 +- 4 files changed, 69 insertions(+), 18 deletions(-) diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index cd7e7f1eb94..01a4b958cb6 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -22,6 +22,8 @@ #include namespace llvm { + class TargetLowering; + /// SCEVExpander - This class uses information about analyze scalars to /// rewrite expressions in canonical form. /// @@ -115,7 +117,8 @@ namespace llvm { /// replaceCongruentIVs - replace congruent phis with their most canonical /// representative. Return the number of phis eliminated. unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, - SmallVectorImpl &DeadInsts); + SmallVectorImpl &DeadInsts, + const TargetLowering *TLI = NULL); /// expandCodeFor - Insert code to directly compute the specified SCEV /// expression into the program. The inserted code is inserted into the diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index a82ac47e32f..0c4bb825bf9 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -19,6 +19,7 @@ #include "llvm/LLVMContext.h" #include "llvm/Support/Debug.h" #include "llvm/Target/TargetData.h" +#include "llvm/Target/TargetLowering.h" #include "llvm/ADT/STLExtras.h" using namespace llvm; @@ -1557,6 +1558,15 @@ bool SCEVExpander::hoistStep(Instruction *IncV, Instruction *InsertPos, return true; } +/// Sort Phis by integer width for replaceCongruentIVs. +static bool width_descending(PHINode *lhs, PHINode *rhs) { + // Put pointers at the back and make sure pointer < pointer = false. + if (!lhs->getType()->isIntegerTy() || !rhs->getType()->isIntegerTy()) + return rhs->getType()->isIntegerTy() && !lhs->getType()->isIntegerTy(); + return rhs->getType()->getPrimitiveSizeInBits() + < lhs->getType()->getPrimitiveSizeInBits(); +} + /// replaceCongruentIVs - Check for congruent phis in this loop header and /// replace them with their most canonical representative. Return the number of /// phis eliminated. @@ -1564,23 +1574,45 @@ bool SCEVExpander::hoistStep(Instruction *IncV, Instruction *InsertPos, /// 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) { + SmallVectorImpl &DeadInsts, + const TargetLowering *TLI) { + // Find integer phis in order of increasing width. + SmallVector Phis; + for (BasicBlock::iterator I = L->getHeader()->begin(); + PHINode *Phi = dyn_cast(I); ++I) { + Phis.push_back(Phi); + } + if (TLI) + std::sort(Phis.begin(), Phis.end(), width_descending); + unsigned NumElim = 0; DenseMap ExprToIVMap; - for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) { - PHINode *Phi = cast(I); + // Process phis from wide to narrow. Mapping wide phis to the their truncation + // so narrow phis can reuse them. + for (SmallVectorImpl::const_iterator PIter = Phis.begin(), + PEnd = Phis.end(); PIter != PEnd; ++PIter) { + PHINode *Phi = *PIter; + if (!SE.isSCEVable(Phi->getType())) continue; PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)]; if (!OrigPhiRef) { OrigPhiRef = Phi; + if (Phi->getType()->isIntegerTy() && TLI + && TLI->isTruncateFree(Phi->getType(), Phis.back()->getType())) { + // This phi can be freely truncated to the narrowest phi type. Map the + // truncated expression to it so it will be reused for narrow types. + const SCEV *TruncExpr = + SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType()); + ExprToIVMap[TruncExpr] = 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()) + // Replacing a pointer phi with an integer phi or vice-versa doesn't make + // sense. + if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy()) continue; if (BasicBlock *LatchBlock = L->getLoopLatch()) { @@ -1589,8 +1621,10 @@ unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT, Instruction *IsomorphicInc = cast(Phi->getIncomingValueForBlock(LatchBlock)); - // If this phi is more canonical, swap it with the original. - if (!isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L) + // If this phi has the same width but is more canonical, replace the + // original with it. + if (OrigPhiRef->getType() == Phi->getType() + && !isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L) && isExpandedAddRecExprPHI(Phi, IsomorphicInc, L)) { std::swap(OrigPhiRef, Phi); std::swap(OrigInc, IsomorphicInc); @@ -1600,21 +1634,35 @@ unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT, // 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) && + const SCEV *TruncExpr = SE.getTruncateOrNoop(SE.getSCEV(OrigInc), + IsomorphicInc->getType()); + if (OrigInc != IsomorphicInc + && TruncExpr == SE.getSCEV(IsomorphicInc) && hoistStep(OrigInc, IsomorphicInc, DT)) { DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Eliminated congruent iv.inc: " << *IsomorphicInc << '\n'); - IsomorphicInc->replaceAllUsesWith(OrigInc); + Value *NewInc = OrigInc; + if (OrigInc->getType() != IsomorphicInc->getType()) { + IRBuilder<> Builder(OrigInc->getNextNode()); + Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc()); + NewInc = Builder. + CreateTruncOrBitCast(OrigInc, IsomorphicInc->getType(), IVName); + } + IsomorphicInc->replaceAllUsesWith(NewInc); DeadInsts.push_back(IsomorphicInc); } } DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Eliminated congruent iv: " << *Phi << '\n'); ++NumElim; - Phi->replaceAllUsesWith(OrigPhiRef); + Value *NewIV = OrigPhiRef; + if (OrigPhiRef->getType() != Phi->getType()) { + IRBuilder<> Builder(L->getHeader()->getFirstInsertionPt()); + Builder.SetCurrentDebugLocation(Phi->getDebugLoc()); + NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName); + } + Phi->replaceAllUsesWith(NewIV); DeadInsts.push_back(Phi); } return NumElim; diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 840614e9b5d..ec0c9a6abd6 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -3865,7 +3865,7 @@ LSRInstance::LSRInstance(const TargetLowering *tli, Loop *l, Pass *P) // Remove any extra phis created by processing inner loops. SmallVector DeadInsts; SCEVExpander Rewriter(SE, "lsr"); - Changed |= (bool)Rewriter.replaceCongruentIVs(L, &DT, DeadInsts); + Changed |= (bool)Rewriter.replaceCongruentIVs(L, &DT, DeadInsts, TLI); Changed |= (bool)DeleteTriviallyDeadInstructions(DeadInsts); } DEBUG(dbgs() << "LSR skipping outer loop " << *L << "\n"); @@ -3918,7 +3918,7 @@ LSRInstance::LSRInstance(const TargetLowering *tli, Loop *l, Pass *P) // Remove any extra phis created by processing inner loops. SmallVector DeadInsts; SCEVExpander Rewriter(SE, "lsr"); - Changed |= (bool)Rewriter.replaceCongruentIVs(L, &DT, DeadInsts); + Changed |= (bool)Rewriter.replaceCongruentIVs(L, &DT, DeadInsts, TLI); Changed |= (bool)DeleteTriviallyDeadInstructions(DeadInsts); } } diff --git a/test/Transforms/IndVarSimplify/no-iv-rewrite.ll b/test/Transforms/IndVarSimplify/no-iv-rewrite.ll index 9c2abd0f31c..23fdc87a071 100644 --- a/test/Transforms/IndVarSimplify/no-iv-rewrite.ll +++ b/test/Transforms/IndVarSimplify/no-iv-rewrite.ll @@ -333,9 +333,9 @@ entry: ; CHECK: loop: ; CHECK: phi %structIF* -; CHECK: phi i32* -; CHECK: getelementptr inbounds +; CHECK-NOT: phi ; CHECK: getelementptr inbounds +; CHECK-NOT: getelementptr ; CHECK: exit: loop: %ptr.iv = phi %structIF* [ %ptr.inc, %latch ], [ %base, %entry ] -- 2.34.1