Line data Source code
1 : //===- Cloning.h - Clone various parts of LLVM programs ---------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file defines various functions that are used to clone chunks of LLVM
11 : // code for various purposes. This varies from copying whole modules into new
12 : // modules, to cloning functions with different arguments, to inlining
13 : // functions, to copying basic blocks to support loop unrolling or superblock
14 : // formation, etc.
15 : //
16 : //===----------------------------------------------------------------------===//
17 :
18 : #ifndef LLVM_TRANSFORMS_UTILS_CLONING_H
19 : #define LLVM_TRANSFORMS_UTILS_CLONING_H
20 :
21 : #include "llvm/ADT/SmallVector.h"
22 : #include "llvm/ADT/Twine.h"
23 : #include "llvm/Analysis/AliasAnalysis.h"
24 : #include "llvm/Analysis/AssumptionCache.h"
25 : #include "llvm/Analysis/InlineCost.h"
26 : #include "llvm/IR/CallSite.h"
27 : #include "llvm/IR/ValueHandle.h"
28 : #include "llvm/Transforms/Utils/ValueMapper.h"
29 : #include <functional>
30 : #include <memory>
31 : #include <vector>
32 :
33 : namespace llvm {
34 :
35 : class AllocaInst;
36 : class BasicBlock;
37 : class BlockFrequencyInfo;
38 : class CallInst;
39 : class CallGraph;
40 : class DebugInfoFinder;
41 : class DominatorTree;
42 : class Function;
43 : class Instruction;
44 : class InvokeInst;
45 : class Loop;
46 : class LoopInfo;
47 : class Module;
48 : class ProfileSummaryInfo;
49 : class ReturnInst;
50 :
51 : /// Return an exact copy of the specified module
52 : ///
53 : std::unique_ptr<Module> CloneModule(const Module &M);
54 : std::unique_ptr<Module> CloneModule(const Module &M, ValueToValueMapTy &VMap);
55 :
56 : /// Return a copy of the specified module. The ShouldCloneDefinition function
57 : /// controls whether a specific GlobalValue's definition is cloned. If the
58 : /// function returns false, the module copy will contain an external reference
59 : /// in place of the global definition.
60 : std::unique_ptr<Module>
61 : CloneModule(const Module &M, ValueToValueMapTy &VMap,
62 : function_ref<bool(const GlobalValue *)> ShouldCloneDefinition);
63 :
64 : /// ClonedCodeInfo - This struct can be used to capture information about code
65 : /// being cloned, while it is being cloned.
66 1399308 : struct ClonedCodeInfo {
67 : /// ContainsCalls - This is set to true if the cloned code contains a normal
68 : /// call instruction.
69 : bool ContainsCalls = false;
70 :
71 : /// ContainsDynamicAllocas - This is set to true if the cloned code contains
72 : /// a 'dynamic' alloca. Dynamic allocas are allocas that are either not in
73 : /// the entry block or they are in the entry block but are not a constant
74 : /// size.
75 : bool ContainsDynamicAllocas = false;
76 :
77 : /// All cloned call sites that have operand bundles attached are appended to
78 : /// this vector. This vector may contain nulls or undefs if some of the
79 : /// originally inserted callsites were DCE'ed after they were cloned.
80 : std::vector<WeakTrackingVH> OperandBundleCallSites;
81 :
82 1399308 : ClonedCodeInfo() = default;
83 : };
84 :
85 : /// CloneBasicBlock - Return a copy of the specified basic block, but without
86 : /// embedding the block into a particular function. The block returned is an
87 : /// exact copy of the specified basic block, without any remapping having been
88 : /// performed. Because of this, this is only suitable for applications where
89 : /// the basic block will be inserted into the same function that it was cloned
90 : /// from (loop unrolling would use this, for example).
91 : ///
92 : /// Also, note that this function makes a direct copy of the basic block, and
93 : /// can thus produce illegal LLVM code. In particular, it will copy any PHI
94 : /// nodes from the original block, even though there are no predecessors for the
95 : /// newly cloned block (thus, phi nodes will have to be updated). Also, this
96 : /// block will branch to the old successors of the original block: these
97 : /// successors will have to have any PHI nodes updated to account for the new
98 : /// incoming edges.
99 : ///
100 : /// The correlation between instructions in the source and result basic blocks
101 : /// is recorded in the VMap map.
102 : ///
103 : /// If you have a particular suffix you'd like to use to add to any cloned
104 : /// names, specify it as the optional third parameter.
105 : ///
106 : /// If you would like the basic block to be auto-inserted into the end of a
107 : /// function, you can specify it as the optional fourth parameter.
108 : ///
109 : /// If you would like to collect additional information about the cloned
110 : /// function, you can specify a ClonedCodeInfo object with the optional fifth
111 : /// parameter.
112 : ///
113 : BasicBlock *CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap,
114 : const Twine &NameSuffix = "", Function *F = nullptr,
115 : ClonedCodeInfo *CodeInfo = nullptr,
116 : DebugInfoFinder *DIFinder = nullptr);
117 :
118 : /// CloneFunction - Return a copy of the specified function and add it to that
119 : /// function's module. Also, any references specified in the VMap are changed
120 : /// to refer to their mapped value instead of the original one. If any of the
121 : /// arguments to the function are in the VMap, the arguments are deleted from
122 : /// the resultant function. The VMap is updated to include mappings from all of
123 : /// the instructions and basicblocks in the function from their old to new
124 : /// values. The final argument captures information about the cloned code if
125 : /// non-null.
126 : ///
127 : /// VMap contains no non-identity GlobalValue mappings and debug info metadata
128 : /// will not be cloned.
129 : ///
130 : Function *CloneFunction(Function *F, ValueToValueMapTy &VMap,
131 : ClonedCodeInfo *CodeInfo = nullptr);
132 :
133 : /// Clone OldFunc into NewFunc, transforming the old arguments into references
134 : /// to VMap values. Note that if NewFunc already has basic blocks, the ones
135 : /// cloned into it will be added to the end of the function. This function
136 : /// fills in a list of return instructions, and can optionally remap types
137 : /// and/or append the specified suffix to all values cloned.
138 : ///
139 : /// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue
140 : /// mappings.
141 : ///
142 : void CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
143 : ValueToValueMapTy &VMap, bool ModuleLevelChanges,
144 : SmallVectorImpl<ReturnInst*> &Returns,
145 : const char *NameSuffix = "",
146 : ClonedCodeInfo *CodeInfo = nullptr,
147 : ValueMapTypeRemapper *TypeMapper = nullptr,
148 : ValueMaterializer *Materializer = nullptr);
149 :
150 : void CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc,
151 : const Instruction *StartingInst,
152 : ValueToValueMapTy &VMap, bool ModuleLevelChanges,
153 : SmallVectorImpl<ReturnInst *> &Returns,
154 : const char *NameSuffix = "",
155 : ClonedCodeInfo *CodeInfo = nullptr);
156 :
157 : /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
158 : /// except that it does some simple constant prop and DCE on the fly. The
159 : /// effect of this is to copy significantly less code in cases where (for
160 : /// example) a function call with constant arguments is inlined, and those
161 : /// constant arguments cause a significant amount of code in the callee to be
162 : /// dead. Since this doesn't produce an exactly copy of the input, it can't be
163 : /// used for things like CloneFunction or CloneModule.
164 : ///
165 : /// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue
166 : /// mappings.
167 : ///
168 : void CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
169 : ValueToValueMapTy &VMap, bool ModuleLevelChanges,
170 : SmallVectorImpl<ReturnInst*> &Returns,
171 : const char *NameSuffix = "",
172 : ClonedCodeInfo *CodeInfo = nullptr,
173 : Instruction *TheCall = nullptr);
174 :
175 : /// InlineFunctionInfo - This class captures the data input to the
176 : /// InlineFunction call, and records the auxiliary results produced by it.
177 : class InlineFunctionInfo {
178 : public:
179 : explicit InlineFunctionInfo(CallGraph *cg = nullptr,
180 : std::function<AssumptionCache &(Function &)>
181 : *GetAssumptionCache = nullptr,
182 : ProfileSummaryInfo *PSI = nullptr,
183 : BlockFrequencyInfo *CallerBFI = nullptr,
184 : BlockFrequencyInfo *CalleeBFI = nullptr)
185 538885 : : CG(cg), GetAssumptionCache(GetAssumptionCache), PSI(PSI),
186 538885 : CallerBFI(CallerBFI), CalleeBFI(CalleeBFI) {}
187 :
188 : /// CG - If non-null, InlineFunction will update the callgraph to reflect the
189 : /// changes it makes.
190 : CallGraph *CG;
191 : std::function<AssumptionCache &(Function &)> *GetAssumptionCache;
192 : ProfileSummaryInfo *PSI;
193 : BlockFrequencyInfo *CallerBFI, *CalleeBFI;
194 :
195 : /// StaticAllocas - InlineFunction fills this in with all static allocas that
196 : /// get copied into the caller.
197 : SmallVector<AllocaInst *, 4> StaticAllocas;
198 :
199 : /// InlinedCalls - InlineFunction fills this in with callsites that were
200 : /// inlined from the callee. This is only filled in if CG is non-null.
201 : SmallVector<WeakTrackingVH, 8> InlinedCalls;
202 :
203 : /// All of the new call sites inlined into the caller.
204 : ///
205 : /// 'InlineFunction' fills this in by scanning the inlined instructions, and
206 : /// only if CG is null. If CG is non-null, instead the value handle
207 : /// `InlinedCalls` above is used.
208 : SmallVector<CallSite, 8> InlinedCallSites;
209 :
210 : void reset() {
211 : StaticAllocas.clear();
212 : InlinedCalls.clear();
213 : InlinedCallSites.clear();
214 : }
215 : };
216 :
217 : /// InlineFunction - This function inlines the called function into the basic
218 : /// block of the caller. This returns false if it is not possible to inline
219 : /// this call. The program is still in a well defined state if this occurs
220 : /// though.
221 : ///
222 : /// Note that this only does one level of inlining. For example, if the
223 : /// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now
224 : /// exists in the instruction stream. Similarly this will inline a recursive
225 : /// function by one level.
226 : ///
227 : /// Note that while this routine is allowed to cleanup and optimize the
228 : /// *inlined* code to minimize the actual inserted code, it must not delete
229 : /// code in the caller as users of this routine may have pointers to
230 : /// instructions in the caller that need to remain stable.
231 : ///
232 : /// If ForwardVarArgsTo is passed, inlining a function with varargs is allowed
233 : /// and all varargs at the callsite will be passed to any calls to
234 : /// ForwardVarArgsTo. The caller of InlineFunction has to make sure any varargs
235 : /// are only used by ForwardVarArgsTo.
236 : InlineResult InlineFunction(CallInst *C, InlineFunctionInfo &IFI,
237 : AAResults *CalleeAAR = nullptr,
238 : bool InsertLifetime = true);
239 : InlineResult InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI,
240 : AAResults *CalleeAAR = nullptr,
241 : bool InsertLifetime = true);
242 : InlineResult InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
243 : AAResults *CalleeAAR = nullptr,
244 : bool InsertLifetime = true,
245 : Function *ForwardVarArgsTo = nullptr);
246 :
247 : /// Clones a loop \p OrigLoop. Returns the loop and the blocks in \p
248 : /// Blocks.
249 : ///
250 : /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block
251 : /// \p LoopDomBB. Insert the new blocks before block specified in \p Before.
252 : /// Note: Only innermost loops are supported.
253 : Loop *cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
254 : Loop *OrigLoop, ValueToValueMapTy &VMap,
255 : const Twine &NameSuffix, LoopInfo *LI,
256 : DominatorTree *DT,
257 : SmallVectorImpl<BasicBlock *> &Blocks);
258 :
259 : /// Remaps instructions in \p Blocks using the mapping in \p VMap.
260 : void remapInstructionsInBlocks(const SmallVectorImpl<BasicBlock *> &Blocks,
261 : ValueToValueMapTy &VMap);
262 :
263 : /// Split edge between BB and PredBB and duplicate all non-Phi instructions
264 : /// from BB between its beginning and the StopAt instruction into the split
265 : /// block. Phi nodes are not duplicated, but their uses are handled correctly:
266 : /// we replace them with the uses of corresponding Phi inputs. ValueMapping
267 : /// is used to map the original instructions from BB to their newly-created
268 : /// copies. Returns the split block.
269 : BasicBlock *
270 : DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB,
271 : Instruction *StopAt,
272 : ValueToValueMapTy &ValueMapping,
273 : DominatorTree *DT = nullptr);
274 : } // end namespace llvm
275 :
276 : #endif // LLVM_TRANSFORMS_UTILS_CLONING_H
|
