test/Analysis/BlockFrequencyInfo/irreducible.ll

   1 ; RUN: opt < %s -analyze -block-freq | FileCheck %s
   2 ; RUN: opt < %s -passes='print<block-freq>' -disable-output 2>&1 | FileCheck %s
   3
   4 ; A loop with multiple exits isn't irreducible.  It should be handled
   5 ; correctly.
   6 ;
   7 ; CHECK-LABEL: Printing analysis {{.*}} for function 'multiexit':
   8 ; CHECK-NEXT: block-frequency-info: multiexit
   9 define void @multiexit(i1 %x) {
  10 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
  11 entry:
  12   br label %loop.1
  13
  14 ; CHECK-NEXT: loop.1: float = 2.0,
  15 loop.1:
  16   br i1 %x, label %exit.1, label %loop.2, !prof !0
  17
  18 ; CHECK-NEXT: loop.2: float = 1.75,
  19 loop.2:
  20   br i1 %x, label %exit.2, label %loop.1, !prof !1
  21
  22 ; CHECK-NEXT: exit.1: float = 0.25,
  23 exit.1:
  24   br label %return
  25
  26 ; CHECK-NEXT: exit.2: float = 0.75,
  27 exit.2:
  28   br label %return
  29
  30 ; CHECK-NEXT: return: float = 1.0, int = [[ENTRY]]
  31 return:
  32   ret void
  33 }
  34
  35 !0 = !{!"branch_weights", i32 1, i32 7}
  36 !1 = !{!"branch_weights", i32 3, i32 4}
  37
  38 ; Irreducible control flow
  39 ; ========================
  40 ;
  41 ; LoopInfo defines a loop as a non-trivial SCC dominated by a single block,
  42 ; called the header.  A given loop, L, can have sub-loops, which are loops
  43 ; within the subgraph of L that excludes the header.
  44 ;
  45 ; In addition to loops, -block-freq has limited support for irreducible SCCs,
  46 ; which are SCCs with multiple entry blocks.  Irreducible SCCs are discovered
  47 ; on they fly, and modelled as loops with multiple headers.
  48 ;
  49 ; The headers of irreducible sub-SCCs consist of its entry blocks and all nodes
  50 ; that are targets of a backedge within it (excluding backedges within true
  51 ; sub-loops).
  52 ;
  53 ; -block-freq is currently designed to act like a block is inserted that
  54 ; intercepts all the edges to the headers.  All backedges and entries point to
  55 ; this block.  Its successors are the headers, which split the frequency
  56 ; evenly.
  57 ;
  58 ; There are a number of testcases below.  Only the first two have detailed
  59 ; explanations.
  60 ;
  61 ; Testcase #1
  62 ; ===========
  63 ;
  64 ; In this case c1 and c2 should have frequencies of 15/7 and 13/7,
  65 ; respectively.  To calculate this, consider assigning 1.0 to entry, and
  66 ; distributing frequency iteratively (to infinity).  At the first iteration,
  67 ; entry gives 3/4 to c1 and 1/4 to c2.  At every step after, c1 and c2 give 3/4
  68 ; of what they have to each other.  Somehow, all of it comes out to exit.
  69 ;
  70 ;       c1 = 3/4 + 1/4*3/4 + 3/4*3^2/4^2 + 1/4*3^3/4^3 + 3/4*3^3/4^3 + ...
  71 ;       c2 = 1/4 + 3/4*3/4 + 1/4*3^2/4^2 + 3/4*3^3/4^3 + 1/4*3^3/4^3 + ...
  72 ;
  73 ; Simplify by splitting up the odd and even terms of the series and taking out
  74 ; factors so that the infite series matches:
  75 ;
  76 ;       c1 =  3/4 *(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
  77 ;          +  3/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
  78 ;       c2 =  1/4 *(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
  79 ;          +  9/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
  80 ;
  81 ;       c1 = 15/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
  82 ;       c2 = 13/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
  83 ;
  84 ; Since this geometric series sums to 16/7:
  85 ;
  86 ;       c1 = 15/7
  87 ;       c2 = 13/7
  88 ;
  89 ; If we treat c1 and c2 as members of the same loop, the exit frequency of the
  90 ; loop as a whole is 1/4, so the loop scale should be 4.  Summing c1 and c2
  91 ; gives 28/7, or 4.0, which is nice confirmation of the math above.
  92 ;
  93 ; -block-freq currently treats the two nodes as equals.
  94 define void @multientry(i1 %x) {
  95 ; CHECK-LABEL: Printing analysis {{.*}} for function 'multientry':
  96 ; CHECK-NEXT: block-frequency-info: multientry
  97 entry:
  98 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
  99   br i1 %x, label %c1, label %c2, !prof !2
 100
 101 c1:
 102 ; CHECK-NEXT: c1: float = 2.0,
 103 ; The "correct" answer is: float = 2.142857{{[0-9]*}},
 104   br i1 %x, label %c2, label %exit, !prof !2
 105
 106 c2:
 107 ; CHECK-NEXT: c2: float = 2.0,
 108 ; The "correct" answer is: float = 1.857142{{[0-9]*}},
 109   br i1 %x, label %c1, label %exit, !prof !2
 110
 111 exit:
 112 ; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 113   ret void
 114 }
 115
 116 !2 = !{!"branch_weights", i32 3, i32 1}
 117
 118 ; Testcase #2
 119 ; ===========
 120 ;
 121 ; In this case c1 and c2 should be treated as equals in a single loop.  The
 122 ; exit frequency is 1/3, so the scaling factor for the loop should be 3.0.  The
 123 ; loop is entered 2/3 of the time, and c1 and c2 split the total loop frequency
 124 ; evenly (1/2), so they should each have frequencies of 1.0 (3.0*2/3*1/2).
 125 ; Another way of computing this result is by assigning 1.0 to entry and showing
 126 ; that c1 and c2 should accumulate frequencies of:
 127 ;
 128 ;       1/3   +   2/9   +   4/27  +   8/81  + ...
 129 ;     2^0/3^1 + 2^1/3^2 + 2^2/3^3 + 2^3/3^4 + ...
 130 ;
 131 ; At the first step, c1 and c2 each get 1/3 of the entry.  At each subsequent
 132 ; step, c1 and c2 each get 1/3 of what's left in c1 and c2 combined.  This
 133 ; infinite series sums to 1.
 134 define void @crossloops(i2 %x) {
 135 ; CHECK-LABEL: Printing analysis {{.*}} for function 'crossloops':
 136 ; CHECK-NEXT: block-frequency-info: crossloops
 137 entry:
 138 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 139   switch i2 %x, label %exit [ i2 1, label %c1
 140                               i2 2, label %c2 ], !prof !3
 141
 142 c1:
 143 ; CHECK-NEXT: c1: float = 1.0,
 144   switch i2 %x, label %exit [ i2 1, label %c1
 145                               i2 2, label %c2 ], !prof !3
 146
 147 c2:
 148 ; CHECK-NEXT: c2: float = 1.0,
 149   switch i2 %x, label %exit [ i2 1, label %c1
 150                               i2 2, label %c2 ], !prof !3
 151
 152 exit:
 153 ; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 154   ret void
 155 }
 156
 157 !3 = !{!"branch_weights", i32 2, i32 2, i32 2}
 158
 159 ; A true loop with irreducible control flow inside.
 160 define void @loop_around_irreducible(i1 %x) {
 161 ; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_around_irreducible':
 162 ; CHECK-NEXT: block-frequency-info: loop_around_irreducible
 163 entry:
 164 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 165   br label %loop
 166
 167 loop:
 168 ; CHECK-NEXT: loop: float = 4.0, int = [[HEAD:[0-9]+]]
 169   br i1 %x, label %left, label %right, !prof !4
 170
 171 left:
 172 ; CHECK-NEXT: left: float = 8.0,
 173   br i1 %x, label %right, label %loop.end, !prof !5
 174
 175 right:
 176 ; CHECK-NEXT: right: float = 8.0,
 177   br i1 %x, label %left, label %loop.end, !prof !5
 178
 179 loop.end:
 180 ; CHECK-NEXT: loop.end: float = 4.0, int = [[HEAD]]
 181   br i1 %x, label %loop, label %exit, !prof !5
 182
 183 exit:
 184 ; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 185   ret void
 186 }
 187 !4 = !{!"branch_weights", i32 1, i32 1}
 188 !5 = !{!"branch_weights", i32 3, i32 1}
 189
 190 ; Two unrelated irreducible SCCs.
 191 define void @two_sccs(i1 %x) {
 192 ; CHECK-LABEL: Printing analysis {{.*}} for function 'two_sccs':
 193 ; CHECK-NEXT: block-frequency-info: two_sccs
 194 entry:
 195 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 196   br i1 %x, label %a, label %b, !prof !6
 197
 198 a:
 199 ; CHECK-NEXT: a: float = 0.75,
 200   br i1 %x, label %a.left, label %a.right, !prof !7
 201
 202 a.left:
 203 ; CHECK-NEXT: a.left: float = 1.5,
 204   br i1 %x, label %a.right, label %exit, !prof !6
 205
 206 a.right:
 207 ; CHECK-NEXT: a.right: float = 1.5,
 208   br i1 %x, label %a.left, label %exit, !prof !6
 209
 210 b:
 211 ; CHECK-NEXT: b: float = 0.25,
 212   br i1 %x, label %b.left, label %b.right, !prof !7
 213
 214 b.left:
 215 ; CHECK-NEXT: b.left: float = 0.625,
 216   br i1 %x, label %b.right, label %exit, !prof !8
 217
 218 b.right:
 219 ; CHECK-NEXT: b.right: float = 0.625,
 220   br i1 %x, label %b.left, label %exit, !prof !8
 221
 222 exit:
 223 ; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 224   ret void
 225 }
 226 !6 = !{!"branch_weights", i32 3, i32 1}
 227 !7 = !{!"branch_weights", i32 1, i32 1}
 228 !8 = !{!"branch_weights", i32 4, i32 1}
 229
 230 ; A true loop inside irreducible control flow.
 231 define void @loop_inside_irreducible(i1 %x) {
 232 ; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_inside_irreducible':
 233 ; CHECK-NEXT: block-frequency-info: loop_inside_irreducible
 234 entry:
 235 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 236   br i1 %x, label %left, label %right, !prof !9
 237
 238 left:
 239 ; CHECK-NEXT: left: float = 2.0,
 240   br i1 %x, label %right, label %exit, !prof !10
 241
 242 right:
 243 ; CHECK-NEXT: right: float = 2.0, int = [[RIGHT:[0-9]+]]
 244   br label %loop
 245
 246 loop:
 247 ; CHECK-NEXT: loop: float = 6.0,
 248   br i1 %x, label %loop, label %right.end, !prof !11
 249
 250 right.end:
 251 ; CHECK-NEXT: right.end: float = 2.0, int = [[RIGHT]]
 252   br i1 %x, label %left, label %exit, !prof !10
 253
 254 exit:
 255 ; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 256   ret void
 257 }
 258 !9 = !{!"branch_weights", i32 1, i32 1}
 259 !10 = !{!"branch_weights", i32 3, i32 1}
 260 !11 = !{!"branch_weights", i32 2, i32 1}
 261
 262 ; Irreducible control flow in a branch that's in a true loop.
 263 define void @loop_around_branch_with_irreducible(i1 %x) {
 264 ; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_around_branch_with_irreducible':
 265 ; CHECK-NEXT: block-frequency-info: loop_around_branch_with_irreducible
 266 entry:
 267 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 268   br label %loop
 269
 270 loop:
 271 ; CHECK-NEXT: loop: float = 2.0, int = [[LOOP:[0-9]+]]
 272   br i1 %x, label %normal, label %irreducible.entry, !prof !12
 273
 274 normal:
 275 ; CHECK-NEXT: normal: float = 1.5,
 276   br label %loop.end
 277
 278 irreducible.entry:
 279 ; CHECK-NEXT: irreducible.entry: float = 0.5, int = [[IRREDUCIBLE:[0-9]+]]
 280   br i1 %x, label %left, label %right, !prof !13
 281
 282 left:
 283 ; CHECK-NEXT: left: float = 1.0,
 284   br i1 %x, label %right, label %irreducible.exit, !prof !12
 285
 286 right:
 287 ; CHECK-NEXT: right: float = 1.0,
 288   br i1 %x, label %left, label %irreducible.exit, !prof !12
 289
 290 irreducible.exit:
 291 ; CHECK-NEXT: irreducible.exit: float = 0.5, int = [[IRREDUCIBLE]]
 292   br label %loop.end
 293
 294 loop.end:
 295 ; CHECK-NEXT: loop.end: float = 2.0, int = [[LOOP]]
 296   br i1 %x, label %loop, label %exit, !prof !13
 297
 298 exit:
 299 ; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 300   ret void
 301 }
 302 !12 = !{!"branch_weights", i32 3, i32 1}
 303 !13 = !{!"branch_weights", i32 1, i32 1}
 304
 305 ; Irreducible control flow between two true loops.
 306 define void @loop_around_branch_with_irreducible_around_loop(i1 %x) {
 307 ; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_around_branch_with_irreducible_around_loop':
 308 ; CHECK-NEXT: block-frequency-info: loop_around_branch_with_irreducible_around_loop
 309 entry:
 310 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 311   br label %loop
 312
 313 loop:
 314 ; CHECK-NEXT: loop: float = 3.0, int = [[LOOP:[0-9]+]]
 315   br i1 %x, label %normal, label %irreducible, !prof !14
 316
 317 normal:
 318 ; CHECK-NEXT: normal: float = 2.0,
 319   br label %loop.end
 320
 321 irreducible:
 322 ; CHECK-NEXT: irreducible: float = 1.0,
 323   br i1 %x, label %left, label %right, !prof !15
 324
 325 left:
 326 ; CHECK-NEXT: left: float = 2.0,
 327   br i1 %x, label %right, label %loop.end, !prof !16
 328
 329 right:
 330 ; CHECK-NEXT: right: float = 2.0, int = [[RIGHT:[0-9]+]]
 331   br label %right.loop
 332
 333 right.loop:
 334 ; CHECK-NEXT: right.loop: float = 10.0,
 335   br i1 %x, label %right.loop, label %right.end, !prof !17
 336
 337 right.end:
 338 ; CHECK-NEXT: right.end: float = 2.0, int = [[RIGHT]]
 339   br i1 %x, label %left, label %loop.end, !prof !16
 340
 341 loop.end:
 342 ; CHECK-NEXT: loop.end: float = 3.0, int = [[LOOP]]
 343   br i1 %x, label %loop, label %exit, !prof !14
 344
 345 exit:
 346 ; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 347   ret void
 348 }
 349 !14 = !{!"branch_weights", i32 2, i32 1}
 350 !15 = !{!"branch_weights", i32 1, i32 1}
 351 !16 = !{!"branch_weights", i32 3, i32 1}
 352 !17 = !{!"branch_weights", i32 4, i32 1}
 353
 354 ; An irreducible SCC with a non-header.
 355 define void @nonheader(i1 %x) {
 356 ; CHECK-LABEL: Printing analysis {{.*}} for function 'nonheader':
 357 ; CHECK-NEXT: block-frequency-info: nonheader
 358 entry:
 359 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 360   br i1 %x, label %left, label %right, !prof !18
 361
 362 left:
 363 ; CHECK-NEXT: left: float = 1.0,
 364   br i1 %x, label %bottom, label %exit, !prof !19
 365
 366 right:
 367 ; CHECK-NEXT: right: float = 1.0,
 368   br i1 %x, label %bottom, label %exit, !prof !20
 369
 370 bottom:
 371 ; CHECK-NEXT: bottom: float = 1.0,
 372   br i1 %x, label %left, label %right, !prof !18
 373
 374 exit:
 375 ; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 376   ret void
 377 }
 378 !18 = !{!"branch_weights", i32 1, i32 1}
 379 !19 = !{!"branch_weights", i32 1, i32 3}
 380 !20 = !{!"branch_weights", i32 3, i32 1}
 381
 382 ; An irreducible SCC with an irreducible sub-SCC.  In the current version of
 383 ; -block-freq, this means an extra header.
 384 ;
 385 ; This testcases uses non-trivial branch weights.  The CHECK statements here
 386 ; will start to fail if we change -block-freq to be more accurate.  Currently,
 387 ; loop headers are affected by the weight of their corresponding back edges.
 388 define void @nonentry_header(i1 %x, i2 %y) {
 389 ; CHECK-LABEL: Printing analysis {{.*}} for function 'nonentry_header':
 390 ; CHECK-NEXT: block-frequency-info: nonentry_header
 391 entry:
 392 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 393   br i1 %x, label %left, label %right, !prof !21
 394
 395 left:
 396 ; CHECK-NEXT: left: float = 0.14
 397   br i1 %x, label %top, label %bottom, !prof !22
 398
 399 right:
 400 ; CHECK-NEXT: right: float = 0.42
 401   br i1 %x, label %top, label %bottom, !prof !22
 402
 403 top:
 404 ; CHECK-NEXT: top: float = 8.43
 405   switch i2 %y, label %exit [ i2 0, label %left
 406                               i2 1, label %right
 407                               i2 2, label %bottom ], !prof !23
 408
 409 bottom:
 410 ; CHECK-NEXT: bottom: float = 4.5,
 411   br label %top
 412
 413 exit:
 414 ; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 415   ret void
 416 }
 417 !21 = !{!"branch_weights", i32 2, i32 1}
 418 !22 = !{!"branch_weights", i32 1, i32 1}
 419 !23 = !{!"branch_weights", i32 8, i32 1, i32 3, i32 12}