File: | lib/Transforms/Utils/CodeExtractor.cpp |
Warning: | line 718, 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 | // 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/ArrayRef.h" | |||
18 | #include "llvm/ADT/DenseMap.h" | |||
19 | #include "llvm/ADT/Optional.h" | |||
20 | #include "llvm/ADT/STLExtras.h" | |||
21 | #include "llvm/ADT/SetVector.h" | |||
22 | #include "llvm/ADT/SmallPtrSet.h" | |||
23 | #include "llvm/ADT/SmallVector.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/Type.h" | |||
48 | #include "llvm/IR/User.h" | |||
49 | #include "llvm/IR/Value.h" | |||
50 | #include "llvm/IR/Verifier.h" | |||
51 | #include "llvm/Pass.h" | |||
52 | #include "llvm/Support/BlockFrequency.h" | |||
53 | #include "llvm/Support/BranchProbability.h" | |||
54 | #include "llvm/Support/Casting.h" | |||
55 | #include "llvm/Support/CommandLine.h" | |||
56 | #include "llvm/Support/Debug.h" | |||
57 | #include "llvm/Support/ErrorHandling.h" | |||
58 | #include "llvm/Support/raw_ostream.h" | |||
59 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
60 | #include <cassert> | |||
61 | #include <cstdint> | |||
62 | #include <iterator> | |||
63 | #include <map> | |||
64 | #include <set> | |||
65 | #include <utility> | |||
66 | #include <vector> | |||
67 | ||||
68 | using namespace llvm; | |||
69 | using ProfileCount = Function::ProfileCount; | |||
70 | ||||
71 | #define DEBUG_TYPE"code-extractor" "code-extractor" | |||
72 | ||||
73 | // Provide a command-line option to aggregate function arguments into a struct | |||
74 | // for functions produced by the code extractor. This is useful when converting | |||
75 | // extracted functions to pthread-based code, as only one argument (void*) can | |||
76 | // be passed in to pthread_create(). | |||
77 | static cl::opt<bool> | |||
78 | AggregateArgsOpt("aggregate-extracted-args", cl::Hidden, | |||
79 | cl::desc("Aggregate arguments to code-extracted functions")); | |||
80 | ||||
81 | /// \brief Test whether a block is valid for extraction. | |||
82 | bool CodeExtractor::isBlockValidForExtraction(const BasicBlock &BB, | |||
83 | bool AllowVarArgs) { | |||
84 | // Landing pads must be in the function where they were inserted for cleanup. | |||
85 | if (BB.isEHPad()) | |||
86 | return false; | |||
87 | // taking the address of a basic block moved to another function is illegal | |||
88 | if (BB.hasAddressTaken()) | |||
89 | return false; | |||
90 | ||||
91 | // don't hoist code that uses another basicblock address, as it's likely to | |||
92 | // lead to unexpected behavior, like cross-function jumps | |||
93 | SmallPtrSet<User const *, 16> Visited; | |||
94 | SmallVector<User const *, 16> ToVisit; | |||
95 | ||||
96 | for (Instruction const &Inst : BB) | |||
97 | ToVisit.push_back(&Inst); | |||
98 | ||||
99 | while (!ToVisit.empty()) { | |||
100 | User const *Curr = ToVisit.pop_back_val(); | |||
101 | if (!Visited.insert(Curr).second) | |||
102 | continue; | |||
103 | if (isa<BlockAddress const>(Curr)) | |||
104 | return false; // even a reference to self is likely to be not compatible | |||
105 | ||||
106 | if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB) | |||
107 | continue; | |||
108 | ||||
109 | for (auto const &U : Curr->operands()) { | |||
110 | if (auto *UU = dyn_cast<User>(U)) | |||
111 | ToVisit.push_back(UU); | |||
112 | } | |||
113 | } | |||
114 | ||||
115 | // Don't hoist code containing allocas or invokes. If explicitly requested, | |||
116 | // allow vastart. | |||
117 | for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) { | |||
118 | if (isa<AllocaInst>(I) || isa<InvokeInst>(I)) | |||
119 | return false; | |||
120 | if (const CallInst *CI = dyn_cast<CallInst>(I)) | |||
121 | if (const Function *F = CI->getCalledFunction()) | |||
122 | if (F->getIntrinsicID() == Intrinsic::vastart) { | |||
123 | if (AllowVarArgs) | |||
124 | continue; | |||
125 | else | |||
126 | return false; | |||
127 | } | |||
128 | } | |||
129 | ||||
130 | return true; | |||
131 | } | |||
132 | ||||
133 | /// \brief Build a set of blocks to extract if the input blocks are viable. | |||
134 | static SetVector<BasicBlock *> | |||
135 | buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, | |||
136 | bool AllowVarArgs) { | |||
137 | assert(!BBs.empty() && "The set of blocks to extract must be non-empty")(static_cast <bool> (!BBs.empty() && "The set of blocks to extract must be non-empty" ) ? void (0) : __assert_fail ("!BBs.empty() && \"The set of blocks to extract must be non-empty\"" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 137, __extension__ __PRETTY_FUNCTION__)); | |||
138 | SetVector<BasicBlock *> Result; | |||
139 | ||||
140 | // Loop over the blocks, adding them to our set-vector, and aborting with an | |||
141 | // empty set if we encounter invalid blocks. | |||
142 | for (BasicBlock *BB : BBs) { | |||
143 | // If this block is dead, don't process it. | |||
144 | if (DT && !DT->isReachableFromEntry(BB)) | |||
145 | continue; | |||
146 | ||||
147 | if (!Result.insert(BB)) | |||
148 | llvm_unreachable("Repeated basic blocks in extraction input")::llvm::llvm_unreachable_internal("Repeated basic blocks in extraction input" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 148); | |||
149 | if (!CodeExtractor::isBlockValidForExtraction(*BB, AllowVarArgs)) { | |||
150 | Result.clear(); | |||
151 | return Result; | |||
152 | } | |||
153 | } | |||
154 | ||||
155 | #ifndef NDEBUG | |||
156 | for (SetVector<BasicBlock *>::iterator I = std::next(Result.begin()), | |||
157 | E = Result.end(); | |||
158 | I != E; ++I) | |||
159 | for (pred_iterator PI = pred_begin(*I), PE = pred_end(*I); | |||
160 | PI != PE; ++PI) | |||
161 | assert(Result.count(*PI) &&(static_cast <bool> (Result.count(*PI) && "No blocks in this region may have entries from outside the region" " except for the first block!") ? void (0) : __assert_fail ( "Result.count(*PI) && \"No blocks in this region may have entries from outside the region\" \" except for the first block!\"" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 163, __extension__ __PRETTY_FUNCTION__)) | |||
162 | "No blocks in this region may have entries from outside the region"(static_cast <bool> (Result.count(*PI) && "No blocks in this region may have entries from outside the region" " except for the first block!") ? void (0) : __assert_fail ( "Result.count(*PI) && \"No blocks in this region may have entries from outside the region\" \" except for the first block!\"" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 163, __extension__ __PRETTY_FUNCTION__)) | |||
163 | " except for the first block!")(static_cast <bool> (Result.count(*PI) && "No blocks in this region may have entries from outside the region" " except for the first block!") ? void (0) : __assert_fail ( "Result.count(*PI) && \"No blocks in this region may have entries from outside the region\" \" except for the first block!\"" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 163, __extension__ __PRETTY_FUNCTION__)); | |||
164 | #endif | |||
165 | ||||
166 | return Result; | |||
167 | } | |||
168 | ||||
169 | CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, | |||
170 | bool AggregateArgs, BlockFrequencyInfo *BFI, | |||
171 | BranchProbabilityInfo *BPI, bool AllowVarArgs) | |||
172 | : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI), | |||
173 | BPI(BPI), AllowVarArgs(AllowVarArgs), | |||
174 | Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs)) {} | |||
175 | ||||
176 | CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs, | |||
177 | BlockFrequencyInfo *BFI, | |||
178 | BranchProbabilityInfo *BPI) | |||
179 | : DT(&DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI), | |||
180 | BPI(BPI), AllowVarArgs(false), | |||
181 | Blocks(buildExtractionBlockSet(L.getBlocks(), &DT, | |||
182 | /* AllowVarArgs */ false)) {} | |||
183 | ||||
184 | /// definedInRegion - Return true if the specified value is defined in the | |||
185 | /// extracted region. | |||
186 | static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) { | |||
187 | if (Instruction *I = dyn_cast<Instruction>(V)) | |||
188 | if (Blocks.count(I->getParent())) | |||
189 | return true; | |||
190 | return false; | |||
191 | } | |||
192 | ||||
193 | /// definedInCaller - Return true if the specified value is defined in the | |||
194 | /// function being code extracted, but not in the region being extracted. | |||
195 | /// These values must be passed in as live-ins to the function. | |||
196 | static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) { | |||
197 | if (isa<Argument>(V)) return true; | |||
198 | if (Instruction *I = dyn_cast<Instruction>(V)) | |||
199 | if (!Blocks.count(I->getParent())) | |||
200 | return true; | |||
201 | return false; | |||
202 | } | |||
203 | ||||
204 | static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) { | |||
205 | BasicBlock *CommonExitBlock = nullptr; | |||
206 | auto hasNonCommonExitSucc = [&](BasicBlock *Block) { | |||
207 | for (auto *Succ : successors(Block)) { | |||
208 | // Internal edges, ok. | |||
209 | if (Blocks.count(Succ)) | |||
210 | continue; | |||
211 | if (!CommonExitBlock) { | |||
212 | CommonExitBlock = Succ; | |||
213 | continue; | |||
214 | } | |||
215 | if (CommonExitBlock == Succ) | |||
216 | continue; | |||
217 | ||||
218 | return true; | |||
219 | } | |||
220 | return false; | |||
221 | }; | |||
222 | ||||
223 | if (any_of(Blocks, hasNonCommonExitSucc)) | |||
224 | return nullptr; | |||
225 | ||||
226 | return CommonExitBlock; | |||
227 | } | |||
228 | ||||
229 | bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers( | |||
230 | Instruction *Addr) const { | |||
231 | AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets()); | |||
232 | Function *Func = (*Blocks.begin())->getParent(); | |||
233 | for (BasicBlock &BB : *Func) { | |||
234 | if (Blocks.count(&BB)) | |||
235 | continue; | |||
236 | for (Instruction &II : BB) { | |||
237 | if (isa<DbgInfoIntrinsic>(II)) | |||
238 | continue; | |||
239 | ||||
240 | unsigned Opcode = II.getOpcode(); | |||
241 | Value *MemAddr = nullptr; | |||
242 | switch (Opcode) { | |||
243 | case Instruction::Store: | |||
244 | case Instruction::Load: { | |||
245 | if (Opcode == Instruction::Store) { | |||
246 | StoreInst *SI = cast<StoreInst>(&II); | |||
247 | MemAddr = SI->getPointerOperand(); | |||
248 | } else { | |||
249 | LoadInst *LI = cast<LoadInst>(&II); | |||
250 | MemAddr = LI->getPointerOperand(); | |||
251 | } | |||
252 | // Global variable can not be aliased with locals. | |||
253 | if (dyn_cast<Constant>(MemAddr)) | |||
254 | break; | |||
255 | Value *Base = MemAddr->stripInBoundsConstantOffsets(); | |||
256 | if (!dyn_cast<AllocaInst>(Base) || Base == AI) | |||
257 | return false; | |||
258 | break; | |||
259 | } | |||
260 | default: { | |||
261 | IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II); | |||
262 | if (IntrInst) { | |||
263 | if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start || | |||
264 | IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) | |||
265 | break; | |||
266 | return false; | |||
267 | } | |||
268 | // Treat all the other cases conservatively if it has side effects. | |||
269 | if (II.mayHaveSideEffects()) | |||
270 | return false; | |||
271 | } | |||
272 | } | |||
273 | } | |||
274 | } | |||
275 | ||||
276 | return true; | |||
277 | } | |||
278 | ||||
279 | BasicBlock * | |||
280 | CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) { | |||
281 | BasicBlock *SinglePredFromOutlineRegion = nullptr; | |||
282 | assert(!Blocks.count(CommonExitBlock) &&(static_cast <bool> (!Blocks.count(CommonExitBlock) && "Expect a block outside the region!") ? void (0) : __assert_fail ("!Blocks.count(CommonExitBlock) && \"Expect a block outside the region!\"" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 283, __extension__ __PRETTY_FUNCTION__)) | |||
283 | "Expect a block outside the region!")(static_cast <bool> (!Blocks.count(CommonExitBlock) && "Expect a block outside the region!") ? void (0) : __assert_fail ("!Blocks.count(CommonExitBlock) && \"Expect a block outside the region!\"" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 283, __extension__ __PRETTY_FUNCTION__)); | |||
284 | for (auto *Pred : predecessors(CommonExitBlock)) { | |||
285 | if (!Blocks.count(Pred)) | |||
286 | continue; | |||
287 | if (!SinglePredFromOutlineRegion) { | |||
288 | SinglePredFromOutlineRegion = Pred; | |||
289 | } else if (SinglePredFromOutlineRegion != Pred) { | |||
290 | SinglePredFromOutlineRegion = nullptr; | |||
291 | break; | |||
292 | } | |||
293 | } | |||
294 | ||||
295 | if (SinglePredFromOutlineRegion) | |||
296 | return SinglePredFromOutlineRegion; | |||
297 | ||||
298 | #ifndef NDEBUG | |||
299 | auto getFirstPHI = [](BasicBlock *BB) { | |||
300 | BasicBlock::iterator I = BB->begin(); | |||
301 | PHINode *FirstPhi = nullptr; | |||
302 | while (I != BB->end()) { | |||
303 | PHINode *Phi = dyn_cast<PHINode>(I); | |||
304 | if (!Phi) | |||
305 | break; | |||
306 | if (!FirstPhi) { | |||
307 | FirstPhi = Phi; | |||
308 | break; | |||
309 | } | |||
310 | } | |||
311 | return FirstPhi; | |||
312 | }; | |||
313 | // If there are any phi nodes, the single pred either exists or has already | |||
314 | // be created before code extraction. | |||
315 | assert(!getFirstPHI(CommonExitBlock) && "Phi not expected")(static_cast <bool> (!getFirstPHI(CommonExitBlock) && "Phi not expected") ? void (0) : __assert_fail ("!getFirstPHI(CommonExitBlock) && \"Phi not expected\"" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 315, __extension__ __PRETTY_FUNCTION__)); | |||
316 | #endif | |||
317 | ||||
318 | BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock( | |||
319 | CommonExitBlock->getFirstNonPHI()->getIterator()); | |||
320 | ||||
321 | for (auto PI = pred_begin(CommonExitBlock), PE = pred_end(CommonExitBlock); | |||
322 | PI != PE;) { | |||
323 | BasicBlock *Pred = *PI++; | |||
324 | if (Blocks.count(Pred)) | |||
325 | continue; | |||
326 | Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock); | |||
327 | } | |||
328 | // Now add the old exit block to the outline region. | |||
329 | Blocks.insert(CommonExitBlock); | |||
330 | return CommonExitBlock; | |||
331 | } | |||
332 | ||||
333 | void CodeExtractor::findAllocas(ValueSet &SinkCands, ValueSet &HoistCands, | |||
334 | BasicBlock *&ExitBlock) const { | |||
335 | Function *Func = (*Blocks.begin())->getParent(); | |||
336 | ExitBlock = getCommonExitBlock(Blocks); | |||
337 | ||||
338 | for (BasicBlock &BB : *Func) { | |||
339 | if (Blocks.count(&BB)) | |||
340 | continue; | |||
341 | for (Instruction &II : BB) { | |||
342 | auto *AI = dyn_cast<AllocaInst>(&II); | |||
343 | if (!AI) | |||
344 | continue; | |||
345 | ||||
346 | // Find the pair of life time markers for address 'Addr' that are either | |||
347 | // defined inside the outline region or can legally be shrinkwrapped into | |||
348 | // the outline region. If there are not other untracked uses of the | |||
349 | // address, return the pair of markers if found; otherwise return a pair | |||
350 | // of nullptr. | |||
351 | auto GetLifeTimeMarkers = | |||
352 | [&](Instruction *Addr, bool &SinkLifeStart, | |||
353 | bool &HoistLifeEnd) -> std::pair<Instruction *, Instruction *> { | |||
354 | Instruction *LifeStart = nullptr, *LifeEnd = nullptr; | |||
355 | ||||
356 | for (User *U : Addr->users()) { | |||
357 | IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U); | |||
358 | if (IntrInst) { | |||
359 | if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) { | |||
360 | // Do not handle the case where AI has multiple start markers. | |||
361 | if (LifeStart) | |||
362 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
363 | LifeStart = IntrInst; | |||
364 | } | |||
365 | if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) { | |||
366 | if (LifeEnd) | |||
367 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
368 | LifeEnd = IntrInst; | |||
369 | } | |||
370 | continue; | |||
371 | } | |||
372 | // Find untracked uses of the address, bail. | |||
373 | if (!definedInRegion(Blocks, U)) | |||
374 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
375 | } | |||
376 | ||||
377 | if (!LifeStart || !LifeEnd) | |||
378 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
379 | ||||
380 | SinkLifeStart = !definedInRegion(Blocks, LifeStart); | |||
381 | HoistLifeEnd = !definedInRegion(Blocks, LifeEnd); | |||
382 | // Do legality Check. | |||
383 | if ((SinkLifeStart || HoistLifeEnd) && | |||
384 | !isLegalToShrinkwrapLifetimeMarkers(Addr)) | |||
385 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
386 | ||||
387 | // Check to see if we have a place to do hoisting, if not, bail. | |||
388 | if (HoistLifeEnd && !ExitBlock) | |||
389 | return std::make_pair<Instruction *>(nullptr, nullptr); | |||
390 | ||||
391 | return std::make_pair(LifeStart, LifeEnd); | |||
392 | }; | |||
393 | ||||
394 | bool SinkLifeStart = false, HoistLifeEnd = false; | |||
395 | auto Markers = GetLifeTimeMarkers(AI, SinkLifeStart, HoistLifeEnd); | |||
396 | ||||
397 | if (Markers.first) { | |||
398 | if (SinkLifeStart) | |||
399 | SinkCands.insert(Markers.first); | |||
400 | SinkCands.insert(AI); | |||
401 | if (HoistLifeEnd) | |||
402 | HoistCands.insert(Markers.second); | |||
403 | continue; | |||
404 | } | |||
405 | ||||
406 | // Follow the bitcast. | |||
407 | Instruction *MarkerAddr = nullptr; | |||
408 | for (User *U : AI->users()) { | |||
409 | if (U->stripInBoundsConstantOffsets() == AI) { | |||
410 | SinkLifeStart = false; | |||
411 | HoistLifeEnd = false; | |||
412 | Instruction *Bitcast = cast<Instruction>(U); | |||
413 | Markers = GetLifeTimeMarkers(Bitcast, SinkLifeStart, HoistLifeEnd); | |||
414 | if (Markers.first) { | |||
415 | MarkerAddr = Bitcast; | |||
416 | continue; | |||
417 | } | |||
418 | } | |||
419 | ||||
420 | // Found unknown use of AI. | |||
421 | if (!definedInRegion(Blocks, U)) { | |||
422 | MarkerAddr = nullptr; | |||
423 | break; | |||
424 | } | |||
425 | } | |||
426 | ||||
427 | if (MarkerAddr) { | |||
428 | if (SinkLifeStart) | |||
429 | SinkCands.insert(Markers.first); | |||
430 | if (!definedInRegion(Blocks, MarkerAddr)) | |||
431 | SinkCands.insert(MarkerAddr); | |||
432 | SinkCands.insert(AI); | |||
433 | if (HoistLifeEnd) | |||
434 | HoistCands.insert(Markers.second); | |||
435 | } | |||
436 | } | |||
437 | } | |||
438 | } | |||
439 | ||||
440 | void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, | |||
441 | const ValueSet &SinkCands) const { | |||
442 | for (BasicBlock *BB : Blocks) { | |||
443 | // If a used value is defined outside the region, it's an input. If an | |||
444 | // instruction is used outside the region, it's an output. | |||
445 | for (Instruction &II : *BB) { | |||
446 | for (User::op_iterator OI = II.op_begin(), OE = II.op_end(); OI != OE; | |||
447 | ++OI) { | |||
448 | Value *V = *OI; | |||
449 | if (!SinkCands.count(V) && definedInCaller(Blocks, V)) | |||
450 | Inputs.insert(V); | |||
451 | } | |||
452 | ||||
453 | for (User *U : II.users()) | |||
454 | if (!definedInRegion(Blocks, U)) { | |||
455 | Outputs.insert(&II); | |||
456 | break; | |||
457 | } | |||
458 | } | |||
459 | } | |||
460 | } | |||
461 | ||||
462 | /// severSplitPHINodes - If a PHI node has multiple inputs from outside of the | |||
463 | /// region, we need to split the entry block of the region so that the PHI node | |||
464 | /// is easier to deal with. | |||
465 | void CodeExtractor::severSplitPHINodes(BasicBlock *&Header) { | |||
466 | unsigned NumPredsFromRegion = 0; | |||
467 | unsigned NumPredsOutsideRegion = 0; | |||
468 | ||||
469 | if (Header != &Header->getParent()->getEntryBlock()) { | |||
470 | PHINode *PN = dyn_cast<PHINode>(Header->begin()); | |||
471 | if (!PN) return; // No PHI nodes. | |||
472 | ||||
473 | // If the header node contains any PHI nodes, check to see if there is more | |||
474 | // than one entry from outside the region. If so, we need to sever the | |||
475 | // header block into two. | |||
476 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |||
477 | if (Blocks.count(PN->getIncomingBlock(i))) | |||
478 | ++NumPredsFromRegion; | |||
479 | else | |||
480 | ++NumPredsOutsideRegion; | |||
481 | ||||
482 | // If there is one (or fewer) predecessor from outside the region, we don't | |||
483 | // need to do anything special. | |||
484 | if (NumPredsOutsideRegion <= 1) return; | |||
485 | } | |||
486 | ||||
487 | // Otherwise, we need to split the header block into two pieces: one | |||
488 | // containing PHI nodes merging values from outside of the region, and a | |||
489 | // second that contains all of the code for the block and merges back any | |||
490 | // incoming values from inside of the region. | |||
491 | BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT); | |||
492 | ||||
493 | // We only want to code extract the second block now, and it becomes the new | |||
494 | // header of the region. | |||
495 | BasicBlock *OldPred = Header; | |||
496 | Blocks.remove(OldPred); | |||
497 | Blocks.insert(NewBB); | |||
498 | Header = NewBB; | |||
499 | ||||
500 | // Okay, now we need to adjust the PHI nodes and any branches from within the | |||
501 | // region to go to the new header block instead of the old header block. | |||
502 | if (NumPredsFromRegion) { | |||
503 | PHINode *PN = cast<PHINode>(OldPred->begin()); | |||
504 | // Loop over all of the predecessors of OldPred that are in the region, | |||
505 | // changing them to branch to NewBB instead. | |||
506 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |||
507 | if (Blocks.count(PN->getIncomingBlock(i))) { | |||
508 | TerminatorInst *TI = PN->getIncomingBlock(i)->getTerminator(); | |||
509 | TI->replaceUsesOfWith(OldPred, NewBB); | |||
510 | } | |||
511 | ||||
512 | // Okay, everything within the region is now branching to the right block, we | |||
513 | // just have to update the PHI nodes now, inserting PHI nodes into NewBB. | |||
514 | BasicBlock::iterator AfterPHIs; | |||
515 | for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) { | |||
516 | PHINode *PN = cast<PHINode>(AfterPHIs); | |||
517 | // Create a new PHI node in the new region, which has an incoming value | |||
518 | // from OldPred of PN. | |||
519 | PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion, | |||
520 | PN->getName() + ".ce", &NewBB->front()); | |||
521 | PN->replaceAllUsesWith(NewPN); | |||
522 | NewPN->addIncoming(PN, OldPred); | |||
523 | ||||
524 | // Loop over all of the incoming value in PN, moving them to NewPN if they | |||
525 | // are from the extracted region. | |||
526 | for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { | |||
527 | if (Blocks.count(PN->getIncomingBlock(i))) { | |||
528 | NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); | |||
529 | PN->removeIncomingValue(i); | |||
530 | --i; | |||
531 | } | |||
532 | } | |||
533 | } | |||
534 | } | |||
535 | } | |||
536 | ||||
537 | void CodeExtractor::splitReturnBlocks() { | |||
538 | for (BasicBlock *Block : Blocks) | |||
539 | if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) { | |||
540 | BasicBlock *New = | |||
541 | Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret"); | |||
542 | if (DT) { | |||
543 | // Old dominates New. New node dominates all other nodes dominated | |||
544 | // by Old. | |||
545 | DomTreeNode *OldNode = DT->getNode(Block); | |||
546 | SmallVector<DomTreeNode *, 8> Children(OldNode->begin(), | |||
547 | OldNode->end()); | |||
548 | ||||
549 | DomTreeNode *NewNode = DT->addNewBlock(New, Block); | |||
550 | ||||
551 | for (DomTreeNode *I : Children) | |||
552 | DT->changeImmediateDominator(I, NewNode); | |||
553 | } | |||
554 | } | |||
555 | } | |||
556 | ||||
557 | /// constructFunction - make a function based on inputs and outputs, as follows: | |||
558 | /// f(in0, ..., inN, out0, ..., outN) | |||
559 | Function *CodeExtractor::constructFunction(const ValueSet &inputs, | |||
560 | const ValueSet &outputs, | |||
561 | BasicBlock *header, | |||
562 | BasicBlock *newRootNode, | |||
563 | BasicBlock *newHeader, | |||
564 | Function *oldFunction, | |||
565 | Module *M) { | |||
566 | DEBUG(dbgs() << "inputs: " << inputs.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "inputs: " << inputs .size() << "\n"; } } while (false); | |||
567 | DEBUG(dbgs() << "outputs: " << outputs.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { dbgs() << "outputs: " << outputs .size() << "\n"; } } while (false); | |||
568 | ||||
569 | // This function returns unsigned, outputs will go back by reference. | |||
570 | switch (NumExitBlocks) { | |||
| ||||
571 | case 0: | |||
572 | case 1: RetTy = Type::getVoidTy(header->getContext()); break; | |||
573 | case 2: RetTy = Type::getInt1Ty(header->getContext()); break; | |||
574 | default: RetTy = Type::getInt16Ty(header->getContext()); break; | |||
575 | } | |||
576 | ||||
577 | std::vector<Type *> paramTy; | |||
578 | ||||
579 | // Add the types of the input values to the function's argument list | |||
580 | for (Value *value : inputs) { | |||
581 | 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); | |||
582 | paramTy.push_back(value->getType()); | |||
583 | } | |||
584 | ||||
585 | // Add the types of the output values to the function's argument list. | |||
586 | for (Value *output : outputs) { | |||
587 | 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); | |||
588 | if (AggregateArgs) | |||
589 | paramTy.push_back(output->getType()); | |||
590 | else | |||
591 | paramTy.push_back(PointerType::getUnqual(output->getType())); | |||
592 | } | |||
593 | ||||
594 | DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { { dbgs() << "Function type: " << *RetTy << " f("; for (Type *i : paramTy) dbgs() << *i << ", "; dbgs() << ")\n"; }; } } while (false ) | |||
595 | 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 ) | |||
596 | 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 ) | |||
597 | 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 ) | |||
598 | 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 ) | |||
599 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { { dbgs() << "Function type: " << *RetTy << " f("; for (Type *i : paramTy) dbgs() << *i << ", "; dbgs() << ")\n"; }; } } while (false ); | |||
600 | ||||
601 | StructType *StructTy; | |||
602 | if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { | |||
603 | StructTy = StructType::get(M->getContext(), paramTy); | |||
604 | paramTy.clear(); | |||
605 | paramTy.push_back(PointerType::getUnqual(StructTy)); | |||
606 | } | |||
607 | FunctionType *funcType = | |||
608 | FunctionType::get(RetTy, paramTy, | |||
609 | AllowVarArgs && oldFunction->isVarArg()); | |||
610 | ||||
611 | // Create the new function | |||
612 | Function *newFunction = Function::Create(funcType, | |||
613 | GlobalValue::InternalLinkage, | |||
614 | oldFunction->getName() + "_" + | |||
615 | header->getName(), M); | |||
616 | // If the old function is no-throw, so is the new one. | |||
617 | if (oldFunction->doesNotThrow()) | |||
618 | newFunction->setDoesNotThrow(); | |||
619 | ||||
620 | // Inherit the uwtable attribute if we need to. | |||
621 | if (oldFunction->hasUWTable()) | |||
622 | newFunction->setHasUWTable(); | |||
623 | ||||
624 | // Inherit all of the target dependent attributes and white-listed | |||
625 | // target independent attributes. | |||
626 | // (e.g. If the extracted region contains a call to an x86.sse | |||
627 | // instruction we need to make sure that the extracted region has the | |||
628 | // "target-features" attribute allowing it to be lowered. | |||
629 | // FIXME: This should be changed to check to see if a specific | |||
630 | // attribute can not be inherited. | |||
631 | for (const auto &Attr : oldFunction->getAttributes().getFnAttributes()) { | |||
632 | if (Attr.isStringAttribute()) { | |||
633 | if (Attr.getKindAsString() == "thunk") | |||
634 | continue; | |||
635 | } else | |||
636 | switch (Attr.getKindAsEnum()) { | |||
637 | // Those attributes cannot be propagated safely. Explicitly list them | |||
638 | // here so we get a warning if new attributes are added. This list also | |||
639 | // includes non-function attributes. | |||
640 | case Attribute::Alignment: | |||
641 | case Attribute::AllocSize: | |||
642 | case Attribute::ArgMemOnly: | |||
643 | case Attribute::Builtin: | |||
644 | case Attribute::ByVal: | |||
645 | case Attribute::Convergent: | |||
646 | case Attribute::Dereferenceable: | |||
647 | case Attribute::DereferenceableOrNull: | |||
648 | case Attribute::InAlloca: | |||
649 | case Attribute::InReg: | |||
650 | case Attribute::InaccessibleMemOnly: | |||
651 | case Attribute::InaccessibleMemOrArgMemOnly: | |||
652 | case Attribute::JumpTable: | |||
653 | case Attribute::Naked: | |||
654 | case Attribute::Nest: | |||
655 | case Attribute::NoAlias: | |||
656 | case Attribute::NoBuiltin: | |||
657 | case Attribute::NoCapture: | |||
658 | case Attribute::NoReturn: | |||
659 | case Attribute::None: | |||
660 | case Attribute::NonNull: | |||
661 | case Attribute::ReadNone: | |||
662 | case Attribute::ReadOnly: | |||
663 | case Attribute::Returned: | |||
664 | case Attribute::ReturnsTwice: | |||
665 | case Attribute::SExt: | |||
666 | case Attribute::Speculatable: | |||
667 | case Attribute::StackAlignment: | |||
668 | case Attribute::StructRet: | |||
669 | case Attribute::SwiftError: | |||
670 | case Attribute::SwiftSelf: | |||
671 | case Attribute::WriteOnly: | |||
672 | case Attribute::ZExt: | |||
673 | case Attribute::EndAttrKinds: | |||
674 | continue; | |||
675 | // Those attributes should be safe to propagate to the extracted function. | |||
676 | case Attribute::AlwaysInline: | |||
677 | case Attribute::Cold: | |||
678 | case Attribute::NoRecurse: | |||
679 | case Attribute::InlineHint: | |||
680 | case Attribute::MinSize: | |||
681 | case Attribute::NoDuplicate: | |||
682 | case Attribute::NoImplicitFloat: | |||
683 | case Attribute::NoInline: | |||
684 | case Attribute::NonLazyBind: | |||
685 | case Attribute::NoRedZone: | |||
686 | case Attribute::NoUnwind: | |||
687 | case Attribute::OptimizeNone: | |||
688 | case Attribute::OptimizeForSize: | |||
689 | case Attribute::SafeStack: | |||
690 | case Attribute::SanitizeAddress: | |||
691 | case Attribute::SanitizeMemory: | |||
692 | case Attribute::SanitizeThread: | |||
693 | case Attribute::SanitizeHWAddress: | |||
694 | case Attribute::StackProtect: | |||
695 | case Attribute::StackProtectReq: | |||
696 | case Attribute::StackProtectStrong: | |||
697 | case Attribute::StrictFP: | |||
698 | case Attribute::UWTable: | |||
699 | break; | |||
700 | } | |||
701 | ||||
702 | newFunction->addFnAttr(Attr); | |||
703 | } | |||
704 | newFunction->getBasicBlockList().push_back(newRootNode); | |||
705 | ||||
706 | // Create an iterator to name all of the arguments we inserted. | |||
707 | Function::arg_iterator AI = newFunction->arg_begin(); | |||
708 | ||||
709 | // Rewrite all users of the inputs in the extracted region to use the | |||
710 | // arguments (or appropriate addressing into struct) instead. | |||
711 | for (unsigned i = 0, e = inputs.size(); i != e; ++i) { | |||
712 | Value *RewriteVal; | |||
713 | if (AggregateArgs) { | |||
714 | Value *Idx[2]; | |||
715 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext())); | |||
716 | Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i); | |||
717 | TerminatorInst *TI = newFunction->begin()->getTerminator(); | |||
718 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
| ||||
719 | StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI); | |||
720 | RewriteVal = new LoadInst(GEP, "loadgep_" + inputs[i]->getName(), TI); | |||
721 | } else | |||
722 | RewriteVal = &*AI++; | |||
723 | ||||
724 | std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end()); | |||
725 | for (User *use : Users) | |||
726 | if (Instruction *inst = dyn_cast<Instruction>(use)) | |||
727 | if (Blocks.count(inst->getParent())) | |||
728 | inst->replaceUsesOfWith(inputs[i], RewriteVal); | |||
729 | } | |||
730 | ||||
731 | // Set names for input and output arguments. | |||
732 | if (!AggregateArgs) { | |||
733 | AI = newFunction->arg_begin(); | |||
734 | for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI) | |||
735 | AI->setName(inputs[i]->getName()); | |||
736 | for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI) | |||
737 | AI->setName(outputs[i]->getName()+".out"); | |||
738 | } | |||
739 | ||||
740 | // Rewrite branches to basic blocks outside of the loop to new dummy blocks | |||
741 | // within the new function. This must be done before we lose track of which | |||
742 | // blocks were originally in the code region. | |||
743 | std::vector<User *> Users(header->user_begin(), header->user_end()); | |||
744 | for (unsigned i = 0, e = Users.size(); i != e; ++i) | |||
745 | // The BasicBlock which contains the branch is not in the region | |||
746 | // modify the branch target to a new block | |||
747 | if (TerminatorInst *TI = dyn_cast<TerminatorInst>(Users[i])) | |||
748 | if (!Blocks.count(TI->getParent()) && | |||
749 | TI->getParent()->getParent() == oldFunction) | |||
750 | TI->replaceUsesOfWith(header, newHeader); | |||
751 | ||||
752 | return newFunction; | |||
753 | } | |||
754 | ||||
755 | /// emitCallAndSwitchStatement - This method sets up the caller side by adding | |||
756 | /// the call instruction, splitting any PHI nodes in the header block as | |||
757 | /// necessary. | |||
758 | void CodeExtractor:: | |||
759 | emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, | |||
760 | ValueSet &inputs, ValueSet &outputs) { | |||
761 | // Emit a call to the new function, passing in: *pointer to struct (if | |||
762 | // aggregating parameters), or plan inputs and allocated memory for outputs | |||
763 | std::vector<Value *> params, StructValues, ReloadOutputs, Reloads; | |||
764 | ||||
765 | Module *M = newFunction->getParent(); | |||
766 | LLVMContext &Context = M->getContext(); | |||
767 | const DataLayout &DL = M->getDataLayout(); | |||
768 | ||||
769 | // Add inputs as params, or to be filled into the struct | |||
770 | for (Value *input : inputs) | |||
771 | if (AggregateArgs) | |||
772 | StructValues.push_back(input); | |||
773 | else | |||
774 | params.push_back(input); | |||
775 | ||||
776 | // Create allocas for the outputs | |||
777 | for (Value *output : outputs) { | |||
778 | if (AggregateArgs) { | |||
779 | StructValues.push_back(output); | |||
780 | } else { | |||
781 | AllocaInst *alloca = | |||
782 | new AllocaInst(output->getType(), DL.getAllocaAddrSpace(), | |||
783 | nullptr, output->getName() + ".loc", | |||
784 | &codeReplacer->getParent()->front().front()); | |||
785 | ReloadOutputs.push_back(alloca); | |||
786 | params.push_back(alloca); | |||
787 | } | |||
788 | } | |||
789 | ||||
790 | StructType *StructArgTy = nullptr; | |||
791 | AllocaInst *Struct = nullptr; | |||
792 | if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { | |||
793 | std::vector<Type *> ArgTypes; | |||
794 | for (ValueSet::iterator v = StructValues.begin(), | |||
795 | ve = StructValues.end(); v != ve; ++v) | |||
796 | ArgTypes.push_back((*v)->getType()); | |||
797 | ||||
798 | // Allocate a struct at the beginning of this function | |||
799 | StructArgTy = StructType::get(newFunction->getContext(), ArgTypes); | |||
800 | Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr, | |||
801 | "structArg", | |||
802 | &codeReplacer->getParent()->front().front()); | |||
803 | params.push_back(Struct); | |||
804 | ||||
805 | for (unsigned i = 0, e = inputs.size(); i != e; ++i) { | |||
806 | Value *Idx[2]; | |||
807 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); | |||
808 | Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i); | |||
809 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
810 | StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName()); | |||
811 | codeReplacer->getInstList().push_back(GEP); | |||
812 | StoreInst *SI = new StoreInst(StructValues[i], GEP); | |||
813 | codeReplacer->getInstList().push_back(SI); | |||
814 | } | |||
815 | } | |||
816 | ||||
817 | // Emit the call to the function | |||
818 | CallInst *call = CallInst::Create(newFunction, params, | |||
819 | NumExitBlocks > 1 ? "targetBlock" : ""); | |||
820 | // Add debug location to the new call, if the original function has debug | |||
821 | // info. In that case, the terminator of the entry block of the extracted | |||
822 | // function contains the first debug location of the extracted function, | |||
823 | // set in extractCodeRegion. | |||
824 | if (codeReplacer->getParent()->getSubprogram()) { | |||
825 | if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc()) | |||
826 | call->setDebugLoc(DL); | |||
827 | } | |||
828 | codeReplacer->getInstList().push_back(call); | |||
829 | ||||
830 | Function::arg_iterator OutputArgBegin = newFunction->arg_begin(); | |||
831 | unsigned FirstOut = inputs.size(); | |||
832 | if (!AggregateArgs) | |||
833 | std::advance(OutputArgBegin, inputs.size()); | |||
834 | ||||
835 | // Reload the outputs passed in by reference. | |||
836 | Function::arg_iterator OAI = OutputArgBegin; | |||
837 | for (unsigned i = 0, e = outputs.size(); i != e; ++i) { | |||
838 | Value *Output = nullptr; | |||
839 | if (AggregateArgs) { | |||
840 | Value *Idx[2]; | |||
841 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); | |||
842 | Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); | |||
843 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
844 | StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName()); | |||
845 | codeReplacer->getInstList().push_back(GEP); | |||
846 | Output = GEP; | |||
847 | } else { | |||
848 | Output = ReloadOutputs[i]; | |||
849 | } | |||
850 | LoadInst *load = new LoadInst(Output, outputs[i]->getName()+".reload"); | |||
851 | Reloads.push_back(load); | |||
852 | codeReplacer->getInstList().push_back(load); | |||
853 | std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end()); | |||
854 | for (unsigned u = 0, e = Users.size(); u != e; ++u) { | |||
855 | Instruction *inst = cast<Instruction>(Users[u]); | |||
856 | if (!Blocks.count(inst->getParent())) | |||
857 | inst->replaceUsesOfWith(outputs[i], load); | |||
858 | } | |||
859 | ||||
860 | // Store to argument right after the definition of output value. | |||
861 | auto *OutI = dyn_cast<Instruction>(outputs[i]); | |||
862 | if (!OutI) | |||
863 | continue; | |||
864 | // Find proper insertion point. | |||
865 | Instruction *InsertPt = OutI->getNextNode(); | |||
866 | // Let's assume that there is no other guy interleave non-PHI in PHIs. | |||
867 | if (isa<PHINode>(InsertPt)) | |||
868 | InsertPt = InsertPt->getParent()->getFirstNonPHI(); | |||
869 | ||||
870 | assert(OAI != newFunction->arg_end() &&(static_cast <bool> (OAI != newFunction->arg_end() && "Number of output arguments should match " "the amount of defined values" ) ? void (0) : __assert_fail ("OAI != newFunction->arg_end() && \"Number of output arguments should match \" \"the amount of defined values\"" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 872, __extension__ __PRETTY_FUNCTION__)) | |||
871 | "Number of output arguments should match "(static_cast <bool> (OAI != newFunction->arg_end() && "Number of output arguments should match " "the amount of defined values" ) ? void (0) : __assert_fail ("OAI != newFunction->arg_end() && \"Number of output arguments should match \" \"the amount of defined values\"" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 872, __extension__ __PRETTY_FUNCTION__)) | |||
872 | "the amount of defined values")(static_cast <bool> (OAI != newFunction->arg_end() && "Number of output arguments should match " "the amount of defined values" ) ? void (0) : __assert_fail ("OAI != newFunction->arg_end() && \"Number of output arguments should match \" \"the amount of defined values\"" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 872, __extension__ __PRETTY_FUNCTION__)); | |||
873 | if (AggregateArgs) { | |||
874 | Value *Idx[2]; | |||
875 | Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); | |||
876 | Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); | |||
877 | GetElementPtrInst *GEP = GetElementPtrInst::Create( | |||
878 | StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(), InsertPt); | |||
879 | new StoreInst(outputs[i], GEP, InsertPt); | |||
880 | // Since there should be only one struct argument aggregating | |||
881 | // all the output values, we shouldn't increment OAI, which always | |||
882 | // points to the struct argument, in this case. | |||
883 | } else { | |||
884 | new StoreInst(outputs[i], &*OAI, InsertPt); | |||
885 | ++OAI; | |||
886 | } | |||
887 | } | |||
888 | ||||
889 | // Now we can emit a switch statement using the call as a value. | |||
890 | SwitchInst *TheSwitch = | |||
891 | SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)), | |||
892 | codeReplacer, 0, codeReplacer); | |||
893 | ||||
894 | // Since there may be multiple exits from the original region, make the new | |||
895 | // function return an unsigned, switch on that number. This loop iterates | |||
896 | // over all of the blocks in the extracted region, updating any terminator | |||
897 | // instructions in the to-be-extracted region that branch to blocks that are | |||
898 | // not in the region to be extracted. | |||
899 | std::map<BasicBlock *, BasicBlock *> ExitBlockMap; | |||
900 | ||||
901 | unsigned switchVal = 0; | |||
902 | for (BasicBlock *Block : Blocks) { | |||
903 | TerminatorInst *TI = Block->getTerminator(); | |||
904 | for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) | |||
905 | if (!Blocks.count(TI->getSuccessor(i))) { | |||
906 | BasicBlock *OldTarget = TI->getSuccessor(i); | |||
907 | // add a new basic block which returns the appropriate value | |||
908 | BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; | |||
909 | if (!NewTarget) { | |||
910 | // If we don't already have an exit stub for this non-extracted | |||
911 | // destination, create one now! | |||
912 | NewTarget = BasicBlock::Create(Context, | |||
913 | OldTarget->getName() + ".exitStub", | |||
914 | newFunction); | |||
915 | unsigned SuccNum = switchVal++; | |||
916 | ||||
917 | Value *brVal = nullptr; | |||
918 | switch (NumExitBlocks) { | |||
919 | case 0: | |||
920 | case 1: break; // No value needed. | |||
921 | case 2: // Conditional branch, return a bool | |||
922 | brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum); | |||
923 | break; | |||
924 | default: | |||
925 | brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum); | |||
926 | break; | |||
927 | } | |||
928 | ||||
929 | ReturnInst::Create(Context, brVal, NewTarget); | |||
930 | ||||
931 | // Update the switch instruction. | |||
932 | TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context), | |||
933 | SuccNum), | |||
934 | OldTarget); | |||
935 | } | |||
936 | ||||
937 | // rewrite the original branch instruction with this new target | |||
938 | TI->setSuccessor(i, NewTarget); | |||
939 | } | |||
940 | } | |||
941 | ||||
942 | // Now that we've done the deed, simplify the switch instruction. | |||
943 | Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); | |||
944 | switch (NumExitBlocks) { | |||
945 | case 0: | |||
946 | // There are no successors (the block containing the switch itself), which | |||
947 | // means that previously this was the last part of the function, and hence | |||
948 | // this should be rewritten as a `ret' | |||
949 | ||||
950 | // Check if the function should return a value | |||
951 | if (OldFnRetTy->isVoidTy()) { | |||
952 | ReturnInst::Create(Context, nullptr, TheSwitch); // Return void | |||
953 | } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) { | |||
954 | // return what we have | |||
955 | ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch); | |||
956 | } else { | |||
957 | // Otherwise we must have code extracted an unwind or something, just | |||
958 | // return whatever we want. | |||
959 | ReturnInst::Create(Context, | |||
960 | Constant::getNullValue(OldFnRetTy), TheSwitch); | |||
961 | } | |||
962 | ||||
963 | TheSwitch->eraseFromParent(); | |||
964 | break; | |||
965 | case 1: | |||
966 | // Only a single destination, change the switch into an unconditional | |||
967 | // branch. | |||
968 | BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch); | |||
969 | TheSwitch->eraseFromParent(); | |||
970 | break; | |||
971 | case 2: | |||
972 | BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), | |||
973 | call, TheSwitch); | |||
974 | TheSwitch->eraseFromParent(); | |||
975 | break; | |||
976 | default: | |||
977 | // Otherwise, make the default destination of the switch instruction be one | |||
978 | // of the other successors. | |||
979 | TheSwitch->setCondition(call); | |||
980 | TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks)); | |||
981 | // Remove redundant case | |||
982 | TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1)); | |||
983 | break; | |||
984 | } | |||
985 | } | |||
986 | ||||
987 | void CodeExtractor::moveCodeToFunction(Function *newFunction) { | |||
988 | Function *oldFunc = (*Blocks.begin())->getParent(); | |||
989 | Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); | |||
990 | Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); | |||
991 | ||||
992 | for (BasicBlock *Block : Blocks) { | |||
993 | // Delete the basic block from the old function, and the list of blocks | |||
994 | oldBlocks.remove(Block); | |||
995 | ||||
996 | // Insert this basic block into the new function | |||
997 | newBlocks.push_back(Block); | |||
998 | } | |||
999 | } | |||
1000 | ||||
1001 | void CodeExtractor::calculateNewCallTerminatorWeights( | |||
1002 | BasicBlock *CodeReplacer, | |||
1003 | DenseMap<BasicBlock *, BlockFrequency> &ExitWeights, | |||
1004 | BranchProbabilityInfo *BPI) { | |||
1005 | using Distribution = BlockFrequencyInfoImplBase::Distribution; | |||
1006 | using BlockNode = BlockFrequencyInfoImplBase::BlockNode; | |||
1007 | ||||
1008 | // Update the branch weights for the exit block. | |||
1009 | TerminatorInst *TI = CodeReplacer->getTerminator(); | |||
1010 | SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0); | |||
1011 | ||||
1012 | // Block Frequency distribution with dummy node. | |||
1013 | Distribution BranchDist; | |||
1014 | ||||
1015 | // Add each of the frequencies of the successors. | |||
1016 | for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) { | |||
1017 | BlockNode ExitNode(i); | |||
1018 | uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency(); | |||
1019 | if (ExitFreq != 0) | |||
1020 | BranchDist.addExit(ExitNode, ExitFreq); | |||
1021 | else | |||
1022 | BPI->setEdgeProbability(CodeReplacer, i, BranchProbability::getZero()); | |||
1023 | } | |||
1024 | ||||
1025 | // Check for no total weight. | |||
1026 | if (BranchDist.Total == 0) | |||
1027 | return; | |||
1028 | ||||
1029 | // Normalize the distribution so that they can fit in unsigned. | |||
1030 | BranchDist.normalize(); | |||
1031 | ||||
1032 | // Create normalized branch weights and set the metadata. | |||
1033 | for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) { | |||
1034 | const auto &Weight = BranchDist.Weights[I]; | |||
1035 | ||||
1036 | // Get the weight and update the current BFI. | |||
1037 | BranchWeights[Weight.TargetNode.Index] = Weight.Amount; | |||
1038 | BranchProbability BP(Weight.Amount, BranchDist.Total); | |||
1039 | BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP); | |||
1040 | } | |||
1041 | TI->setMetadata( | |||
1042 | LLVMContext::MD_prof, | |||
1043 | MDBuilder(TI->getContext()).createBranchWeights(BranchWeights)); | |||
1044 | } | |||
1045 | ||||
1046 | Function *CodeExtractor::extractCodeRegion() { | |||
1047 | if (!isEligible()) | |||
1048 | return nullptr; | |||
1049 | ||||
1050 | // Assumption: this is a single-entry code region, and the header is the first | |||
1051 | // block in the region. | |||
1052 | BasicBlock *header = *Blocks.begin(); | |||
1053 | Function *oldFunction = header->getParent(); | |||
1054 | ||||
1055 | // For functions with varargs, check that varargs handling is only done in the | |||
1056 | // outlined function, i.e vastart and vaend are only used in outlined blocks. | |||
1057 | if (AllowVarArgs && oldFunction->getFunctionType()->isVarArg()) { | |||
1058 | auto containsVarArgIntrinsic = [](Instruction &I) { | |||
1059 | if (const CallInst *CI = dyn_cast<CallInst>(&I)) | |||
1060 | if (const Function *F = CI->getCalledFunction()) | |||
1061 | return F->getIntrinsicID() == Intrinsic::vastart || | |||
1062 | F->getIntrinsicID() == Intrinsic::vaend; | |||
1063 | return false; | |||
1064 | }; | |||
1065 | ||||
1066 | for (auto &BB : *oldFunction) { | |||
1067 | if (Blocks.count(&BB)) | |||
1068 | continue; | |||
1069 | if (llvm::any_of(BB, containsVarArgIntrinsic)) | |||
1070 | return nullptr; | |||
1071 | } | |||
1072 | } | |||
1073 | ValueSet inputs, outputs, SinkingCands, HoistingCands; | |||
1074 | BasicBlock *CommonExit = nullptr; | |||
1075 | ||||
1076 | // Calculate the entry frequency of the new function before we change the root | |||
1077 | // block. | |||
1078 | BlockFrequency EntryFreq; | |||
1079 | if (BFI) { | |||
1080 | assert(BPI && "Both BPI and BFI are required to preserve profile info")(static_cast <bool> (BPI && "Both BPI and BFI are required to preserve profile info" ) ? void (0) : __assert_fail ("BPI && \"Both BPI and BFI are required to preserve profile info\"" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 1080, __extension__ __PRETTY_FUNCTION__)); | |||
1081 | for (BasicBlock *Pred : predecessors(header)) { | |||
1082 | if (Blocks.count(Pred)) | |||
1083 | continue; | |||
1084 | EntryFreq += | |||
1085 | BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header); | |||
1086 | } | |||
1087 | } | |||
1088 | ||||
1089 | // If we have to split PHI nodes or the entry block, do so now. | |||
1090 | severSplitPHINodes(header); | |||
1091 | ||||
1092 | // If we have any return instructions in the region, split those blocks so | |||
1093 | // that the return is not in the region. | |||
1094 | splitReturnBlocks(); | |||
1095 | ||||
1096 | // This takes place of the original loop | |||
1097 | BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(), | |||
1098 | "codeRepl", oldFunction, | |||
1099 | header); | |||
1100 | ||||
1101 | // The new function needs a root node because other nodes can branch to the | |||
1102 | // head of the region, but the entry node of a function cannot have preds. | |||
1103 | BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(), | |||
1104 | "newFuncRoot"); | |||
1105 | auto *BranchI = BranchInst::Create(header); | |||
1106 | // If the original function has debug info, we have to add a debug location | |||
1107 | // to the new branch instruction from the artificial entry block. | |||
1108 | // We use the debug location of the first instruction in the extracted | |||
1109 | // blocks, as there is no other equivalent line in the source code. | |||
1110 | if (oldFunction->getSubprogram()) { | |||
1111 | any_of(Blocks, [&BranchI](const BasicBlock *BB) { | |||
1112 | return any_of(*BB, [&BranchI](const Instruction &I) { | |||
1113 | if (!I.getDebugLoc()) | |||
1114 | return false; | |||
1115 | BranchI->setDebugLoc(I.getDebugLoc()); | |||
1116 | return true; | |||
1117 | }); | |||
1118 | }); | |||
1119 | } | |||
1120 | newFuncRoot->getInstList().push_back(BranchI); | |||
1121 | ||||
1122 | findAllocas(SinkingCands, HoistingCands, CommonExit); | |||
1123 | assert(HoistingCands.empty() || CommonExit)(static_cast <bool> (HoistingCands.empty() || CommonExit ) ? void (0) : __assert_fail ("HoistingCands.empty() || CommonExit" , "/build/llvm-toolchain-snapshot-7~svn326551/lib/Transforms/Utils/CodeExtractor.cpp" , 1123, __extension__ __PRETTY_FUNCTION__)); | |||
1124 | ||||
1125 | // Find inputs to, outputs from the code region. | |||
1126 | findInputsOutputs(inputs, outputs, SinkingCands); | |||
1127 | ||||
1128 | // Now sink all instructions which only have non-phi uses inside the region | |||
1129 | for (auto *II : SinkingCands) | |||
1130 | cast<Instruction>(II)->moveBefore(*newFuncRoot, | |||
1131 | newFuncRoot->getFirstInsertionPt()); | |||
1132 | ||||
1133 | if (!HoistingCands.empty()) { | |||
1134 | auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit); | |||
1135 | Instruction *TI = HoistToBlock->getTerminator(); | |||
1136 | for (auto *II : HoistingCands) | |||
1137 | cast<Instruction>(II)->moveBefore(TI); | |||
1138 | } | |||
1139 | ||||
1140 | // Calculate the exit blocks for the extracted region and the total exit | |||
1141 | // weights for each of those blocks. | |||
1142 | DenseMap<BasicBlock *, BlockFrequency> ExitWeights; | |||
1143 | SmallPtrSet<BasicBlock *, 1> ExitBlocks; | |||
1144 | for (BasicBlock *Block : Blocks) { | |||
1145 | for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE; | |||
1146 | ++SI) { | |||
1147 | if (!Blocks.count(*SI)) { | |||
1148 | // Update the branch weight for this successor. | |||
1149 | if (BFI) { | |||
1150 | BlockFrequency &BF = ExitWeights[*SI]; | |||
1151 | BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI); | |||
1152 | } | |||
1153 | ExitBlocks.insert(*SI); | |||
1154 | } | |||
1155 | } | |||
1156 | } | |||
1157 | NumExitBlocks = ExitBlocks.size(); | |||
1158 | ||||
1159 | // Construct new function based on inputs/outputs & add allocas for all defs. | |||
1160 | Function *newFunction = constructFunction(inputs, outputs, header, | |||
1161 | newFuncRoot, | |||
1162 | codeReplacer, oldFunction, | |||
1163 | oldFunction->getParent()); | |||
1164 | ||||
1165 | // Update the entry count of the function. | |||
1166 | if (BFI) { | |||
1167 | auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency()); | |||
1168 | if (Count.hasValue()) | |||
1169 | newFunction->setEntryCount( | |||
1170 | ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME | |||
1171 | BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency()); | |||
1172 | } | |||
1173 | ||||
1174 | emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); | |||
1175 | ||||
1176 | moveCodeToFunction(newFunction); | |||
1177 | ||||
1178 | // Update the branch weights for the exit block. | |||
1179 | if (BFI && NumExitBlocks > 1) | |||
1180 | calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI); | |||
1181 | ||||
1182 | // Loop over all of the PHI nodes in the header block, and change any | |||
1183 | // references to the old incoming edge to be the new incoming edge. | |||
1184 | for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) { | |||
1185 | PHINode *PN = cast<PHINode>(I); | |||
1186 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |||
1187 | if (!Blocks.count(PN->getIncomingBlock(i))) | |||
1188 | PN->setIncomingBlock(i, newFuncRoot); | |||
1189 | } | |||
1190 | ||||
1191 | // Look at all successors of the codeReplacer block. If any of these blocks | |||
1192 | // had PHI nodes in them, we need to update the "from" block to be the code | |||
1193 | // replacer, not the original block in the extracted region. | |||
1194 | std::vector<BasicBlock *> Succs(succ_begin(codeReplacer), | |||
1195 | succ_end(codeReplacer)); | |||
1196 | for (unsigned i = 0, e = Succs.size(); i != e; ++i) | |||
1197 | for (BasicBlock::iterator I = Succs[i]->begin(); isa<PHINode>(I); ++I) { | |||
1198 | PHINode *PN = cast<PHINode>(I); | |||
1199 | std::set<BasicBlock*> ProcessedPreds; | |||
1200 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |||
1201 | if (Blocks.count(PN->getIncomingBlock(i))) { | |||
1202 | if (ProcessedPreds.insert(PN->getIncomingBlock(i)).second) | |||
1203 | PN->setIncomingBlock(i, codeReplacer); | |||
1204 | else { | |||
1205 | // There were multiple entries in the PHI for this block, now there | |||
1206 | // is only one, so remove the duplicated entries. | |||
1207 | PN->removeIncomingValue(i, false); | |||
1208 | --i; --e; | |||
1209 | } | |||
1210 | } | |||
1211 | } | |||
1212 | ||||
1213 | DEBUG(if (verifyFunction(*newFunction))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { if (verifyFunction(*newFunction)) report_fatal_error ("verifyFunction failed!"); } } while (false) | |||
1214 | report_fatal_error("verifyFunction failed!"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("code-extractor")) { if (verifyFunction(*newFunction)) report_fatal_error ("verifyFunction failed!"); } } while (false); | |||
1215 | return newFunction; | |||
1216 | } |