1 //===- MergeFunctions.cpp - Merge identical functions ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass looks for equivalent functions that are mergable and folds them.
12 // A hash is computed from the function, based on its type and number of
15 // Once all hashes are computed, we perform an expensive equality comparison
16 // on each function pair. This takes n^2/2 comparisons per bucket, so it's
17 // important that the hash function be high quality. The equality comparison
18 // iterates through each instruction in each basic block.
20 // When a match is found the functions are folded. If both functions are
21 // overridable, we move the functionality into a new internal function and
22 // leave two overridable thunks to it.
24 //===----------------------------------------------------------------------===//
28 // * virtual functions.
30 // Many functions have their address taken by the virtual function table for
31 // the object they belong to. However, as long as it's only used for a lookup
32 // and call, this is irrelevant, and we'd like to fold such functions.
34 // * switch from n^2 pair-wise comparisons to an n-way comparison for each
37 // * be smarter about bitcasts.
39 // In order to fold functions, we will sometimes add either bitcast instructions
40 // or bitcast constant expressions. Unfortunately, this can confound further
41 // analysis since the two functions differ where one has a bitcast and the
42 // other doesn't. We should learn to look through bitcasts.
44 //===----------------------------------------------------------------------===//
46 #include "llvm/Transforms/IPO.h"
47 #include "llvm/ADT/DenseSet.h"
48 #include "llvm/ADT/FoldingSet.h"
49 #include "llvm/ADT/STLExtras.h"
50 #include "llvm/ADT/SmallSet.h"
51 #include "llvm/ADT/Statistic.h"
52 #include "llvm/IR/CallSite.h"
53 #include "llvm/IR/Constants.h"
54 #include "llvm/IR/DataLayout.h"
55 #include "llvm/IR/IRBuilder.h"
56 #include "llvm/IR/InlineAsm.h"
57 #include "llvm/IR/Instructions.h"
58 #include "llvm/IR/LLVMContext.h"
59 #include "llvm/IR/Module.h"
60 #include "llvm/IR/Operator.h"
61 #include "llvm/IR/ValueHandle.h"
62 #include "llvm/Pass.h"
63 #include "llvm/Support/CommandLine.h"
64 #include "llvm/Support/Debug.h"
65 #include "llvm/Support/ErrorHandling.h"
66 #include "llvm/Support/raw_ostream.h"
70 #define DEBUG_TYPE "mergefunc"
72 STATISTIC(NumFunctionsMerged, "Number of functions merged");
73 STATISTIC(NumThunksWritten, "Number of thunks generated");
74 STATISTIC(NumAliasesWritten, "Number of aliases generated");
75 STATISTIC(NumDoubleWeak, "Number of new functions created");
77 static cl::opt<unsigned> NumFunctionsForSanityCheck(
79 cl::desc("How many functions in module could be used for "
80 "MergeFunctions pass sanity check. "
81 "'0' disables this check. Works only with '-debug' key."),
82 cl::init(0), cl::Hidden);
84 /// Returns the type id for a type to be hashed. We turn pointer types into
85 /// integers here because the actual compare logic below considers pointers and
86 /// integers of the same size as equal.
87 static Type::TypeID getTypeIDForHash(Type *Ty) {
88 if (Ty->isPointerTy())
89 return Type::IntegerTyID;
90 return Ty->getTypeID();
93 /// Creates a hash-code for the function which is the same for any two
94 /// functions that will compare equal, without looking at the instructions
95 /// inside the function.
96 static unsigned profileFunction(const Function *F) {
97 FunctionType *FTy = F->getFunctionType();
100 ID.AddInteger(F->size());
101 ID.AddInteger(F->getCallingConv());
102 ID.AddBoolean(F->hasGC());
103 ID.AddBoolean(FTy->isVarArg());
104 ID.AddInteger(getTypeIDForHash(FTy->getReturnType()));
105 for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
106 ID.AddInteger(getTypeIDForHash(FTy->getParamType(i)));
107 return ID.ComputeHash();
112 /// ComparableFunction - A struct that pairs together functions with a
113 /// DataLayout so that we can keep them together as elements in the DenseSet.
114 class ComparableFunction {
116 static const ComparableFunction EmptyKey;
117 static const ComparableFunction TombstoneKey;
118 static DataLayout * const LookupOnly;
120 ComparableFunction(Function *Func, const DataLayout *DL)
121 : Func(Func), Hash(profileFunction(Func)), DL(DL) {}
123 Function *getFunc() const { return Func; }
124 unsigned getHash() const { return Hash; }
125 const DataLayout *getDataLayout() const { return DL; }
127 // Drops AssertingVH reference to the function. Outside of debug mode, this
131 "Attempted to release function twice, or release empty/tombstone!");
136 explicit ComparableFunction(unsigned Hash)
137 : Func(nullptr), Hash(Hash), DL(nullptr) {}
139 AssertingVH<Function> Func;
141 const DataLayout *DL;
144 const ComparableFunction ComparableFunction::EmptyKey = ComparableFunction(0);
145 const ComparableFunction ComparableFunction::TombstoneKey =
146 ComparableFunction(1);
147 DataLayout *const ComparableFunction::LookupOnly = (DataLayout*)(-1);
153 struct DenseMapInfo<ComparableFunction> {
154 static ComparableFunction getEmptyKey() {
155 return ComparableFunction::EmptyKey;
157 static ComparableFunction getTombstoneKey() {
158 return ComparableFunction::TombstoneKey;
160 static unsigned getHashValue(const ComparableFunction &CF) {
163 static bool isEqual(const ComparableFunction &LHS,
164 const ComparableFunction &RHS);
170 /// FunctionComparator - Compares two functions to determine whether or not
171 /// they will generate machine code with the same behaviour. DataLayout is
172 /// used if available. The comparator always fails conservatively (erring on the
173 /// side of claiming that two functions are different).
174 class FunctionComparator {
176 FunctionComparator(const DataLayout *DL, const Function *F1,
178 : FnL(F1), FnR(F2), DL(DL) {}
180 /// Test whether the two functions have equivalent behaviour.
184 /// Test whether two basic blocks have equivalent behaviour.
185 int compare(const BasicBlock *BBL, const BasicBlock *BBR);
187 /// Constants comparison.
188 /// Its analog to lexicographical comparison between hypothetical numbers
190 /// <bitcastability-trait><raw-bit-contents>
192 /// 1. Bitcastability.
193 /// Check whether L's type could be losslessly bitcasted to R's type.
194 /// On this stage method, in case when lossless bitcast is not possible
195 /// method returns -1 or 1, thus also defining which type is greater in
196 /// context of bitcastability.
197 /// Stage 0: If types are equal in terms of cmpTypes, then we can go straight
198 /// to the contents comparison.
199 /// If types differ, remember types comparison result and check
200 /// whether we still can bitcast types.
201 /// Stage 1: Types that satisfies isFirstClassType conditions are always
202 /// greater then others.
203 /// Stage 2: Vector is greater then non-vector.
204 /// If both types are vectors, then vector with greater bitwidth is
206 /// If both types are vectors with the same bitwidth, then types
207 /// are bitcastable, and we can skip other stages, and go to contents
209 /// Stage 3: Pointer types are greater than non-pointers. If both types are
210 /// pointers of the same address space - go to contents comparison.
211 /// Different address spaces: pointer with greater address space is
213 /// Stage 4: Types are neither vectors, nor pointers. And they differ.
214 /// We don't know how to bitcast them. So, we better don't do it,
215 /// and return types comparison result (so it determines the
216 /// relationship among constants we don't know how to bitcast).
218 /// Just for clearance, let's see how the set of constants could look
219 /// on single dimension axis:
221 /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors]
222 /// Where: NFCT - Not a FirstClassType
223 /// FCT - FirstClassTyp:
225 /// 2. Compare raw contents.
226 /// It ignores types on this stage and only compares bits from L and R.
227 /// Returns 0, if L and R has equivalent contents.
228 /// -1 or 1 if values are different.
230 /// 2.1. If contents are numbers, compare numbers.
231 /// Ints with greater bitwidth are greater. Ints with same bitwidths
232 /// compared by their contents.
233 /// 2.2. "And so on". Just to avoid discrepancies with comments
234 /// perhaps it would be better to read the implementation itself.
235 /// 3. And again about overall picture. Let's look back at how the ordered set
236 /// of constants will look like:
237 /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors]
239 /// Now look, what could be inside [FCT, "others"], for example:
240 /// [FCT, "others"] =
242 /// [double 0.1], [double 1.23],
243 /// [i32 1], [i32 2],
244 /// { double 1.0 }, ; StructTyID, NumElements = 1
245 /// { i32 1 }, ; StructTyID, NumElements = 1
246 /// { double 1, i32 1 }, ; StructTyID, NumElements = 2
247 /// { i32 1, double 1 } ; StructTyID, NumElements = 2
250 /// Let's explain the order. Float numbers will be less than integers, just
251 /// because of cmpType terms: FloatTyID < IntegerTyID.
252 /// Floats (with same fltSemantics) are sorted according to their value.
253 /// Then you can see integers, and they are, like a floats,
254 /// could be easy sorted among each others.
255 /// The structures. Structures are grouped at the tail, again because of their
256 /// TypeID: StructTyID > IntegerTyID > FloatTyID.
257 /// Structures with greater number of elements are greater. Structures with
258 /// greater elements going first are greater.
259 /// The same logic with vectors, arrays and other possible complex types.
261 /// Bitcastable constants.
262 /// Let's assume, that some constant, belongs to some group of
263 /// "so-called-equal" values with different types, and at the same time
264 /// belongs to another group of constants with equal types
265 /// and "really" equal values.
267 /// Now, prove that this is impossible:
269 /// If constant A with type TyA is bitcastable to B with type TyB, then:
270 /// 1. All constants with equal types to TyA, are bitcastable to B. Since
271 /// those should be vectors (if TyA is vector), pointers
272 /// (if TyA is pointer), or else (if TyA equal to TyB), those types should
274 /// 2. All constants with non-equal, but bitcastable types to TyA, are
275 /// bitcastable to B.
276 /// Once again, just because we allow it to vectors and pointers only.
277 /// This statement could be expanded as below:
278 /// 2.1. All vectors with equal bitwidth to vector A, has equal bitwidth to
279 /// vector B, and thus bitcastable to B as well.
280 /// 2.2. All pointers of the same address space, no matter what they point to,
281 /// bitcastable. So if C is pointer, it could be bitcasted to A and to B.
282 /// So any constant equal or bitcastable to A is equal or bitcastable to B.
285 /// In another words, for pointers and vectors, we ignore top-level type and
286 /// look at their particular properties (bit-width for vectors, and
287 /// address space for pointers).
288 /// If these properties are equal - compare their contents.
289 int cmpConstants(const Constant *L, const Constant *R);
291 /// Assign or look up previously assigned numbers for the two values, and
292 /// return whether the numbers are equal. Numbers are assigned in the order
294 /// Comparison order:
295 /// Stage 0: Value that is function itself is always greater then others.
296 /// If left and right values are references to their functions, then
298 /// Stage 1: Constants are greater than non-constants.
299 /// If both left and right are constants, then the result of
300 /// cmpConstants is used as cmpValues result.
301 /// Stage 2: InlineAsm instances are greater than others. If both left and
302 /// right are InlineAsm instances, InlineAsm* pointers casted to
303 /// integers and compared as numbers.
304 /// Stage 3: For all other cases we compare order we meet these values in
305 /// their functions. If right value was met first during scanning,
306 /// then left value is greater.
307 /// In another words, we compare serial numbers, for more details
308 /// see comments for sn_mapL and sn_mapR.
309 int cmpValues(const Value *L, const Value *R);
311 bool enumerate(const Value *V1, const Value *V2) {
312 return cmpValues(V1, V2) == 0;
315 /// Compare two Instructions for equivalence, similar to
316 /// Instruction::isSameOperationAs but with modifications to the type
318 /// Stages are listed in "most significant stage first" order:
319 /// On each stage below, we do comparison between some left and right
320 /// operation parts. If parts are non-equal, we assign parts comparison
321 /// result to the operation comparison result and exit from method.
322 /// Otherwise we proceed to the next stage.
324 /// 1. Operations opcodes. Compared as numbers.
325 /// 2. Number of operands.
326 /// 3. Operation types. Compared with cmpType method.
327 /// 4. Compare operation subclass optional data as stream of bytes:
328 /// just convert it to integers and call cmpNumbers.
329 /// 5. Compare in operation operand types with cmpType in
330 /// most significant operand first order.
331 /// 6. Last stage. Check operations for some specific attributes.
332 /// For example, for Load it would be:
333 /// 6.1.Load: volatile (as boolean flag)
334 /// 6.2.Load: alignment (as integer numbers)
335 /// 6.3.Load: synch-scope (as integer numbers)
336 /// 6.4.Load: range metadata (as integer numbers)
337 /// On this stage its better to see the code, since its not more than 10-15
338 /// strings for particular instruction, and could change sometimes.
339 int cmpOperation(const Instruction *L, const Instruction *R) const;
341 bool isEquivalentOperation(const Instruction *I1,
342 const Instruction *I2) const {
343 return cmpOperation(I1, I2) == 0;
346 /// Compare two GEPs for equivalent pointer arithmetic.
347 /// Parts to be compared for each comparison stage,
348 /// most significant stage first:
349 /// 1. Address space. As numbers.
350 /// 2. Constant offset, (if "DataLayout *DL" field is not NULL,
351 /// using GEPOperator::accumulateConstantOffset method).
352 /// 3. Pointer operand type (using cmpType method).
353 /// 4. Number of operands.
354 /// 5. Compare operands, using cmpValues method.
355 int cmpGEP(const GEPOperator *GEPL, const GEPOperator *GEPR);
356 int cmpGEP(const GetElementPtrInst *GEPL, const GetElementPtrInst *GEPR) {
357 return cmpGEP(cast<GEPOperator>(GEPL), cast<GEPOperator>(GEPR));
360 bool isEquivalentGEP(const GEPOperator *GEP1, const GEPOperator *GEP2) {
361 return cmpGEP(GEP1, GEP2) == 0;
363 bool isEquivalentGEP(const GetElementPtrInst *GEP1,
364 const GetElementPtrInst *GEP2) {
365 return isEquivalentGEP(cast<GEPOperator>(GEP1), cast<GEPOperator>(GEP2));
368 /// cmpType - compares two types,
369 /// defines total ordering among the types set.
372 /// 0 if types are equal,
373 /// -1 if Left is less than Right,
374 /// +1 if Left is greater than Right.
377 /// Comparison is broken onto stages. Like in lexicographical comparison
378 /// stage coming first has higher priority.
379 /// On each explanation stage keep in mind total ordering properties.
381 /// 0. Before comparison we coerce pointer types of 0 address space to
383 /// We also don't bother with same type at left and right, so
384 /// just return 0 in this case.
386 /// 1. If types are of different kind (different type IDs).
387 /// Return result of type IDs comparison, treating them as numbers.
388 /// 2. If types are vectors or integers, compare Type* values as numbers.
389 /// 3. Types has same ID, so check whether they belongs to the next group:
398 /// If so - return 0, yes - we can treat these types as equal only because
399 /// their IDs are same.
400 /// 4. If Left and Right are pointers, return result of address space
401 /// comparison (numbers comparison). We can treat pointer types of same
402 /// address space as equal.
403 /// 5. If types are complex.
404 /// Then both Left and Right are to be expanded and their element types will
405 /// be checked with the same way. If we get Res != 0 on some stage, return it.
406 /// Otherwise return 0.
407 /// 6. For all other cases put llvm_unreachable.
408 int cmpType(Type *TyL, Type *TyR) const;
410 bool isEquivalentType(Type *Ty1, Type *Ty2) const {
411 return cmpType(Ty1, Ty2) == 0;
414 int cmpNumbers(uint64_t L, uint64_t R) const;
416 int cmpAPInt(const APInt &L, const APInt &R) const;
417 int cmpAPFloat(const APFloat &L, const APFloat &R) const;
418 int cmpStrings(StringRef L, StringRef R) const;
419 int cmpAttrs(const AttributeSet L, const AttributeSet R) const;
421 // The two functions undergoing comparison.
422 const Function *FnL, *FnR;
424 const DataLayout *DL;
426 /// Assign serial numbers to values from left function, and values from
429 /// Being comparing functions we need to compare values we meet at left and
431 /// Its easy to sort things out for external values. It just should be
432 /// the same value at left and right.
433 /// But for local values (those were introduced inside function body)
434 /// we have to ensure they were introduced at exactly the same place,
435 /// and plays the same role.
436 /// Let's assign serial number to each value when we meet it first time.
437 /// Values that were met at same place will be with same serial numbers.
438 /// In this case it would be good to explain few points about values assigned
439 /// to BBs and other ways of implementation (see below).
441 /// 1. Safety of BB reordering.
442 /// It's safe to change the order of BasicBlocks in function.
443 /// Relationship with other functions and serial numbering will not be
444 /// changed in this case.
445 /// As follows from FunctionComparator::compare(), we do CFG walk: we start
446 /// from the entry, and then take each terminator. So it doesn't matter how in
447 /// fact BBs are ordered in function. And since cmpValues are called during
448 /// this walk, the numbering depends only on how BBs located inside the CFG.
449 /// So the answer is - yes. We will get the same numbering.
451 /// 2. Impossibility to use dominance properties of values.
452 /// If we compare two instruction operands: first is usage of local
453 /// variable AL from function FL, and second is usage of local variable AR
454 /// from FR, we could compare their origins and check whether they are
455 /// defined at the same place.
456 /// But, we are still not able to compare operands of PHI nodes, since those
457 /// could be operands from further BBs we didn't scan yet.
458 /// So it's impossible to use dominance properties in general.
459 DenseMap<const Value*, int> sn_mapL, sn_mapR;
464 int FunctionComparator::cmpNumbers(uint64_t L, uint64_t R) const {
465 if (L < R) return -1;
470 int FunctionComparator::cmpAPInt(const APInt &L, const APInt &R) const {
471 if (int Res = cmpNumbers(L.getBitWidth(), R.getBitWidth()))
473 if (L.ugt(R)) return 1;
474 if (R.ugt(L)) return -1;
478 int FunctionComparator::cmpAPFloat(const APFloat &L, const APFloat &R) const {
479 if (int Res = cmpNumbers((uint64_t)&L.getSemantics(),
480 (uint64_t)&R.getSemantics()))
482 return cmpAPInt(L.bitcastToAPInt(), R.bitcastToAPInt());
485 int FunctionComparator::cmpStrings(StringRef L, StringRef R) const {
486 // Prevent heavy comparison, compare sizes first.
487 if (int Res = cmpNumbers(L.size(), R.size()))
490 // Compare strings lexicographically only when it is necessary: only when
491 // strings are equal in size.
495 int FunctionComparator::cmpAttrs(const AttributeSet L,
496 const AttributeSet R) const {
497 if (int Res = cmpNumbers(L.getNumSlots(), R.getNumSlots()))
500 for (unsigned i = 0, e = L.getNumSlots(); i != e; ++i) {
501 AttributeSet::iterator LI = L.begin(i), LE = L.end(i), RI = R.begin(i),
503 for (; LI != LE && RI != RE; ++LI, ++RI) {
519 /// Constants comparison:
520 /// 1. Check whether type of L constant could be losslessly bitcasted to R
522 /// 2. Compare constant contents.
523 /// For more details see declaration comments.
524 int FunctionComparator::cmpConstants(const Constant *L, const Constant *R) {
526 Type *TyL = L->getType();
527 Type *TyR = R->getType();
529 // Check whether types are bitcastable. This part is just re-factored
530 // Type::canLosslesslyBitCastTo method, but instead of returning true/false,
531 // we also pack into result which type is "less" for us.
532 int TypesRes = cmpType(TyL, TyR);
534 // Types are different, but check whether we can bitcast them.
535 if (!TyL->isFirstClassType()) {
536 if (TyR->isFirstClassType())
538 // Neither TyL nor TyR are values of first class type. Return the result
539 // of comparing the types
542 if (!TyR->isFirstClassType()) {
543 if (TyL->isFirstClassType())
548 // Vector -> Vector conversions are always lossless if the two vector types
549 // have the same size, otherwise not.
550 unsigned TyLWidth = 0;
551 unsigned TyRWidth = 0;
553 if (const VectorType *VecTyL = dyn_cast<VectorType>(TyL))
554 TyLWidth = VecTyL->getBitWidth();
555 if (const VectorType *VecTyR = dyn_cast<VectorType>(TyR))
556 TyRWidth = VecTyR->getBitWidth();
558 if (TyLWidth != TyRWidth)
559 return cmpNumbers(TyLWidth, TyRWidth);
561 // Zero bit-width means neither TyL nor TyR are vectors.
563 PointerType *PTyL = dyn_cast<PointerType>(TyL);
564 PointerType *PTyR = dyn_cast<PointerType>(TyR);
566 unsigned AddrSpaceL = PTyL->getAddressSpace();
567 unsigned AddrSpaceR = PTyR->getAddressSpace();
568 if (int Res = cmpNumbers(AddrSpaceL, AddrSpaceR))
576 // TyL and TyR aren't vectors, nor pointers. We don't know how to
582 // OK, types are bitcastable, now check constant contents.
584 if (L->isNullValue() && R->isNullValue())
586 if (L->isNullValue() && !R->isNullValue())
588 if (!L->isNullValue() && R->isNullValue())
591 if (int Res = cmpNumbers(L->getValueID(), R->getValueID()))
594 switch (L->getValueID()) {
595 case Value::UndefValueVal: return TypesRes;
596 case Value::ConstantIntVal: {
597 const APInt &LInt = cast<ConstantInt>(L)->getValue();
598 const APInt &RInt = cast<ConstantInt>(R)->getValue();
599 return cmpAPInt(LInt, RInt);
601 case Value::ConstantFPVal: {
602 const APFloat &LAPF = cast<ConstantFP>(L)->getValueAPF();
603 const APFloat &RAPF = cast<ConstantFP>(R)->getValueAPF();
604 return cmpAPFloat(LAPF, RAPF);
606 case Value::ConstantArrayVal: {
607 const ConstantArray *LA = cast<ConstantArray>(L);
608 const ConstantArray *RA = cast<ConstantArray>(R);
609 uint64_t NumElementsL = cast<ArrayType>(TyL)->getNumElements();
610 uint64_t NumElementsR = cast<ArrayType>(TyR)->getNumElements();
611 if (int Res = cmpNumbers(NumElementsL, NumElementsR))
613 for (uint64_t i = 0; i < NumElementsL; ++i) {
614 if (int Res = cmpConstants(cast<Constant>(LA->getOperand(i)),
615 cast<Constant>(RA->getOperand(i))))
620 case Value::ConstantStructVal: {
621 const ConstantStruct *LS = cast<ConstantStruct>(L);
622 const ConstantStruct *RS = cast<ConstantStruct>(R);
623 unsigned NumElementsL = cast<StructType>(TyL)->getNumElements();
624 unsigned NumElementsR = cast<StructType>(TyR)->getNumElements();
625 if (int Res = cmpNumbers(NumElementsL, NumElementsR))
627 for (unsigned i = 0; i != NumElementsL; ++i) {
628 if (int Res = cmpConstants(cast<Constant>(LS->getOperand(i)),
629 cast<Constant>(RS->getOperand(i))))
634 case Value::ConstantVectorVal: {
635 const ConstantVector *LV = cast<ConstantVector>(L);
636 const ConstantVector *RV = cast<ConstantVector>(R);
637 unsigned NumElementsL = cast<VectorType>(TyL)->getNumElements();
638 unsigned NumElementsR = cast<VectorType>(TyR)->getNumElements();
639 if (int Res = cmpNumbers(NumElementsL, NumElementsR))
641 for (uint64_t i = 0; i < NumElementsL; ++i) {
642 if (int Res = cmpConstants(cast<Constant>(LV->getOperand(i)),
643 cast<Constant>(RV->getOperand(i))))
648 case Value::ConstantExprVal: {
649 const ConstantExpr *LE = cast<ConstantExpr>(L);
650 const ConstantExpr *RE = cast<ConstantExpr>(R);
651 unsigned NumOperandsL = LE->getNumOperands();
652 unsigned NumOperandsR = RE->getNumOperands();
653 if (int Res = cmpNumbers(NumOperandsL, NumOperandsR))
655 for (unsigned i = 0; i < NumOperandsL; ++i) {
656 if (int Res = cmpConstants(cast<Constant>(LE->getOperand(i)),
657 cast<Constant>(RE->getOperand(i))))
662 case Value::FunctionVal:
663 case Value::GlobalVariableVal:
664 case Value::GlobalAliasVal:
665 default: // Unknown constant, cast L and R pointers to numbers and compare.
666 return cmpNumbers((uint64_t)L, (uint64_t)R);
670 /// cmpType - compares two types,
671 /// defines total ordering among the types set.
672 /// See method declaration comments for more details.
673 int FunctionComparator::cmpType(Type *TyL, Type *TyR) const {
675 PointerType *PTyL = dyn_cast<PointerType>(TyL);
676 PointerType *PTyR = dyn_cast<PointerType>(TyR);
679 if (PTyL && PTyL->getAddressSpace() == 0) TyL = DL->getIntPtrType(TyL);
680 if (PTyR && PTyR->getAddressSpace() == 0) TyR = DL->getIntPtrType(TyR);
686 if (int Res = cmpNumbers(TyL->getTypeID(), TyR->getTypeID()))
689 switch (TyL->getTypeID()) {
691 llvm_unreachable("Unknown type!");
692 // Fall through in Release mode.
693 case Type::IntegerTyID:
694 case Type::VectorTyID:
695 // TyL == TyR would have returned true earlier.
696 return cmpNumbers((uint64_t)TyL, (uint64_t)TyR);
699 case Type::FloatTyID:
700 case Type::DoubleTyID:
701 case Type::X86_FP80TyID:
702 case Type::FP128TyID:
703 case Type::PPC_FP128TyID:
704 case Type::LabelTyID:
705 case Type::MetadataTyID:
708 case Type::PointerTyID: {
709 assert(PTyL && PTyR && "Both types must be pointers here.");
710 return cmpNumbers(PTyL->getAddressSpace(), PTyR->getAddressSpace());
713 case Type::StructTyID: {
714 StructType *STyL = cast<StructType>(TyL);
715 StructType *STyR = cast<StructType>(TyR);
716 if (STyL->getNumElements() != STyR->getNumElements())
717 return cmpNumbers(STyL->getNumElements(), STyR->getNumElements());
719 if (STyL->isPacked() != STyR->isPacked())
720 return cmpNumbers(STyL->isPacked(), STyR->isPacked());
722 for (unsigned i = 0, e = STyL->getNumElements(); i != e; ++i) {
723 if (int Res = cmpType(STyL->getElementType(i),
724 STyR->getElementType(i)))
730 case Type::FunctionTyID: {
731 FunctionType *FTyL = cast<FunctionType>(TyL);
732 FunctionType *FTyR = cast<FunctionType>(TyR);
733 if (FTyL->getNumParams() != FTyR->getNumParams())
734 return cmpNumbers(FTyL->getNumParams(), FTyR->getNumParams());
736 if (FTyL->isVarArg() != FTyR->isVarArg())
737 return cmpNumbers(FTyL->isVarArg(), FTyR->isVarArg());
739 if (int Res = cmpType(FTyL->getReturnType(), FTyR->getReturnType()))
742 for (unsigned i = 0, e = FTyL->getNumParams(); i != e; ++i) {
743 if (int Res = cmpType(FTyL->getParamType(i), FTyR->getParamType(i)))
749 case Type::ArrayTyID: {
750 ArrayType *ATyL = cast<ArrayType>(TyL);
751 ArrayType *ATyR = cast<ArrayType>(TyR);
752 if (ATyL->getNumElements() != ATyR->getNumElements())
753 return cmpNumbers(ATyL->getNumElements(), ATyR->getNumElements());
754 return cmpType(ATyL->getElementType(), ATyR->getElementType());
759 // Determine whether the two operations are the same except that pointer-to-A
760 // and pointer-to-B are equivalent. This should be kept in sync with
761 // Instruction::isSameOperationAs.
762 // Read method declaration comments for more details.
763 int FunctionComparator::cmpOperation(const Instruction *L,
764 const Instruction *R) const {
765 // Differences from Instruction::isSameOperationAs:
766 // * replace type comparison with calls to isEquivalentType.
767 // * we test for I->hasSameSubclassOptionalData (nuw/nsw/tail) at the top
768 // * because of the above, we don't test for the tail bit on calls later on
769 if (int Res = cmpNumbers(L->getOpcode(), R->getOpcode()))
772 if (int Res = cmpNumbers(L->getNumOperands(), R->getNumOperands()))
775 if (int Res = cmpType(L->getType(), R->getType()))
778 if (int Res = cmpNumbers(L->getRawSubclassOptionalData(),
779 R->getRawSubclassOptionalData()))
782 // We have two instructions of identical opcode and #operands. Check to see
783 // if all operands are the same type
784 for (unsigned i = 0, e = L->getNumOperands(); i != e; ++i) {
786 cmpType(L->getOperand(i)->getType(), R->getOperand(i)->getType()))
790 // Check special state that is a part of some instructions.
791 if (const LoadInst *LI = dyn_cast<LoadInst>(L)) {
792 if (int Res = cmpNumbers(LI->isVolatile(), cast<LoadInst>(R)->isVolatile()))
795 cmpNumbers(LI->getAlignment(), cast<LoadInst>(R)->getAlignment()))
798 cmpNumbers(LI->getOrdering(), cast<LoadInst>(R)->getOrdering()))
801 cmpNumbers(LI->getSynchScope(), cast<LoadInst>(R)->getSynchScope()))
803 return cmpNumbers((uint64_t)LI->getMetadata(LLVMContext::MD_range),
804 (uint64_t)cast<LoadInst>(R)->getMetadata(LLVMContext::MD_range));
806 if (const StoreInst *SI = dyn_cast<StoreInst>(L)) {
808 cmpNumbers(SI->isVolatile(), cast<StoreInst>(R)->isVolatile()))
811 cmpNumbers(SI->getAlignment(), cast<StoreInst>(R)->getAlignment()))
814 cmpNumbers(SI->getOrdering(), cast<StoreInst>(R)->getOrdering()))
816 return cmpNumbers(SI->getSynchScope(), cast<StoreInst>(R)->getSynchScope());
818 if (const CmpInst *CI = dyn_cast<CmpInst>(L))
819 return cmpNumbers(CI->getPredicate(), cast<CmpInst>(R)->getPredicate());
820 if (const CallInst *CI = dyn_cast<CallInst>(L)) {
821 if (int Res = cmpNumbers(CI->getCallingConv(),
822 cast<CallInst>(R)->getCallingConv()))
824 return cmpAttrs(CI->getAttributes(), cast<CallInst>(R)->getAttributes());
826 if (const InvokeInst *CI = dyn_cast<InvokeInst>(L)) {
827 if (int Res = cmpNumbers(CI->getCallingConv(),
828 cast<InvokeInst>(R)->getCallingConv()))
830 return cmpAttrs(CI->getAttributes(), cast<InvokeInst>(R)->getAttributes());
832 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(L)) {
833 ArrayRef<unsigned> LIndices = IVI->getIndices();
834 ArrayRef<unsigned> RIndices = cast<InsertValueInst>(R)->getIndices();
835 if (int Res = cmpNumbers(LIndices.size(), RIndices.size()))
837 for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
838 if (int Res = cmpNumbers(LIndices[i], RIndices[i]))
842 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(L)) {
843 ArrayRef<unsigned> LIndices = EVI->getIndices();
844 ArrayRef<unsigned> RIndices = cast<ExtractValueInst>(R)->getIndices();
845 if (int Res = cmpNumbers(LIndices.size(), RIndices.size()))
847 for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
848 if (int Res = cmpNumbers(LIndices[i], RIndices[i]))
852 if (const FenceInst *FI = dyn_cast<FenceInst>(L)) {
854 cmpNumbers(FI->getOrdering(), cast<FenceInst>(R)->getOrdering()))
856 return cmpNumbers(FI->getSynchScope(), cast<FenceInst>(R)->getSynchScope());
859 if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(L)) {
860 if (int Res = cmpNumbers(CXI->isVolatile(),
861 cast<AtomicCmpXchgInst>(R)->isVolatile()))
863 if (int Res = cmpNumbers(CXI->isWeak(),
864 cast<AtomicCmpXchgInst>(R)->isWeak()))
866 if (int Res = cmpNumbers(CXI->getSuccessOrdering(),
867 cast<AtomicCmpXchgInst>(R)->getSuccessOrdering()))
869 if (int Res = cmpNumbers(CXI->getFailureOrdering(),
870 cast<AtomicCmpXchgInst>(R)->getFailureOrdering()))
872 return cmpNumbers(CXI->getSynchScope(),
873 cast<AtomicCmpXchgInst>(R)->getSynchScope());
875 if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(L)) {
876 if (int Res = cmpNumbers(RMWI->getOperation(),
877 cast<AtomicRMWInst>(R)->getOperation()))
879 if (int Res = cmpNumbers(RMWI->isVolatile(),
880 cast<AtomicRMWInst>(R)->isVolatile()))
882 if (int Res = cmpNumbers(RMWI->getOrdering(),
883 cast<AtomicRMWInst>(R)->getOrdering()))
885 return cmpNumbers(RMWI->getSynchScope(),
886 cast<AtomicRMWInst>(R)->getSynchScope());
891 // Determine whether two GEP operations perform the same underlying arithmetic.
892 // Read method declaration comments for more details.
893 int FunctionComparator::cmpGEP(const GEPOperator *GEPL,
894 const GEPOperator *GEPR) {
896 unsigned int ASL = GEPL->getPointerAddressSpace();
897 unsigned int ASR = GEPR->getPointerAddressSpace();
899 if (int Res = cmpNumbers(ASL, ASR))
902 // When we have target data, we can reduce the GEP down to the value in bytes
903 // added to the address.
905 unsigned BitWidth = DL->getPointerSizeInBits(ASL);
906 APInt OffsetL(BitWidth, 0), OffsetR(BitWidth, 0);
907 if (GEPL->accumulateConstantOffset(*DL, OffsetL) &&
908 GEPR->accumulateConstantOffset(*DL, OffsetR))
909 return cmpAPInt(OffsetL, OffsetR);
912 if (int Res = cmpNumbers((uint64_t)GEPL->getPointerOperand()->getType(),
913 (uint64_t)GEPR->getPointerOperand()->getType()))
916 if (int Res = cmpNumbers(GEPL->getNumOperands(), GEPR->getNumOperands()))
919 for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i) {
920 if (int Res = cmpValues(GEPL->getOperand(i), GEPR->getOperand(i)))
927 /// Compare two values used by the two functions under pair-wise comparison. If
928 /// this is the first time the values are seen, they're added to the mapping so
929 /// that we will detect mismatches on next use.
930 /// See comments in declaration for more details.
931 int FunctionComparator::cmpValues(const Value *L, const Value *R) {
932 // Catch self-reference case.
944 const Constant *ConstL = dyn_cast<Constant>(L);
945 const Constant *ConstR = dyn_cast<Constant>(R);
946 if (ConstL && ConstR) {
949 return cmpConstants(ConstL, ConstR);
957 const InlineAsm *InlineAsmL = dyn_cast<InlineAsm>(L);
958 const InlineAsm *InlineAsmR = dyn_cast<InlineAsm>(R);
960 if (InlineAsmL && InlineAsmR)
961 return cmpNumbers((uint64_t)L, (uint64_t)R);
967 auto LeftSN = sn_mapL.insert(std::make_pair(L, sn_mapL.size())),
968 RightSN = sn_mapR.insert(std::make_pair(R, sn_mapR.size()));
970 return cmpNumbers(LeftSN.first->second, RightSN.first->second);
972 // Test whether two basic blocks have equivalent behaviour.
973 int FunctionComparator::compare(const BasicBlock *BBL, const BasicBlock *BBR) {
974 BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end();
975 BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end();
978 if (int Res = cmpValues(InstL, InstR))
981 const GetElementPtrInst *GEPL = dyn_cast<GetElementPtrInst>(InstL);
982 const GetElementPtrInst *GEPR = dyn_cast<GetElementPtrInst>(InstR);
991 cmpValues(GEPL->getPointerOperand(), GEPR->getPointerOperand()))
993 if (int Res = cmpGEP(GEPL, GEPR))
996 if (int Res = cmpOperation(InstL, InstR))
998 assert(InstL->getNumOperands() == InstR->getNumOperands());
1000 for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) {
1001 Value *OpL = InstL->getOperand(i);
1002 Value *OpR = InstR->getOperand(i);
1003 if (int Res = cmpValues(OpL, OpR))
1005 if (int Res = cmpNumbers(OpL->getValueID(), OpR->getValueID()))
1007 // TODO: Already checked in cmpOperation
1008 if (int Res = cmpType(OpL->getType(), OpR->getType()))
1014 } while (InstL != InstLE && InstR != InstRE);
1016 if (InstL != InstLE && InstR == InstRE)
1018 if (InstL == InstLE && InstR != InstRE)
1023 // Test whether the two functions have equivalent behaviour.
1024 int FunctionComparator::compare() {
1029 if (int Res = cmpAttrs(FnL->getAttributes(), FnR->getAttributes()))
1032 if (int Res = cmpNumbers(FnL->hasGC(), FnR->hasGC()))
1036 if (int Res = cmpNumbers((uint64_t)FnL->getGC(), (uint64_t)FnR->getGC()))
1040 if (int Res = cmpNumbers(FnL->hasSection(), FnR->hasSection()))
1043 if (FnL->hasSection()) {
1044 if (int Res = cmpStrings(FnL->getSection(), FnR->getSection()))
1048 if (int Res = cmpNumbers(FnL->isVarArg(), FnR->isVarArg()))
1051 // TODO: if it's internal and only used in direct calls, we could handle this
1053 if (int Res = cmpNumbers(FnL->getCallingConv(), FnR->getCallingConv()))
1056 if (int Res = cmpType(FnL->getFunctionType(), FnR->getFunctionType()))
1059 assert(FnL->arg_size() == FnR->arg_size() &&
1060 "Identically typed functions have different numbers of args!");
1062 // Visit the arguments so that they get enumerated in the order they're
1064 for (Function::const_arg_iterator ArgLI = FnL->arg_begin(),
1065 ArgRI = FnR->arg_begin(),
1066 ArgLE = FnL->arg_end();
1067 ArgLI != ArgLE; ++ArgLI, ++ArgRI) {
1068 if (cmpValues(ArgLI, ArgRI) != 0)
1069 llvm_unreachable("Arguments repeat!");
1072 // We do a CFG-ordered walk since the actual ordering of the blocks in the
1073 // linked list is immaterial. Our walk starts at the entry block for both
1074 // functions, then takes each block from each terminator in order. As an
1075 // artifact, this also means that unreachable blocks are ignored.
1076 SmallVector<const BasicBlock *, 8> FnLBBs, FnRBBs;
1077 SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F1.
1079 FnLBBs.push_back(&FnL->getEntryBlock());
1080 FnRBBs.push_back(&FnR->getEntryBlock());
1082 VisitedBBs.insert(FnLBBs[0]);
1083 while (!FnLBBs.empty()) {
1084 const BasicBlock *BBL = FnLBBs.pop_back_val();
1085 const BasicBlock *BBR = FnRBBs.pop_back_val();
1087 if (int Res = cmpValues(BBL, BBR))
1090 if (int Res = compare(BBL, BBR))
1093 const TerminatorInst *TermL = BBL->getTerminator();
1094 const TerminatorInst *TermR = BBR->getTerminator();
1096 assert(TermL->getNumSuccessors() == TermR->getNumSuccessors());
1097 for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) {
1098 if (!VisitedBBs.insert(TermL->getSuccessor(i)))
1101 FnLBBs.push_back(TermL->getSuccessor(i));
1102 FnRBBs.push_back(TermR->getSuccessor(i));
1110 /// MergeFunctions finds functions which will generate identical machine code,
1111 /// by considering all pointer types to be equivalent. Once identified,
1112 /// MergeFunctions will fold them by replacing a call to one to a call to a
1113 /// bitcast of the other.
1115 class MergeFunctions : public ModulePass {
1119 : ModulePass(ID), HasGlobalAliases(false) {
1120 initializeMergeFunctionsPass(*PassRegistry::getPassRegistry());
1123 bool runOnModule(Module &M) override;
1126 typedef DenseSet<ComparableFunction> FnSetType;
1128 /// A work queue of functions that may have been modified and should be
1130 std::vector<WeakVH> Deferred;
1132 /// Checks the rules of order relation introduced among functions set.
1133 /// Returns true, if sanity check has been passed, and false if failed.
1134 bool doSanityCheck(std::vector<WeakVH> &Worklist);
1136 /// Insert a ComparableFunction into the FnSet, or merge it away if it's
1137 /// equal to one that's already present.
1138 bool insert(ComparableFunction &NewF);
1140 /// Remove a Function from the FnSet and queue it up for a second sweep of
1142 void remove(Function *F);
1144 /// Find the functions that use this Value and remove them from FnSet and
1145 /// queue the functions.
1146 void removeUsers(Value *V);
1148 /// Replace all direct calls of Old with calls of New. Will bitcast New if
1149 /// necessary to make types match.
1150 void replaceDirectCallers(Function *Old, Function *New);
1152 /// Merge two equivalent functions. Upon completion, G may be deleted, or may
1153 /// be converted into a thunk. In either case, it should never be visited
1155 void mergeTwoFunctions(Function *F, Function *G);
1157 /// Replace G with a thunk or an alias to F. Deletes G.
1158 void writeThunkOrAlias(Function *F, Function *G);
1160 /// Replace G with a simple tail call to bitcast(F). Also replace direct uses
1161 /// of G with bitcast(F). Deletes G.
1162 void writeThunk(Function *F, Function *G);
1164 /// Replace G with an alias to F. Deletes G.
1165 void writeAlias(Function *F, Function *G);
1167 /// The set of all distinct functions. Use the insert() and remove() methods
1171 /// DataLayout for more accurate GEP comparisons. May be NULL.
1172 const DataLayout *DL;
1174 /// Whether or not the target supports global aliases.
1175 bool HasGlobalAliases;
1178 } // end anonymous namespace
1180 char MergeFunctions::ID = 0;
1181 INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false)
1183 ModulePass *llvm::createMergeFunctionsPass() {
1184 return new MergeFunctions();
1187 bool MergeFunctions::doSanityCheck(std::vector<WeakVH> &Worklist) {
1188 if (const unsigned Max = NumFunctionsForSanityCheck) {
1189 unsigned TripleNumber = 0;
1192 dbgs() << "MERGEFUNC-SANITY: Started for first " << Max << " functions.\n";
1195 for (std::vector<WeakVH>::iterator I = Worklist.begin(), E = Worklist.end();
1196 I != E && i < Max; ++I, ++i) {
1198 for (std::vector<WeakVH>::iterator J = I; J != E && j < Max; ++J, ++j) {
1199 Function *F1 = cast<Function>(*I);
1200 Function *F2 = cast<Function>(*J);
1201 int Res1 = FunctionComparator(DL, F1, F2).compare();
1202 int Res2 = FunctionComparator(DL, F2, F1).compare();
1204 // If F1 <= F2, then F2 >= F1, otherwise report failure.
1205 if (Res1 != -Res2) {
1206 dbgs() << "MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber
1217 for (std::vector<WeakVH>::iterator K = J; K != E && k < Max;
1218 ++k, ++K, ++TripleNumber) {
1222 Function *F3 = cast<Function>(*K);
1223 int Res3 = FunctionComparator(DL, F1, F3).compare();
1224 int Res4 = FunctionComparator(DL, F2, F3).compare();
1226 bool Transitive = true;
1228 if (Res1 != 0 && Res1 == Res4) {
1229 // F1 > F2, F2 > F3 => F1 > F3
1230 Transitive = Res3 == Res1;
1231 } else if (Res3 != 0 && Res3 == -Res4) {
1232 // F1 > F3, F3 > F2 => F1 > F2
1233 Transitive = Res3 == Res1;
1234 } else if (Res4 != 0 && -Res3 == Res4) {
1235 // F2 > F3, F3 > F1 => F2 > F1
1236 Transitive = Res4 == -Res1;
1240 dbgs() << "MERGEFUNC-SANITY: Non-transitive; triple: "
1241 << TripleNumber << "\n";
1242 dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", "
1253 dbgs() << "MERGEFUNC-SANITY: " << (Valid ? "Passed." : "Failed.") << "\n";
1259 bool MergeFunctions::runOnModule(Module &M) {
1260 bool Changed = false;
1261 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
1262 DL = DLP ? &DLP->getDataLayout() : nullptr;
1264 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
1265 if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage())
1266 Deferred.push_back(WeakVH(I));
1268 FnSet.resize(Deferred.size());
1271 std::vector<WeakVH> Worklist;
1272 Deferred.swap(Worklist);
1274 DEBUG(doSanityCheck(Worklist));
1276 DEBUG(dbgs() << "size of module: " << M.size() << '\n');
1277 DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
1279 // Insert only strong functions and merge them. Strong function merging
1280 // always deletes one of them.
1281 for (std::vector<WeakVH>::iterator I = Worklist.begin(),
1282 E = Worklist.end(); I != E; ++I) {
1284 Function *F = cast<Function>(*I);
1285 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
1286 !F->mayBeOverridden()) {
1287 ComparableFunction CF = ComparableFunction(F, DL);
1288 Changed |= insert(CF);
1292 // Insert only weak functions and merge them. By doing these second we
1293 // create thunks to the strong function when possible. When two weak
1294 // functions are identical, we create a new strong function with two weak
1295 // weak thunks to it which are identical but not mergable.
1296 for (std::vector<WeakVH>::iterator I = Worklist.begin(),
1297 E = Worklist.end(); I != E; ++I) {
1299 Function *F = cast<Function>(*I);
1300 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
1301 F->mayBeOverridden()) {
1302 ComparableFunction CF = ComparableFunction(F, DL);
1303 Changed |= insert(CF);
1306 DEBUG(dbgs() << "size of FnSet: " << FnSet.size() << '\n');
1307 } while (!Deferred.empty());
1314 bool DenseMapInfo<ComparableFunction>::isEqual(const ComparableFunction &LHS,
1315 const ComparableFunction &RHS) {
1316 if (LHS.getFunc() == RHS.getFunc() &&
1317 LHS.getHash() == RHS.getHash())
1319 if (!LHS.getFunc() || !RHS.getFunc())
1322 // One of these is a special "underlying pointer comparison only" object.
1323 if (LHS.getDataLayout() == ComparableFunction::LookupOnly ||
1324 RHS.getDataLayout() == ComparableFunction::LookupOnly)
1327 assert(LHS.getDataLayout() == RHS.getDataLayout() &&
1328 "Comparing functions for different targets");
1330 return FunctionComparator(LHS.getDataLayout(), LHS.getFunc(), RHS.getFunc())
1334 // Replace direct callers of Old with New.
1335 void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
1336 Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType());
1337 for (auto UI = Old->use_begin(), UE = Old->use_end(); UI != UE;) {
1340 CallSite CS(U->getUser());
1341 if (CS && CS.isCallee(U)) {
1342 remove(CS.getInstruction()->getParent()->getParent());
1348 // Replace G with an alias to F if possible, or else a thunk to F. Deletes G.
1349 void MergeFunctions::writeThunkOrAlias(Function *F, Function *G) {
1350 if (HasGlobalAliases && G->hasUnnamedAddr()) {
1351 if (G->hasExternalLinkage() || G->hasLocalLinkage() ||
1352 G->hasWeakLinkage()) {
1361 // Helper for writeThunk,
1362 // Selects proper bitcast operation,
1363 // but a bit simpler then CastInst::getCastOpcode.
1364 static Value *createCast(IRBuilder<false> &Builder, Value *V, Type *DestTy) {
1365 Type *SrcTy = V->getType();
1366 if (SrcTy->isStructTy()) {
1367 assert(DestTy->isStructTy());
1368 assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements());
1369 Value *Result = UndefValue::get(DestTy);
1370 for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) {
1371 Value *Element = createCast(
1372 Builder, Builder.CreateExtractValue(V, ArrayRef<unsigned int>(I)),
1373 DestTy->getStructElementType(I));
1376 Builder.CreateInsertValue(Result, Element, ArrayRef<unsigned int>(I));
1380 assert(!DestTy->isStructTy());
1381 if (SrcTy->isIntegerTy() && DestTy->isPointerTy())
1382 return Builder.CreateIntToPtr(V, DestTy);
1383 else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
1384 return Builder.CreatePtrToInt(V, DestTy);
1386 return Builder.CreateBitCast(V, DestTy);
1389 // Replace G with a simple tail call to bitcast(F). Also replace direct uses
1390 // of G with bitcast(F). Deletes G.
1391 void MergeFunctions::writeThunk(Function *F, Function *G) {
1392 if (!G->mayBeOverridden()) {
1393 // Redirect direct callers of G to F.
1394 replaceDirectCallers(G, F);
1397 // If G was internal then we may have replaced all uses of G with F. If so,
1398 // stop here and delete G. There's no need for a thunk.
1399 if (G->hasLocalLinkage() && G->use_empty()) {
1400 G->eraseFromParent();
1404 Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
1406 BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG);
1407 IRBuilder<false> Builder(BB);
1409 SmallVector<Value *, 16> Args;
1411 FunctionType *FFTy = F->getFunctionType();
1412 for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end();
1414 Args.push_back(createCast(Builder, (Value*)AI, FFTy->getParamType(i)));
1418 CallInst *CI = Builder.CreateCall(F, Args);
1420 CI->setCallingConv(F->getCallingConv());
1421 if (NewG->getReturnType()->isVoidTy()) {
1422 Builder.CreateRetVoid();
1424 Builder.CreateRet(createCast(Builder, CI, NewG->getReturnType()));
1427 NewG->copyAttributesFrom(G);
1430 G->replaceAllUsesWith(NewG);
1431 G->eraseFromParent();
1433 DEBUG(dbgs() << "writeThunk: " << NewG->getName() << '\n');
1437 // Replace G with an alias to F and delete G.
1438 void MergeFunctions::writeAlias(Function *F, Function *G) {
1439 PointerType *PTy = G->getType();
1440 auto *GA = GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(),
1441 G->getLinkage(), "", F);
1442 F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
1444 GA->setVisibility(G->getVisibility());
1446 G->replaceAllUsesWith(GA);
1447 G->eraseFromParent();
1449 DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
1450 ++NumAliasesWritten;
1453 // Merge two equivalent functions. Upon completion, Function G is deleted.
1454 void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
1455 if (F->mayBeOverridden()) {
1456 assert(G->mayBeOverridden());
1458 if (HasGlobalAliases) {
1459 // Make them both thunks to the same internal function.
1460 Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
1462 H->copyAttributesFrom(F);
1465 F->replaceAllUsesWith(H);
1467 unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment());
1472 F->setAlignment(MaxAlignment);
1473 F->setLinkage(GlobalValue::PrivateLinkage);
1475 // We can't merge them. Instead, pick one and update all direct callers
1476 // to call it and hope that we improve the instruction cache hit rate.
1477 replaceDirectCallers(G, F);
1482 writeThunkOrAlias(F, G);
1485 ++NumFunctionsMerged;
1488 // Insert a ComparableFunction into the FnSet, or merge it away if equal to one
1489 // that was already inserted.
1490 bool MergeFunctions::insert(ComparableFunction &NewF) {
1491 std::pair<FnSetType::iterator, bool> Result = FnSet.insert(NewF);
1492 if (Result.second) {
1493 DEBUG(dbgs() << "Inserting as unique: " << NewF.getFunc()->getName() << '\n');
1497 const ComparableFunction &OldF = *Result.first;
1499 // Don't merge tiny functions, since it can just end up making the function
1501 // FIXME: Should still merge them if they are unnamed_addr and produce an
1503 if (NewF.getFunc()->size() == 1) {
1504 if (NewF.getFunc()->front().size() <= 2) {
1505 DEBUG(dbgs() << NewF.getFunc()->getName()
1506 << " is to small to bother merging\n");
1511 // Never thunk a strong function to a weak function.
1512 assert(!OldF.getFunc()->mayBeOverridden() ||
1513 NewF.getFunc()->mayBeOverridden());
1515 DEBUG(dbgs() << " " << OldF.getFunc()->getName() << " == "
1516 << NewF.getFunc()->getName() << '\n');
1518 Function *DeleteF = NewF.getFunc();
1520 mergeTwoFunctions(OldF.getFunc(), DeleteF);
1524 // Remove a function from FnSet. If it was already in FnSet, add it to Deferred
1525 // so that we'll look at it in the next round.
1526 void MergeFunctions::remove(Function *F) {
1527 // We need to make sure we remove F, not a function "equal" to F per the
1528 // function equality comparator.
1530 // The special "lookup only" ComparableFunction bypasses the expensive
1531 // function comparison in favour of a pointer comparison on the underlying
1533 ComparableFunction CF = ComparableFunction(F, ComparableFunction::LookupOnly);
1534 if (FnSet.erase(CF)) {
1535 DEBUG(dbgs() << "Removed " << F->getName() << " from set and deferred it.\n");
1536 Deferred.push_back(F);
1540 // For each instruction used by the value, remove() the function that contains
1541 // the instruction. This should happen right before a call to RAUW.
1542 void MergeFunctions::removeUsers(Value *V) {
1543 std::vector<Value *> Worklist;
1544 Worklist.push_back(V);
1545 while (!Worklist.empty()) {
1546 Value *V = Worklist.back();
1547 Worklist.pop_back();
1549 for (User *U : V->users()) {
1550 if (Instruction *I = dyn_cast<Instruction>(U)) {
1551 remove(I->getParent()->getParent());
1552 } else if (isa<GlobalValue>(U)) {
1554 } else if (Constant *C = dyn_cast<Constant>(U)) {
1555 for (User *UU : C->users())
1556 Worklist.push_back(UU);