llvm/test/CodeGen/X86/code_placement_ext_tsp.ll

   1 ;; See also llvm/unittests/Transforms/Utils/CodeLayoutTest.cpp
   2 ; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux -enable-ext-tsp-block-placement=1 < %s | FileCheck %s
   3
   4 define 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
  28 b0:
  29   %call = call zeroext i1 @a()
  30   br i1 %call, label %b1, label %b2, !prof !1
  31
  32 b1:
  33   call void @d()
  34   call void @d()
  35   call void @d()
  36   br label %b2
  37
  38 b2:
  39   call void @e()
  40   ret void
  41 }
  42
  43
  44 define 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
  69 b0:
  70   %call = call zeroext i1 @a()
  71   br i1 %call, label %b1, label %b2, !prof !2
  72
  73 b1:
  74   call void @d()
  75   call void @d()
  76   call void @d()
  77   br label %b2
  78
  79 b2:
  80   call void @e()
  81   ret void
  82 }
  83
  84
  85 define 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
 119 b0:
 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
 126 b1:
 127   call void @d()
 128   br label %b2
 129
 130 b2:
 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
 141 b3:
 142   call void @d()
 143   br label %b4
 144
 145 b4:
 146   call void @d()
 147   %call2 = call zeroext i1 @a()
 148   br i1 %call2, label %b2, label %b4, !prof !5
 149 }
 150
 151
 152 define 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
 187 b0:
 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
 208 b1:
 209   %call = call zeroext i1 @a()
 210   br i1 %call, label %b5, label %b2, !prof !7
 211
 212 b2:
 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
 220 b3:
 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
 242 b4:
 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
 264 b5:
 265   ret void
 266 }
 267
 268 define 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
 305 entry:
 306   br label %header
 307
 308 header:
 309   call void @e()
 310   %call = call zeroext i1 @a()
 311   br i1 %call, label %if.then, label %if.else, !prof !10
 312
 313 if.then:
 314   call void @f()
 315   br label %if.end
 316
 317 if.else:
 318   call void @g()
 319   br label %if.end
 320
 321 if.end:
 322   call void @h()
 323   %call2 = call zeroext i1 @a()
 324   br i1 %call2, label %header, label %end
 325
 326 end:
 327   ret void
 328 }
 329
 330 define 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
 362 entry:
 363   call void @b()
 364   %call2 = call zeroext i1 @a()
 365   br i1 %call2, label %b1, label %b2, !prof !12
 366
 367 b1:
 368   call void @c()
 369   %call = call zeroext i1 @a()
 370   br i1 %call, label %b2, label %b3, !prof !13
 371
 372 b2:
 373   call void @d()
 374   ret void
 375
 376 b3:
 377   call void @e()
 378   br label %b2
 379 }
 380
 381 declare zeroext i1 @a()
 382 declare void @b()
 383 declare void @c()
 384 declare void @d()
 385 declare void @e()
 386 declare void @g()
 387 declare void @f()
 388 declare 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}