From 83f03bfc3f60a05b9ca5807f837c09798632095e Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sat, 27 May 2006 01:22:24 +0000 Subject: Implement a new method, CloneAndPruneFunctionInto, as documented. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@28519 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/CloneFunction.cpp | 188 +++++++++++++++++++++++++++++++++ lib/Transforms/Utils/ValueMapper.cpp | 4 +- 2 files changed, 189 insertions(+), 3 deletions(-) (limited to 'lib/Transforms') diff --git a/lib/Transforms/Utils/CloneFunction.cpp b/lib/Transforms/Utils/CloneFunction.cpp index f6341fa3cf..623da058db 100644 --- a/lib/Transforms/Utils/CloneFunction.cpp +++ b/lib/Transforms/Utils/CloneFunction.cpp @@ -19,6 +19,7 @@ #include "llvm/Instructions.h" #include "llvm/Function.h" #include "ValueMapper.h" +#include "llvm/Transforms/Utils/Local.h" using namespace llvm; // CloneBasicBlock - See comments in Cloning.h @@ -143,3 +144,190 @@ Function *llvm::CloneFunction(const Function *F, return NewF; } + + +namespace { + /// PruningFunctionCloner - This class is a private class used to implement + /// the CloneAndPruneFunctionInto method. + struct PruningFunctionCloner { + Function *NewFunc; + const Function *OldFunc; + std::map &ValueMap; + std::vector &Returns; + const char *NameSuffix; + ClonedCodeInfo *CodeInfo; + + public: + PruningFunctionCloner(Function *newFunc, const Function *oldFunc, + std::map &valueMap, + std::vector &returns, + const char *nameSuffix, + ClonedCodeInfo *codeInfo) + : NewFunc(newFunc), OldFunc(oldFunc), ValueMap(valueMap), Returns(returns), + NameSuffix(nameSuffix), CodeInfo(codeInfo) { + } + + /// CloneBlock - The specified block is found to be reachable, clone it and + /// anything that it can reach. + void CloneBlock(const BasicBlock *BB); + + public: + /// ConstantFoldMappedInstruction - Constant fold the specified instruction, + /// mapping its operands through ValueMap if they are available. + Constant *ConstantFoldMappedInstruction(const Instruction *I); + }; +} + +/// CloneBlock - The specified block is found to be reachable, clone it and +/// anything that it can reach. +void PruningFunctionCloner::CloneBlock(const BasicBlock *BB) { + Value *&BBEntry = ValueMap[BB]; + + // Have we already cloned this block? + if (BBEntry) return; + + // Nope, clone it now. + BasicBlock *NewBB; + BBEntry = NewBB = new BasicBlock(); + if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix); + + bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; + + // Loop over all instructions, and copy them over, DCE'ing as we go. This + // loop doesn't include the terminator. + for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end(); + II != IE; ++II) { + // If this instruction constant folds, don't bother cloning the instruction, + // instead, just add the constant to the value map. + if (Constant *C = ConstantFoldMappedInstruction(II)) { + ValueMap[II] = C; + continue; + } + + Instruction *NewInst = II->clone(); + if (II->hasName()) + NewInst->setName(II->getName()+NameSuffix); + NewBB->getInstList().push_back(NewInst); + ValueMap[II] = NewInst; // Add instruction map to value. + + hasCalls |= isa(II); + if (const AllocaInst *AI = dyn_cast(II)) { + if (isa(AI->getArraySize())) + hasStaticAllocas = true; + else + hasDynamicAllocas = true; + } + } + + if (CodeInfo) { + CodeInfo->ContainsCalls |= hasCalls; + CodeInfo->ContainsUnwinds |= isa(BB->getTerminator()); + CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; + CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && + BB != &BB->getParent()->front(); + } + + if (ReturnInst *RI = dyn_cast(NewBB->getTerminator())) + Returns.push_back(RI); + + // Recursively clone any reachable successor blocks. + const TerminatorInst *TI = BB->getTerminator(); + for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) + CloneBlock(TI->getSuccessor(i)); +} + +/// ConstantFoldMappedInstruction - Constant fold the specified instruction, +/// mapping its operands through ValueMap if they are available. +Constant *PruningFunctionCloner:: +ConstantFoldMappedInstruction(const Instruction *I) { + if (isa(I) || isa(I)) { + if (Constant *Op0 = dyn_cast_or_null(MapValue(I->getOperand(0), + ValueMap))) + if (Constant *Op1 = dyn_cast_or_null(MapValue(I->getOperand(1), + ValueMap))) + return ConstantExpr::get(I->getOpcode(), Op0, Op1); + return 0; + } + + std::vector Ops; + for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) + if (Constant *Op = dyn_cast_or_null(MapValue(I->getOperand(i), + ValueMap))) + Ops.push_back(Op); + else + return 0; // All operands not constant! + + return ConstantFoldInstOperands(I->getOpcode(), I->getType(), Ops); +} + + +/// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto, +/// except that it does some simple constant prop and DCE on the fly. The +/// effect of this is to copy significantly less code in cases where (for +/// example) a function call with constant arguments is inlined, and those +/// constant arguments cause a significant amount of code in the callee to be +/// dead. Since this doesn't produce an exactly copy of the input, it can't be +/// used for things like CloneFunction or CloneModule. +void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, + std::map &ValueMap, + std::vector &Returns, + const char *NameSuffix, + ClonedCodeInfo *CodeInfo) { + assert(NameSuffix && "NameSuffix cannot be null!"); + +#ifndef NDEBUG + for (Function::const_arg_iterator I = OldFunc->arg_begin(), + E = OldFunc->arg_end(); I != E; ++I) + assert(ValueMap.count(I) && "No mapping from source argument specified!"); +#endif + + PruningFunctionCloner PFC(NewFunc, OldFunc, ValueMap, Returns, + NameSuffix, CodeInfo); + + // Clone the entry block, and anything recursively reachable from it. + PFC.CloneBlock(&OldFunc->getEntryBlock()); + + // Loop over all of the basic blocks in the old function. If the block was + // reachable, we have cloned it and the old block is now in the value map: + // insert it into the new function in the right order. If not, ignore it. + // + for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end(); + BI != BE; ++BI) { + BasicBlock *NewBB = cast_or_null(ValueMap[BI]); + if (NewBB == 0) continue; // Dead block. + + // Add the new block to the new function. + NewFunc->getBasicBlockList().push_back(NewBB); + + // Loop over all of the instructions in the block, fixing up operand + // references as we go. This uses ValueMap to do all the hard work. + // + BasicBlock::iterator I = NewBB->begin(); + + // Handle PHI nodes specially, as we have to remove references to dead + // blocks. + if (PHINode *PN = dyn_cast(I)) { + unsigned NumPreds = PN->getNumIncomingValues(); + for (; (PN = dyn_cast(I)); ++I) { + for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) { + if (BasicBlock *MappedBlock = + cast(ValueMap[PN->getIncomingBlock(pred)])) { + Value *InVal = MapValue(PN->getIncomingValue(pred), ValueMap); + assert(InVal && "Unknown input value?"); + PN->setIncomingValue(pred, InVal); + PN->setIncomingBlock(pred, MappedBlock); + } else { + PN->removeIncomingValue(pred, false); + --pred, --e; // Revisit the next entry. + } + } + } + } + + // Otherwise, remap the rest of the instructions normally. + for (; I != NewBB->end(); ++I) + RemapInstruction(I, ValueMap); + } +} + + diff --git a/lib/Transforms/Utils/ValueMapper.cpp b/lib/Transforms/Utils/ValueMapper.cpp index b309f9c0e2..d4be6e47ef 100644 --- a/lib/Transforms/Utils/ValueMapper.cpp +++ b/lib/Transforms/Utils/ValueMapper.cpp @@ -30,7 +30,7 @@ Value *llvm::MapValue(const Value *V, std::map &VM) { if (Constant *C = const_cast(dyn_cast(V))) { if (isa(C) || isa(C) || isa(C) || isa(C) || - isa(C) || isa(V)) + isa(C)) return VMSlot = C; // Primitive constants map directly else if (ConstantArray *CA = dyn_cast(C)) { for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) { @@ -130,8 +130,6 @@ Value *llvm::MapValue(const Value *V, std::map &VM) { } } - V->dump(); - assert(0 && "Unknown value type: why didn't it get resolved?!"); return 0; } -- cgit v1.2.3