LLVM: lib/Transforms/Scalar/NewGVN.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
111#include
112#include
113#include
114#include
115#include
116#include
117#include
118#include
119#include
120#include
121#include
122
123using namespace llvm;
127
128#define DEBUG_TYPE "newgvn"
129
130STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted");
131STATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted");
132STATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified");
133STATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same");
135 "Maximum Number of iterations it took to converge GVN");
136STATISTIC(NumGVNLeaderChanges, "Number of leader changes");
137STATISTIC(NumGVNSortedLeaderChanges, "Number of sorted leader changes");
139 "Number of avoided sorted leader changes");
140STATISTIC(NumGVNDeadStores, "Number of redundant/dead stores eliminated");
141STATISTIC(NumGVNPHIOfOpsCreated, "Number of PHI of ops created");
143 "Number of things eliminated using PHI of ops");
145 "Controls which instructions are value numbered");
147 "Controls which instructions we create phi of ops for");
148
149
150
153
154
157
158
159
160
161
162
170
171namespace {
172
173
174
175
176
177
178
179
180
181struct TarjanSCC {
182 TarjanSCC() : Components(1) {}
183
184 void Start(const Instruction *Start) {
185 if (Root.lookup(Start) == 0)
186 FindSCC(Start);
187 }
188
189 const SmallPtrSetImpl<const Value *> &getComponentFor(const Value *V) const {
190 unsigned ComponentID = ValueToComponent.lookup(V);
191
192 assert(ComponentID > 0 &&
193 "Asking for a component for a value we never processed");
194 return Components[ComponentID];
195 }
196
197private:
198 void FindSCC(const Instruction *I) {
199 Root[I] = ++DFSNum;
200
201 unsigned int OurDFS = DFSNum;
202 for (const auto &Op : I->operands()) {
204 if (Root.lookup(Op) == 0)
205 FindSCC(InstOp);
206 if (!InComponent.count(Op))
207 Root[I] = std::min(Root.lookup(I), Root.lookup(Op));
208 }
209 }
210
211
212
213
214 if (Root.lookup(I) == OurDFS) {
215 unsigned ComponentID = Components.size();
216 Components.resize(Components.size() + 1);
217 auto &Component = Components.back();
219 LLVM_DEBUG(dbgs() << "Component root is " << *I << "\n");
220 InComponent.insert(I);
221 ValueToComponent[I] = ComponentID;
222
223 while (!Stack.empty() && Root.lookup(Stack.back()) >= OurDFS) {
224 auto *Member = Stack.back();
225 LLVM_DEBUG(dbgs() << "Component member is " << *Member << "\n");
227 InComponent.insert(Member);
228 ValueToComponent[Member] = ComponentID;
229 Stack.pop_back();
230 }
231 } else {
232
233 Stack.push_back(I);
234 }
235 }
236
237 unsigned int DFSNum = 1;
238 SmallPtrSet<const Value *, 8> InComponent;
239 DenseMap<const Value *, unsigned int> Root;
240 SmallVector<const Value *, 8> Stack;
241
242
243
245
246 DenseMap<const Value *, unsigned> ValueToComponent;
247};
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287class CongruenceClass {
288public:
289 using MemberType = Value;
290 using MemberSet = SmallPtrSet<MemberType *, 4>;
291 using MemoryMemberType = MemoryPhi;
292 using MemoryMemberSet = SmallPtrSet<const MemoryMemberType *, 2>;
293
294 explicit CongruenceClass(unsigned ID) : ID(ID) {}
295 CongruenceClass(unsigned ID, std::pair<Value *, unsigned int> Leader,
296 const Expression *E)
297 : ID(ID), RepLeader(Leader), DefiningExpr(E) {}
298
299 unsigned getID() const { return ID; }
300
301
302
303 bool isDead() const {
304
305
306 return empty() && memory_empty();
307 }
308
309
310 Value *getLeader() const { return RepLeader.first; }
311 void setLeader(std::pair<Value *, unsigned int> Leader) {
312 RepLeader = Leader;
313 }
314 const std::pair<Value *, unsigned int> &getNextLeader() const {
315 return NextLeader;
316 }
317 void resetNextLeader() { NextLeader = {nullptr, ~0}; }
318 bool addPossibleLeader(std::pair<Value *, unsigned int> LeaderPair) {
319 if (LeaderPair.second < RepLeader.second) {
320 NextLeader = RepLeader;
321 RepLeader = LeaderPair;
322 return true;
323 } else if (LeaderPair.second < NextLeader.second) {
324 NextLeader = LeaderPair;
325 }
326 return false;
327 }
328
330 void setStoredValue(Value *Leader) { RepStoredValue = Leader; }
331 const MemoryAccess *getMemoryLeader() const { return RepMemoryAccess; }
332 void setMemoryLeader(const MemoryAccess *Leader) { RepMemoryAccess = Leader; }
333
334
335 const Expression *getDefiningExpr() const { return DefiningExpr; }
336
337
338 bool empty() const { return Members.empty(); }
339 unsigned size() const { return Members.size(); }
342 void insert(MemberType *M) { Members.insert(M); }
343 void erase(MemberType *M) { Members.erase(M); }
345
346
347 bool memory_empty() const { return MemoryMembers.empty(); }
348 unsigned memory_size() const { return MemoryMembers.size(); }
350 return MemoryMembers.begin();
351 }
353 return MemoryMembers.end();
354 }
356 return make_range(memory_begin(), memory_end());
357 }
358
359 void memory_insert(const MemoryMemberType *M) { MemoryMembers.insert(M); }
360 void memory_erase(const MemoryMemberType *M) { MemoryMembers.erase(M); }
361
362
363 unsigned getStoreCount() const { return StoreCount; }
364 void incStoreCount() { ++StoreCount; }
365 void decStoreCount() {
366 assert(StoreCount != 0 && "Store count went negative");
367 --StoreCount;
368 }
369
370
371 bool definesNoMemory() const { return StoreCount == 0 && memory_empty(); }
372
373
374
375 bool isEquivalentTo(const CongruenceClass *Other) const {
377 return false;
378 if (this == Other)
379 return true;
380
381 if (std::tie(StoreCount, RepLeader, RepStoredValue, RepMemoryAccess) !=
382 std::tie(Other->StoreCount, Other->RepLeader, Other->RepStoredValue,
383 Other->RepMemoryAccess))
384 return false;
385 if (DefiningExpr != Other->DefiningExpr)
386 if (!DefiningExpr || ->DefiningExpr ||
387 *DefiningExpr != *Other->DefiningExpr)
388 return false;
389
390 if (Members.size() != Other->Members.size())
391 return false;
392
394 }
395
396private:
397 unsigned ID;
398
399
400
401 std::pair<Value *, unsigned int> RepLeader = {nullptr, ~0U};
402
403
404
405
406 std::pair<Value *, unsigned int> NextLeader = {nullptr, ~0U};
407
408
409 Value *RepStoredValue = nullptr;
410
411
412
413 const MemoryAccess *RepMemoryAccess = nullptr;
414
415
416 const Expression *DefiningExpr = nullptr;
417
418
419 MemberSet Members;
420
421
422
423
424 MemoryMemberSet MemoryMembers;
425
426
427
428 int StoreCount = 0;
429};
430
431struct ExactEqualsExpression {
432 const Expression &E;
433
434 explicit ExactEqualsExpression(const Expression &E) : E(E) {}
435
436 hash_code getComputedHash() const { return E.getComputedHash(); }
437
439 return E.exactlyEquals(Other);
440 }
441};
442}
443
446 auto Val = static_cast<uintptr_t>(-1);
447 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
448 return reinterpret_cast<const Expression *>(Val);
449 }
450
452 auto Val = static_cast<uintptr_t>(~1U);
453 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
454 return reinterpret_cast<const Expression *>(Val);
455 }
456
458 return E->getComputedHash();
459 }
460
461 static unsigned getHashValue(const ExactEqualsExpression &E) {
462 return E.getComputedHash();
463 }
464
465 static bool isEqual(const ExactEqualsExpression &LHS, const Expression *RHS) {
467 return false;
468 return LHS == *RHS;
469 }
470
472 if (LHS == RHS)
473 return true;
476 return false;
477
478
479
480
481 if (LHS->getComputedHash() != RHS->getComputedHash())
482 return false;
483 return *LHS == *RHS;
484 }
485};
486
487namespace {
488
489class NewGVN {
498
499
500
503 mutable TarjanSCC SCCFinder;
504
505 std::unique_ptr PredInfo;
507
508
509 unsigned int NumFuncArgs = 0;
510
511
513
514
515
516
517
518
519
520 CongruenceClass *TOPClass = nullptr;
521 std::vector<CongruenceClass *> CongruenceClasses;
522 unsigned NextCongruenceNum = 0;
523
524
527
528
529
530
531
533
534
535
536
538 unsigned CacheIdx;
539
540
542
543
544
546
547
548
549
550
551
552
553
554
557 ExpressionToPhiOfOps;
558
559
561
562
563
564
565
567
568
569
570
571
572
573
574
576
577
578
579
580
582 PredicateToUsers;
583
584
585
587 MemoryToUsers;
588
589
590
591
592
593
595
596
597
598
599
600
601
602
603
604
605
606 enum MemoryPhiState { MPS_Invalid, MPS_TOP, MPS_Equivalent, MPS_Unique };
607 DenseMap<const MemoryPhi *, MemoryPhiState> MemoryPhiState;
608
609 enum InstCycleState { ICS_Unknown, ICS_CycleFree, ICS_Cycle };
610 mutable DenseMap<const Instruction *, InstCycleState> InstCycleState;
611
612
613 using ExpressionClassMap = DenseMap<const Expression *, CongruenceClass *>;
614 ExpressionClassMap ExpressionToClass;
615
616
617
618
619
620
621 DeadExpression *SingletonDeadExpression = nullptr;
622
623
624 SmallPtrSet<Value *, 8> LeaderChanges;
625
626
627 using BlockEdge = BasicBlockEdge;
628 DenseSet ReachableEdges;
629 SmallPtrSet<const BasicBlock *, 8> ReachableBlocks;
630
631
632
633
634
635
636
637
638
639
640 BitVector TouchedInstructions;
641
642 DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;
643 mutable DenseMap<const BitCastInst *, const Value *> PredicateSwapChoice;
644
645#ifndef NDEBUG
646
647 DenseMap<const Value *, unsigned> ProcessedCount;
648#endif
649
650
651
652
653
654 DenseMap<const Value *, unsigned> InstrDFS;
655
656
658
659
660 SmallPtrSet<Instruction *, 8> InstructionsToErase;
661
662public:
663 NewGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
665 const DataLayout &DL)
666 : F(F), DT(DT), TLI(TLI), AA(AA), MSSA(MSSA), AC(AC), DL(DL),
667
668 PredInfo(
669 std::make_unique(F, *DT, *AC, ExpressionAllocator)),
670 SQ(DL, TLI, DT, AC, nullptr, false,
671 false) {}
672
673 bool runGVN();
674
675private:
676
677 struct ExprResult {
678 const Expression *Expr;
680 const PredicateBase *PredDep;
681
682 ExprResult(const Expression *Expr, Value *ExtraDep = nullptr,
683 const PredicateBase *PredDep = nullptr)
684 : Expr(Expr), ExtraDep(ExtraDep), PredDep(PredDep) {}
685 ExprResult(const ExprResult &) = delete;
686 ExprResult(ExprResult &&Other)
687 : Expr(Other.Expr), ExtraDep(Other.ExtraDep), PredDep(Other.PredDep) {
688 Other.Expr = nullptr;
689 Other.ExtraDep = nullptr;
690 Other.PredDep = nullptr;
691 }
692 ExprResult &operator=(const ExprResult &Other) = delete;
693 ExprResult &operator=(ExprResult &&Other) = delete;
694
695 ~ExprResult() { assert(!ExtraDep && "unhandled ExtraDep"); }
696
697 operator bool() const { return Expr; }
698
699 static ExprResult none() { return {nullptr, nullptr, nullptr}; }
700 static ExprResult some(const Expression *Expr, Value *ExtraDep = nullptr) {
701 return {Expr, ExtraDep, nullptr};
702 }
703 static ExprResult some(const Expression *Expr,
704 const PredicateBase *PredDep) {
705 return {Expr, nullptr, PredDep};
706 }
707 static ExprResult some(const Expression *Expr, Value *ExtraDep,
708 const PredicateBase *PredDep) {
709 return {Expr, ExtraDep, PredDep};
710 }
711 };
712
713
714 ExprResult createExpression(Instruction *) const;
715 const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *,
716 Instruction *) const;
717
718
719
720 using ValPair = std::pair<Value *, BasicBlock *>;
721
722 PHIExpression *createPHIExpression(ArrayRef, const Instruction *,
723 BasicBlock *, bool &HasBackEdge,
724 bool &OriginalOpsConstant) const;
725 const DeadExpression *createDeadExpression() const;
726 const VariableExpression *createVariableExpression(Value *) const;
727 const ConstantExpression *createConstantExpression(Constant *) const;
728 const Expression *createVariableOrConstant(Value *V) const;
729 const UnknownExpression *createUnknownExpression(Instruction *) const;
730 const StoreExpression *createStoreExpression(StoreInst *,
731 const MemoryAccess *) const;
732 LoadExpression *createLoadExpression(Type *, Value *, LoadInst *,
733 const MemoryAccess *) const;
734 const CallExpression *createCallExpression(CallInst *,
735 const MemoryAccess *) const;
736 const AggregateValueExpression *
737 createAggregateValueExpression(Instruction *) const;
738 bool setBasicExpressionInfo(Instruction *, BasicExpression *) const;
739
740
741 CongruenceClass *createCongruenceClass(Value *Leader, const Expression *E) {
742
743
744 unsigned LeaderDFS = 0;
745
746
747
748
749 if (!Leader)
750 LeaderDFS = ~0;
752 LeaderDFS = InstrToDFSNum(I);
753 auto *result =
754 new CongruenceClass(NextCongruenceNum++, {Leader, LeaderDFS}, E);
755 CongruenceClasses.emplace_back(result);
756 return result;
757 }
758
759 CongruenceClass *createMemoryClass(MemoryAccess *MA) {
760 auto *CC = createCongruenceClass(nullptr, nullptr);
761 CC->setMemoryLeader(MA);
762 return CC;
763 }
764
765 CongruenceClass *ensureLeaderOfMemoryClass(MemoryAccess *MA) {
766 auto *CC = getMemoryClass(MA);
767 if (CC->getMemoryLeader() != MA)
768 CC = createMemoryClass(MA);
769 return CC;
770 }
771
772 CongruenceClass *createSingletonCongruenceClass(Value *Member) {
773 CongruenceClass *CClass = createCongruenceClass(Member, nullptr);
774 CClass->insert(Member);
775 ValueToClass[Member] = CClass;
776 return CClass;
777 }
778
779 void initializeCongruenceClasses(Function &F);
780 const Expression *makePossiblePHIOfOps(Instruction *,
781 SmallPtrSetImpl<Value *> &);
782 Value *findLeaderForInst(Instruction *ValueOp,
783 SmallPtrSetImpl<Value *> &Visited,
784 MemoryAccess *MemAccess, Instruction *OrigInst,
785 BasicBlock *PredBB);
786 bool OpIsSafeForPHIOfOps(Value *Op, const BasicBlock *PHIBlock,
787 SmallPtrSetImpl<const Value *> &);
788 void addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue);
789 void removePhiOfOps(Instruction *I, PHINode *PHITemp);
790
791
792 void valueNumberMemoryPhi(MemoryPhi *);
793 void valueNumberInstruction(Instruction *);
794
795
796 ExprResult checkExprResults(Expression *, Instruction *, Value *) const;
797 ExprResult performSymbolicEvaluation(Instruction *,
798 SmallPtrSetImpl<Value *> &) const;
799 const Expression *performSymbolicLoadCoercion(Type *, Value *, LoadInst *,
800 Instruction *,
801 MemoryAccess *) const;
802 const Expression *performSymbolicLoadEvaluation(Instruction *) const;
803 const Expression *performSymbolicStoreEvaluation(Instruction *) const;
804 ExprResult performSymbolicCallEvaluation(Instruction *) const;
806 const Expression *performSymbolicPHIEvaluation(ArrayRef,
807 Instruction *I,
808 BasicBlock *PHIBlock) const;
809 const Expression *performSymbolicAggrValueEvaluation(Instruction *) const;
810 ExprResult performSymbolicCmpEvaluation(Instruction *) const;
811 ExprResult performSymbolicPredicateInfoEvaluation(BitCastInst *) const;
812
813
814 bool someEquivalentDominates(const Instruction *, const Instruction *) const;
815 Value *lookupOperandLeader(Value *) const;
816 CongruenceClass *getClassForExpression(const Expression *E) const;
817 void performCongruenceFinding(Instruction *, const Expression *);
818 void moveValueToNewCongruenceClass(Instruction *, const Expression *,
819 CongruenceClass *, CongruenceClass *);
820 void moveMemoryToNewCongruenceClass(Instruction *, MemoryAccess *,
821 CongruenceClass *, CongruenceClass *);
822 Value *getNextValueLeader(CongruenceClass *) const;
823 const MemoryAccess *getNextMemoryLeader(CongruenceClass *) const;
824 bool setMemoryClass(const MemoryAccess *From, CongruenceClass *To);
825 CongruenceClass *getMemoryClass(const MemoryAccess *MA) const;
826 const MemoryAccess *lookupMemoryLeader(const MemoryAccess *) const;
827 bool isMemoryAccessTOP(const MemoryAccess *) const;
828
829
830 unsigned int getRank(const Value *) const;
831 bool shouldSwapOperands(const Value *, const Value *) const;
832 bool shouldSwapOperandsForPredicate(const Value *, const Value *,
833 const BitCastInst *I) const;
834
835
836 void updateReachableEdge(BasicBlock *, BasicBlock *);
837 void processOutgoingEdges(Instruction *, BasicBlock *);
838 Value *findConditionEquivalence(Value *) const;
839
840
841 struct ValueDFS;
842 void convertClassToDFSOrdered(const CongruenceClass &,
843 SmallVectorImpl &,
844 DenseMap<const Value *, unsigned int> &,
845 SmallPtrSetImpl<Instruction *> &) const;
846 void convertClassToLoadsAndStores(const CongruenceClass &,
847 SmallVectorImpl &) const;
848
849 bool eliminateInstructions(Function &);
850 void replaceInstruction(Instruction *, Value *);
851 void markInstructionForDeletion(Instruction *);
852 void deleteInstructionsInBlock(BasicBlock *);
853 Value *findPHIOfOpsLeader(const Expression *, const Instruction *,
854 const BasicBlock *) const;
855
856
857 template <typename Map, typename KeyType>
858 void touchAndErase(Map &, const KeyType &);
859 void markUsersTouched(Value *);
860 void markMemoryUsersTouched(const MemoryAccess *);
861 void markMemoryDefTouched(const MemoryAccess *);
862 void markPredicateUsersTouched(Instruction *);
863 void markValueLeaderChangeTouched(CongruenceClass *CC);
864 void markMemoryLeaderChangeTouched(CongruenceClass *CC);
865 void markPhiOfOpsChanged(const Expression *E);
866 void addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const;
867 void addAdditionalUsers(Value *To, Value *User) const;
868 void addAdditionalUsers(ExprResult &Res, Instruction *User) const;
869
870
871 void iterateTouchedInstructions();
872
873
874 void cleanupTables();
875 std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
876 void updateProcessedCount(const Value *V);
877 void verifyMemoryCongruency() const;
878 void verifyIterationSettled(Function &F);
879 void verifyStoreExpressions() const;
880 bool singleReachablePHIPath(SmallPtrSet<const MemoryAccess *, 8> &,
881 const MemoryAccess *, const MemoryAccess *) const;
883 void deleteExpression(const Expression *E) const;
884 MemoryUseOrDef *getMemoryAccess(const Instruction *) const;
885 MemoryPhi *getMemoryAccess(const BasicBlock *) const;
886 template <class T, class Range> T *getMinDFSOfRange(const Range &) const;
887
888 unsigned InstrToDFSNum(const Value *V) const {
890 return InstrDFS.lookup(V);
891 }
892
893 unsigned InstrToDFSNum(const MemoryAccess *MA) const {
894 return MemoryToDFSNum(MA);
895 }
896
897 Value *InstrFromDFSNum(unsigned DFSNum) { return DFSToInstr[DFSNum]; }
898
899
900
901
902 unsigned MemoryToDFSNum(const Value *MA) const {
904 "This should not be used with instructions");
907 : InstrDFS.lookup(MA);
908 }
909
910 bool isCycleFree(const Instruction *) const;
911 bool isBackedge(BasicBlock *From, BasicBlock *To) const;
912
913
914
915 DebugCounter::CounterState StartingVNCounter;
916};
917
918}
919
920template
923 return false;
924 return LHS.MemoryExpression::equals(RHS);
925}
926
930
933 return false;
934
937 return false;
938 return true;
939}
940
943 return false;
944
946 return Call->getAttributes()
947 .intersectWith(Call->getContext(), RHS->Call->getAttributes())
948 .has_value();
949
950 return false;
951}
952
953
955 return From == To ||
958}
959
960#ifndef NDEBUG
964#endif
965
966
967MemoryUseOrDef *NewGVN::getMemoryAccess(const Instruction *I) const {
970}
971
972
973MemoryPhi *NewGVN::getMemoryAccess(const BasicBlock *BB) const {
975}
976
977
980 auto *Parent = I->getParent();
981 if (Parent)
982 return Parent;
983 Parent = TempToBlock.lookup(V);
984 assert(Parent && "Every fake instruction should have a block");
985 return Parent;
986 }
987
989 assert(MP && "Should have been an instruction or a MemoryPhi");
990 return MP->getBlock();
991}
992
993
994
995
996void NewGVN::deleteExpression(const Expression *E) const {
999 const_cast<BasicExpression *>(BE)->deallocateOperands(ArgRecycler);
1000 ExpressionAllocator.Deallocate(E);
1001}
1002
1003
1006 if (BC->getType() == BC->getOperand(0)->getType())
1007 return BC->getOperand(0);
1008 return nullptr;
1009}
1010
1011
1013 return V == PN || getCopyOf(V) == PN;
1014}
1015
1020
1021
1022
1023
1025 llvm::sort(Ops, [&](const ValPair &P1, const ValPair &P2) {
1026 return BlockInstRange.lookup(P1.second).first <
1027 BlockInstRange.lookup(P2.second).first;
1028 });
1029}
1030
1031
1032
1033
1037
1038
1039
1040
1041
1042
1044 const Instruction *I,
1045 BasicBlock *PHIBlock,
1046 bool &HasBackedge,
1047 bool &OriginalOpsConstant) const {
1048 unsigned NumOps = PHIOperands.size();
1050
1052 E->setType(PHIOperands.begin()->first->getType());
1053 E->setOpcode(Instruction::PHI);
1054
1055
1056 auto Filtered = make_filter_range(PHIOperands, [&](const ValPair &P) {
1057 auto *BB = P.second;
1060 return false;
1061 if (!ReachableEdges.count({BB, PHIBlock}))
1062 return false;
1063
1064 if (ValueToClass.lookup(P.first) == TOPClass)
1065 return false;
1066 OriginalOpsConstant = OriginalOpsConstant && isa(P.first);
1067 HasBackedge = HasBackedge || isBackedge(BB, PHIBlock);
1068 return lookupOperandLeader(P.first) != I;
1069 });
1071 return lookupOperandLeader(P.first);
1072 });
1073 return E;
1074}
1075
1076
1077
1078bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E) const {
1079 bool AllConstant = true;
1081 E->setType(GEP->getSourceElementType());
1082 else
1083 E->setType(I->getType());
1084 E->setOpcode(I->getOpcode());
1085 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1086
1087
1088
1089 std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) {
1090 auto Operand = lookupOperandLeader(O);
1091 AllConstant = AllConstant && isa(Operand);
1092 return Operand;
1093 });
1094
1095 return AllConstant;
1096}
1097
1098const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
1100 Instruction *I) const {
1102
1103
1105
1107 E->setOpcode(Opcode);
1108 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1110
1111
1112
1113
1114 if (shouldSwapOperands(Arg1, Arg2))
1116 }
1117 E->op_push_back(lookupOperandLeader(Arg1));
1118 E->op_push_back(lookupOperandLeader(Arg2));
1119
1121 if (auto Simplified = checkExprResults(E, I, V)) {
1122 addAdditionalUsers(Simplified, I);
1124 }
1125 return E;
1126}
1127
1128
1129
1130
1131NewGVN::ExprResult NewGVN::checkExprResults(Expression *E, Instruction *I,
1132 Value *V) const {
1133 if (!V)
1134 return ExprResult::none();
1135
1137 if (I)
1139 << " constant " << *C << "\n");
1140 NumGVNOpsSimplified++;
1142 "We should always have had a basic expression here");
1143 deleteExpression(E);
1144 return ExprResult::some(createConstantExpression(C));
1146 if (I)
1148 << " variable " << *V << "\n");
1149 deleteExpression(E);
1150 return ExprResult::some(createVariableExpression(V));
1151 }
1152
1153 CongruenceClass *CC = ValueToClass.lookup(V);
1154 if (CC) {
1155 if (CC->getLeader() && CC->getLeader() != I) {
1156 return ExprResult::some(createVariableOrConstant(CC->getLeader()), V);
1157 }
1158 if (CC->getDefiningExpr()) {
1159 if (I)
1161 << " expression " << *CC->getDefiningExpr() << "\n");
1162 NumGVNOpsSimplified++;
1163 deleteExpression(E);
1164 return ExprResult::some(CC->getDefiningExpr(), V);
1165 }
1166 }
1167
1168 return ExprResult::none();
1169}
1170
1171
1172
1173
1174NewGVN::ExprResult NewGVN::createExpression(Instruction *I) const {
1175 auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands());
1176
1177
1179
1180 bool AllConstant = setBasicExpressionInfo(I, E);
1181
1182 if (I->isCommutative()) {
1183
1184
1185
1186
1187 assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
1188 if (shouldSwapOperands(E->getOperand(0), E->getOperand(1)))
1189 E->swapOperands(0, 1);
1190 }
1191
1193
1194
1196 if (shouldSwapOperands(E->getOperand(0), E->getOperand(1))) {
1197 E->swapOperands(0, 1);
1199 }
1200 E->setOpcode((CI->getOpcode() << 8) | Predicate);
1201
1202 assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
1203 "Wrong types on cmp instruction");
1204 assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
1205 E->getOperand(1)->getType() == I->getOperand(1)->getType()));
1207 simplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), Q);
1208 if (auto Simplified = checkExprResults(E, I, V))
1212 E->getOperand(1) == E->getOperand(2)) {
1213 assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
1214 E->getOperand(2)->getType() == I->getOperand(2)->getType());
1216 E->getOperand(2), Q);
1217 if (auto Simplified = checkExprResults(E, I, V))
1219 }
1220 } else if (I->isBinaryOp()) {
1222 simplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), Q);
1223 if (auto Simplified = checkExprResults(E, I, V))
1227 simplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), Q);
1228 if (auto Simplified = checkExprResults(E, I, V))
1232 ArrayRef(std::next(E->op_begin()), E->op_end()),
1233 GEPI->getNoWrapFlags(), Q);
1234 if (auto Simplified = checkExprResults(E, I, V))
1236 } else if (AllConstant) {
1237
1238
1239
1240
1241
1242
1243
1245 for (Value *Arg : E->operands())
1247
1249 if (auto Simplified = checkExprResults(E, I, V))
1251 }
1252 return ExprResult::some(E);
1253}
1254
1256NewGVN::createAggregateValueExpression(Instruction *I) const {
1258 auto *E = new (ExpressionAllocator)
1260 setBasicExpressionInfo(I, E);
1261 E->allocateIntOperands(ExpressionAllocator);
1263 return E;
1265 auto *E = new (ExpressionAllocator)
1267 setBasicExpressionInfo(EI, E);
1268 E->allocateIntOperands(ExpressionAllocator);
1270 return E;
1271 }
1272 llvm_unreachable("Unhandled type of aggregate value operation");
1273}
1274
1275const DeadExpression *NewGVN::createDeadExpression() const {
1276
1277
1278 return SingletonDeadExpression;
1279}
1280
1284 return E;
1285}
1286
1287const Expression *NewGVN::createVariableOrConstant(Value *V) const {
1289 return createConstantExpression(C);
1290 return createVariableExpression(V);
1291}
1292
1293const ConstantExpression *NewGVN::createConstantExpression(Constant *C) const {
1296 return E;
1297}
1298
1299const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) const {
1302 return E;
1303}
1304
1306NewGVN::createCallExpression(CallInst *CI, const MemoryAccess *MA) const {
1307
1308 auto *E =
1310 setBasicExpressionInfo(CI, E);
1312
1313
1314
1316 if (shouldSwapOperands(E->getOperand(0), E->getOperand(1)))
1317 E->swapOperands(0, 1);
1318 }
1319 return E;
1320}
1321
1322
1323bool NewGVN::someEquivalentDominates(const Instruction *Inst,
1324 const Instruction *U) const {
1325 auto *CC = ValueToClass.lookup(Inst);
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342 if (!CC)
1343 return false;
1345 return true;
1347 return true;
1348 if (CC->getNextLeader().first &&
1350 return true;
1352 return Member != CC->getLeader() &&
1354 });
1355}
1356
1357
1358
1359Value *NewGVN::lookupOperandLeader(Value *V) const {
1360 CongruenceClass *CC = ValueToClass.lookup(V);
1361 if (CC) {
1362
1363
1364
1365 if (CC == TOPClass)
1367 return CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
1368 }
1369
1370 return V;
1371}
1372
1373const MemoryAccess *NewGVN::lookupMemoryLeader(const MemoryAccess *MA) const {
1374 auto *CC = getMemoryClass(MA);
1375 assert(CC->getMemoryLeader() &&
1376 "Every MemoryAccess should be mapped to a congruence class with a "
1377 "representative memory access");
1378 return CC->getMemoryLeader();
1379}
1380
1381
1382
1383
1384bool NewGVN::isMemoryAccessTOP(const MemoryAccess *MA) const {
1385 return getMemoryClass(MA) == TOPClass;
1386}
1387
1389 LoadInst *LI,
1390 const MemoryAccess *MA) const {
1391 auto *E =
1392 new (ExpressionAllocator) LoadExpression(1, LI, lookupMemoryLeader(MA));
1394 E->setType(LoadType);
1395
1396
1397 E->setOpcode(0);
1398 E->op_push_back(PointerOp);
1399
1400
1401
1402
1403 return E;
1404}
1405
1407NewGVN::createStoreExpression(StoreInst *SI, const MemoryAccess *MA) const {
1408 auto *StoredValueLeader = lookupOperandLeader(SI->getValueOperand());
1409 auto *E = new (ExpressionAllocator)
1410 StoreExpression(SI->getNumOperands(), SI, StoredValueLeader, MA);
1412 E->setType(SI->getValueOperand()->getType());
1413
1414
1415 E->setOpcode(0);
1416 E->op_push_back(lookupOperandLeader(SI->getPointerOperand()));
1417
1418
1419
1420
1421 return E;
1422}
1423
1424const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I) const {
1425
1426
1428 auto *StoreAccess = getMemoryAccess(SI);
1429
1430 const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess();
1433
1434 StoreRHS = lookupMemoryLeader(StoreRHS);
1435 if (StoreRHS != StoreAccess->getDefiningAccess())
1436 addMemoryUsers(StoreRHS, StoreAccess);
1437
1438 if (StoreRHS == StoreAccess)
1440
1441 if (SI->isSimple()) {
1442
1443
1444
1445 const auto *LastStore = createStoreExpression(SI, StoreRHS);
1446 const auto *LastCC = ExpressionToClass.lookup(LastStore);
1447
1448
1449
1450
1451
1452 if (LastCC && LastCC->getStoredValue() == LastStore->getStoredValue())
1453 return LastStore;
1454
1455
1456
1457
1460 LastStore->getOperand(0)) &&
1461 (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) ==
1462 StoreRHS))
1463 return LastStore;
1464 deleteExpression(LastStore);
1465 }
1466
1467
1468
1469
1470 return createStoreExpression(SI, StoreAccess);
1471}
1472
1473
1474
1476NewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr,
1477 LoadInst *LI, Instruction *DepInst,
1478 MemoryAccess *DefiningAccess) const {
1479 assert((!LI || LI->isSimple()) && "Not a simple load");
1481
1482
1483
1484 if (LI->isAtomic() > DepSI->isAtomic() ||
1485 LoadType == DepSI->getValueOperand()->getType())
1486 return nullptr;
1490 lookupOperandLeader(DepSI->getValueOperand()))) {
1492 LLVM_DEBUG(dbgs() << "Coercing load from store " << *DepSI
1493 << " to constant " << *Res << "\n");
1494 return createConstantExpression(Res);
1495 }
1496 }
1497 }
1499
1500 if (LI->isAtomic() > DepLI->isAtomic())
1501 return nullptr;
1504
1506 if (auto *PossibleConstant =
1508 LLVM_DEBUG(dbgs() << "Coercing load from load " << *LI
1509 << " to constant " << *PossibleConstant << "\n");
1510 return createConstantExpression(PossibleConstant);
1511 }
1512 }
1516 if (auto *PossibleConstant =
1518 LLVM_DEBUG(dbgs() << "Coercing load from meminst " << *DepMI
1519 << " to constant " << *PossibleConstant << "\n");
1520 return createConstantExpression(PossibleConstant);
1521 }
1522 }
1523 }
1524
1526 if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
1527 auto *LifetimePtr = II->getOperand(0);
1528 if (LoadPtr == lookupOperandLeader(LifetimePtr) ||
1530 return createConstantExpression(UndefValue::get(LoadType));
1531 }
1532 }
1533
1534
1535
1537 (LoadPtr != lookupOperandLeader(DepInst) &&
1539 return nullptr;
1540
1541
1542
1543
1545 return createConstantExpression(UndefValue::get(LoadType));
1546 } else if (auto *InitVal =
1548 return createConstantExpression(InitVal);
1549
1550 return nullptr;
1551}
1552
1553const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) const {
1555
1556
1557
1559 return nullptr;
1560
1562
1565 MemoryAccess *OriginalAccess = getMemoryAccess(I);
1566 MemoryAccess *DefiningAccess =
1568
1571 Instruction *DefiningInst = MD->getMemoryInst();
1572
1573 if (!ReachableBlocks.count(DefiningInst->getParent()))
1575
1576
1577
1578
1579 if (const auto *CoercionResult =
1580 performSymbolicLoadCoercion(LI->getType(), LoadAddressLeader, LI,
1581 DefiningInst, DefiningAccess))
1582 return CoercionResult;
1583 }
1584 }
1585
1586 const auto *LE = createLoadExpression(LI->getType(), LoadAddressLeader, LI,
1587 DefiningAccess);
1588
1589
1590 if (LE->getMemoryLeader() != DefiningAccess)
1591 addMemoryUsers(LE->getMemoryLeader(), OriginalAccess);
1592 return LE;
1593}
1594
1595NewGVN::ExprResult
1596NewGVN::performSymbolicPredicateInfoEvaluation(BitCastInst *I) const {
1597 auto *PI = PredInfo->getPredicateInfoFor(I);
1598 if (!PI)
1599 return ExprResult::none();
1600
1601 LLVM_DEBUG(dbgs() << "Found predicate info from instruction !\n");
1602
1603 const std::optional &Constraint = PI->getConstraint();
1604 if (!Constraint)
1605 return ExprResult::none();
1606
1608 Value *CmpOp0 = I->getOperand(0);
1609 Value *CmpOp1 = Constraint->OtherOp;
1610
1611 Value *FirstOp = lookupOperandLeader(CmpOp0);
1612 Value *SecondOp = lookupOperandLeader(CmpOp1);
1613 Value *AdditionallyUsedValue = CmpOp0;
1614
1615
1616 if (shouldSwapOperandsForPredicate(FirstOp, SecondOp, I)) {
1619 AdditionallyUsedValue = CmpOp1;
1620 }
1621
1623 return ExprResult::some(createVariableOrConstant(FirstOp),
1624 AdditionallyUsedValue, PI);
1625
1626
1629 return ExprResult::some(createConstantExpression(cast(FirstOp)),
1630 AdditionallyUsedValue, PI);
1631
1632 return ExprResult::none();
1633}
1634
1635
1636NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(Instruction *I) const {
1638
1639
1640
1641
1642
1643
1644
1645
1647 return ExprResult::none();
1648
1649
1650
1651
1653 return ExprResult::none();
1654
1656 return ExprResult::some(
1657 createCallExpression(CI, TOPClass->getMemoryLeader()));
1661 return ExprResult::some(createCallExpression(CI, DefiningAccess));
1662 } else
1663 return ExprResult::some(
1664 createCallExpression(CI, TOPClass->getMemoryLeader()));
1665 }
1666 return ExprResult::none();
1667}
1668
1669
1670CongruenceClass *NewGVN::getMemoryClass(const MemoryAccess *MA) const {
1671 auto *Result = MemoryAccessToClass.lookup(MA);
1672 assert(Result && "Should have found memory class");
1674}
1675
1676
1677
1678bool NewGVN::setMemoryClass(const MemoryAccess *From,
1679 CongruenceClass *NewClass) {
1681 "Every MemoryAccess should be getting mapped to a non-null class");
1683 LLVM_DEBUG(dbgs() << " equivalent to congruence class ");
1685 << " with current MemoryAccess leader ");
1686 LLVM_DEBUG(dbgs() << *NewClass->getMemoryLeader() << "\n");
1687
1690
1691 if (LookupResult != MemoryAccessToClass.end()) {
1693 if (OldClass != NewClass) {
1694
1696 OldClass->memory_erase(MP);
1697 NewClass->memory_insert(MP);
1698
1699 if (OldClass->getMemoryLeader() == From) {
1700 if (OldClass->definesNoMemory()) {
1701 OldClass->setMemoryLeader(nullptr);
1702 } else {
1703 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
1704 LLVM_DEBUG(dbgs() << "Memory class leader change for class "
1705 << OldClass->getID() << " to "
1706 << *OldClass->getMemoryLeader()
1707 << " due to removal of a memory member " << *From
1708 << "\n");
1709 markMemoryLeaderChangeTouched(OldClass);
1710 }
1711 }
1712 }
1713
1716 }
1717 }
1718
1720}
1721
1722
1723
1724
1725
1726bool NewGVN::isCycleFree(const Instruction *I) const {
1727
1728
1729
1730
1731
1732 auto ICS = InstCycleState.lookup(I);
1733 if (ICS == ICS_Unknown) {
1734 SCCFinder.Start(I);
1735 auto &SCC = SCCFinder.getComponentFor(I);
1736
1737 if (SCC.size() == 1)
1738 InstCycleState.insert({I, ICS_CycleFree});
1739 else {
1742 });
1743 ICS = AllPhis ? ICS_CycleFree : ICS_Cycle;
1744 for (const auto *Member : SCC)
1746 InstCycleState.insert({MemberPhi, ICS});
1747 }
1748 }
1749 if (ICS == ICS_Cycle)
1750 return false;
1751 return true;
1752}
1753
1754
1757 Instruction *I,
1758 BasicBlock *PHIBlock) const {
1759
1760 bool HasBackedge = false;
1761
1762
1763
1764
1765 bool OriginalOpsConstant = true;
1767 PHIOps, I, PHIBlock, HasBackedge, OriginalOpsConstant));
1768
1769
1770
1771 bool HasUndef = false, HasPoison = false;
1773 if (isa(Arg)) {
1774 HasPoison = true;
1775 return false;
1776 }
1778 HasUndef = true;
1779 return false;
1780 }
1781 return true;
1782 });
1783
1784 if (Filtered.empty()) {
1785
1786
1787 if (HasUndef) {
1789 dbgs() << "PHI Node " << *I
1790 << " has no non-undef arguments, valuing it as undef\n");
1791 return createConstantExpression(UndefValue::get(I->getType()));
1792 }
1793 if (HasPoison) {
1795 dbgs() << "PHI Node " << *I
1796 << " has no non-poison arguments, valuing it as poison\n");
1797 return createConstantExpression(PoisonValue::get(I->getType()));
1798 }
1799
1800 LLVM_DEBUG(dbgs() << "No arguments of PHI node " << *I << " are live\n");
1801 deleteExpression(E);
1802 return createDeadExpression();
1803 }
1804 Value *AllSameValue = *(Filtered.begin());
1805 ++Filtered.begin();
1806
1807 if (llvm::all_of(Filtered, [&](Value *Arg) { return Arg == AllSameValue; })) {
1808
1809
1811 return E;
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822 if (HasPoison || HasUndef) {
1823
1824
1825
1826
1827
1828 if (HasBackedge && !OriginalOpsConstant &&
1830 return E;
1831
1832
1834 if (!someEquivalentDominates(AllSameInst, I))
1835 return E;
1836 }
1837
1838
1839
1841 InstrToDFSNum(AllSameValue) > InstrToDFSNum(I))
1842 return E;
1843 NumGVNPhisAllSame++;
1844 LLVM_DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue
1845 << "\n");
1846 deleteExpression(E);
1847 return createVariableOrConstant(AllSameValue);
1848 }
1849 return E;
1850}
1851
1853NewGVN::performSymbolicAggrValueEvaluation(Instruction *I) const {
1856 if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0)
1857
1858
1859
1860 return createBinaryExpression(WO->getBinaryOp(), EI->getType(),
1861 WO->getLHS(), WO->getRHS(), I);
1862 }
1863
1864 return createAggregateValueExpression(I);
1865}
1866
1867NewGVN::ExprResult NewGVN::performSymbolicCmpEvaluation(Instruction *I) const {
1869
1871
1872
1873 auto Op0 = lookupOperandLeader(CI->getOperand(0));
1874 auto Op1 = lookupOperandLeader(CI->getOperand(1));
1875 auto OurPredicate = CI->getPredicate();
1876 if (shouldSwapOperands(Op0, Op1)) {
1878 OurPredicate = CI->getSwappedPredicate();
1879 }
1880
1881
1882 const PredicateBase *LastPredInfo = nullptr;
1883
1884
1885 auto *CmpPI = PredInfo->getPredicateInfoFor(I);
1887 return ExprResult::some(
1889
1890 if (Op0 == Op1) {
1891
1892 if (CI->isTrueWhenEqual())
1893 return ExprResult::some(
1895 else if (CI->isFalseWhenEqual())
1896 return ExprResult::some(
1898 }
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925 for (const auto &Op : CI->operands()) {
1926 auto *PI = PredInfo->getPredicateInfoFor(Op);
1928 if (PI == LastPredInfo)
1929 continue;
1930 LastPredInfo = PI;
1931
1932
1933 if (!DT->dominates(PBranch->To, I->getParent()))
1934 continue;
1935
1936
1937
1938
1939
1941 if (!BranchCond)
1942 continue;
1943 auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
1944 auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
1945 auto BranchPredicate = BranchCond->getPredicate();
1946 if (shouldSwapOperands(BranchOp0, BranchOp1)) {
1947 std::swap(BranchOp0, BranchOp1);
1948 BranchPredicate = BranchCond->getSwappedPredicate();
1949 }
1950 if (BranchOp0 == Op0 && BranchOp1 == Op1) {
1951 if (PBranch->TrueEdge) {
1952
1953
1955 OurPredicate)) {
1957 return ExprResult::some(createConstantExpression(C), PI);
1958 }
1959 } else {
1960
1961
1962 if (BranchPredicate == OurPredicate) {
1963
1964 return ExprResult::some(
1966 PI);
1967 } else if (BranchPredicate ==
1969
1970 return ExprResult::some(
1972 PI);
1973 }
1974 }
1975 }
1976 }
1977 }
1978
1979 return createExpression(I);
1980}
1981
1982
1983NewGVN::ExprResult
1984NewGVN::performSymbolicEvaluation(Instruction *I,
1985 SmallPtrSetImpl<Value *> &Visited) const {
1986
1988
1989
1990
1991 switch (I->getOpcode()) {
1992 case Instruction::ExtractValue:
1993 case Instruction::InsertValue:
1994 E = performSymbolicAggrValueEvaluation(I);
1995 break;
1996 case Instruction::PHI: {
1999 for (unsigned i = 0; i < PN->getNumOperands(); ++i)
2000 Ops.push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)});
2001
2002 sortPHIOps(Ops);
2003 E = performSymbolicPHIEvaluation(Ops, I, getBlockForValue(I));
2004 } break;
2005 case Instruction::Call:
2006 return performSymbolicCallEvaluation(I);
2007 break;
2008 case Instruction::Store:
2009 E = performSymbolicStoreEvaluation(I);
2010 break;
2011 case Instruction::Load:
2012 E = performSymbolicLoadEvaluation(I);
2013 break;
2014 case Instruction::BitCast:
2015
2016 if (I->getType() == I->getOperand(0)->getType())
2017 if (auto Res =
2019 return Res;
2020 [[fallthrough]];
2021 case Instruction::AddrSpaceCast:
2022 case Instruction::Freeze:
2023 return createExpression(I);
2024 break;
2025 case Instruction::ICmp:
2026 case Instruction::FCmp:
2027 return performSymbolicCmpEvaluation(I);
2028 break;
2029 case Instruction::FNeg:
2030 case Instruction::Add:
2031 case Instruction::FAdd:
2032 case Instruction::Sub:
2033 case Instruction::FSub:
2034 case Instruction::Mul:
2035 case Instruction::FMul:
2036 case Instruction::UDiv:
2037 case Instruction::SDiv:
2038 case Instruction::FDiv:
2039 case Instruction::URem:
2040 case Instruction::SRem:
2041 case Instruction::FRem:
2042 case Instruction::Shl:
2043 case Instruction::LShr:
2044 case Instruction::AShr:
2045 case Instruction::And:
2046 case Instruction::Or:
2047 case Instruction::Xor:
2048 case Instruction::Trunc:
2049 case Instruction::ZExt:
2050 case Instruction::SExt:
2051 case Instruction::FPToUI:
2052 case Instruction::FPToSI:
2053 case Instruction::UIToFP:
2054 case Instruction::SIToFP:
2055 case Instruction::FPTrunc:
2056 case Instruction::FPExt:
2057 case Instruction::PtrToInt:
2058 case Instruction::PtrToAddr:
2059 case Instruction::IntToPtr:
2060 case Instruction::Select:
2061 case Instruction::ExtractElement:
2062 case Instruction::InsertElement:
2063 case Instruction::GetElementPtr:
2064 return createExpression(I);
2065 break;
2066 case Instruction::ShuffleVector:
2067
2068 return ExprResult::none();
2069 default:
2070 return ExprResult::none();
2071 }
2072 return ExprResult::some(E);
2073}
2074
2075
2076
2077template <typename Map, typename KeyType>
2078void NewGVN::touchAndErase(Map &M, const KeyType &Key) {
2080 if (Result != M.end()) {
2081 for (const typename Map::mapped_type::value_type Mapped : Result->second)
2082 TouchedInstructions.set(InstrToDFSNum(Mapped));
2083 M.erase(Result);
2084 }
2085}
2086
2087void NewGVN::addAdditionalUsers(Value *To, Value *User) const {
2088 assert(User && To != User);
2090 AdditionalUsers[To].insert(User);
2091}
2092
2093void NewGVN::addAdditionalUsers(ExprResult &Res, Instruction *User) const {
2094 if (Res.ExtraDep && Res.ExtraDep != User)
2095 addAdditionalUsers(Res.ExtraDep, User);
2096 Res.ExtraDep = nullptr;
2097
2098 if (Res.PredDep) {
2100 PredicateToUsers[PBranch->Condition].insert(User);
2102 PredicateToUsers[PAssume->Condition].insert(User);
2103 }
2104 Res.PredDep = nullptr;
2105}
2106
2107void NewGVN::markUsersTouched(Value *V) {
2108
2109 for (auto *User : V->users()) {
2111 TouchedInstructions.set(InstrToDFSNum(User));
2112 }
2113 touchAndErase(AdditionalUsers, V);
2114}
2115
2116void NewGVN::addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const {
2117 LLVM_DEBUG(dbgs() << "Adding memory user " << *U << " to " << *To << "\n");
2118 MemoryToUsers[To].insert(U);
2119}
2120
2121void NewGVN::markMemoryDefTouched(const MemoryAccess *MA) {
2122 TouchedInstructions.set(MemoryToDFSNum(MA));
2123}
2124
2125void NewGVN::markMemoryUsersTouched(const MemoryAccess *MA) {
2127 return;
2128 for (const auto *U : MA->users())
2129 TouchedInstructions.set(MemoryToDFSNum(U));
2130 touchAndErase(MemoryToUsers, MA);
2131}
2132
2133
2134void NewGVN::markPredicateUsersTouched(Instruction *I) {
2135 touchAndErase(PredicateToUsers, I);
2136}
2137
2138
2139void NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *CC) {
2140 for (const auto *M : CC->memory())
2141 markMemoryDefTouched(M);
2142}
2143
2144
2145
2146void NewGVN::markValueLeaderChangeTouched(CongruenceClass *CC) {
2147 for (auto *M : *CC) {
2149 TouchedInstructions.set(InstrToDFSNum(I));
2150 LeaderChanges.insert(M);
2151 }
2152}
2153
2154
2155
2156template <class T, class Range>
2157T *NewGVN::getMinDFSOfRange(const Range &R) const {
2158 std::pair<T *, unsigned> MinDFS = {nullptr, ~0U};
2159 for (const auto X : R) {
2160 auto DFSNum = InstrToDFSNum(X);
2161 if (DFSNum < MinDFS.second)
2162 MinDFS = {X, DFSNum};
2163 }
2164 return MinDFS.first;
2165}
2166
2167
2168
2169
2170const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *CC) const {
2171
2172
2173
2174 assert(!CC->definesNoMemory() && "Can't get next leader if there is none");
2175 if (CC->getStoreCount() > 0) {
2177 return getMemoryAccess(NL);
2178
2182 }
2183 assert(CC->getStoreCount() == 0);
2184
2185
2186
2187 if (CC->memory_size() == 1)
2188 return *CC->memory_begin();
2189 return getMinDFSOfRange(CC->memory());
2190}
2191
2192
2193
2194
2195Value *NewGVN::getNextValueLeader(CongruenceClass *CC) const {
2196
2197
2198
2199
2200 if (CC->size() == 1 || CC == TOPClass) {
2201 return *(CC->begin());
2202 } else if (CC->getNextLeader().first) {
2203 ++NumGVNAvoidedSortedLeaderChanges;
2204 return CC->getNextLeader().first;
2205 } else {
2206 ++NumGVNSortedLeaderChanges;
2207
2208
2209
2210 return getMinDFSOfRange(*CC);
2211 }
2212}
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223void NewGVN::moveMemoryToNewCongruenceClass(Instruction *I,
2224 MemoryAccess *InstMA,
2225 CongruenceClass *OldClass,
2226 CongruenceClass *NewClass) {
2227
2228
2229 assert((!InstMA || !OldClass->getMemoryLeader() ||
2230 OldClass->getLeader() != I ||
2231 MemoryAccessToClass.lookup(OldClass->getMemoryLeader()) ==
2232 MemoryAccessToClass.lookup(InstMA)) &&
2233 "Representative MemoryAccess mismatch");
2234
2235 if (!NewClass->getMemoryLeader()) {
2236
2237 assert(NewClass->size() == 1 ||
2239 NewClass->setMemoryLeader(InstMA);
2240
2241 LLVM_DEBUG(dbgs() << "Memory class leader change for class "
2242 << NewClass->getID()
2243 << " due to new memory instruction becoming leader\n");
2244 markMemoryLeaderChangeTouched(NewClass);
2245 }
2246 setMemoryClass(InstMA, NewClass);
2247
2248 if (OldClass->getMemoryLeader() == InstMA) {
2249 if (!OldClass->definesNoMemory()) {
2250 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
2251 LLVM_DEBUG(dbgs() << "Memory class leader change for class "
2252 << OldClass->getID() << " to "
2253 << *OldClass->getMemoryLeader()
2254 << " due to removal of old leader " << *InstMA << "\n");
2255 markMemoryLeaderChangeTouched(OldClass);
2256 } else
2257 OldClass->setMemoryLeader(nullptr);
2258 }
2259}
2260
2261
2262
2263void NewGVN::moveValueToNewCongruenceClass(Instruction *I, const Expression *E,
2264 CongruenceClass *OldClass,
2265 CongruenceClass *NewClass) {
2266 if (I == OldClass->getNextLeader().first)
2267 OldClass->resetNextLeader();
2268
2269 OldClass->erase(I);
2270 NewClass->insert(I);
2271
2272
2273
2274 if (NewClass->getLeader() != I &&
2275 NewClass->addPossibleLeader({I, InstrToDFSNum(I)})) {
2276 markValueLeaderChangeTouched(NewClass);
2277 }
2278
2279
2281 OldClass->decStoreCount();
2282
2283
2284
2285
2286
2287
2288
2289 if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) {
2290
2291
2293 NewClass->setStoredValue(SE->getStoredValue());
2294 markValueLeaderChangeTouched(NewClass);
2295
2296 LLVM_DEBUG(dbgs() << "Changing leader of congruence class "
2297 << NewClass->getID() << " from "
2298 << *NewClass->getLeader() << " to " << *SI
2299 << " because store joined class\n");
2300
2301
2302 NewClass->setLeader({SI, InstrToDFSNum(SI)});
2303 }
2304
2305 }
2306 NewClass->incStoreCount();
2307 }
2308
2309
2310
2311
2313 if (InstMA)
2314 moveMemoryToNewCongruenceClass(I, InstMA, OldClass, NewClass);
2315 ValueToClass[I] = NewClass;
2316
2317 if (OldClass->empty() && OldClass != TOPClass) {
2318 if (OldClass->getDefiningExpr()) {
2319 LLVM_DEBUG(dbgs() << "Erasing expression " << *OldClass->getDefiningExpr()
2320 << " from table\n");
2321
2322
2323 auto Iter = ExpressionToClass.find_as(
2324 ExactEqualsExpression(*OldClass->getDefiningExpr()));
2325 if (Iter != ExpressionToClass.end())
2326 ExpressionToClass.erase(Iter);
2327#ifdef EXPENSIVE_CHECKS
2329 (*OldClass->getDefiningExpr() != *E || ExpressionToClass.lookup(E)) &&
2330 "We erased the expression we just inserted, which should not happen");
2331#endif
2332 }
2333 } else if (OldClass->getLeader() == I) {
2334
2335
2336
2337 LLVM_DEBUG(dbgs() << "Value class leader change for class "
2338 << OldClass->getID() << "\n");
2339 ++NumGVNLeaderChanges;
2340
2341
2342
2343
2344 if (OldClass->getStoreCount() == 0) {
2345 if (OldClass->getStoredValue())
2346 OldClass->setStoredValue(nullptr);
2347 }
2348 OldClass->setLeader({getNextValueLeader(OldClass),
2349 InstrToDFSNum(getNextValueLeader(OldClass))});
2350 OldClass->resetNextLeader();
2351 markValueLeaderChangeTouched(OldClass);
2352 }
2353}
2354
2355
2356
2357void NewGVN::markPhiOfOpsChanged(const Expression *E) {
2358 touchAndErase(ExpressionToPhiOfOps, E);
2359}
2360
2361
2362void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) {
2363
2364
2365
2366 CongruenceClass *IClass = ValueToClass.lookup(I);
2367 assert(IClass && "Should have found a IClass");
2368
2369 assert(!IClass->isDead() && "Found a dead class");
2370
2371 CongruenceClass *EClass = nullptr;
2373 EClass = ValueToClass.lookup(VE->getVariableValue());
2375 EClass = TOPClass;
2376 }
2377 if (!EClass) {
2378 auto lookupResult = ExpressionToClass.try_emplace(E);
2379
2380
2381 if (lookupResult.second) {
2382 CongruenceClass *NewClass = createCongruenceClass(nullptr, E);
2383 auto place = lookupResult.first;
2384 place->second = NewClass;
2385
2386
2388 NewClass->setLeader({CE->getConstantValue(), 0});
2390 StoreInst *SI = SE->getStoreInst();
2391 NewClass->setLeader({SI, InstrToDFSNum(SI)});
2392 NewClass->setStoredValue(SE->getStoredValue());
2393
2394
2395 } else {
2396 NewClass->setLeader({I, InstrToDFSNum(I)});
2397 }
2399 "VariableExpression should have been handled already");
2400
2401 EClass = NewClass;
2402 LLVM_DEBUG(dbgs() << "Created new congruence class for " << *I
2403 << " using expression " << *E << " at "
2404 << NewClass->getID() << " and leader "
2405 << *(NewClass->getLeader()));
2406 if (NewClass->getStoredValue())
2408 << *(NewClass->getStoredValue()));
2410 } else {
2411 EClass = lookupResult.first->second;
2414 (EClass->getStoredValue() &&
2416 "Any class with a constant expression should have a "
2417 "constant leader");
2418
2419 assert(EClass && "Somehow don't have an eclass");
2420
2421 assert(!EClass->isDead() && "We accidentally looked up a dead class");
2422 }
2423 }
2424 bool ClassChanged = IClass != EClass;
2425 bool LeaderChanged = LeaderChanges.erase(I);
2426 if (ClassChanged || LeaderChanged) {
2427 LLVM_DEBUG(dbgs() << "New class " << EClass->getID() << " for expression "
2428 << *E << "\n");
2429 if (ClassChanged) {
2430 moveValueToNewCongruenceClass(I, E, IClass, EClass);
2431 markPhiOfOpsChanged(E);
2432 }
2433
2434 markUsersTouched(I);
2435 if (MemoryAccess *MA = getMemoryAccess(I))
2436 markMemoryUsersTouched(MA);
2438 markPredicateUsersTouched(CI);
2439 }
2440
2441
2442
2443
2445 auto *OldE = ValueToExpression.lookup(I);
2446
2447
2449
2450
2451 auto Iter = ExpressionToClass.find_as(ExactEqualsExpression(*OldE));
2452 if (Iter != ExpressionToClass.end())
2453 ExpressionToClass.erase(Iter);
2454 }
2455 }
2456 ValueToExpression[I] = E;
2457}
2458
2459
2460
2461void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) {
2462
2463 if (ReachableEdges.insert({From, To}).second) {
2464
2465 if (ReachableBlocks.insert(To).second) {
2467 << " marked reachable\n");
2468 const auto &InstRange = BlockInstRange.lookup(To);
2469 TouchedInstructions.set(InstRange.first, InstRange.second);
2470 } else {
2472 << " was reachable, but new edge {"
2474 << "} to it found\n");
2475
2476
2477
2478
2479
2480 if (MemoryAccess *MemPhi = getMemoryAccess(To))
2481 TouchedInstructions.set(InstrToDFSNum(MemPhi));
2482
2483
2484
2485
2486 for (auto InstNum : RevisitOnReachabilityChange[To])
2487 TouchedInstructions.set(InstNum);
2488 }
2489 }
2490}
2491
2492
2493
2494Value *NewGVN::findConditionEquivalence(Value *Cond) const {
2495 auto Result = lookupOperandLeader(Cond);
2497}
2498
2499
2500void NewGVN::processOutgoingEdges(Instruction *TI, BasicBlock *B) {
2501
2505 Value *CondEvaluated = findConditionEquivalence(Cond);
2506 if (!CondEvaluated) {
2508 SmallPtrSet<Value *, 4> Visited;
2509 auto Res = performSymbolicEvaluation(I, Visited);
2511 CondEvaluated = CE->getConstantValue();
2512 addAdditionalUsers(Res, I);
2513 } else {
2514
2515
2516 Res.ExtraDep = nullptr;
2517 }
2519 CondEvaluated = Cond;
2520 }
2521 }
2522 ConstantInt *CI;
2524 if (CI->isOne()) {
2525 LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI
2526 << " evaluated to true\n");
2527 updateReachableEdge(B, TrueSucc);
2528 } else if (CI->isZero()) {
2529 LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI
2530 << " evaluated to false\n");
2531 updateReachableEdge(B, FalseSucc);
2532 }
2533 } else {
2534 updateReachableEdge(B, TrueSucc);
2535 updateReachableEdge(B, FalseSucc);
2536 }
2538
2539
2540
2541 Value *SwitchCond = SI->getCondition();
2542 Value *CondEvaluated = findConditionEquivalence(SwitchCond);
2543
2546
2547 auto Case = *SI->findCaseValue(CondVal);
2548 if (Case.getCaseSuccessor() == SI->getDefaultDest()) {
2549
2550
2551
2552 updateReachableEdge(B, SI->getDefaultDest());
2553 return;
2554 }
2555
2556 BasicBlock *TargetBlock = Case.getCaseSuccessor();
2557 updateReachableEdge(B, TargetBlock);
2558 } else {
2559 for (BasicBlock *TargetBlock : successors(SI->getParent()))
2560 updateReachableEdge(B, TargetBlock);
2561 }
2562 } else {
2563
2564
2566 updateReachableEdge(B, TargetBlock);
2567
2568
2569
2570
2571 auto *MA = getMemoryAccess(TI);
2573 auto *CC = ensureLeaderOfMemoryClass(MA);
2574 if (setMemoryClass(MA, CC))
2575 markMemoryUsersTouched(MA);
2576 }
2577 }
2578}
2579
2580
2581void NewGVN::removePhiOfOps(Instruction *I, PHINode *PHITemp) {
2582 InstrDFS.erase(PHITemp);
2583
2584
2585 TempToBlock.erase(PHITemp);
2587
2588
2589
2590
2591}
2592
2593
2594void NewGVN::addPhiOfOps(PHINode *Op, BasicBlock *BB,
2595 Instruction *ExistingValue) {
2596 InstrDFS[Op] = InstrToDFSNum(ExistingValue);
2597 AllTempInstructions.insert(Op);
2598 TempToBlock[Op] = BB;
2599 RealToTemp[ExistingValue] = Op;
2600
2601
2602 for (auto *U : ExistingValue->users())
2604 PHINodeUses.insert(UI);
2605}
2606
2613
2614
2615
2616
2617
2618
2619
2620
2621bool NewGVN::OpIsSafeForPHIOfOps(Value *V, const BasicBlock *PHIBlock,
2622 SmallPtrSetImpl<const Value *> &Visited) {
2625 while (!Worklist.empty()) {
2628 continue;
2629
2630 auto OISIt = OpSafeForPHIOfOps.find({I, CacheIdx});
2631 if (OISIt != OpSafeForPHIOfOps.end())
2632 return OISIt->second;
2633
2634
2635
2637 OpSafeForPHIOfOps.insert({{I, CacheIdx}, true});
2638 continue;
2639 }
2640
2641 if (isa(I) && getBlockForValue(I) == PHIBlock) {
2642 OpSafeForPHIOfOps.insert({{I, CacheIdx}, false});
2643 return false;
2644 }
2645
2647
2648
2649
2650
2651
2652
2653 if (OrigI->mayReadFromMemory())
2654 return false;
2655
2656
2657 for (auto *Op : OrigI->operand_values()) {
2659 continue;
2660
2661 auto OISIt = OpSafeForPHIOfOps.find({OrigI, CacheIdx});
2662 if (OISIt != OpSafeForPHIOfOps.end()) {
2663 if (!OISIt->second) {
2664 OpSafeForPHIOfOps.insert({{I, CacheIdx}, false});
2665 return false;
2666 }
2667 continue;
2668 }
2669 if (!Visited.insert(Op).second)
2670 continue;
2672 }
2673 }
2674 OpSafeForPHIOfOps.insert({{V, CacheIdx}, true});
2675 return true;
2676}
2677
2678
2679
2680
2681
2682
2683Value *NewGVN::findLeaderForInst(Instruction *TransInst,
2684 SmallPtrSetImpl<Value *> &Visited,
2685 MemoryAccess *MemAccess, Instruction *OrigInst,
2686 BasicBlock *PredBB) {
2687 unsigned IDFSNum = InstrToDFSNum(OrigInst);
2688
2689 AllTempInstructions.insert(TransInst);
2690
2691
2692
2693 TempToBlock.insert({TransInst, PredBB});
2694 InstrDFS.insert({TransInst, IDFSNum});
2695
2696 auto Res = performSymbolicEvaluation(TransInst, Visited);
2698 addAdditionalUsers(Res, OrigInst);
2699 InstrDFS.erase(TransInst);
2700 AllTempInstructions.erase(TransInst);
2701 TempToBlock.erase(TransInst);
2702 if (MemAccess)
2703 TempToMemory.erase(TransInst);
2704 if ()
2705 return nullptr;
2706 auto *FoundVal = findPHIOfOpsLeader(E, OrigInst, PredBB);
2707 if (!FoundVal) {
2708 ExpressionToPhiOfOps[E].insert(OrigInst);
2709 LLVM_DEBUG(dbgs() << "Cannot find phi of ops operand for " << *TransInst
2710 << " in block " << getBlockName(PredBB) << "\n");
2711 return nullptr;
2712 }
2714 FoundVal = SI->getValueOperand();
2715 return FoundVal;
2716}
2717
2718
2719
2721NewGVN::makePossiblePHIOfOps(Instruction *I,
2722 SmallPtrSetImpl<Value *> &Visited) {
2724 return nullptr;
2725
2726 if (!Visited.insert(I).second)
2727 return nullptr;
2728
2729
2730
2731
2732 if (!isCycleFree(I))
2733 return nullptr;
2734
2735
2736
2737
2738 auto *MemAccess = getMemoryAccess(I);
2739
2740
2741
2742 if (MemAccess && (MemAccess->getDefiningAccess()) &&
2744 return nullptr;
2745
2746
2747 SmallPtrSet<const Value *, 10> VisitedOps;
2750 PHINode *OpPHI = nullptr;
2752 return nullptr;
2755 auto *ValuePHI = RealToTemp.lookup(Op);
2756 if (!ValuePHI)
2757 continue;
2758 LLVM_DEBUG(dbgs() << "Found possible dependent phi of ops\n");
2759 Op = ValuePHI;
2760 }
2762 if (!SamePHIBlock) {
2763 SamePHIBlock = getBlockForValue(OpPHI);
2764 } else if (SamePHIBlock != getBlockForValue(OpPHI)) {
2767 << "PHIs for operands are not all in the same block, aborting\n");
2768 return nullptr;
2769 }
2770
2771
2772
2774 return nullptr;
2775 }
2776
2777 if (!OpPHI)
2778 return nullptr;
2779
2781 SmallPtrSet<Value *, 4> Deps;
2782 auto *PHIBlock = getBlockForValue(OpPHI);
2783 RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(I));
2784 for (unsigned PredNum = 0; PredNum < OpPHI->getNumOperands(); ++PredNum) {
2786 Value *FoundVal = nullptr;
2787 SmallPtrSet<Value *, 4> CurrentDeps;
2788
2789
2790 if (ReachableEdges.count({PredBB, PHIBlock})) {
2791
2792
2794
2795
2797 if (MemAccess)
2798 TempToMemory.insert({ValueOp, MemAccess});
2799 bool SafeForPHIOfOps = true;
2800 VisitedOps.clear();
2801 for (auto &Op : ValueOp->operands()) {
2802 auto *OrigOp = &*Op;
2803
2804
2806 Op = Op->DoPHITranslation(PHIBlock, PredBB);
2807 if (Op != OrigOp && Op != I)
2809 } else if (auto *ValuePHI = RealToTemp.lookup(Op)) {
2810 if (getBlockForValue(ValuePHI) == PHIBlock)
2811 Op = ValuePHI->getIncomingValueForBlock(PredBB);
2812 }
2813
2814 SafeForPHIOfOps =
2815 SafeForPHIOfOps &&
2816 (Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps));
2817 }
2818
2819
2820
2821
2822
2823 FoundVal = !SafeForPHIOfOps ? nullptr
2824 : findLeaderForInst(ValueOp, Visited,
2825 MemAccess, I, PredBB);
2827 if (!FoundVal) {
2828
2829
2830 if (SafeForPHIOfOps)
2831 for (auto *Dep : CurrentDeps)
2832 addAdditionalUsers(Dep, I);
2833
2834 return nullptr;
2835 }
2837 } else {
2838 LLVM_DEBUG(dbgs() << "Skipping phi of ops operand for incoming block "
2840 << " because the block is unreachable\n");
2842 RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
2843 }
2844
2845 PHIOps.push_back({FoundVal, PredBB});
2846 LLVM_DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in "
2848 }
2849 for (auto *Dep : Deps)
2850 addAdditionalUsers(Dep, I);
2851 sortPHIOps(PHIOps);
2852 auto *E = performSymbolicPHIEvaluation(PHIOps, I, PHIBlock);
2856 << "Not creating real PHI of ops because it simplified to existing "
2857 "value or constant\n");
2858
2859
2860
2861
2862
2863 for (auto &O : PHIOps)
2864 addAdditionalUsers(O.first, I);
2865
2866 return E;
2867 }
2868 auto *ValuePHI = RealToTemp.lookup(I);
2869 bool NewPHI = false;
2870 if (!ValuePHI) {
2871 ValuePHI =
2873 addPhiOfOps(ValuePHI, PHIBlock, I);
2874 NewPHI = true;
2875 NumGVNPHIOfOpsCreated++;
2876 }
2877 if (NewPHI) {
2878 for (auto PHIOp : PHIOps)
2879 ValuePHI->addIncoming(PHIOp.first, PHIOp.second);
2880 } else {
2881 TempToBlock[ValuePHI] = PHIBlock;
2882 unsigned int i = 0;
2883 for (auto PHIOp : PHIOps) {
2884 ValuePHI->setIncomingValue(i, PHIOp.first);
2885 ValuePHI->setIncomingBlock(i, PHIOp.second);
2886 ++i;
2887 }
2888 }
2889 RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
2890 LLVM_DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I
2891 << "\n");
2892
2893 return E;
2894}
2895
2896
2897
2898
2899void NewGVN::initializeCongruenceClasses(Function &F) {
2900 NextCongruenceNum = 0;
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910 TOPClass = createCongruenceClass(nullptr, nullptr);
2912
2915
2916 for (auto *DTN : nodes(DT)) {
2918
2919
2920
2921
2922 auto *MemoryBlockDefs = MSSA->getBlockDefs(BB);
2923 if (MemoryBlockDefs)
2924 for (const auto &Def : *MemoryBlockDefs) {
2925 MemoryAccessToClass[&Def] = TOPClass;
2927
2928 if (!MD) {
2930 TOPClass->memory_insert(MP);
2931 MemoryPhiState.insert({MP, MPS_TOP});
2932 }
2933
2935 TOPClass->incStoreCount();
2936 }
2937
2938
2939
2940
2941 for (auto &I : *BB) {
2943 for (auto *U : I.users())
2945 if (InstrToDFSNum(UInst) != 0 && okayForPHIOfOps(UInst))
2946 PHINodeUses.insert(UInst);
2947
2948
2949 if (I.isTerminator() && I.getType()->isVoidTy())
2950 continue;
2951 TOPClass->insert(&I);
2952 ValueToClass[&I] = TOPClass;
2953 }
2954 }
2955
2956
2957 for (auto &FA : F.args())
2958 createSingletonCongruenceClass(&FA);
2959}
2960
2961void NewGVN::cleanupTables() {
2962 for (CongruenceClass *&CC : CongruenceClasses) {
2963 LLVM_DEBUG(dbgs() << "Congruence class " << CC->getID() << " has "
2964 << CC->size() << " members\n");
2965
2966
2967 delete CC;
2968 CC = nullptr;
2969 }
2970
2971
2972 SmallVector<Instruction *, 8> TempInst(AllTempInstructions.begin(),
2973 AllTempInstructions.end());
2974 AllTempInstructions.clear();
2975
2976
2977
2978 for (auto *I : TempInst) {
2979 I->dropAllReferences();
2980 }
2981
2982 while (!TempInst.empty()) {
2983 auto *I = TempInst.pop_back_val();
2984 I->deleteValue();
2985 }
2986
2987 ValueToClass.clear();
2988 ArgRecycler.clear(ExpressionAllocator);
2989 ExpressionAllocator.Reset();
2990 CongruenceClasses.clear();
2991 ExpressionToClass.clear();
2992 ValueToExpression.clear();
2993 RealToTemp.clear();
2994 AdditionalUsers.clear();
2995 ExpressionToPhiOfOps.clear();
2996 TempToBlock.clear();
2997 TempToMemory.clear();
2998 PHINodeUses.clear();
2999 OpSafeForPHIOfOps.clear();
3000 ReachableBlocks.clear();
3001 ReachableEdges.clear();
3002#ifndef NDEBUG
3003 ProcessedCount.clear();
3004#endif
3005 InstrDFS.clear();
3006 InstructionsToErase.clear();
3007 DFSToInstr.clear();
3008 BlockInstRange.clear();
3009 TouchedInstructions.clear();
3010 MemoryAccessToClass.clear();
3011 PredicateToUsers.clear();
3012 MemoryToUsers.clear();
3013 RevisitOnReachabilityChange.clear();
3014 PredicateSwapChoice.clear();
3015}
3016
3017
3018
3019std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
3020 unsigned Start) {
3021 unsigned End = Start;
3022 if (MemoryAccess *MemPhi = getMemoryAccess(B)) {
3023 InstrDFS[MemPhi] = End++;
3025 }
3026
3027
3029
3030
3031
3033 InstrDFS[&I] = 0;
3034 LLVM_DEBUG(dbgs() << "Skipping trivially dead instruction " << I << "\n");
3036 markInstructionForDeletion(&I);
3037 continue;
3038 }
3040 RevisitOnReachabilityChange[B].set(End);
3041 InstrDFS[&I] = End++;
3043 }
3044
3045
3046
3047
3048 return std::make_pair(Start, End);
3049}
3050
3051void NewGVN::updateProcessedCount(const Value *V) {
3052#ifndef NDEBUG
3053 assert(++ProcessedCount[V] < 100 &&
3054 "Seem to have processed the same Value a lot");
3055#endif
3056}
3057
3058
3059void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) {
3060
3061
3062
3063
3066 return cast(U) != MP &&
3067 !isMemoryAccessTOP(cast(U)) &&
3068 ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock});
3069 });
3070
3071
3072
3073 if (Filtered.begin() == Filtered.end()) {
3074 if (setMemoryClass(MP, TOPClass))
3075 markMemoryUsersTouched(MP);
3076 return;
3077 }
3078
3079
3080
3081 auto LookupFunc = [&](const Use &U) {
3083 };
3084 auto MappedBegin = map_iterator(Filtered.begin(), LookupFunc);
3085 auto MappedEnd = map_iterator(Filtered.end(), LookupFunc);
3086
3087
3088
3089 const auto *AllSameValue = *MappedBegin;
3090 ++MappedBegin;
3091 bool AllEqual = std::all_of(
3092 MappedBegin, MappedEnd,
3093 [&AllSameValue](const MemoryAccess *V) { return V == AllSameValue; });
3094
3095 if (AllEqual)
3096 LLVM_DEBUG(dbgs() << "Memory Phi value numbered to " << *AllSameValue
3097 << "\n");
3098 else
3099 LLVM_DEBUG(dbgs() << "Memory Phi value numbered to itself\n");
3100
3101
3102
3103
3104
3105 CongruenceClass *CC =
3106 AllEqual ? getMemoryClass(AllSameValue) : ensureLeaderOfMemoryClass(MP);
3107 auto OldState = MemoryPhiState.lookup(MP);
3108 assert(OldState != MPS_Invalid && "Invalid memory phi state");
3109 auto NewState = AllEqual ? MPS_Equivalent : MPS_Unique;
3110 MemoryPhiState[MP] = NewState;
3111 if (setMemoryClass(MP, CC) || OldState != NewState)
3112 markMemoryUsersTouched(MP);
3113}
3114
3115
3116
3117void NewGVN::valueNumberInstruction(Instruction *I) {
3118 LLVM_DEBUG(dbgs() << "Processing instruction " << *I << "\n");
3119 if (->isTerminator()) {
3120 const Expression *Symbolized = nullptr;
3121 SmallPtrSet<Value *, 2> Visited;
3123 auto Res = performSymbolicEvaluation(I, Visited);
3124 Symbolized = Res.Expr;
3125 addAdditionalUsers(Res, I);
3126
3127
3130 auto *PHIE = makePossiblePHIOfOps(I, Visited);
3131
3132
3133 if (PHIE) {
3134 Symbolized = PHIE;
3135 } else if (auto *Op = RealToTemp.lookup(I)) {
3137 }
3138 }
3139 } else {
3140
3141 InstrDFS[I] = 0;
3142 }
3143
3144
3145 if (Symbolized == nullptr)
3146 Symbolized = createUnknownExpression(I);
3147 performCongruenceFinding(I, Symbolized);
3148 } else {
3149
3150
3151
3152 if (->getType()->isVoidTy()) {
3153 auto *Symbolized = createUnknownExpression(I);
3154 performCongruenceFinding(I, Symbolized);
3155 }
3156 processOutgoingEdges(I, I->getParent());
3157 }
3158}
3159
3160
3161
3162bool NewGVN::singleReachablePHIPath(
3163 SmallPtrSet<const MemoryAccess *, 8> &Visited, const MemoryAccess *First,
3164 const MemoryAccess *Second) const {
3165 if (First == Second)
3166 return true;
3168 return false;
3169
3170
3171
3172
3173
3174
3176 return true;
3177
3178 const auto *EndDef = First;
3180 if (ChainDef == Second)
3181 return true;
3183 return false;
3184 EndDef = ChainDef;
3185 }
3187 auto ReachableOperandPred = [&](const Use &U) {
3189 };
3190 auto FilteredPhiArgs =
3193 bool Okay = all_equal(OperandList);
3194 if (Okay)
3195 return singleReachablePHIPath(Visited, cast(OperandList[0]),
3196 Second);
3197 return false;
3198}
3199
3200
3201
3202
3203
3204void NewGVN::verifyMemoryCongruency() const {
3205#ifndef NDEBUG
3206
3207 for (const auto *CC : CongruenceClasses) {
3208 if (CC == TOPClass || CC->isDead())
3209 continue;
3210 if (CC->getStoreCount() != 0) {
3212 "Any class with a store as a leader should have a "
3213 "representative stored value");
3214 assert(CC->getMemoryLeader() &&
3215 "Any congruence class with a store should have a "
3216 "representative access");
3217 }
3218
3219 if (CC->getMemoryLeader())
3220 assert(MemoryAccessToClass.lookup(CC->getMemoryLeader()) == CC &&
3221 "Representative MemoryAccess does not appear to be reverse "
3222 "mapped properly");
3223 for (const auto *M : CC->memory())
3224 assert(MemoryAccessToClass.lookup(M) == CC &&
3225 "Memory member does not appear to be reverse mapped properly");
3226 }
3227
3228
3229
3230
3231
3232
3233 auto ReachableAccessPred =
3234 [&](const std::pair<const MemoryAccess *, CongruenceClass *> Pair) {
3235 bool Result = ReachableBlocks.count(Pair.first->getBlock());
3237 MemoryToDFSNum(Pair.first) == 0)
3238 return false;
3241
3242
3243
3245 for (const auto &U : MemPHI->incoming_values()) {
3248 return true;
3249 }
3250 }
3251 return false;
3252 }
3253
3254 return true;
3255 };
3256
3257 auto Filtered = make_filter_range(MemoryAccessToClass, ReachableAccessPred);
3258 for (auto KV : Filtered) {
3261 if (FirstMUD && SecondMUD) {
3262 SmallPtrSet<const MemoryAccess *, 8> VisitedMAS;
3263 assert((singleReachablePHIPath(VisitedMAS, FirstMUD, SecondMUD) ||
3264 ValueToClass.lookup(FirstMUD->getMemoryInst()) ==
3265 ValueToClass.lookup(SecondMUD->getMemoryInst())) &&
3266 "The instructions for these memory operations should have "
3267 "been in the same congruence class or reachable through"
3268 "a single argument phi");
3269 }
3271
3272
3273 auto ReachableOperandPred = [&](const Use &U) {
3274 return ReachableEdges.count(
3275 {FirstMP->getIncomingBlock(U), FirstMP->getBlock()}) &&
3277 };
3278
3279 auto FilteredPhiArgs =
3282 std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
3283 std::back_inserter(PhiOpClasses), [&](const Use &U) {
3284 const MemoryDef *MD = cast(U);
3285 return ValueToClass.lookup(MD->getMemoryInst());
3286 });
3288 "All MemoryPhi arguments should be in the same class");
3289 }
3290 }
3291#endif
3292}
3293
3294
3295
3296
3297void NewGVN::verifyIterationSettled(Function &F) {
3298#ifndef NDEBUG
3299 LLVM_DEBUG(dbgs() << "Beginning iteration verification\n");
3302
3303
3304
3305
3306
3307 std::map<const Value *, CongruenceClass> BeforeIteration;
3308
3309 for (auto &KV : ValueToClass) {
3311
3312 if (InstrToDFSNum(I) == 0)
3313 continue;
3314 BeforeIteration.insert({KV.first, *KV.second});
3315 }
3316
3317 TouchedInstructions.set();
3318 TouchedInstructions.reset(0);
3319 OpSafeForPHIOfOps.clear();
3320 CacheIdx = 0;
3321 iterateTouchedInstructions();
3322 DenseSet<std::pair<const CongruenceClass *, const CongruenceClass *>>
3323 EqualClasses;
3324 for (const auto &KV : ValueToClass) {
3326
3327 if (InstrToDFSNum(I) == 0)
3328 continue;
3329
3330
3331 auto *BeforeCC = &BeforeIteration.find(KV.first)->second;
3332 auto *AfterCC = KV.second;
3333
3334
3335 if (!EqualClasses.count({BeforeCC, AfterCC})) {
3336 assert(BeforeCC->isEquivalentTo(AfterCC) &&
3337 "Value number changed after main loop completed!");
3338 EqualClasses.insert({BeforeCC, AfterCC});
3339 }
3340 }
3341#endif
3342}
3343
3344
3345
3346
3347
3348
3349void NewGVN::verifyStoreExpressions() const {
3350#ifndef NDEBUG
3351
3352
3353 std::set<
3354 std::pair<const Value *,
3355 std::tuple<const Value *, const CongruenceClass *, Value *>>>
3356 StoreExpressionSet;
3357 for (const auto &KV : ExpressionToClass) {
3359
3360 auto Res = StoreExpressionSet.insert(
3361 {SE->getOperand(0), std::make_tuple(SE->getMemoryLeader(), KV.second,
3362 SE->getStoredValue())});
3363 bool Okay = Res.second;
3364
3365
3366
3367 if (!Okay)
3368 Okay = (std::get<1>(Res.first->second) == KV.second) &&
3369 (lookupOperandLeader(std::get<2>(Res.first->second)) ==
3370 lookupOperandLeader(SE->getStoredValue()));
3371 assert(Okay && "Stored expression conflict exists in expression table");
3372 auto *ValueExpr = ValueToExpression.lookup(SE->getStoreInst());
3373 assert(ValueExpr && ValueExpr->equals(*SE) &&
3374 "StoreExpression in ExpressionToClass is not latest "
3375 "StoreExpression for value");
3376 }
3377 }
3378#endif
3379}
3380
3381
3382
3383
3384void NewGVN::iterateTouchedInstructions() {
3385 uint64_t Iterations = 0;
3386
3387 int FirstInstr = TouchedInstructions.find_first();
3388
3389 if (FirstInstr == -1)
3390 return;
3391 const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
3392 while (TouchedInstructions.any()) {
3393 ++Iterations;
3394
3395
3396
3397
3398 for (unsigned InstrNum : TouchedInstructions.set_bits()) {
3399
3400
3401
3402 if (InstrNum == 0) {
3403 TouchedInstructions.reset(InstrNum);
3404 continue;
3405 }
3406
3407 Value *V = InstrFromDFSNum(InstrNum);
3408 const BasicBlock *CurrBlock = getBlockForValue(V);
3409
3410
3411 if (CurrBlock != LastBlock) {
3412 LastBlock = CurrBlock;
3413 bool BlockReachable = ReachableBlocks.count(CurrBlock);
3414 const auto &CurrInstRange = BlockInstRange.lookup(CurrBlock);
3415
3416
3417 if (!BlockReachable) {
3418 TouchedInstructions.reset(CurrInstRange.first, CurrInstRange.second);
3419 LLVM_DEBUG(dbgs() << "Skipping instructions in block "
3421 << " because it is unreachable\n");
3422 continue;
3423 }
3424
3425 CacheIdx = RPOOrdering.lookup(DT->getNode(CurrBlock)) - 1;
3426 updateProcessedCount(CurrBlock);
3427 }
3428
3429
3430 TouchedInstructions.reset(InstrNum);
3431
3433 LLVM_DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n");
3434 valueNumberMemoryPhi(MP);
3436 valueNumberInstruction(I);
3437 } else {
3438 llvm_unreachable("Should have been a MemoryPhi or Instruction");
3439 }
3440 updateProcessedCount(V);
3441 }
3442 }
3443 NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations);
3444}
3445
3446
3447bool NewGVN::runGVN() {
3451 NumFuncArgs = F.arg_size();
3453 SingletonDeadExpression = new (ExpressionAllocator) DeadExpression();
3454
3455
3456
3457 unsigned ICount = 1;
3458
3460
3461
3462
3463
3464
3465
3466
3467
3468 ReversePostOrderTraversal<Function *> RPOT(&F);
3469 unsigned Counter = 0;
3470 for (auto &B : RPOT) {
3472 assert(Node && "RPO and Dominator tree should have same reachability");
3473 RPOOrdering[Node] = ++Counter;
3474 }
3475
3476 for (auto &B : RPOT) {
3478 if (Node->getNumChildren() > 1)
3480 return RPOOrdering[A] < RPOOrdering[B];
3481 });
3482 }
3483
3484
3487 const auto &BlockRange = assignDFSNumbers(B, ICount);
3488 BlockInstRange.insert({B, BlockRange});
3489 ICount += BlockRange.second - BlockRange.first;
3490 }
3491 initializeCongruenceClasses(F);
3492
3493 TouchedInstructions.resize(ICount);
3494
3495
3496
3497 ExpressionToClass.reserve(ICount);
3498
3499
3500 const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock());
3501 TouchedInstructions.set(InstRange.first, InstRange.second);
3503 << " marked reachable\n");
3504 ReachableBlocks.insert(&F.getEntryBlock());
3505
3506 CacheIdx = 0;
3507
3508 iterateTouchedInstructions();
3509 verifyMemoryCongruency();
3510 verifyIterationSettled(F);
3511 verifyStoreExpressions();
3512
3513 Changed |= eliminateInstructions(F);
3514
3515
3516 for (Instruction *ToErase : InstructionsToErase) {
3517 if (!ToErase->use_empty())
3518 ToErase->replaceAllUsesWith(PoisonValue::get(ToErase->getType()));
3519
3520 assert(ToErase->getParent() &&
3521 "BB containing ToErase deleted unexpectedly!");
3522 ToErase->eraseFromParent();
3523 }
3524 Changed |= !InstructionsToErase.empty();
3525
3526
3527 auto UnreachableBlockPred = [&](const BasicBlock &BB) {
3528 return !ReachableBlocks.count(&BB);
3529 };
3530
3533 << " is unreachable\n");
3534 deleteInstructionsInBlock(&BB);
3536 }
3537
3538 cleanupTables();
3540}
3541
3546
3547
3548
3549
3552
3554
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
3570
3571
3572
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3595 }
3596};
3597
3598
3599
3600
3601
3602
3603void NewGVN::convertClassToDFSOrdered(
3608
3610
3611
3612 assert(BB && "Should have figured out a basic block for value");
3617
3618
3619
3621 auto Leader = lookupOperandLeader(SI->getValueOperand());
3623 VDDef.Def.setPointer(Leader);
3624 } else {
3625 VDDef.Def.setPointer(SI->getValueOperand());
3626 VDDef.Def.setInt(true);
3627 }
3628 } else {
3629 VDDef.Def.setPointer(D);
3630 }
3632 "The dense set member should always be an instruction");
3634 VDDef.LocalNum = InstrToDFSNum(D);
3636
3637 if (auto *PN = RealToTemp.lookup(Def)) {
3638 auto *PHIE =
3640 if (PHIE) {
3641 VDDef.Def.setInt(false);
3642 VDDef.Def.setPointer(PN);
3645 }
3646 }
3647
3648 unsigned int UseCount = 0;
3649
3650 for (auto &U : Def->uses()) {
3652
3653 if (InstructionsToErase.count(I))
3654 continue;
3655 ValueDFS VDUse;
3656
3659 IBlock = P->getIncomingBlock(U);
3660
3661
3663 } else {
3664 IBlock = getBlockForValue(I);
3665 VDUse.LocalNum = InstrToDFSNum(I);
3666 }
3667
3668
3669
3670 if (!ReachableBlocks.contains(IBlock))
3671 continue;
3672
3677 ++UseCount;
3679 }
3680 }
3681
3682
3683
3684
3685 if (UseCount == 0)
3686 ProbablyDead.insert(Def);
3687 else
3688 UseCounts[Def] = UseCount;
3689 }
3690}
3691
3692
3693
3694void NewGVN::convertClassToLoadsAndStores(
3695 const CongruenceClass &Dense,
3696 SmallVectorImpl &LoadsAndStores) const {
3699 continue;
3700
3702 ValueDFS VD;
3706 VD.Def.setPointer(D);
3707
3708
3711 else
3713
3715 }
3716}
3717
3720 I->replaceAllUsesWith(Repl);
3721}
3722
3723void NewGVN::deleteInstructionsInBlock(BasicBlock *BB) {
3725 ++NumGVNBlocksDeleted;
3726
3727
3728
3729 auto StartPoint = BB->rbegin();
3730 ++StartPoint;
3731
3732
3738 continue;
3740
3742 ++NumGVNInstrDeleted;
3743 }
3744
3746 new StoreInst(
3750}
3751
3752void NewGVN::markInstructionForDeletion(Instruction *I) {
3753 LLVM_DEBUG(dbgs() << "Marking " << *I << " for deletion\n");
3754 InstructionsToErase.insert(I);
3755}
3756
3757void NewGVN::replaceInstruction(Instruction *I, Value *V) {
3758 LLVM_DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n");
3760
3761
3762 markInstructionForDeletion(I);
3763}
3764
3765namespace {
3766
3767
3768
3769class ValueDFSStack {
3770public:
3771 Value *back() const { return ValueStack.back(); }
3772 std::pair<int, int> dfs_back() const { return DFSStack.back(); }
3773
3774 void push_back(Value *V, int DFSIn, int DFSOut) {
3775 ValueStack.emplace_back(V);
3776 DFSStack.emplace_back(DFSIn, DFSOut);
3777 }
3778
3779 bool empty() const { return DFSStack.empty(); }
3780
3781 bool isInScope(int DFSIn, int DFSOut) const {
3783 return false;
3784 return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
3785 }
3786
3787 void popUntilDFSScope(int DFSIn, int DFSOut) {
3788
3789
3790 assert(ValueStack.size() == DFSStack.size() &&
3791 "Mismatch between ValueStack and DFSStack");
3792 while (
3793 !DFSStack.empty() &&
3794 !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
3795 DFSStack.pop_back();
3796 ValueStack.pop_back();
3797 }
3798 }
3799
3800private:
3801 SmallVector<Value *, 8> ValueStack;
3803};
3804
3805}
3806
3807
3808CongruenceClass *NewGVN::getClassForExpression(const Expression *E) const {
3810 return ValueToClass.lookup(VE->getVariableValue());
3812 return TOPClass;
3813 return ExpressionToClass.lookup(E);
3814}
3815
3816
3817
3819 const Instruction *OrigInst,
3820 const BasicBlock *BB) const {
3821
3823 return CE->getConstantValue();
3825 auto *V = VE->getVariableValue();
3827 return VE->getVariableValue();
3828 }
3829
3830 auto *CC = getClassForExpression(E);
3831 if (!CC)
3832 return nullptr;
3834 return CC->getLeader();
3835
3836 for (auto *Member : *CC) {
3838 if (MemberInst == OrigInst)
3839 continue;
3840
3841 if (!MemberInst)
3843 if (DT->dominates(getBlockForValue(MemberInst), BB))
3845 }
3846 return nullptr;
3847}
3848
3849bool NewGVN::eliminateInstructions(Function &F) {
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873 bool AnythingReplaced = false;
3874
3875
3876
3878
3879
3880
3881 auto ReplaceUnreachablePHIArgs = [&](PHINode *PHI, BasicBlock *BB) {
3882 for (auto &Operand : PHI->incoming_values())
3883 if (!ReachableEdges.count({PHI->getIncomingBlock(Operand), BB})) {
3885 << " for block "
3887 << " with poison due to it being unreachable\n");
3889 }
3890 };
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900 DenseMap<const BasicBlock *, unsigned> ReachablePredCount;
3901 for (auto &KV : ReachableEdges)
3902 ReachablePredCount[KV.getEnd()]++;
3903 for (auto &BBPair : RevisitOnReachabilityChange) {
3904 for (auto InstNum : BBPair.second) {
3905 auto *Inst = InstrFromDFSNum(InstNum);
3908 if ()
3909 continue;
3910 auto *BB = BBPair.first;
3911 if (ReachablePredCount.lookup(BB) != PHI->getNumIncomingValues())
3912 ReplaceUnreachablePHIArgs(PHI, BB);
3913 }
3914 }
3915
3916
3917 DenseMap<const Value *, unsigned int> UseCounts;
3918 for (auto *CC : reverse(CongruenceClasses)) {
3919 LLVM_DEBUG(dbgs() << "Eliminating in congruence class " << CC->getID()
3920 << "\n");
3921
3922
3924 SmallPtrSet<Instruction *, 8> ProbablyDead;
3925 if (CC->isDead() || CC->empty())
3926 continue;
3927
3928 if (CC == TOPClass) {
3929 for (auto *M : *CC) {
3930 auto *VTE = ValueToExpression.lookup(M);
3935 "Everything in TOP should be unreachable or dead at this "
3936 "point");
3937 }
3938 continue;
3939 }
3940
3941 assert(CC->getLeader() && "We should have had a leader");
3942
3943
3944
3945
3947 CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
3949 CongruenceClass::MemberSet MembersLeft;
3950 for (auto *M : *CC) {
3952
3954 Member->getType()->isVoidTy()) {
3955 MembersLeft.insert(Member);
3956 continue;
3957 }
3958
3959 LLVM_DEBUG(dbgs() << "Found replacement " << *(Leader) << " for "
3960 << *Member << "\n");
3962 assert(Leader != I && "About to accidentally remove our leader");
3963 replaceInstruction(I, Leader);
3964 AnythingReplaced = true;
3965 }
3966 CC->swap(MembersLeft);
3967 } else {
3968
3969 if (CC->size() != 1 || RealToTemp.count(Leader)) {
3970
3971
3972
3973
3974 ValueDFSStack EliminationStack;
3975
3976
3978 convertClassToDFSOrdered(*CC, DFSOrderedSet, UseCounts, ProbablyDead);
3979
3980
3982 for (auto &VD : DFSOrderedSet) {
3983 int MemberDFSIn = VD.DFSIn;
3984 int MemberDFSOut = VD.DFSOut;
3985 Value *Def = VD.Def.getPointer();
3986 bool FromStore = VD.Def.getInt();
3988
3989 if (Def && Def->getType()->isVoidTy())
3990 continue;
3992 if (DefInst && AllTempInstructions.count(DefInst)) {
3994
3995
3996
3997
3998 AllTempInstructions.erase(PN);
3999 auto *DefBlock = getBlockForValue(Def);
4000 LLVM_DEBUG(dbgs() << "Inserting fully real phi of ops" << *Def
4001 << " into block "
4002 << getBlockName(getBlockForValue(Def)) << "\n");
4003 PN->insertBefore(DefBlock->begin());
4004 Def = PN;
4005 NumGVNPHIOfOpsEliminations++;
4006 }
4007
4008 if (EliminationStack.empty()) {
4009 LLVM_DEBUG(dbgs() << "Elimination Stack is empty\n");
4010 } else {
4011 LLVM_DEBUG(dbgs() << "Elimination Stack Top DFS numbers are ("
4012 << EliminationStack.dfs_back().first << ","
4013 << EliminationStack.dfs_back().second << ")\n");
4014 }
4015
4016 LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << MemberDFSIn << ","
4017 << MemberDFSOut << ")\n");
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031 bool ShouldPush = Def && EliminationStack.empty();
4032 bool OutOfScope =
4033 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
4034
4035 if (OutOfScope || ShouldPush) {
4036
4037 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4038 bool ShouldPush = Def && EliminationStack.empty();
4039 if (ShouldPush) {
4040 EliminationStack.push_back(Def, MemberDFSIn, MemberDFSOut);
4041 }
4042 }
4043
4044
4045
4046 if (Def) {
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4060 if (!EliminationStack.empty() && DefI && !FromStore) {
4061 Value *DominatingLeader = EliminationStack.back();
4062 if (DominatingLeader != Def) {
4063
4064
4066
4069
4070 for (auto *DVR : DVRUsers)
4071 DVR->replaceVariableLocationOp(DefI, DominatingLeader);
4072
4073 markInstructionForDeletion(DefI);
4074 }
4075 }
4076 continue;
4077 }
4078
4079
4080
4082 "Current def should have been an instruction");
4084 "Current user should have been an instruction");
4085
4086
4087
4088
4089
4091 if (InstructionsToErase.count(InstUse)) {
4092 auto &UseCount = UseCounts[U->get()];
4093 if (--UseCount == 0) {
4095 }
4096 }
4097
4098
4099
4100 if (EliminationStack.empty())
4101 continue;
4102
4103 Value *DominatingLeader = EliminationStack.back();
4104
4107 if (BC->getType() == BC->getOperand(0)->getType() &&
4108 PredInfo->getPredicateInfoFor(DominatingLeader)) {
4109 SSACopy = BC;
4110 DominatingLeader = BC->getOperand(0);
4111 }
4112 }
4113
4114
4115 if (U->get() == DominatingLeader)
4116 continue;
4117
4118
4119
4120
4122 auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
4123 if (!PI || DominatingLeader != PI->OriginalOp)
4125
4127 << "Found replacement " << *DominatingLeader << " for "
4128 << *U->get() << " in " << *(U->getUser()) << "\n");
4129 U->set(DominatingLeader);
4130
4131
4132 auto &LeaderUseCount = UseCounts[DominatingLeader];
4133
4134 if (LeaderUseCount == 0 && isa(DominatingLeader))
4136
4137
4138 if (SSACopy) {
4139 auto It = UseCounts.find(SSACopy);
4140 if (It != UseCounts.end()) {
4141 unsigned &IIUseCount = It->second;
4142 if (--IIUseCount == 0)
4143 ProbablyDead.insert(SSACopy);
4144 }
4145 }
4146 ++LeaderUseCount;
4147 AnythingReplaced = true;
4148 }
4149 }
4150 }
4151
4152
4153
4154 for (auto *I : ProbablyDead)
4156 markInstructionForDeletion(I);
4157
4158
4159 CongruenceClass::MemberSet MembersLeft;
4160 for (auto *Member : *CC)
4163 MembersLeft.insert(Member);
4164 CC->swap(MembersLeft);
4165
4166
4167 if (CC->getStoreCount() > 0) {
4168 convertClassToLoadsAndStores(*CC, PossibleDeadStores);
4170 ValueDFSStack EliminationStack;
4171 for (auto &VD : PossibleDeadStores) {
4172 int MemberDFSIn = VD.DFSIn;
4173 int MemberDFSOut = VD.DFSOut;
4175 if (EliminationStack.empty() ||
4176 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) {
4177
4178 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4179 if (EliminationStack.empty()) {
4180 EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
4181 continue;
4182 }
4183 }
4184
4186 continue;
4187 assert(!EliminationStack.empty());
4189 (void)Leader;
4191
4192 LLVM_DEBUG(dbgs() << "Marking dead store " << *Member
4193 << " that is dominated by " << *Leader << "\n");
4194 markInstructionForDeletion(Member);
4195 CC->erase(Member);
4196 ++NumGVNDeadStores;
4197 }
4198 }
4199 }
4200 return AnythingReplaced;
4201}
4202
4203
4204
4205
4206
4207
4208unsigned int NewGVN::getRank(const Value *V) const {
4209
4210
4211
4212
4213
4215 return 3;
4217 return 1;
4219 return 2;
4221 return 0;
4223 return 4 + A->getArgNo();
4224
4225
4226
4227 unsigned Result = InstrToDFSNum(V);
4228 if (Result > 0)
4229 return 5 + NumFuncArgs + Result;
4230
4231 return ~0;
4232}
4233
4234
4235
4236bool NewGVN::shouldSwapOperands(const Value *A, const Value *B) const {
4237
4238
4239
4240 return std::make_pair(getRank(A), A) > std::make_pair(getRank(B), B);
4241}
4242
4243bool NewGVN::shouldSwapOperandsForPredicate(const Value *A, const Value *B,
4244 const BitCastInst *I) const {
4245 if (shouldSwapOperands(A, B)) {
4246 PredicateSwapChoice[I] = B;
4247 return true;
4248 }
4249
4251 if (LookupResult != PredicateSwapChoice.end()) {
4253 if (SeenPredicate) {
4254
4255 if (SeenPredicate == B)
4256 return true;
4257 else
4259 }
4260 }
4261 return false;
4262}
4263
4265
4266
4267
4274 NewGVN(F, &DT, &AC, &TLI, &AA, &MSSA, F.getDataLayout())
4275 .runGVN();
4280 return PA;
4281}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
Unify divergent function exit nodes
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Function Alias Analysis false
This file defines the BumpPtrAllocator interface.
This file implements the BitVector class.
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")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-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.
early cse Early CSE w MemorySSA
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 template class that should be specialized by classes that...
This defines the Use class.
static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset, uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs, llvm::Error &Err)
A Lookup helper functions.
const size_t AbstractManglingParser< Derived, Alloc >::NumOps
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Branch Probability Basic Block static false std::string getBlockName(const MachineBasicBlock *BB)
Helper to print the name of a MBB.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
static bool alwaysAvailable(Value *V)
Definition NewGVN.cpp:1034
static Value * getCopyOf(const Value *V)
Definition NewGVN.cpp:1004
static bool isCopyOfPHI(const Value *V, const PHINode *PN)
Definition NewGVN.cpp:1012
static bool isCopyOfAPHI(const Value *V)
Definition NewGVN.cpp:1016
static bool okayForPHIOfOps(const Instruction *I)
Definition NewGVN.cpp:2607
static cl::opt< bool > EnableStoreRefinement("enable-store-refinement", cl::init(false), cl::Hidden)
static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS)
Definition NewGVN.cpp:921
static cl::opt< bool > EnablePhiOfOps("enable-phi-of-ops", cl::init(true), cl::Hidden)
Currently, the generation "phi of ops" can result in correctness issues.
This file provides the interface for LLVM's Global Value Numbering pass.
This file defines the PointerIntPair class.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file implements the PredicateInfo analysis, which creates an Extended SSA form for operations us...
const SmallVectorImpl< MachineOperand > & Cond
bool isDead(const MachineInstr &MI, const MachineRegisterInfo &MRI)
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)
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton 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.
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.
const Function * getParent() const
Return the enclosing method, or null if none.
reverse_iterator rbegin()
InstListType::reverse_iterator reverse_iterator
LLVM_ABI 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
bool isConvergent() const
Determine if the invoke is convergent.
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,...
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
static LLVM_ABI 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 CounterState getCounterState(CounterInfo &Info)
static void setCounterState(CounterInfo &Info, CounterState State)
static bool shouldExecute(CounterInfo &Counter)
static bool isCounterSet(CounterInfo &Info)
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.
LLVM_ABI 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
void allocateOperands(RecyclerType &Recycler, BumpPtrAllocator &Allocator)
~BasicExpression() override
bool equals(const Expression &Other) const override
Definition NewGVN.cpp:941
~CallExpression() override
void setOpcode(unsigned opcode)
bool equals(const Expression &Other) const override
Definition NewGVN.cpp:927
~LoadExpression() override
bool equals(const Expression &Other) const override
~PHIExpression() override
bool equals(const Expression &Other) const override
Definition NewGVN.cpp:931
~StoreExpression() override
Value * getStoredValue() const
static LLVM_ABI std::optional< bool > isImpliedByMatchingCmp(CmpPredicate Pred1, CmpPredicate Pred2)
Determine if Pred1 implies Pred2 is true, false, or if nothing can be inferred about the implication,...
LLVM_ABI bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
LLVM_ABI bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
LLVM_ABI void insertBefore(InstListType::iterator InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified position.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
Value * getPointerOperand()
BasicBlock * getBlock() const
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.
LLVM_ABI 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.
PreservedAnalyses run(Function &F, AnalysisManager< Function > &AM)
Run the pass over the function.
Definition NewGVN.cpp:4264
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
PointerIntPair - This class implements a pair of a pointer and small integer.
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
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.
PreservedAnalyses & preserve()
Mark an analysis as preserved.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
SmallPtrSetIterator< PtrType > const_iterator
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
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)
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool isPointerTy() const
True if this is an instance of PointerType.
static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)
static LLVM_ABI 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.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
std::pair< iterator, bool > insert(const ValueT &V)
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.
const ParentTy * getParent() const
self_iterator getIterator()
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.
Abstract Attribute helper functions.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
bool match(Val *V, const Pattern &P)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr, StoreInst *DepSI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the store at D...
Constant * getConstantValueForLoad(Constant *SrcVal, unsigned Offset, Type *LoadTy, const DataLayout &DL)
int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the load at De...
Constant * getConstantMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, Type *LoadTy, const DataLayout &DL)
int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr, MemIntrinsic *DepMI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the memory int...
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
std::vector< std::optional< ExecutorSymbolDef > > LookupResult
NodeAddr< DefNode * > Def
NodeAddr< UseNode * > Use
NodeAddr< NodeBase * > Node
friend class Instruction
Iterator for Instructions in a `BasicBlock.
LLVM_ABI Instruction & back() const
LLVM_ABI iterator begin() const
This is an optimization pass for GlobalISel generic memory operations.
FunctionAddr VTableAddr Value
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI Value * simplifyGEPInst(Type *SrcTy, Value *Ptr, ArrayRef< Value * > Indices, GEPNoWrapFlags NW, const SimplifyQuery &Q)
Given operands for a GetElementPtrInst, fold the result or return null.
LLVM_ABI 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.
decltype(auto) dyn_cast(const From &Val)
dyn_cast - Return the argument parameter cast to the specified type.
LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
auto successors(const MachineBasicBlock *BB)
SDValue getStoredValue(SDValue Op)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
mapped_iterator< ItTy, FuncTy > map_iterator(ItTy I, FuncTy F)
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
bool isa_and_nonnull(const Y &Val)
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
LLVM_ABI Value * simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
DomTreeNodeBase< BasicBlock > DomTreeNode
auto dyn_cast_or_null(const Y &Val)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
auto reverse(ContainerTy &&C)
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI bool wouldInstructionBeTriviallyDead(const Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used.
LLVM_ABI 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...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
MutableArrayRef(T &OneElt) -> MutableArrayRef< T >
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
LLVM_ABI bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
LLVM_ABI Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
DWARFExpression::Operation Op
ArrayRef(const T &OneElt) -> ArrayRef< T >
OutputIt copy(R &&Range, OutputIt Out)
decltype(auto) cast(const From &Val)
cast - Return the argument parameter cast to the specified type.
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.
LLVM_ABI Value * simplifyCmpInst(CmpPredicate Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
AAResults AliasAnalysis
Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.
LLVM_ABI Value * simplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, const SimplifyQuery &Q)
Given operands for a SelectInst, fold the result or return null.
LLVM_ABI void findDbgUsers(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)
Finds the debug info records describing a value.
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.
Definition NewGVN.cpp:3542
int LocalNum
Definition NewGVN.cpp:3545
Use * U
Definition NewGVN.cpp:3551
PointerIntPair< Value *, 1, bool > Def
Definition NewGVN.cpp:3550
int DFSIn
Definition NewGVN.cpp:3543
int DFSOut
Definition NewGVN.cpp:3544
bool operator<(const ValueDFS &Other) const
Definition NewGVN.cpp:3553
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
static unsigned getHashValue(const ExactEqualsExpression &E)
Definition NewGVN.cpp:461
static unsigned getHashValue(const Expression *E)
Definition NewGVN.cpp:457
static const Expression * getTombstoneKey()
Definition NewGVN.cpp:451
static bool isEqual(const Expression *LHS, const Expression *RHS)
Definition NewGVN.cpp:471
static const Expression * getEmptyKey()
Definition NewGVN.cpp:445
static bool isEqual(const ExactEqualsExpression &LHS, const Expression *RHS)
Definition NewGVN.cpp:465
An information struct used to provide DenseMap with the various necessary components for a given valu...
SimplifyQuery getWithInstruction(const Instruction *I) const