130#define DEBUG_TYPE "newgvn"
132STATISTIC(NumGVNInstrDeleted,
"Number of instructions deleted");
133STATISTIC(NumGVNBlocksDeleted,
"Number of blocks deleted");
134STATISTIC(NumGVNOpsSimplified,
"Number of Expressions simplified");
135STATISTIC(NumGVNPhisAllSame,
"Number of PHIs whos arguments are all the same");
137 "Maximum Number of iterations it took to converge GVN");
138STATISTIC(NumGVNLeaderChanges,
"Number of leader changes");
139STATISTIC(NumGVNSortedLeaderChanges,
"Number of sorted leader changes");
141 "Number of avoided sorted leader changes");
142STATISTIC(NumGVNDeadStores,
"Number of redundant/dead stores eliminated");
143STATISTIC(NumGVNPHIOfOpsCreated,
"Number of PHI of ops created");
145 "Number of things eliminated using PHI of ops");
147 "Controls which instructions are value numbered");
149 "Controls which instructions we create phi of ops for");
166namespace GVNExpression {
190 TarjanSCC() : Components(1) {}
193 if (Root.lookup(Start) == 0)
198 unsigned ComponentID = ValueToComponent.lookup(V);
201 "Asking for a component for a value we never processed");
202 return Components[ComponentID];
209 unsigned int OurDFS = DFSNum;
210 for (
const auto &Op :
I->operands()) {
211 if (
auto *InstOp = dyn_cast<Instruction>(Op)) {
212 if (Root.lookup(Op) == 0)
214 if (!InComponent.count(Op))
215 Root[
I] = std::min(Root.lookup(
I), Root.lookup(Op));
222 if (Root.lookup(
I) == OurDFS) {
223 unsigned ComponentID = Components.size();
224 Components.resize(Components.size() + 1);
228 InComponent.insert(
I);
229 ValueToComponent[
I] = ComponentID;
231 while (!
Stack.empty() && Root.lookup(
Stack.back()) >= OurDFS) {
235 InComponent.insert(Member);
236 ValueToComponent[
Member] = ComponentID;
245 unsigned int DFSNum = 1;
295class CongruenceClass {
297 using MemberType =
Value;
302 explicit CongruenceClass(
unsigned ID) :
ID(
ID) {}
304 :
ID(
ID), RepLeader(Leader), DefiningExpr(
E) {}
306 unsigned getID()
const {
return ID; }
310 bool isDead()
const {
313 return empty() && memory_empty();
317 Value *getLeader()
const {
return RepLeader; }
318 void setLeader(
Value *Leader) { RepLeader = Leader; }
319 const std::pair<Value *, unsigned int> &getNextLeader()
const {
322 void resetNextLeader() { NextLeader = {
nullptr, ~0}; }
323 void addPossibleNextLeader(std::pair<Value *, unsigned int> LeaderPair) {
324 if (LeaderPair.second < NextLeader.second)
325 NextLeader = LeaderPair;
329 void setStoredValue(
Value *Leader) { RepStoredValue = Leader; }
330 const MemoryAccess *getMemoryLeader()
const {
return RepMemoryAccess; }
331 void setMemoryLeader(
const MemoryAccess *Leader) { RepMemoryAccess = Leader; }
334 const Expression *getDefiningExpr()
const {
return DefiningExpr; }
337 bool empty()
const {
return Members.empty(); }
338 unsigned size()
const {
return Members.size(); }
341 void insert(MemberType *M) { Members.insert(M); }
342 void erase(MemberType *M) { Members.erase(M); }
346 bool memory_empty()
const {
return MemoryMembers.empty(); }
347 unsigned memory_size()
const {
return MemoryMembers.size(); }
349 return MemoryMembers.begin();
352 return MemoryMembers.end();
355 return make_range(memory_begin(), memory_end());
358 void memory_insert(
const MemoryMemberType *M) { MemoryMembers.insert(M); }
359 void memory_erase(
const MemoryMemberType *M) { MemoryMembers.erase(M); }
362 unsigned getStoreCount()
const {
return StoreCount; }
363 void incStoreCount() { ++StoreCount; }
364 void decStoreCount() {
365 assert(StoreCount != 0 &&
"Store count went negative");
370 bool definesNoMemory()
const {
return StoreCount == 0 && memory_empty(); }
374 bool isEquivalentTo(
const CongruenceClass *
Other)
const {
380 if (std::tie(StoreCount, RepLeader, RepStoredValue, RepMemoryAccess) !=
382 Other->RepMemoryAccess))
384 if (DefiningExpr !=
Other->DefiningExpr)
385 if (!DefiningExpr || !
Other->DefiningExpr ||
386 *DefiningExpr != *
Other->DefiningExpr)
389 if (Members.size() !=
Other->Members.size())
399 Value *RepLeader =
nullptr;
403 std::pair<Value *, unsigned int> NextLeader = {
nullptr, ~0
U};
406 Value *RepStoredValue =
nullptr;
421 MemoryMemberSet MemoryMembers;
440 return E.exactlyEquals(
Other);
446 auto Val =
static_cast<uintptr_t
>(-1);
447 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
448 return reinterpret_cast<const Expression *
>(Val);
452 auto Val =
static_cast<uintptr_t
>(~1U);
453 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
454 return reinterpret_cast<const Expression *
>(Val);
458 return E->getComputedHash();
462 return E.getComputedHash();
466 if (
RHS == getTombstoneKey() ||
RHS == getEmptyKey())
474 if (
LHS == getTombstoneKey() ||
RHS == getTombstoneKey() ||
475 LHS == getEmptyKey() ||
RHS == getEmptyKey())
481 if (
LHS->getComputedHash() !=
RHS->getComputedHash())
500 std::unique_ptr<PredicateInfo> PredInfo;
506 mutable TarjanSCC SCCFinder;
510 unsigned int NumFuncArgs = 0;
521 CongruenceClass *TOPClass =
nullptr;
522 std::vector<CongruenceClass *> CongruenceClasses;
523 unsigned NextCongruenceNum = 0;
554 ExpressionToPhiOfOps;
603 enum MemoryPhiState { MPS_Invalid, MPS_TOP, MPS_Equivalent, MPS_Unique };
606 enum InstCycleState { ICS_Unknown, ICS_CycleFree, ICS_Cycle };
611 ExpressionClassMap ExpressionToClass;
663 :
F(
F), DT(DT), TLI(TLI), AA(AA), MSSA(MSSA), AC(AC),
DL(
DL),
665 SQ(
DL, TLI, DT, AC, nullptr,
false,
679 : Expr(Expr), ExtraDep(ExtraDep), PredDep(PredDep) {}
680 ExprResult(
const ExprResult &) =
delete;
681 ExprResult(ExprResult &&
Other)
683 Other.Expr =
nullptr;
684 Other.ExtraDep =
nullptr;
685 Other.PredDep =
nullptr;
687 ExprResult &operator=(
const ExprResult &
Other) =
delete;
688 ExprResult &operator=(ExprResult &&
Other) =
delete;
690 ~ExprResult() {
assert(!ExtraDep &&
"unhandled ExtraDep"); }
692 operator bool()
const {
return Expr; }
694 static ExprResult
none() {
return {
nullptr,
nullptr,
nullptr}; }
695 static ExprResult some(
const Expression *Expr,
Value *ExtraDep =
nullptr) {
696 return {Expr, ExtraDep,
nullptr};
698 static ExprResult some(
const Expression *Expr,
700 return {Expr,
nullptr, PredDep};
704 return {Expr, ExtraDep, PredDep};
715 using ValPair = std::pair<Value *, BasicBlock *>;
719 bool &OriginalOpsConstant)
const;
732 createAggregateValueExpression(
Instruction *)
const;
736 CongruenceClass *createCongruenceClass(
Value *Leader,
const Expression *
E) {
737 auto *result =
new CongruenceClass(NextCongruenceNum++, Leader,
E);
738 CongruenceClasses.emplace_back(result);
743 auto *
CC = createCongruenceClass(
nullptr,
nullptr);
744 CC->setMemoryLeader(MA);
748 CongruenceClass *ensureLeaderOfMemoryClass(
MemoryAccess *MA) {
749 auto *
CC = getMemoryClass(MA);
750 if (
CC->getMemoryLeader() != MA)
751 CC = createMemoryClass(MA);
755 CongruenceClass *createSingletonCongruenceClass(
Value *Member) {
756 CongruenceClass *CClass = createCongruenceClass(Member,
nullptr);
757 CClass->insert(Member);
758 ValueToClass[
Member] = CClass;
762 void initializeCongruenceClasses(
Function &
F);
780 ExprResult performSymbolicEvaluation(
Value *,
787 ExprResult performSymbolicCallEvaluation(
Instruction *)
const;
793 ExprResult performSymbolicCmpEvaluation(
Instruction *)
const;
794 ExprResult performSymbolicPredicateInfoEvaluation(
IntrinsicInst *)
const;
799 CongruenceClass *getClassForExpression(
const Expression *
E)
const;
802 CongruenceClass *, CongruenceClass *);
804 CongruenceClass *, CongruenceClass *);
805 Value *getNextValueLeader(CongruenceClass *)
const;
806 const MemoryAccess *getNextMemoryLeader(CongruenceClass *)
const;
808 CongruenceClass *getMemoryClass(
const MemoryAccess *MA)
const;
813 unsigned int getRank(
const Value *)
const;
814 bool shouldSwapOperands(
const Value *,
const Value *)
const;
815 bool shouldSwapOperandsForIntrinsic(
const Value *,
const Value *,
821 Value *findConditionEquivalence(
Value *)
const;
825 void convertClassToDFSOrdered(
const CongruenceClass &,
829 void convertClassToLoadsAndStores(
const CongruenceClass &,
832 bool eliminateInstructions(
Function &);
840 template <
typename Map,
typename KeyType>
841 void touchAndErase(Map &,
const KeyType &);
842 void markUsersTouched(
Value *);
846 void markValueLeaderChangeTouched(CongruenceClass *
CC);
847 void markMemoryLeaderChangeTouched(CongruenceClass *
CC);
854 void iterateTouchedInstructions();
857 void cleanupTables();
858 std::pair<unsigned, unsigned> assignDFSNumbers(
BasicBlock *,
unsigned);
859 void updateProcessedCount(
const Value *V);
860 void verifyMemoryCongruency()
const;
861 void verifyIterationSettled(
Function &
F);
862 void verifyStoreExpressions()
const;
869 template <
class T,
class Range>
T *getMinDFSOfRange(
const Range &)
const;
871 unsigned InstrToDFSNum(
const Value *V)
const {
872 assert(isa<Instruction>(V) &&
"This should not be used for MemoryAccesses");
873 return InstrDFS.
lookup(V);
877 return MemoryToDFSNum(MA);
880 Value *InstrFromDFSNum(
unsigned DFSNum) {
return DFSToInstr[DFSNum]; }
885 unsigned MemoryToDFSNum(
const Value *MA)
const {
886 assert(isa<MemoryAccess>(MA) &&
887 "This should not be used with instructions");
888 return isa<MemoryUseOrDef>(MA)
889 ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst())
898 int64_t StartingVNCounter = 0;
905 if (!isa<LoadExpression>(
RHS) && !isa<StoreExpression>(
RHS))
907 return LHS.MemoryExpression::equals(
RHS);
918 if (
const auto *S = dyn_cast<StoreExpression>(&
Other))
950 if (
auto *
I = dyn_cast<Instruction>(V)) {
951 auto *Parent =
I->getParent();
954 Parent = TempToBlock.
lookup(V);
955 assert(Parent &&
"Every fake instruction should have a block");
959 auto *MP = dyn_cast<MemoryPhi>(V);
960 assert(MP &&
"Should have been an instruction or a MemoryPhi");
961 return MP->getBlock();
967void NewGVN::deleteExpression(
const Expression *
E)
const {
968 assert(isa<BasicExpression>(
E));
969 auto *BE = cast<BasicExpression>(
E);
976 if (
auto *II = dyn_cast<IntrinsicInst>(V))
977 if (II->getIntrinsicID() == Intrinsic::ssa_copy)
978 return II->getOperand(0);
989 return CO && isa<PHINode>(CO);
996 llvm::sort(Ops, [&](
const ValPair &P1,
const ValPair &P2) {
997 return BlockInstRange.
lookup(P1.second).first <
998 BlockInstRange.
lookup(P2.second).first;
1006 return isa<Constant>(V) || isa<Argument>(V);
1018 bool &OriginalOpsConstant)
const {
1019 unsigned NumOps = PHIOperands.
size();
1020 auto *
E =
new (ExpressionAllocator)
PHIExpression(NumOps, PHIBlock);
1022 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1023 E->setType(PHIOperands.
begin()->first->getType());
1024 E->setOpcode(Instruction::PHI);
1028 auto *BB =
P.second;
1029 if (
auto *PHIOp = dyn_cast<PHINode>(
I))
1032 if (!ReachableEdges.
count({BB, PHIBlock}))
1035 if (ValueToClass.
lookup(
P.first) == TOPClass)
1037 OriginalOpsConstant = OriginalOpsConstant && isa<Constant>(
P.first);
1038 HasBackedge = HasBackedge || isBackedge(BB, PHIBlock);
1039 return lookupOperandLeader(
P.first) !=
I;
1041 std::transform(Filtered.begin(), Filtered.end(),
op_inserter(
E),
1042 [&](
const ValPair &
P) ->
Value * {
1043 return lookupOperandLeader(
P.first);
1051 bool AllConstant =
true;
1052 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I))
1053 E->setType(
GEP->getSourceElementType());
1055 E->setType(
I->getType());
1056 E->setOpcode(
I->getOpcode());
1057 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1062 auto Operand = lookupOperandLeader(O);
1063 AllConstant = AllConstant && isa<Constant>(Operand);
1070const Expression *NewGVN::createBinaryExpression(
unsigned Opcode,
Type *
T,
1079 E->setOpcode(Opcode);
1080 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1086 if (shouldSwapOperands(Arg1, Arg2))
1089 E->op_push_back(lookupOperandLeader(Arg1));
1090 E->op_push_back(lookupOperandLeader(Arg2));
1093 if (
auto Simplified = checkExprResults(
E,
I, V)) {
1094 addAdditionalUsers(Simplified,
I);
1106 return ExprResult::none();
1108 if (
auto *
C = dyn_cast<Constant>(V)) {
1111 <<
" constant " << *
C <<
"\n");
1112 NumGVNOpsSimplified++;
1113 assert(isa<BasicExpression>(
E) &&
1114 "We should always have had a basic expression here");
1115 deleteExpression(
E);
1116 return ExprResult::some(createConstantExpression(
C));
1117 }
else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
1120 <<
" variable " << *V <<
"\n");
1121 deleteExpression(
E);
1122 return ExprResult::some(createVariableExpression(V));
1125 CongruenceClass *
CC = ValueToClass.
lookup(V);
1127 if (
CC->getLeader() &&
CC->getLeader() !=
I) {
1128 return ExprResult::some(createVariableOrConstant(
CC->getLeader()), V);
1130 if (
CC->getDefiningExpr()) {
1133 <<
" expression " << *
CC->getDefiningExpr() <<
"\n");
1134 NumGVNOpsSimplified++;
1135 deleteExpression(
E);
1136 return ExprResult::some(
CC->getDefiningExpr(), V);
1140 return ExprResult::none();
1146NewGVN::ExprResult NewGVN::createExpression(
Instruction *
I)
const {
1152 bool AllConstant = setBasicExpressionInfo(
I,
E);
1154 if (
I->isCommutative()) {
1159 assert(
I->getNumOperands() == 2 &&
"Unsupported commutative instruction!");
1160 if (shouldSwapOperands(
E->getOperand(0),
E->getOperand(1)))
1161 E->swapOperands(0, 1);
1164 if (
auto *CI = dyn_cast<CmpInst>(
I)) {
1168 if (shouldSwapOperands(
E->getOperand(0),
E->getOperand(1))) {
1169 E->swapOperands(0, 1);
1172 E->setOpcode((CI->getOpcode() << 8) | Predicate);
1174 assert(
I->getOperand(0)->getType() ==
I->getOperand(1)->getType() &&
1175 "Wrong types on cmp instruction");
1176 assert((
E->getOperand(0)->getType() ==
I->getOperand(0)->getType() &&
1177 E->getOperand(1)->getType() ==
I->getOperand(1)->getType()));
1180 if (
auto Simplified = checkExprResults(
E,
I, V))
1182 }
else if (isa<SelectInst>(
I)) {
1183 if (isa<Constant>(
E->getOperand(0)) ||
1184 E->getOperand(1) ==
E->getOperand(2)) {
1185 assert(
E->getOperand(1)->getType() ==
I->getOperand(1)->getType() &&
1186 E->getOperand(2)->getType() ==
I->getOperand(2)->getType());
1188 E->getOperand(2), Q);
1189 if (
auto Simplified = checkExprResults(
E,
I, V))
1192 }
else if (
I->isBinaryOp()) {
1195 if (
auto Simplified = checkExprResults(
E,
I, V))
1197 }
else if (
auto *CI = dyn_cast<CastInst>(
I)) {
1200 if (
auto Simplified = checkExprResults(
E,
I, V))
1202 }
else if (
auto *GEPI = dyn_cast<GetElementPtrInst>(
I)) {
1204 ArrayRef(std::next(
E->op_begin()),
E->op_end()),
1205 GEPI->isInBounds(), Q);
1206 if (
auto Simplified = checkExprResults(
E,
I, V))
1208 }
else if (AllConstant) {
1218 C.emplace_back(cast<Constant>(
Arg));
1221 if (
auto Simplified = checkExprResults(
E,
I, V))
1224 return ExprResult::some(
E);
1228NewGVN::createAggregateValueExpression(
Instruction *
I)
const {
1229 if (
auto *II = dyn_cast<InsertValueInst>(
I)) {
1230 auto *
E =
new (ExpressionAllocator)
1232 setBasicExpressionInfo(
I,
E);
1233 E->allocateIntOperands(ExpressionAllocator);
1236 }
else if (
auto *EI = dyn_cast<ExtractValueInst>(
I)) {
1237 auto *
E =
new (ExpressionAllocator)
1239 setBasicExpressionInfo(EI,
E);
1240 E->allocateIntOperands(ExpressionAllocator);
1250 return SingletonDeadExpression;
1255 E->setOpcode(
V->getValueID());
1260 if (
auto *
C = dyn_cast<Constant>(V))
1261 return createConstantExpression(
C);
1262 return createVariableExpression(V);
1267 E->setOpcode(
C->getValueID());
1273 E->setOpcode(
I->getOpcode());
1283 setBasicExpressionInfo(CI,
E);
1288bool NewGVN::someEquivalentDominates(
const Instruction *Inst,
1290 auto *
CC = ValueToClass.
lookup(Inst);
1311 if (DT->
dominates(cast<Instruction>(
CC->getLeader()), U))
1313 if (
CC->getNextLeader().first &&
1314 DT->
dominates(cast<Instruction>(
CC->getNextLeader().first), U))
1317 return Member !=
CC->getLeader() &&
1318 DT->
dominates(cast<Instruction>(Member), U);
1324Value *NewGVN::lookupOperandLeader(
Value *V)
const {
1325 CongruenceClass *
CC = ValueToClass.
lookup(V);
1332 return CC->getStoredValue() ?
CC->getStoredValue() :
CC->getLeader();
1339 auto *
CC = getMemoryClass(MA);
1341 "Every MemoryAccess should be mapped to a congruence class with a "
1342 "representative memory access");
1343 return CC->getMemoryLeader();
1349bool NewGVN::isMemoryAccessTOP(
const MemoryAccess *MA)
const {
1350 return getMemoryClass(MA) == TOPClass;
1357 new (ExpressionAllocator)
LoadExpression(1, LI, lookupMemoryLeader(MA));
1358 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1359 E->setType(LoadType);
1363 E->op_push_back(PointerOp);
1373 auto *StoredValueLeader = lookupOperandLeader(
SI->getValueOperand());
1374 auto *
E =
new (ExpressionAllocator)
1376 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1377 E->setType(
SI->getValueOperand()->getType());
1381 E->op_push_back(lookupOperandLeader(
SI->getPointerOperand()));
1392 auto *
SI = cast<StoreInst>(
I);
1393 auto *StoreAccess = getMemoryAccess(SI);
1395 const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess();
1399 StoreRHS = lookupMemoryLeader(StoreRHS);
1400 if (StoreRHS != StoreAccess->getDefiningAccess())
1401 addMemoryUsers(StoreRHS, StoreAccess);
1403 if (StoreRHS == StoreAccess)
1406 if (
SI->isSimple()) {
1410 const auto *LastStore = createStoreExpression(SI, StoreRHS);
1411 const auto *LastCC = ExpressionToClass.lookup(LastStore);
1417 if (LastCC && LastCC->getStoredValue() == LastStore->getStoredValue())
1423 if (
auto *LI = dyn_cast<LoadInst>(LastStore->getStoredValue()))
1425 LastStore->getOperand(0)) &&
1426 (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) ==
1429 deleteExpression(LastStore);
1435 return createStoreExpression(SI, StoreAccess);
1441NewGVN::performSymbolicLoadCoercion(
Type *LoadType,
Value *LoadPtr,
1445 if (
auto *DepSI = dyn_cast<StoreInst>(DepInst)) {
1449 if (LI->
isAtomic() > DepSI->isAtomic() ||
1450 LoadType == DepSI->getValueOperand()->getType())
1454 if (
auto *
C = dyn_cast<Constant>(
1455 lookupOperandLeader(DepSI->getValueOperand()))) {
1459 <<
" to constant " << *Res <<
"\n");
1460 return createConstantExpression(Res);
1464 }
else if (
auto *DepLI = dyn_cast<LoadInst>(DepInst)) {
1466 if (LI->
isAtomic() > DepLI->isAtomic())
1471 if (
auto *
C = dyn_cast<Constant>(lookupOperandLeader(DepLI)))
1472 if (
auto *PossibleConstant =
1475 <<
" to constant " << *PossibleConstant <<
"\n");
1476 return createConstantExpression(PossibleConstant);
1479 }
else if (
auto *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1482 if (
auto *PossibleConstant =
1485 <<
" to constant " << *PossibleConstant <<
"\n");
1486 return createConstantExpression(PossibleConstant);
1493 if (LoadPtr != lookupOperandLeader(DepInst) &&
1500 if (isa<AllocaInst>(DepInst)) {
1505 else if (
auto *II = dyn_cast<IntrinsicInst>(DepInst)) {
1506 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1508 }
else if (
auto *InitVal =
1510 return createConstantExpression(InitVal);
1516 auto *LI = cast<LoadInst>(
I);
1525 if (isa<UndefValue>(LoadAddressLeader))
1532 if (
auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
1541 if (
const auto *CoercionResult =
1542 performSymbolicLoadCoercion(LI->
getType(), LoadAddressLeader, LI,
1543 DefiningInst, DefiningAccess))
1544 return CoercionResult;
1548 const auto *
LE = createLoadExpression(LI->
getType(), LoadAddressLeader, LI,
1552 if (
LE->getMemoryLeader() != DefiningAccess)
1553 addMemoryUsers(
LE->getMemoryLeader(), OriginalAccess);
1558NewGVN::performSymbolicPredicateInfoEvaluation(
IntrinsicInst *
I)
const {
1559 auto *PI = PredInfo->getPredicateInfoFor(
I);
1561 return ExprResult::none();
1563 LLVM_DEBUG(
dbgs() <<
"Found predicate info from instruction !\n");
1565 const std::optional<PredicateConstraint> &Constraint = PI->getConstraint();
1567 return ExprResult::none();
1570 Value *CmpOp0 =
I->getOperand(0);
1571 Value *CmpOp1 = Constraint->OtherOp;
1573 Value *FirstOp = lookupOperandLeader(CmpOp0);
1574 Value *SecondOp = lookupOperandLeader(CmpOp1);
1575 Value *AdditionallyUsedValue = CmpOp0;
1578 if (shouldSwapOperandsForIntrinsic(FirstOp, SecondOp,
I)) {
1581 AdditionallyUsedValue = CmpOp1;
1585 return ExprResult::some(createVariableOrConstant(FirstOp),
1586 AdditionallyUsedValue, PI);
1590 !cast<ConstantFP>(FirstOp)->
isZero())
1591 return ExprResult::some(createConstantExpression(cast<Constant>(FirstOp)),
1592 AdditionallyUsedValue, PI);
1594 return ExprResult::none();
1598NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(
Instruction *
I)
const {
1599 auto *CI = cast<CallInst>(
I);
1600 if (
auto *II = dyn_cast<IntrinsicInst>(
I)) {
1602 if (
auto *ReturnedValue = II->getReturnedArgOperand()) {
1603 if (II->getIntrinsicID() == Intrinsic::ssa_copy)
1604 if (
auto Res = performSymbolicPredicateInfoEvaluation(II))
1606 return ExprResult::some(createVariableOrConstant(ReturnedValue));
1618 return ExprResult::none();
1621 return ExprResult::some(
1622 createCallExpression(CI, TOPClass->getMemoryLeader()));
1626 return ExprResult::some(createCallExpression(CI, DefiningAccess));
1628 return ExprResult::some(
1629 createCallExpression(CI, TOPClass->getMemoryLeader()));
1631 return ExprResult::none();
1635CongruenceClass *NewGVN::getMemoryClass(
const MemoryAccess *MA)
const {
1637 assert(Result &&
"Should have found memory class");
1644 CongruenceClass *NewClass) {
1646 "Every MemoryAccess should be getting mapped to a non-null class");
1650 <<
" with current MemoryAccess leader ");
1654 bool Changed =
false;
1656 if (LookupResult != MemoryAccessToClass.
end()) {
1658 if (OldClass != NewClass) {
1660 if (
auto *MP = dyn_cast<MemoryPhi>(
From)) {
1661 OldClass->memory_erase(MP);
1662 NewClass->memory_insert(MP);
1664 if (OldClass->getMemoryLeader() ==
From) {
1665 if (OldClass->definesNoMemory()) {
1666 OldClass->setMemoryLeader(
nullptr);
1668 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
1670 << OldClass->getID() <<
" to "
1671 << *OldClass->getMemoryLeader()
1672 <<
" due to removal of a memory member " << *
From
1674 markMemoryLeaderChangeTouched(OldClass);
1697 auto ICS = InstCycleState.
lookup(
I);
1698 if (ICS == ICS_Unknown) {
1700 auto &
SCC = SCCFinder.getComponentFor(
I);
1702 if (
SCC.size() == 1)
1703 InstCycleState.
insert({
I, ICS_CycleFree});
1708 ICS = AllPhis ? ICS_CycleFree : ICS_Cycle;
1709 for (
const auto *Member : SCC)
1710 if (
auto *MemberPhi = dyn_cast<PHINode>(Member))
1711 InstCycleState.
insert({MemberPhi, ICS});
1714 if (ICS == ICS_Cycle)
1725 bool HasBackedge =
false;
1730 bool OriginalOpsConstant =
true;
1731 auto *
E = cast<PHIExpression>(createPHIExpression(
1732 PHIOps,
I, PHIBlock, HasBackedge, OriginalOpsConstant));
1736 bool HasUndef =
false, HasPoison =
false;
1738 if (isa<PoisonValue>(Arg)) {
1742 if (isa<UndefValue>(
Arg)) {
1749 if (Filtered.empty()) {
1754 dbgs() <<
"PHI Node " << *
I
1755 <<
" has no non-undef arguments, valuing it as undef\n");
1760 dbgs() <<
"PHI Node " << *
I
1761 <<
" has no non-poison arguments, valuing it as poison\n");
1765 LLVM_DEBUG(
dbgs() <<
"No arguments of PHI node " << *
I <<
" are live\n");
1766 deleteExpression(
E);
1767 return createDeadExpression();
1769 Value *AllSameValue = *(Filtered.begin());
1787 if (HasPoison || HasUndef) {
1793 if (HasBackedge && !OriginalOpsConstant &&
1794 !isa<UndefValue>(AllSameValue) && !isCycleFree(
I))
1798 if (
auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
1799 if (!someEquivalentDominates(AllSameInst,
I))
1805 if (isa<Instruction>(AllSameValue) &&
1806 InstrToDFSNum(AllSameValue) > InstrToDFSNum(
I))
1808 NumGVNPhisAllSame++;
1809 LLVM_DEBUG(
dbgs() <<
"Simplified PHI node " << *
I <<
" to " << *AllSameValue
1811 deleteExpression(
E);
1812 return createVariableOrConstant(AllSameValue);
1818NewGVN::performSymbolicAggrValueEvaluation(
Instruction *
I)
const {
1819 if (
auto *EI = dyn_cast<ExtractValueInst>(
I)) {
1820 auto *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
1821 if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0)
1825 return createBinaryExpression(WO->getBinaryOp(), EI->getType(),
1826 WO->getLHS(), WO->getRHS(),
I);
1829 return createAggregateValueExpression(
I);
1832NewGVN::ExprResult NewGVN::performSymbolicCmpEvaluation(
Instruction *
I)
const {
1833 assert(isa<CmpInst>(
I) &&
"Expected a cmp instruction.");
1835 auto *CI = cast<CmpInst>(
I);
1838 auto Op0 = lookupOperandLeader(CI->
getOperand(0));
1839 auto Op1 = lookupOperandLeader(CI->
getOperand(1));
1840 auto OurPredicate = CI->getPredicate();
1841 if (shouldSwapOperands(Op0, Op1)) {
1843 OurPredicate = CI->getSwappedPredicate();
1850 auto *CmpPI = PredInfo->getPredicateInfoFor(
I);
1851 if (isa_and_nonnull<PredicateAssume>(CmpPI))
1852 return ExprResult::some(
1857 if (CI->isTrueWhenEqual())
1858 return ExprResult::some(
1860 else if (CI->isFalseWhenEqual())
1861 return ExprResult::some(
1890 for (
const auto &Op : CI->
operands()) {
1891 auto *PI = PredInfo->getPredicateInfoFor(Op);
1892 if (
const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
1893 if (PI == LastPredInfo)
1898 if (!DT->
dominates(PBranch->To, getBlockForValue(
I)))
1905 auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
1908 auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
1909 auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
1910 auto BranchPredicate = BranchCond->getPredicate();
1911 if (shouldSwapOperands(BranchOp0, BranchOp1)) {
1913 BranchPredicate = BranchCond->getSwappedPredicate();
1915 if (BranchOp0 == Op0 && BranchOp1 == Op1) {
1916 if (PBranch->TrueEdge) {
1921 return ExprResult::some(
1928 return ExprResult::some(
1935 if (BranchPredicate == OurPredicate) {
1937 return ExprResult::some(
1940 }
else if (BranchPredicate ==
1943 return ExprResult::some(
1952 return createExpression(
I);
1957NewGVN::performSymbolicEvaluation(
Value *V,
1961 if (
auto *
C = dyn_cast<Constant>(V))
1962 E = createConstantExpression(
C);
1963 else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
1964 E = createVariableExpression(V);
1969 auto *
I = cast<Instruction>(V);
1970 switch (
I->getOpcode()) {
1971 case Instruction::ExtractValue:
1972 case Instruction::InsertValue:
1973 E = performSymbolicAggrValueEvaluation(
I);
1975 case Instruction::PHI: {
1977 auto *PN = cast<PHINode>(
I);
1978 for (
unsigned i = 0; i < PN->getNumOperands(); ++i)
1979 Ops.
push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)});
1982 E = performSymbolicPHIEvaluation(Ops,
I, getBlockForValue(
I));
1984 case Instruction::Call:
1985 return performSymbolicCallEvaluation(
I);
1987 case Instruction::Store:
1988 E = performSymbolicStoreEvaluation(
I);
1990 case Instruction::Load:
1991 E = performSymbolicLoadEvaluation(
I);
1993 case Instruction::BitCast:
1994 case Instruction::AddrSpaceCast:
1995 return createExpression(
I);
1997 case Instruction::ICmp:
1998 case Instruction::FCmp:
1999 return performSymbolicCmpEvaluation(
I);
2001 case Instruction::FNeg:
2002 case Instruction::Add:
2003 case Instruction::FAdd:
2004 case Instruction::Sub:
2005 case Instruction::FSub:
2006 case Instruction::Mul:
2007 case Instruction::FMul:
2008 case Instruction::UDiv:
2009 case Instruction::SDiv:
2010 case Instruction::FDiv:
2011 case Instruction::URem:
2012 case Instruction::SRem:
2013 case Instruction::FRem:
2014 case Instruction::Shl:
2015 case Instruction::LShr:
2016 case Instruction::AShr:
2017 case Instruction::And:
2018 case Instruction::Or:
2019 case Instruction::Xor:
2020 case Instruction::Trunc:
2021 case Instruction::ZExt:
2022 case Instruction::SExt:
2023 case Instruction::FPToUI:
2024 case Instruction::FPToSI:
2025 case Instruction::UIToFP:
2026 case Instruction::SIToFP:
2027 case Instruction::FPTrunc:
2028 case Instruction::FPExt:
2029 case Instruction::PtrToInt:
2030 case Instruction::IntToPtr:
2031 case Instruction::Select:
2032 case Instruction::ExtractElement:
2033 case Instruction::InsertElement:
2034 case Instruction::GetElementPtr:
2035 return createExpression(
I);
2037 case Instruction::ShuffleVector:
2039 return ExprResult::none();
2041 return ExprResult::none();
2044 return ExprResult::some(
E);
2049template <
typename Map,
typename KeyType>
2050void NewGVN::touchAndErase(Map &M,
const KeyType &Key) {
2051 const auto Result =
M.find_as(Key);
2052 if (Result !=
M.end()) {
2053 for (
const typename Map::mapped_type::value_type Mapped :
Result->second)
2054 TouchedInstructions.
set(InstrToDFSNum(Mapped));
2061 if (isa<Instruction>(To))
2065void NewGVN::addAdditionalUsers(ExprResult &Res,
Instruction *
User)
const {
2066 if (Res.ExtraDep && Res.ExtraDep !=
User)
2067 addAdditionalUsers(Res.ExtraDep,
User);
2068 Res.ExtraDep =
nullptr;
2071 if (
const auto *PBranch = dyn_cast<PredicateBranch>(Res.PredDep))
2072 PredicateToUsers[PBranch->Condition].
insert(
User);
2073 else if (
const auto *PAssume = dyn_cast<PredicateAssume>(Res.PredDep))
2074 PredicateToUsers[PAssume->Condition].
insert(
User);
2076 Res.PredDep =
nullptr;
2079void NewGVN::markUsersTouched(
Value *V) {
2081 for (
auto *
User :
V->users()) {
2082 assert(isa<Instruction>(
User) &&
"Use of value not within an instruction?");
2083 TouchedInstructions.
set(InstrToDFSNum(
User));
2085 touchAndErase(AdditionalUsers, V);
2089 LLVM_DEBUG(
dbgs() <<
"Adding memory user " << *U <<
" to " << *To <<
"\n");
2090 MemoryToUsers[To].
insert(U);
2093void NewGVN::markMemoryDefTouched(
const MemoryAccess *MA) {
2094 TouchedInstructions.
set(MemoryToDFSNum(MA));
2097void NewGVN::markMemoryUsersTouched(
const MemoryAccess *MA) {
2098 if (isa<MemoryUse>(MA))
2100 for (
const auto *U : MA->
users())
2101 TouchedInstructions.
set(MemoryToDFSNum(U));
2102 touchAndErase(MemoryToUsers, MA);
2106void NewGVN::markPredicateUsersTouched(
Instruction *
I) {
2107 touchAndErase(PredicateToUsers,
I);
2111void NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *
CC) {
2112 for (
const auto *M :
CC->memory())
2113 markMemoryDefTouched(M);
2118void NewGVN::markValueLeaderChangeTouched(CongruenceClass *
CC) {
2119 for (
auto *M : *
CC) {
2120 if (
auto *
I = dyn_cast<Instruction>(M))
2121 TouchedInstructions.
set(InstrToDFSNum(
I));
2128template <
class T,
class Range>
2129T *NewGVN::getMinDFSOfRange(
const Range &R)
const {
2130 std::pair<T *, unsigned> MinDFS = {
nullptr, ~0
U};
2131 for (
const auto X : R) {
2132 auto DFSNum = InstrToDFSNum(
X);
2133 if (DFSNum < MinDFS.second)
2134 MinDFS = {
X, DFSNum};
2136 return MinDFS.first;
2142const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *
CC)
const {
2146 assert(!
CC->definesNoMemory() &&
"Can't get next leader if there is none");
2147 if (
CC->getStoreCount() > 0) {
2148 if (
auto *
NL = dyn_cast_or_null<StoreInst>(
CC->getNextLeader().first))
2149 return getMemoryAccess(
NL);
2152 *
CC, [&](
const Value *V) {
return isa<StoreInst>(V); }));
2153 return getMemoryAccess(cast<StoreInst>(V));
2159 if (
CC->memory_size() == 1)
2160 return *
CC->memory_begin();
2161 return getMinDFSOfRange<const MemoryPhi>(
CC->memory());
2167Value *NewGVN::getNextValueLeader(CongruenceClass *
CC)
const {
2172 if (
CC->size() == 1 ||
CC == TOPClass) {
2173 return *(
CC->begin());
2174 }
else if (
CC->getNextLeader().first) {
2175 ++NumGVNAvoidedSortedLeaderChanges;
2176 return CC->getNextLeader().first;
2178 ++NumGVNSortedLeaderChanges;
2182 return getMinDFSOfRange<Value>(*
CC);
2195void NewGVN::moveMemoryToNewCongruenceClass(
Instruction *
I,
2197 CongruenceClass *OldClass,
2198 CongruenceClass *NewClass) {
2201 assert((!InstMA || !OldClass->getMemoryLeader() ||
2202 OldClass->getLeader() !=
I ||
2203 MemoryAccessToClass.
lookup(OldClass->getMemoryLeader()) ==
2204 MemoryAccessToClass.
lookup(InstMA)) &&
2205 "Representative MemoryAccess mismatch");
2207 if (!NewClass->getMemoryLeader()) {
2209 assert(NewClass->size() == 1 ||
2210 (isa<StoreInst>(
I) && NewClass->getStoreCount() == 1));
2211 NewClass->setMemoryLeader(InstMA);
2214 << NewClass->getID()
2215 <<
" due to new memory instruction becoming leader\n");
2216 markMemoryLeaderChangeTouched(NewClass);
2218 setMemoryClass(InstMA, NewClass);
2220 if (OldClass->getMemoryLeader() == InstMA) {
2221 if (!OldClass->definesNoMemory()) {
2222 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
2224 << OldClass->getID() <<
" to "
2225 << *OldClass->getMemoryLeader()
2226 <<
" due to removal of old leader " << *InstMA <<
"\n");
2227 markMemoryLeaderChangeTouched(OldClass);
2229 OldClass->setMemoryLeader(
nullptr);
2236 CongruenceClass *OldClass,
2237 CongruenceClass *NewClass) {
2238 if (
I == OldClass->getNextLeader().first)
2239 OldClass->resetNextLeader();
2242 NewClass->insert(
I);
2244 if (NewClass->getLeader() !=
I)
2245 NewClass->addPossibleNextLeader({
I, InstrToDFSNum(
I)});
2247 if (
auto *SI = dyn_cast<StoreInst>(
I)) {
2248 OldClass->decStoreCount();
2256 if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) {
2259 if (
auto *SE = dyn_cast<StoreExpression>(
E)) {
2260 NewClass->setStoredValue(SE->getStoredValue());
2261 markValueLeaderChangeTouched(NewClass);
2264 << NewClass->getID() <<
" from "
2265 << *NewClass->getLeader() <<
" to " << *SI
2266 <<
" because store joined class\n");
2269 NewClass->setLeader(SI);
2273 NewClass->incStoreCount();
2279 auto *InstMA = dyn_cast_or_null<MemoryDef>(getMemoryAccess(
I));
2281 moveMemoryToNewCongruenceClass(
I, InstMA, OldClass, NewClass);
2282 ValueToClass[
I] = NewClass;
2284 if (OldClass->empty() && OldClass != TOPClass) {
2285 if (OldClass->getDefiningExpr()) {
2286 LLVM_DEBUG(
dbgs() <<
"Erasing expression " << *OldClass->getDefiningExpr()
2287 <<
" from table\n");
2290 auto Iter = ExpressionToClass.find_as(
2292 if (Iter != ExpressionToClass.end())
2293 ExpressionToClass.erase(Iter);
2294#ifdef EXPENSIVE_CHECKS
2296 (*OldClass->getDefiningExpr() != *
E || ExpressionToClass.lookup(
E)) &&
2297 "We erased the expression we just inserted, which should not happen");
2300 }
else if (OldClass->getLeader() ==
I) {
2305 << OldClass->getID() <<
"\n");
2306 ++NumGVNLeaderChanges;
2311 if (OldClass->getStoreCount() == 0) {
2312 if (OldClass->getStoredValue())
2313 OldClass->setStoredValue(
nullptr);
2315 OldClass->setLeader(getNextValueLeader(OldClass));
2316 OldClass->resetNextLeader();
2317 markValueLeaderChangeTouched(OldClass);
2323void NewGVN::markPhiOfOpsChanged(
const Expression *
E) {
2324 touchAndErase(ExpressionToPhiOfOps,
E);
2332 CongruenceClass *IClass = ValueToClass.
lookup(
I);
2333 assert(IClass &&
"Should have found a IClass");
2335 assert(!IClass->isDead() &&
"Found a dead class");
2337 CongruenceClass *EClass =
nullptr;
2338 if (
const auto *VE = dyn_cast<VariableExpression>(
E)) {
2339 EClass = ValueToClass.
lookup(VE->getVariableValue());
2340 }
else if (isa<DeadExpression>(
E)) {
2344 auto lookupResult = ExpressionToClass.insert({
E,
nullptr});
2347 if (lookupResult.second) {
2348 CongruenceClass *NewClass = createCongruenceClass(
nullptr,
E);
2349 auto place = lookupResult.first;
2350 place->second = NewClass;
2353 if (
const auto *CE = dyn_cast<ConstantExpression>(
E)) {
2354 NewClass->setLeader(
CE->getConstantValue());
2355 }
else if (
const auto *SE = dyn_cast<StoreExpression>(
E)) {
2357 NewClass->setLeader(SI);
2358 NewClass->setStoredValue(SE->getStoredValue());
2362 NewClass->setLeader(
I);
2364 assert(!isa<VariableExpression>(
E) &&
2365 "VariableExpression should have been handled already");
2369 <<
" using expression " << *
E <<
" at "
2370 << NewClass->getID() <<
" and leader "
2371 << *(NewClass->getLeader()));
2372 if (NewClass->getStoredValue())
2374 << *(NewClass->getStoredValue()));
2377 EClass = lookupResult.first->second;
2378 if (isa<ConstantExpression>(
E))
2379 assert((isa<Constant>(EClass->getLeader()) ||
2380 (EClass->getStoredValue() &&
2381 isa<Constant>(EClass->getStoredValue()))) &&
2382 "Any class with a constant expression should have a "
2385 assert(EClass &&
"Somehow don't have an eclass");
2387 assert(!EClass->isDead() &&
"We accidentally looked up a dead class");
2390 bool ClassChanged = IClass != EClass;
2391 bool LeaderChanged = LeaderChanges.
erase(
I);
2392 if (ClassChanged || LeaderChanged) {
2393 LLVM_DEBUG(
dbgs() <<
"New class " << EClass->getID() <<
" for expression "
2396 moveValueToNewCongruenceClass(
I,
E, IClass, EClass);
2397 markPhiOfOpsChanged(
E);
2400 markUsersTouched(
I);
2402 markMemoryUsersTouched(MA);
2403 if (
auto *CI = dyn_cast<CmpInst>(
I))
2404 markPredicateUsersTouched(CI);
2410 if (ClassChanged && isa<StoreInst>(
I)) {
2411 auto *OldE = ValueToExpression.
lookup(
I);
2414 if (OldE && isa<StoreExpression>(OldE) && *
E != *OldE) {
2418 if (Iter != ExpressionToClass.end())
2419 ExpressionToClass.erase(Iter);
2422 ValueToExpression[
I] =
E;
2429 if (ReachableEdges.
insert({From, To}).second) {
2431 if (ReachableBlocks.
insert(To).second) {
2433 <<
" marked reachable\n");
2434 const auto &InstRange = BlockInstRange.
lookup(To);
2435 TouchedInstructions.
set(InstRange.first, InstRange.second);
2438 <<
" was reachable, but new edge {"
2440 <<
"} to it found\n");
2447 TouchedInstructions.
set(InstrToDFSNum(MemPhi));
2452 for (
auto InstNum : RevisitOnReachabilityChange[To])
2453 TouchedInstructions.
set(InstNum);
2462 return isa<Constant>(Result) ?
Result :
nullptr;
2471 Value *CondEvaluated = findConditionEquivalence(
Cond);
2472 if (!CondEvaluated) {
2473 if (
auto *
I = dyn_cast<Instruction>(
Cond)) {
2475 auto Res = performSymbolicEvaluation(
I, Visited);
2476 if (
const auto *CE = dyn_cast_or_null<ConstantExpression>(Res.Expr)) {
2477 CondEvaluated =
CE->getConstantValue();
2478 addAdditionalUsers(Res,
I);
2482 Res.ExtraDep =
nullptr;
2484 }
else if (isa<ConstantInt>(
Cond)) {
2485 CondEvaluated =
Cond;
2489 if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
2492 <<
" evaluated to true\n");
2493 updateReachableEdge(
B, TrueSucc);
2494 }
else if (CI->
isZero()) {
2496 <<
" evaluated to false\n");
2497 updateReachableEdge(
B, FalseSucc);
2500 updateReachableEdge(
B, TrueSucc);
2501 updateReachableEdge(
B, FalseSucc);
2503 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
2507 Value *SwitchCond =
SI->getCondition();
2508 Value *CondEvaluated = findConditionEquivalence(SwitchCond);
2510 if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
2511 auto *CondVal = cast<ConstantInt>(CondEvaluated);
2513 auto Case = *
SI->findCaseValue(CondVal);
2514 if (Case.getCaseSuccessor() ==
SI->getDefaultDest()) {
2518 updateReachableEdge(
B,
SI->getDefaultDest());
2522 BasicBlock *TargetBlock = Case.getCaseSuccessor();
2523 updateReachableEdge(
B, TargetBlock);
2525 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i != e; ++i) {
2527 updateReachableEdge(
B, TargetBlock);
2535 updateReachableEdge(
B, TargetBlock);
2541 auto *MA = getMemoryAccess(TI);
2542 if (MA && !isa<MemoryUse>(MA)) {
2543 auto *
CC = ensureLeaderOfMemoryClass(MA);
2544 if (setMemoryClass(MA,
CC))
2545 markMemoryUsersTouched(MA);
2552 InstrDFS.
erase(PHITemp);
2555 TempToBlock.
erase(PHITemp);
2566 InstrDFS[
Op] = InstrToDFSNum(ExistingValue);
2567 AllTempInstructions.
insert(Op);
2568 TempToBlock[
Op] = BB;
2569 RealToTemp[ExistingValue] =
Op;
2572 for (
auto *U : ExistingValue->
users())
2573 if (
auto *UI = dyn_cast<Instruction>(U))
2580 return isa<BinaryOperator>(
I) || isa<SelectInst>(
I) || isa<CmpInst>(
I) ||
2595 while (!Worklist.
empty()) {
2597 if (!isa<Instruction>(
I))
2600 auto OISIt = OpSafeForPHIOfOps.
find(
I);
2601 if (OISIt != OpSafeForPHIOfOps.
end())
2602 return OISIt->second;
2607 OpSafeForPHIOfOps.
insert({
I,
true});
2611 if (isa<PHINode>(
I) && getBlockForValue(
I) == PHIBlock) {
2612 OpSafeForPHIOfOps.
insert({
I,
false});
2616 auto *OrigI = cast<Instruction>(
I);
2623 if (OrigI->mayReadFromMemory())
2627 for (
auto *Op : OrigI->operand_values()) {
2628 if (!isa<Instruction>(Op))
2631 auto OISIt = OpSafeForPHIOfOps.
find(OrigI);
2632 if (OISIt != OpSafeForPHIOfOps.
end()) {
2633 if (!OISIt->second) {
2634 OpSafeForPHIOfOps.
insert({
I,
false});
2639 if (!Visited.
insert(Op).second)
2641 Worklist.
push_back(cast<Instruction>(Op));
2644 OpSafeForPHIOfOps.
insert({
V,
true});
2657 unsigned IDFSNum = InstrToDFSNum(OrigInst);
2659 AllTempInstructions.
insert(TransInst);
2663 TempToBlock.
insert({TransInst, PredBB});
2664 InstrDFS.
insert({TransInst, IDFSNum});
2666 auto Res = performSymbolicEvaluation(TransInst, Visited);
2668 addAdditionalUsers(Res, OrigInst);
2669 InstrDFS.
erase(TransInst);
2670 AllTempInstructions.
erase(TransInst);
2671 TempToBlock.
erase(TransInst);
2673 TempToMemory.
erase(TransInst);
2676 auto *FoundVal = findPHIOfOpsLeader(
E, OrigInst, PredBB);
2678 ExpressionToPhiOfOps[
E].
insert(OrigInst);
2679 LLVM_DEBUG(
dbgs() <<
"Cannot find phi of ops operand for " << *TransInst
2683 if (
auto *SI = dyn_cast<StoreInst>(FoundVal))
2684 FoundVal =
SI->getValueOperand();
2696 if (!Visited.
insert(
I).second)
2702 if (!isCycleFree(
I))
2709 auto *MemAccess = getMemoryAccess(
I);
2713 if (MemAccess && !isa<MemoryPhi>(MemAccess->getDefiningAccess()) &&
2714 MemAccess->getDefiningAccess()->
getBlock() ==
I->getParent())
2724 for (
auto *Op : Ops) {
2725 if (!isa<PHINode>(Op)) {
2726 auto *ValuePHI = RealToTemp.
lookup(Op);
2732 OpPHI = cast<PHINode>(Op);
2733 if (!SamePHIBlock) {
2734 SamePHIBlock = getBlockForValue(OpPHI);
2735 }
else if (SamePHIBlock != getBlockForValue(OpPHI)) {
2738 <<
"PHIs for operands are not all in the same block, aborting\n");
2753 auto *PHIBlock = getBlockForValue(OpPHI);
2754 RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(
I));
2755 for (
unsigned PredNum = 0; PredNum < OpPHI->
getNumOperands(); ++PredNum) {
2757 Value *FoundVal =
nullptr;
2761 if (ReachableEdges.
count({PredBB, PHIBlock})) {
2766 TempToMemory.
insert({ValueOp, MemAccess});
2767 bool SafeForPHIOfOps =
true;
2769 for (
auto &Op : ValueOp->
operands()) {
2770 auto *OrigOp = &*
Op;
2773 if (isa<PHINode>(Op)) {
2774 Op =
Op->DoPHITranslation(PHIBlock, PredBB);
2775 if (Op != OrigOp && Op !=
I)
2777 }
else if (
auto *ValuePHI = RealToTemp.
lookup(Op)) {
2778 if (getBlockForValue(ValuePHI) == PHIBlock)
2779 Op = ValuePHI->getIncomingValueForBlock(PredBB);
2784 (
Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps));
2791 FoundVal = !SafeForPHIOfOps ? nullptr
2792 : findLeaderForInst(ValueOp, Visited,
2793 MemAccess,
I, PredBB);
2798 if (SafeForPHIOfOps)
2799 for (
auto *Dep : CurrentDeps)
2800 addAdditionalUsers(Dep,
I);
2806 LLVM_DEBUG(
dbgs() <<
"Skipping phi of ops operand for incoming block "
2808 <<
" because the block is unreachable\n");
2810 RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(
I));
2814 LLVM_DEBUG(
dbgs() <<
"Found phi of ops operand " << *FoundVal <<
" in "
2817 for (
auto *Dep : Deps)
2818 addAdditionalUsers(Dep,
I);
2820 auto *
E = performSymbolicPHIEvaluation(PHIOps,
I, PHIBlock);
2821 if (isa<ConstantExpression>(
E) || isa<VariableExpression>(
E)) {
2824 <<
"Not creating real PHI of ops because it simplified to existing "
2825 "value or constant\n");
2831 for (
auto &O : PHIOps)
2832 addAdditionalUsers(
O.first,
I);
2836 auto *ValuePHI = RealToTemp.
lookup(
I);
2837 bool NewPHI =
false;
2841 addPhiOfOps(ValuePHI, PHIBlock,
I);
2843 NumGVNPHIOfOpsCreated++;
2846 for (
auto PHIOp : PHIOps)
2847 ValuePHI->addIncoming(PHIOp.first, PHIOp.second);
2849 TempToBlock[ValuePHI] = PHIBlock;
2851 for (
auto PHIOp : PHIOps) {
2852 ValuePHI->setIncomingValue(i, PHIOp.first);
2853 ValuePHI->setIncomingBlock(i, PHIOp.second);
2857 RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(
I));
2858 LLVM_DEBUG(
dbgs() <<
"Created phi of ops " << *ValuePHI <<
" for " << *
I
2867void NewGVN::initializeCongruenceClasses(
Function &
F) {
2868 NextCongruenceNum = 0;
2878 TOPClass = createCongruenceClass(
nullptr,
nullptr);
2884 for (
auto *DTN :
nodes(DT)) {
2891 if (MemoryBlockDefs)
2892 for (
const auto &Def : *MemoryBlockDefs) {
2893 MemoryAccessToClass[&
Def] = TOPClass;
2894 auto *MD = dyn_cast<MemoryDef>(&Def);
2897 const MemoryPhi *MP = cast<MemoryPhi>(&Def);
2898 TOPClass->memory_insert(MP);
2899 MemoryPhiState.
insert({MP, MPS_TOP});
2902 if (MD && isa<StoreInst>(MD->getMemoryInst()))
2903 TOPClass->incStoreCount();
2909 for (
auto &
I : *BB) {
2910 if (isa<PHINode>(&
I))
2911 for (
auto *U :
I.users())
2912 if (
auto *UInst = dyn_cast<Instruction>(U))
2914 PHINodeUses.
insert(UInst);
2917 if (
I.isTerminator() &&
I.getType()->isVoidTy())
2919 TOPClass->insert(&
I);
2920 ValueToClass[&
I] = TOPClass;
2925 for (
auto &FA :
F.args())
2926 createSingletonCongruenceClass(&FA);
2929void NewGVN::cleanupTables() {
2930 for (CongruenceClass *&
CC : CongruenceClasses) {
2932 <<
CC->size() <<
" members\n");
2941 AllTempInstructions.
end());
2942 AllTempInstructions.
clear();
2946 for (
auto *
I : TempInst) {
2947 I->dropAllReferences();
2950 while (!TempInst.empty()) {
2951 auto *
I = TempInst.pop_back_val();
2955 ValueToClass.
clear();
2956 ArgRecycler.
clear(ExpressionAllocator);
2957 ExpressionAllocator.
Reset();
2958 CongruenceClasses.clear();
2959 ExpressionToClass.clear();
2960 ValueToExpression.
clear();
2962 AdditionalUsers.
clear();
2963 ExpressionToPhiOfOps.
clear();
2964 TempToBlock.
clear();
2965 TempToMemory.
clear();
2966 PHINodeUses.
clear();
2967 OpSafeForPHIOfOps.
clear();
2968 ReachableBlocks.
clear();
2969 ReachableEdges.
clear();
2971 ProcessedCount.
clear();
2974 InstructionsToErase.
clear();
2976 BlockInstRange.
clear();
2977 TouchedInstructions.
clear();
2978 MemoryAccessToClass.
clear();
2979 PredicateToUsers.
clear();
2980 MemoryToUsers.
clear();
2981 RevisitOnReachabilityChange.
clear();
2982 IntrinsicInstPred.
clear();
2987std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(
BasicBlock *
B,
2989 unsigned End = Start;
2991 InstrDFS[MemPhi] = End++;
2996 for (
auto &
I : *
B) {
3002 LLVM_DEBUG(
dbgs() <<
"Skipping trivially dead instruction " <<
I <<
"\n");
3003 markInstructionForDeletion(&
I);
3006 if (isa<PHINode>(&
I))
3007 RevisitOnReachabilityChange[
B].set(End);
3008 InstrDFS[&
I] = End++;
3015 return std::make_pair(Start, End);
3018void NewGVN::updateProcessedCount(
const Value *V) {
3020 if (ProcessedCount.
count(V) == 0) {
3021 ProcessedCount.
insert({
V, 1});
3023 ++ProcessedCount[
V];
3024 assert(ProcessedCount[V] < 100 &&
3025 "Seem to have processed the same Value a lot");
3031void NewGVN::valueNumberMemoryPhi(
MemoryPhi *MP) {
3038 return cast<MemoryAccess>(U) != MP &&
3039 !isMemoryAccessTOP(cast<MemoryAccess>(U)) &&
3040 ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock});
3045 if (Filtered.begin() == Filtered.end()) {
3046 if (setMemoryClass(MP, TOPClass))
3047 markMemoryUsersTouched(MP);
3053 auto LookupFunc = [&](
const Use &
U) {
3054 return lookupMemoryLeader(cast<MemoryAccess>(U));
3056 auto MappedBegin =
map_iterator(Filtered.begin(), LookupFunc);
3057 auto MappedEnd =
map_iterator(Filtered.end(), LookupFunc);
3061 const auto *AllSameValue = *MappedBegin;
3063 bool AllEqual = std::all_of(
3064 MappedBegin, MappedEnd,
3065 [&AllSameValue](
const MemoryAccess *V) {
return V == AllSameValue; });
3068 LLVM_DEBUG(
dbgs() <<
"Memory Phi value numbered to " << *AllSameValue
3077 CongruenceClass *
CC =
3078 AllEqual ? getMemoryClass(AllSameValue) : ensureLeaderOfMemoryClass(MP);
3079 auto OldState = MemoryPhiState.
lookup(MP);
3080 assert(OldState != MPS_Invalid &&
"Invalid memory phi state");
3081 auto NewState = AllEqual ? MPS_Equivalent : MPS_Unique;
3082 MemoryPhiState[MP] = NewState;
3083 if (setMemoryClass(MP,
CC) || OldState != NewState)
3084 markMemoryUsersTouched(MP);
3091 if (!
I->isTerminator()) {
3095 auto Res = performSymbolicEvaluation(
I, Visited);
3096 Symbolized = Res.Expr;
3097 addAdditionalUsers(Res,
I);
3100 if (Symbolized && !isa<ConstantExpression>(Symbolized) &&
3101 !isa<VariableExpression>(Symbolized) && PHINodeUses.
count(
I)) {
3102 auto *PHIE = makePossiblePHIOfOps(
I, Visited);
3107 }
else if (
auto *Op = RealToTemp.
lookup(
I)) {
3108 removePhiOfOps(
I, Op);
3117 if (Symbolized ==
nullptr)
3118 Symbolized = createUnknownExpression(
I);
3119 performCongruenceFinding(
I, Symbolized);
3124 if (!
I->getType()->isVoidTy()) {
3125 auto *Symbolized = createUnknownExpression(
I);
3126 performCongruenceFinding(
I, Symbolized);
3128 processOutgoingEdges(
I,
I->getParent());
3134bool NewGVN::singleReachablePHIPath(
3137 if (First == Second)
3147 if (!Visited.
insert(First).second)
3150 const auto *EndDef =
First;
3152 if (ChainDef == Second)
3158 auto *MP = cast<MemoryPhi>(EndDef);
3159 auto ReachableOperandPred = [&](
const Use &
U) {
3162 auto FilteredPhiArgs =
3165 llvm::copy(FilteredPhiArgs, std::back_inserter(OperandList));
3168 return singleReachablePHIPath(Visited, cast<MemoryAccess>(OperandList[0]),
3177void NewGVN::verifyMemoryCongruency()
const {
3180 for (
const auto *
CC : CongruenceClasses) {
3181 if (
CC == TOPClass ||
CC->isDead())
3183 if (
CC->getStoreCount() != 0) {
3184 assert((
CC->getStoredValue() || !isa<StoreInst>(
CC->getLeader())) &&
3185 "Any class with a store as a leader should have a "
3186 "representative stored value");
3188 "Any congruence class with a store should have a "
3189 "representative access");
3192 if (
CC->getMemoryLeader())
3194 "Representative MemoryAccess does not appear to be reverse "
3196 for (
const auto *M :
CC->memory())
3198 "Memory member does not appear to be reverse mapped properly");
3206 auto ReachableAccessPred =
3207 [&](
const std::pair<const MemoryAccess *, CongruenceClass *> Pair) {
3208 bool Result = ReachableBlocks.
count(Pair.first->getBlock());
3210 MemoryToDFSNum(Pair.first) == 0)
3212 if (
auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
3217 if (
auto *MemPHI = dyn_cast<MemoryPhi>(Pair.first)) {
3218 for (
const auto &U : MemPHI->incoming_values()) {
3219 if (
auto *
I = dyn_cast<Instruction>(&*U)) {
3231 for (
auto KV : Filtered) {
3232 if (
auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
3233 auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second->getMemoryLeader());
3234 if (FirstMUD && SecondMUD) {
3236 assert((singleReachablePHIPath(VisitedMAS, FirstMUD, SecondMUD) ||
3237 ValueToClass.
lookup(FirstMUD->getMemoryInst()) ==
3238 ValueToClass.
lookup(SecondMUD->getMemoryInst())) &&
3239 "The instructions for these memory operations should have "
3240 "been in the same congruence class or reachable through"
3241 "a single argument phi");
3243 }
else if (
auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {
3246 auto ReachableOperandPred = [&](
const Use &
U) {
3247 return ReachableEdges.
count(
3248 {FirstMP->getIncomingBlock(U), FirstMP->getBlock()}) &&
3253 auto FilteredPhiArgs =
3256 std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
3257 std::back_inserter(PhiOpClasses), [&](
const Use &U) {
3258 const MemoryDef *MD = cast<MemoryDef>(U);
3259 return ValueToClass.lookup(MD->getMemoryInst());
3262 "All MemoryPhi arguments should be in the same class");
3271void NewGVN::verifyIterationSettled(
Function &
F) {
3281 std::map<const Value *, CongruenceClass> BeforeIteration;
3283 for (
auto &KV : ValueToClass) {
3284 if (
auto *
I = dyn_cast<Instruction>(KV.first))
3286 if (InstrToDFSNum(
I) == 0)
3288 BeforeIteration.insert({KV.first, *KV.second});
3291 TouchedInstructions.
set();
3292 TouchedInstructions.
reset(0);
3293 OpSafeForPHIOfOps.
clear();
3294 iterateTouchedInstructions();
3297 for (
const auto &KV : ValueToClass) {
3298 if (
auto *
I = dyn_cast<Instruction>(KV.first))
3300 if (InstrToDFSNum(
I) == 0)
3304 auto *BeforeCC = &BeforeIteration.
find(KV.first)->second;
3305 auto *AfterCC = KV.second;
3308 if (!EqualClasses.
count({BeforeCC, AfterCC})) {
3309 assert(BeforeCC->isEquivalentTo(AfterCC) &&
3310 "Value number changed after main loop completed!");
3311 EqualClasses.
insert({BeforeCC, AfterCC});
3322void NewGVN::verifyStoreExpressions()
const {
3327 std::pair<
const Value *,
3328 std::tuple<const Value *, const CongruenceClass *, Value *>>>
3330 for (
const auto &KV : ExpressionToClass) {
3331 if (
auto *SE = dyn_cast<StoreExpression>(KV.first)) {
3333 auto Res = StoreExpressionSet.insert(
3334 {SE->getOperand(0), std::make_tuple(SE->getMemoryLeader(), KV.second,
3335 SE->getStoredValue())});
3336 bool Okay = Res.second;
3341 Okay = (std::get<1>(Res.first->second) == KV.second) &&
3342 (lookupOperandLeader(std::get<2>(Res.first->second)) ==
3343 lookupOperandLeader(SE->getStoredValue()));
3344 assert(Okay &&
"Stored expression conflict exists in expression table");
3345 auto *ValueExpr = ValueToExpression.
lookup(SE->getStoreInst());
3346 assert(ValueExpr && ValueExpr->equals(*SE) &&
3347 "StoreExpression in ExpressionToClass is not latest "
3348 "StoreExpression for value");
3357void NewGVN::iterateTouchedInstructions() {
3360 int FirstInstr = TouchedInstructions.
find_first();
3362 if (FirstInstr == -1)
3364 const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
3365 while (TouchedInstructions.
any()) {
3371 for (
unsigned InstrNum : TouchedInstructions.
set_bits()) {
3375 if (InstrNum == 0) {
3376 TouchedInstructions.
reset(InstrNum);
3380 Value *
V = InstrFromDFSNum(InstrNum);
3381 const BasicBlock *CurrBlock = getBlockForValue(V);
3384 if (CurrBlock != LastBlock) {
3385 LastBlock = CurrBlock;
3386 bool BlockReachable = ReachableBlocks.
count(CurrBlock);
3387 const auto &CurrInstRange = BlockInstRange.
lookup(CurrBlock);
3390 if (!BlockReachable) {
3391 TouchedInstructions.
reset(CurrInstRange.first, CurrInstRange.second);
3394 <<
" because it is unreachable\n");
3397 updateProcessedCount(CurrBlock);
3401 TouchedInstructions.
reset(InstrNum);
3403 if (
auto *MP = dyn_cast<MemoryPhi>(V)) {
3405 valueNumberMemoryPhi(MP);
3406 }
else if (
auto *
I = dyn_cast<Instruction>(V)) {
3407 valueNumberInstruction(
I);
3411 updateProcessedCount(V);
3414 NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations);
3418bool NewGVN::runGVN() {
3421 bool Changed =
false;
3422 NumFuncArgs =
F.arg_size();
3424 SingletonDeadExpression =
new (ExpressionAllocator)
DeadExpression();
3428 unsigned ICount = 1;
3440 unsigned Counter = 0;
3441 for (
auto &
B : RPOT) {
3443 assert(
Node &&
"RPO and Dominator tree should have same reachability");
3444 RPOOrdering[
Node] = ++Counter;
3447 for (
auto &
B : RPOT) {
3449 if (
Node->getNumChildren() > 1)
3451 return RPOOrdering[
A] < RPOOrdering[
B];
3458 const auto &BlockRange = assignDFSNumbers(
B, ICount);
3459 BlockInstRange.
insert({
B, BlockRange});
3460 ICount += BlockRange.second - BlockRange.first;
3462 initializeCongruenceClasses(
F);
3464 TouchedInstructions.
resize(ICount);
3468 ExpressionToClass.reserve(ICount);
3471 const auto &InstRange = BlockInstRange.
lookup(&
F.getEntryBlock());
3472 TouchedInstructions.
set(InstRange.first, InstRange.second);
3474 <<
" marked reachable\n");
3475 ReachableBlocks.
insert(&
F.getEntryBlock());
3477 iterateTouchedInstructions();
3478 verifyMemoryCongruency();
3479 verifyIterationSettled(
F);
3480 verifyStoreExpressions();
3482 Changed |= eliminateInstructions(
F);
3485 for (
Instruction *ToErase : InstructionsToErase) {
3486 if (!ToErase->use_empty())
3489 assert(ToErase->getParent() &&
3490 "BB containing ToErase deleted unexpectedly!");
3491 ToErase->eraseFromParent();
3493 Changed |= !InstructionsToErase.empty();
3496 auto UnreachableBlockPred = [&](
const BasicBlock &BB) {
3497 return !ReachableBlocks.
count(&BB);
3502 <<
" is unreachable\n");
3503 deleteInstructionsInBlock(&BB);
3561 return std::tie(DFSIn, DFSOut,
LocalNum, Def, U) <
3572void NewGVN::convertClassToDFSOrdered(
3581 assert(BB &&
"Should have figured out a basic block for value");
3589 if (
auto *SI = dyn_cast<StoreInst>(
D)) {
3590 auto Leader = lookupOperandLeader(
SI->getValueOperand());
3592 VDDef.
Def.setPointer(Leader);
3594 VDDef.
Def.setPointer(
SI->getValueOperand());
3595 VDDef.
Def.setInt(
true);
3598 VDDef.
Def.setPointer(
D);
3601 "The dense set member should always be an instruction");
3606 if (
auto *PN = RealToTemp.
lookup(Def)) {
3608 dyn_cast_or_null<PHIExpression>(ValueToExpression.
lookup(Def));
3610 VDDef.
Def.setInt(
false);
3611 VDDef.
Def.setPointer(PN);
3617 unsigned int UseCount = 0;
3619 for (
auto &U :
Def->uses()) {
3620 if (
auto *
I = dyn_cast<Instruction>(
U.getUser())) {
3622 if (InstructionsToErase.count(
I))
3627 if (
auto *
P = dyn_cast<PHINode>(
I)) {
3628 IBlock =
P->getIncomingBlock(U);
3633 IBlock = getBlockForValue(
I);
3639 if (!ReachableBlocks.
contains(IBlock))
3655 ProbablyDead.
insert(Def);
3657 UseCounts[
Def] = UseCount;
3663void NewGVN::convertClassToLoadsAndStores(
3664 const CongruenceClass &
Dense,
3667 if (!isa<LoadInst>(
D) && !isa<StoreInst>(
D))
3675 VD.
Def.setPointer(
D);
3678 if (
auto *
I = dyn_cast<Instruction>(
D))
3689 I->replaceAllUsesWith(Repl);
3692void NewGVN::deleteInstructionsInBlock(
BasicBlock *BB) {
3694 ++NumGVNBlocksDeleted;
3698 auto StartPoint = BB->
rbegin();
3706 if (isa<LandingPadInst>(Inst))
3711 ++NumGVNInstrDeleted;
3720void NewGVN::markInstructionForDeletion(
Instruction *
I) {
3722 InstructionsToErase.insert(
I);
3730 markInstructionForDeletion(
I);
3737class ValueDFSStack {
3739 Value *back()
const {
return ValueStack.back(); }
3740 std::pair<int, int> dfs_back()
const {
return DFSStack.back(); }
3742 void push_back(
Value *V,
int DFSIn,
int DFSOut) {
3743 ValueStack.emplace_back(V);
3744 DFSStack.emplace_back(DFSIn, DFSOut);
3747 bool empty()
const {
return DFSStack.empty(); }
3749 bool isInScope(
int DFSIn,
int DFSOut)
const {
3752 return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
3755 void popUntilDFSScope(
int DFSIn,
int DFSOut) {
3758 assert(ValueStack.size() == DFSStack.size() &&
3759 "Mismatch between ValueStack and DFSStack");
3761 !DFSStack.empty() &&
3762 !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
3763 DFSStack.pop_back();
3764 ValueStack.pop_back();
3776CongruenceClass *NewGVN::getClassForExpression(
const Expression *
E)
const {
3777 if (
auto *VE = dyn_cast<VariableExpression>(
E))
3778 return ValueToClass.lookup(VE->getVariableValue());
3779 else if (isa<DeadExpression>(
E))
3781 return ExpressionToClass.lookup(
E);
3790 if (
auto *CE = dyn_cast<ConstantExpression>(
E))
3791 return CE->getConstantValue();
3792 if (
auto *VE = dyn_cast<VariableExpression>(
E)) {
3793 auto *
V = VE->getVariableValue();
3795 return VE->getVariableValue();
3798 auto *
CC = getClassForExpression(
E);
3802 return CC->getLeader();
3804 for (
auto *Member : *
CC) {
3805 auto *MemberInst = dyn_cast<Instruction>(Member);
3806 if (MemberInst == OrigInst)
3811 if (DT->
dominates(getBlockForValue(MemberInst), BB))
3817bool NewGVN::eliminateInstructions(
Function &
F) {
3841 bool AnythingReplaced =
false;
3850 for (
auto &Operand :
PHI->incoming_values())
3851 if (!ReachableEdges.
count({PHI->getIncomingBlock(Operand), BB})) {
3855 <<
" with poison due to it being unreachable\n");
3869 for (
auto &KV : ReachableEdges)
3870 ReachablePredCount[KV.getEnd()]++;
3871 for (
auto &BBPair : RevisitOnReachabilityChange) {
3872 for (
auto InstNum : BBPair.second) {
3873 auto *Inst = InstrFromDFSNum(InstNum);
3874 auto *
PHI = dyn_cast<PHINode>(Inst);
3878 auto *BB = BBPair.first;
3879 if (ReachablePredCount.
lookup(BB) !=
PHI->getNumIncomingValues())
3880 ReplaceUnreachablePHIArgs(
PHI, BB);
3886 for (
auto *
CC :
reverse(CongruenceClasses)) {
3893 if (
CC->isDead() ||
CC->empty())
3896 if (
CC == TOPClass) {
3897 for (
auto *M : *
CC) {
3898 auto *VTE = ValueToExpression.
lookup(M);
3899 if (VTE && isa<DeadExpression>(VTE))
3900 markInstructionForDeletion(cast<Instruction>(M));
3901 assert((!ReachableBlocks.
count(cast<Instruction>(M)->getParent()) ||
3902 InstructionsToErase.count(cast<Instruction>(M))) &&
3903 "Everything in TOP should be unreachable or dead at this "
3909 assert(
CC->getLeader() &&
"We should have had a leader");
3915 CC->getStoredValue() ?
CC->getStoredValue() :
CC->getLeader();
3918 for (
auto *M : *
CC) {
3921 if (Member == Leader || !isa<Instruction>(Member) ||
3922 Member->getType()->isVoidTy()) {
3923 MembersLeft.
insert(Member);
3926 LLVM_DEBUG(
dbgs() <<
"Found replacement " << *(Leader) <<
" for "
3927 << *Member <<
"\n");
3928 auto *
I = cast<Instruction>(Member);
3929 assert(Leader !=
I &&
"About to accidentally remove our leader");
3930 replaceInstruction(
I, Leader);
3931 AnythingReplaced =
true;
3933 CC->swap(MembersLeft);
3936 if (
CC->size() != 1 || RealToTemp.
count(Leader)) {
3941 ValueDFSStack EliminationStack;
3945 convertClassToDFSOrdered(*
CC, DFSOrderedSet, UseCounts, ProbablyDead);
3949 for (
auto &VD : DFSOrderedSet) {
3950 int MemberDFSIn = VD.
DFSIn;
3951 int MemberDFSOut = VD.
DFSOut;
3953 bool FromStore = VD.
Def.getInt();
3956 if (Def &&
Def->getType()->isVoidTy())
3958 auto *DefInst = dyn_cast_or_null<Instruction>(Def);
3959 if (DefInst && AllTempInstructions.
count(DefInst)) {
3960 auto *PN = cast<PHINode>(DefInst);
3965 AllTempInstructions.
erase(PN);
3966 auto *DefBlock = getBlockForValue(Def);
3970 PN->insertBefore(&DefBlock->front());
3972 NumGVNPHIOfOpsEliminations++;
3975 if (EliminationStack.empty()) {
3979 << EliminationStack.dfs_back().first <<
","
3980 << EliminationStack.dfs_back().second <<
")\n");
3983 LLVM_DEBUG(
dbgs() <<
"Current DFS numbers are (" << MemberDFSIn <<
","
3984 << MemberDFSOut <<
")\n");
3998 bool ShouldPush =
Def && EliminationStack.empty();
4000 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
4002 if (OutOfScope || ShouldPush) {
4004 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4005 bool ShouldPush =
Def && EliminationStack.empty();
4007 EliminationStack.push_back(Def, MemberDFSIn, MemberDFSOut);
4026 if (!EliminationStack.empty() && Def != EliminationStack.back() &&
4027 isa<Instruction>(Def) && !FromStore)
4028 markInstructionForDeletion(cast<Instruction>(Def));
4034 assert(isa<Instruction>(
U->get()) &&
4035 "Current def should have been an instruction");
4036 assert(isa<Instruction>(
U->getUser()) &&
4037 "Current user should have been an instruction");
4043 Instruction *InstUse = cast<Instruction>(
U->getUser());
4044 if (InstructionsToErase.count(InstUse)) {
4045 auto &UseCount = UseCounts[
U->get()];
4046 if (--UseCount == 0) {
4047 ProbablyDead.
insert(cast<Instruction>(
U->get()));
4053 if (EliminationStack.empty())
4056 Value *DominatingLeader = EliminationStack.back();
4058 auto *II = dyn_cast<IntrinsicInst>(DominatingLeader);
4059 bool isSSACopy = II && II->getIntrinsicID() == Intrinsic::ssa_copy;
4061 DominatingLeader = II->getOperand(0);
4064 if (
U->get() == DominatingLeader)
4067 <<
"Found replacement " << *DominatingLeader <<
" for "
4068 << *
U->get() <<
" in " << *(
U->getUser()) <<
"\n");
4073 auto *ReplacedInst = cast<Instruction>(
U->get());
4074 auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
4075 if (!PI || DominatingLeader != PI->OriginalOp)
4077 U->set(DominatingLeader);
4080 auto &LeaderUseCount = UseCounts[DominatingLeader];
4082 if (LeaderUseCount == 0 && isa<Instruction>(DominatingLeader))
4083 ProbablyDead.
erase(cast<Instruction>(DominatingLeader));
4087 unsigned &IIUseCount = UseCounts[II];
4088 if (--IIUseCount == 0)
4092 AnythingReplaced =
true;
4099 for (
auto *
I : ProbablyDead)
4101 markInstructionForDeletion(
I);
4105 for (
auto *Member : *
CC)
4106 if (!isa<Instruction>(Member) ||
4107 !InstructionsToErase.count(cast<Instruction>(Member)))
4108 MembersLeft.
insert(Member);
4109 CC->swap(MembersLeft);
4112 if (
CC->getStoreCount() > 0) {
4113 convertClassToLoadsAndStores(*
CC, PossibleDeadStores);
4115 ValueDFSStack EliminationStack;
4116 for (
auto &VD : PossibleDeadStores) {
4117 int MemberDFSIn = VD.
DFSIn;
4118 int MemberDFSOut = VD.
DFSOut;
4120 if (EliminationStack.empty() ||
4121 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) {
4123 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4124 if (EliminationStack.empty()) {
4125 EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
4130 if (isa<LoadInst>(Member))
4132 assert(!EliminationStack.empty());
4133 Instruction *Leader = cast<Instruction>(EliminationStack.back());
4138 <<
" that is dominated by " << *Leader <<
"\n");
4139 markInstructionForDeletion(Member);
4145 return AnythingReplaced;
4153unsigned int NewGVN::getRank(
const Value *V)
const {
4159 if (isa<ConstantExpr>(V))
4161 if (isa<PoisonValue>(V))
4163 if (isa<UndefValue>(V))
4165 if (isa<Constant>(V))
4167 if (
auto *
A = dyn_cast<Argument>(V))
4168 return 4 +
A->getArgNo();
4172 unsigned Result = InstrToDFSNum(V);
4174 return 5 + NumFuncArgs +
Result;
4181bool NewGVN::shouldSwapOperands(
const Value *
A,
const Value *
B)
const {
4185 return std::make_pair(getRank(
A),
A) > std::make_pair(getRank(
B),
B);
4188bool NewGVN::shouldSwapOperandsForIntrinsic(
const Value *
A,
const Value *
B,
4191 if (shouldSwapOperands(
A,
B)) {
4192 if (LookupResult == IntrinsicInstPred.
end())
4199 if (LookupResult != IntrinsicInstPred.
end()) {
4201 if (SeenPredicate) {
4202 if (SeenPredicate ==
B)
4221 NewGVN(
F, &DT, &AC, &TLI, &AA, &MSSA,
F.getParent()->getDataLayout())
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Unify divergent function exit nodes
This file defines the BumpPtrAllocator interface.
SmallVector< MachineOperand, 4 > Cond
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...
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)
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.
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.
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 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.
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
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()
void deleteValue()
Delete a pointer to a generic Value.
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.
Constant * getConstantLoadValueForLoad(Constant *SrcVal, unsigned Offset, Type *LoadTy, const DataLayout &DL)
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...
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...
Constant * getConstantStoreValueForLoad(Constant *SrcVal, unsigned Offset, Type *LoadTy, const DataLayout &DL)
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
std::vector< ExecutorAddr > LookupResult
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.
bool wouldInstructionBeTriviallyDead(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.
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.
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...
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.
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)
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