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;
122  if (LineSplit.size()!=2)
123  report_fatal_error("Invalid line format, expecting lines like: 'funcname bb1[;bb2..]'");
125  LineSplit[1].split(BBNames, ';', /*MaxSplit=*/-1,
126  /*KeepEmpty=*/false);
127  if (BBNames.empty())
128  report_fatal_error("Missing bbs name");
129  BlocksByName.push_back({LineSplit[0], {BBNames.begin(), BBNames.end()}});
130  }
131 }
132 
133 /// Extracts the landing pads to make sure all of them have only one
134 /// predecessor.
135 void BlockExtractor::splitLandingPadPreds(Function &F) {
136  for (BasicBlock &BB : F) {
137  for (Instruction &I : BB) {
138  if (!isa<InvokeInst>(&I))
139  continue;
140  InvokeInst *II = cast<InvokeInst>(&I);
141  BasicBlock *Parent = II->getParent();
142  BasicBlock *LPad = II->getUnwindDest();
143 
144  // Look through the landing pad's predecessors. If one of them ends in an
145  // 'invoke', then we want to split the landing pad.
146  bool Split = false;
147  for (auto PredBB : predecessors(LPad)) {
148  if (PredBB->isLandingPad() && PredBB != Parent &&
149  isa<InvokeInst>(Parent->getTerminator())) {
150  Split = true;
151  break;
152  }
153  }
154 
155  if (!Split)
156  continue;
157 
159  SplitLandingPadPredecessors(LPad, Parent, ".1", ".2", NewBBs);
160  }
161  }
162 }
163 
164 bool BlockExtractor::runOnModule(Module &M) {
165 
166  bool Changed = false;
167 
168  // Get all the functions.
169  SmallVector<Function *, 4> Functions;
170  for (Function &F : M) {
171  splitLandingPadPreds(F);
172  Functions.push_back(&F);
173  }
174 
175  // Get all the blocks specified in the input file.
176  unsigned NextGroupIdx = GroupsOfBlocks.size();
177  GroupsOfBlocks.resize(NextGroupIdx + BlocksByName.size());
178  for (const auto &BInfo : BlocksByName) {
179  Function *F = M.getFunction(BInfo.first);
180  if (!F)
181  report_fatal_error("Invalid function name specified in the input file");
182  for (const auto &BBInfo : BInfo.second) {
183  auto Res = llvm::find_if(*F, [&](const BasicBlock &BB) {
184  return BB.getName().equals(BBInfo);
185  });
186  if (Res == F->end())
187  report_fatal_error("Invalid block name specified in the input file");
188  GroupsOfBlocks[NextGroupIdx].push_back(&*Res);
189  }
190  ++NextGroupIdx;
191  }
192 
193  // Extract each group of basic blocks.
194  for (auto &BBs : GroupsOfBlocks) {
195  SmallVector<BasicBlock *, 32> BlocksToExtractVec;
196  for (BasicBlock *BB : BBs) {
197  // Check if the module contains BB.
198  if (BB->getParent()->getParent() != &M)
199  report_fatal_error("Invalid basic block");
200  LLVM_DEBUG(dbgs() << "BlockExtractor: Extracting "
201  << BB->getParent()->getName() << ":" << BB->getName()
202  << "\n");
203  BlocksToExtractVec.push_back(BB);
204  if (const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
205  BlocksToExtractVec.push_back(II->getUnwindDest());
206  ++NumExtracted;
207  Changed = true;
208  }
209  Function *F = CodeExtractor(BlocksToExtractVec).extractCodeRegion();
210  if (F)
211  LLVM_DEBUG(dbgs() << "Extracted group '" << (*BBs.begin())->getName()
212  << "' in: " << F->getName() << '\n');
213  else
214  LLVM_DEBUG(dbgs() << "Failed to extract for group '"
215  << (*BBs.begin())->getName() << "'\n");
216  }
217 
218  // Erase the functions.
219  if (EraseFunctions || BlockExtractorEraseFuncs) {
220  for (Function *F : Functions) {
221  LLVM_DEBUG(dbgs() << "BlockExtractor: Trying to delete " << F->getName()
222  << "\n");
223  F->deleteBody();
224  }
225  // Set linkage as ExternalLinkage to avoid erasing unreachable functions.
226  for (Function &F : M)
228  Changed = true;
229  }
230 
231  return Changed;
232 }
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