indvars -disable-iv-rewrite: Added SimplifyCongruentIVs.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134530 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index 2b0dfc6..477f42c 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -58,6 +58,7 @@
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Target/TargetData.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
@@ -72,6 +73,7 @@
STATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated");
STATISTIC(NumElimRem , "Number of IV remainder operations eliminated");
STATISTIC(NumElimCmp , "Number of IV comparisons eliminated");
+STATISTIC(NumElimIV , "Number of congruent IVs eliminated");
static cl::opt<bool> DisableIVRewrite(
"disable-iv-rewrite", cl::Hidden,
@@ -79,12 +81,15 @@
namespace {
class IndVarSimplify : public LoopPass {
+ typedef DenseMap<const SCEV *, PHINode *> ExprToIVMapTy;
+
IVUsers *IU;
LoopInfo *LI;
ScalarEvolution *SE;
DominatorTree *DT;
TargetData *TD;
+ ExprToIVMapTy ExprToIVMap;
SmallVector<WeakVH, 16> DeadInsts;
bool Changed;
public:
@@ -114,6 +119,11 @@
}
private:
+ virtual void releaseMemory() {
+ ExprToIVMap.clear();
+ DeadInsts.clear();
+ }
+
bool isValidRewrite(Value *FromVal, Value *ToVal);
void SimplifyIVUsers(SCEVExpander &Rewriter);
@@ -133,6 +143,8 @@
void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
+ void SimplifyCongruentIVs(Loop *L);
+
void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter);
void SinkUnusedInvariants(Loop *L);
@@ -1129,7 +1141,7 @@
// Instructions processed by SimplifyIVUsers for CurrIV.
SmallPtrSet<Instruction*,16> Simplified;
- // Use-def pairs if IVUsers waiting to be processed for CurrIV.
+ // Use-def pairs if IV users waiting to be processed for CurrIV.
SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
// Push users of the current LoopPhi. In rare cases, pushIVUsers may be
@@ -1175,6 +1187,45 @@
}
}
+/// SimplifyCongruentIVs - Check for congruent phis in this loop header and
+/// populate ExprToIVMap for use later.
+///
+void IndVarSimplify::SimplifyCongruentIVs(Loop *L) {
+ for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
+ PHINode *Phi = cast<PHINode>(I);
+ const SCEV *S = SE->getSCEV(Phi);
+ ExprToIVMapTy::const_iterator Pos;
+ bool Inserted;
+ tie(Pos, Inserted) = ExprToIVMap.insert(std::make_pair(S, Phi));
+ if (Inserted)
+ continue;
+ PHINode *OrigPhi = Pos->second;
+ // 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<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
+ Instruction *IsomorphicInc =
+ cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
+ if (OrigInc != IsomorphicInc &&
+ 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);
+ }
+}
+
bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
// If LoopSimplify form is not available, stay out of trouble. Some notes:
// - LSR currently only supports LoopSimplify-form loops. Indvars'
@@ -1194,6 +1245,7 @@
DT = &getAnalysis<DominatorTree>();
TD = getAnalysisIfAvailable<TargetData>();
+ ExprToIVMap.clear();
DeadInsts.clear();
Changed = false;
@@ -1230,6 +1282,11 @@
if (!DisableIVRewrite)
SimplifyIVUsers(Rewriter);
+ // Eliminate redundant IV cycles and populate ExprToIVMap.
+ // TODO: use ExprToIVMap to allow LFTR without canonical IVs
+ if (DisableIVRewrite)
+ SimplifyCongruentIVs(L);
+
// Compute the type of the largest recurrence expression, and decide whether
// a canonical induction variable should be inserted.
const Type *LargestType = 0;