| ; 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} |
