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