#define DEBUG_TYPE "indvars"
-#include "llvm/Instructions.h"
-#include "llvm/Analysis/Dominators.h"
+#include "llvm/Transforms/Utils/SimplifyIndVar.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Instructions.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/Transforms/Utils/SimplifyIndVar.h"
-#include "llvm/Target/TargetData.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/Statistic.h"
using namespace llvm;
class SimplifyIndvar {
Loop *L;
LoopInfo *LI;
- DominatorTree *DT;
ScalarEvolution *SE;
- IVUsers *IU; // NULL for DisableIVRewrite
- const TargetData *TD; // May be NULL
+ const DataLayout *TD; // May be NULL
SmallVectorImpl<WeakVH> &DeadInsts;
bool Changed;
public:
- SimplifyIndvar(Loop *Loop, LPPassManager *LPM,
+ SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LPPassManager *LPM,
SmallVectorImpl<WeakVH> &Dead, IVUsers *IVU = NULL) :
L(Loop),
LI(LPM->getAnalysisIfAvailable<LoopInfo>()),
- SE(LPM->getAnalysisIfAvailable<ScalarEvolution>()),
- IU(IVU),
- TD(LPM->getAnalysisIfAvailable<TargetData>()),
+ SE(SE),
+ TD(LPM->getAnalysisIfAvailable<DataLayout>()),
DeadInsts(Dead),
Changed(false) {
- assert(LI && SE && "IV simplification requires ScalarEvolution");
+ assert(LI && "IV simplification requires LoopInfo");
}
bool hasChanged() const { return Changed; }
/// foldIVUser - Fold an IV operand into its use. This removes increments of an
/// aligned IV when used by a instruction that ignores the low bits.
///
+/// IVOperand is guaranteed SCEVable, but UseInst may not be.
+///
/// Return the operand of IVOperand for this induction variable if IVOperand can
-/// be folded (in case more folding opportunity has been exposed).
+/// be folded (in case more folding opportunities have been exposed).
/// Otherwise return null.
Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
Value *IVSrc = 0;
// Attempt to fold a binary operator with constant operand.
// e.g. ((I + 1) >> 2) => I >> 2
- if (IVOperand->getNumOperands() != 2 ||
- !isa<ConstantInt>(IVOperand->getOperand(1)))
+ if (!isa<BinaryOperator>(IVOperand)
+ || !isa<ConstantInt>(IVOperand->getOperand(1)))
return 0;
IVSrc = IVOperand->getOperand(0);
return;
ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ,
- Rem->getOperand(0), Rem->getOperand(1),
- "tmp");
+ Rem->getOperand(0), Rem->getOperand(1));
SelectInst *Sel =
SelectInst::Create(ICmp,
ConstantInt::get(Rem->getType(), 0),
Rem->replaceAllUsesWith(Sel);
}
- // Inform IVUsers about the new users.
- if (IU) {
- if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0)))
- IU->AddUsersIfInteresting(I);
- }
DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
++NumElimRem;
Changed = true;
/// eliminateIVUser - Eliminate an operation that consumes a simple IV and has
/// no observable side-effect given the range of IV values.
+/// IVOperand is guaranteed SCEVable, but UseInst may not be.
bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
Instruction *IVOperand) {
if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
/// isSimpleIVUser - Return true if this instruction generates a simple SCEV
/// expression in terms of that IV.
///
-/// This is similar to IVUsers' isInsteresting() but processes each instruction
+/// This is similar to IVUsers' isInteresting() but processes each instruction
/// non-recursively when the operand is already known to be a simpleIVUser.
///
static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
///
void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
+ if (!SE->isSCEVable(CurrIV->getType()))
+ return;
+
// Instructions processed by SimplifyIndvar for CurrIV.
SmallPtrSet<Instruction*,16> Simplified;
namespace llvm {
+void IVVisitor::anchor() { }
+
/// simplifyUsersOfIV - Simplify instructions that use this induction variable
/// by using ScalarEvolution to analyze the IV's recurrence.
-bool simplifyUsersOfIV(PHINode *CurrIV, LPPassManager *LPM,
+bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, LPPassManager *LPM,
SmallVectorImpl<WeakVH> &Dead, IVVisitor *V)
{
LoopInfo *LI = &LPM->getAnalysis<LoopInfo>();
- SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), LPM, Dead);
+ SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LPM, Dead);
SIV.simplifyUsers(CurrIV, V);
return SIV.hasChanged();
}
/// simplifyLoopIVs - Simplify users of induction variables within this
/// loop. This does not actually change or add IVs.
-bool simplifyLoopIVs(Loop *L, LPPassManager *LPM,
+bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, LPPassManager *LPM,
SmallVectorImpl<WeakVH> &Dead) {
bool Changed = false;
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
- Changed |= simplifyUsersOfIV(cast<PHINode>(I), LPM, Dead);
+ Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, LPM, Dead);
}
return Changed;
}
-/// simplifyIVUsers - Perform simplification on instructions recorded by the
-/// IVUsers pass.
-///
-/// This is the old approach to IV simplification to be replaced by
-/// SimplifyLoopIVs.
-bool simplifyIVUsers(IVUsers *IU, LPPassManager *LPM,
- SmallVectorImpl<WeakVH> &Dead) {
- SimplifyIndvar SIV(IU->getLoop(), LPM, Dead);
-
- // Each round of simplification involves a round of eliminating operations
- // followed by a round of widening IVs. A single IVUsers worklist is used
- // across all rounds. The inner loop advances the user. If widening exposes
- // more uses, then another pass through the outer loop is triggered.
- for (IVUsers::iterator I = IU->begin(); I != IU->end(); ++I) {
- Instruction *UseInst = I->getUser();
- Value *IVOperand = I->getOperandValToReplace();
-
- if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
- SIV.eliminateIVComparison(ICmp, IVOperand);
- continue;
- }
- if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
- bool IsSigned = Rem->getOpcode() == Instruction::SRem;
- if (IsSigned || Rem->getOpcode() == Instruction::URem) {
- SIV.eliminateIVRemainder(Rem, IVOperand, IsSigned);
- continue;
- }
- }
- }
- return SIV.hasChanged();
-}
-
} // namespace llvm
projects / oota-llvm.git / blobdiff