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/StructuralHash.h" |
111 | #include "llvm/IR/Type.h" |
112 | #include "llvm/IR/Use.h" |
113 | #include "llvm/IR/User.h" |
114 | #include "llvm/IR/Value.h" |
115 | #include "llvm/IR/ValueHandle.h" |
116 | #include "llvm/Support/Casting.h" |
117 | #include "llvm/Support/CommandLine.h" |
118 | #include "llvm/Support/Debug.h" |
119 | #include "llvm/Support/raw_ostream.h" |
120 | #include "llvm/Transforms/IPO.h" |
121 | #include "llvm/Transforms/Utils/FunctionComparator.h" |
122 | #include "llvm/Transforms/Utils/ModuleUtils.h" |
123 | #include <algorithm> |
124 | #include <cassert> |
125 | #include <iterator> |
126 | #include <set> |
127 | #include <utility> |
128 | #include <vector> |
129 | |
130 | using namespace llvm; |
131 | |
132 | #define DEBUG_TYPE "mergefunc" |
133 | |
134 | STATISTIC(NumFunctionsMerged, "Number of functions merged" ); |
135 | STATISTIC(NumThunksWritten, "Number of thunks generated" ); |
136 | STATISTIC(NumAliasesWritten, "Number of aliases generated" ); |
137 | STATISTIC(NumDoubleWeak, "Number of new functions created" ); |
138 | |
139 | static cl::opt<unsigned> NumFunctionsForVerificationCheck( |
140 | "mergefunc-verify" , |
141 | cl::desc("How many functions in a module could be used for " |
142 | "MergeFunctions to pass a basic correctness check. " |
143 | "'0' disables this check. Works only with '-debug' key." ), |
144 | cl::init(Val: 0), cl::Hidden); |
145 | |
146 | // Under option -mergefunc-preserve-debug-info we: |
147 | // - Do not create a new function for a thunk. |
148 | // - Retain the debug info for a thunk's parameters (and associated |
149 | // instructions for the debug info) from the entry block. |
150 | // Note: -debug will display the algorithm at work. |
151 | // - Create debug-info for the call (to the shared implementation) made by |
152 | // a thunk and its return value. |
153 | // - Erase the rest of the function, retaining the (minimally sized) entry |
154 | // block to create a thunk. |
155 | // - Preserve a thunk's call site to point to the thunk even when both occur |
156 | // within the same translation unit, to aid debugability. Note that this |
157 | // behaviour differs from the underlying -mergefunc implementation which |
158 | // modifies the thunk's call site to point to the shared implementation |
159 | // when both occur within the same translation unit. |
160 | static cl::opt<bool> |
161 | MergeFunctionsPDI("mergefunc-preserve-debug-info" , cl::Hidden, |
162 | cl::init(Val: false), |
163 | cl::desc("Preserve debug info in thunk when mergefunc " |
164 | "transformations are made." )); |
165 | |
166 | static cl::opt<bool> |
167 | MergeFunctionsAliases("mergefunc-use-aliases" , cl::Hidden, |
168 | cl::init(Val: false), |
169 | cl::desc("Allow mergefunc to create aliases" )); |
170 | |
171 | namespace { |
172 | |
173 | class FunctionNode { |
174 | mutable AssertingVH<Function> F; |
175 | IRHash Hash; |
176 | |
177 | public: |
178 | // Note the hash is recalculated potentially multiple times, but it is cheap. |
179 | FunctionNode(Function *F) : F(F), Hash(StructuralHash(F: *F)) {} |
180 | |
181 | Function *getFunc() const { return F; } |
182 | IRHash 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 | /// \param PDPVUnrelatedWL The equivalent non-intrinsic debug records. |
260 | void filterInstsUnrelatedToPDI(BasicBlock *GEntryBlock, |
261 | std::vector<Instruction *> &PDIUnrelatedWL, |
262 | std::vector<DPValue *> &PDPVUnrelatedWL); |
263 | |
264 | /// Erase the rest of the CFG (i.e. barring the entry block). |
265 | void eraseTail(Function *G); |
266 | |
267 | /// Erase the instructions in PDIUnrelatedWL as they are unrelated to the |
268 | /// parameter debug info, from the entry block. |
269 | /// \param PDPVUnrelatedWL contains the equivalent set of non-instruction |
270 | /// debug-info records. |
271 | void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL, |
272 | std::vector<DPValue *> &PDPVUnrelatedWL); |
273 | |
274 | /// Replace G with a simple tail call to bitcast(F). Also (unless |
275 | /// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F), |
276 | /// delete G. |
277 | void writeThunk(Function *F, Function *G); |
278 | |
279 | // Replace G with an alias to F (deleting function G) |
280 | void writeAlias(Function *F, Function *G); |
281 | |
282 | // Replace G with an alias to F if possible, or a thunk to F if possible. |
283 | // Returns false if neither is the case. |
284 | bool writeThunkOrAlias(Function *F, Function *G); |
285 | |
286 | /// Replace function F with function G in the function tree. |
287 | void replaceFunctionInTree(const FunctionNode &FN, Function *G); |
288 | |
289 | /// The set of all distinct functions. Use the insert() and remove() methods |
290 | /// to modify it. The map allows efficient lookup and deferring of Functions. |
291 | FnTreeType FnTree; |
292 | |
293 | // Map functions to the iterators of the FunctionNode which contains them |
294 | // in the FnTree. This must be updated carefully whenever the FnTree is |
295 | // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid |
296 | // dangling iterators into FnTree. The invariant that preserves this is that |
297 | // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree. |
298 | DenseMap<AssertingVH<Function>, FnTreeType::iterator> FNodesInTree; |
299 | }; |
300 | } // end anonymous namespace |
301 | |
302 | PreservedAnalyses MergeFunctionsPass::run(Module &M, |
303 | ModuleAnalysisManager &AM) { |
304 | MergeFunctions MF; |
305 | if (!MF.runOnModule(M)) |
306 | return PreservedAnalyses::all(); |
307 | return PreservedAnalyses::none(); |
308 | } |
309 | |
310 | #ifndef NDEBUG |
311 | bool MergeFunctions::doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist) { |
312 | if (const unsigned Max = NumFunctionsForVerificationCheck) { |
313 | unsigned TripleNumber = 0; |
314 | bool Valid = true; |
315 | |
316 | dbgs() << "MERGEFUNC-VERIFY: Started for first " << Max << " functions.\n" ; |
317 | |
318 | unsigned i = 0; |
319 | for (std::vector<WeakTrackingVH>::iterator I = Worklist.begin(), |
320 | E = Worklist.end(); |
321 | I != E && i < Max; ++I, ++i) { |
322 | unsigned j = i; |
323 | for (std::vector<WeakTrackingVH>::iterator J = I; J != E && j < Max; |
324 | ++J, ++j) { |
325 | Function *F1 = cast<Function>(Val&: *I); |
326 | Function *F2 = cast<Function>(Val&: *J); |
327 | int Res1 = FunctionComparator(F1, F2, &GlobalNumbers).compare(); |
328 | int Res2 = FunctionComparator(F2, F1, &GlobalNumbers).compare(); |
329 | |
330 | // If F1 <= F2, then F2 >= F1, otherwise report failure. |
331 | if (Res1 != -Res2) { |
332 | dbgs() << "MERGEFUNC-VERIFY: Non-symmetric; triple: " << TripleNumber |
333 | << "\n" ; |
334 | dbgs() << *F1 << '\n' << *F2 << '\n'; |
335 | Valid = false; |
336 | } |
337 | |
338 | if (Res1 == 0) |
339 | continue; |
340 | |
341 | unsigned k = j; |
342 | for (std::vector<WeakTrackingVH>::iterator K = J; K != E && k < Max; |
343 | ++k, ++K, ++TripleNumber) { |
344 | if (K == J) |
345 | continue; |
346 | |
347 | Function *F3 = cast<Function>(Val&: *K); |
348 | int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare(); |
349 | int Res4 = FunctionComparator(F2, F3, &GlobalNumbers).compare(); |
350 | |
351 | bool Transitive = true; |
352 | |
353 | if (Res1 != 0 && Res1 == Res4) { |
354 | // F1 > F2, F2 > F3 => F1 > F3 |
355 | Transitive = Res3 == Res1; |
356 | } else if (Res3 != 0 && Res3 == -Res4) { |
357 | // F1 > F3, F3 > F2 => F1 > F2 |
358 | Transitive = Res3 == Res1; |
359 | } else if (Res4 != 0 && -Res3 == Res4) { |
360 | // F2 > F3, F3 > F1 => F2 > F1 |
361 | Transitive = Res4 == -Res1; |
362 | } |
363 | |
364 | if (!Transitive) { |
365 | dbgs() << "MERGEFUNC-VERIFY: Non-transitive; triple: " |
366 | << TripleNumber << "\n" ; |
367 | dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", " |
368 | << Res4 << "\n" ; |
369 | dbgs() << *F1 << '\n' << *F2 << '\n' << *F3 << '\n'; |
370 | Valid = false; |
371 | } |
372 | } |
373 | } |
374 | } |
375 | |
376 | dbgs() << "MERGEFUNC-VERIFY: " << (Valid ? "Passed." : "Failed." ) << "\n" ; |
377 | return Valid; |
378 | } |
379 | return true; |
380 | } |
381 | #endif |
382 | |
383 | /// Check whether \p F has an intrinsic which references |
384 | /// distinct metadata as an operand. The most common |
385 | /// instance of this would be CFI checks for function-local types. |
386 | static bool hasDistinctMetadataIntrinsic(const Function &F) { |
387 | for (const BasicBlock &BB : F) { |
388 | for (const Instruction &I : BB.instructionsWithoutDebug()) { |
389 | if (!isa<IntrinsicInst>(Val: &I)) |
390 | continue; |
391 | |
392 | for (Value *Op : I.operands()) { |
393 | auto *MDL = dyn_cast<MetadataAsValue>(Val: Op); |
394 | if (!MDL) |
395 | continue; |
396 | if (MDNode *N = dyn_cast<MDNode>(Val: MDL->getMetadata())) |
397 | if (N->isDistinct()) |
398 | return true; |
399 | } |
400 | } |
401 | } |
402 | return false; |
403 | } |
404 | |
405 | /// Check whether \p F is eligible for function merging. |
406 | static bool isEligibleForMerging(Function &F) { |
407 | return !F.isDeclaration() && !F.hasAvailableExternallyLinkage() && |
408 | !hasDistinctMetadataIntrinsic(F); |
409 | } |
410 | |
411 | bool MergeFunctions::runOnModule(Module &M) { |
412 | bool Changed = false; |
413 | |
414 | SmallVector<GlobalValue *, 4> UsedV; |
415 | collectUsedGlobalVariables(M, Vec&: UsedV, /*CompilerUsed=*/false); |
416 | collectUsedGlobalVariables(M, Vec&: UsedV, /*CompilerUsed=*/true); |
417 | Used.insert(I: UsedV.begin(), E: UsedV.end()); |
418 | |
419 | // All functions in the module, ordered by hash. Functions with a unique |
420 | // hash value are easily eliminated. |
421 | std::vector<std::pair<IRHash, Function *>> HashedFuncs; |
422 | for (Function &Func : M) { |
423 | if (isEligibleForMerging(F&: Func)) { |
424 | HashedFuncs.push_back(x: {StructuralHash(F: Func), &Func}); |
425 | } |
426 | } |
427 | |
428 | llvm::stable_sort(Range&: HashedFuncs, C: less_first()); |
429 | |
430 | auto S = HashedFuncs.begin(); |
431 | for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) { |
432 | // If the hash value matches the previous value or the next one, we must |
433 | // consider merging it. Otherwise it is dropped and never considered again. |
434 | if ((I != S && std::prev(x: I)->first == I->first) || |
435 | (std::next(x: I) != IE && std::next(x: I)->first == I->first) ) { |
436 | Deferred.push_back(x: WeakTrackingVH(I->second)); |
437 | } |
438 | } |
439 | |
440 | do { |
441 | std::vector<WeakTrackingVH> Worklist; |
442 | Deferred.swap(x&: Worklist); |
443 | |
444 | LLVM_DEBUG(doFunctionalCheck(Worklist)); |
445 | |
446 | LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n'); |
447 | LLVM_DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n'); |
448 | |
449 | // Insert functions and merge them. |
450 | for (WeakTrackingVH &I : Worklist) { |
451 | if (!I) |
452 | continue; |
453 | Function *F = cast<Function>(Val&: I); |
454 | if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) { |
455 | Changed |= insert(NewFunction: F); |
456 | } |
457 | } |
458 | LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n'); |
459 | } while (!Deferred.empty()); |
460 | |
461 | FnTree.clear(); |
462 | FNodesInTree.clear(); |
463 | GlobalNumbers.clear(); |
464 | Used.clear(); |
465 | |
466 | return Changed; |
467 | } |
468 | |
469 | // Replace direct callers of Old with New. |
470 | void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) { |
471 | for (Use &U : llvm::make_early_inc_range(Range: Old->uses())) { |
472 | CallBase *CB = dyn_cast<CallBase>(Val: U.getUser()); |
473 | if (CB && CB->isCallee(U: &U)) { |
474 | // Do not copy attributes from the called function to the call-site. |
475 | // Function comparison ensures that the attributes are the same up to |
476 | // type congruences in byval(), in which case we need to keep the byval |
477 | // type of the call-site, not the callee function. |
478 | remove(F: CB->getFunction()); |
479 | U.set(New); |
480 | } |
481 | } |
482 | } |
483 | |
484 | // Helper for writeThunk, |
485 | // Selects proper bitcast operation, |
486 | // but a bit simpler then CastInst::getCastOpcode. |
487 | static Value *createCast(IRBuilder<> &Builder, Value *V, Type *DestTy) { |
488 | Type *SrcTy = V->getType(); |
489 | if (SrcTy->isStructTy()) { |
490 | assert(DestTy->isStructTy()); |
491 | assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements()); |
492 | Value *Result = PoisonValue::get(T: DestTy); |
493 | for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) { |
494 | Value *Element = |
495 | createCast(Builder, V: Builder.CreateExtractValue(Agg: V, Idxs: ArrayRef(I)), |
496 | DestTy: DestTy->getStructElementType(N: I)); |
497 | |
498 | Result = Builder.CreateInsertValue(Agg: Result, Val: Element, Idxs: ArrayRef(I)); |
499 | } |
500 | return Result; |
501 | } |
502 | assert(!DestTy->isStructTy()); |
503 | if (SrcTy->isIntegerTy() && DestTy->isPointerTy()) |
504 | return Builder.CreateIntToPtr(V, DestTy); |
505 | else if (SrcTy->isPointerTy() && DestTy->isIntegerTy()) |
506 | return Builder.CreatePtrToInt(V, DestTy); |
507 | else |
508 | return Builder.CreateBitCast(V, DestTy); |
509 | } |
510 | |
511 | // Erase the instructions in PDIUnrelatedWL as they are unrelated to the |
512 | // parameter debug info, from the entry block. |
513 | void MergeFunctions::eraseInstsUnrelatedToPDI( |
514 | std::vector<Instruction *> &PDIUnrelatedWL, |
515 | std::vector<DPValue *> &PDPVUnrelatedWL) { |
516 | LLVM_DEBUG( |
517 | dbgs() << " Erasing instructions (in reverse order of appearance in " |
518 | "entry block) unrelated to parameter debug info from entry " |
519 | "block: {\n" ); |
520 | while (!PDIUnrelatedWL.empty()) { |
521 | Instruction *I = PDIUnrelatedWL.back(); |
522 | LLVM_DEBUG(dbgs() << " Deleting Instruction: " ); |
523 | LLVM_DEBUG(I->print(dbgs())); |
524 | LLVM_DEBUG(dbgs() << "\n" ); |
525 | I->eraseFromParent(); |
526 | PDIUnrelatedWL.pop_back(); |
527 | } |
528 | |
529 | while (!PDPVUnrelatedWL.empty()) { |
530 | DPValue *DPV = PDPVUnrelatedWL.back(); |
531 | LLVM_DEBUG(dbgs() << " Deleting DPValue " ); |
532 | LLVM_DEBUG(DPV->print(dbgs())); |
533 | LLVM_DEBUG(dbgs() << "\n" ); |
534 | DPV->eraseFromParent(); |
535 | PDPVUnrelatedWL.pop_back(); |
536 | } |
537 | |
538 | LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter " |
539 | "debug info from entry block. \n" ); |
540 | } |
541 | |
542 | // Reduce G to its entry block. |
543 | void MergeFunctions::eraseTail(Function *G) { |
544 | std::vector<BasicBlock *> WorklistBB; |
545 | for (BasicBlock &BB : drop_begin(RangeOrContainer&: *G)) { |
546 | BB.dropAllReferences(); |
547 | WorklistBB.push_back(x: &BB); |
548 | } |
549 | while (!WorklistBB.empty()) { |
550 | BasicBlock *BB = WorklistBB.back(); |
551 | BB->eraseFromParent(); |
552 | WorklistBB.pop_back(); |
553 | } |
554 | } |
555 | |
556 | // We are interested in the following instructions from the entry block as being |
557 | // related to parameter debug info: |
558 | // - @llvm.dbg.declare |
559 | // - stores from the incoming parameters to locations on the stack-frame |
560 | // - allocas that create these locations on the stack-frame |
561 | // - @llvm.dbg.value |
562 | // - the entry block's terminator |
563 | // The rest are unrelated to debug info for the parameters; fill up |
564 | // PDIUnrelatedWL with such instructions. |
565 | void MergeFunctions::filterInstsUnrelatedToPDI( |
566 | BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL, |
567 | std::vector<DPValue *> &PDPVUnrelatedWL) { |
568 | std::set<Instruction *> PDIRelated; |
569 | std::set<DPValue *> PDPVRelated; |
570 | |
571 | // Work out whether a dbg.value intrinsic or an equivalent DPValue is a |
572 | // parameter to be preserved. |
573 | auto ExamineDbgValue = [](auto *DbgVal, auto &Container) { |
574 | LLVM_DEBUG(dbgs() << " Deciding: " ); |
575 | LLVM_DEBUG(DbgVal->print(dbgs())); |
576 | LLVM_DEBUG(dbgs() << "\n" ); |
577 | DILocalVariable *DILocVar = DbgVal->getVariable(); |
578 | if (DILocVar->isParameter()) { |
579 | LLVM_DEBUG(dbgs() << " Include (parameter): " ); |
580 | LLVM_DEBUG(DbgVal->print(dbgs())); |
581 | LLVM_DEBUG(dbgs() << "\n" ); |
582 | Container.insert(DbgVal); |
583 | } else { |
584 | LLVM_DEBUG(dbgs() << " Delete (!parameter): " ); |
585 | LLVM_DEBUG(DbgVal->print(dbgs())); |
586 | LLVM_DEBUG(dbgs() << "\n" ); |
587 | } |
588 | }; |
589 | |
590 | auto ExamineDbgDeclare = [&PDIRelated](auto *DbgDecl, auto &Container) { |
591 | LLVM_DEBUG(dbgs() << " Deciding: " ); |
592 | LLVM_DEBUG(DbgDecl->print(dbgs())); |
593 | LLVM_DEBUG(dbgs() << "\n" ); |
594 | DILocalVariable *DILocVar = DbgDecl->getVariable(); |
595 | if (DILocVar->isParameter()) { |
596 | LLVM_DEBUG(dbgs() << " Parameter: " ); |
597 | LLVM_DEBUG(DILocVar->print(dbgs())); |
598 | AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DbgDecl->getAddress()); |
599 | if (AI) { |
600 | LLVM_DEBUG(dbgs() << " Processing alloca users: " ); |
601 | LLVM_DEBUG(dbgs() << "\n" ); |
602 | for (User *U : AI->users()) { |
603 | if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) { |
604 | if (Value *Arg = SI->getValueOperand()) { |
605 | if (isa<Argument>(Val: Arg)) { |
606 | LLVM_DEBUG(dbgs() << " Include: " ); |
607 | LLVM_DEBUG(AI->print(dbgs())); |
608 | LLVM_DEBUG(dbgs() << "\n" ); |
609 | PDIRelated.insert(x: AI); |
610 | LLVM_DEBUG(dbgs() << " Include (parameter): " ); |
611 | LLVM_DEBUG(SI->print(dbgs())); |
612 | LLVM_DEBUG(dbgs() << "\n" ); |
613 | PDIRelated.insert(x: SI); |
614 | LLVM_DEBUG(dbgs() << " Include: " ); |
615 | LLVM_DEBUG(DbgDecl->print(dbgs())); |
616 | LLVM_DEBUG(dbgs() << "\n" ); |
617 | Container.insert(DbgDecl); |
618 | } else { |
619 | LLVM_DEBUG(dbgs() << " Delete (!parameter): " ); |
620 | LLVM_DEBUG(SI->print(dbgs())); |
621 | LLVM_DEBUG(dbgs() << "\n" ); |
622 | } |
623 | } |
624 | } else { |
625 | LLVM_DEBUG(dbgs() << " Defer: " ); |
626 | LLVM_DEBUG(U->print(dbgs())); |
627 | LLVM_DEBUG(dbgs() << "\n" ); |
628 | } |
629 | } |
630 | } else { |
631 | LLVM_DEBUG(dbgs() << " Delete (alloca NULL): " ); |
632 | LLVM_DEBUG(DbgDecl->print(dbgs())); |
633 | LLVM_DEBUG(dbgs() << "\n" ); |
634 | } |
635 | } else { |
636 | LLVM_DEBUG(dbgs() << " Delete (!parameter): " ); |
637 | LLVM_DEBUG(DbgDecl->print(dbgs())); |
638 | LLVM_DEBUG(dbgs() << "\n" ); |
639 | } |
640 | }; |
641 | |
642 | for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end(); |
643 | BI != BIE; ++BI) { |
644 | // Examine DPValues as they happen "before" the instruction. Are they |
645 | // connected to parameters? |
646 | for (DPValue &DPV : BI->getDbgValueRange()) { |
647 | if (DPV.isDbgValue() || DPV.isDbgAssign()) { |
648 | ExamineDbgValue(&DPV, PDPVRelated); |
649 | } else { |
650 | assert(DPV.isDbgDeclare()); |
651 | ExamineDbgDeclare(&DPV, PDPVRelated); |
652 | } |
653 | } |
654 | |
655 | if (auto *DVI = dyn_cast<DbgValueInst>(Val: &*BI)) { |
656 | ExamineDbgValue(DVI, PDIRelated); |
657 | } else if (auto *DDI = dyn_cast<DbgDeclareInst>(Val: &*BI)) { |
658 | ExamineDbgDeclare(DDI, PDIRelated); |
659 | } else if (BI->isTerminator() && &*BI == GEntryBlock->getTerminator()) { |
660 | LLVM_DEBUG(dbgs() << " Will Include Terminator: " ); |
661 | LLVM_DEBUG(BI->print(dbgs())); |
662 | LLVM_DEBUG(dbgs() << "\n" ); |
663 | PDIRelated.insert(x: &*BI); |
664 | } else { |
665 | LLVM_DEBUG(dbgs() << " Defer: " ); |
666 | LLVM_DEBUG(BI->print(dbgs())); |
667 | LLVM_DEBUG(dbgs() << "\n" ); |
668 | } |
669 | } |
670 | LLVM_DEBUG( |
671 | dbgs() |
672 | << " Report parameter debug info related/related instructions: {\n" ); |
673 | |
674 | auto IsPDIRelated = [](auto *Rec, auto &Container, auto &UnrelatedCont) { |
675 | if (Container.find(Rec) == Container.end()) { |
676 | LLVM_DEBUG(dbgs() << " !PDIRelated: " ); |
677 | LLVM_DEBUG(Rec->print(dbgs())); |
678 | LLVM_DEBUG(dbgs() << "\n" ); |
679 | UnrelatedCont.push_back(Rec); |
680 | } else { |
681 | LLVM_DEBUG(dbgs() << " PDIRelated: " ); |
682 | LLVM_DEBUG(Rec->print(dbgs())); |
683 | LLVM_DEBUG(dbgs() << "\n" ); |
684 | } |
685 | }; |
686 | |
687 | // Collect the set of unrelated instructions and debug records. |
688 | for (Instruction &I : *GEntryBlock) { |
689 | for (auto &DPV : I.getDbgValueRange()) |
690 | IsPDIRelated(&DPV, PDPVRelated, PDPVUnrelatedWL); |
691 | IsPDIRelated(&I, PDIRelated, PDIUnrelatedWL); |
692 | } |
693 | LLVM_DEBUG(dbgs() << " }\n" ); |
694 | } |
695 | |
696 | /// Whether this function may be replaced by a forwarding thunk. |
697 | static bool canCreateThunkFor(Function *F) { |
698 | if (F->isVarArg()) |
699 | return false; |
700 | |
701 | // Don't merge tiny functions using a thunk, since it can just end up |
702 | // making the function larger. |
703 | if (F->size() == 1) { |
704 | if (F->front().sizeWithoutDebug() < 2) { |
705 | LLVM_DEBUG(dbgs() << "canCreateThunkFor: " << F->getName() |
706 | << " is too small to bother creating a thunk for\n" ); |
707 | return false; |
708 | } |
709 | } |
710 | return true; |
711 | } |
712 | |
713 | /// Copy metadata from one function to another. |
714 | static void copyMetadataIfPresent(Function *From, Function *To, StringRef Key) { |
715 | if (MDNode *MD = From->getMetadata(Kind: Key)) { |
716 | To->setMetadata(Kind: Key, Node: MD); |
717 | } |
718 | } |
719 | |
720 | // Replace G with a simple tail call to bitcast(F). Also (unless |
721 | // MergeFunctionsPDI holds) replace direct uses of G with bitcast(F), |
722 | // delete G. Under MergeFunctionsPDI, we use G itself for creating |
723 | // the thunk as we preserve the debug info (and associated instructions) |
724 | // from G's entry block pertaining to G's incoming arguments which are |
725 | // passed on as corresponding arguments in the call that G makes to F. |
726 | // For better debugability, under MergeFunctionsPDI, we do not modify G's |
727 | // call sites to point to F even when within the same translation unit. |
728 | void MergeFunctions::writeThunk(Function *F, Function *G) { |
729 | BasicBlock *GEntryBlock = nullptr; |
730 | std::vector<Instruction *> PDIUnrelatedWL; |
731 | std::vector<DPValue *> PDPVUnrelatedWL; |
732 | BasicBlock *BB = nullptr; |
733 | Function *NewG = nullptr; |
734 | if (MergeFunctionsPDI) { |
735 | LLVM_DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new " |
736 | "function as thunk; retain original: " |
737 | << G->getName() << "()\n" ); |
738 | GEntryBlock = &G->getEntryBlock(); |
739 | LLVM_DEBUG( |
740 | dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related " |
741 | "debug info for " |
742 | << G->getName() << "() {\n" ); |
743 | filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL, PDPVUnrelatedWL); |
744 | GEntryBlock->getTerminator()->eraseFromParent(); |
745 | BB = GEntryBlock; |
746 | } else { |
747 | NewG = Function::Create(Ty: G->getFunctionType(), Linkage: G->getLinkage(), |
748 | AddrSpace: G->getAddressSpace(), N: "" , M: G->getParent()); |
749 | NewG->setComdat(G->getComdat()); |
750 | BB = BasicBlock::Create(Context&: F->getContext(), Name: "" , Parent: NewG); |
751 | } |
752 | |
753 | IRBuilder<> Builder(BB); |
754 | Function *H = MergeFunctionsPDI ? G : NewG; |
755 | SmallVector<Value *, 16> Args; |
756 | unsigned i = 0; |
757 | FunctionType *FFTy = F->getFunctionType(); |
758 | for (Argument &AI : H->args()) { |
759 | Args.push_back(Elt: createCast(Builder, V: &AI, DestTy: FFTy->getParamType(i))); |
760 | ++i; |
761 | } |
762 | |
763 | CallInst *CI = Builder.CreateCall(Callee: F, Args); |
764 | ReturnInst *RI = nullptr; |
765 | bool isSwiftTailCall = F->getCallingConv() == CallingConv::SwiftTail && |
766 | G->getCallingConv() == CallingConv::SwiftTail; |
767 | CI->setTailCallKind(isSwiftTailCall ? llvm::CallInst::TCK_MustTail |
768 | : llvm::CallInst::TCK_Tail); |
769 | CI->setCallingConv(F->getCallingConv()); |
770 | CI->setAttributes(F->getAttributes()); |
771 | if (H->getReturnType()->isVoidTy()) { |
772 | RI = Builder.CreateRetVoid(); |
773 | } else { |
774 | RI = Builder.CreateRet(V: createCast(Builder, V: CI, DestTy: H->getReturnType())); |
775 | } |
776 | |
777 | if (MergeFunctionsPDI) { |
778 | DISubprogram *DIS = G->getSubprogram(); |
779 | if (DIS) { |
780 | DebugLoc CIDbgLoc = |
781 | DILocation::get(Context&: DIS->getContext(), Line: DIS->getScopeLine(), Column: 0, Scope: DIS); |
782 | DebugLoc RIDbgLoc = |
783 | DILocation::get(Context&: DIS->getContext(), Line: DIS->getScopeLine(), Column: 0, Scope: DIS); |
784 | CI->setDebugLoc(CIDbgLoc); |
785 | RI->setDebugLoc(RIDbgLoc); |
786 | } else { |
787 | LLVM_DEBUG( |
788 | dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for " |
789 | << G->getName() << "()\n" ); |
790 | } |
791 | eraseTail(G); |
792 | eraseInstsUnrelatedToPDI(PDIUnrelatedWL, PDPVUnrelatedWL); |
793 | LLVM_DEBUG( |
794 | dbgs() << "} // End of parameter related debug info filtering for: " |
795 | << G->getName() << "()\n" ); |
796 | } else { |
797 | NewG->copyAttributesFrom(Src: G); |
798 | NewG->takeName(V: G); |
799 | // Ensure CFI type metadata is propagated to the new function. |
800 | copyMetadataIfPresent(From: G, To: NewG, Key: "type" ); |
801 | copyMetadataIfPresent(From: G, To: NewG, Key: "kcfi_type" ); |
802 | removeUsers(V: G); |
803 | G->replaceAllUsesWith(V: NewG); |
804 | G->eraseFromParent(); |
805 | } |
806 | |
807 | LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n'); |
808 | ++NumThunksWritten; |
809 | } |
810 | |
811 | // Whether this function may be replaced by an alias |
812 | static bool canCreateAliasFor(Function *F) { |
813 | if (!MergeFunctionsAliases || !F->hasGlobalUnnamedAddr()) |
814 | return false; |
815 | |
816 | // We should only see linkages supported by aliases here |
817 | assert(F->hasLocalLinkage() || F->hasExternalLinkage() |
818 | || F->hasWeakLinkage() || F->hasLinkOnceLinkage()); |
819 | return true; |
820 | } |
821 | |
822 | // Replace G with an alias to F (deleting function G) |
823 | void MergeFunctions::writeAlias(Function *F, Function *G) { |
824 | PointerType *PtrType = G->getType(); |
825 | auto *GA = GlobalAlias::create(Ty: G->getValueType(), AddressSpace: PtrType->getAddressSpace(), |
826 | Linkage: G->getLinkage(), Name: "" , Aliasee: F, Parent: G->getParent()); |
827 | |
828 | const MaybeAlign FAlign = F->getAlign(); |
829 | const MaybeAlign GAlign = G->getAlign(); |
830 | if (FAlign || GAlign) |
831 | F->setAlignment(std::max(a: FAlign.valueOrOne(), b: GAlign.valueOrOne())); |
832 | else |
833 | F->setAlignment(std::nullopt); |
834 | GA->takeName(V: G); |
835 | GA->setVisibility(G->getVisibility()); |
836 | GA->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); |
837 | |
838 | removeUsers(V: G); |
839 | G->replaceAllUsesWith(V: GA); |
840 | G->eraseFromParent(); |
841 | |
842 | LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n'); |
843 | ++NumAliasesWritten; |
844 | } |
845 | |
846 | // Replace G with an alias to F if possible, or a thunk to F if |
847 | // profitable. Returns false if neither is the case. |
848 | bool MergeFunctions::writeThunkOrAlias(Function *F, Function *G) { |
849 | if (canCreateAliasFor(F: G)) { |
850 | writeAlias(F, G); |
851 | return true; |
852 | } |
853 | if (canCreateThunkFor(F)) { |
854 | writeThunk(F, G); |
855 | return true; |
856 | } |
857 | return false; |
858 | } |
859 | |
860 | // Merge two equivalent functions. Upon completion, Function G is deleted. |
861 | void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) { |
862 | if (F->isInterposable()) { |
863 | assert(G->isInterposable()); |
864 | |
865 | // Both writeThunkOrAlias() calls below must succeed, either because we can |
866 | // create aliases for G and NewF, or because a thunk for F is profitable. |
867 | // F here has the same signature as NewF below, so that's what we check. |
868 | if (!canCreateThunkFor(F) && |
869 | (!canCreateAliasFor(F) || !canCreateAliasFor(F: G))) |
870 | return; |
871 | |
872 | // Make them both thunks to the same internal function. |
873 | Function *NewF = Function::Create(Ty: F->getFunctionType(), Linkage: F->getLinkage(), |
874 | AddrSpace: F->getAddressSpace(), N: "" , M: F->getParent()); |
875 | NewF->copyAttributesFrom(Src: F); |
876 | NewF->takeName(V: F); |
877 | // Ensure CFI type metadata is propagated to the new function. |
878 | copyMetadataIfPresent(From: F, To: NewF, Key: "type" ); |
879 | copyMetadataIfPresent(From: F, To: NewF, Key: "kcfi_type" ); |
880 | removeUsers(V: F); |
881 | F->replaceAllUsesWith(V: NewF); |
882 | |
883 | // We collect alignment before writeThunkOrAlias that overwrites NewF and |
884 | // G's content. |
885 | const MaybeAlign NewFAlign = NewF->getAlign(); |
886 | const MaybeAlign GAlign = G->getAlign(); |
887 | |
888 | writeThunkOrAlias(F, G); |
889 | writeThunkOrAlias(F, G: NewF); |
890 | |
891 | if (NewFAlign || GAlign) |
892 | F->setAlignment(std::max(a: NewFAlign.valueOrOne(), b: GAlign.valueOrOne())); |
893 | else |
894 | F->setAlignment(std::nullopt); |
895 | F->setLinkage(GlobalValue::PrivateLinkage); |
896 | ++NumDoubleWeak; |
897 | ++NumFunctionsMerged; |
898 | } else { |
899 | // For better debugability, under MergeFunctionsPDI, we do not modify G's |
900 | // call sites to point to F even when within the same translation unit. |
901 | if (!G->isInterposable() && !MergeFunctionsPDI) { |
902 | // Functions referred to by llvm.used/llvm.compiler.used are special: |
903 | // there are uses of the symbol name that are not visible to LLVM, |
904 | // usually from inline asm. |
905 | if (G->hasGlobalUnnamedAddr() && !Used.contains(Ptr: G)) { |
906 | // G might have been a key in our GlobalNumberState, and it's illegal |
907 | // to replace a key in ValueMap<GlobalValue *> with a non-global. |
908 | GlobalNumbers.erase(Global: G); |
909 | // If G's address is not significant, replace it entirely. |
910 | removeUsers(V: G); |
911 | G->replaceAllUsesWith(V: F); |
912 | } else { |
913 | // Redirect direct callers of G to F. (See note on MergeFunctionsPDI |
914 | // above). |
915 | replaceDirectCallers(Old: G, New: F); |
916 | } |
917 | } |
918 | |
919 | // If G was internal then we may have replaced all uses of G with F. If so, |
920 | // stop here and delete G. There's no need for a thunk. (See note on |
921 | // MergeFunctionsPDI above). |
922 | if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) { |
923 | G->eraseFromParent(); |
924 | ++NumFunctionsMerged; |
925 | return; |
926 | } |
927 | |
928 | if (writeThunkOrAlias(F, G)) { |
929 | ++NumFunctionsMerged; |
930 | } |
931 | } |
932 | } |
933 | |
934 | /// Replace function F by function G. |
935 | void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN, |
936 | Function *G) { |
937 | Function *F = FN.getFunc(); |
938 | assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 && |
939 | "The two functions must be equal" ); |
940 | |
941 | auto I = FNodesInTree.find(Val: F); |
942 | assert(I != FNodesInTree.end() && "F should be in FNodesInTree" ); |
943 | assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G" ); |
944 | |
945 | FnTreeType::iterator IterToFNInFnTree = I->second; |
946 | assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree." ); |
947 | // Remove F -> FN and insert G -> FN |
948 | FNodesInTree.erase(I); |
949 | FNodesInTree.insert(KV: {G, IterToFNInFnTree}); |
950 | // Replace F with G in FN, which is stored inside the FnTree. |
951 | FN.replaceBy(G); |
952 | } |
953 | |
954 | // Ordering for functions that are equal under FunctionComparator |
955 | static bool isFuncOrderCorrect(const Function *F, const Function *G) { |
956 | if (F->isInterposable() != G->isInterposable()) { |
957 | // Strong before weak, because the weak function may call the strong |
958 | // one, but not the other way around. |
959 | return !F->isInterposable(); |
960 | } |
961 | if (F->hasLocalLinkage() != G->hasLocalLinkage()) { |
962 | // External before local, because we definitely have to keep the external |
963 | // function, but may be able to drop the local one. |
964 | return !F->hasLocalLinkage(); |
965 | } |
966 | // Impose a total order (by name) on the replacement of functions. This is |
967 | // important when operating on more than one module independently to prevent |
968 | // cycles of thunks calling each other when the modules are linked together. |
969 | return F->getName() <= G->getName(); |
970 | } |
971 | |
972 | // Insert a ComparableFunction into the FnTree, or merge it away if equal to one |
973 | // that was already inserted. |
974 | bool MergeFunctions::insert(Function *NewFunction) { |
975 | std::pair<FnTreeType::iterator, bool> Result = |
976 | FnTree.insert(x: FunctionNode(NewFunction)); |
977 | |
978 | if (Result.second) { |
979 | assert(FNodesInTree.count(NewFunction) == 0); |
980 | FNodesInTree.insert(KV: {NewFunction, Result.first}); |
981 | LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName() |
982 | << '\n'); |
983 | return false; |
984 | } |
985 | |
986 | const FunctionNode &OldF = *Result.first; |
987 | |
988 | if (!isFuncOrderCorrect(F: OldF.getFunc(), G: NewFunction)) { |
989 | // Swap the two functions. |
990 | Function *F = OldF.getFunc(); |
991 | replaceFunctionInTree(FN: *Result.first, G: NewFunction); |
992 | NewFunction = F; |
993 | assert(OldF.getFunc() != F && "Must have swapped the functions." ); |
994 | } |
995 | |
996 | LLVM_DEBUG(dbgs() << " " << OldF.getFunc()->getName() |
997 | << " == " << NewFunction->getName() << '\n'); |
998 | |
999 | Function *DeleteF = NewFunction; |
1000 | mergeTwoFunctions(F: OldF.getFunc(), G: DeleteF); |
1001 | return true; |
1002 | } |
1003 | |
1004 | // Remove a function from FnTree. If it was already in FnTree, add |
1005 | // it to Deferred so that we'll look at it in the next round. |
1006 | void MergeFunctions::remove(Function *F) { |
1007 | auto I = FNodesInTree.find(Val: F); |
1008 | if (I != FNodesInTree.end()) { |
1009 | LLVM_DEBUG(dbgs() << "Deferred " << F->getName() << ".\n" ); |
1010 | FnTree.erase(position: I->second); |
1011 | // I->second has been invalidated, remove it from the FNodesInTree map to |
1012 | // preserve the invariant. |
1013 | FNodesInTree.erase(I); |
1014 | Deferred.emplace_back(args&: F); |
1015 | } |
1016 | } |
1017 | |
1018 | // For each instruction used by the value, remove() the function that contains |
1019 | // the instruction. This should happen right before a call to RAUW. |
1020 | void MergeFunctions::removeUsers(Value *V) { |
1021 | for (User *U : V->users()) |
1022 | if (auto *I = dyn_cast<Instruction>(Val: U)) |
1023 | remove(F: I->getFunction()); |
1024 | } |
1025 | |