Lines Matching +full:push +full:- +full:ci +full:- +full:container
1 //===- NewGVN.cpp - Global Value Numbering Pass ---------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
14 /// compile-time approximation of equivalence of values at runtime.
27 /// operation -> value number). Thus, when a value number of an operation
31 /// reverse mapping from value number -> operations with that value number), so
39 /// In order to make the GVN mostly-complete, we use a technique derived from
40 /// "Detection of Redundant Expressions: A Complete and Polynomial-time
52 //===----------------------------------------------------------------------===//
143 DEBUG_COUNTER(VNCounter, "newgvn-vn",
145 DEBUG_COUNTER(PHIOfOpsCounter, "newgvn-phi",
150 static cl::opt<bool> EnableStoreRefinement("enable-store-refinement",
154 static cl::opt<bool> EnablePhiOfOps("enable-phi-of-ops", cl::init(true),
157 //===----------------------------------------------------------------------===//
159 //===----------------------------------------------------------------------===//
183 // This SCC finder is specialized to walk use-def chains, and only follows
207 for (const auto &Op : I->operands()) {
237 // Part of a component, push to stack
258 // you can willy-nilly replace any member with any other at any
372 --StoreCount;
387 std::tie(Other->StoreCount, Other->RepLeader, Other->RepStoredValue,
388 Other->RepMemoryAccess))
390 if (DefiningExpr != Other->DefiningExpr)
391 if (!DefiningExpr || !Other->DefiningExpr ||
392 *DefiningExpr != *Other->DefiningExpr)
395 if (Members.size() != Other->Members.size())
398 return llvm::set_is_subset(Members, Other->Members);
454 auto Val = static_cast<uintptr_t>(-1);
466 return E->getComputedHash();
489 if (LHS->getComputedHash() != RHS->getComputedHash())
511 // side-effects on due to allocating memory.
552 // Map between the already in-program instructions and the temporary phis we
556 // In order to know when we should re-process instructions that have
557 // phi-of-ops, we track the set of expressions that they needed as
559 // associated phi-of-op instructions again in case they have changed. The
594 // stores, we no longer can rely solely on the def-use chains of MemorySSA.
768 CC->setMemoryLeader(MA);
774 if (CC->getMemoryLeader() != MA)
781 CClass->insert(Member);
908 // auto-convert to Value's but not to MemoryAccess's.
913 ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst())
943 if (getStoredValue() != S->getStoredValue())
953 return Call->getAttributes()
954 .intersectWith(Call->getContext(), RHS->Call->getAttributes())
960 // Determine if the edge From->To is a backedge
963 RPOOrdering.lookup(DT->getNode(From)) >=
964 RPOOrdering.lookup(DT->getNode(To));
975 auto *Result = MSSA->getMemoryAccess(I);
981 return MSSA->getMemoryAccess(BB);
987 auto *Parent = I->getParent();
997 return MP->getBlock();
1006 const_cast<BasicExpression *>(BE)->deallocateOperands(ArgRecycler);
1013 if (II->getIntrinsicID() == Intrinsic::ssa_copy)
1014 return II->getOperand(0);
1058 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1059 E->setType(PHIOperands.begin()->first->getType());
1060 E->setOpcode(Instruction::PHI);
1078 [&](const ValPair &P) -> Value * {
1089 E->setType(GEP->getSourceElementType());
1091 E->setType(I->getType());
1092 E->setOpcode(I->getOpcode());
1093 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1097 std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) {
1114 E->setType(T);
1115 E->setOpcode(Opcode);
1116 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1125 E->op_push_back(lookupOperandLeader(Arg1));
1126 E->op_push_back(lookupOperandLeader(Arg2));
1128 Value *V = simplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), Q);
1163 if (CC->getLeader() && CC->getLeader() != I) {
1164 return ExprResult::some(createVariableOrConstant(CC->getLeader()), V);
1166 if (CC->getDefiningExpr()) {
1169 << " expression " << *CC->getDefiningExpr() << "\n");
1172 return ExprResult::some(CC->getDefiningExpr(), V);
1183 auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands());
1190 if (I->isCommutative()) {
1195 assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
1196 if (shouldSwapOperands(E->getOperand(0), E->getOperand(1)))
1197 E->swapOperands(0, 1);
1200 if (auto *CI = dyn_cast<CmpInst>(I)) {
1203 CmpInst::Predicate Predicate = CI->getPredicate();
1204 if (shouldSwapOperands(E->getOperand(0), E->getOperand(1))) {
1205 E->swapOperands(0, 1);
1208 E->setOpcode((CI->getOpcode() << 8) | Predicate);
1210 assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
1212 assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
1213 E->getOperand(1)->getType() == I->getOperand(1)->getType()));
1215 simplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), Q);
1219 if (isa<Constant>(E->getOperand(0)) ||
1220 E->getOperand(1) == E->getOperand(2)) {
1221 assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
1222 E->getOperand(2)->getType() == I->getOperand(2)->getType());
1223 Value *V = simplifySelectInst(E->getOperand(0), E->getOperand(1),
1224 E->getOperand(2), Q);
1228 } else if (I->isBinaryOp()) {
1230 simplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), Q);
1233 } else if (auto *CI = dyn_cast<CastInst>(I)) {
1235 simplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), Q);
1239 Value *V = simplifyGEPInst(GEPI->getSourceElementType(), *E->op_begin(),
1240 ArrayRef(std::next(E->op_begin()), E->op_end()),
1241 GEPI->getNoWrapFlags(), Q);
1253 for (Value *Arg : E->operands())
1267 AggregateValueExpression(I->getNumOperands(), II->getNumIndices());
1269 E->allocateIntOperands(ExpressionAllocator);
1270 std::copy(II->idx_begin(), II->idx_end(), int_op_inserter(E));
1274 AggregateValueExpression(I->getNumOperands(), EI->getNumIndices());
1276 E->allocateIntOperands(ExpressionAllocator);
1277 std::copy(EI->idx_begin(), EI->idx_end(), int_op_inserter(E));
1291 E->setOpcode(V->getValueID());
1303 E->setOpcode(C->getValueID());
1309 E->setOpcode(I->getOpcode());
1314 NewGVN::createCallExpression(CallInst *CI, const MemoryAccess *MA) const {
1317 new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, MA);
1318 setBasicExpressionInfo(CI, E);
1319 if (CI->isCommutative()) {
1323 assert(CI->getNumOperands() >= 2 && "Unsupported commutative intrinsic!");
1324 if (shouldSwapOperands(E->getOperand(0), E->getOperand(1)))
1325 E->swapOperands(0, 1);
1341 // dominator tree could have an infinite number of non-dominating siblings
1352 if (alwaysAvailable(CC->getLeader()))
1354 if (DT->dominates(cast<Instruction>(CC->getLeader()), U))
1356 if (CC->getNextLeader().first &&
1357 DT->dominates(cast<Instruction>(CC->getNextLeader().first), U))
1360 return Member != CC->getLeader() &&
1361 DT->dominates(cast<Instruction>(Member), U);
1374 return PoisonValue::get(V->getType());
1375 return CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
1383 assert(CC->getMemoryLeader() &&
1386 return CC->getMemoryLeader();
1401 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1402 E->setType(LoadType);
1405 E->setOpcode(0);
1406 E->op_push_back(PointerOp);
1416 auto *StoredValueLeader = lookupOperandLeader(SI->getValueOperand());
1418 StoreExpression(SI->getNumOperands(), SI, StoredValueLeader, MA);
1419 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1420 E->setType(SI->getValueOperand()->getType());
1423 E->setOpcode(0);
1424 E->op_push_back(lookupOperandLeader(SI->getPointerOperand()));
1438 const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess();
1440 StoreRHS = MSSAWalker->getClobberingMemoryAccess(StoreAccess);
1441 // If we bypassed the use-def chains, make sure we add a use.
1443 if (StoreRHS != StoreAccess->getDefiningAccess())
1447 StoreRHS = MSSA->getLiveOnEntryDef();
1449 if (SI->isSimple()) {
1460 if (LastCC && LastCC->getStoredValue() == LastStore->getStoredValue())
1466 if (auto *LI = dyn_cast<LoadInst>(LastStore->getStoredValue()))
1467 if ((lookupOperandLeader(LI->getPointerOperand()) ==
1468 LastStore->getOperand(0)) &&
1469 (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) ==
1487 assert((!LI || LI->isSimple()) && "Not a simple load");
1489 // Can't forward from non-atomic to atomic without violating memory model.
1492 if (LI->isAtomic() > DepSI->isAtomic() ||
1493 LoadType == DepSI->getValueOperand()->getType())
1498 lookupOperandLeader(DepSI->getValueOperand()))) {
1507 // Can't forward from non-atomic to atomic without violating memory model.
1508 if (LI->isAtomic() > DepLI->isAtomic())
1536 !AA->isMustAlias(LoadPtr, DepInst))
1548 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1560 // We can eliminate in favor of non-simple loads, but we won't be able to
1562 if (!LI->isSimple())
1565 Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand());
1568 return createConstantExpression(PoisonValue::get(LI->getType()));
1571 MSSAWalker->getClobberingMemoryAccess(OriginalAccess);
1573 if (!MSSA->isLiveOnEntryDef(DefiningAccess)) {
1575 Instruction *DefiningInst = MD->getMemoryInst();
1577 if (!ReachableBlocks.count(DefiningInst->getParent()))
1578 return createConstantExpression(PoisonValue::get(LI->getType()));
1584 performSymbolicLoadCoercion(LI->getType(), LoadAddressLeader, LI,
1590 const auto *LE = createLoadExpression(LI->getType(), LoadAddressLeader, LI,
1594 if (LE->getMemoryLeader() != DefiningAccess)
1595 addMemoryUsers(LE->getMemoryLeader(), OriginalAccess);
1601 auto *PI = PredInfo->getPredicateInfoFor(I);
1607 const std::optional<PredicateConstraint> &Constraint = PI->getConstraint();
1611 CmpInst::Predicate Predicate = Constraint->Predicate;
1612 Value *CmpOp0 = I->getOperand(0);
1613 Value *CmpOp1 = Constraint->OtherOp;
1632 !cast<ConstantFP>(FirstOp)->isZero())
1641 auto *CI = cast<CallInst>(I);
1644 if (auto *ReturnedValue = II->getReturnedArgOperand()) {
1645 if (II->getIntrinsicID() == Intrinsic::ssa_copy)
1659 if (CI->getFunction()->isPresplitCoroutine())
1665 if (CI->isConvergent())
1668 if (AA->doesNotAccessMemory(CI)) {
1670 createCallExpression(CI, TOPClass->getMemoryLeader()));
1671 } else if (AA->onlyReadsMemory(CI)) {
1672 if (auto *MA = MSSA->getMemoryAccess(CI)) {
1673 auto *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(MA);
1674 return ExprResult::some(createCallExpression(CI, DefiningAccess));
1675 } else // MSSA determined that CI does not access memory.
1677 createCallExpression(CI, TOPClass->getMemoryLeader()));
1694 "Every MemoryAccess should be getting mapped to a non-null class");
1697 LLVM_DEBUG(dbgs() << NewClass->getID()
1699 LLVM_DEBUG(dbgs() << *NewClass->getMemoryLeader() << "\n");
1705 auto *OldClass = LookupResult->second;
1709 OldClass->memory_erase(MP);
1710 NewClass->memory_insert(MP);
1711 // This may have killed the class if it had no non-memory members
1712 if (OldClass->getMemoryLeader() == From) {
1713 if (OldClass->definesNoMemory()) {
1714 OldClass->setMemoryLeader(nullptr);
1716 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
1718 << OldClass->getID() << " to "
1719 << *OldClass->getMemoryLeader()
1727 LookupResult->second = NewClass;
1735 // Determine if a instruction is cycle-free. That means the values in the
1737 // of the instruction. For example, a non-cycle free instruction would be v =
1740 // In order to compute cycle-freeness, we do SCC finding on the instruction,
1742 // cycle-free. If it is not in a singleton, it is only cycle free if the
1785 auto Filtered = make_filter_range(E->operands(), [&](Value *Arg) {
1798 // If it has undef or poison at this point, it means there are no-non-undef
1803 << " has no non-undef arguments, valuing it as undef\n");
1804 return createConstantExpression(UndefValue::get(I->getType()));
1809 << " has no non-poison arguments, valuing it as poison\n");
1810 return createConstantExpression(PoisonValue::get(I->getType()));
1821 // Can't fold phi(undef, X) -> X unless X can't be poison (thus X is undef
1826 // In LLVM's non-standard representation of phi nodes, it's possible to have
1868 auto *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
1869 if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0)
1873 return createBinaryExpression(WO->getBinaryOp(), EI->getType(),
1874 WO->getLHS(), WO->getRHS(), I);
1883 auto *CI = cast<CmpInst>(I);
1886 auto Op0 = lookupOperandLeader(CI->getOperand(0));
1887 auto Op1 = lookupOperandLeader(CI->getOperand(1));
1888 auto OurPredicate = CI->getPredicate();
1891 OurPredicate = CI->getSwappedPredicate();
1898 auto *CmpPI = PredInfo->getPredicateInfoFor(I);
1901 createConstantExpression(ConstantInt::getTrue(CI->getType())));
1905 if (CI->isTrueWhenEqual())
1907 createConstantExpression(ConstantInt::getTrue(CI->getType())));
1908 else if (CI->isFalseWhenEqual())
1910 createConstantExpression(ConstantInt::getFalse(CI->getType())));
1938 for (const auto &Op : CI->operands()) {
1939 auto *PI = PredInfo->getPredicateInfoFor(Op);
1946 if (!DT->dominates(PBranch->To, I->getParent()))
1953 auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
1956 auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
1957 auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
1958 auto BranchPredicate = BranchCond->getPredicate();
1961 BranchPredicate = BranchCond->getSwappedPredicate();
1964 if (PBranch->TrueEdge) {
1969 auto *C = ConstantInt::getBool(CI->getType(), *R);
1978 createConstantExpression(ConstantInt::getFalse(CI->getType())),
1984 createConstantExpression(ConstantInt::getTrue(CI->getType())),
2004 switch (I->getOpcode()) {
2012 for (unsigned i = 0; i < PN->getNumOperands(); ++i)
2013 Ops.push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)});
2081 // Look up a container of values/instructions in a map, and touch all the
2082 // instructions in the container. Then erase value from the map.
2087 for (const typename Map::mapped_type::value_type Mapped : Result->second)
2106 PredicateToUsers[PBranch->Condition].insert(User);
2108 PredicateToUsers[PAssume->Condition].insert(User);
2115 for (auto *User : V->users()) {
2134 for (const auto *U : MA->users())
2146 for (const auto *M : CC->memory())
2180 assert(!CC->definesNoMemory() && "Can't get next leader if there is none");
2181 if (CC->getStoreCount() > 0) {
2182 if (auto *NL = dyn_cast_or_null<StoreInst>(CC->getNextLeader().first))
2189 assert(CC->getStoreCount() == 0);
2192 // !OldClass->memory_empty()
2193 if (CC->memory_size() == 1)
2194 return *CC->memory_begin();
2195 return getMinDFSOfRange<const MemoryPhi>(CC->memory());
2206 if (CC->size() == 1 || CC == TOPClass) {
2207 return *(CC->begin());
2208 } else if (CC->getNextLeader().first) {
2210 return CC->getNextLeader().first;
2225 // - I must be moving to NewClass from OldClass
2226 // - The StoreCount of OldClass and NewClass is expected to have been updated
2228 // - The OldClass memory leader has not been updated yet if I was the leader.
2235 assert((!InstMA || !OldClass->getMemoryLeader() ||
2236 OldClass->getLeader() != I ||
2237 MemoryAccessToClass.lookup(OldClass->getMemoryLeader()) ==
2241 if (!NewClass->getMemoryLeader()) {
2243 assert(NewClass->size() == 1 ||
2244 (isa<StoreInst>(I) && NewClass->getStoreCount() == 1));
2245 NewClass->setMemoryLeader(InstMA);
2248 << NewClass->getID()
2254 if (OldClass->getMemoryLeader() == InstMA) {
2255 if (!OldClass->definesNoMemory()) {
2256 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
2258 << OldClass->getID() << " to "
2259 << *OldClass->getMemoryLeader()
2263 OldClass->setMemoryLeader(nullptr);
2272 if (I == OldClass->getNextLeader().first)
2273 OldClass->resetNextLeader();
2275 OldClass->erase(I);
2276 NewClass->insert(I);
2280 if (NewClass->getLeader() != I &&
2281 NewClass->addPossibleLeader({I, InstrToDFSNum(I)})) {
2287 OldClass->decStoreCount();
2295 if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) {
2299 NewClass->setStoredValue(SE->getStoredValue());
2303 << NewClass->getID() << " from "
2304 << *NewClass->getLeader() << " to " << *SI
2308 NewClass->setLeader({SI, InstrToDFSNum(SI)});
2312 NewClass->incStoreCount();
2323 if (OldClass->empty() && OldClass != TOPClass) {
2324 if (OldClass->getDefiningExpr()) {
2325 LLVM_DEBUG(dbgs() << "Erasing expression " << *OldClass->getDefiningExpr()
2330 ExactEqualsExpression(*OldClass->getDefiningExpr()));
2335 (*OldClass->getDefiningExpr() != *E || ExpressionToClass.lookup(E)) &&
2339 } else if (OldClass->getLeader() == I) {
2344 << OldClass->getID() << "\n");
2350 if (OldClass->getStoreCount() == 0) {
2351 if (OldClass->getStoredValue())
2352 OldClass->setStoredValue(nullptr);
2354 OldClass->setLeader({getNextValueLeader(OldClass),
2356 OldClass->resetNextLeader();
2375 assert(!IClass->isDead() && "Found a dead class");
2379 EClass = ValueToClass.lookup(VE->getVariableValue());
2390 place->second = NewClass;
2394 NewClass->setLeader({CE->getConstantValue(), 0});
2396 StoreInst *SI = SE->getStoreInst();
2397 NewClass->setLeader({SI, InstrToDFSNum(SI)});
2398 NewClass->setStoredValue(SE->getStoredValue());
2402 NewClass->setLeader({I, InstrToDFSNum(I)});
2410 << NewClass->getID() << " and leader "
2411 << *(NewClass->getLeader()));
2412 if (NewClass->getStoredValue())
2414 << *(NewClass->getStoredValue()));
2417 EClass = lookupResult.first->second;
2419 assert((isa<Constant>(EClass->getLeader()) ||
2420 (EClass->getStoredValue() &&
2421 isa<Constant>(EClass->getStoredValue()))) &&
2427 assert(!EClass->isDead() && "We accidentally looked up a dead class");
2433 LLVM_DEBUG(dbgs() << "New class " << EClass->getID() << " for expression "
2443 if (auto *CI = dyn_cast<CmpInst>(I))
2444 markPredicateUsersTouched(CI);
2517 CondEvaluated = CE->getConstantValue();
2528 ConstantInt *CI;
2529 if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
2530 if (CI->isOne()) {
2534 } else if (CI->isZero()) {
2547 Value *SwitchCond = SI->getCondition();
2553 auto Case = *SI->findCaseValue(CondVal);
2554 if (Case.getCaseSuccessor() == SI->getDefaultDest()) {
2558 updateReachableEdge(B, SI->getDefaultDest());
2565 for (BasicBlock *TargetBlock : successors(SI->getParent()))
2571 for (BasicBlock *TargetBlock : successors(TI->getParent()))
2608 for (auto *U : ExistingValue->users())
2638 return OISIt->second;
2642 if (DT->properlyDominates(getBlockForValue(I), PHIBlock)) {
2659 if (OrigI->mayReadFromMemory())
2663 for (auto *Op : OrigI->operand_values()) {
2669 if (!OISIt->second) {
2720 FoundVal = SI->getValueOperand();
2749 if (MemAccess && !isa<MemoryPhi>(MemAccess->getDefiningAccess()) &&
2750 MemAccess->getDefiningAccess()->getBlock() == I->getParent())
2755 SmallVector<Value *, 4> Ops(I->operand_values());
2777 // No point in doing this for one-operand phis.
2780 if (OpPHI->getNumOperands() == 1)
2791 for (unsigned PredNum = 0; PredNum < OpPHI->getNumOperands(); ++PredNum) {
2792 auto *PredBB = OpPHI->getIncomingBlock(PredNum);
2800 Instruction *ValueOp = I->clone();
2803 ValueOp->insertBefore(PredBB->getTerminator()->getIterator());
2808 for (auto &Op : ValueOp->operands()) {
2813 Op = Op->DoPHITranslation(PHIBlock, PredBB);
2818 Op = ValuePHI->getIncomingValueForBlock(PredBB);
2820 // If we phi-translated the op, it must be safe.
2828 // have made a phi-of-ops (or value numbered it equivalent to something)
2833 ValueOp->eraseFromParent();
2848 FoundVal = PoisonValue::get(I->getType());
2867 // PHI-of-ops is not materialized in the IR. If any of those leaders
2868 // changes, the PHI-of-op may change also, so we need to add the operands as
2879 PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops");
2886 ValuePHI->addIncoming(PHIOp.first, PHIOp.second);
2891 ValuePHI->setIncomingValue(i, PHIOp.first);
2892 ValuePHI->setIncomingBlock(i, PHIOp.second);
2918 TOPClass->setMemoryLeader(MSSA->getLiveOnEntryDef());
2920 MemoryAccessToClass[MSSA->getLiveOnEntryDef()] =
2921 createMemoryClass(MSSA->getLiveOnEntryDef());
2924 BasicBlock *BB = DTN->getBlock();
2929 auto *MemoryBlockDefs = MSSA->getBlockDefs(BB);
2937 TOPClass->memory_insert(MP);
2941 if (MD && isa<StoreInst>(MD->getMemoryInst()))
2942 TOPClass->incStoreCount();
2956 if (I.isTerminator() && I.getType()->isVoidTy())
2958 TOPClass->insert(&I);
2970 LLVM_DEBUG(dbgs() << "Congruence class " << CC->getID() << " has "
2971 << CC->size() << " members\n");
2986 I->dropAllReferences();
2991 I->deleteValue();
3051 // All of the range functions taken half-open ranges (open on the end side).
3073 // TODO: We could do cycle-checking on the memory phis to allow valueizing for
3074 // self-phi checking.
3075 const BasicBlock *PHIBlock = MP->getBlock();
3076 auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) {
3079 ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock});
3083 // least one self-argument.
3130 if (!I->isTerminator()) {
3161 // don't currently understand. We don't place non-value producing
3163 if (!I->getType()->isVoidTy()) {
3167 processOutgoingEdges(I, I->getParent());
3178 if (MSSA->isLiveOnEntryDef(First))
3193 if (MSSA->isLiveOnEntryDef(ChainDef))
3199 return ReachableEdges.count({MP->getIncomingBlock(U), MP->getBlock()});
3202 make_filter_range(MP->operands(), ReachableOperandPred);
3220 if (CC == TOPClass || CC->isDead())
3222 if (CC->getStoreCount() != 0) {
3223 assert((CC->getStoredValue() || !isa<StoreInst>(CC->getLeader())) &&
3226 assert(CC->getMemoryLeader() &&
3231 if (CC->getMemoryLeader())
3232 assert(MemoryAccessToClass.lookup(CC->getMemoryLeader()) == CC &&
3235 for (const auto *M : CC->memory())
3247 bool Result = ReachableBlocks.count(Pair.first->getBlock());
3248 if (!Result || MSSA->isLiveOnEntryDef(Pair.first) ||
3252 return !isInstructionTriviallyDead(MemDef->getMemoryInst());
3257 for (const auto &U : MemPHI->incoming_values()) {
3272 auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second->getMemoryLeader());
3276 ValueToClass.lookup(FirstMUD->getMemoryInst()) ==
3277 ValueToClass.lookup(SecondMUD->getMemoryInst())) &&
3287 {FirstMP->getIncomingBlock(U), FirstMP->getBlock()}) &&
3292 make_filter_range(FirstMP->operands(), ReachableOperandPred);
3297 return ValueToClass.lookup(MD->getMemoryInst());
3343 auto *BeforeCC = &BeforeIteration.find(KV.first)->second;
3348 assert(BeforeCC->isEquivalentTo(AfterCC) &&
3360 // a no-longer valid StoreExpression.
3373 {SE->getOperand(0), std::make_tuple(SE->getMemoryLeader(), KV.second,
3374 SE->getStoredValue())});
3380 Okay = (std::get<1>(Res.first->second) == KV.second) &&
3381 (lookupOperandLeader(std::get<2>(Res.first->second)) ==
3382 lookupOperandLeader(SE->getStoredValue()));
3384 auto *ValueExpr = ValueToExpression.lookup(SE->getStoreInst());
3385 assert(ValueExpr && ValueExpr->equals(*SE) &&
3401 if (FirstInstr == -1)
3407 // TODO: As we hit a new block, we should push and pop equalities into a
3409 // might miss, like edge-only equivalences.
3437 CacheIdx = RPOOrdering.lookup(DT->getNode(CurrBlock)) - 1;
3464 MSSAWalker = MSSA->getWalker();
3483 auto *Node = DT->getNode(B);
3489 auto *Node = DT->getNode(B);
3490 if (Node->getNumChildren() > 1)
3497 for (auto *DTN : depth_first(DT->getRootNode())) {
3498 BasicBlock *B = DTN->getBlock();
3501 ICount += BlockRange.second - BlockRange.first;
3529 if (!ToErase->use_empty())
3530 ToErase->replaceAllUsesWith(PoisonValue::get(ToErase->getType()));
3532 assert(ToErase->getParent() &&
3534 ToErase->eraseFromParent();
3566 // It's not enough that any given field be less than - we have sets
3577 // Each LLVM instruction only produces one value, and thus the lowest-level
3614 // dead (have no non-dead uses) are stored in ProbablyDead.
3626 DomTreeNode *DomNode = DT->getNode(BB);
3627 VDDef.DFSIn = DomNode->getDFSNumIn();
3628 VDDef.DFSOut = DomNode->getDFSNumOut();
3633 auto Leader = lookupOperandLeader(SI->getValueOperand());
3637 VDDef.Def.setPointer(SI->getValueOperand());
3662 for (auto &U : Def->uses()) {
3671 IBlock = P->getIncomingBlock(U);
3685 DomTreeNode *DomNode = DT->getNode(IBlock);
3686 VDUse.DFSIn = DomNode->getDFSNumIn();
3687 VDUse.DFSOut = DomNode->getDFSNumOut();
3694 // If there are no uses, it's probably dead (but it may have side-effects,
3715 DomTreeNode *DomNode = DT->getNode(BB);
3716 VD.DFSIn = DomNode->getDFSNumIn();
3717 VD.DFSOut = DomNode->getDFSNumOut();
3732 I->replaceAllUsesWith(Repl);
3740 // to update as many def-use and use-def chains. Start after the terminator.
3741 auto StartPoint = BB->rbegin();
3743 // Note that we explicitly recalculate BB->rend() on each iteration,
3745 for (BasicBlock::reverse_iterator I(StartPoint); I != BB->rend();) {
3757 Type *Int8Ty = Type::getInt8Ty(BB->getContext());
3760 Constant::getNullValue(PointerType::getUnqual(BB->getContext())),
3761 BB->getTerminator()->getIterator());
3822 return ValueToClass.lookup(VE->getVariableValue());
3835 return CE->getConstantValue();
3837 auto *V = VE->getVariableValue();
3838 if (alwaysAvailable(V) || DT->dominates(getBlockForValue(V), BB))
3839 return VE->getVariableValue();
3845 if (alwaysAvailable(CC->getLeader()))
3846 return CC->getLeader();
3855 if (DT->dominates(getBlockForValue(MemberInst), BB))
3862 // This is a non-standard eliminator. The normal way to eliminate is
3889 DT->updateDFSNumbers();
3894 for (auto &Operand : PHI->incoming_values())
3895 if (!ReachableEdges.count({PHI->getIncomingBlock(Operand), BB})) {
3898 << getBlockName(PHI->getIncomingBlock(Operand))
3900 Operand.set(PoisonValue::get(PHI->getType()));
3923 if (ReachablePredCount.lookup(BB) != PHI->getNumIncomingValues())
3931 LLVM_DEBUG(dbgs() << "Eliminating in congruence class " << CC->getID()
3937 if (CC->isDead() || CC->empty())
3945 assert((!ReachableBlocks.count(cast<Instruction>(M)->getParent()) ||
3953 assert(CC->getLeader() && "We should have had a leader");
3959 CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
3966 Member->getType()->isVoidTy()) {
3978 CC->swap(MembersLeft);
3981 if (CC->size() != 1 || RealToTemp.count(Leader)) {
4001 if (Def && Def->getType()->isVoidTy())
4015 PN->insertBefore(DefBlock->begin());
4038 // If the stack is now empty, we need to push
4040 // start using, we also push.
4060 // guarantees that any side-effects that would have occurred (ie
4062 // dominated by something that has the same side-effects), or never
4067 // easy to prove dead if they are also side-effect free. Note that
4088 assert(isa<Instruction>(U->get()) &&
4090 assert(isa<Instruction>(U->getUser()) &&
4097 Instruction *InstUse = cast<Instruction>(U->getUser());
4099 auto &UseCount = UseCounts[U->get()];
4100 if (--UseCount == 0) {
4101 ProbablyDead.insert(cast<Instruction>(U->get()));
4113 bool isSSACopy = II && II->getIntrinsicID() == Intrinsic::ssa_copy;
4115 DominatingLeader = II->getOperand(0);
4118 if (U->get() == DominatingLeader)
4124 auto *ReplacedInst = cast<Instruction>(U->get());
4125 auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
4126 if (!PI || DominatingLeader != PI->OriginalOp)
4131 << *U->get() << " in " << *(U->getUser()) << "\n");
4132 U->set(DominatingLeader);
4144 unsigned &IIUseCount = It->second;
4145 if (--IIUseCount == 0)
4167 CC->swap(MembersLeft);
4170 if (CC->getStoreCount() > 0) {
4193 assert(DT->dominates(Leader->getParent(), Member->getParent()));
4198 CC->erase(Member);
4226 return 4 + A->getArgNo();
4253 LookupResult->second = B;
4258 auto *SeenPredicate = LookupResult->second;
4263 LookupResult->second = nullptr;