125 using namespace llvm;
130 #define DEBUG_TYPE "newgvn"
132 STATISTIC(NumGVNInstrDeleted,
"Number of instructions deleted");
133 STATISTIC(NumGVNBlocksDeleted,
"Number of blocks deleted");
134 STATISTIC(NumGVNOpsSimplified,
"Number of Expressions simplified");
135 STATISTIC(NumGVNPhisAllSame,
"Number of PHIs whos arguments are all the same");
137 "Maximum Number of iterations it took to converge GVN");
138 STATISTIC(NumGVNLeaderChanges,
"Number of leader changes");
139 STATISTIC(NumGVNSortedLeaderChanges,
"Number of sorted leader changes");
140 STATISTIC(NumGVNAvoidedSortedLeaderChanges,
141 "Number of avoided sorted leader changes");
142 STATISTIC(NumGVNDeadStores,
"Number of redundant/dead stores eliminated");
143 STATISTIC(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");
166 namespace 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 (
auto &
Op :
I->operands()) {
211 if (
auto *InstOp = dyn_cast<Instruction>(
Op)) {
212 if (Root.lookup(
Op) == 0)
214 if (!InComponent.count(
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;
295 class 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(); }
339 MemberSet::const_iterator
begin()
const {
return Members.
begin(); }
340 MemberSet::const_iterator
end()
const {
return Members.
end(); }
341 void insert(MemberType *M) { Members.insert(M); }
342 void erase(MemberType *M) { Members.erase(M); }
343 void swap(MemberSet &Other) { Members.swap(Other); }
346 bool memory_empty()
const {
return MemoryMembers.empty(); }
347 unsigned memory_size()
const {
return MemoryMembers.size(); }
348 MemoryMemberSet::const_iterator memory_begin()
const {
349 return MemoryMembers.begin();
351 MemoryMemberSet::const_iterator memory_end()
const {
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, ~0U};
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);
783 ExprResult performSymbolicEvaluation(
Value *,
790 ExprResult performSymbolicCallEvaluation(
Instruction *)
const;
796 ExprResult performSymbolicCmpEvaluation(
Instruction *)
const;
797 ExprResult performSymbolicPredicateInfoEvaluation(
IntrinsicInst *)
const;
802 CongruenceClass *getClassForExpression(
const Expression *
E)
const;
805 CongruenceClass *, CongruenceClass *);
807 CongruenceClass *, CongruenceClass *);
808 Value *getNextValueLeader(CongruenceClass *)
const;
809 const MemoryAccess *getNextMemoryLeader(CongruenceClass *)
const;
811 CongruenceClass *getMemoryClass(
const MemoryAccess *MA)
const;
816 unsigned int getRank(
const Value *)
const;
817 bool shouldSwapOperands(
const Value *,
const Value *)
const;
818 bool shouldSwapOperandsForIntrinsic(
const Value *,
const Value *,
824 Value *findConditionEquivalence(
Value *)
const;
828 void convertClassToDFSOrdered(
const CongruenceClass &,
832 void convertClassToLoadsAndStores(
const CongruenceClass &,
835 bool eliminateInstructions(
Function &);
843 template <
typename Map,
typename KeyType>
844 void touchAndErase(Map &,
const KeyType &);
845 void markUsersTouched(
Value *);
849 void markValueLeaderChangeTouched(CongruenceClass *CC);
850 void markMemoryLeaderChangeTouched(CongruenceClass *CC);
857 void iterateTouchedInstructions();
860 void cleanupTables();
861 std::pair<unsigned, unsigned> assignDFSNumbers(
BasicBlock *,
unsigned);
862 void updateProcessedCount(
const Value *V);
863 void verifyMemoryCongruency()
const;
864 void verifyIterationSettled(
Function &
F);
865 void verifyStoreExpressions()
const;
872 template <
class T,
class Range>
T *getMinDFSOfRange(
const Range &)
const;
874 unsigned InstrToDFSNum(
const Value *V)
const {
875 assert(isa<Instruction>(V) &&
"This should not be used for MemoryAccesses");
876 return InstrDFS.
lookup(V);
880 return MemoryToDFSNum(MA);
883 Value *InstrFromDFSNum(
unsigned DFSNum) {
return DFSToInstr[DFSNum]; }
888 unsigned MemoryToDFSNum(
const Value *MA)
const {
889 assert(isa<MemoryAccess>(MA) &&
890 "This should not be used with instructions");
891 return isa<MemoryUseOrDef>(MA)
892 ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst())
901 int64_t StartingVNCounter = 0;
906 template <
typename T>
908 if (!isa<LoadExpression>(
RHS) && !isa<StoreExpression>(
RHS))
910 return LHS.MemoryExpression::equals(
RHS);
921 if (
const auto *
S = dyn_cast<StoreExpression>(&
Other))
953 if (
auto *
I = dyn_cast<Instruction>(V)) {
954 auto *Parent =
I->getParent();
957 Parent = TempToBlock.
lookup(V);
958 assert(Parent &&
"Every fake instruction should have a block");
962 auto *MP = dyn_cast<MemoryPhi>(V);
963 assert(MP &&
"Should have been an instruction or a MemoryPhi");
964 return MP->getBlock();
970 void NewGVN::deleteExpression(
const Expression *
E)
const {
971 assert(isa<BasicExpression>(
E));
972 auto *BE = cast<BasicExpression>(
E);
979 if (
auto *II = dyn_cast<IntrinsicInst>(V))
980 if (II->getIntrinsicID() == Intrinsic::ssa_copy)
981 return II->getOperand(0);
992 return CO && isa<PHINode>(CO);
999 llvm::sort(Ops, [&](
const ValPair &P1,
const ValPair &
P2) {
1000 return BlockInstRange.
lookup(P1.second).first <
1001 BlockInstRange.
lookup(
P2.second).first;
1009 return isa<Constant>(V) || isa<Argument>(V);
1021 bool &OriginalOpsConstant)
const {
1022 unsigned NumOps = PHIOperands.
size();
1023 auto *
E =
new (ExpressionAllocator)
PHIExpression(NumOps, PHIBlock);
1025 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1026 E->setType(PHIOperands.
begin()->first->getType());
1027 E->setOpcode(Instruction::PHI);
1031 auto *
BB =
P.second;
1032 if (
auto *PHIOp = dyn_cast<PHINode>(
I))
1035 if (!ReachableEdges.
count({BB, PHIBlock}))
1038 if (ValueToClass.
lookup(
P.first) == TOPClass)
1040 OriginalOpsConstant = OriginalOpsConstant && isa<Constant>(
P.first);
1041 HasBackedge = HasBackedge || isBackedge(
BB, PHIBlock);
1042 return lookupOperandLeader(
P.first) !=
I;
1045 [&](
const ValPair &
P) ->
Value * {
1046 return lookupOperandLeader(
P.first);
1054 bool AllConstant =
true;
1055 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I))
1056 E->setType(
GEP->getSourceElementType());
1058 E->setType(
I->getType());
1059 E->setOpcode(
I->getOpcode());
1060 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1065 auto Operand = lookupOperandLeader(
O);
1066 AllConstant = AllConstant && isa<Constant>(Operand);
1073 const 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));
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();
1146 NewGVN::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()));
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), SQ);
1189 }
else if (
I->isBinaryOp()) {
1194 }
else if (
auto *CI = dyn_cast<CastInst>(
I)) {
1199 }
else if (
auto *GEPI = dyn_cast<GetElementPtrInst>(
I)) {
1203 GEPI->isInBounds(), SQ);
1206 }
else if (AllConstant) {
1216 C.emplace_back(cast<Constant>(
Arg));
1222 return ExprResult::some(
E);
1226 NewGVN::createAggregateValueExpression(
Instruction *
I)
const {
1227 if (
auto *II = dyn_cast<InsertValueInst>(
I)) {
1228 auto *
E =
new (ExpressionAllocator)
1230 setBasicExpressionInfo(
I,
E);
1231 E->allocateIntOperands(ExpressionAllocator);
1234 }
else if (
auto *EI = dyn_cast<ExtractValueInst>(
I)) {
1235 auto *
E =
new (ExpressionAllocator)
1237 setBasicExpressionInfo(EI,
E);
1238 E->allocateIntOperands(ExpressionAllocator);
1248 return SingletonDeadExpression;
1258 if (
auto *
C = dyn_cast<Constant>(V))
1259 return createConstantExpression(
C);
1260 return createVariableExpression(V);
1265 E->setOpcode(
C->getValueID());
1271 E->setOpcode(
I->getOpcode());
1281 setBasicExpressionInfo(CI,
E);
1286 bool NewGVN::someEquivalentDominates(
const Instruction *Inst,
1288 auto *CC = ValueToClass.
lookup(Inst);
1309 if (DT->
dominates(cast<Instruction>(CC->getLeader()), U))
1311 if (CC->getNextLeader().first &&
1312 DT->
dominates(cast<Instruction>(CC->getNextLeader().first), U))
1315 return Member != CC->getLeader() &&
1316 DT->
dominates(cast<Instruction>(Member), U);
1322 Value *NewGVN::lookupOperandLeader(
Value *V)
const {
1323 CongruenceClass *CC = ValueToClass.
lookup(V);
1330 return CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
1337 auto *CC = getMemoryClass(MA);
1338 assert(CC->getMemoryLeader() &&
1339 "Every MemoryAccess should be mapped to a congruence class with a "
1340 "representative memory access");
1341 return CC->getMemoryLeader();
1347 bool NewGVN::isMemoryAccessTOP(
const MemoryAccess *MA)
const {
1348 return getMemoryClass(MA) == TOPClass;
1355 new (ExpressionAllocator)
LoadExpression(1, LI, lookupMemoryLeader(MA));
1356 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1357 E->setType(LoadType);
1361 E->op_push_back(PointerOp);
1371 auto *StoredValueLeader = lookupOperandLeader(
SI->getValueOperand());
1372 auto *
E =
new (ExpressionAllocator)
1374 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1375 E->setType(
SI->getValueOperand()->getType());
1379 E->op_push_back(lookupOperandLeader(
SI->getPointerOperand()));
1390 auto *
SI = cast<StoreInst>(
I);
1391 auto *StoreAccess = getMemoryAccess(
SI);
1393 const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess();
1397 StoreRHS = lookupMemoryLeader(StoreRHS);
1398 if (StoreRHS != StoreAccess->getDefiningAccess())
1399 addMemoryUsers(StoreRHS, StoreAccess);
1401 if (StoreRHS == StoreAccess)
1404 if (
SI->isSimple()) {
1408 const auto *LastStore = createStoreExpression(
SI, StoreRHS);
1409 const auto *LastCC = ExpressionToClass.lookup(LastStore);
1415 if (LastCC && LastCC->getStoredValue() == LastStore->getStoredValue())
1421 if (
auto *LI = dyn_cast<LoadInst>(LastStore->getStoredValue()))
1423 LastStore->getOperand(0)) &&
1424 (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) ==
1427 deleteExpression(LastStore);
1433 return createStoreExpression(
SI, StoreAccess);
1439 NewGVN::performSymbolicLoadCoercion(
Type *LoadType,
Value *LoadPtr,
1443 if (
auto *DepSI = dyn_cast<StoreInst>(DepInst)) {
1447 if (LI->
isAtomic() > DepSI->isAtomic() ||
1448 LoadType == DepSI->getValueOperand()->getType())
1452 if (
auto *
C = dyn_cast<Constant>(
1453 lookupOperandLeader(DepSI->getValueOperand()))) {
1455 <<
" to constant " << *
C <<
"\n");
1456 return createConstantExpression(
1460 }
else if (
auto *DepLI = dyn_cast<LoadInst>(DepInst)) {
1462 if (LI->
isAtomic() > DepLI->isAtomic())
1467 if (
auto *
C = dyn_cast<Constant>(lookupOperandLeader(DepLI)))
1468 if (
auto *PossibleConstant =
1471 <<
" to constant " << *PossibleConstant <<
"\n");
1472 return createConstantExpression(PossibleConstant);
1475 }
else if (
auto *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1478 if (
auto *PossibleConstant =
1481 <<
" to constant " << *PossibleConstant <<
"\n");
1482 return createConstantExpression(PossibleConstant);
1489 if (LoadPtr != lookupOperandLeader(DepInst) &&
1490 !
AA->isMustAlias(LoadPtr, DepInst))
1496 if (isa<AllocaInst>(DepInst)) {
1501 else if (
auto *II = dyn_cast<IntrinsicInst>(DepInst)) {
1502 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1507 return createConstantExpression(InitVal);
1513 auto *LI = cast<LoadInst>(
I);
1522 if (isa<UndefValue>(LoadAddressLeader))
1529 if (
auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
1538 if (
const auto *CoercionResult =
1539 performSymbolicLoadCoercion(LI->
getType(), LoadAddressLeader, LI,
1540 DefiningInst, DefiningAccess))
1541 return CoercionResult;
1545 const auto *
LE = createLoadExpression(LI->
getType(), LoadAddressLeader, LI,
1549 if (
LE->getMemoryLeader() != DefiningAccess)
1550 addMemoryUsers(
LE->getMemoryLeader(), OriginalAccess);
1555 NewGVN::performSymbolicPredicateInfoEvaluation(
IntrinsicInst *
I)
const {
1556 auto *PI = PredInfo->getPredicateInfoFor(
I);
1558 return ExprResult::none();
1560 LLVM_DEBUG(
dbgs() <<
"Found predicate info from instruction !\n");
1564 return ExprResult::none();
1567 Value *CmpOp0 =
I->getOperand(0);
1570 Value *FirstOp = lookupOperandLeader(CmpOp0);
1571 Value *SecondOp = lookupOperandLeader(CmpOp1);
1572 Value *AdditionallyUsedValue = CmpOp0;
1575 if (shouldSwapOperandsForIntrinsic(FirstOp, SecondOp,
I)) {
1578 AdditionallyUsedValue = CmpOp1;
1582 return ExprResult::some(createVariableOrConstant(FirstOp),
1583 AdditionallyUsedValue, PI);
1587 !cast<ConstantFP>(FirstOp)->
isZero())
1588 return ExprResult::some(createConstantExpression(cast<Constant>(FirstOp)),
1589 AdditionallyUsedValue, PI);
1591 return ExprResult::none();
1595 NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(
Instruction *
I)
const {
1596 auto *CI = cast<CallInst>(
I);
1597 if (
auto *II = dyn_cast<IntrinsicInst>(
I)) {
1599 if (
auto *ReturnedValue = II->getReturnedArgOperand()) {
1600 if (II->getIntrinsicID() == Intrinsic::ssa_copy)
1601 if (
auto Res = performSymbolicPredicateInfoEvaluation(II))
1603 return ExprResult::some(createVariableOrConstant(ReturnedValue));
1606 if (
AA->doesNotAccessMemory(CI)) {
1607 return ExprResult::some(
1608 createCallExpression(CI, TOPClass->getMemoryLeader()));
1609 }
else if (
AA->onlyReadsMemory(CI)) {
1612 return ExprResult::some(createCallExpression(CI, DefiningAccess));
1614 return ExprResult::some(
1615 createCallExpression(CI, TOPClass->getMemoryLeader()));
1617 return ExprResult::none();
1621 CongruenceClass *NewGVN::getMemoryClass(
const MemoryAccess *MA)
const {
1623 assert(Result &&
"Should have found memory class");
1630 CongruenceClass *NewClass) {
1632 "Every MemoryAccess should be getting mapped to a non-null class");
1636 <<
" with current MemoryAccess leader ");
1640 bool Changed =
false;
1644 if (OldClass != NewClass) {
1646 if (
auto *MP = dyn_cast<MemoryPhi>(
From)) {
1647 OldClass->memory_erase(MP);
1648 NewClass->memory_insert(MP);
1650 if (OldClass->getMemoryLeader() ==
From) {
1651 if (OldClass->definesNoMemory()) {
1652 OldClass->setMemoryLeader(
nullptr);
1654 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
1656 << OldClass->getID() <<
" to "
1657 << *OldClass->getMemoryLeader()
1658 <<
" due to removal of a memory member " << *
From
1660 markMemoryLeaderChangeTouched(OldClass);
1683 auto ICS = InstCycleState.
lookup(
I);
1684 if (ICS == ICS_Unknown) {
1686 auto &
SCC = SCCFinder.getComponentFor(
I);
1688 if (
SCC.size() == 1)
1689 InstCycleState.
insert({
I, ICS_CycleFree});
1694 ICS = AllPhis ? ICS_CycleFree : ICS_Cycle;
1695 for (
auto *Member :
SCC)
1696 if (
auto *MemberPhi = dyn_cast<PHINode>(Member))
1697 InstCycleState.
insert({MemberPhi, ICS});
1700 if (ICS == ICS_Cycle)
1711 bool HasBackedge =
false;
1716 bool OriginalOpsConstant =
true;
1717 auto *
E = cast<PHIExpression>(createPHIExpression(
1718 PHIOps,
I, PHIBlock, HasBackedge, OriginalOpsConstant));
1722 bool HasUndef =
false, HasPoison =
false;
1724 if (isa<PoisonValue>(Arg)) {
1728 if (isa<UndefValue>(
Arg)) {
1735 if (Filtered.empty()) {
1740 dbgs() <<
"PHI Node " << *
I
1741 <<
" has no non-undef arguments, valuing it as undef\n");
1746 dbgs() <<
"PHI Node " << *
I
1747 <<
" has no non-poison arguments, valuing it as poison\n");
1751 LLVM_DEBUG(
dbgs() <<
"No arguments of PHI node " << *
I <<
" are live\n");
1752 deleteExpression(
E);
1753 return createDeadExpression();
1755 Value *AllSameValue = *(Filtered.begin());
1773 if (HasPoison || HasUndef) {
1779 if (HasBackedge && !OriginalOpsConstant &&
1780 !isa<UndefValue>(AllSameValue) && !isCycleFree(
I))
1784 if (
auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
1785 if (!someEquivalentDominates(AllSameInst,
I))
1791 if (isa<Instruction>(AllSameValue) &&
1792 InstrToDFSNum(AllSameValue) > InstrToDFSNum(
I))
1794 NumGVNPhisAllSame++;
1795 LLVM_DEBUG(
dbgs() <<
"Simplified PHI node " << *
I <<
" to " << *AllSameValue
1797 deleteExpression(
E);
1798 return createVariableOrConstant(AllSameValue);
1804 NewGVN::performSymbolicAggrValueEvaluation(
Instruction *
I)
const {
1805 if (
auto *EI = dyn_cast<ExtractValueInst>(
I)) {
1806 auto *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
1807 if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0)
1811 return createBinaryExpression(WO->getBinaryOp(), EI->getType(),
1812 WO->getLHS(), WO->getRHS(),
I);
1815 return createAggregateValueExpression(
I);
1818 NewGVN::ExprResult NewGVN::performSymbolicCmpEvaluation(
Instruction *
I)
const {
1819 assert(isa<CmpInst>(
I) &&
"Expected a cmp instruction.");
1821 auto *CI = cast<CmpInst>(
I);
1824 auto Op0 = lookupOperandLeader(CI->
getOperand(0));
1825 auto Op1 = lookupOperandLeader(CI->
getOperand(1));
1826 auto OurPredicate = CI->getPredicate();
1827 if (shouldSwapOperands(Op0, Op1)) {
1829 OurPredicate = CI->getSwappedPredicate();
1836 auto *CmpPI = PredInfo->getPredicateInfoFor(
I);
1837 if (isa_and_nonnull<PredicateAssume>(CmpPI))
1838 return ExprResult::some(
1843 if (CI->isTrueWhenEqual())
1844 return ExprResult::some(
1846 else if (CI->isFalseWhenEqual())
1847 return ExprResult::some(
1877 auto *PI = PredInfo->getPredicateInfoFor(
Op);
1878 if (
const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
1879 if (PI == LastPredInfo)
1884 if (!DT->
dominates(PBranch->To, getBlockForValue(
I)))
1891 auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
1894 auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
1895 auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
1896 auto BranchPredicate = BranchCond->getPredicate();
1897 if (shouldSwapOperands(BranchOp0, BranchOp1)) {
1899 BranchPredicate = BranchCond->getSwappedPredicate();
1901 if (BranchOp0 == Op0 && BranchOp1 == Op1) {
1902 if (PBranch->TrueEdge) {
1907 return ExprResult::some(
1914 return ExprResult::some(
1921 if (BranchPredicate == OurPredicate) {
1923 return ExprResult::some(
1926 }
else if (BranchPredicate ==
1929 return ExprResult::some(
1938 return createExpression(
I);
1943 NewGVN::performSymbolicEvaluation(
Value *V,
1947 if (
auto *
C = dyn_cast<Constant>(V))
1948 E = createConstantExpression(
C);
1949 else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
1950 E = createVariableExpression(V);
1955 auto *
I = cast<Instruction>(V);
1956 switch (
I->getOpcode()) {
1957 case Instruction::ExtractValue:
1958 case Instruction::InsertValue:
1959 E = performSymbolicAggrValueEvaluation(
I);
1961 case Instruction::PHI: {
1963 auto *PN = cast<PHINode>(
I);
1964 for (
unsigned i = 0;
i < PN->getNumOperands(); ++
i)
1965 Ops.push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)});
1968 E = performSymbolicPHIEvaluation(Ops,
I, getBlockForValue(
I));
1971 return performSymbolicCallEvaluation(
I);
1974 E = performSymbolicStoreEvaluation(
I);
1977 E = performSymbolicLoadEvaluation(
I);
1979 case Instruction::BitCast:
1980 case Instruction::AddrSpaceCast:
1981 return createExpression(
I);
1983 case Instruction::ICmp:
1984 case Instruction::FCmp:
1985 return performSymbolicCmpEvaluation(
I);
1987 case Instruction::FNeg:
1989 case Instruction::FAdd:
1990 case Instruction::Sub:
1991 case Instruction::FSub:
1993 case Instruction::FMul:
1994 case Instruction::UDiv:
1995 case Instruction::SDiv:
1996 case Instruction::FDiv:
1997 case Instruction::URem:
1998 case Instruction::SRem:
1999 case Instruction::FRem:
2000 case Instruction::Shl:
2001 case Instruction::LShr:
2002 case Instruction::AShr:
2003 case Instruction::And:
2004 case Instruction::Or:
2005 case Instruction::Xor:
2006 case Instruction::Trunc:
2007 case Instruction::ZExt:
2008 case Instruction::SExt:
2009 case Instruction::FPToUI:
2010 case Instruction::FPToSI:
2011 case Instruction::UIToFP:
2012 case Instruction::SIToFP:
2013 case Instruction::FPTrunc:
2014 case Instruction::FPExt:
2015 case Instruction::PtrToInt:
2016 case Instruction::IntToPtr:
2018 case Instruction::ExtractElement:
2019 case Instruction::InsertElement:
2020 case Instruction::GetElementPtr:
2021 return createExpression(
I);
2023 case Instruction::ShuffleVector:
2025 return ExprResult::none();
2027 return ExprResult::none();
2030 return ExprResult::some(
E);
2035 template <
typename Map,
typename KeyType>
2036 void NewGVN::touchAndErase(Map &
M,
const KeyType &
Key) {
2038 if (Result !=
M.end()) {
2039 for (
const typename Map::mapped_type::value_type Mapped :
Result->second)
2040 TouchedInstructions.
set(InstrToDFSNum(Mapped));
2047 if (isa<Instruction>(To))
2051 void NewGVN::addAdditionalUsers(ExprResult &Res,
Instruction *
User)
const {
2052 if (Res.ExtraDep && Res.ExtraDep !=
User)
2053 addAdditionalUsers(Res.ExtraDep,
User);
2054 Res.ExtraDep =
nullptr;
2057 if (
const auto *PBranch = dyn_cast<PredicateBranch>(Res.PredDep))
2058 PredicateToUsers[PBranch->Condition].
insert(
User);
2059 else if (
const auto *PAssume = dyn_cast<PredicateAssume>(Res.PredDep))
2060 PredicateToUsers[PAssume->Condition].
insert(
User);
2062 Res.PredDep =
nullptr;
2065 void NewGVN::markUsersTouched(
Value *V) {
2068 assert(isa<Instruction>(
User) &&
"Use of value not within an instruction?");
2069 TouchedInstructions.
set(InstrToDFSNum(
User));
2071 touchAndErase(AdditionalUsers, V);
2075 LLVM_DEBUG(
dbgs() <<
"Adding memory user " << *U <<
" to " << *To <<
"\n");
2076 MemoryToUsers[To].
insert(U);
2079 void NewGVN::markMemoryDefTouched(
const MemoryAccess *MA) {
2080 TouchedInstructions.
set(MemoryToDFSNum(MA));
2083 void NewGVN::markMemoryUsersTouched(
const MemoryAccess *MA) {
2084 if (isa<MemoryUse>(MA))
2086 for (
auto U : MA->
users())
2087 TouchedInstructions.
set(MemoryToDFSNum(U));
2088 touchAndErase(MemoryToUsers, MA);
2092 void NewGVN::markPredicateUsersTouched(
Instruction *
I) {
2093 touchAndErase(PredicateToUsers,
I);
2097 void NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *CC) {
2098 for (
auto M : CC->memory())
2099 markMemoryDefTouched(
M);
2104 void NewGVN::markValueLeaderChangeTouched(CongruenceClass *CC) {
2105 for (
auto M : *CC) {
2106 if (
auto *
I = dyn_cast<Instruction>(
M))
2107 TouchedInstructions.
set(InstrToDFSNum(
I));
2114 template <
class T,
class Range>
2115 T *NewGVN::getMinDFSOfRange(
const Range &
R)
const {
2116 std::pair<T *, unsigned> MinDFS = {
nullptr, ~0U};
2117 for (
const auto X :
R) {
2118 auto DFSNum = InstrToDFSNum(
X);
2119 if (DFSNum < MinDFS.second)
2120 MinDFS = {
X, DFSNum};
2122 return MinDFS.first;
2128 const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *CC)
const {
2132 assert(!CC->definesNoMemory() &&
"Can't get next leader if there is none");
2133 if (CC->getStoreCount() > 0) {
2134 if (
auto *
NL = dyn_cast_or_null<StoreInst>(CC->getNextLeader().first))
2135 return getMemoryAccess(
NL);
2138 *CC, [&](
const Value *V) {
return isa<StoreInst>(V); }));
2139 return getMemoryAccess(cast<StoreInst>(V));
2141 assert(CC->getStoreCount() == 0);
2145 if (CC->memory_size() == 1)
2146 return *CC->memory_begin();
2147 return getMinDFSOfRange<const MemoryPhi>(CC->memory());
2153 Value *NewGVN::getNextValueLeader(CongruenceClass *CC)
const {
2158 if (CC->size() == 1 || CC == TOPClass) {
2159 return *(CC->begin());
2160 }
else if (CC->getNextLeader().first) {
2161 ++NumGVNAvoidedSortedLeaderChanges;
2162 return CC->getNextLeader().first;
2164 ++NumGVNSortedLeaderChanges;
2168 return getMinDFSOfRange<Value>(*CC);
2181 void NewGVN::moveMemoryToNewCongruenceClass(
Instruction *
I,
2183 CongruenceClass *OldClass,
2184 CongruenceClass *NewClass) {
2187 assert((!InstMA || !OldClass->getMemoryLeader() ||
2188 OldClass->getLeader() !=
I ||
2189 MemoryAccessToClass.
lookup(OldClass->getMemoryLeader()) ==
2190 MemoryAccessToClass.
lookup(InstMA)) &&
2191 "Representative MemoryAccess mismatch");
2193 if (!NewClass->getMemoryLeader()) {
2195 assert(NewClass->size() == 1 ||
2196 (isa<StoreInst>(
I) && NewClass->getStoreCount() == 1));
2197 NewClass->setMemoryLeader(InstMA);
2200 << NewClass->getID()
2201 <<
" due to new memory instruction becoming leader\n");
2202 markMemoryLeaderChangeTouched(NewClass);
2204 setMemoryClass(InstMA, NewClass);
2206 if (OldClass->getMemoryLeader() == InstMA) {
2207 if (!OldClass->definesNoMemory()) {
2208 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
2210 << OldClass->getID() <<
" to "
2211 << *OldClass->getMemoryLeader()
2212 <<
" due to removal of old leader " << *InstMA <<
"\n");
2213 markMemoryLeaderChangeTouched(OldClass);
2215 OldClass->setMemoryLeader(
nullptr);
2222 CongruenceClass *OldClass,
2223 CongruenceClass *NewClass) {
2224 if (
I == OldClass->getNextLeader().first)
2225 OldClass->resetNextLeader();
2228 NewClass->insert(
I);
2230 if (NewClass->getLeader() !=
I)
2231 NewClass->addPossibleNextLeader({
I, InstrToDFSNum(
I)});
2233 if (
auto *
SI = dyn_cast<StoreInst>(
I)) {
2234 OldClass->decStoreCount();
2242 if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) {
2245 if (
auto *SE = dyn_cast<StoreExpression>(
E)) {
2246 NewClass->setStoredValue(SE->getStoredValue());
2247 markValueLeaderChangeTouched(NewClass);
2250 << NewClass->getID() <<
" from "
2251 << *NewClass->getLeader() <<
" to " << *
SI
2252 <<
" because store joined class\n");
2255 NewClass->setLeader(
SI);
2259 NewClass->incStoreCount();
2265 auto *InstMA = dyn_cast_or_null<MemoryDef>(getMemoryAccess(
I));
2267 moveMemoryToNewCongruenceClass(
I, InstMA, OldClass, NewClass);
2268 ValueToClass[
I] = NewClass;
2270 if (OldClass->empty() && OldClass != TOPClass) {
2271 if (OldClass->getDefiningExpr()) {
2272 LLVM_DEBUG(
dbgs() <<
"Erasing expression " << *OldClass->getDefiningExpr()
2273 <<
" from table\n");
2276 auto Iter = ExpressionToClass.find_as(
2278 if (Iter != ExpressionToClass.end())
2279 ExpressionToClass.erase(Iter);
2280 #ifdef EXPENSIVE_CHECKS
2282 (*OldClass->getDefiningExpr() != *
E || ExpressionToClass.lookup(
E)) &&
2283 "We erased the expression we just inserted, which should not happen");
2286 }
else if (OldClass->getLeader() ==
I) {
2291 << OldClass->getID() <<
"\n");
2292 ++NumGVNLeaderChanges;
2297 if (OldClass->getStoreCount() == 0) {
2298 if (OldClass->getStoredValue())
2299 OldClass->setStoredValue(
nullptr);
2301 OldClass->setLeader(getNextValueLeader(OldClass));
2302 OldClass->resetNextLeader();
2303 markValueLeaderChangeTouched(OldClass);
2309 void NewGVN::markPhiOfOpsChanged(
const Expression *
E) {
2310 touchAndErase(ExpressionToPhiOfOps,
E);
2318 CongruenceClass *IClass = ValueToClass.
lookup(
I);
2319 assert(IClass &&
"Should have found a IClass");
2321 assert(!IClass->isDead() &&
"Found a dead class");
2323 CongruenceClass *EClass =
nullptr;
2324 if (
const auto *VE = dyn_cast<VariableExpression>(
E)) {
2325 EClass = ValueToClass.
lookup(VE->getVariableValue());
2326 }
else if (isa<DeadExpression>(
E)) {
2330 auto lookupResult = ExpressionToClass.insert({
E,
nullptr});
2333 if (lookupResult.second) {
2334 CongruenceClass *NewClass = createCongruenceClass(
nullptr,
E);
2335 auto place = lookupResult.first;
2336 place->second = NewClass;
2339 if (
const auto *CE = dyn_cast<ConstantExpression>(
E)) {
2340 NewClass->setLeader(
CE->getConstantValue());
2341 }
else if (
const auto *SE = dyn_cast<StoreExpression>(
E)) {
2343 NewClass->setLeader(
SI);
2344 NewClass->setStoredValue(SE->getStoredValue());
2348 NewClass->setLeader(
I);
2350 assert(!isa<VariableExpression>(
E) &&
2351 "VariableExpression should have been handled already");
2355 <<
" using expression " << *
E <<
" at "
2356 << NewClass->getID() <<
" and leader "
2357 << *(NewClass->getLeader()));
2358 if (NewClass->getStoredValue())
2360 << *(NewClass->getStoredValue()));
2363 EClass = lookupResult.first->second;
2364 if (isa<ConstantExpression>(
E))
2365 assert((isa<Constant>(EClass->getLeader()) ||
2366 (EClass->getStoredValue() &&
2367 isa<Constant>(EClass->getStoredValue()))) &&
2368 "Any class with a constant expression should have a "
2371 assert(EClass &&
"Somehow don't have an eclass");
2373 assert(!EClass->isDead() &&
"We accidentally looked up a dead class");
2376 bool ClassChanged = IClass != EClass;
2377 bool LeaderChanged = LeaderChanges.
erase(
I);
2378 if (ClassChanged || LeaderChanged) {
2379 LLVM_DEBUG(
dbgs() <<
"New class " << EClass->getID() <<
" for expression "
2382 moveValueToNewCongruenceClass(
I,
E, IClass, EClass);
2383 markPhiOfOpsChanged(
E);
2386 markUsersTouched(
I);
2388 markMemoryUsersTouched(MA);
2389 if (
auto *CI = dyn_cast<CmpInst>(
I))
2390 markPredicateUsersTouched(CI);
2396 if (ClassChanged && isa<StoreInst>(
I)) {
2397 auto *OldE = ValueToExpression.
lookup(
I);
2400 if (OldE && isa<StoreExpression>(OldE) && *
E != *OldE) {
2404 if (Iter != ExpressionToClass.end())
2405 ExpressionToClass.erase(Iter);
2408 ValueToExpression[
I] =
E;
2415 if (ReachableEdges.
insert({From, To}).second) {
2417 if (ReachableBlocks.
insert(To).second) {
2419 <<
" marked reachable\n");
2420 const auto &InstRange = BlockInstRange.
lookup(To);
2421 TouchedInstructions.
set(InstRange.first, InstRange.second);
2424 <<
" was reachable, but new edge {"
2426 <<
"} to it found\n");
2433 TouchedInstructions.
set(InstrToDFSNum(MemPhi));
2438 for (
auto InstNum : RevisitOnReachabilityChange[To])
2439 TouchedInstructions.
set(InstNum);
2448 return isa<Constant>(Result) ?
Result :
nullptr;
2457 Value *CondEvaluated = findConditionEquivalence(
Cond);
2458 if (!CondEvaluated) {
2459 if (
auto *
I = dyn_cast<Instruction>(
Cond)) {
2461 auto Res = performSymbolicEvaluation(
I, Visited);
2462 if (
const auto *CE = dyn_cast_or_null<ConstantExpression>(Res.Expr)) {
2463 CondEvaluated =
CE->getConstantValue();
2464 addAdditionalUsers(Res,
I);
2468 Res.ExtraDep =
nullptr;
2470 }
else if (isa<ConstantInt>(
Cond)) {
2471 CondEvaluated =
Cond;
2475 if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
2478 <<
" evaluated to true\n");
2479 updateReachableEdge(
B, TrueSucc);
2480 }
else if (CI->
isZero()) {
2482 <<
" evaluated to false\n");
2483 updateReachableEdge(
B, FalseSucc);
2486 updateReachableEdge(
B, TrueSucc);
2487 updateReachableEdge(
B, FalseSucc);
2489 }
else if (
auto *
SI = dyn_cast<SwitchInst>(TI)) {
2493 Value *SwitchCond =
SI->getCondition();
2494 Value *CondEvaluated = findConditionEquivalence(SwitchCond);
2496 if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
2497 auto *CondVal = cast<ConstantInt>(CondEvaluated);
2499 auto Case = *
SI->findCaseValue(CondVal);
2500 if (Case.getCaseSuccessor() ==
SI->getDefaultDest()) {
2504 updateReachableEdge(
B,
SI->getDefaultDest());
2508 BasicBlock *TargetBlock = Case.getCaseSuccessor();
2509 updateReachableEdge(
B, TargetBlock);
2511 for (
unsigned i = 0,
e =
SI->getNumSuccessors();
i !=
e; ++
i) {
2513 updateReachableEdge(
B, TargetBlock);
2521 updateReachableEdge(
B, TargetBlock);
2527 auto *MA = getMemoryAccess(TI);
2528 if (MA && !isa<MemoryUse>(MA)) {
2529 auto *CC = ensureLeaderOfMemoryClass(MA);
2530 if (setMemoryClass(MA, CC))
2531 markMemoryUsersTouched(MA);
2538 InstrDFS.
erase(PHITemp);
2541 TempToBlock.
erase(PHITemp);
2552 InstrDFS[
Op] = InstrToDFSNum(ExistingValue);
2554 TempToBlock[
Op] =
BB;
2555 RealToTemp[ExistingValue] =
Op;
2558 for (
auto *U : ExistingValue->
users())
2559 if (
auto *UI = dyn_cast<Instruction>(U))
2566 return isa<BinaryOperator>(
I) || isa<SelectInst>(
I) || isa<CmpInst>(
I) ||
2570 bool NewGVN::OpIsSafeForPHIOfOpsHelper(
2575 if (!isa<Instruction>(V))
2577 auto OISIt = OpSafeForPHIOfOps.
find(V);
2578 if (OISIt != OpSafeForPHIOfOps.
end())
2579 return OISIt->second;
2584 OpSafeForPHIOfOps.
insert({V,
true});
2588 if (isa<PHINode>(V) && getBlockForValue(V) == PHIBlock) {
2589 OpSafeForPHIOfOps.
insert({V,
false});
2593 auto *OrigI = cast<Instruction>(V);
2600 if (OrigI->mayReadFromMemory())
2603 for (
auto *
Op : OrigI->operand_values()) {
2604 if (!isa<Instruction>(
Op))
2607 auto OISIt = OpSafeForPHIOfOps.
find(OrigI);
2608 if (OISIt != OpSafeForPHIOfOps.
end()) {
2609 if (!OISIt->second) {
2610 OpSafeForPHIOfOps.
insert({V,
false});
2617 Worklist.push_back(cast<Instruction>(
Op));
2629 bool NewGVN::OpIsSafeForPHIOfOps(
Value *V,
const BasicBlock *PHIBlock,
2632 if (!OpIsSafeForPHIOfOpsHelper(V, PHIBlock, Visited, Worklist))
2634 while (!Worklist.empty()) {
2636 if (!OpIsSafeForPHIOfOpsHelper(
I, PHIBlock, Visited, Worklist))
2639 OpSafeForPHIOfOps.
insert({V,
true});
2652 unsigned IDFSNum = InstrToDFSNum(OrigInst);
2654 AllTempInstructions.
insert(TransInst);
2658 TempToBlock.
insert({TransInst, PredBB});
2659 InstrDFS.
insert({TransInst, IDFSNum});
2661 auto Res = performSymbolicEvaluation(TransInst, Visited);
2663 addAdditionalUsers(Res, OrigInst);
2664 InstrDFS.
erase(TransInst);
2665 AllTempInstructions.
erase(TransInst);
2666 TempToBlock.
erase(TransInst);
2668 TempToMemory.
erase(TransInst);
2671 auto *FoundVal = findPHIOfOpsLeader(
E, OrigInst, PredBB);
2673 ExpressionToPhiOfOps[
E].
insert(OrigInst);
2674 LLVM_DEBUG(
dbgs() <<
"Cannot find phi of ops operand for " << *TransInst
2678 if (
auto *
SI = dyn_cast<StoreInst>(FoundVal))
2679 FoundVal =
SI->getValueOperand();
2691 if (!Visited.
insert(
I).second)
2697 if (!isCycleFree(
I))
2704 auto *MemAccess = getMemoryAccess(
I);
2708 if (MemAccess && !isa<MemoryPhi>(MemAccess->getDefiningAccess()) &&
2709 MemAccess->getDefiningAccess()->
getBlock() ==
I->getParent())
2719 for (
auto *
Op : Ops) {
2720 if (!isa<PHINode>(
Op)) {
2721 auto *ValuePHI = RealToTemp.
lookup(
Op);
2727 OpPHI = cast<PHINode>(
Op);
2728 if (!SamePHIBlock) {
2729 SamePHIBlock = getBlockForValue(OpPHI);
2730 }
else if (SamePHIBlock != getBlockForValue(OpPHI)) {
2733 <<
"PHIs for operands are not all in the same block, aborting\n");
2748 auto *PHIBlock = getBlockForValue(OpPHI);
2749 RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(
I));
2750 for (
unsigned PredNum = 0; PredNum < OpPHI->
getNumOperands(); ++PredNum) {
2752 Value *FoundVal =
nullptr;
2756 if (ReachableEdges.
count({PredBB, PHIBlock})) {
2761 TempToMemory.
insert({ValueOp, MemAccess});
2762 bool SafeForPHIOfOps =
true;
2765 auto *OrigOp = &*
Op;
2768 if (isa<PHINode>(
Op)) {
2769 Op =
Op->DoPHITranslation(PHIBlock, PredBB);
2770 if (
Op != OrigOp &&
Op !=
I)
2772 }
else if (
auto *ValuePHI = RealToTemp.
lookup(
Op)) {
2773 if (getBlockForValue(ValuePHI) == PHIBlock)
2774 Op = ValuePHI->getIncomingValueForBlock(PredBB);
2779 (
Op != OrigOp || OpIsSafeForPHIOfOps(
Op, PHIBlock, VisitedOps));
2786 FoundVal = !SafeForPHIOfOps ? nullptr
2787 : findLeaderForInst(ValueOp, Visited,
2788 MemAccess,
I, PredBB);
2793 if (SafeForPHIOfOps)
2794 for (
auto Dep : CurrentDeps)
2795 addAdditionalUsers(Dep,
I);
2801 LLVM_DEBUG(
dbgs() <<
"Skipping phi of ops operand for incoming block "
2803 <<
" because the block is unreachable\n");
2805 RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(
I));
2808 PHIOps.push_back({FoundVal, PredBB});
2809 LLVM_DEBUG(
dbgs() <<
"Found phi of ops operand " << *FoundVal <<
" in "
2812 for (
auto Dep : Deps)
2813 addAdditionalUsers(Dep,
I);
2815 auto *
E = performSymbolicPHIEvaluation(PHIOps,
I, PHIBlock);
2816 if (isa<ConstantExpression>(
E) || isa<VariableExpression>(
E)) {
2819 <<
"Not creating real PHI of ops because it simplified to existing "
2820 "value or constant\n");
2826 for (
auto &
O : PHIOps)
2827 addAdditionalUsers(
O.first,
I);
2831 auto *ValuePHI = RealToTemp.
lookup(
I);
2832 bool NewPHI =
false;
2836 addPhiOfOps(ValuePHI, PHIBlock,
I);
2838 NumGVNPHIOfOpsCreated++;
2841 for (
auto PHIOp : PHIOps)
2842 ValuePHI->addIncoming(PHIOp.first, PHIOp.second);
2844 TempToBlock[ValuePHI] = PHIBlock;
2846 for (
auto PHIOp : PHIOps) {
2847 ValuePHI->setIncomingValue(
i, PHIOp.first);
2848 ValuePHI->setIncomingBlock(
i, PHIOp.second);
2852 RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(
I));
2853 LLVM_DEBUG(
dbgs() <<
"Created phi of ops " << *ValuePHI <<
" for " << *
I
2862 void NewGVN::initializeCongruenceClasses(
Function &
F) {
2863 NextCongruenceNum = 0;
2873 TOPClass = createCongruenceClass(
nullptr,
nullptr);
2879 for (
auto DTN :
nodes(DT)) {
2886 if (MemoryBlockDefs)
2887 for (
const auto &
Def : *MemoryBlockDefs) {
2888 MemoryAccessToClass[&
Def] = TOPClass;
2889 auto *MD = dyn_cast<MemoryDef>(&
Def);
2893 TOPClass->memory_insert(MP);
2894 MemoryPhiState.
insert({MP, MPS_TOP});
2897 if (MD && isa<StoreInst>(MD->getMemoryInst()))
2898 TOPClass->incStoreCount();
2904 for (
auto &
I : *
BB) {
2905 if (isa<PHINode>(&
I))
2906 for (
auto *U :
I.users())
2907 if (
auto *UInst = dyn_cast<Instruction>(U))
2909 PHINodeUses.
insert(UInst);
2912 if (
I.isTerminator() &&
I.getType()->isVoidTy())
2914 TOPClass->insert(&
I);
2915 ValueToClass[&
I] = TOPClass;
2920 for (
auto &FA :
F.args())
2921 createSingletonCongruenceClass(&FA);
2924 void NewGVN::cleanupTables() {
2925 for (
unsigned i = 0,
e = CongruenceClasses.size();
i !=
e; ++
i) {
2926 LLVM_DEBUG(
dbgs() <<
"Congruence class " << CongruenceClasses[
i]->getID()
2927 <<
" has " << CongruenceClasses[
i]->
size()
2931 delete CongruenceClasses[
i];
2932 CongruenceClasses[
i] =
nullptr;
2937 AllTempInstructions.
end());
2938 AllTempInstructions.
clear();
2942 for (
auto *
I : TempInst) {
2943 I->dropAllReferences();
2946 while (!TempInst.empty()) {
2947 auto *
I = TempInst.pop_back_val();
2951 ValueToClass.
clear();
2952 ArgRecycler.
clear(ExpressionAllocator);
2953 ExpressionAllocator.
Reset();
2954 CongruenceClasses.clear();
2955 ExpressionToClass.clear();
2956 ValueToExpression.
clear();
2958 AdditionalUsers.
clear();
2959 ExpressionToPhiOfOps.
clear();
2960 TempToBlock.
clear();
2961 TempToMemory.
clear();
2962 PHINodeUses.
clear();
2963 OpSafeForPHIOfOps.
clear();
2964 ReachableBlocks.
clear();
2965 ReachableEdges.
clear();
2967 ProcessedCount.
clear();
2970 InstructionsToErase.
clear();
2972 BlockInstRange.
clear();
2973 TouchedInstructions.
clear();
2974 MemoryAccessToClass.
clear();
2975 PredicateToUsers.
clear();
2976 MemoryToUsers.
clear();
2977 RevisitOnReachabilityChange.
clear();
2978 IntrinsicInstPred.
clear();
2983 std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(
BasicBlock *
B,
2985 unsigned End = Start;
2987 InstrDFS[MemPhi] = End++;
2992 for (
auto &
I : *
B) {
2998 LLVM_DEBUG(
dbgs() <<
"Skipping trivially dead instruction " <<
I <<
"\n");
2999 markInstructionForDeletion(&
I);
3002 if (isa<PHINode>(&
I))
3003 RevisitOnReachabilityChange[
B].set(End);
3004 InstrDFS[&
I] = End++;
3011 return std::make_pair(Start, End);
3014 void NewGVN::updateProcessedCount(
const Value *V) {
3016 if (ProcessedCount.
count(V) == 0) {
3017 ProcessedCount.
insert({V, 1});
3019 ++ProcessedCount[V];
3020 assert(ProcessedCount[V] < 100 &&
3021 "Seem to have processed the same Value a lot");
3027 void NewGVN::valueNumberMemoryPhi(
MemoryPhi *MP) {
3034 return cast<MemoryAccess>(U) != MP &&
3035 !isMemoryAccessTOP(cast<MemoryAccess>(U)) &&
3036 ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock});
3041 if (Filtered.begin() == Filtered.end()) {
3042 if (setMemoryClass(MP, TOPClass))
3043 markMemoryUsersTouched(MP);
3049 auto LookupFunc = [&](
const Use &U) {
3050 return lookupMemoryLeader(cast<MemoryAccess>(U));
3052 auto MappedBegin =
map_iterator(Filtered.begin(), LookupFunc);
3053 auto MappedEnd =
map_iterator(Filtered.end(), LookupFunc);
3057 const auto *AllSameValue = *MappedBegin;
3060 MappedBegin, MappedEnd,
3061 [&AllSameValue](
const MemoryAccess *V) {
return V == AllSameValue; });
3064 LLVM_DEBUG(
dbgs() <<
"Memory Phi value numbered to " << *AllSameValue
3073 CongruenceClass *CC =
3074 AllEqual ? getMemoryClass(AllSameValue) : ensureLeaderOfMemoryClass(MP);
3075 auto OldState = MemoryPhiState.
lookup(MP);
3076 assert(OldState != MPS_Invalid &&
"Invalid memory phi state");
3077 auto NewState = AllEqual ? MPS_Equivalent : MPS_Unique;
3078 MemoryPhiState[MP] = NewState;
3079 if (setMemoryClass(MP, CC) || OldState != NewState)
3080 markMemoryUsersTouched(MP);
3087 if (!
I->isTerminator()) {
3091 auto Res = performSymbolicEvaluation(
I, Visited);
3092 Symbolized = Res.Expr;
3093 addAdditionalUsers(Res,
I);
3096 if (Symbolized && !isa<ConstantExpression>(Symbolized) &&
3097 !isa<VariableExpression>(Symbolized) && PHINodeUses.
count(
I)) {
3098 auto *PHIE = makePossiblePHIOfOps(
I, Visited);
3103 }
else if (
auto *
Op = RealToTemp.
lookup(
I)) {
3104 removePhiOfOps(
I,
Op);
3113 if (Symbolized ==
nullptr)
3114 Symbolized = createUnknownExpression(
I);
3115 performCongruenceFinding(
I, Symbolized);
3120 if (!
I->getType()->isVoidTy()) {
3121 auto *Symbolized = createUnknownExpression(
I);
3122 performCongruenceFinding(
I, Symbolized);
3124 processOutgoingEdges(
I,
I->getParent());
3130 bool NewGVN::singleReachablePHIPath(
3133 if (
First == Second)
3147 const auto *EndDef =
First;
3149 if (ChainDef == Second)
3155 auto *MP = cast<MemoryPhi>(EndDef);
3156 auto ReachableOperandPred = [&](
const Use &U) {
3159 auto FilteredPhiArgs =
3162 llvm::copy(FilteredPhiArgs, std::back_inserter(OperandList));
3165 return singleReachablePHIPath(Visited, cast<MemoryAccess>(OperandList[0]),
3174 void NewGVN::verifyMemoryCongruency()
const {
3177 for (
const auto *CC : CongruenceClasses) {
3178 if (CC == TOPClass || CC->isDead())
3180 if (CC->getStoreCount() != 0) {
3181 assert((CC->getStoredValue() || !isa<StoreInst>(CC->getLeader())) &&
3182 "Any class with a store as a leader should have a "
3183 "representative stored value");
3184 assert(CC->getMemoryLeader() &&
3185 "Any congruence class with a store should have a "
3186 "representative access");
3189 if (CC->getMemoryLeader())
3190 assert(MemoryAccessToClass.
lookup(CC->getMemoryLeader()) == CC &&
3191 "Representative MemoryAccess does not appear to be reverse "
3193 for (
auto M : CC->memory())
3195 "Memory member does not appear to be reverse mapped properly");
3203 auto ReachableAccessPred =
3204 [&](
const std::pair<const MemoryAccess *, CongruenceClass *> Pair) {
3205 bool Result = ReachableBlocks.
count(Pair.first->getBlock());
3207 MemoryToDFSNum(Pair.first) == 0)
3209 if (
auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
3214 if (
auto *MemPHI = dyn_cast<MemoryPhi>(Pair.first)) {
3215 for (
auto &U : MemPHI->incoming_values()) {
3216 if (
auto *
I = dyn_cast<Instruction>(&*U)) {
3228 for (
auto KV : Filtered) {
3229 if (
auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
3230 auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second->getMemoryLeader());
3231 if (FirstMUD && SecondMUD) {
3233 assert((singleReachablePHIPath(VisitedMAS, FirstMUD, SecondMUD) ||
3234 ValueToClass.
lookup(FirstMUD->getMemoryInst()) ==
3235 ValueToClass.
lookup(SecondMUD->getMemoryInst())) &&
3236 "The instructions for these memory operations should have "
3237 "been in the same congruence class or reachable through"
3238 "a single argument phi");
3240 }
else if (
auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {
3243 auto ReachableOperandPred = [&](
const Use &U) {
3244 return ReachableEdges.
count(
3245 {FirstMP->getIncomingBlock(U), FirstMP->getBlock()}) &&
3250 auto FilteredPhiArgs =
3254 std::back_inserter(PhiOpClasses), [&](
const Use &U) {
3255 const MemoryDef *MD = cast<MemoryDef>(U);
3256 return ValueToClass.lookup(MD->getMemoryInst());
3259 "All MemoryPhi arguments should be in the same class");
3268 void NewGVN::verifyIterationSettled(
Function &
F) {
3278 std::map<const Value *, CongruenceClass> BeforeIteration;
3280 for (
auto &KV : ValueToClass) {
3281 if (
auto *
I = dyn_cast<Instruction>(KV.first))
3283 if (InstrToDFSNum(
I) == 0)
3285 BeforeIteration.insert({KV.first, *KV.second});
3288 TouchedInstructions.
set();
3289 TouchedInstructions.
reset(0);
3290 iterateTouchedInstructions();
3293 for (
const auto &KV : ValueToClass) {
3294 if (
auto *
I = dyn_cast<Instruction>(KV.first))
3296 if (InstrToDFSNum(
I) == 0)
3300 auto *BeforeCC = &BeforeIteration.
find(KV.first)->second;
3301 auto *AfterCC = KV.second;
3304 if (!EqualClasses.
count({BeforeCC, AfterCC})) {
3305 assert(BeforeCC->isEquivalentTo(AfterCC) &&
3306 "Value number changed after main loop completed!");
3307 EqualClasses.
insert({BeforeCC, AfterCC});
3318 void NewGVN::verifyStoreExpressions()
const {
3323 std::pair<
const Value *,
3324 std::tuple<const Value *, const CongruenceClass *, Value *>>>
3326 for (
const auto &KV : ExpressionToClass) {
3327 if (
auto *SE = dyn_cast<StoreExpression>(KV.first)) {
3329 auto Res = StoreExpressionSet.insert(
3330 {SE->getOperand(0), std::make_tuple(SE->getMemoryLeader(), KV.second,
3331 SE->getStoredValue())});
3332 bool Okay = Res.second;
3337 Okay = (std::get<1>(Res.first->second) == KV.second) &&
3338 (lookupOperandLeader(std::get<2>(Res.first->second)) ==
3339 lookupOperandLeader(SE->getStoredValue()));
3340 assert(Okay &&
"Stored expression conflict exists in expression table");
3341 auto *ValueExpr = ValueToExpression.
lookup(SE->getStoreInst());
3342 assert(ValueExpr && ValueExpr->equals(*SE) &&
3343 "StoreExpression in ExpressionToClass is not latest "
3344 "StoreExpression for value");
3353 void NewGVN::iterateTouchedInstructions() {
3354 unsigned int Iterations = 0;
3356 int FirstInstr = TouchedInstructions.
find_first();
3358 if (FirstInstr == -1)
3360 const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
3361 while (TouchedInstructions.
any()) {
3367 for (
unsigned InstrNum : TouchedInstructions.
set_bits()) {
3371 if (InstrNum == 0) {
3372 TouchedInstructions.
reset(InstrNum);
3376 Value *V = InstrFromDFSNum(InstrNum);
3377 const BasicBlock *CurrBlock = getBlockForValue(V);
3380 if (CurrBlock != LastBlock) {
3381 LastBlock = CurrBlock;
3382 bool BlockReachable = ReachableBlocks.
count(CurrBlock);
3383 const auto &CurrInstRange = BlockInstRange.
lookup(CurrBlock);
3386 if (!BlockReachable) {
3387 TouchedInstructions.
reset(CurrInstRange.first, CurrInstRange.second);
3390 <<
" because it is unreachable\n");
3393 updateProcessedCount(CurrBlock);
3397 TouchedInstructions.
reset(InstrNum);
3399 if (
auto *MP = dyn_cast<MemoryPhi>(V)) {
3401 valueNumberMemoryPhi(MP);
3402 }
else if (
auto *
I = dyn_cast<Instruction>(V)) {
3403 valueNumberInstruction(
I);
3407 updateProcessedCount(V);
3410 NumGVNMaxIterations =
std::max(NumGVNMaxIterations.getValue(), Iterations);
3414 bool NewGVN::runGVN() {
3417 bool Changed =
false;
3418 NumFuncArgs =
F.arg_size();
3420 SingletonDeadExpression =
new (ExpressionAllocator)
DeadExpression();
3424 unsigned ICount = 1;
3436 unsigned Counter = 0;
3437 for (
auto &
B : RPOT) {
3439 assert(Node &&
"RPO and Dominator tree should have same reachability");
3440 RPOOrdering[Node] = ++Counter;
3443 for (
auto &
B : RPOT) {
3445 if (Node->getNumChildren() > 1)
3447 return RPOOrdering[
A] < RPOOrdering[
B];
3454 const auto &BlockRange = assignDFSNumbers(
B, ICount);
3455 BlockInstRange.
insert({
B, BlockRange});
3456 ICount += BlockRange.second - BlockRange.first;
3458 initializeCongruenceClasses(
F);
3460 TouchedInstructions.
resize(ICount);
3464 ExpressionToClass.reserve(ICount);
3467 const auto &InstRange = BlockInstRange.
lookup(&
F.getEntryBlock());
3468 TouchedInstructions.
set(InstRange.first, InstRange.second);
3470 <<
" marked reachable\n");
3471 ReachableBlocks.
insert(&
F.getEntryBlock());
3473 iterateTouchedInstructions();
3474 verifyMemoryCongruency();
3475 verifyIterationSettled(
F);
3476 verifyStoreExpressions();
3478 Changed |= eliminateInstructions(
F);
3481 for (
Instruction *ToErase : InstructionsToErase) {
3482 if (!ToErase->use_empty())
3485 assert(ToErase->getParent() &&
3486 "BB containing ToErase deleted unexpectedly!");
3487 ToErase->eraseFromParent();
3489 Changed |= !InstructionsToErase.empty();
3492 auto UnreachableBlockPred = [&](
const BasicBlock &
BB) {
3493 return !ReachableBlocks.
count(&
BB);
3498 <<
" is unreachable\n");
3499 deleteInstructionsInBlock(&
BB);
3557 return std::tie(DFSIn, DFSOut,
LocalNum,
Def, U) <
3568 void NewGVN::convertClassToDFSOrdered(
3572 for (
auto D : Dense) {
3577 assert(
BB &&
"Should have figured out a basic block for value");
3585 if (
auto *
SI = dyn_cast<StoreInst>(
D)) {
3586 auto Leader = lookupOperandLeader(
SI->getValueOperand());
3588 VDDef.
Def.setPointer(Leader);
3590 VDDef.
Def.setPointer(
SI->getValueOperand());
3591 VDDef.
Def.setInt(
true);
3594 VDDef.
Def.setPointer(
D);
3597 "The dense set member should always be an instruction");
3600 DFSOrderedSet.push_back(VDDef);
3602 if (
auto *PN = RealToTemp.
lookup(
Def)) {
3604 dyn_cast_or_null<PHIExpression>(ValueToExpression.
lookup(
Def));
3606 VDDef.
Def.setInt(
false);
3607 VDDef.
Def.setPointer(PN);
3609 DFSOrderedSet.push_back(VDDef);
3613 unsigned int UseCount = 0;
3615 for (
auto &U :
Def->uses()) {
3616 if (
auto *
I = dyn_cast<Instruction>(U.getUser())) {
3618 if (InstructionsToErase.count(
I))
3623 if (
auto *
P = dyn_cast<PHINode>(
I)) {
3624 IBlock =
P->getIncomingBlock(U);
3629 IBlock = getBlockForValue(
I);
3635 if (!ReachableBlocks.
contains(IBlock))
3653 UseCounts[
Def] = UseCount;
3659 void NewGVN::convertClassToLoadsAndStores(
3660 const CongruenceClass &Dense,
3662 for (
auto D : Dense) {
3663 if (!isa<LoadInst>(
D) && !isa<StoreInst>(
D))
3671 VD.
Def.setPointer(
D);
3674 if (
auto *
I = dyn_cast<Instruction>(
D))
3685 I->replaceAllUsesWith(Repl);
3688 void NewGVN::deleteInstructionsInBlock(
BasicBlock *
BB) {
3690 ++NumGVNBlocksDeleted;
3694 auto StartPoint =
BB->rbegin();
3702 if (isa<LandingPadInst>(Inst))
3707 ++NumGVNInstrDeleted;
3713 BB->getTerminator());
3716 void NewGVN::markInstructionForDeletion(
Instruction *
I) {
3718 InstructionsToErase.insert(
I);
3726 markInstructionForDeletion(
I);
3733 class ValueDFSStack {
3735 Value *back()
const {
return ValueStack.back(); }
3736 std::pair<int, int> dfs_back()
const {
return DFSStack.back(); }
3738 void push_back(
Value *V,
int DFSIn,
int DFSOut) {
3739 ValueStack.emplace_back(V);
3740 DFSStack.emplace_back(DFSIn, DFSOut);
3743 bool empty()
const {
return DFSStack.empty(); }
3745 bool isInScope(
int DFSIn,
int DFSOut)
const {
3748 return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
3751 void popUntilDFSScope(
int DFSIn,
int DFSOut) {
3754 assert(ValueStack.size() == DFSStack.size() &&
3755 "Mismatch between ValueStack and DFSStack");
3757 !DFSStack.empty() &&
3758 !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
3759 DFSStack.pop_back();
3760 ValueStack.pop_back();
3772 CongruenceClass *NewGVN::getClassForExpression(
const Expression *
E)
const {
3773 if (
auto *VE = dyn_cast<VariableExpression>(
E))
3774 return ValueToClass.lookup(VE->getVariableValue());
3775 else if (isa<DeadExpression>(
E))
3777 return ExpressionToClass.lookup(
E);
3786 if (
auto *CE = dyn_cast<ConstantExpression>(
E))
3787 return CE->getConstantValue();
3788 if (
auto *VE = dyn_cast<VariableExpression>(
E)) {
3789 auto *V = VE->getVariableValue();
3791 return VE->getVariableValue();
3794 auto *CC = getClassForExpression(
E);
3798 return CC->getLeader();
3800 for (
auto Member : *CC) {
3801 auto *MemberInst = dyn_cast<Instruction>(Member);
3802 if (MemberInst == OrigInst)
3807 if (DT->
dominates(getBlockForValue(MemberInst),
BB))
3813 bool NewGVN::eliminateInstructions(
Function &
F) {
3837 bool AnythingReplaced =
false;
3847 if (!ReachableEdges.
count({PHI->getIncomingBlock(Operand), BB})) {
3851 <<
" with poison due to it being unreachable\n");
3865 for (
auto &KV : ReachableEdges)
3866 ReachablePredCount[KV.getEnd()]++;
3867 for (
auto &BBPair : RevisitOnReachabilityChange) {
3868 for (
auto InstNum : BBPair.second) {
3869 auto *Inst = InstrFromDFSNum(InstNum);
3870 auto *PHI = dyn_cast<PHINode>(Inst);
3871 PHI = PHI ? PHI : dyn_cast_or_null<PHINode>(RealToTemp.
lookup(Inst));
3874 auto *
BB = BBPair.first;
3876 ReplaceUnreachablePHIArgs(PHI,
BB);
3882 for (
auto *CC :
reverse(CongruenceClasses)) {
3883 LLVM_DEBUG(
dbgs() <<
"Eliminating in congruence class " << CC->getID()
3889 if (CC->isDead() || CC->empty())
3892 if (CC == TOPClass) {
3893 for (
auto M : *CC) {
3894 auto *VTE = ValueToExpression.
lookup(M);
3895 if (VTE && isa<DeadExpression>(VTE))
3896 markInstructionForDeletion(cast<Instruction>(M));
3897 assert((!ReachableBlocks.
count(cast<Instruction>(M)->getParent()) ||
3898 InstructionsToErase.count(cast<Instruction>(M))) &&
3899 "Everything in TOP should be unreachable or dead at this "
3905 assert(CC->getLeader() &&
"We should have had a leader");
3911 CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
3914 for (
auto M : *CC) {
3917 if (Member == Leader || !isa<Instruction>(Member) ||
3918 Member->getType()->isVoidTy()) {
3919 MembersLeft.
insert(Member);
3922 LLVM_DEBUG(
dbgs() <<
"Found replacement " << *(Leader) <<
" for "
3923 << *Member <<
"\n");
3924 auto *
I = cast<Instruction>(Member);
3925 assert(Leader !=
I &&
"About to accidentally remove our leader");
3926 replaceInstruction(
I, Leader);
3927 AnythingReplaced =
true;
3929 CC->swap(MembersLeft);
3932 if (CC->size() != 1 || RealToTemp.
count(Leader)) {
3937 ValueDFSStack EliminationStack;
3941 convertClassToDFSOrdered(*CC, DFSOrderedSet, UseCounts, ProbablyDead);
3945 for (
auto &VD : DFSOrderedSet) {
3946 int MemberDFSIn = VD.
DFSIn;
3947 int MemberDFSOut = VD.
DFSOut;
3949 bool FromStore = VD.
Def.getInt();
3952 if (
Def &&
Def->getType()->isVoidTy())
3954 auto *DefInst = dyn_cast_or_null<Instruction>(
Def);
3955 if (DefInst && AllTempInstructions.
count(DefInst)) {
3956 auto *PN = cast<PHINode>(DefInst);
3961 AllTempInstructions.
erase(PN);
3962 auto *DefBlock = getBlockForValue(
Def);
3966 PN->insertBefore(&DefBlock->front());
3968 NumGVNPHIOfOpsEliminations++;
3971 if (EliminationStack.empty()) {
3975 << EliminationStack.dfs_back().first <<
","
3976 << EliminationStack.dfs_back().second <<
")\n");
3979 LLVM_DEBUG(
dbgs() <<
"Current DFS numbers are (" << MemberDFSIn <<
","
3980 << MemberDFSOut <<
")\n");
3994 bool ShouldPush =
Def && EliminationStack.empty();
3996 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
3998 if (OutOfScope || ShouldPush) {
4000 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4001 bool ShouldPush =
Def && EliminationStack.empty();
4003 EliminationStack.push_back(
Def, MemberDFSIn, MemberDFSOut);
4022 if (!EliminationStack.empty() &&
Def != EliminationStack.back() &&
4023 isa<Instruction>(
Def) && !FromStore)
4024 markInstructionForDeletion(cast<Instruction>(
Def));
4030 assert(isa<Instruction>(U->get()) &&
4031 "Current def should have been an instruction");
4032 assert(isa<Instruction>(U->getUser()) &&
4033 "Current user should have been an instruction");
4039 Instruction *InstUse = cast<Instruction>(U->getUser());
4040 if (InstructionsToErase.count(InstUse)) {
4041 auto &UseCount = UseCounts[U->get()];
4042 if (--UseCount == 0) {
4043 ProbablyDead.
insert(cast<Instruction>(U->get()));
4049 if (EliminationStack.empty())
4052 Value *DominatingLeader = EliminationStack.back();
4054 auto *II = dyn_cast<IntrinsicInst>(DominatingLeader);
4055 bool isSSACopy = II && II->getIntrinsicID() == Intrinsic::ssa_copy;
4057 DominatingLeader = II->getOperand(0);
4060 if (U->get() == DominatingLeader)
4063 <<
"Found replacement " << *DominatingLeader <<
" for "
4064 << *U->get() <<
" in " << *(U->getUser()) <<
"\n");
4069 auto *ReplacedInst = cast<Instruction>(U->get());
4070 auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
4071 if (!PI || DominatingLeader != PI->OriginalOp)
4073 U->set(DominatingLeader);
4076 auto &LeaderUseCount = UseCounts[DominatingLeader];
4078 if (LeaderUseCount == 0 && isa<Instruction>(DominatingLeader))
4079 ProbablyDead.
erase(cast<Instruction>(DominatingLeader));
4083 unsigned &IIUseCount = UseCounts[II];
4084 if (--IIUseCount == 0)
4088 AnythingReplaced =
true;
4095 for (
auto *
I : ProbablyDead)
4097 markInstructionForDeletion(
I);
4101 for (
auto *Member : *CC)
4102 if (!isa<Instruction>(Member) ||
4103 !InstructionsToErase.count(cast<Instruction>(Member)))
4104 MembersLeft.
insert(Member);
4105 CC->swap(MembersLeft);
4108 if (CC->getStoreCount() > 0) {
4109 convertClassToLoadsAndStores(*CC, PossibleDeadStores);
4111 ValueDFSStack EliminationStack;
4112 for (
auto &VD : PossibleDeadStores) {
4113 int MemberDFSIn = VD.
DFSIn;
4114 int MemberDFSOut = VD.
DFSOut;
4116 if (EliminationStack.empty() ||
4117 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) {
4119 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4120 if (EliminationStack.empty()) {
4121 EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
4126 if (isa<LoadInst>(Member))
4128 assert(!EliminationStack.empty());
4129 Instruction *Leader = cast<Instruction>(EliminationStack.back());
4134 <<
" that is dominated by " << *Leader <<
"\n");
4135 markInstructionForDeletion(Member);
4141 return AnythingReplaced;
4149 unsigned int NewGVN::getRank(
const Value *V)
const {
4155 if (isa<ConstantExpr>(V))
4157 if (isa<PoisonValue>(V))
4159 if (isa<UndefValue>(V))
4161 if (isa<Constant>(V))
4163 if (
auto *A = dyn_cast<Argument>(V))
4164 return 4 +
A->getArgNo();
4168 unsigned Result = InstrToDFSNum(V);
4170 return 5 + NumFuncArgs +
Result;
4177 bool NewGVN::shouldSwapOperands(
const Value *A,
const Value *
B)
const {
4181 return std::make_pair(getRank(A), A) > std::make_pair(getRank(
B),
B);
4184 bool NewGVN::shouldSwapOperandsForIntrinsic(
const Value *A,
const Value *
B,
4187 if (shouldSwapOperands(A,
B)) {
4197 if (SeenPredicate) {
4198 if (SeenPredicate ==
B)
4235 if (skipFunction(
F))
4237 return NewGVN(
F, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
4238 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F),
4239 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F),
4240 &getAnalysis<AAResultsWrapperPass>().getAAResults(),
4241 &getAnalysis<MemorySSAWrapperPass>().getMSSA(),
4242 F.getParent()->getDataLayout())
4272 NewGVN(
F, &DT, &AC, &TLI, &
AA, &MSSA,
F.getParent()->getDataLayout())