1 //===---- NewGVN.cpp - Global Value Numbering Pass --------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// This file implements the new LLVM's Global Value Numbering pass.
11 /// GVN partitions values computed by a function into congruence classes.
12 /// Values ending up in the same congruence class are guaranteed to be the same
13 /// for every execution of the program. In that respect, congruency is a
14 /// compile-time approximation of equivalence of values at runtime.
15 /// The algorithm implemented here uses a sparse formulation and it's based
16 /// on the ideas described in the paper:
17 /// "A Sparse Algorithm for Predicated Global Value Numbering" from
20 //===----------------------------------------------------------------------===//
22 #include "llvm/Transforms/Scalar/NewGVN.h"
23 #include "llvm/ADT/BitVector.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/DenseSet.h"
26 #include "llvm/ADT/DepthFirstIterator.h"
27 #include "llvm/ADT/Hashing.h"
28 #include "llvm/ADT/MapVector.h"
29 #include "llvm/ADT/PostOrderIterator.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/ADT/SmallPtrSet.h"
32 #include "llvm/ADT/SmallSet.h"
33 #include "llvm/ADT/SparseBitVector.h"
34 #include "llvm/ADT/Statistic.h"
35 #include "llvm/ADT/TinyPtrVector.h"
36 #include "llvm/Analysis/AliasAnalysis.h"
37 #include "llvm/Analysis/AssumptionCache.h"
38 #include "llvm/Analysis/CFG.h"
39 #include "llvm/Analysis/CFGPrinter.h"
40 #include "llvm/Analysis/ConstantFolding.h"
41 #include "llvm/Analysis/GlobalsModRef.h"
42 #include "llvm/Analysis/InstructionSimplify.h"
43 #include "llvm/Analysis/Loads.h"
44 #include "llvm/Analysis/MemoryBuiltins.h"
45 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
46 #include "llvm/Analysis/MemoryLocation.h"
47 #include "llvm/Analysis/PHITransAddr.h"
48 #include "llvm/Analysis/TargetLibraryInfo.h"
49 #include "llvm/Analysis/ValueTracking.h"
50 #include "llvm/IR/DataLayout.h"
51 #include "llvm/IR/Dominators.h"
52 #include "llvm/IR/GlobalVariable.h"
53 #include "llvm/IR/IRBuilder.h"
54 #include "llvm/IR/IntrinsicInst.h"
55 #include "llvm/IR/LLVMContext.h"
56 #include "llvm/IR/Metadata.h"
57 #include "llvm/IR/PatternMatch.h"
58 #include "llvm/IR/PredIteratorCache.h"
59 #include "llvm/IR/Type.h"
60 #include "llvm/Support/Allocator.h"
61 #include "llvm/Support/CommandLine.h"
62 #include "llvm/Support/Debug.h"
63 #include "llvm/Transforms/Scalar.h"
64 #include "llvm/Transforms/Scalar/GVNExpression.h"
65 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
66 #include "llvm/Transforms/Utils/Local.h"
67 #include "llvm/Transforms/Utils/MemorySSA.h"
68 #include "llvm/Transforms/Utils/SSAUpdater.h"
69 #include <unordered_map>
73 using namespace PatternMatch;
74 using namespace llvm::GVNExpression;
76 #define DEBUG_TYPE "newgvn"
78 STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted");
79 STATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted");
80 STATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified");
81 STATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same");
83 //===----------------------------------------------------------------------===//
85 //===----------------------------------------------------------------------===//
89 namespace GVNExpression {
90 Expression::~Expression() = default;
91 BasicExpression::~BasicExpression() = default;
92 CallExpression::~CallExpression() = default;
93 LoadExpression::~LoadExpression() = default;
94 StoreExpression::~StoreExpression() = default;
95 AggregateValueExpression::~AggregateValueExpression() = default;
96 PHIExpression::~PHIExpression() = default;
100 // Congruence classes represent the set of expressions/instructions
101 // that are all the same *during some scope in the function*.
102 // That is, because of the way we perform equality propagation, and
103 // because of memory value numbering, it is not correct to assume
104 // you can willy-nilly replace any member with any other at any
105 // point in the function.
107 // For any Value in the Member set, it is valid to replace any dominated member
110 // Every congruence class has a leader, and the leader is used to
111 // symbolize instructions in a canonical way (IE every operand of an
112 // instruction that is a member of the same congruence class will
113 // always be replaced with leader during symbolization).
114 // To simplify symbolization, we keep the leader as a constant if class can be
115 // proved to be a constant value.
116 // Otherwise, the leader is a randomly chosen member of the value set, it does
117 // not matter which one is chosen.
118 // Each congruence class also has a defining expression,
119 // though the expression may be null. If it exists, it can be used for forward
120 // propagation and reassociation of values.
122 struct CongruenceClass {
123 using MemberSet = SmallPtrSet<Value *, 4>;
125 // Representative leader.
126 Value *RepLeader = nullptr;
127 // Defining Expression.
128 const Expression *DefiningExpr = nullptr;
129 // Actual members of this class.
132 // True if this class has no members left. This is mainly used for assertion
133 // purposes, and for skipping empty classes.
136 explicit CongruenceClass(unsigned ID) : ID(ID) {}
137 CongruenceClass(unsigned ID, Value *Leader, const Expression *E)
138 : ID(ID), RepLeader(Leader), DefiningExpr(E) {}
142 template <> struct DenseMapInfo<const Expression *> {
143 static const Expression *getEmptyKey() {
144 auto Val = static_cast<uintptr_t>(-1);
145 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
146 return reinterpret_cast<const Expression *>(Val);
148 static const Expression *getTombstoneKey() {
149 auto Val = static_cast<uintptr_t>(~1U);
150 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
151 return reinterpret_cast<const Expression *>(Val);
153 static unsigned getHashValue(const Expression *V) {
154 return static_cast<unsigned>(V->getHashValue());
156 static bool isEqual(const Expression *LHS, const Expression *RHS) {
159 if (LHS == getTombstoneKey() || RHS == getTombstoneKey() ||
160 LHS == getEmptyKey() || RHS == getEmptyKey())
165 } // end namespace llvm
167 class NewGVN : public FunctionPass {
169 const DataLayout *DL;
170 const TargetLibraryInfo *TLI;
174 MemorySSAWalker *MSSAWalker;
175 BumpPtrAllocator ExpressionAllocator;
176 ArrayRecycler<Value *> ArgRecycler;
178 // Congruence class info.
179 CongruenceClass *InitialClass;
180 std::vector<CongruenceClass *> CongruenceClasses;
181 unsigned NextCongruenceNum;
184 DenseMap<Value *, CongruenceClass *> ValueToClass;
185 DenseMap<Value *, const Expression *> ValueToExpression;
187 // A table storing which memorydefs/phis represent a memory state provably
188 // equivalent to another memory state.
189 // We could use the congruence class machinery, but the MemoryAccess's are
190 // abstract memory states, so they can only ever be equivalent to each other,
191 // and not to constants, etc.
192 DenseMap<const MemoryAccess *, MemoryAccess *> MemoryAccessEquiv;
194 // Expression to class mapping.
195 using ExpressionClassMap = DenseMap<const Expression *, CongruenceClass *>;
196 ExpressionClassMap ExpressionToClass;
198 // Which values have changed as a result of leader changes.
199 SmallPtrSet<Value *, 8> ChangedValues;
201 // Reachability info.
202 using BlockEdge = BasicBlockEdge;
203 DenseSet<BlockEdge> ReachableEdges;
204 SmallPtrSet<const BasicBlock *, 8> ReachableBlocks;
206 // This is a bitvector because, on larger functions, we may have
207 // thousands of touched instructions at once (entire blocks,
208 // instructions with hundreds of uses, etc). Even with optimization
209 // for when we mark whole blocks as touched, when this was a
210 // SmallPtrSet or DenseSet, for some functions, we spent >20% of all
211 // the time in GVN just managing this list. The bitvector, on the
212 // other hand, efficiently supports test/set/clear of both
213 // individual and ranges, as well as "find next element" This
214 // enables us to use it as a worklist with essentially 0 cost.
215 BitVector TouchedInstructions;
217 DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;
218 DenseMap<const DomTreeNode *, std::pair<unsigned, unsigned>>
222 // Debugging for how many times each block and instruction got processed.
223 DenseMap<const Value *, unsigned> ProcessedCount;
227 DenseMap<const BasicBlock *, std::pair<int, int>> DFSDomMap;
228 DenseMap<const Value *, unsigned> InstrDFS;
229 SmallVector<Value *, 32> DFSToInstr;
232 SmallPtrSet<Instruction *, 8> InstructionsToErase;
235 static char ID; // Pass identification, replacement for typeid.
236 NewGVN() : FunctionPass(ID) {
237 initializeNewGVNPass(*PassRegistry::getPassRegistry());
240 bool runOnFunction(Function &F) override;
241 bool runGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
242 TargetLibraryInfo *TLI, AliasAnalysis *AA, MemorySSA *MSSA);
245 // This transformation requires dominator postdominator info.
246 void getAnalysisUsage(AnalysisUsage &AU) const override {
247 AU.addRequired<AssumptionCacheTracker>();
248 AU.addRequired<DominatorTreeWrapperPass>();
249 AU.addRequired<TargetLibraryInfoWrapperPass>();
250 AU.addRequired<MemorySSAWrapperPass>();
251 AU.addRequired<AAResultsWrapperPass>();
253 AU.addPreserved<DominatorTreeWrapperPass>();
254 AU.addPreserved<GlobalsAAWrapperPass>();
257 // Expression handling.
258 const Expression *createExpression(Instruction *, const BasicBlock *);
259 const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *,
261 PHIExpression *createPHIExpression(Instruction *);
262 const VariableExpression *createVariableExpression(Value *);
263 const ConstantExpression *createConstantExpression(Constant *);
264 const Expression *createVariableOrConstant(Value *V, const BasicBlock *B);
265 const UnknownExpression *createUnknownExpression(Instruction *);
266 const StoreExpression *createStoreExpression(StoreInst *, MemoryAccess *,
268 LoadExpression *createLoadExpression(Type *, Value *, LoadInst *,
269 MemoryAccess *, const BasicBlock *);
271 const CallExpression *createCallExpression(CallInst *, MemoryAccess *,
273 const AggregateValueExpression *
274 createAggregateValueExpression(Instruction *, const BasicBlock *);
275 bool setBasicExpressionInfo(Instruction *, BasicExpression *,
278 // Congruence class handling.
279 CongruenceClass *createCongruenceClass(Value *Leader, const Expression *E) {
280 auto *result = new CongruenceClass(NextCongruenceNum++, Leader, E);
281 CongruenceClasses.emplace_back(result);
285 CongruenceClass *createSingletonCongruenceClass(Value *Member) {
286 CongruenceClass *CClass = createCongruenceClass(Member, nullptr);
287 CClass->Members.insert(Member);
288 ValueToClass[Member] = CClass;
291 void initializeCongruenceClasses(Function &F);
293 // Value number an Instruction or MemoryPhi.
294 void valueNumberMemoryPhi(MemoryPhi *);
295 void valueNumberInstruction(Instruction *);
297 // Symbolic evaluation.
298 const Expression *checkSimplificationResults(Expression *, Instruction *,
300 const Expression *performSymbolicEvaluation(Value *, const BasicBlock *);
301 const Expression *performSymbolicLoadEvaluation(Instruction *,
303 const Expression *performSymbolicStoreEvaluation(Instruction *,
305 const Expression *performSymbolicCallEvaluation(Instruction *,
307 const Expression *performSymbolicPHIEvaluation(Instruction *,
309 bool setMemoryAccessEquivTo(MemoryAccess *From, MemoryAccess *To);
310 const Expression *performSymbolicAggrValueEvaluation(Instruction *,
313 // Congruence finding.
314 // Templated to allow them to work both on BB's and BB-edges.
316 Value *lookupOperandLeader(Value *, const User *, const T &) const;
317 void performCongruenceFinding(Value *, const Expression *);
319 // Reachability handling.
320 void updateReachableEdge(BasicBlock *, BasicBlock *);
321 void processOutgoingEdges(TerminatorInst *, BasicBlock *);
322 bool isOnlyReachableViaThisEdge(const BasicBlockEdge &) const;
323 Value *findConditionEquivalence(Value *, BasicBlock *) const;
324 MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const;
328 void convertDenseToDFSOrdered(CongruenceClass::MemberSet &,
329 std::vector<ValueDFS> &);
331 bool eliminateInstructions(Function &);
332 void replaceInstruction(Instruction *, Value *);
333 void markInstructionForDeletion(Instruction *);
334 void deleteInstructionsInBlock(BasicBlock *);
336 // New instruction creation.
337 void handleNewInstruction(Instruction *){};
338 void markUsersTouched(Value *);
339 void markMemoryUsersTouched(MemoryAccess *);
342 void cleanupTables();
343 std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
344 void updateProcessedCount(Value *V);
345 void verifyMemoryCongruency();
350 // createGVNPass - The public interface to this file.
351 FunctionPass *llvm::createNewGVNPass() { return new NewGVN(); }
353 template <typename T>
354 static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS) {
355 if ((!isa<LoadExpression>(RHS) && !isa<StoreExpression>(RHS)) ||
356 !LHS.BasicExpression::equals(RHS)) {
358 } else if (const auto *L = dyn_cast<LoadExpression>(&RHS)) {
359 if (LHS.getDefiningAccess() != L->getDefiningAccess())
361 } else if (const auto *S = dyn_cast<StoreExpression>(&RHS)) {
362 if (LHS.getDefiningAccess() != S->getDefiningAccess())
368 bool LoadExpression::equals(const Expression &Other) const {
369 return equalsLoadStoreHelper(*this, Other);
372 bool StoreExpression::equals(const Expression &Other) const {
373 return equalsLoadStoreHelper(*this, Other);
377 static std::string getBlockName(const BasicBlock *B) {
378 return DOTGraphTraits<const Function *>::getSimpleNodeLabel(B, nullptr);
382 INITIALIZE_PASS_BEGIN(NewGVN, "newgvn", "Global Value Numbering", false, false)
383 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
384 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
385 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
386 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
387 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
388 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
389 INITIALIZE_PASS_END(NewGVN, "newgvn", "Global Value Numbering", false, false)
391 PHIExpression *NewGVN::createPHIExpression(Instruction *I) {
392 BasicBlock *PhiBlock = I->getParent();
393 auto *PN = cast<PHINode>(I);
394 auto *E = new (ExpressionAllocator)
395 PHIExpression(PN->getNumOperands(), I->getParent());
397 E->allocateOperands(ArgRecycler, ExpressionAllocator);
398 E->setType(I->getType());
399 E->setOpcode(I->getOpcode());
401 auto ReachablePhiArg = [&](const Use &U) {
402 return ReachableBlocks.count(PN->getIncomingBlock(U));
405 // Filter out unreachable operands
406 auto Filtered = make_filter_range(PN->operands(), ReachablePhiArg);
408 std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
409 [&](const Use &U) -> Value * {
410 // Don't try to transform self-defined phis
413 const BasicBlockEdge BBE(PN->getIncomingBlock(U), PhiBlock);
414 return lookupOperandLeader(U, I, BBE);
419 // Set basic expression info (Arguments, type, opcode) for Expression
420 // E from Instruction I in block B.
421 bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E,
422 const BasicBlock *B) {
423 bool AllConstant = true;
424 if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
425 E->setType(GEP->getSourceElementType());
427 E->setType(I->getType());
428 E->setOpcode(I->getOpcode());
429 E->allocateOperands(ArgRecycler, ExpressionAllocator);
431 // Transform the operand array into an operand leader array, and keep track of
432 // whether all members are constant.
433 std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) {
434 auto Operand = lookupOperandLeader(O, I, B);
435 AllConstant &= isa<Constant>(Operand);
442 const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
443 Value *Arg1, Value *Arg2,
444 const BasicBlock *B) {
445 auto *E = new (ExpressionAllocator) BasicExpression(2);
448 E->setOpcode(Opcode);
449 E->allocateOperands(ArgRecycler, ExpressionAllocator);
450 if (Instruction::isCommutative(Opcode)) {
451 // Ensure that commutative instructions that only differ by a permutation
452 // of their operands get the same value number by sorting the operand value
453 // numbers. Since all commutative instructions have two operands it is more
454 // efficient to sort by hand rather than using, say, std::sort.
456 std::swap(Arg1, Arg2);
458 E->op_push_back(lookupOperandLeader(Arg1, nullptr, B));
459 E->op_push_back(lookupOperandLeader(Arg2, nullptr, B));
461 Value *V = SimplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), *DL, TLI,
463 if (const Expression *SimplifiedE = checkSimplificationResults(E, nullptr, V))
468 // Take a Value returned by simplification of Expression E/Instruction
469 // I, and see if it resulted in a simpler expression. If so, return
471 // TODO: Once finished, this should not take an Instruction, we only
472 // use it for printing.
473 const Expression *NewGVN::checkSimplificationResults(Expression *E,
474 Instruction *I, Value *V) {
477 if (auto *C = dyn_cast<Constant>(V)) {
479 DEBUG(dbgs() << "Simplified " << *I << " to "
480 << " constant " << *C << "\n");
481 NumGVNOpsSimplified++;
482 assert(isa<BasicExpression>(E) &&
483 "We should always have had a basic expression here");
485 cast<BasicExpression>(E)->deallocateOperands(ArgRecycler);
486 ExpressionAllocator.Deallocate(E);
487 return createConstantExpression(C);
488 } else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
490 DEBUG(dbgs() << "Simplified " << *I << " to "
491 << " variable " << *V << "\n");
492 cast<BasicExpression>(E)->deallocateOperands(ArgRecycler);
493 ExpressionAllocator.Deallocate(E);
494 return createVariableExpression(V);
497 CongruenceClass *CC = ValueToClass.lookup(V);
498 if (CC && CC->DefiningExpr) {
500 DEBUG(dbgs() << "Simplified " << *I << " to "
501 << " expression " << *V << "\n");
502 NumGVNOpsSimplified++;
503 assert(isa<BasicExpression>(E) &&
504 "We should always have had a basic expression here");
505 cast<BasicExpression>(E)->deallocateOperands(ArgRecycler);
506 ExpressionAllocator.Deallocate(E);
507 return CC->DefiningExpr;
512 const Expression *NewGVN::createExpression(Instruction *I,
513 const BasicBlock *B) {
515 auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands());
517 bool AllConstant = setBasicExpressionInfo(I, E, B);
519 if (I->isCommutative()) {
520 // Ensure that commutative instructions that only differ by a permutation
521 // of their operands get the same value number by sorting the operand value
522 // numbers. Since all commutative instructions have two operands it is more
523 // efficient to sort by hand rather than using, say, std::sort.
524 assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
525 if (E->getOperand(0) > E->getOperand(1))
526 E->swapOperands(0, 1);
529 // Perform simplificaiton
530 // TODO: Right now we only check to see if we get a constant result.
531 // We may get a less than constant, but still better, result for
536 // We should handle this by simply rewriting the expression.
537 if (auto *CI = dyn_cast<CmpInst>(I)) {
538 // Sort the operand value numbers so x<y and y>x get the same value
540 CmpInst::Predicate Predicate = CI->getPredicate();
541 if (E->getOperand(0) > E->getOperand(1)) {
542 E->swapOperands(0, 1);
543 Predicate = CmpInst::getSwappedPredicate(Predicate);
545 E->setOpcode((CI->getOpcode() << 8) | Predicate);
546 // TODO: 25% of our time is spent in SimplifyCmpInst with pointer operands
547 // TODO: Since we noop bitcasts, we may need to check types before
548 // simplifying, so that we don't end up simplifying based on a wrong
549 // type assumption. We should clean this up so we can use constants of the
552 assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
553 "Wrong types on cmp instruction");
554 if ((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
555 E->getOperand(1)->getType() == I->getOperand(1)->getType())) {
556 Value *V = SimplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1),
558 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
561 } else if (isa<SelectInst>(I)) {
562 if (isa<Constant>(E->getOperand(0)) ||
563 (E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
564 E->getOperand(2)->getType() == I->getOperand(2)->getType())) {
565 Value *V = SimplifySelectInst(E->getOperand(0), E->getOperand(1),
566 E->getOperand(2), *DL, TLI, DT, AC);
567 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
570 } else if (I->isBinaryOp()) {
571 Value *V = SimplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1),
573 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
575 } else if (auto *BI = dyn_cast<BitCastInst>(I)) {
576 Value *V = SimplifyInstruction(BI, *DL, TLI, DT, AC);
577 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
579 } else if (isa<GetElementPtrInst>(I)) {
580 Value *V = SimplifyGEPInst(E->getType(),
581 ArrayRef<Value *>(E->op_begin(), E->op_end()),
583 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
585 } else if (AllConstant) {
586 // We don't bother trying to simplify unless all of the operands
588 // TODO: There are a lot of Simplify*'s we could call here, if we
589 // wanted to. The original motivating case for this code was a
590 // zext i1 false to i8, which we don't have an interface to
591 // simplify (IE there is no SimplifyZExt).
593 SmallVector<Constant *, 8> C;
594 for (Value *Arg : E->operands())
595 C.emplace_back(cast<Constant>(Arg));
597 if (Value *V = ConstantFoldInstOperands(I, C, *DL, TLI))
598 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
604 const AggregateValueExpression *
605 NewGVN::createAggregateValueExpression(Instruction *I, const BasicBlock *B) {
606 if (auto *II = dyn_cast<InsertValueInst>(I)) {
607 auto *E = new (ExpressionAllocator)
608 AggregateValueExpression(I->getNumOperands(), II->getNumIndices());
609 setBasicExpressionInfo(I, E, B);
610 E->allocateIntOperands(ExpressionAllocator);
611 std::copy(II->idx_begin(), II->idx_end(), int_op_inserter(E));
613 } else if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
614 auto *E = new (ExpressionAllocator)
615 AggregateValueExpression(I->getNumOperands(), EI->getNumIndices());
616 setBasicExpressionInfo(EI, E, B);
617 E->allocateIntOperands(ExpressionAllocator);
618 std::copy(EI->idx_begin(), EI->idx_end(), int_op_inserter(E));
621 llvm_unreachable("Unhandled type of aggregate value operation");
624 const VariableExpression *NewGVN::createVariableExpression(Value *V) {
625 auto *E = new (ExpressionAllocator) VariableExpression(V);
626 E->setOpcode(V->getValueID());
630 const Expression *NewGVN::createVariableOrConstant(Value *V,
631 const BasicBlock *B) {
632 auto Leader = lookupOperandLeader(V, nullptr, B);
633 if (auto *C = dyn_cast<Constant>(Leader))
634 return createConstantExpression(C);
635 return createVariableExpression(Leader);
638 const ConstantExpression *NewGVN::createConstantExpression(Constant *C) {
639 auto *E = new (ExpressionAllocator) ConstantExpression(C);
640 E->setOpcode(C->getValueID());
644 const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) {
645 auto *E = new (ExpressionAllocator) UnknownExpression(I);
646 E->setOpcode(I->getOpcode());
650 const CallExpression *NewGVN::createCallExpression(CallInst *CI,
652 const BasicBlock *B) {
653 // FIXME: Add operand bundles for calls.
655 new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, HV);
656 setBasicExpressionInfo(CI, E, B);
660 // See if we have a congruence class and leader for this operand, and if so,
661 // return it. Otherwise, return the operand itself.
663 Value *NewGVN::lookupOperandLeader(Value *V, const User *U, const T &B) const {
664 CongruenceClass *CC = ValueToClass.lookup(V);
665 if (CC && (CC != InitialClass))
666 return CC->RepLeader;
670 MemoryAccess *NewGVN::lookupMemoryAccessEquiv(MemoryAccess *MA) const {
671 MemoryAccess *Result = MemoryAccessEquiv.lookup(MA);
672 return Result ? Result : MA;
675 LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp,
676 LoadInst *LI, MemoryAccess *DA,
677 const BasicBlock *B) {
678 auto *E = new (ExpressionAllocator) LoadExpression(1, LI, DA);
679 E->allocateOperands(ArgRecycler, ExpressionAllocator);
680 E->setType(LoadType);
682 // Give store and loads same opcode so they value number together.
684 E->op_push_back(lookupOperandLeader(PointerOp, LI, B));
686 E->setAlignment(LI->getAlignment());
688 // TODO: Value number heap versions. We may be able to discover
689 // things alias analysis can't on it's own (IE that a store and a
690 // load have the same value, and thus, it isn't clobbering the load).
694 const StoreExpression *NewGVN::createStoreExpression(StoreInst *SI,
696 const BasicBlock *B) {
698 new (ExpressionAllocator) StoreExpression(SI->getNumOperands(), SI, DA);
699 E->allocateOperands(ArgRecycler, ExpressionAllocator);
700 E->setType(SI->getValueOperand()->getType());
702 // Give store and loads same opcode so they value number together.
704 E->op_push_back(lookupOperandLeader(SI->getPointerOperand(), SI, B));
706 // TODO: Value number heap versions. We may be able to discover
707 // things alias analysis can't on it's own (IE that a store and a
708 // load have the same value, and thus, it isn't clobbering the load).
712 const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I,
713 const BasicBlock *B) {
714 // Unlike loads, we never try to eliminate stores, so we do not check if they
715 // are simple and avoid value numbering them.
716 auto *SI = cast<StoreInst>(I);
717 // If this store's memorydef stores the same value as the last store, the
718 // memory accesses are equivalent.
719 // Get the expression, if any, for the RHS of the MemoryDef.
720 MemoryAccess *StoreAccess = MSSA->getMemoryAccess(SI);
721 MemoryAccess *StoreRHS = lookupMemoryAccessEquiv(
722 cast<MemoryDef>(StoreAccess)->getDefiningAccess());
723 const Expression *OldStore = createStoreExpression(SI, StoreRHS, B);
724 // See if this store expression already has a value, and it's the same as our
725 // current store. FIXME: Right now, we only do this for simple stores.
726 if (SI->isSimple()) {
727 CongruenceClass *CC = ExpressionToClass.lookup(OldStore);
728 if (CC && CC->DefiningExpr && isa<StoreExpression>(CC->DefiningExpr) &&
729 CC->RepLeader == lookupOperandLeader(SI->getValueOperand(), SI, B))
730 return createStoreExpression(SI, StoreRHS, B);
733 return createStoreExpression(SI, StoreAccess, B);
736 const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I,
737 const BasicBlock *B) {
738 auto *LI = cast<LoadInst>(I);
740 // We can eliminate in favor of non-simple loads, but we won't be able to
741 // eliminate the loads themselves.
745 Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand(), I, B);
746 // Load of undef is undef.
747 if (isa<UndefValue>(LoadAddressLeader))
748 return createConstantExpression(UndefValue::get(LI->getType()));
750 MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(I);
752 if (!MSSA->isLiveOnEntryDef(DefiningAccess)) {
753 if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
754 Instruction *DefiningInst = MD->getMemoryInst();
755 // If the defining instruction is not reachable, replace with undef.
756 if (!ReachableBlocks.count(DefiningInst->getParent()))
757 return createConstantExpression(UndefValue::get(LI->getType()));
761 const Expression *E =
762 createLoadExpression(LI->getType(), LI->getPointerOperand(), LI,
763 lookupMemoryAccessEquiv(DefiningAccess), B);
767 // Evaluate read only and pure calls, and create an expression result.
768 const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I,
769 const BasicBlock *B) {
770 auto *CI = cast<CallInst>(I);
771 if (AA->doesNotAccessMemory(CI))
772 return createCallExpression(CI, nullptr, B);
773 if (AA->onlyReadsMemory(CI)) {
774 MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(CI);
775 return createCallExpression(CI, lookupMemoryAccessEquiv(DefiningAccess), B);
780 // Update the memory access equivalence table to say that From is equal to To,
781 // and return true if this is different from what already existed in the table.
782 bool NewGVN::setMemoryAccessEquivTo(MemoryAccess *From, MemoryAccess *To) {
783 DEBUG(dbgs() << "Setting " << *From << " equivalent to ");
785 DEBUG(dbgs() << "itself");
787 DEBUG(dbgs() << *To);
788 DEBUG(dbgs() << "\n");
789 auto LookupResult = MemoryAccessEquiv.find(From);
790 bool Changed = false;
791 // If it's already in the table, see if the value changed.
792 if (LookupResult != MemoryAccessEquiv.end()) {
793 if (To && LookupResult->second != To) {
794 // It wasn't equivalent before, and now it is.
795 LookupResult->second = To;
798 // It used to be equivalent to something, and now it's not.
799 MemoryAccessEquiv.erase(LookupResult);
804 "Memory equivalence should never change from nothing to something");
809 // Evaluate PHI nodes symbolically, and create an expression result.
810 const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I,
811 const BasicBlock *B) {
812 auto *E = cast<PHIExpression>(createPHIExpression(I));
814 DEBUG(dbgs() << "Simplified PHI node " << *I << " to undef"
816 E->deallocateOperands(ArgRecycler);
817 ExpressionAllocator.Deallocate(E);
818 return createConstantExpression(UndefValue::get(I->getType()));
821 Value *AllSameValue = E->getOperand(0);
823 // See if all arguments are the same, ignoring undef arguments, because we can
824 // choose a value that is the same for them.
825 for (const Value *Arg : E->operands())
826 if (Arg != AllSameValue && !isa<UndefValue>(Arg)) {
827 AllSameValue = nullptr;
832 // It's possible to have phi nodes with cycles (IE dependent on
833 // other phis that are .... dependent on the original phi node),
834 // especially in weird CFG's where some arguments are unreachable, or
835 // uninitialized along certain paths.
836 // This can cause infinite loops during evaluation (even if you disable
837 // the recursion below, you will simply ping-pong between congruence
838 // classes). If a phi node symbolically evaluates to another phi node,
839 // just leave it alone. If they are really the same, we will still
840 // eliminate them in favor of each other.
841 if (isa<PHINode>(AllSameValue))
844 DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue
846 E->deallocateOperands(ArgRecycler);
847 ExpressionAllocator.Deallocate(E);
848 if (auto *C = dyn_cast<Constant>(AllSameValue))
849 return createConstantExpression(C);
850 return createVariableExpression(AllSameValue);
856 NewGVN::performSymbolicAggrValueEvaluation(Instruction *I,
857 const BasicBlock *B) {
858 if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
859 auto *II = dyn_cast<IntrinsicInst>(EI->getAggregateOperand());
860 if (II && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {
862 // EI might be an extract from one of our recognised intrinsics. If it
863 // is we'll synthesize a semantically equivalent expression instead on
864 // an extract value expression.
865 switch (II->getIntrinsicID()) {
866 case Intrinsic::sadd_with_overflow:
867 case Intrinsic::uadd_with_overflow:
868 Opcode = Instruction::Add;
870 case Intrinsic::ssub_with_overflow:
871 case Intrinsic::usub_with_overflow:
872 Opcode = Instruction::Sub;
874 case Intrinsic::smul_with_overflow:
875 case Intrinsic::umul_with_overflow:
876 Opcode = Instruction::Mul;
883 // Intrinsic recognized. Grab its args to finish building the
885 assert(II->getNumArgOperands() == 2 &&
886 "Expect two args for recognised intrinsics.");
887 return createBinaryExpression(Opcode, EI->getType(),
888 II->getArgOperand(0),
889 II->getArgOperand(1), B);
894 return createAggregateValueExpression(I, B);
897 // Substitute and symbolize the value before value numbering.
898 const Expression *NewGVN::performSymbolicEvaluation(Value *V,
899 const BasicBlock *B) {
900 const Expression *E = nullptr;
901 if (auto *C = dyn_cast<Constant>(V))
902 E = createConstantExpression(C);
903 else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
904 E = createVariableExpression(V);
906 // TODO: memory intrinsics.
907 // TODO: Some day, we should do the forward propagation and reassociation
908 // parts of the algorithm.
909 auto *I = cast<Instruction>(V);
910 switch (I->getOpcode()) {
911 case Instruction::ExtractValue:
912 case Instruction::InsertValue:
913 E = performSymbolicAggrValueEvaluation(I, B);
915 case Instruction::PHI:
916 E = performSymbolicPHIEvaluation(I, B);
918 case Instruction::Call:
919 E = performSymbolicCallEvaluation(I, B);
921 case Instruction::Store:
922 E = performSymbolicStoreEvaluation(I, B);
924 case Instruction::Load:
925 E = performSymbolicLoadEvaluation(I, B);
927 case Instruction::BitCast: {
928 E = createExpression(I, B);
931 case Instruction::Add:
932 case Instruction::FAdd:
933 case Instruction::Sub:
934 case Instruction::FSub:
935 case Instruction::Mul:
936 case Instruction::FMul:
937 case Instruction::UDiv:
938 case Instruction::SDiv:
939 case Instruction::FDiv:
940 case Instruction::URem:
941 case Instruction::SRem:
942 case Instruction::FRem:
943 case Instruction::Shl:
944 case Instruction::LShr:
945 case Instruction::AShr:
946 case Instruction::And:
947 case Instruction::Or:
948 case Instruction::Xor:
949 case Instruction::ICmp:
950 case Instruction::FCmp:
951 case Instruction::Trunc:
952 case Instruction::ZExt:
953 case Instruction::SExt:
954 case Instruction::FPToUI:
955 case Instruction::FPToSI:
956 case Instruction::UIToFP:
957 case Instruction::SIToFP:
958 case Instruction::FPTrunc:
959 case Instruction::FPExt:
960 case Instruction::PtrToInt:
961 case Instruction::IntToPtr:
962 case Instruction::Select:
963 case Instruction::ExtractElement:
964 case Instruction::InsertElement:
965 case Instruction::ShuffleVector:
966 case Instruction::GetElementPtr:
967 E = createExpression(I, B);
976 // There is an edge from 'Src' to 'Dst'. Return true if every path from
977 // the entry block to 'Dst' passes via this edge. In particular 'Dst'
978 // must not be reachable via another edge from 'Src'.
979 bool NewGVN::isOnlyReachableViaThisEdge(const BasicBlockEdge &E) const {
981 // While in theory it is interesting to consider the case in which Dst has
982 // more than one predecessor, because Dst might be part of a loop which is
983 // only reachable from Src, in practice it is pointless since at the time
984 // GVN runs all such loops have preheaders, which means that Dst will have
985 // been changed to have only one predecessor, namely Src.
986 const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();
987 const BasicBlock *Src = E.getStart();
988 assert((!Pred || Pred == Src) && "No edge between these basic blocks!");
990 return Pred != nullptr;
993 void NewGVN::markUsersTouched(Value *V) {
994 // Now mark the users as touched.
995 for (auto *User : V->users()) {
996 assert(isa<Instruction>(User) && "Use of value not within an instruction?");
997 TouchedInstructions.set(InstrDFS[User]);
1001 void NewGVN::markMemoryUsersTouched(MemoryAccess *MA) {
1002 for (auto U : MA->users()) {
1003 if (auto *MUD = dyn_cast<MemoryUseOrDef>(U))
1004 TouchedInstructions.set(InstrDFS[MUD->getMemoryInst()]);
1006 TouchedInstructions.set(InstrDFS[U]);
1010 // Perform congruence finding on a given value numbering expression.
1011 void NewGVN::performCongruenceFinding(Value *V, const Expression *E) {
1013 ValueToExpression[V] = E;
1014 // This is guaranteed to return something, since it will at least find
1016 CongruenceClass *VClass = ValueToClass[V];
1017 assert(VClass && "Should have found a vclass");
1018 // Dead classes should have been eliminated from the mapping.
1019 assert(!VClass->Dead && "Found a dead class");
1021 CongruenceClass *EClass;
1022 if (const auto *VE = dyn_cast<VariableExpression>(E)) {
1023 EClass = ValueToClass[VE->getVariableValue()];
1025 auto lookupResult = ExpressionToClass.insert({E, nullptr});
1027 // If it's not in the value table, create a new congruence class.
1028 if (lookupResult.second) {
1029 CongruenceClass *NewClass = createCongruenceClass(nullptr, E);
1030 auto place = lookupResult.first;
1031 place->second = NewClass;
1033 // Constants and variables should always be made the leader.
1034 if (const auto *CE = dyn_cast<ConstantExpression>(E))
1035 NewClass->RepLeader = CE->getConstantValue();
1036 else if (const auto *VE = dyn_cast<VariableExpression>(E))
1037 NewClass->RepLeader = VE->getVariableValue();
1038 else if (const auto *SE = dyn_cast<StoreExpression>(E))
1039 NewClass->RepLeader = SE->getStoreInst()->getValueOperand();
1041 NewClass->RepLeader = V;
1044 DEBUG(dbgs() << "Created new congruence class for " << *V
1045 << " using expression " << *E << " at " << NewClass->ID
1046 << " and leader " << *(NewClass->RepLeader) << "\n");
1047 DEBUG(dbgs() << "Hash value was " << E->getHashValue() << "\n");
1049 EClass = lookupResult.first->second;
1050 if (isa<ConstantExpression>(E))
1051 assert(isa<Constant>(EClass->RepLeader) &&
1052 "Any class with a constant expression should have a "
1055 assert(EClass && "Somehow don't have an eclass");
1057 assert(!EClass->Dead && "We accidentally looked up a dead class");
1060 bool WasInChanged = ChangedValues.erase(V);
1061 if (VClass != EClass || WasInChanged) {
1062 DEBUG(dbgs() << "Found class " << EClass->ID << " for expression " << E
1065 if (VClass != EClass) {
1066 DEBUG(dbgs() << "New congruence class for " << V << " is " << EClass->ID
1069 VClass->Members.erase(V);
1070 EClass->Members.insert(V);
1071 ValueToClass[V] = EClass;
1072 // See if we destroyed the class or need to swap leaders.
1073 if (VClass->Members.empty() && VClass != InitialClass) {
1074 if (VClass->DefiningExpr) {
1075 VClass->Dead = true;
1076 DEBUG(dbgs() << "Erasing expression " << *E << " from table\n");
1077 ExpressionToClass.erase(VClass->DefiningExpr);
1079 } else if (VClass->RepLeader == V) {
1080 // FIXME: When the leader changes, the value numbering of
1081 // everything may change, so we need to reprocess.
1082 VClass->RepLeader = *(VClass->Members.begin());
1083 for (auto M : VClass->Members) {
1084 if (auto *I = dyn_cast<Instruction>(M))
1085 TouchedInstructions.set(InstrDFS[I]);
1086 ChangedValues.insert(M);
1091 markUsersTouched(V);
1092 if (auto *I = dyn_cast<Instruction>(V)) {
1093 if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) {
1094 // If this is a MemoryDef, we need to update the equivalence table. If
1096 // determined the expression is congruent to a different memory state,
1097 // use that different memory state. If we determined it didn't, we
1099 // that as well. Note that currently, we do not guarantee the
1100 // "different" memory state dominates us. The goal is to make things
1101 // that are congruent look congruent, not ensure we can eliminate one in
1102 // favor of the other.
1103 // Right now, the only way they can be equivalent is for store
1105 if (!isa<MemoryUse>(MA)) {
1106 if (E && isa<StoreExpression>(E) && EClass->Members.size() != 1) {
1107 auto *DefAccess = cast<StoreExpression>(E)->getDefiningAccess();
1108 setMemoryAccessEquivTo(MA, DefAccess != MA ? DefAccess : nullptr);
1110 setMemoryAccessEquivTo(MA, nullptr);
1113 markMemoryUsersTouched(MA);
1119 // Process the fact that Edge (from, to) is reachable, including marking
1120 // any newly reachable blocks and instructions for processing.
1121 void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) {
1122 // Check if the Edge was reachable before.
1123 if (ReachableEdges.insert({From, To}).second) {
1124 // If this block wasn't reachable before, all instructions are touched.
1125 if (ReachableBlocks.insert(To).second) {
1126 DEBUG(dbgs() << "Block " << getBlockName(To) << " marked reachable\n");
1127 const auto &InstRange = BlockInstRange.lookup(To);
1128 TouchedInstructions.set(InstRange.first, InstRange.second);
1130 DEBUG(dbgs() << "Block " << getBlockName(To)
1131 << " was reachable, but new edge {" << getBlockName(From)
1132 << "," << getBlockName(To) << "} to it found\n");
1134 // We've made an edge reachable to an existing block, which may
1135 // impact predicates. Otherwise, only mark the phi nodes as touched, as
1136 // they are the only thing that depend on new edges. Anything using their
1137 // values will get propagated to if necessary.
1138 if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(To))
1139 TouchedInstructions.set(InstrDFS[MemPhi]);
1141 auto BI = To->begin();
1142 while (isa<PHINode>(BI)) {
1143 TouchedInstructions.set(InstrDFS[&*BI]);
1150 // Given a predicate condition (from a switch, cmp, or whatever) and a block,
1151 // see if we know some constant value for it already.
1152 Value *NewGVN::findConditionEquivalence(Value *Cond, BasicBlock *B) const {
1153 auto Result = lookupOperandLeader(Cond, nullptr, B);
1154 if (isa<Constant>(Result))
1159 // Process the outgoing edges of a block for reachability.
1160 void NewGVN::processOutgoingEdges(TerminatorInst *TI, BasicBlock *B) {
1161 // Evaluate reachability of terminator instruction.
1163 if ((BR = dyn_cast<BranchInst>(TI)) && BR->isConditional()) {
1164 Value *Cond = BR->getCondition();
1165 Value *CondEvaluated = findConditionEquivalence(Cond, B);
1166 if (!CondEvaluated) {
1167 if (auto *I = dyn_cast<Instruction>(Cond)) {
1168 const Expression *E = createExpression(I, B);
1169 if (const auto *CE = dyn_cast<ConstantExpression>(E)) {
1170 CondEvaluated = CE->getConstantValue();
1172 } else if (isa<ConstantInt>(Cond)) {
1173 CondEvaluated = Cond;
1177 BasicBlock *TrueSucc = BR->getSuccessor(0);
1178 BasicBlock *FalseSucc = BR->getSuccessor(1);
1179 if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
1181 DEBUG(dbgs() << "Condition for Terminator " << *TI
1182 << " evaluated to true\n");
1183 updateReachableEdge(B, TrueSucc);
1184 } else if (CI->isZero()) {
1185 DEBUG(dbgs() << "Condition for Terminator " << *TI
1186 << " evaluated to false\n");
1187 updateReachableEdge(B, FalseSucc);
1190 updateReachableEdge(B, TrueSucc);
1191 updateReachableEdge(B, FalseSucc);
1193 } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
1194 // For switches, propagate the case values into the case
1197 // Remember how many outgoing edges there are to every successor.
1198 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
1200 Value *SwitchCond = SI->getCondition();
1201 Value *CondEvaluated = findConditionEquivalence(SwitchCond, B);
1202 // See if we were able to turn this switch statement into a constant.
1203 if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
1204 auto *CondVal = cast<ConstantInt>(CondEvaluated);
1205 // We should be able to get case value for this.
1206 auto CaseVal = SI->findCaseValue(CondVal);
1207 if (CaseVal.getCaseSuccessor() == SI->getDefaultDest()) {
1208 // We proved the value is outside of the range of the case.
1209 // We can't do anything other than mark the default dest as reachable,
1211 updateReachableEdge(B, SI->getDefaultDest());
1214 // Now get where it goes and mark it reachable.
1215 BasicBlock *TargetBlock = CaseVal.getCaseSuccessor();
1216 updateReachableEdge(B, TargetBlock);
1218 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
1219 BasicBlock *TargetBlock = SI->getSuccessor(i);
1220 ++SwitchEdges[TargetBlock];
1221 updateReachableEdge(B, TargetBlock);
1225 // Otherwise this is either unconditional, or a type we have no
1226 // idea about. Just mark successors as reachable.
1227 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1228 BasicBlock *TargetBlock = TI->getSuccessor(i);
1229 updateReachableEdge(B, TargetBlock);
1232 // This also may be a memory defining terminator, in which case, set it
1233 // equivalent to nothing.
1234 if (MemoryAccess *MA = MSSA->getMemoryAccess(TI))
1235 setMemoryAccessEquivTo(MA, nullptr);
1239 // The algorithm initially places the values of the routine in the INITIAL
1241 // class. The leader of INITIAL is the undetermined value `TOP`.
1242 // When the algorithm has finished, values still in INITIAL are unreachable.
1243 void NewGVN::initializeCongruenceClasses(Function &F) {
1244 // FIXME now i can't remember why this is 2
1245 NextCongruenceNum = 2;
1246 // Initialize all other instructions to be in INITIAL class.
1247 CongruenceClass::MemberSet InitialValues;
1248 InitialClass = createCongruenceClass(nullptr, nullptr);
1250 if (auto *MP = MSSA->getMemoryAccess(&B))
1251 MemoryAccessEquiv.insert({MP, MSSA->getLiveOnEntryDef()});
1254 InitialValues.insert(&I);
1255 ValueToClass[&I] = InitialClass;
1256 // All memory accesses are equivalent to live on entry to start. They must
1257 // be initialized to something so that initial changes are noticed. For
1258 // the maximal answer, we initialize them all to be the same as
1259 // liveOnEntry. Note that to save time, we only initialize the
1260 // MemoryDef's for stores and all MemoryPhis to be equal. Right now, no
1261 // other expression can generate a memory equivalence. If we start
1262 // handling memcpy/etc, we can expand this.
1263 if (isa<StoreInst>(&I))
1264 MemoryAccessEquiv.insert(
1265 {MSSA->getMemoryAccess(&I), MSSA->getLiveOnEntryDef()});
1268 InitialClass->Members.swap(InitialValues);
1270 // Initialize arguments to be in their own unique congruence classes
1271 for (auto &FA : F.args())
1272 createSingletonCongruenceClass(&FA);
1275 void NewGVN::cleanupTables() {
1276 for (unsigned i = 0, e = CongruenceClasses.size(); i != e; ++i) {
1277 DEBUG(dbgs() << "Congruence class " << CongruenceClasses[i]->ID << " has "
1278 << CongruenceClasses[i]->Members.size() << " members\n");
1279 // Make sure we delete the congruence class (probably worth switching to
1280 // a unique_ptr at some point.
1281 delete CongruenceClasses[i];
1282 CongruenceClasses[i] = nullptr;
1285 ValueToClass.clear();
1286 ArgRecycler.clear(ExpressionAllocator);
1287 ExpressionAllocator.Reset();
1288 CongruenceClasses.clear();
1289 ExpressionToClass.clear();
1290 ValueToExpression.clear();
1291 ReachableBlocks.clear();
1292 ReachableEdges.clear();
1294 ProcessedCount.clear();
1298 InstructionsToErase.clear();
1301 BlockInstRange.clear();
1302 TouchedInstructions.clear();
1303 DominatedInstRange.clear();
1304 MemoryAccessEquiv.clear();
1307 std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
1309 unsigned End = Start;
1310 if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(B)) {
1311 InstrDFS[MemPhi] = End++;
1312 DFSToInstr.emplace_back(MemPhi);
1315 for (auto &I : *B) {
1316 InstrDFS[&I] = End++;
1317 DFSToInstr.emplace_back(&I);
1320 // All of the range functions taken half-open ranges (open on the end side).
1321 // So we do not subtract one from count, because at this point it is one
1322 // greater than the last instruction.
1323 return std::make_pair(Start, End);
1326 void NewGVN::updateProcessedCount(Value *V) {
1328 if (ProcessedCount.count(V) == 0) {
1329 ProcessedCount.insert({V, 1});
1331 ProcessedCount[V] += 1;
1332 assert(ProcessedCount[V] < 100 &&
1333 "Seem to have processed the same Value a lot");
1337 // Evaluate MemoryPhi nodes symbolically, just like PHI nodes
1338 void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) {
1339 // If all the arguments are the same, the MemoryPhi has the same value as the
1341 // Filter out unreachable blocks from our operands.
1342 auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) {
1343 return ReachableBlocks.count(MP->getIncomingBlock(U));
1346 assert(Filtered.begin() != Filtered.end() &&
1347 "We should not be processing a MemoryPhi in a completely "
1348 "unreachable block");
1350 // Transform the remaining operands into operand leaders.
1351 // FIXME: mapped_iterator should have a range version.
1352 auto LookupFunc = [&](const Use &U) {
1353 return lookupMemoryAccessEquiv(cast<MemoryAccess>(U));
1355 auto MappedBegin = map_iterator(Filtered.begin(), LookupFunc);
1356 auto MappedEnd = map_iterator(Filtered.end(), LookupFunc);
1358 // and now check if all the elements are equal.
1359 // Sadly, we can't use std::equals since these are random access iterators.
1360 MemoryAccess *AllSameValue = *MappedBegin;
1362 bool AllEqual = std::all_of(
1363 MappedBegin, MappedEnd,
1364 [&AllSameValue](const MemoryAccess *V) { return V == AllSameValue; });
1367 DEBUG(dbgs() << "Memory Phi value numbered to " << *AllSameValue << "\n");
1369 DEBUG(dbgs() << "Memory Phi value numbered to itself\n");
1371 if (setMemoryAccessEquivTo(MP, AllEqual ? AllSameValue : nullptr))
1372 markMemoryUsersTouched(MP);
1375 // Value number a single instruction, symbolically evaluating, performing
1376 // congruence finding, and updating mappings.
1377 void NewGVN::valueNumberInstruction(Instruction *I) {
1378 DEBUG(dbgs() << "Processing instruction " << *I << "\n");
1379 if (isInstructionTriviallyDead(I, TLI)) {
1380 DEBUG(dbgs() << "Skipping unused instruction\n");
1381 markInstructionForDeletion(I);
1384 if (!I->isTerminator()) {
1385 const auto *Symbolized = performSymbolicEvaluation(I, I->getParent());
1386 // If we couldn't come up with a symbolic expression, use the unknown
1388 if (Symbolized == nullptr)
1389 Symbolized = createUnknownExpression(I);
1390 performCongruenceFinding(I, Symbolized);
1392 // Handle terminators that return values. All of them produce values we
1393 // don't currently understand.
1394 if (!I->getType()->isVoidTy()){
1395 auto *Symbolized = createUnknownExpression(I);
1396 performCongruenceFinding(I, Symbolized);
1398 processOutgoingEdges(dyn_cast<TerminatorInst>(I), I->getParent());
1402 // Verify the that the memory equivalence table makes sense relative to the
1403 // congruence classes.
1404 void NewGVN::verifyMemoryCongruency() {
1405 // Anything equivalent in the memory access table should be in the same
1406 // congruence class.
1408 // Filter out the unreachable and trivially dead entries, because they may
1409 // never have been updated if the instructions were not processed.
1410 auto ReachableAccessPred =
1411 [&](const std::pair<const MemoryAccess *, MemoryAccess *> Pair) {
1412 bool Result = ReachableBlocks.count(Pair.first->getBlock());
1415 if (auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
1416 return !isInstructionTriviallyDead(MemDef->getMemoryInst());
1420 auto Filtered = make_filter_range(MemoryAccessEquiv, ReachableAccessPred);
1421 for (auto KV : Filtered) {
1422 assert(KV.first != KV.second &&
1423 "We added a useless equivalence to the memory equivalence table");
1424 // Unreachable instructions may not have changed because we never process
1426 if (!ReachableBlocks.count(KV.first->getBlock()))
1428 if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
1429 auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second);
1430 if (FirstMUD && SecondMUD) {
1431 auto *FirstInst = FirstMUD->getMemoryInst();
1432 auto *SecondInst = SecondMUD->getMemoryInst();
1434 ValueToClass.lookup(FirstInst) == ValueToClass.lookup(SecondInst) &&
1435 "The instructions for these memory operations should have been in "
1436 "the same congruence class");
1438 } else if (auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {
1440 // We can only sanely verify that MemoryDefs in the operand list all have
1442 auto ReachableOperandPred = [&](const Use &U) {
1443 return ReachableBlocks.count(FirstMP->getIncomingBlock(U)) &&
1447 // All arguments should in the same class, ignoring unreachable arguments
1448 auto FilteredPhiArgs =
1449 make_filter_range(FirstMP->operands(), ReachableOperandPred);
1450 SmallVector<const CongruenceClass *, 16> PhiOpClasses;
1451 std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
1452 std::back_inserter(PhiOpClasses), [&](const Use &U) {
1453 const MemoryDef *MD = cast<MemoryDef>(U);
1454 return ValueToClass.lookup(MD->getMemoryInst());
1456 assert(std::equal(PhiOpClasses.begin(), PhiOpClasses.end(),
1457 PhiOpClasses.begin()) &&
1458 "All MemoryPhi arguments should be in the same class");
1463 // This is the main transformation entry point.
1464 bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC,
1465 TargetLibraryInfo *_TLI, AliasAnalysis *_AA,
1467 bool Changed = false;
1473 DL = &F.getParent()->getDataLayout();
1474 MSSAWalker = MSSA->getWalker();
1476 // Count number of instructions for sizing of hash tables, and come
1477 // up with a global dfs numbering for instructions.
1478 unsigned ICount = 1;
1479 // Add an empty instruction to account for the fact that we start at 1
1480 DFSToInstr.emplace_back(nullptr);
1481 // Note: We want RPO traversal of the blocks, which is not quite the same as
1482 // dominator tree order, particularly with regard whether backedges get
1483 // visited first or second, given a block with multiple successors.
1484 // If we visit in the wrong order, we will end up performing N times as many
1486 // The dominator tree does guarantee that, for a given dom tree node, it's
1487 // parent must occur before it in the RPO ordering. Thus, we only need to sort
1489 DenseMap<const DomTreeNode *, unsigned> RPOOrdering;
1490 ReversePostOrderTraversal<Function *> RPOT(&F);
1491 unsigned Counter = 0;
1492 for (auto &B : RPOT) {
1493 auto *Node = DT->getNode(B);
1494 assert(Node && "RPO and Dominator tree should have same reachability");
1495 RPOOrdering[Node] = ++Counter;
1497 // Sort dominator tree children arrays into RPO.
1498 for (auto &B : RPOT) {
1499 auto *Node = DT->getNode(B);
1500 if (Node->getChildren().size() > 1)
1501 std::sort(Node->begin(), Node->end(),
1502 [&RPOOrdering](const DomTreeNode *A, const DomTreeNode *B) {
1503 return RPOOrdering[A] < RPOOrdering[B];
1507 // Now a standard depth first ordering of the domtree is equivalent to RPO.
1508 auto DFI = df_begin(DT->getRootNode());
1509 for (auto DFE = df_end(DT->getRootNode()); DFI != DFE; ++DFI) {
1510 BasicBlock *B = DFI->getBlock();
1511 const auto &BlockRange = assignDFSNumbers(B, ICount);
1512 BlockInstRange.insert({B, BlockRange});
1513 ICount += BlockRange.second - BlockRange.first;
1516 // Handle forward unreachable blocks and figure out which blocks
1517 // have single preds.
1519 // Assign numbers to unreachable blocks.
1520 if (!DFI.nodeVisited(DT->getNode(&B))) {
1521 const auto &BlockRange = assignDFSNumbers(&B, ICount);
1522 BlockInstRange.insert({&B, BlockRange});
1523 ICount += BlockRange.second - BlockRange.first;
1527 TouchedInstructions.resize(ICount);
1528 DominatedInstRange.reserve(F.size());
1529 // Ensure we don't end up resizing the expressionToClass map, as
1530 // that can be quite expensive. At most, we have one expression per
1532 ExpressionToClass.reserve(ICount);
1534 // Initialize the touched instructions to include the entry block.
1535 const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock());
1536 TouchedInstructions.set(InstRange.first, InstRange.second);
1537 ReachableBlocks.insert(&F.getEntryBlock());
1539 initializeCongruenceClasses(F);
1541 // We start out in the entry block.
1542 BasicBlock *LastBlock = &F.getEntryBlock();
1543 while (TouchedInstructions.any()) {
1544 // Walk through all the instructions in all the blocks in RPO.
1545 for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1;
1546 InstrNum = TouchedInstructions.find_next(InstrNum)) {
1547 assert(InstrNum != 0 && "Bit 0 should never be set, something touched an "
1548 "instruction not in the lookup table");
1549 Value *V = DFSToInstr[InstrNum];
1550 BasicBlock *CurrBlock = nullptr;
1552 if (auto *I = dyn_cast<Instruction>(V))
1553 CurrBlock = I->getParent();
1554 else if (auto *MP = dyn_cast<MemoryPhi>(V))
1555 CurrBlock = MP->getBlock();
1557 llvm_unreachable("DFSToInstr gave us an unknown type of instruction");
1559 // If we hit a new block, do reachability processing.
1560 if (CurrBlock != LastBlock) {
1561 LastBlock = CurrBlock;
1562 bool BlockReachable = ReachableBlocks.count(CurrBlock);
1563 const auto &CurrInstRange = BlockInstRange.lookup(CurrBlock);
1565 // If it's not reachable, erase any touched instructions and move on.
1566 if (!BlockReachable) {
1567 TouchedInstructions.reset(CurrInstRange.first, CurrInstRange.second);
1568 DEBUG(dbgs() << "Skipping instructions in block "
1569 << getBlockName(CurrBlock)
1570 << " because it is unreachable\n");
1573 updateProcessedCount(CurrBlock);
1576 if (auto *MP = dyn_cast<MemoryPhi>(V)) {
1577 DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n");
1578 valueNumberMemoryPhi(MP);
1579 } else if (auto *I = dyn_cast<Instruction>(V)) {
1580 valueNumberInstruction(I);
1582 llvm_unreachable("Should have been a MemoryPhi or Instruction");
1584 updateProcessedCount(V);
1585 // Reset after processing (because we may mark ourselves as touched when
1586 // we propagate equalities).
1587 TouchedInstructions.reset(InstrNum);
1591 // FIXME: Move this to expensive checks when we are satisfied with NewGVN
1593 verifyMemoryCongruency();
1595 Changed |= eliminateInstructions(F);
1597 // Delete all instructions marked for deletion.
1598 for (Instruction *ToErase : InstructionsToErase) {
1599 if (!ToErase->use_empty())
1600 ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType()));
1602 ToErase->eraseFromParent();
1605 // Delete all unreachable blocks.
1606 auto UnreachableBlockPred = [&](const BasicBlock &BB) {
1607 return !ReachableBlocks.count(&BB);
1610 for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
1611 DEBUG(dbgs() << "We believe block " << getBlockName(&BB)
1612 << " is unreachable\n");
1613 deleteInstructionsInBlock(&BB);
1621 bool NewGVN::runOnFunction(Function &F) {
1622 if (skipFunction(F))
1624 return runGVN(F, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
1625 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
1626 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
1627 &getAnalysis<AAResultsWrapperPass>().getAAResults(),
1628 &getAnalysis<MemorySSAWrapperPass>().getMSSA());
1631 PreservedAnalyses NewGVNPass::run(Function &F, AnalysisManager<Function> &AM) {
1634 // Apparently the order in which we get these results matter for
1635 // the old GVN (see Chandler's comment in GVN.cpp). I'll keep
1636 // the same order here, just in case.
1637 auto &AC = AM.getResult<AssumptionAnalysis>(F);
1638 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1639 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1640 auto &AA = AM.getResult<AAManager>(F);
1641 auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
1642 bool Changed = Impl.runGVN(F, &DT, &AC, &TLI, &AA, &MSSA);
1644 return PreservedAnalyses::all();
1645 PreservedAnalyses PA;
1646 PA.preserve<DominatorTreeAnalysis>();
1647 PA.preserve<GlobalsAA>();
1651 // Return true if V is a value that will always be available (IE can
1652 // be placed anywhere) in the function. We don't do globals here
1653 // because they are often worse to put in place.
1654 // TODO: Separate cost from availability
1655 static bool alwaysAvailable(Value *V) {
1656 return isa<Constant>(V) || isa<Argument>(V);
1659 // Get the basic block from an instruction/value.
1660 static BasicBlock *getBlockForValue(Value *V) {
1661 if (auto *I = dyn_cast<Instruction>(V))
1662 return I->getParent();
1666 struct NewGVN::ValueDFS {
1670 // Only one of these will be set.
1671 Value *Val = nullptr;
1674 bool operator<(const ValueDFS &Other) const {
1675 // It's not enough that any given field be less than - we have sets
1676 // of fields that need to be evaluated together to give a proper ordering.
1677 // For example, if you have;
1682 // We want the second to be less than the first, but if we just go field
1683 // by field, we will get to Val 0 < Val 50 and say the first is less than
1684 // the second. We only want it to be less than if the DFS orders are equal.
1686 // Each LLVM instruction only produces one value, and thus the lowest-level
1687 // differentiator that really matters for the stack (and what we use as as a
1688 // replacement) is the local dfs number.
1689 // Everything else in the structure is instruction level, and only affects
1690 // the order in which we will replace operands of a given instruction.
1692 // For a given instruction (IE things with equal dfsin, dfsout, localnum),
1693 // the order of replacement of uses does not matter.
1697 // When you hit b, you will have two valuedfs with the same dfsin, out, and
1699 // The .val will be the same as well.
1700 // The .u's will be different.
1701 // You will replace both, and it does not matter what order you replace them
1702 // in (IE whether you replace operand 2, then operand 1, or operand 1, then
1704 // Similarly for the case of same dfsin, dfsout, localnum, but different
1709 // in c, we will a valuedfs for a, and one for b,with everything the same
1711 // It does not matter what order we replace these operands in.
1712 // You will always end up with the same IR, and this is guaranteed.
1713 return std::tie(DFSIn, DFSOut, LocalNum, Val, U) <
1714 std::tie(Other.DFSIn, Other.DFSOut, Other.LocalNum, Other.Val,
1719 void NewGVN::convertDenseToDFSOrdered(CongruenceClass::MemberSet &Dense,
1720 std::vector<ValueDFS> &DFSOrderedSet) {
1721 for (auto D : Dense) {
1722 // First add the value.
1723 BasicBlock *BB = getBlockForValue(D);
1724 // Constants are handled prior to ever calling this function, so
1725 // we should only be left with instructions as members.
1726 assert(BB && "Should have figured out a basic block for value");
1729 std::pair<int, int> DFSPair = DFSDomMap[BB];
1730 assert(DFSPair.first != -1 && DFSPair.second != -1 && "Invalid DFS Pair");
1731 VD.DFSIn = DFSPair.first;
1732 VD.DFSOut = DFSPair.second;
1734 // If it's an instruction, use the real local dfs number.
1735 if (auto *I = dyn_cast<Instruction>(D))
1736 VD.LocalNum = InstrDFS[I];
1738 llvm_unreachable("Should have been an instruction");
1740 DFSOrderedSet.emplace_back(VD);
1742 // Now add the users.
1743 for (auto &U : D->uses()) {
1744 if (auto *I = dyn_cast<Instruction>(U.getUser())) {
1746 // Put the phi node uses in the incoming block.
1748 if (auto *P = dyn_cast<PHINode>(I)) {
1749 IBlock = P->getIncomingBlock(U);
1750 // Make phi node users appear last in the incoming block
1752 VD.LocalNum = InstrDFS.size() + 1;
1754 IBlock = I->getParent();
1755 VD.LocalNum = InstrDFS[I];
1757 std::pair<int, int> DFSPair = DFSDomMap[IBlock];
1758 VD.DFSIn = DFSPair.first;
1759 VD.DFSOut = DFSPair.second;
1761 DFSOrderedSet.emplace_back(VD);
1767 static void patchReplacementInstruction(Instruction *I, Value *Repl) {
1768 // Patch the replacement so that it is not more restrictive than the value
1770 auto *Op = dyn_cast<BinaryOperator>(I);
1771 auto *ReplOp = dyn_cast<BinaryOperator>(Repl);
1774 ReplOp->andIRFlags(Op);
1776 if (auto *ReplInst = dyn_cast<Instruction>(Repl)) {
1777 // FIXME: If both the original and replacement value are part of the
1778 // same control-flow region (meaning that the execution of one
1779 // guarentees the executation of the other), then we can combine the
1780 // noalias scopes here and do better than the general conservative
1781 // answer used in combineMetadata().
1783 // In general, GVN unifies expressions over different control-flow
1784 // regions, and so we need a conservative combination of the noalias
1786 unsigned KnownIDs[] = {
1787 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
1788 LLVMContext::MD_noalias, LLVMContext::MD_range,
1789 LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load,
1790 LLVMContext::MD_invariant_group};
1791 combineMetadata(ReplInst, I, KnownIDs);
1795 static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {
1796 patchReplacementInstruction(I, Repl);
1797 I->replaceAllUsesWith(Repl);
1800 void NewGVN::deleteInstructionsInBlock(BasicBlock *BB) {
1801 DEBUG(dbgs() << " BasicBlock Dead:" << *BB);
1802 ++NumGVNBlocksDeleted;
1804 // Check to see if there are non-terminating instructions to delete.
1805 if (isa<TerminatorInst>(BB->begin()))
1808 // Delete the instructions backwards, as it has a reduced likelihood of having
1809 // to update as many def-use and use-def chains. Start after the terminator.
1810 auto StartPoint = BB->rbegin();
1812 // Note that we explicitly recalculate BB->rend() on each iteration,
1813 // as it may change when we remove the first instruction.
1814 for (BasicBlock::reverse_iterator I(StartPoint); I != BB->rend();) {
1815 Instruction &Inst = *I++;
1816 if (!Inst.use_empty())
1817 Inst.replaceAllUsesWith(UndefValue::get(Inst.getType()));
1818 if (isa<LandingPadInst>(Inst))
1821 Inst.eraseFromParent();
1822 ++NumGVNInstrDeleted;
1826 void NewGVN::markInstructionForDeletion(Instruction *I) {
1827 DEBUG(dbgs() << "Marking " << *I << " for deletion\n");
1828 InstructionsToErase.insert(I);
1831 void NewGVN::replaceInstruction(Instruction *I, Value *V) {
1833 DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n");
1834 patchAndReplaceAllUsesWith(I, V);
1835 // We save the actual erasing to avoid invalidating memory
1836 // dependencies until we are done with everything.
1837 markInstructionForDeletion(I);
1842 // This is a stack that contains both the value and dfs info of where
1843 // that value is valid.
1844 class ValueDFSStack {
1846 Value *back() const { return ValueStack.back(); }
1847 std::pair<int, int> dfs_back() const { return DFSStack.back(); }
1849 void push_back(Value *V, int DFSIn, int DFSOut) {
1850 ValueStack.emplace_back(V);
1851 DFSStack.emplace_back(DFSIn, DFSOut);
1853 bool empty() const { return DFSStack.empty(); }
1854 bool isInScope(int DFSIn, int DFSOut) const {
1857 return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
1860 void popUntilDFSScope(int DFSIn, int DFSOut) {
1862 // These two should always be in sync at this point.
1863 assert(ValueStack.size() == DFSStack.size() &&
1864 "Mismatch between ValueStack and DFSStack");
1866 !DFSStack.empty() &&
1867 !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
1868 DFSStack.pop_back();
1869 ValueStack.pop_back();
1874 SmallVector<Value *, 8> ValueStack;
1875 SmallVector<std::pair<int, int>, 8> DFSStack;
1879 bool NewGVN::eliminateInstructions(Function &F) {
1880 // This is a non-standard eliminator. The normal way to eliminate is
1881 // to walk the dominator tree in order, keeping track of available
1882 // values, and eliminating them. However, this is mildly
1883 // pointless. It requires doing lookups on every instruction,
1884 // regardless of whether we will ever eliminate it. For
1885 // instructions part of most singleton congruence classes, we know we
1886 // will never eliminate them.
1888 // Instead, this eliminator looks at the congruence classes directly, sorts
1889 // them into a DFS ordering of the dominator tree, and then we just
1890 // perform elimination straight on the sets by walking the congruence
1891 // class member uses in order, and eliminate the ones dominated by the
1892 // last member. This is worst case O(E log E) where E = number of
1893 // instructions in a single congruence class. In theory, this is all
1894 // instructions. In practice, it is much faster, as most instructions are
1895 // either in singleton congruence classes or can't possibly be eliminated
1896 // anyway (if there are no overlapping DFS ranges in class).
1897 // When we find something not dominated, it becomes the new leader
1898 // for elimination purposes.
1899 // TODO: If we wanted to be faster, We could remove any members with no
1900 // overlapping ranges while sorting, as we will never eliminate anything
1901 // with those members, as they don't dominate anything else in our set.
1903 bool AnythingReplaced = false;
1905 // Since we are going to walk the domtree anyway, and we can't guarantee the
1906 // DFS numbers are updated, we compute some ourselves.
1907 DT->updateDFSNumbers();
1910 if (!ReachableBlocks.count(&B)) {
1911 for (const auto S : successors(&B)) {
1912 for (auto II = S->begin(); isa<PHINode>(II); ++II) {
1913 auto &Phi = cast<PHINode>(*II);
1914 DEBUG(dbgs() << "Replacing incoming value of " << *II << " for block "
1916 << " with undef due to it being unreachable\n");
1917 for (auto &Operand : Phi.incoming_values())
1918 if (Phi.getIncomingBlock(Operand) == &B)
1919 Operand.set(UndefValue::get(Phi.getType()));
1923 DomTreeNode *Node = DT->getNode(&B);
1925 DFSDomMap[&B] = {Node->getDFSNumIn(), Node->getDFSNumOut()};
1928 for (CongruenceClass *CC : CongruenceClasses) {
1929 // FIXME: We should eventually be able to replace everything still
1930 // in the initial class with undef, as they should be unreachable.
1931 // Right now, initial still contains some things we skip value
1932 // numbering of (UNREACHABLE's, for example).
1933 if (CC == InitialClass || CC->Dead)
1935 assert(CC->RepLeader && "We should have had a leader");
1937 // If this is a leader that is always available, and it's a
1938 // constant or has no equivalences, just replace everything with
1939 // it. We then update the congruence class with whatever members
1941 if (alwaysAvailable(CC->RepLeader)) {
1942 SmallPtrSet<Value *, 4> MembersLeft;
1943 for (auto M : CC->Members) {
1947 // Void things have no uses we can replace.
1948 if (Member == CC->RepLeader || Member->getType()->isVoidTy()) {
1949 MembersLeft.insert(Member);
1953 DEBUG(dbgs() << "Found replacement " << *(CC->RepLeader) << " for "
1954 << *Member << "\n");
1955 // Due to equality propagation, these may not always be
1956 // instructions, they may be real values. We don't really
1957 // care about trying to replace the non-instructions.
1958 if (auto *I = dyn_cast<Instruction>(Member)) {
1959 assert(CC->RepLeader != I &&
1960 "About to accidentally remove our leader");
1961 replaceInstruction(I, CC->RepLeader);
1962 AnythingReplaced = true;
1966 MembersLeft.insert(I);
1969 CC->Members.swap(MembersLeft);
1972 DEBUG(dbgs() << "Eliminating in congruence class " << CC->ID << "\n");
1973 // If this is a singleton, we can skip it.
1974 if (CC->Members.size() != 1) {
1976 // This is a stack because equality replacement/etc may place
1977 // constants in the middle of the member list, and we want to use
1978 // those constant values in preference to the current leader, over
1979 // the scope of those constants.
1980 ValueDFSStack EliminationStack;
1982 // Convert the members to DFS ordered sets and then merge them.
1983 std::vector<ValueDFS> DFSOrderedSet;
1984 convertDenseToDFSOrdered(CC->Members, DFSOrderedSet);
1986 // Sort the whole thing.
1987 sort(DFSOrderedSet.begin(), DFSOrderedSet.end());
1989 for (auto &C : DFSOrderedSet) {
1990 int MemberDFSIn = C.DFSIn;
1991 int MemberDFSOut = C.DFSOut;
1992 Value *Member = C.Val;
1993 Use *MemberUse = C.U;
1995 // We ignore void things because we can't get a value from them.
1996 if (Member && Member->getType()->isVoidTy())
1999 if (EliminationStack.empty()) {
2000 DEBUG(dbgs() << "Elimination Stack is empty\n");
2002 DEBUG(dbgs() << "Elimination Stack Top DFS numbers are ("
2003 << EliminationStack.dfs_back().first << ","
2004 << EliminationStack.dfs_back().second << ")\n");
2006 if (Member && isa<Constant>(Member))
2007 assert(isa<Constant>(CC->RepLeader));
2009 DEBUG(dbgs() << "Current DFS numbers are (" << MemberDFSIn << ","
2010 << MemberDFSOut << ")\n");
2011 // First, we see if we are out of scope or empty. If so,
2012 // and there equivalences, we try to replace the top of
2013 // stack with equivalences (if it's on the stack, it must
2014 // not have been eliminated yet).
2015 // Then we synchronize to our current scope, by
2016 // popping until we are back within a DFS scope that
2017 // dominates the current member.
2018 // Then, what happens depends on a few factors
2019 // If the stack is now empty, we need to push
2020 // If we have a constant or a local equivalence we want to
2021 // start using, we also push.
2022 // Otherwise, we walk along, processing members who are
2023 // dominated by this scope, and eliminate them.
2025 Member && (EliminationStack.empty() || isa<Constant>(Member));
2027 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
2029 if (OutOfScope || ShouldPush) {
2030 // Sync to our current scope.
2031 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
2032 ShouldPush |= Member && EliminationStack.empty();
2034 EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
2038 // If we get to this point, and the stack is empty we must have a use
2039 // with nothing we can use to eliminate it, just skip it.
2040 if (EliminationStack.empty())
2043 // Skip the Value's, we only want to eliminate on their uses.
2046 Value *Result = EliminationStack.back();
2048 // Don't replace our existing users with ourselves, and don't replace
2049 // phi node arguments with the result of the same phi node.
2050 // IE tmp = phi(tmp11, undef); tmp11 = foo -> tmp = phi(tmp, undef)
2051 if (MemberUse->get() == Result ||
2052 (isa<PHINode>(Result) && MemberUse->getUser() == Result))
2055 DEBUG(dbgs() << "Found replacement " << *Result << " for "
2056 << *MemberUse->get() << " in " << *(MemberUse->getUser())
2059 // If we replaced something in an instruction, handle the patching of
2061 if (auto *ReplacedInst = dyn_cast<Instruction>(MemberUse->get()))
2062 patchReplacementInstruction(ReplacedInst, Result);
2064 assert(isa<Instruction>(MemberUse->getUser()));
2065 MemberUse->set(Result);
2066 AnythingReplaced = true;
2071 // Cleanup the congruence class.
2072 SmallPtrSet<Value *, 4> MembersLeft;
2073 for (Value * Member : CC->Members) {
2074 if (Member->getType()->isVoidTy()) {
2075 MembersLeft.insert(Member);
2079 if (auto *MemberInst = dyn_cast<Instruction>(Member)) {
2080 if (isInstructionTriviallyDead(MemberInst)) {
2081 // TODO: Don't mark loads of undefs.
2082 markInstructionForDeletion(MemberInst);
2086 MembersLeft.insert(Member);
2088 CC->Members.swap(MembersLeft);
2091 return AnythingReplaced;