LLVM 19.0.0git
ADCE.cpp
Go to the documentation of this file.
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
17#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/MapVector.h"
22#include "llvm/ADT/SetVector.h"
25#include "llvm/ADT/Statistic.h"
31#include "llvm/IR/BasicBlock.h"
32#include "llvm/IR/CFG.h"
33#include "llvm/IR/DebugInfo.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"
40#include "llvm/IR/Instruction.h"
43#include "llvm/IR/PassManager.h"
44#include "llvm/IR/Use.h"
45#include "llvm/IR/Value.h"
49#include "llvm/Support/Debug.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(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(false),
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;
127
128 /// Mapping of blocks to associated information, an element in BlockInfoVec.
129 /// Use MapVector to get deterministic iteration order.
131 bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; }
132
133 /// Mapping of instructions to associated information.
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.
140
141 /// Debug info scopes around a live instruction.
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.
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(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,
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
216 auto *BR = dyn_cast<BranchInst>(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(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(Info.Terminator);
236 }
237
238 // Initialize instruction map and set pointers to block info.
239 InstInfo.reserve(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);
253
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(std::make_pair(BB, 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(BB);
277 return Iter != end() && Iter->second;
278 }
279 } State;
280
281 State.reserve(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(&F.getEntryBlock(), State)) {
286 Instruction *Term = BB->getTerminator();
287 if (isLive(Term))
288 continue;
289
290 for (auto *Succ : successors(BB))
291 if (State.onStack(Succ)) {
292 // back edge....
293 markLive(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 *>(PDT.getRootNode())) {
304 auto *BB = PDTChild->getBlock();
305 auto &Info = BlockInfo[BB];
306 // Real function return
307 if (isa<ReturnInst>(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(PDTChild))
315 markLive(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(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(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>(I) || isa<SwitchInst>(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>(&I))
352 if (Function *Callee = CI->getCalledFunction())
353 if (Callee->getName().equals(getInstrProfValueProfFuncName()))
354 if (isa<Constant>(CI->getArgOperand(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>(OI))
370 markLive(Inst);
371
372 if (auto *PN = dyn_cast<PHINode>(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(I);
391
392 // Collect the live debug info scopes attached to this instruction.
393 if (const DILocation *DL = I->getDebugLoc())
394 collectLiveScopes(*DL);
395
396 // Mark the containing block live
397 auto &BBInfo = *Info.Block;
398 if (BBInfo.Terminator == I) {
399 BlocksWithDeadTerminators.remove(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(I->getParent()))
404 markLive(BB);
405 }
406 markLive(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(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(BBInfo.Terminator);
423}
424
425void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) {
426 if (!AliveScopes.insert(&LS).second)
427 return;
428
429 if (isa<DISubprogram>(LS))
430 return;
431
432 // Tail-recurse through the scope chain.
433 collectLiveScopes(cast<DILocalScope>(*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(&DL).second)
440 return;
441
442 // Collect live scopes from the scope chain.
443 collectLiveScopes(*DL.getScope());
444
445 // Tail-recurse through the inlined-at chain.
446 if (const DILocation *IA = DL.getInlinedAt())
447 collectLiveScopes(*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(Info.BB)) {
461 auto &Info = BlockInfo[PredBB];
462 if (!Info.CFLive) {
463 Info.CFLive = true;
464 NewLiveBlocks.insert(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
489 BlocksWithDeadTerminators.begin(),
490 BlocksWithDeadTerminators.end()
491 };
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(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.
547 // With "RemoveDIs" debug-info stored in DPValue objects, debug-info
548 // attached to this instruction, and drop any for scopes that aren't alive,
549 // like the rest of this loop does. Extending support to assignment tracking
550 // is future work.
551 for (DbgRecord &DR : make_early_inc_range(I.getDbgRecordRange())) {
552 // Avoid removing a DPV that is linked to instructions because it holds
553 // information about an existing store.
554 if (DPValue *DPV = dyn_cast<DPValue>(&DR); DPV && DPV->isDbgAssign())
555 if (!at::getAssignmentInsts(DPV).empty())
556 continue;
557 if (AliveScopes.count(DR.getDebugLoc()->getScope()))
558 continue;
559 I.dropOneDbgRecord(&DR);
560 }
561
562 // Check if the instruction is alive.
563 if (isLive(&I))
564 continue;
565
566 if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
567 // Avoid removing a dbg.assign that is linked to instructions because it
568 // holds information about an existing store.
569 if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(DII))
570 if (!at::getAssignmentInsts(DAI).empty())
571 continue;
572 // Check if the scope of this variable location is alive.
573 if (AliveScopes.count(DII->getDebugLoc()->getScope()))
574 continue;
575
576 // Fallthrough and drop the intrinsic.
577 } else {
578 Changed.ChangedNonDebugInstr = true;
579 }
580
581 // Prepare to delete.
582 Worklist.push_back(&I);
584 }
585
586 for (Instruction *&I : Worklist)
587 I->dropAllReferences();
588
589 for (Instruction *&I : Worklist) {
590 ++NumRemoved;
591 I->eraseFromParent();
592 }
593
594 Changed.ChangedAnything = Changed.ChangedControlFlow || !Worklist.empty();
595
596 return Changed;
597}
598
599// A dead region is the set of dead blocks with a common live post-dominator.
600bool AggressiveDeadCodeElimination::updateDeadRegions() {
601 LLVM_DEBUG({
602 dbgs() << "final dead terminator blocks: " << '\n';
603 for (auto *BB : BlocksWithDeadTerminators)
604 dbgs() << '\t' << BB->getName()
605 << (BlockInfo[BB].Live ? " LIVE\n" : "\n");
606 });
607
608 // Don't compute the post ordering unless we needed it.
609 bool HavePostOrder = false;
610 bool Changed = false;
612
613 for (auto *BB : BlocksWithDeadTerminators) {
614 auto &Info = BlockInfo[BB];
615 if (Info.UnconditionalBranch) {
616 InstInfo[Info.Terminator].Live = true;
617 continue;
618 }
619
620 if (!HavePostOrder) {
621 computeReversePostOrder();
622 HavePostOrder = true;
623 }
624
625 // Add an unconditional branch to the successor closest to the
626 // end of the function which insures a path to the exit for each
627 // live edge.
628 BlockInfoType *PreferredSucc = nullptr;
629 for (auto *Succ : successors(BB)) {
630 auto *Info = &BlockInfo[Succ];
631 if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder)
632 PreferredSucc = Info;
633 }
634 assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
635 "Failed to find safe successor for dead branch");
636
637 // Collect removed successors to update the (Post)DominatorTrees.
638 SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;
639 bool First = true;
640 for (auto *Succ : successors(BB)) {
641 if (!First || Succ != PreferredSucc->BB) {
642 Succ->removePredecessor(BB);
643 RemovedSuccessors.insert(Succ);
644 } else
645 First = false;
646 }
647 makeUnconditional(BB, PreferredSucc->BB);
648
649 // Inform the dominators about the deleted CFG edges.
650 for (auto *Succ : RemovedSuccessors) {
651 // It might have happened that the same successor appeared multiple times
652 // and the CFG edge wasn't really removed.
653 if (Succ != PreferredSucc->BB) {
654 LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"
655 << BB->getName() << " -> " << Succ->getName()
656 << "\n");
657 DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});
658 }
659 }
660
661 NumBranchesRemoved += 1;
662 Changed = true;
663 }
664
665 if (!DeletedEdges.empty())
666 DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager)
667 .applyUpdates(DeletedEdges);
668
669 return Changed;
670}
671
672// reverse top-sort order
673void AggressiveDeadCodeElimination::computeReversePostOrder() {
674 // This provides a post-order numbering of the reverse control flow graph
675 // Note that it is incomplete in the presence of infinite loops but we don't
676 // need numbers blocks which don't reach the end of the functions since
677 // all branches in those blocks are forced live.
678
679 // For each block without successors, extend the DFS from the block
680 // backward through the graph
682 unsigned PostOrder = 0;
683 for (auto &BB : F) {
684 if (!succ_empty(&BB))
685 continue;
686 for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited))
687 BlockInfo[Block].PostOrder = PostOrder++;
688 }
689}
690
691void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
693 Instruction *PredTerm = BB->getTerminator();
694 // Collect the live debug info scopes attached to this instruction.
695 if (const DILocation *DL = PredTerm->getDebugLoc())
696 collectLiveScopes(*DL);
697
698 // Just mark live an existing unconditional branch
699 if (isUnconditionalBranch(PredTerm)) {
700 PredTerm->setSuccessor(0, Target);
701 InstInfo[PredTerm].Live = true;
702 return;
703 }
704 LLVM_DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n');
705 NumBranchesRemoved += 1;
706 IRBuilder<> Builder(PredTerm);
707 auto *NewTerm = Builder.CreateBr(Target);
708 InstInfo[NewTerm].Live = true;
709 if (const DILocation *DL = PredTerm->getDebugLoc())
710 NewTerm->setDebugLoc(DL);
711
712 InstInfo.erase(PredTerm);
713 PredTerm->eraseFromParent();
714}
715
716//===----------------------------------------------------------------------===//
717//
718// Pass Manager integration code
719//
720//===----------------------------------------------------------------------===//
722 // ADCE does not need DominatorTree, but require DominatorTree here
723 // to update analysis if it is already available.
726 ADCEChanged Changed =
727 AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination();
728 if (!Changed.ChangedAnything)
729 return PreservedAnalyses::all();
730
732 if (!Changed.ChangedControlFlow) {
734 if (!Changed.ChangedNonDebugInstr) {
735 // Only removing debug instructions does not affect MemorySSA.
736 //
737 // Therefore we preserve MemorySSA when only removing debug instructions
738 // since otherwise later passes may behave differently which then makes
739 // the presence of debug info affect code generation.
741 }
742 }
745
746 return PA;
747}
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static bool isUnconditionalBranch(Instruction *Term)
Definition: ADCE.cpp:215
static cl::opt< bool > RemoveLoops("adce-remove-loops", cl::init(false), cl::Hidden)
static cl::opt< bool > RemoveControlFlowFlag("adce-remove-control-flow", cl::init(true), cl::Hidden)
Expand Atomic instructions
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static bool isAlwaysLive(Instruction *I)
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
This is the interface for a simple mod/ref and alias analysis over globals.
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file implements a map that provides insertion order iteration.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
This defines the Use class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:519
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:220
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
This class represents a function call, abstracting a target machine's calling convention.
A scope for locals.
Debug location.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
Base class for non-instruction debug metadata records that have positions within IR.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2649
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:453
const BasicBlock * getParent() const
Definition: Instruction.h:151
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:923
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
iterator begin() const
Definition: SmallPtrSet.h:380
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Target - Wrapper for Target specific information.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
LLVM Value Representation.
Definition: Value.h:74
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:5203
AssignmentInstRange getAssignmentInsts(DIAssignID *ID)
Return a range of instructions (typically just one) that have ID as an attachment.
Definition: DebugInfo.cpp:1775
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1751
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
iterator_range< ipo_ext_iterator< T, SetType > > inverse_post_order_ext(const T &G, SetType &S)
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition: Utils.cpp:1581
auto successors(const MachineBasicBlock *BB)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:665
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
auto predecessors(const MachineBasicBlock *BB)
StringRef getInstrProfValueProfFuncName()
Return the name profile runtime entry point to do value profiling for a given site.
Definition: InstrProf.h:79
iterator_range< df_iterator< T > > depth_first(const T &G)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Definition: ADCE.cpp:721