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