LLVM  16.0.0git
NewGVN.cpp
Go to the documentation of this file.
1 //===- NewGVN.cpp - Global Value Numbering Pass ---------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
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
18 /// Karthik Gargi.
19 ///
20 /// A brief overview of the algorithm: The algorithm is essentially the same as
21 /// the standard RPO value numbering algorithm (a good reference is the paper
22 /// "SCC based value numbering" by L. Taylor Simpson) with one major difference:
23 /// The RPO algorithm proceeds, on every iteration, to process every reachable
24 /// block and every instruction in that block. This is because the standard RPO
25 /// algorithm does not track what things have the same value number, it only
26 /// tracks what the value number of a given operation is (the mapping is
27 /// operation -> value number). Thus, when a value number of an operation
28 /// changes, it must reprocess everything to ensure all uses of a value number
29 /// get updated properly. In constrast, the sparse algorithm we use *also*
30 /// tracks what operations have a given value number (IE it also tracks the
31 /// reverse mapping from value number -> operations with that value number), so
32 /// that it only needs to reprocess the instructions that are affected when
33 /// something's value number changes. The vast majority of complexity and code
34 /// in this file is devoted to tracking what value numbers could change for what
35 /// instructions when various things happen. The rest of the algorithm is
36 /// devoted to performing symbolic evaluation, forward propagation, and
37 /// simplification of operations based on the value numbers deduced so far
38 ///
39 /// In order to make the GVN mostly-complete, we use a technique derived from
40 /// "Detection of Redundant Expressions: A Complete and Polynomial-time
41 /// Algorithm in SSA" by R.R. Pai. The source of incompleteness in most SSA
42 /// based GVN algorithms is related to their inability to detect equivalence
43 /// between phi of ops (IE phi(a+b, c+d)) and op of phis (phi(a,c) + phi(b, d)).
44 /// We resolve this issue by generating the equivalent "phi of ops" form for
45 /// each op of phis we see, in a way that only takes polynomial time to resolve.
46 ///
47 /// We also do not perform elimination by using any published algorithm. All
48 /// published algorithms are O(Instructions). Instead, we use a technique that
49 /// is O(number of operations with the same value number), enabling us to skip
50 /// trying to eliminate things that have unique value numbers.
51 //
52 //===----------------------------------------------------------------------===//
53 
55 #include "llvm/ADT/ArrayRef.h"
56 #include "llvm/ADT/BitVector.h"
57 #include "llvm/ADT/DenseMap.h"
58 #include "llvm/ADT/DenseMapInfo.h"
59 #include "llvm/ADT/DenseSet.h"
61 #include "llvm/ADT/GraphTraits.h"
62 #include "llvm/ADT/Hashing.h"
65 #include "llvm/ADT/SetOperations.h"
66 #include "llvm/ADT/SmallPtrSet.h"
67 #include "llvm/ADT/SmallVector.h"
69 #include "llvm/ADT/Statistic.h"
81 #include "llvm/IR/Argument.h"
82 #include "llvm/IR/BasicBlock.h"
83 #include "llvm/IR/Constant.h"
84 #include "llvm/IR/Constants.h"
85 #include "llvm/IR/Dominators.h"
86 #include "llvm/IR/Function.h"
87 #include "llvm/IR/InstrTypes.h"
88 #include "llvm/IR/Instruction.h"
89 #include "llvm/IR/Instructions.h"
90 #include "llvm/IR/IntrinsicInst.h"
91 #include "llvm/IR/PatternMatch.h"
92 #include "llvm/IR/Type.h"
93 #include "llvm/IR/Use.h"
94 #include "llvm/IR/User.h"
95 #include "llvm/IR/Value.h"
96 #include "llvm/InitializePasses.h"
97 #include "llvm/Pass.h"
98 #include "llvm/Support/Allocator.h"
100 #include "llvm/Support/Casting.h"
102 #include "llvm/Support/Debug.h"
107 #include "llvm/Transforms/Scalar.h"
113 #include <algorithm>
114 #include <cassert>
115 #include <cstdint>
116 #include <iterator>
117 #include <map>
118 #include <memory>
119 #include <set>
120 #include <string>
121 #include <tuple>
122 #include <utility>
123 #include <vector>
124 
125 using namespace llvm;
126 using namespace llvm::GVNExpression;
127 using namespace llvm::VNCoercion;
128 using namespace llvm::PatternMatch;
129 
130 #define DEBUG_TYPE "newgvn"
131 
132 STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted");
133 STATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted");
134 STATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified");
135 STATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same");
136 STATISTIC(NumGVNMaxIterations,
137  "Maximum Number of iterations it took to converge GVN");
138 STATISTIC(NumGVNLeaderChanges, "Number of leader changes");
139 STATISTIC(NumGVNSortedLeaderChanges, "Number of sorted leader changes");
140 STATISTIC(NumGVNAvoidedSortedLeaderChanges,
141  "Number of avoided sorted leader changes");
142 STATISTIC(NumGVNDeadStores, "Number of redundant/dead stores eliminated");
143 STATISTIC(NumGVNPHIOfOpsCreated, "Number of PHI of ops created");
144 STATISTIC(NumGVNPHIOfOpsEliminations,
145  "Number of things eliminated using PHI of ops");
146 DEBUG_COUNTER(VNCounter, "newgvn-vn",
147  "Controls which instructions are value numbered");
148 DEBUG_COUNTER(PHIOfOpsCounter, "newgvn-phi",
149  "Controls which instructions we create phi of ops for");
150 // Currently store defining access refinement is too slow due to basicaa being
151 // egregiously slow. This flag lets us keep it working while we work on this
152 // issue.
153 static cl::opt<bool> EnableStoreRefinement("enable-store-refinement",
154  cl::init(false), cl::Hidden);
155 
156 /// Currently, the generation "phi of ops" can result in correctness issues.
157 static cl::opt<bool> EnablePhiOfOps("enable-phi-of-ops", cl::init(true),
158  cl::Hidden);
159 
160 //===----------------------------------------------------------------------===//
161 // GVN Pass
162 //===----------------------------------------------------------------------===//
163 
164 // Anchor methods.
165 namespace llvm {
166 namespace GVNExpression {
167 
168 Expression::~Expression() = default;
175 
176 } // end namespace GVNExpression
177 } // end namespace llvm
178 
179 namespace {
180 
181 // Tarjan's SCC finding algorithm with Nuutila's improvements
182 // SCCIterator is actually fairly complex for the simple thing we want.
183 // It also wants to hand us SCC's that are unrelated to the phi node we ask
184 // about, and have us process them there or risk redoing work.
185 // Graph traits over a filter iterator also doesn't work that well here.
186 // This SCC finder is specialized to walk use-def chains, and only follows
187 // instructions,
188 // not generic values (arguments, etc).
189 struct TarjanSCC {
190  TarjanSCC() : Components(1) {}
191 
192  void Start(const Instruction *Start) {
193  if (Root.lookup(Start) == 0)
194  FindSCC(Start);
195  }
196 
197  const SmallPtrSetImpl<const Value *> &getComponentFor(const Value *V) const {
198  unsigned ComponentID = ValueToComponent.lookup(V);
199 
200  assert(ComponentID > 0 &&
201  "Asking for a component for a value we never processed");
202  return Components[ComponentID];
203  }
204 
205 private:
206  void FindSCC(const Instruction *I) {
207  Root[I] = ++DFSNum;
208  // Store the DFS Number we had before it possibly gets incremented.
209  unsigned int OurDFS = DFSNum;
210  for (const auto &Op : I->operands()) {
211  if (auto *InstOp = dyn_cast<Instruction>(Op)) {
212  if (Root.lookup(Op) == 0)
213  FindSCC(InstOp);
214  if (!InComponent.count(Op))
215  Root[I] = std::min(Root.lookup(I), Root.lookup(Op));
216  }
217  }
218  // See if we really were the root of a component, by seeing if we still have
219  // our DFSNumber. If we do, we are the root of the component, and we have
220  // completed a component. If we do not, we are not the root of a component,
221  // and belong on the component stack.
222  if (Root.lookup(I) == OurDFS) {
223  unsigned ComponentID = Components.size();
224  Components.resize(Components.size() + 1);
225  auto &Component = Components.back();
226  Component.insert(I);
227  LLVM_DEBUG(dbgs() << "Component root is " << *I << "\n");
228  InComponent.insert(I);
229  ValueToComponent[I] = ComponentID;
230  // Pop a component off the stack and label it.
231  while (!Stack.empty() && Root.lookup(Stack.back()) >= OurDFS) {
232  auto *Member = Stack.back();
233  LLVM_DEBUG(dbgs() << "Component member is " << *Member << "\n");
234  Component.insert(Member);
235  InComponent.insert(Member);
236  ValueToComponent[Member] = ComponentID;
237  Stack.pop_back();
238  }
239  } else {
240  // Part of a component, push to stack
241  Stack.push_back(I);
242  }
243  }
244 
245  unsigned int DFSNum = 1;
246  SmallPtrSet<const Value *, 8> InComponent;
249 
250  // Store the components as vector of ptr sets, because we need the topo order
251  // of SCC's, but not individual member order
253 
254  DenseMap<const Value *, unsigned> ValueToComponent;
255 };
256 
257 // Congruence classes represent the set of expressions/instructions
258 // that are all the same *during some scope in the function*.
259 // That is, because of the way we perform equality propagation, and
260 // because of memory value numbering, it is not correct to assume
261 // you can willy-nilly replace any member with any other at any
262 // point in the function.
263 //
264 // For any Value in the Member set, it is valid to replace any dominated member
265 // with that Value.
266 //
267 // Every congruence class has a leader, and the leader is used to symbolize
268 // instructions in a canonical way (IE every operand of an instruction that is a
269 // member of the same congruence class will always be replaced with leader
270 // during symbolization). To simplify symbolization, we keep the leader as a
271 // constant if class can be proved to be a constant value. Otherwise, the
272 // leader is the member of the value set with the smallest DFS number. Each
273 // congruence class also has a defining expression, though the expression may be
274 // null. If it exists, it can be used for forward propagation and reassociation
275 // of values.
276 
277 // For memory, we also track a representative MemoryAccess, and a set of memory
278 // members for MemoryPhis (which have no real instructions). Note that for
279 // memory, it seems tempting to try to split the memory members into a
280 // MemoryCongruenceClass or something. Unfortunately, this does not work
281 // easily. The value numbering of a given memory expression depends on the
282 // leader of the memory congruence class, and the leader of memory congruence
283 // class depends on the value numbering of a given memory expression. This
284 // leads to wasted propagation, and in some cases, missed optimization. For
285 // example: If we had value numbered two stores together before, but now do not,
286 // we move them to a new value congruence class. This in turn will move at one
287 // of the memorydefs to a new memory congruence class. Which in turn, affects
288 // the value numbering of the stores we just value numbered (because the memory
289 // congruence class is part of the value number). So while theoretically
290 // possible to split them up, it turns out to be *incredibly* complicated to get
291 // it to work right, because of the interdependency. While structurally
292 // slightly messier, it is algorithmically much simpler and faster to do what we
293 // do here, and track them both at once in the same class.
294 // Note: The default iterators for this class iterate over values
295 class CongruenceClass {
296 public:
297  using MemberType = Value;
298  using MemberSet = SmallPtrSet<MemberType *, 4>;
299  using MemoryMemberType = MemoryPhi;
300  using MemoryMemberSet = SmallPtrSet<const MemoryMemberType *, 2>;
301 
302  explicit CongruenceClass(unsigned ID) : ID(ID) {}
303  CongruenceClass(unsigned ID, Value *Leader, const Expression *E)
304  : ID(ID), RepLeader(Leader), DefiningExpr(E) {}
305 
306  unsigned getID() const { return ID; }
307 
308  // True if this class has no members left. This is mainly used for assertion
309  // purposes, and for skipping empty classes.
310  bool isDead() const {
311  // If it's both dead from a value perspective, and dead from a memory
312  // perspective, it's really dead.
313  return empty() && memory_empty();
314  }
315 
316  // Leader functions
317  Value *getLeader() const { return RepLeader; }
318  void setLeader(Value *Leader) { RepLeader = Leader; }
319  const std::pair<Value *, unsigned int> &getNextLeader() const {
320  return NextLeader;
321  }
322  void resetNextLeader() { NextLeader = {nullptr, ~0}; }
323  void addPossibleNextLeader(std::pair<Value *, unsigned int> LeaderPair) {
324  if (LeaderPair.second < NextLeader.second)
325  NextLeader = LeaderPair;
326  }
327 
328  Value *getStoredValue() const { return RepStoredValue; }
329  void setStoredValue(Value *Leader) { RepStoredValue = Leader; }
330  const MemoryAccess *getMemoryLeader() const { return RepMemoryAccess; }
331  void setMemoryLeader(const MemoryAccess *Leader) { RepMemoryAccess = Leader; }
332 
333  // Forward propagation info
334  const Expression *getDefiningExpr() const { return DefiningExpr; }
335 
336  // Value member set
337  bool empty() const { return Members.empty(); }
338  unsigned size() const { return Members.size(); }
339  MemberSet::const_iterator begin() const { return Members.begin(); }
340  MemberSet::const_iterator end() const { return Members.end(); }
341  void insert(MemberType *M) { Members.insert(M); }
342  void erase(MemberType *M) { Members.erase(M); }
343  void swap(MemberSet &Other) { Members.swap(Other); }
344 
345  // Memory member set
346  bool memory_empty() const { return MemoryMembers.empty(); }
347  unsigned memory_size() const { return MemoryMembers.size(); }
348  MemoryMemberSet::const_iterator memory_begin() const {
349  return MemoryMembers.begin();
350  }
351  MemoryMemberSet::const_iterator memory_end() const {
352  return MemoryMembers.end();
353  }
355  return make_range(memory_begin(), memory_end());
356  }
357 
358  void memory_insert(const MemoryMemberType *M) { MemoryMembers.insert(M); }
359  void memory_erase(const MemoryMemberType *M) { MemoryMembers.erase(M); }
360 
361  // Store count
362  unsigned getStoreCount() const { return StoreCount; }
363  void incStoreCount() { ++StoreCount; }
364  void decStoreCount() {
365  assert(StoreCount != 0 && "Store count went negative");
366  --StoreCount;
367  }
368 
369  // True if this class has no memory members.
370  bool definesNoMemory() const { return StoreCount == 0 && memory_empty(); }
371 
372  // Return true if two congruence classes are equivalent to each other. This
373  // means that every field but the ID number and the dead field are equivalent.
374  bool isEquivalentTo(const CongruenceClass *Other) const {
375  if (!Other)
376  return false;
377  if (this == Other)
378  return true;
379 
380  if (std::tie(StoreCount, RepLeader, RepStoredValue, RepMemoryAccess) !=
381  std::tie(Other->StoreCount, Other->RepLeader, Other->RepStoredValue,
382  Other->RepMemoryAccess))
383  return false;
384  if (DefiningExpr != Other->DefiningExpr)
385  if (!DefiningExpr || !Other->DefiningExpr ||
386  *DefiningExpr != *Other->DefiningExpr)
387  return false;
388 
389  if (Members.size() != Other->Members.size())
390  return false;
391 
392  return llvm::set_is_subset(Members, Other->Members);
393  }
394 
395 private:
396  unsigned ID;
397 
398  // Representative leader.
399  Value *RepLeader = nullptr;
400 
401  // The most dominating leader after our current leader, because the member set
402  // is not sorted and is expensive to keep sorted all the time.
403  std::pair<Value *, unsigned int> NextLeader = {nullptr, ~0U};
404 
405  // If this is represented by a store, the value of the store.
406  Value *RepStoredValue = nullptr;
407 
408  // If this class contains MemoryDefs or MemoryPhis, this is the leading memory
409  // access.
410  const MemoryAccess *RepMemoryAccess = nullptr;
411 
412  // Defining Expression.
413  const Expression *DefiningExpr = nullptr;
414 
415  // Actual members of this class.
416  MemberSet Members;
417 
418  // This is the set of MemoryPhis that exist in the class. MemoryDefs and
419  // MemoryUses have real instructions representing them, so we only need to
420  // track MemoryPhis here.
421  MemoryMemberSet MemoryMembers;
422 
423  // Number of stores in this congruence class.
424  // This is used so we can detect store equivalence changes properly.
425  int StoreCount = 0;
426 };
427 
428 } // end anonymous namespace
429 
430 namespace llvm {
431 
433  const Expression &E;
434 
435  explicit ExactEqualsExpression(const Expression &E) : E(E) {}
436 
437  hash_code getComputedHash() const { return E.getComputedHash(); }
438 
439  bool operator==(const Expression &Other) const {
440  return E.exactlyEquals(Other);
441  }
442 };
443 
444 template <> struct DenseMapInfo<const Expression *> {
445  static const Expression *getEmptyKey() {
446  auto Val = static_cast<uintptr_t>(-1);
447  Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
448  return reinterpret_cast<const Expression *>(Val);
449  }
450 
451  static const Expression *getTombstoneKey() {
452  auto Val = static_cast<uintptr_t>(~1U);
453  Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
454  return reinterpret_cast<const Expression *>(Val);
455  }
456 
457  static unsigned getHashValue(const Expression *E) {
458  return E->getComputedHash();
459  }
460 
461  static unsigned getHashValue(const ExactEqualsExpression &E) {
462  return E.getComputedHash();
463  }
464 
465  static bool isEqual(const ExactEqualsExpression &LHS, const Expression *RHS) {
466  if (RHS == getTombstoneKey() || RHS == getEmptyKey())
467  return false;
468  return LHS == *RHS;
469  }
470 
471  static bool isEqual(const Expression *LHS, const Expression *RHS) {
472  if (LHS == RHS)
473  return true;
474  if (LHS == getTombstoneKey() || RHS == getTombstoneKey() ||
475  LHS == getEmptyKey() || RHS == getEmptyKey())
476  return false;
477  // Compare hashes before equality. This is *not* what the hashtable does,
478  // since it is computing it modulo the number of buckets, whereas we are
479  // using the full hash keyspace. Since the hashes are precomputed, this
480  // check is *much* faster than equality.
481  if (LHS->getComputedHash() != RHS->getComputedHash())
482  return false;
483  return *LHS == *RHS;
484  }
485 };
486 
487 } // end namespace llvm
488 
489 namespace {
490 
491 class NewGVN {
492  Function &F;
493  DominatorTree *DT = nullptr;
494  const TargetLibraryInfo *TLI = nullptr;
495  AliasAnalysis *AA = nullptr;
496  MemorySSA *MSSA = nullptr;
497  MemorySSAWalker *MSSAWalker = nullptr;
498  AssumptionCache *AC = nullptr;
499  const DataLayout &DL;
500  std::unique_ptr<PredicateInfo> PredInfo;
501 
502  // These are the only two things the create* functions should have
503  // side-effects on due to allocating memory.
504  mutable BumpPtrAllocator ExpressionAllocator;
505  mutable ArrayRecycler<Value *> ArgRecycler;
506  mutable TarjanSCC SCCFinder;
507  const SimplifyQuery SQ;
508 
509  // Number of function arguments, used by ranking
510  unsigned int NumFuncArgs = 0;
511 
512  // RPOOrdering of basic blocks
514 
515  // Congruence class info.
516 
517  // This class is called INITIAL in the paper. It is the class everything
518  // startsout in, and represents any value. Being an optimistic analysis,
519  // anything in the TOP class has the value TOP, which is indeterminate and
520  // equivalent to everything.
521  CongruenceClass *TOPClass = nullptr;
522  std::vector<CongruenceClass *> CongruenceClasses;
523  unsigned NextCongruenceNum = 0;
524 
525  // Value Mappings.
527  DenseMap<Value *, const Expression *> ValueToExpression;
528 
529  // Value PHI handling, used to make equivalence between phi(op, op) and
530  // op(phi, phi).
531  // These mappings just store various data that would normally be part of the
532  // IR.
534 
535  DenseMap<const Value *, bool> OpSafeForPHIOfOps;
536 
537  // Map a temporary instruction we created to a parent block.
539 
540  // Map between the already in-program instructions and the temporary phis we
541  // created that they are known equivalent to.
543 
544  // In order to know when we should re-process instructions that have
545  // phi-of-ops, we track the set of expressions that they needed as
546  // leaders. When we discover new leaders for those expressions, we process the
547  // associated phi-of-op instructions again in case they have changed. The
548  // other way they may change is if they had leaders, and those leaders
549  // disappear. However, at the point they have leaders, there are uses of the
550  // relevant operands in the created phi node, and so they will get reprocessed
551  // through the normal user marking we perform.
552  mutable DenseMap<const Value *, SmallPtrSet<Value *, 2>> AdditionalUsers;
554  ExpressionToPhiOfOps;
555 
556  // Map from temporary operation to MemoryAccess.
558 
559  // Set of all temporary instructions we created.
560  // Note: This will include instructions that were just created during value
561  // numbering. The way to test if something is using them is to check
562  // RealToTemp.
563  DenseSet<Instruction *> AllTempInstructions;
564 
565  // This is the set of instructions to revisit on a reachability change. At
566  // the end of the main iteration loop it will contain at least all the phi of
567  // ops instructions that will be changed to phis, as well as regular phis.
568  // During the iteration loop, it may contain other things, such as phi of ops
569  // instructions that used edge reachability to reach a result, and so need to
570  // be revisited when the edge changes, independent of whether the phi they
571  // depended on changes.
572  DenseMap<BasicBlock *, SparseBitVector<>> RevisitOnReachabilityChange;
573 
574  // Mapping from predicate info we used to the instructions we used it with.
575  // In order to correctly ensure propagation, we must keep track of what
576  // comparisons we used, so that when the values of the comparisons change, we
577  // propagate the information to the places we used the comparison.
579  PredicateToUsers;
580 
581  // the same reasoning as PredicateToUsers. When we skip MemoryAccesses for
582  // stores, we no longer can rely solely on the def-use chains of MemorySSA.
584  MemoryToUsers;
585 
586  // A table storing which memorydefs/phis represent a memory state provably
587  // equivalent to another memory state.
588  // We could use the congruence class machinery, but the MemoryAccess's are
589  // abstract memory states, so they can only ever be equivalent to each other,
590  // and not to constants, etc.
592 
593  // We could, if we wanted, build MemoryPhiExpressions and
594  // MemoryVariableExpressions, etc, and value number them the same way we value
595  // number phi expressions. For the moment, this seems like overkill. They
596  // can only exist in one of three states: they can be TOP (equal to
597  // everything), Equivalent to something else, or unique. Because we do not
598  // create expressions for them, we need to simulate leader change not just
599  // when they change class, but when they change state. Note: We can do the
600  // same thing for phis, and avoid having phi expressions if we wanted, We
601  // should eventually unify in one direction or the other, so this is a little
602  // bit of an experiment in which turns out easier to maintain.
603  enum MemoryPhiState { MPS_Invalid, MPS_TOP, MPS_Equivalent, MPS_Unique };
605 
606  enum InstCycleState { ICS_Unknown, ICS_CycleFree, ICS_Cycle };
607  mutable DenseMap<const Instruction *, InstCycleState> InstCycleState;
608 
609  // Expression to class mapping.
610  using ExpressionClassMap = DenseMap<const Expression *, CongruenceClass *>;
611  ExpressionClassMap ExpressionToClass;
612 
613  // We have a single expression that represents currently DeadExpressions.
614  // For dead expressions we can prove will stay dead, we mark them with
615  // DFS number zero. However, it's possible in the case of phi nodes
616  // for us to assume/prove all arguments are dead during fixpointing.
617  // We use DeadExpression for that case.
618  DeadExpression *SingletonDeadExpression = nullptr;
619 
620  // Which values have changed as a result of leader changes.
621  SmallPtrSet<Value *, 8> LeaderChanges;
622 
623  // Reachability info.
624  using BlockEdge = BasicBlockEdge;
625  DenseSet<BlockEdge> ReachableEdges;
626  SmallPtrSet<const BasicBlock *, 8> ReachableBlocks;
627 
628  // This is a bitvector because, on larger functions, we may have
629  // thousands of touched instructions at once (entire blocks,
630  // instructions with hundreds of uses, etc). Even with optimization
631  // for when we mark whole blocks as touched, when this was a
632  // SmallPtrSet or DenseSet, for some functions, we spent >20% of all
633  // the time in GVN just managing this list. The bitvector, on the
634  // other hand, efficiently supports test/set/clear of both
635  // individual and ranges, as well as "find next element" This
636  // enables us to use it as a worklist with essentially 0 cost.
637  BitVector TouchedInstructions;
638 
640  mutable DenseMap<const IntrinsicInst *, const Value *> IntrinsicInstPred;
641 
642 #ifndef NDEBUG
643  // Debugging for how many times each block and instruction got processed.
644  DenseMap<const Value *, unsigned> ProcessedCount;
645 #endif
646 
647  // DFS info.
648  // This contains a mapping from Instructions to DFS numbers.
649  // The numbering starts at 1. An instruction with DFS number zero
650  // means that the instruction is dead.
652 
653  // This contains the mapping DFS numbers to instructions.
654  SmallVector<Value *, 32> DFSToInstr;
655 
656  // Deletion info.
657  SmallPtrSet<Instruction *, 8> InstructionsToErase;
658 
659 public:
660  NewGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
661  TargetLibraryInfo *TLI, AliasAnalysis *AA, MemorySSA *MSSA,
662  const DataLayout &DL)
663  : F(F), DT(DT), TLI(TLI), AA(AA), MSSA(MSSA), AC(AC), DL(DL),
664  PredInfo(std::make_unique<PredicateInfo>(F, *DT, *AC)),
665  SQ(DL, TLI, DT, AC, /*CtxI=*/nullptr, /*UseInstrInfo=*/false,
666  /*CanUseUndef=*/false) {}
667 
668  bool runGVN();
669 
670 private:
671  /// Helper struct return a Expression with an optional extra dependency.
672  struct ExprResult {
673  const Expression *Expr;
674  Value *ExtraDep;
675  const PredicateBase *PredDep;
676 
677  ExprResult(const Expression *Expr, Value *ExtraDep = nullptr,
678  const PredicateBase *PredDep = nullptr)
679  : Expr(Expr), ExtraDep(ExtraDep), PredDep(PredDep) {}
680  ExprResult(const ExprResult &) = delete;
681  ExprResult(ExprResult &&Other)
682  : Expr(Other.Expr), ExtraDep(Other.ExtraDep), PredDep(Other.PredDep) {
683  Other.Expr = nullptr;
684  Other.ExtraDep = nullptr;
685  Other.PredDep = nullptr;
686  }
687  ExprResult &operator=(const ExprResult &Other) = delete;
688  ExprResult &operator=(ExprResult &&Other) = delete;
689 
690  ~ExprResult() { assert(!ExtraDep && "unhandled ExtraDep"); }
691 
692  operator bool() const { return Expr; }
693 
694  static ExprResult none() { return {nullptr, nullptr, nullptr}; }
695  static ExprResult some(const Expression *Expr, Value *ExtraDep = nullptr) {
696  return {Expr, ExtraDep, nullptr};
697  }
698  static ExprResult some(const Expression *Expr,
699  const PredicateBase *PredDep) {
700  return {Expr, nullptr, PredDep};
701  }
702  static ExprResult some(const Expression *Expr, Value *ExtraDep,
703  const PredicateBase *PredDep) {
704  return {Expr, ExtraDep, PredDep};
705  }
706  };
707 
708  // Expression handling.
709  ExprResult createExpression(Instruction *) const;
710  const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *,
711  Instruction *) const;
712 
713  // Our canonical form for phi arguments is a pair of incoming value, incoming
714  // basic block.
715  using ValPair = std::pair<Value *, BasicBlock *>;
716 
717  PHIExpression *createPHIExpression(ArrayRef<ValPair>, const Instruction *,
718  BasicBlock *, bool &HasBackEdge,
719  bool &OriginalOpsConstant) const;
720  const DeadExpression *createDeadExpression() const;
721  const VariableExpression *createVariableExpression(Value *) const;
722  const ConstantExpression *createConstantExpression(Constant *) const;
723  const Expression *createVariableOrConstant(Value *V) const;
724  const UnknownExpression *createUnknownExpression(Instruction *) const;
725  const StoreExpression *createStoreExpression(StoreInst *,
726  const MemoryAccess *) const;
727  LoadExpression *createLoadExpression(Type *, Value *, LoadInst *,
728  const MemoryAccess *) const;
729  const CallExpression *createCallExpression(CallInst *,
730  const MemoryAccess *) const;
732  createAggregateValueExpression(Instruction *) const;
733  bool setBasicExpressionInfo(Instruction *, BasicExpression *) const;
734 
735  // Congruence class handling.
736  CongruenceClass *createCongruenceClass(Value *Leader, const Expression *E) {
737  auto *result = new CongruenceClass(NextCongruenceNum++, Leader, E);
738  CongruenceClasses.emplace_back(result);
739  return result;
740  }
741 
742  CongruenceClass *createMemoryClass(MemoryAccess *MA) {
743  auto *CC = createCongruenceClass(nullptr, nullptr);
744  CC->setMemoryLeader(MA);
745  return CC;
746  }
747 
748  CongruenceClass *ensureLeaderOfMemoryClass(MemoryAccess *MA) {
749  auto *CC = getMemoryClass(MA);
750  if (CC->getMemoryLeader() != MA)
751  CC = createMemoryClass(MA);
752  return CC;
753  }
754 
755  CongruenceClass *createSingletonCongruenceClass(Value *Member) {
756  CongruenceClass *CClass = createCongruenceClass(Member, nullptr);
757  CClass->insert(Member);
758  ValueToClass[Member] = CClass;
759  return CClass;
760  }
761 
762  void initializeCongruenceClasses(Function &F);
763  const Expression *makePossiblePHIOfOps(Instruction *,
765  Value *findLeaderForInst(Instruction *ValueOp,
766  SmallPtrSetImpl<Value *> &Visited,
767  MemoryAccess *MemAccess, Instruction *OrigInst,
768  BasicBlock *PredBB);
769  bool OpIsSafeForPHIOfOps(Value *Op, const BasicBlock *PHIBlock,
771  void addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue);
772  void removePhiOfOps(Instruction *I, PHINode *PHITemp);
773 
774  // Value number an Instruction or MemoryPhi.
775  void valueNumberMemoryPhi(MemoryPhi *);
776  void valueNumberInstruction(Instruction *);
777 
778  // Symbolic evaluation.
779  ExprResult checkExprResults(Expression *, Instruction *, Value *) const;
780  ExprResult performSymbolicEvaluation(Value *,
781  SmallPtrSetImpl<Value *> &) const;
782  const Expression *performSymbolicLoadCoercion(Type *, Value *, LoadInst *,
783  Instruction *,
784  MemoryAccess *) const;
785  const Expression *performSymbolicLoadEvaluation(Instruction *) const;
786  const Expression *performSymbolicStoreEvaluation(Instruction *) const;
787  ExprResult performSymbolicCallEvaluation(Instruction *) const;
788  void sortPHIOps(MutableArrayRef<ValPair> Ops) const;
789  const Expression *performSymbolicPHIEvaluation(ArrayRef<ValPair>,
790  Instruction *I,
791  BasicBlock *PHIBlock) const;
792  const Expression *performSymbolicAggrValueEvaluation(Instruction *) const;
793  ExprResult performSymbolicCmpEvaluation(Instruction *) const;
794  ExprResult performSymbolicPredicateInfoEvaluation(IntrinsicInst *) const;
795 
796  // Congruence finding.
797  bool someEquivalentDominates(const Instruction *, const Instruction *) const;
798  Value *lookupOperandLeader(Value *) const;
799  CongruenceClass *getClassForExpression(const Expression *E) const;
800  void performCongruenceFinding(Instruction *, const Expression *);
801  void moveValueToNewCongruenceClass(Instruction *, const Expression *,
802  CongruenceClass *, CongruenceClass *);
803  void moveMemoryToNewCongruenceClass(Instruction *, MemoryAccess *,
804  CongruenceClass *, CongruenceClass *);
805  Value *getNextValueLeader(CongruenceClass *) const;
806  const MemoryAccess *getNextMemoryLeader(CongruenceClass *) const;
807  bool setMemoryClass(const MemoryAccess *From, CongruenceClass *To);
808  CongruenceClass *getMemoryClass(const MemoryAccess *MA) const;
809  const MemoryAccess *lookupMemoryLeader(const MemoryAccess *) const;
810  bool isMemoryAccessTOP(const MemoryAccess *) const;
811 
812  // Ranking
813  unsigned int getRank(const Value *) const;
814  bool shouldSwapOperands(const Value *, const Value *) const;
815  bool shouldSwapOperandsForIntrinsic(const Value *, const Value *,
816  const IntrinsicInst *I) const;
817 
818  // Reachability handling.
819  void updateReachableEdge(BasicBlock *, BasicBlock *);
820  void processOutgoingEdges(Instruction *, BasicBlock *);
821  Value *findConditionEquivalence(Value *) const;
822 
823  // Elimination.
824  struct ValueDFS;
825  void convertClassToDFSOrdered(const CongruenceClass &,
829  void convertClassToLoadsAndStores(const CongruenceClass &,
830  SmallVectorImpl<ValueDFS> &) const;
831 
832  bool eliminateInstructions(Function &);
833  void replaceInstruction(Instruction *, Value *);
834  void markInstructionForDeletion(Instruction *);
835  void deleteInstructionsInBlock(BasicBlock *);
836  Value *findPHIOfOpsLeader(const Expression *, const Instruction *,
837  const BasicBlock *) const;
838 
839  // Various instruction touch utilities
840  template <typename Map, typename KeyType>
841  void touchAndErase(Map &, const KeyType &);
842  void markUsersTouched(Value *);
843  void markMemoryUsersTouched(const MemoryAccess *);
844  void markMemoryDefTouched(const MemoryAccess *);
845  void markPredicateUsersTouched(Instruction *);
846  void markValueLeaderChangeTouched(CongruenceClass *CC);
847  void markMemoryLeaderChangeTouched(CongruenceClass *CC);
848  void markPhiOfOpsChanged(const Expression *E);
849  void addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const;
850  void addAdditionalUsers(Value *To, Value *User) const;
851  void addAdditionalUsers(ExprResult &Res, Instruction *User) const;
852 
853  // Main loop of value numbering
854  void iterateTouchedInstructions();
855 
856  // Utilities.
857  void cleanupTables();
858  std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
859  void updateProcessedCount(const Value *V);
860  void verifyMemoryCongruency() const;
861  void verifyIterationSettled(Function &F);
862  void verifyStoreExpressions() const;
863  bool singleReachablePHIPath(SmallPtrSet<const MemoryAccess *, 8> &,
864  const MemoryAccess *, const MemoryAccess *) const;
865  BasicBlock *getBlockForValue(Value *V) const;
866  void deleteExpression(const Expression *E) const;
867  MemoryUseOrDef *getMemoryAccess(const Instruction *) const;
868  MemoryPhi *getMemoryAccess(const BasicBlock *) const;
869  template <class T, class Range> T *getMinDFSOfRange(const Range &) const;
870 
871  unsigned InstrToDFSNum(const Value *V) const {
872  assert(isa<Instruction>(V) && "This should not be used for MemoryAccesses");
873  return InstrDFS.lookup(V);
874  }
875 
876  unsigned InstrToDFSNum(const MemoryAccess *MA) const {
877  return MemoryToDFSNum(MA);
878  }
879 
880  Value *InstrFromDFSNum(unsigned DFSNum) { return DFSToInstr[DFSNum]; }
881 
882  // Given a MemoryAccess, return the relevant instruction DFS number. Note:
883  // This deliberately takes a value so it can be used with Use's, which will
884  // auto-convert to Value's but not to MemoryAccess's.
885  unsigned MemoryToDFSNum(const Value *MA) const {
886  assert(isa<MemoryAccess>(MA) &&
887  "This should not be used with instructions");
888  return isa<MemoryUseOrDef>(MA)
889  ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst())
890  : InstrDFS.lookup(MA);
891  }
892 
893  bool isCycleFree(const Instruction *) const;
894  bool isBackedge(BasicBlock *From, BasicBlock *To) const;
895 
896  // Debug counter info. When verifying, we have to reset the value numbering
897  // debug counter to the same state it started in to get the same results.
898  int64_t StartingVNCounter = 0;
899 };
900 
901 } // end anonymous namespace
902 
903 template <typename T>
904 static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS) {
905  if (!isa<LoadExpression>(RHS) && !isa<StoreExpression>(RHS))
906  return false;
907  return LHS.MemoryExpression::equals(RHS);
908 }
909 
911  return equalsLoadStoreHelper(*this, Other);
912 }
913 
915  if (!equalsLoadStoreHelper(*this, Other))
916  return false;
917  // Make sure that store vs store includes the value operand.
918  if (const auto *S = dyn_cast<StoreExpression>(&Other))
919  if (getStoredValue() != S->getStoredValue())
920  return false;
921  return true;
922 }
923 
924 // Determine if the edge From->To is a backedge
925 bool NewGVN::isBackedge(BasicBlock *From, BasicBlock *To) const {
926  return From == To ||
927  RPOOrdering.lookup(DT->getNode(From)) >=
928  RPOOrdering.lookup(DT->getNode(To));
929 }
930 
931 #ifndef NDEBUG
932 static std::string getBlockName(const BasicBlock *B) {
934 }
935 #endif
936 
937 // Get a MemoryAccess for an instruction, fake or real.
938 MemoryUseOrDef *NewGVN::getMemoryAccess(const Instruction *I) const {
939  auto *Result = MSSA->getMemoryAccess(I);
940  return Result ? Result : TempToMemory.lookup(I);
941 }
942 
943 // Get a MemoryPhi for a basic block. These are all real.
944 MemoryPhi *NewGVN::getMemoryAccess(const BasicBlock *BB) const {
945  return MSSA->getMemoryAccess(BB);
946 }
947 
948 // Get the basic block from an instruction/memory value.
949 BasicBlock *NewGVN::getBlockForValue(Value *V) const {
950  if (auto *I = dyn_cast<Instruction>(V)) {
951  auto *Parent = I->getParent();
952  if (Parent)
953  return Parent;
954  Parent = TempToBlock.lookup(V);
955  assert(Parent && "Every fake instruction should have a block");
956  return Parent;
957  }
958 
959  auto *MP = dyn_cast<MemoryPhi>(V);
960  assert(MP && "Should have been an instruction or a MemoryPhi");
961  return MP->getBlock();
962 }
963 
964 // Delete a definitely dead expression, so it can be reused by the expression
965 // allocator. Some of these are not in creation functions, so we have to accept
966 // const versions.
967 void NewGVN::deleteExpression(const Expression *E) const {
968  assert(isa<BasicExpression>(E));
969  auto *BE = cast<BasicExpression>(E);
970  const_cast<BasicExpression *>(BE)->deallocateOperands(ArgRecycler);
971  ExpressionAllocator.Deallocate(E);
972 }
973 
974 // If V is a predicateinfo copy, get the thing it is a copy of.
975 static Value *getCopyOf(const Value *V) {
976  if (auto *II = dyn_cast<IntrinsicInst>(V))
977  if (II->getIntrinsicID() == Intrinsic::ssa_copy)
978  return II->getOperand(0);
979  return nullptr;
980 }
981 
982 // Return true if V is really PN, even accounting for predicateinfo copies.
983 static bool isCopyOfPHI(const Value *V, const PHINode *PN) {
984  return V == PN || getCopyOf(V) == PN;
985 }
986 
987 static bool isCopyOfAPHI(const Value *V) {
988  auto *CO = getCopyOf(V);
989  return CO && isa<PHINode>(CO);
990 }
991 
992 // Sort PHI Operands into a canonical order. What we use here is an RPO
993 // order. The BlockInstRange numbers are generated in an RPO walk of the basic
994 // blocks.
995 void NewGVN::sortPHIOps(MutableArrayRef<ValPair> Ops) const {
996  llvm::sort(Ops, [&](const ValPair &P1, const ValPair &P2) {
997  return BlockInstRange.lookup(P1.second).first <
998  BlockInstRange.lookup(P2.second).first;
999  });
1000 }
1001 
1002 // Return true if V is a value that will always be available (IE can
1003 // be placed anywhere) in the function. We don't do globals here
1004 // because they are often worse to put in place.
1005 static bool alwaysAvailable(Value *V) {
1006  return isa<Constant>(V) || isa<Argument>(V);
1007 }
1008 
1009 // Create a PHIExpression from an array of {incoming edge, value} pairs. I is
1010 // the original instruction we are creating a PHIExpression for (but may not be
1011 // a phi node). We require, as an invariant, that all the PHIOperands in the
1012 // same block are sorted the same way. sortPHIOps will sort them into a
1013 // canonical order.
1014 PHIExpression *NewGVN::createPHIExpression(ArrayRef<ValPair> PHIOperands,
1015  const Instruction *I,
1016  BasicBlock *PHIBlock,
1017  bool &HasBackedge,
1018  bool &OriginalOpsConstant) const {
1019  unsigned NumOps = PHIOperands.size();
1020  auto *E = new (ExpressionAllocator) PHIExpression(NumOps, PHIBlock);
1021 
1022  E->allocateOperands(ArgRecycler, ExpressionAllocator);
1023  E->setType(PHIOperands.begin()->first->getType());
1024  E->setOpcode(Instruction::PHI);
1025 
1026  // Filter out unreachable phi operands.
1027  auto Filtered = make_filter_range(PHIOperands, [&](const ValPair &P) {
1028  auto *BB = P.second;
1029  if (auto *PHIOp = dyn_cast<PHINode>(I))
1030  if (isCopyOfPHI(P.first, PHIOp))
1031  return false;
1032  if (!ReachableEdges.count({BB, PHIBlock}))
1033  return false;
1034  // Things in TOPClass are equivalent to everything.
1035  if (ValueToClass.lookup(P.first) == TOPClass)
1036  return false;
1037  OriginalOpsConstant = OriginalOpsConstant && isa<Constant>(P.first);
1038  HasBackedge = HasBackedge || isBackedge(BB, PHIBlock);
1039  return lookupOperandLeader(P.first) != I;
1040  });
1041  std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
1042  [&](const ValPair &P) -> Value * {
1043  return lookupOperandLeader(P.first);
1044  });
1045  return E;
1046 }
1047 
1048 // Set basic expression info (Arguments, type, opcode) for Expression
1049 // E from Instruction I in block B.
1050 bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E) const {
1051  bool AllConstant = true;
1052  if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
1053  E->setType(GEP->getSourceElementType());
1054  else
1055  E->setType(I->getType());
1056  E->setOpcode(I->getOpcode());
1057  E->allocateOperands(ArgRecycler, ExpressionAllocator);
1058 
1059  // Transform the operand array into an operand leader array, and keep track of
1060  // whether all members are constant.
1061  std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) {
1062  auto Operand = lookupOperandLeader(O);
1063  AllConstant = AllConstant && isa<Constant>(Operand);
1064  return Operand;
1065  });
1066 
1067  return AllConstant;
1068 }
1069 
1070 const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
1071  Value *Arg1, Value *Arg2,
1072  Instruction *I) const {
1073  auto *E = new (ExpressionAllocator) BasicExpression(2);
1074  // TODO: we need to remove context instruction after Value Tracking
1075  // can run without context instruction
1076  const SimplifyQuery Q = SQ.getWithInstruction(I);
1077 
1078  E->setType(T);
1079  E->setOpcode(Opcode);
1080  E->allocateOperands(ArgRecycler, ExpressionAllocator);
1081  if (Instruction::isCommutative(Opcode)) {
1082  // Ensure that commutative instructions that only differ by a permutation
1083  // of their operands get the same value number by sorting the operand value
1084  // numbers. Since all commutative instructions have two operands it is more
1085  // efficient to sort by hand rather than using, say, std::sort.
1086  if (shouldSwapOperands(Arg1, Arg2))
1087  std::swap(Arg1, Arg2);
1088  }
1089  E->op_push_back(lookupOperandLeader(Arg1));
1090  E->op_push_back(lookupOperandLeader(Arg2));
1091 
1092  Value *V = simplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), Q);
1093  if (auto Simplified = checkExprResults(E, I, V)) {
1094  addAdditionalUsers(Simplified, I);
1095  return Simplified.Expr;
1096  }
1097  return E;
1098 }
1099 
1100 // Take a Value returned by simplification of Expression E/Instruction
1101 // I, and see if it resulted in a simpler expression. If so, return
1102 // that expression.
1103 NewGVN::ExprResult NewGVN::checkExprResults(Expression *E, Instruction *I,
1104  Value *V) const {
1105  if (!V)
1106  return ExprResult::none();
1107 
1108  if (auto *C = dyn_cast<Constant>(V)) {
1109  if (I)
1110  LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
1111  << " constant " << *C << "\n");
1112  NumGVNOpsSimplified++;
1113  assert(isa<BasicExpression>(E) &&
1114  "We should always have had a basic expression here");
1115  deleteExpression(E);
1116  return ExprResult::some(createConstantExpression(C));
1117  } else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
1118  if (I)
1119  LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
1120  << " variable " << *V << "\n");
1121  deleteExpression(E);
1122  return ExprResult::some(createVariableExpression(V));
1123  }
1124 
1125  CongruenceClass *CC = ValueToClass.lookup(V);
1126  if (CC) {
1127  if (CC->getLeader() && CC->getLeader() != I) {
1128  return ExprResult::some(createVariableOrConstant(CC->getLeader()), V);
1129  }
1130  if (CC->getDefiningExpr()) {
1131  if (I)
1132  LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
1133  << " expression " << *CC->getDefiningExpr() << "\n");
1134  NumGVNOpsSimplified++;
1135  deleteExpression(E);
1136  return ExprResult::some(CC->getDefiningExpr(), V);
1137  }
1138  }
1139 
1140  return ExprResult::none();
1141 }
1142 
1143 // Create a value expression from the instruction I, replacing operands with
1144 // their leaders.
1145 
1146 NewGVN::ExprResult NewGVN::createExpression(Instruction *I) const {
1147  auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands());
1148  // TODO: we need to remove context instruction after Value Tracking
1149  // can run without context instruction
1150  const SimplifyQuery Q = SQ.getWithInstruction(I);
1151 
1152  bool AllConstant = setBasicExpressionInfo(I, E);
1153 
1154  if (I->isCommutative()) {
1155  // Ensure that commutative instructions that only differ by a permutation
1156  // of their operands get the same value number by sorting the operand value
1157  // numbers. Since all commutative instructions have two operands it is more
1158  // efficient to sort by hand rather than using, say, std::sort.
1159  assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
1160  if (shouldSwapOperands(E->getOperand(0), E->getOperand(1)))
1161  E->swapOperands(0, 1);
1162  }
1163  // Perform simplification.
1164  if (auto *CI = dyn_cast<CmpInst>(I)) {
1165  // Sort the operand value numbers so x<y and y>x get the same value
1166  // number.
1167  CmpInst::Predicate Predicate = CI->getPredicate();
1168  if (shouldSwapOperands(E->getOperand(0), E->getOperand(1))) {
1169  E->swapOperands(0, 1);
1171  }
1172  E->setOpcode((CI->getOpcode() << 8) | Predicate);
1173  // TODO: 25% of our time is spent in simplifyCmpInst with pointer operands
1174  assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
1175  "Wrong types on cmp instruction");
1176  assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
1177  E->getOperand(1)->getType() == I->getOperand(1)->getType()));
1178  Value *V =
1179  simplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), Q);
1180  if (auto Simplified = checkExprResults(E, I, V))
1181  return Simplified;
1182  } else if (isa<SelectInst>(I)) {
1183  if (isa<Constant>(E->getOperand(0)) ||
1184  E->getOperand(1) == E->getOperand(2)) {
1185  assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
1186  E->getOperand(2)->getType() == I->getOperand(2)->getType());
1187  Value *V = simplifySelectInst(E->getOperand(0), E->getOperand(1),
1188  E->getOperand(2), Q);
1189  if (auto Simplified = checkExprResults(E, I, V))
1190  return Simplified;
1191  }
1192  } else if (I->isBinaryOp()) {
1193  Value *V =
1194  simplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), Q);
1195  if (auto Simplified = checkExprResults(E, I, V))
1196  return Simplified;
1197  } else if (auto *CI = dyn_cast<CastInst>(I)) {
1198  Value *V =
1199  simplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), Q);
1200  if (auto Simplified = checkExprResults(E, I, V))
1201  return Simplified;
1202  } else if (auto *GEPI = dyn_cast<GetElementPtrInst>(I)) {
1203  Value *V =
1204  simplifyGEPInst(GEPI->getSourceElementType(), *E->op_begin(),
1205  makeArrayRef(std::next(E->op_begin()), E->op_end()),
1206  GEPI->isInBounds(), Q);
1207  if (auto Simplified = checkExprResults(E, I, V))
1208  return Simplified;
1209  } else if (AllConstant) {
1210  // We don't bother trying to simplify unless all of the operands
1211  // were constant.
1212  // TODO: There are a lot of Simplify*'s we could call here, if we
1213  // wanted to. The original motivating case for this code was a
1214  // zext i1 false to i8, which we don't have an interface to
1215  // simplify (IE there is no SimplifyZExt).
1216 
1218  for (Value *Arg : E->operands())
1219  C.emplace_back(cast<Constant>(Arg));
1220 
1221  if (Value *V = ConstantFoldInstOperands(I, C, DL, TLI))
1222  if (auto Simplified = checkExprResults(E, I, V))
1223  return Simplified;
1224  }
1225  return ExprResult::some(E);
1226 }
1227 
1229 NewGVN::createAggregateValueExpression(Instruction *I) const {
1230  if (auto *II = dyn_cast<InsertValueInst>(I)) {
1231  auto *E = new (ExpressionAllocator)
1232  AggregateValueExpression(I->getNumOperands(), II->getNumIndices());
1233  setBasicExpressionInfo(I, E);
1234  E->allocateIntOperands(ExpressionAllocator);
1235  std::copy(II->idx_begin(), II->idx_end(), int_op_inserter(E));
1236  return E;
1237  } else if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
1238  auto *E = new (ExpressionAllocator)
1239  AggregateValueExpression(I->getNumOperands(), EI->getNumIndices());
1240  setBasicExpressionInfo(EI, E);
1241  E->allocateIntOperands(ExpressionAllocator);
1242  std::copy(EI->idx_begin(), EI->idx_end(), int_op_inserter(E));
1243  return E;
1244  }
1245  llvm_unreachable("Unhandled type of aggregate value operation");
1246 }
1247 
1248 const DeadExpression *NewGVN::createDeadExpression() const {
1249  // DeadExpression has no arguments and all DeadExpression's are the same,
1250  // so we only need one of them.
1251  return SingletonDeadExpression;
1252 }
1253 
1254 const VariableExpression *NewGVN::createVariableExpression(Value *V) const {
1255  auto *E = new (ExpressionAllocator) VariableExpression(V);
1256  E->setOpcode(V->getValueID());
1257  return E;
1258 }
1259 
1260 const Expression *NewGVN::createVariableOrConstant(Value *V) const {
1261  if (auto *C = dyn_cast<Constant>(V))
1262  return createConstantExpression(C);
1263  return createVariableExpression(V);
1264 }
1265 
1266 const ConstantExpression *NewGVN::createConstantExpression(Constant *C) const {
1267  auto *E = new (ExpressionAllocator) ConstantExpression(C);
1268  E->setOpcode(C->getValueID());
1269  return E;
1270 }
1271 
1272 const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) const {
1273  auto *E = new (ExpressionAllocator) UnknownExpression(I);
1274  E->setOpcode(I->getOpcode());
1275  return E;
1276 }
1277 
1278 const CallExpression *
1279 NewGVN::createCallExpression(CallInst *CI, const MemoryAccess *MA) const {
1280  // FIXME: Add operand bundles for calls.
1281  // FIXME: Allow commutative matching for intrinsics.
1282  auto *E =
1283  new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, MA);
1284  setBasicExpressionInfo(CI, E);
1285  return E;
1286 }
1287 
1288 // Return true if some equivalent of instruction Inst dominates instruction U.
1289 bool NewGVN::someEquivalentDominates(const Instruction *Inst,
1290  const Instruction *U) const {
1291  auto *CC = ValueToClass.lookup(Inst);
1292  // This must be an instruction because we are only called from phi nodes
1293  // in the case that the value it needs to check against is an instruction.
1294 
1295  // The most likely candidates for dominance are the leader and the next leader.
1296  // The leader or nextleader will dominate in all cases where there is an
1297  // equivalent that is higher up in the dom tree.
1298  // We can't *only* check them, however, because the
1299  // dominator tree could have an infinite number of non-dominating siblings
1300  // with instructions that are in the right congruence class.
1301  // A
1302  // B C D E F G
1303  // |
1304  // H
1305  // Instruction U could be in H, with equivalents in every other sibling.
1306  // Depending on the rpo order picked, the leader could be the equivalent in
1307  // any of these siblings.
1308  if (!CC)
1309  return false;
1310  if (alwaysAvailable(CC->getLeader()))
1311  return true;
1312  if (DT->dominates(cast<Instruction>(CC->getLeader()), U))
1313  return true;
1314  if (CC->getNextLeader().first &&
1315  DT->dominates(cast<Instruction>(CC->getNextLeader().first), U))
1316  return true;
1317  return llvm::any_of(*CC, [&](const Value *Member) {
1318  return Member != CC->getLeader() &&
1319  DT->dominates(cast<Instruction>(Member), U);
1320  });
1321 }
1322 
1323 // See if we have a congruence class and leader for this operand, and if so,
1324 // return it. Otherwise, return the operand itself.
1325 Value *NewGVN::lookupOperandLeader(Value *V) const {
1326  CongruenceClass *CC = ValueToClass.lookup(V);
1327  if (CC) {
1328  // Everything in TOP is represented by poison, as it can be any value.
1329  // We do have to make sure we get the type right though, so we can't set the
1330  // RepLeader to poison.
1331  if (CC == TOPClass)
1332  return PoisonValue::get(V->getType());
1333  return CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
1334  }
1335 
1336  return V;
1337 }
1338 
1339 const MemoryAccess *NewGVN::lookupMemoryLeader(const MemoryAccess *MA) const {
1340  auto *CC = getMemoryClass(MA);
1341  assert(CC->getMemoryLeader() &&
1342  "Every MemoryAccess should be mapped to a congruence class with a "
1343  "representative memory access");
1344  return CC->getMemoryLeader();
1345 }
1346 
1347 // Return true if the MemoryAccess is really equivalent to everything. This is
1348 // equivalent to the lattice value "TOP" in most lattices. This is the initial
1349 // state of all MemoryAccesses.
1350 bool NewGVN::isMemoryAccessTOP(const MemoryAccess *MA) const {
1351  return getMemoryClass(MA) == TOPClass;
1352 }
1353 
1354 LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp,
1355  LoadInst *LI,
1356  const MemoryAccess *MA) const {
1357  auto *E =
1358  new (ExpressionAllocator) LoadExpression(1, LI, lookupMemoryLeader(MA));
1359  E->allocateOperands(ArgRecycler, ExpressionAllocator);
1360  E->setType(LoadType);
1361 
1362  // Give store and loads same opcode so they value number together.
1363  E->setOpcode(0);
1364  E->op_push_back(PointerOp);
1365 
1366  // TODO: Value number heap versions. We may be able to discover
1367  // things alias analysis can't on it's own (IE that a store and a
1368  // load have the same value, and thus, it isn't clobbering the load).
1369  return E;
1370 }
1371 
1372 const StoreExpression *
1373 NewGVN::createStoreExpression(StoreInst *SI, const MemoryAccess *MA) const {
1374  auto *StoredValueLeader = lookupOperandLeader(SI->getValueOperand());
1375  auto *E = new (ExpressionAllocator)
1376  StoreExpression(SI->getNumOperands(), SI, StoredValueLeader, MA);
1377  E->allocateOperands(ArgRecycler, ExpressionAllocator);
1378  E->setType(SI->getValueOperand()->getType());
1379 
1380  // Give store and loads same opcode so they value number together.
1381  E->setOpcode(0);
1382  E->op_push_back(lookupOperandLeader(SI->getPointerOperand()));
1383 
1384  // TODO: Value number heap versions. We may be able to discover
1385  // things alias analysis can't on it's own (IE that a store and a
1386  // load have the same value, and thus, it isn't clobbering the load).
1387  return E;
1388 }
1389 
1390 const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I) const {
1391  // Unlike loads, we never try to eliminate stores, so we do not check if they
1392  // are simple and avoid value numbering them.
1393  auto *SI = cast<StoreInst>(I);
1394  auto *StoreAccess = getMemoryAccess(SI);
1395  // Get the expression, if any, for the RHS of the MemoryDef.
1396  const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess();
1398  StoreRHS = MSSAWalker->getClobberingMemoryAccess(StoreAccess);
1399  // If we bypassed the use-def chains, make sure we add a use.
1400  StoreRHS = lookupMemoryLeader(StoreRHS);
1401  if (StoreRHS != StoreAccess->getDefiningAccess())
1402  addMemoryUsers(StoreRHS, StoreAccess);
1403  // If we are defined by ourselves, use the live on entry def.
1404  if (StoreRHS == StoreAccess)
1405  StoreRHS = MSSA->getLiveOnEntryDef();
1406 
1407  if (SI->isSimple()) {
1408  // See if we are defined by a previous store expression, it already has a
1409  // value, and it's the same value as our current store. FIXME: Right now, we
1410  // only do this for simple stores, we should expand to cover memcpys, etc.
1411  const auto *LastStore = createStoreExpression(SI, StoreRHS);
1412  const auto *LastCC = ExpressionToClass.lookup(LastStore);
1413  // We really want to check whether the expression we matched was a store. No
1414  // easy way to do that. However, we can check that the class we found has a
1415  // store, which, assuming the value numbering state is not corrupt, is
1416  // sufficient, because we must also be equivalent to that store's expression
1417  // for it to be in the same class as the load.
1418  if (LastCC && LastCC->getStoredValue() == LastStore->getStoredValue())
1419  return LastStore;
1420  // Also check if our value operand is defined by a load of the same memory
1421  // location, and the memory state is the same as it was then (otherwise, it
1422  // could have been overwritten later. See test32 in
1423  // transforms/DeadStoreElimination/simple.ll).
1424  if (auto *LI = dyn_cast<LoadInst>(LastStore->getStoredValue()))
1425  if ((lookupOperandLeader(LI->getPointerOperand()) ==
1426  LastStore->getOperand(0)) &&
1427  (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) ==
1428  StoreRHS))
1429  return LastStore;
1430  deleteExpression(LastStore);
1431  }
1432 
1433  // If the store is not equivalent to anything, value number it as a store that
1434  // produces a unique memory state (instead of using it's MemoryUse, we use
1435  // it's MemoryDef).
1436  return createStoreExpression(SI, StoreAccess);
1437 }
1438 
1439 // See if we can extract the value of a loaded pointer from a load, a store, or
1440 // a memory instruction.
1441 const Expression *
1442 NewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr,
1443  LoadInst *LI, Instruction *DepInst,
1444  MemoryAccess *DefiningAccess) const {
1445  assert((!LI || LI->isSimple()) && "Not a simple load");
1446  if (auto *DepSI = dyn_cast<StoreInst>(DepInst)) {
1447  // Can't forward from non-atomic to atomic without violating memory model.
1448  // Also don't need to coerce if they are the same type, we will just
1449  // propagate.
1450  if (LI->isAtomic() > DepSI->isAtomic() ||
1451  LoadType == DepSI->getValueOperand()->getType())
1452  return nullptr;
1453  int Offset = analyzeLoadFromClobberingStore(LoadType, LoadPtr, DepSI, DL);
1454  if (Offset >= 0) {
1455  if (auto *C = dyn_cast<Constant>(
1456  lookupOperandLeader(DepSI->getValueOperand()))) {
1457  if (Constant *Res =
1458  getConstantStoreValueForLoad(C, Offset, LoadType, DL)) {
1459  LLVM_DEBUG(dbgs() << "Coercing load from store " << *DepSI
1460  << " to constant " << *Res << "\n");
1461  return createConstantExpression(Res);
1462  }
1463  }
1464  }
1465  } else if (auto *DepLI = dyn_cast<LoadInst>(DepInst)) {
1466  // Can't forward from non-atomic to atomic without violating memory model.
1467  if (LI->isAtomic() > DepLI->isAtomic())
1468  return nullptr;
1469  int Offset = analyzeLoadFromClobberingLoad(LoadType, LoadPtr, DepLI, DL);
1470  if (Offset >= 0) {
1471  // We can coerce a constant load into a load.
1472  if (auto *C = dyn_cast<Constant>(lookupOperandLeader(DepLI)))
1473  if (auto *PossibleConstant =
1474  getConstantLoadValueForLoad(C, Offset, LoadType, DL)) {
1475  LLVM_DEBUG(dbgs() << "Coercing load from load " << *LI
1476  << " to constant " << *PossibleConstant << "\n");
1477  return createConstantExpression(PossibleConstant);
1478  }
1479  }
1480  } else if (auto *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1481  int Offset = analyzeLoadFromClobberingMemInst(LoadType, LoadPtr, DepMI, DL);
1482  if (Offset >= 0) {
1483  if (auto *PossibleConstant =
1484  getConstantMemInstValueForLoad(DepMI, Offset, LoadType, DL)) {
1485  LLVM_DEBUG(dbgs() << "Coercing load from meminst " << *DepMI
1486  << " to constant " << *PossibleConstant << "\n");
1487  return createConstantExpression(PossibleConstant);
1488  }
1489  }
1490  }
1491 
1492  // All of the below are only true if the loaded pointer is produced
1493  // by the dependent instruction.
1494  if (LoadPtr != lookupOperandLeader(DepInst) &&
1495  !AA->isMustAlias(LoadPtr, DepInst))
1496  return nullptr;
1497  // If this load really doesn't depend on anything, then we must be loading an
1498  // undef value. This can happen when loading for a fresh allocation with no
1499  // intervening stores, for example. Note that this is only true in the case
1500  // that the result of the allocation is pointer equal to the load ptr.
1501  if (isa<AllocaInst>(DepInst)) {
1502  return createConstantExpression(UndefValue::get(LoadType));
1503  }
1504  // If this load occurs either right after a lifetime begin,
1505  // then the loaded value is undefined.
1506  else if (auto *II = dyn_cast<IntrinsicInst>(DepInst)) {
1507  if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1508  return createConstantExpression(UndefValue::get(LoadType));
1509  } else if (auto *InitVal =
1510  getInitialValueOfAllocation(DepInst, TLI, LoadType))
1511  return createConstantExpression(InitVal);
1512 
1513  return nullptr;
1514 }
1515 
1516 const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) const {
1517  auto *LI = cast<LoadInst>(I);
1518 
1519  // We can eliminate in favor of non-simple loads, but we won't be able to
1520  // eliminate the loads themselves.
1521  if (!LI->isSimple())
1522  return nullptr;
1523 
1524  Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand());
1525  // Load of undef is UB.
1526  if (isa<UndefValue>(LoadAddressLeader))
1527  return createConstantExpression(PoisonValue::get(LI->getType()));
1528  MemoryAccess *OriginalAccess = getMemoryAccess(I);
1529  MemoryAccess *DefiningAccess =
1530  MSSAWalker->getClobberingMemoryAccess(OriginalAccess);
1531 
1532  if (!MSSA->isLiveOnEntryDef(DefiningAccess)) {
1533  if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
1534  Instruction *DefiningInst = MD->getMemoryInst();
1535  // If the defining instruction is not reachable, replace with poison.
1536  if (!ReachableBlocks.count(DefiningInst->getParent()))
1537  return createConstantExpression(PoisonValue::get(LI->getType()));
1538  // This will handle stores and memory insts. We only do if it the
1539  // defining access has a different type, or it is a pointer produced by
1540  // certain memory operations that cause the memory to have a fixed value
1541  // (IE things like calloc).
1542  if (const auto *CoercionResult =
1543  performSymbolicLoadCoercion(LI->getType(), LoadAddressLeader, LI,
1544  DefiningInst, DefiningAccess))
1545  return CoercionResult;
1546  }
1547  }
1548 
1549  const auto *LE = createLoadExpression(LI->getType(), LoadAddressLeader, LI,
1550  DefiningAccess);
1551  // If our MemoryLeader is not our defining access, add a use to the
1552  // MemoryLeader, so that we get reprocessed when it changes.
1553  if (LE->getMemoryLeader() != DefiningAccess)
1554  addMemoryUsers(LE->getMemoryLeader(), OriginalAccess);
1555  return LE;
1556 }
1557 
1558 NewGVN::ExprResult
1559 NewGVN::performSymbolicPredicateInfoEvaluation(IntrinsicInst *I) const {
1560  auto *PI = PredInfo->getPredicateInfoFor(I);
1561  if (!PI)
1562  return ExprResult::none();
1563 
1564  LLVM_DEBUG(dbgs() << "Found predicate info from instruction !\n");
1565 
1566  const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
1567  if (!Constraint)
1568  return ExprResult::none();
1569 
1570  CmpInst::Predicate Predicate = Constraint->Predicate;
1571  Value *CmpOp0 = I->getOperand(0);
1572  Value *CmpOp1 = Constraint->OtherOp;
1573 
1574  Value *FirstOp = lookupOperandLeader(CmpOp0);
1575  Value *SecondOp = lookupOperandLeader(CmpOp1);
1576  Value *AdditionallyUsedValue = CmpOp0;
1577 
1578  // Sort the ops.
1579  if (shouldSwapOperandsForIntrinsic(FirstOp, SecondOp, I)) {
1580  std::swap(FirstOp, SecondOp);
1582  AdditionallyUsedValue = CmpOp1;
1583  }
1584 
1585  if (Predicate == CmpInst::ICMP_EQ)
1586  return ExprResult::some(createVariableOrConstant(FirstOp),
1587  AdditionallyUsedValue, PI);
1588 
1589  // Handle the special case of floating point.
1590  if (Predicate == CmpInst::FCMP_OEQ && isa<ConstantFP>(FirstOp) &&
1591  !cast<ConstantFP>(FirstOp)->isZero())
1592  return ExprResult::some(createConstantExpression(cast<Constant>(FirstOp)),
1593  AdditionallyUsedValue, PI);
1594 
1595  return ExprResult::none();
1596 }
1597 
1598 // Evaluate read only and pure calls, and create an expression result.
1599 NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(Instruction *I) const {
1600  auto *CI = cast<CallInst>(I);
1601  if (auto *II = dyn_cast<IntrinsicInst>(I)) {
1602  // Intrinsics with the returned attribute are copies of arguments.
1603  if (auto *ReturnedValue = II->getReturnedArgOperand()) {
1604  if (II->getIntrinsicID() == Intrinsic::ssa_copy)
1605  if (auto Res = performSymbolicPredicateInfoEvaluation(II))
1606  return Res;
1607  return ExprResult::some(createVariableOrConstant(ReturnedValue));
1608  }
1609  }
1610 
1611  // FIXME: Currently the calls which may access the thread id may
1612  // be considered as not accessing the memory. But this is
1613  // problematic for coroutines, since coroutines may resume in a
1614  // different thread. So we disable the optimization here for the
1615  // correctness. However, it may block many other correct
1616  // optimizations. Revert this one when we detect the memory
1617  // accessing kind more precisely.
1618  if (CI->getFunction()->isPresplitCoroutine())
1619  return ExprResult::none();
1620 
1621  if (AA->doesNotAccessMemory(CI)) {
1622  return ExprResult::some(
1623  createCallExpression(CI, TOPClass->getMemoryLeader()));
1624  } else if (AA->onlyReadsMemory(CI)) {
1625  if (auto *MA = MSSA->getMemoryAccess(CI)) {
1626  auto *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(MA);
1627  return ExprResult::some(createCallExpression(CI, DefiningAccess));
1628  } else // MSSA determined that CI does not access memory.
1629  return ExprResult::some(
1630  createCallExpression(CI, TOPClass->getMemoryLeader()));
1631  }
1632  return ExprResult::none();
1633 }
1634 
1635 // Retrieve the memory class for a given MemoryAccess.
1636 CongruenceClass *NewGVN::getMemoryClass(const MemoryAccess *MA) const {
1637  auto *Result = MemoryAccessToClass.lookup(MA);
1638  assert(Result && "Should have found memory class");
1639  return Result;
1640 }
1641 
1642 // Update the MemoryAccess equivalence table to say that From is equal to To,
1643 // and return true if this is different from what already existed in the table.
1644 bool NewGVN::setMemoryClass(const MemoryAccess *From,
1645  CongruenceClass *NewClass) {
1646  assert(NewClass &&
1647  "Every MemoryAccess should be getting mapped to a non-null class");
1648  LLVM_DEBUG(dbgs() << "Setting " << *From);
1649  LLVM_DEBUG(dbgs() << " equivalent to congruence class ");
1650  LLVM_DEBUG(dbgs() << NewClass->getID()
1651  << " with current MemoryAccess leader ");
1652  LLVM_DEBUG(dbgs() << *NewClass->getMemoryLeader() << "\n");
1653 
1654  auto LookupResult = MemoryAccessToClass.find(From);
1655  bool Changed = false;
1656  // If it's already in the table, see if the value changed.
1657  if (LookupResult != MemoryAccessToClass.end()) {
1658  auto *OldClass = LookupResult->second;
1659  if (OldClass != NewClass) {
1660  // If this is a phi, we have to handle memory member updates.
1661  if (auto *MP = dyn_cast<MemoryPhi>(From)) {
1662  OldClass->memory_erase(MP);
1663  NewClass->memory_insert(MP);
1664  // This may have killed the class if it had no non-memory members
1665  if (OldClass->getMemoryLeader() == From) {
1666  if (OldClass->definesNoMemory()) {
1667  OldClass->setMemoryLeader(nullptr);
1668  } else {
1669  OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
1670  LLVM_DEBUG(dbgs() << "Memory class leader change for class "
1671  << OldClass->getID() << " to "
1672  << *OldClass->getMemoryLeader()
1673  << " due to removal of a memory member " << *From
1674  << "\n");
1675  markMemoryLeaderChangeTouched(OldClass);
1676  }
1677  }
1678  }
1679  // It wasn't equivalent before, and now it is.
1680  LookupResult->second = NewClass;
1681  Changed = true;
1682  }
1683  }
1684 
1685  return Changed;
1686 }
1687 
1688 // Determine if a instruction is cycle-free. That means the values in the
1689 // instruction don't depend on any expressions that can change value as a result
1690 // of the instruction. For example, a non-cycle free instruction would be v =
1691 // phi(0, v+1).
1692 bool NewGVN::isCycleFree(const Instruction *I) const {
1693  // In order to compute cycle-freeness, we do SCC finding on the instruction,
1694  // and see what kind of SCC it ends up in. If it is a singleton, it is
1695  // cycle-free. If it is not in a singleton, it is only cycle free if the
1696  // other members are all phi nodes (as they do not compute anything, they are
1697  // copies).
1698  auto ICS = InstCycleState.lookup(I);
1699  if (ICS == ICS_Unknown) {
1700  SCCFinder.Start(I);
1701  auto &SCC = SCCFinder.getComponentFor(I);
1702  // It's cycle free if it's size 1 or the SCC is *only* phi nodes.
1703  if (SCC.size() == 1)
1704  InstCycleState.insert({I, ICS_CycleFree});
1705  else {
1706  bool AllPhis = llvm::all_of(SCC, [](const Value *V) {
1707  return isa<PHINode>(V) || isCopyOfAPHI(V);
1708  });
1709  ICS = AllPhis ? ICS_CycleFree : ICS_Cycle;
1710  for (const auto *Member : SCC)
1711  if (auto *MemberPhi = dyn_cast<PHINode>(Member))
1712  InstCycleState.insert({MemberPhi, ICS});
1713  }
1714  }
1715  if (ICS == ICS_Cycle)
1716  return false;
1717  return true;
1718 }
1719 
1720 // Evaluate PHI nodes symbolically and create an expression result.
1721 const Expression *
1722 NewGVN::performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps,
1723  Instruction *I,
1724  BasicBlock *PHIBlock) const {
1725  // True if one of the incoming phi edges is a backedge.
1726  bool HasBackedge = false;
1727  // All constant tracks the state of whether all the *original* phi operands
1728  // This is really shorthand for "this phi cannot cycle due to forward
1729  // change in value of the phi is guaranteed not to later change the value of
1730  // the phi. IE it can't be v = phi(undef, v+1)
1731  bool OriginalOpsConstant = true;
1732  auto *E = cast<PHIExpression>(createPHIExpression(
1733  PHIOps, I, PHIBlock, HasBackedge, OriginalOpsConstant));
1734  // We match the semantics of SimplifyPhiNode from InstructionSimplify here.
1735  // See if all arguments are the same.
1736  // We track if any were undef because they need special handling.
1737  bool HasUndef = false, HasPoison = false;
1738  auto Filtered = make_filter_range(E->operands(), [&](Value *Arg) {
1739  if (isa<PoisonValue>(Arg)) {
1740  HasPoison = true;
1741  return false;
1742  }
1743  if (isa<UndefValue>(Arg)) {
1744  HasUndef = true;
1745  return false;
1746  }
1747  return true;
1748  });
1749  // If we are left with no operands, it's dead.
1750  if (Filtered.empty()) {
1751  // If it has undef or poison at this point, it means there are no-non-undef
1752  // arguments, and thus, the value of the phi node must be undef.
1753  if (HasUndef) {
1754  LLVM_DEBUG(
1755  dbgs() << "PHI Node " << *I
1756  << " has no non-undef arguments, valuing it as undef\n");
1757  return createConstantExpression(UndefValue::get(I->getType()));
1758  }
1759  if (HasPoison) {
1760  LLVM_DEBUG(
1761  dbgs() << "PHI Node " << *I
1762  << " has no non-poison arguments, valuing it as poison\n");
1763  return createConstantExpression(PoisonValue::get(I->getType()));
1764  }
1765 
1766  LLVM_DEBUG(dbgs() << "No arguments of PHI node " << *I << " are live\n");
1767  deleteExpression(E);
1768  return createDeadExpression();
1769  }
1770  Value *AllSameValue = *(Filtered.begin());
1771  ++Filtered.begin();
1772  // Can't use std::equal here, sadly, because filter.begin moves.
1773  if (llvm::all_of(Filtered, [&](Value *Arg) { return Arg == AllSameValue; })) {
1774  // Can't fold phi(undef, X) -> X unless X can't be poison (thus X is undef
1775  // in the worst case).
1776  if (HasUndef && !isGuaranteedNotToBePoison(AllSameValue, AC, nullptr, DT))
1777  return E;
1778 
1779  // In LLVM's non-standard representation of phi nodes, it's possible to have
1780  // phi nodes with cycles (IE dependent on other phis that are .... dependent
1781  // on the original phi node), especially in weird CFG's where some arguments
1782  // are unreachable, or uninitialized along certain paths. This can cause
1783  // infinite loops during evaluation. We work around this by not trying to
1784  // really evaluate them independently, but instead using a variable
1785  // expression to say if one is equivalent to the other.
1786  // We also special case undef/poison, so that if we have an undef, we can't
1787  // use the common value unless it dominates the phi block.
1788  if (HasPoison || HasUndef) {
1789  // If we have undef and at least one other value, this is really a
1790  // multivalued phi, and we need to know if it's cycle free in order to
1791  // evaluate whether we can ignore the undef. The other parts of this are
1792  // just shortcuts. If there is no backedge, or all operands are
1793  // constants, it also must be cycle free.
1794  if (HasBackedge && !OriginalOpsConstant &&
1795  !isa<UndefValue>(AllSameValue) && !isCycleFree(I))
1796  return E;
1797 
1798  // Only have to check for instructions
1799  if (auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
1800  if (!someEquivalentDominates(AllSameInst, I))
1801  return E;
1802  }
1803  // Can't simplify to something that comes later in the iteration.
1804  // Otherwise, when and if it changes congruence class, we will never catch
1805  // up. We will always be a class behind it.
1806  if (isa<Instruction>(AllSameValue) &&
1807  InstrToDFSNum(AllSameValue) > InstrToDFSNum(I))
1808  return E;
1809  NumGVNPhisAllSame++;
1810  LLVM_DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue
1811  << "\n");
1812  deleteExpression(E);
1813  return createVariableOrConstant(AllSameValue);
1814  }
1815  return E;
1816 }
1817 
1818 const Expression *
1819 NewGVN::performSymbolicAggrValueEvaluation(Instruction *I) const {
1820  if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
1821  auto *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
1822  if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0)
1823  // EI is an extract from one of our with.overflow intrinsics. Synthesize
1824  // a semantically equivalent expression instead of an extract value
1825  // expression.
1826  return createBinaryExpression(WO->getBinaryOp(), EI->getType(),
1827  WO->getLHS(), WO->getRHS(), I);
1828  }
1829 
1830  return createAggregateValueExpression(I);
1831 }
1832 
1833 NewGVN::ExprResult NewGVN::performSymbolicCmpEvaluation(Instruction *I) const {
1834  assert(isa<CmpInst>(I) && "Expected a cmp instruction.");
1835 
1836  auto *CI = cast<CmpInst>(I);
1837  // See if our operands are equal to those of a previous predicate, and if so,
1838  // if it implies true or false.
1839  auto Op0 = lookupOperandLeader(CI->getOperand(0));
1840  auto Op1 = lookupOperandLeader(CI->getOperand(1));
1841  auto OurPredicate = CI->getPredicate();
1842  if (shouldSwapOperands(Op0, Op1)) {
1843  std::swap(Op0, Op1);
1844  OurPredicate = CI->getSwappedPredicate();
1845  }
1846 
1847  // Avoid processing the same info twice.
1848  const PredicateBase *LastPredInfo = nullptr;
1849  // See if we know something about the comparison itself, like it is the target
1850  // of an assume.
1851  auto *CmpPI = PredInfo->getPredicateInfoFor(I);
1852  if (isa_and_nonnull<PredicateAssume>(CmpPI))
1853  return ExprResult::some(
1854  createConstantExpression(ConstantInt::getTrue(CI->getType())));
1855 
1856  if (Op0 == Op1) {
1857  // This condition does not depend on predicates, no need to add users
1858  if (CI->isTrueWhenEqual())
1859  return ExprResult::some(
1860  createConstantExpression(ConstantInt::getTrue(CI->getType())));
1861  else if (CI->isFalseWhenEqual())
1862  return ExprResult::some(
1863  createConstantExpression(ConstantInt::getFalse(CI->getType())));
1864  }
1865 
1866  // NOTE: Because we are comparing both operands here and below, and using
1867  // previous comparisons, we rely on fact that predicateinfo knows to mark
1868  // comparisons that use renamed operands as users of the earlier comparisons.
1869  // It is *not* enough to just mark predicateinfo renamed operands as users of
1870  // the earlier comparisons, because the *other* operand may have changed in a
1871  // previous iteration.
1872  // Example:
1873  // icmp slt %a, %b
1874  // %b.0 = ssa.copy(%b)
1875  // false branch:
1876  // icmp slt %c, %b.0
1877 
1878  // %c and %a may start out equal, and thus, the code below will say the second
1879  // %icmp is false. c may become equal to something else, and in that case the
1880  // %second icmp *must* be reexamined, but would not if only the renamed
1881  // %operands are considered users of the icmp.
1882 
1883  // *Currently* we only check one level of comparisons back, and only mark one
1884  // level back as touched when changes happen. If you modify this code to look
1885  // back farther through comparisons, you *must* mark the appropriate
1886  // comparisons as users in PredicateInfo.cpp, or you will cause bugs. See if
1887  // we know something just from the operands themselves
1888 
1889  // See if our operands have predicate info, so that we may be able to derive
1890  // something from a previous comparison.
1891  for (const auto &Op : CI->operands()) {
1892  auto *PI = PredInfo->getPredicateInfoFor(Op);
1893  if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
1894  if (PI == LastPredInfo)
1895  continue;
1896  LastPredInfo = PI;
1897  // In phi of ops cases, we may have predicate info that we are evaluating
1898  // in a different context.
1899  if (!DT->dominates(PBranch->To, getBlockForValue(I)))
1900  continue;
1901  // TODO: Along the false edge, we may know more things too, like
1902  // icmp of
1903  // same operands is false.
1904  // TODO: We only handle actual comparison conditions below, not
1905  // and/or.
1906  auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
1907  if (!BranchCond)
1908  continue;
1909  auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
1910  auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
1911  auto BranchPredicate = BranchCond->getPredicate();
1912  if (shouldSwapOperands(BranchOp0, BranchOp1)) {
1913  std::swap(BranchOp0, BranchOp1);
1914  BranchPredicate = BranchCond->getSwappedPredicate();
1915  }
1916  if (BranchOp0 == Op0 && BranchOp1 == Op1) {
1917  if (PBranch->TrueEdge) {
1918  // If we know the previous predicate is true and we are in the true
1919  // edge then we may be implied true or false.
1920  if (CmpInst::isImpliedTrueByMatchingCmp(BranchPredicate,
1921  OurPredicate)) {
1922  return ExprResult::some(
1923  createConstantExpression(ConstantInt::getTrue(CI->getType())),
1924  PI);
1925  }
1926 
1927  if (CmpInst::isImpliedFalseByMatchingCmp(BranchPredicate,
1928  OurPredicate)) {
1929  return ExprResult::some(
1930  createConstantExpression(ConstantInt::getFalse(CI->getType())),
1931  PI);
1932  }
1933  } else {
1934  // Just handle the ne and eq cases, where if we have the same
1935  // operands, we may know something.
1936  if (BranchPredicate == OurPredicate) {
1937  // Same predicate, same ops,we know it was false, so this is false.
1938  return ExprResult::some(
1939  createConstantExpression(ConstantInt::getFalse(CI->getType())),
1940  PI);
1941  } else if (BranchPredicate ==
1942  CmpInst::getInversePredicate(OurPredicate)) {
1943  // Inverse predicate, we know the other was false, so this is true.
1944  return ExprResult::some(
1945  createConstantExpression(ConstantInt::getTrue(CI->getType())),
1946  PI);
1947  }
1948  }
1949  }
1950  }
1951  }
1952  // Create expression will take care of simplifyCmpInst
1953  return createExpression(I);
1954 }
1955 
1956 // Substitute and symbolize the value before value numbering.
1957 NewGVN::ExprResult
1958 NewGVN::performSymbolicEvaluation(Value *V,
1959  SmallPtrSetImpl<Value *> &Visited) const {
1960 
1961  const Expression *E = nullptr;
1962  if (auto *C = dyn_cast<Constant>(V))
1963  E = createConstantExpression(C);
1964  else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
1965  E = createVariableExpression(V);
1966  } else {
1967  // TODO: memory intrinsics.
1968  // TODO: Some day, we should do the forward propagation and reassociation
1969  // parts of the algorithm.
1970  auto *I = cast<Instruction>(V);
1971  switch (I->getOpcode()) {
1972  case Instruction::ExtractValue:
1973  case Instruction::InsertValue:
1974  E = performSymbolicAggrValueEvaluation(I);
1975  break;
1976  case Instruction::PHI: {
1978  auto *PN = cast<PHINode>(I);
1979  for (unsigned i = 0; i < PN->getNumOperands(); ++i)
1980  Ops.push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)});
1981  // Sort to ensure the invariant createPHIExpression requires is met.
1982  sortPHIOps(Ops);
1983  E = performSymbolicPHIEvaluation(Ops, I, getBlockForValue(I));
1984  } break;
1985  case Instruction::Call:
1986  return performSymbolicCallEvaluation(I);
1987  break;
1988  case Instruction::Store:
1989  E = performSymbolicStoreEvaluation(I);
1990  break;
1991  case Instruction::Load:
1992  E = performSymbolicLoadEvaluation(I);
1993  break;
1994  case Instruction::BitCast:
1995  case Instruction::AddrSpaceCast:
1996  return createExpression(I);
1997  break;
1998  case Instruction::ICmp:
1999  case Instruction::FCmp:
2000  return performSymbolicCmpEvaluation(I);
2001  break;
2002  case Instruction::FNeg:
2003  case Instruction::Add:
2004  case Instruction::FAdd:
2005  case Instruction::Sub:
2006  case Instruction::FSub:
2007  case Instruction::Mul:
2008  case Instruction::FMul:
2009  case Instruction::UDiv:
2010  case Instruction::SDiv:
2011  case Instruction::FDiv:
2012  case Instruction::URem:
2013  case Instruction::SRem:
2014  case Instruction::FRem:
2015  case Instruction::Shl:
2016  case Instruction::LShr:
2017  case Instruction::AShr:
2018  case Instruction::And:
2019  case Instruction::Or:
2020  case Instruction::Xor:
2021  case Instruction::Trunc:
2022  case Instruction::ZExt:
2023  case Instruction::SExt:
2024  case Instruction::FPToUI:
2025  case Instruction::FPToSI:
2026  case Instruction::UIToFP:
2027  case Instruction::SIToFP:
2028  case Instruction::FPTrunc:
2029  case Instruction::FPExt:
2030  case Instruction::PtrToInt:
2031  case Instruction::IntToPtr:
2032  case Instruction::Select:
2033  case Instruction::ExtractElement:
2034  case Instruction::InsertElement:
2035  case Instruction::GetElementPtr:
2036  return createExpression(I);
2037  break;
2038  case Instruction::ShuffleVector:
2039  // FIXME: Add support for shufflevector to createExpression.
2040  return ExprResult::none();
2041  default:
2042  return ExprResult::none();
2043  }
2044  }
2045  return ExprResult::some(E);
2046 }
2047 
2048 // Look up a container of values/instructions in a map, and touch all the
2049 // instructions in the container. Then erase value from the map.
2050 template <typename Map, typename KeyType>
2051 void NewGVN::touchAndErase(Map &M, const KeyType &Key) {
2052  const auto Result = M.find_as(Key);
2053  if (Result != M.end()) {
2054  for (const typename Map::mapped_type::value_type Mapped : Result->second)
2055  TouchedInstructions.set(InstrToDFSNum(Mapped));
2056  M.erase(Result);
2057  }
2058 }
2059 
2060 void NewGVN::addAdditionalUsers(Value *To, Value *User) const {
2061  assert(User && To != User);
2062  if (isa<Instruction>(To))
2063  AdditionalUsers[To].insert(User);
2064 }
2065 
2066 void NewGVN::addAdditionalUsers(ExprResult &Res, Instruction *User) const {
2067  if (Res.ExtraDep && Res.ExtraDep != User)
2068  addAdditionalUsers(Res.ExtraDep, User);
2069  Res.ExtraDep = nullptr;
2070 
2071  if (Res.PredDep) {
2072  if (const auto *PBranch = dyn_cast<PredicateBranch>(Res.PredDep))
2073  PredicateToUsers[PBranch->Condition].insert(User);
2074  else if (const auto *PAssume = dyn_cast<PredicateAssume>(Res.PredDep))
2075  PredicateToUsers[PAssume->Condition].insert(User);
2076  }
2077  Res.PredDep = nullptr;
2078 }
2079 
2080 void NewGVN::markUsersTouched(Value *V) {
2081  // Now mark the users as touched.
2082  for (auto *User : V->users()) {
2083  assert(isa<Instruction>(User) && "Use of value not within an instruction?");
2084  TouchedInstructions.set(InstrToDFSNum(User));
2085  }
2086  touchAndErase(AdditionalUsers, V);
2087 }
2088 
2089 void NewGVN::addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const {
2090  LLVM_DEBUG(dbgs() << "Adding memory user " << *U << " to " << *To << "\n");
2091  MemoryToUsers[To].insert(U);
2092 }
2093 
2094 void NewGVN::markMemoryDefTouched(const MemoryAccess *MA) {
2095  TouchedInstructions.set(MemoryToDFSNum(MA));
2096 }
2097 
2098 void NewGVN::markMemoryUsersTouched(const MemoryAccess *MA) {
2099  if (isa<MemoryUse>(MA))
2100  return;
2101  for (const auto *U : MA->users())
2102  TouchedInstructions.set(MemoryToDFSNum(U));
2103  touchAndErase(MemoryToUsers, MA);
2104 }
2105 
2106 // Touch all the predicates that depend on this instruction.
2107 void NewGVN::markPredicateUsersTouched(Instruction *I) {
2108  touchAndErase(PredicateToUsers, I);
2109 }
2110 
2111 // Mark users affected by a memory leader change.
2112 void NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *CC) {
2113  for (const auto *M : CC->memory())
2114  markMemoryDefTouched(M);
2115 }
2116 
2117 // Touch the instructions that need to be updated after a congruence class has a
2118 // leader change, and mark changed values.
2119 void NewGVN::markValueLeaderChangeTouched(CongruenceClass *CC) {
2120  for (auto *M : *CC) {
2121  if (auto *I = dyn_cast<Instruction>(M))
2122  TouchedInstructions.set(InstrToDFSNum(I));
2123  LeaderChanges.insert(M);
2124  }
2125 }
2126 
2127 // Give a range of things that have instruction DFS numbers, this will return
2128 // the member of the range with the smallest dfs number.
2129 template <class T, class Range>
2130 T *NewGVN::getMinDFSOfRange(const Range &R) const {
2131  std::pair<T *, unsigned> MinDFS = {nullptr, ~0U};
2132  for (const auto X : R) {
2133  auto DFSNum = InstrToDFSNum(X);
2134  if (DFSNum < MinDFS.second)
2135  MinDFS = {X, DFSNum};
2136  }
2137  return MinDFS.first;
2138 }
2139 
2140 // This function returns the MemoryAccess that should be the next leader of
2141 // congruence class CC, under the assumption that the current leader is going to
2142 // disappear.
2143 const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *CC) const {
2144  // TODO: If this ends up to slow, we can maintain a next memory leader like we
2145  // do for regular leaders.
2146  // Make sure there will be a leader to find.
2147  assert(!CC->definesNoMemory() && "Can't get next leader if there is none");
2148  if (CC->getStoreCount() > 0) {
2149  if (auto *NL = dyn_cast_or_null<StoreInst>(CC->getNextLeader().first))
2150  return getMemoryAccess(NL);
2151  // Find the store with the minimum DFS number.
2152  auto *V = getMinDFSOfRange<Value>(make_filter_range(
2153  *CC, [&](const Value *V) { return isa<StoreInst>(V); }));
2154  return getMemoryAccess(cast<StoreInst>(V));
2155  }
2156  assert(CC->getStoreCount() == 0);
2157 
2158  // Given our assertion, hitting this part must mean
2159  // !OldClass->memory_empty()
2160  if (CC->memory_size() == 1)
2161  return *CC->memory_begin();
2162  return getMinDFSOfRange<const MemoryPhi>(CC->memory());
2163 }
2164 
2165 // This function returns the next value leader of a congruence class, under the
2166 // assumption that the current leader is going away. This should end up being
2167 // the next most dominating member.
2168 Value *NewGVN::getNextValueLeader(CongruenceClass *CC) const {
2169  // We don't need to sort members if there is only 1, and we don't care about
2170  // sorting the TOP class because everything either gets out of it or is
2171  // unreachable.
2172 
2173  if (CC->size() == 1 || CC == TOPClass) {
2174  return *(CC->begin());
2175  } else if (CC->getNextLeader().first) {
2176  ++NumGVNAvoidedSortedLeaderChanges;
2177  return CC->getNextLeader().first;
2178  } else {
2179  ++NumGVNSortedLeaderChanges;
2180  // NOTE: If this ends up to slow, we can maintain a dual structure for
2181  // member testing/insertion, or keep things mostly sorted, and sort only
2182  // here, or use SparseBitVector or ....
2183  return getMinDFSOfRange<Value>(*CC);
2184  }
2185 }
2186 
2187 // Move a MemoryAccess, currently in OldClass, to NewClass, including updates to
2188 // the memory members, etc for the move.
2189 //
2190 // The invariants of this function are:
2191 //
2192 // - I must be moving to NewClass from OldClass
2193 // - The StoreCount of OldClass and NewClass is expected to have been updated
2194 // for I already if it is a store.
2195 // - The OldClass memory leader has not been updated yet if I was the leader.
2196 void NewGVN::moveMemoryToNewCongruenceClass(Instruction *I,
2197  MemoryAccess *InstMA,
2198  CongruenceClass *OldClass,
2199  CongruenceClass *NewClass) {
2200  // If the leader is I, and we had a representative MemoryAccess, it should
2201  // be the MemoryAccess of OldClass.
2202  assert((!InstMA || !OldClass->getMemoryLeader() ||
2203  OldClass->getLeader() != I ||
2204  MemoryAccessToClass.lookup(OldClass->getMemoryLeader()) ==
2205  MemoryAccessToClass.lookup(InstMA)) &&
2206  "Representative MemoryAccess mismatch");
2207  // First, see what happens to the new class
2208  if (!NewClass->getMemoryLeader()) {
2209  // Should be a new class, or a store becoming a leader of a new class.
2210  assert(NewClass->size() == 1 ||
2211  (isa<StoreInst>(I) && NewClass->getStoreCount() == 1));
2212  NewClass->setMemoryLeader(InstMA);
2213  // Mark it touched if we didn't just create a singleton
2214  LLVM_DEBUG(dbgs() << "Memory class leader change for class "
2215  << NewClass->getID()
2216  << " due to new memory instruction becoming leader\n");
2217  markMemoryLeaderChangeTouched(NewClass);
2218  }
2219  setMemoryClass(InstMA, NewClass);
2220  // Now, fixup the old class if necessary
2221  if (OldClass->getMemoryLeader() == InstMA) {
2222  if (!OldClass->definesNoMemory()) {
2223  OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
2224  LLVM_DEBUG(dbgs() << "Memory class leader change for class "
2225  << OldClass->getID() << " to "
2226  << *OldClass->getMemoryLeader()
2227  << " due to removal of old leader " << *InstMA << "\n");
2228  markMemoryLeaderChangeTouched(OldClass);
2229  } else
2230  OldClass->setMemoryLeader(nullptr);
2231  }
2232 }
2233 
2234 // Move a value, currently in OldClass, to be part of NewClass
2235 // Update OldClass and NewClass for the move (including changing leaders, etc).
2236 void NewGVN::moveValueToNewCongruenceClass(Instruction *I, const Expression *E,
2237  CongruenceClass *OldClass,
2238  CongruenceClass *NewClass) {
2239  if (I == OldClass->getNextLeader().first)
2240  OldClass->resetNextLeader();
2241 
2242  OldClass->erase(I);
2243  NewClass->insert(I);
2244 
2245  if (NewClass->getLeader() != I)
2246  NewClass->addPossibleNextLeader({I, InstrToDFSNum(I)});
2247  // Handle our special casing of stores.
2248  if (auto *SI = dyn_cast<StoreInst>(I)) {
2249  OldClass->decStoreCount();
2250  // Okay, so when do we want to make a store a leader of a class?
2251  // If we have a store defined by an earlier load, we want the earlier load
2252  // to lead the class.
2253  // If we have a store defined by something else, we want the store to lead
2254  // the class so everything else gets the "something else" as a value.
2255  // If we have a store as the single member of the class, we want the store
2256  // as the leader
2257  if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) {
2258  // If it's a store expression we are using, it means we are not equivalent
2259  // to something earlier.
2260  if (auto *SE = dyn_cast<StoreExpression>(E)) {
2261  NewClass->setStoredValue(SE->getStoredValue());
2262  markValueLeaderChangeTouched(NewClass);
2263  // Shift the new class leader to be the store
2264  LLVM_DEBUG(dbgs() << "Changing leader of congruence class "
2265  << NewClass->getID() << " from "
2266  << *NewClass->getLeader() << " to " << *SI
2267  << " because store joined class\n");
2268  // If we changed the leader, we have to mark it changed because we don't
2269  // know what it will do to symbolic evaluation.
2270  NewClass->setLeader(SI);
2271  }
2272  // We rely on the code below handling the MemoryAccess change.
2273  }
2274  NewClass->incStoreCount();
2275  }
2276  // True if there is no memory instructions left in a class that had memory
2277  // instructions before.
2278 
2279  // If it's not a memory use, set the MemoryAccess equivalence
2280  auto *InstMA = dyn_cast_or_null<MemoryDef>(getMemoryAccess(I));
2281  if (InstMA)
2282  moveMemoryToNewCongruenceClass(I, InstMA, OldClass, NewClass);
2283  ValueToClass[I] = NewClass;
2284  // See if we destroyed the class or need to swap leaders.
2285  if (OldClass->empty() && OldClass != TOPClass) {
2286  if (OldClass->getDefiningExpr()) {
2287  LLVM_DEBUG(dbgs() << "Erasing expression " << *OldClass->getDefiningExpr()
2288  << " from table\n");
2289  // We erase it as an exact expression to make sure we don't just erase an
2290  // equivalent one.
2291  auto Iter = ExpressionToClass.find_as(
2292  ExactEqualsExpression(*OldClass->getDefiningExpr()));
2293  if (Iter != ExpressionToClass.end())
2294  ExpressionToClass.erase(Iter);
2295 #ifdef EXPENSIVE_CHECKS
2296  assert(
2297  (*OldClass->getDefiningExpr() != *E || ExpressionToClass.lookup(E)) &&
2298  "We erased the expression we just inserted, which should not happen");
2299 #endif
2300  }
2301  } else if (OldClass->getLeader() == I) {
2302  // When the leader changes, the value numbering of
2303  // everything may change due to symbolization changes, so we need to
2304  // reprocess.
2305  LLVM_DEBUG(dbgs() << "Value class leader change for class "
2306  << OldClass->getID() << "\n");
2307  ++NumGVNLeaderChanges;
2308  // Destroy the stored value if there are no more stores to represent it.
2309  // Note that this is basically clean up for the expression removal that
2310  // happens below. If we remove stores from a class, we may leave it as a
2311  // class of equivalent memory phis.
2312  if (OldClass->getStoreCount() == 0) {
2313  if (OldClass->getStoredValue())
2314  OldClass->setStoredValue(nullptr);
2315  }
2316  OldClass->setLeader(getNextValueLeader(OldClass));
2317  OldClass->resetNextLeader();
2318  markValueLeaderChangeTouched(OldClass);
2319  }
2320 }
2321 
2322 // For a given expression, mark the phi of ops instructions that could have
2323 // changed as a result.
2324 void NewGVN::markPhiOfOpsChanged(const Expression *E) {
2325  touchAndErase(ExpressionToPhiOfOps, E);
2326 }
2327 
2328 // Perform congruence finding on a given value numbering expression.
2329 void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) {
2330  // This is guaranteed to return something, since it will at least find
2331  // TOP.
2332 
2333  CongruenceClass *IClass = ValueToClass.lookup(I);
2334  assert(IClass && "Should have found a IClass");
2335  // Dead classes should have been eliminated from the mapping.
2336  assert(!IClass->isDead() && "Found a dead class");
2337 
2338  CongruenceClass *EClass = nullptr;
2339  if (const auto *VE = dyn_cast<VariableExpression>(E)) {
2340  EClass = ValueToClass.lookup(VE->getVariableValue());
2341  } else if (isa<DeadExpression>(E)) {
2342  EClass = TOPClass;
2343  }
2344  if (!EClass) {
2345  auto lookupResult = ExpressionToClass.insert({E, nullptr});
2346 
2347  // If it's not in the value table, create a new congruence class.
2348  if (lookupResult.second) {
2349  CongruenceClass *NewClass = createCongruenceClass(nullptr, E);
2350  auto place = lookupResult.first;
2351  place->second = NewClass;
2352 
2353  // Constants and variables should always be made the leader.
2354  if (const auto *CE = dyn_cast<ConstantExpression>(E)) {
2355  NewClass->setLeader(CE->getConstantValue());
2356  } else if (const auto *SE = dyn_cast<StoreExpression>(E)) {
2357  StoreInst *SI = SE->getStoreInst();
2358  NewClass->setLeader(SI);
2359  NewClass->setStoredValue(SE->getStoredValue());
2360  // The RepMemoryAccess field will be filled in properly by the
2361  // moveValueToNewCongruenceClass call.
2362  } else {
2363  NewClass->setLeader(I);
2364  }
2365  assert(!isa<VariableExpression>(E) &&
2366  "VariableExpression should have been handled already");
2367 
2368  EClass = NewClass;
2369  LLVM_DEBUG(dbgs() << "Created new congruence class for " << *I
2370  << " using expression " << *E << " at "
2371  << NewClass->getID() << " and leader "
2372  << *(NewClass->getLeader()));
2373  if (NewClass->getStoredValue())
2374  LLVM_DEBUG(dbgs() << " and stored value "
2375  << *(NewClass->getStoredValue()));
2376  LLVM_DEBUG(dbgs() << "\n");
2377  } else {
2378  EClass = lookupResult.first->second;
2379  if (isa<ConstantExpression>(E))
2380  assert((isa<Constant>(EClass->getLeader()) ||
2381  (EClass->getStoredValue() &&
2382  isa<Constant>(EClass->getStoredValue()))) &&
2383  "Any class with a constant expression should have a "
2384  "constant leader");
2385 
2386  assert(EClass && "Somehow don't have an eclass");
2387 
2388  assert(!EClass->isDead() && "We accidentally looked up a dead class");
2389  }
2390  }
2391  bool ClassChanged = IClass != EClass;
2392  bool LeaderChanged = LeaderChanges.erase(I);
2393  if (ClassChanged || LeaderChanged) {
2394  LLVM_DEBUG(dbgs() << "New class " << EClass->getID() << " for expression "
2395  << *E << "\n");
2396  if (ClassChanged) {
2397  moveValueToNewCongruenceClass(I, E, IClass, EClass);
2398  markPhiOfOpsChanged(E);
2399  }
2400 
2401  markUsersTouched(I);
2402  if (MemoryAccess *MA = getMemoryAccess(I))
2403  markMemoryUsersTouched(MA);
2404  if (auto *CI = dyn_cast<CmpInst>(I))
2405  markPredicateUsersTouched(CI);
2406  }
2407  // If we changed the class of the store, we want to ensure nothing finds the
2408  // old store expression. In particular, loads do not compare against stored
2409  // value, so they will find old store expressions (and associated class
2410  // mappings) if we leave them in the table.
2411  if (ClassChanged && isa<StoreInst>(I)) {
2412  auto *OldE = ValueToExpression.lookup(I);
2413  // It could just be that the old class died. We don't want to erase it if we
2414  // just moved classes.
2415  if (OldE && isa<StoreExpression>(OldE) && *E != *OldE) {
2416  // Erase this as an exact expression to ensure we don't erase expressions
2417  // equivalent to it.
2418  auto Iter = ExpressionToClass.find_as(ExactEqualsExpression(*OldE));
2419  if (Iter != ExpressionToClass.end())
2420  ExpressionToClass.erase(Iter);
2421  }
2422  }
2423  ValueToExpression[I] = E;
2424 }
2425 
2426 // Process the fact that Edge (from, to) is reachable, including marking
2427 // any newly reachable blocks and instructions for processing.
2428 void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) {
2429  // Check if the Edge was reachable before.
2430  if (ReachableEdges.insert({From, To}).second) {
2431  // If this block wasn't reachable before, all instructions are touched.
2432  if (ReachableBlocks.insert(To).second) {
2433  LLVM_DEBUG(dbgs() << "Block " << getBlockName(To)
2434  << " marked reachable\n");
2435  const auto &InstRange = BlockInstRange.lookup(To);
2436  TouchedInstructions.set(InstRange.first, InstRange.second);
2437  } else {
2438  LLVM_DEBUG(dbgs() << "Block " << getBlockName(To)
2439  << " was reachable, but new edge {"
2440  << getBlockName(From) << "," << getBlockName(To)
2441  << "} to it found\n");
2442 
2443  // We've made an edge reachable to an existing block, which may
2444  // impact predicates. Otherwise, only mark the phi nodes as touched, as
2445  // they are the only thing that depend on new edges. Anything using their
2446  // values will get propagated to if necessary.
2447  if (MemoryAccess *MemPhi = getMemoryAccess(To))
2448  TouchedInstructions.set(InstrToDFSNum(MemPhi));
2449 
2450  // FIXME: We should just add a union op on a Bitvector and
2451  // SparseBitVector. We can do it word by word faster than we are doing it
2452  // here.
2453  for (auto InstNum : RevisitOnReachabilityChange[To])
2454  TouchedInstructions.set(InstNum);
2455  }
2456  }
2457 }
2458 
2459 // Given a predicate condition (from a switch, cmp, or whatever) and a block,
2460 // see if we know some constant value for it already.
2461 Value *NewGVN::findConditionEquivalence(Value *Cond) const {
2462  auto Result = lookupOperandLeader(Cond);
2463  return isa<Constant>(Result) ? Result : nullptr;
2464 }
2465 
2466 // Process the outgoing edges of a block for reachability.
2467 void NewGVN::processOutgoingEdges(Instruction *TI, BasicBlock *B) {
2468  // Evaluate reachability of terminator instruction.
2469  Value *Cond;
2470  BasicBlock *TrueSucc, *FalseSucc;
2471  if (match(TI, m_Br(m_Value(Cond), TrueSucc, FalseSucc))) {
2472  Value *CondEvaluated = findConditionEquivalence(Cond);
2473  if (!CondEvaluated) {
2474  if (auto *I = dyn_cast<Instruction>(Cond)) {
2475  SmallPtrSet<Value *, 4> Visited;
2476  auto Res = performSymbolicEvaluation(I, Visited);
2477  if (const auto *CE = dyn_cast_or_null<ConstantExpression>(Res.Expr)) {
2478  CondEvaluated = CE->getConstantValue();
2479  addAdditionalUsers(Res, I);
2480  } else {
2481  // Did not use simplification result, no need to add the extra
2482  // dependency.
2483  Res.ExtraDep = nullptr;
2484  }
2485  } else if (isa<ConstantInt>(Cond)) {
2486  CondEvaluated = Cond;
2487  }
2488  }
2489  ConstantInt *CI;
2490  if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
2491  if (CI->isOne()) {
2492  LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI
2493  << " evaluated to true\n");
2494  updateReachableEdge(B, TrueSucc);
2495  } else if (CI->isZero()) {
2496  LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI
2497  << " evaluated to false\n");
2498  updateReachableEdge(B, FalseSucc);
2499  }
2500  } else {
2501  updateReachableEdge(B, TrueSucc);
2502  updateReachableEdge(B, FalseSucc);
2503  }
2504  } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
2505  // For switches, propagate the case values into the case
2506  // destinations.
2507 
2508  Value *SwitchCond = SI->getCondition();
2509  Value *CondEvaluated = findConditionEquivalence(SwitchCond);
2510  // See if we were able to turn this switch statement into a constant.
2511  if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
2512  auto *CondVal = cast<ConstantInt>(CondEvaluated);
2513  // We should be able to get case value for this.
2514  auto Case = *SI->findCaseValue(CondVal);
2515  if (Case.getCaseSuccessor() == SI->getDefaultDest()) {
2516  // We proved the value is outside of the range of the case.
2517  // We can't do anything other than mark the default dest as reachable,
2518  // and go home.
2519  updateReachableEdge(B, SI->getDefaultDest());
2520  return;
2521  }
2522  // Now get where it goes and mark it reachable.
2523  BasicBlock *TargetBlock = Case.getCaseSuccessor();
2524  updateReachableEdge(B, TargetBlock);
2525  } else {
2526  for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
2527  BasicBlock *TargetBlock = SI->getSuccessor(i);
2528  updateReachableEdge(B, TargetBlock);
2529  }
2530  }
2531  } else {
2532  // Otherwise this is either unconditional, or a type we have no
2533  // idea about. Just mark successors as reachable.
2534  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
2535  BasicBlock *TargetBlock = TI->getSuccessor(i);
2536  updateReachableEdge(B, TargetBlock);
2537  }
2538 
2539  // This also may be a memory defining terminator, in which case, set it
2540  // equivalent only to itself.
2541  //
2542  auto *MA = getMemoryAccess(TI);
2543  if (MA && !isa<MemoryUse>(MA)) {
2544  auto *CC = ensureLeaderOfMemoryClass(MA);
2545  if (setMemoryClass(MA, CC))
2546  markMemoryUsersTouched(MA);
2547  }
2548  }
2549 }
2550 
2551 // Remove the PHI of Ops PHI for I
2552 void NewGVN::removePhiOfOps(Instruction *I, PHINode *PHITemp) {
2553  InstrDFS.erase(PHITemp);
2554  // It's still a temp instruction. We keep it in the array so it gets erased.
2555  // However, it's no longer used by I, or in the block
2556  TempToBlock.erase(PHITemp);
2557  RealToTemp.erase(I);
2558  // We don't remove the users from the phi node uses. This wastes a little
2559  // time, but such is life. We could use two sets to track which were there
2560  // are the start of NewGVN, and which were added, but right nowt he cost of
2561  // tracking is more than the cost of checking for more phi of ops.
2562 }
2563 
2564 // Add PHI Op in BB as a PHI of operations version of ExistingValue.
2565 void NewGVN::addPhiOfOps(PHINode *Op, BasicBlock *BB,
2566  Instruction *ExistingValue) {
2567  InstrDFS[Op] = InstrToDFSNum(ExistingValue);
2568  AllTempInstructions.insert(Op);
2569  TempToBlock[Op] = BB;
2570  RealToTemp[ExistingValue] = Op;
2571  // Add all users to phi node use, as they are now uses of the phi of ops phis
2572  // and may themselves be phi of ops.
2573  for (auto *U : ExistingValue->users())
2574  if (auto *UI = dyn_cast<Instruction>(U))
2575  PHINodeUses.insert(UI);
2576 }
2577 
2578 static bool okayForPHIOfOps(const Instruction *I) {
2579  if (!EnablePhiOfOps)
2580  return false;
2581  return isa<BinaryOperator>(I) || isa<SelectInst>(I) || isa<CmpInst>(I) ||
2582  isa<LoadInst>(I);
2583 }
2584 
2585 // Return true if this operand will be safe to use for phi of ops.
2586 //
2587 // The reason some operands are unsafe is that we are not trying to recursively
2588 // translate everything back through phi nodes. We actually expect some lookups
2589 // of expressions to fail. In particular, a lookup where the expression cannot
2590 // exist in the predecessor. This is true even if the expression, as shown, can
2591 // be determined to be constant.
2592 bool NewGVN::OpIsSafeForPHIOfOps(Value *V, const BasicBlock *PHIBlock,
2593  SmallPtrSetImpl<const Value *> &Visited) {
2594  SmallVector<Value *, 4> Worklist;
2595  Worklist.push_back(V);
2596  while (!Worklist.empty()) {
2597  auto *I = Worklist.pop_back_val();
2598  if (!isa<Instruction>(I))
2599  continue;
2600 
2601  auto OISIt = OpSafeForPHIOfOps.find(I);
2602  if (OISIt != OpSafeForPHIOfOps.end())
2603  return OISIt->second;
2604 
2605  // Keep walking until we either dominate the phi block, or hit a phi, or run
2606  // out of things to check.
2607  if (DT->properlyDominates(getBlockForValue(I), PHIBlock)) {
2608  OpSafeForPHIOfOps.insert({I, true});
2609  continue;
2610  }
2611  // PHI in the same block.
2612  if (isa<PHINode>(I) && getBlockForValue(I) == PHIBlock) {
2613  OpSafeForPHIOfOps.insert({I, false});
2614  return false;
2615  }
2616 
2617  auto *OrigI = cast<Instruction>(I);
2618  // When we hit an instruction that reads memory (load, call, etc), we must
2619  // consider any store that may happen in the loop. For now, we assume the
2620  // worst: there is a store in the loop that alias with this read.
2621  // The case where the load is outside the loop is already covered by the
2622  // dominator check above.
2623  // TODO: relax this condition
2624  if (OrigI->mayReadFromMemory())
2625  return false;
2626 
2627  // Check the operands of the current instruction.
2628  for (auto *Op : OrigI->operand_values()) {
2629  if (!isa<Instruction>(Op))
2630  continue;
2631  // Stop now if we find an unsafe operand.
2632  auto OISIt = OpSafeForPHIOfOps.find(OrigI);
2633  if (OISIt != OpSafeForPHIOfOps.end()) {
2634  if (!OISIt->second) {
2635  OpSafeForPHIOfOps.insert({I, false});
2636  return false;
2637  }
2638  continue;
2639  }
2640  if (!Visited.insert(Op).second)
2641  continue;
2642  Worklist.push_back(cast<Instruction>(Op));
2643  }
2644  }
2645  OpSafeForPHIOfOps.insert({V, true});
2646  return true;
2647 }
2648 
2649 // Try to find a leader for instruction TransInst, which is a phi translated
2650 // version of something in our original program. Visited is used to ensure we
2651 // don't infinite loop during translations of cycles. OrigInst is the
2652 // instruction in the original program, and PredBB is the predecessor we
2653 // translated it through.
2654 Value *NewGVN::findLeaderForInst(Instruction *TransInst,
2655  SmallPtrSetImpl<Value *> &Visited,
2656  MemoryAccess *MemAccess, Instruction *OrigInst,
2657  BasicBlock *PredBB) {
2658  unsigned IDFSNum = InstrToDFSNum(OrigInst);
2659  // Make sure it's marked as a temporary instruction.
2660  AllTempInstructions.insert(TransInst);
2661  // and make sure anything that tries to add it's DFS number is
2662  // redirected to the instruction we are making a phi of ops
2663  // for.
2664  TempToBlock.insert({TransInst, PredBB});
2665  InstrDFS.insert({TransInst, IDFSNum});
2666 
2667  auto Res = performSymbolicEvaluation(TransInst, Visited);
2668  const Expression *E = Res.Expr;
2669  addAdditionalUsers(Res, OrigInst);
2670  InstrDFS.erase(TransInst);
2671  AllTempInstructions.erase(TransInst);
2672  TempToBlock.erase(TransInst);
2673  if (MemAccess)
2674  TempToMemory.erase(TransInst);
2675  if (!E)
2676  return nullptr;
2677  auto *FoundVal = findPHIOfOpsLeader(E, OrigInst, PredBB);
2678  if (!FoundVal) {
2679  ExpressionToPhiOfOps[E].insert(OrigInst);
2680  LLVM_DEBUG(dbgs() << "Cannot find phi of ops operand for " << *TransInst
2681  << " in block " << getBlockName(PredBB) << "\n");
2682  return nullptr;
2683  }
2684  if (auto *SI = dyn_cast<StoreInst>(FoundVal))
2685  FoundVal = SI->getValueOperand();
2686  return FoundVal;
2687 }
2688 
2689 // When we see an instruction that is an op of phis, generate the equivalent phi
2690 // of ops form.
2691 const Expression *
2692 NewGVN::makePossiblePHIOfOps(Instruction *I,
2693  SmallPtrSetImpl<Value *> &Visited) {
2694  if (!okayForPHIOfOps(I))
2695  return nullptr;
2696 
2697  if (!Visited.insert(I).second)
2698  return nullptr;
2699  // For now, we require the instruction be cycle free because we don't
2700  // *always* create a phi of ops for instructions that could be done as phi
2701  // of ops, we only do it if we think it is useful. If we did do it all the
2702  // time, we could remove the cycle free check.
2703  if (!isCycleFree(I))
2704  return nullptr;
2705 
2706  SmallPtrSet<const Value *, 8> ProcessedPHIs;
2707  // TODO: We don't do phi translation on memory accesses because it's
2708  // complicated. For a load, we'd need to be able to simulate a new memoryuse,
2709  // which we don't have a good way of doing ATM.
2710  auto *MemAccess = getMemoryAccess(I);
2711  // If the memory operation is defined by a memory operation this block that
2712  // isn't a MemoryPhi, transforming the pointer backwards through a scalar phi
2713  // can't help, as it would still be killed by that memory operation.
2714  if (MemAccess && !isa<MemoryPhi>(MemAccess->getDefiningAccess()) &&
2715  MemAccess->getDefiningAccess()->getBlock() == I->getParent())
2716  return nullptr;
2717 
2718  // Convert op of phis to phi of ops
2719  SmallPtrSet<const Value *, 10> VisitedOps;
2720  SmallVector<Value *, 4> Ops(I->operand_values());
2721  BasicBlock *SamePHIBlock = nullptr;
2722  PHINode *OpPHI = nullptr;
2723  if (!DebugCounter::shouldExecute(PHIOfOpsCounter))
2724  return nullptr;
2725  for (auto *Op : Ops) {
2726  if (!isa<PHINode>(Op)) {
2727  auto *ValuePHI = RealToTemp.lookup(Op);
2728  if (!ValuePHI)
2729  continue;
2730  LLVM_DEBUG(dbgs() << "Found possible dependent phi of ops\n");
2731  Op = ValuePHI;
2732  }
2733  OpPHI = cast<PHINode>(Op);
2734  if (!SamePHIBlock) {
2735  SamePHIBlock = getBlockForValue(OpPHI);
2736  } else if (SamePHIBlock != getBlockForValue(OpPHI)) {
2737  LLVM_DEBUG(
2738  dbgs()
2739  << "PHIs for operands are not all in the same block, aborting\n");
2740  return nullptr;
2741  }
2742  // No point in doing this for one-operand phis.
2743  if (OpPHI->getNumOperands() == 1) {
2744  OpPHI = nullptr;
2745  continue;
2746  }
2747  }
2748 
2749  if (!OpPHI)
2750  return nullptr;
2751 
2752  SmallVector<ValPair, 4> PHIOps;
2754  auto *PHIBlock = getBlockForValue(OpPHI);
2755  RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(I));
2756  for (unsigned PredNum = 0; PredNum < OpPHI->getNumOperands(); ++PredNum) {
2757  auto *PredBB = OpPHI->getIncomingBlock(PredNum);
2758  Value *FoundVal = nullptr;
2759  SmallPtrSet<Value *, 4> CurrentDeps;
2760  // We could just skip unreachable edges entirely but it's tricky to do
2761  // with rewriting existing phi nodes.
2762  if (ReachableEdges.count({PredBB, PHIBlock})) {
2763  // Clone the instruction, create an expression from it that is
2764  // translated back into the predecessor, and see if we have a leader.
2765  Instruction *ValueOp = I->clone();
2766  if (MemAccess)
2767  TempToMemory.insert({ValueOp, MemAccess});
2768  bool SafeForPHIOfOps = true;
2769  VisitedOps.clear();
2770  for (auto &Op : ValueOp->operands()) {
2771  auto *OrigOp = &*Op;
2772  // When these operand changes, it could change whether there is a
2773  // leader for us or not, so we have to add additional users.
2774  if (isa<PHINode>(Op)) {
2775  Op = Op->DoPHITranslation(PHIBlock, PredBB);
2776  if (Op != OrigOp && Op != I)
2777  CurrentDeps.insert(Op);
2778  } else if (auto *ValuePHI = RealToTemp.lookup(Op)) {
2779  if (getBlockForValue(ValuePHI) == PHIBlock)
2780  Op = ValuePHI->getIncomingValueForBlock(PredBB);
2781  }
2782  // If we phi-translated the op, it must be safe.
2783  SafeForPHIOfOps =
2784  SafeForPHIOfOps &&
2785  (Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps));
2786  }
2787  // FIXME: For those things that are not safe we could generate
2788  // expressions all the way down, and see if this comes out to a
2789  // constant. For anything where that is true, and unsafe, we should
2790  // have made a phi-of-ops (or value numbered it equivalent to something)
2791  // for the pieces already.
2792  FoundVal = !SafeForPHIOfOps ? nullptr
2793  : findLeaderForInst(ValueOp, Visited,
2794  MemAccess, I, PredBB);
2795  ValueOp->deleteValue();
2796  if (!FoundVal) {
2797  // We failed to find a leader for the current ValueOp, but this might
2798  // change in case of the translated operands change.
2799  if (SafeForPHIOfOps)
2800  for (auto *Dep : CurrentDeps)
2801  addAdditionalUsers(Dep, I);
2802 
2803  return nullptr;
2804  }
2805  Deps.insert(CurrentDeps.begin(), CurrentDeps.end());
2806  } else {
2807  LLVM_DEBUG(dbgs() << "Skipping phi of ops operand for incoming block "
2808  << getBlockName(PredBB)
2809  << " because the block is unreachable\n");
2810  FoundVal = PoisonValue::get(I->getType());
2811  RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
2812  }
2813 
2814  PHIOps.push_back({FoundVal, PredBB});
2815  LLVM_DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in "
2816  << getBlockName(PredBB) << "\n");
2817  }
2818  for (auto *Dep : Deps)
2819  addAdditionalUsers(Dep, I);
2820  sortPHIOps(PHIOps);
2821  auto *E = performSymbolicPHIEvaluation(PHIOps, I, PHIBlock);
2822  if (isa<ConstantExpression>(E) || isa<VariableExpression>(E)) {
2823  LLVM_DEBUG(
2824  dbgs()
2825  << "Not creating real PHI of ops because it simplified to existing "
2826  "value or constant\n");
2827  // We have leaders for all operands, but do not create a real PHI node with
2828  // those leaders as operands, so the link between the operands and the
2829  // PHI-of-ops is not materialized in the IR. If any of those leaders
2830  // changes, the PHI-of-op may change also, so we need to add the operands as
2831  // additional users.
2832  for (auto &O : PHIOps)
2833  addAdditionalUsers(O.first, I);
2834 
2835  return E;
2836  }
2837  auto *ValuePHI = RealToTemp.lookup(I);
2838  bool NewPHI = false;
2839  if (!ValuePHI) {
2840  ValuePHI =
2841  PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops");
2842  addPhiOfOps(ValuePHI, PHIBlock, I);
2843  NewPHI = true;
2844  NumGVNPHIOfOpsCreated++;
2845  }
2846  if (NewPHI) {
2847  for (auto PHIOp : PHIOps)
2848  ValuePHI->addIncoming(PHIOp.first, PHIOp.second);
2849  } else {
2850  TempToBlock[ValuePHI] = PHIBlock;
2851  unsigned int i = 0;
2852  for (auto PHIOp : PHIOps) {
2853  ValuePHI->setIncomingValue(i, PHIOp.first);
2854  ValuePHI->setIncomingBlock(i, PHIOp.second);
2855  ++i;
2856  }
2857  }
2858  RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
2859  LLVM_DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I
2860  << "\n");
2861 
2862  return E;
2863 }
2864 
2865 // The algorithm initially places the values of the routine in the TOP
2866 // congruence class. The leader of TOP is the undetermined value `poison`.
2867 // When the algorithm has finished, values still in TOP are unreachable.
2868 void NewGVN::initializeCongruenceClasses(Function &F) {
2869  NextCongruenceNum = 0;
2870 
2871  // Note that even though we use the live on entry def as a representative
2872  // MemoryAccess, it is *not* the same as the actual live on entry def. We
2873  // have no real equivalent to poison for MemoryAccesses, and so we really
2874  // should be checking whether the MemoryAccess is top if we want to know if it
2875  // is equivalent to everything. Otherwise, what this really signifies is that
2876  // the access "it reaches all the way back to the beginning of the function"
2877 
2878  // Initialize all other instructions to be in TOP class.
2879  TOPClass = createCongruenceClass(nullptr, nullptr);
2880  TOPClass->setMemoryLeader(MSSA->getLiveOnEntryDef());
2881  // The live on entry def gets put into it's own class
2882  MemoryAccessToClass[MSSA->getLiveOnEntryDef()] =
2883  createMemoryClass(MSSA->getLiveOnEntryDef());
2884 
2885  for (auto *DTN : nodes(DT)) {
2886  BasicBlock *BB = DTN->getBlock();
2887  // All MemoryAccesses are equivalent to live on entry to start. They must
2888  // be initialized to something so that initial changes are noticed. For
2889  // the maximal answer, we initialize them all to be the same as
2890  // liveOnEntry.
2891  auto *MemoryBlockDefs = MSSA->getBlockDefs(BB);
2892  if (MemoryBlockDefs)
2893  for (const auto &Def : *MemoryBlockDefs) {
2894  MemoryAccessToClass[&Def] = TOPClass;
2895  auto *MD = dyn_cast<MemoryDef>(&Def);
2896  // Insert the memory phis into the member list.
2897  if (!MD) {
2898  const MemoryPhi *MP = cast<MemoryPhi>(&Def);
2899  TOPClass->memory_insert(MP);
2900  MemoryPhiState.insert({MP, MPS_TOP});
2901  }
2902 
2903  if (MD && isa<StoreInst>(MD->getMemoryInst()))
2904  TOPClass->incStoreCount();
2905  }
2906 
2907  // FIXME: This is trying to discover which instructions are uses of phi
2908  // nodes. We should move this into one of the myriad of places that walk
2909  // all the operands already.
2910  for (auto &I : *BB) {
2911  if (isa<PHINode>(&I))
2912  for (auto *U : I.users())
2913  if (auto *UInst = dyn_cast<Instruction>(U))
2914  if (InstrToDFSNum(UInst) != 0 && okayForPHIOfOps(UInst))
2915  PHINodeUses.insert(UInst);
2916  // Don't insert void terminators into the class. We don't value number
2917  // them, and they just end up sitting in TOP.
2918  if (I.isTerminator() && I.getType()->isVoidTy())
2919  continue;
2920  TOPClass->insert(&I);
2921  ValueToClass[&I] = TOPClass;
2922  }
2923  }
2924 
2925  // Initialize arguments to be in their own unique congruence classes
2926  for (auto &FA : F.args())
2927  createSingletonCongruenceClass(&FA);
2928 }
2929 
2930 void NewGVN::cleanupTables() {
2931  for (CongruenceClass *&CC : CongruenceClasses) {
2932  LLVM_DEBUG(dbgs() << "Congruence class " << CC->getID() << " has "
2933  << CC->size() << " members\n");
2934  // Make sure we delete the congruence class (probably worth switching to
2935  // a unique_ptr at some point.
2936  delete CC;
2937  CC = nullptr;
2938  }
2939 
2940  // Destroy the value expressions
2941  SmallVector<Instruction *, 8> TempInst(AllTempInstructions.begin(),
2942  AllTempInstructions.end());
2943  AllTempInstructions.clear();
2944 
2945  // We have to drop all references for everything first, so there are no uses
2946  // left as we delete them.
2947  for (auto *I : TempInst) {
2948  I->dropAllReferences();
2949  }
2950 
2951  while (!TempInst.empty()) {
2952  auto *I = TempInst.pop_back_val();
2953  I->deleteValue();
2954  }
2955 
2956  ValueToClass.clear();
2957  ArgRecycler.clear(ExpressionAllocator);
2958  ExpressionAllocator.Reset();
2959  CongruenceClasses.clear();
2960  ExpressionToClass.clear();
2961  ValueToExpression.clear();
2962  RealToTemp.clear();
2963  AdditionalUsers.clear();
2964  ExpressionToPhiOfOps.clear();
2965  TempToBlock.clear();
2966  TempToMemory.clear();
2967  PHINodeUses.clear();
2968  OpSafeForPHIOfOps.clear();
2969  ReachableBlocks.clear();
2970  ReachableEdges.clear();
2971 #ifndef NDEBUG
2972  ProcessedCount.clear();
2973 #endif
2974  InstrDFS.clear();
2975  InstructionsToErase.clear();
2976  DFSToInstr.clear();
2977  BlockInstRange.clear();
2978  TouchedInstructions.clear();
2979  MemoryAccessToClass.clear();
2980  PredicateToUsers.clear();
2981  MemoryToUsers.clear();
2982  RevisitOnReachabilityChange.clear();
2983  IntrinsicInstPred.clear();
2984 }
2985 
2986 // Assign local DFS number mapping to instructions, and leave space for Value
2987 // PHI's.
2988 std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
2989  unsigned Start) {
2990  unsigned End = Start;
2991  if (MemoryAccess *MemPhi = getMemoryAccess(B)) {
2992  InstrDFS[MemPhi] = End++;
2993  DFSToInstr.emplace_back(MemPhi);
2994  }
2995 
2996  // Then the real block goes next.
2997  for (auto &I : *B) {
2998  // There's no need to call isInstructionTriviallyDead more than once on
2999  // an instruction. Therefore, once we know that an instruction is dead
3000  // we change its DFS number so that it doesn't get value numbered.
3001  if (isInstructionTriviallyDead(&I, TLI)) {
3002  InstrDFS[&I] = 0;
3003  LLVM_DEBUG(dbgs() << "Skipping trivially dead instruction " << I << "\n");
3004  markInstructionForDeletion(&I);
3005  continue;
3006  }
3007  if (isa<PHINode>(&I))
3008  RevisitOnReachabilityChange[B].set(End);
3009  InstrDFS[&I] = End++;
3010  DFSToInstr.emplace_back(&I);
3011  }
3012 
3013  // All of the range functions taken half-open ranges (open on the end side).
3014  // So we do not subtract one from count, because at this point it is one
3015  // greater than the last instruction.
3016  return std::make_pair(Start, End);
3017 }
3018 
3019 void NewGVN::updateProcessedCount(const Value *V) {
3020 #ifndef NDEBUG
3021  if (ProcessedCount.count(V) == 0) {
3022  ProcessedCount.insert({V, 1});
3023  } else {
3024  ++ProcessedCount[V];
3025  assert(ProcessedCount[V] < 100 &&
3026  "Seem to have processed the same Value a lot");
3027  }
3028 #endif
3029 }
3030 
3031 // Evaluate MemoryPhi nodes symbolically, just like PHI nodes
3032 void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) {
3033  // If all the arguments are the same, the MemoryPhi has the same value as the
3034  // argument. Filter out unreachable blocks and self phis from our operands.
3035  // TODO: We could do cycle-checking on the memory phis to allow valueizing for
3036  // self-phi checking.
3037  const BasicBlock *PHIBlock = MP->getBlock();
3038  auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) {
3039  return cast<MemoryAccess>(U) != MP &&
3040  !isMemoryAccessTOP(cast<MemoryAccess>(U)) &&
3041  ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock});
3042  });
3043  // If all that is left is nothing, our memoryphi is poison. We keep it as
3044  // InitialClass. Note: The only case this should happen is if we have at
3045  // least one self-argument.
3046  if (Filtered.begin() == Filtered.end()) {
3047  if (setMemoryClass(MP, TOPClass))
3048  markMemoryUsersTouched(MP);
3049  return;
3050  }
3051 
3052  // Transform the remaining operands into operand leaders.
3053  // FIXME: mapped_iterator should have a range version.
3054  auto LookupFunc = [&](const Use &U) {
3055  return lookupMemoryLeader(cast<MemoryAccess>(U));
3056  };
3057  auto MappedBegin = map_iterator(Filtered.begin(), LookupFunc);
3058  auto MappedEnd = map_iterator(Filtered.end(), LookupFunc);
3059 
3060  // and now check if all the elements are equal.
3061  // Sadly, we can't use std::equals since these are random access iterators.
3062  const auto *AllSameValue = *MappedBegin;
3063  ++MappedBegin;
3064  bool AllEqual = std::all_of(
3065  MappedBegin, MappedEnd,
3066  [&AllSameValue](const MemoryAccess *V) { return V == AllSameValue; });
3067 
3068  if (AllEqual)
3069  LLVM_DEBUG(dbgs() << "Memory Phi value numbered to " << *AllSameValue
3070  << "\n");
3071  else
3072  LLVM_DEBUG(dbgs() << "Memory Phi value numbered to itself\n");
3073  // If it's equal to something, it's in that class. Otherwise, it has to be in
3074  // a class where it is the leader (other things may be equivalent to it, but
3075  // it needs to start off in its own class, which means it must have been the
3076  // leader, and it can't have stopped being the leader because it was never
3077  // removed).
3078  CongruenceClass *CC =
3079  AllEqual ? getMemoryClass(AllSameValue) : ensureLeaderOfMemoryClass(MP);
3080  auto OldState = MemoryPhiState.lookup(MP);
3081  assert(OldState != MPS_Invalid && "Invalid memory phi state");
3082  auto NewState = AllEqual ? MPS_Equivalent : MPS_Unique;
3083  MemoryPhiState[MP] = NewState;
3084  if (setMemoryClass(MP, CC) || OldState != NewState)
3085  markMemoryUsersTouched(MP);
3086 }
3087 
3088 // Value number a single instruction, symbolically evaluating, performing
3089 // congruence finding, and updating mappings.
3090 void NewGVN::valueNumberInstruction(Instruction *I) {
3091  LLVM_DEBUG(dbgs() << "Processing instruction " << *I << "\n");
3092  if (!I->isTerminator()) {
3093  const Expression *Symbolized = nullptr;
3094  SmallPtrSet<Value *, 2> Visited;
3095  if (DebugCounter::shouldExecute(VNCounter)) {
3096  auto Res = performSymbolicEvaluation(I, Visited);
3097  Symbolized = Res.Expr;
3098  addAdditionalUsers(Res, I);
3099 
3100  // Make a phi of ops if necessary
3101  if (Symbolized && !isa<ConstantExpression>(Symbolized) &&
3102  !isa<VariableExpression>(Symbolized) && PHINodeUses.count(I)) {
3103  auto *PHIE = makePossiblePHIOfOps(I, Visited);
3104  // If we created a phi of ops, use it.
3105  // If we couldn't create one, make sure we don't leave one lying around
3106  if (PHIE) {
3107  Symbolized = PHIE;
3108  } else if (auto *Op = RealToTemp.lookup(I)) {
3109  removePhiOfOps(I, Op);
3110  }
3111  }
3112  } else {
3113  // Mark the instruction as unused so we don't value number it again.
3114  InstrDFS[I] = 0;
3115  }
3116  // If we couldn't come up with a symbolic expression, use the unknown
3117  // expression
3118  if (Symbolized == nullptr)
3119  Symbolized = createUnknownExpression(I);
3120  performCongruenceFinding(I, Symbolized);
3121  } else {
3122  // Handle terminators that return values. All of them produce values we
3123  // don't currently understand. We don't place non-value producing
3124  // terminators in a class.
3125  if (!I->getType()->isVoidTy()) {
3126  auto *Symbolized = createUnknownExpression(I);
3127  performCongruenceFinding(I, Symbolized);
3128  }
3129  processOutgoingEdges(I, I->getParent());
3130  }
3131 }
3132 
3133 // Check if there is a path, using single or equal argument phi nodes, from
3134 // First to Second.
3135 bool NewGVN::singleReachablePHIPath(
3137  const MemoryAccess *Second) const {
3138  if (First == Second)
3139  return true;
3140  if (MSSA->isLiveOnEntryDef(First))
3141  return false;
3142 
3143  // This is not perfect, but as we're just verifying here, we can live with
3144  // the loss of precision. The real solution would be that of doing strongly
3145  // connected component finding in this routine, and it's probably not worth
3146  // the complexity for the time being. So, we just keep a set of visited
3147  // MemoryAccess and return true when we hit a cycle.
3148  if (!Visited.insert(First).second)
3149  return true;
3150 
3151  const auto *EndDef = First;
3152  for (const auto *ChainDef : optimized_def_chain(First)) {
3153  if (ChainDef == Second)
3154  return true;
3155  if (MSSA->isLiveOnEntryDef(ChainDef))
3156  return false;
3157  EndDef = ChainDef;
3158  }
3159  auto *MP = cast<MemoryPhi>(EndDef);
3160  auto ReachableOperandPred = [&](const Use &U) {
3161  return ReachableEdges.count({MP->getIncomingBlock(U), MP->getBlock()});
3162  };
3163  auto FilteredPhiArgs =
3164  make_filter_range(MP->operands(), ReachableOperandPred);
3165  SmallVector<const Value *, 32> OperandList;
3166  llvm::copy(FilteredPhiArgs, std::back_inserter(OperandList));
3167  bool Okay = all_equal(OperandList);
3168  if (Okay)
3169  return singleReachablePHIPath(Visited, cast<MemoryAccess>(OperandList[0]),
3170  Second);
3171  return false;
3172 }
3173 
3174 // Verify the that the memory equivalence table makes sense relative to the
3175 // congruence classes. Note that this checking is not perfect, and is currently
3176 // subject to very rare false negatives. It is only useful for
3177 // testing/debugging.
3178 void NewGVN::verifyMemoryCongruency() const {
3179 #ifndef NDEBUG
3180  // Verify that the memory table equivalence and memory member set match
3181  for (const auto *CC : CongruenceClasses) {
3182  if (CC == TOPClass || CC->isDead())
3183  continue;
3184  if (CC->getStoreCount() != 0) {
3185  assert((CC->getStoredValue() || !isa<StoreInst>(CC->getLeader())) &&
3186  "Any class with a store as a leader should have a "
3187  "representative stored value");
3188  assert(CC->getMemoryLeader() &&
3189  "Any congruence class with a store should have a "
3190  "representative access");
3191  }
3192 
3193  if (CC->getMemoryLeader())
3194  assert(MemoryAccessToClass.lookup(CC->getMemoryLeader()) == CC &&
3195  "Representative MemoryAccess does not appear to be reverse "
3196  "mapped properly");
3197  for (const auto *M : CC->memory())
3198  assert(MemoryAccessToClass.lookup(M) == CC &&
3199  "Memory member does not appear to be reverse mapped properly");
3200  }
3201 
3202  // Anything equivalent in the MemoryAccess table should be in the same
3203  // congruence class.
3204 
3205  // Filter out the unreachable and trivially dead entries, because they may
3206  // never have been updated if the instructions were not processed.
3207  auto ReachableAccessPred =
3208  [&](const std::pair<const MemoryAccess *, CongruenceClass *> Pair) {
3209  bool Result = ReachableBlocks.count(Pair.first->getBlock());
3210  if (!Result || MSSA->isLiveOnEntryDef(Pair.first) ||
3211  MemoryToDFSNum(Pair.first) == 0)
3212  return false;
3213  if (auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
3214  return !isInstructionTriviallyDead(MemDef->getMemoryInst());
3215 
3216  // We could have phi nodes which operands are all trivially dead,
3217  // so we don't process them.
3218  if (auto *MemPHI = dyn_cast<MemoryPhi>(Pair.first)) {
3219  for (const auto &U : MemPHI->incoming_values()) {
3220  if (auto *I = dyn_cast<Instruction>(&*U)) {
3222  return true;
3223  }
3224  }
3225  return false;
3226  }
3227 
3228  return true;
3229  };
3230 
3231  auto Filtered = make_filter_range(MemoryAccessToClass, ReachableAccessPred);
3232  for (auto KV : Filtered) {
3233  if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
3234  auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second->getMemoryLeader());
3235  if (FirstMUD && SecondMUD) {
3237  assert((singleReachablePHIPath(VisitedMAS, FirstMUD, SecondMUD) ||
3238  ValueToClass.lookup(FirstMUD->getMemoryInst()) ==
3239  ValueToClass.lookup(SecondMUD->getMemoryInst())) &&
3240  "The instructions for these memory operations should have "
3241  "been in the same congruence class or reachable through"
3242  "a single argument phi");
3243  }
3244  } else if (auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {
3245  // We can only sanely verify that MemoryDefs in the operand list all have
3246  // the same class.
3247  auto ReachableOperandPred = [&](const Use &U) {
3248  return ReachableEdges.count(
3249  {FirstMP->getIncomingBlock(U), FirstMP->getBlock()}) &&
3250  isa<MemoryDef>(U);
3251 
3252  };
3253  // All arguments should in the same class, ignoring unreachable arguments
3254  auto FilteredPhiArgs =
3255  make_filter_range(FirstMP->operands(), ReachableOperandPred);
3257  std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
3258  std::back_inserter(PhiOpClasses), [&](const Use &U) {
3259  const MemoryDef *MD = cast<MemoryDef>(U);
3260  return ValueToClass.lookup(MD->getMemoryInst());
3261  });
3262  assert(all_equal(PhiOpClasses) &&
3263  "All MemoryPhi arguments should be in the same class");
3264  }
3265  }
3266 #endif
3267 }
3268 
3269 // Verify that the sparse propagation we did actually found the maximal fixpoint
3270 // We do this by storing the value to class mapping, touching all instructions,
3271 // and redoing the iteration to see if anything changed.
3272 void NewGVN::verifyIterationSettled(Function &F) {
3273 #ifndef NDEBUG
3274  LLVM_DEBUG(dbgs() << "Beginning iteration verification\n");
3275  if (DebugCounter::isCounterSet(VNCounter))
3276  DebugCounter::setCounterValue(VNCounter, StartingVNCounter);
3277 
3278  // Note that we have to store the actual classes, as we may change existing
3279  // classes during iteration. This is because our memory iteration propagation
3280  // is not perfect, and so may waste a little work. But it should generate
3281  // exactly the same congruence classes we have now, with different IDs.
3282  std::map<const Value *, CongruenceClass> BeforeIteration;
3283 
3284  for (auto &KV : ValueToClass) {
3285  if (auto *I = dyn_cast<Instruction>(KV.first))
3286  // Skip unused/dead instructions.
3287  if (InstrToDFSNum(I) == 0)
3288  continue;
3289  BeforeIteration.insert({KV.first, *KV.second});
3290  }
3291 
3292  TouchedInstructions.set();
3293  TouchedInstructions.reset(0);
3294  OpSafeForPHIOfOps.clear();
3295  iterateTouchedInstructions();
3297  EqualClasses;
3298  for (const auto &KV : ValueToClass) {
3299  if (auto *I = dyn_cast<Instruction>(KV.first))
3300  // Skip unused/dead instructions.
3301  if (InstrToDFSNum(I) == 0)
3302  continue;
3303  // We could sink these uses, but i think this adds a bit of clarity here as
3304  // to what we are comparing.
3305  auto *BeforeCC = &BeforeIteration.find(KV.first)->second;
3306  auto *AfterCC = KV.second;
3307  // Note that the classes can't change at this point, so we memoize the set
3308  // that are equal.
3309  if (!EqualClasses.count({BeforeCC, AfterCC})) {
3310  assert(BeforeCC->isEquivalentTo(AfterCC) &&
3311  "Value number changed after main loop completed!");
3312  EqualClasses.insert({BeforeCC, AfterCC});
3313  }
3314  }
3315 #endif
3316 }
3317 
3318 // Verify that for each store expression in the expression to class mapping,
3319 // only the latest appears, and multiple ones do not appear.
3320 // Because loads do not use the stored value when doing equality with stores,
3321 // if we don't erase the old store expressions from the table, a load can find
3322 // a no-longer valid StoreExpression.
3323 void NewGVN::verifyStoreExpressions() const {
3324 #ifndef NDEBUG
3325  // This is the only use of this, and it's not worth defining a complicated
3326  // densemapinfo hash/equality function for it.
3327  std::set<
3328  std::pair<const Value *,
3329  std::tuple<const Value *, const CongruenceClass *, Value *>>>
3330  StoreExpressionSet;
3331  for (const auto &KV : ExpressionToClass) {
3332  if (auto *SE = dyn_cast<StoreExpression>(KV.first)) {
3333  // Make sure a version that will conflict with loads is not already there
3334  auto Res = StoreExpressionSet.insert(
3335  {SE->getOperand(0), std::make_tuple(SE->getMemoryLeader(), KV.second,
3336  SE->getStoredValue())});
3337  bool Okay = Res.second;
3338  // It's okay to have the same expression already in there if it is
3339  // identical in nature.
3340  // This can happen when the leader of the stored value changes over time.
3341  if (!Okay)
3342  Okay = (std::get<1>(Res.first->second) == KV.second) &&
3343  (lookupOperandLeader(std::get<2>(Res.first->second)) ==
3344  lookupOperandLeader(SE->getStoredValue()));
3345  assert(Okay && "Stored expression conflict exists in expression table");
3346  auto *ValueExpr = ValueToExpression.lookup(SE->getStoreInst());
3347  assert(ValueExpr && ValueExpr->equals(*SE) &&
3348  "StoreExpression in ExpressionToClass is not latest "
3349  "StoreExpression for value");
3350  }
3351  }
3352 #endif
3353 }
3354 
3355 // This is the main value numbering loop, it iterates over the initial touched
3356 // instruction set, propagating value numbers, marking things touched, etc,
3357 // until the set of touched instructions is completely empty.
3358 void NewGVN::iterateTouchedInstructions() {
3359  uint64_t Iterations = 0;
3360  // Figure out where touchedinstructions starts
3361  int FirstInstr = TouchedInstructions.find_first();
3362  // Nothing set, nothing to iterate, just return.
3363  if (FirstInstr == -1)
3364  return;
3365  const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
3366  while (TouchedInstructions.any()) {
3367  ++Iterations;
3368  // Walk through all the instructions in all the blocks in RPO.
3369  // TODO: As we hit a new block, we should push and pop equalities into a
3370  // table lookupOperandLeader can use, to catch things PredicateInfo
3371  // might miss, like edge-only equivalences.
3372  for (unsigned InstrNum : TouchedInstructions.set_bits()) {
3373 
3374  // This instruction was found to be dead. We don't bother looking
3375  // at it again.
3376  if (InstrNum == 0) {
3377  TouchedInstructions.reset(InstrNum);
3378  continue;
3379  }
3380 
3381  Value *V = InstrFromDFSNum(InstrNum);
3382  const BasicBlock *CurrBlock = getBlockForValue(V);
3383 
3384  // If we hit a new block, do reachability processing.
3385  if (CurrBlock != LastBlock) {
3386  LastBlock = CurrBlock;
3387  bool BlockReachable = ReachableBlocks.count(CurrBlock);
3388  const auto &CurrInstRange = BlockInstRange.lookup(CurrBlock);
3389 
3390  // If it's not reachable, erase any touched instructions and move on.
3391  if (!BlockReachable) {
3392  TouchedInstructions.reset(CurrInstRange.first, CurrInstRange.second);
3393  LLVM_DEBUG(dbgs() << "Skipping instructions in block "
3394  << getBlockName(CurrBlock)
3395  << " because it is unreachable\n");
3396  continue;
3397  }
3398  updateProcessedCount(CurrBlock);
3399  }
3400  // Reset after processing (because we may mark ourselves as touched when
3401  // we propagate equalities).
3402  TouchedInstructions.reset(InstrNum);
3403 
3404  if (auto *MP = dyn_cast<MemoryPhi>(V)) {
3405  LLVM_DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n");
3406  valueNumberMemoryPhi(MP);
3407  } else if (auto *I = dyn_cast<Instruction>(V)) {
3408  valueNumberInstruction(I);
3409  } else {
3410  llvm_unreachable("Should have been a MemoryPhi or Instruction");
3411  }
3412  updateProcessedCount(V);
3413  }
3414  }
3415  NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations);
3416 }
3417 
3418 // This is the main transformation entry point.
3419 bool NewGVN::runGVN() {
3420  if (DebugCounter::isCounterSet(VNCounter))
3421  StartingVNCounter = DebugCounter::getCounterValue(VNCounter);
3422  bool Changed = false;
3423  NumFuncArgs = F.arg_size();
3424  MSSAWalker = MSSA->getWalker();
3425  SingletonDeadExpression = new (ExpressionAllocator) DeadExpression();
3426 
3427  // Count number of instructions for sizing of hash tables, and come
3428  // up with a global dfs numbering for instructions.
3429  unsigned ICount = 1;
3430  // Add an empty instruction to account for the fact that we start at 1
3431  DFSToInstr.emplace_back(nullptr);
3432  // Note: We want ideal RPO traversal of the blocks, which is not quite the
3433  // same as dominator tree order, particularly with regard whether backedges
3434  // get visited first or second, given a block with multiple successors.
3435  // If we visit in the wrong order, we will end up performing N times as many
3436  // iterations.
3437  // The dominator tree does guarantee that, for a given dom tree node, it's
3438  // parent must occur before it in the RPO ordering. Thus, we only need to sort
3439  // the siblings.
3441  unsigned Counter = 0;
3442  for (auto &B : RPOT) {
3443  auto *Node = DT->getNode(B);
3444  assert(Node && "RPO and Dominator tree should have same reachability");
3445  RPOOrdering[Node] = ++Counter;
3446  }
3447  // Sort dominator tree children arrays into RPO.
3448  for (auto &B : RPOT) {
3449  auto *Node = DT->getNode(B);
3450  if (Node->getNumChildren() > 1)
3451  llvm::sort(*Node, [&](const DomTreeNode *A, const DomTreeNode *B) {
3452  return RPOOrdering[A] < RPOOrdering[B];
3453  });
3454  }
3455 
3456  // Now a standard depth first ordering of the domtree is equivalent to RPO.
3457  for (auto *DTN : depth_first(DT->getRootNode())) {
3458  BasicBlock *B = DTN->getBlock();
3459  const auto &BlockRange = assignDFSNumbers(B, ICount);
3460  BlockInstRange.insert({B, BlockRange});
3461  ICount += BlockRange.second - BlockRange.first;
3462  }
3463  initializeCongruenceClasses(F);
3464 
3465  TouchedInstructions.resize(ICount);
3466  // Ensure we don't end up resizing the expressionToClass map, as
3467  // that can be quite expensive. At most, we have one expression per
3468  // instruction.
3469  ExpressionToClass.reserve(ICount);
3470 
3471  // Initialize the touched instructions to include the entry block.
3472  const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock());
3473  TouchedInstructions.set(InstRange.first, InstRange.second);
3474  LLVM_DEBUG(dbgs() << "Block " << getBlockName(&F.getEntryBlock())
3475  << " marked reachable\n");
3476  ReachableBlocks.insert(&F.getEntryBlock());
3477 
3478  iterateTouchedInstructions();
3479  verifyMemoryCongruency();
3480  verifyIterationSettled(F);
3481  verifyStoreExpressions();
3482 
3483  Changed |= eliminateInstructions(F);
3484 
3485  // Delete all instructions marked for deletion.
3486  for (Instruction *ToErase : InstructionsToErase) {
3487  if (!ToErase->use_empty())
3488  ToErase->replaceAllUsesWith(PoisonValue::get(ToErase->getType()));
3489 
3490  assert(ToErase->getParent() &&
3491  "BB containing ToErase deleted unexpectedly!");
3492  ToErase->eraseFromParent();
3493  }
3494  Changed |= !InstructionsToErase.empty();
3495 
3496  // Delete all unreachable blocks.
3497  auto UnreachableBlockPred = [&](const BasicBlock &BB) {
3498  return !ReachableBlocks.count(&BB);
3499  };
3500 
3501  for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
3502  LLVM_DEBUG(dbgs() << "We believe block " << getBlockName(&BB)
3503  << " is unreachable\n");
3504  deleteInstructionsInBlock(&BB);
3505  Changed = true;
3506  }
3507 
3508  cleanupTables();
3509  return Changed;
3510 }
3511 
3513  int DFSIn = 0;
3514  int DFSOut = 0;
3515  int LocalNum = 0;
3516 
3517  // Only one of Def and U will be set.
3518  // The bool in the Def tells us whether the Def is the stored value of a
3519  // store.
3521  Use *U = nullptr;
3522 
3523  bool operator<(const ValueDFS &Other) const {
3524  // It's not enough that any given field be less than - we have sets
3525  // of fields that need to be evaluated together to give a proper ordering.
3526  // For example, if you have;
3527  // DFS (1, 3)
3528  // Val 0
3529  // DFS (1, 2)
3530  // Val 50
3531  // We want the second to be less than the first, but if we just go field
3532  // by field, we will get to Val 0 < Val 50 and say the first is less than
3533  // the second. We only want it to be less than if the DFS orders are equal.
3534  //
3535  // Each LLVM instruction only produces one value, and thus the lowest-level
3536  // differentiator that really matters for the stack (and what we use as as a
3537  // replacement) is the local dfs number.
3538  // Everything else in the structure is instruction level, and only affects
3539  // the order in which we will replace operands of a given instruction.
3540  //
3541  // For a given instruction (IE things with equal dfsin, dfsout, localnum),
3542  // the order of replacement of uses does not matter.
3543  // IE given,
3544  // a = 5
3545  // b = a + a
3546  // When you hit b, you will have two valuedfs with the same dfsin, out, and
3547  // localnum.
3548  // The .val will be the same as well.
3549  // The .u's will be different.
3550  // You will replace both, and it does not matter what order you replace them
3551  // in (IE whether you replace operand 2, then operand 1, or operand 1, then
3552  // operand 2).
3553  // Similarly for the case of same dfsin, dfsout, localnum, but different
3554  // .val's
3555  // a = 5
3556  // b = 6
3557  // c = a + b
3558  // in c, we will a valuedfs for a, and one for b,with everything the same
3559  // but .val and .u.
3560  // It does not matter what order we replace these operands in.
3561  // You will always end up with the same IR, and this is guaranteed.
3562  return std::tie(DFSIn, DFSOut, LocalNum, Def, U) <
3563  std::tie(Other.DFSIn, Other.DFSOut, Other.LocalNum, Other.Def,
3564  Other.U);
3565  }
3566 };
3567 
3568 // This function converts the set of members for a congruence class from values,
3569 // to sets of defs and uses with associated DFS info. The total number of
3570 // reachable uses for each value is stored in UseCount, and instructions that
3571 // seem
3572 // dead (have no non-dead uses) are stored in ProbablyDead.
3573 void NewGVN::convertClassToDFSOrdered(
3574  const CongruenceClass &Dense, SmallVectorImpl<ValueDFS> &DFSOrderedSet,
3576  SmallPtrSetImpl<Instruction *> &ProbablyDead) const {
3577  for (auto *D : Dense) {
3578  // First add the value.
3579  BasicBlock *BB = getBlockForValue(D);
3580  // Constants are handled prior to ever calling this function, so
3581  // we should only be left with instructions as members.
3582  assert(BB && "Should have figured out a basic block for value");
3583  ValueDFS VDDef;
3584  DomTreeNode *DomNode = DT->getNode(BB);
3585  VDDef.DFSIn = DomNode->getDFSNumIn();
3586  VDDef.DFSOut = DomNode->getDFSNumOut();
3587  // If it's a store, use the leader of the value operand, if it's always
3588  // available, or the value operand. TODO: We could do dominance checks to
3589  // find a dominating leader, but not worth it ATM.
3590  if (auto *SI = dyn_cast<StoreInst>(D)) {
3591  auto Leader = lookupOperandLeader(SI->getValueOperand());
3592  if (alwaysAvailable(Leader)) {
3593  VDDef.Def.setPointer(Leader);
3594  } else {
3595  VDDef.Def.setPointer(SI->getValueOperand());
3596  VDDef.Def.setInt(true);
3597  }
3598  } else {
3599  VDDef.Def.setPointer(D);
3600  }
3601  assert(isa<Instruction>(D) &&
3602  "The dense set member should always be an instruction");
3603  Instruction *Def = cast<Instruction>(D);
3604  VDDef.LocalNum = InstrToDFSNum(D);
3605  DFSOrderedSet.push_back(VDDef);
3606  // If there is a phi node equivalent, add it
3607  if (auto *PN = RealToTemp.lookup(Def)) {
3608  auto *PHIE =
3609  dyn_cast_or_null<PHIExpression>(ValueToExpression.lookup(Def));
3610  if (PHIE) {
3611  VDDef.Def.setInt(false);
3612  VDDef.Def.setPointer(PN);
3613  VDDef.LocalNum = 0;
3614  DFSOrderedSet.push_back(VDDef);
3615  }
3616  }
3617 
3618  unsigned int UseCount = 0;
3619  // Now add the uses.
3620  for (auto &U : Def->uses()) {
3621  if (auto *I = dyn_cast<Instruction>(U.getUser())) {
3622  // Don't try to replace into dead uses
3623  if (InstructionsToErase.count(I))
3624  continue;
3625  ValueDFS VDUse;
3626  // Put the phi node uses in the incoming block.
3627  BasicBlock *IBlock;
3628  if (auto *P = dyn_cast<PHINode>(I)) {
3629  IBlock = P->getIncomingBlock(U);
3630  // Make phi node users appear last in the incoming block
3631  // they are from.
3632  VDUse.LocalNum = InstrDFS.size() + 1;
3633  } else {
3634  IBlock = getBlockForValue(I);
3635  VDUse.LocalNum = InstrToDFSNum(I);
3636  }
3637 
3638  // Skip uses in unreachable blocks, as we're going
3639  // to delete them.
3640  if (!ReachableBlocks.contains(IBlock))
3641  continue;
3642 
3643  DomTreeNode *DomNode = DT->getNode(IBlock);
3644  VDUse.DFSIn = DomNode->getDFSNumIn();
3645  VDUse.DFSOut = DomNode->getDFSNumOut();
3646  VDUse.U = &U;
3647  ++UseCount;
3648  DFSOrderedSet.emplace_back(VDUse);
3649  }
3650  }
3651 
3652  // If there are no uses, it's probably dead (but it may have side-effects,
3653  // so not definitely dead. Otherwise, store the number of uses so we can
3654  // track if it becomes dead later).
3655  if (UseCount == 0)
3656  ProbablyDead.insert(Def);
3657  else
3658  UseCounts[Def] = UseCount;
3659  }
3660 }
3661 
3662 // This function converts the set of members for a congruence class from values,
3663 // to the set of defs for loads and stores, with associated DFS info.
3664 void NewGVN::convertClassToLoadsAndStores(
3665  const CongruenceClass &Dense,
3666  SmallVectorImpl<ValueDFS> &LoadsAndStores) const {
3667  for (auto *D : Dense) {
3668  if (!isa<LoadInst>(D) && !isa<StoreInst>(D))
3669  continue;
3670 
3671  BasicBlock *BB = getBlockForValue(D);
3672  ValueDFS VD;
3673  DomTreeNode *DomNode = DT->getNode(BB);
3674  VD.DFSIn = DomNode->getDFSNumIn();
3675  VD.DFSOut = DomNode->getDFSNumOut();
3676  VD.Def.setPointer(D);
3677 
3678  // If it's an instruction, use the real local dfs number.
3679  if (auto *I = dyn_cast<Instruction>(D))
3680  VD.LocalNum = InstrToDFSNum(I);
3681  else
3682  llvm_unreachable("Should have been an instruction");
3683 
3684  LoadsAndStores.emplace_back(VD);
3685  }
3686 }
3687 
3690  I->replaceAllUsesWith(Repl);
3691 }
3692 
3693 void NewGVN::deleteInstructionsInBlock(BasicBlock *BB) {
3694  LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << *BB);
3695  ++NumGVNBlocksDeleted;
3696 
3697  // Delete the instructions backwards, as it has a reduced likelihood of having
3698  // to update as many def-use and use-def chains. Start after the terminator.
3699  auto StartPoint = BB->rbegin();
3700  ++StartPoint;
3701  // Note that we explicitly recalculate BB->rend() on each iteration,
3702  // as it may change when we remove the first instruction.
3703  for (BasicBlock::reverse_iterator I(StartPoint); I != BB->rend();) {
3704  Instruction &Inst = *I++;
3705  if (!Inst.use_empty())
3707  if (isa<LandingPadInst>(Inst))
3708  continue;
3709  salvageKnowledge(&Inst, AC);
3710 
3711  Inst.eraseFromParent();
3712  ++NumGVNInstrDeleted;
3713  }
3714  // Now insert something that simplifycfg will turn into an unreachable.
3715  Type *Int8Ty = Type::getInt8Ty(BB->getContext());
3716  new StoreInst(PoisonValue::get(Int8Ty),
3718  BB->getTerminator());
3719 }
3720 
3721 void NewGVN::markInstructionForDeletion(Instruction *I) {
3722  LLVM_DEBUG(dbgs() << "Marking " << *I << " for deletion\n");
3723  InstructionsToErase.insert(I);
3724 }
3725 
3726 void NewGVN::replaceInstruction(Instruction *I, Value *V) {
3727  LLVM_DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n");
3729  // We save the actual erasing to avoid invalidating memory
3730  // dependencies until we are done with everything.
3731  markInstructionForDeletion(I);
3732 }
3733 
3734 namespace {
3735 
3736 // This is a stack that contains both the value and dfs info of where
3737 // that value is valid.
3738 class ValueDFSStack {
3739 public:
3740  Value *back() const { return ValueStack.back(); }
3741  std::pair<int, int> dfs_back() const { return DFSStack.back(); }
3742 
3743  void push_back(Value *V, int DFSIn, int DFSOut) {
3744  ValueStack.emplace_back(V);
3745  DFSStack.emplace_back(DFSIn, DFSOut);
3746  }
3747 
3748  bool empty() const { return DFSStack.empty(); }
3749 
3750  bool isInScope(int DFSIn, int DFSOut) const {
3751  if (empty())
3752  return false;
3753  return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
3754  }
3755 
3756  void popUntilDFSScope(int DFSIn, int DFSOut) {
3757 
3758  // These two should always be in sync at this point.
3759  assert(ValueStack.size() == DFSStack.size() &&
3760  "Mismatch between ValueStack and DFSStack");
3761  while (
3762  !DFSStack.empty() &&
3763  !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
3764  DFSStack.pop_back();
3765  ValueStack.pop_back();
3766  }
3767  }
3768 
3769 private:
3770  SmallVector<Value *, 8> ValueStack;
3771  SmallVector<std::pair<int, int>, 8> DFSStack;
3772 };
3773 
3774 } // end anonymous namespace
3775 
3776 // Given an expression, get the congruence class for it.
3777 CongruenceClass *NewGVN::getClassForExpression(const Expression *E) const {
3778  if (auto *VE = dyn_cast<VariableExpression>(E))
3779  return ValueToClass.lookup(VE->getVariableValue());
3780  else if (isa<DeadExpression>(E))
3781  return TOPClass;
3782  return ExpressionToClass.lookup(E);
3783 }
3784 
3785 // Given a value and a basic block we are trying to see if it is available in,
3786 // see if the value has a leader available in that block.
3787 Value *NewGVN::findPHIOfOpsLeader(const Expression *E,
3788  const Instruction *OrigInst,
3789  const BasicBlock *BB) const {
3790  // It would already be constant if we could make it constant
3791  if (auto *CE = dyn_cast<ConstantExpression>(E))
3792  return CE->getConstantValue();
3793  if (auto *VE = dyn_cast<VariableExpression>(E)) {
3794  auto *V = VE->getVariableValue();
3795  if (alwaysAvailable(V) || DT->dominates(getBlockForValue(V), BB))
3796  return VE->getVariableValue();
3797  }
3798 
3799  auto *CC = getClassForExpression(E);
3800  if (!CC)
3801  return nullptr;
3802  if (alwaysAvailable(CC->getLeader()))
3803  return CC->getLeader();
3804 
3805  for (auto *Member : *CC) {
3806  auto *MemberInst = dyn_cast<Instruction>(Member);
3807  if (MemberInst == OrigInst)
3808  continue;
3809  // Anything that isn't an instruction is always available.
3810  if (!MemberInst)
3811  return Member;
3812  if (DT->dominates(getBlockForValue(MemberInst), BB))
3813  return Member;
3814  }
3815  return nullptr;
3816 }
3817 
3818 bool NewGVN::eliminateInstructions(Function &F) {
3819  // This is a non-standard eliminator. The normal way to eliminate is
3820  // to walk the dominator tree in order, keeping track of available
3821  // values, and eliminating them. However, this is mildly
3822  // pointless. It requires doing lookups on every instruction,
3823  // regardless of whether we will ever eliminate it. For
3824  // instructions part of most singleton congruence classes, we know we
3825  // will never eliminate them.
3826 
3827  // Instead, this eliminator looks at the congruence classes directly, sorts
3828  // them into a DFS ordering of the dominator tree, and then we just
3829  // perform elimination straight on the sets by walking the congruence
3830  // class member uses in order, and eliminate the ones dominated by the
3831  // last member. This is worst case O(E log E) where E = number of
3832  // instructions in a single congruence class. In theory, this is all
3833  // instructions. In practice, it is much faster, as most instructions are
3834  // either in singleton congruence classes or can't possibly be eliminated
3835  // anyway (if there are no overlapping DFS ranges in class).
3836  // When we find something not dominated, it becomes the new leader
3837  // for elimination purposes.
3838  // TODO: If we wanted to be faster, We could remove any members with no
3839  // overlapping ranges while sorting, as we will never eliminate anything
3840  // with those members, as they don't dominate anything else in our set.
3841 
3842  bool AnythingReplaced = false;
3843 
3844  // Since we are going to walk the domtree anyway, and we can't guarantee the
3845  // DFS numbers are updated, we compute some ourselves.
3846  DT->updateDFSNumbers();
3847 
3848  // Go through all of our phi nodes, and kill the arguments associated with
3849  // unreachable edges.
3850  auto ReplaceUnreachablePHIArgs = [&](PHINode *PHI, BasicBlock *BB) {
3851  for (auto &Operand : PHI->incoming_values())
3852  if (!ReachableEdges.count({PHI->getIncomingBlock(Operand), BB})) {
3853  LLVM_DEBUG(dbgs() << "Replacing incoming value of " << PHI
3854  << " for block "
3855  << getBlockName(PHI->getIncomingBlock(Operand))
3856  << " with poison due to it being unreachable\n");
3857  Operand.set(PoisonValue::get(PHI->getType()));
3858  }
3859  };
3860  // Replace unreachable phi arguments.
3861  // At this point, RevisitOnReachabilityChange only contains:
3862  //
3863  // 1. PHIs
3864  // 2. Temporaries that will convert to PHIs
3865  // 3. Operations that are affected by an unreachable edge but do not fit into
3866  // 1 or 2 (rare).
3867  // So it is a slight overshoot of what we want. We could make it exact by
3868  // using two SparseBitVectors per block.
3869  DenseMap<const BasicBlock *, unsigned> ReachablePredCount;
3870  for (auto &KV : ReachableEdges)
3871  ReachablePredCount[KV.getEnd()]++;
3872  for (auto &BBPair : RevisitOnReachabilityChange) {
3873  for (auto InstNum : BBPair.second) {
3874  auto *Inst = InstrFromDFSNum(InstNum);
3875  auto *PHI = dyn_cast<PHINode>(Inst);
3876  PHI = PHI ? PHI : dyn_cast_or_null<PHINode>(RealToTemp.lookup(Inst));
3877  if (!PHI)
3878  continue;
3879  auto *BB = BBPair.first;
3880  if (ReachablePredCount.lookup(BB) != PHI->getNumIncomingValues())
3881  ReplaceUnreachablePHIArgs(PHI, BB);
3882  }
3883  }
3884 
3885  // Map to store the use counts
3887  for (auto *CC : reverse(CongruenceClasses)) {
3888  LLVM_DEBUG(dbgs() << "Eliminating in congruence class " << CC->getID()
3889  << "\n");
3890  // Track the equivalent store info so we can decide whether to try
3891  // dead store elimination.
3892  SmallVector<ValueDFS, 8> PossibleDeadStores;
3893  SmallPtrSet<Instruction *, 8> ProbablyDead;
3894  if (CC->isDead() || CC->empty())
3895  continue;
3896  // Everything still in the TOP class is unreachable or dead.
3897  if (CC == TOPClass) {
3898  for (auto *M : *CC) {
3899  auto *VTE = ValueToExpression.lookup(M);
3900  if (VTE && isa<DeadExpression>(VTE))
3901  markInstructionForDeletion(cast<Instruction>(M));
3902  assert((!ReachableBlocks.count(cast<Instruction>(M)->getParent()) ||
3903  InstructionsToErase.count(cast<Instruction>(M))) &&
3904  "Everything in TOP should be unreachable or dead at this "
3905  "point");
3906  }
3907  continue;
3908  }
3909 
3910  assert(CC->getLeader() && "We should have had a leader");
3911  // If this is a leader that is always available, and it's a
3912  // constant or has no equivalences, just replace everything with
3913  // it. We then update the congruence class with whatever members
3914  // are left.
3915  Value *Leader =
3916  CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
3917  if (alwaysAvailable(Leader)) {
3918  CongruenceClass::MemberSet MembersLeft;
3919  for (auto *M : *CC) {
3920  Value *Member = M;
3921  // Void things have no uses we can replace.
3922  if (Member == Leader || !isa<Instruction>(Member) ||
3923  Member->getType()->isVoidTy()) {
3924  MembersLeft.insert(Member);
3925  continue;
3926  }
3927  LLVM_DEBUG(dbgs() << "Found replacement " << *(Leader) << " for "
3928  << *Member << "\n");
3929  auto *I = cast<Instruction>(Member);
3930  assert(Leader != I && "About to accidentally remove our leader");
3931  replaceInstruction(I, Leader);
3932  AnythingReplaced = true;
3933  }
3934  CC->swap(MembersLeft);
3935  } else {
3936  // If this is a singleton, we can skip it.
3937  if (CC->size() != 1 || RealToTemp.count(Leader)) {
3938  // This is a stack because equality replacement/etc may place
3939  // constants in the middle of the member list, and we want to use
3940  // those constant values in preference to the current leader, over
3941  // the scope of those constants.
3942  ValueDFSStack EliminationStack;
3943 
3944  // Convert the members to DFS ordered sets and then merge them.
3945  SmallVector<ValueDFS, 8> DFSOrderedSet;
3946  convertClassToDFSOrdered(*CC, DFSOrderedSet, UseCounts, ProbablyDead);
3947 
3948  // Sort the whole thing.
3949  llvm::sort(DFSOrderedSet);
3950  for (auto &VD : DFSOrderedSet) {
3951  int MemberDFSIn = VD.DFSIn;
3952  int MemberDFSOut = VD.DFSOut;
3953  Value *Def = VD.Def.getPointer();
3954  bool FromStore = VD.Def.getInt();
3955  Use *U = VD.U;
3956  // We ignore void things because we can't get a value from them.
3957  if (Def && Def->getType()->isVoidTy())
3958  continue;
3959  auto *DefInst = dyn_cast_or_null<Instruction>(Def);
3960  if (DefInst && AllTempInstructions.count(DefInst)) {
3961  auto *PN = cast<PHINode>(DefInst);
3962 
3963  // If this is a value phi and that's the expression we used, insert
3964  // it into the program
3965  // remove from temp instruction list.
3966  AllTempInstructions.erase(PN);
3967  auto *DefBlock = getBlockForValue(Def);
3968  LLVM_DEBUG(dbgs() << "Inserting fully real phi of ops" << *Def
3969  << " into block "
3970  << getBlockName(getBlockForValue(Def)) << "\n");
3971  PN->insertBefore(&DefBlock->front());
3972  Def = PN;
3973  NumGVNPHIOfOpsEliminations++;
3974  }
3975 
3976  if (EliminationStack.empty()) {
3977  LLVM_DEBUG(dbgs() << "Elimination Stack is empty\n");
3978  } else {
3979  LLVM_DEBUG(dbgs() << "Elimination Stack Top DFS numbers are ("
3980  << EliminationStack.dfs_back().first << ","
3981  << EliminationStack.dfs_back().second << ")\n");
3982  }
3983 
3984  LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << MemberDFSIn << ","
3985  << MemberDFSOut << ")\n");
3986  // First, we see if we are out of scope or empty. If so,
3987  // and there equivalences, we try to replace the top of
3988  // stack with equivalences (if it's on the stack, it must
3989  // not have been eliminated yet).
3990  // Then we synchronize to our current scope, by
3991  // popping until we are back within a DFS scope that
3992  // dominates the current member.
3993  // Then, what happens depends on a few factors
3994  // If the stack is now empty, we need to push
3995  // If we have a constant or a local equivalence we want to
3996  // start using, we also push.
3997  // Otherwise, we walk along, processing members who are
3998  // dominated by this scope, and eliminate them.
3999  bool ShouldPush = Def && EliminationStack.empty();
4000  bool OutOfScope =
4001  !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
4002 
4003  if (OutOfScope || ShouldPush) {
4004  // Sync to our current scope.
4005  EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4006  bool ShouldPush = Def && EliminationStack.empty();
4007  if (ShouldPush) {
4008  EliminationStack.push_back(Def, MemberDFSIn, MemberDFSOut);
4009  }
4010  }
4011 
4012  // Skip the Def's, we only want to eliminate on their uses. But mark
4013  // dominated defs as dead.
4014  if (Def) {
4015  // For anything in this case, what and how we value number
4016  // guarantees that any side-effets that would have occurred (ie
4017  // throwing, etc) can be proven to either still occur (because it's
4018  // dominated by something that has the same side-effects), or never
4019  // occur. Otherwise, we would not have been able to prove it value
4020  // equivalent to something else. For these things, we can just mark
4021  // it all dead. Note that this is different from the "ProbablyDead"
4022  // set, which may not be dominated by anything, and thus, are only
4023  // easy to prove dead if they are also side-effect free. Note that
4024  // because stores are put in terms of the stored value, we skip
4025  // stored values here. If the stored value is really dead, it will
4026  // still be marked for deletion when we process it in its own class.
4027  if (!EliminationStack.empty() && Def != EliminationStack.back() &&
4028  isa<Instruction>(Def) && !FromStore)
4029  markInstructionForDeletion(cast<Instruction>(Def));
4030  continue;
4031  }
4032  // At this point, we know it is a Use we are trying to possibly
4033  // replace.
4034 
4035  assert(isa<Instruction>(U->get()) &&
4036  "Current def should have been an instruction");
4037  assert(isa<Instruction>(U->getUser()) &&
4038  "Current user should have been an instruction");
4039 
4040  // If the thing we are replacing into is already marked to be dead,
4041  // this use is dead. Note that this is true regardless of whether
4042  // we have anything dominating the use or not. We do this here
4043  // because we are already walking all the uses anyway.
4044  Instruction *InstUse = cast<Instruction>(U->getUser());
4045  if (InstructionsToErase.count(InstUse)) {
4046  auto &UseCount = UseCounts[U->get()];
4047  if (--UseCount == 0) {
4048  ProbablyDead.insert(cast<Instruction>(U->get()));
4049  }
4050  }
4051 
4052  // If we get to this point, and the stack is empty we must have a use
4053  // with nothing we can use to eliminate this use, so just skip it.
4054  if (EliminationStack.empty())
4055  continue;
4056 
4057  Value *DominatingLeader = EliminationStack.back();
4058 
4059  auto *II = dyn_cast<IntrinsicInst>(DominatingLeader);
4060  bool isSSACopy = II && II->getIntrinsicID() == Intrinsic::ssa_copy;
4061  if (isSSACopy)
4062  DominatingLeader = II->getOperand(0);
4063 
4064  // Don't replace our existing users with ourselves.
4065  if (U->get() == DominatingLeader)
4066  continue;
4067  LLVM_DEBUG(dbgs()
4068  << "Found replacement " << *DominatingLeader << " for "
4069  << *U->get() << " in " << *(U->getUser()) << "\n");
4070 
4071  // If we replaced something in an instruction, handle the patching of
4072  // metadata. Skip this if we are replacing predicateinfo with its
4073  // original operand, as we already know we can just drop it.
4074  auto *ReplacedInst = cast<Instruction>(U->get());
4075  auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
4076  if (!PI || DominatingLeader != PI->OriginalOp)
4077  patchReplacementInstruction(ReplacedInst, DominatingLeader);
4078  U->set(DominatingLeader);
4079  // This is now a use of the dominating leader, which means if the
4080  // dominating leader was dead, it's now live!
4081  auto &LeaderUseCount = UseCounts[DominatingLeader];
4082  // It's about to be alive again.
4083  if (LeaderUseCount == 0 && isa<Instruction>(DominatingLeader))
4084  ProbablyDead.erase(cast<Instruction>(DominatingLeader));
4085  // For copy instructions, we use their operand as a leader,
4086  // which means we remove a user of the copy and it may become dead.
4087  if (isSSACopy) {
4088  unsigned &IIUseCount = UseCounts[II];
4089  if (--IIUseCount == 0)
4090  ProbablyDead.insert(II);
4091  }
4092  ++LeaderUseCount;
4093  AnythingReplaced = true;
4094  }
4095  }
4096  }
4097 
4098  // At this point, anything still in the ProbablyDead set is actually dead if
4099  // would be trivially dead.
4100  for (auto *I : ProbablyDead)
4102  markInstructionForDeletion(I);
4103 
4104  // Cleanup the congruence class.
4105  CongruenceClass::MemberSet MembersLeft;
4106  for (auto *Member : *CC)
4107  if (!isa<Instruction>(Member) ||
4108  !InstructionsToErase.count(cast<Instruction>(Member)))
4109  MembersLeft.insert(Member);
4110  CC->swap(MembersLeft);
4111 
4112  // If we have possible dead stores to look at, try to eliminate them.
4113  if (CC->getStoreCount() > 0) {
4114  convertClassToLoadsAndStores(*CC, PossibleDeadStores);
4115  llvm::sort(PossibleDeadStores);
4116  ValueDFSStack EliminationStack;
4117  for (auto &VD : PossibleDeadStores) {
4118  int MemberDFSIn = VD.DFSIn;
4119  int MemberDFSOut = VD.DFSOut;
4120  Instruction *Member = cast<Instruction>(VD.Def.getPointer());
4121  if (EliminationStack.empty() ||
4122  !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) {
4123  // Sync to our current scope.
4124  EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4125  if (EliminationStack.empty()) {
4126  EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
4127  continue;
4128  }
4129  }
4130  // We already did load elimination, so nothing to do here.
4131  if (isa<LoadInst>(Member))
4132  continue;
4133  assert(!EliminationStack.empty());
4134  Instruction *Leader = cast<Instruction>(EliminationStack.back());
4135  (void)Leader;
4136  assert(DT->dominates(Leader->getParent(), Member->getParent()));
4137  // Member is dominater by Leader, and thus dead
4138  LLVM_DEBUG(dbgs() << "Marking dead store " << *Member
4139  << " that is dominated by " << *Leader << "\n");
4140  markInstructionForDeletion(Member);
4141  CC->erase(Member);
4142  ++NumGVNDeadStores;
4143  }
4144  }
4145  }
4146  return AnythingReplaced;
4147 }
4148 
4149 // This function provides global ranking of operations so that we can place them
4150 // in a canonical order. Note that rank alone is not necessarily enough for a
4151 // complete ordering, as constants all have the same rank. However, generally,
4152 // we will simplify an operation with all constants so that it doesn't matter
4153 // what order they appear in.
4154 unsigned int NewGVN::getRank(const Value *V) const {
4155  // Prefer constants to undef to anything else
4156  // Undef is a constant, have to check it first.
4157  // Prefer poison to undef as it's less defined.
4158  // Prefer smaller constants to constantexprs
4159  // Note that the order here matters because of class inheritance
4160  if (isa<ConstantExpr>(V))
4161  return 3;
4162  if (isa<PoisonValue>(V))
4163  return 1;
4164  if (isa<UndefValue>(V))
4165  return 2;
4166  if (isa<Constant>(V))
4167  return 0;
4168  if (auto *A = dyn_cast<Argument>(V))
4169  return 4 + A->getArgNo();
4170 
4171  // Need to shift the instruction DFS by number of arguments + 5 to account for
4172  // the constant and argument ranking above.
4173  unsigned Result = InstrToDFSNum(V);
4174  if (Result > 0)
4175  return 5 + NumFuncArgs + Result;
4176  // Unreachable or something else, just return a really large number.
4177  return ~0;
4178 }
4179 
4180 // This is a function that says whether two commutative operations should
4181 // have their order swapped when canonicalizing.
4182 bool NewGVN::shouldSwapOperands(const Value *A, const Value *B) const {
4183  // Because we only care about a total ordering, and don't rewrite expressions
4184  // in this order, we order by rank, which will give a strict weak ordering to
4185  // everything but constants, and then we order by pointer address.
4186  return std::make_pair(getRank(A), A) > std::make_pair(getRank(B), B);
4187 }
4188 
4189 bool NewGVN::shouldSwapOperandsForIntrinsic(const Value *A, const Value *B,
4190  const IntrinsicInst *I) const {
4191  auto LookupResult = IntrinsicInstPred.find(I);
4192  if (shouldSwapOperands(A, B)) {
4193  if (LookupResult == IntrinsicInstPred.end())
4194  IntrinsicInstPred.insert({I, B});
4195  else
4196  LookupResult->second = B;
4197  return true;
4198  }
4199 
4200  if (LookupResult != IntrinsicInstPred.end()) {
4201  auto *SeenPredicate = LookupResult->second;
4202  if (SeenPredicate) {
4203  if (SeenPredicate == B)
4204  return true;
4205  else
4206  LookupResult->second = nullptr;
4207  }
4208  }
4209  return false;
4210 }
4211 
4212 namespace {
4213 
4214 class NewGVNLegacyPass : public FunctionPass {
4215 public:
4216  // Pass identification, replacement for typeid.
4217  static char ID;
4218 
4219  NewGVNLegacyPass() : FunctionPass(ID) {
4221  }
4222 
4223  bool runOnFunction(Function &F) override;
4224 
4225 private:
4226  void getAnalysisUsage(AnalysisUsage &AU) const override {
4234  }
4235 };
4236 
4237 } // end anonymous namespace
4238 
4240  if (skipFunction(F))
4241  return false;
4242  return NewGVN(F, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
4243  &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
4244  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
4245  &getAnalysis<AAResultsWrapperPass>().getAAResults(),
4246  &getAnalysis<MemorySSAWrapperPass>().getMSSA(),
4247  F.getParent()->getDataLayout())
4248  .runGVN();
4249 }
4250 
4251 char NewGVNLegacyPass::ID = 0;
4252 
4253 INITIALIZE_PASS_BEGIN(NewGVNLegacyPass, "newgvn", "Global Value Numbering",
4254  false, false)
4261 INITIALIZE_PASS_END(NewGVNLegacyPass, "newgvn", "Global Value Numbering", false,
4262  false)
4263 
4264 // createGVNPass - The public interface to this file.
4265 FunctionPass *llvm::createNewGVNPass() { return new NewGVNLegacyPass(); }
4266 
4268  // Apparently the order in which we get these results matter for
4269  // the old GVN (see Chandler's comment in GVN.cpp). I'll keep
4270  // the same order here, just in case.
4271  auto &AC = AM.getResult<AssumptionAnalysis>(F);
4272  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
4273  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
4274  auto &AA = AM.getResult<AAManager>(F);
4275  auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
4276  bool Changed =
4277  NewGVN(F, &DT, &AC, &TLI, &AA, &MSSA, F.getParent()->getDataLayout())
4278  .runGVN();
4279  if (!Changed)
4280  return PreservedAnalyses::all();
4281  PreservedAnalyses PA;
4283  return PA;
4284 }
i
i
Definition: README.txt:29
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::VNCoercion::analyzeLoadFromClobberingMemInst
int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr, MemIntrinsic *DepMI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the memory int...
Definition: VNCoercion.cpp:349
set
We currently generate a but we really shouldn eax ecx xorl edx divl ecx eax divl ecx movl eax ret A similar code sequence works for division We currently compile i32 v2 eax eax jo LBB1_2 atomic and others It is also currently not done for read modify write instructions It is also current not done if the OF or CF flags are needed The shift operators have the complication that when the shift count is EFLAGS is not set
Definition: README.txt:1277
AssumptionCache.h
patchAndReplaceAllUsesWith
static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl)
Definition: NewGVN.cpp:3688
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:876
llvm::ValueDFS::LocalNum
unsigned int LocalNum
Definition: PredicateInfo.cpp:96
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
Definition: Instruction.cpp:814
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:850
llvm::simplifyGEPInst
Value * simplifyGEPInst(Type *SrcTy, Value *Ptr, ArrayRef< Value * > Indices, bool InBounds, const SimplifyQuery &Q)
Given operands for a GetElementPtrInst, fold the result or return null.
Definition: InstructionSimplify.cpp:4801
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::sys::path::const_iterator::end
friend const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
NewGVN::ValueDFS
Definition: NewGVN.cpp:3512
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::set_is_subset
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
Definition: SetOperations.h:72
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:379
getBlockName
static std::string getBlockName(const BasicBlock *B)
Definition: NewGVN.cpp:932
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::BumpPtrAllocatorImpl::Reset
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:123
PredicateInfo.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::User::operands
op_range operands()
Definition: User.h:242
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
IntrinsicInst.h
llvm::SimplifyQuery
Definition: InstructionSimplify.h:93
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
llvm::pdb::PDB_DataKind::Member
@ Member
Scalar.h
SetOperations.h
T
llvm::Function
Definition: Function.h:60
llvm::optimized_def_chain
iterator_range< def_chain_iterator< T, true > > optimized_def_chain(T MA)
Definition: MemorySSA.h:1342
llvm::DenseMapBase::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:344
llvm::LocalNum
LocalNum
Definition: PredicateInfo.cpp:81
llvm::BitVector::clear
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:328
llvm::DenseMapInfo< const Expression * >::getTombstoneKey
static const Expression * getTombstoneKey()
Definition: NewGVN.cpp:451
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
isCopyOfAPHI
static bool isCopyOfAPHI(const Value *V)
Definition: NewGVN.cpp:987
Statistic.h
llvm::detail::DenseSetImpl::find
iterator find(const_arg_type_t< ValueT > V)
Definition: DenseSet.h:179
ErrorHandling.h
Allocator.h
llvm::BitVector::set_bits
iterator_range< const_set_bits_iterator > set_bits() const
Definition: BitVector.h:133
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:834
ValueTracking.h
Local.h
llvm::ValueDFS::DFSIn
int DFSIn
Definition: PredicateInfo.cpp:94
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
alwaysAvailable
static bool alwaysAvailable(Value *V)
Definition: NewGVN.cpp:1005
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::PatternMatch::m_Br
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
Definition: PatternMatch.h:1731
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
NL
#define NL
Definition: DetailedRecordsBackend.cpp:31
DenseMap.h
MemoryBuiltins.h
llvm::BitVector::resize
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:334
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::MemorySSA::getLiveOnEntryDef
MemoryAccess * getLiveOnEntryDef() const
Definition: MemorySSA.h:741
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::BasicBlockEdge
Definition: Dominators.h:98
llvm::AMDGPU::VOPD::Component
Component
Definition: AMDGPUBaseInfo.h:520
llvm::copy
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1836
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::Optional
Definition: APInt.h:33
llvm::DenseMapBase::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:80
llvm::SmallPtrSet< const Value *, 8 >
llvm::GVNExpression::StoreExpression::~StoreExpression
~StoreExpression() override
Hashing.h
llvm::MemoryPhi
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:479
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
getCopyOf
static Value * getCopyOf(const Value *V)
Definition: NewGVN.cpp:975
equalsLoadStoreHelper
static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS)
Definition: NewGVN.cpp:904
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:261
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:237
ConstantFolding.h
Use.h
llvm::DebugCounter::getCounterValue
static int64_t getCounterValue(unsigned ID)
Definition: DebugCounter.h:105
llvm::GVNExpression::CallExpression::~CallExpression
~CallExpression() override
llvm::MemoryPhi::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned I) const
Return incoming basic block number i.
Definition: MemorySSA.h:540
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
llvm::map_iterator
mapped_iterator< ItTy, FuncTy > map_iterator(ItTy I, FuncTy F)
Definition: STLExtras.h:430
llvm::DebugCounter::isCounterSet
static bool isCounterSet(unsigned ID)
Definition: DebugCounter.h:100
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
result
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s result
Definition: README_P9.txt:256
PointerIntPair.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
GraphTraits.h
llvm::GVNExpression::UnknownExpression
Definition: GVNExpression.h:625
llvm::DomTreeNodeBase::getDFSNumIn
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
Definition: GenericDomTree.h:143
SparseBitVector.h
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
llvm::DomTreeNodeBase::getDFSNumOut
unsigned getDFSNumOut() const
Definition: GenericDomTree.h:144
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::end
iterator end()
Definition: DenseSet.h:174
llvm::ValueDFS::U
Use * U
Definition: PredicateInfo.cpp:99
Instruction.h
CommandLine.h
llvm::GVNExpression::int_op_inserter
Definition: GVNExpression.h:480
llvm::GVNExpression::ConstantExpression
Definition: GVNExpression.h:588
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1734
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:984
llvm::DominatorTreeBase::getRootNode
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Definition: GenericDomTree.h:370
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::DenseMapInfo< const Expression * >::isEqual
static bool isEqual(const Expression *LHS, const Expression *RHS)
Definition: NewGVN.cpp:471
NewGVN::ValueDFS::operator<
bool operator<(const ValueDFS &Other) const
Definition: NewGVN.cpp:3523
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:28
llvm::AAResults::onlyReadsMemory
bool onlyReadsMemory(const CallBase *Call)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
Definition: AliasAnalysis.h:461
llvm::PredicateConstraint::OtherOp
Value * OtherOp
Definition: PredicateInfo.h:77
llvm::GVNExpression::PHIExpression
Definition: GVNExpression.h:505
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::ExactEqualsExpression::ExactEqualsExpression
ExactEqualsExpression(const Expression &E)
Definition: NewGVN.cpp:435
isZero
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:524
llvm::AAResults
Definition: AliasAnalysis.h:294
llvm::getStoredValue
SDValue getStoredValue(SDValue Op)
Definition: VECustomDAG.cpp:332
llvm::MemorySSA::isLiveOnEntryDef
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:737
P2
This might compile to this xmm1 xorps xmm0 movss xmm0 ret Now consider if the code caused xmm1 to get spilled This might produce this xmm1 movaps xmm0 movaps xmm1 movss xmm0 ret since the reload is only used by these we could fold it into the producing something like xmm1 movaps xmm0 ret saving two instructions The basic idea is that a reload from a spill if only one byte chunk is bring in zeros the one element instead of elements This can be used to simplify a variety of shuffle where the elements are fixed zeros This code generates ugly probably due to costs being off or< 4 x float > * P2
Definition: README-SSE.txt:278
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
llvm::initializeNewGVNLegacyPassPass
void initializeNewGVNLegacyPassPass(PassRegistry &)
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::Instruction::isAtomic
bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
Definition: Instruction.cpp:653
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
InstrTypes.h
EnableStoreRefinement
static cl::opt< bool > EnableStoreRefinement("enable-store-refinement", cl::init(false), cl::Hidden)
llvm::JumpTable::Simplified
@ Simplified
Definition: TargetOptions.h:47
llvm::createNewGVNPass
FunctionPass * createNewGVNPass()
Definition: NewGVN.cpp:4265
SI
@ SI
Definition: SIInstrInfo.cpp:7966
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::simplifyBinOp
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
Definition: InstructionSimplify.cpp:5705
NewGVN::ValueDFS::Def
PointerIntPair< Value *, 1, bool > Def
Definition: NewGVN.cpp:3520
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
TargetLibraryInfo.h
llvm::GVNExpression::LoadExpression::equals
bool equals(const Expression &Other) const override
Definition: NewGVN.cpp:910
AssumeBundleBuilder.h
DenseSet.h
false
Definition: StackSlotColoring.cpp:141
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::Value::getValueID
unsigned getValueID() const
Return an ID for the concrete type of this object.
Definition: Value.h:532
llvm::VNCoercion
Definition: VNCoercion.h:34
llvm::GVNExpression::Expression
Definition: GVNExpression.h:60
llvm::Instruction
Definition: Instruction.h:42
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:306
GVNExpression.h
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
isCopyOfPHI
static bool isCopyOfPHI(const Value *V, const PHINode *PN)
Definition: NewGVN.cpp:983
PointerLikeTypeTraits.h
EnablePhiOfOps
static cl::opt< bool > EnablePhiOfOps("enable-phi-of-ops", cl::init(true), cl::Hidden)
Currently, the generation "phi of ops" can result in correctness issues.
llvm::AArch64CC::LE
@ LE
Definition: AArch64BaseInfo.h:268
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1713
BitVector.h
llvm::GVNExpression::BasicExpression::~BasicExpression
~BasicExpression() override
llvm::CmpInst::FCMP_OEQ
@ FCMP_OEQ
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:723
SmallPtrSet.h
llvm::BitVector
Definition: BitVector.h:75
llvm::DominatorTreeBase::updateDFSNumbers
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
Definition: GenericDomTree.h:732
none
@ none
Definition: HWAddressSanitizer.cpp:188
PatternMatch.h
llvm::ExactEqualsExpression::getComputedHash
hash_code getComputedHash() const
Definition: NewGVN.cpp:437
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::orc::tpctypes::LookupResult
std::vector< ExecutorAddr > LookupResult
Definition: TargetProcessControlTypes.h:90
place
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first place
Definition: README.txt:50
llvm::GVNExpression::PHIExpression::~PHIExpression
~PHIExpression() override
llvm::MemoryAccess::getBlock
BasicBlock * getBlock() const
Definition: MemorySSA.h:164
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(NewGVNLegacyPass, "newgvn", "Global Value Numbering", false, false) INITIALIZE_PASS_END(NewGVNLegacyPass
llvm::PredicateInfo
Encapsulates PredicateInfo, including all data associated with memory accesses.
Definition: PredicateInfo.h:178
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::DenseMapInfo< const Expression * >::isEqual
static bool isEqual(const ExactEqualsExpression &LHS, const Expression *RHS)
Definition: NewGVN.cpp:465
llvm::Instruction::isCommutative
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
Definition: Instruction.cpp:807
llvm::PredicateConstraint::Predicate
CmpInst::Predicate Predicate
Definition: PredicateInfo.h:76
llvm::DOTGraphTraits
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
Definition: DOTGraphTraits.h:166
llvm::all_equal
bool all_equal(std::initializer_list< T > Values)
Returns true if all Values in the initializer lists are equal or the list.
Definition: STLExtras.h:1985
llvm::ExactEqualsExpression::operator==
bool operator==(const Expression &Other) const
Definition: NewGVN.cpp:439
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1682
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::MemorySSAWalker::getClobberingMemoryAccess
MemoryAccess * getClobberingMemoryAccess(const Instruction *I)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Definition: MemorySSA.h:1044
llvm::wouldInstructionBeTriviallyDead
bool wouldInstructionBeTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used.
Definition: Local.cpp:415
llvm::PredicateBase
Definition: PredicateInfo.h:82
DEBUG_COUNTER
DEBUG_COUNTER(VNCounter, "newgvn-vn", "Controls which instructions are value numbered")
BasicBlock.h
llvm::cl::opt< bool >
llvm::ValueDFS
Definition: PredicateInfo.cpp:93
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:298
llvm::DebugCounter::setCounterValue
static void setCounterValue(unsigned ID, int64_t Count)
Definition: DebugCounter.h:113
llvm::getInitialValueOfAllocation
Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
Definition: MemoryBuiltins.cpp:459
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:826
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
CFGPrinter.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:110
llvm::GVNExpression
Definition: GVNExpression.h:40
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:475
uint64_t
llvm::GVNExpression::AggregateValueExpression::~AggregateValueExpression
~AggregateValueExpression() override
llvm::simplifySelectInst
Value * simplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, const SimplifyQuery &Q)
Given operands for a SelectInst, fold the result or return null.
Definition: InstructionSimplify.cpp:4656
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::BitVector::any
bool any() const
any - Returns true if any bit is set.
Definition: BitVector.h:163
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:408
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:63
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::DenseMap
Definition: DenseMap.h:714
llvm::nodes
iterator_range< typename GraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
Definition: GraphTraits.h:110
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
VNCoercion.h
llvm::DenseMapInfo< const Expression * >::getHashValue
static unsigned getHashValue(const Expression *E)
Definition: NewGVN.cpp:457
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
newgvn
newgvn
Definition: NewGVN.cpp:4261
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
ArrayRef.h
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::begin
iterator begin()
Definition: DenseSet.h:173
llvm::pdb::PDB_MemoryType::Stack
@ Stack
transform
instcombine should handle this transform
Definition: README.txt:262
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::sys::path::const_iterator::begin
friend const_iterator begin(StringRef path, Style style)
Get begin iterator over path.
Definition: Path.cpp:226
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::GVNExpression::StoreExpression
Definition: GVNExpression.h:370
llvm::GVNExpression::VariableExpression
Definition: GVNExpression.h:552
iterator_range.h
okayForPHIOfOps
static bool okayForPHIOfOps(const Instruction *I)
Definition: NewGVN.cpp:2578
llvm::SimplifyQuery::getWithInstruction
SimplifyQuery getWithInstruction(Instruction *I) const
Definition: InstructionSimplify.h:120
llvm::WinEH::EncodingType::CE
@ CE
Windows NT (Windows on ARM)
llvm::salvageKnowledge
void salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Definition: AssumeBundleBuilder.cpp:293
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:934
llvm::MemorySSA::getWalker
MemorySSAWalker * getWalker()
Definition: MemorySSA.cpp:1556
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::ArrayRecycler::clear
void clear(AllocatorType &Allocator)
Release all the tracked allocations to the allocator.
Definition: ArrayRecycler.h:104
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear
void clear()
Definition: DenseSet.h:92
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1715
llvm::GVNExpression::StoreExpression::equals
bool equals(const Expression &Other) const override
Definition: NewGVN.cpp:914
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:307
llvm::ConstantFoldInstOperands
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
Definition: ConstantFolding.cpp:1213
llvm::Expression
Class representing an expression and its matching format.
Definition: FileCheckImpl.h:237
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:396
llvm::VNCoercion::getConstantLoadValueForLoad
Constant * getConstantLoadValueForLoad(Constant *SrcVal, unsigned Offset, Type *LoadTy, const DataLayout &DL)
Definition: VNCoercion.cpp:507
llvm::simplifyCastInst
Value * simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
Definition: InstructionSimplify.cpp:5032
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1741
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:138
llvm::LoadInst::isSimple
bool isSimple() const
Definition: Instructions.h:253
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::MemorySSA::getBlockDefs
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
Definition: MemorySSA.h:765
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::ConstantInt::isZero
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:194
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:73
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
A
* A
Definition: README_ALTIVEC.txt:89
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::ExactEqualsExpression
Definition: NewGVN.cpp:432
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
NewGVN.h
CC
auto CC
Definition: RISCVRedundantCopyElimination.cpp:79
llvm::GVNExpression::CallExpression
Definition: GVNExpression.h:301
llvm::DominatorTreeBase::properlyDominates
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Definition: GenericDomTree.h:392
llvm::MemoryAccess
Definition: MemorySSA.h:142
llvm::DomTreeNodeBase< BasicBlock >
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::make_filter_range
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:632
llvm::DenseMapInfo< const Expression * >::getHashValue
static unsigned getHashValue(const ExactEqualsExpression &E)
Definition: NewGVN.cpp:461
llvm::ValueDFS::Def
Value * Def
Definition: PredicateInfo.cpp:98
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:834
Argument.h
llvm::ArrayRecycler
Recycle small arrays allocated from a BumpPtrAllocator.
Definition: ArrayRecycler.h:28
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::GVNExpression::Expression::~Expression
virtual ~Expression()
llvm::VNCoercion::getConstantMemInstValueForLoad
Constant * getConstantMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, Type *LoadTy, const DataLayout &DL)
Definition: VNCoercion.cpp:566
llvm::CmpInst::isImpliedFalseByMatchingCmp
static bool isImpliedFalseByMatchingCmp(Predicate Pred1, Predicate Pred2)
Determine if Pred1 implies Pred2 is false when two compares have matching operands.
Definition: Instructions.cpp:4463
Constant.h
llvm::CmpInst::isImpliedTrueByMatchingCmp
static bool isImpliedTrueByMatchingCmp(Predicate Pred1, Predicate Pred2)
Determine if Pred1 implies Pred2 is true when two compares have matching operands.
Definition: Instructions.cpp:4438
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:827
std
Definition: BitVector.h:851
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::PHINode::Create
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Definition: Instructions.h:2741
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:152
llvm::VNCoercion::analyzeLoadFromClobberingStore
int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr, StoreInst *DepSI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the store at D...
Definition: VNCoercion.cpp:208
Casting.h
Function.h
llvm::GVNExpression::DeadExpression
Definition: GVNExpression.h:541
DebugCounter.h
llvm::DenseMapBase::size
unsigned size() const
Definition: DenseMap.h:99
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::Type::getPointerTo
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
Definition: Type.cpp:774
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
Numbering
Global Value Numbering
Definition: NewGVN.cpp:4261
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::ExactEqualsExpression::E
const Expression & E
Definition: NewGVN.cpp:433
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::GVNExpression::LoadExpression::~LoadExpression
~LoadExpression() override
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:291
llvm::BitVector::reset
BitVector & reset()
Definition: BitVector.h:385
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::VNCoercion::getConstantStoreValueForLoad
Constant * getConstantStoreValueForLoad(Constant *SrcVal, unsigned Offset, Type *LoadTy, const DataLayout &DL)
Definition: VNCoercion.cpp:450
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:475
llvm::NewGVNPass::run
PreservedAnalyses run(Function &F, AnalysisManager< Function > &AM)
Run the pass over the function.
Definition: NewGVN.cpp:4267
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:271
llvm::DenseMapInfo< const Expression * >::getEmptyKey
static const Expression * getEmptyKey()
Definition: NewGVN.cpp:445
llvm::BasicBlock::reverse_iterator
InstListType::reverse_iterator reverse_iterator
Definition: BasicBlock.h:89
MemorySSA.h
Instructions.h
PostOrderIterator.h
llvm::GVNExpression::AggregateValueExpression
Definition: GVNExpression.h:411
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
llvm::PointerIntPair< Value *, 1, bool >
llvm::AAResults::doesNotAccessMemory
bool doesNotAccessMemory(const CallBase *Call)
Checks if the specified call is known to never read or write memory.
Definition: AliasAnalysis.h:433
llvm::ValueDFS::DFSOut
int DFSOut
Definition: PredicateInfo.cpp:95
SmallVector.h
lookup
static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset, uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs, llvm::Error &Err)
A Lookup helper functions.
Definition: InlineInfo.cpp:108
User.h
ArrayRecycler.h
Dominators.h
llvm::BitVector::find_first
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
Definition: BitVector.h:293
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:924
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
InstructionSimplify.h
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::Value::deleteValue
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:109
llvm::VNCoercion::analyzeLoadFromClobberingLoad
int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the load at De...
Definition: VNCoercion.cpp:314
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:142
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2815
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::AAResults::isMustAlias
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are must-alias.
Definition: AliasAnalysis.h:366
llvm::PHINode
Definition: Instructions.h:2699
llvm::GVNExpression::BasicExpression
Definition: GVNExpression.h:136
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::erase
bool erase(const ValueT &V)
Definition: DenseSet.h:101
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
DenseMapInfo.h
llvm::SmallPtrSetImpl< const Value * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
llvm::ConstantInt::isOne
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:200
llvm::isGuaranteedNotToBePoison
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Definition: ValueTracking.cpp:5447
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::GVNExpression::op_inserter
Definition: GVNExpression.h:243
llvm::patchReplacementInstruction
void patchReplacementInstruction(Instruction *I, Value *Repl)
Patch the replacement so that it is not more restrictive than the value being replaced.
Definition: Local.cpp:2765
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::MemorySSAWalker
This is the generic walker interface for walkers of MemorySSA.
Definition: MemorySSA.h:1015
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::simplifyCmpInst
Value * simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
Definition: InstructionSimplify.cpp:5723
raw_ostream.h
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
copy
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local copy
Definition: README.txt:101
Value.h
llvm::GVNExpression::LoadExpression
Definition: GVNExpression.h:328
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:450
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::BumpPtrAllocatorImpl::Deallocate
void Deallocate(const void *Ptr, size_t Size, size_t)
Definition: Allocator.h:218
llvm::Function::isPresplitCoroutine
bool isPresplitCoroutine() const
Determine if the function is presplit coroutine.
Definition: Function.h:488
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1251
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:73
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1732