[FuncSpec] Do not generate multiple copies for identical specializations.

[labrinea]

Summary

Fix for the problem shown in D135459.

[chill]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

411

Avoid C-style casts. It should work as hash_value(ArrayRef<ArgInfo>(Info.Args));

413

This is not correct, if the hash values clash two different specialisation will be regarded as the same and one will be discarded.

414

Discarding duplicates should happen before we decide which of the possible specialisations to perform. For example, in calculateGains the MaxClonedThreshold limit is applied on a list, which potentially contains duplicates.

419

This looks like a big redundancy, we traverse all the call sites of F for each specialisation while all we need is traverse all the call sites of F once and redirect the call site to the correct specialisation.

424

So the idea here is, when specializing on the second parameter only, to turn

void g(int x, int y) {
...
  g(x, y);
...
}
...
g(1, 2);

into

void g.1(int x, /* unused */ int y) {
...
  g.1(x, 2);
...
}
...
g.1(1, 2);

But the same ought to happen for:

void g(int x, int y) {
...
  g(x, 2);
...
}
...
g(1, 2);

and it looks to me the test will miss it because it will compare 2 (from the call argument) to y in the cloned function.

(Similar issue in the original code as well).

[chill]

llvm/include/llvm/Transforms/Utils/SCCPSolver.h

56

I don't really see the point in creating the temporary pair.

return hash_combine(Info.Formal, Info.Actual)

[labrinea]

This adds just a 0.03% geomean overhead in terms of instruction count for CTMark (llvmtestsuite O3+NewPM) over the parent revision D126455 (with specialization of functions enabled).

[chill]

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

82

This has to be a DenseSet. std::set has logarithmic complexity of operations.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

364

Here evaluation of the gain occurs even if the specialization is a duplicate.
I would expect getSpecializationBonus to take non-negligible time.

441

(nit) This function return Close twice, once as a return value and once as an out argument. A cleaner design would be to just return the value as the function does not depend on the Clone member variable and need not know anything about it.

[labrinea]

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

82

DenseSet is more expensive to iterate on. I have another patch which sorts the specializations globally (across module, not per function) where I keep the specializations sorted in a std::multiset and I use std::merge to unite the two sets. That's relatively cheap as it doesn't perform copies of objects but shuffles pointers around. Also that multiset is iterated a lot more than the set I am adding here. The compexity is logarithmic to the number of callsites, still not a huge number in my opinion.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

364

This is already happening, but good point there's room for improvement.

441

I cached the Clone pointer to the SpecInfo for the parent revision D126455, so that updateCallSites() does not rely on two vectors (clones, specialziations) being in sync. So you are suggesting to not set the member variable here, but after returning from this function?

[chill]

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

82

This should be a comparison function which induces strict weak ordering on the elements.

[labrinea]

Added strict weak ordering for the elements inserted to std::set.

[labrinea]

llvm/lib/Transforms/IPO/SCCP.cpp

46 ↗

(On Diff #481216)

oops

[labrinea]

This patch achieves the same as D139346 with ~0.001% (geomean) increase of Instruction Count for CTMark (LTO) or ~0.033% (geomean) increase of execution time (user+system) for the IPSCCP pass. I am abandoning this patch in favor of D139346.

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

 #include "llvm/Transforms/Utils/SCCPSolver.h"
 #include "llvm/Transforms/Utils/SizeOpts.h"
 
 using namespace llvm;
 
 namespace llvm {
 // Bookkeeping struct to pass data from the analysis and profitability phase
 // to the actual transform helper functions.
-struct SpecializationInfo {
+struct SpecInfo {
   SmallVector<ArgInfo, 8> Args; // Stores the {formal,actual} argument pairs.
   InstructionCost Gain;         // Profitability: Gain = Bonus - Cost.
   Function *Clone;              // The definition of the specialized function.
+
+  bool operator==(const SpecInfo &Other) const {
+    if (Args.size() != Other.Args.size())
+      return false;
+    for (size_t I = 0; I < Args.size(); ++I)
+      if (Args[I] != Other.Args[I])
+        return false;
+    return true;
+  }
+
+  bool operator!=(const SpecInfo &Other) const { return !(*this == Other); }
 };
 
-using CallSpecBinding = std::pair<CallBase *, SpecializationInfo>;
-// We are using MapVector because it guarantees deterministic iteration
-// order across executions.
-using SpecializationMap = SmallMapVector<CallBase *, SpecializationInfo, 8>;
+using UniqueSpecSet = std::set<SpecInfo, std::not_equal_to<SpecInfo>>;
 
 class FunctionSpecializer {
 
   /// The IPSCCP Solver.
   SCCPSolver &Solver;
 
   Module &M;
 
private:
 
   /// This function decides whether it's worthwhile to specialize function
   /// \p F based on the known constant values its arguments can take on. It
   /// only discovers potential specialization opportunities without actually
   /// applying them.
   ///
   /// \returns true if any specializations have been found.
   bool findSpecializations(Function *F, InstructionCost Cost,
-                           SmallVectorImpl<CallSpecBinding> &WorkList);
+                           SmallVectorImpl<SpecInfo> &WorkList);
 
   bool isCandidateFunction(Function *F);
 
-  Function *createSpecialization(Function *F, CallSpecBinding &Specialization);
+  Function *createSpecialization(Function *F, SpecInfo &Specialization);
 
   /// Compute and return the cost of specializing function \p F.
   InstructionCost getSpecializationCost(Function *F);
 
   /// Compute a bonus for replacing argument \p A with constant \p C.
   InstructionCost getSpecializationBonus(Argument *A, Constant *C,
                                          const LoopInfo &LI);
 
   /// Determine if it is possible to specialise the function for constant values
   /// of the formal parameter \p A.
   bool isArgumentInteresting(Argument *A);
 
   /// Check if the value \p V  (an actual argument) is a constant or can only
   /// have a constant value. Return that constant.
   Constant *getCandidateConstant(Value *V);
 
   /// Redirects callsites of function \p F to its specialized copies.
-  void updateCallSites(Function *F,
-                       SmallVectorImpl<CallSpecBinding> &Specializations);
+  void updateCallSites(Function *F, SmallVectorImpl<SpecInfo> &Specializations);
 };
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H

llvm/include/llvm/Transforms/Utils/SCCPSolver.h

struct AnalysisResultsForFn {
   LoopInfo *LI;
 };
 
 /// Helper struct shared between Function Specialization and SCCP Solver.
 struct ArgInfo {
   Argument *Formal; // The Formal argument being analysed.
   Constant *Actual; // A corresponding actual constant argument.
 
-  ArgInfo(Argument *F, Constant *A) : Formal(F), Actual(A){};
+  ArgInfo(Argument *F, Constant *A) : Formal(F), Actual(A) {};
+
+  bool operator==(const ArgInfo &Other) const {
+    return Formal == Other.Formal && Actual == Other.Actual;
+  }
+
+  bool operator!=(const ArgInfo &Other) const { return !(*this == Other); }
 };
 
 class SCCPInstVisitor;
 
 //===----------------------------------------------------------------------===//
 //
 /// SCCPSolver - This interface class is a general purpose solver for Sparse
 /// Conditional Constant Propagation (SCCP).

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

for (Function &F : M) {
     if (!Cost.isValid()) {
       LLVM_DEBUG(dbgs() << "FnSpecialization: Invalid specialization cost.\n");
       continue;
     }
 
     LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization cost for "
                       << F.getName() << " is " << Cost << "\n");
 
-    SmallVector<CallSpecBinding, 8> Specializations;
+    SmallVector<SpecInfo, 8> Specializations;
     if (!findSpecializations(&F, Cost, Specializations)) {
       LLVM_DEBUG(
           dbgs() << "FnSpecialization: No possible specializations found\n");
       continue;
     }
 
     Changed = true;
 
     SmallVector<Function *, 4> Clones;
-    for (CallSpecBinding &Specialization : Specializations)
+    for (SpecInfo &Specialization : Specializations)
       Clones.push_back(createSpecialization(&F, Specialization));
 
     Solver.solveWhileResolvedUndefsIn(Clones);
     updateCallSites(&F, Specializations);
   }
 
   promoteConstantStackValues();
 

 }
 
 /// This function decides whether it's worthwhile to specialize function
 /// \p F based on the known constant values its arguments can take on. It
 /// only discovers potential specialization opportunities without actually
 /// applying them.
 ///
 /// \returns true if any specializations have been found.
-bool FunctionSpecializer::findSpecializations(
-    Function *F, InstructionCost Cost,
-    SmallVectorImpl<CallSpecBinding> &WorkList) {
+bool
+FunctionSpecializer::findSpecializations(Function *F, InstructionCost Cost,
+                                         SmallVectorImpl<SpecInfo> &WorkList) {
   // Get a list of interesting arguments.
   SmallVector<Argument *, 4> Args;
   for (Argument &Arg : F->args())
     if (isArgumentInteresting(&Arg))
       Args.push_back(&Arg);
 
   if (!Args.size())
     return false;
 
   // Find all the call sites for the function.
-  SpecializationMap Specializations;
+  UniqueSpecSet UniqueSpecs;
   for (User *U : F->users()) {
     if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
       continue;
     auto &CS = *cast<CallBase>(U);
 
     // Skip irrelevant users.
     if (CS.getCalledFunction() != F)
       continue;
 
     // If the call site has attribute minsize set, that callsite won't be
     // specialized.
     if (CS.hasFnAttr(Attribute::MinSize))
       continue;
 
     // If the parent of the call site will never be executed, we don't need
     // to worry about the passed value.
     if (!Solver.isBlockExecutable(CS.getParent()))
       continue;
 
     // Examine arguments and create specialization candidates from call sites
     // with constant arguments.
-    bool Added = false;
+    SpecInfo Spec{{}, 0 - Cost, /*Clone=*/nullptr};
     for (Argument *A : Args) {
       Constant *C = getCandidateConstant(CS.getArgOperand(A->getArgNo()));
       if (!C)
         continue;
 
-      if (!Added) {
-        Specializations[&CS] = {{}, 0 - Cost, nullptr};
-        Added = true;
-      }
-
-      SpecializationInfo &S = Specializations.back().second;
-      S.Gain += getSpecializationBonus(A, C, Solver.getLoopInfo(*F));
-      S.Args.push_back({A, C});
-    }
-    Added = false;
+      Spec.Gain += getSpecializationBonus(A, C, Solver.getLoopInfo(*F));
+      Spec.Args.push_back({A, C});
+    if (!Spec.Args.empty() && (Spec.Gain > 0 || ForceFunctionSpecialization))
+      UniqueSpecs.insert(std::move(Spec));
   }
 
-  // Remove unprofitable specializations.
-  if (!ForceFunctionSpecialization)
-    Specializations.remove_if(
-        [](const auto &Entry) { return Entry.second.Gain <= 0; });
-
-  // Clear the MapVector and return the underlying vector.
-  WorkList = Specializations.takeVector();
+  WorkList.append(UniqueSpecs.begin(), UniqueSpecs.end());
 
   // Sort the candidates in descending order.
   llvm::stable_sort(WorkList, [](const auto &L, const auto &R) {
-    return L.second.Gain > R.second.Gain;
+    return L.Gain > R.Gain;
   });
 
   // Truncate the worklist to 'MaxClonesThreshold' candidates if necessary.
   if (WorkList.size() > MaxClonesThreshold) {
     LLVM_DEBUG(dbgs() << "FnSpecialization: Number of candidates exceed "
                       << "the maximum number of clones threshold.\n"
                       << "FnSpecialization: Truncating worklist to "
                       << MaxClonesThreshold << " candidates.\n");
     WorkList.erase(WorkList.begin() + MaxClonesThreshold, WorkList.end());
   }
 
   LLVM_DEBUG(dbgs() << "FnSpecialization: Specializations for function "
                     << F->getName() << "\n";
-             for (const auto &Entry
-                  : WorkList) {
-               dbgs() << "FnSpecialization:   Gain = " << Entry.second.Gain
-                      << "\n";
-               for (const ArgInfo &Arg : Entry.second.Args)
+             for (const SpecInfo &Spec : WorkList) {
+               dbgs() << "FnSpecialization:   Gain = " << Spec.Gain << "\n";
+               for (const ArgInfo &Arg : Spec.Args)
                  dbgs() << "FnSpecialization:   FormalArg = "
                         << Arg.Formal->getNameOrAsOperand()
                         << ", ActualArg = " << Arg.Actual->getNameOrAsOperand()
                         << "\n";
              });
 
   return !WorkList.empty();
 }
 
 bool FunctionSpecializer::isCandidateFunction(Function *F) {
   if (F->isDeclaration())
     return false;
 
   if (F->hasFnAttribute(Attribute::NoDuplicate))
     return false;
 
   if (!Solver.isArgumentTrackedFunction(F))
     return false;
 
   // Do not specialize the cloned function again.
   if (SpecializedFuncs.contains(F))
     return false;
 
   // If we're optimizing the function for size, we shouldn't specialize it.
   if (F->hasOptSize() ||
       shouldOptimizeForSize(F, nullptr, nullptr, PGSOQueryType::IRPass))
     return false;
 
   // Exit if the function is not executable. There's no point in specializing
   // a dead function.
   if (!Solver.isBlockExecutable(&F->getEntryBlock()))
     return false;
 
   // It wastes time to specialize a function which would get inlined finally.
   if (F->hasFnAttribute(Attribute::AlwaysInline))
     return false;
 
   LLVM_DEBUG(dbgs() << "FnSpecialization: Try function: " << F->getName()
                     << "\n");
   return true;
 }
 
 Function *
 FunctionSpecializer::createSpecialization(Function *F,
-                                          CallSpecBinding &Specialization) {
+                                          SpecInfo &Specialization) {
   Function *Clone = cloneCandidateFunction(F);
-  Specialization.second.Clone = Clone;
+  Specialization.Clone = Clone;
 
   // Initialize the lattice state of the arguments of the function clone,
   // marking the argument on which we specialized the function constant
   // with the given value.
-  Solver.markArgInFuncSpecialization(Clone, Specialization.second.Args);
+  Solver.markArgInFuncSpecialization(Clone, Specialization.Args);
 
   Solver.addArgumentTrackedFunction(Clone);
   Solver.markBlockExecutable(&Clone->front());
 
   // Mark all the specialized functions
   SpecializedFuncs.insert(Clone);
   NbFunctionsSpecialized++;
 
Constant *FunctionSpecializer::getCandidateConstant(Value *V) {
   LLVM_DEBUG(dbgs() << "FnSpecialization: Found interesting argument "
                     << V->getNameOrAsOperand() << "\n");
 
   return C;
 }
 
 /// Redirects callsites of function \p F to its specialized copies.
 void FunctionSpecializer::updateCallSites(
-    Function *F, SmallVectorImpl<CallSpecBinding> &Specializations) {
+    Function *F, SmallVectorImpl<SpecInfo> &Specializations) {
   SmallVector<CallBase *, 8> ToUpdate;
   for (User *U : F->users()) {
     if (auto *CS = dyn_cast<CallBase>(U))
       if (CS->getCalledFunction() == F &&
           Solver.isBlockExecutable(CS->getParent()))
         ToUpdate.push_back(CS);
   }
 
   unsigned NCallsLeft = ToUpdate.size();
   for (CallBase *CS : ToUpdate) {
     // Decrement the counter if the callsite is either recursive or updated.
     bool ShouldDecrementCount = CS->getFunction() == F;
-    for (CallSpecBinding &Specialization : Specializations) {
-      Function *Clone = Specialization.second.Clone;
-      SmallVectorImpl<ArgInfo> &Args = Specialization.second.Args;
+    for (SpecInfo &Specialization : Specializations) {
+      Function *Clone = Specialization.Clone;
+      SmallVectorImpl<ArgInfo> &Args = Specialization.Args;
 
       if (any_of(Args, [CS, this](const ArgInfo &Arg) {
             unsigned ArgNo = Arg.Formal->getArgNo();
             return getCandidateConstant(CS->getArgOperand(ArgNo)) != Arg.Actual;
           }))
         continue;
 
       LLVM_DEBUG(dbgs() << "FnSpecialization: Replacing call site " << *CS

llvm/test/Transforms/FunctionSpecialization/function-specialization-constant-expression.ll

entry:
   ret i64 %tmp0
 }
 
 define internal i64 @zoo(i1 %flag) {
 ; CHECK-LABEL: @zoo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[FLAG:%.*]], label [[PLUS:%.*]], label [[MINUS:%.*]]
 ; CHECK:       plus:
-; CHECK-NEXT:    [[TMP0:%.*]] = call i64 @func2.2(i64* getelementptr inbounds ([[STRUCT:%.*]], %struct* @Global, i32 0, i32 3))
+; CHECK-NEXT:    [[TMP0:%.*]] = call i64 @func2.1(i64* getelementptr inbounds ([[STRUCT:%.*]], %struct* @Global, i32 0, i32 3))
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       minus:
-; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @func2.1(i64* getelementptr inbounds ([[STRUCT]], %struct* @Global, i32 0, i32 4))
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @func2.2(i64* getelementptr inbounds ([[STRUCT]], %struct* @Global, i32 0, i32 4))
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
 ; CHECK-NEXT:    [[TMP2:%.*]] = phi i64 [ [[TMP0]], [[PLUS]] ], [ [[TMP1]], [[MINUS]] ]
 ; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 entry:
   br i1 %flag, label %plus, label %minus
 

llvm/test/Transforms/FunctionSpecialization/function-specialization-constant-expression3.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -ipsccp -specialize-functions -force-function-specialization -S < %s | FileCheck %s
 
 define i32 @main() {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    tail call void @wombat.1(i8* undef, i64 undef, i64 undef, i32 (i8*, i8*)* bitcast (i32 ()* @quux to i32 (i8*, i8*)*))
-; CHECK-NEXT:    tail call void @wombat.2(i8* undef, i64 undef, i64 undef, i32 (i8*, i8*)* bitcast (i32 ()* @eggs to i32 (i8*, i8*)*))
+; CHECK-NEXT:    tail call void @wombat.2(i8* undef, i64 undef, i64 undef, i32 (i8*, i8*)* bitcast (i32 ()* @quux to i32 (i8*, i8*)*))
+; CHECK-NEXT:    tail call void @wombat.1(i8* undef, i64 undef, i64 undef, i32 (i8*, i8*)* bitcast (i32 ()* @eggs to i32 (i8*, i8*)*))
 ; CHECK-NEXT:    ret i32 undef
 ;
 bb:
   tail call void @wombat(i8* undef, i64 undef, i64 undef, i32 (i8*, i8*)* bitcast (i32 ()* @quux to i32 (i8*, i8*)*))
   tail call void @wombat(i8* undef, i64 undef, i64 undef, i32 (i8*, i8*)* bitcast (i32 ()* @eggs to i32 (i8*, i8*)*))
   ret i32 undef
 }
 
 declare i32 @quux()
 declare i32 @eggs()
 
 define internal void @wombat(i8* %arg, i64 %arg1, i64 %arg2, i32 (i8*, i8*)* %arg3) {
 bb4:
   %tmp = tail call i32 %arg3(i8* undef, i8* undef)
   ret void
 }

llvm/test/Transforms/FunctionSpecialization/function-specialization-nonconst-glob.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 
 ; RUN: opt -ipsccp -specialize-functions -force-function-specialization -S < %s | FileCheck %s
 ; RUN: opt -ipsccp -specialize-functions -force-function-specialization -func-specialization-on-address=0 -S < %s | FileCheck %s
 ; RUN: opt -ipsccp -specialize-functions -force-function-specialization -func-specialization-on-address=1 -S < %s | FileCheck %s --check-prefix=ON-ADDRESS
 
 ; Global B is not constant. We do not specialise on addresses unless we
 ; enable that:
 
-; ON-ADDRESS: call i32 @foo.1(i32 %x, i32* @A)
-; ON-ADDRESS: call i32 @foo.2(i32 %y, i32* @B)
+; ON-ADDRESS: call i32 @foo.2(i32 %x, i32* @A)
+; ON-ADDRESS: call i32 @foo.1(i32 %y, i32* @B)
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
 @A = external dso_local constant i32, align 4
 @B = external dso_local global i32, align 4
 
 define dso_local i32 @bar(i32 %x, i32 %y) {
 ; CHECK-LABEL: @bar(

llvm/test/Transforms/FunctionSpecialization/function-specialization.ll

 ; RUN: opt -ipsccp -specialize-functions -func-specialization-size-threshold=3 -S < %s | FileCheck %s
 
 define i64 @main(i64 %x, i1 %flag) {
 ;
 ; CHECK-LABEL: @main(i64 %x, i1 %flag) {
 ; CHECK:      entry:
 ; CHECK-NEXT:   br i1 %flag, label %plus, label %minus
 ; CHECK:      plus:
-; CHECK-NEXT:   [[TMP0:%.+]] = call i64 @compute.1(i64 %x, i64 (i64)* @plus)
+; CHECK-NEXT:   [[TMP0:%.+]] = call i64 @compute.2(i64 %x, i64 (i64)* @plus)
 ; CHECK-NEXT:   br label %merge
 ; CHECK:      minus:
-; CHECK-NEXT:   [[TMP1:%.+]] = call i64 @compute.2(i64 %x, i64 (i64)* @minus)
+; CHECK-NEXT:   [[TMP1:%.+]] = call i64 @compute.1(i64 %x, i64 (i64)* @minus)
 ; CHECK-NEXT:   br label %merge
 ; CHECK:      merge:
 ; CHECK-NEXT:   [[TMP2:%.+]] = phi i64 [ [[TMP0]], %plus ], [ [[TMP1]], %minus ]
 ; CHECK-NEXT:   ret i64 [[TMP2]]
 ; CHECK-NEXT: }
 ;
 entry:
   br i1 %flag, label %plus, label %minus
merge:
   %tmp2 = phi i64 [ %tmp0, %plus ], [ %tmp1, %minus]
   ret i64 %tmp2
 }
 
 ; CHECK-NOT: define internal i64 @compute(
 ;
 ; CHECK-LABEL: define internal i64 @compute.1(i64 %x, i64 (i64)* %binop) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.+]] = call i64 @plus(i64 %x)
+; CHECK-NEXT:    [[TMP0:%.+]] = call i64 @minus(i64 %x)
 ; CHECK-NEXT:    ret i64 [[TMP0]]
 ; CHECK-NEXT:  }
 ;
 ; CHECK-LABEL: define internal i64 @compute.2(i64 %x, i64 (i64)* %binop) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.+]] = call i64 @minus(i64 %x)
+; CHECK-NEXT:    [[TMP0:%.+]] = call i64 @plus(i64 %x)
 ; CHECK-NEXT:    ret i64 [[TMP0]]
 ; CHECK-NEXT:  }
 ;
 define internal i64 @compute(i64 %x, i64 (i64)* %binop) {
 entry:
   %tmp0 = call i64 %binop(i64 %x)
   ret i64 %tmp0
 }

llvm/test/Transforms/FunctionSpecialization/function-specialization2.ll

 define internal void @decrement(i32* nocapture %0) {
   %2 = load i32, i32* %0, align 4
   %3 = add nsw i32 %2, -1
   store i32 %3, i32* %0, align 4
   ret void
 }
 
 define i32 @main(i32* %0, i32 %1) {
-; CHECK:    call void @func.2(i32* [[TMP0:%.*]], i32 [[TMP1:%.*]])
+; CHECK:    call void @func.1(i32* [[TMP0:%.*]], i32 [[TMP1:%.*]])
   %3 = call i32 @func(i32* %0, i32 %1, void (i32*)* nonnull @increment)
-; CHECK:    call void @func.1(i32* [[TMP0]], i32 0)
+; CHECK:    call void @func.2(i32* [[TMP0]], i32 0)
   %4 = call i32 @func(i32* %0, i32 %3, void (i32*)* nonnull @decrement)
 ; CHECK:    ret i32 0
   ret i32 %4
 }
 
 ; CHECK: @func.1(
 ; CHECK:    [[TMP3:%.*]] = alloca i32, align 4
 ; CHECK:    store i32 [[TMP1:%.*]], i32* [[TMP3]], align 4
 ; CHECK:    [[TMP4:%.*]] = load i32, i32* [[TMP3]], align 4
 ; CHECK:    [[TMP5:%.*]] = icmp slt i32 [[TMP4]], 1
 ; CHECK:    br i1 [[TMP5]], label [[TMP13:%.*]], label [[TMP6:%.*]]
 ; CHECK:       6:
 ; CHECK:    [[TMP7:%.*]] = load i32, i32* [[TMP3]], align 4
 ; CHECK:    [[TMP8:%.*]] = sext i32 [[TMP7]] to i64
 ; CHECK:    [[TMP9:%.*]] = getelementptr inbounds i32, i32* [[TMP0:%.*]], i64 [[TMP8]]
-; CHECK:    call void @decrement(i32* [[TMP9]])
+; CHECK:    call void @increment(i32* [[TMP9]])
 ; CHECK:    [[TMP10:%.*]] = load i32, i32* [[TMP3]], align 4
 ; CHECK:    [[TMP11:%.*]] = add nsw i32 [[TMP10]], -1
 ; CHECK:    call void @func.1(i32* [[TMP0]], i32 [[TMP11]])
 ; CHECK:    br label [[TMP12:%.*]]
 ; CHECK:       12:
 ; CHECK:    ret void
 ;
 ;
 ; CHECK: @func.2(
 ; CHECK:    [[TMP3:%.*]] = alloca i32, align 4
 ; CHECK:    store i32 [[TMP1:%.*]], i32* [[TMP3]], align 4
 ; CHECK:    [[TMP4:%.*]] = load i32, i32* [[TMP3]], align 4
 ; CHECK:    [[TMP5:%.*]] = icmp slt i32 [[TMP4]], 1
 ; CHECK:    br i1 [[TMP5]], label [[TMP13:%.*]], label [[TMP6:%.*]]
 ; CHECK:       6:
 ; CHECK:    [[TMP7:%.*]] = load i32, i32* [[TMP3]], align 4
 ; CHECK:    [[TMP8:%.*]] = sext i32 [[TMP7]] to i64
 ; CHECK:    [[TMP9:%.*]] = getelementptr inbounds i32, i32* [[TMP0:%.*]], i64 [[TMP8]]
-; CHECK:    call void @increment(i32* [[TMP9]])
+; CHECK:    call void @decrement(i32* [[TMP9]])
 ; CHECK:    [[TMP10:%.*]] = load i32, i32* [[TMP3]], align 4
 ; CHECK:    [[TMP11:%.*]] = add nsw i32 [[TMP10]], -1
 ; CHECK:    call void @func.2(i32* [[TMP0]], i32 [[TMP11]])
 ; CHECK:    br label [[TMP12:%.*]]
 ; CHECK:       12:
 ; CHECK:    ret void

llvm/test/Transforms/FunctionSpecialization/function-specialization3.ll

 ; RUN: opt -ipsccp -specialize-functions -func-specialization-avg-iters-cost=3 -S < %s | \
 ; RUN:   FileCheck %s --check-prefixes=COMMON,DISABLED
 ; RUN: opt -ipsccp -specialize-functions -force-function-specialization -S < %s | \
 ; RUN:   FileCheck %s --check-prefixes=COMMON,FORCE
 ; RUN: opt -ipsccp -specialize-functions -func-specialization-avg-iters-cost=3 -force-function-specialization -S < %s | \
 ; RUN:   FileCheck %s --check-prefixes=COMMON,FORCE
 
 ; Test for specializing a constant global.
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
 @A = external dso_local constant i32, align 4
 @B = external dso_local constant i32, align 4
 
 define dso_local i32 @bar(i32 %x, i32 %y) {
 ; COMMON-LABEL: @bar
-; FORCE:        %call = call i32 @foo.1(i32 %x, i32* @A)
-; FORCE:        %call1 = call i32 @foo.2(i32 %y, i32* @B)
+; FORCE:        %call = call i32 @foo.2(i32 %x, i32* @A)
+; FORCE:        %call1 = call i32 @foo.1(i32 %y, i32* @B)
 ; DISABLED-NOT: %call1 = call i32 @foo.1(
 entry:
   %tobool = icmp ne i32 %x, 0
   br i1 %tobool, label %if.then, label %if.else
 
 if.then:
   %call = call i32 @foo(i32 %x, i32* @A)
   br label %return
 
 if.else:
   %call1 = call i32 @foo(i32 %y, i32* @B)
   br label %return
 
 return:
   %retval.0 = phi i32 [ %call, %if.then ], [ %call1, %if.else ]
   ret i32 %retval.0
 }
 
 ; FORCE-NOT: define internal i32 @foo(
 ;
 ; FORCE:      define internal i32 @foo.1(i32 %x, i32* %b) {
 ; FORCE-NEXT: entry:
-; FORCE-NEXT:   %0 = load i32, i32* @A, align 4
+; FORCE-NEXT:   %0 = load i32, i32* @B, align 4
 ; FORCE-NEXT:   %add = add nsw i32 %x, %0
 ; FORCE-NEXT:   ret i32 %add
 ; FORCE-NEXT: }
 ;
 ; FORCE:      define internal i32 @foo.2(i32 %x, i32* %b) {
 ; FORCE-NEXT: entry:
-; FORCE-NEXT:   %0 = load i32, i32* @B, align 4
+; FORCE-NEXT:   %0 = load i32, i32* @A, align 4
 ; FORCE-NEXT:   %add = add nsw i32 %x, %0
 ; FORCE-NEXT:   ret i32 %add
 ; FORCE-NEXT: }
 ;
 define internal i32 @foo(i32 %x, i32* %b) {
 entry:
   %0 = load i32, i32* %b, align 4
   %add = add nsw i32 %x, %0
   ret i32 %add
 }

llvm/test/Transforms/FunctionSpecialization/function-specialization4.ll

entry:
   ret i32 %add1
 }
 
 ; CONST1:     define internal i32 @foo.1(i32 %x, i32* %b, i32* %c)
 ; CONST1-NOT: define internal i32 @foo.2(i32 %x, i32* %b, i32* %c)
 
 ; CHECK:        define internal i32 @foo.1(i32 %x, i32* %b, i32* %c) {
 ; CHECK-NEXT:   entry:
-; CHECK-NEXT:     %0 = load i32, i32* @A, align 4
+; CHECK-NEXT:     %0 = load i32, i32* @B, align 4
 ; CHECK-NEXT:     %add = add nsw i32 %x, %0
-; CHECK-NEXT:     %1 = load i32, i32* @C, align 4
+; CHECK-NEXT:     %1 = load i32, i32* @D, align 4
 ; CHECK-NEXT:     %add1 = add nsw i32 %add, %1
 ; CHECK-NEXT:     ret i32 %add1
 ; CHECK-NEXT:   }
 
 ; CHECK: define internal i32 @foo.2(i32 %x, i32* %b, i32* %c) {
 ; CHECK-NEXT:   entry:
-; CHECK-NEXT:     %0 = load i32, i32* @B, align 4
+; CHECK-NEXT:     %0 = load i32, i32* @A, align 4
 ; CHECK-NEXT:     %add = add nsw i32 %x, %0
-; CHECK-NEXT:     %1 = load i32, i32* @D, align 4
+; CHECK-NEXT:     %1 = load i32, i32* @C, align 4
 ; CHECK-NEXT:     %add1 = add nsw i32 %add, %1
 ; CHECK-NEXT:     ret i32 %add1
 ; CHECK-NEXT:   }

llvm/test/Transforms/FunctionSpecialization/identical-specializations.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=ipsccp -specialize-functions -force-function-specialization -S < %s | FileCheck %s
 
 define i64 @main(i64 %x, i64 %y, i1 %flag) {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[FLAG:%.*]], label [[PLUS:%.*]], label [[MINUS:%.*]]
 ; CHECK:       plus:
-; CHECK-NEXT:    [[CMP0:%.*]] = call i64 @compute.1(i64 [[X:%.*]], i64 [[Y:%.*]], i64 (i64, i64)* @plus, i64 (i64, i64)* @minus)
+; CHECK-NEXT:    [[CMP0:%.*]] = call i64 @compute.2(i64 [[X:%.*]], i64 [[Y:%.*]], i64 (i64, i64)* @plus, i64 (i64, i64)* @minus)
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       minus:
-; CHECK-NEXT:    [[CMP1:%.*]] = call i64 @compute.2(i64 [[X]], i64 [[Y]], i64 (i64, i64)* @minus, i64 (i64, i64)* @plus)
+; CHECK-NEXT:    [[CMP1:%.*]] = call i64 @compute.1(i64 [[X]], i64 [[Y]], i64 (i64, i64)* @minus, i64 (i64, i64)* @plus)
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
 ; CHECK-NEXT:    [[PH:%.*]] = phi i64 [ [[CMP0]], [[PLUS]] ], [ [[CMP1]], [[MINUS]] ]
-; CHECK-NEXT:    [[CMP2:%.*]] = call i64 @compute.1(i64 [[PH]], i64 42, i64 (i64, i64)* @plus, i64 (i64, i64)* @minus)
+; CHECK-NEXT:    [[CMP2:%.*]] = call i64 @compute.2(i64 [[PH]], i64 42, i64 (i64, i64)* @plus, i64 (i64, i64)* @minus)
 ; CHECK-NEXT:    ret i64 [[CMP2]]
 ;
 entry:
   br i1 %flag, label %plus, label %minus
 
 plus:
   %cmp0 = call i64 @compute(i64 %x, i64 %y, i64 (i64, i64)* @plus, i64 (i64, i64)* @minus)
   br label %merge

 
 define internal i64 @minus(i64 %x, i64 %y) {
 ; CHECK-LABEL: @minus(
 entry:
   %sub = sub i64 %x, %y
   ret i64 %sub
 }
 
-; CHECK-LABEL: @compute.1
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP0:%.*]] = call i64 @plus(i64 [[X:%.*]], i64 [[Y:%.*]])
-; CHECK-NEXT:    [[CMP1:%.*]] = call i64 @minus(i64 [[X]], i64 [[Y]])
-; CHECK-NEXT:    [[CMP2:%.*]] = call i64 @compute(i64 [[X]], i64 [[Y]], i64 (i64, i64)* @plus, i64 (i64, i64)* @plus)
-
-; CHECK-LABEL: @compute.2
+; CHECK: define internal i64 @compute.1
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP0:%.*]] = call i64 @minus(i64 [[X:%.*]], i64 [[Y:%.*]])
 ; CHECK-NEXT:    [[CMP1:%.*]] = call i64 @plus(i64 [[X]], i64 [[Y]])
-; CHECK-NEXT:    [[CMP2:%.*]] = call i64 @compute.2(i64 [[X]], i64 [[Y]], i64 (i64, i64)* @minus, i64 (i64, i64)* @plus)
+; CHECK-NEXT:    [[CMP2:%.*]] = call i64 @compute.1(i64 [[X]], i64 [[Y]], i64 (i64, i64)* @minus, i64 (i64, i64)* @plus)
 
-; CHECK-LABEL: @compute.3
+; CHECK: define internal i64 @compute.2
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP0:%.*]] = call i64 @plus(i64 [[X:%.*]], i64 [[Y:%.*]])
 ; CHECK-NEXT:    [[CMP1:%.*]] = call i64 @minus(i64 [[X]], i64 [[Y]])
-; CHECK-NEXT:    [[CMP2:%.*]] = call i64 @compute(i64 [[X]], i64 [[Y]], i64 (i64, i64)* @plus, i64 (i64, i64)* @plus)
+; CHECK-NEXT:    [[CMP2:%.*]] = call i64 @compute.3(i64 [[X]], i64 [[Y]], i64 (i64, i64)* @plus, i64 (i64, i64)* @plus)
+
+; CHECK: define internal i64 @compute.3
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP0:%.*]] = call i64 %binop1(i64 [[X:%.*]], i64 [[Y:%.*]])
+; CHECK-NEXT:    [[CMP1:%.*]] = call i64 @plus(i64 [[X]], i64 [[Y]])
+; CHECK-NEXT:    [[CMP2:%.*]] = call i64 @compute.3(i64 [[X]], i64 [[Y]], i64 (i64, i64)* %binop1, i64 (i64, i64)* @plus)

llvm/test/Transforms/FunctionSpecialization/remove-dead-recursive-function.ll

 merge:
   %tmp2 = phi i64 [ %tmp0, %plus ], [ %tmp1, %minus]
   ret i64 %tmp2
 }
 
 ; CHECK-NOT: define internal i64 @compute(
 ;
 ; CHECK-LABEL: define internal i64 @compute.1(i64 %n, i64 (i64)* %binop) {
-; CHECK:  [[TMP0:%.+]] = call i64 @plus(i64 %n)
-; CHECK:  [[TMP1:%.+]] = call i64 @compute.1(i64 [[TMP2:%.+]], i64 (i64)* @plus)
+; CHECK:  [[TMP0:%.+]] = call i64 @minus(i64 %n)
+; CHECK:  [[TMP1:%.+]] = call i64 @compute.1(i64 [[TMP2:%.+]], i64 (i64)* @minus)
 ; CHECK:  add nsw i64 [[TMP1]], [[TMP0]]
 ;
 ; CHECK-LABEL: define internal i64 @compute.2(i64 %n, i64 (i64)* %binop) {
-; CHECK:  [[TMP0:%.+]] = call i64 @minus(i64 %n)
-; CHECK:  [[TMP1:%.+]] = call i64 @compute.2(i64 [[TMP2:%.+]], i64 (i64)* @minus)
+; CHECK:  [[TMP0:%.+]] = call i64 @plus(i64 %n)
+; CHECK:  [[TMP1:%.+]] = call i64 @compute.2(i64 [[TMP2:%.+]], i64 (i64)* @plus)
 ; CHECK:  add nsw i64 [[TMP1]], [[TMP0]]
 ;
 define internal i64 @compute(i64 %n, i64 (i64)* %binop) {
 entry:
   %cmp = icmp sgt i64 %n, 0
   br i1 %cmp, label %if.then, label %if.end
 
 if.then:

llvm/test/Transforms/FunctionSpecialization/specialization-order.ll

entry:
   %call = tail call i32 %u(i32 %x, i32 %y)
   %call1 = tail call i32 %v(i32 %x, i32 %y)
   %mul = mul nsw i32 %call1, %call
   ret i32 %mul
 }
 
 define dso_local i32 @g0(i32 %x, i32 %y) {
 ; CHECK-LABEL: @g0
-; CHECK:       call i32 @f.2(i32 [[X:%.*]], i32 [[Y:%.*]])
+; CHECK:       call i32 @f.1(i32 [[X:%.*]], i32 [[Y:%.*]])
 entry:
   %call = tail call i32 @f(i32 %x, i32 %y, ptr @add, ptr @add)
   ret i32 %call
 }
 
 
 define dso_local i32 @g1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @g1(
-; CHECK:       call i32 @f.1(i32 [[X:%.*]], i32 [[Y:%.*]])
+; CHECK:       call i32 @f.2(i32 [[X:%.*]], i32 [[Y:%.*]])
 entry:
   %call = tail call i32 @f(i32 %x, i32 %y, ptr @sub, ptr @add)
   ret i32 %call
 }
 
 define dso_local i32 @g2(i32 %x, i32 %y, ptr %v) {
 ; CHECK-LABEL @g2
 ; CHECK       call i32 @f.3(i32 [[X:%.*]], i32 [[Y:%.*]], ptr [[V:%.*]])
 entry:
   %call = tail call i32 @f(i32 %x, i32 %y, ptr @sub, ptr %v)
   ret i32 %call
 }
 
 ; CHECK-LABEL: define {{.*}} i32 @f.1
-; CHECK:       call i32 @sub(i32 %x, i32 %y)
+; CHECK:       call i32 @add(i32 %x, i32 %y)
 ; CHECK-NEXT:  call i32 @add(i32 %x, i32 %y)
 
 ; CHECK-LABEL: define {{.*}} i32 @f.2
-; CHECK:       call i32 @add(i32 %x, i32 %y)
+; CHECK:       call i32 @sub(i32 %x, i32 %y)
 ; CHECK-NEXT   call i32 @add(i32 %x, i32 %y)
 
 ; CHECK-LABEL: define {{.*}} i32 @f.3
 ; CHECK:       call i32 @sub(i32 %x, i32 %y)
 ; CHECK-NEXT:  call i32 %v(i32 %x, i32 %y)