LLVM  9.0.0svn
EarlyCSE.cpp
Go to the documentation of this file.
1 //===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass performs a simple dominator tree walk that eliminates trivially
10 // redundant instructions.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/DenseMapInfo.h"
16 #include "llvm/ADT/Hashing.h"
17 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
32 #include "llvm/IR/BasicBlock.h"
33 #include "llvm/IR/Constants.h"
34 #include "llvm/IR/DataLayout.h"
35 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/Function.h"
37 #include "llvm/IR/InstrTypes.h"
38 #include "llvm/IR/Instruction.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/IntrinsicInst.h"
41 #include "llvm/IR/Intrinsics.h"
42 #include "llvm/IR/LLVMContext.h"
43 #include "llvm/IR/PassManager.h"
44 #include "llvm/IR/PatternMatch.h"
45 #include "llvm/IR/Type.h"
46 #include "llvm/IR/Use.h"
47 #include "llvm/IR/Value.h"
48 #include "llvm/Pass.h"
49 #include "llvm/Support/Allocator.h"
51 #include "llvm/Support/Casting.h"
52 #include "llvm/Support/Debug.h"
56 #include "llvm/Transforms/Scalar.h"
58 #include <cassert>
59 #include <deque>
60 #include <memory>
61 #include <utility>
62 
63 using namespace llvm;
64 using namespace llvm::PatternMatch;
65 
66 #define DEBUG_TYPE "early-cse"
67 
68 STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
69 STATISTIC(NumCSE, "Number of instructions CSE'd");
70 STATISTIC(NumCSECVP, "Number of compare instructions CVP'd");
71 STATISTIC(NumCSELoad, "Number of load instructions CSE'd");
72 STATISTIC(NumCSECall, "Number of call instructions CSE'd");
73 STATISTIC(NumDSE, "Number of trivial dead stores removed");
74 
75 DEBUG_COUNTER(CSECounter, "early-cse",
76  "Controls which instructions are removed");
77 
79  "earlycse-mssa-optimization-cap", cl::init(500), cl::Hidden,
80  cl::desc("Enable imprecision in EarlyCSE in pathological cases, in exchange "
81  "for faster compile. Caps the MemorySSA clobbering calls."));
82 
83 //===----------------------------------------------------------------------===//
84 // SimpleValue
85 //===----------------------------------------------------------------------===//
86 
87 namespace {
88 
89 /// Struct representing the available values in the scoped hash table.
90 struct SimpleValue {
91  Instruction *Inst;
92 
93  SimpleValue(Instruction *I) : Inst(I) {
94  assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
95  }
96 
97  bool isSentinel() const {
100  }
101 
102  static bool canHandle(Instruction *Inst) {
103  // This can only handle non-void readnone functions.
104  if (CallInst *CI = dyn_cast<CallInst>(Inst))
105  return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
106  return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
107  isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
108  isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
109  isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
110  isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
111  }
112 };
113 
114 } // end anonymous namespace
115 
116 namespace llvm {
117 
118 template <> struct DenseMapInfo<SimpleValue> {
119  static inline SimpleValue getEmptyKey() {
121  }
122 
123  static inline SimpleValue getTombstoneKey() {
125  }
126 
127  static unsigned getHashValue(SimpleValue Val);
128  static bool isEqual(SimpleValue LHS, SimpleValue RHS);
129 };
130 
131 } // end namespace llvm
132 
133 /// Match a 'select' including an optional 'not' of the condition.
135  Value *&T, Value *&F) {
136  if (match(V, m_Select(m_Value(Cond), m_Value(T), m_Value(F)))) {
137  // Look through a 'not' of the condition operand by swapping true/false.
138  Value *CondNot;
139  if (match(Cond, m_Not(m_Value(CondNot)))) {
140  Cond = CondNot;
141  std::swap(T, F);
142  }
143  return true;
144  }
145  return false;
146 }
147 
148 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
149  Instruction *Inst = Val.Inst;
150  // Hash in all of the operands as pointers.
151  if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
152  Value *LHS = BinOp->getOperand(0);
153  Value *RHS = BinOp->getOperand(1);
154  if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
155  std::swap(LHS, RHS);
156 
157  return hash_combine(BinOp->getOpcode(), LHS, RHS);
158  }
159 
160  if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
161  Value *LHS = CI->getOperand(0);
162  Value *RHS = CI->getOperand(1);
163  CmpInst::Predicate Pred = CI->getPredicate();
164  if (Inst->getOperand(0) > Inst->getOperand(1)) {
165  std::swap(LHS, RHS);
166  Pred = CI->getSwappedPredicate();
167  }
168  return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
169  }
170 
171  // Hash min/max/abs (cmp + select) to allow for commuted operands.
172  // Min/max may also have non-canonical compare predicate (eg, the compare for
173  // smin may use 'sgt' rather than 'slt'), and non-canonical operands in the
174  // compare.
175  Value *A, *B;
177  // TODO: We should also detect FP min/max.
178  if (SPF == SPF_SMIN || SPF == SPF_SMAX ||
179  SPF == SPF_UMIN || SPF == SPF_UMAX) {
180  if (A > B)
181  std::swap(A, B);
182  return hash_combine(Inst->getOpcode(), SPF, A, B);
183  }
184  if (SPF == SPF_ABS || SPF == SPF_NABS) {
185  // ABS/NABS always puts the input in A and its negation in B.
186  return hash_combine(Inst->getOpcode(), SPF, A, B);
187  }
188 
189  // Hash general selects to allow matching commuted true/false operands.
190  Value *Cond, *TVal, *FVal;
191  if (matchSelectWithOptionalNotCond(Inst, Cond, TVal, FVal)) {
192  // If we do not have a compare as the condition, just hash in the condition.
193  CmpInst::Predicate Pred;
194  Value *X, *Y;
195  if (!match(Cond, m_Cmp(Pred, m_Value(X), m_Value(Y))))
196  return hash_combine(Inst->getOpcode(), Cond, TVal, FVal);
197 
198  // Similar to cmp normalization (above) - canonicalize the predicate value:
199  // select (icmp Pred, X, Y), T, F --> select (icmp InvPred, X, Y), F, T
200  if (CmpInst::getInversePredicate(Pred) < Pred) {
201  Pred = CmpInst::getInversePredicate(Pred);
202  std::swap(TVal, FVal);
203  }
204  return hash_combine(Inst->getOpcode(), Pred, X, Y, TVal, FVal);
205  }
206 
207  if (CastInst *CI = dyn_cast<CastInst>(Inst))
208  return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
209 
210  if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
211  return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
212  hash_combine_range(EVI->idx_begin(), EVI->idx_end()));
213 
214  if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
215  return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
216  IVI->getOperand(1),
217  hash_combine_range(IVI->idx_begin(), IVI->idx_end()));
218 
219  assert((isa<CallInst>(Inst) || isa<GetElementPtrInst>(Inst) ||
220  isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
221  isa<ShuffleVectorInst>(Inst)) &&
222  "Invalid/unknown instruction");
223 
224  // Mix in the opcode.
225  return hash_combine(
226  Inst->getOpcode(),
228 }
229 
230 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
231  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
232 
233  if (LHS.isSentinel() || RHS.isSentinel())
234  return LHSI == RHSI;
235 
236  if (LHSI->getOpcode() != RHSI->getOpcode())
237  return false;
238  if (LHSI->isIdenticalToWhenDefined(RHSI))
239  return true;
240 
241  // If we're not strictly identical, we still might be a commutable instruction
242  if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
243  if (!LHSBinOp->isCommutative())
244  return false;
245 
246  assert(isa<BinaryOperator>(RHSI) &&
247  "same opcode, but different instruction type?");
248  BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
249 
250  // Commuted equality
251  return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
252  LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
253  }
254  if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
255  assert(isa<CmpInst>(RHSI) &&
256  "same opcode, but different instruction type?");
257  CmpInst *RHSCmp = cast<CmpInst>(RHSI);
258  // Commuted equality
259  return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
260  LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
261  LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
262  }
263 
264  // Min/max/abs can occur with commuted operands, non-canonical predicates,
265  // and/or non-canonical operands.
266  Value *LHSA, *LHSB;
267  SelectPatternFlavor LSPF = matchSelectPattern(LHSI, LHSA, LHSB).Flavor;
268  // TODO: We should also detect FP min/max.
269  if (LSPF == SPF_SMIN || LSPF == SPF_SMAX ||
270  LSPF == SPF_UMIN || LSPF == SPF_UMAX ||
271  LSPF == SPF_ABS || LSPF == SPF_NABS) {
272  Value *RHSA, *RHSB;
273  SelectPatternFlavor RSPF = matchSelectPattern(RHSI, RHSA, RHSB).Flavor;
274  if (LSPF == RSPF) {
275  // Abs results are placed in a defined order by matchSelectPattern.
276  if (LSPF == SPF_ABS || LSPF == SPF_NABS)
277  return LHSA == RHSA && LHSB == RHSB;
278  return ((LHSA == RHSA && LHSB == RHSB) ||
279  (LHSA == RHSB && LHSB == RHSA));
280  }
281  }
282 
283  // Selects can be non-trivially equivalent via inverted conditions and swaps.
284  Value *CondL, *CondR, *TrueL, *TrueR, *FalseL, *FalseR;
285  if (matchSelectWithOptionalNotCond(LHSI, CondL, TrueL, FalseL) &&
286  matchSelectWithOptionalNotCond(RHSI, CondR, TrueR, FalseR)) {
287  // select Cond, T, F <--> select not(Cond), F, T
288  if (CondL == CondR && TrueL == TrueR && FalseL == FalseR)
289  return true;
290 
291  // If the true/false operands are swapped and the conditions are compares
292  // with inverted predicates, the selects are equal:
293  // select (icmp Pred, X, Y), T, F <--> select (icmp InvPred, X, Y), F, T
294  //
295  // This also handles patterns with a double-negation because we looked
296  // through a 'not' in the matching function and swapped T/F:
297  // select (cmp Pred, X, Y), T, F <--> select (not (cmp InvPred, X, Y)), T, F
298  if (TrueL == FalseR && FalseL == TrueR) {
299  CmpInst::Predicate PredL, PredR;
300  Value *X, *Y;
301  if (match(CondL, m_Cmp(PredL, m_Value(X), m_Value(Y))) &&
302  match(CondR, m_Cmp(PredR, m_Specific(X), m_Specific(Y))) &&
303  CmpInst::getInversePredicate(PredL) == PredR)
304  return true;
305  }
306  }
307 
308  return false;
309 }
310 
311 //===----------------------------------------------------------------------===//
312 // CallValue
313 //===----------------------------------------------------------------------===//
314 
315 namespace {
316 
317 /// Struct representing the available call values in the scoped hash
318 /// table.
319 struct CallValue {
320  Instruction *Inst;
321 
322  CallValue(Instruction *I) : Inst(I) {
323  assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
324  }
325 
326  bool isSentinel() const {
327  return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
329  }
330 
331  static bool canHandle(Instruction *Inst) {
332  // Don't value number anything that returns void.
333  if (Inst->getType()->isVoidTy())
334  return false;
335 
336  CallInst *CI = dyn_cast<CallInst>(Inst);
337  if (!CI || !CI->onlyReadsMemory())
338  return false;
339  return true;
340  }
341 };
342 
343 } // end anonymous namespace
344 
345 namespace llvm {
346 
347 template <> struct DenseMapInfo<CallValue> {
348  static inline CallValue getEmptyKey() {
350  }
351 
352  static inline CallValue getTombstoneKey() {
354  }
355 
356  static unsigned getHashValue(CallValue Val);
357  static bool isEqual(CallValue LHS, CallValue RHS);
358 };
359 
360 } // end namespace llvm
361 
362 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
363  Instruction *Inst = Val.Inst;
364  // Hash all of the operands as pointers and mix in the opcode.
365  return hash_combine(
366  Inst->getOpcode(),
368 }
369 
370 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
371  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
372  if (LHS.isSentinel() || RHS.isSentinel())
373  return LHSI == RHSI;
374  return LHSI->isIdenticalTo(RHSI);
375 }
376 
377 //===----------------------------------------------------------------------===//
378 // EarlyCSE implementation
379 //===----------------------------------------------------------------------===//
380 
381 namespace {
382 
383 /// A simple and fast domtree-based CSE pass.
384 ///
385 /// This pass does a simple depth-first walk over the dominator tree,
386 /// eliminating trivially redundant instructions and using instsimplify to
387 /// canonicalize things as it goes. It is intended to be fast and catch obvious
388 /// cases so that instcombine and other passes are more effective. It is
389 /// expected that a later pass of GVN will catch the interesting/hard cases.
390 class EarlyCSE {
391 public:
392  const TargetLibraryInfo &TLI;
393  const TargetTransformInfo &TTI;
394  DominatorTree &DT;
395  AssumptionCache &AC;
396  const SimplifyQuery SQ;
397  MemorySSA *MSSA;
398  std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
399 
400  using AllocatorTy =
403  using ScopedHTType =
405  AllocatorTy>;
406 
407  /// A scoped hash table of the current values of all of our simple
408  /// scalar expressions.
409  ///
410  /// As we walk down the domtree, we look to see if instructions are in this:
411  /// if so, we replace them with what we find, otherwise we insert them so
412  /// that dominated values can succeed in their lookup.
413  ScopedHTType AvailableValues;
414 
415  /// A scoped hash table of the current values of previously encountered
416  /// memory locations.
417  ///
418  /// This allows us to get efficient access to dominating loads or stores when
419  /// we have a fully redundant load. In addition to the most recent load, we
420  /// keep track of a generation count of the read, which is compared against
421  /// the current generation count. The current generation count is incremented
422  /// after every possibly writing memory operation, which ensures that we only
423  /// CSE loads with other loads that have no intervening store. Ordering
424  /// events (such as fences or atomic instructions) increment the generation
425  /// count as well; essentially, we model these as writes to all possible
426  /// locations. Note that atomic and/or volatile loads and stores can be
427  /// present the table; it is the responsibility of the consumer to inspect
428  /// the atomicity/volatility if needed.
429  struct LoadValue {
430  Instruction *DefInst = nullptr;
431  unsigned Generation = 0;
432  int MatchingId = -1;
433  bool IsAtomic = false;
434 
435  LoadValue() = default;
436  LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,
437  bool IsAtomic)
438  : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
439  IsAtomic(IsAtomic) {}
440  };
441 
442  using LoadMapAllocator =
445  using LoadHTType =
447  LoadMapAllocator>;
448 
449  LoadHTType AvailableLoads;
450 
451  // A scoped hash table mapping memory locations (represented as typed
452  // addresses) to generation numbers at which that memory location became
453  // (henceforth indefinitely) invariant.
454  using InvariantMapAllocator =
457  using InvariantHTType =
459  InvariantMapAllocator>;
460  InvariantHTType AvailableInvariants;
461 
462  /// A scoped hash table of the current values of read-only call
463  /// values.
464  ///
465  /// It uses the same generation count as loads.
466  using CallHTType =
468  CallHTType AvailableCalls;
469 
470  /// This is the current generation of the memory value.
471  unsigned CurrentGeneration = 0;
472 
473  /// Set up the EarlyCSE runner for a particular function.
474  EarlyCSE(const DataLayout &DL, const TargetLibraryInfo &TLI,
475  const TargetTransformInfo &TTI, DominatorTree &DT,
476  AssumptionCache &AC, MemorySSA *MSSA)
477  : TLI(TLI), TTI(TTI), DT(DT), AC(AC), SQ(DL, &TLI, &DT, &AC), MSSA(MSSA),
478  MSSAUpdater(llvm::make_unique<MemorySSAUpdater>(MSSA)) {}
479 
480  bool run();
481 
482 private:
483  unsigned ClobberCounter = 0;
484  // Almost a POD, but needs to call the constructors for the scoped hash
485  // tables so that a new scope gets pushed on. These are RAII so that the
486  // scope gets popped when the NodeScope is destroyed.
487  class NodeScope {
488  public:
489  NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
490  InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls)
491  : Scope(AvailableValues), LoadScope(AvailableLoads),
492  InvariantScope(AvailableInvariants), CallScope(AvailableCalls) {}
493  NodeScope(const NodeScope &) = delete;
494  NodeScope &operator=(const NodeScope &) = delete;
495 
496  private:
497  ScopedHTType::ScopeTy Scope;
498  LoadHTType::ScopeTy LoadScope;
499  InvariantHTType::ScopeTy InvariantScope;
500  CallHTType::ScopeTy CallScope;
501  };
502 
503  // Contains all the needed information to create a stack for doing a depth
504  // first traversal of the tree. This includes scopes for values, loads, and
505  // calls as well as the generation. There is a child iterator so that the
506  // children do not need to be store separately.
507  class StackNode {
508  public:
509  StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
510  InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,
511  unsigned cg, DomTreeNode *n, DomTreeNode::iterator child,
513  : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
514  EndIter(end),
515  Scopes(AvailableValues, AvailableLoads, AvailableInvariants,
516  AvailableCalls)
517  {}
518  StackNode(const StackNode &) = delete;
519  StackNode &operator=(const StackNode &) = delete;
520 
521  // Accessors.
522  unsigned currentGeneration() { return CurrentGeneration; }
523  unsigned childGeneration() { return ChildGeneration; }
524  void childGeneration(unsigned generation) { ChildGeneration = generation; }
525  DomTreeNode *node() { return Node; }
526  DomTreeNode::iterator childIter() { return ChildIter; }
527 
528  DomTreeNode *nextChild() {
529  DomTreeNode *child = *ChildIter;
530  ++ChildIter;
531  return child;
532  }
533 
534  DomTreeNode::iterator end() { return EndIter; }
535  bool isProcessed() { return Processed; }
536  void process() { Processed = true; }
537 
538  private:
539  unsigned CurrentGeneration;
540  unsigned ChildGeneration;
541  DomTreeNode *Node;
542  DomTreeNode::iterator ChildIter;
543  DomTreeNode::iterator EndIter;
544  NodeScope Scopes;
545  bool Processed = false;
546  };
547 
548  /// Wrapper class to handle memory instructions, including loads,
549  /// stores and intrinsic loads and stores defined by the target.
550  class ParseMemoryInst {
551  public:
552  ParseMemoryInst(Instruction *Inst, const TargetTransformInfo &TTI)
553  : Inst(Inst) {
554  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
555  if (TTI.getTgtMemIntrinsic(II, Info))
556  IsTargetMemInst = true;
557  }
558 
559  bool isLoad() const {
560  if (IsTargetMemInst) return Info.ReadMem;
561  return isa<LoadInst>(Inst);
562  }
563 
564  bool isStore() const {
565  if (IsTargetMemInst) return Info.WriteMem;
566  return isa<StoreInst>(Inst);
567  }
568 
569  bool isAtomic() const {
570  if (IsTargetMemInst)
571  return Info.Ordering != AtomicOrdering::NotAtomic;
572  return Inst->isAtomic();
573  }
574 
575  bool isUnordered() const {
576  if (IsTargetMemInst)
577  return Info.isUnordered();
578 
579  if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
580  return LI->isUnordered();
581  } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
582  return SI->isUnordered();
583  }
584  // Conservative answer
585  return !Inst->isAtomic();
586  }
587 
588  bool isVolatile() const {
589  if (IsTargetMemInst)
590  return Info.IsVolatile;
591 
592  if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
593  return LI->isVolatile();
594  } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
595  return SI->isVolatile();
596  }
597  // Conservative answer
598  return true;
599  }
600 
601  bool isInvariantLoad() const {
602  if (auto *LI = dyn_cast<LoadInst>(Inst))
603  return LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr;
604  return false;
605  }
606 
607  bool isMatchingMemLoc(const ParseMemoryInst &Inst) const {
608  return (getPointerOperand() == Inst.getPointerOperand() &&
609  getMatchingId() == Inst.getMatchingId());
610  }
611 
612  bool isValid() const { return getPointerOperand() != nullptr; }
613 
614  // For regular (non-intrinsic) loads/stores, this is set to -1. For
615  // intrinsic loads/stores, the id is retrieved from the corresponding
616  // field in the MemIntrinsicInfo structure. That field contains
617  // non-negative values only.
618  int getMatchingId() const {
619  if (IsTargetMemInst) return Info.MatchingId;
620  return -1;
621  }
622 
623  Value *getPointerOperand() const {
624  if (IsTargetMemInst) return Info.PtrVal;
625  return getLoadStorePointerOperand(Inst);
626  }
627 
628  bool mayReadFromMemory() const {
629  if (IsTargetMemInst) return Info.ReadMem;
630  return Inst->mayReadFromMemory();
631  }
632 
633  bool mayWriteToMemory() const {
634  if (IsTargetMemInst) return Info.WriteMem;
635  return Inst->mayWriteToMemory();
636  }
637 
638  private:
639  bool IsTargetMemInst = false;
641  Instruction *Inst;
642  };
643 
644  bool processNode(DomTreeNode *Node);
645 
646  bool handleBranchCondition(Instruction *CondInst, const BranchInst *BI,
647  const BasicBlock *BB, const BasicBlock *Pred);
648 
649  Value *getOrCreateResult(Value *Inst, Type *ExpectedType) const {
650  if (auto *LI = dyn_cast<LoadInst>(Inst))
651  return LI;
652  if (auto *SI = dyn_cast<StoreInst>(Inst))
653  return SI->getValueOperand();
654  assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
655  return TTI.getOrCreateResultFromMemIntrinsic(cast<IntrinsicInst>(Inst),
656  ExpectedType);
657  }
658 
659  /// Return true if the instruction is known to only operate on memory
660  /// provably invariant in the given "generation".
661  bool isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt);
662 
663  bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
664  Instruction *EarlierInst, Instruction *LaterInst);
665 
666  void removeMSSA(Instruction *Inst) {
667  if (!MSSA)
668  return;
669  if (VerifyMemorySSA)
670  MSSA->verifyMemorySSA();
671  // Removing a store here can leave MemorySSA in an unoptimized state by
672  // creating MemoryPhis that have identical arguments and by creating
673  // MemoryUses whose defining access is not an actual clobber. The phi case
674  // is handled by MemorySSA when passing OptimizePhis = true to
675  // removeMemoryAccess. The non-optimized MemoryUse case is lazily updated
676  // by MemorySSA's getClobberingMemoryAccess.
677  MSSAUpdater->removeMemoryAccess(Inst, true);
678  }
679 };
680 
681 } // end anonymous namespace
682 
683 /// Determine if the memory referenced by LaterInst is from the same heap
684 /// version as EarlierInst.
685 /// This is currently called in two scenarios:
686 ///
687 /// load p
688 /// ...
689 /// load p
690 ///
691 /// and
692 ///
693 /// x = load p
694 /// ...
695 /// store x, p
696 ///
697 /// in both cases we want to verify that there are no possible writes to the
698 /// memory referenced by p between the earlier and later instruction.
699 bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
700  unsigned LaterGeneration,
701  Instruction *EarlierInst,
702  Instruction *LaterInst) {
703  // Check the simple memory generation tracking first.
704  if (EarlierGeneration == LaterGeneration)
705  return true;
706 
707  if (!MSSA)
708  return false;
709 
710  // If MemorySSA has determined that one of EarlierInst or LaterInst does not
711  // read/write memory, then we can safely return true here.
712  // FIXME: We could be more aggressive when checking doesNotAccessMemory(),
713  // onlyReadsMemory(), mayReadFromMemory(), and mayWriteToMemory() in this pass
714  // by also checking the MemorySSA MemoryAccess on the instruction. Initial
715  // experiments suggest this isn't worthwhile, at least for C/C++ code compiled
716  // with the default optimization pipeline.
717  auto *EarlierMA = MSSA->getMemoryAccess(EarlierInst);
718  if (!EarlierMA)
719  return true;
720  auto *LaterMA = MSSA->getMemoryAccess(LaterInst);
721  if (!LaterMA)
722  return true;
723 
724  // Since we know LaterDef dominates LaterInst and EarlierInst dominates
725  // LaterInst, if LaterDef dominates EarlierInst then it can't occur between
726  // EarlierInst and LaterInst and neither can any other write that potentially
727  // clobbers LaterInst.
728  MemoryAccess *LaterDef;
729  if (ClobberCounter < EarlyCSEMssaOptCap) {
730  LaterDef = MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
731  ClobberCounter++;
732  } else
733  LaterDef = LaterMA->getDefiningAccess();
734 
735  return MSSA->dominates(LaterDef, EarlierMA);
736 }
737 
738 bool EarlyCSE::isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt) {
739  // A location loaded from with an invariant_load is assumed to *never* change
740  // within the visible scope of the compilation.
741  if (auto *LI = dyn_cast<LoadInst>(I))
742  if (LI->getMetadata(LLVMContext::MD_invariant_load))
743  return true;
744 
745  auto MemLocOpt = MemoryLocation::getOrNone(I);
746  if (!MemLocOpt)
747  // "target" intrinsic forms of loads aren't currently known to
748  // MemoryLocation::get. TODO
749  return false;
750  MemoryLocation MemLoc = *MemLocOpt;
751  if (!AvailableInvariants.count(MemLoc))
752  return false;
753 
754  // Is the generation at which this became invariant older than the
755  // current one?
756  return AvailableInvariants.lookup(MemLoc) <= GenAt;
757 }
758 
759 bool EarlyCSE::handleBranchCondition(Instruction *CondInst,
760  const BranchInst *BI, const BasicBlock *BB,
761  const BasicBlock *Pred) {
762  assert(BI->isConditional() && "Should be a conditional branch!");
763  assert(BI->getCondition() == CondInst && "Wrong condition?");
764  assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
765  auto *TorF = (BI->getSuccessor(0) == BB)
768  auto MatchBinOp = [](Instruction *I, unsigned Opcode) {
769  if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(I))
770  return BOp->getOpcode() == Opcode;
771  return false;
772  };
773  // If the condition is AND operation, we can propagate its operands into the
774  // true branch. If it is OR operation, we can propagate them into the false
775  // branch.
776  unsigned PropagateOpcode =
777  (BI->getSuccessor(0) == BB) ? Instruction::And : Instruction::Or;
778 
779  bool MadeChanges = false;
782  WorkList.push_back(CondInst);
783  while (!WorkList.empty()) {
784  Instruction *Curr = WorkList.pop_back_val();
785 
786  AvailableValues.insert(Curr, TorF);
787  LLVM_DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
788  << Curr->getName() << "' as " << *TorF << " in "
789  << BB->getName() << "\n");
790  if (!DebugCounter::shouldExecute(CSECounter)) {
791  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
792  } else {
793  // Replace all dominated uses with the known value.
794  if (unsigned Count = replaceDominatedUsesWith(Curr, TorF, DT,
795  BasicBlockEdge(Pred, BB))) {
796  NumCSECVP += Count;
797  MadeChanges = true;
798  }
799  }
800 
801  if (MatchBinOp(Curr, PropagateOpcode))
802  for (auto &Op : cast<BinaryOperator>(Curr)->operands())
803  if (Instruction *OPI = dyn_cast<Instruction>(Op))
804  if (SimpleValue::canHandle(OPI) && Visited.insert(OPI).second)
805  WorkList.push_back(OPI);
806  }
807 
808  return MadeChanges;
809 }
810 
811 bool EarlyCSE::processNode(DomTreeNode *Node) {
812  bool Changed = false;
813  BasicBlock *BB = Node->getBlock();
814 
815  // If this block has a single predecessor, then the predecessor is the parent
816  // of the domtree node and all of the live out memory values are still current
817  // in this block. If this block has multiple predecessors, then they could
818  // have invalidated the live-out memory values of our parent value. For now,
819  // just be conservative and invalidate memory if this block has multiple
820  // predecessors.
821  if (!BB->getSinglePredecessor())
822  ++CurrentGeneration;
823 
824  // If this node has a single predecessor which ends in a conditional branch,
825  // we can infer the value of the branch condition given that we took this
826  // path. We need the single predecessor to ensure there's not another path
827  // which reaches this block where the condition might hold a different
828  // value. Since we're adding this to the scoped hash table (like any other
829  // def), it will have been popped if we encounter a future merge block.
830  if (BasicBlock *Pred = BB->getSinglePredecessor()) {
831  auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());
832  if (BI && BI->isConditional()) {
833  auto *CondInst = dyn_cast<Instruction>(BI->getCondition());
834  if (CondInst && SimpleValue::canHandle(CondInst))
835  Changed |= handleBranchCondition(CondInst, BI, BB, Pred);
836  }
837  }
838 
839  /// LastStore - Keep track of the last non-volatile store that we saw... for
840  /// as long as there in no instruction that reads memory. If we see a store
841  /// to the same location, we delete the dead store. This zaps trivial dead
842  /// stores which can occur in bitfield code among other things.
843  Instruction *LastStore = nullptr;
844 
845  // See if any instructions in the block can be eliminated. If so, do it. If
846  // not, add them to AvailableValues.
847  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
848  Instruction *Inst = &*I++;
849 
850  // Dead instructions should just be removed.
851  if (isInstructionTriviallyDead(Inst, &TLI)) {
852  LLVM_DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
853  if (!DebugCounter::shouldExecute(CSECounter)) {
854  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
855  continue;
856  }
857  if (!salvageDebugInfo(*Inst))
859  removeMSSA(Inst);
860  Inst->eraseFromParent();
861  Changed = true;
862  ++NumSimplify;
863  continue;
864  }
865 
866  // Skip assume intrinsics, they don't really have side effects (although
867  // they're marked as such to ensure preservation of control dependencies),
868  // and this pass will not bother with its removal. However, we should mark
869  // its condition as true for all dominated blocks.
870  if (match(Inst, m_Intrinsic<Intrinsic::assume>())) {
871  auto *CondI =
872  dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0));
873  if (CondI && SimpleValue::canHandle(CondI)) {
874  LLVM_DEBUG(dbgs() << "EarlyCSE considering assumption: " << *Inst
875  << '\n');
876  AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
877  } else
878  LLVM_DEBUG(dbgs() << "EarlyCSE skipping assumption: " << *Inst << '\n');
879  continue;
880  }
881 
882  // Skip sideeffect intrinsics, for the same reason as assume intrinsics.
883  if (match(Inst, m_Intrinsic<Intrinsic::sideeffect>())) {
884  LLVM_DEBUG(dbgs() << "EarlyCSE skipping sideeffect: " << *Inst << '\n');
885  continue;
886  }
887 
888  // We can skip all invariant.start intrinsics since they only read memory,
889  // and we can forward values across it. For invariant starts without
890  // invariant ends, we can use the fact that the invariantness never ends to
891  // start a scope in the current generaton which is true for all future
892  // generations. Also, we dont need to consume the last store since the
893  // semantics of invariant.start allow us to perform DSE of the last
894  // store, if there was a store following invariant.start. Consider:
895  //
896  // store 30, i8* p
897  // invariant.start(p)
898  // store 40, i8* p
899  // We can DSE the store to 30, since the store 40 to invariant location p
900  // causes undefined behaviour.
901  if (match(Inst, m_Intrinsic<Intrinsic::invariant_start>())) {
902  // If there are any uses, the scope might end.
903  if (!Inst->use_empty())
904  continue;
905  auto *CI = cast<CallInst>(Inst);
906  MemoryLocation MemLoc = MemoryLocation::getForArgument(CI, 1, TLI);
907  // Don't start a scope if we already have a better one pushed
908  if (!AvailableInvariants.count(MemLoc))
909  AvailableInvariants.insert(MemLoc, CurrentGeneration);
910  continue;
911  }
912 
913  if (isGuard(Inst)) {
914  if (auto *CondI =
915  dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
916  if (SimpleValue::canHandle(CondI)) {
917  // Do we already know the actual value of this condition?
918  if (auto *KnownCond = AvailableValues.lookup(CondI)) {
919  // Is the condition known to be true?
920  if (isa<ConstantInt>(KnownCond) &&
921  cast<ConstantInt>(KnownCond)->isOne()) {
922  LLVM_DEBUG(dbgs()
923  << "EarlyCSE removing guard: " << *Inst << '\n');
924  removeMSSA(Inst);
925  Inst->eraseFromParent();
926  Changed = true;
927  continue;
928  } else
929  // Use the known value if it wasn't true.
930  cast<CallInst>(Inst)->setArgOperand(0, KnownCond);
931  }
932  // The condition we're on guarding here is true for all dominated
933  // locations.
934  AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
935  }
936  }
937 
938  // Guard intrinsics read all memory, but don't write any memory.
939  // Accordingly, don't update the generation but consume the last store (to
940  // avoid an incorrect DSE).
941  LastStore = nullptr;
942  continue;
943  }
944 
945  // If the instruction can be simplified (e.g. X+0 = X) then replace it with
946  // its simpler value.
947  if (Value *V = SimplifyInstruction(Inst, SQ)) {
948  LLVM_DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << " to: " << *V
949  << '\n');
950  if (!DebugCounter::shouldExecute(CSECounter)) {
951  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
952  } else {
953  bool Killed = false;
954  if (!Inst->use_empty()) {
955  Inst->replaceAllUsesWith(V);
956  Changed = true;
957  }
958  if (isInstructionTriviallyDead(Inst, &TLI)) {
959  removeMSSA(Inst);
960  Inst->eraseFromParent();
961  Changed = true;
962  Killed = true;
963  }
964  if (Changed)
965  ++NumSimplify;
966  if (Killed)
967  continue;
968  }
969  }
970 
971  // If this is a simple instruction that we can value number, process it.
972  if (SimpleValue::canHandle(Inst)) {
973  // See if the instruction has an available value. If so, use it.
974  if (Value *V = AvailableValues.lookup(Inst)) {
975  LLVM_DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << " to: " << *V
976  << '\n');
977  if (!DebugCounter::shouldExecute(CSECounter)) {
978  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
979  continue;
980  }
981  if (auto *I = dyn_cast<Instruction>(V))
982  I->andIRFlags(Inst);
983  Inst->replaceAllUsesWith(V);
984  removeMSSA(Inst);
985  Inst->eraseFromParent();
986  Changed = true;
987  ++NumCSE;
988  continue;
989  }
990 
991  // Otherwise, just remember that this value is available.
992  AvailableValues.insert(Inst, Inst);
993  continue;
994  }
995 
996  ParseMemoryInst MemInst(Inst, TTI);
997  // If this is a non-volatile load, process it.
998  if (MemInst.isValid() && MemInst.isLoad()) {
999  // (conservatively) we can't peak past the ordering implied by this
1000  // operation, but we can add this load to our set of available values
1001  if (MemInst.isVolatile() || !MemInst.isUnordered()) {
1002  LastStore = nullptr;
1003  ++CurrentGeneration;
1004  }
1005 
1006  if (MemInst.isInvariantLoad()) {
1007  // If we pass an invariant load, we know that memory location is
1008  // indefinitely constant from the moment of first dereferenceability.
1009  // We conservatively treat the invariant_load as that moment. If we
1010  // pass a invariant load after already establishing a scope, don't
1011  // restart it since we want to preserve the earliest point seen.
1012  auto MemLoc = MemoryLocation::get(Inst);
1013  if (!AvailableInvariants.count(MemLoc))
1014  AvailableInvariants.insert(MemLoc, CurrentGeneration);
1015  }
1016 
1017  // If we have an available version of this load, and if it is the right
1018  // generation or the load is known to be from an invariant location,
1019  // replace this instruction.
1020  //
1021  // If either the dominating load or the current load are invariant, then
1022  // we can assume the current load loads the same value as the dominating
1023  // load.
1024  LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1025  if (InVal.DefInst != nullptr &&
1026  InVal.MatchingId == MemInst.getMatchingId() &&
1027  // We don't yet handle removing loads with ordering of any kind.
1028  !MemInst.isVolatile() && MemInst.isUnordered() &&
1029  // We can't replace an atomic load with one which isn't also atomic.
1030  InVal.IsAtomic >= MemInst.isAtomic() &&
1031  (isOperatingOnInvariantMemAt(Inst, InVal.Generation) ||
1032  isSameMemGeneration(InVal.Generation, CurrentGeneration,
1033  InVal.DefInst, Inst))) {
1034  Value *Op = getOrCreateResult(InVal.DefInst, Inst->getType());
1035  if (Op != nullptr) {
1036  LLVM_DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
1037  << " to: " << *InVal.DefInst << '\n');
1038  if (!DebugCounter::shouldExecute(CSECounter)) {
1039  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1040  continue;
1041  }
1042  if (!Inst->use_empty())
1043  Inst->replaceAllUsesWith(Op);
1044  removeMSSA(Inst);
1045  Inst->eraseFromParent();
1046  Changed = true;
1047  ++NumCSELoad;
1048  continue;
1049  }
1050  }
1051 
1052  // Otherwise, remember that we have this instruction.
1053  AvailableLoads.insert(
1054  MemInst.getPointerOperand(),
1055  LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
1056  MemInst.isAtomic()));
1057  LastStore = nullptr;
1058  continue;
1059  }
1060 
1061  // If this instruction may read from memory or throw (and potentially read
1062  // from memory in the exception handler), forget LastStore. Load/store
1063  // intrinsics will indicate both a read and a write to memory. The target
1064  // may override this (e.g. so that a store intrinsic does not read from
1065  // memory, and thus will be treated the same as a regular store for
1066  // commoning purposes).
1067  if ((Inst->mayReadFromMemory() || Inst->mayThrow()) &&
1068  !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
1069  LastStore = nullptr;
1070 
1071  // If this is a read-only call, process it.
1072  if (CallValue::canHandle(Inst)) {
1073  // If we have an available version of this call, and if it is the right
1074  // generation, replace this instruction.
1075  std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(Inst);
1076  if (InVal.first != nullptr &&
1077  isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
1078  Inst)) {
1079  LLVM_DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst
1080  << " to: " << *InVal.first << '\n');
1081  if (!DebugCounter::shouldExecute(CSECounter)) {
1082  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1083  continue;
1084  }
1085  if (!Inst->use_empty())
1086  Inst->replaceAllUsesWith(InVal.first);
1087  removeMSSA(Inst);
1088  Inst->eraseFromParent();
1089  Changed = true;
1090  ++NumCSECall;
1091  continue;
1092  }
1093 
1094  // Otherwise, remember that we have this instruction.
1095  AvailableCalls.insert(
1096  Inst, std::pair<Instruction *, unsigned>(Inst, CurrentGeneration));
1097  continue;
1098  }
1099 
1100  // A release fence requires that all stores complete before it, but does
1101  // not prevent the reordering of following loads 'before' the fence. As a
1102  // result, we don't need to consider it as writing to memory and don't need
1103  // to advance the generation. We do need to prevent DSE across the fence,
1104  // but that's handled above.
1105  if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
1106  if (FI->getOrdering() == AtomicOrdering::Release) {
1107  assert(Inst->mayReadFromMemory() && "relied on to prevent DSE above");
1108  continue;
1109  }
1110 
1111  // write back DSE - If we write back the same value we just loaded from
1112  // the same location and haven't passed any intervening writes or ordering
1113  // operations, we can remove the write. The primary benefit is in allowing
1114  // the available load table to remain valid and value forward past where
1115  // the store originally was.
1116  if (MemInst.isValid() && MemInst.isStore()) {
1117  LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1118  if (InVal.DefInst &&
1119  InVal.DefInst == getOrCreateResult(Inst, InVal.DefInst->getType()) &&
1120  InVal.MatchingId == MemInst.getMatchingId() &&
1121  // We don't yet handle removing stores with ordering of any kind.
1122  !MemInst.isVolatile() && MemInst.isUnordered() &&
1123  (isOperatingOnInvariantMemAt(Inst, InVal.Generation) ||
1124  isSameMemGeneration(InVal.Generation, CurrentGeneration,
1125  InVal.DefInst, Inst))) {
1126  // It is okay to have a LastStore to a different pointer here if MemorySSA
1127  // tells us that the load and store are from the same memory generation.
1128  // In that case, LastStore should keep its present value since we're
1129  // removing the current store.
1130  assert((!LastStore ||
1131  ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
1132  MemInst.getPointerOperand() ||
1133  MSSA) &&
1134  "can't have an intervening store if not using MemorySSA!");
1135  LLVM_DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << *Inst << '\n');
1136  if (!DebugCounter::shouldExecute(CSECounter)) {
1137  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1138  continue;
1139  }
1140  removeMSSA(Inst);
1141  Inst->eraseFromParent();
1142  Changed = true;
1143  ++NumDSE;
1144  // We can avoid incrementing the generation count since we were able
1145  // to eliminate this store.
1146  continue;
1147  }
1148  }
1149 
1150  // Okay, this isn't something we can CSE at all. Check to see if it is
1151  // something that could modify memory. If so, our available memory values
1152  // cannot be used so bump the generation count.
1153  if (Inst->mayWriteToMemory()) {
1154  ++CurrentGeneration;
1155 
1156  if (MemInst.isValid() && MemInst.isStore()) {
1157  // We do a trivial form of DSE if there are two stores to the same
1158  // location with no intervening loads. Delete the earlier store.
1159  // At the moment, we don't remove ordered stores, but do remove
1160  // unordered atomic stores. There's no special requirement (for
1161  // unordered atomics) about removing atomic stores only in favor of
1162  // other atomic stores since we were going to execute the non-atomic
1163  // one anyway and the atomic one might never have become visible.
1164  if (LastStore) {
1165  ParseMemoryInst LastStoreMemInst(LastStore, TTI);
1166  assert(LastStoreMemInst.isUnordered() &&
1167  !LastStoreMemInst.isVolatile() &&
1168  "Violated invariant");
1169  if (LastStoreMemInst.isMatchingMemLoc(MemInst)) {
1170  LLVM_DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
1171  << " due to: " << *Inst << '\n');
1172  if (!DebugCounter::shouldExecute(CSECounter)) {
1173  LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1174  } else {
1175  removeMSSA(LastStore);
1176  LastStore->eraseFromParent();
1177  Changed = true;
1178  ++NumDSE;
1179  LastStore = nullptr;
1180  }
1181  }
1182  // fallthrough - we can exploit information about this store
1183  }
1184 
1185  // Okay, we just invalidated anything we knew about loaded values. Try
1186  // to salvage *something* by remembering that the stored value is a live
1187  // version of the pointer. It is safe to forward from volatile stores
1188  // to non-volatile loads, so we don't have to check for volatility of
1189  // the store.
1190  AvailableLoads.insert(
1191  MemInst.getPointerOperand(),
1192  LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
1193  MemInst.isAtomic()));
1194 
1195  // Remember that this was the last unordered store we saw for DSE. We
1196  // don't yet handle DSE on ordered or volatile stores since we don't
1197  // have a good way to model the ordering requirement for following
1198  // passes once the store is removed. We could insert a fence, but
1199  // since fences are slightly stronger than stores in their ordering,
1200  // it's not clear this is a profitable transform. Another option would
1201  // be to merge the ordering with that of the post dominating store.
1202  if (MemInst.isUnordered() && !MemInst.isVolatile())
1203  LastStore = Inst;
1204  else
1205  LastStore = nullptr;
1206  }
1207  }
1208  }
1209 
1210  return Changed;
1211 }
1212 
1213 bool EarlyCSE::run() {
1214  // Note, deque is being used here because there is significant performance
1215  // gains over vector when the container becomes very large due to the
1216  // specific access patterns. For more information see the mailing list
1217  // discussion on this:
1218  // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
1219  std::deque<StackNode *> nodesToProcess;
1220 
1221  bool Changed = false;
1222 
1223  // Process the root node.
1224  nodesToProcess.push_back(new StackNode(
1225  AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1226  CurrentGeneration, DT.getRootNode(),
1227  DT.getRootNode()->begin(), DT.getRootNode()->end()));
1228 
1229  assert(!CurrentGeneration && "Create a new EarlyCSE instance to rerun it.");
1230 
1231  // Process the stack.
1232  while (!nodesToProcess.empty()) {
1233  // Grab the first item off the stack. Set the current generation, remove
1234  // the node from the stack, and process it.
1235  StackNode *NodeToProcess = nodesToProcess.back();
1236 
1237  // Initialize class members.
1238  CurrentGeneration = NodeToProcess->currentGeneration();
1239 
1240  // Check if the node needs to be processed.
1241  if (!NodeToProcess->isProcessed()) {
1242  // Process the node.
1243  Changed |= processNode(NodeToProcess->node());
1244  NodeToProcess->childGeneration(CurrentGeneration);
1245  NodeToProcess->process();
1246  } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
1247  // Push the next child onto the stack.
1248  DomTreeNode *child = NodeToProcess->nextChild();
1249  nodesToProcess.push_back(
1250  new StackNode(AvailableValues, AvailableLoads, AvailableInvariants,
1251  AvailableCalls, NodeToProcess->childGeneration(),
1252  child, child->begin(), child->end()));
1253  } else {
1254  // It has been processed, and there are no more children to process,
1255  // so delete it and pop it off the stack.
1256  delete NodeToProcess;
1257  nodesToProcess.pop_back();
1258  }
1259  } // while (!nodes...)
1260 
1261  return Changed;
1262 }
1263 
1266  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1267  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1268  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1269  auto &AC = AM.getResult<AssumptionAnalysis>(F);
1270  auto *MSSA =
1271  UseMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA() : nullptr;
1272 
1273  EarlyCSE CSE(F.getParent()->getDataLayout(), TLI, TTI, DT, AC, MSSA);
1274 
1275  if (!CSE.run())
1276  return PreservedAnalyses::all();
1277 
1278  PreservedAnalyses PA;
1279  PA.preserveSet<CFGAnalyses>();
1280  PA.preserve<GlobalsAA>();
1281  if (UseMemorySSA)
1283  return PA;
1284 }
1285 
1286 namespace {
1287 
1288 /// A simple and fast domtree-based CSE pass.
1289 ///
1290 /// This pass does a simple depth-first walk over the dominator tree,
1291 /// eliminating trivially redundant instructions and using instsimplify to
1292 /// canonicalize things as it goes. It is intended to be fast and catch obvious
1293 /// cases so that instcombine and other passes are more effective. It is
1294 /// expected that a later pass of GVN will catch the interesting/hard cases.
1295 template<bool UseMemorySSA>
1296 class EarlyCSELegacyCommonPass : public FunctionPass {
1297 public:
1298  static char ID;
1299 
1300  EarlyCSELegacyCommonPass() : FunctionPass(ID) {
1301  if (UseMemorySSA)
1303  else
1305  }
1306 
1307  bool runOnFunction(Function &F) override {
1308  if (skipFunction(F))
1309  return false;
1310 
1311  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1312  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1313  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1314  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1315  auto *MSSA =
1316  UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() : nullptr;
1317 
1318  EarlyCSE CSE(F.getParent()->getDataLayout(), TLI, TTI, DT, AC, MSSA);
1319 
1320  return CSE.run();
1321  }
1322 
1323  void getAnalysisUsage(AnalysisUsage &AU) const override {
1328  if (UseMemorySSA) {
1331  }
1333  AU.setPreservesCFG();
1334  }
1335 };
1336 
1337 } // end anonymous namespace
1338 
1339 using EarlyCSELegacyPass = EarlyCSELegacyCommonPass</*UseMemorySSA=*/false>;
1340 
1341 template<>
1342 char EarlyCSELegacyPass::ID = 0;
1343 
1344 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
1345  false)
1350 INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)
1351 
1352 using EarlyCSEMemSSALegacyPass =
1353  EarlyCSELegacyCommonPass</*UseMemorySSA=*/true>;
1354 
1355 template<>
1356 char EarlyCSEMemSSALegacyPass::ID = 0;
1357 
1358 FunctionPass *llvm::createEarlyCSEPass(bool UseMemorySSA) {
1359  if (UseMemorySSA)
1360  return new EarlyCSEMemSSALegacyPass();
1361  else
1362  return new EarlyCSELegacyPass();
1363 }
1364 
1365 INITIALIZE_PASS_BEGIN(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1366  "Early CSE w/ MemorySSA", false, false)
1372 INITIALIZE_PASS_END(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1373  "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:110
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:594
static SimpleValue getTombstoneKey()
Definition: EarlyCSE.cpp:123
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:699
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:78
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...
Value * getPointerOperand(Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
Unsigned minimum.
Atomic ordering constants.
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:82
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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.
An instruction for ordering other memory operations.
Definition: Instructions.h:454
static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond, Value *&T, Value *&F)
Match a &#39;select&#39; including an optional &#39;not&#39; of the condition.
Definition: EarlyCSE.cpp:134
value_op_iterator value_op_begin()
Definition: User.h:255
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 @llvm.assume calls within a function.
Analysis pass providing the TargetTransformInfo.
bool salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1624
static CallValue getTombstoneKey()
Definition: EarlyCSE.cpp:352
bool replaceDbgUsesWithUndef(Instruction *I)
Replace all the uses of an SSA value in .dbg intrinsics with undef.
Definition: Local.cpp:483
value_op_iterator value_op_end()
Definition: User.h:258
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
block Block Frequency true
An instruction for reading from memory.
Definition: Instructions.h:167
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
This defines the Use class.
static Optional< MemoryLocation > getOrNone(const Instruction *Inst)
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:2461
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: EarlyCSE.cpp:1264
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
Signed maximum.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
bool isIdenticalTo(const Instruction *I) const
Return true if the specified instruction is exactly identical to the current one. ...
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:963
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:808
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
Absolute value.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:416
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:703
static bool isLoad(int Opcode)
static CallValue getEmptyKey()
Definition: EarlyCSE.cpp:348
RecyclingAllocator - This class wraps an Allocator, adding the functionality of recycling deleted obj...
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
This file provides an implementation of debug counters.
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:244
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:1372
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)
static cl::opt< unsigned > EarlyCSEMssaOptCap("earlycse-mssa-optimization-cap", cl::init(500), cl::Hidden, cl::desc("Enable imprecision in EarlyCSE in pathological cases, in exchange " "for faster compile. Caps the MemorySSA clobbering calls."))
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
Value * getLoadStorePointerOperand(Value *V)
A helper function that returns the pointer operand of a load or store instruction.
An instruction for storing to memory.
Definition: Instructions.h:320
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
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:144
Value * getOperand(unsigned i) const
Definition: User.h:169
Analysis containing CSE Info
Definition: CSEInfo.cpp:20
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:140
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:434
NodeT * getBlock() const
static bool runOnFunction(Function &F, bool PostInlining)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
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:233
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:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
Conditional or Unconditional Branch instruction.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static SimpleValue getEmptyKey()
Definition: EarlyCSE.cpp:119
This file contains the declarations for the subclasses of Constant, which represent the different fla...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
bool mayThrow() const
Return true if this instruction may throw an exception.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:501
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:709
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:73
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
Floating point maxnum.
Representation for a specific memory location.
A function analysis which provides an AssumptionCache.
Iterator for intrusive lists based on ilist_node.
SelectPatternFlavor Flavor
void verifyMemorySSA() const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1848
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
iterator end()
Definition: BasicBlock.h:270
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
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:924
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
bool isConditional() const
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:587
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental.guard intrinsic.
Definition: GuardUtils.cpp:17
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:940
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:600
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:478
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:784
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
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:214
Value * getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst, Type *ExpectedType) const
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1534
#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:332
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
DEBUG_COUNTER(CSECounter, "early-cse", "Controls which instructions are removed")
Signed minimum.
EarlyCSELegacyCommonPass< false > EarlyCSELegacyPass
Definition: EarlyCSE.cpp:1339
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE)
bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) const
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
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:353
LLVM Value Representation.
Definition: Value.h:72
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
typename std::vector< DomTreeNodeBase *>::iterator iterator
void initializeEarlyCSEMemSSALegacyPassPass(PassRegistry &)
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:1358
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
This pass exposes codegen information to IR-level passes.
static bool isVolatile(Instruction *Inst)
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
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:322
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a &#39;Not&#39; as &#39;xor V, -1&#39; or &#39;xor -1, V&#39;.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
This instruction inserts a struct field of array element value into an aggregate value.