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