LLVM  7.0.0svn
EarlyCSE.cpp
Go to the documentation of this file.
1 //===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass performs a simple dominator tree walk that eliminates trivially
11 // redundant instructions.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/DenseMapInfo.h"
17 #include "llvm/ADT/Hashing.h"
18 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallVector.h"
22 #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/Pass.h"
48 #include "llvm/Support/Allocator.h"
50 #include "llvm/Support/Casting.h"
51 #include "llvm/Support/Debug.h"
54 #include "llvm/Transforms/Scalar.h"
56 #include <cassert>
57 #include <deque>
58 #include <memory>
59 #include <utility>
60 
61 using namespace llvm;
62 using namespace llvm::PatternMatch;
63 
64 #define DEBUG_TYPE "early-cse"
65 
66 STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
67 STATISTIC(NumCSE, "Number of instructions CSE'd");
68 STATISTIC(NumCSECVP, "Number of compare instructions CVP'd");
69 STATISTIC(NumCSELoad, "Number of load instructions CSE'd");
70 STATISTIC(NumCSECall, "Number of call instructions CSE'd");
71 STATISTIC(NumDSE, "Number of trivial dead stores removed");
72 
73 //===----------------------------------------------------------------------===//
74 // SimpleValue
75 //===----------------------------------------------------------------------===//
76 
77 namespace {
78 
79 /// \brief Struct representing the available values in the scoped hash table.
80 struct SimpleValue {
81  Instruction *Inst;
82 
83  SimpleValue(Instruction *I) : Inst(I) {
84  assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
85  }
86 
87  bool isSentinel() const {
90  }
91 
92  static bool canHandle(Instruction *Inst) {
93  // This can only handle non-void readnone functions.
94  if (CallInst *CI = dyn_cast<CallInst>(Inst))
95  return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
96  return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
97  isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
98  isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
99  isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
100  isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
101  }
102 };
103 
104 } // end anonymous namespace
105 
106 namespace llvm {
107 
108 template <> struct DenseMapInfo<SimpleValue> {
109  static inline SimpleValue getEmptyKey() {
111  }
112 
113  static inline SimpleValue getTombstoneKey() {
115  }
116 
117  static unsigned getHashValue(SimpleValue Val);
118  static bool isEqual(SimpleValue LHS, SimpleValue RHS);
119 };
120 
121 } // end namespace llvm
122 
123 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
124  Instruction *Inst = Val.Inst;
125  // Hash in all of the operands as pointers.
126  if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
127  Value *LHS = BinOp->getOperand(0);
128  Value *RHS = BinOp->getOperand(1);
129  if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
130  std::swap(LHS, RHS);
131 
132  return hash_combine(BinOp->getOpcode(), LHS, RHS);
133  }
134 
135  if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
136  Value *LHS = CI->getOperand(0);
137  Value *RHS = CI->getOperand(1);
138  CmpInst::Predicate Pred = CI->getPredicate();
139  if (Inst->getOperand(0) > Inst->getOperand(1)) {
140  std::swap(LHS, RHS);
141  Pred = CI->getSwappedPredicate();
142  }
143  return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
144  }
145 
146  // Hash min/max/abs (cmp + select) to allow for commuted operands.
147  // Min/max may also have non-canonical compare predicate (eg, the compare for
148  // smin may use 'sgt' rather than 'slt'), and non-canonical operands in the
149  // compare.
150  Value *A, *B;
152  // TODO: We should also detect FP min/max.
153  if (SPF == SPF_SMIN || SPF == SPF_SMAX ||
154  SPF == SPF_UMIN || SPF == SPF_UMAX ||
155  SPF == SPF_ABS || SPF == SPF_NABS) {
156  if (A > B)
157  std::swap(A, B);
158  return hash_combine(Inst->getOpcode(), SPF, A, B);
159  }
160 
161  if (CastInst *CI = dyn_cast<CastInst>(Inst))
162  return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
163 
164  if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
165  return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
166  hash_combine_range(EVI->idx_begin(), EVI->idx_end()));
167 
168  if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
169  return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
170  IVI->getOperand(1),
171  hash_combine_range(IVI->idx_begin(), IVI->idx_end()));
172 
173  assert((isa<CallInst>(Inst) || isa<BinaryOperator>(Inst) ||
174  isa<GetElementPtrInst>(Inst) || isa<SelectInst>(Inst) ||
175  isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
176  isa<ShuffleVectorInst>(Inst)) &&
177  "Invalid/unknown instruction");
178 
179  // Mix in the opcode.
180  return hash_combine(
181  Inst->getOpcode(),
183 }
184 
185 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
186  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
187 
188  if (LHS.isSentinel() || RHS.isSentinel())
189  return LHSI == RHSI;
190 
191  if (LHSI->getOpcode() != RHSI->getOpcode())
192  return false;
193  if (LHSI->isIdenticalToWhenDefined(RHSI))
194  return true;
195 
196  // If we're not strictly identical, we still might be a commutable instruction
197  if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
198  if (!LHSBinOp->isCommutative())
199  return false;
200 
201  assert(isa<BinaryOperator>(RHSI) &&
202  "same opcode, but different instruction type?");
203  BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
204 
205  // Commuted equality
206  return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
207  LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
208  }
209  if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
210  assert(isa<CmpInst>(RHSI) &&
211  "same opcode, but different instruction type?");
212  CmpInst *RHSCmp = cast<CmpInst>(RHSI);
213  // Commuted equality
214  return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
215  LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
216  LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
217  }
218 
219  // Min/max/abs can occur with commuted operands, non-canonical predicates,
220  // and/or non-canonical operands.
221  Value *LHSA, *LHSB;
222  SelectPatternFlavor LSPF = matchSelectPattern(LHSI, LHSA, LHSB).Flavor;
223  // TODO: We should also detect FP min/max.
224  if (LSPF == SPF_SMIN || LSPF == SPF_SMAX ||
225  LSPF == SPF_UMIN || LSPF == SPF_UMAX ||
226  LSPF == SPF_ABS || LSPF == SPF_NABS) {
227  Value *RHSA, *RHSB;
228  SelectPatternFlavor RSPF = matchSelectPattern(RHSI, RHSA, RHSB).Flavor;
229  return (LSPF == RSPF && ((LHSA == RHSA && LHSB == RHSB) ||
230  (LHSA == RHSB && LHSB == RHSA)));
231  }
232 
233  return false;
234 }
235 
236 //===----------------------------------------------------------------------===//
237 // CallValue
238 //===----------------------------------------------------------------------===//
239 
240 namespace {
241 
242 /// \brief Struct representing the available call values in the scoped hash
243 /// table.
244 struct CallValue {
245  Instruction *Inst;
246 
247  CallValue(Instruction *I) : Inst(I) {
248  assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
249  }
250 
251  bool isSentinel() const {
252  return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
254  }
255 
256  static bool canHandle(Instruction *Inst) {
257  // Don't value number anything that returns void.
258  if (Inst->getType()->isVoidTy())
259  return false;
260 
261  CallInst *CI = dyn_cast<CallInst>(Inst);
262  if (!CI || !CI->onlyReadsMemory())
263  return false;
264  return true;
265  }
266 };
267 
268 } // end anonymous namespace
269 
270 namespace llvm {
271 
272 template <> struct DenseMapInfo<CallValue> {
273  static inline CallValue getEmptyKey() {
275  }
276 
277  static inline CallValue getTombstoneKey() {
279  }
280 
281  static unsigned getHashValue(CallValue Val);
282  static bool isEqual(CallValue LHS, CallValue RHS);
283 };
284 
285 } // end namespace llvm
286 
287 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
288  Instruction *Inst = Val.Inst;
289  // Hash all of the operands as pointers and mix in the opcode.
290  return hash_combine(
291  Inst->getOpcode(),
293 }
294 
295 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
296  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
297  if (LHS.isSentinel() || RHS.isSentinel())
298  return LHSI == RHSI;
299  return LHSI->isIdenticalTo(RHSI);
300 }
301 
302 //===----------------------------------------------------------------------===//
303 // EarlyCSE implementation
304 //===----------------------------------------------------------------------===//
305 
306 namespace {
307 
308 /// \brief A simple and fast domtree-based CSE pass.
309 ///
310 /// This pass does a simple depth-first walk over the dominator tree,
311 /// eliminating trivially redundant instructions and using instsimplify to
312 /// canonicalize things as it goes. It is intended to be fast and catch obvious
313 /// cases so that instcombine and other passes are more effective. It is
314 /// expected that a later pass of GVN will catch the interesting/hard cases.
315 class EarlyCSE {
316 public:
317  const TargetLibraryInfo &TLI;
318  const TargetTransformInfo &TTI;
319  DominatorTree &DT;
320  AssumptionCache &AC;
321  const SimplifyQuery SQ;
322  MemorySSA *MSSA;
323  std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
324 
325  using AllocatorTy =
328  using ScopedHTType =
330  AllocatorTy>;
331 
332  /// \brief A scoped hash table of the current values of all of our simple
333  /// scalar expressions.
334  ///
335  /// As we walk down the domtree, we look to see if instructions are in this:
336  /// if so, we replace them with what we find, otherwise we insert them so
337  /// that dominated values can succeed in their lookup.
338  ScopedHTType AvailableValues;
339 
340  /// A scoped hash table of the current values of previously encounted memory
341  /// locations.
342  ///
343  /// This allows us to get efficient access to dominating loads or stores when
344  /// we have a fully redundant load. In addition to the most recent load, we
345  /// keep track of a generation count of the read, which is compared against
346  /// the current generation count. The current generation count is incremented
347  /// after every possibly writing memory operation, which ensures that we only
348  /// CSE loads with other loads that have no intervening store. Ordering
349  /// events (such as fences or atomic instructions) increment the generation
350  /// count as well; essentially, we model these as writes to all possible
351  /// locations. Note that atomic and/or volatile loads and stores can be
352  /// present the table; it is the responsibility of the consumer to inspect
353  /// the atomicity/volatility if needed.
354  struct LoadValue {
355  Instruction *DefInst = nullptr;
356  unsigned Generation = 0;
357  int MatchingId = -1;
358  bool IsAtomic = false;
359  bool IsInvariant = false;
360 
361  LoadValue() = default;
362  LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,
363  bool IsAtomic, bool IsInvariant)
364  : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
365  IsAtomic(IsAtomic), IsInvariant(IsInvariant) {}
366  };
367 
368  using LoadMapAllocator =
371  using LoadHTType =
373  LoadMapAllocator>;
374 
375  LoadHTType AvailableLoads;
376 
377  /// \brief A scoped hash table of the current values of read-only call
378  /// values.
379  ///
380  /// It uses the same generation count as loads.
381  using CallHTType =
383  CallHTType AvailableCalls;
384 
385  /// \brief This is the current generation of the memory value.
386  unsigned CurrentGeneration = 0;
387 
388  /// \brief Set up the EarlyCSE runner for a particular function.
389  EarlyCSE(const DataLayout &DL, const TargetLibraryInfo &TLI,
390  const TargetTransformInfo &TTI, DominatorTree &DT,
391  AssumptionCache &AC, MemorySSA *MSSA)
392  : TLI(TLI), TTI(TTI), DT(DT), AC(AC), SQ(DL, &TLI, &DT, &AC), MSSA(MSSA),
393  MSSAUpdater(llvm::make_unique<MemorySSAUpdater>(MSSA)) {}
394 
395  bool run();
396 
397 private:
398  // Almost a POD, but needs to call the constructors for the scoped hash
399  // tables so that a new scope gets pushed on. These are RAII so that the
400  // scope gets popped when the NodeScope is destroyed.
401  class NodeScope {
402  public:
403  NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
404  CallHTType &AvailableCalls)
405  : Scope(AvailableValues), LoadScope(AvailableLoads),
406  CallScope(AvailableCalls) {}
407  NodeScope(const NodeScope &) = delete;
408  NodeScope &operator=(const NodeScope &) = delete;
409 
410  private:
411  ScopedHTType::ScopeTy Scope;
412  LoadHTType::ScopeTy LoadScope;
413  CallHTType::ScopeTy CallScope;
414  };
415 
416  // Contains all the needed information to create a stack for doing a depth
417  // first traversal of the tree. This includes scopes for values, loads, and
418  // calls as well as the generation. There is a child iterator so that the
419  // children do not need to be store separately.
420  class StackNode {
421  public:
422  StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
423  CallHTType &AvailableCalls, unsigned cg, DomTreeNode *n,
425  : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
426  EndIter(end), Scopes(AvailableValues, AvailableLoads, AvailableCalls)
427  {}
428  StackNode(const StackNode &) = delete;
429  StackNode &operator=(const StackNode &) = delete;
430 
431  // Accessors.
432  unsigned currentGeneration() { return CurrentGeneration; }
433  unsigned childGeneration() { return ChildGeneration; }
434  void childGeneration(unsigned generation) { ChildGeneration = generation; }
435  DomTreeNode *node() { return Node; }
436  DomTreeNode::iterator childIter() { return ChildIter; }
437 
438  DomTreeNode *nextChild() {
439  DomTreeNode *child = *ChildIter;
440  ++ChildIter;
441  return child;
442  }
443 
444  DomTreeNode::iterator end() { return EndIter; }
445  bool isProcessed() { return Processed; }
446  void process() { Processed = true; }
447 
448  private:
449  unsigned CurrentGeneration;
450  unsigned ChildGeneration;
451  DomTreeNode *Node;
452  DomTreeNode::iterator ChildIter;
453  DomTreeNode::iterator EndIter;
454  NodeScope Scopes;
455  bool Processed = false;
456  };
457 
458  /// \brief Wrapper class to handle memory instructions, including loads,
459  /// stores and intrinsic loads and stores defined by the target.
460  class ParseMemoryInst {
461  public:
462  ParseMemoryInst(Instruction *Inst, const TargetTransformInfo &TTI)
463  : Inst(Inst) {
464  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
465  if (TTI.getTgtMemIntrinsic(II, Info))
466  IsTargetMemInst = true;
467  }
468 
469  bool isLoad() const {
470  if (IsTargetMemInst) return Info.ReadMem;
471  return isa<LoadInst>(Inst);
472  }
473 
474  bool isStore() const {
475  if (IsTargetMemInst) return Info.WriteMem;
476  return isa<StoreInst>(Inst);
477  }
478 
479  bool isAtomic() const {
480  if (IsTargetMemInst)
481  return Info.Ordering != AtomicOrdering::NotAtomic;
482  return Inst->isAtomic();
483  }
484 
485  bool isUnordered() const {
486  if (IsTargetMemInst)
487  return Info.isUnordered();
488 
489  if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
490  return LI->isUnordered();
491  } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
492  return SI->isUnordered();
493  }
494  // Conservative answer
495  return !Inst->isAtomic();
496  }
497 
498  bool isVolatile() const {
499  if (IsTargetMemInst)
500  return Info.IsVolatile;
501 
502  if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
503  return LI->isVolatile();
504  } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
505  return SI->isVolatile();
506  }
507  // Conservative answer
508  return true;
509  }
510 
511  bool isInvariantLoad() const {
512  if (auto *LI = dyn_cast<LoadInst>(Inst))
513  return LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr;
514  return false;
515  }
516 
517  bool isMatchingMemLoc(const ParseMemoryInst &Inst) const {
518  return (getPointerOperand() == Inst.getPointerOperand() &&
519  getMatchingId() == Inst.getMatchingId());
520  }
521 
522  bool isValid() const { return getPointerOperand() != nullptr; }
523 
524  // For regular (non-intrinsic) loads/stores, this is set to -1. For
525  // intrinsic loads/stores, the id is retrieved from the corresponding
526  // field in the MemIntrinsicInfo structure. That field contains
527  // non-negative values only.
528  int getMatchingId() const {
529  if (IsTargetMemInst) return Info.MatchingId;
530  return -1;
531  }
532 
533  Value *getPointerOperand() const {
534  if (IsTargetMemInst) return Info.PtrVal;
535  if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
536  return LI->getPointerOperand();
537  } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
538  return SI->getPointerOperand();
539  }
540  return nullptr;
541  }
542 
543  bool mayReadFromMemory() const {
544  if (IsTargetMemInst) return Info.ReadMem;
545  return Inst->mayReadFromMemory();
546  }
547 
548  bool mayWriteToMemory() const {
549  if (IsTargetMemInst) return Info.WriteMem;
550  return Inst->mayWriteToMemory();
551  }
552 
553  private:
554  bool IsTargetMemInst = false;
555  MemIntrinsicInfo Info;
556  Instruction *Inst;
557  };
558 
559  bool processNode(DomTreeNode *Node);
560 
561  Value *getOrCreateResult(Value *Inst, Type *ExpectedType) const {
562  if (auto *LI = dyn_cast<LoadInst>(Inst))
563  return LI;
564  if (auto *SI = dyn_cast<StoreInst>(Inst))
565  return SI->getValueOperand();
566  assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
567  return TTI.getOrCreateResultFromMemIntrinsic(cast<IntrinsicInst>(Inst),
568  ExpectedType);
569  }
570 
571  bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
572  Instruction *EarlierInst, Instruction *LaterInst);
573 
574  void removeMSSA(Instruction *Inst) {
575  if (!MSSA)
576  return;
577  // Removing a store here can leave MemorySSA in an unoptimized state by
578  // creating MemoryPhis that have identical arguments and by creating
579  // MemoryUses whose defining access is not an actual clobber. We handle the
580  // phi case eagerly here. The non-optimized MemoryUse case is lazily
581  // updated by MemorySSA getClobberingMemoryAccess.
582  if (MemoryAccess *MA = MSSA->getMemoryAccess(Inst)) {
583  // Optimize MemoryPhi nodes that may become redundant by having all the
584  // same input values once MA is removed.
585  SmallSetVector<MemoryPhi *, 4> PhisToCheck;
587  WorkQueue.push_back(MA);
588  // Process MemoryPhi nodes in FIFO order using a ever-growing vector since
589  // we shouldn't be processing that many phis and this will avoid an
590  // allocation in almost all cases.
591  for (unsigned I = 0; I < WorkQueue.size(); ++I) {
592  MemoryAccess *WI = WorkQueue[I];
593 
594  for (auto *U : WI->users())
595  if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U))
596  PhisToCheck.insert(MP);
597 
598  MSSAUpdater->removeMemoryAccess(WI);
599 
600  for (MemoryPhi *MP : PhisToCheck) {
601  MemoryAccess *FirstIn = MP->getIncomingValue(0);
602  if (llvm::all_of(MP->incoming_values(),
603  [=](Use &In) { return In == FirstIn; }))
604  WorkQueue.push_back(MP);
605  }
606  PhisToCheck.clear();
607  }
608  }
609  }
610 };
611 
612 } // end anonymous namespace
613 
614 /// Determine if the memory referenced by LaterInst is from the same heap
615 /// version as EarlierInst.
616 /// This is currently called in two scenarios:
617 ///
618 /// load p
619 /// ...
620 /// load p
621 ///
622 /// and
623 ///
624 /// x = load p
625 /// ...
626 /// store x, p
627 ///
628 /// in both cases we want to verify that there are no possible writes to the
629 /// memory referenced by p between the earlier and later instruction.
630 bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
631  unsigned LaterGeneration,
632  Instruction *EarlierInst,
633  Instruction *LaterInst) {
634  // Check the simple memory generation tracking first.
635  if (EarlierGeneration == LaterGeneration)
636  return true;
637 
638  if (!MSSA)
639  return false;
640 
641  // If MemorySSA has determined that one of EarlierInst or LaterInst does not
642  // read/write memory, then we can safely return true here.
643  // FIXME: We could be more aggressive when checking doesNotAccessMemory(),
644  // onlyReadsMemory(), mayReadFromMemory(), and mayWriteToMemory() in this pass
645  // by also checking the MemorySSA MemoryAccess on the instruction. Initial
646  // experiments suggest this isn't worthwhile, at least for C/C++ code compiled
647  // with the default optimization pipeline.
648  auto *EarlierMA = MSSA->getMemoryAccess(EarlierInst);
649  if (!EarlierMA)
650  return true;
651  auto *LaterMA = MSSA->getMemoryAccess(LaterInst);
652  if (!LaterMA)
653  return true;
654 
655  // Since we know LaterDef dominates LaterInst and EarlierInst dominates
656  // LaterInst, if LaterDef dominates EarlierInst then it can't occur between
657  // EarlierInst and LaterInst and neither can any other write that potentially
658  // clobbers LaterInst.
659  MemoryAccess *LaterDef =
660  MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
661  return MSSA->dominates(LaterDef, EarlierMA);
662 }
663 
664 bool EarlyCSE::processNode(DomTreeNode *Node) {
665  bool Changed = false;
666  BasicBlock *BB = Node->getBlock();
667 
668  // If this block has a single predecessor, then the predecessor is the parent
669  // of the domtree node and all of the live out memory values are still current
670  // in this block. If this block has multiple predecessors, then they could
671  // have invalidated the live-out memory values of our parent value. For now,
672  // just be conservative and invalidate memory if this block has multiple
673  // predecessors.
674  if (!BB->getSinglePredecessor())
675  ++CurrentGeneration;
676 
677  // If this node has a single predecessor which ends in a conditional branch,
678  // we can infer the value of the branch condition given that we took this
679  // path. We need the single predecessor to ensure there's not another path
680  // which reaches this block where the condition might hold a different
681  // value. Since we're adding this to the scoped hash table (like any other
682  // def), it will have been popped if we encounter a future merge block.
683  if (BasicBlock *Pred = BB->getSinglePredecessor()) {
684  auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());
685  if (BI && BI->isConditional()) {
686  auto *CondInst = dyn_cast<Instruction>(BI->getCondition());
687  if (CondInst && SimpleValue::canHandle(CondInst)) {
688  assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
689  auto *TorF = (BI->getSuccessor(0) == BB)
692  AvailableValues.insert(CondInst, TorF);
693  DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
694  << CondInst->getName() << "' as " << *TorF << " in "
695  << BB->getName() << "\n");
696  // Replace all dominated uses with the known value.
697  if (unsigned Count = replaceDominatedUsesWith(
698  CondInst, TorF, DT, BasicBlockEdge(Pred, BB))) {
699  Changed = true;
700  NumCSECVP += Count;
701  }
702  }
703  }
704  }
705 
706  /// LastStore - Keep track of the last non-volatile store that we saw... for
707  /// as long as there in no instruction that reads memory. If we see a store
708  /// to the same location, we delete the dead store. This zaps trivial dead
709  /// stores which can occur in bitfield code among other things.
710  Instruction *LastStore = nullptr;
711 
712  // See if any instructions in the block can be eliminated. If so, do it. If
713  // not, add them to AvailableValues.
714  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
715  Instruction *Inst = &*I++;
716 
717  // Dead instructions should just be removed.
718  if (isInstructionTriviallyDead(Inst, &TLI)) {
719  DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
720  salvageDebugInfo(*Inst);
721  removeMSSA(Inst);
722  Inst->eraseFromParent();
723  Changed = true;
724  ++NumSimplify;
725  continue;
726  }
727 
728  // Skip assume intrinsics, they don't really have side effects (although
729  // they're marked as such to ensure preservation of control dependencies),
730  // and this pass will not bother with its removal. However, we should mark
731  // its condition as true for all dominated blocks.
732  if (match(Inst, m_Intrinsic<Intrinsic::assume>())) {
733  auto *CondI =
734  dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0));
735  if (CondI && SimpleValue::canHandle(CondI)) {
736  DEBUG(dbgs() << "EarlyCSE considering assumption: " << *Inst << '\n');
737  AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
738  } else
739  DEBUG(dbgs() << "EarlyCSE skipping assumption: " << *Inst << '\n');
740  continue;
741  }
742 
743  // Skip sideeffect intrinsics, for the same reason as assume intrinsics.
744  if (match(Inst, m_Intrinsic<Intrinsic::sideeffect>())) {
745  DEBUG(dbgs() << "EarlyCSE skipping sideeffect: " << *Inst << '\n');
746  continue;
747  }
748 
749  // Skip invariant.start intrinsics since they only read memory, and we can
750  // forward values across it. Also, we dont need to consume the last store
751  // since the semantics of invariant.start allow us to perform DSE of the
752  // last store, if there was a store following invariant.start. Consider:
753  //
754  // store 30, i8* p
755  // invariant.start(p)
756  // store 40, i8* p
757  // We can DSE the store to 30, since the store 40 to invariant location p
758  // causes undefined behaviour.
759  if (match(Inst, m_Intrinsic<Intrinsic::invariant_start>()))
760  continue;
761 
762  if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
763  if (auto *CondI =
764  dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
765  if (SimpleValue::canHandle(CondI)) {
766  // Do we already know the actual value of this condition?
767  if (auto *KnownCond = AvailableValues.lookup(CondI)) {
768  // Is the condition known to be true?
769  if (isa<ConstantInt>(KnownCond) &&
770  cast<ConstantInt>(KnownCond)->isOne()) {
771  DEBUG(dbgs() << "EarlyCSE removing guard: " << *Inst << '\n');
772  removeMSSA(Inst);
773  Inst->eraseFromParent();
774  Changed = true;
775  continue;
776  } else
777  // Use the known value if it wasn't true.
778  cast<CallInst>(Inst)->setArgOperand(0, KnownCond);
779  }
780  // The condition we're on guarding here is true for all dominated
781  // locations.
782  AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
783  }
784  }
785 
786  // Guard intrinsics read all memory, but don't write any memory.
787  // Accordingly, don't update the generation but consume the last store (to
788  // avoid an incorrect DSE).
789  LastStore = nullptr;
790  continue;
791  }
792 
793  // If the instruction can be simplified (e.g. X+0 = X) then replace it with
794  // its simpler value.
795  if (Value *V = SimplifyInstruction(Inst, SQ)) {
796  DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << " to: " << *V << '\n');
797  bool Killed = false;
798  if (!Inst->use_empty()) {
799  Inst->replaceAllUsesWith(V);
800  Changed = true;
801  }
802  if (isInstructionTriviallyDead(Inst, &TLI)) {
803  removeMSSA(Inst);
804  Inst->eraseFromParent();
805  Changed = true;
806  Killed = true;
807  }
808  if (Changed)
809  ++NumSimplify;
810  if (Killed)
811  continue;
812  }
813 
814  // If this is a simple instruction that we can value number, process it.
815  if (SimpleValue::canHandle(Inst)) {
816  // See if the instruction has an available value. If so, use it.
817  if (Value *V = AvailableValues.lookup(Inst)) {
818  DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << " to: " << *V << '\n');
819  if (auto *I = dyn_cast<Instruction>(V))
820  I->andIRFlags(Inst);
821  Inst->replaceAllUsesWith(V);
822  removeMSSA(Inst);
823  Inst->eraseFromParent();
824  Changed = true;
825  ++NumCSE;
826  continue;
827  }
828 
829  // Otherwise, just remember that this value is available.
830  AvailableValues.insert(Inst, Inst);
831  continue;
832  }
833 
834  ParseMemoryInst MemInst(Inst, TTI);
835  // If this is a non-volatile load, process it.
836  if (MemInst.isValid() && MemInst.isLoad()) {
837  // (conservatively) we can't peak past the ordering implied by this
838  // operation, but we can add this load to our set of available values
839  if (MemInst.isVolatile() || !MemInst.isUnordered()) {
840  LastStore = nullptr;
841  ++CurrentGeneration;
842  }
843 
844  // If we have an available version of this load, and if it is the right
845  // generation or the load is known to be from an invariant location,
846  // replace this instruction.
847  //
848  // If either the dominating load or the current load are invariant, then
849  // we can assume the current load loads the same value as the dominating
850  // load.
851  LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
852  if (InVal.DefInst != nullptr &&
853  InVal.MatchingId == MemInst.getMatchingId() &&
854  // We don't yet handle removing loads with ordering of any kind.
855  !MemInst.isVolatile() && MemInst.isUnordered() &&
856  // We can't replace an atomic load with one which isn't also atomic.
857  InVal.IsAtomic >= MemInst.isAtomic() &&
858  (InVal.IsInvariant || MemInst.isInvariantLoad() ||
859  isSameMemGeneration(InVal.Generation, CurrentGeneration,
860  InVal.DefInst, Inst))) {
861  Value *Op = getOrCreateResult(InVal.DefInst, Inst->getType());
862  if (Op != nullptr) {
863  DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
864  << " to: " << *InVal.DefInst << '\n');
865  if (!Inst->use_empty())
866  Inst->replaceAllUsesWith(Op);
867  removeMSSA(Inst);
868  Inst->eraseFromParent();
869  Changed = true;
870  ++NumCSELoad;
871  continue;
872  }
873  }
874 
875  // Otherwise, remember that we have this instruction.
876  AvailableLoads.insert(
877  MemInst.getPointerOperand(),
878  LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
879  MemInst.isAtomic(), MemInst.isInvariantLoad()));
880  LastStore = nullptr;
881  continue;
882  }
883 
884  // If this instruction may read from memory or throw (and potentially read
885  // from memory in the exception handler), forget LastStore. Load/store
886  // intrinsics will indicate both a read and a write to memory. The target
887  // may override this (e.g. so that a store intrinsic does not read from
888  // memory, and thus will be treated the same as a regular store for
889  // commoning purposes).
890  if ((Inst->mayReadFromMemory() || Inst->mayThrow()) &&
891  !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
892  LastStore = nullptr;
893 
894  // If this is a read-only call, process it.
895  if (CallValue::canHandle(Inst)) {
896  // If we have an available version of this call, and if it is the right
897  // generation, replace this instruction.
898  std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(Inst);
899  if (InVal.first != nullptr &&
900  isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
901  Inst)) {
902  DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst
903  << " to: " << *InVal.first << '\n');
904  if (!Inst->use_empty())
905  Inst->replaceAllUsesWith(InVal.first);
906  removeMSSA(Inst);
907  Inst->eraseFromParent();
908  Changed = true;
909  ++NumCSECall;
910  continue;
911  }
912 
913  // Otherwise, remember that we have this instruction.
914  AvailableCalls.insert(
915  Inst, std::pair<Instruction *, unsigned>(Inst, CurrentGeneration));
916  continue;
917  }
918 
919  // A release fence requires that all stores complete before it, but does
920  // not prevent the reordering of following loads 'before' the fence. As a
921  // result, we don't need to consider it as writing to memory and don't need
922  // to advance the generation. We do need to prevent DSE across the fence,
923  // but that's handled above.
924  if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
925  if (FI->getOrdering() == AtomicOrdering::Release) {
926  assert(Inst->mayReadFromMemory() && "relied on to prevent DSE above");
927  continue;
928  }
929 
930  // write back DSE - If we write back the same value we just loaded from
931  // the same location and haven't passed any intervening writes or ordering
932  // operations, we can remove the write. The primary benefit is in allowing
933  // the available load table to remain valid and value forward past where
934  // the store originally was.
935  if (MemInst.isValid() && MemInst.isStore()) {
936  LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
937  if (InVal.DefInst &&
938  InVal.DefInst == getOrCreateResult(Inst, InVal.DefInst->getType()) &&
939  InVal.MatchingId == MemInst.getMatchingId() &&
940  // We don't yet handle removing stores with ordering of any kind.
941  !MemInst.isVolatile() && MemInst.isUnordered() &&
942  isSameMemGeneration(InVal.Generation, CurrentGeneration,
943  InVal.DefInst, Inst)) {
944  // It is okay to have a LastStore to a different pointer here if MemorySSA
945  // tells us that the load and store are from the same memory generation.
946  // In that case, LastStore should keep its present value since we're
947  // removing the current store.
948  assert((!LastStore ||
949  ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
950  MemInst.getPointerOperand() ||
951  MSSA) &&
952  "can't have an intervening store if not using MemorySSA!");
953  DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << *Inst << '\n');
954  removeMSSA(Inst);
955  Inst->eraseFromParent();
956  Changed = true;
957  ++NumDSE;
958  // We can avoid incrementing the generation count since we were able
959  // to eliminate this store.
960  continue;
961  }
962  }
963 
964  // Okay, this isn't something we can CSE at all. Check to see if it is
965  // something that could modify memory. If so, our available memory values
966  // cannot be used so bump the generation count.
967  if (Inst->mayWriteToMemory()) {
968  ++CurrentGeneration;
969 
970  if (MemInst.isValid() && MemInst.isStore()) {
971  // We do a trivial form of DSE if there are two stores to the same
972  // location with no intervening loads. Delete the earlier store.
973  // At the moment, we don't remove ordered stores, but do remove
974  // unordered atomic stores. There's no special requirement (for
975  // unordered atomics) about removing atomic stores only in favor of
976  // other atomic stores since we we're going to execute the non-atomic
977  // one anyway and the atomic one might never have become visible.
978  if (LastStore) {
979  ParseMemoryInst LastStoreMemInst(LastStore, TTI);
980  assert(LastStoreMemInst.isUnordered() &&
981  !LastStoreMemInst.isVolatile() &&
982  "Violated invariant");
983  if (LastStoreMemInst.isMatchingMemLoc(MemInst)) {
984  DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
985  << " due to: " << *Inst << '\n');
986  removeMSSA(LastStore);
987  LastStore->eraseFromParent();
988  Changed = true;
989  ++NumDSE;
990  LastStore = nullptr;
991  }
992  // fallthrough - we can exploit information about this store
993  }
994 
995  // Okay, we just invalidated anything we knew about loaded values. Try
996  // to salvage *something* by remembering that the stored value is a live
997  // version of the pointer. It is safe to forward from volatile stores
998  // to non-volatile loads, so we don't have to check for volatility of
999  // the store.
1000  AvailableLoads.insert(
1001  MemInst.getPointerOperand(),
1002  LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
1003  MemInst.isAtomic(), /*IsInvariant=*/false));
1004 
1005  // Remember that this was the last unordered store we saw for DSE. We
1006  // don't yet handle DSE on ordered or volatile stores since we don't
1007  // have a good way to model the ordering requirement for following
1008  // passes once the store is removed. We could insert a fence, but
1009  // since fences are slightly stronger than stores in their ordering,
1010  // it's not clear this is a profitable transform. Another option would
1011  // be to merge the ordering with that of the post dominating store.
1012  if (MemInst.isUnordered() && !MemInst.isVolatile())
1013  LastStore = Inst;
1014  else
1015  LastStore = nullptr;
1016  }
1017  }
1018  }
1019 
1020  return Changed;
1021 }
1022 
1023 bool EarlyCSE::run() {
1024  // Note, deque is being used here because there is significant performance
1025  // gains over vector when the container becomes very large due to the
1026  // specific access patterns. For more information see the mailing list
1027  // discussion on this:
1028  // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
1029  std::deque<StackNode *> nodesToProcess;
1030 
1031  bool Changed = false;
1032 
1033  // Process the root node.
1034  nodesToProcess.push_back(new StackNode(
1035  AvailableValues, AvailableLoads, AvailableCalls, CurrentGeneration,
1036  DT.getRootNode(), DT.getRootNode()->begin(), DT.getRootNode()->end()));
1037 
1038  // Save the current generation.
1039  unsigned LiveOutGeneration = CurrentGeneration;
1040 
1041  // Process the stack.
1042  while (!nodesToProcess.empty()) {
1043  // Grab the first item off the stack. Set the current generation, remove
1044  // the node from the stack, and process it.
1045  StackNode *NodeToProcess = nodesToProcess.back();
1046 
1047  // Initialize class members.
1048  CurrentGeneration = NodeToProcess->currentGeneration();
1049 
1050  // Check if the node needs to be processed.
1051  if (!NodeToProcess->isProcessed()) {
1052  // Process the node.
1053  Changed |= processNode(NodeToProcess->node());
1054  NodeToProcess->childGeneration(CurrentGeneration);
1055  NodeToProcess->process();
1056  } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
1057  // Push the next child onto the stack.
1058  DomTreeNode *child = NodeToProcess->nextChild();
1059  nodesToProcess.push_back(
1060  new StackNode(AvailableValues, AvailableLoads, AvailableCalls,
1061  NodeToProcess->childGeneration(), child, child->begin(),
1062  child->end()));
1063  } else {
1064  // It has been processed, and there are no more children to process,
1065  // so delete it and pop it off the stack.
1066  delete NodeToProcess;
1067  nodesToProcess.pop_back();
1068  }
1069  } // while (!nodes...)
1070 
1071  // Reset the current generation.
1072  CurrentGeneration = LiveOutGeneration;
1073 
1074  return Changed;
1075 }
1076 
1079  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1080  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1081  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1082  auto &AC = AM.getResult<AssumptionAnalysis>(F);
1083  auto *MSSA =
1084  UseMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA() : nullptr;
1085 
1086  EarlyCSE CSE(F.getParent()->getDataLayout(), TLI, TTI, DT, AC, MSSA);
1087 
1088  if (!CSE.run())
1089  return PreservedAnalyses::all();
1090 
1091  PreservedAnalyses PA;
1092  PA.preserveSet<CFGAnalyses>();
1093  PA.preserve<GlobalsAA>();
1094  if (UseMemorySSA)
1096  return PA;
1097 }
1098 
1099 namespace {
1100 
1101 /// \brief A simple and fast domtree-based CSE pass.
1102 ///
1103 /// This pass does a simple depth-first walk over the dominator tree,
1104 /// eliminating trivially redundant instructions and using instsimplify to
1105 /// canonicalize things as it goes. It is intended to be fast and catch obvious
1106 /// cases so that instcombine and other passes are more effective. It is
1107 /// expected that a later pass of GVN will catch the interesting/hard cases.
1108 template<bool UseMemorySSA>
1109 class EarlyCSELegacyCommonPass : public FunctionPass {
1110 public:
1111  static char ID;
1112 
1113  EarlyCSELegacyCommonPass() : FunctionPass(ID) {
1114  if (UseMemorySSA)
1116  else
1118  }
1119 
1120  bool runOnFunction(Function &F) override {
1121  if (skipFunction(F))
1122  return false;
1123 
1124  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1125  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1126  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1127  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1128  auto *MSSA =
1129  UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() : nullptr;
1130 
1131  EarlyCSE CSE(F.getParent()->getDataLayout(), TLI, TTI, DT, AC, MSSA);
1132 
1133  return CSE.run();
1134  }
1135 
1136  void getAnalysisUsage(AnalysisUsage &AU) const override {
1141  if (UseMemorySSA) {
1144  }
1146  AU.setPreservesCFG();
1147  }
1148 };
1149 
1150 } // end anonymous namespace
1151 
1152 using EarlyCSELegacyPass = EarlyCSELegacyCommonPass</*UseMemorySSA=*/false>;
1153 
1154 template<>
1155 char EarlyCSELegacyPass::ID = 0;
1156 
1157 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
1158  false)
1163 INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)
1164 
1165 using EarlyCSEMemSSALegacyPass =
1166  EarlyCSELegacyCommonPass</*UseMemorySSA=*/true>;
1167 
1168 template<>
1169 char EarlyCSEMemSSALegacyPass::ID = 0;
1170 
1171 FunctionPass *llvm::createEarlyCSEPass(bool UseMemorySSA) {
1172  if (UseMemorySSA)
1173  return new EarlyCSEMemSSALegacyPass();
1174  else
1175  return new EarlyCSELegacyPass();
1176 }
1177 
1178 INITIALIZE_PASS_BEGIN(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1179  "Early CSE w/ MemorySSA", false, false)
1185 INITIALIZE_PASS_END(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1186  "Early CSE w/ MemorySSA", false, false)
Legacy wrapper pass to provide the GlobalsAAResult object.
void initializeEarlyCSELegacyPassPass(PassRegistry &)
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:245
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:522
static SimpleValue getTombstoneKey()
Definition: EarlyCSE.cpp:113
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:843
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
This instruction extracts a struct member or array element value from an aggregate value...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Unsigned minimum.
Atomic ordering constants.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool isAtomic() const
Return true if this instruction has an AtomicOrdering of unordered or higher.
This is the interface for a simple mod/ref and alias analysis over globals.
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
An instruction for ordering other memory operations.
Definition: Instructions.h:440
value_op_iterator value_op_begin()
Definition: User.h:240
This class represents a function call, abstracting a target machine&#39;s calling convention.
An immutable pass that tracks lazily created AssumptionCache objects.
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
A cache of .assume calls within a function.
Analysis pass providing the TargetTransformInfo.
static CallValue getTombstoneKey()
Definition: EarlyCSE.cpp:277
value_op_iterator value_op_end()
Definition: User.h:243
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:814
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
F(f)
An instruction for reading from memory.
Definition: Instructions.h:164
This defines the Use class.
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of &#39;From&#39; with &#39;To&#39; if that use is dominated by the given edge.
Definition: Local.cpp:1988
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: EarlyCSE.cpp:1077
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
Signed maximum.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
bool isIdenticalTo(const Instruction *I) const
Return true if the specified instruction is exactly identical to the current one. ...
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:850
static Value * getPointerOperand(Instruction &Inst)
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
Absolute value.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:560
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
separate const offset from Split GEPs to a variadic base and a constant offset for better CSE
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:612
static bool isLoad(int Opcode)
static CallValue getEmptyKey()
Definition: EarlyCSE.cpp:273
RecyclingAllocator - This class wraps an Allocator, adding the functionality of recycling deleted obj...
static void cse(BasicBlock *BB)
Perform cse of induction variable instructions.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
static bool isEqual(const Function &Caller, const Function &Callee)
This file provides the interface for a simple, fast CSE pass.
early cse memssa
Definition: EarlyCSE.cpp:1185
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage any dbg.value intrinsics referr...
Definition: Local.cpp:1448
void andIRFlags(const Value *V)
Logical &#39;and&#39; of any supported wrapping, exact, and fast-math flags of V and this instruction...
static bool isStore(int Opcode)
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:126
An instruction for storing to memory.
Definition: Instructions.h:306
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
Optimize for code generation
INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false) using EarlyCSEMemSSALegacyPass
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
Value * getOperand(unsigned i) const
Definition: User.h:154
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:378
NodeT * getBlock() const
static bool runOnFunction(Function &F, bool PostInlining)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:217
bool isIdenticalToWhenDefined(const Instruction *I) const
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags, which may specify conditions under which the instruction&#39;s result is undefined.
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
Conditional or Unconditional Branch instruction.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static SimpleValue getEmptyKey()
Definition: EarlyCSE.cpp:109
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool mayThrow() const
Return true if this instruction may throw an exception.
Represent the analysis usage information of a pass.
Analysis pass providing a never-invalidated alias analysis result.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:853
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
static bool isAtomic(Instruction *I)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
MemoryUseOrDef * getMemoryAccess(const Instruction *) const
Given a memory Mod/Ref&#39;ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.cpp:1737
Floating point maxnum.
A function analysis which provides an AssumptionCache.
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
Iterator for intrusive lists based on ilist_node.
SelectPatternFlavor Flavor
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
iterator end()
Definition: BasicBlock.h:254
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
SelectPatternFlavor
Specific patterns of select instructions we can match.
Provides information about what library functions are available for the current target.
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:814
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:515
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:602
iterator_range< user_iterator > users()
Definition: Value.h:405
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:480
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
Basic Alias true
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:927
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:189
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
Value * getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst, Type *ExpectedType) const
#define I(x, y, z)
Definition: MD5.cpp:58
bool mayReadFromMemory() const
Return true if this instruction may read memory.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
Signed minimum.
EarlyCSELegacyCommonPass< false > EarlyCSELegacyPass
Definition: EarlyCSE.cpp:1152
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) const
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:559
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:345
LLVM Value Representation.
Definition: Value.h:73
typename std::vector< DomTreeNodeBase *>::iterator iterator
void initializeEarlyCSEMemSSALegacyPassPass(PassRegistry &)
#define DEBUG(X)
Definition: Debug.h:118
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
FunctionPass * createEarlyCSEPass(bool UseMemorySSA=false)
Definition: EarlyCSE.cpp:1171
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
This pass exposes codegen information to IR-level passes.
static bool isVolatile(Instruction *Inst)
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:431
This header defines various interfaces for pass management in LLVM.
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Information about a load/store intrinsic defined by the target.
bool use_empty() const
Definition: Value.h:328
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
This instruction inserts a struct field of array element value into an aggregate value.