64#define DEBUG_TYPE "early-cse"
66STATISTIC(NumSimplify,
"Number of instructions simplified or DCE'd");
68STATISTIC(NumCSECVP,
"Number of compare instructions CVP'd");
69STATISTIC(NumCSELoad,
"Number of load instructions CSE'd");
70STATISTIC(NumCSECall,
"Number of call instructions CSE'd");
71STATISTIC(NumCSEGEP,
"Number of GEP instructions CSE'd");
72STATISTIC(NumDSE,
"Number of trivial dead stores removed");
75 "Controls which instructions are removed");
88 assert(canHandle(
I) &&
"Inst can't be handled!");
91 static bool canHandle(Instruction *Inst) {
96 if (
Function *
F = CI->getCalledFunction()) {
97 switch (
F->getIntrinsicID()) {
98 case Intrinsic::experimental_constrained_fadd:
99 case Intrinsic::experimental_constrained_fsub:
100 case Intrinsic::experimental_constrained_fmul:
101 case Intrinsic::experimental_constrained_fdiv:
102 case Intrinsic::experimental_constrained_frem:
103 case Intrinsic::experimental_constrained_fptosi:
104 case Intrinsic::experimental_constrained_sitofp:
105 case Intrinsic::experimental_constrained_fptoui:
106 case Intrinsic::experimental_constrained_uitofp:
107 case Intrinsic::experimental_constrained_fcmp:
108 case Intrinsic::experimental_constrained_fcmps: {
110 if (CFP->getExceptionBehavior() &&
115 if (CFP->getRoundingMode() &&
116 CFP->getRoundingMode() == RoundingMode::Dynamic)
122 return CI->doesNotAccessMemory() &&
130 !CI->getFunction()->isPresplitCoroutine();
146 static bool isEqual(SimpleValue LHS, SimpleValue RHS);
183 if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
198 if (std::tie(
LHS,
Pred) > std::tie(
RHS, SwappedPred)) {
227 return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
230 return hash_combine(FI->getOpcode(), FI->getOperand(0));
233 return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
237 return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
244 "Invalid/unknown instruction");
248 if (
II &&
II->isCommutative() &&
II->arg_size() >= 2) {
261 return hash_combine(GCR->getOpcode(), GCR->getOperand(0),
262 GCR->getBasePtr(), GCR->getDerivedPtr());
289 if (LHSI->
getOpcode() != RHSI->getOpcode())
296 CI && CI->isConvergent() && LHSI->
getParent() != RHSI->getParent())
304 if (!LHSBinOp->isCommutative())
308 "same opcode, but different instruction type?");
312 return LHSBinOp->getOperand(0) == RHSBinOp->
getOperand(1) &&
313 LHSBinOp->getOperand(1) == RHSBinOp->
getOperand(0);
317 "same opcode, but different instruction type?");
320 return LHSCmp->getOperand(0) == RHSCmp->
getOperand(1) &&
321 LHSCmp->getOperand(1) == RHSCmp->
getOperand(0) &&
322 LHSCmp->getSwappedPredicate() == RHSCmp->
getPredicate();
327 if (LII &&
RII && LII->getIntrinsicID() ==
RII->getIntrinsicID() &&
328 LII->isCommutative() && LII->arg_size() >= 2) {
329 return LII->getArgOperand(0) ==
RII->getArgOperand(1) &&
330 LII->getArgOperand(1) ==
RII->getArgOperand(0) &&
331 std::equal(LII->arg_begin() + 2, LII->arg_end(),
332 RII->arg_begin() + 2,
RII->arg_end()) &&
333 LII->hasSameSpecialState(
RII,
false,
340 return GCR1->getOperand(0) == GCR2->getOperand(0) &&
341 GCR1->getBasePtr() == GCR2->getBasePtr() &&
342 GCR1->getDerivedPtr() == GCR2->getDerivedPtr();
345 Value *CondL, *CondR, *LHSA, *RHSA, *LHSB, *RHSB;
349 if (CondL == CondR && LHSA == RHSA && LHSB == RHSB)
360 if (LHSA == RHSB && LHSB == RHSA) {
392 CallValue(Instruction *
I) : Inst(
I) {
393 assert(canHandle(
I) &&
"Inst can't be handled!");
396 static bool canHandle(Instruction *Inst) {
416 static bool isEqual(CallValue LHS, CallValue RHS);
447 std::optional<int64_t> ConstantOffset;
449 GEPValue(Instruction *
I) : Inst(
I) {
450 assert(canHandle(
I) &&
"Inst can't be handled!");
453 GEPValue(Instruction *
I, std::optional<int64_t> ConstantOffset)
454 : Inst(
I), ConstantOffset(ConstantOffset) {
455 assert(canHandle(
I) &&
"Inst can't be handled!");
458 static bool canHandle(Instruction *Inst) {
467 static bool isEqual(
const GEPValue &LHS,
const GEPValue &RHS);
472 if (Val.ConstantOffset.has_value())
474 Val.ConstantOffset.value());
482 if (LGEP->getPointerOperand() != RGEP->getPointerOperand())
484 if (
LHS.ConstantOffset.has_value() &&
RHS.ConstantOffset.has_value())
485 return LHS.ConstantOffset.value() ==
RHS.ConstantOffset.value();
486 return LGEP->isIdenticalToWhenDefined(RGEP);
504 const ScalarOptions &Opts;
505 const TargetLibraryInfo &TLI;
506 const TargetTransformInfo &TTI;
509 const SimplifyQuery SQ;
511 std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
515 ScopedHashTableVal<SimpleValue, Value *>>;
517 ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,
526 ScopedHTType AvailableValues;
544 unsigned Generation = 0;
546 bool IsAtomic =
false;
549 LoadValue() =
default;
550 LoadValue(Instruction *Inst,
unsigned Generation,
unsigned MatchingId,
551 bool IsAtomic,
bool IsLoad)
552 : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
553 IsAtomic(IsAtomic), IsLoad(IsLoad) {}
556 using LoadMapAllocator =
558 ScopedHashTableVal<Value *, LoadValue>>;
560 ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
563 LoadHTType AvailableLoads;
568 using InvariantMapAllocator =
570 ScopedHashTableVal<MemoryLocation, unsigned>>;
571 using InvariantHTType =
572 ScopedHashTable<MemoryLocation, unsigned, DenseMapInfo<MemoryLocation>,
573 InvariantMapAllocator>;
574 InvariantHTType AvailableInvariants;
581 ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>;
582 CallHTType AvailableCalls;
584 using GEPMapAllocatorTy =
586 ScopedHashTableVal<GEPValue, Value *>>;
587 using GEPHTType = ScopedHashTable<GEPValue, Value *, DenseMapInfo<GEPValue>,
589 GEPHTType AvailableGEPs;
592 unsigned CurrentGeneration = 0;
595 EarlyCSE(
const ScalarOptions &Opts,
const DataLayout &
DL,
596 const TargetLibraryInfo &TLI,
const TargetTransformInfo &TTI,
597 DominatorTree &DT, AssumptionCache &AC,
MemorySSA *MSSA)
598 : Opts(Opts), TLI(TLI), TTI(TTI), DT(DT), AC(AC), SQ(
DL, &TLI, &DT, &AC),
599 MSSA(MSSA), MSSAUpdater(std::make_unique<MemorySSAUpdater>(MSSA)) {}
604 unsigned ClobberCounter = 0;
610 NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
611 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,
612 GEPHTType &AvailableGEPs)
613 : Scope(AvailableValues), LoadScope(AvailableLoads),
614 InvariantScope(AvailableInvariants), CallScope(AvailableCalls),
615 GEPScope(AvailableGEPs) {}
616 NodeScope(
const NodeScope &) =
delete;
617 NodeScope &operator=(
const NodeScope &) =
delete;
633 StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
634 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,
635 GEPHTType &AvailableGEPs,
unsigned cg,
DomTreeNode *n,
636 DomTreeNode::const_iterator child,
637 DomTreeNode::const_iterator end)
638 : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
640 Scopes(AvailableValues, AvailableLoads, AvailableInvariants,
641 AvailableCalls, AvailableGEPs) {}
642 StackNode(
const StackNode &) =
delete;
643 StackNode &operator=(
const StackNode &) =
delete;
646 unsigned currentGeneration()
const {
return CurrentGeneration; }
647 unsigned childGeneration()
const {
return ChildGeneration; }
650 DomTreeNode::const_iterator childIter()
const {
return ChildIter; }
658 DomTreeNode::const_iterator
end()
const {
return EndIter; }
659 bool isProcessed()
const {
return Processed; }
660 void process() { Processed =
true; }
663 unsigned CurrentGeneration;
664 unsigned ChildGeneration;
666 DomTreeNode::const_iterator ChildIter;
667 DomTreeNode::const_iterator EndIter;
669 bool Processed =
false;
674 class ParseMemoryInst {
676 ParseMemoryInst(Instruction *Inst,
const TargetTransformInfo &
TTI)
679 IntrID =
II->getIntrinsicID();
682 if (isHandledNonTargetIntrinsic(IntrID)) {
684 case Intrinsic::masked_load:
685 Info.PtrVal = Inst->getOperand(0);
686 Info.MatchingId = Intrinsic::masked_load;
688 Info.WriteMem =
false;
689 Info.IsVolatile =
false;
691 case Intrinsic::masked_store:
692 Info.PtrVal = Inst->getOperand(1);
699 Info.MatchingId = Intrinsic::masked_load;
700 Info.ReadMem =
false;
701 Info.WriteMem =
true;
702 Info.IsVolatile =
false;
706 Info.PtrVal =
MI->getDest();
708 Info.ReadMem =
false;
709 Info.WriteMem =
true;
710 Info.IsVolatile =
MI->isVolatile();
726 return Info.WriteMem;
732 return Info.Ordering != AtomicOrdering::NotAtomic;
733 return Inst->isAtomic();
736 bool isUnordered()
const {
738 return Info.isUnordered();
741 return LI->isUnordered();
743 return SI->isUnordered();
746 return !Inst->isAtomic();
749 bool isVolatile()
const {
751 return Info.IsVolatile;
754 return LI->isVolatile();
756 return SI->isVolatile();
764 return LI->hasMetadata(LLVMContext::MD_invariant_load);
774 int getMatchingId()
const {
776 return Info.MatchingId;
788 return Inst->getAccessType();
791 bool mayReadFromMemory()
const {
794 return Inst->mayReadFromMemory();
797 bool mayWriteToMemory()
const {
799 return Info.WriteMem;
800 return Inst->mayWriteToMemory();
805 MemIntrinsicInfo Info;
813 case Intrinsic::masked_load:
814 case Intrinsic::masked_store:
819 static bool isHandledNonTargetIntrinsic(
const Value *
V) {
821 return isHandledNonTargetIntrinsic(
II->getIntrinsicID());
827 bool handleBranchCondition(Instruction *CondInst,
const CondBrInst *BI,
828 const BasicBlock *BB,
const BasicBlock *
Pred);
831 unsigned CurrentGeneration);
833 bool overridingStores(
const ParseMemoryInst &Earlier,
834 const ParseMemoryInst &Later);
836 Value *getOrCreateResult(Instruction *Inst,
Type *ExpectedType,
837 bool CanCreate)
const {
842 switch (
II->getIntrinsicID()) {
843 case Intrinsic::masked_load:
846 case Intrinsic::masked_store:
847 V =
II->getOperand(0);
850 return TTI.getOrCreateResultFromMemIntrinsic(
II, ExpectedType,
857 return V->getType() == ExpectedType ?
V :
nullptr;
862 bool isOperatingOnInvariantMemAt(Instruction *
I,
unsigned GenAt);
864 bool isSameMemGeneration(
unsigned EarlierGeneration,
unsigned LaterGeneration,
865 Instruction *EarlierInst, Instruction *LaterInst);
867 bool isNonTargetIntrinsicMatch(
const IntrinsicInst *Earlier,
868 const IntrinsicInst *Later) {
869 auto IsSubmask = [](
const Value *Mask0,
const Value *Mask1) {
879 if (Vec0->getType() != Vec1->getType())
881 for (
int i = 0, e = Vec0->getNumOperands(); i != e; ++i) {
882 Constant *Elem0 = Vec0->getOperand(i);
883 Constant *Elem1 = Vec1->getOperand(i);
885 if (Int0 && Int0->isZero())
898 auto PtrOp = [](
const IntrinsicInst *
II) {
899 if (
II->getIntrinsicID() == Intrinsic::masked_load)
900 return II->getOperand(0);
901 if (
II->getIntrinsicID() == Intrinsic::masked_store)
902 return II->getOperand(1);
905 auto MaskOp = [](
const IntrinsicInst *
II) {
906 if (
II->getIntrinsicID() == Intrinsic::masked_load)
907 return II->getOperand(1);
908 if (
II->getIntrinsicID() == Intrinsic::masked_store)
909 return II->getOperand(2);
912 auto ThruOp = [](
const IntrinsicInst *
II) {
913 if (
II->getIntrinsicID() == Intrinsic::masked_load)
914 return II->getOperand(2);
918 if (PtrOp(Earlier) != PtrOp(Later))
925 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_load) {
931 if (MaskOp(Earlier) == MaskOp(Later) && ThruOp(Earlier) == ThruOp(Later))
935 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
937 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_load) {
942 if (!IsSubmask(MaskOp(Later), MaskOp(Earlier)))
946 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_store) {
950 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
952 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_store) {
957 return IsSubmask(MaskOp(Earlier), MaskOp(Later));
962 void removeMSSA(Instruction &Inst) {
966 MSSA->verifyMemorySSA();
973 MSSAUpdater->removeMemoryAccess(&Inst,
true);
995bool EarlyCSE::isSameMemGeneration(
unsigned EarlierGeneration,
996 unsigned LaterGeneration,
1000 if (EarlierGeneration == LaterGeneration)
1024 MemoryAccess *LaterDef;
1025 if (ClobberCounter < Opts.earlycse_mssa_optimization_cap) {
1029 LaterDef = LaterMA->getDefiningAccess();
1031 return MSSA->
dominates(LaterDef, EarlierMA);
1034bool EarlyCSE::isOperatingOnInvariantMemAt(Instruction *
I,
unsigned GenAt) {
1038 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1046 MemoryLocation MemLoc = *MemLocOpt;
1047 if (!AvailableInvariants.count(MemLoc))
1052 return AvailableInvariants.lookup(MemLoc) <= GenAt;
1055bool EarlyCSE::handleBranchCondition(Instruction *CondInst,
1056 const CondBrInst *BI,
const BasicBlock *BB,
1057 const BasicBlock *
Pred) {
1065 if (Opcode == Instruction::And &&
1068 else if (Opcode == Instruction::Or &&
1076 unsigned PropagateOpcode =
1077 (BI->
getSuccessor(0) == BB) ? Instruction::And : Instruction::Or;
1079 bool MadeChanges =
false;
1080 SmallVector<Instruction *, 4> WorkList;
1081 SmallPtrSet<Instruction *, 4> Visited;
1083 while (!WorkList.
empty()) {
1084 Instruction *Curr = WorkList.pop_back_val();
1086 AvailableValues.insert(Curr, TorF);
1087 LLVM_DEBUG(dbgs() <<
"EarlyCSE CVP: Add conditional value for '"
1088 << Curr->getName() <<
"' as " << *TorF <<
" in "
1089 << BB->getName() <<
"\n");
1090 if (!DebugCounter::shouldExecute(CSECounter)) {
1091 LLVM_DEBUG(dbgs() <<
"Skipping due to debug counter\n");
1094 if (unsigned Count = replaceDominatedUsesWith(Curr, TorF, DT,
1095 BasicBlockEdge(Pred, BB))) {
1102 if (MatchBinOp(Curr, PropagateOpcode,
LHS,
RHS))
1105 if (SimpleValue::canHandle(OPI) && Visited.
insert(OPI).second)
1112Value *EarlyCSE::getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
1113 unsigned CurrentGeneration) {
1114 if (InVal.DefInst ==
nullptr)
1117 if (!MemInst.isLoad() || MemInst.isVolatile() || !MemInst.isUnordered() ||
1118 MemInst.getMatchingId() != -1)
1120 if (MSI->isVolatile())
1123 if (!Val || !Val->isZero())
1125 auto Len = MSI->getLengthInBytes();
1128 Type *InstType = MemInst.getValueType();
1134 if (!isOperatingOnInvariantMemAt(MemInst.get(), InVal.
Generation) &&
1135 !isSameMemGeneration(InVal.
Generation, CurrentGeneration, InVal.DefInst,
1140 if (InVal.MatchingId != MemInst.getMatchingId())
1143 if (MemInst.isVolatile() || !MemInst.isUnordered())
1146 if (MemInst.isLoad() && !InVal.IsAtomic && MemInst.isAtomic())
1152 bool MemInstMatching = !MemInst.isLoad();
1153 Instruction *Matching = MemInstMatching ? MemInst.get() : InVal.DefInst;
1160 ? getOrCreateResult(Matching,
Other->getType(),
false)
1162 if (MemInst.isStore() && InVal.DefInst != Result)
1166 bool MatchingNTI = isHandledNonTargetIntrinsic(Matching);
1167 bool OtherNTI = isHandledNonTargetIntrinsic(
Other);
1168 if (OtherNTI != MatchingNTI)
1170 if (OtherNTI && MatchingNTI) {
1176 if (!isOperatingOnInvariantMemAt(MemInst.get(), InVal.
Generation) &&
1177 !isSameMemGeneration(InVal.
Generation, CurrentGeneration, InVal.DefInst,
1182 Result = getOrCreateResult(Matching,
Other->getType(),
true);
1196 I->andIRFlags(&From);
1210 assert(
Success &&
"Failed to intersect attributes in callsites that "
1211 "passed identical check");
1217bool EarlyCSE::overridingStores(
const ParseMemoryInst &Earlier,
1218 const ParseMemoryInst &Later) {
1221 assert(Earlier.isUnordered() && !Earlier.isVolatile() &&
1222 "Violated invariant");
1223 if (Earlier.getPointerOperand() != Later.getPointerOperand())
1225 if (!Earlier.getValueType() || !Later.getValueType() ||
1226 Earlier.getValueType() != Later.getValueType())
1228 if (Earlier.getMatchingId() != Later.getMatchingId())
1235 if (!Earlier.isUnordered() || !Later.isUnordered())
1239 bool ENTI = isHandledNonTargetIntrinsic(Earlier.get());
1240 bool LNTI = isHandledNonTargetIntrinsic(Later.get());
1248 return ENTI == LNTI;
1262 ++CurrentGeneration;
1273 if (CondInst && SimpleValue::canHandle(CondInst))
1274 Changed |= handleBranchCondition(CondInst, BI, BB,
Pred);
1310 if (CondI && SimpleValue::canHandle(CondI)) {
1315 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping assumption: " << Inst <<
'\n');
1322 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping noalias intrinsic: " << Inst
1329 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping sideeffect: " << Inst <<
'\n');
1335 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping pseudoprobe: " << Inst <<
'\n');
1356 MemoryLocation MemLoc =
1359 if (!AvailableInvariants.count(MemLoc))
1360 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1367 if (SimpleValue::canHandle(CondI)) {
1369 if (
auto *KnownCond = AvailableValues.lookup(CondI)) {
1374 <<
"EarlyCSE removing guard: " << Inst <<
'\n');
1393 LastStore =
nullptr;
1405 bool Killed =
false;
1427 LastStore =
nullptr;
1430 if (SimpleValue::canHandle(&Inst)) {
1433 "Unexpected ebStrict from SimpleValue::canHandle()");
1434 assert((!CI->getRoundingMode() ||
1435 CI->getRoundingMode() != RoundingMode::Dynamic) &&
1436 "Unexpected dynamic rounding from SimpleValue::canHandle()");
1439 if (
Value *
V = AvailableValues.lookup(&Inst)) {
1457 AvailableValues.insert(&Inst, &Inst);
1461 ParseMemoryInst MemInst(&Inst,
TTI);
1463 if (MemInst.isValid() && MemInst.isLoad()) {
1466 if (MemInst.isVolatile() || !MemInst.isUnordered()) {
1467 LastStore =
nullptr;
1468 ++CurrentGeneration;
1471 if (MemInst.isInvariantLoad()) {
1478 if (!AvailableInvariants.count(MemLoc))
1479 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1489 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1492 <<
" to: " << *InVal.DefInst <<
'\n');
1511 AvailableLoads.insert(MemInst.getPointerOperand(),
1512 LoadValue(&Inst, CurrentGeneration,
1513 MemInst.getMatchingId(),
1516 LastStore =
nullptr;
1526 !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
1527 LastStore =
nullptr;
1533 if (CallValue::canHandle(&Inst) &&
1534 (!MemInst.isValid() || !MemInst.isStore()) && !
isa<MemSetInst>(&Inst)) {
1537 std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(&Inst);
1538 if (InVal.first !=
nullptr &&
1539 isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
1543 <<
" to: " << *InVal.first <<
'\n');
1562 ++CurrentGeneration;
1565 AvailableCalls.insert(&Inst, std::make_pair(&Inst, CurrentGeneration));
1570 if (GEPValue::canHandle(&Inst)) {
1573 GEPValue GEPVal(
GEP,
GEP->accumulateConstantOffset(SQ.
DL,
Offset)
1576 if (
Value *
V = AvailableGEPs.lookup(GEPVal)) {
1590 AvailableGEPs.insert(GEPVal, &Inst);
1600 if (FI->getOrdering() == AtomicOrdering::Release) {
1610 if (MemInst.isValid() && MemInst.isStore()) {
1611 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1612 if (InVal.DefInst &&
1615 LLVM_DEBUG(
dbgs() <<
"EarlyCSE DSE (writeback): " << Inst <<
'\n');
1635 ++CurrentGeneration;
1637 if (MemInst.isValid() && MemInst.isStore()) {
1641 if (overridingStores(ParseMemoryInst(LastStore,
TTI), MemInst)) {
1643 <<
" due to: " << Inst <<
'\n');
1648 removeMSSA(*LastStore);
1652 LastStore =
nullptr;
1663 AvailableLoads.insert(MemInst.getPointerOperand(),
1664 LoadValue(&Inst, CurrentGeneration,
1665 MemInst.getMatchingId(),
1676 if (MemInst.isUnordered() && !MemInst.isVolatile())
1679 LastStore =
nullptr;
1687bool EarlyCSE::run() {
1693 std::deque<StackNode *> nodesToProcess;
1698 nodesToProcess.push_back(
new StackNode(
1699 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1700 AvailableGEPs, CurrentGeneration, DT.
getRootNode(),
1703 assert(!CurrentGeneration &&
"Create a new EarlyCSE instance to rerun it.");
1706 while (!nodesToProcess.empty()) {
1709 StackNode *NodeToProcess = nodesToProcess.back();
1720 }
else if (NodeToProcess->
childIter() != NodeToProcess->
end()) {
1723 nodesToProcess.push_back(
new StackNode(
1724 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1730 delete NodeToProcess;
1731 nodesToProcess.pop_back();
1761 static_cast<PassInfoMixin<EarlyCSEPass> *
>(
this)->
printPipeline(
1762 OS, MapClassName2PassName);
1778template<
bool UseMemorySSA>
1791 if (skipFunction(
F))
1794 auto &
TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1795 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
1796 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1797 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1799 UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() :
nullptr;
1807 void getAnalysisUsage(AnalysisUsage &AU)
const override {
1828char EarlyCSELegacyPass::ID = 0;
1838using EarlyCSEMemSSALegacyPass =
1839 EarlyCSELegacyCommonPass<
true>;
1842char EarlyCSEMemSSALegacyPass::ID = 0;
1846 return new EarlyCSEMemSSALegacyPass();
1852 "Early CSE w/ MemorySSA",
false,
false)
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static bool isLoad(int Opcode)
static bool isStore(int Opcode)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file defines the BumpPtrAllocator interface.
Atomic ordering constants.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Optimize for code generation
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines DenseMapInfo traits for DenseMap.
static void combineIRFlags(Instruction &From, Value *To)
EarlyCSELegacyCommonPass< false > EarlyCSELegacyPass
static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond, Value *&A, Value *&B)
Match a 'select' including an optional 'not's of the condition.
early cse Early CSE w MemorySSA
static unsigned getHashValueImpl(SimpleValue Val)
static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS)
static unsigned hashCallInst(CallInst *CI)
This file provides the interface for a simple, fast CSE pass.
static bool runOnFunction(Function &F, bool PostInlining)
This is the interface for a simple mod/ref and alias analysis over globals.
This header defines various interfaces for pass management in LLVM.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
static bool isAtomic(MachineBasicBlock::iterator I)
Value * getMatchingValue(LoadValue LV, LoadInst *LI, unsigned CurrentGeneration, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
static bool isInvariantLoad(const Instruction *I, const Value *Ptr, const bool IsKernelFn)
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
SmallVector< MachineOperand, 4 > Cond
const RISCVInstrInfo * RII
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Func getContext().diagnose(DiagnosticInfoUnsupported(Func
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)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
unsigned currentGeneration() const
unsigned childGeneration() const
DomTreeNode::const_iterator end() const
DomTreeNode * nextChild()
DomTreeNode::const_iterator childIter() const
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM_ABI 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.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
Represents analyses that only rely on functions' control flow.
bool onlyWritesMemory(unsigned OpNo) const
bool onlyReadsMemory(unsigned OpNo) const
bool isConvergent() const
Determine if the invoke is convergent.
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.
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.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
TypeSize getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type.
static bool shouldExecute(CounterInfo &Counter)
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.
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.
This instruction inserts a struct field of array element value into an aggregate value.
LLVM_ABI bool mayThrow(bool IncludePhaseOneUnwind=false) const LLVM_READONLY
Return true if this instruction may throw an exception.
LLVM_ABI bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static LLVM_ABI std::optional< MemoryLocation > getOrNone(const Instruction *Inst)
static LLVM_ABI 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.
LLVM_ABI bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
LLVM_ABI MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
static LLVM_ABI 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.
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
PreservedAnalyses & preserve()
Mark an analysis as preserved.
ScopedHashTableScope< SimpleValue, Value *, DenseMapInfo< SimpleValue >, AllocatorTy > ScopeTy
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
void push_back(const T &Elt)
Represent a constant reference to a string, i.e.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Value * getOperand(unsigned i) const
iterator_range< value_op_iterator > operand_values()
LLVM Value Representation.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
constexpr ScalarTy getFixedValue() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
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.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
auto m_Cmp()
Matches any compare instruction and ignore it.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ ebStrict
This corresponds to "fpexcept.strict".
NodeAddr< NodeBase * > Node
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Type * getValueType(Value *V, bool ReVec, bool LookThroughCmp)
Returns the "element type" of the given value/instruction V.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI 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...
const ScalarOptions & getScalarOptions(const LLVMContext &C)
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
LLVM_ABI void initializeEarlyCSEMemSSALegacyPassPass(PassRegistry &)
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
DomTreeNodeBase< BasicBlock > DomTreeNode
LLVM_ABI 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.
LLVM_ABI bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
LLVM_ABI bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
LLVM_ABI FunctionPass * createEarlyCSEPass(bool UseMemorySSA=false)
LLVM_ABI void initializeEarlyCSELegacyPassPass(PassRegistry &)
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 bool isEqual(CallValue LHS, CallValue RHS)
static bool isEqual(const GEPValue &LHS, const GEPValue &RHS)
static unsigned getHashValue(const GEPValue &Val)
static unsigned getHashValue(SimpleValue Val)
static bool isEqual(SimpleValue LHS, SimpleValue RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)