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

source code of llvm/lib/Transforms/Scalar/GVNHoist.cpp