Bug Summary

File:lib/Transforms/Utils/CodeExtractor.cpp
Warning:line 846, column 32
1st function call argument is an uninitialized value

Annotated Source Code

Press '?' to see keyboard shortcuts

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