Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/UnreachableBlockElim.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===//
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 pass is an extremely simple version of the SimplifyCFG pass.  Its sole
10
// job is to delete LLVM basic blocks that are not reachable from the entry
11
// node.  To do this, it performs a simple depth first traversal of the CFG,
12
// then deletes any unvisited nodes.
13
//
14
// Note that this pass is really a hack.  In particular, the instruction
15
// selectors for various targets should just not generate code for unreachable
16
// blocks.  Until LLVM has a more systematic way of defining instruction
17
// selectors, however, we cannot really expect them to handle additional
18
// complexity.
19
//
20
//===----------------------------------------------------------------------===//
21
22
#include "llvm/CodeGen/UnreachableBlockElim.h"
23
#include "llvm/ADT/DepthFirstIterator.h"
24
#include "llvm/ADT/SmallPtrSet.h"
25
#include "llvm/CodeGen/MachineDominators.h"
26
#include "llvm/CodeGen/MachineFunctionPass.h"
27
#include "llvm/CodeGen/MachineInstrBuilder.h"
28
#include "llvm/CodeGen/MachineLoopInfo.h"
29
#include "llvm/CodeGen/MachineModuleInfo.h"
30
#include "llvm/CodeGen/MachineRegisterInfo.h"
31
#include "llvm/CodeGen/Passes.h"
32
#include "llvm/CodeGen/TargetInstrInfo.h"
33
#include "llvm/IR/CFG.h"
34
#include "llvm/IR/Constant.h"
35
#include "llvm/IR/Dominators.h"
36
#include "llvm/IR/Function.h"
37
#include "llvm/IR/Instructions.h"
38
#include "llvm/IR/Type.h"
39
#include "llvm/Pass.h"
40
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
41
using namespace llvm;
42
43
namespace {
44
class UnreachableBlockElimLegacyPass : public FunctionPass {
45
537k
  bool runOnFunction(Function &F) override {
46
537k
    return llvm::EliminateUnreachableBlocks(F);
47
537k
  }
48
49
public:
50
  static char ID; // Pass identification, replacement for typeid
51
40.2k
  UnreachableBlockElimLegacyPass() : FunctionPass(ID) {
52
40.2k
    initializeUnreachableBlockElimLegacyPassPass(
53
40.2k
        *PassRegistry::getPassRegistry());
54
40.2k
  }
55
56
40.0k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
57
40.0k
    AU.addPreserved<DominatorTreeWrapperPass>();
58
40.0k
  }
59
};
60
}
61
char UnreachableBlockElimLegacyPass::ID = 0;
62
INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim",
63
                "Remove unreachable blocks from the CFG", false, false)
64
65
40.2k
FunctionPass *llvm::createUnreachableBlockEliminationPass() {
66
40.2k
  return new UnreachableBlockElimLegacyPass();
67
40.2k
}
68
69
PreservedAnalyses UnreachableBlockElimPass::run(Function &F,
70
1
                                                FunctionAnalysisManager &AM) {
71
1
  bool Changed = llvm::EliminateUnreachableBlocks(F);
72
1
  if (!Changed)
73
0
    return PreservedAnalyses::all();
74
1
  PreservedAnalyses PA;
75
1
  PA.preserve<DominatorTreeAnalysis>();
76
1
  return PA;
77
1
}
78
79
namespace {
80
  class UnreachableMachineBlockElim : public MachineFunctionPass {
81
    bool runOnMachineFunction(MachineFunction &F) override;
82
    void getAnalysisUsage(AnalysisUsage &AU) const override;
83
    MachineModuleInfo *MMI;
84
  public:
85
    static char ID; // Pass identification, replacement for typeid
86
35.9k
    UnreachableMachineBlockElim() : MachineFunctionPass(ID) {}
87
  };
88
}
89
char UnreachableMachineBlockElim::ID = 0;
90
91
INITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination",
92
  "Remove unreachable machine basic blocks", false, false)
93
94
char &llvm::UnreachableMachineBlockElimID = UnreachableMachineBlockElim::ID;
95
96
35.9k
void UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const {
97
35.9k
  AU.addPreserved<MachineLoopInfo>();
98
35.9k
  AU.addPreserved<MachineDominatorTree>();
99
35.9k
  MachineFunctionPass::getAnalysisUsage(AU);
100
35.9k
}
101
102
498k
bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) {
103
498k
  df_iterator_default_set<MachineBasicBlock*> Reachable;
104
498k
  bool ModifiedPHI = false;
105
498k
106
498k
  MMI = getAnalysisIfAvailable<MachineModuleInfo>();
107
498k
  MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>();
108
498k
  MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
109
498k
110
498k
  // Mark all reachable blocks.
111
498k
  for (MachineBasicBlock *BB : depth_first_ext(&F, Reachable))
112
2.70M
    (void)BB/* Mark all reachable blocks */;
113
498k
114
498k
  // Loop over all dead blocks, remembering them and deleting all instructions
115
498k
  // in them.
116
498k
  std::vector<MachineBasicBlock*> DeadBlocks;
117
3.19M
  for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; 
++I2.70M
) {
118
2.70M
    MachineBasicBlock *BB = &*I;
119
2.70M
120
2.70M
    // Test for deadness.
121
2.70M
    if (!Reachable.count(BB)) {
122
212
      DeadBlocks.push_back(BB);
123
212
124
212
      // Update dominator and loop info.
125
212
      if (MLI) 
MLI->removeBlock(BB)24
;
126
212
      if (MDT && 
MDT->getNode(BB)28
)
MDT->eraseNode(BB)0
;
127
212
128
215
      while (BB->succ_begin() != BB->succ_end()) {
129
3
        MachineBasicBlock* succ = *BB->succ_begin();
130
3
131
3
        MachineBasicBlock::iterator start = succ->begin();
132
5
        while (start != succ->end() && start->isPHI()) {
133
6
          for (unsigned i = start->getNumOperands() - 1; i >= 2; 
i-=24
)
134
4
            if (start->getOperand(i).isMBB() &&
135
4
                start->getOperand(i).getMBB() == BB) {
136
2
              start->RemoveOperand(i);
137
2
              start->RemoveOperand(i-1);
138
2
            }
139
2
140
2
          start++;
141
2
        }
142
3
143
3
        BB->removeSuccessor(BB->succ_begin());
144
3
      }
145
212
    }
146
2.70M
  }
147
498k
148
498k
  // Actually remove the blocks now.
149
498k
  for (unsigned i = 0, e = DeadBlocks.size(); i != e; 
++i212
)
150
212
    DeadBlocks[i]->eraseFromParent();
151
498k
152
498k
  // Cleanup PHI nodes.
153
3.19M
  for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; 
++I2.70M
) {
154
2.70M
    MachineBasicBlock *BB = &*I;
155
2.70M
    // Prune unneeded PHI entries.
156
2.70M
    SmallPtrSet<MachineBasicBlock*, 8> preds(BB->pred_begin(),
157
2.70M
                                             BB->pred_end());
158
2.70M
    MachineBasicBlock::iterator phi = BB->begin();
159
3.33M
    while (phi != BB->end() && 
phi->isPHI()3.28M
) {
160
2.16M
      for (unsigned i = phi->getNumOperands() - 1; i >= 2; 
i-=21.53M
)
161
1.53M
        if (!preds.count(phi->getOperand(i).getMBB())) {
162
0
          phi->RemoveOperand(i);
163
0
          phi->RemoveOperand(i-1);
164
0
          ModifiedPHI = true;
165
0
        }
166
635k
167
635k
      if (phi->getNumOperands() == 3) {
168
1.19k
        const MachineOperand &Input = phi->getOperand(1);
169
1.19k
        const MachineOperand &Output = phi->getOperand(0);
170
1.19k
        unsigned InputReg = Input.getReg();
171
1.19k
        unsigned OutputReg = Output.getReg();
172
1.19k
        assert(Output.getSubReg() == 0 && "Cannot have output subregister");
173
1.19k
        ModifiedPHI = true;
174
1.19k
175
1.19k
        if (InputReg != OutputReg) {
176
1.19k
          MachineRegisterInfo &MRI = F.getRegInfo();
177
1.19k
          unsigned InputSub = Input.getSubReg();
178
1.19k
          if (InputSub == 0 &&
179
1.19k
              
MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg))1.19k
&&
180
1.19k
              
!Input.isUndef()1.19k
) {
181
1.19k
            MRI.replaceRegWith(OutputReg, InputReg);
182
1.19k
          } else {
183
2
            // The input register to the PHI has a subregister or it can't be
184
2
            // constrained to the proper register class or it is undef:
185
2
            // insert a COPY instead of simply replacing the output
186
2
            // with the input.
187
2
            const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo();
188
2
            BuildMI(*BB, BB->getFirstNonPHI(), phi->getDebugLoc(),
189
2
                    TII->get(TargetOpcode::COPY), OutputReg)
190
2
                .addReg(InputReg, getRegState(Input), InputSub);
191
2
          }
192
1.19k
          phi++->eraseFromParent();
193
1.19k
        }
194
1.19k
        continue;
195
1.19k
      }
196
634k
197
634k
      ++phi;
198
634k
    }
199
2.70M
  }
200
498k
201
498k
  F.RenumberBlocks();
202
498k
203
498k
  return (!DeadBlocks.empty() || 
ModifiedPHI498k
);
204
498k
}