Bug Summary

File:llvm/lib/Transforms/Scalar/ADCE.cpp
Warning:line 615, column 27
Access to field 'BB' results in a dereference of a null pointer (loaded from variable 'PreferredSucc')

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ADCE.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Scalar -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Scalar/ADCE.cpp
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
58using namespace llvm;
59
60#define DEBUG_TYPE"adce" "adce"
61
62STATISTIC(NumRemoved, "Number of instructions removed")static llvm::Statistic NumRemoved = {"adce", "NumRemoved", "Number of instructions removed"
}
;
63STATISTIC(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.
67static 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.
72static cl::opt<bool> RemoveLoops("adce-remove-loops", cl::init(false),
73 cl::Hidden);
74
75namespace {
76
77/// Information about Instructions
78struct 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.
87struct 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
116class 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
195public:
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
205bool AggressiveDeadCodeElimination::performDeadCodeElimination() {
206 initialize();
207 markLiveInstructions();
208 return removeDeadInstructions();
5
Calling 'AggressiveDeadCodeElimination::removeDeadInstructions'
209}
210
211static bool isUnconditionalBranch(Instruction *Term) {
212 auto *BR = dyn_cast<BranchInst>(Term);
213 return BR && BR->isUnconditional();
214}
215
216void 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
327bool 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.
345bool 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
355void 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
379void 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
405void 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
421void 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
432void 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
446void 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
465void 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//===----------------------------------------------------------------------===//
507bool AggressiveDeadCodeElimination::removeDeadInstructions() {
508 // Updates control and dataflow around dead blocks
509 bool RegionsUpdated = updateDeadRegions();
6
Calling 'AggressiveDeadCodeElimination::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.
569bool AggressiveDeadCodeElimination::updateDeadRegions() {
570 LLVM_DEBUG({do { } while (false)
7
Loop condition is false. Exiting loop
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) {
8
Assuming '__begin1' is not equal to '__end1'
582 auto &Info = BlockInfo[BB];
583 if (Info.UnconditionalBranch) {
9
Assuming field 'UnconditionalBranch' is false
10
Taking false branch
584 InstInfo[Info.Terminator].Live = true;
585 continue;
586 }
587
588 if (!HavePostOrder
10.1
'HavePostOrder' is false
) {
11
Taking true branch
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;
12
'PreferredSucc' initialized to a null pointer value
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 || Succ != PreferredSucc->BB) {
610 Succ->removePredecessor(BB);
611 RemovedSuccessors.insert(Succ);
612 } else
613 First = false;
614 }
615 makeUnconditional(BB, PreferredSucc->BB);
13
Access to field 'BB' results in a dereference of a null pointer (loaded from variable 'PreferredSucc')
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
641void 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
659void 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//===----------------------------------------------------------------------===//
689PreservedAnalyses 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
708namespace {
709
710struct 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))
1
Assuming the condition is false
2
Taking false branch
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
2.1
'DTWP' is null
? &DTWP->getDomTree() : nullptr;
3
'?' condition is false
725 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
726 return AggressiveDeadCodeElimination(F, DT, PDT)
4
Calling 'AggressiveDeadCodeElimination::performDeadCodeElimination'
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
744char ADCELegacyPass::ID = 0;
745
746INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",static void *initializeADCELegacyPassPassOnce(PassRegistry &
Registry) {
747 "Aggressive Dead Code Elimination", false, false)static void *initializeADCELegacyPassPassOnce(PassRegistry &
Registry) {
748INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry);
749INITIALIZE_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
752FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }