1;; See also llvm/unittests/Transforms/Utils/CodeLayoutTest.cpp 2; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux -verify-machineinstrs -enable-ext-tsp-block-placement < %s | FileCheck %s 3 4define void @func1a() { 5; Test that the algorithm positions the most likely successor first 6; 7; +-----+ 8; | b0 | -+ 9; +-----+ | 10; | | 11; | 40 | 12; v | 13; +-----+ | 14; | b1 | | 100 15; +-----+ | 16; | | 17; | 40 | 18; v | 19; +-----+ | 20; | b2 | <+ 21; +-----+ 22; 23; CHECK-LABEL: func1a: 24; CHECK: b0 25; CHECK: b2 26; CHECK: b1 27 28b0: 29 %call = call zeroext i1 @a() 30 br i1 %call, label %b1, label %b2, !prof !1 31 32b1: 33 call void @d() 34 call void @d() 35 call void @d() 36 br label %b2 37 38b2: 39 call void @e() 40 ret void 41} 42 43 44define void @func1b() { 45; Test that the algorithm prefers many fallthroughs even in the presence of 46; a heavy successor 47; 48; +-----+ 49; | b0 | -+ 50; +-----+ | 51; | | 52; | 80 | 53; v | 54; +-----+ | 55; | b1 | | 100 56; +-----+ | 57; | | 58; | 80 | 59; v | 60; +-----+ | 61; | b2 | <+ 62; +-----+ 63; 64; CHECK-LABEL: func1b: 65; CHECK: b0 66; CHECK: b1 67; CHECK: b2 68 69b0: 70 %call = call zeroext i1 @a() 71 br i1 %call, label %b1, label %b2, !prof !2 72 73b1: 74 call void @d() 75 call void @d() 76 call void @d() 77 br label %b2 78 79b2: 80 call void @e() 81 ret void 82} 83 84 85define void @func2() !prof !3 { 86; Test that the algorithm positions the hot chain continuously 87; 88; +----+ [7] +-------+ 89; | b1 | <----- | b0 | 90; +----+ +-------+ 91; | | 92; | | [15] 93; | v 94; | +-------+ 95; | | b3 | 96; | +-------+ 97; | | 98; | | [15] 99; | v 100; | +-------+ [31] 101; | | | -------+ 102; | | b4 | | 103; | | | <------+ 104; | +-------+ 105; | | 106; | | [15] 107; | v 108; | [7] +-------+ 109; +---------> | b2 | 110; +-------+ 111; 112; CHECK-LABEL: func2: 113; CHECK: b0 114; CHECK: b3 115; CHECK: b4 116; CHECK: b2 117; CHECK: b1 118 119b0: 120 call void @d() 121 call void @d() 122 call void @d() 123 %call = call zeroext i1 @a() 124 br i1 %call, label %b1, label %b3, !prof !4 125 126b1: 127 call void @d() 128 br label %b2 129 130b2: 131 call void @e() 132 call void @e() 133 call void @e() 134 call void @e() 135 call void @e() 136 call void @e() 137 call void @e() 138 call void @e() 139 ret void 140 141b3: 142 call void @d() 143 br label %b4 144 145b4: 146 call void @d() 147 %call2 = call zeroext i1 @a() 148 br i1 %call2, label %b2, label %b4, !prof !5 149} 150 151 152define void @func3() !prof !6 { 153; A larger test where it is beneficial for locality to break the loop 154; 155; +--------+ 156; | b0 | 157; +--------+ 158; | 159; | [177] 160; v 161; +----+ [177] +---------------------------+ 162; | b5 | <------- | b1 | 163; +----+ +---------------------------+ 164; | ^ ^ 165; | [196] | [124] | [70] 166; v | | 167; +----+ [70] +--------+ | | 168; | b4 | <------- | b2 | | | 169; +----+ +--------+ | | 170; | | | | 171; | | [124] | | 172; | v | | 173; | +--------+ | | 174; | | b3 | -+ | 175; | +--------+ | 176; | | 177; +-----------------------------------+ 178; 179; CHECK-LABEL: func3: 180; CHECK: b0 181; CHECK: b1 182; CHECK: b2 183; CHECK: b3 184; CHECK: b5 185; CHECK: b4 186 187b0: 188 call void @f() 189 call void @f() 190 call void @f() 191 call void @f() 192 call void @f() 193 call void @f() 194 call void @f() 195 call void @f() 196 call void @f() 197 call void @f() 198 call void @f() 199 call void @f() 200 call void @f() 201 call void @f() 202 call void @f() 203 call void @f() 204 call void @f() 205 call void @f() 206 br label %b1 207 208b1: 209 %call = call zeroext i1 @a() 210 br i1 %call, label %b5, label %b2, !prof !7 211 212b2: 213 call void @d() 214 call void @d() 215 call void @d() 216 call void @d() 217 %call2 = call zeroext i1 @a() 218 br i1 %call2, label %b3, label %b4, !prof !8 219 220b3: 221 call void @d() 222 call void @f() 223 call void @d() 224 call void @d() 225 call void @d() 226 call void @d() 227 call void @d() 228 call void @d() 229 call void @d() 230 call void @d() 231 call void @d() 232 call void @d() 233 call void @d() 234 call void @d() 235 call void @d() 236 call void @d() 237 call void @d() 238 call void @d() 239 call void @d() 240 br label %b1 241 242b4: 243 call void @d() 244 call void @e() 245 call void @e() 246 call void @e() 247 call void @e() 248 call void @e() 249 call void @e() 250 call void @e() 251 call void @e() 252 call void @e() 253 call void @e() 254 call void @e() 255 call void @e() 256 call void @e() 257 call void @e() 258 call void @e() 259 call void @e() 260 call void @e() 261 call void @e() 262 br label %b1 263 264b5: 265 ret void 266} 267 268define void @func_loop() !prof !9 { 269; Test that the algorithm can rotate loops in the presence of profile data. 270; 271; +--------+ 272; | entry | 273; +--------+ 274; | 275; | 1 276; v 277; +--------+ 16 +--------+ 278; | if.then| <---- | header | <+ 279; +--------+ +--------+ | 280; | | | 281; | | 16 | 282; | v | 283; | +--------+ | 284; | | if.else| | 31 285; | +--------+ | 286; | | | 287; | | 16 | 288; | v | 289; | 16 +--------+ | 290; +------------> | if.end | -+ 291; +--------+ 292; | 293; | 1 294; v 295; +--------+ 296; | end | 297; +--------+ 298; 299; CHECK-LABEL: func_loop: 300; CHECK: if.else 301; CHECK: if.end 302; CHECK: header 303; CHECK: if.then 304 305entry: 306 br label %header 307 308header: 309 call void @e() 310 %call = call zeroext i1 @a() 311 br i1 %call, label %if.then, label %if.else, !prof !10 312 313if.then: 314 call void @f() 315 br label %if.end 316 317if.else: 318 call void @g() 319 br label %if.end 320 321if.end: 322 call void @h() 323 %call2 = call zeroext i1 @a() 324 br i1 %call2, label %header, label %end 325 326end: 327 ret void 328} 329 330define void @func4() !prof !11 { 331; Test verifying that chains can be split in order to improve the objective 332; by creating more fallthroughs 333; 334; +-------+ 335; | entry |--------+ 336; +-------+ | 337; | | 338; | 27 | 339; v | 340; +-------+ | 341; | b1 | -+ | 342; +-------+ | | 343; | | | 344; | 10 | | 0 345; v | | 346; +-------+ | | 347; | b3 | | 17 | 348; +-------+ | | 349; | | | 350; | 10 | | 351; v | | 352; +-------+ | | 353; | b2 | <+ ----+ 354; +-------+ 355; 356; CHECK-LABEL: func4: 357; CHECK: entry 358; CHECK: b1 359; CHECK: b3 360; CHECK: b2 361 362entry: 363 call void @b() 364 %call2 = call zeroext i1 @a() 365 br i1 %call2, label %b1, label %b2, !prof !12 366 367b1: 368 call void @c() 369 %call = call zeroext i1 @a() 370 br i1 %call, label %b2, label %b3, !prof !13 371 372b2: 373 call void @d() 374 ret void 375 376b3: 377 call void @e() 378 br label %b2 379} 380 381declare zeroext i1 @a() 382declare void @b() 383declare void @c() 384declare void @d() 385declare void @e() 386declare void @g() 387declare void @f() 388declare void @h() 389 390!1 = !{!"branch_weights", i32 40, i32 100} 391!2 = !{!"branch_weights", i32 80, i32 100} 392!3 = !{!"function_entry_count", i64 2200} 393!4 = !{!"branch_weights", i32 700, i32 1500} 394!5 = !{!"branch_weights", i32 1500, i32 3100} 395!6 = !{!"function_entry_count", i64 177} 396!7 = !{!"branch_weights", i32 177, i32 196} 397!8 = !{!"branch_weights", i32 125, i32 70} 398!9 = !{!"function_entry_count", i64 1} 399!10 = !{!"branch_weights", i32 16, i32 16} 400!11 = !{!"function_entry_count", i64 1} 401!12 = !{!"branch_weights", i32 27, i32 0} 402!13 = !{!"branch_weights", i32 17, i32 10} 403