Go to the documentation of this file.
82 using namespace llvm::gvn;
84 using namespace PatternMatch;
86 #define DEBUG_TYPE "gvn"
88 STATISTIC(NumGVNInstr,
"Number of instructions deleted");
89 STATISTIC(NumGVNLoad,
"Number of loads deleted");
90 STATISTIC(NumGVNPRE,
"Number of instructions PRE'd");
91 STATISTIC(NumGVNBlocks,
"Number of blocks merged");
92 STATISTIC(NumGVNSimpl,
"Number of instructions simplified");
93 STATISTIC(NumGVNEqProp,
"Number of equalities propagated");
94 STATISTIC(NumPRELoad,
"Number of loads PRE'd");
95 STATISTIC(NumPRELoopLoad,
"Number of loop loads PRE'd");
97 STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax,
98 "Number of blocks speculated as available in "
99 "IsValueFullyAvailableInBlock(), max");
100 STATISTIC(MaxBBSpeculationCutoffReachedTimes,
101 "Number of times we we reached gvn-max-block-speculations cut-off "
102 "preventing further exploration");
115 cl::desc(
"Max number of dependences to attempt Load PRE (default = 100)"));
120 cl::desc(
"Max number of blocks we're willing to speculate on (and recurse "
121 "into) when deducing if a value is fully available or not in GVN "
135 if (opcode != other.
opcode)
137 if (opcode == ~0U || opcode == ~1U)
199 Res.
Kind = ValType::SimpleVal;
207 Res.
Kind = ValType::MemIntrin;
215 Res.
Kind = ValType::LoadVal;
223 Res.
Kind = ValType::UndefVal;
231 Res.
Kind = ValType::SelectVal;
243 assert(isSimpleValue() &&
"Wrong accessor");
248 assert(isCoercedLoadValue() &&
"Wrong accessor");
249 return cast<LoadInst>(Val);
253 assert(isMemIntrinValue() &&
"Wrong accessor");
254 return cast<MemIntrinsic>(Val);
258 assert(isSelectValue() &&
"Wrong accessor");
259 return cast<SelectInst>(Val);
285 unsigned Offset = 0) {
310 e.type =
I->getType();
311 e.opcode =
I->getOpcode();
316 e.varargs.push_back(lookupOrAdd(GCR->getOperand(0)));
317 e.varargs.push_back(lookupOrAdd(GCR->getBasePtr()));
318 e.varargs.push_back(lookupOrAdd(GCR->getDerivedPtr()));
320 for (
Use &
Op :
I->operands())
321 e.varargs.push_back(lookupOrAdd(
Op));
323 if (
I->isCommutative()) {
328 assert(
I->getNumOperands() >= 2 &&
"Unsupported commutative instruction!");
329 if (
e.varargs[0] >
e.varargs[1])
331 e.commutative =
true;
334 if (
auto *
C = dyn_cast<CmpInst>(
I)) {
337 if (
e.varargs[0] >
e.varargs[1]) {
342 e.commutative =
true;
343 }
else if (
auto *
E = dyn_cast<InsertValueInst>(
I)) {
344 e.varargs.append(
E->idx_begin(),
E->idx_end());
345 }
else if (
auto *SVI = dyn_cast<ShuffleVectorInst>(
I)) {
347 e.varargs.append(ShuffleMask.
begin(), ShuffleMask.
end());
355 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
356 "Not a comparison!");
359 e.varargs.push_back(lookupOrAdd(
LHS));
360 e.varargs.push_back(lookupOrAdd(
RHS));
363 if (
e.varargs[0] >
e.varargs[1]) {
368 e.commutative =
true;
374 assert(EI &&
"Not an ExtractValueInst?");
385 e.varargs.push_back(lookupOrAdd(WO->
getLHS()));
386 e.varargs.push_back(lookupOrAdd(WO->
getRHS()));
394 e.varargs.push_back(lookupOrAdd(
Op));
403 Type *PtrTy =
GEP->getType()->getScalarType();
405 unsigned BitWidth =
DL.getIndexTypeSizeInBits(PtrTy);
409 GEP->collectOffset(
DL,
BitWidth, VariableOffsets, ConstantOffset)) {
413 E.opcode =
GEP->getOpcode();
415 E.varargs.push_back(lookupOrAdd(
GEP->getPointerOperand()));
416 for (
const auto &Pair : VariableOffsets) {
417 E.varargs.push_back(lookupOrAdd(Pair.first));
420 if (!ConstantOffset.isZero())
426 E.opcode =
GEP->getOpcode();
427 E.type =
GEP->getSourceElementType();
429 E.varargs.push_back(lookupOrAdd(
Op));
447 valueNumbering.insert(std::make_pair(V, num));
448 if (
PHINode *PN = dyn_cast<PHINode>(V))
449 NumberingPhi[num] = PN;
453 if (
AA->doesNotAccessMemory(
C)) {
455 uint32_t e = assignExpNewValueNum(exp).first;
456 valueNumbering[
C] =
e;
458 }
else if (MD &&
AA->onlyReadsMemory(
C)) {
460 auto ValNum = assignExpNewValueNum(exp);
462 valueNumbering[
C] = ValNum.first;
469 valueNumbering[
C] = nextValueNumber;
470 return nextValueNumber++;
473 if (local_dep.
isDef()) {
478 if (!local_cdep || local_cdep->
arg_size() !=
C->arg_size()) {
479 valueNumbering[
C] = nextValueNumber;
480 return nextValueNumber++;
483 for (
unsigned i = 0,
e =
C->arg_size();
i <
e; ++
i) {
484 uint32_t c_vn = lookupOrAdd(
C->getArgOperand(
i));
487 valueNumbering[
C] = nextValueNumber;
488 return nextValueNumber++;
492 uint32_t v = lookupOrAdd(local_cdep);
493 valueNumbering[
C] = v;
499 MD->getNonLocalCallDependency(
C);
505 for (
unsigned i = 0,
e = deps.size();
i !=
e; ++
i) {
507 if (
I->getResult().isNonLocal())
512 if (!
I->getResult().isDef() || cdep !=
nullptr) {
517 CallInst *NonLocalDepCall = dyn_cast<CallInst>(
I->getResult().getInst());
519 if (NonLocalDepCall && DT->properlyDominates(
I->getBB(),
C->getParent())){
520 cdep = NonLocalDepCall;
529 valueNumbering[
C] = nextValueNumber;
530 return nextValueNumber++;
534 valueNumbering[
C] = nextValueNumber;
535 return nextValueNumber++;
537 for (
unsigned i = 0,
e =
C->arg_size();
i <
e; ++
i) {
538 uint32_t c_vn = lookupOrAdd(
C->getArgOperand(
i));
541 valueNumbering[
C] = nextValueNumber;
542 return nextValueNumber++;
547 valueNumbering[
C] = v;
550 valueNumbering[
C] = nextValueNumber;
551 return nextValueNumber++;
557 return valueNumbering.count(V) != 0;
564 if (
VI != valueNumbering.end())
567 if (!isa<Instruction>(V)) {
568 valueNumbering[V] = nextValueNumber;
569 return nextValueNumber++;
574 switch (
I->getOpcode()) {
576 return lookupOrAddCall(cast<CallInst>(
I));
577 case Instruction::FNeg:
579 case Instruction::FAdd:
580 case Instruction::Sub:
581 case Instruction::FSub:
583 case Instruction::FMul:
584 case Instruction::UDiv:
585 case Instruction::SDiv:
586 case Instruction::FDiv:
587 case Instruction::URem:
588 case Instruction::SRem:
589 case Instruction::FRem:
590 case Instruction::Shl:
591 case Instruction::LShr:
592 case Instruction::AShr:
593 case Instruction::And:
594 case Instruction::Or:
595 case Instruction::Xor:
596 case Instruction::ICmp:
597 case Instruction::FCmp:
598 case Instruction::Trunc:
599 case Instruction::ZExt:
600 case Instruction::SExt:
601 case Instruction::FPToUI:
602 case Instruction::FPToSI:
603 case Instruction::UIToFP:
604 case Instruction::SIToFP:
605 case Instruction::FPTrunc:
606 case Instruction::FPExt:
607 case Instruction::PtrToInt:
608 case Instruction::IntToPtr:
609 case Instruction::AddrSpaceCast:
610 case Instruction::BitCast:
612 case Instruction::Freeze:
613 case Instruction::ExtractElement:
614 case Instruction::InsertElement:
615 case Instruction::ShuffleVector:
616 case Instruction::InsertValue:
619 case Instruction::GetElementPtr:
620 exp = createGEPExpr(cast<GetElementPtrInst>(
I));
622 case Instruction::ExtractValue:
623 exp = createExtractvalueExpr(cast<ExtractValueInst>(
I));
625 case Instruction::PHI:
626 valueNumbering[V] = nextValueNumber;
627 NumberingPhi[nextValueNumber] = cast<PHINode>(V);
628 return nextValueNumber++;
630 valueNumbering[V] = nextValueNumber;
631 return nextValueNumber++;
634 uint32_t e = assignExpNewValueNum(exp).first;
635 valueNumbering[V] =
e;
644 assert(
VI != valueNumbering.end() &&
"Value not numbered?");
647 return (
VI != valueNumbering.end()) ?
VI->second : 0;
658 return assignExpNewValueNum(exp).first;
663 valueNumbering.clear();
664 expressionNumbering.clear();
665 NumberingPhi.clear();
666 PhiTranslateTable.clear();
675 uint32_t Num = valueNumbering.lookup(V);
676 valueNumbering.erase(V);
679 NumberingPhi.erase(Num);
686 I = valueNumbering.begin(),
E = valueNumbering.end();
I !=
E; ++
I) {
687 assert(
I->first != V &&
"Inst still occurs in value numbering map!");
708 return Options.AllowLoadPRESplitBackedge.value_or(
730 bool Changed =
runImpl(
F, AC, DT, TLI,
AA, MemDep, LI, &ORE,
731 MSSA ? &MSSA->getMSSA() :
nullptr);
747 OS, MapClassName2PassName);
751 OS << (
Options.AllowPRE.getValue() ?
"" :
"no-") <<
"pre;";
753 OS << (
Options.AllowLoadPRE.getValue() ?
"" :
"no-") <<
"load-pre;";
755 OS << (
Options.AllowLoadPRESplitBackedge.getValue() ?
"" :
"no-")
756 <<
"split-backedge-load-pre;";
758 OS << (
Options.AllowMemDep.getValue() ?
"" :
"no-") <<
"memdep";
762 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
766 errs() <<
I.first <<
"\n";
801 unsigned NumNewNewSpeculativelyAvailableBBs = 0;
809 while (!Worklist.empty()) {
813 std::pair<DenseMap<BasicBlock *, AvailabilityState>::iterator,
bool>
IV =
821 UnavailableBB = CurrBB;
832 ++NumNewNewSpeculativelyAvailableBBs;
838 MaxBBSpeculationCutoffReachedTimes += (
int)OutOfBudget;
840 UnavailableBB = CurrBB;
846 NewSpeculativelyAvailableBBs.
insert(CurrBB);
852 #if LLVM_ENABLE_STATS
853 IsValueFullyAvailableInBlockNumSpeculationsMax.updateMax(
854 NumNewNewSpeculativelyAvailableBBs);
859 auto MarkAsFixpointAndEnqueueSuccessors =
861 auto It = FullyAvailableBlocks.
find(
BB);
862 if (It == FullyAvailableBlocks.
end())
869 State = FixpointState;
872 "Found a speculatively available successor leftover?");
887 while (!Worklist.empty())
888 MarkAsFixpointAndEnqueueSuccessors(Worklist.
pop_back_val(),
896 while (!Worklist.empty())
897 MarkAsFixpointAndEnqueueSuccessors(Worklist.
pop_back_val(),
901 "Must have fixed all the new speculatively available blocks.");
904 return !UnavailableBB;
916 if (ValuesPerBlock.size() == 1 &&
918 Load->getParent())) {
919 assert(!ValuesPerBlock[0].AV.isUndefValue() &&
920 "Dead BB dominate this block");
921 return ValuesPerBlock[0].MaterializeAdjustedValue(
Load, gvn);
932 if (AV.AV.isUndefValue())
942 if (
BB ==
Load->getParent() &&
943 ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() ==
Load) ||
944 (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() ==
Load)))
957 auto *LI = dyn_cast<LoadInst>(U);
958 if (LI && LI->getType() == LoadTy && LI->getParent() == Sel->
getParent() &&
971 if (isSimpleValue()) {
972 Res = getSimpleValue();
973 if (Res->
getType() != LoadTy) {
976 LLVM_DEBUG(
dbgs() <<
"GVN COERCED NONLOCAL VAL:\nOffset: " << Offset
977 <<
" " << *getSimpleValue() <<
'\n'
981 }
else if (isCoercedLoadValue()) {
982 LoadInst *CoercedLoad = getCoercedLoadValue();
983 if (CoercedLoad->
getType() == LoadTy && Offset == 0) {
993 LLVM_DEBUG(
dbgs() <<
"GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset
994 <<
" " << *getCoercedLoadValue() <<
'\n'
998 }
else if (isMemIntrinValue()) {
1001 LLVM_DEBUG(
dbgs() <<
"GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
1002 <<
" " << *getMemIntrinValue() <<
'\n'
1005 }
else if (isSelectValue()) {
1013 "must be able to obtain dominating loads for both value operands of "
1019 assert(Res &&
"failed to materialize?");
1024 if (
const IntrinsicInst* II = dyn_cast<IntrinsicInst>(Inst))
1025 return II->getIntrinsicID() == Intrinsic::lifetime_start;
1045 using namespace ore;
1047 User *OtherAccess =
nullptr;
1050 R <<
"load of type " <<
NV(
"Type",
Load->getType()) <<
" not eliminated"
1053 for (
auto *U :
Load->getPointerOperand()->users()) {
1054 if (U !=
Load && (isa<LoadInst>(U) || isa<StoreInst>(U)) &&
1059 if (DT->
dominates(cast<Instruction>(OtherAccess), cast<Instruction>(U)))
1063 cast<Instruction>(OtherAccess)));
1072 for (
auto *U :
Load->getPointerOperand()->users()) {
1073 if (U !=
Load && (isa<LoadInst>(U) || isa<StoreInst>(U)) &&
1077 if (
liesBetween(cast<Instruction>(OtherAccess), cast<Instruction>(U),
1081 cast<Instruction>(OtherAccess),
Load, DT)) {
1084 OtherAccess =
nullptr;
1095 R <<
" in favor of " <<
NV(
"OtherAccess", OtherAccess);
1097 R <<
" because it is clobbered by " <<
NV(
"ClobberedBy", DepInfo.
getInst());
1114 auto *Sel = dyn_cast_or_null<SelectInst>(Address);
1129 return isModSet(AA->getModRefInfo(&I, L1Loc)) ||
1130 isModSet(AA->getModRefInfo(&I, L2Loc));
1140 assert(isa<SelectInst>(Address));
1142 Load->getParent(),
Load->getIterator(), Address,
Load->getType(),
1143 getDominatorTree(), getAliasAnalysis())) {
1151 "expected a local dependence");
1152 assert(
Load->isUnordered() &&
"rules below are incorrect for ordered access");
1161 if (
StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {
1163 if (Address &&
Load->isAtomic() <= DepSI->isAtomic()) {
1177 if (
LoadInst *DepLoad = dyn_cast<LoadInst>(DepInst)) {
1181 if (DepLoad !=
Load && Address &&
1182 Load->isAtomic() <= DepLoad->isAtomic()) {
1189 const auto ClobberOff = MD->getClobberOffset(DepLoad);
1191 Offset = (ClobberOff ==
None || *ClobberOff < 0) ? -1 : *ClobberOff;
1205 if (
MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1206 if (Address && !
Load->isAtomic()) {
1220 dbgs() <<
" is clobbered by " << *DepInst <<
'\n';);
1241 if (
StoreInst *
S = dyn_cast<StoreInst>(DepInst)) {
1250 if (
S->isAtomic() <
Load->isAtomic())
1257 if (
LoadInst *
LD = dyn_cast<LoadInst>(DepInst)) {
1265 if (
LD->isAtomic() <
Load->isAtomic())
1276 dbgs() <<
" has unknown def " << *DepInst <<
'\n';);
1280 void GVNPass::AnalyzeLoadAvailability(
LoadInst *
Load, LoadDepVect &Deps,
1281 AvailValInBlkVect &ValuesPerBlock,
1282 UnavailBlkVect &UnavailableBlocks) {
1287 unsigned NumDeps = Deps.size();
1288 for (
unsigned i = 0,
e = NumDeps;
i !=
e; ++
i) {
1292 if (DeadBlocks.count(DepBB)) {
1306 DepBB, DepBB->
end(), Address,
Load->getType(), getDominatorTree(),
1307 getAliasAnalysis())) {
1308 ValuesPerBlock.push_back(
1312 UnavailableBlocks.push_back(DepBB);
1317 if (AnalyzeLoadAvailability(
Load, DepInfo, Address, AV)) {
1324 UnavailableBlocks.push_back(DepBB);
1328 assert(NumDeps == ValuesPerBlock.size() + UnavailableBlocks.size() &&
1329 "post condition violation");
1332 void GVNPass::eliminatePartiallyRedundantLoad(
1335 for (
const auto &AvailableLoad : AvailableLoads) {
1336 BasicBlock *UnavailableBlock = AvailableLoad.first;
1337 Value *LoadPtr = AvailableLoad.second;
1341 Load->isVolatile(),
Load->getAlign(),
Load->getOrdering(),
1343 NewLoad->setDebugLoc(
Load->getDebugLoc());
1345 auto *MSSA = MSSAU->getMemorySSA();
1349 auto *LoadAcc = MSSA->getMemoryAccess(
Load);
1351 isa<MemoryDef>(LoadAcc) ? LoadAcc : LoadAcc->getDefiningAccess();
1352 auto *NewAccess = MSSAU->createMemoryAccessInBB(
1353 NewLoad, DefiningAcc, NewLoad->getParent(),
1355 if (
auto *NewDef = dyn_cast<MemoryDef>(NewAccess))
1356 MSSAU->insertDef(NewDef,
true);
1358 MSSAU->insertUse(cast<MemoryUse>(NewAccess),
true);
1364 NewLoad->setAAMetadata(Tags);
1366 if (
auto *MD =
Load->getMetadata(LLVMContext::MD_invariant_load))
1367 NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
1368 if (
auto *InvGroupMD =
Load->getMetadata(LLVMContext::MD_invariant_group))
1369 NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
1370 if (
auto *RangeMD =
Load->getMetadata(LLVMContext::MD_range))
1371 NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);
1372 if (
auto *AccessMD =
Load->getMetadata(LLVMContext::MD_access_group))
1374 LI->getLoopFor(
Load->getParent()) == LI->getLoopFor(UnavailableBlock))
1375 NewLoad->setMetadata(LLVMContext::MD_access_group, AccessMD);
1384 ValuesPerBlock.push_back(
1386 MD->invalidateCachedPointerInfo(LoadPtr);
1392 Load->replaceAllUsesWith(V);
1393 if (isa<PHINode>(V))
1396 I->setDebugLoc(
Load->getDebugLoc());
1398 MD->invalidateCachedPointerInfo(V);
1399 markInstructionForDeletion(
Load);
1402 <<
"load eliminated by PRE";
1406 bool GVNPass::PerformLoadPRE(
LoadInst *
Load, AvailValInBlkVect &ValuesPerBlock,
1407 UnavailBlkVect &UnavailableBlocks) {
1417 UnavailableBlocks.end());
1439 bool MustEnsureSafetyOfSpeculativeExecution =
1440 ICF->isDominatedByICFIFromSameBlock(
Load);
1444 if (TmpBB == LoadBB)
1446 if (Blockers.count(TmpBB))
1458 MustEnsureSafetyOfSpeculativeExecution =
1459 MustEnsureSafetyOfSpeculativeExecution || ICF->hasICF(TmpBB);
1471 for (
BasicBlock *UnavailableBB : UnavailableBlocks)
1478 if (Pred->getTerminator()->isEHPad()) {
1480 dbgs() <<
"COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
1481 << Pred->getName() <<
"': " << *
Load <<
'\n');
1489 if (Pred->getTerminator()->getNumSuccessors() != 1) {
1490 if (isa<IndirectBrInst>(Pred->getTerminator())) {
1492 dbgs() <<
"COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
1493 << Pred->getName() <<
"': " << *
Load <<
'\n');
1498 if (isa<CallBrInst>(Pred->getTerminator())) {
1500 dbgs() <<
"COULD NOT PRE LOAD BECAUSE OF CALLBR CRITICAL EDGE '"
1501 << Pred->getName() <<
"': " << *
Load <<
'\n');
1507 dbgs() <<
"COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
1508 << Pred->getName() <<
"': " << *
Load <<
'\n');
1513 if (!isLoadPRESplitBackedgeEnabled())
1514 if (DT->dominates(LoadBB, Pred)) {
1517 <<
"COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
1518 << Pred->getName() <<
"': " << *
Load <<
'\n');
1522 CriticalEdgePred.push_back(Pred);
1525 PredLoads[Pred] =
nullptr;
1530 unsigned NumUnavailablePreds = PredLoads.
size() + CriticalEdgePred.size();
1531 assert(NumUnavailablePreds != 0 &&
1532 "Fully available value should already be eliminated!");
1538 if (NumUnavailablePreds != 1)
1543 if (MustEnsureSafetyOfSpeculativeExecution) {
1544 if (CriticalEdgePred.size())
1547 for (
auto &
PL : PredLoads)
1553 for (
BasicBlock *OrigPred : CriticalEdgePred) {
1554 BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);
1555 assert(!PredLoads.count(OrigPred) &&
"Split edges shouldn't be in map!");
1556 PredLoads[NewPred] =
nullptr;
1557 LLVM_DEBUG(
dbgs() <<
"Split critical edge " << OrigPred->getName() <<
"->"
1558 << LoadBB->
getName() <<
'\n');
1562 bool CanDoPRE =
true;
1565 for (
auto &PredLoad : PredLoads) {
1566 BasicBlock *UnavailablePred = PredLoad.first;
1576 Value *LoadPtr =
Load->getPointerOperand();
1578 while (Cur != LoadBB) {
1580 LoadPtr =
Address.PHITranslateWithInsertion(
1591 LoadPtr =
Address.PHITranslateWithInsertion(LoadBB, UnavailablePred, *DT,
1598 << *
Load->getPointerOperand() <<
"\n");
1603 PredLoad.second = LoadPtr;
1607 while (!NewInsts.empty()) {
1617 return !CriticalEdgePred.empty();
1624 LLVM_DEBUG(
if (!NewInsts.empty())
dbgs() <<
"INSERTED " << NewInsts.size()
1625 <<
" INSTS: " << *NewInsts.back()
1633 I->updateLocationAfterHoist();
1642 eliminatePartiallyRedundantLoad(
Load, ValuesPerBlock, PredLoads);
1648 AvailValInBlkVect &ValuesPerBlock,
1649 UnavailBlkVect &UnavailableBlocks) {
1653 const Loop *L = LI->getLoopFor(
Load->getParent());
1660 if (!Preheader || !Latch)
1663 Value *LoadPtr =
Load->getPointerOperand();
1671 if (ICF->isDominatedByICFIFromSameBlock(
Load))
1675 for (
auto *Blocker : UnavailableBlocks) {
1689 if (L != LI->getLoopFor(Blocker))
1697 if (DT->dominates(Blocker, Latch))
1701 if (Blocker->getTerminator()->mayWriteToMemory())
1704 LoopBlock = Blocker;
1717 AvailableLoads[LoopBlock] = LoadPtr;
1718 AvailableLoads[Preheader] = LoadPtr;
1721 eliminatePartiallyRedundantLoad(
Load, ValuesPerBlock, AvailableLoads);
1728 using namespace ore;
1732 <<
"load of type " <<
NV(
"Type",
Load->getType()) <<
" eliminated"
1742 if (
Load->getParent()->getParent()->hasFnAttribute(
1743 Attribute::SanitizeAddress) ||
1744 Load->getParent()->getParent()->hasFnAttribute(
1745 Attribute::SanitizeHWAddress))
1750 MD->getNonLocalPointerDependency(
Load, Deps);
1755 unsigned NumDeps = Deps.size();
1762 !Deps[0].getResult().isDef() && !Deps[0].getResult().isClobber()) {
1764 dbgs() <<
" has unknown dependencies\n";);
1768 bool Changed =
false;
1771 dyn_cast<GetElementPtrInst>(
Load->getOperand(0))) {
1772 for (
Use &U :
GEP->indices())
1774 Changed |= performScalarPRE(
I);
1778 AvailValInBlkVect ValuesPerBlock;
1779 UnavailBlkVect UnavailableBlocks;
1780 AnalyzeLoadAvailability(
Load, Deps, ValuesPerBlock, UnavailableBlocks);
1784 if (ValuesPerBlock.empty())
1792 if (UnavailableBlocks.empty()) {
1797 Load->replaceAllUsesWith(V);
1799 if (isa<PHINode>(V))
1805 if (
Load->getDebugLoc() &&
Load->getParent() ==
I->getParent())
1806 I->setDebugLoc(
Load->getDebugLoc());
1808 MD->invalidateCachedPointerInfo(V);
1809 markInstructionForDeletion(
Load);
1816 if (!isPREEnabled() || !isLoadPREEnabled())
1818 if (!isLoadInLoopPREEnabled() && LI && LI->getLoopFor(
Load->getParent()))
1821 if (performLoopLoadPRE(
Load, ValuesPerBlock, UnavailableBlocks) ||
1822 PerformLoadPRE(
Load, ValuesPerBlock, UnavailableBlocks))
1829 if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_EQ)
1835 if (Cmp->getPredicate() == CmpInst::Predicate::FCMP_OEQ ||
1836 (Cmp->getPredicate() == CmpInst::Predicate::FCMP_UEQ &&
1837 Cmp->getFastMathFlags().noNaNs())) {
1845 if (isa<ConstantFP>(
LHS) && !cast<ConstantFP>(
LHS)->
isZero())
1847 if (isa<ConstantFP>(
RHS) && !cast<ConstantFP>(
RHS)->
isZero())
1855 if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_NE)
1861 if ((Cmp->getPredicate() == CmpInst::Predicate::FCMP_ONE &&
1862 Cmp->getFastMathFlags().noNaNs()) ||
1863 Cmp->getPredicate() == CmpInst::Predicate::FCMP_UNE) {
1871 if (isa<ConstantFP>(
LHS) && !cast<ConstantFP>(
LHS)->
isZero())
1873 if (isa<ConstantFP>(
RHS) && !cast<ConstantFP>(
RHS)->
isZero())
1883 if (isa<Instruction>(U) &&
1889 bool GVNPass::processAssumeIntrinsic(
AssumeInst *IntrinsicI) {
1893 if (
Cond->isZero()) {
1904 MSSAU->getMemorySSA()->getBlockAccesses(IntrinsicI->
getParent());
1911 for (
auto &Acc : *
AL) {
1912 if (
auto *Current = dyn_cast<MemoryUseOrDef>(&Acc))
1913 if (!Current->getMemoryInst()->comesBefore(NewS)) {
1914 FirstNonDom = Current;
1923 FirstNonDom ? MSSAU->createMemoryAccessBefore(
1924 NewS, MSSAU->getMemorySSA()->getLiveOnEntryDef(),
1926 : MSSAU->createMemoryAccessInBB(
1927 NewS, MSSAU->getMemorySSA()->getLiveOnEntryDef(),
1930 MSSAU->insertDef(cast<MemoryDef>(NewDef),
false);
1934 markInstructionForDeletion(IntrinsicI);
1936 }
else if (isa<Constant>(V)) {
1944 bool Changed =
false;
1951 Changed |= propagateEquality(V, True, Edge,
false);
1957 ReplaceOperandsWithMap[V] = True;
1979 if (
auto *CmpI = dyn_cast<CmpInst>(V)) {
1981 Value *CmpLHS = CmpI->getOperand(0);
1982 Value *CmpRHS = CmpI->getOperand(1);
1988 if (isa<Constant>(CmpLHS) && !isa<Constant>(CmpRHS))
1990 if (!isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))
1992 if ((isa<Argument>(CmpLHS) && isa<Argument>(CmpRHS)) ||
1993 (isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))) {
1996 uint32_t LVN = VN.lookupOrAdd(CmpLHS);
1997 uint32_t RVN = VN.lookupOrAdd(CmpRHS);
2004 if (isa<Constant>(CmpLHS) && isa<Constant>(CmpRHS))
2008 << *CmpLHS <<
" with "
2009 << *CmpRHS <<
" in block "
2015 ReplaceOperandsWithMap[CmpLHS] = CmpRHS;
2028 I->replaceAllUsesWith(Repl);
2033 bool GVNPass::processLoad(
LoadInst *L) {
2042 markInstructionForDeletion(L);
2051 return processNonLocalLoad(L);
2055 if (!Dep.
isDef() && !Dep.
isClobber() && !isa<SelectInst>(Address)) {
2060 dbgs() <<
" has unknown dependence\n";);
2065 if (AnalyzeLoadAvailability(L, Dep, Address, AV)) {
2070 markInstructionForDeletion(L);
2072 MSSAU->removeMemoryAccess(L);
2087 std::pair<uint32_t, bool>
2088 GVNPass::ValueTable::assignExpNewValueNum(
Expression &Exp) {
2090 bool CreateNewValNum = !
e;
2091 if (CreateNewValNum) {
2093 if (ExprIdx.size() < nextValueNumber + 1)
2094 ExprIdx.resize(nextValueNumber * 2);
2095 e = nextValueNumber;
2096 ExprIdx[nextValueNumber++] = nextExprNumber++;
2098 return {
e, CreateNewValNum};
2105 LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
2106 while (Vals && Vals->BB ==
BB)
2115 auto FindRes = PhiTranslateTable.find({Num, Pred});
2116 if (FindRes != PhiTranslateTable.end())
2117 return FindRes->second;
2118 uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, Gvn);
2119 PhiTranslateTable.insert({{Num, Pred}, NewNum});
2130 LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
2132 Call = dyn_cast<CallInst>(Vals->Val);
2133 if (Call && Call->getParent() == PhiBlock)
2138 if (
AA->doesNotAccessMemory(Call))
2141 if (!MD || !
AA->onlyReadsMemory(Call))
2149 MD->getNonLocalCallDependency(Call);
2153 if (
D.getResult().isNonFuncLocal())
2164 if (
PHINode *PN = NumberingPhi[Num]) {
2165 for (
unsigned i = 0;
i != PN->getNumIncomingValues(); ++
i) {
2166 if (PN->getParent() == PhiBlock && PN->getIncomingBlock(
i) == Pred)
2176 if (!areAllValsInBB(Num, PhiBlock, Gvn))
2179 if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)
2183 for (
unsigned i = 0;
i <
Exp.varargs.size();
i++) {
2187 if ((
i > 1 &&
Exp.opcode == Instruction::InsertValue) ||
2188 (
i > 0 &&
Exp.opcode == Instruction::ExtractValue) ||
2189 (
i > 1 &&
Exp.opcode == Instruction::ShuffleVector))
2191 Exp.varargs[
i] = phiTranslate(Pred, PhiBlock,
Exp.varargs[
i], Gvn);
2194 if (
Exp.commutative) {
2195 assert(
Exp.varargs.size() >= 2 &&
"Unsupported commutative instruction!");
2196 if (
Exp.varargs[0] >
Exp.varargs[1]) {
2199 if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
2200 Exp.opcode = (Opcode << 8) |
2206 if (
uint32_t NewNum = expressionNumbering[Exp]) {
2208 return areCallValsEqual(Num, NewNum, Pred, PhiBlock, Gvn) ? NewNum : Num;
2219 PhiTranslateTable.erase({Num, Pred});
2228 LeaderTableEntry Vals = LeaderTable[num];
2229 if (!Vals.Val)
return nullptr;
2231 Value *Val =
nullptr;
2232 if (DT->dominates(Vals.BB,
BB)) {
2234 if (isa<Constant>(Val))
return Val;
2237 LeaderTableEntry* Next = Vals.Next;
2239 if (DT->dominates(Next->BB,
BB)) {
2240 if (isa<Constant>(Next->Val))
return Next->Val;
2241 if (!Val) Val = Next->Val;
2260 const BasicBlock *Pred =
E.getEnd()->getSinglePredecessor();
2261 assert((!Pred || Pred ==
E.getStart()) &&
2262 "No edge between these basic blocks!");
2263 return Pred !=
nullptr;
2266 void GVNPass::assignBlockRPONumber(
Function &
F) {
2267 BlockRPONumber.clear();
2271 BlockRPONumber[
BB] = NextBlockNumber++;
2272 InvalidBlockRPONumbers =
false;
2275 bool GVNPass::replaceOperandsForInBlockEquality(
Instruction *Instr)
const {
2276 bool Changed =
false;
2277 for (
unsigned OpNum = 0; OpNum < Instr->
getNumOperands(); ++OpNum) {
2279 auto it = ReplaceOperandsWithMap.find(Operand);
2280 if (
it != ReplaceOperandsWithMap.end()) {
2282 << *
it->second <<
" in instruction " << *Instr <<
'\n');
2297 bool DominatesByEdge) {
2299 Worklist.push_back(std::make_pair(
LHS,
RHS));
2300 bool Changed =
false;
2305 while (!Worklist.empty()) {
2306 std::pair<Value*, Value*> Item = Worklist.
pop_back_val();
2307 LHS = Item.first;
RHS = Item.second;
2314 if (isa<Constant>(
LHS) && isa<Constant>(
RHS))
2318 if (isa<Constant>(
LHS) || (isa<Argument>(
LHS) && !isa<Constant>(
RHS)))
2320 assert((isa<Argument>(
LHS) || isa<Instruction>(
LHS)) &&
"Unexpected value!");
2327 if ((isa<Argument>(
LHS) && isa<Argument>(
RHS)) ||
2328 (isa<Instruction>(
LHS) && isa<Instruction>(
RHS))) {
2347 if (RootDominatesEnd && !isa<Instruction>(
RHS))
2348 addToLeaderTable(LVN,
RHS, Root.
getEnd());
2354 unsigned NumReplacements =
2359 Changed |= NumReplacements > 0;
2360 NumGVNEqProp += NumReplacements;
2363 MD->invalidateCachedPointerInfo(
LHS);
2379 bool isKnownFalse = !isKnownTrue;
2386 Worklist.push_back(std::make_pair(A,
RHS));
2387 Worklist.push_back(std::make_pair(
B,
RHS));
2395 Value *Op0 =
Cmp->getOperand(0), *Op1 =
Cmp->getOperand(1);
2402 Worklist.push_back(std::make_pair(Op0, Op1));
2410 uint32_t NextNum = VN.getNextUnusedValueNumber();
2411 uint32_t Num = VN.lookupOrAddCmp(
Cmp->getOpcode(), NotPred, Op0, Op1);
2414 if (Num < NextNum) {
2416 if (NotCmp && isa<Instruction>(NotCmp)) {
2417 unsigned NumReplacements =
2422 Changed |= NumReplacements > 0;
2423 NumGVNEqProp += NumReplacements;
2426 MD->invalidateCachedPointerInfo(NotCmp);
2433 if (RootDominatesEnd)
2434 addToLeaderTable(Num, NotVal, Root.
getEnd());
2447 if (isa<DbgInfoIntrinsic>(
I))
2456 bool Changed =
false;
2457 if (!
I->use_empty()) {
2460 ICF->removeUsersOf(
I);
2461 I->replaceAllUsesWith(V);
2465 markInstructionForDeletion(
I);
2470 MD->invalidateCachedPointerInfo(V);
2476 if (
auto *Assume = dyn_cast<AssumeInst>(
I))
2477 return processAssumeIntrinsic(Assume);
2480 if (processLoad(
Load))
2483 unsigned Num = VN.lookupOrAdd(
Load);
2484 addToLeaderTable(Num,
Load,
Load->getParent());
2491 if (!BI->isConditional())
2494 if (isa<Constant>(BI->getCondition()))
2495 return processFoldableCondBr(BI);
2497 Value *BranchCond = BI->getCondition();
2501 if (TrueSucc == FalseSucc)
2505 bool Changed =
false;
2509 Changed |= propagateEquality(BranchCond,
TrueVal, TrueE,
true);
2513 Changed |= propagateEquality(BranchCond,
FalseVal, FalseE,
true);
2520 Value *SwitchCond =
SI->getCondition();
2522 bool Changed =
false;
2526 for (
unsigned i = 0,
n =
SI->getNumSuccessors();
i !=
n; ++
i)
2527 ++SwitchEdges[
SI->getSuccessor(
i)];
2533 if (SwitchEdges.
lookup(Dst) == 1) {
2535 Changed |= propagateEquality(SwitchCond,
i->getCaseValue(),
E,
true);
2543 if (
I->getType()->isVoidTy())
2546 uint32_t NextNum = VN.getNextUnusedValueNumber();
2547 unsigned Num = VN.lookupOrAdd(
I);
2551 if (isa<AllocaInst>(
I) ||
I->isTerminator() || isa<PHINode>(
I)) {
2552 addToLeaderTable(Num,
I,
I->getParent());
2559 if (Num >= NextNum) {
2560 addToLeaderTable(Num,
I,
I->getParent());
2566 Value *Repl = findLeader(
I->getParent(), Num);
2569 addToLeaderTable(Num,
I,
I->getParent());
2571 }
else if (Repl ==
I) {
2580 MD->invalidateCachedPointerInfo(Repl);
2581 markInstructionForDeletion(
I);
2594 VN.setAliasAnalysis(&RunAA);
2601 InvalidBlockRPONumbers =
true;
2603 MSSAU = MSSA ? &Updater :
nullptr;
2605 bool Changed =
false;
2606 bool ShouldContinue =
true;
2616 Changed |= removedBlock;
2619 unsigned Iteration = 0;
2620 while (ShouldContinue) {
2623 ShouldContinue = iterateOnFunction(
F);
2624 Changed |= ShouldContinue;
2628 if (isPREEnabled()) {
2631 assignValNumForDeadCode();
2632 bool PREChanged =
true;
2633 while (PREChanged) {
2634 PREChanged = performPRE(
F);
2635 Changed |= PREChanged;
2644 cleanupGlobalSets();
2658 assert(InstrsToErase.empty() &&
2659 "We expect InstrsToErase to be empty across iterations");
2660 if (DeadBlocks.count(
BB))
2664 ReplaceOperandsWithMap.clear();
2665 bool ChangedFunction =
false;
2675 if (!ReplaceOperandsWithMap.empty())
2676 ChangedFunction |= replaceOperandsForInBlockEquality(&*BI);
2677 ChangedFunction |= processInstruction(&*BI);
2679 if (InstrsToErase.empty()) {
2685 NumGVNInstr += InstrsToErase.size();
2688 bool AtStart = BI ==
BB->begin();
2692 for (
auto *
I : InstrsToErase) {
2693 assert(
I->getParent() ==
BB &&
"Removing instruction from wrong block?");
2697 if (MD) MD->removeInstruction(
I);
2699 MSSAU->removeMemoryAccess(
I);
2701 ICF->removeInstruction(
I);
2702 I->eraseFromParent();
2704 InstrsToErase.clear();
2712 return ChangedFunction;
2725 if (isa<Argument>(
Op) || isa<Constant>(
Op) || isa<GlobalValue>(
Op))
2731 if (!VN.exists(
Op)) {
2736 VN.phiTranslate(Pred, Curr, VN.lookup(
Op), *
this);
2737 if (
Value *V = findLeader(Pred, TValNo)) {
2755 ICF->insertInstructionTo(Instr, Pred);
2757 unsigned Num = VN.lookupOrAdd(Instr);
2761 addToLeaderTable(Num, Instr, Pred);
2765 bool GVNPass::performScalarPRE(
Instruction *CurInst) {
2766 if (isa<AllocaInst>(CurInst) || CurInst->
isTerminator() ||
2769 isa<DbgInfoIntrinsic>(CurInst))
2776 if (isa<CmpInst>(CurInst))
2786 if (isa<GetElementPtrInst>(CurInst))
2789 if (
auto *CallB = dyn_cast<CallBase>(CurInst)) {
2791 if (CallB->isInlineAsm())
2794 if (CallB->isConvergent())
2798 uint32_t ValNo = VN.lookup(CurInst);
2806 unsigned NumWith = 0;
2807 unsigned NumWithout = 0;
2812 if (InvalidBlockRPONumbers)
2813 assignBlockRPONumber(*CurrentBlock->
getParent());
2819 if (!DT->isReachableFromEntry(
P)) {
2826 assert(BlockRPONumber.count(
P) && BlockRPONumber.count(CurrentBlock) &&
2827 "Invalid BlockRPONumber map.");
2828 if (BlockRPONumber[
P] >= BlockRPONumber[CurrentBlock] &&
2830 if (auto *Inst = dyn_cast<Instruction>(U.get()))
2831 return Inst->getParent() == CurrentBlock;
2838 uint32_t TValNo = VN.phiTranslate(
P, CurrentBlock, ValNo, *
this);
2839 Value *predV = findLeader(
P, TValNo);
2841 predMap.push_back(std::make_pair(
static_cast<Value *
>(
nullptr),
P));
2844 }
else if (predV == CurInst) {
2849 predMap.push_back(std::make_pair(predV,
P));
2856 if (NumWithout > 1 || NumWith == 0)
2864 if (NumWithout != 0) {
2870 if (ICF->isDominatedByICFIFromSameBlock(CurInst))
2888 toSplit.push_back(std::make_pair(PREPred->
getTerminator(), SuccNum));
2892 PREInstr = CurInst->
clone();
2893 if (!performScalarPREInsertion(PREInstr, PREPred, CurrentBlock, ValNo)) {
2903 assert(PREInstr !=
nullptr || NumWithout == 0);
2910 CurInst->
getName() +
".pre-phi", &CurrentBlock->
front());
2911 for (
unsigned i = 0,
e = predMap.size();
i !=
e; ++
i) {
2912 if (
Value *V = predMap[
i].first) {
2924 VN.eraseTranslateCacheEntry(ValNo, *CurrentBlock);
2925 addToLeaderTable(ValNo, Phi, CurrentBlock);
2929 MD->invalidateCachedPointerInfo(Phi);
2931 removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
2935 MD->removeInstruction(CurInst);
2937 MSSAU->removeMemoryAccess(CurInst);
2941 ICF->removeInstruction(CurInst);
2951 bool Changed =
false;
2954 if (CurrentBlock == &
F.getEntryBlock())
2962 BE = CurrentBlock->
end();
2965 Changed |= performScalarPRE(CurInst);
2969 if (splitCriticalEdges())
2985 MD->invalidateCachedPredecessors();
2986 InvalidBlockRPONumbers =
true;
2993 bool GVNPass::splitCriticalEdges() {
2994 if (toSplit.empty())
2997 bool Changed =
false;
2999 std::pair<Instruction *, unsigned> Edge = toSplit.pop_back_val();
3003 }
while (!toSplit.empty());
3006 MD->invalidateCachedPredecessors();
3007 InvalidBlockRPONumbers =
true;
3013 bool GVNPass::iterateOnFunction(
Function &
F) {
3014 cleanupGlobalSets();
3017 bool Changed =
false;
3024 Changed |= processBlock(
BB);
3029 void GVNPass::cleanupGlobalSets() {
3031 LeaderTable.clear();
3032 BlockRPONumber.clear();
3033 TableAllocator.Reset();
3035 InvalidBlockRPONumbers =
true;
3040 void GVNPass::verifyRemoved(
const Instruction *Inst)
const {
3041 VN.verifyRemoved(Inst);
3045 for (
const auto &
I : LeaderTable) {
3046 const LeaderTableEntry *Node = &
I.second;
3047 assert(Node->Val != Inst &&
"Inst still in value numbering scope!");
3049 while (Node->Next) {
3051 assert(Node->Val != Inst &&
"Inst still in value numbering scope!");
3064 NewDead.push_back(
BB);
3065 while (!NewDead.empty()) {
3067 if (DeadBlocks.count(
D))
3072 DT->getDescendants(
D, Dom);
3073 DeadBlocks.
insert(Dom.begin(), Dom.end());
3078 if (DeadBlocks.count(
S))
3081 bool AllPredDead =
true;
3083 if (!DeadBlocks.count(
P)) {
3084 AllPredDead =
false;
3096 NewDead.push_back(
S);
3105 if (DeadBlocks.count(
B))
3112 if (!DeadBlocks.count(
P))
3118 DeadBlocks.insert(
P =
S);
3124 if (!DeadBlocks.count(
P))
3129 MD->invalidateCachedPointerInfo(&Phi);
3148 bool GVNPass::processFoldableCondBr(
BranchInst *BI) {
3162 if (DeadBlocks.count(DeadRoot))
3166 DeadRoot = splitCriticalEdges(BI->
getParent(), DeadRoot);
3168 addDeadBlock(DeadRoot);
3176 void GVNPass::assignValNumForDeadCode() {
3179 unsigned ValNum = VN.lookupOrAdd(&Inst);
3180 addToLeaderTable(ValNum, &Inst,
BB);
3195 if (skipFunction(
F))
3198 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
3200 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
3201 return Impl.runImpl(
3202 F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F),
3203 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
3204 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F),
3205 getAnalysis<AAResultsWrapperPass>().getAAResults(),
3206 Impl.isMemDepEnabled()
3207 ? &getAnalysis<MemoryDependenceWrapperPass>().getMemDep()
3209 LIWP ? &LIWP->getLoopInfo() :
nullptr,
3210 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(),
3211 MSSAWP ? &MSSAWP->getMSSA() :
nullptr);
3219 if (Impl.isMemDepEnabled())
A set of parameters to control various transforms performed by GVN pass.
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
A set of analyses that are preserved following a run of a transformation pass.
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
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...
bool isTerminator() const
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
A manager for alias analyses.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This class allows to keep track on instructions with implicit control flow.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
friend hash_code hash_value(const Expression &Value)
This is an optimization pass for GlobalISel generic memory operations.
This is an entry in the NonLocalDepInfo cache.
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void clear()
Remove all entries from the ValueTable.
A parsed version of the target data layout string in and methods for querying it.
Value * getStoreValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &DL)
If analyzeLoadFromClobberingStore returned an offset, this function can be used to actually perform t...
bool hasOneUse() const
Return true if there is exactly one use of this value.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
InstListType::iterator iterator
Instruction iterators...
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
PHITransAddr - An address value which tracks and handles phi translation.
const Function * getParent() const
Return the enclosing method, or null if none.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
static cl::opt< bool > GVNEnableLoadPRE("enable-load-pre", cl::init(true))
Interval::succ_iterator succ_end(Interval *I)
uint32_t lookupOrAdd(Value *V)
lookup_or_add - Returns the value number for the specified value, assigning it a new number if it did...
bool exists(Value *V) const
Returns true if a value number exists for the specified value.
static Function * getFunction(Constant *C)
Represents a single loop in the control flow graph.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
uint32_t lookup(Value *V, bool Verify=true) const
Returns the value number of the specified value.
static bool impliesEquivalanceIfTrue(CmpInst *Cmp)
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Value * MaterializeAdjustedValue(LoadInst *Load, GVNPass &gvn) const
Emit code at the end of this block to adjust the value defined here to the specified type.
bool isAssumeWithEmptyBundle(AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
This represents the llvm.assume intrinsic.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
bool isCoercedLoadValue() const
The instances of the Type class are immutable: once they are created, they are never changed.
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.
static Value * ConstructSSAForLoadSet(LoadInst *Load, SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, GVNPass &gvn)
Given a set of loads specified by ValuesPerBlock, construct SSA form, allowing us to eliminate Load.
The legacy pass manager's analysis pass to compute loop information.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset=0)
This is the common base class for memset/memcpy/memmove.
A memory dependence query can return one of three different answers.
This class implements a map that also provides access to all stored values in a deterministic order.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
static void reportMayClobberedLoad(LoadInst *Load, MemDepResult DepInfo, DominatorTree *DT, OptimizationRemarkEmitter *ORE)
Try to locate the three instruction involved in a missed load-elimination case that is due to an inte...
DiagnosticInfoOptimizationBase::Argument NV
auto successors(MachineBasicBlock *BB)
FunctionPass * createGVNPass(bool NoMemDepAnalysis=false)
Create a legacy GVN pass.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
LLVM_NODISCARD T pop_back_val()
Value * getPointerOperand()
static bool isEqual(const GVNPass::Expression &LHS, const GVNPass::Expression &RHS)
hash_code hash_value(const APFloat &Arg)
See friend declarations above.
static IntegerType * getInt8Ty(LLVMContext &C)
void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock)
Erase stale entry from phiTranslate cache so phiTranslate can be computed again.
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
AvailableValue AV
AV - The actual available value.
LLVM Basic Block Representation.
ppc ctr loops PowerPC CTR Loops Verify
Represents an AvailableValue which can be rematerialized at the end of the associated BasicBlock.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static bool hasUsersIn(Value *V, BasicBlock *BB)
static AvailableValue getLoad(LoadInst *Load, unsigned Offset=0)
This is the shared class of boolean and integer constants.
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
An information struct used to provide DenseMap with the various necessary components for a given valu...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
const Value * getCondition() const
ValueTable & operator=(const ValueTable &Arg)
Legacy analysis pass which computes MemorySSA.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool match(Val *V, const Pattern &P)
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV)
@ Available
We know the block is fully available. This is a fixpoint.
(vector float) vec_cmpeq(*A, *B) C
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
iterator begin()
Instruction iterator methods.
Represent the analysis usage information of a pass.
static bool runImpl(const TargetLibraryInfo &TLI, Function &F)
Option class for critical edge splitting.
static bool IsValueFullyAvailableInBlock(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.
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GVNPass::Expression getTombstoneKey()
Represents a particular available value that we know how to materialize.
bool isLoadInLoopPREEnabled() const
Legacy analysis pass which computes a DominatorTree.
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
STATISTIC(NumFunctions, "Total number of functions")
auto predecessors(MachineBasicBlock *BB)
This class implements an extremely fast bulk output stream that can only output to a stream.
void setName(const Twine &Name)
Change the name of the value.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
static AvailableValue get(Value *V, unsigned Offset=0)
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static cl::opt< bool > GVNEnableMemDep("enable-gvn-memdep", cl::init(true))
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
bool isPREEnabled() const
static void reportLoadElim(LoadInst *Load, Value *AvailableValue, OptimizationRemarkEmitter *ORE)
static AvailableValue getSelect(SelectInst *Sel)
GVNLegacyPass(bool NoMemDepAnalysis=!GVNEnableMemDep)
static LoadInst * findDominatingLoad(Value *Ptr, Type *LoadTy, SelectInst *Sel, DominatorTree &DT)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
void add(Value *V, uint32_t num)
add - Insert a value into the table with a specified value number.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
static Optional< AvailableValue > tryToConvertLoadOfPtrSelect(BasicBlock *DepBB, BasicBlock::iterator End, Value *Address, Type *LoadTy, DominatorTree &DT, AAResults *AA)
Check if a load from pointer-select Address in DepBB can be converted to a value select.
Value * getCondition() const
Value * MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt, GVNPass &gvn) const
Emit code at the specified insertion point to adjust the value defined here to the specified type.
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...
This class is the base class for the comparison instructions.
bool isIntegerTy() const
True if this is an instance of IntegerType.
An efficient, type-erasing, non-owning reference to a callable.
LoadInst * getCoercedLoadValue() const
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
An instruction for storing to memory.
DominatorTree & getDominatorTree() const
bool isLoadPRESplitBackedgeEnabled() const
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,...
This is an important base class in LLVM.
bool isMemIntrinValue() const
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Represents calls to the gc.relocate intrinsic.
static cl::opt< uint32_t > MaxBBSpeculations("gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::desc("Max number of blocks we're willing to speculate on (and recurse " "into) when deducing if a value is fully available or not in GVN " "(default = 600)"))
MemoryDependenceResults & getMemDep() const
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
A function analysis which provides an AssumptionCache.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
void preserve()
Mark an analysis as preserved.
void erase(Value *v)
Remove a value from the value numbering.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
This is an important class for using LLVM in a threaded context.
Encapsulates MemorySSA, including all data associated with memory accesses.
bool isClobber() const
Tests if this MemDepResult represents a query that is an instruction clobber dependency.
SmallVector< uint32_t, 4 > varargs
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
initializer< Ty > init(const Ty &Val)
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...
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl)
static cl::opt< bool > GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden)
static AvailableValueInBlock getUndef(BasicBlock *BB)
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
bool isMemDepEnabled() const
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
@ Unavailable
We know the block is not fully available. This is a fixpoint.
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
StandardInstrumentations SI(Debug, VerifyEach)
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...
This class represents the LLVM 'select' instruction.
bool isVoidTy() const
Return true if this is 'void'.
void salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
An analysis that produces MemorySSA for a function.
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.
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
bool isUnconditional() const
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Class for arbitrary precision integers.
void setOperand(unsigned i, Value *Val)
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...
Class representing an expression and its matching format.
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
bool isLoadPREEnabled() const
An immutable pass that tracks lazily created AssumptionCache objects.
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.
static cl::opt< bool > GVNEnableLoadInLoopPRE("enable-load-in-loop-pre", cl::init(true))
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
const BasicBlock * getEnd() const
Expression(uint32_t o=~2U)
SmallVector< MachineOperand, 4 > Cond
StringRef - Represent a constant reference to a string, i.e.
A cache of @llvm.assume calls within a function.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Type * getType() const
All values are typed, get the type of this value.
static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E, DominatorTree *DT)
There is an edge from 'Src' to 'Dst'.
void verifyRemoved(const Value *) const
verifyRemoved - Verify that the value is removed from all internal data structures.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
static const Function * getParent(const Value *V)
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
LLVMContext & getContext() const
All values hold a context through their type.
self_iterator getIterator()
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
This class holds the mapping between values and value numbers.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
MemIntrinsic * getMemIntrinValue() const
bool pred_empty(const BasicBlock *BB)
SelectInst * getSelectValue() const
bool isPtrOrPtrVectorTy() const
Return true if this is a pointer type or a vector of pointer types.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Represents an op.with.overflow intrinsic.
bool mayReadFromMemory() const
Return true if this instruction may read memory.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
StringRef getName() const
Return a constant reference to the value's name.
An instruction for reading from memory.
bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
Value * getLoadValueForLoad(LoadInst *SrcVal, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &DL)
If analyzeLoadFromClobberingLoad returned an offset, this function can be used to actually perform th...
bool isUndefValue() const
static ConstantInt * getFalse(LLVMContext &Context)
const Instruction & front() const
static bool liesBetween(const Instruction *From, Instruction *Between, const Instruction *To, DominatorTree *DT)
Assuming To can be reached from both From and Between, does Between lie on every path from From to To...
bool isSimpleValue() const
LLVMContext & getContext() const
Get the context in which this basic block lives.
iterator_range< df_iterator< T > > depth_first(const T &G)
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
Provides a lazy, caching interface for making common memory aliasing information queries,...
static ConstantInt * getTrue(LLVMContext &Context)
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.
static GVNPass::Expression getEmptyKey()
Should compile to something r4 addze r3 instead we get
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
DiagnosticInfoOptimizationBase::setExtraArgs setExtraArgs
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...
unsigned arg_size() const
Interval::pred_iterator pred_end(Interval *I)
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
static bool impliesEquivalanceIfFalse(CmpInst *Cmp)
constexpr unsigned BitWidth
BlockT * getHeader() const
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
Provides information about what library functions are available for the current target.
BasicBlock * BB
BB - The basic block in question.
Class that has the common methods + fields of memory uses/defs.
Value * getSimpleValue() const
bool canCoerceMustAliasedValueToLoad(Value *StoredVal, Type *LoadTy, const DataLayout &DL)
Return true if CoerceAvailableValueToLoadType would succeed if it was called.
std::unique_ptr< ValueIDNum[]> ValueTable
Type for a table of values in a block.
static AvailableValueInBlock getSelect(BasicBlock *BB, SelectInst *Sel)
static unsigned getHashValue(const GVNPass::Expression &e)
A wrapper class for inspecting calls to intrinsic functions.
bool isSelectValue() const
static bool isLifetimeStart(const Instruction *Inst)
static cl::opt< uint32_t > MaxNumDeps("gvn-max-num-deps", cl::Hidden, cl::init(100), cl::desc("Max number of dependences to attempt Load PRE (default = 100)"))
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Analysis pass which computes a DominatorTree.
http eax xorl edx cl sete al setne dl sall eax sall edx But that requires good bit subreg support this might be better It s an extra but it s one instruction and doesn t stress bit subreg eax eax movl edx edx sall eax sall cl edx bit we should expand to a conditional branch like GCC produces Some isel and Sequencing of Instructions Scheduling for reduced register pressure E g Minimum Register Instruction Sequence load p Because the compare isn t commutative
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...
bool isOpaquePointerTy() const
True if this is an instance of an opaque PointerType.
void initializeGVNLegacyPassPass(PassRegistry &)
unsigned getNumOperands() const
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset, uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs, llvm::Error &Err)
A Lookup helper functions.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
static cl::opt< bool > GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre", cl::init(false))
Value * getArgOperand(unsigned i) const
std::vector< NonLocalDepEntry > NonLocalDepInfo
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
const BasicBlock * getParent() const
void deleteValue()
Delete a pointer to a generic Value.
gvn Early GVN Hoisting of Expressions
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...
Legacy wrapper pass to provide the GlobalsAAResult object.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, uint32_t Num, GVNPass &Gvn)
Wrap phiTranslateImpl to provide caching functionality.
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...
@ SpeculativelyAvailable
We do not know whether the block is fully available or not, but we are currently speculating that it ...
static const uint32_t IV[8]
LLVM_NODISCARD bool empty() const
unsigned Offset
Offset - The byte offset in Val that is interesting for the load query.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
A SetVector that performs no allocations if smaller than a certain size.
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
This class represents a function call, abstracting a target machine's calling convention.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
void patchReplacementInstruction(Instruction *I, Value *Repl)
Patch the replacement so that it is not more restrictive than the value being replaced.
AnalysisUsage & addRequired()
bool VerifyMemorySSA
Enables verification of MemorySSA.
The core GVN pass object.
BlockVerifier::State From
void takeName(Value *V)
Transfer the name from V to this value.
Value * getOperand(unsigned i) const
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Conditional or Unconditional Branch instruction.
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int int d
Helper class for SSA formation on a set of values defined in multiple blocks.
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Value * Val
Val - The value that is live out of the block.
bool isEHPad() const
Return true if this basic block is an exception handling block.
LLVM Value Representation.
ValType Kind
Kind of the live-out value.
bool operator==(const Expression &other) const
Analysis pass providing the TargetLibraryInfo.
bool isNonLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the block,...
iterator_range< user_iterator > users()
static AvailableValueInBlock get(BasicBlock *BB, Value *V, unsigned Offset=0)
static AvailableValue getUndef()
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
BasicBlock * getSuccessor(unsigned i) const
Representation for a specific memory location.
Analysis pass that exposes the LoopInfo for a function.
A Use represents the edge between a Value definition and its users.
reference emplace_back(ArgTypes &&... Args)
An analysis that produces MemoryDependenceResults for a function.
An opaque object representing a hash code.
iterator insert(iterator I, T &&Elt)
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.