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