File: | lib/Transforms/Utils/CodeExtractor.cpp |
Location: | line 368, column 32 |
Description: | Function call argument is an uninitialized value |
1 | //===- CodeExtractor.cpp - Pull code region into a new function -----------===// | |||
2 | // | |||
3 | // The LLVM Compiler Infrastructure | |||
4 | // | |||
5 | // This file is distributed under the University of Illinois Open Source | |||
6 | // License. See LICENSE.TXT for details. | |||
7 | // | |||
8 | //===----------------------------------------------------------------------===// | |||
9 | // | |||
10 | // This file implements the interface to tear out a code region, such as an | |||
11 | // individual loop or a parallel section, into a new function, replacing it with | |||
12 | // a call to the new function. | |||
13 | // | |||
14 | //===----------------------------------------------------------------------===// | |||
15 | ||||
16 | #include "llvm/Transforms/Utils/CodeExtractor.h" | |||
17 | #include "llvm/ADT/STLExtras.h" | |||
18 | #include "llvm/ADT/SetVector.h" | |||
19 | #include "llvm/ADT/StringExtras.h" | |||
20 | #include "llvm/Analysis/LoopInfo.h" | |||
21 | #include "llvm/Analysis/RegionInfo.h" | |||
22 | #include "llvm/Analysis/RegionIterator.h" | |||
23 | #include "llvm/IR/Constants.h" | |||
24 | #include "llvm/IR/DerivedTypes.h" | |||
25 | #include "llvm/IR/Dominators.h" | |||
26 | #include "llvm/IR/Instructions.h" | |||
27 | #include "llvm/IR/Intrinsics.h" | |||
28 | #include "llvm/IR/LLVMContext.h" | |||
29 | #include "llvm/IR/Module.h" | |||
30 | #include "llvm/IR/Verifier.h" | |||
31 | #include "llvm/Pass.h" | |||
32 | #include "llvm/Support/CommandLine.h" | |||
33 | #include "llvm/Support/Debug.h" | |||
34 | #include "llvm/Support/ErrorHandling.h" | |||
35 | #include "llvm/Support/raw_ostream.h" | |||
36 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
37 | #include <algorithm> | |||
38 | #include <set> | |||
39 | using namespace llvm; | |||
40 | ||||
41 | #define DEBUG_TYPE"code-extractor" "code-extractor" | |||
42 | ||||
43 | // Provide a command-line option to aggregate function arguments into a struct | |||
44 | // for functions produced by the code extractor. This is useful when converting | |||
45 | // extracted functions to pthread-based code, as only one argument (void*) can | |||
46 | // be passed in to pthread_create(). | |||
47 | static cl::opt<bool> | |||
48 | AggregateArgsOpt("aggregate-extracted-args", cl::Hidden, | |||
49 | cl::desc("Aggregate arguments to code-extracted functions")); | |||
50 | ||||
51 | /// \brief Test whether a block is valid for extraction. | |||
52 | static bool isBlockValidForExtraction(const BasicBlock &BB) { | |||
53 | // Landing pads must be in the function where they were inserted for cleanup. | |||
54 | if (BB.isEHPad()) | |||
55 | return false; | |||
56 | ||||
57 | // Don't hoist code containing allocas, invokes, or vastarts. | |||
58 | for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) { | |||
59 | if (isa<AllocaInst>(I) || isa<InvokeInst>(I)) | |||
60 | return false; | |||
61 | if (const CallInst *CI = dyn_cast<CallInst>(I)) | |||
62 | if (const Function *F = CI->getCalledFunction()) | |||
63 | if (F->getIntrinsicID() == Intrinsic::vastart) | |||
64 | return false; | |||
65 | } | |||
66 | ||||
67 | return true; | |||
68 | } | |||
69 | ||||
70 | /// \brief Build a set of blocks to extract if the input blocks are viable. | |||
71 | template <typename IteratorT> | |||
72 | static SetVector<BasicBlock *> buildExtractionBlockSet(IteratorT BBBegin, | |||
73 | IteratorT BBEnd) { | |||
74 | SetVector<BasicBlock *> Result; | |||
75 | ||||
76 | assert(BBBegin != BBEnd)((BBBegin != BBEnd) ? static_cast<void> (0) : __assert_fail ("BBBegin != BBEnd", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn250153/lib/Transforms/Utils/CodeExtractor.cpp" , 76, __PRETTY_FUNCTION__)); | |||
77 | ||||
78 | // Loop over the blocks, adding them to our set-vector, and aborting with an | |||
79 | // empty set if we encounter invalid blocks. | |||
80 | for (IteratorT I = BBBegin, E = BBEnd; I != E; ++I) { | |||
81 | if (!Result.insert(*I)) | |||
82 | llvm_unreachable("Repeated basic blocks in extraction input")::llvm::llvm_unreachable_internal("Repeated basic blocks in extraction input" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn250153/lib/Transforms/Utils/CodeExtractor.cpp" , 82); | |||
83 | ||||
84 | if (!isBlockValidForExtraction(**I)) { | |||
85 | Result.clear(); | |||
86 | return Result; | |||
87 | } | |||
88 | } | |||
89 | ||||
90 | #ifndef NDEBUG | |||
91 | for (SetVector<BasicBlock *>::iterator I = std::next(Result.begin()), | |||
92 | E = Result.end(); | |||
93 | I != E; ++I) | |||
94 | for (pred_iterator PI = pred_begin(*I), PE = pred_end(*I); | |||
95 | PI != PE; ++PI) | |||
96 | assert(Result.count(*PI) &&((Result.count(*PI) && "No blocks in this region may have entries from outside the region" " except for the first block!") ? static_cast<void> (0 ) : __assert_fail ("Result.count(*PI) && \"No blocks in this region may have entries from outside the region\" \" except for the first block!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn250153/lib/Transforms/Utils/CodeExtractor.cpp" , 98, __PRETTY_FUNCTION__)) | |||
97 | "No blocks in this region may have entries from outside the region"((Result.count(*PI) && "No blocks in this region may have entries from outside the region" " except for the first block!") ? static_cast<void> (0 ) : __assert_fail ("Result.count(*PI) && \"No blocks in this region may have entries from outside the region\" \" except for the first block!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn250153/lib/Transforms/Utils/CodeExtractor.cpp" , 98, __PRETTY_FUNCTION__)) | |||
98 | " except for the first block!")((Result.count(*PI) && "No blocks in this region may have entries from outside the region" " except for the first block!") ? static_cast<void> (0 ) : __assert_fail ("Result.count(*PI) && \"No blocks in this region may have entries from outside the region\" \" except for the first block!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn250153/lib/Transforms/Utils/CodeExtractor.cpp" , 98, __PRETTY_FUNCTION__)); | |||
99 | #endif | |||
100 | ||||
101 | return Result; | |||
102 | } | |||
103 | ||||
104 | /// \brief Helper to call buildExtractionBlockSet with an ArrayRef. | |||
105 | static SetVector<BasicBlock *> | |||
106 | buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs) { | |||
107 | return buildExtractionBlockSet(BBs.begin(), BBs.end()); | |||
108 | } | |||
109 | ||||
110 | /// \brief Helper to call buildExtractionBlockSet with a RegionNode. | |||
111 | static SetVector<BasicBlock *> | |||
112 | buildExtractionBlockSet(const RegionNode &RN) { | |||
113 | if (!RN.isSubRegion()) | |||
114 | // Just a single BasicBlock. | |||
115 | return buildExtractionBlockSet(RN.getNodeAs<BasicBlock>()); | |||
116 | ||||
117 | const Region &R = *RN.getNodeAs<Region>(); | |||
118 | ||||
119 | return buildExtractionBlockSet(R.block_begin(), R.block_end()); | |||
120 | } | |||
121 | ||||
122 | CodeExtractor::CodeExtractor(BasicBlock *BB, bool AggregateArgs) | |||
123 | : DT(nullptr), AggregateArgs(AggregateArgs||AggregateArgsOpt), | |||
124 | Blocks(buildExtractionBlockSet(BB)), NumExitBlocks(~0U) {} | |||
125 | ||||
126 | CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, | |||
127 | bool AggregateArgs) | |||
128 | : DT(DT), AggregateArgs(AggregateArgs||AggregateArgsOpt), | |||
129 | Blocks(buildExtractionBlockSet(BBs)), NumExitBlocks(~0U) {} | |||
130 | ||||
131 | CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs) | |||
132 | : DT(&DT), AggregateArgs(AggregateArgs||AggregateArgsOpt), | |||
133 | Blocks(buildExtractionBlockSet(L.getBlocks())), NumExitBlocks(~0U) {} | |||
134 | ||||
135 | CodeExtractor::CodeExtractor(DominatorTree &DT, const RegionNode &RN, | |||
136 | bool AggregateArgs) | |||
137 | : DT(&DT), AggregateArgs(AggregateArgs||AggregateArgsOpt), | |||
138 | Blocks(buildExtractionBlockSet(RN)), NumExitBlocks(~0U) {} | |||
139 | ||||
140 | /// definedInRegion - Return true if the specified value is defined in the | |||
141 | /// extracted region. | |||
142 | static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) { | |||
143 | if (Instruction *I = dyn_cast<Instruction>(V)) | |||
144 | if (Blocks.count(I->getParent())) | |||
145 | return true; | |||
146 | return false; | |||
147 | } | |||
148 | ||||
149 | /// definedInCaller - Return true if the specified value is defined in the | |||
150 | /// function being code extracted, but not in the region being extracted. | |||
151 | /// These values must be passed in as live-ins to the function. | |||
152 | static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) { | |||
153 | if (isa<Argument>(V)) return true; | |||
154 | if (Instruction *I = dyn_cast<Instruction>(V)) | |||
155 | if (!Blocks.count(I->getParent())) | |||
156 | return true; | |||
157 | return false; | |||
158 | } | |||
159 | ||||
160 | void CodeExtractor::findInputsOutputs(ValueSet &Inputs, | |||
161 | ValueSet &Outputs) const { | |||
162 | for (SetVector<BasicBlock *>::const_iterator I = Blocks.begin(), | |||
163 | E = Blocks.end(); | |||
164 | I != E; ++I) { | |||
165 | BasicBlock *BB = *I; | |||
166 | ||||
167 | // If a used value is defined outside the region, it's an input. If an | |||
168 | // instruction is used outside the region, it's an output. | |||
169 | for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); | |||
170 | II != IE; ++II) { | |||
171 | for (User::op_iterator OI = II->op_begin(), OE = II->op_end(); | |||
172 | OI != OE; ++OI) | |||
173 | if (definedInCaller(Blocks, *OI)) | |||
174 | Inputs.insert(*OI); | |||
175 | ||||
176 | for (User *U : II->users()) | |||
177 | if (!definedInRegion(Blocks, U)) { | |||
178 | Outputs.insert(&*II); | |||
179 | break; | |||
180 | } | |||
181 | } | |||
182 | } | |||
183 | } | |||
184 | ||||
185 | /// severSplitPHINodes - If a PHI node has multiple inputs from outside of the | |||
186 | /// region, we need to split the entry block of the region so that the PHI node | |||
187 | /// is easier to deal with. | |||
188 | void CodeExtractor::severSplitPHINodes(BasicBlock *&Header) { | |||
189 | unsigned NumPredsFromRegion = 0; | |||
190 | unsigned NumPredsOutsideRegion = 0; | |||
191 | ||||
192 | if (Header != &Header->getParent()->getEntryBlock()) { | |||
193 | PHINode *PN = dyn_cast<PHINode>(Header->begin()); | |||
194 | if (!PN) return; // No PHI nodes. | |||
195 | ||||
196 | // If the header node contains any PHI nodes, check to see if there is more | |||
197 | // than one entry from outside the region. If so, we need to sever the | |||
198 | // header block into two. | |||
199 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |||
200 | if (Blocks.count(PN->getIncomingBlock(i))) | |||
201 | ++NumPredsFromRegion; | |||
202 | else | |||
203 | ++NumPredsOutsideRegion; | |||
204 | ||||
205 | // If there is one (or fewer) predecessor from outside the region, we don't | |||
206 | // need to do anything special. | |||
207 | if (NumPredsOutsideRegion <= 1) return; | |||
208 | } | |||
209 | ||||
210 | // Otherwise, we need to split the header block into two pieces: one | |||
211 | // containing PHI nodes merging values from outside of the region, and a | |||
212 | // second that contains all of the code for the block and merges back any | |||
213 | // incoming values from inside of the region. | |||
214 | BasicBlock::iterator AfterPHIs = Header->getFirstNonPHI()->getIterator(); | |||
215 | BasicBlock *NewBB = Header->splitBasicBlock(AfterPHIs, | |||
216 | Header->getName()+".ce"); | |||
217 | ||||
218 | // We only want to code extract the second block now, and it becomes the new | |||
219 | // header of the region. | |||
220 | BasicBlock *OldPred = Header; | |||
221 | Blocks.remove(OldPred); | |||
222 | Blocks.insert(NewBB); | |||
223 | Header = NewBB; | |||
224 | ||||
225 | // Okay, update dominator sets. The blocks that dominate the new one are the | |||
226 | // blocks that dominate TIBB plus the new block itself. | |||
227 | if (DT) | |||
228 | DT->splitBlock(NewBB); | |||
229 | ||||
230 | // Okay, now we need to adjust the PHI nodes and any branches from within the | |||
231 | // region to go to the new header block instead of the old header block. | |||
232 | if (NumPredsFromRegion) { | |||
233 | PHINode *PN = cast<PHINode>(OldPred->begin()); | |||
234 | // Loop over all of the predecessors of OldPred that are in the region, | |||
235 | // changing them to branch to NewBB instead. | |||
236 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |||
237 | if (Blocks.count(PN->getIncomingBlock(i))) { | |||
238 | TerminatorInst *TI = PN->getIncomingBlock(i)->getTerminator(); | |||
239 | TI->replaceUsesOfWith(OldPred, NewBB); | |||
240 | } | |||
241 | ||||
242 | // Okay, everything within the region is now branching to the right block, we | |||
243 | // just have to update the PHI nodes now, inserting PHI nodes into NewBB. | |||
244 | for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) { | |||
245 | PHINode *PN = cast<PHINode>(AfterPHIs); | |||
246 | // Create a new PHI node in the new region, which has an incoming value | |||
247 | // from OldPred of PN. | |||
248 | PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion, | |||
249 | PN->getName() + ".ce", &NewBB->front()); | |||
250 | NewPN->addIncoming(PN, OldPred); | |||
251 | ||||
252 | // Loop over all of the incoming value in PN, moving them to NewPN if they | |||
253 | // are from the extracted region. | |||
254 | for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { | |||
255 | if (Blocks.count(PN->getIncomingBlock(i))) { | |||
256 | NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); | |||
257 | PN->removeIncomingValue(i); | |||
258 | --i; | |||
259 | } | |||
260 | } | |||
261 | } | |||
262 | } | |||
263 | } | |||
264 | ||||
265 | void CodeExtractor::splitReturnBlocks() { | |||
266 | for (SetVector<BasicBlock *>::iterator I = Blocks.begin(), E = Blocks.end(); | |||
267 | I != E; ++I) | |||
268 | if (ReturnInst *RI = dyn_cast<ReturnInst>((*I)->getTerminator())) { | |||
269 | BasicBlock *New = | |||
270 | (*I)->splitBasicBlock(RI->getIterator(), (*I)->getName() + ".ret"); | |||
271 | if (DT) { | |||
272 | // Old dominates New. New node dominates all other nodes dominated | |||
273 | // by Old. | |||
274 | DomTreeNode *OldNode = DT->getNode(*I); | |||
275 | SmallVector<DomTreeNode*, 8> Children; | |||
276 | for (DomTreeNode::iterator DI = OldNode->begin(), DE = OldNode->end(); | |||
277 | DI != DE; ++DI) | |||
278 | Children.push_back(*DI); | |||
279 | ||||
280 | DomTreeNode *NewNode = DT->addNewBlock(New, *I); | |||
281 | ||||
282 | for (SmallVectorImpl<DomTreeNode *>::iterator I = Children.begin(), | |||
283 | E = Children.end(); I != E; ++I) | |||
284 | DT->changeImmediateDominator(*I, NewNode); | |||
285 | } | |||
286 | } | |||
287 | } | |||
288 | ||||
289 | /// constructFunction - make a function based on inputs and outputs, as follows: | |||
290 | /// f(in0, ..., inN, out0, ..., outN) | |||
291 | /// | |||
292 | Function *CodeExtractor::constructFunction(const ValueSet &inputs, | |||
293 | const ValueSet &outputs, | |||
294 | BasicBlock *header, | |||
295 | BasicBlock *newRootNode, | |||
296 | BasicBlock *newHeader, | |||
297 | Function *oldFunction, | |||
298 | Module *M) { | |||
299 | DEBUG(dbgs() << "inputs: " << inputs.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "inputs: " << inputs .size() << "\n"; } } while (0); | |||
300 | DEBUG(dbgs() << "outputs: " << outputs.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "outputs: " << outputs .size() << "\n"; } } while (0); | |||
301 | ||||
302 | // This function returns unsigned, outputs will go back by reference. | |||
303 | switch (NumExitBlocks) { | |||
| ||||
304 | case 0: | |||
305 | case 1: RetTy = Type::getVoidTy(header->getContext()); break; | |||
306 | case 2: RetTy = Type::getInt1Ty(header->getContext()); break; | |||
307 | default: RetTy = Type::getInt16Ty(header->getContext()); break; | |||
308 | } | |||
309 | ||||
310 | std::vector<Type*> paramTy; | |||
311 | ||||
312 | // Add the types of the input values to the function's argument list | |||
313 | for (ValueSet::const_iterator i = inputs.begin(), e = inputs.end(); | |||
314 | i != e; ++i) { | |||
315 | const Value *value = *i; | |||
316 | DEBUG(dbgs() << "value used in func: " << *value << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "value used in func: " << *value << "\n"; } } while (0); | |||
317 | paramTy.push_back(value->getType()); | |||
318 | } | |||
319 | ||||
320 | // Add the types of the output values to the function's argument list. | |||
321 | for (ValueSet::const_iterator I = outputs.begin(), E = outputs.end(); | |||
322 | I != E; ++I) { | |||
323 | DEBUG(dbgs() << "instr used in func: " << **I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "instr used in func: " << **I << "\n"; } } while (0); | |||
324 | if (AggregateArgs) | |||
325 | paramTy.push_back((*I)->getType()); | |||
326 | else | |||
327 | paramTy.push_back(PointerType::getUnqual((*I)->getType())); | |||
328 | } | |||
329 | ||||
330 | DEBUG(dbgs() << "Function type: " << *RetTy << " f(")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "Function type: " << *RetTy << " f("; } } while (0); | |||
331 | for (std::vector<Type*>::iterator i = paramTy.begin(), | |||
332 | e = paramTy.end(); i != e; ++i) | |||
333 | DEBUG(dbgs() << **i << ", ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << **i << ", "; } } while (0); | |||
334 | DEBUG(dbgs() << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << ")\n"; } } while (0); | |||
335 | ||||
336 | StructType *StructTy; | |||
337 | if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { | |||
338 | StructTy = StructType::get(M->getContext(), paramTy); | |||
339 | paramTy.clear(); | |||
340 | paramTy.push_back(PointerType::getUnqual(StructTy)); | |||
341 | } | |||
342 | FunctionType *funcType = | |||
343 | FunctionType::get(RetTy, paramTy, false); | |||
344 | ||||
345 | // Create the new function | |||
346 | Function *newFunction = Function::Create(funcType, | |||
347 | GlobalValue::InternalLinkage, | |||
348 | oldFunction->getName() + "_" + | |||
349 | header->getName(), M); | |||
350 | // If the old function is no-throw, so is the new one. | |||
351 | if (oldFunction->doesNotThrow()) | |||
352 | newFunction->setDoesNotThrow(); | |||
353 | ||||
354 | newFunction->getBasicBlockList().push_back(newRootNode); | |||
355 | ||||
356 | // Create an iterator to name all of the arguments we inserted. | |||
357 | Function::arg_iterator AI = newFunction->arg_begin(); | |||
358 | ||||
359 | // Rewrite all users of the inputs in the extracted region to use the | |||
360 | // arguments (or appropriate addressing into struct) instead. | |||
361 | for (unsigned i = 0, e = inputs.size(); i != e; ++i) { | |||
362 | Value *RewriteVal; | |||
363 | if (AggregateArgs) { | |||
364 | Value *Idx[2]; | |||
365 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext())); | |||
366 | Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i); | |||
367 | TerminatorInst *TI = newFunction->begin()->getTerminator(); | |||
368 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
| ||||
369 | StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI); | |||
370 | RewriteVal = new LoadInst(GEP, "loadgep_" + inputs[i]->getName(), TI); | |||
371 | } else | |||
372 | RewriteVal = &*AI++; | |||
373 | ||||
374 | std::vector<User*> Users(inputs[i]->user_begin(), inputs[i]->user_end()); | |||
375 | for (std::vector<User*>::iterator use = Users.begin(), useE = Users.end(); | |||
376 | use != useE; ++use) | |||
377 | if (Instruction* inst = dyn_cast<Instruction>(*use)) | |||
378 | if (Blocks.count(inst->getParent())) | |||
379 | inst->replaceUsesOfWith(inputs[i], RewriteVal); | |||
380 | } | |||
381 | ||||
382 | // Set names for input and output arguments. | |||
383 | if (!AggregateArgs) { | |||
384 | AI = newFunction->arg_begin(); | |||
385 | for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI) | |||
386 | AI->setName(inputs[i]->getName()); | |||
387 | for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI) | |||
388 | AI->setName(outputs[i]->getName()+".out"); | |||
389 | } | |||
390 | ||||
391 | // Rewrite branches to basic blocks outside of the loop to new dummy blocks | |||
392 | // within the new function. This must be done before we lose track of which | |||
393 | // blocks were originally in the code region. | |||
394 | std::vector<User*> Users(header->user_begin(), header->user_end()); | |||
395 | for (unsigned i = 0, e = Users.size(); i != e; ++i) | |||
396 | // The BasicBlock which contains the branch is not in the region | |||
397 | // modify the branch target to a new block | |||
398 | if (TerminatorInst *TI = dyn_cast<TerminatorInst>(Users[i])) | |||
399 | if (!Blocks.count(TI->getParent()) && | |||
400 | TI->getParent()->getParent() == oldFunction) | |||
401 | TI->replaceUsesOfWith(header, newHeader); | |||
402 | ||||
403 | return newFunction; | |||
404 | } | |||
405 | ||||
406 | /// FindPhiPredForUseInBlock - Given a value and a basic block, find a PHI | |||
407 | /// that uses the value within the basic block, and return the predecessor | |||
408 | /// block associated with that use, or return 0 if none is found. | |||
409 | static BasicBlock* FindPhiPredForUseInBlock(Value* Used, BasicBlock* BB) { | |||
410 | for (Use &U : Used->uses()) { | |||
411 | PHINode *P = dyn_cast<PHINode>(U.getUser()); | |||
412 | if (P && P->getParent() == BB) | |||
413 | return P->getIncomingBlock(U); | |||
414 | } | |||
415 | ||||
416 | return nullptr; | |||
417 | } | |||
418 | ||||
419 | /// emitCallAndSwitchStatement - This method sets up the caller side by adding | |||
420 | /// the call instruction, splitting any PHI nodes in the header block as | |||
421 | /// necessary. | |||
422 | void CodeExtractor:: | |||
423 | emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, | |||
424 | ValueSet &inputs, ValueSet &outputs) { | |||
425 | // Emit a call to the new function, passing in: *pointer to struct (if | |||
426 | // aggregating parameters), or plan inputs and allocated memory for outputs | |||
427 | std::vector<Value*> params, StructValues, ReloadOutputs, Reloads; | |||
428 | ||||
429 | LLVMContext &Context = newFunction->getContext(); | |||
430 | ||||
431 | // Add inputs as params, or to be filled into the struct | |||
432 | for (ValueSet::iterator i = inputs.begin(), e = inputs.end(); i != e; ++i) | |||
433 | if (AggregateArgs) | |||
434 | StructValues.push_back(*i); | |||
435 | else | |||
436 | params.push_back(*i); | |||
437 | ||||
438 | // Create allocas for the outputs | |||
439 | for (ValueSet::iterator i = outputs.begin(), e = outputs.end(); i != e; ++i) { | |||
440 | if (AggregateArgs) { | |||
441 | StructValues.push_back(*i); | |||
442 | } else { | |||
443 | AllocaInst *alloca = | |||
444 | new AllocaInst((*i)->getType(), nullptr, (*i)->getName() + ".loc", | |||
445 | &codeReplacer->getParent()->front().front()); | |||
446 | ReloadOutputs.push_back(alloca); | |||
447 | params.push_back(alloca); | |||
448 | } | |||
449 | } | |||
450 | ||||
451 | StructType *StructArgTy = nullptr; | |||
452 | AllocaInst *Struct = nullptr; | |||
453 | if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { | |||
454 | std::vector<Type*> ArgTypes; | |||
455 | for (ValueSet::iterator v = StructValues.begin(), | |||
456 | ve = StructValues.end(); v != ve; ++v) | |||
457 | ArgTypes.push_back((*v)->getType()); | |||
458 | ||||
459 | // Allocate a struct at the beginning of this function | |||
460 | StructArgTy = StructType::get(newFunction->getContext(), ArgTypes); | |||
461 | Struct = new AllocaInst(StructArgTy, nullptr, "structArg", | |||
462 | &codeReplacer->getParent()->front().front()); | |||
463 | params.push_back(Struct); | |||
464 | ||||
465 | for (unsigned i = 0, e = inputs.size(); i != e; ++i) { | |||
466 | Value *Idx[2]; | |||
467 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); | |||
468 | Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i); | |||
469 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
470 | StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName()); | |||
471 | codeReplacer->getInstList().push_back(GEP); | |||
472 | StoreInst *SI = new StoreInst(StructValues[i], GEP); | |||
473 | codeReplacer->getInstList().push_back(SI); | |||
474 | } | |||
475 | } | |||
476 | ||||
477 | // Emit the call to the function | |||
478 | CallInst *call = CallInst::Create(newFunction, params, | |||
479 | NumExitBlocks > 1 ? "targetBlock" : ""); | |||
480 | codeReplacer->getInstList().push_back(call); | |||
481 | ||||
482 | Function::arg_iterator OutputArgBegin = newFunction->arg_begin(); | |||
483 | unsigned FirstOut = inputs.size(); | |||
484 | if (!AggregateArgs) | |||
485 | std::advance(OutputArgBegin, inputs.size()); | |||
486 | ||||
487 | // Reload the outputs passed in by reference | |||
488 | for (unsigned i = 0, e = outputs.size(); i != e; ++i) { | |||
489 | Value *Output = nullptr; | |||
490 | if (AggregateArgs) { | |||
491 | Value *Idx[2]; | |||
492 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); | |||
493 | Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); | |||
494 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
495 | StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName()); | |||
496 | codeReplacer->getInstList().push_back(GEP); | |||
497 | Output = GEP; | |||
498 | } else { | |||
499 | Output = ReloadOutputs[i]; | |||
500 | } | |||
501 | LoadInst *load = new LoadInst(Output, outputs[i]->getName()+".reload"); | |||
502 | Reloads.push_back(load); | |||
503 | codeReplacer->getInstList().push_back(load); | |||
504 | std::vector<User*> Users(outputs[i]->user_begin(), outputs[i]->user_end()); | |||
505 | for (unsigned u = 0, e = Users.size(); u != e; ++u) { | |||
506 | Instruction *inst = cast<Instruction>(Users[u]); | |||
507 | if (!Blocks.count(inst->getParent())) | |||
508 | inst->replaceUsesOfWith(outputs[i], load); | |||
509 | } | |||
510 | } | |||
511 | ||||
512 | // Now we can emit a switch statement using the call as a value. | |||
513 | SwitchInst *TheSwitch = | |||
514 | SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)), | |||
515 | codeReplacer, 0, codeReplacer); | |||
516 | ||||
517 | // Since there may be multiple exits from the original region, make the new | |||
518 | // function return an unsigned, switch on that number. This loop iterates | |||
519 | // over all of the blocks in the extracted region, updating any terminator | |||
520 | // instructions in the to-be-extracted region that branch to blocks that are | |||
521 | // not in the region to be extracted. | |||
522 | std::map<BasicBlock*, BasicBlock*> ExitBlockMap; | |||
523 | ||||
524 | unsigned switchVal = 0; | |||
525 | for (SetVector<BasicBlock*>::const_iterator i = Blocks.begin(), | |||
526 | e = Blocks.end(); i != e; ++i) { | |||
527 | TerminatorInst *TI = (*i)->getTerminator(); | |||
528 | for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) | |||
529 | if (!Blocks.count(TI->getSuccessor(i))) { | |||
530 | BasicBlock *OldTarget = TI->getSuccessor(i); | |||
531 | // add a new basic block which returns the appropriate value | |||
532 | BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; | |||
533 | if (!NewTarget) { | |||
534 | // If we don't already have an exit stub for this non-extracted | |||
535 | // destination, create one now! | |||
536 | NewTarget = BasicBlock::Create(Context, | |||
537 | OldTarget->getName() + ".exitStub", | |||
538 | newFunction); | |||
539 | unsigned SuccNum = switchVal++; | |||
540 | ||||
541 | Value *brVal = nullptr; | |||
542 | switch (NumExitBlocks) { | |||
543 | case 0: | |||
544 | case 1: break; // No value needed. | |||
545 | case 2: // Conditional branch, return a bool | |||
546 | brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum); | |||
547 | break; | |||
548 | default: | |||
549 | brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum); | |||
550 | break; | |||
551 | } | |||
552 | ||||
553 | ReturnInst *NTRet = ReturnInst::Create(Context, brVal, NewTarget); | |||
554 | ||||
555 | // Update the switch instruction. | |||
556 | TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context), | |||
557 | SuccNum), | |||
558 | OldTarget); | |||
559 | ||||
560 | // Restore values just before we exit | |||
561 | Function::arg_iterator OAI = OutputArgBegin; | |||
562 | for (unsigned out = 0, e = outputs.size(); out != e; ++out) { | |||
563 | // For an invoke/catchpad, the normal destination is the only one | |||
564 | // that is dominated by the result of the invocation | |||
565 | BasicBlock *DefBlock = cast<Instruction>(outputs[out])->getParent(); | |||
566 | ||||
567 | bool DominatesDef = true; | |||
568 | ||||
569 | BasicBlock *NormalDest = nullptr; | |||
570 | if (auto *Invoke = dyn_cast<InvokeInst>(outputs[out])) | |||
571 | NormalDest = Invoke->getNormalDest(); | |||
572 | if (auto *CatchPad = dyn_cast<CatchPadInst>(outputs[out])) | |||
573 | NormalDest = CatchPad->getNormalDest(); | |||
574 | ||||
575 | if (NormalDest) { | |||
576 | DefBlock = NormalDest; | |||
577 | ||||
578 | // Make sure we are looking at the original successor block, not | |||
579 | // at a newly inserted exit block, which won't be in the dominator | |||
580 | // info. | |||
581 | for (std::map<BasicBlock*, BasicBlock*>::iterator I = | |||
582 | ExitBlockMap.begin(), E = ExitBlockMap.end(); I != E; ++I) | |||
583 | if (DefBlock == I->second) { | |||
584 | DefBlock = I->first; | |||
585 | break; | |||
586 | } | |||
587 | ||||
588 | // In the extract block case, if the block we are extracting ends | |||
589 | // with an invoke instruction, make sure that we don't emit a | |||
590 | // store of the invoke value for the unwind block. | |||
591 | if (!DT && DefBlock != OldTarget) | |||
592 | DominatesDef = false; | |||
593 | } | |||
594 | ||||
595 | if (DT) { | |||
596 | DominatesDef = DT->dominates(DefBlock, OldTarget); | |||
597 | ||||
598 | // If the output value is used by a phi in the target block, | |||
599 | // then we need to test for dominance of the phi's predecessor | |||
600 | // instead. Unfortunately, this a little complicated since we | |||
601 | // have already rewritten uses of the value to uses of the reload. | |||
602 | BasicBlock* pred = FindPhiPredForUseInBlock(Reloads[out], | |||
603 | OldTarget); | |||
604 | if (pred && DT && DT->dominates(DefBlock, pred)) | |||
605 | DominatesDef = true; | |||
606 | } | |||
607 | ||||
608 | if (DominatesDef) { | |||
609 | if (AggregateArgs) { | |||
610 | Value *Idx[2]; | |||
611 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); | |||
612 | Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), | |||
613 | FirstOut+out); | |||
614 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
615 | StructArgTy, &*OAI, Idx, "gep_" + outputs[out]->getName(), | |||
616 | NTRet); | |||
617 | new StoreInst(outputs[out], GEP, NTRet); | |||
618 | } else { | |||
619 | new StoreInst(outputs[out], &*OAI, NTRet); | |||
620 | } | |||
621 | } | |||
622 | // Advance output iterator even if we don't emit a store | |||
623 | if (!AggregateArgs) ++OAI; | |||
624 | } | |||
625 | } | |||
626 | ||||
627 | // rewrite the original branch instruction with this new target | |||
628 | TI->setSuccessor(i, NewTarget); | |||
629 | } | |||
630 | } | |||
631 | ||||
632 | // Now that we've done the deed, simplify the switch instruction. | |||
633 | Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); | |||
634 | switch (NumExitBlocks) { | |||
635 | case 0: | |||
636 | // There are no successors (the block containing the switch itself), which | |||
637 | // means that previously this was the last part of the function, and hence | |||
638 | // this should be rewritten as a `ret' | |||
639 | ||||
640 | // Check if the function should return a value | |||
641 | if (OldFnRetTy->isVoidTy()) { | |||
642 | ReturnInst::Create(Context, nullptr, TheSwitch); // Return void | |||
643 | } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) { | |||
644 | // return what we have | |||
645 | ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch); | |||
646 | } else { | |||
647 | // Otherwise we must have code extracted an unwind or something, just | |||
648 | // return whatever we want. | |||
649 | ReturnInst::Create(Context, | |||
650 | Constant::getNullValue(OldFnRetTy), TheSwitch); | |||
651 | } | |||
652 | ||||
653 | TheSwitch->eraseFromParent(); | |||
654 | break; | |||
655 | case 1: | |||
656 | // Only a single destination, change the switch into an unconditional | |||
657 | // branch. | |||
658 | BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch); | |||
659 | TheSwitch->eraseFromParent(); | |||
660 | break; | |||
661 | case 2: | |||
662 | BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), | |||
663 | call, TheSwitch); | |||
664 | TheSwitch->eraseFromParent(); | |||
665 | break; | |||
666 | default: | |||
667 | // Otherwise, make the default destination of the switch instruction be one | |||
668 | // of the other successors. | |||
669 | TheSwitch->setCondition(call); | |||
670 | TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks)); | |||
671 | // Remove redundant case | |||
672 | TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1)); | |||
673 | break; | |||
674 | } | |||
675 | } | |||
676 | ||||
677 | void CodeExtractor::moveCodeToFunction(Function *newFunction) { | |||
678 | Function *oldFunc = (*Blocks.begin())->getParent(); | |||
679 | Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); | |||
680 | Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); | |||
681 | ||||
682 | for (SetVector<BasicBlock*>::const_iterator i = Blocks.begin(), | |||
683 | e = Blocks.end(); i != e; ++i) { | |||
684 | // Delete the basic block from the old function, and the list of blocks | |||
685 | oldBlocks.remove(*i); | |||
686 | ||||
687 | // Insert this basic block into the new function | |||
688 | newBlocks.push_back(*i); | |||
689 | } | |||
690 | } | |||
691 | ||||
692 | Function *CodeExtractor::extractCodeRegion() { | |||
693 | if (!isEligible()) | |||
694 | return nullptr; | |||
695 | ||||
696 | ValueSet inputs, outputs; | |||
697 | ||||
698 | // Assumption: this is a single-entry code region, and the header is the first | |||
699 | // block in the region. | |||
700 | BasicBlock *header = *Blocks.begin(); | |||
701 | ||||
702 | // If we have to split PHI nodes or the entry block, do so now. | |||
703 | severSplitPHINodes(header); | |||
704 | ||||
705 | // If we have any return instructions in the region, split those blocks so | |||
706 | // that the return is not in the region. | |||
707 | splitReturnBlocks(); | |||
708 | ||||
709 | Function *oldFunction = header->getParent(); | |||
710 | ||||
711 | // This takes place of the original loop | |||
712 | BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(), | |||
713 | "codeRepl", oldFunction, | |||
714 | header); | |||
715 | ||||
716 | // The new function needs a root node because other nodes can branch to the | |||
717 | // head of the region, but the entry node of a function cannot have preds. | |||
718 | BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(), | |||
719 | "newFuncRoot"); | |||
720 | newFuncRoot->getInstList().push_back(BranchInst::Create(header)); | |||
721 | ||||
722 | // Find inputs to, outputs from the code region. | |||
723 | findInputsOutputs(inputs, outputs); | |||
724 | ||||
725 | SmallPtrSet<BasicBlock *, 1> ExitBlocks; | |||
726 | for (SetVector<BasicBlock *>::iterator I = Blocks.begin(), E = Blocks.end(); | |||
727 | I != E; ++I) | |||
728 | for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) | |||
729 | if (!Blocks.count(*SI)) | |||
730 | ExitBlocks.insert(*SI); | |||
731 | NumExitBlocks = ExitBlocks.size(); | |||
732 | ||||
733 | // Construct new function based on inputs/outputs & add allocas for all defs. | |||
734 | Function *newFunction = constructFunction(inputs, outputs, header, | |||
735 | newFuncRoot, | |||
736 | codeReplacer, oldFunction, | |||
737 | oldFunction->getParent()); | |||
738 | ||||
739 | emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); | |||
740 | ||||
741 | moveCodeToFunction(newFunction); | |||
742 | ||||
743 | // Loop over all of the PHI nodes in the header block, and change any | |||
744 | // references to the old incoming edge to be the new incoming edge. | |||
745 | for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) { | |||
746 | PHINode *PN = cast<PHINode>(I); | |||
747 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |||
748 | if (!Blocks.count(PN->getIncomingBlock(i))) | |||
749 | PN->setIncomingBlock(i, newFuncRoot); | |||
750 | } | |||
751 | ||||
752 | // Look at all successors of the codeReplacer block. If any of these blocks | |||
753 | // had PHI nodes in them, we need to update the "from" block to be the code | |||
754 | // replacer, not the original block in the extracted region. | |||
755 | std::vector<BasicBlock*> Succs(succ_begin(codeReplacer), | |||
756 | succ_end(codeReplacer)); | |||
757 | for (unsigned i = 0, e = Succs.size(); i != e; ++i) | |||
758 | for (BasicBlock::iterator I = Succs[i]->begin(); isa<PHINode>(I); ++I) { | |||
759 | PHINode *PN = cast<PHINode>(I); | |||
760 | std::set<BasicBlock*> ProcessedPreds; | |||
761 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |||
762 | if (Blocks.count(PN->getIncomingBlock(i))) { | |||
763 | if (ProcessedPreds.insert(PN->getIncomingBlock(i)).second) | |||
764 | PN->setIncomingBlock(i, codeReplacer); | |||
765 | else { | |||
766 | // There were multiple entries in the PHI for this block, now there | |||
767 | // is only one, so remove the duplicated entries. | |||
768 | PN->removeIncomingValue(i, false); | |||
769 | --i; --e; | |||
770 | } | |||
771 | } | |||
772 | } | |||
773 | ||||
774 | //cerr << "NEW FUNCTION: " << *newFunction; | |||
775 | // verifyFunction(*newFunction); | |||
776 | ||||
777 | // cerr << "OLD FUNCTION: " << *oldFunction; | |||
778 | // verifyFunction(*oldFunction); | |||
779 | ||||
780 | DEBUG(if (verifyFunction(*newFunction))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { if (verifyFunction(*newFunction)) report_fatal_error ("verifyFunction failed!"); } } while (0) | |||
781 | report_fatal_error("verifyFunction failed!"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { if (verifyFunction(*newFunction)) report_fatal_error ("verifyFunction failed!"); } } while (0); | |||
782 | return newFunction; | |||
783 | } |