Bug Summary

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