diff options
Diffstat (limited to 'lib/Transforms/Utils/InlineFunction.cpp')
| -rw-r--r-- | lib/Transforms/Utils/InlineFunction.cpp | 164 |
1 files changed, 164 insertions, 0 deletions
diff --git a/lib/Transforms/Utils/InlineFunction.cpp b/lib/Transforms/Utils/InlineFunction.cpp new file mode 100644 index 0000000000..e88153e1f8 --- /dev/null +++ b/lib/Transforms/Utils/InlineFunction.cpp @@ -0,0 +1,164 @@ +//===- InlineFunction.cpp - Code to perform function inlining -------------===// +// +// This file implements inlining of a function into a call site, resolving +// parameters and the return value as appropriate. +// +// FIXME: This pass should transform alloca instructions in the called function +// into malloc/free pairs! Or perhaps it should refuse to inline them! +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Module.h" +#include "llvm/iTerminators.h" +#include "llvm/iPHINode.h" +#include "llvm/iMemory.h" +#include "llvm/iOther.h" +#include "llvm/DerivedTypes.h" + +// InlineFunction - This function inlines the called function into the basic +// block of the caller. This returns false if it is not possible to inline this +// call. The program is still in a well defined state if this occurs though. +// +// Note that this only does one level of inlining. For example, if the +// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now +// exists in the instruction stream. Similiarly this will inline a recursive +// function by one level. +// +bool InlineFunction(CallInst *CI) { + assert(isa<CallInst>(CI) && "InlineFunction only works on CallInst nodes"); + assert(CI->getParent() && "Instruction not embedded in basic block!"); + assert(CI->getParent()->getParent() && "Instruction not in function!"); + + const Function *CalledFunc = CI->getCalledFunction(); + if (CalledFunc == 0 || // Can't inline external function or indirect + CalledFunc->isExternal() || // call, or call to a vararg function! + CalledFunc->getFunctionType()->isVarArg()) return false; + + BasicBlock *OrigBB = CI->getParent(); + Function *Caller = OrigBB->getParent(); + + // Call splitBasicBlock - The original basic block now ends at the instruction + // immediately before the call. The original basic block now ends with an + // unconditional branch to NewBB, and NewBB starts with the call instruction. + // + BasicBlock *NewBB = OrigBB->splitBasicBlock(CI); + NewBB->setName(OrigBB->getName()+".split"); + + // Remove (unlink) the CallInst from the start of the new basic block. + NewBB->getInstList().remove(CI); + + // If we have a return value generated by this call, convert it into a PHI + // node that gets values from each of the old RET instructions in the original + // function. + // + PHINode *PHI = 0; + if (!CI->use_empty()) { + // The PHI node should go at the front of the new basic block to merge all + // possible incoming values. + // + PHI = new PHINode(CalledFunc->getReturnType(), CI->getName(), + NewBB->begin()); + + // Anything that used the result of the function call should now use the PHI + // node as their operand. + // + CI->replaceAllUsesWith(PHI); + } + + // Get an iterator to the last basic block in the function, which will have + // the new function inlined after it. + // + Function::iterator LastBlock = &Caller->back(); + + // Calculate the vector of arguments to pass into the function cloner... + std::map<const Value*, Value*> ValueMap; + assert((unsigned)std::distance(CalledFunc->abegin(), CalledFunc->aend()) == + CI->getNumOperands()-1 && "No varargs calls can be inlined yet!"); + + unsigned i = 1; + for (Function::const_aiterator I = CalledFunc->abegin(), E=CalledFunc->aend(); + I != E; ++I, ++i) + ValueMap[I] = CI->getOperand(i); + + // Since we are now done with the CallInst, we can delete it. + delete CI; + + // Make a vector to capture the return instructions in the cloned function... + std::vector<ReturnInst*> Returns; + + // Populate the value map with all of the globals in the program. + Module &M = *Caller->getParent(); + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + ValueMap[I] = I; + for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I) + ValueMap[I] = I; + + // Do all of the hard part of cloning the callee into the caller... + CloneFunctionInto(Caller, CalledFunc, ValueMap, Returns, ".i"); + + // Loop over all of the return instructions, turning them into unconditional + // branches to the merge point now... + for (unsigned i = 0, e = Returns.size(); i != e; ++i) { + ReturnInst *RI = Returns[i]; + BasicBlock *BB = RI->getParent(); + + // Add a branch to the merge point where the PHI node would live... + new BranchInst(NewBB, RI); + + if (PHI) { // The PHI node should include this value! + assert(RI->getReturnValue() && "Ret should have value!"); + assert(RI->getReturnValue()->getType() == PHI->getType() && + "Ret value not consistent in function!"); + PHI->addIncoming(RI->getReturnValue(), BB); + } + + // Delete the return instruction now + BB->getInstList().erase(RI); + } + + // Check to see if the PHI node only has one argument. This is a common + // case resulting from there only being a single return instruction in the + // function call. Because this is so common, eliminate the PHI node. + // + if (PHI && PHI->getNumIncomingValues() == 1) { + PHI->replaceAllUsesWith(PHI->getIncomingValue(0)); + PHI->getParent()->getInstList().erase(PHI); + } + + // Change the branch that used to go to NewBB to branch to the first basic + // block of the inlined function. + // + TerminatorInst *Br = OrigBB->getTerminator(); + assert(Br && Br->getOpcode() == Instruction::Br && + "splitBasicBlock broken!"); + Br->setOperand(0, ++LastBlock); + + // If there are any alloca instructions in the block that used to be the entry + // block for the callee, move them to the entry block of the caller. First + // calculate which instruction they should be inserted before. We insert the + // instructions at the end of the current alloca list. + // + BasicBlock::iterator InsertPoint = Caller->begin()->begin(); + while (isa<AllocaInst>(InsertPoint)) ++InsertPoint; + + for (BasicBlock::iterator I = LastBlock->begin(), E = LastBlock->end(); + I != E; ) + if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) { + ++I; // Move to the next instruction + LastBlock->getInstList().remove(AI); + Caller->front().getInstList().insert(InsertPoint, AI); + + } else { + ++I; + } + + // Now that the function is correct, make it a little bit nicer. In + // particular, move the basic blocks inserted from the end of the function + // into the space made by splitting the source basic block. + // + Caller->getBasicBlockList().splice(NewBB, Caller->getBasicBlockList(), + LastBlock, Caller->end()); + + return true; +} |