#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LibCallSemantics.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
if (!A || !C || !B || !D)
return nullptr;
+ Value *V = nullptr;
Value *SimplifiedInst = nullptr;
Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
Instruction::BinaryOps TopLevelOpcode = I.getOpcode();
std::swap(C, D);
// Consider forming "A op' (B op D)".
// If "B op D" simplifies then it can be formed with no cost.
- Value *V = SimplifyBinOp(TopLevelOpcode, B, D, DL);
+ V = SimplifyBinOp(TopLevelOpcode, B, D, DL);
// If "B op D" doesn't simplify then only go on if both of the existing
// operations "A op' B" and "C op' D" will be zapped as no longer used.
if (!V && LHS->hasOneUse() && RHS->hasOneUse())
std::swap(C, D);
// Consider forming "(A op C) op' B".
// If "A op C" simplifies then it can be formed with no cost.
- Value *V = SimplifyBinOp(TopLevelOpcode, A, C, DL);
+ V = SimplifyBinOp(TopLevelOpcode, A, C, DL);
// If "A op C" doesn't simplify then only go on if both of the existing
// operations "A op' B" and "C op' D" will be zapped as no longer used.
if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
if (isa<OverflowingBinaryOperator>(Op1))
HasNSW &= Op1->hasNoSignedWrap();
- BO->setHasNoSignedWrap(HasNSW);
+
+ // We can propagate 'nsw' if we know that
+ // %Y = mul nsw i16 %X, C
+ // %Z = add nsw i16 %Y, %X
+ // =>
+ // %Z = mul nsw i16 %X, C+1
+ //
+ // iff C+1 isn't INT_MIN
+ const APInt *CInt;
+ if (TopLevelOpcode == Instruction::Add &&
+ InnerOpcode == Instruction::Mul)
+ if (match(V, m_APInt(CInt)) && !CInt->isMinSignedValue())
+ BO->setHasNoSignedWrap(HasNSW);
}
}
}
}
}
+ // (op (select (a, c, b)), (select (a, d, b))) -> (select (a, (op c, d), 0))
+ // (op (select (a, b, c)), (select (a, b, d))) -> (select (a, 0, (op c, d)))
+ if (auto *SI0 = dyn_cast<SelectInst>(LHS)) {
+ if (auto *SI1 = dyn_cast<SelectInst>(RHS)) {
+ if (SI0->getCondition() == SI1->getCondition()) {
+ Value *SI = nullptr;
+ if (Value *V = SimplifyBinOp(TopLevelOpcode, SI0->getFalseValue(),
+ SI1->getFalseValue(), DL, TLI, DT, AC))
+ SI = Builder->CreateSelect(SI0->getCondition(),
+ Builder->CreateBinOp(TopLevelOpcode,
+ SI0->getTrueValue(),
+ SI1->getTrueValue()),
+ V);
+ if (Value *V = SimplifyBinOp(TopLevelOpcode, SI0->getTrueValue(),
+ SI1->getTrueValue(), DL, TLI, DT, AC))
+ SI = Builder->CreateSelect(
+ SI0->getCondition(), V,
+ Builder->CreateBinOp(TopLevelOpcode, SI0->getFalseValue(),
+ SI1->getFalseValue()));
+ if (SI) {
+ SI->takeName(&I);
+ return SI;
+ }
+ }
+ }
+ }
+
return nullptr;
}
return nullptr;
}
+ // Test if a CmpInst instruction is used exclusively by a select as
+ // part of a minimum or maximum operation. If so, refrain from doing
+ // any other folding. This helps out other analyses which understand
+ // non-obfuscated minimum and maximum idioms, such as ScalarEvolution
+ // and CodeGen. And in this case, at least one of the comparison
+ // operands has at least one user besides the compare (the select),
+ // which would often largely negate the benefit of folding anyway.
+ if (auto *CI = dyn_cast<CmpInst>(SI->getCondition())) {
+ if (CI->hasOneUse()) {
+ Value *Op0 = CI->getOperand(0), *Op1 = CI->getOperand(1);
+ if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
+ (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
+ return nullptr;
+ }
+ }
+
Value *SelectTrueVal = FoldOperationIntoSelectOperand(Op, TV, this);
Value *SelectFalseVal = FoldOperationIntoSelectOperand(Op, FV, this);
return nullptr;
}
-
/// FoldOpIntoPhi - Given a binary operator, cast instruction, or select which
/// has a PHI node as operand #0, see if we can fold the instruction into the
/// PHI (which is only possible if all operands to the PHI are constants).
NewPN->takeName(PN);
// If we are going to have to insert a new computation, do so right before the
- // predecessors terminator.
+ // predecessor's terminator.
if (NonConstBB)
Builder->SetInsertPoint(NonConstBB->getTerminator());
/// whether or not there is a sequence of GEP indices into the pointed type that
/// will land us at the specified offset. If so, fill them into NewIndices and
/// return the resultant element type, otherwise return null.
-Type *InstCombiner::FindElementAtOffset(Type *PtrTy, int64_t Offset,
+Type *InstCombiner::FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
SmallVectorImpl<Value *> &NewIndices) {
- assert(PtrTy->isPtrOrPtrVectorTy());
-
- Type *Ty = PtrTy->getPointerElementType();
+ Type *Ty = PtrTy->getElementType();
if (!Ty->isSized())
return nullptr;
// normalized.
if (SO1->getType() != GO1->getType())
return nullptr;
+ // Only do the combine when GO1 and SO1 are both constants. Only in
+ // this case, we are sure the cost after the merge is never more than
+ // that before the merge.
+ if (!isa<Constant>(GO1) || !isa<Constant>(SO1))
+ return nullptr;
Sum = Builder->CreateAdd(SO1, GO1, PtrOp->getName()+".sum");
}
// is a leading zero) we can fold the cast into this GEP.
if (StrippedPtrTy->getAddressSpace() == GEP.getAddressSpace()) {
GEP.setOperand(0, StrippedPtr);
+ GEP.setSourceElementType(XATy);
return &GEP;
}
// Cannot replace the base pointer directly because StrippedPtr's
// %0 = GEP [10 x i8] addrspace(1)* X, ...
// addrspacecast i8 addrspace(1)* %0 to i8*
SmallVector<Value*, 8> Idx(GEP.idx_begin(), GEP.idx_end());
- Value *NewGEP = GEP.isInBounds() ?
- Builder->CreateInBoundsGEP(StrippedPtr, Idx, GEP.getName()) :
- Builder->CreateGEP(StrippedPtr, Idx, GEP.getName());
+ Value *NewGEP = GEP.isInBounds()
+ ? Builder->CreateInBoundsGEP(
+ nullptr, StrippedPtr, Idx, GEP.getName())
+ : Builder->CreateGEP(nullptr, StrippedPtr, Idx,
+ GEP.getName());
return new AddrSpaceCastInst(NewGEP, GEP.getType());
}
}
DL.getTypeAllocSize(ResElTy)) {
Type *IdxType = DL.getIntPtrType(GEP.getType());
Value *Idx[2] = { Constant::getNullValue(IdxType), GEP.getOperand(1) };
- Value *NewGEP = GEP.isInBounds() ?
- Builder->CreateInBoundsGEP(StrippedPtr, Idx, GEP.getName()) :
- Builder->CreateGEP(StrippedPtr, Idx, GEP.getName());
+ Value *NewGEP =
+ GEP.isInBounds()
+ ? Builder->CreateInBoundsGEP(nullptr, StrippedPtr, Idx,
+ GEP.getName())
+ : Builder->CreateGEP(nullptr, StrippedPtr, Idx, GEP.getName());
// V and GEP are both pointer types --> BitCast
return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP,
// Successfully decomposed Idx as NewIdx * Scale, form a new GEP.
// If the multiplication NewIdx * Scale may overflow then the new
// GEP may not be "inbounds".
- Value *NewGEP = GEP.isInBounds() && NSW ?
- Builder->CreateInBoundsGEP(StrippedPtr, NewIdx, GEP.getName()) :
- Builder->CreateGEP(StrippedPtr, NewIdx, GEP.getName());
+ Value *NewGEP =
+ GEP.isInBounds() && NSW
+ ? Builder->CreateInBoundsGEP(nullptr, StrippedPtr, NewIdx,
+ GEP.getName())
+ : Builder->CreateGEP(nullptr, StrippedPtr, NewIdx,
+ GEP.getName());
// The NewGEP must be pointer typed, so must the old one -> BitCast
return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP,
Constant::getNullValue(DL.getIntPtrType(GEP.getType())),
NewIdx};
- Value *NewGEP = GEP.isInBounds() && NSW ?
- Builder->CreateInBoundsGEP(StrippedPtr, Off, GEP.getName()) :
- Builder->CreateGEP(StrippedPtr, Off, GEP.getName());
+ Value *NewGEP = GEP.isInBounds() && NSW
+ ? Builder->CreateInBoundsGEP(
+ SrcElTy, StrippedPtr, Off, GEP.getName())
+ : Builder->CreateGEP(SrcElTy, StrippedPtr, Off,
+ GEP.getName());
// The NewGEP must be pointer typed, so must the old one -> BitCast
return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP,
GEP.getType());
// GEP.
SmallVector<Value*, 8> NewIndices;
if (FindElementAtOffset(OpType, Offset.getSExtValue(), NewIndices)) {
- Value *NGEP = GEP.isInBounds() ?
- Builder->CreateInBoundsGEP(Operand, NewIndices) :
- Builder->CreateGEP(Operand, NewIndices);
+ Value *NGEP =
+ GEP.isInBounds()
+ ? Builder->CreateInBoundsGEP(nullptr, Operand, NewIndices)
+ : Builder->CreateGEP(nullptr, Operand, NewIndices);
if (NGEP->getType() == GEP.getType())
return ReplaceInstUsesWith(GEP, NGEP);
case Instruction::BitCast:
case Instruction::GetElementPtr:
- Users.push_back(I);
+ Users.emplace_back(I);
Worklist.push_back(I);
continue;
// We can fold eq/ne comparisons with null to false/true, respectively.
if (!ICI->isEquality() || !isa<ConstantPointerNull>(ICI->getOperand(1)))
return false;
- Users.push_back(I);
+ Users.emplace_back(I);
continue;
}
case Intrinsic::lifetime_start:
case Intrinsic::lifetime_end:
case Intrinsic::objectsize:
- Users.push_back(I);
+ Users.emplace_back(I);
continue;
}
}
if (isFreeCall(I, TLI)) {
- Users.push_back(I);
+ Users.emplace_back(I);
continue;
}
return false;
StoreInst *SI = cast<StoreInst>(I);
if (SI->isVolatile() || SI->getPointerOperand() != PI)
return false;
- Users.push_back(I);
+ Users.emplace_back(I);
continue;
}
}
// Truncate the condition operand if the new type is equal to or larger than
// the largest legal integer type. We need to be conservative here since
- // x86 generates redundant zero-extenstion instructions if the operand is
+ // x86 generates redundant zero-extension instructions if the operand is
// truncated to i8 or i16.
bool TruncCond = false;
if (NewWidth > 0 && BitWidth > NewWidth &&
if (!EV.hasIndices())
return ReplaceInstUsesWith(EV, Agg);
- if (Constant *C = dyn_cast<Constant>(Agg)) {
- if (Constant *C2 = C->getAggregateElement(*EV.idx_begin())) {
- if (EV.getNumIndices() == 0)
- return ReplaceInstUsesWith(EV, C2);
- // Extract the remaining indices out of the constant indexed by the
- // first index
- return ExtractValueInst::Create(C2, EV.getIndices().slice(1));
- }
- return nullptr; // Can't handle other constants
- }
+ if (Value *V =
+ SimplifyExtractValueInst(Agg, EV.getIndices(), DL, TLI, DT, AC))
+ return ReplaceInstUsesWith(EV, V);
if (InsertValueInst *IV = dyn_cast<InsertValueInst>(Agg)) {
// We're extracting from an insertvalue instruction, compare the indices
// We need to insert these at the location of the old load, not at that of
// the extractvalue.
Builder->SetInsertPoint(L->getParent(), L);
- Value *GEP = Builder->CreateInBoundsGEP(L->getPointerOperand(), Indices);
+ Value *GEP = Builder->CreateInBoundsGEP(L->getType(),
+ L->getPointerOperand(), Indices);
// Returning the load directly will cause the main loop to insert it in
// the wrong spot, so use ReplaceInstUsesWith().
return ReplaceInstUsesWith(EV, Builder->CreateLoad(GEP));
// The logic here should be correct for any real-world personality function.
// However if that turns out not to be true, the offending logic can always
// be conditioned on the personality function, like the catch-all logic is.
- EHPersonality Personality = classifyEHPersonality(LI.getPersonalityFn());
+ EHPersonality Personality =
+ classifyEHPersonality(LI.getParent()->getParent()->getPersonalityFn());
// Simplify the list of clauses, eg by removing repeated catch clauses
// (these are often created by inlining).
// with a new one.
if (MakeNewInstruction) {
LandingPadInst *NLI = LandingPadInst::Create(LI.getType(),
- LI.getPersonalityFn(),
NewClauses.size());
for (unsigned i = 0, e = NewClauses.size(); i != e; ++i)
NLI->addClause(NewClauses[i]);
assert(I->hasOneUse() && "Invariants didn't hold!");
// Cannot move control-flow-involving, volatile loads, vaarg, etc.
- if (isa<PHINode>(I) || isa<LandingPadInst>(I) || I->mayHaveSideEffects() ||
+ if (isa<PHINode>(I) || I->isEHPad() || I->mayHaveSideEffects() ||
isa<TerminatorInst>(I))
return false;
}
// Instruction isn't dead, see if we can constant propagate it.
- if (!I->use_empty() && isa<Constant>(I->getOperand(0))) {
+ if (!I->use_empty() &&
+ (I->getNumOperands() == 0 || isa<Constant>(I->getOperand(0)))) {
if (Constant *C = ConstantFoldInstruction(I, DL, TLI)) {
DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *I << '\n');
DEBUG(dbgs() << "IC: Old = " << *I << '\n'
<< " New = " << *Result << '\n');
- if (!I->getDebugLoc().isUnknown())
+ if (I->getDebugLoc())
Result->setDebugLoc(I->getDebugLoc());
// Everything uses the new instruction now.
I->replaceAllUsesWith(Result);
}
// ConstantProp instruction if trivially constant.
- if (!Inst->use_empty() && isa<Constant>(Inst->getOperand(0)))
+ if (!Inst->use_empty() &&
+ (Inst->getNumOperands() == 0 || isa<Constant>(Inst->getOperand(0))))
if (Constant *C = ConstantFoldInstruction(Inst, DL, TLI)) {
DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: "
<< *Inst << '\n');
}
}
- for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
- Worklist.push_back(TI->getSuccessor(i));
+ for (BasicBlock *SuccBB : TI->successors())
+ Worklist.push_back(SuccBB);
} while (!Worklist.empty());
// Once we've found all of the instructions to add to instcombine's worklist,
Instruction *Inst = --I;
if (!Inst->use_empty())
Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
- if (isa<LandingPadInst>(Inst)) {
+ if (Inst->isEHPad()) {
EndInst = Inst;
continue;
}
static bool
combineInstructionsOverFunction(Function &F, InstCombineWorklist &Worklist,
- AssumptionCache &AC, TargetLibraryInfo &TLI,
- DominatorTree &DT, LoopInfo *LI = nullptr) {
- // Minimizing size?
- bool MinimizeSize = F.hasFnAttribute(Attribute::MinSize);
+ AliasAnalysis *AA, AssumptionCache &AC,
+ TargetLibraryInfo &TLI, DominatorTree &DT,
+ LoopInfo *LI = nullptr) {
auto &DL = F.getParent()->getDataLayout();
/// Builder - This is an IRBuilder that automatically inserts new
if (prepareICWorklistFromFunction(F, DL, &TLI, Worklist))
Changed = true;
- InstCombiner IC(Worklist, &Builder, MinimizeSize, &AC, &TLI, &DT, DL, LI);
+ InstCombiner IC(Worklist, &Builder, F.optForMinSize(),
+ AA, &AC, &TLI, &DT, DL, LI);
if (IC.run())
Changed = true;
auto *LI = AM->getCachedResult<LoopAnalysis>(F);
- if (!combineInstructionsOverFunction(F, Worklist, AC, TLI, DT, LI))
+ // FIXME: The AliasAnalysis is not yet supported in the new pass manager
+ if (!combineInstructionsOverFunction(F, Worklist, nullptr, AC, TLI, DT, LI))
// No changes, all analyses are preserved.
return PreservedAnalyses::all();
void InstructionCombiningPass::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
+ AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<AssumptionCacheTracker>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
AU.addRequired<DominatorTreeWrapperPass>();
AU.addPreserved<DominatorTreeWrapperPass>();
+ AU.addPreserved<GlobalsAAWrapperPass>();
}
bool InstructionCombiningPass::runOnFunction(Function &F) {
return false;
// Required analyses.
+ auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
- return combineInstructionsOverFunction(F, Worklist, AC, TLI, DT, LI);
+ return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, LI);
}
char InstructionCombiningPass::ID = 0;
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
INITIALIZE_PASS_END(InstructionCombiningPass, "instcombine",
"Combine redundant instructions", false, false)
projects / oota-llvm.git / blobdiff