Bug Summary

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