Lines Matching +full:actions +full:- +full:builder
1 //===- CodeGenPrepare.cpp - Prepare a function for code generation --------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 // SelectionDAG-based code generation. This works around limitations in it's
11 // basic-block-at-a-time approach. It should eventually be removed.
13 //===----------------------------------------------------------------------===//
44 #include "llvm/Config/llvm-config.h"
137 "disable-cgp-branch-opts", cl::Hidden, cl::init(false),
141 DisableGCOpts("disable-cgp-gc-opts", cl::Hidden, cl::init(false),
145 DisableSelectToBranch("disable-cgp-select2branch", cl::Hidden,
150 AddrSinkUsingGEPs("addr-sink-using-gep", cl::Hidden, cl::init(true),
154 EnableAndCmpSinking("enable-andcmp-sinking", cl::Hidden, cl::init(true),
158 "disable-cgp-store-extract", cl::Hidden, cl::init(false),
162 "stress-cgp-store-extract", cl::Hidden, cl::init(false),
166 "disable-cgp-ext-ld-promotion", cl::Hidden, cl::init(false),
167 cl::desc("Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
171 "stress-cgp-ext-ld-promotion", cl::Hidden, cl::init(false),
172 cl::desc("Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
176 "disable-preheader-prot", cl::Hidden, cl::init(false),
180 "profile-guided-section-prefix", cl::Hidden, cl::init(true),
184 "profile-unknown-in-special-section", cl::Hidden,
194 "bbsections-guided-section-prefix", cl::Hidden, cl::init(true),
195 cl::desc("Use the basic-block-sections profile to determine the text "
197 "basic-block-sections profile will be placed in `.text.hot` "
203 "cgp-freq-ratio-to-skip-merge", cl::Hidden, cl::init(2),
208 "force-split-store", cl::Hidden, cl::init(false),
212 "cgp-type-promotion-merge", cl::Hidden,
218 "disable-complex-addr-modes", cl::Hidden, cl::init(false),
223 AddrSinkNewPhis("addr-sink-new-phis", cl::Hidden, cl::init(false),
227 "addr-sink-new-select", cl::Hidden, cl::init(true),
231 "addr-sink-combine-base-reg", cl::Hidden, cl::init(true),
235 "addr-sink-combine-base-gv", cl::Hidden, cl::init(true),
239 "addr-sink-combine-base-offs", cl::Hidden, cl::init(true),
243 "addr-sink-combine-scaled-reg", cl::Hidden, cl::init(true),
247 EnableGEPOffsetSplit("cgp-split-large-offset-gep", cl::Hidden,
252 "cgp-icmp-eq2icmp-st", cl::Hidden, cl::init(false),
256 VerifyBFIUpdates("cgp-verify-bfi-updates", cl::Hidden, cl::init(false),
261 OptimizePhiTypes("cgp-optimize-phi-types", cl::Hidden, cl::init(true),
265 HugeFuncThresholdInCGPP("cgpp-huge-func", cl::init(10000), cl::Hidden,
269 MaxAddressUsersToScan("cgp-max-address-users-to-scan", cl::init(100),
274 DisableDeletePHIs("disable-cgp-delete-phis", cl::Hidden, cl::init(false),
293 // in a Basic Block. So we should re-iterate instructions
323 /// Keeps track of non-local addresses that have been sunk into a block.
406 CurInstIterator = BB->begin();
514 CGP.SubtargetInfo = TM->getSubtargetImpl(F);
515 CGP.TLI = CGP.SubtargetInfo->getTargetLowering();
516 CGP.TRI = CGP.SubtargetInfo->getRegisterInfo();
525 CGP.BBSectionsProfileReader = BBSPRWP ? &BBSPRWP->getBBSPR() : nullptr;
562 SubtargetInfo = TM->getSubtargetImpl(F);
563 TLI = SubtargetInfo->getTargetLowering();
564 TRI = SubtargetInfo->getRegisterInfo();
581 // Use the basic-block-sections profile to promote hot functions to .text.hot
584 BBSectionsProfileReader->isFunctionHot(F.getName())) {
591 PSI->isFunctionHotInCallGraph(&F, *BFI))
596 else if (PSI->isFunctionColdInCallGraph(&F, *BFI) ||
599 else if (ProfileUnknownInSpecialSection && PSI->hasPartialSampleProfile() &&
600 PSI->isFunctionHotnessUnknown(F))
606 if (!OptSize && !PSI->hasHugeWorkingSetSize() && TLI->isSlowDivBypassed()) {
608 TLI->getBypassSlowDivWidths();
613 BasicBlock *Next = BB->getNextNode();
644 LI->releaseMemory();
645 LI->analyze(getDT(F));
698 LI->verify(getDT(F));
703 I->deleteValue();
764 // Do this last to clean up use-before-def scenarios introduced by other
785 Value *Operand = Assume->getOperand(0);
786 Assume->eraseFromParent();
798 /// GEP-tracking data strcutures.
809 auto VecI = LargeOffsetGEPMap.find(GEP->getPointerOperand());
813 auto &GEPVector = VecI->second;
848 BasicBlock *SinglePred = BB->getSinglePredecessor();
851 if (!SinglePred || SinglePred == BB || BB->hasAddressTaken())
855 if (DT && !DT->isReachableFromEntry(BB))
858 BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
859 if (Term && !Term->isConditional()) {
889 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
890 if (!BI || !BI->isUnconditional())
895 BasicBlock::iterator BBI = BI->getIterator();
896 if (BBI != BB->begin()) {
897 --BBI;
899 if (BBI == BB->begin())
901 --BBI;
908 BasicBlock *DestBB = BI->getSuccessor(0);
920 /// edges in ways that are non-optimal for isel. Start by eliminating these
924 SmallVector<Loop *, 16> LoopList(LI->begin(), LI->end());
928 if (BasicBlock *Preheader = L->getLoopPreheader())
967 !(BB->getSinglePredecessor() &&
968 BB->getSinglePredecessor()->getSingleSuccessor()))
975 if (isa<CallBrInst>(Pred->getTerminator()) &&
988 BasicBlock *Pred = BB->getUniquePredecessor();
989 if (!Pred || !(isa<SwitchInst>(Pred->getTerminator()) ||
990 isa<IndirectBrInst>(Pred->getTerminator())))
993 if (BB->getTerminator() != &*BB->getFirstNonPHIOrDbg())
1007 if (!isa<PHINode>(DestBB->begin()))
1018 if (llvm::all_of(DestBB->phis(), [&](const PHINode &DestPN) {
1031 BlockFrequency PredFreq = BFI->getBlockFreq(Pred);
1032 BlockFrequency BBFreq = BFI->getBlockFreq(BB);
1035 if (SameValueBB->getUniquePredecessor() == Pred &&
1037 BBFreq += BFI->getBlockFreq(SameValueBB);
1044 /// unconditional branch between them, and BB contains no other non-phi
1051 for (const PHINode &PN : BB->phis()) {
1054 if (UI->getParent() != DestBB || !isa<PHINode>(UI))
1059 if (UI->getParent() == DestBB) {
1061 for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) {
1062 Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I));
1063 if (Insn && Insn->getParent() == BB &&
1064 Insn->getParent() != UPN->getIncomingBlock(I))
1074 const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin());
1080 if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
1082 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1083 BBPreds.insert(BBPN->getIncomingBlock(i));
1089 for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) {
1090 BasicBlock *Pred = DestBBPN->getIncomingBlock(i);
1092 for (const PHINode &PN : DestBB->phis()) {
1098 if (V2PN->getParent() == BB)
1099 V2 = V2PN->getIncomingValueForBlock(Pred);
1117 for (Value::user_iterator UI = OldI->user_begin(), E = OldI->user_end();
1121 FreshBBs.insert(User->getParent());
1124 Old->replaceAllUsesWith(New);
1130 BranchInst *BI = cast<BranchInst>(BB->getTerminator());
1131 BasicBlock *DestBB = BI->getSuccessor(0);
1133 LLVM_DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n"
1138 if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
1159 for (PHINode &PN : DestBB->phis()) {
1166 if (InValPhi && InValPhi->getParent() == BB) {
1168 for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i)
1169 PN.addIncoming(InValPhi->getIncomingValue(i),
1170 InValPhi->getIncomingBlock(i));
1174 if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
1175 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1176 PN.addIncoming(InVal, BBPN->getIncomingBlock(i));
1185 if (BI->hasMetadata(LLVMContext::MD_loop)) {
1187 Pred->getTerminator()->copyMetadata(*BI, LLVMContext::MD_loop);
1192 BB->replaceAllUsesWith(DestBB);
1193 BB->eraseFromParent();
1210 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1211 ThisRelocate->getDerivedPtrIndex());
1230 RelocateInstMap[MaybeBase->second].push_back(I);
1238 for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
1240 auto *Op = dyn_cast<ConstantInt>(GEP->getOperand(i));
1241 if (!Op || Op->getZExtValue() > 20)
1245 for (unsigned i = 1; i < GEP->getNumOperands(); i++)
1246 OffsetV.push_back(GEP->getOperand(i));
1262 for (auto R = RelocatedBase->getParent()->getFirstInsertionPt();
1265 if (RI->getStatepoint() == RelocatedBase->getStatepoint())
1266 if (RI->getBasePtrIndex() == RelocatedBase->getBasePtrIndex()) {
1267 RelocatedBase->moveBefore(RI->getIterator());
1273 assert(ToReplace->getBasePtrIndex() == RelocatedBase->getBasePtrIndex() &&
1275 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1280 if (RelocatedBase->getParent() != ToReplace->getParent()) {
1288 Value *Base = ToReplace->getBasePtr();
1289 auto *Derived = dyn_cast<GetElementPtrInst>(ToReplace->getDerivedPtr());
1290 if (!Derived || Derived->getPointerOperand() != Base)
1297 // Create a Builder and replace the target callsite with a gep
1298 assert(RelocatedBase->getNextNode() &&
1302 IRBuilder<> Builder(RelocatedBase->getNextNode());
1303 Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
1328 if (RelocatedBase->getType() != Base->getType()) {
1330 Builder.CreateBitCast(RelocatedBase, Base->getType());
1333 Builder.CreateGEP(Derived->getSourceElementType(), ActualRelocatedBase,
1335 Replacement->takeName(ToReplace);
1340 if (Replacement->getType() != ToReplace->getType()) {
1342 Builder.CreateBitCast(Replacement, ToReplace->getType());
1344 ToReplace->replaceAllUsesWith(ActualReplacement);
1345 ToReplace->eraseFromParent();
1398 BasicBlock *DefBB = CI->getParent();
1400 /// InsertedCasts - Only insert a cast in each block once.
1404 for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end();
1411 BasicBlock *UserBB = User->getParent();
1413 UserBB = PN->getIncomingBlock(TheUse);
1421 if (User->isEHPad())
1425 // allow non-PHI instructions before the terminator, we can't sink the
1427 if (UserBB->getTerminator()->isEHPad())
1438 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1439 assert(InsertPt != UserBB->end());
1440 InsertedCast = cast<CastInst>(CI->clone());
1441 InsertedCast->insertBefore(*UserBB, InsertPt);
1451 if (CI->use_empty()) {
1453 CI->eraseFromParent();
1461 /// one pointer type to another, i32->i8 on PPC), sink it into user blocks to
1467 // Sink only "cheap" (or nop) address-space casts. This is a weaker condition
1470 if (!TLI.isFreeAddrSpaceCast(ASC->getSrcAddressSpace(),
1471 ASC->getDestAddressSpace()))
1476 EVT SrcVT = TLI.getValueType(DL, CI->getOperand(0)->getType());
1477 EVT DstVT = TLI.getValueType(DL, CI->getType());
1479 // This is an fp<->int conversion?
1491 if (TLI.getTypeAction(CI->getContext(), SrcVT) ==
1493 SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
1494 if (TLI.getTypeAction(CI->getContext(), DstVT) ==
1496 DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);
1528 const Loop *L = LI->getLoopFor(PN->getParent());
1529 if (!L || L->getHeader() != PN->getParent() || !L->getLoopLatch())
1532 dyn_cast<Instruction>(PN->getIncomingValueForBlock(L->getLoopLatch()));
1533 if (!IVInc || LI->getLoopFor(IVInc->getParent()) != L)
1552 return IVInc->first == I;
1563 const Loop *L = LI->getLoopFor(BO->getParent());
1566 if (LI->getLoopFor(Cmp->getParent()) != L)
1572 auto &DT = getDT(*BO->getParent()->getParent());
1573 if (DT.dominates(Cmp->getParent(), BO->getParent()))
1579 return BO->hasOneUse() && DT.dominates(Cmp->getParent(), L->getLoopLatch());
1581 if (BO->getParent() != Cmp->getParent() && !IsReplacableIVIncrement(BO)) {
1582 // We used to use a dominator tree here to allow multi-block optimization.
1588 // 3. Use of a dominator tree could cause large compile-time regression.
1590 // run-loop. The recomputing is probably unnecessary in many cases, so if
1595 // - We can speculate IV increment anywhere in the loop (as long as the
1597 // - Upon computing Cmp, we effectively compute something equivalent to the
1603 // We allow matching the canonical IR (add X, C) back to (usubo X, -C).
1604 if (BO->getOpcode() == Instruction::Add &&
1612 for (Instruction &Iter : *Cmp->getParent()) {
1615 if ((BO->getOpcode() != Instruction::Xor && &Iter == BO) || &Iter == Cmp) {
1622 IRBuilder<> Builder(InsertPt);
1623 Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
1624 if (BO->getOpcode() != Instruction::Xor) {
1625 Value *Math = Builder.CreateExtractValue(MathOV, 0, "math");
1628 assert(BO->hasOneUse() &&
1630 Value *OV = Builder.CreateExtractValue(MathOV, 1, "ov");
1632 Cmp->eraseFromParent();
1633 BO->eraseFromParent();
1637 /// Match special-case patterns that check for unsigned add overflow.
1640 // Add = add A, 1; Cmp = icmp eq A,-1 (overflow if A is max val)
1641 // Add = add A,-1; Cmp = icmp ne A, 0 (overflow if A is non-zero)
1642 Value *A = Cmp->getOperand(0), *B = Cmp->getOperand(1);
1644 // We are not expecting non-canonical/degenerate code. Just bail out.
1648 ICmpInst::Predicate Pred = Cmp->getPredicate();
1650 B = ConstantInt::get(B->getType(), 1);
1652 B = Constant::getAllOnesValue(B->getType());
1658 for (User *U : A->users()) {
1678 A = Add->getOperand(0);
1679 B = Add->getOperand(1);
1683 if (!TLI->shouldFormOverflowOp(ISD::UADDO,
1684 TLI->getValueType(*DL, Add->getType()),
1685 Add->hasNUsesOrMore(EdgeCase ? 1 : 2)))
1691 if (Add->getParent() != Cmp->getParent() && !Add->hasOneUse())
1698 // Reset callers - do not crash by iterating over a dead instruction.
1705 // We are not expecting non-canonical/degenerate code. Just bail out.
1706 Value *A = Cmp->getOperand(0), *B = Cmp->getOperand(1);
1711 ICmpInst::Predicate Pred = Cmp->getPredicate();
1716 // Convert special-case: (A == 0) is the same as (A u< 1).
1718 B = ConstantInt::get(B->getType(), 1);
1721 // Convert special-case: (A != 0) is the same as (0 u< A).
1734 for (User *U : CmpVariableOperand->users()) {
1735 // A - B, A u< B --> usubo(A, B)
1741 // A + (-C), A u< C (canonicalized form of (sub A, C))
1744 match(B, m_APInt(CmpC)) && *AddC == -(*CmpC)) {
1752 if (!TLI->shouldFormOverflowOp(ISD::USUBO,
1753 TLI->getValueType(*DL, Sub->getType()),
1754 Sub->hasNUsesOrMore(1)))
1757 if (!replaceMathCmpWithIntrinsic(Sub, Sub->getOperand(0), Sub->getOperand(1),
1761 // Reset callers - do not crash by iterating over a dead instruction.
1776 // Avoid sinking soft-FP comparisons, since this can move them into a loop.
1784 for (Value::user_iterator UI = Cmp->user_begin(), E = Cmp->user_end();
1797 BasicBlock *UserBB = User->getParent();
1798 BasicBlock *DefBB = Cmp->getParent();
1808 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1809 assert(InsertPt != UserBB->end());
1810 InsertedCmp = CmpInst::Create(Cmp->getOpcode(), Cmp->getPredicate(),
1811 Cmp->getOperand(0), Cmp->getOperand(1), "");
1812 InsertedCmp->insertBefore(*UserBB, InsertPt);
1814 InsertedCmp->setDebugLoc(Cmp->getDebugLoc());
1824 if (Cmp->use_empty()) {
1825 Cmp->eraseFromParent();
1856 ICmpInst::Predicate Pred = Cmp->getPredicate();
1862 for (User *U : Cmp->users()) {
1865 if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == Cmp)
1870 // This is a cheap/incomplete check for dominance - just match a single
1872 BasicBlock *CmpBB = Cmp->getParent();
1873 BasicBlock *DomBB = CmpBB->getSinglePredecessor();
1882 if (!match(DomBB->getTerminator(), m_Br(m_Value(DomCond), TrueBB, FalseBB)))
1887 Value *CmpOp0 = Cmp->getOperand(0), *CmpOp1 = Cmp->getOperand(1);
1901 for (User *U : Cmp->users()) {
1903 assert(BI->isConditional() && "Must be conditional");
1904 BI->swapSuccessors();
1909 SI->swapValues();
1910 SI->swapProfMetadata();
1915 Cmp->setPredicate(CmpInst::getSwappedPredicate(DomPred));
1922 Value *Op0 = Cmp->getOperand(0);
1923 Value *Op1 = Cmp->getOperand(1);
1924 if (!Op0->getType()->isIntegerTy() || isa<Constant>(Op0) ||
1933 for (const User *U : Op0->users()) {
1940 GoodToSwap--;
1944 Cmp->swapOperands();
1957 EVT VT = TLI.getValueType(DL, Cmp->getOperand(0)->getType());
1959 TLI.isCondCodeLegal(getFCmpCondCode(FCmp->getPredicate()),
1968 fcmpToClassTest(FCmp->getPredicate(), *FCmp->getParent()->getParent(),
1969 FCmp->getOperand(0), FCmp->getOperand(1));
1976 IRBuilder<> Builder(Cmp);
1977 Value *IsFPClass = Builder.createIsFPClass(ClassVal, ClassTest);
1978 Cmp->replaceAllUsesWith(IsFPClass);
2018 if (PN->getNumIncomingValues() != 2)
2022 Loop *L = LI->getLoopFor(PN->getParent());
2023 if (!L || !L->getLoopPreheader() || !L->getLoopLatch())
2027 if (!L->contains(Rem))
2031 if (!L->isLoopInvariant(RemAmt))
2042 if (!match(LoopIncrInfo->second, m_One()))
2046 if (!match(LoopIncrInfo->first, m_c_NUWAdd(m_Specific(PN), m_Value())))
2063 // ->
2078 // Only non-constant remainder as the extra IV is probably not profitable
2091 Loop *L = LI->getLoopFor(LoopIncrPN->getParent());
2092 Value *Start = LoopIncrPN->getIncomingValueForBlock(L->getLoopPreheader());
2101 // Without dom-condition/assumption cache we aren't likely to get much out
2116 Type *Ty = Rem->getType();
2117 IRBuilder<> Builder(Rem->getContext());
2119 Builder.SetInsertPoint(LoopIncrPN);
2120 PHINode *NewRem = Builder.CreatePHI(Ty, 2);
2122 Builder.SetInsertPoint(cast<Instruction>(
2123 LoopIncrPN->getIncomingValueForBlock(L->getLoopLatch())));
2125 Value *RemAdd = Builder.CreateNUWAdd(NewRem, ConstantInt::get(Ty, 1));
2126 Value *RemCmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, RemAdd, RemAmt);
2128 Builder.CreateSelect(RemCmp, Constant::getNullValue(Ty), RemAdd);
2130 NewRem->addIncoming(Start, L->getLoopPreheader());
2131 NewRem->addIncoming(RemSel, L->getLoopLatch());
2134 FreshBBs.insert(LoopIncrPN->getParent());
2135 FreshBBs.insert(L->getLoopLatch());
2136 FreshBBs.insert(Rem->getParent());
2138 FreshBBs.insert(cast<Instruction>(AddInst)->getParent());
2140 Rem->eraseFromParent();
2141 if (AddInst && AddInst->use_empty())
2142 cast<Instruction>(AddInst)->eraseFromParent();
2163 auto *II = cast<IntrinsicInst>(Cmp->getOperand(0));
2167 Cmp->setOperand(1, ConstantInt::get(II->getType(), 2));
2168 Cmp->setPredicate(ICmpInst::ICMP_ULT);
2170 Cmp->setPredicate(ICmpInst::ICMP_UGT);
2209 // Double-check that we're not trying to optimize an instruction that was
2216 if (AndI->hasOneUse() &&
2217 AndI->getParent() == cast<Instruction>(*AndI->user_begin())->getParent())
2222 if (!isa<ConstantInt>(AndI->getOperand(0)) &&
2223 !isa<ConstantInt>(AndI->getOperand(1)) &&
2224 AndI->getOperand(0)->hasOneUse() && AndI->getOperand(1)->hasOneUse())
2227 for (auto *U : AndI->users()) {
2234 auto *CmpC = dyn_cast<ConstantInt>(User->getOperand(1));
2235 if (!CmpC || !CmpC->isZero())
2243 LLVM_DEBUG(AndI->getParent()->dump());
2248 for (Value::user_iterator UI = AndI->user_begin(), E = AndI->user_end();
2260 User->getParent() == AndI->getParent() ? AndI : User;
2262 Instruction::And, AndI->getOperand(0), AndI->getOperand(1), "",
2263 InsertPt->getIterator());
2265 InsertedAnd->setDebugLoc(AndI->getDebugLoc());
2270 LLVM_DEBUG(User->getParent()->dump());
2274 AndI->eraseFromParent();
2285 if (User->getOpcode() != Instruction::And ||
2286 !isa<ConstantInt>(User->getOperand(1)))
2289 const APInt &Cimm = cast<ConstantInt>(User->getOperand(1))->getValue();
2302 BasicBlock *UserBB = User->getParent();
2307 for (Value::user_iterator TruncUI = TruncI->user_begin(),
2308 TruncE = TruncI->user_end();
2317 int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode());
2327 ISDOpcode, TLI.getValueType(DL, TruncUser->getType(), true)))
2334 BasicBlock *TruncUserBB = TruncUser->getParent();
2343 BasicBlock::iterator InsertPt = TruncUserBB->getFirstInsertionPt();
2344 assert(InsertPt != TruncUserBB->end());
2346 if (ShiftI->getOpcode() == Instruction::AShr)
2348 BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, "");
2351 BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, "");
2352 InsertedShift->setDebugLoc(ShiftI->getDebugLoc());
2353 InsertedShift->insertBefore(*TruncUserBB, InsertPt);
2356 BasicBlock::iterator TruncInsertPt = TruncUserBB->getFirstInsertionPt();
2358 // It will go ahead of any debug-info.
2360 assert(TruncInsertPt != TruncUserBB->end());
2362 InsertedTrunc = CastInst::Create(TruncI->getOpcode(), InsertedShift,
2363 TruncI->getType(), "");
2364 InsertedTrunc->insertBefore(*TruncUserBB, TruncInsertPt);
2365 InsertedTrunc->setDebugLoc(TruncI->getDebugLoc());
2395 BasicBlock *DefBB = ShiftI->getParent();
2400 bool shiftIsLegal = TLI.isTypeLegal(TLI.getValueType(DL, ShiftI->getType()));
2403 for (Value::user_iterator UI = ShiftI->user_begin(), E = ShiftI->user_end();
2417 BasicBlock *UserBB = User->getParent();
2430 // ----> We will have an implicit truncate here if the architecture does
2438 && (!TLI.isTypeLegal(TLI.getValueType(DL, User->getType()))))
2448 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
2449 assert(InsertPt != UserBB->end());
2451 if (ShiftI->getOpcode() == Instruction::AShr)
2453 BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, "");
2456 BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, "");
2457 InsertedShift->insertBefore(*UserBB, InsertPt);
2458 InsertedShift->setDebugLoc(ShiftI->getDebugLoc());
2468 if (ShiftI->use_empty()) {
2470 ShiftI->eraseFromParent();
2501 if (match(CountZeros->getOperand(1), m_One()))
2505 Type *Ty = CountZeros->getType();
2506 auto IntrinsicID = CountZeros->getIntrinsicID();
2507 if ((IntrinsicID == Intrinsic::cttz && TLI->isCheapToSpeculateCttz(Ty)) ||
2508 (IntrinsicID == Intrinsic::ctlz && TLI->isCheapToSpeculateCtlz(Ty)))
2512 unsigned SizeInBits = Ty->getScalarSizeInBits();
2513 if (Ty->isVectorTy() || SizeInBits > DL->getLargestLegalIntTypeSizeInBits())
2517 Use &Op = CountZeros->getOperandUse(0);
2522 BasicBlock *StartBlock = CountZeros->getParent();
2523 BasicBlock *CallBlock = StartBlock->splitBasicBlock(CountZeros, "cond.false");
2528 // in this block to select the result of the intrinsic or the bit-width
2531 // Any debug-info after CountZeros should not be included.
2533 BasicBlock *EndBlock = CallBlock->splitBasicBlock(SplitPt, "cond.end");
2540 L->addBasicBlockToLoop(CallBlock, LI);
2541 L->addBasicBlockToLoop(EndBlock, LI);
2544 // Set up a builder to create a compare, conditional branch, and PHI.
2545 IRBuilder<> Builder(CountZeros->getContext());
2546 Builder.SetInsertPoint(StartBlock->getTerminator());
2547 Builder.SetCurrentDebugLocation(CountZeros->getDebugLoc());
2554 Op = Builder.CreateFreeze(Op, Op->getName() + ".fr");
2555 Value *Cmp = Builder.CreateICmpEQ(Op, Zero, "cmpz");
2556 Builder.CreateCondBr(Cmp, EndBlock, CallBlock);
2557 StartBlock->getTerminator()->eraseFromParent();
2561 Builder.SetInsertPoint(EndBlock, EndBlock->begin());
2562 PHINode *PN = Builder.CreatePHI(Ty, 2, "ctz");
2564 Value *BitWidth = Builder.getInt(APInt(SizeInBits, SizeInBits));
2565 PN->addIncoming(BitWidth, StartBlock);
2566 PN->addIncoming(CountZeros, CallBlock);
2571 CountZeros->setArgOperand(1, Builder.getTrue());
2577 BasicBlock *BB = CI->getParent();
2582 if (CI->isInlineAsm()) {
2583 if (TLI->ExpandInlineAsm(CI)) {
2585 CurInstIterator = BB->begin();
2600 if (TLI->shouldAlignPointerArgs(CI, MinSize, PrefAlign)) {
2601 for (auto &Arg : CI->args()) {
2605 // if size - offset meets the size threshold.
2606 if (!Arg->getType()->isPointerTy())
2608 APInt Offset(DL->getIndexSizeInBits(
2609 cast<PointerType>(Arg->getType())->getAddressSpace()),
2611 Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*DL, Offset);
2616 if ((AI = dyn_cast<AllocaInst>(Val)) && AI->getAlign() < PrefAlign &&
2617 DL->getTypeAllocSize(AI->getAllocatedType()) >= MinSize + Offset2)
2618 AI->setAlignment(PrefAlign);
2621 // over-aligning global variables that have an explicit section is
2624 if ((GV = dyn_cast<GlobalVariable>(Val)) && GV->canIncreaseAlignment() &&
2625 GV->getPointerAlignment(*DL) < PrefAlign &&
2626 DL->getTypeAllocSize(GV->getValueType()) >= MinSize + Offset2)
2627 GV->setAlignment(PrefAlign);
2633 Align DestAlign = getKnownAlignment(MI->getDest(), *DL);
2634 MaybeAlign MIDestAlign = MI->getDestAlign();
2636 MI->setDestAlignment(DestAlign);
2638 MaybeAlign MTISrcAlign = MTI->getSourceAlign();
2639 Align SrcAlign = getKnownAlignment(MTI->getSource(), *DL);
2641 MTI->setSourceAlignment(SrcAlign);
2649 if (CI->hasFnAttr(Attribute::Cold) &&
2651 for (auto &Arg : CI->args()) {
2652 if (!Arg->getType()->isPointerTy())
2654 unsigned AS = Arg->getType()->getPointerAddressSpace();
2655 if (optimizeMemoryInst(CI, Arg, Arg->getType(), AS))
2661 switch (II->getIntrinsicID()) {
2670 // paths and merge blocks before going into block-local instruction
2672 if (II->use_empty()) {
2673 II->eraseFromParent();
2676 Constant *RetVal = ConstantInt::getTrue(II->getContext());
2688 ZExtInst *ExtVal = dyn_cast<ZExtInst>(CI->getArgOperand(0));
2689 if (!ExtVal || !ExtVal->hasOneUse() ||
2690 ExtVal->getParent() == CI->getParent())
2693 ExtVal->moveBefore(CI->getIterator());
2702 Value *ArgVal = II->getArgOperand(0);
2708 auto GEPs = std::move(it->second);
2714 II->eraseFromParent();
2729 return optimizeGatherScatterInst(II, II->getArgOperand(0));
2731 return optimizeGatherScatterInst(II, II->getArgOperand(1));
2736 if (TLI->getAddrModeArguments(II, PtrOps, AccessTy))
2739 unsigned AS = PtrVal->getType()->getPointerAddressSpace();
2746 auto *Callee = CI->getCalledFunction();
2755 IRBuilder<> Builder(CI);
2756 if (Value *V = Simplifier.optimizeCall(CI, Builder)) {
2758 CI->eraseFromParent();
2766 auto GetUniformReturnValue = [](const Function *F) -> GlobalVariable * {
2767 if (!F->getReturnType()->isPointerTy())
2773 if (auto *V = dyn_cast<GlobalVariable>(RI->getReturnValue())) {
2787 if (Callee->hasExactDefinition()) {
2790 for (Use &U : make_early_inc_range(RV->uses())) {
2792 if (!I || I->getParent() != CI->getParent()) {
2793 // Limit to the same basic block to avoid extending the call-site live
2797 if (CI->comesBefore(I)) {
2812 assert(CI && CI->use_empty());
2815 switch (II->getIntrinsicID()) {
2825 Function *Callee = CI->getCalledFunction();
2826 if (Callee && TLInfo && TLInfo->getLibFunc(*Callee, LF))
2874 if (!BB->getTerminator())
2877 ReturnInst *RetI = dyn_cast<ReturnInst>(BB->getTerminator());
2881 assert(LI->getLoopFor(BB) == nullptr && "A return block cannot be in a loop");
2886 Value *V = RetI->getReturnValue();
2890 V = BCI->getOperand(0);
2894 V = EVI->getOperand(0);
2895 if (!llvm::all_of(EVI->indices(), [](unsigned idx) { return idx == 0; }))
2902 if (PN && PN->getParent() != BB)
2907 if (BC && BC->hasOneUse())
2908 Inst = BC->user_back();
2911 return II->getIntrinsicID() == Intrinsic::lifetime_end;
2919 II && II->getIntrinsicID() == Intrinsic::fake_use) {
2927 if (!isa<PHINode>(II->getOperand(0))) {
2938 BasicBlock::const_iterator BI = BB->getFirstNonPHIIt();
2949 const Function *F = BB->getParent();
2955 for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
2957 Value *IncomingVal = PN->getIncomingValue(I)->stripPointerCasts();
2959 BasicBlock *PredBB = PN->getIncomingBlock(I);
2961 if (CI && CI->hasOneUse() && CI->getParent() == PredBB &&
2962 TLI->mayBeEmittedAsTailCall(CI) &&
2977 if (PredBB && PredBB->getSingleSuccessor() == BB)
2979 PredBB->getTerminator()->getPrevNonDebugInstruction(true));
2981 if (CI && CI->use_empty() &&
2983 IncomingVal == CI->getArgOperand(0) &&
2984 TLI->mayBeEmittedAsTailCall(CI) &&
2996 if (Instruction *I = Pred->rbegin()->getPrevNonDebugInstruction(true)) {
2998 if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI) &&
3004 V == CI->getArgOperand(0))) {
3017 BranchInst *BI = dyn_cast<BranchInst>(TailCallBB->getTerminator());
3018 if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
3024 BFI->getBlockFreq(BB) >= BFI->getBlockFreq(TailCallBB));
3025 BFI->setBlockFreq(BB,
3026 (BFI->getBlockFreq(BB) - BFI->getBlockFreq(TailCallBB)));
3033 if (Changed && !BB->hasAddressTaken() && pred_empty(BB)) {
3038 auto *ClonedInst = FakeUse->clone();
3039 ClonedInst->insertBefore(CI->getIterator());
3042 BB->eraseFromParent();
3048 //===----------------------------------------------------------------------===//
3050 //===----------------------------------------------------------------------===//
3081 BaseReg->getType() != other.BaseReg->getType())
3083 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
3086 ScaledReg->getType() != other.ScaledReg->getType())
3120 // consider to be 'non-zero' here.
3193 BaseGV->printAsOperand(OS, /*PrintType=*/false);
3204 BaseReg->printAsOperand(OS, /*PrintType=*/false);
3209 ScaledReg->printAsOperand(OS, /*PrintType=*/false);
3266 /// - Is the first in a basic block: BB is used.
3267 /// - Has a previous instruction: PrevInst is used.
3280 HasPrevInstruction = (Inst != &*(Inst->getParent()->begin()));
3281 BasicBlock *BB = Inst->getParent();
3283 // Record where we would have to re-insert the instruction in the sequence
3285 if (BB->IsNewDbgInfoFormat)
3286 BeforeDbgRecord = Inst->getDbgReinsertionPosition();
3289 Point.PrevInst = std::prev(Inst->getIterator());
3298 if (Inst->getParent())
3299 Inst->removeFromParent();
3300 Inst->insertAfter(Point.PrevInst);
3302 BasicBlock::iterator Position = Point.BB->getFirstInsertionPt();
3303 if (Inst->getParent())
3304 Inst->moveBefore(*Point.BB, Position);
3306 Inst->insertBefore(*Point.BB, Position);
3309 Inst->getParent()->reinsertInstInDbgRecords(Inst, BeforeDbgRecord);
3324 Inst->moveBefore(Before);
3349 Origin = Inst->getOperand(Idx);
3350 Inst->setOperand(Idx, NewVal);
3358 Inst->setOperand(Idx, Origin);
3372 unsigned NumOpnds = Inst->getNumOperands();
3376 Value *Val = Inst->getOperand(It);
3381 Inst->setOperand(It, PoisonValue::get(Val->getType()));
3389 Inst->setOperand(It, OriginalValues[It]);
3402 IRBuilder<> Builder(Opnd);
3403 Builder.SetCurrentDebugLocation(DebugLoc());
3404 Val = Builder.CreateTrunc(Opnd, Ty, "promoted");
3415 IVal->eraseFromParent();
3429 IRBuilder<> Builder(InsertPt);
3430 Val = Builder.CreateSExt(Opnd, Ty, "promoted");
3441 IVal->eraseFromParent();
3455 IRBuilder<> Builder(InsertPt);
3456 Builder.SetCurrentDebugLocation(DebugLoc());
3457 Val = Builder.CreateZExt(Opnd, Ty, "promoted");
3468 IVal->eraseFromParent();
3480 : TypePromotionAction(Inst), OrigTy(Inst->getType()) {
3483 Inst->mutateType(NewTy);
3490 Inst->mutateType(OrigTy);
3512 /// And non-instruction debug-users too.
3528 for (Use &U : Inst->uses()) {
3537 Inst->replaceAllUsesWith(New);
3544 Use.Inst->setOperand(Use.Idx, Inst);
3550 DVI->replaceVariableLocationOp(New, Inst);
3551 // Similar story with DbgVariableRecords, the non-instruction
3554 DVR->replaceVariableLocationOp(New, Inst);
3577 /// \pre If !Inst->use_empty(), then New != nullptr
3589 Inst->removeFromParent();
3603 Replacer->undo();
3652 /// The ordered list of actions made so far.
3653 SmallVector<std::unique_ptr<TypePromotionAction>, 16> Actions;
3665 Actions.push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3671 Actions.push_back(
3678 Actions.push_back(
3683 Actions.push_back(
3689 Value *Val = Ptr->getBuiltValue();
3690 Actions.push_back(std::move(Ptr));
3697 Value *Val = Ptr->getBuiltValue();
3698 Actions.push_back(std::move(Ptr));
3705 Value *Val = Ptr->getBuiltValue();
3706 Actions.push_back(std::move(Ptr));
3712 return !Actions.empty() ? Actions.back().get() : nullptr;
3716 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3717 Action->commit();
3718 bool Modified = !Actions.empty();
3719 Actions.clear();
3725 while (!Actions.empty() && Point != Actions.back().get()) {
3726 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3727 Curr->undo();
3735 /// This encapsulates the logic for matching the target-legal addressing modes.
3744 /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and
3786 DL(MI->getDataLayout()), LI(LI), getDTFn(getDTFn),
3941 if (it != NodeMap.end() && it->second == CurrentIndex)
3952 assert(CurrentIndex < Set->NodeList.size() &&
3954 return Set->NodeList[CurrentIndex];
3958 assert(CurrentIndex < Set->NodeList.size() &&
3961 Set->SkipRemovedElements(CurrentIndex);
3993 V = SV->second;
4007 for (auto *U : PI->users())
4010 PI->replaceAllUsesWith(V);
4015 PI->eraseFromParent();
4032 From->replaceAllUsesWith(To);
4034 From->eraseFromParent();
4051 I->replaceAllUsesWith(Dummy);
4052 I->eraseFromParent();
4056 I->replaceAllUsesWith(Dummy);
4057 I->eraseFromParent();
4103 // Take note of if we have any non-trivial AddrModes, as we need to detect
4190 if (CommonValue && CommonValue->getNumUses() == 0)
4192 CommonInst->eraseFromParent();
4204 Type *IntPtrTy = SQ.DL.getIntPtrType(AddrModes[0].OriginalValue->getType());
4208 auto *Type = DV->getType();
4217 assert(CommonType && "At least one non-null value must be!");
4241 // p1 -> b1
4242 // p2 -> b2
4244 // p -> ?
4276 auto *Result = ST.Get(Map.find(Original)->second);
4304 for (auto *B : Item.first->blocks()) {
4305 Value *FirstValue = Item.first->getIncomingValueForBlock(B);
4306 Value *SecondValue = Item.second->getIncomingValueForBlock(B);
4318 FirstPhi->getParent() != SecondPhi->getParent())
4356 for (auto &P : PHI->getParent()->phis()) {
4398 auto *TrueValue = CurrentSelect->getTrueValue();
4400 Select->setTrueValue(ST.Get(Map[TrueValue]));
4401 auto *FalseValue = CurrentSelect->getFalseValue();
4403 Select->setFalseValue(ST.Get(Map[FalseValue]));
4408 for (auto *B : predecessors(PHI->getParent())) {
4409 Value *PV = cast<PHINode>(Current)->getIncomingValueForBlock(B);
4411 PHI->addIncoming(ST.Get(Map[PV]), B);
4418 /// Starting from original value recursively iterates over def-use chain up to
4444 SelectInst::Create(CurrentSelect->getCondition(), Dummy, Dummy,
4445 CurrentSelect->getName(),
4446 CurrentSelect->getIterator(), CurrentSelect);
4450 Worklist.push_back(CurrentSelect->getTrueValue());
4451 Worklist.push_back(CurrentSelect->getFalseValue());
4455 unsigned PredCount = CurrentPhi->getNumIncomingValues();
4457 PHINode::Create(CommonType, PredCount, "sunk_phi", CurrentPhi->getIterator());
4460 append_range(Worklist, CurrentPhi->incoming_values());
4505 // Add scale to turn X*4+X*3 -> X*7. This could also do things like
4506 // [A+B + A*7] -> [B+A*8].
4525 !isIVIncrement(ScaleReg, &LI) && CI->getValue().isSignedIntN(64)) {
4528 TestAddrMode.BaseOffs += CI->getSExtValue() * TestAddrMode.Scale;
4544 [this](const Value *V) -> std::optional<std::pair<Instruction *, APInt>> {
4551 // TODO: The result of the intrinsics above is two-complement. However when
4555 // well-defined two-complement computation with poison. Currently, to avoid
4557 if (auto *OIVInc = dyn_cast<OverflowingBinaryOperator>(IVInc->first))
4558 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4560 if (auto *ConstantStep = dyn_cast<ConstantInt>(IVInc->second))
4561 return std::make_pair(IVInc->first, ConstantStep->getValue());
4567 // 2. We use it with non-zero offset;
4578 Instruction *IVInc = IVStep->first;
4584 APInt Step = IVStep->second;
4589 TestAddrMode.BaseOffs -= Offset.getLimitedValue();
4614 switch (I->getOpcode()) {
4618 if (I->getType() == I->getOperand(0)->getType())
4620 return I->getType()->isIntOrPtrTy();
4632 return isa<ConstantInt>(I->getOperand(1));
4643 /// to be legal, as the non-promoted value would have had the same state.
4649 int ISDOpcode = TLI.InstructionOpcodeToISD(PromotedInst->getOpcode());
4655 ISDOpcode, TLI.getValueType(DL, PromotedInst->getType()));
4671 if (It->second.getInt() == ExtTy)
4679 PromotedInsts[ExtOpnd] = TypeIsSExt(ExtOpnd->getType(), ExtTy);
4690 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4691 return It->second.getPointer();
4799 if (Inst->getType()->isVectorTy())
4814 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4815 (IsSExt && BinOp->hasNoSignedWrap())))
4818 // ext(and(opnd, cst)) --> and(ext(opnd), ext(cst))
4819 if ((Inst->getOpcode() == Instruction::And ||
4820 Inst->getOpcode() == Instruction::Or))
4823 // ext(xor(opnd, cst)) --> xor(ext(opnd), ext(cst))
4824 if (Inst->getOpcode() == Instruction::Xor) {
4826 if (const auto *Cst = dyn_cast<ConstantInt>(Inst->getOperand(1)))
4827 if (!Cst->getValue().isAllOnes())
4831 // zext(shrl(opnd, cst)) --> shrl(zext(opnd), zext(cst))
4833 // zext i32 (shrl i8 %val, 12) --> shrl i32 (zext i8 %val), 12
4836 if (Inst->getOpcode() == Instruction::LShr && !IsSExt)
4839 // and(ext(shl(opnd, cst)), cst) --> and(shl(ext(opnd), ext(cst)), cst)
4841 // zext i32 (shl i8 %val, 12) --> shl i32 (zext i8 %val), 12
4844 if (Inst->getOpcode() == Instruction::Shl && Inst->hasOneUse()) {
4845 const auto *ExtInst = cast<const Instruction>(*Inst->user_begin());
4846 if (ExtInst->hasOneUse()) {
4847 const auto *AndInst = dyn_cast<const Instruction>(*ExtInst->user_begin());
4848 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4849 const auto *Cst = dyn_cast<ConstantInt>(AndInst->getOperand(1));
4851 Cst->getValue().isIntN(Inst->getType()->getIntegerBitWidth()))
4858 // ext(trunc(opnd)) --> ext(opnd)
4862 Value *OpndVal = Inst->getOperand(0);
4865 if (!OpndVal->getType()->isIntegerTy() ||
4866 OpndVal->getType()->getIntegerBitWidth() >
4867 ConsideredExtType->getIntegerBitWidth())
4885 OpndType = Opnd->getOperand(0)->getType();
4890 return Inst->getType()->getIntegerBitWidth() >=
4891 OpndType->getIntegerBitWidth();
4899 Instruction *ExtOpnd = dyn_cast<Instruction>(Ext->getOperand(0));
4900 Type *ExtTy = Ext->getType();
4921 // Abort early if we will have to insert non-free instructions.
4922 if (!ExtOpnd->hasOneUse() && !TLI.isTruncateFree(ExtTy, ExtOpnd->getType()))
4934 Instruction *SExtOpnd = cast<Instruction>(SExt->getOperand(0));
4942 TPT.createZExt(SExt, SExtOpnd->getOperand(0), SExt->getType());
4949 TPT.setOperand(SExt, 0, SExtOpnd->getOperand(0));
4954 if (SExtOpnd->use_empty())
4959 if (!ExtInst || ExtInst->getType() != ExtInst->getOperand(0)->getType()) {
4962 Exts->push_back(ExtInst);
4970 Value *NextVal = ExtInst->getOperand(0);
4983 Instruction *ExtOpnd = cast<Instruction>(Ext->getOperand(0));
4985 if (!ExtOpnd->hasOneUse()) {
4990 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->getType());
4993 ITrunc->moveAfter(ExtOpnd);
4995 Truncs->push_back(ITrunc);
5000 // to replaceAllUsesWith) to avoid creating a cycle trunc <-> sext.
5013 TPT.mutateType(ExtOpnd, Ext->getType());
5018 for (int OpIdx = 0, EndOpIdx = ExtOpnd->getNumOperands(); OpIdx != EndOpIdx;
5020 LLVM_DEBUG(dbgs() << "Operand:\n" << *(ExtOpnd->getOperand(OpIdx)) << '\n');
5021 if (ExtOpnd->getOperand(OpIdx)->getType() == Ext->getType() ||
5027 Value *Opnd = ExtOpnd->getOperand(OpIdx);
5030 unsigned BitWidth = Ext->getType()->getIntegerBitWidth();
5031 APInt CstVal = IsSExt ? Cst->getValue().sext(BitWidth)
5032 : Cst->getValue().zext(BitWidth);
5033 TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(Ext->getType(), CstVal));
5039 TPT.setOperand(ExtOpnd, OpIdx, UndefValue::get(Ext->getType()));
5045 ? TPT.createSExt(ExtOpnd, Opnd, Ext->getType())
5046 : TPT.createZExt(ExtOpnd, Opnd, Ext->getType());
5053 Exts->push_back(InstForExtOpnd);
5112 return matchAddr(AddrInst->getOperand(0), Depth);
5114 auto AS = AddrInst->getType()->getPointerAddressSpace();
5116 // This inttoptr is a no-op if the integer type is pointer sized.
5117 if (TLI.getValueType(DL, AddrInst->getOperand(0)->getType()) == PtrTy)
5118 return matchAddr(AddrInst->getOperand(0), Depth);
5123 // int->int or pointer->pointer (we don't want int<->fp or something).
5124 if (AddrInst->getOperand(0)->getType()->isIntOrPtrTy() &&
5128 AddrInst->getOperand(0)->getType() != AddrInst->getType())
5129 return matchAddr(AddrInst->getOperand(0), Depth);
5133 AddrInst->getOperand(0)->getType()->getPointerAddressSpace();
5134 unsigned DestAS = AddrInst->getType()->getPointerAddressSpace();
5136 return matchAddr(AddrInst->getOperand(0), Depth);
5154 if (isa<ConstantInt>(AddrInst->getOperand(First))
5155 && !isa<ConstantInt>(AddrInst->getOperand(Second)))
5158 if (matchAddr(AddrInst->getOperand(First), Depth + 1) &&
5159 matchAddr(AddrInst->getOperand(Second), Depth + 1))
5167 // Otherwise this was over-aggressive. Try merging operands in the opposite
5169 if (matchAddr(AddrInst->getOperand(Second), Depth + 1) &&
5170 matchAddr(AddrInst->getOperand(First), Depth + 1))
5186 ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1));
5187 if (!RHS || RHS->getBitWidth() > 64)
5190 ? 1LL << RHS->getLimitedValue(RHS->getBitWidth() - 1)
5191 : RHS->getSExtValue();
5193 return matchScaledValue(AddrInst->getOperand(0), Scale, Depth);
5198 int VariableOperand = -1;
5203 for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) {
5207 cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue();
5208 ConstantOffset += SL->getElementOffset(Idx);
5217 dyn_cast<ConstantInt>(AddrInst->getOperand(i))) {
5218 const APInt &CVal = CI->getValue();
5225 if (VariableOperand != -1)
5237 if (VariableOperand == -1) {
5239 if (matchAddr(AddrInst->getOperand(0), Depth + 1)) {
5240 if (!cast<GEPOperator>(AddrInst)->isInBounds())
5244 AddrMode.BaseOffs -= ConstantOffset;
5249 // Record GEPs with non-zero offsets as candidates for splitting in
5253 Value *Base = AddrInst->getOperand(0);
5259 // Make sure the parent block allows inserting non-PHI instructions
5261 BasicBlock *Parent = BaseI ? BaseI->getParent()
5262 : &GEP->getFunction()->getEntryBlock();
5263 if (!Parent->getTerminator()->isEHPad())
5277 if (!cast<GEPOperator>(AddrInst)->isInBounds())
5281 if (!matchAddr(AddrInst->getOperand(0), Depth + 1)) {
5289 AddrMode.BaseReg = AddrInst->getOperand(0);
5293 if (!matchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale,
5302 AddrMode.BaseReg = AddrInst->getOperand(0);
5304 if (!matchScaledValue(AddrInst->getOperand(VariableOperand),
5342 // promotedOpnd = ext opnd <- no match here
5343 // op = promoted_add promotedOpnd, 1 <- match (later in recursive calls)
5344 // addr = gep base, op <- match
5360 ExtCost + (AddrModeInsts.size() - OldSize),
5372 if (II->getIntrinsicID() == Intrinsic::threadlocal_address) {
5373 GlobalValue &GV = cast<GlobalValue>(*II->getArgOperand(0));
5375 return matchAddr(AddrInst->getOperand(0), Depth);
5394 if (CI->getValue().isSignedIntN(64)) {
5396 AddrMode.BaseOffs += CI->getSExtValue();
5399 AddrMode.BaseOffs -= CI->getSExtValue();
5415 if (matchOperationAddr(I, I->getOpcode(), Depth, &MovedAway)) {
5423 if (I->hasOneUse() ||
5435 if (matchOperationAddr(CE, CE->getOpcode(), Depth))
5473 const Function *F = CI->getFunction();
5475 TLI.ParseConstraints(F->getDataLayout(), &TRI, *CI);
5493 /// If we find an obviously non-foldable instruction, return true.
5509 for (Use &U : I->uses()) {
5517 MemoryUses.push_back({&U, LI->getType()});
5524 MemoryUses.push_back({&U, SI->getValueOperand()->getType()});
5531 MemoryUses.push_back({&U, RMW->getValOperand()->getType()});
5538 MemoryUses.push_back({&U, CmpX->getCompareOperand()->getType()});
5543 if (CI->hasFnAttr(Attribute::Cold)) {
5546 if (!llvm::shouldOptimizeForSize(CI->getParent(), PSI, BFI))
5550 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledOperand());
5586 // If Val is either of the known-live values, we know it is live!
5598 if (AI->isStaticAlloca())
5604 return Val->isUsedInBasicBlock(MemoryInst->getParent());
5615 /// use(Y) -> nonload/store
5662 return false; // Has a non-memory, non-foldable use!
5675 Value *Address = Pair.first->get();
5676 Instruction *UserI = cast<Instruction>(Pair.first->getUser());
5678 unsigned AS = Address->getType()->getPointerAddressSpace();
5716 return I->getParent() != BB;
5743 // Try to collapse single-value PHI nodes. This is necessary to undo
5750 // ensure that the addressing mode obtained from the non-PHI/select roots of
5776 append_range(worklist, P->incoming_values());
5782 worklist.push_back(SI->getFalseValue());
5783 worklist.push_back(SI->getTrueValue());
5788 // For non-PHIs, determine the addressing mode being computed. Note that
5797 auto getDTFn = [MemoryInst, this]() -> const DominatorTree & {
5798 Function *F = MemoryInst->getParent()->getParent();
5799 return this->getDT(*F);
5811 LargeOffsetGEPMap[GEP->getPointerOperand()].push_back(LargeOffsetGEP);
5837 return IsNonLocalValue(V, MemoryInst->getParent());
5847 IRBuilder<> Builder(MemoryInst);
5858 Type *IntPtrTy = DL->getIntPtrType(Addr->getType());
5862 if (SunkAddr->getType() != Addr->getType()) {
5863 if (SunkAddr->getType()->getPointerAddressSpace() !=
5864 Addr->getType()->getPointerAddressSpace() &&
5865 !DL->isNonIntegralPointerType(Addr->getType())) {
5866 // There are two reasons the address spaces might not match: a no-op
5871 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy, "sunkaddr");
5873 Builder.CreateIntToPtr(SunkAddr, Addr->getType(), "sunkaddr");
5875 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->getType());
5878 SubtargetInfo->addrSinkUsingGEPs())) {
5879 // By default, we use the GEP-based method when AA is used later. This
5886 if (AddrMode.BaseReg && AddrMode.BaseReg->getType()->isPointerTy()) {
5891 if (AddrMode.Scale && AddrMode.ScaledReg->getType()->isPointerTy()) {
5909 Type *ScaledRegTy = AddrMode.ScaledReg->getType();
5910 if (cast<IntegerType>(IntPtrTy)->getBitWidth() >
5911 cast<IntegerType>(ScaledRegTy)->getBitWidth())
5920 if (BaseGV->isThreadLocal()) {
5921 ResultPtr = Builder.CreateThreadLocalAddress(BaseGV);
5930 if (!DL->isNonIntegralPointerType(Addr->getType())) {
5932 ResultPtr = Builder.CreateIntToPtr(AddrMode.BaseReg, Addr->getType(),
5936 ResultPtr = Builder.CreateIntToPtr(AddrMode.ScaledReg, Addr->getType(),
5944 SunkAddr = Constant::getNullValue(Addr->getType());
5949 Builder.getPtrTy(Addr->getType()->getPointerAddressSpace());
5958 if (V->getType() != IntPtrTy)
5959 V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr");
5967 if (V->getType() == IntPtrTy) {
5970 assert(cast<IntegerType>(IntPtrTy)->getBitWidth() <
5971 cast<IntegerType>(V->getType())->getBitWidth() &&
5973 V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
5977 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
5980 ResultIndex = Builder.CreateAdd(ResultIndex, V, "sunkaddr");
5991 if (ResultPtr->getType() != I8PtrTy)
5992 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
5993 ResultPtr = Builder.CreatePtrAdd(ResultPtr, ResultIndex, "sunkaddr",
6003 if (ResultPtr->getType() != I8PtrTy)
6004 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6005 SunkAddr = Builder.CreatePtrAdd(ResultPtr, ResultIndex, "sunkaddr",
6009 if (SunkAddr->getType() != Addr->getType()) {
6010 if (SunkAddr->getType()->getPointerAddressSpace() !=
6011 Addr->getType()->getPointerAddressSpace() &&
6012 !DL->isNonIntegralPointerType(Addr->getType())) {
6013 // There are two reasons the address spaces might not match: a no-op
6018 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy, "sunkaddr");
6020 Builder.CreateIntToPtr(SunkAddr, Addr->getType(), "sunkaddr");
6022 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->getType());
6027 // non-integral pointers, so in that case bail out now.
6028 Type *BaseTy = AddrMode.BaseReg ? AddrMode.BaseReg->getType() : nullptr;
6029 Type *ScaleTy = AddrMode.Scale ? AddrMode.ScaledReg->getType() : nullptr;
6032 if (DL->isNonIntegralPointerType(Addr->getType()) ||
6033 (BasePtrTy && DL->isNonIntegralPointerType(BasePtrTy)) ||
6034 (ScalePtrTy && DL->isNonIntegralPointerType(ScalePtrTy)) ||
6036 DL->isNonIntegralPointerType(AddrMode.BaseGV->getType())))
6041 Type *IntPtrTy = DL->getIntPtrType(Addr->getType());
6051 if (V->getType()->isPointerTy())
6052 V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
6053 if (V->getType() != IntPtrTy)
6054 V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr");
6061 if (V->getType() == IntPtrTy) {
6063 } else if (V->getType()->isPointerTy()) {
6064 V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
6065 } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() <
6066 cast<IntegerType>(V->getType())->getBitWidth()) {
6067 V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
6076 I->eraseFromParent();
6080 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
6083 Result = Builder.CreateAdd(Result, V, "sunkaddr");
6092 if (BaseGV->isThreadLocal()) {
6093 BaseGVPtr = Builder.CreateThreadLocalAddress(BaseGV);
6097 Value *V = Builder.CreatePtrToInt(BaseGVPtr, IntPtrTy, "sunkaddr");
6099 Result = Builder.CreateAdd(Result, V, "sunkaddr");
6108 Result = Builder.CreateAdd(Result, V, "sunkaddr");
6114 SunkAddr = Constant::getNullValue(Addr->getType());
6116 SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr");
6119 MemoryInst->replaceUsesOfWith(Repl, SunkAddr);
6126 if (Repl->use_empty()) {
6127 resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
6160 if (!GEP->hasIndices())
6165 if (MemoryInst->getParent() != GEP->getParent())
6168 SmallVector<Value *, 2> Ops(GEP->operands());
6172 if (Ops[0]->getType()->isVectorTy()) {
6179 unsigned FinalIndex = Ops.size() - 1;
6188 if (isa<VectorType>(C->getType()))
6189 C = C->getSplatValue();
6191 if (!CI || !CI->isZero())
6198 if (Ops[FinalIndex]->getType()->isVectorTy()) {
6202 if (!C || !C->isZero()) {
6214 auto NumElts = cast<VectorType>(Ptr->getType())->getElementCount();
6216 IRBuilder<> Builder(MemoryInst);
6218 Type *SourceTy = GEP->getSourceElementType();
6219 Type *ScalarIndexTy = DL->getIndexType(Ops[0]->getType()->getScalarType());
6223 if (!Ops[FinalIndex]->getType()->isVectorTy()) {
6224 NewAddr = Builder.CreateGEP(SourceTy, Ops[0], ArrayRef(Ops).drop_front());
6229 Builder.CreateGEP(SecondTy, NewAddr, Constant::getNullValue(IndexTy));
6238 Constant::getNullValue(Ops[FinalIndex]->getType()->getScalarType());
6239 Base = Builder.CreateGEP(SourceTy, Base, ArrayRef(Ops).drop_front());
6245 NewAddr = Builder.CreateGEP(SourceTy, Base, Index);
6254 auto NumElts = cast<VectorType>(Ptr->getType())->getElementCount();
6256 IRBuilder<> Builder(MemoryInst);
6259 Type *ScalarIndexTy = DL->getIndexType(V->getType()->getScalarType());
6262 if (cast<IntrinsicInst>(MemoryInst)->getIntrinsicID() ==
6264 ScalarTy = MemoryInst->getType()->getScalarType();
6266 assert(cast<IntrinsicInst>(MemoryInst)->getIntrinsicID() ==
6268 ScalarTy = MemoryInst->getOperand(0)->getType()->getScalarType();
6270 NewAddr = Builder.CreateGEP(ScalarTy, V, Constant::getNullValue(IndexTy));
6276 MemoryInst->replaceUsesOfWith(Ptr, NewAddr);
6280 if (Ptr->use_empty())
6294 TM->getSubtargetImpl(*CS->getFunction())->getRegisterInfo();
6296 TLI->ParseConstraints(*DL, TRI, *CS);
6300 TLI->ComputeConstraintToUse(OpInfo, SDValue());
6305 Value *OpVal = CS->getArgOperand(ArgNo++);
6306 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->getType(), ~0u);
6317 assert(!Val->use_empty() && "Input must have at least one use");
6318 const Instruction *FirstUser = cast<Instruction>(*Val->user_begin());
6320 Type *ExtTy = FirstUser->getType();
6321 for (const User *U : Val->users()) {
6325 Type *CurTy = UI->getType();
6346 if (ExtTy->getScalarType()->getIntegerBitWidth() >
6347 CurTy->getScalarType()->getIntegerBitWidth()) {
6378 if (isa<LoadInst>(I->getOperand(0))) {
6387 if (!TLI->enableExtLdPromotion() || DisableExtLdPromotion)
6405 unsigned ExtCost = !TLI->isExtFree(I);
6424 std::max((long long)0, (TotalCreatedInstsCost - ExtCost));
6442 Value *ExtOperand = MovedExt->getOperand(0);
6447 (ExtOperand->hasOneUse() || hasSameExtUse(ExtOperand, *TLI))))
6475 Inst->getOperand(0) != Entry.first)
6482 Pt->removeFromParent();
6494 Inst->removeFromParent();
6532 // %new_gep1 = gep %new_base, off1 - off0
6533 // %new_gep2 = gep %new_base, off2 - off0
6563 GetElementPtrInst *BaseGEP = LargeOffsetGEPs.begin()->first;
6564 int64_t BaseOffset = LargeOffsetGEPs.begin()->second;
6569 LLVMContext &Ctx = GEP->getContext();
6570 Type *PtrIdxTy = DL->getIndexType(GEP->getType());
6572 PointerType::get(Ctx, GEP->getType()->getPointerAddressSpace());
6579 NewBaseInsertBB = BaseI->getParent();
6581 NewBaseInsertPt = NewBaseInsertBB->getFirstInsertionPt();
6584 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), DT.get(), LI);
6585 NewBaseInsertPt = NewBaseInsertBB->getFirstInsertionPt();
6587 NewBaseInsertPt = std::next(BaseI->getIterator());
6591 NewBaseInsertBB = &BaseGEP->getFunction()->getEntryBlock();
6592 NewBaseInsertPt = NewBaseInsertBB->getFirstInsertionPt();
6598 if (NewBaseGEP->getType() != I8PtrTy)
6607 if (int64_t PreferBase = TLI->getPreferredLargeGEPBaseOffset(
6617 GetElementPtrInst *GEP = LargeOffsetGEP->first;
6618 int64_t Offset = LargeOffsetGEP->second;
6622 AddrMode.BaseOffs = Offset - BaseOffset;
6625 if (!TLI->isLegalAddressingMode(*DL, AddrMode,
6626 GEP->getResultElementType(),
6627 GEP->getAddressSpace())) {
6638 Type *PtrIdxTy = DL->getIndexType(GEP->getType());
6646 IRBuilder<> Builder(GEP);
6650 Value *Index = ConstantInt::get(PtrIdxTy, Offset - BaseOffset);
6651 NewGEP = Builder.CreatePtrAdd(NewBaseGEP, Index);
6656 GEP->eraseFromParent();
6670 Type *PhiTy = I->getType();
6673 (!I->getType()->isIntegerTy() && !I->getType()->isFloatingPointTy()))
6696 for (Value *V : Phi->incoming_values()) {
6705 if (!OpLoad->isSimple())
6714 ConvertTy = OpBC->getOperand(0)->getType();
6715 if (OpBC->getOperand(0)->getType() != ConvertTy)
6719 AnyAnchored |= !isa<LoadInst>(OpBC->getOperand(0)) &&
6720 !isa<ExtractElementInst>(OpBC->getOperand(0));
6730 for (User *V : II->users()) {
6740 if (!OpStore->isSimple() || OpStore->getOperand(0) != II)
6745 ConvertTy = OpBC->getType();
6746 if (OpBC->getType() != ConvertTy)
6750 any_of(OpBC->users(), [](User *U) { return !isa<StoreInst>(U); });
6758 !TLI->shouldConvertPhiType(PhiTy, ConvertTy))
6771 ValMap[D] = D->getOperand(0);
6774 BasicBlock::iterator insertPt = std::next(D->getIterator());
6775 ValMap[D] = new BitCastInst(D, ConvertTy, D->getName() + ".bc", insertPt);
6779 ValMap[Phi] = PHINode::Create(ConvertTy, Phi->getNumIncomingValues(),
6780 Phi->getName() + ".tc", Phi->getIterator());
6784 for (int i = 0, e = Phi->getNumIncomingValues(); i < e; i++)
6785 NewPhi->addIncoming(ValMap[Phi->getIncomingValue(i)],
6786 Phi->getIncomingBlock(i));
6793 replaceAllUsesWith(U, ValMap[U->getOperand(0)], FreshBBs, IsHugeFunc);
6795 U->setOperand(0, new BitCastInst(ValMap[U->getOperand(0)], PhiTy, "bc",
6796 U->getIterator()));
6821 replaceAllUsesWith(I, PoisonValue::get(I->getType()), FreshBBs, IsHugeFunc);
6822 I->eraseFromParent();
6834 if (isa<LoadInst>(MovedExtInst->getOperand(0))) {
6835 LI = cast<LoadInst>(MovedExtInst->getOperand(0));
6846 if (!HasPromoted && LI->getParent() == Inst->getParent())
6849 return TLI->isExtLoad(LI, Inst, *DL);
6893 bool ATPConsiderable = TTI->shouldConsiderAddressTypePromotion(
6914 ExtFedByLoad->moveAfter(LI);
6943 Value *HeadOfChain = I->getOperand(0);
6949 if (AlreadySeen->second != nullptr)
6950 UnhandledExts.insert(AlreadySeen->second);
6961 Value *HeadOfChain = I->getOperand(0);
6972 Value *HeadOfChain = I->getOperand(0);
6991 Value *HeadOfChain = I->getOperand(0);
7001 BasicBlock *DefBB = I->getParent();
7005 Value *Src = I->getOperand(0);
7006 if (Src->hasOneUse())
7010 if (!TLI->isTruncateFree(I->getType(), Src->getType()))
7015 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent())
7019 for (User *U : I->users()) {
7023 BasicBlock *UserBB = UI->getParent();
7033 for (User *U : Src->users()) {
7035 BasicBlock *UserBB = UI->getParent();
7044 // InsertedTruncs - Only insert one trunc in each block once.
7048 for (Use &U : Src->uses()) {
7052 BasicBlock *UserBB = User->getParent();
7060 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
7061 assert(InsertPt != UserBB->end());
7062 InsertedTrunc = new TruncInst(I, Src->getType(), "");
7063 InsertedTrunc->insertBefore(*UserBB, InsertPt);
7128 if (!Load->isSimple() || !Load->getType()->isIntOrPtrTy())
7132 if (Load->hasOneUse() &&
7133 InsertedInsts.count(cast<Instruction>(*Load->user_begin())))
7142 for (auto *U : Load->users())
7145 EVT LoadResultVT = TLI->getValueType(*DL, Load->getType());
7157 // Break use-def graph loops.
7163 for (auto *U : Phi->users())
7168 switch (I->getOpcode()) {
7170 auto *AndC = dyn_cast<ConstantInt>(I->getOperand(1));
7173 APInt AndBits = AndC->getValue();
7178 if (AndBits == WidestAndBits && I->getOperand(0) == Load)
7184 auto *ShlC = dyn_cast<ConstantInt>(I->getOperand(1));
7187 uint64_t ShiftAmt = ShlC->getLimitedValue(BitWidth - 1);
7188 DemandBits.setLowBits(BitWidth - ShiftAmt);
7194 EVT TruncVT = TLI->getValueType(*DL, I->getType());
7222 LLVMContext &Ctx = Load->getType()->getContext();
7224 EVT TruncVT = TLI->getValueType(*DL, TruncTy);
7228 !TLI->isLoadExtLegal(ISD::ZEXTLOAD, LoadResultVT, TruncVT))
7231 IRBuilder<> Builder(Load->getNextNonDebugInstruction());
7233 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
7241 NewAnd->setOperand(0, Load);
7247 if (cast<ConstantInt>(And->getOperand(1))->getValue() == DemandBits) {
7250 CurInstIterator = std::next(And->getIterator());
7251 And->eraseFromParent();
7257 Inst->setHasNoSignedWrap(false);
7269 return I && I->hasOneUse() && isSafeToSpeculativelyExecute(I) &&
7270 TTI->isExpensiveToSpeculativelyExecute(I);
7278 if (!TLI->isPredictableSelectExpensive())
7292 if (Probability > TTI->getPredictableBranchThreshold())
7297 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
7299 // If a branch is predictable, an out-of-order CPU can avoid blocking on its
7302 if (!Cmp || !Cmp->hasOneUse())
7307 if (sinkSelectOperand(TTI, SI->getTrueValue()) ||
7308 sinkSelectOperand(TTI, SI->getFalseValue()))
7325 assert(DefSI->getCondition() == SI->getCondition() &&
7327 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
7335 assert(Shift->isShift() && "Expected a shift");
7338 // general vector shifts, and (3) the shift amount is a select-of-splatted
7340 // shift Op0, (select Cond, TVal, FVal) -->
7344 // general vector shift is more than the cost of 2 shift-by-scalars.
7347 Type *Ty = Shift->getType();
7348 if (!Ty->isVectorTy() || !TTI->isVectorShiftByScalarCheap(Ty))
7351 if (!match(Shift->getOperand(1),
7357 IRBuilder<> Builder(Shift);
7358 BinaryOperator::BinaryOps Opcode = Shift->getOpcode();
7359 Value *NewTVal = Builder.CreateBinOp(Opcode, Shift->getOperand(0), TVal);
7360 Value *NewFVal = Builder.CreateBinOp(Opcode, Shift->getOperand(0), FVal);
7361 Value *NewSel = Builder.CreateSelect(Cond, NewTVal, NewFVal);
7363 Shift->eraseFromParent();
7368 Intrinsic::ID Opcode = Fsh->getIntrinsicID();
7373 // than general vector shifts, and (3) the shift amount is select-of-splatted
7375 // fsh Op0, Op1, (select Cond, TVal, FVal) -->
7379 // general vector shift is more than the cost of 2 shift-by-scalars.
7382 Type *Ty = Fsh->getType();
7383 if (!Ty->isVectorTy() || !TTI->isVectorShiftByScalarCheap(Ty))
7386 if (!match(Fsh->getOperand(2),
7392 IRBuilder<> Builder(Fsh);
7393 Value *X = Fsh->getOperand(0), *Y = Fsh->getOperand(1);
7394 Value *NewTVal = Builder.CreateIntrinsic(Opcode, Ty, {X, Y, TVal});
7395 Value *NewFVal = Builder.CreateIntrinsic(Opcode, Ty, {X, Y, FVal});
7396 Value *NewSel = Builder.CreateSelect(Cond, NewTVal, NewFVal);
7398 Fsh->eraseFromParent();
7416 It != SI->getParent()->end(); ++It) {
7418 if (I && SI->getCondition() == I->getCondition()) {
7428 CurInstIterator = std::next(LastSI->getIterator());
7429 // Examine debug-info attached to the consecutive select instructions. They
7435 bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1);
7438 if (VectorCond || SI->getMetadata(LLVMContext::MD_unpredictable))
7442 if (SI->getType()->isVectorTy())
7447 if (TLI->isSelectSupported(SelectKind) &&
7449 llvm::shouldOptimizeForSize(SI->getParent(), PSI, BFI.get())))
7487 if (Value *V = SI->getTrueValue(); sinkSelectOperand(TTI, V))
7489 if (Value *V = SI->getFalseValue(); sinkSelectOperand(TTI, V))
7495 BasicBlock *StartBlock = SI->getParent();
7497 // We should split before any debug-info.
7501 auto *CondFr = IB.CreateFreeze(SI->getCondition(), SI->getName() + ".frozen");
7511 FalseBlock = FalseBranch->getParent();
7512 EndBlock = cast<BasicBlock>(FalseBranch->getOperand(0));
7516 TrueBlock = TrueBranch->getParent();
7517 EndBlock = cast<BasicBlock>(TrueBranch->getOperand(0));
7525 TrueBlock = TrueBranch->getParent();
7526 FalseBlock = FalseBranch->getParent();
7527 EndBlock = cast<BasicBlock>(TrueBranch->getOperand(0));
7530 EndBlock->setName("select.end");
7532 TrueBlock->setName("select.true.sink");
7534 FalseBlock->setName(FalseInstrs.size() == 0 ? "select.false"
7545 BFI->setBlockFreq(EndBlock, BFI->getBlockFreq(StartBlock));
7550 StartBlock->getTerminator()->copyMetadata(*SI, MD);
7555 I->moveBefore(TrueBranch->getIterator());
7557 I->moveBefore(FalseBranch->getIterator());
7575 PHINode *PN = PHINode::Create(SI->getType(), 2, "");
7576 PN->insertBefore(EndBlock->begin());
7577 PN->takeName(SI);
7578 PN->addIncoming(getTrueOrFalseValue(SI, true, INS), TrueBlock);
7579 PN->addIncoming(getTrueOrFalseValue(SI, false, INS), FalseBlock);
7580 PN->setDebugLoc(SI->getDebugLoc());
7583 SI->eraseFromParent();
7589 CurInstIterator = StartBlock->end();
7601 Type *NewType = TLI->shouldConvertSplatType(SVI);
7605 auto *SVIVecType = cast<FixedVectorType>(SVI->getType());
7606 assert(!NewType->isVectorTy() && "Expected a scalar type!");
7607 assert(NewType->getScalarSizeInBits() == SVIVecType->getScalarSizeInBits() &&
7610 FixedVectorType::get(NewType, SVIVecType->getNumElements());
7613 IRBuilder<> Builder(SVI->getContext());
7614 Builder.SetInsertPoint(SVI);
7615 Value *BC1 = Builder.CreateBitCast(
7616 cast<Instruction>(SVI->getOperand(0))->getOperand(1), NewType);
7617 Value *Shuffle = Builder.CreateVectorSplat(NewVecType->getNumElements(), BC1);
7618 Value *BC2 = Builder.CreateBitCast(Shuffle, SVIVecType);
7628 if (auto *Op = dyn_cast<Instruction>(BCI->getOperand(0)))
7629 if (BCI->getParent() != Op->getParent() && !isa<PHINode>(Op) &&
7630 !Op->isTerminator() && !Op->isEHPad())
7631 BCI->moveAfter(Op);
7640 if (!TTI->isProfitableToSinkOperands(I, OpsToSink))
7647 BasicBlock *TargetBB = I->getParent();
7657 auto *UI = cast<Instruction>(U->get());
7660 if (UI->getParent() == TargetBB) {
7671 auto *UI = cast<Instruction>(U->get());
7672 Instruction *NI = UI->clone();
7677 for (Value *Op : NI->operands())
7679 FreshBBs.insert(OpDef->getParent());
7685 NI->insertBefore(InsertPoint->getIterator());
7692 Instruction *OldI = cast<Instruction>(U->getUser());
7694 It->second->setOperand(U->getOperandNo(), NI);
7696 U->set(NI);
7702 if (!I->hasNUsesOrMore(1)) {
7704 I->eraseFromParent();
7712 Value *Cond = SI->getCondition();
7713 Type *OldType = Cond->getType();
7714 LLVMContext &Context = Cond->getContext();
7715 EVT OldVT = TLI->getValueType(*DL, OldType);
7716 MVT RegType = TLI->getPreferredSwitchConditionType(Context, OldVT);
7719 if (RegWidth <= cast<IntegerType>(OldType)->getBitWidth())
7726 // preferred register width, so we will potentially eliminate N-1 extends,
7736 if (TLI->isSExtCheaperThanZExt(OldVT, RegType))
7740 if (Arg->hasSExtAttr())
7742 if (Arg->hasZExtAttr())
7747 ExtInst->insertBefore(SI->getIterator());
7748 ExtInst->setDebugLoc(SI->getDebugLoc());
7749 SI->setCondition(ExtInst);
7750 for (auto Case : SI->cases()) {
7751 const APInt &NarrowConst = Case.getCaseValue()->getValue();
7764 // Materializing the constant for the phi-argument needs instructions; So we
7768 Value *Condition = SI->getCondition();
7774 BasicBlock *SwitchBB = SI->getParent();
7775 Type *ConditionType = Condition->getType();
7777 for (const SwitchInst::CaseHandle &Case : SI->cases()) {
7783 for (PHINode &PHI : CaseBB->phis()) {
7789 PHIType->isIntegerTy() &&
7790 PHIType->getIntegerBitWidth() > ConditionType->getIntegerBitWidth() &&
7791 TLI->isZExtFree(ConditionType, PHIType);
7803 PHIValueInt->getValue() !=
7804 CaseValue->getValue().zext(PHIType->getIntegerBitWidth()))
7814 if (SI->findCaseDest(CaseBB) == nullptr) {
7824 IRBuilder<> Builder(SI);
7825 Replacement = Builder.CreateZExt(Condition, PHIType);
7916 return Transition->getOperand(getTransitionOriginalValueIdx())->getType();
7931 Value *ValIdx = Transition->getOperand(getTransitionOriginalValueIdx());
7933 ? cast<ConstantInt>(ValIdx)->getZExtValue()
7934 : -1;
7938 unsigned AS = ST->getPointerAddressSpace();
7941 TLI.getValueType(DL, ST->getValueOperand()->getType()), AS,
7942 ST->getAlign())) {
7961 Value *Arg0 = Inst->getOperand(0);
7971 Inst->getOpcode(), Inst->getType(), CostKind, Arg0Info, Arg1Info);
7972 VectorCost += TTI.getArithmeticInstrCost(Inst->getOpcode(), PromotedType,
7994 Value *ValExtractIdx = Transition->getOperand(getTransitionIdx());
7996 ExtractIdx = CstVal->getSExtValue();
8001 ElementCount EC = cast<VectorType>(getTransitionType())->getElementCount();
8007 PoisonValue *PoisonVal = PoisonValue::get(Val->getType());
8017 "Generate scalable vector for non-splat is unimplemented");
8025 // the right hand side of a division-like instruction.
8028 switch (Use->getOpcode()) {
8038 return !Use->hasNoNaNs();
8063 for (const Use &U : ToBePromoted->operands()) {
8078 int ISDOpcode = TLI.InstructionOpcodeToISD(ToBePromoted->getOpcode());
8135 assert(ToBePromoted->getType() == Transition->getType() &&
8138 ToBePromoted->replaceAllUsesWith(Transition);
8142 ToBePromoted->mutateType(TransitionTy);
8146 for (Use &U : ToBePromoted->operands()) {
8150 NewVal = Transition->getOperand(getTransitionOriginalValueIdx());
8161 ToBePromoted->setOperand(U.getOperandNo(), NewVal);
8163 Transition->moveAfter(ToBePromoted);
8164 Transition->setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
8174 !TLI->canCombineStoreAndExtract(Inst->getOperand(0)->getType(),
8175 Inst->getOperand(1), CombineCost)))
8179 // Try to move it down the def-use chain, until:
8180 // - We can combine the transition with its single use
8182 // - We escape the current basic block
8185 BasicBlock *Parent = Inst->getParent();
8190 while (Inst->hasOneUse()) {
8191 Instruction *ToBePromoted = cast<Instruction>(*Inst->user_begin());
8194 if (ToBePromoted->getParent() != Parent) {
8196 << ToBePromoted->getParent()->getName()
8197 << ") than the transition (" << Parent->getName()
8229 /// (shl (zext I to i64), 32)), addr) -->
8233 /// For pair of {i32, i32}, i64 store --> two i32 stores.
8234 /// For pair of {i32, i16}, i64 store --> two i32 stores.
8235 /// For pair of {i16, i16}, i32 store --> two i16 stores.
8236 /// For pair of {i16, i8}, i32 store --> two i16 stores.
8237 /// For pair of {i8, i8}, i16 store --> two i8 stores.
8258 Type *StoreType = SI.getValueOperand()->getType();
8264 if (StoreType->isScalableTy())
8296 if (!LValue->getType()->isIntegerTy() ||
8297 DL.getTypeSizeInBits(LValue->getType()) > HalfValBitSize ||
8298 !HValue->getType()->isIntegerTy() ||
8299 DL.getTypeSizeInBits(HValue->getType()) > HalfValBitSize)
8306 EVT LowTy = LBC ? EVT::getEVT(LBC->getOperand(0)->getType())
8307 : EVT::getEVT(LValue->getType());
8308 EVT HighTy = HBC ? EVT::getEVT(HBC->getOperand(0)->getType())
8309 : EVT::getEVT(HValue->getType());
8314 IRBuilder<> Builder(SI.getContext());
8315 Builder.SetInsertPoint(&SI);
8319 if (LBC && LBC->getParent() != SI.getParent())
8320 LValue = Builder.CreateBitCast(LBC->getOperand(0), LBC->getType());
8321 if (HBC && HBC->getParent() != SI.getParent())
8322 HValue = Builder.CreateBitCast(HBC->getOperand(0), HBC->getType());
8326 V = Builder.CreateZExtOrBitCast(V, SplitStoreType);
8331 Addr = Builder.CreateGEP(
8337 // over-aligned or not, while the other will require adjustment.
8340 Builder.CreateAlignedStore(V, Addr, Alignment);
8355 return GEP->getNumOperands() == 2 && I.isSequential() &&
8356 isa<ConstantInt>(GEP->getOperand(1));
8366 // ---------- BEFORE ----------
8386 // ---------------------------
8388 // ---------- AFTER ----------
8398 // %UGEPI = gep %GEPI, (UIdx-Idx)
8400 // ---------------------------
8412 // between the register pressure and the length of data-flow critical
8418 BasicBlock *SrcBlock = GEPI->getParent();
8420 // (non-IndirectBr) cases exit early here.
8421 if (!isa<IndirectBrInst>(SrcBlock->getTerminator()))
8426 ConstantInt *GEPIIdx = cast<ConstantInt>(GEPI->getOperand(1));
8428 if (TTI->getIntImmCost(GEPIIdx->getValue(), GEPIIdx->getType(),
8432 Value *GEPIOp = GEPI->getOperand(0);
8437 if (GEPIOpI->getParent() != SrcBlock)
8441 if (llvm::none_of(GEPI->users(), [&](User *Usr) {
8443 if (I->getParent() != SrcBlock) {
8454 for (User *Usr : GEPIOp->users()) {
8462 if (UI->getParent() == SrcBlock)
8473 if (UGEPI->getOperand(0) != GEPIOp)
8475 if (UGEPI->getSourceElementType() != GEPI->getSourceElementType())
8477 if (GEPIIdx->getType() !=
8478 cast<ConstantInt>(UGEPI->getOperand(1))->getType())
8480 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8481 if (TTI->getIntImmCost(UGEPIIdx->getValue(), UGEPIIdx->getType(),
8489 // Check the materializing cost of (Uidx-Idx).
8491 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8492 APInt NewIdx = UGEPIIdx->getValue() - GEPIIdx->getValue();
8493 InstructionCost ImmCost = TTI->getIntImmCost(
8494 NewIdx, GEPIIdx->getType(), TargetTransformInfo::TCK_SizeAndLatency);
8500 UGEPI->setOperand(0, GEPI);
8501 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8503 GEPIIdx->getType(), UGEPIIdx->getValue() - GEPIIdx->getValue());
8504 UGEPI->setOperand(1, NewUGEPIIdx);
8507 if (!GEPI->isInBounds()) {
8508 UGEPI->setIsInBounds(false);
8513 assert(llvm::none_of(GEPIOp->users(),
8515 return cast<Instruction>(Usr)->getParent() != SrcBlock;
8534 if (!TLI.preferZeroCompareBranch() || !Branch->isConditional())
8537 ICmpInst *Cmp = dyn_cast<ICmpInst>(Branch->getCondition());
8538 if (!Cmp || !isa<ConstantInt>(Cmp->getOperand(1)) || !Cmp->hasOneUse())
8541 Value *X = Cmp->getOperand(0);
8542 APInt CmpC = cast<ConstantInt>(Cmp->getOperand(1))->getValue();
8544 for (auto *U : X->users()) {
8548 (UI->getParent() != Branch->getParent() &&
8549 UI->getParent() != Branch->getSuccessor(0) &&
8550 UI->getParent() != Branch->getSuccessor(1)) ||
8551 (UI->getParent() != Branch->getParent() &&
8552 !UI->getParent()->getSinglePredecessor()))
8555 if (CmpC.isPowerOf2() && Cmp->getPredicate() == ICmpInst::ICMP_ULT &&
8557 IRBuilder<> Builder(Branch);
8558 if (UI->getParent() != Branch->getParent())
8559 UI->moveBefore(Branch->getIterator());
8560 UI->dropPoisonGeneratingFlags();
8561 Value *NewCmp = Builder.CreateCmp(ICmpInst::ICMP_EQ, UI,
8562 ConstantInt::get(UI->getType(), 0));
8568 if (Cmp->isEquality() &&
8569 (match(UI, m_Add(m_Specific(X), m_SpecificInt(-CmpC))) ||
8571 IRBuilder<> Builder(Branch);
8572 if (UI->getParent() != Branch->getParent())
8573 UI->moveBefore(Branch->getIterator());
8574 UI->dropPoisonGeneratingFlags();
8575 Value *NewCmp = Builder.CreateCmp(Cmp->getPredicate(), UI,
8576 ConstantInt::get(UI->getType(), 0));
8603 P->eraseFromParent();
8616 // want to forward-subst the cast.
8617 if (isa<Constant>(CI->getOperand(0)))
8625 TLI->optimizeExtendOrTruncateConversion(
8626 I, LI->getLoopFor(I->getParent()), *TTI))
8632 if (TLI->getTypeAction(CI->getContext(),
8633 TLI->getValueType(*DL, CI->getType())) ==
8637 if (TLI->optimizeExtendOrTruncateConversion(
8638 I, LI->getLoopFor(I->getParent()), *TTI))
8657 LI->setMetadata(LLVMContext::MD_invariant_group, nullptr);
8659 unsigned AS = LI->getPointerAddressSpace();
8660 Modified |= optimizeMemoryInst(I, I->getOperand(0), LI->getType(), AS);
8667 SI->setMetadata(LLVMContext::MD_invariant_group, nullptr);
8668 unsigned AS = SI->getPointerAddressSpace();
8669 return optimizeMemoryInst(I, SI->getOperand(1),
8670 SI->getOperand(0)->getType(), AS);
8674 unsigned AS = RMW->getPointerAddressSpace();
8675 return optimizeMemoryInst(I, RMW->getPointerOperand(), RMW->getType(), AS);
8679 unsigned AS = CmpX->getPointerAddressSpace();
8680 return optimizeMemoryInst(I, CmpX->getPointerOperand(),
8681 CmpX->getCompareOperand()->getType(), AS);
8686 if (BinOp && BinOp->getOpcode() == Instruction::And && EnableAndCmpSinking &&
8690 // TODO: Move this into the switch on opcode - it handles shifts already.
8691 if (BinOp && (BinOp->getOpcode() == Instruction::AShr ||
8692 BinOp->getOpcode() == Instruction::LShr)) {
8693 ConstantInt *CI = dyn_cast<ConstantInt>(BinOp->getOperand(1));
8694 if (CI && TLI->hasExtractBitsInsn())
8700 if (GEPI->hasAllZeroIndices()) {
8701 /// The GEP operand must be a pointer, so must its result -> BitCast
8702 Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
8703 GEPI->getName(), GEPI->getIterator());
8704 NC->setDebugLoc(GEPI->getDebugLoc());
8719 // freeze(icmp a, const)) -> icmp (freeze a), const
8722 if (ICmpInst *II = dyn_cast<ICmpInst>(FI->getOperand(0)))
8724 else if (FCmpInst *F = dyn_cast<FCmpInst>(FI->getOperand(0)))
8725 CmpI = F->getFastMathFlags().none() ? F : nullptr;
8727 if (CmpI && CmpI->hasOneUse()) {
8728 auto Op0 = CmpI->getOperand(0), Op1 = CmpI->getOperand(1);
8735 auto *F = new FreezeInst(Const0 ? Op1 : Op0, "", CmpI->getIterator());
8736 F->takeName(FI);
8737 CmpI->setOperand(Const0 ? 1 : 0, F);
8740 FI->eraseFromParent();
8750 switch (I->getOpcode()) {
8775 if (!I.getType()->isIntegerTy() ||
8776 !TLI->isOperationLegalOrCustom(ISD::BITREVERSE,
8777 TLI->getValueType(*DL, I.getType(), true)))
8792 // across basic blocks and rewrite them to improve basic-block-at-a-time
8805 // opportunities in the BB. So we go back to the BB head to re-optimize
8866 // FIXME: should updating debug-info really cause the "changed" flag to fire,
8894 DVI->removeFromParent();
8896 DVI->insertBefore(VI->getParent()->getFirstInsertionPt());
8898 DVI->insertAfter(VI);
8902 DVR->removeFromParent();
8903 BasicBlock *VIBB = VI->getParent();
8905 VIBB->insertDbgRecordBefore(DVR, VIBB->getFirstInsertionPt());
8907 VIBB->insertDbgRecordAfter(DVR, &*VI);
8914 // to re-order dbg.value intrinsics.
8921 for (Value *V : DbgItem->location_ops())
8930 if (VI->isTerminator())
8935 if (isa<PHINode>(VI) && VI->getParent()->getTerminator()->isEHPad())
8951 DbgItem->setKillLocation();
8957 DbgInserterHelper(DbgItem, VI->getIterator());
8994 while (FirstInst != Block.end() && FirstInst->isDebugOrPseudoInst())
9000 II->moveBefore(FirstInst);
9039 if (!TM->Options.EnableFastISel || TLI->isJumpExpensive())
9056 if (Br1->getMetadata(LLVMContext::MD_unpredictable))
9094 Br1->setCondition(Cond1);
9095 LogicOp->eraseFromParent();
9100 Br1->setSuccessor(0, TmpBB);
9102 Br1->setSuccessor(1, TmpBB);
9107 I->removeFromParent();
9108 I->insertBefore(Br2->getIterator());
9124 TBB->replacePhiUsesWith(&BB, TmpBB);
9127 for (PHINode &PN : FBB->phis()) {
9159 Br1->setMetadata(LLVMContext::MD_prof,
9160 MDBuilder(Br1->getContext())
9167 Br2->setMetadata(LLVMContext::MD_prof,
9168 MDBuilder(Br2->getContext())
9195 Br1->setMetadata(LLVMContext::MD_prof,
9196 MDBuilder(Br1->getContext())
9202 Br2->setMetadata(LLVMContext::MD_prof,
9203 MDBuilder(Br2->getContext())
9212 TmpBB->dump());