1 //===- CodeExtractor.cpp - Pull code region into a new function -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
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"
70 #define DEBUG_TYPE "code-extractor"
72 // Provide a command-line option to aggregate function arguments into a struct
73 // for functions produced by the code extractor. This is useful when converting
74 // extracted functions to pthread-based code, as only one argument (void*) can
75 // be passed in to pthread_create().
77 AggregateArgsOpt("aggregate-extracted-args", cl::Hidden,
78 cl::desc("Aggregate arguments to code-extracted functions"));
80 /// \brief Test whether a block is valid for extraction.
81 bool CodeExtractor::isBlockValidForExtraction(const BasicBlock &BB,
83 // Landing pads must be in the function where they were inserted for cleanup.
86 // taking the address of a basic block moved to another function is illegal
87 if (BB.hasAddressTaken())
90 // don't hoist code that uses another basicblock address, as it's likely to
91 // lead to unexpected behavior, like cross-function jumps
92 SmallPtrSet<User const *, 16> Visited;
93 SmallVector<User const *, 16> ToVisit;
95 for (Instruction const &Inst : BB)
96 ToVisit.push_back(&Inst);
98 while (!ToVisit.empty()) {
99 User const *Curr = ToVisit.pop_back_val();
100 if (!Visited.insert(Curr).second)
102 if (isa<BlockAddress const>(Curr))
103 return false; // even a reference to self is likely to be not compatible
105 if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB)
108 for (auto const &U : Curr->operands()) {
109 if (auto *UU = dyn_cast<User>(U))
110 ToVisit.push_back(UU);
114 // Don't hoist code containing allocas or invokes. If explicitly requested,
116 for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) {
117 if (isa<AllocaInst>(I) || isa<InvokeInst>(I))
119 if (const CallInst *CI = dyn_cast<CallInst>(I))
120 if (const Function *F = CI->getCalledFunction())
121 if (F->getIntrinsicID() == Intrinsic::vastart) {
132 /// \brief Build a set of blocks to extract if the input blocks are viable.
133 static SetVector<BasicBlock *>
134 buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
136 assert(!BBs.empty() && "The set of blocks to extract must be non-empty");
137 SetVector<BasicBlock *> Result;
139 // Loop over the blocks, adding them to our set-vector, and aborting with an
140 // empty set if we encounter invalid blocks.
141 for (BasicBlock *BB : BBs) {
142 // If this block is dead, don't process it.
143 if (DT && !DT->isReachableFromEntry(BB))
146 if (!Result.insert(BB))
147 llvm_unreachable("Repeated basic blocks in extraction input");
148 if (!CodeExtractor::isBlockValidForExtraction(*BB, AllowVarArgs)) {
155 for (SetVector<BasicBlock *>::iterator I = std::next(Result.begin()),
158 for (pred_iterator PI = pred_begin(*I), PE = pred_end(*I);
160 assert(Result.count(*PI) &&
161 "No blocks in this region may have entries from outside the region"
162 " except for the first block!");
168 CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
169 bool AggregateArgs, BlockFrequencyInfo *BFI,
170 BranchProbabilityInfo *BPI, bool AllowVarArgs)
171 : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
172 BPI(BPI), AllowVarArgs(AllowVarArgs),
173 Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs)) {}
175 CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs,
176 BlockFrequencyInfo *BFI,
177 BranchProbabilityInfo *BPI)
178 : DT(&DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
179 BPI(BPI), AllowVarArgs(false),
180 Blocks(buildExtractionBlockSet(L.getBlocks(), &DT,
181 /* AllowVarArgs */ false)) {}
183 /// definedInRegion - Return true if the specified value is defined in the
184 /// extracted region.
185 static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) {
186 if (Instruction *I = dyn_cast<Instruction>(V))
187 if (Blocks.count(I->getParent()))
192 /// definedInCaller - Return true if the specified value is defined in the
193 /// function being code extracted, but not in the region being extracted.
194 /// These values must be passed in as live-ins to the function.
195 static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) {
196 if (isa<Argument>(V)) return true;
197 if (Instruction *I = dyn_cast<Instruction>(V))
198 if (!Blocks.count(I->getParent()))
203 static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) {
204 BasicBlock *CommonExitBlock = nullptr;
205 auto hasNonCommonExitSucc = [&](BasicBlock *Block) {
206 for (auto *Succ : successors(Block)) {
207 // Internal edges, ok.
208 if (Blocks.count(Succ))
210 if (!CommonExitBlock) {
211 CommonExitBlock = Succ;
214 if (CommonExitBlock == Succ)
222 if (any_of(Blocks, hasNonCommonExitSucc))
225 return CommonExitBlock;
228 bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(
229 Instruction *Addr) const {
230 AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets());
231 Function *Func = (*Blocks.begin())->getParent();
232 for (BasicBlock &BB : *Func) {
233 if (Blocks.count(&BB))
235 for (Instruction &II : BB) {
236 if (isa<DbgInfoIntrinsic>(II))
239 unsigned Opcode = II.getOpcode();
240 Value *MemAddr = nullptr;
242 case Instruction::Store:
243 case Instruction::Load: {
244 if (Opcode == Instruction::Store) {
245 StoreInst *SI = cast<StoreInst>(&II);
246 MemAddr = SI->getPointerOperand();
248 LoadInst *LI = cast<LoadInst>(&II);
249 MemAddr = LI->getPointerOperand();
251 // Global variable can not be aliased with locals.
252 if (dyn_cast<Constant>(MemAddr))
254 Value *Base = MemAddr->stripInBoundsConstantOffsets();
255 if (!dyn_cast<AllocaInst>(Base) || Base == AI)
260 IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II);
262 if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start ||
263 IntrInst->getIntrinsicID() == Intrinsic::lifetime_end)
267 // Treat all the other cases conservatively if it has side effects.
268 if (II.mayHaveSideEffects())
279 CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) {
280 BasicBlock *SinglePredFromOutlineRegion = nullptr;
281 assert(!Blocks.count(CommonExitBlock) &&
282 "Expect a block outside the region!");
283 for (auto *Pred : predecessors(CommonExitBlock)) {
284 if (!Blocks.count(Pred))
286 if (!SinglePredFromOutlineRegion) {
287 SinglePredFromOutlineRegion = Pred;
288 } else if (SinglePredFromOutlineRegion != Pred) {
289 SinglePredFromOutlineRegion = nullptr;
294 if (SinglePredFromOutlineRegion)
295 return SinglePredFromOutlineRegion;
298 auto getFirstPHI = [](BasicBlock *BB) {
299 BasicBlock::iterator I = BB->begin();
300 PHINode *FirstPhi = nullptr;
301 while (I != BB->end()) {
302 PHINode *Phi = dyn_cast<PHINode>(I);
312 // If there are any phi nodes, the single pred either exists or has already
313 // be created before code extraction.
314 assert(!getFirstPHI(CommonExitBlock) && "Phi not expected");
317 BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock(
318 CommonExitBlock->getFirstNonPHI()->getIterator());
320 for (auto PI = pred_begin(CommonExitBlock), PE = pred_end(CommonExitBlock);
322 BasicBlock *Pred = *PI++;
323 if (Blocks.count(Pred))
325 Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock);
327 // Now add the old exit block to the outline region.
328 Blocks.insert(CommonExitBlock);
329 return CommonExitBlock;
332 void CodeExtractor::findAllocas(ValueSet &SinkCands, ValueSet &HoistCands,
333 BasicBlock *&ExitBlock) const {
334 Function *Func = (*Blocks.begin())->getParent();
335 ExitBlock = getCommonExitBlock(Blocks);
337 for (BasicBlock &BB : *Func) {
338 if (Blocks.count(&BB))
340 for (Instruction &II : BB) {
341 auto *AI = dyn_cast<AllocaInst>(&II);
345 // Find the pair of life time markers for address 'Addr' that are either
346 // defined inside the outline region or can legally be shrinkwrapped into
347 // the outline region. If there are not other untracked uses of the
348 // address, return the pair of markers if found; otherwise return a pair
350 auto GetLifeTimeMarkers =
351 [&](Instruction *Addr, bool &SinkLifeStart,
352 bool &HoistLifeEnd) -> std::pair<Instruction *, Instruction *> {
353 Instruction *LifeStart = nullptr, *LifeEnd = nullptr;
355 for (User *U : Addr->users()) {
356 IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U);
358 if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) {
359 // Do not handle the case where AI has multiple start markers.
361 return std::make_pair<Instruction *>(nullptr, nullptr);
362 LifeStart = IntrInst;
364 if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) {
366 return std::make_pair<Instruction *>(nullptr, nullptr);
371 // Find untracked uses of the address, bail.
372 if (!definedInRegion(Blocks, U))
373 return std::make_pair<Instruction *>(nullptr, nullptr);
376 if (!LifeStart || !LifeEnd)
377 return std::make_pair<Instruction *>(nullptr, nullptr);
379 SinkLifeStart = !definedInRegion(Blocks, LifeStart);
380 HoistLifeEnd = !definedInRegion(Blocks, LifeEnd);
381 // Do legality Check.
382 if ((SinkLifeStart || HoistLifeEnd) &&
383 !isLegalToShrinkwrapLifetimeMarkers(Addr))
384 return std::make_pair<Instruction *>(nullptr, nullptr);
386 // Check to see if we have a place to do hoisting, if not, bail.
387 if (HoistLifeEnd && !ExitBlock)
388 return std::make_pair<Instruction *>(nullptr, nullptr);
390 return std::make_pair(LifeStart, LifeEnd);
393 bool SinkLifeStart = false, HoistLifeEnd = false;
394 auto Markers = GetLifeTimeMarkers(AI, SinkLifeStart, HoistLifeEnd);
398 SinkCands.insert(Markers.first);
399 SinkCands.insert(AI);
401 HoistCands.insert(Markers.second);
405 // Follow the bitcast.
406 Instruction *MarkerAddr = nullptr;
407 for (User *U : AI->users()) {
408 if (U->stripInBoundsConstantOffsets() == AI) {
409 SinkLifeStart = false;
410 HoistLifeEnd = false;
411 Instruction *Bitcast = cast<Instruction>(U);
412 Markers = GetLifeTimeMarkers(Bitcast, SinkLifeStart, HoistLifeEnd);
414 MarkerAddr = Bitcast;
419 // Found unknown use of AI.
420 if (!definedInRegion(Blocks, U)) {
421 MarkerAddr = nullptr;
428 SinkCands.insert(Markers.first);
429 if (!definedInRegion(Blocks, MarkerAddr))
430 SinkCands.insert(MarkerAddr);
431 SinkCands.insert(AI);
433 HoistCands.insert(Markers.second);
439 void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
440 const ValueSet &SinkCands) const {
441 for (BasicBlock *BB : Blocks) {
442 // If a used value is defined outside the region, it's an input. If an
443 // instruction is used outside the region, it's an output.
444 for (Instruction &II : *BB) {
445 for (User::op_iterator OI = II.op_begin(), OE = II.op_end(); OI != OE;
448 if (!SinkCands.count(V) && definedInCaller(Blocks, V))
452 for (User *U : II.users())
453 if (!definedInRegion(Blocks, U)) {
461 /// severSplitPHINodes - If a PHI node has multiple inputs from outside of the
462 /// region, we need to split the entry block of the region so that the PHI node
463 /// is easier to deal with.
464 void CodeExtractor::severSplitPHINodes(BasicBlock *&Header) {
465 unsigned NumPredsFromRegion = 0;
466 unsigned NumPredsOutsideRegion = 0;
468 if (Header != &Header->getParent()->getEntryBlock()) {
469 PHINode *PN = dyn_cast<PHINode>(Header->begin());
470 if (!PN) return; // No PHI nodes.
472 // If the header node contains any PHI nodes, check to see if there is more
473 // than one entry from outside the region. If so, we need to sever the
474 // header block into two.
475 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
476 if (Blocks.count(PN->getIncomingBlock(i)))
477 ++NumPredsFromRegion;
479 ++NumPredsOutsideRegion;
481 // If there is one (or fewer) predecessor from outside the region, we don't
482 // need to do anything special.
483 if (NumPredsOutsideRegion <= 1) return;
486 // Otherwise, we need to split the header block into two pieces: one
487 // containing PHI nodes merging values from outside of the region, and a
488 // second that contains all of the code for the block and merges back any
489 // incoming values from inside of the region.
490 BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT);
492 // We only want to code extract the second block now, and it becomes the new
493 // header of the region.
494 BasicBlock *OldPred = Header;
495 Blocks.remove(OldPred);
496 Blocks.insert(NewBB);
499 // Okay, now we need to adjust the PHI nodes and any branches from within the
500 // region to go to the new header block instead of the old header block.
501 if (NumPredsFromRegion) {
502 PHINode *PN = cast<PHINode>(OldPred->begin());
503 // Loop over all of the predecessors of OldPred that are in the region,
504 // changing them to branch to NewBB instead.
505 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
506 if (Blocks.count(PN->getIncomingBlock(i))) {
507 TerminatorInst *TI = PN->getIncomingBlock(i)->getTerminator();
508 TI->replaceUsesOfWith(OldPred, NewBB);
511 // Okay, everything within the region is now branching to the right block, we
512 // just have to update the PHI nodes now, inserting PHI nodes into NewBB.
513 BasicBlock::iterator AfterPHIs;
514 for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) {
515 PHINode *PN = cast<PHINode>(AfterPHIs);
516 // Create a new PHI node in the new region, which has an incoming value
517 // from OldPred of PN.
518 PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion,
519 PN->getName() + ".ce", &NewBB->front());
520 PN->replaceAllUsesWith(NewPN);
521 NewPN->addIncoming(PN, OldPred);
523 // Loop over all of the incoming value in PN, moving them to NewPN if they
524 // are from the extracted region.
525 for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
526 if (Blocks.count(PN->getIncomingBlock(i))) {
527 NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i));
528 PN->removeIncomingValue(i);
536 void CodeExtractor::splitReturnBlocks() {
537 for (BasicBlock *Block : Blocks)
538 if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) {
540 Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret");
542 // Old dominates New. New node dominates all other nodes dominated
544 DomTreeNode *OldNode = DT->getNode(Block);
545 SmallVector<DomTreeNode *, 8> Children(OldNode->begin(),
548 DomTreeNode *NewNode = DT->addNewBlock(New, Block);
550 for (DomTreeNode *I : Children)
551 DT->changeImmediateDominator(I, NewNode);
556 /// constructFunction - make a function based on inputs and outputs, as follows:
557 /// f(in0, ..., inN, out0, ..., outN)
558 Function *CodeExtractor::constructFunction(const ValueSet &inputs,
559 const ValueSet &outputs,
561 BasicBlock *newRootNode,
562 BasicBlock *newHeader,
563 Function *oldFunction,
565 DEBUG(dbgs() << "inputs: " << inputs.size() << "\n");
566 DEBUG(dbgs() << "outputs: " << outputs.size() << "\n");
568 // This function returns unsigned, outputs will go back by reference.
569 switch (NumExitBlocks) {
571 case 1: RetTy = Type::getVoidTy(header->getContext()); break;
572 case 2: RetTy = Type::getInt1Ty(header->getContext()); break;
573 default: RetTy = Type::getInt16Ty(header->getContext()); break;
576 std::vector<Type *> paramTy;
578 // Add the types of the input values to the function's argument list
579 for (Value *value : inputs) {
580 DEBUG(dbgs() << "value used in func: " << *value << "\n");
581 paramTy.push_back(value->getType());
584 // Add the types of the output values to the function's argument list.
585 for (Value *output : outputs) {
586 DEBUG(dbgs() << "instr used in func: " << *output << "\n");
588 paramTy.push_back(output->getType());
590 paramTy.push_back(PointerType::getUnqual(output->getType()));
594 dbgs() << "Function type: " << *RetTy << " f(";
595 for (Type *i : paramTy)
596 dbgs() << *i << ", ";
600 StructType *StructTy;
601 if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
602 StructTy = StructType::get(M->getContext(), paramTy);
604 paramTy.push_back(PointerType::getUnqual(StructTy));
606 FunctionType *funcType =
607 FunctionType::get(RetTy, paramTy,
608 AllowVarArgs && oldFunction->isVarArg());
610 // Create the new function
611 Function *newFunction = Function::Create(funcType,
612 GlobalValue::InternalLinkage,
613 oldFunction->getName() + "_" +
614 header->getName(), M);
615 // If the old function is no-throw, so is the new one.
616 if (oldFunction->doesNotThrow())
617 newFunction->setDoesNotThrow();
619 // Inherit the uwtable attribute if we need to.
620 if (oldFunction->hasUWTable())
621 newFunction->setHasUWTable();
623 // Inherit all of the target dependent attributes.
624 // (e.g. If the extracted region contains a call to an x86.sse
625 // instruction we need to make sure that the extracted region has the
626 // "target-features" attribute allowing it to be lowered.
627 // FIXME: This should be changed to check to see if a specific
628 // attribute can not be inherited.
629 AttrBuilder AB(oldFunction->getAttributes().getFnAttributes());
630 for (const auto &Attr : AB.td_attrs())
631 newFunction->addFnAttr(Attr.first, Attr.second);
633 newFunction->getBasicBlockList().push_back(newRootNode);
635 // Create an iterator to name all of the arguments we inserted.
636 Function::arg_iterator AI = newFunction->arg_begin();
638 // Rewrite all users of the inputs in the extracted region to use the
639 // arguments (or appropriate addressing into struct) instead.
640 for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
644 Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext()));
645 Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i);
646 TerminatorInst *TI = newFunction->begin()->getTerminator();
647 GetElementPtrInst *GEP = GetElementPtrInst::Create(
648 StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI);
649 RewriteVal = new LoadInst(GEP, "loadgep_" + inputs[i]->getName(), TI);
653 std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
654 for (User *use : Users)
655 if (Instruction *inst = dyn_cast<Instruction>(use))
656 if (Blocks.count(inst->getParent()))
657 inst->replaceUsesOfWith(inputs[i], RewriteVal);
660 // Set names for input and output arguments.
661 if (!AggregateArgs) {
662 AI = newFunction->arg_begin();
663 for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI)
664 AI->setName(inputs[i]->getName());
665 for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI)
666 AI->setName(outputs[i]->getName()+".out");
669 // Rewrite branches to basic blocks outside of the loop to new dummy blocks
670 // within the new function. This must be done before we lose track of which
671 // blocks were originally in the code region.
672 std::vector<User *> Users(header->user_begin(), header->user_end());
673 for (unsigned i = 0, e = Users.size(); i != e; ++i)
674 // The BasicBlock which contains the branch is not in the region
675 // modify the branch target to a new block
676 if (TerminatorInst *TI = dyn_cast<TerminatorInst>(Users[i]))
677 if (!Blocks.count(TI->getParent()) &&
678 TI->getParent()->getParent() == oldFunction)
679 TI->replaceUsesOfWith(header, newHeader);
684 /// emitCallAndSwitchStatement - This method sets up the caller side by adding
685 /// the call instruction, splitting any PHI nodes in the header block as
688 emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer,
689 ValueSet &inputs, ValueSet &outputs) {
690 // Emit a call to the new function, passing in: *pointer to struct (if
691 // aggregating parameters), or plan inputs and allocated memory for outputs
692 std::vector<Value *> params, StructValues, ReloadOutputs, Reloads;
694 Module *M = newFunction->getParent();
695 LLVMContext &Context = M->getContext();
696 const DataLayout &DL = M->getDataLayout();
698 // Add inputs as params, or to be filled into the struct
699 for (Value *input : inputs)
701 StructValues.push_back(input);
703 params.push_back(input);
705 // Create allocas for the outputs
706 for (Value *output : outputs) {
708 StructValues.push_back(output);
711 new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
712 nullptr, output->getName() + ".loc",
713 &codeReplacer->getParent()->front().front());
714 ReloadOutputs.push_back(alloca);
715 params.push_back(alloca);
719 StructType *StructArgTy = nullptr;
720 AllocaInst *Struct = nullptr;
721 if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
722 std::vector<Type *> ArgTypes;
723 for (ValueSet::iterator v = StructValues.begin(),
724 ve = StructValues.end(); v != ve; ++v)
725 ArgTypes.push_back((*v)->getType());
727 // Allocate a struct at the beginning of this function
728 StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
729 Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr,
731 &codeReplacer->getParent()->front().front());
732 params.push_back(Struct);
734 for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
736 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
737 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i);
738 GetElementPtrInst *GEP = GetElementPtrInst::Create(
739 StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
740 codeReplacer->getInstList().push_back(GEP);
741 StoreInst *SI = new StoreInst(StructValues[i], GEP);
742 codeReplacer->getInstList().push_back(SI);
746 // Emit the call to the function
747 CallInst *call = CallInst::Create(newFunction, params,
748 NumExitBlocks > 1 ? "targetBlock" : "");
749 // Add debug location to the new call, if the original function has debug
750 // info. In that case, the terminator of the entry block of the extracted
751 // function contains the first debug location of the extracted function,
752 // set in extractCodeRegion.
753 if (codeReplacer->getParent()->getSubprogram()) {
754 if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
755 call->setDebugLoc(DL);
757 codeReplacer->getInstList().push_back(call);
759 Function::arg_iterator OutputArgBegin = newFunction->arg_begin();
760 unsigned FirstOut = inputs.size();
762 std::advance(OutputArgBegin, inputs.size());
764 // Reload the outputs passed in by reference.
765 Function::arg_iterator OAI = OutputArgBegin;
766 for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
767 Value *Output = nullptr;
770 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
771 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
772 GetElementPtrInst *GEP = GetElementPtrInst::Create(
773 StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
774 codeReplacer->getInstList().push_back(GEP);
777 Output = ReloadOutputs[i];
779 LoadInst *load = new LoadInst(Output, outputs[i]->getName()+".reload");
780 Reloads.push_back(load);
781 codeReplacer->getInstList().push_back(load);
782 std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
783 for (unsigned u = 0, e = Users.size(); u != e; ++u) {
784 Instruction *inst = cast<Instruction>(Users[u]);
785 if (!Blocks.count(inst->getParent()))
786 inst->replaceUsesOfWith(outputs[i], load);
789 // Store to argument right after the definition of output value.
790 auto *OutI = dyn_cast<Instruction>(outputs[i]);
793 // Find proper insertion point.
794 Instruction *InsertPt = OutI->getNextNode();
795 // Let's assume that there is no other guy interleave non-PHI in PHIs.
796 if (isa<PHINode>(InsertPt))
797 InsertPt = InsertPt->getParent()->getFirstNonPHI();
799 assert(OAI != newFunction->arg_end() &&
800 "Number of output arguments should match "
801 "the amount of defined values");
804 Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
805 Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
806 GetElementPtrInst *GEP = GetElementPtrInst::Create(
807 StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(), InsertPt);
808 new StoreInst(outputs[i], GEP, InsertPt);
809 // Since there should be only one struct argument aggregating
810 // all the output values, we shouldn't increment OAI, which always
811 // points to the struct argument, in this case.
813 new StoreInst(outputs[i], &*OAI, InsertPt);
818 // Now we can emit a switch statement using the call as a value.
819 SwitchInst *TheSwitch =
820 SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)),
821 codeReplacer, 0, codeReplacer);
823 // Since there may be multiple exits from the original region, make the new
824 // function return an unsigned, switch on that number. This loop iterates
825 // over all of the blocks in the extracted region, updating any terminator
826 // instructions in the to-be-extracted region that branch to blocks that are
827 // not in the region to be extracted.
828 std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
830 unsigned switchVal = 0;
831 for (BasicBlock *Block : Blocks) {
832 TerminatorInst *TI = Block->getTerminator();
833 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
834 if (!Blocks.count(TI->getSuccessor(i))) {
835 BasicBlock *OldTarget = TI->getSuccessor(i);
836 // add a new basic block which returns the appropriate value
837 BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
839 // If we don't already have an exit stub for this non-extracted
840 // destination, create one now!
841 NewTarget = BasicBlock::Create(Context,
842 OldTarget->getName() + ".exitStub",
844 unsigned SuccNum = switchVal++;
846 Value *brVal = nullptr;
847 switch (NumExitBlocks) {
849 case 1: break; // No value needed.
850 case 2: // Conditional branch, return a bool
851 brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
854 brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
858 ReturnInst::Create(Context, brVal, NewTarget);
860 // Update the switch instruction.
861 TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context),
866 // rewrite the original branch instruction with this new target
867 TI->setSuccessor(i, NewTarget);
871 // Now that we've done the deed, simplify the switch instruction.
872 Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
873 switch (NumExitBlocks) {
875 // There are no successors (the block containing the switch itself), which
876 // means that previously this was the last part of the function, and hence
877 // this should be rewritten as a `ret'
879 // Check if the function should return a value
880 if (OldFnRetTy->isVoidTy()) {
881 ReturnInst::Create(Context, nullptr, TheSwitch); // Return void
882 } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {
883 // return what we have
884 ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch);
886 // Otherwise we must have code extracted an unwind or something, just
887 // return whatever we want.
888 ReturnInst::Create(Context,
889 Constant::getNullValue(OldFnRetTy), TheSwitch);
892 TheSwitch->eraseFromParent();
895 // Only a single destination, change the switch into an unconditional
897 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch);
898 TheSwitch->eraseFromParent();
901 BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
903 TheSwitch->eraseFromParent();
906 // Otherwise, make the default destination of the switch instruction be one
907 // of the other successors.
908 TheSwitch->setCondition(call);
909 TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
910 // Remove redundant case
911 TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
916 void CodeExtractor::moveCodeToFunction(Function *newFunction) {
917 Function *oldFunc = (*Blocks.begin())->getParent();
918 Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList();
919 Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList();
921 for (BasicBlock *Block : Blocks) {
922 // Delete the basic block from the old function, and the list of blocks
923 oldBlocks.remove(Block);
925 // Insert this basic block into the new function
926 newBlocks.push_back(Block);
930 void CodeExtractor::calculateNewCallTerminatorWeights(
931 BasicBlock *CodeReplacer,
932 DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
933 BranchProbabilityInfo *BPI) {
934 using Distribution = BlockFrequencyInfoImplBase::Distribution;
935 using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
937 // Update the branch weights for the exit block.
938 TerminatorInst *TI = CodeReplacer->getTerminator();
939 SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);
941 // Block Frequency distribution with dummy node.
942 Distribution BranchDist;
944 // Add each of the frequencies of the successors.
945 for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
946 BlockNode ExitNode(i);
947 uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
949 BranchDist.addExit(ExitNode, ExitFreq);
951 BPI->setEdgeProbability(CodeReplacer, i, BranchProbability::getZero());
954 // Check for no total weight.
955 if (BranchDist.Total == 0)
958 // Normalize the distribution so that they can fit in unsigned.
959 BranchDist.normalize();
961 // Create normalized branch weights and set the metadata.
962 for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
963 const auto &Weight = BranchDist.Weights[I];
965 // Get the weight and update the current BFI.
966 BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
967 BranchProbability BP(Weight.Amount, BranchDist.Total);
968 BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP);
971 LLVMContext::MD_prof,
972 MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
975 Function *CodeExtractor::extractCodeRegion() {
979 // Assumption: this is a single-entry code region, and the header is the first
980 // block in the region.
981 BasicBlock *header = *Blocks.begin();
982 Function *oldFunction = header->getParent();
984 // For functions with varargs, check that varargs handling is only done in the
985 // outlined function, i.e vastart and vaend are only used in outlined blocks.
986 if (AllowVarArgs && oldFunction->getFunctionType()->isVarArg()) {
987 auto containsVarArgIntrinsic = [](Instruction &I) {
988 if (const CallInst *CI = dyn_cast<CallInst>(&I))
989 if (const Function *F = CI->getCalledFunction())
990 return F->getIntrinsicID() == Intrinsic::vastart ||
991 F->getIntrinsicID() == Intrinsic::vaend;
995 for (auto &BB : *oldFunction) {
996 if (Blocks.count(&BB))
998 if (llvm::any_of(BB, containsVarArgIntrinsic))
1002 ValueSet inputs, outputs, SinkingCands, HoistingCands;
1003 BasicBlock *CommonExit = nullptr;
1005 // Calculate the entry frequency of the new function before we change the root
1007 BlockFrequency EntryFreq;
1009 assert(BPI && "Both BPI and BFI are required to preserve profile info");
1010 for (BasicBlock *Pred : predecessors(header)) {
1011 if (Blocks.count(Pred))
1014 BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
1018 // If we have to split PHI nodes or the entry block, do so now.
1019 severSplitPHINodes(header);
1021 // If we have any return instructions in the region, split those blocks so
1022 // that the return is not in the region.
1023 splitReturnBlocks();
1025 // This takes place of the original loop
1026 BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
1027 "codeRepl", oldFunction,
1030 // The new function needs a root node because other nodes can branch to the
1031 // head of the region, but the entry node of a function cannot have preds.
1032 BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
1034 auto *BranchI = BranchInst::Create(header);
1035 // If the original function has debug info, we have to add a debug location
1036 // to the new branch instruction from the artificial entry block.
1037 // We use the debug location of the first instruction in the extracted
1038 // blocks, as there is no other equivalent line in the source code.
1039 if (oldFunction->getSubprogram()) {
1040 any_of(Blocks, [&BranchI](const BasicBlock *BB) {
1041 return any_of(*BB, [&BranchI](const Instruction &I) {
1042 if (!I.getDebugLoc())
1044 BranchI->setDebugLoc(I.getDebugLoc());
1049 newFuncRoot->getInstList().push_back(BranchI);
1051 findAllocas(SinkingCands, HoistingCands, CommonExit);
1052 assert(HoistingCands.empty() || CommonExit);
1054 // Find inputs to, outputs from the code region.
1055 findInputsOutputs(inputs, outputs, SinkingCands);
1057 // Now sink all instructions which only have non-phi uses inside the region
1058 for (auto *II : SinkingCands)
1059 cast<Instruction>(II)->moveBefore(*newFuncRoot,
1060 newFuncRoot->getFirstInsertionPt());
1062 if (!HoistingCands.empty()) {
1063 auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
1064 Instruction *TI = HoistToBlock->getTerminator();
1065 for (auto *II : HoistingCands)
1066 cast<Instruction>(II)->moveBefore(TI);
1069 // Calculate the exit blocks for the extracted region and the total exit
1070 // weights for each of those blocks.
1071 DenseMap<BasicBlock *, BlockFrequency> ExitWeights;
1072 SmallPtrSet<BasicBlock *, 1> ExitBlocks;
1073 for (BasicBlock *Block : Blocks) {
1074 for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE;
1076 if (!Blocks.count(*SI)) {
1077 // Update the branch weight for this successor.
1079 BlockFrequency &BF = ExitWeights[*SI];
1080 BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI);
1082 ExitBlocks.insert(*SI);
1086 NumExitBlocks = ExitBlocks.size();
1088 // Construct new function based on inputs/outputs & add allocas for all defs.
1089 Function *newFunction = constructFunction(inputs, outputs, header,
1091 codeReplacer, oldFunction,
1092 oldFunction->getParent());
1094 // Update the entry count of the function.
1096 Optional<uint64_t> EntryCount =
1097 BFI->getProfileCountFromFreq(EntryFreq.getFrequency());
1098 if (EntryCount.hasValue())
1099 newFunction->setEntryCount(EntryCount.getValue());
1100 BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency());
1103 emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1105 moveCodeToFunction(newFunction);
1107 // Update the branch weights for the exit block.
1108 if (BFI && NumExitBlocks > 1)
1109 calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1111 // Loop over all of the PHI nodes in the header block, and change any
1112 // references to the old incoming edge to be the new incoming edge.
1113 for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {
1114 PHINode *PN = cast<PHINode>(I);
1115 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1116 if (!Blocks.count(PN->getIncomingBlock(i)))
1117 PN->setIncomingBlock(i, newFuncRoot);
1120 // Look at all successors of the codeReplacer block. If any of these blocks
1121 // had PHI nodes in them, we need to update the "from" block to be the code
1122 // replacer, not the original block in the extracted region.
1123 std::vector<BasicBlock *> Succs(succ_begin(codeReplacer),
1124 succ_end(codeReplacer));
1125 for (unsigned i = 0, e = Succs.size(); i != e; ++i)
1126 for (BasicBlock::iterator I = Succs[i]->begin(); isa<PHINode>(I); ++I) {
1127 PHINode *PN = cast<PHINode>(I);
1128 std::set<BasicBlock*> ProcessedPreds;
1129 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1130 if (Blocks.count(PN->getIncomingBlock(i))) {
1131 if (ProcessedPreds.insert(PN->getIncomingBlock(i)).second)
1132 PN->setIncomingBlock(i, codeReplacer);
1134 // There were multiple entries in the PHI for this block, now there
1135 // is only one, so remove the duplicated entries.
1136 PN->removeIncomingValue(i, false);
1142 DEBUG(if (verifyFunction(*newFunction))
1143 report_fatal_error("verifyFunction failed!"));