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) ||
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  // TODO: We could insert relevant casts on type mismatch here.
831  if (auto *LI = dyn_cast<LoadInst>(Inst))
832  return LI->getType() == ExpectedType ? LI : nullptr;
833  else if (auto *SI = dyn_cast<StoreInst>(Inst)) {
834  Value *V = SI->getValueOperand();
835  return V->getType() == ExpectedType ? V : nullptr;
836  }
837  assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
838  auto *II = cast<IntrinsicInst>(Inst);
839  if (isHandledNonTargetIntrinsic(II->getIntrinsicID()))
840  return getOrCreateResultNonTargetMemIntrinsic(II, ExpectedType);
841  return TTI.getOrCreateResultFromMemIntrinsic(II, ExpectedType);
842  }
843 
844  Value *getOrCreateResultNonTargetMemIntrinsic(IntrinsicInst *II,
845  Type *ExpectedType) const {
846  switch (II->getIntrinsicID()) {
847  case Intrinsic::masked_load:
848  return II;
849  case Intrinsic::masked_store:
850  return II->getOperand(0);
851  }
852  return nullptr;
853  }
854 
855  /// Return true if the instruction is known to only operate on memory
856  /// provably invariant in the given "generation".
857  bool isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt);
858 
859  bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
860  Instruction *EarlierInst, Instruction *LaterInst);
861 
862  bool isNonTargetIntrinsicMatch(const IntrinsicInst *Earlier,
863  const IntrinsicInst *Later) {
864  auto IsSubmask = [](const Value *Mask0, const Value *Mask1) {
865  // Is Mask0 a submask of Mask1?
866  if (Mask0 == Mask1)
867  return true;
868  if (isa<UndefValue>(Mask0) || isa<UndefValue>(Mask1))
869  return false;
870  auto *Vec0 = dyn_cast<ConstantVector>(Mask0);
871  auto *Vec1 = dyn_cast<ConstantVector>(Mask1);
872  if (!Vec0 || !Vec1)
873  return false;
874  assert(Vec0->getType() == Vec1->getType() &&
875  "Masks should have the same type");
876  for (int i = 0, e = Vec0->getNumOperands(); i != e; ++i) {
877  Constant *Elem0 = Vec0->getOperand(i);
878  Constant *Elem1 = Vec1->getOperand(i);
879  auto *Int0 = dyn_cast<ConstantInt>(Elem0);
880  if (Int0 && Int0->isZero())
881  continue;
882  auto *Int1 = dyn_cast<ConstantInt>(Elem1);
883  if (Int1 && !Int1->isZero())
884  continue;
885  if (isa<UndefValue>(Elem0) || isa<UndefValue>(Elem1))
886  return false;
887  if (Elem0 == Elem1)
888  continue;
889  return false;
890  }
891  return true;
892  };
893  auto PtrOp = [](const IntrinsicInst *II) {
894  if (II->getIntrinsicID() == Intrinsic::masked_load)
895  return II->getOperand(0);
896  if (II->getIntrinsicID() == Intrinsic::masked_store)
897  return II->getOperand(1);
898  llvm_unreachable("Unexpected IntrinsicInst");
899  };
900  auto MaskOp = [](const IntrinsicInst *II) {
901  if (II->getIntrinsicID() == Intrinsic::masked_load)
902  return II->getOperand(2);
903  if (II->getIntrinsicID() == Intrinsic::masked_store)
904  return II->getOperand(3);
905  llvm_unreachable("Unexpected IntrinsicInst");
906  };
907  auto ThruOp = [](const IntrinsicInst *II) {
908  if (II->getIntrinsicID() == Intrinsic::masked_load)
909  return II->getOperand(3);
910  llvm_unreachable("Unexpected IntrinsicInst");
911  };
912 
913  if (PtrOp(Earlier) != PtrOp(Later))
914  return false;
915 
916  Intrinsic::ID IDE = Earlier->getIntrinsicID();
917  Intrinsic::ID IDL = Later->getIntrinsicID();
918  // We could really use specific intrinsic classes for masked loads
919  // and stores in IntrinsicInst.h.
920  if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_load) {
921  // Trying to replace later masked load with the earlier one.
922  // Check that the pointers are the same, and
923  // - masks and pass-throughs are the same, or
924  // - replacee's pass-through is "undef" and replacer's mask is a
925  // super-set of the replacee's mask.
926  if (MaskOp(Earlier) == MaskOp(Later) && ThruOp(Earlier) == ThruOp(Later))
927  return true;
928  if (!isa<UndefValue>(ThruOp(Later)))
929  return false;
930  return IsSubmask(MaskOp(Later), MaskOp(Earlier));
931  }
932  if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_load) {
933  // Trying to replace a load of a stored value with the store's value.
934  // Check that the pointers are the same, and
935  // - load's mask is a subset of store's mask, and
936  // - load's pass-through is "undef".
937  if (!IsSubmask(MaskOp(Later), MaskOp(Earlier)))
938  return false;
939  return isa<UndefValue>(ThruOp(Later));
940  }
941  if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_store) {
942  // Trying to remove a store of the loaded value.
943  // Check that the pointers are the same, and
944  // - store's mask is a subset of the load's mask.
945  return IsSubmask(MaskOp(Later), MaskOp(Earlier));
946  }
947  if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_store) {
948  // Trying to remove a dead store (earlier).
949  // Check that the pointers are the same,
950  // - the to-be-removed store's mask is a subset of the other store's
951  // mask.
952  return IsSubmask(MaskOp(Earlier), MaskOp(Later));
953  }
954  return false;
955  }
956 
957  void removeMSSA(Instruction &Inst) {
958  if (!MSSA)
959  return;
960  if (VerifyMemorySSA)
961  MSSA->verifyMemorySSA();
962  // Removing a store here can leave MemorySSA in an unoptimized state by
963  // creating MemoryPhis that have identical arguments and by creating
964  // MemoryUses whose defining access is not an actual clobber. The phi case
965  // is handled by MemorySSA when passing OptimizePhis = true to
966  // removeMemoryAccess. The non-optimized MemoryUse case is lazily updated
967  // by MemorySSA's getClobberingMemoryAccess.
968  MSSAUpdater->removeMemoryAccess(&Inst, true);
969  }
970 };
971 
972 } // end anonymous namespace
973 
974 /// Determine if the memory referenced by LaterInst is from the same heap
975 /// version as EarlierInst.
976 /// This is currently called in two scenarios:
977 ///
978 /// load p
979 /// ...
980 /// load p
981 ///
982 /// and
983 ///
984 /// x = load p
985 /// ...
986 /// store x, p
987 ///
988 /// in both cases we want to verify that there are no possible writes to the
989 /// memory referenced by p between the earlier and later instruction.
990 bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
991  unsigned LaterGeneration,
992  Instruction *EarlierInst,
993  Instruction *LaterInst) {
994  // Check the simple memory generation tracking first.
995  if (EarlierGeneration == LaterGeneration)
996  return true;
997 
998  if (!MSSA)
999  return false;
1000 
1001  // If MemorySSA has determined that one of EarlierInst or LaterInst does not
1002  // read/write memory, then we can safely return true here.
1003  // FIXME: We could be more aggressive when checking doesNotAccessMemory(),
1004  // onlyReadsMemory(), mayReadFromMemory(), and mayWriteToMemory() in this pass
1005  // by also checking the MemorySSA MemoryAccess on the instruction. Initial
1006  // experiments suggest this isn't worthwhile, at least for C/C++ code compiled
1007  // with the default optimization pipeline.
1008  auto *EarlierMA = MSSA->getMemoryAccess(EarlierInst);
1009  if (!EarlierMA)
1010  return true;
1011  auto *LaterMA = MSSA->getMemoryAccess(LaterInst);
1012  if (!LaterMA)
1013  return true;
1014 
1015  // Since we know LaterDef dominates LaterInst and EarlierInst dominates
1016  // LaterInst, if LaterDef dominates EarlierInst then it can't occur between
1017  // EarlierInst and LaterInst and neither can any other write that potentially
1018  // clobbers LaterInst.
1019  MemoryAccess *LaterDef;
1020  if (ClobberCounter < EarlyCSEMssaOptCap) {
1021  LaterDef = MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
1022  ClobberCounter++;
1023  } else
1024  LaterDef = LaterMA->getDefiningAccess();
1025 
1026  return MSSA->dominates(LaterDef, EarlierMA);
1027 }
1028 
1029 bool EarlyCSE::isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt) {
1030  // A location loaded from with an invariant_load is assumed to *never* change
1031  // within the visible scope of the compilation.
1032  if (auto *LI = dyn_cast<LoadInst>(I))
1033  if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1034  return true;
1035 
1036  auto MemLocOpt = MemoryLocation::getOrNone(I);
1037  if (!MemLocOpt)
1038  // "target" intrinsic forms of loads aren't currently known to
1039  // MemoryLocation::get. TODO
1040  return false;
1041  MemoryLocation MemLoc = *MemLocOpt;
1042  if (!AvailableInvariants.count(MemLoc))
1043  return false;
1044 
1045  // Is the generation at which this became invariant older than the
1046  // current one?
1047  return AvailableInvariants.lookup(MemLoc) <= GenAt;
1048 }
1049 
1050 bool EarlyCSE::handleBranchCondition(Instruction *CondInst,
1051  const BranchInst *BI, const BasicBlock *BB,
1052  const BasicBlock *Pred) {
1053  assert(BI->isConditional() && "Should be a conditional branch!");
1054  assert(BI->getCondition() == CondInst && "Wrong condition?");
1055  assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
1056  auto *TorF = (BI->getSuccessor(0) == BB)
1057  ? ConstantInt::getTrue(BB->getContext())
1058  : ConstantInt::getFalse(BB->getContext());
1059  auto MatchBinOp = [](Instruction *I, unsigned Opcode, Value *&LHS,
1060  Value *&RHS) {
1061  if (Opcode == Instruction::And &&
1063  return true;
1064  else if (Opcode == Instruction::Or &&
1066  return true;
1067  return false;
1068  };
1069  // If the condition is AND operation, we can propagate its operands into the
1070  // true branch. If it is OR operation, we can propagate them into the false
1071  // branch.
1072  unsigned PropagateOpcode =
1073  (BI->getSuccessor(0) == BB) ? Instruction::And : Instruction::Or;
1074 
1075  bool MadeChanges = false;
1078  WorkList.push_back(CondInst);
1079  while (!WorkList.empty()) {
1080  Instruction *Curr = WorkList.pop_back_val();
1081 
1082  AvailableValues.insert(Curr, TorF);
1083  LLVM_DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
1084  << Curr->getName() << "' as " << *TorF << " in "
1085  << BB->getName() << "\n");
1086  if (!DebugCounter::shouldExecute(CSECounter)) {
1087  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1088  } else {
1089  // Replace all dominated uses with the known value.
1090  if (unsigned Count = replaceDominatedUsesWith(Curr, TorF, DT,
1091  BasicBlockEdge(Pred, BB))) {
1092  NumCSECVP += Count;
1093  MadeChanges = true;
1094  }
1095  }
1096 
1097  Value *LHS, *RHS;
1098  if (MatchBinOp(Curr, PropagateOpcode, LHS, RHS))
1099  for (auto &Op : { LHS, RHS })
1100  if (Instruction *OPI = dyn_cast<Instruction>(Op))
1101  if (SimpleValue::canHandle(OPI) && Visited.insert(OPI).second)
1102  WorkList.push_back(OPI);
1103  }
1104 
1105  return MadeChanges;
1106 }
1107 
1108 Value *EarlyCSE::getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
1109  unsigned CurrentGeneration) {
1110  if (InVal.DefInst == nullptr)
1111  return nullptr;
1112  if (InVal.MatchingId != MemInst.getMatchingId())
1113  return nullptr;
1114  // We don't yet handle removing loads with ordering of any kind.
1115  if (MemInst.isVolatile() || !MemInst.isUnordered())
1116  return nullptr;
1117  // We can't replace an atomic load with one which isn't also atomic.
1118  if (MemInst.isLoad() && !InVal.IsAtomic && MemInst.isAtomic())
1119  return nullptr;
1120  // The value V returned from this function is used differently depending
1121  // on whether MemInst is a load or a store. If it's a load, we will replace
1122  // MemInst with V, if it's a store, we will check if V is the same as the
1123  // available value.
1124  bool MemInstMatching = !MemInst.isLoad();
1125  Instruction *Matching = MemInstMatching ? MemInst.get() : InVal.DefInst;
1126  Instruction *Other = MemInstMatching ? InVal.DefInst : MemInst.get();
1127 
1128  // For stores check the result values before checking memory generation
1129  // (otherwise isSameMemGeneration may crash).
1130  Value *Result = MemInst.isStore()
1131  ? getOrCreateResult(Matching, Other->getType())
1132  : nullptr;
1133  if (MemInst.isStore() && InVal.DefInst != Result)
1134  return nullptr;
1135 
1136  // Deal with non-target memory intrinsics.
1137  bool MatchingNTI = isHandledNonTargetIntrinsic(Matching);
1138  bool OtherNTI = isHandledNonTargetIntrinsic(Other);
1139  if (OtherNTI != MatchingNTI)
1140  return nullptr;
1141  if (OtherNTI && MatchingNTI) {
1142  if (!isNonTargetIntrinsicMatch(cast<IntrinsicInst>(InVal.DefInst),
1143  cast<IntrinsicInst>(MemInst.get())))
1144  return nullptr;
1145  }
1146 
1147  if (!isOperatingOnInvariantMemAt(MemInst.get(), InVal.Generation) &&
1148  !isSameMemGeneration(InVal.Generation, CurrentGeneration, InVal.DefInst,
1149  MemInst.get()))
1150  return nullptr;
1151 
1152  if (!Result)
1153  Result = getOrCreateResult(Matching, Other->getType());
1154  return Result;
1155 }
1156 
1157 bool EarlyCSE::overridingStores(const ParseMemoryInst &Earlier,
1158  const ParseMemoryInst &Later) {
1159  // Can we remove Earlier store because of Later store?
1160 
1161  assert(Earlier.isUnordered() && !Earlier.isVolatile() &&
1162  "Violated invariant");
1163  if (Earlier.getPointerOperand() != Later.getPointerOperand())
1164  return false;
1165  if (Earlier.getMatchingId() != Later.getMatchingId())
1166  return false;
1167  // At the moment, we don't remove ordered stores, but do remove
1168  // unordered atomic stores. There's no special requirement (for
1169  // unordered atomics) about removing atomic stores only in favor of
1170  // other atomic stores since we were going to execute the non-atomic
1171  // one anyway and the atomic one might never have become visible.
1172  if (!Earlier.isUnordered() || !Later.isUnordered())
1173  return false;
1174 
1175  // Deal with non-target memory intrinsics.
1176  bool ENTI = isHandledNonTargetIntrinsic(Earlier.get());
1177  bool LNTI = isHandledNonTargetIntrinsic(Later.get());
1178  if (ENTI && LNTI)
1179  return isNonTargetIntrinsicMatch(cast<IntrinsicInst>(Earlier.get()),
1180  cast<IntrinsicInst>(Later.get()));
1181 
1182  // Because of the check above, at least one of them is false.
1183  // For now disallow matching intrinsics with non-intrinsics,
1184  // so assume that the stores match if neither is an intrinsic.
1185  return ENTI == LNTI;
1186 }
1187 
1188 bool EarlyCSE::processNode(DomTreeNode *Node) {
1189  bool Changed = false;
1190  BasicBlock *BB = Node->getBlock();
1191 
1192  // If this block has a single predecessor, then the predecessor is the parent
1193  // of the domtree node and all of the live out memory values are still current
1194  // in this block. If this block has multiple predecessors, then they could
1195  // have invalidated the live-out memory values of our parent value. For now,
1196  // just be conservative and invalidate memory if this block has multiple
1197  // predecessors.
1198  if (!BB->getSinglePredecessor())
1199  ++CurrentGeneration;
1200 
1201  // If this node has a single predecessor which ends in a conditional branch,
1202  // we can infer the value of the branch condition given that we took this
1203  // path. We need the single predecessor to ensure there's not another path
1204  // which reaches this block where the condition might hold a different
1205  // value. Since we're adding this to the scoped hash table (like any other
1206  // def), it will have been popped if we encounter a future merge block.
1207  if (BasicBlock *Pred = BB->getSinglePredecessor()) {
1208  auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());
1209  if (BI && BI->isConditional()) {
1210  auto *CondInst = dyn_cast<Instruction>(BI->getCondition());
1211  if (CondInst && SimpleValue::canHandle(CondInst))
1212  Changed |= handleBranchCondition(CondInst, BI, BB, Pred);
1213  }
1214  }
1215 
1216  /// LastStore - Keep track of the last non-volatile store that we saw... for
1217  /// as long as there in no instruction that reads memory. If we see a store
1218  /// to the same location, we delete the dead store. This zaps trivial dead
1219  /// stores which can occur in bitfield code among other things.
1220  Instruction *LastStore = nullptr;
1221 
1222  // See if any instructions in the block can be eliminated. If so, do it. If
1223  // not, add them to AvailableValues.
1224  for (Instruction &Inst : make_early_inc_range(BB->getInstList())) {
1225  // Dead instructions should just be removed.
1226  if (isInstructionTriviallyDead(&Inst, &TLI)) {
1227  LLVM_DEBUG(dbgs() << "EarlyCSE DCE: " << Inst << '\n');
1228  if (!DebugCounter::shouldExecute(CSECounter)) {
1229  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1230  continue;
1231  }
1232 
1233  salvageKnowledge(&Inst, &AC);
1234  salvageDebugInfo(Inst);
1235  removeMSSA(Inst);
1236  Inst.eraseFromParent();
1237  Changed = true;
1238  ++NumSimplify;
1239  continue;
1240  }
1241 
1242  // Skip assume intrinsics, they don't really have side effects (although
1243  // they're marked as such to ensure preservation of control dependencies),
1244  // and this pass will not bother with its removal. However, we should mark
1245  // its condition as true for all dominated blocks.
1246  if (auto *Assume = dyn_cast<AssumeInst>(&Inst)) {
1247  auto *CondI = dyn_cast<Instruction>(Assume->getArgOperand(0));
1248  if (CondI && SimpleValue::canHandle(CondI)) {
1249  LLVM_DEBUG(dbgs() << "EarlyCSE considering assumption: " << Inst
1250  << '\n');
1251  AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
1252  } else
1253  LLVM_DEBUG(dbgs() << "EarlyCSE skipping assumption: " << Inst << '\n');
1254  continue;
1255  }
1256 
1257  // Likewise, noalias intrinsics don't actually write.
1258  if (match(&Inst,
1259  m_Intrinsic<Intrinsic::experimental_noalias_scope_decl>())) {
1260  LLVM_DEBUG(dbgs() << "EarlyCSE skipping noalias intrinsic: " << Inst
1261  << '\n');
1262  continue;
1263  }
1264 
1265  // Skip sideeffect intrinsics, for the same reason as assume intrinsics.
1266  if (match(&Inst, m_Intrinsic<Intrinsic::sideeffect>())) {
1267  LLVM_DEBUG(dbgs() << "EarlyCSE skipping sideeffect: " << Inst << '\n');
1268  continue;
1269  }
1270 
1271  // Skip pseudoprobe intrinsics, for the same reason as assume intrinsics.
1272  if (match(&Inst, m_Intrinsic<Intrinsic::pseudoprobe>())) {
1273  LLVM_DEBUG(dbgs() << "EarlyCSE skipping pseudoprobe: " << Inst << '\n');
1274  continue;
1275  }
1276 
1277  // We can skip all invariant.start intrinsics since they only read memory,
1278  // and we can forward values across it. For invariant starts without
1279  // invariant ends, we can use the fact that the invariantness never ends to
1280  // start a scope in the current generaton which is true for all future
1281  // generations. Also, we dont need to consume the last store since the
1282  // semantics of invariant.start allow us to perform DSE of the last
1283  // store, if there was a store following invariant.start. Consider:
1284  //
1285  // store 30, i8* p
1286  // invariant.start(p)
1287  // store 40, i8* p
1288  // We can DSE the store to 30, since the store 40 to invariant location p
1289  // causes undefined behaviour.
1290  if (match(&Inst, m_Intrinsic<Intrinsic::invariant_start>())) {
1291  // If there are any uses, the scope might end.
1292  if (!Inst.use_empty())
1293  continue;
1294  MemoryLocation MemLoc =
1295  MemoryLocation::getForArgument(&cast<CallInst>(Inst), 1, TLI);
1296  // Don't start a scope if we already have a better one pushed
1297  if (!AvailableInvariants.count(MemLoc))
1298  AvailableInvariants.insert(MemLoc, CurrentGeneration);
1299  continue;
1300  }
1301 
1302  if (isGuard(&Inst)) {
1303  if (auto *CondI =
1304  dyn_cast<Instruction>(cast<CallInst>(Inst).getArgOperand(0))) {
1305  if (SimpleValue::canHandle(CondI)) {
1306  // Do we already know the actual value of this condition?
1307  if (auto *KnownCond = AvailableValues.lookup(CondI)) {
1308  // Is the condition known to be true?
1309  if (isa<ConstantInt>(KnownCond) &&
1310  cast<ConstantInt>(KnownCond)->isOne()) {
1311  LLVM_DEBUG(dbgs()
1312  << "EarlyCSE removing guard: " << Inst << '\n');
1313  salvageKnowledge(&Inst, &AC);
1314  removeMSSA(Inst);
1315  Inst.eraseFromParent();
1316  Changed = true;
1317  continue;
1318  } else
1319  // Use the known value if it wasn't true.
1320  cast<CallInst>(Inst).setArgOperand(0, KnownCond);
1321  }
1322  // The condition we're on guarding here is true for all dominated
1323  // locations.
1324  AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
1325  }
1326  }
1327 
1328  // Guard intrinsics read all memory, but don't write any memory.
1329  // Accordingly, don't update the generation but consume the last store (to
1330  // avoid an incorrect DSE).
1331  LastStore = nullptr;
1332  continue;
1333  }
1334 
1335  // If the instruction can be simplified (e.g. X+0 = X) then replace it with
1336  // its simpler value.
1337  if (Value *V = SimplifyInstruction(&Inst, SQ)) {
1338  LLVM_DEBUG(dbgs() << "EarlyCSE Simplify: " << Inst << " to: " << *V
1339  << '\n');
1340  if (!DebugCounter::shouldExecute(CSECounter)) {
1341  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1342  } else {
1343  bool Killed = false;
1344  if (!Inst.use_empty()) {
1345  Inst.replaceAllUsesWith(V);
1346  Changed = true;
1347  }
1348  if (isInstructionTriviallyDead(&Inst, &TLI)) {
1349  salvageKnowledge(&Inst, &AC);
1350  removeMSSA(Inst);
1351  Inst.eraseFromParent();
1352  Changed = true;
1353  Killed = true;
1354  }
1355  if (Changed)
1356  ++NumSimplify;
1357  if (Killed)
1358  continue;
1359  }
1360  }
1361 
1362  // If this is a simple instruction that we can value number, process it.
1363  if (SimpleValue::canHandle(&Inst)) {
1364  // See if the instruction has an available value. If so, use it.
1365  if (Value *V = AvailableValues.lookup(&Inst)) {
1366  LLVM_DEBUG(dbgs() << "EarlyCSE CSE: " << Inst << " to: " << *V
1367  << '\n');
1368  if (!DebugCounter::shouldExecute(CSECounter)) {
1369  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1370  continue;
1371  }
1372  if (auto *I = dyn_cast<Instruction>(V)) {
1373  // If I being poison triggers UB, there is no need to drop those
1374  // flags. Otherwise, only retain flags present on both I and Inst.
1375  // TODO: Currently some fast-math flags are not treated as
1376  // poison-generating even though they should. Until this is fixed,
1377  // always retain flags present on both I and Inst for floating point
1378  // instructions.
1379  if (isa<FPMathOperator>(I) || (I->hasPoisonGeneratingFlags() && !programUndefinedIfPoison(I)))
1380  I->andIRFlags(&Inst);
1381  }
1382  Inst.replaceAllUsesWith(V);
1383  salvageKnowledge(&Inst, &AC);
1384  removeMSSA(Inst);
1385  Inst.eraseFromParent();
1386  Changed = true;
1387  ++NumCSE;
1388  continue;
1389  }
1390 
1391  // Otherwise, just remember that this value is available.
1392  AvailableValues.insert(&Inst, &Inst);
1393  continue;
1394  }
1395 
1396  ParseMemoryInst MemInst(&Inst, TTI);
1397  // If this is a non-volatile load, process it.
1398  if (MemInst.isValid() && MemInst.isLoad()) {
1399  // (conservatively) we can't peak past the ordering implied by this
1400  // operation, but we can add this load to our set of available values
1401  if (MemInst.isVolatile() || !MemInst.isUnordered()) {
1402  LastStore = nullptr;
1403  ++CurrentGeneration;
1404  }
1405 
1406  if (MemInst.isInvariantLoad()) {
1407  // If we pass an invariant load, we know that memory location is
1408  // indefinitely constant from the moment of first dereferenceability.
1409  // We conservatively treat the invariant_load as that moment. If we
1410  // pass a invariant load after already establishing a scope, don't
1411  // restart it since we want to preserve the earliest point seen.
1412  auto MemLoc = MemoryLocation::get(&Inst);
1413  if (!AvailableInvariants.count(MemLoc))
1414  AvailableInvariants.insert(MemLoc, CurrentGeneration);
1415  }
1416 
1417  // If we have an available version of this load, and if it is the right
1418  // generation or the load is known to be from an invariant location,
1419  // replace this instruction.
1420  //
1421  // If either the dominating load or the current load are invariant, then
1422  // we can assume the current load loads the same value as the dominating
1423  // load.
1424  LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1425  if (Value *Op = getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1426  LLVM_DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << Inst
1427  << " to: " << *InVal.DefInst << '\n');
1428  if (!DebugCounter::shouldExecute(CSECounter)) {
1429  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1430  continue;
1431  }
1432  if (!Inst.use_empty())
1433  Inst.replaceAllUsesWith(Op);
1434  salvageKnowledge(&Inst, &AC);
1435  removeMSSA(Inst);
1436  Inst.eraseFromParent();
1437  Changed = true;
1438  ++NumCSELoad;
1439  continue;
1440  }
1441 
1442  // Otherwise, remember that we have this instruction.
1443  AvailableLoads.insert(MemInst.getPointerOperand(),
1444  LoadValue(&Inst, CurrentGeneration,
1445  MemInst.getMatchingId(),
1446  MemInst.isAtomic()));
1447  LastStore = nullptr;
1448  continue;
1449  }
1450 
1451  // If this instruction may read from memory or throw (and potentially read
1452  // from memory in the exception handler), forget LastStore. Load/store
1453  // intrinsics will indicate both a read and a write to memory. The target
1454  // may override this (e.g. so that a store intrinsic does not read from
1455  // memory, and thus will be treated the same as a regular store for
1456  // commoning purposes).
1457  if ((Inst.mayReadFromMemory() || Inst.mayThrow()) &&
1458  !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
1459  LastStore = nullptr;
1460 
1461  // If this is a read-only call, process it.
1462  if (CallValue::canHandle(&Inst)) {
1463  // If we have an available version of this call, and if it is the right
1464  // generation, replace this instruction.
1465  std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(&Inst);
1466  if (InVal.first != nullptr &&
1467  isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
1468  &Inst)) {
1469  LLVM_DEBUG(dbgs() << "EarlyCSE CSE CALL: " << Inst
1470  << " to: " << *InVal.first << '\n');
1471  if (!DebugCounter::shouldExecute(CSECounter)) {
1472  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1473  continue;
1474  }
1475  if (!Inst.use_empty())
1476  Inst.replaceAllUsesWith(InVal.first);
1477  salvageKnowledge(&Inst, &AC);
1478  removeMSSA(Inst);
1479  Inst.eraseFromParent();
1480  Changed = true;
1481  ++NumCSECall;
1482  continue;
1483  }
1484 
1485  // Otherwise, remember that we have this instruction.
1486  AvailableCalls.insert(&Inst, std::make_pair(&Inst, CurrentGeneration));
1487  continue;
1488  }
1489 
1490  // A release fence requires that all stores complete before it, but does
1491  // not prevent the reordering of following loads 'before' the fence. As a
1492  // result, we don't need to consider it as writing to memory and don't need
1493  // to advance the generation. We do need to prevent DSE across the fence,
1494  // but that's handled above.
1495  if (auto *FI = dyn_cast<FenceInst>(&Inst))
1496  if (FI->getOrdering() == AtomicOrdering::Release) {
1497  assert(Inst.mayReadFromMemory() && "relied on to prevent DSE above");
1498  continue;
1499  }
1500 
1501  // write back DSE - If we write back the same value we just loaded from
1502  // the same location and haven't passed any intervening writes or ordering
1503  // operations, we can remove the write. The primary benefit is in allowing
1504  // the available load table to remain valid and value forward past where
1505  // the store originally was.
1506  if (MemInst.isValid() && MemInst.isStore()) {
1507  LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1508  if (InVal.DefInst &&
1509  InVal.DefInst == getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1510  // It is okay to have a LastStore to a different pointer here if MemorySSA
1511  // tells us that the load and store are from the same memory generation.
1512  // In that case, LastStore should keep its present value since we're
1513  // removing the current store.
1514  assert((!LastStore ||
1515  ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
1516  MemInst.getPointerOperand() ||
1517  MSSA) &&
1518  "can't have an intervening store if not using MemorySSA!");
1519  LLVM_DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << Inst << '\n');
1520  if (!DebugCounter::shouldExecute(CSECounter)) {
1521  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1522  continue;
1523  }
1524  salvageKnowledge(&Inst, &AC);
1525  removeMSSA(Inst);
1526  Inst.eraseFromParent();
1527  Changed = true;
1528  ++NumDSE;
1529  // We can avoid incrementing the generation count since we were able
1530  // to eliminate this store.
1531  continue;
1532  }
1533  }
1534 
1535  // Okay, this isn't something we can CSE at all. Check to see if it is
1536  // something that could modify memory. If so, our available memory values
1537  // cannot be used so bump the generation count.
1538  if (Inst.mayWriteToMemory()) {
1539  ++CurrentGeneration;
1540 
1541  if (MemInst.isValid() && MemInst.isStore()) {
1542  // We do a trivial form of DSE if there are two stores to the same
1543  // location with no intervening loads. Delete the earlier store.
1544  if (LastStore) {
1545  if (overridingStores(ParseMemoryInst(LastStore, TTI), MemInst)) {
1546  LLVM_DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
1547  << " due to: " << Inst << '\n');
1548  if (!DebugCounter::shouldExecute(CSECounter)) {
1549  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1550  } else {
1551  salvageKnowledge(&Inst, &AC);
1552  removeMSSA(*LastStore);
1553  LastStore->eraseFromParent();
1554  Changed = true;
1555  ++NumDSE;
1556  LastStore = nullptr;
1557  }
1558  }
1559  // fallthrough - we can exploit information about this store
1560  }
1561 
1562  // Okay, we just invalidated anything we knew about loaded values. Try
1563  // to salvage *something* by remembering that the stored value is a live
1564  // version of the pointer. It is safe to forward from volatile stores
1565  // to non-volatile loads, so we don't have to check for volatility of
1566  // the store.
1567  AvailableLoads.insert(MemInst.getPointerOperand(),
1568  LoadValue(&Inst, CurrentGeneration,
1569  MemInst.getMatchingId(),
1570  MemInst.isAtomic()));
1571 
1572  // Remember that this was the last unordered store we saw for DSE. We
1573  // don't yet handle DSE on ordered or volatile stores since we don't
1574  // have a good way to model the ordering requirement for following
1575  // passes once the store is removed. We could insert a fence, but
1576  // since fences are slightly stronger than stores in their ordering,
1577  // it's not clear this is a profitable transform. Another option would
1578  // be to merge the ordering with that of the post dominating store.
1579  if (MemInst.isUnordered() && !MemInst.isVolatile())
1580  LastStore = &Inst;
1581  else
1582  LastStore = nullptr;
1583  }
1584  }
1585  }
1586 
1587  return Changed;
1588 }
1589 
1590 bool EarlyCSE::run() {
1591  // Note, deque is being used here because there is significant performance
1592  // gains over vector when the container becomes very large due to the
1593  // specific access patterns. For more information see the mailing list
1594  // discussion on this:
1595  // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
1596  std::deque<StackNode *> nodesToProcess;
1597 
1598  bool Changed = false;
1599 
1600  // Process the root node.
1601  nodesToProcess.push_back(new StackNode(
1602  AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1603  CurrentGeneration, DT.getRootNode(),
1604  DT.getRootNode()->begin(), DT.getRootNode()->end()));
1605 
1606  assert(!CurrentGeneration && "Create a new EarlyCSE instance to rerun it.");
1607 
1608  // Process the stack.
1609  while (!nodesToProcess.empty()) {
1610  // Grab the first item off the stack. Set the current generation, remove
1611  // the node from the stack, and process it.
1612  StackNode *NodeToProcess = nodesToProcess.back();
1613 
1614  // Initialize class members.
1615  CurrentGeneration = NodeToProcess->currentGeneration();
1616 
1617  // Check if the node needs to be processed.
1618  if (!NodeToProcess->isProcessed()) {
1619  // Process the node.
1620  Changed |= processNode(NodeToProcess->node());
1621  NodeToProcess->childGeneration(CurrentGeneration);
1622  NodeToProcess->process();
1623  } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
1624  // Push the next child onto the stack.
1625  DomTreeNode *child = NodeToProcess->nextChild();
1626  nodesToProcess.push_back(
1627  new StackNode(AvailableValues, AvailableLoads, AvailableInvariants,
1628  AvailableCalls, NodeToProcess->childGeneration(),
1629  child, child->begin(), child->end()));
1630  } else {
1631  // It has been processed, and there are no more children to process,
1632  // so delete it and pop it off the stack.
1633  delete NodeToProcess;
1634  nodesToProcess.pop_back();
1635  }
1636  } // while (!nodes...)
1637 
1638  return Changed;
1639 }
1640 
1643  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1644  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1645  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1646  auto &AC = AM.getResult<AssumptionAnalysis>(F);
1647  auto *MSSA =
1648  UseMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA() : nullptr;
1649 
1650  EarlyCSE CSE(F.getParent()->getDataLayout(), TLI, TTI, DT, AC, MSSA);
1651 
1652  if (!CSE.run())
1653  return PreservedAnalyses::all();
1654 
1655  PreservedAnalyses PA;
1656  PA.preserveSet<CFGAnalyses>();
1657  if (UseMemorySSA)
1659  return PA;
1660 }
1661 
1663  raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1664  static_cast<PassInfoMixin<EarlyCSEPass> *>(this)->printPipeline(
1665  OS, MapClassName2PassName);
1666  OS << "<";
1667  if (UseMemorySSA)
1668  OS << "memssa";
1669  OS << ">";
1670 }
1671 
1672 namespace {
1673 
1674 /// A simple and fast domtree-based CSE pass.
1675 ///
1676 /// This pass does a simple depth-first walk over the dominator tree,
1677 /// eliminating trivially redundant instructions and using instsimplify to
1678 /// canonicalize things as it goes. It is intended to be fast and catch obvious
1679 /// cases so that instcombine and other passes are more effective. It is
1680 /// expected that a later pass of GVN will catch the interesting/hard cases.
1681 template<bool UseMemorySSA>
1682 class EarlyCSELegacyCommonPass : public FunctionPass {
1683 public:
1684  static char ID;
1685 
1686  EarlyCSELegacyCommonPass() : FunctionPass(ID) {
1687  if (UseMemorySSA)
1689  else
1691  }
1692 
1693  bool runOnFunction(Function &F) override {
1694  if (skipFunction(F))
1695  return false;
1696 
1697  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1698  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1699  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1700  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1701  auto *MSSA =
1702  UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() : nullptr;
1703 
1704  EarlyCSE CSE(F.getParent()->getDataLayout(), TLI, TTI, DT, AC, MSSA);
1705 
1706  return CSE.run();
1707  }
1708 
1709  void getAnalysisUsage(AnalysisUsage &AU) const override {
1714  if (UseMemorySSA) {
1718  }
1721  AU.setPreservesCFG();
1722  }
1723 };
1724 
1725 } // end anonymous namespace
1726 
1727 using EarlyCSELegacyPass = EarlyCSELegacyCommonPass</*UseMemorySSA=*/false>;
1728 
1729 template<>
1730 char EarlyCSELegacyPass::ID = 0;
1731 
1732 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
1733  false)
1739 
1740 using EarlyCSEMemSSALegacyPass =
1741  EarlyCSELegacyCommonPass</*UseMemorySSA=*/true>;
1742 
1743 template<>
1744 char EarlyCSEMemSSALegacyPass::ID = 0;
1745 
1746 FunctionPass *llvm::createEarlyCSEPass(bool UseMemorySSA) {
1747  if (UseMemorySSA)
1748  return new EarlyCSEMemSSALegacyPass();
1749  else
1750  return new EarlyCSELegacyPass();
1751 }
1752 
1753 INITIALIZE_PASS_BEGIN(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1754  "Early CSE w/ MemorySSA", false, false)
1761 INITIALIZE_PASS_END(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1762  "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:2420
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:851
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 is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
llvm::EarlyCSEPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: EarlyCSE.cpp:1662
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:721
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:1176
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:835
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:1746
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::DenseMapInfo< SimpleValue >::getEmptyKey
static SimpleValue getEmptyKey()
Definition: EarlyCSE.cpp:148
llvm::programUndefinedIfPoison
bool programUndefinedIfPoison(const Instruction *Inst)
Definition: ValueTracking.cpp:5474
cse
static void cse(BasicBlock *BB)
Perform cse of induction variable instructions.
Definition: LoopVectorize.cpp:3744
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:748
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1886
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
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:367
llvm::SmallPtrSet< Instruction *, 4 >
llvm::Instruction::mayThrow
bool mayThrow() const
Return true if this instruction may throw an exception.
Definition: Instruction.cpp:683
Hashing.h
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:751
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:643
RHS
Value * RHS
Definition: X86PartialReduction.cpp:74
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:2287
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:676
memssa
early cse memssa
Definition: EarlyCSE.cpp:1761
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:55
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
LHS
Value * LHS
Definition: X86PartialReduction.cpp:73
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h: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:969
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:980
llvm::DominatorTreeBase::getRootNode
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Definition: GenericDomTree.h:370
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::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:747
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:505
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:6363
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:54
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
PatternMatch.h
llvm::Instruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: Instruction.cpp:594
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:1713
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:3173
llvm::EarlyCSEPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: EarlyCSE.cpp:1641
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:711
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::MemorySSAWalker::getClobberingMemoryAccess
MemoryAccess * getClobberingMemoryAccess(const Instruction *I)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Definition: MemorySSA.h:1040
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:309
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:1322
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:5333
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:465
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2476
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:2554
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:55
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h: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:500
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:704
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:721
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:585
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:160
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:852
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:745
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:930
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:2714
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:750
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:398
llvm::BinaryOperator
Definition: InstrTypes.h:190
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:42
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:746
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:431
llvm::Instruction::mayReadFromMemory
bool mayReadFromMemory() const
Return true if this instruction may read memory.
Definition: Instruction.cpp:574
llvm::MemoryAccess
Definition: MemorySSA.h:136
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:180
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:614
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:850
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::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:2404
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:1745
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:1803
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:749
EarlyCSELegacyPass
EarlyCSELegacyCommonPass< false > EarlyCSELegacyPass
Definition: EarlyCSE.cpp:1727
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:780
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:744
Dominators.h
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5378
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1343
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:811
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:5319
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:1478
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:3092
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:2515
llvm::TargetTransformInfo::getTgtMemIntrinsic
bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) const
Definition: TargetTransformInfo.cpp:960
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:3171
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:2536
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3185
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:1198
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38