diff options
Diffstat (limited to 'lib/Transforms/IPO/InlineSimple.cpp')
| -rw-r--r-- | lib/Transforms/IPO/InlineSimple.cpp | 283 |
1 files changed, 283 insertions, 0 deletions
diff --git a/lib/Transforms/IPO/InlineSimple.cpp b/lib/Transforms/IPO/InlineSimple.cpp new file mode 100644 index 0000000000..a1e3156b3b --- /dev/null +++ b/lib/Transforms/IPO/InlineSimple.cpp @@ -0,0 +1,283 @@ +//===- MethodInlining.cpp - Code to perform method inlining ---------------===// +// +// This file implements inlining of methods. +// +// Specifically, this: +// * Exports functionality to inline any method call +// * Inlines methods that consist of a single basic block +// * Is able to inline ANY method call +// . Has a smart heuristic for when to inline a method +// +// Notice that: +// * This pass has a habit of introducing duplicated constant pool entries, +// and also opens up a lot of opportunities for constant propogation. It is +// a good idea to to run a constant propogation pass, then a DCE pass +// sometime after running this pass. +// +// TODO: Currently this throws away all of the symbol names in the method being +// inlined to try to avoid name clashes. Use a name if it's not taken +// +//===----------------------------------------------------------------------===// + +#include "llvm/Module.h" +#include "llvm/Method.h" +#include "llvm/BasicBlock.h" +#include "llvm/iTerminators.h" +#include "llvm/iOther.h" +#include "llvm/Opt/AllOpts.h" +#include <algorithm> +#include <map> + +#include "llvm/Assembly/Writer.h" + +// RemapInstruction - Convert the instruction operands from referencing the +// current values into those specified by ValueMap. +// +static inline void RemapInstruction(Instruction *I, + map<const Value *, Value*> &ValueMap) { + + for (unsigned op = 0; const Value *Op = I->getOperand(op); op++) { + Value *V = ValueMap[Op]; + if (!V && Op->getValueType() == Value::MethodVal) + continue; // Methods don't get relocated + + if (!V) { + cerr << "Val = " << endl << Op << "Addr = " << (void*)Op << endl; + cerr << "Inst = " << I; + } + assert(V && "Referenced value not in value map!"); + I->setOperand(op, V); + } +} + +// InlineMethod - This function forcibly inlines the called method 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 +// method by one level. +// +bool InlineMethod(BasicBlock::InstListType::iterator CIIt) { + assert((*CIIt)->getInstType() == Instruction::Call && + "InlineMethod only works on CallInst nodes!"); + assert((*CIIt)->getParent() && "Instruction not embedded in basic block!"); + assert((*CIIt)->getParent()->getParent() && "Instruction not in method!"); + + CallInst *CI = (CallInst*)*CIIt; + const Method *CalledMeth = CI->getCalledMethod(); + Method *CurrentMeth = CI->getParent()->getParent(); + + //cerr << "Inlining " << CalledMeth->getName() << " into " + // << CurrentMeth->getName() << endl; + + BasicBlock *OrigBB = CI->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(CIIt); + + // 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 + // method. + // + PHINode *PHI = 0; + if (CalledMeth->getReturnType() != Type::VoidTy) { + PHI = new PHINode(CalledMeth->getReturnType(), CI->getName()); + + // The PHI node should go at the front of the new basic block to merge all + // possible incoming values. + // + NewBB->getInstList().push_front(PHI); + + // Anything that used the result of the function call should now use the PHI + // node as their operand. + // + CI->replaceAllUsesWith(PHI); + } + + // Keep a mapping between the original method's values and the new duplicated + // code's values. This includes all of: Method arguments, instruction values, + // constant pool entries, and basic blocks. + // + map<const Value *, Value*> ValueMap; + + // Add the method arguments to the mapping: (start counting at 1 to skip the + // method reference itself) + // + Method::ArgumentListType::const_iterator PTI = + CalledMeth->getArgumentList().begin(); + for (unsigned a = 1; Value *Operand = CI->getOperand(a); ++a, ++PTI) { + ValueMap[*PTI] = Operand; + } + + + ValueMap[NewBB] = NewBB; // Returns get converted to reference NewBB + + // Loop over all of the basic blocks in the method, inlining them as + // appropriate. Keep track of the first basic block of the method... + // + for (Method::BasicBlocksType::const_iterator BI = + CalledMeth->getBasicBlocks().begin(); + BI != CalledMeth->getBasicBlocks().end(); BI++) { + const BasicBlock *BB = *BI; + assert(BB->getTerminator() && "BasicBlock doesn't have terminator!?!?"); + + // Create a new basic block to copy instructions into! + BasicBlock *IBB = new BasicBlock("", NewBB->getParent()); + + ValueMap[*BI] = IBB; // Add basic block mapping. + + // Make sure to capture the mapping that a return will use... + // TODO: This assumes that the RET is returning a value computed in the same + // basic block as the return was issued from! + // + const TerminatorInst *TI = BB->getTerminator(); + + // Loop over all instructions copying them over... + Instruction *NewInst; + for (BasicBlock::InstListType::const_iterator II = BB->getInstList().begin(); + II != (BB->getInstList().end()-1); II++) { + IBB->getInstList().push_back((NewInst = (*II)->clone())); + ValueMap[*II] = NewInst; // Add instruction map to value. + } + + // Copy over the terminator now... + switch (TI->getInstType()) { + case Instruction::Ret: { + const ReturnInst *RI = (const ReturnInst*)TI; + + 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 method!"); + PHI->addIncoming((Value*)RI->getReturnValue()); + } + + // Add a branch to the code that was after the original Call. + IBB->getInstList().push_back(new BranchInst(NewBB)); + break; + } + case Instruction::Br: + IBB->getInstList().push_back(TI->clone()); + break; + + default: + cerr << "MethodInlining: Don't know how to handle terminator: " << TI; + abort(); + } + } + + + // Copy over the constant pool... + // + const ConstantPool &CP = CalledMeth->getConstantPool(); + ConstantPool &NewCP = CurrentMeth->getConstantPool(); + for (ConstantPool::plane_const_iterator PI = CP.begin(); PI != CP.end(); ++PI){ + ConstantPool::PlaneType &Plane = **PI; + for (ConstantPool::PlaneType::const_iterator I = Plane.begin(); + I != Plane.end(); ++I) { + ConstPoolVal *NewVal = (*I)->clone(); // Copy existing constant + NewCP.insert(NewVal); // Insert the new copy into local const pool + ValueMap[*I] = NewVal; // Keep track of constant value mappings + } + } + + // Loop over all of the instructions in the method, fixing up operand + // references as we go. This uses ValueMap to do all the hard work. + // + for (Method::BasicBlocksType::const_iterator BI = + CalledMeth->getBasicBlocks().begin(); + BI != CalledMeth->getBasicBlocks().end(); BI++) { + const BasicBlock *BB = *BI; + BasicBlock *NBB = (BasicBlock*)ValueMap[BB]; + + // Loop over all instructions, fixing each one as we find it... + // + for (BasicBlock::InstListType::iterator II = NBB->getInstList().begin(); + II != NBB->getInstList().end(); II++) + RemapInstruction(*II, ValueMap); + } + + if (PHI) RemapInstruction(PHI, ValueMap); // Fix the PHI node also... + + // Change the branch that used to go to NewBB to branch to the first basic + // block of the inlined method. + // + TerminatorInst *Br = OrigBB->getTerminator(); + assert(Br && Br->getInstType() == Instruction::Br && + "splitBasicBlock broken!"); + Br->setOperand(0, ValueMap[CalledMeth->getBasicBlocks().front()]); + + // Since we are now done with the CallInst, we can finally delete it. + delete CI; + return true; +} + +bool InlineMethod(CallInst *CI) { + assert(CI->getParent() && "CallInst not embeded in BasicBlock!"); + BasicBlock *PBB = CI->getParent(); + + BasicBlock::InstListType::iterator CallIt = find(PBB->getInstList().begin(), + PBB->getInstList().end(), + CI); + assert(CallIt != PBB->getInstList().end() && + "CallInst has parent that doesn't contain CallInst?!?"); + return InlineMethod(CallIt); +} + +static inline bool ShouldInlineMethod(const CallInst *CI, const Method *M) { + assert(CI->getParent() && CI->getParent()->getParent() && + "Call not embedded into a method!"); + + // Don't inline a recursive call. + if (CI->getParent()->getParent() == M) return false; + + // Don't inline something too big. This is a really crappy heuristic + if (M->getBasicBlocks().size() > 3) return false; + + // Don't inline into something too big. This is a **really** crappy heuristic + if (CI->getParent()->getParent()->getBasicBlocks().size() > 10) return false; + + // Go ahead and try just about anything else. + return true; +} + + +static inline bool DoMethodInlining(BasicBlock *BB) { + for (BasicBlock::InstListType::iterator I = BB->getInstList().begin(); + I != BB->getInstList().end(); I++) { + if ((*I)->getInstType() == Instruction::Call) { + // Check to see if we should inline this method + CallInst *CI = (CallInst*)*I; + Method *M = CI->getCalledMethod(); + if (ShouldInlineMethod(CI, M)) + return InlineMethod(I); + } + } + return false; +} + +bool DoMethodInlining(Method *M) { + Method::BasicBlocksType &BBs = M->getBasicBlocks(); + bool Changed = false; + + // Loop through now and inline instructions a basic block at a time... + for (Method::BasicBlocksType::iterator I = BBs.begin(); I != BBs.end(); ) + if (DoMethodInlining(*I)) { + Changed = true; + // Iterator is now invalidated by new basic blocks inserted + I = BBs.begin(); + } else { + ++I; + } + + return Changed; +} |