[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

526

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

528

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

529

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.

534

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.

539

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

54

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 ↗

(On Diff #475864)

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

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

408–409

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

726–727

(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 ↗

(On Diff #475864)

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

408–409

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

726–727

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 ↗

(On Diff #475864)

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/Utils/SCCPSolver.h

 };
 
 /// 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){};
+
+  friend hash_code hash_value(const ArgInfo &Info) {
+    return hash_value(std::make_pair(Info.Formal, Info.Actual));
+  }
 };
 
 class SCCPInstVisitor;
 
 //===----------------------------------------------------------------------===//
 //
 /// SCCPSolver - This interface class is a general purpose solver for Sparse
 /// Conditional Constant Propagation (SCCP).

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

for (auto *F : Candidates) {
 
       SmallVector<CallSpecBinding, 8> Specializations;
       if (!calculateGains(F, Cost, Specializations)) {
         LLVM_DEBUG(dbgs() << "FnSpecialization: No possible constants found\n");
         continue;
       }
 
       Changed = true;
-      for (auto &Entry : Specializations)
-        specializeFunction(F, Entry.second, WorkList);
+      createSpecializations(Specializations, F, WorkList);
     }
 
     updateSpecializedFuncs(Candidates, WorkList);
     NumFuncSpecialized += NbFunctionsSpecialized;
     return Changed;
   }
 
   void removeDeadInstructions() {
if (I.second) {
         Metrics.analyzeBasicBlock(&BB, (GetTTI)(*F), EphValues);
 
       LLVM_DEBUG(dbgs() << "FnSpecialization: Code size of function "
                         << F->getName() << " is " << Metrics.NumInsts
                         << " instructions\n");
     }
     return Metrics;
   }
 
   /// Clone the function \p F and remove the ssa_copy intrinsics added by
   /// the SCCPSolver in the cloned version.
   Function *cloneCandidateFunction(Function *F, ValueToValueMapTy &Mappings) {
     Function *Clone = CloneFunction(F, Mappings);
     removeSSACopy(*Clone);
     return Clone;
   }
 
   /// This function decides whether it's worthwhile to specialize function
bool isCandidateFunction(Function *F) {
     if (F->hasFnAttribute(Attribute::AlwaysInline))
       return false;
 
     LLVM_DEBUG(dbgs() << "FnSpecialization: Try function: " << F->getName()
                       << "\n");
     return true;
   }
 
-  void specializeFunction(Function *F, SpecializationInfo &S,
-                          FuncList &WorkList) {
+  void createSpecializations(SmallVectorImpl<CallSpecBinding> &Specializations,
+                             Function *F, FuncList &WorkList) {
+    // Make sure we don't create multiple copies for the same specialization.
+    SmallDenseMap<size_t, Function *, 4> Clones;
+
+    for (const auto &Entry : Specializations) {
+      CallBase *Call = Entry.first;
+      const SpecializationInfo &Info = Entry.second;
+
+      // Create a copy of the function if it doesn't already exist.
+      hash_code Key = hash_value((ArrayRef<ArgInfo>)Info.Args);
+      auto Pair = Clones.insert({Key, nullptr});
+      Function *&Clone = Pair.first->second;
+      if (Pair.second) {
         ValueToValueMapTy Mappings;
-    Function *Clone = cloneCandidateFunction(F, Mappings);
+        Clone = cloneCandidateFunction(F, Mappings);
+        // Update recursive calls if their parameters are the same as the
+        // formal arguments of the specialization.
+        for (User *U : F->users())
+          if (auto CS = dyn_cast<CallBase>(U))
+            if (CS->getFunction() == Clone &&
+                all_of(Info.Args, [CS, &Mappings](const ArgInfo &Arg) {
+                    unsigned ArgNo = Arg.Formal->getArgNo();
+                    return CS->getArgOperand(ArgNo) == Mappings[Arg.Formal];
+                }))
+              CS->setCalledFunction(Clone);
+      }
 
-    // Rewrite calls to the function so that they call the clone instead.
-    rewriteCallSites(Clone, S.Args, Mappings);
+      // Update the call site.
+      Call->setCalledFunction(Clone);
+      Solver.markOverdefined(Call);
 
       // 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, S.Args);
+      Solver.markArgInFuncSpecialization(Clone, Info.Args);
 
       // Mark all the specialized functions
       WorkList.push_back(Clone);
       NbFunctionsSpecialized++;
 
       // If the function has been completely specialized, the original function
       // is no longer needed. Mark it unreachable.
       if (F->getNumUses() == 0 || all_of(F->users(), [F](User *U) {
             if (auto *CS = dyn_cast<CallBase>(U))
               return CS->getFunction() == F;
             return false;
           })) {
         Solver.markFunctionUnreachable(F);
         FullySpecialized.insert(F);
       }
     }
+  }
 
   /// Compute and return the cost of specializing function \p F.
   InstructionCost getSpecializationCost(Function *F) {
     CodeMetrics &Metrics = analyzeFunction(F);
     // If the code metrics reveal that we shouldn't duplicate the function, we
     // shouldn't specialize it. Set the specialization cost to Invalid.
     // Or if the lines of codes implies that this function is easy to get
     // inlined so that we shouldn't specialize it.
bool isArgumentInteresting(Argument *A,
     // model, so we would need to find the unique constants.
     //
     // TODO 2: this currently does not support constants, i.e. integer ranges.
     //
     getPossibleConstants(A, Constants);
 
     if (Constants.empty())
       return false;
 
     LLVM_DEBUG(dbgs() << "FnSpecialization: Found interesting argument "
                       << A->getNameOrAsOperand() << "\n");
     return true;
   }
 
   /// Collect in \p Constants all the constant values that argument \p A can
   /// take on.
   void getPossibleConstants(Argument *A,
                             SmallVectorImpl<CallArgBinding> &Constants) {
for (User *U : F->users()) {
       }
 
       if (isa<Constant>(V) && (Solver.getLatticeValueFor(V).isConstant() ||
                                EnableSpecializationForLiteralConstant))
         Constants.push_back({&CS, cast<Constant>(V)});
     }
   }
 
-  /// Rewrite calls to function \p F to call function \p Clone instead.
-  ///
-  /// This function modifies calls to function \p F as long as the actual
-  /// arguments match those in \p Args. Note that for recursive calls we
-  /// need to compare against the cloned formal arguments.
-  ///
-  /// Callsites that have been marked with the MinSize function attribute won't
-  /// be specialized and rewritten.
-  void rewriteCallSites(Function *Clone, const SmallVectorImpl<ArgInfo> &Args,
-                        ValueToValueMapTy &Mappings) {
-    assert(!Args.empty() && "Specialization without arguments");
-    Function *F = Args[0].Formal->getParent();
-
-    SmallVector<CallBase *, 8> CallSitesToRewrite;
-    for (auto *U : F->users()) {
-      if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
-        continue;
-      auto &CS = *cast<CallBase>(U);
-      if (!CS.getCalledFunction() || CS.getCalledFunction() != F)
-        continue;
-      CallSitesToRewrite.push_back(&CS);
-    }
-
-    LLVM_DEBUG(dbgs() << "FnSpecialization: Replacing call sites of "
-                      << F->getName() << " with " << Clone->getName() << "\n");
-
-    for (auto *CS : CallSitesToRewrite) {
-      LLVM_DEBUG(dbgs() << "FnSpecialization:   "
-                        << CS->getFunction()->getName() << " ->" << *CS
-                        << "\n");
-      if (/* recursive call */
-          (CS->getFunction() == Clone &&
-           all_of(Args,
-                  [CS, &Mappings](const ArgInfo &Arg) {
-                    unsigned ArgNo = Arg.Formal->getArgNo();
-                    return CS->getArgOperand(ArgNo) == Mappings[Arg.Formal];
-                  })) ||
-          /* normal call */
-          all_of(Args, [CS](const ArgInfo &Arg) {
-            unsigned ArgNo = Arg.Formal->getArgNo();
-            return CS->getArgOperand(ArgNo) == Arg.Actual;
-          })) {
-        CS->setCalledFunction(Clone);
-        Solver.markOverdefined(CS);
-      }
-    }
-  }
-
   void updateSpecializedFuncs(FuncList &Candidates, FuncList &WorkList) {
     for (auto *F : WorkList) {
       SpecializedFuncs.insert(F);
 
       // Initialize the state of the newly created functions, marking them
       // argument-tracked and executable.
       if (F->hasExactDefinition() && !F->hasFnAttribute(Attribute::Naked))
         Solver.addTrackedFunction(F);

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

 ; CHECK-NEXT:    [[CMP0:%.*]] = call i64 @plus(i64 [[X:%.*]], i64 [[Y:%.*]])
 ; CHECK-NEXT:    [[CMP1:%.*]] = call i64 @minus(i64 [[X]], i64 [[Y]])
 
 ; CHECK-LABEL: @compute.2
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP0:%.*]] = call i64 @minus(i64 [[X:%.*]], i64 [[Y:%.*]])
 ; CHECK-NEXT:    [[CMP1:%.*]] = call i64 @plus(i64 [[X]], i64 [[Y]])
 
-; CHECK-LABEL: @compute.3
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP0:%.*]] = call i64 @plus(i64 [[X:%.*]], i64 [[Y:%.*]])
-; CHECK-NEXT:    [[CMP1:%.*]] = call i64 @minus(i64 [[X]], i64 [[Y]])
-
+; CHECK-NOT: define internal i64 @compute.3(