File: | lib/Transforms/Scalar/GVNSink.cpp |
Warning: | line 399, column 7 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- GVNSink.cpp - sink expressions into successors ---------------------===// | |||
2 | // | |||
3 | // The LLVM Compiler Infrastructure | |||
4 | // | |||
5 | // This file is distributed under the University of Illinois Open Source | |||
6 | // License. See LICENSE.TXT for details. | |||
7 | // | |||
8 | //===----------------------------------------------------------------------===// | |||
9 | // | |||
10 | /// \file GVNSink.cpp | |||
11 | /// This pass attempts to sink instructions into successors, reducing static | |||
12 | /// instruction count and enabling if-conversion. | |||
13 | /// | |||
14 | /// We use a variant of global value numbering to decide what can be sunk. | |||
15 | /// Consider: | |||
16 | /// | |||
17 | /// [ %a1 = add i32 %b, 1 ] [ %c1 = add i32 %d, 1 ] | |||
18 | /// [ %a2 = xor i32 %a1, 1 ] [ %c2 = xor i32 %c1, 1 ] | |||
19 | /// \ / | |||
20 | /// [ %e = phi i32 %a2, %c2 ] | |||
21 | /// [ add i32 %e, 4 ] | |||
22 | /// | |||
23 | /// | |||
24 | /// GVN would number %a1 and %c1 differently because they compute different | |||
25 | /// results - the VN of an instruction is a function of its opcode and the | |||
26 | /// transitive closure of its operands. This is the key property for hoisting | |||
27 | /// and CSE. | |||
28 | /// | |||
29 | /// What we want when sinking however is for a numbering that is a function of | |||
30 | /// the *uses* of an instruction, which allows us to answer the question "if I | |||
31 | /// replace %a1 with %c1, will it contribute in an equivalent way to all | |||
32 | /// successive instructions?". The PostValueTable class in GVN provides this | |||
33 | /// mapping. | |||
34 | // | |||
35 | //===----------------------------------------------------------------------===// | |||
36 | ||||
37 | #include "llvm/ADT/ArrayRef.h" | |||
38 | #include "llvm/ADT/DenseMap.h" | |||
39 | #include "llvm/ADT/DenseMapInfo.h" | |||
40 | #include "llvm/ADT/DenseSet.h" | |||
41 | #include "llvm/ADT/Hashing.h" | |||
42 | #include "llvm/ADT/None.h" | |||
43 | #include "llvm/ADT/Optional.h" | |||
44 | #include "llvm/ADT/PostOrderIterator.h" | |||
45 | #include "llvm/ADT/STLExtras.h" | |||
46 | #include "llvm/ADT/SmallPtrSet.h" | |||
47 | #include "llvm/ADT/SmallVector.h" | |||
48 | #include "llvm/ADT/Statistic.h" | |||
49 | #include "llvm/ADT/StringExtras.h" | |||
50 | #include "llvm/Analysis/GlobalsModRef.h" | |||
51 | #include "llvm/IR/BasicBlock.h" | |||
52 | #include "llvm/IR/CFG.h" | |||
53 | #include "llvm/IR/Constants.h" | |||
54 | #include "llvm/IR/Function.h" | |||
55 | #include "llvm/IR/InstrTypes.h" | |||
56 | #include "llvm/IR/Instruction.h" | |||
57 | #include "llvm/IR/Instructions.h" | |||
58 | #include "llvm/IR/PassManager.h" | |||
59 | #include "llvm/IR/Type.h" | |||
60 | #include "llvm/IR/Use.h" | |||
61 | #include "llvm/IR/Value.h" | |||
62 | #include "llvm/Pass.h" | |||
63 | #include "llvm/Support/Allocator.h" | |||
64 | #include "llvm/Support/ArrayRecycler.h" | |||
65 | #include "llvm/Support/AtomicOrdering.h" | |||
66 | #include "llvm/Support/Casting.h" | |||
67 | #include "llvm/Support/Compiler.h" | |||
68 | #include "llvm/Support/Debug.h" | |||
69 | #include "llvm/Support/raw_ostream.h" | |||
70 | #include "llvm/Transforms/Scalar.h" | |||
71 | #include "llvm/Transforms/Scalar/GVN.h" | |||
72 | #include "llvm/Transforms/Scalar/GVNExpression.h" | |||
73 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
74 | #include "llvm/Transforms/Utils/Local.h" | |||
75 | #include <algorithm> | |||
76 | #include <cassert> | |||
77 | #include <cstddef> | |||
78 | #include <cstdint> | |||
79 | #include <iterator> | |||
80 | #include <utility> | |||
81 | ||||
82 | using namespace llvm; | |||
83 | ||||
84 | #define DEBUG_TYPE"gvn-sink" "gvn-sink" | |||
85 | ||||
86 | STATISTIC(NumRemoved, "Number of instructions removed")static llvm::Statistic NumRemoved = {"gvn-sink", "NumRemoved" , "Number of instructions removed", {0}, {false}}; | |||
87 | ||||
88 | namespace llvm { | |||
89 | namespace GVNExpression { | |||
90 | ||||
91 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void Expression::dump() const { | |||
92 | print(dbgs()); | |||
93 | dbgs() << "\n"; | |||
94 | } | |||
95 | ||||
96 | } // end namespace GVNExpression | |||
97 | } // end namespace llvm | |||
98 | ||||
99 | namespace { | |||
100 | ||||
101 | static bool isMemoryInst(const Instruction *I) { | |||
102 | return isa<LoadInst>(I) || isa<StoreInst>(I) || | |||
103 | (isa<InvokeInst>(I) && !cast<InvokeInst>(I)->doesNotAccessMemory()) || | |||
104 | (isa<CallInst>(I) && !cast<CallInst>(I)->doesNotAccessMemory()); | |||
105 | } | |||
106 | ||||
107 | /// Iterates through instructions in a set of blocks in reverse order from the | |||
108 | /// first non-terminator. For example (assume all blocks have size n): | |||
109 | /// LockstepReverseIterator I([B1, B2, B3]); | |||
110 | /// *I-- = [B1[n], B2[n], B3[n]]; | |||
111 | /// *I-- = [B1[n-1], B2[n-1], B3[n-1]]; | |||
112 | /// *I-- = [B1[n-2], B2[n-2], B3[n-2]]; | |||
113 | /// ... | |||
114 | /// | |||
115 | /// It continues until all blocks have been exhausted. Use \c getActiveBlocks() | |||
116 | /// to | |||
117 | /// determine which blocks are still going and the order they appear in the | |||
118 | /// list returned by operator*. | |||
119 | class LockstepReverseIterator { | |||
120 | ArrayRef<BasicBlock *> Blocks; | |||
121 | SmallSetVector<BasicBlock *, 4> ActiveBlocks; | |||
122 | SmallVector<Instruction *, 4> Insts; | |||
123 | bool Fail; | |||
124 | ||||
125 | public: | |||
126 | LockstepReverseIterator(ArrayRef<BasicBlock *> Blocks) : Blocks(Blocks) { | |||
127 | reset(); | |||
128 | } | |||
129 | ||||
130 | void reset() { | |||
131 | Fail = false; | |||
132 | ActiveBlocks.clear(); | |||
133 | for (BasicBlock *BB : Blocks) | |||
134 | ActiveBlocks.insert(BB); | |||
135 | Insts.clear(); | |||
136 | for (BasicBlock *BB : Blocks) { | |||
137 | if (BB->size() <= 1) { | |||
138 | // Block wasn't big enough - only contained a terminator. | |||
139 | ActiveBlocks.remove(BB); | |||
140 | continue; | |||
141 | } | |||
142 | Insts.push_back(BB->getTerminator()->getPrevNode()); | |||
143 | } | |||
144 | if (Insts.empty()) | |||
145 | Fail = true; | |||
146 | } | |||
147 | ||||
148 | bool isValid() const { return !Fail; } | |||
149 | ArrayRef<Instruction *> operator*() const { return Insts; } | |||
150 | ||||
151 | // Note: This needs to return a SmallSetVector as the elements of | |||
152 | // ActiveBlocks will be later copied to Blocks using std::copy. The | |||
153 | // resultant order of elements in Blocks needs to be deterministic. | |||
154 | // Using SmallPtrSet instead causes non-deterministic order while | |||
155 | // copying. And we cannot simply sort Blocks as they need to match the | |||
156 | // corresponding Values. | |||
157 | SmallSetVector<BasicBlock *, 4> &getActiveBlocks() { return ActiveBlocks; } | |||
158 | ||||
159 | void restrictToBlocks(SmallSetVector<BasicBlock *, 4> &Blocks) { | |||
160 | for (auto II = Insts.begin(); II != Insts.end();) { | |||
161 | if (std::find(Blocks.begin(), Blocks.end(), (*II)->getParent()) == | |||
162 | Blocks.end()) { | |||
163 | ActiveBlocks.remove((*II)->getParent()); | |||
164 | II = Insts.erase(II); | |||
165 | } else { | |||
166 | ++II; | |||
167 | } | |||
168 | } | |||
169 | } | |||
170 | ||||
171 | void operator--() { | |||
172 | if (Fail) | |||
173 | return; | |||
174 | SmallVector<Instruction *, 4> NewInsts; | |||
175 | for (auto *Inst : Insts) { | |||
176 | if (Inst == &Inst->getParent()->front()) | |||
177 | ActiveBlocks.remove(Inst->getParent()); | |||
178 | else | |||
179 | NewInsts.push_back(Inst->getPrevNode()); | |||
180 | } | |||
181 | if (NewInsts.empty()) { | |||
182 | Fail = true; | |||
183 | return; | |||
184 | } | |||
185 | Insts = NewInsts; | |||
186 | } | |||
187 | }; | |||
188 | ||||
189 | //===----------------------------------------------------------------------===// | |||
190 | ||||
191 | /// Candidate solution for sinking. There may be different ways to | |||
192 | /// sink instructions, differing in the number of instructions sunk, | |||
193 | /// the number of predecessors sunk from and the number of PHIs | |||
194 | /// required. | |||
195 | struct SinkingInstructionCandidate { | |||
196 | unsigned NumBlocks; | |||
197 | unsigned NumInstructions; | |||
198 | unsigned NumPHIs; | |||
199 | unsigned NumMemoryInsts; | |||
200 | int Cost = -1; | |||
201 | SmallVector<BasicBlock *, 4> Blocks; | |||
202 | ||||
203 | void calculateCost(unsigned NumOrigPHIs, unsigned NumOrigBlocks) { | |||
204 | unsigned NumExtraPHIs = NumPHIs - NumOrigPHIs; | |||
205 | unsigned SplitEdgeCost = (NumOrigBlocks > NumBlocks) ? 2 : 0; | |||
206 | Cost = (NumInstructions * (NumBlocks - 1)) - | |||
207 | (NumExtraPHIs * | |||
208 | NumExtraPHIs) // PHIs are expensive, so make sure they're worth it. | |||
209 | - SplitEdgeCost; | |||
210 | } | |||
211 | ||||
212 | bool operator>(const SinkingInstructionCandidate &Other) const { | |||
213 | return Cost > Other.Cost; | |||
214 | } | |||
215 | }; | |||
216 | ||||
217 | #ifndef NDEBUG | |||
218 | raw_ostream &operator<<(raw_ostream &OS, const SinkingInstructionCandidate &C) { | |||
219 | OS << "<Candidate Cost=" << C.Cost << " #Blocks=" << C.NumBlocks | |||
220 | << " #Insts=" << C.NumInstructions << " #PHIs=" << C.NumPHIs << ">"; | |||
221 | return OS; | |||
222 | } | |||
223 | #endif | |||
224 | ||||
225 | //===----------------------------------------------------------------------===// | |||
226 | ||||
227 | /// Describes a PHI node that may or may not exist. These track the PHIs | |||
228 | /// that must be created if we sunk a sequence of instructions. It provides | |||
229 | /// a hash function for efficient equality comparisons. | |||
230 | class ModelledPHI { | |||
231 | SmallVector<Value *, 4> Values; | |||
232 | SmallVector<BasicBlock *, 4> Blocks; | |||
233 | ||||
234 | public: | |||
235 | ModelledPHI() = default; | |||
236 | ||||
237 | ModelledPHI(const PHINode *PN) { | |||
238 | // BasicBlock comes first so we sort by basic block pointer order, then by value pointer order. | |||
239 | SmallVector<std::pair<BasicBlock *, Value *>, 4> Ops; | |||
240 | for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) | |||
241 | Ops.push_back({PN->getIncomingBlock(I), PN->getIncomingValue(I)}); | |||
242 | std::sort(Ops.begin(), Ops.end()); | |||
243 | for (auto &P : Ops) { | |||
244 | Blocks.push_back(P.first); | |||
245 | Values.push_back(P.second); | |||
246 | } | |||
247 | } | |||
248 | ||||
249 | /// Create a dummy ModelledPHI that will compare unequal to any other ModelledPHI | |||
250 | /// without the same ID. | |||
251 | /// \note This is specifically for DenseMapInfo - do not use this! | |||
252 | static ModelledPHI createDummy(size_t ID) { | |||
253 | ModelledPHI M; | |||
254 | M.Values.push_back(reinterpret_cast<Value*>(ID)); | |||
255 | return M; | |||
256 | } | |||
257 | ||||
258 | /// Create a PHI from an array of incoming values and incoming blocks. | |||
259 | template <typename VArray, typename BArray> | |||
260 | ModelledPHI(const VArray &V, const BArray &B) { | |||
261 | std::copy(V.begin(), V.end(), std::back_inserter(Values)); | |||
262 | std::copy(B.begin(), B.end(), std::back_inserter(Blocks)); | |||
263 | } | |||
264 | ||||
265 | /// Create a PHI from [I[OpNum] for I in Insts]. | |||
266 | template <typename BArray> | |||
267 | ModelledPHI(ArrayRef<Instruction *> Insts, unsigned OpNum, const BArray &B) { | |||
268 | std::copy(B.begin(), B.end(), std::back_inserter(Blocks)); | |||
269 | for (auto *I : Insts) | |||
270 | Values.push_back(I->getOperand(OpNum)); | |||
271 | } | |||
272 | ||||
273 | /// Restrict the PHI's contents down to only \c NewBlocks. | |||
274 | /// \c NewBlocks must be a subset of \c this->Blocks. | |||
275 | void restrictToBlocks(const SmallSetVector<BasicBlock *, 4> &NewBlocks) { | |||
276 | auto BI = Blocks.begin(); | |||
277 | auto VI = Values.begin(); | |||
278 | while (BI != Blocks.end()) { | |||
279 | assert(VI != Values.end())(static_cast <bool> (VI != Values.end()) ? void (0) : __assert_fail ("VI != Values.end()", "/build/llvm-toolchain-snapshot-7~svn326246/lib/Transforms/Scalar/GVNSink.cpp" , 279, __extension__ __PRETTY_FUNCTION__)); | |||
280 | if (std::find(NewBlocks.begin(), NewBlocks.end(), *BI) == | |||
281 | NewBlocks.end()) { | |||
282 | BI = Blocks.erase(BI); | |||
283 | VI = Values.erase(VI); | |||
284 | } else { | |||
285 | ++BI; | |||
286 | ++VI; | |||
287 | } | |||
288 | } | |||
289 | assert(Blocks.size() == NewBlocks.size())(static_cast <bool> (Blocks.size() == NewBlocks.size()) ? void (0) : __assert_fail ("Blocks.size() == NewBlocks.size()" , "/build/llvm-toolchain-snapshot-7~svn326246/lib/Transforms/Scalar/GVNSink.cpp" , 289, __extension__ __PRETTY_FUNCTION__)); | |||
290 | } | |||
291 | ||||
292 | ArrayRef<Value *> getValues() const { return Values; } | |||
293 | ||||
294 | bool areAllIncomingValuesSame() const { | |||
295 | return llvm::all_of(Values, [&](Value *V) { return V == Values[0]; }); | |||
296 | } | |||
297 | ||||
298 | bool areAllIncomingValuesSameType() const { | |||
299 | return llvm::all_of( | |||
300 | Values, [&](Value *V) { return V->getType() == Values[0]->getType(); }); | |||
301 | } | |||
302 | ||||
303 | bool areAnyIncomingValuesConstant() const { | |||
304 | return llvm::any_of(Values, [&](Value *V) { return isa<Constant>(V); }); | |||
305 | } | |||
306 | ||||
307 | // Hash functor | |||
308 | unsigned hash() const { | |||
309 | return (unsigned)hash_combine_range(Values.begin(), Values.end()); | |||
310 | } | |||
311 | ||||
312 | bool operator==(const ModelledPHI &Other) const { | |||
313 | return Values == Other.Values && Blocks == Other.Blocks; | |||
314 | } | |||
315 | }; | |||
316 | ||||
317 | template <typename ModelledPHI> struct DenseMapInfo { | |||
318 | static inline ModelledPHI &getEmptyKey() { | |||
319 | static ModelledPHI Dummy = ModelledPHI::createDummy(0); | |||
320 | return Dummy; | |||
321 | } | |||
322 | ||||
323 | static inline ModelledPHI &getTombstoneKey() { | |||
324 | static ModelledPHI Dummy = ModelledPHI::createDummy(1); | |||
325 | return Dummy; | |||
326 | } | |||
327 | ||||
328 | static unsigned getHashValue(const ModelledPHI &V) { return V.hash(); } | |||
329 | ||||
330 | static bool isEqual(const ModelledPHI &LHS, const ModelledPHI &RHS) { | |||
331 | return LHS == RHS; | |||
332 | } | |||
333 | }; | |||
334 | ||||
335 | using ModelledPHISet = DenseSet<ModelledPHI, DenseMapInfo<ModelledPHI>>; | |||
336 | ||||
337 | //===----------------------------------------------------------------------===// | |||
338 | // ValueTable | |||
339 | //===----------------------------------------------------------------------===// | |||
340 | // This is a value number table where the value number is a function of the | |||
341 | // *uses* of a value, rather than its operands. Thus, if VN(A) == VN(B) we know | |||
342 | // that the program would be equivalent if we replaced A with PHI(A, B). | |||
343 | //===----------------------------------------------------------------------===// | |||
344 | ||||
345 | /// A GVN expression describing how an instruction is used. The operands | |||
346 | /// field of BasicExpression is used to store uses, not operands. | |||
347 | /// | |||
348 | /// This class also contains fields for discriminators used when determining | |||
349 | /// equivalence of instructions with sideeffects. | |||
350 | class InstructionUseExpr : public GVNExpression::BasicExpression { | |||
351 | unsigned MemoryUseOrder = -1; | |||
352 | bool Volatile = false; | |||
353 | ||||
354 | public: | |||
355 | InstructionUseExpr(Instruction *I, ArrayRecycler<Value *> &R, | |||
356 | BumpPtrAllocator &A) | |||
357 | : GVNExpression::BasicExpression(I->getNumUses()) { | |||
358 | allocateOperands(R, A); | |||
359 | setOpcode(I->getOpcode()); | |||
360 | setType(I->getType()); | |||
361 | ||||
362 | for (auto &U : I->uses()) | |||
363 | op_push_back(U.getUser()); | |||
364 | std::sort(op_begin(), op_end()); | |||
365 | } | |||
366 | ||||
367 | void setMemoryUseOrder(unsigned MUO) { MemoryUseOrder = MUO; } | |||
368 | void setVolatile(bool V) { Volatile = V; } | |||
369 | ||||
370 | hash_code getHashValue() const override { | |||
371 | return hash_combine(GVNExpression::BasicExpression::getHashValue(), | |||
372 | MemoryUseOrder, Volatile); | |||
373 | } | |||
374 | ||||
375 | template <typename Function> hash_code getHashValue(Function MapFn) { | |||
376 | hash_code H = | |||
377 | hash_combine(getOpcode(), getType(), MemoryUseOrder, Volatile); | |||
378 | for (auto *V : operands()) | |||
379 | H = hash_combine(H, MapFn(V)); | |||
380 | return H; | |||
381 | } | |||
382 | }; | |||
383 | ||||
384 | class ValueTable { | |||
385 | DenseMap<Value *, uint32_t> ValueNumbering; | |||
386 | DenseMap<GVNExpression::Expression *, uint32_t> ExpressionNumbering; | |||
387 | DenseMap<size_t, uint32_t> HashNumbering; | |||
388 | BumpPtrAllocator Allocator; | |||
389 | ArrayRecycler<Value *> Recycler; | |||
390 | uint32_t nextValueNumber = 1; | |||
391 | ||||
392 | /// Create an expression for I based on its opcode and its uses. If I | |||
393 | /// touches or reads memory, the expression is also based upon its memory | |||
394 | /// order - see \c getMemoryUseOrder(). | |||
395 | InstructionUseExpr *createExpr(Instruction *I) { | |||
396 | InstructionUseExpr *E = | |||
397 | new (Allocator) InstructionUseExpr(I, Recycler, Allocator); | |||
398 | if (isMemoryInst(I)) | |||
399 | E->setMemoryUseOrder(getMemoryUseOrder(I)); | |||
| ||||
400 | ||||
401 | if (CmpInst *C = dyn_cast<CmpInst>(I)) { | |||
402 | CmpInst::Predicate Predicate = C->getPredicate(); | |||
403 | E->setOpcode((C->getOpcode() << 8) | Predicate); | |||
404 | } | |||
405 | return E; | |||
406 | } | |||
407 | ||||
408 | /// Helper to compute the value number for a memory instruction | |||
409 | /// (LoadInst/StoreInst), including checking the memory ordering and | |||
410 | /// volatility. | |||
411 | template <class Inst> InstructionUseExpr *createMemoryExpr(Inst *I) { | |||
412 | if (isStrongerThanUnordered(I->getOrdering()) || I->isAtomic()) | |||
| ||||
413 | return nullptr; | |||
414 | InstructionUseExpr *E = createExpr(I); | |||
415 | E->setVolatile(I->isVolatile()); | |||
416 | return E; | |||
417 | } | |||
418 | ||||
419 | public: | |||
420 | ValueTable() = default; | |||
421 | ||||
422 | /// Returns the value number for the specified value, assigning | |||
423 | /// it a new number if it did not have one before. | |||
424 | uint32_t lookupOrAdd(Value *V) { | |||
425 | auto VI = ValueNumbering.find(V); | |||
426 | if (VI != ValueNumbering.end()) | |||
427 | return VI->second; | |||
428 | ||||
429 | if (!isa<Instruction>(V)) { | |||
430 | ValueNumbering[V] = nextValueNumber; | |||
431 | return nextValueNumber++; | |||
432 | } | |||
433 | ||||
434 | Instruction *I = cast<Instruction>(V); | |||
435 | InstructionUseExpr *exp = nullptr; | |||
436 | switch (I->getOpcode()) { | |||
437 | case Instruction::Load: | |||
438 | exp = createMemoryExpr(cast<LoadInst>(I)); | |||
439 | break; | |||
440 | case Instruction::Store: | |||
441 | exp = createMemoryExpr(cast<StoreInst>(I)); | |||
442 | break; | |||
443 | case Instruction::Call: | |||
444 | case Instruction::Invoke: | |||
445 | case Instruction::Add: | |||
446 | case Instruction::FAdd: | |||
447 | case Instruction::Sub: | |||
448 | case Instruction::FSub: | |||
449 | case Instruction::Mul: | |||
450 | case Instruction::FMul: | |||
451 | case Instruction::UDiv: | |||
452 | case Instruction::SDiv: | |||
453 | case Instruction::FDiv: | |||
454 | case Instruction::URem: | |||
455 | case Instruction::SRem: | |||
456 | case Instruction::FRem: | |||
457 | case Instruction::Shl: | |||
458 | case Instruction::LShr: | |||
459 | case Instruction::AShr: | |||
460 | case Instruction::And: | |||
461 | case Instruction::Or: | |||
462 | case Instruction::Xor: | |||
463 | case Instruction::ICmp: | |||
464 | case Instruction::FCmp: | |||
465 | case Instruction::Trunc: | |||
466 | case Instruction::ZExt: | |||
467 | case Instruction::SExt: | |||
468 | case Instruction::FPToUI: | |||
469 | case Instruction::FPToSI: | |||
470 | case Instruction::UIToFP: | |||
471 | case Instruction::SIToFP: | |||
472 | case Instruction::FPTrunc: | |||
473 | case Instruction::FPExt: | |||
474 | case Instruction::PtrToInt: | |||
475 | case Instruction::IntToPtr: | |||
476 | case Instruction::BitCast: | |||
477 | case Instruction::Select: | |||
478 | case Instruction::ExtractElement: | |||
479 | case Instruction::InsertElement: | |||
480 | case Instruction::ShuffleVector: | |||
481 | case Instruction::InsertValue: | |||
482 | case Instruction::GetElementPtr: | |||
483 | exp = createExpr(I); | |||
484 | break; | |||
485 | default: | |||
486 | break; | |||
487 | } | |||
488 | ||||
489 | if (!exp) { | |||
490 | ValueNumbering[V] = nextValueNumber; | |||
491 | return nextValueNumber++; | |||
492 | } | |||
493 | ||||
494 | uint32_t e = ExpressionNumbering[exp]; | |||
495 | if (!e) { | |||
496 | hash_code H = exp->getHashValue([=](Value *V) { return lookupOrAdd(V); }); | |||
497 | auto I = HashNumbering.find(H); | |||
498 | if (I != HashNumbering.end()) { | |||
499 | e = I->second; | |||
500 | } else { | |||
501 | e = nextValueNumber++; | |||
502 | HashNumbering[H] = e; | |||
503 | ExpressionNumbering[exp] = e; | |||
504 | } | |||
505 | } | |||
506 | ValueNumbering[V] = e; | |||
507 | return e; | |||
508 | } | |||
509 | ||||
510 | /// Returns the value number of the specified value. Fails if the value has | |||
511 | /// not yet been numbered. | |||
512 | uint32_t lookup(Value *V) const { | |||
513 | auto VI = ValueNumbering.find(V); | |||
514 | assert(VI != ValueNumbering.end() && "Value not numbered?")(static_cast <bool> (VI != ValueNumbering.end() && "Value not numbered?") ? void (0) : __assert_fail ("VI != ValueNumbering.end() && \"Value not numbered?\"" , "/build/llvm-toolchain-snapshot-7~svn326246/lib/Transforms/Scalar/GVNSink.cpp" , 514, __extension__ __PRETTY_FUNCTION__)); | |||
515 | return VI->second; | |||
516 | } | |||
517 | ||||
518 | /// Removes all value numberings and resets the value table. | |||
519 | void clear() { | |||
520 | ValueNumbering.clear(); | |||
521 | ExpressionNumbering.clear(); | |||
522 | HashNumbering.clear(); | |||
523 | Recycler.clear(Allocator); | |||
524 | nextValueNumber = 1; | |||
525 | } | |||
526 | ||||
527 | /// \c Inst uses or touches memory. Return an ID describing the memory state | |||
528 | /// at \c Inst such that if getMemoryUseOrder(I1) == getMemoryUseOrder(I2), | |||
529 | /// the exact same memory operations happen after I1 and I2. | |||
530 | /// | |||
531 | /// This is a very hard problem in general, so we use domain-specific | |||
532 | /// knowledge that we only ever check for equivalence between blocks sharing a | |||
533 | /// single immediate successor that is common, and when determining if I1 == | |||
534 | /// I2 we will have already determined that next(I1) == next(I2). This | |||
535 | /// inductive property allows us to simply return the value number of the next | |||
536 | /// instruction that defines memory. | |||
537 | uint32_t getMemoryUseOrder(Instruction *Inst) { | |||
538 | auto *BB = Inst->getParent(); | |||
539 | for (auto I = std::next(Inst->getIterator()), E = BB->end(); | |||
540 | I != E && !I->isTerminator(); ++I) { | |||
541 | if (!isMemoryInst(&*I)) | |||
542 | continue; | |||
543 | if (isa<LoadInst>(&*I)) | |||
544 | continue; | |||
545 | CallInst *CI = dyn_cast<CallInst>(&*I); | |||
546 | if (CI && CI->onlyReadsMemory()) | |||
547 | continue; | |||
548 | InvokeInst *II = dyn_cast<InvokeInst>(&*I); | |||
549 | if (II && II->onlyReadsMemory()) | |||
550 | continue; | |||
551 | return lookupOrAdd(&*I); | |||
552 | } | |||
553 | return 0; | |||
554 | } | |||
555 | }; | |||
556 | ||||
557 | //===----------------------------------------------------------------------===// | |||
558 | ||||
559 | class GVNSink { | |||
560 | public: | |||
561 | GVNSink() = default; | |||
562 | ||||
563 | bool run(Function &F) { | |||
564 | DEBUG(dbgs() << "GVNSink: running on function @" << F.getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << "GVNSink: running on function @" << F.getName() << "\n"; } } while (false); | |||
565 | ||||
566 | unsigned NumSunk = 0; | |||
567 | ReversePostOrderTraversal<Function*> RPOT(&F); | |||
568 | for (auto *N : RPOT) | |||
569 | NumSunk += sinkBB(N); | |||
570 | ||||
571 | return NumSunk > 0; | |||
572 | } | |||
573 | ||||
574 | private: | |||
575 | ValueTable VN; | |||
576 | ||||
577 | bool isInstructionBlacklisted(Instruction *I) { | |||
578 | // These instructions may change or break semantics if moved. | |||
579 | if (isa<PHINode>(I) || I->isEHPad() || isa<AllocaInst>(I) || | |||
580 | I->getType()->isTokenTy()) | |||
581 | return true; | |||
582 | return false; | |||
583 | } | |||
584 | ||||
585 | /// The main heuristic function. Analyze the set of instructions pointed to by | |||
586 | /// LRI and return a candidate solution if these instructions can be sunk, or | |||
587 | /// None otherwise. | |||
588 | Optional<SinkingInstructionCandidate> analyzeInstructionForSinking( | |||
589 | LockstepReverseIterator &LRI, unsigned &InstNum, unsigned &MemoryInstNum, | |||
590 | ModelledPHISet &NeededPHIs, SmallPtrSetImpl<Value *> &PHIContents); | |||
591 | ||||
592 | /// Create a ModelledPHI for each PHI in BB, adding to PHIs. | |||
593 | void analyzeInitialPHIs(BasicBlock *BB, ModelledPHISet &PHIs, | |||
594 | SmallPtrSetImpl<Value *> &PHIContents) { | |||
595 | for (PHINode &PN : BB->phis()) { | |||
596 | auto MPHI = ModelledPHI(&PN); | |||
597 | PHIs.insert(MPHI); | |||
598 | for (auto *V : MPHI.getValues()) | |||
599 | PHIContents.insert(V); | |||
600 | } | |||
601 | } | |||
602 | ||||
603 | /// The main instruction sinking driver. Set up state and try and sink | |||
604 | /// instructions into BBEnd from its predecessors. | |||
605 | unsigned sinkBB(BasicBlock *BBEnd); | |||
606 | ||||
607 | /// Perform the actual mechanics of sinking an instruction from Blocks into | |||
608 | /// BBEnd, which is their only successor. | |||
609 | void sinkLastInstruction(ArrayRef<BasicBlock *> Blocks, BasicBlock *BBEnd); | |||
610 | ||||
611 | /// Remove PHIs that all have the same incoming value. | |||
612 | void foldPointlessPHINodes(BasicBlock *BB) { | |||
613 | auto I = BB->begin(); | |||
614 | while (PHINode *PN = dyn_cast<PHINode>(I++)) { | |||
615 | if (!llvm::all_of(PN->incoming_values(), [&](const Value *V) { | |||
616 | return V == PN->getIncomingValue(0); | |||
617 | })) | |||
618 | continue; | |||
619 | if (PN->getIncomingValue(0) != PN) | |||
620 | PN->replaceAllUsesWith(PN->getIncomingValue(0)); | |||
621 | else | |||
622 | PN->replaceAllUsesWith(UndefValue::get(PN->getType())); | |||
623 | PN->eraseFromParent(); | |||
624 | } | |||
625 | } | |||
626 | }; | |||
627 | ||||
628 | Optional<SinkingInstructionCandidate> GVNSink::analyzeInstructionForSinking( | |||
629 | LockstepReverseIterator &LRI, unsigned &InstNum, unsigned &MemoryInstNum, | |||
630 | ModelledPHISet &NeededPHIs, SmallPtrSetImpl<Value *> &PHIContents) { | |||
631 | auto Insts = *LRI; | |||
632 | DEBUG(dbgs() << " -- Analyzing instruction set: [\n"; for (auto *Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " -- Analyzing instruction set: [\n" ; for (auto *I : Insts) { I->dump(); } dbgs() << " ]\n" ;; } } while (false) | |||
633 | : Insts) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " -- Analyzing instruction set: [\n" ; for (auto *I : Insts) { I->dump(); } dbgs() << " ]\n" ;; } } while (false) | |||
634 | I->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " -- Analyzing instruction set: [\n" ; for (auto *I : Insts) { I->dump(); } dbgs() << " ]\n" ;; } } while (false) | |||
635 | } dbgs() << " ]\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " -- Analyzing instruction set: [\n" ; for (auto *I : Insts) { I->dump(); } dbgs() << " ]\n" ;; } } while (false); | |||
636 | ||||
637 | DenseMap<uint32_t, unsigned> VNums; | |||
638 | for (auto *I : Insts) { | |||
639 | uint32_t N = VN.lookupOrAdd(I); | |||
640 | DEBUG(dbgs() << " VN=" << Twine::utohexstr(N) << " for" << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " VN=" << Twine::utohexstr (N) << " for" << *I << "\n"; } } while (false ); | |||
641 | if (N == ~0U) | |||
642 | return None; | |||
643 | VNums[N]++; | |||
644 | } | |||
645 | unsigned VNumToSink = | |||
646 | std::max_element(VNums.begin(), VNums.end(), | |||
647 | [](const std::pair<uint32_t, unsigned> &I, | |||
648 | const std::pair<uint32_t, unsigned> &J) { | |||
649 | return I.second < J.second; | |||
650 | }) | |||
651 | ->first; | |||
652 | ||||
653 | if (VNums[VNumToSink] == 1) | |||
654 | // Can't sink anything! | |||
655 | return None; | |||
656 | ||||
657 | // Now restrict the number of incoming blocks down to only those with | |||
658 | // VNumToSink. | |||
659 | auto &ActivePreds = LRI.getActiveBlocks(); | |||
660 | unsigned InitialActivePredSize = ActivePreds.size(); | |||
661 | SmallVector<Instruction *, 4> NewInsts; | |||
662 | for (auto *I : Insts) { | |||
663 | if (VN.lookup(I) != VNumToSink) | |||
664 | ActivePreds.remove(I->getParent()); | |||
665 | else | |||
666 | NewInsts.push_back(I); | |||
667 | } | |||
668 | for (auto *I : NewInsts) | |||
669 | if (isInstructionBlacklisted(I)) | |||
670 | return None; | |||
671 | ||||
672 | // If we've restricted the incoming blocks, restrict all needed PHIs also | |||
673 | // to that set. | |||
674 | bool RecomputePHIContents = false; | |||
675 | if (ActivePreds.size() != InitialActivePredSize) { | |||
676 | ModelledPHISet NewNeededPHIs; | |||
677 | for (auto P : NeededPHIs) { | |||
678 | P.restrictToBlocks(ActivePreds); | |||
679 | NewNeededPHIs.insert(P); | |||
680 | } | |||
681 | NeededPHIs = NewNeededPHIs; | |||
682 | LRI.restrictToBlocks(ActivePreds); | |||
683 | RecomputePHIContents = true; | |||
684 | } | |||
685 | ||||
686 | // The sunk instruction's results. | |||
687 | ModelledPHI NewPHI(NewInsts, ActivePreds); | |||
688 | ||||
689 | // Does sinking this instruction render previous PHIs redundant? | |||
690 | if (NeededPHIs.find(NewPHI) != NeededPHIs.end()) { | |||
691 | NeededPHIs.erase(NewPHI); | |||
692 | RecomputePHIContents = true; | |||
693 | } | |||
694 | ||||
695 | if (RecomputePHIContents) { | |||
696 | // The needed PHIs have changed, so recompute the set of all needed | |||
697 | // values. | |||
698 | PHIContents.clear(); | |||
699 | for (auto &PHI : NeededPHIs) | |||
700 | PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end()); | |||
701 | } | |||
702 | ||||
703 | // Is this instruction required by a later PHI that doesn't match this PHI? | |||
704 | // if so, we can't sink this instruction. | |||
705 | for (auto *V : NewPHI.getValues()) | |||
706 | if (PHIContents.count(V)) | |||
707 | // V exists in this PHI, but the whole PHI is different to NewPHI | |||
708 | // (else it would have been removed earlier). We cannot continue | |||
709 | // because this isn't representable. | |||
710 | return None; | |||
711 | ||||
712 | // Which operands need PHIs? | |||
713 | // FIXME: If any of these fail, we should partition up the candidates to | |||
714 | // try and continue making progress. | |||
715 | Instruction *I0 = NewInsts[0]; | |||
716 | for (unsigned OpNum = 0, E = I0->getNumOperands(); OpNum != E; ++OpNum) { | |||
717 | ModelledPHI PHI(NewInsts, OpNum, ActivePreds); | |||
718 | if (PHI.areAllIncomingValuesSame()) | |||
719 | continue; | |||
720 | if (!canReplaceOperandWithVariable(I0, OpNum)) | |||
721 | // We can 't create a PHI from this instruction! | |||
722 | return None; | |||
723 | if (NeededPHIs.count(PHI)) | |||
724 | continue; | |||
725 | if (!PHI.areAllIncomingValuesSameType()) | |||
726 | return None; | |||
727 | // Don't create indirect calls! The called value is the final operand. | |||
728 | if ((isa<CallInst>(I0) || isa<InvokeInst>(I0)) && OpNum == E - 1 && | |||
729 | PHI.areAnyIncomingValuesConstant()) | |||
730 | return None; | |||
731 | ||||
732 | NeededPHIs.reserve(NeededPHIs.size()); | |||
733 | NeededPHIs.insert(PHI); | |||
734 | PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end()); | |||
735 | } | |||
736 | ||||
737 | if (isMemoryInst(NewInsts[0])) | |||
738 | ++MemoryInstNum; | |||
739 | ||||
740 | SinkingInstructionCandidate Cand; | |||
741 | Cand.NumInstructions = ++InstNum; | |||
742 | Cand.NumMemoryInsts = MemoryInstNum; | |||
743 | Cand.NumBlocks = ActivePreds.size(); | |||
744 | Cand.NumPHIs = NeededPHIs.size(); | |||
745 | for (auto *C : ActivePreds) | |||
746 | Cand.Blocks.push_back(C); | |||
747 | ||||
748 | return Cand; | |||
749 | } | |||
750 | ||||
751 | unsigned GVNSink::sinkBB(BasicBlock *BBEnd) { | |||
752 | DEBUG(dbgs() << "GVNSink: running on basic block ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << "GVNSink: running on basic block " ; BBEnd->printAsOperand(dbgs()); dbgs() << "\n"; } } while (false) | |||
753 | BBEnd->printAsOperand(dbgs()); dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << "GVNSink: running on basic block " ; BBEnd->printAsOperand(dbgs()); dbgs() << "\n"; } } while (false); | |||
754 | SmallVector<BasicBlock *, 4> Preds; | |||
755 | for (auto *B : predecessors(BBEnd)) { | |||
756 | auto *T = B->getTerminator(); | |||
757 | if (isa<BranchInst>(T) || isa<SwitchInst>(T)) | |||
758 | Preds.push_back(B); | |||
759 | else | |||
760 | return 0; | |||
761 | } | |||
762 | if (Preds.size() < 2) | |||
763 | return 0; | |||
764 | std::sort(Preds.begin(), Preds.end()); | |||
765 | ||||
766 | unsigned NumOrigPreds = Preds.size(); | |||
767 | // We can only sink instructions through unconditional branches. | |||
768 | for (auto I = Preds.begin(); I != Preds.end();) { | |||
769 | if ((*I)->getTerminator()->getNumSuccessors() != 1) | |||
770 | I = Preds.erase(I); | |||
771 | else | |||
772 | ++I; | |||
773 | } | |||
774 | ||||
775 | LockstepReverseIterator LRI(Preds); | |||
776 | SmallVector<SinkingInstructionCandidate, 4> Candidates; | |||
777 | unsigned InstNum = 0, MemoryInstNum = 0; | |||
778 | ModelledPHISet NeededPHIs; | |||
779 | SmallPtrSet<Value *, 4> PHIContents; | |||
780 | analyzeInitialPHIs(BBEnd, NeededPHIs, PHIContents); | |||
781 | unsigned NumOrigPHIs = NeededPHIs.size(); | |||
782 | ||||
783 | while (LRI.isValid()) { | |||
784 | auto Cand = analyzeInstructionForSinking(LRI, InstNum, MemoryInstNum, | |||
785 | NeededPHIs, PHIContents); | |||
786 | if (!Cand) | |||
787 | break; | |||
788 | Cand->calculateCost(NumOrigPHIs, Preds.size()); | |||
789 | Candidates.emplace_back(*Cand); | |||
790 | --LRI; | |||
791 | } | |||
792 | ||||
793 | std::stable_sort( | |||
794 | Candidates.begin(), Candidates.end(), | |||
795 | [](const SinkingInstructionCandidate &A, | |||
796 | const SinkingInstructionCandidate &B) { return A > B; }); | |||
797 | DEBUG(dbgs() << " -- Sinking candidates:\n"; for (auto &Cdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " -- Sinking candidates:\n"; for (auto &C : Candidates) dbgs() << " " << C << "\n";; } } while (false) | |||
798 | : Candidates) dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " -- Sinking candidates:\n"; for (auto &C : Candidates) dbgs() << " " << C << "\n";; } } while (false) | |||
799 | << " " << C << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " -- Sinking candidates:\n"; for (auto &C : Candidates) dbgs() << " " << C << "\n";; } } while (false); | |||
800 | ||||
801 | // Pick the top candidate, as long it is positive! | |||
802 | if (Candidates.empty() || Candidates.front().Cost <= 0) | |||
803 | return 0; | |||
804 | auto C = Candidates.front(); | |||
805 | ||||
806 | DEBUG(dbgs() << " -- Sinking: " << C << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " -- Sinking: " << C << "\n"; } } while (false); | |||
807 | BasicBlock *InsertBB = BBEnd; | |||
808 | if (C.Blocks.size() < NumOrigPreds) { | |||
809 | DEBUG(dbgs() << " -- Splitting edge to "; BBEnd->printAsOperand(dbgs());do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " -- Splitting edge to "; BBEnd ->printAsOperand(dbgs()); dbgs() << "\n"; } } while ( false) | |||
810 | dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " -- Splitting edge to "; BBEnd ->printAsOperand(dbgs()); dbgs() << "\n"; } } while ( false); | |||
811 | InsertBB = SplitBlockPredecessors(BBEnd, C.Blocks, ".gvnsink.split"); | |||
812 | if (!InsertBB) { | |||
813 | DEBUG(dbgs() << " -- FAILED to split edge!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("gvn-sink")) { dbgs() << " -- FAILED to split edge!\n" ; } } while (false); | |||
814 | // Edge couldn't be split. | |||
815 | return 0; | |||
816 | } | |||
817 | } | |||
818 | ||||
819 | for (unsigned I = 0; I < C.NumInstructions; ++I) | |||
820 | sinkLastInstruction(C.Blocks, InsertBB); | |||
821 | ||||
822 | return C.NumInstructions; | |||
823 | } | |||
824 | ||||
825 | void GVNSink::sinkLastInstruction(ArrayRef<BasicBlock *> Blocks, | |||
826 | BasicBlock *BBEnd) { | |||
827 | SmallVector<Instruction *, 4> Insts; | |||
828 | for (BasicBlock *BB : Blocks) | |||
829 | Insts.push_back(BB->getTerminator()->getPrevNode()); | |||
830 | Instruction *I0 = Insts.front(); | |||
831 | ||||
832 | SmallVector<Value *, 4> NewOperands; | |||
833 | for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) { | |||
834 | bool NeedPHI = llvm::any_of(Insts, [&I0, O](const Instruction *I) { | |||
835 | return I->getOperand(O) != I0->getOperand(O); | |||
836 | }); | |||
837 | if (!NeedPHI) { | |||
838 | NewOperands.push_back(I0->getOperand(O)); | |||
839 | continue; | |||
840 | } | |||
841 | ||||
842 | // Create a new PHI in the successor block and populate it. | |||
843 | auto *Op = I0->getOperand(O); | |||
844 | assert(!Op->getType()->isTokenTy() && "Can't PHI tokens!")(static_cast <bool> (!Op->getType()->isTokenTy() && "Can't PHI tokens!") ? void (0) : __assert_fail ("!Op->getType()->isTokenTy() && \"Can't PHI tokens!\"" , "/build/llvm-toolchain-snapshot-7~svn326246/lib/Transforms/Scalar/GVNSink.cpp" , 844, __extension__ __PRETTY_FUNCTION__)); | |||
845 | auto *PN = PHINode::Create(Op->getType(), Insts.size(), | |||
846 | Op->getName() + ".sink", &BBEnd->front()); | |||
847 | for (auto *I : Insts) | |||
848 | PN->addIncoming(I->getOperand(O), I->getParent()); | |||
849 | NewOperands.push_back(PN); | |||
850 | } | |||
851 | ||||
852 | // Arbitrarily use I0 as the new "common" instruction; remap its operands | |||
853 | // and move it to the start of the successor block. | |||
854 | for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) | |||
855 | I0->getOperandUse(O).set(NewOperands[O]); | |||
856 | I0->moveBefore(&*BBEnd->getFirstInsertionPt()); | |||
857 | ||||
858 | // Update metadata and IR flags. | |||
859 | for (auto *I : Insts) | |||
860 | if (I != I0) { | |||
861 | combineMetadataForCSE(I0, I); | |||
862 | I0->andIRFlags(I); | |||
863 | } | |||
864 | ||||
865 | for (auto *I : Insts) | |||
866 | if (I != I0) | |||
867 | I->replaceAllUsesWith(I0); | |||
868 | foldPointlessPHINodes(BBEnd); | |||
869 | ||||
870 | // Finally nuke all instructions apart from the common instruction. | |||
871 | for (auto *I : Insts) | |||
872 | if (I != I0) | |||
873 | I->eraseFromParent(); | |||
874 | ||||
875 | NumRemoved += Insts.size() - 1; | |||
876 | } | |||
877 | ||||
878 | //////////////////////////////////////////////////////////////////////////////// | |||
879 | // Pass machinery / boilerplate | |||
880 | ||||
881 | class GVNSinkLegacyPass : public FunctionPass { | |||
882 | public: | |||
883 | static char ID; | |||
884 | ||||
885 | GVNSinkLegacyPass() : FunctionPass(ID) { | |||
886 | initializeGVNSinkLegacyPassPass(*PassRegistry::getPassRegistry()); | |||
887 | } | |||
888 | ||||
889 | bool runOnFunction(Function &F) override { | |||
890 | if (skipFunction(F)) | |||
891 | return false; | |||
892 | GVNSink G; | |||
893 | return G.run(F); | |||
894 | } | |||
895 | ||||
896 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
897 | AU.addPreserved<GlobalsAAWrapperPass>(); | |||
898 | } | |||
899 | }; | |||
900 | ||||
901 | } // end anonymous namespace | |||
902 | ||||
903 | PreservedAnalyses GVNSinkPass::run(Function &F, FunctionAnalysisManager &AM) { | |||
904 | GVNSink G; | |||
905 | if (!G.run(F)) | |||
906 | return PreservedAnalyses::all(); | |||
907 | ||||
908 | PreservedAnalyses PA; | |||
909 | PA.preserve<GlobalsAA>(); | |||
910 | return PA; | |||
911 | } | |||
912 | ||||
913 | char GVNSinkLegacyPass::ID = 0; | |||
914 | ||||
915 | INITIALIZE_PASS_BEGIN(GVNSinkLegacyPass, "gvn-sink",static void *initializeGVNSinkLegacyPassPassOnce(PassRegistry &Registry) { | |||
916 | "Early GVN sinking of Expressions", false, false)static void *initializeGVNSinkLegacyPassPassOnce(PassRegistry &Registry) { | |||
917 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | |||
918 | INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry); | |||
919 | INITIALIZE_PASS_END(GVNSinkLegacyPass, "gvn-sink",PassInfo *PI = new PassInfo( "Early GVN sinking of Expressions" , "gvn-sink", &GVNSinkLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<GVNSinkLegacyPass>), false, false); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeGVNSinkLegacyPassPassFlag; void llvm::initializeGVNSinkLegacyPassPass (PassRegistry &Registry) { llvm::call_once(InitializeGVNSinkLegacyPassPassFlag , initializeGVNSinkLegacyPassPassOnce, std::ref(Registry)); } | |||
920 | "Early GVN sinking of Expressions", false, false)PassInfo *PI = new PassInfo( "Early GVN sinking of Expressions" , "gvn-sink", &GVNSinkLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<GVNSinkLegacyPass>), false, false); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeGVNSinkLegacyPassPassFlag; void llvm::initializeGVNSinkLegacyPassPass (PassRegistry &Registry) { llvm::call_once(InitializeGVNSinkLegacyPassPassFlag , initializeGVNSinkLegacyPassPassOnce, std::ref(Registry)); } | |||
921 | ||||
922 | FunctionPass *llvm::createGVNSinkPass() { return new GVNSinkLegacyPass(); } |