InlineFunction.cpp revision 1edbd6f3f07176851cb03f7932ff50b9e9619dfb
1ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner//===- InlineFunction.cpp - Code to perform function inlining -------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 10ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// This file implements inlining of a function into a call site, resolving 11ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// parameters and the return value as appropriate. 12ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 13a3de16bc8f36638d5444e3e7b0112998af54f826John McCall// The code in this file for handling inlines through invoke 14a3de16bc8f36638d5444e3e7b0112998af54f826John McCall// instructions preserves semantics only under some assumptions about 15a3de16bc8f36638d5444e3e7b0112998af54f826John McCall// the behavior of unwinders which correspond to gcc-style libUnwind 16a3de16bc8f36638d5444e3e7b0112998af54f826John McCall// exception personality functions. Eventually the IR will be 17a3de16bc8f36638d5444e3e7b0112998af54f826John McCall// improved to make this unnecessary, but until then, this code is 18a3de16bc8f36638d5444e3e7b0112998af54f826John McCall// marked [LIBUNWIND]. 19a3de16bc8f36638d5444e3e7b0112998af54f826John McCall// 20ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner//===----------------------------------------------------------------------===// 21ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 22ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner#include "llvm/Transforms/Utils/Cloning.h" 233787e765facfad5ea62753922d940bcdd52afd57Chris Lattner#include "llvm/Constants.h" 247152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner#include "llvm/DerivedTypes.h" 25ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner#include "llvm/Module.h" 2680a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner#include "llvm/Instructions.h" 27517576d6f96a0acde9bab79553d89f4ceba20cf6Devang Patel#include "llvm/IntrinsicInst.h" 2880a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner#include "llvm/Intrinsics.h" 29eaf42abab6d465c38891345d999255871cf03943Devang Patel#include "llvm/Attributes.h" 30468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner#include "llvm/Analysis/CallGraph.h" 31517576d6f96a0acde9bab79553d89f4ceba20cf6Devang Patel#include "llvm/Analysis/DebugInfo.h" 326fb881c036c32728c4a128d81b6083457e534e09Duncan Sands#include "llvm/Analysis/InstructionSimplify.h" 33c93adca35856d0eaae088e52ba30cfefbd7ad910Chris Lattner#include "llvm/Target/TargetData.h" 347569d79de1bd97a6a17b81340ea6ce97d8a3c279Chris Lattner#include "llvm/Transforms/Utils/Local.h" 3593e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner#include "llvm/ADT/SmallVector.h" 36641ca93cff0f957fc5fb9dfb05d2a4a340aa8af7Devang Patel#include "llvm/ADT/StringExtras.h" 3780a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner#include "llvm/Support/CallSite.h" 386d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky#include "llvm/Support/IRBuilder.h" 39f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 40ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 4160915146f4d35e12f10dcdaa155596fac79184daChris Lattnerbool llvm::InlineFunction(CallInst *CI, InlineFunctionInfo &IFI) { 4260915146f4d35e12f10dcdaa155596fac79184daChris Lattner return InlineFunction(CallSite(CI), IFI); 43468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner} 4460915146f4d35e12f10dcdaa155596fac79184daChris Lattnerbool llvm::InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI) { 4560915146f4d35e12f10dcdaa155596fac79184daChris Lattner return InlineFunction(CallSite(II), IFI); 46468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner} 4780a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner 48d7c10862016939c9850cadfe5e1c35513c0adf28John McCall/// [LIBUNWIND] Find the (possibly absent) call to @llvm.eh.selector in 49d7c10862016939c9850cadfe5e1c35513c0adf28John McCall/// the given landing pad. 50d7c10862016939c9850cadfe5e1c35513c0adf28John McCallstatic EHSelectorInst *findSelectorForLandingPad(BasicBlock *lpad) { 51d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // The llvm.eh.exception call is required to be in the landing pad. 52d7c10862016939c9850cadfe5e1c35513c0adf28John McCall for (BasicBlock::iterator i = lpad->begin(), e = lpad->end(); i != e; i++) { 53d7c10862016939c9850cadfe5e1c35513c0adf28John McCall EHExceptionInst *exn = dyn_cast<EHExceptionInst>(i); 54d7c10862016939c9850cadfe5e1c35513c0adf28John McCall if (!exn) continue; 55d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 56d7c10862016939c9850cadfe5e1c35513c0adf28John McCall EHSelectorInst *selector = 0; 57d7c10862016939c9850cadfe5e1c35513c0adf28John McCall for (Instruction::use_iterator 58d7c10862016939c9850cadfe5e1c35513c0adf28John McCall ui = exn->use_begin(), ue = exn->use_end(); ui != ue; ++ui) { 59d7c10862016939c9850cadfe5e1c35513c0adf28John McCall EHSelectorInst *sel = dyn_cast<EHSelectorInst>(*ui); 60d7c10862016939c9850cadfe5e1c35513c0adf28John McCall if (!sel) continue; 61d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 62d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // Immediately accept an eh.selector in the landing pad. 63d7c10862016939c9850cadfe5e1c35513c0adf28John McCall if (sel->getParent() == lpad) return sel; 64d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 65d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // Otherwise, use the first selector we see. 66d7c10862016939c9850cadfe5e1c35513c0adf28John McCall if (!selector) selector = sel; 67d7c10862016939c9850cadfe5e1c35513c0adf28John McCall } 68d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 69d7c10862016939c9850cadfe5e1c35513c0adf28John McCall return selector; 70d7c10862016939c9850cadfe5e1c35513c0adf28John McCall } 71d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 72d7c10862016939c9850cadfe5e1c35513c0adf28John McCall return 0; 73d7c10862016939c9850cadfe5e1c35513c0adf28John McCall} 74d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 75a3de16bc8f36638d5444e3e7b0112998af54f826John McCallnamespace { 76a3de16bc8f36638d5444e3e7b0112998af54f826John McCall /// A class for recording information about inlining through an invoke. 77a3de16bc8f36638d5444e3e7b0112998af54f826John McCall class InvokeInliningInfo { 78d7c10862016939c9850cadfe5e1c35513c0adf28John McCall BasicBlock *OuterUnwindDest; 79d7c10862016939c9850cadfe5e1c35513c0adf28John McCall EHSelectorInst *OuterSelector; 80d7c10862016939c9850cadfe5e1c35513c0adf28John McCall BasicBlock *InnerUnwindDest; 81d7c10862016939c9850cadfe5e1c35513c0adf28John McCall PHINode *InnerExceptionPHI; 82d7c10862016939c9850cadfe5e1c35513c0adf28John McCall PHINode *InnerSelectorPHI; 83a3de16bc8f36638d5444e3e7b0112998af54f826John McCall SmallVector<Value*, 8> UnwindDestPHIValues; 84a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 85a3de16bc8f36638d5444e3e7b0112998af54f826John McCall public: 86d7c10862016939c9850cadfe5e1c35513c0adf28John McCall InvokeInliningInfo(InvokeInst *II) : 87d7c10862016939c9850cadfe5e1c35513c0adf28John McCall OuterUnwindDest(II->getUnwindDest()), OuterSelector(0), 88d7c10862016939c9850cadfe5e1c35513c0adf28John McCall InnerUnwindDest(0), InnerExceptionPHI(0), InnerSelectorPHI(0) { 89d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 90a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // If there are PHI nodes in the unwind destination block, we 91a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // need to keep track of which values came into them from the 92a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // invoke before removing the edge from this block. 93d7c10862016939c9850cadfe5e1c35513c0adf28John McCall llvm::BasicBlock *invokeBB = II->getParent(); 94d7c10862016939c9850cadfe5e1c35513c0adf28John McCall for (BasicBlock::iterator I = OuterUnwindDest->begin(); 95d7c10862016939c9850cadfe5e1c35513c0adf28John McCall isa<PHINode>(I); ++I) { 96a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // Save the value to use for this edge. 97d7c10862016939c9850cadfe5e1c35513c0adf28John McCall PHINode *phi = cast<PHINode>(I); 98d7c10862016939c9850cadfe5e1c35513c0adf28John McCall UnwindDestPHIValues.push_back(phi->getIncomingValueForBlock(invokeBB)); 99a3de16bc8f36638d5444e3e7b0112998af54f826John McCall } 100a3de16bc8f36638d5444e3e7b0112998af54f826John McCall } 101a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 102d7c10862016939c9850cadfe5e1c35513c0adf28John McCall /// The outer unwind destination is the target of unwind edges 103d7c10862016939c9850cadfe5e1c35513c0adf28John McCall /// introduced for calls within the inlined function. 104d7c10862016939c9850cadfe5e1c35513c0adf28John McCall BasicBlock *getOuterUnwindDest() const { 105d7c10862016939c9850cadfe5e1c35513c0adf28John McCall return OuterUnwindDest; 106a3de16bc8f36638d5444e3e7b0112998af54f826John McCall } 107a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 108d7c10862016939c9850cadfe5e1c35513c0adf28John McCall EHSelectorInst *getOuterSelector() { 109d7c10862016939c9850cadfe5e1c35513c0adf28John McCall if (!OuterSelector) 110d7c10862016939c9850cadfe5e1c35513c0adf28John McCall OuterSelector = findSelectorForLandingPad(OuterUnwindDest); 111d7c10862016939c9850cadfe5e1c35513c0adf28John McCall return OuterSelector; 112d7c10862016939c9850cadfe5e1c35513c0adf28John McCall } 113d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 114d7c10862016939c9850cadfe5e1c35513c0adf28John McCall BasicBlock *getInnerUnwindDest(); 115d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 116d7c10862016939c9850cadfe5e1c35513c0adf28John McCall bool forwardEHResume(CallInst *call, BasicBlock *src); 117d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 118a3de16bc8f36638d5444e3e7b0112998af54f826John McCall /// Add incoming-PHI values to the unwind destination block for 119a3de16bc8f36638d5444e3e7b0112998af54f826John McCall /// the given basic block, using the values for the original 120a3de16bc8f36638d5444e3e7b0112998af54f826John McCall /// invoke's source block. 121a3de16bc8f36638d5444e3e7b0112998af54f826John McCall void addIncomingPHIValuesFor(BasicBlock *BB) const { 122d7c10862016939c9850cadfe5e1c35513c0adf28John McCall addIncomingPHIValuesForInto(BB, OuterUnwindDest); 123d7c10862016939c9850cadfe5e1c35513c0adf28John McCall } 124d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 125d7c10862016939c9850cadfe5e1c35513c0adf28John McCall void addIncomingPHIValuesForInto(BasicBlock *src, BasicBlock *dest) const { 126d7c10862016939c9850cadfe5e1c35513c0adf28John McCall BasicBlock::iterator I = dest->begin(); 127a3de16bc8f36638d5444e3e7b0112998af54f826John McCall for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) { 128d7c10862016939c9850cadfe5e1c35513c0adf28John McCall PHINode *phi = cast<PHINode>(I); 129d7c10862016939c9850cadfe5e1c35513c0adf28John McCall phi->addIncoming(UnwindDestPHIValues[i], src); 130a3de16bc8f36638d5444e3e7b0112998af54f826John McCall } 131a3de16bc8f36638d5444e3e7b0112998af54f826John McCall } 132a3de16bc8f36638d5444e3e7b0112998af54f826John McCall }; 133a3de16bc8f36638d5444e3e7b0112998af54f826John McCall} 134a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 135d7c10862016939c9850cadfe5e1c35513c0adf28John McCall/// Replace all the instruction uses of a value with a different value. 136d7c10862016939c9850cadfe5e1c35513c0adf28John McCall/// This has the advantage of not screwing up the CallGraph. 137d7c10862016939c9850cadfe5e1c35513c0adf28John McCallstatic void replaceAllInsnUsesWith(Instruction *insn, Value *replacement) { 138d7c10862016939c9850cadfe5e1c35513c0adf28John McCall for (Value::use_iterator i = insn->use_begin(), e = insn->use_end(); 139d7c10862016939c9850cadfe5e1c35513c0adf28John McCall i != e; ) { 140d7c10862016939c9850cadfe5e1c35513c0adf28John McCall Use &use = i.getUse(); 141d7c10862016939c9850cadfe5e1c35513c0adf28John McCall ++i; 142d7c10862016939c9850cadfe5e1c35513c0adf28John McCall if (isa<Instruction>(use.getUser())) 143d7c10862016939c9850cadfe5e1c35513c0adf28John McCall use.set(replacement); 144d7c10862016939c9850cadfe5e1c35513c0adf28John McCall } 145a3de16bc8f36638d5444e3e7b0112998af54f826John McCall} 146a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 147d7c10862016939c9850cadfe5e1c35513c0adf28John McCall/// Get or create a target for the branch out of rewritten calls to 148d7c10862016939c9850cadfe5e1c35513c0adf28John McCall/// llvm.eh.resume. 149d7c10862016939c9850cadfe5e1c35513c0adf28John McCallBasicBlock *InvokeInliningInfo::getInnerUnwindDest() { 150d7c10862016939c9850cadfe5e1c35513c0adf28John McCall if (InnerUnwindDest) return InnerUnwindDest; 151d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 152d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // Find and hoist the llvm.eh.exception and llvm.eh.selector calls 153d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // in the outer landing pad to immediately following the phis. 154d7c10862016939c9850cadfe5e1c35513c0adf28John McCall EHSelectorInst *selector = getOuterSelector(); 155d7c10862016939c9850cadfe5e1c35513c0adf28John McCall if (!selector) return 0; 156d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 157d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // The call to llvm.eh.exception *must* be in the landing pad. 158d7c10862016939c9850cadfe5e1c35513c0adf28John McCall Instruction *exn = cast<Instruction>(selector->getArgOperand(0)); 159d7c10862016939c9850cadfe5e1c35513c0adf28John McCall assert(exn->getParent() == OuterUnwindDest); 160d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 161d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // TODO: recognize when we've already done this, so that we don't 162d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // get a linear number of these when inlining calls into lots of 163d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // invokes with the same landing pad. 164d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 165d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // Do the hoisting. 166d7c10862016939c9850cadfe5e1c35513c0adf28John McCall Instruction *splitPoint = exn->getParent()->getFirstNonPHI(); 167d7c10862016939c9850cadfe5e1c35513c0adf28John McCall assert(splitPoint != selector && "selector-on-exception dominance broken!"); 168d7c10862016939c9850cadfe5e1c35513c0adf28John McCall if (splitPoint == exn) { 169d7c10862016939c9850cadfe5e1c35513c0adf28John McCall selector->removeFromParent(); 170d7c10862016939c9850cadfe5e1c35513c0adf28John McCall selector->insertAfter(exn); 171d7c10862016939c9850cadfe5e1c35513c0adf28John McCall splitPoint = selector->getNextNode(); 172d7c10862016939c9850cadfe5e1c35513c0adf28John McCall } else { 173d7c10862016939c9850cadfe5e1c35513c0adf28John McCall exn->moveBefore(splitPoint); 174d7c10862016939c9850cadfe5e1c35513c0adf28John McCall selector->moveBefore(splitPoint); 175d7c10862016939c9850cadfe5e1c35513c0adf28John McCall } 176d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 177d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // Split the landing pad. 178d7c10862016939c9850cadfe5e1c35513c0adf28John McCall InnerUnwindDest = OuterUnwindDest->splitBasicBlock(splitPoint, 179d7c10862016939c9850cadfe5e1c35513c0adf28John McCall OuterUnwindDest->getName() + ".body"); 180d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 181d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // The number of incoming edges we expect to the inner landing pad. 182d7c10862016939c9850cadfe5e1c35513c0adf28John McCall const unsigned phiCapacity = 2; 183d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 184d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // Create corresponding new phis for all the phis in the outer landing pad. 185d7c10862016939c9850cadfe5e1c35513c0adf28John McCall BasicBlock::iterator insertPoint = InnerUnwindDest->begin(); 186d7c10862016939c9850cadfe5e1c35513c0adf28John McCall BasicBlock::iterator I = OuterUnwindDest->begin(); 187d7c10862016939c9850cadfe5e1c35513c0adf28John McCall for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) { 188d7c10862016939c9850cadfe5e1c35513c0adf28John McCall PHINode *outerPhi = cast<PHINode>(I); 189d7c10862016939c9850cadfe5e1c35513c0adf28John McCall PHINode *innerPhi = PHINode::Create(outerPhi->getType(), phiCapacity, 190d7c10862016939c9850cadfe5e1c35513c0adf28John McCall outerPhi->getName() + ".lpad-body", 191d7c10862016939c9850cadfe5e1c35513c0adf28John McCall insertPoint); 192a6d7345ec91e4b07671f62d231e7c42f054bc70dJohn McCall outerPhi->replaceAllUsesWith(innerPhi); 193d7c10862016939c9850cadfe5e1c35513c0adf28John McCall innerPhi->addIncoming(outerPhi, OuterUnwindDest); 194d7c10862016939c9850cadfe5e1c35513c0adf28John McCall } 195d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 196d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // Create a phi for the exception value... 197d7c10862016939c9850cadfe5e1c35513c0adf28John McCall InnerExceptionPHI = PHINode::Create(exn->getType(), phiCapacity, 198d7c10862016939c9850cadfe5e1c35513c0adf28John McCall "exn.lpad-body", insertPoint); 199d7c10862016939c9850cadfe5e1c35513c0adf28John McCall replaceAllInsnUsesWith(exn, InnerExceptionPHI); 200d7c10862016939c9850cadfe5e1c35513c0adf28John McCall selector->setArgOperand(0, exn); // restore this use 201d7c10862016939c9850cadfe5e1c35513c0adf28John McCall InnerExceptionPHI->addIncoming(exn, OuterUnwindDest); 202d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 203d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // ...and the selector. 204d7c10862016939c9850cadfe5e1c35513c0adf28John McCall InnerSelectorPHI = PHINode::Create(selector->getType(), phiCapacity, 205d7c10862016939c9850cadfe5e1c35513c0adf28John McCall "selector.lpad-body", insertPoint); 206d7c10862016939c9850cadfe5e1c35513c0adf28John McCall replaceAllInsnUsesWith(selector, InnerSelectorPHI); 207d7c10862016939c9850cadfe5e1c35513c0adf28John McCall InnerSelectorPHI->addIncoming(selector, OuterUnwindDest); 208d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 209d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // All done. 210d7c10862016939c9850cadfe5e1c35513c0adf28John McCall return InnerUnwindDest; 211d7c10862016939c9850cadfe5e1c35513c0adf28John McCall} 212d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 213d7c10862016939c9850cadfe5e1c35513c0adf28John McCall/// [LIBUNWIND] Try to forward the given call, which logically occurs 214d7c10862016939c9850cadfe5e1c35513c0adf28John McCall/// at the end of the given block, as a branch to the inner unwind 215d7c10862016939c9850cadfe5e1c35513c0adf28John McCall/// block. Returns true if the call was forwarded. 216d7c10862016939c9850cadfe5e1c35513c0adf28John McCallbool InvokeInliningInfo::forwardEHResume(CallInst *call, BasicBlock *src) { 2171edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall // First, check whether this is a call to the intrinsic. 218d7c10862016939c9850cadfe5e1c35513c0adf28John McCall Function *fn = dyn_cast<Function>(call->getCalledValue()); 219d7c10862016939c9850cadfe5e1c35513c0adf28John McCall if (!fn || fn->getName() != "llvm.eh.resume") 220d7c10862016939c9850cadfe5e1c35513c0adf28John McCall return false; 2211edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall 2221edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall // At this point, we need to return true on all paths, because 2231edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall // otherwise we'll construct an invoke of the intrinsic, which is 2241edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall // not well-formed. 225d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 2261edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall // Try to find or make an inner unwind dest, which will fail if we 2271edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall // can't find a selector call for the outer unwind dest. 228d7c10862016939c9850cadfe5e1c35513c0adf28John McCall BasicBlock *dest = getInnerUnwindDest(); 2291edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall bool hasSelector = (dest != 0); 2301edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall 2311edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall // If we failed, just use the outer unwind dest, dropping the 2321edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall // exception and selector on the floor. 2331edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall if (!hasSelector) 2341edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall dest = OuterUnwindDest; 235d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 236d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // Make a branch. 237d7c10862016939c9850cadfe5e1c35513c0adf28John McCall BranchInst::Create(dest, src); 238d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 239d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // Update the phis in the destination. They were inserted in an 240d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // order which makes this work. 241d7c10862016939c9850cadfe5e1c35513c0adf28John McCall addIncomingPHIValuesForInto(src, dest); 2421edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall 2431edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall if (hasSelector) { 2441edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall InnerExceptionPHI->addIncoming(call->getArgOperand(0), src); 2451edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall InnerSelectorPHI->addIncoming(call->getArgOperand(1), src); 2461edbd6f3f07176851cb03f7932ff50b9e9619dfbJohn McCall } 247d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 248d7c10862016939c9850cadfe5e1c35513c0adf28John McCall return true; 249a3de16bc8f36638d5444e3e7b0112998af54f826John McCall} 250a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 251a3de16bc8f36638d5444e3e7b0112998af54f826John McCall/// [LIBUNWIND] Check whether this selector is "only cleanups": 252a3de16bc8f36638d5444e3e7b0112998af54f826John McCall/// call i32 @llvm.eh.selector(blah, blah, i32 0) 253a3de16bc8f36638d5444e3e7b0112998af54f826John McCallstatic bool isCleanupOnlySelector(EHSelectorInst *selector) { 254a3de16bc8f36638d5444e3e7b0112998af54f826John McCall if (selector->getNumArgOperands() != 3) return false; 255a3de16bc8f36638d5444e3e7b0112998af54f826John McCall ConstantInt *val = dyn_cast<ConstantInt>(selector->getArgOperand(2)); 256a3de16bc8f36638d5444e3e7b0112998af54f826John McCall return (val && val->isZero()); 257a3de16bc8f36638d5444e3e7b0112998af54f826John McCall} 258135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 259135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner/// HandleCallsInBlockInlinedThroughInvoke - When we inline a basic block into 260f61f89ae14cf332a014a598153137113af34002fEric Christopher/// an invoke, we have to turn all of the calls that can throw into 261135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner/// invokes. This function analyze BB to see if there are any calls, and if so, 262135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner/// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI 26381dfb3885252fbf621b080827a080099864415f8Chris Lattner/// nodes in that block with the values specified in InvokeDestPHIValues. 264135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner/// 265a3de16bc8f36638d5444e3e7b0112998af54f826John McCall/// Returns true to indicate that the next block should be skipped. 266a3de16bc8f36638d5444e3e7b0112998af54f826John McCallstatic bool HandleCallsInBlockInlinedThroughInvoke(BasicBlock *BB, 267a3de16bc8f36638d5444e3e7b0112998af54f826John McCall InvokeInliningInfo &Invoke) { 268135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) { 269135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Instruction *I = BBI++; 270135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 271135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // We only need to check for function calls: inlined invoke 272135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // instructions require no special handling. 273135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner CallInst *CI = dyn_cast<CallInst>(I); 274135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (CI == 0) continue; 275a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 276a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // LIBUNWIND: merge selector instructions. 277a3de16bc8f36638d5444e3e7b0112998af54f826John McCall if (EHSelectorInst *Inner = dyn_cast<EHSelectorInst>(CI)) { 278d7c10862016939c9850cadfe5e1c35513c0adf28John McCall EHSelectorInst *Outer = Invoke.getOuterSelector(); 279a3de16bc8f36638d5444e3e7b0112998af54f826John McCall if (!Outer) continue; 280a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 281a3de16bc8f36638d5444e3e7b0112998af54f826John McCall bool innerIsOnlyCleanup = isCleanupOnlySelector(Inner); 282a3de16bc8f36638d5444e3e7b0112998af54f826John McCall bool outerIsOnlyCleanup = isCleanupOnlySelector(Outer); 283a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 284a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // If both selectors contain only cleanups, we don't need to do 285a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // anything. TODO: this is really just a very specific instance 286a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // of a much more general optimization. 287a3de16bc8f36638d5444e3e7b0112998af54f826John McCall if (innerIsOnlyCleanup && outerIsOnlyCleanup) continue; 288a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 289a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // Otherwise, we just append the outer selector to the inner selector. 290a3de16bc8f36638d5444e3e7b0112998af54f826John McCall SmallVector<Value*, 16> NewSelector; 291a3de16bc8f36638d5444e3e7b0112998af54f826John McCall for (unsigned i = 0, e = Inner->getNumArgOperands(); i != e; ++i) 292a3de16bc8f36638d5444e3e7b0112998af54f826John McCall NewSelector.push_back(Inner->getArgOperand(i)); 293a3de16bc8f36638d5444e3e7b0112998af54f826John McCall for (unsigned i = 2, e = Outer->getNumArgOperands(); i != e; ++i) 294a3de16bc8f36638d5444e3e7b0112998af54f826John McCall NewSelector.push_back(Outer->getArgOperand(i)); 295a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 296a3de16bc8f36638d5444e3e7b0112998af54f826John McCall CallInst *NewInner = CallInst::Create(Inner->getCalledValue(), 297a3de16bc8f36638d5444e3e7b0112998af54f826John McCall NewSelector.begin(), 298a3de16bc8f36638d5444e3e7b0112998af54f826John McCall NewSelector.end(), 299a3de16bc8f36638d5444e3e7b0112998af54f826John McCall "", 300a3de16bc8f36638d5444e3e7b0112998af54f826John McCall Inner); 301a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // No need to copy attributes, calling convention, etc. 302a3de16bc8f36638d5444e3e7b0112998af54f826John McCall NewInner->takeName(Inner); 303a3de16bc8f36638d5444e3e7b0112998af54f826John McCall Inner->replaceAllUsesWith(NewInner); 304a3de16bc8f36638d5444e3e7b0112998af54f826John McCall Inner->eraseFromParent(); 305a3de16bc8f36638d5444e3e7b0112998af54f826John McCall continue; 306a3de16bc8f36638d5444e3e7b0112998af54f826John McCall } 307135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 308135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // If this call cannot unwind, don't convert it to an invoke. 309135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (CI->doesNotThrow()) 310135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 311135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 312135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Convert this function call into an invoke instruction. 313135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // First, split the basic block. 314135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner BasicBlock *Split = BB->splitBasicBlock(CI, CI->getName()+".noexc"); 315a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 316d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // Delete the unconditional branch inserted by splitBasicBlock 317d7c10862016939c9850cadfe5e1c35513c0adf28John McCall BB->getInstList().pop_back(); 318a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 319d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // LIBUNWIND: If this is a call to @llvm.eh.resume, just branch 320a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // directly to the new landing pad. 321d7c10862016939c9850cadfe5e1c35513c0adf28John McCall if (Invoke.forwardEHResume(CI, BB)) { 322a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // TODO: 'Split' is now unreachable; clean it up. 323a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 324a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // We want to leave the original call intact so that the call 325a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // graph and other structures won't get misled. We also have to 326a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // avoid processing the next block, or we'll iterate here forever. 327d7c10862016939c9850cadfe5e1c35513c0adf28John McCall return true; 328d7c10862016939c9850cadfe5e1c35513c0adf28John McCall } 329a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 330a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // Otherwise, create the new invoke instruction. 331d7c10862016939c9850cadfe5e1c35513c0adf28John McCall ImmutableCallSite CS(CI); 332d7c10862016939c9850cadfe5e1c35513c0adf28John McCall SmallVector<Value*, 8> InvokeArgs(CS.arg_begin(), CS.arg_end()); 333d7c10862016939c9850cadfe5e1c35513c0adf28John McCall InvokeInst *II = 334d7c10862016939c9850cadfe5e1c35513c0adf28John McCall InvokeInst::Create(CI->getCalledValue(), Split, 335d7c10862016939c9850cadfe5e1c35513c0adf28John McCall Invoke.getOuterUnwindDest(), 336d7c10862016939c9850cadfe5e1c35513c0adf28John McCall InvokeArgs.begin(), InvokeArgs.end(), 337d7c10862016939c9850cadfe5e1c35513c0adf28John McCall CI->getName(), BB); 338d7c10862016939c9850cadfe5e1c35513c0adf28John McCall II->setCallingConv(CI->getCallingConv()); 339d7c10862016939c9850cadfe5e1c35513c0adf28John McCall II->setAttributes(CI->getAttributes()); 340135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 341d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // Make sure that anything using the call now uses the invoke! This also 342d7c10862016939c9850cadfe5e1c35513c0adf28John McCall // updates the CallGraph if present, because it uses a WeakVH. 343d7c10862016939c9850cadfe5e1c35513c0adf28John McCall CI->replaceAllUsesWith(II); 344d7c10862016939c9850cadfe5e1c35513c0adf28John McCall 345d7c10862016939c9850cadfe5e1c35513c0adf28John McCall Split->getInstList().pop_front(); // Delete the original call 346a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 347135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Update any PHI nodes in the exceptional block to indicate that 348135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // there is now a new entry in them. 349a3de16bc8f36638d5444e3e7b0112998af54f826John McCall Invoke.addIncomingPHIValuesFor(BB); 350d7c10862016939c9850cadfe5e1c35513c0adf28John McCall return false; 351135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } 352a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 353a3de16bc8f36638d5444e3e7b0112998af54f826John McCall return false; 354135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner} 355135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 356135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 357cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner/// HandleInlinedInvoke - If we inlined an invoke site, we need to convert calls 358cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner/// in the body of the inlined function into invokes and turn unwind 359cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner/// instructions into branches to the invoke unwind dest. 360cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner/// 361dac5c4b10b387b55c2394cd98a64f3f1394df2e8Nick Lewycky/// II is the invoke instruction being inlined. FirstNewBlock is the first 362cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner/// block of the inlined code (the last block is the end of the function), 363cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner/// and InlineCodeInfo is information about the code that got inlined. 364cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattnerstatic void HandleInlinedInvoke(InvokeInst *II, BasicBlock *FirstNewBlock, 36581dfb3885252fbf621b080827a080099864415f8Chris Lattner ClonedCodeInfo &InlinedCodeInfo) { 366cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner BasicBlock *InvokeDest = II->getUnwindDest(); 367cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner 368cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner Function *Caller = FirstNewBlock->getParent(); 369a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 370cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner // The inlined code is currently at the end of the function, scan from the 371cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner // start of the inlined code to its end, checking for stuff we need to 372135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // rewrite. If the code doesn't have calls or unwinds, we know there is 373135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // nothing to rewrite. 374135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!InlinedCodeInfo.ContainsCalls && !InlinedCodeInfo.ContainsUnwinds) { 375135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Now that everything is happy, we have one final detail. The PHI nodes in 376135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // the exception destination block still have entries due to the original 377135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // invoke instruction. Eliminate these entries (which might even delete the 378135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // PHI node) now. 379135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner InvokeDest->removePredecessor(II->getParent()); 380135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner return; 381135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } 382a3de16bc8f36638d5444e3e7b0112998af54f826John McCall 383a3de16bc8f36638d5444e3e7b0112998af54f826John McCall InvokeInliningInfo Invoke(II); 384135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 385135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E; ++BB){ 386135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (InlinedCodeInfo.ContainsCalls) 387a3de16bc8f36638d5444e3e7b0112998af54f826John McCall if (HandleCallsInBlockInlinedThroughInvoke(BB, Invoke)) { 388a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // Honor a request to skip the next block. We don't need to 389a3de16bc8f36638d5444e3e7b0112998af54f826John McCall // consider UnwindInsts in this case either. 390a3de16bc8f36638d5444e3e7b0112998af54f826John McCall ++BB; 391a3de16bc8f36638d5444e3e7b0112998af54f826John McCall continue; 392a3de16bc8f36638d5444e3e7b0112998af54f826John McCall } 393135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 394135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) { 395135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // An UnwindInst requires special handling when it gets inlined into an 396135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // invoke site. Once this happens, we know that the unwind would cause 397135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // a control transfer to the invoke exception destination, so we can 398135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // transform it into a direct branch to the exception destination. 399135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner BranchInst::Create(InvokeDest, UI); 400135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 401135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Delete the unwind instruction! 402135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner UI->eraseFromParent(); 403135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 404135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Update any PHI nodes in the exceptional block to indicate that 405135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // there is now a new entry in them. 406a3de16bc8f36638d5444e3e7b0112998af54f826John McCall Invoke.addIncomingPHIValuesFor(BB); 407cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner } 408cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner } 409cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner 410cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner // Now that everything is happy, we have one final detail. The PHI nodes in 411cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner // the exception destination block still have entries due to the original 412cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner // invoke instruction. Eliminate these entries (which might even delete the 413cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner // PHI node) now. 414cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner InvokeDest->removePredecessor(II->getParent()); 415cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner} 416cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner 417d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner/// UpdateCallGraphAfterInlining - Once we have cloned code over from a callee 418d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner/// into the caller, update the specified callgraph to reflect the changes we 419d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner/// made. Note that it's possible that not all code was copied over, so only 420d7b9851c4e634ed3599b1a4c70b1c76c90a11686Duncan Sands/// some edges of the callgraph may remain. 421d7b9851c4e634ed3599b1a4c70b1c76c90a11686Duncan Sandsstatic void UpdateCallGraphAfterInlining(CallSite CS, 422d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner Function::iterator FirstNewBlock, 4231ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy &VMap, 424fe9af3b1f7e5d68ecc330bdf4f047d76838f8cc3Chris Lattner InlineFunctionInfo &IFI) { 425fe9af3b1f7e5d68ecc330bdf4f047d76838f8cc3Chris Lattner CallGraph &CG = *IFI.CG; 426d7b9851c4e634ed3599b1a4c70b1c76c90a11686Duncan Sands const Function *Caller = CS.getInstruction()->getParent()->getParent(); 427d7b9851c4e634ed3599b1a4c70b1c76c90a11686Duncan Sands const Function *Callee = CS.getCalledFunction(); 428468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner CallGraphNode *CalleeNode = CG[Callee]; 429468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner CallGraphNode *CallerNode = CG[Caller]; 430a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 431d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner // Since we inlined some uninlined call sites in the callee into the caller, 432468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner // add edges from the caller to all of the callees of the callee. 433c478e52bf4c12691037856ee103c66946afeab6cGabor Greif CallGraphNode::iterator I = CalleeNode->begin(), E = CalleeNode->end(); 434c478e52bf4c12691037856ee103c66946afeab6cGabor Greif 435c478e52bf4c12691037856ee103c66946afeab6cGabor Greif // Consider the case where CalleeNode == CallerNode. 436125329891f97baedef21e4b464ba70182c3fb45eGabor Greif CallGraphNode::CalledFunctionsVector CallCache; 437c478e52bf4c12691037856ee103c66946afeab6cGabor Greif if (CalleeNode == CallerNode) { 438c478e52bf4c12691037856ee103c66946afeab6cGabor Greif CallCache.assign(I, E); 439c478e52bf4c12691037856ee103c66946afeab6cGabor Greif I = CallCache.begin(); 440c478e52bf4c12691037856ee103c66946afeab6cGabor Greif E = CallCache.end(); 441c478e52bf4c12691037856ee103c66946afeab6cGabor Greif } 442c478e52bf4c12691037856ee103c66946afeab6cGabor Greif 443c478e52bf4c12691037856ee103c66946afeab6cGabor Greif for (; I != E; ++I) { 444a541b0fde2ab6b8b037edf113d42da41a2c5aae9Chris Lattner const Value *OrigCall = I->first; 445a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 4461ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy::iterator VMI = VMap.find(OrigCall); 447981418bf1562d0b5b470ddc7d0034c9f3297b893Chris Lattner // Only copy the edge if the call was inlined! 44829d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel if (VMI == VMap.end() || VMI->second == 0) 449135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 450135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 451135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // If the call was inlined, but then constant folded, there is no edge to 452135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // add. Check for this case. 453b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner Instruction *NewCall = dyn_cast<Instruction>(VMI->second); 454b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner if (NewCall == 0) continue; 4550ca2f28458ae9122f413a4092ddcee33a9dd21c6Chris Lattner 4560ca2f28458ae9122f413a4092ddcee33a9dd21c6Chris Lattner // Remember that this call site got inlined for the client of 4570ca2f28458ae9122f413a4092ddcee33a9dd21c6Chris Lattner // InlineFunction. 4580ca2f28458ae9122f413a4092ddcee33a9dd21c6Chris Lattner IFI.InlinedCalls.push_back(NewCall); 4590ca2f28458ae9122f413a4092ddcee33a9dd21c6Chris Lattner 460b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner // It's possible that inlining the callsite will cause it to go from an 461b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner // indirect to a direct call by resolving a function pointer. If this 462b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner // happens, set the callee of the new call site to a more precise 463b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner // destination. This can also happen if the call graph node of the caller 464b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner // was just unnecessarily imprecise. 465b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner if (I->second->getFunction() == 0) 466b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner if (Function *F = CallSite(NewCall).getCalledFunction()) { 467b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner // Indirect call site resolved to direct call. 46886099345db95fdce6960ab62fbd9cb0cf96875f7Gabor Greif CallerNode->addCalledFunction(CallSite(NewCall), CG[F]); 46986099345db95fdce6960ab62fbd9cb0cf96875f7Gabor Greif 470b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner continue; 471b957a5e41ed6288f4d033167f6413621a09655eeChris Lattner } 47286099345db95fdce6960ab62fbd9cb0cf96875f7Gabor Greif 47386099345db95fdce6960ab62fbd9cb0cf96875f7Gabor Greif CallerNode->addCalledFunction(CallSite(NewCall), I->second); 474d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner } 475135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 47639fa32403e0b5e163f4f05566d6cde65e6c11095Dale Johannesen // Update the call graph by deleting the edge from Callee to Caller. We must 47739fa32403e0b5e163f4f05566d6cde65e6c11095Dale Johannesen // do this after the loop above in case Caller and Callee are the same. 47839fa32403e0b5e163f4f05566d6cde65e6c11095Dale Johannesen CallerNode->removeCallEdgeFor(CS); 479468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner} 480468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner 4810b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner/// HandleByValArgument - When inlining a call site that has a byval argument, 4820b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner/// we have to make the implicit memcpy explicit by adding it. 483e7ae705c32906979a527926864345016e76867b9Chris Lattnerstatic Value *HandleByValArgument(Value *Arg, Instruction *TheCall, 484e7ae705c32906979a527926864345016e76867b9Chris Lattner const Function *CalledFunc, 485e7ae705c32906979a527926864345016e76867b9Chris Lattner InlineFunctionInfo &IFI, 486e7ae705c32906979a527926864345016e76867b9Chris Lattner unsigned ByValAlignment) { 4870b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner const Type *AggTy = cast<PointerType>(Arg->getType())->getElementType(); 4880b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner 4890b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner // If the called function is readonly, then it could not mutate the caller's 4900b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner // copy of the byval'd memory. In this case, it is safe to elide the copy and 4910b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner // temporary. 4920b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner if (CalledFunc->onlyReadsMemory()) { 4930b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner // If the byval argument has a specified alignment that is greater than the 4940b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner // passed in pointer, then we either have to round up the input pointer or 4950b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner // give up on this transformation. 4960b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner if (ByValAlignment <= 1) // 0 = unspecified, 1 = no particular alignment. 4970b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner return Arg; 4980b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner 4997569d79de1bd97a6a17b81340ea6ce97d8a3c279Chris Lattner // If the pointer is already known to be sufficiently aligned, or if we can 5007569d79de1bd97a6a17b81340ea6ce97d8a3c279Chris Lattner // round it up to a larger alignment, then we don't need a temporary. 5017569d79de1bd97a6a17b81340ea6ce97d8a3c279Chris Lattner if (getOrEnforceKnownAlignment(Arg, ByValAlignment, 5027569d79de1bd97a6a17b81340ea6ce97d8a3c279Chris Lattner IFI.TD) >= ByValAlignment) 5037569d79de1bd97a6a17b81340ea6ce97d8a3c279Chris Lattner return Arg; 5040b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner 5057569d79de1bd97a6a17b81340ea6ce97d8a3c279Chris Lattner // Otherwise, we have to make a memcpy to get a safe alignment. This is bad 5067569d79de1bd97a6a17b81340ea6ce97d8a3c279Chris Lattner // for code quality, but rarely happens and is required for correctness. 5070b66f63a26387f5c0360a4324fc3c31e0599a6e0Chris Lattner } 508e7ae705c32906979a527926864345016e76867b9Chris Lattner 509e7ae705c32906979a527926864345016e76867b9Chris Lattner LLVMContext &Context = Arg->getContext(); 510e7ae705c32906979a527926864345016e76867b9Chris Lattner 511e7ae705c32906979a527926864345016e76867b9Chris Lattner const Type *VoidPtrTy = Type::getInt8PtrTy(Context); 512e7ae705c32906979a527926864345016e76867b9Chris Lattner 513e7ae705c32906979a527926864345016e76867b9Chris Lattner // Create the alloca. If we have TargetData, use nice alignment. 514e7ae705c32906979a527926864345016e76867b9Chris Lattner unsigned Align = 1; 515e7ae705c32906979a527926864345016e76867b9Chris Lattner if (IFI.TD) 516e7ae705c32906979a527926864345016e76867b9Chris Lattner Align = IFI.TD->getPrefTypeAlignment(AggTy); 517e7ae705c32906979a527926864345016e76867b9Chris Lattner 518e7ae705c32906979a527926864345016e76867b9Chris Lattner // If the byval had an alignment specified, we *must* use at least that 519e7ae705c32906979a527926864345016e76867b9Chris Lattner // alignment, as it is required by the byval argument (and uses of the 520e7ae705c32906979a527926864345016e76867b9Chris Lattner // pointer inside the callee). 521e7ae705c32906979a527926864345016e76867b9Chris Lattner Align = std::max(Align, ByValAlignment); 522e7ae705c32906979a527926864345016e76867b9Chris Lattner 523e7ae705c32906979a527926864345016e76867b9Chris Lattner Function *Caller = TheCall->getParent()->getParent(); 524e7ae705c32906979a527926864345016e76867b9Chris Lattner 525e7ae705c32906979a527926864345016e76867b9Chris Lattner Value *NewAlloca = new AllocaInst(AggTy, 0, Align, Arg->getName(), 526e7ae705c32906979a527926864345016e76867b9Chris Lattner &*Caller->begin()->begin()); 527e7ae705c32906979a527926864345016e76867b9Chris Lattner // Emit a memcpy. 528e7ae705c32906979a527926864345016e76867b9Chris Lattner const Type *Tys[3] = {VoidPtrTy, VoidPtrTy, Type::getInt64Ty(Context)}; 529e7ae705c32906979a527926864345016e76867b9Chris Lattner Function *MemCpyFn = Intrinsic::getDeclaration(Caller->getParent(), 530e7ae705c32906979a527926864345016e76867b9Chris Lattner Intrinsic::memcpy, 531e7ae705c32906979a527926864345016e76867b9Chris Lattner Tys, 3); 532e7ae705c32906979a527926864345016e76867b9Chris Lattner Value *DestCast = new BitCastInst(NewAlloca, VoidPtrTy, "tmp", TheCall); 533e7ae705c32906979a527926864345016e76867b9Chris Lattner Value *SrcCast = new BitCastInst(Arg, VoidPtrTy, "tmp", TheCall); 534e7ae705c32906979a527926864345016e76867b9Chris Lattner 535e7ae705c32906979a527926864345016e76867b9Chris Lattner Value *Size; 536e7ae705c32906979a527926864345016e76867b9Chris Lattner if (IFI.TD == 0) 537e7ae705c32906979a527926864345016e76867b9Chris Lattner Size = ConstantExpr::getSizeOf(AggTy); 538e7ae705c32906979a527926864345016e76867b9Chris Lattner else 539e7ae705c32906979a527926864345016e76867b9Chris Lattner Size = ConstantInt::get(Type::getInt64Ty(Context), 540e7ae705c32906979a527926864345016e76867b9Chris Lattner IFI.TD->getTypeStoreSize(AggTy)); 541e7ae705c32906979a527926864345016e76867b9Chris Lattner 542e7ae705c32906979a527926864345016e76867b9Chris Lattner // Always generate a memcpy of alignment 1 here because we don't know 543e7ae705c32906979a527926864345016e76867b9Chris Lattner // the alignment of the src pointer. Other optimizations can infer 544e7ae705c32906979a527926864345016e76867b9Chris Lattner // better alignment. 545e7ae705c32906979a527926864345016e76867b9Chris Lattner Value *CallArgs[] = { 546e7ae705c32906979a527926864345016e76867b9Chris Lattner DestCast, SrcCast, Size, 547e7ae705c32906979a527926864345016e76867b9Chris Lattner ConstantInt::get(Type::getInt32Ty(Context), 1), 548e7ae705c32906979a527926864345016e76867b9Chris Lattner ConstantInt::getFalse(Context) // isVolatile 549e7ae705c32906979a527926864345016e76867b9Chris Lattner }; 550e7ae705c32906979a527926864345016e76867b9Chris Lattner CallInst *TheMemCpy = 551e7ae705c32906979a527926864345016e76867b9Chris Lattner CallInst::Create(MemCpyFn, CallArgs, CallArgs+5, "", TheCall); 552e7ae705c32906979a527926864345016e76867b9Chris Lattner 553e7ae705c32906979a527926864345016e76867b9Chris Lattner // If we have a call graph, update it. 554e7ae705c32906979a527926864345016e76867b9Chris Lattner if (CallGraph *CG = IFI.CG) { 555e7ae705c32906979a527926864345016e76867b9Chris Lattner CallGraphNode *MemCpyCGN = CG->getOrInsertFunction(MemCpyFn); 556e7ae705c32906979a527926864345016e76867b9Chris Lattner CallGraphNode *CallerNode = (*CG)[Caller]; 557e7ae705c32906979a527926864345016e76867b9Chris Lattner CallerNode->addCalledFunction(TheMemCpy, MemCpyCGN); 558e7ae705c32906979a527926864345016e76867b9Chris Lattner } 559e7ae705c32906979a527926864345016e76867b9Chris Lattner 560e7ae705c32906979a527926864345016e76867b9Chris Lattner // Uses of the argument in the function should use our new alloca 561e7ae705c32906979a527926864345016e76867b9Chris Lattner // instead. 562e7ae705c32906979a527926864345016e76867b9Chris Lattner return NewAlloca; 563e7ae705c32906979a527926864345016e76867b9Chris Lattner} 564e7ae705c32906979a527926864345016e76867b9Chris Lattner 5656d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky// isUsedByLifetimeMarker - Check whether this Value is used by a lifetime 5666d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky// intrinsic. 5676d55f2269e20298a1d6a683be72d9552482156a9Nick Lewyckystatic bool isUsedByLifetimeMarker(Value *V) { 5686d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE; 5696d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky ++UI) { 5706d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*UI)) { 5716d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky switch (II->getIntrinsicID()) { 5726d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky default: break; 5736d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky case Intrinsic::lifetime_start: 5746d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky case Intrinsic::lifetime_end: 5756d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky return true; 5766d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky } 5776d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky } 5786d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky } 5796d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky return false; 5806d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky} 5816d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky 5826d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky// hasLifetimeMarkers - Check whether the given alloca already has 5836d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky// lifetime.start or lifetime.end intrinsics. 5846d55f2269e20298a1d6a683be72d9552482156a9Nick Lewyckystatic bool hasLifetimeMarkers(AllocaInst *AI) { 5856d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky const Type *Int8PtrTy = Type::getInt8PtrTy(AI->getType()->getContext()); 5866d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky if (AI->getType() == Int8PtrTy) 5876d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky return isUsedByLifetimeMarker(AI); 5886d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky 5896d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky // Do a scan to find all the bitcasts to i8*. 5906d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); I != E; 5916d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky ++I) { 5926d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky if (I->getType() != Int8PtrTy) continue; 5936d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky if (!isa<BitCastInst>(*I)) continue; 5946d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky if (isUsedByLifetimeMarker(*I)) 5956d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky return true; 5966d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky } 5976d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky return false; 5986d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky} 5996d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky 600ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// InlineFunction - This function inlines the called function into the basic 601ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// block of the caller. This returns false if it is not possible to inline this 602ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// call. The program is still in a well defined state if this occurs though. 603ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 604fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// Note that this only does one level of inlining. For example, if the 605fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now 6067a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// exists in the instruction stream. Similarly this will inline a recursive 607ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// function by one level. 608ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 60960915146f4d35e12f10dcdaa155596fac79184daChris Lattnerbool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) { 61080a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner Instruction *TheCall = CS.getInstruction(); 611e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson LLVMContext &Context = TheCall->getContext(); 61280a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner assert(TheCall->getParent() && TheCall->getParent()->getParent() && 61380a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner "Instruction not in function!"); 614ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 61560915146f4d35e12f10dcdaa155596fac79184daChris Lattner // If IFI has any state in it, zap it before we fill it in. 61660915146f4d35e12f10dcdaa155596fac79184daChris Lattner IFI.reset(); 61760915146f4d35e12f10dcdaa155596fac79184daChris Lattner 61880a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner const Function *CalledFunc = CS.getCalledFunction(); 619ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner if (CalledFunc == 0 || // Can't inline external function or indirect 6205cbf985dcbc89fba3208e7baf8b6f488b06d3ec9Reid Spencer CalledFunc->isDeclaration() || // call, or call to a vararg function! 6210623e90398153be61226ad19f1b40d3817874526Eric Christopher CalledFunc->getFunctionType()->isVarArg()) return false; 622ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 623af9985c6b9d066cb70a0363fed699022d0ec196cChris Lattner // If the call to the callee is not a tail call, we must clear the 'tail' 6241b49141821e98e4321bfe6234c7001c836b2a289Chris Lattner // flags on any calls that we inline. 6251b49141821e98e4321bfe6234c7001c836b2a289Chris Lattner bool MustClearTailCallFlags = 626af9985c6b9d066cb70a0363fed699022d0ec196cChris Lattner !(isa<CallInst>(TheCall) && cast<CallInst>(TheCall)->isTailCall()); 6271b49141821e98e4321bfe6234c7001c836b2a289Chris Lattner 628f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands // If the call to the callee cannot throw, set the 'nounwind' flag on any 629f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands // calls that we inline. 630f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands bool MarkNoUnwind = CS.doesNotThrow(); 631f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands 63280a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner BasicBlock *OrigBB = TheCall->getParent(); 633ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner Function *Caller = OrigBB->getParent(); 634ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 6350e13821c96937830ec817f08095c3cef1fdcac8dGordon Henriksen // GC poses two hazards to inlining, which only occur when the callee has GC: 6360e13821c96937830ec817f08095c3cef1fdcac8dGordon Henriksen // 1. If the caller has no GC, then the callee's GC must be propagated to the 6370e13821c96937830ec817f08095c3cef1fdcac8dGordon Henriksen // caller. 6380e13821c96937830ec817f08095c3cef1fdcac8dGordon Henriksen // 2. If the caller has a differing GC, it is invalid to inline. 6395eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen if (CalledFunc->hasGC()) { 6405eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen if (!Caller->hasGC()) 6415eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen Caller->setGC(CalledFunc->getGC()); 6425eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen else if (CalledFunc->getGC() != Caller->getGC()) 6430e13821c96937830ec817f08095c3cef1fdcac8dGordon Henriksen return false; 6440e13821c96937830ec817f08095c3cef1fdcac8dGordon Henriksen } 645a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 6465052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner // Get an iterator to the last basic block in the function, which will have 6475052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner // the new function inlined after it. 6485052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner // 6495052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner Function::iterator LastBlock = &Caller->back(); 6505052c911ec1be51ecb36e7f025c26412e9f1bfacChris Lattner 6515e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Make sure to capture all of the return instructions from the cloned 6525e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // function. 653ec1bea0d94372985a0a5eb283e644c6d0dd345dcChris Lattner SmallVector<ReturnInst*, 8> Returns; 654cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner ClonedCodeInfo InlinedFunctionInfo; 6550744f09efc53d3352ac1caffc61f6e8239201c3bDale Johannesen Function::iterator FirstNewBlock; 656f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands 65729d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel { // Scope to destroy VMap after cloning. 6581ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy VMap; 6595b5bc3032f97cfa7bfa3e22282d3a9c1ed05eec6Chris Lattner 6609614fcc640eb628cc5dfddb277ebae9f6cb61014Dan Gohman assert(CalledFunc->arg_size() == CS.arg_size() && 6615e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner "No varargs calls can be inlined!"); 662a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 663c93adca35856d0eaae088e52ba30cfefbd7ad910Chris Lattner // Calculate the vector of arguments to pass into the function cloner, which 664c93adca35856d0eaae088e52ba30cfefbd7ad910Chris Lattner // matches up the formal to the actual argument values. 6655e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner CallSite::arg_iterator AI = CS.arg_begin(); 666c93adca35856d0eaae088e52ba30cfefbd7ad910Chris Lattner unsigned ArgNo = 0; 667e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner for (Function::const_arg_iterator I = CalledFunc->arg_begin(), 668c93adca35856d0eaae088e52ba30cfefbd7ad910Chris Lattner E = CalledFunc->arg_end(); I != E; ++I, ++AI, ++ArgNo) { 669c93adca35856d0eaae088e52ba30cfefbd7ad910Chris Lattner Value *ActualArg = *AI; 670a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 671d82375c1c43db7f823dd4660d3495e76566699e3Duncan Sands // When byval arguments actually inlined, we need to make the copy implied 672d82375c1c43db7f823dd4660d3495e76566699e3Duncan Sands // by them explicit. However, we don't do this if the callee is readonly 673d82375c1c43db7f823dd4660d3495e76566699e3Duncan Sands // or readnone, because the copy would be unneeded: the callee doesn't 674d82375c1c43db7f823dd4660d3495e76566699e3Duncan Sands // modify the struct. 675e7ae705c32906979a527926864345016e76867b9Chris Lattner if (CalledFunc->paramHasAttr(ArgNo+1, Attribute::ByVal)) { 676e7ae705c32906979a527926864345016e76867b9Chris Lattner ActualArg = HandleByValArgument(ActualArg, TheCall, CalledFunc, IFI, 677e7ae705c32906979a527926864345016e76867b9Chris Lattner CalledFunc->getParamAlignment(ArgNo+1)); 678e7ae705c32906979a527926864345016e76867b9Chris Lattner 6792914ba6ec793e2bb0e9ca5891af1d29ee2fee28eDuncan Sands // Calls that we inline may use the new alloca, so we need to clear 680e7ae705c32906979a527926864345016e76867b9Chris Lattner // their 'tail' flags if HandleByValArgument introduced a new alloca and 681e7ae705c32906979a527926864345016e76867b9Chris Lattner // the callee has calls. 682e7ae705c32906979a527926864345016e76867b9Chris Lattner MustClearTailCallFlags |= ActualArg != *AI; 683c93adca35856d0eaae088e52ba30cfefbd7ad910Chris Lattner } 684a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 68529d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel VMap[I] = ActualArg; 686c93adca35856d0eaae088e52ba30cfefbd7ad910Chris Lattner } 687fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6885b5bc3032f97cfa7bfa3e22282d3a9c1ed05eec6Chris Lattner // We want the inliner to prune the code as it copies. We would LOVE to 6895b5bc3032f97cfa7bfa3e22282d3a9c1ed05eec6Chris Lattner // have no dead or constant instructions leftover after inlining occurs 6905b5bc3032f97cfa7bfa3e22282d3a9c1ed05eec6Chris Lattner // (which can happen, e.g., because an argument was constant), but we'll be 6915b5bc3032f97cfa7bfa3e22282d3a9c1ed05eec6Chris Lattner // happy with whatever the cloner can do. 6926cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman CloneAndPruneFunctionInto(Caller, CalledFunc, VMap, 6936cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman /*ModuleLevelChanges=*/false, Returns, ".i", 69460915146f4d35e12f10dcdaa155596fac79184daChris Lattner &InlinedFunctionInfo, IFI.TD, TheCall); 695a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 696d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner // Remember the first block that is newly cloned over. 697d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner FirstNewBlock = LastBlock; ++FirstNewBlock; 698a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 699d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner // Update the callgraph if requested. 70060915146f4d35e12f10dcdaa155596fac79184daChris Lattner if (IFI.CG) 70129d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel UpdateCallGraphAfterInlining(CS, FirstNewBlock, VMap, IFI); 702fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman } 703a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 704ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // If there are any alloca instructions in the block that used to be the entry 705ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // block for the callee, move them to the entry block of the caller. First 706ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // calculate which instruction they should be inserted before. We insert the 707ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // instructions at the end of the current alloca list. 708ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // 70921f20558d629f7ff8f64c20746d890d29328a544Chris Lattner { 71080a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner BasicBlock::iterator InsertPoint = Caller->begin()->begin(); 7115e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner for (BasicBlock::iterator I = FirstNewBlock->begin(), 712135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner E = FirstNewBlock->end(); I != E; ) { 713135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner AllocaInst *AI = dyn_cast<AllocaInst>(I++); 714135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (AI == 0) continue; 715135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 716135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // If the alloca is now dead, remove it. This often occurs due to code 717135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // specialization. 718135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (AI->use_empty()) { 719135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner AI->eraseFromParent(); 720135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 72133bb3c8be355d179ece8e751f6e0f0978d0dd038Chris Lattner } 722135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 723135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner if (!isa<Constant>(AI->getArraySize())) 724135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner continue; 725135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 72639add23dc54a1580983b1901384688d6622daa3bChris Lattner // Keep track of the static allocas that we inline into the caller. 72760915146f4d35e12f10dcdaa155596fac79184daChris Lattner IFI.StaticAllocas.push_back(AI); 7288f2718fbef6177966ff807af0732eb2431bd9a5fChris Lattner 729135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Scan for the block of allocas that we can move over, and move them 730135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // all at once. 731135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner while (isa<AllocaInst>(I) && 7328f2718fbef6177966ff807af0732eb2431bd9a5fChris Lattner isa<Constant>(cast<AllocaInst>(I)->getArraySize())) { 73360915146f4d35e12f10dcdaa155596fac79184daChris Lattner IFI.StaticAllocas.push_back(cast<AllocaInst>(I)); 734135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner ++I; 7358f2718fbef6177966ff807af0732eb2431bd9a5fChris Lattner } 736135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner 737135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // Transfer all of the allocas over in a block. Using splice means 738135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // that the instructions aren't removed from the symbol table, then 739135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner // reinserted. 740135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner Caller->getEntryBlock().getInstList().splice(InsertPoint, 741135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner FirstNewBlock->getInstList(), 742135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner AI, I); 743135755dae4c3fa8003b76150689d5064aa4612eeChris Lattner } 74480a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner } 74580a38d245359cb0a3be8f78f5d7d911232886b9aChris Lattner 7466d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky // Leave lifetime markers for the static alloca's, scoping them to the 7476d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky // function we just inlined. 7486d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky if (!IFI.StaticAllocas.empty()) { 7496d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky // Also preserve the call graph, if applicable. 7506d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky CallGraphNode *StartCGN = 0, *EndCGN = 0, *CallerNode = 0; 7516d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky if (CallGraph *CG = IFI.CG) { 7526d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky Function *Start = Intrinsic::getDeclaration(Caller->getParent(), 7536d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky Intrinsic::lifetime_start); 7546d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky Function *End = Intrinsic::getDeclaration(Caller->getParent(), 7556d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky Intrinsic::lifetime_end); 7566d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky StartCGN = CG->getOrInsertFunction(Start); 7576d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky EndCGN = CG->getOrInsertFunction(End); 7586d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky CallerNode = (*CG)[Caller]; 7596d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky } 7606d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky 7616d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky IRBuilder<> builder(FirstNewBlock->begin()); 7626d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky for (unsigned ai = 0, ae = IFI.StaticAllocas.size(); ai != ae; ++ai) { 7636d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky AllocaInst *AI = IFI.StaticAllocas[ai]; 7646d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky 7656d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky // If the alloca is already scoped to something smaller than the whole 7666d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky // function then there's no need to add redundant, less accurate markers. 7676d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky if (hasLifetimeMarkers(AI)) 7686d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky continue; 7696d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky 7706d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky CallInst *StartCall = builder.CreateLifetimeStart(AI); 7716d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky if (IFI.CG) CallerNode->addCalledFunction(StartCall, StartCGN); 7726d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky for (unsigned ri = 0, re = Returns.size(); ri != re; ++ri) { 7736d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky IRBuilder<> builder(Returns[ri]); 7746d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky CallInst *EndCall = builder.CreateLifetimeEnd(AI); 7756d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky if (IFI.CG) CallerNode->addCalledFunction(EndCall, EndCGN); 7766d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky } 7776d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky } 7786d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky } 7796d55f2269e20298a1d6a683be72d9552482156a9Nick Lewycky 780bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner // If the inlined code contained dynamic alloca instructions, wrap the inlined 781bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner // code with llvm.stacksave/llvm.stackrestore intrinsics. 782bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner if (InlinedFunctionInfo.ContainsDynamicAllocas) { 783bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner Module *M = Caller->getParent(); 784bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner // Get the two intrinsics we care about. 7856128df525501c333a650d097703c18d7e878f5e8Chris Lattner Function *StackSave = Intrinsic::getDeclaration(M, Intrinsic::stacksave); 7866128df525501c333a650d097703c18d7e878f5e8Chris Lattner Function *StackRestore=Intrinsic::getDeclaration(M,Intrinsic::stackrestore); 787d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner 788d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner // If we are preserving the callgraph, add edges to the stacksave/restore 789d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner // functions for the calls we insert. 79021ba23d0d88cff57dcdf104cd6914dabcbc68131Chris Lattner CallGraphNode *StackSaveCGN = 0, *StackRestoreCGN = 0, *CallerNode = 0; 79160915146f4d35e12f10dcdaa155596fac79184daChris Lattner if (CallGraph *CG = IFI.CG) { 7926128df525501c333a650d097703c18d7e878f5e8Chris Lattner StackSaveCGN = CG->getOrInsertFunction(StackSave); 7936128df525501c333a650d097703c18d7e878f5e8Chris Lattner StackRestoreCGN = CG->getOrInsertFunction(StackRestore); 794d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner CallerNode = (*CG)[Caller]; 795d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner } 796a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 797bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner // Insert the llvm.stacksave. 798a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands CallInst *SavedPtr = CallInst::Create(StackSave, "savedstack", 799051a950000e21935165db56695e35bade668193bGabor Greif FirstNewBlock->begin()); 80060915146f4d35e12f10dcdaa155596fac79184daChris Lattner if (IFI.CG) CallerNode->addCalledFunction(SavedPtr, StackSaveCGN); 801a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 802bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner // Insert a call to llvm.stackrestore before any return instructions in the 803bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner // inlined function. 804d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 805051a950000e21935165db56695e35bade668193bGabor Greif CallInst *CI = CallInst::Create(StackRestore, SavedPtr, "", Returns[i]); 80660915146f4d35e12f10dcdaa155596fac79184daChris Lattner if (IFI.CG) CallerNode->addCalledFunction(CI, StackRestoreCGN); 807d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner } 808468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner 809468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner // Count the number of StackRestore calls we insert. 810468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner unsigned NumStackRestores = Returns.size(); 811a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 812bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner // If we are inlining an invoke instruction, insert restores before each 813bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner // unwind. These unwinds will be rewritten into branches later. 814bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner if (InlinedFunctionInfo.ContainsUnwinds && isa<InvokeInst>(TheCall)) { 815bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner for (Function::iterator BB = FirstNewBlock, E = Caller->end(); 816bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner BB != E; ++BB) 817468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) { 8186128df525501c333a650d097703c18d7e878f5e8Chris Lattner CallInst *CI = CallInst::Create(StackRestore, SavedPtr, "", UI); 81960915146f4d35e12f10dcdaa155596fac79184daChris Lattner if (IFI.CG) CallerNode->addCalledFunction(CI, StackRestoreCGN); 820468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner ++NumStackRestores; 821468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner } 822468fb1df7db466e5682ee44341c3990b599e8d6aChris Lattner } 823bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner } 824bf229f488a7541abd979cc3fbe9c3ce1c100e5c0Chris Lattner 825a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands // If we are inlining tail call instruction through a call site that isn't 8261fdf4a859f03ce5aa4ce9acba29ce321c847388eChris Lattner // marked 'tail', we must remove the tail marker for any calls in the inlined 827f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands // code. Also, calls inlined through a 'nounwind' call site should be marked 828f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands // 'nounwind'. 829f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands if (InlinedFunctionInfo.ContainsCalls && 830f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands (MustClearTailCallFlags || MarkNoUnwind)) { 8311b49141821e98e4321bfe6234c7001c836b2a289Chris Lattner for (Function::iterator BB = FirstNewBlock, E = Caller->end(); 8321b49141821e98e4321bfe6234c7001c836b2a289Chris Lattner BB != E; ++BB) 8331b49141821e98e4321bfe6234c7001c836b2a289Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 834f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands if (CallInst *CI = dyn_cast<CallInst>(I)) { 835f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands if (MustClearTailCallFlags) 836f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands CI->setTailCall(false); 837f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands if (MarkNoUnwind) 838f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands CI->setDoesNotThrow(); 839f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands } 8401b49141821e98e4321bfe6234c7001c836b2a289Chris Lattner } 8411b49141821e98e4321bfe6234c7001c836b2a289Chris Lattner 842f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands // If we are inlining through a 'nounwind' call site then any inlined 'unwind' 843f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands // instructions are unreachable. 844f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands if (InlinedFunctionInfo.ContainsUnwinds && MarkNoUnwind) 845f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands for (Function::iterator BB = FirstNewBlock, E = Caller->end(); 846f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands BB != E; ++BB) { 847f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands TerminatorInst *Term = BB->getTerminator(); 848f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands if (isa<UnwindInst>(Term)) { 8491d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson new UnreachableInst(Context, Term); 850f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands BB->getInstList().erase(Term); 851f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands } 852f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands } 853f0c3354d998507515ab39e26b5292ea0ceb06aefDuncan Sands 8545e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // If we are inlining for an invoke instruction, we must make sure to rewrite 8555e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // any inlined 'unwind' instructions into branches to the invoke exception 8565e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // destination, and call instructions into invoke instructions. 857cd4d339ec187182c9abc22b80560349f8ba5010fChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) 85881dfb3885252fbf621b080827a080099864415f8Chris Lattner HandleInlinedInvoke(II, FirstNewBlock, InlinedFunctionInfo); 8595e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 86044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If we cloned in _exactly one_ basic block, and if that block ends in a 86144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // return instruction, we splice the body of the inlined callee directly into 86244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // the calling basic block. 86344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) { 86444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Move all of the instructions right before the call. 86544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner OrigBB->getInstList().splice(TheCall, FirstNewBlock->getInstList(), 86644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner FirstNewBlock->begin(), FirstNewBlock->end()); 86744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Remove the cloned basic block. 86844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner Caller->getBasicBlockList().pop_back(); 869fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 87044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If the call site was an invoke instruction, add a branch to the normal 87144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // destination. 87244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) 873051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(II->getNormalDest(), TheCall); 87444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 87544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If the return instruction returned a value, replace uses of the call with 87644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // uses of the returned value. 877dc00d42bb18a6748f43c365d9bd30c1ed0e800acDevang Patel if (!TheCall->use_empty()) { 878dc00d42bb18a6748f43c365d9bd30c1ed0e800acDevang Patel ReturnInst *R = Returns[0]; 8795877ad7e90de2179c15914ff9e8f1c72152cac30Eli Friedman if (TheCall == R->getReturnValue()) 8809e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType())); 8815877ad7e90de2179c15914ff9e8f1c72152cac30Eli Friedman else 8825877ad7e90de2179c15914ff9e8f1c72152cac30Eli Friedman TheCall->replaceAllUsesWith(R->getReturnValue()); 883dc00d42bb18a6748f43c365d9bd30c1ed0e800acDevang Patel } 88444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Since we are now done with the Call/Invoke, we can delete it. 8851adec83ae84031bfa9f0bf209c5ee6c64906a1ffDan Gohman TheCall->eraseFromParent(); 88644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 88744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Since we are now done with the return instruction, delete it also. 8881adec83ae84031bfa9f0bf209c5ee6c64906a1ffDan Gohman Returns[0]->eraseFromParent(); 88944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 89044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // We are now done with the inlining. 89144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner return true; 89244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner } 89344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 89444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Otherwise, we have the normal case, of more than one block to inline or 89544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // multiple return sites. 89644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 8975e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // We want to clone the entire callee function into the hole between the 8985e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // "starter" and "ender" blocks. How we accomplish this depends on whether 8995e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // this is an invoke instruction or a call instruction. 9005e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner BasicBlock *AfterCallBB; 9015e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) { 902fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 9035e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Add an unconditional branch to make this look like the CallInst case... 904051a950000e21935165db56695e35bade668193bGabor Greif BranchInst *NewBr = BranchInst::Create(II->getNormalDest(), TheCall); 905fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 9065e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Split the basic block. This guarantees that no PHI nodes will have to be 9075e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // updated due to new incoming edges, and make the invoke case more 9085e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // symmetric to the call case. 9095e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner AfterCallBB = OrigBB->splitBasicBlock(NewBr, 910284d1b88273eb1967c8faef407f1167791c760e0Chris Lattner CalledFunc->getName()+".exit"); 911fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 9125e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } else { // It's a call 91344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // If this is a call instruction, we need to split the basic block that 91444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // the call lives in. 9155e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // 9165e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner AfterCallBB = OrigBB->splitBasicBlock(TheCall, 917284d1b88273eb1967c8faef407f1167791c760e0Chris Lattner CalledFunc->getName()+".exit"); 9185e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 9195e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner 92044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Change the branch that used to go to AfterCallBB to branch to the first 92144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // basic block of the inlined function. 92244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // 92344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner TerminatorInst *Br = OrigBB->getTerminator(); 924fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman assert(Br && Br->getOpcode() == Instruction::Br && 92544a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner "splitBasicBlock broken!"); 92644a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner Br->setOperand(0, FirstNewBlock); 92744a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 92844a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 92944a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // Now that the function is correct, make it a little bit nicer. In 93044a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // particular, move the basic blocks inserted from the end of the function 93144a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner // into the space made by splitting the source basic block. 93244a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner Caller->getBasicBlockList().splice(AfterCallBB, Caller->getBasicBlockList(), 93344a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner FirstNewBlock, Caller->end()); 93444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 9355e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Handle all of the return instructions that we just cloned in, and eliminate 9365e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // any users of the original call/invoke instruction. 937b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel const Type *RTy = CalledFunc->getReturnType(); 9382c31750cd0ebdc83a890ace97dbb6249b3abe44eDan Gohman 9396fb881c036c32728c4a128d81b6083457e534e09Duncan Sands PHINode *PHI = 0; 940fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (Returns.size() > 1) { 9415e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // The PHI node should go at the front of the new basic block to merge all 9425e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // possible incoming values. 9435e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner if (!TheCall->use_empty()) { 9443ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHI = PHINode::Create(RTy, Returns.size(), TheCall->getName(), 945fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman AfterCallBB->begin()); 946fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman // Anything that used the result of the function call should now use the 947fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman // PHI node as their operand. 948a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands TheCall->replaceAllUsesWith(PHI); 9495e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 950fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 951c478e52bf4c12691037856ee103c66946afeab6cGabor Greif // Loop over all of the return instructions adding entries to the PHI node 952c478e52bf4c12691037856ee103c66946afeab6cGabor Greif // as appropriate. 953fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (PHI) { 954fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 955fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman ReturnInst *RI = Returns[i]; 956fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman assert(RI->getReturnValue()->getType() == PHI->getType() && 957fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman "Ret value not consistent in function!"); 958fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman PHI->addIncoming(RI->getReturnValue(), RI->getParent()); 9595e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 96012a466b9d0e27be453cfa05cff18acc9d7c1cfbaDevang Patel } 961fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 962c581acbbba3cb1af6a08e17314b26344333f9267Chris Lattner 963de62aeaec49ddcf4a4c61fbbb3a22d3a4dd448f0Gabor Greif // Add a branch to the merge points and remove return instructions. 96412a466b9d0e27be453cfa05cff18acc9d7c1cfbaDevang Patel for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 96512a466b9d0e27be453cfa05cff18acc9d7c1cfbaDevang Patel ReturnInst *RI = Returns[i]; 9660744f09efc53d3352ac1caffc61f6e8239201c3bDale Johannesen BranchInst::Create(AfterCallBB, RI); 967b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel RI->eraseFromParent(); 9685e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 969b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel } else if (!Returns.empty()) { 970b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel // Otherwise, if there is exactly one return value, just replace anything 971b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel // using the return value of the call with the computed value. 9725877ad7e90de2179c15914ff9e8f1c72152cac30Eli Friedman if (!TheCall->use_empty()) { 9735877ad7e90de2179c15914ff9e8f1c72152cac30Eli Friedman if (TheCall == Returns[0]->getReturnValue()) 9749e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType())); 9755877ad7e90de2179c15914ff9e8f1c72152cac30Eli Friedman else 9765877ad7e90de2179c15914ff9e8f1c72152cac30Eli Friedman TheCall->replaceAllUsesWith(Returns[0]->getReturnValue()); 9775877ad7e90de2179c15914ff9e8f1c72152cac30Eli Friedman } 978a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 979b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel // Splice the code from the return block into the block that it will return 980b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel // to, which contains the code that was after the call. 981b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel BasicBlock *ReturnBB = Returns[0]->getParent(); 982b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel AfterCallBB->getInstList().splice(AfterCallBB->begin(), 983b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel ReturnBB->getInstList()); 984a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 985b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel // Update PHI nodes that use the ReturnBB to use the AfterCallBB. 986b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel ReturnBB->replaceAllUsesWith(AfterCallBB); 987a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 988b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel // Delete the return instruction now and empty ReturnBB now. 989b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel Returns[0]->eraseFromParent(); 990b8f198af1b62f2ed48dcb914973a9d211dcba38bDevang Patel ReturnBB->eraseFromParent(); 9913787e765facfad5ea62753922d940bcdd52afd57Chris Lattner } else if (!TheCall->use_empty()) { 9923787e765facfad5ea62753922d940bcdd52afd57Chris Lattner // No returns, but something is using the return value of the call. Just 9933787e765facfad5ea62753922d940bcdd52afd57Chris Lattner // nuke the result. 9949e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType())); 9955e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner } 996fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 9975e923dee6024248f58fa83a7c7299437f44f0d1aChris Lattner // Since we are now done with the Call/Invoke, we can delete it. 9983787e765facfad5ea62753922d940bcdd52afd57Chris Lattner TheCall->eraseFromParent(); 999ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 10007152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner // We should always be able to fold the entry block of the function into the 10017152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner // single predecessor of the block... 1002cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!"); 10037152c237b46a920b29d5605af934766b8f9a07a1Chris Lattner BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0); 100444a6807f4f785ecdd96b3aa67dad056677131b98Chris Lattner 1005cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner // Splice the code entry block into calling block, right before the 1006cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner // unconditional branch. 1007cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner OrigBB->getInstList().splice(Br, CalleeEntry->getInstList()); 1008cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner CalleeEntry->replaceAllUsesWith(OrigBB); // Update PHI nodes 1009cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner 1010cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner // Remove the unconditional branch. 1011cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner OrigBB->getInstList().erase(Br); 1012cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner 1013cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner // Now we can remove the CalleeEntry block, which is now empty. 1014cd01ae5c7071fb99a665b2bbea7428d769792ab8Chris Lattner Caller->getBasicBlockList().erase(CalleeEntry); 1015a7212e58260f6d1ead0c4eec7af400cf6c0d289eDuncan Sands 10166fb881c036c32728c4a128d81b6083457e534e09Duncan Sands // If we inserted a phi node, check to see if it has a single value (e.g. all 10176fb881c036c32728c4a128d81b6083457e534e09Duncan Sands // the entries are the same or undef). If so, remove the PHI so it doesn't 10186fb881c036c32728c4a128d81b6083457e534e09Duncan Sands // block other optimizations. 10196fb881c036c32728c4a128d81b6083457e534e09Duncan Sands if (PHI) 10206fb881c036c32728c4a128d81b6083457e534e09Duncan Sands if (Value *V = SimplifyInstruction(PHI, IFI.TD)) { 10216fb881c036c32728c4a128d81b6083457e534e09Duncan Sands PHI->replaceAllUsesWith(V); 10226fb881c036c32728c4a128d81b6083457e534e09Duncan Sands PHI->eraseFromParent(); 10236fb881c036c32728c4a128d81b6083457e534e09Duncan Sands } 10246fb881c036c32728c4a128d81b6083457e534e09Duncan Sands 1025ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner return true; 1026ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner} 1027