File: | llvm/lib/Transforms/Scalar/ADCE.cpp |
Warning: | line 609, column 29 Access to field 'BB' results in a dereference of a null pointer (loaded from variable 'PreferredSucc') |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- ADCE.cpp - Code to perform dead code elimination -------------------===// | |||
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 file implements the Aggressive Dead Code Elimination pass. This pass | |||
10 | // optimistically assumes that all instructions are dead until proven otherwise, | |||
11 | // allowing it to eliminate dead computations that other DCE passes do not | |||
12 | // catch, particularly involving loop computations. | |||
13 | // | |||
14 | //===----------------------------------------------------------------------===// | |||
15 | ||||
16 | #include "llvm/Transforms/Scalar/ADCE.h" | |||
17 | #include "llvm/ADT/DenseMap.h" | |||
18 | #include "llvm/ADT/DepthFirstIterator.h" | |||
19 | #include "llvm/ADT/GraphTraits.h" | |||
20 | #include "llvm/ADT/MapVector.h" | |||
21 | #include "llvm/ADT/PostOrderIterator.h" | |||
22 | #include "llvm/ADT/SetVector.h" | |||
23 | #include "llvm/ADT/SmallPtrSet.h" | |||
24 | #include "llvm/ADT/SmallVector.h" | |||
25 | #include "llvm/ADT/Statistic.h" | |||
26 | #include "llvm/Analysis/DomTreeUpdater.h" | |||
27 | #include "llvm/Analysis/GlobalsModRef.h" | |||
28 | #include "llvm/Analysis/IteratedDominanceFrontier.h" | |||
29 | #include "llvm/Analysis/PostDominators.h" | |||
30 | #include "llvm/IR/BasicBlock.h" | |||
31 | #include "llvm/IR/CFG.h" | |||
32 | #include "llvm/IR/DebugInfoMetadata.h" | |||
33 | #include "llvm/IR/DebugLoc.h" | |||
34 | #include "llvm/IR/Dominators.h" | |||
35 | #include "llvm/IR/Function.h" | |||
36 | #include "llvm/IR/IRBuilder.h" | |||
37 | #include "llvm/IR/InstIterator.h" | |||
38 | #include "llvm/IR/InstrTypes.h" | |||
39 | #include "llvm/IR/Instruction.h" | |||
40 | #include "llvm/IR/Instructions.h" | |||
41 | #include "llvm/IR/IntrinsicInst.h" | |||
42 | #include "llvm/IR/PassManager.h" | |||
43 | #include "llvm/IR/Use.h" | |||
44 | #include "llvm/IR/Value.h" | |||
45 | #include "llvm/InitializePasses.h" | |||
46 | #include "llvm/Pass.h" | |||
47 | #include "llvm/ProfileData/InstrProf.h" | |||
48 | #include "llvm/Support/Casting.h" | |||
49 | #include "llvm/Support/CommandLine.h" | |||
50 | #include "llvm/Support/Debug.h" | |||
51 | #include "llvm/Support/raw_ostream.h" | |||
52 | #include "llvm/Transforms/Scalar.h" | |||
53 | #include "llvm/Transforms/Utils/Local.h" | |||
54 | #include <cassert> | |||
55 | #include <cstddef> | |||
56 | #include <utility> | |||
57 | ||||
58 | using namespace llvm; | |||
59 | ||||
60 | #define DEBUG_TYPE"adce" "adce" | |||
61 | ||||
62 | STATISTIC(NumRemoved, "Number of instructions removed")static llvm::Statistic NumRemoved = {"adce", "NumRemoved", "Number of instructions removed" }; | |||
63 | STATISTIC(NumBranchesRemoved, "Number of branch instructions removed")static llvm::Statistic NumBranchesRemoved = {"adce", "NumBranchesRemoved" , "Number of branch instructions removed"}; | |||
64 | ||||
65 | // This is a temporary option until we change the interface to this pass based | |||
66 | // on optimization level. | |||
67 | static cl::opt<bool> RemoveControlFlowFlag("adce-remove-control-flow", | |||
68 | cl::init(true), cl::Hidden); | |||
69 | ||||
70 | // This option enables removing of may-be-infinite loops which have no other | |||
71 | // effect. | |||
72 | static cl::opt<bool> RemoveLoops("adce-remove-loops", cl::init(false), | |||
73 | cl::Hidden); | |||
74 | ||||
75 | namespace { | |||
76 | ||||
77 | /// Information about Instructions | |||
78 | struct InstInfoType { | |||
79 | /// True if the associated instruction is live. | |||
80 | bool Live = false; | |||
81 | ||||
82 | /// Quick access to information for block containing associated Instruction. | |||
83 | struct BlockInfoType *Block = nullptr; | |||
84 | }; | |||
85 | ||||
86 | /// Information about basic blocks relevant to dead code elimination. | |||
87 | struct BlockInfoType { | |||
88 | /// True when this block contains a live instructions. | |||
89 | bool Live = false; | |||
90 | ||||
91 | /// True when this block ends in an unconditional branch. | |||
92 | bool UnconditionalBranch = false; | |||
93 | ||||
94 | /// True when this block is known to have live PHI nodes. | |||
95 | bool HasLivePhiNodes = false; | |||
96 | ||||
97 | /// Control dependence sources need to be live for this block. | |||
98 | bool CFLive = false; | |||
99 | ||||
100 | /// Quick access to the LiveInfo for the terminator, | |||
101 | /// holds the value &InstInfo[Terminator] | |||
102 | InstInfoType *TerminatorLiveInfo = nullptr; | |||
103 | ||||
104 | /// Corresponding BasicBlock. | |||
105 | BasicBlock *BB = nullptr; | |||
106 | ||||
107 | /// Cache of BB->getTerminator(). | |||
108 | Instruction *Terminator = nullptr; | |||
109 | ||||
110 | /// Post-order numbering of reverse control flow graph. | |||
111 | unsigned PostOrder; | |||
112 | ||||
113 | bool terminatorIsLive() const { return TerminatorLiveInfo->Live; } | |||
114 | }; | |||
115 | ||||
116 | class AggressiveDeadCodeElimination { | |||
117 | Function &F; | |||
118 | ||||
119 | // ADCE does not use DominatorTree per se, but it updates it to preserve the | |||
120 | // analysis. | |||
121 | DominatorTree *DT; | |||
122 | PostDominatorTree &PDT; | |||
123 | ||||
124 | /// Mapping of blocks to associated information, an element in BlockInfoVec. | |||
125 | /// Use MapVector to get deterministic iteration order. | |||
126 | MapVector<BasicBlock *, BlockInfoType> BlockInfo; | |||
127 | bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; } | |||
128 | ||||
129 | /// Mapping of instructions to associated information. | |||
130 | DenseMap<Instruction *, InstInfoType> InstInfo; | |||
131 | bool isLive(Instruction *I) { return InstInfo[I].Live; } | |||
132 | ||||
133 | /// Instructions known to be live where we need to mark | |||
134 | /// reaching definitions as live. | |||
135 | SmallVector<Instruction *, 128> Worklist; | |||
136 | ||||
137 | /// Debug info scopes around a live instruction. | |||
138 | SmallPtrSet<const Metadata *, 32> AliveScopes; | |||
139 | ||||
140 | /// Set of blocks with not known to have live terminators. | |||
141 | SmallSetVector<BasicBlock *, 16> BlocksWithDeadTerminators; | |||
142 | ||||
143 | /// The set of blocks which we have determined whose control | |||
144 | /// dependence sources must be live and which have not had | |||
145 | /// those dependences analyzed. | |||
146 | SmallPtrSet<BasicBlock *, 16> NewLiveBlocks; | |||
147 | ||||
148 | /// Set up auxiliary data structures for Instructions and BasicBlocks and | |||
149 | /// initialize the Worklist to the set of must-be-live Instruscions. | |||
150 | void initialize(); | |||
151 | ||||
152 | /// Return true for operations which are always treated as live. | |||
153 | bool isAlwaysLive(Instruction &I); | |||
154 | ||||
155 | /// Return true for instrumentation instructions for value profiling. | |||
156 | bool isInstrumentsConstant(Instruction &I); | |||
157 | ||||
158 | /// Propagate liveness to reaching definitions. | |||
159 | void markLiveInstructions(); | |||
160 | ||||
161 | /// Mark an instruction as live. | |||
162 | void markLive(Instruction *I); | |||
163 | ||||
164 | /// Mark a block as live. | |||
165 | void markLive(BlockInfoType &BB); | |||
166 | void markLive(BasicBlock *BB) { markLive(BlockInfo[BB]); } | |||
167 | ||||
168 | /// Mark terminators of control predecessors of a PHI node live. | |||
169 | void markPhiLive(PHINode *PN); | |||
170 | ||||
171 | /// Record the Debug Scopes which surround live debug information. | |||
172 | void collectLiveScopes(const DILocalScope &LS); | |||
173 | void collectLiveScopes(const DILocation &DL); | |||
174 | ||||
175 | /// Analyze dead branches to find those whose branches are the sources | |||
176 | /// of control dependences impacting a live block. Those branches are | |||
177 | /// marked live. | |||
178 | void markLiveBranchesFromControlDependences(); | |||
179 | ||||
180 | /// Remove instructions not marked live, return if any instruction was | |||
181 | /// removed. | |||
182 | bool removeDeadInstructions(); | |||
183 | ||||
184 | /// Identify connected sections of the control flow graph which have | |||
185 | /// dead terminators and rewrite the control flow graph to remove them. | |||
186 | bool updateDeadRegions(); | |||
187 | ||||
188 | /// Set the BlockInfo::PostOrder field based on a post-order | |||
189 | /// numbering of the reverse control flow graph. | |||
190 | void computeReversePostOrder(); | |||
191 | ||||
192 | /// Make the terminator of this block an unconditional branch to \p Target. | |||
193 | void makeUnconditional(BasicBlock *BB, BasicBlock *Target); | |||
194 | ||||
195 | public: | |||
196 | AggressiveDeadCodeElimination(Function &F, DominatorTree *DT, | |||
197 | PostDominatorTree &PDT) | |||
198 | : F(F), DT(DT), PDT(PDT) {} | |||
199 | ||||
200 | bool performDeadCodeElimination(); | |||
201 | }; | |||
202 | ||||
203 | } // end anonymous namespace | |||
204 | ||||
205 | bool AggressiveDeadCodeElimination::performDeadCodeElimination() { | |||
206 | initialize(); | |||
207 | markLiveInstructions(); | |||
208 | return removeDeadInstructions(); | |||
209 | } | |||
210 | ||||
211 | static bool isUnconditionalBranch(Instruction *Term) { | |||
212 | auto *BR = dyn_cast<BranchInst>(Term); | |||
213 | return BR && BR->isUnconditional(); | |||
214 | } | |||
215 | ||||
216 | void AggressiveDeadCodeElimination::initialize() { | |||
217 | auto NumBlocks = F.size(); | |||
218 | ||||
219 | // We will have an entry in the map for each block so we grow the | |||
220 | // structure to twice that size to keep the load factor low in the hash table. | |||
221 | BlockInfo.reserve(NumBlocks); | |||
222 | size_t NumInsts = 0; | |||
223 | ||||
224 | // Iterate over blocks and initialize BlockInfoVec entries, count | |||
225 | // instructions to size the InstInfo hash table. | |||
226 | for (auto &BB : F) { | |||
227 | NumInsts += BB.size(); | |||
228 | auto &Info = BlockInfo[&BB]; | |||
229 | Info.BB = &BB; | |||
230 | Info.Terminator = BB.getTerminator(); | |||
231 | Info.UnconditionalBranch = isUnconditionalBranch(Info.Terminator); | |||
232 | } | |||
233 | ||||
234 | // Initialize instruction map and set pointers to block info. | |||
235 | InstInfo.reserve(NumInsts); | |||
236 | for (auto &BBInfo : BlockInfo) | |||
237 | for (Instruction &I : *BBInfo.second.BB) | |||
238 | InstInfo[&I].Block = &BBInfo.second; | |||
239 | ||||
240 | // Since BlockInfoVec holds pointers into InstInfo and vice-versa, we may not | |||
241 | // add any more elements to either after this point. | |||
242 | for (auto &BBInfo : BlockInfo) | |||
243 | BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator]; | |||
244 | ||||
245 | // Collect the set of "root" instructions that are known live. | |||
246 | for (Instruction &I : instructions(F)) | |||
247 | if (isAlwaysLive(I)) | |||
248 | markLive(&I); | |||
249 | ||||
250 | if (!RemoveControlFlowFlag) | |||
251 | return; | |||
252 | ||||
253 | if (!RemoveLoops) { | |||
254 | // This stores state for the depth-first iterator. In addition | |||
255 | // to recording which nodes have been visited we also record whether | |||
256 | // a node is currently on the "stack" of active ancestors of the current | |||
257 | // node. | |||
258 | using StatusMap = DenseMap<BasicBlock *, bool>; | |||
259 | ||||
260 | class DFState : public StatusMap { | |||
261 | public: | |||
262 | std::pair<StatusMap::iterator, bool> insert(BasicBlock *BB) { | |||
263 | return StatusMap::insert(std::make_pair(BB, true)); | |||
264 | } | |||
265 | ||||
266 | // Invoked after we have visited all children of a node. | |||
267 | void completed(BasicBlock *BB) { (*this)[BB] = false; } | |||
268 | ||||
269 | // Return true if \p BB is currently on the active stack | |||
270 | // of ancestors. | |||
271 | bool onStack(BasicBlock *BB) { | |||
272 | auto Iter = find(BB); | |||
273 | return Iter != end() && Iter->second; | |||
274 | } | |||
275 | } State; | |||
276 | ||||
277 | State.reserve(F.size()); | |||
278 | // Iterate over blocks in depth-first pre-order and | |||
279 | // treat all edges to a block already seen as loop back edges | |||
280 | // and mark the branch live it if there is a back edge. | |||
281 | for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) { | |||
282 | Instruction *Term = BB->getTerminator(); | |||
283 | if (isLive(Term)) | |||
284 | continue; | |||
285 | ||||
286 | for (auto *Succ : successors(BB)) | |||
287 | if (State.onStack(Succ)) { | |||
288 | // back edge.... | |||
289 | markLive(Term); | |||
290 | break; | |||
291 | } | |||
292 | } | |||
293 | } | |||
294 | ||||
295 | // Mark blocks live if there is no path from the block to a | |||
296 | // return of the function. | |||
297 | // We do this by seeing which of the postdomtree root children exit the | |||
298 | // program, and for all others, mark the subtree live. | |||
299 | for (auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) { | |||
300 | auto *BB = PDTChild->getBlock(); | |||
301 | auto &Info = BlockInfo[BB]; | |||
302 | // Real function return | |||
303 | if (isa<ReturnInst>(Info.Terminator)) { | |||
304 | LLVM_DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName()do { } while (false) | |||
305 | << '\n';)do { } while (false); | |||
306 | continue; | |||
307 | } | |||
308 | ||||
309 | // This child is something else, like an infinite loop. | |||
310 | for (auto DFNode : depth_first(PDTChild)) | |||
311 | markLive(BlockInfo[DFNode->getBlock()].Terminator); | |||
312 | } | |||
313 | ||||
314 | // Treat the entry block as always live | |||
315 | auto *BB = &F.getEntryBlock(); | |||
316 | auto &EntryInfo = BlockInfo[BB]; | |||
317 | EntryInfo.Live = true; | |||
318 | if (EntryInfo.UnconditionalBranch) | |||
319 | markLive(EntryInfo.Terminator); | |||
320 | ||||
321 | // Build initial collection of blocks with dead terminators | |||
322 | for (auto &BBInfo : BlockInfo) | |||
323 | if (!BBInfo.second.terminatorIsLive()) | |||
324 | BlocksWithDeadTerminators.insert(BBInfo.second.BB); | |||
325 | } | |||
326 | ||||
327 | bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) { | |||
328 | // TODO -- use llvm::isInstructionTriviallyDead | |||
329 | if (I.isEHPad() || I.mayHaveSideEffects()) { | |||
330 | // Skip any value profile instrumentation calls if they are | |||
331 | // instrumenting constants. | |||
332 | if (isInstrumentsConstant(I)) | |||
333 | return false; | |||
334 | return true; | |||
335 | } | |||
336 | if (!I.isTerminator()) | |||
337 | return false; | |||
338 | if (RemoveControlFlowFlag && (isa<BranchInst>(I) || isa<SwitchInst>(I))) | |||
339 | return false; | |||
340 | return true; | |||
341 | } | |||
342 | ||||
343 | // Check if this instruction is a runtime call for value profiling and | |||
344 | // if it's instrumenting a constant. | |||
345 | bool AggressiveDeadCodeElimination::isInstrumentsConstant(Instruction &I) { | |||
346 | // TODO -- move this test into llvm::isInstructionTriviallyDead | |||
347 | if (CallInst *CI = dyn_cast<CallInst>(&I)) | |||
348 | if (Function *Callee = CI->getCalledFunction()) | |||
349 | if (Callee->getName().equals(getInstrProfValueProfFuncName())) | |||
350 | if (isa<Constant>(CI->getArgOperand(0))) | |||
351 | return true; | |||
352 | return false; | |||
353 | } | |||
354 | ||||
355 | void AggressiveDeadCodeElimination::markLiveInstructions() { | |||
356 | // Propagate liveness backwards to operands. | |||
357 | do { | |||
358 | // Worklist holds newly discovered live instructions | |||
359 | // where we need to mark the inputs as live. | |||
360 | while (!Worklist.empty()) { | |||
361 | Instruction *LiveInst = Worklist.pop_back_val(); | |||
362 | LLVM_DEBUG(dbgs() << "work live: "; LiveInst->dump();)do { } while (false); | |||
363 | ||||
364 | for (Use &OI : LiveInst->operands()) | |||
365 | if (Instruction *Inst = dyn_cast<Instruction>(OI)) | |||
366 | markLive(Inst); | |||
367 | ||||
368 | if (auto *PN = dyn_cast<PHINode>(LiveInst)) | |||
369 | markPhiLive(PN); | |||
370 | } | |||
371 | ||||
372 | // After data flow liveness has been identified, examine which branch | |||
373 | // decisions are required to determine live instructions are executed. | |||
374 | markLiveBranchesFromControlDependences(); | |||
375 | ||||
376 | } while (!Worklist.empty()); | |||
377 | } | |||
378 | ||||
379 | void AggressiveDeadCodeElimination::markLive(Instruction *I) { | |||
380 | auto &Info = InstInfo[I]; | |||
381 | if (Info.Live) | |||
382 | return; | |||
383 | ||||
384 | LLVM_DEBUG(dbgs() << "mark live: "; I->dump())do { } while (false); | |||
385 | Info.Live = true; | |||
386 | Worklist.push_back(I); | |||
387 | ||||
388 | // Collect the live debug info scopes attached to this instruction. | |||
389 | if (const DILocation *DL = I->getDebugLoc()) | |||
390 | collectLiveScopes(*DL); | |||
391 | ||||
392 | // Mark the containing block live | |||
393 | auto &BBInfo = *Info.Block; | |||
394 | if (BBInfo.Terminator == I) { | |||
395 | BlocksWithDeadTerminators.remove(BBInfo.BB); | |||
396 | // For live terminators, mark destination blocks | |||
397 | // live to preserve this control flow edges. | |||
398 | if (!BBInfo.UnconditionalBranch) | |||
399 | for (auto *BB : successors(I->getParent())) | |||
400 | markLive(BB); | |||
401 | } | |||
402 | markLive(BBInfo); | |||
403 | } | |||
404 | ||||
405 | void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) { | |||
406 | if (BBInfo.Live) | |||
407 | return; | |||
408 | LLVM_DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n')do { } while (false); | |||
409 | BBInfo.Live = true; | |||
410 | if (!BBInfo.CFLive) { | |||
411 | BBInfo.CFLive = true; | |||
412 | NewLiveBlocks.insert(BBInfo.BB); | |||
413 | } | |||
414 | ||||
415 | // Mark unconditional branches at the end of live | |||
416 | // blocks as live since there is no work to do for them later | |||
417 | if (BBInfo.UnconditionalBranch) | |||
418 | markLive(BBInfo.Terminator); | |||
419 | } | |||
420 | ||||
421 | void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) { | |||
422 | if (!AliveScopes.insert(&LS).second) | |||
423 | return; | |||
424 | ||||
425 | if (isa<DISubprogram>(LS)) | |||
426 | return; | |||
427 | ||||
428 | // Tail-recurse through the scope chain. | |||
429 | collectLiveScopes(cast<DILocalScope>(*LS.getScope())); | |||
430 | } | |||
431 | ||||
432 | void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) { | |||
433 | // Even though DILocations are not scopes, shove them into AliveScopes so we | |||
434 | // don't revisit them. | |||
435 | if (!AliveScopes.insert(&DL).second) | |||
436 | return; | |||
437 | ||||
438 | // Collect live scopes from the scope chain. | |||
439 | collectLiveScopes(*DL.getScope()); | |||
440 | ||||
441 | // Tail-recurse through the inlined-at chain. | |||
442 | if (const DILocation *IA = DL.getInlinedAt()) | |||
443 | collectLiveScopes(*IA); | |||
444 | } | |||
445 | ||||
446 | void AggressiveDeadCodeElimination::markPhiLive(PHINode *PN) { | |||
447 | auto &Info = BlockInfo[PN->getParent()]; | |||
448 | // Only need to check this once per block. | |||
449 | if (Info.HasLivePhiNodes) | |||
450 | return; | |||
451 | Info.HasLivePhiNodes = true; | |||
452 | ||||
453 | // If a predecessor block is not live, mark it as control-flow live | |||
454 | // which will trigger marking live branches upon which | |||
455 | // that block is control dependent. | |||
456 | for (auto *PredBB : predecessors(Info.BB)) { | |||
457 | auto &Info = BlockInfo[PredBB]; | |||
458 | if (!Info.CFLive) { | |||
459 | Info.CFLive = true; | |||
460 | NewLiveBlocks.insert(PredBB); | |||
461 | } | |||
462 | } | |||
463 | } | |||
464 | ||||
465 | void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() { | |||
466 | if (BlocksWithDeadTerminators.empty()) | |||
467 | return; | |||
468 | ||||
469 | LLVM_DEBUG({do { } while (false) | |||
470 | dbgs() << "new live blocks:\n";do { } while (false) | |||
471 | for (auto *BB : NewLiveBlocks)do { } while (false) | |||
472 | dbgs() << "\t" << BB->getName() << '\n';do { } while (false) | |||
473 | dbgs() << "dead terminator blocks:\n";do { } while (false) | |||
474 | for (auto *BB : BlocksWithDeadTerminators)do { } while (false) | |||
475 | dbgs() << "\t" << BB->getName() << '\n';do { } while (false) | |||
476 | })do { } while (false); | |||
477 | ||||
478 | // The dominance frontier of a live block X in the reverse | |||
479 | // control graph is the set of blocks upon which X is control | |||
480 | // dependent. The following sequence computes the set of blocks | |||
481 | // which currently have dead terminators that are control | |||
482 | // dependence sources of a block which is in NewLiveBlocks. | |||
483 | ||||
484 | const SmallPtrSet<BasicBlock *, 16> BWDT{ | |||
485 | BlocksWithDeadTerminators.begin(), | |||
486 | BlocksWithDeadTerminators.end() | |||
487 | }; | |||
488 | SmallVector<BasicBlock *, 32> IDFBlocks; | |||
489 | ReverseIDFCalculator IDFs(PDT); | |||
490 | IDFs.setDefiningBlocks(NewLiveBlocks); | |||
491 | IDFs.setLiveInBlocks(BWDT); | |||
492 | IDFs.calculate(IDFBlocks); | |||
493 | NewLiveBlocks.clear(); | |||
494 | ||||
495 | // Dead terminators which control live blocks are now marked live. | |||
496 | for (auto *BB : IDFBlocks) { | |||
497 | LLVM_DEBUG(dbgs() << "live control in: " << BB->getName() << '\n')do { } while (false); | |||
498 | markLive(BB->getTerminator()); | |||
499 | } | |||
500 | } | |||
501 | ||||
502 | //===----------------------------------------------------------------------===// | |||
503 | // | |||
504 | // Routines to update the CFG and SSA information before removing dead code. | |||
505 | // | |||
506 | //===----------------------------------------------------------------------===// | |||
507 | bool AggressiveDeadCodeElimination::removeDeadInstructions() { | |||
508 | // Updates control and dataflow around dead blocks | |||
509 | bool RegionsUpdated = updateDeadRegions(); | |||
510 | ||||
511 | LLVM_DEBUG({do { } while (false) | |||
512 | for (Instruction &I : instructions(F)) {do { } while (false) | |||
513 | // Check if the instruction is alive.do { } while (false) | |||
514 | if (isLive(&I))do { } while (false) | |||
515 | continue;do { } while (false) | |||
516 | ||||
517 | if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {do { } while (false) | |||
518 | // Check if the scope of this variable location is alive.do { } while (false) | |||
519 | if (AliveScopes.count(DII->getDebugLoc()->getScope()))do { } while (false) | |||
520 | continue;do { } while (false) | |||
521 | ||||
522 | // If intrinsic is pointing at a live SSA value, there may be ando { } while (false) | |||
523 | // earlier optimization bug: if we know the location of the variable,do { } while (false) | |||
524 | // why isn't the scope of the location alive?do { } while (false) | |||
525 | for (Value *V : DII->location_ops()) {do { } while (false) | |||
526 | if (Instruction *II = dyn_cast<Instruction>(V)) {do { } while (false) | |||
527 | if (isLive(II)) {do { } while (false) | |||
528 | dbgs() << "Dropping debug info for " << *DII << "\n";do { } while (false) | |||
529 | break;do { } while (false) | |||
530 | }do { } while (false) | |||
531 | }do { } while (false) | |||
532 | }do { } while (false) | |||
533 | }do { } while (false) | |||
534 | }do { } while (false) | |||
535 | })do { } while (false); | |||
536 | ||||
537 | // The inverse of the live set is the dead set. These are those instructions | |||
538 | // that have no side effects and do not influence the control flow or return | |||
539 | // value of the function, and may therefore be deleted safely. | |||
540 | // NOTE: We reuse the Worklist vector here for memory efficiency. | |||
541 | for (Instruction &I : instructions(F)) { | |||
542 | // Check if the instruction is alive. | |||
543 | if (isLive(&I)) | |||
544 | continue; | |||
545 | ||||
546 | if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) { | |||
547 | // Check if the scope of this variable location is alive. | |||
548 | if (AliveScopes.count(DII->getDebugLoc()->getScope())) | |||
549 | continue; | |||
550 | ||||
551 | // Fallthrough and drop the intrinsic. | |||
552 | } | |||
553 | ||||
554 | // Prepare to delete. | |||
555 | Worklist.push_back(&I); | |||
556 | salvageDebugInfo(I); | |||
557 | I.dropAllReferences(); | |||
558 | } | |||
559 | ||||
560 | for (Instruction *&I : Worklist) { | |||
561 | ++NumRemoved; | |||
562 | I->eraseFromParent(); | |||
563 | } | |||
564 | ||||
565 | return !Worklist.empty() || RegionsUpdated; | |||
566 | } | |||
567 | ||||
568 | // A dead region is the set of dead blocks with a common live post-dominator. | |||
569 | bool AggressiveDeadCodeElimination::updateDeadRegions() { | |||
570 | LLVM_DEBUG({do { } while (false) | |||
571 | dbgs() << "final dead terminator blocks: " << '\n';do { } while (false) | |||
572 | for (auto *BB : BlocksWithDeadTerminators)do { } while (false) | |||
573 | dbgs() << '\t' << BB->getName()do { } while (false) | |||
574 | << (BlockInfo[BB].Live ? " LIVE\n" : "\n");do { } while (false) | |||
575 | })do { } while (false); | |||
576 | ||||
577 | // Don't compute the post ordering unless we needed it. | |||
578 | bool HavePostOrder = false; | |||
579 | bool Changed = false; | |||
580 | ||||
581 | for (auto *BB : BlocksWithDeadTerminators) { | |||
582 | auto &Info = BlockInfo[BB]; | |||
583 | if (Info.UnconditionalBranch) { | |||
584 | InstInfo[Info.Terminator].Live = true; | |||
585 | continue; | |||
586 | } | |||
587 | ||||
588 | if (!HavePostOrder
| |||
589 | computeReversePostOrder(); | |||
590 | HavePostOrder = true; | |||
591 | } | |||
592 | ||||
593 | // Add an unconditional branch to the successor closest to the | |||
594 | // end of the function which insures a path to the exit for each | |||
595 | // live edge. | |||
596 | BlockInfoType *PreferredSucc = nullptr; | |||
597 | for (auto *Succ : successors(BB)) { | |||
598 | auto *Info = &BlockInfo[Succ]; | |||
599 | if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder) | |||
600 | PreferredSucc = Info; | |||
601 | } | |||
602 | assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&(static_cast<void> (0)) | |||
603 | "Failed to find safe successor for dead branch")(static_cast<void> (0)); | |||
604 | ||||
605 | // Collect removed successors to update the (Post)DominatorTrees. | |||
606 | SmallPtrSet<BasicBlock *, 4> RemovedSuccessors; | |||
607 | bool First = true; | |||
608 | for (auto *Succ : successors(BB)) { | |||
609 | if (!First
| |||
| ||||
610 | Succ->removePredecessor(BB); | |||
611 | RemovedSuccessors.insert(Succ); | |||
612 | } else | |||
613 | First = false; | |||
614 | } | |||
615 | makeUnconditional(BB, PreferredSucc->BB); | |||
616 | ||||
617 | // Inform the dominators about the deleted CFG edges. | |||
618 | SmallVector<DominatorTree::UpdateType, 4> DeletedEdges; | |||
619 | for (auto *Succ : RemovedSuccessors) { | |||
620 | // It might have happened that the same successor appeared multiple times | |||
621 | // and the CFG edge wasn't really removed. | |||
622 | if (Succ != PreferredSucc->BB) { | |||
623 | LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"do { } while (false) | |||
624 | << BB->getName() << " -> " << Succ->getName()do { } while (false) | |||
625 | << "\n")do { } while (false); | |||
626 | DeletedEdges.push_back({DominatorTree::Delete, BB, Succ}); | |||
627 | } | |||
628 | } | |||
629 | ||||
630 | DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager) | |||
631 | .applyUpdates(DeletedEdges); | |||
632 | ||||
633 | NumBranchesRemoved += 1; | |||
634 | Changed = true; | |||
635 | } | |||
636 | ||||
637 | return Changed; | |||
638 | } | |||
639 | ||||
640 | // reverse top-sort order | |||
641 | void AggressiveDeadCodeElimination::computeReversePostOrder() { | |||
642 | // This provides a post-order numbering of the reverse control flow graph | |||
643 | // Note that it is incomplete in the presence of infinite loops but we don't | |||
644 | // need numbers blocks which don't reach the end of the functions since | |||
645 | // all branches in those blocks are forced live. | |||
646 | ||||
647 | // For each block without successors, extend the DFS from the block | |||
648 | // backward through the graph | |||
649 | SmallPtrSet<BasicBlock*, 16> Visited; | |||
650 | unsigned PostOrder = 0; | |||
651 | for (auto &BB : F) { | |||
652 | if (!succ_empty(&BB)) | |||
653 | continue; | |||
654 | for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited)) | |||
655 | BlockInfo[Block].PostOrder = PostOrder++; | |||
656 | } | |||
657 | } | |||
658 | ||||
659 | void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB, | |||
660 | BasicBlock *Target) { | |||
661 | Instruction *PredTerm = BB->getTerminator(); | |||
662 | // Collect the live debug info scopes attached to this instruction. | |||
663 | if (const DILocation *DL = PredTerm->getDebugLoc()) | |||
664 | collectLiveScopes(*DL); | |||
665 | ||||
666 | // Just mark live an existing unconditional branch | |||
667 | if (isUnconditionalBranch(PredTerm)) { | |||
668 | PredTerm->setSuccessor(0, Target); | |||
669 | InstInfo[PredTerm].Live = true; | |||
670 | return; | |||
671 | } | |||
672 | LLVM_DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n')do { } while (false); | |||
673 | NumBranchesRemoved += 1; | |||
674 | IRBuilder<> Builder(PredTerm); | |||
675 | auto *NewTerm = Builder.CreateBr(Target); | |||
676 | InstInfo[NewTerm].Live = true; | |||
677 | if (const DILocation *DL = PredTerm->getDebugLoc()) | |||
678 | NewTerm->setDebugLoc(DL); | |||
679 | ||||
680 | InstInfo.erase(PredTerm); | |||
681 | PredTerm->eraseFromParent(); | |||
682 | } | |||
683 | ||||
684 | //===----------------------------------------------------------------------===// | |||
685 | // | |||
686 | // Pass Manager integration code | |||
687 | // | |||
688 | //===----------------------------------------------------------------------===// | |||
689 | PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) { | |||
690 | // ADCE does not need DominatorTree, but require DominatorTree here | |||
691 | // to update analysis if it is already available. | |||
692 | auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F); | |||
693 | auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F); | |||
694 | if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination()) | |||
695 | return PreservedAnalyses::all(); | |||
696 | ||||
697 | PreservedAnalyses PA; | |||
698 | // TODO: We could track if we have actually done CFG changes. | |||
699 | if (!RemoveControlFlowFlag) | |||
700 | PA.preserveSet<CFGAnalyses>(); | |||
701 | else { | |||
702 | PA.preserve<DominatorTreeAnalysis>(); | |||
703 | PA.preserve<PostDominatorTreeAnalysis>(); | |||
704 | } | |||
705 | return PA; | |||
706 | } | |||
707 | ||||
708 | namespace { | |||
709 | ||||
710 | struct ADCELegacyPass : public FunctionPass { | |||
711 | static char ID; // Pass identification, replacement for typeid | |||
712 | ||||
713 | ADCELegacyPass() : FunctionPass(ID) { | |||
714 | initializeADCELegacyPassPass(*PassRegistry::getPassRegistry()); | |||
715 | } | |||
716 | ||||
717 | bool runOnFunction(Function &F) override { | |||
718 | if (skipFunction(F)) | |||
| ||||
719 | return false; | |||
720 | ||||
721 | // ADCE does not need DominatorTree, but require DominatorTree here | |||
722 | // to update analysis if it is already available. | |||
723 | auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); | |||
724 | auto *DT = DTWP
| |||
725 | auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(); | |||
726 | return AggressiveDeadCodeElimination(F, DT, PDT) | |||
727 | .performDeadCodeElimination(); | |||
728 | } | |||
729 | ||||
730 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
731 | AU.addRequired<PostDominatorTreeWrapperPass>(); | |||
732 | if (!RemoveControlFlowFlag) | |||
733 | AU.setPreservesCFG(); | |||
734 | else { | |||
735 | AU.addPreserved<DominatorTreeWrapperPass>(); | |||
736 | AU.addPreserved<PostDominatorTreeWrapperPass>(); | |||
737 | } | |||
738 | AU.addPreserved<GlobalsAAWrapperPass>(); | |||
739 | } | |||
740 | }; | |||
741 | ||||
742 | } // end anonymous namespace | |||
743 | ||||
744 | char ADCELegacyPass::ID = 0; | |||
745 | ||||
746 | INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",static void *initializeADCELegacyPassPassOnce(PassRegistry & Registry) { | |||
747 | "Aggressive Dead Code Elimination", false, false)static void *initializeADCELegacyPassPassOnce(PassRegistry & Registry) { | |||
748 | INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry); | |||
749 | INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",PassInfo *PI = new PassInfo( "Aggressive Dead Code Elimination" , "adce", &ADCELegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <ADCELegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeADCELegacyPassPassFlag ; void llvm::initializeADCELegacyPassPass(PassRegistry &Registry ) { llvm::call_once(InitializeADCELegacyPassPassFlag, initializeADCELegacyPassPassOnce , std::ref(Registry)); } | |||
750 | false, false)PassInfo *PI = new PassInfo( "Aggressive Dead Code Elimination" , "adce", &ADCELegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <ADCELegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeADCELegacyPassPassFlag ; void llvm::initializeADCELegacyPassPass(PassRegistry &Registry ) { llvm::call_once(InitializeADCELegacyPassPassFlag, initializeADCELegacyPassPassOnce , std::ref(Registry)); } | |||
751 | ||||
752 | FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); } |