LLVM  15.0.0git
GVN.cpp
Go to the documentation of this file.
1 //===- GVN.cpp - Eliminate redundant values and loads ---------------------===//
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 global value numbering to eliminate fully redundant
10 // instructions. It also performs simple dead load elimination.
11 //
12 // Note that this pass does the value numbering itself; it does not use the
13 // ValueNumbering analysis passes.
14 //
15 //===----------------------------------------------------------------------===//
16 
18 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/Hashing.h"
21 #include "llvm/ADT/MapVector.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include "llvm/ADT/SetVector.h"
25 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/ADT/Statistic.h"
31 #include "llvm/Analysis/CFG.h"
36 #include "llvm/Analysis/LoopInfo.h"
45 #include "llvm/IR/Attributes.h"
46 #include "llvm/IR/BasicBlock.h"
47 #include "llvm/IR/Constant.h"
48 #include "llvm/IR/Constants.h"
49 #include "llvm/IR/DebugLoc.h"
50 #include "llvm/IR/Dominators.h"
51 #include "llvm/IR/Function.h"
52 #include "llvm/IR/InstrTypes.h"
53 #include "llvm/IR/Instruction.h"
54 #include "llvm/IR/Instructions.h"
55 #include "llvm/IR/IntrinsicInst.h"
56 #include "llvm/IR/LLVMContext.h"
57 #include "llvm/IR/Metadata.h"
58 #include "llvm/IR/Module.h"
59 #include "llvm/IR/PassManager.h"
60 #include "llvm/IR/PatternMatch.h"
61 #include "llvm/IR/Type.h"
62 #include "llvm/IR/Use.h"
63 #include "llvm/IR/Value.h"
64 #include "llvm/InitializePasses.h"
65 #include "llvm/Pass.h"
66 #include "llvm/Support/Casting.h"
68 #include "llvm/Support/Compiler.h"
69 #include "llvm/Support/Debug.h"
76 #include <algorithm>
77 #include <cassert>
78 #include <cstdint>
79 #include <utility>
80 
81 using namespace llvm;
82 using namespace llvm::gvn;
83 using namespace llvm::VNCoercion;
84 using namespace PatternMatch;
85 
86 #define DEBUG_TYPE "gvn"
87 
88 STATISTIC(NumGVNInstr, "Number of instructions deleted");
89 STATISTIC(NumGVNLoad, "Number of loads deleted");
90 STATISTIC(NumGVNPRE, "Number of instructions PRE'd");
91 STATISTIC(NumGVNBlocks, "Number of blocks merged");
92 STATISTIC(NumGVNSimpl, "Number of instructions simplified");
93 STATISTIC(NumGVNEqProp, "Number of equalities propagated");
94 STATISTIC(NumPRELoad, "Number of loads PRE'd");
95 STATISTIC(NumPRELoopLoad, "Number of loop loads PRE'd");
96 
97 STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax,
98  "Number of blocks speculated as available in "
99  "IsValueFullyAvailableInBlock(), max");
100 STATISTIC(MaxBBSpeculationCutoffReachedTimes,
101  "Number of times we we reached gvn-max-block-speculations cut-off "
102  "preventing further exploration");
103 
104 static cl::opt<bool> GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden);
105 static cl::opt<bool> GVNEnableLoadPRE("enable-load-pre", cl::init(true));
106 static cl::opt<bool> GVNEnableLoadInLoopPRE("enable-load-in-loop-pre",
107  cl::init(true));
108 static cl::opt<bool>
109 GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre",
110  cl::init(false));
111 static cl::opt<bool> GVNEnableMemDep("enable-gvn-memdep", cl::init(true));
112 
114  "gvn-max-num-deps", cl::Hidden, cl::init(100),
115  cl::desc("Max number of dependences to attempt Load PRE (default = 100)"));
116 
117 // This is based on IsValueFullyAvailableInBlockNumSpeculationsMax stat.
119  "gvn-max-block-speculations", cl::Hidden, cl::init(600),
120  cl::desc("Max number of blocks we're willing to speculate on (and recurse "
121  "into) when deducing if a value is fully available or not in GVN "
122  "(default = 600)"));
123 
126  bool commutative = false;
127  // The type is not necessarily the result type of the expression, it may be
128  // any additional type needed to disambiguate the expression.
129  Type *type = nullptr;
131 
132  Expression(uint32_t o = ~2U) : opcode(o) {}
133 
134  bool operator==(const Expression &other) const {
135  if (opcode != other.opcode)
136  return false;
137  if (opcode == ~0U || opcode == ~1U)
138  return true;
139  if (type != other.type)
140  return false;
141  if (varargs != other.varargs)
142  return false;
143  return true;
144  }
145 
147  return hash_combine(
148  Value.opcode, Value.type,
149  hash_combine_range(Value.varargs.begin(), Value.varargs.end()));
150  }
151 };
152 
153 namespace llvm {
154 
155 template <> struct DenseMapInfo<GVNPass::Expression> {
156  static inline GVNPass::Expression getEmptyKey() { return ~0U; }
157  static inline GVNPass::Expression getTombstoneKey() { return ~1U; }
158 
159  static unsigned getHashValue(const GVNPass::Expression &e) {
160  using llvm::hash_value;
161 
162  return static_cast<unsigned>(hash_value(e));
163  }
164 
165  static bool isEqual(const GVNPass::Expression &LHS,
166  const GVNPass::Expression &RHS) {
167  return LHS == RHS;
168  }
169 };
170 
171 } // end namespace llvm
172 
173 /// Represents a particular available value that we know how to materialize.
174 /// Materialization of an AvailableValue never fails. An AvailableValue is
175 /// implicitly associated with a rematerialization point which is the
176 /// location of the instruction from which it was formed.
178  enum class ValType {
179  SimpleVal, // A simple offsetted value that is accessed.
180  LoadVal, // A value produced by a load.
181  MemIntrin, // A memory intrinsic which is loaded from.
182  UndefVal, // A UndefValue representing a value from dead block (which
183  // is not yet physically removed from the CFG).
184  SelectVal, // A pointer select which is loaded from and for which the load
185  // can be replace by a value select.
186  };
187 
188  /// Val - The value that is live out of the block.
190  /// Kind of the live-out value.
192 
193  /// Offset - The byte offset in Val that is interesting for the load query.
194  unsigned Offset = 0;
195 
196  static AvailableValue get(Value *V, unsigned Offset = 0) {
197  AvailableValue Res;
198  Res.Val = V;
199  Res.Kind = ValType::SimpleVal;
200  Res.Offset = Offset;
201  return Res;
202  }
203 
204  static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset = 0) {
205  AvailableValue Res;
206  Res.Val = MI;
207  Res.Kind = ValType::MemIntrin;
208  Res.Offset = Offset;
209  return Res;
210  }
211 
212  static AvailableValue getLoad(LoadInst *Load, unsigned Offset = 0) {
213  AvailableValue Res;
214  Res.Val = Load;
215  Res.Kind = ValType::LoadVal;
216  Res.Offset = Offset;
217  return Res;
218  }
219 
221  AvailableValue Res;
222  Res.Val = nullptr;
223  Res.Kind = ValType::UndefVal;
224  Res.Offset = 0;
225  return Res;
226  }
227 
229  AvailableValue Res;
230  Res.Val = Sel;
231  Res.Kind = ValType::SelectVal;
232  Res.Offset = 0;
233  return Res;
234  }
235 
236  bool isSimpleValue() const { return Kind == ValType::SimpleVal; }
237  bool isCoercedLoadValue() const { return Kind == ValType::LoadVal; }
238  bool isMemIntrinValue() const { return Kind == ValType::MemIntrin; }
239  bool isUndefValue() const { return Kind == ValType::UndefVal; }
240  bool isSelectValue() const { return Kind == ValType::SelectVal; }
241 
243  assert(isSimpleValue() && "Wrong accessor");
244  return Val;
245  }
246 
248  assert(isCoercedLoadValue() && "Wrong accessor");
249  return cast<LoadInst>(Val);
250  }
251 
253  assert(isMemIntrinValue() && "Wrong accessor");
254  return cast<MemIntrinsic>(Val);
255  }
256 
258  assert(isSelectValue() && "Wrong accessor");
259  return cast<SelectInst>(Val);
260  }
261 
262  /// Emit code at the specified insertion point to adjust the value defined
263  /// here to the specified type. This handles various coercion cases.
264  Value *MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt,
265  GVNPass &gvn) const;
266 };
267 
268 /// Represents an AvailableValue which can be rematerialized at the end of
269 /// the associated BasicBlock.
271  /// BB - The basic block in question.
272  BasicBlock *BB = nullptr;
273 
274  /// AV - The actual available value
276 
279  Res.BB = BB;
280  Res.AV = std::move(AV);
281  return Res;
282  }
283 
285  unsigned Offset = 0) {
286  return get(BB, AvailableValue::get(V, Offset));
287  }
288 
290  return get(BB, AvailableValue::getUndef());
291  }
292 
294  return get(BB, AvailableValue::getSelect(Sel));
295  }
296 
297  /// Emit code at the end of this block to adjust the value defined here to
298  /// the specified type. This handles various coercion cases.
300  return AV.MaterializeAdjustedValue(Load, BB->getTerminator(), gvn);
301  }
302 };
303 
304 //===----------------------------------------------------------------------===//
305 // ValueTable Internal Functions
306 //===----------------------------------------------------------------------===//
307 
308 GVNPass::Expression GVNPass::ValueTable::createExpr(Instruction *I) {
309  Expression e;
310  e.type = I->getType();
311  e.opcode = I->getOpcode();
312  if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(I)) {
313  // gc.relocate is 'special' call: its second and third operands are
314  // not real values, but indices into statepoint's argument list.
315  // Use the refered to values for purposes of identity.
316  e.varargs.push_back(lookupOrAdd(GCR->getOperand(0)));
317  e.varargs.push_back(lookupOrAdd(GCR->getBasePtr()));
318  e.varargs.push_back(lookupOrAdd(GCR->getDerivedPtr()));
319  } else {
320  for (Use &Op : I->operands())
321  e.varargs.push_back(lookupOrAdd(Op));
322  }
323  if (I->isCommutative()) {
324  // Ensure that commutative instructions that only differ by a permutation
325  // of their operands get the same value number by sorting the operand value
326  // numbers. Since commutative operands are the 1st two operands it is more
327  // efficient to sort by hand rather than using, say, std::sort.
328  assert(I->getNumOperands() >= 2 && "Unsupported commutative instruction!");
329  if (e.varargs[0] > e.varargs[1])
330  std::swap(e.varargs[0], e.varargs[1]);
331  e.commutative = true;
332  }
333 
334  if (auto *C = dyn_cast<CmpInst>(I)) {
335  // Sort the operand value numbers so x<y and y>x get the same value number.
336  CmpInst::Predicate Predicate = C->getPredicate();
337  if (e.varargs[0] > e.varargs[1]) {
338  std::swap(e.varargs[0], e.varargs[1]);
340  }
341  e.opcode = (C->getOpcode() << 8) | Predicate;
342  e.commutative = true;
343  } else if (auto *E = dyn_cast<InsertValueInst>(I)) {
344  e.varargs.append(E->idx_begin(), E->idx_end());
345  } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) {
346  ArrayRef<int> ShuffleMask = SVI->getShuffleMask();
347  e.varargs.append(ShuffleMask.begin(), ShuffleMask.end());
348  }
349 
350  return e;
351 }
352 
353 GVNPass::Expression GVNPass::ValueTable::createCmpExpr(
354  unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) {
355  assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
356  "Not a comparison!");
357  Expression e;
359  e.varargs.push_back(lookupOrAdd(LHS));
360  e.varargs.push_back(lookupOrAdd(RHS));
361 
362  // Sort the operand value numbers so x<y and y>x get the same value number.
363  if (e.varargs[0] > e.varargs[1]) {
364  std::swap(e.varargs[0], e.varargs[1]);
366  }
367  e.opcode = (Opcode << 8) | Predicate;
368  e.commutative = true;
369  return e;
370 }
371 
373 GVNPass::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) {
374  assert(EI && "Not an ExtractValueInst?");
375  Expression e;
376  e.type = EI->getType();
377  e.opcode = 0;
378 
379  WithOverflowInst *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
380  if (WO != nullptr && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {
381  // EI is an extract from one of our with.overflow intrinsics. Synthesize
382  // a semantically equivalent expression instead of an extract value
383  // expression.
384  e.opcode = WO->getBinaryOp();
385  e.varargs.push_back(lookupOrAdd(WO->getLHS()));
386  e.varargs.push_back(lookupOrAdd(WO->getRHS()));
387  return e;
388  }
389 
390  // Not a recognised intrinsic. Fall back to producing an extract value
391  // expression.
392  e.opcode = EI->getOpcode();
393  for (Use &Op : EI->operands())
394  e.varargs.push_back(lookupOrAdd(Op));
395 
396  append_range(e.varargs, EI->indices());
397 
398  return e;
399 }
400 
401 GVNPass::Expression GVNPass::ValueTable::createGEPExpr(GetElementPtrInst *GEP) {
402  Expression E;
403  Type *PtrTy = GEP->getType()->getScalarType();
404  const DataLayout &DL = GEP->getModule()->getDataLayout();
405  unsigned BitWidth = DL.getIndexTypeSizeInBits(PtrTy);
406  MapVector<Value *, APInt> VariableOffsets;
407  APInt ConstantOffset(BitWidth, 0);
408  if (PtrTy->isOpaquePointerTy() &&
409  GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset)) {
410  // For opaque pointers, convert into offset representation, to recognize
411  // equivalent address calculations that use different type encoding.
412  LLVMContext &Context = GEP->getContext();
413  E.opcode = GEP->getOpcode();
414  E.type = nullptr;
415  E.varargs.push_back(lookupOrAdd(GEP->getPointerOperand()));
416  for (const auto &Pair : VariableOffsets) {
417  E.varargs.push_back(lookupOrAdd(Pair.first));
418  E.varargs.push_back(lookupOrAdd(ConstantInt::get(Context, Pair.second)));
419  }
420  if (!ConstantOffset.isZero())
421  E.varargs.push_back(
422  lookupOrAdd(ConstantInt::get(Context, ConstantOffset)));
423  } else {
424  // If converting to offset representation fails (for typed pointers and
425  // scalable vectors), fall back to type-based implementation:
426  E.opcode = GEP->getOpcode();
427  E.type = GEP->getSourceElementType();
428  for (Use &Op : GEP->operands())
429  E.varargs.push_back(lookupOrAdd(Op));
430  }
431  return E;
432 }
433 
434 //===----------------------------------------------------------------------===//
435 // ValueTable External Functions
436 //===----------------------------------------------------------------------===//
437 
444 
445 /// add - Insert a value into the table with a specified value number.
447  valueNumbering.insert(std::make_pair(V, num));
448  if (PHINode *PN = dyn_cast<PHINode>(V))
449  NumberingPhi[num] = PN;
450 }
451 
452 uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) {
453  if (AA->doesNotAccessMemory(C)) {
454  Expression exp = createExpr(C);
455  uint32_t e = assignExpNewValueNum(exp).first;
456  valueNumbering[C] = e;
457  return e;
458  } else if (MD && AA->onlyReadsMemory(C)) {
459  Expression exp = createExpr(C);
460  auto ValNum = assignExpNewValueNum(exp);
461  if (ValNum.second) {
462  valueNumbering[C] = ValNum.first;
463  return ValNum.first;
464  }
465 
466  MemDepResult local_dep = MD->getDependency(C);
467 
468  if (!local_dep.isDef() && !local_dep.isNonLocal()) {
469  valueNumbering[C] = nextValueNumber;
470  return nextValueNumber++;
471  }
472 
473  if (local_dep.isDef()) {
474  // For masked load/store intrinsics, the local_dep may actully be
475  // a normal load or store instruction.
476  CallInst *local_cdep = dyn_cast<CallInst>(local_dep.getInst());
477 
478  if (!local_cdep || local_cdep->arg_size() != C->arg_size()) {
479  valueNumbering[C] = nextValueNumber;
480  return nextValueNumber++;
481  }
482 
483  for (unsigned i = 0, e = C->arg_size(); i < e; ++i) {
484  uint32_t c_vn = lookupOrAdd(C->getArgOperand(i));
485  uint32_t cd_vn = lookupOrAdd(local_cdep->getArgOperand(i));
486  if (c_vn != cd_vn) {
487  valueNumbering[C] = nextValueNumber;
488  return nextValueNumber++;
489  }
490  }
491 
492  uint32_t v = lookupOrAdd(local_cdep);
493  valueNumbering[C] = v;
494  return v;
495  }
496 
497  // Non-local case.
499  MD->getNonLocalCallDependency(C);
500  // FIXME: Move the checking logic to MemDep!
501  CallInst* cdep = nullptr;
502 
503  // Check to see if we have a single dominating call instruction that is
504  // identical to C.
505  for (unsigned i = 0, e = deps.size(); i != e; ++i) {
506  const NonLocalDepEntry *I = &deps[i];
507  if (I->getResult().isNonLocal())
508  continue;
509 
510  // We don't handle non-definitions. If we already have a call, reject
511  // instruction dependencies.
512  if (!I->getResult().isDef() || cdep != nullptr) {
513  cdep = nullptr;
514  break;
515  }
516 
517  CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->getResult().getInst());
518  // FIXME: All duplicated with non-local case.
519  if (NonLocalDepCall && DT->properlyDominates(I->getBB(), C->getParent())){
520  cdep = NonLocalDepCall;
521  continue;
522  }
523 
524  cdep = nullptr;
525  break;
526  }
527 
528  if (!cdep) {
529  valueNumbering[C] = nextValueNumber;
530  return nextValueNumber++;
531  }
532 
533  if (cdep->arg_size() != C->arg_size()) {
534  valueNumbering[C] = nextValueNumber;
535  return nextValueNumber++;
536  }
537  for (unsigned i = 0, e = C->arg_size(); i < e; ++i) {
538  uint32_t c_vn = lookupOrAdd(C->getArgOperand(i));
539  uint32_t cd_vn = lookupOrAdd(cdep->getArgOperand(i));
540  if (c_vn != cd_vn) {
541  valueNumbering[C] = nextValueNumber;
542  return nextValueNumber++;
543  }
544  }
545 
546  uint32_t v = lookupOrAdd(cdep);
547  valueNumbering[C] = v;
548  return v;
549  } else {
550  valueNumbering[C] = nextValueNumber;
551  return nextValueNumber++;
552  }
553 }
554 
555 /// Returns true if a value number exists for the specified value.
557  return valueNumbering.count(V) != 0;
558 }
559 
560 /// lookup_or_add - Returns the value number for the specified value, assigning
561 /// it a new number if it did not have one before.
563  DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
564  if (VI != valueNumbering.end())
565  return VI->second;
566 
567  if (!isa<Instruction>(V)) {
568  valueNumbering[V] = nextValueNumber;
569  return nextValueNumber++;
570  }
571 
572  Instruction* I = cast<Instruction>(V);
573  Expression exp;
574  switch (I->getOpcode()) {
575  case Instruction::Call:
576  return lookupOrAddCall(cast<CallInst>(I));
577  case Instruction::FNeg:
578  case Instruction::Add:
579  case Instruction::FAdd:
580  case Instruction::Sub:
581  case Instruction::FSub:
582  case Instruction::Mul:
583  case Instruction::FMul:
584  case Instruction::UDiv:
585  case Instruction::SDiv:
586  case Instruction::FDiv:
587  case Instruction::URem:
588  case Instruction::SRem:
589  case Instruction::FRem:
590  case Instruction::Shl:
591  case Instruction::LShr:
592  case Instruction::AShr:
593  case Instruction::And:
594  case Instruction::Or:
595  case Instruction::Xor:
596  case Instruction::ICmp:
597  case Instruction::FCmp:
598  case Instruction::Trunc:
599  case Instruction::ZExt:
600  case Instruction::SExt:
601  case Instruction::FPToUI:
602  case Instruction::FPToSI:
603  case Instruction::UIToFP:
604  case Instruction::SIToFP:
605  case Instruction::FPTrunc:
606  case Instruction::FPExt:
607  case Instruction::PtrToInt:
608  case Instruction::IntToPtr:
609  case Instruction::AddrSpaceCast:
610  case Instruction::BitCast:
611  case Instruction::Select:
612  case Instruction::Freeze:
613  case Instruction::ExtractElement:
614  case Instruction::InsertElement:
615  case Instruction::ShuffleVector:
616  case Instruction::InsertValue:
617  exp = createExpr(I);
618  break;
619  case Instruction::GetElementPtr:
620  exp = createGEPExpr(cast<GetElementPtrInst>(I));
621  break;
622  case Instruction::ExtractValue:
623  exp = createExtractvalueExpr(cast<ExtractValueInst>(I));
624  break;
625  case Instruction::PHI:
626  valueNumbering[V] = nextValueNumber;
627  NumberingPhi[nextValueNumber] = cast<PHINode>(V);
628  return nextValueNumber++;
629  default:
630  valueNumbering[V] = nextValueNumber;
631  return nextValueNumber++;
632  }
633 
634  uint32_t e = assignExpNewValueNum(exp).first;
635  valueNumbering[V] = e;
636  return e;
637 }
638 
639 /// Returns the value number of the specified value. Fails if
640 /// the value has not yet been numbered.
642  DenseMap<Value*, uint32_t>::const_iterator VI = valueNumbering.find(V);
643  if (Verify) {
644  assert(VI != valueNumbering.end() && "Value not numbered?");
645  return VI->second;
646  }
647  return (VI != valueNumbering.end()) ? VI->second : 0;
648 }
649 
650 /// Returns the value number of the given comparison,
651 /// assigning it a new number if it did not have one before. Useful when
652 /// we deduced the result of a comparison, but don't immediately have an
653 /// instruction realizing that comparison to hand.
656  Value *LHS, Value *RHS) {
657  Expression exp = createCmpExpr(Opcode, Predicate, LHS, RHS);
658  return assignExpNewValueNum(exp).first;
659 }
660 
661 /// Remove all entries from the ValueTable.
663  valueNumbering.clear();
664  expressionNumbering.clear();
665  NumberingPhi.clear();
666  PhiTranslateTable.clear();
667  nextValueNumber = 1;
668  Expressions.clear();
669  ExprIdx.clear();
670  nextExprNumber = 0;
671 }
672 
673 /// Remove a value from the value numbering.
675  uint32_t Num = valueNumbering.lookup(V);
676  valueNumbering.erase(V);
677  // If V is PHINode, V <--> value number is an one-to-one mapping.
678  if (isa<PHINode>(V))
679  NumberingPhi.erase(Num);
680 }
681 
682 /// verifyRemoved - Verify that the value is removed from all internal data
683 /// structures.
686  I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) {
687  assert(I->first != V && "Inst still occurs in value numbering map!");
688  }
689 }
690 
691 //===----------------------------------------------------------------------===//
692 // GVN Pass
693 //===----------------------------------------------------------------------===//
694 
695 bool GVNPass::isPREEnabled() const {
696  return Options.AllowPRE.value_or(GVNEnablePRE);
697 }
698 
700  return Options.AllowLoadPRE.value_or(GVNEnableLoadPRE);
701 }
702 
704  return Options.AllowLoadInLoopPRE.value_or(GVNEnableLoadInLoopPRE);
705 }
706 
708  return Options.AllowLoadPRESplitBackedge.value_or(
710 }
711 
713  return Options.AllowMemDep.value_or(GVNEnableMemDep);
714 }
715 
717  // FIXME: The order of evaluation of these 'getResult' calls is very
718  // significant! Re-ordering these variables will cause GVN when run alone to
719  // be less effective! We should fix memdep and basic-aa to not exhibit this
720  // behavior, but until then don't change the order here.
721  auto &AC = AM.getResult<AssumptionAnalysis>(F);
722  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
723  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
724  auto &AA = AM.getResult<AAManager>(F);
725  auto *MemDep =
726  isMemDepEnabled() ? &AM.getResult<MemoryDependenceAnalysis>(F) : nullptr;
727  auto *LI = AM.getCachedResult<LoopAnalysis>(F);
728  auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(F);
730  bool Changed = runImpl(F, AC, DT, TLI, AA, MemDep, LI, &ORE,
731  MSSA ? &MSSA->getMSSA() : nullptr);
732  if (!Changed)
733  return PreservedAnalyses::all();
737  if (MSSA)
739  if (LI)
740  PA.preserve<LoopAnalysis>();
741  return PA;
742 }
743 
745  raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
746  static_cast<PassInfoMixin<GVNPass> *>(this)->printPipeline(
747  OS, MapClassName2PassName);
748 
749  OS << "<";
750  if (Options.AllowPRE != None)
751  OS << (Options.AllowPRE.getValue() ? "" : "no-") << "pre;";
752  if (Options.AllowLoadPRE != None)
753  OS << (Options.AllowLoadPRE.getValue() ? "" : "no-") << "load-pre;";
754  if (Options.AllowLoadPRESplitBackedge != None)
755  OS << (Options.AllowLoadPRESplitBackedge.getValue() ? "" : "no-")
756  << "split-backedge-load-pre;";
757  if (Options.AllowMemDep != None)
758  OS << (Options.AllowMemDep.getValue() ? "" : "no-") << "memdep";
759  OS << ">";
760 }
761 
762 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
763 LLVM_DUMP_METHOD void GVNPass::dump(DenseMap<uint32_t, Value *> &d) const {
764  errs() << "{\n";
765  for (auto &I : d) {
766  errs() << I.first << "\n";
767  I.second->dump();
768  }
769  errs() << "}\n";
770 }
771 #endif
772 
773 enum class AvailabilityState : char {
774  /// We know the block *is not* fully available. This is a fixpoint.
775  Unavailable = 0,
776  /// We know the block *is* fully available. This is a fixpoint.
777  Available = 1,
778  /// We do not know whether the block is fully available or not,
779  /// but we are currently speculating that it will be.
780  /// If it would have turned out that the block was, in fact, not fully
781  /// available, this would have been cleaned up into an Unavailable.
783 };
784 
785 /// Return true if we can prove that the value
786 /// we're analyzing is fully available in the specified block. As we go, keep
787 /// track of which blocks we know are fully alive in FullyAvailableBlocks. This
788 /// map is actually a tri-state map with the following values:
789 /// 0) we know the block *is not* fully available.
790 /// 1) we know the block *is* fully available.
791 /// 2) we do not know whether the block is fully available or not, but we are
792 /// currently speculating that it will be.
794  BasicBlock *BB,
795  DenseMap<BasicBlock *, AvailabilityState> &FullyAvailableBlocks) {
797  Optional<BasicBlock *> UnavailableBB;
798 
799  // The number of times we didn't find an entry for a block in a map and
800  // optimistically inserted an entry marking block as speculatively available.
801  unsigned NumNewNewSpeculativelyAvailableBBs = 0;
802 
803 #ifndef NDEBUG
804  SmallSet<BasicBlock *, 32> NewSpeculativelyAvailableBBs;
805  SmallVector<BasicBlock *, 32> AvailableBBs;
806 #endif
807 
808  Worklist.emplace_back(BB);
809  while (!Worklist.empty()) {
810  BasicBlock *CurrBB = Worklist.pop_back_val(); // LoadFO - depth-first!
811  // Optimistically assume that the block is Speculatively Available and check
812  // to see if we already know about this block in one lookup.
813  std::pair<DenseMap<BasicBlock *, AvailabilityState>::iterator, bool> IV =
814  FullyAvailableBlocks.try_emplace(
816  AvailabilityState &State = IV.first->second;
817 
818  // Did the entry already exist for this block?
819  if (!IV.second) {
820  if (State == AvailabilityState::Unavailable) {
821  UnavailableBB = CurrBB;
822  break; // Backpropagate unavailability info.
823  }
824 
825 #ifndef NDEBUG
826  AvailableBBs.emplace_back(CurrBB);
827 #endif
828  continue; // Don't recurse further, but continue processing worklist.
829  }
830 
831  // No entry found for block.
832  ++NumNewNewSpeculativelyAvailableBBs;
833  bool OutOfBudget = NumNewNewSpeculativelyAvailableBBs > MaxBBSpeculations;
834 
835  // If we have exhausted our budget, mark this block as unavailable.
836  // Also, if this block has no predecessors, the value isn't live-in here.
837  if (OutOfBudget || pred_empty(CurrBB)) {
838  MaxBBSpeculationCutoffReachedTimes += (int)OutOfBudget;
840  UnavailableBB = CurrBB;
841  break; // Backpropagate unavailability info.
842  }
843 
844  // Tentatively consider this block as speculatively available.
845 #ifndef NDEBUG
846  NewSpeculativelyAvailableBBs.insert(CurrBB);
847 #endif
848  // And further recurse into block's predecessors, in depth-first order!
849  Worklist.append(pred_begin(CurrBB), pred_end(CurrBB));
850  }
851 
852 #if LLVM_ENABLE_STATS
853  IsValueFullyAvailableInBlockNumSpeculationsMax.updateMax(
854  NumNewNewSpeculativelyAvailableBBs);
855 #endif
856 
857  // If the block isn't marked as fixpoint yet
858  // (the Unavailable and Available states are fixpoints)
859  auto MarkAsFixpointAndEnqueueSuccessors =
860  [&](BasicBlock *BB, AvailabilityState FixpointState) {
861  auto It = FullyAvailableBlocks.find(BB);
862  if (It == FullyAvailableBlocks.end())
863  return; // Never queried this block, leave as-is.
864  switch (AvailabilityState &State = It->second) {
867  return; // Don't backpropagate further, continue processing worklist.
869  State = FixpointState;
870 #ifndef NDEBUG
871  assert(NewSpeculativelyAvailableBBs.erase(BB) &&
872  "Found a speculatively available successor leftover?");
873 #endif
874  // Queue successors for further processing.
875  Worklist.append(succ_begin(BB), succ_end(BB));
876  return;
877  }
878  };
879 
880  if (UnavailableBB) {
881  // Okay, we have encountered an unavailable block.
882  // Mark speculatively available blocks reachable from UnavailableBB as
883  // unavailable as well. Paths are terminated when they reach blocks not in
884  // FullyAvailableBlocks or they are not marked as speculatively available.
885  Worklist.clear();
886  Worklist.append(succ_begin(*UnavailableBB), succ_end(*UnavailableBB));
887  while (!Worklist.empty())
888  MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
890  }
891 
892 #ifndef NDEBUG
893  Worklist.clear();
894  for (BasicBlock *AvailableBB : AvailableBBs)
895  Worklist.append(succ_begin(AvailableBB), succ_end(AvailableBB));
896  while (!Worklist.empty())
897  MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
899 
900  assert(NewSpeculativelyAvailableBBs.empty() &&
901  "Must have fixed all the new speculatively available blocks.");
902 #endif
903 
904  return !UnavailableBB;
905 }
906 
907 /// Given a set of loads specified by ValuesPerBlock,
908 /// construct SSA form, allowing us to eliminate Load. This returns the value
909 /// that should be used at Load's definition site.
910 static Value *
913  GVNPass &gvn) {
914  // Check for the fully redundant, dominating load case. In this case, we can
915  // just use the dominating value directly.
916  if (ValuesPerBlock.size() == 1 &&
917  gvn.getDominatorTree().properlyDominates(ValuesPerBlock[0].BB,
918  Load->getParent())) {
919  assert(!ValuesPerBlock[0].AV.isUndefValue() &&
920  "Dead BB dominate this block");
921  return ValuesPerBlock[0].MaterializeAdjustedValue(Load, gvn);
922  }
923 
924  // Otherwise, we have to construct SSA form.
925  SmallVector<PHINode*, 8> NewPHIs;
926  SSAUpdater SSAUpdate(&NewPHIs);
927  SSAUpdate.Initialize(Load->getType(), Load->getName());
928 
929  for (const AvailableValueInBlock &AV : ValuesPerBlock) {
930  BasicBlock *BB = AV.BB;
931 
932  if (AV.AV.isUndefValue())
933  continue;
934 
935  if (SSAUpdate.HasValueForBlock(BB))
936  continue;
937 
938  // If the value is the load that we will be eliminating, and the block it's
939  // available in is the block that the load is in, then don't add it as
940  // SSAUpdater will resolve the value to the relevant phi which may let it
941  // avoid phi construction entirely if there's actually only one value.
942  if (BB == Load->getParent() &&
943  ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() == Load) ||
944  (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() == Load)))
945  continue;
946 
947  SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(Load, gvn));
948  }
949 
950  // Perform PHI construction.
951  return SSAUpdate.GetValueInMiddleOfBlock(Load->getParent());
952 }
953 
954 static LoadInst *findDominatingLoad(Value *Ptr, Type *LoadTy, SelectInst *Sel,
955  DominatorTree &DT) {
956  for (Value *U : Ptr->users()) {
957  auto *LI = dyn_cast<LoadInst>(U);
958  if (LI && LI->getType() == LoadTy && LI->getParent() == Sel->getParent() &&
959  DT.dominates(LI, Sel))
960  return LI;
961  }
962  return nullptr;
963 }
964 
966  Instruction *InsertPt,
967  GVNPass &gvn) const {
968  Value *Res;
969  Type *LoadTy = Load->getType();
970  const DataLayout &DL = Load->getModule()->getDataLayout();
971  if (isSimpleValue()) {
972  Res = getSimpleValue();
973  if (Res->getType() != LoadTy) {
974  Res = getStoreValueForLoad(Res, Offset, LoadTy, InsertPt, DL);
975 
976  LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset
977  << " " << *getSimpleValue() << '\n'
978  << *Res << '\n'
979  << "\n\n\n");
980  }
981  } else if (isCoercedLoadValue()) {
982  LoadInst *CoercedLoad = getCoercedLoadValue();
983  if (CoercedLoad->getType() == LoadTy && Offset == 0) {
984  Res = CoercedLoad;
985  } else {
986  Res = getLoadValueForLoad(CoercedLoad, Offset, LoadTy, InsertPt, DL);
987  // We would like to use gvn.markInstructionForDeletion here, but we can't
988  // because the load is already memoized into the leader map table that GVN
989  // tracks. It is potentially possible to remove the load from the table,
990  // but then there all of the operations based on it would need to be
991  // rehashed. Just leave the dead load around.
992  gvn.getMemDep().removeInstruction(CoercedLoad);
993  LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset
994  << " " << *getCoercedLoadValue() << '\n'
995  << *Res << '\n'
996  << "\n\n\n");
997  }
998  } else if (isMemIntrinValue()) {
999  Res = getMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy,
1000  InsertPt, DL);
1001  LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
1002  << " " << *getMemIntrinValue() << '\n'
1003  << *Res << '\n'
1004  << "\n\n\n");
1005  } else if (isSelectValue()) {
1006  // Introduce a new value select for a load from an eligible pointer select.
1007  SelectInst *Sel = getSelectValue();
1008  LoadInst *L1 = findDominatingLoad(Sel->getOperand(1), LoadTy, Sel,
1009  gvn.getDominatorTree());
1010  LoadInst *L2 = findDominatingLoad(Sel->getOperand(2), LoadTy, Sel,
1011  gvn.getDominatorTree());
1012  assert(L1 && L2 &&
1013  "must be able to obtain dominating loads for both value operands of "
1014  "the select");
1015  Res = SelectInst::Create(Sel->getCondition(), L1, L2, "", Sel);
1016  } else {
1017  llvm_unreachable("Should not materialize value from dead block");
1018  }
1019  assert(Res && "failed to materialize?");
1020  return Res;
1021 }
1022 
1023 static bool isLifetimeStart(const Instruction *Inst) {
1024  if (const IntrinsicInst* II = dyn_cast<IntrinsicInst>(Inst))
1025  return II->getIntrinsicID() == Intrinsic::lifetime_start;
1026  return false;
1027 }
1028 
1029 /// Assuming To can be reached from both From and Between, does Between lie on
1030 /// every path from From to To?
1031 static bool liesBetween(const Instruction *From, Instruction *Between,
1032  const Instruction *To, DominatorTree *DT) {
1033  if (From->getParent() == Between->getParent())
1034  return DT->dominates(From, Between);
1035  SmallSet<BasicBlock *, 1> Exclusion;
1036  Exclusion.insert(Between->getParent());
1037  return !isPotentiallyReachable(From, To, &Exclusion, DT);
1038 }
1039 
1040 /// Try to locate the three instruction involved in a missed
1041 /// load-elimination case that is due to an intervening store.
1043  DominatorTree *DT,
1045  using namespace ore;
1046 
1047  User *OtherAccess = nullptr;
1048 
1049  OptimizationRemarkMissed R(DEBUG_TYPE, "LoadClobbered", Load);
1050  R << "load of type " << NV("Type", Load->getType()) << " not eliminated"
1051  << setExtraArgs();
1052 
1053  for (auto *U : Load->getPointerOperand()->users()) {
1054  if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U)) &&
1055  cast<Instruction>(U)->getFunction() == Load->getFunction() &&
1056  DT->dominates(cast<Instruction>(U), Load)) {
1057  // Use the most immediately dominating value
1058  if (OtherAccess) {
1059  if (DT->dominates(cast<Instruction>(OtherAccess), cast<Instruction>(U)))
1060  OtherAccess = U;
1061  else
1062  assert(DT->dominates(cast<Instruction>(U),
1063  cast<Instruction>(OtherAccess)));
1064  } else
1065  OtherAccess = U;
1066  }
1067  }
1068 
1069  if (!OtherAccess) {
1070  // There is no dominating use, check if we can find a closest non-dominating
1071  // use that lies between any other potentially available use and Load.
1072  for (auto *U : Load->getPointerOperand()->users()) {
1073  if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U)) &&
1074  cast<Instruction>(U)->getFunction() == Load->getFunction() &&
1075  isPotentiallyReachable(cast<Instruction>(U), Load, nullptr, DT)) {
1076  if (OtherAccess) {
1077  if (liesBetween(cast<Instruction>(OtherAccess), cast<Instruction>(U),
1078  Load, DT)) {
1079  OtherAccess = U;
1080  } else if (!liesBetween(cast<Instruction>(U),
1081  cast<Instruction>(OtherAccess), Load, DT)) {
1082  // These uses are both partially available at Load were it not for
1083  // the clobber, but neither lies strictly after the other.
1084  OtherAccess = nullptr;
1085  break;
1086  } // else: keep current OtherAccess since it lies between U and Load
1087  } else {
1088  OtherAccess = U;
1089  }
1090  }
1091  }
1092  }
1093 
1094  if (OtherAccess)
1095  R << " in favor of " << NV("OtherAccess", OtherAccess);
1096 
1097  R << " because it is clobbered by " << NV("ClobberedBy", DepInfo.getInst());
1098 
1099  ORE->emit(R);
1100 }
1101 
1102 /// Check if a load from pointer-select \p Address in \p DepBB can be converted
1103 /// to a value select. The following conditions need to be satisfied:
1104 /// 1. The pointer select (\p Address) must be defined in \p DepBB.
1105 /// 2. Both value operands of the pointer select must be loaded in the same
1106 /// basic block, before the pointer select.
1107 /// 3. There must be no instructions between the found loads and \p End that may
1108 /// clobber the loads.
1111  Value *Address, Type *LoadTy, DominatorTree &DT,
1112  AAResults *AA) {
1113 
1114  auto *Sel = dyn_cast_or_null<SelectInst>(Address);
1115  if (!Sel || DepBB != Sel->getParent())
1116  return None;
1117 
1118  LoadInst *L1 = findDominatingLoad(Sel->getOperand(1), LoadTy, Sel, DT);
1119  LoadInst *L2 = findDominatingLoad(Sel->getOperand(2), LoadTy, Sel, DT);
1120  if (!L1 || !L2)
1121  return None;
1122 
1123  // Ensure there are no accesses that may modify the locations referenced by
1124  // either L1 or L2 between L1, L2 and the specified End iterator.
1125  Instruction *EarlierLoad = L1->comesBefore(L2) ? L1 : L2;
1126  MemoryLocation L1Loc = MemoryLocation::get(L1);
1128  if (any_of(make_range(EarlierLoad->getIterator(), End), [&](Instruction &I) {
1129  return isModSet(AA->getModRefInfo(&I, L1Loc)) ||
1130  isModSet(AA->getModRefInfo(&I, L2Loc));
1131  }))
1132  return None;
1133 
1134  return AvailableValue::getSelect(Sel);
1135 }
1136 
1137 bool GVNPass::AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
1138  Value *Address, AvailableValue &Res) {
1139  if (!DepInfo.isDef() && !DepInfo.isClobber()) {
1140  assert(isa<SelectInst>(Address));
1141  if (auto R = tryToConvertLoadOfPtrSelect(
1142  Load->getParent(), Load->getIterator(), Address, Load->getType(),
1143  getDominatorTree(), getAliasAnalysis())) {
1144  Res = *R;
1145  return true;
1146  }
1147  return false;
1148  }
1149 
1150  assert((DepInfo.isDef() || DepInfo.isClobber()) &&
1151  "expected a local dependence");
1152  assert(Load->isUnordered() && "rules below are incorrect for ordered access");
1153 
1154  const DataLayout &DL = Load->getModule()->getDataLayout();
1155 
1156  Instruction *DepInst = DepInfo.getInst();
1157  if (DepInfo.isClobber()) {
1158  // If the dependence is to a store that writes to a superset of the bits
1159  // read by the load, we can extract the bits we need for the load from the
1160  // stored value.
1161  if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {
1162  // Can't forward from non-atomic to atomic without violating memory model.
1163  if (Address && Load->isAtomic() <= DepSI->isAtomic()) {
1164  int Offset =
1165  analyzeLoadFromClobberingStore(Load->getType(), Address, DepSI, DL);
1166  if (Offset != -1) {
1167  Res = AvailableValue::get(DepSI->getValueOperand(), Offset);
1168  return true;
1169  }
1170  }
1171  }
1172 
1173  // Check to see if we have something like this:
1174  // load i32* P
1175  // load i8* (P+1)
1176  // if we have this, replace the later with an extraction from the former.
1177  if (LoadInst *DepLoad = dyn_cast<LoadInst>(DepInst)) {
1178  // If this is a clobber and L is the first instruction in its block, then
1179  // we have the first instruction in the entry block.
1180  // Can't forward from non-atomic to atomic without violating memory model.
1181  if (DepLoad != Load && Address &&
1182  Load->isAtomic() <= DepLoad->isAtomic()) {
1183  Type *LoadType = Load->getType();
1184  int Offset = -1;
1185 
1186  // If MD reported clobber, check it was nested.
1187  if (DepInfo.isClobber() &&
1188  canCoerceMustAliasedValueToLoad(DepLoad, LoadType, DL)) {
1189  const auto ClobberOff = MD->getClobberOffset(DepLoad);
1190  // GVN has no deal with a negative offset.
1191  Offset = (ClobberOff == None || *ClobberOff < 0) ? -1 : *ClobberOff;
1192  }
1193  if (Offset == -1)
1194  Offset =
1195  analyzeLoadFromClobberingLoad(LoadType, Address, DepLoad, DL);
1196  if (Offset != -1) {
1197  Res = AvailableValue::getLoad(DepLoad, Offset);
1198  return true;
1199  }
1200  }
1201  }
1202 
1203  // If the clobbering value is a memset/memcpy/memmove, see if we can
1204  // forward a value on from it.
1205  if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1206  if (Address && !Load->isAtomic()) {
1207  int Offset = analyzeLoadFromClobberingMemInst(Load->getType(), Address,
1208  DepMI, DL);
1209  if (Offset != -1) {
1210  Res = AvailableValue::getMI(DepMI, Offset);
1211  return true;
1212  }
1213  }
1214  }
1215 
1216  // Nothing known about this clobber, have to be conservative
1217  LLVM_DEBUG(
1218  // fast print dep, using operator<< on instruction is too slow.
1219  dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
1220  dbgs() << " is clobbered by " << *DepInst << '\n';);
1221  if (ORE->allowExtraAnalysis(DEBUG_TYPE))
1222  reportMayClobberedLoad(Load, DepInfo, DT, ORE);
1223 
1224  return false;
1225  }
1226  assert(DepInfo.isDef() && "follows from above");
1227 
1228  // Loading the alloca -> undef.
1229  // Loading immediately after lifetime begin -> undef.
1230  if (isa<AllocaInst>(DepInst) || isLifetimeStart(DepInst)) {
1231  Res = AvailableValue::get(UndefValue::get(Load->getType()));
1232  return true;
1233  }
1234 
1235  if (Constant *InitVal =
1236  getInitialValueOfAllocation(DepInst, TLI, Load->getType())) {
1237  Res = AvailableValue::get(InitVal);
1238  return true;
1239  }
1240 
1241  if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) {
1242  // Reject loads and stores that are to the same address but are of
1243  // different types if we have to. If the stored value is convertable to
1244  // the loaded value, we can reuse it.
1245  if (!canCoerceMustAliasedValueToLoad(S->getValueOperand(), Load->getType(),
1246  DL))
1247  return false;
1248 
1249  // Can't forward from non-atomic to atomic without violating memory model.
1250  if (S->isAtomic() < Load->isAtomic())
1251  return false;
1252 
1253  Res = AvailableValue::get(S->getValueOperand());
1254  return true;
1255  }
1256 
1257  if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) {
1258  // If the types mismatch and we can't handle it, reject reuse of the load.
1259  // If the stored value is larger or equal to the loaded value, we can reuse
1260  // it.
1261  if (!canCoerceMustAliasedValueToLoad(LD, Load->getType(), DL))
1262  return false;
1263 
1264  // Can't forward from non-atomic to atomic without violating memory model.
1265  if (LD->isAtomic() < Load->isAtomic())
1266  return false;
1267 
1268  Res = AvailableValue::getLoad(LD);
1269  return true;
1270  }
1271 
1272  // Unknown def - must be conservative
1273  LLVM_DEBUG(
1274  // fast print dep, using operator<< on instruction is too slow.
1275  dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
1276  dbgs() << " has unknown def " << *DepInst << '\n';);
1277  return false;
1278 }
1279 
1280 void GVNPass::AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
1281  AvailValInBlkVect &ValuesPerBlock,
1282  UnavailBlkVect &UnavailableBlocks) {
1283  // Filter out useless results (non-locals, etc). Keep track of the blocks
1284  // where we have a value available in repl, also keep track of whether we see
1285  // dependencies that produce an unknown value for the load (such as a call
1286  // that could potentially clobber the load).
1287  unsigned NumDeps = Deps.size();
1288  for (unsigned i = 0, e = NumDeps; i != e; ++i) {
1289  BasicBlock *DepBB = Deps[i].getBB();
1290  MemDepResult DepInfo = Deps[i].getResult();
1291 
1292  if (DeadBlocks.count(DepBB)) {
1293  // Dead dependent mem-op disguise as a load evaluating the same value
1294  // as the load in question.
1295  ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB));
1296  continue;
1297  }
1298 
1299  // The address being loaded in this non-local block may not be the same as
1300  // the pointer operand of the load if PHI translation occurs. Make sure
1301  // to consider the right address.
1302  Value *Address = Deps[i].getAddress();
1303 
1304  if (!DepInfo.isDef() && !DepInfo.isClobber()) {
1305  if (auto R = tryToConvertLoadOfPtrSelect(
1306  DepBB, DepBB->end(), Address, Load->getType(), getDominatorTree(),
1307  getAliasAnalysis())) {
1308  ValuesPerBlock.push_back(
1310  continue;
1311  }
1312  UnavailableBlocks.push_back(DepBB);
1313  continue;
1314  }
1315 
1316  AvailableValue AV;
1317  if (AnalyzeLoadAvailability(Load, DepInfo, Address, AV)) {
1318  // subtlety: because we know this was a non-local dependency, we know
1319  // it's safe to materialize anywhere between the instruction within
1320  // DepInfo and the end of it's block.
1321  ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB,
1322  std::move(AV)));
1323  } else {
1324  UnavailableBlocks.push_back(DepBB);
1325  }
1326  }
1327 
1328  assert(NumDeps == ValuesPerBlock.size() + UnavailableBlocks.size() &&
1329  "post condition violation");
1330 }
1331 
1332 void GVNPass::eliminatePartiallyRedundantLoad(
1333  LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
1334  MapVector<BasicBlock *, Value *> &AvailableLoads) {
1335  for (const auto &AvailableLoad : AvailableLoads) {
1336  BasicBlock *UnavailableBlock = AvailableLoad.first;
1337  Value *LoadPtr = AvailableLoad.second;
1338 
1339  auto *NewLoad =
1340  new LoadInst(Load->getType(), LoadPtr, Load->getName() + ".pre",
1341  Load->isVolatile(), Load->getAlign(), Load->getOrdering(),
1342  Load->getSyncScopeID(), UnavailableBlock->getTerminator());
1343  NewLoad->setDebugLoc(Load->getDebugLoc());
1344  if (MSSAU) {
1345  auto *MSSA = MSSAU->getMemorySSA();
1346  // Get the defining access of the original load or use the load if it is a
1347  // MemoryDef (e.g. because it is volatile). The inserted loads are
1348  // guaranteed to load from the same definition.
1349  auto *LoadAcc = MSSA->getMemoryAccess(Load);
1350  auto *DefiningAcc =
1351  isa<MemoryDef>(LoadAcc) ? LoadAcc : LoadAcc->getDefiningAccess();
1352  auto *NewAccess = MSSAU->createMemoryAccessInBB(
1353  NewLoad, DefiningAcc, NewLoad->getParent(),
1355  if (auto *NewDef = dyn_cast<MemoryDef>(NewAccess))
1356  MSSAU->insertDef(NewDef, /*RenameUses=*/true);
1357  else
1358  MSSAU->insertUse(cast<MemoryUse>(NewAccess), /*RenameUses=*/true);
1359  }
1360 
1361  // Transfer the old load's AA tags to the new load.
1362  AAMDNodes Tags = Load->getAAMetadata();
1363  if (Tags)
1364  NewLoad->setAAMetadata(Tags);
1365 
1366  if (auto *MD = Load->getMetadata(LLVMContext::MD_invariant_load))
1367  NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
1368  if (auto *InvGroupMD = Load->getMetadata(LLVMContext::MD_invariant_group))
1369  NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
1370  if (auto *RangeMD = Load->getMetadata(LLVMContext::MD_range))
1371  NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);
1372  if (auto *AccessMD = Load->getMetadata(LLVMContext::MD_access_group))
1373  if (LI &&
1374  LI->getLoopFor(Load->getParent()) == LI->getLoopFor(UnavailableBlock))
1375  NewLoad->setMetadata(LLVMContext::MD_access_group, AccessMD);
1376 
1377  // We do not propagate the old load's debug location, because the new
1378  // load now lives in a different BB, and we want to avoid a jumpy line
1379  // table.
1380  // FIXME: How do we retain source locations without causing poor debugging
1381  // behavior?
1382 
1383  // Add the newly created load.
1384  ValuesPerBlock.push_back(
1385  AvailableValueInBlock::get(UnavailableBlock, NewLoad));
1386  MD->invalidateCachedPointerInfo(LoadPtr);
1387  LLVM_DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n');
1388  }
1389 
1390  // Perform PHI construction.
1391  Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
1392  Load->replaceAllUsesWith(V);
1393  if (isa<PHINode>(V))
1394  V->takeName(Load);
1395  if (Instruction *I = dyn_cast<Instruction>(V))
1396  I->setDebugLoc(Load->getDebugLoc());
1397  if (V->getType()->isPtrOrPtrVectorTy())
1398  MD->invalidateCachedPointerInfo(V);
1399  markInstructionForDeletion(Load);
1400  ORE->emit([&]() {
1401  return OptimizationRemark(DEBUG_TYPE, "LoadPRE", Load)
1402  << "load eliminated by PRE";
1403  });
1404 }
1405 
1406 bool GVNPass::PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
1407  UnavailBlkVect &UnavailableBlocks) {
1408  // Okay, we have *some* definitions of the value. This means that the value
1409  // is available in some of our (transitive) predecessors. Lets think about
1410  // doing PRE of this load. This will involve inserting a new load into the
1411  // predecessor when it's not available. We could do this in general, but
1412  // prefer to not increase code size. As such, we only do this when we know
1413  // that we only have to insert *one* load (which means we're basically moving
1414  // the load, not inserting a new one).
1415 
1416  SmallPtrSet<BasicBlock *, 4> Blockers(UnavailableBlocks.begin(),
1417  UnavailableBlocks.end());
1418 
1419  // Let's find the first basic block with more than one predecessor. Walk
1420  // backwards through predecessors if needed.
1421  BasicBlock *LoadBB = Load->getParent();
1422  BasicBlock *TmpBB = LoadBB;
1423 
1424  // Check that there is no implicit control flow instructions above our load in
1425  // its block. If there is an instruction that doesn't always pass the
1426  // execution to the following instruction, then moving through it may become
1427  // invalid. For example:
1428  //
1429  // int arr[LEN];
1430  // int index = ???;
1431  // ...
1432  // guard(0 <= index && index < LEN);
1433  // use(arr[index]);
1434  //
1435  // It is illegal to move the array access to any point above the guard,
1436  // because if the index is out of bounds we should deoptimize rather than
1437  // access the array.
1438  // Check that there is no guard in this block above our instruction.
1439  bool MustEnsureSafetyOfSpeculativeExecution =
1440  ICF->isDominatedByICFIFromSameBlock(Load);
1441 
1442  while (TmpBB->getSinglePredecessor()) {
1443  TmpBB = TmpBB->getSinglePredecessor();
1444  if (TmpBB == LoadBB) // Infinite (unreachable) loop.
1445  return false;
1446  if (Blockers.count(TmpBB))
1447  return false;
1448 
1449  // If any of these blocks has more than one successor (i.e. if the edge we
1450  // just traversed was critical), then there are other paths through this
1451  // block along which the load may not be anticipated. Hoisting the load
1452  // above this block would be adding the load to execution paths along
1453  // which it was not previously executed.
1454  if (TmpBB->getTerminator()->getNumSuccessors() != 1)
1455  return false;
1456 
1457  // Check that there is no implicit control flow in a block above.
1458  MustEnsureSafetyOfSpeculativeExecution =
1459  MustEnsureSafetyOfSpeculativeExecution || ICF->hasICF(TmpBB);
1460  }
1461 
1462  assert(TmpBB);
1463  LoadBB = TmpBB;
1464 
1465  // Check to see how many predecessors have the loaded value fully
1466  // available.
1468  DenseMap<BasicBlock *, AvailabilityState> FullyAvailableBlocks;
1469  for (const AvailableValueInBlock &AV : ValuesPerBlock)
1470  FullyAvailableBlocks[AV.BB] = AvailabilityState::Available;
1471  for (BasicBlock *UnavailableBB : UnavailableBlocks)
1472  FullyAvailableBlocks[UnavailableBB] = AvailabilityState::Unavailable;
1473 
1474  SmallVector<BasicBlock *, 4> CriticalEdgePred;
1475  for (BasicBlock *Pred : predecessors(LoadBB)) {
1476  // If any predecessor block is an EH pad that does not allow non-PHI
1477  // instructions before the terminator, we can't PRE the load.
1478  if (Pred->getTerminator()->isEHPad()) {
1479  LLVM_DEBUG(
1480  dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
1481  << Pred->getName() << "': " << *Load << '\n');
1482  return false;
1483  }
1484 
1485  if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks)) {
1486  continue;
1487  }
1488 
1489  if (Pred->getTerminator()->getNumSuccessors() != 1) {
1490  if (isa<IndirectBrInst>(Pred->getTerminator())) {
1491  LLVM_DEBUG(
1492  dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
1493  << Pred->getName() << "': " << *Load << '\n');
1494  return false;
1495  }
1496 
1497  // FIXME: Can we support the fallthrough edge?
1498  if (isa<CallBrInst>(Pred->getTerminator())) {
1499  LLVM_DEBUG(
1500  dbgs() << "COULD NOT PRE LOAD BECAUSE OF CALLBR CRITICAL EDGE '"
1501  << Pred->getName() << "': " << *Load << '\n');
1502  return false;
1503  }
1504 
1505  if (LoadBB->isEHPad()) {
1506  LLVM_DEBUG(
1507  dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
1508  << Pred->getName() << "': " << *Load << '\n');
1509  return false;
1510  }
1511 
1512  // Do not split backedge as it will break the canonical loop form.
1513  if (!isLoadPRESplitBackedgeEnabled())
1514  if (DT->dominates(LoadBB, Pred)) {
1515  LLVM_DEBUG(
1516  dbgs()
1517  << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
1518  << Pred->getName() << "': " << *Load << '\n');
1519  return false;
1520  }
1521 
1522  CriticalEdgePred.push_back(Pred);
1523  } else {
1524  // Only add the predecessors that will not be split for now.
1525  PredLoads[Pred] = nullptr;
1526  }
1527  }
1528 
1529  // Decide whether PRE is profitable for this load.
1530  unsigned NumUnavailablePreds = PredLoads.size() + CriticalEdgePred.size();
1531  assert(NumUnavailablePreds != 0 &&
1532  "Fully available value should already be eliminated!");
1533 
1534  // If this load is unavailable in multiple predecessors, reject it.
1535  // FIXME: If we could restructure the CFG, we could make a common pred with
1536  // all the preds that don't have an available Load and insert a new load into
1537  // that one block.
1538  if (NumUnavailablePreds != 1)
1539  return false;
1540 
1541  // Now we know where we will insert load. We must ensure that it is safe
1542  // to speculatively execute the load at that points.
1543  if (MustEnsureSafetyOfSpeculativeExecution) {
1544  if (CriticalEdgePred.size())
1545  if (!isSafeToSpeculativelyExecute(Load, LoadBB->getFirstNonPHI(), DT))
1546  return false;
1547  for (auto &PL : PredLoads)
1548  if (!isSafeToSpeculativelyExecute(Load, PL.first->getTerminator(), DT))
1549  return false;
1550  }
1551 
1552  // Split critical edges, and update the unavailable predecessors accordingly.
1553  for (BasicBlock *OrigPred : CriticalEdgePred) {
1554  BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);
1555  assert(!PredLoads.count(OrigPred) && "Split edges shouldn't be in map!");
1556  PredLoads[NewPred] = nullptr;
1557  LLVM_DEBUG(dbgs() << "Split critical edge " << OrigPred->getName() << "->"
1558  << LoadBB->getName() << '\n');
1559  }
1560 
1561  // Check if the load can safely be moved to all the unavailable predecessors.
1562  bool CanDoPRE = true;
1563  const DataLayout &DL = Load->getModule()->getDataLayout();
1565  for (auto &PredLoad : PredLoads) {
1566  BasicBlock *UnavailablePred = PredLoad.first;
1567 
1568  // Do PHI translation to get its value in the predecessor if necessary. The
1569  // returned pointer (if non-null) is guaranteed to dominate UnavailablePred.
1570  // We do the translation for each edge we skipped by going from Load's block
1571  // to LoadBB, otherwise we might miss pieces needing translation.
1572 
1573  // If all preds have a single successor, then we know it is safe to insert
1574  // the load on the pred (?!?), so we can insert code to materialize the
1575  // pointer if it is not available.
1576  Value *LoadPtr = Load->getPointerOperand();
1577  BasicBlock *Cur = Load->getParent();
1578  while (Cur != LoadBB) {
1579  PHITransAddr Address(LoadPtr, DL, AC);
1580  LoadPtr = Address.PHITranslateWithInsertion(
1581  Cur, Cur->getSinglePredecessor(), *DT, NewInsts);
1582  if (!LoadPtr) {
1583  CanDoPRE = false;
1584  break;
1585  }
1586  Cur = Cur->getSinglePredecessor();
1587  }
1588 
1589  if (LoadPtr) {
1590  PHITransAddr Address(LoadPtr, DL, AC);
1591  LoadPtr = Address.PHITranslateWithInsertion(LoadBB, UnavailablePred, *DT,
1592  NewInsts);
1593  }
1594  // If we couldn't find or insert a computation of this phi translated value,
1595  // we fail PRE.
1596  if (!LoadPtr) {
1597  LLVM_DEBUG(dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
1598  << *Load->getPointerOperand() << "\n");
1599  CanDoPRE = false;
1600  break;
1601  }
1602 
1603  PredLoad.second = LoadPtr;
1604  }
1605 
1606  if (!CanDoPRE) {
1607  while (!NewInsts.empty()) {
1608  // Erase instructions generated by the failed PHI translation before
1609  // trying to number them. PHI translation might insert instructions
1610  // in basic blocks other than the current one, and we delete them
1611  // directly, as markInstructionForDeletion only allows removing from the
1612  // current basic block.
1613  NewInsts.pop_back_val()->eraseFromParent();
1614  }
1615  // HINT: Don't revert the edge-splitting as following transformation may
1616  // also need to split these critical edges.
1617  return !CriticalEdgePred.empty();
1618  }
1619 
1620  // Okay, we can eliminate this load by inserting a reload in the predecessor
1621  // and using PHI construction to get the value in the other predecessors, do
1622  // it.
1623  LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOAD: " << *Load << '\n');
1624  LLVM_DEBUG(if (!NewInsts.empty()) dbgs() << "INSERTED " << NewInsts.size()
1625  << " INSTS: " << *NewInsts.back()
1626  << '\n');
1627 
1628  // Assign value numbers to the new instructions.
1629  for (Instruction *I : NewInsts) {
1630  // Instructions that have been inserted in predecessor(s) to materialize
1631  // the load address do not retain their original debug locations. Doing
1632  // so could lead to confusing (but correct) source attributions.
1633  I->updateLocationAfterHoist();
1634 
1635  // FIXME: We really _ought_ to insert these value numbers into their
1636  // parent's availability map. However, in doing so, we risk getting into
1637  // ordering issues. If a block hasn't been processed yet, we would be
1638  // marking a value as AVAIL-IN, which isn't what we intend.
1639  VN.lookupOrAdd(I);
1640  }
1641 
1642  eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, PredLoads);
1643  ++NumPRELoad;
1644  return true;
1645 }
1646 
1647 bool GVNPass::performLoopLoadPRE(LoadInst *Load,
1648  AvailValInBlkVect &ValuesPerBlock,
1649  UnavailBlkVect &UnavailableBlocks) {
1650  if (!LI)
1651  return false;
1652 
1653  const Loop *L = LI->getLoopFor(Load->getParent());
1654  // TODO: Generalize to other loop blocks that dominate the latch.
1655  if (!L || L->getHeader() != Load->getParent())
1656  return false;
1657 
1658  BasicBlock *Preheader = L->getLoopPreheader();
1659  BasicBlock *Latch = L->getLoopLatch();
1660  if (!Preheader || !Latch)
1661  return false;
1662 
1663  Value *LoadPtr = Load->getPointerOperand();
1664  // Must be available in preheader.
1665  if (!L->isLoopInvariant(LoadPtr))
1666  return false;
1667 
1668  // We plan to hoist the load to preheader without introducing a new fault.
1669  // In order to do it, we need to prove that we cannot side-exit the loop
1670  // once loop header is first entered before execution of the load.
1671  if (ICF->isDominatedByICFIFromSameBlock(Load))
1672  return false;
1673 
1674  BasicBlock *LoopBlock = nullptr;
1675  for (auto *Blocker : UnavailableBlocks) {
1676  // Blockers from outside the loop are handled in preheader.
1677  if (!L->contains(Blocker))
1678  continue;
1679 
1680  // Only allow one loop block. Loop header is not less frequently executed
1681  // than each loop block, and likely it is much more frequently executed. But
1682  // in case of multiple loop blocks, we need extra information (such as block
1683  // frequency info) to understand whether it is profitable to PRE into
1684  // multiple loop blocks.
1685  if (LoopBlock)
1686  return false;
1687 
1688  // Do not sink into inner loops. This may be non-profitable.
1689  if (L != LI->getLoopFor(Blocker))
1690  return false;
1691 
1692  // Blocks that dominate the latch execute on every single iteration, maybe
1693  // except the last one. So PREing into these blocks doesn't make much sense
1694  // in most cases. But the blocks that do not necessarily execute on each
1695  // iteration are sometimes much colder than the header, and this is when
1696  // PRE is potentially profitable.
1697  if (DT->dominates(Blocker, Latch))
1698  return false;
1699 
1700  // Make sure that the terminator itself doesn't clobber.
1701  if (Blocker->getTerminator()->mayWriteToMemory())
1702  return false;
1703 
1704  LoopBlock = Blocker;
1705  }
1706 
1707  if (!LoopBlock)
1708  return false;
1709 
1710  // Make sure the memory at this pointer cannot be freed, therefore we can
1711  // safely reload from it after clobber.
1712  if (LoadPtr->canBeFreed())
1713  return false;
1714 
1715  // TODO: Support critical edge splitting if blocker has more than 1 successor.
1716  MapVector<BasicBlock *, Value *> AvailableLoads;
1717  AvailableLoads[LoopBlock] = LoadPtr;
1718  AvailableLoads[Preheader] = LoadPtr;
1719 
1720  LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOOP LOAD: " << *Load << '\n');
1721  eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, AvailableLoads);
1722  ++NumPRELoopLoad;
1723  return true;
1724 }
1725 
1728  using namespace ore;
1729 
1730  ORE->emit([&]() {
1731  return OptimizationRemark(DEBUG_TYPE, "LoadElim", Load)
1732  << "load of type " << NV("Type", Load->getType()) << " eliminated"
1733  << setExtraArgs() << " in favor of "
1734  << NV("InfavorOfValue", AvailableValue);
1735  });
1736 }
1737 
1738 /// Attempt to eliminate a load whose dependencies are
1739 /// non-local by performing PHI construction.
1740 bool GVNPass::processNonLocalLoad(LoadInst *Load) {
1741  // non-local speculations are not allowed under asan.
1742  if (Load->getParent()->getParent()->hasFnAttribute(
1743  Attribute::SanitizeAddress) ||
1744  Load->getParent()->getParent()->hasFnAttribute(
1745  Attribute::SanitizeHWAddress))
1746  return false;
1747 
1748  // Step 1: Find the non-local dependencies of the load.
1749  LoadDepVect Deps;
1750  MD->getNonLocalPointerDependency(Load, Deps);
1751 
1752  // If we had to process more than one hundred blocks to find the
1753  // dependencies, this load isn't worth worrying about. Optimizing
1754  // it will be too expensive.
1755  unsigned NumDeps = Deps.size();
1756  if (NumDeps > MaxNumDeps)
1757  return false;
1758 
1759  // If we had a phi translation failure, we'll have a single entry which is a
1760  // clobber in the current block. Reject this early.
1761  if (NumDeps == 1 &&
1762  !Deps[0].getResult().isDef() && !Deps[0].getResult().isClobber()) {
1763  LLVM_DEBUG(dbgs() << "GVN: non-local load "; Load->printAsOperand(dbgs());
1764  dbgs() << " has unknown dependencies\n";);
1765  return false;
1766  }
1767 
1768  bool Changed = false;
1769  // If this load follows a GEP, see if we can PRE the indices before analyzing.
1770  if (GetElementPtrInst *GEP =
1771  dyn_cast<GetElementPtrInst>(Load->getOperand(0))) {
1772  for (Use &U : GEP->indices())
1773  if (Instruction *I = dyn_cast<Instruction>(U.get()))
1774  Changed |= performScalarPRE(I);
1775  }
1776 
1777  // Step 2: Analyze the availability of the load
1778  AvailValInBlkVect ValuesPerBlock;
1779  UnavailBlkVect UnavailableBlocks;
1780  AnalyzeLoadAvailability(Load, Deps, ValuesPerBlock, UnavailableBlocks);
1781 
1782  // If we have no predecessors that produce a known value for this load, exit
1783  // early.
1784  if (ValuesPerBlock.empty())
1785  return Changed;
1786 
1787  // Step 3: Eliminate fully redundancy.
1788  //
1789  // If all of the instructions we depend on produce a known value for this
1790  // load, then it is fully redundant and we can use PHI insertion to compute
1791  // its value. Insert PHIs and remove the fully redundant value now.
1792  if (UnavailableBlocks.empty()) {
1793  LLVM_DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *Load << '\n');
1794 
1795  // Perform PHI construction.
1796  Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
1797  Load->replaceAllUsesWith(V);
1798 
1799  if (isa<PHINode>(V))
1800  V->takeName(Load);
1801  if (Instruction *I = dyn_cast<Instruction>(V))
1802  // If instruction I has debug info, then we should not update it.
1803  // Also, if I has a null DebugLoc, then it is still potentially incorrect
1804  // to propagate Load's DebugLoc because Load may not post-dominate I.
1805  if (Load->getDebugLoc() && Load->getParent() == I->getParent())
1806  I->setDebugLoc(Load->getDebugLoc());
1807  if (V->getType()->isPtrOrPtrVectorTy())
1808  MD->invalidateCachedPointerInfo(V);
1809  markInstructionForDeletion(Load);
1810  ++NumGVNLoad;
1811  reportLoadElim(Load, V, ORE);
1812  return true;
1813  }
1814 
1815  // Step 4: Eliminate partial redundancy.
1816  if (!isPREEnabled() || !isLoadPREEnabled())
1817  return Changed;
1818  if (!isLoadInLoopPREEnabled() && LI && LI->getLoopFor(Load->getParent()))
1819  return Changed;
1820 
1821  if (performLoopLoadPRE(Load, ValuesPerBlock, UnavailableBlocks) ||
1822  PerformLoadPRE(Load, ValuesPerBlock, UnavailableBlocks))
1823  return true;
1824 
1825  return Changed;
1826 }
1827 
1829  if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_EQ)
1830  return true;
1831 
1832  // Floating point comparisons can be equal, but not equivalent. Cases:
1833  // NaNs for unordered operators
1834  // +0.0 vs 0.0 for all operators
1835  if (Cmp->getPredicate() == CmpInst::Predicate::FCMP_OEQ ||
1836  (Cmp->getPredicate() == CmpInst::Predicate::FCMP_UEQ &&
1837  Cmp->getFastMathFlags().noNaNs())) {
1838  Value *LHS = Cmp->getOperand(0);
1839  Value *RHS = Cmp->getOperand(1);
1840  // If we can prove either side non-zero, then equality must imply
1841  // equivalence.
1842  // FIXME: We should do this optimization if 'no signed zeros' is
1843  // applicable via an instruction-level fast-math-flag or some other
1844  // indicator that relaxed FP semantics are being used.
1845  if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
1846  return true;
1847  if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
1848  return true;;
1849  // TODO: Handle vector floating point constants
1850  }
1851  return false;
1852 }
1853 
1855  if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_NE)
1856  return true;
1857 
1858  // Floating point comparisons can be equal, but not equivelent. Cases:
1859  // NaNs for unordered operators
1860  // +0.0 vs 0.0 for all operators
1861  if ((Cmp->getPredicate() == CmpInst::Predicate::FCMP_ONE &&
1862  Cmp->getFastMathFlags().noNaNs()) ||
1863  Cmp->getPredicate() == CmpInst::Predicate::FCMP_UNE) {
1864  Value *LHS = Cmp->getOperand(0);
1865  Value *RHS = Cmp->getOperand(1);
1866  // If we can prove either side non-zero, then equality must imply
1867  // equivalence.
1868  // FIXME: We should do this optimization if 'no signed zeros' is
1869  // applicable via an instruction-level fast-math-flag or some other
1870  // indicator that relaxed FP semantics are being used.
1871  if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
1872  return true;
1873  if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
1874  return true;;
1875  // TODO: Handle vector floating point constants
1876  }
1877  return false;
1878 }
1879 
1880 
1881 static bool hasUsersIn(Value *V, BasicBlock *BB) {
1882  for (User *U : V->users())
1883  if (isa<Instruction>(U) &&
1884  cast<Instruction>(U)->getParent() == BB)
1885  return true;
1886  return false;
1887 }
1888 
1889 bool GVNPass::processAssumeIntrinsic(AssumeInst *IntrinsicI) {
1890  Value *V = IntrinsicI->getArgOperand(0);
1891 
1892  if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {
1893  if (Cond->isZero()) {
1894  Type *Int8Ty = Type::getInt8Ty(V->getContext());
1895  // Insert a new store to null instruction before the load to indicate that
1896  // this code is not reachable. FIXME: We could insert unreachable
1897  // instruction directly because we can modify the CFG.
1898  auto *NewS = new StoreInst(PoisonValue::get(Int8Ty),
1900  IntrinsicI);
1901  if (MSSAU) {
1902  const MemoryUseOrDef *FirstNonDom = nullptr;
1903  const auto *AL =
1904  MSSAU->getMemorySSA()->getBlockAccesses(IntrinsicI->getParent());
1905 
1906  // If there are accesses in the current basic block, find the first one
1907  // that does not come before NewS. The new memory access is inserted
1908  // after the found access or before the terminator if no such access is
1909  // found.
1910  if (AL) {
1911  for (auto &Acc : *AL) {
1912  if (auto *Current = dyn_cast<MemoryUseOrDef>(&Acc))
1913  if (!Current->getMemoryInst()->comesBefore(NewS)) {
1914  FirstNonDom = Current;
1915  break;
1916  }
1917  }
1918  }
1919 
1920  // This added store is to null, so it will never executed and we can
1921  // just use the LiveOnEntry def as defining access.
1922  auto *NewDef =
1923  FirstNonDom ? MSSAU->createMemoryAccessBefore(
1924  NewS, MSSAU->getMemorySSA()->getLiveOnEntryDef(),
1925  const_cast<MemoryUseOrDef *>(FirstNonDom))
1926  : MSSAU->createMemoryAccessInBB(
1927  NewS, MSSAU->getMemorySSA()->getLiveOnEntryDef(),
1928  NewS->getParent(), MemorySSA::BeforeTerminator);
1929 
1930  MSSAU->insertDef(cast<MemoryDef>(NewDef), /*RenameUses=*/false);
1931  }
1932  }
1933  if (isAssumeWithEmptyBundle(*IntrinsicI))
1934  markInstructionForDeletion(IntrinsicI);
1935  return false;
1936  } else if (isa<Constant>(V)) {
1937  // If it's not false, and constant, it must evaluate to true. This means our
1938  // assume is assume(true), and thus, pointless, and we don't want to do
1939  // anything more here.
1940  return false;
1941  }
1942 
1944  bool Changed = false;
1945 
1946  for (BasicBlock *Successor : successors(IntrinsicI->getParent())) {
1947  BasicBlockEdge Edge(IntrinsicI->getParent(), Successor);
1948 
1949  // This property is only true in dominated successors, propagateEquality
1950  // will check dominance for us.
1951  Changed |= propagateEquality(V, True, Edge, false);
1952  }
1953 
1954  // We can replace assume value with true, which covers cases like this:
1955  // call void @llvm.assume(i1 %cmp)
1956  // br i1 %cmp, label %bb1, label %bb2 ; will change %cmp to true
1957  ReplaceOperandsWithMap[V] = True;
1958 
1959  // Similarly, after assume(!NotV) we know that NotV == false.
1960  Value *NotV;
1961  if (match(V, m_Not(m_Value(NotV))))
1962  ReplaceOperandsWithMap[NotV] = ConstantInt::getFalse(V->getContext());
1963 
1964  // If we find an equality fact, canonicalize all dominated uses in this block
1965  // to one of the two values. We heuristically choice the "oldest" of the
1966  // two where age is determined by value number. (Note that propagateEquality
1967  // above handles the cross block case.)
1968  //
1969  // Key case to cover are:
1970  // 1)
1971  // %cmp = fcmp oeq float 3.000000e+00, %0 ; const on lhs could happen
1972  // call void @llvm.assume(i1 %cmp)
1973  // ret float %0 ; will change it to ret float 3.000000e+00
1974  // 2)
1975  // %load = load float, float* %addr
1976  // %cmp = fcmp oeq float %load, %0
1977  // call void @llvm.assume(i1 %cmp)
1978  // ret float %load ; will change it to ret float %0
1979  if (auto *CmpI = dyn_cast<CmpInst>(V)) {
1980  if (impliesEquivalanceIfTrue(CmpI)) {
1981  Value *CmpLHS = CmpI->getOperand(0);
1982  Value *CmpRHS = CmpI->getOperand(1);
1983  // Heuristically pick the better replacement -- the choice of heuristic
1984  // isn't terribly important here, but the fact we canonicalize on some
1985  // replacement is for exposing other simplifications.
1986  // TODO: pull this out as a helper function and reuse w/existing
1987  // (slightly different) logic.
1988  if (isa<Constant>(CmpLHS) && !isa<Constant>(CmpRHS))
1989  std::swap(CmpLHS, CmpRHS);
1990  if (!isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))
1991  std::swap(CmpLHS, CmpRHS);
1992  if ((isa<Argument>(CmpLHS) && isa<Argument>(CmpRHS)) ||
1993  (isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))) {
1994  // Move the 'oldest' value to the right-hand side, using the value
1995  // number as a proxy for age.
1996  uint32_t LVN = VN.lookupOrAdd(CmpLHS);
1997  uint32_t RVN = VN.lookupOrAdd(CmpRHS);
1998  if (LVN < RVN)
1999  std::swap(CmpLHS, CmpRHS);
2000  }
2001 
2002  // Handle degenerate case where we either haven't pruned a dead path or a
2003  // removed a trivial assume yet.
2004  if (isa<Constant>(CmpLHS) && isa<Constant>(CmpRHS))
2005  return Changed;
2006 
2007  LLVM_DEBUG(dbgs() << "Replacing dominated uses of "
2008  << *CmpLHS << " with "
2009  << *CmpRHS << " in block "
2010  << IntrinsicI->getParent()->getName() << "\n");
2011 
2012 
2013  // Setup the replacement map - this handles uses within the same block
2014  if (hasUsersIn(CmpLHS, IntrinsicI->getParent()))
2015  ReplaceOperandsWithMap[CmpLHS] = CmpRHS;
2016 
2017  // NOTE: The non-block local cases are handled by the call to
2018  // propagateEquality above; this block is just about handling the block
2019  // local cases. TODO: There's a bunch of logic in propagateEqualiy which
2020  // isn't duplicated for the block local case, can we share it somehow?
2021  }
2022  }
2023  return Changed;
2024 }
2025 
2028  I->replaceAllUsesWith(Repl);
2029 }
2030 
2031 /// Attempt to eliminate a load, first by eliminating it
2032 /// locally, and then attempting non-local elimination if that fails.
2033 bool GVNPass::processLoad(LoadInst *L) {
2034  if (!MD)
2035  return false;
2036 
2037  // This code hasn't been audited for ordered or volatile memory access
2038  if (!L->isUnordered())
2039  return false;
2040 
2041  if (L->use_empty()) {
2042  markInstructionForDeletion(L);
2043  return true;
2044  }
2045 
2046  // ... to a pointer that has been loaded from before...
2047  MemDepResult Dep = MD->getDependency(L);
2048 
2049  // If it is defined in another block, try harder.
2050  if (Dep.isNonLocal())
2051  return processNonLocalLoad(L);
2052 
2054  // Only handle the local case below
2055  if (!Dep.isDef() && !Dep.isClobber() && !isa<SelectInst>(Address)) {
2056  // This might be a NonFuncLocal or an Unknown
2057  LLVM_DEBUG(
2058  // fast print dep, using operator<< on instruction is too slow.
2059  dbgs() << "GVN: load "; L->printAsOperand(dbgs());
2060  dbgs() << " has unknown dependence\n";);
2061  return false;
2062  }
2063 
2064  AvailableValue AV;
2065  if (AnalyzeLoadAvailability(L, Dep, Address, AV)) {
2066  Value *AvailableValue = AV.MaterializeAdjustedValue(L, L, *this);
2067 
2068  // Replace the load!
2070  markInstructionForDeletion(L);
2071  if (MSSAU)
2072  MSSAU->removeMemoryAccess(L);
2073  ++NumGVNLoad;
2074  reportLoadElim(L, AvailableValue, ORE);
2075  // Tell MDA to reexamine the reused pointer since we might have more
2076  // information after forwarding it.
2077  if (MD && AvailableValue->getType()->isPtrOrPtrVectorTy())
2078  MD->invalidateCachedPointerInfo(AvailableValue);
2079  return true;
2080  }
2081 
2082  return false;
2083 }
2084 
2085 /// Return a pair the first field showing the value number of \p Exp and the
2086 /// second field showing whether it is a value number newly created.
2087 std::pair<uint32_t, bool>
2088 GVNPass::ValueTable::assignExpNewValueNum(Expression &Exp) {
2089  uint32_t &e = expressionNumbering[Exp];
2090  bool CreateNewValNum = !e;
2091  if (CreateNewValNum) {
2092  Expressions.push_back(Exp);
2093  if (ExprIdx.size() < nextValueNumber + 1)
2094  ExprIdx.resize(nextValueNumber * 2);
2095  e = nextValueNumber;
2096  ExprIdx[nextValueNumber++] = nextExprNumber++;
2097  }
2098  return {e, CreateNewValNum};
2099 }
2100 
2101 /// Return whether all the values related with the same \p num are
2102 /// defined in \p BB.
2103 bool GVNPass::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB,
2104  GVNPass &Gvn) {
2105  LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
2106  while (Vals && Vals->BB == BB)
2107  Vals = Vals->Next;
2108  return !Vals;
2109 }
2110 
2111 /// Wrap phiTranslateImpl to provide caching functionality.
2113  const BasicBlock *PhiBlock,
2114  uint32_t Num, GVNPass &Gvn) {
2115  auto FindRes = PhiTranslateTable.find({Num, Pred});
2116  if (FindRes != PhiTranslateTable.end())
2117  return FindRes->second;
2118  uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, Gvn);
2119  PhiTranslateTable.insert({{Num, Pred}, NewNum});
2120  return NewNum;
2121 }
2122 
2123 // Return true if the value number \p Num and NewNum have equal value.
2124 // Return false if the result is unknown.
2125 bool GVNPass::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum,
2126  const BasicBlock *Pred,
2127  const BasicBlock *PhiBlock,
2128  GVNPass &Gvn) {
2129  CallInst *Call = nullptr;
2130  LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
2131  while (Vals) {
2132  Call = dyn_cast<CallInst>(Vals->Val);
2133  if (Call && Call->getParent() == PhiBlock)
2134  break;
2135  Vals = Vals->Next;
2136  }
2137 
2138  if (AA->doesNotAccessMemory(Call))
2139  return true;
2140 
2141  if (!MD || !AA->onlyReadsMemory(Call))
2142  return false;
2143 
2144  MemDepResult local_dep = MD->getDependency(Call);
2145  if (!local_dep.isNonLocal())
2146  return false;
2147 
2149  MD->getNonLocalCallDependency(Call);
2150 
2151  // Check to see if the Call has no function local clobber.
2152  for (const NonLocalDepEntry &D : deps) {
2153  if (D.getResult().isNonFuncLocal())
2154  return true;
2155  }
2156  return false;
2157 }
2158 
2159 /// Translate value number \p Num using phis, so that it has the values of
2160 /// the phis in BB.
2161 uint32_t GVNPass::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
2162  const BasicBlock *PhiBlock,
2163  uint32_t Num, GVNPass &Gvn) {
2164  if (PHINode *PN = NumberingPhi[Num]) {
2165  for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
2166  if (PN->getParent() == PhiBlock && PN->getIncomingBlock(i) == Pred)
2167  if (uint32_t TransVal = lookup(PN->getIncomingValue(i), false))
2168  return TransVal;
2169  }
2170  return Num;
2171  }
2172 
2173  // If there is any value related with Num is defined in a BB other than
2174  // PhiBlock, it cannot depend on a phi in PhiBlock without going through
2175  // a backedge. We can do an early exit in that case to save compile time.
2176  if (!areAllValsInBB(Num, PhiBlock, Gvn))
2177  return Num;
2178 
2179  if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)
2180  return Num;
2181  Expression Exp = Expressions[ExprIdx[Num]];
2182 
2183  for (unsigned i = 0; i < Exp.varargs.size(); i++) {
2184  // For InsertValue and ExtractValue, some varargs are index numbers
2185  // instead of value numbers. Those index numbers should not be
2186  // translated.
2187  if ((i > 1 && Exp.opcode == Instruction::InsertValue) ||
2188  (i > 0 && Exp.opcode == Instruction::ExtractValue) ||
2189  (i > 1 && Exp.opcode == Instruction::ShuffleVector))
2190  continue;
2191  Exp.varargs[i] = phiTranslate(Pred, PhiBlock, Exp.varargs[i], Gvn);
2192  }
2193 
2194  if (Exp.commutative) {
2195  assert(Exp.varargs.size() >= 2 && "Unsupported commutative instruction!");
2196  if (Exp.varargs[0] > Exp.varargs[1]) {
2197  std::swap(Exp.varargs[0], Exp.varargs[1]);
2198  uint32_t Opcode = Exp.opcode >> 8;
2199  if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
2200  Exp.opcode = (Opcode << 8) |
2202  static_cast<CmpInst::Predicate>(Exp.opcode & 255));
2203  }
2204  }
2205 
2206  if (uint32_t NewNum = expressionNumbering[Exp]) {
2207  if (Exp.opcode == Instruction::Call && NewNum != Num)
2208  return areCallValsEqual(Num, NewNum, Pred, PhiBlock, Gvn) ? NewNum : Num;
2209  return NewNum;
2210  }
2211  return Num;
2212 }
2213 
2214 /// Erase stale entry from phiTranslate cache so phiTranslate can be computed
2215 /// again.
2217  uint32_t Num, const BasicBlock &CurrBlock) {
2218  for (const BasicBlock *Pred : predecessors(&CurrBlock))
2219  PhiTranslateTable.erase({Num, Pred});
2220 }
2221 
2222 // In order to find a leader for a given value number at a
2223 // specific basic block, we first obtain the list of all Values for that number,
2224 // and then scan the list to find one whose block dominates the block in
2225 // question. This is fast because dominator tree queries consist of only
2226 // a few comparisons of DFS numbers.
2227 Value *GVNPass::findLeader(const BasicBlock *BB, uint32_t num) {
2228  LeaderTableEntry Vals = LeaderTable[num];
2229  if (!Vals.Val) return nullptr;
2230 
2231  Value *Val = nullptr;
2232  if (DT->dominates(Vals.BB, BB)) {
2233  Val = Vals.Val;
2234  if (isa<Constant>(Val)) return Val;
2235  }
2236 
2237  LeaderTableEntry* Next = Vals.Next;
2238  while (Next) {
2239  if (DT->dominates(Next->BB, BB)) {
2240  if (isa<Constant>(Next->Val)) return Next->Val;
2241  if (!Val) Val = Next->Val;
2242  }
2243 
2244  Next = Next->Next;
2245  }
2246 
2247  return Val;
2248 }
2249 
2250 /// There is an edge from 'Src' to 'Dst'. Return
2251 /// true if every path from the entry block to 'Dst' passes via this edge. In
2252 /// particular 'Dst' must not be reachable via another edge from 'Src'.
2254  DominatorTree *DT) {
2255  // While in theory it is interesting to consider the case in which Dst has
2256  // more than one predecessor, because Dst might be part of a loop which is
2257  // only reachable from Src, in practice it is pointless since at the time
2258  // GVN runs all such loops have preheaders, which means that Dst will have
2259  // been changed to have only one predecessor, namely Src.
2260  const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();
2261  assert((!Pred || Pred == E.getStart()) &&
2262  "No edge between these basic blocks!");
2263  return Pred != nullptr;
2264 }
2265 
2266 void GVNPass::assignBlockRPONumber(Function &F) {
2267  BlockRPONumber.clear();
2268  uint32_t NextBlockNumber = 1;
2270  for (BasicBlock *BB : RPOT)
2271  BlockRPONumber[BB] = NextBlockNumber++;
2272  InvalidBlockRPONumbers = false;
2273 }
2274 
2275 bool GVNPass::replaceOperandsForInBlockEquality(Instruction *Instr) const {
2276  bool Changed = false;
2277  for (unsigned OpNum = 0; OpNum < Instr->getNumOperands(); ++OpNum) {
2278  Value *Operand = Instr->getOperand(OpNum);
2279  auto it = ReplaceOperandsWithMap.find(Operand);
2280  if (it != ReplaceOperandsWithMap.end()) {
2281  LLVM_DEBUG(dbgs() << "GVN replacing: " << *Operand << " with "
2282  << *it->second << " in instruction " << *Instr << '\n');
2283  Instr->setOperand(OpNum, it->second);
2284  Changed = true;
2285  }
2286  }
2287  return Changed;
2288 }
2289 
2290 /// The given values are known to be equal in every block
2291 /// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with
2292 /// 'RHS' everywhere in the scope. Returns whether a change was made.
2293 /// If DominatesByEdge is false, then it means that we will propagate the RHS
2294 /// value starting from the end of Root.Start.
2295 bool GVNPass::propagateEquality(Value *LHS, Value *RHS,
2296  const BasicBlockEdge &Root,
2297  bool DominatesByEdge) {
2299  Worklist.push_back(std::make_pair(LHS, RHS));
2300  bool Changed = false;
2301  // For speed, compute a conservative fast approximation to
2302  // DT->dominates(Root, Root.getEnd());
2303  const bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT);
2304 
2305  while (!Worklist.empty()) {
2306  std::pair<Value*, Value*> Item = Worklist.pop_back_val();
2307  LHS = Item.first; RHS = Item.second;
2308 
2309  if (LHS == RHS)
2310  continue;
2311  assert(LHS->getType() == RHS->getType() && "Equality but unequal types!");
2312 
2313  // Don't try to propagate equalities between constants.
2314  if (isa<Constant>(LHS) && isa<Constant>(RHS))
2315  continue;
2316 
2317  // Prefer a constant on the right-hand side, or an Argument if no constants.
2318  if (isa<Constant>(LHS) || (isa<Argument>(LHS) && !isa<Constant>(RHS)))
2319  std::swap(LHS, RHS);
2320  assert((isa<Argument>(LHS) || isa<Instruction>(LHS)) && "Unexpected value!");
2321 
2322  // If there is no obvious reason to prefer the left-hand side over the
2323  // right-hand side, ensure the longest lived term is on the right-hand side,
2324  // so the shortest lived term will be replaced by the longest lived.
2325  // This tends to expose more simplifications.
2326  uint32_t LVN = VN.lookupOrAdd(LHS);
2327  if ((isa<Argument>(LHS) && isa<Argument>(RHS)) ||
2328  (isa<Instruction>(LHS) && isa<Instruction>(RHS))) {
2329  // Move the 'oldest' value to the right-hand side, using the value number
2330  // as a proxy for age.
2331  uint32_t RVN = VN.lookupOrAdd(RHS);
2332  if (LVN < RVN) {
2333  std::swap(LHS, RHS);
2334  LVN = RVN;
2335  }
2336  }
2337 
2338  // If value numbering later sees that an instruction in the scope is equal
2339  // to 'LHS' then ensure it will be turned into 'RHS'. In order to preserve
2340  // the invariant that instructions only occur in the leader table for their
2341  // own value number (this is used by removeFromLeaderTable), do not do this
2342  // if RHS is an instruction (if an instruction in the scope is morphed into
2343  // LHS then it will be turned into RHS by the next GVN iteration anyway, so
2344  // using the leader table is about compiling faster, not optimizing better).
2345  // The leader table only tracks basic blocks, not edges. Only add to if we
2346  // have the simple case where the edge dominates the end.
2347  if (RootDominatesEnd && !isa<Instruction>(RHS))
2348  addToLeaderTable(LVN, RHS, Root.getEnd());
2349 
2350  // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope. As
2351  // LHS always has at least one use that is not dominated by Root, this will
2352  // never do anything if LHS has only one use.
2353  if (!LHS->hasOneUse()) {
2354  unsigned NumReplacements =
2355  DominatesByEdge
2356  ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
2357  : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart());
2358 
2359  Changed |= NumReplacements > 0;
2360  NumGVNEqProp += NumReplacements;
2361  // Cached information for anything that uses LHS will be invalid.
2362  if (MD)
2363  MD->invalidateCachedPointerInfo(LHS);
2364  }
2365 
2366  // Now try to deduce additional equalities from this one. For example, if
2367  // the known equality was "(A != B)" == "false" then it follows that A and B
2368  // are equal in the scope. Only boolean equalities with an explicit true or
2369  // false RHS are currently supported.
2370  if (!RHS->getType()->isIntegerTy(1))
2371  // Not a boolean equality - bail out.
2372  continue;
2373  ConstantInt *CI = dyn_cast<ConstantInt>(RHS);
2374  if (!CI)
2375  // RHS neither 'true' nor 'false' - bail out.
2376  continue;
2377  // Whether RHS equals 'true'. Otherwise it equals 'false'.
2378  bool isKnownTrue = CI->isMinusOne();
2379  bool isKnownFalse = !isKnownTrue;
2380 
2381  // If "A && B" is known true then both A and B are known true. If "A || B"
2382  // is known false then both A and B are known false.
2383  Value *A, *B;
2384  if ((isKnownTrue && match(LHS, m_LogicalAnd(m_Value(A), m_Value(B)))) ||
2385  (isKnownFalse && match(LHS, m_LogicalOr(m_Value(A), m_Value(B))))) {
2386  Worklist.push_back(std::make_pair(A, RHS));
2387  Worklist.push_back(std::make_pair(B, RHS));
2388  continue;
2389  }
2390 
2391  // If we are propagating an equality like "(A == B)" == "true" then also
2392  // propagate the equality A == B. When propagating a comparison such as
2393  // "(A >= B)" == "true", replace all instances of "A < B" with "false".
2394  if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
2395  Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1);
2396 
2397  // If "A == B" is known true, or "A != B" is known false, then replace
2398  // A with B everywhere in the scope. For floating point operations, we
2399  // have to be careful since equality does not always imply equivalance.
2400  if ((isKnownTrue && impliesEquivalanceIfTrue(Cmp)) ||
2401  (isKnownFalse && impliesEquivalanceIfFalse(Cmp)))
2402  Worklist.push_back(std::make_pair(Op0, Op1));
2403 
2404  // If "A >= B" is known true, replace "A < B" with false everywhere.
2405  CmpInst::Predicate NotPred = Cmp->getInversePredicate();
2406  Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse);
2407  // Since we don't have the instruction "A < B" immediately to hand, work
2408  // out the value number that it would have and use that to find an
2409  // appropriate instruction (if any).
2410  uint32_t NextNum = VN.getNextUnusedValueNumber();
2411  uint32_t Num = VN.lookupOrAddCmp(Cmp->getOpcode(), NotPred, Op0, Op1);
2412  // If the number we were assigned was brand new then there is no point in
2413  // looking for an instruction realizing it: there cannot be one!
2414  if (Num < NextNum) {
2415  Value *NotCmp = findLeader(Root.getEnd(), Num);
2416  if (NotCmp && isa<Instruction>(NotCmp)) {
2417  unsigned NumReplacements =
2418  DominatesByEdge
2419  ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root)
2420  : replaceDominatedUsesWith(NotCmp, NotVal, *DT,
2421  Root.getStart());
2422  Changed |= NumReplacements > 0;
2423  NumGVNEqProp += NumReplacements;
2424  // Cached information for anything that uses NotCmp will be invalid.
2425  if (MD)
2426  MD->invalidateCachedPointerInfo(NotCmp);
2427  }
2428  }
2429  // Ensure that any instruction in scope that gets the "A < B" value number
2430  // is replaced with false.
2431  // The leader table only tracks basic blocks, not edges. Only add to if we
2432  // have the simple case where the edge dominates the end.
2433  if (RootDominatesEnd)
2434  addToLeaderTable(Num, NotVal, Root.getEnd());
2435 
2436  continue;
2437  }
2438  }
2439 
2440  return Changed;
2441 }
2442 
2443 /// When calculating availability, handle an instruction
2444 /// by inserting it into the appropriate sets
2445 bool GVNPass::processInstruction(Instruction *I) {
2446  // Ignore dbg info intrinsics.
2447  if (isa<DbgInfoIntrinsic>(I))
2448  return false;
2449 
2450  // If the instruction can be easily simplified then do so now in preference
2451  // to value numbering it. Value numbering often exposes redundancies, for
2452  // example if it determines that %y is equal to %x then the instruction
2453  // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.
2454  const DataLayout &DL = I->getModule()->getDataLayout();
2455  if (Value *V = simplifyInstruction(I, {DL, TLI, DT, AC})) {
2456  bool Changed = false;
2457  if (!I->use_empty()) {
2458  // Simplification can cause a special instruction to become not special.
2459  // For example, devirtualization to a willreturn function.
2460  ICF->removeUsersOf(I);
2461  I->replaceAllUsesWith(V);
2462  Changed = true;
2463  }
2464  if (isInstructionTriviallyDead(I, TLI)) {
2465  markInstructionForDeletion(I);
2466  Changed = true;
2467  }
2468  if (Changed) {
2469  if (MD && V->getType()->isPtrOrPtrVectorTy())
2470  MD->invalidateCachedPointerInfo(V);
2471  ++NumGVNSimpl;
2472  return true;
2473  }
2474  }
2475 
2476  if (auto *Assume = dyn_cast<AssumeInst>(I))
2477  return processAssumeIntrinsic(Assume);
2478 
2479  if (LoadInst *Load = dyn_cast<LoadInst>(I)) {
2480  if (processLoad(Load))
2481  return true;
2482 
2483  unsigned Num = VN.lookupOrAdd(Load);
2484  addToLeaderTable(Num, Load, Load->getParent());
2485  return false;
2486  }
2487 
2488  // For conditional branches, we can perform simple conditional propagation on
2489  // the condition value itself.
2490  if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
2491  if (!BI->isConditional())
2492  return false;
2493 
2494  if (isa<Constant>(BI->getCondition()))
2495  return processFoldableCondBr(BI);
2496 
2497  Value *BranchCond = BI->getCondition();
2498  BasicBlock *TrueSucc = BI->getSuccessor(0);
2499  BasicBlock *FalseSucc = BI->getSuccessor(1);
2500  // Avoid multiple edges early.
2501  if (TrueSucc == FalseSucc)
2502  return false;
2503 
2504  BasicBlock *Parent = BI->getParent();
2505  bool Changed = false;
2506 
2507  Value *TrueVal = ConstantInt::getTrue(TrueSucc->getContext());
2508  BasicBlockEdge TrueE(Parent, TrueSucc);
2509  Changed |= propagateEquality(BranchCond, TrueVal, TrueE, true);
2510 
2512  BasicBlockEdge FalseE(Parent, FalseSucc);
2513  Changed |= propagateEquality(BranchCond, FalseVal, FalseE, true);
2514 
2515  return Changed;
2516  }
2517 
2518  // For switches, propagate the case values into the case destinations.
2519  if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
2520  Value *SwitchCond = SI->getCondition();
2521  BasicBlock *Parent = SI->getParent();
2522  bool Changed = false;
2523 
2524  // Remember how many outgoing edges there are to every successor.
2526  for (unsigned i = 0, n = SI->getNumSuccessors(); i != n; ++i)
2527  ++SwitchEdges[SI->getSuccessor(i)];
2528 
2529  for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
2530  i != e; ++i) {
2531  BasicBlock *Dst = i->getCaseSuccessor();
2532  // If there is only a single edge, propagate the case value into it.
2533  if (SwitchEdges.lookup(Dst) == 1) {
2534  BasicBlockEdge E(Parent, Dst);
2535  Changed |= propagateEquality(SwitchCond, i->getCaseValue(), E, true);
2536  }
2537  }
2538  return Changed;
2539  }
2540 
2541  // Instructions with void type don't return a value, so there's
2542  // no point in trying to find redundancies in them.
2543  if (I->getType()->isVoidTy())
2544  return false;
2545 
2546  uint32_t NextNum = VN.getNextUnusedValueNumber();
2547  unsigned Num = VN.lookupOrAdd(I);
2548 
2549  // Allocations are always uniquely numbered, so we can save time and memory
2550  // by fast failing them.
2551  if (isa<AllocaInst>(I) || I->isTerminator() || isa<PHINode>(I)) {
2552  addToLeaderTable(Num, I, I->getParent());
2553  return false;
2554  }
2555 
2556  // If the number we were assigned was a brand new VN, then we don't
2557  // need to do a lookup to see if the number already exists
2558  // somewhere in the domtree: it can't!
2559  if (Num >= NextNum) {
2560  addToLeaderTable(Num, I, I->getParent());
2561  return false;
2562  }
2563 
2564  // Perform fast-path value-number based elimination of values inherited from
2565  // dominators.
2566  Value *Repl = findLeader(I->getParent(), Num);
2567  if (!Repl) {
2568  // Failure, just remember this instance for future use.
2569  addToLeaderTable(Num, I, I->getParent());
2570  return false;
2571  } else if (Repl == I) {
2572  // If I was the result of a shortcut PRE, it might already be in the table
2573  // and the best replacement for itself. Nothing to do.
2574  return false;
2575  }
2576 
2577  // Remove it!
2579  if (MD && Repl->getType()->isPtrOrPtrVectorTy())
2580  MD->invalidateCachedPointerInfo(Repl);
2581  markInstructionForDeletion(I);
2582  return true;
2583 }
2584 
2585 /// runOnFunction - This is the main transformation entry point for a function.
2586 bool GVNPass::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
2587  const TargetLibraryInfo &RunTLI, AAResults &RunAA,
2588  MemoryDependenceResults *RunMD, LoopInfo *LI,
2589  OptimizationRemarkEmitter *RunORE, MemorySSA *MSSA) {
2590  AC = &RunAC;
2591  DT = &RunDT;
2592  VN.setDomTree(DT);
2593  TLI = &RunTLI;
2594  VN.setAliasAnalysis(&RunAA);
2595  MD = RunMD;
2596  ImplicitControlFlowTracking ImplicitCFT;
2597  ICF = &ImplicitCFT;
2598  this->LI = LI;
2599  VN.setMemDep(MD);
2600  ORE = RunORE;
2601  InvalidBlockRPONumbers = true;
2602  MemorySSAUpdater Updater(MSSA);
2603  MSSAU = MSSA ? &Updater : nullptr;
2604 
2605  bool Changed = false;
2606  bool ShouldContinue = true;
2607 
2609  // Merge unconditional branches, allowing PRE to catch more
2610  // optimization opportunities.
2612  bool removedBlock = MergeBlockIntoPredecessor(&BB, &DTU, LI, MSSAU, MD);
2613  if (removedBlock)
2614  ++NumGVNBlocks;
2615 
2616  Changed |= removedBlock;
2617  }
2618 
2619  unsigned Iteration = 0;
2620  while (ShouldContinue) {
2621  LLVM_DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n");
2622  (void) Iteration;
2623  ShouldContinue = iterateOnFunction(F);
2624  Changed |= ShouldContinue;
2625  ++Iteration;
2626  }
2627 
2628  if (isPREEnabled()) {
2629  // Fabricate val-num for dead-code in order to suppress assertion in
2630  // performPRE().
2631  assignValNumForDeadCode();
2632  bool PREChanged = true;
2633  while (PREChanged) {
2634  PREChanged = performPRE(F);
2635  Changed |= PREChanged;
2636  }
2637  }
2638 
2639  // FIXME: Should perform GVN again after PRE does something. PRE can move
2640  // computations into blocks where they become fully redundant. Note that
2641  // we can't do this until PRE's critical edge splitting updates memdep.
2642  // Actually, when this happens, we should just fully integrate PRE into GVN.
2643 
2644  cleanupGlobalSets();
2645  // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each
2646  // iteration.
2647  DeadBlocks.clear();
2648 
2649  if (MSSA && VerifyMemorySSA)
2650  MSSA->verifyMemorySSA();
2651 
2652  return Changed;
2653 }
2654 
2655 bool GVNPass::processBlock(BasicBlock *BB) {
2656  // FIXME: Kill off InstrsToErase by doing erasing eagerly in a helper function
2657  // (and incrementing BI before processing an instruction).
2658  assert(InstrsToErase.empty() &&
2659  "We expect InstrsToErase to be empty across iterations");
2660  if (DeadBlocks.count(BB))
2661  return false;
2662 
2663  // Clearing map before every BB because it can be used only for single BB.
2664  ReplaceOperandsWithMap.clear();
2665  bool ChangedFunction = false;
2666 
2667  // Since we may not have visited the input blocks of the phis, we can't
2668  // use our normal hash approach for phis. Instead, simply look for
2669  // obvious duplicates. The first pass of GVN will tend to create
2670  // identical phis, and the second or later passes can eliminate them.
2671  ChangedFunction |= EliminateDuplicatePHINodes(BB);
2672 
2673  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
2674  BI != BE;) {
2675  if (!ReplaceOperandsWithMap.empty())
2676  ChangedFunction |= replaceOperandsForInBlockEquality(&*BI);
2677  ChangedFunction |= processInstruction(&*BI);
2678 
2679  if (InstrsToErase.empty()) {
2680  ++BI;
2681  continue;
2682  }
2683 
2684  // If we need some instructions deleted, do it now.
2685  NumGVNInstr += InstrsToErase.size();
2686 
2687  // Avoid iterator invalidation.
2688  bool AtStart = BI == BB->begin();
2689  if (!AtStart)
2690  --BI;
2691 
2692  for (auto *I : InstrsToErase) {
2693  assert(I->getParent() == BB && "Removing instruction from wrong block?");
2694  LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n');
2695  salvageKnowledge(I, AC);
2696  salvageDebugInfo(*I);
2697  if (MD) MD->removeInstruction(I);
2698  if (MSSAU)
2699  MSSAU->removeMemoryAccess(I);
2700  LLVM_DEBUG(verifyRemoved(I));
2701  ICF->removeInstruction(I);
2702  I->eraseFromParent();
2703  }
2704  InstrsToErase.clear();
2705 
2706  if (AtStart)
2707  BI = BB->begin();
2708  else
2709  ++BI;
2710  }
2711 
2712  return ChangedFunction;
2713 }
2714 
2715 // Instantiate an expression in a predecessor that lacked it.
2716 bool GVNPass::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
2717  BasicBlock *Curr, unsigned int ValNo) {
2718  // Because we are going top-down through the block, all value numbers
2719  // will be available in the predecessor by the time we need them. Any
2720  // that weren't originally present will have been instantiated earlier
2721  // in this loop.
2722  bool success = true;
2723  for (unsigned i = 0, e = Instr->getNumOperands(); i != e; ++i) {
2724  Value *Op = Instr->getOperand(i);
2725  if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op))
2726  continue;
2727  // This could be a newly inserted instruction, in which case, we won't
2728  // find a value number, and should give up before we hurt ourselves.
2729  // FIXME: Rewrite the infrastructure to let it easier to value number
2730  // and process newly inserted instructions.
2731  if (!VN.exists(Op)) {
2732  success = false;
2733  break;
2734  }
2735  uint32_t TValNo =
2736  VN.phiTranslate(Pred, Curr, VN.lookup(Op), *this);
2737  if (Value *V = findLeader(Pred, TValNo)) {
2738  Instr->setOperand(i, V);
2739  } else {
2740  success = false;
2741  break;
2742  }
2743  }
2744 
2745  // Fail out if we encounter an operand that is not available in
2746  // the PRE predecessor. This is typically because of loads which
2747  // are not value numbered precisely.
2748  if (!success)
2749  return false;
2750 
2751  Instr->insertBefore(Pred->getTerminator());
2752  Instr->setName(Instr->getName() + ".pre");
2753  Instr->setDebugLoc(Instr->getDebugLoc());
2754 
2755  ICF->insertInstructionTo(Instr, Pred);
2756 
2757  unsigned Num = VN.lookupOrAdd(Instr);
2758  VN.add(Instr, Num);
2759 
2760  // Update the availability map to include the new instruction.
2761  addToLeaderTable(Num, Instr, Pred);
2762  return true;
2763 }
2764 
2765 bool GVNPass::performScalarPRE(Instruction *CurInst) {
2766  if (isa<AllocaInst>(CurInst) || CurInst->isTerminator() ||
2767  isa<PHINode>(CurInst) || CurInst->getType()->isVoidTy() ||
2768  CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() ||
2769  isa<DbgInfoIntrinsic>(CurInst))
2770  return false;
2771 
2772  // Don't do PRE on compares. The PHI would prevent CodeGenPrepare from
2773  // sinking the compare again, and it would force the code generator to
2774  // move the i1 from processor flags or predicate registers into a general
2775  // purpose register.
2776  if (isa<CmpInst>(CurInst))
2777  return false;
2778 
2779  // Don't do PRE on GEPs. The inserted PHI would prevent CodeGenPrepare from
2780  // sinking the addressing mode computation back to its uses. Extending the
2781  // GEP's live range increases the register pressure, and therefore it can
2782  // introduce unnecessary spills.
2783  //
2784  // This doesn't prevent Load PRE. PHI translation will make the GEP available
2785  // to the load by moving it to the predecessor block if necessary.
2786  if (isa<GetElementPtrInst>(CurInst))
2787  return false;
2788 
2789  if (auto *CallB = dyn_cast<CallBase>(CurInst)) {
2790  // We don't currently value number ANY inline asm calls.
2791  if (CallB->isInlineAsm())
2792  return false;
2793  // Don't do PRE on convergent calls.
2794  if (CallB->isConvergent())
2795  return false;
2796  }
2797 
2798  uint32_t ValNo = VN.lookup(CurInst);
2799 
2800  // Look for the predecessors for PRE opportunities. We're
2801  // only trying to solve the basic diamond case, where
2802  // a value is computed in the successor and one predecessor,
2803  // but not the other. We also explicitly disallow cases
2804  // where the successor is its own predecessor, because they're
2805  // more complicated to get right.
2806  unsigned NumWith = 0;
2807  unsigned NumWithout = 0;
2808  BasicBlock *PREPred = nullptr;
2809  BasicBlock *CurrentBlock = CurInst->getParent();
2810 
2811  // Update the RPO numbers for this function.
2812  if (InvalidBlockRPONumbers)
2813  assignBlockRPONumber(*CurrentBlock->getParent());
2814 
2816  for (BasicBlock *P : predecessors(CurrentBlock)) {
2817  // We're not interested in PRE where blocks with predecessors that are
2818  // not reachable.
2819  if (!DT->isReachableFromEntry(P)) {
2820  NumWithout = 2;
2821  break;
2822  }
2823  // It is not safe to do PRE when P->CurrentBlock is a loop backedge, and
2824  // when CurInst has operand defined in CurrentBlock (so it may be defined
2825  // by phi in the loop header).
2826  assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) &&
2827  "Invalid BlockRPONumber map.");
2828  if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock] &&
2829  llvm::any_of(CurInst->operands(), [&](const Use &U) {
2830  if (auto *Inst = dyn_cast<Instruction>(U.get()))
2831  return Inst->getParent() == CurrentBlock;
2832  return false;
2833  })) {
2834  NumWithout = 2;
2835  break;
2836  }
2837 
2838  uint32_t TValNo = VN.phiTranslate(P, CurrentBlock, ValNo, *this);
2839  Value *predV = findLeader(P, TValNo);
2840  if (!predV) {
2841  predMap.push_back(std::make_pair(static_cast<Value *>(nullptr), P));
2842  PREPred = P;
2843  ++NumWithout;
2844  } else if (predV == CurInst) {
2845  /* CurInst dominates this predecessor. */
2846  NumWithout = 2;
2847  break;
2848  } else {
2849  predMap.push_back(std::make_pair(predV, P));
2850  ++NumWith;
2851  }
2852  }
2853 
2854  // Don't do PRE when it might increase code size, i.e. when
2855  // we would need to insert instructions in more than one pred.
2856  if (NumWithout > 1 || NumWith == 0)
2857  return false;
2858 
2859  // We may have a case where all predecessors have the instruction,
2860  // and we just need to insert a phi node. Otherwise, perform
2861  // insertion.
2862  Instruction *PREInstr = nullptr;
2863 
2864  if (NumWithout != 0) {
2865  if (!isSafeToSpeculativelyExecute(CurInst)) {
2866  // It is only valid to insert a new instruction if the current instruction
2867  // is always executed. An instruction with implicit control flow could
2868  // prevent us from doing it. If we cannot speculate the execution, then
2869  // PRE should be prohibited.
2870  if (ICF->isDominatedByICFIFromSameBlock(CurInst))
2871  return false;
2872  }
2873 
2874  // Don't do PRE across indirect branch.
2875  if (isa<IndirectBrInst>(PREPred->getTerminator()))
2876  return false;
2877 
2878  // Don't do PRE across callbr.
2879  // FIXME: Can we do this across the fallthrough edge?
2880  if (isa<CallBrInst>(PREPred->getTerminator()))
2881  return false;
2882 
2883  // We can't do PRE safely on a critical edge, so instead we schedule
2884  // the edge to be split and perform the PRE the next time we iterate
2885  // on the function.
2886  unsigned SuccNum = GetSuccessorNumber(PREPred, CurrentBlock);
2887  if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {
2888  toSplit.push_back(std::make_pair(PREPred->getTerminator(), SuccNum));
2889  return false;
2890  }
2891  // We need to insert somewhere, so let's give it a shot
2892  PREInstr = CurInst->clone();
2893  if (!performScalarPREInsertion(PREInstr, PREPred, CurrentBlock, ValNo)) {
2894  // If we failed insertion, make sure we remove the instruction.
2895  LLVM_DEBUG(verifyRemoved(PREInstr));
2896  PREInstr->deleteValue();
2897  return false;
2898  }
2899  }
2900 
2901  // Either we should have filled in the PRE instruction, or we should
2902  // not have needed insertions.
2903  assert(PREInstr != nullptr || NumWithout == 0);
2904 
2905  ++NumGVNPRE;
2906 
2907  // Create a PHI to make the value available in this block.
2908  PHINode *Phi =
2909  PHINode::Create(CurInst->getType(), predMap.size(),
2910  CurInst->getName() + ".pre-phi", &CurrentBlock->front());
2911  for (unsigned i = 0, e = predMap.size(); i != e; ++i) {
2912  if (Value *V = predMap[i].first) {
2913  // If we use an existing value in this phi, we have to patch the original
2914  // value because the phi will be used to replace a later value.
2915  patchReplacementInstruction(CurInst, V);
2916  Phi->addIncoming(V, predMap[i].second);
2917  } else
2918  Phi->addIncoming(PREInstr, PREPred);
2919  }
2920 
2921  VN.add(Phi, ValNo);
2922  // After creating a new PHI for ValNo, the phi translate result for ValNo will
2923  // be changed, so erase the related stale entries in phi translate cache.
2924  VN.eraseTranslateCacheEntry(ValNo, *CurrentBlock);
2925  addToLeaderTable(ValNo, Phi, CurrentBlock);
2926  Phi->setDebugLoc(CurInst->getDebugLoc());
2927  CurInst->replaceAllUsesWith(Phi);
2928  if (MD && Phi->getType()->isPtrOrPtrVectorTy())
2929  MD->invalidateCachedPointerInfo(Phi);
2930  VN.erase(CurInst);
2931  removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
2932 
2933  LLVM_DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
2934  if (MD)
2935  MD->removeInstruction(CurInst);
2936  if (MSSAU)
2937  MSSAU->removeMemoryAccess(CurInst);
2938  LLVM_DEBUG(verifyRemoved(CurInst));
2939  // FIXME: Intended to be markInstructionForDeletion(CurInst), but it causes
2940  // some assertion failures.
2941  ICF->removeInstruction(CurInst);
2942  CurInst->eraseFromParent();
2943  ++NumGVNInstr;
2944 
2945  return true;
2946 }
2947 
2948 /// Perform a purely local form of PRE that looks for diamond
2949 /// control flow patterns and attempts to perform simple PRE at the join point.
2950 bool GVNPass::performPRE(Function &F) {
2951  bool Changed = false;
2952  for (BasicBlock *CurrentBlock : depth_first(&F.getEntryBlock())) {
2953  // Nothing to PRE in the entry block.
2954  if (CurrentBlock == &F.getEntryBlock())
2955  continue;
2956 
2957  // Don't perform PRE on an EH pad.
2958  if (CurrentBlock->isEHPad())
2959  continue;
2960 
2961  for (BasicBlock::iterator BI = CurrentBlock->begin(),
2962  BE = CurrentBlock->end();
2963  BI != BE;) {
2964  Instruction *CurInst = &*BI++;
2965  Changed |= performScalarPRE(CurInst);
2966  }
2967  }
2968 
2969  if (splitCriticalEdges())
2970  Changed = true;
2971 
2972  return Changed;
2973 }
2974 
2975 /// Split the critical edge connecting the given two blocks, and return
2976 /// the block inserted to the critical edge.
2977 BasicBlock *GVNPass::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
2978  // GVN does not require loop-simplify, do not try to preserve it if it is not
2979  // possible.
2981  Pred, Succ,
2982  CriticalEdgeSplittingOptions(DT, LI, MSSAU).unsetPreserveLoopSimplify());
2983  if (BB) {
2984  if (MD)
2985  MD->invalidateCachedPredecessors();
2986  InvalidBlockRPONumbers = true;
2987  }
2988  return BB;
2989 }
2990 
2991 /// Split critical edges found during the previous
2992 /// iteration that may enable further optimization.
2993 bool GVNPass::splitCriticalEdges() {
2994  if (toSplit.empty())
2995  return false;
2996 
2997  bool Changed = false;
2998  do {
2999  std::pair<Instruction *, unsigned> Edge = toSplit.pop_back_val();
3000  Changed |= SplitCriticalEdge(Edge.first, Edge.second,
3001  CriticalEdgeSplittingOptions(DT, LI, MSSAU)) !=
3002  nullptr;
3003  } while (!toSplit.empty());
3004  if (Changed) {
3005  if (MD)
3006  MD->invalidateCachedPredecessors();
3007  InvalidBlockRPONumbers = true;
3008  }
3009  return Changed;
3010 }
3011 
3012 /// Executes one iteration of GVN
3013 bool GVNPass::iterateOnFunction(Function &F) {
3014  cleanupGlobalSets();
3015 
3016  // Top-down walk of the dominator tree
3017  bool Changed = false;
3018  // Needed for value numbering with phi construction to work.
3019  // RPOT walks the graph in its constructor and will not be invalidated during
3020  // processBlock.
3022 
3023  for (BasicBlock *BB : RPOT)
3024  Changed |= processBlock(BB);
3025 
3026  return Changed;
3027 }
3028 
3029 void GVNPass::cleanupGlobalSets() {
3030  VN.clear();
3031  LeaderTable.clear();
3032  BlockRPONumber.clear();
3033  TableAllocator.Reset();
3034  ICF->clear();
3035  InvalidBlockRPONumbers = true;
3036 }
3037 
3038 /// Verify that the specified instruction does not occur in our
3039 /// internal data structures.
3040 void GVNPass::verifyRemoved(const Instruction *Inst) const {
3041  VN.verifyRemoved(Inst);
3042 
3043  // Walk through the value number scope to make sure the instruction isn't
3044  // ferreted away in it.
3045  for (const auto &I : LeaderTable) {
3046  const LeaderTableEntry *Node = &I.second;
3047  assert(Node->Val != Inst && "Inst still in value numbering scope!");
3048 
3049  while (Node->Next) {
3050  Node = Node->Next;
3051  assert(Node->Val != Inst && "Inst still in value numbering scope!");
3052  }
3053  }
3054 }
3055 
3056 /// BB is declared dead, which implied other blocks become dead as well. This
3057 /// function is to add all these blocks to "DeadBlocks". For the dead blocks'
3058 /// live successors, update their phi nodes by replacing the operands
3059 /// corresponding to dead blocks with UndefVal.
3060 void GVNPass::addDeadBlock(BasicBlock *BB) {
3063 
3064  NewDead.push_back(BB);
3065  while (!NewDead.empty()) {
3066  BasicBlock *D = NewDead.pop_back_val();
3067  if (DeadBlocks.count(D))
3068  continue;
3069 
3070  // All blocks dominated by D are dead.
3072  DT->getDescendants(D, Dom);
3073  DeadBlocks.insert(Dom.begin(), Dom.end());
3074 
3075  // Figure out the dominance-frontier(D).
3076  for (BasicBlock *B : Dom) {
3077  for (BasicBlock *S : successors(B)) {
3078  if (DeadBlocks.count(S))
3079  continue;
3080 
3081  bool AllPredDead = true;
3082  for (BasicBlock *P : predecessors(S))
3083  if (!DeadBlocks.count(P)) {
3084  AllPredDead = false;
3085  break;
3086  }
3087 
3088  if (!AllPredDead) {
3089  // S could be proved dead later on. That is why we don't update phi
3090  // operands at this moment.
3091  DF.insert(S);
3092  } else {
3093  // While S is not dominated by D, it is dead by now. This could take
3094  // place if S already have a dead predecessor before D is declared
3095  // dead.
3096  NewDead.push_back(S);
3097  }
3098  }
3099  }
3100  }
3101 
3102  // For the dead blocks' live successors, update their phi nodes by replacing
3103  // the operands corresponding to dead blocks with UndefVal.
3104  for (BasicBlock *B : DF) {
3105  if (DeadBlocks.count(B))
3106  continue;
3107 
3108  // First, split the critical edges. This might also create additional blocks
3109  // to preserve LoopSimplify form and adjust edges accordingly.
3111  for (BasicBlock *P : Preds) {
3112  if (!DeadBlocks.count(P))
3113  continue;
3114 
3115  if (llvm::is_contained(successors(P), B) &&
3116  isCriticalEdge(P->getTerminator(), B)) {
3117  if (BasicBlock *S = splitCriticalEdges(P, B))
3118  DeadBlocks.insert(P = S);
3119  }
3120  }
3121 
3122  // Now poison the incoming values from the dead predecessors.
3123  for (BasicBlock *P : predecessors(B)) {
3124  if (!DeadBlocks.count(P))
3125  continue;
3126  for (PHINode &Phi : B->phis()) {
3128  if (MD)
3129  MD->invalidateCachedPointerInfo(&Phi);
3130  }
3131  }
3132  }
3133 }
3134 
3135 // If the given branch is recognized as a foldable branch (i.e. conditional
3136 // branch with constant condition), it will perform following analyses and
3137 // transformation.
3138 // 1) If the dead out-coming edge is a critical-edge, split it. Let
3139 // R be the target of the dead out-coming edge.
3140 // 1) Identify the set of dead blocks implied by the branch's dead outcoming
3141 // edge. The result of this step will be {X| X is dominated by R}
3142 // 2) Identify those blocks which haves at least one dead predecessor. The
3143 // result of this step will be dominance-frontier(R).
3144 // 3) Update the PHIs in DF(R) by replacing the operands corresponding to
3145 // dead blocks with "UndefVal" in an hope these PHIs will optimized away.
3146 //
3147 // Return true iff *NEW* dead code are found.
3148 bool GVNPass::processFoldableCondBr(BranchInst *BI) {
3149  if (!BI || BI->isUnconditional())
3150  return false;
3151 
3152  // If a branch has two identical successors, we cannot declare either dead.
3153  if (BI->getSuccessor(0) == BI->getSuccessor(1))
3154  return false;
3155 
3156  ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
3157  if (!Cond)
3158  return false;
3159 
3160  BasicBlock *DeadRoot =
3161  Cond->getZExtValue() ? BI->getSuccessor(1) : BI->getSuccessor(0);
3162  if (DeadBlocks.count(DeadRoot))
3163  return false;
3164 
3165  if (!DeadRoot->getSinglePredecessor())
3166  DeadRoot = splitCriticalEdges(BI->getParent(), DeadRoot);
3167 
3168  addDeadBlock(DeadRoot);
3169  return true;
3170 }
3171 
3172 // performPRE() will trigger assert if it comes across an instruction without
3173 // associated val-num. As it normally has far more live instructions than dead
3174 // instructions, it makes more sense just to "fabricate" a val-number for the
3175 // dead code than checking if instruction involved is dead or not.
3176 void GVNPass::assignValNumForDeadCode() {
3177  for (BasicBlock *BB : DeadBlocks) {
3178  for (Instruction &Inst : *BB) {
3179  unsigned ValNum = VN.lookupOrAdd(&Inst);
3180  addToLeaderTable(ValNum, &Inst, BB);
3181  }
3182  }
3183 }
3184 
3186 public:
3187  static char ID; // Pass identification, replacement for typeid
3188 
3189  explicit GVNLegacyPass(bool NoMemDepAnalysis = !GVNEnableMemDep)
3190  : FunctionPass(ID), Impl(GVNOptions().setMemDep(!NoMemDepAnalysis)) {
3192  }
3193 
3194  bool runOnFunction(Function &F) override {
3195  if (skipFunction(F))
3196  return false;
3197 
3198  auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
3199 
3200  auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
3201  return Impl.runImpl(
3202  F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
3203  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
3204  getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
3205  getAnalysis<AAResultsWrapperPass>().getAAResults(),
3206  Impl.isMemDepEnabled()
3207  ? &getAnalysis<MemoryDependenceWrapperPass>().getMemDep()
3208  : nullptr,
3209  LIWP ? &LIWP->getLoopInfo() : nullptr,
3210  &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(),
3211  MSSAWP ? &MSSAWP->getMSSA() : nullptr);
3212  }
3213 
3214  void getAnalysisUsage(AnalysisUsage &AU) const override {
3219  if (Impl.isMemDepEnabled())
3228  }
3229 
3230 private:
3231  GVNPass Impl;
3232 };
3233 
3234 char GVNLegacyPass::ID = 0;
3235 
3236 INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)
3245 
3246 // The public interface to this file...
3247 FunctionPass *llvm::createGVNPass(bool NoMemDepAnalysis) {
3248  return new GVNLegacyPass(NoMemDepAnalysis);
3249 }
llvm::GVNOptions
A set of parameters to control various transforms performed by GVN pass.
Definition: GVN.h:73
llvm::coverage::coveragemap_error::success
@ success
i
i
Definition: README.txt:29
llvm::SSAUpdater::Initialize
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
Definition: SSAUpdater.cpp:52
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::MemoryDependenceResults::removeInstruction
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
Definition: MemoryDependenceAnalysis.cpp:1502
llvm::VNCoercion::analyzeLoadFromClobberingMemInst
int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr, MemIntrinsic *DepMI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the memory int...
Definition: VNCoercion.cpp:356
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:160
AssumptionCache.h
llvm::BinaryOpIntrinsic::getBinaryOp
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
Definition: IntrinsicInst.cpp:657
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1303
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:299
llvm::OptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: DiagnosticInfo.h:735
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:60
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:849
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:494
llvm::ImplicitControlFlowTracking
This class allows to keep track on instructions with implicit control flow.
Definition: InstructionPrecedenceTracking.h:99
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:35
llvm::GVNPass::Expression::hash_value
friend hash_code hash_value(const Expression &Value)
Definition: GVN.cpp:146
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::GVNPass::Expression::type
Type * type
Definition: GVN.cpp:129
llvm::NonLocalDepEntry
This is an entry in the NonLocalDepInfo cache.
Definition: MemoryDependenceAnalysis.h:199
llvm::MemorySSA::verifyMemorySSA
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1906
llvm::AArch64CC::AL
@ AL
Definition: AArch64BaseInfo.h:269
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::GVNPass::ValueTable::clear
void clear()
Remove all entries from the ValueTable.
Definition: GVN.cpp:662
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::VNCoercion::getStoreValueForLoad
Value * getStoreValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &DL)
If analyzeLoadFromClobberingStore returned an offset, this function can be used to actually perform t...
Definition: VNCoercion.cpp:448
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
type
Metadata.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4688
llvm::PHITransAddr
PHITransAddr - An address value which tracks and handles phi translation.
Definition: PHITransAddr.h:35
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
GVNEnableLoadPRE
static cl::opt< bool > GVNEnableLoadPRE("enable-load-pre", cl::init(true))
llvm::PassInfoMixin< GVNPass >
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::GVNPass::ValueTable::lookupOrAdd
uint32_t lookupOrAdd(Value *V)
lookup_or_add - Returns the value number for the specified value, assigning it a new number if it did...
Definition: GVN.cpp:562
llvm::GVNPass::ValueTable::exists
bool exists(Value *V) const
Returns true if a value number exists for the specified value.
Definition: GVN.cpp:556
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:60
getFunction
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:233
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:199
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
llvm::ARM_MB::LD
@ LD
Definition: ARMBaseInfo.h:72
llvm::GVNPass::ValueTable::lookup
uint32_t lookup(Value *V, bool Verify=true) const
Returns the value number of the specified value.
Definition: GVN.cpp:641
llvm::BinaryOpIntrinsic::getRHS
Value * getRHS() const
Definition: IntrinsicInst.h:664
llvm::SmallVector< uint32_t, 4 >
impliesEquivalanceIfTrue
static bool impliesEquivalanceIfTrue(CmpInst *Cmp)
Definition: GVN.cpp:1828
Statistic.h
llvm::BinaryOpIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:663
llvm::CmpInst::makeCmpResultType
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1044
llvm::GVNPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVN.cpp:716
MapVector.h
DomTreeUpdater.h
llvm::SmallDenseMap
Definition: DenseMap.h:882
llvm::gvn::AvailableValueInBlock::MaterializeAdjustedValue
Value * MaterializeAdjustedValue(LoadInst *Load, GVNPass &gvn) const
Emit code at the end of this block to adjust the value defined here to the specified type.
Definition: GVN.cpp:299
ValueTracking.h
llvm::isAssumeWithEmptyBundle
bool isAssumeWithEmptyBundle(AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
Definition: AssumeBundleQueries.cpp:125
Local.h
OptimizationRemarkEmitter.h
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:83
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::AssumeInst
This represents the llvm.assume intrinsic.
Definition: IntrinsicInst.h:1429
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:652
llvm::DenseMapIterator
Definition: DenseMap.h:57
llvm::gvn::AvailableValue::isCoercedLoadValue
bool isCoercedLoadValue() const
Definition: GVN.cpp:237
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::SplitCriticalEdge
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
Definition: BreakCriticalEdges.cpp:101
Module.h
MemoryBuiltins.h
ConstructSSAForLoadSet
static Value * ConstructSSAForLoadSet(LoadInst *Load, SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, GVNPass &gvn)
Given a set of loads specified by ValuesPerBlock, construct SSA form, allowing us to eliminate Load.
Definition: GVN.cpp:911
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1287
llvm::BasicBlockEdge
Definition: Dominators.h:98
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::Instruction::comesBefore
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
Definition: Instruction.cpp:110
llvm::ExtractValueInst::indices
iterator_range< idx_iterator > indices() const
Definition: Instructions.h:2449
llvm::gvn::AvailableValue::getMI
static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset=0)
Definition: GVN.cpp:204
llvm::MemIntrinsic
This is the common base class for memset/memcpy/memmove.
Definition: IntrinsicInst.h:957
llvm::Optional
Definition: APInt.h:33
llvm::MemDepResult
A memory dependence query can return one of three different answers.
Definition: MemoryDependenceAnalysis.h:38
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
reportMayClobberedLoad
static void reportMayClobberedLoad(LoadInst *Load, MemDepResult DepInfo, DominatorTree *DT, OptimizationRemarkEmitter *ORE)
Try to locate the three instruction involved in a missed load-elimination case that is due to an inte...
Definition: GVN.cpp:1042
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:62
Hashing.h
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::createGVNPass
FunctionPass * createGVNPass(bool NoMemDepAnalysis=false)
Create a legacy GVN pass.
Definition: GVN.cpp:3247
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
llvm::isCriticalEdge
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:261
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
MemoryDependenceAnalysis.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:260
llvm::DenseMapInfo< GVNPass::Expression >::isEqual
static bool isEqual(const GVNPass::Expression &LHS, const GVNPass::Expression &RHS)
Definition: GVN.cpp:165
llvm::hash_value
hash_code hash_value(const APFloat &Arg)
See friend declarations above.
Definition: APFloat.cpp:4828
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:237
llvm::GVNPass::ValueTable::eraseTranslateCacheEntry
void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock)
Erase stale entry from phiTranslate cache so phiTranslate can be computed again.
Definition: GVN.cpp:2216
Use.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::gvn::GVNLegacyPass
Definition: GVN.cpp:3185
DepthFirstIterator.h
llvm::gvn::AvailableValue::ValType
ValType
Definition: GVN.cpp:178
llvm::Instruction::mayHaveSideEffects
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.cpp:695
llvm::gvn::AvailableValueInBlock::AV
AvailableValue AV
AV - The actual available value.
Definition: GVN.cpp:275
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:240
llvm::SwitchInst::CaseIteratorImpl
Definition: Instructions.h:3271
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
Verify
ppc ctr loops PowerPC CTR Loops Verify
Definition: PPCCTRLoopsVerify.cpp:77
AliasAnalysis.h
llvm::gvn::AvailableValueInBlock
Represents an AvailableValue which can be rematerialized at the end of the associated BasicBlock.
Definition: GVN.cpp:270
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
PHITransAddr.h
Instruction.h
CommandLine.h
hasUsersIn
static bool hasUsersIn(Value *V, BasicBlock *BB)
Definition: GVN.cpp:1881
llvm::gvn::AvailableValue::getLoad
static AvailableValue getLoad(LoadInst *Load, unsigned Offset=0)
Definition: GVN.cpp:212
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:777
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:157
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1755
llvm::SelectInst::getCondition
const Value * getCondition() const
Definition: Instructions.h:1771
llvm::GVNPass::ValueTable::operator=
ValueTable & operator=(const ValueTable &Arg)
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:998
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
L2
add sub stmia L5 ldr L2
Definition: README.txt:201
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
isZero
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:524
llvm::AAResults
Definition: AliasAnalysis.h:511
llvm::GVNPass::ValueTable::~ValueTable
~ValueTable()
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:667
llvm::gvn::AvailableValueInBlock::get
static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV)
Definition: GVN.cpp:277
AvailabilityState::Available
@ Available
We know the block is fully available. This is a fixpoint.
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
InstrTypes.h
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
llvm::ExtractValueInst::getNumIndices
unsigned getNumIndices() const
Definition: Instructions.h:2467
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
runImpl
static bool runImpl(const TargetLibraryInfo &TLI, Function &F)
Definition: ReplaceWithVeclib.cpp:176
AssumeBundleQueries.h
TargetLibraryInfo.h
llvm::CriticalEdgeSplittingOptions
Option class for critical edge splitting.
Definition: BasicBlockUtils.h:142
AssumeBundleBuilder.h
false
Definition: StackSlotColoring.cpp:141
IsValueFullyAvailableInBlock
static bool IsValueFullyAvailableInBlock(BasicBlock *BB, DenseMap< BasicBlock *, AvailabilityState > &FullyAvailableBlocks)
Return true if we can prove that the value we're analyzing is fully available in the specified block.
Definition: GVN.cpp:793
llvm::isPotentiallyReachable
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Definition: CFG.cpp:232
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::VNCoercion
Definition: VNCoercion.h:34
llvm::Instruction
Definition: Instruction.h:42
llvm::DenseMapInfo< GVNPass::Expression >::getTombstoneKey
static GVNPass::Expression getTombstoneKey()
Definition: GVN.cpp:157
llvm::gvn::AvailableValue
Represents a particular available value that we know how to materialize.
Definition: GVN.cpp:177
llvm::GVNPass::isLoadInLoopPREEnabled
bool isLoadInLoopPREEnabled() const
Definition: GVN.cpp:703
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:372
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1777
llvm::gvn::AvailableValue::get
static AvailableValue get(Value *V, unsigned Offset=0)
Definition: GVN.cpp:196
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:928
GVN.h
llvm::AArch64CC::PL
@ PL
Definition: AArch64BaseInfo.h:260
GVNEnableMemDep
static cl::opt< bool > GVNEnableMemDep("enable-gvn-memdep", cl::init(true))
DebugLoc.h
SmallPtrSet.h
PatternMatch.h
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:209
llvm::GVNPass::isPREEnabled
bool isPREEnabled() const
Definition: GVN.cpp:695
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
reportLoadElim
static void reportLoadElim(LoadInst *Load, Value *AvailableValue, OptimizationRemarkEmitter *ORE)
Definition: GVN.cpp:1726
llvm::gvn::AvailableValue::getSelect
static AvailableValue getSelect(SelectInst *Sel)
Definition: GVN.cpp:228
llvm::gvn::GVNLegacyPass::GVNLegacyPass
GVNLegacyPass(bool NoMemDepAnalysis=!GVNEnableMemDep)
Definition: GVN.cpp:3189
DEBUG_TYPE
#define DEBUG_TYPE
Definition: GVN.cpp:86
llvm::None
const NoneType None
Definition: None.h:24
findDominatingLoad
static LoadInst * findDominatingLoad(Value *Ptr, Type *LoadTy, SelectInst *Sel, DominatorTree &DT)
Definition: GVN.cpp:954
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
DF
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
llvm::GVNPass::ValueTable::add
void add(Value *V, uint32_t num)
add - Insert a value into the table with a specified value number.
Definition: GVN.cpp:446
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
tryToConvertLoadOfPtrSelect
static Optional< AvailableValue > tryToConvertLoadOfPtrSelect(BasicBlock *DepBB, BasicBlock::iterator End, Value *Address, Type *LoadTy, DominatorTree &DT, AAResults *AA)
Check if a load from pointer-select Address in DepBB can be converted to a value select.
Definition: GVN.cpp:1110
LoopInfo.h
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3167
llvm::gvn::AvailableValue::MaterializeAdjustedValue
Value * MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt, GVNPass &gvn) const
Emit code at the specified insertion point to adjust the value defined here to the specified type.
Definition: GVN.cpp:965
llvm::VNCoercion::getMemInstValueForLoad
Value * getMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &DL)
If analyzeLoadFromClobberingMemInst returned an offset, this function can be used to actually perform...
Definition: VNCoercion.cpp:576
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:191
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::gvn::AvailableValue::getCoercedLoadValue
LoadInst * getCoercedLoadValue() const
Definition: GVN.cpp:247
llvm::GVNPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: GVN.cpp:744
BasicBlock.h
llvm::cl::opt< bool >
llvm::MemDepResult::getInst
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
Definition: MemoryDependenceAnalysis.h:166
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
llvm::GVNPass::getDominatorTree
DominatorTree & getDominatorTree() const
Definition: GVN.h:137
llvm::GVNPass::isLoadPRESplitBackedgeEnabled
bool isLoadPRESplitBackedgeEnabled() const
Definition: GVN.cpp:707
VI
@ VI
Definition: SIInstrInfo.cpp:7824
llvm::getInitialValueOfAllocation
Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
Definition: MemoryBuiltins.cpp:422
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::pdb::PDB_ColorItem::Address
@ Address
llvm::gvn::AvailableValue::isMemIntrinValue
bool isMemIntrinValue() const
Definition: GVN.cpp:238
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
llvm::GCRelocateInst
Represents calls to the gc.relocate intrinsic.
Definition: IntrinsicInst.h:1388
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:413
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:468
MaxBBSpeculations
static cl::opt< uint32_t > MaxBBSpeculations("gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::desc("Max number of blocks we're willing to speculate on (and recurse " "into) when deducing if a value is fully available or not in GVN " "(default = 600)"))
llvm::GVNPass::getMemDep
MemoryDependenceResults & getMemDep() const
Definition: GVN.h:139
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::PatternMatch::m_LogicalOr
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
Definition: PatternMatch.h:2549
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::SSAUpdater::GetValueInMiddleOfBlock
Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block.
Definition: SSAUpdater.cpp:97
llvm::gvn::GVNLegacyPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: GVN.cpp:3194
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::GVNPass::ValueTable::erase
void erase(Value *v)
Remove a value from the value numbering.
Definition: GVN.cpp:674
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2801
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:716
AvailabilityState
AvailabilityState
Definition: GVN.cpp:773
llvm::ExtractValueInst::idx_begin
idx_iterator idx_begin() const
Definition: Instructions.h:2447
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemDepResult::isClobber
bool isClobber() const
Tests if this MemDepResult represents a query that is an instruction clobber dependency.
Definition: MemoryDependenceAnalysis.h:140
llvm::GVNPass::Expression::varargs
SmallVector< uint32_t, 4 > varargs
Definition: GVN.cpp:130
VNCoercion.h
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:916
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:618
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1682
llvm::simplifyInstruction
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6486
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:364
patchAndReplaceAllUsesWith
static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl)
Definition: GVN.cpp:2026
GVNEnablePRE
static cl::opt< bool > GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden)
llvm::gvn::AvailableValueInBlock::getUndef
static AvailableValueInBlock getUndef(BasicBlock *BB)
Definition: GVN.cpp:289
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:215
llvm::GVNPass::isMemDepEnabled
bool isMemDepEnabled() const
Definition: GVN.cpp:712
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
AvailabilityState::Unavailable
@ Unavailable
We know the block is not fully available. This is a fixpoint.
llvm::PHINode::setIncomingValueForBlock
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
Definition: Instructions.h:2843
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::OptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Definition: OptimizationRemarkEmitter.cpp:77
llvm::GVNPass::ValueTable::lookupOrAddCmp
uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, Value *LHS, Value *RHS)
Returns the value number of the given comparison, assigning it a new number if it did not have one be...
Definition: GVN.cpp:654
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1724
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
llvm::salvageKnowledge
void salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Definition: AssumeBundleBuilder.cpp:293
llvm::GVNPass::ValueTable::ValueTable
ValueTable()
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:948
llvm::replaceDominatedUsesWith
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of 'From' with 'To' if that use is dominated by the given edge.
Definition: Local.cpp:2732
llvm::SmallSet::erase
bool erase(const T &V)
Definition: SmallSet.h:209
llvm::Value::printAsOperand
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:4673
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3164
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::GetSuccessorNumber
unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
Definition: CFG.cpp:79
CFG.h
llvm::Expression
Class representing an expression and its matching format.
Definition: FileCheckImpl.h:237
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:862
llvm::GVNPass::isLoadPREEnabled
bool isLoadPREEnabled() const
Definition: GVN.cpp:699
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::ArrayRef< int >
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:395
llvm::LoopInfo
Definition: LoopInfo.h:1102
GVNEnableLoadInLoopPRE
static cl::opt< bool > GVNEnableLoadInLoopPRE("enable-load-in-loop-pre", cl::init(true))
llvm::MergeBlockIntoPredecessor
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
Definition: BasicBlockUtils.cpp:178
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1624
llvm::BasicBlockEdge::getEnd
const BasicBlock * getEnd() const
Definition: Dominators.h:116
llvm::GVNPass::Expression::Expression
Expression(uint32_t o=~2U)
Definition: GVN.cpp:132
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
isOnlyReachableViaThisEdge
static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E, DominatorTree *DT)
There is an edge from 'Src' to 'Dst'.
Definition: GVN.cpp:2253
llvm::GVNPass::ValueTable::verifyRemoved
void verifyRemoved(const Value *) const
verifyRemoved - Verify that the value is removed from all internal data structures.
Definition: GVN.cpp:684
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:529
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:845
uint32_t
Compiler.h
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1823
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::ConstantInt::isMinusOne
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:206
llvm::GVNPass::ValueTable
This class holds the mapping between values and value numbers.
Definition: GVN.h:150
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::gvn::AvailableValue::getMemIntrinValue
MemIntrinsic * getMemIntrinValue() const
Definition: GVN.cpp:252
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
llvm::pred_empty
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
llvm::gvn::AvailableValue::getSelectValue
SelectInst * getSelectValue() const
Definition: GVN.cpp:257
llvm::Type::isPtrOrPtrVectorTy
bool isPtrOrPtrVectorTy() const
Return true if this is a pointer type or a vector of pointer types.
Definition: Type.h:224
llvm::DominatorTreeBase::properlyDominates
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Definition: GenericDomTree.h:392
llvm::WithOverflowInst
Represents an op.with.overflow intrinsic.
Definition: IntrinsicInst.h:677
SSAUpdater.h
llvm::Instruction::mayReadFromMemory
bool mayReadFromMemory() const
Return true if this instruction may read memory.
Definition: Instruction.cpp:576
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:182
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::SSAUpdater::HasValueForBlock
bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
Definition: SSAUpdater.cpp:61
llvm::VNCoercion::getLoadValueForLoad
Value * getLoadValueForLoad(LoadInst *SrcVal, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &DL)
If analyzeLoadFromClobberingLoad returned an offset, this function can be used to actually perform th...
Definition: VNCoercion.cpp:468
llvm::gvn::AvailableValue::isUndefValue
bool isUndefValue() const
Definition: GVN.cpp:239
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:883
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:309
liesBetween
static bool liesBetween(const Instruction *From, Instruction *Between, const Instruction *To, DominatorTree *DT)
Assuming To can be reached from both From and Between, does Between lie on every path from From to To...
Definition: GVN.cpp:1031
llvm::gvn::AvailableValue::isSimpleValue
bool isSimpleValue() const
Definition: GVN.cpp:236
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
llvm::EliminateDuplicatePHINodes
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
Definition: Local.cpp:1297
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
Attributes.h
llvm::MemoryDependenceResults
Provides a lazy, caching interface for making common memory aliasing information queries,...
Definition: MemoryDependenceAnalysis.h:265
Constant.h
llvm::OptimizationRemarkEmitterWrapperPass
OptimizationRemarkEmitter legacy analysis pass.
Definition: OptimizationRemarkEmitter.h:146
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:876
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
llvm::MemoryDependenceWrapperPass
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.
Definition: MemoryDependenceAnalysis.h:526
llvm::DenseMapInfo< GVNPass::Expression >::getEmptyKey
static GVNPass::Expression getEmptyKey()
Definition: GVN.cpp:156
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::PHINode::Create
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Definition: Instructions.h:2693
llvm::ore::setExtraArgs
DiagnosticInfoOptimizationBase::setExtraArgs setExtraArgs
Definition: OptimizationRemarkEmitter.h:138
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:152
llvm::X86::FirstMacroFusionInstKind::Cmp
@ Cmp
llvm::VNCoercion::analyzeLoadFromClobberingStore
int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr, StoreInst *DepSI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the store at D...
Definition: VNCoercion.cpp:215
llvm::CallBase::arg_size
unsigned arg_size() const
Definition: InstrTypes.h:1339
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2398
llvm::MemorySSA::BeforeTerminator
@ BeforeTerminator
Definition: MemorySSA.h:802
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:799
Casting.h
impliesEquivalanceIfFalse
static bool impliesEquivalanceIfFalse(CmpInst *Cmp)
Definition: GVN.cpp:1854
Function.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
PassManager.h
llvm::salvageDebugInfo
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1739
llvm::MapVector::size
size_type size() const
Definition: MapVector.h:61
llvm::Type::getPointerTo
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
Definition: Type.cpp:774
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
Numbering
Global Value Numbering
Definition: NewGVN.cpp:4260
llvm::ExtractValueInst::getAggregateOperand
Value * getAggregateOperand()
Definition: Instructions.h:2453
llvm::GVNPass::Expression::opcode
uint32_t opcode
Definition: GVN.cpp:125
llvm::gvn::AvailableValueInBlock::BB
BasicBlock * BB
BB - The basic block in question.
Definition: GVN.cpp:272
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
llvm::gvn::AvailableValue::getSimpleValue
Value * getSimpleValue() const
Definition: GVN.cpp:242
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::VNCoercion::canCoerceMustAliasedValueToLoad
bool canCoerceMustAliasedValueToLoad(Value *StoredVal, Type *LoadTy, const DataLayout &DL)
Return true if CoerceAvailableValueToLoadType would succeed if it was called.
Definition: VNCoercion.cpp:18
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
LiveDebugValues::ValueTable
std::unique_ptr< ValueIDNum[]> ValueTable
Type for a table of values in a block.
Definition: InstrRefBasedImpl.h:172
llvm::gvn::AvailableValueInBlock::getSelect
static AvailableValueInBlock getSelect(BasicBlock *BB, SelectInst *Sel)
Definition: GVN.cpp:293
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:291
llvm::DenseMapInfo< GVNPass::Expression >::getHashValue
static unsigned getHashValue(const GVNPass::Expression &e)
Definition: GVN.cpp:159
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::gvn::AvailableValue::isSelectValue
bool isSelectValue() const
Definition: GVN.cpp:240
isLifetimeStart
static bool isLifetimeStart(const Instruction *Inst)
Definition: GVN.cpp:1023
AA
InstructionPrecedenceTracking.h
MaxNumDeps
static cl::opt< uint32_t > MaxNumDeps("gvn-max-num-deps", cl::Hidden, cl::init(100), cl::desc("Max number of dependences to attempt Load PRE (default = 100)"))
llvm::pred_begin
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
commutative
http eax xorl edx cl sete al setne dl sall eax sall edx But that requires good bit subreg support this might be better It s an extra but it s one instruction and doesn t stress bit subreg eax eax movl edx edx sall eax sall cl edx bit we should expand to a conditional branch like GCC produces Some isel and Sequencing of Instructions Scheduling for reduced register pressure E g Minimum Register Instruction Sequence load p Because the compare isn t commutative
Definition: README.txt:77
llvm::Value::canBeFreed
bool canBeFreed() const
Return true if the memory object referred to by V can by freed in the scope for which the SSA value d...
Definition: Value.cpp:778
llvm::Type::isOpaquePointerTy
bool isOpaquePointerTy() const
True if this is an instance of an opaque PointerType.
Definition: Type.cpp:61
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:690
MemorySSA.h
Instructions.h
PostOrderIterator.h
llvm::initializeGVNLegacyPassPass
void initializeGVNLegacyPassPass(PassRegistry &)
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
INITIALIZE_PASS_BEGIN
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:51
SmallVector.h
lookup
static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset, uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs, llvm::Error &Err)
A Lookup helper functions.
Definition: InlineInfo.cpp:108
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:367
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:605
GVNEnableSplitBackedgeInLoadPRE
static cl::opt< bool > GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre", cl::init(false))
Dominators.h
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1341
llvm::MemoryDependenceResults::NonLocalDepInfo
std::vector< NonLocalDepEntry > NonLocalDepInfo
Definition: MemoryDependenceAnalysis.h:271
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1351
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:483
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::try_emplace
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:224
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
InstructionSimplify.h
llvm::Value::deleteValue
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:106
Expressions
gvn Early GVN Hoisting of Expressions
Definition: GVNHoist.cpp:1265
llvm::VNCoercion::analyzeLoadFromClobberingLoad
int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the load at De...
Definition: VNCoercion.cpp:321
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:148
llvm::GVNPass::Expression
Definition: GVN.cpp:124
llvm::gvn::GVNLegacyPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: GVN.cpp:3214
llvm::GVNPass::ValueTable::phiTranslate
uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, uint32_t Num, GVNPass &Gvn)
Wrap phiTranslateImpl to provide caching functionality.
Definition: GVN.cpp:2112
llvm::codeview::CompileSym3Flags::Exp
@ Exp
llvm::PHINode
Definition: Instructions.h:2651
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
AvailabilityState::SpeculativelyAvailable
@ SpeculativelyAvailable
We do not know whether the block is fully available or not, but we are currently speculating that it ...
IV
static const uint32_t IV[8]
Definition: blake3_impl.h:85
llvm::SmallSet::empty
LLVM_NODISCARD bool empty() const
Definition: SmallSet.h:157
llvm::gvn::AvailableValue::Offset
unsigned Offset
Offset - The byte offset in Val that is interesting for the load query.
Definition: GVN.cpp:194
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::gvn::GVNLegacyPass::ID
static char ID
Definition: GVN.cpp:3187
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1461
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::LoadInst::isUnordered
bool isUnordered() const
Definition: Instructions.h:254
llvm::MIPatternMatch::m_Not
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
Definition: MIPatternMatch.h:696
llvm::patchReplacementInstruction
void patchReplacementInstruction(Instruction *I, Value *Repl)
Patch the replacement so that it is not more restrictive than the value being replaced.
Definition: Local.cpp:2667
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
llvm::GVNPass
The core GVN pass object.
Definition: GVN.h:116
LLVMContext.h
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3230
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:378
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::SSAUpdater::AddAvailableValue
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdater.cpp:69
llvm::cl::desc
Definition: CommandLine.h:405
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3086
raw_ostream.h
d
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int int d
Definition: README.txt:418
llvm::SSAUpdater
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:38
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::gvn::AvailableValue::Val
Value * Val
Val - The value that is live out of the block.
Definition: GVN.cpp:189
BasicBlockUtils.h
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:62
Value.h
InitializePasses.h
llvm::BasicBlock::isEHPad
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:466
llvm::OptimizationRemarkEmitterAnalysis
Definition: OptimizationRemarkEmitter.h:164
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::gvn::AvailableValue::Kind
ValType Kind
Kind of the live-out value.
Definition: GVN.cpp:191
llvm::GVNPass::Expression::operator==
bool operator==(const Expression &other) const
Definition: GVN.cpp:134
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:443
llvm::MemDepResult::isNonLocal
bool isNonLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the block,...
Definition: MemoryDependenceAnalysis.h:148
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:153
llvm::gvn::AvailableValueInBlock::get
static AvailableValueInBlock get(BasicBlock *BB, Value *V, unsigned Offset=0)
Definition: GVN.cpp:284
llvm::gvn::AvailableValue::getUndef
static AvailableValue getUndef()
Definition: GVN.cpp:220
llvm::PatternMatch::m_LogicalAnd
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
Definition: PatternMatch.h:2531
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3179
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1262
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:927
llvm::MemoryDependenceAnalysis
An analysis that produces MemoryDependenceResults for a function.
Definition: MemoryDependenceAnalysis.h:507
llvm::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:73
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:792
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1796
llvm::MemDepResult::isDef
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.
Definition: MemoryDependenceAnalysis.h:144