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 "ScalarOptions.h"
18#include "llvm/ADT/DepthFirstIterator.h"
19#include "llvm/ADT/GraphTraits.h"
20#include "llvm/ADT/PostOrderIterator.h"
21#include "llvm/ADT/SetVector.h"
22#include "llvm/ADT/SmallPtrSet.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/ADT/Statistic.h"
25#include "llvm/Analysis/CFG.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/PassManager.h"
43#include "llvm/IR/Use.h"
44#include "llvm/IR/Value.h"
45#include "llvm/ProfileData/InstrProf.h"
46#include "llvm/Support/Casting.h"
47#include "llvm/Support/Debug.h"
48#include "llvm/Support/raw_ostream.h"
49#include "llvm/Transforms/Utils/Local.h"
50#include <cassert>
51#include <cstddef>
52#include <utility>
53
54using namespace llvm;
55
56#define DEBUG_TYPE "adce"
57
58STATISTIC(NumRemoved, "Number of instructions removed");
59STATISTIC(NumBranchesRemoved, "Number of branch instructions removed");
60
61namespace {
62
63/// Information about basic blocks relevant to dead code elimination.
64struct BlockInfoType {
65 /// True when this block contains a live instructions.
66 bool Live = false;
67
68 /// True when this block is known to have live PHI nodes.
69 bool HasLivePhiNodes = false;
70
71 /// Control dependence sources need to be live for this block.
72 bool CFLive = false;
73
74 /// Post-order numbering of reverse control flow graph.
75 unsigned PostOrder = 0;
76};
77
78struct ADCEChanged {
79 bool ChangedAnything = false;
80 bool ChangedNonDebugInstr = false;
81 bool ChangedControlFlow = false;
82};
83
84class AggressiveDeadCodeElimination {
85 const ScalarOptions &Opts;
86 Function &F;
87
88 // ADCE does not use DominatorTree per se, but it updates it to preserve the
89 // analysis.
90 DominatorTree *DT;
91 PostDominatorTree &PDT;
92
93 /// Mapping of blocks to associated information, indexed by block number.
94 SmallVector<BlockInfoType> BlockInfo;
95
96 /// Set of live instructions.
97 SmallPtrSet<Instruction *, 32> LiveInst;
98 bool isLive(Instruction *I) { return LiveInst.contains(Ptr: I); }
99
100 /// Instructions known to be live where we need to mark
101 /// reaching definitions as live.
102 SmallVector<Instruction *, 128> Worklist;
103
104 /// Debug info scopes around a live instruction.
105 SmallPtrSet<const Metadata *, 32> AliveScopes;
106
107 /// Set of blocks with not known to have live terminators.
108 SmallSetVector<BasicBlock *, 16> BlocksWithDeadTerminators;
109
110 /// The set of blocks which we have determined whose control
111 /// dependence sources must be live and which have not had
112 /// those dependences analyzed.
113 SmallPtrSet<BasicBlock *, 16> NewLiveBlocks;
114
115 /// Set up auxiliary data structures for Instructions and BasicBlocks and
116 /// initialize the Worklist to the set of must-be-live Instruscions.
117 void initialize();
118
119 BlockInfoType &getBlockInfo(BasicBlock *BB) {
120 return BlockInfo[BB->getNumber()];
121 }
122
123 /// Return true for operations which are always treated as live.
124 bool isAlwaysLive(Instruction &I);
125
126 /// Return true for instrumentation instructions for value profiling.
127 bool isInstrumentsConstant(Instruction &I);
128
129 /// Propagate liveness to reaching definitions.
130 void markLiveInstructions();
131
132 /// Mark an instruction as live.
133 void markLive(Instruction *I);
134
135 /// Mark a block as live.
136 void markLive(BasicBlock *BB);
137
138 /// Mark terminators of control predecessors of a PHI node live.
139 void markPhiLive(PHINode *PN);
140
141 /// Record the Debug Scopes which surround live debug information.
142 void collectLiveScopes(const DILocalScope &LS);
143 void collectLiveScopes(const DILocation &DL);
144
145 /// Analyze dead branches to find those whose branches are the sources
146 /// of control dependences impacting a live block. Those branches are
147 /// marked live.
148 void markLiveBranchesFromControlDependences();
149
150 /// Remove instructions not marked live, return if any instruction was
151 /// removed.
152 ADCEChanged removeDeadInstructions();
153
154 /// Identify connected sections of the control flow graph which have
155 /// dead terminators and rewrite the control flow graph to remove them.
156 bool updateDeadRegions();
157
158 /// Set the BlockInfo::PostOrder field based on a post-order
159 /// numbering of the reverse control flow graph.
160 void computeReversePostOrder();
161
162 /// Make the terminator of this block an unconditional branch to \p Target.
163 void makeUnconditional(BasicBlock *BB, BasicBlock *Target);
164
165public:
166 AggressiveDeadCodeElimination(const ScalarOptions &Opts, Function &F,
167 DominatorTree *DT, PostDominatorTree &PDT)
168 : Opts(Opts), F(F), DT(DT), PDT(PDT) {}
169
170 ADCEChanged performDeadCodeElimination();
171};
172
173} // end anonymous namespace
174
175ADCEChanged AggressiveDeadCodeElimination::performDeadCodeElimination() {
176 initialize();
177 markLiveInstructions();
178 return removeDeadInstructions();
179}
180
181void AggressiveDeadCodeElimination::initialize() {
182 BlockInfo.resize(N: F.getMaxBlockNumber());
183 size_t NumInsts = 0;
184 for (auto &BB : F)
185 NumInsts += BB.size();
186 LiveInst.reserve(NewNumEntries: NumInsts);
187
188 // Collect the set of "root" instructions that are known live.
189 for (Instruction &I : instructions(F))
190 if (isAlwaysLive(I))
191 markLive(I: &I);
192
193 if (!Opts.adce_remove_control_flow)
194 return;
195
196 if (!Opts.adce_remove_loops) {
197 // Mark all terminators that have backedges as live.
198 SmallVector<std::pair<const BasicBlock *, const BasicBlock *>> Backedges;
199 FindFunctionBackedges(F, Result&: Backedges);
200 for (const auto &[Src, Dst] : Backedges)
201 markLive(I: const_cast<Instruction *>(Src->getTerminator()));
202 }
203
204 // Mark blocks live if there is no path from the block to a
205 // return of the function.
206 // We do this by seeing which of the postdomtree root children exit the
207 // program, and for all others, mark the subtree live.
208 for (const auto &PDTChild : children<DomTreeNode *>(G: PDT.getRootNode())) {
209 auto *BB = PDTChild->getBlock();
210 // Real function return
211 if (isa<ReturnInst>(Val: BB->back())) {
212 LLVM_DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName()
213 << '\n';);
214 continue;
215 }
216
217 // This child is something else, like an infinite loop.
218 for (auto *DFNode : depth_first(G: PDTChild))
219 markLive(I: &DFNode->getBlock()->back());
220 }
221
222 // Treat the entry block as always live
223 auto *BB = &F.getEntryBlock();
224 auto &EntryInfo = getBlockInfo(BB);
225 EntryInfo.Live = true;
226 if (isa<UncondBrInst>(Val: BB->back()))
227 markLive(I: &BB->back());
228
229 // Build initial collection of blocks with dead terminators
230 for (auto &BB : F)
231 if (!isLive(I: &BB.back()))
232 BlocksWithDeadTerminators.insert(X: &BB);
233}
234
235bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) {
236 // TODO -- use llvm::isInstructionTriviallyDead
237 if (I.isEHPad() || I.mayHaveSideEffects()) {
238 // Skip any value profile instrumentation calls if they are
239 // instrumenting constants.
240 if (isInstrumentsConstant(I))
241 return false;
242 return true;
243 }
244 if (!I.isTerminator())
245 return false;
246 if (Opts.adce_remove_control_flow &&
247 isa<UncondBrInst, CondBrInst, SwitchInst>(Val: I))
248 return false;
249 return true;
250}
251
252// Check if this instruction is a runtime call for value profiling and
253// if it's instrumenting a constant.
254bool AggressiveDeadCodeElimination::isInstrumentsConstant(Instruction &I) {
255 // TODO -- move this test into llvm::isInstructionTriviallyDead
256 if (CallInst *CI = dyn_cast<CallInst>(Val: &I))
257 if (Function *Callee = CI->getCalledFunction())
258 if (Callee->getName() == getInstrProfValueProfFuncName())
259 if (isa<Constant>(Val: CI->getArgOperand(i: 0)))
260 return true;
261 return false;
262}
263
264void AggressiveDeadCodeElimination::markLiveInstructions() {
265 // Propagate liveness backwards to operands.
266 do {
267 // Worklist holds newly discovered live instructions
268 // where we need to mark the inputs as live.
269 while (!Worklist.empty()) {
270 Instruction *LiveInst = Worklist.pop_back_val();
271 LLVM_DEBUG(dbgs() << "work live: "; LiveInst->dump(););
272
273 for (Use &OI : LiveInst->operands())
274 if (Instruction *Inst = dyn_cast<Instruction>(Val&: OI))
275 markLive(I: Inst);
276
277 if (auto *PN = dyn_cast<PHINode>(Val: LiveInst))
278 markPhiLive(PN);
279 }
280
281 // After data flow liveness has been identified, examine which branch
282 // decisions are required to determine live instructions are executed.
283 markLiveBranchesFromControlDependences();
284
285 } while (!Worklist.empty());
286}
287
288void AggressiveDeadCodeElimination::markLive(Instruction *I) {
289 auto [It, Inserted] = LiveInst.insert(Ptr: I);
290 if (!Inserted)
291 return;
292
293 LLVM_DEBUG(dbgs() << "mark live: "; I->dump());
294 Worklist.push_back(Elt: I);
295
296 // Collect the live debug info scopes attached to this instruction.
297 if (const DILocation *DL = I->getDebugLoc())
298 collectLiveScopes(DL: *DL);
299
300 // Mark the containing block live
301 BasicBlock *BB = I->getParent();
302 if (I == &BB->back()) {
303 BlocksWithDeadTerminators.remove(X: BB);
304 // For live terminators, mark destination blocks
305 // live to preserve this control flow edges.
306 if (!isa<UncondBrInst>(Val: I))
307 for (auto *Succ : I->successors())
308 markLive(BB: Succ);
309 }
310 markLive(BB);
311}
312
313void AggressiveDeadCodeElimination::markLive(BasicBlock *BB) {
314 auto &BBInfo = BlockInfo[BB->getNumber()];
315 if (BBInfo.Live)
316 return;
317 LLVM_DEBUG(dbgs() << "mark block live: " << BB->getName() << '\n');
318 BBInfo.Live = true;
319 if (!BBInfo.CFLive) {
320 BBInfo.CFLive = true;
321 NewLiveBlocks.insert(Ptr: BB);
322 }
323
324 // Mark unconditional branches at the end of live
325 // blocks as live since there is no work to do for them later
326 if (isa<UncondBrInst>(Val: BB->back()))
327 markLive(I: &BB->back());
328}
329
330void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) {
331 if (!AliveScopes.insert(Ptr: &LS).second)
332 return;
333
334 if (isa<DISubprogram>(Val: LS))
335 return;
336
337 // Tail-recurse through the scope chain.
338 collectLiveScopes(LS: cast<DILocalScope>(Val&: *LS.getScope()));
339}
340
341void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) {
342 // Even though DILocations are not scopes, shove them into AliveScopes so we
343 // don't revisit them.
344 if (!AliveScopes.insert(Ptr: &DL).second)
345 return;
346
347 // Collect live scopes from the scope chain.
348 collectLiveScopes(LS: *DL.getScope());
349
350 // Tail-recurse through the inlined-at chain.
351 if (const DILocation *IA = DL.getInlinedAt())
352 collectLiveScopes(DL: *IA);
353}
354
355void AggressiveDeadCodeElimination::markPhiLive(PHINode *PN) {
356 auto &Info = getBlockInfo(BB: PN->getParent());
357 // Only need to check this once per block.
358 if (Info.HasLivePhiNodes)
359 return;
360 Info.HasLivePhiNodes = true;
361
362 // If a predecessor block is not live, mark it as control-flow live
363 // which will trigger marking live branches upon which
364 // that block is control dependent.
365 for (auto *PredBB : predecessors(BB: PN->getParent())) {
366 auto &Info = getBlockInfo(BB: PredBB);
367 if (!Info.CFLive) {
368 Info.CFLive = true;
369 NewLiveBlocks.insert(Ptr: PredBB);
370 }
371 }
372}
373
374void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
375 if (BlocksWithDeadTerminators.empty())
376 return;
377
378 LLVM_DEBUG({
379 dbgs() << "new live blocks:\n";
380 for (auto *BB : NewLiveBlocks)
381 dbgs() << "\t" << BB->getName() << '\n';
382 dbgs() << "dead terminator blocks:\n";
383 for (auto *BB : BlocksWithDeadTerminators)
384 dbgs() << "\t" << BB->getName() << '\n';
385 });
386
387 // The dominance frontier of a live block X in the reverse
388 // control graph is the set of blocks upon which X is control
389 // dependent. The following sequence computes the set of blocks
390 // which currently have dead terminators that are control
391 // dependence sources of a block which is in NewLiveBlocks.
392
393 const SmallPtrSet<BasicBlock *, 16> BWDT(llvm::from_range,
394 BlocksWithDeadTerminators);
395 SmallVector<BasicBlock *, 32> IDFBlocks;
396 ReverseIDFCalculator IDFs(PDT);
397 IDFs.setDefiningBlocks(NewLiveBlocks);
398 IDFs.setLiveInBlocks(BWDT);
399 IDFs.calculate(IDFBlocks);
400 NewLiveBlocks.clear();
401
402 // Dead terminators which control live blocks are now marked live.
403 for (auto *BB : IDFBlocks) {
404 LLVM_DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');
405 markLive(I: BB->getTerminator());
406 }
407}
408
409//===----------------------------------------------------------------------===//
410//
411// Routines to update the CFG and SSA information before removing dead code.
412//
413//===----------------------------------------------------------------------===//
414ADCEChanged AggressiveDeadCodeElimination::removeDeadInstructions() {
415 ADCEChanged Changed;
416 // Updates control and dataflow around dead blocks
417 Changed.ChangedControlFlow = updateDeadRegions();
418
419 // The inverse of the live set is the dead set. These are those instructions
420 // that have no side effects and do not influence the control flow or return
421 // value of the function, and may therefore be deleted safely.
422 // NOTE: We reuse the Worklist vector here for memory efficiency.
423 for (Instruction &I : llvm::reverse(C: instructions(F))) {
424 // With "RemoveDIs" debug-info stored in DbgVariableRecord objects,
425 // debug-info attached to this instruction, and drop any for scopes that
426 // aren't alive, like the rest of this loop does. Extending support to
427 // assignment tracking is future work.
428 for (DbgRecord &DR : make_early_inc_range(Range: I.getDbgRecordRange())) {
429 // Avoid removing a DVR that is linked to instructions because it holds
430 // information about an existing store.
431 if (DbgVariableRecord *DVR = dyn_cast<DbgVariableRecord>(Val: &DR);
432 DVR && DVR->isDbgAssign())
433 if (!at::getAssignmentInsts(DVR).empty())
434 continue;
435 if (AliveScopes.count(Ptr: DR.getDebugLoc()->getScope()))
436 continue;
437 I.dropOneDbgRecord(I: &DR);
438 }
439
440 // Check if the instruction is alive.
441 if (isLive(I: &I))
442 continue;
443
444 Changed.ChangedNonDebugInstr = true;
445
446 // Prepare to delete.
447 Worklist.push_back(Elt: &I);
448 salvageDebugInfo(I);
449 }
450
451 for (Instruction *&I : Worklist)
452 I->dropAllReferences();
453
454 for (Instruction *&I : Worklist) {
455 ++NumRemoved;
456 I->eraseFromParent();
457 }
458
459 Changed.ChangedAnything = Changed.ChangedControlFlow || !Worklist.empty();
460
461 return Changed;
462}
463
464// A dead region is the set of dead blocks with a common live post-dominator.
465bool AggressiveDeadCodeElimination::updateDeadRegions() {
466 LLVM_DEBUG({
467 dbgs() << "final dead terminator blocks: " << '\n';
468 for (auto *BB : BlocksWithDeadTerminators)
469 dbgs() << '\t' << BB->getName()
470 << (getBlockInfo(BB).Live ? " LIVE\n" : "\n");
471 });
472
473 // Don't compute the post ordering unless we needed it.
474 bool HavePostOrder = false;
475 bool Changed = false;
476 SmallVector<DominatorTree::UpdateType, 10> DeletedEdges;
477
478 for (auto *BB : BlocksWithDeadTerminators) {
479 if (isa<UncondBrInst>(Val: BB->back())) {
480 LiveInst.insert(Ptr: &BB->back());
481 continue;
482 }
483
484 if (!HavePostOrder) {
485 computeReversePostOrder();
486 HavePostOrder = true;
487 }
488
489 // Add an unconditional branch to the successor closest to the
490 // end of the function which insures a path to the exit for each
491 // live edge.
492 BasicBlock *PreferredSucc = nullptr;
493 unsigned PreferredSuccPostOrder = 0;
494 for (auto *Succ : successors(BB)) {
495 unsigned SuccPostOrder = BlockInfo[Succ->getNumber()].PostOrder;
496 if (PreferredSuccPostOrder < SuccPostOrder) {
497 PreferredSucc = Succ;
498 PreferredSuccPostOrder = SuccPostOrder;
499 }
500 }
501 assert((PreferredSucc && PreferredSuccPostOrder > 0) &&
502 "Failed to find safe successor for dead branch");
503
504 // Collect removed successors to update the (Post)DominatorTrees.
505 SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;
506 bool First = true;
507 for (auto *Succ : successors(BB)) {
508 if (!First || Succ != PreferredSucc) {
509 Succ->removePredecessor(Pred: BB);
510 RemovedSuccessors.insert(Ptr: Succ);
511 } else
512 First = false;
513 }
514 makeUnconditional(BB, Target: PreferredSucc);
515
516 // Inform the dominators about the deleted CFG edges.
517 for (auto *Succ : RemovedSuccessors) {
518 // It might have happened that the same successor appeared multiple times
519 // and the CFG edge wasn't really removed.
520 if (Succ != PreferredSucc) {
521 LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"
522 << BB->getName() << " -> " << Succ->getName()
523 << "\n");
524 DeletedEdges.push_back(Elt: {DominatorTree::Delete, BB, Succ});
525 }
526 }
527
528 NumBranchesRemoved += 1;
529 Changed = true;
530 }
531
532 if (!DeletedEdges.empty())
533 DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager)
534 .applyUpdates(Updates: DeletedEdges);
535
536 return Changed;
537}
538
539// reverse top-sort order
540void AggressiveDeadCodeElimination::computeReversePostOrder() {
541 // This provides a post-order numbering of the reverse control flow graph
542 // Note that it is incomplete in the presence of infinite loops but we don't
543 // need numbers blocks which don't reach the end of the functions since
544 // all branches in those blocks are forced live.
545
546 // For each block without successors, extend the DFS from the block
547 // backward through the graph
548 SmallPtrSet<BasicBlock*, 16> Visited;
549 unsigned PostOrder = 0;
550 for (auto &BB : F) {
551 if (!succ_empty(BB: &BB))
552 continue;
553 for (BasicBlock *Block : inverse_post_order_ext(G: &BB,S&: Visited))
554 getBlockInfo(BB: Block).PostOrder = PostOrder++;
555 }
556}
557
558void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
559 BasicBlock *Target) {
560 Instruction *PredTerm = BB->getTerminator();
561 // Collect the live debug info scopes attached to this instruction.
562 if (const DILocation *DL = PredTerm->getDebugLoc())
563 collectLiveScopes(DL: *DL);
564
565 // Just mark live an existing unconditional branch
566 if (auto *BI = dyn_cast<UncondBrInst>(Val: PredTerm)) {
567 BI->setSuccessor(Target);
568 LiveInst.insert(Ptr: PredTerm);
569 return;
570 }
571 LLVM_DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n');
572 NumBranchesRemoved += 1;
573 IRBuilder<> Builder(PredTerm);
574 auto *NewTerm = Builder.CreateBr(Dest: Target);
575 LiveInst.insert(Ptr: NewTerm);
576 if (const DILocation *DL = PredTerm->getDebugLoc())
577 NewTerm->setDebugLoc(DL);
578 PredTerm->eraseFromParent();
579}
580
581//===----------------------------------------------------------------------===//
582//
583// Pass Manager integration code
584//
585//===----------------------------------------------------------------------===//
586PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
587 // ADCE does not need DominatorTree, but require DominatorTree here
588 // to update analysis if it is already available.
589 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(IR&: F);
590 auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(IR&: F);
591 const ScalarOptions &Opts =
592 F.getContext().getLibraryOptions().get<ScalarOptions>();
593 ADCEChanged Changed = AggressiveDeadCodeElimination(Opts, F, DT, PDT)
594 .performDeadCodeElimination();
595 if (!Changed.ChangedAnything)
596 return PreservedAnalyses::all();
597
598 PreservedAnalyses PA;
599 if (!Changed.ChangedControlFlow) {
600 PA.preserveSet<CFGAnalyses>();
601 if (!Changed.ChangedNonDebugInstr) {
602 // Only removing debug instructions does not affect MemorySSA.
603 //
604 // Therefore we preserve MemorySSA when only removing debug instructions
605 // since otherwise later passes may behave differently which then makes
606 // the presence of debug info affect code generation.
607 PA.preserve<MemorySSAAnalysis>();
608 }
609 }
610 PA.preserve<DominatorTreeAnalysis>();
611 PA.preserve<PostDominatorTreeAnalysis>();
612
613 return PA;
614}
615