LLVM  8.0.0svn
GVNHoist.cpp
Go to the documentation of this file.
1 //===- GVNHoist.cpp - Hoist scalar and load expressions -------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass hoists expressions from branches to a common dominator. It uses
11 // GVN (global value numbering) to discover expressions computing the same
12 // values. The primary goals of code-hoisting are:
13 // 1. To reduce the code size.
14 // 2. In some cases reduce critical path (by exposing more ILP).
15 //
16 // The algorithm factors out the reachability of values such that multiple
17 // queries to find reachability of values are fast. This is based on finding the
18 // ANTIC points in the CFG which do not change during hoisting. The ANTIC points
19 // are basically the dominance-frontiers in the inverse graph. So we introduce a
20 // data structure (CHI nodes) to keep track of values flowing out of a basic
21 // block. We only do this for values with multiple occurrences in the function
22 // as they are the potential hoistable candidates. This approach allows us to
23 // hoist instructions to a basic block with more than two successors, as well as
24 // deal with infinite loops in a trivial way.
25 //
26 // Limitations: This pass does not hoist fully redundant expressions because
27 // they are already handled by GVN-PRE. It is advisable to run gvn-hoist before
28 // and after gvn-pre because gvn-pre creates opportunities for more instructions
29 // to be hoisted.
30 //
31 // Hoisting may affect the performance in some cases. To mitigate that, hoisting
32 // is disabled in the following cases.
33 // 1. Scalars across calls.
34 // 2. geps when corresponding load/store cannot be hoisted.
35 //===----------------------------------------------------------------------===//
36 
37 #include "llvm/ADT/DenseMap.h"
38 #include "llvm/ADT/DenseSet.h"
39 #include "llvm/ADT/STLExtras.h"
40 #include "llvm/ADT/SmallPtrSet.h"
41 #include "llvm/ADT/SmallVector.h"
42 #include "llvm/ADT/Statistic.h"
53 #include "llvm/IR/Argument.h"
54 #include "llvm/IR/BasicBlock.h"
55 #include "llvm/IR/CFG.h"
56 #include "llvm/IR/Constants.h"
57 #include "llvm/IR/Dominators.h"
58 #include "llvm/IR/Function.h"
59 #include "llvm/IR/InstrTypes.h"
60 #include "llvm/IR/Instruction.h"
61 #include "llvm/IR/Instructions.h"
62 #include "llvm/IR/IntrinsicInst.h"
63 #include "llvm/IR/Intrinsics.h"
64 #include "llvm/IR/LLVMContext.h"
65 #include "llvm/IR/PassManager.h"
66 #include "llvm/IR/Use.h"
67 #include "llvm/IR/User.h"
68 #include "llvm/IR/Value.h"
69 #include "llvm/Pass.h"
70 #include "llvm/Support/Casting.h"
72 #include "llvm/Support/Debug.h"
74 #include "llvm/Transforms/Scalar.h"
76 #include <algorithm>
77 #include <cassert>
78 #include <iterator>
79 #include <memory>
80 #include <utility>
81 #include <vector>
82 
83 using namespace llvm;
84 
85 #define DEBUG_TYPE "gvn-hoist"
86 
87 STATISTIC(NumHoisted, "Number of instructions hoisted");
88 STATISTIC(NumRemoved, "Number of instructions removed");
89 STATISTIC(NumLoadsHoisted, "Number of loads hoisted");
90 STATISTIC(NumLoadsRemoved, "Number of loads removed");
91 STATISTIC(NumStoresHoisted, "Number of stores hoisted");
92 STATISTIC(NumStoresRemoved, "Number of stores removed");
93 STATISTIC(NumCallsHoisted, "Number of calls hoisted");
94 STATISTIC(NumCallsRemoved, "Number of calls removed");
95 
96 static cl::opt<int>
97  MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1),
98  cl::desc("Max number of instructions to hoist "
99  "(default unlimited = -1)"));
100 
102  "gvn-hoist-max-bbs", cl::Hidden, cl::init(4),
103  cl::desc("Max number of basic blocks on the path between "
104  "hoisting locations (default = 4, unlimited = -1)"));
105 
107  "gvn-hoist-max-depth", cl::Hidden, cl::init(100),
108  cl::desc("Hoist instructions from the beginning of the BB up to the "
109  "maximum specified depth (default = 100, unlimited = -1)"));
110 
111 static cl::opt<int>
112  MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
113  cl::desc("Maximum length of dependent chains to hoist "
114  "(default = 10, unlimited = -1)"));
115 
116 namespace llvm {
117 
121 
122 // Each element of a hoisting list contains the basic block where to hoist and
123 // a list of instructions to be hoisted.
124 using HoistingPointInfo = std::pair<BasicBlock *, SmallVecInsn>;
125 
127 
128 // A map from a pair of VNs to all the instructions with those VNs.
129 using VNType = std::pair<unsigned, unsigned>;
130 
132 
133 // CHI keeps information about values flowing out of a basic block. It is
134 // similar to PHI but in the inverse graph, and used for outgoing values on each
135 // edge. For conciseness, it is computed only for instructions with multiple
136 // occurrences in the CFG because they are the only hoistable candidates.
137 // A (CHI[{V, B, I1}, {V, C, I2}]
138 // / \
139 // / \
140 // B(I1) C (I2)
141 // The Value number for both I1 and I2 is V, the CHI node will save the
142 // instruction as well as the edge where the value is flowing to.
143 struct CHIArg {
145 
146  // Edge destination (shows the direction of flow), may not be where the I is.
148 
149  // The instruction (VN) which uses the values flowing out of CHI.
151 
152  bool operator==(const CHIArg &A) { return VN == A.VN; }
153  bool operator!=(const CHIArg &A) { return !(*this == A); }
154 };
155 
159 using InValuesType =
161 
162 // An invalid value number Used when inserting a single value number into
163 // VNtoInsns.
164 enum : unsigned { InvalidVN = ~2U };
165 
166 // Records all scalar instructions candidate for code hoisting.
167 class InsnInfo {
168  VNtoInsns VNtoScalars;
169 
170 public:
171  // Inserts I and its value number in VNtoScalars.
173  // Scalar instruction.
174  unsigned V = VN.lookupOrAdd(I);
175  VNtoScalars[{V, InvalidVN}].push_back(I);
176  }
177 
178  const VNtoInsns &getVNTable() const { return VNtoScalars; }
179 };
180 
181 // Records all load instructions candidate for code hoisting.
182 class LoadInfo {
183  VNtoInsns VNtoLoads;
184 
185 public:
186  // Insert Load and the value number of its memory address in VNtoLoads.
188  if (Load->isSimple()) {
189  unsigned V = VN.lookupOrAdd(Load->getPointerOperand());
190  VNtoLoads[{V, InvalidVN}].push_back(Load);
191  }
192  }
193 
194  const VNtoInsns &getVNTable() const { return VNtoLoads; }
195 };
196 
197 // Records all store instructions candidate for code hoisting.
198 class StoreInfo {
199  VNtoInsns VNtoStores;
200 
201 public:
202  // Insert the Store and a hash number of the store address and the stored
203  // value in VNtoStores.
205  if (!Store->isSimple())
206  return;
207  // Hash the store address and the stored value.
208  Value *Ptr = Store->getPointerOperand();
209  Value *Val = Store->getValueOperand();
210  VNtoStores[{VN.lookupOrAdd(Ptr), VN.lookupOrAdd(Val)}].push_back(Store);
211  }
212 
213  const VNtoInsns &getVNTable() const { return VNtoStores; }
214 };
215 
216 // Records all call instructions candidate for code hoisting.
217 class CallInfo {
218  VNtoInsns VNtoCallsScalars;
219  VNtoInsns VNtoCallsLoads;
220  VNtoInsns VNtoCallsStores;
221 
222 public:
223  // Insert Call and its value numbering in one of the VNtoCalls* containers.
225  // A call that doesNotAccessMemory is handled as a Scalar,
226  // onlyReadsMemory will be handled as a Load instruction,
227  // all other calls will be handled as stores.
228  unsigned V = VN.lookupOrAdd(Call);
229  auto Entry = std::make_pair(V, InvalidVN);
230 
231  if (Call->doesNotAccessMemory())
232  VNtoCallsScalars[Entry].push_back(Call);
233  else if (Call->onlyReadsMemory())
234  VNtoCallsLoads[Entry].push_back(Call);
235  else
236  VNtoCallsStores[Entry].push_back(Call);
237  }
238 
239  const VNtoInsns &getScalarVNTable() const { return VNtoCallsScalars; }
240  const VNtoInsns &getLoadVNTable() const { return VNtoCallsLoads; }
241  const VNtoInsns &getStoreVNTable() const { return VNtoCallsStores; }
242 };
243 
244 static void combineKnownMetadata(Instruction *ReplInst, Instruction *I) {
245  static const unsigned KnownIDs[] = {
250  combineMetadata(ReplInst, I, KnownIDs, true);
251 }
252 
253 // This pass hoists common computations across branches sharing common
254 // dominator. The primary goal is to reduce the code size, and in some
255 // cases reduce critical path (by exposing more ILP).
256 class GVNHoist {
257 public:
260  : DT(DT), PDT(PDT), AA(AA), MD(MD), MSSA(MSSA),
261  MSSAUpdater(llvm::make_unique<MemorySSAUpdater>(MSSA)) {}
262 
263  bool run(Function &F) {
264  NumFuncArgs = F.arg_size();
265  VN.setDomTree(DT);
266  VN.setAliasAnalysis(AA);
267  VN.setMemDep(MD);
268  bool Res = false;
269  // Perform DFS Numbering of instructions.
270  unsigned BBI = 0;
271  for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) {
272  DFSNumber[BB] = ++BBI;
273  unsigned I = 0;
274  for (auto &Inst : *BB)
275  DFSNumber[&Inst] = ++I;
276  }
277 
278  int ChainLength = 0;
279 
280  // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
281  while (true) {
282  if (MaxChainLength != -1 && ++ChainLength >= MaxChainLength)
283  return Res;
284 
285  auto HoistStat = hoistExpressions(F);
286  if (HoistStat.first + HoistStat.second == 0)
287  return Res;
288 
289  if (HoistStat.second > 0)
290  // To address a limitation of the current GVN, we need to rerun the
291  // hoisting after we hoisted loads or stores in order to be able to
292  // hoist all scalars dependent on the hoisted ld/st.
293  VN.clear();
294 
295  Res = true;
296  }
297 
298  return Res;
299  }
300 
301  // Copied from NewGVN.cpp
302  // This function provides global ranking of operations so that we can place
303  // them in a canonical order. Note that rank alone is not necessarily enough
304  // for a complete ordering, as constants all have the same rank. However,
305  // generally, we will simplify an operation with all constants so that it
306  // doesn't matter what order they appear in.
307  unsigned int rank(const Value *V) const {
308  // Prefer constants to undef to anything else
309  // Undef is a constant, have to check it first.
310  // Prefer smaller constants to constantexprs
311  if (isa<ConstantExpr>(V))
312  return 2;
313  if (isa<UndefValue>(V))
314  return 1;
315  if (isa<Constant>(V))
316  return 0;
317  else if (auto *A = dyn_cast<Argument>(V))
318  return 3 + A->getArgNo();
319 
320  // Need to shift the instruction DFS by number of arguments + 3 to account
321  // for the constant and argument ranking above.
322  auto Result = DFSNumber.lookup(V);
323  if (Result > 0)
324  return 4 + NumFuncArgs + Result;
325  // Unreachable or something else, just return a really large number.
326  return ~0;
327  }
328 
329 private:
331  DominatorTree *DT;
332  PostDominatorTree *PDT;
333  AliasAnalysis *AA;
335  MemorySSA *MSSA;
336  std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
338  BBSideEffectsSet BBSideEffects;
339  DenseSet<const BasicBlock *> HoistBarrier;
341  unsigned NumFuncArgs;
342  const bool HoistingGeps = false;
343 
344  enum InsKind { Unknown, Scalar, Load, Store };
345 
346  // Return true when there are exception handling in BB.
347  bool hasEH(const BasicBlock *BB) {
348  auto It = BBSideEffects.find(BB);
349  if (It != BBSideEffects.end())
350  return It->second;
351 
352  if (BB->isEHPad() || BB->hasAddressTaken()) {
353  BBSideEffects[BB] = true;
354  return true;
355  }
356 
357  if (BB->getTerminator()->mayThrow()) {
358  BBSideEffects[BB] = true;
359  return true;
360  }
361 
362  BBSideEffects[BB] = false;
363  return false;
364  }
365 
366  // Return true when a successor of BB dominates A.
367  bool successorDominate(const BasicBlock *BB, const BasicBlock *A) {
368  for (const BasicBlock *Succ : successors(BB))
369  if (DT->dominates(Succ, A))
370  return true;
371 
372  return false;
373  }
374 
375  // Return true when I1 appears before I2 in the instructions of BB.
376  bool firstInBB(const Instruction *I1, const Instruction *I2) {
377  assert(I1->getParent() == I2->getParent());
378  unsigned I1DFS = DFSNumber.lookup(I1);
379  unsigned I2DFS = DFSNumber.lookup(I2);
380  assert(I1DFS && I2DFS);
381  return I1DFS < I2DFS;
382  }
383 
384  // Return true when there are memory uses of Def in BB.
385  bool hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
386  const BasicBlock *BB) {
387  const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
388  if (!Acc)
389  return false;
390 
391  Instruction *OldPt = Def->getMemoryInst();
392  const BasicBlock *OldBB = OldPt->getParent();
393  const BasicBlock *NewBB = NewPt->getParent();
394  bool ReachedNewPt = false;
395 
396  for (const MemoryAccess &MA : *Acc)
397  if (const MemoryUse *MU = dyn_cast<MemoryUse>(&MA)) {
398  Instruction *Insn = MU->getMemoryInst();
399 
400  // Do not check whether MU aliases Def when MU occurs after OldPt.
401  if (BB == OldBB && firstInBB(OldPt, Insn))
402  break;
403 
404  // Do not check whether MU aliases Def when MU occurs before NewPt.
405  if (BB == NewBB) {
406  if (!ReachedNewPt) {
407  if (firstInBB(Insn, NewPt))
408  continue;
409  ReachedNewPt = true;
410  }
411  }
412  if (MemorySSAUtil::defClobbersUseOrDef(Def, MU, *AA))
413  return true;
414  }
415 
416  return false;
417  }
418 
419  bool hasEHhelper(const BasicBlock *BB, const BasicBlock *SrcBB,
420  int &NBBsOnAllPaths) {
421  // Stop walk once the limit is reached.
422  if (NBBsOnAllPaths == 0)
423  return true;
424 
425  // Impossible to hoist with exceptions on the path.
426  if (hasEH(BB))
427  return true;
428 
429  // No such instruction after HoistBarrier in a basic block was
430  // selected for hoisting so instructions selected within basic block with
431  // a hoist barrier can be hoisted.
432  if ((BB != SrcBB) && HoistBarrier.count(BB))
433  return true;
434 
435  return false;
436  }
437 
438  // Return true when there are exception handling or loads of memory Def
439  // between Def and NewPt. This function is only called for stores: Def is
440  // the MemoryDef of the store to be hoisted.
441 
442  // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
443  // return true when the counter NBBsOnAllPaths reaces 0, except when it is
444  // initialized to -1 which is unlimited.
445  bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
446  int &NBBsOnAllPaths) {
447  const BasicBlock *NewBB = NewPt->getParent();
448  const BasicBlock *OldBB = Def->getBlock();
449  assert(DT->dominates(NewBB, OldBB) && "invalid path");
450  assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&
451  "def does not dominate new hoisting point");
452 
453  // Walk all basic blocks reachable in depth-first iteration on the inverse
454  // CFG from OldBB to NewBB. These blocks are all the blocks that may be
455  // executed between the execution of NewBB and OldBB. Hoisting an expression
456  // from OldBB into NewBB has to be safe on all execution paths.
457  for (auto I = idf_begin(OldBB), E = idf_end(OldBB); I != E;) {
458  const BasicBlock *BB = *I;
459  if (BB == NewBB) {
460  // Stop traversal when reaching HoistPt.
461  I.skipChildren();
462  continue;
463  }
464 
465  if (hasEHhelper(BB, OldBB, NBBsOnAllPaths))
466  return true;
467 
468  // Check that we do not move a store past loads.
469  if (hasMemoryUse(NewPt, Def, BB))
470  return true;
471 
472  // -1 is unlimited number of blocks on all paths.
473  if (NBBsOnAllPaths != -1)
474  --NBBsOnAllPaths;
475 
476  ++I;
477  }
478 
479  return false;
480  }
481 
482  // Return true when there are exception handling between HoistPt and BB.
483  // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
484  // return true when the counter NBBsOnAllPaths reaches 0, except when it is
485  // initialized to -1 which is unlimited.
486  bool hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,
487  int &NBBsOnAllPaths) {
488  assert(DT->dominates(HoistPt, SrcBB) && "Invalid path");
489 
490  // Walk all basic blocks reachable in depth-first iteration on
491  // the inverse CFG from BBInsn to NewHoistPt. These blocks are all the
492  // blocks that may be executed between the execution of NewHoistPt and
493  // BBInsn. Hoisting an expression from BBInsn into NewHoistPt has to be safe
494  // on all execution paths.
495  for (auto I = idf_begin(SrcBB), E = idf_end(SrcBB); I != E;) {
496  const BasicBlock *BB = *I;
497  if (BB == HoistPt) {
498  // Stop traversal when reaching NewHoistPt.
499  I.skipChildren();
500  continue;
501  }
502 
503  if (hasEHhelper(BB, SrcBB, NBBsOnAllPaths))
504  return true;
505 
506  // -1 is unlimited number of blocks on all paths.
507  if (NBBsOnAllPaths != -1)
508  --NBBsOnAllPaths;
509 
510  ++I;
511  }
512 
513  return false;
514  }
515 
516  // Return true when it is safe to hoist a memory load or store U from OldPt
517  // to NewPt.
518  bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,
519  MemoryUseOrDef *U, InsKind K, int &NBBsOnAllPaths) {
520  // In place hoisting is safe.
521  if (NewPt == OldPt)
522  return true;
523 
524  const BasicBlock *NewBB = NewPt->getParent();
525  const BasicBlock *OldBB = OldPt->getParent();
526  const BasicBlock *UBB = U->getBlock();
527 
528  // Check for dependences on the Memory SSA.
530  BasicBlock *DBB = D->getBlock();
531  if (DT->properlyDominates(NewBB, DBB))
532  // Cannot move the load or store to NewBB above its definition in DBB.
533  return false;
534 
535  if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D))
536  if (auto *UD = dyn_cast<MemoryUseOrDef>(D))
537  if (!firstInBB(UD->getMemoryInst(), NewPt))
538  // Cannot move the load or store to NewPt above its definition in D.
539  return false;
540 
541  // Check for unsafe hoistings due to side effects.
542  if (K == InsKind::Store) {
543  if (hasEHOrLoadsOnPath(NewPt, dyn_cast<MemoryDef>(U), NBBsOnAllPaths))
544  return false;
545  } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
546  return false;
547 
548  if (UBB == NewBB) {
549  if (DT->properlyDominates(DBB, NewBB))
550  return true;
551  assert(UBB == DBB);
552  assert(MSSA->locallyDominates(D, U));
553  }
554 
555  // No side effects: it is safe to hoist.
556  return true;
557  }
558 
559  // Return true when it is safe to hoist scalar instructions from all blocks in
560  // WL to HoistBB.
561  bool safeToHoistScalar(const BasicBlock *HoistBB, const BasicBlock *BB,
562  int &NBBsOnAllPaths) {
563  return !hasEHOnPath(HoistBB, BB, NBBsOnAllPaths);
564  }
565 
566  // In the inverse CFG, the dominance frontier of basic block (BB) is the
567  // point where ANTIC needs to be computed for instructions which are going
568  // to be hoisted. Since this point does not change during gvn-hoist,
569  // we compute it only once (on demand).
570  // The ides is inspired from:
571  // "Partial Redundancy Elimination in SSA Form"
572  // ROBERT KENNEDY, SUN CHAN, SHIN-MING LIU, RAYMOND LO, PENG TU and FRED CHOW
573  // They use similar idea in the forward graph to find fully redundant and
574  // partially redundant expressions, here it is used in the inverse graph to
575  // find fully anticipable instructions at merge point (post-dominator in
576  // the inverse CFG).
577  // Returns the edge via which an instruction in BB will get the values from.
578 
579  // Returns true when the values are flowing out to each edge.
580  bool valueAnticipable(CHIArgs C, TerminatorInst *TI) const {
581  if (TI->getNumSuccessors() > (unsigned)size(C))
582  return false; // Not enough args in this CHI.
583 
584  for (auto CHI : C) {
585  BasicBlock *Dest = CHI.Dest;
586  // Find if all the edges have values flowing out of BB.
587  bool Found = llvm::any_of(
588  successors(TI), [Dest](const BasicBlock *BB) { return BB == Dest; });
589  if (!Found)
590  return false;
591  }
592  return true;
593  }
594 
595  // Check if it is safe to hoist values tracked by CHI in the range
596  // [Begin, End) and accumulate them in Safe.
597  void checkSafety(CHIArgs C, BasicBlock *BB, InsKind K,
598  SmallVectorImpl<CHIArg> &Safe) {
599  int NumBBsOnAllPaths = MaxNumberOfBBSInPath;
600  for (auto CHI : C) {
601  Instruction *Insn = CHI.I;
602  if (!Insn) // No instruction was inserted in this CHI.
603  continue;
604  if (K == InsKind::Scalar) {
605  if (safeToHoistScalar(BB, Insn->getParent(), NumBBsOnAllPaths))
606  Safe.push_back(CHI);
607  } else {
608  MemoryUseOrDef *UD = MSSA->getMemoryAccess(Insn);
609  if (safeToHoistLdSt(BB->getTerminator(), Insn, UD, K, NumBBsOnAllPaths))
610  Safe.push_back(CHI);
611  }
612  }
613  }
614 
616 
617  // Push all the VNs corresponding to BB into RenameStack.
618  void fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
619  RenameStackType &RenameStack) {
620  auto it1 = ValueBBs.find(BB);
621  if (it1 != ValueBBs.end()) {
622  // Iterate in reverse order to keep lower ranked values on the top.
623  for (std::pair<VNType, Instruction *> &VI : reverse(it1->second)) {
624  // Get the value of instruction I
625  LLVM_DEBUG(dbgs() << "\nPushing on stack: " << *VI.second);
626  RenameStack[VI.first].push_back(VI.second);
627  }
628  }
629  }
630 
631  void fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,
632  RenameStackType &RenameStack) {
633  // For each *predecessor* (because Post-DOM) of BB check if it has a CHI
634  for (auto Pred : predecessors(BB)) {
635  auto P = CHIBBs.find(Pred);
636  if (P == CHIBBs.end()) {
637  continue;
638  }
639  LLVM_DEBUG(dbgs() << "\nLooking at CHIs in: " << Pred->getName(););
640  // A CHI is found (BB -> Pred is an edge in the CFG)
641  // Pop the stack until Top(V) = Ve.
642  auto &VCHI = P->second;
643  for (auto It = VCHI.begin(), E = VCHI.end(); It != E;) {
644  CHIArg &C = *It;
645  if (!C.Dest) {
646  auto si = RenameStack.find(C.VN);
647  // The Basic Block where CHI is must dominate the value we want to
648  // track in a CHI. In the PDom walk, there can be values in the
649  // stack which are not control dependent e.g., nested loop.
650  if (si != RenameStack.end() && si->second.size() &&
651  DT->properlyDominates(Pred, si->second.back()->getParent())) {
652  C.Dest = BB; // Assign the edge
653  C.I = si->second.pop_back_val(); // Assign the argument
654  LLVM_DEBUG(dbgs()
655  << "\nCHI Inserted in BB: " << C.Dest->getName() << *C.I
656  << ", VN: " << C.VN.first << ", " << C.VN.second);
657  }
658  // Move to next CHI of a different value
659  It = std::find_if(It, VCHI.end(),
660  [It](CHIArg &A) { return A != *It; });
661  } else
662  ++It;
663  }
664  }
665  }
666 
667  // Walk the post-dominator tree top-down and use a stack for each value to
668  // store the last value you see. When you hit a CHI from a given edge, the
669  // value to use as the argument is at the top of the stack, add the value to
670  // CHI and pop.
671  void insertCHI(InValuesType &ValueBBs, OutValuesType &CHIBBs) {
672  auto Root = PDT->getNode(nullptr);
673  if (!Root)
674  return;
675  // Depth first walk on PDom tree to fill the CHIargs at each PDF.
676  RenameStackType RenameStack;
677  for (auto Node : depth_first(Root)) {
678  BasicBlock *BB = Node->getBlock();
679  if (!BB)
680  continue;
681 
682  // Collect all values in BB and push to stack.
683  fillRenameStack(BB, ValueBBs, RenameStack);
684 
685  // Fill outgoing values in each CHI corresponding to BB.
686  fillChiArgs(BB, CHIBBs, RenameStack);
687  }
688  }
689 
690  // Walk all the CHI-nodes to find ones which have a empty-entry and remove
691  // them Then collect all the instructions which are safe to hoist and see if
692  // they form a list of anticipable values. OutValues contains CHIs
693  // corresponding to each basic block.
694  void findHoistableCandidates(OutValuesType &CHIBBs, InsKind K,
695  HoistingPointList &HPL) {
696  auto cmpVN = [](const CHIArg &A, const CHIArg &B) { return A.VN < B.VN; };
697 
698  // CHIArgs now have the outgoing values, so check for anticipability and
699  // accumulate hoistable candidates in HPL.
700  for (std::pair<BasicBlock *, SmallVector<CHIArg, 2>> &A : CHIBBs) {
701  BasicBlock *BB = A.first;
702  SmallVectorImpl<CHIArg> &CHIs = A.second;
703  // Vector of PHIs contains PHIs for different instructions.
704  // Sort the args according to their VNs, such that identical
705  // instructions are together.
706  std::stable_sort(CHIs.begin(), CHIs.end(), cmpVN);
707  auto TI = BB->getTerminator();
708  auto B = CHIs.begin();
709  // [PreIt, PHIIt) form a range of CHIs which have identical VNs.
710  auto PHIIt = std::find_if(CHIs.begin(), CHIs.end(),
711  [B](CHIArg &A) { return A != *B; });
712  auto PrevIt = CHIs.begin();
713  while (PrevIt != PHIIt) {
714  // Collect values which satisfy safety checks.
716  // We check for safety first because there might be multiple values in
717  // the same path, some of which are not safe to be hoisted, but overall
718  // each edge has at least one value which can be hoisted, making the
719  // value anticipable along that path.
720  checkSafety(make_range(PrevIt, PHIIt), BB, K, Safe);
721 
722  // List of safe values should be anticipable at TI.
723  if (valueAnticipable(make_range(Safe.begin(), Safe.end()), TI)) {
724  HPL.push_back({BB, SmallVecInsn()});
725  SmallVecInsn &V = HPL.back().second;
726  for (auto B : Safe)
727  V.push_back(B.I);
728  }
729 
730  // Check other VNs
731  PrevIt = PHIIt;
732  PHIIt = std::find_if(PrevIt, CHIs.end(),
733  [PrevIt](CHIArg &A) { return A != *PrevIt; });
734  }
735  }
736  }
737 
738  // Compute insertion points for each values which can be fully anticipated at
739  // a dominator. HPL contains all such values.
740  void computeInsertionPoints(const VNtoInsns &Map, HoistingPointList &HPL,
741  InsKind K) {
742  // Sort VNs based on their rankings
743  std::vector<VNType> Ranks;
744  for (const auto &Entry : Map) {
745  Ranks.push_back(Entry.first);
746  }
747 
748  // TODO: Remove fully-redundant expressions.
749  // Get instruction from the Map, assume that all the Instructions
750  // with same VNs have same rank (this is an approximation).
751  llvm::sort(Ranks.begin(), Ranks.end(),
752  [this, &Map](const VNType &r1, const VNType &r2) {
753  return (rank(*Map.lookup(r1).begin()) <
754  rank(*Map.lookup(r2).begin()));
755  });
756 
757  // - Sort VNs according to their rank, and start with lowest ranked VN
758  // - Take a VN and for each instruction with same VN
759  // - Find the dominance frontier in the inverse graph (PDF)
760  // - Insert the chi-node at PDF
761  // - Remove the chi-nodes with missing entries
762  // - Remove values from CHI-nodes which do not truly flow out, e.g.,
763  // modified along the path.
764  // - Collect the remaining values that are still anticipable
766  ReverseIDFCalculator IDFs(*PDT);
767  OutValuesType OutValue;
768  InValuesType InValue;
769  for (const auto &R : Ranks) {
770  const SmallVecInsn &V = Map.lookup(R);
771  if (V.size() < 2)
772  continue;
773  const VNType &VN = R;
775  for (auto &I : V) {
776  BasicBlock *BBI = I->getParent();
777  if (!hasEH(BBI))
778  VNBlocks.insert(BBI);
779  }
780  // Compute the Post Dominance Frontiers of each basic block
781  // The dominance frontier of a live block X in the reverse
782  // control graph is the set of blocks upon which X is control
783  // dependent. The following sequence computes the set of blocks
784  // which currently have dead terminators that are control
785  // dependence sources of a block which is in NewLiveBlocks.
786  IDFs.setDefiningBlocks(VNBlocks);
787  IDFBlocks.clear();
788  IDFs.calculate(IDFBlocks);
789 
790  // Make a map of BB vs instructions to be hoisted.
791  for (unsigned i = 0; i < V.size(); ++i) {
792  InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
793  }
794  // Insert empty CHI node for this VN. This is used to factor out
795  // basic blocks where the ANTIC can potentially change.
796  for (auto IDFB : IDFBlocks) {
797  for (unsigned i = 0; i < V.size(); ++i) {
798  CHIArg C = {VN, nullptr, nullptr};
799  // Ignore spurious PDFs.
800  if (DT->properlyDominates(IDFB, V[i]->getParent())) {
801  OutValue[IDFB].push_back(C);
802  LLVM_DEBUG(dbgs() << "\nInsertion a CHI for BB: " << IDFB->getName()
803  << ", for Insn: " << *V[i]);
804  }
805  }
806  }
807  }
808 
809  // Insert CHI args at each PDF to iterate on factored graph of
810  // control dependence.
811  insertCHI(InValue, OutValue);
812  // Using the CHI args inserted at each PDF, find fully anticipable values.
813  findHoistableCandidates(OutValue, K, HPL);
814  }
815 
816  // Return true when all operands of Instr are available at insertion point
817  // HoistPt. When limiting the number of hoisted expressions, one could hoist
818  // a load without hoisting its access function. So before hoisting any
819  // expression, make sure that all its operands are available at insert point.
820  bool allOperandsAvailable(const Instruction *I,
821  const BasicBlock *HoistPt) const {
822  for (const Use &Op : I->operands())
823  if (const auto *Inst = dyn_cast<Instruction>(&Op))
824  if (!DT->dominates(Inst->getParent(), HoistPt))
825  return false;
826 
827  return true;
828  }
829 
830  // Same as allOperandsAvailable with recursive check for GEP operands.
831  bool allGepOperandsAvailable(const Instruction *I,
832  const BasicBlock *HoistPt) const {
833  for (const Use &Op : I->operands())
834  if (const auto *Inst = dyn_cast<Instruction>(&Op))
835  if (!DT->dominates(Inst->getParent(), HoistPt)) {
836  if (const GetElementPtrInst *GepOp =
837  dyn_cast<GetElementPtrInst>(Inst)) {
838  if (!allGepOperandsAvailable(GepOp, HoistPt))
839  return false;
840  // Gep is available if all operands of GepOp are available.
841  } else {
842  // Gep is not available if it has operands other than GEPs that are
843  // defined in blocks not dominating HoistPt.
844  return false;
845  }
846  }
847  return true;
848  }
849 
850  // Make all operands of the GEP available.
851  void makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
852  const SmallVecInsn &InstructionsToHoist,
853  Instruction *Gep) const {
854  assert(allGepOperandsAvailable(Gep, HoistPt) &&
855  "GEP operands not available");
856 
857  Instruction *ClonedGep = Gep->clone();
858  for (unsigned i = 0, e = Gep->getNumOperands(); i != e; ++i)
859  if (Instruction *Op = dyn_cast<Instruction>(Gep->getOperand(i))) {
860  // Check whether the operand is already available.
861  if (DT->dominates(Op->getParent(), HoistPt))
862  continue;
863 
864  // As a GEP can refer to other GEPs, recursively make all the operands
865  // of this GEP available at HoistPt.
866  if (GetElementPtrInst *GepOp = dyn_cast<GetElementPtrInst>(Op))
867  makeGepsAvailable(ClonedGep, HoistPt, InstructionsToHoist, GepOp);
868  }
869 
870  // Copy Gep and replace its uses in Repl with ClonedGep.
871  ClonedGep->insertBefore(HoistPt->getTerminator());
872 
873  // Conservatively discard any optimization hints, they may differ on the
874  // other paths.
875  ClonedGep->dropUnknownNonDebugMetadata();
876 
877  // If we have optimization hints which agree with each other along different
878  // paths, preserve them.
879  for (const Instruction *OtherInst : InstructionsToHoist) {
880  const GetElementPtrInst *OtherGep;
881  if (auto *OtherLd = dyn_cast<LoadInst>(OtherInst))
882  OtherGep = cast<GetElementPtrInst>(OtherLd->getPointerOperand());
883  else
884  OtherGep = cast<GetElementPtrInst>(
885  cast<StoreInst>(OtherInst)->getPointerOperand());
886  ClonedGep->andIRFlags(OtherGep);
887  }
888 
889  // Replace uses of Gep with ClonedGep in Repl.
890  Repl->replaceUsesOfWith(Gep, ClonedGep);
891  }
892 
893  void updateAlignment(Instruction *I, Instruction *Repl) {
894  if (auto *ReplacementLoad = dyn_cast<LoadInst>(Repl)) {
895  ReplacementLoad->setAlignment(
896  std::min(ReplacementLoad->getAlignment(),
897  cast<LoadInst>(I)->getAlignment()));
898  ++NumLoadsRemoved;
899  } else if (auto *ReplacementStore = dyn_cast<StoreInst>(Repl)) {
900  ReplacementStore->setAlignment(
901  std::min(ReplacementStore->getAlignment(),
902  cast<StoreInst>(I)->getAlignment()));
903  ++NumStoresRemoved;
904  } else if (auto *ReplacementAlloca = dyn_cast<AllocaInst>(Repl)) {
905  ReplacementAlloca->setAlignment(
906  std::max(ReplacementAlloca->getAlignment(),
907  cast<AllocaInst>(I)->getAlignment()));
908  } else if (isa<CallInst>(Repl)) {
909  ++NumCallsRemoved;
910  }
911  }
912 
913  // Remove all the instructions in Candidates and replace their usage with Repl.
914  // Returns the number of instructions removed.
915  unsigned rauw(const SmallVecInsn &Candidates, Instruction *Repl,
916  MemoryUseOrDef *NewMemAcc) {
917  unsigned NR = 0;
918  for (Instruction *I : Candidates) {
919  if (I != Repl) {
920  ++NR;
921  updateAlignment(I, Repl);
922  if (NewMemAcc) {
923  // Update the uses of the old MSSA access with NewMemAcc.
924  MemoryAccess *OldMA = MSSA->getMemoryAccess(I);
925  OldMA->replaceAllUsesWith(NewMemAcc);
926  MSSAUpdater->removeMemoryAccess(OldMA);
927  }
928 
929  Repl->andIRFlags(I);
930  combineKnownMetadata(Repl, I);
931  I->replaceAllUsesWith(Repl);
932  // Also invalidate the Alias Analysis cache.
933  MD->removeInstruction(I);
934  I->eraseFromParent();
935  }
936  }
937  return NR;
938  }
939 
940  // Replace all Memory PHI usage with NewMemAcc.
941  void raMPHIuw(MemoryUseOrDef *NewMemAcc) {
943  for (User *U : NewMemAcc->users())
944  if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(U))
945  UsePhis.insert(Phi);
946 
947  for (MemoryPhi *Phi : UsePhis) {
948  auto In = Phi->incoming_values();
949  if (llvm::all_of(In, [&](Use &U) { return U == NewMemAcc; })) {
950  Phi->replaceAllUsesWith(NewMemAcc);
951  MSSAUpdater->removeMemoryAccess(Phi);
952  }
953  }
954  }
955 
956  // Remove all other instructions and replace them with Repl.
957  unsigned removeAndReplace(const SmallVecInsn &Candidates, Instruction *Repl,
958  BasicBlock *DestBB, bool MoveAccess) {
959  MemoryUseOrDef *NewMemAcc = MSSA->getMemoryAccess(Repl);
960  if (MoveAccess && NewMemAcc) {
961  // The definition of this ld/st will not change: ld/st hoisting is
962  // legal when the ld/st is not moved past its current definition.
963  MSSAUpdater->moveToPlace(NewMemAcc, DestBB, MemorySSA::End);
964  }
965 
966  // Replace all other instructions with Repl with memory access NewMemAcc.
967  unsigned NR = rauw(Candidates, Repl, NewMemAcc);
968 
969  // Remove MemorySSA phi nodes with the same arguments.
970  if (NewMemAcc)
971  raMPHIuw(NewMemAcc);
972  return NR;
973  }
974 
975  // In the case Repl is a load or a store, we make all their GEPs
976  // available: GEPs are not hoisted by default to avoid the address
977  // computations to be hoisted without the associated load or store.
978  bool makeGepOperandsAvailable(Instruction *Repl, BasicBlock *HoistPt,
979  const SmallVecInsn &InstructionsToHoist) const {
980  // Check whether the GEP of a ld/st can be synthesized at HoistPt.
981  GetElementPtrInst *Gep = nullptr;
982  Instruction *Val = nullptr;
983  if (auto *Ld = dyn_cast<LoadInst>(Repl)) {
984  Gep = dyn_cast<GetElementPtrInst>(Ld->getPointerOperand());
985  } else if (auto *St = dyn_cast<StoreInst>(Repl)) {
986  Gep = dyn_cast<GetElementPtrInst>(St->getPointerOperand());
987  Val = dyn_cast<Instruction>(St->getValueOperand());
988  // Check that the stored value is available.
989  if (Val) {
990  if (isa<GetElementPtrInst>(Val)) {
991  // Check whether we can compute the GEP at HoistPt.
992  if (!allGepOperandsAvailable(Val, HoistPt))
993  return false;
994  } else if (!DT->dominates(Val->getParent(), HoistPt))
995  return false;
996  }
997  }
998 
999  // Check whether we can compute the Gep at HoistPt.
1000  if (!Gep || !allGepOperandsAvailable(Gep, HoistPt))
1001  return false;
1002 
1003  makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Gep);
1004 
1005  if (Val && isa<GetElementPtrInst>(Val))
1006  makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Val);
1007 
1008  return true;
1009  }
1010 
1011  std::pair<unsigned, unsigned> hoist(HoistingPointList &HPL) {
1012  unsigned NI = 0, NL = 0, NS = 0, NC = 0, NR = 0;
1013  for (const HoistingPointInfo &HP : HPL) {
1014  // Find out whether we already have one of the instructions in HoistPt,
1015  // in which case we do not have to move it.
1016  BasicBlock *DestBB = HP.first;
1017  const SmallVecInsn &InstructionsToHoist = HP.second;
1018  Instruction *Repl = nullptr;
1019  for (Instruction *I : InstructionsToHoist)
1020  if (I->getParent() == DestBB)
1021  // If there are two instructions in HoistPt to be hoisted in place:
1022  // update Repl to be the first one, such that we can rename the uses
1023  // of the second based on the first.
1024  if (!Repl || firstInBB(I, Repl))
1025  Repl = I;
1026 
1027  // Keep track of whether we moved the instruction so we know whether we
1028  // should move the MemoryAccess.
1029  bool MoveAccess = true;
1030  if (Repl) {
1031  // Repl is already in HoistPt: it remains in place.
1032  assert(allOperandsAvailable(Repl, DestBB) &&
1033  "instruction depends on operands that are not available");
1034  MoveAccess = false;
1035  } else {
1036  // When we do not find Repl in HoistPt, select the first in the list
1037  // and move it to HoistPt.
1038  Repl = InstructionsToHoist.front();
1039 
1040  // We can move Repl in HoistPt only when all operands are available.
1041  // The order in which hoistings are done may influence the availability
1042  // of operands.
1043  if (!allOperandsAvailable(Repl, DestBB)) {
1044  // When HoistingGeps there is nothing more we can do to make the
1045  // operands available: just continue.
1046  if (HoistingGeps)
1047  continue;
1048 
1049  // When not HoistingGeps we need to copy the GEPs.
1050  if (!makeGepOperandsAvailable(Repl, DestBB, InstructionsToHoist))
1051  continue;
1052  }
1053 
1054  // Move the instruction at the end of HoistPt.
1055  Instruction *Last = DestBB->getTerminator();
1056  MD->removeInstruction(Repl);
1057  Repl->moveBefore(Last);
1058 
1059  DFSNumber[Repl] = DFSNumber[Last]++;
1060  }
1061 
1062  NR += removeAndReplace(InstructionsToHoist, Repl, DestBB, MoveAccess);
1063 
1064  if (isa<LoadInst>(Repl))
1065  ++NL;
1066  else if (isa<StoreInst>(Repl))
1067  ++NS;
1068  else if (isa<CallInst>(Repl))
1069  ++NC;
1070  else // Scalar
1071  ++NI;
1072  }
1073 
1074  NumHoisted += NL + NS + NC + NI;
1075  NumRemoved += NR;
1076  NumLoadsHoisted += NL;
1077  NumStoresHoisted += NS;
1078  NumCallsHoisted += NC;
1079  return {NI, NL + NC + NS};
1080  }
1081 
1082  // Hoist all expressions. Returns Number of scalars hoisted
1083  // and number of non-scalars hoisted.
1084  std::pair<unsigned, unsigned> hoistExpressions(Function &F) {
1085  InsnInfo II;
1086  LoadInfo LI;
1087  StoreInfo SI;
1088  CallInfo CI;
1089  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
1090  int InstructionNb = 0;
1091  for (Instruction &I1 : *BB) {
1092  // If I1 cannot guarantee progress, subsequent instructions
1093  // in BB cannot be hoisted anyways.
1095  HoistBarrier.insert(BB);
1096  break;
1097  }
1098  // Only hoist the first instructions in BB up to MaxDepthInBB. Hoisting
1099  // deeper may increase the register pressure and compilation time.
1100  if (MaxDepthInBB != -1 && InstructionNb++ >= MaxDepthInBB)
1101  break;
1102 
1103  // Do not value number terminator instructions.
1104  if (I1.isTerminator())
1105  break;
1106 
1107  if (auto *Load = dyn_cast<LoadInst>(&I1))
1108  LI.insert(Load, VN);
1109  else if (auto *Store = dyn_cast<StoreInst>(&I1))
1110  SI.insert(Store, VN);
1111  else if (auto *Call = dyn_cast<CallInst>(&I1)) {
1112  if (auto *Intr = dyn_cast<IntrinsicInst>(Call)) {
1113  if (isa<DbgInfoIntrinsic>(Intr) ||
1114  Intr->getIntrinsicID() == Intrinsic::assume ||
1115  Intr->getIntrinsicID() == Intrinsic::sideeffect)
1116  continue;
1117  }
1118  if (Call->mayHaveSideEffects())
1119  break;
1120 
1121  if (Call->isConvergent())
1122  break;
1123 
1124  CI.insert(Call, VN);
1125  } else if (HoistingGeps || !isa<GetElementPtrInst>(&I1))
1126  // Do not hoist scalars past calls that may write to memory because
1127  // that could result in spills later. geps are handled separately.
1128  // TODO: We can relax this for targets like AArch64 as they have more
1129  // registers than X86.
1130  II.insert(&I1, VN);
1131  }
1132  }
1133 
1134  HoistingPointList HPL;
1135  computeInsertionPoints(II.getVNTable(), HPL, InsKind::Scalar);
1136  computeInsertionPoints(LI.getVNTable(), HPL, InsKind::Load);
1137  computeInsertionPoints(SI.getVNTable(), HPL, InsKind::Store);
1138  computeInsertionPoints(CI.getScalarVNTable(), HPL, InsKind::Scalar);
1139  computeInsertionPoints(CI.getLoadVNTable(), HPL, InsKind::Load);
1140  computeInsertionPoints(CI.getStoreVNTable(), HPL, InsKind::Store);
1141  return hoist(HPL);
1142  }
1143 };
1144 
1146 public:
1147  static char ID;
1148 
1151  }
1152 
1153  bool runOnFunction(Function &F) override {
1154  if (skipFunction(F))
1155  return false;
1156  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1157  auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1158  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1159  auto &MD = getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
1160  auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
1161 
1162  GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
1163  return G.run(F);
1164  }
1165 
1166  void getAnalysisUsage(AnalysisUsage &AU) const override {
1175  }
1176 };
1177 
1178 } // end namespace llvm
1179 
1183  AliasAnalysis &AA = AM.getResult<AAManager>(F);
1185  MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
1186  GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
1187  if (!G.run(F))
1188  return PreservedAnalyses::all();
1189 
1190  PreservedAnalyses PA;
1193  PA.preserve<GlobalsAA>();
1194  return PA;
1195 }
1196 
1197 char GVNHoistLegacyPass::ID = 0;
1198 
1200  "Early GVN Hoisting of Expressions", false, false)
1207  "Early GVN Hoisting of Expressions", false, false)
1208 
1209 FunctionPass *llvm::createGVNHoistPass() { return new GVNHoistLegacyPass(); }
Legacy wrapper pass to provide the GlobalsAAResult object.
uint64_t CallInst * C
Value * getValueOperand()
Definition: Instructions.h:399
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
static cl::opt< int > MaxDepthInBB("gvn-hoist-max-depth", cl::Hidden, cl::init(100), cl::desc("Hoist instructions from the beginning of the BB up to the " "maximum specified depth (default = 100, unlimited = -1)"))
static void r2(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E, int I, uint32_t *Buf)
Definition: SHA1.cpp:55
bool isSimple() const
Definition: Instructions.h:266
gvn hoist
When an instruction is found to only use loop invariant operands that is safe to hoist, this instruction is called to do the dirty work.
Definition: GVNHoist.cpp:1206
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Provides a lazy, caching interface for making common memory aliasing information queries, backed by LLVM&#39;s alias analysis passes.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Value * getPointerOperand(Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition: MemorySSA.h:255
This is the interface for a simple mod/ref and alias analysis over globals.
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1199
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVNHoist.cpp:1180
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess&#39;s for a given basic block.
Definition: MemorySSA.h:749
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
This class represents a function call, abstracting a target machine&#39;s calling convention.
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:373
bool isTerminator() const
Definition: Instruction.h:129
unsigned int rank(const Value *V) const
Definition: GVNHoist.cpp:307
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1042
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
FunctionPass * createGVNHoistPass()
Definition: GVNHoist.cpp:1209
An instruction for reading from memory.
Definition: Instructions.h:168
std::enable_if<!std::is_array< T >::value, std::unique_ptr< T > >::type make_unique(Args &&... args)
Constructs a new T() with the given args and returns a unique_ptr<T> which owns the object...
Definition: STLExtras.h:1199
This defines the Use class.
static void combineKnownMetadata(Instruction *ReplInst, Instruction *I)
Definition: GVNHoist.cpp:244
gvn Early GVN Hoisting of Expressions
Definition: GVNHoist.cpp:1206
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
Represents read-only accesses to memory.
Definition: MemorySSA.h:317
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
static uint32_t getAlignment(const MCSectionCOFF &Sec)
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:950
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
Definition: GVNHoist.cpp:1153
Constant Hoisting
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
void setDefiningBlocks(const SmallPtrSetImpl< BasicBlock *> &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, AliasAnalysis &AA)
Definition: MemorySSA.cpp:318
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
void insert(Instruction *I, GVN::ValueTable &VN)
Definition: GVNHoist.cpp:172
An analysis that produces MemoryDependenceResults for a function.
unsigned Intr
static cl::opt< int > MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10), cl::desc("Maximum length of dependent chains to hoist " "(default = 10, unlimited = -1)"))
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: GVNHoist.cpp:1166
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:251
INITIALIZE_PASS_BEGIN(GVNHoistLegacyPass, "gvn-hoist", "Early GVN Hoisting of Expressions", false, false) INITIALIZE_PASS_END(GVNHoistLegacyPass
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
bool run(Function &F)
Definition: GVNHoist.cpp:263
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref&#39;ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:711
void insert(LoadInst *Load, GVN::ValueTable &VN)
Definition: GVNHoist.cpp:187
The core GVN pass object.
Definition: GVN.h:68
void andIRFlags(const Value *V)
Logical &#39;and&#39; of any supported wrapping, exact, and fast-math flags of V and this instruction...
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2291
const VNtoInsns & getVNTable() const
Definition: GVNHoist.cpp:178
An instruction for storing to memory.
Definition: Instructions.h:310
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
const VNtoInsns & getLoadVNTable() const
Definition: GVNHoist.cpp:240
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Value * getOperand(unsigned i) const
Definition: User.h:170
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
idf_iterator< T > idf_begin(const T &G)
bool doesNotAccessMemory() const
Determine if the call does not access memory.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
idf_iterator< T > idf_end(const T &G)
const BasicBlock & getEntryBlock() const
Definition: Function.h:640
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:841
void insert(CallInst *Call, GVN::ValueTable &VN)
Definition: GVNHoist.cpp:224
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:55
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:74
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
const VNtoInsns & getScalarVNTable() const
Definition: GVNHoist.cpp:239
This class holds the mapping between values and value numbers.
Definition: GVN.h:89
This file provides the interface for LLVM&#39;s Global Value Numbering pass which eliminates fully redund...
SmallVector< Instruction *, 4 > SmallVecInsn
Definition: GVNHoist.cpp:119
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
This file contains the declarations for the subclasses of Constant, which represent the different fla...
A manager for alias analyses.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
bool mayThrow() const
Return true if this instruction may throw an exception.
const VNtoInsns & getStoreVNTable() const
Definition: GVNHoist.cpp:241
Represent the analysis usage information of a pass.
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:1049
Analysis pass providing a never-invalidated alias analysis result.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
size_t arg_size() const
Definition: Function.h:698
op_range operands()
Definition: User.h:238
Value * getPointerOperand()
Definition: Instructions.h:274
BasicBlock * Dest
Definition: GVNHoist.cpp:147
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1070
static void r1(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E, int I, uint32_t *Buf)
Definition: SHA1.cpp:49
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
size_t size() const
Definition: SmallVector.h:53
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance...
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:390
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
static cl::opt< int > MaxNumberOfBBSInPath("gvn-hoist-max-bbs", cl::Hidden, cl::init(4), cl::desc("Max number of basic blocks on the path between " "hoisting locations (default = 4, unlimited = -1)"))
const VNtoInsns & getVNTable() const
Definition: GVNHoist.cpp:194
std::pair< unsigned, unsigned > VNType
Definition: GVNHoist.cpp:129
bool operator==(const CHIArg &A)
Definition: GVNHoist.cpp:152
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:972
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
Definition: BasicBlock.h:387
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
unsigned getNumOperands() const
Definition: User.h:192
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1023
void calculate(SmallVectorImpl< BasicBlock *> &IDFBlocks)
Calculate iterated dominance frontiers.
bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in the same basic block, determine whether MemoryAccess A dominates MemoryA...
Definition: MemorySSA.cpp:1924
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:249
Analysis pass which computes a PostDominatorTree.
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:914
BasicBlock * getBlock() const
Definition: MemorySSA.h:157
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:123
GVNHoist(DominatorTree *DT, PostDominatorTree *PDT, AliasAnalysis *AA, MemoryDependenceResults *MD, MemorySSA *MSSA)
Definition: GVNHoist.cpp:258
#define NC
Definition: regutils.h:42
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
A range adaptor for a pair of iterators.
std::pair< BasicBlock *, SmallVecInsn > HoistingPointInfo
Definition: GVNHoist.cpp:124
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:245
typename SuperClass::iterator iterator
Definition: SmallVector.h:327
iterator_range< user_iterator > users()
Definition: Value.h:400
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Instruction * getMemoryInst() const
Get the instruction that this MemoryUse represents.
Definition: MemorySSA.h:252
void insert(StoreInst *Store, GVN::ValueTable &VN)
Definition: GVNHoist.cpp:204
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
void initializeGVNHoistLegacyPassPass(PassRegistry &)
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
iterator end()
Definition: DenseMap.h:79
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:729
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
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:501
const VNtoInsns & getVNTable() const
Definition: GVNHoist.cpp:213
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:181
static cl::opt< int > MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1), cl::desc("Max number of instructions to hoist " "(default unlimited = -1)"))
iterator_range< df_iterator< T > > depth_first(const T &G)
Determine the iterated dominance frontier, given a set of defining blocks, and optionally, a set of live-in blocks.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:394
LLVM Value Representation.
Definition: Value.h:73
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
succ_range successors(Instruction *I)
Definition: CFG.h:262
SmallVectorImpl< CHIArg >::iterator CHIIt
Definition: GVNHoist.cpp:156
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:87
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
bool isSimple() const
Definition: Instructions.h:391
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:478
const TerminatorInst * 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:138
Utility type to build an inheritance chain that makes it easy to rank overload candidates.
Definition: STLExtras.h:867
This header defines various interfaces for pass management in LLVM.
bool operator!=(const CHIArg &A)
Definition: GVNHoist.cpp:153
#define LLVM_DEBUG(X)
Definition: Debug.h:123
Instruction * I
Definition: GVNHoist.cpp:150
Value * getPointerOperand()
Definition: Instructions.h:402
const BasicBlock * getParent() const
Definition: Instruction.h:67