File: | lib/Transforms/Utils/CodeExtractor.cpp |
Warning: | line 856, column 32 1st function call argument is an uninitialized value |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- CodeExtractor.cpp - Pull code region into a new function -----------===// | |||
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 file implements the interface to tear out a code region, such as an | |||
10 | // individual loop or a parallel section, into a new function, replacing it with | |||
11 | // a call to the new function. | |||
12 | // | |||
13 | //===----------------------------------------------------------------------===// | |||
14 | ||||
15 | #include "llvm/Transforms/Utils/CodeExtractor.h" | |||
16 | #include "llvm/ADT/ArrayRef.h" | |||
17 | #include "llvm/ADT/DenseMap.h" | |||
18 | #include "llvm/ADT/Optional.h" | |||
19 | #include "llvm/ADT/STLExtras.h" | |||
20 | #include "llvm/ADT/SetVector.h" | |||
21 | #include "llvm/ADT/SmallPtrSet.h" | |||
22 | #include "llvm/ADT/SmallVector.h" | |||
23 | #include "llvm/Analysis/AssumptionCache.h" | |||
24 | #include "llvm/Analysis/BlockFrequencyInfo.h" | |||
25 | #include "llvm/Analysis/BlockFrequencyInfoImpl.h" | |||
26 | #include "llvm/Analysis/BranchProbabilityInfo.h" | |||
27 | #include "llvm/Analysis/LoopInfo.h" | |||
28 | #include "llvm/IR/Argument.h" | |||
29 | #include "llvm/IR/Attributes.h" | |||
30 | #include "llvm/IR/BasicBlock.h" | |||
31 | #include "llvm/IR/CFG.h" | |||
32 | #include "llvm/IR/Constant.h" | |||
33 | #include "llvm/IR/Constants.h" | |||
34 | #include "llvm/IR/DataLayout.h" | |||
35 | #include "llvm/IR/DerivedTypes.h" | |||
36 | #include "llvm/IR/Dominators.h" | |||
37 | #include "llvm/IR/Function.h" | |||
38 | #include "llvm/IR/GlobalValue.h" | |||
39 | #include "llvm/IR/InstrTypes.h" | |||
40 | #include "llvm/IR/Instruction.h" | |||
41 | #include "llvm/IR/Instructions.h" | |||
42 | #include "llvm/IR/IntrinsicInst.h" | |||
43 | #include "llvm/IR/Intrinsics.h" | |||
44 | #include "llvm/IR/LLVMContext.h" | |||
45 | #include "llvm/IR/MDBuilder.h" | |||
46 | #include "llvm/IR/Module.h" | |||
47 | #include "llvm/IR/PatternMatch.h" | |||
48 | #include "llvm/IR/Type.h" | |||
49 | #include "llvm/IR/User.h" | |||
50 | #include "llvm/IR/Value.h" | |||
51 | #include "llvm/IR/Verifier.h" | |||
52 | #include "llvm/Pass.h" | |||
53 | #include "llvm/Support/BlockFrequency.h" | |||
54 | #include "llvm/Support/BranchProbability.h" | |||
55 | #include "llvm/Support/Casting.h" | |||
56 | #include "llvm/Support/CommandLine.h" | |||
57 | #include "llvm/Support/Debug.h" | |||
58 | #include "llvm/Support/ErrorHandling.h" | |||
59 | #include "llvm/Support/raw_ostream.h" | |||
60 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
61 | #include "llvm/Transforms/Utils/Local.h" | |||
62 | #include <cassert> | |||
63 | #include <cstdint> | |||
64 | #include <iterator> | |||
65 | #include <map> | |||
66 | #include <set> | |||
67 | #include <utility> | |||
68 | #include <vector> | |||
69 | ||||
70 | using namespace llvm; | |||
71 | using namespace llvm::PatternMatch; | |||
72 | using ProfileCount = Function::ProfileCount; | |||
73 | ||||
74 | #define DEBUG_TYPE"code-extractor" "code-extractor" | |||
75 | ||||
76 | // Provide a command-line option to aggregate function arguments into a struct | |||
77 | // for functions produced by the code extractor. This is useful when converting | |||
78 | // extracted functions to pthread-based code, as only one argument (void*) can | |||
79 | // be passed in to pthread_create(). | |||
80 | static cl::opt<bool> | |||
81 | AggregateArgsOpt("aggregate-extracted-args", cl::Hidden, | |||
82 | cl::desc("Aggregate arguments to code-extracted functions")); | |||
83 | ||||
84 | /// Test whether a block is valid for extraction. | |||
85 | static bool isBlockValidForExtraction(const BasicBlock &BB, | |||
86 | const SetVector<BasicBlock *> &Result, | |||
87 | bool AllowVarArgs, bool AllowAlloca) { | |||
88 | // taking the address of a basic block moved to another function is illegal | |||
89 | if (BB.hasAddressTaken()) | |||
90 | return false; | |||
91 | ||||
92 | // don't hoist code that uses another basicblock address, as it's likely to | |||
93 | // lead to unexpected behavior, like cross-function jumps | |||
94 | SmallPtrSet<User const *, 16> Visited; | |||
95 | SmallVector<User const *, 16> ToVisit; | |||
96 | ||||
97 | for (Instruction const &Inst : BB) | |||
98 | ToVisit.push_back(&Inst); | |||
99 | ||||
100 | while (!ToVisit.empty()) { | |||
101 | User const *Curr = ToVisit.pop_back_val(); | |||
102 | if (!Visited.insert(Curr).second) | |||
103 | continue; | |||
104 | if (isa<BlockAddress const>(Curr)) | |||
105 | return false; // even a reference to self is likely to be not compatible | |||
106 | ||||
107 | if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB) | |||
108 | continue; | |||
109 | ||||
110 | for (auto const &U : Curr->operands()) { | |||
111 | if (auto *UU = dyn_cast<User>(U)) | |||
112 | ToVisit.push_back(UU); | |||
113 | } | |||
114 | } | |||
115 | ||||
116 | // If explicitly requested, allow vastart and alloca. For invoke instructions | |||
117 | // verify that extraction is valid. | |||
118 | for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) { | |||
119 | if (isa<AllocaInst>(I)) { | |||
120 | if (!AllowAlloca) | |||
121 | return false; | |||
122 | continue; | |||
123 | } | |||
124 | ||||
125 | if (const auto *II = dyn_cast<InvokeInst>(I)) { | |||
126 | // Unwind destination (either a landingpad, catchswitch, or cleanuppad) | |||
127 | // must be a part of the subgraph which is being extracted. | |||
128 | if (auto *UBB = II->getUnwindDest()) | |||
129 | if (!Result.count(UBB)) | |||
130 | return false; | |||
131 | continue; | |||
132 | } | |||
133 | ||||
134 | // All catch handlers of a catchswitch instruction as well as the unwind | |||
135 | // destination must be in the subgraph. | |||
136 | if (const auto *CSI = dyn_cast<CatchSwitchInst>(I)) { | |||
137 | if (auto *UBB = CSI->getUnwindDest()) | |||
138 | if (!Result.count(UBB)) | |||
139 | return false; | |||
140 | for (auto *HBB : CSI->handlers()) | |||
141 | if (!Result.count(const_cast<BasicBlock*>(HBB))) | |||
142 | return false; | |||
143 | continue; | |||
144 | } | |||
145 | ||||
146 | // Make sure that entire catch handler is within subgraph. It is sufficient | |||
147 | // to check that catch return's block is in the list. | |||
148 | if (const auto *CPI = dyn_cast<CatchPadInst>(I)) { | |||
149 | for (const auto *U : CPI->users()) | |||
150 | if (const auto *CRI = dyn_cast<CatchReturnInst>(U)) | |||
151 | if (!Result.count(const_cast<BasicBlock*>(CRI->getParent()))) | |||
152 | return false; | |||
153 | continue; | |||
154 | } | |||
155 | ||||
156 | // And do similar checks for cleanup handler - the entire handler must be | |||
157 | // in subgraph which is going to be extracted. For cleanup return should | |||
158 | // additionally check that the unwind destination is also in the subgraph. | |||
159 | if (const auto *CPI = dyn_cast<CleanupPadInst>(I)) { | |||
160 | for (const auto *U : CPI->users()) | |||
161 | if (const auto *CRI = dyn_cast<CleanupReturnInst>(U)) | |||
162 | if (!Result.count(const_cast<BasicBlock*>(CRI->getParent()))) | |||
163 | return false; | |||
164 | continue; | |||
165 | } | |||
166 | if (const auto *CRI = dyn_cast<CleanupReturnInst>(I)) { | |||
167 | if (auto *UBB = CRI->getUnwindDest()) | |||
168 | if (!Result.count(UBB)) | |||
169 | return false; | |||
170 | continue; | |||
171 | } | |||
172 | ||||
173 | if (const CallInst *CI = dyn_cast<CallInst>(I)) { | |||
174 | if (const Function *F = CI->getCalledFunction()) { | |||
175 | auto IID = F->getIntrinsicID(); | |||
176 | if (IID == Intrinsic::vastart) { | |||
177 | if (AllowVarArgs) | |||
178 | continue; | |||
179 | else | |||
180 | return false; | |||
181 | } | |||
182 | ||||
183 | // Currently, we miscompile outlined copies of eh_typid_for. There are | |||
184 | // proposals for fixing this in llvm.org/PR39545. | |||
185 | if (IID == Intrinsic::eh_typeid_for) | |||
186 | return false; | |||
187 | } | |||
188 | } | |||
189 | } | |||
190 | ||||
191 | return true; | |||
192 | } | |||
193 | ||||
194 | /// Build a set of blocks to extract if the input blocks are viable. | |||
195 | static SetVector<BasicBlock *> | |||
196 | buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, | |||
197 | bool AllowVarArgs, bool AllowAlloca) { | |||
198 | assert(!BBs.empty() && "The set of blocks to extract must be non-empty")((!BBs.empty() && "The set of blocks to extract must be non-empty" ) ? static_cast<void> (0) : __assert_fail ("!BBs.empty() && \"The set of blocks to extract must be non-empty\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 198, __PRETTY_FUNCTION__)); | |||
199 | SetVector<BasicBlock *> Result; | |||
200 | ||||
201 | // Loop over the blocks, adding them to our set-vector, and aborting with an | |||
202 | // empty set if we encounter invalid blocks. | |||
203 | for (BasicBlock *BB : BBs) { | |||
204 | // If this block is dead, don't process it. | |||
205 | if (DT && !DT->isReachableFromEntry(BB)) | |||
206 | continue; | |||
207 | ||||
208 | if (!Result.insert(BB)) | |||
209 | llvm_unreachable("Repeated basic blocks in extraction input")::llvm::llvm_unreachable_internal("Repeated basic blocks in extraction input" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 209); | |||
210 | } | |||
211 | ||||
212 | LLVM_DEBUG(dbgs() << "Region front block: " << Result.front()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "Region front block: " << Result.front()->getName() << '\n'; } } while (false ) | |||
213 | << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "Region front block: " << Result.front()->getName() << '\n'; } } while (false ); | |||
214 | ||||
215 | for (auto *BB : Result) { | |||
216 | if (!isBlockValidForExtraction(*BB, Result, AllowVarArgs, AllowAlloca)) | |||
217 | return {}; | |||
218 | ||||
219 | // Make sure that the first block is not a landing pad. | |||
220 | if (BB == Result.front()) { | |||
221 | if (BB->isEHPad()) { | |||
222 | LLVM_DEBUG(dbgs() << "The first block cannot be an unwind block\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "The first block cannot be an unwind block\n" ; } } while (false); | |||
223 | return {}; | |||
224 | } | |||
225 | continue; | |||
226 | } | |||
227 | ||||
228 | // All blocks other than the first must not have predecessors outside of | |||
229 | // the subgraph which is being extracted. | |||
230 | for (auto *PBB : predecessors(BB)) | |||
231 | if (!Result.count(PBB)) { | |||
232 | LLVM_DEBUG(dbgs() << "No blocks in this region may have entries from "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "No blocks in this region may have entries from " "outside the region except for the first block!\n" << "Problematic source BB: " << BB->getName() << "\n" << "Problematic destination BB: " << PBB->getName() << "\n"; } } while (false) | |||
233 | "outside the region except for the first block!\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "No blocks in this region may have entries from " "outside the region except for the first block!\n" << "Problematic source BB: " << BB->getName() << "\n" << "Problematic destination BB: " << PBB->getName() << "\n"; } } while (false) | |||
234 | << "Problematic source BB: " << BB->getName() << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "No blocks in this region may have entries from " "outside the region except for the first block!\n" << "Problematic source BB: " << BB->getName() << "\n" << "Problematic destination BB: " << PBB->getName() << "\n"; } } while (false) | |||
235 | << "Problematic destination BB: " << PBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "No blocks in this region may have entries from " "outside the region except for the first block!\n" << "Problematic source BB: " << BB->getName() << "\n" << "Problematic destination BB: " << PBB->getName() << "\n"; } } while (false) | |||
236 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "No blocks in this region may have entries from " "outside the region except for the first block!\n" << "Problematic source BB: " << BB->getName() << "\n" << "Problematic destination BB: " << PBB->getName() << "\n"; } } while (false); | |||
237 | return {}; | |||
238 | } | |||
239 | } | |||
240 | ||||
241 | return Result; | |||
242 | } | |||
243 | ||||
244 | CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, | |||
245 | bool AggregateArgs, BlockFrequencyInfo *BFI, | |||
246 | BranchProbabilityInfo *BPI, AssumptionCache *AC, | |||
247 | bool AllowVarArgs, bool AllowAlloca, | |||
248 | std::string Suffix) | |||
249 | : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI), | |||
250 | BPI(BPI), AC(AC), AllowVarArgs(AllowVarArgs), | |||
251 | Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs, AllowAlloca)), | |||
252 | Suffix(Suffix) {} | |||
253 | ||||
254 | CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs, | |||
255 | BlockFrequencyInfo *BFI, | |||
256 | BranchProbabilityInfo *BPI, AssumptionCache *AC, | |||
257 | std::string Suffix) | |||
258 | : DT(&DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI), | |||
259 | BPI(BPI), AC(AC), AllowVarArgs(false), | |||
260 | Blocks(buildExtractionBlockSet(L.getBlocks(), &DT, | |||
261 | /* AllowVarArgs */ false, | |||
262 | /* AllowAlloca */ false)), | |||
263 | Suffix(Suffix) {} | |||
264 | ||||
265 | /// definedInRegion - Return true if the specified value is defined in the | |||
266 | /// extracted region. | |||
267 | static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) { | |||
268 | if (Instruction *I = dyn_cast<Instruction>(V)) | |||
269 | if (Blocks.count(I->getParent())) | |||
270 | return true; | |||
271 | return false; | |||
272 | } | |||
273 | ||||
274 | /// definedInCaller - Return true if the specified value is defined in the | |||
275 | /// function being code extracted, but not in the region being extracted. | |||
276 | /// These values must be passed in as live-ins to the function. | |||
277 | static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) { | |||
278 | if (isa<Argument>(V)) return true; | |||
279 | if (Instruction *I = dyn_cast<Instruction>(V)) | |||
280 | if (!Blocks.count(I->getParent())) | |||
281 | return true; | |||
282 | return false; | |||
283 | } | |||
284 | ||||
285 | static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) { | |||
286 | BasicBlock *CommonExitBlock = nullptr; | |||
287 | auto hasNonCommonExitSucc = [&](BasicBlock *Block) { | |||
288 | for (auto *Succ : successors(Block)) { | |||
289 | // Internal edges, ok. | |||
290 | if (Blocks.count(Succ)) | |||
291 | continue; | |||
292 | if (!CommonExitBlock) { | |||
293 | CommonExitBlock = Succ; | |||
294 | continue; | |||
295 | } | |||
296 | if (CommonExitBlock == Succ) | |||
297 | continue; | |||
298 | ||||
299 | return true; | |||
300 | } | |||
301 | return false; | |||
302 | }; | |||
303 | ||||
304 | if (any_of(Blocks, hasNonCommonExitSucc)) | |||
305 | return nullptr; | |||
306 | ||||
307 | return CommonExitBlock; | |||
308 | } | |||
309 | ||||
310 | bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers( | |||
311 | Instruction *Addr) const { | |||
312 | AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets()); | |||
313 | Function *Func = (*Blocks.begin())->getParent(); | |||
314 | for (BasicBlock &BB : *Func) { | |||
315 | if (Blocks.count(&BB)) | |||
316 | continue; | |||
317 | for (Instruction &II : BB) { | |||
318 | if (isa<DbgInfoIntrinsic>(II)) | |||
319 | continue; | |||
320 | ||||
321 | unsigned Opcode = II.getOpcode(); | |||
322 | Value *MemAddr = nullptr; | |||
323 | switch (Opcode) { | |||
324 | case Instruction::Store: | |||
325 | case Instruction::Load: { | |||
326 | if (Opcode == Instruction::Store) { | |||
327 | StoreInst *SI = cast<StoreInst>(&II); | |||
328 | MemAddr = SI->getPointerOperand(); | |||
329 | } else { | |||
330 | LoadInst *LI = cast<LoadInst>(&II); | |||
331 | MemAddr = LI->getPointerOperand(); | |||
332 | } | |||
333 | // Global variable can not be aliased with locals. | |||
334 | if (dyn_cast<Constant>(MemAddr)) | |||
335 | break; | |||
336 | Value *Base = MemAddr->stripInBoundsConstantOffsets(); | |||
337 | if (!isa<AllocaInst>(Base) || Base == AI) | |||
338 | return false; | |||
339 | break; | |||
340 | } | |||
341 | default: { | |||
342 | IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II); | |||
343 | if (IntrInst) { | |||
344 | if (IntrInst->isLifetimeStartOrEnd()) | |||
345 | break; | |||
346 | return false; | |||
347 | } | |||
348 | // Treat all the other cases conservatively if it has side effects. | |||
349 | if (II.mayHaveSideEffects()) | |||
350 | return false; | |||
351 | } | |||
352 | } | |||
353 | } | |||
354 | } | |||
355 | ||||
356 | return true; | |||
357 | } | |||
358 | ||||
359 | BasicBlock * | |||
360 | CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) { | |||
361 | BasicBlock *SinglePredFromOutlineRegion = nullptr; | |||
362 | assert(!Blocks.count(CommonExitBlock) &&((!Blocks.count(CommonExitBlock) && "Expect a block outside the region!" ) ? static_cast<void> (0) : __assert_fail ("!Blocks.count(CommonExitBlock) && \"Expect a block outside the region!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 363, __PRETTY_FUNCTION__)) | |||
363 | "Expect a block outside the region!")((!Blocks.count(CommonExitBlock) && "Expect a block outside the region!" ) ? static_cast<void> (0) : __assert_fail ("!Blocks.count(CommonExitBlock) && \"Expect a block outside the region!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 363, __PRETTY_FUNCTION__)); | |||
364 | for (auto *Pred : predecessors(CommonExitBlock)) { | |||
365 | if (!Blocks.count(Pred)) | |||
366 | continue; | |||
367 | if (!SinglePredFromOutlineRegion) { | |||
368 | SinglePredFromOutlineRegion = Pred; | |||
369 | } else if (SinglePredFromOutlineRegion != Pred) { | |||
370 | SinglePredFromOutlineRegion = nullptr; | |||
371 | break; | |||
372 | } | |||
373 | } | |||
374 | ||||
375 | if (SinglePredFromOutlineRegion) | |||
376 | return SinglePredFromOutlineRegion; | |||
377 | ||||
378 | #ifndef NDEBUG | |||
379 | auto getFirstPHI = [](BasicBlock *BB) { | |||
380 | BasicBlock::iterator I = BB->begin(); | |||
381 | PHINode *FirstPhi = nullptr; | |||
382 | while (I != BB->end()) { | |||
383 | PHINode *Phi = dyn_cast<PHINode>(I); | |||
384 | if (!Phi) | |||
385 | break; | |||
386 | if (!FirstPhi) { | |||
387 | FirstPhi = Phi; | |||
388 | break; | |||
389 | } | |||
390 | } | |||
391 | return FirstPhi; | |||
392 | }; | |||
393 | // If there are any phi nodes, the single pred either exists or has already | |||
394 | // be created before code extraction. | |||
395 | assert(!getFirstPHI(CommonExitBlock) && "Phi not expected")((!getFirstPHI(CommonExitBlock) && "Phi not expected" ) ? static_cast<void> (0) : __assert_fail ("!getFirstPHI(CommonExitBlock) && \"Phi not expected\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 395, __PRETTY_FUNCTION__)); | |||
396 | #endif | |||
397 | ||||
398 | BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock( | |||
399 | CommonExitBlock->getFirstNonPHI()->getIterator()); | |||
400 | ||||
401 | for (auto PI = pred_begin(CommonExitBlock), PE = pred_end(CommonExitBlock); | |||
402 | PI != PE;) { | |||
403 | BasicBlock *Pred = *PI++; | |||
404 | if (Blocks.count(Pred)) | |||
405 | continue; | |||
406 | Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock); | |||
407 | } | |||
408 | // Now add the old exit block to the outline region. | |||
409 | Blocks.insert(CommonExitBlock); | |||
410 | return CommonExitBlock; | |||
411 | } | |||
412 | ||||
413 | void CodeExtractor::findAllocas(ValueSet &SinkCands, ValueSet &HoistCands, | |||
414 | BasicBlock *&ExitBlock) const { | |||
415 | Function *Func = (*Blocks.begin())->getParent(); | |||
416 | ExitBlock = getCommonExitBlock(Blocks); | |||
417 | ||||
418 | for (BasicBlock &BB : *Func) { | |||
419 | if (Blocks.count(&BB)) | |||
420 | continue; | |||
421 | for (Instruction &II : BB) { | |||
422 | auto *AI = dyn_cast<AllocaInst>(&II); | |||
423 | if (!AI) | |||
424 | continue; | |||
425 | ||||
426 | // Find the pair of life time markers for address 'Addr' that are either | |||
427 | // defined inside the outline region or can legally be shrinkwrapped into | |||
428 | // the outline region. If there are not other untracked uses of the | |||
429 | // address, return the pair of markers if found; otherwise return a pair | |||
430 | // of nullptr. | |||
431 | auto GetLifeTimeMarkers = | |||
432 | [&](Instruction *Addr, bool &SinkLifeStart, | |||
433 | bool &HoistLifeEnd) -> std::pair<Instruction *, Instruction *> { | |||
434 | Instruction *LifeStart = nullptr, *LifeEnd = nullptr; | |||
435 | ||||
436 | for (User *U : Addr->users()) { | |||
437 | IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U); | |||
438 | if (IntrInst) { | |||
439 | if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) { | |||
440 | // Do not handle the case where AI has multiple start markers. | |||
441 | if (LifeStart) | |||
442 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
443 | LifeStart = IntrInst; | |||
444 | } | |||
445 | if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) { | |||
446 | if (LifeEnd) | |||
447 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
448 | LifeEnd = IntrInst; | |||
449 | } | |||
450 | continue; | |||
451 | } | |||
452 | // Find untracked uses of the address, bail. | |||
453 | if (!definedInRegion(Blocks, U)) | |||
454 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
455 | } | |||
456 | ||||
457 | if (!LifeStart || !LifeEnd) | |||
458 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
459 | ||||
460 | SinkLifeStart = !definedInRegion(Blocks, LifeStart); | |||
461 | HoistLifeEnd = !definedInRegion(Blocks, LifeEnd); | |||
462 | // Do legality Check. | |||
463 | if ((SinkLifeStart || HoistLifeEnd) && | |||
464 | !isLegalToShrinkwrapLifetimeMarkers(Addr)) | |||
465 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
466 | ||||
467 | // Check to see if we have a place to do hoisting, if not, bail. | |||
468 | if (HoistLifeEnd && !ExitBlock) | |||
469 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
470 | ||||
471 | return std::make_pair(LifeStart, LifeEnd); | |||
472 | }; | |||
473 | ||||
474 | bool SinkLifeStart = false, HoistLifeEnd = false; | |||
475 | auto Markers = GetLifeTimeMarkers(AI, SinkLifeStart, HoistLifeEnd); | |||
476 | ||||
477 | if (Markers.first) { | |||
478 | if (SinkLifeStart) | |||
479 | SinkCands.insert(Markers.first); | |||
480 | SinkCands.insert(AI); | |||
481 | if (HoistLifeEnd) | |||
482 | HoistCands.insert(Markers.second); | |||
483 | continue; | |||
484 | } | |||
485 | ||||
486 | // Follow the bitcast. | |||
487 | Instruction *MarkerAddr = nullptr; | |||
488 | for (User *U : AI->users()) { | |||
489 | if (U->stripInBoundsConstantOffsets() == AI) { | |||
490 | SinkLifeStart = false; | |||
491 | HoistLifeEnd = false; | |||
492 | Instruction *Bitcast = cast<Instruction>(U); | |||
493 | Markers = GetLifeTimeMarkers(Bitcast, SinkLifeStart, HoistLifeEnd); | |||
494 | if (Markers.first) { | |||
495 | MarkerAddr = Bitcast; | |||
496 | continue; | |||
497 | } | |||
498 | } | |||
499 | ||||
500 | // Found unknown use of AI. | |||
501 | if (!definedInRegion(Blocks, U)) { | |||
502 | MarkerAddr = nullptr; | |||
503 | break; | |||
504 | } | |||
505 | } | |||
506 | ||||
507 | if (MarkerAddr) { | |||
508 | if (SinkLifeStart) | |||
509 | SinkCands.insert(Markers.first); | |||
510 | if (!definedInRegion(Blocks, MarkerAddr)) | |||
511 | SinkCands.insert(MarkerAddr); | |||
512 | SinkCands.insert(AI); | |||
513 | if (HoistLifeEnd) | |||
514 | HoistCands.insert(Markers.second); | |||
515 | } | |||
516 | } | |||
517 | } | |||
518 | } | |||
519 | ||||
520 | void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, | |||
521 | const ValueSet &SinkCands) const { | |||
522 | for (BasicBlock *BB : Blocks) { | |||
523 | // If a used value is defined outside the region, it's an input. If an | |||
524 | // instruction is used outside the region, it's an output. | |||
525 | for (Instruction &II : *BB) { | |||
526 | for (User::op_iterator OI = II.op_begin(), OE = II.op_end(); OI != OE; | |||
527 | ++OI) { | |||
528 | Value *V = *OI; | |||
529 | if (!SinkCands.count(V) && definedInCaller(Blocks, V)) | |||
530 | Inputs.insert(V); | |||
531 | } | |||
532 | ||||
533 | for (User *U : II.users()) | |||
534 | if (!definedInRegion(Blocks, U)) { | |||
535 | Outputs.insert(&II); | |||
536 | break; | |||
537 | } | |||
538 | } | |||
539 | } | |||
540 | } | |||
541 | ||||
542 | /// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside | |||
543 | /// of the region, we need to split the entry block of the region so that the | |||
544 | /// PHI node is easier to deal with. | |||
545 | void CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) { | |||
546 | unsigned NumPredsFromRegion = 0; | |||
547 | unsigned NumPredsOutsideRegion = 0; | |||
548 | ||||
549 | if (Header != &Header->getParent()->getEntryBlock()) { | |||
550 | PHINode *PN = dyn_cast<PHINode>(Header->begin()); | |||
551 | if (!PN) return; // No PHI nodes. | |||
552 | ||||
553 | // If the header node contains any PHI nodes, check to see if there is more | |||
554 | // than one entry from outside the region. If so, we need to sever the | |||
555 | // header block into two. | |||
556 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |||
557 | if (Blocks.count(PN->getIncomingBlock(i))) | |||
558 | ++NumPredsFromRegion; | |||
559 | else | |||
560 | ++NumPredsOutsideRegion; | |||
561 | ||||
562 | // If there is one (or fewer) predecessor from outside the region, we don't | |||
563 | // need to do anything special. | |||
564 | if (NumPredsOutsideRegion <= 1) return; | |||
565 | } | |||
566 | ||||
567 | // Otherwise, we need to split the header block into two pieces: one | |||
568 | // containing PHI nodes merging values from outside of the region, and a | |||
569 | // second that contains all of the code for the block and merges back any | |||
570 | // incoming values from inside of the region. | |||
571 | BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT); | |||
572 | ||||
573 | // We only want to code extract the second block now, and it becomes the new | |||
574 | // header of the region. | |||
575 | BasicBlock *OldPred = Header; | |||
576 | Blocks.remove(OldPred); | |||
577 | Blocks.insert(NewBB); | |||
578 | Header = NewBB; | |||
579 | ||||
580 | // Okay, now we need to adjust the PHI nodes and any branches from within the | |||
581 | // region to go to the new header block instead of the old header block. | |||
582 | if (NumPredsFromRegion) { | |||
583 | PHINode *PN = cast<PHINode>(OldPred->begin()); | |||
584 | // Loop over all of the predecessors of OldPred that are in the region, | |||
585 | // changing them to branch to NewBB instead. | |||
586 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |||
587 | if (Blocks.count(PN->getIncomingBlock(i))) { | |||
588 | Instruction *TI = PN->getIncomingBlock(i)->getTerminator(); | |||
589 | TI->replaceUsesOfWith(OldPred, NewBB); | |||
590 | } | |||
591 | ||||
592 | // Okay, everything within the region is now branching to the right block, we | |||
593 | // just have to update the PHI nodes now, inserting PHI nodes into NewBB. | |||
594 | BasicBlock::iterator AfterPHIs; | |||
595 | for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) { | |||
596 | PHINode *PN = cast<PHINode>(AfterPHIs); | |||
597 | // Create a new PHI node in the new region, which has an incoming value | |||
598 | // from OldPred of PN. | |||
599 | PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion, | |||
600 | PN->getName() + ".ce", &NewBB->front()); | |||
601 | PN->replaceAllUsesWith(NewPN); | |||
602 | NewPN->addIncoming(PN, OldPred); | |||
603 | ||||
604 | // Loop over all of the incoming value in PN, moving them to NewPN if they | |||
605 | // are from the extracted region. | |||
606 | for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { | |||
607 | if (Blocks.count(PN->getIncomingBlock(i))) { | |||
608 | NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); | |||
609 | PN->removeIncomingValue(i); | |||
610 | --i; | |||
611 | } | |||
612 | } | |||
613 | } | |||
614 | } | |||
615 | } | |||
616 | ||||
617 | /// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from | |||
618 | /// outlined region, we split these PHIs on two: one with inputs from region | |||
619 | /// and other with remaining incoming blocks; then first PHIs are placed in | |||
620 | /// outlined region. | |||
621 | void CodeExtractor::severSplitPHINodesOfExits( | |||
622 | const SmallPtrSetImpl<BasicBlock *> &Exits) { | |||
623 | for (BasicBlock *ExitBB : Exits) { | |||
624 | BasicBlock *NewBB = nullptr; | |||
625 | ||||
626 | for (PHINode &PN : ExitBB->phis()) { | |||
627 | // Find all incoming values from the outlining region. | |||
628 | SmallVector<unsigned, 2> IncomingVals; | |||
629 | for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i) | |||
630 | if (Blocks.count(PN.getIncomingBlock(i))) | |||
631 | IncomingVals.push_back(i); | |||
632 | ||||
633 | // Do not process PHI if there is one (or fewer) predecessor from region. | |||
634 | // If PHI has exactly one predecessor from region, only this one incoming | |||
635 | // will be replaced on codeRepl block, so it should be safe to skip PHI. | |||
636 | if (IncomingVals.size() <= 1) | |||
637 | continue; | |||
638 | ||||
639 | // Create block for new PHIs and add it to the list of outlined if it | |||
640 | // wasn't done before. | |||
641 | if (!NewBB) { | |||
642 | NewBB = BasicBlock::Create(ExitBB->getContext(), | |||
643 | ExitBB->getName() + ".split", | |||
644 | ExitBB->getParent(), ExitBB); | |||
645 | SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBB), | |||
646 | pred_end(ExitBB)); | |||
647 | for (BasicBlock *PredBB : Preds) | |||
648 | if (Blocks.count(PredBB)) | |||
649 | PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB); | |||
650 | BranchInst::Create(ExitBB, NewBB); | |||
651 | Blocks.insert(NewBB); | |||
652 | } | |||
653 | ||||
654 | // Split this PHI. | |||
655 | PHINode *NewPN = | |||
656 | PHINode::Create(PN.getType(), IncomingVals.size(), | |||
657 | PN.getName() + ".ce", NewBB->getFirstNonPHI()); | |||
658 | for (unsigned i : IncomingVals) | |||
659 | NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i)); | |||
660 | for (unsigned i : reverse(IncomingVals)) | |||
661 | PN.removeIncomingValue(i, false); | |||
662 | PN.addIncoming(NewPN, NewBB); | |||
663 | } | |||
664 | } | |||
665 | } | |||
666 | ||||
667 | void CodeExtractor::splitReturnBlocks() { | |||
668 | for (BasicBlock *Block : Blocks) | |||
669 | if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) { | |||
670 | BasicBlock *New = | |||
671 | Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret"); | |||
672 | if (DT) { | |||
673 | // Old dominates New. New node dominates all other nodes dominated | |||
674 | // by Old. | |||
675 | DomTreeNode *OldNode = DT->getNode(Block); | |||
676 | SmallVector<DomTreeNode *, 8> Children(OldNode->begin(), | |||
677 | OldNode->end()); | |||
678 | ||||
679 | DomTreeNode *NewNode = DT->addNewBlock(New, Block); | |||
680 | ||||
681 | for (DomTreeNode *I : Children) | |||
682 | DT->changeImmediateDominator(I, NewNode); | |||
683 | } | |||
684 | } | |||
685 | } | |||
686 | ||||
687 | /// constructFunction - make a function based on inputs and outputs, as follows: | |||
688 | /// f(in0, ..., inN, out0, ..., outN) | |||
689 | Function *CodeExtractor::constructFunction(const ValueSet &inputs, | |||
690 | const ValueSet &outputs, | |||
691 | BasicBlock *header, | |||
692 | BasicBlock *newRootNode, | |||
693 | BasicBlock *newHeader, | |||
694 | Function *oldFunction, | |||
695 | Module *M) { | |||
696 | LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "inputs: " << inputs .size() << "\n"; } } while (false); | |||
| ||||
697 | LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "outputs: " << outputs .size() << "\n"; } } while (false); | |||
698 | ||||
699 | // This function returns unsigned, outputs will go back by reference. | |||
700 | switch (NumExitBlocks) { | |||
701 | case 0: | |||
702 | case 1: RetTy = Type::getVoidTy(header->getContext()); break; | |||
703 | case 2: RetTy = Type::getInt1Ty(header->getContext()); break; | |||
704 | default: RetTy = Type::getInt16Ty(header->getContext()); break; | |||
705 | } | |||
706 | ||||
707 | std::vector<Type *> paramTy; | |||
708 | ||||
709 | // Add the types of the input values to the function's argument list | |||
710 | for (Value *value : inputs) { | |||
711 | LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "value used in func: " << *value << "\n"; } } while (false); | |||
712 | paramTy.push_back(value->getType()); | |||
713 | } | |||
714 | ||||
715 | // Add the types of the output values to the function's argument list. | |||
716 | for (Value *output : outputs) { | |||
717 | LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "instr used in func: " << *output << "\n"; } } while (false); | |||
718 | if (AggregateArgs) | |||
719 | paramTy.push_back(output->getType()); | |||
720 | else | |||
721 | paramTy.push_back(PointerType::getUnqual(output->getType())); | |||
722 | } | |||
723 | ||||
724 | LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { { dbgs() << "Function type: " << *RetTy << " f("; for (Type *i : paramTy) dbgs() << *i << ", "; dbgs() << ")\n"; }; } } while (false ) | |||
725 | dbgs() << "Function type: " << *RetTy << " f(";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { { dbgs() << "Function type: " << *RetTy << " f("; for (Type *i : paramTy) dbgs() << *i << ", "; dbgs() << ")\n"; }; } } while (false ) | |||
726 | for (Type *i : paramTy)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { { dbgs() << "Function type: " << *RetTy << " f("; for (Type *i : paramTy) dbgs() << *i << ", "; dbgs() << ")\n"; }; } } while (false ) | |||
727 | dbgs() << *i << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { { dbgs() << "Function type: " << *RetTy << " f("; for (Type *i : paramTy) dbgs() << *i << ", "; dbgs() << ")\n"; }; } } while (false ) | |||
728 | dbgs() << ")\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { { dbgs() << "Function type: " << *RetTy << " f("; for (Type *i : paramTy) dbgs() << *i << ", "; dbgs() << ")\n"; }; } } while (false ) | |||
729 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { { dbgs() << "Function type: " << *RetTy << " f("; for (Type *i : paramTy) dbgs() << *i << ", "; dbgs() << ")\n"; }; } } while (false ); | |||
730 | ||||
731 | StructType *StructTy; | |||
732 | if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { | |||
733 | StructTy = StructType::get(M->getContext(), paramTy); | |||
734 | paramTy.clear(); | |||
735 | paramTy.push_back(PointerType::getUnqual(StructTy)); | |||
736 | } | |||
737 | FunctionType *funcType = | |||
738 | FunctionType::get(RetTy, paramTy, | |||
739 | AllowVarArgs && oldFunction->isVarArg()); | |||
740 | ||||
741 | std::string SuffixToUse = | |||
742 | Suffix.empty() | |||
743 | ? (header->getName().empty() ? "extracted" : header->getName().str()) | |||
744 | : Suffix; | |||
745 | // Create the new function | |||
746 | Function *newFunction = Function::Create( | |||
747 | funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(), | |||
748 | oldFunction->getName() + "." + SuffixToUse, M); | |||
749 | // If the old function is no-throw, so is the new one. | |||
750 | if (oldFunction->doesNotThrow()) | |||
751 | newFunction->setDoesNotThrow(); | |||
752 | ||||
753 | // Inherit the uwtable attribute if we need to. | |||
754 | if (oldFunction->hasUWTable()) | |||
755 | newFunction->setHasUWTable(); | |||
756 | ||||
757 | // Inherit all of the target dependent attributes and white-listed | |||
758 | // target independent attributes. | |||
759 | // (e.g. If the extracted region contains a call to an x86.sse | |||
760 | // instruction we need to make sure that the extracted region has the | |||
761 | // "target-features" attribute allowing it to be lowered. | |||
762 | // FIXME: This should be changed to check to see if a specific | |||
763 | // attribute can not be inherited. | |||
764 | for (const auto &Attr : oldFunction->getAttributes().getFnAttributes()) { | |||
765 | if (Attr.isStringAttribute()) { | |||
766 | if (Attr.getKindAsString() == "thunk") | |||
767 | continue; | |||
768 | } else | |||
769 | switch (Attr.getKindAsEnum()) { | |||
770 | // Those attributes cannot be propagated safely. Explicitly list them | |||
771 | // here so we get a warning if new attributes are added. This list also | |||
772 | // includes non-function attributes. | |||
773 | case Attribute::Alignment: | |||
774 | case Attribute::AllocSize: | |||
775 | case Attribute::ArgMemOnly: | |||
776 | case Attribute::Builtin: | |||
777 | case Attribute::ByVal: | |||
778 | case Attribute::Convergent: | |||
779 | case Attribute::Dereferenceable: | |||
780 | case Attribute::DereferenceableOrNull: | |||
781 | case Attribute::InAlloca: | |||
782 | case Attribute::InReg: | |||
783 | case Attribute::InaccessibleMemOnly: | |||
784 | case Attribute::InaccessibleMemOrArgMemOnly: | |||
785 | case Attribute::JumpTable: | |||
786 | case Attribute::Naked: | |||
787 | case Attribute::Nest: | |||
788 | case Attribute::NoAlias: | |||
789 | case Attribute::NoBuiltin: | |||
790 | case Attribute::NoCapture: | |||
791 | case Attribute::NoReturn: | |||
792 | case Attribute::None: | |||
793 | case Attribute::NonNull: | |||
794 | case Attribute::ReadNone: | |||
795 | case Attribute::ReadOnly: | |||
796 | case Attribute::Returned: | |||
797 | case Attribute::ReturnsTwice: | |||
798 | case Attribute::SExt: | |||
799 | case Attribute::Speculatable: | |||
800 | case Attribute::StackAlignment: | |||
801 | case Attribute::StructRet: | |||
802 | case Attribute::SwiftError: | |||
803 | case Attribute::SwiftSelf: | |||
804 | case Attribute::WriteOnly: | |||
805 | case Attribute::ZExt: | |||
806 | case Attribute::ImmArg: | |||
807 | case Attribute::EndAttrKinds: | |||
808 | continue; | |||
809 | // Those attributes should be safe to propagate to the extracted function. | |||
810 | case Attribute::AlwaysInline: | |||
811 | case Attribute::Cold: | |||
812 | case Attribute::NoRecurse: | |||
813 | case Attribute::InlineHint: | |||
814 | case Attribute::MinSize: | |||
815 | case Attribute::NoDuplicate: | |||
816 | case Attribute::NoImplicitFloat: | |||
817 | case Attribute::NoInline: | |||
818 | case Attribute::NonLazyBind: | |||
819 | case Attribute::NoRedZone: | |||
820 | case Attribute::NoUnwind: | |||
821 | case Attribute::OptForFuzzing: | |||
822 | case Attribute::OptimizeNone: | |||
823 | case Attribute::OptimizeForSize: | |||
824 | case Attribute::SafeStack: | |||
825 | case Attribute::ShadowCallStack: | |||
826 | case Attribute::SanitizeAddress: | |||
827 | case Attribute::SanitizeMemory: | |||
828 | case Attribute::SanitizeThread: | |||
829 | case Attribute::SanitizeHWAddress: | |||
830 | case Attribute::SpeculativeLoadHardening: | |||
831 | case Attribute::StackProtect: | |||
832 | case Attribute::StackProtectReq: | |||
833 | case Attribute::StackProtectStrong: | |||
834 | case Attribute::StrictFP: | |||
835 | case Attribute::UWTable: | |||
836 | case Attribute::NoCfCheck: | |||
837 | break; | |||
838 | } | |||
839 | ||||
840 | newFunction->addFnAttr(Attr); | |||
841 | } | |||
842 | newFunction->getBasicBlockList().push_back(newRootNode); | |||
843 | ||||
844 | // Create an iterator to name all of the arguments we inserted. | |||
845 | Function::arg_iterator AI = newFunction->arg_begin(); | |||
846 | ||||
847 | // Rewrite all users of the inputs in the extracted region to use the | |||
848 | // arguments (or appropriate addressing into struct) instead. | |||
849 | for (unsigned i = 0, e = inputs.size(); i != e; ++i) { | |||
850 | Value *RewriteVal; | |||
851 | if (AggregateArgs) { | |||
852 | Value *Idx[2]; | |||
853 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext())); | |||
854 | Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i); | |||
855 | Instruction *TI = newFunction->begin()->getTerminator(); | |||
856 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
| ||||
857 | StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI); | |||
858 | RewriteVal = new LoadInst(StructTy->getElementType(i), GEP, | |||
859 | "loadgep_" + inputs[i]->getName(), TI); | |||
860 | } else | |||
861 | RewriteVal = &*AI++; | |||
862 | ||||
863 | std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end()); | |||
864 | for (User *use : Users) | |||
865 | if (Instruction *inst = dyn_cast<Instruction>(use)) | |||
866 | if (Blocks.count(inst->getParent())) | |||
867 | inst->replaceUsesOfWith(inputs[i], RewriteVal); | |||
868 | } | |||
869 | ||||
870 | // Set names for input and output arguments. | |||
871 | if (!AggregateArgs) { | |||
872 | AI = newFunction->arg_begin(); | |||
873 | for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI) | |||
874 | AI->setName(inputs[i]->getName()); | |||
875 | for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI) | |||
876 | AI->setName(outputs[i]->getName()+".out"); | |||
877 | } | |||
878 | ||||
879 | // Rewrite branches to basic blocks outside of the loop to new dummy blocks | |||
880 | // within the new function. This must be done before we lose track of which | |||
881 | // blocks were originally in the code region. | |||
882 | std::vector<User *> Users(header->user_begin(), header->user_end()); | |||
883 | for (unsigned i = 0, e = Users.size(); i != e; ++i) | |||
884 | // The BasicBlock which contains the branch is not in the region | |||
885 | // modify the branch target to a new block | |||
886 | if (Instruction *I = dyn_cast<Instruction>(Users[i])) | |||
887 | if (I->isTerminator() && !Blocks.count(I->getParent()) && | |||
888 | I->getParent()->getParent() == oldFunction) | |||
889 | I->replaceUsesOfWith(header, newHeader); | |||
890 | ||||
891 | return newFunction; | |||
892 | } | |||
893 | ||||
894 | /// Erase lifetime.start markers which reference inputs to the extraction | |||
895 | /// region, and insert the referenced memory into \p LifetimesStart. | |||
896 | /// | |||
897 | /// The extraction region is defined by a set of blocks (\p Blocks), and a set | |||
898 | /// of allocas which will be moved from the caller function into the extracted | |||
899 | /// function (\p SunkAllocas). | |||
900 | static void eraseLifetimeMarkersOnInputs(const SetVector<BasicBlock *> &Blocks, | |||
901 | const SetVector<Value *> &SunkAllocas, | |||
902 | SetVector<Value *> &LifetimesStart) { | |||
903 | for (BasicBlock *BB : Blocks) { | |||
904 | for (auto It = BB->begin(), End = BB->end(); It != End;) { | |||
905 | auto *II = dyn_cast<IntrinsicInst>(&*It); | |||
906 | ++It; | |||
907 | if (!II || !II->isLifetimeStartOrEnd()) | |||
908 | continue; | |||
909 | ||||
910 | // Get the memory operand of the lifetime marker. If the underlying | |||
911 | // object is a sunk alloca, or is otherwise defined in the extraction | |||
912 | // region, the lifetime marker must not be erased. | |||
913 | Value *Mem = II->getOperand(1)->stripInBoundsOffsets(); | |||
914 | if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem)) | |||
915 | continue; | |||
916 | ||||
917 | if (II->getIntrinsicID() == Intrinsic::lifetime_start) | |||
918 | LifetimesStart.insert(Mem); | |||
919 | II->eraseFromParent(); | |||
920 | } | |||
921 | } | |||
922 | } | |||
923 | ||||
924 | /// Insert lifetime start/end markers surrounding the call to the new function | |||
925 | /// for objects defined in the caller. | |||
926 | static void insertLifetimeMarkersSurroundingCall( | |||
927 | Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd, | |||
928 | CallInst *TheCall) { | |||
929 | LLVMContext &Ctx = M->getContext(); | |||
930 | auto Int8PtrTy = Type::getInt8PtrTy(Ctx); | |||
931 | auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1); | |||
932 | Instruction *Term = TheCall->getParent()->getTerminator(); | |||
933 | ||||
934 | // The memory argument to a lifetime marker must be a i8*. Cache any bitcasts | |||
935 | // needed to satisfy this requirement so they may be reused. | |||
936 | DenseMap<Value *, Value *> Bitcasts; | |||
937 | ||||
938 | // Emit lifetime markers for the pointers given in \p Objects. Insert the | |||
939 | // markers before the call if \p InsertBefore, and after the call otherwise. | |||
940 | auto insertMarkers = [&](Function *MarkerFunc, ArrayRef<Value *> Objects, | |||
941 | bool InsertBefore) { | |||
942 | for (Value *Mem : Objects) { | |||
943 | assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() ==(((!isa<Instruction>(Mem) || cast<Instruction>(Mem )->getFunction() == TheCall->getFunction()) && "Input memory not defined in original function" ) ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() == TheCall->getFunction()) && \"Input memory not defined in original function\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 945, __PRETTY_FUNCTION__)) | |||
944 | TheCall->getFunction()) &&(((!isa<Instruction>(Mem) || cast<Instruction>(Mem )->getFunction() == TheCall->getFunction()) && "Input memory not defined in original function" ) ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() == TheCall->getFunction()) && \"Input memory not defined in original function\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 945, __PRETTY_FUNCTION__)) | |||
945 | "Input memory not defined in original function")(((!isa<Instruction>(Mem) || cast<Instruction>(Mem )->getFunction() == TheCall->getFunction()) && "Input memory not defined in original function" ) ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() == TheCall->getFunction()) && \"Input memory not defined in original function\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 945, __PRETTY_FUNCTION__)); | |||
946 | Value *&MemAsI8Ptr = Bitcasts[Mem]; | |||
947 | if (!MemAsI8Ptr) { | |||
948 | if (Mem->getType() == Int8PtrTy) | |||
949 | MemAsI8Ptr = Mem; | |||
950 | else | |||
951 | MemAsI8Ptr = | |||
952 | CastInst::CreatePointerCast(Mem, Int8PtrTy, "lt.cast", TheCall); | |||
953 | } | |||
954 | ||||
955 | auto Marker = CallInst::Create(MarkerFunc, {NegativeOne, MemAsI8Ptr}); | |||
956 | if (InsertBefore) | |||
957 | Marker->insertBefore(TheCall); | |||
958 | else | |||
959 | Marker->insertBefore(Term); | |||
960 | } | |||
961 | }; | |||
962 | ||||
963 | if (!LifetimesStart.empty()) { | |||
964 | auto StartFn = llvm::Intrinsic::getDeclaration( | |||
965 | M, llvm::Intrinsic::lifetime_start, Int8PtrTy); | |||
966 | insertMarkers(StartFn, LifetimesStart, /*InsertBefore=*/true); | |||
967 | } | |||
968 | ||||
969 | if (!LifetimesEnd.empty()) { | |||
970 | auto EndFn = llvm::Intrinsic::getDeclaration( | |||
971 | M, llvm::Intrinsic::lifetime_end, Int8PtrTy); | |||
972 | insertMarkers(EndFn, LifetimesEnd, /*InsertBefore=*/false); | |||
973 | } | |||
974 | } | |||
975 | ||||
976 | /// emitCallAndSwitchStatement - This method sets up the caller side by adding | |||
977 | /// the call instruction, splitting any PHI nodes in the header block as | |||
978 | /// necessary. | |||
979 | CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction, | |||
980 | BasicBlock *codeReplacer, | |||
981 | ValueSet &inputs, | |||
982 | ValueSet &outputs) { | |||
983 | // Emit a call to the new function, passing in: *pointer to struct (if | |||
984 | // aggregating parameters), or plan inputs and allocated memory for outputs | |||
985 | std::vector<Value *> params, StructValues, ReloadOutputs, Reloads; | |||
986 | ||||
987 | Module *M = newFunction->getParent(); | |||
988 | LLVMContext &Context = M->getContext(); | |||
989 | const DataLayout &DL = M->getDataLayout(); | |||
990 | CallInst *call = nullptr; | |||
991 | ||||
992 | // Add inputs as params, or to be filled into the struct | |||
993 | unsigned ArgNo = 0; | |||
994 | SmallVector<unsigned, 1> SwiftErrorArgs; | |||
995 | for (Value *input : inputs) { | |||
996 | if (AggregateArgs) | |||
997 | StructValues.push_back(input); | |||
998 | else { | |||
999 | params.push_back(input); | |||
1000 | if (input->isSwiftError()) | |||
1001 | SwiftErrorArgs.push_back(ArgNo); | |||
1002 | } | |||
1003 | ++ArgNo; | |||
1004 | } | |||
1005 | ||||
1006 | // Create allocas for the outputs | |||
1007 | for (Value *output : outputs) { | |||
1008 | if (AggregateArgs) { | |||
1009 | StructValues.push_back(output); | |||
1010 | } else { | |||
1011 | AllocaInst *alloca = | |||
1012 | new AllocaInst(output->getType(), DL.getAllocaAddrSpace(), | |||
1013 | nullptr, output->getName() + ".loc", | |||
1014 | &codeReplacer->getParent()->front().front()); | |||
1015 | ReloadOutputs.push_back(alloca); | |||
1016 | params.push_back(alloca); | |||
1017 | } | |||
1018 | } | |||
1019 | ||||
1020 | StructType *StructArgTy = nullptr; | |||
1021 | AllocaInst *Struct = nullptr; | |||
1022 | if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { | |||
1023 | std::vector<Type *> ArgTypes; | |||
1024 | for (ValueSet::iterator v = StructValues.begin(), | |||
1025 | ve = StructValues.end(); v != ve; ++v) | |||
1026 | ArgTypes.push_back((*v)->getType()); | |||
1027 | ||||
1028 | // Allocate a struct at the beginning of this function | |||
1029 | StructArgTy = StructType::get(newFunction->getContext(), ArgTypes); | |||
1030 | Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr, | |||
1031 | "structArg", | |||
1032 | &codeReplacer->getParent()->front().front()); | |||
1033 | params.push_back(Struct); | |||
1034 | ||||
1035 | for (unsigned i = 0, e = inputs.size(); i != e; ++i) { | |||
1036 | Value *Idx[2]; | |||
1037 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); | |||
1038 | Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i); | |||
1039 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
1040 | StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName()); | |||
1041 | codeReplacer->getInstList().push_back(GEP); | |||
1042 | StoreInst *SI = new StoreInst(StructValues[i], GEP); | |||
1043 | codeReplacer->getInstList().push_back(SI); | |||
1044 | } | |||
1045 | } | |||
1046 | ||||
1047 | // Emit the call to the function | |||
1048 | call = CallInst::Create(newFunction, params, | |||
1049 | NumExitBlocks > 1 ? "targetBlock" : ""); | |||
1050 | // Add debug location to the new call, if the original function has debug | |||
1051 | // info. In that case, the terminator of the entry block of the extracted | |||
1052 | // function contains the first debug location of the extracted function, | |||
1053 | // set in extractCodeRegion. | |||
1054 | if (codeReplacer->getParent()->getSubprogram()) { | |||
1055 | if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc()) | |||
1056 | call->setDebugLoc(DL); | |||
1057 | } | |||
1058 | codeReplacer->getInstList().push_back(call); | |||
1059 | ||||
1060 | // Set swifterror parameter attributes. | |||
1061 | for (unsigned SwiftErrArgNo : SwiftErrorArgs) { | |||
1062 | call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError); | |||
1063 | newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError); | |||
1064 | } | |||
1065 | ||||
1066 | Function::arg_iterator OutputArgBegin = newFunction->arg_begin(); | |||
1067 | unsigned FirstOut = inputs.size(); | |||
1068 | if (!AggregateArgs) | |||
1069 | std::advance(OutputArgBegin, inputs.size()); | |||
1070 | ||||
1071 | // Reload the outputs passed in by reference. | |||
1072 | for (unsigned i = 0, e = outputs.size(); i != e; ++i) { | |||
1073 | Value *Output = nullptr; | |||
1074 | if (AggregateArgs) { | |||
1075 | Value *Idx[2]; | |||
1076 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); | |||
1077 | Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); | |||
1078 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
1079 | StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName()); | |||
1080 | codeReplacer->getInstList().push_back(GEP); | |||
1081 | Output = GEP; | |||
1082 | } else { | |||
1083 | Output = ReloadOutputs[i]; | |||
1084 | } | |||
1085 | LoadInst *load = new LoadInst(outputs[i]->getType(), Output, | |||
1086 | outputs[i]->getName() + ".reload"); | |||
1087 | Reloads.push_back(load); | |||
1088 | codeReplacer->getInstList().push_back(load); | |||
1089 | std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end()); | |||
1090 | for (unsigned u = 0, e = Users.size(); u != e; ++u) { | |||
1091 | Instruction *inst = cast<Instruction>(Users[u]); | |||
1092 | if (!Blocks.count(inst->getParent())) | |||
1093 | inst->replaceUsesOfWith(outputs[i], load); | |||
1094 | } | |||
1095 | } | |||
1096 | ||||
1097 | // Now we can emit a switch statement using the call as a value. | |||
1098 | SwitchInst *TheSwitch = | |||
1099 | SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)), | |||
1100 | codeReplacer, 0, codeReplacer); | |||
1101 | ||||
1102 | // Since there may be multiple exits from the original region, make the new | |||
1103 | // function return an unsigned, switch on that number. This loop iterates | |||
1104 | // over all of the blocks in the extracted region, updating any terminator | |||
1105 | // instructions in the to-be-extracted region that branch to blocks that are | |||
1106 | // not in the region to be extracted. | |||
1107 | std::map<BasicBlock *, BasicBlock *> ExitBlockMap; | |||
1108 | ||||
1109 | unsigned switchVal = 0; | |||
1110 | for (BasicBlock *Block : Blocks) { | |||
1111 | Instruction *TI = Block->getTerminator(); | |||
1112 | for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) | |||
1113 | if (!Blocks.count(TI->getSuccessor(i))) { | |||
1114 | BasicBlock *OldTarget = TI->getSuccessor(i); | |||
1115 | // add a new basic block which returns the appropriate value | |||
1116 | BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; | |||
1117 | if (!NewTarget) { | |||
1118 | // If we don't already have an exit stub for this non-extracted | |||
1119 | // destination, create one now! | |||
1120 | NewTarget = BasicBlock::Create(Context, | |||
1121 | OldTarget->getName() + ".exitStub", | |||
1122 | newFunction); | |||
1123 | unsigned SuccNum = switchVal++; | |||
1124 | ||||
1125 | Value *brVal = nullptr; | |||
1126 | switch (NumExitBlocks) { | |||
1127 | case 0: | |||
1128 | case 1: break; // No value needed. | |||
1129 | case 2: // Conditional branch, return a bool | |||
1130 | brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum); | |||
1131 | break; | |||
1132 | default: | |||
1133 | brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum); | |||
1134 | break; | |||
1135 | } | |||
1136 | ||||
1137 | ReturnInst::Create(Context, brVal, NewTarget); | |||
1138 | ||||
1139 | // Update the switch instruction. | |||
1140 | TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context), | |||
1141 | SuccNum), | |||
1142 | OldTarget); | |||
1143 | } | |||
1144 | ||||
1145 | // rewrite the original branch instruction with this new target | |||
1146 | TI->setSuccessor(i, NewTarget); | |||
1147 | } | |||
1148 | } | |||
1149 | ||||
1150 | // Store the arguments right after the definition of output value. | |||
1151 | // This should be proceeded after creating exit stubs to be ensure that invoke | |||
1152 | // result restore will be placed in the outlined function. | |||
1153 | Function::arg_iterator OAI = OutputArgBegin; | |||
1154 | for (unsigned i = 0, e = outputs.size(); i != e; ++i) { | |||
1155 | auto *OutI = dyn_cast<Instruction>(outputs[i]); | |||
1156 | if (!OutI) | |||
1157 | continue; | |||
1158 | ||||
1159 | // Find proper insertion point. | |||
1160 | BasicBlock::iterator InsertPt; | |||
1161 | // In case OutI is an invoke, we insert the store at the beginning in the | |||
1162 | // 'normal destination' BB. Otherwise we insert the store right after OutI. | |||
1163 | if (auto *InvokeI = dyn_cast<InvokeInst>(OutI)) | |||
1164 | InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt(); | |||
1165 | else if (auto *Phi = dyn_cast<PHINode>(OutI)) | |||
1166 | InsertPt = Phi->getParent()->getFirstInsertionPt(); | |||
1167 | else | |||
1168 | InsertPt = std::next(OutI->getIterator()); | |||
1169 | ||||
1170 | Instruction *InsertBefore = &*InsertPt; | |||
1171 | assert((InsertBefore->getFunction() == newFunction ||(((InsertBefore->getFunction() == newFunction || Blocks.count (InsertBefore->getParent())) && "InsertPt should be in new function" ) ? static_cast<void> (0) : __assert_fail ("(InsertBefore->getFunction() == newFunction || Blocks.count(InsertBefore->getParent())) && \"InsertPt should be in new function\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 1173, __PRETTY_FUNCTION__)) | |||
1172 | Blocks.count(InsertBefore->getParent())) &&(((InsertBefore->getFunction() == newFunction || Blocks.count (InsertBefore->getParent())) && "InsertPt should be in new function" ) ? static_cast<void> (0) : __assert_fail ("(InsertBefore->getFunction() == newFunction || Blocks.count(InsertBefore->getParent())) && \"InsertPt should be in new function\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 1173, __PRETTY_FUNCTION__)) | |||
1173 | "InsertPt should be in new function")(((InsertBefore->getFunction() == newFunction || Blocks.count (InsertBefore->getParent())) && "InsertPt should be in new function" ) ? static_cast<void> (0) : __assert_fail ("(InsertBefore->getFunction() == newFunction || Blocks.count(InsertBefore->getParent())) && \"InsertPt should be in new function\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 1173, __PRETTY_FUNCTION__)); | |||
1174 | assert(OAI != newFunction->arg_end() &&((OAI != newFunction->arg_end() && "Number of output arguments should match " "the amount of defined values") ? static_cast<void> (0 ) : __assert_fail ("OAI != newFunction->arg_end() && \"Number of output arguments should match \" \"the amount of defined values\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 1176, __PRETTY_FUNCTION__)) | |||
1175 | "Number of output arguments should match "((OAI != newFunction->arg_end() && "Number of output arguments should match " "the amount of defined values") ? static_cast<void> (0 ) : __assert_fail ("OAI != newFunction->arg_end() && \"Number of output arguments should match \" \"the amount of defined values\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 1176, __PRETTY_FUNCTION__)) | |||
1176 | "the amount of defined values")((OAI != newFunction->arg_end() && "Number of output arguments should match " "the amount of defined values") ? static_cast<void> (0 ) : __assert_fail ("OAI != newFunction->arg_end() && \"Number of output arguments should match \" \"the amount of defined values\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 1176, __PRETTY_FUNCTION__)); | |||
1177 | if (AggregateArgs) { | |||
1178 | Value *Idx[2]; | |||
1179 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); | |||
1180 | Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); | |||
1181 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
1182 | StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(), | |||
1183 | InsertBefore); | |||
1184 | new StoreInst(outputs[i], GEP, InsertBefore); | |||
1185 | // Since there should be only one struct argument aggregating | |||
1186 | // all the output values, we shouldn't increment OAI, which always | |||
1187 | // points to the struct argument, in this case. | |||
1188 | } else { | |||
1189 | new StoreInst(outputs[i], &*OAI, InsertBefore); | |||
1190 | ++OAI; | |||
1191 | } | |||
1192 | } | |||
1193 | ||||
1194 | // Now that we've done the deed, simplify the switch instruction. | |||
1195 | Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); | |||
1196 | switch (NumExitBlocks) { | |||
1197 | case 0: | |||
1198 | // There are no successors (the block containing the switch itself), which | |||
1199 | // means that previously this was the last part of the function, and hence | |||
1200 | // this should be rewritten as a `ret' | |||
1201 | ||||
1202 | // Check if the function should return a value | |||
1203 | if (OldFnRetTy->isVoidTy()) { | |||
1204 | ReturnInst::Create(Context, nullptr, TheSwitch); // Return void | |||
1205 | } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) { | |||
1206 | // return what we have | |||
1207 | ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch); | |||
1208 | } else { | |||
1209 | // Otherwise we must have code extracted an unwind or something, just | |||
1210 | // return whatever we want. | |||
1211 | ReturnInst::Create(Context, | |||
1212 | Constant::getNullValue(OldFnRetTy), TheSwitch); | |||
1213 | } | |||
1214 | ||||
1215 | TheSwitch->eraseFromParent(); | |||
1216 | break; | |||
1217 | case 1: | |||
1218 | // Only a single destination, change the switch into an unconditional | |||
1219 | // branch. | |||
1220 | BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch); | |||
1221 | TheSwitch->eraseFromParent(); | |||
1222 | break; | |||
1223 | case 2: | |||
1224 | BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), | |||
1225 | call, TheSwitch); | |||
1226 | TheSwitch->eraseFromParent(); | |||
1227 | break; | |||
1228 | default: | |||
1229 | // Otherwise, make the default destination of the switch instruction be one | |||
1230 | // of the other successors. | |||
1231 | TheSwitch->setCondition(call); | |||
1232 | TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks)); | |||
1233 | // Remove redundant case | |||
1234 | TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1)); | |||
1235 | break; | |||
1236 | } | |||
1237 | ||||
1238 | // Insert lifetime markers around the reloads of any output values. The | |||
1239 | // allocas output values are stored in are only in-use in the codeRepl block. | |||
1240 | insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call); | |||
1241 | ||||
1242 | return call; | |||
1243 | } | |||
1244 | ||||
1245 | void CodeExtractor::moveCodeToFunction(Function *newFunction) { | |||
1246 | Function *oldFunc = (*Blocks.begin())->getParent(); | |||
1247 | Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); | |||
1248 | Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); | |||
1249 | ||||
1250 | for (BasicBlock *Block : Blocks) { | |||
1251 | // Delete the basic block from the old function, and the list of blocks | |||
1252 | oldBlocks.remove(Block); | |||
1253 | ||||
1254 | // Insert this basic block into the new function | |||
1255 | newBlocks.push_back(Block); | |||
1256 | ||||
1257 | // Remove @llvm.assume calls that were moved to the new function from the | |||
1258 | // old function's assumption cache. | |||
1259 | if (AC) | |||
1260 | for (auto &I : *Block) | |||
1261 | if (match(&I, m_Intrinsic<Intrinsic::assume>())) | |||
1262 | AC->unregisterAssumption(cast<CallInst>(&I)); | |||
1263 | } | |||
1264 | } | |||
1265 | ||||
1266 | void CodeExtractor::calculateNewCallTerminatorWeights( | |||
1267 | BasicBlock *CodeReplacer, | |||
1268 | DenseMap<BasicBlock *, BlockFrequency> &ExitWeights, | |||
1269 | BranchProbabilityInfo *BPI) { | |||
1270 | using Distribution = BlockFrequencyInfoImplBase::Distribution; | |||
1271 | using BlockNode = BlockFrequencyInfoImplBase::BlockNode; | |||
1272 | ||||
1273 | // Update the branch weights for the exit block. | |||
1274 | Instruction *TI = CodeReplacer->getTerminator(); | |||
1275 | SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0); | |||
1276 | ||||
1277 | // Block Frequency distribution with dummy node. | |||
1278 | Distribution BranchDist; | |||
1279 | ||||
1280 | // Add each of the frequencies of the successors. | |||
1281 | for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) { | |||
1282 | BlockNode ExitNode(i); | |||
1283 | uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency(); | |||
1284 | if (ExitFreq != 0) | |||
1285 | BranchDist.addExit(ExitNode, ExitFreq); | |||
1286 | else | |||
1287 | BPI->setEdgeProbability(CodeReplacer, i, BranchProbability::getZero()); | |||
1288 | } | |||
1289 | ||||
1290 | // Check for no total weight. | |||
1291 | if (BranchDist.Total == 0) | |||
1292 | return; | |||
1293 | ||||
1294 | // Normalize the distribution so that they can fit in unsigned. | |||
1295 | BranchDist.normalize(); | |||
1296 | ||||
1297 | // Create normalized branch weights and set the metadata. | |||
1298 | for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) { | |||
1299 | const auto &Weight = BranchDist.Weights[I]; | |||
1300 | ||||
1301 | // Get the weight and update the current BFI. | |||
1302 | BranchWeights[Weight.TargetNode.Index] = Weight.Amount; | |||
1303 | BranchProbability BP(Weight.Amount, BranchDist.Total); | |||
1304 | BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP); | |||
1305 | } | |||
1306 | TI->setMetadata( | |||
1307 | LLVMContext::MD_prof, | |||
1308 | MDBuilder(TI->getContext()).createBranchWeights(BranchWeights)); | |||
1309 | } | |||
1310 | ||||
1311 | Function *CodeExtractor::extractCodeRegion() { | |||
1312 | if (!isEligible()) | |||
1313 | return nullptr; | |||
1314 | ||||
1315 | // Assumption: this is a single-entry code region, and the header is the first | |||
1316 | // block in the region. | |||
1317 | BasicBlock *header = *Blocks.begin(); | |||
1318 | Function *oldFunction = header->getParent(); | |||
1319 | ||||
1320 | // For functions with varargs, check that varargs handling is only done in the | |||
1321 | // outlined function, i.e vastart and vaend are only used in outlined blocks. | |||
1322 | if (AllowVarArgs && oldFunction->getFunctionType()->isVarArg()) { | |||
1323 | auto containsVarArgIntrinsic = [](Instruction &I) { | |||
1324 | if (const CallInst *CI = dyn_cast<CallInst>(&I)) | |||
1325 | if (const Function *F = CI->getCalledFunction()) | |||
1326 | return F->getIntrinsicID() == Intrinsic::vastart || | |||
1327 | F->getIntrinsicID() == Intrinsic::vaend; | |||
1328 | return false; | |||
1329 | }; | |||
1330 | ||||
1331 | for (auto &BB : *oldFunction) { | |||
1332 | if (Blocks.count(&BB)) | |||
1333 | continue; | |||
1334 | if (llvm::any_of(BB, containsVarArgIntrinsic)) | |||
1335 | return nullptr; | |||
1336 | } | |||
1337 | } | |||
1338 | ValueSet inputs, outputs, SinkingCands, HoistingCands; | |||
1339 | BasicBlock *CommonExit = nullptr; | |||
1340 | ||||
1341 | // Calculate the entry frequency of the new function before we change the root | |||
1342 | // block. | |||
1343 | BlockFrequency EntryFreq; | |||
1344 | if (BFI) { | |||
1345 | assert(BPI && "Both BPI and BFI are required to preserve profile info")((BPI && "Both BPI and BFI are required to preserve profile info" ) ? static_cast<void> (0) : __assert_fail ("BPI && \"Both BPI and BFI are required to preserve profile info\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 1345, __PRETTY_FUNCTION__)); | |||
1346 | for (BasicBlock *Pred : predecessors(header)) { | |||
1347 | if (Blocks.count(Pred)) | |||
1348 | continue; | |||
1349 | EntryFreq += | |||
1350 | BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header); | |||
1351 | } | |||
1352 | } | |||
1353 | ||||
1354 | // If we have any return instructions in the region, split those blocks so | |||
1355 | // that the return is not in the region. | |||
1356 | splitReturnBlocks(); | |||
1357 | ||||
1358 | // Calculate the exit blocks for the extracted region and the total exit | |||
1359 | // weights for each of those blocks. | |||
1360 | DenseMap<BasicBlock *, BlockFrequency> ExitWeights; | |||
1361 | SmallPtrSet<BasicBlock *, 1> ExitBlocks; | |||
1362 | for (BasicBlock *Block : Blocks) { | |||
1363 | for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE; | |||
1364 | ++SI) { | |||
1365 | if (!Blocks.count(*SI)) { | |||
1366 | // Update the branch weight for this successor. | |||
1367 | if (BFI) { | |||
1368 | BlockFrequency &BF = ExitWeights[*SI]; | |||
1369 | BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI); | |||
1370 | } | |||
1371 | ExitBlocks.insert(*SI); | |||
1372 | } | |||
1373 | } | |||
1374 | } | |||
1375 | NumExitBlocks = ExitBlocks.size(); | |||
1376 | ||||
1377 | // If we have to split PHI nodes of the entry or exit blocks, do so now. | |||
1378 | severSplitPHINodesOfEntry(header); | |||
1379 | severSplitPHINodesOfExits(ExitBlocks); | |||
1380 | ||||
1381 | // This takes place of the original loop | |||
1382 | BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(), | |||
1383 | "codeRepl", oldFunction, | |||
1384 | header); | |||
1385 | ||||
1386 | // The new function needs a root node because other nodes can branch to the | |||
1387 | // head of the region, but the entry node of a function cannot have preds. | |||
1388 | BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(), | |||
1389 | "newFuncRoot"); | |||
1390 | auto *BranchI = BranchInst::Create(header); | |||
1391 | // If the original function has debug info, we have to add a debug location | |||
1392 | // to the new branch instruction from the artificial entry block. | |||
1393 | // We use the debug location of the first instruction in the extracted | |||
1394 | // blocks, as there is no other equivalent line in the source code. | |||
1395 | if (oldFunction->getSubprogram()) { | |||
1396 | any_of(Blocks, [&BranchI](const BasicBlock *BB) { | |||
1397 | return any_of(*BB, [&BranchI](const Instruction &I) { | |||
1398 | if (!I.getDebugLoc()) | |||
1399 | return false; | |||
1400 | BranchI->setDebugLoc(I.getDebugLoc()); | |||
1401 | return true; | |||
1402 | }); | |||
1403 | }); | |||
1404 | } | |||
1405 | newFuncRoot->getInstList().push_back(BranchI); | |||
1406 | ||||
1407 | findAllocas(SinkingCands, HoistingCands, CommonExit); | |||
1408 | assert(HoistingCands.empty() || CommonExit)((HoistingCands.empty() || CommonExit) ? static_cast<void> (0) : __assert_fail ("HoistingCands.empty() || CommonExit", "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 1408, __PRETTY_FUNCTION__)); | |||
1409 | ||||
1410 | // Find inputs to, outputs from the code region. | |||
1411 | findInputsOutputs(inputs, outputs, SinkingCands); | |||
1412 | ||||
1413 | // Now sink all instructions which only have non-phi uses inside the region | |||
1414 | for (auto *II : SinkingCands) | |||
1415 | cast<Instruction>(II)->moveBefore(*newFuncRoot, | |||
1416 | newFuncRoot->getFirstInsertionPt()); | |||
1417 | ||||
1418 | if (!HoistingCands.empty()) { | |||
1419 | auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit); | |||
1420 | Instruction *TI = HoistToBlock->getTerminator(); | |||
1421 | for (auto *II : HoistingCands) | |||
1422 | cast<Instruction>(II)->moveBefore(TI); | |||
1423 | } | |||
1424 | ||||
1425 | // Collect objects which are inputs to the extraction region and also | |||
1426 | // referenced by lifetime start markers within it. The effects of these | |||
1427 | // markers must be replicated in the calling function to prevent the stack | |||
1428 | // coloring pass from merging slots which store input objects. | |||
1429 | ValueSet LifetimesStart; | |||
1430 | eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart); | |||
1431 | ||||
1432 | // Construct new function based on inputs/outputs & add allocas for all defs. | |||
1433 | Function *newFunction = | |||
1434 | constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer, | |||
1435 | oldFunction, oldFunction->getParent()); | |||
1436 | ||||
1437 | // Update the entry count of the function. | |||
1438 | if (BFI) { | |||
1439 | auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency()); | |||
1440 | if (Count.hasValue()) | |||
1441 | newFunction->setEntryCount( | |||
1442 | ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME | |||
1443 | BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency()); | |||
1444 | } | |||
1445 | ||||
1446 | CallInst *TheCall = | |||
1447 | emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); | |||
1448 | ||||
1449 | moveCodeToFunction(newFunction); | |||
1450 | ||||
1451 | // Replicate the effects of any lifetime start/end markers which referenced | |||
1452 | // input objects in the extraction region by placing markers around the call. | |||
1453 | insertLifetimeMarkersSurroundingCall( | |||
1454 | oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall); | |||
1455 | ||||
1456 | // Propagate personality info to the new function if there is one. | |||
1457 | if (oldFunction->hasPersonalityFn()) | |||
1458 | newFunction->setPersonalityFn(oldFunction->getPersonalityFn()); | |||
1459 | ||||
1460 | // Update the branch weights for the exit block. | |||
1461 | if (BFI && NumExitBlocks > 1) | |||
1462 | calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI); | |||
1463 | ||||
1464 | // Loop over all of the PHI nodes in the header and exit blocks, and change | |||
1465 | // any references to the old incoming edge to be the new incoming edge. | |||
1466 | for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) { | |||
1467 | PHINode *PN = cast<PHINode>(I); | |||
1468 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |||
1469 | if (!Blocks.count(PN->getIncomingBlock(i))) | |||
1470 | PN->setIncomingBlock(i, newFuncRoot); | |||
1471 | } | |||
1472 | ||||
1473 | for (BasicBlock *ExitBB : ExitBlocks) | |||
1474 | for (PHINode &PN : ExitBB->phis()) { | |||
1475 | Value *IncomingCodeReplacerVal = nullptr; | |||
1476 | for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { | |||
1477 | // Ignore incoming values from outside of the extracted region. | |||
1478 | if (!Blocks.count(PN.getIncomingBlock(i))) | |||
1479 | continue; | |||
1480 | ||||
1481 | // Ensure that there is only one incoming value from codeReplacer. | |||
1482 | if (!IncomingCodeReplacerVal) { | |||
1483 | PN.setIncomingBlock(i, codeReplacer); | |||
1484 | IncomingCodeReplacerVal = PN.getIncomingValue(i); | |||
1485 | } else | |||
1486 | assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&((IncomingCodeReplacerVal == PN.getIncomingValue(i) && "PHI has two incompatbile incoming values from codeRepl") ? static_cast <void> (0) : __assert_fail ("IncomingCodeReplacerVal == PN.getIncomingValue(i) && \"PHI has two incompatbile incoming values from codeRepl\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 1487, __PRETTY_FUNCTION__)) | |||
1487 | "PHI has two incompatbile incoming values from codeRepl")((IncomingCodeReplacerVal == PN.getIncomingValue(i) && "PHI has two incompatbile incoming values from codeRepl") ? static_cast <void> (0) : __assert_fail ("IncomingCodeReplacerVal == PN.getIncomingValue(i) && \"PHI has two incompatbile incoming values from codeRepl\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Utils/CodeExtractor.cpp" , 1487, __PRETTY_FUNCTION__)); | |||
1488 | } | |||
1489 | } | |||
1490 | ||||
1491 | // Erase debug info intrinsics. Variable updates within the new function are | |||
1492 | // invisible to debuggers. This could be improved by defining a DISubprogram | |||
1493 | // for the new function. | |||
1494 | for (BasicBlock &BB : *newFunction) { | |||
1495 | auto BlockIt = BB.begin(); | |||
1496 | // Remove debug info intrinsics from the new function. | |||
1497 | while (BlockIt != BB.end()) { | |||
1498 | Instruction *Inst = &*BlockIt; | |||
1499 | ++BlockIt; | |||
1500 | if (isa<DbgInfoIntrinsic>(Inst)) | |||
1501 | Inst->eraseFromParent(); | |||
1502 | } | |||
1503 | // Remove debug info intrinsics which refer to values in the new function | |||
1504 | // from the old function. | |||
1505 | SmallVector<DbgVariableIntrinsic *, 4> DbgUsers; | |||
1506 | for (Instruction &I : BB) | |||
1507 | findDbgUsers(DbgUsers, &I); | |||
1508 | for (DbgVariableIntrinsic *DVI : DbgUsers) | |||
1509 | DVI->eraseFromParent(); | |||
1510 | } | |||
1511 | ||||
1512 | // Mark the new function `noreturn` if applicable. Terminators which resume | |||
1513 | // exception propagation are treated as returning instructions. This is to | |||
1514 | // avoid inserting traps after calls to outlined functions which unwind. | |||
1515 | bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) { | |||
1516 | const Instruction *Term = BB.getTerminator(); | |||
1517 | return isa<ReturnInst>(Term) || isa<ResumeInst>(Term); | |||
1518 | }); | |||
1519 | if (doesNotReturn) | |||
1520 | newFunction->setDoesNotReturn(); | |||
1521 | ||||
1522 | LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { if (verifyFunction(*newFunction, &errs ())) { newFunction->dump(); report_fatal_error("verification of newFunction failed!" ); }; } } while (false) | |||
1523 | newFunction->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { if (verifyFunction(*newFunction, &errs ())) { newFunction->dump(); report_fatal_error("verification of newFunction failed!" ); }; } } while (false) | |||
1524 | report_fatal_error("verification of newFunction failed!");do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { if (verifyFunction(*newFunction, &errs ())) { newFunction->dump(); report_fatal_error("verification of newFunction failed!" ); }; } } while (false) | |||
1525 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { if (verifyFunction(*newFunction, &errs ())) { newFunction->dump(); report_fatal_error("verification of newFunction failed!" ); }; } } while (false); | |||
1526 | LLVM_DEBUG(if (verifyFunction(*oldFunction))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { if (verifyFunction(*oldFunction)) report_fatal_error ("verification of oldFunction failed!"); } } while (false) | |||
1527 | report_fatal_error("verification of oldFunction failed!"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { if (verifyFunction(*oldFunction)) report_fatal_error ("verification of oldFunction failed!"); } } while (false); | |||
1528 | return newFunction; | |||
1529 | } |