File: | build/source/llvm/lib/Transforms/IPO/MergeFunctions.cpp |
Warning: | line 681, column 23 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- MergeFunctions.cpp - Merge identical functions ---------------------===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | // This pass looks for equivalent functions that are mergable and folds them. | |||
10 | // | |||
11 | // Order relation is defined on set of functions. It was made through | |||
12 | // special function comparison procedure that returns | |||
13 | // 0 when functions are equal, | |||
14 | // -1 when Left function is less than right function, and | |||
15 | // 1 for opposite case. We need total-ordering, so we need to maintain | |||
16 | // four properties on the functions set: | |||
17 | // a <= a (reflexivity) | |||
18 | // if a <= b and b <= a then a = b (antisymmetry) | |||
19 | // if a <= b and b <= c then a <= c (transitivity). | |||
20 | // for all a and b: a <= b or b <= a (totality). | |||
21 | // | |||
22 | // Comparison iterates through each instruction in each basic block. | |||
23 | // Functions are kept on binary tree. For each new function F we perform | |||
24 | // lookup in binary tree. | |||
25 | // In practice it works the following way: | |||
26 | // -- We define Function* container class with custom "operator<" (FunctionPtr). | |||
27 | // -- "FunctionPtr" instances are stored in std::set collection, so every | |||
28 | // std::set::insert operation will give you result in log(N) time. | |||
29 | // | |||
30 | // As an optimization, a hash of the function structure is calculated first, and | |||
31 | // two functions are only compared if they have the same hash. This hash is | |||
32 | // cheap to compute, and has the property that if function F == G according to | |||
33 | // the comparison function, then hash(F) == hash(G). This consistency property | |||
34 | // is critical to ensuring all possible merging opportunities are exploited. | |||
35 | // Collisions in the hash affect the speed of the pass but not the correctness | |||
36 | // or determinism of the resulting transformation. | |||
37 | // | |||
38 | // When a match is found the functions are folded. If both functions are | |||
39 | // overridable, we move the functionality into a new internal function and | |||
40 | // leave two overridable thunks to it. | |||
41 | // | |||
42 | //===----------------------------------------------------------------------===// | |||
43 | // | |||
44 | // Future work: | |||
45 | // | |||
46 | // * virtual functions. | |||
47 | // | |||
48 | // Many functions have their address taken by the virtual function table for | |||
49 | // the object they belong to. However, as long as it's only used for a lookup | |||
50 | // and call, this is irrelevant, and we'd like to fold such functions. | |||
51 | // | |||
52 | // * be smarter about bitcasts. | |||
53 | // | |||
54 | // In order to fold functions, we will sometimes add either bitcast instructions | |||
55 | // or bitcast constant expressions. Unfortunately, this can confound further | |||
56 | // analysis since the two functions differ where one has a bitcast and the | |||
57 | // other doesn't. We should learn to look through bitcasts. | |||
58 | // | |||
59 | // * Compare complex types with pointer types inside. | |||
60 | // * Compare cross-reference cases. | |||
61 | // * Compare complex expressions. | |||
62 | // | |||
63 | // All the three issues above could be described as ability to prove that | |||
64 | // fA == fB == fC == fE == fF == fG in example below: | |||
65 | // | |||
66 | // void fA() { | |||
67 | // fB(); | |||
68 | // } | |||
69 | // void fB() { | |||
70 | // fA(); | |||
71 | // } | |||
72 | // | |||
73 | // void fE() { | |||
74 | // fF(); | |||
75 | // } | |||
76 | // void fF() { | |||
77 | // fG(); | |||
78 | // } | |||
79 | // void fG() { | |||
80 | // fE(); | |||
81 | // } | |||
82 | // | |||
83 | // Simplest cross-reference case (fA <--> fB) was implemented in previous | |||
84 | // versions of MergeFunctions, though it presented only in two function pairs | |||
85 | // in test-suite (that counts >50k functions) | |||
86 | // Though possibility to detect complex cross-referencing (e.g.: A->B->C->D->A) | |||
87 | // could cover much more cases. | |||
88 | // | |||
89 | //===----------------------------------------------------------------------===// | |||
90 | ||||
91 | #include "llvm/Transforms/IPO/MergeFunctions.h" | |||
92 | #include "llvm/ADT/ArrayRef.h" | |||
93 | #include "llvm/ADT/SmallVector.h" | |||
94 | #include "llvm/ADT/Statistic.h" | |||
95 | #include "llvm/IR/Argument.h" | |||
96 | #include "llvm/IR/BasicBlock.h" | |||
97 | #include "llvm/IR/Constant.h" | |||
98 | #include "llvm/IR/Constants.h" | |||
99 | #include "llvm/IR/DebugInfoMetadata.h" | |||
100 | #include "llvm/IR/DebugLoc.h" | |||
101 | #include "llvm/IR/DerivedTypes.h" | |||
102 | #include "llvm/IR/Function.h" | |||
103 | #include "llvm/IR/GlobalValue.h" | |||
104 | #include "llvm/IR/IRBuilder.h" | |||
105 | #include "llvm/IR/InstrTypes.h" | |||
106 | #include "llvm/IR/Instruction.h" | |||
107 | #include "llvm/IR/Instructions.h" | |||
108 | #include "llvm/IR/IntrinsicInst.h" | |||
109 | #include "llvm/IR/Module.h" | |||
110 | #include "llvm/IR/Type.h" | |||
111 | #include "llvm/IR/Use.h" | |||
112 | #include "llvm/IR/User.h" | |||
113 | #include "llvm/IR/Value.h" | |||
114 | #include "llvm/IR/ValueHandle.h" | |||
115 | #include "llvm/Support/Casting.h" | |||
116 | #include "llvm/Support/CommandLine.h" | |||
117 | #include "llvm/Support/Debug.h" | |||
118 | #include "llvm/Support/raw_ostream.h" | |||
119 | #include "llvm/Transforms/IPO.h" | |||
120 | #include "llvm/Transforms/Utils/FunctionComparator.h" | |||
121 | #include "llvm/Transforms/Utils/ModuleUtils.h" | |||
122 | #include <algorithm> | |||
123 | #include <cassert> | |||
124 | #include <iterator> | |||
125 | #include <set> | |||
126 | #include <utility> | |||
127 | #include <vector> | |||
128 | ||||
129 | using namespace llvm; | |||
130 | ||||
131 | #define DEBUG_TYPE"mergefunc" "mergefunc" | |||
132 | ||||
133 | STATISTIC(NumFunctionsMerged, "Number of functions merged")static llvm::Statistic NumFunctionsMerged = {"mergefunc", "NumFunctionsMerged" , "Number of functions merged"}; | |||
134 | STATISTIC(NumThunksWritten, "Number of thunks generated")static llvm::Statistic NumThunksWritten = {"mergefunc", "NumThunksWritten" , "Number of thunks generated"}; | |||
135 | STATISTIC(NumAliasesWritten, "Number of aliases generated")static llvm::Statistic NumAliasesWritten = {"mergefunc", "NumAliasesWritten" , "Number of aliases generated"}; | |||
136 | STATISTIC(NumDoubleWeak, "Number of new functions created")static llvm::Statistic NumDoubleWeak = {"mergefunc", "NumDoubleWeak" , "Number of new functions created"}; | |||
137 | ||||
138 | static cl::opt<unsigned> NumFunctionsForVerificationCheck( | |||
139 | "mergefunc-verify", | |||
140 | cl::desc("How many functions in a module could be used for " | |||
141 | "MergeFunctions to pass a basic correctness check. " | |||
142 | "'0' disables this check. Works only with '-debug' key."), | |||
143 | cl::init(0), cl::Hidden); | |||
144 | ||||
145 | // Under option -mergefunc-preserve-debug-info we: | |||
146 | // - Do not create a new function for a thunk. | |||
147 | // - Retain the debug info for a thunk's parameters (and associated | |||
148 | // instructions for the debug info) from the entry block. | |||
149 | // Note: -debug will display the algorithm at work. | |||
150 | // - Create debug-info for the call (to the shared implementation) made by | |||
151 | // a thunk and its return value. | |||
152 | // - Erase the rest of the function, retaining the (minimally sized) entry | |||
153 | // block to create a thunk. | |||
154 | // - Preserve a thunk's call site to point to the thunk even when both occur | |||
155 | // within the same translation unit, to aid debugability. Note that this | |||
156 | // behaviour differs from the underlying -mergefunc implementation which | |||
157 | // modifies the thunk's call site to point to the shared implementation | |||
158 | // when both occur within the same translation unit. | |||
159 | static cl::opt<bool> | |||
160 | MergeFunctionsPDI("mergefunc-preserve-debug-info", cl::Hidden, | |||
161 | cl::init(false), | |||
162 | cl::desc("Preserve debug info in thunk when mergefunc " | |||
163 | "transformations are made.")); | |||
164 | ||||
165 | static cl::opt<bool> | |||
166 | MergeFunctionsAliases("mergefunc-use-aliases", cl::Hidden, | |||
167 | cl::init(false), | |||
168 | cl::desc("Allow mergefunc to create aliases")); | |||
169 | ||||
170 | namespace { | |||
171 | ||||
172 | class FunctionNode { | |||
173 | mutable AssertingVH<Function> F; | |||
174 | FunctionComparator::FunctionHash Hash; | |||
175 | ||||
176 | public: | |||
177 | // Note the hash is recalculated potentially multiple times, but it is cheap. | |||
178 | FunctionNode(Function *F) | |||
179 | : F(F), Hash(FunctionComparator::functionHash(*F)) {} | |||
180 | ||||
181 | Function *getFunc() const { return F; } | |||
182 | FunctionComparator::FunctionHash getHash() const { return Hash; } | |||
183 | ||||
184 | /// Replace the reference to the function F by the function G, assuming their | |||
185 | /// implementations are equal. | |||
186 | void replaceBy(Function *G) const { | |||
187 | F = G; | |||
188 | } | |||
189 | }; | |||
190 | ||||
191 | /// MergeFunctions finds functions which will generate identical machine code, | |||
192 | /// by considering all pointer types to be equivalent. Once identified, | |||
193 | /// MergeFunctions will fold them by replacing a call to one to a call to a | |||
194 | /// bitcast of the other. | |||
195 | class MergeFunctions { | |||
196 | public: | |||
197 | MergeFunctions() : FnTree(FunctionNodeCmp(&GlobalNumbers)) { | |||
198 | } | |||
199 | ||||
200 | bool runOnModule(Module &M); | |||
201 | ||||
202 | private: | |||
203 | // The function comparison operator is provided here so that FunctionNodes do | |||
204 | // not need to become larger with another pointer. | |||
205 | class FunctionNodeCmp { | |||
206 | GlobalNumberState* GlobalNumbers; | |||
207 | ||||
208 | public: | |||
209 | FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {} | |||
210 | ||||
211 | bool operator()(const FunctionNode &LHS, const FunctionNode &RHS) const { | |||
212 | // Order first by hashes, then full function comparison. | |||
213 | if (LHS.getHash() != RHS.getHash()) | |||
214 | return LHS.getHash() < RHS.getHash(); | |||
215 | FunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(), GlobalNumbers); | |||
216 | return FCmp.compare() < 0; | |||
217 | } | |||
218 | }; | |||
219 | using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>; | |||
220 | ||||
221 | GlobalNumberState GlobalNumbers; | |||
222 | ||||
223 | /// A work queue of functions that may have been modified and should be | |||
224 | /// analyzed again. | |||
225 | std::vector<WeakTrackingVH> Deferred; | |||
226 | ||||
227 | /// Set of values marked as used in llvm.used and llvm.compiler.used. | |||
228 | SmallPtrSet<GlobalValue *, 4> Used; | |||
229 | ||||
230 | #ifndef NDEBUG | |||
231 | /// Checks the rules of order relation introduced among functions set. | |||
232 | /// Returns true, if check has been passed, and false if failed. | |||
233 | bool doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist); | |||
234 | #endif | |||
235 | ||||
236 | /// Insert a ComparableFunction into the FnTree, or merge it away if it's | |||
237 | /// equal to one that's already present. | |||
238 | bool insert(Function *NewFunction); | |||
239 | ||||
240 | /// Remove a Function from the FnTree and queue it up for a second sweep of | |||
241 | /// analysis. | |||
242 | void remove(Function *F); | |||
243 | ||||
244 | /// Find the functions that use this Value and remove them from FnTree and | |||
245 | /// queue the functions. | |||
246 | void removeUsers(Value *V); | |||
247 | ||||
248 | /// Replace all direct calls of Old with calls of New. Will bitcast New if | |||
249 | /// necessary to make types match. | |||
250 | void replaceDirectCallers(Function *Old, Function *New); | |||
251 | ||||
252 | /// Merge two equivalent functions. Upon completion, G may be deleted, or may | |||
253 | /// be converted into a thunk. In either case, it should never be visited | |||
254 | /// again. | |||
255 | void mergeTwoFunctions(Function *F, Function *G); | |||
256 | ||||
257 | /// Fill PDIUnrelatedWL with instructions from the entry block that are | |||
258 | /// unrelated to parameter related debug info. | |||
259 | void filterInstsUnrelatedToPDI(BasicBlock *GEntryBlock, | |||
260 | std::vector<Instruction *> &PDIUnrelatedWL); | |||
261 | ||||
262 | /// Erase the rest of the CFG (i.e. barring the entry block). | |||
263 | void eraseTail(Function *G); | |||
264 | ||||
265 | /// Erase the instructions in PDIUnrelatedWL as they are unrelated to the | |||
266 | /// parameter debug info, from the entry block. | |||
267 | void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL); | |||
268 | ||||
269 | /// Replace G with a simple tail call to bitcast(F). Also (unless | |||
270 | /// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F), | |||
271 | /// delete G. | |||
272 | void writeThunk(Function *F, Function *G); | |||
273 | ||||
274 | // Replace G with an alias to F (deleting function G) | |||
275 | void writeAlias(Function *F, Function *G); | |||
276 | ||||
277 | // Replace G with an alias to F if possible, or a thunk to F if possible. | |||
278 | // Returns false if neither is the case. | |||
279 | bool writeThunkOrAlias(Function *F, Function *G); | |||
280 | ||||
281 | /// Replace function F with function G in the function tree. | |||
282 | void replaceFunctionInTree(const FunctionNode &FN, Function *G); | |||
283 | ||||
284 | /// The set of all distinct functions. Use the insert() and remove() methods | |||
285 | /// to modify it. The map allows efficient lookup and deferring of Functions. | |||
286 | FnTreeType FnTree; | |||
287 | ||||
288 | // Map functions to the iterators of the FunctionNode which contains them | |||
289 | // in the FnTree. This must be updated carefully whenever the FnTree is | |||
290 | // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid | |||
291 | // dangling iterators into FnTree. The invariant that preserves this is that | |||
292 | // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree. | |||
293 | DenseMap<AssertingVH<Function>, FnTreeType::iterator> FNodesInTree; | |||
294 | }; | |||
295 | } // end anonymous namespace | |||
296 | ||||
297 | PreservedAnalyses MergeFunctionsPass::run(Module &M, | |||
298 | ModuleAnalysisManager &AM) { | |||
299 | MergeFunctions MF; | |||
300 | if (!MF.runOnModule(M)) | |||
301 | return PreservedAnalyses::all(); | |||
302 | return PreservedAnalyses::none(); | |||
303 | } | |||
304 | ||||
305 | #ifndef NDEBUG | |||
306 | bool MergeFunctions::doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist) { | |||
307 | if (const unsigned Max = NumFunctionsForVerificationCheck) { | |||
308 | unsigned TripleNumber = 0; | |||
309 | bool Valid = true; | |||
310 | ||||
311 | dbgs() << "MERGEFUNC-VERIFY: Started for first " << Max << " functions.\n"; | |||
312 | ||||
313 | unsigned i = 0; | |||
314 | for (std::vector<WeakTrackingVH>::iterator I = Worklist.begin(), | |||
315 | E = Worklist.end(); | |||
316 | I != E && i < Max; ++I, ++i) { | |||
317 | unsigned j = i; | |||
318 | for (std::vector<WeakTrackingVH>::iterator J = I; J != E && j < Max; | |||
319 | ++J, ++j) { | |||
320 | Function *F1 = cast<Function>(*I); | |||
321 | Function *F2 = cast<Function>(*J); | |||
322 | int Res1 = FunctionComparator(F1, F2, &GlobalNumbers).compare(); | |||
323 | int Res2 = FunctionComparator(F2, F1, &GlobalNumbers).compare(); | |||
324 | ||||
325 | // If F1 <= F2, then F2 >= F1, otherwise report failure. | |||
326 | if (Res1 != -Res2) { | |||
327 | dbgs() << "MERGEFUNC-VERIFY: Non-symmetric; triple: " << TripleNumber | |||
328 | << "\n"; | |||
329 | dbgs() << *F1 << '\n' << *F2 << '\n'; | |||
330 | Valid = false; | |||
331 | } | |||
332 | ||||
333 | if (Res1 == 0) | |||
334 | continue; | |||
335 | ||||
336 | unsigned k = j; | |||
337 | for (std::vector<WeakTrackingVH>::iterator K = J; K != E && k < Max; | |||
338 | ++k, ++K, ++TripleNumber) { | |||
339 | if (K == J) | |||
340 | continue; | |||
341 | ||||
342 | Function *F3 = cast<Function>(*K); | |||
343 | int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare(); | |||
344 | int Res4 = FunctionComparator(F2, F3, &GlobalNumbers).compare(); | |||
345 | ||||
346 | bool Transitive = true; | |||
347 | ||||
348 | if (Res1 != 0 && Res1 == Res4) { | |||
349 | // F1 > F2, F2 > F3 => F1 > F3 | |||
350 | Transitive = Res3 == Res1; | |||
351 | } else if (Res3 != 0 && Res3 == -Res4) { | |||
352 | // F1 > F3, F3 > F2 => F1 > F2 | |||
353 | Transitive = Res3 == Res1; | |||
354 | } else if (Res4 != 0 && -Res3 == Res4) { | |||
355 | // F2 > F3, F3 > F1 => F2 > F1 | |||
356 | Transitive = Res4 == -Res1; | |||
357 | } | |||
358 | ||||
359 | if (!Transitive) { | |||
360 | dbgs() << "MERGEFUNC-VERIFY: Non-transitive; triple: " | |||
361 | << TripleNumber << "\n"; | |||
362 | dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", " | |||
363 | << Res4 << "\n"; | |||
364 | dbgs() << *F1 << '\n' << *F2 << '\n' << *F3 << '\n'; | |||
365 | Valid = false; | |||
366 | } | |||
367 | } | |||
368 | } | |||
369 | } | |||
370 | ||||
371 | dbgs() << "MERGEFUNC-VERIFY: " << (Valid ? "Passed." : "Failed.") << "\n"; | |||
372 | return Valid; | |||
373 | } | |||
374 | return true; | |||
375 | } | |||
376 | #endif | |||
377 | ||||
378 | /// Check whether \p F is eligible for function merging. | |||
379 | static bool isEligibleForMerging(Function &F) { | |||
380 | return !F.isDeclaration() && !F.hasAvailableExternallyLinkage(); | |||
381 | } | |||
382 | ||||
383 | bool MergeFunctions::runOnModule(Module &M) { | |||
384 | bool Changed = false; | |||
385 | ||||
386 | SmallVector<GlobalValue *, 4> UsedV; | |||
387 | collectUsedGlobalVariables(M, UsedV, /*CompilerUsed=*/false); | |||
388 | collectUsedGlobalVariables(M, UsedV, /*CompilerUsed=*/true); | |||
389 | Used.insert(UsedV.begin(), UsedV.end()); | |||
390 | ||||
391 | // All functions in the module, ordered by hash. Functions with a unique | |||
392 | // hash value are easily eliminated. | |||
393 | std::vector<std::pair<FunctionComparator::FunctionHash, Function *>> | |||
394 | HashedFuncs; | |||
395 | for (Function &Func : M) { | |||
396 | if (isEligibleForMerging(Func)) { | |||
397 | HashedFuncs.push_back({FunctionComparator::functionHash(Func), &Func}); | |||
398 | } | |||
399 | } | |||
400 | ||||
401 | llvm::stable_sort(HashedFuncs, less_first()); | |||
402 | ||||
403 | auto S = HashedFuncs.begin(); | |||
404 | for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) { | |||
405 | // If the hash value matches the previous value or the next one, we must | |||
406 | // consider merging it. Otherwise it is dropped and never considered again. | |||
407 | if ((I != S && std::prev(I)->first == I->first) || | |||
408 | (std::next(I) != IE && std::next(I)->first == I->first) ) { | |||
409 | Deferred.push_back(WeakTrackingVH(I->second)); | |||
410 | } | |||
411 | } | |||
412 | ||||
413 | do { | |||
414 | std::vector<WeakTrackingVH> Worklist; | |||
415 | Deferred.swap(Worklist); | |||
416 | ||||
417 | LLVM_DEBUG(doFunctionalCheck(Worklist))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { doFunctionalCheck(Worklist); } } while (false ); | |||
418 | ||||
419 | LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "size of module: " << M .size() << '\n'; } } while (false); | |||
420 | LLVM_DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "size of worklist: " << Worklist.size() << '\n'; } } while (false); | |||
421 | ||||
422 | // Insert functions and merge them. | |||
423 | for (WeakTrackingVH &I : Worklist) { | |||
424 | if (!I) | |||
425 | continue; | |||
426 | Function *F = cast<Function>(I); | |||
427 | if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) { | |||
428 | Changed |= insert(F); | |||
429 | } | |||
430 | } | |||
431 | LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "size of FnTree: " << FnTree .size() << '\n'; } } while (false); | |||
432 | } while (!Deferred.empty()); | |||
433 | ||||
434 | FnTree.clear(); | |||
435 | FNodesInTree.clear(); | |||
436 | GlobalNumbers.clear(); | |||
437 | Used.clear(); | |||
438 | ||||
439 | return Changed; | |||
440 | } | |||
441 | ||||
442 | // Replace direct callers of Old with New. | |||
443 | void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) { | |||
444 | Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType()); | |||
445 | for (Use &U : llvm::make_early_inc_range(Old->uses())) { | |||
446 | CallBase *CB = dyn_cast<CallBase>(U.getUser()); | |||
447 | if (CB && CB->isCallee(&U)) { | |||
448 | // Do not copy attributes from the called function to the call-site. | |||
449 | // Function comparison ensures that the attributes are the same up to | |||
450 | // type congruences in byval(), in which case we need to keep the byval | |||
451 | // type of the call-site, not the callee function. | |||
452 | remove(CB->getFunction()); | |||
453 | U.set(BitcastNew); | |||
454 | } | |||
455 | } | |||
456 | } | |||
457 | ||||
458 | // Helper for writeThunk, | |||
459 | // Selects proper bitcast operation, | |||
460 | // but a bit simpler then CastInst::getCastOpcode. | |||
461 | static Value *createCast(IRBuilder<> &Builder, Value *V, Type *DestTy) { | |||
462 | Type *SrcTy = V->getType(); | |||
463 | if (SrcTy->isStructTy()) { | |||
464 | assert(DestTy->isStructTy())(static_cast <bool> (DestTy->isStructTy()) ? void (0 ) : __assert_fail ("DestTy->isStructTy()", "llvm/lib/Transforms/IPO/MergeFunctions.cpp" , 464, __extension__ __PRETTY_FUNCTION__)); | |||
465 | assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements())(static_cast <bool> (SrcTy->getStructNumElements() == DestTy->getStructNumElements()) ? void (0) : __assert_fail ("SrcTy->getStructNumElements() == DestTy->getStructNumElements()" , "llvm/lib/Transforms/IPO/MergeFunctions.cpp", 465, __extension__ __PRETTY_FUNCTION__)); | |||
466 | Value *Result = PoisonValue::get(DestTy); | |||
467 | for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) { | |||
468 | Value *Element = | |||
469 | createCast(Builder, Builder.CreateExtractValue(V, ArrayRef(I)), | |||
470 | DestTy->getStructElementType(I)); | |||
471 | ||||
472 | Result = Builder.CreateInsertValue(Result, Element, ArrayRef(I)); | |||
473 | } | |||
474 | return Result; | |||
475 | } | |||
476 | assert(!DestTy->isStructTy())(static_cast <bool> (!DestTy->isStructTy()) ? void ( 0) : __assert_fail ("!DestTy->isStructTy()", "llvm/lib/Transforms/IPO/MergeFunctions.cpp" , 476, __extension__ __PRETTY_FUNCTION__)); | |||
477 | if (SrcTy->isIntegerTy() && DestTy->isPointerTy()) | |||
478 | return Builder.CreateIntToPtr(V, DestTy); | |||
479 | else if (SrcTy->isPointerTy() && DestTy->isIntegerTy()) | |||
480 | return Builder.CreatePtrToInt(V, DestTy); | |||
481 | else | |||
482 | return Builder.CreateBitCast(V, DestTy); | |||
483 | } | |||
484 | ||||
485 | // Erase the instructions in PDIUnrelatedWL as they are unrelated to the | |||
486 | // parameter debug info, from the entry block. | |||
487 | void MergeFunctions::eraseInstsUnrelatedToPDI( | |||
488 | std::vector<Instruction *> &PDIUnrelatedWL) { | |||
489 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Erasing instructions (in reverse order of appearance in " "entry block) unrelated to parameter debug info from entry " "block: {\n"; } } while (false) | |||
490 | dbgs() << " Erasing instructions (in reverse order of appearance in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Erasing instructions (in reverse order of appearance in " "entry block) unrelated to parameter debug info from entry " "block: {\n"; } } while (false) | |||
491 | "entry block) unrelated to parameter debug info from entry "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Erasing instructions (in reverse order of appearance in " "entry block) unrelated to parameter debug info from entry " "block: {\n"; } } while (false) | |||
492 | "block: {\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Erasing instructions (in reverse order of appearance in " "entry block) unrelated to parameter debug info from entry " "block: {\n"; } } while (false); | |||
493 | while (!PDIUnrelatedWL.empty()) { | |||
494 | Instruction *I = PDIUnrelatedWL.back(); | |||
495 | LLVM_DEBUG(dbgs() << " Deleting Instruction: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Deleting Instruction: "; } } while (false); | |||
496 | LLVM_DEBUG(I->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { I->print(dbgs()); } } while (false); | |||
497 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
498 | I->eraseFromParent(); | |||
499 | PDIUnrelatedWL.pop_back(); | |||
500 | } | |||
501 | LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " } // Done erasing instructions unrelated to parameter " "debug info from entry block. \n"; } } while (false) | |||
502 | "debug info from entry block. \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " } // Done erasing instructions unrelated to parameter " "debug info from entry block. \n"; } } while (false); | |||
503 | } | |||
504 | ||||
505 | // Reduce G to its entry block. | |||
506 | void MergeFunctions::eraseTail(Function *G) { | |||
507 | std::vector<BasicBlock *> WorklistBB; | |||
508 | for (BasicBlock &BB : drop_begin(*G)) { | |||
509 | BB.dropAllReferences(); | |||
510 | WorklistBB.push_back(&BB); | |||
511 | } | |||
512 | while (!WorklistBB.empty()) { | |||
513 | BasicBlock *BB = WorklistBB.back(); | |||
514 | BB->eraseFromParent(); | |||
515 | WorklistBB.pop_back(); | |||
516 | } | |||
517 | } | |||
518 | ||||
519 | // We are interested in the following instructions from the entry block as being | |||
520 | // related to parameter debug info: | |||
521 | // - @llvm.dbg.declare | |||
522 | // - stores from the incoming parameters to locations on the stack-frame | |||
523 | // - allocas that create these locations on the stack-frame | |||
524 | // - @llvm.dbg.value | |||
525 | // - the entry block's terminator | |||
526 | // The rest are unrelated to debug info for the parameters; fill up | |||
527 | // PDIUnrelatedWL with such instructions. | |||
528 | void MergeFunctions::filterInstsUnrelatedToPDI( | |||
529 | BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) { | |||
530 | std::set<Instruction *> PDIRelated; | |||
531 | for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end(); | |||
532 | BI != BIE; ++BI) { | |||
533 | if (auto *DVI = dyn_cast<DbgValueInst>(&*BI)) { | |||
534 | LLVM_DEBUG(dbgs() << " Deciding: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Deciding: "; } } while (false ); | |||
535 | LLVM_DEBUG(BI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { BI->print(dbgs()); } } while (false); | |||
536 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
537 | DILocalVariable *DILocVar = DVI->getVariable(); | |||
538 | if (DILocVar->isParameter()) { | |||
539 | LLVM_DEBUG(dbgs() << " Include (parameter): ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Include (parameter): "; } } while (false); | |||
540 | LLVM_DEBUG(BI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { BI->print(dbgs()); } } while (false); | |||
541 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
542 | PDIRelated.insert(&*BI); | |||
543 | } else { | |||
544 | LLVM_DEBUG(dbgs() << " Delete (!parameter): ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Delete (!parameter): "; } } while (false); | |||
545 | LLVM_DEBUG(BI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { BI->print(dbgs()); } } while (false); | |||
546 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
547 | } | |||
548 | } else if (auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) { | |||
549 | LLVM_DEBUG(dbgs() << " Deciding: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Deciding: "; } } while (false ); | |||
550 | LLVM_DEBUG(BI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { BI->print(dbgs()); } } while (false); | |||
551 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
552 | DILocalVariable *DILocVar = DDI->getVariable(); | |||
553 | if (DILocVar->isParameter()) { | |||
554 | LLVM_DEBUG(dbgs() << " Parameter: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Parameter: "; } } while ( false); | |||
555 | LLVM_DEBUG(DILocVar->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { DILocVar->print(dbgs()); } } while (false ); | |||
556 | AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress()); | |||
557 | if (AI) { | |||
558 | LLVM_DEBUG(dbgs() << " Processing alloca users: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Processing alloca users: " ; } } while (false); | |||
559 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
560 | for (User *U : AI->users()) { | |||
561 | if (StoreInst *SI = dyn_cast<StoreInst>(U)) { | |||
562 | if (Value *Arg = SI->getValueOperand()) { | |||
563 | if (isa<Argument>(Arg)) { | |||
564 | LLVM_DEBUG(dbgs() << " Include: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Include: "; } } while (false ); | |||
565 | LLVM_DEBUG(AI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { AI->print(dbgs()); } } while (false); | |||
566 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
567 | PDIRelated.insert(AI); | |||
568 | LLVM_DEBUG(dbgs() << " Include (parameter): ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Include (parameter): "; } } while (false); | |||
569 | LLVM_DEBUG(SI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { SI->print(dbgs()); } } while (false); | |||
570 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
571 | PDIRelated.insert(SI); | |||
572 | LLVM_DEBUG(dbgs() << " Include: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Include: "; } } while (false ); | |||
573 | LLVM_DEBUG(BI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { BI->print(dbgs()); } } while (false); | |||
574 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
575 | PDIRelated.insert(&*BI); | |||
576 | } else { | |||
577 | LLVM_DEBUG(dbgs() << " Delete (!parameter): ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Delete (!parameter): "; } } while (false); | |||
578 | LLVM_DEBUG(SI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { SI->print(dbgs()); } } while (false); | |||
579 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
580 | } | |||
581 | } | |||
582 | } else { | |||
583 | LLVM_DEBUG(dbgs() << " Defer: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Defer: "; } } while (false ); | |||
584 | LLVM_DEBUG(U->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { U->print(dbgs()); } } while (false); | |||
585 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
586 | } | |||
587 | } | |||
588 | } else { | |||
589 | LLVM_DEBUG(dbgs() << " Delete (alloca NULL): ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Delete (alloca NULL): "; } } while (false); | |||
590 | LLVM_DEBUG(BI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { BI->print(dbgs()); } } while (false); | |||
591 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
592 | } | |||
593 | } else { | |||
594 | LLVM_DEBUG(dbgs() << " Delete (!parameter): ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Delete (!parameter): "; } } while (false); | |||
595 | LLVM_DEBUG(BI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { BI->print(dbgs()); } } while (false); | |||
596 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
597 | } | |||
598 | } else if (BI->isTerminator() && &*BI == GEntryBlock->getTerminator()) { | |||
599 | LLVM_DEBUG(dbgs() << " Will Include Terminator: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Will Include Terminator: " ; } } while (false); | |||
600 | LLVM_DEBUG(BI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { BI->print(dbgs()); } } while (false); | |||
601 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
602 | PDIRelated.insert(&*BI); | |||
603 | } else { | |||
604 | LLVM_DEBUG(dbgs() << " Defer: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Defer: "; } } while (false ); | |||
605 | LLVM_DEBUG(BI->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { BI->print(dbgs()); } } while (false); | |||
606 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
607 | } | |||
608 | } | |||
609 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Report parameter debug info related/related instructions: {\n" ; } } while (false) | |||
610 | dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Report parameter debug info related/related instructions: {\n" ; } } while (false) | |||
611 | << " Report parameter debug info related/related instructions: {\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " Report parameter debug info related/related instructions: {\n" ; } } while (false); | |||
612 | for (Instruction &I : *GEntryBlock) { | |||
613 | if (PDIRelated.find(&I) == PDIRelated.end()) { | |||
614 | LLVM_DEBUG(dbgs() << " !PDIRelated: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " !PDIRelated: "; } } while (false); | |||
615 | LLVM_DEBUG(I.print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { I.print(dbgs()); } } while (false); | |||
616 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
617 | PDIUnrelatedWL.push_back(&I); | |||
618 | } else { | |||
619 | LLVM_DEBUG(dbgs() << " PDIRelated: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " PDIRelated: "; } } while (false); | |||
620 | LLVM_DEBUG(I.print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { I.print(dbgs()); } } while (false); | |||
621 | LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "\n"; } } while (false); | |||
622 | } | |||
623 | } | |||
624 | LLVM_DEBUG(dbgs() << " }\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " }\n"; } } while (false); | |||
625 | } | |||
626 | ||||
627 | /// Whether this function may be replaced by a forwarding thunk. | |||
628 | static bool canCreateThunkFor(Function *F) { | |||
629 | if (F->isVarArg()) | |||
630 | return false; | |||
631 | ||||
632 | // Don't merge tiny functions using a thunk, since it can just end up | |||
633 | // making the function larger. | |||
634 | if (F->size() == 1) { | |||
635 | if (F->front().size() <= 2) { | |||
636 | LLVM_DEBUG(dbgs() << "canCreateThunkFor: " << F->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "canCreateThunkFor: " << F->getName() << " is too small to bother creating a thunk for\n" ; } } while (false) | |||
637 | << " is too small to bother creating a thunk for\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "canCreateThunkFor: " << F->getName() << " is too small to bother creating a thunk for\n" ; } } while (false); | |||
638 | return false; | |||
639 | } | |||
640 | } | |||
641 | return true; | |||
642 | } | |||
643 | ||||
644 | // Replace G with a simple tail call to bitcast(F). Also (unless | |||
645 | // MergeFunctionsPDI holds) replace direct uses of G with bitcast(F), | |||
646 | // delete G. Under MergeFunctionsPDI, we use G itself for creating | |||
647 | // the thunk as we preserve the debug info (and associated instructions) | |||
648 | // from G's entry block pertaining to G's incoming arguments which are | |||
649 | // passed on as corresponding arguments in the call that G makes to F. | |||
650 | // For better debugability, under MergeFunctionsPDI, we do not modify G's | |||
651 | // call sites to point to F even when within the same translation unit. | |||
652 | void MergeFunctions::writeThunk(Function *F, Function *G) { | |||
653 | BasicBlock *GEntryBlock = nullptr; | |||
654 | std::vector<Instruction *> PDIUnrelatedWL; | |||
655 | BasicBlock *BB = nullptr; | |||
656 | Function *NewG = nullptr; | |||
| ||||
657 | if (MergeFunctionsPDI) { | |||
658 | LLVM_DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new " "function as thunk; retain original: " << G->getName () << "()\n"; } } while (false) | |||
659 | "function as thunk; retain original: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new " "function as thunk; retain original: " << G->getName () << "()\n"; } } while (false) | |||
660 | << G->getName() << "()\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new " "function as thunk; retain original: " << G->getName () << "()\n"; } } while (false); | |||
661 | GEntryBlock = &G->getEntryBlock(); | |||
662 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related " "debug info for " << G->getName() << "() {\n" ; } } while (false) | |||
663 | dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related " "debug info for " << G->getName() << "() {\n" ; } } while (false) | |||
664 | "debug info for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related " "debug info for " << G->getName() << "() {\n" ; } } while (false) | |||
665 | << G->getName() << "() {\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related " "debug info for " << G->getName() << "() {\n" ; } } while (false); | |||
666 | filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL); | |||
667 | GEntryBlock->getTerminator()->eraseFromParent(); | |||
668 | BB = GEntryBlock; | |||
669 | } else { | |||
670 | NewG = Function::Create(G->getFunctionType(), G->getLinkage(), | |||
671 | G->getAddressSpace(), "", G->getParent()); | |||
672 | NewG->setComdat(G->getComdat()); | |||
673 | BB = BasicBlock::Create(F->getContext(), "", NewG); | |||
674 | } | |||
675 | ||||
676 | IRBuilder<> Builder(BB); | |||
677 | Function *H = MergeFunctionsPDI ? G : NewG; | |||
678 | SmallVector<Value *, 16> Args; | |||
679 | unsigned i = 0; | |||
680 | FunctionType *FFTy = F->getFunctionType(); | |||
681 | for (Argument &AI : H->args()) { | |||
| ||||
682 | Args.push_back(createCast(Builder, &AI, FFTy->getParamType(i))); | |||
683 | ++i; | |||
684 | } | |||
685 | ||||
686 | CallInst *CI = Builder.CreateCall(F, Args); | |||
687 | ReturnInst *RI = nullptr; | |||
688 | bool isSwiftTailCall = F->getCallingConv() == CallingConv::SwiftTail && | |||
689 | G->getCallingConv() == CallingConv::SwiftTail; | |||
690 | CI->setTailCallKind(isSwiftTailCall ? llvm::CallInst::TCK_MustTail | |||
691 | : llvm::CallInst::TCK_Tail); | |||
692 | CI->setCallingConv(F->getCallingConv()); | |||
693 | CI->setAttributes(F->getAttributes()); | |||
694 | if (H->getReturnType()->isVoidTy()) { | |||
695 | RI = Builder.CreateRetVoid(); | |||
696 | } else { | |||
697 | RI = Builder.CreateRet(createCast(Builder, CI, H->getReturnType())); | |||
698 | } | |||
699 | ||||
700 | if (MergeFunctionsPDI) { | |||
701 | DISubprogram *DIS = G->getSubprogram(); | |||
702 | if (DIS) { | |||
703 | DebugLoc CIDbgLoc = | |||
704 | DILocation::get(DIS->getContext(), DIS->getScopeLine(), 0, DIS); | |||
705 | DebugLoc RIDbgLoc = | |||
706 | DILocation::get(DIS->getContext(), DIS->getScopeLine(), 0, DIS); | |||
707 | CI->setDebugLoc(CIDbgLoc); | |||
708 | RI->setDebugLoc(RIDbgLoc); | |||
709 | } else { | |||
710 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for " << G->getName() << "()\n"; } } while (false) | |||
711 | dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for " << G->getName() << "()\n"; } } while (false) | |||
712 | << G->getName() << "()\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for " << G->getName() << "()\n"; } } while (false); | |||
713 | } | |||
714 | eraseTail(G); | |||
715 | eraseInstsUnrelatedToPDI(PDIUnrelatedWL); | |||
716 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "} // End of parameter related debug info filtering for: " << G->getName() << "()\n"; } } while (false) | |||
717 | dbgs() << "} // End of parameter related debug info filtering for: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "} // End of parameter related debug info filtering for: " << G->getName() << "()\n"; } } while (false) | |||
718 | << G->getName() << "()\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "} // End of parameter related debug info filtering for: " << G->getName() << "()\n"; } } while (false); | |||
719 | } else { | |||
720 | NewG->copyAttributesFrom(G); | |||
721 | NewG->takeName(G); | |||
722 | removeUsers(G); | |||
723 | G->replaceAllUsesWith(NewG); | |||
724 | G->eraseFromParent(); | |||
725 | } | |||
726 | ||||
727 | LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeThunk: " << H-> getName() << '\n'; } } while (false); | |||
728 | ++NumThunksWritten; | |||
729 | } | |||
730 | ||||
731 | // Whether this function may be replaced by an alias | |||
732 | static bool canCreateAliasFor(Function *F) { | |||
733 | if (!MergeFunctionsAliases || !F->hasGlobalUnnamedAddr()) | |||
734 | return false; | |||
735 | ||||
736 | // We should only see linkages supported by aliases here | |||
737 | assert(F->hasLocalLinkage() || F->hasExternalLinkage()(static_cast <bool> (F->hasLocalLinkage() || F->hasExternalLinkage () || F->hasWeakLinkage() || F->hasLinkOnceLinkage()) ? void (0) : __assert_fail ("F->hasLocalLinkage() || F->hasExternalLinkage() || F->hasWeakLinkage() || F->hasLinkOnceLinkage()" , "llvm/lib/Transforms/IPO/MergeFunctions.cpp", 738, __extension__ __PRETTY_FUNCTION__)) | |||
738 | || F->hasWeakLinkage() || F->hasLinkOnceLinkage())(static_cast <bool> (F->hasLocalLinkage() || F->hasExternalLinkage () || F->hasWeakLinkage() || F->hasLinkOnceLinkage()) ? void (0) : __assert_fail ("F->hasLocalLinkage() || F->hasExternalLinkage() || F->hasWeakLinkage() || F->hasLinkOnceLinkage()" , "llvm/lib/Transforms/IPO/MergeFunctions.cpp", 738, __extension__ __PRETTY_FUNCTION__)); | |||
739 | return true; | |||
740 | } | |||
741 | ||||
742 | // Replace G with an alias to F (deleting function G) | |||
743 | void MergeFunctions::writeAlias(Function *F, Function *G) { | |||
744 | Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType()); | |||
745 | PointerType *PtrType = G->getType(); | |||
746 | auto *GA = GlobalAlias::create(G->getValueType(), PtrType->getAddressSpace(), | |||
747 | G->getLinkage(), "", BitcastF, G->getParent()); | |||
748 | ||||
749 | const MaybeAlign FAlign = F->getAlign(); | |||
750 | const MaybeAlign GAlign = G->getAlign(); | |||
751 | if (FAlign || GAlign) | |||
752 | F->setAlignment(std::max(FAlign.valueOrOne(), GAlign.valueOrOne())); | |||
753 | else | |||
754 | F->setAlignment(std::nullopt); | |||
755 | GA->takeName(G); | |||
756 | GA->setVisibility(G->getVisibility()); | |||
757 | GA->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); | |||
758 | ||||
759 | removeUsers(G); | |||
760 | G->replaceAllUsesWith(GA); | |||
761 | G->eraseFromParent(); | |||
762 | ||||
763 | LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "writeAlias: " << GA-> getName() << '\n'; } } while (false); | |||
764 | ++NumAliasesWritten; | |||
765 | } | |||
766 | ||||
767 | // Replace G with an alias to F if possible, or a thunk to F if | |||
768 | // profitable. Returns false if neither is the case. | |||
769 | bool MergeFunctions::writeThunkOrAlias(Function *F, Function *G) { | |||
770 | if (canCreateAliasFor(G)) { | |||
771 | writeAlias(F, G); | |||
772 | return true; | |||
773 | } | |||
774 | if (canCreateThunkFor(F)) { | |||
775 | writeThunk(F, G); | |||
776 | return true; | |||
777 | } | |||
778 | return false; | |||
779 | } | |||
780 | ||||
781 | // Merge two equivalent functions. Upon completion, Function G is deleted. | |||
782 | void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) { | |||
783 | if (F->isInterposable()) { | |||
784 | assert(G->isInterposable())(static_cast <bool> (G->isInterposable()) ? void (0) : __assert_fail ("G->isInterposable()", "llvm/lib/Transforms/IPO/MergeFunctions.cpp" , 784, __extension__ __PRETTY_FUNCTION__)); | |||
785 | ||||
786 | // Both writeThunkOrAlias() calls below must succeed, either because we can | |||
787 | // create aliases for G and NewF, or because a thunk for F is profitable. | |||
788 | // F here has the same signature as NewF below, so that's what we check. | |||
789 | if (!canCreateThunkFor(F) && | |||
790 | (!canCreateAliasFor(F) || !canCreateAliasFor(G))) | |||
791 | return; | |||
792 | ||||
793 | // Make them both thunks to the same internal function. | |||
794 | Function *NewF = Function::Create(F->getFunctionType(), F->getLinkage(), | |||
795 | F->getAddressSpace(), "", F->getParent()); | |||
796 | NewF->copyAttributesFrom(F); | |||
797 | NewF->takeName(F); | |||
798 | removeUsers(F); | |||
799 | F->replaceAllUsesWith(NewF); | |||
800 | ||||
801 | // We collect alignment before writeThunkOrAlias that overwrites NewF and | |||
802 | // G's content. | |||
803 | const MaybeAlign NewFAlign = NewF->getAlign(); | |||
804 | const MaybeAlign GAlign = G->getAlign(); | |||
805 | ||||
806 | writeThunkOrAlias(F, G); | |||
807 | writeThunkOrAlias(F, NewF); | |||
808 | ||||
809 | if (NewFAlign || GAlign) | |||
810 | F->setAlignment(std::max(NewFAlign.valueOrOne(), GAlign.valueOrOne())); | |||
811 | else | |||
812 | F->setAlignment(std::nullopt); | |||
813 | F->setLinkage(GlobalValue::PrivateLinkage); | |||
814 | ++NumDoubleWeak; | |||
815 | ++NumFunctionsMerged; | |||
816 | } else { | |||
817 | // For better debugability, under MergeFunctionsPDI, we do not modify G's | |||
818 | // call sites to point to F even when within the same translation unit. | |||
819 | if (!G->isInterposable() && !MergeFunctionsPDI) { | |||
820 | // Functions referred to by llvm.used/llvm.compiler.used are special: | |||
821 | // there are uses of the symbol name that are not visible to LLVM, | |||
822 | // usually from inline asm. | |||
823 | if (G->hasGlobalUnnamedAddr() && !Used.contains(G)) { | |||
824 | // G might have been a key in our GlobalNumberState, and it's illegal | |||
825 | // to replace a key in ValueMap<GlobalValue *> with a non-global. | |||
826 | GlobalNumbers.erase(G); | |||
827 | // If G's address is not significant, replace it entirely. | |||
828 | Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType()); | |||
829 | removeUsers(G); | |||
830 | G->replaceAllUsesWith(BitcastF); | |||
831 | } else { | |||
832 | // Redirect direct callers of G to F. (See note on MergeFunctionsPDI | |||
833 | // above). | |||
834 | replaceDirectCallers(G, F); | |||
835 | } | |||
836 | } | |||
837 | ||||
838 | // If G was internal then we may have replaced all uses of G with F. If so, | |||
839 | // stop here and delete G. There's no need for a thunk. (See note on | |||
840 | // MergeFunctionsPDI above). | |||
841 | if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) { | |||
842 | G->eraseFromParent(); | |||
843 | ++NumFunctionsMerged; | |||
844 | return; | |||
845 | } | |||
846 | ||||
847 | if (writeThunkOrAlias(F, G)) { | |||
848 | ++NumFunctionsMerged; | |||
849 | } | |||
850 | } | |||
851 | } | |||
852 | ||||
853 | /// Replace function F by function G. | |||
854 | void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN, | |||
855 | Function *G) { | |||
856 | Function *F = FN.getFunc(); | |||
857 | assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&(static_cast <bool> (FunctionComparator(F, G, &GlobalNumbers ).compare() == 0 && "The two functions must be equal" ) ? void (0) : __assert_fail ("FunctionComparator(F, G, &GlobalNumbers).compare() == 0 && \"The two functions must be equal\"" , "llvm/lib/Transforms/IPO/MergeFunctions.cpp", 858, __extension__ __PRETTY_FUNCTION__)) | |||
858 | "The two functions must be equal")(static_cast <bool> (FunctionComparator(F, G, &GlobalNumbers ).compare() == 0 && "The two functions must be equal" ) ? void (0) : __assert_fail ("FunctionComparator(F, G, &GlobalNumbers).compare() == 0 && \"The two functions must be equal\"" , "llvm/lib/Transforms/IPO/MergeFunctions.cpp", 858, __extension__ __PRETTY_FUNCTION__)); | |||
859 | ||||
860 | auto I = FNodesInTree.find(F); | |||
861 | assert(I != FNodesInTree.end() && "F should be in FNodesInTree")(static_cast <bool> (I != FNodesInTree.end() && "F should be in FNodesInTree") ? void (0) : __assert_fail ("I != FNodesInTree.end() && \"F should be in FNodesInTree\"" , "llvm/lib/Transforms/IPO/MergeFunctions.cpp", 861, __extension__ __PRETTY_FUNCTION__)); | |||
862 | assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G")(static_cast <bool> (FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G") ? void (0) : __assert_fail ("FNodesInTree.count(G) == 0 && \"FNodesInTree should not contain G\"" , "llvm/lib/Transforms/IPO/MergeFunctions.cpp", 862, __extension__ __PRETTY_FUNCTION__)); | |||
863 | ||||
864 | FnTreeType::iterator IterToFNInFnTree = I->second; | |||
865 | assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.")(static_cast <bool> (&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.") ? void (0) : __assert_fail ("&(*IterToFNInFnTree) == &FN && \"F should map to FN in FNodesInTree.\"" , "llvm/lib/Transforms/IPO/MergeFunctions.cpp", 865, __extension__ __PRETTY_FUNCTION__)); | |||
866 | // Remove F -> FN and insert G -> FN | |||
867 | FNodesInTree.erase(I); | |||
868 | FNodesInTree.insert({G, IterToFNInFnTree}); | |||
869 | // Replace F with G in FN, which is stored inside the FnTree. | |||
870 | FN.replaceBy(G); | |||
871 | } | |||
872 | ||||
873 | // Ordering for functions that are equal under FunctionComparator | |||
874 | static bool isFuncOrderCorrect(const Function *F, const Function *G) { | |||
875 | if (F->isInterposable() != G->isInterposable()) { | |||
876 | // Strong before weak, because the weak function may call the strong | |||
877 | // one, but not the other way around. | |||
878 | return !F->isInterposable(); | |||
879 | } | |||
880 | if (F->hasLocalLinkage() != G->hasLocalLinkage()) { | |||
881 | // External before local, because we definitely have to keep the external | |||
882 | // function, but may be able to drop the local one. | |||
883 | return !F->hasLocalLinkage(); | |||
884 | } | |||
885 | // Impose a total order (by name) on the replacement of functions. This is | |||
886 | // important when operating on more than one module independently to prevent | |||
887 | // cycles of thunks calling each other when the modules are linked together. | |||
888 | return F->getName() <= G->getName(); | |||
889 | } | |||
890 | ||||
891 | // Insert a ComparableFunction into the FnTree, or merge it away if equal to one | |||
892 | // that was already inserted. | |||
893 | bool MergeFunctions::insert(Function *NewFunction) { | |||
894 | std::pair<FnTreeType::iterator, bool> Result = | |||
895 | FnTree.insert(FunctionNode(NewFunction)); | |||
896 | ||||
897 | if (Result.second) { | |||
898 | assert(FNodesInTree.count(NewFunction) == 0)(static_cast <bool> (FNodesInTree.count(NewFunction) == 0) ? void (0) : __assert_fail ("FNodesInTree.count(NewFunction) == 0" , "llvm/lib/Transforms/IPO/MergeFunctions.cpp", 898, __extension__ __PRETTY_FUNCTION__)); | |||
899 | FNodesInTree.insert({NewFunction, Result.first}); | |||
900 | LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "Inserting as unique: " << NewFunction->getName() << '\n'; } } while (false) | |||
901 | << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "Inserting as unique: " << NewFunction->getName() << '\n'; } } while (false); | |||
902 | return false; | |||
903 | } | |||
904 | ||||
905 | const FunctionNode &OldF = *Result.first; | |||
906 | ||||
907 | if (!isFuncOrderCorrect(OldF.getFunc(), NewFunction)) { | |||
908 | // Swap the two functions. | |||
909 | Function *F = OldF.getFunc(); | |||
910 | replaceFunctionInTree(*Result.first, NewFunction); | |||
911 | NewFunction = F; | |||
912 | assert(OldF.getFunc() != F && "Must have swapped the functions.")(static_cast <bool> (OldF.getFunc() != F && "Must have swapped the functions." ) ? void (0) : __assert_fail ("OldF.getFunc() != F && \"Must have swapped the functions.\"" , "llvm/lib/Transforms/IPO/MergeFunctions.cpp", 912, __extension__ __PRETTY_FUNCTION__)); | |||
913 | } | |||
914 | ||||
915 | LLVM_DEBUG(dbgs() << " " << OldF.getFunc()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " " << OldF.getFunc() ->getName() << " == " << NewFunction->getName () << '\n'; } } while (false) | |||
916 | << " == " << NewFunction->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << " " << OldF.getFunc() ->getName() << " == " << NewFunction->getName () << '\n'; } } while (false); | |||
917 | ||||
918 | Function *DeleteF = NewFunction; | |||
919 | mergeTwoFunctions(OldF.getFunc(), DeleteF); | |||
920 | return true; | |||
921 | } | |||
922 | ||||
923 | // Remove a function from FnTree. If it was already in FnTree, add | |||
924 | // it to Deferred so that we'll look at it in the next round. | |||
925 | void MergeFunctions::remove(Function *F) { | |||
926 | auto I = FNodesInTree.find(F); | |||
927 | if (I != FNodesInTree.end()) { | |||
928 | LLVM_DEBUG(dbgs() << "Deferred " << F->getName() << ".\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("mergefunc")) { dbgs() << "Deferred " << F->getName () << ".\n"; } } while (false); | |||
929 | FnTree.erase(I->second); | |||
930 | // I->second has been invalidated, remove it from the FNodesInTree map to | |||
931 | // preserve the invariant. | |||
932 | FNodesInTree.erase(I); | |||
933 | Deferred.emplace_back(F); | |||
934 | } | |||
935 | } | |||
936 | ||||
937 | // For each instruction used by the value, remove() the function that contains | |||
938 | // the instruction. This should happen right before a call to RAUW. | |||
939 | void MergeFunctions::removeUsers(Value *V) { | |||
940 | for (User *U : V->users()) | |||
941 | if (auto *I = dyn_cast<Instruction>(U)) | |||
942 | remove(I->getFunction()); | |||
943 | } |