SimplifyIndVar.cpp [plain text]
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include "llvm/ADT/STLExtras.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/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
#define DEBUG_TYPE "indvars"
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 DataLayout *DL;
SmallVectorImpl<WeakVH> &DeadInsts;
bool Changed;
public:
SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LPPassManager *LPM,
SmallVectorImpl<WeakVH> &Dead, IVUsers *IVU = nullptr) :
L(Loop),
LI(LPM->getAnalysisIfAvailable<LoopInfo>()),
SE(SE),
DeadInsts(Dead),
Changed(false) {
DataLayoutPass *DLP = LPM->getAnalysisIfAvailable<DataLayoutPass>();
DL = DLP ? &DLP->getDataLayout() : nullptr;
assert(LI && "IV simplification requires LoopInfo");
}
bool hasChanged() const { return Changed; }
void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
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);
Instruction *splitOverflowIntrinsic(Instruction *IVUser,
const DominatorTree *DT);
};
}
Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
Value *IVSrc = nullptr;
unsigned OperIdx = 0;
const SCEV *FoldedExpr = nullptr;
switch (UseInst->getOpcode()) {
default:
return nullptr;
case Instruction::UDiv:
case Instruction::LShr:
if (IVOperand != UseInst->getOperand(OperIdx) ||
!isa<ConstantInt>(UseInst->getOperand(1)))
return nullptr;
if (!isa<BinaryOperator>(IVOperand)
|| !isa<ConstantInt>(IVOperand->getOperand(1)))
return nullptr;
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 nullptr;
D = ConstantInt::get(UseInst->getContext(),
APInt::getOneBitSet(BitWidth, D->getZExtValue()));
}
FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
}
if (!SE->isSCEVable(UseInst->getType()))
return nullptr;
if (SE->getSCEV(UseInst) != FoldedExpr)
return nullptr;
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;
}
Instruction *SimplifyIndvar::splitOverflowIntrinsic(Instruction *IVUser,
const DominatorTree *DT) {
IntrinsicInst *II = dyn_cast<IntrinsicInst>(IVUser);
if (!II || II->getIntrinsicID() != Intrinsic::sadd_with_overflow)
return IVUser;
BranchInst *Branch = nullptr;
Instruction *AddVal = nullptr;
for (User *U : II->users()) {
if (ExtractValueInst *ExtractInst = dyn_cast<ExtractValueInst>(U)) {
if (ExtractInst->getNumIndices() != 1)
continue;
if (ExtractInst->getIndices()[0] == 0)
AddVal = ExtractInst;
else if (ExtractInst->getIndices()[0] == 1 && ExtractInst->hasOneUse())
Branch = dyn_cast<BranchInst>(ExtractInst->user_back());
}
}
if (!AddVal || !Branch)
return IVUser;
BasicBlock *ContinueBB = Branch->getSuccessor(1);
if (std::next(pred_begin(ContinueBB)) != pred_end(ContinueBB))
return IVUser;
bool AllNSW = true;
for (Use &U : AddVal->uses()) {
if (Instruction *UseInst = dyn_cast<Instruction>(U.getUser())) {
BasicBlock *UseBB = UseInst->getParent();
if (PHINode *PHI = dyn_cast<PHINode>(UseInst))
UseBB = PHI->getIncomingBlock(U);
if (!DT->dominates(ContinueBB, UseBB)) {
AllNSW = false;
break;
}
}
}
if (!AllNSW)
return IVUser;
IRBuilder<> Builder(IVUser);
Instruction *AddInst = dyn_cast<Instruction>(
Builder.CreateNSWAdd(II->getOperand(0), II->getOperand(1)));
assert((AddInst->getOpcode() == Instruction::Add &&
AddInst->getOperand(0) == II->getOperand(0)) &&
"Bad add instruction created from overflow intrinsic.");
AddVal->replaceAllUsesWith(AddInst);
DeadInsts.push_back(AddVal);
return AddInst;
}
static void pushIVUsers(
Instruction *Def,
SmallPtrSet<Instruction*,16> &Simplified,
SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
for (User *U : Def->users()) {
Instruction *UI = cast<Instruction>(U);
if (UI != Def && Simplified.insert(UI))
SimpleIVUsers.push_back(std::make_pair(UI, 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();
Instruction *UseInst = UseOper.first;
if (UseInst == CurrIV) continue;
if (V && V->shouldSplitOverflowInstrinsics()) {
UseInst = splitOverflowIntrinsic(UseInst, V->getDomTree());
if (!UseInst)
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;
}
}