LLVM  15.0.0git
EarlyCSE.cpp
Go to the documentation of this file.
1 //===- EarlyCSE.cpp - Simple and fast CSE 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 // This pass performs a simple dominator tree walk that eliminates trivially
10 // redundant instructions.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/DenseMapInfo.h"
16 #include "llvm/ADT/Hashing.h"
17 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/Constants.h"
32 #include "llvm/IR/Dominators.h"
33 #include "llvm/IR/Function.h"
34 #include "llvm/IR/InstrTypes.h"
35 #include "llvm/IR/Instruction.h"
36 #include "llvm/IR/Instructions.h"
37 #include "llvm/IR/IntrinsicInst.h"
38 #include "llvm/IR/LLVMContext.h"
39 #include "llvm/IR/PassManager.h"
40 #include "llvm/IR/PatternMatch.h"
41 #include "llvm/IR/Type.h"
42 #include "llvm/IR/Value.h"
43 #include "llvm/InitializePasses.h"
44 #include "llvm/Pass.h"
45 #include "llvm/Support/Allocator.h"
47 #include "llvm/Support/Casting.h"
48 #include "llvm/Support/Debug.h"
52 #include "llvm/Transforms/Scalar.h"
55 #include <cassert>
56 #include <deque>
57 #include <memory>
58 #include <utility>
59 
60 using namespace llvm;
61 using namespace llvm::PatternMatch;
62 
63 #define DEBUG_TYPE "early-cse"
64 
65 STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
66 STATISTIC(NumCSE, "Number of instructions CSE'd");
67 STATISTIC(NumCSECVP, "Number of compare instructions CVP'd");
68 STATISTIC(NumCSELoad, "Number of load instructions CSE'd");
69 STATISTIC(NumCSECall, "Number of call instructions CSE'd");
70 STATISTIC(NumDSE, "Number of trivial dead stores removed");
71 
72 DEBUG_COUNTER(CSECounter, "early-cse",
73  "Controls which instructions are removed");
74 
76  "earlycse-mssa-optimization-cap", cl::init(500), cl::Hidden,
77  cl::desc("Enable imprecision in EarlyCSE in pathological cases, in exchange "
78  "for faster compile. Caps the MemorySSA clobbering calls."));
79 
81  "earlycse-debug-hash", cl::init(false), cl::Hidden,
82  cl::desc("Perform extra assertion checking to verify that SimpleValue's hash "
83  "function is well-behaved w.r.t. its isEqual predicate"));
84 
85 //===----------------------------------------------------------------------===//
86 // SimpleValue
87 //===----------------------------------------------------------------------===//
88 
89 namespace {
90 
91 /// Struct representing the available values in the scoped hash table.
92 struct SimpleValue {
93  Instruction *Inst;
94 
95  SimpleValue(Instruction *I) : Inst(I) {
96  assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
97  }
98 
99  bool isSentinel() const {
100  return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
102  }
103 
104  static bool canHandle(Instruction *Inst) {
105  // This can only handle non-void readnone functions.
106  // Also handled are constrained intrinsic that look like the types
107  // of instruction handled below (UnaryOperator, etc.).
108  if (CallInst *CI = dyn_cast<CallInst>(Inst)) {
109  if (Function *F = CI->getCalledFunction()) {
110  switch ((Intrinsic::ID)F->getIntrinsicID()) {
111  case Intrinsic::experimental_constrained_fadd:
112  case Intrinsic::experimental_constrained_fsub:
113  case Intrinsic::experimental_constrained_fmul:
114  case Intrinsic::experimental_constrained_fdiv:
115  case Intrinsic::experimental_constrained_frem:
116  case Intrinsic::experimental_constrained_fptosi:
117  case Intrinsic::experimental_constrained_sitofp:
118  case Intrinsic::experimental_constrained_fptoui:
119  case Intrinsic::experimental_constrained_uitofp:
120  case Intrinsic::experimental_constrained_fcmp:
121  case Intrinsic::experimental_constrained_fcmps: {
122  auto *CFP = cast<ConstrainedFPIntrinsic>(CI);
123  return CFP->isDefaultFPEnvironment();
124  }
125  }
126  }
127  return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
128  }
129  return isa<CastInst>(Inst) || isa<UnaryOperator>(Inst) ||
130  isa<BinaryOperator>(Inst) || isa<GetElementPtrInst>(Inst) ||
131  isa<CmpInst>(Inst) || isa<SelectInst>(Inst) ||
132  isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
133  isa<ShuffleVectorInst>(Inst) || isa<ExtractValueInst>(Inst) ||
134  isa<InsertValueInst>(Inst) || isa<FreezeInst>(Inst);
135  }
136 };
137 
138 } // end anonymous namespace
139 
140 namespace llvm {
141 
142 template <> struct DenseMapInfo<SimpleValue> {
143  static inline SimpleValue getEmptyKey() {
145  }
146 
147  static inline SimpleValue getTombstoneKey() {
149  }
150 
151  static unsigned getHashValue(SimpleValue Val);
152  static bool isEqual(SimpleValue LHS, SimpleValue RHS);
153 };
154 
155 } // end namespace llvm
156 
157 /// Match a 'select' including an optional 'not's of the condition.
159  Value *&B,
160  SelectPatternFlavor &Flavor) {
161  // Return false if V is not even a select.
162  if (!match(V, m_Select(m_Value(Cond), m_Value(A), m_Value(B))))
163  return false;
164 
165  // Look through a 'not' of the condition operand by swapping A/B.
166  Value *CondNot;
167  if (match(Cond, m_Not(m_Value(CondNot)))) {
168  Cond = CondNot;
169  std::swap(A, B);
170  }
171 
172  // Match canonical forms of min/max. We are not using ValueTracking's
173  // more powerful matchSelectPattern() because it may rely on instruction flags
174  // such as "nsw". That would be incompatible with the current hashing
175  // mechanism that may remove flags to increase the likelihood of CSE.
176 
177  Flavor = SPF_UNKNOWN;
178  CmpInst::Predicate Pred;
179 
180  if (!match(Cond, m_ICmp(Pred, m_Specific(A), m_Specific(B)))) {
181  // Check for commuted variants of min/max by swapping predicate.
182  // If we do not match the standard or commuted patterns, this is not a
183  // recognized form of min/max, but it is still a select, so return true.
184  if (!match(Cond, m_ICmp(Pred, m_Specific(B), m_Specific(A))))
185  return true;
186  Pred = ICmpInst::getSwappedPredicate(Pred);
187  }
188 
189  switch (Pred) {
190  case CmpInst::ICMP_UGT: Flavor = SPF_UMAX; break;
191  case CmpInst::ICMP_ULT: Flavor = SPF_UMIN; break;
192  case CmpInst::ICMP_SGT: Flavor = SPF_SMAX; break;
193  case CmpInst::ICMP_SLT: Flavor = SPF_SMIN; break;
194  // Non-strict inequalities.
195  case CmpInst::ICMP_ULE: Flavor = SPF_UMIN; break;
196  case CmpInst::ICMP_UGE: Flavor = SPF_UMAX; break;
197  case CmpInst::ICMP_SLE: Flavor = SPF_SMIN; break;
198  case CmpInst::ICMP_SGE: Flavor = SPF_SMAX; break;
199  default: break;
200  }
201 
202  return true;
203 }
204 
205 static unsigned getHashValueImpl(SimpleValue Val) {
206  Instruction *Inst = Val.Inst;
207  // Hash in all of the operands as pointers.
208  if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
209  Value *LHS = BinOp->getOperand(0);
210  Value *RHS = BinOp->getOperand(1);
211  if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
212  std::swap(LHS, RHS);
213 
214  return hash_combine(BinOp->getOpcode(), LHS, RHS);
215  }
216 
217  if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
218  // Compares can be commuted by swapping the comparands and
219  // updating the predicate. Choose the form that has the
220  // comparands in sorted order, or in the case of a tie, the
221  // one with the lower predicate.
222  Value *LHS = CI->getOperand(0);
223  Value *RHS = CI->getOperand(1);
224  CmpInst::Predicate Pred = CI->getPredicate();
225  CmpInst::Predicate SwappedPred = CI->getSwappedPredicate();
226  if (std::tie(LHS, Pred) > std::tie(RHS, SwappedPred)) {
227  std::swap(LHS, RHS);
228  Pred = SwappedPred;
229  }
230  return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
231  }
232 
233  // Hash general selects to allow matching commuted true/false operands.
235  Value *Cond, *A, *B;
236  if (matchSelectWithOptionalNotCond(Inst, Cond, A, B, SPF)) {
237  // Hash min/max (cmp + select) to allow for commuted operands.
238  // Min/max may also have non-canonical compare predicate (eg, the compare for
239  // smin may use 'sgt' rather than 'slt'), and non-canonical operands in the
240  // compare.
241  // TODO: We should also detect FP min/max.
242  if (SPF == SPF_SMIN || SPF == SPF_SMAX ||
243  SPF == SPF_UMIN || SPF == SPF_UMAX) {
244  if (A > B)
245  std::swap(A, B);
246  return hash_combine(Inst->getOpcode(), SPF, A, B);
247  }
248 
249  // Hash general selects to allow matching commuted true/false operands.
250 
251  // If we do not have a compare as the condition, just hash in the condition.
252  CmpInst::Predicate Pred;
253  Value *X, *Y;
254  if (!match(Cond, m_Cmp(Pred, m_Value(X), m_Value(Y))))
255  return hash_combine(Inst->getOpcode(), Cond, A, B);
256 
257  // Similar to cmp normalization (above) - canonicalize the predicate value:
258  // select (icmp Pred, X, Y), A, B --> select (icmp InvPred, X, Y), B, A
259  if (CmpInst::getInversePredicate(Pred) < Pred) {
260  Pred = CmpInst::getInversePredicate(Pred);
261  std::swap(A, B);
262  }
263  return hash_combine(Inst->getOpcode(), Pred, X, Y, A, B);
264  }
265 
266  if (CastInst *CI = dyn_cast<CastInst>(Inst))
267  return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
268 
269  if (FreezeInst *FI = dyn_cast<FreezeInst>(Inst))
270  return hash_combine(FI->getOpcode(), FI->getOperand(0));
271 
272  if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
273  return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
274  hash_combine_range(EVI->idx_begin(), EVI->idx_end()));
275 
276  if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
277  return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
278  IVI->getOperand(1),
279  hash_combine_range(IVI->idx_begin(), IVI->idx_end()));
280 
281  assert((isa<CallInst>(Inst) || isa<GetElementPtrInst>(Inst) ||
282  isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
283  isa<ShuffleVectorInst>(Inst) || isa<UnaryOperator>(Inst) ||
284  isa<FreezeInst>(Inst)) &&
285  "Invalid/unknown instruction");
286 
287  // Handle intrinsics with commutative operands.
288  // TODO: Extend this to handle intrinsics with >2 operands where the 1st
289  // 2 operands are commutative.
290  auto *II = dyn_cast<IntrinsicInst>(Inst);
291  if (II && II->isCommutative() && II->arg_size() == 2) {
292  Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1);
293  if (LHS > RHS)
294  std::swap(LHS, RHS);
295  return hash_combine(II->getOpcode(), LHS, RHS);
296  }
297 
298  // gc.relocate is 'special' call: its second and third operands are
299  // not real values, but indices into statepoint's argument list.
300  // Get values they point to.
301  if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(Inst))
302  return hash_combine(GCR->getOpcode(), GCR->getOperand(0),
303  GCR->getBasePtr(), GCR->getDerivedPtr());
304 
305  // Mix in the opcode.
306  return hash_combine(
307  Inst->getOpcode(),
309 }
310 
311 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
312 #ifndef NDEBUG
313  // If -earlycse-debug-hash was specified, return a constant -- this
314  // will force all hashing to collide, so we'll exhaustively search
315  // the table for a match, and the assertion in isEqual will fire if
316  // there's a bug causing equal keys to hash differently.
317  if (EarlyCSEDebugHash)
318  return 0;
319 #endif
320  return getHashValueImpl(Val);
321 }
322 
323 static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS) {
324  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
325 
326  if (LHS.isSentinel() || RHS.isSentinel())
327  return LHSI == RHSI;
328 
329  if (LHSI->getOpcode() != RHSI->getOpcode())
330  return false;
331  if (LHSI->isIdenticalToWhenDefined(RHSI))
332  return true;
333 
334  // If we're not strictly identical, we still might be a commutable instruction
335  if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
336  if (!LHSBinOp->isCommutative())
337  return false;
338 
339  assert(isa<BinaryOperator>(RHSI) &&
340  "same opcode, but different instruction type?");
341  BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
342 
343  // Commuted equality
344  return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
345  LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
346  }
347  if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
348  assert(isa<CmpInst>(RHSI) &&
349  "same opcode, but different instruction type?");
350  CmpInst *RHSCmp = cast<CmpInst>(RHSI);
351  // Commuted equality
352  return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
353  LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
354  LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
355  }
356 
357  // TODO: Extend this for >2 args by matching the trailing N-2 args.
358  auto *LII = dyn_cast<IntrinsicInst>(LHSI);
359  auto *RII = dyn_cast<IntrinsicInst>(RHSI);
360  if (LII && RII && LII->getIntrinsicID() == RII->getIntrinsicID() &&
361  LII->isCommutative() && LII->arg_size() == 2) {
362  return LII->getArgOperand(0) == RII->getArgOperand(1) &&
363  LII->getArgOperand(1) == RII->getArgOperand(0);
364  }
365 
366  // See comment above in `getHashValue()`.
367  if (const GCRelocateInst *GCR1 = dyn_cast<GCRelocateInst>(LHSI))
368  if (const GCRelocateInst *GCR2 = dyn_cast<GCRelocateInst>(RHSI))
369  return GCR1->getOperand(0) == GCR2->getOperand(0) &&
370  GCR1->getBasePtr() == GCR2->getBasePtr() &&
371  GCR1->getDerivedPtr() == GCR2->getDerivedPtr();
372 
373  // Min/max can occur with commuted operands, non-canonical predicates,
374  // and/or non-canonical operands.
375  // Selects can be non-trivially equivalent via inverted conditions and swaps.
376  SelectPatternFlavor LSPF, RSPF;
377  Value *CondL, *CondR, *LHSA, *RHSA, *LHSB, *RHSB;
378  if (matchSelectWithOptionalNotCond(LHSI, CondL, LHSA, LHSB, LSPF) &&
379  matchSelectWithOptionalNotCond(RHSI, CondR, RHSA, RHSB, RSPF)) {
380  if (LSPF == RSPF) {
381  // TODO: We should also detect FP min/max.
382  if (LSPF == SPF_SMIN || LSPF == SPF_SMAX ||
383  LSPF == SPF_UMIN || LSPF == SPF_UMAX)
384  return ((LHSA == RHSA && LHSB == RHSB) ||
385  (LHSA == RHSB && LHSB == RHSA));
386 
387  // select Cond, A, B <--> select not(Cond), B, A
388  if (CondL == CondR && LHSA == RHSA && LHSB == RHSB)
389  return true;
390  }
391 
392  // If the true/false operands are swapped and the conditions are compares
393  // with inverted predicates, the selects are equal:
394  // select (icmp Pred, X, Y), A, B <--> select (icmp InvPred, X, Y), B, A
395  //
396  // This also handles patterns with a double-negation in the sense of not +
397  // inverse, because we looked through a 'not' in the matching function and
398  // swapped A/B:
399  // select (cmp Pred, X, Y), A, B <--> select (not (cmp InvPred, X, Y)), B, A
400  //
401  // This intentionally does NOT handle patterns with a double-negation in
402  // the sense of not + not, because doing so could result in values
403  // comparing
404  // as equal that hash differently in the min/max cases like:
405  // select (cmp slt, X, Y), X, Y <--> select (not (not (cmp slt, X, Y))), X, Y
406  // ^ hashes as min ^ would not hash as min
407  // In the context of the EarlyCSE pass, however, such cases never reach
408  // this code, as we simplify the double-negation before hashing the second
409  // select (and so still succeed at CSEing them).
410  if (LHSA == RHSB && LHSB == RHSA) {
411  CmpInst::Predicate PredL, PredR;
412  Value *X, *Y;
413  if (match(CondL, m_Cmp(PredL, m_Value(X), m_Value(Y))) &&
414  match(CondR, m_Cmp(PredR, m_Specific(X), m_Specific(Y))) &&
415  CmpInst::getInversePredicate(PredL) == PredR)
416  return true;
417  }
418  }
419 
420  return false;
421 }
422 
423 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
424  // These comparisons are nontrivial, so assert that equality implies
425  // hash equality (DenseMap demands this as an invariant).
426  bool Result = isEqualImpl(LHS, RHS);
427  assert(!Result || (LHS.isSentinel() && LHS.Inst == RHS.Inst) ||
429  return Result;
430 }
431 
432 //===----------------------------------------------------------------------===//
433 // CallValue
434 //===----------------------------------------------------------------------===//
435 
436 namespace {
437 
438 /// Struct representing the available call values in the scoped hash
439 /// table.
440 struct CallValue {
441  Instruction *Inst;
442 
443  CallValue(Instruction *I) : Inst(I) {
444  assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
445  }
446 
447  bool isSentinel() const {
448  return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
450  }
451 
452  static bool canHandle(Instruction *Inst) {
453  // Don't value number anything that returns void.
454  if (Inst->getType()->isVoidTy())
455  return false;
456 
457  CallInst *CI = dyn_cast<CallInst>(Inst);
458  if (!CI || !CI->onlyReadsMemory())
459  return false;
460  return true;
461  }
462 };
463 
464 } // end anonymous namespace
465 
466 namespace llvm {
467 
468 template <> struct DenseMapInfo<CallValue> {
469  static inline CallValue getEmptyKey() {
471  }
472 
473  static inline CallValue getTombstoneKey() {
475  }
476 
477  static unsigned getHashValue(CallValue Val);
478  static bool isEqual(CallValue LHS, CallValue RHS);
479 };
480 
481 } // end namespace llvm
482 
483 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
484  Instruction *Inst = Val.Inst;
485 
486  // Hash all of the operands as pointers and mix in the opcode.
487  return hash_combine(
488  Inst->getOpcode(),
490 }
491 
492 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
493  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
494  if (LHS.isSentinel() || RHS.isSentinel())
495  return LHSI == RHSI;
496 
497  return LHSI->isIdenticalTo(RHSI);
498 }
499 
500 //===----------------------------------------------------------------------===//
501 // EarlyCSE implementation
502 //===----------------------------------------------------------------------===//
503 
504 namespace {
505 
506 /// A simple and fast domtree-based CSE pass.
507 ///
508 /// This pass does a simple depth-first walk over the dominator tree,
509 /// eliminating trivially redundant instructions and using instsimplify to
510 /// canonicalize things as it goes. It is intended to be fast and catch obvious
511 /// cases so that instcombine and other passes are more effective. It is
512 /// expected that a later pass of GVN will catch the interesting/hard cases.
513 class EarlyCSE {
514 public:
515  const TargetLibraryInfo &TLI;
516  const TargetTransformInfo &TTI;
517  DominatorTree &DT;
518  AssumptionCache &AC;
519  const SimplifyQuery SQ;
520  MemorySSA *MSSA;
521  std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
522 
523  using AllocatorTy =
526  using ScopedHTType =
528  AllocatorTy>;
529 
530  /// A scoped hash table of the current values of all of our simple
531  /// scalar expressions.
532  ///
533  /// As we walk down the domtree, we look to see if instructions are in this:
534  /// if so, we replace them with what we find, otherwise we insert them so
535  /// that dominated values can succeed in their lookup.
536  ScopedHTType AvailableValues;
537 
538  /// A scoped hash table of the current values of previously encountered
539  /// memory locations.
540  ///
541  /// This allows us to get efficient access to dominating loads or stores when
542  /// we have a fully redundant load. In addition to the most recent load, we
543  /// keep track of a generation count of the read, which is compared against
544  /// the current generation count. The current generation count is incremented
545  /// after every possibly writing memory operation, which ensures that we only
546  /// CSE loads with other loads that have no intervening store. Ordering
547  /// events (such as fences or atomic instructions) increment the generation
548  /// count as well; essentially, we model these as writes to all possible
549  /// locations. Note that atomic and/or volatile loads and stores can be
550  /// present the table; it is the responsibility of the consumer to inspect
551  /// the atomicity/volatility if needed.
552  struct LoadValue {
553  Instruction *DefInst = nullptr;
554  unsigned Generation = 0;
555  int MatchingId = -1;
556  bool IsAtomic = false;
557 
558  LoadValue() = default;
559  LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,
560  bool IsAtomic)
561  : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
562  IsAtomic(IsAtomic) {}
563  };
564 
565  using LoadMapAllocator =
568  using LoadHTType =
570  LoadMapAllocator>;
571 
572  LoadHTType AvailableLoads;
573 
574  // A scoped hash table mapping memory locations (represented as typed
575  // addresses) to generation numbers at which that memory location became
576  // (henceforth indefinitely) invariant.
577  using InvariantMapAllocator =
580  using InvariantHTType =
582  InvariantMapAllocator>;
583  InvariantHTType AvailableInvariants;
584 
585  /// A scoped hash table of the current values of read-only call
586  /// values.
587  ///
588  /// It uses the same generation count as loads.
589  using CallHTType =
591  CallHTType AvailableCalls;
592 
593  /// This is the current generation of the memory value.
594  unsigned CurrentGeneration = 0;
595 
596  /// Set up the EarlyCSE runner for a particular function.
597  EarlyCSE(const DataLayout &DL, const TargetLibraryInfo &TLI,
599  AssumptionCache &AC, MemorySSA *MSSA)
600  : TLI(TLI), TTI(TTI), DT(DT), AC(AC), SQ(DL, &TLI, &DT, &AC), MSSA(MSSA),
601  MSSAUpdater(std::make_unique<MemorySSAUpdater>(MSSA)) {}
602 
603  bool run();
604 
605 private:
606  unsigned ClobberCounter = 0;
607  // Almost a POD, but needs to call the constructors for the scoped hash
608  // tables so that a new scope gets pushed on. These are RAII so that the
609  // scope gets popped when the NodeScope is destroyed.
610  class NodeScope {
611  public:
612  NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
613  InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls)
614  : Scope(AvailableValues), LoadScope(AvailableLoads),
615  InvariantScope(AvailableInvariants), CallScope(AvailableCalls) {}
616  NodeScope(const NodeScope &) = delete;
617  NodeScope &operator=(const NodeScope &) = delete;
618 
619  private:
620  ScopedHTType::ScopeTy Scope;
621  LoadHTType::ScopeTy LoadScope;
622  InvariantHTType::ScopeTy InvariantScope;
623  CallHTType::ScopeTy CallScope;
624  };
625 
626  // Contains all the needed information to create a stack for doing a depth
627  // first traversal of the tree. This includes scopes for values, loads, and
628  // calls as well as the generation. There is a child iterator so that the
629  // children do not need to be store separately.
630  class StackNode {
631  public:
632  StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
633  InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,
634  unsigned cg, DomTreeNode *n, DomTreeNode::const_iterator child,
636  : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
637  EndIter(end),
638  Scopes(AvailableValues, AvailableLoads, AvailableInvariants,
639  AvailableCalls)
640  {}
641  StackNode(const StackNode &) = delete;
642  StackNode &operator=(const StackNode &) = delete;
643 
644  // Accessors.
645  unsigned currentGeneration() const { return CurrentGeneration; }
646  unsigned childGeneration() const { return ChildGeneration; }
647  void childGeneration(unsigned generation) { ChildGeneration = generation; }
648  DomTreeNode *node() { return Node; }
649  DomTreeNode::const_iterator childIter() const { return ChildIter; }
650 
651  DomTreeNode *nextChild() {
652  DomTreeNode *child = *ChildIter;
653  ++ChildIter;
654  return child;
655  }
656 
657  DomTreeNode::const_iterator end() const { return EndIter; }
658  bool isProcessed() const { return Processed; }
659  void process() { Processed = true; }
660 
661  private:
662  unsigned CurrentGeneration;
663  unsigned ChildGeneration;
664  DomTreeNode *Node;
665  DomTreeNode::const_iterator ChildIter;
667  NodeScope Scopes;
668  bool Processed = false;
669  };
670 
671  /// Wrapper class to handle memory instructions, including loads,
672  /// stores and intrinsic loads and stores defined by the target.
673  class ParseMemoryInst {
674  public:
675  ParseMemoryInst(Instruction *Inst, const TargetTransformInfo &TTI)
676  : Inst(Inst) {
677  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
678  IntrID = II->getIntrinsicID();
679  if (TTI.getTgtMemIntrinsic(II, Info))
680  return;
681  if (isHandledNonTargetIntrinsic(IntrID)) {
682  switch (IntrID) {
683  case Intrinsic::masked_load:
684  Info.PtrVal = Inst->getOperand(0);
685  Info.MatchingId = Intrinsic::masked_load;
686  Info.ReadMem = true;
687  Info.WriteMem = false;
688  Info.IsVolatile = false;
689  break;
690  case Intrinsic::masked_store:
691  Info.PtrVal = Inst->getOperand(1);
692  // Use the ID of masked load as the "matching id". This will
693  // prevent matching non-masked loads/stores with masked ones
694  // (which could be done), but at the moment, the code here
695  // does not support matching intrinsics with non-intrinsics,
696  // so keep the MatchingIds specific to masked instructions
697  // for now (TODO).
698  Info.MatchingId = Intrinsic::masked_load;
699  Info.ReadMem = false;
700  Info.WriteMem = true;
701  Info.IsVolatile = false;
702  break;
703  }
704  }
705  }
706  }
707 
708  Instruction *get() { return Inst; }
709  const Instruction *get() const { return Inst; }
710 
711  bool isLoad() const {
712  if (IntrID != 0)
713  return Info.ReadMem;
714  return isa<LoadInst>(Inst);
715  }
716 
717  bool isStore() const {
718  if (IntrID != 0)
719  return Info.WriteMem;
720  return isa<StoreInst>(Inst);
721  }
722 
723  bool isAtomic() const {
724  if (IntrID != 0)
725  return Info.Ordering != AtomicOrdering::NotAtomic;
726  return Inst->isAtomic();
727  }
728 
729  bool isUnordered() const {
730  if (IntrID != 0)
731  return Info.isUnordered();
732 
733  if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
734  return LI->isUnordered();
735  } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
736  return SI->isUnordered();
737  }
738  // Conservative answer
739  return !Inst->isAtomic();
740  }
741 
742  bool isVolatile() const {
743  if (IntrID != 0)
744  return Info.IsVolatile;
745 
746  if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
747  return LI->isVolatile();
748  } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
749  return SI->isVolatile();
750  }
751  // Conservative answer
752  return true;
753  }
754 
755  bool isInvariantLoad() const {
756  if (auto *LI = dyn_cast<LoadInst>(Inst))
757  return LI->hasMetadata(LLVMContext::MD_invariant_load);
758  return false;
759  }
760 
761  bool isValid() const { return getPointerOperand() != nullptr; }
762 
763  // For regular (non-intrinsic) loads/stores, this is set to -1. For
764  // intrinsic loads/stores, the id is retrieved from the corresponding
765  // field in the MemIntrinsicInfo structure. That field contains
766  // non-negative values only.
767  int getMatchingId() const {
768  if (IntrID != 0)
769  return Info.MatchingId;
770  return -1;
771  }
772 
773  Value *getPointerOperand() const {
774  if (IntrID != 0)
775  return Info.PtrVal;
776  return getLoadStorePointerOperand(Inst);
777  }
778 
779  Type *getValueType() const {
780  // TODO: handle target-specific intrinsics.
781  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
782  switch (II->getIntrinsicID()) {
783  case Intrinsic::masked_load:
784  return II->getType();
785  case Intrinsic::masked_store:
786  return II->getArgOperand(0)->getType();
787  default:
788  return nullptr;
789  }
790  }
791  return getLoadStoreType(Inst);
792  }
793 
794  bool mayReadFromMemory() const {
795  if (IntrID != 0)
796  return Info.ReadMem;
797  return Inst->mayReadFromMemory();
798  }
799 
800  bool mayWriteToMemory() const {
801  if (IntrID != 0)
802  return Info.WriteMem;
803  return Inst->mayWriteToMemory();
804  }
805 
806  private:
807  Intrinsic::ID IntrID = 0;
809  Instruction *Inst;
810  };
811 
812  // This function is to prevent accidentally passing a non-target
813  // intrinsic ID to TargetTransformInfo.
814  static bool isHandledNonTargetIntrinsic(Intrinsic::ID ID) {
815  switch (ID) {
816  case Intrinsic::masked_load:
817  case Intrinsic::masked_store:
818  return true;
819  }
820  return false;
821  }
822  static bool isHandledNonTargetIntrinsic(const Value *V) {
823  if (auto *II = dyn_cast<IntrinsicInst>(V))
824  return isHandledNonTargetIntrinsic(II->getIntrinsicID());
825  return false;
826  }
827 
828  bool processNode(DomTreeNode *Node);
829 
830  bool handleBranchCondition(Instruction *CondInst, const BranchInst *BI,
831  const BasicBlock *BB, const BasicBlock *Pred);
832 
833  Value *getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
834  unsigned CurrentGeneration);
835 
836  bool overridingStores(const ParseMemoryInst &Earlier,
837  const ParseMemoryInst &Later);
838 
839  Value *getOrCreateResult(Value *Inst, Type *ExpectedType) const {
840  // TODO: We could insert relevant casts on type mismatch here.
841  if (auto *LI = dyn_cast<LoadInst>(Inst))
842  return LI->getType() == ExpectedType ? LI : nullptr;
843  else if (auto *SI = dyn_cast<StoreInst>(Inst)) {
844  Value *V = SI->getValueOperand();
845  return V->getType() == ExpectedType ? V : nullptr;
846  }
847  assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
848  auto *II = cast<IntrinsicInst>(Inst);
849  if (isHandledNonTargetIntrinsic(II->getIntrinsicID()))
850  return getOrCreateResultNonTargetMemIntrinsic(II, ExpectedType);
851  return TTI.getOrCreateResultFromMemIntrinsic(II, ExpectedType);
852  }
853 
854  Value *getOrCreateResultNonTargetMemIntrinsic(IntrinsicInst *II,
855  Type *ExpectedType) const {
856  switch (II->getIntrinsicID()) {
857  case Intrinsic::masked_load:
858  return II;
859  case Intrinsic::masked_store:
860  return II->getOperand(0);
861  }
862  return nullptr;
863  }
864 
865  /// Return true if the instruction is known to only operate on memory
866  /// provably invariant in the given "generation".
867  bool isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt);
868 
869  bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
870  Instruction *EarlierInst, Instruction *LaterInst);
871 
872  bool isNonTargetIntrinsicMatch(const IntrinsicInst *Earlier,
873  const IntrinsicInst *Later) {
874  auto IsSubmask = [](const Value *Mask0, const Value *Mask1) {
875  // Is Mask0 a submask of Mask1?
876  if (Mask0 == Mask1)
877  return true;
878  if (isa<UndefValue>(Mask0) || isa<UndefValue>(Mask1))
879  return false;
880  auto *Vec0 = dyn_cast<ConstantVector>(Mask0);
881  auto *Vec1 = dyn_cast<ConstantVector>(Mask1);
882  if (!Vec0 || !Vec1)
883  return false;
884  assert(Vec0->getType() == Vec1->getType() &&
885  "Masks should have the same type");
886  for (int i = 0, e = Vec0->getNumOperands(); i != e; ++i) {
887  Constant *Elem0 = Vec0->getOperand(i);
888  Constant *Elem1 = Vec1->getOperand(i);
889  auto *Int0 = dyn_cast<ConstantInt>(Elem0);
890  if (Int0 && Int0->isZero())
891  continue;
892  auto *Int1 = dyn_cast<ConstantInt>(Elem1);
893  if (Int1 && !Int1->isZero())
894  continue;
895  if (isa<UndefValue>(Elem0) || isa<UndefValue>(Elem1))
896  return false;
897  if (Elem0 == Elem1)
898  continue;
899  return false;
900  }
901  return true;
902  };
903  auto PtrOp = [](const IntrinsicInst *II) {
904  if (II->getIntrinsicID() == Intrinsic::masked_load)
905  return II->getOperand(0);
906  if (II->getIntrinsicID() == Intrinsic::masked_store)
907  return II->getOperand(1);
908  llvm_unreachable("Unexpected IntrinsicInst");
909  };
910  auto MaskOp = [](const IntrinsicInst *II) {
911  if (II->getIntrinsicID() == Intrinsic::masked_load)
912  return II->getOperand(2);
913  if (II->getIntrinsicID() == Intrinsic::masked_store)
914  return II->getOperand(3);
915  llvm_unreachable("Unexpected IntrinsicInst");
916  };
917  auto ThruOp = [](const IntrinsicInst *II) {
918  if (II->getIntrinsicID() == Intrinsic::masked_load)
919  return II->getOperand(3);
920  llvm_unreachable("Unexpected IntrinsicInst");
921  };
922 
923  if (PtrOp(Earlier) != PtrOp(Later))
924  return false;
925 
926  Intrinsic::ID IDE = Earlier->getIntrinsicID();
927  Intrinsic::ID IDL = Later->getIntrinsicID();
928  // We could really use specific intrinsic classes for masked loads
929  // and stores in IntrinsicInst.h.
930  if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_load) {
931  // Trying to replace later masked load with the earlier one.
932  // Check that the pointers are the same, and
933  // - masks and pass-throughs are the same, or
934  // - replacee's pass-through is "undef" and replacer's mask is a
935  // super-set of the replacee's mask.
936  if (MaskOp(Earlier) == MaskOp(Later) && ThruOp(Earlier) == ThruOp(Later))
937  return true;
938  if (!isa<UndefValue>(ThruOp(Later)))
939  return false;
940  return IsSubmask(MaskOp(Later), MaskOp(Earlier));
941  }
942  if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_load) {
943  // Trying to replace a load of a stored value with the store's value.
944  // Check that the pointers are the same, and
945  // - load's mask is a subset of store's mask, and
946  // - load's pass-through is "undef".
947  if (!IsSubmask(MaskOp(Later), MaskOp(Earlier)))
948  return false;
949  return isa<UndefValue>(ThruOp(Later));
950  }
951  if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_store) {
952  // Trying to remove a store of the loaded value.
953  // Check that the pointers are the same, and
954  // - store's mask is a subset of the load's mask.
955  return IsSubmask(MaskOp(Later), MaskOp(Earlier));
956  }
957  if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_store) {
958  // Trying to remove a dead store (earlier).
959  // Check that the pointers are the same,
960  // - the to-be-removed store's mask is a subset of the other store's
961  // mask.
962  return IsSubmask(MaskOp(Earlier), MaskOp(Later));
963  }
964  return false;
965  }
966 
967  void removeMSSA(Instruction &Inst) {
968  if (!MSSA)
969  return;
970  if (VerifyMemorySSA)
971  MSSA->verifyMemorySSA();
972  // Removing a store here can leave MemorySSA in an unoptimized state by
973  // creating MemoryPhis that have identical arguments and by creating
974  // MemoryUses whose defining access is not an actual clobber. The phi case
975  // is handled by MemorySSA when passing OptimizePhis = true to
976  // removeMemoryAccess. The non-optimized MemoryUse case is lazily updated
977  // by MemorySSA's getClobberingMemoryAccess.
978  MSSAUpdater->removeMemoryAccess(&Inst, true);
979  }
980 };
981 
982 } // end anonymous namespace
983 
984 /// Determine if the memory referenced by LaterInst is from the same heap
985 /// version as EarlierInst.
986 /// This is currently called in two scenarios:
987 ///
988 /// load p
989 /// ...
990 /// load p
991 ///
992 /// and
993 ///
994 /// x = load p
995 /// ...
996 /// store x, p
997 ///
998 /// in both cases we want to verify that there are no possible writes to the
999 /// memory referenced by p between the earlier and later instruction.
1000 bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
1001  unsigned LaterGeneration,
1002  Instruction *EarlierInst,
1003  Instruction *LaterInst) {
1004  // Check the simple memory generation tracking first.
1005  if (EarlierGeneration == LaterGeneration)
1006  return true;
1007 
1008  if (!MSSA)
1009  return false;
1010 
1011  // If MemorySSA has determined that one of EarlierInst or LaterInst does not
1012  // read/write memory, then we can safely return true here.
1013  // FIXME: We could be more aggressive when checking doesNotAccessMemory(),
1014  // onlyReadsMemory(), mayReadFromMemory(), and mayWriteToMemory() in this pass
1015  // by also checking the MemorySSA MemoryAccess on the instruction. Initial
1016  // experiments suggest this isn't worthwhile, at least for C/C++ code compiled
1017  // with the default optimization pipeline.
1018  auto *EarlierMA = MSSA->getMemoryAccess(EarlierInst);
1019  if (!EarlierMA)
1020  return true;
1021  auto *LaterMA = MSSA->getMemoryAccess(LaterInst);
1022  if (!LaterMA)
1023  return true;
1024 
1025  // Since we know LaterDef dominates LaterInst and EarlierInst dominates
1026  // LaterInst, if LaterDef dominates EarlierInst then it can't occur between
1027  // EarlierInst and LaterInst and neither can any other write that potentially
1028  // clobbers LaterInst.
1029  MemoryAccess *LaterDef;
1030  if (ClobberCounter < EarlyCSEMssaOptCap) {
1031  LaterDef = MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
1032  ClobberCounter++;
1033  } else
1034  LaterDef = LaterMA->getDefiningAccess();
1035 
1036  return MSSA->dominates(LaterDef, EarlierMA);
1037 }
1038 
1039 bool EarlyCSE::isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt) {
1040  // A location loaded from with an invariant_load is assumed to *never* change
1041  // within the visible scope of the compilation.
1042  if (auto *LI = dyn_cast<LoadInst>(I))
1043  if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1044  return true;
1045 
1046  auto MemLocOpt = MemoryLocation::getOrNone(I);
1047  if (!MemLocOpt)
1048  // "target" intrinsic forms of loads aren't currently known to
1049  // MemoryLocation::get. TODO
1050  return false;
1051  MemoryLocation MemLoc = *MemLocOpt;
1052  if (!AvailableInvariants.count(MemLoc))
1053  return false;
1054 
1055  // Is the generation at which this became invariant older than the
1056  // current one?
1057  return AvailableInvariants.lookup(MemLoc) <= GenAt;
1058 }
1059 
1060 bool EarlyCSE::handleBranchCondition(Instruction *CondInst,
1061  const BranchInst *BI, const BasicBlock *BB,
1062  const BasicBlock *Pred) {
1063  assert(BI->isConditional() && "Should be a conditional branch!");
1064  assert(BI->getCondition() == CondInst && "Wrong condition?");
1065  assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
1066  auto *TorF = (BI->getSuccessor(0) == BB)
1067  ? ConstantInt::getTrue(BB->getContext())
1068  : ConstantInt::getFalse(BB->getContext());
1069  auto MatchBinOp = [](Instruction *I, unsigned Opcode, Value *&LHS,
1070  Value *&RHS) {
1071  if (Opcode == Instruction::And &&
1073  return true;
1074  else if (Opcode == Instruction::Or &&
1076  return true;
1077  return false;
1078  };
1079  // If the condition is AND operation, we can propagate its operands into the
1080  // true branch. If it is OR operation, we can propagate them into the false
1081  // branch.
1082  unsigned PropagateOpcode =
1083  (BI->getSuccessor(0) == BB) ? Instruction::And : Instruction::Or;
1084 
1085  bool MadeChanges = false;
1088  WorkList.push_back(CondInst);
1089  while (!WorkList.empty()) {
1090  Instruction *Curr = WorkList.pop_back_val();
1091 
1092  AvailableValues.insert(Curr, TorF);
1093  LLVM_DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
1094  << Curr->getName() << "' as " << *TorF << " in "
1095  << BB->getName() << "\n");
1096  if (!DebugCounter::shouldExecute(CSECounter)) {
1097  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1098  } else {
1099  // Replace all dominated uses with the known value.
1100  if (unsigned Count = replaceDominatedUsesWith(Curr, TorF, DT,
1101  BasicBlockEdge(Pred, BB))) {
1102  NumCSECVP += Count;
1103  MadeChanges = true;
1104  }
1105  }
1106 
1107  Value *LHS, *RHS;
1108  if (MatchBinOp(Curr, PropagateOpcode, LHS, RHS))
1109  for (auto &Op : { LHS, RHS })
1110  if (Instruction *OPI = dyn_cast<Instruction>(Op))
1111  if (SimpleValue::canHandle(OPI) && Visited.insert(OPI).second)
1112  WorkList.push_back(OPI);
1113  }
1114 
1115  return MadeChanges;
1116 }
1117 
1118 Value *EarlyCSE::getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
1119  unsigned CurrentGeneration) {
1120  if (InVal.DefInst == nullptr)
1121  return nullptr;
1122  if (InVal.MatchingId != MemInst.getMatchingId())
1123  return nullptr;
1124  // We don't yet handle removing loads with ordering of any kind.
1125  if (MemInst.isVolatile() || !MemInst.isUnordered())
1126  return nullptr;
1127  // We can't replace an atomic load with one which isn't also atomic.
1128  if (MemInst.isLoad() && !InVal.IsAtomic && MemInst.isAtomic())
1129  return nullptr;
1130  // The value V returned from this function is used differently depending
1131  // on whether MemInst is a load or a store. If it's a load, we will replace
1132  // MemInst with V, if it's a store, we will check if V is the same as the
1133  // available value.
1134  bool MemInstMatching = !MemInst.isLoad();
1135  Instruction *Matching = MemInstMatching ? MemInst.get() : InVal.DefInst;
1136  Instruction *Other = MemInstMatching ? InVal.DefInst : MemInst.get();
1137 
1138  // For stores check the result values before checking memory generation
1139  // (otherwise isSameMemGeneration may crash).
1140  Value *Result = MemInst.isStore()
1141  ? getOrCreateResult(Matching, Other->getType())
1142  : nullptr;
1143  if (MemInst.isStore() && InVal.DefInst != Result)
1144  return nullptr;
1145 
1146  // Deal with non-target memory intrinsics.
1147  bool MatchingNTI = isHandledNonTargetIntrinsic(Matching);
1148  bool OtherNTI = isHandledNonTargetIntrinsic(Other);
1149  if (OtherNTI != MatchingNTI)
1150  return nullptr;
1151  if (OtherNTI && MatchingNTI) {
1152  if (!isNonTargetIntrinsicMatch(cast<IntrinsicInst>(InVal.DefInst),
1153  cast<IntrinsicInst>(MemInst.get())))
1154  return nullptr;
1155  }
1156 
1157  if (!isOperatingOnInvariantMemAt(MemInst.get(), InVal.Generation) &&
1158  !isSameMemGeneration(InVal.Generation, CurrentGeneration, InVal.DefInst,
1159  MemInst.get()))
1160  return nullptr;
1161 
1162  if (!Result)
1163  Result = getOrCreateResult(Matching, Other->getType());
1164  return Result;
1165 }
1166 
1167 bool EarlyCSE::overridingStores(const ParseMemoryInst &Earlier,
1168  const ParseMemoryInst &Later) {
1169  // Can we remove Earlier store because of Later store?
1170 
1171  assert(Earlier.isUnordered() && !Earlier.isVolatile() &&
1172  "Violated invariant");
1173  if (Earlier.getPointerOperand() != Later.getPointerOperand())
1174  return false;
1175  if (!Earlier.getValueType() || !Later.getValueType() ||
1176  Earlier.getValueType() != Later.getValueType())
1177  return false;
1178  if (Earlier.getMatchingId() != Later.getMatchingId())
1179  return false;
1180  // At the moment, we don't remove ordered stores, but do remove
1181  // unordered atomic stores. There's no special requirement (for
1182  // unordered atomics) about removing atomic stores only in favor of
1183  // other atomic stores since we were going to execute the non-atomic
1184  // one anyway and the atomic one might never have become visible.
1185  if (!Earlier.isUnordered() || !Later.isUnordered())
1186  return false;
1187 
1188  // Deal with non-target memory intrinsics.
1189  bool ENTI = isHandledNonTargetIntrinsic(Earlier.get());
1190  bool LNTI = isHandledNonTargetIntrinsic(Later.get());
1191  if (ENTI && LNTI)
1192  return isNonTargetIntrinsicMatch(cast<IntrinsicInst>(Earlier.get()),
1193  cast<IntrinsicInst>(Later.get()));
1194 
1195  // Because of the check above, at least one of them is false.
1196  // For now disallow matching intrinsics with non-intrinsics,
1197  // so assume that the stores match if neither is an intrinsic.
1198  return ENTI == LNTI;
1199 }
1200 
1201 bool EarlyCSE::processNode(DomTreeNode *Node) {
1202  bool Changed = false;
1203  BasicBlock *BB = Node->getBlock();
1204 
1205  // If this block has a single predecessor, then the predecessor is the parent
1206  // of the domtree node and all of the live out memory values are still current
1207  // in this block. If this block has multiple predecessors, then they could
1208  // have invalidated the live-out memory values of our parent value. For now,
1209  // just be conservative and invalidate memory if this block has multiple
1210  // predecessors.
1211  if (!BB->getSinglePredecessor())
1212  ++CurrentGeneration;
1213 
1214  // If this node has a single predecessor which ends in a conditional branch,
1215  // we can infer the value of the branch condition given that we took this
1216  // path. We need the single predecessor to ensure there's not another path
1217  // which reaches this block where the condition might hold a different
1218  // value. Since we're adding this to the scoped hash table (like any other
1219  // def), it will have been popped if we encounter a future merge block.
1220  if (BasicBlock *Pred = BB->getSinglePredecessor()) {
1221  auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());
1222  if (BI && BI->isConditional()) {
1223  auto *CondInst = dyn_cast<Instruction>(BI->getCondition());
1224  if (CondInst && SimpleValue::canHandle(CondInst))
1225  Changed |= handleBranchCondition(CondInst, BI, BB, Pred);
1226  }
1227  }
1228 
1229  /// LastStore - Keep track of the last non-volatile store that we saw... for
1230  /// as long as there in no instruction that reads memory. If we see a store
1231  /// to the same location, we delete the dead store. This zaps trivial dead
1232  /// stores which can occur in bitfield code among other things.
1233  Instruction *LastStore = nullptr;
1234 
1235  // See if any instructions in the block can be eliminated. If so, do it. If
1236  // not, add them to AvailableValues.
1237  for (Instruction &Inst : make_early_inc_range(BB->getInstList())) {
1238  // Dead instructions should just be removed.
1239  if (isInstructionTriviallyDead(&Inst, &TLI)) {
1240  LLVM_DEBUG(dbgs() << "EarlyCSE DCE: " << Inst << '\n');
1241  if (!DebugCounter::shouldExecute(CSECounter)) {
1242  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1243  continue;
1244  }
1245 
1246  salvageKnowledge(&Inst, &AC);
1247  salvageDebugInfo(Inst);
1248  removeMSSA(Inst);
1249  Inst.eraseFromParent();
1250  Changed = true;
1251  ++NumSimplify;
1252  continue;
1253  }
1254 
1255  // Skip assume intrinsics, they don't really have side effects (although
1256  // they're marked as such to ensure preservation of control dependencies),
1257  // and this pass will not bother with its removal. However, we should mark
1258  // its condition as true for all dominated blocks.
1259  if (auto *Assume = dyn_cast<AssumeInst>(&Inst)) {
1260  auto *CondI = dyn_cast<Instruction>(Assume->getArgOperand(0));
1261  if (CondI && SimpleValue::canHandle(CondI)) {
1262  LLVM_DEBUG(dbgs() << "EarlyCSE considering assumption: " << Inst
1263  << '\n');
1264  AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
1265  } else
1266  LLVM_DEBUG(dbgs() << "EarlyCSE skipping assumption: " << Inst << '\n');
1267  continue;
1268  }
1269 
1270  // Likewise, noalias intrinsics don't actually write.
1271  if (match(&Inst,
1272  m_Intrinsic<Intrinsic::experimental_noalias_scope_decl>())) {
1273  LLVM_DEBUG(dbgs() << "EarlyCSE skipping noalias intrinsic: " << Inst
1274  << '\n');
1275  continue;
1276  }
1277 
1278  // Skip sideeffect intrinsics, for the same reason as assume intrinsics.
1279  if (match(&Inst, m_Intrinsic<Intrinsic::sideeffect>())) {
1280  LLVM_DEBUG(dbgs() << "EarlyCSE skipping sideeffect: " << Inst << '\n');
1281  continue;
1282  }
1283 
1284  // Skip pseudoprobe intrinsics, for the same reason as assume intrinsics.
1285  if (match(&Inst, m_Intrinsic<Intrinsic::pseudoprobe>())) {
1286  LLVM_DEBUG(dbgs() << "EarlyCSE skipping pseudoprobe: " << Inst << '\n');
1287  continue;
1288  }
1289 
1290  // We can skip all invariant.start intrinsics since they only read memory,
1291  // and we can forward values across it. For invariant starts without
1292  // invariant ends, we can use the fact that the invariantness never ends to
1293  // start a scope in the current generaton which is true for all future
1294  // generations. Also, we dont need to consume the last store since the
1295  // semantics of invariant.start allow us to perform DSE of the last
1296  // store, if there was a store following invariant.start. Consider:
1297  //
1298  // store 30, i8* p
1299  // invariant.start(p)
1300  // store 40, i8* p
1301  // We can DSE the store to 30, since the store 40 to invariant location p
1302  // causes undefined behaviour.
1303  if (match(&Inst, m_Intrinsic<Intrinsic::invariant_start>())) {
1304  // If there are any uses, the scope might end.
1305  if (!Inst.use_empty())
1306  continue;
1307  MemoryLocation MemLoc =
1308  MemoryLocation::getForArgument(&cast<CallInst>(Inst), 1, TLI);
1309  // Don't start a scope if we already have a better one pushed
1310  if (!AvailableInvariants.count(MemLoc))
1311  AvailableInvariants.insert(MemLoc, CurrentGeneration);
1312  continue;
1313  }
1314 
1315  if (isGuard(&Inst)) {
1316  if (auto *CondI =
1317  dyn_cast<Instruction>(cast<CallInst>(Inst).getArgOperand(0))) {
1318  if (SimpleValue::canHandle(CondI)) {
1319  // Do we already know the actual value of this condition?
1320  if (auto *KnownCond = AvailableValues.lookup(CondI)) {
1321  // Is the condition known to be true?
1322  if (isa<ConstantInt>(KnownCond) &&
1323  cast<ConstantInt>(KnownCond)->isOne()) {
1324  LLVM_DEBUG(dbgs()
1325  << "EarlyCSE removing guard: " << Inst << '\n');
1326  salvageKnowledge(&Inst, &AC);
1327  removeMSSA(Inst);
1328  Inst.eraseFromParent();
1329  Changed = true;
1330  continue;
1331  } else
1332  // Use the known value if it wasn't true.
1333  cast<CallInst>(Inst).setArgOperand(0, KnownCond);
1334  }
1335  // The condition we're on guarding here is true for all dominated
1336  // locations.
1337  AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
1338  }
1339  }
1340 
1341  // Guard intrinsics read all memory, but don't write any memory.
1342  // Accordingly, don't update the generation but consume the last store (to
1343  // avoid an incorrect DSE).
1344  LastStore = nullptr;
1345  continue;
1346  }
1347 
1348  // If the instruction can be simplified (e.g. X+0 = X) then replace it with
1349  // its simpler value.
1350  if (Value *V = simplifyInstruction(&Inst, SQ)) {
1351  LLVM_DEBUG(dbgs() << "EarlyCSE Simplify: " << Inst << " to: " << *V
1352  << '\n');
1353  if (!DebugCounter::shouldExecute(CSECounter)) {
1354  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1355  } else {
1356  bool Killed = false;
1357  if (!Inst.use_empty()) {
1358  Inst.replaceAllUsesWith(V);
1359  Changed = true;
1360  }
1361  if (isInstructionTriviallyDead(&Inst, &TLI)) {
1362  salvageKnowledge(&Inst, &AC);
1363  removeMSSA(Inst);
1364  Inst.eraseFromParent();
1365  Changed = true;
1366  Killed = true;
1367  }
1368  if (Changed)
1369  ++NumSimplify;
1370  if (Killed)
1371  continue;
1372  }
1373  }
1374 
1375  // If this is a simple instruction that we can value number, process it.
1376  if (SimpleValue::canHandle(&Inst)) {
1377  // See if the instruction has an available value. If so, use it.
1378  if (Value *V = AvailableValues.lookup(&Inst)) {
1379  LLVM_DEBUG(dbgs() << "EarlyCSE CSE: " << Inst << " to: " << *V
1380  << '\n');
1381  if (!DebugCounter::shouldExecute(CSECounter)) {
1382  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1383  continue;
1384  }
1385  if (auto *I = dyn_cast<Instruction>(V)) {
1386  // If I being poison triggers UB, there is no need to drop those
1387  // flags. Otherwise, only retain flags present on both I and Inst.
1388  // TODO: Currently some fast-math flags are not treated as
1389  // poison-generating even though they should. Until this is fixed,
1390  // always retain flags present on both I and Inst for floating point
1391  // instructions.
1392  if (isa<FPMathOperator>(I) || (I->hasPoisonGeneratingFlags() && !programUndefinedIfPoison(I)))
1393  I->andIRFlags(&Inst);
1394  }
1395  Inst.replaceAllUsesWith(V);
1396  salvageKnowledge(&Inst, &AC);
1397  removeMSSA(Inst);
1398  Inst.eraseFromParent();
1399  Changed = true;
1400  ++NumCSE;
1401  continue;
1402  }
1403 
1404  // Otherwise, just remember that this value is available.
1405  AvailableValues.insert(&Inst, &Inst);
1406  continue;
1407  }
1408 
1409  ParseMemoryInst MemInst(&Inst, TTI);
1410  // If this is a non-volatile load, process it.
1411  if (MemInst.isValid() && MemInst.isLoad()) {
1412  // (conservatively) we can't peak past the ordering implied by this
1413  // operation, but we can add this load to our set of available values
1414  if (MemInst.isVolatile() || !MemInst.isUnordered()) {
1415  LastStore = nullptr;
1416  ++CurrentGeneration;
1417  }
1418 
1419  if (MemInst.isInvariantLoad()) {
1420  // If we pass an invariant load, we know that memory location is
1421  // indefinitely constant from the moment of first dereferenceability.
1422  // We conservatively treat the invariant_load as that moment. If we
1423  // pass a invariant load after already establishing a scope, don't
1424  // restart it since we want to preserve the earliest point seen.
1425  auto MemLoc = MemoryLocation::get(&Inst);
1426  if (!AvailableInvariants.count(MemLoc))
1427  AvailableInvariants.insert(MemLoc, CurrentGeneration);
1428  }
1429 
1430  // If we have an available version of this load, and if it is the right
1431  // generation or the load is known to be from an invariant location,
1432  // replace this instruction.
1433  //
1434  // If either the dominating load or the current load are invariant, then
1435  // we can assume the current load loads the same value as the dominating
1436  // load.
1437  LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1438  if (Value *Op = getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1439  LLVM_DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << Inst
1440  << " to: " << *InVal.DefInst << '\n');
1441  if (!DebugCounter::shouldExecute(CSECounter)) {
1442  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1443  continue;
1444  }
1445  if (!Inst.use_empty())
1446  Inst.replaceAllUsesWith(Op);
1447  salvageKnowledge(&Inst, &AC);
1448  removeMSSA(Inst);
1449  Inst.eraseFromParent();
1450  Changed = true;
1451  ++NumCSELoad;
1452  continue;
1453  }
1454 
1455  // Otherwise, remember that we have this instruction.
1456  AvailableLoads.insert(MemInst.getPointerOperand(),
1457  LoadValue(&Inst, CurrentGeneration,
1458  MemInst.getMatchingId(),
1459  MemInst.isAtomic()));
1460  LastStore = nullptr;
1461  continue;
1462  }
1463 
1464  // If this instruction may read from memory or throw (and potentially read
1465  // from memory in the exception handler), forget LastStore. Load/store
1466  // intrinsics will indicate both a read and a write to memory. The target
1467  // may override this (e.g. so that a store intrinsic does not read from
1468  // memory, and thus will be treated the same as a regular store for
1469  // commoning purposes).
1470  if ((Inst.mayReadFromMemory() || Inst.mayThrow()) &&
1471  !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
1472  LastStore = nullptr;
1473 
1474  // If this is a read-only call, process it.
1475  if (CallValue::canHandle(&Inst)) {
1476  // If we have an available version of this call, and if it is the right
1477  // generation, replace this instruction.
1478  std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(&Inst);
1479  if (InVal.first != nullptr &&
1480  isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
1481  &Inst)) {
1482  LLVM_DEBUG(dbgs() << "EarlyCSE CSE CALL: " << Inst
1483  << " to: " << *InVal.first << '\n');
1484  if (!DebugCounter::shouldExecute(CSECounter)) {
1485  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1486  continue;
1487  }
1488  if (!Inst.use_empty())
1489  Inst.replaceAllUsesWith(InVal.first);
1490  salvageKnowledge(&Inst, &AC);
1491  removeMSSA(Inst);
1492  Inst.eraseFromParent();
1493  Changed = true;
1494  ++NumCSECall;
1495  continue;
1496  }
1497 
1498  // Otherwise, remember that we have this instruction.
1499  AvailableCalls.insert(&Inst, std::make_pair(&Inst, CurrentGeneration));
1500  continue;
1501  }
1502 
1503  // A release fence requires that all stores complete before it, but does
1504  // not prevent the reordering of following loads 'before' the fence. As a
1505  // result, we don't need to consider it as writing to memory and don't need
1506  // to advance the generation. We do need to prevent DSE across the fence,
1507  // but that's handled above.
1508  if (auto *FI = dyn_cast<FenceInst>(&Inst))
1509  if (FI->getOrdering() == AtomicOrdering::Release) {
1510  assert(Inst.mayReadFromMemory() && "relied on to prevent DSE above");
1511  continue;
1512  }
1513 
1514  // write back DSE - If we write back the same value we just loaded from
1515  // the same location and haven't passed any intervening writes or ordering
1516  // operations, we can remove the write. The primary benefit is in allowing
1517  // the available load table to remain valid and value forward past where
1518  // the store originally was.
1519  if (MemInst.isValid() && MemInst.isStore()) {
1520  LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1521  if (InVal.DefInst &&
1522  InVal.DefInst == getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1523  // It is okay to have a LastStore to a different pointer here if MemorySSA
1524  // tells us that the load and store are from the same memory generation.
1525  // In that case, LastStore should keep its present value since we're
1526  // removing the current store.
1527  assert((!LastStore ||
1528  ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
1529  MemInst.getPointerOperand() ||
1530  MSSA) &&
1531  "can't have an intervening store if not using MemorySSA!");
1532  LLVM_DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << Inst << '\n');
1533  if (!DebugCounter::shouldExecute(CSECounter)) {
1534  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1535  continue;
1536  }
1537  salvageKnowledge(&Inst, &AC);
1538  removeMSSA(Inst);
1539  Inst.eraseFromParent();
1540  Changed = true;
1541  ++NumDSE;
1542  // We can avoid incrementing the generation count since we were able
1543  // to eliminate this store.
1544  continue;
1545  }
1546  }
1547 
1548  // Okay, this isn't something we can CSE at all. Check to see if it is
1549  // something that could modify memory. If so, our available memory values
1550  // cannot be used so bump the generation count.
1551  if (Inst.mayWriteToMemory()) {
1552  ++CurrentGeneration;
1553 
1554  if (MemInst.isValid() && MemInst.isStore()) {
1555  // We do a trivial form of DSE if there are two stores to the same
1556  // location with no intervening loads. Delete the earlier store.
1557  if (LastStore) {
1558  if (overridingStores(ParseMemoryInst(LastStore, TTI), MemInst)) {
1559  LLVM_DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
1560  << " due to: " << Inst << '\n');
1561  if (!DebugCounter::shouldExecute(CSECounter)) {
1562  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1563  } else {
1564  salvageKnowledge(&Inst, &AC);
1565  removeMSSA(*LastStore);
1566  LastStore->eraseFromParent();
1567  Changed = true;
1568  ++NumDSE;
1569  LastStore = nullptr;
1570  }
1571  }
1572  // fallthrough - we can exploit information about this store
1573  }
1574 
1575  // Okay, we just invalidated anything we knew about loaded values. Try
1576  // to salvage *something* by remembering that the stored value is a live
1577  // version of the pointer. It is safe to forward from volatile stores
1578  // to non-volatile loads, so we don't have to check for volatility of
1579  // the store.
1580  AvailableLoads.insert(MemInst.getPointerOperand(),
1581  LoadValue(&Inst, CurrentGeneration,
1582  MemInst.getMatchingId(),
1583  MemInst.isAtomic()));
1584 
1585  // Remember that this was the last unordered store we saw for DSE. We
1586  // don't yet handle DSE on ordered or volatile stores since we don't
1587  // have a good way to model the ordering requirement for following
1588  // passes once the store is removed. We could insert a fence, but
1589  // since fences are slightly stronger than stores in their ordering,
1590  // it's not clear this is a profitable transform. Another option would
1591  // be to merge the ordering with that of the post dominating store.
1592  if (MemInst.isUnordered() && !MemInst.isVolatile())
1593  LastStore = &Inst;
1594  else
1595  LastStore = nullptr;
1596  }
1597  }
1598  }
1599 
1600  return Changed;
1601 }
1602 
1603 bool EarlyCSE::run() {
1604  // Note, deque is being used here because there is significant performance
1605  // gains over vector when the container becomes very large due to the
1606  // specific access patterns. For more information see the mailing list
1607  // discussion on this:
1608  // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
1609  std::deque<StackNode *> nodesToProcess;
1610 
1611  bool Changed = false;
1612 
1613  // Process the root node.
1614  nodesToProcess.push_back(new StackNode(
1615  AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1616  CurrentGeneration, DT.getRootNode(),
1617  DT.getRootNode()->begin(), DT.getRootNode()->end()));
1618 
1619  assert(!CurrentGeneration && "Create a new EarlyCSE instance to rerun it.");
1620 
1621  // Process the stack.
1622  while (!nodesToProcess.empty()) {
1623  // Grab the first item off the stack. Set the current generation, remove
1624  // the node from the stack, and process it.
1625  StackNode *NodeToProcess = nodesToProcess.back();
1626 
1627  // Initialize class members.
1628  CurrentGeneration = NodeToProcess->currentGeneration();
1629 
1630  // Check if the node needs to be processed.
1631  if (!NodeToProcess->isProcessed()) {
1632  // Process the node.
1633  Changed |= processNode(NodeToProcess->node());
1634  NodeToProcess->childGeneration(CurrentGeneration);
1635  NodeToProcess->process();
1636  } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
1637  // Push the next child onto the stack.
1638  DomTreeNode *child = NodeToProcess->nextChild();
1639  nodesToProcess.push_back(
1640  new StackNode(AvailableValues, AvailableLoads, AvailableInvariants,
1641  AvailableCalls, NodeToProcess->childGeneration(),
1642  child, child->begin(), child->end()));
1643  } else {
1644  // It has been processed, and there are no more children to process,
1645  // so delete it and pop it off the stack.
1646  delete NodeToProcess;
1647  nodesToProcess.pop_back();
1648  }
1649  } // while (!nodes...)
1650 
1651  return Changed;
1652 }
1653 
1656  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1657  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1658  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1659  auto &AC = AM.getResult<AssumptionAnalysis>(F);
1660  auto *MSSA =
1661  UseMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA() : nullptr;
1662 
1663  EarlyCSE CSE(F.getParent()->getDataLayout(), TLI, TTI, DT, AC, MSSA);
1664 
1665  if (!CSE.run())
1666  return PreservedAnalyses::all();
1667 
1668  PreservedAnalyses PA;
1669  PA.preserveSet<CFGAnalyses>();
1670  if (UseMemorySSA)
1672  return PA;
1673 }
1674 
1676  raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1677  static_cast<PassInfoMixin<EarlyCSEPass> *>(this)->printPipeline(
1678  OS, MapClassName2PassName);
1679  OS << "<";
1680  if (UseMemorySSA)
1681  OS << "memssa";
1682  OS << ">";
1683 }
1684 
1685 namespace {
1686 
1687 /// A simple and fast domtree-based CSE pass.
1688 ///
1689 /// This pass does a simple depth-first walk over the dominator tree,
1690 /// eliminating trivially redundant instructions and using instsimplify to
1691 /// canonicalize things as it goes. It is intended to be fast and catch obvious
1692 /// cases so that instcombine and other passes are more effective. It is
1693 /// expected that a later pass of GVN will catch the interesting/hard cases.
1694 template<bool UseMemorySSA>
1695 class EarlyCSELegacyCommonPass : public FunctionPass {
1696 public:
1697  static char ID;
1698 
1699  EarlyCSELegacyCommonPass() : FunctionPass(ID) {
1700  if (UseMemorySSA)
1702  else
1704  }
1705 
1706  bool runOnFunction(Function &F) override {
1707  if (skipFunction(F))
1708  return false;
1709 
1710  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1711  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1712  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1713  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1714  auto *MSSA =
1715  UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() : nullptr;
1716 
1717  EarlyCSE CSE(F.getParent()->getDataLayout(), TLI, TTI, DT, AC, MSSA);
1718 
1719  return CSE.run();
1720  }
1721 
1722  void getAnalysisUsage(AnalysisUsage &AU) const override {
1727  if (UseMemorySSA) {
1731  }
1734  AU.setPreservesCFG();
1735  }
1736 };
1737 
1738 } // end anonymous namespace
1739 
1740 using EarlyCSELegacyPass = EarlyCSELegacyCommonPass</*UseMemorySSA=*/false>;
1741 
1742 template<>
1743 char EarlyCSELegacyPass::ID = 0;
1744 
1745 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
1746  false)
1752 
1753 using EarlyCSEMemSSALegacyPass =
1754  EarlyCSELegacyCommonPass</*UseMemorySSA=*/true>;
1755 
1756 template<>
1757 char EarlyCSEMemSSALegacyPass::ID = 0;
1758 
1759 FunctionPass *llvm::createEarlyCSEPass(bool UseMemorySSA) {
1760  if (UseMemorySSA)
1761  return new EarlyCSEMemSSALegacyPass();
1762  else
1763  return new EarlyCSELegacyPass();
1764 }
1765 
1766 INITIALIZE_PASS_BEGIN(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1767  "Early CSE w/ MemorySSA", false, false)
1774 INITIALIZE_PASS_END(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1775  "Early CSE w/ MemorySSA", false, false)
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
AssumptionCache.h
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2485
llvm::SPF_SMAX
@ SPF_SMAX
Unsigned minimum.
Definition: ValueTracking.h:702
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:849
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:35
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::EarlyCSEPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: EarlyCSE.cpp:1675
llvm::MemorySSA::verifyMemorySSA
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1906
llvm::ScopedHashTableVal
Definition: ScopedHashTable.h:46
matchSelectWithOptionalNotCond
static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond, Value *&A, Value *&B, SelectPatternFlavor &Flavor)
Match a 'select' including an optional 'not's of the condition.
Definition: EarlyCSE.cpp:158
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
IntrinsicInst.h
llvm::SimplifyQuery
Definition: InstructionSimplify.h:93
getHashValueImpl
static unsigned getHashValueImpl(SimpleValue Val)
Definition: EarlyCSE.cpp:205
AtomicOrdering.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
Scalar.h
llvm::PassInfoMixin< EarlyCSEPass >
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:60
Pass.h
llvm::IntrinsicInst::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:53
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
Allocator.h
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:833
llvm::MemorySSA::dominates
bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
Definition: MemorySSA.cpp:2159
ValueTracking.h
Local.h
DEBUG_COUNTER
DEBUG_COUNTER(CSECounter, "early-cse", "Controls which instructions are removed")
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
GlobalsModRef.h
llvm::createEarlyCSEPass
FunctionPass * createEarlyCSEPass(bool UseMemorySSA=false)
Definition: EarlyCSE.cpp:1759
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::DenseMapInfo< SimpleValue >::getEmptyKey
static SimpleValue getEmptyKey()
Definition: EarlyCSE.cpp:143
llvm::getLoadStoreType
Type * getLoadStoreType(Value *I)
A helper function that returns the type of a load or store instruction.
Definition: Instructions.h:5362
llvm::programUndefinedIfPoison
bool programUndefinedIfPoison(const Instruction *Inst)
Definition: ValueTracking.cpp:5718
cse
static void cse(BasicBlock *BB)
Perform cse of induction variable instructions.
Definition: LoopVectorize.cpp:3410
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:746
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1886
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::BasicBlockEdge
Definition: Dominators.h:98
llvm::User::value_op_begin
value_op_iterator value_op_begin()
Definition: User.h:260
llvm::SPF_UMAX
@ SPF_UMAX
Signed maximum.
Definition: ValueTracking.h:703
llvm::BumpPtrAllocator
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:372
llvm::SmallPtrSet< Instruction *, 4 >
llvm::Instruction::mayThrow
bool mayThrow() const
Return true if this instruction may throw an exception.
Definition: Instruction.cpp:685
Hashing.h
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:749
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::PatternMatch::m_Not
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
Definition: PatternMatch.h:2283
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:698
memssa
early cse memssa
Definition: EarlyCSE.cpp:1774
isSentinel
static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE)
Definition: DWARFAcceleratorTable.cpp:424
llvm::isEqual
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
Definition: GCNRegPressure.cpp:55
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::isGuard
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
Definition: GuardUtils.cpp:18
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:157
llvm::SPF_UNKNOWN
@ SPF_UNKNOWN
Definition: ValueTracking.h:699
CSE
separate const offset from Split GEPs to a variadic base and a constant offset for better CSE
Definition: SeparateConstOffsetFromGEP.cpp:495
llvm::TargetTransformInfo::getOrCreateResultFromMemIntrinsic
Value * getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst, Type *ExpectedType) const
Definition: TargetTransformInfo.cpp:994
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:998
llvm::DominatorTreeBase::getRootNode
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Definition: GenericDomTree.h:370
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PatternMatch::m_Select
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
Definition: PatternMatch.h:1456
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::DenseMapInfo< CallValue >::getEmptyKey
static CallValue getEmptyKey()
Definition: EarlyCSE.cpp:469
llvm::CmpInst::ICMP_ULE
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:745
InstrTypes.h
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::Instruction::isIdenticalToWhenDefined
bool isIdenticalToWhenDefined(const Instruction *I) const
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Definition: Instruction.cpp:507
llvm::DenseMapInfo< CallValue >::getTombstoneKey
static CallValue getTombstoneKey()
Definition: EarlyCSE.cpp:473
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
TargetLibraryInfo.h
AssumeBundleBuilder.h
false
Definition: StackSlotColoring.cpp:141
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:42
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
PatternMatch.h
llvm::Instruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: Instruction.cpp:596
ScopedHashTable.h
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::CallBase::onlyReadsMemory
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1720
llvm::SPF_SMIN
@ SPF_SMIN
Definition: ValueTracking.h:700
Type.h
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::ScopedHashTable
Definition: ScopedHashTable.h:43
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:101
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3167
llvm::EarlyCSEPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: EarlyCSE.cpp:1654
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::MemorySSAWalker::getClobberingMemoryAccess
MemoryAccess * getClobberingMemoryAccess(const Instruction *I)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Definition: MemorySSA.h:1058
BasicBlock.h
llvm::cl::opt
Definition: CommandLine.h:1392
generation
Optimize for code generation
Definition: CodeGenPrepare.cpp:463
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
EarlyCSE.h
llvm::GCRelocateInst
Represents calls to the gc.relocate intrinsic.
Definition: IntrinsicInst.h:1388
llvm::MemoryLocation::getOrNone
static Optional< MemoryLocation > getOrNone(const Instruction *Inst)
Definition: MemoryLocation.cpp:76
llvm::getPointerOperand
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
Definition: Instructions.h:5331
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:468
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2541
llvm::PatternMatch::m_LogicalOr
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
Definition: PatternMatch.h:2549
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::Instruction::isIdenticalTo
bool isIdenticalTo(const Instruction *I) const
Return true if the specified instruction is exactly identical to the current one.
Definition: Instruction.cpp:502
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:731
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:618
node
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 node
Definition: README-SSE.txt:406
llvm::simplifyInstruction
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6482
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MemoryLocation::getForArgument
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
Definition: MemoryLocation.cpp:158
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:743
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:163
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
llvm::salvageKnowledge
void salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Definition: AssumeBundleBuilder.cpp:293
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:948
llvm::replaceDominatedUsesWith
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of 'From' with 'To' if that use is dominated by the given edge.
Definition: Local.cpp:2732
llvm::MemorySSA::getWalker
MemorySSAWalker * getWalker()
Definition: MemorySSA.cpp:1604
isStore
static bool isStore(int Opcode)
Definition: ARCInstrInfo.cpp:58
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:748
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:395
llvm::BinaryOperator
Definition: InstrTypes.h:188
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
isLoad
static bool isLoad(int Opcode)
Definition: ARCInstrInfo.cpp:53
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:744
llvm::initializeEarlyCSEMemSSALegacyPassPass
void initializeEarlyCSEMemSSALegacyPassPass(PassRegistry &)
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:529
EarlyCSEMssaOptCap
static cl::opt< unsigned > EarlyCSEMssaOptCap("earlycse-mssa-optimization-cap", cl::init(500), cl::Hidden, cl::desc("Enable imprecision in EarlyCSE in pathological cases, in exchange " "for faster compile. Caps the MemorySSA clobbering calls."))
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::DomTreeNodeBase::begin
iterator begin()
Definition: GenericDomTree.h:75
isEqualImpl
static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS)
Definition: EarlyCSE.cpp:323
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:429
llvm::Instruction::mayReadFromMemory
bool mayReadFromMemory() const
Return true if this instruction may read memory.
Definition: Instruction.cpp:576
llvm::MemoryAccess
Definition: MemorySSA.h:142
llvm::DomTreeNodeBase< BasicBlock >
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:881
llvm::AtomicOrdering::Release
@ Release
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::Instruction::isAtomic
bool isAtomic() const
Return true if this instruction has an AtomicOrdering of unordered or higher.
Definition: Instruction.cpp:616
llvm::User::value_op_end
value_op_iterator value_op_end()
Definition: User.h:263
llvm::RecyclingAllocator
RecyclingAllocator - This class wraps an Allocator, adding the functionality of recycling deleted obj...
Definition: RecyclingAllocator.h:26
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:874
std
Definition: BitVector.h:851
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::DomTreeNodeBase::end
iterator end()
Definition: GenericDomTree.h:76
llvm::initializeEarlyCSELegacyPassPass
void initializeEarlyCSELegacyPassPass(PassRegistry &)
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2398
Casting.h
Function.h
DebugCounter.h
PassManager.h
llvm::salvageDebugInfo
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1739
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
RecyclingAllocator.h
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1869
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:747
EarlyCSELegacyPass
EarlyCSELegacyCommonPass< false > EarlyCSELegacyPass
Definition: EarlyCSE.cpp:1740
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
GuardUtils.h
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
MemorySSA.h
isValid
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Definition: RustDemangle.cpp:187
llvm::DomTreeNodeBase< BasicBlock >::const_iterator
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
Definition: GenericDomTree.h:73
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
SmallVector.h
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:766
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:605
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1388
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:742
Dominators.h
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5394
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1351
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:483
llvm::SPF_UMIN
@ SPF_UMIN
Signed minimum.
Definition: ValueTracking.h:701
InstructionSimplify.h
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:809
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:148
TargetTransformInfo.h
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
early
the custom lowered code happens to be but we shouldn t have to custom lower anything This is probably related to< 2 x i64 > ops being so bad LLVM currently generates stack realignment when it is not necessary needed The problem is that we need to know about stack alignment too early
Definition: README-SSE.txt:486
llvm::PatternMatch
Definition: PatternMatch.h:47
DenseMapInfo.h
llvm::MemIntrinsicInfo
Information about a load/store intrinsic defined by the target.
Definition: TargetTransformInfo.h:70
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::getLoadStorePointerOperand
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
Definition: Instructions.h:5317
EarlyCSEDebugHash
static cl::opt< bool > EarlyCSEDebugHash("earlycse-debug-hash", cl::init(false), cl::Hidden, cl::desc("Perform extra assertion checking to verify that SimpleValue's hash " "function is well-behaved w.r.t. its isEqual predicate"))
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1461
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
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
LLVMContext.h
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:405
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3086
raw_ostream.h
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::InsertValueInst
This instruction inserts a struct field of array element value into an aggregate value.
Definition: Instructions.h:2509
llvm::TargetTransformInfo::getTgtMemIntrinsic
bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) const
Definition: TargetTransformInfo.cpp:985
Value.h
llvm::PatternMatch::m_Cmp
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:89
InitializePasses.h
llvm::DenseMapInfo< SimpleValue >::getTombstoneKey
static SimpleValue getTombstoneKey()
Definition: EarlyCSE.cpp:147
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:443
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3165
llvm::AtomicOrdering::NotAtomic
@ NotAtomic
llvm::PatternMatch::m_LogicalAnd
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
Definition: PatternMatch.h:2531
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3179
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false) using EarlyCSEMemSSALegacyPass
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1237
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38