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;
551 ExpressionToPhiOfOps;
600 enum MemoryPhiState { MPS_Invalid, MPS_TOP, MPS_Equivalent, MPS_Unique };
603 enum InstCycleState { ICS_Unknown, ICS_CycleFree, ICS_Cycle };
608 ExpressionClassMap ExpressionToClass;
660 :
F(
F), DT(DT), TLI(TLI), AA(AA), MSSA(MSSA), AC(AC),
DL(
DL),
662 SQ(
DL, TLI, DT, AC, nullptr,
false,
676 : Expr(Expr), ExtraDep(ExtraDep), PredDep(PredDep) {}
677 ExprResult(
const ExprResult &) =
delete;
678 ExprResult(ExprResult &&
Other)
680 Other.Expr =
nullptr;
681 Other.ExtraDep =
nullptr;
682 Other.PredDep =
nullptr;
684 ExprResult &operator=(
const ExprResult &
Other) =
delete;
685 ExprResult &operator=(ExprResult &&
Other) =
delete;
687 ~ExprResult() {
assert(!ExtraDep &&
"unhandled ExtraDep"); }
689 operator bool()
const {
return Expr; }
691 static ExprResult
none() {
return {
nullptr,
nullptr,
nullptr}; }
692 static ExprResult some(
const Expression *Expr,
Value *ExtraDep =
nullptr) {
693 return {Expr, ExtraDep,
nullptr};
695 static ExprResult some(
const Expression *Expr,
697 return {Expr,
nullptr, PredDep};
701 return {Expr, ExtraDep, PredDep};
712 using ValPair = std::pair<Value *, BasicBlock *>;
716 bool &OriginalOpsConstant)
const;
729 createAggregateValueExpression(
Instruction *)
const;
733 CongruenceClass *createCongruenceClass(
Value *Leader,
const Expression *
E) {
734 auto *result =
new CongruenceClass(NextCongruenceNum++, Leader,
E);
735 CongruenceClasses.emplace_back(result);
740 auto *
CC = createCongruenceClass(
nullptr,
nullptr);
741 CC->setMemoryLeader(MA);
745 CongruenceClass *ensureLeaderOfMemoryClass(
MemoryAccess *MA) {
746 auto *
CC = getMemoryClass(MA);
747 if (
CC->getMemoryLeader() != MA)
748 CC = createMemoryClass(MA);
752 CongruenceClass *createSingletonCongruenceClass(
Value *Member) {
753 CongruenceClass *CClass = createCongruenceClass(Member,
nullptr);
754 CClass->insert(Member);
755 ValueToClass[
Member] = CClass;
759 void initializeCongruenceClasses(
Function &
F);
777 ExprResult performSymbolicEvaluation(
Instruction *,
784 ExprResult performSymbolicCallEvaluation(
Instruction *)
const;
790 ExprResult performSymbolicCmpEvaluation(
Instruction *)
const;
791 ExprResult performSymbolicPredicateInfoEvaluation(
IntrinsicInst *)
const;
796 CongruenceClass *getClassForExpression(
const Expression *
E)
const;
799 CongruenceClass *, CongruenceClass *);
801 CongruenceClass *, CongruenceClass *);
802 Value *getNextValueLeader(CongruenceClass *)
const;
803 const MemoryAccess *getNextMemoryLeader(CongruenceClass *)
const;
805 CongruenceClass *getMemoryClass(
const MemoryAccess *MA)
const;
810 unsigned int getRank(
const Value *)
const;
811 bool shouldSwapOperands(
const Value *,
const Value *)
const;
812 bool shouldSwapOperandsForIntrinsic(
const Value *,
const Value *,
818 Value *findConditionEquivalence(
Value *)
const;
822 void convertClassToDFSOrdered(
const CongruenceClass &,
826 void convertClassToLoadsAndStores(
const CongruenceClass &,
829 bool eliminateInstructions(
Function &);
837 template <
typename Map,
typename KeyType>
838 void touchAndErase(Map &,
const KeyType &);
839 void markUsersTouched(
Value *);
843 void markValueLeaderChangeTouched(CongruenceClass *
CC);
844 void markMemoryLeaderChangeTouched(CongruenceClass *
CC);
851 void iterateTouchedInstructions();
854 void cleanupTables();
855 std::pair<unsigned, unsigned> assignDFSNumbers(
BasicBlock *,
unsigned);
856 void updateProcessedCount(
const Value *V);
857 void verifyMemoryCongruency()
const;
858 void verifyIterationSettled(
Function &
F);
859 void verifyStoreExpressions()
const;
866 template <
class T,
class Range>
T *getMinDFSOfRange(
const Range &)
const;
868 unsigned InstrToDFSNum(
const Value *V)
const {
869 assert(isa<Instruction>(V) &&
"This should not be used for MemoryAccesses");
870 return InstrDFS.
lookup(V);
874 return MemoryToDFSNum(MA);
877 Value *InstrFromDFSNum(
unsigned DFSNum) {
return DFSToInstr[DFSNum]; }
882 unsigned MemoryToDFSNum(
const Value *MA)
const {
883 assert(isa<MemoryAccess>(MA) &&
884 "This should not be used with instructions");
885 return isa<MemoryUseOrDef>(MA)
886 ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst())
895 int64_t StartingVNCounter = 0;
902 if (!isa<LoadExpression>(
RHS) && !isa<StoreExpression>(
RHS))
904 return LHS.MemoryExpression::equals(
RHS);
915 if (
const auto *S = dyn_cast<StoreExpression>(&
Other))
947 if (
auto *
I = dyn_cast<Instruction>(V)) {
948 auto *Parent =
I->getParent();
951 Parent = TempToBlock.
lookup(V);
952 assert(Parent &&
"Every fake instruction should have a block");
956 auto *MP = dyn_cast<MemoryPhi>(V);
957 assert(MP &&
"Should have been an instruction or a MemoryPhi");
958 return MP->getBlock();
964void NewGVN::deleteExpression(
const Expression *
E)
const {
965 assert(isa<BasicExpression>(
E));
966 auto *BE = cast<BasicExpression>(
E);
973 if (
auto *II = dyn_cast<IntrinsicInst>(V))
974 if (II->getIntrinsicID() == Intrinsic::ssa_copy)
975 return II->getOperand(0);
986 return CO && isa<PHINode>(CO);
993 llvm::sort(Ops, [&](
const ValPair &P1,
const ValPair &P2) {
994 return BlockInstRange.
lookup(P1.second).first <
995 BlockInstRange.
lookup(P2.second).first;
1003 return isa<Constant>(V) || isa<Argument>(V);
1015 bool &OriginalOpsConstant)
const {
1016 unsigned NumOps = PHIOperands.
size();
1017 auto *
E =
new (ExpressionAllocator)
PHIExpression(NumOps, PHIBlock);
1019 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1020 E->setType(PHIOperands.
begin()->first->getType());
1021 E->setOpcode(Instruction::PHI);
1025 auto *BB =
P.second;
1026 if (
auto *PHIOp = dyn_cast<PHINode>(
I))
1029 if (!ReachableEdges.
count({BB, PHIBlock}))
1032 if (ValueToClass.
lookup(
P.first) == TOPClass)
1034 OriginalOpsConstant = OriginalOpsConstant && isa<Constant>(
P.first);
1035 HasBackedge = HasBackedge || isBackedge(BB, PHIBlock);
1036 return lookupOperandLeader(
P.first) !=
I;
1038 std::transform(Filtered.begin(), Filtered.end(),
op_inserter(
E),
1039 [&](
const ValPair &
P) ->
Value * {
1040 return lookupOperandLeader(
P.first);
1048 bool AllConstant =
true;
1049 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I))
1050 E->setType(
GEP->getSourceElementType());
1052 E->setType(
I->getType());
1053 E->setOpcode(
I->getOpcode());
1054 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1059 auto Operand = lookupOperandLeader(O);
1060 AllConstant = AllConstant && isa<Constant>(Operand);
1067const Expression *NewGVN::createBinaryExpression(
unsigned Opcode,
Type *
T,
1076 E->setOpcode(Opcode);
1077 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1083 if (shouldSwapOperands(Arg1, Arg2))
1086 E->op_push_back(lookupOperandLeader(Arg1));
1087 E->op_push_back(lookupOperandLeader(Arg2));
1090 if (
auto Simplified = checkExprResults(
E,
I, V)) {
1091 addAdditionalUsers(Simplified,
I);
1103 return ExprResult::none();
1105 if (
auto *
C = dyn_cast<Constant>(V)) {
1108 <<
" constant " << *
C <<
"\n");
1109 NumGVNOpsSimplified++;
1110 assert(isa<BasicExpression>(
E) &&
1111 "We should always have had a basic expression here");
1112 deleteExpression(
E);
1113 return ExprResult::some(createConstantExpression(
C));
1114 }
else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
1117 <<
" variable " << *V <<
"\n");
1118 deleteExpression(
E);
1119 return ExprResult::some(createVariableExpression(V));
1122 CongruenceClass *
CC = ValueToClass.
lookup(V);
1124 if (
CC->getLeader() &&
CC->getLeader() !=
I) {
1125 return ExprResult::some(createVariableOrConstant(
CC->getLeader()), V);
1127 if (
CC->getDefiningExpr()) {
1130 <<
" expression " << *
CC->getDefiningExpr() <<
"\n");
1131 NumGVNOpsSimplified++;
1132 deleteExpression(
E);
1133 return ExprResult::some(
CC->getDefiningExpr(), V);
1137 return ExprResult::none();
1143NewGVN::ExprResult NewGVN::createExpression(
Instruction *
I)
const {
1149 bool AllConstant = setBasicExpressionInfo(
I,
E);
1151 if (
I->isCommutative()) {
1156 assert(
I->getNumOperands() == 2 &&
"Unsupported commutative instruction!");
1157 if (shouldSwapOperands(
E->getOperand(0),
E->getOperand(1)))
1158 E->swapOperands(0, 1);
1161 if (
auto *CI = dyn_cast<CmpInst>(
I)) {
1165 if (shouldSwapOperands(
E->getOperand(0),
E->getOperand(1))) {
1166 E->swapOperands(0, 1);
1169 E->setOpcode((CI->getOpcode() << 8) | Predicate);
1171 assert(
I->getOperand(0)->getType() ==
I->getOperand(1)->getType() &&
1172 "Wrong types on cmp instruction");
1173 assert((
E->getOperand(0)->getType() ==
I->getOperand(0)->getType() &&
1174 E->getOperand(1)->getType() ==
I->getOperand(1)->getType()));
1177 if (
auto Simplified = checkExprResults(
E,
I, V))
1179 }
else if (isa<SelectInst>(
I)) {
1180 if (isa<Constant>(
E->getOperand(0)) ||
1181 E->getOperand(1) ==
E->getOperand(2)) {
1182 assert(
E->getOperand(1)->getType() ==
I->getOperand(1)->getType() &&
1183 E->getOperand(2)->getType() ==
I->getOperand(2)->getType());
1185 E->getOperand(2), Q);
1186 if (
auto Simplified = checkExprResults(
E,
I, V))
1189 }
else if (
I->isBinaryOp()) {
1192 if (
auto Simplified = checkExprResults(
E,
I, V))
1194 }
else if (
auto *CI = dyn_cast<CastInst>(
I)) {
1197 if (
auto Simplified = checkExprResults(
E,
I, V))
1199 }
else if (
auto *GEPI = dyn_cast<GetElementPtrInst>(
I)) {
1201 ArrayRef(std::next(
E->op_begin()),
E->op_end()),
1202 GEPI->isInBounds(), Q);
1203 if (
auto Simplified = checkExprResults(
E,
I, V))
1205 }
else if (AllConstant) {
1214 for (
Value *Arg :
E->operands())
1215 C.emplace_back(cast<Constant>(Arg));
1218 if (
auto Simplified = checkExprResults(
E,
I, V))
1221 return ExprResult::some(
E);
1225NewGVN::createAggregateValueExpression(
Instruction *
I)
const {
1226 if (
auto *II = dyn_cast<InsertValueInst>(
I)) {
1227 auto *
E =
new (ExpressionAllocator)
1229 setBasicExpressionInfo(
I,
E);
1230 E->allocateIntOperands(ExpressionAllocator);
1233 }
else if (
auto *EI = dyn_cast<ExtractValueInst>(
I)) {
1234 auto *
E =
new (ExpressionAllocator)
1236 setBasicExpressionInfo(EI,
E);
1237 E->allocateIntOperands(ExpressionAllocator);
1247 return SingletonDeadExpression;
1252 E->setOpcode(
V->getValueID());
1257 if (
auto *
C = dyn_cast<Constant>(V))
1258 return createConstantExpression(
C);
1259 return createVariableExpression(V);
1264 E->setOpcode(
C->getValueID());
1270 E->setOpcode(
I->getOpcode());
1279 setBasicExpressionInfo(CI,
E);
1285 if (shouldSwapOperands(
E->getOperand(0),
E->getOperand(1)))
1286 E->swapOperands(0, 1);
1292bool NewGVN::someEquivalentDominates(
const Instruction *Inst,
1294 auto *
CC = ValueToClass.
lookup(Inst);
1315 if (DT->
dominates(cast<Instruction>(
CC->getLeader()), U))
1317 if (
CC->getNextLeader().first &&
1318 DT->
dominates(cast<Instruction>(
CC->getNextLeader().first), U))
1321 return Member !=
CC->getLeader() &&
1322 DT->
dominates(cast<Instruction>(Member), U);
1328Value *NewGVN::lookupOperandLeader(
Value *V)
const {
1329 CongruenceClass *
CC = ValueToClass.
lookup(V);
1336 return CC->getStoredValue() ?
CC->getStoredValue() :
CC->getLeader();
1343 auto *
CC = getMemoryClass(MA);
1345 "Every MemoryAccess should be mapped to a congruence class with a "
1346 "representative memory access");
1347 return CC->getMemoryLeader();
1353bool NewGVN::isMemoryAccessTOP(
const MemoryAccess *MA)
const {
1354 return getMemoryClass(MA) == TOPClass;
1361 new (ExpressionAllocator)
LoadExpression(1, LI, lookupMemoryLeader(MA));
1362 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1363 E->setType(LoadType);
1367 E->op_push_back(PointerOp);
1377 auto *StoredValueLeader = lookupOperandLeader(
SI->getValueOperand());
1378 auto *
E =
new (ExpressionAllocator)
1380 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1381 E->setType(
SI->getValueOperand()->getType());
1385 E->op_push_back(lookupOperandLeader(
SI->getPointerOperand()));
1396 auto *
SI = cast<StoreInst>(
I);
1397 auto *StoreAccess = getMemoryAccess(SI);
1399 const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess();
1403 StoreRHS = lookupMemoryLeader(StoreRHS);
1404 if (StoreRHS != StoreAccess->getDefiningAccess())
1405 addMemoryUsers(StoreRHS, StoreAccess);
1407 if (StoreRHS == StoreAccess)
1410 if (
SI->isSimple()) {
1414 const auto *LastStore = createStoreExpression(SI, StoreRHS);
1415 const auto *LastCC = ExpressionToClass.lookup(LastStore);
1421 if (LastCC && LastCC->getStoredValue() == LastStore->getStoredValue())
1427 if (
auto *LI = dyn_cast<LoadInst>(LastStore->getStoredValue()))
1429 LastStore->getOperand(0)) &&
1430 (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) ==
1433 deleteExpression(LastStore);
1439 return createStoreExpression(SI, StoreAccess);
1445NewGVN::performSymbolicLoadCoercion(
Type *LoadType,
Value *LoadPtr,
1449 if (
auto *DepSI = dyn_cast<StoreInst>(DepInst)) {
1453 if (LI->
isAtomic() > DepSI->isAtomic() ||
1454 LoadType == DepSI->getValueOperand()->getType())
1458 if (
auto *
C = dyn_cast<Constant>(
1459 lookupOperandLeader(DepSI->getValueOperand()))) {
1462 <<
" to constant " << *Res <<
"\n");
1463 return createConstantExpression(Res);
1467 }
else if (
auto *DepLI = dyn_cast<LoadInst>(DepInst)) {
1469 if (LI->
isAtomic() > DepLI->isAtomic())
1474 if (
auto *
C = dyn_cast<Constant>(lookupOperandLeader(DepLI)))
1475 if (
auto *PossibleConstant =
1478 <<
" to constant " << *PossibleConstant <<
"\n");
1479 return createConstantExpression(PossibleConstant);
1482 }
else if (
auto *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1485 if (
auto *PossibleConstant =
1488 <<
" to constant " << *PossibleConstant <<
"\n");
1489 return createConstantExpression(PossibleConstant);
1496 if (LoadPtr != lookupOperandLeader(DepInst) &&
1503 if (isa<AllocaInst>(DepInst)) {
1508 else if (
auto *II = dyn_cast<IntrinsicInst>(DepInst)) {
1509 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1511 }
else if (
auto *InitVal =
1513 return createConstantExpression(InitVal);
1519 auto *LI = cast<LoadInst>(
I);
1528 if (isa<UndefValue>(LoadAddressLeader))
1535 if (
auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
1544 if (
const auto *CoercionResult =
1545 performSymbolicLoadCoercion(LI->
getType(), LoadAddressLeader, LI,
1546 DefiningInst, DefiningAccess))
1547 return CoercionResult;
1551 const auto *
LE = createLoadExpression(LI->
getType(), LoadAddressLeader, LI,
1555 if (
LE->getMemoryLeader() != DefiningAccess)
1556 addMemoryUsers(
LE->getMemoryLeader(), OriginalAccess);
1561NewGVN::performSymbolicPredicateInfoEvaluation(
IntrinsicInst *
I)
const {
1562 auto *PI = PredInfo->getPredicateInfoFor(
I);
1564 return ExprResult::none();
1566 LLVM_DEBUG(
dbgs() <<
"Found predicate info from instruction !\n");
1568 const std::optional<PredicateConstraint> &Constraint = PI->getConstraint();
1570 return ExprResult::none();
1573 Value *CmpOp0 =
I->getOperand(0);
1574 Value *CmpOp1 = Constraint->OtherOp;
1576 Value *FirstOp = lookupOperandLeader(CmpOp0);
1577 Value *SecondOp = lookupOperandLeader(CmpOp1);
1578 Value *AdditionallyUsedValue = CmpOp0;
1581 if (shouldSwapOperandsForIntrinsic(FirstOp, SecondOp,
I)) {
1584 AdditionallyUsedValue = CmpOp1;
1588 return ExprResult::some(createVariableOrConstant(FirstOp),
1589 AdditionallyUsedValue, PI);
1593 !cast<ConstantFP>(FirstOp)->
isZero())
1594 return ExprResult::some(createConstantExpression(cast<Constant>(FirstOp)),
1595 AdditionallyUsedValue, PI);
1597 return ExprResult::none();
1601NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(
Instruction *
I)
const {
1602 auto *CI = cast<CallInst>(
I);
1603 if (
auto *II = dyn_cast<IntrinsicInst>(
I)) {
1605 if (
auto *ReturnedValue = II->getReturnedArgOperand()) {
1606 if (II->getIntrinsicID() == Intrinsic::ssa_copy)
1607 if (
auto Res = performSymbolicPredicateInfoEvaluation(II))
1609 return ExprResult::some(createVariableOrConstant(ReturnedValue));
1621 return ExprResult::none();
1627 return ExprResult::none();
1630 return ExprResult::some(
1631 createCallExpression(CI, TOPClass->getMemoryLeader()));
1635 return ExprResult::some(createCallExpression(CI, DefiningAccess));
1637 return ExprResult::some(
1638 createCallExpression(CI, TOPClass->getMemoryLeader()));
1640 return ExprResult::none();
1644CongruenceClass *NewGVN::getMemoryClass(
const MemoryAccess *MA)
const {
1646 assert(Result &&
"Should have found memory class");
1653 CongruenceClass *NewClass) {
1655 "Every MemoryAccess should be getting mapped to a non-null class");
1659 <<
" with current MemoryAccess leader ");
1663 bool Changed =
false;
1665 if (LookupResult != MemoryAccessToClass.
end()) {
1667 if (OldClass != NewClass) {
1669 if (
auto *MP = dyn_cast<MemoryPhi>(
From)) {
1670 OldClass->memory_erase(MP);
1671 NewClass->memory_insert(MP);
1673 if (OldClass->getMemoryLeader() ==
From) {
1674 if (OldClass->definesNoMemory()) {
1675 OldClass->setMemoryLeader(
nullptr);
1677 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
1679 << OldClass->getID() <<
" to "
1680 << *OldClass->getMemoryLeader()
1681 <<
" due to removal of a memory member " << *
From
1683 markMemoryLeaderChangeTouched(OldClass);
1706 auto ICS = InstCycleState.
lookup(
I);
1707 if (ICS == ICS_Unknown) {
1709 auto &
SCC = SCCFinder.getComponentFor(
I);
1711 if (
SCC.size() == 1)
1712 InstCycleState.
insert({
I, ICS_CycleFree});
1717 ICS = AllPhis ? ICS_CycleFree : ICS_Cycle;
1718 for (
const auto *Member : SCC)
1719 if (
auto *MemberPhi = dyn_cast<PHINode>(Member))
1720 InstCycleState.
insert({MemberPhi, ICS});
1723 if (ICS == ICS_Cycle)
1734 bool HasBackedge =
false;
1739 bool OriginalOpsConstant =
true;
1740 auto *
E = cast<PHIExpression>(createPHIExpression(
1741 PHIOps,
I, PHIBlock, HasBackedge, OriginalOpsConstant));
1745 bool HasUndef =
false, HasPoison =
false;
1747 if (isa<PoisonValue>(Arg)) {
1751 if (isa<UndefValue>(Arg)) {
1758 if (Filtered.empty()) {
1763 dbgs() <<
"PHI Node " << *
I
1764 <<
" has no non-undef arguments, valuing it as undef\n");
1769 dbgs() <<
"PHI Node " << *
I
1770 <<
" has no non-poison arguments, valuing it as poison\n");
1774 LLVM_DEBUG(
dbgs() <<
"No arguments of PHI node " << *
I <<
" are live\n");
1775 deleteExpression(
E);
1776 return createDeadExpression();
1778 Value *AllSameValue = *(Filtered.begin());
1796 if (HasPoison || HasUndef) {
1802 if (HasBackedge && !OriginalOpsConstant &&
1803 !isa<UndefValue>(AllSameValue) && !isCycleFree(
I))
1807 if (
auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
1808 if (!someEquivalentDominates(AllSameInst,
I))
1814 if (isa<Instruction>(AllSameValue) &&
1815 InstrToDFSNum(AllSameValue) > InstrToDFSNum(
I))
1817 NumGVNPhisAllSame++;
1818 LLVM_DEBUG(
dbgs() <<
"Simplified PHI node " << *
I <<
" to " << *AllSameValue
1820 deleteExpression(
E);
1821 return createVariableOrConstant(AllSameValue);
1827NewGVN::performSymbolicAggrValueEvaluation(
Instruction *
I)
const {
1828 if (
auto *EI = dyn_cast<ExtractValueInst>(
I)) {
1829 auto *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
1830 if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0)
1834 return createBinaryExpression(WO->getBinaryOp(), EI->getType(),
1835 WO->getLHS(), WO->getRHS(),
I);
1838 return createAggregateValueExpression(
I);
1841NewGVN::ExprResult NewGVN::performSymbolicCmpEvaluation(
Instruction *
I)
const {
1842 assert(isa<CmpInst>(
I) &&
"Expected a cmp instruction.");
1844 auto *CI = cast<CmpInst>(
I);
1847 auto Op0 = lookupOperandLeader(CI->
getOperand(0));
1848 auto Op1 = lookupOperandLeader(CI->
getOperand(1));
1849 auto OurPredicate = CI->getPredicate();
1850 if (shouldSwapOperands(Op0, Op1)) {
1852 OurPredicate = CI->getSwappedPredicate();
1859 auto *CmpPI = PredInfo->getPredicateInfoFor(
I);
1860 if (isa_and_nonnull<PredicateAssume>(CmpPI))
1861 return ExprResult::some(
1866 if (CI->isTrueWhenEqual())
1867 return ExprResult::some(
1869 else if (CI->isFalseWhenEqual())
1870 return ExprResult::some(
1900 auto *PI = PredInfo->getPredicateInfoFor(
Op);
1901 if (
const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
1902 if (PI == LastPredInfo)
1907 if (!DT->
dominates(PBranch->To,
I->getParent()))
1914 auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
1917 auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
1918 auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
1919 auto BranchPredicate = BranchCond->getPredicate();
1920 if (shouldSwapOperands(BranchOp0, BranchOp1)) {
1922 BranchPredicate = BranchCond->getSwappedPredicate();
1924 if (BranchOp0 == Op0 && BranchOp1 == Op1) {
1925 if (PBranch->TrueEdge) {
1930 return ExprResult::some(
1937 return ExprResult::some(
1944 if (BranchPredicate == OurPredicate) {
1946 return ExprResult::some(
1949 }
else if (BranchPredicate ==
1952 return ExprResult::some(
1961 return createExpression(
I);
1973 switch (
I->getOpcode()) {
1974 case Instruction::ExtractValue:
1975 case Instruction::InsertValue:
1976 E = performSymbolicAggrValueEvaluation(
I);
1978 case Instruction::PHI: {
1980 auto *PN = cast<PHINode>(
I);
1981 for (
unsigned i = 0; i < PN->getNumOperands(); ++i)
1982 Ops.
push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)});
1985 E = performSymbolicPHIEvaluation(Ops,
I, getBlockForValue(
I));
1987 case Instruction::Call:
1988 return performSymbolicCallEvaluation(
I);
1990 case Instruction::Store:
1991 E = performSymbolicStoreEvaluation(
I);
1993 case Instruction::Load:
1994 E = performSymbolicLoadEvaluation(
I);
1996 case Instruction::BitCast:
1997 case Instruction::AddrSpaceCast:
1998 case Instruction::Freeze:
1999 return createExpression(
I);
2001 case Instruction::ICmp:
2002 case Instruction::FCmp:
2003 return performSymbolicCmpEvaluation(
I);
2005 case Instruction::FNeg:
2006 case Instruction::Add:
2007 case Instruction::FAdd:
2008 case Instruction::Sub:
2009 case Instruction::FSub:
2010 case Instruction::Mul:
2011 case Instruction::FMul:
2012 case Instruction::UDiv:
2013 case Instruction::SDiv:
2014 case Instruction::FDiv:
2015 case Instruction::URem:
2016 case Instruction::SRem:
2017 case Instruction::FRem:
2018 case Instruction::Shl:
2019 case Instruction::LShr:
2020 case Instruction::AShr:
2021 case Instruction::And:
2022 case Instruction::Or:
2023 case Instruction::Xor:
2024 case Instruction::Trunc:
2025 case Instruction::ZExt:
2026 case Instruction::SExt:
2027 case Instruction::FPToUI:
2028 case Instruction::FPToSI:
2029 case Instruction::UIToFP:
2030 case Instruction::SIToFP:
2031 case Instruction::FPTrunc:
2032 case Instruction::FPExt:
2033 case Instruction::PtrToInt:
2034 case Instruction::IntToPtr:
2035 case Instruction::Select:
2036 case Instruction::ExtractElement:
2037 case Instruction::InsertElement:
2038 case Instruction::GetElementPtr:
2039 return createExpression(
I);
2041 case Instruction::ShuffleVector:
2043 return ExprResult::none();
2045 return ExprResult::none();
2047 return ExprResult::some(
E);
2052template <
typename Map,
typename KeyType>
2053void NewGVN::touchAndErase(Map &M,
const KeyType &Key) {
2054 const auto Result =
M.find_as(Key);
2055 if (Result !=
M.end()) {
2056 for (
const typename Map::mapped_type::value_type Mapped :
Result->second)
2057 TouchedInstructions.
set(InstrToDFSNum(Mapped));
2064 if (isa<Instruction>(To))
2068void NewGVN::addAdditionalUsers(ExprResult &Res,
Instruction *
User)
const {
2069 if (Res.ExtraDep && Res.ExtraDep !=
User)
2070 addAdditionalUsers(Res.ExtraDep,
User);
2071 Res.ExtraDep =
nullptr;
2074 if (
const auto *PBranch = dyn_cast<PredicateBranch>(Res.PredDep))
2075 PredicateToUsers[PBranch->Condition].
insert(
User);
2076 else if (
const auto *PAssume = dyn_cast<PredicateAssume>(Res.PredDep))
2077 PredicateToUsers[PAssume->Condition].
insert(
User);
2079 Res.PredDep =
nullptr;
2082void NewGVN::markUsersTouched(
Value *V) {
2084 for (
auto *
User :
V->users()) {
2085 assert(isa<Instruction>(
User) &&
"Use of value not within an instruction?");
2086 TouchedInstructions.
set(InstrToDFSNum(
User));
2088 touchAndErase(AdditionalUsers, V);
2092 LLVM_DEBUG(
dbgs() <<
"Adding memory user " << *U <<
" to " << *To <<
"\n");
2093 MemoryToUsers[To].
insert(U);
2096void NewGVN::markMemoryDefTouched(
const MemoryAccess *MA) {
2097 TouchedInstructions.
set(MemoryToDFSNum(MA));
2100void NewGVN::markMemoryUsersTouched(
const MemoryAccess *MA) {
2101 if (isa<MemoryUse>(MA))
2103 for (
const auto *U : MA->
users())
2104 TouchedInstructions.
set(MemoryToDFSNum(U));
2105 touchAndErase(MemoryToUsers, MA);
2109void NewGVN::markPredicateUsersTouched(
Instruction *
I) {
2110 touchAndErase(PredicateToUsers,
I);
2114void NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *
CC) {
2115 for (
const auto *M :
CC->memory())
2116 markMemoryDefTouched(M);
2121void NewGVN::markValueLeaderChangeTouched(CongruenceClass *
CC) {
2122 for (
auto *M : *
CC) {
2123 if (
auto *
I = dyn_cast<Instruction>(M))
2124 TouchedInstructions.
set(InstrToDFSNum(
I));
2131template <
class T,
class Range>
2132T *NewGVN::getMinDFSOfRange(
const Range &R)
const {
2133 std::pair<T *, unsigned> MinDFS = {
nullptr, ~0
U};
2134 for (
const auto X : R) {
2135 auto DFSNum = InstrToDFSNum(
X);
2136 if (DFSNum < MinDFS.second)
2137 MinDFS = {
X, DFSNum};
2139 return MinDFS.first;
2145const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *
CC)
const {
2149 assert(!
CC->definesNoMemory() &&
"Can't get next leader if there is none");
2150 if (
CC->getStoreCount() > 0) {
2151 if (
auto *
NL = dyn_cast_or_null<StoreInst>(
CC->getNextLeader().first))
2152 return getMemoryAccess(
NL);
2155 *
CC, [&](
const Value *V) {
return isa<StoreInst>(V); }));
2156 return getMemoryAccess(cast<StoreInst>(V));
2162 if (
CC->memory_size() == 1)
2163 return *
CC->memory_begin();
2164 return getMinDFSOfRange<const MemoryPhi>(
CC->memory());
2170Value *NewGVN::getNextValueLeader(CongruenceClass *
CC)
const {
2175 if (
CC->size() == 1 ||
CC == TOPClass) {
2176 return *(
CC->begin());
2177 }
else if (
CC->getNextLeader().first) {
2178 ++NumGVNAvoidedSortedLeaderChanges;
2179 return CC->getNextLeader().first;
2181 ++NumGVNSortedLeaderChanges;
2185 return getMinDFSOfRange<Value>(*
CC);
2198void NewGVN::moveMemoryToNewCongruenceClass(
Instruction *
I,
2200 CongruenceClass *OldClass,
2201 CongruenceClass *NewClass) {
2204 assert((!InstMA || !OldClass->getMemoryLeader() ||
2205 OldClass->getLeader() !=
I ||
2206 MemoryAccessToClass.
lookup(OldClass->getMemoryLeader()) ==
2207 MemoryAccessToClass.
lookup(InstMA)) &&
2208 "Representative MemoryAccess mismatch");
2210 if (!NewClass->getMemoryLeader()) {
2212 assert(NewClass->size() == 1 ||
2213 (isa<StoreInst>(
I) && NewClass->getStoreCount() == 1));
2214 NewClass->setMemoryLeader(InstMA);
2217 << NewClass->getID()
2218 <<
" due to new memory instruction becoming leader\n");
2219 markMemoryLeaderChangeTouched(NewClass);
2221 setMemoryClass(InstMA, NewClass);
2223 if (OldClass->getMemoryLeader() == InstMA) {
2224 if (!OldClass->definesNoMemory()) {
2225 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
2227 << OldClass->getID() <<
" to "
2228 << *OldClass->getMemoryLeader()
2229 <<
" due to removal of old leader " << *InstMA <<
"\n");
2230 markMemoryLeaderChangeTouched(OldClass);
2232 OldClass->setMemoryLeader(
nullptr);
2239 CongruenceClass *OldClass,
2240 CongruenceClass *NewClass) {
2241 if (
I == OldClass->getNextLeader().first)
2242 OldClass->resetNextLeader();
2245 NewClass->insert(
I);
2247 if (NewClass->getLeader() !=
I)
2248 NewClass->addPossibleNextLeader({
I, InstrToDFSNum(
I)});
2250 if (
auto *SI = dyn_cast<StoreInst>(
I)) {
2251 OldClass->decStoreCount();
2259 if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) {
2262 if (
auto *SE = dyn_cast<StoreExpression>(
E)) {
2263 NewClass->setStoredValue(SE->getStoredValue());
2264 markValueLeaderChangeTouched(NewClass);
2267 << NewClass->getID() <<
" from "
2268 << *NewClass->getLeader() <<
" to " << *SI
2269 <<
" because store joined class\n");
2272 NewClass->setLeader(SI);
2276 NewClass->incStoreCount();
2282 auto *InstMA = dyn_cast_or_null<MemoryDef>(getMemoryAccess(
I));
2284 moveMemoryToNewCongruenceClass(
I, InstMA, OldClass, NewClass);
2285 ValueToClass[
I] = NewClass;
2287 if (OldClass->empty() && OldClass != TOPClass) {
2288 if (OldClass->getDefiningExpr()) {
2289 LLVM_DEBUG(
dbgs() <<
"Erasing expression " << *OldClass->getDefiningExpr()
2290 <<
" from table\n");
2293 auto Iter = ExpressionToClass.find_as(
2295 if (Iter != ExpressionToClass.end())
2296 ExpressionToClass.erase(Iter);
2297#ifdef EXPENSIVE_CHECKS
2299 (*OldClass->getDefiningExpr() != *
E || ExpressionToClass.lookup(
E)) &&
2300 "We erased the expression we just inserted, which should not happen");
2303 }
else if (OldClass->getLeader() ==
I) {
2308 << OldClass->getID() <<
"\n");
2309 ++NumGVNLeaderChanges;
2314 if (OldClass->getStoreCount() == 0) {
2315 if (OldClass->getStoredValue())
2316 OldClass->setStoredValue(
nullptr);
2318 OldClass->setLeader(getNextValueLeader(OldClass));
2319 OldClass->resetNextLeader();
2320 markValueLeaderChangeTouched(OldClass);
2326void NewGVN::markPhiOfOpsChanged(
const Expression *
E) {
2327 touchAndErase(ExpressionToPhiOfOps,
E);
2335 CongruenceClass *IClass = ValueToClass.
lookup(
I);
2336 assert(IClass &&
"Should have found a IClass");
2338 assert(!IClass->isDead() &&
"Found a dead class");
2340 CongruenceClass *EClass =
nullptr;
2341 if (
const auto *VE = dyn_cast<VariableExpression>(
E)) {
2342 EClass = ValueToClass.
lookup(VE->getVariableValue());
2343 }
else if (isa<DeadExpression>(
E)) {
2347 auto lookupResult = ExpressionToClass.insert({
E,
nullptr});
2350 if (lookupResult.second) {
2351 CongruenceClass *NewClass = createCongruenceClass(
nullptr,
E);
2352 auto place = lookupResult.first;
2353 place->second = NewClass;
2356 if (
const auto *CE = dyn_cast<ConstantExpression>(
E)) {
2357 NewClass->setLeader(
CE->getConstantValue());
2358 }
else if (
const auto *SE = dyn_cast<StoreExpression>(
E)) {
2360 NewClass->setLeader(SI);
2361 NewClass->setStoredValue(SE->getStoredValue());
2365 NewClass->setLeader(
I);
2367 assert(!isa<VariableExpression>(
E) &&
2368 "VariableExpression should have been handled already");
2372 <<
" using expression " << *
E <<
" at "
2373 << NewClass->getID() <<
" and leader "
2374 << *(NewClass->getLeader()));
2375 if (NewClass->getStoredValue())
2377 << *(NewClass->getStoredValue()));
2380 EClass = lookupResult.first->second;
2381 if (isa<ConstantExpression>(
E))
2382 assert((isa<Constant>(EClass->getLeader()) ||
2383 (EClass->getStoredValue() &&
2384 isa<Constant>(EClass->getStoredValue()))) &&
2385 "Any class with a constant expression should have a "
2388 assert(EClass &&
"Somehow don't have an eclass");
2390 assert(!EClass->isDead() &&
"We accidentally looked up a dead class");
2393 bool ClassChanged = IClass != EClass;
2394 bool LeaderChanged = LeaderChanges.
erase(
I);
2395 if (ClassChanged || LeaderChanged) {
2396 LLVM_DEBUG(
dbgs() <<
"New class " << EClass->getID() <<
" for expression "
2399 moveValueToNewCongruenceClass(
I,
E, IClass, EClass);
2400 markPhiOfOpsChanged(
E);
2403 markUsersTouched(
I);
2405 markMemoryUsersTouched(MA);
2406 if (
auto *CI = dyn_cast<CmpInst>(
I))
2407 markPredicateUsersTouched(CI);
2413 if (ClassChanged && isa<StoreInst>(
I)) {
2414 auto *OldE = ValueToExpression.
lookup(
I);
2417 if (OldE && isa<StoreExpression>(OldE) && *
E != *OldE) {
2421 if (Iter != ExpressionToClass.end())
2422 ExpressionToClass.erase(Iter);
2425 ValueToExpression[
I] =
E;
2432 if (ReachableEdges.
insert({From, To}).second) {
2434 if (ReachableBlocks.
insert(To).second) {
2436 <<
" marked reachable\n");
2437 const auto &InstRange = BlockInstRange.
lookup(To);
2438 TouchedInstructions.
set(InstRange.first, InstRange.second);
2441 <<
" was reachable, but new edge {"
2443 <<
"} to it found\n");
2450 TouchedInstructions.
set(InstrToDFSNum(MemPhi));
2455 for (
auto InstNum : RevisitOnReachabilityChange[To])
2456 TouchedInstructions.
set(InstNum);
2465 return isa<Constant>(Result) ?
Result :
nullptr;
2474 Value *CondEvaluated = findConditionEquivalence(
Cond);
2475 if (!CondEvaluated) {
2476 if (
auto *
I = dyn_cast<Instruction>(
Cond)) {
2478 auto Res = performSymbolicEvaluation(
I, Visited);
2479 if (
const auto *CE = dyn_cast_or_null<ConstantExpression>(Res.Expr)) {
2480 CondEvaluated =
CE->getConstantValue();
2481 addAdditionalUsers(Res,
I);
2485 Res.ExtraDep =
nullptr;
2487 }
else if (isa<ConstantInt>(
Cond)) {
2488 CondEvaluated =
Cond;
2492 if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
2495 <<
" evaluated to true\n");
2496 updateReachableEdge(
B, TrueSucc);
2497 }
else if (CI->
isZero()) {
2499 <<
" evaluated to false\n");
2500 updateReachableEdge(
B, FalseSucc);
2503 updateReachableEdge(
B, TrueSucc);
2504 updateReachableEdge(
B, FalseSucc);
2506 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
2510 Value *SwitchCond =
SI->getCondition();
2511 Value *CondEvaluated = findConditionEquivalence(SwitchCond);
2513 if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
2514 auto *CondVal = cast<ConstantInt>(CondEvaluated);
2516 auto Case = *
SI->findCaseValue(CondVal);
2517 if (Case.getCaseSuccessor() ==
SI->getDefaultDest()) {
2521 updateReachableEdge(
B,
SI->getDefaultDest());
2525 BasicBlock *TargetBlock = Case.getCaseSuccessor();
2526 updateReachableEdge(
B, TargetBlock);
2528 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i != e; ++i) {
2530 updateReachableEdge(
B, TargetBlock);
2538 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);
2604 if (OISIt != OpSafeForPHIOfOps.
end())
2605 return OISIt->second;
2610 OpSafeForPHIOfOps.
insert({
I,
true});
2614 if (isa<PHINode>(
I) && getBlockForValue(
I) == PHIBlock) {
2615 OpSafeForPHIOfOps.
insert({
I,
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);
2635 if (OISIt != OpSafeForPHIOfOps.
end()) {
2636 if (!OISIt->second) {
2637 OpSafeForPHIOfOps.
insert({
I,
false});
2647 OpSafeForPHIOfOps.
insert({
V,
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();
3300 iterateTouchedInstructions();
3303 for (
const auto &KV : ValueToClass) {
3304 if (
auto *
I = dyn_cast<Instruction>(KV.first))
3306 if (InstrToDFSNum(
I) == 0)
3310 auto *BeforeCC = &BeforeIteration.
find(KV.first)->second;
3311 auto *AfterCC = KV.second;
3314 if (!EqualClasses.
count({BeforeCC, AfterCC})) {
3315 assert(BeforeCC->isEquivalentTo(AfterCC) &&
3316 "Value number changed after main loop completed!");
3317 EqualClasses.
insert({BeforeCC, AfterCC});
3328void NewGVN::verifyStoreExpressions()
const {
3333 std::pair<
const Value *,
3334 std::tuple<const Value *, const CongruenceClass *, Value *>>>
3336 for (
const auto &KV : ExpressionToClass) {
3337 if (
auto *SE = dyn_cast<StoreExpression>(KV.first)) {
3339 auto Res = StoreExpressionSet.insert(
3340 {SE->getOperand(0), std::make_tuple(SE->getMemoryLeader(), KV.second,
3341 SE->getStoredValue())});
3342 bool Okay = Res.second;
3347 Okay = (std::get<1>(Res.first->second) == KV.second) &&
3348 (lookupOperandLeader(std::get<2>(Res.first->second)) ==
3349 lookupOperandLeader(SE->getStoredValue()));
3350 assert(Okay &&
"Stored expression conflict exists in expression table");
3351 auto *ValueExpr = ValueToExpression.
lookup(SE->getStoreInst());
3352 assert(ValueExpr && ValueExpr->equals(*SE) &&
3353 "StoreExpression in ExpressionToClass is not latest "
3354 "StoreExpression for value");
3363void NewGVN::iterateTouchedInstructions() {
3366 int FirstInstr = TouchedInstructions.
find_first();
3368 if (FirstInstr == -1)
3370 const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
3371 while (TouchedInstructions.
any()) {
3377 for (
unsigned InstrNum : TouchedInstructions.
set_bits()) {
3381 if (InstrNum == 0) {
3382 TouchedInstructions.
reset(InstrNum);
3386 Value *
V = InstrFromDFSNum(InstrNum);
3387 const BasicBlock *CurrBlock = getBlockForValue(V);
3390 if (CurrBlock != LastBlock) {
3391 LastBlock = CurrBlock;
3392 bool BlockReachable = ReachableBlocks.
count(CurrBlock);
3393 const auto &CurrInstRange = BlockInstRange.
lookup(CurrBlock);
3396 if (!BlockReachable) {
3397 TouchedInstructions.
reset(CurrInstRange.first, CurrInstRange.second);
3400 <<
" because it is unreachable\n");
3403 updateProcessedCount(CurrBlock);
3407 TouchedInstructions.
reset(InstrNum);
3409 if (
auto *MP = dyn_cast<MemoryPhi>(V)) {
3411 valueNumberMemoryPhi(MP);
3412 }
else if (
auto *
I = dyn_cast<Instruction>(V)) {
3413 valueNumberInstruction(
I);
3417 updateProcessedCount(V);
3420 NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations);
3424bool NewGVN::runGVN() {
3427 bool Changed =
false;
3428 NumFuncArgs =
F.arg_size();
3430 SingletonDeadExpression =
new (ExpressionAllocator)
DeadExpression();
3434 unsigned ICount = 1;
3446 unsigned Counter = 0;
3447 for (
auto &
B : RPOT) {
3449 assert(
Node &&
"RPO and Dominator tree should have same reachability");
3450 RPOOrdering[
Node] = ++Counter;
3453 for (
auto &
B : RPOT) {
3455 if (
Node->getNumChildren() > 1)
3457 return RPOOrdering[
A] < RPOOrdering[
B];
3464 const auto &BlockRange = assignDFSNumbers(
B, ICount);
3465 BlockInstRange.
insert({
B, BlockRange});
3466 ICount += BlockRange.second - BlockRange.first;
3468 initializeCongruenceClasses(
F);
3470 TouchedInstructions.
resize(ICount);
3474 ExpressionToClass.reserve(ICount);
3477 const auto &InstRange = BlockInstRange.
lookup(&
F.getEntryBlock());
3478 TouchedInstructions.
set(InstRange.first, InstRange.second);
3480 <<
" marked reachable\n");
3481 ReachableBlocks.
insert(&
F.getEntryBlock());
3483 iterateTouchedInstructions();
3484 verifyMemoryCongruency();
3485 verifyIterationSettled(
F);
3486 verifyStoreExpressions();
3488 Changed |= eliminateInstructions(
F);
3491 for (
Instruction *ToErase : InstructionsToErase) {
3492 if (!ToErase->use_empty())
3495 assert(ToErase->getParent() &&
3496 "BB containing ToErase deleted unexpectedly!");
3497 ToErase->eraseFromParent();
3499 Changed |= !InstructionsToErase.empty();
3502 auto UnreachableBlockPred = [&](
const BasicBlock &BB) {
3503 return !ReachableBlocks.
count(&BB);
3508 <<
" is unreachable\n");
3509 deleteInstructionsInBlock(&BB);
3567 return std::tie(DFSIn, DFSOut,
LocalNum, Def, U) <
3578void NewGVN::convertClassToDFSOrdered(
3587 assert(BB &&
"Should have figured out a basic block for value");
3595 if (
auto *SI = dyn_cast<StoreInst>(
D)) {
3596 auto Leader = lookupOperandLeader(SI->getValueOperand());
3598 VDDef.
Def.setPointer(Leader);
3600 VDDef.
Def.setPointer(
SI->getValueOperand());
3601 VDDef.
Def.setInt(
true);
3604 VDDef.
Def.setPointer(
D);
3607 "The dense set member should always be an instruction");
3612 if (
auto *PN = RealToTemp.
lookup(Def)) {
3614 dyn_cast_or_null<PHIExpression>(ValueToExpression.
lookup(Def));
3616 VDDef.
Def.setInt(
false);
3617 VDDef.
Def.setPointer(PN);
3623 unsigned int UseCount = 0;
3625 for (
auto &U :
Def->uses()) {
3626 if (
auto *
I = dyn_cast<Instruction>(
U.getUser())) {
3628 if (InstructionsToErase.count(
I))
3633 if (
auto *
P = dyn_cast<PHINode>(
I)) {
3634 IBlock =
P->getIncomingBlock(U);
3639 IBlock = getBlockForValue(
I);
3645 if (!ReachableBlocks.
contains(IBlock))
3661 ProbablyDead.
insert(Def);
3663 UseCounts[
Def] = UseCount;
3669void NewGVN::convertClassToLoadsAndStores(
3670 const CongruenceClass &
Dense,
3673 if (!isa<LoadInst>(
D) && !isa<StoreInst>(
D))
3681 VD.
Def.setPointer(
D);
3684 if (
auto *
I = dyn_cast<Instruction>(
D))
3695 I->replaceAllUsesWith(Repl);
3698void NewGVN::deleteInstructionsInBlock(
BasicBlock *BB) {
3700 ++NumGVNBlocksDeleted;
3704 auto StartPoint = BB->
rbegin();
3712 if (isa<LandingPadInst>(Inst))
3717 ++NumGVNInstrDeleted;
3727void NewGVN::markInstructionForDeletion(
Instruction *
I) {
3729 InstructionsToErase.insert(
I);
3737 markInstructionForDeletion(
I);
3744class ValueDFSStack {
3746 Value *back()
const {
return ValueStack.back(); }
3747 std::pair<int, int> dfs_back()
const {
return DFSStack.back(); }
3749 void push_back(
Value *V,
int DFSIn,
int DFSOut) {
3750 ValueStack.emplace_back(V);
3751 DFSStack.emplace_back(DFSIn, DFSOut);
3754 bool empty()
const {
return DFSStack.empty(); }
3756 bool isInScope(
int DFSIn,
int DFSOut)
const {
3759 return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
3762 void popUntilDFSScope(
int DFSIn,
int DFSOut) {
3765 assert(ValueStack.size() == DFSStack.size() &&
3766 "Mismatch between ValueStack and DFSStack");
3768 !DFSStack.empty() &&
3769 !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
3770 DFSStack.pop_back();
3771 ValueStack.pop_back();
3783CongruenceClass *NewGVN::getClassForExpression(
const Expression *
E)
const {
3784 if (
auto *VE = dyn_cast<VariableExpression>(
E))
3785 return ValueToClass.lookup(VE->getVariableValue());
3786 else if (isa<DeadExpression>(
E))
3788 return ExpressionToClass.lookup(
E);
3797 if (
auto *CE = dyn_cast<ConstantExpression>(
E))
3798 return CE->getConstantValue();
3799 if (
auto *VE = dyn_cast<VariableExpression>(
E)) {
3800 auto *
V = VE->getVariableValue();
3802 return VE->getVariableValue();
3805 auto *
CC = getClassForExpression(
E);
3809 return CC->getLeader();
3811 for (
auto *Member : *
CC) {
3812 auto *MemberInst = dyn_cast<Instruction>(Member);
3813 if (MemberInst == OrigInst)
3818 if (DT->
dominates(getBlockForValue(MemberInst), BB))
3824bool NewGVN::eliminateInstructions(
Function &
F) {
3848 bool AnythingReplaced =
false;
3857 for (
auto &Operand :
PHI->incoming_values())
3858 if (!ReachableEdges.
count({PHI->getIncomingBlock(Operand), BB})) {
3862 <<
" with poison due to it being unreachable\n");
3876 for (
auto &KV : ReachableEdges)
3877 ReachablePredCount[KV.getEnd()]++;
3878 for (
auto &BBPair : RevisitOnReachabilityChange) {
3879 for (
auto InstNum : BBPair.second) {
3880 auto *Inst = InstrFromDFSNum(InstNum);
3881 auto *
PHI = dyn_cast<PHINode>(Inst);
3885 auto *BB = BBPair.first;
3886 if (ReachablePredCount.
lookup(BB) !=
PHI->getNumIncomingValues())
3887 ReplaceUnreachablePHIArgs(
PHI, BB);
3893 for (
auto *
CC :
reverse(CongruenceClasses)) {
3900 if (
CC->isDead() ||
CC->empty())
3903 if (
CC == TOPClass) {
3904 for (
auto *M : *
CC) {
3905 auto *VTE = ValueToExpression.
lookup(M);
3906 if (VTE && isa<DeadExpression>(VTE))
3907 markInstructionForDeletion(cast<Instruction>(M));
3908 assert((!ReachableBlocks.
count(cast<Instruction>(M)->getParent()) ||
3909 InstructionsToErase.count(cast<Instruction>(M))) &&
3910 "Everything in TOP should be unreachable or dead at this "
3916 assert(
CC->getLeader() &&
"We should have had a leader");
3922 CC->getStoredValue() ?
CC->getStoredValue() :
CC->getLeader();
3925 for (
auto *M : *
CC) {
3928 if (Member == Leader || !isa<Instruction>(Member) ||
3929 Member->getType()->isVoidTy()) {
3930 MembersLeft.
insert(Member);
3933 LLVM_DEBUG(
dbgs() <<
"Found replacement " << *(Leader) <<
" for "
3934 << *Member <<
"\n");
3935 auto *
I = cast<Instruction>(Member);
3936 assert(Leader !=
I &&
"About to accidentally remove our leader");
3937 replaceInstruction(
I, Leader);
3938 AnythingReplaced =
true;
3940 CC->swap(MembersLeft);
3943 if (
CC->size() != 1 || RealToTemp.
count(Leader)) {
3948 ValueDFSStack EliminationStack;
3952 convertClassToDFSOrdered(*
CC, DFSOrderedSet, UseCounts, ProbablyDead);
3956 for (
auto &VD : DFSOrderedSet) {
3957 int MemberDFSIn = VD.
DFSIn;
3958 int MemberDFSOut = VD.
DFSOut;
3960 bool FromStore = VD.
Def.getInt();
3963 if (Def &&
Def->getType()->isVoidTy())
3965 auto *DefInst = dyn_cast_or_null<Instruction>(Def);
3966 if (DefInst && AllTempInstructions.
count(DefInst)) {
3967 auto *PN = cast<PHINode>(DefInst);
3972 AllTempInstructions.
erase(PN);
3973 auto *DefBlock = getBlockForValue(Def);
3977 PN->insertBefore(&DefBlock->front());
3979 NumGVNPHIOfOpsEliminations++;
3982 if (EliminationStack.empty()) {
3986 << EliminationStack.dfs_back().first <<
","
3987 << EliminationStack.dfs_back().second <<
")\n");
3990 LLVM_DEBUG(
dbgs() <<
"Current DFS numbers are (" << MemberDFSIn <<
","
3991 << MemberDFSOut <<
")\n");
4005 bool ShouldPush =
Def && EliminationStack.empty();
4007 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
4009 if (OutOfScope || ShouldPush) {
4011 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4012 bool ShouldPush =
Def && EliminationStack.empty();
4014 EliminationStack.push_back(Def, MemberDFSIn, MemberDFSOut);
4033 auto *DefI = dyn_cast<Instruction>(Def);
4034 if (!EliminationStack.empty() && DefI && !FromStore) {
4035 Value *DominatingLeader = EliminationStack.back();
4036 if (DominatingLeader != Def) {
4039 if (!
match(DefI, m_Intrinsic<Intrinsic::ssa_copy>()))
4042 markInstructionForDeletion(DefI);
4050 assert(isa<Instruction>(
U->get()) &&
4051 "Current def should have been an instruction");
4052 assert(isa<Instruction>(
U->getUser()) &&
4053 "Current user should have been an instruction");
4059 Instruction *InstUse = cast<Instruction>(
U->getUser());
4060 if (InstructionsToErase.count(InstUse)) {
4061 auto &UseCount = UseCounts[
U->get()];
4062 if (--UseCount == 0) {
4063 ProbablyDead.
insert(cast<Instruction>(
U->get()));
4069 if (EliminationStack.empty())
4072 Value *DominatingLeader = EliminationStack.back();
4074 auto *II = dyn_cast<IntrinsicInst>(DominatingLeader);
4075 bool isSSACopy = II && II->getIntrinsicID() == Intrinsic::ssa_copy;
4077 DominatingLeader = II->getOperand(0);
4080 if (
U->get() == DominatingLeader)
4083 <<
"Found replacement " << *DominatingLeader <<
" for "
4084 << *
U->get() <<
" in " << *(
U->getUser()) <<
"\n");
4089 auto *ReplacedInst = cast<Instruction>(
U->get());
4090 auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
4091 if (!PI || DominatingLeader != PI->OriginalOp)
4093 U->set(DominatingLeader);
4096 auto &LeaderUseCount = UseCounts[DominatingLeader];
4098 if (LeaderUseCount == 0 && isa<Instruction>(DominatingLeader))
4099 ProbablyDead.
erase(cast<Instruction>(DominatingLeader));
4103 auto It = UseCounts.
find(II);
4104 if (It != UseCounts.
end()) {
4105 unsigned &IIUseCount = It->second;
4106 if (--IIUseCount == 0)
4111 AnythingReplaced =
true;
4118 for (
auto *
I : ProbablyDead)
4120 markInstructionForDeletion(
I);
4124 for (
auto *Member : *
CC)
4125 if (!isa<Instruction>(Member) ||
4126 !InstructionsToErase.count(cast<Instruction>(Member)))
4127 MembersLeft.
insert(Member);
4128 CC->swap(MembersLeft);
4131 if (
CC->getStoreCount() > 0) {
4132 convertClassToLoadsAndStores(*
CC, PossibleDeadStores);
4134 ValueDFSStack EliminationStack;
4135 for (
auto &VD : PossibleDeadStores) {
4136 int MemberDFSIn = VD.
DFSIn;
4137 int MemberDFSOut = VD.
DFSOut;
4139 if (EliminationStack.empty() ||
4140 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) {
4142 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4143 if (EliminationStack.empty()) {
4144 EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
4149 if (isa<LoadInst>(Member))
4151 assert(!EliminationStack.empty());
4152 Instruction *Leader = cast<Instruction>(EliminationStack.back());
4157 <<
" that is dominated by " << *Leader <<
"\n");
4158 markInstructionForDeletion(Member);
4164 return AnythingReplaced;
4172unsigned int NewGVN::getRank(
const Value *V)
const {
4178 if (isa<ConstantExpr>(V))
4180 if (isa<PoisonValue>(V))
4182 if (isa<UndefValue>(V))
4184 if (isa<Constant>(V))
4186 if (
auto *
A = dyn_cast<Argument>(V))
4187 return 4 +
A->getArgNo();
4191 unsigned Result = InstrToDFSNum(V);
4193 return 5 + NumFuncArgs +
Result;
4200bool NewGVN::shouldSwapOperands(
const Value *
A,
const Value *
B)
const {
4204 return std::make_pair(getRank(
A),
A) > std::make_pair(getRank(
B),
B);
4207bool NewGVN::shouldSwapOperandsForIntrinsic(
const Value *
A,
const Value *
B,
4210 if (shouldSwapOperands(
A,
B)) {
4211 if (LookupResult == IntrinsicInstPred.
end())
4218 if (LookupResult != IntrinsicInstPred.
end()) {
4220 if (SeenPredicate) {
4221 if (SeenPredicate ==
B)
4240 NewGVN(
F, &DT, &AC, &TLI, &AA, &MSSA,
F.getParent()->getDataLayout())
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Unify divergent function exit nodes
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...
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...
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)
This defines the Use class.
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 void setCounterValue(unsigned ID, int64_t Count)
static bool isCounterSet(unsigned ID)
static bool shouldExecute(unsigned CounterName)
static int64_t getCounterValue(unsigned ID)
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
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
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.
const BasicBlock * getParent() const
const Function * getFunction() const
Return the function this instruction belongs to.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
A wrapper class for inspecting calls to intrinsic functions.
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.
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...
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
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)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
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.
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< ExecutorAddr > 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.
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.
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.
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)
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
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...
@ 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)
Value * simplifyGEPInst(Type *SrcTy, Value *Ptr, ArrayRef< Value * > Indices, bool InBounds, const SimplifyQuery &Q)
Given operands for a GetElementPtrInst, fold the result or return null.
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(Instruction *I) const