xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Scalar/GVNHoist.cpp (revision 7ef62cebc2f965b0f640263e179276928885e33d)
1 //===- GVNHoist.cpp - Hoist scalar and load expressions -------------------===//
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 hoists expressions from branches to a common dominator. It uses
10 // GVN (global value numbering) to discover expressions computing the same
11 // values. The primary goals of code-hoisting are:
12 // 1. To reduce the code size.
13 // 2. In some cases reduce critical path (by exposing more ILP).
14 //
15 // The algorithm factors out the reachability of values such that multiple
16 // queries to find reachability of values are fast. This is based on finding the
17 // ANTIC points in the CFG which do not change during hoisting. The ANTIC points
18 // are basically the dominance-frontiers in the inverse graph. So we introduce a
19 // data structure (CHI nodes) to keep track of values flowing out of a basic
20 // block. We only do this for values with multiple occurrences in the function
21 // as they are the potential hoistable candidates. This approach allows us to
22 // hoist instructions to a basic block with more than two successors, as well as
23 // deal with infinite loops in a trivial way.
24 //
25 // Limitations: This pass does not hoist fully redundant expressions because
26 // they are already handled by GVN-PRE. It is advisable to run gvn-hoist before
27 // and after gvn-pre because gvn-pre creates opportunities for more instructions
28 // to be hoisted.
29 //
30 // Hoisting may affect the performance in some cases. To mitigate that, hoisting
31 // is disabled in the following cases.
32 // 1. Scalars across calls.
33 // 2. geps when corresponding load/store cannot be hoisted.
34 //===----------------------------------------------------------------------===//
35 
36 #include "llvm/ADT/DenseMap.h"
37 #include "llvm/ADT/DenseSet.h"
38 #include "llvm/ADT/STLExtras.h"
39 #include "llvm/ADT/SmallPtrSet.h"
40 #include "llvm/ADT/SmallVector.h"
41 #include "llvm/ADT/Statistic.h"
42 #include "llvm/ADT/iterator_range.h"
43 #include "llvm/Analysis/AliasAnalysis.h"
44 #include "llvm/Analysis/GlobalsModRef.h"
45 #include "llvm/Analysis/IteratedDominanceFrontier.h"
46 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
47 #include "llvm/Analysis/MemorySSA.h"
48 #include "llvm/Analysis/MemorySSAUpdater.h"
49 #include "llvm/Analysis/PostDominators.h"
50 #include "llvm/Analysis/ValueTracking.h"
51 #include "llvm/IR/Argument.h"
52 #include "llvm/IR/BasicBlock.h"
53 #include "llvm/IR/CFG.h"
54 #include "llvm/IR/Constants.h"
55 #include "llvm/IR/Dominators.h"
56 #include "llvm/IR/Function.h"
57 #include "llvm/IR/Instruction.h"
58 #include "llvm/IR/Instructions.h"
59 #include "llvm/IR/IntrinsicInst.h"
60 #include "llvm/IR/LLVMContext.h"
61 #include "llvm/IR/PassManager.h"
62 #include "llvm/IR/Use.h"
63 #include "llvm/IR/User.h"
64 #include "llvm/IR/Value.h"
65 #include "llvm/InitializePasses.h"
66 #include "llvm/Pass.h"
67 #include "llvm/Support/Casting.h"
68 #include "llvm/Support/CommandLine.h"
69 #include "llvm/Support/Debug.h"
70 #include "llvm/Support/raw_ostream.h"
71 #include "llvm/Transforms/Scalar.h"
72 #include "llvm/Transforms/Scalar/GVN.h"
73 #include "llvm/Transforms/Utils/Local.h"
74 #include <algorithm>
75 #include <cassert>
76 #include <iterator>
77 #include <memory>
78 #include <utility>
79 #include <vector>
80 
81 using namespace llvm;
82 
83 #define DEBUG_TYPE "gvn-hoist"
84 
85 STATISTIC(NumHoisted, "Number of instructions hoisted");
86 STATISTIC(NumRemoved, "Number of instructions removed");
87 STATISTIC(NumLoadsHoisted, "Number of loads hoisted");
88 STATISTIC(NumLoadsRemoved, "Number of loads removed");
89 STATISTIC(NumStoresHoisted, "Number of stores hoisted");
90 STATISTIC(NumStoresRemoved, "Number of stores removed");
91 STATISTIC(NumCallsHoisted, "Number of calls hoisted");
92 STATISTIC(NumCallsRemoved, "Number of calls removed");
93 
94 static cl::opt<int>
95     MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1),
96                         cl::desc("Max number of instructions to hoist "
97                                  "(default unlimited = -1)"));
98 
99 static cl::opt<int> MaxNumberOfBBSInPath(
100     "gvn-hoist-max-bbs", cl::Hidden, cl::init(4),
101     cl::desc("Max number of basic blocks on the path between "
102              "hoisting locations (default = 4, unlimited = -1)"));
103 
104 static cl::opt<int> MaxDepthInBB(
105     "gvn-hoist-max-depth", cl::Hidden, cl::init(100),
106     cl::desc("Hoist instructions from the beginning of the BB up to the "
107              "maximum specified depth (default = 100, unlimited = -1)"));
108 
109 static cl::opt<int>
110     MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
111                    cl::desc("Maximum length of dependent chains to hoist "
112                             "(default = 10, unlimited = -1)"));
113 
114 namespace llvm {
115 
116 using BBSideEffectsSet = DenseMap<const BasicBlock *, bool>;
117 using SmallVecInsn = SmallVector<Instruction *, 4>;
118 using SmallVecImplInsn = SmallVectorImpl<Instruction *>;
119 
120 // Each element of a hoisting list contains the basic block where to hoist and
121 // a list of instructions to be hoisted.
122 using HoistingPointInfo = std::pair<BasicBlock *, SmallVecInsn>;
123 
124 using HoistingPointList = SmallVector<HoistingPointInfo, 4>;
125 
126 // A map from a pair of VNs to all the instructions with those VNs.
127 using VNType = std::pair<unsigned, uintptr_t>;
128 
129 using VNtoInsns = DenseMap<VNType, SmallVector<Instruction *, 4>>;
130 
131 // CHI keeps information about values flowing out of a basic block.  It is
132 // similar to PHI but in the inverse graph, and used for outgoing values on each
133 // edge. For conciseness, it is computed only for instructions with multiple
134 // occurrences in the CFG because they are the only hoistable candidates.
135 //     A (CHI[{V, B, I1}, {V, C, I2}]
136 //  /     \
137 // /       \
138 // B(I1)  C (I2)
139 // The Value number for both I1 and I2 is V, the CHI node will save the
140 // instruction as well as the edge where the value is flowing to.
141 struct CHIArg {
142   VNType VN;
143 
144   // Edge destination (shows the direction of flow), may not be where the I is.
145   BasicBlock *Dest;
146 
147   // The instruction (VN) which uses the values flowing out of CHI.
148   Instruction *I;
149 
150   bool operator==(const CHIArg &A) const { return VN == A.VN; }
151   bool operator!=(const CHIArg &A) const { return !(*this == A); }
152 };
153 
154 using CHIIt = SmallVectorImpl<CHIArg>::iterator;
155 using CHIArgs = iterator_range<CHIIt>;
156 using OutValuesType = DenseMap<BasicBlock *, SmallVector<CHIArg, 2>>;
157 using InValuesType =
158     DenseMap<BasicBlock *, SmallVector<std::pair<VNType, Instruction *>, 2>>;
159 
160 // An invalid value number Used when inserting a single value number into
161 // VNtoInsns.
162 enum : uintptr_t { InvalidVN = ~(uintptr_t)2 };
163 
164 // Records all scalar instructions candidate for code hoisting.
165 class InsnInfo {
166   VNtoInsns VNtoScalars;
167 
168 public:
169   // Inserts I and its value number in VNtoScalars.
170   void insert(Instruction *I, GVNPass::ValueTable &VN) {
171     // Scalar instruction.
172     unsigned V = VN.lookupOrAdd(I);
173     VNtoScalars[{V, InvalidVN}].push_back(I);
174   }
175 
176   const VNtoInsns &getVNTable() const { return VNtoScalars; }
177 };
178 
179 // Records all load instructions candidate for code hoisting.
180 class LoadInfo {
181   VNtoInsns VNtoLoads;
182 
183 public:
184   // Insert Load and the value number of its memory address in VNtoLoads.
185   void insert(LoadInst *Load, GVNPass::ValueTable &VN) {
186     if (Load->isSimple()) {
187       unsigned V = VN.lookupOrAdd(Load->getPointerOperand());
188       // With opaque pointers we may have loads from the same pointer with
189       // different result types, which should be disambiguated.
190       VNtoLoads[{V, (uintptr_t)Load->getType()}].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.
204   void insert(StoreInst *Store, GVNPass::ValueTable &VN) {
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.
224   void insert(CallInst *Call, GVNPass::ValueTable &VN) {
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[] = {LLVMContext::MD_tbaa,
246                                       LLVMContext::MD_alias_scope,
247                                       LLVMContext::MD_noalias,
248                                       LLVMContext::MD_range,
249                                       LLVMContext::MD_fpmath,
250                                       LLVMContext::MD_invariant_load,
251                                       LLVMContext::MD_invariant_group,
252                                       LLVMContext::MD_access_group};
253   combineMetadata(ReplInst, I, KnownIDs, true);
254 }
255 
256 // This pass hoists common computations across branches sharing common
257 // dominator. The primary goal is to reduce the code size, and in some
258 // cases reduce critical path (by exposing more ILP).
259 class GVNHoist {
260 public:
261   GVNHoist(DominatorTree *DT, PostDominatorTree *PDT, AliasAnalysis *AA,
262            MemoryDependenceResults *MD, MemorySSA *MSSA)
263       : DT(DT), PDT(PDT), AA(AA), MD(MD), MSSA(MSSA),
264         MSSAUpdater(std::make_unique<MemorySSAUpdater>(MSSA)) {
265     MSSA->ensureOptimizedUses();
266   }
267 
268   bool run(Function &F);
269 
270   // Copied from NewGVN.cpp
271   // This function provides global ranking of operations so that we can place
272   // them in a canonical order.  Note that rank alone is not necessarily enough
273   // for a complete ordering, as constants all have the same rank.  However,
274   // generally, we will simplify an operation with all constants so that it
275   // doesn't matter what order they appear in.
276   unsigned int rank(const Value *V) const;
277 
278 private:
279   GVNPass::ValueTable VN;
280   DominatorTree *DT;
281   PostDominatorTree *PDT;
282   AliasAnalysis *AA;
283   MemoryDependenceResults *MD;
284   MemorySSA *MSSA;
285   std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
286   DenseMap<const Value *, unsigned> DFSNumber;
287   BBSideEffectsSet BBSideEffects;
288   DenseSet<const BasicBlock *> HoistBarrier;
289   SmallVector<BasicBlock *, 32> IDFBlocks;
290   unsigned NumFuncArgs;
291   const bool HoistingGeps = false;
292 
293   enum InsKind { Unknown, Scalar, Load, Store };
294 
295   // Return true when there are exception handling in BB.
296   bool hasEH(const BasicBlock *BB);
297 
298   // Return true when I1 appears before I2 in the instructions of BB.
299   bool firstInBB(const Instruction *I1, const Instruction *I2) {
300     assert(I1->getParent() == I2->getParent());
301     unsigned I1DFS = DFSNumber.lookup(I1);
302     unsigned I2DFS = DFSNumber.lookup(I2);
303     assert(I1DFS && I2DFS);
304     return I1DFS < I2DFS;
305   }
306 
307   // Return true when there are memory uses of Def in BB.
308   bool hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
309                     const BasicBlock *BB);
310 
311   bool hasEHhelper(const BasicBlock *BB, const BasicBlock *SrcBB,
312                    int &NBBsOnAllPaths);
313 
314   // Return true when there are exception handling or loads of memory Def
315   // between Def and NewPt.  This function is only called for stores: Def is
316   // the MemoryDef of the store to be hoisted.
317 
318   // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
319   // return true when the counter NBBsOnAllPaths reaces 0, except when it is
320   // initialized to -1 which is unlimited.
321   bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
322                           int &NBBsOnAllPaths);
323 
324   // Return true when there are exception handling between HoistPt and BB.
325   // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
326   // return true when the counter NBBsOnAllPaths reaches 0, except when it is
327   // initialized to -1 which is unlimited.
328   bool hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,
329                    int &NBBsOnAllPaths);
330 
331   // Return true when it is safe to hoist a memory load or store U from OldPt
332   // to NewPt.
333   bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,
334                        MemoryUseOrDef *U, InsKind K, int &NBBsOnAllPaths);
335 
336   // Return true when it is safe to hoist scalar instructions from all blocks in
337   // WL to HoistBB.
338   bool safeToHoistScalar(const BasicBlock *HoistBB, const BasicBlock *BB,
339                          int &NBBsOnAllPaths) {
340     return !hasEHOnPath(HoistBB, BB, NBBsOnAllPaths);
341   }
342 
343   // In the inverse CFG, the dominance frontier of basic block (BB) is the
344   // point where ANTIC needs to be computed for instructions which are going
345   // to be hoisted. Since this point does not change during gvn-hoist,
346   // we compute it only once (on demand).
347   // The ides is inspired from:
348   // "Partial Redundancy Elimination in SSA Form"
349   // ROBERT KENNEDY, SUN CHAN, SHIN-MING LIU, RAYMOND LO, PENG TU and FRED CHOW
350   // They use similar idea in the forward graph to find fully redundant and
351   // partially redundant expressions, here it is used in the inverse graph to
352   // find fully anticipable instructions at merge point (post-dominator in
353   // the inverse CFG).
354   // Returns the edge via which an instruction in BB will get the values from.
355 
356   // Returns true when the values are flowing out to each edge.
357   bool valueAnticipable(CHIArgs C, Instruction *TI) const;
358 
359   // Check if it is safe to hoist values tracked by CHI in the range
360   // [Begin, End) and accumulate them in Safe.
361   void checkSafety(CHIArgs C, BasicBlock *BB, InsKind K,
362                    SmallVectorImpl<CHIArg> &Safe);
363 
364   using RenameStackType = DenseMap<VNType, SmallVector<Instruction *, 2>>;
365 
366   // Push all the VNs corresponding to BB into RenameStack.
367   void fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
368                        RenameStackType &RenameStack);
369 
370   void fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,
371                    RenameStackType &RenameStack);
372 
373   // Walk the post-dominator tree top-down and use a stack for each value to
374   // store the last value you see. When you hit a CHI from a given edge, the
375   // value to use as the argument is at the top of the stack, add the value to
376   // CHI and pop.
377   void insertCHI(InValuesType &ValueBBs, OutValuesType &CHIBBs) {
378     auto Root = PDT->getNode(nullptr);
379     if (!Root)
380       return;
381     // Depth first walk on PDom tree to fill the CHIargs at each PDF.
382     for (auto *Node : depth_first(Root)) {
383       BasicBlock *BB = Node->getBlock();
384       if (!BB)
385         continue;
386 
387       RenameStackType RenameStack;
388       // Collect all values in BB and push to stack.
389       fillRenameStack(BB, ValueBBs, RenameStack);
390 
391       // Fill outgoing values in each CHI corresponding to BB.
392       fillChiArgs(BB, CHIBBs, RenameStack);
393     }
394   }
395 
396   // Walk all the CHI-nodes to find ones which have a empty-entry and remove
397   // them Then collect all the instructions which are safe to hoist and see if
398   // they form a list of anticipable values. OutValues contains CHIs
399   // corresponding to each basic block.
400   void findHoistableCandidates(OutValuesType &CHIBBs, InsKind K,
401                                HoistingPointList &HPL);
402 
403   // Compute insertion points for each values which can be fully anticipated at
404   // a dominator. HPL contains all such values.
405   void computeInsertionPoints(const VNtoInsns &Map, HoistingPointList &HPL,
406                               InsKind K) {
407     // Sort VNs based on their rankings
408     std::vector<VNType> Ranks;
409     for (const auto &Entry : Map) {
410       Ranks.push_back(Entry.first);
411     }
412 
413     // TODO: Remove fully-redundant expressions.
414     // Get instruction from the Map, assume that all the Instructions
415     // with same VNs have same rank (this is an approximation).
416     llvm::sort(Ranks, [this, &Map](const VNType &r1, const VNType &r2) {
417       return (rank(*Map.lookup(r1).begin()) < rank(*Map.lookup(r2).begin()));
418     });
419 
420     // - Sort VNs according to their rank, and start with lowest ranked VN
421     // - Take a VN and for each instruction with same VN
422     //   - Find the dominance frontier in the inverse graph (PDF)
423     //   - Insert the chi-node at PDF
424     // - Remove the chi-nodes with missing entries
425     // - Remove values from CHI-nodes which do not truly flow out, e.g.,
426     //   modified along the path.
427     // - Collect the remaining values that are still anticipable
428     SmallVector<BasicBlock *, 2> IDFBlocks;
429     ReverseIDFCalculator IDFs(*PDT);
430     OutValuesType OutValue;
431     InValuesType InValue;
432     for (const auto &R : Ranks) {
433       const SmallVecInsn &V = Map.lookup(R);
434       if (V.size() < 2)
435         continue;
436       const VNType &VN = R;
437       SmallPtrSet<BasicBlock *, 2> VNBlocks;
438       for (const auto &I : V) {
439         BasicBlock *BBI = I->getParent();
440         if (!hasEH(BBI))
441           VNBlocks.insert(BBI);
442       }
443       // Compute the Post Dominance Frontiers of each basic block
444       // The dominance frontier of a live block X in the reverse
445       // control graph is the set of blocks upon which X is control
446       // dependent. The following sequence computes the set of blocks
447       // which currently have dead terminators that are control
448       // dependence sources of a block which is in NewLiveBlocks.
449       IDFs.setDefiningBlocks(VNBlocks);
450       IDFBlocks.clear();
451       IDFs.calculate(IDFBlocks);
452 
453       // Make a map of BB vs instructions to be hoisted.
454       for (unsigned i = 0; i < V.size(); ++i) {
455         InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
456       }
457       // Insert empty CHI node for this VN. This is used to factor out
458       // basic blocks where the ANTIC can potentially change.
459       CHIArg EmptyChi = {VN, nullptr, nullptr};
460       for (auto *IDFBB : IDFBlocks) {
461         for (unsigned i = 0; i < V.size(); ++i) {
462           // Ignore spurious PDFs.
463           if (DT->properlyDominates(IDFBB, V[i]->getParent())) {
464             OutValue[IDFBB].push_back(EmptyChi);
465             LLVM_DEBUG(dbgs() << "\nInserting a CHI for BB: "
466                               << IDFBB->getName() << ", for Insn: " << *V[i]);
467           }
468         }
469       }
470     }
471 
472     // Insert CHI args at each PDF to iterate on factored graph of
473     // control dependence.
474     insertCHI(InValue, OutValue);
475     // Using the CHI args inserted at each PDF, find fully anticipable values.
476     findHoistableCandidates(OutValue, K, HPL);
477   }
478 
479   // Return true when all operands of Instr are available at insertion point
480   // HoistPt. When limiting the number of hoisted expressions, one could hoist
481   // a load without hoisting its access function. So before hoisting any
482   // expression, make sure that all its operands are available at insert point.
483   bool allOperandsAvailable(const Instruction *I,
484                             const BasicBlock *HoistPt) const;
485 
486   // Same as allOperandsAvailable with recursive check for GEP operands.
487   bool allGepOperandsAvailable(const Instruction *I,
488                                const BasicBlock *HoistPt) const;
489 
490   // Make all operands of the GEP available.
491   void makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
492                          const SmallVecInsn &InstructionsToHoist,
493                          Instruction *Gep) const;
494 
495   void updateAlignment(Instruction *I, Instruction *Repl);
496 
497   // Remove all the instructions in Candidates and replace their usage with
498   // Repl. Returns the number of instructions removed.
499   unsigned rauw(const SmallVecInsn &Candidates, Instruction *Repl,
500                 MemoryUseOrDef *NewMemAcc);
501 
502   // Replace all Memory PHI usage with NewMemAcc.
503   void raMPHIuw(MemoryUseOrDef *NewMemAcc);
504 
505   // Remove all other instructions and replace them with Repl.
506   unsigned removeAndReplace(const SmallVecInsn &Candidates, Instruction *Repl,
507                             BasicBlock *DestBB, bool MoveAccess);
508 
509   // In the case Repl is a load or a store, we make all their GEPs
510   // available: GEPs are not hoisted by default to avoid the address
511   // computations to be hoisted without the associated load or store.
512   bool makeGepOperandsAvailable(Instruction *Repl, BasicBlock *HoistPt,
513                                 const SmallVecInsn &InstructionsToHoist) const;
514 
515   std::pair<unsigned, unsigned> hoist(HoistingPointList &HPL);
516 
517   // Hoist all expressions. Returns Number of scalars hoisted
518   // and number of non-scalars hoisted.
519   std::pair<unsigned, unsigned> hoistExpressions(Function &F);
520 };
521 
522 class GVNHoistLegacyPass : public FunctionPass {
523 public:
524   static char ID;
525 
526   GVNHoistLegacyPass() : FunctionPass(ID) {
527     initializeGVNHoistLegacyPassPass(*PassRegistry::getPassRegistry());
528   }
529 
530   bool runOnFunction(Function &F) override {
531     if (skipFunction(F))
532       return false;
533     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
534     auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
535     auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
536     auto &MD = getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
537     auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
538 
539     GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
540     return G.run(F);
541   }
542 
543   void getAnalysisUsage(AnalysisUsage &AU) const override {
544     AU.addRequired<DominatorTreeWrapperPass>();
545     AU.addRequired<PostDominatorTreeWrapperPass>();
546     AU.addRequired<AAResultsWrapperPass>();
547     AU.addRequired<MemoryDependenceWrapperPass>();
548     AU.addRequired<MemorySSAWrapperPass>();
549     AU.addPreserved<DominatorTreeWrapperPass>();
550     AU.addPreserved<MemorySSAWrapperPass>();
551     AU.addPreserved<GlobalsAAWrapperPass>();
552   }
553 };
554 
555 bool GVNHoist::run(Function &F) {
556   NumFuncArgs = F.arg_size();
557   VN.setDomTree(DT);
558   VN.setAliasAnalysis(AA);
559   VN.setMemDep(MD);
560   bool Res = false;
561   // Perform DFS Numbering of instructions.
562   unsigned BBI = 0;
563   for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) {
564     DFSNumber[BB] = ++BBI;
565     unsigned I = 0;
566     for (const auto &Inst : *BB)
567       DFSNumber[&Inst] = ++I;
568   }
569 
570   int ChainLength = 0;
571 
572   // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
573   while (true) {
574     if (MaxChainLength != -1 && ++ChainLength >= MaxChainLength)
575       return Res;
576 
577     auto HoistStat = hoistExpressions(F);
578     if (HoistStat.first + HoistStat.second == 0)
579       return Res;
580 
581     if (HoistStat.second > 0)
582       // To address a limitation of the current GVN, we need to rerun the
583       // hoisting after we hoisted loads or stores in order to be able to
584       // hoist all scalars dependent on the hoisted ld/st.
585       VN.clear();
586 
587     Res = true;
588   }
589 
590   return Res;
591 }
592 
593 unsigned int GVNHoist::rank(const Value *V) const {
594   // Prefer constants to undef to anything else
595   // Undef is a constant, have to check it first.
596   // Prefer smaller constants to constantexprs
597   if (isa<ConstantExpr>(V))
598     return 2;
599   if (isa<UndefValue>(V))
600     return 1;
601   if (isa<Constant>(V))
602     return 0;
603   else if (auto *A = dyn_cast<Argument>(V))
604     return 3 + A->getArgNo();
605 
606   // Need to shift the instruction DFS by number of arguments + 3 to account
607   // for the constant and argument ranking above.
608   auto Result = DFSNumber.lookup(V);
609   if (Result > 0)
610     return 4 + NumFuncArgs + Result;
611   // Unreachable or something else, just return a really large number.
612   return ~0;
613 }
614 
615 bool GVNHoist::hasEH(const BasicBlock *BB) {
616   auto It = BBSideEffects.find(BB);
617   if (It != BBSideEffects.end())
618     return It->second;
619 
620   if (BB->isEHPad() || BB->hasAddressTaken()) {
621     BBSideEffects[BB] = true;
622     return true;
623   }
624 
625   if (BB->getTerminator()->mayThrow()) {
626     BBSideEffects[BB] = true;
627     return true;
628   }
629 
630   BBSideEffects[BB] = false;
631   return false;
632 }
633 
634 bool GVNHoist::hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
635                             const BasicBlock *BB) {
636   const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
637   if (!Acc)
638     return false;
639 
640   Instruction *OldPt = Def->getMemoryInst();
641   const BasicBlock *OldBB = OldPt->getParent();
642   const BasicBlock *NewBB = NewPt->getParent();
643   bool ReachedNewPt = false;
644 
645   for (const MemoryAccess &MA : *Acc)
646     if (const MemoryUse *MU = dyn_cast<MemoryUse>(&MA)) {
647       Instruction *Insn = MU->getMemoryInst();
648 
649       // Do not check whether MU aliases Def when MU occurs after OldPt.
650       if (BB == OldBB && firstInBB(OldPt, Insn))
651         break;
652 
653       // Do not check whether MU aliases Def when MU occurs before NewPt.
654       if (BB == NewBB) {
655         if (!ReachedNewPt) {
656           if (firstInBB(Insn, NewPt))
657             continue;
658           ReachedNewPt = true;
659         }
660       }
661       if (MemorySSAUtil::defClobbersUseOrDef(Def, MU, *AA))
662         return true;
663     }
664 
665   return false;
666 }
667 
668 bool GVNHoist::hasEHhelper(const BasicBlock *BB, const BasicBlock *SrcBB,
669                            int &NBBsOnAllPaths) {
670   // Stop walk once the limit is reached.
671   if (NBBsOnAllPaths == 0)
672     return true;
673 
674   // Impossible to hoist with exceptions on the path.
675   if (hasEH(BB))
676     return true;
677 
678   // No such instruction after HoistBarrier in a basic block was
679   // selected for hoisting so instructions selected within basic block with
680   // a hoist barrier can be hoisted.
681   if ((BB != SrcBB) && HoistBarrier.count(BB))
682     return true;
683 
684   return false;
685 }
686 
687 bool GVNHoist::hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
688                                   int &NBBsOnAllPaths) {
689   const BasicBlock *NewBB = NewPt->getParent();
690   const BasicBlock *OldBB = Def->getBlock();
691   assert(DT->dominates(NewBB, OldBB) && "invalid path");
692   assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&
693          "def does not dominate new hoisting point");
694 
695   // Walk all basic blocks reachable in depth-first iteration on the inverse
696   // CFG from OldBB to NewBB. These blocks are all the blocks that may be
697   // executed between the execution of NewBB and OldBB. Hoisting an expression
698   // from OldBB into NewBB has to be safe on all execution paths.
699   for (auto I = idf_begin(OldBB), E = idf_end(OldBB); I != E;) {
700     const BasicBlock *BB = *I;
701     if (BB == NewBB) {
702       // Stop traversal when reaching HoistPt.
703       I.skipChildren();
704       continue;
705     }
706 
707     if (hasEHhelper(BB, OldBB, NBBsOnAllPaths))
708       return true;
709 
710     // Check that we do not move a store past loads.
711     if (hasMemoryUse(NewPt, Def, BB))
712       return true;
713 
714     // -1 is unlimited number of blocks on all paths.
715     if (NBBsOnAllPaths != -1)
716       --NBBsOnAllPaths;
717 
718     ++I;
719   }
720 
721   return false;
722 }
723 
724 bool GVNHoist::hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,
725                            int &NBBsOnAllPaths) {
726   assert(DT->dominates(HoistPt, SrcBB) && "Invalid path");
727 
728   // Walk all basic blocks reachable in depth-first iteration on
729   // the inverse CFG from BBInsn to NewHoistPt. These blocks are all the
730   // blocks that may be executed between the execution of NewHoistPt and
731   // BBInsn. Hoisting an expression from BBInsn into NewHoistPt has to be safe
732   // on all execution paths.
733   for (auto I = idf_begin(SrcBB), E = idf_end(SrcBB); I != E;) {
734     const BasicBlock *BB = *I;
735     if (BB == HoistPt) {
736       // Stop traversal when reaching NewHoistPt.
737       I.skipChildren();
738       continue;
739     }
740 
741     if (hasEHhelper(BB, SrcBB, NBBsOnAllPaths))
742       return true;
743 
744     // -1 is unlimited number of blocks on all paths.
745     if (NBBsOnAllPaths != -1)
746       --NBBsOnAllPaths;
747 
748     ++I;
749   }
750 
751   return false;
752 }
753 
754 bool GVNHoist::safeToHoistLdSt(const Instruction *NewPt,
755                                const Instruction *OldPt, MemoryUseOrDef *U,
756                                GVNHoist::InsKind K, int &NBBsOnAllPaths) {
757   // In place hoisting is safe.
758   if (NewPt == OldPt)
759     return true;
760 
761   const BasicBlock *NewBB = NewPt->getParent();
762   const BasicBlock *OldBB = OldPt->getParent();
763   const BasicBlock *UBB = U->getBlock();
764 
765   // Check for dependences on the Memory SSA.
766   MemoryAccess *D = U->getDefiningAccess();
767   BasicBlock *DBB = D->getBlock();
768   if (DT->properlyDominates(NewBB, DBB))
769     // Cannot move the load or store to NewBB above its definition in DBB.
770     return false;
771 
772   if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D))
773     if (auto *UD = dyn_cast<MemoryUseOrDef>(D))
774       if (!firstInBB(UD->getMemoryInst(), NewPt))
775         // Cannot move the load or store to NewPt above its definition in D.
776         return false;
777 
778   // Check for unsafe hoistings due to side effects.
779   if (K == InsKind::Store) {
780     if (hasEHOrLoadsOnPath(NewPt, cast<MemoryDef>(U), NBBsOnAllPaths))
781       return false;
782   } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
783     return false;
784 
785   if (UBB == NewBB) {
786     if (DT->properlyDominates(DBB, NewBB))
787       return true;
788     assert(UBB == DBB);
789     assert(MSSA->locallyDominates(D, U));
790   }
791 
792   // No side effects: it is safe to hoist.
793   return true;
794 }
795 
796 bool GVNHoist::valueAnticipable(CHIArgs C, Instruction *TI) const {
797   if (TI->getNumSuccessors() > (unsigned)size(C))
798     return false; // Not enough args in this CHI.
799 
800   for (auto CHI : C) {
801     // Find if all the edges have values flowing out of BB.
802     if (!llvm::is_contained(successors(TI), CHI.Dest))
803       return false;
804   }
805   return true;
806 }
807 
808 void GVNHoist::checkSafety(CHIArgs C, BasicBlock *BB, GVNHoist::InsKind K,
809                            SmallVectorImpl<CHIArg> &Safe) {
810   int NumBBsOnAllPaths = MaxNumberOfBBSInPath;
811   for (auto CHI : C) {
812     Instruction *Insn = CHI.I;
813     if (!Insn) // No instruction was inserted in this CHI.
814       continue;
815     if (K == InsKind::Scalar) {
816       if (safeToHoistScalar(BB, Insn->getParent(), NumBBsOnAllPaths))
817         Safe.push_back(CHI);
818     } else {
819       auto *T = BB->getTerminator();
820       if (MemoryUseOrDef *UD = MSSA->getMemoryAccess(Insn))
821         if (safeToHoistLdSt(T, Insn, UD, K, NumBBsOnAllPaths))
822           Safe.push_back(CHI);
823     }
824   }
825 }
826 
827 void GVNHoist::fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
828                                GVNHoist::RenameStackType &RenameStack) {
829   auto it1 = ValueBBs.find(BB);
830   if (it1 != ValueBBs.end()) {
831     // Iterate in reverse order to keep lower ranked values on the top.
832     LLVM_DEBUG(dbgs() << "\nVisiting: " << BB->getName()
833                       << " for pushing instructions on stack";);
834     for (std::pair<VNType, Instruction *> &VI : reverse(it1->second)) {
835       // Get the value of instruction I
836       LLVM_DEBUG(dbgs() << "\nPushing on stack: " << *VI.second);
837       RenameStack[VI.first].push_back(VI.second);
838     }
839   }
840 }
841 
842 void GVNHoist::fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,
843                            GVNHoist::RenameStackType &RenameStack) {
844   // For each *predecessor* (because Post-DOM) of BB check if it has a CHI
845   for (auto *Pred : predecessors(BB)) {
846     auto P = CHIBBs.find(Pred);
847     if (P == CHIBBs.end()) {
848       continue;
849     }
850     LLVM_DEBUG(dbgs() << "\nLooking at CHIs in: " << Pred->getName(););
851     // A CHI is found (BB -> Pred is an edge in the CFG)
852     // Pop the stack until Top(V) = Ve.
853     auto &VCHI = P->second;
854     for (auto It = VCHI.begin(), E = VCHI.end(); It != E;) {
855       CHIArg &C = *It;
856       if (!C.Dest) {
857         auto si = RenameStack.find(C.VN);
858         // The Basic Block where CHI is must dominate the value we want to
859         // track in a CHI. In the PDom walk, there can be values in the
860         // stack which are not control dependent e.g., nested loop.
861         if (si != RenameStack.end() && si->second.size() &&
862             DT->properlyDominates(Pred, si->second.back()->getParent())) {
863           C.Dest = BB;                     // Assign the edge
864           C.I = si->second.pop_back_val(); // Assign the argument
865           LLVM_DEBUG(dbgs()
866                      << "\nCHI Inserted in BB: " << C.Dest->getName() << *C.I
867                      << ", VN: " << C.VN.first << ", " << C.VN.second);
868         }
869         // Move to next CHI of a different value
870         It = std::find_if(It, VCHI.end(), [It](CHIArg &A) { return A != *It; });
871       } else
872         ++It;
873     }
874   }
875 }
876 
877 void GVNHoist::findHoistableCandidates(OutValuesType &CHIBBs,
878                                        GVNHoist::InsKind K,
879                                        HoistingPointList &HPL) {
880   auto cmpVN = [](const CHIArg &A, const CHIArg &B) { return A.VN < B.VN; };
881 
882   // CHIArgs now have the outgoing values, so check for anticipability and
883   // accumulate hoistable candidates in HPL.
884   for (std::pair<BasicBlock *, SmallVector<CHIArg, 2>> &A : CHIBBs) {
885     BasicBlock *BB = A.first;
886     SmallVectorImpl<CHIArg> &CHIs = A.second;
887     // Vector of PHIs contains PHIs for different instructions.
888     // Sort the args according to their VNs, such that identical
889     // instructions are together.
890     llvm::stable_sort(CHIs, cmpVN);
891     auto TI = BB->getTerminator();
892     auto B = CHIs.begin();
893     // [PreIt, PHIIt) form a range of CHIs which have identical VNs.
894     auto PHIIt = llvm::find_if(CHIs, [B](CHIArg &A) { return A != *B; });
895     auto PrevIt = CHIs.begin();
896     while (PrevIt != PHIIt) {
897       // Collect values which satisfy safety checks.
898       SmallVector<CHIArg, 2> Safe;
899       // We check for safety first because there might be multiple values in
900       // the same path, some of which are not safe to be hoisted, but overall
901       // each edge has at least one value which can be hoisted, making the
902       // value anticipable along that path.
903       checkSafety(make_range(PrevIt, PHIIt), BB, K, Safe);
904 
905       // List of safe values should be anticipable at TI.
906       if (valueAnticipable(make_range(Safe.begin(), Safe.end()), TI)) {
907         HPL.push_back({BB, SmallVecInsn()});
908         SmallVecInsn &V = HPL.back().second;
909         for (auto B : Safe)
910           V.push_back(B.I);
911       }
912 
913       // Check other VNs
914       PrevIt = PHIIt;
915       PHIIt = std::find_if(PrevIt, CHIs.end(),
916                            [PrevIt](CHIArg &A) { return A != *PrevIt; });
917     }
918   }
919 }
920 
921 bool GVNHoist::allOperandsAvailable(const Instruction *I,
922                                     const BasicBlock *HoistPt) const {
923   for (const Use &Op : I->operands())
924     if (const auto *Inst = dyn_cast<Instruction>(&Op))
925       if (!DT->dominates(Inst->getParent(), HoistPt))
926         return false;
927 
928   return true;
929 }
930 
931 bool GVNHoist::allGepOperandsAvailable(const Instruction *I,
932                                        const BasicBlock *HoistPt) const {
933   for (const Use &Op : I->operands())
934     if (const auto *Inst = dyn_cast<Instruction>(&Op))
935       if (!DT->dominates(Inst->getParent(), HoistPt)) {
936         if (const GetElementPtrInst *GepOp =
937                 dyn_cast<GetElementPtrInst>(Inst)) {
938           if (!allGepOperandsAvailable(GepOp, HoistPt))
939             return false;
940           // Gep is available if all operands of GepOp are available.
941         } else {
942           // Gep is not available if it has operands other than GEPs that are
943           // defined in blocks not dominating HoistPt.
944           return false;
945         }
946       }
947   return true;
948 }
949 
950 void GVNHoist::makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
951                                  const SmallVecInsn &InstructionsToHoist,
952                                  Instruction *Gep) const {
953   assert(allGepOperandsAvailable(Gep, HoistPt) && "GEP operands not available");
954 
955   Instruction *ClonedGep = Gep->clone();
956   for (unsigned i = 0, e = Gep->getNumOperands(); i != e; ++i)
957     if (Instruction *Op = dyn_cast<Instruction>(Gep->getOperand(i))) {
958       // Check whether the operand is already available.
959       if (DT->dominates(Op->getParent(), HoistPt))
960         continue;
961 
962       // As a GEP can refer to other GEPs, recursively make all the operands
963       // of this GEP available at HoistPt.
964       if (GetElementPtrInst *GepOp = dyn_cast<GetElementPtrInst>(Op))
965         makeGepsAvailable(ClonedGep, HoistPt, InstructionsToHoist, GepOp);
966     }
967 
968   // Copy Gep and replace its uses in Repl with ClonedGep.
969   ClonedGep->insertBefore(HoistPt->getTerminator());
970 
971   // Conservatively discard any optimization hints, they may differ on the
972   // other paths.
973   ClonedGep->dropUnknownNonDebugMetadata();
974 
975   // If we have optimization hints which agree with each other along different
976   // paths, preserve them.
977   for (const Instruction *OtherInst : InstructionsToHoist) {
978     const GetElementPtrInst *OtherGep;
979     if (auto *OtherLd = dyn_cast<LoadInst>(OtherInst))
980       OtherGep = cast<GetElementPtrInst>(OtherLd->getPointerOperand());
981     else
982       OtherGep = cast<GetElementPtrInst>(
983           cast<StoreInst>(OtherInst)->getPointerOperand());
984     ClonedGep->andIRFlags(OtherGep);
985   }
986 
987   // Replace uses of Gep with ClonedGep in Repl.
988   Repl->replaceUsesOfWith(Gep, ClonedGep);
989 }
990 
991 void GVNHoist::updateAlignment(Instruction *I, Instruction *Repl) {
992   if (auto *ReplacementLoad = dyn_cast<LoadInst>(Repl)) {
993     ReplacementLoad->setAlignment(
994         std::min(ReplacementLoad->getAlign(), cast<LoadInst>(I)->getAlign()));
995     ++NumLoadsRemoved;
996   } else if (auto *ReplacementStore = dyn_cast<StoreInst>(Repl)) {
997     ReplacementStore->setAlignment(
998         std::min(ReplacementStore->getAlign(), cast<StoreInst>(I)->getAlign()));
999     ++NumStoresRemoved;
1000   } else if (auto *ReplacementAlloca = dyn_cast<AllocaInst>(Repl)) {
1001     ReplacementAlloca->setAlignment(std::max(ReplacementAlloca->getAlign(),
1002                                              cast<AllocaInst>(I)->getAlign()));
1003   } else if (isa<CallInst>(Repl)) {
1004     ++NumCallsRemoved;
1005   }
1006 }
1007 
1008 unsigned GVNHoist::rauw(const SmallVecInsn &Candidates, Instruction *Repl,
1009                         MemoryUseOrDef *NewMemAcc) {
1010   unsigned NR = 0;
1011   for (Instruction *I : Candidates) {
1012     if (I != Repl) {
1013       ++NR;
1014       updateAlignment(I, Repl);
1015       if (NewMemAcc) {
1016         // Update the uses of the old MSSA access with NewMemAcc.
1017         MemoryAccess *OldMA = MSSA->getMemoryAccess(I);
1018         OldMA->replaceAllUsesWith(NewMemAcc);
1019         MSSAUpdater->removeMemoryAccess(OldMA);
1020       }
1021 
1022       Repl->andIRFlags(I);
1023       combineKnownMetadata(Repl, I);
1024       I->replaceAllUsesWith(Repl);
1025       // Also invalidate the Alias Analysis cache.
1026       MD->removeInstruction(I);
1027       I->eraseFromParent();
1028     }
1029   }
1030   return NR;
1031 }
1032 
1033 void GVNHoist::raMPHIuw(MemoryUseOrDef *NewMemAcc) {
1034   SmallPtrSet<MemoryPhi *, 4> UsePhis;
1035   for (User *U : NewMemAcc->users())
1036     if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(U))
1037       UsePhis.insert(Phi);
1038 
1039   for (MemoryPhi *Phi : UsePhis) {
1040     auto In = Phi->incoming_values();
1041     if (llvm::all_of(In, [&](Use &U) { return U == NewMemAcc; })) {
1042       Phi->replaceAllUsesWith(NewMemAcc);
1043       MSSAUpdater->removeMemoryAccess(Phi);
1044     }
1045   }
1046 }
1047 
1048 unsigned GVNHoist::removeAndReplace(const SmallVecInsn &Candidates,
1049                                     Instruction *Repl, BasicBlock *DestBB,
1050                                     bool MoveAccess) {
1051   MemoryUseOrDef *NewMemAcc = MSSA->getMemoryAccess(Repl);
1052   if (MoveAccess && NewMemAcc) {
1053     // The definition of this ld/st will not change: ld/st hoisting is
1054     // legal when the ld/st is not moved past its current definition.
1055     MSSAUpdater->moveToPlace(NewMemAcc, DestBB, MemorySSA::BeforeTerminator);
1056   }
1057 
1058   // Replace all other instructions with Repl with memory access NewMemAcc.
1059   unsigned NR = rauw(Candidates, Repl, NewMemAcc);
1060 
1061   // Remove MemorySSA phi nodes with the same arguments.
1062   if (NewMemAcc)
1063     raMPHIuw(NewMemAcc);
1064   return NR;
1065 }
1066 
1067 bool GVNHoist::makeGepOperandsAvailable(
1068     Instruction *Repl, BasicBlock *HoistPt,
1069     const SmallVecInsn &InstructionsToHoist) const {
1070   // Check whether the GEP of a ld/st can be synthesized at HoistPt.
1071   GetElementPtrInst *Gep = nullptr;
1072   Instruction *Val = nullptr;
1073   if (auto *Ld = dyn_cast<LoadInst>(Repl)) {
1074     Gep = dyn_cast<GetElementPtrInst>(Ld->getPointerOperand());
1075   } else if (auto *St = dyn_cast<StoreInst>(Repl)) {
1076     Gep = dyn_cast<GetElementPtrInst>(St->getPointerOperand());
1077     Val = dyn_cast<Instruction>(St->getValueOperand());
1078     // Check that the stored value is available.
1079     if (Val) {
1080       if (isa<GetElementPtrInst>(Val)) {
1081         // Check whether we can compute the GEP at HoistPt.
1082         if (!allGepOperandsAvailable(Val, HoistPt))
1083           return false;
1084       } else if (!DT->dominates(Val->getParent(), HoistPt))
1085         return false;
1086     }
1087   }
1088 
1089   // Check whether we can compute the Gep at HoistPt.
1090   if (!Gep || !allGepOperandsAvailable(Gep, HoistPt))
1091     return false;
1092 
1093   makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Gep);
1094 
1095   if (Val && isa<GetElementPtrInst>(Val))
1096     makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Val);
1097 
1098   return true;
1099 }
1100 
1101 std::pair<unsigned, unsigned> GVNHoist::hoist(HoistingPointList &HPL) {
1102   unsigned NI = 0, NL = 0, NS = 0, NC = 0, NR = 0;
1103   for (const HoistingPointInfo &HP : HPL) {
1104     // Find out whether we already have one of the instructions in HoistPt,
1105     // in which case we do not have to move it.
1106     BasicBlock *DestBB = HP.first;
1107     const SmallVecInsn &InstructionsToHoist = HP.second;
1108     Instruction *Repl = nullptr;
1109     for (Instruction *I : InstructionsToHoist)
1110       if (I->getParent() == DestBB)
1111         // If there are two instructions in HoistPt to be hoisted in place:
1112         // update Repl to be the first one, such that we can rename the uses
1113         // of the second based on the first.
1114         if (!Repl || firstInBB(I, Repl))
1115           Repl = I;
1116 
1117     // Keep track of whether we moved the instruction so we know whether we
1118     // should move the MemoryAccess.
1119     bool MoveAccess = true;
1120     if (Repl) {
1121       // Repl is already in HoistPt: it remains in place.
1122       assert(allOperandsAvailable(Repl, DestBB) &&
1123              "instruction depends on operands that are not available");
1124       MoveAccess = false;
1125     } else {
1126       // When we do not find Repl in HoistPt, select the first in the list
1127       // and move it to HoistPt.
1128       Repl = InstructionsToHoist.front();
1129 
1130       // We can move Repl in HoistPt only when all operands are available.
1131       // The order in which hoistings are done may influence the availability
1132       // of operands.
1133       if (!allOperandsAvailable(Repl, DestBB)) {
1134         // When HoistingGeps there is nothing more we can do to make the
1135         // operands available: just continue.
1136         if (HoistingGeps)
1137           continue;
1138 
1139         // When not HoistingGeps we need to copy the GEPs.
1140         if (!makeGepOperandsAvailable(Repl, DestBB, InstructionsToHoist))
1141           continue;
1142       }
1143 
1144       // Move the instruction at the end of HoistPt.
1145       Instruction *Last = DestBB->getTerminator();
1146       MD->removeInstruction(Repl);
1147       Repl->moveBefore(Last);
1148 
1149       DFSNumber[Repl] = DFSNumber[Last]++;
1150     }
1151 
1152     // Drop debug location as per debug info update guide.
1153     Repl->dropLocation();
1154     NR += removeAndReplace(InstructionsToHoist, Repl, DestBB, MoveAccess);
1155 
1156     if (isa<LoadInst>(Repl))
1157       ++NL;
1158     else if (isa<StoreInst>(Repl))
1159       ++NS;
1160     else if (isa<CallInst>(Repl))
1161       ++NC;
1162     else // Scalar
1163       ++NI;
1164   }
1165 
1166   if (MSSA && VerifyMemorySSA)
1167     MSSA->verifyMemorySSA();
1168 
1169   NumHoisted += NL + NS + NC + NI;
1170   NumRemoved += NR;
1171   NumLoadsHoisted += NL;
1172   NumStoresHoisted += NS;
1173   NumCallsHoisted += NC;
1174   return {NI, NL + NC + NS};
1175 }
1176 
1177 std::pair<unsigned, unsigned> GVNHoist::hoistExpressions(Function &F) {
1178   InsnInfo II;
1179   LoadInfo LI;
1180   StoreInfo SI;
1181   CallInfo CI;
1182   for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
1183     int InstructionNb = 0;
1184     for (Instruction &I1 : *BB) {
1185       // If I1 cannot guarantee progress, subsequent instructions
1186       // in BB cannot be hoisted anyways.
1187       if (!isGuaranteedToTransferExecutionToSuccessor(&I1)) {
1188         HoistBarrier.insert(BB);
1189         break;
1190       }
1191       // Only hoist the first instructions in BB up to MaxDepthInBB. Hoisting
1192       // deeper may increase the register pressure and compilation time.
1193       if (MaxDepthInBB != -1 && InstructionNb++ >= MaxDepthInBB)
1194         break;
1195 
1196       // Do not value number terminator instructions.
1197       if (I1.isTerminator())
1198         break;
1199 
1200       if (auto *Load = dyn_cast<LoadInst>(&I1))
1201         LI.insert(Load, VN);
1202       else if (auto *Store = dyn_cast<StoreInst>(&I1))
1203         SI.insert(Store, VN);
1204       else if (auto *Call = dyn_cast<CallInst>(&I1)) {
1205         if (auto *Intr = dyn_cast<IntrinsicInst>(Call)) {
1206           if (isa<DbgInfoIntrinsic>(Intr) ||
1207               Intr->getIntrinsicID() == Intrinsic::assume ||
1208               Intr->getIntrinsicID() == Intrinsic::sideeffect)
1209             continue;
1210         }
1211         if (Call->mayHaveSideEffects())
1212           break;
1213 
1214         if (Call->isConvergent())
1215           break;
1216 
1217         CI.insert(Call, VN);
1218       } else if (HoistingGeps || !isa<GetElementPtrInst>(&I1))
1219         // Do not hoist scalars past calls that may write to memory because
1220         // that could result in spills later. geps are handled separately.
1221         // TODO: We can relax this for targets like AArch64 as they have more
1222         // registers than X86.
1223         II.insert(&I1, VN);
1224     }
1225   }
1226 
1227   HoistingPointList HPL;
1228   computeInsertionPoints(II.getVNTable(), HPL, InsKind::Scalar);
1229   computeInsertionPoints(LI.getVNTable(), HPL, InsKind::Load);
1230   computeInsertionPoints(SI.getVNTable(), HPL, InsKind::Store);
1231   computeInsertionPoints(CI.getScalarVNTable(), HPL, InsKind::Scalar);
1232   computeInsertionPoints(CI.getLoadVNTable(), HPL, InsKind::Load);
1233   computeInsertionPoints(CI.getStoreVNTable(), HPL, InsKind::Store);
1234   return hoist(HPL);
1235 }
1236 
1237 } // end namespace llvm
1238 
1239 PreservedAnalyses GVNHoistPass::run(Function &F, FunctionAnalysisManager &AM) {
1240   DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
1241   PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
1242   AliasAnalysis &AA = AM.getResult<AAManager>(F);
1243   MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
1244   MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
1245   GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
1246   if (!G.run(F))
1247     return PreservedAnalyses::all();
1248 
1249   PreservedAnalyses PA;
1250   PA.preserve<DominatorTreeAnalysis>();
1251   PA.preserve<MemorySSAAnalysis>();
1252   return PA;
1253 }
1254 
1255 char GVNHoistLegacyPass::ID = 0;
1256 
1257 INITIALIZE_PASS_BEGIN(GVNHoistLegacyPass, "gvn-hoist",
1258                       "Early GVN Hoisting of Expressions", false, false)
1259 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
1260 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
1261 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1262 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
1263 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1264 INITIALIZE_PASS_END(GVNHoistLegacyPass, "gvn-hoist",
1265                     "Early GVN Hoisting of Expressions", false, false)
1266 
1267 FunctionPass *llvm::createGVNHoistPass() { return new GVNHoistLegacyPass(); }
1268