92#define DEBUG_TYPE "gvn"
94STATISTIC(NumGVNInstr,
"Number of instructions deleted");
96STATISTIC(NumGVNPRE,
"Number of instructions PRE'd");
98STATISTIC(NumGVNSimpl,
"Number of instructions simplified");
99STATISTIC(NumGVNEqProp,
"Number of equalities propagated");
103 "Number of loads moved to predecessor of a critical edge in PRE");
105STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax,
106 "Number of blocks speculated as available in "
107 "IsValueFullyAvailableInBlock(), max");
109 "Number of times we we reached gvn-max-block-speculations cut-off "
110 "preventing further exploration");
133 if ((!
Attrs.isEmpty() || !
Other.Attrs.isEmpty()) &&
134 !
Attrs.intersectWith(
Ty->getContext(),
Other.Attrs).has_value())
172 struct LeaderListNode {
173 LeaderTableEntry Entry;
174 LeaderListNode *
Next;
178 DenseMap<uint32_t, LeaderListNode> NumToLeaders;
183 const LeaderListNode *Current;
194 assert(Current &&
"Dereferenced end of leader list!");
195 Current = Current->Next;
199 return Current ==
Other.Current;
202 return Current !=
Other.Current;
208 auto I = NumToLeaders.find(
N);
209 if (
I == NumToLeaders.end()) {
223 for (
auto &[
_, HeadNode] : NumToLeaders) {
224 LeaderListNode *
N = HeadNode.Next;
226 auto *
Next =
N->Next;
227 N->~LeaderListNode();
231 NumToLeaders.clear();
232 TableAllocator.Reset();
243 const ScalarOptions *Opts =
nullptr;
269 friend class ::GVNLegacyPass;
294 bool InvalidBlockRPONumbers =
true;
317 struct ReachingMemVal {
326 const Value *SelTrueAddr =
nullptr;
327 const Value *SelFalseAddr =
nullptr;
331 return {DepKind::Other, BB, Addr, Inst, -1};
334 static ReachingMemVal getDef(
const Value *Addr, Instruction *Inst) {
335 return {DepKind::Def, Inst->getParent(), Addr, Inst, -1};
338 static ReachingMemVal getClobber(
const Value *Addr, Instruction *Inst,
339 int32_t Offset = -1) {
340 return {DepKind::Clobber, Inst->getParent(), Addr, Inst, Offset};
343 static ReachingMemVal getSelect(BasicBlock *BB, SelectInst *Sel,
344 const Value *TrueAddr,
345 const Value *FalseAddr) {
346 return {DepKind::Select, BB,
nullptr,
nullptr, -1, Sel,
347 TrueAddr, FalseAddr};
351 struct DependencyBlockInfo {
352 DependencyBlockInfo() =
delete;
353 DependencyBlockInfo(
const PHITransAddr &Addr, MemoryAccess *ClobberMA)
354 : Addr(Addr), InitialClobberMA(ClobberMA), ClobberMA(ClobberMA),
357 MemoryAccess *InitialClobberMA;
358 MemoryAccess *ClobberMA;
359 std::optional<ReachingMemVal> MemVal;
360 bool ForceUnknown : 1;
364 using DependencyBlockSet = DenseMap<BasicBlock *, DependencyBlockInfo>;
366 std::optional<GVNPassImpl::ReachingMemVal> scanMemoryAccessesUsers(
367 const MemoryLocation &Loc,
bool IsInvariantLoad, BasicBlock *BB,
368 const SmallVectorImpl<MemoryAccess *> &ClobbersList,
MemorySSA &MSSA,
369 BatchAAResults &AA, LoadInst *L =
nullptr);
371 std::optional<GVNPassImpl::ReachingMemVal>
372 accessMayModifyLocation(MemoryAccess *ClobberMA,
const MemoryLocation &Loc,
373 Align LoadAlign,
bool IsInvariantLoad, BasicBlock *BB,
376 bool collectPredecessors(BasicBlock *BB,
const PHITransAddr &Addr,
377 MemoryAccess *ClobberMA, DependencyBlockSet &Blocks,
378 SmallVectorImpl<BasicBlock *> &Worklist);
380 void collectClobberList(SmallVectorImpl<MemoryAccess *> &Clobbers,
381 BasicBlock *BB,
const DependencyBlockInfo &StartInfo,
382 const DependencyBlockSet &Blocks,
MemorySSA &MSSA);
384 bool findReachingValuesForLoad(LoadInst *Inst,
385 SmallVectorImpl<ReachingMemVal> &
Values,
389 bool processLoad(LoadInst *L);
390 bool processMaskedLoad(IntrinsicInst *
I);
391 bool processNonLocalLoad(LoadInst *L);
392 bool processNonLocalLoad(LoadInst *L, SmallVectorImpl<ReachingMemVal> &Deps);
393 bool processAssumeIntrinsic(AssumeInst *
II);
397 std::optional<AvailableValue>
398 analyzeLoadAvailability(LoadInst *
Load,
const ReachingMemVal &Dep,
405 std::optional<AvailableValue>
406 analyzeSelectAvailability(LoadInst *
Load, SelectInst *Sel,
Value *TrueAddr,
407 Value *FalseAddr, Instruction *From);
412 void analyzeLoadAvailability(LoadInst *
Load,
413 SmallVectorImpl<ReachingMemVal> &Deps,
414 AvailValInBlkVect &ValuesPerBlock,
415 UnavailBlkVect &UnavailableBlocks);
419 LoadInst *findLoadToHoistIntoPred(BasicBlock *
Pred, BasicBlock *LoadBB,
422 bool performLoadPRE(LoadInst *
Load, AvailValInBlkVect &ValuesPerBlock,
423 UnavailBlkVect &UnavailableBlocks);
428 bool performLoopLoadPRE(LoadInst *
Load, AvailValInBlkVect &ValuesPerBlock,
429 UnavailBlkVect &UnavailableBlocks);
433 void eliminatePartiallyRedundantLoad(
434 LoadInst *
Load, AvailValInBlkVect &ValuesPerBlock,
435 MapVector<BasicBlock *, Value *> &AvailableLoads,
436 MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad);
439 bool processInstruction(Instruction *
I);
440 bool processBlock(BasicBlock *BB);
441 bool replaceWithEquivalentCmp(CmpInst *Cmp);
444 bool performScalarPRE(Instruction *
I);
445 bool performScalarPREInsertion(Instruction *Instr, BasicBlock *
Pred,
446 BasicBlock *Curr,
unsigned int ValNo);
447 Value *findLeader(
const BasicBlock *BB, uint32_t Num);
448 void cleanupGlobalSets();
449 void removeInstruction(Instruction *
I);
450 void verifyRemoved(
const Instruction *
I)
const;
451 bool splitCriticalEdges();
452 BasicBlock *splitCriticalEdges(BasicBlock *
Pred, BasicBlock *Succ);
455 const std::variant<BasicBlockEdge, Instruction *> &Root);
456 bool processFoldableCondBr(CondBrInst *BI);
457 void addDeadBlock(BasicBlock *BB);
458 void assignValNumForDeadCode();
490 Res.
Kind = ValType::SimpleVal;
498 Res.
Kind = ValType::MemIntrin;
506 Res.
Kind = ValType::LoadVal;
514 Res.
Kind = ValType::UndefVal;
522 Res.
Kind = ValType::SelectVal;
572 Res.
AV = std::move(
AV);
588 return AV.MaterializeAdjustedValue(
Load,
BB->getTerminator());
599 E.Opcode =
I->getOpcode();
604 E.VarArgs.push_back(
lookupOrAdd(GCR->getOperand(0)));
605 E.VarArgs.push_back(
lookupOrAdd(GCR->getBasePtr()));
606 E.VarArgs.push_back(
lookupOrAdd(GCR->getDerivedPtr()));
608 for (
Use &
Op :
I->operands())
611 if (
I->isCommutative()) {
616 assert(
I->getNumOperands() >= 2 &&
"Unsupported commutative instruction!");
617 if (
E.VarArgs[0] >
E.VarArgs[1])
619 E.Commutative =
true;
623 E.VarArgs.append(IVI->idx_begin(), IVI->idx_end());
625 ArrayRef<int> ShuffleMask = SVI->getShuffleMask();
626 E.VarArgs.append(ShuffleMask.
begin(), ShuffleMask.
end());
628 E.Attrs = CB->getAttributes();
637 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
638 "Not a comparison!");
645 if (
E.VarArgs[0] >
E.VarArgs[1]) {
649 E.Opcode = (Opcode << 8) | Predicate;
650 E.Commutative =
true;
656 assert(EI &&
"Not an ExtractValueInst?");
685 Type *PtrTy =
GEP->getType()->getScalarType();
686 const DataLayout &
DL =
GEP->getDataLayout();
687 unsigned BitWidth =
DL.getIndexTypeSizeInBits(PtrTy);
688 SmallMapVector<Value *, APInt, 4> VariableOffsets;
690 if (
GEP->collectOffset(
DL,
BitWidth, VariableOffsets, ConstantOffset)) {
694 E.Opcode =
GEP->getOpcode();
697 for (
const auto &[
V, Scale] : VariableOffsets) {
701 if (!ConstantOffset.isZero())
707 E.Opcode =
GEP->getOpcode();
708 E.Ty =
GEP->getSourceElementType();
709 for (Use &
Op :
GEP->operands())
727 ValueNumbering.insert(std::make_pair(V, Num));
729 NumberingPhi[Num] = PN;
739 assert(MSSA &&
"addMemoryStateToExp should not be called without MemorySSA");
753 if (
C->getFunction()->isPresplitCoroutine()) {
754 ValueNumbering[
C] = NextValueNumber;
755 return NextValueNumber++;
761 if (
C->isConvergent()) {
762 ValueNumbering[
C] = NextValueNumber;
763 return NextValueNumber++;
769 if (
C->hasOperandBundles()) {
770 ValueNumbering[
C] = NextValueNumber;
771 return NextValueNumber++;
774 if (AA->doesNotAccessMemory(
C)) {
776 uint32_t
E = assignExpNewValueNum(Exp).first;
777 ValueNumbering[
C] =
E;
781 if (MD && AA->onlyReadsMemory(
C)) {
783 auto [
E, IsValNumNew] = assignExpNewValueNum(Exp);
785 ValueNumbering[
C] =
E;
789 MemDepResult LocalDep = MD->getDependency(
C);
792 ValueNumbering[
C] = NextValueNumber;
793 return NextValueNumber++;
796 if (LocalDep.
isDef()) {
801 if (!LocalDepCall || LocalDepCall->
arg_size() !=
C->arg_size()) {
802 ValueNumbering[
C] = NextValueNumber;
803 return NextValueNumber++;
806 for (
unsigned I = 0,
E =
C->arg_size();
I <
E; ++
I) {
809 if (CVN != LocalDepCallVN) {
810 ValueNumbering[
C] = NextValueNumber;
811 return NextValueNumber++;
816 ValueNumbering[
C] =
V;
822 MD->getNonLocalCallDependency(
C);
824 CallInst *CDep =
nullptr;
828 for (
const NonLocalDepEntry &
I : Deps) {
829 if (
I.getResult().isNonLocal())
834 if (!
I.getResult().isDef() || CDep !=
nullptr) {
841 if (NonLocalDepCall && DT->properlyDominates(
I.getBB(),
C->getParent())) {
842 CDep = NonLocalDepCall;
851 ValueNumbering[
C] = NextValueNumber;
852 return NextValueNumber++;
856 ValueNumbering[
C] = NextValueNumber;
857 return NextValueNumber++;
859 for (
unsigned I = 0,
E =
C->arg_size();
I <
E; ++
I) {
863 ValueNumbering[
C] = NextValueNumber;
864 return NextValueNumber++;
869 ValueNumbering[
C] =
V;
873 if (MSSA && IsMSSAEnabled && AA->onlyReadsMemory(
C)) {
875 addMemoryStateToExp(
C, Exp);
876 auto [
V,
_] = assignExpNewValueNum(Exp);
877 ValueNumbering[
C] =
V;
881 ValueNumbering[
C] = NextValueNumber;
882 return NextValueNumber++;
886uint32_t GVNValueTable::computeLoadStoreVN(
Instruction *
I) {
887 if (!MSSA || !IsMSSAEnabled) {
888 ValueNumbering[
I] = NextValueNumber;
889 return NextValueNumber++;
893 Exp.Ty =
I->getType();
894 Exp.Opcode =
I->getOpcode();
895 for (Use &
Op :
I->operands())
897 addMemoryStateToExp(
I, Exp);
899 auto [
V,
_] = assignExpNewValueNum(Exp);
900 ValueNumbering[
I] =
V;
906 return ValueNumbering.contains(V);
918 auto VI = ValueNumbering.find(V);
919 if (VI != ValueNumbering.end())
924 ValueNumbering[V] = NextValueNumber;
927 return NextValueNumber++;
931 switch (
I->getOpcode()) {
932 case Instruction::Call:
934 case Instruction::FNeg:
935 case Instruction::Add:
936 case Instruction::FAdd:
937 case Instruction::Sub:
938 case Instruction::FSub:
939 case Instruction::Mul:
940 case Instruction::FMul:
941 case Instruction::UDiv:
942 case Instruction::SDiv:
943 case Instruction::FDiv:
944 case Instruction::URem:
945 case Instruction::SRem:
946 case Instruction::FRem:
947 case Instruction::Shl:
948 case Instruction::LShr:
949 case Instruction::AShr:
950 case Instruction::And:
951 case Instruction::Or:
952 case Instruction::Xor:
953 case Instruction::Trunc:
954 case Instruction::ZExt:
955 case Instruction::SExt:
956 case Instruction::FPToUI:
957 case Instruction::FPToSI:
958 case Instruction::UIToFP:
959 case Instruction::SIToFP:
960 case Instruction::FPTrunc:
961 case Instruction::FPExt:
962 case Instruction::PtrToInt:
963 case Instruction::PtrToAddr:
964 case Instruction::IntToPtr:
965 case Instruction::AddrSpaceCast:
966 case Instruction::BitCast:
967 case Instruction::Select:
968 case Instruction::Freeze:
969 case Instruction::ExtractElement:
970 case Instruction::InsertElement:
971 case Instruction::ShuffleVector:
972 case Instruction::InsertValue:
973 case Instruction::BitExtract:
974 case Instruction::BitInsert:
977 case Instruction::ICmp:
978 case Instruction::FCmp:
980 I->getOperand(0),
I->getOperand(1));
982 case Instruction::GetElementPtr:
985 case Instruction::ExtractValue:
988 case Instruction::PHI:
989 ValueNumbering[V] = NextValueNumber;
991 return NextValueNumber++;
992 case Instruction::Load:
993 case Instruction::Store:
994 return computeLoadStoreVN(
I);
996 ValueNumbering[V] = NextValueNumber;
997 return NextValueNumber++;
1000 uint32_t E = assignExpNewValueNum(Exp).first;
1001 ValueNumbering[V] = E;
1008 auto VI = ValueNumbering.find(V);
1010 assert(VI != ValueNumbering.end() &&
"Value not numbered?");
1013 return (VI != ValueNumbering.end()) ? VI->second : 0;
1023 Expression Exp = createCmpExpr(Opcode, Predicate, LHS, RHS);
1024 return assignExpNewValueNum(Exp).first;
1029 Expression Exp = createCmpExpr(Opcode, Predicate, LHS, RHS);
1030 return ExpressionNumbering.lookup(Exp);
1038 return ExpressionNumbering.lookup(Exp);
1043 ValueNumbering.clear();
1044 ExpressionNumbering.clear();
1045 NumberingPhi.clear();
1046 NumberingBB.clear();
1047 PhiTranslateTable.clear();
1048 NextValueNumber = 1;
1049 Expressions.clear();
1056 uint32_t Num = ValueNumbering.lookup(V);
1057 ValueNumbering.erase(V);
1060 NumberingPhi.erase(Num);
1062 NumberingBB.erase(Num);
1068 assert(!ValueNumbering.contains(V) &&
1069 "Inst still occurs in value numbering map!");
1078 const auto &[It, Inserted] = NumToLeaders.try_emplace(
N, V, BB,
nullptr);
1081 auto *NewSlot = TableAllocator.Allocate<LeaderListNode>();
1082 new (NewSlot) LeaderListNode(V, BB, It->second.Next);
1083 It->second.Next = NewSlot;
1090 auto It = NumToLeaders.find(
N);
1091 if (It == NumToLeaders.end())
1094 LeaderListNode *Prev =
nullptr;
1095 LeaderListNode *Curr = &It->second;
1097 while (Curr && (Curr->Entry.Val !=
I || Curr->Entry.BB != BB)) {
1107 Prev->Next = Curr->Next;
1108 Curr->~LeaderListNode();
1109 TableAllocator.Deallocate<LeaderListNode>(Curr);
1114 NumToLeaders.erase(It);
1117 LeaderListNode *
Next = Curr->Next;
1118 Curr->Entry.Val = std::move(
Next->Entry.Val);
1119 Curr->Entry.BB =
Next->Entry.BB;
1120 Curr->Next =
Next->Next;
1121 Next->~LeaderListNode();
1122 TableAllocator.Deallocate<LeaderListNode>(
Next);
1132 return Options.AllowScalarPRE.value_or(Opts->enable_scalar_pre);
1136 return Options.AllowLoadPRE.value_or(Opts->enable_load_pre);
1140 return Options.AllowLoadInLoopPRE.value_or(Opts->enable_load_in_loop_pre);
1144 return Options.AllowLoadPRESplitBackedge.value_or(
1145 Opts->enable_split_backedge_in_load_pre);
1153 return Options.AllowMemDep.value_or(
false);
1154 return Options.AllowMemDep.value_or(
valueOr(Opts->enable_gvn_memdep,
true));
1158 return Options.AllowMemorySSA.value_or(Opts->enable_gvn_memoryssa);
1180 auto *MemDep = Impl->isMemDepEnabled()
1185 if (Impl->isMemorySSAEnabled() && !MSSA) {
1187 "On-demand computation of MemSSA implies that MemDep is disabled!");
1191 bool Changed = Impl->run(
F, AC, DT,
TLI,
AA, MemDep, LI, &ORE,
1192 MSSA ? &MSSA->getMSSA() :
nullptr);
1207 removeInstruction(
I);
1213 OS, MapClassName2PassName);
1217 if (
Options.AllowScalarPRE != std::nullopt)
1218 OS << (*
Options.AllowScalarPRE ?
"" :
"no-") <<
"scalar-pre;";
1219 if (
Options.AllowLoadPRE != std::nullopt)
1220 OS << (*
Options.AllowLoadPRE ?
"" :
"no-") <<
"load-pre;";
1221 if (
Options.AllowLoadPRESplitBackedge != std::nullopt)
1222 OS << (*
Options.AllowLoadPRESplitBackedge ?
"" :
"no-")
1223 <<
"split-backedge-load-pre;";
1224 if (
Options.AllowMemDep != std::nullopt)
1225 OS << (*
Options.AllowMemDep ?
"" :
"no-") <<
"memdep;";
1226 if (
Options.AllowMemorySSA != std::nullopt)
1227 OS << (*
Options.AllowMemorySSA ?
"" :
"no-") <<
"memoryssa";
1255 std::optional<BasicBlock *> UnavailableBB;
1259 unsigned NumNewNewSpeculativelyAvailableBBs = 0;
1267 while (!Worklist.
empty()) {
1271 std::pair<DenseMap<BasicBlock *, AvailabilityState>::iterator,
bool>
IV =
1279 UnavailableBB = CurrBB;
1290 ++NumNewNewSpeculativelyAvailableBBs;
1292 NumNewNewSpeculativelyAvailableBBs > Opts.gvn_max_block_speculations;
1297 MaxBBSpeculationCutoffReachedTimes += (int)OutOfBudget;
1299 UnavailableBB = CurrBB;
1305 NewSpeculativelyAvailableBBs.
insert(CurrBB);
1311#if LLVM_ENABLE_STATS
1312 IsValueFullyAvailableInBlockNumSpeculationsMax.updateMax(
1313 NumNewNewSpeculativelyAvailableBBs);
1318 auto MarkAsFixpointAndEnqueueSuccessors =
1320 auto It = FullyAvailableBlocks.
find(BB);
1321 if (It == FullyAvailableBlocks.
end())
1328 State = FixpointState;
1331 "Found a speculatively available successor leftover?");
1339 if (UnavailableBB) {
1346 while (!Worklist.
empty())
1347 MarkAsFixpointAndEnqueueSuccessors(Worklist.
pop_back_val(),
1355 while (!Worklist.
empty())
1356 MarkAsFixpointAndEnqueueSuccessors(Worklist.
pop_back_val(),
1360 "Must have fixed all the new speculatively available blocks.");
1363 return !UnavailableBB;
1375 if (
V.AV.Val == OldValue)
1376 V.AV.Val = NewValue;
1377 if (
V.AV.isSelectValue()) {
1378 if (
V.AV.V1 == OldValue)
1380 if (
V.AV.V2 == OldValue)
1395 if (ValuesPerBlock.
size() == 1 &&
1397 assert(!ValuesPerBlock[0].AV.isUndefValue() &&
1398 "Dead BB dominate this block");
1399 return ValuesPerBlock[0].MaterializeAdjustedValue(
Load);
1410 if (AV.AV.isUndefValue())
1420 if (BB ==
Load->getParent() &&
1421 ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() ==
Load) ||
1422 (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() ==
Load)))
1439 if (Res->
getType() != LoadTy) {
1454 Load->getFunction());
1465 if (!CoercedLoad->
hasMetadata(LLVMContext::MD_noundef))
1467 {LLVMContext::MD_dereferenceable,
1468 LLVMContext::MD_dereferenceable_or_null,
1469 LLVMContext::MD_invariant_load, LLVMContext::MD_invariant_group,
1470 LLVMContext::MD_alias_scope, LLVMContext::MD_noalias});
1486 assert(
V1 &&
V2 &&
"both value operands of the select must be present");
1496 assert(Res &&
"failed to materialize?");
1502 return II->getIntrinsicID() == Intrinsic::lifetime_start;
1519 Value *PtrOp =
Load->getPointerOperand();
1525 for (
auto *U : PtrOp->
users()) {
1546 for (
auto *U : PtrOp->
users()) {
1549 if (
I->getFunction() ==
Load->getFunction() &&
1557 OtherAccess =
nullptr;
1576 using namespace ore;
1579 R <<
"load of type " << NV(
"Type",
Load->getType()) <<
" not eliminated"
1584 R <<
" in favor of " << NV(
"OtherAccess", OtherAccess);
1586 R <<
" because it is clobbered by " << NV(
"ClobberedBy", DepInst);
1601 for (
auto *Inst = BB == FromBB ? From : BB->getTerminator();
1604 if (++NumVisitedInsts > Opts.gvn_max_num_visited_insts)
1609 if (
SI->isSimple() &&
SI->getPointerOperand() ==
Loc.Ptr &&
1610 SI->getValueOperand()->getType() == LoadTy)
1611 return SI->getValueOperand();
1615 if (LI->getPointerOperand() ==
Loc.Ptr && LI->getType() == LoadTy)
1621std::optional<AvailableValue>
1626 "Invalid address type of true side of select dependency");
1628 "Invalid address type of false side of select dependency");
1636 return std::nullopt;
1640 return std::nullopt;
1644std::optional<AvailableValue>
1645GVNPassImpl::analyzeLoadAvailability(
LoadInst *
Load,
const ReachingMemVal &Dep,
1647 assert(
Load->isUnordered() &&
"rules below are incorrect for ordered access");
1648 assert((Dep.Kind == DepKind::Def || Dep.Kind == DepKind::Clobber) &&
1649 "expected a local dependence");
1653 const DataLayout &
DL =
Load->getDataLayout();
1654 if (Dep.Kind == DepKind::Clobber) {
1660 if (
Address &&
Load->isAtomic() <= DepSI->isAtomic()) {
1677 Load->isAtomic() <= DepLoad->isAtomic()) {
1684 DepLoad->getFunction())) {
1685 const auto ClobberOff = MD->getClobberOffset(DepLoad);
1687 Offset = (ClobberOff == std::nullopt || *ClobberOff < 0)
1693 DepLoad->getFunction()) ||
1720 dbgs() <<
" is clobbered by " << *DepInst <<
'\n';);
1724 return std::nullopt;
1726 assert(Dep.Kind == DepKind::Def &&
"follows from above");
1733 if (Constant *InitVal =
1743 return std::nullopt;
1746 if (S->isAtomic() <
Load->isAtomic())
1747 return std::nullopt;
1758 return std::nullopt;
1761 if (
LD->isAtomic() <
Load->isAtomic())
1762 return std::nullopt;
1775 return std::nullopt;
1782 dbgs() <<
" has unknown def " << *DepInst <<
'\n';);
1783 return std::nullopt;
1786void GVNPassImpl::analyzeLoadAvailability(
LoadInst *
Load,
1788 AvailValInBlkVect &ValuesPerBlock,
1789 UnavailBlkVect &UnavailableBlocks) {
1794 for (
const auto &Dep : Deps) {
1797 if (DeadBlocks.count(DepBB)) {
1804 if (Dep.Kind == DepKind::Other) {
1805 UnavailableBlocks.push_back(DepBB);
1812 if (Dep.Kind == DepKind::Select) {
1813 if (
auto AV = analyzeSelectAvailability(
1814 Load, Dep.Sel,
const_cast<Value *
>(Dep.SelTrueAddr),
1816 ValuesPerBlock.push_back(
1819 UnavailableBlocks.push_back(DepBB);
1828 analyzeLoadAvailability(
Load, Dep,
const_cast<Value *
>(Dep.Addr))) {
1832 ValuesPerBlock.push_back(
1835 UnavailableBlocks.push_back(DepBB);
1839 assert(Deps.size() == ValuesPerBlock.size() + UnavailableBlocks.size() &&
1840 "post condition violation");
1866 auto *
Term =
Pred->getTerminator();
1867 if (
Term->getNumSuccessors() != 2 ||
Term->isSpecialTerminator())
1869 auto *SuccBB =
Term->getSuccessor(0);
1870 if (SuccBB == LoadBB)
1871 SuccBB =
Term->getSuccessor(1);
1872 if (!SuccBB->getSinglePredecessor())
1875 unsigned int NumInsts = Opts->gvn_max_num_insns;
1876 for (Instruction &Inst : *SuccBB) {
1879 if (--NumInsts == 0)
1885 bool HasLocalDep =
true;
1887 MemDepResult Dep = MD->getDependency(&Inst);
1890 auto *MSSA = MSSAU->getMemorySSA();
1892 if (
auto *MA = MSSA->getMemoryAccess(&Inst); MA &&
isa<MemoryUse>(MA)) {
1893 auto *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(MA);
1894 HasLocalDep = Clobber->getBlock() == SuccBB;
1902 if (!HasLocalDep && !ICF->isDominatedByICFIFromSameBlock(&Inst))
1913void GVNPassImpl::eliminatePartiallyRedundantLoad(
1917 for (
const auto &AvailableLoad : AvailableLoads) {
1918 BasicBlock *UnavailableBlock = AvailableLoad.first;
1919 Value *LoadPtr = AvailableLoad.second;
1922 new LoadInst(
Load->getType(), LoadPtr,
Load->getName() +
".pre",
1923 Load->getProperties(),
1925 NewLoad->setDebugLoc(
Load->getDebugLoc());
1927 auto *NewAccess = MSSAU->createMemoryAccessInBB(
1930 MSSAU->insertDef(NewDef,
true);
1936 AAMDNodes Tags =
Load->getAAMetadata();
1938 NewLoad->setAAMetadata(Tags);
1940 if (
auto *MD =
Load->getMetadata(LLVMContext::MD_invariant_load))
1941 NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
1942 if (
auto *InvGroupMD =
Load->getMetadata(LLVMContext::MD_invariant_group))
1943 NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
1944 if (
auto *RangeMD =
Load->getMetadata(LLVMContext::MD_range))
1945 NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);
1946 if (
auto *NoFPClassMD =
Load->getMetadata(LLVMContext::MD_nofpclass))
1947 NewLoad->setMetadata(LLVMContext::MD_nofpclass, NoFPClassMD);
1949 if (
auto *AccessMD =
Load->getMetadata(LLVMContext::MD_access_group))
1950 if (LI->getLoopFor(
Load->getParent()) == LI->getLoopFor(UnavailableBlock))
1951 NewLoad->setMetadata(LLVMContext::MD_access_group, AccessMD);
1960 ValuesPerBlock.push_back(
1963 MD->invalidateCachedPointerInfo(LoadPtr);
1968 if (CriticalEdgePredAndLoad) {
1969 auto It = CriticalEdgePredAndLoad->
find(UnavailableBlock);
1970 if (It != CriticalEdgePredAndLoad->
end()) {
1971 ++NumPRELoadMoved2CEPred;
1972 ICF->insertInstructionTo(NewLoad, UnavailableBlock);
1973 LoadInst *OldLoad = It->second;
1977 if (uint32_t ValNo = VN.lookup(OldLoad,
false))
1978 LeaderTable.erase(ValNo, OldLoad, OldLoad->
getParent());
1979 removeInstruction(OldLoad);
1987 ICF->removeUsersOf(
Load);
1988 Load->replaceAllUsesWith(
V);
1992 I->setDebugLoc(
Load->getDebugLoc());
1993 if (MD &&
V->getType()->isPtrOrPtrVectorTy())
1994 MD->invalidateCachedPointerInfo(
V);
1997 <<
"load eliminated by PRE";
2003 AvailValInBlkVect &ValuesPerBlock,
2004 UnavailBlkVect &UnavailableBlocks) {
2013 SmallPtrSet<BasicBlock *, 4> Blockers(
llvm::from_range, UnavailableBlocks);
2035 bool MustEnsureSafetyOfSpeculativeExecution =
2036 ICF->isDominatedByICFIFromSameBlock(
Load);
2040 if (TmpBB == LoadBB)
2042 if (Blockers.count(TmpBB))
2054 MustEnsureSafetyOfSpeculativeExecution =
2055 MustEnsureSafetyOfSpeculativeExecution || ICF->hasICF(TmpBB);
2063 MapVector<BasicBlock *, Value *> PredLoads;
2064 DenseMap<BasicBlock *, AvailabilityState> FullyAvailableBlocks;
2067 for (BasicBlock *UnavailableBB : UnavailableBlocks)
2075 MapVector<BasicBlock *, LoadInst *> CriticalEdgePredAndLoad;
2079 if (
Pred->getTerminator()->isEHPad()) {
2081 dbgs() <<
"COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
2082 <<
Pred->getName() <<
"': " << *
Load <<
'\n');
2090 if (
Pred->getTerminator()->getNumSuccessors() != 1) {
2093 dbgs() <<
"COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
2094 <<
Pred->getName() <<
"': " << *
Load <<
'\n');
2100 dbgs() <<
"COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
2101 <<
Pred->getName() <<
"': " << *
Load <<
'\n');
2107 if (DT->dominates(LoadBB,
Pred)) {
2110 <<
"COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
2111 <<
Pred->getName() <<
"': " << *
Load <<
'\n');
2115 if (LoadInst *LI = findLoadToHoistIntoPred(
Pred, LoadBB,
Load))
2116 CriticalEdgePredAndLoad[
Pred] = LI;
2121 PredLoads[
Pred] =
nullptr;
2126 unsigned NumInsertPreds = PredLoads.
size() + CriticalEdgePredSplit.
size();
2127 unsigned NumUnavailablePreds = NumInsertPreds +
2128 CriticalEdgePredAndLoad.
size();
2129 assert(NumUnavailablePreds != 0 &&
2130 "Fully available value should already be eliminated!");
2131 (void)NumUnavailablePreds;
2137 if (NumInsertPreds > 1)
2142 if (MustEnsureSafetyOfSpeculativeExecution) {
2143 if (CriticalEdgePredSplit.
size())
2147 for (
auto &PL : PredLoads)
2151 for (
auto &CEP : CriticalEdgePredAndLoad)
2158 for (BasicBlock *OrigPred : CriticalEdgePredSplit) {
2159 BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);
2160 assert(!PredLoads.count(OrigPred) &&
"Split edges shouldn't be in map!");
2161 PredLoads[NewPred] =
nullptr;
2162 LLVM_DEBUG(
dbgs() <<
"Split critical edge " << OrigPred->getName() <<
"->"
2163 << LoadBB->
getName() <<
'\n');
2166 for (
auto &CEP : CriticalEdgePredAndLoad)
2167 PredLoads[CEP.first] =
nullptr;
2170 bool CanDoPRE =
true;
2171 const DataLayout &
DL =
Load->getDataLayout();
2172 SmallVector<Instruction*, 8> NewInsts;
2173 for (
auto &PredLoad : PredLoads) {
2174 BasicBlock *UnavailablePred = PredLoad.first;
2184 Value *LoadPtr =
Load->getPointerOperand();
2186 while (Cur != LoadBB) {
2199 LoadPtr =
Address.translateWithInsertion(LoadBB, UnavailablePred, *DT,
2206 << *
Load->getPointerOperand() <<
"\n");
2211 PredLoad.second = LoadPtr;
2215 while (!NewInsts.
empty()) {
2225 return !CriticalEdgePredSplit.empty();
2233 <<
" INSTS: " << *NewInsts.
back()
2237 for (Instruction *
I : NewInsts) {
2241 I->updateLocationAfterHoist();
2250 eliminatePartiallyRedundantLoad(
Load, ValuesPerBlock, PredLoads,
2251 &CriticalEdgePredAndLoad);
2257 AvailValInBlkVect &ValuesPerBlock,
2258 UnavailBlkVect &UnavailableBlocks) {
2259 const Loop *
L = LI->getLoopFor(
Load->getParent());
2261 if (!L ||
L->getHeader() !=
Load->getParent())
2266 if (!Preheader || !Latch)
2269 Value *LoadPtr =
Load->getPointerOperand();
2271 if (!
L->isLoopInvariant(LoadPtr))
2277 if (ICF->isDominatedByICFIFromSameBlock(
Load))
2281 for (
auto *Blocker : UnavailableBlocks) {
2283 if (!
L->contains(Blocker))
2300 if (
const Loop *Inner = LI->getLoopFor(Blocker); Inner != L) {
2304 while (Inner->getParentLoop() != L)
2305 Inner = Inner->getParentLoop();
2311 ReloadBB = Inner->getUniqueExitBlock();
2312 if (!ReloadBB || LI->getLoopFor(ReloadBB) != L)
2321 if (DT->dominates(ReloadBB, Latch))
2328 LoopBlock = ReloadBB;
2346 MapVector<BasicBlock *, Value *> AvailableLoads;
2347 AvailableLoads[LoopBlock] = LoadPtr;
2348 AvailableLoads[Preheader] = LoadPtr;
2351 eliminatePartiallyRedundantLoad(
Load, ValuesPerBlock, AvailableLoads,
2359 using namespace ore;
2363 <<
"load of type " << NV(
"Type",
Load->getType()) <<
" eliminated"
2364 << setExtraArgs() <<
" in favor of "
2373 if (
Load->getFunction()->hasFnAttribute(Attribute::SanitizeAddress) ||
2374 Load->getFunction()->hasFnAttribute(Attribute::SanitizeHWAddress))
2379 MD->getNonLocalPointerDependency(
Load, Deps);
2384 unsigned NumDeps = Deps.size();
2385 if (NumDeps > Opts->gvn_max_num_deps)
2391 for (
const NonLocalDepResult &Dep : Deps) {
2392 const auto &
R = Dep.getResult();
2393 SelectAddr SelAddr = Dep.getAddress();
2399 ReachingMemVal::getSelect(BB, Sel, Addrs.first, Addrs.second));
2411 return processNonLocalLoad(
Load, MemVals);
2418 if (Deps.
size() == 1 && Deps[0].Kind == DepKind::Other) {
2420 dbgs() <<
" has unknown dependencies\n";);
2428 if (GetElementPtrInst *
GEP =
2430 for (Use &U :
GEP->indices())
2440 AvailValInBlkVect ValuesPerBlock;
2441 UnavailBlkVect UnavailableBlocks;
2442 analyzeLoadAvailability(
Load, Deps, ValuesPerBlock, UnavailableBlocks);
2446 if (ValuesPerBlock.empty())
2454 if (UnavailableBlocks.empty()) {
2460 ICF->removeUsersOf(
Load);
2461 Load->replaceAllUsesWith(
V);
2469 if (
Load->getDebugLoc() &&
Load->getParent() ==
I->getParent())
2470 I->setDebugLoc(
Load->getDebugLoc());
2471 if (MD &&
V->getType()->isPtrOrPtrVectorTy())
2472 MD->invalidateCachedPointerInfo(
V);
2485 if (performLoopLoadPRE(
Load, ValuesPerBlock, UnavailableBlocks) ||
2486 performLoadPRE(
Load, ValuesPerBlock, UnavailableBlocks))
2492bool GVNPassImpl::processAssumeIntrinsic(
AssumeInst *IntrinsicI) {
2496 if (
Cond->isZero()) {
2506 const MemoryUseOrDef *FirstNonDom =
nullptr;
2508 MSSAU->getMemorySSA()->getBlockAccesses(IntrinsicI->
getParent());
2515 for (
const auto &Acc : *AL) {
2517 if (!Current->getMemoryInst()->comesBefore(NewS)) {
2518 FirstNonDom = Current;
2525 FirstNonDom ? MSSAU->createMemoryAccessBefore(
2527 const_cast<MemoryUseOrDef *
>(FirstNonDom))
2528 : MSSAU->createMemoryAccessInBB(
2550 return propagateEquality(
V,
True, IntrinsicI);
2555 I->replaceAllUsesWith(Repl);
2562 Value *PointerOperand = L->getPointerOperand()->stripPointerCasts();
2573 PointerUsesQueue.
push_back(PointerOperand);
2578 while (!PointerUsesQueue.
empty()) {
2581 "Null or GlobalValue should not be inserted");
2585 if (!
I ||
I == L || !DT.
dominates(
I, MostDominatingInstruction))
2600 if (
I->hasMetadata(LLVMContext::MD_invariant_group) &&
2602 MostDominatingInstruction =
I;
2606 return MostDominatingInstruction != L ? MostDominatingInstruction :
nullptr;
2612static std::optional<MemoryLocation>
2619 switch (
II->getIntrinsicID()) {
2620 case Intrinsic::masked_load:
2622 case Intrinsic::masked_store:
2625 return std::nullopt;
2632 return std::nullopt;
2636 return std::nullopt;
2642std::optional<GVNPassImpl::ReachingMemVal> GVNPassImpl::scanMemoryAccessesUsers(
2648 auto UpdateChoice = [&](std::optional<ReachingMemVal> &Choice,
2652 Choice = ReachingMemVal::getClobber(Loc.
Ptr, Candidate, AR.getOffset());
2654 Choice = ReachingMemVal::getDef(Loc.
Ptr, Candidate);
2662 Choice->Kind = DepKind::Clobber;
2663 Choice->Offset = AR.getOffset();
2665 Choice->Kind = DepKind::Def;
2666 Choice->Offset = -1;
2669 Choice->Inst = Candidate;
2670 Choice->Block = Candidate->getParent();
2673 std::optional<ReachingMemVal> ReachingVal;
2674 for (MemoryAccess *MA : ClobbersList) {
2676 for (User *U : MA->
users()) {
2677 if (++Scanned >= Opts->gvn_scan_users_limit)
2678 return ReachingMemVal::getUnknown(BB, Loc.
Ptr);
2681 if (!UseOrDef || UseOrDef->getBlock() != BB)
2690 AliasResult AR = AA.alias(*MaybeLoc, Loc);
2704 UpdateChoice(ReachingVal, AR, MemI);
2716std::optional<GVNPassImpl::ReachingMemVal> GVNPassImpl::accessMayModifyLocation(
2726 if (
Alloc->getParent() == BB)
2727 return ReachingMemVal::getDef(Loc.
Ptr,
const_cast<AllocaInst *
>(
Alloc));
2728 return ReachingMemVal::getUnknown(BB, Loc.
Ptr);
2732 if (IsInvariantLoad || AA.pointsToConstantMemory(Loc))
2733 return std::nullopt;
2737 return L->getOrdering();
2744 AliasResult AR = AA.alias(*MaybeLoc, Loc);
2746 return ReachingMemVal::getDef(Loc.
Ptr, ClobberI);
2757 return std::nullopt;
2758 return ReachingMemVal::getClobber(Loc.
Ptr, ClobberI);
2763 return std::nullopt;
2769 Opts->gvn_max_num_insns))
2770 return std::nullopt;
2775 return ReachingMemVal::getClobber(Loc.
Ptr, ClobberI);
2780 "Must be the superset/partial overlap case with positive offset");
2781 return ReachingMemVal::getClobber(Loc.
Ptr, ClobberI, AR.
getOffset());
2785 if (
II->getIntrinsicID() == Intrinsic::lifetime_start) {
2787 if (AA.isMustAlias(IIObjLoc, Loc))
2788 return ReachingMemVal::getDef(Loc.
Ptr, ClobberI);
2789 return std::nullopt;
2797 if (Obj == ClobberI || AA.isMustAlias(ClobberI, Loc.
Ptr))
2798 return ReachingMemVal::getDef(Loc.
Ptr, ClobberI);
2804 return std::nullopt;
2808 ModRefInfo MR = AA.getModRefInfo(ClobberI, Loc);
2812 return std::nullopt;
2816 return ReachingMemVal::getClobber(Loc.
Ptr, ClobberI);
2824 DependencyBlockSet &Blocks,
2835 if (!DT->isReachableFromEntry(
Pred))
2842 PHITransAddr TransAddr = Addr;
2846 auto It = Blocks.find(
Pred);
2847 if (It != Blocks.end()) {
2851 if (It->second.Addr.getAddr() != TransAddr.
getAddr())
2858 Pred, DependencyBlockInfo(TransAddr,
2859 MPhi ? MPhi->getIncomingValueForBlock(
Pred)
2866 for (
auto &
P : Preds) {
2867 [[maybe_unused]]
auto It =
2868 Blocks.try_emplace(
P.first, std::move(
P.second)).first;
2882 const DependencyBlockInfo &StartInfo,
2883 const DependencyBlockSet &Blocks,
2885 MemoryAccess *MA = StartInfo.InitialClobberMA;
2886 MemoryAccess *LastMA = StartInfo.ClobberMA;
2889 while (MA != LastMA) {
2903 BB = DT->getNode(BB)->getIDom()->getBlock();
2907 auto It = Blocks.find(BB);
2908 if (It == Blocks.end())
2911 MA = It->second.InitialClobberMA;
2912 LastMA = It->second.ClobberMA;
2913 if (MA == Clobbers.
back())
2930bool GVNPassImpl::findReachingValuesForLoad(
2933 BatchAAResults AA(AAR, EA);
2935 bool IsInvariantLoad =
L->hasMetadata(LLVMContext::MD_invariant_load);
2941 if (
L->hasMetadata(LLVMContext::MD_invariant_group)) {
2954 if (
auto RMV = scanMemoryAccessesUsers(
2955 Loc, IsInvariantLoad, StartBlock,
2957 Values.emplace_back(*RMV);
2968 accessMayModifyLocation(ClobberMA, Loc,
L->getAlign(),
2969 IsInvariantLoad, StartBlock, MSSA, AA)) {
2970 Values.emplace_back(*RMV);
2980 if (
L->getFunction()->hasFnAttribute(Attribute::SanitizeAddress) ||
2981 L->getFunction()->hasFnAttribute(Attribute::SanitizeHWAddress))
2990 DependencyBlockSet Blocks;
2991 SmallVector<BasicBlock *, 16> InitialWorklist;
2992 const DataLayout &
DL =
L->getDataLayout();
2993 if (!collectPredecessors(StartBlock,
2994 PHITransAddr(
L->getPointerOperand(),
DL, AC),
2995 ClobberMA, Blocks, InitialWorklist))
2999 auto Worklist = InitialWorklist;
3000 while (!Worklist.
empty()) {
3002 if (Blocks.size() > Opts->gvn_max_num_reaching_blocks)
3005 DependencyBlockInfo &
Info = Blocks.find(BB)->second;
3008 if (!
Info.Addr.getAddr())
3018 accessMayModifyLocation(
Info.ClobberMA, BBLoc,
L->getAlign(),
3019 IsInvariantLoad, BB, MSSA, AA)) {
3024 "LiveOnEntry aliases everything");
3040 if (BB == StartBlock &&
Info.Addr.getAddr() !=
L->getPointerOperand()) {
3041 Info.ForceUnknown =
true;
3044 if (BB != StartBlock &&
3045 !collectPredecessors(BB,
Info.Addr,
Info.ClobberMA, Blocks, Worklist))
3046 Info.ForceUnknown =
true;
3056 Worklist = InitialWorklist;
3057 for (BasicBlock *BB : Worklist) {
3058 DependencyBlockInfo &
Info = Blocks.find(BB)->second;
3059 Info.Visited =
true;
3063 while (!Worklist.empty()) {
3064 auto *BB = Worklist.pop_back_val();
3065 DependencyBlockInfo &
Info = Blocks.find(BB)->second;
3069 if (!
Info.Addr.getAddr()) {
3070 Values.push_back(ReachingMemVal::getUnknown(BB,
nullptr));
3075 collectClobberList(Clobbers, BB, Info, Blocks, MSSA);
3078 IsInvariantLoad, BB, Clobbers, MSSA, AA)) {
3090 if (
Info.ForceUnknown) {
3091 Values.push_back(ReachingMemVal::getUnknown(BB,
Info.Addr.getAddr()));
3097 auto It = Blocks.find(
Pred);
3098 if (It == Blocks.end())
3100 DependencyBlockInfo &PredInfo = It->second;
3101 if (PredInfo.Visited)
3103 PredInfo.Visited =
true;
3104 Worklist.push_back(
Pred);
3113bool GVNPassImpl::processLoad(
LoadInst *L) {
3118 if (!
L->isUnordered())
3121 if (
L->getType()->isTokenLikeTy())
3124 if (
L->use_empty()) {
3129 ReachingMemVal MemVal = ReachingMemVal::getUnknown(
nullptr,
nullptr);
3132 MemDepResult Dep = MD->getDependency(L);
3136 return processNonLocalLoad(L);
3140 MemVal = ReachingMemVal::getDef(
L->getPointerOperand(), Dep.
getInst());
3143 ReachingMemVal::getClobber(
L->getPointerOperand(), Dep.
getInst());
3146 if (!findReachingValuesForLoad(L, MemVals, *MSSAU->getMemorySSA(), *AA))
3148 assert(MemVals.
size() &&
"Expected at least an unknown value");
3149 if (MemVals.
size() > 1 || MemVals[0].Block !=
L->getParent())
3150 return processNonLocalLoad(L, MemVals);
3152 MemVal = MemVals[0];
3155 if (MemVal.Kind == DepKind::Other) {
3159 dbgs() <<
"GVN: load ";
L->printAsOperand(
dbgs());
3160 dbgs() <<
" has unknown dependence\n";);
3164 auto AV = analyzeLoadAvailability(L, MemVal,
L->getPointerOperand());
3171 ICF->removeUsersOf(L);
3174 MSSAU->removeMemoryAccess(L);
3188 BatchAAResults BatchAA(*AA);
3195 MemDepResult Dep = MD->getDependency(
I);
3200 auto *MSSA = MSSAU->getMemorySSA();
3206 Def->getBlock() !=
I->getParent())
3208 DepInst = Def->getMemoryInst();
3212 Value *Passthrough =
I->getOperand(2);
3216 StoreVal->
getType() !=
I->getType())
3221 MemoryLocation StoreLoc =
3223 if (!BatchAA.isMustAlias(StoreLoc, LoadLoc))
3231 ICF->removeUsersOf(
I);
3232 I->replaceAllUsesWith(OpToForward);
3240std::pair<uint32_t, bool> GVNValueTable::assignExpNewValueNum(
Expression &Exp) {
3241 uint32_t &
E = ExpressionNumbering[
Exp];
3242 bool CreateNewValNum = !
E;
3243 if (CreateNewValNum) {
3244 Expressions.push_back(Exp);
3245 if (ExprIdx.size() < NextValueNumber + 1)
3246 ExprIdx.resize(NextValueNumber * 2);
3247 E = NextValueNumber;
3248 ExprIdx[NextValueNumber++] = NextExprNumber++;
3250 return {
E, CreateNewValNum};
3255bool GVNValueTable::areAllValsInBB(uint32_t Num,
const BasicBlock *BB,
3259 [=](
const GVNLeaderMap::LeaderTableEntry &L) { return L.BB == BB; });
3266 auto FindRes = PhiTranslateTable.find({Num, Pred});
3267 if (FindRes != PhiTranslateTable.end())
3268 return FindRes->second;
3269 uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, LeaderTable);
3270 PhiTranslateTable.insert({{Num, Pred}, NewNum});
3282 for (
const auto &Entry : Leaders) {
3284 if (
Call &&
Call->getParent() == PhiBlock)
3288 if (
AA->doesNotAccessMemory(
Call))
3291 if (!MD || !
AA->onlyReadsMemory(
Call))
3303 if (
D.getResult().isNonFuncLocal())
3317 if (PHINode *PN = NumberingPhi[Num]) {
3318 if (PN->getParent() != PhiBlock)
3320 for (
unsigned I = 0;
I != PN->getNumIncomingValues(); ++
I) {
3321 if (PN->getIncomingBlock(
I) !=
Pred)
3323 if (uint32_t TransVal =
lookup(PN->getIncomingValue(
I),
false))
3329 if (BasicBlock *BB = NumberingBB[Num]) {
3330 assert(MSSA &&
"NumberingBB is non-empty only when using MemorySSA");
3336 MemoryPhi *MPhi = MSSA->getMemoryAccess(BB);
3343 if (MSSA->isLiveOnEntryDef(MA))
3348 "CFG/MemorySSA mismatch: predecessor not found among incoming blocks");
3354 if (!areAllValsInBB(Num, PhiBlock, LeaderTable))
3357 if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)
3361 for (
unsigned I = 0;
I <
Exp.VarArgs.size();
I++) {
3365 if ((
I > 1 &&
Exp.Opcode == Instruction::InsertValue) ||
3366 (
I > 0 &&
Exp.Opcode == Instruction::ExtractValue) ||
3367 (
I > 1 &&
Exp.Opcode == Instruction::ShuffleVector))
3372 if (
Exp.Commutative) {
3373 assert(
Exp.VarArgs.size() >= 2 &&
"Unsupported commutative instruction!");
3374 if (
Exp.VarArgs[0] >
Exp.VarArgs[1]) {
3376 uint32_t Opcode =
Exp.Opcode >> 8;
3377 if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
3378 Exp.Opcode = (Opcode << 8) |
3384 if (uint32_t NewNum = ExpressionNumbering[Exp]) {
3385 if (
Exp.Opcode == Instruction::Call && NewNum != Num)
3386 return areCallValsEqual(Num, NewNum,
Pred, PhiBlock, LeaderTable) ? NewNum
3398 PhiTranslateTable.erase({Num, Pred});
3408 if (Leaders.empty())
3411 Value *Val =
nullptr;
3412 for (
const auto &Entry : Leaders) {
3435 "No edge between these basic blocks!");
3436 return Pred !=
nullptr;
3439void GVNPassImpl::assignBlockRPONumber(
Function &
F) {
3440 BlockRPONumber.clear();
3441 uint32_t NextBlockNumber = 1;
3442 ReversePostOrderTraversal<Function *> RPOT(&
F);
3443 for (BasicBlock *BB : RPOT)
3444 BlockRPONumber[BB] = NextBlockNumber++;
3445 InvalidBlockRPONumbers =
false;
3453bool GVNPassImpl::propagateEquality(
3455 const std::variant<BasicBlockEdge, Instruction *> &Root) {
3457 SmallDenseSet<std::pair<Value *, Value *>, 4> Visited;
3461 if (
const BasicBlockEdge *
Edge = std::get_if<BasicBlockEdge>(&Root)) {
3468 for (
const auto *Node : DT->getNode(
I->getParent())->children())
3472 while (!Worklist.
empty()) {
3473 std::pair<Value*, Value*> Item = Worklist.
pop_back_val();
3474 LHS = Item.first;
RHS = Item.second;
3488 const DataLayout &
DL =
3497 uint32_t LVN = VN.lookupOrAdd(
LHS);
3502 uint32_t RVN = VN.lookupOrAdd(
RHS);
3509 if (!Visited.
insert({LHS, RHS}).second)
3522 for (
const BasicBlock *BB : DominatedBlocks)
3523 LeaderTable.insert(LVN,
RHS, BB);
3530 auto CanReplacePointersCallBack = [&
DL](
const Use &
U,
const Value *To) {
3533 unsigned NumReplacements;
3534 if (
const BasicBlockEdge *
Edge = std::get_if<BasicBlockEdge>(&Root))
3536 LHS,
RHS, *DT, *
Edge, CanReplacePointersCallBack);
3539 LHS,
RHS, *DT, std::get<Instruction *>(Root),
3540 CanReplacePointersCallBack);
3542 if (NumReplacements > 0) {
3544 NumGVNEqProp += NumReplacements;
3547 MD->invalidateCachedPointerInfo(
LHS);
3564 bool IsKnownFalse = !IsKnownTrue;
3580 Value *Op0 =
Cmp->getOperand(0), *Op1 =
Cmp->getOperand(1);
3585 if (
Cmp->isEquivalence(IsKnownFalse))
3586 Worklist.
push_back(std::make_pair(Op0, Op1));
3590 Constant *NotVal = ConstantInt::get(
Cmp->getType(), IsKnownFalse);
3594 uint32_t NextNum = VN.getNextUnusedValueNumber();
3595 uint32_t Num = VN.lookupOrAddCmp(
Cmp->getOpcode(), NotPred, Op0, Op1);
3598 if (Num < NextNum) {
3599 for (
const auto &Entry : LeaderTable.getLeaders(Num)) {
3604 if (
const BasicBlockEdge *
Edge = std::get_if<BasicBlockEdge>(&Root)) {
3605 if (!DT->dominates(
Entry.BB,
Edge->getStart()) &&
3606 !DT->dominates(
Edge->getEnd(),
Entry.BB))
3609 auto *InstBB = std::get<Instruction *>(Root)->getParent();
3610 if (!DT->dominates(
Entry.BB, InstBB) &&
3611 !DT->dominates(InstBB,
Entry.BB))
3617 unsigned NumReplacements;
3618 if (
const BasicBlockEdge *
Edge = std::get_if<BasicBlockEdge>(&Root))
3623 NotCmp, NotVal, *DT, std::get<Instruction *>(Root));
3624 Changed |= NumReplacements > 0;
3625 NumGVNEqProp += NumReplacements;
3628 MD->invalidateCachedPointerInfo(NotCmp);
3636 for (
const BasicBlock *BB : DominatedBlocks)
3637 LeaderTable.insert(Num, NotVal, BB);
3646 Worklist.
emplace_back(
A, ConstantInt::get(
A->getType(), IsKnownTrue));
3651 Worklist.
emplace_back(
A, ConstantInt::get(
A->getType(), !IsKnownTrue));
3659bool GVNPassImpl::replaceWithEquivalentCmp(
CmpInst *Cmp) {
3661 uint32_t Num = VN.lookupCmp(
Cmp->getOpcode(),
Pred,
Cmp->getOperand(0),
3662 Cmp->getOperand(1));
3664 return findLeader(
Cmp->getParent(), Num);
3669 if (
Value *Repl = FindCmpLeader(
Cmp->getInversePredicate())) {
3672 Repl, Repl->getName() +
".not",
Cmp->getIterator());
3673 Not->setDebugLoc(
Cmp->getDebugLoc());
3674 Cmp->replaceAllUsesWith(Not);
3681 if (ICmp && ICmp->hasSameSign() && !ICmp->isEquality()) {
3682 if (
Value *Repl = FindCmpLeader(
3699 const DataLayout &
DL =
I->getDataLayout();
3702 if (!
I->use_empty()) {
3705 ICF->removeUsersOf(
I);
3706 I->replaceAllUsesWith(
V);
3714 if (MD &&
V->getType()->isPtrOrPtrVectorTy())
3715 MD->invalidateCachedPointerInfo(
V);
3722 return processAssumeIntrinsic(Assume);
3725 if (processLoad(
Load))
3728 unsigned Num = VN.lookupOrAdd(
Load);
3729 LeaderTable.insert(Num,
Load,
Load->getParent());
3741 return processFoldableCondBr(BI);
3743 Value *BranchCond = BI->getCondition();
3747 if (TrueSucc == FalseSucc)
3754 BasicBlockEdge TrueE(Parent, TrueSucc);
3755 Changed |= propagateEquality(BranchCond, TrueVal, TrueE);
3758 BasicBlockEdge FalseE(Parent, FalseSucc);
3759 Changed |= propagateEquality(BranchCond, FalseVal, FalseE);
3766 Value *SwitchCond =
SI->getCondition();
3771 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
3773 ++SwitchEdges[Succ];
3775 for (
const auto &Case :
SI->cases()) {
3778 if (SwitchEdges.
lookup(Dst) == 1) {
3779 BasicBlockEdge
E(Parent, Dst);
3780 Changed |= propagateEquality(SwitchCond, Case.getCaseValue(),
E);
3788 if (
I->getType()->isVoidTy())
3791 uint32_t NextNum = VN.getNextUnusedValueNumber();
3792 unsigned Num = VN.lookupOrAdd(
I);
3797 LeaderTable.insert(Num,
I,
I->getParent());
3804 const DataLayout &
DL =
I->getDataLayout();
3805 unsigned AS = PTA->getPointerAddressSpace();
3806 if (
DL.getAddressSizeInBits(AS) ==
DL.getPointerSizeInBits(AS) &&
3807 !
DL.hasUnstableRepresentation(AS)) {
3809 VN.lookupPtrToInt(PTA->getPointerOperand(), PTA->getType());
3810 if (
Value *PTI = findLeader(
I->getParent(), PTINum)) {
3822 Value *Repl = Num < NextNum ? findLeader(
I->getParent(), Num) : nullptr;
3828 LeaderTable.insert(Num,
I,
I->getParent());
3841 MD->invalidateCachedPointerInfo(Repl);
3856 Opts->enable_gvn_memoryssa)
3858 "mutually exclusive",
3865 VN.setAliasAnalysis(&RunAA);
3867 ImplicitControlFlowTracking ImplicitCFT;
3876 InvalidBlockRPONumbers =
true;
3877 MemorySSAUpdater Updater(MSSA);
3878 MSSAU = MSSA ? &Updater :
nullptr;
3881 bool ShouldContinue =
true;
3883 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
3895 EarliestEscapeAnalysis RunEA(*DT, &LI);
3896 EA = MSSA ? &RunEA :
nullptr;
3898 unsigned Iteration = 0;
3899 while (ShouldContinue) {
3902 ShouldContinue = iterateOnFunction(
F);
3910 assignValNumForDeadCode();
3911 bool PREChanged =
true;
3912 while (PREChanged) {
3913 PREChanged = performPRE(
F);
3923 cleanupGlobalSets();
3934bool GVNPassImpl::processBlock(
BasicBlock *BB) {
3935 if (DeadBlocks.count(BB))
3938 bool ChangedFunction =
false;
3944 SmallPtrSet<PHINode *, 8> PHINodesToRemove;
3946 for (PHINode *PN : PHINodesToRemove) {
3947 removeInstruction(PN);
3950 ChangedFunction |= processInstruction(&Inst);
3951 return ChangedFunction;
3955bool GVNPassImpl::performScalarPREInsertion(
Instruction *Instr,
3957 unsigned int ValNo) {
3963 for (
unsigned I = 0,
E =
Instr->getNumOperands();
I !=
E; ++
I) {
3971 if (!VN.exists(
Op)) {
3975 uint32_t TValNo = VN.phiTranslate(
Pred, Curr, VN.lookup(
Op), LeaderTable);
3994 ICF->insertInstructionTo(Instr,
Pred);
3996 unsigned Num = VN.lookupOrAdd(Instr);
4000 LeaderTable.insert(Num, Instr,
Pred);
4004bool GVNPassImpl::performScalarPRE(
Instruction *CurInst) {
4030 if (CallB->isInlineAsm())
4034 uint32_t ValNo = VN.lookup(CurInst);
4042 unsigned NumWith = 0;
4043 unsigned NumWithout = 0;
4048 if (InvalidBlockRPONumbers)
4049 assignBlockRPONumber(*CurrentBlock->
getParent());
4055 if (!DT->isReachableFromEntry(
P)) {
4060 assert(BlockRPONumber.count(
P) && BlockRPONumber.count(CurrentBlock) &&
4061 "Invalid BlockRPONumber map.");
4062 if (BlockRPONumber[
P] >= BlockRPONumber[CurrentBlock]) {
4067 uint32_t TValNo = VN.phiTranslate(
P, CurrentBlock, ValNo, LeaderTable);
4068 Value *PredV = findLeader(
P, TValNo);
4073 }
else if (PredV == CurInst) {
4085 if (NumWithout > 1 || NumWith == 0)
4093 if (NumWithout != 0) {
4099 if (ICF->isDominatedByICFIFromSameBlock(CurInst))
4112 ToSplit.push_back(std::make_pair(PREPred->
getTerminator(), SuccNum));
4116 PREInstr = CurInst->
clone();
4117 if (!performScalarPREInsertion(PREInstr, PREPred, CurrentBlock, ValNo)) {
4120 verifyRemoved(PREInstr);
4129 assert(PREInstr !=
nullptr || NumWithout == 0);
4135 CurInst->
getName() +
".pre-phi");
4136 Phi->insertBefore(CurrentBlock->begin());
4137 for (
auto &[
V, BB] : PredMap) {
4142 Phi->addIncoming(
V, BB);
4144 Phi->addIncoming(PREInstr, PREPred);
4150 VN.eraseTranslateCacheEntry(ValNo, *CurrentBlock);
4151 LeaderTable.insert(ValNo, Phi, CurrentBlock);
4154 if (MD &&
Phi->getType()->isPtrOrPtrVectorTy())
4155 MD->invalidateCachedPointerInfo(Phi);
4156 LeaderTable.erase(ValNo, CurInst, CurrentBlock);
4159 removeInstruction(CurInst);
4166bool GVNPassImpl::performPRE(
Function &
F) {
4168 for (BasicBlock *CurrentBlock :
depth_first(&
F.getEntryBlock())) {
4170 if (CurrentBlock == &
F.getEntryBlock())
4174 if (CurrentBlock->isEHPad())
4178 BE = CurrentBlock->end();
4181 Changed |= performScalarPRE(CurInst);
4185 if (splitCriticalEdges())
4199 CriticalEdgeSplittingOptions(DT, LI, MSSAU).unsetPreserveLoopSimplify());
4202 MD->invalidateCachedPredecessors();
4203 InvalidBlockRPONumbers =
true;
4210bool GVNPassImpl::splitCriticalEdges() {
4211 if (ToSplit.empty())
4216 std::pair<Instruction *, unsigned>
Edge = ToSplit.pop_back_val();
4218 CriticalEdgeSplittingOptions(DT, LI, MSSAU)) !=
4220 }
while (!ToSplit.empty());
4223 MD->invalidateCachedPredecessors();
4224 InvalidBlockRPONumbers =
true;
4230bool GVNPassImpl::iterateOnFunction(
Function &
F) {
4231 cleanupGlobalSets();
4238 ReversePostOrderTraversal<Function *> RPOT(&
F);
4240 for (BasicBlock *BB : RPOT)
4246void GVNPassImpl::cleanupGlobalSets() {
4248 LeaderTable.clear();
4249 BlockRPONumber.clear();
4251 InvalidBlockRPONumbers =
true;
4256 if (MD) MD->removeInstruction(
I);
4258 EA->removeInstruction(
I);
4260 MSSAU->removeMemoryAccess(
I);
4264 ICF->removeInstruction(
I);
4265 I->eraseFromParent();
4271void GVNPassImpl::verifyRemoved(
const Instruction *Inst)
const {
4272 VN.verifyRemoved(Inst);
4279void GVNPassImpl::addDeadBlock(
BasicBlock *BB) {
4281 SmallSetVector<BasicBlock *, 4>
DF;
4284 while (!NewDead.
empty()) {
4286 if (DeadBlocks.count(
D))
4290 SmallVector<BasicBlock *, 8> Dom;
4291 DT->getDescendants(
D, Dom);
4292 DeadBlocks.insert_range(Dom);
4295 for (BasicBlock *
B : Dom) {
4297 if (DeadBlocks.count(S))
4300 bool AllPredDead =
true;
4302 if (!DeadBlocks.count(
P)) {
4303 AllPredDead =
false;
4323 for (BasicBlock *
B :
DF) {
4324 if (DeadBlocks.count(
B))
4330 for (BasicBlock *
P : Preds) {
4331 if (!DeadBlocks.count(
P))
4336 if (BasicBlock *S = splitCriticalEdges(
P,
B))
4337 DeadBlocks.insert(
P = S);
4343 if (!DeadBlocks.count(
P))
4345 for (PHINode &Phi :
B->phis()) {
4348 MD->invalidateCachedPointerInfo(&Phi);
4367bool GVNPassImpl::processFoldableCondBr(
CondBrInst *BI) {
4378 if (DeadBlocks.count(DeadRoot))
4382 DeadRoot = splitCriticalEdges(BI->
getParent(), DeadRoot);
4384 addDeadBlock(DeadRoot);
4392void GVNPassImpl::assignValNumForDeadCode() {
4393 for (BasicBlock *BB : DeadBlocks) {
4394 for (Instruction &Inst : *BB) {
4395 unsigned ValNum = VN.lookupOrAdd(&Inst);
4396 LeaderTable.insert(ValNum, &Inst, BB);
4427 MSSAWP ? &MSSAWP->getMSSA() :
nullptr);
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Function Alias Analysis false
This file contains the simple types necessary to represent the attributes associated with functions a...
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
early cse Early CSE w MemorySSA
This file provides a data structure for mapping values and expressions to congruence class IDs.
static Value * findDominatingValue(const ScalarOptions &Opts, const MemoryLocation &Loc, Type *LoadTy, Instruction *From, AAResults *AA)
static void reportMayClobberedLoad(LoadInst *Load, Instruction *DepInst, const DominatorTree *DT, OptimizationRemarkEmitter *ORE)
Try to locate the three instruction involved in a missed load-elimination case that is due to an inte...
static Instruction * findInvariantGroupValue(LoadInst *L, DominatorTree &DT)
If a load has !invariant.group, try to find the most-dominating instruction with the same metadata an...
static void reportLoadElim(LoadInst *Load, Value *AvailableValue, OptimizationRemarkEmitter *ORE)
static const Instruction * findMayClobberedPtrAccess(LoadInst *Load, const DominatorTree *DT)
static std::optional< MemoryLocation > maybeLoadStoreLocation(Instruction *I, bool AllowStores, const TargetLibraryInfo *TLI)
Return the memory location accessed by the (masked) load/store instruction I, if the instruction coul...
GVNPassImpl::AvailableValue AvailableValue
static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E, DominatorTree *DT)
There is an edge from 'Src' to 'Dst'.
static bool isValueFullyAvailableInBlock(const ScalarOptions &Opts, BasicBlock *BB, DenseMap< BasicBlock *, AvailabilityState > &FullyAvailableBlocks)
Return true if we can prove that the value we're analyzing is fully available in the specified block.
static bool liesBetween(const Instruction *From, Instruction *Between, const Instruction *To, const DominatorTree *DT)
Assuming To can be reached from both From and Between, does Between lie on every path from From to To...
static bool isLifetimeStart(const Instruction *Inst)
static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl)
static void replaceValuesPerBlockEntry(SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, Value *OldValue, Value *NewValue)
If the specified OldValue exists in ValuesPerBlock, replace its value with NewValue.
GVNPassImpl::AvailableValueInBlock AvailableValueInBlock
@ Unavailable
We know the block is not fully available. This is a fixpoint.
@ Available
We know the block is fully available. This is a fixpoint.
@ SpeculativelyAvailable
We do not know whether the block is fully available or not, but we are currently speculating that it ...
static Value * constructSSAForLoadSet(LoadInst *Load, SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, DominatorTree &DT)
Given a set of loads specified by ValuesPerBlock, construct SSA form, allowing us to eliminate Load.
This file provides the interface for LLVM's Global Value Numbering pass which eliminates fully redund...
This is the interface for a simple mod/ref and alias analysis over globals.
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
This defines the Use class.
This file implements a map that provides insertion order iteration.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
uint64_t IntrinsicInst * II
ppc ctr loops PowerPC CTR Loops Verify
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file contains the declarations for profiling metadata utility functions.
SmallVector< MachineOperand, 4 > Cond
static DominatorTree getDomTree(Function &F)
std::pair< BasicBlock *, BasicBlock * > Edge
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
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 const uint32_t IV[8]
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
GVNLegacyPass(bool ScalarPRE=true)
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
constexpr int32_t getOffset() const
constexpr bool hasOffset() const
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.
Value handle that asserts if the Value is deleted.
This represents the llvm.assume intrinsic.
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 Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
bool isEHPad() const
Return true if this basic block is an exception handling block.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
static LLVM_ABI BinaryOperator * CreateNot(Value *Op, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Value * getArgOperand(unsigned i) const
unsigned arg_size() const
This class represents a function call, abstracting a target machine's calling convention.
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Analysis pass which computes a DominatorTree.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Context-sensitive CaptureAnalysis provider, which computes and caches the earliest common dominator c...
Class representing an expression and its matching format.
FunctionPass class - This class is used to implement most global optimizations.
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
const BasicBlock & getEntryBlock() const
Represents calls to the gc.relocate intrinsic.
leader_iterator & operator++()
bool operator!=(const leader_iterator &Other) const
leader_iterator(const LeaderListNode *C)
reference operator*() const
const LeaderTableEntry value_type
std::forward_iterator_tag iterator_category
std::ptrdiff_t difference_type
bool operator==(const leader_iterator &Other) const
A mapping from value numbers to lists of Value*'s that have that value number.
LLVM_ABI void insert(uint32_t N, Value *V, const BasicBlock *BB)
Push a new Value to the LeaderTable onto the list for its value number.
LLVM_ABI void erase(uint32_t N, Instruction *I, const BasicBlock *BB)
Scan the list of values corresponding to a given value number, and remove the given instruction if en...
iterator_range< leader_iterator > getLeaders(uint32_t N)
The core GVN pass object.
bool isMemDepEnabled() const
bool isScalarPREEnabled() const
bool isLoadPRESplitBackedgeEnabled() const
MemoryDependenceResults & getMemDep() const
AAResults * getAliasAnalysis() const
void salvageAndRemoveInstruction(Instruction *I)
This removes the specified instruction from our various maps and marks it for deletion.
bool isLoadInLoopPREEnabled() const
bool isLoadPREEnabled() const
bool isMemorySSAEnabled() const
DominatorTree & getDominatorTree() const
GVNPassImpl(llvm::GVNOptions Options={})
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
LLVM_ABI GVNPass(GVNOptions Options={})
LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
This class holds the mapping between values and value numbers.
LLVM_ABI uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, Value *LHS, Value *RHS)
Returns the value number of the given comparison, assigning it a new number if it did not have one be...
LLVM_ABI void erase(Value *V)
Remove a value from the value numbering.
LLVM_ABI uint32_t lookup(Value *V, bool Verify=true) const
Returns the value number of the specified value.
LLVM_ABI void add(Value *V, uint32_t Num)
add - Insert a value into the table with a specified value number.
LLVM_ABI void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock)
Erase stale entry from phiTranslate cache so phiTranslate can be computed again.
LLVM_ABI void verifyRemoved(const Value *) const
verifyRemoved - Verify that the value is removed from all internal data structures.
LLVM_ABI uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, uint32_t Num, GVNLeaderMap &LeaderTable)
Wrap phiTranslateImpl to provide caching functionality.
LLVM_ABI uint32_t lookupCmp(unsigned Opcode, CmpInst::Predicate Pred, Value *LHS, Value *RHS)
LLVM_ABI uint32_t lookupOrAdd(MemoryAccess *MA)
LLVM_ABI void clear()
Remove all entries from the ValueTable.
LLVM_ABI bool exists(Value *V) const
Returns true if a value number exists for the specified value.
LLVM_ABI GVNValueTable & operator=(const GVNValueTable &Arg)
LLVM_ABI uint32_t lookupPtrToInt(Value *Ptr, Type *Ty)
Returns the value number of ptrtoint Ptr to \Ty.
LLVM_ABI ~GVNValueTable()
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Legacy wrapper pass to provide the GlobalsAAResult object.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
This class allows to keep track on instructions with implicit control flow.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
LLVM_ABI bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
LLVM_ABI bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
LLVM_ABI void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs={})
Drop all unknown metadata except for debug locations.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
A wrapper class for inspecting calls to intrinsic functions.
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
The legacy pass manager's analysis pass to compute loop information.
This class implements a map that also provides access to all stored values in a deterministic order.
iterator find(const KeyT &Key)
A memory dependence query can return one of three different answers.
bool isClobber() const
Tests if this MemDepResult represents a query that is an instruction clobber dependency.
bool isNonLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the block,...
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.
bool isLocal() const
Tests if this MemDepResult represents a valid local query (Clobber/Def).
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
This is the common base class for memset/memcpy/memmove.
BasicBlock * getBlock() const
An analysis that produces MemoryDependenceResults for a function.
Provides a lazy, caching interface for making common memory aliasing information queries,...
std::vector< NonLocalDepEntry > NonLocalDepInfo
LLVM_ABI MemDepResult getDependency(Instruction *QueryInst)
Returns the instruction on which a memory operation depends.
LLVM_ABI const NonLocalDepInfo & getNonLocalCallDependency(CallBase *QueryCall)
Perform a full dependency query for the specified call, returning the set of blocks that the value is...
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.
Representation for a specific memory location.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
MemoryLocation getWithNewPtr(const Value *NewPtr) const
const Value * Ptr
The address of the start of the location.
static LLVM_ABI MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
BasicBlock * getIncomingBlock(unsigned I) const
Return incoming basic block number i.
MemoryAccess * getIncomingValue(unsigned I) const
Return incoming value number x.
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.
LLVM_ABI MemorySSAWalker * getSkipSelfWalker()
LLVM_ABI void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
LLVM_ABI MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
LLVM_ABI bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in the same basic block, determine whether MemoryAccess A dominates MemoryA...
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
This is an entry in the NonLocalDepInfo cache.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
PHITransAddr - An address value which tracks and handles phi translation.
LLVM_ABI Value * translateValue(BasicBlock *CurBB, BasicBlock *PredBB, const DominatorTree *DT, bool MustDominate)
translateValue - PHI translate the current address up the CFG from CurBB to Pred, updating our state ...
LLVM_ABI bool isPotentiallyPHITranslatable() const
isPotentiallyPHITranslatable - If this needs PHI translation, return true if we have some hope of doi...
bool needsPHITranslationFromBlock(BasicBlock *BB) const
needsPHITranslationFromBlock - Return true if moving from the specified BasicBlock to its predecessor...
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
AnalysisType * getAnalysisIfAvailable() const
getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to get analysis information tha...
static LLVM_ABI PointerType * get(LLVMContext &C, unsigned AddressSpace)
This constructs an opaque pointer to an object in a numbered address space.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
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 & preserve()
Mark an analysis as preserved.
Helper class for SSA formation on a set of values defined in multiple blocks.
LLVM_ABI void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
LLVM_ABI Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block.
LLVM_ABI bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
LLVM_ABI void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
std::pair< SelectInst *, SelectAddrs > getSelectAndAddrs() const
This class represents the LLVM 'select' instruction.
const Value * getFalseValue() const
const Value * getCondition() const
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, const Instruction *MDFrom=nullptr)
const Value * getTrueValue() const
A vector that has set insertion semantics.
bool erase(PtrType Ptr)
Remove pointer from the set.
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.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
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.
LLVM_ABI bool isTokenLikeTy() const
Returns true if this is 'token' or a token-like target type.s.
static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)
bool isPtrOrPtrVectorTy() const
Return true if this is a pointer type or a vector of pointer types.
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isVoidTy() const
Return true if this is 'void'.
static LLVM_ABI UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
bool hasUseList() const
Check if this Value has a use-list.
LLVM_ABI bool canBeFreed() const
Return true if the memory object referred to by V can by freed in the scope for which the SSA value d...
LLVM_ABI void deleteValue()
Delete a pointer to a generic Value.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
An efficient, type-erasing, non-owning reference to a callable.
An opaque object representing a hash code.
const ParentTy * getParent() const
self_iterator getIterator()
A range adaptor for a pair of iterators.
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.
Abstract Attribute helper functions.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ 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.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
auto m_MaskedStore(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2)
Matches MaskedStore Intrinsic.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
Not(const Pred &P) -> Not< Pred >
LLVM_ABI int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr, StoreInst *DepSI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the store at D...
LLVM_ABI Value * getMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &DL)
If analyzeLoadFromClobberingMemInst returned an offset, this function can be used to actually perform...
LLVM_ABI int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the load at De...
LLVM_ABI Value * getValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy, Instruction *InsertPt, Function *F)
If analyzeLoadFromClobberingStore/Load returned an offset, this function can be used to actually perf...
LLVM_ABI int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr, MemIntrinsic *DepMI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the memory int...
LLVM_ABI bool canCoerceMustAliasedValueToLoad(Value *StoredVal, Type *LoadTy, Function *F)
Return true if CoerceAvailableValueToLoadType would succeed if it was called.
Add a small namespace to avoid name clashes with the classes used in the streaming interface.
NodeAddr< InstrNode * > Instr
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
NodeAddr< NodeBase * > Node
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI cl::opt< bool > ProfcheckDisableMetadataFixes
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
hash_code hash_value(const FixedPointSemantics &Val)
LLVM_ABI Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
LLVM_ABI unsigned replaceDominatedUsesWithIf(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge, function_ref< bool(const Use &U, const Value *To)> ShouldReplace)
Replace each use of 'From' with 'To' if that use is dominated by the given edge and the callback Shou...
RelativeUniformCounterPtr Values
LLVM_ABI unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
auto pred_end(const MachineBasicBlock *BB)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI FunctionPass * createGVNPass(bool ScalarPRE)
Create a legacy GVN pass.
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...
auto successors(const MachineBasicBlock *BB)
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
@ Load
The value being inserted comes from a load (InsertElement only).
constexpr from_range_t from_range
LLVM_ABI bool isStorePreservingMemoryLocation(const StoreInst *SI, const MemoryLocation &MemLoc, Align MemLocAlign, BatchAAResults &AA, unsigned ScanLimit)
Check whether SI, which may alias MemLoc, can be safely skipped.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
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...
LLVM_ABI bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
LLVM_ABI bool isAssumeWithEmptyBundle(const AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
const ScalarOptions & getScalarOptions(const LLVMContext &C)
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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 canReplacePointersInUseIfEqual(const Use &U, const Value *To, const DataLayout &DL)
LLVM_ABI bool canReplacePointersIfEqual(const Value *From, const Value *To, const DataLayout &DL)
Returns true if a pointer value From can be replaced with another pointer value \To if they are deeme...
bool isModSet(const ModRefInfo MRI)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)
LLVM_ABI void patchReplacementInstruction(Instruction *I, Value *Repl, bool DoesKMove=false)
Patch the replacement so that it is not more restrictive than the value being replaced.
LLVM_ABI void initializeGVNLegacyPassPass(PassRegistry &)
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
LLVM_ABI 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.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
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...
@ Success
The lock was released successfully.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
@ Ref
The access may reference the value stored in memory.
@ NoModRef
The access neither references nor modifies the value stored in memory.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
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.
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI FunctionPass * createGVNPass()
LLVM_ABI bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr, const CycleInfo *CI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
DWARFExpression::Operation Op
LLVM_ABI BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
LLVM_ABI bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
LLVM_ABI bool willNotFreeBetween(const Instruction *Assume, const Instruction *CtxI, const DominatorTree *DT=nullptr)
Returns true, if no instruction between Assume and CtxI may free (including through synchronization).
constexpr unsigned BitWidth
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
constexpr bool valueOr(BoolOrDefault X, bool Default)
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
bool pred_empty(const BasicBlock *BB)
iterator_range< df_iterator< T > > depth_first(const T &G)
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 bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
bool isStrongerThan(AtomicOrdering AO, AtomicOrdering Other)
Returns true if ao is stronger than other as defined by the AtomicOrdering lattice,...
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Represents an AvailableValue which can be rematerialized at the end of the associated BasicBlock.
AvailableValue AV
AV - The actual available value.
BasicBlock * BB
BB - The basic block in question.
static AvailableValueInBlock get(BasicBlock *BB, Value *V, unsigned Offset=0)
Value * MaterializeAdjustedValue(LoadInst *Load) const
Emit code at the end of this block to adjust the value defined here to the specified type.
static AvailableValueInBlock getUndef(BasicBlock *BB)
static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV)
Represents a particular available value that we know how to materialize.
bool isMemIntrinValue() const
Value * getSimpleValue() const
SelectInst * getSelectInstr() const
static AvailableValue getUndef()
Value * Val
Val - The value that is live out of the block.
ValType Kind
Kind of the live-out value.
bool isCoercedLoadValue() const
static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset=0)
unsigned Offset
Offset - The byte offset in Val that is interesting for the load query.
LoadInst * getCoercedLoadValue() const
static AvailableValue get(Value *V, unsigned Offset=0)
bool isUndefValue() const
static AvailableValue getSelect(SelectInst *Sel, Value *V1, Value *V2)
bool isSelectValue() const
Value * V1
V1, V2 - The dominating non-clobbered values of SelectVal.
static AvailableValue getLoad(LoadInst *Load, unsigned Offset=0)
Value * MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt) const
Emit code at the specified insertion point to adjust the value defined here to the specified type.
MemIntrinsic * getMemIntrinValue() const
bool isSimpleValue() const
This struct is a compact representation of a valid (non-zero power of two) alignment.
static unsigned getHashValue(const GVNValueTable::Expression &E)
static bool isEqual(const GVNValueTable::Expression &LHS, const GVNValueTable::Expression &RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
LeaderTableEntry(Value *V, const BasicBlock *BB)
A set of parameters to control various transforms performed by GVN pass.
Expression(uint32_t Op=~2U)
SmallVector< uint32_t, 4 > VarArgs
bool operator==(const Expression &Other) const
friend hash_code hash_value(const Expression &Value)