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

(On Diff #173378)

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 ↗

(On Diff #173378)

Thanks for pointing this out.

llvm/trunk/lib/Transforms/IPO/HotColdSplitting.cpp

 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
+#include "llvm/IR/CallSite.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Metadata.h"
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(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))
+
+  // The block is cold if it calls/invokes a cold function.
+  for (Instruction &I : BB)
+    if (auto CS = CallSite(&I))
+      if (CS.hasFnAttr(Attribute::Cold))
         return true;
 
-      // Assume that inline assembly is hot code.
-      if (isa<InlineAsm>(CI->getCalledValue()))
+  // The block is cold if it has an unreachable terminator, unless it's
+  // preceded by a call to a (possibly warm) noreturn call (e.g. longjmp).
+  if (blockEndsInUnreachable(BB)) {
+    if (auto *CI =
+            dyn_cast_or_null<CallInst>(BB.getTerminator()->getPrevNode()))
+      if (CI->hasFnAttr(Attribute::NoReturn))
         return false;
-    }
+    return true;
+
   return false;
 }
 
 /// Check whether it's safe to outline \p BB.
 static bool mayExtractBlock(const BasicBlock &BB) {
   return !BB.hasAddressTaken();
 }
 

llvm/trunk/test/Transforms/HotColdSplit/eh-pads.ll

 ; RUN: opt -S -hotcoldsplit < %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 {{.*}}@foo(
 ; CHECK: landingpad
 ; CHECK: sideeffect(i32 2)
-
-; CHECK-LABEL: define {{.*}}@foo.cold.1(
-; CHECK: sideeffect(i32 0)
-; CHECK: sideeffect(i32 1)
-; CHECK: sink
-
 define void @foo(i32 %cond) personality i8 0 {
 entry:
   invoke void @llvm.donothing() to label %normal unwind label %exception
 
 exception:
   ; Note: EH pads are not candidates for region entry points.
   %cleanup = landingpad i8 cleanup
   br label %continue_exception
 
 continue_exception:
   call void @sideeffect(i32 0)
   call void @sideeffect(i32 1)
   call void @sink()
   ret void
 
 normal:
   call void @sideeffect(i32 2)
   ret void
 }
 
+; CHECK-LABEL: define {{.*}}@bar(
+; CHECK-NOT: landingpad
+define void @bar(i32 %cond) personality i8 0 {
+entry:
+  br i1 undef, label %exit, label %continue
+
+exit:
+  ret void
+
+continue:
+  invoke void @sink() to label %normal unwind label %exception
+
+exception:
+  ; Note: EH pads are not candidates for region entry points.
+  %cleanup = landingpad i8 cleanup
+  ret void
+
+normal:
+  call void @sideeffect(i32 0)
+  call void @sideeffect(i32 1)
+  ret void
+}
+
+; CHECK-LABEL: define {{.*}}@foo.cold.1(
+; CHECK: sideeffect(i32 0)
+; CHECK: sideeffect(i32 1)
+; CHECK: sink
+
+; CHECK-LABEL: define {{.*}}@bar.cold.1(
+; CHECK: sideeffect(i32 0)
+; CHECK: sideeffect(i32 1)
+
 declare void @sideeffect(i32)
 
 declare void @sink() cold
 
 declare void @llvm.donothing() nounwind readnone

llvm/trunk/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(
+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
+}
+
+; Do outline noreturn calls preceded by a cold call.
+
+; CHECK-LABEL: define {{.*}}@baz(
+; CHECK: call {{.*}}@baz.cold.1(
+define void @baz(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
+  call void @sink()
+  tail call void @longjmp(%struct.__jmp_buf_tag* %1, i32 0)
+  unreachable
+
+; <label>:5:                                      ; preds = %2
+  ret void
+}
+
+; CHECK-LABEL: define {{.*}}@bar.cold.1(
+; CHECK: call {{.*}}@llvm.trap(
+
+declare void @sink() cold
+
+declare void @llvm.trap() noreturn cold
+
+declare void @_Z10sideeffectv()
+
+declare void @longjmp(%struct.__jmp_buf_tag*, i32) noreturn nounwind

llvm/trunk/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