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