LLVM  10.0.0svn
BlockExtractor.cpp
Go to the documentation of this file.
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/ADT/STLExtras.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/IR/Instructions.h"
17 #include "llvm/IR/Module.h"
18 #include "llvm/Pass.h"
20 #include "llvm/Support/Debug.h"
22 #include "llvm/Transforms/IPO.h"
25 
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "block-extractor"
29 
30 STATISTIC(NumExtracted, "Number of basic blocks extracted");
31 
33  "extract-blocks-file", cl::value_desc("filename"),
34  cl::desc("A file containing list of basic blocks to extract"), cl::Hidden);
35 
36 cl::opt<bool> BlockExtractorEraseFuncs("extract-blocks-erase-funcs",
37  cl::desc("Erase the existing functions"),
38  cl::Hidden);
39 namespace {
40 class BlockExtractor : public ModulePass {
42  bool EraseFunctions;
43  /// Map a function name to groups of blocks.
45  BlocksByName;
46 
48  &GroupsOfBlocksToExtract) {
49  for (const SmallVectorImpl<BasicBlock *> &GroupOfBlocks :
50  GroupsOfBlocksToExtract) {
52  NewGroup.append(GroupOfBlocks.begin(), GroupOfBlocks.end());
53  GroupsOfBlocks.emplace_back(NewGroup);
54  }
55  if (!BlockExtractorFile.empty())
56  loadFile();
57  }
58 
59 public:
60  static char ID;
61  BlockExtractor(const SmallVectorImpl<BasicBlock *> &BlocksToExtract,
62  bool EraseFunctions)
63  : ModulePass(ID), EraseFunctions(EraseFunctions) {
64  // We want one group per element of the input list.
65  SmallVector<SmallVector<BasicBlock *, 16>, 4> MassagedGroupsOfBlocks;
66  for (BasicBlock *BB : BlocksToExtract) {
68  NewGroup.push_back(BB);
69  MassagedGroupsOfBlocks.push_back(NewGroup);
70  }
71  init(MassagedGroupsOfBlocks);
72  }
73 
75  &GroupsOfBlocksToExtract,
76  bool EraseFunctions)
77  : ModulePass(ID), EraseFunctions(EraseFunctions) {
78  init(GroupsOfBlocksToExtract);
79  }
80 
81  BlockExtractor() : BlockExtractor(SmallVector<BasicBlock *, 0>(), false) {}
82  bool runOnModule(Module &M) override;
83 
84 private:
85  void loadFile();
86  void splitLandingPadPreds(Function &F);
87 };
88 } // end anonymous namespace
89 
90 char BlockExtractor::ID = 0;
91 INITIALIZE_PASS(BlockExtractor, "extract-blocks",
92  "Extract basic blocks from module", false, false)
93 
94 ModulePass *llvm::createBlockExtractorPass() { return new BlockExtractor(); }
96  const SmallVectorImpl<BasicBlock *> &BlocksToExtract, bool EraseFunctions) {
97  return new BlockExtractor(BlocksToExtract, EraseFunctions);
98 }
101  &GroupsOfBlocksToExtract,
102  bool EraseFunctions) {
103  return new BlockExtractor(GroupsOfBlocksToExtract, EraseFunctions);
104 }
105 
106 /// Gets all of the blocks specified in the input file.
108  auto ErrOrBuf = MemoryBuffer::getFile(BlockExtractorFile);
109  if (ErrOrBuf.getError())
110  report_fatal_error("BlockExtractor couldn't load the file.");
111  // Read the file.
112  auto &Buf = *ErrOrBuf;
114  Buf->getBuffer().split(Lines, '\n', /*MaxSplit=*/-1,
115  /*KeepEmpty=*/false);
116  for (const auto &Line : Lines) {
117  SmallVector<StringRef, 4> LineSplit;
118  Line.split(LineSplit, ' ', /*MaxSplit=*/-1,
119  /*KeepEmpty=*/false);
120  if (LineSplit.empty())
121  continue;
123  LineSplit[1].split(BBNames, ';', /*MaxSplit=*/-1,
124  /*KeepEmpty=*/false);
125  if (BBNames.empty())
126  report_fatal_error("Missing bbs name");
127  BlocksByName.push_back({LineSplit[0], {BBNames.begin(), BBNames.end()}});
128  }
129 }
130 
131 /// Extracts the landing pads to make sure all of them have only one
132 /// predecessor.
133 void BlockExtractor::splitLandingPadPreds(Function &F) {
134  for (BasicBlock &BB : F) {
135  for (Instruction &I : BB) {
136  if (!isa<InvokeInst>(&I))
137  continue;
138  InvokeInst *II = cast<InvokeInst>(&I);
139  BasicBlock *Parent = II->getParent();
140  BasicBlock *LPad = II->getUnwindDest();
141 
142  // Look through the landing pad's predecessors. If one of them ends in an
143  // 'invoke', then we want to split the landing pad.
144  bool Split = false;
145  for (auto PredBB : predecessors(LPad)) {
146  if (PredBB->isLandingPad() && PredBB != Parent &&
147  isa<InvokeInst>(Parent->getTerminator())) {
148  Split = true;
149  break;
150  }
151  }
152 
153  if (!Split)
154  continue;
155 
157  SplitLandingPadPredecessors(LPad, Parent, ".1", ".2", NewBBs);
158  }
159  }
160 }
161 
162 bool BlockExtractor::runOnModule(Module &M) {
163 
164  bool Changed = false;
165 
166  // Get all the functions.
167  SmallVector<Function *, 4> Functions;
168  for (Function &F : M) {
169  splitLandingPadPreds(F);
170  Functions.push_back(&F);
171  }
172 
173  // Get all the blocks specified in the input file.
174  unsigned NextGroupIdx = GroupsOfBlocks.size();
175  GroupsOfBlocks.resize(NextGroupIdx + BlocksByName.size());
176  for (const auto &BInfo : BlocksByName) {
177  Function *F = M.getFunction(BInfo.first);
178  if (!F)
179  report_fatal_error("Invalid function name specified in the input file");
180  for (const auto &BBInfo : BInfo.second) {
181  auto Res = llvm::find_if(*F, [&](const BasicBlock &BB) {
182  return BB.getName().equals(BBInfo);
183  });
184  if (Res == F->end())
185  report_fatal_error("Invalid block name specified in the input file");
186  GroupsOfBlocks[NextGroupIdx].push_back(&*Res);
187  }
188  ++NextGroupIdx;
189  }
190 
191  // Extract each group of basic blocks.
192  for (auto &BBs : GroupsOfBlocks) {
193  SmallVector<BasicBlock *, 32> BlocksToExtractVec;
194  for (BasicBlock *BB : BBs) {
195  // Check if the module contains BB.
196  if (BB->getParent()->getParent() != &M)
197  report_fatal_error("Invalid basic block");
198  LLVM_DEBUG(dbgs() << "BlockExtractor: Extracting "
199  << BB->getParent()->getName() << ":" << BB->getName()
200  << "\n");
201  BlocksToExtractVec.push_back(BB);
202  if (const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
203  BlocksToExtractVec.push_back(II->getUnwindDest());
204  ++NumExtracted;
205  Changed = true;
206  }
207  Function *F = CodeExtractor(BlocksToExtractVec).extractCodeRegion();
208  if (F)
209  LLVM_DEBUG(dbgs() << "Extracted group '" << (*BBs.begin())->getName()
210  << "' in: " << F->getName() << '\n');
211  else
212  LLVM_DEBUG(dbgs() << "Failed to extract for group '"
213  << (*BBs.begin())->getName() << "'\n");
214  }
215 
216  // Erase the functions.
217  if (EraseFunctions || BlockExtractorEraseFuncs) {
218  for (Function *F : Functions) {
219  LLVM_DEBUG(dbgs() << "BlockExtractor: Trying to delete " << F->getName()
220  << "\n");
221  F->deleteBody();
222  }
223  // Set linkage as ExternalLinkage to avoid erasing unreachable functions.
224  for (Function &F : M)
226  Changed = true;
227  }
228 
229  return Changed;
230 }
const Function & getFunction() const
Definition: Function.h:133
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:52
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
iterator end()
Definition: Function.h:682
Function * extractCodeRegion()
Perform the extraction, returning the new function.
Externally visible function.
Definition: GlobalValue.h:48
STATISTIC(NumFunctions, "Total number of functions")
cl::opt< bool > BlockExtractorEraseFuncs("extract-blocks-erase-funcs", cl::desc("Erase the existing functions"), cl::Hidden)
F(f)
static std::unique_ptr< Module > loadFile(const std::string &FileName, LLVMContext &Context)
ModulePass * createBlockExtractorPass()
createBlockExtractorPass - This pass extracts all the specified blocks from the functions in the modu...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
static StringRef getName(Value *V)
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock *> Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock *> &NewBBs, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...
INITIALIZE_PASS(BlockExtractor, "extract-blocks", "Extract basic blocks from module", false, false) ModulePass *llvm
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
void deleteBody()
deleteBody - This method deletes the body of the function, and converts the linkage to external...
Definition: Function.h:633
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1205
size_t size() const
Definition: SmallVector.h:52
static cl::opt< std::string > BlockExtractorFile("extract-blocks-file", cl::value_desc("filename"), cl::desc("A file containing list of basic blocks to extract"), cl::Hidden)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:454
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:387
LLVM_NODISCARD bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:160
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
static ErrorOr< std::unique_ptr< MemoryBuffer > > getFile(const Twine &Filename, int64_t FileSize=-1, bool RequiresNullTerminator=true, bool IsVolatile=false)
Open the specified file as a MemoryBuffer, returning a new MemoryBuffer if successful, otherwise returning null.
BasicBlock * getUnwindDest() const
Invoke instruction.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const BasicBlock * getParent() const
Definition: Instruction.h:66
void resize(size_type N)
Definition: SmallVector.h:344