Coverage Report

Created: 2019-07-24 05:18

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