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());
350 if (
LHS.isSentinel() ||
RHS.isSentinel())
353 if (LHSI->
getOpcode() != RHSI->getOpcode())
359 if (
CallInst *CI = dyn_cast<CallInst>(LHSI);
368 if (!LHSBinOp->isCommutative())
371 assert(isa<BinaryOperator>(RHSI) &&
372 "same opcode, but different instruction type?");
376 return LHSBinOp->getOperand(0) == RHSBinOp->
getOperand(1) &&
377 LHSBinOp->getOperand(1) == RHSBinOp->
getOperand(0);
379 if (
CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
380 assert(isa<CmpInst>(RHSI) &&
381 "same opcode, but different instruction type?");
382 CmpInst *RHSCmp = cast<CmpInst>(RHSI);
384 return LHSCmp->getOperand(0) == RHSCmp->
getOperand(1) &&
385 LHSCmp->getOperand(1) == RHSCmp->
getOperand(0) &&
386 LHSCmp->getSwappedPredicate() == RHSCmp->
getPredicate();
390 auto *LII = dyn_cast<IntrinsicInst>(LHSI);
391 auto *RII = dyn_cast<IntrinsicInst>(RHSI);
392 if (LII && RII && LII->getIntrinsicID() == RII->getIntrinsicID() &&
393 LII->isCommutative() && LII->arg_size() == 2) {
394 return LII->getArgOperand(0) == RII->getArgOperand(1) &&
395 LII->getArgOperand(1) == RII->getArgOperand(0);
401 return GCR1->getOperand(0) == GCR2->getOperand(0) &&
402 GCR1->getBasePtr() == GCR2->getBasePtr() &&
403 GCR1->getDerivedPtr() == GCR2->getDerivedPtr();
409 Value *CondL, *CondR, *LHSA, *RHSA, *LHSB, *RHSB;
416 return ((LHSA == RHSA && LHSB == RHSB) ||
417 (LHSA == RHSB && LHSB == RHSA));
420 if (CondL == CondR && LHSA == RHSA && LHSB == RHSB)
442 if (LHSA == RHSB && LHSB == RHSA) {
489 CallInst *CI = dyn_cast<CallInst>(Inst);
518 static bool isEqual(CallValue LHS, CallValue RHS);
534 if (
LHS.isSentinel() ||
RHS.isSentinel())
561 std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
576 ScopedHTType AvailableValues;
594 unsigned Generation = 0;
596 bool IsAtomic =
false;
599 LoadValue() =
default;
600 LoadValue(
Instruction *Inst,
unsigned Generation,
unsigned MatchingId,
601 bool IsAtomic,
bool IsLoad)
602 : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
603 IsAtomic(IsAtomic), IsLoad(IsLoad) {}
606 using LoadMapAllocator =
613 LoadHTType AvailableLoads;
618 using InvariantMapAllocator =
621 using InvariantHTType =
623 InvariantMapAllocator>;
624 InvariantHTType AvailableInvariants;
632 CallHTType AvailableCalls;
635 unsigned CurrentGeneration = 0;
641 : TLI(TLI),
TTI(
TTI), DT(DT), AC(AC), SQ(
DL, &TLI, &DT, &AC), MSSA(MSSA),
647 unsigned ClobberCounter = 0;
653 NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
654 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls)
655 :
Scope(AvailableValues), LoadScope(AvailableLoads),
656 InvariantScope(AvailableInvariants), CallScope(AvailableCalls) {}
657 NodeScope(
const NodeScope &) =
delete;
658 NodeScope &operator=(
const NodeScope &) =
delete;
673 StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
674 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,
677 : CurrentGeneration(cg), ChildGeneration(cg),
Node(n), ChildIter(child),
679 Scopes(AvailableValues, AvailableLoads, AvailableInvariants,
682 StackNode(
const StackNode &) =
delete;
683 StackNode &operator=(
const StackNode &) =
delete;
686 unsigned currentGeneration()
const {
return CurrentGeneration; }
687 unsigned childGeneration()
const {
return ChildGeneration; }
699 bool isProcessed()
const {
return Processed; }
700 void process() { Processed =
true; }
703 unsigned CurrentGeneration;
704 unsigned ChildGeneration;
709 bool Processed =
false;
714 class ParseMemoryInst {
719 IntrID = II->getIntrinsicID();
722 if (isHandledNonTargetIntrinsic(IntrID)) {
724 case Intrinsic::masked_load:
726 Info.MatchingId = Intrinsic::masked_load;
728 Info.WriteMem =
false;
729 Info.IsVolatile =
false;
731 case Intrinsic::masked_store:
739 Info.MatchingId = Intrinsic::masked_load;
740 Info.ReadMem =
false;
741 Info.WriteMem =
true;
742 Info.IsVolatile =
false;
755 return isa<LoadInst>(Inst);
760 return Info.WriteMem;
761 return isa<StoreInst>(Inst);
764 bool isAtomic()
const {
766 return Info.Ordering != AtomicOrdering::NotAtomic;
770 bool isUnordered()
const {
772 return Info.isUnordered();
774 if (
LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
775 return LI->isUnordered();
776 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
777 return SI->isUnordered();
783 bool isVolatile()
const {
785 return Info.IsVolatile;
787 if (
LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
788 return LI->isVolatile();
789 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
790 return SI->isVolatile();
796 bool isInvariantLoad()
const {
797 if (
auto *LI = dyn_cast<LoadInst>(Inst))
798 return LI->hasMetadata(LLVMContext::MD_invariant_load);
808 int getMatchingId()
const {
810 return Info.MatchingId;
820 Type *getValueType()
const {
823 switch (II->getIntrinsicID()) {
824 case Intrinsic::masked_load:
825 return II->getType();
826 case Intrinsic::masked_store:
827 return II->getArgOperand(0)->getType();
835 bool mayReadFromMemory()
const {
841 bool mayWriteToMemory()
const {
843 return Info.WriteMem;
857 case Intrinsic::masked_load:
858 case Intrinsic::masked_store:
863 static bool isHandledNonTargetIntrinsic(
const Value *V) {
864 if (
auto *II = dyn_cast<IntrinsicInst>(V))
865 return isHandledNonTargetIntrinsic(II->getIntrinsicID());
874 Value *getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
875 unsigned CurrentGeneration);
877 bool overridingStores(
const ParseMemoryInst &Earlier,
878 const ParseMemoryInst &Later);
882 if (
auto *LI = dyn_cast<LoadInst>(Inst))
883 return LI->
getType() == ExpectedType ? LI :
nullptr;
884 if (
auto *SI = dyn_cast<StoreInst>(Inst)) {
886 return V->getType() == ExpectedType ?
V :
nullptr;
888 assert(isa<IntrinsicInst>(Inst) &&
"Instruction not supported");
889 auto *II = cast<IntrinsicInst>(Inst);
890 if (isHandledNonTargetIntrinsic(II->getIntrinsicID()))
891 return getOrCreateResultNonTargetMemIntrinsic(II, ExpectedType);
896 Type *ExpectedType)
const {
899 case Intrinsic::masked_load:
900 return II->
getType() == ExpectedType ? II :
nullptr;
901 case Intrinsic::masked_store: {
903 return V->getType() == ExpectedType ?
V :
nullptr;
911 bool isOperatingOnInvariantMemAt(
Instruction *
I,
unsigned GenAt);
913 bool isSameMemGeneration(
unsigned EarlierGeneration,
unsigned LaterGeneration,
918 auto IsSubmask = [](
const Value *Mask0,
const Value *Mask1) {
922 if (isa<UndefValue>(Mask0) || isa<UndefValue>(Mask1))
924 auto *Vec0 = dyn_cast<ConstantVector>(Mask0);
925 auto *Vec1 = dyn_cast<ConstantVector>(Mask1);
928 if (Vec0->getType() != Vec1->getType())
930 for (
int i = 0, e = Vec0->getNumOperands(); i != e; ++i) {
933 auto *Int0 = dyn_cast<ConstantInt>(Elem0);
934 if (Int0 && Int0->isZero())
936 auto *
Int1 = dyn_cast<ConstantInt>(Elem1);
939 if (isa<UndefValue>(Elem0) || isa<UndefValue>(Elem1))
967 if (PtrOp(Earlier) != PtrOp(Later))
974 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_load) {
980 if (MaskOp(Earlier) == MaskOp(Later) && ThruOp(Earlier) == ThruOp(Later))
982 if (!isa<UndefValue>(ThruOp(Later)))
984 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
986 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_load) {
991 if (!IsSubmask(MaskOp(Later), MaskOp(Earlier)))
993 return isa<UndefValue>(ThruOp(Later));
995 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_store) {
999 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
1001 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_store) {
1006 return IsSubmask(MaskOp(Earlier), MaskOp(Later));
1022 MSSAUpdater->removeMemoryAccess(&Inst,
true);
1044bool EarlyCSE::isSameMemGeneration(
unsigned EarlierGeneration,
1045 unsigned LaterGeneration,
1049 if (EarlierGeneration == LaterGeneration)
1078 LaterDef = LaterMA->getDefiningAccess();
1080 return MSSA->
dominates(LaterDef, EarlierMA);
1083bool EarlyCSE::isOperatingOnInvariantMemAt(
Instruction *
I,
unsigned GenAt) {
1086 if (
auto *LI = dyn_cast<LoadInst>(
I))
1087 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1096 if (!AvailableInvariants.count(MemLoc))
1101 return AvailableInvariants.lookup(MemLoc) <= GenAt;
1104bool EarlyCSE::handleBranchCondition(
Instruction *CondInst,
1115 if (Opcode == Instruction::And &&
1118 else if (Opcode == Instruction::Or &&
1126 unsigned PropagateOpcode =
1127 (BI->
getSuccessor(0) == BB) ? Instruction::And : Instruction::Or;
1129 bool MadeChanges =
false;
1133 while (!WorkList.
empty()) {
1136 AvailableValues.insert(Curr, TorF);
1138 << Curr->
getName() <<
"' as " << *TorF <<
" in "
1152 if (MatchBinOp(Curr, PropagateOpcode, LHS, RHS))
1153 for (
auto *Op : {
LHS,
RHS })
1155 if (SimpleValue::canHandle(OPI) && Visited.
insert(OPI).second)
1162Value *EarlyCSE::getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
1163 unsigned CurrentGeneration) {
1164 if (InVal.DefInst ==
nullptr)
1166 if (InVal.MatchingId != MemInst.getMatchingId())
1169 if (MemInst.isVolatile() || !MemInst.isUnordered())
1172 if (MemInst.isLoad() && !InVal.IsAtomic && MemInst.isAtomic())
1178 bool MemInstMatching = !MemInst.isLoad();
1179 Instruction *Matching = MemInstMatching ? MemInst.get() : InVal.DefInst;
1185 ? getOrCreateResult(Matching,
Other->getType())
1187 if (MemInst.isStore() && InVal.DefInst != Result)
1191 bool MatchingNTI = isHandledNonTargetIntrinsic(Matching);
1192 bool OtherNTI = isHandledNonTargetIntrinsic(
Other);
1193 if (OtherNTI != MatchingNTI)
1195 if (OtherNTI && MatchingNTI) {
1196 if (!isNonTargetIntrinsicMatch(cast<IntrinsicInst>(InVal.DefInst),
1197 cast<IntrinsicInst>(MemInst.get())))
1201 if (!isOperatingOnInvariantMemAt(MemInst.get(), InVal.Generation) &&
1202 !isSameMemGeneration(InVal.Generation, CurrentGeneration, InVal.DefInst,
1207 Result = getOrCreateResult(Matching,
Other->getType());
1211bool EarlyCSE::overridingStores(
const ParseMemoryInst &Earlier,
1212 const ParseMemoryInst &Later) {
1215 assert(Earlier.isUnordered() && !Earlier.isVolatile() &&
1216 "Violated invariant");
1217 if (Earlier.getPointerOperand() != Later.getPointerOperand())
1219 if (!Earlier.getValueType() || !Later.getValueType() ||
1220 Earlier.getValueType() != Later.getValueType())
1222 if (Earlier.getMatchingId() != Later.getMatchingId())
1229 if (!Earlier.isUnordered() || !Later.isUnordered())
1233 bool ENTI = isHandledNonTargetIntrinsic(Earlier.get());
1234 bool LNTI = isHandledNonTargetIntrinsic(Later.get());
1236 return isNonTargetIntrinsicMatch(cast<IntrinsicInst>(Earlier.get()),
1237 cast<IntrinsicInst>(Later.get()));
1242 return ENTI == LNTI;
1246 bool Changed =
false;
1256 ++CurrentGeneration;
1267 auto *CondInst = dyn_cast<Instruction>(BI->
getCondition());
1268 if (CondInst && SimpleValue::canHandle(CondInst))
1269 Changed |= handleBranchCondition(CondInst, BI, BB, Pred);
1303 if (
auto *Assume = dyn_cast<AssumeInst>(&Inst)) {
1304 auto *CondI = dyn_cast<Instruction>(Assume->getArgOperand(0));
1305 if (CondI && SimpleValue::canHandle(CondI)) {
1310 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping assumption: " << Inst <<
'\n');
1316 m_Intrinsic<Intrinsic::experimental_noalias_scope_decl>())) {
1317 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping noalias intrinsic: " << Inst
1323 if (
match(&Inst, m_Intrinsic<Intrinsic::sideeffect>())) {
1324 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping sideeffect: " << Inst <<
'\n');
1329 if (
match(&Inst, m_Intrinsic<Intrinsic::pseudoprobe>())) {
1330 LLVM_DEBUG(
dbgs() <<
"EarlyCSE skipping pseudoprobe: " << Inst <<
'\n');
1347 if (
match(&Inst, m_Intrinsic<Intrinsic::invariant_start>())) {
1354 if (!AvailableInvariants.count(MemLoc))
1355 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1361 dyn_cast<Instruction>(cast<CallInst>(Inst).getArgOperand(0))) {
1362 if (SimpleValue::canHandle(CondI)) {
1364 if (
auto *KnownCond = AvailableValues.lookup(CondI)) {
1366 if (isa<ConstantInt>(KnownCond) &&
1367 cast<ConstantInt>(KnownCond)->isOne()) {
1369 <<
"EarlyCSE removing guard: " << Inst <<
'\n');
1377 cast<CallInst>(Inst).setArgOperand(0, KnownCond);
1388 LastStore =
nullptr;
1395 LLVM_DEBUG(
dbgs() <<
"EarlyCSE Simplify: " << Inst <<
" to: " << *V
1400 bool Killed =
false;
1420 if (SimpleValue::canHandle(&Inst)) {
1421 if (
auto *CI = dyn_cast<ConstrainedFPIntrinsic>(&Inst)) {
1423 "Unexpected ebStrict from SimpleValue::canHandle()");
1424 assert((!CI->getRoundingMode() ||
1425 CI->getRoundingMode() != RoundingMode::Dynamic) &&
1426 "Unexpected dynamic rounding from SimpleValue::canHandle()");
1429 if (
Value *V = AvailableValues.lookup(&Inst)) {
1436 if (
auto *
I = dyn_cast<Instruction>(V)) {
1444 I->andIRFlags(&Inst);
1456 AvailableValues.insert(&Inst, &Inst);
1460 ParseMemoryInst MemInst(&Inst,
TTI);
1462 if (MemInst.isValid() && MemInst.isLoad()) {
1465 if (MemInst.isVolatile() || !MemInst.isUnordered()) {
1466 LastStore =
nullptr;
1467 ++CurrentGeneration;
1470 if (MemInst.isInvariantLoad()) {
1477 if (!AvailableInvariants.count(MemLoc))
1478 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1488 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1489 if (
Value *Op = getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1491 <<
" to: " << *InVal.DefInst <<
'\n');
1497 if (
auto *
I = dyn_cast<Instruction>(Op))
1510 AvailableLoads.insert(MemInst.getPointerOperand(),
1511 LoadValue(&Inst, CurrentGeneration,
1512 MemInst.getMatchingId(),
1515 LastStore =
nullptr;
1526 !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
1527 LastStore =
nullptr;
1530 if (CallValue::canHandle(&Inst)) {
1533 std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(&Inst);
1534 if (InVal.first !=
nullptr &&
1535 isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
1538 <<
" to: " << *InVal.first <<
'\n');
1554 AvailableCalls.insert(&Inst, std::make_pair(&Inst, CurrentGeneration));
1563 if (
auto *FI = dyn_cast<FenceInst>(&Inst))
1564 if (FI->getOrdering() == AtomicOrdering::Release) {
1574 if (MemInst.isValid() && MemInst.isStore()) {
1575 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1576 if (InVal.DefInst &&
1577 InVal.DefInst == getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1584 MemInst.getPointerOperand() ||
1586 "can't have an intervening store if not using MemorySSA!");
1587 LLVM_DEBUG(
dbgs() <<
"EarlyCSE DSE (writeback): " << Inst <<
'\n');
1607 ++CurrentGeneration;
1609 if (MemInst.isValid() && MemInst.isStore()) {
1613 if (overridingStores(ParseMemoryInst(LastStore,
TTI), MemInst)) {
1615 <<
" due to: " << Inst <<
'\n');
1620 removeMSSA(*LastStore);
1624 LastStore =
nullptr;
1635 AvailableLoads.insert(MemInst.getPointerOperand(),
1636 LoadValue(&Inst, CurrentGeneration,
1637 MemInst.getMatchingId(),
1648 if (MemInst.isUnordered() && !MemInst.isVolatile())
1651 LastStore =
nullptr;
1659bool EarlyCSE::run() {
1665 std::deque<StackNode *> nodesToProcess;
1667 bool Changed =
false;
1670 nodesToProcess.push_back(
new StackNode(
1671 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1675 assert(!CurrentGeneration &&
"Create a new EarlyCSE instance to rerun it.");
1678 while (!nodesToProcess.empty()) {
1681 StackNode *NodeToProcess = nodesToProcess.back();
1684 CurrentGeneration = NodeToProcess->currentGeneration();
1687 if (!NodeToProcess->isProcessed()) {
1689 Changed |= processNode(NodeToProcess->node());
1690 NodeToProcess->childGeneration(CurrentGeneration);
1691 NodeToProcess->process();
1692 }
else if (NodeToProcess->childIter() != NodeToProcess->end()) {
1695 nodesToProcess.push_back(
1696 new StackNode(AvailableValues, AvailableLoads, AvailableInvariants,
1697 AvailableCalls, NodeToProcess->childGeneration(),
1698 child, child->
begin(), child->
end()));
1702 delete NodeToProcess;
1703 nodesToProcess.pop_back();
1719 EarlyCSE
CSE(
F.getParent()->getDataLayout(), TLI,
TTI, DT, AC, MSSA);
1734 OS, MapClassName2PassName);
1750template<
bool UseMemorySSA>
1763 if (skipFunction(
F))
1766 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1767 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
1768 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1769 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1771 UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() :
nullptr;
1773 EarlyCSE
CSE(
F.getParent()->getDataLayout(), TLI,
TTI, DT, AC, MSSA);
1799char EarlyCSELegacyPass::ID = 0;
1809using EarlyCSEMemSSALegacyPass =
1810 EarlyCSELegacyCommonPass<
true>;
1813char EarlyCSEMemSSALegacyPass::
ID = 0;
1817 return new EarlyCSEMemSSALegacyPass();
1823 "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.
const Function * getParent() const
Return the enclosing method, or null if none.
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
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 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 mayThrow(bool IncludePhaseOneUnwind=false) const LLVM_READONLY
Return true if this instruction may throw an exception.
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.
const BasicBlock * getParent() const
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.
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.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this 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 &)
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
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.
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.