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 | |
78 | using namespace llvm; |
79 | |
80 | #define DEBUG_TYPE "gvn-hoist" |
81 | |
82 | STATISTIC(NumHoisted, "Number of instructions hoisted" ); |
83 | STATISTIC(NumRemoved, "Number of instructions removed" ); |
84 | STATISTIC(NumLoadsHoisted, "Number of loads hoisted" ); |
85 | STATISTIC(NumLoadsRemoved, "Number of loads removed" ); |
86 | STATISTIC(NumStoresHoisted, "Number of stores hoisted" ); |
87 | STATISTIC(NumStoresRemoved, "Number of stores removed" ); |
88 | STATISTIC(NumCallsHoisted, "Number of calls hoisted" ); |
89 | STATISTIC(NumCallsRemoved, "Number of calls removed" ); |
90 | |
91 | static 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 | |
96 | static 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 | |
101 | static 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 | |
106 | static 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 | |
111 | namespace llvm { |
112 | |
113 | using BBSideEffectsSet = DenseMap<const BasicBlock *, bool>; |
114 | using SmallVecInsn = SmallVector<Instruction *, 4>; |
115 | using 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. |
119 | using HoistingPointInfo = std::pair<BasicBlock *, SmallVecInsn>; |
120 | |
121 | using HoistingPointList = SmallVector<HoistingPointInfo, 4>; |
122 | |
123 | // A map from a pair of VNs to all the instructions with those VNs. |
124 | using VNType = std::pair<unsigned, uintptr_t>; |
125 | |
126 | using 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. |
138 | struct 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 | |
151 | using CHIIt = SmallVectorImpl<CHIArg>::iterator; |
152 | using CHIArgs = iterator_range<CHIIt>; |
153 | using OutValuesType = DenseMap<BasicBlock *, SmallVector<CHIArg, 2>>; |
154 | using 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. |
159 | enum : uintptr_t { InvalidVN = ~(uintptr_t)2 }; |
160 | |
161 | // Records all scalar instructions candidate for code hoisting. |
162 | class InsnInfo { |
163 | VNtoInsns VNtoScalars; |
164 | |
165 | public: |
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. |
177 | class LoadInfo { |
178 | VNtoInsns VNtoLoads; |
179 | |
180 | public: |
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. |
195 | class StoreInfo { |
196 | VNtoInsns VNtoStores; |
197 | |
198 | public: |
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. |
214 | class CallInfo { |
215 | VNtoInsns VNtoCallsScalars; |
216 | VNtoInsns VNtoCallsLoads; |
217 | VNtoInsns VNtoCallsStores; |
218 | |
219 | public: |
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 | |
241 | static 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). |
256 | class GVNHoist { |
257 | public: |
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 | |
275 | private: |
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 | |
519 | bool 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 | |
557 | unsigned 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 | |
579 | bool 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 | |
598 | bool 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 | |
632 | bool 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 | |
651 | bool 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 | |
688 | bool 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 | |
718 | bool 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 | |
760 | bool 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 | |
772 | void 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 | |
796 | void 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 | |
811 | void 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 | |
846 | void 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 | |
890 | bool 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 | |
900 | bool 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 | |
919 | void 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 | |
968 | void 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 | |
985 | unsigned 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 | |
1010 | void 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 | |
1025 | unsigned 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 | |
1044 | bool 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 | |
1078 | std::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 | |
1154 | std::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 | |
1216 | PreservedAnalyses 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 | |