[BOLT] Add sink block to flow CFG in profile inference (#95047)

Summary: Constructing an artificial sink block for the
flow CFG in stale profile inference to allow profile
inference to be run on CFGs with blocks that terminate
and have successors.

Testing Plan: Added infer_no_exits.test to verify that 
functions with exit blocks with a landing pad are 
covered by stale profile inference.

---------

Co-authored-by: Amir Ayupov <fads93@gmail.com>

2 files changed, 186 insertions, 0 deletions

diff --git a/bolt/test/X86/Inputs/infer_no_exits.s b/bolt/test/X86/Inputs/infer_no_exits.s
new file mode 100644
index 0000000..0a65b65
--- /dev/null
+++ b/bolt/test/X86/Inputs/infer_no_exits.s
@@ -0,0 +1,175 @@
+	.text
+	.file	"infer_no_exits.cpp"
+	.globl	_Z3fooi                         # -- Begin function _Z3fooi
+	.p2align	4, 0x90
+	.type	_Z3fooi,@function
+_Z3fooi:                                # @_Z3fooi
+.Lfunc_begin0:
+	.cfi_startproc
+	.cfi_personality 155, DW.ref.__gxx_personality_v0
+	.cfi_lsda 27, .Lexception0
+# %bb.0:                                # %entry
+	pushq	%rbp
+	.cfi_def_cfa_offset 16
+	.cfi_offset %rbp, -16
+	movq	%rsp, %rbp
+	.cfi_def_cfa_register %rbp
+	subq	$32, %rsp
+	movl	%edi, -4(%rbp)
+	cmpl	$0, -4(%rbp)
+	jne	.LBB0_4
+# %bb.1:                                # %if.then
+	movl	$16, %edi
+	callq	__cxa_allocate_exception@PLT
+	movq	%rax, %rdi
+	movq	%rdi, %rax
+	movq	%rax, -32(%rbp)                 # 8-byte Spill
+.Ltmp0:
+	leaq	.L.str(%rip), %rsi
+	callq	_ZNSt12out_of_rangeC1EPKc@PLT
+.Ltmp1:
+	jmp	.LBB0_2
+.LBB0_2:                                # %invoke.cont
+	movq	-32(%rbp), %rdi                 # 8-byte Reload
+	movq	_ZTISt12out_of_range@GOTPCREL(%rip), %rsi
+	movq	_ZNSt12out_of_rangeD1Ev@GOTPCREL(%rip), %rdx
+	callq	__cxa_throw@PLT
+.LBB0_3:                                # %lpad
+.Ltmp2:
+	movq	-32(%rbp), %rdi                 # 8-byte Reload
+	movq	%rax, %rcx
+	movl	%edx, %eax
+	movq	%rcx, -16(%rbp)
+	movl	%eax, -20(%rbp)
+	callq	__cxa_free_exception@PLT
+	jmp	.LBB0_5
+.LBB0_4:                                # %if.end
+	xorl	%eax, %eax
+	addq	$32, %rsp
+	popq	%rbp
+	.cfi_def_cfa %rsp, 8
+	retq
+.LBB0_5:                                # %eh.resume
+	.cfi_def_cfa %rbp, 16
+	movq	-16(%rbp), %rdi
+	callq	_Unwind_Resume@PLT
+.Lfunc_end0:
+	.size	_Z3fooi, .Lfunc_end0-_Z3fooi
+	.cfi_endproc
+	.section	.gcc_except_table,"a",@progbits
+	.p2align	2, 0x0
+GCC_except_table0:
+.Lexception0:
+	.byte	255                             # @LPStart Encoding = omit
+	.byte	255                             # @TType Encoding = omit
+	.byte	1                               # Call site Encoding = uleb128
+	.uleb128 .Lcst_end0-.Lcst_begin0
+.Lcst_begin0:
+	.uleb128 .Lfunc_begin0-.Lfunc_begin0    # >> Call Site 1 <<
+	.uleb128 .Ltmp0-.Lfunc_begin0           #   Call between .Lfunc_begin0 and .Ltmp0
+	.byte	0                               #     has no landing pad
+	.byte	0                               #   On action: cleanup
+	.uleb128 .Ltmp0-.Lfunc_begin0           # >> Call Site 2 <<
+	.uleb128 .Ltmp1-.Ltmp0                  #   Call between .Ltmp0 and .Ltmp1
+	.uleb128 .Ltmp2-.Lfunc_begin0           #     jumps to .Ltmp2
+	.byte	0                               #   On action: cleanup
+	.uleb128 .Ltmp1-.Lfunc_begin0           # >> Call Site 3 <<
+	.uleb128 .Lfunc_end0-.Ltmp1             #   Call between .Ltmp1 and .Lfunc_end0
+	.byte	0                               #     has no landing pad
+	.byte	0                               #   On action: cleanup
+.Lcst_end0:
+	.p2align	2, 0x0
+                                        # -- End function
+	.text
+	.globl	main                            # -- Begin function main
+	.p2align	4, 0x90
+	.type	main,@function
+main:                                   # @main
+.Lfunc_begin1:
+	.cfi_startproc
+	.cfi_personality 155, DW.ref.__gxx_personality_v0
+	.cfi_lsda 27, .Lexception1
+# %bb.0:                                # %entry
+	pushq	%rbp
+	.cfi_def_cfa_offset 16
+	.cfi_offset %rbp, -16
+	movq	%rsp, %rbp
+	.cfi_def_cfa_register %rbp
+	subq	$32, %rsp
+	movl	$0, -4(%rbp)
+	jmp	.Ltmp3
+.LBB1_2:                                # %lpad
+	movq	%rax, %rcx
+	movl	%edx, %eax
+	movq	%rcx, -16(%rbp)
+	movl	%eax, -20(%rbp)
+.Lcatch:
+# %bb.3:                                # %catch
+	movq	-16(%rbp), %rdi
+	callq	__cxa_begin_catch@PLT
+	callq	_ZSt9terminatev@PLT
+.Ltmp3:
+	xorl	%edi, %edi
+	callq	_Z3fooi
+	xorl	%eax, %eax
+	addq	$32, %rsp
+	popq	%rbp
+	.cfi_def_cfa %rsp, 8
+	retq
+.Lgarbage:
+
+.Lfunc_end1:
+	.size	main, .Lfunc_end1-main
+	.cfi_endproc
+	.section	.gcc_except_table,"a",@progbits
+	.p2align	2, 0x0
+GCC_except_table1:
+.Lexception1:
+	.byte	255                             # @LPStart Encoding = omit
+	.byte	155                             # @TType Encoding = indirect pcrel sdata4
+	.uleb128 .Lttbase0-.Lttbaseref0
+.Lttbaseref0:
+	.byte	1                               # Call site Encoding = uleb128
+	.uleb128 .Lcst_end1-.Lcst_begin1
+.Lcst_begin1:
+	.uleb128 .Ltmp3-.Lfunc_begin1           # >> Call Site 1 <<
+	.uleb128 .Lgarbage-.Ltmp3                  #   Call between .Ltmp3 and .Ltmp4
+	.uleb128 .LBB1_2-.Lfunc_begin1           #     jumps to .LBB1_2
+	.byte	1                               #   On action: 1
+	.uleb128 .Lcatch-.Lfunc_begin1           # >> Call Site 2 <<
+	.uleb128 .Lfunc_end1-.Ltmp3             #   Call between .Ltmp4 and .Lfunc_end1
+#	.uleb128 .LBB1_2-.Lfunc_begin1           #     jumps to .LBB1_2
+	.byte	0                               #   On action: cleanup
+	.byte	0                               #   On action: cleanup
+.Lcst_end1:
+	.byte	1                               # >> Action Record 1 <<
+                                        #   Catch TypeInfo 1
+	.byte	0                               #   No further actions
+	.p2align	2, 0x0
+                                        # >> Catch TypeInfos <<
+	.long	0                               # TypeInfo 1
+.Lttbase0:
+	.p2align	2, 0x0
+                                        # -- End function
+	.type	.L.str,@object                  # @.str
+	.section	.rodata.str1.1,"aMS",@progbits,1
+.L.str:
+	.asciz	"bad value"
+	.size	.L.str, 10
+
+	.hidden	DW.ref.__gxx_personality_v0
+	.weak	DW.ref.__gxx_personality_v0
+	.section	.data.DW.ref.__gxx_personality_v0,"awG",@progbits,DW.ref.__gxx_personality_v0,comdat
+	.p2align	3, 0x0
+	.type	DW.ref.__gxx_personality_v0,@object
+	.section	".note.GNU-stack","",@progbits
+	.addrsig
+	.addrsig_sym _Z3fooi
+	.addrsig_sym __cxa_allocate_exception
+	.addrsig_sym __gxx_personality_v0
+	.addrsig_sym __cxa_free_exception
+	.addrsig_sym __cxa_throw
+	.addrsig_sym __cxa_begin_catch
+	.addrsig_sym _ZSt9terminatev
+	.addrsig_sym _Unwind_Resume
+	.addrsig_sym _ZTISt12out_of_range
diff --git a/bolt/test/X86/infer_no_exits.test b/bolt/test/X86/infer_no_exits.test
new file mode 100644
index 0000000..b8a39d3
--- /dev/null
+++ b/bolt/test/X86/infer_no_exits.test
@@ -0,0 +1,11 @@
+## This verifies that functions where an exit block has a landing pad are covered by stale profile inference.
+# RUN: %clangxx %cxxflags %p/Inputs/infer_no_exits.s -o %t.exe
+# RUN: link_fdata %s %t.exe %t.preagg PREAGG
+# RUN: perf2bolt %t.exe -p %t.preagg --pa -o %t.fdata -w %t.yaml
+# RUN: sed -i '0,/hash:/s/0x[0-9A-Fa-f]\{16\}/0x0000000000000000/' %t.yaml
+# RUN: llvm-bolt %t.exe -data %t.yaml -o %t.null -v=1 -infer-stale-profile 2>&1 \
+# RUN:   | FileCheck %s
+
+# PREAGG: B X:0 #main# 1 0
+
+# CHECK: BOLT-INFO: inferred profile for 1 (100.00% of profiled, 100.00% of stale) functions responsible for -nan% samples (0 out of 0)