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