63#define DEBUG_TYPE "early-cse"
65STATISTIC(NumSimplify,
"Number of instructions simplified or DCE'd");
67STATISTIC(NumCSECVP,
"Number of compare instructions CVP'd");
68STATISTIC(NumCSELoad,
"Number of load instructions CSE'd");
69STATISTIC(NumCSECall,
"Number of call instructions CSE'd");
70STATISTIC(NumDSE,
"Number of trivial dead stores removed");
73 "Controls which instructions are removed");
77 cl::desc(
"Enable imprecision in EarlyCSE in pathological cases, in exchange "
78 "for faster compile. Caps the MemorySSA clobbering calls."));
82 cl::desc(
"Perform extra assertion checking to verify that SimpleValue's hash "
83 "function is well-behaved w.r.t. its isEqual predicate"));
108 if (
CallInst *CI = dyn_cast<CallInst>(Inst)) {
109 if (
Function *
F = CI->getCalledFunction()) {
111 case Intrinsic::experimental_constrained_fadd:
112 case Intrinsic::experimental_constrained_fsub:
113 case Intrinsic::experimental_constrained_fmul:
114 case Intrinsic::experimental_constrained_fdiv:
115 case Intrinsic::experimental_constrained_frem:
116 case Intrinsic::experimental_constrained_fptosi:
117 case Intrinsic::experimental_constrained_sitofp:
118 case Intrinsic::experimental_constrained_fptoui:
119 case Intrinsic::experimental_constrained_uitofp:
120 case Intrinsic::experimental_constrained_fcmp:
121 case Intrinsic::experimental_constrained_fcmps: {
122 auto *CFP = cast<ConstrainedFPIntrinsic>(CI);
123 if (CFP->getExceptionBehavior() &&
128 if (CFP->getRoundingMode() &&
129 CFP->getRoundingMode() == RoundingMode::Dynamic)
135 return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy() &&
143 !CI->getFunction()->isPresplitCoroutine();
145 return isa<CastInst>(Inst) || isa<UnaryOperator>(Inst) ||
146 isa<BinaryOperator>(Inst) || isa<GetElementPtrInst>(Inst) ||
147 isa<CmpInst>(Inst) || isa<SelectInst>(Inst) ||
148 isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
149 isa<ShuffleVectorInst>(Inst) || isa<ExtractValueInst>(Inst) ||
150 isa<InsertValueInst>(Inst) || isa<FreezeInst>(Inst);
168 static bool isEqual(SimpleValue LHS, SimpleValue RHS);
202 Pred = ICmpInst::getSwappedPredicate(Pred);
227 if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
233 if (
CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
242 if (std::tie(
LHS, Pred) > std::tie(
RHS, SwappedPred)) {
282 if (
CastInst *CI = dyn_cast<CastInst>(Inst))
283 return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
285 if (
FreezeInst *FI = dyn_cast<FreezeInst>(Inst))
286 return hash_combine(FI->getOpcode(), FI->getOperand(0));
289 return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
293 return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
297 assert((isa<CallInst>(Inst) || isa<GetElementPtrInst>(Inst) ||
298 isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
299 isa<ShuffleVectorInst>(Inst) || isa<UnaryOperator>(Inst) ||
300 isa<FreezeInst>(Inst)) &&
301 "Invalid/unknown instruction");
306 auto *II = dyn_cast<IntrinsicInst>(Inst);
307 if (II && II->isCommutative() && II->arg_size() == 2) {
308 Value *
LHS = II->getArgOperand(0), *
RHS = II->getArgOperand(1);
318 return hash_combine(GCR->getOpcode(), GCR->getOperand(0),
319 GCR->getBasePtr(), GCR->getDerivedPtr());
342 if (
LHS.isSentinel() ||
RHS.isSentinel())
345 if (LHSI->
getOpcode() != RHSI->getOpcode())
352 if (!LHSBinOp->isCommutative())
355 assert(isa<BinaryOperator>(RHSI) &&
356 "same opcode, but different instruction type?");
360 return LHSBinOp->getOperand(0) == RHSBinOp->
getOperand(1) &&
361 LHSBinOp->getOperand(1) == RHSBinOp->
getOperand(0);
363 if (
CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
364 assert(isa<CmpInst>(RHSI) &&
365 "same opcode, but different instruction type?");
366 CmpInst *RHSCmp = cast<CmpInst>(RHSI);
368 return LHSCmp->getOperand(0) == RHSCmp->
getOperand(1) &&
369 LHSCmp->getOperand(1) == RHSCmp->
getOperand(0) &&
370 LHSCmp->getSwappedPredicate() == RHSCmp->
getPredicate();
374 auto *LII = dyn_cast<IntrinsicInst>(LHSI);
375 auto *RII = dyn_cast<IntrinsicInst>(RHSI);
376 if (LII && RII && LII->getIntrinsicID() == RII->getIntrinsicID() &&
377 LII->isCommutative() && LII->arg_size() == 2) {
378 return LII->getArgOperand(0) == RII->getArgOperand(1) &&
379 LII->getArgOperand(1) == RII->getArgOperand(0);
385 return GCR1->getOperand(0) == GCR2->getOperand(0) &&
386 GCR1->getBasePtr() == GCR2->getBasePtr() &&
387 GCR1->getDerivedPtr() == GCR2->getDerivedPtr();
393 Value *CondL, *CondR, *LHSA, *RHSA, *LHSB, *RHSB;
400 return ((LHSA == RHSA && LHSB == RHSB) ||
401 (LHSA == RHSB && LHSB == RHSA));
404 if (CondL == CondR && LHSA == RHSA && LHSB == RHSB)
426 if (LHSA == RHSB && LHSB == RHSA) {
473 CallInst *CI = dyn_cast<CallInst>(Inst);
502 static bool isEqual(CallValue LHS, CallValue RHS);
518 if (
LHS.isSentinel() ||
RHS.isSentinel())
545 std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
560 ScopedHTType AvailableValues;
578 unsigned Generation = 0;
580 bool IsAtomic =
false;
582 LoadValue() =
default;
583 LoadValue(
Instruction *Inst,
unsigned Generation,
unsigned MatchingId,
585 : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
586 IsAtomic(IsAtomic) {}
589 using LoadMapAllocator =
596 LoadHTType AvailableLoads;
601 using InvariantMapAllocator =
604 using InvariantHTType =
606 InvariantMapAllocator>;
607 InvariantHTType AvailableInvariants;
615 CallHTType AvailableCalls;
618 unsigned CurrentGeneration = 0;
624 : TLI(TLI),
TTI(
TTI), DT(DT), AC(AC), SQ(
DL, &TLI, &DT, &AC), MSSA(MSSA),
630 unsigned ClobberCounter = 0;
636 NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
637 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls)
638 :
Scope(AvailableValues), LoadScope(AvailableLoads),
639 InvariantScope(AvailableInvariants), CallScope(AvailableCalls) {}
640 NodeScope(
const NodeScope &) =
delete;
641 NodeScope &operator=(
const NodeScope &) =
delete;
656 StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
657 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,
660 : CurrentGeneration(cg), ChildGeneration(cg),
Node(n), ChildIter(child),
662 Scopes(AvailableValues, AvailableLoads, AvailableInvariants,
665 StackNode(
const StackNode &) =
delete;
666 StackNode &operator=(
const StackNode &) =
delete;
669 unsigned currentGeneration()
const {
return CurrentGeneration; }
670 unsigned childGeneration()
const {
return ChildGeneration; }
682 bool isProcessed()
const {
return Processed; }
683 void process() { Processed =
true; }
686 unsigned CurrentGeneration;
687 unsigned ChildGeneration;
692 bool Processed =
false;
697 class ParseMemoryInst {
702 IntrID = II->getIntrinsicID();
705 if (isHandledNonTargetIntrinsic(IntrID)) {
707 case Intrinsic::masked_load:
709 Info.MatchingId = Intrinsic::masked_load;
711 Info.WriteMem =
false;
712 Info.IsVolatile =
false;
714 case Intrinsic::masked_store:
722 Info.MatchingId = Intrinsic::masked_load;
723 Info.ReadMem =
false;
724 Info.WriteMem =
true;
725 Info.IsVolatile =
false;
738 return isa<LoadInst>(Inst);
743 return Info.WriteMem;
744 return isa<StoreInst>(Inst);
747 bool isAtomic()
const {
749 return Info.Ordering != AtomicOrdering::NotAtomic;
753 bool isUnordered()
const {
755 return Info.isUnordered();
757 if (
LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
758 return LI->isUnordered();
759 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
760 return SI->isUnordered();
766 bool isVolatile()
const {
768 return Info.IsVolatile;
770 if (
LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
771 return LI->isVolatile();
772 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
773 return SI->isVolatile();
779 bool isInvariantLoad()
const {
780 if (
auto *LI = dyn_cast<LoadInst>(Inst))
781 return LI->hasMetadata(LLVMContext::MD_invariant_load);
791 int getMatchingId()
const {
793 return Info.MatchingId;
803 Type *getValueType()
const {
806 switch (II->getIntrinsicID()) {
807 case Intrinsic::masked_load:
808 return II->getType();
809 case Intrinsic::masked_store:
810 return II->getArgOperand(0)->getType();
818 bool mayReadFromMemory()
const {
824 bool mayWriteToMemory()
const {
826 return Info.WriteMem;
840 case Intrinsic::masked_load:
841 case Intrinsic::masked_store:
846 static bool isHandledNonTargetIntrinsic(
const Value *V) {
847 if (
auto *II = dyn_cast<IntrinsicInst>(V))
848 return isHandledNonTargetIntrinsic(II->getIntrinsicID());
857 Value *getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
858 unsigned CurrentGeneration);
860 bool overridingStores(
const ParseMemoryInst &Earlier,
861 const ParseMemoryInst &Later);
865 if (
auto *LI = dyn_cast<LoadInst>(Inst))
866 return LI->
getType() == ExpectedType ? LI :
nullptr;
867 if (
auto *SI = dyn_cast<StoreInst>(Inst)) {
869 return V->getType() == ExpectedType ?
V :
nullptr;
871 assert(isa<IntrinsicInst>(Inst) &&
"Instruction not supported");
872 auto *II = cast<IntrinsicInst>(Inst);
873 if (isHandledNonTargetIntrinsic(II->getIntrinsicID()))
874 return getOrCreateResultNonTargetMemIntrinsic(II, ExpectedType);
879 Type *ExpectedType)
const {
882 case Intrinsic::masked_load:
883 return II->
getType() == ExpectedType ? II :
nullptr;
884 case Intrinsic::masked_store: {
886 return V->getType() == ExpectedType ?
V :
nullptr;
894 bool isOperatingOnInvariantMemAt(
Instruction *
I,
unsigned GenAt);
896 bool isSameMemGeneration(
unsigned EarlierGeneration,
unsigned LaterGeneration,
901 auto IsSubmask = [](
const Value *Mask0,
const Value *Mask1) {
905 if (isa<UndefValue>(Mask0) || isa<UndefValue>(Mask1))
907 auto *Vec0 = dyn_cast<ConstantVector>(Mask0);
908 auto *Vec1 = dyn_cast<ConstantVector>(Mask1);
911 if (Vec0->getType() != Vec1->getType())
913 for (
int i = 0, e = Vec0->getNumOperands(); i != e; ++i) {
916 auto *Int0 = dyn_cast<ConstantInt>(Elem0);
917 if (Int0 && Int0->isZero())
919 auto *
Int1 = dyn_cast<ConstantInt>(Elem1);
922 if (isa<UndefValue>(Elem0) || isa<UndefValue>(Elem1))
950 if (PtrOp(Earlier) != PtrOp(Later))
957 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_load) {
963 if (MaskOp(Earlier) == MaskOp(Later) && ThruOp(Earlier) == ThruOp(Later))
965 if (!isa<UndefValue>(ThruOp(Later)))
967 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
969 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_load) {
974 if (!IsSubmask(MaskOp(Later), MaskOp(Earlier)))
976 return isa<UndefValue>(ThruOp(Later));
978 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_store) {
982 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
984 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_store) {
989 return IsSubmask(MaskOp(Earlier), MaskOp(Later));
1005 MSSAUpdater->removeMemoryAccess(&Inst,
true);
1027bool EarlyCSE::isSameMemGeneration(
unsigned EarlierGeneration,
1028 unsigned LaterGeneration,
1032 if (EarlierGeneration == LaterGeneration)
1061 LaterDef = LaterMA->getDefiningAccess();
1063 return MSSA->
dominates(LaterDef, EarlierMA);
1066bool EarlyCSE::isOperatingOnInvariantMemAt(
Instruction *
I,
unsigned GenAt) {
1069 if (
auto *LI = dyn_cast<LoadInst>(
I))
1070 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1079 if (!AvailableInvariants.count(MemLoc))
1084 return AvailableInvariants.lookup(MemLoc) <= GenAt;
1087bool EarlyCSE::handleBranchCondition(
Instruction *CondInst,
1098 if (Opcode == Instruction::And &&
1101 else if (Opcode == Instruction::Or &&
1109 unsigned PropagateOpcode =
1110 (BI->
getSuccessor(0) == BB) ? Instruction::And : Instruction::Or;
1112 bool MadeChanges =
false;
1116 while (!WorkList.
empty()) {
1119 AvailableValues.insert(Curr, TorF);
1121 << Curr->
getName() <<
"' as " << *TorF <<
" in "
1135 if (MatchBinOp(Curr, PropagateOpcode, LHS, RHS))
1136 for (
auto *Op : {
LHS,
RHS })
1138 if (SimpleValue::canHandle(OPI) && Visited.
insert(OPI).second)
1145Value *EarlyCSE::getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
1146 unsigned CurrentGeneration) {
1147 if (InVal.DefInst ==
nullptr)
1149 if (InVal.MatchingId != MemInst.getMatchingId())
1152 if (MemInst.isVolatile() || !MemInst.isUnordered())
1155 if (MemInst.isLoad() && !InVal.IsAtomic && MemInst.isAtomic())
1161 bool MemInstMatching = !MemInst.isLoad();
1162 Instruction *Matching = MemInstMatching ? MemInst.get() : InVal.DefInst;
1168 ? getOrCreateResult(Matching,
Other->getType())
1170 if (MemInst.isStore() && InVal.DefInst != Result)
1174 bool MatchingNTI = isHandledNonTargetIntrinsic(Matching);
1175 bool OtherNTI = isHandledNonTargetIntrinsic(
Other);
1176 if (OtherNTI != MatchingNTI)
1178 if (OtherNTI && MatchingNTI) {
1179 if (!isNonTargetIntrinsicMatch(cast<IntrinsicInst>(InVal.DefInst),
1180 cast<IntrinsicInst>(MemInst.get())))
1184 if (!isOperatingOnInvariantMemAt(MemInst.get(), InVal.Generation) &&
1185 !isSameMemGeneration(InVal.Generation, CurrentGeneration, InVal.DefInst,
1190 Result = getOrCreateResult(Matching,
Other->getType());
1194bool EarlyCSE::overridingStores(
const ParseMemoryInst &Earlier,
1195 const ParseMemoryInst &Later) {
1198 assert(Earlier.isUnordered() && !Earlier.isVolatile() &&
1199 "Violated invariant");
1200 if (Earlier.getPointerOperand() != Later.getPointerOperand())
1202 if (!Earlier.getValueType() || !Later.getValueType() ||
1203 Earlier.getValueType() != Later.getValueType())
1205 if (Earlier.getMatchingId() != Later.getMatchingId())
1212 if (!Earlier.isUnordered() || !Later.isUnordered())
1216 bool ENTI = isHandledNonTargetIntrinsic(Earlier.get());
1217 bool LNTI = isHandledNonTargetIntrinsic(Later.get());
1219 return isNonTargetIntrinsicMatch(cast<IntrinsicInst>(Earlier.get()),
1220 cast<IntrinsicInst>(Later.get()));
1225 return ENTI == LNTI;
1229 bool Changed =
false;
1239 ++CurrentGeneration;
1250 auto *CondInst = dyn_cast<Instruction>(BI->
getCondition());
1251 if (CondInst && SimpleValue::canHandle(CondInst))
1252 Changed |= handleBranchCondition(CondInst, BI, BB, Pred);
1286 if (
auto *Assume = dyn_cast<AssumeInst>(&Inst)) {
1287 auto *CondI = dyn_cast<Instruction>(Assume->getArgOperand(0));
1288 if (CondI && SimpleValue::canHandle(CondI)) {
1293 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping assumption: " << Inst <<
'\n');
1299 m_Intrinsic<Intrinsic::experimental_noalias_scope_decl>())) {
1300 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping noalias intrinsic: " << Inst
1306 if (
match(&Inst, m_Intrinsic<Intrinsic::sideeffect>())) {
1307 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping sideeffect: " << Inst <<
'\n');
1312 if (
match(&Inst, m_Intrinsic<Intrinsic::pseudoprobe>())) {
1313 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping pseudoprobe: " << Inst <<
'\n');
1330 if (
match(&Inst, m_Intrinsic<Intrinsic::invariant_start>())) {
1337 if (!AvailableInvariants.count(MemLoc))
1338 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1344 dyn_cast<Instruction>(cast<CallInst>(Inst).getArgOperand(0))) {
1345 if (SimpleValue::canHandle(CondI)) {
1347 if (
auto *KnownCond = AvailableValues.lookup(CondI)) {
1349 if (isa<ConstantInt>(KnownCond) &&
1350 cast<ConstantInt>(KnownCond)->isOne()) {
1352 <<
"EarlyCSE removing guard: " << Inst <<
'\n');
1360 cast<CallInst>(Inst).setArgOperand(0, KnownCond);
1371 LastStore =
nullptr;
1378 LLVM_DEBUG(
dbgs() <<
"EarlyCSE Simplify: " << Inst <<
" to: " << *V
1383 bool Killed =
false;
1403 if (SimpleValue::canHandle(&Inst)) {
1404 if (
auto *CI = dyn_cast<ConstrainedFPIntrinsic>(&Inst)) {
1406 "Unexpected ebStrict from SimpleValue::canHandle()");
1407 assert((!CI->getRoundingMode() ||
1408 CI->getRoundingMode() != RoundingMode::Dynamic) &&
1409 "Unexpected dynamic rounding from SimpleValue::canHandle()");
1412 if (
Value *V = AvailableValues.lookup(&Inst)) {
1419 if (
auto *
I = dyn_cast<Instruction>(V)) {
1427 I->andIRFlags(&Inst);
1439 AvailableValues.insert(&Inst, &Inst);
1443 ParseMemoryInst MemInst(&Inst,
TTI);
1445 if (MemInst.isValid() && MemInst.isLoad()) {
1448 if (MemInst.isVolatile() || !MemInst.isUnordered()) {
1449 LastStore =
nullptr;
1450 ++CurrentGeneration;
1453 if (MemInst.isInvariantLoad()) {
1460 if (!AvailableInvariants.count(MemLoc))
1461 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1471 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1472 if (
Value *Op = getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1474 <<
" to: " << *InVal.DefInst <<
'\n');
1490 AvailableLoads.insert(MemInst.getPointerOperand(),
1491 LoadValue(&Inst, CurrentGeneration,
1492 MemInst.getMatchingId(),
1493 MemInst.isAtomic()));
1494 LastStore =
nullptr;
1505 !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
1506 LastStore =
nullptr;
1509 if (CallValue::canHandle(&Inst)) {
1512 std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(&Inst);
1513 if (InVal.first !=
nullptr &&
1514 isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
1517 <<
" to: " << *InVal.first <<
'\n');
1533 AvailableCalls.insert(&Inst, std::make_pair(&Inst, CurrentGeneration));
1542 if (
auto *FI = dyn_cast<FenceInst>(&Inst))
1543 if (FI->getOrdering() == AtomicOrdering::Release) {
1553 if (MemInst.isValid() && MemInst.isStore()) {
1554 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1555 if (InVal.DefInst &&
1556 InVal.DefInst == getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1563 MemInst.getPointerOperand() ||
1565 "can't have an intervening store if not using MemorySSA!");
1566 LLVM_DEBUG(
dbgs() <<
"EarlyCSE DSE (writeback): " << Inst <<
'\n');
1586 ++CurrentGeneration;
1588 if (MemInst.isValid() && MemInst.isStore()) {
1592 if (overridingStores(ParseMemoryInst(LastStore,
TTI), MemInst)) {
1594 <<
" due to: " << Inst <<
'\n');
1599 removeMSSA(*LastStore);
1603 LastStore =
nullptr;
1614 AvailableLoads.insert(MemInst.getPointerOperand(),
1615 LoadValue(&Inst, CurrentGeneration,
1616 MemInst.getMatchingId(),
1617 MemInst.isAtomic()));
1626 if (MemInst.isUnordered() && !MemInst.isVolatile())
1629 LastStore =
nullptr;
1637bool EarlyCSE::run() {
1643 std::deque<StackNode *> nodesToProcess;
1645 bool Changed =
false;
1648 nodesToProcess.push_back(
new StackNode(
1649 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1653 assert(!CurrentGeneration &&
"Create a new EarlyCSE instance to rerun it.");
1656 while (!nodesToProcess.empty()) {
1659 StackNode *NodeToProcess = nodesToProcess.back();
1662 CurrentGeneration = NodeToProcess->currentGeneration();
1665 if (!NodeToProcess->isProcessed()) {
1667 Changed |= processNode(NodeToProcess->node());
1668 NodeToProcess->childGeneration(CurrentGeneration);
1669 NodeToProcess->process();
1670 }
else if (NodeToProcess->childIter() != NodeToProcess->end()) {
1673 nodesToProcess.push_back(
1674 new StackNode(AvailableValues, AvailableLoads, AvailableInvariants,
1675 AvailableCalls, NodeToProcess->childGeneration(),
1676 child, child->
begin(), child->
end()));
1680 delete NodeToProcess;
1681 nodesToProcess.pop_back();
1697 EarlyCSE
CSE(
F.getParent()->getDataLayout(), TLI,
TTI, DT, AC, MSSA);
1712 OS, MapClassName2PassName);
1728template<
bool UseMemorySSA>
1741 if (skipFunction(
F))
1744 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1745 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
1746 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1747 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1749 UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() :
nullptr;
1751 EarlyCSE
CSE(
F.getParent()->getDataLayout(), TLI,
TTI, DT, AC, MSSA);
1777char EarlyCSELegacyPass::ID = 0;
1787using EarlyCSEMemSSALegacyPass =
1788 EarlyCSELegacyCommonPass<
true>;
1791char EarlyCSEMemSSALegacyPass::
ID = 0;
1795 return new EarlyCSEMemSSALegacyPass();
1801 "Early CSE w/ MemorySSA",
false,
false)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static bool isLoad(int Opcode)
static bool isStore(int Opcode)
This file defines the BumpPtrAllocator interface.
Atomic ordering constants.
SmallVector< MachineOperand, 4 > Cond
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Analysis containing CSE Info
Optimize for code generation
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE)
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines DenseMapInfo traits for DenseMap.
std::optional< std::vector< StOtherPiece > > Other
static cl::opt< bool > EarlyCSEDebugHash("earlycse-debug-hash", cl::init(false), cl::Hidden, cl::desc("Perform extra assertion checking to verify that SimpleValue's hash " "function is well-behaved w.r.t. its isEqual predicate"))
EarlyCSELegacyCommonPass< false > EarlyCSELegacyPass
static unsigned getHashValueImpl(SimpleValue Val)
static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS)
static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond, Value *&A, Value *&B, SelectPatternFlavor &Flavor)
Match a 'select' including an optional 'not's of the condition.
static cl::opt< unsigned > EarlyCSEMssaOptCap("earlycse-mssa-optimization-cap", cl::init(500), cl::Hidden, cl::desc("Enable imprecision in EarlyCSE in pathological cases, in exchange " "for faster compile. Caps the MemorySSA clobbering calls."))
This file provides the interface for a simple, fast CSE pass.
static bool runOnFunction(Function &F, bool PostInlining)
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This is the interface for a simple mod/ref and alias analysis over globals.
static void cse(BasicBlock *BB)
Perform cse of induction variable instructions.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
separate const offset from Split GEPs to a variadic base and a constant offset for better CSE
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Conditional or Unconditional Branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
Represents analyses that only rely on functions' control flow.
bool onlyReadsMemory(unsigned OpNo) const
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Predicate getPredicate() const
Return the predicate for this instruction.
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
static bool shouldExecute(unsigned CounterName)
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
This class represents a freeze function that returns random concrete value if an operand is either a ...
FunctionPass class - This class is used to implement most global optimizations.
bool isPresplitCoroutine() const
Determine if the function is presplit coroutine.
Represents calls to the gc.relocate intrinsic.
Legacy wrapper pass to provide the GlobalsAAResult object.
This instruction inserts a struct field of array element value into an aggregate value.
bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
bool isIdenticalToWhenDefined(const Instruction *I) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
const Function * getFunction() const
Return the function this instruction belongs to.
bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
bool mayThrow() const LLVM_READONLY
Return true if this instruction may throw an exception.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
An instruction for reading from memory.
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static std::optional< MemoryLocation > getOrNone(const Instruction *Inst)
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
An analysis that produces MemorySSA for a function.
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Legacy analysis pass which computes MemorySSA.
Encapsulates MemorySSA, including all data associated with memory accesses.
bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
void preserve()
Mark an analysis as preserved.
RecyclingAllocator - This class wraps an Allocator, adding the functionality of recycling deleted obj...
ScopedHashTableScope< K, V, KInfo, AllocatorTy > ScopeTy
ScopeTy - This is a helpful typedef that allows clients to get easy access to the name of the scope f...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
StringRef - Represent a constant reference to a string, i.e.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isVoidTy() const
Return true if this is 'void'.
value_op_iterator value_op_end()
Value * getOperand(unsigned i) const
value_op_iterator value_op_begin()
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
StringRef getName() const
Return a constant reference to the value's name.
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ ebStrict
This corresponds to "fpexcept.strict".
Scope
Defines the scope in which this symbol should be visible: Default – Visible in the public interface o...
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
void initializeEarlyCSEMemSSALegacyPassPass(PassRegistry &)
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
SelectPatternFlavor
Specific patterns of select instructions we can match.
@ SPF_UMIN
Signed minimum.
@ SPF_UMAX
Signed maximum.
@ SPF_SMAX
Unsigned minimum.
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
bool programUndefinedIfPoison(const Instruction *Inst)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of 'From' with 'To' if that use is dominated by the given edge.
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
void initializeEarlyCSELegacyPassPass(PassRegistry &)
bool VerifyMemorySSA
Enables verification of MemorySSA.
bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
FunctionPass * createEarlyCSEPass(bool UseMemorySSA=false)
Type * getLoadStoreType(Value *I)
A helper function that returns the type of a load or store instruction.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static unsigned getHashValue(CallValue Val)
static CallValue getTombstoneKey()
static bool isEqual(CallValue LHS, CallValue RHS)
static CallValue getEmptyKey()
static SimpleValue getEmptyKey()
static unsigned getHashValue(SimpleValue Val)
static SimpleValue getTombstoneKey()
static bool isEqual(SimpleValue LHS, SimpleValue RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Information about a load/store intrinsic defined by the target.
A CRTP mix-in to automatically provide informational APIs needed for passes.