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