SimplifyIndVar.cpp [plain text]
#define DEBUG_TYPE "indvars"
#include "llvm/Instructions.h"
#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.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;
STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
STATISTIC(NumElimOperand, "Number of IV operands folded into a use");
STATISTIC(NumElimRem , "Number of IV remainder operations eliminated");
STATISTIC(NumElimCmp , "Number of IV comparisons eliminated");
namespace {
class SimplifyIndvar {
Loop *L;
LoopInfo *LI;
ScalarEvolution *SE;
const TargetData *TD;
SmallVectorImpl<WeakVH> &DeadInsts;
bool Changed;
public:
SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LPPassManager *LPM,
SmallVectorImpl<WeakVH> &Dead, IVUsers *IVU = NULL) :
L(Loop),
LI(LPM->getAnalysisIfAvailable<LoopInfo>()),
SE(SE),
TD(LPM->getAnalysisIfAvailable<TargetData>()),
DeadInsts(Dead),
Changed(false) {
assert(LI && "IV simplification requires LoopInfo");
}
bool hasChanged() const { return Changed; }
void simplifyUsers(PHINode *CurrIV, IVVisitor *V = NULL);
Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand,
bool IsSigned);
};
}
Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
Value *IVSrc = 0;
unsigned OperIdx = 0;
const SCEV *FoldedExpr = 0;
switch (UseInst->getOpcode()) {
default:
return 0;
case Instruction::UDiv:
case Instruction::LShr:
if (IVOperand != UseInst->getOperand(OperIdx) ||
!isa<ConstantInt>(UseInst->getOperand(1)))
return 0;
if (!isa<BinaryOperator>(IVOperand)
|| !isa<ConstantInt>(IVOperand->getOperand(1)))
return 0;
IVSrc = IVOperand->getOperand(0);
assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
if (UseInst->getOpcode() == Instruction::LShr) {
uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
if (D->getValue().uge(BitWidth))
return 0;
D = ConstantInt::get(UseInst->getContext(),
APInt(BitWidth, 1).shl(D->getZExtValue()));
}
FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
}
if (!SE->isSCEVable(UseInst->getType()))
return 0;
if (SE->getSCEV(UseInst) != FoldedExpr)
return 0;
DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
<< " -> " << *UseInst << '\n');
UseInst->setOperand(OperIdx, IVSrc);
assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
++NumElimOperand;
Changed = true;
if (IVOperand->use_empty())
DeadInsts.push_back(IVOperand);
return IVSrc;
}
void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
unsigned IVOperIdx = 0;
ICmpInst::Predicate Pred = ICmp->getPredicate();
if (IVOperand != ICmp->getOperand(0)) {
assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
IVOperIdx = 1;
Pred = ICmpInst::getSwappedPredicate(Pred);
}
const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx));
const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx));
const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
S = SE->getSCEVAtScope(S, ICmpLoop);
X = SE->getSCEVAtScope(X, ICmpLoop);
if (SE->isKnownPredicate(Pred, S, X))
ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X))
ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
else
return;
DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
++NumElimCmp;
Changed = true;
DeadInsts.push_back(ICmp);
}
void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem,
Value *IVOperand,
bool IsSigned) {
if (IVOperand != Rem->getOperand(0))
return;
const SCEV *S = SE->getSCEV(Rem->getOperand(0));
const SCEV *X = SE->getSCEV(Rem->getOperand(1));
const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
S = SE->getSCEVAtScope(S, ICmpLoop);
X = SE->getSCEVAtScope(X, ICmpLoop);
if ((!IsSigned || SE->isKnownNonNegative(S)) &&
SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
S, X))
Rem->replaceAllUsesWith(Rem->getOperand(0));
else {
const SCEV *LessOne =
SE->getMinusSCEV(S, SE->getConstant(S->getType(), 1));
if (IsSigned && !SE->isKnownNonNegative(LessOne))
return;
if (!SE->isKnownPredicate(IsSigned ?
ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
LessOne, X))
return;
ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ,
Rem->getOperand(0), Rem->getOperand(1));
SelectInst *Sel =
SelectInst::Create(ICmp,
ConstantInt::get(Rem->getType(), 0),
Rem->getOperand(0), "tmp", Rem);
Rem->replaceAllUsesWith(Sel);
}
DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
++NumElimRem;
Changed = true;
DeadInsts.push_back(Rem);
}
bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
Instruction *IVOperand) {
if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
eliminateIVComparison(ICmp, IVOperand);
return true;
}
if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
bool IsSigned = Rem->getOpcode() == Instruction::SRem;
if (IsSigned || Rem->getOpcode() == Instruction::URem) {
eliminateIVRemainder(Rem, IVOperand, IsSigned);
return true;
}
}
if (!SE->isSCEVable(UseInst->getType()) ||
(UseInst->getType() != IVOperand->getType()) ||
(SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
return false;
DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
UseInst->replaceAllUsesWith(IVOperand);
++NumElimIdentity;
Changed = true;
DeadInsts.push_back(UseInst);
return true;
}
static void pushIVUsers(
Instruction *Def,
SmallPtrSet<Instruction*,16> &Simplified,
SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
for (Value::use_iterator UI = Def->use_begin(), E = Def->use_end();
UI != E; ++UI) {
Instruction *User = cast<Instruction>(*UI);
if (User != Def && Simplified.insert(User))
SimpleIVUsers.push_back(std::make_pair(User, Def));
}
}
static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
if (!SE->isSCEVable(I->getType()))
return false;
const SCEV *S = SE->getSCEV(I);
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
if (AR && AR->getLoop() == L)
return true;
return false;
}
void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
if (!SE->isSCEVable(CurrIV->getType()))
return;
SmallPtrSet<Instruction*,16> Simplified;
SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
pushIVUsers(CurrIV, Simplified, SimpleIVUsers);
while (!SimpleIVUsers.empty()) {
std::pair<Instruction*, Instruction*> UseOper =
SimpleIVUsers.pop_back_val();
if (UseOper.first == CurrIV) continue;
Instruction *IVOperand = UseOper.second;
for (unsigned N = 0; IVOperand; ++N) {
assert(N <= Simplified.size() && "runaway iteration");
Value *NewOper = foldIVUser(UseOper.first, IVOperand);
if (!NewOper)
break; IVOperand = dyn_cast<Instruction>(NewOper);
}
if (!IVOperand)
continue;
if (eliminateIVUser(UseOper.first, IVOperand)) {
pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
continue;
}
CastInst *Cast = dyn_cast<CastInst>(UseOper.first);
if (V && Cast) {
V->visitCast(Cast);
continue;
}
if (isSimpleIVUser(UseOper.first, L, SE)) {
pushIVUsers(UseOper.first, Simplified, SimpleIVUsers);
}
}
}
namespace llvm {
void IVVisitor::anchor() { }
bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, LPPassManager *LPM,
SmallVectorImpl<WeakVH> &Dead, IVVisitor *V)
{
LoopInfo *LI = &LPM->getAnalysis<LoopInfo>();
SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LPM, Dead);
SIV.simplifyUsers(CurrIV, V);
return SIV.hasChanged();
}
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), SE, LPM, Dead);
}
return Changed;
}
}