test/Analysis/BlockFrequencyInfo/irreducible.ll

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