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