127#define DEBUG_TYPE "newgvn"
129STATISTIC(NumGVNInstrDeleted,
"Number of instructions deleted");
130STATISTIC(NumGVNBlocksDeleted,
"Number of blocks deleted");
131STATISTIC(NumGVNOpsSimplified,
"Number of Expressions simplified");
132STATISTIC(NumGVNPhisAllSame,
"Number of PHIs whos arguments are all the same");
134 "Maximum Number of iterations it took to converge GVN");
135STATISTIC(NumGVNLeaderChanges,
"Number of leader changes");
136STATISTIC(NumGVNSortedLeaderChanges,
"Number of sorted leader changes");
138 "Number of avoided sorted leader changes");
139STATISTIC(NumGVNDeadStores,
"Number of redundant/dead stores eliminated");
140STATISTIC(NumGVNPHIOfOpsCreated,
"Number of PHI of ops created");
142 "Number of things eliminated using PHI of ops");
144 "Controls which instructions are value numbered");
146 "Controls which instructions we create phi of ops for");
163namespace GVNExpression {
187 TarjanSCC() : Components(1) {}
190 if (Root.lookup(Start) == 0)
195 unsigned ComponentID = ValueToComponent.lookup(V);
198 "Asking for a component for a value we never processed");
199 return Components[ComponentID];
206 unsigned int OurDFS = DFSNum;
207 for (
const auto &
Op :
I->operands()) {
208 if (
auto *InstOp = dyn_cast<Instruction>(
Op)) {
209 if (Root.lookup(
Op) == 0)
211 if (!InComponent.count(
Op))
212 Root[
I] = std::min(Root.lookup(
I), Root.lookup(
Op));
219 if (Root.lookup(
I) == OurDFS) {
220 unsigned ComponentID = Components.size();
221 Components.resize(Components.size() + 1);
225 InComponent.insert(
I);
226 ValueToComponent[
I] = ComponentID;
228 while (!
Stack.empty() && Root.lookup(
Stack.back()) >= OurDFS) {
232 InComponent.insert(Member);
233 ValueToComponent[
Member] = ComponentID;
242 unsigned int DFSNum = 1;
292class CongruenceClass {
294 using MemberType =
Value;
299 explicit CongruenceClass(
unsigned ID) :
ID(
ID) {}
301 :
ID(
ID), RepLeader(Leader), DefiningExpr(E) {}
303 unsigned getID()
const {
return ID; }
307 bool isDead()
const {
310 return empty() && memory_empty();
314 Value *getLeader()
const {
return RepLeader; }
315 void setLeader(
Value *Leader) { RepLeader = Leader; }
316 const std::pair<Value *, unsigned int> &getNextLeader()
const {
319 void resetNextLeader() { NextLeader = {
nullptr, ~0}; }
320 void addPossibleNextLeader(std::pair<Value *, unsigned int> LeaderPair) {
321 if (LeaderPair.second < NextLeader.second)
322 NextLeader = LeaderPair;
326 void setStoredValue(
Value *Leader) { RepStoredValue = Leader; }
327 const MemoryAccess *getMemoryLeader()
const {
return RepMemoryAccess; }
328 void setMemoryLeader(
const MemoryAccess *Leader) { RepMemoryAccess = Leader; }
331 const Expression *getDefiningExpr()
const {
return DefiningExpr; }
334 bool empty()
const {
return Members.empty(); }
335 unsigned size()
const {
return Members.size(); }
338 void insert(MemberType *M) { Members.insert(M); }
339 void erase(MemberType *M) { Members.erase(M); }
343 bool memory_empty()
const {
return MemoryMembers.empty(); }
344 unsigned memory_size()
const {
return MemoryMembers.size(); }
346 return MemoryMembers.begin();
349 return MemoryMembers.end();
352 return make_range(memory_begin(), memory_end());
355 void memory_insert(
const MemoryMemberType *M) { MemoryMembers.insert(M); }
356 void memory_erase(
const MemoryMemberType *M) { MemoryMembers.erase(M); }
359 unsigned getStoreCount()
const {
return StoreCount; }
360 void incStoreCount() { ++StoreCount; }
361 void decStoreCount() {
362 assert(StoreCount != 0 &&
"Store count went negative");
367 bool definesNoMemory()
const {
return StoreCount == 0 && memory_empty(); }
371 bool isEquivalentTo(
const CongruenceClass *
Other)
const {
377 if (std::tie(StoreCount, RepLeader, RepStoredValue, RepMemoryAccess) !=
379 Other->RepMemoryAccess))
381 if (DefiningExpr !=
Other->DefiningExpr)
382 if (!DefiningExpr || !
Other->DefiningExpr ||
383 *DefiningExpr != *
Other->DefiningExpr)
386 if (Members.size() !=
Other->Members.size())
396 Value *RepLeader =
nullptr;
400 std::pair<Value *, unsigned int> NextLeader = {
nullptr, ~0
U};
403 Value *RepStoredValue =
nullptr;
418 MemoryMemberSet MemoryMembers;
437 return E.exactlyEquals(
Other);
443 auto Val =
static_cast<uintptr_t
>(-1);
444 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
445 return reinterpret_cast<const Expression *
>(Val);
449 auto Val =
static_cast<uintptr_t
>(~1U);
450 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
451 return reinterpret_cast<const Expression *
>(Val);
455 return E->getComputedHash();
459 return E.getComputedHash();
463 if (
RHS == getTombstoneKey() ||
RHS == getEmptyKey())
471 if (
LHS == getTombstoneKey() ||
RHS == getTombstoneKey() ||
472 LHS == getEmptyKey() ||
RHS == getEmptyKey())
478 if (
LHS->getComputedHash() !=
RHS->getComputedHash())
497 std::unique_ptr<PredicateInfo> PredInfo;
503 mutable TarjanSCC SCCFinder;
507 unsigned int NumFuncArgs = 0;
518 CongruenceClass *TOPClass =
nullptr;
519 std::vector<CongruenceClass *> CongruenceClasses;
520 unsigned NextCongruenceNum = 0;
555 ExpressionToPhiOfOps;
604 enum MemoryPhiState { MPS_Invalid, MPS_TOP, MPS_Equivalent, MPS_Unique };
607 enum InstCycleState { ICS_Unknown, ICS_CycleFree, ICS_Cycle };
612 ExpressionClassMap ExpressionToClass;
664 :
F(
F), DT(DT), TLI(TLI), AA(AA), MSSA(MSSA), AC(AC),
DL(
DL),
666 SQ(
DL, TLI, DT, AC, nullptr,
false,
680 : Expr(Expr), ExtraDep(ExtraDep), PredDep(PredDep) {}
681 ExprResult(
const ExprResult &) =
delete;
682 ExprResult(ExprResult &&
Other)
684 Other.Expr =
nullptr;
685 Other.ExtraDep =
nullptr;
686 Other.PredDep =
nullptr;
688 ExprResult &operator=(
const ExprResult &
Other) =
delete;
689 ExprResult &operator=(ExprResult &&
Other) =
delete;
691 ~ExprResult() {
assert(!ExtraDep &&
"unhandled ExtraDep"); }
693 operator bool()
const {
return Expr; }
695 static ExprResult
none() {
return {
nullptr,
nullptr,
nullptr}; }
696 static ExprResult some(
const Expression *Expr,
Value *ExtraDep =
nullptr) {
697 return {Expr, ExtraDep,
nullptr};
699 static ExprResult some(
const Expression *Expr,
701 return {Expr,
nullptr, PredDep};
705 return {Expr, ExtraDep, PredDep};
716 using ValPair = std::pair<Value *, BasicBlock *>;
720 bool &OriginalOpsConstant)
const;
733 createAggregateValueExpression(
Instruction *)
const;
737 CongruenceClass *createCongruenceClass(
Value *Leader,
const Expression *
E) {
738 auto *result =
new CongruenceClass(NextCongruenceNum++, Leader,
E);
739 CongruenceClasses.emplace_back(result);
744 auto *
CC = createCongruenceClass(
nullptr,
nullptr);
745 CC->setMemoryLeader(MA);
749 CongruenceClass *ensureLeaderOfMemoryClass(
MemoryAccess *MA) {
750 auto *
CC = getMemoryClass(MA);
751 if (
CC->getMemoryLeader() != MA)
752 CC = createMemoryClass(MA);
756 CongruenceClass *createSingletonCongruenceClass(
Value *Member) {
757 CongruenceClass *CClass = createCongruenceClass(Member,
nullptr);
758 CClass->insert(Member);
759 ValueToClass[
Member] = CClass;
763 void initializeCongruenceClasses(
Function &
F);
781 ExprResult performSymbolicEvaluation(
Instruction *,
788 ExprResult performSymbolicCallEvaluation(
Instruction *)
const;
794 ExprResult performSymbolicCmpEvaluation(
Instruction *)
const;
795 ExprResult performSymbolicPredicateInfoEvaluation(
IntrinsicInst *)
const;
800 CongruenceClass *getClassForExpression(
const Expression *
E)
const;
803 CongruenceClass *, CongruenceClass *);
805 CongruenceClass *, CongruenceClass *);
806 Value *getNextValueLeader(CongruenceClass *)
const;
807 const MemoryAccess *getNextMemoryLeader(CongruenceClass *)
const;
809 CongruenceClass *getMemoryClass(
const MemoryAccess *MA)
const;
814 unsigned int getRank(
const Value *)
const;
815 bool shouldSwapOperands(
const Value *,
const Value *)
const;
816 bool shouldSwapOperandsForIntrinsic(
const Value *,
const Value *,
822 Value *findConditionEquivalence(
Value *)
const;
826 void convertClassToDFSOrdered(
const CongruenceClass &,
830 void convertClassToLoadsAndStores(
const CongruenceClass &,
833 bool eliminateInstructions(
Function &);
841 template <
typename Map,
typename KeyType>
842 void touchAndErase(Map &,
const KeyType &);
843 void markUsersTouched(
Value *);
847 void markValueLeaderChangeTouched(CongruenceClass *
CC);
848 void markMemoryLeaderChangeTouched(CongruenceClass *
CC);
855 void iterateTouchedInstructions();
858 void cleanupTables();
859 std::pair<unsigned, unsigned> assignDFSNumbers(
BasicBlock *,
unsigned);
860 void updateProcessedCount(
const Value *V);
861 void verifyMemoryCongruency()
const;
862 void verifyIterationSettled(
Function &
F);
863 void verifyStoreExpressions()
const;
870 template <
class T,
class Range>
T *getMinDFSOfRange(
const Range &)
const;
872 unsigned InstrToDFSNum(
const Value *V)
const {
873 assert(isa<Instruction>(V) &&
"This should not be used for MemoryAccesses");
874 return InstrDFS.
lookup(V);
878 return MemoryToDFSNum(MA);
881 Value *InstrFromDFSNum(
unsigned DFSNum) {
return DFSToInstr[DFSNum]; }
886 unsigned MemoryToDFSNum(
const Value *MA)
const {
887 assert(isa<MemoryAccess>(MA) &&
888 "This should not be used with instructions");
889 return isa<MemoryUseOrDef>(MA)
890 ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst())
906 if (!isa<LoadExpression>(
RHS) && !isa<StoreExpression>(
RHS))
908 return LHS.MemoryExpression::equals(
RHS);
919 if (
const auto *S = dyn_cast<StoreExpression>(&
Other))
951 if (
auto *
I = dyn_cast<Instruction>(V)) {
952 auto *Parent =
I->getParent();
955 Parent = TempToBlock.
lookup(V);
956 assert(Parent &&
"Every fake instruction should have a block");
960 auto *MP = dyn_cast<MemoryPhi>(V);
961 assert(MP &&
"Should have been an instruction or a MemoryPhi");
962 return MP->getBlock();
968void NewGVN::deleteExpression(
const Expression *
E)
const {
969 assert(isa<BasicExpression>(
E));
970 auto *BE = cast<BasicExpression>(
E);
977 if (
auto *
II = dyn_cast<IntrinsicInst>(V))
978 if (
II->getIntrinsicID() == Intrinsic::ssa_copy)
979 return II->getOperand(0);
990 return CO && isa<PHINode>(CO);
997 llvm::sort(Ops, [&](
const ValPair &P1,
const ValPair &P2) {
998 return BlockInstRange.
lookup(P1.second).first <
999 BlockInstRange.
lookup(P2.second).first;
1007 return isa<Constant>(V) || isa<Argument>(V);
1019 bool &OriginalOpsConstant)
const {
1020 unsigned NumOps = PHIOperands.
size();
1021 auto *
E =
new (ExpressionAllocator)
PHIExpression(NumOps, PHIBlock);
1023 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1024 E->setType(PHIOperands.
begin()->first->getType());
1025 E->setOpcode(Instruction::PHI);
1029 auto *BB =
P.second;
1030 if (
auto *PHIOp = dyn_cast<PHINode>(
I))
1033 if (!ReachableEdges.
count({BB, PHIBlock}))
1036 if (ValueToClass.
lookup(
P.first) == TOPClass)
1038 OriginalOpsConstant = OriginalOpsConstant && isa<Constant>(
P.first);
1039 HasBackedge = HasBackedge || isBackedge(BB, PHIBlock);
1040 return lookupOperandLeader(
P.first) !=
I;
1042 std::transform(Filtered.begin(), Filtered.end(),
op_inserter(
E),
1043 [&](
const ValPair &
P) ->
Value * {
1044 return lookupOperandLeader(
P.first);
1052 bool AllConstant =
true;
1053 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I))
1054 E->setType(
GEP->getSourceElementType());
1056 E->setType(
I->getType());
1057 E->setOpcode(
I->getOpcode());
1058 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1063 auto Operand = lookupOperandLeader(O);
1064 AllConstant = AllConstant && isa<Constant>(Operand);
1071const Expression *NewGVN::createBinaryExpression(
unsigned Opcode,
Type *
T,
1080 E->setOpcode(Opcode);
1081 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1087 if (shouldSwapOperands(Arg1, Arg2))
1090 E->op_push_back(lookupOperandLeader(Arg1));
1091 E->op_push_back(lookupOperandLeader(Arg2));
1094 if (
auto Simplified = checkExprResults(
E,
I, V)) {
1095 addAdditionalUsers(Simplified,
I);
1107 return ExprResult::none();
1109 if (
auto *
C = dyn_cast<Constant>(V)) {
1112 <<
" constant " << *
C <<
"\n");
1113 NumGVNOpsSimplified++;
1114 assert(isa<BasicExpression>(
E) &&
1115 "We should always have had a basic expression here");
1116 deleteExpression(
E);
1117 return ExprResult::some(createConstantExpression(
C));
1118 }
else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
1121 <<
" variable " << *V <<
"\n");
1122 deleteExpression(
E);
1123 return ExprResult::some(createVariableExpression(V));
1126 CongruenceClass *
CC = ValueToClass.
lookup(V);
1128 if (
CC->getLeader() &&
CC->getLeader() !=
I) {
1129 return ExprResult::some(createVariableOrConstant(
CC->getLeader()), V);
1131 if (
CC->getDefiningExpr()) {
1134 <<
" expression " << *
CC->getDefiningExpr() <<
"\n");
1135 NumGVNOpsSimplified++;
1136 deleteExpression(
E);
1137 return ExprResult::some(
CC->getDefiningExpr(), V);
1141 return ExprResult::none();
1147NewGVN::ExprResult NewGVN::createExpression(
Instruction *
I)
const {
1153 bool AllConstant = setBasicExpressionInfo(
I,
E);
1155 if (
I->isCommutative()) {
1160 assert(
I->getNumOperands() == 2 &&
"Unsupported commutative instruction!");
1161 if (shouldSwapOperands(
E->getOperand(0),
E->getOperand(1)))
1162 E->swapOperands(0, 1);
1165 if (
auto *CI = dyn_cast<CmpInst>(
I)) {
1169 if (shouldSwapOperands(
E->getOperand(0),
E->getOperand(1))) {
1170 E->swapOperands(0, 1);
1173 E->setOpcode((CI->getOpcode() << 8) | Predicate);
1175 assert(
I->getOperand(0)->getType() ==
I->getOperand(1)->getType() &&
1176 "Wrong types on cmp instruction");
1177 assert((
E->getOperand(0)->getType() ==
I->getOperand(0)->getType() &&
1178 E->getOperand(1)->getType() ==
I->getOperand(1)->getType()));
1181 if (
auto Simplified = checkExprResults(
E,
I, V))
1183 }
else if (isa<SelectInst>(
I)) {
1184 if (isa<Constant>(
E->getOperand(0)) ||
1185 E->getOperand(1) ==
E->getOperand(2)) {
1186 assert(
E->getOperand(1)->getType() ==
I->getOperand(1)->getType() &&
1187 E->getOperand(2)->getType() ==
I->getOperand(2)->getType());
1189 E->getOperand(2), Q);
1190 if (
auto Simplified = checkExprResults(
E,
I, V))
1193 }
else if (
I->isBinaryOp()) {
1196 if (
auto Simplified = checkExprResults(
E,
I, V))
1198 }
else if (
auto *CI = dyn_cast<CastInst>(
I)) {
1201 if (
auto Simplified = checkExprResults(
E,
I, V))
1203 }
else if (
auto *GEPI = dyn_cast<GetElementPtrInst>(
I)) {
1205 ArrayRef(std::next(
E->op_begin()),
E->op_end()),
1206 GEPI->getNoWrapFlags(), Q);
1207 if (
auto Simplified = checkExprResults(
E,
I, V))
1209 }
else if (AllConstant) {
1218 for (
Value *Arg :
E->operands())
1219 C.emplace_back(cast<Constant>(Arg));
1222 if (
auto Simplified = checkExprResults(
E,
I, V))
1225 return ExprResult::some(
E);
1229NewGVN::createAggregateValueExpression(
Instruction *
I)
const {
1230 if (
auto *
II = dyn_cast<InsertValueInst>(
I)) {
1231 auto *
E =
new (ExpressionAllocator)
1233 setBasicExpressionInfo(
I,
E);
1234 E->allocateIntOperands(ExpressionAllocator);
1237 }
else if (
auto *EI = dyn_cast<ExtractValueInst>(
I)) {
1238 auto *
E =
new (ExpressionAllocator)
1240 setBasicExpressionInfo(EI,
E);
1241 E->allocateIntOperands(ExpressionAllocator);
1251 return SingletonDeadExpression;
1256 E->setOpcode(
V->getValueID());
1261 if (
auto *
C = dyn_cast<Constant>(V))
1262 return createConstantExpression(
C);
1263 return createVariableExpression(V);
1268 E->setOpcode(
C->getValueID());
1274 E->setOpcode(
I->getOpcode());
1283 setBasicExpressionInfo(CI,
E);
1289 if (shouldSwapOperands(
E->getOperand(0),
E->getOperand(1)))
1290 E->swapOperands(0, 1);
1296bool NewGVN::someEquivalentDominates(
const Instruction *Inst,
1298 auto *
CC = ValueToClass.
lookup(Inst);
1319 if (DT->
dominates(cast<Instruction>(
CC->getLeader()), U))
1321 if (
CC->getNextLeader().first &&
1322 DT->
dominates(cast<Instruction>(
CC->getNextLeader().first), U))
1325 return Member !=
CC->getLeader() &&
1326 DT->
dominates(cast<Instruction>(Member), U);
1332Value *NewGVN::lookupOperandLeader(
Value *V)
const {
1333 CongruenceClass *
CC = ValueToClass.
lookup(V);
1340 return CC->getStoredValue() ?
CC->getStoredValue() :
CC->getLeader();
1347 auto *
CC = getMemoryClass(MA);
1349 "Every MemoryAccess should be mapped to a congruence class with a "
1350 "representative memory access");
1351 return CC->getMemoryLeader();
1357bool NewGVN::isMemoryAccessTOP(
const MemoryAccess *MA)
const {
1358 return getMemoryClass(MA) == TOPClass;
1365 new (ExpressionAllocator)
LoadExpression(1, LI, lookupMemoryLeader(MA));
1366 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1367 E->setType(LoadType);
1371 E->op_push_back(PointerOp);
1381 auto *StoredValueLeader = lookupOperandLeader(
SI->getValueOperand());
1382 auto *
E =
new (ExpressionAllocator)
1384 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1385 E->setType(
SI->getValueOperand()->getType());
1389 E->op_push_back(lookupOperandLeader(
SI->getPointerOperand()));
1400 auto *
SI = cast<StoreInst>(
I);
1401 auto *StoreAccess = getMemoryAccess(SI);
1403 const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess();
1407 StoreRHS = lookupMemoryLeader(StoreRHS);
1408 if (StoreRHS != StoreAccess->getDefiningAccess())
1409 addMemoryUsers(StoreRHS, StoreAccess);
1411 if (StoreRHS == StoreAccess)
1414 if (
SI->isSimple()) {
1418 const auto *LastStore = createStoreExpression(SI, StoreRHS);
1419 const auto *LastCC = ExpressionToClass.lookup(LastStore);
1425 if (LastCC && LastCC->getStoredValue() == LastStore->getStoredValue())
1431 if (
auto *LI = dyn_cast<LoadInst>(LastStore->getStoredValue()))
1433 LastStore->getOperand(0)) &&
1434 (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) ==
1437 deleteExpression(LastStore);
1443 return createStoreExpression(SI, StoreAccess);
1449NewGVN::performSymbolicLoadCoercion(
Type *LoadType,
Value *LoadPtr,
1453 if (
auto *DepSI = dyn_cast<StoreInst>(DepInst)) {
1457 if (LI->
isAtomic() > DepSI->isAtomic() ||
1458 LoadType == DepSI->getValueOperand()->getType())
1462 if (
auto *
C = dyn_cast<Constant>(
1463 lookupOperandLeader(DepSI->getValueOperand()))) {
1466 <<
" to constant " << *Res <<
"\n");
1467 return createConstantExpression(Res);
1471 }
else if (
auto *DepLI = dyn_cast<LoadInst>(DepInst)) {
1473 if (LI->
isAtomic() > DepLI->isAtomic())
1478 if (
auto *
C = dyn_cast<Constant>(lookupOperandLeader(DepLI)))
1479 if (
auto *PossibleConstant =
1482 <<
" to constant " << *PossibleConstant <<
"\n");
1483 return createConstantExpression(PossibleConstant);
1486 }
else if (
auto *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1489 if (
auto *PossibleConstant =
1492 <<
" to constant " << *PossibleConstant <<
"\n");
1493 return createConstantExpression(PossibleConstant);
1500 if (LoadPtr != lookupOperandLeader(DepInst) &&
1507 if (isa<AllocaInst>(DepInst)) {
1512 else if (
auto *
II = dyn_cast<IntrinsicInst>(DepInst)) {
1513 if (
II->getIntrinsicID() == Intrinsic::lifetime_start)
1515 }
else if (
auto *InitVal =
1517 return createConstantExpression(InitVal);
1523 auto *LI = cast<LoadInst>(
I);
1532 if (isa<UndefValue>(LoadAddressLeader))
1539 if (
auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
1548 if (
const auto *CoercionResult =
1549 performSymbolicLoadCoercion(LI->
getType(), LoadAddressLeader, LI,
1550 DefiningInst, DefiningAccess))
1551 return CoercionResult;
1555 const auto *
LE = createLoadExpression(LI->
getType(), LoadAddressLeader, LI,
1559 if (
LE->getMemoryLeader() != DefiningAccess)
1560 addMemoryUsers(
LE->getMemoryLeader(), OriginalAccess);
1565NewGVN::performSymbolicPredicateInfoEvaluation(
IntrinsicInst *
I)
const {
1566 auto *PI = PredInfo->getPredicateInfoFor(
I);
1568 return ExprResult::none();
1570 LLVM_DEBUG(
dbgs() <<
"Found predicate info from instruction !\n");
1572 const std::optional<PredicateConstraint> &Constraint = PI->getConstraint();
1574 return ExprResult::none();
1577 Value *CmpOp0 =
I->getOperand(0);
1578 Value *CmpOp1 = Constraint->OtherOp;
1580 Value *FirstOp = lookupOperandLeader(CmpOp0);
1581 Value *SecondOp = lookupOperandLeader(CmpOp1);
1582 Value *AdditionallyUsedValue = CmpOp0;
1585 if (shouldSwapOperandsForIntrinsic(FirstOp, SecondOp,
I)) {
1588 AdditionallyUsedValue = CmpOp1;
1592 return ExprResult::some(createVariableOrConstant(FirstOp),
1593 AdditionallyUsedValue, PI);
1597 !cast<ConstantFP>(FirstOp)->
isZero())
1598 return ExprResult::some(createConstantExpression(cast<Constant>(FirstOp)),
1599 AdditionallyUsedValue, PI);
1601 return ExprResult::none();
1605NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(
Instruction *
I)
const {
1606 auto *CI = cast<CallInst>(
I);
1607 if (
auto *
II = dyn_cast<IntrinsicInst>(
I)) {
1609 if (
auto *ReturnedValue =
II->getReturnedArgOperand()) {
1610 if (
II->getIntrinsicID() == Intrinsic::ssa_copy)
1611 if (
auto Res = performSymbolicPredicateInfoEvaluation(
II))
1613 return ExprResult::some(createVariableOrConstant(ReturnedValue));
1625 return ExprResult::none();
1631 return ExprResult::none();
1634 return ExprResult::some(
1635 createCallExpression(CI, TOPClass->getMemoryLeader()));
1639 return ExprResult::some(createCallExpression(CI, DefiningAccess));
1641 return ExprResult::some(
1642 createCallExpression(CI, TOPClass->getMemoryLeader()));
1644 return ExprResult::none();
1648CongruenceClass *NewGVN::getMemoryClass(
const MemoryAccess *MA)
const {
1650 assert(Result &&
"Should have found memory class");
1657 CongruenceClass *NewClass) {
1659 "Every MemoryAccess should be getting mapped to a non-null class");
1663 <<
" with current MemoryAccess leader ");
1667 bool Changed =
false;
1669 if (LookupResult != MemoryAccessToClass.
end()) {
1671 if (OldClass != NewClass) {
1673 if (
auto *MP = dyn_cast<MemoryPhi>(
From)) {
1674 OldClass->memory_erase(MP);
1675 NewClass->memory_insert(MP);
1677 if (OldClass->getMemoryLeader() ==
From) {
1678 if (OldClass->definesNoMemory()) {
1679 OldClass->setMemoryLeader(
nullptr);
1681 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
1683 << OldClass->getID() <<
" to "
1684 << *OldClass->getMemoryLeader()
1685 <<
" due to removal of a memory member " << *
From
1687 markMemoryLeaderChangeTouched(OldClass);
1710 auto ICS = InstCycleState.
lookup(
I);
1711 if (ICS == ICS_Unknown) {
1713 auto &
SCC = SCCFinder.getComponentFor(
I);
1715 if (
SCC.size() == 1)
1716 InstCycleState.
insert({
I, ICS_CycleFree});
1721 ICS = AllPhis ? ICS_CycleFree : ICS_Cycle;
1722 for (
const auto *Member : SCC)
1723 if (
auto *MemberPhi = dyn_cast<PHINode>(Member))
1724 InstCycleState.
insert({MemberPhi, ICS});
1727 if (ICS == ICS_Cycle)
1738 bool HasBackedge =
false;
1743 bool OriginalOpsConstant =
true;
1744 auto *
E = cast<PHIExpression>(createPHIExpression(
1745 PHIOps,
I, PHIBlock, HasBackedge, OriginalOpsConstant));
1749 bool HasUndef =
false, HasPoison =
false;
1751 if (isa<PoisonValue>(Arg)) {
1755 if (isa<UndefValue>(Arg)) {
1762 if (Filtered.empty()) {
1767 dbgs() <<
"PHI Node " << *
I
1768 <<
" has no non-undef arguments, valuing it as undef\n");
1773 dbgs() <<
"PHI Node " << *
I
1774 <<
" has no non-poison arguments, valuing it as poison\n");
1778 LLVM_DEBUG(
dbgs() <<
"No arguments of PHI node " << *
I <<
" are live\n");
1779 deleteExpression(
E);
1780 return createDeadExpression();
1782 Value *AllSameValue = *(Filtered.begin());
1800 if (HasPoison || HasUndef) {
1806 if (HasBackedge && !OriginalOpsConstant &&
1807 !isa<UndefValue>(AllSameValue) && !isCycleFree(
I))
1811 if (
auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
1812 if (!someEquivalentDominates(AllSameInst,
I))
1818 if (isa<Instruction>(AllSameValue) &&
1819 InstrToDFSNum(AllSameValue) > InstrToDFSNum(
I))
1821 NumGVNPhisAllSame++;
1822 LLVM_DEBUG(
dbgs() <<
"Simplified PHI node " << *
I <<
" to " << *AllSameValue
1824 deleteExpression(
E);
1825 return createVariableOrConstant(AllSameValue);
1831NewGVN::performSymbolicAggrValueEvaluation(
Instruction *
I)
const {
1832 if (
auto *EI = dyn_cast<ExtractValueInst>(
I)) {
1833 auto *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
1834 if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0)
1838 return createBinaryExpression(WO->getBinaryOp(), EI->getType(),
1839 WO->getLHS(), WO->getRHS(),
I);
1842 return createAggregateValueExpression(
I);
1845NewGVN::ExprResult NewGVN::performSymbolicCmpEvaluation(
Instruction *
I)
const {
1846 assert(isa<CmpInst>(
I) &&
"Expected a cmp instruction.");
1848 auto *CI = cast<CmpInst>(
I);
1851 auto Op0 = lookupOperandLeader(CI->
getOperand(0));
1852 auto Op1 = lookupOperandLeader(CI->
getOperand(1));
1853 auto OurPredicate = CI->getPredicate();
1854 if (shouldSwapOperands(Op0, Op1)) {
1856 OurPredicate = CI->getSwappedPredicate();
1863 auto *CmpPI = PredInfo->getPredicateInfoFor(
I);
1864 if (isa_and_nonnull<PredicateAssume>(CmpPI))
1865 return ExprResult::some(
1870 if (CI->isTrueWhenEqual())
1871 return ExprResult::some(
1873 else if (CI->isFalseWhenEqual())
1874 return ExprResult::some(
1904 auto *PI = PredInfo->getPredicateInfoFor(
Op);
1905 if (
const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
1906 if (PI == LastPredInfo)
1911 if (!DT->
dominates(PBranch->To,
I->getParent()))
1918 auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
1921 auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
1922 auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
1923 auto BranchPredicate = BranchCond->getPredicate();
1924 if (shouldSwapOperands(BranchOp0, BranchOp1)) {
1926 BranchPredicate = BranchCond->getSwappedPredicate();
1928 if (BranchOp0 == Op0 && BranchOp1 == Op1) {
1929 if (PBranch->TrueEdge) {
1934 return ExprResult::some(
1941 return ExprResult::some(
1948 if (BranchPredicate == OurPredicate) {
1950 return ExprResult::some(
1953 }
else if (BranchPredicate ==
1956 return ExprResult::some(
1965 return createExpression(
I);
1977 switch (
I->getOpcode()) {
1978 case Instruction::ExtractValue:
1979 case Instruction::InsertValue:
1980 E = performSymbolicAggrValueEvaluation(
I);
1982 case Instruction::PHI: {
1984 auto *PN = cast<PHINode>(
I);
1985 for (
unsigned i = 0; i < PN->getNumOperands(); ++i)
1986 Ops.
push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)});
1989 E = performSymbolicPHIEvaluation(Ops,
I, getBlockForValue(
I));
1991 case Instruction::Call:
1992 return performSymbolicCallEvaluation(
I);
1994 case Instruction::Store:
1995 E = performSymbolicStoreEvaluation(
I);
1997 case Instruction::Load:
1998 E = performSymbolicLoadEvaluation(
I);
2000 case Instruction::BitCast:
2001 case Instruction::AddrSpaceCast:
2002 case Instruction::Freeze:
2003 return createExpression(
I);
2005 case Instruction::ICmp:
2006 case Instruction::FCmp:
2007 return performSymbolicCmpEvaluation(
I);
2009 case Instruction::FNeg:
2010 case Instruction::Add:
2011 case Instruction::FAdd:
2012 case Instruction::Sub:
2013 case Instruction::FSub:
2014 case Instruction::Mul:
2015 case Instruction::FMul:
2016 case Instruction::UDiv:
2017 case Instruction::SDiv:
2018 case Instruction::FDiv:
2019 case Instruction::URem:
2020 case Instruction::SRem:
2021 case Instruction::FRem:
2022 case Instruction::Shl:
2023 case Instruction::LShr:
2024 case Instruction::AShr:
2025 case Instruction::And:
2026 case Instruction::Or:
2027 case Instruction::Xor:
2028 case Instruction::Trunc:
2029 case Instruction::ZExt:
2030 case Instruction::SExt:
2031 case Instruction::FPToUI:
2032 case Instruction::FPToSI:
2033 case Instruction::UIToFP:
2034 case Instruction::SIToFP:
2035 case Instruction::FPTrunc:
2036 case Instruction::FPExt:
2037 case Instruction::PtrToInt:
2038 case Instruction::IntToPtr:
2039 case Instruction::Select:
2040 case Instruction::ExtractElement:
2041 case Instruction::InsertElement:
2042 case Instruction::GetElementPtr:
2043 return createExpression(
I);
2045 case Instruction::ShuffleVector:
2047 return ExprResult::none();
2049 return ExprResult::none();
2051 return ExprResult::some(
E);
2056template <
typename Map,
typename KeyType>
2057void NewGVN::touchAndErase(Map &M,
const KeyType &Key) {
2058 const auto Result =
M.find_as(Key);
2059 if (Result !=
M.end()) {
2060 for (
const typename Map::mapped_type::value_type Mapped :
Result->second)
2061 TouchedInstructions.
set(InstrToDFSNum(Mapped));
2068 if (isa<Instruction>(To))
2072void NewGVN::addAdditionalUsers(ExprResult &Res,
Instruction *
User)
const {
2073 if (Res.ExtraDep && Res.ExtraDep !=
User)
2074 addAdditionalUsers(Res.ExtraDep,
User);
2075 Res.ExtraDep =
nullptr;
2078 if (
const auto *PBranch = dyn_cast<PredicateBranch>(Res.PredDep))
2079 PredicateToUsers[PBranch->Condition].
insert(
User);
2080 else if (
const auto *PAssume = dyn_cast<PredicateAssume>(Res.PredDep))
2081 PredicateToUsers[PAssume->Condition].
insert(
User);
2083 Res.PredDep =
nullptr;
2086void NewGVN::markUsersTouched(
Value *V) {
2088 for (
auto *
User :
V->users()) {
2089 assert(isa<Instruction>(
User) &&
"Use of value not within an instruction?");
2090 TouchedInstructions.
set(InstrToDFSNum(
User));
2092 touchAndErase(AdditionalUsers, V);
2096 LLVM_DEBUG(
dbgs() <<
"Adding memory user " << *U <<
" to " << *To <<
"\n");
2097 MemoryToUsers[To].
insert(U);
2100void NewGVN::markMemoryDefTouched(
const MemoryAccess *MA) {
2101 TouchedInstructions.
set(MemoryToDFSNum(MA));
2104void NewGVN::markMemoryUsersTouched(
const MemoryAccess *MA) {
2105 if (isa<MemoryUse>(MA))
2107 for (
const auto *U : MA->
users())
2108 TouchedInstructions.
set(MemoryToDFSNum(U));
2109 touchAndErase(MemoryToUsers, MA);
2113void NewGVN::markPredicateUsersTouched(
Instruction *
I) {
2114 touchAndErase(PredicateToUsers,
I);
2118void NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *
CC) {
2119 for (
const auto *M :
CC->memory())
2120 markMemoryDefTouched(M);
2125void NewGVN::markValueLeaderChangeTouched(CongruenceClass *
CC) {
2126 for (
auto *M : *
CC) {
2127 if (
auto *
I = dyn_cast<Instruction>(M))
2128 TouchedInstructions.
set(InstrToDFSNum(
I));
2135template <
class T,
class Range>
2136T *NewGVN::getMinDFSOfRange(
const Range &R)
const {
2137 std::pair<T *, unsigned> MinDFS = {
nullptr, ~0
U};
2138 for (
const auto X : R) {
2139 auto DFSNum = InstrToDFSNum(
X);
2140 if (DFSNum < MinDFS.second)
2141 MinDFS = {
X, DFSNum};
2143 return MinDFS.first;
2149const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *
CC)
const {
2153 assert(!
CC->definesNoMemory() &&
"Can't get next leader if there is none");
2154 if (
CC->getStoreCount() > 0) {
2155 if (
auto *
NL = dyn_cast_or_null<StoreInst>(
CC->getNextLeader().first))
2156 return getMemoryAccess(
NL);
2159 *
CC, [&](
const Value *V) {
return isa<StoreInst>(V); }));
2160 return getMemoryAccess(cast<StoreInst>(V));
2166 if (
CC->memory_size() == 1)
2167 return *
CC->memory_begin();
2168 return getMinDFSOfRange<const MemoryPhi>(
CC->memory());
2174Value *NewGVN::getNextValueLeader(CongruenceClass *
CC)
const {
2179 if (
CC->size() == 1 ||
CC == TOPClass) {
2180 return *(
CC->begin());
2181 }
else if (
CC->getNextLeader().first) {
2182 ++NumGVNAvoidedSortedLeaderChanges;
2183 return CC->getNextLeader().first;
2185 ++NumGVNSortedLeaderChanges;
2189 return getMinDFSOfRange<Value>(*
CC);
2202void NewGVN::moveMemoryToNewCongruenceClass(
Instruction *
I,
2204 CongruenceClass *OldClass,
2205 CongruenceClass *NewClass) {
2208 assert((!InstMA || !OldClass->getMemoryLeader() ||
2209 OldClass->getLeader() !=
I ||
2210 MemoryAccessToClass.
lookup(OldClass->getMemoryLeader()) ==
2211 MemoryAccessToClass.
lookup(InstMA)) &&
2212 "Representative MemoryAccess mismatch");
2214 if (!NewClass->getMemoryLeader()) {
2216 assert(NewClass->size() == 1 ||
2217 (isa<StoreInst>(
I) && NewClass->getStoreCount() == 1));
2218 NewClass->setMemoryLeader(InstMA);
2221 << NewClass->getID()
2222 <<
" due to new memory instruction becoming leader\n");
2223 markMemoryLeaderChangeTouched(NewClass);
2225 setMemoryClass(InstMA, NewClass);
2227 if (OldClass->getMemoryLeader() == InstMA) {
2228 if (!OldClass->definesNoMemory()) {
2229 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
2231 << OldClass->getID() <<
" to "
2232 << *OldClass->getMemoryLeader()
2233 <<
" due to removal of old leader " << *InstMA <<
"\n");
2234 markMemoryLeaderChangeTouched(OldClass);
2236 OldClass->setMemoryLeader(
nullptr);
2243 CongruenceClass *OldClass,
2244 CongruenceClass *NewClass) {
2245 if (
I == OldClass->getNextLeader().first)
2246 OldClass->resetNextLeader();
2249 NewClass->insert(
I);
2251 if (NewClass->getLeader() !=
I)
2252 NewClass->addPossibleNextLeader({
I, InstrToDFSNum(
I)});
2254 if (
auto *SI = dyn_cast<StoreInst>(
I)) {
2255 OldClass->decStoreCount();
2263 if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) {
2266 if (
auto *SE = dyn_cast<StoreExpression>(
E)) {
2267 NewClass->setStoredValue(SE->getStoredValue());
2268 markValueLeaderChangeTouched(NewClass);
2271 << NewClass->getID() <<
" from "
2272 << *NewClass->getLeader() <<
" to " << *SI
2273 <<
" because store joined class\n");
2276 NewClass->setLeader(SI);
2280 NewClass->incStoreCount();
2286 auto *InstMA = dyn_cast_or_null<MemoryDef>(getMemoryAccess(
I));
2288 moveMemoryToNewCongruenceClass(
I, InstMA, OldClass, NewClass);
2289 ValueToClass[
I] = NewClass;
2291 if (OldClass->empty() && OldClass != TOPClass) {
2292 if (OldClass->getDefiningExpr()) {
2293 LLVM_DEBUG(
dbgs() <<
"Erasing expression " << *OldClass->getDefiningExpr()
2294 <<
" from table\n");
2297 auto Iter = ExpressionToClass.find_as(
2299 if (Iter != ExpressionToClass.end())
2300 ExpressionToClass.erase(Iter);
2301#ifdef EXPENSIVE_CHECKS
2303 (*OldClass->getDefiningExpr() != *
E || ExpressionToClass.lookup(
E)) &&
2304 "We erased the expression we just inserted, which should not happen");
2307 }
else if (OldClass->getLeader() ==
I) {
2312 << OldClass->getID() <<
"\n");
2313 ++NumGVNLeaderChanges;
2318 if (OldClass->getStoreCount() == 0) {
2319 if (OldClass->getStoredValue())
2320 OldClass->setStoredValue(
nullptr);
2322 OldClass->setLeader(getNextValueLeader(OldClass));
2323 OldClass->resetNextLeader();
2324 markValueLeaderChangeTouched(OldClass);
2330void NewGVN::markPhiOfOpsChanged(
const Expression *
E) {
2331 touchAndErase(ExpressionToPhiOfOps,
E);
2339 CongruenceClass *IClass = ValueToClass.
lookup(
I);
2340 assert(IClass &&
"Should have found a IClass");
2342 assert(!IClass->isDead() &&
"Found a dead class");
2344 CongruenceClass *EClass =
nullptr;
2345 if (
const auto *VE = dyn_cast<VariableExpression>(
E)) {
2346 EClass = ValueToClass.
lookup(VE->getVariableValue());
2347 }
else if (isa<DeadExpression>(
E)) {
2351 auto lookupResult = ExpressionToClass.insert({
E,
nullptr});
2354 if (lookupResult.second) {
2355 CongruenceClass *NewClass = createCongruenceClass(
nullptr,
E);
2356 auto place = lookupResult.first;
2357 place->second = NewClass;
2360 if (
const auto *CE = dyn_cast<ConstantExpression>(
E)) {
2361 NewClass->setLeader(
CE->getConstantValue());
2362 }
else if (
const auto *SE = dyn_cast<StoreExpression>(
E)) {
2364 NewClass->setLeader(SI);
2365 NewClass->setStoredValue(SE->getStoredValue());
2369 NewClass->setLeader(
I);
2371 assert(!isa<VariableExpression>(
E) &&
2372 "VariableExpression should have been handled already");
2376 <<
" using expression " << *
E <<
" at "
2377 << NewClass->getID() <<
" and leader "
2378 << *(NewClass->getLeader()));
2379 if (NewClass->getStoredValue())
2381 << *(NewClass->getStoredValue()));
2384 EClass = lookupResult.first->second;
2385 if (isa<ConstantExpression>(
E))
2386 assert((isa<Constant>(EClass->getLeader()) ||
2387 (EClass->getStoredValue() &&
2388 isa<Constant>(EClass->getStoredValue()))) &&
2389 "Any class with a constant expression should have a "
2392 assert(EClass &&
"Somehow don't have an eclass");
2394 assert(!EClass->isDead() &&
"We accidentally looked up a dead class");
2397 bool ClassChanged = IClass != EClass;
2398 bool LeaderChanged = LeaderChanges.
erase(
I);
2399 if (ClassChanged || LeaderChanged) {
2400 LLVM_DEBUG(
dbgs() <<
"New class " << EClass->getID() <<
" for expression "
2403 moveValueToNewCongruenceClass(
I,
E, IClass, EClass);
2404 markPhiOfOpsChanged(
E);
2407 markUsersTouched(
I);
2409 markMemoryUsersTouched(MA);
2410 if (
auto *CI = dyn_cast<CmpInst>(
I))
2411 markPredicateUsersTouched(CI);
2417 if (ClassChanged && isa<StoreInst>(
I)) {
2418 auto *OldE = ValueToExpression.
lookup(
I);
2421 if (OldE && isa<StoreExpression>(OldE) && *
E != *OldE) {
2425 if (Iter != ExpressionToClass.end())
2426 ExpressionToClass.erase(Iter);
2429 ValueToExpression[
I] =
E;
2436 if (ReachableEdges.
insert({From, To}).second) {
2438 if (ReachableBlocks.
insert(To).second) {
2440 <<
" marked reachable\n");
2441 const auto &InstRange = BlockInstRange.
lookup(To);
2442 TouchedInstructions.
set(InstRange.first, InstRange.second);
2445 <<
" was reachable, but new edge {"
2447 <<
"} to it found\n");
2454 TouchedInstructions.
set(InstrToDFSNum(MemPhi));
2459 for (
auto InstNum : RevisitOnReachabilityChange[To])
2460 TouchedInstructions.
set(InstNum);
2469 return isa<Constant>(Result) ?
Result :
nullptr;
2478 Value *CondEvaluated = findConditionEquivalence(
Cond);
2479 if (!CondEvaluated) {
2480 if (
auto *
I = dyn_cast<Instruction>(
Cond)) {
2482 auto Res = performSymbolicEvaluation(
I, Visited);
2483 if (
const auto *CE = dyn_cast_or_null<ConstantExpression>(Res.Expr)) {
2484 CondEvaluated =
CE->getConstantValue();
2485 addAdditionalUsers(Res,
I);
2489 Res.ExtraDep =
nullptr;
2491 }
else if (isa<ConstantInt>(
Cond)) {
2492 CondEvaluated =
Cond;
2496 if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
2499 <<
" evaluated to true\n");
2500 updateReachableEdge(
B, TrueSucc);
2501 }
else if (CI->
isZero()) {
2503 <<
" evaluated to false\n");
2504 updateReachableEdge(
B, FalseSucc);
2507 updateReachableEdge(
B, TrueSucc);
2508 updateReachableEdge(
B, FalseSucc);
2510 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
2514 Value *SwitchCond =
SI->getCondition();
2515 Value *CondEvaluated = findConditionEquivalence(SwitchCond);
2517 if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
2518 auto *CondVal = cast<ConstantInt>(CondEvaluated);
2520 auto Case = *
SI->findCaseValue(CondVal);
2521 if (Case.getCaseSuccessor() ==
SI->getDefaultDest()) {
2525 updateReachableEdge(
B,
SI->getDefaultDest());
2529 BasicBlock *TargetBlock = Case.getCaseSuccessor();
2530 updateReachableEdge(
B, TargetBlock);
2533 updateReachableEdge(
B, TargetBlock);
2539 updateReachableEdge(
B, TargetBlock);
2544 auto *MA = getMemoryAccess(TI);
2545 if (MA && !isa<MemoryUse>(MA)) {
2546 auto *
CC = ensureLeaderOfMemoryClass(MA);
2547 if (setMemoryClass(MA,
CC))
2548 markMemoryUsersTouched(MA);
2555 InstrDFS.
erase(PHITemp);
2558 TempToBlock.
erase(PHITemp);
2569 InstrDFS[
Op] = InstrToDFSNum(ExistingValue);
2571 TempToBlock[
Op] = BB;
2572 RealToTemp[ExistingValue] =
Op;
2575 for (
auto *U : ExistingValue->
users())
2576 if (
auto *UI = dyn_cast<Instruction>(U))
2583 return isa<BinaryOperator>(
I) || isa<SelectInst>(
I) || isa<CmpInst>(
I) ||
2598 while (!Worklist.
empty()) {
2600 if (!isa<Instruction>(
I))
2603 auto OISIt = OpSafeForPHIOfOps.
find({
I, CacheIdx});
2604 if (OISIt != OpSafeForPHIOfOps.
end())
2605 return OISIt->second;
2610 OpSafeForPHIOfOps.
insert({{
I, CacheIdx},
true});
2614 if (isa<PHINode>(
I) && getBlockForValue(
I) == PHIBlock) {
2615 OpSafeForPHIOfOps.
insert({{
I, CacheIdx},
false});
2619 auto *OrigI = cast<Instruction>(
I);
2626 if (OrigI->mayReadFromMemory())
2630 for (
auto *
Op : OrigI->operand_values()) {
2631 if (!isa<Instruction>(
Op))
2634 auto OISIt = OpSafeForPHIOfOps.
find({OrigI, CacheIdx});
2635 if (OISIt != OpSafeForPHIOfOps.
end()) {
2636 if (!OISIt->second) {
2637 OpSafeForPHIOfOps.
insert({{
I, CacheIdx},
false});
2647 OpSafeForPHIOfOps.
insert({{
V, CacheIdx},
true});
2660 unsigned IDFSNum = InstrToDFSNum(OrigInst);
2662 AllTempInstructions.
insert(TransInst);
2666 TempToBlock.
insert({TransInst, PredBB});
2667 InstrDFS.
insert({TransInst, IDFSNum});
2669 auto Res = performSymbolicEvaluation(TransInst, Visited);
2671 addAdditionalUsers(Res, OrigInst);
2672 InstrDFS.
erase(TransInst);
2673 AllTempInstructions.
erase(TransInst);
2674 TempToBlock.
erase(TransInst);
2676 TempToMemory.
erase(TransInst);
2679 auto *FoundVal = findPHIOfOpsLeader(
E, OrigInst, PredBB);
2681 ExpressionToPhiOfOps[
E].
insert(OrigInst);
2682 LLVM_DEBUG(
dbgs() <<
"Cannot find phi of ops operand for " << *TransInst
2686 if (
auto *SI = dyn_cast<StoreInst>(FoundVal))
2687 FoundVal =
SI->getValueOperand();
2699 if (!Visited.
insert(
I).second)
2705 if (!isCycleFree(
I))
2712 auto *MemAccess = getMemoryAccess(
I);
2716 if (MemAccess && !isa<MemoryPhi>(MemAccess->getDefiningAccess()) &&
2717 MemAccess->getDefiningAccess()->
getBlock() ==
I->getParent())
2727 for (
auto *
Op : Ops) {
2728 if (!isa<PHINode>(
Op)) {
2729 auto *ValuePHI = RealToTemp.
lookup(
Op);
2735 OpPHI = cast<PHINode>(
Op);
2736 if (!SamePHIBlock) {
2737 SamePHIBlock = getBlockForValue(OpPHI);
2738 }
else if (SamePHIBlock != getBlockForValue(OpPHI)) {
2741 <<
"PHIs for operands are not all in the same block, aborting\n");
2756 auto *PHIBlock = getBlockForValue(OpPHI);
2757 RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(
I));
2758 for (
unsigned PredNum = 0; PredNum < OpPHI->
getNumOperands(); ++PredNum) {
2760 Value *FoundVal =
nullptr;
2764 if (ReachableEdges.
count({PredBB, PHIBlock})) {
2772 TempToMemory.
insert({ValueOp, MemAccess});
2773 bool SafeForPHIOfOps =
true;
2776 auto *OrigOp = &*
Op;
2779 if (isa<PHINode>(
Op)) {
2780 Op =
Op->DoPHITranslation(PHIBlock, PredBB);
2781 if (
Op != OrigOp &&
Op !=
I)
2783 }
else if (
auto *ValuePHI = RealToTemp.
lookup(
Op)) {
2784 if (getBlockForValue(ValuePHI) == PHIBlock)
2785 Op = ValuePHI->getIncomingValueForBlock(PredBB);
2790 (
Op != OrigOp || OpIsSafeForPHIOfOps(
Op, PHIBlock, VisitedOps));
2797 FoundVal = !SafeForPHIOfOps ? nullptr
2798 : findLeaderForInst(ValueOp, Visited,
2799 MemAccess,
I, PredBB);
2804 if (SafeForPHIOfOps)
2805 for (
auto *Dep : CurrentDeps)
2806 addAdditionalUsers(Dep,
I);
2812 LLVM_DEBUG(
dbgs() <<
"Skipping phi of ops operand for incoming block "
2814 <<
" because the block is unreachable\n");
2816 RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(
I));
2820 LLVM_DEBUG(
dbgs() <<
"Found phi of ops operand " << *FoundVal <<
" in "
2823 for (
auto *Dep : Deps)
2824 addAdditionalUsers(Dep,
I);
2826 auto *
E = performSymbolicPHIEvaluation(PHIOps,
I, PHIBlock);
2827 if (isa<ConstantExpression>(
E) || isa<VariableExpression>(
E)) {
2830 <<
"Not creating real PHI of ops because it simplified to existing "
2831 "value or constant\n");
2837 for (
auto &O : PHIOps)
2838 addAdditionalUsers(
O.first,
I);
2842 auto *ValuePHI = RealToTemp.
lookup(
I);
2843 bool NewPHI =
false;
2847 addPhiOfOps(ValuePHI, PHIBlock,
I);
2849 NumGVNPHIOfOpsCreated++;
2852 for (
auto PHIOp : PHIOps)
2853 ValuePHI->addIncoming(PHIOp.first, PHIOp.second);
2855 TempToBlock[ValuePHI] = PHIBlock;
2857 for (
auto PHIOp : PHIOps) {
2858 ValuePHI->setIncomingValue(i, PHIOp.first);
2859 ValuePHI->setIncomingBlock(i, PHIOp.second);
2863 RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(
I));
2864 LLVM_DEBUG(
dbgs() <<
"Created phi of ops " << *ValuePHI <<
" for " << *
I
2873void NewGVN::initializeCongruenceClasses(
Function &
F) {
2874 NextCongruenceNum = 0;
2884 TOPClass = createCongruenceClass(
nullptr,
nullptr);
2890 for (
auto *DTN :
nodes(DT)) {
2897 if (MemoryBlockDefs)
2898 for (
const auto &Def : *MemoryBlockDefs) {
2899 MemoryAccessToClass[&
Def] = TOPClass;
2900 auto *MD = dyn_cast<MemoryDef>(&Def);
2903 const MemoryPhi *MP = cast<MemoryPhi>(&Def);
2904 TOPClass->memory_insert(MP);
2905 MemoryPhiState.
insert({MP, MPS_TOP});
2908 if (MD && isa<StoreInst>(MD->getMemoryInst()))
2909 TOPClass->incStoreCount();
2915 for (
auto &
I : *BB) {
2916 if (isa<PHINode>(&
I))
2917 for (
auto *U :
I.users())
2918 if (
auto *UInst = dyn_cast<Instruction>(U))
2920 PHINodeUses.
insert(UInst);
2923 if (
I.isTerminator() &&
I.getType()->isVoidTy())
2925 TOPClass->insert(&
I);
2926 ValueToClass[&
I] = TOPClass;
2931 for (
auto &FA :
F.args())
2932 createSingletonCongruenceClass(&FA);
2935void NewGVN::cleanupTables() {
2936 for (CongruenceClass *&
CC : CongruenceClasses) {
2938 <<
CC->size() <<
" members\n");
2947 AllTempInstructions.
end());
2948 AllTempInstructions.
clear();
2952 for (
auto *
I : TempInst) {
2953 I->dropAllReferences();
2956 while (!TempInst.empty()) {
2957 auto *
I = TempInst.pop_back_val();
2961 ValueToClass.
clear();
2962 ArgRecycler.
clear(ExpressionAllocator);
2963 ExpressionAllocator.
Reset();
2964 CongruenceClasses.clear();
2965 ExpressionToClass.clear();
2966 ValueToExpression.
clear();
2968 AdditionalUsers.
clear();
2969 ExpressionToPhiOfOps.
clear();
2970 TempToBlock.
clear();
2971 TempToMemory.
clear();
2972 PHINodeUses.
clear();
2973 OpSafeForPHIOfOps.
clear();
2974 ReachableBlocks.
clear();
2975 ReachableEdges.
clear();
2977 ProcessedCount.
clear();
2980 InstructionsToErase.
clear();
2982 BlockInstRange.
clear();
2983 TouchedInstructions.
clear();
2984 MemoryAccessToClass.
clear();
2985 PredicateToUsers.
clear();
2986 MemoryToUsers.
clear();
2987 RevisitOnReachabilityChange.
clear();
2988 IntrinsicInstPred.
clear();
2993std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(
BasicBlock *
B,
2995 unsigned End = Start;
2997 InstrDFS[MemPhi] =
End++;
3002 for (
auto &
I : *
B) {
3008 LLVM_DEBUG(
dbgs() <<
"Skipping trivially dead instruction " <<
I <<
"\n");
3009 markInstructionForDeletion(&
I);
3012 if (isa<PHINode>(&
I))
3013 RevisitOnReachabilityChange[
B].set(
End);
3014 InstrDFS[&
I] =
End++;
3021 return std::make_pair(Start,
End);
3024void NewGVN::updateProcessedCount(
const Value *V) {
3026 if (ProcessedCount.
count(V) == 0) {
3027 ProcessedCount.
insert({
V, 1});
3029 ++ProcessedCount[
V];
3030 assert(ProcessedCount[V] < 100 &&
3031 "Seem to have processed the same Value a lot");
3037void NewGVN::valueNumberMemoryPhi(
MemoryPhi *MP) {
3044 return cast<MemoryAccess>(U) != MP &&
3045 !isMemoryAccessTOP(cast<MemoryAccess>(U)) &&
3046 ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock});
3051 if (Filtered.begin() == Filtered.end()) {
3052 if (setMemoryClass(MP, TOPClass))
3053 markMemoryUsersTouched(MP);
3059 auto LookupFunc = [&](
const Use &
U) {
3060 return lookupMemoryLeader(cast<MemoryAccess>(U));
3062 auto MappedBegin =
map_iterator(Filtered.begin(), LookupFunc);
3063 auto MappedEnd =
map_iterator(Filtered.end(), LookupFunc);
3067 const auto *AllSameValue = *MappedBegin;
3069 bool AllEqual = std::all_of(
3070 MappedBegin, MappedEnd,
3071 [&AllSameValue](
const MemoryAccess *V) {
return V == AllSameValue; });
3074 LLVM_DEBUG(
dbgs() <<
"Memory Phi value numbered to " << *AllSameValue
3083 CongruenceClass *
CC =
3084 AllEqual ? getMemoryClass(AllSameValue) : ensureLeaderOfMemoryClass(MP);
3085 auto OldState = MemoryPhiState.
lookup(MP);
3086 assert(OldState != MPS_Invalid &&
"Invalid memory phi state");
3087 auto NewState = AllEqual ? MPS_Equivalent : MPS_Unique;
3088 MemoryPhiState[MP] = NewState;
3089 if (setMemoryClass(MP,
CC) || OldState != NewState)
3090 markMemoryUsersTouched(MP);
3097 if (!
I->isTerminator()) {
3101 auto Res = performSymbolicEvaluation(
I, Visited);
3102 Symbolized = Res.Expr;
3103 addAdditionalUsers(Res,
I);
3106 if (Symbolized && !isa<ConstantExpression>(Symbolized) &&
3107 !isa<VariableExpression>(Symbolized) && PHINodeUses.
count(
I)) {
3108 auto *PHIE = makePossiblePHIOfOps(
I, Visited);
3113 }
else if (
auto *
Op = RealToTemp.
lookup(
I)) {
3114 removePhiOfOps(
I,
Op);
3123 if (Symbolized ==
nullptr)
3124 Symbolized = createUnknownExpression(
I);
3125 performCongruenceFinding(
I, Symbolized);
3130 if (!
I->getType()->isVoidTy()) {
3131 auto *Symbolized = createUnknownExpression(
I);
3132 performCongruenceFinding(
I, Symbolized);
3134 processOutgoingEdges(
I,
I->getParent());
3140bool NewGVN::singleReachablePHIPath(
3143 if (
First == Second)
3156 const auto *EndDef =
First;
3158 if (ChainDef == Second)
3164 auto *MP = cast<MemoryPhi>(EndDef);
3165 auto ReachableOperandPred = [&](
const Use &
U) {
3168 auto FilteredPhiArgs =
3171 llvm::copy(FilteredPhiArgs, std::back_inserter(OperandList));
3174 return singleReachablePHIPath(Visited, cast<MemoryAccess>(OperandList[0]),
3183void NewGVN::verifyMemoryCongruency()
const {
3186 for (
const auto *
CC : CongruenceClasses) {
3187 if (
CC == TOPClass ||
CC->isDead())
3189 if (
CC->getStoreCount() != 0) {
3190 assert((
CC->getStoredValue() || !isa<StoreInst>(
CC->getLeader())) &&
3191 "Any class with a store as a leader should have a "
3192 "representative stored value");
3194 "Any congruence class with a store should have a "
3195 "representative access");
3198 if (
CC->getMemoryLeader())
3200 "Representative MemoryAccess does not appear to be reverse "
3202 for (
const auto *M :
CC->memory())
3204 "Memory member does not appear to be reverse mapped properly");
3212 auto ReachableAccessPred =
3213 [&](
const std::pair<const MemoryAccess *, CongruenceClass *> Pair) {
3214 bool Result = ReachableBlocks.
count(Pair.first->getBlock());
3216 MemoryToDFSNum(Pair.first) == 0)
3218 if (
auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
3223 if (
auto *MemPHI = dyn_cast<MemoryPhi>(Pair.first)) {
3224 for (
const auto &U : MemPHI->incoming_values()) {
3225 if (
auto *
I = dyn_cast<Instruction>(&*U)) {
3237 for (
auto KV : Filtered) {
3238 if (
auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
3239 auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second->getMemoryLeader());
3240 if (FirstMUD && SecondMUD) {
3242 assert((singleReachablePHIPath(VisitedMAS, FirstMUD, SecondMUD) ||
3243 ValueToClass.
lookup(FirstMUD->getMemoryInst()) ==
3244 ValueToClass.
lookup(SecondMUD->getMemoryInst())) &&
3245 "The instructions for these memory operations should have "
3246 "been in the same congruence class or reachable through"
3247 "a single argument phi");
3249 }
else if (
auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {
3252 auto ReachableOperandPred = [&](
const Use &
U) {
3253 return ReachableEdges.
count(
3254 {FirstMP->getIncomingBlock(U), FirstMP->getBlock()}) &&
3259 auto FilteredPhiArgs =
3262 std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
3263 std::back_inserter(PhiOpClasses), [&](
const Use &U) {
3264 const MemoryDef *MD = cast<MemoryDef>(U);
3265 return ValueToClass.lookup(MD->getMemoryInst());
3268 "All MemoryPhi arguments should be in the same class");
3277void NewGVN::verifyIterationSettled(
Function &
F) {
3287 std::map<const Value *, CongruenceClass> BeforeIteration;
3289 for (
auto &KV : ValueToClass) {
3290 if (
auto *
I = dyn_cast<Instruction>(KV.first))
3292 if (InstrToDFSNum(
I) == 0)
3294 BeforeIteration.insert({KV.first, *KV.second});
3297 TouchedInstructions.
set();
3298 TouchedInstructions.
reset(0);
3299 OpSafeForPHIOfOps.
clear();
3301 iterateTouchedInstructions();
3304 for (
const auto &KV : ValueToClass) {
3305 if (
auto *
I = dyn_cast<Instruction>(KV.first))
3307 if (InstrToDFSNum(
I) == 0)
3311 auto *BeforeCC = &BeforeIteration.
find(KV.first)->second;
3312 auto *AfterCC = KV.second;
3315 if (!EqualClasses.
count({BeforeCC, AfterCC})) {
3316 assert(BeforeCC->isEquivalentTo(AfterCC) &&
3317 "Value number changed after main loop completed!");
3318 EqualClasses.
insert({BeforeCC, AfterCC});
3329void NewGVN::verifyStoreExpressions()
const {
3334 std::pair<
const Value *,
3335 std::tuple<const Value *, const CongruenceClass *, Value *>>>
3337 for (
const auto &KV : ExpressionToClass) {
3338 if (
auto *SE = dyn_cast<StoreExpression>(KV.first)) {
3340 auto Res = StoreExpressionSet.insert(
3341 {SE->getOperand(0), std::make_tuple(SE->getMemoryLeader(), KV.second,
3342 SE->getStoredValue())});
3343 bool Okay = Res.second;
3348 Okay = (std::get<1>(Res.first->second) == KV.second) &&
3349 (lookupOperandLeader(std::get<2>(Res.first->second)) ==
3350 lookupOperandLeader(SE->getStoredValue()));
3351 assert(Okay &&
"Stored expression conflict exists in expression table");
3352 auto *ValueExpr = ValueToExpression.
lookup(SE->getStoreInst());
3353 assert(ValueExpr && ValueExpr->equals(*SE) &&
3354 "StoreExpression in ExpressionToClass is not latest "
3355 "StoreExpression for value");
3364void NewGVN::iterateTouchedInstructions() {
3367 int FirstInstr = TouchedInstructions.
find_first();
3369 if (FirstInstr == -1)
3371 const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
3372 while (TouchedInstructions.
any()) {
3378 for (
unsigned InstrNum : TouchedInstructions.
set_bits()) {
3382 if (InstrNum == 0) {
3383 TouchedInstructions.
reset(InstrNum);
3387 Value *
V = InstrFromDFSNum(InstrNum);
3388 const BasicBlock *CurrBlock = getBlockForValue(V);
3391 if (CurrBlock != LastBlock) {
3392 LastBlock = CurrBlock;
3393 bool BlockReachable = ReachableBlocks.
count(CurrBlock);
3394 const auto &CurrInstRange = BlockInstRange.
lookup(CurrBlock);
3397 if (!BlockReachable) {
3398 TouchedInstructions.
reset(CurrInstRange.first, CurrInstRange.second);
3401 <<
" because it is unreachable\n");
3406 updateProcessedCount(CurrBlock);
3410 TouchedInstructions.
reset(InstrNum);
3412 if (
auto *MP = dyn_cast<MemoryPhi>(V)) {
3414 valueNumberMemoryPhi(MP);
3415 }
else if (
auto *
I = dyn_cast<Instruction>(V)) {
3416 valueNumberInstruction(
I);
3420 updateProcessedCount(V);
3423 NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations);
3427bool NewGVN::runGVN() {
3430 bool Changed =
false;
3431 NumFuncArgs =
F.arg_size();
3433 SingletonDeadExpression =
new (ExpressionAllocator)
DeadExpression();
3437 unsigned ICount = 1;
3449 unsigned Counter = 0;
3450 for (
auto &
B : RPOT) {
3452 assert(
Node &&
"RPO and Dominator tree should have same reachability");
3453 RPOOrdering[
Node] = ++Counter;
3456 for (
auto &
B : RPOT) {
3458 if (
Node->getNumChildren() > 1)
3460 return RPOOrdering[
A] < RPOOrdering[
B];
3467 const auto &BlockRange = assignDFSNumbers(
B, ICount);
3468 BlockInstRange.
insert({
B, BlockRange});
3469 ICount += BlockRange.second - BlockRange.first;
3471 initializeCongruenceClasses(
F);
3473 TouchedInstructions.
resize(ICount);
3477 ExpressionToClass.reserve(ICount);
3480 const auto &InstRange = BlockInstRange.
lookup(&
F.getEntryBlock());
3481 TouchedInstructions.
set(InstRange.first, InstRange.second);
3483 <<
" marked reachable\n");
3484 ReachableBlocks.
insert(&
F.getEntryBlock());
3488 iterateTouchedInstructions();
3489 verifyMemoryCongruency();
3490 verifyIterationSettled(
F);
3491 verifyStoreExpressions();
3493 Changed |= eliminateInstructions(
F);
3496 for (
Instruction *ToErase : InstructionsToErase) {
3497 if (!ToErase->use_empty())
3500 assert(ToErase->getParent() &&
3501 "BB containing ToErase deleted unexpectedly!");
3502 ToErase->eraseFromParent();
3504 Changed |= !InstructionsToErase.empty();
3507 auto UnreachableBlockPred = [&](
const BasicBlock &BB) {
3508 return !ReachableBlocks.
count(&BB);
3513 <<
" is unreachable\n");
3514 deleteInstructionsInBlock(&BB);
3572 return std::tie(DFSIn, DFSOut,
LocalNum, Def, U) <
3583void NewGVN::convertClassToDFSOrdered(
3592 assert(BB &&
"Should have figured out a basic block for value");
3600 if (
auto *SI = dyn_cast<StoreInst>(
D)) {
3601 auto Leader = lookupOperandLeader(SI->getValueOperand());
3603 VDDef.
Def.setPointer(Leader);
3605 VDDef.
Def.setPointer(
SI->getValueOperand());
3606 VDDef.
Def.setInt(
true);
3609 VDDef.
Def.setPointer(
D);
3612 "The dense set member should always be an instruction");
3617 if (
auto *PN = RealToTemp.
lookup(Def)) {
3619 dyn_cast_or_null<PHIExpression>(ValueToExpression.
lookup(Def));
3621 VDDef.
Def.setInt(
false);
3622 VDDef.
Def.setPointer(PN);
3628 unsigned int UseCount = 0;
3630 for (
auto &U :
Def->uses()) {
3631 if (
auto *
I = dyn_cast<Instruction>(
U.getUser())) {
3633 if (InstructionsToErase.count(
I))
3638 if (
auto *
P = dyn_cast<PHINode>(
I)) {
3639 IBlock =
P->getIncomingBlock(U);
3644 IBlock = getBlockForValue(
I);
3650 if (!ReachableBlocks.
contains(IBlock))
3666 ProbablyDead.
insert(Def);
3668 UseCounts[
Def] = UseCount;
3674void NewGVN::convertClassToLoadsAndStores(
3675 const CongruenceClass &
Dense,
3678 if (!isa<LoadInst>(
D) && !isa<StoreInst>(
D))
3686 VD.
Def.setPointer(
D);
3689 if (
auto *
I = dyn_cast<Instruction>(
D))
3700 I->replaceAllUsesWith(Repl);
3703void NewGVN::deleteInstructionsInBlock(
BasicBlock *BB) {
3705 ++NumGVNBlocksDeleted;
3709 auto StartPoint = BB->
rbegin();
3717 if (isa<LandingPadInst>(Inst))
3722 ++NumGVNInstrDeleted;
3732void NewGVN::markInstructionForDeletion(
Instruction *
I) {
3734 InstructionsToErase.insert(
I);
3742 markInstructionForDeletion(
I);
3749class ValueDFSStack {
3751 Value *back()
const {
return ValueStack.back(); }
3752 std::pair<int, int> dfs_back()
const {
return DFSStack.back(); }
3754 void push_back(
Value *V,
int DFSIn,
int DFSOut) {
3755 ValueStack.emplace_back(V);
3756 DFSStack.emplace_back(DFSIn, DFSOut);
3759 bool empty()
const {
return DFSStack.empty(); }
3761 bool isInScope(
int DFSIn,
int DFSOut)
const {
3764 return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
3767 void popUntilDFSScope(
int DFSIn,
int DFSOut) {
3770 assert(ValueStack.size() == DFSStack.size() &&
3771 "Mismatch between ValueStack and DFSStack");
3773 !DFSStack.empty() &&
3774 !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
3775 DFSStack.pop_back();
3776 ValueStack.pop_back();
3788CongruenceClass *NewGVN::getClassForExpression(
const Expression *E)
const {
3789 if (
auto *VE = dyn_cast<VariableExpression>(E))
3790 return ValueToClass.lookup(VE->getVariableValue());
3791 else if (isa<DeadExpression>(E))
3793 return ExpressionToClass.lookup(E);
3802 if (
auto *CE = dyn_cast<ConstantExpression>(E))
3803 return CE->getConstantValue();
3804 if (
auto *VE = dyn_cast<VariableExpression>(E)) {
3805 auto *
V = VE->getVariableValue();
3807 return VE->getVariableValue();
3810 auto *
CC = getClassForExpression(E);
3814 return CC->getLeader();
3816 for (
auto *Member : *
CC) {
3817 auto *MemberInst = dyn_cast<Instruction>(Member);
3818 if (MemberInst == OrigInst)
3823 if (DT->
dominates(getBlockForValue(MemberInst), BB))
3829bool NewGVN::eliminateInstructions(
Function &
F) {
3853 bool AnythingReplaced =
false;
3862 for (
auto &Operand :
PHI->incoming_values())
3863 if (!ReachableEdges.
count({PHI->getIncomingBlock(Operand), BB})) {
3867 <<
" with poison due to it being unreachable\n");
3881 for (
auto &KV : ReachableEdges)
3882 ReachablePredCount[KV.getEnd()]++;
3883 for (
auto &BBPair : RevisitOnReachabilityChange) {
3884 for (
auto InstNum : BBPair.second) {
3885 auto *Inst = InstrFromDFSNum(InstNum);
3886 auto *
PHI = dyn_cast<PHINode>(Inst);
3890 auto *BB = BBPair.first;
3891 if (ReachablePredCount.
lookup(BB) !=
PHI->getNumIncomingValues())
3892 ReplaceUnreachablePHIArgs(
PHI, BB);
3898 for (
auto *
CC :
reverse(CongruenceClasses)) {
3905 if (
CC->isDead() ||
CC->empty())
3908 if (
CC == TOPClass) {
3909 for (
auto *M : *
CC) {
3910 auto *VTE = ValueToExpression.
lookup(M);
3911 if (VTE && isa<DeadExpression>(VTE))
3912 markInstructionForDeletion(cast<Instruction>(M));
3913 assert((!ReachableBlocks.
count(cast<Instruction>(M)->getParent()) ||
3914 InstructionsToErase.count(cast<Instruction>(M))) &&
3915 "Everything in TOP should be unreachable or dead at this "
3921 assert(
CC->getLeader() &&
"We should have had a leader");
3927 CC->getStoredValue() ?
CC->getStoredValue() :
CC->getLeader();
3930 for (
auto *M : *
CC) {
3933 if (Member == Leader || !isa<Instruction>(Member) ||
3934 Member->getType()->isVoidTy()) {
3935 MembersLeft.
insert(Member);
3938 LLVM_DEBUG(
dbgs() <<
"Found replacement " << *(Leader) <<
" for "
3939 << *Member <<
"\n");
3940 auto *
I = cast<Instruction>(Member);
3941 assert(Leader !=
I &&
"About to accidentally remove our leader");
3942 replaceInstruction(
I, Leader);
3943 AnythingReplaced =
true;
3945 CC->swap(MembersLeft);
3948 if (
CC->size() != 1 || RealToTemp.
count(Leader)) {
3953 ValueDFSStack EliminationStack;
3957 convertClassToDFSOrdered(*
CC, DFSOrderedSet, UseCounts, ProbablyDead);
3961 for (
auto &VD : DFSOrderedSet) {
3962 int MemberDFSIn = VD.
DFSIn;
3963 int MemberDFSOut = VD.
DFSOut;
3965 bool FromStore = VD.
Def.getInt();
3968 if (Def &&
Def->getType()->isVoidTy())
3970 auto *DefInst = dyn_cast_or_null<Instruction>(Def);
3971 if (DefInst && AllTempInstructions.
count(DefInst)) {
3972 auto *PN = cast<PHINode>(DefInst);
3977 AllTempInstructions.
erase(PN);
3978 auto *DefBlock = getBlockForValue(Def);
3982 PN->insertBefore(&DefBlock->front());
3984 NumGVNPHIOfOpsEliminations++;
3987 if (EliminationStack.empty()) {
3991 << EliminationStack.dfs_back().first <<
","
3992 << EliminationStack.dfs_back().second <<
")\n");
3995 LLVM_DEBUG(
dbgs() <<
"Current DFS numbers are (" << MemberDFSIn <<
","
3996 << MemberDFSOut <<
")\n");
4010 bool ShouldPush =
Def && EliminationStack.empty();
4012 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
4014 if (OutOfScope || ShouldPush) {
4016 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4017 bool ShouldPush =
Def && EliminationStack.empty();
4019 EliminationStack.push_back(Def, MemberDFSIn, MemberDFSOut);
4038 auto *DefI = dyn_cast<Instruction>(Def);
4039 if (!EliminationStack.empty() && DefI && !FromStore) {
4040 Value *DominatingLeader = EliminationStack.back();
4041 if (DominatingLeader != Def) {
4044 if (!
match(DefI, m_Intrinsic<Intrinsic::ssa_copy>()))
4047 markInstructionForDeletion(DefI);
4055 assert(isa<Instruction>(
U->get()) &&
4056 "Current def should have been an instruction");
4057 assert(isa<Instruction>(
U->getUser()) &&
4058 "Current user should have been an instruction");
4064 Instruction *InstUse = cast<Instruction>(
U->getUser());
4065 if (InstructionsToErase.count(InstUse)) {
4066 auto &UseCount = UseCounts[
U->get()];
4067 if (--UseCount == 0) {
4068 ProbablyDead.
insert(cast<Instruction>(
U->get()));
4074 if (EliminationStack.empty())
4077 Value *DominatingLeader = EliminationStack.back();
4079 auto *
II = dyn_cast<IntrinsicInst>(DominatingLeader);
4080 bool isSSACopy =
II &&
II->getIntrinsicID() == Intrinsic::ssa_copy;
4082 DominatingLeader =
II->getOperand(0);
4085 if (
U->get() == DominatingLeader)
4088 <<
"Found replacement " << *DominatingLeader <<
" for "
4089 << *
U->get() <<
" in " << *(
U->getUser()) <<
"\n");
4094 auto *ReplacedInst = cast<Instruction>(
U->get());
4095 auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
4096 if (!PI || DominatingLeader != PI->OriginalOp)
4098 U->set(DominatingLeader);
4101 auto &LeaderUseCount = UseCounts[DominatingLeader];
4103 if (LeaderUseCount == 0 && isa<Instruction>(DominatingLeader))
4104 ProbablyDead.
erase(cast<Instruction>(DominatingLeader));
4108 auto It = UseCounts.
find(
II);
4109 if (It != UseCounts.
end()) {
4110 unsigned &IIUseCount = It->second;
4111 if (--IIUseCount == 0)
4116 AnythingReplaced =
true;
4123 for (
auto *
I : ProbablyDead)
4125 markInstructionForDeletion(
I);
4129 for (
auto *Member : *
CC)
4130 if (!isa<Instruction>(Member) ||
4131 !InstructionsToErase.count(cast<Instruction>(Member)))
4132 MembersLeft.
insert(Member);
4133 CC->swap(MembersLeft);
4136 if (
CC->getStoreCount() > 0) {
4137 convertClassToLoadsAndStores(*
CC, PossibleDeadStores);
4139 ValueDFSStack EliminationStack;
4140 for (
auto &VD : PossibleDeadStores) {
4141 int MemberDFSIn = VD.
DFSIn;
4142 int MemberDFSOut = VD.
DFSOut;
4144 if (EliminationStack.empty() ||
4145 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) {
4147 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4148 if (EliminationStack.empty()) {
4149 EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
4154 if (isa<LoadInst>(Member))
4156 assert(!EliminationStack.empty());
4157 Instruction *Leader = cast<Instruction>(EliminationStack.back());
4162 <<
" that is dominated by " << *Leader <<
"\n");
4163 markInstructionForDeletion(Member);
4169 return AnythingReplaced;
4177unsigned int NewGVN::getRank(
const Value *V)
const {
4183 if (isa<ConstantExpr>(V))
4185 if (isa<PoisonValue>(V))
4187 if (isa<UndefValue>(V))
4189 if (isa<Constant>(V))
4191 if (
auto *
A = dyn_cast<Argument>(V))
4192 return 4 +
A->getArgNo();
4196 unsigned Result = InstrToDFSNum(V);
4198 return 5 + NumFuncArgs +
Result;
4205bool NewGVN::shouldSwapOperands(
const Value *
A,
const Value *
B)
const {
4209 return std::make_pair(getRank(
A),
A) > std::make_pair(getRank(
B),
B);
4212bool NewGVN::shouldSwapOperandsForIntrinsic(
const Value *
A,
const Value *
B,
4215 if (shouldSwapOperands(
A,
B)) {
4216 if (LookupResult == IntrinsicInstPred.
end())
4223 if (LookupResult != IntrinsicInstPred.
end()) {
4225 if (SeenPredicate) {
4226 if (SeenPredicate ==
B)
4245 NewGVN(
F, &DT, &AC, &TLI, &AA, &MSSA,
F.getDataLayout())
Unify divergent function exit nodes
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file defines the BumpPtrAllocator interface.
This file implements the BitVector class.
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
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")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
std::optional< std::vector< StOtherPiece > > Other
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
The header file for the GVN pass that contains expression handling classes.
static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl)
This is the interface for a simple mod/ref and alias analysis over globals.
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
This defines the Use class.
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.
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Branch Probability Basic Block static false std::string getBlockName(const MachineBasicBlock *BB)
Helper to print the name of a MBB.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
static bool alwaysAvailable(Value *V)
static Value * getCopyOf(const Value *V)
static bool isCopyOfPHI(const Value *V, const PHINode *PN)
static bool isCopyOfAPHI(const Value *V)
static bool okayForPHIOfOps(const Instruction *I)
static cl::opt< bool > EnableStoreRefinement("enable-store-refinement", cl::init(false), cl::Hidden)
static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS)
static cl::opt< bool > EnablePhiOfOps("enable-phi-of-ops", cl::init(true), cl::Hidden)
Currently, the generation "phi of ops" can result in correctness issues.
This file provides the interface for LLVM's Global Value Numbering pass.
This file defines the PointerIntPair class.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file implements the PredicateInfo analysis, which creates an Extended SSA form for operations us...
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines generic set operations that may be used on set's of different types,...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the SparseBitVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A manager for alias analyses.
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are must-alias.
bool doesNotAccessMemory(const CallBase *Call)
Checks if the specified call is known to never read or write memory.
bool onlyReadsMemory(const CallBase *Call)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Recycle small arrays allocated from a BumpPtrAllocator.
void clear(AllocatorType &Allocator)
Release all the tracked allocations to the allocator.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
reverse_iterator rbegin()
InstListType::reverse_iterator reverse_iterator
LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
void clear()
clear - Removes all bits from the bitvector.
bool any() const
any - Returns true if any bit is set.
iterator_range< const_set_bits_iterator > set_bits() const
Allocate memory in an ever growing pool, as if by bump-pointer.
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
void Deallocate(const void *Ptr, size_t Size, size_t)
bool isConvergent() const
Determine if the invoke is convergent.
This class represents a function call, abstracting a target machine's calling convention.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ FCMP_OEQ
0 0 0 1 True if ordered and equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
static bool isImpliedTrueByMatchingCmp(Predicate Pred1, Predicate Pred2)
Determine if Pred1 implies Pred2 is true when two compares have matching operands.
static bool isImpliedFalseByMatchingCmp(Predicate Pred1, Predicate Pred2)
Determine if Pred1 implies Pred2 is false when two compares have matching operands.
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
static ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static ConstantInt * getFalse(LLVMContext &Context)
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
static CounterState getCounterState(unsigned ID)
static bool isCounterSet(unsigned ID)
static bool shouldExecute(unsigned CounterName)
static void setCounterState(unsigned ID, CounterState State)
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...
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
unsigned getDFSNumOut() const
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Class representing an expression and its matching format.
bool isPresplitCoroutine() const
Determine if the function is presplit coroutine.
~AggregateValueExpression() override
~BasicExpression() override
~CallExpression() override
bool equals(const Expression &Other) const override
~LoadExpression() override
~PHIExpression() override
bool equals(const Expression &Other) const override
~StoreExpression() override
Value * getStoredValue() const
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
const Function * getFunction() const
Return the function this instruction belongs to.
A wrapper class for inspecting calls to intrinsic functions.
An instruction for reading from memory.
Value * getPointerOperand()
BasicBlock * getBlock() const
Represents phi nodes for memory accesses.
BasicBlock * getIncomingBlock(unsigned I) const
Return incoming basic block number i.
An analysis that produces MemorySSA for a function.
This is the generic walker interface for walkers of MemorySSA.
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Encapsulates MemorySSA, including all data associated with memory accesses.
MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
MemoryAccess * getLiveOnEntryDef() const
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Class that has the common methods + fields of memory uses/defs.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
PreservedAnalyses run(Function &F, AnalysisManager< Function > &AM)
Run the pass over the function.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
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...
PointerIntPair - This class implements a pair of a pointer and small integer.
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Encapsulates PredicateInfo, including all data associated with memory accesses.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserve()
Mark an analysis as preserved.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
SmallPtrSetIterator< PtrType > const_iterator
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
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 push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
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.
static IntegerType * getInt8Ty(LLVMContext &C)
static 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.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
std::pair< iterator, bool > insert(const ValueT &V)
iterator find(const_arg_type_t< ValueT > V)
bool erase(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
An opaque object representing a hash code.
const ParentTy * getParent() const
self_iterator getIterator()
A range adaptor for a pair of iterators.
friend const_iterator begin(StringRef path, Style style)
Get begin iterator over path.
friend const_iterator end(StringRef path)
Get end iterator over path.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
bool match(Val *V, const Pattern &P)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
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...
Constant * getConstantValueForLoad(Constant *SrcVal, unsigned Offset, Type *LoadTy, const DataLayout &DL)
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...
Constant * getConstantMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, Type *LoadTy, const DataLayout &DL)
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...
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
std::vector< ExecutorSymbolDef > LookupResult
NodeAddr< DefNode * > Def
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Value * simplifyGEPInst(Type *SrcTy, Value *Ptr, ArrayRef< Value * > Indices, GEPNoWrapFlags NW, const SimplifyQuery &Q)
Given operands for a GetElementPtrInst, fold the result or return null.
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,...
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
auto successors(const MachineBasicBlock *BB)
SDValue getStoredValue(SDValue Op)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
mapped_iterator< ItTy, FuncTy > map_iterator(ItTy I, FuncTy F)
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
Value * simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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.
auto reverse(ContainerTy &&C)
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool wouldInstructionBeTriviallyDead(const Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used.
void patchReplacementInstruction(Instruction *I, Value *Repl)
Patch the replacement so that it is not more restrictive than the value being replaced.
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
Value * simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
DWARFExpression::Operation Op
OutputIt copy(R &&Range, OutputIt Out)
iterator_range< df_iterator< T > > depth_first(const T &G)
bool all_equal(std::initializer_list< T > Values)
Returns true if all Values in the initializer lists are equal or the list.
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
Value * simplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, const SimplifyQuery &Q)
Given operands for a SelectInst, fold the result or return null.
iterator_range< def_chain_iterator< T, true > > optimized_def_chain(T MA)
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.
PointerIntPair< Value *, 1, bool > Def
bool operator<(const ValueDFS &Other) const
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
static unsigned getHashValue(const ExactEqualsExpression &E)
static unsigned getHashValue(const Expression *E)
static const Expression * getTombstoneKey()
static bool isEqual(const Expression *LHS, const Expression *RHS)
static const Expression * getEmptyKey()
static bool isEqual(const ExactEqualsExpression &LHS, const Expression *RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
ExactEqualsExpression(const Expression &E)
hash_code getComputedHash() const
bool operator==(const Expression &Other) const
SimplifyQuery getWithInstruction(const Instruction *I) const