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(NumCSEGEP,
"Number of GEP instructions CSE'd");
71STATISTIC(NumDSE,
"Number of trivial dead stores removed");
74 "Controls which instructions are removed");
78 cl::desc(
"Enable imprecision in EarlyCSE in pathological cases, in exchange "
79 "for faster compile. Caps the MemorySSA clobbering calls."));
83 cl::desc(
"Perform extra assertion checking to verify that SimpleValue's hash "
84 "function is well-behaved w.r.t. its isEqual predicate"));
101 return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
102 Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
105 static bool canHandle(Instruction *Inst) {
110 if (Function *
F = CI->getCalledFunction()) {
112 case Intrinsic::experimental_constrained_fadd:
113 case Intrinsic::experimental_constrained_fsub:
114 case Intrinsic::experimental_constrained_fmul:
115 case Intrinsic::experimental_constrained_fdiv:
116 case Intrinsic::experimental_constrained_frem:
117 case Intrinsic::experimental_constrained_fptosi:
118 case Intrinsic::experimental_constrained_sitofp:
119 case Intrinsic::experimental_constrained_fptoui:
120 case Intrinsic::experimental_constrained_uitofp:
121 case Intrinsic::experimental_constrained_fcmp:
122 case Intrinsic::experimental_constrained_fcmps: {
124 if (CFP->getExceptionBehavior() &&
129 if (CFP->getRoundingMode() &&
130 CFP->getRoundingMode() == RoundingMode::Dynamic)
136 return CI->doesNotAccessMemory() &&
144 !CI->getFunction()->isPresplitCoroutine();
169 static bool isEqual(SimpleValue LHS, SimpleValue RHS);
239 if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
254 if (std::tie(
LHS, Pred) > std::tie(
RHS, SwappedPred)) {
296 return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
299 return hash_combine(FI->getOpcode(), FI->getOperand(0));
302 return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
306 return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
312 "Invalid/unknown instruction");
316 if (
II &&
II->isCommutative() &&
II->arg_size() >= 2) {
329 return hash_combine(GCR->getOpcode(), GCR->getOperand(0),
330 GCR->getBasePtr(), GCR->getDerivedPtr());
357 if (
LHS.isSentinel() ||
RHS.isSentinel())
360 if (LHSI->
getOpcode() != RHSI->getOpcode())
367 CI && CI->isConvergent() && LHSI->
getParent() != RHSI->getParent())
375 if (!LHSBinOp->isCommutative())
379 "same opcode, but different instruction type?");
383 return LHSBinOp->getOperand(0) == RHSBinOp->
getOperand(1) &&
384 LHSBinOp->getOperand(1) == RHSBinOp->
getOperand(0);
388 "same opcode, but different instruction type?");
391 return LHSCmp->getOperand(0) == RHSCmp->
getOperand(1) &&
392 LHSCmp->getOperand(1) == RHSCmp->
getOperand(0) &&
393 LHSCmp->getSwappedPredicate() == RHSCmp->
getPredicate();
398 if (LII && RII && LII->getIntrinsicID() == RII->getIntrinsicID() &&
399 LII->isCommutative() && LII->arg_size() >= 2) {
400 return LII->getArgOperand(0) == RII->getArgOperand(1) &&
401 LII->getArgOperand(1) == RII->getArgOperand(0) &&
402 std::equal(LII->arg_begin() + 2, LII->arg_end(),
403 RII->arg_begin() + 2, RII->arg_end()) &&
404 LII->hasSameSpecialState(RII,
false,
411 return GCR1->getOperand(0) == GCR2->getOperand(0) &&
412 GCR1->getBasePtr() == GCR2->getBasePtr() &&
413 GCR1->getDerivedPtr() == GCR2->getDerivedPtr();
419 Value *CondL, *CondR, *LHSA, *RHSA, *LHSB, *RHSB;
426 return ((LHSA == RHSA && LHSB == RHSB) ||
427 (LHSA == RHSB && LHSB == RHSA));
430 if (CondL == CondR && LHSA == RHSA && LHSB == RHSB)
452 if (LHSA == RHSB && LHSB == RHSA) {
485 CallValue(Instruction *
I) : Inst(
I) {
490 return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
491 Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
494 static bool canHandle(Instruction *Inst) {
524 static bool isEqual(CallValue LHS, CallValue RHS);
537 if (
LHS.isSentinel() ||
RHS.isSentinel())
538 return LHS.Inst ==
RHS.Inst;
560 std::optional<int64_t> ConstantOffset;
562 GEPValue(Instruction *
I) : Inst(
I) {
566 GEPValue(Instruction *
I, std::optional<int64_t> ConstantOffset)
567 : Inst(
I), ConstantOffset(ConstantOffset) {
572 return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
573 Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
576 static bool canHandle(Instruction *Inst) {
595 static bool isEqual(
const GEPValue &LHS,
const GEPValue &RHS);
602 if (Val.ConstantOffset.has_value())
604 Val.ConstantOffset.value());
610 if (
LHS.isSentinel() ||
RHS.isSentinel())
611 return LHS.Inst ==
RHS.Inst;
614 if (LGEP->getPointerOperand() != RGEP->getPointerOperand())
616 if (
LHS.ConstantOffset.has_value() &&
RHS.ConstantOffset.has_value())
617 return LHS.ConstantOffset.value() ==
RHS.ConstantOffset.value();
618 return LGEP->isIdenticalToWhenDefined(RGEP);
636 const TargetLibraryInfo &TLI;
637 const TargetTransformInfo &TTI;
640 const SimplifyQuery SQ;
642 std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
646 ScopedHashTableVal<SimpleValue, Value *>>;
648 ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,
657 ScopedHTType AvailableValues;
675 unsigned Generation = 0;
677 bool IsAtomic =
false;
680 LoadValue() =
default;
681 LoadValue(Instruction *Inst,
unsigned Generation,
unsigned MatchingId,
682 bool IsAtomic,
bool IsLoad)
683 : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
684 IsAtomic(IsAtomic), IsLoad(IsLoad) {}
687 using LoadMapAllocator =
689 ScopedHashTableVal<Value *, LoadValue>>;
691 ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
694 LoadHTType AvailableLoads;
699 using InvariantMapAllocator =
701 ScopedHashTableVal<MemoryLocation, unsigned>>;
702 using InvariantHTType =
703 ScopedHashTable<MemoryLocation, unsigned, DenseMapInfo<MemoryLocation>,
704 InvariantMapAllocator>;
705 InvariantHTType AvailableInvariants;
712 ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>;
713 CallHTType AvailableCalls;
715 using GEPMapAllocatorTy =
717 ScopedHashTableVal<GEPValue, Value *>>;
718 using GEPHTType = ScopedHashTable<GEPValue, Value *, DenseMapInfo<GEPValue>,
720 GEPHTType AvailableGEPs;
723 unsigned CurrentGeneration = 0;
726 EarlyCSE(
const DataLayout &
DL,
const TargetLibraryInfo &TLI,
727 const TargetTransformInfo &TTI, DominatorTree &DT,
729 : TLI(TLI), TTI(TTI), DT(DT), AC(AC), SQ(
DL, &TLI, &DT, &AC), MSSA(MSSA),
730 MSSAUpdater(std::make_unique<MemorySSAUpdater>(MSSA)) {}
735 unsigned ClobberCounter = 0;
741 NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
742 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,
743 GEPHTType &AvailableGEPs)
744 : Scope(AvailableValues), LoadScope(AvailableLoads),
745 InvariantScope(AvailableInvariants), CallScope(AvailableCalls),
746 GEPScope(AvailableGEPs) {}
747 NodeScope(
const NodeScope &) =
delete;
748 NodeScope &operator=(
const NodeScope &) =
delete;
764 StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
765 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,
766 GEPHTType &AvailableGEPs,
unsigned cg,
DomTreeNode *n,
769 : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
771 Scopes(AvailableValues, AvailableLoads, AvailableInvariants,
772 AvailableCalls, AvailableGEPs) {}
773 StackNode(
const StackNode &) =
delete;
774 StackNode &operator=(
const StackNode &) =
delete;
777 unsigned currentGeneration()
const {
return CurrentGeneration; }
778 unsigned childGeneration()
const {
return ChildGeneration; }
790 bool isProcessed()
const {
return Processed; }
791 void process() { Processed =
true; }
794 unsigned CurrentGeneration;
795 unsigned ChildGeneration;
800 bool Processed =
false;
805 class ParseMemoryInst {
807 ParseMemoryInst(Instruction *Inst,
const TargetTransformInfo &
TTI)
810 IntrID =
II->getIntrinsicID();
813 if (isHandledNonTargetIntrinsic(IntrID)) {
815 case Intrinsic::masked_load:
816 Info.PtrVal = Inst->getOperand(0);
817 Info.MatchingId = Intrinsic::masked_load;
819 Info.WriteMem =
false;
820 Info.IsVolatile =
false;
822 case Intrinsic::masked_store:
823 Info.PtrVal = Inst->getOperand(1);
830 Info.MatchingId = Intrinsic::masked_load;
831 Info.ReadMem =
false;
832 Info.WriteMem =
true;
833 Info.IsVolatile =
false;
851 return Info.WriteMem;
855 bool isAtomic()
const {
857 return Info.Ordering != AtomicOrdering::NotAtomic;
858 return Inst->isAtomic();
861 bool isUnordered()
const {
863 return Info.isUnordered();
866 return LI->isUnordered();
868 return SI->isUnordered();
871 return !Inst->isAtomic();
874 bool isVolatile()
const {
876 return Info.IsVolatile;
879 return LI->isVolatile();
881 return SI->isVolatile();
889 return LI->hasMetadata(LLVMContext::MD_invariant_load);
899 int getMatchingId()
const {
901 return Info.MatchingId;
913 return Inst->getAccessType();
916 bool mayReadFromMemory()
const {
919 return Inst->mayReadFromMemory();
922 bool mayWriteToMemory()
const {
924 return Info.WriteMem;
925 return Inst->mayWriteToMemory();
930 MemIntrinsicInfo Info;
938 case Intrinsic::masked_load:
939 case Intrinsic::masked_store:
944 static bool isHandledNonTargetIntrinsic(
const Value *V) {
946 return isHandledNonTargetIntrinsic(
II->getIntrinsicID());
952 bool handleBranchCondition(Instruction *CondInst,
const BranchInst *BI,
953 const BasicBlock *BB,
const BasicBlock *Pred);
956 unsigned CurrentGeneration);
958 bool overridingStores(
const ParseMemoryInst &Earlier,
959 const ParseMemoryInst &Later);
961 Value *getOrCreateResult(Instruction *Inst,
Type *ExpectedType,
962 bool CanCreate)
const {
967 switch (
II->getIntrinsicID()) {
968 case Intrinsic::masked_load:
971 case Intrinsic::masked_store:
972 V =
II->getOperand(0);
975 return TTI.getOrCreateResultFromMemIntrinsic(
II, ExpectedType,
982 return V->getType() == ExpectedType ?
V :
nullptr;
987 bool isOperatingOnInvariantMemAt(Instruction *
I,
unsigned GenAt);
989 bool isSameMemGeneration(
unsigned EarlierGeneration,
unsigned LaterGeneration,
990 Instruction *EarlierInst, Instruction *LaterInst);
992 bool isNonTargetIntrinsicMatch(
const IntrinsicInst *Earlier,
993 const IntrinsicInst *Later) {
994 auto IsSubmask = [](
const Value *Mask0,
const Value *Mask1) {
1004 if (Vec0->getType() != Vec1->getType())
1006 for (
int i = 0, e = Vec0->getNumOperands(); i != e; ++i) {
1007 Constant *Elem0 = Vec0->getOperand(i);
1008 Constant *Elem1 = Vec1->getOperand(i);
1010 if (Int0 && Int0->isZero())
1023 auto PtrOp = [](
const IntrinsicInst *
II) {
1024 if (
II->getIntrinsicID() == Intrinsic::masked_load)
1025 return II->getOperand(0);
1026 if (
II->getIntrinsicID() == Intrinsic::masked_store)
1027 return II->getOperand(1);
1030 auto MaskOp = [](
const IntrinsicInst *
II) {
1031 if (
II->getIntrinsicID() == Intrinsic::masked_load)
1032 return II->getOperand(2);
1033 if (
II->getIntrinsicID() == Intrinsic::masked_store)
1034 return II->getOperand(3);
1037 auto ThruOp = [](
const IntrinsicInst *
II) {
1038 if (
II->getIntrinsicID() == Intrinsic::masked_load)
1039 return II->getOperand(3);
1043 if (PtrOp(Earlier) != PtrOp(Later))
1050 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_load) {
1056 if (MaskOp(Earlier) == MaskOp(Later) && ThruOp(Earlier) == ThruOp(Later))
1060 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
1062 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_load) {
1067 if (!IsSubmask(MaskOp(Later), MaskOp(Earlier)))
1071 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_store) {
1075 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
1077 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_store) {
1082 return IsSubmask(MaskOp(Earlier), MaskOp(Later));
1087 void removeMSSA(Instruction &Inst) {
1091 MSSA->verifyMemorySSA();
1098 MSSAUpdater->removeMemoryAccess(&Inst,
true);
1120bool EarlyCSE::isSameMemGeneration(
unsigned EarlierGeneration,
1121 unsigned LaterGeneration,
1125 if (EarlierGeneration == LaterGeneration)
1149 MemoryAccess *LaterDef;
1154 LaterDef = LaterMA->getDefiningAccess();
1156 return MSSA->
dominates(LaterDef, EarlierMA);
1159bool EarlyCSE::isOperatingOnInvariantMemAt(Instruction *
I,
unsigned GenAt) {
1163 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1171 MemoryLocation MemLoc = *MemLocOpt;
1172 if (!AvailableInvariants.count(MemLoc))
1177 return AvailableInvariants.lookup(MemLoc) <= GenAt;
1180bool EarlyCSE::handleBranchCondition(Instruction *CondInst,
1181 const BranchInst *BI,
const BasicBlock *BB,
1182 const BasicBlock *Pred) {
1191 if (Opcode == Instruction::And &&
1194 else if (Opcode == Instruction::Or &&
1202 unsigned PropagateOpcode =
1203 (BI->
getSuccessor(0) == BB) ? Instruction::And : Instruction::Or;
1205 bool MadeChanges =
false;
1206 SmallVector<Instruction *, 4> WorkList;
1207 SmallPtrSet<Instruction *, 4> Visited;
1209 while (!WorkList.
empty()) {
1210 Instruction *Curr = WorkList.pop_back_val();
1212 AvailableValues.insert(Curr, TorF);
1213 LLVM_DEBUG(dbgs() <<
"EarlyCSE CVP: Add conditional value for '"
1214 << Curr->getName() <<
"' as " << *TorF <<
" in "
1215 << BB->getName() <<
"\n");
1216 if (!DebugCounter::shouldExecute(CSECounter)) {
1217 LLVM_DEBUG(dbgs() <<
"Skipping due to debug counter\n");
1220 if (unsigned Count = replaceDominatedUsesWith(Curr, TorF, DT,
1221 BasicBlockEdge(Pred, BB))) {
1228 if (MatchBinOp(Curr, PropagateOpcode,
LHS,
RHS))
1231 if (SimpleValue::canHandle(OPI) && Visited.
insert(OPI).second)
1238Value *EarlyCSE::getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
1239 unsigned CurrentGeneration) {
1240 if (InVal.DefInst ==
nullptr)
1242 if (InVal.MatchingId != MemInst.getMatchingId())
1245 if (MemInst.isVolatile() || !MemInst.isUnordered())
1248 if (MemInst.isLoad() && !InVal.IsAtomic && MemInst.isAtomic())
1254 bool MemInstMatching = !MemInst.isLoad();
1255 Instruction *Matching = MemInstMatching ? MemInst.get() : InVal.DefInst;
1262 ? getOrCreateResult(Matching,
Other->getType(),
false)
1264 if (MemInst.isStore() && InVal.DefInst != Result)
1268 bool MatchingNTI = isHandledNonTargetIntrinsic(Matching);
1269 bool OtherNTI = isHandledNonTargetIntrinsic(
Other);
1270 if (OtherNTI != MatchingNTI)
1272 if (OtherNTI && MatchingNTI) {
1278 if (!isOperatingOnInvariantMemAt(MemInst.get(), InVal.
Generation) &&
1279 !isSameMemGeneration(InVal.
Generation, CurrentGeneration, InVal.DefInst,
1284 Result = getOrCreateResult(Matching,
Other->getType(),
true);
1298 I->andIRFlags(&From);
1312 assert(
Success &&
"Failed to intersect attributes in callsites that "
1313 "passed identical check");
1319bool EarlyCSE::overridingStores(
const ParseMemoryInst &Earlier,
1320 const ParseMemoryInst &Later) {
1323 assert(Earlier.isUnordered() && !Earlier.isVolatile() &&
1324 "Violated invariant");
1325 if (Earlier.getPointerOperand() != Later.getPointerOperand())
1327 if (!Earlier.getValueType() || !Later.getValueType() ||
1328 Earlier.getValueType() != Later.getValueType())
1330 if (Earlier.getMatchingId() != Later.getMatchingId())
1337 if (!Earlier.isUnordered() || !Later.isUnordered())
1341 bool ENTI = isHandledNonTargetIntrinsic(Earlier.get());
1342 bool LNTI = isHandledNonTargetIntrinsic(Later.get());
1350 return ENTI == LNTI;
1364 ++CurrentGeneration;
1376 if (CondInst && SimpleValue::canHandle(CondInst))
1377 Changed |= handleBranchCondition(CondInst, BI, BB, Pred);
1413 if (CondI && SimpleValue::canHandle(CondI)) {
1418 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping assumption: " << Inst <<
'\n');
1425 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping noalias intrinsic: " << Inst
1432 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping sideeffect: " << Inst <<
'\n');
1438 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping pseudoprobe: " << Inst <<
'\n');
1459 MemoryLocation MemLoc =
1462 if (!AvailableInvariants.count(MemLoc))
1463 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1470 if (SimpleValue::canHandle(CondI)) {
1472 if (
auto *KnownCond = AvailableValues.lookup(CondI)) {
1477 <<
"EarlyCSE removing guard: " << Inst <<
'\n');
1496 LastStore =
nullptr;
1503 LLVM_DEBUG(
dbgs() <<
"EarlyCSE Simplify: " << Inst <<
" to: " << *V
1508 bool Killed =
false;
1530 LastStore =
nullptr;
1533 if (SimpleValue::canHandle(&Inst)) {
1536 "Unexpected ebStrict from SimpleValue::canHandle()");
1537 assert((!CI->getRoundingMode() ||
1538 CI->getRoundingMode() != RoundingMode::Dynamic) &&
1539 "Unexpected dynamic rounding from SimpleValue::canHandle()");
1542 if (
Value *V = AvailableValues.lookup(&Inst)) {
1560 AvailableValues.insert(&Inst, &Inst);
1564 ParseMemoryInst MemInst(&Inst,
TTI);
1566 if (MemInst.isValid() && MemInst.isLoad()) {
1569 if (MemInst.isVolatile() || !MemInst.isUnordered()) {
1570 LastStore =
nullptr;
1571 ++CurrentGeneration;
1574 if (MemInst.isInvariantLoad()) {
1581 if (!AvailableInvariants.count(MemLoc))
1582 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1592 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1595 <<
" to: " << *InVal.DefInst <<
'\n');
1614 AvailableLoads.insert(MemInst.getPointerOperand(),
1615 LoadValue(&Inst, CurrentGeneration,
1616 MemInst.getMatchingId(),
1619 LastStore =
nullptr;
1629 !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
1630 LastStore =
nullptr;
1636 if (CallValue::canHandle(&Inst) &&
1637 (!MemInst.isValid() || !MemInst.isStore()) && !
isa<MemSetInst>(&Inst)) {
1640 std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(&Inst);
1641 if (InVal.first !=
nullptr &&
1642 isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
1646 <<
" to: " << *InVal.first <<
'\n');
1665 ++CurrentGeneration;
1668 AvailableCalls.insert(&Inst, std::make_pair(&Inst, CurrentGeneration));
1673 if (GEPValue::canHandle(&Inst)) {
1676 GEPValue GEPVal(
GEP,
GEP->accumulateConstantOffset(SQ.
DL,
Offset)
1679 if (
Value *V = AvailableGEPs.lookup(GEPVal)) {
1680 LLVM_DEBUG(
dbgs() <<
"EarlyCSE CSE GEP: " << Inst <<
" to: " << *V
1693 AvailableGEPs.insert(GEPVal, &Inst);
1703 if (FI->getOrdering() == AtomicOrdering::Release) {
1713 if (MemInst.isValid() && MemInst.isStore()) {
1714 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1715 if (InVal.DefInst &&
1718 LLVM_DEBUG(
dbgs() <<
"EarlyCSE DSE (writeback): " << Inst <<
'\n');
1738 ++CurrentGeneration;
1740 if (MemInst.isValid() && MemInst.isStore()) {
1744 if (overridingStores(ParseMemoryInst(LastStore,
TTI), MemInst)) {
1746 <<
" due to: " << Inst <<
'\n');
1751 removeMSSA(*LastStore);
1755 LastStore =
nullptr;
1766 AvailableLoads.insert(MemInst.getPointerOperand(),
1767 LoadValue(&Inst, CurrentGeneration,
1768 MemInst.getMatchingId(),
1779 if (MemInst.isUnordered() && !MemInst.isVolatile())
1782 LastStore =
nullptr;
1790bool EarlyCSE::run() {
1796 std::deque<StackNode *> nodesToProcess;
1801 nodesToProcess.push_back(
new StackNode(
1802 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1803 AvailableGEPs, CurrentGeneration, DT.
getRootNode(),
1806 assert(!CurrentGeneration &&
"Create a new EarlyCSE instance to rerun it.");
1809 while (!nodesToProcess.empty()) {
1812 StackNode *NodeToProcess = nodesToProcess.back();
1823 }
else if (NodeToProcess->
childIter() != NodeToProcess->
end()) {
1826 nodesToProcess.push_back(
new StackNode(
1827 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1833 delete NodeToProcess;
1834 nodesToProcess.pop_back();
1850 EarlyCSE
CSE(
F.getDataLayout(), TLI,
TTI, DT, AC, MSSA);
1865 OS, MapClassName2PassName);
1881template<
bool UseMemorySSA>
1894 if (skipFunction(
F))
1897 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1898 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
1899 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1900 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1902 UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() :
nullptr;
1904 EarlyCSE
CSE(
F.getDataLayout(), TLI,
TTI, DT, AC, MSSA);
1909 void getAnalysisUsage(AnalysisUsage &AU)
const override {
1930char EarlyCSELegacyPass::ID = 0;
1940using EarlyCSEMemSSALegacyPass =
1941 EarlyCSELegacyCommonPass<
true>;
1944char EarlyCSEMemSSALegacyPass::
ID = 0;
1948 return new EarlyCSEMemSSALegacyPass();
1954 "Early CSE w/ MemorySSA",
false,
false)
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...
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.
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"))
static void combineIRFlags(Instruction &From, Value *To)
EarlyCSELegacyCommonPass< false > EarlyCSELegacyPass
early cse Early CSE w MemorySSA
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 unsigned hashCallInst(CallInst *CI)
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)
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.
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 LoadInst *LI, 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)
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
static Type * getValueType(Value *V)
Returns the type of the given value/instruction V.
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")
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
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.
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...
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
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.
@ 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 getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
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...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
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.
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)
StringRef - 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.
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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ 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.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
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.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ ebStrict
This corresponds to "fpexcept.strict".
@ Assume
Do not drop type tests (default).
NodeAddr< NodeBase * > Node
Context & getContext() const
friend class Instruction
Iterator for Instructions in a `BasicBlock.
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.
FunctionAddr VTableAddr Value
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 Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
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.
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)
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
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 VerifyMemorySSA
Enables verification of MemorySSA.
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.
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 CallValue getTombstoneKey()
static bool isEqual(CallValue LHS, CallValue RHS)
static CallValue getEmptyKey()
static bool isEqual(const GEPValue &LHS, const GEPValue &RHS)
static unsigned getHashValue(const GEPValue &Val)
static GEPValue getTombstoneKey()
static GEPValue 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...
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)
A CRTP mix-in to automatically provide informational APIs needed for passes.