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