[FuncSpec] Track the return values of specializations.

[labrinea]

Summary

To track the return values of specializations, we need to invalidate all the lattice values across the use-def chain which originates from the callsites, recompute and propagate.

[labrinea]

Alternatively I was thinking to remove the lattice value for the callsites whose called function has just been replaced. However I believe that might be incorrect, as the users of those callsites might be already in a lattice state of less specificity (i.e. overdefined, or wider constant range).

[labrinea]

Actually I have a WIP for recursively invalidating the lattice state of the users of such callsites and adding them back to the solver's worklist. Will run some tests and upload soon.

[labrinea]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

750

Perhaps we could only run this only when the new lattice is more specific than the old one?

[labrinea]

I found a bug in the previosu revision. When invalidating return instructions we shouldn't be looking for their lattice state in the value map, but in the tracked returns map instead. Then we should invalidate the users of the function which corresponds to that return instruction. I've changed the unit test to verify this scenario.

[labrinea]

ping

[labrinea]

The previous revision failed stage2 clang build. The problem was that some invalidated values remained unknown until the end and as a result SCCP would incorrectly zap return values of functions. One solution is to rerun resolveUndefs on the entire module to make sure that the invalidated values will get overdefined. Instead I postpone the invalidation until we've solved the specializations, and therefore we can tell whether they return a constant before we decide to invalidate its users. This (supposedly) guarantees that the entire use-def chain which was invalidated will be revisited but I am not sure.

[labrinea]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

750

Release build without assertions emits warning: unused variable here. Should fix.

[labrinea]

Changes from last revision:

• Fixed unused variable warning on release builds without assertions.
• Erase each value, which is popped from the solver's worklists, from the set of invalidated values.
• Factored out code from resolvedUndefsIn which applies to an individual instruction, so that we can call it on the remaining invalidated instructions which didn't pop from the solver's worklists.

This guarantees that all the invalidated instructions will become overdefined if they are still unknown after the solver has run.

Testing:

• Passed stage2 build of clang (with LTO, specialization of constants enabled and max-iters=10).
• The compile times for the llvm-test-suite have actually gone down too (-0.066% geomean for non-lto, -0.087% geomean for lto)

[labrinea]

ping

[chill]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

530

It'd be better to not write function recursively, but with an explicit worklist. Both maximum length of the list and the maximum stack depth would be the same (say N), but while the worklist would keep N pointers, the stack would grow to N stack frames, which is easily several times bigger memory usage (resp. cache footprint) and has the potential to overflow in extreme cases.

[labrinea]

ping?

[chill]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

486

Don't we always call invalidate with CallBase * ? Then the parameter ought to be CallBase *.

493

if (!Invalidated.insert(Inst).second)
  continue;

505

nit: In C++17 one can use

if (auto It = TrackedRetVals.find(F); It != TYrackedRetVals.end()) {
 ...

512

nit: Some (if not all) of these could be turned into {F, I} - less line noise, easier to read.

[labrinea]

Addressed comments and rebased.

[chill]

LGTM, cheers!

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

public:
   /// method should be use to handle this.  If this returns true, the solver
   /// should be rerun.
   bool resolvedUndefsIn(Function &F);
 
   void solveWhileResolvedUndefsIn(Module &M);
 
   void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList);
 
+  void solveWhileResolvedUndefs();
+
   bool isBlockExecutable(BasicBlock *BB) const;
 
   // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
   // block to the 'To' basic block is currently feasible.
   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
 
   std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const;
 
   void removeLatticeValueFor(Value *V);
 
+  /// Invalidate the Lattice Value of \p Call and its users after specializing
+  /// the call. Then recompute it.
+  void resetLatticeValueFor(CallBase *Call);
+
   const ValueLatticeElement &getLatticeValueFor(Value *V) const;
 
   /// getTrackedRetVals - Get the inferred return value map.
   const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals();
 
   /// getTrackedGlobals - Get and return the set of inferred initializers for
   /// global variables.
   const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals();

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

bool FunctionSpecializer::run() {
   // Update the rest of the call sites - these are the recursive calls, calls
   // to discarded specialisations and calls that may match a specialisation
   // after the solver runs.
   for (Function *F : OriginalFuncs) {
     auto [Begin, End] = SM[F];
     updateCallSites(F, AllSpecs.begin() + Begin, AllSpecs.begin() + End);
   }
 
+  for (Function *F : Clones) {
+    if (F->getReturnType()->isVoidTy())
+      continue;
+    if (F->getReturnType()->isStructTy()) {
+      auto *STy = cast<StructType>(F->getReturnType());
+      if (!Solver.isStructLatticeConstant(F, STy))
+        continue;
+    } else {
+      auto It = Solver.getTrackedRetVals().find(F);
+      assert(It != Solver.getTrackedRetVals().end() &&
+             "Return value ought to be tracked");
+      if (SCCPSolver::isOverdefined(It->second))
+        continue;
+    }
+    for (User *U : F->users()) {
+      if (auto *CS = dyn_cast<CallBase>(U)) {
+        //The user instruction does not call our function.
+        if (CS->getCalledFunction() != F)
+          continue;
+        Solver.resetLatticeValueFor(CS);
+      }
+    }
+  }
+
+  // Rerun the solver to notify the users of the modified callsites.
+  Solver.solveWhileResolvedUndefs();
+
   promoteConstantStackValues();
   return true;
 }
 
 void FunctionSpecializer::removeDeadFunctions() {
   for (Function *F : FullySpecialized) {
     LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead function "
                       << F->getName() << "\n");
Function *FunctionSpecializer::createSpecialization(Function *F, const SpecSig &S) {
   // The original function does not neccessarily have internal linkage, but the
   // clone must.
   Clone->setLinkage(GlobalValue::InternalLinkage);
 
   // 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.setLatticeValueForSpecializationArguments(Clone, S.Args);
-
-  Solver.addArgumentTrackedFunction(Clone);
   Solver.markBlockExecutable(&Clone->front());
+  Solver.addArgumentTrackedFunction(Clone);
+  Solver.addTrackedFunction(Clone);
 
   // Mark all the specialized functions
   Specializations.insert(Clone);
   ++NumSpecsCreated;
 
   return Clone;
 }
 

llvm/lib/Transforms/Utils/SCCPSolver.cpp

class SCCPInstVisitor : public InstVisitor<SCCPInstVisitor> {
   /// what the known return value for the function is.
   MapVector<Function *, ValueLatticeElement> TrackedRetVals;
 
   /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
   /// that return multiple values.
   MapVector<std::pair<Function *, unsigned>, ValueLatticeElement>
       TrackedMultipleRetVals;
 
+  /// The set of values whose lattice has been invalidated.
+  /// Populated by resetLatticeValueFor(), cleared after resolving undefs.
+  DenseSet<Value *> Invalidated;
+
   /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is
   /// represented here for efficient lookup.
   SmallPtrSet<Function *, 16> MRVFunctionsTracked;
 
   /// A list of functions whose return cannot be modified.
   SmallPtrSet<Function *, 16> MustPreserveReturnsInFunctions;
 
   /// TrackingIncomingArguments - This is the set of functions for whose
if (auto *C = dyn_cast<Constant>(V)) {
       else
         LV.markConstant(Elt); // Constants are constant.
     }
 
     // All others are underdefined by default.
     return LV;
   }
 
+  /// Traverse the use-def chain of \p Call, marking itself and its users as
+  /// "unknown" on the way.
+  void invalidate(CallBase *Call) {
+    SmallVector<Instruction *, 64> ToInvalidate;
+    ToInvalidate.push_back(Call);
+
+    while (!ToInvalidate.empty()) {
+      Instruction *Inst = ToInvalidate.pop_back_val();
+
+      if (!Invalidated.insert(Inst).second)
+        continue;
+
+      if (!BBExecutable.count(Inst->getParent()))
+        continue;
+
+      Value *V = nullptr;
+      // For return instructions we need to invalidate the tracked returns map.
+      // Anything else has its lattice in the value map.
+      if (auto *RetInst = dyn_cast<ReturnInst>(Inst)) {
+        Function *F = RetInst->getParent()->getParent();
+        if (auto It = TrackedRetVals.find(F); It != TrackedRetVals.end()) {
+          It->second = ValueLatticeElement();
+          V = F;
+        } else if (MRVFunctionsTracked.count(F)) {
+          auto *STy = cast<StructType>(F->getReturnType());
+          for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I)
+            TrackedMultipleRetVals[{F, I}] = ValueLatticeElement();
+          V = F;
+        }
+      } else if (auto *STy = dyn_cast<StructType>(Inst->getType())) {
+        for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
+          if (auto It = StructValueState.find({Inst, I});
+              It != StructValueState.end()) {
+            It->second = ValueLatticeElement();
+            V = Inst;
+          }
+        }
+      } else if (auto It = ValueState.find(Inst); It != ValueState.end()) {
+        It->second = ValueLatticeElement();
+        V = Inst;
+      }
+
+      if (V) {
+        LLVM_DEBUG(dbgs() << "Invalidated lattice for " << *V << "\n");
+
+        for (User *U : V->users())
+          if (auto *UI = dyn_cast<Instruction>(U))
+            ToInvalidate.push_back(UI);
+
+        auto It = AdditionalUsers.find(V);
+        if (It != AdditionalUsers.end())
+          for (User *U : It->second)
+            if (auto *UI = dyn_cast<Instruction>(U))
+              ToInvalidate.push_back(UI);
+      }
+    }
+  }
+
   /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
   /// work list if it is not already executable.
   bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
 
   // getFeasibleSuccessors - Return a vector of booleans to indicate which
   // successors are reachable from a given terminator instruction.
   void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);
 
public:
   }
 
   bool isArgumentTrackedFunction(Function *F) {
     return TrackingIncomingArguments.count(F);
   }
 
   void solve();
 
+  bool resolvedUndef(Instruction &I);
+
   bool resolvedUndefsIn(Function &F);
 
   bool isBlockExecutable(BasicBlock *BB) const {
     return BBExecutable.count(BB);
   }
 
   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
 
   std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
     std::vector<ValueLatticeElement> StructValues;
     auto *STy = dyn_cast<StructType>(V->getType());
     assert(STy && "getStructLatticeValueFor() can be called only on structs");
     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
       auto I = StructValueState.find(std::make_pair(V, i));
       assert(I != StructValueState.end() && "Value not in valuemap!");
       StructValues.push_back(I->second);
     }
     return StructValues;
   }
 
   void removeLatticeValueFor(Value *V) { ValueState.erase(V); }
 
+  /// Invalidate the Lattice Value of \p Call and its users after specializing
+  /// the call. Then recompute it.
+  void resetLatticeValueFor(CallBase *Call) {
+    // Calls to void returning functions do not need invalidation.
+    Function *F = Call->getCalledFunction();
+    (void)F;
+    assert(!F->getReturnType()->isVoidTy() &&
+           (TrackedRetVals.count(F) || MRVFunctionsTracked.count(F)) &&
+           "All non void specializations should be tracked");
+    invalidate(Call);
+    handleCallResult(*Call);
+  }
+
   const ValueLatticeElement &getLatticeValueFor(Value *V) const {
     assert(!V->getType()->isStructTy() &&
            "Should use getStructLatticeValueFor");
     DenseMap<Value *, ValueLatticeElement>::const_iterator I =
         ValueState.find(V);
     assert(I != ValueState.end() &&
            "V not found in ValueState nor Paramstate map!");
     return I->second;
void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList) {
     bool ResolvedUndefs = true;
     while (ResolvedUndefs) {
       solve();
       ResolvedUndefs = false;
       for (Function *F : WorkList)
         ResolvedUndefs |= resolvedUndefsIn(*F);
     }
   }
+
+  void solveWhileResolvedUndefs() {
+    bool ResolvedUndefs = true;
+    while (ResolvedUndefs) {
+      solve();
+      ResolvedUndefs = false;
+      for (Value *V : Invalidated)
+        if (auto *I = dyn_cast<Instruction>(V))
+          ResolvedUndefs |= resolvedUndef(*I);
+    }
+    Invalidated.clear();
+  }
 };
 
 } // namespace llvm
 
 bool SCCPInstVisitor::markBlockExecutable(BasicBlock *BB) {
   if (!BBExecutable.insert(BB).second)
     return false;
   LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');

 void SCCPInstVisitor::solve() {
   // Process the work lists until they are empty!
   while (!BBWorkList.empty() || !InstWorkList.empty() ||
          !OverdefinedInstWorkList.empty()) {
     // Process the overdefined instruction's work list first, which drives other
     // things to overdefined more quickly.
     while (!OverdefinedInstWorkList.empty()) {
       Value *I = OverdefinedInstWorkList.pop_back_val();
+      Invalidated.erase(I);
 
       LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
 
       // "I" got into the work list because it either made the transition from
       // bottom to constant, or to overdefined.
       //
       // Anything on this worklist that is overdefined need not be visited
       // since all of its users will have already been marked as overdefined
       // Update all of the users of this instruction's value.
       //
       markUsersAsChanged(I);
     }
 
     // Process the instruction work list.
     while (!InstWorkList.empty()) {
       Value *I = InstWorkList.pop_back_val();
+      Invalidated.erase(I);
 
       LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
 
       // "I" got into the work list because it made the transition from undef to
       // constant.
       //
       // Anything on this worklist that is overdefined need not be visited
       // since all of its users will have already been marked as overdefined.
while (!BBWorkList.empty()) {
 
       // Notify all instructions in this basic block that they are newly
       // executable.
       visit(BB);
     }
   }
 }
 
-/// While solving the dataflow for a function, we don't compute a result for
-/// operations with an undef operand, to allow undef to be lowered to a
-/// constant later. For example, constant folding of "zext i8 undef to i16"
-/// would result in "i16 0", and if undef is later lowered to "i8 1", then the
-/// zext result would become "i16 1" and would result into an overdefined
-/// lattice value once merged with the previous result. Not computing the
-/// result of the zext (treating undef the same as unknown) allows us to handle
-/// a later undef->constant lowering more optimally.
-///
-/// However, if the operand remains undef when the solver returns, we do need
-/// to assign some result to the instruction (otherwise we would treat it as
-/// unreachable). For simplicity, we mark any instructions that are still
-/// unknown as overdefined.
-bool SCCPInstVisitor::resolvedUndefsIn(Function &F) {
-  bool MadeChange = false;
-  for (BasicBlock &BB : F) {
-    if (!BBExecutable.count(&BB))
-      continue;
-
-    for (Instruction &I : BB) {
-      // Look for instructions which produce undef values.
-      if (I.getType()->isVoidTy())
-        continue;
+bool SCCPInstVisitor::resolvedUndef(Instruction &I) {
+    return false;
 
-      if (auto *STy = dyn_cast<StructType>(I.getType())) {
-        // Only a few things that can be structs matter for undef.
 
-        // Tracked calls must never be marked overdefined in resolvedUndefsIn.
-        if (auto *CB = dyn_cast<CallBase>(&I))
-          if (Function *F = CB->getCalledFunction())
-            if (MRVFunctionsTracked.count(F))
-              continue;
+          return false;
 
-        // extractvalue and insertvalue don't need to be marked; they are
-        // tracked as precisely as their operands.
-        if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
-          continue;
-        // Send the results of everything else to overdefined.  We could be
-        // more precise than this but it isn't worth bothering.
-        for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
-          ValueLatticeElement &LV = getStructValueState(&I, i);
-          if (LV.isUnknown()) {
-            markOverdefined(LV, &I);
-            MadeChange = true;
-          }
-        }
-        continue;
-      }
+      return false;
+        return true;
+    return false;
 
-      ValueLatticeElement &LV = getValueState(&I);
-      if (!LV.isUnknown())
-        continue;
+    return false;
 
-      // There are two reasons a call can have an undef result
-      // 1. It could be tracked.
-      // 2. It could be constant-foldable.
-      // Because of the way we solve return values, tracked calls must
-      // never be marked overdefined in resolvedUndefsIn.
-      if (auto *CB = dyn_cast<CallBase>(&I))
-        if (Function *F = CB->getCalledFunction())
-          if (TrackedRetVals.count(F))
-            continue;
+        return false;
 
-      if (isa<LoadInst>(I)) {
-        // A load here means one of two things: a load of undef from a global,
-        // a load from an unknown pointer.  Either way, having it return undef
-        // is okay.
-        continue;
-      }
+    return false;
 
-      markOverdefined(&I);
-      MadeChange = true;
-    }
+  return true;
+
+/// While solving the dataflow for a function, we don't compute a result for
+/// operations with an undef operand, to allow undef to be lowered to a
+/// constant later. For example, constant folding of "zext i8 undef to i16"
+/// would result in "i16 0", and if undef is later lowered to "i8 1", then the
+/// zext result would become "i16 1" and would result into an overdefined
+/// lattice value once merged with the previous result. Not computing the
+/// result of the zext (treating undef the same as unknown) allows us to handle
+/// a later undef->constant lowering more optimally.
+///
+/// However, if the operand remains undef when the solver returns, we do need
+/// to assign some result to the instruction (otherwise we would treat it as
+/// unreachable). For simplicity, we mark any instructions that are still
+/// unknown as overdefined.
+bool SCCPInstVisitor::resolvedUndefsIn(Function &F) {
+  bool MadeChange = false;
+  for (BasicBlock &BB : F) {
+    if (!BBExecutable.count(&BB))
+      continue;
+
+    for (Instruction &I : BB)
+      MadeChange |= resolvedUndef(I);
   }
 
   LLVM_DEBUG(if (MadeChange) dbgs()
              << "\nResolved undefs in " << F.getName() << '\n');
 
   return MadeChange;
 }
 
void SCCPSolver::solveWhileResolvedUndefsIn(Module &M) {
   Visitor->solveWhileResolvedUndefsIn(M);
 }
 
 void
 SCCPSolver::solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList) {
   Visitor->solveWhileResolvedUndefsIn(WorkList);
 }
 
+void SCCPSolver::solveWhileResolvedUndefs() {
+  Visitor->solveWhileResolvedUndefs();
+}
+
 bool SCCPSolver::isBlockExecutable(BasicBlock *BB) const {
   return Visitor->isBlockExecutable(BB);
 }
 
 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {
   return Visitor->isEdgeFeasible(From, To);
 }
 
 std::vector<ValueLatticeElement>
 SCCPSolver::getStructLatticeValueFor(Value *V) const {
   return Visitor->getStructLatticeValueFor(V);
 }
 
 void SCCPSolver::removeLatticeValueFor(Value *V) {
   return Visitor->removeLatticeValueFor(V);
 }
 
+void SCCPSolver::resetLatticeValueFor(CallBase *Call) {
+  Visitor->resetLatticeValueFor(Call);
+}
+
 const ValueLatticeElement &SCCPSolver::getLatticeValueFor(Value *V) const {
   return Visitor->getLatticeValueFor(V);
 }
 
 const MapVector<Function *, ValueLatticeElement> &
 SCCPSolver::getTrackedRetVals() {
   return Visitor->getTrackedRetVals();
 }

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

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

 ; CHECK-NEXT:    [[TMP3:%.*]] = add i64 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %1 = call i64 @zoo(i1 0)
   %2 = call i64 @zoo(i1 1)
   %3 = add i64 %1, %2
   ret i64 %3
 }
+

llvm/test/Transforms/FunctionSpecialization/non-argument-tracked.ll

 define internal i32 @f2(i32 %i) {
   %v = add i32 %i, 1
   ret i32 %v
 }
 
 ;; All calls are to specilisation instances.
 
 ; CHECK-LABEL: define i32 @g0
-; CHECK:         [[U0:%.*]] = call i32 @f0.[[#A:]]()
-; CHECK-NEXT:    [[U1:%.*]] = call i32 @f1.[[#B:]]()
-; CHECK-NEXT:    [[U2:%.*]] = call i32 @f2.[[#C:]]()
+; CHECK:         call void @f0.[[#A:]]()
+; CHECK-NEXT:    call void @f1.[[#B:]]()
+; CHECK-NEXT:    call void @f2.[[#C:]]()
+; CHECK-NEXT:    ret i32 9
 define i32 @g0(i32 %i) {
   %u0 = call i32 @f0(i32 1)
   %u1 = call i32 @f1(i32 2)
   %u2 = call i32 @f2(i32 3)
   %v0 = add i32 %u0, %u1
   %v = add i32 %v0, %u2
   ret i32 %v
 }
 
 ; CHECK-LABEL: define i32 @g1
-; CHECK:         [[U0:%.*]] = call i32 @f0.[[#D:]]()
-; CHECK-NEXT:    [[U1:%.*]] = call i32 @f1.[[#E:]]()
-; CHECK-NEXT:    [[U2:%.*]] = call i32 @f2.[[#F:]]()
+; CHECK:         call void @f0.[[#D:]]()
+; CHECK-NEXT:    call void @f1.[[#E:]]()
+; CHECK-NEXT:    call void @f2.[[#F:]]()
+; CHECK-NEXT:    ret i32 12
 define i32 @g1(i32 %i) {
   %u0 = call i32 @f0(i32 2)
   %u1 = call i32 @f1(i32 3)
   %u2 = call i32 @f2(i32 4)
   %v0 = add i32 %u0, %u1
   %v = add i32 %v0, %u2
   ret i32 %v
 }
 
 ; All of the function are specialized and all clones are with internal linkage.
 
-; CHECK-DAG: define internal i32 @f0.[[#A]]() {
-; CHECK-DAG: define internal i32 @f1.[[#B]]() {
-; CHECK-DAG: define internal i32 @f2.[[#C]]() {
-; CHECK-DAG: define internal i32 @f0.[[#D]]() {
-; CHECK-DAG: define internal i32 @f1.[[#E]]() {
-; CHECK-DAG: define internal i32 @f2.[[#F]]() {
+; CHECK-DAG: define internal void @f0.[[#A]]() {
+; CHECK-DAG: define internal void @f1.[[#B]]() {
+; CHECK-DAG: define internal void @f2.[[#C]]() {
+; CHECK-DAG: define internal void @f0.[[#D]]() {
+; CHECK-DAG: define internal void @f1.[[#E]]() {
+; CHECK-DAG: define internal void @f2.[[#F]]() {

llvm/test/Transforms/FunctionSpecialization/track-return.ll

+; RUN: opt -passes="ipsccp<func-spec>" -force-specialization -funcspec-for-literal-constant -funcspec-max-iters=3 -S < %s | FileCheck %s
+
+define i64 @main() {
+; CHECK:       define i64 @main
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C1:%.*]] = call i64 @foo.1(i1 true, i64 3, i64 1)
+; CHECK-NEXT:    [[C2:%.*]] = call i64 @foo.2(i1 false, i64 4, i64 -1)
+; CHECK-NEXT:    ret i64 8
+;
+entry:
+  %c1 = call i64 @foo(i1 true, i64 3, i64 1)
+  %c2 = call i64 @foo(i1 false, i64 4, i64 -1)
+  %add = add i64 %c1, %c2
+  ret i64 %add
+}
+
+define internal i64 @foo(i1 %flag, i64 %m, i64 %n) {
+;
+; CHECK:       define internal i64 @foo.1
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label %plus
+; CHECK:       plus:
+; CHECK-NEXT:    [[N0:%.*]] = call i64 @binop.4(i64 3, i64 1)
+; CHECK-NEXT:    [[RES0:%.*]] = call i64 @bar.6(i64 4)
+; CHECK-NEXT:    br label %merge
+; CHECK:       merge:
+; CHECK-NEXT:    ret i64 undef
+;
+; CHECK:       define internal i64 @foo.2
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label %minus
+; CHECK:       minus:
+; CHECK-NEXT:    [[N1:%.*]] = call i64 @binop.3(i64 4, i64 -1)
+; CHECK-NEXT:    [[RES1:%.*]] = call i64 @bar.5(i64 3)
+; CHECK-NEXT:    br label %merge
+; CHECK:       merge:
+; CHECK-NEXT:    ret i64 undef
+;
+entry:
+  br i1 %flag, label %plus, label %minus
+
+plus:
+  %n0 = call i64 @binop(i64 %m, i64 %n)
+  %res0 = call i64 @bar(i64 %n0)
+  br label %merge
+
+minus:
+  %n1 = call i64 @binop(i64 %m, i64 %n)
+  %res1 = call i64 @bar(i64 %n1)
+  br label %merge
+
+merge:
+  %res = phi i64 [ %res0, %plus ], [ %res1, %minus]
+  ret i64 %res
+}
+
+define internal i64 @binop(i64 %x, i64 %y) {
+;
+; CHECK:       define internal i64 @binop.3
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i64 undef
+;
+; CHECK:       define internal i64 @binop.4
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i64 undef
+;
+entry:
+  %z = add i64 %x, %y
+  ret i64 %z
+}
+
+define internal i64 @bar(i64 %n) {
+;
+; CHECK:       define internal i64 @bar.5
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label %if.else
+; CHECK:       if.else:
+; CHECK-NEXT:    br label %if.end
+; CHECK:       if.end:
+; CHECK-NEXT:    ret i64 undef
+;
+; CHECK:       define internal i64 @bar.6
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label %if.then
+; CHECK:       if.then:
+; CHECK-NEXT:    br label %if.end
+; CHECK:       if.end:
+; CHECK-NEXT:    ret i64 undef
+;
+entry:
+  %cmp = icmp sgt i64 %n, 3
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %res0 = sdiv i64 %n, 2
+  br label %if.end
+
+if.else:
+  %res1 = mul i64 %n, 2
+  br label %if.end
+
+if.end:
+  %res = phi i64 [ %res0, %if.then ], [ %res1, %if.else]
+  ret i64 %res
+}
+