summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/ScalarEvolutionExpander.h5
-rw-r--r--lib/Analysis/ScalarEvolutionExpander.cpp74
-rw-r--r--lib/Transforms/Scalar/LoopStrengthReduce.cpp4
-rw-r--r--test/Transforms/IndVarSimplify/no-iv-rewrite.ll4
4 files changed, 69 insertions, 18 deletions
diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h
index cd7e7f1eb9..01a4b958cb 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpander.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -22,6 +22,8 @@
#include <set>
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<WeakVH> &DeadInsts);
+ SmallVectorImpl<WeakVH> &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 a82ac47e32..0c4bb825bf 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<WeakVH> &DeadInsts) {
+ SmallVectorImpl<WeakVH> &DeadInsts,
+ const TargetLowering *TLI) {
+ // Find integer phis in order of increasing width.
+ SmallVector<PHINode*, 8> Phis;
+ for (BasicBlock::iterator I = L->getHeader()->begin();
+ PHINode *Phi = dyn_cast<PHINode>(I); ++I) {
+ Phis.push_back(Phi);
+ }
+ if (TLI)
+ std::sort(Phis.begin(), Phis.end(), width_descending);
+
unsigned NumElim = 0;
DenseMap<const SCEV *, PHINode *> ExprToIVMap;
- for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
- PHINode *Phi = cast<PHINode>(I);
+ // Process phis from wide to narrow. Mapping wide phis to the their truncation
+ // so narrow phis can reuse them.
+ for (SmallVectorImpl<PHINode*>::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<Instruction>(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 840614e9b5..ec0c9a6abd 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<WeakVH, 16> 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<WeakVH, 16> 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 9c2abd0f31..23fdc87a07 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 ]
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-29 07:08:53 +0000