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