16c2e2e52870230838380778415d9ad543e66dae3Chris Lattner//===- CloneFunction.cpp - Clone a function into another function ---------===// 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//===----------------------------------------------------------------------===// 96c2e2e52870230838380778415d9ad543e66dae3Chris Lattner// 106c2e2e52870230838380778415d9ad543e66dae3Chris Lattner// This file implements the CloneFunctionInto interface, which is used as the 116c2e2e52870230838380778415d9ad543e66dae3Chris Lattner// low-level function cloner. This is used by the CloneFunction and function 126c2e2e52870230838380778415d9ad543e66dae3Chris Lattner// inliner to do the dirty work of copying the body of a function around. 136c2e2e52870230838380778415d9ad543e66dae3Chris Lattner// 146c2e2e52870230838380778415d9ad543e66dae3Chris Lattner//===----------------------------------------------------------------------===// 15fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner 16309f19391b571084ba9f6b0372e63b875ca2b869Chris Lattner#include "llvm/Transforms/Utils/Cloning.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallVector.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ConstantFolding.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/InstructionSimplify.h" 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/DebugInfo.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 250b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalVariable.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 280b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 290b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Metadata.h" 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Module.h" 31afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth#include "llvm/Transforms/Utils/BasicBlockUtils.h" 32afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth#include "llvm/Transforms/Utils/Local.h" 3305ea54e8869a81b8dd846397175f218f97968907Dan Gohman#include "llvm/Transforms/Utils/ValueMapper.h" 345e665f559419c7f58a4fd9360cd488f065505c44Chris Lattner#include <map> 35f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 36d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// See comments in Cloning.h. 38f7703df4968084c18c248c1feea9961c19a32e6aChris LattnerBasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB, 39774cca70b10bc679daff8203d639d9004a2eb194Devang Patel ValueToValueMapTy &VMap, 405deb57c68552a85094b786dfdbd16e3744716733Benjamin Kramer const Twine &NameSuffix, Function *F, 41a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner ClonedCodeInfo *CodeInfo) { 421d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F); 4317d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix); 4417d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner 45a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; 46a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner 47a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner // Loop over all instructions, and copy them over. 4817d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end(); 4917d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner II != IE; ++II) { 506776064d190701c5bae4d5403939eed2e480d1cdNick Lewycky Instruction *NewInst = II->clone(); 5117d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner if (II->hasName()) 5217d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner NewInst->setName(II->getName()+NameSuffix); 5317d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner NewBB->getInstList().push_back(NewInst); 5429d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel VMap[II] = NewInst; // Add instruction map to value. 55a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner 568aa90feb3d391145d2bc82a9d51a5714a4fe71f8Dale Johannesen hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II)); 57a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) { 58a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner if (isa<ConstantInt>(AI->getArraySize())) 59a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner hasStaticAllocas = true; 60a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner else 61a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner hasDynamicAllocas = true; 62a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner } 63a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner } 64a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner 65a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner if (CodeInfo) { 66a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner CodeInfo->ContainsCalls |= hasCalls; 67a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; 68a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 69ecb7a77885b174cf4d001a9b48533b3979e7810dDan Gohman BB != &BB->getParent()->getEntryBlock(); 7017d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner } 7117d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner return NewBB; 7217d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner} 7317d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner 74fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner// Clone OldFunc into NewFunc, transforming the old arguments into references to 756cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman// VMap values. 76fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner// 77f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnervoid llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc, 78774cca70b10bc679daff8203d639d9004a2eb194Devang Patel ValueToValueMapTy &VMap, 796cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman bool ModuleLevelChanges, 80ec1bea0d94372985a0a5eb283e644c6d0dd345dcChris Lattner SmallVectorImpl<ReturnInst*> &Returns, 81d24397a9319a41e80169f572ad274a711f41d64eMon P Wang const char *NameSuffix, ClonedCodeInfo *CodeInfo, 82a84a83bbcdfaecadfc6574094272fd3edc429a23James Molloy ValueMapTypeRemapper *TypeMapper, 83a84a83bbcdfaecadfc6574094272fd3edc429a23James Molloy ValueMaterializer *Materializer) { 84dcd8040d115803e427dc1caf9feb44a894eef927Chris Lattner assert(NameSuffix && "NameSuffix cannot be null!"); 85fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 86d18015599cbe09dd327b5f73501581a865bf27daChris Lattner#ifndef NDEBUG 87a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner for (Function::const_arg_iterator I = OldFunc->arg_begin(), 88a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner E = OldFunc->arg_end(); I != E; ++I) 8929d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel assert(VMap.count(I) && "No mapping from source argument specified!"); 90d18015599cbe09dd327b5f73501581a865bf27daChris Lattner#endif 91fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Copy all attributes other than those stored in the AttributeSet. We need 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // to remap the parameter indices of the AttributeSet. 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AttributeSet NewAttrs = NewFunc->getAttributes(); 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewFunc->copyAttributesFrom(OldFunc); 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewFunc->setAttributes(NewAttrs); 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 980f57a98a65df5e617ed0adcf0ca0877745c84a79Joey Gouly AttributeSet OldAttrs = OldFunc->getAttributes(); 990f57a98a65df5e617ed0adcf0ca0877745c84a79Joey Gouly // Clone any argument attributes that are present in the VMap. 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (const Argument &OldArg : OldFunc->args()) 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Argument *NewArg = dyn_cast<Argument>(VMap[&OldArg])) { 1020f57a98a65df5e617ed0adcf0ca0877745c84a79Joey Gouly AttributeSet attrs = 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OldAttrs.getParamAttributes(OldArg.getArgNo() + 1); 1040f57a98a65df5e617ed0adcf0ca0877745c84a79Joey Gouly if (attrs.getNumSlots() > 0) 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewArg->addAttr(attrs); 1060f57a98a65df5e617ed0adcf0ca0877745c84a79Joey Gouly } 10782cf32e5efbb1f49ddd5742743599fa7f23ab925Andrew Lenharth 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewFunc->setAttributes( 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewFunc->getAttributes() 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines .addAttributes(NewFunc->getContext(), AttributeSet::ReturnIndex, 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OldAttrs.getRetAttributes()) 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines .addAttributes(NewFunc->getContext(), AttributeSet::FunctionIndex, 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OldAttrs.getFnAttributes())); 1149e49f1bc582a709349295c00c585246558c52958Anton Korobeynikov 115fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner // Loop over all of the basic blocks in the function, cloning them as 116dcd8040d115803e427dc1caf9feb44a894eef927Chris Lattner // appropriate. Note that we save BE this way in order to handle cloning of 117dcd8040d115803e427dc1caf9feb44a894eef927Chris Lattner // recursive functions into themselves. 118fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner // 119fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end(); 120fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner BI != BE; ++BI) { 12118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner const BasicBlock &BB = *BI; 122fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 12317d145d26fbe2fd0091a291cddefde912dc54503Chris Lattner // Create a new basic block and copy instructions into it! 124b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner BasicBlock *CBB = CloneBasicBlock(&BB, VMap, NameSuffix, NewFunc, CodeInfo); 125fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner 1264090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // Add basic block mapping. 1274090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman VMap[&BB] = CBB; 1284090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman 1294090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // It is only legal to clone a function if a block address within that 1304090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // function is never referenced outside of the function. Given that, we 1314090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // want to map block addresses from the old function to block addresses in 1324090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // the clone. (This is different from the generic ValueMapper 1334090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // implementation, which generates an invalid blockaddress when 1344090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // cloning a function.) 1354090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman if (BB.hasAddressTaken()) { 1364090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc), 1374090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman const_cast<BasicBlock*>(&BB)); 1384090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman VMap[OldBBAddr] = BlockAddress::get(NewFunc, CBB); 1394090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman } 1404090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman 1414090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // Note return instructions for the caller. 142dcd8040d115803e427dc1caf9feb44a894eef927Chris Lattner if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator())) 143dcd8040d115803e427dc1caf9feb44a894eef927Chris Lattner Returns.push_back(RI); 144fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner } 145fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner 146fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // Loop over all of the instructions in the function, fixing up operand 14729d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel // references as we go. This uses VMap to do all the hard work. 14829d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel for (Function::iterator BB = cast<BasicBlock>(VMap[OldFunc->begin()]), 149280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky BE = NewFunc->end(); BB != BE; ++BB) 150fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner // Loop over all instructions, fixing each one as we find it... 151a33ceaa2d46f6bf50c979e28581d9e4941b45d44Chris Lattner for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II) 152b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner RemapInstruction(II, VMap, 153d24397a9319a41e80169f572ad274a711f41d64eMon P Wang ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges, 154a84a83bbcdfaecadfc6574094272fd3edc429a23James Molloy TypeMapper, Materializer); 155fa703a4ae5dedce3cb43b75a57b6546a8dc61a06Chris Lattner} 1565a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Find the MDNode which corresponds to the DISubprogram data that described F. 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic MDNode* FindSubprogram(const Function *F, DebugInfoFinder &Finder) { 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (DISubprogram Subprogram : Finder.subprograms()) { 1602c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar if (Subprogram->describes(F)) 1612c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar return Subprogram; 16236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 16436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Add an operand to an existing MDNode. The new operand will be added at the 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// back of the operand list. 1682c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainarstatic void AddOperand(DICompileUnit CU, MDSubprogramArray SPs, Metadata *NewSP) { 169ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallVector<Metadata *, 16> NewSPs; 1702c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar NewSPs.reserve(SPs.size() + 1); 1712c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar for (auto *SP : SPs) 1722c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar NewSPs.push_back(SP); 173ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines NewSPs.push_back(NewSP); 1742c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar CU->replaceSubprograms(MDTuple::get(CU->getContext(), NewSPs)); 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 17636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Clone the module-level debug info associated with OldFunc. The cloned data 17836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// will point to NewFunc instead. 17936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic void CloneDebugInfoMetadata(Function *NewFunc, const Function *OldFunc, 18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ValueToValueMapTy &VMap) { 18136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DebugInfoFinder Finder; 18236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Finder.processModule(*OldFunc->getParent()); 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const MDNode *OldSubprogramMDNode = FindSubprogram(OldFunc, Finder); 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!OldSubprogramMDNode) return; 18636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Ensure that OldFunc appears in the map. 18836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // (if it's already there it must point to NewFunc anyway) 18936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines VMap[OldFunc] = NewFunc; 1902c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar DISubprogram NewSubprogram = 1912c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar cast<MDSubprogram>(MapMetadata(OldSubprogramMDNode, VMap)); 19236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (DICompileUnit CU : Finder.compile_units()) { 1942c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar auto Subprograms = CU->getSubprograms(); 19536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If the compile unit's function list contains the old function, it should 19636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // also contain the new one. 1972c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar for (auto *SP : Subprograms) { 1982c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar if (SP == OldSubprogramMDNode) { 199ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines AddOperand(CU, Subprograms, NewSubprogram); 200ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 20136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 20236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 20336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 20436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 20536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 2064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// Return a copy of the specified function, but without 2075a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner/// embedding the function into another module. Also, any references specified 20829d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel/// in the VMap are changed to refer to their mapped value instead of the 20929d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel/// original one. If any of the arguments to the function are in the VMap, 21029d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel/// the arguments are deleted from the resultant function. The VMap is 2115a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner/// updated to include mappings from all of the instructions and basicblocks in 2125a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner/// the function from their old to new values. 2135a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner/// 214b5fa5fcecc97168a72c9533c84cf297c018b957cChris LattnerFunction *llvm::CloneFunction(const Function *F, ValueToValueMapTy &VMap, 2156cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman bool ModuleLevelChanges, 216a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner ClonedCodeInfo *CodeInfo) { 2175fdd6c8793462549e3593890ec61573da06e3346Jay Foad std::vector<Type*> ArgTypes; 2185a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner 2195a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner // The user might be deleting arguments to the function by specifying them in 22029d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel // the VMap. If so, we need to not add the arguments to the arg ty vector 2215a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner // 222a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); 223a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner I != E; ++I) 22429d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel if (VMap.count(I) == 0) // Haven't mapped the argument to anything yet? 2255a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner ArgTypes.push_back(I->getType()); 2265a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner 2275a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner // Create a new function type... 228debcb01b0f0a15f568ca69e8f288fade4bfc7297Owen Anderson FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(), 2295a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner ArgTypes, F->getFunctionType()->isVarArg()); 2305a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner 2315a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner // Create the new function... 232051a950000e21935165db56695e35bade668193bGabor Greif Function *NewF = Function::Create(FTy, F->getLinkage(), F->getName()); 233fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 2345a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner // Loop over the arguments, copying the names of the mapped arguments over... 235e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner Function::arg_iterator DestI = NewF->arg_begin(); 236a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); 237a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner I != E; ++I) 23829d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel if (VMap.count(I) == 0) { // Is this argument preserved? 2395a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner DestI->setName(I->getName()); // Copy the name over... 24029d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel VMap[I] = DestI++; // Add mapping to VMap 2415a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner } 2425a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner 24336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ModuleLevelChanges) 24436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CloneDebugInfoMetadata(NewF, F, VMap); 24536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 246ec1bea0d94372985a0a5eb283e644c6d0dd345dcChris Lattner SmallVector<ReturnInst*, 8> Returns; // Ignore returns cloned. 2476cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman CloneFunctionInto(NewF, F, VMap, ModuleLevelChanges, Returns, "", CodeInfo); 248fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman return NewF; 2495a8932f57ffaf09bf5119fea142c96e5e3f653dbChris Lattner} 250d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 25183f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner 25283f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner 25383f03bfc3f60a05b9ca5807f837c09798632095eChris Lattnernamespace { 2544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// This is a private class used to implement CloneAndPruneFunctionInto. 2556726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct PruningFunctionCloner { 25683f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner Function *NewFunc; 25783f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner const Function *OldFunc; 258774cca70b10bc679daff8203d639d9004a2eb194Devang Patel ValueToValueMapTy &VMap; 2596cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman bool ModuleLevelChanges; 26083f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner const char *NameSuffix; 26183f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner ClonedCodeInfo *CodeInfo; 262ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines CloningDirector *Director; 263ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ValueMapTypeRemapper *TypeMapper; 264ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ValueMaterializer *Materializer; 265ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 26683f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner public: 26783f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner PruningFunctionCloner(Function *newFunc, const Function *oldFunc, 2684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ValueToValueMapTy &valueMap, bool moduleLevelChanges, 2694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const char *nameSuffix, ClonedCodeInfo *codeInfo, 270ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines CloningDirector *Director) 2714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar : NewFunc(newFunc), OldFunc(oldFunc), VMap(valueMap), 2724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ModuleLevelChanges(moduleLevelChanges), NameSuffix(nameSuffix), 2734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar CodeInfo(codeInfo), Director(Director) { 274ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // These are optional components. The Director may return null. 275ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Director) { 276ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TypeMapper = Director->getTypeRemapper(); 277ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Materializer = Director->getValueMaterializer(); 278ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } else { 279ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TypeMapper = nullptr; 280ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Materializer = nullptr; 281ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 28283f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner } 28383f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner 2844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// The specified block is found to be reachable, clone it and 28583f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner /// anything that it can reach. 286ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void CloneBlock(const BasicBlock *BB, 287ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock::const_iterator StartingInst, 28867ef241f45331d1df572ab95f5f19475d8e48a9eChris Lattner std::vector<const BasicBlock*> &ToClone); 28983f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner }; 29083f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner} 29183f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner 2924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// The specified block is found to be reachable, clone it and 29383f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner/// anything that it can reach. 29467ef241f45331d1df572ab95f5f19475d8e48a9eChris Lattnervoid PruningFunctionCloner::CloneBlock(const BasicBlock *BB, 295ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock::const_iterator StartingInst, 29667ef241f45331d1df572ab95f5f19475d8e48a9eChris Lattner std::vector<const BasicBlock*> &ToClone){ 297afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth WeakVH &BBEntry = VMap[BB]; 29883f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner 29983f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // Have we already cloned this block? 30083f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner if (BBEntry) return; 30183f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner 30283f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // Nope, clone it now. 30383f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner BasicBlock *NewBB; 3041d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BBEntry = NewBB = BasicBlock::Create(BB->getContext()); 30583f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix); 30683f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner 3074090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // It is only legal to clone a function if a block address within that 3084090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // function is never referenced outside of the function. Given that, we 3094090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // want to map block addresses from the old function to block addresses in 3104090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // the clone. (This is different from the generic ValueMapper 3114090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // implementation, which generates an invalid blockaddress when 3124090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // cloning a function.) 3134090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // 3144090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // Note that we don't need to fix the mapping for unreachable blocks; 3154090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman // the default mapping there is safe. 3164090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman if (BB->hasAddressTaken()) { 3174090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc), 3184090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman const_cast<BasicBlock*>(BB)); 3194090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB); 3204090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman } 3214090e1ce91fd5a6a690fd0bd6c9240b69ac1f301Eli Friedman 32283f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false; 323ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 32483f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // Loop over all instructions, and copy them over, DCE'ing as we go. This 32583f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // loop doesn't include the terminator. 326ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (BasicBlock::const_iterator II = StartingInst, IE = --BB->end(); 32783f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner II != IE; ++II) { 328ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // If the "Director" remaps the instruction, don't clone it. 329ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Director) { 330ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines CloningDirector::CloningAction Action 331ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines = Director->handleInstruction(VMap, II, NewBB); 332ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // If the cloning director says stop, we want to stop everything, not 333ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // just break out of the loop (which would cause the terminator to be 334ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // cloned). The cloning director is responsible for inserting a proper 335ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // terminator into the new basic block in this case. 336ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Action == CloningDirector::StopCloningBB) 337ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return; 338ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // If the cloning director says skip, continue to the next instruction. 339ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // In this case, the cloning director is responsible for mapping the 340ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // skipped instruction to some value that is defined in the new 341ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // basic block. 342ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Action == CloningDirector::SkipInstruction) 343ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines continue; 344ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 345ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 346d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth Instruction *NewInst = II->clone(); 347d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth 348d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth // Eagerly remap operands to the newly cloned instruction, except for PHI 349d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth // nodes for which we defer processing until we update the CFG. 350d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth if (!isa<PHINode>(NewInst)) { 351d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth RemapInstruction(NewInst, VMap, 352ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges, 353ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TypeMapper, Materializer); 354d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth 355d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth // If we can simplify this instruction to some other value, simply add 356d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth // a mapping to that value rather than inserting a new instruction into 357d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth // the basic block. 3584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Value *V = 3594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar SimplifyInstruction(NewInst, BB->getModule()->getDataLayout())) { 360d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth // On the off-chance that this simplifies to an instruction in the old 361d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth // function, map it back into the new function. 362d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth if (Value *MappedV = VMap.lookup(V)) 363d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth V = MappedV; 364d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth 365d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth VMap[II] = V; 366d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth delete NewInst; 367d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth continue; 368d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth } 36983f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner } 370f66d7b5a51f956901e5949413965fecc41cc9761Devang Patel 37183f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner if (II->hasName()) 37283f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner NewInst->setName(II->getName()+NameSuffix); 37329d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel VMap[II] = NewInst; // Add instruction map to value. 374d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth NewBB->getInstList().push_back(NewInst); 3758aa90feb3d391145d2bc82a9d51a5714a4fe71f8Dale Johannesen hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II)); 37683f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) { 37783f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner if (isa<ConstantInt>(AI->getArraySize())) 37883f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner hasStaticAllocas = true; 37983f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner else 38083f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner hasDynamicAllocas = true; 38183f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner } 38283f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner } 38383f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner 38435033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // Finally, clone over the terminator. 38535033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner const TerminatorInst *OldTI = BB->getTerminator(); 38635033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner bool TerminatorDone = false; 387ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Director) { 388ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines CloningDirector::CloningAction Action 389ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines = Director->handleInstruction(VMap, OldTI, NewBB); 390ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // If the cloning director says stop, we want to stop everything, not 391ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // just break out of the loop (which would cause the terminator to be 392ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // cloned). The cloning director is responsible for inserting a proper 393ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // terminator into the new basic block in this case. 394ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Action == CloningDirector::StopCloningBB) 395ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return; 3964c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Action == CloningDirector::CloneSuccessors) { 3974c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // If the director says to skip with a terminate instruction, we still 3984c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // need to clone this block's successors. 3992c3e0051c31c3f5b2328b447eadf1cf9c4427442Pirama Arumuga Nainar const TerminatorInst *TI = NewBB->getTerminator(); 4004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 4014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ToClone.push_back(TI->getSuccessor(i)); 4024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return; 4034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 404ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(Action != CloningDirector::SkipInstruction && 405ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines "SkipInstruction is not valid for terminators."); 406ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 40735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) { 40835033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner if (BI->isConditional()) { 40935033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // If the condition was a known constant in the callee... 4106b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition()); 4116b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng // Or is a known constant in the caller... 412dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Cond) { 4136688c4a742b3d4ad511e35b463c2fe0f8abc04abRafael Espindola Value *V = VMap[BI->getCondition()]; 4146688c4a742b3d4ad511e35b463c2fe0f8abc04abRafael Espindola Cond = dyn_cast_or_null<ConstantInt>(V); 4156688c4a742b3d4ad511e35b463c2fe0f8abc04abRafael Espindola } 4166b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng 4176b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng // Constant fold to uncond branch! 4186b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (Cond) { 419579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue()); 42029d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel VMap[OldTI] = BranchInst::Create(Dest, NewBB); 42167ef241f45331d1df572ab95f5f19475d8e48a9eChris Lattner ToClone.push_back(Dest); 42235033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner TerminatorDone = true; 42335033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 42435033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 42535033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) { 42635033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // If switching on a value known constant in the caller. 42735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition()); 428dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Cond) { // Or known constant after constant prop in the callee... 4296688c4a742b3d4ad511e35b463c2fe0f8abc04abRafael Espindola Value *V = VMap[SI->getCondition()]; 4306688c4a742b3d4ad511e35b463c2fe0f8abc04abRafael Espindola Cond = dyn_cast_or_null<ConstantInt>(V); 4316688c4a742b3d4ad511e35b463c2fe0f8abc04abRafael Espindola } 43235033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner if (Cond) { // Constant fold to uncond branch! 433c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy SwitchInst::ConstCaseIt Case = SI->findCaseValue(Cond); 434c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy BasicBlock *Dest = const_cast<BasicBlock*>(Case.getCaseSuccessor()); 43529d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel VMap[OldTI] = BranchInst::Create(Dest, NewBB); 43667ef241f45331d1df572ab95f5f19475d8e48a9eChris Lattner ToClone.push_back(Dest); 43735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner TerminatorDone = true; 43835033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 43935033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 44035033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner 44135033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner if (!TerminatorDone) { 4426776064d190701c5bae4d5403939eed2e480d1cdNick Lewycky Instruction *NewInst = OldTI->clone(); 44335033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner if (OldTI->hasName()) 44435033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner NewInst->setName(OldTI->getName()+NameSuffix); 44535033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner NewBB->getInstList().push_back(NewInst); 44629d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel VMap[OldTI] = NewInst; // Add instruction map to value. 44735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner 44835033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // Recursively clone any reachable successor blocks. 44935033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner const TerminatorInst *TI = BB->getTerminator(); 45035033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 45167ef241f45331d1df572ab95f5f19475d8e48a9eChris Lattner ToClone.push_back(TI->getSuccessor(i)); 45235033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 45335033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner 45483f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner if (CodeInfo) { 45583f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner CodeInfo->ContainsCalls |= hasCalls; 45683f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas; 45783f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 45883f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner BB != &BB->getParent()->front(); 45983f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner } 46083f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner} 46183f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner 4624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// This works like CloneAndPruneFunctionInto, except that it does not clone the 4634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// entire function. Instead it starts at an instruction provided by the caller 4644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// and copies (and prunes) only the code reachable from that instruction. 465ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesvoid llvm::CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc, 466ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const Instruction *StartingInst, 467774cca70b10bc679daff8203d639d9004a2eb194Devang Patel ValueToValueMapTy &VMap, 4686cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman bool ModuleLevelChanges, 469ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallVectorImpl<ReturnInst *> &Returns, 47083f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner const char *NameSuffix, 4711dfdf8255e803d6376f5fe94a113f892e796ae6cChris Lattner ClonedCodeInfo *CodeInfo, 472ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines CloningDirector *Director) { 47383f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner assert(NameSuffix && "NameSuffix cannot be null!"); 474ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 475ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ValueMapTypeRemapper *TypeMapper = nullptr; 476ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ValueMaterializer *Materializer = nullptr; 477ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 478ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Director) { 479ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TypeMapper = Director->getTypeRemapper(); 480ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Materializer = Director->getValueMaterializer(); 481ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 482ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 48383f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner#ifndef NDEBUG 484ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // If the cloning starts at the begining of the function, verify that 485ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // the function arguments are mapped. 486ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!StartingInst) 487ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Function::const_arg_iterator II = OldFunc->arg_begin(), 488ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines E = OldFunc->arg_end(); II != E; ++II) 489ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(VMap.count(II) && "No mapping from source argument specified!"); 49083f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner#endif 49128c3cff8250b3fe2adc6479306fe7dbdb48a1bdbDuncan Sands 4926cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges, 4934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar NameSuffix, CodeInfo, Director); 494ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const BasicBlock *StartingBB; 495ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (StartingInst) 496ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines StartingBB = StartingInst->getParent(); 497ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines else { 498ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines StartingBB = &OldFunc->getEntryBlock(); 499ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines StartingInst = StartingBB->begin(); 500ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 50183f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner 50283f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // Clone the entry block, and anything recursively reachable from it. 50367ef241f45331d1df572ab95f5f19475d8e48a9eChris Lattner std::vector<const BasicBlock*> CloneWorklist; 504ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PFC.CloneBlock(StartingBB, StartingInst, CloneWorklist); 50567ef241f45331d1df572ab95f5f19475d8e48a9eChris Lattner while (!CloneWorklist.empty()) { 50667ef241f45331d1df572ab95f5f19475d8e48a9eChris Lattner const BasicBlock *BB = CloneWorklist.back(); 50767ef241f45331d1df572ab95f5f19475d8e48a9eChris Lattner CloneWorklist.pop_back(); 508ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PFC.CloneBlock(BB, BB->begin(), CloneWorklist); 50967ef241f45331d1df572ab95f5f19475d8e48a9eChris Lattner } 51083f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner 51183f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // Loop over all of the basic blocks in the old function. If the block was 51283f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // reachable, we have cloned it and the old block is now in the value map: 51383f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // insert it into the new function in the right order. If not, ignore it. 51483f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // 51535033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // Defer PHI resolution until rest of function is resolved. 516ec1bea0d94372985a0a5eb283e644c6d0dd345dcChris Lattner SmallVector<const PHINode*, 16> PHIToResolve; 51783f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end(); 51883f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner BI != BE; ++BI) { 5196688c4a742b3d4ad511e35b463c2fe0f8abc04abRafael Espindola Value *V = VMap[BI]; 5206688c4a742b3d4ad511e35b463c2fe0f8abc04abRafael Espindola BasicBlock *NewBB = cast_or_null<BasicBlock>(V); 521dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!NewBB) continue; // Dead block. 52235033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner 52383f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // Add the new block to the new function. 52483f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner NewFunc->getBasicBlockList().push_back(NewBB); 52553bb5c95afe4ff2627cac513221af2e4e7c5d2e3Devang Patel 52683f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // Handle PHI nodes specially, as we have to remove references to dead 52783f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner // blocks. 5284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (BasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) { 5294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // PHI nodes may have been remapped to non-PHI nodes by the caller or 5304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // during the cloning process. 5314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (const PHINode *PN = dyn_cast<PHINode>(I)) { 5324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (isa<PHINode>(VMap[PN])) 5334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar PHIToResolve.push_back(PN); 5344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else 5354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar break; 5364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } else { 537d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth break; 5384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 5394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 540d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth 541d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth // Finally, remap the terminator instructions, as those can't be remapped 542d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth // until all BBs are mapped. 543d54f9a4c3bcdb247ea4aa311251c19242b03be63Chandler Carruth RemapInstruction(NewBB->getTerminator(), VMap, 544ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges, 545ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TypeMapper, Materializer); 54683f03bfc3f60a05b9ca5807f837c09798632095eChris Lattner } 54735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner 54835033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // Defer PHI resolution until rest of function is resolved, PHI resolution 54935033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // requires the CFG to be up-to-date. 55035033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) { 55135033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner const PHINode *OPN = PHIToResolve[phino]; 55235033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner unsigned NumPreds = OPN->getNumIncomingValues(); 55335033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner const BasicBlock *OldBB = OPN->getParent(); 55429d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel BasicBlock *NewBB = cast<BasicBlock>(VMap[OldBB]); 55535033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner 55635033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // Map operands for blocks that are live and remove operands for blocks 55735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // that are dead. 55835033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner for (; phino != PHIToResolve.size() && 55935033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner PHIToResolve[phino]->getParent() == OldBB; ++phino) { 56035033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner OPN = PHIToResolve[phino]; 56129d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel PHINode *PN = cast<PHINode>(VMap[OPN]); 56235033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) { 5636688c4a742b3d4ad511e35b463c2fe0f8abc04abRafael Espindola Value *V = VMap[PN->getIncomingBlock(pred)]; 564b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(V)) { 5650a205a459884ec745df1c529396dd921f029dafdOwen Anderson Value *InVal = MapValue(PN->getIncomingValue(pred), 566b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner VMap, 567b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges); 56835033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner assert(InVal && "Unknown input value?"); 56935033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner PN->setIncomingValue(pred, InVal); 57035033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner PN->setIncomingBlock(pred, MappedBlock); 57135033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } else { 57235033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner PN->removeIncomingValue(pred, false); 57335033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner --pred, --e; // Revisit the next entry. 57435033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 57535033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 57635033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 57735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner 57835033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // The loop above has removed PHI entries for those blocks that are dead 57935033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // and has updated others. However, if a block is live (i.e. copied over) 58035033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // but its terminator has been changed to not go to this block, then our 58135033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // phi nodes will have invalid entries. Update the PHI nodes in this 58235033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // case. 58335033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner PHINode *PN = cast<PHINode>(NewBB->begin()); 58435033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB)); 58535033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner if (NumPreds != PN->getNumIncomingValues()) { 58635033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner assert(NumPreds < PN->getNumIncomingValues()); 58735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // Count how many times each predecessor comes to this block. 58835033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner std::map<BasicBlock*, unsigned> PredCount; 58935033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); 59035033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner PI != E; ++PI) 59135033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner --PredCount[*PI]; 59235033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner 59335033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // Figure out how many entries to remove from each PHI. 59435033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 59535033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner ++PredCount[PN->getIncomingBlock(i)]; 59635033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner 59735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // At this point, the excess predecessor entries are positive in the 59835033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // map. Loop over all of the PHIs and remove excess predecessor 59935033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // entries. 60035033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner BasicBlock::iterator I = NewBB->begin(); 60135033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner for (; (PN = dyn_cast<PHINode>(I)); ++I) { 60235033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner for (std::map<BasicBlock*, unsigned>::iterator PCI =PredCount.begin(), 60335033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner E = PredCount.end(); PCI != E; ++PCI) { 60435033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner BasicBlock *Pred = PCI->first; 60535033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner for (unsigned NumToRemove = PCI->second; NumToRemove; --NumToRemove) 60635033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner PN->removeIncomingValue(Pred, false); 60735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 60835033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 60935033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 61035033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner 61135033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // If the loops above have made these phi nodes have 0 or 1 operand, 61235033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // replace them with undef or the input value. We must do this for 61335033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner // correctness, because 0-operand phis are not valid. 61435033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner PN = cast<PHINode>(NewBB->begin()); 61535033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner if (PN->getNumIncomingValues() == 0) { 61635033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner BasicBlock::iterator I = NewBB->begin(); 61735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner BasicBlock::const_iterator OldI = OldBB->begin(); 61835033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner while ((PN = dyn_cast<PHINode>(I++))) { 6199e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Value *NV = UndefValue::get(PN->getType()); 62035033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner PN->replaceAllUsesWith(NV); 62129d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel assert(VMap[OldI] == PN && "VMap mismatch"); 62229d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel VMap[OldI] = NV; 62335033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner PN->eraseFromParent(); 62435033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner ++OldI; 62535033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 62635033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 62735033efd08420a8a2aad14083a0178e2edebdfd6Chris Lattner } 628f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth 629f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth // Make a second pass over the PHINodes now that all of them have been 630f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth // remapped into the new function, simplifying the PHINode and performing any 631f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth // recursive simplifications exposed. This will transparently update the 632afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth // WeakVH in the VMap. Notably, we rely on that so that if we coalesce 633f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth // two PHINodes, the iteration over the old PHIs remains valid, and the 634f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth // mapping will just map us to the new node (which may not even be a PHI 635f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth // node). 636f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx) 637f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth if (PHINode *PN = dyn_cast<PHINode>(VMap[PHIToResolve[Idx]])) 6384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar recursivelySimplifyInstruction(PN); 639f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth 640a4646b61e48453e343730103d3ad689be493a371Chris Lattner // Now that the inlined function body has been fully constructed, go through 6414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // and zap unconditional fall-through branches. This happens all the time when 642a4646b61e48453e343730103d3ad689be493a371Chris Lattner // specializing code: code specialization turns conditional branches into 643a4646b61e48453e343730103d3ad689be493a371Chris Lattner // uncond branches, and this code folds them. 644ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Function::iterator Begin = cast<BasicBlock>(VMap[StartingBB]); 645afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth Function::iterator I = Begin; 646a4646b61e48453e343730103d3ad689be493a371Chris Lattner while (I != NewFunc->end()) { 647afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth // Check if this block has become dead during inlining or other 648afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth // simplifications. Note that the first block will appear dead, as it has 649afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth // not yet been wired up properly. 650afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth if (I != Begin && (pred_begin(I) == pred_end(I) || 651afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth I->getSinglePredecessor() == I)) { 652afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth BasicBlock *DeadBB = I++; 653afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth DeleteDeadBlock(DeadBB); 654afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth continue; 655afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth } 656afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth 657afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth // We need to simplify conditional branches and switches with a constant 658afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth // operand. We try to prune these out when cloning, but if the 659afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth // simplification required looking through PHI nodes, those are only 660afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth // available after forming the full basic block. That may leave some here, 661afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth // and we still want to prune the dead code as early as possible. 662afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth ConstantFoldTerminator(I); 663afff33001a4fd3049d97cb40eea459d5c87ae5ccChandler Carruth 664a4646b61e48453e343730103d3ad689be493a371Chris Lattner BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator()); 665a4646b61e48453e343730103d3ad689be493a371Chris Lattner if (!BI || BI->isConditional()) { ++I; continue; } 666a4646b61e48453e343730103d3ad689be493a371Chris Lattner 667a4646b61e48453e343730103d3ad689be493a371Chris Lattner BasicBlock *Dest = BI->getSuccessor(0); 668f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth if (!Dest->getSinglePredecessor()) { 6698e8eda78cc5f06e4b19f2c374189a25017085286Chris Lattner ++I; continue; 6708e8eda78cc5f06e4b19f2c374189a25017085286Chris Lattner } 671f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth 672f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth // We shouldn't be able to get single-entry PHI nodes here, as instsimplify 673f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth // above should have zapped all of them.. 674f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth assert(!isa<PHINode>(Dest->begin())); 675f8c8a9cbb40972b07432d6b25d1a351556485b1eChandler Carruth 676a4646b61e48453e343730103d3ad689be493a371Chris Lattner // We know all single-entry PHI nodes in the inlined function have been 677a4646b61e48453e343730103d3ad689be493a371Chris Lattner // removed, so we just need to splice the blocks. 678a4646b61e48453e343730103d3ad689be493a371Chris Lattner BI->eraseFromParent(); 679a4646b61e48453e343730103d3ad689be493a371Chris Lattner 680e59fbc04ad343435705c28b3cf7038d65fe4af0aEric Christopher // Make all PHI nodes that referred to Dest now refer to I as their source. 681e59fbc04ad343435705c28b3cf7038d65fe4af0aEric Christopher Dest->replaceAllUsesWith(I); 682e59fbc04ad343435705c28b3cf7038d65fe4af0aEric Christopher 68395c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // Move all the instructions in the succ to the pred. 68495c3e48f9557adb6064d580684bb14cacec2f826Jay Foad I->getInstList().splice(I->end(), Dest->getInstList()); 68595c3e48f9557adb6064d580684bb14cacec2f826Jay Foad 686a4646b61e48453e343730103d3ad689be493a371Chris Lattner // Remove the dest block. 687a4646b61e48453e343730103d3ad689be493a371Chris Lattner Dest->eraseFromParent(); 688a4646b61e48453e343730103d3ad689be493a371Chris Lattner 689a4646b61e48453e343730103d3ad689be493a371Chris Lattner // Do not increment I, iteratively merge all things this block branches to. 690a4646b61e48453e343730103d3ad689be493a371Chris Lattner } 6919ceebb7e92e980340d199b550e3a2110c80ea871Chandler Carruth 6924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Make a final pass over the basic blocks from the old function to gather 6939ceebb7e92e980340d199b550e3a2110c80ea871Chandler Carruth // any return instructions which survived folding. We have to do this here 6949ceebb7e92e980340d199b550e3a2110c80ea871Chandler Carruth // because we can iteratively remove and merge returns above. 695ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Function::iterator I = cast<BasicBlock>(VMap[StartingBB]), 6969ceebb7e92e980340d199b550e3a2110c80ea871Chandler Carruth E = NewFunc->end(); 6979ceebb7e92e980340d199b550e3a2110c80ea871Chandler Carruth I != E; ++I) 6989ceebb7e92e980340d199b550e3a2110c80ea871Chandler Carruth if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator())) 6999ceebb7e92e980340d199b550e3a2110c80ea871Chandler Carruth Returns.push_back(RI); 700a4646b61e48453e343730103d3ad689be493a371Chris Lattner} 701ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 702ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 7034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// This works exactly like CloneFunctionInto, 704ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// except that it does some simple constant prop and DCE on the fly. The 705ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// effect of this is to copy significantly less code in cases where (for 706ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// example) a function call with constant arguments is inlined, and those 707ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// constant arguments cause a significant amount of code in the callee to be 708ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// dead. Since this doesn't produce an exact copy of the input, it can't be 709ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// used for things like CloneFunction or CloneModule. 710ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesvoid llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, 711ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ValueToValueMapTy &VMap, 712ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool ModuleLevelChanges, 713ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallVectorImpl<ReturnInst*> &Returns, 714ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const char *NameSuffix, 715ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ClonedCodeInfo *CodeInfo, 716ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Instruction *TheCall) { 7174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar CloneAndPruneIntoFromInst(NewFunc, OldFunc, OldFunc->front().begin(), VMap, 7184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ModuleLevelChanges, Returns, NameSuffix, CodeInfo, 7194c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar nullptr); 720ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 721