28#define DEBUG_TYPE "instcombine"
32 cl::desc(
"Maximum number phis to handle in intptr/ptrint folding"));
35 "Number of phi-of-insertvalue turned into insertvalue-of-phis");
37 "Number of phi-of-extractvalue turned into extractvalue-of-phi");
38STATISTIC(NumPHICSEs,
"Number of PHI's that got CSE'd");
48 assert(!isa<CallInst>(Inst));
51 auto *
I = cast<Instruction>(V);
112 auto *IntToPtr = dyn_cast<IntToPtrInst>(PN.
user_back());
118 for (
User *U : IIP->users()) {
120 if (
LoadInst *LoadI = dyn_cast<LoadInst>(U)) {
121 Ptr = LoadI->getPointerOperand();
122 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(U)) {
123 Ptr = SI->getPointerOperand();
125 Ptr = GI->getPointerOperand();
134 if (!HasPointerUse(IntToPtr))
147 if (
auto *PI = dyn_cast<PtrToIntInst>(Arg)) {
153 Value *ArgIntToPtr =
nullptr;
155 if (isa<IntToPtrInst>(U) && U->getType() == IntToPtr->getType() &&
157 cast<Instruction>(U)->getParent() == BB)) {
170 if (isa<PHINode>(Arg)) {
176 auto *LoadI = dyn_cast<LoadInst>(Arg);
180 if (!LoadI->hasOneUse())
192 "Not enough available ptr typed incoming values");
193 PHINode *MatchingPtrPHI =
nullptr;
194 unsigned NumPhis = 0;
195 for (
PHINode &PtrPHI : BB->phis()) {
199 if (&PtrPHI == &PN || PtrPHI.
getType() != IntToPtr->getType())
202 [&](
const auto &BlockAndValue) {
203 BasicBlock *BB = std::get<0>(BlockAndValue);
204 Value *V = std::get<1>(BlockAndValue);
205 return PtrPHI.getIncomingValueForBlock(BB) != V;
208 MatchingPtrPHI = &PtrPHI;
212 if (MatchingPtrPHI) {
214 "Phi's Type does not match with IntToPtr");
225 return (V->getType() != IntToPtr->getType()) || isa<IntToPtrInst>(V);
234 if (V->getType() == IntToPtr->getType())
236 auto *Inst = dyn_cast<Instruction>(V);
239 if (Inst->isTerminator())
241 auto *BB = Inst->getParent();
242 if (isa<PHINode>(Inst) && BB->getFirstInsertionPt() == BB->end())
254 auto *IncomingBB = std::get<0>(
Incoming);
255 auto *IncomingVal = std::get<1>(
Incoming);
257 if (IncomingVal->getType() == IntToPtr->getType()) {
263 LoadInst *LoadI = dyn_cast<LoadInst>(IncomingVal);
264 assert((isa<PHINode>(IncomingVal) ||
265 IncomingVal->getType()->isPointerTy() ||
267 "Can not replace LoadInst with multiple uses");
280 IncomingVal->getName() +
".ptr");
281 if (
auto *IncomingI = dyn_cast<Instruction>(IncomingVal)) {
285 if (isa<PHINode>(IncomingI))
287 assert(InsertPos != BB->
end() &&
"should have checked above");
290 auto *InsertBB = &IncomingBB->getParent()->getEntryBlock();
315 bool OperandWithRoundTripCast =
false;
320 OperandWithRoundTripCast =
true;
323 if (!OperandWithRoundTripCast)
337 auto *
I = dyn_cast<InsertValueInst>(V);
338 if (!
I || !
I->hasOneUser() ||
I->getIndices() != FirstIVI->getIndices())
343 std::array<PHINode *, 2> NewOperands;
344 for (
int OpIdx : {0, 1}) {
345 auto *&NewOperand = NewOperands[OpIdx];
350 FirstIVI->getOperand(OpIdx)->getName() +
".pn");
353 NewOperand->addIncoming(
354 cast<InsertValueInst>(std::get<1>(
Incoming))->getOperand(OpIdx),
361 FirstIVI->getIndices(), PN.
getName());
364 ++NumPHIsOfInsertValues;
377 auto *
I = dyn_cast<ExtractValueInst>(V);
378 if (!
I || !
I->hasOneUser() ||
I->getIndices() != FirstEVI->getIndices() ||
379 I->getAggregateOperand()->getType() !=
380 FirstEVI->getAggregateOperand()->getType())
388 FirstEVI->getAggregateOperand()->getName() +
".pn");
391 NewAggregateOperand->addIncoming(
392 cast<ExtractValueInst>(std::get<1>(
Incoming))->getAggregateOperand(),
398 FirstEVI->getIndices(), PN.
getName());
401 ++NumPHIsOfExtractValues;
409 assert(isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst));
420 if (!
I ||
I->getOpcode() != Opc || !
I->hasOneUser() ||
423 I->getOperand(0)->getType() != LHSType ||
424 I->getOperand(1)->getType() != RHSType)
428 if (
CmpInst *CI = dyn_cast<CmpInst>(
I))
429 if (CI->getPredicate() != cast<CmpInst>(FirstInst)->getPredicate())
433 if (
I->getOperand(0) != LHSVal) LHSVal =
nullptr;
434 if (
I->getOperand(1) != RHSVal) RHSVal =
nullptr;
441 if (!LHSVal && !RHSVal)
448 PHINode *NewLHS =
nullptr, *NewRHS =
nullptr;
466 if (NewLHS || NewRHS) {
477 NewRHS->addIncoming(NewInRHS, InBB);
482 if (
CmpInst *CIOp = dyn_cast<CmpInst>(FirstInst)) {
509 bool AllBasePointersAreAllocas =
true;
514 bool NeededPhi =
false;
521 if (!
GEP || !
GEP->hasOneUser() ||
526 NW &=
GEP->getNoWrapFlags();
529 if (AllBasePointersAreAllocas &&
530 (!isa<AllocaInst>(
GEP->getOperand(0)) ||
531 !
GEP->hasAllConstantIndices()))
532 AllBasePointersAreAllocas =
false;
545 isa<ConstantInt>(
GEP->getOperand(
Op)))
549 GEP->getOperand(
Op)->getType())
559 FixedOperands[
Op] =
nullptr;
570 if (AllBasePointersAreAllocas)
577 bool HasAnyPHIs =
false;
578 for (
unsigned I = 0, E = FixedOperands.
size();
I != E; ++
I) {
579 if (FixedOperands[
I])
587 OperandPhis[
I] = NewPN;
588 FixedOperands[
I] = NewPN;
599 for (
unsigned Op = 0, E = OperandPhis.
size();
Op != E; ++
Op)
608 ArrayRef(FixedOperands).slice(1), NW);
623 for (++BBI; BBI != E; ++BBI)
624 if (BBI->mayWriteToMemory()) {
627 if (
auto *CB = dyn_cast<CallBase>(BBI))
628 if (CB->onlyAccessesInaccessibleMemory())
635 if (
AllocaInst *AI = dyn_cast<AllocaInst>(L->getOperand(0))) {
636 bool IsAddressTaken =
false;
637 for (
User *U : AI->users()) {
638 if (isa<LoadInst>(U))
continue;
639 if (
StoreInst *SI = dyn_cast<StoreInst>(U)) {
641 if (SI->getOperand(1) == AI)
continue;
643 IsAddressTaken =
true;
647 if (!IsAddressTaken && AI->isStaticAlloca())
657 if (
AllocaInst *AI = dyn_cast<AllocaInst>(
GEP->getOperand(0)))
658 if (AI->isStaticAlloca() &&
GEP->hasAllConstantIndices())
692 FirstLI->
getParent()->getTerminator()->getNumSuccessors() != 1)
699 if (!
LI || !
LI->hasOneUser() ||
LI->isAtomic())
703 if (
LI->isVolatile() != IsVolatile ||
704 LI->getPointerAddressSpace() != LoadAddrSpace)
708 if (
LI->getOperand(0)->isSwiftError())
716 LoadAlignment = std::min(LoadAlignment,
LI->getAlign());
721 if (IsVolatile &&
LI->getParent()->getTerminator()->getNumSuccessors() != 1)
734 new LoadInst(FirstLI->
getType(), NewPN,
"", IsVolatile, LoadAlignment);
736 unsigned KnownIDs[] = {
737 LLVMContext::MD_tbaa,
738 LLVMContext::MD_range,
739 LLVMContext::MD_invariant_load,
740 LLVMContext::MD_alias_scope,
741 LLVMContext::MD_noalias,
742 LLVMContext::MD_nonnull,
743 LLVMContext::MD_align,
744 LLVMContext::MD_dereferenceable,
745 LLVMContext::MD_dereferenceable_or_null,
746 LLVMContext::MD_access_group,
747 LLVMContext::MD_noundef,
750 for (
unsigned ID : KnownIDs)
759 Value *NewInVal =
LI->getOperand(0);
760 if (NewInVal != InVal)
779 cast<LoadInst>(IncValue)->setVolatile(
false);
791 if (
Instruction *TI = Phi.getParent()->getTerminator())
798 unsigned NumIncomingValues = Phi.getNumIncomingValues();
799 if (NumIncomingValues < 3)
803 Type *NarrowType =
nullptr;
804 for (
Value *V : Phi.incoming_values()) {
805 if (
auto *Zext = dyn_cast<ZExtInst>(V)) {
806 NarrowType = Zext->getSrcTy();
816 unsigned NumZexts = 0;
817 unsigned NumConsts = 0;
818 for (
Value *V : Phi.incoming_values()) {
819 if (
auto *Zext = dyn_cast<ZExtInst>(V)) {
821 if (Zext->getSrcTy() != NarrowType || !Zext->hasOneUser())
823 NewIncoming.
push_back(Zext->getOperand(0));
825 }
else if (
auto *
C = dyn_cast<Constant>(V)) {
844 if (NumConsts == 0 || NumZexts < 2)
851 Phi.getName() +
".shrunk");
852 for (
unsigned I = 0;
I != NumIncomingValues; ++
I)
853 NewPhi->
addIncoming(NewIncoming[
I], Phi.getIncomingBlock(
I));
871 if (isa<GetElementPtrInst>(FirstInst))
873 if (isa<LoadInst>(FirstInst))
875 if (isa<InsertValueInst>(FirstInst))
877 if (isa<ExtractValueInst>(FirstInst))
885 Type *CastSrcTy =
nullptr;
887 if (isa<CastInst>(FirstInst)) {
893 if (!shouldChangeType(PN.
getType(), CastSrcTy))
896 }
else if (isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst)) {
899 ConstantOp = dyn_cast<Constant>(FirstInst->
getOperand(1));
909 if (!
I || !
I->hasOneUser() || !
I->isSameOperationAs(FirstInst))
912 if (
I->getOperand(0)->getType() != CastSrcTy)
914 }
else if (
I->getOperand(1) != ConstantOp) {
932 Value *NewInVal = cast<Instruction>(V)->getOperand(0);
933 if (NewInVal != InVal)
950 if (
CastInst *FirstCI = dyn_cast<CastInst>(FirstInst)) {
957 if (
BinaryOperator *BinOp = dyn_cast<BinaryOperator>(FirstInst)) {
962 BinOp->andIRFlags(V);
968 CmpInst *CIOp = cast<CmpInst>(FirstInst);
982 if (!PotentiallyDeadPHIs.
insert(PN).second)
986 if (PotentiallyDeadPHIs.
size() == 16)
1001 if (!ValueEqualPHIs.
insert(PN).second)
1005 if (ValueEqualPHIs.
size() == 16)
1011 if (
PHINode *OpPN = dyn_cast<PHINode>(
Op)) {
1017 }
else if (
Op != NonPhiInVal)
1027 assert(isa<IntegerType>(PN.
getType()) &&
"Expect only integer type phi");
1029 if (
auto *ConstVA = dyn_cast<ConstantInt>(V))
1030 if (!ConstVA->isZero())
1032 return ConstantInt::get(cast<IntegerType>(PN.
getType()), 1);
1036struct PHIUsageRecord {
1042 : PHIId(Pn), Shift(Sh), Inst(
User) {}
1045 if (PHIId <
RHS.PHIId)
return true;
1046 if (PHIId >
RHS.PHIId)
return false;
1047 if (Shift <
RHS.Shift)
return true;
1048 if (Shift >
RHS.Shift)
return false;
1054struct LoweredPHIRecord {
1059 LoweredPHIRecord(
PHINode *Phi,
unsigned Sh,
Type *Ty)
1060 : PN(
Phi), Shift(Sh), Width(Ty->getPrimitiveSizeInBits()) {}
1063 LoweredPHIRecord(
PHINode *Phi,
unsigned Sh) : PN(
Phi), Shift(Sh), Width(0) {}
1071 return LoweredPHIRecord(
nullptr, 0);
1074 return LoweredPHIRecord(
nullptr, 1);
1081 const LoweredPHIRecord &RHS) {
1110 PHIsInspected.
insert(&FirstPhi);
1112 for (
unsigned PHIId = 0; PHIId != PHIsToSlice.
size(); ++PHIId) {
1113 PHINode *PN = PHIsToSlice[PHIId];
1125 if (
II->getParent() != BB)
1137 for (
auto *Pred : PN->
blocks())
1138 if (Pred->getFirstInsertionPt() == Pred->end())
1145 if (
PHINode *UserPN = dyn_cast<PHINode>(UserI)) {
1146 if (PHIsInspected.
insert(UserPN).second)
1152 if (isa<TruncInst>(UserI)) {
1153 PHIUsers.
push_back(PHIUsageRecord(PHIId, 0, UserI));
1158 if (UserI->
getOpcode() != Instruction::LShr ||
1165 if (cast<ConstantInt>(UserI->
getOperand(1))->getValue().uge(SizeInBits))
1168 unsigned Shift = cast<ConstantInt>(UserI->
getOperand(1))->getZExtValue();
1174 if (PHIUsers.
empty())
1182 for (
unsigned I = 1;
I != PHIsToSlice.
size(); ++
I)
dbgs()
1183 <<
"AND USER PHI #" <<
I <<
": " << *PHIsToSlice[
I] <<
'\n');
1193 for (
unsigned UserI = 0, UserE = PHIUsers.
size(); UserI != UserE; ++UserI) {
1194 unsigned PHIId = PHIUsers[UserI].PHIId;
1195 PHINode *PN = PHIsToSlice[PHIId];
1196 unsigned Offset = PHIUsers[UserI].Shift;
1197 Type *Ty = PHIUsers[UserI].Inst->getType();
1203 if ((EltPHI = ExtractedVals[LoweredPHIRecord(PN,
Offset, Ty)]) ==
nullptr) {
1210 "Truncate didn't shrink phi?");
1215 Value *&PredVal = PredValues[Pred];
1230 if (
PHINode *InPHI = dyn_cast<PHINode>(PN)) {
1233 if (
Value *Res = ExtractedVals[LoweredPHIRecord(InPHI,
Offset, Ty)]) {
1245 Res, ConstantInt::get(InVal->
getType(),
Offset),
"extract");
1254 if (
PHINode *OldInVal = dyn_cast<PHINode>(InVal))
1255 if (PHIsInspected.
count(OldInVal)) {
1257 find(PHIsToSlice, OldInVal) - PHIsToSlice.
begin();
1259 PHIUsageRecord(RefPHIId,
Offset, cast<Instruction>(Res)));
1266 << *EltPHI <<
'\n');
1267 ExtractedVals[LoweredPHIRecord(PN,
Offset, Ty)] = EltPHI;
1312 SuccForValue[
C] = Succ;
1315 if (
auto *BI = dyn_cast<BranchInst>(IDom->getTerminator())) {
1316 if (BI->isUnconditional())
1319 Cond = BI->getCondition();
1322 }
else if (
auto *SI = dyn_cast<SwitchInst>(IDom->getTerminator())) {
1323 Cond = SI->getCondition();
1324 ++SuccCount[SI->getDefaultDest()];
1325 for (
auto Case : SI->cases())
1326 AddSucc(Case.getCaseValue(), Case.getCaseSuccessor());
1336 std::optional<bool> Invert;
1338 auto *Input = cast<ConstantInt>(std::get<0>(Pair));
1344 auto It = SuccForValue.
find(Input);
1345 return It != SuccForValue.
end() && SuccCount[It->second] == 1 &&
1352 if (IsCorrectInput(Input))
1353 NeedsInvert =
false;
1360 if (Invert && *Invert != NeedsInvert)
1363 Invert = NeedsInvert;
1373 if (InsertPt != BB->
end()) {
1393 auto MatchOuterIV = [&](
Value *V1,
Value *V2) {
1397 IvNext = cast<Instruction>(V2);
1408 Value *Iv2Start, *Iv2Step;
1413 auto *BO = dyn_cast<BinaryOperator>(IvNext);
1417 if (Iv2Start != Identity)
1422 auto *
GEP = cast<GEPOperator>(IvNext);
1423 return Builder.
CreateGEP(
GEP->getSourceElementType(), Start, Iv2,
"",
1424 cast<GEPOperator>(IvNext)->getNoWrapFlags());
1427 assert(BO->isCommutative() &&
"Must be commutative");
1429 cast<Instruction>(Res)->copyIRFlags(BO);
1449 if (Inst0 && Inst1 && Inst0->getOpcode() == Inst1->getOpcode() &&
1450 Inst0->hasOneUser())
1464 if (IV0 != IV0Stripped &&
1466 return !CheckedIVs.insert(IV).second ||
1467 IV0Stripped == IV->stripPointerCasts();
1481 if (
PHINode *PU = dyn_cast<PHINode>(PHIUser)) {
1483 PotentiallyDeadPHIs.
insert(&PN);
1495 (isa<BinaryOperator>(PHIUser) || isa<UnaryOperator>(PHIUser) ||
1496 isa<GetElementPtrInst>(PHIUser)) &&
1517 auto *CmpInst = dyn_cast<ICmpInst>(U);
1521 if (U->hasOneUse() && match(U, m_c_Or(m_Specific(&PN), m_Value()))) {
1522 DropPoisonFlags.push_back(cast<Instruction>(U));
1523 CmpInst = dyn_cast<ICmpInst>(U->user_back());
1533 if (AllUsesOfPhiEndsInCmp) {
1535 bool MadeChange =
false;
1542 if (NonZeroConst != VA) {
1546 I->dropPoisonGeneratingFlags();
1567 while (InValNo != NumIncomingVals &&
1568 isa<PHINode>(PN.getIncomingValue(InValNo)))
1571 Value *NonPhiInVal =
1572 InValNo != NumIncomingVals ? PN.getIncomingValue(InValNo) :
nullptr;
1577 for (++InValNo; InValNo != NumIncomingVals; ++InValNo) {
1578 Value *OpVal = PN.getIncomingValue(InValNo);
1579 if (OpVal != NonPhiInVal && !isa<PHINode>(OpVal))
1586 if (InValNo == NumIncomingVals) {
1589 return replaceInstUsesWith(PN, NonPhiInVal);
1597 auto Res = PredOrder.try_emplace(PN.getParent());
1599 const auto &Preds = Res.first->second;
1600 for (
unsigned I = 0, E = PN.getNumIncomingValues();
I != E; ++
I) {
1604 Value *VA = PN.getIncomingValue(
I);
1605 unsigned J = PN.getBasicBlockIndex(BBB);
1606 Value *
VB = PN.getIncomingValue(J);
1607 PN.setIncomingBlock(
I, BBB);
1608 PN.setIncomingValue(
I, VB);
1609 PN.setIncomingBlock(J, BBA);
1610 PN.setIncomingValue(J, VA);
1625 if (&IdenticalPN == &PN)
1630 if (!PN.isIdenticalToWhenDefined(&IdenticalPN))
1634 return replaceInstUsesWith(PN, &IdenticalPN);
1641 if (PN.getType()->isIntegerTy() &&
1642 !
DL.isLegalInteger(PN.getType()->getPrimitiveSizeInBits()))
1643 if (
Instruction *Res = SliceUpIllegalIntegerPHI(PN))
1648 return replaceInstUsesWith(PN, V);
1651 return replaceInstUsesWith(PN, Res);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file provides internal interfaces used to implement the InstCombine.
static ConstantInt * getAnyNonZeroConstInt(PHINode &PN)
Return an existing non-zero constant if this phi node has one, otherwise return constant 1.
static Value * foldDependentIVs(PHINode &PN, IRBuilderBase &Builder)
static bool isDeadPHICycle(PHINode *PN, SmallPtrSetImpl< PHINode * > &PotentiallyDeadPHIs)
Return true if this PHI node is only used by a PHI node cycle that is dead.
static bool isSafeAndProfitableToSinkLoad(LoadInst *L)
Return true if we know that it is safe to sink the load out of the block that defines it.
static Value * simplifyUsingControlFlow(InstCombiner &Self, PHINode &PN, const DominatorTree &DT)
static bool PHIsEqualValue(PHINode *PN, Value *&NonPhiInVal, SmallPtrSetImpl< PHINode * > &ValueEqualPHIs)
Return true if this phi node is always equal to NonPhiInVal.
static cl::opt< unsigned > MaxNumPhis("instcombine-max-num-phis", cl::init(512), cl::desc("Maximum number phis to handle in intptr/ptrint folding"))
This file provides the interface for the instcombine pass implementation.
uint64_t IntrinsicInst * II
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static const uint32_t IV[8]
an instruction to allocate memory on the stack
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
BinaryOps getOpcode() const
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
This is the base class for all instructions that perform data casts.
static CastInst * CreatePointerCast(Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Create a BitCast, AddrSpaceCast or a PtrToInt cast instruction.
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
static CastInst * CreateZExtOrBitCast(Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Create a ZExt or BitCast cast instruction.
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
This class is the base class for the comparison instructions.
static bool isEquality(Predicate pred)
Determine if this is an equals/not equals predicate.
static CmpInst * Create(OtherOps Op, Predicate Pred, Value *S1, Value *S2, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Construct a compare instruction, given the opcode, the predicate and the two operands.
Predicate getPredicate() const
Return the predicate for this instruction.
OtherOps getOpcode() const
Get the opcode casted to the right type.
static Constant * getNot(Constant *C)
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
This class represents an Operation in the Expression.
unsigned getPointerSizeInBits(unsigned AS=0) const
Layout pointer size, in bits FIXME: The defaults need to be removed once all of the backends/clients ...
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
iterator find(const_arg_type_t< KeyT > Val)
DomTreeNodeBase * getIDom() const
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags all()
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Type * getSourceElementType() const
Common base class shared among various IRBuilders.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Value * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())
Value * CreateNot(Value *V, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
static InsertValueInst * Create(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Instruction * foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN)
If we have something like phi [insertvalue(a,b,0), insertvalue(c,d,0)], turn this into a phi[a,...
Instruction * foldPHIArgBinOpIntoPHI(PHINode &PN)
If we have something like phi [add (a,b), add(a,c)] and if a/b/c and the adds all have a single user,...
Constant * getLosslessUnsignedTrunc(Constant *C, Type *TruncTy)
Instruction * eraseInstFromFunction(Instruction &I) override
Combiner aware instruction erasure.
Instruction * visitPHINode(PHINode &PN)
Instruction * foldPHIArgOpIntoPHI(PHINode &PN)
Try to rotate an operation below a PHI node, using PHI nodes for its operands.
Instruction * foldPHIArgZextsIntoPHI(PHINode &PN)
TODO: This function could handle other cast types, but then it might require special-casing a cast fr...
Instruction * foldPHIArgLoadIntoPHI(PHINode &PN)
bool foldIntegerTypedPHI(PHINode &PN)
If an integer typed PHI has only one use which is an IntToPtr operation, replace the PHI with an exis...
Instruction * foldPHIArgIntToPtrToPHI(PHINode &PN)
Instruction * SliceUpIllegalIntegerPHI(PHINode &PN)
This is an integer PHI and we know that it has an illegal type: see if it is only used by trunc or tr...
Instruction * foldPHIArgGEPIntoPHI(PHINode &PN)
void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN)
Helper function for FoldPHIArgXIntoPHI() to set debug location for the folded operation.
Instruction * foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN)
If we have something like phi [extractvalue(a,0), extractvalue(b,0)], turn this into a phi[a,...
The core instruction combiner logic.
Instruction * InsertNewInstBefore(Instruction *New, BasicBlock::iterator Old)
Inserts an instruction New before instruction Old.
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
const SimplifyQuery & getSimplifyQuery() const
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void applyMergedLocation(DILocation *LocA, DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
This is an important class for using LLVM in a threaded context.
An instruction for reading from memory.
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
bool isVolatile() const
Return true if this is a load from a volatile memory location.
Align getAlign() const
Return the alignment of the access that is being performed.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
iterator_range< user_iterator > users()
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N uses or more.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
bool isSwiftError() const
Return true if this value is a swifterror value.
LLVMContext & getContext() const
All values hold a context through their type.
StringRef getName() const
Return a constant reference to the value's name.
const ParentTy * getParent() const
self_iterator getIterator()
@ C
The default llvm calling convention, compatible with C.
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_GEP(const OperandTypes &...Ops)
Matches GetElementPtrInst.
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
initializer< Ty > init(const Ty &Val)
NodeAddr< PhiNode * > Phi
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
DWARFExpression::Operation Op
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
This struct is a compact representation of a valid (non-zero power of two) alignment.
static bool isEqual(const LoweredPHIRecord &LHS, const LoweredPHIRecord &RHS)
static unsigned getHashValue(const LoweredPHIRecord &Val)
static LoweredPHIRecord getEmptyKey()
static LoweredPHIRecord getTombstoneKey()
An information struct used to provide DenseMap with the various necessary components for a given valu...
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
SimplifyQuery getWithInstruction(const Instruction *I) const