184bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner//===- Cloning.h - Clone various parts of LLVM programs ---------*- C++ -*-===// 234695381d626485a560594f162701088079589dfMisha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 734695381d626485a560594f162701088079589dfMisha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 984bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner// 1084bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner// This file defines various functions that are used to clone chunks of LLVM 1184bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner// code for various purposes. This varies from copying whole modules into new 1284bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner// modules, to cloning functions with different arguments, to inlining 1384bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner// functions, to copying basic blocks to support loop unrolling or superblock 1484bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner// formation, etc. 1584bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner// 1684bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner//===----------------------------------------------------------------------===// 1784bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner 18a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner#ifndef LLVM_TRANSFORMS_UTILS_CLONING_H 19a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner#define LLVM_TRANSFORMS_UTILS_CLONING_H 2084bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner 21e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel#include "llvm/ADT/ValueMap.h" 2260915146f4d35e12f10dcdaa155596fac79184daChris Lattner#include "llvm/ADT/SmallVector.h" 235deb57c68552a85094b786dfdbd16e3744716733Benjamin Kramer#include "llvm/ADT/Twine.h" 24076863225ce070345ff7048f48b3550e00598a10Chris Lattner#include "llvm/Support/ValueHandle.h" 251ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola#include "llvm/Transforms/Utils/ValueMapper.h" 26d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 27d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 28d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2984bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnerclass Module; 3084bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnerclass Function; 3153bb5c95afe4ff2627cac513221af2e4e7c5d2e3Devang Patelclass Instruction; 324bc2a0b420c728e77a852bad9721e4edfd4b3f79Devang Patelclass Pass; 334bc2a0b420c728e77a852bad9721e4edfd4b3f79Devang Patelclass LPPassManager; 3484bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnerclass BasicBlock; 3584bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnerclass Value; 3684bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnerclass CallInst; 379d3a1b2d972baf72b7da371a1ae72126bc5c6c04Chris Lattnerclass InvokeInst; 381c9985067bfedc219c1a6128bfc703cf3894b866Chris Lattnerclass ReturnInst; 399d3a1b2d972baf72b7da371a1ae72126bc5c6c04Chris Lattnerclass CallSite; 402b6d2eb2d0e44eb8d897fce107961767b9676a79Alkis Evlogimenosclass Trace; 414c2881ecb97ca9306396b74a61a6ce05f2b9a4f4Chris Lattnerclass CallGraph; 421dfdf8255e803d6376f5fe94a113f892e796ae6cChris Lattnerclass TargetData; 43c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohmanclass Loop; 443dab223dc9a398b30484fca23d912433ea0033f3Chris Lattnerclass LoopInfo; 458f2718fbef6177966ff807af0732eb2431bd9a5fChris Lattnerclass AllocaInst; 4684bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner 47d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// CloneModule - Return an exact copy of the specified module 48d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// 49d4fd3978056928b156bc51bff7cd4eb825bffb1aChris LattnerModule *CloneModule(const Module *M); 501ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael EspindolaModule *CloneModule(const Module *M, ValueToValueMapTy &VMap); 51d18015599cbe09dd327b5f73501581a865bf27daChris Lattner 52a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// ClonedCodeInfo - This struct can be used to capture information about code 53a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// being cloned, while it is being cloned. 54a4c29d20376f4736325a493cf39cda36bed62318Chris Lattnerstruct ClonedCodeInfo { 55a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner /// ContainsCalls - This is set to true if the cloned code contains a normal 56a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner /// call instruction. 57a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner bool ContainsCalls; 58a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner 59a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner /// ContainsDynamicAllocas - This is set to true if the cloned code contains 60a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner /// a 'dynamic' alloca. Dynamic allocas are allocas that are either not in 61a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner /// the entry block or they are in the entry block but are not a constant 62a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner /// size. 63a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner bool ContainsDynamicAllocas; 64a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner 658833ef03b9ceaa52063116819fff8b3d16fd8933Bill Wendling ClonedCodeInfo() : ContainsCalls(false), ContainsDynamicAllocas(false) {} 66a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner}; 67a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner 68a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner 69a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// CloneBasicBlock - Return a copy of the specified basic block, but without 70a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// embedding the block into a particular function. The block returned is an 71a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// exact copy of the specified basic block, without any remapping having been 72a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// performed. Because of this, this is only suitable for applications where 73a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// the basic block will be inserted into the same function that it was cloned 74a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// from (loop unrolling would use this, for example). 75a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// 76a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// Also, note that this function makes a direct copy of the basic block, and 77a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// can thus produce illegal LLVM code. In particular, it will copy any PHI 78a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// nodes from the original block, even though there are no predecessors for the 79a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// newly cloned block (thus, phi nodes will have to be updated). Also, this 80a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// block will branch to the old successors of the original block: these 81a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// successors will have to have any PHI nodes updated to account for the new 82a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// incoming edges. 83a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// 84a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// The correlation between instructions in the source and result basic blocks 8529d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel/// is recorded in the VMap map. 86a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// 87a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// If you have a particular suffix you'd like to use to add to any cloned 88cb2b3e5005c09f24afeb0dab49ac8bc1967e491aChris Lattner/// names, specify it as the optional third parameter. 89cb2b3e5005c09f24afeb0dab49ac8bc1967e491aChris Lattner/// 90cb2b3e5005c09f24afeb0dab49ac8bc1967e491aChris Lattner/// If you would like the basic block to be auto-inserted into the end of a 91cb2b3e5005c09f24afeb0dab49ac8bc1967e491aChris Lattner/// function, you can specify it as the optional fourth parameter. 92a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// 93a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// If you would like to collect additional information about the cloned 94a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// function, you can specify a ClonedCodeInfo object with the optional fifth 95a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// parameter. 96a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// 97a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris LattnerBasicBlock *CloneBasicBlock(const BasicBlock *BB, 981ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy &VMap, 995deb57c68552a85094b786dfdbd16e3744716733Benjamin Kramer const Twine &NameSuffix = "", Function *F = 0, 100a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner ClonedCodeInfo *CodeInfo = 0); 101a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner 102d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// CloneFunction - Return a copy of the specified function, but without 103d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// embedding the function into another module. Also, any references specified 10429d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel/// in the VMap are changed to refer to their mapped value instead of the 10529d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel/// original one. If any of the arguments to the function are in the VMap, 10629d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel/// the arguments are deleted from the resultant function. The VMap is 107d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// updated to include mappings from all of the instructions and basicblocks in 108a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// the function from their old to new values. The final argument captures 109a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// information about the cloned code if non-null. 110d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// 1116cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman/// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue 1126cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman/// mappings. 1136cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman/// 114d18015599cbe09dd327b5f73501581a865bf27daChris LattnerFunction *CloneFunction(const Function *F, 1151ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy &VMap, 1166cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman bool ModuleLevelChanges, 117a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner ClonedCodeInfo *CodeInfo = 0); 118d18015599cbe09dd327b5f73501581a865bf27daChris Lattner 11929d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel/// CloneFunction - Version of the function that doesn't need the VMap. 120d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// 121a4c29d20376f4736325a493cf39cda36bed62318Chris Lattnerinline Function *CloneFunction(const Function *F, ClonedCodeInfo *CodeInfo = 0){ 1221ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy VMap; 12329d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel return CloneFunction(F, VMap, CodeInfo); 124d18015599cbe09dd327b5f73501581a865bf27daChris Lattner} 125d18015599cbe09dd327b5f73501581a865bf27daChris Lattner 126aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// Clone OldFunc into NewFunc, transforming the old arguments into references 1276cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman/// to VMap values. Note that if NewFunc already has basic blocks, the ones 128aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// cloned into it will be added to the end of the function. This function 129d24397a9319a41e80169f572ad274a711f41d64eMon P Wang/// fills in a list of return instructions, and can optionally remap types 130d24397a9319a41e80169f572ad274a711f41d64eMon P Wang/// and/or append the specified suffix to all values cloned. 131aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// 1326cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman/// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue 1336cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman/// mappings. 1346cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman/// 13584bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnervoid CloneFunctionInto(Function *NewFunc, const Function *OldFunc, 1361ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy &VMap, 1376cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman bool ModuleLevelChanges, 138ec1bea0d94372985a0a5eb283e644c6d0dd345dcChris Lattner SmallVectorImpl<ReturnInst*> &Returns, 139a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner const char *NameSuffix = "", 140d24397a9319a41e80169f572ad274a711f41d64eMon P Wang ClonedCodeInfo *CodeInfo = 0, 141d24397a9319a41e80169f572ad274a711f41d64eMon P Wang ValueMapTypeRemapper *TypeMapper = 0); 14284bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner 143f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto, 144f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// except that it does some simple constant prop and DCE on the fly. The 145f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// effect of this is to copy significantly less code in cases where (for 146f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// example) a function call with constant arguments is inlined, and those 147f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// constant arguments cause a significant amount of code in the callee to be 148f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// dead. Since this doesn't produce an exactly copy of the input, it can't be 149f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// used for things like CloneFunction or CloneModule. 1506cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman/// 1516cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman/// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue 1526cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman/// mappings. 1536cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman/// 154f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattnervoid CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, 1551ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy &VMap, 1566cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman bool ModuleLevelChanges, 157ec1bea0d94372985a0a5eb283e644c6d0dd345dcChris Lattner SmallVectorImpl<ReturnInst*> &Returns, 158f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner const char *NameSuffix = "", 1591dfdf8255e803d6376f5fe94a113f892e796ae6cChris Lattner ClonedCodeInfo *CodeInfo = 0, 16053bb5c95afe4ff2627cac513221af2e4e7c5d2e3Devang Patel const TargetData *TD = 0, 16153bb5c95afe4ff2627cac513221af2e4e7c5d2e3Devang Patel Instruction *TheCall = 0); 162f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner 16360915146f4d35e12f10dcdaa155596fac79184daChris Lattner 16460915146f4d35e12f10dcdaa155596fac79184daChris Lattner/// InlineFunctionInfo - This class captures the data input to the 16560915146f4d35e12f10dcdaa155596fac79184daChris Lattner/// InlineFunction call, and records the auxiliary results produced by it. 16660915146f4d35e12f10dcdaa155596fac79184daChris Lattnerclass InlineFunctionInfo { 16760915146f4d35e12f10dcdaa155596fac79184daChris Lattnerpublic: 16860915146f4d35e12f10dcdaa155596fac79184daChris Lattner explicit InlineFunctionInfo(CallGraph *cg = 0, const TargetData *td = 0) 16960915146f4d35e12f10dcdaa155596fac79184daChris Lattner : CG(cg), TD(td) {} 17060915146f4d35e12f10dcdaa155596fac79184daChris Lattner 17160915146f4d35e12f10dcdaa155596fac79184daChris Lattner /// CG - If non-null, InlineFunction will update the callgraph to reflect the 17260915146f4d35e12f10dcdaa155596fac79184daChris Lattner /// changes it makes. 17360915146f4d35e12f10dcdaa155596fac79184daChris Lattner CallGraph *CG; 17460915146f4d35e12f10dcdaa155596fac79184daChris Lattner const TargetData *TD; 17560915146f4d35e12f10dcdaa155596fac79184daChris Lattner 17660915146f4d35e12f10dcdaa155596fac79184daChris Lattner /// StaticAllocas - InlineFunction fills this in with all static allocas that 17760915146f4d35e12f10dcdaa155596fac79184daChris Lattner /// get copied into the caller. 17860915146f4d35e12f10dcdaa155596fac79184daChris Lattner SmallVector<AllocaInst*, 4> StaticAllocas; 179fe9af3b1f7e5d68ecc330bdf4f047d76838f8cc3Chris Lattner 1800ca2f28458ae9122f413a4092ddcee33a9dd21c6Chris Lattner /// InlinedCalls - InlineFunction fills this in with callsites that were 1810ca2f28458ae9122f413a4092ddcee33a9dd21c6Chris Lattner /// inlined from the callee. This is only filled in if CG is non-null. 1820ca2f28458ae9122f413a4092ddcee33a9dd21c6Chris Lattner SmallVector<WeakVH, 8> InlinedCalls; 18360915146f4d35e12f10dcdaa155596fac79184daChris Lattner 18460915146f4d35e12f10dcdaa155596fac79184daChris Lattner void reset() { 18560915146f4d35e12f10dcdaa155596fac79184daChris Lattner StaticAllocas.clear(); 1860ca2f28458ae9122f413a4092ddcee33a9dd21c6Chris Lattner InlinedCalls.clear(); 18760915146f4d35e12f10dcdaa155596fac79184daChris Lattner } 18860915146f4d35e12f10dcdaa155596fac79184daChris Lattner}; 18960915146f4d35e12f10dcdaa155596fac79184daChris Lattner 190aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// InlineFunction - This function inlines the called function into the basic 191a04e51f4c0dd981af9b8f6e8b219df495cccaa45Chris Lattner/// block of the caller. This returns false if it is not possible to inline 192a04e51f4c0dd981af9b8f6e8b219df495cccaa45Chris Lattner/// this call. The program is still in a well defined state if this occurs 193a04e51f4c0dd981af9b8f6e8b219df495cccaa45Chris Lattner/// though. 194aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// 19534695381d626485a560594f162701088079589dfMisha Brukman/// Note that this only does one level of inlining. For example, if the 196aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now 1977a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// exists in the instruction stream. Similarly this will inline a recursive 198aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// function by one level. 199aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// 200fa086f1f00a8b75ab2e2208bd7a028e62f9854dbChad Rosierbool InlineFunction(CallInst *C, InlineFunctionInfo &IFI, bool InsertLifetime = true); 201fa086f1f00a8b75ab2e2208bd7a028e62f9854dbChad Rosierbool InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI, bool InsertLifetime = true); 202fa086f1f00a8b75ab2e2208bd7a028e62f9854dbChad Rosierbool InlineFunction(CallSite CS, InlineFunctionInfo &IFI, bool InsertLifetime = true); 2032c49fc023ee0885c8c577829cd40c00ef48581fcTanya Lattner 204d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 205d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 20684bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner#endif 207