LLVM  15.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 (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,
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 OpIsSafeForPHIOfOpsHelper(Value *V, const BasicBlock *PHIBlock,
772  bool OpIsSafeForPHIOfOps(Value *Op, const BasicBlock *PHIBlock,
774  void addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue);
775  void removePhiOfOps(Instruction *I, PHINode *PHITemp);
776 
777  // Value number an Instruction or MemoryPhi.
778  void valueNumberMemoryPhi(MemoryPhi *);
779  void valueNumberInstruction(Instruction *);
780 
781  // Symbolic evaluation.
782  ExprResult checkExprResults(Expression *, Instruction *, Value *) const;
783  ExprResult performSymbolicEvaluation(Value *,
784  SmallPtrSetImpl<Value *> &) const;
785  const Expression *performSymbolicLoadCoercion(Type *, Value *, LoadInst *,
786  Instruction *,
787  MemoryAccess *) const;
788  const Expression *performSymbolicLoadEvaluation(Instruction *) const;
789  const Expression *performSymbolicStoreEvaluation(Instruction *) const;
790  ExprResult performSymbolicCallEvaluation(Instruction *) const;
791  void sortPHIOps(MutableArrayRef<ValPair> Ops) const;
792  const Expression *performSymbolicPHIEvaluation(ArrayRef<ValPair>,
793  Instruction *I,
794  BasicBlock *PHIBlock) const;
795  const Expression *performSymbolicAggrValueEvaluation(Instruction *) const;
796  ExprResult performSymbolicCmpEvaluation(Instruction *) const;
797  ExprResult performSymbolicPredicateInfoEvaluation(IntrinsicInst *) const;
798 
799  // Congruence finding.
800  bool someEquivalentDominates(const Instruction *, const Instruction *) const;
801  Value *lookupOperandLeader(Value *) const;
802  CongruenceClass *getClassForExpression(const Expression *E) const;
803  void performCongruenceFinding(Instruction *, const Expression *);
804  void moveValueToNewCongruenceClass(Instruction *, const Expression *,
805  CongruenceClass *, CongruenceClass *);
806  void moveMemoryToNewCongruenceClass(Instruction *, MemoryAccess *,
807  CongruenceClass *, CongruenceClass *);
808  Value *getNextValueLeader(CongruenceClass *) const;
809  const MemoryAccess *getNextMemoryLeader(CongruenceClass *) const;
810  bool setMemoryClass(const MemoryAccess *From, CongruenceClass *To);
811  CongruenceClass *getMemoryClass(const MemoryAccess *MA) const;
812  const MemoryAccess *lookupMemoryLeader(const MemoryAccess *) const;
813  bool isMemoryAccessTOP(const MemoryAccess *) const;
814 
815  // Ranking
816  unsigned int getRank(const Value *) const;
817  bool shouldSwapOperands(const Value *, const Value *) const;
818  bool shouldSwapOperandsForIntrinsic(const Value *, const Value *,
819  const IntrinsicInst *I) const;
820 
821  // Reachability handling.
822  void updateReachableEdge(BasicBlock *, BasicBlock *);
823  void processOutgoingEdges(Instruction *, BasicBlock *);
824  Value *findConditionEquivalence(Value *) const;
825 
826  // Elimination.
827  struct ValueDFS;
828  void convertClassToDFSOrdered(const CongruenceClass &,
832  void convertClassToLoadsAndStores(const CongruenceClass &,
833  SmallVectorImpl<ValueDFS> &) const;
834 
835  bool eliminateInstructions(Function &);
836  void replaceInstruction(Instruction *, Value *);
837  void markInstructionForDeletion(Instruction *);
838  void deleteInstructionsInBlock(BasicBlock *);
839  Value *findPHIOfOpsLeader(const Expression *, const Instruction *,
840  const BasicBlock *) const;
841 
842  // Various instruction touch utilities
843  template <typename Map, typename KeyType>
844  void touchAndErase(Map &, const KeyType &);
845  void markUsersTouched(Value *);
846  void markMemoryUsersTouched(const MemoryAccess *);
847  void markMemoryDefTouched(const MemoryAccess *);
848  void markPredicateUsersTouched(Instruction *);
849  void markValueLeaderChangeTouched(CongruenceClass *CC);
850  void markMemoryLeaderChangeTouched(CongruenceClass *CC);
851  void markPhiOfOpsChanged(const Expression *E);
852  void addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const;
853  void addAdditionalUsers(Value *To, Value *User) const;
854  void addAdditionalUsers(ExprResult &Res, Instruction *User) const;
855 
856  // Main loop of value numbering
857  void iterateTouchedInstructions();
858 
859  // Utilities.
860  void cleanupTables();
861  std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
862  void updateProcessedCount(const Value *V);
863  void verifyMemoryCongruency() const;
864  void verifyIterationSettled(Function &F);
865  void verifyStoreExpressions() const;
866  bool singleReachablePHIPath(SmallPtrSet<const MemoryAccess *, 8> &,
867  const MemoryAccess *, const MemoryAccess *) const;
868  BasicBlock *getBlockForValue(Value *V) const;
869  void deleteExpression(const Expression *E) const;
870  MemoryUseOrDef *getMemoryAccess(const Instruction *) const;
871  MemoryPhi *getMemoryAccess(const BasicBlock *) const;
872  template <class T, class Range> T *getMinDFSOfRange(const Range &) const;
873 
874  unsigned InstrToDFSNum(const Value *V) const {
875  assert(isa<Instruction>(V) && "This should not be used for MemoryAccesses");
876  return InstrDFS.lookup(V);
877  }
878 
879  unsigned InstrToDFSNum(const MemoryAccess *MA) const {
880  return MemoryToDFSNum(MA);
881  }
882 
883  Value *InstrFromDFSNum(unsigned DFSNum) { return DFSToInstr[DFSNum]; }
884 
885  // Given a MemoryAccess, return the relevant instruction DFS number. Note:
886  // This deliberately takes a value so it can be used with Use's, which will
887  // auto-convert to Value's but not to MemoryAccess's.
888  unsigned MemoryToDFSNum(const Value *MA) const {
889  assert(isa<MemoryAccess>(MA) &&
890  "This should not be used with instructions");
891  return isa<MemoryUseOrDef>(MA)
892  ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst())
893  : InstrDFS.lookup(MA);
894  }
895 
896  bool isCycleFree(const Instruction *) const;
897  bool isBackedge(BasicBlock *From, BasicBlock *To) const;
898 
899  // Debug counter info. When verifying, we have to reset the value numbering
900  // debug counter to the same state it started in to get the same results.
901  int64_t StartingVNCounter = 0;
902 };
903 
904 } // end anonymous namespace
905 
906 template <typename T>
907 static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS) {
908  if (!isa<LoadExpression>(RHS) && !isa<StoreExpression>(RHS))
909  return false;
910  return LHS.MemoryExpression::equals(RHS);
911 }
912 
914  return equalsLoadStoreHelper(*this, Other);
915 }
916 
918  if (!equalsLoadStoreHelper(*this, Other))
919  return false;
920  // Make sure that store vs store includes the value operand.
921  if (const auto *S = dyn_cast<StoreExpression>(&Other))
922  if (getStoredValue() != S->getStoredValue())
923  return false;
924  return true;
925 }
926 
927 // Determine if the edge From->To is a backedge
928 bool NewGVN::isBackedge(BasicBlock *From, BasicBlock *To) const {
929  return From == To ||
930  RPOOrdering.lookup(DT->getNode(From)) >=
931  RPOOrdering.lookup(DT->getNode(To));
932 }
933 
934 #ifndef NDEBUG
935 static std::string getBlockName(const BasicBlock *B) {
937 }
938 #endif
939 
940 // Get a MemoryAccess for an instruction, fake or real.
941 MemoryUseOrDef *NewGVN::getMemoryAccess(const Instruction *I) const {
942  auto *Result = MSSA->getMemoryAccess(I);
943  return Result ? Result : TempToMemory.lookup(I);
944 }
945 
946 // Get a MemoryPhi for a basic block. These are all real.
947 MemoryPhi *NewGVN::getMemoryAccess(const BasicBlock *BB) const {
948  return MSSA->getMemoryAccess(BB);
949 }
950 
951 // Get the basic block from an instruction/memory value.
952 BasicBlock *NewGVN::getBlockForValue(Value *V) const {
953  if (auto *I = dyn_cast<Instruction>(V)) {
954  auto *Parent = I->getParent();
955  if (Parent)
956  return Parent;
957  Parent = TempToBlock.lookup(V);
958  assert(Parent && "Every fake instruction should have a block");
959  return Parent;
960  }
961 
962  auto *MP = dyn_cast<MemoryPhi>(V);
963  assert(MP && "Should have been an instruction or a MemoryPhi");
964  return MP->getBlock();
965 }
966 
967 // Delete a definitely dead expression, so it can be reused by the expression
968 // allocator. Some of these are not in creation functions, so we have to accept
969 // const versions.
970 void NewGVN::deleteExpression(const Expression *E) const {
971  assert(isa<BasicExpression>(E));
972  auto *BE = cast<BasicExpression>(E);
973  const_cast<BasicExpression *>(BE)->deallocateOperands(ArgRecycler);
974  ExpressionAllocator.Deallocate(E);
975 }
976 
977 // If V is a predicateinfo copy, get the thing it is a copy of.
978 static Value *getCopyOf(const Value *V) {
979  if (auto *II = dyn_cast<IntrinsicInst>(V))
980  if (II->getIntrinsicID() == Intrinsic::ssa_copy)
981  return II->getOperand(0);
982  return nullptr;
983 }
984 
985 // Return true if V is really PN, even accounting for predicateinfo copies.
986 static bool isCopyOfPHI(const Value *V, const PHINode *PN) {
987  return V == PN || getCopyOf(V) == PN;
988 }
989 
990 static bool isCopyOfAPHI(const Value *V) {
991  auto *CO = getCopyOf(V);
992  return CO && isa<PHINode>(CO);
993 }
994 
995 // Sort PHI Operands into a canonical order. What we use here is an RPO
996 // order. The BlockInstRange numbers are generated in an RPO walk of the basic
997 // blocks.
998 void NewGVN::sortPHIOps(MutableArrayRef<ValPair> Ops) const {
999  llvm::sort(Ops, [&](const ValPair &P1, const ValPair &P2) {
1000  return BlockInstRange.lookup(P1.second).first <
1001  BlockInstRange.lookup(P2.second).first;
1002  });
1003 }
1004 
1005 // Return true if V is a value that will always be available (IE can
1006 // be placed anywhere) in the function. We don't do globals here
1007 // because they are often worse to put in place.
1008 static bool alwaysAvailable(Value *V) {
1009  return isa<Constant>(V) || isa<Argument>(V);
1010 }
1011 
1012 // Create a PHIExpression from an array of {incoming edge, value} pairs. I is
1013 // the original instruction we are creating a PHIExpression for (but may not be
1014 // a phi node). We require, as an invariant, that all the PHIOperands in the
1015 // same block are sorted the same way. sortPHIOps will sort them into a
1016 // canonical order.
1017 PHIExpression *NewGVN::createPHIExpression(ArrayRef<ValPair> PHIOperands,
1018  const Instruction *I,
1019  BasicBlock *PHIBlock,
1020  bool &HasBackedge,
1021  bool &OriginalOpsConstant) const {
1022  unsigned NumOps = PHIOperands.size();
1023  auto *E = new (ExpressionAllocator) PHIExpression(NumOps, PHIBlock);
1024 
1025  E->allocateOperands(ArgRecycler, ExpressionAllocator);
1026  E->setType(PHIOperands.begin()->first->getType());
1027  E->setOpcode(Instruction::PHI);
1028 
1029  // Filter out unreachable phi operands.
1030  auto Filtered = make_filter_range(PHIOperands, [&](const ValPair &P) {
1031  auto *BB = P.second;
1032  if (auto *PHIOp = dyn_cast<PHINode>(I))
1033  if (isCopyOfPHI(P.first, PHIOp))
1034  return false;
1035  if (!ReachableEdges.count({BB, PHIBlock}))
1036  return false;
1037  // Things in TOPClass are equivalent to everything.
1038  if (ValueToClass.lookup(P.first) == TOPClass)
1039  return false;
1040  OriginalOpsConstant = OriginalOpsConstant && isa<Constant>(P.first);
1041  HasBackedge = HasBackedge || isBackedge(BB, PHIBlock);
1042  return lookupOperandLeader(P.first) != I;
1043  });
1044  std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
1045  [&](const ValPair &P) -> Value * {
1046  return lookupOperandLeader(P.first);
1047  });
1048  return E;
1049 }
1050 
1051 // Set basic expression info (Arguments, type, opcode) for Expression
1052 // E from Instruction I in block B.
1053 bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E) const {
1054  bool AllConstant = true;
1055  if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
1056  E->setType(GEP->getSourceElementType());
1057  else
1058  E->setType(I->getType());
1059  E->setOpcode(I->getOpcode());
1060  E->allocateOperands(ArgRecycler, ExpressionAllocator);
1061 
1062  // Transform the operand array into an operand leader array, and keep track of
1063  // whether all members are constant.
1064  std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) {
1065  auto Operand = lookupOperandLeader(O);
1066  AllConstant = AllConstant && isa<Constant>(Operand);
1067  return Operand;
1068  });
1069 
1070  return AllConstant;
1071 }
1072 
1073 const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
1074  Value *Arg1, Value *Arg2,
1075  Instruction *I) const {
1076  auto *E = new (ExpressionAllocator) BasicExpression(2);
1077  // TODO: we need to remove context instruction after Value Tracking
1078  // can run without context instruction
1079  const SimplifyQuery Q = SQ.getWithInstruction(I);
1080 
1081  E->setType(T);
1082  E->setOpcode(Opcode);
1083  E->allocateOperands(ArgRecycler, ExpressionAllocator);
1084  if (Instruction::isCommutative(Opcode)) {
1085  // Ensure that commutative instructions that only differ by a permutation
1086  // of their operands get the same value number by sorting the operand value
1087  // numbers. Since all commutative instructions have two operands it is more
1088  // efficient to sort by hand rather than using, say, std::sort.
1089  if (shouldSwapOperands(Arg1, Arg2))
1090  std::swap(Arg1, Arg2);
1091  }
1092  E->op_push_back(lookupOperandLeader(Arg1));
1093  E->op_push_back(lookupOperandLeader(Arg2));
1094 
1095  Value *V = simplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), Q);
1096  if (auto Simplified = checkExprResults(E, I, V)) {
1097  addAdditionalUsers(Simplified, I);
1098  return Simplified.Expr;
1099  }
1100  return E;
1101 }
1102 
1103 // Take a Value returned by simplification of Expression E/Instruction
1104 // I, and see if it resulted in a simpler expression. If so, return
1105 // that expression.
1106 NewGVN::ExprResult NewGVN::checkExprResults(Expression *E, Instruction *I,
1107  Value *V) const {
1108  if (!V)
1109  return ExprResult::none();
1110 
1111  if (auto *C = dyn_cast<Constant>(V)) {
1112  if (I)
1113  LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
1114  << " constant " << *C << "\n");
1115  NumGVNOpsSimplified++;
1116  assert(isa<BasicExpression>(E) &&
1117  "We should always have had a basic expression here");
1118  deleteExpression(E);
1119  return ExprResult::some(createConstantExpression(C));
1120  } else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
1121  if (I)
1122  LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
1123  << " variable " << *V << "\n");
1124  deleteExpression(E);
1125  return ExprResult::some(createVariableExpression(V));
1126  }
1127 
1128  CongruenceClass *CC = ValueToClass.lookup(V);
1129  if (CC) {
1130  if (CC->getLeader() && CC->getLeader() != I) {
1131  return ExprResult::some(createVariableOrConstant(CC->getLeader()), V);
1132  }
1133  if (CC->getDefiningExpr()) {
1134  if (I)
1135  LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
1136  << " expression " << *CC->getDefiningExpr() << "\n");
1137  NumGVNOpsSimplified++;
1138  deleteExpression(E);
1139  return ExprResult::some(CC->getDefiningExpr(), V);
1140  }
1141  }
1142 
1143  return ExprResult::none();
1144 }
1145 
1146 // Create a value expression from the instruction I, replacing operands with
1147 // their leaders.
1148 
1149 NewGVN::ExprResult NewGVN::createExpression(Instruction *I) const {
1150  auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands());
1151  // TODO: we need to remove context instruction after Value Tracking
1152  // can run without context instruction
1153  const SimplifyQuery Q = SQ.getWithInstruction(I);
1154 
1155  bool AllConstant = setBasicExpressionInfo(I, E);
1156 
1157  if (I->isCommutative()) {
1158  // Ensure that commutative instructions that only differ by a permutation
1159  // of their operands get the same value number by sorting the operand value
1160  // numbers. Since all commutative instructions have two operands it is more
1161  // efficient to sort by hand rather than using, say, std::sort.
1162  assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
1163  if (shouldSwapOperands(E->getOperand(0), E->getOperand(1)))
1164  E->swapOperands(0, 1);
1165  }
1166  // Perform simplification.
1167  if (auto *CI = dyn_cast<CmpInst>(I)) {
1168  // Sort the operand value numbers so x<y and y>x get the same value
1169  // number.
1170  CmpInst::Predicate Predicate = CI->getPredicate();
1171  if (shouldSwapOperands(E->getOperand(0), E->getOperand(1))) {
1172  E->swapOperands(0, 1);
1174  }
1175  E->setOpcode((CI->getOpcode() << 8) | Predicate);
1176  // TODO: 25% of our time is spent in simplifyCmpInst with pointer operands
1177  assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
1178  "Wrong types on cmp instruction");
1179  assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
1180  E->getOperand(1)->getType() == I->getOperand(1)->getType()));
1181  Value *V =
1182  simplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), Q);
1183  if (auto Simplified = checkExprResults(E, I, V))
1184  return Simplified;
1185  } else if (isa<SelectInst>(I)) {
1186  if (isa<Constant>(E->getOperand(0)) ||
1187  E->getOperand(1) == E->getOperand(2)) {
1188  assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
1189  E->getOperand(2)->getType() == I->getOperand(2)->getType());
1190  Value *V = simplifySelectInst(E->getOperand(0), E->getOperand(1),
1191  E->getOperand(2), Q);
1192  if (auto Simplified = checkExprResults(E, I, V))
1193  return Simplified;
1194  }
1195  } else if (I->isBinaryOp()) {
1196  Value *V =
1197  simplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), Q);
1198  if (auto Simplified = checkExprResults(E, I, V))
1199  return Simplified;
1200  } else if (auto *CI = dyn_cast<CastInst>(I)) {
1201  Value *V =
1202  simplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), Q);
1203  if (auto Simplified = checkExprResults(E, I, V))
1204  return Simplified;
1205  } else if (auto *GEPI = dyn_cast<GetElementPtrInst>(I)) {
1206  Value *V =
1207  simplifyGEPInst(GEPI->getSourceElementType(), *E->op_begin(),
1208  makeArrayRef(std::next(E->op_begin()), E->op_end()),
1209  GEPI->isInBounds(), Q);
1210  if (auto Simplified = checkExprResults(E, I, V))
1211  return Simplified;
1212  } else if (AllConstant) {
1213  // We don't bother trying to simplify unless all of the operands
1214  // were constant.
1215  // TODO: There are a lot of Simplify*'s we could call here, if we
1216  // wanted to. The original motivating case for this code was a
1217  // zext i1 false to i8, which we don't have an interface to
1218  // simplify (IE there is no SimplifyZExt).
1219 
1221  for (Value *Arg : E->operands())
1222  C.emplace_back(cast<Constant>(Arg));
1223 
1224  if (Value *V = ConstantFoldInstOperands(I, C, DL, TLI))
1225  if (auto Simplified = checkExprResults(E, I, V))
1226  return Simplified;
1227  }
1228  return ExprResult::some(E);
1229 }
1230 
1232 NewGVN::createAggregateValueExpression(Instruction *I) const {
1233  if (auto *II = dyn_cast<InsertValueInst>(I)) {
1234  auto *E = new (ExpressionAllocator)
1235  AggregateValueExpression(I->getNumOperands(), II->getNumIndices());
1236  setBasicExpressionInfo(I, E);
1237  E->allocateIntOperands(ExpressionAllocator);
1238  std::copy(II->idx_begin(), II->idx_end(), int_op_inserter(E));
1239  return E;
1240  } else if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
1241  auto *E = new (ExpressionAllocator)
1242  AggregateValueExpression(I->getNumOperands(), EI->getNumIndices());
1243  setBasicExpressionInfo(EI, E);
1244  E->allocateIntOperands(ExpressionAllocator);
1245  std::copy(EI->idx_begin(), EI->idx_end(), int_op_inserter(E));
1246  return E;
1247  }
1248  llvm_unreachable("Unhandled type of aggregate value operation");
1249 }
1250 
1251 const DeadExpression *NewGVN::createDeadExpression() const {
1252  // DeadExpression has no arguments and all DeadExpression's are the same,
1253  // so we only need one of them.
1254  return SingletonDeadExpression;
1255 }
1256 
1257 const VariableExpression *NewGVN::createVariableExpression(Value *V) const {
1258  auto *E = new (ExpressionAllocator) VariableExpression(V);
1259  E->setOpcode(V->getValueID());
1260  return E;
1261 }
1262 
1263 const Expression *NewGVN::createVariableOrConstant(Value *V) const {
1264  if (auto *C = dyn_cast<Constant>(V))
1265  return createConstantExpression(C);
1266  return createVariableExpression(V);
1267 }
1268 
1269 const ConstantExpression *NewGVN::createConstantExpression(Constant *C) const {
1270  auto *E = new (ExpressionAllocator) ConstantExpression(C);
1271  E->setOpcode(C->getValueID());
1272  return E;
1273 }
1274 
1275 const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) const {
1276  auto *E = new (ExpressionAllocator) UnknownExpression(I);
1277  E->setOpcode(I->getOpcode());
1278  return E;
1279 }
1280 
1281 const CallExpression *
1282 NewGVN::createCallExpression(CallInst *CI, const MemoryAccess *MA) const {
1283  // FIXME: Add operand bundles for calls.
1284  // FIXME: Allow commutative matching for intrinsics.
1285  auto *E =
1286  new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, MA);
1287  setBasicExpressionInfo(CI, E);
1288  return E;
1289 }
1290 
1291 // Return true if some equivalent of instruction Inst dominates instruction U.
1292 bool NewGVN::someEquivalentDominates(const Instruction *Inst,
1293  const Instruction *U) const {
1294  auto *CC = ValueToClass.lookup(Inst);
1295  // This must be an instruction because we are only called from phi nodes
1296  // in the case that the value it needs to check against is an instruction.
1297 
1298  // The most likely candidates for dominance are the leader and the next leader.
1299  // The leader or nextleader will dominate in all cases where there is an
1300  // equivalent that is higher up in the dom tree.
1301  // We can't *only* check them, however, because the
1302  // dominator tree could have an infinite number of non-dominating siblings
1303  // with instructions that are in the right congruence class.
1304  // A
1305  // B C D E F G
1306  // |
1307  // H
1308  // Instruction U could be in H, with equivalents in every other sibling.
1309  // Depending on the rpo order picked, the leader could be the equivalent in
1310  // any of these siblings.
1311  if (!CC)
1312  return false;
1313  if (alwaysAvailable(CC->getLeader()))
1314  return true;
1315  if (DT->dominates(cast<Instruction>(CC->getLeader()), U))
1316  return true;
1317  if (CC->getNextLeader().first &&
1318  DT->dominates(cast<Instruction>(CC->getNextLeader().first), U))
1319  return true;
1320  return llvm::any_of(*CC, [&](const Value *Member) {
1321  return Member != CC->getLeader() &&
1322  DT->dominates(cast<Instruction>(Member), U);
1323  });
1324 }
1325 
1326 // See if we have a congruence class and leader for this operand, and if so,
1327 // return it. Otherwise, return the operand itself.
1328 Value *NewGVN::lookupOperandLeader(Value *V) const {
1329  CongruenceClass *CC = ValueToClass.lookup(V);
1330  if (CC) {
1331  // Everything in TOP is represented by poison, as it can be any value.
1332  // We do have to make sure we get the type right though, so we can't set the
1333  // RepLeader to poison.
1334  if (CC == TOPClass)
1335  return PoisonValue::get(V->getType());
1336  return CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
1337  }
1338 
1339  return V;
1340 }
1341 
1342 const MemoryAccess *NewGVN::lookupMemoryLeader(const MemoryAccess *MA) const {
1343  auto *CC = getMemoryClass(MA);
1344  assert(CC->getMemoryLeader() &&
1345  "Every MemoryAccess should be mapped to a congruence class with a "
1346  "representative memory access");
1347  return CC->getMemoryLeader();
1348 }
1349 
1350 // Return true if the MemoryAccess is really equivalent to everything. This is
1351 // equivalent to the lattice value "TOP" in most lattices. This is the initial
1352 // state of all MemoryAccesses.
1353 bool NewGVN::isMemoryAccessTOP(const MemoryAccess *MA) const {
1354  return getMemoryClass(MA) == TOPClass;
1355 }
1356 
1357 LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp,
1358  LoadInst *LI,
1359  const MemoryAccess *MA) const {
1360  auto *E =
1361  new (ExpressionAllocator) LoadExpression(1, LI, lookupMemoryLeader(MA));
1362  E->allocateOperands(ArgRecycler, ExpressionAllocator);
1363  E->setType(LoadType);
1364 
1365  // Give store and loads same opcode so they value number together.
1366  E->setOpcode(0);
1367  E->op_push_back(PointerOp);
1368 
1369  // TODO: Value number heap versions. We may be able to discover
1370  // things alias analysis can't on it's own (IE that a store and a
1371  // load have the same value, and thus, it isn't clobbering the load).
1372  return E;
1373 }
1374 
1375 const StoreExpression *
1376 NewGVN::createStoreExpression(StoreInst *SI, const MemoryAccess *MA) const {
1377  auto *StoredValueLeader = lookupOperandLeader(SI->getValueOperand());
1378  auto *E = new (ExpressionAllocator)
1379  StoreExpression(SI->getNumOperands(), SI, StoredValueLeader, MA);
1380  E->allocateOperands(ArgRecycler, ExpressionAllocator);
1381  E->setType(SI->getValueOperand()->getType());
1382 
1383  // Give store and loads same opcode so they value number together.
1384  E->setOpcode(0);
1385  E->op_push_back(lookupOperandLeader(SI->getPointerOperand()));
1386 
1387  // TODO: Value number heap versions. We may be able to discover
1388  // things alias analysis can't on it's own (IE that a store and a
1389  // load have the same value, and thus, it isn't clobbering the load).
1390  return E;
1391 }
1392 
1393 const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I) const {
1394  // Unlike loads, we never try to eliminate stores, so we do not check if they
1395  // are simple and avoid value numbering them.
1396  auto *SI = cast<StoreInst>(I);
1397  auto *StoreAccess = getMemoryAccess(SI);
1398  // Get the expression, if any, for the RHS of the MemoryDef.
1399  const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess();
1401  StoreRHS = MSSAWalker->getClobberingMemoryAccess(StoreAccess);
1402  // If we bypassed the use-def chains, make sure we add a use.
1403  StoreRHS = lookupMemoryLeader(StoreRHS);
1404  if (StoreRHS != StoreAccess->getDefiningAccess())
1405  addMemoryUsers(StoreRHS, StoreAccess);
1406  // If we are defined by ourselves, use the live on entry def.
1407  if (StoreRHS == StoreAccess)
1408  StoreRHS = MSSA->getLiveOnEntryDef();
1409 
1410  if (SI->isSimple()) {
1411  // See if we are defined by a previous store expression, it already has a
1412  // value, and it's the same value as our current store. FIXME: Right now, we
1413  // only do this for simple stores, we should expand to cover memcpys, etc.
1414  const auto *LastStore = createStoreExpression(SI, StoreRHS);
1415  const auto *LastCC = ExpressionToClass.lookup(LastStore);
1416  // We really want to check whether the expression we matched was a store. No
1417  // easy way to do that. However, we can check that the class we found has a
1418  // store, which, assuming the value numbering state is not corrupt, is
1419  // sufficient, because we must also be equivalent to that store's expression
1420  // for it to be in the same class as the load.
1421  if (LastCC && LastCC->getStoredValue() == LastStore->getStoredValue())
1422  return LastStore;
1423  // Also check if our value operand is defined by a load of the same memory
1424  // location, and the memory state is the same as it was then (otherwise, it
1425  // could have been overwritten later. See test32 in
1426  // transforms/DeadStoreElimination/simple.ll).
1427  if (auto *LI = dyn_cast<LoadInst>(LastStore->getStoredValue()))
1428  if ((lookupOperandLeader(LI->getPointerOperand()) ==
1429  LastStore->getOperand(0)) &&
1430  (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) ==
1431  StoreRHS))
1432  return LastStore;
1433  deleteExpression(LastStore);
1434  }
1435 
1436  // If the store is not equivalent to anything, value number it as a store that
1437  // produces a unique memory state (instead of using it's MemoryUse, we use
1438  // it's MemoryDef).
1439  return createStoreExpression(SI, StoreAccess);
1440 }
1441 
1442 // See if we can extract the value of a loaded pointer from a load, a store, or
1443 // a memory instruction.
1444 const Expression *
1445 NewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr,
1446  LoadInst *LI, Instruction *DepInst,
1447  MemoryAccess *DefiningAccess) const {
1448  assert((!LI || LI->isSimple()) && "Not a simple load");
1449  if (auto *DepSI = dyn_cast<StoreInst>(DepInst)) {
1450  // Can't forward from non-atomic to atomic without violating memory model.
1451  // Also don't need to coerce if they are the same type, we will just
1452  // propagate.
1453  if (LI->isAtomic() > DepSI->isAtomic() ||
1454  LoadType == DepSI->getValueOperand()->getType())
1455  return nullptr;
1456  int Offset = analyzeLoadFromClobberingStore(LoadType, LoadPtr, DepSI, DL);
1457  if (Offset >= 0) {
1458  if (auto *C = dyn_cast<Constant>(
1459  lookupOperandLeader(DepSI->getValueOperand()))) {
1460  if (Constant *Res =
1461  getConstantStoreValueForLoad(C, Offset, LoadType, DL)) {
1462  LLVM_DEBUG(dbgs() << "Coercing load from store " << *DepSI
1463  << " to constant " << *Res << "\n");
1464  return createConstantExpression(Res);
1465  }
1466  }
1467  }
1468  } else if (auto *DepLI = dyn_cast<LoadInst>(DepInst)) {
1469  // Can't forward from non-atomic to atomic without violating memory model.
1470  if (LI->isAtomic() > DepLI->isAtomic())
1471  return nullptr;
1472  int Offset = analyzeLoadFromClobberingLoad(LoadType, LoadPtr, DepLI, DL);
1473  if (Offset >= 0) {
1474  // We can coerce a constant load into a load.
1475  if (auto *C = dyn_cast<Constant>(lookupOperandLeader(DepLI)))
1476  if (auto *PossibleConstant =
1477  getConstantLoadValueForLoad(C, Offset, LoadType, DL)) {
1478  LLVM_DEBUG(dbgs() << "Coercing load from load " << *LI
1479  << " to constant " << *PossibleConstant << "\n");
1480  return createConstantExpression(PossibleConstant);
1481  }
1482  }
1483  } else if (auto *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1484  int Offset = analyzeLoadFromClobberingMemInst(LoadType, LoadPtr, DepMI, DL);
1485  if (Offset >= 0) {
1486  if (auto *PossibleConstant =
1487  getConstantMemInstValueForLoad(DepMI, Offset, LoadType, DL)) {
1488  LLVM_DEBUG(dbgs() << "Coercing load from meminst " << *DepMI
1489  << " to constant " << *PossibleConstant << "\n");
1490  return createConstantExpression(PossibleConstant);
1491  }
1492  }
1493  }
1494 
1495  // All of the below are only true if the loaded pointer is produced
1496  // by the dependent instruction.
1497  if (LoadPtr != lookupOperandLeader(DepInst) &&
1498  !AA->isMustAlias(LoadPtr, DepInst))
1499  return nullptr;
1500  // If this load really doesn't depend on anything, then we must be loading an
1501  // undef value. This can happen when loading for a fresh allocation with no
1502  // intervening stores, for example. Note that this is only true in the case
1503  // that the result of the allocation is pointer equal to the load ptr.
1504  if (isa<AllocaInst>(DepInst)) {
1505  return createConstantExpression(UndefValue::get(LoadType));
1506  }
1507  // If this load occurs either right after a lifetime begin,
1508  // then the loaded value is undefined.
1509  else if (auto *II = dyn_cast<IntrinsicInst>(DepInst)) {
1510  if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1511  return createConstantExpression(UndefValue::get(LoadType));
1512  } else if (auto *InitVal =
1513  getInitialValueOfAllocation(DepInst, TLI, LoadType))
1514  return createConstantExpression(InitVal);
1515 
1516  return nullptr;
1517 }
1518 
1519 const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) const {
1520  auto *LI = cast<LoadInst>(I);
1521 
1522  // We can eliminate in favor of non-simple loads, but we won't be able to
1523  // eliminate the loads themselves.
1524  if (!LI->isSimple())
1525  return nullptr;
1526 
1527  Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand());
1528  // Load of undef is UB.
1529  if (isa<UndefValue>(LoadAddressLeader))
1530  return createConstantExpression(PoisonValue::get(LI->getType()));
1531  MemoryAccess *OriginalAccess = getMemoryAccess(I);
1532  MemoryAccess *DefiningAccess =
1533  MSSAWalker->getClobberingMemoryAccess(OriginalAccess);
1534 
1535  if (!MSSA->isLiveOnEntryDef(DefiningAccess)) {
1536  if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
1537  Instruction *DefiningInst = MD->getMemoryInst();
1538  // If the defining instruction is not reachable, replace with poison.
1539  if (!ReachableBlocks.count(DefiningInst->getParent()))
1540  return createConstantExpression(PoisonValue::get(LI->getType()));
1541  // This will handle stores and memory insts. We only do if it the
1542  // defining access has a different type, or it is a pointer produced by
1543  // certain memory operations that cause the memory to have a fixed value
1544  // (IE things like calloc).
1545  if (const auto *CoercionResult =
1546  performSymbolicLoadCoercion(LI->getType(), LoadAddressLeader, LI,
1547  DefiningInst, DefiningAccess))
1548  return CoercionResult;
1549  }
1550  }
1551 
1552  const auto *LE = createLoadExpression(LI->getType(), LoadAddressLeader, LI,
1553  DefiningAccess);
1554  // If our MemoryLeader is not our defining access, add a use to the
1555  // MemoryLeader, so that we get reprocessed when it changes.
1556  if (LE->getMemoryLeader() != DefiningAccess)
1557  addMemoryUsers(LE->getMemoryLeader(), OriginalAccess);
1558  return LE;
1559 }
1560 
1561 NewGVN::ExprResult
1562 NewGVN::performSymbolicPredicateInfoEvaluation(IntrinsicInst *I) const {
1563  auto *PI = PredInfo->getPredicateInfoFor(I);
1564  if (!PI)
1565  return ExprResult::none();
1566 
1567  LLVM_DEBUG(dbgs() << "Found predicate info from instruction !\n");
1568 
1569  const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
1570  if (!Constraint)
1571  return ExprResult::none();
1572 
1573  CmpInst::Predicate Predicate = Constraint->Predicate;
1574  Value *CmpOp0 = I->getOperand(0);
1575  Value *CmpOp1 = Constraint->OtherOp;
1576 
1577  Value *FirstOp = lookupOperandLeader(CmpOp0);
1578  Value *SecondOp = lookupOperandLeader(CmpOp1);
1579  Value *AdditionallyUsedValue = CmpOp0;
1580 
1581  // Sort the ops.
1582  if (shouldSwapOperandsForIntrinsic(FirstOp, SecondOp, I)) {
1583  std::swap(FirstOp, SecondOp);
1585  AdditionallyUsedValue = CmpOp1;
1586  }
1587 
1588  if (Predicate == CmpInst::ICMP_EQ)
1589  return ExprResult::some(createVariableOrConstant(FirstOp),
1590  AdditionallyUsedValue, PI);
1591 
1592  // Handle the special case of floating point.
1593  if (Predicate == CmpInst::FCMP_OEQ && isa<ConstantFP>(FirstOp) &&
1594  !cast<ConstantFP>(FirstOp)->isZero())
1595  return ExprResult::some(createConstantExpression(cast<Constant>(FirstOp)),
1596  AdditionallyUsedValue, PI);
1597 
1598  return ExprResult::none();
1599 }
1600 
1601 // Evaluate read only and pure calls, and create an expression result.
1602 NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(Instruction *I) const {
1603  auto *CI = cast<CallInst>(I);
1604  if (auto *II = dyn_cast<IntrinsicInst>(I)) {
1605  // Intrinsics with the returned attribute are copies of arguments.
1606  if (auto *ReturnedValue = II->getReturnedArgOperand()) {
1607  if (II->getIntrinsicID() == Intrinsic::ssa_copy)
1608  if (auto Res = performSymbolicPredicateInfoEvaluation(II))
1609  return Res;
1610  return ExprResult::some(createVariableOrConstant(ReturnedValue));
1611  }
1612  }
1613  if (AA->doesNotAccessMemory(CI)) {
1614  return ExprResult::some(
1615  createCallExpression(CI, TOPClass->getMemoryLeader()));
1616  } else if (AA->onlyReadsMemory(CI)) {
1617  if (auto *MA = MSSA->getMemoryAccess(CI)) {
1618  auto *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(MA);
1619  return ExprResult::some(createCallExpression(CI, DefiningAccess));
1620  } else // MSSA determined that CI does not access memory.
1621  return ExprResult::some(
1622  createCallExpression(CI, TOPClass->getMemoryLeader()));
1623  }
1624  return ExprResult::none();
1625 }
1626 
1627 // Retrieve the memory class for a given MemoryAccess.
1628 CongruenceClass *NewGVN::getMemoryClass(const MemoryAccess *MA) const {
1629  auto *Result = MemoryAccessToClass.lookup(MA);
1630  assert(Result && "Should have found memory class");
1631  return Result;
1632 }
1633 
1634 // Update the MemoryAccess equivalence table to say that From is equal to To,
1635 // and return true if this is different from what already existed in the table.
1636 bool NewGVN::setMemoryClass(const MemoryAccess *From,
1637  CongruenceClass *NewClass) {
1638  assert(NewClass &&
1639  "Every MemoryAccess should be getting mapped to a non-null class");
1640  LLVM_DEBUG(dbgs() << "Setting " << *From);
1641  LLVM_DEBUG(dbgs() << " equivalent to congruence class ");
1642  LLVM_DEBUG(dbgs() << NewClass->getID()
1643  << " with current MemoryAccess leader ");
1644  LLVM_DEBUG(dbgs() << *NewClass->getMemoryLeader() << "\n");
1645 
1646  auto LookupResult = MemoryAccessToClass.find(From);
1647  bool Changed = false;
1648  // If it's already in the table, see if the value changed.
1649  if (LookupResult != MemoryAccessToClass.end()) {
1650  auto *OldClass = LookupResult->second;
1651  if (OldClass != NewClass) {
1652  // If this is a phi, we have to handle memory member updates.
1653  if (auto *MP = dyn_cast<MemoryPhi>(From)) {
1654  OldClass->memory_erase(MP);
1655  NewClass->memory_insert(MP);
1656  // This may have killed the class if it had no non-memory members
1657  if (OldClass->getMemoryLeader() == From) {
1658  if (OldClass->definesNoMemory()) {
1659  OldClass->setMemoryLeader(nullptr);
1660  } else {
1661  OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
1662  LLVM_DEBUG(dbgs() << "Memory class leader change for class "
1663  << OldClass->getID() << " to "
1664  << *OldClass->getMemoryLeader()
1665  << " due to removal of a memory member " << *From
1666  << "\n");
1667  markMemoryLeaderChangeTouched(OldClass);
1668  }
1669  }
1670  }
1671  // It wasn't equivalent before, and now it is.
1672  LookupResult->second = NewClass;
1673  Changed = true;
1674  }
1675  }
1676 
1677  return Changed;
1678 }
1679 
1680 // Determine if a instruction is cycle-free. That means the values in the
1681 // instruction don't depend on any expressions that can change value as a result
1682 // of the instruction. For example, a non-cycle free instruction would be v =
1683 // phi(0, v+1).
1684 bool NewGVN::isCycleFree(const Instruction *I) const {
1685  // In order to compute cycle-freeness, we do SCC finding on the instruction,
1686  // and see what kind of SCC it ends up in. If it is a singleton, it is
1687  // cycle-free. If it is not in a singleton, it is only cycle free if the
1688  // other members are all phi nodes (as they do not compute anything, they are
1689  // copies).
1690  auto ICS = InstCycleState.lookup(I);
1691  if (ICS == ICS_Unknown) {
1692  SCCFinder.Start(I);
1693  auto &SCC = SCCFinder.getComponentFor(I);
1694  // It's cycle free if it's size 1 or the SCC is *only* phi nodes.
1695  if (SCC.size() == 1)
1696  InstCycleState.insert({I, ICS_CycleFree});
1697  else {
1698  bool AllPhis = llvm::all_of(SCC, [](const Value *V) {
1699  return isa<PHINode>(V) || isCopyOfAPHI(V);
1700  });
1701  ICS = AllPhis ? ICS_CycleFree : ICS_Cycle;
1702  for (auto *Member : SCC)
1703  if (auto *MemberPhi = dyn_cast<PHINode>(Member))
1704  InstCycleState.insert({MemberPhi, ICS});
1705  }
1706  }
1707  if (ICS == ICS_Cycle)
1708  return false;
1709  return true;
1710 }
1711 
1712 // Evaluate PHI nodes symbolically and create an expression result.
1713 const Expression *
1714 NewGVN::performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps,
1715  Instruction *I,
1716  BasicBlock *PHIBlock) const {
1717  // True if one of the incoming phi edges is a backedge.
1718  bool HasBackedge = false;
1719  // All constant tracks the state of whether all the *original* phi operands
1720  // This is really shorthand for "this phi cannot cycle due to forward
1721  // change in value of the phi is guaranteed not to later change the value of
1722  // the phi. IE it can't be v = phi(undef, v+1)
1723  bool OriginalOpsConstant = true;
1724  auto *E = cast<PHIExpression>(createPHIExpression(
1725  PHIOps, I, PHIBlock, HasBackedge, OriginalOpsConstant));
1726  // We match the semantics of SimplifyPhiNode from InstructionSimplify here.
1727  // See if all arguments are the same.
1728  // We track if any were undef because they need special handling.
1729  bool HasUndef = false, HasPoison = false;
1730  auto Filtered = make_filter_range(E->operands(), [&](Value *Arg) {
1731  if (isa<PoisonValue>(Arg)) {
1732  HasPoison = true;
1733  return false;
1734  }
1735  if (isa<UndefValue>(Arg)) {
1736  HasUndef = true;
1737  return false;
1738  }
1739  return true;
1740  });
1741  // If we are left with no operands, it's dead.
1742  if (Filtered.empty()) {
1743  // If it has undef or poison at this point, it means there are no-non-undef
1744  // arguments, and thus, the value of the phi node must be undef.
1745  if (HasUndef) {
1746  LLVM_DEBUG(
1747  dbgs() << "PHI Node " << *I
1748  << " has no non-undef arguments, valuing it as undef\n");
1749  return createConstantExpression(UndefValue::get(I->getType()));
1750  }
1751  if (HasPoison) {
1752  LLVM_DEBUG(
1753  dbgs() << "PHI Node " << *I
1754  << " has no non-poison arguments, valuing it as poison\n");
1755  return createConstantExpression(PoisonValue::get(I->getType()));
1756  }
1757 
1758  LLVM_DEBUG(dbgs() << "No arguments of PHI node " << *I << " are live\n");
1759  deleteExpression(E);
1760  return createDeadExpression();
1761  }
1762  Value *AllSameValue = *(Filtered.begin());
1763  ++Filtered.begin();
1764  // Can't use std::equal here, sadly, because filter.begin moves.
1765  if (llvm::all_of(Filtered, [&](Value *Arg) { return Arg == AllSameValue; })) {
1766  // Can't fold phi(undef, X) -> X unless X can't be poison (thus X is undef
1767  // in the worst case).
1768  if (HasUndef && !isGuaranteedNotToBePoison(AllSameValue, AC, nullptr, DT))
1769  return E;
1770 
1771  // In LLVM's non-standard representation of phi nodes, it's possible to have
1772  // phi nodes with cycles (IE dependent on other phis that are .... dependent
1773  // on the original phi node), especially in weird CFG's where some arguments
1774  // are unreachable, or uninitialized along certain paths. This can cause
1775  // infinite loops during evaluation. We work around this by not trying to
1776  // really evaluate them independently, but instead using a variable
1777  // expression to say if one is equivalent to the other.
1778  // We also special case undef/poison, so that if we have an undef, we can't
1779  // use the common value unless it dominates the phi block.
1780  if (HasPoison || HasUndef) {
1781  // If we have undef and at least one other value, this is really a
1782  // multivalued phi, and we need to know if it's cycle free in order to
1783  // evaluate whether we can ignore the undef. The other parts of this are
1784  // just shortcuts. If there is no backedge, or all operands are
1785  // constants, it also must be cycle free.
1786  if (HasBackedge && !OriginalOpsConstant &&
1787  !isa<UndefValue>(AllSameValue) && !isCycleFree(I))
1788  return E;
1789 
1790  // Only have to check for instructions
1791  if (auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
1792  if (!someEquivalentDominates(AllSameInst, I))
1793  return E;
1794  }
1795  // Can't simplify to something that comes later in the iteration.
1796  // Otherwise, when and if it changes congruence class, we will never catch
1797  // up. We will always be a class behind it.
1798  if (isa<Instruction>(AllSameValue) &&
1799  InstrToDFSNum(AllSameValue) > InstrToDFSNum(I))
1800  return E;
1801  NumGVNPhisAllSame++;
1802  LLVM_DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue
1803  << "\n");
1804  deleteExpression(E);
1805  return createVariableOrConstant(AllSameValue);
1806  }
1807  return E;
1808 }
1809 
1810 const Expression *
1811 NewGVN::performSymbolicAggrValueEvaluation(Instruction *I) const {
1812  if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
1813  auto *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
1814  if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0)
1815  // EI is an extract from one of our with.overflow intrinsics. Synthesize
1816  // a semantically equivalent expression instead of an extract value
1817  // expression.
1818  return createBinaryExpression(WO->getBinaryOp(), EI->getType(),
1819  WO->getLHS(), WO->getRHS(), I);
1820  }
1821 
1822  return createAggregateValueExpression(I);
1823 }
1824 
1825 NewGVN::ExprResult NewGVN::performSymbolicCmpEvaluation(Instruction *I) const {
1826  assert(isa<CmpInst>(I) && "Expected a cmp instruction.");
1827 
1828  auto *CI = cast<CmpInst>(I);
1829  // See if our operands are equal to those of a previous predicate, and if so,
1830  // if it implies true or false.
1831  auto Op0 = lookupOperandLeader(CI->getOperand(0));
1832  auto Op1 = lookupOperandLeader(CI->getOperand(1));
1833  auto OurPredicate = CI->getPredicate();
1834  if (shouldSwapOperands(Op0, Op1)) {
1835  std::swap(Op0, Op1);
1836  OurPredicate = CI->getSwappedPredicate();
1837  }
1838 
1839  // Avoid processing the same info twice.
1840  const PredicateBase *LastPredInfo = nullptr;
1841  // See if we know something about the comparison itself, like it is the target
1842  // of an assume.
1843  auto *CmpPI = PredInfo->getPredicateInfoFor(I);
1844  if (isa_and_nonnull<PredicateAssume>(CmpPI))
1845  return ExprResult::some(
1846  createConstantExpression(ConstantInt::getTrue(CI->getType())));
1847 
1848  if (Op0 == Op1) {
1849  // This condition does not depend on predicates, no need to add users
1850  if (CI->isTrueWhenEqual())
1851  return ExprResult::some(
1852  createConstantExpression(ConstantInt::getTrue(CI->getType())));
1853  else if (CI->isFalseWhenEqual())
1854  return ExprResult::some(
1855  createConstantExpression(ConstantInt::getFalse(CI->getType())));
1856  }
1857 
1858  // NOTE: Because we are comparing both operands here and below, and using
1859  // previous comparisons, we rely on fact that predicateinfo knows to mark
1860  // comparisons that use renamed operands as users of the earlier comparisons.
1861  // It is *not* enough to just mark predicateinfo renamed operands as users of
1862  // the earlier comparisons, because the *other* operand may have changed in a
1863  // previous iteration.
1864  // Example:
1865  // icmp slt %a, %b
1866  // %b.0 = ssa.copy(%b)
1867  // false branch:
1868  // icmp slt %c, %b.0
1869 
1870  // %c and %a may start out equal, and thus, the code below will say the second
1871  // %icmp is false. c may become equal to something else, and in that case the
1872  // %second icmp *must* be reexamined, but would not if only the renamed
1873  // %operands are considered users of the icmp.
1874 
1875  // *Currently* we only check one level of comparisons back, and only mark one
1876  // level back as touched when changes happen. If you modify this code to look
1877  // back farther through comparisons, you *must* mark the appropriate
1878  // comparisons as users in PredicateInfo.cpp, or you will cause bugs. See if
1879  // we know something just from the operands themselves
1880 
1881  // See if our operands have predicate info, so that we may be able to derive
1882  // something from a previous comparison.
1883  for (const auto &Op : CI->operands()) {
1884  auto *PI = PredInfo->getPredicateInfoFor(Op);
1885  if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
1886  if (PI == LastPredInfo)
1887  continue;
1888  LastPredInfo = PI;
1889  // In phi of ops cases, we may have predicate info that we are evaluating
1890  // in a different context.
1891  if (!DT->dominates(PBranch->To, getBlockForValue(I)))
1892  continue;
1893  // TODO: Along the false edge, we may know more things too, like
1894  // icmp of
1895  // same operands is false.
1896  // TODO: We only handle actual comparison conditions below, not
1897  // and/or.
1898  auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
1899  if (!BranchCond)
1900  continue;
1901  auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
1902  auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
1903  auto BranchPredicate = BranchCond->getPredicate();
1904  if (shouldSwapOperands(BranchOp0, BranchOp1)) {
1905  std::swap(BranchOp0, BranchOp1);
1906  BranchPredicate = BranchCond->getSwappedPredicate();
1907  }
1908  if (BranchOp0 == Op0 && BranchOp1 == Op1) {
1909  if (PBranch->TrueEdge) {
1910  // If we know the previous predicate is true and we are in the true
1911  // edge then we may be implied true or false.
1912  if (CmpInst::isImpliedTrueByMatchingCmp(BranchPredicate,
1913  OurPredicate)) {
1914  return ExprResult::some(
1915  createConstantExpression(ConstantInt::getTrue(CI->getType())),
1916  PI);
1917  }
1918 
1919  if (CmpInst::isImpliedFalseByMatchingCmp(BranchPredicate,
1920  OurPredicate)) {
1921  return ExprResult::some(
1922  createConstantExpression(ConstantInt::getFalse(CI->getType())),
1923  PI);
1924  }
1925  } else {
1926  // Just handle the ne and eq cases, where if we have the same
1927  // operands, we may know something.
1928  if (BranchPredicate == OurPredicate) {
1929  // Same predicate, same ops,we know it was false, so this is false.
1930  return ExprResult::some(
1931  createConstantExpression(ConstantInt::getFalse(CI->getType())),
1932  PI);
1933  } else if (BranchPredicate ==
1934  CmpInst::getInversePredicate(OurPredicate)) {
1935  // Inverse predicate, we know the other was false, so this is true.
1936  return ExprResult::some(
1937  createConstantExpression(ConstantInt::getTrue(CI->getType())),
1938  PI);
1939  }
1940  }
1941  }
1942  }
1943  }
1944  // Create expression will take care of simplifyCmpInst
1945  return createExpression(I);
1946 }
1947 
1948 // Substitute and symbolize the value before value numbering.
1949 NewGVN::ExprResult
1950 NewGVN::performSymbolicEvaluation(Value *V,
1951  SmallPtrSetImpl<Value *> &Visited) const {
1952 
1953  const Expression *E = nullptr;
1954  if (auto *C = dyn_cast<Constant>(V))
1955  E = createConstantExpression(C);
1956  else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
1957  E = createVariableExpression(V);
1958  } else {
1959  // TODO: memory intrinsics.
1960  // TODO: Some day, we should do the forward propagation and reassociation
1961  // parts of the algorithm.
1962  auto *I = cast<Instruction>(V);
1963  switch (I->getOpcode()) {
1964  case Instruction::ExtractValue:
1965  case Instruction::InsertValue:
1966  E = performSymbolicAggrValueEvaluation(I);
1967  break;
1968  case Instruction::PHI: {
1970  auto *PN = cast<PHINode>(I);
1971  for (unsigned i = 0; i < PN->getNumOperands(); ++i)
1972  Ops.push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)});
1973  // Sort to ensure the invariant createPHIExpression requires is met.
1974  sortPHIOps(Ops);
1975  E = performSymbolicPHIEvaluation(Ops, I, getBlockForValue(I));
1976  } break;
1977  case Instruction::Call:
1978  return performSymbolicCallEvaluation(I);
1979  break;
1980  case Instruction::Store:
1981  E = performSymbolicStoreEvaluation(I);
1982  break;
1983  case Instruction::Load:
1984  E = performSymbolicLoadEvaluation(I);
1985  break;
1986  case Instruction::BitCast:
1987  case Instruction::AddrSpaceCast:
1988  return createExpression(I);
1989  break;
1990  case Instruction::ICmp:
1991  case Instruction::FCmp:
1992  return performSymbolicCmpEvaluation(I);
1993  break;
1994  case Instruction::FNeg:
1995  case Instruction::Add:
1996  case Instruction::FAdd:
1997  case Instruction::Sub:
1998  case Instruction::FSub:
1999  case Instruction::Mul:
2000  case Instruction::FMul:
2001  case Instruction::UDiv:
2002  case Instruction::SDiv:
2003  case Instruction::FDiv:
2004  case Instruction::URem:
2005  case Instruction::SRem:
2006  case Instruction::FRem:
2007  case Instruction::Shl:
2008  case Instruction::LShr:
2009  case Instruction::AShr:
2010  case Instruction::And:
2011  case Instruction::Or:
2012  case Instruction::Xor:
2013  case Instruction::Trunc:
2014  case Instruction::ZExt:
2015  case Instruction::SExt:
2016  case Instruction::FPToUI:
2017  case Instruction::FPToSI:
2018  case Instruction::UIToFP:
2019  case Instruction::SIToFP:
2020  case Instruction::FPTrunc:
2021  case Instruction::FPExt:
2022  case Instruction::PtrToInt:
2023  case Instruction::IntToPtr:
2024  case Instruction::Select:
2025  case Instruction::ExtractElement:
2026  case Instruction::InsertElement:
2027  case Instruction::GetElementPtr:
2028  return createExpression(I);
2029  break;
2030  case Instruction::ShuffleVector:
2031  // FIXME: Add support for shufflevector to createExpression.
2032  return ExprResult::none();
2033  default:
2034  return ExprResult::none();
2035  }
2036  }
2037  return ExprResult::some(E);
2038 }
2039 
2040 // Look up a container of values/instructions in a map, and touch all the
2041 // instructions in the container. Then erase value from the map.
2042 template <typename Map, typename KeyType>
2043 void NewGVN::touchAndErase(Map &M, const KeyType &Key) {
2044  const auto Result = M.find_as(Key);
2045  if (Result != M.end()) {
2046  for (const typename Map::mapped_type::value_type Mapped : Result->second)
2047  TouchedInstructions.set(InstrToDFSNum(Mapped));
2048  M.erase(Result);
2049  }
2050 }
2051 
2052 void NewGVN::addAdditionalUsers(Value *To, Value *User) const {
2053  assert(User && To != User);
2054  if (isa<Instruction>(To))
2055  AdditionalUsers[To].insert(User);
2056 }
2057 
2058 void NewGVN::addAdditionalUsers(ExprResult &Res, Instruction *User) const {
2059  if (Res.ExtraDep && Res.ExtraDep != User)
2060  addAdditionalUsers(Res.ExtraDep, User);
2061  Res.ExtraDep = nullptr;
2062 
2063  if (Res.PredDep) {
2064  if (const auto *PBranch = dyn_cast<PredicateBranch>(Res.PredDep))
2065  PredicateToUsers[PBranch->Condition].insert(User);
2066  else if (const auto *PAssume = dyn_cast<PredicateAssume>(Res.PredDep))
2067  PredicateToUsers[PAssume->Condition].insert(User);
2068  }
2069  Res.PredDep = nullptr;
2070 }
2071 
2072 void NewGVN::markUsersTouched(Value *V) {
2073  // Now mark the users as touched.
2074  for (auto *User : V->users()) {
2075  assert(isa<Instruction>(User) && "Use of value not within an instruction?");
2076  TouchedInstructions.set(InstrToDFSNum(User));
2077  }
2078  touchAndErase(AdditionalUsers, V);
2079 }
2080 
2081 void NewGVN::addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const {
2082  LLVM_DEBUG(dbgs() << "Adding memory user " << *U << " to " << *To << "\n");
2083  MemoryToUsers[To].insert(U);
2084 }
2085 
2086 void NewGVN::markMemoryDefTouched(const MemoryAccess *MA) {
2087  TouchedInstructions.set(MemoryToDFSNum(MA));
2088 }
2089 
2090 void NewGVN::markMemoryUsersTouched(const MemoryAccess *MA) {
2091  if (isa<MemoryUse>(MA))
2092  return;
2093  for (auto U : MA->users())
2094  TouchedInstructions.set(MemoryToDFSNum(U));
2095  touchAndErase(MemoryToUsers, MA);
2096 }
2097 
2098 // Touch all the predicates that depend on this instruction.
2099 void NewGVN::markPredicateUsersTouched(Instruction *I) {
2100  touchAndErase(PredicateToUsers, I);
2101 }
2102 
2103 // Mark users affected by a memory leader change.
2104 void NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *CC) {
2105  for (auto M : CC->memory())
2106  markMemoryDefTouched(M);
2107 }
2108 
2109 // Touch the instructions that need to be updated after a congruence class has a
2110 // leader change, and mark changed values.
2111 void NewGVN::markValueLeaderChangeTouched(CongruenceClass *CC) {
2112  for (auto M : *CC) {
2113  if (auto *I = dyn_cast<Instruction>(M))
2114  TouchedInstructions.set(InstrToDFSNum(I));
2115  LeaderChanges.insert(M);
2116  }
2117 }
2118 
2119 // Give a range of things that have instruction DFS numbers, this will return
2120 // the member of the range with the smallest dfs number.
2121 template <class T, class Range>
2122 T *NewGVN::getMinDFSOfRange(const Range &R) const {
2123  std::pair<T *, unsigned> MinDFS = {nullptr, ~0U};
2124  for (const auto X : R) {
2125  auto DFSNum = InstrToDFSNum(X);
2126  if (DFSNum < MinDFS.second)
2127  MinDFS = {X, DFSNum};
2128  }
2129  return MinDFS.first;
2130 }
2131 
2132 // This function returns the MemoryAccess that should be the next leader of
2133 // congruence class CC, under the assumption that the current leader is going to
2134 // disappear.
2135 const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *CC) const {
2136  // TODO: If this ends up to slow, we can maintain a next memory leader like we
2137  // do for regular leaders.
2138  // Make sure there will be a leader to find.
2139  assert(!CC->definesNoMemory() && "Can't get next leader if there is none");
2140  if (CC->getStoreCount() > 0) {
2141  if (auto *NL = dyn_cast_or_null<StoreInst>(CC->getNextLeader().first))
2142  return getMemoryAccess(NL);
2143  // Find the store with the minimum DFS number.
2144  auto *V = getMinDFSOfRange<Value>(make_filter_range(
2145  *CC, [&](const Value *V) { return isa<StoreInst>(V); }));
2146  return getMemoryAccess(cast<StoreInst>(V));
2147  }
2148  assert(CC->getStoreCount() == 0);
2149 
2150  // Given our assertion, hitting this part must mean
2151  // !OldClass->memory_empty()
2152  if (CC->memory_size() == 1)
2153  return *CC->memory_begin();
2154  return getMinDFSOfRange<const MemoryPhi>(CC->memory());
2155 }
2156 
2157 // This function returns the next value leader of a congruence class, under the
2158 // assumption that the current leader is going away. This should end up being
2159 // the next most dominating member.
2160 Value *NewGVN::getNextValueLeader(CongruenceClass *CC) const {
2161  // We don't need to sort members if there is only 1, and we don't care about
2162  // sorting the TOP class because everything either gets out of it or is
2163  // unreachable.
2164 
2165  if (CC->size() == 1 || CC == TOPClass) {
2166  return *(CC->begin());
2167  } else if (CC->getNextLeader().first) {
2168  ++NumGVNAvoidedSortedLeaderChanges;
2169  return CC->getNextLeader().first;
2170  } else {
2171  ++NumGVNSortedLeaderChanges;
2172  // NOTE: If this ends up to slow, we can maintain a dual structure for
2173  // member testing/insertion, or keep things mostly sorted, and sort only
2174  // here, or use SparseBitVector or ....
2175  return getMinDFSOfRange<Value>(*CC);
2176  }
2177 }
2178 
2179 // Move a MemoryAccess, currently in OldClass, to NewClass, including updates to
2180 // the memory members, etc for the move.
2181 //
2182 // The invariants of this function are:
2183 //
2184 // - I must be moving to NewClass from OldClass
2185 // - The StoreCount of OldClass and NewClass is expected to have been updated
2186 // for I already if it is a store.
2187 // - The OldClass memory leader has not been updated yet if I was the leader.
2188 void NewGVN::moveMemoryToNewCongruenceClass(Instruction *I,
2189  MemoryAccess *InstMA,
2190  CongruenceClass *OldClass,
2191  CongruenceClass *NewClass) {
2192  // If the leader is I, and we had a representative MemoryAccess, it should
2193  // be the MemoryAccess of OldClass.
2194  assert((!InstMA || !OldClass->getMemoryLeader() ||
2195  OldClass->getLeader() != I ||
2196  MemoryAccessToClass.lookup(OldClass->getMemoryLeader()) ==
2197  MemoryAccessToClass.lookup(InstMA)) &&
2198  "Representative MemoryAccess mismatch");
2199  // First, see what happens to the new class
2200  if (!NewClass->getMemoryLeader()) {
2201  // Should be a new class, or a store becoming a leader of a new class.
2202  assert(NewClass->size() == 1 ||
2203  (isa<StoreInst>(I) && NewClass->getStoreCount() == 1));
2204  NewClass->setMemoryLeader(InstMA);
2205  // Mark it touched if we didn't just create a singleton
2206  LLVM_DEBUG(dbgs() << "Memory class leader change for class "
2207  << NewClass->getID()
2208  << " due to new memory instruction becoming leader\n");
2209  markMemoryLeaderChangeTouched(NewClass);
2210  }
2211  setMemoryClass(InstMA, NewClass);
2212  // Now, fixup the old class if necessary
2213  if (OldClass->getMemoryLeader() == InstMA) {
2214  if (!OldClass->definesNoMemory()) {
2215  OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
2216  LLVM_DEBUG(dbgs() << "Memory class leader change for class "
2217  << OldClass->getID() << " to "
2218  << *OldClass->getMemoryLeader()
2219  << " due to removal of old leader " << *InstMA << "\n");
2220  markMemoryLeaderChangeTouched(OldClass);
2221  } else
2222  OldClass->setMemoryLeader(nullptr);
2223  }
2224 }
2225 
2226 // Move a value, currently in OldClass, to be part of NewClass
2227 // Update OldClass and NewClass for the move (including changing leaders, etc).
2228 void NewGVN::moveValueToNewCongruenceClass(Instruction *I, const Expression *E,
2229  CongruenceClass *OldClass,
2230  CongruenceClass *NewClass) {
2231  if (I == OldClass->getNextLeader().first)
2232  OldClass->resetNextLeader();
2233 
2234  OldClass->erase(I);
2235  NewClass->insert(I);
2236 
2237  if (NewClass->getLeader() != I)
2238  NewClass->addPossibleNextLeader({I, InstrToDFSNum(I)});
2239  // Handle our special casing of stores.
2240  if (auto *SI = dyn_cast<StoreInst>(I)) {
2241  OldClass->decStoreCount();
2242  // Okay, so when do we want to make a store a leader of a class?
2243  // If we have a store defined by an earlier load, we want the earlier load
2244  // to lead the class.
2245  // If we have a store defined by something else, we want the store to lead
2246  // the class so everything else gets the "something else" as a value.
2247  // If we have a store as the single member of the class, we want the store
2248  // as the leader
2249  if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) {
2250  // If it's a store expression we are using, it means we are not equivalent
2251  // to something earlier.
2252  if (auto *SE = dyn_cast<StoreExpression>(E)) {
2253  NewClass->setStoredValue(SE->getStoredValue());
2254  markValueLeaderChangeTouched(NewClass);
2255  // Shift the new class leader to be the store
2256  LLVM_DEBUG(dbgs() << "Changing leader of congruence class "
2257  << NewClass->getID() << " from "
2258  << *NewClass->getLeader() << " to " << *SI
2259  << " because store joined class\n");
2260  // If we changed the leader, we have to mark it changed because we don't
2261  // know what it will do to symbolic evaluation.
2262  NewClass->setLeader(SI);
2263  }
2264  // We rely on the code below handling the MemoryAccess change.
2265  }
2266  NewClass->incStoreCount();
2267  }
2268  // True if there is no memory instructions left in a class that had memory
2269  // instructions before.
2270 
2271  // If it's not a memory use, set the MemoryAccess equivalence
2272  auto *InstMA = dyn_cast_or_null<MemoryDef>(getMemoryAccess(I));
2273  if (InstMA)
2274  moveMemoryToNewCongruenceClass(I, InstMA, OldClass, NewClass);
2275  ValueToClass[I] = NewClass;
2276  // See if we destroyed the class or need to swap leaders.
2277  if (OldClass->empty() && OldClass != TOPClass) {
2278  if (OldClass->getDefiningExpr()) {
2279  LLVM_DEBUG(dbgs() << "Erasing expression " << *OldClass->getDefiningExpr()
2280  << " from table\n");
2281  // We erase it as an exact expression to make sure we don't just erase an
2282  // equivalent one.
2283  auto Iter = ExpressionToClass.find_as(
2284  ExactEqualsExpression(*OldClass->getDefiningExpr()));
2285  if (Iter != ExpressionToClass.end())
2286  ExpressionToClass.erase(Iter);
2287 #ifdef EXPENSIVE_CHECKS
2288  assert(
2289  (*OldClass->getDefiningExpr() != *E || ExpressionToClass.lookup(E)) &&
2290  "We erased the expression we just inserted, which should not happen");
2291 #endif
2292  }
2293  } else if (OldClass->getLeader() == I) {
2294  // When the leader changes, the value numbering of
2295  // everything may change due to symbolization changes, so we need to
2296  // reprocess.
2297  LLVM_DEBUG(dbgs() << "Value class leader change for class "
2298  << OldClass->getID() << "\n");
2299  ++NumGVNLeaderChanges;
2300  // Destroy the stored value if there are no more stores to represent it.
2301  // Note that this is basically clean up for the expression removal that
2302  // happens below. If we remove stores from a class, we may leave it as a
2303  // class of equivalent memory phis.
2304  if (OldClass->getStoreCount() == 0) {
2305  if (OldClass->getStoredValue())
2306  OldClass->setStoredValue(nullptr);
2307  }
2308  OldClass->setLeader(getNextValueLeader(OldClass));
2309  OldClass->resetNextLeader();
2310  markValueLeaderChangeTouched(OldClass);
2311  }
2312 }
2313 
2314 // For a given expression, mark the phi of ops instructions that could have
2315 // changed as a result.
2316 void NewGVN::markPhiOfOpsChanged(const Expression *E) {
2317  touchAndErase(ExpressionToPhiOfOps, E);
2318 }
2319 
2320 // Perform congruence finding on a given value numbering expression.
2321 void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) {
2322  // This is guaranteed to return something, since it will at least find
2323  // TOP.
2324 
2325  CongruenceClass *IClass = ValueToClass.lookup(I);
2326  assert(IClass && "Should have found a IClass");
2327  // Dead classes should have been eliminated from the mapping.
2328  assert(!IClass->isDead() && "Found a dead class");
2329 
2330  CongruenceClass *EClass = nullptr;
2331  if (const auto *VE = dyn_cast<VariableExpression>(E)) {
2332  EClass = ValueToClass.lookup(VE->getVariableValue());
2333  } else if (isa<DeadExpression>(E)) {
2334  EClass = TOPClass;
2335  }
2336  if (!EClass) {
2337  auto lookupResult = ExpressionToClass.insert({E, nullptr});
2338 
2339  // If it's not in the value table, create a new congruence class.
2340  if (lookupResult.second) {
2341  CongruenceClass *NewClass = createCongruenceClass(nullptr, E);
2342  auto place = lookupResult.first;
2343  place->second = NewClass;
2344 
2345  // Constants and variables should always be made the leader.
2346  if (const auto *CE = dyn_cast<ConstantExpression>(E)) {
2347  NewClass->setLeader(CE->getConstantValue());
2348  } else if (const auto *SE = dyn_cast<StoreExpression>(E)) {
2349  StoreInst *SI = SE->getStoreInst();
2350  NewClass->setLeader(SI);
2351  NewClass->setStoredValue(SE->getStoredValue());
2352  // The RepMemoryAccess field will be filled in properly by the
2353  // moveValueToNewCongruenceClass call.
2354  } else {
2355  NewClass->setLeader(I);
2356  }
2357  assert(!isa<VariableExpression>(E) &&
2358  "VariableExpression should have been handled already");
2359 
2360  EClass = NewClass;
2361  LLVM_DEBUG(dbgs() << "Created new congruence class for " << *I
2362  << " using expression " << *E << " at "
2363  << NewClass->getID() << " and leader "
2364  << *(NewClass->getLeader()));
2365  if (NewClass->getStoredValue())
2366  LLVM_DEBUG(dbgs() << " and stored value "
2367  << *(NewClass->getStoredValue()));
2368  LLVM_DEBUG(dbgs() << "\n");
2369  } else {
2370  EClass = lookupResult.first->second;
2371  if (isa<ConstantExpression>(E))
2372  assert((isa<Constant>(EClass->getLeader()) ||
2373  (EClass->getStoredValue() &&
2374  isa<Constant>(EClass->getStoredValue()))) &&
2375  "Any class with a constant expression should have a "
2376  "constant leader");
2377 
2378  assert(EClass && "Somehow don't have an eclass");
2379 
2380  assert(!EClass->isDead() && "We accidentally looked up a dead class");
2381  }
2382  }
2383  bool ClassChanged = IClass != EClass;
2384  bool LeaderChanged = LeaderChanges.erase(I);
2385  if (ClassChanged || LeaderChanged) {
2386  LLVM_DEBUG(dbgs() << "New class " << EClass->getID() << " for expression "
2387  << *E << "\n");
2388  if (ClassChanged) {
2389  moveValueToNewCongruenceClass(I, E, IClass, EClass);
2390  markPhiOfOpsChanged(E);
2391  }
2392 
2393  markUsersTouched(I);
2394  if (MemoryAccess *MA = getMemoryAccess(I))
2395  markMemoryUsersTouched(MA);
2396  if (auto *CI = dyn_cast<CmpInst>(I))
2397  markPredicateUsersTouched(CI);
2398  }
2399  // If we changed the class of the store, we want to ensure nothing finds the
2400  // old store expression. In particular, loads do not compare against stored
2401  // value, so they will find old store expressions (and associated class
2402  // mappings) if we leave them in the table.
2403  if (ClassChanged && isa<StoreInst>(I)) {
2404  auto *OldE = ValueToExpression.lookup(I);
2405  // It could just be that the old class died. We don't want to erase it if we
2406  // just moved classes.
2407  if (OldE && isa<StoreExpression>(OldE) && *E != *OldE) {
2408  // Erase this as an exact expression to ensure we don't erase expressions
2409  // equivalent to it.
2410  auto Iter = ExpressionToClass.find_as(ExactEqualsExpression(*OldE));
2411  if (Iter != ExpressionToClass.end())
2412  ExpressionToClass.erase(Iter);
2413  }
2414  }
2415  ValueToExpression[I] = E;
2416 }
2417 
2418 // Process the fact that Edge (from, to) is reachable, including marking
2419 // any newly reachable blocks and instructions for processing.
2420 void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) {
2421  // Check if the Edge was reachable before.
2422  if (ReachableEdges.insert({From, To}).second) {
2423  // If this block wasn't reachable before, all instructions are touched.
2424  if (ReachableBlocks.insert(To).second) {
2425  LLVM_DEBUG(dbgs() << "Block " << getBlockName(To)
2426  << " marked reachable\n");
2427  const auto &InstRange = BlockInstRange.lookup(To);
2428  TouchedInstructions.set(InstRange.first, InstRange.second);
2429  } else {
2430  LLVM_DEBUG(dbgs() << "Block " << getBlockName(To)
2431  << " was reachable, but new edge {"
2432  << getBlockName(From) << "," << getBlockName(To)
2433  << "} to it found\n");
2434 
2435  // We've made an edge reachable to an existing block, which may
2436  // impact predicates. Otherwise, only mark the phi nodes as touched, as
2437  // they are the only thing that depend on new edges. Anything using their
2438  // values will get propagated to if necessary.
2439  if (MemoryAccess *MemPhi = getMemoryAccess(To))
2440  TouchedInstructions.set(InstrToDFSNum(MemPhi));
2441 
2442  // FIXME: We should just add a union op on a Bitvector and
2443  // SparseBitVector. We can do it word by word faster than we are doing it
2444  // here.
2445  for (auto InstNum : RevisitOnReachabilityChange[To])
2446  TouchedInstructions.set(InstNum);
2447  }
2448  }
2449 }
2450 
2451 // Given a predicate condition (from a switch, cmp, or whatever) and a block,
2452 // see if we know some constant value for it already.
2453 Value *NewGVN::findConditionEquivalence(Value *Cond) const {
2454  auto Result = lookupOperandLeader(Cond);
2455  return isa<Constant>(Result) ? Result : nullptr;
2456 }
2457 
2458 // Process the outgoing edges of a block for reachability.
2459 void NewGVN::processOutgoingEdges(Instruction *TI, BasicBlock *B) {
2460  // Evaluate reachability of terminator instruction.
2461  Value *Cond;
2462  BasicBlock *TrueSucc, *FalseSucc;
2463  if (match(TI, m_Br(m_Value(Cond), TrueSucc, FalseSucc))) {
2464  Value *CondEvaluated = findConditionEquivalence(Cond);
2465  if (!CondEvaluated) {
2466  if (auto *I = dyn_cast<Instruction>(Cond)) {
2467  SmallPtrSet<Value *, 4> Visited;
2468  auto Res = performSymbolicEvaluation(I, Visited);
2469  if (const auto *CE = dyn_cast_or_null<ConstantExpression>(Res.Expr)) {
2470  CondEvaluated = CE->getConstantValue();
2471  addAdditionalUsers(Res, I);
2472  } else {
2473  // Did not use simplification result, no need to add the extra
2474  // dependency.
2475  Res.ExtraDep = nullptr;
2476  }
2477  } else if (isa<ConstantInt>(Cond)) {
2478  CondEvaluated = Cond;
2479  }
2480  }
2481  ConstantInt *CI;
2482  if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
2483  if (CI->isOne()) {
2484  LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI
2485  << " evaluated to true\n");
2486  updateReachableEdge(B, TrueSucc);
2487  } else if (CI->isZero()) {
2488  LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI
2489  << " evaluated to false\n");
2490  updateReachableEdge(B, FalseSucc);
2491  }
2492  } else {
2493  updateReachableEdge(B, TrueSucc);
2494  updateReachableEdge(B, FalseSucc);
2495  }
2496  } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
2497  // For switches, propagate the case values into the case
2498  // destinations.
2499 
2500  Value *SwitchCond = SI->getCondition();
2501  Value *CondEvaluated = findConditionEquivalence(SwitchCond);
2502  // See if we were able to turn this switch statement into a constant.
2503  if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
2504  auto *CondVal = cast<ConstantInt>(CondEvaluated);
2505  // We should be able to get case value for this.
2506  auto Case = *SI->findCaseValue(CondVal);
2507  if (Case.getCaseSuccessor() == SI->getDefaultDest()) {
2508  // We proved the value is outside of the range of the case.
2509  // We can't do anything other than mark the default dest as reachable,
2510  // and go home.
2511  updateReachableEdge(B, SI->getDefaultDest());
2512  return;
2513  }
2514  // Now get where it goes and mark it reachable.
2515  BasicBlock *TargetBlock = Case.getCaseSuccessor();
2516  updateReachableEdge(B, TargetBlock);
2517  } else {
2518  for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
2519  BasicBlock *TargetBlock = SI->getSuccessor(i);
2520  updateReachableEdge(B, TargetBlock);
2521  }
2522  }
2523  } else {
2524  // Otherwise this is either unconditional, or a type we have no
2525  // idea about. Just mark successors as reachable.
2526  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
2527  BasicBlock *TargetBlock = TI->getSuccessor(i);
2528  updateReachableEdge(B, TargetBlock);
2529  }
2530 
2531  // This also may be a memory defining terminator, in which case, set it
2532  // equivalent only to itself.
2533  //
2534  auto *MA = getMemoryAccess(TI);
2535  if (MA && !isa<MemoryUse>(MA)) {
2536  auto *CC = ensureLeaderOfMemoryClass(MA);
2537  if (setMemoryClass(MA, CC))
2538  markMemoryUsersTouched(MA);
2539  }
2540  }
2541 }
2542 
2543 // Remove the PHI of Ops PHI for I
2544 void NewGVN::removePhiOfOps(Instruction *I, PHINode *PHITemp) {
2545  InstrDFS.erase(PHITemp);
2546  // It's still a temp instruction. We keep it in the array so it gets erased.
2547  // However, it's no longer used by I, or in the block
2548  TempToBlock.erase(PHITemp);
2549  RealToTemp.erase(I);
2550  // We don't remove the users from the phi node uses. This wastes a little
2551  // time, but such is life. We could use two sets to track which were there
2552  // are the start of NewGVN, and which were added, but right nowt he cost of
2553  // tracking is more than the cost of checking for more phi of ops.
2554 }
2555 
2556 // Add PHI Op in BB as a PHI of operations version of ExistingValue.
2557 void NewGVN::addPhiOfOps(PHINode *Op, BasicBlock *BB,
2558  Instruction *ExistingValue) {
2559  InstrDFS[Op] = InstrToDFSNum(ExistingValue);
2560  AllTempInstructions.insert(Op);
2561  TempToBlock[Op] = BB;
2562  RealToTemp[ExistingValue] = Op;
2563  // Add all users to phi node use, as they are now uses of the phi of ops phis
2564  // and may themselves be phi of ops.
2565  for (auto *U : ExistingValue->users())
2566  if (auto *UI = dyn_cast<Instruction>(U))
2567  PHINodeUses.insert(UI);
2568 }
2569 
2570 static bool okayForPHIOfOps(const Instruction *I) {
2571  if (!EnablePhiOfOps)
2572  return false;
2573  return isa<BinaryOperator>(I) || isa<SelectInst>(I) || isa<CmpInst>(I) ||
2574  isa<LoadInst>(I);
2575 }
2576 
2577 bool NewGVN::OpIsSafeForPHIOfOpsHelper(
2578  Value *V, const BasicBlock *PHIBlock,
2580  SmallVectorImpl<Instruction *> &Worklist) {
2581 
2582  if (!isa<Instruction>(V))
2583  return true;
2584  auto OISIt = OpSafeForPHIOfOps.find(V);
2585  if (OISIt != OpSafeForPHIOfOps.end())
2586  return OISIt->second;
2587 
2588  // Keep walking until we either dominate the phi block, or hit a phi, or run
2589  // out of things to check.
2590  if (DT->properlyDominates(getBlockForValue(V), PHIBlock)) {
2591  OpSafeForPHIOfOps.insert({V, true});
2592  return true;
2593  }
2594  // PHI in the same block.
2595  if (isa<PHINode>(V) && getBlockForValue(V) == PHIBlock) {
2596  OpSafeForPHIOfOps.insert({V, false});
2597  return false;
2598  }
2599 
2600  auto *OrigI = cast<Instruction>(V);
2601  // When we hit an instruction that reads memory (load, call, etc), we must
2602  // consider any store that may happen in the loop. For now, we assume the
2603  // worst: there is a store in the loop that alias with this read.
2604  // The case where the load is outside the loop is already covered by the
2605  // dominator check above.
2606  // TODO: relax this condition
2607  if (OrigI->mayReadFromMemory())
2608  return false;
2609 
2610  for (auto *Op : OrigI->operand_values()) {
2611  if (!isa<Instruction>(Op))
2612  continue;
2613  // Stop now if we find an unsafe operand.
2614  auto OISIt = OpSafeForPHIOfOps.find(OrigI);
2615  if (OISIt != OpSafeForPHIOfOps.end()) {
2616  if (!OISIt->second) {
2617  OpSafeForPHIOfOps.insert({V, false});
2618  return false;
2619  }
2620  continue;
2621  }
2622  if (!Visited.insert(Op).second)
2623  continue;
2624  Worklist.push_back(cast<Instruction>(Op));
2625  }
2626  return true;
2627 }
2628 
2629 // Return true if this operand will be safe to use for phi of ops.
2630 //
2631 // The reason some operands are unsafe is that we are not trying to recursively
2632 // translate everything back through phi nodes. We actually expect some lookups
2633 // of expressions to fail. In particular, a lookup where the expression cannot
2634 // exist in the predecessor. This is true even if the expression, as shown, can
2635 // be determined to be constant.
2636 bool NewGVN::OpIsSafeForPHIOfOps(Value *V, const BasicBlock *PHIBlock,
2637  SmallPtrSetImpl<const Value *> &Visited) {
2639  if (!OpIsSafeForPHIOfOpsHelper(V, PHIBlock, Visited, Worklist))
2640  return false;
2641  while (!Worklist.empty()) {
2642  auto *I = Worklist.pop_back_val();
2643  if (!OpIsSafeForPHIOfOpsHelper(I, PHIBlock, Visited, Worklist))
2644  return false;
2645  }
2646  OpSafeForPHIOfOps.insert({V, true});
2647  return true;
2648 }
2649 
2650 // Try to find a leader for instruction TransInst, which is a phi translated
2651 // version of something in our original program. Visited is used to ensure we
2652 // don't infinite loop during translations of cycles. OrigInst is the
2653 // instruction in the original program, and PredBB is the predecessor we
2654 // translated it through.
2655 Value *NewGVN::findLeaderForInst(Instruction *TransInst,
2656  SmallPtrSetImpl<Value *> &Visited,
2657  MemoryAccess *MemAccess, Instruction *OrigInst,
2658  BasicBlock *PredBB) {
2659  unsigned IDFSNum = InstrToDFSNum(OrigInst);
2660  // Make sure it's marked as a temporary instruction.
2661  AllTempInstructions.insert(TransInst);
2662  // and make sure anything that tries to add it's DFS number is
2663  // redirected to the instruction we are making a phi of ops
2664  // for.
2665  TempToBlock.insert({TransInst, PredBB});
2666  InstrDFS.insert({TransInst, IDFSNum});
2667 
2668  auto Res = performSymbolicEvaluation(TransInst, Visited);
2669  const Expression *E = Res.Expr;
2670  addAdditionalUsers(Res, OrigInst);
2671  InstrDFS.erase(TransInst);
2672  AllTempInstructions.erase(TransInst);
2673  TempToBlock.erase(TransInst);
2674  if (MemAccess)
2675  TempToMemory.erase(TransInst);
2676  if (!E)
2677  return nullptr;
2678  auto *FoundVal = findPHIOfOpsLeader(E, OrigInst, PredBB);
2679  if (!FoundVal) {
2680  ExpressionToPhiOfOps[E].insert(OrigInst);
2681  LLVM_DEBUG(dbgs() << "Cannot find phi of ops operand for " << *TransInst
2682  << " in block " << getBlockName(PredBB) << "\n");
2683  return nullptr;
2684  }
2685  if (auto *SI = dyn_cast<StoreInst>(FoundVal))
2686  FoundVal = SI->getValueOperand();
2687  return FoundVal;
2688 }
2689 
2690 // When we see an instruction that is an op of phis, generate the equivalent phi
2691 // of ops form.
2692 const Expression *
2693 NewGVN::makePossiblePHIOfOps(Instruction *I,
2694  SmallPtrSetImpl<Value *> &Visited) {
2695  if (!okayForPHIOfOps(I))
2696  return nullptr;
2697 
2698  if (!Visited.insert(I).second)
2699  return nullptr;
2700  // For now, we require the instruction be cycle free because we don't
2701  // *always* create a phi of ops for instructions that could be done as phi
2702  // of ops, we only do it if we think it is useful. If we did do it all the
2703  // time, we could remove the cycle free check.
2704  if (!isCycleFree(I))
2705  return nullptr;
2706 
2707  SmallPtrSet<const Value *, 8> ProcessedPHIs;
2708  // TODO: We don't do phi translation on memory accesses because it's
2709  // complicated. For a load, we'd need to be able to simulate a new memoryuse,
2710  // which we don't have a good way of doing ATM.
2711  auto *MemAccess = getMemoryAccess(I);
2712  // If the memory operation is defined by a memory operation this block that
2713  // isn't a MemoryPhi, transforming the pointer backwards through a scalar phi
2714  // can't help, as it would still be killed by that memory operation.
2715  if (MemAccess && !isa<MemoryPhi>(MemAccess->getDefiningAccess()) &&
2716  MemAccess->getDefiningAccess()->getBlock() == I->getParent())
2717  return nullptr;
2718 
2719  // Convert op of phis to phi of ops
2720  SmallPtrSet<const Value *, 10> VisitedOps;
2721  SmallVector<Value *, 4> Ops(I->operand_values());
2722  BasicBlock *SamePHIBlock = nullptr;
2723  PHINode *OpPHI = nullptr;
2724  if (!DebugCounter::shouldExecute(PHIOfOpsCounter))
2725  return nullptr;
2726  for (auto *Op : Ops) {
2727  if (!isa<PHINode>(Op)) {
2728  auto *ValuePHI = RealToTemp.lookup(Op);
2729  if (!ValuePHI)
2730  continue;
2731  LLVM_DEBUG(dbgs() << "Found possible dependent phi of ops\n");
2732  Op = ValuePHI;
2733  }
2734  OpPHI = cast<PHINode>(Op);
2735  if (!SamePHIBlock) {
2736  SamePHIBlock = getBlockForValue(OpPHI);
2737  } else if (SamePHIBlock != getBlockForValue(OpPHI)) {
2738  LLVM_DEBUG(
2739  dbgs()
2740  << "PHIs for operands are not all in the same block, aborting\n");
2741  return nullptr;
2742  }
2743  // No point in doing this for one-operand phis.
2744  if (OpPHI->getNumOperands() == 1) {
2745  OpPHI = nullptr;
2746  continue;
2747  }
2748  }
2749 
2750  if (!OpPHI)
2751  return nullptr;
2752 
2753  SmallVector<ValPair, 4> PHIOps;
2755  auto *PHIBlock = getBlockForValue(OpPHI);
2756  RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(I));
2757  for (unsigned PredNum = 0; PredNum < OpPHI->getNumOperands(); ++PredNum) {
2758  auto *PredBB = OpPHI->getIncomingBlock(PredNum);
2759  Value *FoundVal = nullptr;
2760  SmallPtrSet<Value *, 4> CurrentDeps;
2761  // We could just skip unreachable edges entirely but it's tricky to do
2762  // with rewriting existing phi nodes.
2763  if (ReachableEdges.count({PredBB, PHIBlock})) {
2764  // Clone the instruction, create an expression from it that is
2765  // translated back into the predecessor, and see if we have a leader.
2766  Instruction *ValueOp = I->clone();
2767  if (MemAccess)
2768  TempToMemory.insert({ValueOp, MemAccess});
2769  bool SafeForPHIOfOps = true;
2770  VisitedOps.clear();
2771  for (auto &Op : ValueOp->operands()) {
2772  auto *OrigOp = &*Op;
2773  // When these operand changes, it could change whether there is a
2774  // leader for us or not, so we have to add additional users.
2775  if (isa<PHINode>(Op)) {
2776  Op = Op->DoPHITranslation(PHIBlock, PredBB);
2777  if (Op != OrigOp && Op != I)
2778  CurrentDeps.insert(Op);
2779  } else if (auto *ValuePHI = RealToTemp.lookup(Op)) {
2780  if (getBlockForValue(ValuePHI) == PHIBlock)
2781  Op = ValuePHI->getIncomingValueForBlock(PredBB);
2782  }
2783  // If we phi-translated the op, it must be safe.
2784  SafeForPHIOfOps =
2785  SafeForPHIOfOps &&
2786  (Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps));
2787  }
2788  // FIXME: For those things that are not safe we could generate
2789  // expressions all the way down, and see if this comes out to a
2790  // constant. For anything where that is true, and unsafe, we should
2791  // have made a phi-of-ops (or value numbered it equivalent to something)
2792  // for the pieces already.
2793  FoundVal = !SafeForPHIOfOps ? nullptr
2794  : findLeaderForInst(ValueOp, Visited,
2795  MemAccess, I, PredBB);
2796  ValueOp->deleteValue();
2797  if (!FoundVal) {
2798  // We failed to find a leader for the current ValueOp, but this might
2799  // change in case of the translated operands change.
2800  if (SafeForPHIOfOps)
2801  for (auto Dep : CurrentDeps)
2802  addAdditionalUsers(Dep, I);
2803 
2804  return nullptr;
2805  }
2806  Deps.insert(CurrentDeps.begin(), CurrentDeps.end());
2807  } else {
2808  LLVM_DEBUG(dbgs() << "Skipping phi of ops operand for incoming block "
2809  << getBlockName(PredBB)
2810  << " because the block is unreachable\n");
2811  FoundVal = PoisonValue::get(I->getType());
2812  RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
2813  }
2814 
2815  PHIOps.push_back({FoundVal, PredBB});
2816  LLVM_DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in "
2817  << getBlockName(PredBB) << "\n");
2818  }
2819  for (auto Dep : Deps)
2820  addAdditionalUsers(Dep, I);
2821  sortPHIOps(PHIOps);
2822  auto *E = performSymbolicPHIEvaluation(PHIOps, I, PHIBlock);
2823  if (isa<ConstantExpression>(E) || isa<VariableExpression>(E)) {
2824  LLVM_DEBUG(
2825  dbgs()
2826  << "Not creating real PHI of ops because it simplified to existing "
2827  "value or constant\n");
2828  // We have leaders for all operands, but do not create a real PHI node with
2829  // those leaders as operands, so the link between the operands and the
2830  // PHI-of-ops is not materialized in the IR. If any of those leaders
2831  // changes, the PHI-of-op may change also, so we need to add the operands as
2832  // additional users.
2833  for (auto &O : PHIOps)
2834  addAdditionalUsers(O.first, I);
2835 
2836  return E;
2837  }
2838  auto *ValuePHI = RealToTemp.lookup(I);
2839  bool NewPHI = false;
2840  if (!ValuePHI) {
2841  ValuePHI =
2842  PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops");
2843  addPhiOfOps(ValuePHI, PHIBlock, I);
2844  NewPHI = true;
2845  NumGVNPHIOfOpsCreated++;
2846  }
2847  if (NewPHI) {
2848  for (auto PHIOp : PHIOps)
2849  ValuePHI->addIncoming(PHIOp.first, PHIOp.second);
2850  } else {
2851  TempToBlock[ValuePHI] = PHIBlock;
2852  unsigned int i = 0;
2853  for (auto PHIOp : PHIOps) {
2854  ValuePHI->setIncomingValue(i, PHIOp.first);
2855  ValuePHI->setIncomingBlock(i, PHIOp.second);
2856  ++i;
2857  }
2858  }
2859  RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
2860  LLVM_DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I
2861  << "\n");
2862 
2863  return E;
2864 }
2865 
2866 // The algorithm initially places the values of the routine in the TOP
2867 // congruence class. The leader of TOP is the undetermined value `poison`.
2868 // When the algorithm has finished, values still in TOP are unreachable.
2869 void NewGVN::initializeCongruenceClasses(Function &F) {
2870  NextCongruenceNum = 0;
2871 
2872  // Note that even though we use the live on entry def as a representative
2873  // MemoryAccess, it is *not* the same as the actual live on entry def. We
2874  // have no real equivalent to poison for MemoryAccesses, and so we really
2875  // should be checking whether the MemoryAccess is top if we want to know if it
2876  // is equivalent to everything. Otherwise, what this really signifies is that
2877  // the access "it reaches all the way back to the beginning of the function"
2878 
2879  // Initialize all other instructions to be in TOP class.
2880  TOPClass = createCongruenceClass(nullptr, nullptr);
2881  TOPClass->setMemoryLeader(MSSA->getLiveOnEntryDef());
2882  // The live on entry def gets put into it's own class
2883  MemoryAccessToClass[MSSA->getLiveOnEntryDef()] =
2884  createMemoryClass(MSSA->getLiveOnEntryDef());
2885 
2886  for (auto DTN : nodes(DT)) {
2887  BasicBlock *BB = DTN->getBlock();
2888  // All MemoryAccesses are equivalent to live on entry to start. They must
2889  // be initialized to something so that initial changes are noticed. For
2890  // the maximal answer, we initialize them all to be the same as
2891  // liveOnEntry.
2892  auto *MemoryBlockDefs = MSSA->getBlockDefs(BB);
2893  if (MemoryBlockDefs)
2894  for (const auto &Def : *MemoryBlockDefs) {
2895  MemoryAccessToClass[&Def] = TOPClass;
2896  auto *MD = dyn_cast<MemoryDef>(&Def);
2897  // Insert the memory phis into the member list.
2898  if (!MD) {
2899  const MemoryPhi *MP = cast<MemoryPhi>(&Def);
2900  TOPClass->memory_insert(MP);
2901  MemoryPhiState.insert({MP, MPS_TOP});
2902  }
2903 
2904  if (MD && isa<StoreInst>(MD->getMemoryInst()))
2905  TOPClass->incStoreCount();
2906  }
2907 
2908  // FIXME: This is trying to discover which instructions are uses of phi
2909  // nodes. We should move this into one of the myriad of places that walk
2910  // all the operands already.
2911  for (auto &I : *BB) {
2912  if (isa<PHINode>(&I))
2913  for (auto *U : I.users())
2914  if (auto *UInst = dyn_cast<Instruction>(U))
2915  if (InstrToDFSNum(UInst) != 0 && okayForPHIOfOps(UInst))
2916  PHINodeUses.insert(UInst);
2917  // Don't insert void terminators into the class. We don't value number
2918  // them, and they just end up sitting in TOP.
2919  if (I.isTerminator() && I.getType()->isVoidTy())
2920  continue;
2921  TOPClass->insert(&I);
2922  ValueToClass[&I] = TOPClass;
2923  }
2924  }
2925 
2926  // Initialize arguments to be in their own unique congruence classes
2927  for (auto &FA : F.args())
2928  createSingletonCongruenceClass(&FA);
2929 }
2930 
2931 void NewGVN::cleanupTables() {
2932  for (unsigned i = 0, e = CongruenceClasses.size(); i != e; ++i) {
2933  LLVM_DEBUG(dbgs() << "Congruence class " << CongruenceClasses[i]->getID()
2934  << " has " << CongruenceClasses[i]->size()
2935  << " members\n");
2936  // Make sure we delete the congruence class (probably worth switching to
2937  // a unique_ptr at some point.
2938  delete CongruenceClasses[i];
2939  CongruenceClasses[i] = nullptr;
2940  }
2941 
2942  // Destroy the value expressions
2943  SmallVector<Instruction *, 8> TempInst(AllTempInstructions.begin(),
2944  AllTempInstructions.end());
2945  AllTempInstructions.clear();
2946 
2947  // We have to drop all references for everything first, so there are no uses
2948  // left as we delete them.
2949  for (auto *I : TempInst) {
2950  I->dropAllReferences();
2951  }
2952 
2953  while (!TempInst.empty()) {
2954  auto *I = TempInst.pop_back_val();
2955  I->deleteValue();
2956  }
2957 
2958  ValueToClass.clear();
2959  ArgRecycler.clear(ExpressionAllocator);
2960  ExpressionAllocator.Reset();
2961  CongruenceClasses.clear();
2962  ExpressionToClass.clear();
2963  ValueToExpression.clear();
2964  RealToTemp.clear();
2965  AdditionalUsers.clear();
2966  ExpressionToPhiOfOps.clear();
2967  TempToBlock.clear();
2968  TempToMemory.clear();
2969  PHINodeUses.clear();
2970  OpSafeForPHIOfOps.clear();
2971  ReachableBlocks.clear();
2972  ReachableEdges.clear();
2973 #ifndef NDEBUG
2974  ProcessedCount.clear();
2975 #endif
2976  InstrDFS.clear();
2977  InstructionsToErase.clear();
2978  DFSToInstr.clear();
2979  BlockInstRange.clear();
2980  TouchedInstructions.clear();
2981  MemoryAccessToClass.clear();
2982  PredicateToUsers.clear();
2983  MemoryToUsers.clear();
2984  RevisitOnReachabilityChange.clear();
2985  IntrinsicInstPred.clear();
2986 }
2987 
2988 // Assign local DFS number mapping to instructions, and leave space for Value
2989 // PHI's.
2990 std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
2991  unsigned Start) {
2992  unsigned End = Start;
2993  if (MemoryAccess *MemPhi = getMemoryAccess(B)) {
2994  InstrDFS[MemPhi] = End++;
2995  DFSToInstr.emplace_back(MemPhi);
2996  }
2997 
2998  // Then the real block goes next.
2999  for (auto &I : *B) {
3000  // There's no need to call isInstructionTriviallyDead more than once on
3001  // an instruction. Therefore, once we know that an instruction is dead
3002  // we change its DFS number so that it doesn't get value numbered.
3003  if (isInstructionTriviallyDead(&I, TLI)) {
3004  InstrDFS[&I] = 0;
3005  LLVM_DEBUG(dbgs() << "Skipping trivially dead instruction " << I << "\n");
3006  markInstructionForDeletion(&I);
3007  continue;
3008  }
3009  if (isa<PHINode>(&I))
3010  RevisitOnReachabilityChange[B].set(End);
3011  InstrDFS[&I] = End++;
3012  DFSToInstr.emplace_back(&I);
3013  }
3014 
3015  // All of the range functions taken half-open ranges (open on the end side).
3016  // So we do not subtract one from count, because at this point it is one
3017  // greater than the last instruction.
3018  return std::make_pair(Start, End);
3019 }
3020 
3021 void NewGVN::updateProcessedCount(const Value *V) {
3022 #ifndef NDEBUG
3023  if (ProcessedCount.count(V) == 0) {
3024  ProcessedCount.insert({V, 1});
3025  } else {
3026  ++ProcessedCount[V];
3027  assert(ProcessedCount[V] < 100 &&
3028  "Seem to have processed the same Value a lot");
3029  }
3030 #endif
3031 }
3032 
3033 // Evaluate MemoryPhi nodes symbolically, just like PHI nodes
3034 void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) {
3035  // If all the arguments are the same, the MemoryPhi has the same value as the
3036  // argument. Filter out unreachable blocks and self phis from our operands.
3037  // TODO: We could do cycle-checking on the memory phis to allow valueizing for
3038  // self-phi checking.
3039  const BasicBlock *PHIBlock = MP->getBlock();
3040  auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) {
3041  return cast<MemoryAccess>(U) != MP &&
3042  !isMemoryAccessTOP(cast<MemoryAccess>(U)) &&
3043  ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock});
3044  });
3045  // If all that is left is nothing, our memoryphi is poison. We keep it as
3046  // InitialClass. Note: The only case this should happen is if we have at
3047  // least one self-argument.
3048  if (Filtered.begin() == Filtered.end()) {
3049  if (setMemoryClass(MP, TOPClass))
3050  markMemoryUsersTouched(MP);
3051  return;
3052  }
3053 
3054  // Transform the remaining operands into operand leaders.
3055  // FIXME: mapped_iterator should have a range version.
3056  auto LookupFunc = [&](const Use &U) {
3057  return lookupMemoryLeader(cast<MemoryAccess>(U));
3058  };
3059  auto MappedBegin = map_iterator(Filtered.begin(), LookupFunc);
3060  auto MappedEnd = map_iterator(Filtered.end(), LookupFunc);
3061 
3062  // and now check if all the elements are equal.
3063  // Sadly, we can't use std::equals since these are random access iterators.
3064  const auto *AllSameValue = *MappedBegin;
3065  ++MappedBegin;
3066  bool AllEqual = std::all_of(
3067  MappedBegin, MappedEnd,
3068  [&AllSameValue](const MemoryAccess *V) { return V == AllSameValue; });
3069 
3070  if (AllEqual)
3071  LLVM_DEBUG(dbgs() << "Memory Phi value numbered to " << *AllSameValue
3072  << "\n");
3073  else
3074  LLVM_DEBUG(dbgs() << "Memory Phi value numbered to itself\n");
3075  // If it's equal to something, it's in that class. Otherwise, it has to be in
3076  // a class where it is the leader (other things may be equivalent to it, but
3077  // it needs to start off in its own class, which means it must have been the
3078  // leader, and it can't have stopped being the leader because it was never
3079  // removed).
3080  CongruenceClass *CC =
3081  AllEqual ? getMemoryClass(AllSameValue) : ensureLeaderOfMemoryClass(MP);
3082  auto OldState = MemoryPhiState.lookup(MP);
3083  assert(OldState != MPS_Invalid && "Invalid memory phi state");
3084  auto NewState = AllEqual ? MPS_Equivalent : MPS_Unique;
3085  MemoryPhiState[MP] = NewState;
3086  if (setMemoryClass(MP, CC) || OldState != NewState)
3087  markMemoryUsersTouched(MP);
3088 }
3089 
3090 // Value number a single instruction, symbolically evaluating, performing
3091 // congruence finding, and updating mappings.
3092 void NewGVN::valueNumberInstruction(Instruction *I) {
3093  LLVM_DEBUG(dbgs() << "Processing instruction " << *I << "\n");
3094  if (!I->isTerminator()) {
3095  const Expression *Symbolized = nullptr;
3096  SmallPtrSet<Value *, 2> Visited;
3097  if (DebugCounter::shouldExecute(VNCounter)) {
3098  auto Res = performSymbolicEvaluation(I, Visited);
3099  Symbolized = Res.Expr;
3100  addAdditionalUsers(Res, I);
3101 
3102  // Make a phi of ops if necessary
3103  if (Symbolized && !isa<ConstantExpression>(Symbolized) &&
3104  !isa<VariableExpression>(Symbolized) && PHINodeUses.count(I)) {
3105  auto *PHIE = makePossiblePHIOfOps(I, Visited);
3106  // If we created a phi of ops, use it.
3107  // If we couldn't create one, make sure we don't leave one lying around
3108  if (PHIE) {
3109  Symbolized = PHIE;
3110  } else if (auto *Op = RealToTemp.lookup(I)) {
3111  removePhiOfOps(I, Op);
3112  }
3113  }
3114  } else {
3115  // Mark the instruction as unused so we don't value number it again.
3116  InstrDFS[I] = 0;
3117  }
3118  // If we couldn't come up with a symbolic expression, use the unknown
3119  // expression
3120  if (Symbolized == nullptr)
3121  Symbolized = createUnknownExpression(I);
3122  performCongruenceFinding(I, Symbolized);
3123  } else {
3124  // Handle terminators that return values. All of them produce values we
3125  // don't currently understand. We don't place non-value producing
3126  // terminators in a class.
3127  if (!I->getType()->isVoidTy()) {
3128  auto *Symbolized = createUnknownExpression(I);
3129  performCongruenceFinding(I, Symbolized);
3130  }
3131  processOutgoingEdges(I, I->getParent());
3132  }
3133 }
3134 
3135 // Check if there is a path, using single or equal argument phi nodes, from
3136 // First to Second.
3137 bool NewGVN::singleReachablePHIPath(
3139  const MemoryAccess *Second) const {
3140  if (First == Second)
3141  return true;
3142  if (MSSA->isLiveOnEntryDef(First))
3143  return false;
3144 
3145  // This is not perfect, but as we're just verifying here, we can live with
3146  // the loss of precision. The real solution would be that of doing strongly
3147  // connected component finding in this routine, and it's probably not worth
3148  // the complexity for the time being. So, we just keep a set of visited
3149  // MemoryAccess and return true when we hit a cycle.
3150  if (!Visited.insert(First).second)
3151  return true;
3152 
3153  const auto *EndDef = First;
3154  for (auto *ChainDef : optimized_def_chain(First)) {
3155  if (ChainDef == Second)
3156  return true;
3157  if (MSSA->isLiveOnEntryDef(ChainDef))
3158  return false;
3159  EndDef = ChainDef;
3160  }
3161  auto *MP = cast<MemoryPhi>(EndDef);
3162  auto ReachableOperandPred = [&](const Use &U) {
3163  return ReachableEdges.count({MP->getIncomingBlock(U), MP->getBlock()});
3164  };
3165  auto FilteredPhiArgs =
3166  make_filter_range(MP->operands(), ReachableOperandPred);
3167  SmallVector<const Value *, 32> OperandList;
3168  llvm::copy(FilteredPhiArgs, std::back_inserter(OperandList));
3169  bool Okay = is_splat(OperandList);
3170  if (Okay)
3171  return singleReachablePHIPath(Visited, cast<MemoryAccess>(OperandList[0]),
3172  Second);
3173  return false;
3174 }
3175 
3176 // Verify the that the memory equivalence table makes sense relative to the
3177 // congruence classes. Note that this checking is not perfect, and is currently
3178 // subject to very rare false negatives. It is only useful for
3179 // testing/debugging.
3180 void NewGVN::verifyMemoryCongruency() const {
3181 #ifndef NDEBUG
3182  // Verify that the memory table equivalence and memory member set match
3183  for (const auto *CC : CongruenceClasses) {
3184  if (CC == TOPClass || CC->isDead())
3185  continue;
3186  if (CC->getStoreCount() != 0) {
3187  assert((CC->getStoredValue() || !isa<StoreInst>(CC->getLeader())) &&
3188  "Any class with a store as a leader should have a "
3189  "representative stored value");
3190  assert(CC->getMemoryLeader() &&
3191  "Any congruence class with a store should have a "
3192  "representative access");
3193  }
3194 
3195  if (CC->getMemoryLeader())
3196  assert(MemoryAccessToClass.lookup(CC->getMemoryLeader()) == CC &&
3197  "Representative MemoryAccess does not appear to be reverse "
3198  "mapped properly");
3199  for (auto M : CC->memory())
3200  assert(MemoryAccessToClass.lookup(M) == CC &&
3201  "Memory member does not appear to be reverse mapped properly");
3202  }
3203 
3204  // Anything equivalent in the MemoryAccess table should be in the same
3205  // congruence class.
3206 
3207  // Filter out the unreachable and trivially dead entries, because they may
3208  // never have been updated if the instructions were not processed.
3209  auto ReachableAccessPred =
3210  [&](const std::pair<const MemoryAccess *, CongruenceClass *> Pair) {
3211  bool Result = ReachableBlocks.count(Pair.first->getBlock());
3212  if (!Result || MSSA->isLiveOnEntryDef(Pair.first) ||
3213  MemoryToDFSNum(Pair.first) == 0)
3214  return false;
3215  if (auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
3216  return !isInstructionTriviallyDead(MemDef->getMemoryInst());
3217 
3218  // We could have phi nodes which operands are all trivially dead,
3219  // so we don't process them.
3220  if (auto *MemPHI = dyn_cast<MemoryPhi>(Pair.first)) {
3221  for (auto &U : MemPHI->incoming_values()) {
3222  if (auto *I = dyn_cast<Instruction>(&*U)) {
3224  return true;
3225  }
3226  }
3227  return false;
3228  }
3229 
3230  return true;
3231  };
3232 
3233  auto Filtered = make_filter_range(MemoryAccessToClass, ReachableAccessPred);
3234  for (auto KV : Filtered) {
3235  if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
3236  auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second->getMemoryLeader());
3237  if (FirstMUD && SecondMUD) {
3239  assert((singleReachablePHIPath(VisitedMAS, FirstMUD, SecondMUD) ||
3240  ValueToClass.lookup(FirstMUD->getMemoryInst()) ==
3241  ValueToClass.lookup(SecondMUD->getMemoryInst())) &&
3242  "The instructions for these memory operations should have "
3243  "been in the same congruence class or reachable through"
3244  "a single argument phi");
3245  }
3246  } else if (auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {
3247  // We can only sanely verify that MemoryDefs in the operand list all have
3248  // the same class.
3249  auto ReachableOperandPred = [&](const Use &U) {
3250  return ReachableEdges.count(
3251  {FirstMP->getIncomingBlock(U), FirstMP->getBlock()}) &&
3252  isa<MemoryDef>(U);
3253 
3254  };
3255  // All arguments should in the same class, ignoring unreachable arguments
3256  auto FilteredPhiArgs =
3257  make_filter_range(FirstMP->operands(), ReachableOperandPred);
3259  std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
3260  std::back_inserter(PhiOpClasses), [&](const Use &U) {
3261  const MemoryDef *MD = cast<MemoryDef>(U);
3262  return ValueToClass.lookup(MD->getMemoryInst());
3263  });
3264  assert(is_splat(PhiOpClasses) &&
3265  "All MemoryPhi arguments should be in the same class");
3266  }
3267  }
3268 #endif
3269 }
3270 
3271 // Verify that the sparse propagation we did actually found the maximal fixpoint
3272 // We do this by storing the value to class mapping, touching all instructions,
3273 // and redoing the iteration to see if anything changed.
3274 void NewGVN::verifyIterationSettled(Function &F) {
3275 #ifndef NDEBUG
3276  LLVM_DEBUG(dbgs() << "Beginning iteration verification\n");
3277  if (DebugCounter::isCounterSet(VNCounter))
3278  DebugCounter::setCounterValue(VNCounter, StartingVNCounter);
3279 
3280  // Note that we have to store the actual classes, as we may change existing
3281  // classes during iteration. This is because our memory iteration propagation
3282  // is not perfect, and so may waste a little work. But it should generate
3283  // exactly the same congruence classes we have now, with different IDs.
3284  std::map<const Value *, CongruenceClass> BeforeIteration;
3285 
3286  for (auto &KV : ValueToClass) {
3287  if (auto *I = dyn_cast<Instruction>(KV.first))
3288  // Skip unused/dead instructions.
3289  if (InstrToDFSNum(I) == 0)
3290  continue;
3291  BeforeIteration.insert({KV.first, *KV.second});
3292  }
3293 
3294  TouchedInstructions.set();
3295  TouchedInstructions.reset(0);
3296  iterateTouchedInstructions();
3298  EqualClasses;
3299  for (const auto &KV : ValueToClass) {
3300  if (auto *I = dyn_cast<Instruction>(KV.first))
3301  // Skip unused/dead instructions.
3302  if (InstrToDFSNum(I) == 0)
3303  continue;
3304  // We could sink these uses, but i think this adds a bit of clarity here as
3305  // to what we are comparing.
3306  auto *BeforeCC = &BeforeIteration.find(KV.first)->second;
3307  auto *AfterCC = KV.second;
3308  // Note that the classes can't change at this point, so we memoize the set
3309  // that are equal.
3310  if (!EqualClasses.count({BeforeCC, AfterCC})) {
3311  assert(BeforeCC->isEquivalentTo(AfterCC) &&
3312  "Value number changed after main loop completed!");
3313  EqualClasses.insert({BeforeCC, AfterCC});
3314  }
3315  }
3316 #endif
3317 }
3318 
3319 // Verify that for each store expression in the expression to class mapping,
3320 // only the latest appears, and multiple ones do not appear.
3321 // Because loads do not use the stored value when doing equality with stores,
3322 // if we don't erase the old store expressions from the table, a load can find
3323 // a no-longer valid StoreExpression.
3324 void NewGVN::verifyStoreExpressions() const {
3325 #ifndef NDEBUG
3326  // This is the only use of this, and it's not worth defining a complicated
3327  // densemapinfo hash/equality function for it.
3328  std::set<
3329  std::pair<const Value *,
3330  std::tuple<const Value *, const CongruenceClass *, Value *>>>
3331  StoreExpressionSet;
3332  for (const auto &KV : ExpressionToClass) {
3333  if (auto *SE = dyn_cast<StoreExpression>(KV.first)) {
3334  // Make sure a version that will conflict with loads is not already there
3335  auto Res = StoreExpressionSet.insert(
3336  {SE->getOperand(0), std::make_tuple(SE->getMemoryLeader(), KV.second,
3337  SE->getStoredValue())});
3338  bool Okay = Res.second;
3339  // It's okay to have the same expression already in there if it is
3340  // identical in nature.
3341  // This can happen when the leader of the stored value changes over time.
3342  if (!Okay)
3343  Okay = (std::get<1>(Res.first->second) == KV.second) &&
3344  (lookupOperandLeader(std::get<2>(Res.first->second)) ==
3345  lookupOperandLeader(SE->getStoredValue()));
3346  assert(Okay && "Stored expression conflict exists in expression table");
3347  auto *ValueExpr = ValueToExpression.lookup(SE->getStoreInst());
3348  assert(ValueExpr && ValueExpr->equals(*SE) &&
3349  "StoreExpression in ExpressionToClass is not latest "
3350  "StoreExpression for value");
3351  }
3352  }
3353 #endif
3354 }
3355 
3356 // This is the main value numbering loop, it iterates over the initial touched
3357 // instruction set, propagating value numbers, marking things touched, etc,
3358 // until the set of touched instructions is completely empty.
3359 void NewGVN::iterateTouchedInstructions() {
3360  uint64_t Iterations = 0;
3361  // Figure out where touchedinstructions starts
3362  int FirstInstr = TouchedInstructions.find_first();
3363  // Nothing set, nothing to iterate, just return.
3364  if (FirstInstr == -1)
3365  return;
3366  const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
3367  while (TouchedInstructions.any()) {
3368  ++Iterations;
3369  // Walk through all the instructions in all the blocks in RPO.
3370  // TODO: As we hit a new block, we should push and pop equalities into a
3371  // table lookupOperandLeader can use, to catch things PredicateInfo
3372  // might miss, like edge-only equivalences.
3373  for (unsigned InstrNum : TouchedInstructions.set_bits()) {
3374 
3375  // This instruction was found to be dead. We don't bother looking
3376  // at it again.
3377  if (InstrNum == 0) {
3378  TouchedInstructions.reset(InstrNum);
3379  continue;
3380  }
3381 
3382  Value *V = InstrFromDFSNum(InstrNum);
3383  const BasicBlock *CurrBlock = getBlockForValue(V);
3384 
3385  // If we hit a new block, do reachability processing.
3386  if (CurrBlock != LastBlock) {
3387  LastBlock = CurrBlock;
3388  bool BlockReachable = ReachableBlocks.count(CurrBlock);
3389  const auto &CurrInstRange = BlockInstRange.lookup(CurrBlock);
3390 
3391  // If it's not reachable, erase any touched instructions and move on.
3392  if (!BlockReachable) {
3393  TouchedInstructions.reset(CurrInstRange.first, CurrInstRange.second);
3394  LLVM_DEBUG(dbgs() << "Skipping instructions in block "
3395  << getBlockName(CurrBlock)
3396  << " because it is unreachable\n");
3397  continue;
3398  }
3399  updateProcessedCount(CurrBlock);
3400  }
3401  // Reset after processing (because we may mark ourselves as touched when
3402  // we propagate equalities).
3403  TouchedInstructions.reset(InstrNum);
3404 
3405  if (auto *MP = dyn_cast<MemoryPhi>(V)) {
3406  LLVM_DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n");
3407  valueNumberMemoryPhi(MP);
3408  } else if (auto *I = dyn_cast<Instruction>(V)) {
3409  valueNumberInstruction(I);
3410  } else {
3411  llvm_unreachable("Should have been a MemoryPhi or Instruction");
3412  }
3413  updateProcessedCount(V);
3414  }
3415  }
3416  NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations);
3417 }
3418 
3419 // This is the main transformation entry point.
3420 bool NewGVN::runGVN() {
3421  if (DebugCounter::isCounterSet(VNCounter))
3422  StartingVNCounter = DebugCounter::getCounterValue(VNCounter);
3423  bool Changed = false;
3424  NumFuncArgs = F.arg_size();
3425  MSSAWalker = MSSA->getWalker();
3426  SingletonDeadExpression = new (ExpressionAllocator) DeadExpression();
3427 
3428  // Count number of instructions for sizing of hash tables, and come
3429  // up with a global dfs numbering for instructions.
3430  unsigned ICount = 1;
3431  // Add an empty instruction to account for the fact that we start at 1
3432  DFSToInstr.emplace_back(nullptr);
3433  // Note: We want ideal RPO traversal of the blocks, which is not quite the
3434  // same as dominator tree order, particularly with regard whether backedges
3435  // get visited first or second, given a block with multiple successors.
3436  // If we visit in the wrong order, we will end up performing N times as many
3437  // iterations.
3438  // The dominator tree does guarantee that, for a given dom tree node, it's
3439  // parent must occur before it in the RPO ordering. Thus, we only need to sort
3440  // the siblings.
3442  unsigned Counter = 0;
3443  for (auto &B : RPOT) {
3444  auto *Node = DT->getNode(B);
3445  assert(Node && "RPO and Dominator tree should have same reachability");
3446  RPOOrdering[Node] = ++Counter;
3447  }
3448  // Sort dominator tree children arrays into RPO.
3449  for (auto &B : RPOT) {
3450  auto *Node = DT->getNode(B);
3451  if (Node->getNumChildren() > 1)
3452  llvm::sort(*Node, [&](const DomTreeNode *A, const DomTreeNode *B) {
3453  return RPOOrdering[A] < RPOOrdering[B];
3454  });
3455  }
3456 
3457  // Now a standard depth first ordering of the domtree is equivalent to RPO.
3458  for (auto DTN : depth_first(DT->getRootNode())) {
3459  BasicBlock *B = DTN->getBlock();
3460  const auto &BlockRange = assignDFSNumbers(B, ICount);
3461  BlockInstRange.insert({B, BlockRange});
3462  ICount += BlockRange.second - BlockRange.first;
3463  }
3464  initializeCongruenceClasses(F);
3465 
3466  TouchedInstructions.resize(ICount);
3467  // Ensure we don't end up resizing the expressionToClass map, as
3468  // that can be quite expensive. At most, we have one expression per
3469  // instruction.
3470  ExpressionToClass.reserve(ICount);
3471 
3472  // Initialize the touched instructions to include the entry block.
3473  const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock());
3474  TouchedInstructions.set(InstRange.first, InstRange.second);
3475  LLVM_DEBUG(dbgs() << "Block " << getBlockName(&F.getEntryBlock())
3476  << " marked reachable\n");
3477  ReachableBlocks.insert(&F.getEntryBlock());
3478 
3479  iterateTouchedInstructions();
3480  verifyMemoryCongruency();
3481  verifyIterationSettled(F);
3482  verifyStoreExpressions();
3483 
3484  Changed |= eliminateInstructions(F);
3485 
3486  // Delete all instructions marked for deletion.
3487  for (Instruction *ToErase : InstructionsToErase) {
3488  if (!ToErase->use_empty())
3489  ToErase->replaceAllUsesWith(PoisonValue::get(ToErase->getType()));
3490 
3491  assert(ToErase->getParent() &&
3492  "BB containing ToErase deleted unexpectedly!");
3493  ToErase->eraseFromParent();
3494  }
3495  Changed |= !InstructionsToErase.empty();
3496 
3497  // Delete all unreachable blocks.
3498  auto UnreachableBlockPred = [&](const BasicBlock &BB) {
3499  return !ReachableBlocks.count(&BB);
3500  };
3501 
3502  for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
3503  LLVM_DEBUG(dbgs() << "We believe block " << getBlockName(&BB)
3504  << " is unreachable\n");
3505  deleteInstructionsInBlock(&BB);
3506  Changed = true;
3507  }
3508 
3509  cleanupTables();
3510  return Changed;
3511 }
3512 
3514  int DFSIn = 0;
3515  int DFSOut = 0;
3516  int LocalNum = 0;
3517 
3518  // Only one of Def and U will be set.
3519  // The bool in the Def tells us whether the Def is the stored value of a
3520  // store.
3522  Use *U = nullptr;
3523 
3524  bool operator<(const ValueDFS &Other) const {
3525  // It's not enough that any given field be less than - we have sets
3526  // of fields that need to be evaluated together to give a proper ordering.
3527  // For example, if you have;
3528  // DFS (1, 3)
3529  // Val 0
3530  // DFS (1, 2)
3531  // Val 50
3532  // We want the second to be less than the first, but if we just go field
3533  // by field, we will get to Val 0 < Val 50 and say the first is less than
3534  // the second. We only want it to be less than if the DFS orders are equal.
3535  //
3536  // Each LLVM instruction only produces one value, and thus the lowest-level
3537  // differentiator that really matters for the stack (and what we use as as a
3538  // replacement) is the local dfs number.
3539  // Everything else in the structure is instruction level, and only affects
3540  // the order in which we will replace operands of a given instruction.
3541  //
3542  // For a given instruction (IE things with equal dfsin, dfsout, localnum),
3543  // the order of replacement of uses does not matter.
3544  // IE given,
3545  // a = 5
3546  // b = a + a
3547  // When you hit b, you will have two valuedfs with the same dfsin, out, and
3548  // localnum.
3549  // The .val will be the same as well.
3550  // The .u's will be different.
3551  // You will replace both, and it does not matter what order you replace them
3552  // in (IE whether you replace operand 2, then operand 1, or operand 1, then
3553  // operand 2).
3554  // Similarly for the case of same dfsin, dfsout, localnum, but different
3555  // .val's
3556  // a = 5
3557  // b = 6
3558  // c = a + b
3559  // in c, we will a valuedfs for a, and one for b,with everything the same
3560  // but .val and .u.
3561  // It does not matter what order we replace these operands in.
3562  // You will always end up with the same IR, and this is guaranteed.
3563  return std::tie(DFSIn, DFSOut, LocalNum, Def, U) <
3564  std::tie(Other.DFSIn, Other.DFSOut, Other.LocalNum, Other.Def,
3565  Other.U);
3566  }
3567 };
3568 
3569 // This function converts the set of members for a congruence class from values,
3570 // to sets of defs and uses with associated DFS info. The total number of
3571 // reachable uses for each value is stored in UseCount, and instructions that
3572 // seem
3573 // dead (have no non-dead uses) are stored in ProbablyDead.
3574 void NewGVN::convertClassToDFSOrdered(
3575  const CongruenceClass &Dense, SmallVectorImpl<ValueDFS> &DFSOrderedSet,
3577  SmallPtrSetImpl<Instruction *> &ProbablyDead) const {
3578  for (auto D : Dense) {
3579  // First add the value.
3580  BasicBlock *BB = getBlockForValue(D);
3581  // Constants are handled prior to ever calling this function, so
3582  // we should only be left with instructions as members.
3583  assert(BB && "Should have figured out a basic block for value");
3584  ValueDFS VDDef;
3585  DomTreeNode *DomNode = DT->getNode(BB);
3586  VDDef.DFSIn = DomNode->getDFSNumIn();
3587  VDDef.DFSOut = DomNode->getDFSNumOut();
3588  // If it's a store, use the leader of the value operand, if it's always
3589  // available, or the value operand. TODO: We could do dominance checks to
3590  // find a dominating leader, but not worth it ATM.
3591  if (auto *SI = dyn_cast<StoreInst>(D)) {
3592  auto Leader = lookupOperandLeader(SI->getValueOperand());
3593  if (alwaysAvailable(Leader)) {
3594  VDDef.Def.setPointer(Leader);
3595  } else {
3596  VDDef.Def.setPointer(SI->getValueOperand());
3597  VDDef.Def.setInt(true);
3598  }
3599  } else {
3600  VDDef.Def.setPointer(D);
3601  }
3602  assert(isa<Instruction>(D) &&
3603  "The dense set member should always be an instruction");
3604  Instruction *Def = cast<Instruction>(D);
3605  VDDef.LocalNum = InstrToDFSNum(D);
3606  DFSOrderedSet.push_back(VDDef);
3607  // If there is a phi node equivalent, add it
3608  if (auto *PN = RealToTemp.lookup(Def)) {
3609  auto *PHIE =
3610  dyn_cast_or_null<PHIExpression>(ValueToExpression.lookup(Def));
3611  if (PHIE) {
3612  VDDef.Def.setInt(false);
3613  VDDef.Def.setPointer(PN);
3614  VDDef.LocalNum = 0;
3615  DFSOrderedSet.push_back(VDDef);
3616  }
3617  }
3618 
3619  unsigned int UseCount = 0;
3620  // Now add the uses.
3621  for (auto &U : Def->uses()) {
3622  if (auto *I = dyn_cast<Instruction>(U.getUser())) {
3623  // Don't try to replace into dead uses
3624  if (InstructionsToErase.count(I))
3625  continue;
3626  ValueDFS VDUse;
3627  // Put the phi node uses in the incoming block.
3628  BasicBlock *IBlock;
3629  if (auto *P = dyn_cast<PHINode>(I)) {
3630  IBlock = P->getIncomingBlock(U);
3631  // Make phi node users appear last in the incoming block
3632  // they are from.
3633  VDUse.LocalNum = InstrDFS.size() + 1;
3634  } else {
3635  IBlock = getBlockForValue(I);
3636  VDUse.LocalNum = InstrToDFSNum(I);
3637  }
3638 
3639  // Skip uses in unreachable blocks, as we're going
3640  // to delete them.
3641  if (!ReachableBlocks.contains(IBlock))
3642  continue;
3643 
3644  DomTreeNode *DomNode = DT->getNode(IBlock);
3645  VDUse.DFSIn = DomNode->getDFSNumIn();
3646  VDUse.DFSOut = DomNode->getDFSNumOut();
3647  VDUse.U = &U;
3648  ++UseCount;
3649  DFSOrderedSet.emplace_back(VDUse);
3650  }
3651  }
3652 
3653  // If there are no uses, it's probably dead (but it may have side-effects,
3654  // so not definitely dead. Otherwise, store the number of uses so we can
3655  // track if it becomes dead later).
3656  if (UseCount == 0)
3657  ProbablyDead.insert(Def);
3658  else
3659  UseCounts[Def] = UseCount;
3660  }
3661 }
3662 
3663 // This function converts the set of members for a congruence class from values,
3664 // to the set of defs for loads and stores, with associated DFS info.
3665 void NewGVN::convertClassToLoadsAndStores(
3666  const CongruenceClass &Dense,
3667  SmallVectorImpl<ValueDFS> &LoadsAndStores) const {
3668  for (auto D : Dense) {
3669  if (!isa<LoadInst>(D) && !isa<StoreInst>(D))
3670  continue;
3671 
3672  BasicBlock *BB = getBlockForValue(D);
3673  ValueDFS VD;
3674  DomTreeNode *DomNode = DT->getNode(BB);
3675  VD.DFSIn = DomNode->getDFSNumIn();
3676  VD.DFSOut = DomNode->getDFSNumOut();
3677  VD.Def.setPointer(D);
3678 
3679  // If it's an instruction, use the real local dfs number.
3680  if (auto *I = dyn_cast<Instruction>(D))
3681  VD.LocalNum = InstrToDFSNum(I);
3682  else
3683  llvm_unreachable("Should have been an instruction");
3684 
3685  LoadsAndStores.emplace_back(VD);
3686  }
3687 }
3688 
3691  I->replaceAllUsesWith(Repl);
3692 }
3693 
3694 void NewGVN::deleteInstructionsInBlock(BasicBlock *BB) {
3695  LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << *BB);
3696  ++NumGVNBlocksDeleted;
3697 
3698  // Delete the instructions backwards, as it has a reduced likelihood of having
3699  // to update as many def-use and use-def chains. Start after the terminator.
3700  auto StartPoint = BB->rbegin();
3701  ++StartPoint;
3702  // Note that we explicitly recalculate BB->rend() on each iteration,
3703  // as it may change when we remove the first instruction.
3704  for (BasicBlock::reverse_iterator I(StartPoint); I != BB->rend();) {
3705  Instruction &Inst = *I++;
3706  if (!Inst.use_empty())
3708  if (isa<LandingPadInst>(Inst))
3709  continue;
3710  salvageKnowledge(&Inst, AC);
3711 
3712  Inst.eraseFromParent();
3713  ++NumGVNInstrDeleted;
3714  }
3715  // Now insert something that simplifycfg will turn into an unreachable.
3716  Type *Int8Ty = Type::getInt8Ty(BB->getContext());
3717  new StoreInst(PoisonValue::get(Int8Ty),
3719  BB->getTerminator());
3720 }
3721 
3722 void NewGVN::markInstructionForDeletion(Instruction *I) {
3723  LLVM_DEBUG(dbgs() << "Marking " << *I << " for deletion\n");
3724  InstructionsToErase.insert(I);
3725 }
3726 
3727 void NewGVN::replaceInstruction(Instruction *I, Value *V) {
3728  LLVM_DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n");
3730  // We save the actual erasing to avoid invalidating memory
3731  // dependencies until we are done with everything.
3732  markInstructionForDeletion(I);
3733 }
3734 
3735 namespace {
3736 
3737 // This is a stack that contains both the value and dfs info of where
3738 // that value is valid.
3739 class ValueDFSStack {
3740 public:
3741  Value *back() const { return ValueStack.back(); }
3742  std::pair<int, int> dfs_back() const { return DFSStack.back(); }
3743 
3744  void push_back(Value *V, int DFSIn, int DFSOut) {
3745  ValueStack.emplace_back(V);
3746  DFSStack.emplace_back(DFSIn, DFSOut);
3747  }
3748 
3749  bool empty() const { return DFSStack.empty(); }
3750 
3751  bool isInScope(int DFSIn, int DFSOut) const {
3752  if (empty())
3753  return false;
3754  return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
3755  }
3756 
3757  void popUntilDFSScope(int DFSIn, int DFSOut) {
3758 
3759  // These two should always be in sync at this point.
3760  assert(ValueStack.size() == DFSStack.size() &&
3761  "Mismatch between ValueStack and DFSStack");
3762  while (
3763  !DFSStack.empty() &&
3764  !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
3765  DFSStack.pop_back();
3766  ValueStack.pop_back();
3767  }
3768  }
3769 
3770 private:
3771  SmallVector<Value *, 8> ValueStack;
3772  SmallVector<std::pair<int, int>, 8> DFSStack;
3773 };
3774 
3775 } // end anonymous namespace
3776 
3777 // Given an expression, get the congruence class for it.
3778 CongruenceClass *NewGVN::getClassForExpression(const Expression *E) const {
3779  if (auto *VE = dyn_cast<VariableExpression>(E))
3780  return ValueToClass.lookup(VE->getVariableValue());
3781  else if (isa<DeadExpression>(E))
3782  return TOPClass;
3783  return ExpressionToClass.lookup(E);
3784 }
3785 
3786 // Given a value and a basic block we are trying to see if it is available in,
3787 // see if the value has a leader available in that block.
3788 Value *NewGVN::findPHIOfOpsLeader(const Expression *E,
3789  const Instruction *OrigInst,
3790  const BasicBlock *BB) const {
3791  // It would already be constant if we could make it constant
3792  if (auto *CE = dyn_cast<ConstantExpression>(E))
3793  return CE->getConstantValue();
3794  if (auto *VE = dyn_cast<VariableExpression>(E)) {
3795  auto *V = VE->getVariableValue();
3796  if (alwaysAvailable(V) || DT->dominates(getBlockForValue(V), BB))
3797  return VE->getVariableValue();
3798  }
3799 
3800  auto *CC = getClassForExpression(E);
3801  if (!CC)
3802  return nullptr;
3803  if (alwaysAvailable(CC->getLeader()))
3804  return CC->getLeader();
3805 
3806  for (auto Member : *CC) {
3807  auto *MemberInst = dyn_cast<Instruction>(Member);
3808  if (MemberInst == OrigInst)
3809  continue;
3810  // Anything that isn't an instruction is always available.
3811  if (!MemberInst)
3812  return Member;
3813  if (DT->dominates(getBlockForValue(MemberInst), BB))
3814  return Member;
3815  }
3816  return nullptr;
3817 }
3818 
3819 bool NewGVN::eliminateInstructions(Function &F) {
3820  // This is a non-standard eliminator. The normal way to eliminate is
3821  // to walk the dominator tree in order, keeping track of available
3822  // values, and eliminating them. However, this is mildly
3823  // pointless. It requires doing lookups on every instruction,
3824  // regardless of whether we will ever eliminate it. For
3825  // instructions part of most singleton congruence classes, we know we
3826  // will never eliminate them.
3827 
3828  // Instead, this eliminator looks at the congruence classes directly, sorts
3829  // them into a DFS ordering of the dominator tree, and then we just
3830  // perform elimination straight on the sets by walking the congruence
3831  // class member uses in order, and eliminate the ones dominated by the
3832  // last member. This is worst case O(E log E) where E = number of
3833  // instructions in a single congruence class. In theory, this is all
3834  // instructions. In practice, it is much faster, as most instructions are
3835  // either in singleton congruence classes or can't possibly be eliminated
3836  // anyway (if there are no overlapping DFS ranges in class).
3837  // When we find something not dominated, it becomes the new leader
3838  // for elimination purposes.
3839  // TODO: If we wanted to be faster, We could remove any members with no
3840  // overlapping ranges while sorting, as we will never eliminate anything
3841  // with those members, as they don't dominate anything else in our set.
3842 
3843  bool AnythingReplaced = false;
3844 
3845  // Since we are going to walk the domtree anyway, and we can't guarantee the
3846  // DFS numbers are updated, we compute some ourselves.
3847  DT->updateDFSNumbers();
3848 
3849  // Go through all of our phi nodes, and kill the arguments associated with
3850  // unreachable edges.
3851  auto ReplaceUnreachablePHIArgs = [&](PHINode *PHI, BasicBlock *BB) {
3852  for (auto &Operand : PHI->incoming_values())
3853  if (!ReachableEdges.count({PHI->getIncomingBlock(Operand), BB})) {
3854  LLVM_DEBUG(dbgs() << "Replacing incoming value of " << PHI
3855  << " for block "
3856  << getBlockName(PHI->getIncomingBlock(Operand))
3857  << " with poison due to it being unreachable\n");
3858  Operand.set(PoisonValue::get(PHI->getType()));
3859  }
3860  };
3861  // Replace unreachable phi arguments.
3862  // At this point, RevisitOnReachabilityChange only contains:
3863  //
3864  // 1. PHIs
3865  // 2. Temporaries that will convert to PHIs
3866  // 3. Operations that are affected by an unreachable edge but do not fit into
3867  // 1 or 2 (rare).
3868  // So it is a slight overshoot of what we want. We could make it exact by
3869  // using two SparseBitVectors per block.
3870  DenseMap<const BasicBlock *, unsigned> ReachablePredCount;
3871  for (auto &KV : ReachableEdges)
3872  ReachablePredCount[KV.getEnd()]++;
3873  for (auto &BBPair : RevisitOnReachabilityChange) {
3874  for (auto InstNum : BBPair.second) {
3875  auto *Inst = InstrFromDFSNum(InstNum);
3876  auto *PHI = dyn_cast<PHINode>(Inst);
3877  PHI = PHI ? PHI : dyn_cast_or_null<PHINode>(RealToTemp.lookup(Inst));
3878  if (!PHI)
3879  continue;
3880  auto *BB = BBPair.first;
3881  if (ReachablePredCount.lookup(BB) != PHI->getNumIncomingValues())
3882  ReplaceUnreachablePHIArgs(PHI, BB);
3883  }
3884  }
3885 
3886  // Map to store the use counts
3888  for (auto *CC : reverse(CongruenceClasses)) {
3889  LLVM_DEBUG(dbgs() << "Eliminating in congruence class " << CC->getID()
3890  << "\n");
3891  // Track the equivalent store info so we can decide whether to try
3892  // dead store elimination.
3893  SmallVector<ValueDFS, 8> PossibleDeadStores;
3894  SmallPtrSet<Instruction *, 8> ProbablyDead;
3895  if (CC->isDead() || CC->empty())
3896  continue;
3897  // Everything still in the TOP class is unreachable or dead.
3898  if (CC == TOPClass) {
3899  for (auto M : *CC) {
3900  auto *VTE = ValueToExpression.lookup(M);
3901  if (VTE && isa<DeadExpression>(VTE))
3902  markInstructionForDeletion(cast<Instruction>(M));
3903  assert((!ReachableBlocks.count(cast<Instruction>(M)->getParent()) ||
3904  InstructionsToErase.count(cast<Instruction>(M))) &&
3905  "Everything in TOP should be unreachable or dead at this "
3906  "point");
3907  }
3908  continue;
3909  }
3910 
3911  assert(CC->getLeader() && "We should have had a leader");
3912  // If this is a leader that is always available, and it's a
3913  // constant or has no equivalences, just replace everything with
3914  // it. We then update the congruence class with whatever members
3915  // are left.
3916  Value *Leader =
3917  CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
3918  if (alwaysAvailable(Leader)) {
3919  CongruenceClass::MemberSet MembersLeft;
3920  for (auto M : *CC) {
3921  Value *Member = M;
3922  // Void things have no uses we can replace.
3923  if (Member == Leader || !isa<Instruction>(Member) ||
3924  Member->getType()->isVoidTy()) {
3925  MembersLeft.insert(Member);
3926  continue;
3927  }
3928  LLVM_DEBUG(dbgs() << "Found replacement " << *(Leader) << " for "
3929  << *Member << "\n");
3930  auto *I = cast<Instruction>(Member);
3931  assert(Leader != I && "About to accidentally remove our leader");
3932  replaceInstruction(I, Leader);
3933  AnythingReplaced = true;
3934  }
3935  CC->swap(MembersLeft);
3936  } else {
3937  // If this is a singleton, we can skip it.
3938  if (CC->size() != 1 || RealToTemp.count(Leader)) {
3939  // This is a stack because equality replacement/etc may place
3940  // constants in the middle of the member list, and we want to use
3941  // those constant values in preference to the current leader, over
3942  // the scope of those constants.
3943  ValueDFSStack EliminationStack;
3944 
3945  // Convert the members to DFS ordered sets and then merge them.
3946  SmallVector<ValueDFS, 8> DFSOrderedSet;
3947  convertClassToDFSOrdered(*CC, DFSOrderedSet, UseCounts, ProbablyDead);
3948 
3949  // Sort the whole thing.
3950  llvm::sort(DFSOrderedSet);
3951  for (auto &VD : DFSOrderedSet) {
3952  int MemberDFSIn = VD.DFSIn;
3953  int MemberDFSOut = VD.DFSOut;
3954  Value *Def = VD.Def.getPointer();
3955  bool FromStore = VD.Def.getInt();
3956  Use *U = VD.U;
3957  // We ignore void things because we can't get a value from them.
3958  if (Def && Def->getType()->isVoidTy())
3959  continue;
3960  auto *DefInst = dyn_cast_or_null<Instruction>(Def);
3961  if (DefInst && AllTempInstructions.count(DefInst)) {
3962  auto *PN = cast<PHINode>(DefInst);
3963 
3964  // If this is a value phi and that's the expression we used, insert
3965  // it into the program
3966  // remove from temp instruction list.
3967  AllTempInstructions.erase(PN);
3968  auto *DefBlock = getBlockForValue(Def);
3969  LLVM_DEBUG(dbgs() << "Inserting fully real phi of ops" << *Def
3970  << " into block "
3971  << getBlockName(getBlockForValue(Def)) << "\n");
3972  PN->insertBefore(&DefBlock->front());
3973  Def = PN;
3974  NumGVNPHIOfOpsEliminations++;
3975  }
3976 
3977  if (EliminationStack.empty()) {
3978  LLVM_DEBUG(dbgs() << "Elimination Stack is empty\n");
3979  } else {
3980  LLVM_DEBUG(dbgs() << "Elimination Stack Top DFS numbers are ("
3981  << EliminationStack.dfs_back().first << ","
3982  << EliminationStack.dfs_back().second << ")\n");
3983  }
3984 
3985  LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << MemberDFSIn << ","
3986  << MemberDFSOut << ")\n");
3987  // First, we see if we are out of scope or empty. If so,
3988  // and there equivalences, we try to replace the top of
3989  // stack with equivalences (if it's on the stack, it must
3990  // not have been eliminated yet).
3991  // Then we synchronize to our current scope, by
3992  // popping until we are back within a DFS scope that
3993  // dominates the current member.
3994  // Then, what happens depends on a few factors
3995  // If the stack is now empty, we need to push
3996  // If we have a constant or a local equivalence we want to
3997  // start using, we also push.
3998  // Otherwise, we walk along, processing members who are
3999  // dominated by this scope, and eliminate them.
4000  bool ShouldPush = Def && EliminationStack.empty();
4001  bool OutOfScope =
4002  !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
4003 
4004  if (OutOfScope || ShouldPush) {
4005  // Sync to our current scope.
4006  EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4007  bool ShouldPush = Def && EliminationStack.empty();
4008  if (ShouldPush) {
4009  EliminationStack.push_back(Def, MemberDFSIn, MemberDFSOut);
4010  }
4011  }
4012 
4013  // Skip the Def's, we only want to eliminate on their uses. But mark
4014  // dominated defs as dead.
4015  if (Def) {
4016  // For anything in this case, what and how we value number
4017  // guarantees that any side-effets that would have occurred (ie
4018  // throwing, etc) can be proven to either still occur (because it's
4019  // dominated by something that has the same side-effects), or never
4020  // occur. Otherwise, we would not have been able to prove it value
4021  // equivalent to something else. For these things, we can just mark
4022  // it all dead. Note that this is different from the "ProbablyDead"
4023  // set, which may not be dominated by anything, and thus, are only
4024  // easy to prove dead if they are also side-effect free. Note that
4025  // because stores are put in terms of the stored value, we skip
4026  // stored values here. If the stored value is really dead, it will
4027  // still be marked for deletion when we process it in its own class.
4028  if (!EliminationStack.empty() && Def != EliminationStack.back() &&
4029  isa<Instruction>(Def) && !FromStore)
4030  markInstructionForDeletion(cast<Instruction>(Def));
4031  continue;
4032  }
4033  // At this point, we know it is a Use we are trying to possibly
4034  // replace.
4035 
4036  assert(isa<Instruction>(U->get()) &&
4037  "Current def should have been an instruction");
4038  assert(isa<Instruction>(U->getUser()) &&
4039  "Current user should have been an instruction");
4040 
4041  // If the thing we are replacing into is already marked to be dead,
4042  // this use is dead. Note that this is true regardless of whether
4043  // we have anything dominating the use or not. We do this here
4044  // because we are already walking all the uses anyway.
4045  Instruction *InstUse = cast<Instruction>(U->getUser());
4046  if (InstructionsToErase.count(InstUse)) {
4047  auto &UseCount = UseCounts[U->get()];
4048  if (--UseCount == 0) {
4049  ProbablyDead.insert(cast<Instruction>(U->get()));
4050  }
4051  }
4052 
4053  // If we get to this point, and the stack is empty we must have a use
4054  // with nothing we can use to eliminate this use, so just skip it.
4055  if (EliminationStack.empty())
4056  continue;
4057 
4058  Value *DominatingLeader = EliminationStack.back();
4059 
4060  auto *II = dyn_cast<IntrinsicInst>(DominatingLeader);
4061  bool isSSACopy = II && II->getIntrinsicID() == Intrinsic::ssa_copy;
4062  if (isSSACopy)
4063  DominatingLeader = II->getOperand(0);
4064 
4065  // Don't replace our existing users with ourselves.
4066  if (U->get() == DominatingLeader)
4067  continue;
4068  LLVM_DEBUG(dbgs()
4069  << "Found replacement " << *DominatingLeader << " for "
4070  << *U->get() << " in " << *(U->getUser()) << "\n");
4071 
4072  // If we replaced something in an instruction, handle the patching of
4073  // metadata. Skip this if we are replacing predicateinfo with its
4074  // original operand, as we already know we can just drop it.
4075  auto *ReplacedInst = cast<Instruction>(U->get());
4076  auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
4077  if (!PI || DominatingLeader != PI->OriginalOp)
4078  patchReplacementInstruction(ReplacedInst, DominatingLeader);
4079  U->set(DominatingLeader);
4080  // This is now a use of the dominating leader, which means if the
4081  // dominating leader was dead, it's now live!
4082  auto &LeaderUseCount = UseCounts[DominatingLeader];
4083  // It's about to be alive again.
4084  if (LeaderUseCount == 0 && isa<Instruction>(DominatingLeader))
4085  ProbablyDead.erase(cast<Instruction>(DominatingLeader));
4086  // For copy instructions, we use their operand as a leader,
4087  // which means we remove a user of the copy and it may become dead.
4088  if (isSSACopy) {
4089  unsigned &IIUseCount = UseCounts[II];
4090  if (--IIUseCount == 0)
4091  ProbablyDead.insert(II);
4092  }
4093  ++LeaderUseCount;
4094  AnythingReplaced = true;
4095  }
4096  }
4097  }
4098 
4099  // At this point, anything still in the ProbablyDead set is actually dead if
4100  // would be trivially dead.
4101  for (auto *I : ProbablyDead)
4103  markInstructionForDeletion(I);
4104 
4105  // Cleanup the congruence class.
4106  CongruenceClass::MemberSet MembersLeft;
4107  for (auto *Member : *CC)
4108  if (!isa<Instruction>(Member) ||
4109  !InstructionsToErase.count(cast<Instruction>(Member)))
4110  MembersLeft.insert(Member);
4111  CC->swap(MembersLeft);
4112 
4113  // If we have possible dead stores to look at, try to eliminate them.
4114  if (CC->getStoreCount() > 0) {
4115  convertClassToLoadsAndStores(*CC, PossibleDeadStores);
4116  llvm::sort(PossibleDeadStores);
4117  ValueDFSStack EliminationStack;
4118  for (auto &VD : PossibleDeadStores) {
4119  int MemberDFSIn = VD.DFSIn;
4120  int MemberDFSOut = VD.DFSOut;
4121  Instruction *Member = cast<Instruction>(VD.Def.getPointer());
4122  if (EliminationStack.empty() ||
4123  !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) {
4124  // Sync to our current scope.
4125  EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4126  if (EliminationStack.empty()) {
4127  EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
4128  continue;
4129  }
4130  }
4131  // We already did load elimination, so nothing to do here.
4132  if (isa<LoadInst>(Member))
4133  continue;
4134  assert(!EliminationStack.empty());
4135  Instruction *Leader = cast<Instruction>(EliminationStack.back());
4136  (void)Leader;
4137  assert(DT->dominates(Leader->getParent(), Member->getParent()));
4138  // Member is dominater by Leader, and thus dead
4139  LLVM_DEBUG(dbgs() << "Marking dead store " << *Member
4140  << " that is dominated by " << *Leader << "\n");
4141  markInstructionForDeletion(Member);
4142  CC->erase(Member);
4143  ++NumGVNDeadStores;
4144  }
4145  }
4146  }
4147  return AnythingReplaced;
4148 }
4149 
4150 // This function provides global ranking of operations so that we can place them
4151 // in a canonical order. Note that rank alone is not necessarily enough for a
4152 // complete ordering, as constants all have the same rank. However, generally,
4153 // we will simplify an operation with all constants so that it doesn't matter
4154 // what order they appear in.
4155 unsigned int NewGVN::getRank(const Value *V) const {
4156  // Prefer constants to undef to anything else
4157  // Undef is a constant, have to check it first.
4158  // Prefer poison to undef as it's less defined.
4159  // Prefer smaller constants to constantexprs
4160  // Note that the order here matters because of class inheritance
4161  if (isa<ConstantExpr>(V))
4162  return 3;
4163  if (isa<PoisonValue>(V))
4164  return 1;
4165  if (isa<UndefValue>(V))
4166  return 2;
4167  if (isa<Constant>(V))
4168  return 0;
4169  if (auto *A = dyn_cast<Argument>(V))
4170  return 4 + A->getArgNo();
4171 
4172  // Need to shift the instruction DFS by number of arguments + 5 to account for
4173  // the constant and argument ranking above.
4174  unsigned Result = InstrToDFSNum(V);
4175  if (Result > 0)
4176  return 5 + NumFuncArgs + Result;
4177  // Unreachable or something else, just return a really large number.
4178  return ~0;
4179 }
4180 
4181 // This is a function that says whether two commutative operations should
4182 // have their order swapped when canonicalizing.
4183 bool NewGVN::shouldSwapOperands(const Value *A, const Value *B) const {
4184  // Because we only care about a total ordering, and don't rewrite expressions
4185  // in this order, we order by rank, which will give a strict weak ordering to
4186  // everything but constants, and then we order by pointer address.
4187  return std::make_pair(getRank(A), A) > std::make_pair(getRank(B), B);
4188 }
4189 
4190 bool NewGVN::shouldSwapOperandsForIntrinsic(const Value *A, const Value *B,
4191  const IntrinsicInst *I) const {
4192  auto LookupResult = IntrinsicInstPred.find(I);
4193  if (shouldSwapOperands(A, B)) {
4194  if (LookupResult == IntrinsicInstPred.end())
4195  IntrinsicInstPred.insert({I, B});
4196  else
4197  LookupResult->second = B;
4198  return true;
4199  }
4200 
4201  if (LookupResult != IntrinsicInstPred.end()) {
4202  auto *SeenPredicate = LookupResult->second;
4203  if (SeenPredicate) {
4204  if (SeenPredicate == B)
4205  return true;
4206  else
4207  LookupResult->second = nullptr;
4208  }
4209  }
4210  return false;
4211 }
4212 
4213 namespace {
4214 
4215 class NewGVNLegacyPass : public FunctionPass {
4216 public:
4217  // Pass identification, replacement for typeid.
4218  static char ID;
4219 
4220  NewGVNLegacyPass() : FunctionPass(ID) {
4222  }
4223 
4224  bool runOnFunction(Function &F) override;
4225 
4226 private:
4227  void getAnalysisUsage(AnalysisUsage &AU) const override {
4235  }
4236 };
4237 
4238 } // end anonymous namespace
4239 
4241  if (skipFunction(F))
4242  return false;
4243  return NewGVN(F, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
4244  &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
4245  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
4246  &getAnalysis<AAResultsWrapperPass>().getAAResults(),
4247  &getAnalysis<MemorySSAWrapperPass>().getMSSA(),
4248  F.getParent()->getDataLayout())
4249  .runGVN();
4250 }
4251 
4252 char NewGVNLegacyPass::ID = 0;
4253 
4254 INITIALIZE_PASS_BEGIN(NewGVNLegacyPass, "newgvn", "Global Value Numbering",
4255  false, false)
4262 INITIALIZE_PASS_END(NewGVNLegacyPass, "newgvn", "Global Value Numbering", false,
4263  false)
4264 
4265 // createGVNPass - The public interface to this file.
4266 FunctionPass *llvm::createNewGVNPass() { return new NewGVNLegacyPass(); }
4267 
4269  // Apparently the order in which we get these results matter for
4270  // the old GVN (see Chandler's comment in GVN.cpp). I'll keep
4271  // the same order here, just in case.
4272  auto &AC = AM.getResult<AssumptionAnalysis>(F);
4273  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
4274  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
4275  auto &AA = AM.getResult<AAManager>(F);
4276  auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
4277  bool Changed =
4278  NewGVN(F, &DT, &AC, &TLI, &AA, &MSSA, F.getParent()->getDataLayout())
4279  .runGVN();
4280  if (!Changed)
4281  return PreservedAnalyses::all();
4282  PreservedAnalyses PA;
4284  return PA;
4285 }
i
i
Definition: README.txt:29
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:3689
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1303
llvm::ValueDFS::LocalNum
unsigned int LocalNum
Definition: PredicateInfo.cpp:96
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:849
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:4672
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:3513
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:740
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:935
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2737
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::BumpPtrAllocatorImpl::Reset
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:121
PredicateInfo.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
llvm::User::operands
op_range operands()
Definition: User.h:242
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:780
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:1371
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:199
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:1185
isCopyOfAPHI
static bool isCopyOfAPHI(const Value *V)
Definition: NewGVN.cpp:990
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:833
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:1008
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
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:1725
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:304
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::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
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:755
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::copy
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1668
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:147
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:79
llvm::SmallPtrSet< const Value *, 8 >
llvm::GVNExpression::StoreExpression::~StoreExpression
~StoreExpression() override
Hashing.h
llvm::MemoryPhi
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:493
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:978
equalsLoadStoreHelper
static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS)
Definition: NewGVN.cpp:907
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:260
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:107
llvm::GVNExpression::CallExpression::~CallExpression
~CallExpression() override
llvm::MemoryPhi::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned I) const
Return incoming basic block number i.
Definition: MemorySSA.h:554
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:322
llvm::DebugCounter::isCounterSet
static bool isCounterSet(unsigned ID)
Definition: DebugCounter.h:102
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:241
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:186
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
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:777
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:1617
llvm::orc::tpctypes::LookupResult
std::vector< JITTargetAddress > LookupResult
Definition: TargetProcessControlTypes.h:119
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:998
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:31
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:3524
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:306
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:511
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:751
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::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:4266
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:5552
NewGVN::ValueDFS::Def
PointerIntPair< Value *, 1, bool > Def
Definition: NewGVN.cpp:3521
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:913
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:74
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
GVNExpression.h
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
isCopyOfPHI
static bool isCopyOfPHI(const Value *V, const PHINode *PN)
Definition: NewGVN.cpp:986
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:1768
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:722
SmallPtrSet.h
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:789
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
PatternMatch.h
llvm::ExactEqualsExpression::getComputedHash
hash_code getComputedHash() const
Definition: NewGVN.cpp:437
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
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::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2743
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:770
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::SPIRV::Decoration::Component
@ Component
llvm::ExactEqualsExpression::operator==
bool operator==(const Expression &Other) const
Definition: NewGVN.cpp:439
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:1058
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:414
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:240
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:297
llvm::DebugCounter::setCounterValue
static void setCounterValue(unsigned ID, int64_t Count)
Definition: DebugCounter.h:115
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:422
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
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:112
llvm::GVNExpression
Definition: GVNExpression.h:40
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:468
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:4527
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:57
llvm::DenseMap
Definition: DenseMap.h:716
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:714
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:731
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:432
newgvn
newgvn
Definition: NewGVN.cpp:4262
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
ArrayRef.h
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
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:152
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
SI
StandardInstrumentations SI(Debug, VerifyEach)
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:2570
llvm::SimplifyQuery::getWithInstruction
SimplifyQuery getWithInstruction(Instruction *I) const
Definition: InstructionSimplify.h:120
llvm::is_splat
bool is_splat(R &&Range)
Wrapper function around std::equal to detect if all elements in a container are same.
Definition: STLExtras.h:1793
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:948
llvm::MemorySSA::getWalker
MemorySSAWalker * getWalker()
Definition: MemorySSA.cpp:1604
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:1598
llvm::GVNExpression::StoreExpression::equals
bool equals(const Expression &Other) const override
Definition: NewGVN.cpp:917
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:1208
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:395
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:4901
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:1624
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::LoadInst::isSimple
bool isSimple() const
Definition: Instructions.h:252
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:779
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::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:529
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
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:173
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:209
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:534
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:881
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:69
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:4305
llvm::Instruction::isAtomic
bool isAtomic() const
Return true if this instruction has an AtomicOrdering of unordered or higher.
Definition: Instruction.cpp:616
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:4280
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:268
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:874
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:2693
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:101
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1562
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:222
Numbering
Global Value Numbering
Definition: NewGVN.cpp:4262
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
transform
instcombine should handle this transform
Definition: README.txt:262
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
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
AA
llvm::NewGVNPass::run
PreservedAnalyses run(Function &F, AnalysisManager< Function > &AM)
Run the pass over the function.
Definition: NewGVN.cpp:4268
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
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::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:1351
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
InstructionSimplify.h
llvm::Value::deleteValue
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:106
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:148
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2767
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::PHINode
Definition: Instructions.h:2651
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< Instruction * >
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:1461
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:5406
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:2667
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:1029
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:5570
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:443
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:216
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1237
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:927
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::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
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:1787