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