Lines Matching +full:- +full:bi1
1 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
8 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
62 "phi-node-folding-threshold", cl::Hidden, cl::init(2),
67 "simplifycfg-dup-ret", cl::Hidden, cl::init(false),
71 SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true),
75 "simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true),
79 "simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true),
81 "precede - hoist multiple conditional stores into a single "
85 "simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false),
87 "basic blocks are unlikely to be if-converted as a result"));
90 "speculate-one-expensive-inst", cl::Hidden, cl::init(true),
95 "max-speculation-depth", cl::Hidden, cl::init(10),
123 /// ValueEqualityComparisonCase - Represents a case of a switch.
184 BasicBlock *SI1BB = SI1->getParent(); in SafeToMergeTerminators()
185 BasicBlock *SI2BB = SI2->getParent(); in SafeToMergeTerminators()
190 for (BasicBlock::iterator BBI = Succ->begin(); isa<PHINode>(BBI); ++BBI) { in SafeToMergeTerminators()
192 if (PN->getIncomingValueForBlock(SI1BB) != in SafeToMergeTerminators()
193 PN->getIncomingValueForBlock(SI2BB)) in SafeToMergeTerminators()
209 assert(SI1->isUnconditional() && SI2->isConditional()); in isProfitableToFoldUnconditional()
215 // 3> SI2->getCondition() and Cond have same operands. in isProfitableToFoldUnconditional()
216 CmpInst *Ci2 = dyn_cast<CmpInst>(SI2->getCondition()); in isProfitableToFoldUnconditional()
219 if (!(Cond->getOperand(0) == Ci2->getOperand(0) && in isProfitableToFoldUnconditional()
220 Cond->getOperand(1) == Ci2->getOperand(1)) && in isProfitableToFoldUnconditional()
221 !(Cond->getOperand(0) == Ci2->getOperand(1) && in isProfitableToFoldUnconditional()
222 Cond->getOperand(1) == Ci2->getOperand(0))) in isProfitableToFoldUnconditional()
225 BasicBlock *SI1BB = SI1->getParent(); in isProfitableToFoldUnconditional()
226 BasicBlock *SI2BB = SI2->getParent(); in isProfitableToFoldUnconditional()
230 for (BasicBlock::iterator BBI = Succ->begin(); isa<PHINode>(BBI); ++BBI) { in isProfitableToFoldUnconditional()
232 if (PN->getIncomingValueForBlock(SI1BB) != Cond || in isProfitableToFoldUnconditional()
233 !isa<ConstantInt>(PN->getIncomingValueForBlock(SI2BB))) in isProfitableToFoldUnconditional()
246 if (!isa<PHINode>(Succ->begin())) in AddPredecessorToBlock()
250 for (BasicBlock::iterator I = Succ->begin(); (PN = dyn_cast<PHINode>(I)); ++I) in AddPredecessorToBlock()
251 PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); in AddPredecessorToBlock()
270 /// If AggressiveInsts is non-null, and if V does not dominate BB, we check to
273 /// are non-trapping. If both are true, the instruction is inserted into the
276 /// The cost for most non-trapping instructions is defined as 1 except for
280 /// V plus its non-dominating operands. If that cost is greater than
287 // It is possible to hit a zero-cost cycle (phi/gep instructions for example), in DominatesMergePoint()
296 // Non-instructions all dominate instructions, but not all constantexprs in DominatesMergePoint()
299 if (C->canTrap()) in DominatesMergePoint()
303 BasicBlock *PBB = I->getParent(); in DominatesMergePoint()
313 BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator()); in DominatesMergePoint()
314 if (!BI || BI->isConditional() || BI->getSuccessor(0) != BB) in DominatesMergePoint()
323 if (AggressiveInsts->count(I)) in DominatesMergePoint()
341 (!SpeculateOneExpensiveInst || !AggressiveInsts->empty() || Depth > 0)) in DominatesMergePoint()
345 CostRemaining = (Cost > CostRemaining) ? 0 : CostRemaining - Cost; in DominatesMergePoint()
349 for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) in DominatesMergePoint()
354 AggressiveInsts->insert(I); in DominatesMergePoint()
363 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy()) in GetConstantInt()
366 // This is some kind of pointer constant. Turn it into a pointer-sized in GetConstantInt()
368 IntegerType *PtrTy = cast<IntegerType>(DL.getIntPtrType(V->getType())); in GetConstantInt()
376 if (CE->getOpcode() == Instruction::IntToPtr) in GetConstantInt()
377 if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) { in GetConstantInt()
379 if (CI->getType() == PtrTy) in GetConstantInt()
393 /// It will depth-first traverse the chain of comparison, seeking for patterns
440 (C = GetConstantInt(I->getOperand(1), DL)))) { in matchInstruction()
448 // (x & ~2^z) == y --> x == y || x == y|2^z in matchInstruction()
450 if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) { in matchInstruction()
453 // correct. Here is a CVC3 program to verify them for 64-bit values: in matchInstruction()
469 // Please note that each pattern must be a dual implication (<--> or in matchInstruction()
471 // implication is only one-way, an unsatisfiable condition on the left in matchInstruction()
481 // (x & ~mask) == y --> (x == y || x == (y | mask)) in matchInstruction()
484 // (x & -2) == 3 --> (x == 3 || x == 2) in matchInstruction()
492 if (match(ICI->getOperand(0), in matchInstruction()
495 if (Mask.isPowerOf2() && (C->getValue() & ~Mask) == C->getValue()) { in matchInstruction()
502 ConstantInt::get(C->getContext(), in matchInstruction()
503 C->getValue() | Mask)); in matchInstruction()
515 if (match(ICI->getOperand(0), in matchInstruction()
518 if (Mask.isPowerOf2() && (C->getValue() | Mask) == C->getValue()) { in matchInstruction()
524 Vals.push_back(ConstantInt::get(C->getContext(), in matchInstruction()
525 C->getValue() & ~Mask)); in matchInstruction()
532 if (!setValueOnce(ICI->getOperand(0))) in matchInstruction()
537 return ICI->getOperand(0); in matchInstruction()
542 ICI->getPredicate(), C->getValue()); in matchInstruction()
546 Value *CandidateVal = I->getOperand(0); in matchInstruction()
547 if (match(I->getOperand(0), m_Add(m_Value(RHSVal), m_APInt(RHSC)))) { in matchInstruction()
569 Vals.push_back(ConstantInt::get(I->getContext(), Tmp)); in matchInstruction()
582 bool isEQ = (I->getOpcode() == Instruction::Or); in gather()
584 // Keep a stack (SmallVector for efficiency) for depth-first traversal in gather()
597 if (I->getOpcode() == (isEQ ? Instruction::Or : Instruction::And)) { in gather()
598 if (Visited.insert(I->getOperand(1)).second) in gather()
599 DFT.push_back(I->getOperand(1)); in gather()
600 if (Visited.insert(I->getOperand(0)).second) in gather()
601 DFT.push_back(I->getOperand(0)); in gather()
629 Cond = dyn_cast<Instruction>(SI->getCondition()); in EraseTerminatorInstAndDCECond()
631 if (BI->isConditional()) in EraseTerminatorInstAndDCECond()
632 Cond = dyn_cast<Instruction>(BI->getCondition()); in EraseTerminatorInstAndDCECond()
634 Cond = dyn_cast<Instruction>(IBI->getAddress()); in EraseTerminatorInstAndDCECond()
637 TI->eraseFromParent(); in EraseTerminatorInstAndDCECond()
649 if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), in isValueEqualityComparison()
650 pred_end(SI->getParent())) <= in isValueEqualityComparison()
652 CV = SI->getCondition(); in isValueEqualityComparison()
654 if (BI->isConditional() && BI->getCondition()->hasOneUse()) in isValueEqualityComparison()
655 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) { in isValueEqualityComparison()
656 if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL)) in isValueEqualityComparison()
657 CV = ICI->getOperand(0); in isValueEqualityComparison()
663 Value *Ptr = PTII->getPointerOperand(); in isValueEqualityComparison()
664 if (PTII->getType() == DL.getIntPtrType(Ptr->getType())) in isValueEqualityComparison()
676 Cases.reserve(SI->getNumCases()); in GetValueEqualityComparisonCases()
677 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; in GetValueEqualityComparisonCases()
681 return SI->getDefaultDest(); in GetValueEqualityComparisonCases()
685 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); in GetValueEqualityComparisonCases()
686 BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE); in GetValueEqualityComparisonCases()
688 GetConstantInt(ICI->getOperand(1), DL), Succ)); in GetValueEqualityComparisonCases()
689 return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); in GetValueEqualityComparisonCases()
706 if (V1->size() > V2->size()) in ValuesOverlap()
709 if (V1->size() == 0) in ValuesOverlap()
711 if (V1->size() == 1) { in ValuesOverlap()
714 for (unsigned i = 0, e = V2->size(); i != e; ++i) in ValuesOverlap()
720 array_pod_sort(V1->begin(), V1->end()); in ValuesOverlap()
721 array_pod_sort(V2->begin(), V2->end()); in ValuesOverlap()
722 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); in ValuesOverlap()
741 Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); in SimplifyEqualityComparisonWithOnlyPredecessor()
756 GetValueEqualityComparisonCases(Pred->getTerminator(), PredCases); in SimplifyEqualityComparisonWithOnlyPredecessor()
766 if (PredDef == TI->getParent()) { in SimplifyEqualityComparisonWithOnlyPredecessor()
782 ThisCases[0].Dest->removePredecessor(TI->getParent()); in SimplifyEqualityComparisonWithOnlyPredecessor()
784 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() in SimplifyEqualityComparisonWithOnlyPredecessor()
798 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() in SimplifyEqualityComparisonWithOnlyPredecessor()
803 MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); in SimplifyEqualityComparisonWithOnlyPredecessor()
804 bool HasWeight = MD && (MD->getNumOperands() == 2 + SI->getNumCases()); in SimplifyEqualityComparisonWithOnlyPredecessor()
806 for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; in SimplifyEqualityComparisonWithOnlyPredecessor()
808 ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i)); in SimplifyEqualityComparisonWithOnlyPredecessor()
809 Weights.push_back(CI->getValue().getZExtValue()); in SimplifyEqualityComparisonWithOnlyPredecessor()
811 for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) { in SimplifyEqualityComparisonWithOnlyPredecessor()
812 --i; in SimplifyEqualityComparisonWithOnlyPredecessor()
818 i.getCaseSuccessor()->removePredecessor(TI->getParent()); in SimplifyEqualityComparisonWithOnlyPredecessor()
819 SI->removeCase(i); in SimplifyEqualityComparisonWithOnlyPredecessor()
823 SI->setMetadata(LLVMContext::MD_prof, in SimplifyEqualityComparisonWithOnlyPredecessor()
824 MDBuilder(SI->getParent()->getContext()) in SimplifyEqualityComparisonWithOnlyPredecessor()
834 BasicBlock *TIBB = TI->getParent(); in SimplifyEqualityComparisonWithOnlyPredecessor()
860 Succ->removePredecessor(TIBB); in SimplifyEqualityComparisonWithOnlyPredecessor()
868 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() in SimplifyEqualityComparisonWithOnlyPredecessor()
882 return LHS->getValue().ult(RHS->getValue()); in operator ()()
893 return LHS->getValue().ult(RHS->getValue()) ? 1 : -1; in ConstantIntSortPredicate()
897 MDNode *ProfMD = I->getMetadata(LLVMContext::MD_prof); in HasBranchWeights()
898 if (ProfMD && ProfMD->getOperand(0)) in HasBranchWeights()
899 if (MDString *MDS = dyn_cast<MDString>(ProfMD->getOperand(0))) in HasBranchWeights()
900 return MDS->getString().equals("branch_weights"); in HasBranchWeights()
906 /// of the vector. If TI is a conditional eq, we need to swap the branch-weight
910 MDNode *MD = TI->getMetadata(LLVMContext::MD_prof); in GetBranchWeights()
912 for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) { in GetBranchWeights()
913 ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(i)); in GetBranchWeights()
914 Weights.push_back(CI->getValue().getZExtValue()); in GetBranchWeights()
918 // and the corresponding branch-weight data is at index 2. We swap the in GetBranchWeights()
922 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); in GetBranchWeights()
923 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) in GetBranchWeights()
932 unsigned Offset = 32 - countLeadingZeros(Max); in FitWeights()
944 BasicBlock *BB = TI->getParent(); in FoldValueComparisonIntoPredecessors()
954 TerminatorInst *PTI = Pred->getTerminator(); in FoldValueComparisonIntoPredecessors()
977 // branch-weight metadata is inconsistent here. in FoldValueComparisonIntoPredecessors()
989 // branch-weight metadata is inconsistent here. in FoldValueComparisonIntoPredecessors()
1014 --i; in FoldValueComparisonIntoPredecessors()
1015 --e; in FoldValueComparisonIntoPredecessors()
1020 PredDefault->removePredecessor(Pred); in FoldValueComparisonIntoPredecessors()
1067 --i; in FoldValueComparisonIntoPredecessors()
1068 --e; in FoldValueComparisonIntoPredecessors()
1102 if (CV->getType()->isPointerTy()) { in FoldValueComparisonIntoPredecessors()
1103 CV = Builder.CreatePtrToInt(CV, DL.getIntPtrType(CV->getType()), in FoldValueComparisonIntoPredecessors()
1110 NewSI->setDebugLoc(PTI->getDebugLoc()); in FoldValueComparisonIntoPredecessors()
1112 NewSI->addCase(V.Value, V.Dest); in FoldValueComparisonIntoPredecessors()
1120 NewSI->setMetadata( in FoldValueComparisonIntoPredecessors()
1122 MDBuilder(BB->getContext()).createBranchWeights(MDWeights)); in FoldValueComparisonIntoPredecessors()
1131 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) in FoldValueComparisonIntoPredecessors()
1132 if (NewSI->getSuccessor(i) == BB) { in FoldValueComparisonIntoPredecessors()
1136 InfLoopBlock = BasicBlock::Create(BB->getContext(), "infloop", in FoldValueComparisonIntoPredecessors()
1137 BB->getParent()); in FoldValueComparisonIntoPredecessors()
1140 NewSI->setSuccessor(i, InfLoopBlock); in FoldValueComparisonIntoPredecessors()
1156 for (BasicBlock::iterator BBI = Succ->begin(); in isSafeToHoistInvoke()
1158 Value *BB1V = PN->getIncomingValueForBlock(BB1); in isSafeToHoistInvoke()
1159 Value *BB2V = PN->getIncomingValueForBlock(BB2); in isSafeToHoistInvoke()
1180 BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. in HoistThenElseCodeToIf()
1181 BasicBlock *BB2 = BI->getSuccessor(1); // The false destination in HoistThenElseCodeToIf()
1183 BasicBlock::iterator BB1_Itr = BB1->begin(); in HoistThenElseCodeToIf()
1184 BasicBlock::iterator BB2_Itr = BB2->begin(); in HoistThenElseCodeToIf()
1190 if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { in HoistThenElseCodeToIf()
1196 if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) || in HoistThenElseCodeToIf()
1200 BasicBlock *BIParent = BI->getParent(); in HoistThenElseCodeToIf()
1215 BIParent->getInstList().splice(BI->getIterator(), BB1->getInstList(), I1); in HoistThenElseCodeToIf()
1216 if (!I2->use_empty()) in HoistThenElseCodeToIf()
1217 I2->replaceAllUsesWith(I1); in HoistThenElseCodeToIf()
1218 I1->intersectOptionalDataWith(I2); in HoistThenElseCodeToIf()
1230 I2->eraseFromParent(); in HoistThenElseCodeToIf()
1238 if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { in HoistThenElseCodeToIf()
1244 } while (I1->isIdenticalToWhenDefined(I2)); in HoistThenElseCodeToIf()
1255 for (BasicBlock::iterator BBI = Succ->begin(); in HoistThenElseCodeToIf()
1257 Value *BB1V = PN->getIncomingValueForBlock(BB1); in HoistThenElseCodeToIf()
1258 Value *BB2V = PN->getIncomingValueForBlock(BB2); in HoistThenElseCodeToIf()
1276 Instruction *NT = I1->clone(); in HoistThenElseCodeToIf()
1277 BIParent->getInstList().insert(BI->getIterator(), NT); in HoistThenElseCodeToIf()
1278 if (!NT->getType()->isVoidTy()) { in HoistThenElseCodeToIf()
1279 I1->replaceAllUsesWith(NT); in HoistThenElseCodeToIf()
1280 I2->replaceAllUsesWith(NT); in HoistThenElseCodeToIf()
1281 NT->takeName(I1); in HoistThenElseCodeToIf()
1292 for (BasicBlock::iterator BBI = Succ->begin(); in HoistThenElseCodeToIf()
1294 Value *BB1V = PN->getIncomingValueForBlock(BB1); in HoistThenElseCodeToIf()
1295 Value *BB2V = PN->getIncomingValueForBlock(BB2); in HoistThenElseCodeToIf()
1304 Builder.CreateSelect(BI->getCondition(), BB1V, BB2V, in HoistThenElseCodeToIf()
1305 BB1V->getName() + "." + BB2V->getName(), BI)); in HoistThenElseCodeToIf()
1308 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) in HoistThenElseCodeToIf()
1309 if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) in HoistThenElseCodeToIf()
1310 PN->setIncomingValue(i, SI); in HoistThenElseCodeToIf()
1326 static bool SinkThenElseCodeToEnd(BranchInst *BI1) { in SinkThenElseCodeToEnd() argument
1327 assert(BI1->isUnconditional()); in SinkThenElseCodeToEnd()
1328 BasicBlock *BB1 = BI1->getParent(); in SinkThenElseCodeToEnd()
1329 BasicBlock *BBEnd = BI1->getSuccessor(0); in SinkThenElseCodeToEnd()
1341 BranchInst *BI2 = dyn_cast<BranchInst>(BB2->getTerminator()); in SinkThenElseCodeToEnd()
1342 if (!BI2 || !BI2->isUnconditional()) in SinkThenElseCodeToEnd()
1348 for (BasicBlock::iterator I = BBEnd->begin(), E = BBEnd->end(); I != E; ++I) { in SinkThenElseCodeToEnd()
1350 Value *BB1V = PN->getIncomingValueForBlock(BB1); in SinkThenElseCodeToEnd()
1351 Value *BB2V = PN->getIncomingValueForBlock(BB2); in SinkThenElseCodeToEnd()
1364 BasicBlock::InstListType::reverse_iterator RI1 = BB1->getInstList().rbegin(), in SinkThenElseCodeToEnd()
1365 RE1 = BB1->getInstList().rend(), in SinkThenElseCodeToEnd()
1366 RI2 = BB2->getInstList().rbegin(), in SinkThenElseCodeToEnd()
1367 RE2 = BB2->getInstList().rend(); in SinkThenElseCodeToEnd()
1397 // Cannot move control-flow-involving, volatile loads, vaarg, etc. in SinkThenElseCodeToEnd()
1399 isa<TerminatorInst>(I2) || I1->isEHPad() || I2->isEHPad() || in SinkThenElseCodeToEnd()
1401 I1->mayHaveSideEffects() || I2->mayHaveSideEffects() || in SinkThenElseCodeToEnd()
1402 I1->mayReadOrWriteMemory() || I2->mayReadOrWriteMemory() || in SinkThenElseCodeToEnd()
1403 !I1->hasOneUse() || !I2->hasOneUse() || !JointValueMap.count(InstPair)) in SinkThenElseCodeToEnd()
1410 if (ICmp1 && ICmp2 && ICmp1->getOperand(0) != ICmp2->getOperand(0) && in SinkThenElseCodeToEnd()
1411 ICmp1->getOperand(1) != ICmp2->getOperand(1) && in SinkThenElseCodeToEnd()
1412 (ICmp1->getOperand(0) == ICmp2->getOperand(1) || in SinkThenElseCodeToEnd()
1413 ICmp1->getOperand(1) == ICmp2->getOperand(0))) { in SinkThenElseCodeToEnd()
1414 ICmp2->swapOperands(); in SinkThenElseCodeToEnd()
1417 if (!I1->isSameOperationAs(I2)) { in SinkThenElseCodeToEnd()
1419 ICmp2->swapOperands(); in SinkThenElseCodeToEnd()
1428 for (unsigned I = 0, E = I1->getNumOperands(); I != E; ++I) { in SinkThenElseCodeToEnd()
1429 if (I1->getOperand(I) == I2->getOperand(I)) in SinkThenElseCodeToEnd()
1431 // Early exit if we have more-than one pair of different operands or if in SinkThenElseCodeToEnd()
1433 if (Op1Idx != ~0U || isa<Constant>(I1->getOperand(I)) || in SinkThenElseCodeToEnd()
1434 isa<Constant>(I2->getOperand(I))) { in SinkThenElseCodeToEnd()
1437 ICmp2->swapOperands(); in SinkThenElseCodeToEnd()
1440 DifferentOp1 = I1->getOperand(I); in SinkThenElseCodeToEnd()
1442 DifferentOp2 = I2->getOperand(I); in SinkThenElseCodeToEnd()
1454 PHINode::Create(DifferentOp1->getType(), 2, in SinkThenElseCodeToEnd()
1455 DifferentOp1->getName() + ".sink", &BBEnd->front()); in SinkThenElseCodeToEnd()
1456 NewPN->addIncoming(DifferentOp1, BB1); in SinkThenElseCodeToEnd()
1457 NewPN->addIncoming(DifferentOp2, BB2); in SinkThenElseCodeToEnd()
1461 I1->setOperand(Op1Idx, NewPN); in SinkThenElseCodeToEnd()
1468 bool UpdateRE1 = (I1 == &BB1->front()), UpdateRE2 = (I2 == &BB2->front()); in SinkThenElseCodeToEnd()
1470 BBEnd->getInstList().splice(FirstNonPhiInBBEnd->getIterator(), in SinkThenElseCodeToEnd()
1471 BB1->getInstList(), I1); in SinkThenElseCodeToEnd()
1472 if (!OldPN->use_empty()) in SinkThenElseCodeToEnd()
1473 OldPN->replaceAllUsesWith(I1); in SinkThenElseCodeToEnd()
1474 OldPN->eraseFromParent(); in SinkThenElseCodeToEnd()
1476 if (!I2->use_empty()) in SinkThenElseCodeToEnd()
1477 I2->replaceAllUsesWith(I1); in SinkThenElseCodeToEnd()
1478 I1->intersectOptionalDataWith(I2); in SinkThenElseCodeToEnd()
1481 I2->eraseFromParent(); in SinkThenElseCodeToEnd()
1484 RE1 = BB1->getInstList().rend(); in SinkThenElseCodeToEnd()
1486 RE2 = BB2->getInstList().rend(); in SinkThenElseCodeToEnd()
1527 if (!StoreToHoist->isSimple()) in isSafeToSpeculateStore()
1530 Value *StorePtr = StoreToHoist->getPointerOperand(); in isSafeToSpeculateStore()
1540 --MaxNumInstToLookAt; in isSafeToSpeculateStore()
1548 if (SI->getPointerOperand() == StorePtr) in isSafeToSpeculateStore()
1550 return SI->getValueOperand(); in isSafeToSpeculateStore()
1598 Value *BrCond = BI->getCondition(); in SpeculativelyExecuteBB()
1602 BasicBlock *BB = BI->getParent(); in SpeculativelyExecuteBB()
1603 BasicBlock *EndBB = ThenBB->getTerminator()->getSuccessor(0); in SpeculativelyExecuteBB()
1608 if (ThenBB != BI->getSuccessor(0)) { in SpeculativelyExecuteBB()
1609 assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?"); in SpeculativelyExecuteBB()
1612 assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block"); in SpeculativelyExecuteBB()
1616 // - They are defined in BB, and in SpeculativelyExecuteBB()
1617 // - They have no side effects, and in SpeculativelyExecuteBB()
1618 // - All of their uses are in CondBB. in SpeculativelyExecuteBB()
1624 for (BasicBlock::iterator BBI = ThenBB->begin(), in SpeculativelyExecuteBB()
1625 BBE = std::prev(ThenBB->end()); in SpeculativelyExecuteBB()
1655 for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) { in SpeculativelyExecuteBB()
1657 if (!OpI || OpI->getParent() != BB || OpI->mayHaveSideEffects()) in SpeculativelyExecuteBB()
1671 if (I->first->getNumUses() == I->second) { in SpeculativelyExecuteBB()
1679 for (BasicBlock::iterator I = EndBB->begin(); in SpeculativelyExecuteBB()
1681 Value *OrigV = PN->getIncomingValueForBlock(BB); in SpeculativelyExecuteBB()
1682 Value *ThenV = PN->getIncomingValueForBlock(ThenBB); in SpeculativelyExecuteBB()
1724 // If we get here, we can hoist the instruction and if-convert. in SpeculativelyExecuteBB()
1730 Value *TrueV = SpeculatedStore->getValueOperand(); in SpeculativelyExecuteBB()
1735 BrCond, TrueV, FalseV, TrueV->getName() + "." + FalseV->getName(), BI); in SpeculativelyExecuteBB()
1736 SpeculatedStore->setOperand(0, S); in SpeculativelyExecuteBB()
1745 BB->getInstList().splice(BI->getIterator(), ThenBB->getInstList(), in SpeculativelyExecuteBB()
1746 ThenBB->begin(), std::prev(ThenBB->end())); in SpeculativelyExecuteBB()
1750 for (BasicBlock::iterator I = EndBB->begin(); in SpeculativelyExecuteBB()
1752 unsigned OrigI = PN->getBasicBlockIndex(BB); in SpeculativelyExecuteBB()
1753 unsigned ThenI = PN->getBasicBlockIndex(ThenBB); in SpeculativelyExecuteBB()
1754 Value *OrigV = PN->getIncomingValue(OrigI); in SpeculativelyExecuteBB()
1755 Value *ThenV = PN->getIncomingValue(ThenI); in SpeculativelyExecuteBB()
1768 BrCond, TrueV, FalseV, TrueV->getName() + "." + FalseV->getName(), BI); in SpeculativelyExecuteBB()
1769 PN->setIncomingValue(OrigI, V); in SpeculativelyExecuteBB()
1770 PN->setIncomingValue(ThenI, V); in SpeculativelyExecuteBB()
1779 BranchInst *BI = cast<BranchInst>(BB->getTerminator()); in BlockIsSimpleEnoughToThreadThrough()
1782 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { in BlockIsSimpleEnoughToThreadThrough()
1791 for (User *U : BBI->users()) { in BlockIsSimpleEnoughToThreadThrough()
1793 if (UI->getParent() != BB || isa<PHINode>(UI)) in BlockIsSimpleEnoughToThreadThrough()
1807 BasicBlock *BB = BI->getParent(); in FoldCondBranchOnPHI()
1808 PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); in FoldCondBranchOnPHI()
1811 if (!PN || PN->getParent() != BB || !PN->hasOneUse()) in FoldCondBranchOnPHI()
1815 if (PN->getNumIncomingValues() == 1) { in FoldCondBranchOnPHI()
1816 FoldSingleEntryPHINodes(PN->getParent()); in FoldCondBranchOnPHI()
1827 return CI && (CI->cannotDuplicate() || CI->isConvergent()); in FoldCondBranchOnPHI()
1833 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { in FoldCondBranchOnPHI()
1834 ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i)); in FoldCondBranchOnPHI()
1835 if (!CB || !CB->getType()->isIntegerTy(1)) in FoldCondBranchOnPHI()
1840 BasicBlock *PredBB = PN->getIncomingBlock(i); in FoldCondBranchOnPHI()
1841 BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); in FoldCondBranchOnPHI()
1846 if (isa<IndirectBrInst>(PredBB->getTerminator())) in FoldCondBranchOnPHI()
1854 BasicBlock::Create(BB->getContext(), RealDest->getName() + ".critedge", in FoldCondBranchOnPHI()
1855 RealDest->getParent(), RealDest); in FoldCondBranchOnPHI()
1864 BasicBlock::iterator InsertPt = EdgeBB->begin(); in FoldCondBranchOnPHI()
1866 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { in FoldCondBranchOnPHI()
1868 TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); in FoldCondBranchOnPHI()
1872 Instruction *N = BBI->clone(); in FoldCondBranchOnPHI()
1873 if (BBI->hasName()) in FoldCondBranchOnPHI()
1874 N->setName(BBI->getName() + ".c"); in FoldCondBranchOnPHI()
1877 for (User::op_iterator i = N->op_begin(), e = N->op_end(); i != e; ++i) { in FoldCondBranchOnPHI()
1880 *i = PI->second; in FoldCondBranchOnPHI()
1885 if (!BBI->use_empty()) in FoldCondBranchOnPHI()
1887 if (!N->mayHaveSideEffects()) { in FoldCondBranchOnPHI()
1892 if (!BBI->use_empty()) in FoldCondBranchOnPHI()
1897 EdgeBB->getInstList().insert(InsertPt, N); in FoldCondBranchOnPHI()
1902 TerminatorInst *PredBBTI = PredBB->getTerminator(); in FoldCondBranchOnPHI()
1903 for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) in FoldCondBranchOnPHI()
1904 if (PredBBTI->getSuccessor(i) == BB) { in FoldCondBranchOnPHI()
1905 BB->removePredecessor(PredBB); in FoldCondBranchOnPHI()
1906 PredBBTI->setSuccessor(i, EdgeBB); in FoldCondBranchOnPHI()
1916 /// Given a BB that starts with the specified two-entry PHI node,
1926 BasicBlock *BB = PN->getParent(); in FoldTwoEntryPHINode()
1934 // Okay, we found that we can merge this two-entry phi node into a select. in FoldTwoEntryPHINode()
1936 // At some point this becomes non-profitable (particularly if the target in FoldTwoEntryPHINode()
1940 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I) in FoldTwoEntryPHINode()
1953 for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) { in FoldTwoEntryPHINode()
1956 PN->replaceAllUsesWith(V); in FoldTwoEntryPHINode()
1957 PN->eraseFromParent(); in FoldTwoEntryPHINode()
1961 if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts, in FoldTwoEntryPHINode()
1963 !DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts, in FoldTwoEntryPHINode()
1970 PN = dyn_cast<PHINode>(BB->begin()); in FoldTwoEntryPHINode()
1976 if (PN->getType()->isIntegerTy(1) && in FoldTwoEntryPHINode()
1977 (isa<BinaryOperator>(PN->getIncomingValue(0)) || in FoldTwoEntryPHINode()
1978 isa<BinaryOperator>(PN->getIncomingValue(1)) || in FoldTwoEntryPHINode()
1987 BasicBlock *IfBlock1 = PN->getIncomingBlock(0); in FoldTwoEntryPHINode()
1988 BasicBlock *IfBlock2 = PN->getIncomingBlock(1); in FoldTwoEntryPHINode()
1989 if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) { in FoldTwoEntryPHINode()
1993 for (BasicBlock::iterator I = IfBlock1->begin(); !isa<TerminatorInst>(I); in FoldTwoEntryPHINode()
2003 if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) { in FoldTwoEntryPHINode()
2007 for (BasicBlock::iterator I = IfBlock2->begin(); !isa<TerminatorInst>(I); in FoldTwoEntryPHINode()
2018 << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); in FoldTwoEntryPHINode()
2022 Instruction *InsertPt = DomBlock->getTerminator(); in FoldTwoEntryPHINode()
2028 DomBlock->getInstList().splice(InsertPt->getIterator(), in FoldTwoEntryPHINode()
2029 IfBlock1->getInstList(), IfBlock1->begin(), in FoldTwoEntryPHINode()
2030 IfBlock1->getTerminator()->getIterator()); in FoldTwoEntryPHINode()
2032 DomBlock->getInstList().splice(InsertPt->getIterator(), in FoldTwoEntryPHINode()
2033 IfBlock2->getInstList(), IfBlock2->begin(), in FoldTwoEntryPHINode()
2034 IfBlock2->getTerminator()->getIterator()); in FoldTwoEntryPHINode()
2036 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { in FoldTwoEntryPHINode()
2038 Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); in FoldTwoEntryPHINode()
2039 Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); in FoldTwoEntryPHINode()
2042 PN->replaceAllUsesWith(Sel); in FoldTwoEntryPHINode()
2043 Sel->takeName(PN); in FoldTwoEntryPHINode()
2044 PN->eraseFromParent(); in FoldTwoEntryPHINode()
2050 TerminatorInst *OldTI = DomBlock->getTerminator(); in FoldTwoEntryPHINode()
2053 OldTI->eraseFromParent(); in FoldTwoEntryPHINode()
2062 assert(BI->isConditional() && "Must be a conditional branch"); in SimplifyCondBranchToTwoReturns()
2063 BasicBlock *TrueSucc = BI->getSuccessor(0); in SimplifyCondBranchToTwoReturns()
2064 BasicBlock *FalseSucc = BI->getSuccessor(1); in SimplifyCondBranchToTwoReturns()
2065 ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator()); in SimplifyCondBranchToTwoReturns()
2066 ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator()); in SimplifyCondBranchToTwoReturns()
2071 if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator()) in SimplifyCondBranchToTwoReturns()
2073 if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator()) in SimplifyCondBranchToTwoReturns()
2080 if (FalseRet->getNumOperands() == 0) { in SimplifyCondBranchToTwoReturns()
2081 TrueSucc->removePredecessor(BI->getParent()); in SimplifyCondBranchToTwoReturns()
2082 FalseSucc->removePredecessor(BI->getParent()); in SimplifyCondBranchToTwoReturns()
2090 Value *TrueValue = TrueRet->getReturnValue(); in SimplifyCondBranchToTwoReturns()
2091 Value *FalseValue = FalseRet->getReturnValue(); in SimplifyCondBranchToTwoReturns()
2095 if (TVPN->getParent() == TrueSucc) in SimplifyCondBranchToTwoReturns()
2096 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); in SimplifyCondBranchToTwoReturns()
2098 if (FVPN->getParent() == FalseSucc) in SimplifyCondBranchToTwoReturns()
2099 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); in SimplifyCondBranchToTwoReturns()
2103 // normally the case, but we could have a potentially-trapping in SimplifyCondBranchToTwoReturns()
2107 if (TCV->canTrap()) in SimplifyCondBranchToTwoReturns()
2110 if (FCV->canTrap()) in SimplifyCondBranchToTwoReturns()
2115 TrueSucc->removePredecessor(BI->getParent()); in SimplifyCondBranchToTwoReturns()
2116 FalseSucc->removePredecessor(BI->getParent()); in SimplifyCondBranchToTwoReturns()
2119 Value *BrCond = BI->getCondition(); in SimplifyCondBranchToTwoReturns()
2153 if (Inst->isIdenticalTo(PBI)) { in checkCSEInPredecessor()
2154 Inst->replaceAllUsesWith(PBI); in checkCSEInPredecessor()
2155 Inst->eraseFromParent(); in checkCSEInPredecessor()
2171 PBI->extractProfMetadata(PredTrueWeight, PredFalseWeight); in extractPredSuccWeights()
2173 BI->extractProfMetadata(SuccTrueWeight, SuccFalseWeight); in extractPredSuccWeights()
2189 BasicBlock *BB = BI->getParent(); in FoldBranchToCommonDest()
2192 if (BI->isConditional()) in FoldBranchToCommonDest()
2193 Cond = dyn_cast<Instruction>(BI->getCondition()); in FoldBranchToCommonDest()
2199 if (BasicBlock *PB = BB->getSinglePredecessor()) in FoldBranchToCommonDest()
2200 if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator())) in FoldBranchToCommonDest()
2201 if (PBI->isConditional() && in FoldBranchToCommonDest()
2202 (BI->getSuccessor(0) == PBI->getSuccessor(0) || in FoldBranchToCommonDest()
2203 BI->getSuccessor(0) == PBI->getSuccessor(1))) { in FoldBranchToCommonDest()
2204 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) { in FoldBranchToCommonDest()
2221 Cond->getParent() != BB || !Cond->hasOneUse()) in FoldBranchToCommonDest()
2225 BasicBlock::iterator CondIt = ++Cond->getIterator(); in FoldBranchToCommonDest()
2240 for (auto I = BB->begin(); Cond != &*I; ++I) { in FoldBranchToCommonDest()
2244 if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(&*I)) in FoldBranchToCommonDest()
2247 Instruction *User = dyn_cast<Instruction>(I->user_back()); in FoldBranchToCommonDest()
2248 if (User == nullptr || User->getParent() != BB) in FoldBranchToCommonDest()
2260 // neither operand is a potentially-trapping constant expression. in FoldBranchToCommonDest()
2261 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0))) in FoldBranchToCommonDest()
2262 if (CE->canTrap()) in FoldBranchToCommonDest()
2264 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1))) in FoldBranchToCommonDest()
2265 if (CE->canTrap()) in FoldBranchToCommonDest()
2269 BasicBlock *TrueDest = BI->getSuccessor(0); in FoldBranchToCommonDest()
2270 BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr; in FoldBranchToCommonDest()
2276 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator()); in FoldBranchToCommonDest()
2282 if (!PBI || PBI->isUnconditional() || in FoldBranchToCommonDest()
2283 (BI->isConditional() && !SafeToMergeTerminators(BI, PBI)) || in FoldBranchToCommonDest()
2284 (!BI->isConditional() && in FoldBranchToCommonDest()
2292 if (BI->isConditional()) { in FoldBranchToCommonDest()
2293 if (PBI->getSuccessor(0) == TrueDest) { in FoldBranchToCommonDest()
2295 } else if (PBI->getSuccessor(1) == FalseDest) { in FoldBranchToCommonDest()
2297 } else if (PBI->getSuccessor(0) == FalseDest) { in FoldBranchToCommonDest()
2300 } else if (PBI->getSuccessor(1) == TrueDest) { in FoldBranchToCommonDest()
2307 if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest) in FoldBranchToCommonDest()
2316 Value *NewCond = PBI->getCondition(); in FoldBranchToCommonDest()
2318 if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) { in FoldBranchToCommonDest()
2320 CI->setPredicate(CI->getInversePredicate()); in FoldBranchToCommonDest()
2323 Builder.CreateNot(NewCond, PBI->getCondition()->getName() + ".not"); in FoldBranchToCommonDest()
2326 PBI->setCondition(NewCond); in FoldBranchToCommonDest()
2327 PBI->swapSuccessors(); in FoldBranchToCommonDest()
2337 for (auto BonusInst = BB->begin(); Cond != &*BonusInst; ++BonusInst) { in FoldBranchToCommonDest()
2340 Instruction *NewBonusInst = BonusInst->clone(); in FoldBranchToCommonDest()
2350 NewBonusInst->dropUnknownNonDebugMetadata(); in FoldBranchToCommonDest()
2352 PredBlock->getInstList().insert(PBI->getIterator(), NewBonusInst); in FoldBranchToCommonDest()
2353 NewBonusInst->takeName(&*BonusInst); in FoldBranchToCommonDest()
2354 BonusInst->setName(BonusInst->getName() + ".old"); in FoldBranchToCommonDest()
2359 Instruction *New = Cond->clone(); in FoldBranchToCommonDest()
2362 PredBlock->getInstList().insert(PBI->getIterator(), New); in FoldBranchToCommonDest()
2363 New->takeName(Cond); in FoldBranchToCommonDest()
2364 Cond->setName(New->getName() + ".old"); in FoldBranchToCommonDest()
2366 if (BI->isConditional()) { in FoldBranchToCommonDest()
2368 Builder.CreateBinOp(Opc, PBI->getCondition(), New, "or.cond")); in FoldBranchToCommonDest()
2369 PBI->setCondition(NewCond); in FoldBranchToCommonDest()
2377 if (PBI->getSuccessor(0) == BB) { in FoldBranchToCommonDest()
2386 // Therefore, we will not have overflow using 64-bit arithmetic. in FoldBranchToCommonDest()
2392 PBI->setSuccessor(0, TrueDest); in FoldBranchToCommonDest()
2394 if (PBI->getSuccessor(1) == BB) { in FoldBranchToCommonDest()
2407 PBI->setSuccessor(1, FalseDest); in FoldBranchToCommonDest()
2415 PBI->setMetadata( in FoldBranchToCommonDest()
2417 MDBuilder(BI->getContext()).createBranchWeights(MDWeights)); in FoldBranchToCommonDest()
2419 PBI->setMetadata(LLVMContext::MD_prof, nullptr); in FoldBranchToCommonDest()
2424 PHIs[i]->getIncomingValueForBlock(PBI->getParent())); in FoldBranchToCommonDest()
2425 assert(PBI_C->getType()->isIntegerTy(1)); in FoldBranchToCommonDest()
2427 if (PBI->getSuccessor(0) == TrueDest) { in FoldBranchToCommonDest()
2432 Builder.CreateNot(PBI->getCondition(), "not.cond")); in FoldBranchToCommonDest()
2435 if (PBI_C->isOne()) in FoldBranchToCommonDest()
2437 Instruction::Or, PBI->getCondition(), MergedCond, "or.cond")); in FoldBranchToCommonDest()
2443 Instruction::And, PBI->getCondition(), New, "and.cond")); in FoldBranchToCommonDest()
2444 if (PBI_C->isOne()) { in FoldBranchToCommonDest()
2446 Builder.CreateNot(PBI->getCondition(), "not.cond")); in FoldBranchToCommonDest()
2452 PHIs[i]->setIncomingValue(PHIs[i]->getBasicBlockIndex(PBI->getParent()), in FoldBranchToCommonDest()
2467 I.clone()->insertBefore(PBI); in FoldBranchToCommonDest()
2510 BasicBlock *Succ = BB->getSingleSuccessor(); in ensureValueAvailableInSuccessor()
2512 for (auto I = Succ->begin(); isa<PHINode>(I); ++I) in ensureValueAvailableInSuccessor()
2513 if (cast<PHINode>(I)->getIncomingValueForBlock(BB) == V) { in ensureValueAvailableInSuccessor()
2521 if (PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV) in ensureValueAvailableInSuccessor()
2530 (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB)) in ensureValueAvailableInSuccessor()
2533 PHI = PHINode::Create(V->getType(), 2, "simplifycfg.merge", &Succ->front()); in ensureValueAvailableInSuccessor()
2534 PHI->addIncoming(V, BB); in ensureValueAvailableInSuccessor()
2537 PHI->addIncoming( in ensureValueAvailableInSuccessor()
2538 AlternativeV ? AlternativeV : UndefValue::get(V->getType()), PredBB); in ensureValueAvailableInSuccessor()
2548 I.getType()->isPointerTy(); in mergeConditionalStoreToAddress()
2552 // confidence that by optimizing we'll allow P and/or Q to be if-converted. in mergeConditionalStoreToAddress()
2556 // Heuristic: if the block can be if-converted/phi-folded and the in mergeConditionalStoreToAddress()
2591 if (!QStore->isUnordered() || !PStore->isUnordered()) in mergeConditionalStoreToAddress()
2605 for (auto &I : *QFB->getSinglePredecessor()) in mergeConditionalStoreToAddress()
2615 for (auto I = BasicBlock::iterator(PStore), E = PStore->getParent()->end(); in mergeConditionalStoreToAddress()
2617 if (&*I != PStore && I->mayReadOrWriteMemory()) in mergeConditionalStoreToAddress()
2622 Value *PCond = cast<BranchInst>(PFB->getSinglePredecessor()->getTerminator()) in mergeConditionalStoreToAddress()
2623 ->getCondition(); in mergeConditionalStoreToAddress()
2624 Value *QCond = cast<BranchInst>(QFB->getSinglePredecessor()->getTerminator()) in mergeConditionalStoreToAddress()
2625 ->getCondition(); in mergeConditionalStoreToAddress()
2627 Value *PPHI = ensureValueAvailableInSuccessor(PStore->getValueOperand(), in mergeConditionalStoreToAddress()
2628 PStore->getParent()); in mergeConditionalStoreToAddress()
2629 Value *QPHI = ensureValueAvailableInSuccessor(QStore->getValueOperand(), in mergeConditionalStoreToAddress()
2630 QStore->getParent(), PPHI); in mergeConditionalStoreToAddress()
2632 IRBuilder<> QB(&*PostBB->getFirstInsertionPt()); in mergeConditionalStoreToAddress()
2634 Value *PPred = PStore->getParent() == PTB ? PCond : QB.CreateNot(PCond); in mergeConditionalStoreToAddress()
2635 Value *QPred = QStore->getParent() == QTB ? QCond : QB.CreateNot(QCond); in mergeConditionalStoreToAddress()
2648 PStore->getAAMetadata(AAMD, /*Merge=*/false); in mergeConditionalStoreToAddress()
2649 PStore->getAAMetadata(AAMD, /*Merge=*/true); in mergeConditionalStoreToAddress()
2650 SI->setAAMetadata(AAMD); in mergeConditionalStoreToAddress()
2652 QStore->eraseFromParent(); in mergeConditionalStoreToAddress()
2653 PStore->eraseFromParent(); in mergeConditionalStoreToAddress()
2667 // true, and can allow the blocks to become small enough to be if-converted. in mergeConditionalStores()
2668 // This optimization will also chain, so that ladders of test-and-set in mergeConditionalStores()
2669 // sequences can be if-converted away. in mergeConditionalStores()
2687 BasicBlock *PTB = PBI->getSuccessor(0); in mergeConditionalStores()
2688 BasicBlock *PFB = PBI->getSuccessor(1); in mergeConditionalStores()
2689 BasicBlock *QTB = QBI->getSuccessor(0); in mergeConditionalStores()
2690 BasicBlock *QFB = QBI->getSuccessor(1); in mergeConditionalStores()
2691 BasicBlock *PostBB = QFB->getSingleSuccessor(); in mergeConditionalStores()
2695 if (PFB == QBI->getParent()) { in mergeConditionalStores()
2706 if (PTB == QBI->getParent()) in mergeConditionalStores()
2711 // Legality bailouts. We must have at least the non-fallthrough blocks and in mergeConditionalStores()
2712 // the post-dominating block, and the non-fallthroughs must only have one in mergeConditionalStores()
2715 return BB->getSinglePredecessor() == P && BB->getSingleSuccessor() == S; in mergeConditionalStores()
2718 !HasOnePredAndOneSucc(PFB, PBI->getParent(), QBI->getParent()) || in mergeConditionalStores()
2719 !HasOnePredAndOneSucc(QFB, QBI->getParent(), PostBB)) in mergeConditionalStores()
2721 if ((PTB && !HasOnePredAndOneSucc(PTB, PBI->getParent(), QBI->getParent())) || in mergeConditionalStores()
2722 (QTB && !HasOnePredAndOneSucc(QTB, QBI->getParent(), PostBB))) in mergeConditionalStores()
2724 if (PostBB->getNumUses() != 2 || QBI->getParent()->getNumUses() != 2) in mergeConditionalStores()
2735 PStoreAddresses.insert(SI->getPointerOperand()); in mergeConditionalStores()
2742 QStoreAddresses.insert(SI->getPointerOperand()); in mergeConditionalStores()
2760 /// successor blocks of PBI - PBI branches to BI.
2763 assert(PBI->isConditional() && BI->isConditional()); in SimplifyCondBranchToCondBranch()
2764 BasicBlock *BB = BI->getParent(); in SimplifyCondBranchToCondBranch()
2769 if (PBI->getCondition() == BI->getCondition() && in SimplifyCondBranchToCondBranch()
2770 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { in SimplifyCondBranchToCondBranch()
2773 if (BB->getSinglePredecessor()) { in SimplifyCondBranchToCondBranch()
2775 bool CondIsTrue = PBI->getSuccessor(0) == BB; in SimplifyCondBranchToCondBranch()
2776 BI->setCondition( in SimplifyCondBranchToCondBranch()
2777 ConstantInt::get(Type::getInt1Ty(BB->getContext()), CondIsTrue)); in SimplifyCondBranchToCondBranch()
2787 Type::getInt1Ty(BB->getContext()), std::distance(PB, PE), in SimplifyCondBranchToCondBranch()
2788 BI->getCondition()->getName() + ".pr", &BB->front()); in SimplifyCondBranchToCondBranch()
2794 if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) && PBI != BI && in SimplifyCondBranchToCondBranch()
2795 PBI->isConditional() && PBI->getCondition() == BI->getCondition() && in SimplifyCondBranchToCondBranch()
2796 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { in SimplifyCondBranchToCondBranch()
2797 bool CondIsTrue = PBI->getSuccessor(0) == BB; in SimplifyCondBranchToCondBranch()
2798 NewPN->addIncoming( in SimplifyCondBranchToCondBranch()
2799 ConstantInt::get(Type::getInt1Ty(BB->getContext()), CondIsTrue), in SimplifyCondBranchToCondBranch()
2802 NewPN->addIncoming(BI->getCondition(), P); in SimplifyCondBranchToCondBranch()
2806 BI->setCondition(NewPN); in SimplifyCondBranchToCondBranch()
2811 if (auto *CE = dyn_cast<ConstantExpr>(BI->getCondition())) in SimplifyCondBranchToCondBranch()
2812 if (CE->canTrap()) in SimplifyCondBranchToCondBranch()
2824 BasicBlock::iterator BBI = BB->begin(); in SimplifyCondBranchToCondBranch()
2832 if (PBI->getSuccessor(0) == BI->getSuccessor(0)) { in SimplifyCondBranchToCondBranch()
2835 } else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) { in SimplifyCondBranchToCondBranch()
2838 } else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) { in SimplifyCondBranchToCondBranch()
2841 } else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) { in SimplifyCondBranchToCondBranch()
2851 if (PBI->getSuccessor(PBIOp) == BB) in SimplifyCondBranchToCondBranch()
2862 BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); in SimplifyCondBranchToCondBranch()
2864 for (BasicBlock::iterator II = CommonDest->begin(); isa<PHINode>(II); in SimplifyCondBranchToCondBranch()
2870 Value *BIV = PN->getIncomingValueForBlock(BB); in SimplifyCondBranchToCondBranch()
2872 if (CE->canTrap()) in SimplifyCondBranchToCondBranch()
2875 unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); in SimplifyCondBranchToCondBranch()
2876 Value *PBIV = PN->getIncomingValue(PBBIdx); in SimplifyCondBranchToCondBranch()
2878 if (CE->canTrap()) in SimplifyCondBranchToCondBranch()
2883 BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); in SimplifyCondBranchToCondBranch()
2885 DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent() in SimplifyCondBranchToCondBranch()
2886 << "AND: " << *BI->getParent()); in SimplifyCondBranchToCondBranch()
2899 BasicBlock::Create(BB->getContext(), "infloop", BB->getParent()); in SimplifyCondBranchToCondBranch()
2904 DEBUG(dbgs() << *PBI->getParent()->getParent()); in SimplifyCondBranchToCondBranch()
2910 Value *PBICond = PBI->getCondition(); in SimplifyCondBranchToCondBranch()
2913 PBICond = Builder.CreateNot(PBICond, PBICond->getName() + ".not"); in SimplifyCondBranchToCondBranch()
2915 Value *BICond = BI->getCondition(); in SimplifyCondBranchToCondBranch()
2917 BICond = Builder.CreateNot(BICond, BICond->getName() + ".not"); in SimplifyCondBranchToCondBranch()
2923 PBI->setCondition(Cond); in SimplifyCondBranchToCondBranch()
2924 PBI->setSuccessor(0, CommonDest); in SimplifyCondBranchToCondBranch()
2925 PBI->setSuccessor(1, OtherDest); in SimplifyCondBranchToCondBranch()
2947 PBI->setMetadata(LLVMContext::MD_prof, in SimplifyCondBranchToCondBranch()
2948 MDBuilder(BI->getContext()) in SimplifyCondBranchToCondBranch()
2954 AddPredecessorToBlock(OtherDest, PBI->getParent(), BB); in SimplifyCondBranchToCondBranch()
2961 for (BasicBlock::iterator II = CommonDest->begin(); in SimplifyCondBranchToCondBranch()
2963 Value *BIV = PN->getIncomingValueForBlock(BB); in SimplifyCondBranchToCondBranch()
2964 unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); in SimplifyCondBranchToCondBranch()
2965 Value *PBIV = PN->getIncomingValue(PBBIdx); in SimplifyCondBranchToCondBranch()
2969 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName() + ".mux")); in SimplifyCondBranchToCondBranch()
2970 PN->setIncomingValue(PBBIdx, NV); in SimplifyCondBranchToCondBranch()
2987 NV->setMetadata(LLVMContext::MD_prof, in SimplifyCondBranchToCondBranch()
2988 MDBuilder(BI->getContext()) in SimplifyCondBranchToCondBranch()
2994 DEBUG(dbgs() << "INTO: " << *PBI->getParent()); in SimplifyCondBranchToCondBranch()
2995 DEBUG(dbgs() << *PBI->getParent()->getParent()); in SimplifyCondBranchToCondBranch()
3006 // non-successor TrueBBs and FalseBBs aren't reachable.
3019 for (BasicBlock *Succ : OldTerm->successors()) { in SimplifyTerminatorOnSelect()
3026 Succ->removePredecessor(OldTerm->getParent(), in SimplifyTerminatorOnSelect()
3031 Builder.SetCurrentDebugLocation(OldTerm->getDebugLoc()); in SimplifyTerminatorOnSelect()
3044 NewBI->setMetadata(LLVMContext::MD_prof, in SimplifyTerminatorOnSelect()
3045 MDBuilder(OldTerm->getContext()) in SimplifyTerminatorOnSelect()
3051 new UnreachableInst(OldTerm->getContext(), OldTerm); in SimplifyTerminatorOnSelect()
3070 // with a branch - conditional if X and Y lead to distinct BBs,
3074 ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue()); in SimplifySwitchOnSelect()
3075 ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue()); in SimplifySwitchOnSelect()
3080 Value *Condition = Select->getCondition(); in SimplifySwitchOnSelect()
3081 BasicBlock *TrueBB = SI->findCaseValue(TrueVal).getCaseSuccessor(); in SimplifySwitchOnSelect()
3082 BasicBlock *FalseBB = SI->findCaseValue(FalseVal).getCaseSuccessor(); in SimplifySwitchOnSelect()
3090 if (Weights.size() == 1 + SI->getNumCases()) { in SimplifySwitchOnSelect()
3092 (uint32_t)Weights[SI->findCaseValue(TrueVal).getSuccessorIndex()]; in SimplifySwitchOnSelect()
3094 (uint32_t)Weights[SI->findCaseValue(FalseVal).getSuccessorIndex()]; in SimplifySwitchOnSelect()
3110 BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue()); in SimplifyIndirectBrOnSelect()
3111 BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue()); in SimplifyIndirectBrOnSelect()
3116 BasicBlock *TrueBB = TBA->getBasicBlock(); in SimplifyIndirectBrOnSelect()
3117 BasicBlock *FalseBB = FBA->getBasicBlock(); in SimplifyIndirectBrOnSelect()
3120 return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB, 0, in SimplifyIndirectBrOnSelect()
3145 BasicBlock *BB = ICI->getParent(); in TryToSimplifyUncondBranchWithICmpInIt()
3149 if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) in TryToSimplifyUncondBranchWithICmpInIt()
3152 Value *V = ICI->getOperand(0); in TryToSimplifyUncondBranchWithICmpInIt()
3153 ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1)); in TryToSimplifyUncondBranchWithICmpInIt()
3158 BasicBlock *Pred = BB->getSinglePredecessor(); in TryToSimplifyUncondBranchWithICmpInIt()
3159 if (!Pred || !isa<SwitchInst>(Pred->getTerminator())) in TryToSimplifyUncondBranchWithICmpInIt()
3162 SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator()); in TryToSimplifyUncondBranchWithICmpInIt()
3163 if (SI->getCondition() != V) in TryToSimplifyUncondBranchWithICmpInIt()
3166 // If BB is reachable on a non-default case, then we simply know the value of in TryToSimplifyUncondBranchWithICmpInIt()
3169 if (SI->getDefaultDest() != BB) { in TryToSimplifyUncondBranchWithICmpInIt()
3170 ConstantInt *VVal = SI->findCaseDest(BB); in TryToSimplifyUncondBranchWithICmpInIt()
3172 ICI->setOperand(0, VVal); in TryToSimplifyUncondBranchWithICmpInIt()
3175 ICI->replaceAllUsesWith(V); in TryToSimplifyUncondBranchWithICmpInIt()
3176 ICI->eraseFromParent(); in TryToSimplifyUncondBranchWithICmpInIt()
3185 if (SI->findCaseValue(Cst) != SI->case_default()) { in TryToSimplifyUncondBranchWithICmpInIt()
3187 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) in TryToSimplifyUncondBranchWithICmpInIt()
3188 V = ConstantInt::getFalse(BB->getContext()); in TryToSimplifyUncondBranchWithICmpInIt()
3190 V = ConstantInt::getTrue(BB->getContext()); in TryToSimplifyUncondBranchWithICmpInIt()
3192 ICI->replaceAllUsesWith(V); in TryToSimplifyUncondBranchWithICmpInIt()
3193 ICI->eraseFromParent(); in TryToSimplifyUncondBranchWithICmpInIt()
3200 BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0); in TryToSimplifyUncondBranchWithICmpInIt()
3201 PHINode *PHIUse = dyn_cast<PHINode>(ICI->user_back()); in TryToSimplifyUncondBranchWithICmpInIt()
3202 if (PHIUse == nullptr || PHIUse != &SuccBlock->front() || in TryToSimplifyUncondBranchWithICmpInIt()
3208 Constant *DefaultCst = ConstantInt::getTrue(BB->getContext()); in TryToSimplifyUncondBranchWithICmpInIt()
3209 Constant *NewCst = ConstantInt::getFalse(BB->getContext()); in TryToSimplifyUncondBranchWithICmpInIt()
3211 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) in TryToSimplifyUncondBranchWithICmpInIt()
3216 ICI->replaceAllUsesWith(DefaultCst); in TryToSimplifyUncondBranchWithICmpInIt()
3217 ICI->eraseFromParent(); in TryToSimplifyUncondBranchWithICmpInIt()
3222 BasicBlock::Create(BB->getContext(), "switch.edge", BB->getParent(), BB); in TryToSimplifyUncondBranchWithICmpInIt()
3227 if (Weights.size() == 1 + SI->getNumCases()) { in TryToSimplifyUncondBranchWithICmpInIt()
3233 SI->setMetadata( in TryToSimplifyUncondBranchWithICmpInIt()
3235 MDBuilder(SI->getContext()).createBranchWeights(MDWeights)); in TryToSimplifyUncondBranchWithICmpInIt()
3238 SI->addCase(Cst, NewBB); in TryToSimplifyUncondBranchWithICmpInIt()
3242 Builder.SetCurrentDebugLocation(SI->getDebugLoc()); in TryToSimplifyUncondBranchWithICmpInIt()
3244 PHIUse->addIncoming(NewCst, NewBB); in TryToSimplifyUncondBranchWithICmpInIt()
3253 Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); in SimplifyBranchOnICmpChain()
3277 bool TrueWhenEqual = (Cond->getOpcode() == Instruction::Or); in SimplifyBranchOnICmpChain()
3293 BasicBlock *DefaultBB = BI->getSuccessor(1); in SimplifyBranchOnICmpChain()
3294 BasicBlock *EdgeBB = BI->getSuccessor(0); in SimplifyBranchOnICmpChain()
3298 BasicBlock *BB = BI->getParent(); in SimplifyBranchOnICmpChain()
3309 BB->splitBasicBlock(BI->getIterator(), "switch.early.test"); in SimplifyBranchOnICmpChain()
3311 TerminatorInst *OldTI = BB->getTerminator(); in SimplifyBranchOnICmpChain()
3319 OldTI->eraseFromParent(); in SimplifyBranchOnICmpChain()
3332 if (CompVal->getType()->isPointerTy()) { in SimplifyBranchOnICmpChain()
3334 CompVal, DL.getIntPtrType(CompVal->getType()), "magicptr"); in SimplifyBranchOnICmpChain()
3342 New->addCase(Values[i], EdgeBB); in SimplifyBranchOnICmpChain()
3347 for (BasicBlock::iterator BBI = EdgeBB->begin(); isa<PHINode>(BBI); ++BBI) { in SimplifyBranchOnICmpChain()
3349 Value *InVal = PN->getIncomingValueForBlock(BB); in SimplifyBranchOnICmpChain()
3350 for (unsigned i = 0, e = Values.size() - 1; i != e; ++i) in SimplifyBranchOnICmpChain()
3351 PN->addIncoming(InVal, BB); in SimplifyBranchOnICmpChain()
3362 if (isa<PHINode>(RI->getValue())) in SimplifyResume()
3364 else if (isa<LandingPadInst>(RI->getParent()->getFirstNonPHI()) && in SimplifyResume()
3365 RI->getValue() == RI->getParent()->getFirstNonPHI()) in SimplifyResume()
3374 BasicBlock *BB = RI->getParent(); in SimplifyCommonResume()
3377 // between the phi of landing pads (RI->getValue()) and resume instruction. in SimplifyCommonResume()
3378 BasicBlock::iterator I = cast<Instruction>(RI->getValue())->getIterator(), in SimplifyCommonResume()
3379 E = RI->getIterator(); in SimplifyCommonResume()
3385 auto *PhiLPInst = cast<PHINode>(RI->getValue()); in SimplifyCommonResume()
3388 for (unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End; in SimplifyCommonResume()
3390 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx); in SimplifyCommonResume()
3391 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx); in SimplifyCommonResume()
3395 if (IncomingBB->getUniqueSuccessor() != BB) in SimplifyCommonResume()
3398 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI()); in SimplifyCommonResume()
3405 I = IncomingBB->getFirstNonPHI()->getIterator(); in SimplifyCommonResume()
3406 E = IncomingBB->getTerminator()->getIterator(); in SimplifyCommonResume()
3426 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1) in SimplifyCommonResume()
3427 BB->removePredecessor(TrivialBB, true); in SimplifyCommonResume()
3440 TrivialBB->getTerminator()->eraseFromParent(); in SimplifyCommonResume()
3441 new UnreachableInst(RI->getContext(), TrivialBB); in SimplifyCommonResume()
3446 BB->eraseFromParent(); in SimplifyCommonResume()
3451 // Simplify resume that is only used by a single (non-phi) landing pad.
3453 BasicBlock *BB = RI->getParent(); in SimplifySingleResume()
3454 LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()); in SimplifySingleResume()
3455 assert(RI->getValue() == LPInst && in SimplifySingleResume()
3459 BasicBlock::iterator I = LPInst->getIterator(), E = RI->getIterator(); in SimplifySingleResume()
3471 BB->eraseFromParent(); in SimplifySingleResume()
3473 LoopHeaders->erase(BB); in SimplifySingleResume()
3486 BasicBlock *BB = RI->getParent(); in removeEmptyCleanup()
3487 CleanupPadInst *CPInst = RI->getCleanupPad(); in removeEmptyCleanup()
3488 if (CPInst->getParent() != BB) in removeEmptyCleanup()
3494 if (!CPInst->hasOneUse()) in removeEmptyCleanup()
3498 BasicBlock::iterator I = CPInst->getIterator(), E = RI->getIterator(); in removeEmptyCleanup()
3504 Intrinsic::ID IntrinsicID = II->getIntrinsicID(); in removeEmptyCleanup()
3517 BasicBlock *UnwindDest = RI->getUnwindDest(); in removeEmptyCleanup()
3518 Instruction *DestEHPad = UnwindDest ? UnwindDest->getFirstNonPHI() : nullptr; in removeEmptyCleanup()
3528 for (BasicBlock::iterator I = UnwindDest->begin(), in removeEmptyCleanup()
3529 IE = DestEHPad->getIterator(); in removeEmptyCleanup()
3533 int Idx = DestPN->getBasicBlockIndex(BB); in removeEmptyCleanup()
3535 assert(Idx != -1); in removeEmptyCleanup()
3547 Value *SrcVal = DestPN->getIncomingValue(Idx); in removeEmptyCleanup()
3551 DestPN->removeIncomingValue(Idx, false); in removeEmptyCleanup()
3553 if (SrcPN && SrcPN->getParent() == BB) { in removeEmptyCleanup()
3557 for (unsigned SrcIdx = 0, SrcE = SrcPN->getNumIncomingValues(); in removeEmptyCleanup()
3559 DestPN->addIncoming(SrcPN->getIncomingValue(SrcIdx), in removeEmptyCleanup()
3560 SrcPN->getIncomingBlock(SrcIdx)); in removeEmptyCleanup()
3567 DestPN->addIncoming(SrcVal, pred); in removeEmptyCleanup()
3574 for (BasicBlock::iterator I = BB->begin(), in removeEmptyCleanup()
3575 IE = BB->getFirstNonPHI()->getIterator(); in removeEmptyCleanup()
3580 if (PN->use_empty()) in removeEmptyCleanup()
3591 PN->addIncoming(PN, pred); in removeEmptyCleanup()
3592 PN->moveBefore(InsertPt); in removeEmptyCleanup()
3602 TerminatorInst *TI = PredBB->getTerminator(); in removeEmptyCleanup()
3603 TI->replaceUsesOfWith(BB, UnwindDest); in removeEmptyCleanup()
3608 BB->eraseFromParent(); in removeEmptyCleanup()
3616 BasicBlock *UnwindDest = RI->getUnwindDest(); in mergeCleanupPad()
3622 if (UnwindDest->getSinglePredecessor() != RI->getParent()) in mergeCleanupPad()
3626 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->front()); in mergeCleanupPad()
3630 CleanupPadInst *PredecessorCleanupPad = RI->getCleanupPad(); in mergeCleanupPad()
3634 SuccessorCleanupPad->replaceAllUsesWith(PredecessorCleanupPad); in mergeCleanupPad()
3636 SuccessorCleanupPad->eraseFromParent(); in mergeCleanupPad()
3639 BranchInst::Create(UnwindDest, RI->getParent()); in mergeCleanupPad()
3640 RI->eraseFromParent(); in mergeCleanupPad()
3649 if (isa<UndefValue>(RI->getOperand(0))) in SimplifyCleanupReturn()
3662 BasicBlock *BB = RI->getParent(); in SimplifyReturn()
3663 if (!BB->getFirstNonPHIOrDbg()->isTerminator()) in SimplifyReturn()
3671 TerminatorInst *PTI = P->getTerminator(); in SimplifyReturn()
3673 if (BI->isUnconditional()) in SimplifyReturn()
3692 BB->eraseFromParent(); in SimplifyReturn()
3694 LoopHeaders->erase(BB); in SimplifyReturn()
3706 // Check to see if the non-BB successor is also a return block. in SimplifyReturn()
3707 if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) && in SimplifyReturn()
3708 isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) && in SimplifyReturn()
3716 BasicBlock *BB = UI->getParent(); in SimplifyUnreachable()
3722 while (UI->getIterator() != BB->begin()) { in SimplifyUnreachable()
3723 BasicBlock::iterator BBI = UI->getIterator(); in SimplifyUnreachable()
3724 --BBI; in SimplifyUnreachable()
3731 if (BBI->mayHaveSideEffects()) { in SimplifyUnreachable()
3733 if (SI->isVolatile()) in SimplifyUnreachable()
3736 if (LI->isVolatile()) in SimplifyUnreachable()
3739 if (RMWI->isVolatile()) in SimplifyUnreachable()
3742 if (CXI->isVolatile()) in SimplifyUnreachable()
3749 if (classifyEHPersonality(BB->getParent()->getPersonalityFn()) != in SimplifyUnreachable()
3763 if (!BBI->use_empty()) in SimplifyUnreachable()
3764 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); in SimplifyUnreachable()
3765 BBI->eraseFromParent(); in SimplifyUnreachable()
3771 if (&BB->front() != UI) in SimplifyUnreachable()
3776 TerminatorInst *TI = Preds[i]->getTerminator(); in SimplifyUnreachable()
3779 if (BI->isUnconditional()) { in SimplifyUnreachable()
3780 if (BI->getSuccessor(0) == BB) { in SimplifyUnreachable()
3781 new UnreachableInst(TI->getContext(), TI); in SimplifyUnreachable()
3782 TI->eraseFromParent(); in SimplifyUnreachable()
3786 if (BI->getSuccessor(0) == BB) { in SimplifyUnreachable()
3787 Builder.CreateBr(BI->getSuccessor(1)); in SimplifyUnreachable()
3789 } else if (BI->getSuccessor(1) == BB) { in SimplifyUnreachable()
3790 Builder.CreateBr(BI->getSuccessor(0)); in SimplifyUnreachable()
3796 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; in SimplifyUnreachable()
3799 BB->removePredecessor(SI->getParent()); in SimplifyUnreachable()
3800 SI->removeCase(i); in SimplifyUnreachable()
3801 --i; in SimplifyUnreachable()
3802 --e; in SimplifyUnreachable()
3806 if (II->getUnwindDest() == BB) { in SimplifyUnreachable()
3807 removeUnwindEdge(TI->getParent()); in SimplifyUnreachable()
3811 if (CSI->getUnwindDest() == BB) { in SimplifyUnreachable()
3812 removeUnwindEdge(TI->getParent()); in SimplifyUnreachable()
3817 for (CatchSwitchInst::handler_iterator I = CSI->handler_begin(), in SimplifyUnreachable()
3818 E = CSI->handler_end(); in SimplifyUnreachable()
3821 CSI->removeHandler(I); in SimplifyUnreachable()
3822 --I; in SimplifyUnreachable()
3823 --E; in SimplifyUnreachable()
3827 if (CSI->getNumHandlers() == 0) { in SimplifyUnreachable()
3828 BasicBlock *CatchSwitchBB = CSI->getParent(); in SimplifyUnreachable()
3829 if (CSI->hasUnwindDest()) { in SimplifyUnreachable()
3831 CatchSwitchBB->replaceAllUsesWith(CSI->getUnwindDest()); in SimplifyUnreachable()
3839 new UnreachableInst(CSI->getContext(), CSI); in SimplifyUnreachable()
3840 CSI->eraseFromParent(); in SimplifyUnreachable()
3844 new UnreachableInst(TI->getContext(), TI); in SimplifyUnreachable()
3845 TI->eraseFromParent(); in SimplifyUnreachable()
3851 if (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) { in SimplifyUnreachable()
3853 BB->eraseFromParent(); in SimplifyUnreachable()
3855 LoopHeaders->erase(BB); in SimplifyUnreachable()
3867 if (Cases[I - 1]->getValue() != Cases[I]->getValue() + 1) in CasesAreContiguous()
3876 assert(SI->getNumCases() > 1 && "Degenerate switch?"); in TurnSwitchRangeIntoICmp()
3879 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()); in TurnSwitchRangeIntoICmp()
3882 BasicBlock *DestA = HasDefault ? SI->getDefaultDest() : nullptr; in TurnSwitchRangeIntoICmp()
3887 for (SwitchInst::CaseIt I : SI->cases()) { in TurnSwitchRangeIntoICmp()
3905 "Single-destination switch should have been folded."); in TurnSwitchRangeIntoICmp()
3907 assert(DestB != SI->getDefaultDest()); in TurnSwitchRangeIntoICmp()
3908 assert(!CasesB.empty() && "There must be non-default cases."); in TurnSwitchRangeIntoICmp()
3928 Constant *Offset = ConstantExpr::getNeg(ContiguousCases->back()); in TurnSwitchRangeIntoICmp()
3930 ConstantInt::get(Offset->getType(), ContiguousCases->size()); in TurnSwitchRangeIntoICmp()
3932 Value *Sub = SI->getCondition(); in TurnSwitchRangeIntoICmp()
3933 if (!Offset->isNullValue()) in TurnSwitchRangeIntoICmp()
3934 Sub = Builder.CreateAdd(Sub, Offset, Sub->getName() + ".off"); in TurnSwitchRangeIntoICmp()
3938 if (NumCases->isNullValue() && !ContiguousCases->empty()) in TurnSwitchRangeIntoICmp()
3939 Cmp = ConstantInt::getTrue(SI->getContext()); in TurnSwitchRangeIntoICmp()
3944 // Update weight for the newly-created conditional branch. in TurnSwitchRangeIntoICmp()
3948 if (Weights.size() == 1 + SI->getNumCases()) { in TurnSwitchRangeIntoICmp()
3952 if (SI->getSuccessor(I) == ContiguousDest) in TurnSwitchRangeIntoICmp()
3961 NewBI->setMetadata(LLVMContext::MD_prof, in TurnSwitchRangeIntoICmp()
3962 MDBuilder(SI->getContext()) in TurnSwitchRangeIntoICmp()
3969 for (auto BBI = ContiguousDest->begin(); isa<PHINode>(BBI); ++BBI) { in TurnSwitchRangeIntoICmp()
3970 unsigned PreviousEdges = ContiguousCases->size(); in TurnSwitchRangeIntoICmp()
3971 if (ContiguousDest == SI->getDefaultDest()) in TurnSwitchRangeIntoICmp()
3973 for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I) in TurnSwitchRangeIntoICmp()
3974 cast<PHINode>(BBI)->removeIncomingValue(SI->getParent()); in TurnSwitchRangeIntoICmp()
3976 for (auto BBI = OtherDest->begin(); isa<PHINode>(BBI); ++BBI) { in TurnSwitchRangeIntoICmp()
3977 unsigned PreviousEdges = SI->getNumCases() - ContiguousCases->size(); in TurnSwitchRangeIntoICmp()
3978 if (OtherDest == SI->getDefaultDest()) in TurnSwitchRangeIntoICmp()
3980 for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I) in TurnSwitchRangeIntoICmp()
3981 cast<PHINode>(BBI)->removeIncomingValue(SI->getParent()); in TurnSwitchRangeIntoICmp()
3985 SI->eraseFromParent(); in TurnSwitchRangeIntoICmp()
3994 Value *Cond = SI->getCondition(); in EliminateDeadSwitchCases()
3995 unsigned Bits = Cond->getType()->getIntegerBitWidth(); in EliminateDeadSwitchCases()
4000 // the limited range of the condition based on how many significant (non-sign) in EliminateDeadSwitchCases()
4002 unsigned ExtraSignBits = ComputeNumSignBits(Cond, DL, 0, AC, SI) - 1; in EliminateDeadSwitchCases()
4003 unsigned MaxSignificantBitsInCond = Bits - ExtraSignBits; in EliminateDeadSwitchCases()
4007 for (auto &Case : SI->cases()) { in EliminateDeadSwitchCases()
4008 APInt CaseVal = Case.getCaseValue()->getValue(); in EliminateDeadSwitchCases()
4021 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()); in EliminateDeadSwitchCases()
4023 Bits - (KnownZero.Or(KnownOne)).countPopulation(); in EliminateDeadSwitchCases()
4027 SI->getNumCases() == (1ULL << NumUnknownBits)) { in EliminateDeadSwitchCases()
4030 SplitBlockPredecessors(SI->getDefaultDest(), SI->getParent(), ""); in EliminateDeadSwitchCases()
4031 SI->setDefaultDest(&*NewDefault); in EliminateDeadSwitchCases()
4032 SplitBlock(&*NewDefault, &NewDefault->front()); in EliminateDeadSwitchCases()
4033 auto *OldTI = NewDefault->getTerminator(); in EliminateDeadSwitchCases()
4034 new UnreachableInst(SI->getContext(), OldTI); in EliminateDeadSwitchCases()
4043 HasWeight = (Weights.size() == 1 + SI->getNumCases()); in EliminateDeadSwitchCases()
4048 SwitchInst::CaseIt Case = SI->findCaseValue(DeadCase); in EliminateDeadSwitchCases()
4049 assert(Case != SI->case_default() && in EliminateDeadSwitchCases()
4057 Case.getCaseSuccessor()->removePredecessor(SI->getParent()); in EliminateDeadSwitchCases()
4058 SI->removeCase(Case); in EliminateDeadSwitchCases()
4062 SI->setMetadata(LLVMContext::MD_prof, in EliminateDeadSwitchCases()
4063 MDBuilder(SI->getParent()->getContext()) in EliminateDeadSwitchCases()
4077 if (BB->getFirstNonPHIOrDbg() != BB->getTerminator()) in FindPHIForConditionForwarding()
4079 if (!BB->getSinglePredecessor()) in FindPHIForConditionForwarding()
4082 BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator()); in FindPHIForConditionForwarding()
4083 if (!Branch || !Branch->isUnconditional()) in FindPHIForConditionForwarding()
4086 BasicBlock *Succ = Branch->getSuccessor(0); in FindPHIForConditionForwarding()
4088 BasicBlock::iterator I = Succ->begin(); in FindPHIForConditionForwarding()
4090 int Idx = PHI->getBasicBlockIndex(BB); in FindPHIForConditionForwarding()
4093 Value *InValue = PHI->getIncomingValue(Idx); in FindPHIForConditionForwarding()
4112 for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; in ForwardSwitchConditionToPHI()
4131 PHINode *Phi = I->first; in ForwardSwitchConditionToPHI()
4132 SmallVectorImpl<int> &Indexes = I->second; in ForwardSwitchConditionToPHI()
4138 Phi->setIncomingValue(Indexes[I], SI->getCondition()); in ForwardSwitchConditionToPHI()
4148 if (C->isThreadDependent()) in ValidLookupTableConstant()
4150 if (C->isDLLImportDependent()) in ValidLookupTableConstant()
4154 return CE->isGEPWithNoNotionalOverIndexing(); in ValidLookupTableConstant()
4179 Constant *A = LookupConstant(Select->getCondition(), ConstantPool); in ConstantFold()
4182 if (A->isAllOnesValue()) in ConstantFold()
4183 return LookupConstant(Select->getTrueValue(), ConstantPool); in ConstantFold()
4184 if (A->isNullValue()) in ConstantFold()
4185 return LookupConstant(Select->getFalseValue(), ConstantPool); in ConstantFold()
4190 for (unsigned N = 0, E = I->getNumOperands(); N != E; ++N) { in ConstantFold()
4191 if (Constant *A = LookupConstant(I->getOperand(N), ConstantPool)) in ConstantFold()
4198 return ConstantFoldCompareInstOperands(Cmp->getPredicate(), COps[0], in ConstantFold()
4215 BasicBlock *Pred = SI->getParent(); in GetCaseResults()
4217 // If CaseDest is empty except for some side-effect free instructions through in GetCaseResults()
4218 // which we can constant-propagate the CaseVal, continue to its successor. in GetCaseResults()
4220 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal)); in GetCaseResults()
4221 for (BasicBlock::iterator I = CaseDest->begin(), E = CaseDest->end(); I != E; in GetCaseResults()
4225 if (T->getNumSuccessors() != 1) in GetCaseResults()
4228 CaseDest = T->getSuccessor(0); in GetCaseResults()
4233 // Instruction is side-effect free and constant. in GetCaseResults()
4238 for (auto &Use : I->uses()) { in GetCaseResults()
4241 if (I->getParent() == CaseDest) in GetCaseResults()
4244 if (Phi->getIncomingBlock(Use) == CaseDest) in GetCaseResults()
4263 BasicBlock::iterator I = (*CommonDest)->begin(); in GetCaseResults()
4265 int Idx = PHI->getBasicBlockIndex(Pred); in GetCaseResults()
4266 if (Idx == -1) in GetCaseResults()
4270 LookupConstant(PHI->getIncomingValue(Idx), ConstantPool); in GetCaseResults()
4308 for (auto &I : SI->cases()) { in InitializeUniqueCases()
4320 MapCaseToResult(CaseVal, UniqueResults, Results.begin()->second); in InitializeUniqueCases()
4330 BasicBlock *DefaultDest = SI->getDefaultDest(); in InitializeUniqueCases()
4331 GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults, in InitializeUniqueCases()
4336 DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr; in InitializeUniqueCases()
4338 !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()))) in InitializeUniqueCases()
4350 // case 20: ----> %2 = icmp eq i32 %a, 20
4361 // select or a two-way select if default is possible. in ConvertTwoCaseSwitch()
4389 BasicBlock *SelectBB = SI->getParent(); in RemoveSwitchAfterSelectConversion()
4390 while (PHI->getBasicBlockIndex(SelectBB) >= 0) in RemoveSwitchAfterSelectConversion()
4391 PHI->removeIncomingValue(SelectBB); in RemoveSwitchAfterSelectConversion()
4392 PHI->addIncoming(SelectValue, SelectBB); in RemoveSwitchAfterSelectConversion()
4394 Builder.CreateBr(PHI->getParent()); in RemoveSwitchAfterSelectConversion()
4397 for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) { in RemoveSwitchAfterSelectConversion()
4398 BasicBlock *Succ = SI->getSuccessor(i); in RemoveSwitchAfterSelectConversion()
4400 if (Succ == PHI->getParent()) in RemoveSwitchAfterSelectConversion()
4402 Succ->removePredecessor(SelectBB); in RemoveSwitchAfterSelectConversion()
4404 SI->eraseFromParent(); in RemoveSwitchAfterSelectConversion()
4412 Value *const Cond = SI->getCondition(); in SwitchToSelect()
4453 /// type ElementType would fit in a target-legal register.
4471 // that fits into a target-legal register. Values are retrieved by
4506 SingleValue = Values.begin()->second; in SwitchLookupTable()
4508 Type *ValueType = Values.begin()->second->getType(); in SwitchLookupTable()
4515 assert(CaseRes->getType() == ValueType); in SwitchLookupTable()
4517 uint64_t Idx = (CaseVal->getValue() - Offset->getValue()).getLimitedValue(); in SwitchLookupTable()
4528 assert(DefaultValue->getType() == ValueType); in SwitchLookupTable()
4561 APInt Val = ConstVal->getValue(); in SwitchLookupTable()
4563 APInt Dist = Val - PrevVal; in SwitchLookupTable()
4585 APInt TableInt(TableSize * IT->getBitWidth(), 0); in SwitchLookupTable()
4586 for (uint64_t I = TableSize; I > 0; --I) { in SwitchLookupTable()
4587 TableInt <<= IT->getBitWidth(); in SwitchLookupTable()
4589 if (!isa<UndefValue>(TableContents[I - 1])) { in SwitchLookupTable()
4590 ConstantInt *Val = cast<ConstantInt>(TableContents[I - 1]); in SwitchLookupTable()
4591 TableInt |= Val->getValue().zext(TableInt.getBitWidth()); in SwitchLookupTable()
4608 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); in SwitchLookupTable()
4618 Value *Result = Builder.CreateIntCast(Index, LinearMultiplier->getType(), in BuildLookup()
4620 if (!LinearMultiplier->isOne()) in BuildLookup()
4622 if (!LinearOffset->isZero()) in BuildLookup()
4628 IntegerType *MapTy = BitMap->getType(); in BuildLookup()
4637 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()), in BuildLookup()
4648 IntegerType *IT = cast<IntegerType>(Index->getType()); in BuildLookup()
4650 Array->getInitializer()->getType()->getArrayNumElements(); in BuildLookup()
4651 if (TableSize > (1ULL << (IT->getBitWidth() - 1))) in BuildLookup()
4653 Index, IntegerType::get(IT->getContext(), IT->getBitWidth() + 1), in BuildLookup()
4657 Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array, in BuildLookup()
4675 if (TableSize >= UINT_MAX / IT->getBitWidth()) in WouldFitInRegister()
4677 return DL.fitsInLegalInteger(TableSize * IT->getBitWidth()); in WouldFitInRegister()
4686 if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10) in ShouldBuildLookupTable()
4704 // non-deterministic behavior of iterating over a dense map. in ShouldBuildLookupTable()
4713 // Don't build a table that doesn't fit in-register if it has illegal types. in ShouldBuildLookupTable()
4719 // FIXME: Find the best cut-off. in ShouldBuildLookupTable()
4720 return SI->getNumCases() * 10 >= TableSize * 4; in ShouldBuildLookupTable()
4754 if (CmpInst->getParent() != PhiBlock) in reuseTableCompare()
4757 Constant *CmpOp1 = dyn_cast<Constant>(CmpInst->getOperand(1)); in reuseTableCompare()
4761 Value *RangeCmp = RangeCheckBranch->getCondition(); in reuseTableCompare()
4762 Constant *TrueConst = ConstantInt::getTrue(RangeCmp->getType()); in reuseTableCompare()
4763 Constant *FalseConst = ConstantInt::getFalse(RangeCmp->getType()); in reuseTableCompare()
4766 Constant *DefaultConst = ConstantExpr::getICmp(CmpInst->getPredicate(), in reuseTableCompare()
4774 Constant *CaseConst = ConstantExpr::getICmp(CmpInst->getPredicate(), in reuseTableCompare()
4786 BasicBlock *BranchBlock = RangeCheckBranch->getParent(); in reuseTableCompare()
4789 if (Pred != BranchBlock && Pred->getUniquePredecessor() != BranchBlock) in reuseTableCompare()
4795 CmpInst->replaceAllUsesWith(RangeCmp); in reuseTableCompare()
4800 RangeCmp, ConstantInt::get(RangeCmp->getType(), 1), "inverted.cmp", in reuseTableCompare()
4802 CmpInst->replaceAllUsesWith(InvertedTableCmp); in reuseTableCompare()
4813 assert(SI->getNumCases() > 1 && "Degenerate switch?"); in SwitchToLookupTable()
4829 if (SI->getNumCases() < 3) in SwitchToLookupTable()
4834 assert(SI->case_begin() != SI->case_end()); in SwitchToLookupTable()
4835 SwitchInst::CaseIt CI = SI->case_begin(); in SwitchToLookupTable()
4846 for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) { in SwitchToLookupTable()
4848 if (CaseVal->getValue().slt(MinCaseVal->getValue())) in SwitchToLookupTable()
4850 if (CaseVal->getValue().sgt(MaxCaseVal->getValue())) in SwitchToLookupTable()
4872 ResultTypes[PHI] = ResultLists[PHI][0].second->getType(); in SwitchToLookupTable()
4876 APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue(); in SwitchToLookupTable()
4883 bool HasDefaultResults = GetCaseResults(SI, nullptr, SI->getDefaultDest(), in SwitchToLookupTable()
4889 if (SI->getNumCases() < 4) // FIXME: Find best threshold value (benchmark). in SwitchToLookupTable()
4905 Module &Mod = *CommonDest->getParent()->getParent(); in SwitchToLookupTable()
4907 Mod.getContext(), "switch.lookup", CommonDest->getParent(), CommonDest); in SwitchToLookupTable()
4912 Builder.CreateSub(SI->getCondition(), MinCaseVal, "switch.tableidx"); in SwitchToLookupTable()
4916 unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits(); in SwitchToLookupTable()
4926 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()); in SwitchToLookupTable()
4936 TableIndex, ConstantInt::get(MinCaseVal->getType(), TableSize)); in SwitchToLookupTable()
4938 Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest()); in SwitchToLookupTable()
4946 // The LookupBB is therefore re-purposed to do the hole check in SwitchToLookupTable()
4949 MaskBB->setName("switch.hole_check"); in SwitchToLookupTable()
4951 CommonDest->getParent(), CommonDest); in SwitchToLookupTable()
4953 // Make the mask's bitwidth at least 8bit and a power-of-2 to avoid in SwitchToLookupTable()
4955 uint64_t TableSizePowOf2 = NextPowerOf2(std::max(7ULL, TableSize - 1ULL)); in SwitchToLookupTable()
4961 uint64_t Idx = (ResultList[I].first->getValue() - MinCaseVal->getValue()) in SwitchToLookupTable()
4970 IntegerType *MapTy = TableMask->getType(); in SwitchToLookupTable()
4976 Builder.CreateCondBr(LoBit, LookupBB, SI->getDefaultDest()); in SwitchToLookupTable()
4979 AddPredecessorToBlock(SI->getDefaultDest(), MaskBB, SI->getParent()); in SwitchToLookupTable()
4985 SI->getDefaultDest()->removePredecessor(SI->getParent(), in SwitchToLookupTable()
5002 if (PHI->hasOneUse() && isa<ReturnInst>(*PHI->user_begin()) && in SwitchToLookupTable()
5003 PHI->user_back() == CommonDest->getFirstNonPHIOrDbg()) { in SwitchToLookupTable()
5009 // Do a small peephole optimization: re-use the switch table compare if in SwitchToLookupTable()
5012 BasicBlock *PhiBlock = PHI->getParent(); in SwitchToLookupTable()
5014 for (auto *User : PHI->users()) { in SwitchToLookupTable()
5019 PHI->addIncoming(Result, LookupBB); in SwitchToLookupTable()
5026 for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) { in SwitchToLookupTable()
5027 BasicBlock *Succ = SI->getSuccessor(i); in SwitchToLookupTable()
5029 if (Succ == SI->getDefaultDest()) in SwitchToLookupTable()
5031 Succ->removePredecessor(SI->getParent()); in SwitchToLookupTable()
5033 SI->eraseFromParent(); in SwitchToLookupTable()
5042 BasicBlock *BB = SI->getParent(); in SimplifySwitch()
5047 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) in SimplifySwitch()
5051 Value *Cond = SI->getCondition(); in SimplifySwitch()
5058 BasicBlock::iterator BBI = BB->begin(); in SimplifySwitch()
5088 BasicBlock *BB = IBI->getParent(); in SimplifyIndirectBr()
5093 for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { in SimplifyIndirectBr()
5094 BasicBlock *Dest = IBI->getDestination(i); in SimplifyIndirectBr()
5095 if (!Dest->hasAddressTaken() || !Succs.insert(Dest).second) { in SimplifyIndirectBr()
5096 Dest->removePredecessor(BB); in SimplifyIndirectBr()
5097 IBI->removeDestination(i); in SimplifyIndirectBr()
5098 --i; in SimplifyIndirectBr()
5099 --e; in SimplifyIndirectBr()
5104 if (IBI->getNumDestinations() == 0) { in SimplifyIndirectBr()
5106 new UnreachableInst(IBI->getContext(), IBI); in SimplifyIndirectBr()
5111 if (IBI->getNumDestinations() == 1) { in SimplifyIndirectBr()
5113 BranchInst::Create(IBI->getDestination(0), IBI); in SimplifyIndirectBr()
5118 if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) { in SimplifyIndirectBr()
5130 /// We specifically choose to not worry about merging non-empty blocks
5133 /// when dealing with exception dense code. (see: instcombine, gvn, if-else
5143 /// TODO - This transformation could remove entries from a phi in the target
5148 auto Succ = BB->getUniqueSuccessor(); in TryToMergeLandingPad()
5152 if (isa<PHINode>(*Succ->begin())) in TryToMergeLandingPad()
5158 BasicBlock::iterator I = OtherPred->begin(); in TryToMergeLandingPad()
5160 if (!LPad2 || !LPad2->isIdenticalTo(LPad)) in TryToMergeLandingPad()
5165 if (!BI2 || !BI2->isIdenticalTo(BI)) in TryToMergeLandingPad()
5173 InvokeInst *II = cast<InvokeInst>(Pred->getTerminator()); in TryToMergeLandingPad()
5174 assert(II->getNormalDest() != BB && II->getUnwindDest() == BB && in TryToMergeLandingPad()
5176 II->setUnwindDest(OtherPred); in TryToMergeLandingPad()
5181 for (auto I = OtherPred->begin(), E = OtherPred->end(); I != E;) { in TryToMergeLandingPad()
5191 Succ->removePredecessor(BB); in TryToMergeLandingPad()
5196 BI->eraseFromParent(); in TryToMergeLandingPad()
5204 BasicBlock *BB = BI->getParent(); in SimplifyUncondBranch()
5209 // If the Terminator is the only non-phi instruction, simplify the block. in SimplifyUncondBranch()
5214 // in the back-end.) in SimplifyUncondBranch()
5215 BasicBlock::iterator I = BB->getFirstNonPHIOrDbg()->getIterator(); in SimplifyUncondBranch()
5216 if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && in SimplifyUncondBranch()
5217 (!LoopHeaders || !LoopHeaders->count(BB)) && in SimplifyUncondBranch()
5224 if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) { in SimplifyUncondBranch()
5227 if (I->isTerminator() && in SimplifyUncondBranch()
5238 if (I->isTerminator() && TryToMergeLandingPad(LPad, BI, BB)) in SimplifyUncondBranch()
5254 BasicBlock *PPred = P->getSinglePredecessor(); in allPredecessorsComeFromSameSource()
5263 BasicBlock *BB = BI->getParent(); in SimplifyCondBranch()
5270 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) in SimplifyCondBranch()
5276 BasicBlock::iterator I = BB->begin(); in SimplifyCondBranch()
5283 } else if (&*I == cast<Instruction>(BI->getCondition())) { in SimplifyCondBranch()
5300 if (BasicBlock *Dom = BB->getSinglePredecessor()) { in SimplifyCondBranch()
5301 auto *PBI = dyn_cast_or_null<BranchInst>(Dom->getTerminator()); in SimplifyCondBranch()
5302 if (PBI && PBI->isConditional() && in SimplifyCondBranch()
5303 PBI->getSuccessor(0) != PBI->getSuccessor(1) && in SimplifyCondBranch()
5304 (PBI->getSuccessor(0) == BB || PBI->getSuccessor(1) == BB)) { in SimplifyCondBranch()
5305 bool CondIsFalse = PBI->getSuccessor(1) == BB; in SimplifyCondBranch()
5307 PBI->getCondition(), BI->getCondition(), DL, CondIsFalse); in SimplifyCondBranch()
5310 auto *OldCond = BI->getCondition(); in SimplifyCondBranch()
5312 ? ConstantInt::getTrue(BB->getContext()) in SimplifyCondBranch()
5313 : ConstantInt::getFalse(BB->getContext()); in SimplifyCondBranch()
5314 BI->setCondition(CI); in SimplifyCondBranch()
5331 if (BI->getSuccessor(0)->getSinglePredecessor()) { in SimplifyCondBranch()
5332 if (BI->getSuccessor(1)->getSinglePredecessor()) { in SimplifyCondBranch()
5338 TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator(); in SimplifyCondBranch()
5339 if (Succ0TI->getNumSuccessors() == 1 && in SimplifyCondBranch()
5340 Succ0TI->getSuccessor(0) == BI->getSuccessor(1)) in SimplifyCondBranch()
5341 if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), TTI)) in SimplifyCondBranch()
5344 } else if (BI->getSuccessor(1)->getSinglePredecessor()) { in SimplifyCondBranch()
5347 TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator(); in SimplifyCondBranch()
5348 if (Succ1TI->getNumSuccessors() == 1 && in SimplifyCondBranch()
5349 Succ1TI->getSuccessor(0) == BI->getSuccessor(0)) in SimplifyCondBranch()
5350 if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), TTI)) in SimplifyCondBranch()
5356 if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) in SimplifyCondBranch()
5357 if (PN->getParent() == BI->getParent()) in SimplifyCondBranch()
5363 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) in SimplifyCondBranch()
5364 if (PBI != BI && PBI->isConditional()) in SimplifyCondBranch()
5371 if (BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator())) in SimplifyCondBranch()
5372 if (PBI != BI && PBI->isConditional()) in SimplifyCondBranch()
5385 if (I->use_empty()) in passingValueIsAlwaysUndefined()
5388 if (C->isNullValue() || isa<UndefValue>(C)) { in passingValueIsAlwaysUndefined()
5390 User *Use = *I->user_begin(); in passingValueIsAlwaysUndefined()
5395 if (i == I->getParent()->end() || i->mayHaveSideEffects()) in passingValueIsAlwaysUndefined()
5400 if (GEP->getPointerOperand() == I) in passingValueIsAlwaysUndefined()
5409 if (!LI->isVolatile()) in passingValueIsAlwaysUndefined()
5410 return LI->getPointerAddressSpace() == 0; in passingValueIsAlwaysUndefined()
5414 if (!SI->isVolatile()) in passingValueIsAlwaysUndefined()
5415 return SI->getPointerAddressSpace() == 0 && in passingValueIsAlwaysUndefined()
5416 SI->getPointerOperand() == I; in passingValueIsAlwaysUndefined()
5428 for (BasicBlock::iterator i = BB->begin(); in removeUndefIntroducingPredecessor()
5430 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) in removeUndefIntroducingPredecessor()
5431 if (passingValueIsAlwaysUndefined(PHI->getIncomingValue(i), PHI)) { in removeUndefIntroducingPredecessor()
5432 TerminatorInst *T = PHI->getIncomingBlock(i)->getTerminator(); in removeUndefIntroducingPredecessor()
5435 BB->removePredecessor(PHI->getIncomingBlock(i)); in removeUndefIntroducingPredecessor()
5438 if (BI->isUnconditional()) in removeUndefIntroducingPredecessor()
5441 Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) in removeUndefIntroducingPredecessor()
5442 : BI->getSuccessor(0)); in removeUndefIntroducingPredecessor()
5443 BI->eraseFromParent(); in removeUndefIntroducingPredecessor()
5455 assert(BB && BB->getParent() && "Block not embedded in function!"); in run()
5456 assert(BB->getTerminator() && "Degenerate basic block encountered!"); in run()
5460 if ((pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) || in run()
5461 BB->getSinglePredecessor() == BB) { in run()
5486 // If there is a trivial two-entry PHI node in this basic block, and we can in run()
5488 if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) in run()
5489 if (PN->getNumIncomingValues() == 2) in run()
5492 Builder.SetInsertPoint(BB->getTerminator()); in run()
5493 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { in run()
5494 if (BI->isUnconditional()) { in run()
5501 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { in run()
5504 } else if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) { in run()
5508 dyn_cast<CleanupReturnInst>(BB->getTerminator())) { in run()
5511 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { in run()
5515 dyn_cast<UnreachableInst>(BB->getTerminator())) { in run()
5519 dyn_cast<IndirectBrInst>(BB->getTerminator())) { in run()
5535 return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), in SimplifyCFG()