; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux -enable-ext-tsp-block-placement=1 < %s | FileCheck %s
; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux -enable-ext-tsp-block-placement=1 -ext-tsp-chain-split-threshold=0 -ext-tsp-enable-chain-split-along-jumps=0 < %s | FileCheck %s -check-prefix=CHECK2
define void @func1a() {
; Test that the algorithm positions the most likely successor first
;
; +-----+
; | b0 | -+
; +-----+ |
; | |
; | 40 |
; v |
; +-----+ |
; | b1 | | 100
; +-----+ |
; | |
; | 40 |
; v |
; +-----+ |
; | b2 | <+
; +-----+
;
; CHECK-LABEL: func1a:
; CHECK: b0
; CHECK: b2
; CHECK: b1
b0:
%call = call zeroext i1 @a()
br i1 %call, label %b1, label %b2, !prof !1
b1:
call void @d()
call void @d()
call void @d()
br label %b2
b2:
call void @e()
ret void
}
define void @func1b() {
; Test that the algorithm prefers many fallthroughs even in the presence of
; a heavy successor
;
; +-----+
; | b0 | -+
; +-----+ |
; | |
; | 80 |
; v |
; +-----+ |
; | b1 | | 100
; +-----+ |
; | |
; | 80 |
; v |
; +-----+ |
; | b2 | <+
; +-----+
;
; CHECK-LABEL: func1b:
; CHECK: b0
; CHECK: b1
; CHECK: b2
b0:
%call = call zeroext i1 @a()
br i1 %call, label %b1, label %b2, !prof !2
b1:
call void @d()
call void @d()
call void @d()
br label %b2
b2:
call void @e()
ret void
}
define void @func2() !prof !3 {
; Test that the algorithm positions the hot chain continuously
;
; +----+ [7] +-------+
; | b1 | <----- | b0 |
; +----+ +-------+
; | |
; | | [15]
; | v
; | +-------+
; | | b3 |
; | +-------+
; | |
; | | [15]
; | v
; | +-------+ [31]
; | | | -------+
; | | b4 | |
; | | | <------+
; | +-------+
; | |
; | | [15]
; | v
; | [7] +-------+
; +---------> | b2 |
; +-------+
;
; CHECK-LABEL: func2:
; CHECK: b0
; CHECK: b3
; CHECK: b4
; CHECK: b2
; CHECK: b1
b0:
call void @d()
call void @d()
call void @d()
%call = call zeroext i1 @a()
br i1 %call, label %b1, label %b3, !prof !4
b1:
call void @d()
br label %b2
b2:
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
ret void
b3:
call void @d()
br label %b4
b4:
call void @d()
%call2 = call zeroext i1 @a()
br i1 %call2, label %b2, label %b4, !prof !5
}
define void @func3() !prof !6 {
; A larger test where it is beneficial for locality to break the loop
;
; +--------+
; | b0 |
; +--------+
; |
; | [177]
; v
; +----+ [177] +---------------------------+
; | b5 | <------- | b1 |
; +----+ +---------------------------+
; | ^ ^
; | [196] | [124] | [70]
; v | |
; +----+ [70] +--------+ | |
; | b4 | <------- | b2 | | |
; +----+ +--------+ | |
; | | | |
; | | [124] | |
; | v | |
; | +--------+ | |
; | | b3 | -+ |
; | +--------+ |
; | |
; +-----------------------------------+
;
; CHECK-LABEL: func3:
; CHECK: b0
; CHECK: b1
; CHECK: b2
; CHECK: b3
; CHECK: b5
; CHECK: b4
b0:
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
call void @f()
br label %b1
b1:
%call = call zeroext i1 @a()
br i1 %call, label %b5, label %b2, !prof !7
b2:
call void @d()
call void @d()
call void @d()
call void @d()
%call2 = call zeroext i1 @a()
br i1 %call2, label %b3, label %b4, !prof !8
b3:
call void @d()
call void @f()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
call void @d()
br label %b1
b4:
call void @d()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
call void @e()
br label %b1
b5:
ret void
}
define void @func_loop() !prof !9 {
; Test that the algorithm can rotate loops in the presence of profile data.
;
; +--------+
; | entry |
; +--------+
; |
; | 1
; v
; +--------+ 16 +--------+
; | if.then| <---- | header | <+
; +--------+ +--------+ |
; | | |
; | | 16 |
; | v |
; | +--------+ |
; | | if.else| | 31
; | +--------+ |
; | | |
; | | 16 |
; | v |
; | 16 +--------+ |
; +------------> | if.end | -+
; +--------+
; |
; | 1
; v
; +--------+
; | end |
; +--------+
;
; CHECK-LABEL: func_loop:
; CHECK: if.else
; CHECK: if.end
; CHECK: header
; CHECK: if.then
entry:
br label %header
header:
call void @e()
%call = call zeroext i1 @a()
br i1 %call, label %if.then, label %if.else, !prof !10
if.then:
call void @f()
br label %if.end
if.else:
call void @g()
br label %if.end
if.end:
call void @h()
%call2 = call zeroext i1 @a()
br i1 %call2, label %header, label %end
end:
ret void
}
define void @func4() !prof !11 {
; Test verifying that, if enabled, chains can be split in order to improve the
; objective (by creating more fallthroughs)
;
; +-------+
; | entry |--------+
; +-------+ |
; | |
; | 27 |
; v |
; +-------+ |
; | b1 | -+ |
; +-------+ | |
; | | |
; | 10 | | 0
; v | |
; +-------+ | |
; | b3 | | 17 |
; +-------+ | |
; | | |
; | 10 | |
; v | |
; +-------+ | |
; | b2 | <+ ----+
; +-------+
;
; With chain splitting enabled:
; CHECK-LABEL: func4:
; CHECK: entry
; CHECK: b1
; CHECK: b3
; CHECK: b2
;
; With chain splitting disabled:
; CHECK2-LABEL: func4:
; CHECK2: entry
; CHECK2: b1
; CHECK2: b2
; CHECK2: b3
entry:
call void @b()
%call2 = call zeroext i1 @a()
br i1 %call2, label %b1, label %b2, !prof !12
b1:
call void @c()
%call = call zeroext i1 @a()
br i1 %call, label %b2, label %b3, !prof !13
b2:
call void @d()
ret void
b3:
call void @e()
br label %b2
}
declare zeroext i1 @a()
declare void @b()
declare void @c()
declare void @d()
declare void @e()
declare void @g()
declare void @f()
declare void @h()
!1 = !{!"branch_weights", i32 40, i32 100}
!2 = !{!"branch_weights", i32 80, i32 100}
!3 = !{!"function_entry_count", i64 2200}
!4 = !{!"branch_weights", i32 700, i32 1500}
!5 = !{!"branch_weights", i32 1500, i32 3100}
!6 = !{!"function_entry_count", i64 177}
!7 = !{!"branch_weights", i32 177, i32 196}
!8 = !{!"branch_weights", i32 125, i32 70}
!9 = !{!"function_entry_count", i64 1}
!10 = !{!"branch_weights", i32 16, i32 16}
!11 = !{!"function_entry_count", i64 1}
!12 = !{!"branch_weights", i32 27, i32 0}
!13 = !{!"branch_weights", i32 17, i32 10}