NAKAMURA Takumi | e4513b1 | 2011-11-23 12:18:22 +0000 | [diff] [blame] | 1 | ; RUN: llc -mtriple=i686-linux -enable-block-placement < %s | FileCheck %s |
Chandler Carruth | 4162ece | 2011-10-21 08:01:56 +0000 | [diff] [blame] | 2 | |
| 3 | declare void @error(i32 %i, i32 %a, i32 %b) |
| 4 | |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 5 | define i32 @test_ifchains(i32 %i, i32* %a, i32 %b) { |
Chandler Carruth | 4162ece | 2011-10-21 08:01:56 +0000 | [diff] [blame] | 6 | ; Test a chain of ifs, where the block guarded by the if is error handling code |
| 7 | ; that is not expected to run. |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 8 | ; CHECK: test_ifchains: |
Chandler Carruth | 4162ece | 2011-10-21 08:01:56 +0000 | [diff] [blame] | 9 | ; CHECK: %entry |
| 10 | ; CHECK: %else1 |
| 11 | ; CHECK: %else2 |
| 12 | ; CHECK: %else3 |
| 13 | ; CHECK: %else4 |
| 14 | ; CHECK: %exit |
| 15 | ; CHECK: %then1 |
| 16 | ; CHECK: %then2 |
| 17 | ; CHECK: %then3 |
| 18 | ; CHECK: %then4 |
| 19 | ; CHECK: %then5 |
| 20 | |
| 21 | entry: |
| 22 | %gep1 = getelementptr i32* %a, i32 1 |
| 23 | %val1 = load i32* %gep1 |
| 24 | %cond1 = icmp ugt i32 %val1, 1 |
| 25 | br i1 %cond1, label %then1, label %else1, !prof !0 |
| 26 | |
| 27 | then1: |
| 28 | call void @error(i32 %i, i32 1, i32 %b) |
| 29 | br label %else1 |
| 30 | |
| 31 | else1: |
| 32 | %gep2 = getelementptr i32* %a, i32 2 |
| 33 | %val2 = load i32* %gep2 |
| 34 | %cond2 = icmp ugt i32 %val2, 2 |
| 35 | br i1 %cond2, label %then2, label %else2, !prof !0 |
| 36 | |
| 37 | then2: |
| 38 | call void @error(i32 %i, i32 1, i32 %b) |
| 39 | br label %else2 |
| 40 | |
| 41 | else2: |
| 42 | %gep3 = getelementptr i32* %a, i32 3 |
| 43 | %val3 = load i32* %gep3 |
| 44 | %cond3 = icmp ugt i32 %val3, 3 |
| 45 | br i1 %cond3, label %then3, label %else3, !prof !0 |
| 46 | |
| 47 | then3: |
| 48 | call void @error(i32 %i, i32 1, i32 %b) |
| 49 | br label %else3 |
| 50 | |
| 51 | else3: |
| 52 | %gep4 = getelementptr i32* %a, i32 4 |
| 53 | %val4 = load i32* %gep4 |
| 54 | %cond4 = icmp ugt i32 %val4, 4 |
| 55 | br i1 %cond4, label %then4, label %else4, !prof !0 |
| 56 | |
| 57 | then4: |
| 58 | call void @error(i32 %i, i32 1, i32 %b) |
| 59 | br label %else4 |
| 60 | |
| 61 | else4: |
| 62 | %gep5 = getelementptr i32* %a, i32 3 |
| 63 | %val5 = load i32* %gep5 |
| 64 | %cond5 = icmp ugt i32 %val5, 3 |
| 65 | br i1 %cond5, label %then5, label %exit, !prof !0 |
| 66 | |
| 67 | then5: |
| 68 | call void @error(i32 %i, i32 1, i32 %b) |
| 69 | br label %exit |
| 70 | |
| 71 | exit: |
| 72 | ret i32 %b |
| 73 | } |
| 74 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 75 | define i32 @test_loop_cold_blocks(i32 %i, i32* %a) { |
| 76 | ; Check that we sink cold loop blocks after the hot loop body. |
| 77 | ; CHECK: test_loop_cold_blocks: |
| 78 | ; CHECK: %entry |
| 79 | ; CHECK: %body1 |
| 80 | ; CHECK: %body2 |
| 81 | ; CHECK: %body3 |
| 82 | ; CHECK: %unlikely1 |
| 83 | ; CHECK: %unlikely2 |
| 84 | ; CHECK: %exit |
| 85 | |
| 86 | entry: |
| 87 | br label %body1 |
| 88 | |
| 89 | body1: |
| 90 | %iv = phi i32 [ 0, %entry ], [ %next, %body3 ] |
| 91 | %base = phi i32 [ 0, %entry ], [ %sum, %body3 ] |
| 92 | %unlikelycond1 = icmp slt i32 %base, 42 |
| 93 | br i1 %unlikelycond1, label %unlikely1, label %body2, !prof !0 |
| 94 | |
| 95 | unlikely1: |
| 96 | call void @error(i32 %i, i32 1, i32 %base) |
| 97 | br label %body2 |
| 98 | |
| 99 | body2: |
| 100 | %unlikelycond2 = icmp sgt i32 %base, 21 |
| 101 | br i1 %unlikelycond2, label %unlikely2, label %body3, !prof !0 |
| 102 | |
| 103 | unlikely2: |
| 104 | call void @error(i32 %i, i32 2, i32 %base) |
| 105 | br label %body3 |
| 106 | |
| 107 | body3: |
| 108 | %arrayidx = getelementptr inbounds i32* %a, i32 %iv |
| 109 | %0 = load i32* %arrayidx |
| 110 | %sum = add nsw i32 %0, %base |
| 111 | %next = add i32 %iv, 1 |
| 112 | %exitcond = icmp eq i32 %next, %i |
| 113 | br i1 %exitcond, label %exit, label %body1 |
| 114 | |
| 115 | exit: |
| 116 | ret i32 %sum |
| 117 | } |
| 118 | |
Chandler Carruth | 4162ece | 2011-10-21 08:01:56 +0000 | [diff] [blame] | 119 | !0 = metadata !{metadata !"branch_weights", i32 4, i32 64} |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 120 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 121 | define i32 @test_loop_early_exits(i32 %i, i32* %a) { |
| 122 | ; Check that we sink early exit blocks out of loop bodies. |
| 123 | ; CHECK: test_loop_early_exits: |
| 124 | ; CHECK: %entry |
| 125 | ; CHECK: %body1 |
| 126 | ; CHECK: %body2 |
| 127 | ; CHECK: %body3 |
| 128 | ; CHECK: %body4 |
| 129 | ; CHECK: %exit |
| 130 | ; CHECK: %bail1 |
| 131 | ; CHECK: %bail2 |
| 132 | ; CHECK: %bail3 |
| 133 | |
| 134 | entry: |
| 135 | br label %body1 |
| 136 | |
| 137 | body1: |
| 138 | %iv = phi i32 [ 0, %entry ], [ %next, %body4 ] |
| 139 | %base = phi i32 [ 0, %entry ], [ %sum, %body4 ] |
| 140 | %bailcond1 = icmp eq i32 %base, 42 |
| 141 | br i1 %bailcond1, label %bail1, label %body2 |
| 142 | |
| 143 | bail1: |
| 144 | ret i32 -1 |
| 145 | |
| 146 | body2: |
| 147 | %bailcond2 = icmp eq i32 %base, 43 |
| 148 | br i1 %bailcond2, label %bail2, label %body3 |
| 149 | |
| 150 | bail2: |
| 151 | ret i32 -2 |
| 152 | |
| 153 | body3: |
| 154 | %bailcond3 = icmp eq i32 %base, 44 |
| 155 | br i1 %bailcond3, label %bail3, label %body4 |
| 156 | |
| 157 | bail3: |
| 158 | ret i32 -3 |
| 159 | |
| 160 | body4: |
| 161 | %arrayidx = getelementptr inbounds i32* %a, i32 %iv |
| 162 | %0 = load i32* %arrayidx |
| 163 | %sum = add nsw i32 %0, %base |
| 164 | %next = add i32 %iv, 1 |
| 165 | %exitcond = icmp eq i32 %next, %i |
| 166 | br i1 %exitcond, label %exit, label %body1 |
| 167 | |
| 168 | exit: |
| 169 | ret i32 %sum |
| 170 | } |
| 171 | |
Chandler Carruth | 2e38cf9 | 2011-11-27 00:38:03 +0000 | [diff] [blame^] | 172 | define i32 @test_loop_rotate(i32 %i, i32* %a) { |
| 173 | ; Check that we rotate conditional exits from the loop to the bottom of the |
| 174 | ; loop, eliminating unconditional branches to the top. |
| 175 | ; CHECK: test_loop_rotate: |
| 176 | ; CHECK: %entry |
| 177 | ; CHECK: %body1 |
| 178 | ; CHECK: %body0 |
| 179 | ; CHECK: %exit |
| 180 | |
| 181 | entry: |
| 182 | br label %body0 |
| 183 | |
| 184 | body0: |
| 185 | %iv = phi i32 [ 0, %entry ], [ %next, %body1 ] |
| 186 | %base = phi i32 [ 0, %entry ], [ %sum, %body1 ] |
| 187 | %next = add i32 %iv, 1 |
| 188 | %exitcond = icmp eq i32 %next, %i |
| 189 | br i1 %exitcond, label %exit, label %body1 |
| 190 | |
| 191 | body1: |
| 192 | %arrayidx = getelementptr inbounds i32* %a, i32 %iv |
| 193 | %0 = load i32* %arrayidx |
| 194 | %sum = add nsw i32 %0, %base |
| 195 | %bailcond1 = icmp eq i32 %sum, 42 |
| 196 | br label %body0 |
| 197 | |
| 198 | exit: |
| 199 | ret i32 %base |
| 200 | } |
| 201 | |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 202 | define i32 @test_loop_align(i32 %i, i32* %a) { |
| 203 | ; Check that we provide basic loop body alignment with the block placement |
| 204 | ; pass. |
| 205 | ; CHECK: test_loop_align: |
| 206 | ; CHECK: %entry |
Chandler Carruth | 7555c40 | 2011-10-21 16:41:39 +0000 | [diff] [blame] | 207 | ; CHECK: .align [[ALIGN:[0-9]+]], |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 208 | ; CHECK-NEXT: %body |
| 209 | ; CHECK: %exit |
| 210 | |
| 211 | entry: |
| 212 | br label %body |
| 213 | |
| 214 | body: |
| 215 | %iv = phi i32 [ 0, %entry ], [ %next, %body ] |
| 216 | %base = phi i32 [ 0, %entry ], [ %sum, %body ] |
| 217 | %arrayidx = getelementptr inbounds i32* %a, i32 %iv |
| 218 | %0 = load i32* %arrayidx |
| 219 | %sum = add nsw i32 %0, %base |
| 220 | %next = add i32 %iv, 1 |
| 221 | %exitcond = icmp eq i32 %next, %i |
| 222 | br i1 %exitcond, label %exit, label %body |
| 223 | |
| 224 | exit: |
| 225 | ret i32 %sum |
| 226 | } |
| 227 | |
| 228 | define i32 @test_nested_loop_align(i32 %i, i32* %a, i32* %b) { |
| 229 | ; Check that we provide nested loop body alignment. |
| 230 | ; CHECK: test_nested_loop_align: |
| 231 | ; CHECK: %entry |
Chandler Carruth | 7555c40 | 2011-10-21 16:41:39 +0000 | [diff] [blame] | 232 | ; CHECK: .align [[ALIGN]], |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 233 | ; CHECK-NEXT: %loop.body.1 |
Chandler Carruth | 7555c40 | 2011-10-21 16:41:39 +0000 | [diff] [blame] | 234 | ; CHECK: .align [[ALIGN]], |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 235 | ; CHECK-NEXT: %inner.loop.body |
| 236 | ; CHECK-NOT: .align |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 237 | ; CHECK: %exit |
| 238 | |
| 239 | entry: |
| 240 | br label %loop.body.1 |
| 241 | |
| 242 | loop.body.1: |
| 243 | %iv = phi i32 [ 0, %entry ], [ %next, %loop.body.2 ] |
| 244 | %arrayidx = getelementptr inbounds i32* %a, i32 %iv |
| 245 | %bidx = load i32* %arrayidx |
| 246 | br label %inner.loop.body |
| 247 | |
| 248 | inner.loop.body: |
| 249 | %inner.iv = phi i32 [ 0, %loop.body.1 ], [ %inner.next, %inner.loop.body ] |
| 250 | %base = phi i32 [ 0, %loop.body.1 ], [ %sum, %inner.loop.body ] |
| 251 | %scaled_idx = mul i32 %bidx, %iv |
| 252 | %inner.arrayidx = getelementptr inbounds i32* %b, i32 %scaled_idx |
| 253 | %0 = load i32* %inner.arrayidx |
| 254 | %sum = add nsw i32 %0, %base |
| 255 | %inner.next = add i32 %iv, 1 |
| 256 | %inner.exitcond = icmp eq i32 %inner.next, %i |
| 257 | br i1 %inner.exitcond, label %loop.body.2, label %inner.loop.body |
| 258 | |
| 259 | loop.body.2: |
| 260 | %next = add i32 %iv, 1 |
| 261 | %exitcond = icmp eq i32 %next, %i |
| 262 | br i1 %exitcond, label %exit, label %loop.body.1 |
| 263 | |
| 264 | exit: |
| 265 | ret i32 %sum |
| 266 | } |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 267 | |
| 268 | define void @unnatural_cfg1() { |
| 269 | ; Test that we can handle a loop with an inner unnatural loop at the end of |
| 270 | ; a function. This is a gross CFG reduced out of the single source GCC. |
| 271 | ; CHECK: unnatural_cfg1 |
| 272 | ; CHECK: %entry |
| 273 | ; CHECK: %loop.body1 |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 274 | ; CHECK: %loop.body2 |
Chandler Carruth | 3273c89 | 2011-11-15 06:26:43 +0000 | [diff] [blame] | 275 | ; CHECK: %loop.body3 |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 276 | |
| 277 | entry: |
| 278 | br label %loop.header |
| 279 | |
| 280 | loop.header: |
| 281 | br label %loop.body1 |
| 282 | |
| 283 | loop.body1: |
| 284 | br i1 undef, label %loop.body3, label %loop.body2 |
| 285 | |
| 286 | loop.body2: |
| 287 | %ptr = load i32** undef, align 4 |
| 288 | br label %loop.body3 |
| 289 | |
| 290 | loop.body3: |
| 291 | %myptr = phi i32* [ %ptr2, %loop.body5 ], [ %ptr, %loop.body2 ], [ undef, %loop.body1 ] |
| 292 | %bcmyptr = bitcast i32* %myptr to i32* |
| 293 | %val = load i32* %bcmyptr, align 4 |
| 294 | %comp = icmp eq i32 %val, 48 |
| 295 | br i1 %comp, label %loop.body4, label %loop.body5 |
| 296 | |
| 297 | loop.body4: |
| 298 | br i1 undef, label %loop.header, label %loop.body5 |
| 299 | |
| 300 | loop.body5: |
| 301 | %ptr2 = load i32** undef, align 4 |
| 302 | br label %loop.body3 |
| 303 | } |
Chandler Carruth | 2770c14 | 2011-11-14 08:50:16 +0000 | [diff] [blame] | 304 | |
Chandler Carruth | 3273c89 | 2011-11-15 06:26:43 +0000 | [diff] [blame] | 305 | define void @unnatural_cfg2() { |
| 306 | ; Test that we can handle a loop with a nested natural loop *and* an unnatural |
| 307 | ; loop. This was reduced from a crash on block placement when run over |
| 308 | ; single-source GCC. |
| 309 | ; CHECK: unnatural_cfg2 |
| 310 | ; CHECK: %entry |
| 311 | ; CHECK: %loop.header |
| 312 | ; CHECK: %loop.body1 |
| 313 | ; CHECK: %loop.body2 |
| 314 | ; CHECK: %loop.body3 |
| 315 | ; CHECK: %loop.inner1.begin |
| 316 | ; The end block is folded with %loop.body3... |
| 317 | ; CHECK-NOT: %loop.inner1.end |
| 318 | ; CHECK: %loop.body4 |
| 319 | ; CHECK: %loop.inner2.begin |
| 320 | ; The loop.inner2.end block is folded |
| 321 | ; CHECK: %bail |
| 322 | |
| 323 | entry: |
| 324 | br label %loop.header |
| 325 | |
| 326 | loop.header: |
| 327 | %comp0 = icmp eq i32* undef, null |
| 328 | br i1 %comp0, label %bail, label %loop.body1 |
| 329 | |
| 330 | loop.body1: |
| 331 | %val0 = load i32** undef, align 4 |
| 332 | br i1 undef, label %loop.body2, label %loop.inner1.begin |
| 333 | |
| 334 | loop.body2: |
| 335 | br i1 undef, label %loop.body4, label %loop.body3 |
| 336 | |
| 337 | loop.body3: |
| 338 | %ptr1 = getelementptr inbounds i32* %val0, i32 0 |
| 339 | %castptr1 = bitcast i32* %ptr1 to i32** |
| 340 | %val1 = load i32** %castptr1, align 4 |
| 341 | br label %loop.inner1.begin |
| 342 | |
| 343 | loop.inner1.begin: |
| 344 | %valphi = phi i32* [ %val2, %loop.inner1.end ], [ %val1, %loop.body3 ], [ %val0, %loop.body1 ] |
| 345 | %castval = bitcast i32* %valphi to i32* |
| 346 | %comp1 = icmp eq i32 undef, 48 |
| 347 | br i1 %comp1, label %loop.inner1.end, label %loop.body4 |
| 348 | |
| 349 | loop.inner1.end: |
| 350 | %ptr2 = getelementptr inbounds i32* %valphi, i32 0 |
| 351 | %castptr2 = bitcast i32* %ptr2 to i32** |
| 352 | %val2 = load i32** %castptr2, align 4 |
| 353 | br label %loop.inner1.begin |
| 354 | |
| 355 | loop.body4.dead: |
| 356 | br label %loop.body4 |
| 357 | |
| 358 | loop.body4: |
| 359 | %comp2 = icmp ult i32 undef, 3 |
| 360 | br i1 %comp2, label %loop.inner2.begin, label %loop.end |
| 361 | |
| 362 | loop.inner2.begin: |
| 363 | br i1 false, label %loop.end, label %loop.inner2.end |
| 364 | |
| 365 | loop.inner2.end: |
| 366 | %comp3 = icmp eq i32 undef, 1769472 |
| 367 | br i1 %comp3, label %loop.end, label %loop.inner2.begin |
| 368 | |
| 369 | loop.end: |
| 370 | br label %loop.header |
| 371 | |
| 372 | bail: |
| 373 | unreachable |
| 374 | } |
| 375 | |
Chandler Carruth | 2770c14 | 2011-11-14 08:50:16 +0000 | [diff] [blame] | 376 | define i32 @problematic_switch() { |
| 377 | ; This function's CFG caused overlow in the machine branch probability |
| 378 | ; calculation, triggering asserts. Make sure we don't crash on it. |
| 379 | ; CHECK: problematic_switch |
| 380 | |
| 381 | entry: |
| 382 | switch i32 undef, label %exit [ |
| 383 | i32 879, label %bogus |
| 384 | i32 877, label %step |
| 385 | i32 876, label %step |
| 386 | i32 875, label %step |
| 387 | i32 874, label %step |
| 388 | i32 873, label %step |
| 389 | i32 872, label %step |
| 390 | i32 868, label %step |
| 391 | i32 867, label %step |
| 392 | i32 866, label %step |
| 393 | i32 861, label %step |
| 394 | i32 860, label %step |
| 395 | i32 856, label %step |
| 396 | i32 855, label %step |
| 397 | i32 854, label %step |
| 398 | i32 831, label %step |
| 399 | i32 830, label %step |
| 400 | i32 829, label %step |
| 401 | i32 828, label %step |
| 402 | i32 815, label %step |
| 403 | i32 814, label %step |
| 404 | i32 811, label %step |
| 405 | i32 806, label %step |
| 406 | i32 805, label %step |
| 407 | i32 804, label %step |
| 408 | i32 803, label %step |
| 409 | i32 802, label %step |
| 410 | i32 801, label %step |
| 411 | i32 800, label %step |
| 412 | i32 799, label %step |
| 413 | i32 798, label %step |
| 414 | i32 797, label %step |
| 415 | i32 796, label %step |
| 416 | i32 795, label %step |
| 417 | ] |
| 418 | bogus: |
| 419 | unreachable |
| 420 | step: |
| 421 | br label %exit |
| 422 | exit: |
| 423 | %merge = phi i32 [ 3, %step ], [ 6, %entry ] |
| 424 | ret i32 %merge |
| 425 | } |
Chandler Carruth | 03300ec | 2011-11-19 10:26:02 +0000 | [diff] [blame] | 426 | |
| 427 | define void @fpcmp_unanalyzable_branch(i1 %cond) { |
Chandler Carruth | 2901243 | 2011-11-20 09:30:40 +0000 | [diff] [blame] | 428 | ; This function's CFG contains an unanalyzable branch that is likely to be |
| 429 | ; split due to having a different high-probability predecessor. |
| 430 | ; CHECK: fpcmp_unanalyzable_branch |
| 431 | ; CHECK: %entry |
| 432 | ; CHECK: %exit |
| 433 | ; CHECK-NOT: %if.then |
| 434 | ; CHECK-NOT: %if.end |
| 435 | ; CHECK-NOT: jne |
| 436 | ; CHECK-NOT: jnp |
| 437 | ; CHECK: jne |
| 438 | ; CHECK-NEXT: jnp |
| 439 | ; CHECK-NEXT: %if.then |
| 440 | |
Chandler Carruth | 03300ec | 2011-11-19 10:26:02 +0000 | [diff] [blame] | 441 | entry: |
Chandler Carruth | 2901243 | 2011-11-20 09:30:40 +0000 | [diff] [blame] | 442 | ; Note that this branch must be strongly biased toward |
| 443 | ; 'entry.if.then_crit_edge' to ensure that we would try to form a chain for |
| 444 | ; 'entry' -> 'entry.if.then_crit_edge' -> 'if.then'. It is the last edge in that |
| 445 | ; chain which would violate the unanalyzable branch in 'exit', but we won't even |
| 446 | ; try this trick unless 'if.then' is believed to almost always be reached from |
| 447 | ; 'entry.if.then_crit_edge'. |
| 448 | br i1 %cond, label %entry.if.then_crit_edge, label %lor.lhs.false, !prof !1 |
Chandler Carruth | 03300ec | 2011-11-19 10:26:02 +0000 | [diff] [blame] | 449 | |
| 450 | entry.if.then_crit_edge: |
| 451 | %.pre14 = load i8* undef, align 1, !tbaa !0 |
| 452 | br label %if.then |
| 453 | |
| 454 | lor.lhs.false: |
| 455 | br i1 undef, label %if.end, label %exit |
| 456 | |
| 457 | exit: |
| 458 | %cmp.i = fcmp une double 0.000000e+00, undef |
| 459 | br i1 %cmp.i, label %if.then, label %if.end |
| 460 | |
| 461 | if.then: |
| 462 | %0 = phi i8 [ %.pre14, %entry.if.then_crit_edge ], [ undef, %exit ] |
| 463 | %1 = and i8 %0, 1 |
| 464 | store i8 %1, i8* undef, align 4, !tbaa !0 |
| 465 | br label %if.end |
| 466 | |
| 467 | if.end: |
| 468 | ret void |
| 469 | } |
Chandler Carruth | 2901243 | 2011-11-20 09:30:40 +0000 | [diff] [blame] | 470 | |
| 471 | !1 = metadata !{metadata !"branch_weights", i32 1000, i32 1} |
Chandler Carruth | b0dadb9 | 2011-11-20 11:22:06 +0000 | [diff] [blame] | 472 | |
| 473 | declare i32 @f() |
| 474 | declare i32 @g() |
| 475 | declare i32 @h(i32 %x) |
| 476 | |
| 477 | define i32 @test_global_cfg_break_profitability() { |
| 478 | ; Check that our metrics for the profitability of a CFG break are global rather |
| 479 | ; than local. A successor may be very hot, but if the current block isn't, it |
| 480 | ; doesn't matter. Within this test the 'then' block is slightly warmer than the |
| 481 | ; 'else' block, but not nearly enough to merit merging it with the exit block |
| 482 | ; even though the probability of 'then' branching to the 'exit' block is very |
| 483 | ; high. |
| 484 | ; CHECK: test_global_cfg_break_profitability |
NAKAMURA Takumi | 742e5cf | 2011-11-20 12:49:45 +0000 | [diff] [blame] | 485 | ; CHECK: calll {{_?}}f |
| 486 | ; CHECK: calll {{_?}}g |
| 487 | ; CHECK: calll {{_?}}h |
Chandler Carruth | b0dadb9 | 2011-11-20 11:22:06 +0000 | [diff] [blame] | 488 | ; CHECK: ret |
| 489 | |
| 490 | entry: |
| 491 | br i1 undef, label %then, label %else, !prof !2 |
| 492 | |
| 493 | then: |
| 494 | %then.result = call i32 @f() |
| 495 | br label %exit |
| 496 | |
| 497 | else: |
| 498 | %else.result = call i32 @g() |
| 499 | br label %exit |
| 500 | |
| 501 | exit: |
| 502 | %result = phi i32 [ %then.result, %then ], [ %else.result, %else ] |
| 503 | %result2 = call i32 @h(i32 %result) |
| 504 | ret i32 %result |
| 505 | } |
| 506 | |
| 507 | !2 = metadata !{metadata !"branch_weights", i32 3, i32 1} |
Chandler Carruth | 3b7b209 | 2011-11-22 13:13:16 +0000 | [diff] [blame] | 508 | |
| 509 | declare i32 @__gxx_personality_v0(...) |
| 510 | |
| 511 | define void @test_eh_lpad_successor() { |
| 512 | ; Some times the landing pad ends up as the first successor of an invoke block. |
| 513 | ; When this happens, a strange result used to fall out of updateTerminators: we |
| 514 | ; didn't correctly locate the fallthrough successor, assuming blindly that the |
| 515 | ; first one was the fallthrough successor. As a result, we would add an |
| 516 | ; erroneous jump to the landing pad thinking *that* was the default successor. |
| 517 | ; CHECK: test_eh_lpad_successor |
| 518 | ; CHECK: %entry |
| 519 | ; CHECK-NOT: jmp |
| 520 | ; CHECK: %loop |
| 521 | |
| 522 | entry: |
| 523 | invoke i32 @f() to label %preheader unwind label %lpad |
| 524 | |
| 525 | preheader: |
| 526 | br label %loop |
| 527 | |
| 528 | lpad: |
| 529 | %lpad.val = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) |
| 530 | cleanup |
| 531 | resume { i8*, i32 } %lpad.val |
| 532 | |
| 533 | loop: |
| 534 | br label %loop |
| 535 | } |
Chandler Carruth | 47fb954 | 2011-11-23 03:03:21 +0000 | [diff] [blame] | 536 | |
Chandler Carruth | 521fc5b | 2011-11-23 08:23:54 +0000 | [diff] [blame] | 537 | declare void @fake_throw() noreturn |
| 538 | |
| 539 | define void @test_eh_throw() { |
| 540 | ; For blocks containing a 'throw' (or similar functionality), we have |
| 541 | ; a no-return invoke. In this case, only EH successors will exist, and |
| 542 | ; fallthrough simply won't occur. Make sure we don't crash trying to update |
| 543 | ; terminators for such constructs. |
| 544 | ; |
| 545 | ; CHECK: test_eh_throw |
| 546 | ; CHECK: %entry |
| 547 | ; CHECK: %cleanup |
| 548 | |
| 549 | entry: |
| 550 | invoke void @fake_throw() to label %continue unwind label %cleanup |
| 551 | |
| 552 | continue: |
| 553 | unreachable |
| 554 | |
| 555 | cleanup: |
| 556 | %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) |
| 557 | cleanup |
| 558 | unreachable |
| 559 | } |
| 560 | |
Chandler Carruth | 47fb954 | 2011-11-23 03:03:21 +0000 | [diff] [blame] | 561 | define void @test_unnatural_cfg_backwards_inner_loop() { |
| 562 | ; Test that when we encounter an unnatural CFG structure after having formed |
| 563 | ; a chain for an inner loop which happened to be laid out backwards we don't |
| 564 | ; attempt to merge onto the wrong end of the inner loop just because we find it |
| 565 | ; first. This was reduced from a crasher in GCC's single source. |
| 566 | ; |
| 567 | ; CHECK: test_unnatural_cfg_backwards_inner_loop |
| 568 | ; CHECK: %entry |
| 569 | ; CHECK: %body |
| 570 | ; CHECK: %loop1 |
| 571 | ; CHECK: %loop2b |
| 572 | ; CHECK: %loop2a |
| 573 | |
| 574 | entry: |
| 575 | br i1 undef, label %loop2a, label %body |
| 576 | |
| 577 | body: |
| 578 | br label %loop2a |
| 579 | |
| 580 | loop1: |
| 581 | %next.load = load i32** undef |
| 582 | br i1 %comp.a, label %loop2a, label %loop2b |
| 583 | |
| 584 | loop2a: |
| 585 | %var = phi i32* [ null, %entry ], [ null, %body ], [ %next.phi, %loop1 ] |
| 586 | %next.var = phi i32* [ null, %entry ], [ undef, %body ], [ %next.load, %loop1 ] |
| 587 | %comp.a = icmp eq i32* %var, null |
| 588 | br label %loop3 |
| 589 | |
| 590 | loop2b: |
| 591 | %gep = getelementptr inbounds i32* %var.phi, i32 0 |
| 592 | %next.ptr = bitcast i32* %gep to i32** |
| 593 | store i32* %next.phi, i32** %next.ptr |
| 594 | br label %loop3 |
| 595 | |
| 596 | loop3: |
| 597 | %var.phi = phi i32* [ %next.phi, %loop2b ], [ %var, %loop2a ] |
| 598 | %next.phi = phi i32* [ %next.load, %loop2b ], [ %next.var, %loop2a ] |
| 599 | br label %loop1 |
| 600 | } |
Chandler Carruth | 598894f | 2011-11-23 10:35:36 +0000 | [diff] [blame] | 601 | |
| 602 | define void @unanalyzable_branch_to_loop_header() { |
| 603 | ; Ensure that we can handle unanalyzable branches into loop headers. We |
| 604 | ; pre-form chains for unanalyzable branches, and will find the tail end of that |
| 605 | ; at the start of the loop. This function uses floating point comparison |
| 606 | ; fallthrough because that happens to always produce unanalyzable branches on |
| 607 | ; x86. |
| 608 | ; |
| 609 | ; CHECK: unanalyzable_branch_to_loop_header |
| 610 | ; CHECK: %entry |
| 611 | ; CHECK: %loop |
| 612 | ; CHECK: %exit |
| 613 | |
| 614 | entry: |
| 615 | %cmp = fcmp une double 0.000000e+00, undef |
| 616 | br i1 %cmp, label %loop, label %exit |
| 617 | |
| 618 | loop: |
| 619 | %cond = icmp eq i8 undef, 42 |
| 620 | br i1 %cond, label %exit, label %loop |
| 621 | |
| 622 | exit: |
| 623 | ret void |
| 624 | } |
| 625 | |
Chandler Carruth | a2deea1 | 2011-11-24 08:46:04 +0000 | [diff] [blame] | 626 | define void @unanalyzable_branch_to_best_succ(i1 %cond) { |
| 627 | ; Ensure that we can handle unanalyzable branches where the destination block |
| 628 | ; gets selected as the optimal sucessor to merge. |
| 629 | ; |
| 630 | ; CHECK: unanalyzable_branch_to_best_succ |
| 631 | ; CHECK: %entry |
| 632 | ; CHECK: %foo |
| 633 | ; CHECK: %bar |
| 634 | ; CHECK: %exit |
| 635 | |
| 636 | entry: |
| 637 | ; Bias this branch toward bar to ensure we form that chain. |
| 638 | br i1 %cond, label %bar, label %foo, !prof !1 |
| 639 | |
| 640 | foo: |
| 641 | %cmp = fcmp une double 0.000000e+00, undef |
| 642 | br i1 %cmp, label %bar, label %exit |
| 643 | |
| 644 | bar: |
| 645 | call i32 @f() |
| 646 | br label %exit |
| 647 | |
| 648 | exit: |
| 649 | ret void |
| 650 | } |
| 651 | |
| 652 | define void @unanalyzable_branch_to_free_block(float %x) { |
| 653 | ; Ensure that we can handle unanalyzable branches where the destination block |
| 654 | ; gets selected as the best free block in the CFG. |
| 655 | ; |
| 656 | ; CHECK: unanalyzable_branch_to_free_block |
| 657 | ; CHECK: %entry |
| 658 | ; CHECK: %a |
| 659 | ; CHECK: %b |
| 660 | ; CHECK: %c |
| 661 | ; CHECK: %exit |
| 662 | |
| 663 | entry: |
| 664 | br i1 undef, label %a, label %b |
| 665 | |
| 666 | a: |
| 667 | call i32 @f() |
| 668 | br label %c |
| 669 | |
| 670 | b: |
| 671 | %cmp = fcmp une float %x, undef |
| 672 | br i1 %cmp, label %c, label %exit |
| 673 | |
| 674 | c: |
| 675 | call i32 @g() |
| 676 | br label %exit |
| 677 | |
| 678 | exit: |
| 679 | ret void |
| 680 | } |
| 681 | |
Chandler Carruth | 4aae4f9 | 2011-11-24 11:23:15 +0000 | [diff] [blame] | 682 | define void @many_unanalyzable_branches() { |
| 683 | ; Ensure that we don't crash as we're building up many unanalyzable branches, |
| 684 | ; blocks, and loops. |
| 685 | ; |
| 686 | ; CHECK: many_unanalyzable_branches |
| 687 | ; CHECK: %entry |
| 688 | ; CHECK: %exit |
| 689 | |
| 690 | entry: |
| 691 | br label %0 |
| 692 | |
| 693 | %val0 = volatile load float* undef |
| 694 | %cmp0 = fcmp une float %val0, undef |
| 695 | br i1 %cmp0, label %1, label %0 |
| 696 | %val1 = volatile load float* undef |
| 697 | %cmp1 = fcmp une float %val1, undef |
| 698 | br i1 %cmp1, label %2, label %1 |
| 699 | %val2 = volatile load float* undef |
| 700 | %cmp2 = fcmp une float %val2, undef |
| 701 | br i1 %cmp2, label %3, label %2 |
| 702 | %val3 = volatile load float* undef |
| 703 | %cmp3 = fcmp une float %val3, undef |
| 704 | br i1 %cmp3, label %4, label %3 |
| 705 | %val4 = volatile load float* undef |
| 706 | %cmp4 = fcmp une float %val4, undef |
| 707 | br i1 %cmp4, label %5, label %4 |
| 708 | %val5 = volatile load float* undef |
| 709 | %cmp5 = fcmp une float %val5, undef |
| 710 | br i1 %cmp5, label %6, label %5 |
| 711 | %val6 = volatile load float* undef |
| 712 | %cmp6 = fcmp une float %val6, undef |
| 713 | br i1 %cmp6, label %7, label %6 |
| 714 | %val7 = volatile load float* undef |
| 715 | %cmp7 = fcmp une float %val7, undef |
| 716 | br i1 %cmp7, label %8, label %7 |
| 717 | %val8 = volatile load float* undef |
| 718 | %cmp8 = fcmp une float %val8, undef |
| 719 | br i1 %cmp8, label %9, label %8 |
| 720 | %val9 = volatile load float* undef |
| 721 | %cmp9 = fcmp une float %val9, undef |
| 722 | br i1 %cmp9, label %10, label %9 |
| 723 | %val10 = volatile load float* undef |
| 724 | %cmp10 = fcmp une float %val10, undef |
| 725 | br i1 %cmp10, label %11, label %10 |
| 726 | %val11 = volatile load float* undef |
| 727 | %cmp11 = fcmp une float %val11, undef |
| 728 | br i1 %cmp11, label %12, label %11 |
| 729 | %val12 = volatile load float* undef |
| 730 | %cmp12 = fcmp une float %val12, undef |
| 731 | br i1 %cmp12, label %13, label %12 |
| 732 | %val13 = volatile load float* undef |
| 733 | %cmp13 = fcmp une float %val13, undef |
| 734 | br i1 %cmp13, label %14, label %13 |
| 735 | %val14 = volatile load float* undef |
| 736 | %cmp14 = fcmp une float %val14, undef |
| 737 | br i1 %cmp14, label %15, label %14 |
| 738 | %val15 = volatile load float* undef |
| 739 | %cmp15 = fcmp une float %val15, undef |
| 740 | br i1 %cmp15, label %16, label %15 |
| 741 | %val16 = volatile load float* undef |
| 742 | %cmp16 = fcmp une float %val16, undef |
| 743 | br i1 %cmp16, label %17, label %16 |
| 744 | %val17 = volatile load float* undef |
| 745 | %cmp17 = fcmp une float %val17, undef |
| 746 | br i1 %cmp17, label %18, label %17 |
| 747 | %val18 = volatile load float* undef |
| 748 | %cmp18 = fcmp une float %val18, undef |
| 749 | br i1 %cmp18, label %19, label %18 |
| 750 | %val19 = volatile load float* undef |
| 751 | %cmp19 = fcmp une float %val19, undef |
| 752 | br i1 %cmp19, label %20, label %19 |
| 753 | %val20 = volatile load float* undef |
| 754 | %cmp20 = fcmp une float %val20, undef |
| 755 | br i1 %cmp20, label %21, label %20 |
| 756 | %val21 = volatile load float* undef |
| 757 | %cmp21 = fcmp une float %val21, undef |
| 758 | br i1 %cmp21, label %22, label %21 |
| 759 | %val22 = volatile load float* undef |
| 760 | %cmp22 = fcmp une float %val22, undef |
| 761 | br i1 %cmp22, label %23, label %22 |
| 762 | %val23 = volatile load float* undef |
| 763 | %cmp23 = fcmp une float %val23, undef |
| 764 | br i1 %cmp23, label %24, label %23 |
| 765 | %val24 = volatile load float* undef |
| 766 | %cmp24 = fcmp une float %val24, undef |
| 767 | br i1 %cmp24, label %25, label %24 |
| 768 | %val25 = volatile load float* undef |
| 769 | %cmp25 = fcmp une float %val25, undef |
| 770 | br i1 %cmp25, label %26, label %25 |
| 771 | %val26 = volatile load float* undef |
| 772 | %cmp26 = fcmp une float %val26, undef |
| 773 | br i1 %cmp26, label %27, label %26 |
| 774 | %val27 = volatile load float* undef |
| 775 | %cmp27 = fcmp une float %val27, undef |
| 776 | br i1 %cmp27, label %28, label %27 |
| 777 | %val28 = volatile load float* undef |
| 778 | %cmp28 = fcmp une float %val28, undef |
| 779 | br i1 %cmp28, label %29, label %28 |
| 780 | %val29 = volatile load float* undef |
| 781 | %cmp29 = fcmp une float %val29, undef |
| 782 | br i1 %cmp29, label %30, label %29 |
| 783 | %val30 = volatile load float* undef |
| 784 | %cmp30 = fcmp une float %val30, undef |
| 785 | br i1 %cmp30, label %31, label %30 |
| 786 | %val31 = volatile load float* undef |
| 787 | %cmp31 = fcmp une float %val31, undef |
| 788 | br i1 %cmp31, label %32, label %31 |
| 789 | %val32 = volatile load float* undef |
| 790 | %cmp32 = fcmp une float %val32, undef |
| 791 | br i1 %cmp32, label %33, label %32 |
| 792 | %val33 = volatile load float* undef |
| 793 | %cmp33 = fcmp une float %val33, undef |
| 794 | br i1 %cmp33, label %34, label %33 |
| 795 | %val34 = volatile load float* undef |
| 796 | %cmp34 = fcmp une float %val34, undef |
| 797 | br i1 %cmp34, label %35, label %34 |
| 798 | %val35 = volatile load float* undef |
| 799 | %cmp35 = fcmp une float %val35, undef |
| 800 | br i1 %cmp35, label %36, label %35 |
| 801 | %val36 = volatile load float* undef |
| 802 | %cmp36 = fcmp une float %val36, undef |
| 803 | br i1 %cmp36, label %37, label %36 |
| 804 | %val37 = volatile load float* undef |
| 805 | %cmp37 = fcmp une float %val37, undef |
| 806 | br i1 %cmp37, label %38, label %37 |
| 807 | %val38 = volatile load float* undef |
| 808 | %cmp38 = fcmp une float %val38, undef |
| 809 | br i1 %cmp38, label %39, label %38 |
| 810 | %val39 = volatile load float* undef |
| 811 | %cmp39 = fcmp une float %val39, undef |
| 812 | br i1 %cmp39, label %40, label %39 |
| 813 | %val40 = volatile load float* undef |
| 814 | %cmp40 = fcmp une float %val40, undef |
| 815 | br i1 %cmp40, label %41, label %40 |
| 816 | %val41 = volatile load float* undef |
| 817 | %cmp41 = fcmp une float %val41, undef |
| 818 | br i1 %cmp41, label %42, label %41 |
| 819 | %val42 = volatile load float* undef |
| 820 | %cmp42 = fcmp une float %val42, undef |
| 821 | br i1 %cmp42, label %43, label %42 |
| 822 | %val43 = volatile load float* undef |
| 823 | %cmp43 = fcmp une float %val43, undef |
| 824 | br i1 %cmp43, label %44, label %43 |
| 825 | %val44 = volatile load float* undef |
| 826 | %cmp44 = fcmp une float %val44, undef |
| 827 | br i1 %cmp44, label %45, label %44 |
| 828 | %val45 = volatile load float* undef |
| 829 | %cmp45 = fcmp une float %val45, undef |
| 830 | br i1 %cmp45, label %46, label %45 |
| 831 | %val46 = volatile load float* undef |
| 832 | %cmp46 = fcmp une float %val46, undef |
| 833 | br i1 %cmp46, label %47, label %46 |
| 834 | %val47 = volatile load float* undef |
| 835 | %cmp47 = fcmp une float %val47, undef |
| 836 | br i1 %cmp47, label %48, label %47 |
| 837 | %val48 = volatile load float* undef |
| 838 | %cmp48 = fcmp une float %val48, undef |
| 839 | br i1 %cmp48, label %49, label %48 |
| 840 | %val49 = volatile load float* undef |
| 841 | %cmp49 = fcmp une float %val49, undef |
| 842 | br i1 %cmp49, label %50, label %49 |
| 843 | %val50 = volatile load float* undef |
| 844 | %cmp50 = fcmp une float %val50, undef |
| 845 | br i1 %cmp50, label %51, label %50 |
| 846 | %val51 = volatile load float* undef |
| 847 | %cmp51 = fcmp une float %val51, undef |
| 848 | br i1 %cmp51, label %52, label %51 |
| 849 | %val52 = volatile load float* undef |
| 850 | %cmp52 = fcmp une float %val52, undef |
| 851 | br i1 %cmp52, label %53, label %52 |
| 852 | %val53 = volatile load float* undef |
| 853 | %cmp53 = fcmp une float %val53, undef |
| 854 | br i1 %cmp53, label %54, label %53 |
| 855 | %val54 = volatile load float* undef |
| 856 | %cmp54 = fcmp une float %val54, undef |
| 857 | br i1 %cmp54, label %55, label %54 |
| 858 | %val55 = volatile load float* undef |
| 859 | %cmp55 = fcmp une float %val55, undef |
| 860 | br i1 %cmp55, label %56, label %55 |
| 861 | %val56 = volatile load float* undef |
| 862 | %cmp56 = fcmp une float %val56, undef |
| 863 | br i1 %cmp56, label %57, label %56 |
| 864 | %val57 = volatile load float* undef |
| 865 | %cmp57 = fcmp une float %val57, undef |
| 866 | br i1 %cmp57, label %58, label %57 |
| 867 | %val58 = volatile load float* undef |
| 868 | %cmp58 = fcmp une float %val58, undef |
| 869 | br i1 %cmp58, label %59, label %58 |
| 870 | %val59 = volatile load float* undef |
| 871 | %cmp59 = fcmp une float %val59, undef |
| 872 | br i1 %cmp59, label %60, label %59 |
| 873 | %val60 = volatile load float* undef |
| 874 | %cmp60 = fcmp une float %val60, undef |
| 875 | br i1 %cmp60, label %61, label %60 |
| 876 | %val61 = volatile load float* undef |
| 877 | %cmp61 = fcmp une float %val61, undef |
| 878 | br i1 %cmp61, label %62, label %61 |
| 879 | %val62 = volatile load float* undef |
| 880 | %cmp62 = fcmp une float %val62, undef |
| 881 | br i1 %cmp62, label %63, label %62 |
| 882 | %val63 = volatile load float* undef |
| 883 | %cmp63 = fcmp une float %val63, undef |
| 884 | br i1 %cmp63, label %64, label %63 |
| 885 | %val64 = volatile load float* undef |
| 886 | %cmp64 = fcmp une float %val64, undef |
| 887 | br i1 %cmp64, label %65, label %64 |
| 888 | |
| 889 | br label %exit |
| 890 | exit: |
| 891 | ret void |
| 892 | } |