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");
82 STATISTIC(NumGVNMaxIterations, "Maximum Number of iterations it took to converge GVN");
84 //===----------------------------------------------------------------------===//
86 //===----------------------------------------------------------------------===//
90 namespace GVNExpression {
91 Expression::~Expression() = default;
92 BasicExpression::~BasicExpression() = default;
93 CallExpression::~CallExpression() = default;
94 LoadExpression::~LoadExpression() = default;
95 StoreExpression::~StoreExpression() = default;
96 AggregateValueExpression::~AggregateValueExpression() = default;
97 PHIExpression::~PHIExpression() = default;
101 // Congruence classes represent the set of expressions/instructions
102 // that are all the same *during some scope in the function*.
103 // That is, because of the way we perform equality propagation, and
104 // because of memory value numbering, it is not correct to assume
105 // you can willy-nilly replace any member with any other at any
106 // point in the function.
108 // For any Value in the Member set, it is valid to replace any dominated member
111 // Every congruence class has a leader, and the leader is used to
112 // symbolize instructions in a canonical way (IE every operand of an
113 // instruction that is a member of the same congruence class will
114 // always be replaced with leader during symbolization).
115 // To simplify symbolization, we keep the leader as a constant if class can be
116 // proved to be a constant value.
117 // Otherwise, the leader is a randomly chosen member of the value set, it does
118 // not matter which one is chosen.
119 // Each congruence class also has a defining expression,
120 // though the expression may be null. If it exists, it can be used for forward
121 // propagation and reassociation of values.
123 struct CongruenceClass {
124 using MemberSet = SmallPtrSet<Value *, 4>;
126 // Representative leader.
127 Value *RepLeader = nullptr;
128 // Defining Expression.
129 const Expression *DefiningExpr = nullptr;
130 // Actual members of this class.
133 // True if this class has no members left. This is mainly used for assertion
134 // purposes, and for skipping empty classes.
137 explicit CongruenceClass(unsigned ID) : ID(ID) {}
138 CongruenceClass(unsigned ID, Value *Leader, const Expression *E)
139 : ID(ID), RepLeader(Leader), DefiningExpr(E) {}
143 template <> struct DenseMapInfo<const Expression *> {
144 static const Expression *getEmptyKey() {
145 auto Val = static_cast<uintptr_t>(-1);
146 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
147 return reinterpret_cast<const Expression *>(Val);
149 static const Expression *getTombstoneKey() {
150 auto Val = static_cast<uintptr_t>(~1U);
151 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
152 return reinterpret_cast<const Expression *>(Val);
154 static unsigned getHashValue(const Expression *V) {
155 return static_cast<unsigned>(V->getHashValue());
157 static bool isEqual(const Expression *LHS, const Expression *RHS) {
160 if (LHS == getTombstoneKey() || RHS == getTombstoneKey() ||
161 LHS == getEmptyKey() || RHS == getEmptyKey())
166 } // end namespace llvm
168 class NewGVN : public FunctionPass {
170 const DataLayout *DL;
171 const TargetLibraryInfo *TLI;
175 MemorySSAWalker *MSSAWalker;
176 BumpPtrAllocator ExpressionAllocator;
177 ArrayRecycler<Value *> ArgRecycler;
179 // Congruence class info.
180 CongruenceClass *InitialClass;
181 std::vector<CongruenceClass *> CongruenceClasses;
182 unsigned NextCongruenceNum;
185 DenseMap<Value *, CongruenceClass *> ValueToClass;
186 DenseMap<Value *, const Expression *> ValueToExpression;
188 // A table storing which memorydefs/phis represent a memory state provably
189 // equivalent to another memory state.
190 // We could use the congruence class machinery, but the MemoryAccess's are
191 // abstract memory states, so they can only ever be equivalent to each other,
192 // and not to constants, etc.
193 DenseMap<const MemoryAccess *, MemoryAccess *> MemoryAccessEquiv;
195 // Expression to class mapping.
196 using ExpressionClassMap = DenseMap<const Expression *, CongruenceClass *>;
197 ExpressionClassMap ExpressionToClass;
199 // Which values have changed as a result of leader changes.
200 SmallPtrSet<Value *, 8> ChangedValues;
202 // Reachability info.
203 using BlockEdge = BasicBlockEdge;
204 DenseSet<BlockEdge> ReachableEdges;
205 SmallPtrSet<const BasicBlock *, 8> ReachableBlocks;
207 // This is a bitvector because, on larger functions, we may have
208 // thousands of touched instructions at once (entire blocks,
209 // instructions with hundreds of uses, etc). Even with optimization
210 // for when we mark whole blocks as touched, when this was a
211 // SmallPtrSet or DenseSet, for some functions, we spent >20% of all
212 // the time in GVN just managing this list. The bitvector, on the
213 // other hand, efficiently supports test/set/clear of both
214 // individual and ranges, as well as "find next element" This
215 // enables us to use it as a worklist with essentially 0 cost.
216 BitVector TouchedInstructions;
218 DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;
219 DenseMap<const DomTreeNode *, std::pair<unsigned, unsigned>>
223 // Debugging for how many times each block and instruction got processed.
224 DenseMap<const Value *, unsigned> ProcessedCount;
228 DenseMap<const BasicBlock *, std::pair<int, int>> DFSDomMap;
229 DenseMap<const Value *, unsigned> InstrDFS;
230 SmallVector<Value *, 32> DFSToInstr;
233 SmallPtrSet<Instruction *, 8> InstructionsToErase;
236 static char ID; // Pass identification, replacement for typeid.
237 NewGVN() : FunctionPass(ID) {
238 initializeNewGVNPass(*PassRegistry::getPassRegistry());
241 bool runOnFunction(Function &F) override;
242 bool runGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
243 TargetLibraryInfo *TLI, AliasAnalysis *AA, MemorySSA *MSSA);
246 // This transformation requires dominator postdominator info.
247 void getAnalysisUsage(AnalysisUsage &AU) const override {
248 AU.addRequired<AssumptionCacheTracker>();
249 AU.addRequired<DominatorTreeWrapperPass>();
250 AU.addRequired<TargetLibraryInfoWrapperPass>();
251 AU.addRequired<MemorySSAWrapperPass>();
252 AU.addRequired<AAResultsWrapperPass>();
254 AU.addPreserved<DominatorTreeWrapperPass>();
255 AU.addPreserved<GlobalsAAWrapperPass>();
258 // Expression handling.
259 const Expression *createExpression(Instruction *, const BasicBlock *);
260 const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *,
262 PHIExpression *createPHIExpression(Instruction *);
263 const VariableExpression *createVariableExpression(Value *);
264 const ConstantExpression *createConstantExpression(Constant *);
265 const Expression *createVariableOrConstant(Value *V, const BasicBlock *B);
266 const UnknownExpression *createUnknownExpression(Instruction *);
267 const StoreExpression *createStoreExpression(StoreInst *, MemoryAccess *,
269 LoadExpression *createLoadExpression(Type *, Value *, LoadInst *,
270 MemoryAccess *, const BasicBlock *);
272 const CallExpression *createCallExpression(CallInst *, MemoryAccess *,
274 const AggregateValueExpression *
275 createAggregateValueExpression(Instruction *, const BasicBlock *);
276 bool setBasicExpressionInfo(Instruction *, BasicExpression *,
279 // Congruence class handling.
280 CongruenceClass *createCongruenceClass(Value *Leader, const Expression *E) {
281 auto *result = new CongruenceClass(NextCongruenceNum++, Leader, E);
282 CongruenceClasses.emplace_back(result);
286 CongruenceClass *createSingletonCongruenceClass(Value *Member) {
287 CongruenceClass *CClass = createCongruenceClass(Member, nullptr);
288 CClass->Members.insert(Member);
289 ValueToClass[Member] = CClass;
292 void initializeCongruenceClasses(Function &F);
294 // Value number an Instruction or MemoryPhi.
295 void valueNumberMemoryPhi(MemoryPhi *);
296 void valueNumberInstruction(Instruction *);
298 // Symbolic evaluation.
299 const Expression *checkSimplificationResults(Expression *, Instruction *,
301 const Expression *performSymbolicEvaluation(Value *, const BasicBlock *);
302 const Expression *performSymbolicLoadEvaluation(Instruction *,
304 const Expression *performSymbolicStoreEvaluation(Instruction *,
306 const Expression *performSymbolicCallEvaluation(Instruction *,
308 const Expression *performSymbolicPHIEvaluation(Instruction *,
310 bool setMemoryAccessEquivTo(MemoryAccess *From, MemoryAccess *To);
311 const Expression *performSymbolicAggrValueEvaluation(Instruction *,
314 // Congruence finding.
315 // Templated to allow them to work both on BB's and BB-edges.
317 Value *lookupOperandLeader(Value *, const User *, const T &) const;
318 void performCongruenceFinding(Value *, const Expression *);
320 // Reachability handling.
321 void updateReachableEdge(BasicBlock *, BasicBlock *);
322 void processOutgoingEdges(TerminatorInst *, BasicBlock *);
323 bool isOnlyReachableViaThisEdge(const BasicBlockEdge &) const;
324 Value *findConditionEquivalence(Value *, BasicBlock *) const;
325 MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const;
329 void convertDenseToDFSOrdered(CongruenceClass::MemberSet &,
330 std::vector<ValueDFS> &);
332 bool eliminateInstructions(Function &);
333 void replaceInstruction(Instruction *, Value *);
334 void markInstructionForDeletion(Instruction *);
335 void deleteInstructionsInBlock(BasicBlock *);
337 // New instruction creation.
338 void handleNewInstruction(Instruction *){};
339 void markUsersTouched(Value *);
340 void markMemoryUsersTouched(MemoryAccess *);
343 void cleanupTables();
344 std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
345 void updateProcessedCount(Value *V);
346 void verifyMemoryCongruency();
351 // createGVNPass - The public interface to this file.
352 FunctionPass *llvm::createNewGVNPass() { return new NewGVN(); }
354 template <typename T>
355 static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS) {
356 if ((!isa<LoadExpression>(RHS) && !isa<StoreExpression>(RHS)) ||
357 !LHS.BasicExpression::equals(RHS)) {
359 } else if (const auto *L = dyn_cast<LoadExpression>(&RHS)) {
360 if (LHS.getDefiningAccess() != L->getDefiningAccess())
362 } else if (const auto *S = dyn_cast<StoreExpression>(&RHS)) {
363 if (LHS.getDefiningAccess() != S->getDefiningAccess())
369 bool LoadExpression::equals(const Expression &Other) const {
370 return equalsLoadStoreHelper(*this, Other);
373 bool StoreExpression::equals(const Expression &Other) const {
374 return equalsLoadStoreHelper(*this, Other);
378 static std::string getBlockName(const BasicBlock *B) {
379 return DOTGraphTraits<const Function *>::getSimpleNodeLabel(B, nullptr);
383 INITIALIZE_PASS_BEGIN(NewGVN, "newgvn", "Global Value Numbering", false, false)
384 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
385 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
386 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
387 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
388 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
389 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
390 INITIALIZE_PASS_END(NewGVN, "newgvn", "Global Value Numbering", false, false)
392 PHIExpression *NewGVN::createPHIExpression(Instruction *I) {
393 BasicBlock *PhiBlock = I->getParent();
394 auto *PN = cast<PHINode>(I);
395 auto *E = new (ExpressionAllocator)
396 PHIExpression(PN->getNumOperands(), I->getParent());
398 E->allocateOperands(ArgRecycler, ExpressionAllocator);
399 E->setType(I->getType());
400 E->setOpcode(I->getOpcode());
402 auto ReachablePhiArg = [&](const Use &U) {
403 return ReachableBlocks.count(PN->getIncomingBlock(U));
406 // Filter out unreachable operands
407 auto Filtered = make_filter_range(PN->operands(), ReachablePhiArg);
409 std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
410 [&](const Use &U) -> Value * {
411 // Don't try to transform self-defined phis
414 const BasicBlockEdge BBE(PN->getIncomingBlock(U), PhiBlock);
415 return lookupOperandLeader(U, I, BBE);
420 // Set basic expression info (Arguments, type, opcode) for Expression
421 // E from Instruction I in block B.
422 bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E,
423 const BasicBlock *B) {
424 bool AllConstant = true;
425 if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
426 E->setType(GEP->getSourceElementType());
428 E->setType(I->getType());
429 E->setOpcode(I->getOpcode());
430 E->allocateOperands(ArgRecycler, ExpressionAllocator);
432 // Transform the operand array into an operand leader array, and keep track of
433 // whether all members are constant.
434 std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) {
435 auto Operand = lookupOperandLeader(O, I, B);
436 AllConstant &= isa<Constant>(Operand);
443 const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
444 Value *Arg1, Value *Arg2,
445 const BasicBlock *B) {
446 auto *E = new (ExpressionAllocator) BasicExpression(2);
449 E->setOpcode(Opcode);
450 E->allocateOperands(ArgRecycler, ExpressionAllocator);
451 if (Instruction::isCommutative(Opcode)) {
452 // Ensure that commutative instructions that only differ by a permutation
453 // of their operands get the same value number by sorting the operand value
454 // numbers. Since all commutative instructions have two operands it is more
455 // efficient to sort by hand rather than using, say, std::sort.
457 std::swap(Arg1, Arg2);
459 E->op_push_back(lookupOperandLeader(Arg1, nullptr, B));
460 E->op_push_back(lookupOperandLeader(Arg2, nullptr, B));
462 Value *V = SimplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), *DL, TLI,
464 if (const Expression *SimplifiedE = checkSimplificationResults(E, nullptr, V))
469 // Take a Value returned by simplification of Expression E/Instruction
470 // I, and see if it resulted in a simpler expression. If so, return
472 // TODO: Once finished, this should not take an Instruction, we only
473 // use it for printing.
474 const Expression *NewGVN::checkSimplificationResults(Expression *E,
475 Instruction *I, Value *V) {
478 if (auto *C = dyn_cast<Constant>(V)) {
480 DEBUG(dbgs() << "Simplified " << *I << " to "
481 << " constant " << *C << "\n");
482 NumGVNOpsSimplified++;
483 assert(isa<BasicExpression>(E) &&
484 "We should always have had a basic expression here");
486 cast<BasicExpression>(E)->deallocateOperands(ArgRecycler);
487 ExpressionAllocator.Deallocate(E);
488 return createConstantExpression(C);
489 } else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
491 DEBUG(dbgs() << "Simplified " << *I << " to "
492 << " variable " << *V << "\n");
493 cast<BasicExpression>(E)->deallocateOperands(ArgRecycler);
494 ExpressionAllocator.Deallocate(E);
495 return createVariableExpression(V);
498 CongruenceClass *CC = ValueToClass.lookup(V);
499 if (CC && CC->DefiningExpr) {
501 DEBUG(dbgs() << "Simplified " << *I << " to "
502 << " expression " << *V << "\n");
503 NumGVNOpsSimplified++;
504 assert(isa<BasicExpression>(E) &&
505 "We should always have had a basic expression here");
506 cast<BasicExpression>(E)->deallocateOperands(ArgRecycler);
507 ExpressionAllocator.Deallocate(E);
508 return CC->DefiningExpr;
513 const Expression *NewGVN::createExpression(Instruction *I,
514 const BasicBlock *B) {
516 auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands());
518 bool AllConstant = setBasicExpressionInfo(I, E, B);
520 if (I->isCommutative()) {
521 // Ensure that commutative instructions that only differ by a permutation
522 // of their operands get the same value number by sorting the operand value
523 // numbers. Since all commutative instructions have two operands it is more
524 // efficient to sort by hand rather than using, say, std::sort.
525 assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
526 if (E->getOperand(0) > E->getOperand(1))
527 E->swapOperands(0, 1);
530 // Perform simplificaiton
531 // TODO: Right now we only check to see if we get a constant result.
532 // We may get a less than constant, but still better, result for
537 // We should handle this by simply rewriting the expression.
538 if (auto *CI = dyn_cast<CmpInst>(I)) {
539 // Sort the operand value numbers so x<y and y>x get the same value
541 CmpInst::Predicate Predicate = CI->getPredicate();
542 if (E->getOperand(0) > E->getOperand(1)) {
543 E->swapOperands(0, 1);
544 Predicate = CmpInst::getSwappedPredicate(Predicate);
546 E->setOpcode((CI->getOpcode() << 8) | Predicate);
547 // TODO: 25% of our time is spent in SimplifyCmpInst with pointer operands
548 // TODO: Since we noop bitcasts, we may need to check types before
549 // simplifying, so that we don't end up simplifying based on a wrong
550 // type assumption. We should clean this up so we can use constants of the
553 assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
554 "Wrong types on cmp instruction");
555 if ((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
556 E->getOperand(1)->getType() == I->getOperand(1)->getType())) {
557 Value *V = SimplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1),
559 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
562 } else if (isa<SelectInst>(I)) {
563 if (isa<Constant>(E->getOperand(0)) ||
564 (E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
565 E->getOperand(2)->getType() == I->getOperand(2)->getType())) {
566 Value *V = SimplifySelectInst(E->getOperand(0), E->getOperand(1),
567 E->getOperand(2), *DL, TLI, DT, AC);
568 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
571 } else if (I->isBinaryOp()) {
572 Value *V = SimplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1),
574 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
576 } else if (auto *BI = dyn_cast<BitCastInst>(I)) {
577 Value *V = SimplifyInstruction(BI, *DL, TLI, DT, AC);
578 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
580 } else if (isa<GetElementPtrInst>(I)) {
581 Value *V = SimplifyGEPInst(E->getType(),
582 ArrayRef<Value *>(E->op_begin(), E->op_end()),
584 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
586 } else if (AllConstant) {
587 // We don't bother trying to simplify unless all of the operands
589 // TODO: There are a lot of Simplify*'s we could call here, if we
590 // wanted to. The original motivating case for this code was a
591 // zext i1 false to i8, which we don't have an interface to
592 // simplify (IE there is no SimplifyZExt).
594 SmallVector<Constant *, 8> C;
595 for (Value *Arg : E->operands())
596 C.emplace_back(cast<Constant>(Arg));
598 if (Value *V = ConstantFoldInstOperands(I, C, *DL, TLI))
599 if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
605 const AggregateValueExpression *
606 NewGVN::createAggregateValueExpression(Instruction *I, const BasicBlock *B) {
607 if (auto *II = dyn_cast<InsertValueInst>(I)) {
608 auto *E = new (ExpressionAllocator)
609 AggregateValueExpression(I->getNumOperands(), II->getNumIndices());
610 setBasicExpressionInfo(I, E, B);
611 E->allocateIntOperands(ExpressionAllocator);
612 std::copy(II->idx_begin(), II->idx_end(), int_op_inserter(E));
614 } else if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
615 auto *E = new (ExpressionAllocator)
616 AggregateValueExpression(I->getNumOperands(), EI->getNumIndices());
617 setBasicExpressionInfo(EI, E, B);
618 E->allocateIntOperands(ExpressionAllocator);
619 std::copy(EI->idx_begin(), EI->idx_end(), int_op_inserter(E));
622 llvm_unreachable("Unhandled type of aggregate value operation");
625 const VariableExpression *NewGVN::createVariableExpression(Value *V) {
626 auto *E = new (ExpressionAllocator) VariableExpression(V);
627 E->setOpcode(V->getValueID());
631 const Expression *NewGVN::createVariableOrConstant(Value *V,
632 const BasicBlock *B) {
633 auto Leader = lookupOperandLeader(V, nullptr, B);
634 if (auto *C = dyn_cast<Constant>(Leader))
635 return createConstantExpression(C);
636 return createVariableExpression(Leader);
639 const ConstantExpression *NewGVN::createConstantExpression(Constant *C) {
640 auto *E = new (ExpressionAllocator) ConstantExpression(C);
641 E->setOpcode(C->getValueID());
645 const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) {
646 auto *E = new (ExpressionAllocator) UnknownExpression(I);
647 E->setOpcode(I->getOpcode());
651 const CallExpression *NewGVN::createCallExpression(CallInst *CI,
653 const BasicBlock *B) {
654 // FIXME: Add operand bundles for calls.
656 new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, HV);
657 setBasicExpressionInfo(CI, E, B);
661 // See if we have a congruence class and leader for this operand, and if so,
662 // return it. Otherwise, return the operand itself.
664 Value *NewGVN::lookupOperandLeader(Value *V, const User *U, const T &B) const {
665 CongruenceClass *CC = ValueToClass.lookup(V);
666 if (CC && (CC != InitialClass))
667 return CC->RepLeader;
671 MemoryAccess *NewGVN::lookupMemoryAccessEquiv(MemoryAccess *MA) const {
672 MemoryAccess *Result = MemoryAccessEquiv.lookup(MA);
673 return Result ? Result : MA;
676 LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp,
677 LoadInst *LI, MemoryAccess *DA,
678 const BasicBlock *B) {
679 auto *E = new (ExpressionAllocator) LoadExpression(1, LI, DA);
680 E->allocateOperands(ArgRecycler, ExpressionAllocator);
681 E->setType(LoadType);
683 // Give store and loads same opcode so they value number together.
685 E->op_push_back(lookupOperandLeader(PointerOp, LI, B));
687 E->setAlignment(LI->getAlignment());
689 // TODO: Value number heap versions. We may be able to discover
690 // things alias analysis can't on it's own (IE that a store and a
691 // load have the same value, and thus, it isn't clobbering the load).
695 const StoreExpression *NewGVN::createStoreExpression(StoreInst *SI,
697 const BasicBlock *B) {
699 new (ExpressionAllocator) StoreExpression(SI->getNumOperands(), SI, DA);
700 E->allocateOperands(ArgRecycler, ExpressionAllocator);
701 E->setType(SI->getValueOperand()->getType());
703 // Give store and loads same opcode so they value number together.
705 E->op_push_back(lookupOperandLeader(SI->getPointerOperand(), SI, B));
707 // TODO: Value number heap versions. We may be able to discover
708 // things alias analysis can't on it's own (IE that a store and a
709 // load have the same value, and thus, it isn't clobbering the load).
713 const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I,
714 const BasicBlock *B) {
715 // Unlike loads, we never try to eliminate stores, so we do not check if they
716 // are simple and avoid value numbering them.
717 auto *SI = cast<StoreInst>(I);
718 MemoryAccess *StoreAccess = MSSA->getMemoryAccess(SI);
719 // See if we are defined by a previous store expression, it already has a
720 // value, and it's the same value as our current store. FIXME: Right now, we
721 // only do this for simple stores, we should expand to cover memcpys, etc.
722 if (SI->isSimple()) {
723 // Get the expression, if any, for the RHS of the MemoryDef.
724 MemoryAccess *StoreRHS = lookupMemoryAccessEquiv(
725 cast<MemoryDef>(StoreAccess)->getDefiningAccess());
726 const Expression *OldStore = createStoreExpression(SI, StoreRHS, B);
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
1095 // we determined the expression is congruent to a different memory
1096 // state, use that different memory state. If we determined it didn't,
1097 // we update that as well. Right now, we only support store
1099 if (!isa<MemoryUse>(MA) && isa<StoreExpression>(E) &&
1100 EClass->Members.size() != 1) {
1101 auto *DefAccess = cast<StoreExpression>(E)->getDefiningAccess();
1102 setMemoryAccessEquivTo(MA, DefAccess != MA ? DefAccess : nullptr);
1104 setMemoryAccessEquivTo(MA, nullptr);
1106 markMemoryUsersTouched(MA);
1112 // Process the fact that Edge (from, to) is reachable, including marking
1113 // any newly reachable blocks and instructions for processing.
1114 void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) {
1115 // Check if the Edge was reachable before.
1116 if (ReachableEdges.insert({From, To}).second) {
1117 // If this block wasn't reachable before, all instructions are touched.
1118 if (ReachableBlocks.insert(To).second) {
1119 DEBUG(dbgs() << "Block " << getBlockName(To) << " marked reachable\n");
1120 const auto &InstRange = BlockInstRange.lookup(To);
1121 TouchedInstructions.set(InstRange.first, InstRange.second);
1123 DEBUG(dbgs() << "Block " << getBlockName(To)
1124 << " was reachable, but new edge {" << getBlockName(From)
1125 << "," << getBlockName(To) << "} to it found\n");
1127 // We've made an edge reachable to an existing block, which may
1128 // impact predicates. Otherwise, only mark the phi nodes as touched, as
1129 // they are the only thing that depend on new edges. Anything using their
1130 // values will get propagated to if necessary.
1131 if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(To))
1132 TouchedInstructions.set(InstrDFS[MemPhi]);
1134 auto BI = To->begin();
1135 while (isa<PHINode>(BI)) {
1136 TouchedInstructions.set(InstrDFS[&*BI]);
1143 // Given a predicate condition (from a switch, cmp, or whatever) and a block,
1144 // see if we know some constant value for it already.
1145 Value *NewGVN::findConditionEquivalence(Value *Cond, BasicBlock *B) const {
1146 auto Result = lookupOperandLeader(Cond, nullptr, B);
1147 if (isa<Constant>(Result))
1152 // Process the outgoing edges of a block for reachability.
1153 void NewGVN::processOutgoingEdges(TerminatorInst *TI, BasicBlock *B) {
1154 // Evaluate reachability of terminator instruction.
1156 if ((BR = dyn_cast<BranchInst>(TI)) && BR->isConditional()) {
1157 Value *Cond = BR->getCondition();
1158 Value *CondEvaluated = findConditionEquivalence(Cond, B);
1159 if (!CondEvaluated) {
1160 if (auto *I = dyn_cast<Instruction>(Cond)) {
1161 const Expression *E = createExpression(I, B);
1162 if (const auto *CE = dyn_cast<ConstantExpression>(E)) {
1163 CondEvaluated = CE->getConstantValue();
1165 } else if (isa<ConstantInt>(Cond)) {
1166 CondEvaluated = Cond;
1170 BasicBlock *TrueSucc = BR->getSuccessor(0);
1171 BasicBlock *FalseSucc = BR->getSuccessor(1);
1172 if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
1174 DEBUG(dbgs() << "Condition for Terminator " << *TI
1175 << " evaluated to true\n");
1176 updateReachableEdge(B, TrueSucc);
1177 } else if (CI->isZero()) {
1178 DEBUG(dbgs() << "Condition for Terminator " << *TI
1179 << " evaluated to false\n");
1180 updateReachableEdge(B, FalseSucc);
1183 updateReachableEdge(B, TrueSucc);
1184 updateReachableEdge(B, FalseSucc);
1186 } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
1187 // For switches, propagate the case values into the case
1190 // Remember how many outgoing edges there are to every successor.
1191 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
1193 Value *SwitchCond = SI->getCondition();
1194 Value *CondEvaluated = findConditionEquivalence(SwitchCond, B);
1195 // See if we were able to turn this switch statement into a constant.
1196 if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
1197 auto *CondVal = cast<ConstantInt>(CondEvaluated);
1198 // We should be able to get case value for this.
1199 auto CaseVal = SI->findCaseValue(CondVal);
1200 if (CaseVal.getCaseSuccessor() == SI->getDefaultDest()) {
1201 // We proved the value is outside of the range of the case.
1202 // We can't do anything other than mark the default dest as reachable,
1204 updateReachableEdge(B, SI->getDefaultDest());
1207 // Now get where it goes and mark it reachable.
1208 BasicBlock *TargetBlock = CaseVal.getCaseSuccessor();
1209 updateReachableEdge(B, TargetBlock);
1211 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
1212 BasicBlock *TargetBlock = SI->getSuccessor(i);
1213 ++SwitchEdges[TargetBlock];
1214 updateReachableEdge(B, TargetBlock);
1218 // Otherwise this is either unconditional, or a type we have no
1219 // idea about. Just mark successors as reachable.
1220 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1221 BasicBlock *TargetBlock = TI->getSuccessor(i);
1222 updateReachableEdge(B, TargetBlock);
1225 // This also may be a memory defining terminator, in which case, set it
1226 // equivalent to nothing.
1227 if (MemoryAccess *MA = MSSA->getMemoryAccess(TI))
1228 setMemoryAccessEquivTo(MA, nullptr);
1232 // The algorithm initially places the values of the routine in the INITIAL
1234 // class. The leader of INITIAL is the undetermined value `TOP`.
1235 // When the algorithm has finished, values still in INITIAL are unreachable.
1236 void NewGVN::initializeCongruenceClasses(Function &F) {
1237 // FIXME now i can't remember why this is 2
1238 NextCongruenceNum = 2;
1239 // Initialize all other instructions to be in INITIAL class.
1240 CongruenceClass::MemberSet InitialValues;
1241 InitialClass = createCongruenceClass(nullptr, nullptr);
1243 if (auto *MP = MSSA->getMemoryAccess(&B))
1244 MemoryAccessEquiv.insert({MP, MSSA->getLiveOnEntryDef()});
1247 InitialValues.insert(&I);
1248 ValueToClass[&I] = InitialClass;
1249 // All memory accesses are equivalent to live on entry to start. They must
1250 // be initialized to something so that initial changes are noticed. For
1251 // the maximal answer, we initialize them all to be the same as
1252 // liveOnEntry. Note that to save time, we only initialize the
1253 // MemoryDef's for stores and all MemoryPhis to be equal. Right now, no
1254 // other expression can generate a memory equivalence. If we start
1255 // handling memcpy/etc, we can expand this.
1256 if (isa<StoreInst>(&I))
1257 MemoryAccessEquiv.insert(
1258 {MSSA->getMemoryAccess(&I), MSSA->getLiveOnEntryDef()});
1261 InitialClass->Members.swap(InitialValues);
1263 // Initialize arguments to be in their own unique congruence classes
1264 for (auto &FA : F.args())
1265 createSingletonCongruenceClass(&FA);
1268 void NewGVN::cleanupTables() {
1269 for (unsigned i = 0, e = CongruenceClasses.size(); i != e; ++i) {
1270 DEBUG(dbgs() << "Congruence class " << CongruenceClasses[i]->ID << " has "
1271 << CongruenceClasses[i]->Members.size() << " members\n");
1272 // Make sure we delete the congruence class (probably worth switching to
1273 // a unique_ptr at some point.
1274 delete CongruenceClasses[i];
1275 CongruenceClasses[i] = nullptr;
1278 ValueToClass.clear();
1279 ArgRecycler.clear(ExpressionAllocator);
1280 ExpressionAllocator.Reset();
1281 CongruenceClasses.clear();
1282 ExpressionToClass.clear();
1283 ValueToExpression.clear();
1284 ReachableBlocks.clear();
1285 ReachableEdges.clear();
1287 ProcessedCount.clear();
1291 InstructionsToErase.clear();
1294 BlockInstRange.clear();
1295 TouchedInstructions.clear();
1296 DominatedInstRange.clear();
1297 MemoryAccessEquiv.clear();
1300 std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
1302 unsigned End = Start;
1303 if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(B)) {
1304 InstrDFS[MemPhi] = End++;
1305 DFSToInstr.emplace_back(MemPhi);
1308 for (auto &I : *B) {
1309 InstrDFS[&I] = End++;
1310 DFSToInstr.emplace_back(&I);
1313 // All of the range functions taken half-open ranges (open on the end side).
1314 // So we do not subtract one from count, because at this point it is one
1315 // greater than the last instruction.
1316 return std::make_pair(Start, End);
1319 void NewGVN::updateProcessedCount(Value *V) {
1321 if (ProcessedCount.count(V) == 0) {
1322 ProcessedCount.insert({V, 1});
1324 ProcessedCount[V] += 1;
1325 assert(ProcessedCount[V] < 100 &&
1326 "Seem to have processed the same Value a lot");
1330 // Evaluate MemoryPhi nodes symbolically, just like PHI nodes
1331 void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) {
1332 // If all the arguments are the same, the MemoryPhi has the same value as the
1334 // Filter out unreachable blocks from our operands.
1335 auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) {
1336 return ReachableBlocks.count(MP->getIncomingBlock(U));
1339 assert(Filtered.begin() != Filtered.end() &&
1340 "We should not be processing a MemoryPhi in a completely "
1341 "unreachable block");
1343 // Transform the remaining operands into operand leaders.
1344 // FIXME: mapped_iterator should have a range version.
1345 auto LookupFunc = [&](const Use &U) {
1346 return lookupMemoryAccessEquiv(cast<MemoryAccess>(U));
1348 auto MappedBegin = map_iterator(Filtered.begin(), LookupFunc);
1349 auto MappedEnd = map_iterator(Filtered.end(), LookupFunc);
1351 // and now check if all the elements are equal.
1352 // Sadly, we can't use std::equals since these are random access iterators.
1353 MemoryAccess *AllSameValue = *MappedBegin;
1355 bool AllEqual = std::all_of(
1356 MappedBegin, MappedEnd,
1357 [&AllSameValue](const MemoryAccess *V) { return V == AllSameValue; });
1360 DEBUG(dbgs() << "Memory Phi value numbered to " << *AllSameValue << "\n");
1362 DEBUG(dbgs() << "Memory Phi value numbered to itself\n");
1364 if (setMemoryAccessEquivTo(MP, AllEqual ? AllSameValue : nullptr))
1365 markMemoryUsersTouched(MP);
1368 // Value number a single instruction, symbolically evaluating, performing
1369 // congruence finding, and updating mappings.
1370 void NewGVN::valueNumberInstruction(Instruction *I) {
1371 DEBUG(dbgs() << "Processing instruction " << *I << "\n");
1372 if (isInstructionTriviallyDead(I, TLI)) {
1373 DEBUG(dbgs() << "Skipping unused instruction\n");
1374 markInstructionForDeletion(I);
1377 if (!I->isTerminator()) {
1378 const auto *Symbolized = performSymbolicEvaluation(I, I->getParent());
1379 // If we couldn't come up with a symbolic expression, use the unknown
1381 if (Symbolized == nullptr)
1382 Symbolized = createUnknownExpression(I);
1383 performCongruenceFinding(I, Symbolized);
1385 // Handle terminators that return values. All of them produce values we
1386 // don't currently understand.
1387 if (!I->getType()->isVoidTy()) {
1388 auto *Symbolized = createUnknownExpression(I);
1389 performCongruenceFinding(I, Symbolized);
1391 processOutgoingEdges(dyn_cast<TerminatorInst>(I), I->getParent());
1395 // Verify the that the memory equivalence table makes sense relative to the
1396 // congruence classes.
1397 void NewGVN::verifyMemoryCongruency() {
1398 // Anything equivalent in the memory access table should be in the same
1399 // congruence class.
1401 // Filter out the unreachable and trivially dead entries, because they may
1402 // never have been updated if the instructions were not processed.
1403 auto ReachableAccessPred =
1404 [&](const std::pair<const MemoryAccess *, MemoryAccess *> Pair) {
1405 bool Result = ReachableBlocks.count(Pair.first->getBlock());
1408 if (auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
1409 return !isInstructionTriviallyDead(MemDef->getMemoryInst());
1413 auto Filtered = make_filter_range(MemoryAccessEquiv, ReachableAccessPred);
1414 for (auto KV : Filtered) {
1415 assert(KV.first != KV.second &&
1416 "We added a useless equivalence to the memory equivalence table");
1417 // Unreachable instructions may not have changed because we never process
1419 if (!ReachableBlocks.count(KV.first->getBlock()))
1421 if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
1422 auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second);
1423 if (FirstMUD && SecondMUD)
1425 ValueToClass.lookup(FirstMUD->getMemoryInst()) ==
1426 ValueToClass.lookup(SecondMUD->getMemoryInst()) &&
1427 "The instructions for these memory operations should have been in "
1428 "the same congruence class");
1429 } else if (auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {
1431 // We can only sanely verify that MemoryDefs in the operand list all have
1433 auto ReachableOperandPred = [&](const Use &U) {
1434 return ReachableBlocks.count(FirstMP->getIncomingBlock(U)) &&
1438 // All arguments should in the same class, ignoring unreachable arguments
1439 auto FilteredPhiArgs =
1440 make_filter_range(FirstMP->operands(), ReachableOperandPred);
1441 SmallVector<const CongruenceClass *, 16> PhiOpClasses;
1442 std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
1443 std::back_inserter(PhiOpClasses), [&](const Use &U) {
1444 const MemoryDef *MD = cast<MemoryDef>(U);
1445 return ValueToClass.lookup(MD->getMemoryInst());
1447 assert(std::equal(PhiOpClasses.begin(), PhiOpClasses.end(),
1448 PhiOpClasses.begin()) &&
1449 "All MemoryPhi arguments should be in the same class");
1454 // This is the main transformation entry point.
1455 bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC,
1456 TargetLibraryInfo *_TLI, AliasAnalysis *_AA,
1458 bool Changed = false;
1464 DL = &F.getParent()->getDataLayout();
1465 MSSAWalker = MSSA->getWalker();
1467 // Count number of instructions for sizing of hash tables, and come
1468 // up with a global dfs numbering for instructions.
1469 unsigned ICount = 1;
1470 // Add an empty instruction to account for the fact that we start at 1
1471 DFSToInstr.emplace_back(nullptr);
1472 // Note: We want RPO traversal of the blocks, which is not quite the same as
1473 // dominator tree order, particularly with regard whether backedges get
1474 // visited first or second, given a block with multiple successors.
1475 // If we visit in the wrong order, we will end up performing N times as many
1477 // The dominator tree does guarantee that, for a given dom tree node, it's
1478 // parent must occur before it in the RPO ordering. Thus, we only need to sort
1480 DenseMap<const DomTreeNode *, unsigned> RPOOrdering;
1481 ReversePostOrderTraversal<Function *> RPOT(&F);
1482 unsigned Counter = 0;
1483 for (auto &B : RPOT) {
1484 auto *Node = DT->getNode(B);
1485 assert(Node && "RPO and Dominator tree should have same reachability");
1486 RPOOrdering[Node] = ++Counter;
1488 // Sort dominator tree children arrays into RPO.
1489 for (auto &B : RPOT) {
1490 auto *Node = DT->getNode(B);
1491 if (Node->getChildren().size() > 1)
1492 std::sort(Node->begin(), Node->end(),
1493 [&RPOOrdering](const DomTreeNode *A, const DomTreeNode *B) {
1494 return RPOOrdering[A] < RPOOrdering[B];
1498 // Now a standard depth first ordering of the domtree is equivalent to RPO.
1499 auto DFI = df_begin(DT->getRootNode());
1500 for (auto DFE = df_end(DT->getRootNode()); DFI != DFE; ++DFI) {
1501 BasicBlock *B = DFI->getBlock();
1502 const auto &BlockRange = assignDFSNumbers(B, ICount);
1503 BlockInstRange.insert({B, BlockRange});
1504 ICount += BlockRange.second - BlockRange.first;
1507 // Handle forward unreachable blocks and figure out which blocks
1508 // have single preds.
1510 // Assign numbers to unreachable blocks.
1511 if (!DFI.nodeVisited(DT->getNode(&B))) {
1512 const auto &BlockRange = assignDFSNumbers(&B, ICount);
1513 BlockInstRange.insert({&B, BlockRange});
1514 ICount += BlockRange.second - BlockRange.first;
1518 TouchedInstructions.resize(ICount);
1519 DominatedInstRange.reserve(F.size());
1520 // Ensure we don't end up resizing the expressionToClass map, as
1521 // that can be quite expensive. At most, we have one expression per
1523 ExpressionToClass.reserve(ICount);
1525 // Initialize the touched instructions to include the entry block.
1526 const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock());
1527 TouchedInstructions.set(InstRange.first, InstRange.second);
1528 ReachableBlocks.insert(&F.getEntryBlock());
1530 initializeCongruenceClasses(F);
1532 unsigned int Iterations = 0;
1533 // We start out in the entry block.
1534 BasicBlock *LastBlock = &F.getEntryBlock();
1535 while (TouchedInstructions.any()) {
1537 // Walk through all the instructions in all the blocks in RPO.
1538 for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1;
1539 InstrNum = TouchedInstructions.find_next(InstrNum)) {
1540 assert(InstrNum != 0 && "Bit 0 should never be set, something touched an "
1541 "instruction not in the lookup table");
1542 Value *V = DFSToInstr[InstrNum];
1543 BasicBlock *CurrBlock = nullptr;
1545 if (auto *I = dyn_cast<Instruction>(V))
1546 CurrBlock = I->getParent();
1547 else if (auto *MP = dyn_cast<MemoryPhi>(V))
1548 CurrBlock = MP->getBlock();
1550 llvm_unreachable("DFSToInstr gave us an unknown type of instruction");
1552 // If we hit a new block, do reachability processing.
1553 if (CurrBlock != LastBlock) {
1554 LastBlock = CurrBlock;
1555 bool BlockReachable = ReachableBlocks.count(CurrBlock);
1556 const auto &CurrInstRange = BlockInstRange.lookup(CurrBlock);
1558 // If it's not reachable, erase any touched instructions and move on.
1559 if (!BlockReachable) {
1560 TouchedInstructions.reset(CurrInstRange.first, CurrInstRange.second);
1561 DEBUG(dbgs() << "Skipping instructions in block "
1562 << getBlockName(CurrBlock)
1563 << " because it is unreachable\n");
1566 updateProcessedCount(CurrBlock);
1569 if (auto *MP = dyn_cast<MemoryPhi>(V)) {
1570 DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n");
1571 valueNumberMemoryPhi(MP);
1572 } else if (auto *I = dyn_cast<Instruction>(V)) {
1573 valueNumberInstruction(I);
1575 llvm_unreachable("Should have been a MemoryPhi or Instruction");
1577 updateProcessedCount(V);
1578 // Reset after processing (because we may mark ourselves as touched when
1579 // we propagate equalities).
1580 TouchedInstructions.reset(InstrNum);
1583 NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations);
1585 verifyMemoryCongruency();
1587 Changed |= eliminateInstructions(F);
1589 // Delete all instructions marked for deletion.
1590 for (Instruction *ToErase : InstructionsToErase) {
1591 if (!ToErase->use_empty())
1592 ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType()));
1594 ToErase->eraseFromParent();
1597 // Delete all unreachable blocks.
1598 auto UnreachableBlockPred = [&](const BasicBlock &BB) {
1599 return !ReachableBlocks.count(&BB);
1602 for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
1603 DEBUG(dbgs() << "We believe block " << getBlockName(&BB)
1604 << " is unreachable\n");
1605 deleteInstructionsInBlock(&BB);
1613 bool NewGVN::runOnFunction(Function &F) {
1614 if (skipFunction(F))
1616 return runGVN(F, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
1617 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
1618 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
1619 &getAnalysis<AAResultsWrapperPass>().getAAResults(),
1620 &getAnalysis<MemorySSAWrapperPass>().getMSSA());
1623 PreservedAnalyses NewGVNPass::run(Function &F, AnalysisManager<Function> &AM) {
1626 // Apparently the order in which we get these results matter for
1627 // the old GVN (see Chandler's comment in GVN.cpp). I'll keep
1628 // the same order here, just in case.
1629 auto &AC = AM.getResult<AssumptionAnalysis>(F);
1630 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1631 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1632 auto &AA = AM.getResult<AAManager>(F);
1633 auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
1634 bool Changed = Impl.runGVN(F, &DT, &AC, &TLI, &AA, &MSSA);
1636 return PreservedAnalyses::all();
1637 PreservedAnalyses PA;
1638 PA.preserve<DominatorTreeAnalysis>();
1639 PA.preserve<GlobalsAA>();
1643 // Return true if V is a value that will always be available (IE can
1644 // be placed anywhere) in the function. We don't do globals here
1645 // because they are often worse to put in place.
1646 // TODO: Separate cost from availability
1647 static bool alwaysAvailable(Value *V) {
1648 return isa<Constant>(V) || isa<Argument>(V);
1651 // Get the basic block from an instruction/value.
1652 static BasicBlock *getBlockForValue(Value *V) {
1653 if (auto *I = dyn_cast<Instruction>(V))
1654 return I->getParent();
1658 struct NewGVN::ValueDFS {
1662 // Only one of these will be set.
1663 Value *Val = nullptr;
1666 bool operator<(const ValueDFS &Other) const {
1667 // It's not enough that any given field be less than - we have sets
1668 // of fields that need to be evaluated together to give a proper ordering.
1669 // For example, if you have;
1674 // We want the second to be less than the first, but if we just go field
1675 // by field, we will get to Val 0 < Val 50 and say the first is less than
1676 // the second. We only want it to be less than if the DFS orders are equal.
1678 // Each LLVM instruction only produces one value, and thus the lowest-level
1679 // differentiator that really matters for the stack (and what we use as as a
1680 // replacement) is the local dfs number.
1681 // Everything else in the structure is instruction level, and only affects
1682 // the order in which we will replace operands of a given instruction.
1684 // For a given instruction (IE things with equal dfsin, dfsout, localnum),
1685 // the order of replacement of uses does not matter.
1689 // When you hit b, you will have two valuedfs with the same dfsin, out, and
1691 // The .val will be the same as well.
1692 // The .u's will be different.
1693 // You will replace both, and it does not matter what order you replace them
1694 // in (IE whether you replace operand 2, then operand 1, or operand 1, then
1696 // Similarly for the case of same dfsin, dfsout, localnum, but different
1701 // in c, we will a valuedfs for a, and one for b,with everything the same
1703 // It does not matter what order we replace these operands in.
1704 // You will always end up with the same IR, and this is guaranteed.
1705 return std::tie(DFSIn, DFSOut, LocalNum, Val, U) <
1706 std::tie(Other.DFSIn, Other.DFSOut, Other.LocalNum, Other.Val,
1711 void NewGVN::convertDenseToDFSOrdered(CongruenceClass::MemberSet &Dense,
1712 std::vector<ValueDFS> &DFSOrderedSet) {
1713 for (auto D : Dense) {
1714 // First add the value.
1715 BasicBlock *BB = getBlockForValue(D);
1716 // Constants are handled prior to ever calling this function, so
1717 // we should only be left with instructions as members.
1718 assert(BB && "Should have figured out a basic block for value");
1721 std::pair<int, int> DFSPair = DFSDomMap[BB];
1722 assert(DFSPair.first != -1 && DFSPair.second != -1 && "Invalid DFS Pair");
1723 VD.DFSIn = DFSPair.first;
1724 VD.DFSOut = DFSPair.second;
1726 // If it's an instruction, use the real local dfs number.
1727 if (auto *I = dyn_cast<Instruction>(D))
1728 VD.LocalNum = InstrDFS[I];
1730 llvm_unreachable("Should have been an instruction");
1732 DFSOrderedSet.emplace_back(VD);
1734 // Now add the users.
1735 for (auto &U : D->uses()) {
1736 if (auto *I = dyn_cast<Instruction>(U.getUser())) {
1738 // Put the phi node uses in the incoming block.
1740 if (auto *P = dyn_cast<PHINode>(I)) {
1741 IBlock = P->getIncomingBlock(U);
1742 // Make phi node users appear last in the incoming block
1744 VD.LocalNum = InstrDFS.size() + 1;
1746 IBlock = I->getParent();
1747 VD.LocalNum = InstrDFS[I];
1749 std::pair<int, int> DFSPair = DFSDomMap[IBlock];
1750 VD.DFSIn = DFSPair.first;
1751 VD.DFSOut = DFSPair.second;
1753 DFSOrderedSet.emplace_back(VD);
1759 static void patchReplacementInstruction(Instruction *I, Value *Repl) {
1760 // Patch the replacement so that it is not more restrictive than the value
1762 auto *Op = dyn_cast<BinaryOperator>(I);
1763 auto *ReplOp = dyn_cast<BinaryOperator>(Repl);
1766 ReplOp->andIRFlags(Op);
1768 if (auto *ReplInst = dyn_cast<Instruction>(Repl)) {
1769 // FIXME: If both the original and replacement value are part of the
1770 // same control-flow region (meaning that the execution of one
1771 // guarentees the executation of the other), then we can combine the
1772 // noalias scopes here and do better than the general conservative
1773 // answer used in combineMetadata().
1775 // In general, GVN unifies expressions over different control-flow
1776 // regions, and so we need a conservative combination of the noalias
1778 unsigned KnownIDs[] = {
1779 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
1780 LLVMContext::MD_noalias, LLVMContext::MD_range,
1781 LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load,
1782 LLVMContext::MD_invariant_group};
1783 combineMetadata(ReplInst, I, KnownIDs);
1787 static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {
1788 patchReplacementInstruction(I, Repl);
1789 I->replaceAllUsesWith(Repl);
1792 void NewGVN::deleteInstructionsInBlock(BasicBlock *BB) {
1793 DEBUG(dbgs() << " BasicBlock Dead:" << *BB);
1794 ++NumGVNBlocksDeleted;
1796 // Check to see if there are non-terminating instructions to delete.
1797 if (isa<TerminatorInst>(BB->begin()))
1800 // Delete the instructions backwards, as it has a reduced likelihood of having
1801 // to update as many def-use and use-def chains. Start after the terminator.
1802 auto StartPoint = BB->rbegin();
1804 // Note that we explicitly recalculate BB->rend() on each iteration,
1805 // as it may change when we remove the first instruction.
1806 for (BasicBlock::reverse_iterator I(StartPoint); I != BB->rend();) {
1807 Instruction &Inst = *I++;
1808 if (!Inst.use_empty())
1809 Inst.replaceAllUsesWith(UndefValue::get(Inst.getType()));
1810 if (isa<LandingPadInst>(Inst))
1813 Inst.eraseFromParent();
1814 ++NumGVNInstrDeleted;
1818 void NewGVN::markInstructionForDeletion(Instruction *I) {
1819 DEBUG(dbgs() << "Marking " << *I << " for deletion\n");
1820 InstructionsToErase.insert(I);
1823 void NewGVN::replaceInstruction(Instruction *I, Value *V) {
1825 DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n");
1826 patchAndReplaceAllUsesWith(I, V);
1827 // We save the actual erasing to avoid invalidating memory
1828 // dependencies until we are done with everything.
1829 markInstructionForDeletion(I);
1834 // This is a stack that contains both the value and dfs info of where
1835 // that value is valid.
1836 class ValueDFSStack {
1838 Value *back() const { return ValueStack.back(); }
1839 std::pair<int, int> dfs_back() const { return DFSStack.back(); }
1841 void push_back(Value *V, int DFSIn, int DFSOut) {
1842 ValueStack.emplace_back(V);
1843 DFSStack.emplace_back(DFSIn, DFSOut);
1845 bool empty() const { return DFSStack.empty(); }
1846 bool isInScope(int DFSIn, int DFSOut) const {
1849 return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
1852 void popUntilDFSScope(int DFSIn, int DFSOut) {
1854 // These two should always be in sync at this point.
1855 assert(ValueStack.size() == DFSStack.size() &&
1856 "Mismatch between ValueStack and DFSStack");
1858 !DFSStack.empty() &&
1859 !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
1860 DFSStack.pop_back();
1861 ValueStack.pop_back();
1866 SmallVector<Value *, 8> ValueStack;
1867 SmallVector<std::pair<int, int>, 8> DFSStack;
1871 bool NewGVN::eliminateInstructions(Function &F) {
1872 // This is a non-standard eliminator. The normal way to eliminate is
1873 // to walk the dominator tree in order, keeping track of available
1874 // values, and eliminating them. However, this is mildly
1875 // pointless. It requires doing lookups on every instruction,
1876 // regardless of whether we will ever eliminate it. For
1877 // instructions part of most singleton congruence classes, we know we
1878 // will never eliminate them.
1880 // Instead, this eliminator looks at the congruence classes directly, sorts
1881 // them into a DFS ordering of the dominator tree, and then we just
1882 // perform elimination straight on the sets by walking the congruence
1883 // class member uses in order, and eliminate the ones dominated by the
1884 // last member. This is worst case O(E log E) where E = number of
1885 // instructions in a single congruence class. In theory, this is all
1886 // instructions. In practice, it is much faster, as most instructions are
1887 // either in singleton congruence classes or can't possibly be eliminated
1888 // anyway (if there are no overlapping DFS ranges in class).
1889 // When we find something not dominated, it becomes the new leader
1890 // for elimination purposes.
1891 // TODO: If we wanted to be faster, We could remove any members with no
1892 // overlapping ranges while sorting, as we will never eliminate anything
1893 // with those members, as they don't dominate anything else in our set.
1895 bool AnythingReplaced = false;
1897 // Since we are going to walk the domtree anyway, and we can't guarantee the
1898 // DFS numbers are updated, we compute some ourselves.
1899 DT->updateDFSNumbers();
1902 if (!ReachableBlocks.count(&B)) {
1903 for (const auto S : successors(&B)) {
1904 for (auto II = S->begin(); isa<PHINode>(II); ++II) {
1905 auto &Phi = cast<PHINode>(*II);
1906 DEBUG(dbgs() << "Replacing incoming value of " << *II << " for block "
1908 << " with undef due to it being unreachable\n");
1909 for (auto &Operand : Phi.incoming_values())
1910 if (Phi.getIncomingBlock(Operand) == &B)
1911 Operand.set(UndefValue::get(Phi.getType()));
1915 DomTreeNode *Node = DT->getNode(&B);
1917 DFSDomMap[&B] = {Node->getDFSNumIn(), Node->getDFSNumOut()};
1920 for (CongruenceClass *CC : CongruenceClasses) {
1921 // FIXME: We should eventually be able to replace everything still
1922 // in the initial class with undef, as they should be unreachable.
1923 // Right now, initial still contains some things we skip value
1924 // numbering of (UNREACHABLE's, for example).
1925 if (CC == InitialClass || CC->Dead)
1927 assert(CC->RepLeader && "We should have had a leader");
1929 // If this is a leader that is always available, and it's a
1930 // constant or has no equivalences, just replace everything with
1931 // it. We then update the congruence class with whatever members
1933 if (alwaysAvailable(CC->RepLeader)) {
1934 SmallPtrSet<Value *, 4> MembersLeft;
1935 for (auto M : CC->Members) {
1939 // Void things have no uses we can replace.
1940 if (Member == CC->RepLeader || Member->getType()->isVoidTy()) {
1941 MembersLeft.insert(Member);
1945 DEBUG(dbgs() << "Found replacement " << *(CC->RepLeader) << " for "
1946 << *Member << "\n");
1947 // Due to equality propagation, these may not always be
1948 // instructions, they may be real values. We don't really
1949 // care about trying to replace the non-instructions.
1950 if (auto *I = dyn_cast<Instruction>(Member)) {
1951 assert(CC->RepLeader != I &&
1952 "About to accidentally remove our leader");
1953 replaceInstruction(I, CC->RepLeader);
1954 AnythingReplaced = true;
1958 MembersLeft.insert(I);
1961 CC->Members.swap(MembersLeft);
1964 DEBUG(dbgs() << "Eliminating in congruence class " << CC->ID << "\n");
1965 // If this is a singleton, we can skip it.
1966 if (CC->Members.size() != 1) {
1968 // This is a stack because equality replacement/etc may place
1969 // constants in the middle of the member list, and we want to use
1970 // those constant values in preference to the current leader, over
1971 // the scope of those constants.
1972 ValueDFSStack EliminationStack;
1974 // Convert the members to DFS ordered sets and then merge them.
1975 std::vector<ValueDFS> DFSOrderedSet;
1976 convertDenseToDFSOrdered(CC->Members, DFSOrderedSet);
1978 // Sort the whole thing.
1979 sort(DFSOrderedSet.begin(), DFSOrderedSet.end());
1981 for (auto &C : DFSOrderedSet) {
1982 int MemberDFSIn = C.DFSIn;
1983 int MemberDFSOut = C.DFSOut;
1984 Value *Member = C.Val;
1985 Use *MemberUse = C.U;
1987 // We ignore void things because we can't get a value from them.
1988 if (Member && Member->getType()->isVoidTy())
1991 if (EliminationStack.empty()) {
1992 DEBUG(dbgs() << "Elimination Stack is empty\n");
1994 DEBUG(dbgs() << "Elimination Stack Top DFS numbers are ("
1995 << EliminationStack.dfs_back().first << ","
1996 << EliminationStack.dfs_back().second << ")\n");
1998 if (Member && isa<Constant>(Member))
1999 assert(isa<Constant>(CC->RepLeader));
2001 DEBUG(dbgs() << "Current DFS numbers are (" << MemberDFSIn << ","
2002 << MemberDFSOut << ")\n");
2003 // First, we see if we are out of scope or empty. If so,
2004 // and there equivalences, we try to replace the top of
2005 // stack with equivalences (if it's on the stack, it must
2006 // not have been eliminated yet).
2007 // Then we synchronize to our current scope, by
2008 // popping until we are back within a DFS scope that
2009 // dominates the current member.
2010 // Then, what happens depends on a few factors
2011 // If the stack is now empty, we need to push
2012 // If we have a constant or a local equivalence we want to
2013 // start using, we also push.
2014 // Otherwise, we walk along, processing members who are
2015 // dominated by this scope, and eliminate them.
2017 Member && (EliminationStack.empty() || isa<Constant>(Member));
2019 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
2021 if (OutOfScope || ShouldPush) {
2022 // Sync to our current scope.
2023 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
2024 ShouldPush |= Member && EliminationStack.empty();
2026 EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
2030 // If we get to this point, and the stack is empty we must have a use
2031 // with nothing we can use to eliminate it, just skip it.
2032 if (EliminationStack.empty())
2035 // Skip the Value's, we only want to eliminate on their uses.
2038 Value *Result = EliminationStack.back();
2040 // Don't replace our existing users with ourselves, and don't replace
2041 // phi node arguments with the result of the same phi node.
2042 // IE tmp = phi(tmp11, undef); tmp11 = foo -> tmp = phi(tmp, undef)
2043 if (MemberUse->get() == Result ||
2044 (isa<PHINode>(Result) && MemberUse->getUser() == Result))
2047 DEBUG(dbgs() << "Found replacement " << *Result << " for "
2048 << *MemberUse->get() << " in " << *(MemberUse->getUser())
2051 // If we replaced something in an instruction, handle the patching of
2053 if (auto *ReplacedInst = dyn_cast<Instruction>(MemberUse->get()))
2054 patchReplacementInstruction(ReplacedInst, Result);
2056 assert(isa<Instruction>(MemberUse->getUser()));
2057 MemberUse->set(Result);
2058 AnythingReplaced = true;
2063 // Cleanup the congruence class.
2064 SmallPtrSet<Value *, 4> MembersLeft;
2065 for (Value *Member : CC->Members) {
2066 if (Member->getType()->isVoidTy()) {
2067 MembersLeft.insert(Member);
2071 if (auto *MemberInst = dyn_cast<Instruction>(Member)) {
2072 if (isInstructionTriviallyDead(MemberInst)) {
2073 // TODO: Don't mark loads of undefs.
2074 markInstructionForDeletion(MemberInst);
2078 MembersLeft.insert(Member);
2080 CC->Members.swap(MembersLeft);
2083 return AnythingReplaced;