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