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/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;
DominatorTree *DT;
SmallVectorImpl<WeakVH> &DeadInsts;
bool Changed;
public:
SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
LoopInfo *LI,SmallVectorImpl<WeakVH> &Dead)
: L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) {
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 eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand,
bool IsSigned);
bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
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.emplace_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);
ICmpInst::Predicate InvariantPredicate;
const SCEV *InvariantLHS, *InvariantRHS;
if (SE->isKnownPredicate(Pred, S, X)) {
ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
DeadInsts.emplace_back(ICmp);
DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
} else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
DeadInsts.emplace_back(ICmp);
DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
} else if (isa<PHINode>(IVOperand) &&
SE->isLoopInvariantPredicate(Pred, S, X, ICmpLoop,
InvariantPredicate, InvariantLHS,
InvariantRHS)) {
Value *NewLHS = nullptr, *NewRHS = nullptr;
if (S == InvariantLHS || X == InvariantLHS)
NewLHS =
ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx));
if (S == InvariantRHS || X == InvariantRHS)
NewRHS =
ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
for (Value *Incoming : cast<PHINode>(IVOperand)->incoming_values()) {
if (NewLHS && NewRHS)
break;
const SCEV *IncomingS = SE->getSCEV(Incoming);
if (!NewLHS && IncomingS == InvariantLHS)
NewLHS = Incoming;
if (!NewRHS && IncomingS == InvariantRHS)
NewRHS = Incoming;
}
if (!NewLHS || !NewRHS)
return;
DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
ICmp->setPredicate(InvariantPredicate);
ICmp->setOperand(0, NewLHS);
ICmp->setOperand(1, NewRHS);
} else
return;
++NumElimCmp;
Changed = true;
}
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->getOne(S->getType()));
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.emplace_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 (eliminateIdentitySCEV(UseInst, IVOperand))
return true;
return false;
}
bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
Instruction *IVOperand) {
if (!SE->isSCEVable(UseInst->getType()) ||
(UseInst->getType() != IVOperand->getType()) ||
(SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
return false;
if (isa<PHINode>(UseInst))
if (!DT || !DT->dominates(IVOperand, UseInst))
return false;
if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
return false;
DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
UseInst->replaceAllUsesWith(IVOperand);
++NumElimIdentity;
Changed = true;
DeadInsts.emplace_back(UseInst);
return true;
}
bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
Value *IVOperand) {
if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
return false;
const SCEV *(ScalarEvolution::*GetExprForBO)(const SCEV *, const SCEV *,
SCEV::NoWrapFlags);
switch (BO->getOpcode()) {
default:
return false;
case Instruction::Add:
GetExprForBO = &ScalarEvolution::getAddExpr;
break;
case Instruction::Sub:
GetExprForBO = &ScalarEvolution::getMinusSCEV;
break;
case Instruction::Mul:
GetExprForBO = &ScalarEvolution::getMulExpr;
break;
}
unsigned BitWidth = cast<IntegerType>(BO->getType())->getBitWidth();
Type *WideTy = IntegerType::get(BO->getContext(), BitWidth * 2);
const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
bool Changed = false;
if (!BO->hasNoUnsignedWrap()) {
const SCEV *ExtendAfterOp = SE->getZeroExtendExpr(SE->getSCEV(BO), WideTy);
const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
SE->getZeroExtendExpr(LHS, WideTy), SE->getZeroExtendExpr(RHS, WideTy),
SCEV::FlagAnyWrap);
if (ExtendAfterOp == OpAfterExtend) {
BO->setHasNoUnsignedWrap();
SE->forgetValue(BO);
Changed = true;
}
}
if (!BO->hasNoSignedWrap()) {
const SCEV *ExtendAfterOp = SE->getSignExtendExpr(SE->getSCEV(BO), WideTy);
const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
SE->getSignExtendExpr(LHS, WideTy), SE->getSignExtendExpr(RHS, WideTy),
SCEV::FlagAnyWrap);
if (ExtendAfterOp == OpAfterExtend) {
BO->setHasNoSignedWrap();
SE->forgetValue(BO);
Changed = true;
}
}
return Changed;
}
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.emplace_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).second)
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;
}
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseOper.first)) {
if (isa<OverflowingBinaryOperator>(BO) &&
strengthenOverflowingOperation(BO, IVOperand)) {
pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
}
}
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, DominatorTree *DT,
LPPassManager *LPM, SmallVectorImpl<WeakVH> &Dead, IVVisitor *V)
{
LoopInfo *LI = &LPM->getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Dead);
SIV.simplifyUsers(CurrIV, V);
return SIV.hasChanged();
}
bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
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, DT, LPM, Dead);
}
return Changed;
}
}