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