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