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