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