1//===- BlockExtractor.cpp - Extracts blocks into their own functions ------===//
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 extracts the specified basic blocks from the module into their
10// own functions.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/IPO/BlockExtractor.h"
15#include "IPOOptions.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/IR/Instructions.h"
19#include "llvm/IR/Module.h"
20#include "llvm/IR/PassManager.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/MemoryBuffer.h"
23#include "llvm/Transforms/IPO.h"
24#include "llvm/Transforms/Utils/BasicBlockUtils.h"
25#include "llvm/Transforms/Utils/CodeExtractor.h"
26
27using namespace llvm;
28
29#define DEBUG_TYPE "block-extractor"
30
31STATISTIC(NumExtracted, "Number of basic blocks extracted");
32
33namespace {
34class BlockExtractor {
35public:
36 BlockExtractor(const IPOOptions &Opts, bool EraseFunctions)
37 : Opts(Opts), EraseFunctions(EraseFunctions) {}
38 bool runOnModule(Module &M);
39 void
40 init(const std::vector<std::vector<BasicBlock *>> &GroupsOfBlocksToExtract) {
41 GroupsOfBlocks = GroupsOfBlocksToExtract;
42 if (!Opts.extract_blocks_file.empty())
43 loadFile();
44 }
45
46private:
47 const IPOOptions &Opts;
48 std::vector<std::vector<BasicBlock *>> GroupsOfBlocks;
49 bool EraseFunctions;
50 /// Map a function name to groups of blocks.
51 SmallVector<std::pair<std::string, SmallVector<std::string, 4>>, 4>
52 BlocksByName;
53
54 void loadFile();
55 bool splitLandingPadPreds(Function &F);
56};
57
58} // end anonymous namespace
59
60/// Gets all of the blocks specified in the input file.
61void BlockExtractor::loadFile() {
62 auto ErrOrBuf = MemoryBuffer::getFile(Filename: Opts.extract_blocks_file);
63 if (ErrOrBuf.getError())
64 report_fatal_error(reason: "BlockExtractor couldn't load the file.");
65 // Read the file.
66 auto &Buf = *ErrOrBuf;
67 SmallVector<StringRef, 16> Lines;
68 Buf->getBuffer().split(A&: Lines, Separator: '\n', /*MaxSplit=*/-1,
69 /*KeepEmpty=*/false);
70 for (const auto &Line : Lines) {
71 SmallVector<StringRef, 4> LineSplit;
72 Line.split(A&: LineSplit, Separator: ' ', /*MaxSplit=*/-1,
73 /*KeepEmpty=*/false);
74 if (LineSplit.empty())
75 continue;
76 if (LineSplit.size()!=2)
77 reportFatalUsageError(
78 reason: "Invalid line format, expecting lines like: 'funcname bb1[;bb2..]'");
79 SmallVector<StringRef, 4> BBNames;
80 LineSplit[1].split(A&: BBNames, Separator: ';', /*MaxSplit=*/-1,
81 /*KeepEmpty=*/false);
82 if (BBNames.empty())
83 report_fatal_error(reason: "Missing bbs name");
84 BlocksByName.push_back(
85 Elt: {std::string(LineSplit[0]), {BBNames.begin(), BBNames.end()}});
86 }
87}
88
89/// Extracts the landing pads to make sure all of them have only one
90/// predecessor.
91bool BlockExtractor::splitLandingPadPreds(Function &F) {
92 bool Changed = false;
93 for (BasicBlock &BB : F) {
94 for (Instruction &I : BB) {
95 if (!isa<InvokeInst>(Val: &I))
96 continue;
97 InvokeInst *II = cast<InvokeInst>(Val: &I);
98 BasicBlock *Parent = II->getParent();
99 BasicBlock *LPad = II->getUnwindDest();
100
101 // Look through the landing pad's predecessors. If one of them ends in an
102 // 'invoke', then we want to split the landing pad.
103 bool Split = false;
104 for (auto *PredBB : predecessors(BB: LPad)) {
105 if (PredBB->isLandingPad() && PredBB != Parent &&
106 isa<InvokeInst>(Val: Parent->getTerminator())) {
107 Split = true;
108 break;
109 }
110 }
111
112 if (!Split)
113 continue;
114
115 SmallVector<BasicBlock *, 2> NewBBs;
116 SplitLandingPadPredecessors(OrigBB: LPad, Preds: Parent, Suffix: ".1", Suffix2: ".2", NewBBs);
117 Changed = true;
118 }
119 }
120 return Changed;
121}
122
123bool BlockExtractor::runOnModule(Module &M) {
124 bool Changed = false;
125
126 // Get all the functions.
127 SmallVector<Function *, 4> Functions;
128 for (Function &F : M) {
129 Changed |= splitLandingPadPreds(F);
130 Functions.push_back(Elt: &F);
131 }
132
133 // Get all the blocks specified in the input file.
134 unsigned NextGroupIdx = GroupsOfBlocks.size();
135 GroupsOfBlocks.resize(new_size: NextGroupIdx + BlocksByName.size());
136 for (const auto &BInfo : BlocksByName) {
137 Function *F = M.getFunction(Name: BInfo.first);
138 if (!F)
139 reportFatalUsageError(
140 reason: "Invalid function name specified in the input file");
141 for (const auto &BBInfo : BInfo.second) {
142 auto Res = llvm::find_if(
143 Range&: *F, P: [&](const BasicBlock &BB) { return BB.getName() == BBInfo; });
144 if (Res == F->end())
145 reportFatalUsageError(reason: "Invalid block name specified in the input file");
146 GroupsOfBlocks[NextGroupIdx].push_back(x: &*Res);
147 }
148 ++NextGroupIdx;
149 }
150
151 // Extract each group of basic blocks.
152 for (auto &BBs : GroupsOfBlocks) {
153 SmallVector<BasicBlock *, 32> BlocksToExtractVec;
154 for (BasicBlock *BB : BBs) {
155 // Check if the module contains BB.
156 if (BB->getParent()->getParent() != &M)
157 reportFatalUsageError(reason: "Invalid basic block");
158 LLVM_DEBUG(dbgs() << "BlockExtractor: Extracting "
159 << BB->getParent()->getName() << ":" << BB->getName()
160 << "\n");
161 BlocksToExtractVec.push_back(Elt: BB);
162 if (const InvokeInst *II = dyn_cast<InvokeInst>(Val: BB->getTerminator()))
163 BlocksToExtractVec.push_back(Elt: II->getUnwindDest());
164 ++NumExtracted;
165 Changed = true;
166 }
167 CodeExtractorAnalysisCache CEAC(*BBs[0]->getParent());
168 Function *F = CodeExtractor(BlocksToExtractVec).extractCodeRegion(CEAC);
169 if (F)
170 LLVM_DEBUG(dbgs() << "Extracted group '" << (*BBs.begin())->getName()
171 << "' in: " << F->getName() << '\n');
172 else
173 LLVM_DEBUG(dbgs() << "Failed to extract for group '"
174 << (*BBs.begin())->getName() << "'\n");
175 }
176
177 // Erase the functions.
178 if (EraseFunctions || Opts.extract_blocks_erase_funcs) {
179 for (Function *F : Functions) {
180 LLVM_DEBUG(dbgs() << "BlockExtractor: Trying to delete " << F->getName()
181 << "\n");
182 F->deleteBody();
183 }
184 // Set linkage as ExternalLinkage to avoid erasing unreachable functions.
185 for (Function &F : M)
186 F.setLinkage(GlobalValue::ExternalLinkage);
187 Changed = true;
188 }
189
190 return Changed;
191}
192
193BlockExtractorPass::BlockExtractorPass(
194 std::vector<std::vector<BasicBlock *>> &&GroupsOfBlocks,
195 bool EraseFunctions)
196 : GroupsOfBlocks(std::move(GroupsOfBlocks)),
197 EraseFunctions(EraseFunctions) {}
198
199PreservedAnalyses BlockExtractorPass::run(Module &M,
200 ModuleAnalysisManager &AM) {
201 BlockExtractor BE(getIPOOptions(M), EraseFunctions);
202 BE.init(GroupsOfBlocksToExtract: GroupsOfBlocks);
203 return BE.runOnModule(M) ? PreservedAnalyses::none()
204 : PreservedAnalyses::all();
205}
206