[HotColdSplitting] Refine definition of unlikelyExecuted

[vsk]

Summary

The splitting pass uses its 'unlikelyExecuted' predicate to statically
decide which blocks are cold.

• Do not treat noreturn calls as if they are cold unless they are actually marked cold. This is motivated by functions like exit() and longjmp(), which are not beneficial to outline.

• Do not treat inline asm as an outlining barrier. In practice asm("") is frequently used to inhibit basic block merging; enabling outlining in this case results in substantial memory savings.

• Treat invokes of cold functions as cold.

As a drive-by, remove the 'exceptionHandlingFunctions' predicate, because it's
no longer needed. The pass can identify & outline blocks dominated by EH pads,
so there's no need to special-case __cxa_begin_catch etc.

[efriedma]

This is motivated by functions like exit() and longjmp(), which are not beneficial to outline.

exit() seems like a weird example: it executes at most once per process. What's the downside of outlining it?

[vsk]

In D54244#1291193, @efriedma wrote:

This is motivated by functions like exit() and longjmp(), which are not beneficial to outline.

exit() seems like a weird example: it executes at most once per process. What's the downside of outlining it?

It’s not clear that there’s an actual benefit to outlining it. A call to exit(0) could be expected to happen: outlining it to a cold section might force a page fault when it otherwise wouldn’t.

[junbuml]

Thanks Vedant for handling this. Overall I agree with this change, but I believe it's good to break this patch down into three parts and get each of them reviewed separately :

1. Mark @llvm.trap cold.
2. Do not treat noreturn calls as cold unless they are actually marked cold.
3. Do not treat inline asm as an outlining barrier.

Or

1. Mark @llvm.trap cold.
2. Do not treat noreturn calls as cold unless they are actually marked cold, and Do not treat inline asm as an outlining barrier.

[vsk]

• Split out the change to mark llvm.trap cold, per review feedback.

[hiraditya]

Thanks for removing the exception handlers. I never wanted to hard code them in the first place.

It’s not clear that there’s an actual benefit to outlining it. A call to exit(0) could be expected to happen: outlining it to a cold section might force a page fault when it otherwise wouldn’t.

Agreed, also long jumps may incur page faults early in the program. Outlining them may have additional page faults. A program using co-routine features may see unexpected perf changes if we outline long jumps.

[junbuml]

Thanks for the update. Just one minor comment inlined.

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

106–120

It seems that the case below will be ended up with warm. Don't we need to see this case as cold?

BB:
  ..... 
  call void @sink()
  ...... 
  tail call void @longjmp(%struct.__jmp_buf_tag* %1, i32 0)
  unreachable

declare void @sink() cold
declare void @longjmp(%struct.__jmp_buf_tag*, i32) noreturn nounwind

[vsk]

• Handle cold invokes, and address review feedback from @junbuml

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

106–120

Thanks for pointing this out.

llvm/docs/LangRef.rst

 '``llvm.trap``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
-      declare void @llvm.trap() noreturn nounwind
+      declare void @llvm.trap() cold noreturn nounwind
 
 Overview:
 """""""""
 
 The '``llvm.trap``' intrinsic.
 
 Arguments:
 """"""""""

llvm/include/llvm/IR/Intrinsics.td

 // ReadNone - The specified argument pointer is not dereferenced by the
 // intrinsic.
 class ReadNone<int argNo> : IntrinsicProperty {
   int ArgNo = argNo;
 }
 
 def IntrNoReturn : IntrinsicProperty;
 
+// IntrCold - Calls to this intrinsic are cold.
+// Parallels the cold attribute on LLVM IR functions.
+def IntrCold : IntrinsicProperty;
+
 // IntrNoduplicate - Calls to this intrinsic cannot be duplicated.
 // Parallels the noduplicate attribute on LLVM IR functions.
 def IntrNoDuplicate : IntrinsicProperty;
 
 // IntrConvergent - Calls to this intrinsic are convergent and may not be made
 // control-dependent on any additional values.
 // Parallels the convergent attribute on LLVM IR functions.
 def IntrConvergent : IntrinsicProperty;

 def int_coro_subfn_addr : Intrinsic<[llvm_ptr_ty], [llvm_ptr_ty, llvm_i8_ty],
                                     [IntrReadMem, IntrArgMemOnly, ReadOnly<0>,
                                      NoCapture<0>]>;
 
 ///===-------------------------- Other Intrinsics --------------------------===//
 //
 def int_flt_rounds : Intrinsic<[llvm_i32_ty]>,
                      GCCBuiltin<"__builtin_flt_rounds">;
-def int_trap : Intrinsic<[], [], [IntrNoReturn]>,
+def int_trap : Intrinsic<[], [], [IntrNoReturn, IntrCold]>,
                GCCBuiltin<"__builtin_trap">;
 def int_debugtrap : Intrinsic<[]>,
                     GCCBuiltin<"__builtin_debugtrap">;
 
 // Support for dynamic deoptimization (or de-specialization)
 def int_experimental_deoptimize : Intrinsic<[llvm_any_ty], [llvm_vararg_ty],
                                             [Throws]>;
 

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

bool blockEndsInUnreachable(const BasicBlock &BB) {
   if (!succ_empty(&BB))
     return false;
   if (BB.empty())
     return true;
   const Instruction *I = BB.getTerminator();
   return !(isa<ReturnInst>(I) || isa<IndirectBrInst>(I));
 }
 
-static bool exceptionHandlingFunctions(const CallInst *CI) {
-  auto F = CI->getCalledFunction();
-  if (!F)
-    return false;
-  auto FName = F->getName();
-  return FName == "__cxa_begin_catch" ||
-         FName == "__cxa_free_exception" ||
-         FName == "__cxa_allocate_exception" ||
-         FName == "__cxa_begin_catch" ||
-         FName == "__cxa_end_catch";
-}
-
-static bool unlikelyExecuted(const BasicBlock &BB) {
-  if (blockEndsInUnreachable(BB))
-    return true;
+bool unlikelyExecuted(const BasicBlock &BB) {
   // Exception handling blocks are unlikely executed.
   if (BB.isEHPad())
     return true;
-  for (const Instruction &I : BB)
-    if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
-      // The block is cold if it calls functions tagged as cold or noreturn.
-      if (CI->hasFnAttr(Attribute::Cold) ||
-          CI->hasFnAttr(Attribute::NoReturn) ||
-          exceptionHandlingFunctions(CI))
-        return true;
 
-      // Assume that inline assembly is hot code.
-      if (isa<InlineAsm>(CI->getCalledValue()))
+  if (blockEndsInUnreachable(BB)) {
+    // Calls to noreturn functions are followed by an unreachable inst, but
+    // the call itself may be warm (e.g. longjmp, or exit).
+    if (auto *CI =
+            dyn_cast_or_null<CallInst>(BB.getTerminator()->getPrevNode()))
+      if (CI->hasFnAttr(Attribute::NoReturn) && !CI->hasFnAttr(Attribute::Cold))
         return false;
-    }
+    return true;
+
+  for (const Instruction &I : BB)
+    if (const CallInst *CI = dyn_cast<CallInst>(&I))
+      // The block is cold if it calls a cold function.
+      if (CI->hasFnAttr(Attribute::Cold))
+        return true;
+
   return false;
 }
 
 /// Check whether it's safe to outline \p BB.
 static bool mayExtractBlock(const BasicBlock &BB) {
   return !BB.hasAddressTaken();
 }
 

llvm/test/Feature/intrinsics.ll

 declare void @llvm.trap()
 
 define void @trap() {
   call void @llvm.trap()
   ret void
 }
 
 ; CHECK: attributes #0 = { nounwind readnone speculatable }
-; CHECK: attributes #1 = { noreturn nounwind }
+; CHECK: attributes #1 = { cold noreturn nounwind }

llvm/test/Transforms/HotColdSplit/noreturn.ll

+; RUN: opt -hotcoldsplit -S < %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.14.0"
+
+%struct.__jmp_buf_tag = type { [8 x i64], i32, %struct.__sigset_t }
+%struct.__sigset_t = type { [16 x i64] }
+
+; Don't outline noreturn calls which aren't explicitly marked cold.
+
+; CHECK-LABEL: define {{.*}}@foo(
+; CHECK-NOT: foo.cold.1
+define void @foo(i32, %struct.__jmp_buf_tag*) {
+  %3 = icmp eq i32 %0, 0
+  tail call void @_Z10sideeffectv()
+  br i1 %3, label %5, label %4
+
+; <label>:4:                                      ; preds = %2
+  tail call void @longjmp(%struct.__jmp_buf_tag* %1, i32 0)
+  unreachable
+
+; <label>:5:                                      ; preds = %2
+  ret void
+}
+
+; Do outline noreturn calls marked cold.
+
+; CHECK-LABEL: define {{.*}}@bar(
+; CHECK: call {{.*}}@bar.cold.1(
+
+; CHECK-LABEL: define {{.*}}@bar.cold.1(
+; CHECK: call {{.*}}@llvm.trap(
+define void @bar(i32) {
+  %2 = icmp eq i32 %0, 0
+  tail call void @_Z10sideeffectv()
+  br i1 %2, label %sink, label %exit
+
+sink:
+  tail call void @_Z10sideeffectv()
+  tail call void @_Z10sideeffectv()
+  tail call void @_Z10sideeffectv()
+  call void @llvm.trap()
+  unreachable
+
+exit:
+  ret void
+}
+
+declare void @llvm.trap() noreturn cold
+
+declare void @_Z10sideeffectv()
+
+declare void @longjmp(%struct.__jmp_buf_tag*, i32) noreturn nounwind

llvm/test/Transforms/HotColdSplit/outline-cold-asm.ll

+; RUN: opt -hotcoldsplit -S < %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.14.0"
+
+; CHECK-LABEL: define {{.*}}@fun(
+; CHECK: call {{.*}}@fun.cold.1(
+
+; CHECK-LABEL: define {{.*}}@fun.cold.1(
+; CHECK: asm ""
+
+define void @fun() {
+entry:
+  br i1 undef, label %if.then, label %if.else
+
+if.then:
+  ret void
+
+if.else:
+  call void asm "", ""()
+  call void @sink()
+  call void @sink()
+  call void @sink()
+  ret void
+}
+
+declare void @sink() cold

llvm/test/Transforms/SimplifyCFG/switch-on-const-select.ll

bees:
     unreachable
 }
 
 declare void @llvm.trap() nounwind noreturn
 declare void @bees.a() nounwind
 declare void @bees.b() nounwind
 
 ; CHECK: attributes [[$NUW]] = { nounwind }
-; CHECK: attributes #1 = { noreturn nounwind }
+; CHECK: attributes #1 = { cold noreturn nounwind }

llvm/utils/TableGen/CodeGenIntrinsics.h

struct CodeGenIntrinsic {
   bool canThrow;
 
   /// True if the intrinsic is marked as noduplicate.
   bool isNoDuplicate;
 
   /// True if the intrinsic is no-return.
   bool isNoReturn;
 
+  /// True if the intrinsic is cold.
+  bool isCold;
+
   /// True if the intrinsic is marked as convergent.
   bool isConvergent;
 
   /// True if the intrinsic has side effects that aren't captured by any
   /// of the other flags.
   bool hasSideEffects;
 
   // True if the intrinsic is marked as speculatable.

llvm/utils/TableGen/CodeGenTarget.cpp

CodeGenIntrinsic::CodeGenIntrinsic(Record *R) {
   TheDef = R;
   std::string DefName = R->getName();
   ModRef = ReadWriteMem;
   Properties = 0;
   isOverloaded = false;
   isCommutative = false;
   canThrow = false;
   isNoReturn = false;
+  isCold = false;
   isNoDuplicate = false;
   isConvergent = false;
   isSpeculatable = false;
   hasSideEffects = false;
 
   if (DefName.size() <= 4 ||
       std::string(DefName.begin(), DefName.begin() + 4) != "int_")
     PrintFatalError("Intrinsic '" + DefName + "' does not start with 'int_'!");
for (unsigned i = 0, e = PropList->size(); i != e; ++i) {
     else if (Property->getName() == "Throws")
       canThrow = true;
     else if (Property->getName() == "IntrNoDuplicate")
       isNoDuplicate = true;
     else if (Property->getName() == "IntrConvergent")
       isConvergent = true;
     else if (Property->getName() == "IntrNoReturn")
       isNoReturn = true;
+    else if (Property->getName() == "IntrCold")
+      isCold = true;
     else if (Property->getName() == "IntrSpeculatable")
       isSpeculatable = true;
     else if (Property->getName() == "IntrHasSideEffects")
       hasSideEffects = true;
     else if (Property->isSubClassOf("NoCapture")) {
       unsigned ArgNo = Property->getValueAsInt("ArgNo");
       ArgumentAttributes.push_back(std::make_pair(ArgNo, NoCapture));
     } else if (Property->isSubClassOf("Returned")) {

llvm/utils/TableGen/IntrinsicEmitter.cpp

if (L->canThrow != R->canThrow)
       return R->canThrow;
 
     if (L->isNoDuplicate != R->isNoDuplicate)
       return R->isNoDuplicate;
 
     if (L->isNoReturn != R->isNoReturn)
       return R->isNoReturn;
 
+    if (L->isCold != R->isCold)
+      return R->isCold;
+
     if (L->isConvergent != R->isConvergent)
       return R->isConvergent;
 
     if (L->isSpeculatable != R->isSpeculatable)
       return R->isSpeculatable;
 
     if (L->hasSideEffects != R->hasSideEffects)
       return R->hasSideEffects;
if (ae) {
         OS << "};\n";
         OS << "      AS[" << numAttrs++ << "] = AttributeList::get(C, "
            << attrIdx << ", AttrParam" << attrIdx << ");\n";
       }
     }
 
     if (!intrinsic.canThrow ||
         intrinsic.ModRef != CodeGenIntrinsic::ReadWriteMem ||
-        intrinsic.isNoReturn || intrinsic.isNoDuplicate ||
+        intrinsic.isNoReturn || intrinsic.isCold || intrinsic.isNoDuplicate ||
         intrinsic.isConvergent || intrinsic.isSpeculatable) {
       OS << "      const Attribute::AttrKind Atts[] = {";
       bool addComma = false;
       if (!intrinsic.canThrow) {
         OS << "Attribute::NoUnwind";
         addComma = true;
       }
       if (intrinsic.isNoReturn) {
         if (addComma)
           OS << ",";
         OS << "Attribute::NoReturn";
         addComma = true;
       }
+      if (intrinsic.isCold) {
+        if (addComma)
+          OS << ",";
+        OS << "Attribute::Cold";
+        addComma = true;
+      }
       if (intrinsic.isNoDuplicate) {
         if (addComma)
           OS << ",";
         OS << "Attribute::NoDuplicate";
         addComma = true;
       }
       if (intrinsic.isConvergent) {
         if (addComma)