1//===-- GCEmptyBasicBlocks.cpp ----------------------------------*- C++ -*-===//
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/// \file
10/// This file contains the implementation of empty blocks garbage collection
11/// pass.
12///
13//===----------------------------------------------------------------------===//
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/ADT/Statistic.h"
16#include "llvm/CodeGen/MachineBasicBlock.h"
17#include "llvm/CodeGen/MachineFunction.h"
18#include "llvm/CodeGen/MachineFunctionPass.h"
19#include "llvm/CodeGen/MachineJumpTableInfo.h"
20#include "llvm/CodeGen/Passes.h"
21#include "llvm/CodeGen/TargetInstrInfo.h"
22#include "llvm/InitializePasses.h"
23
24using namespace llvm;
25
26#define DEBUG_TYPE "gc-empty-basic-blocks"
27
28STATISTIC(NumEmptyBlocksRemoved, "Number of empty blocks removed");
29
30class GCEmptyBasicBlocks : public MachineFunctionPass {
31public:
32 static char ID;
33
34 GCEmptyBasicBlocks() : MachineFunctionPass(ID) {
35 initializeGCEmptyBasicBlocksPass(*PassRegistry::getPassRegistry());
36 }
37
38 StringRef getPassName() const override {
39 return "Remove Empty Basic Blocks.";
40 }
41
42 bool runOnMachineFunction(MachineFunction &MF) override;
43};
44
45bool GCEmptyBasicBlocks::runOnMachineFunction(MachineFunction &MF) {
46 if (MF.size() < 2)
47 return false;
48 MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
49 int NumRemoved = 0;
50
51 // Iterate over all blocks except the last one. We can't remove the last block
52 // since it has no fallthrough block to rewire its predecessors to.
53 for (MachineFunction::iterator MBB = MF.begin(),
54 LastMBB = MachineFunction::iterator(MF.back()),
55 NextMBB;
56 MBB != LastMBB; MBB = NextMBB) {
57 NextMBB = std::next(x: MBB);
58 // TODO If a block is an eh pad, or it has address taken, we don't remove
59 // it. Removing such blocks is possible, but it probably requires a more
60 // complex logic.
61 if (MBB->isEHPad() || MBB->hasAddressTaken())
62 continue;
63 // Skip blocks with real code.
64 bool HasAnyRealCode = llvm::any_of(Range&: *MBB, P: [](const MachineInstr &MI) {
65 return !MI.isPosition() && !MI.isImplicitDef() && !MI.isKill() &&
66 !MI.isDebugInstr();
67 });
68 if (HasAnyRealCode)
69 continue;
70
71 LLVM_DEBUG(dbgs() << "Removing basic block " << MBB->getName()
72 << " in function " << MF.getName() << ":\n"
73 << *MBB << "\n");
74 SmallVector<MachineBasicBlock *, 8> Preds(MBB->predecessors());
75 // Rewire the predecessors of this block to use the next block.
76 for (auto &Pred : Preds)
77 Pred->ReplaceUsesOfBlockWith(Old: &*MBB, New: &*NextMBB);
78 // Update the jump tables.
79 if (JTI)
80 JTI->ReplaceMBBInJumpTables(Old: &*MBB, New: &*NextMBB);
81 // Remove this block from predecessors of all its successors.
82 while (!MBB->succ_empty())
83 MBB->removeSuccessor(I: MBB->succ_end() - 1);
84 // Finally, remove the block from the function.
85 MBB->eraseFromParent();
86 ++NumRemoved;
87 }
88 NumEmptyBlocksRemoved += NumRemoved;
89 return NumRemoved != 0;
90}
91
92char GCEmptyBasicBlocks::ID = 0;
93INITIALIZE_PASS(GCEmptyBasicBlocks, "gc-empty-basic-blocks",
94 "Removes empty basic blocks and redirects their uses to their "
95 "fallthrough blocks.",
96 false, false)
97
98MachineFunctionPass *llvm::createGCEmptyBasicBlocksPass() {
99 return new GCEmptyBasicBlocks();
100}
101