Cloning.h revision c8d76d5afb023a1c6b439941be3b62789fcc0ed3
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 2184bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner#include <vector> 225e665f559419c7f58a4fd9360cd488f065505c44Chris Lattner#include "llvm/ADT/DenseMap.h" 23d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 24d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 25d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2684bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnerclass Module; 2784bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnerclass Function; 284bc2a0b420c728e77a852bad9721e4edfd4b3f79Devang Patelclass Pass; 294bc2a0b420c728e77a852bad9721e4edfd4b3f79Devang Patelclass LPPassManager; 3084bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnerclass BasicBlock; 3184bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnerclass Value; 3284bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnerclass CallInst; 339d3a1b2d972baf72b7da371a1ae72126bc5c6c04Chris Lattnerclass InvokeInst; 341c9985067bfedc219c1a6128bfc703cf3894b866Chris Lattnerclass ReturnInst; 359d3a1b2d972baf72b7da371a1ae72126bc5c6c04Chris Lattnerclass CallSite; 362b6d2eb2d0e44eb8d897fce107961767b9676a79Alkis Evlogimenosclass Trace; 374c2881ecb97ca9306396b74a61a6ce05f2b9a4f4Chris Lattnerclass CallGraph; 381dfdf8255e803d6376f5fe94a113f892e796ae6cChris Lattnerclass TargetData; 39c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohmanclass Loop; 403dab223dc9a398b30484fca23d912433ea0033f3Chris Lattnerclass LoopInfo; 418b477ed579794ba6d76915d56b3f448a7dd20120Owen Andersonclass LLVMContext; 4284bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner 43d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// CloneModule - Return an exact copy of the specified module 44d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// 45d4fd3978056928b156bc51bff7cd4eb825bffb1aChris LattnerModule *CloneModule(const Module *M); 465e665f559419c7f58a4fd9360cd488f065505c44Chris LattnerModule *CloneModule(const Module *M, DenseMap<const Value*, Value*> &ValueMap); 47d18015599cbe09dd327b5f73501581a865bf27daChris Lattner 48a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// ClonedCodeInfo - This struct can be used to capture information about code 49a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// being cloned, while it is being cloned. 50a4c29d20376f4736325a493cf39cda36bed62318Chris Lattnerstruct ClonedCodeInfo { 51a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner /// ContainsCalls - This is set to true if the cloned code contains a normal 52a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner /// call instruction. 53a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner bool ContainsCalls; 54a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner 55a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner /// ContainsUnwinds - This is set to true if the cloned code contains an 56a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner /// unwind instruction. 57a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner bool ContainsUnwinds; 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 65a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner ClonedCodeInfo() { 66a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner ContainsCalls = false; 67a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner ContainsUnwinds = false; 68a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner ContainsDynamicAllocas = false; 69a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner } 70a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner}; 71a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner 72a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner 73a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// CloneBasicBlock - Return a copy of the specified basic block, but without 74a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// embedding the block into a particular function. The block returned is an 75a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// exact copy of the specified basic block, without any remapping having been 76a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// performed. Because of this, this is only suitable for applications where 77a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// the basic block will be inserted into the same function that it was cloned 78a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// from (loop unrolling would use this, for example). 79a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// 80a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// Also, note that this function makes a direct copy of the basic block, and 81a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// can thus produce illegal LLVM code. In particular, it will copy any PHI 82a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// nodes from the original block, even though there are no predecessors for the 83a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// newly cloned block (thus, phi nodes will have to be updated). Also, this 84a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// block will branch to the old successors of the original block: these 85a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// successors will have to have any PHI nodes updated to account for the new 86a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// incoming edges. 87a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// 88a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// The correlation between instructions in the source and result basic blocks 89a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// is recorded in the ValueMap map. 90a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// 91a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// If you have a particular suffix you'd like to use to add to any cloned 92cb2b3e5005c09f24afeb0dab49ac8bc1967e491aChris Lattner/// names, specify it as the optional third parameter. 93cb2b3e5005c09f24afeb0dab49ac8bc1967e491aChris Lattner/// 94cb2b3e5005c09f24afeb0dab49ac8bc1967e491aChris Lattner/// If you would like the basic block to be auto-inserted into the end of a 95cb2b3e5005c09f24afeb0dab49ac8bc1967e491aChris Lattner/// function, you can specify it as the optional fourth parameter. 96a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner/// 97a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// If you would like to collect additional information about the cloned 98a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// function, you can specify a ClonedCodeInfo object with the optional fifth 99a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// parameter. 100a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// 101a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris LattnerBasicBlock *CloneBasicBlock(const BasicBlock *BB, 1025e665f559419c7f58a4fd9360cd488f065505c44Chris Lattner DenseMap<const Value*, Value*> &ValueMap, 103a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner const char *NameSuffix = "", Function *F = 0, 104a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner ClonedCodeInfo *CodeInfo = 0); 105a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner 106a107e5f11cf7aa362d2fdd5cebc7e64bb09ed22dChris Lattner 1074bc2a0b420c728e77a852bad9721e4edfd4b3f79Devang Patel/// CloneLoop - Clone Loop. Clone dominator info for loop insiders. Populate ValueMap 1084bc2a0b420c728e77a852bad9721e4edfd4b3f79Devang Patel/// using old blocks to new blocks mapping. 1094bc2a0b420c728e77a852bad9721e4edfd4b3f79Devang PatelLoop *CloneLoop(Loop *L, LPPassManager *LPM, LoopInfo *LI, 1104bc2a0b420c728e77a852bad9721e4edfd4b3f79Devang Patel DenseMap<const Value *, Value *> &ValueMap, Pass *P); 1114bc2a0b420c728e77a852bad9721e4edfd4b3f79Devang Patel 112d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// CloneFunction - Return a copy of the specified function, but without 113d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// embedding the function into another module. Also, any references specified 114d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// in the ValueMap are changed to refer to their mapped value instead of the 115d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// original one. If any of the arguments to the function are in the ValueMap, 116d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// the arguments are deleted from the resultant function. The ValueMap is 117d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// updated to include mappings from all of the instructions and basicblocks in 118a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// the function from their old to new values. The final argument captures 119a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner/// information about the cloned code if non-null. 120d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// 121d18015599cbe09dd327b5f73501581a865bf27daChris LattnerFunction *CloneFunction(const Function *F, 1225e665f559419c7f58a4fd9360cd488f065505c44Chris Lattner DenseMap<const Value*, Value*> &ValueMap, 123a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner ClonedCodeInfo *CodeInfo = 0); 124d18015599cbe09dd327b5f73501581a865bf27daChris Lattner 125d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// CloneFunction - Version of the function that doesn't need the ValueMap. 126d18015599cbe09dd327b5f73501581a865bf27daChris Lattner/// 127a4c29d20376f4736325a493cf39cda36bed62318Chris Lattnerinline Function *CloneFunction(const Function *F, ClonedCodeInfo *CodeInfo = 0){ 1285e665f559419c7f58a4fd9360cd488f065505c44Chris Lattner DenseMap<const Value*, Value*> ValueMap; 129a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner return CloneFunction(F, ValueMap, CodeInfo); 130d18015599cbe09dd327b5f73501581a865bf27daChris Lattner} 131d18015599cbe09dd327b5f73501581a865bf27daChris Lattner 132aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// Clone OldFunc into NewFunc, transforming the old arguments into references 133aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// to ArgMap values. Note that if NewFunc already has basic blocks, the ones 134aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// cloned into it will be added to the end of the function. This function 135aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// fills in a list of return instructions, and can optionally append the 136aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// specified suffix to all values cloned. 137aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// 13884bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattnervoid CloneFunctionInto(Function *NewFunc, const Function *OldFunc, 1395e665f559419c7f58a4fd9360cd488f065505c44Chris Lattner DenseMap<const Value*, Value*> &ValueMap, 1401c9985067bfedc219c1a6128bfc703cf3894b866Chris Lattner std::vector<ReturnInst*> &Returns, 141a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner const char *NameSuffix = "", 142a4c29d20376f4736325a493cf39cda36bed62318Chris Lattner ClonedCodeInfo *CodeInfo = 0); 14384bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner 144f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto, 145f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// except that it does some simple constant prop and DCE on the fly. The 146f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// effect of this is to copy significantly less code in cases where (for 147f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// example) a function call with constant arguments is inlined, and those 148f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// constant arguments cause a significant amount of code in the callee to be 149f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// dead. Since this doesn't produce an exactly copy of the input, it can't be 150f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner/// used for things like CloneFunction or CloneModule. 151f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattnervoid CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, 1525e665f559419c7f58a4fd9360cd488f065505c44Chris Lattner DenseMap<const Value*, Value*> &ValueMap, 153f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner std::vector<ReturnInst*> &Returns, 154f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner const char *NameSuffix = "", 1551dfdf8255e803d6376f5fe94a113f892e796ae6cChris Lattner ClonedCodeInfo *CodeInfo = 0, 1561dfdf8255e803d6376f5fe94a113f892e796ae6cChris Lattner const TargetData *TD = 0); 157f72716d81f64664e6897d9f2e8a7d071bad1de68Chris Lattner 15884bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner 1592b6d2eb2d0e44eb8d897fce107961767b9676a79Alkis Evlogimenos/// CloneTraceInto - Clone T into NewFunc. Original<->clone mapping is 1602b6d2eb2d0e44eb8d897fce107961767b9676a79Alkis Evlogimenos/// saved in ValueMap. 1612b6d2eb2d0e44eb8d897fce107961767b9676a79Alkis Evlogimenos/// 1622b6d2eb2d0e44eb8d897fce107961767b9676a79Alkis Evlogimenosvoid CloneTraceInto(Function *NewFunc, Trace &T, 1635e665f559419c7f58a4fd9360cd488f065505c44Chris Lattner DenseMap<const Value*, Value*> &ValueMap, 1642b6d2eb2d0e44eb8d897fce107961767b9676a79Alkis Evlogimenos const char *NameSuffix); 1652b6d2eb2d0e44eb8d897fce107961767b9676a79Alkis Evlogimenos 1664c2881ecb97ca9306396b74a61a6ce05f2b9a4f4Chris Lattner/// CloneTrace - Returns a copy of the specified trace. 1674c2881ecb97ca9306396b74a61a6ce05f2b9a4f4Chris Lattner/// It takes a vector of basic blocks clones the basic blocks, removes internal 1684c2881ecb97ca9306396b74a61a6ce05f2b9a4f4Chris Lattner/// phi nodes, adds it to the same function as the original (although there is 1694c2881ecb97ca9306396b74a61a6ce05f2b9a4f4Chris Lattner/// no jump to it) and returns the new vector of basic blocks. 1704c2881ecb97ca9306396b74a61a6ce05f2b9a4f4Chris Lattnerstd::vector<BasicBlock *> CloneTrace(const std::vector<BasicBlock*> &origTrace); 1714c2881ecb97ca9306396b74a61a6ce05f2b9a4f4Chris Lattner 172aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// InlineFunction - This function inlines the called function into the basic 173a04e51f4c0dd981af9b8f6e8b219df495cccaa45Chris Lattner/// block of the caller. This returns false if it is not possible to inline 174a04e51f4c0dd981af9b8f6e8b219df495cccaa45Chris Lattner/// this call. The program is still in a well defined state if this occurs 175a04e51f4c0dd981af9b8f6e8b219df495cccaa45Chris Lattner/// though. 176aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// 17734695381d626485a560594f162701088079589dfMisha Brukman/// Note that this only does one level of inlining. For example, if the 178aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now 179aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// exists in the instruction stream. Similiarly this will inline a recursive 180aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// function by one level. 181aa101c3147debcba3f0441c80b477782e456a03bChris Lattner/// 1824c2881ecb97ca9306396b74a61a6ce05f2b9a4f4Chris Lattner/// If a non-null callgraph pointer is provided, these functions update the 1834c2881ecb97ca9306396b74a61a6ce05f2b9a4f4Chris Lattner/// CallGraph to represent the program after inlining. 1844c2881ecb97ca9306396b74a61a6ce05f2b9a4f4Chris Lattner/// 1851dfdf8255e803d6376f5fe94a113f892e796ae6cChris Lattnerbool InlineFunction(CallInst *C, CallGraph *CG = 0, const TargetData *TD = 0); 1861dfdf8255e803d6376f5fe94a113f892e796ae6cChris Lattnerbool InlineFunction(InvokeInst *II, CallGraph *CG = 0, const TargetData *TD =0); 187652f7ea955bb433d6b7a4d33685dca9485fd7b8bEvan Chengbool InlineFunction(CallSite CS, CallGraph *CG = 0, const TargetData *TD = 0); 1882c49fc023ee0885c8c577829cd40c00ef48581fcTanya Lattner 189d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 190d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 19184bf9880eaf57f00cc01b4ade40179553ea6fd08Chris Lattner#endif 192