[FuncSpec] Remove definitions of fully specialized functions.

[labrinea]

Summary

A function is basically dead when:

• it has no uses
• it has only self-referencing uses (it's recursive)

[ChuanqiXu]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

526–528

It surprised me that the unreachable function wouldn't be removed. Have you tested to run opt -O3 for the tests? I think they might be removed in later passes.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

526–528

Yes, later passes will remove these dead functions. The benefit of removing them now is that the later passes won't have to discover them all over again.

[ChuanqiXu]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

526–528

OK, I agree it is not bad to delete it now since the cost looks cheap.

[nikic]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

522

or_null is unnecessary here, user cannot be null.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

522

thanks, will update it accordingly

[labrinea]

This patch makes clang crash when compiling ClamAV from the llvm-test-suite:

0.	Program arguments: /data/oss-llvm/debug_build/bin/clang -DNDEBUG -O3 -w -Werror=date-time -DHAVE_CONFIG_H -I/data/oss-llvm/llvm-project/test-suite/CTMark/ClamAV -I/data/oss-llvm/llvm-project/test-suite/CTMark/ClamAV/zlib -DDONT_LOCK_DBDIRS -DC_LINUX -DFPU_WORDS_BIGENDIAN=0 -DWORDS_BIGENDIAN=0 -MD -MT CTMark/ClamAV/CMakeFiles/clamscan.dir/libclamav_message.c.o -MF CTMark/ClamAV/CMakeFiles/clamscan.dir/libclamav_message.c.o.d -o CTMark/ClamAV/CMakeFiles/clamscan.dir/libclamav_message.c.o -c /data/oss-llvm/llvm-project/test-suite/CTMark/ClamAV/libclamav_message.c
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x0000000005860211 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /data/oss-llvm/llvm-project/llvm/lib/Support/Unix/Signals.inc:565:22
 #1 0x00000000058602c8 PrintStackTraceSignalHandler(void*) /data/oss-llvm/llvm-project/llvm/lib/Support/Unix/Signals.inc:632:1
 #2 0x000000000585e284 llvm::sys::RunSignalHandlers() /data/oss-llvm/llvm-project/llvm/lib/Support/Signals.cpp:97:20
 #3 0x000000000585fb70 llvm::sys::CleanupOnSignal(unsigned long) /data/oss-llvm/llvm-project/llvm/lib/Support/Unix/Signals.inc:361:31
 #4 0x00000000057894d6 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) /data/oss-llvm/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:79:5
 #5 0x0000000005789982 CrashRecoverySignalHandler(int) /data/oss-llvm/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:393:1
 #6 0x00007f3c4d908390 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x11390)
 #7 0x00000000025ba226 llvm::PointerIntPair<llvm::ilist_node_base<true>*, 1u, unsigned int, llvm::PointerLikeTypeTraits<llvm::ilist_node_base<true>*>, llvm::PointerIntPairInfo<llvm::ilist_node_base<true>*, 1u, llvm::PointerLikeTypeTraits<llvm::ilist_node_base<true>*> > >::setPointer(llvm::ilist_node_base<true>*) & /data/oss-llvm/llvm-project/llvm/include/llvm/ADT/PointerIntPair.h:65:32
 #8 0x00000000025b8def llvm::ilist_node_base<true>::setPrev(llvm::ilist_node_base<true>*) /data/oss-llvm/llvm-project/llvm/include/llvm/ADT/ilist_node_base.h:40:75
 #9 0x00000000025bf15d llvm::ilist_base<true>::removeImpl(llvm::ilist_node_base<true>&) /data/oss-llvm/llvm-project/llvm/include/llvm/ADT/ilist_base.h:34:5
#10 0x000000000417ceb3 void llvm::ilist_base<true>::remove<llvm::ilist_node_impl<llvm::ilist_detail::node_options<llvm::Function, true, false, void> > >(llvm::ilist_node_impl<llvm::ilist_detail::node_options<llvm::Function, true, false, void> >&) /data/oss-llvm/llvm-project/llvm/include/llvm/ADT/ilist_base.h:80:64
#11 0x000000000417c86c llvm::simple_ilist<llvm::Function>::remove(llvm::Function&) /data/oss-llvm/llvm-project/llvm/include/llvm/ADT/simple_ilist.h:183:77
#12 0x000000000417bc37 llvm::iplist_impl<llvm::simple_ilist<llvm::Function>, llvm::SymbolTableListTraits<llvm::Function> >::remove(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Function, true, false, void>, false, false>&) /data/oss-llvm/llvm-project/llvm/include/llvm/ADT/ilist.h:256:12
#13 0x0000000004c672a1 llvm::iplist_impl<llvm::simple_ilist<llvm::Function>, llvm::SymbolTableListTraits<llvm::Function> >::erase(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Function, true, false, void>, false, false>) /data/oss-llvm/llvm-project/llvm/include/llvm/ADT/ilist.h:269:5
#14 0x0000000004c4c6db llvm::Function::eraseFromParent() /data/oss-llvm/llvm-project/llvm/lib/IR/Function.cpp:366:1
#15 0x0000000004ffcd0b (anonymous namespace)::FunctionSpecializer::removeDeadFunctions() /data/oss-llvm/llvm-project/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp:336:5
#16 0x0000000004fffe5a llvm::runFunctionSpecialization(llvm::Module&, llvm::DataLayout const&, std::function<llvm::TargetLibraryInfo& (llvm::Function&)>, std::function<llvm::TargetTransformInfo& (llvm::Function&)>, std::function<llvm::AssumptionCache& (llvm::Function&)>, llvm::function_ref<llvm::AnalysisResultsForFn (llvm::Function&)>) /data/oss-llvm/llvm-project/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp:941:16
#17 0x0000000004fbf1a8 llvm::FunctionSpecializationPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /data/oss-llvm/llvm-project/llvm/lib/Transforms/IPO/SCCP.cpp:128:33

[labrinea]

• Fixed a segfault which would happen if you tried to erase a function twice (replaced SmallVector with SmallPtrSet)
• Moved the deletion of dead instructions and functions in a destructor to make sure it's the last thing being called (though I am wondering if the Solver could still contain references to dead functions/instructions)
• Changed the dyn_cast_or_null to dyn_cast as suggested

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

class FunctionSpecializer {
   /// The IPSCCP Solver.
   SCCPSolver &Solver;
 
   /// Analyses used to help determine if a function should be specialized.
   std::function<AssumptionCache &(Function &)> GetAC;
   std::function<TargetTransformInfo &(Function &)> GetTTI;
   std::function<TargetLibraryInfo &(Function &)> GetTLI;
 
-  SmallPtrSet<Function *, 2> SpecializedFuncs;
+  SmallPtrSet<Function *, 4> SpecializedFuncs;
+  SmallPtrSet<Function *, 4> FullySpecialized;
   SmallVector<Instruction *> ReplacedWithConstant;
 
 public:
   FunctionSpecializer(SCCPSolver &Solver,
                       std::function<AssumptionCache &(Function &)> GetAC,
                       std::function<TargetTransformInfo &(Function &)> GetTTI,
                       std::function<TargetLibraryInfo &(Function &)> GetTLI)
       : Solver(Solver), GetAC(GetAC), GetTTI(GetTTI), GetTLI(GetTLI) {}
 
+  ~FunctionSpecializer() {
+    // Eliminate dead code.
+    removeDeadInstructions();
+    removeDeadFunctions();
+  }
+
   /// Attempt to specialize functions in the module to enable constant
   /// propagation across function boundaries.
   ///
   /// \returns true if at least one function is specialized.
   bool specializeFunctions(FuncList &Candidates, FuncList &WorkList) {
     bool Changed = false;
     for (auto *F : Candidates) {
       if (!isCandidateFunction(F))
void removeDeadInstructions() {
     for (auto *I : ReplacedWithConstant) {
       LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead instruction "
                         << *I << "\n");
       I->eraseFromParent();
     }
     ReplacedWithConstant.clear();
   }
 
+  void removeDeadFunctions() {
+    for (auto *F : FullySpecialized) {
+      LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead function "
+                        << F->getName() << "\n");
+      F->eraseFromParent();
+    }
+    FullySpecialized.clear();
+  }
+
   bool tryToReplaceWithConstant(Value *V) {
     if (!V->getType()->isSingleValueType() || isa<CallBase>(V) ||
         V->user_empty())
       return false;
 
     const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
     if (isOverdefined(IV))
       return false;
void specializeFunction(ArgInfo &AI, FuncList &WorkList) {
     Solver.markArgInFuncSpecialization(AI.Fn, ClonedArg, AI.Actual);
 
     // 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 (!AI.Partial)
+    if (AI.Fn->getNumUses() == 0 ||
+        all_of(AI.Fn->users(), [&AI](User *U) {
+          if (auto *CS = dyn_cast<CallBase>(U))
+            return CS->getFunction() == AI.Fn;
+          return false;
+        })) {
       Solver.markFunctionUnreachable(AI.Fn);
+      FullySpecialized.insert(AI.Fn);
+    }
   }
 
   /// Compute and return the cost of specializing function \p F.
   InstructionCost getSpecializationCost(Function *F) {
     // Compute the code metrics for the function.
     SmallPtrSet<const Value *, 32> EphValues;
     CodeMetrics::collectEphemeralValues(F, &(GetAC)(*F), EphValues);
     CodeMetrics Metrics;
while (FuncSpecializationMaxIters != I++ &&
 
     WorkList.clear();
     Changed = true;
   }
 
   LLVM_DEBUG(dbgs() << "FnSpecialization: Number of specializations = "
                     << NumFuncSpecialized <<"\n");
 
-  // Clean up the IR by removing dead instructions and ssa_copy intrinsics.
-  FS.removeDeadInstructions();
+  // Remove any ssa_copy intrinsics that may have been introduced.
   removeSSACopy(M);
   return Changed;
 }

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

bb:
   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) {
-; CHECK-LABEL: @wombat(
-; CHECK-NEXT:  bb4:
-; CHECK-NEXT:    [[TMP:%.*]] = tail call i32 [[ARG3:%.*]](i8* undef, i8* undef)
-; CHECK-NEXT:    ret void
-;
 bb4:
   %tmp = tail call i32 %arg3(i8* undef, i8* undef)
   ret void
 }

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

minus:
   %tmp1 = call i64 @compute(i64 %x, i64 (i64)* @minus)
   br label %merge
 
 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:    ret i64 [[TMP0]]
 ; CHECK-NEXT:  }
 ;
 ; CHECK-LABEL: define internal i64 @compute.2(i64 %x, i64 (i64)* %binop) {
 ; CHECK-NEXT:  entry:

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

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:   %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:   %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

if.else:
   %call1 = call i32 @foo(i32 %y, i32* @B, i32* @D)
   br label %return
 
 return:
   %retval.0 = phi i32 [ %call, %if.then ], [ %call1, %if.else ]
   ret i32 %retval.0
 }
 
+; CHECK-NOT: define internal i32 @foo(
 define internal i32 @foo(i32 %x, i32* %b, i32* %c) {
 entry:
   %0 = load i32, i32* %b, align 4
   %add = add nsw i32 %x, %0
   %1 = load i32, i32* %c, align 4
   %add1 = add nsw i32 %add, %1
   ret i32 %add1
 }

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

+; RUN: opt -function-specialization -func-specialization-size-threshold=3 -S < %s | FileCheck %s
+
+define i64 @main(i64 %x, i1 %flag) {
+entry:
+  br i1 %flag, label %plus, label %minus
+
+plus:
+  %tmp0 = call i64 @compute(i64 %x, i64 (i64)* @plus)
+  br label %merge
+
+minus:
+  %tmp1 = call i64 @compute(i64 %x, i64 (i64)* @minus)
+  br label %merge
+
+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:  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:  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:
+  %call = call i64 %binop(i64 %n)
+  %sub = add nsw i64 %n, -1
+  %call1 = call i64 @compute(i64 %sub, i64 (i64)* %binop)
+  %add2 = add nsw i64 %call1, %call
+  br label %if.end
+
+if.end:
+  %result.0 = phi i64 [ %add2, %if.then ], [ 0, %entry ]
+  ret i64 %result.0
+}
+
+define internal i64 @plus(i64 %x) {
+entry:
+  %tmp0 = add i64 %x, 1
+  ret i64 %tmp0
+}
+
+define internal i64 @minus(i64 %x) {
+entry:
+  %tmp0 = sub i64 %x, 1
+  ret i64 %tmp0
+}