1; RUN: opt -gvn-hoist -S < %s | FileCheck %s 2target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 3target triple = "x86_64-unknown-linux-gnu" 4 5@GlobalVar = internal global float 1.000000e+00 6 7; Check that all scalar expressions are hoisted. 8; 9; CHECK-LABEL: @scalarsHoisting 10; CHECK: fsub 11; CHECK: fmul 12; CHECK: fsub 13; CHECK: fmul 14; CHECK-NOT: fmul 15; CHECK-NOT: fsub 16define float @scalarsHoisting(float %d, float %min, float %max, float %a) { 17entry: 18 %div = fdiv float 1.000000e+00, %d 19 %cmp = fcmp oge float %div, 0.000000e+00 20 br i1 %cmp, label %if.then, label %if.else 21 22if.then: ; preds = %entry 23 %sub = fsub float %min, %a 24 %mul = fmul float %sub, %div 25 %sub1 = fsub float %max, %a 26 %mul2 = fmul float %sub1, %div 27 br label %if.end 28 29if.else: ; preds = %entry 30 %sub3 = fsub float %max, %a 31 %mul4 = fmul float %sub3, %div 32 %sub5 = fsub float %min, %a 33 %mul6 = fmul float %sub5, %div 34 br label %if.end 35 36if.end: ; preds = %if.else, %if.then 37 %tmax.0 = phi float [ %mul2, %if.then ], [ %mul6, %if.else ] 38 %tmin.0 = phi float [ %mul, %if.then ], [ %mul4, %if.else ] 39 %add = fadd float %tmax.0, %tmin.0 40 ret float %add 41} 42 43; Check that all loads and scalars depending on the loads are hoisted. 44; Check that getelementptr computation gets hoisted before the load. 45; 46; CHECK-LABEL: @readsAndScalarsHoisting 47; CHECK: load 48; CHECK: load 49; CHECK: load 50; CHECK: fsub 51; CHECK: fmul 52; CHECK: fsub 53; CHECK: fmul 54; CHECK-NOT: load 55; CHECK-NOT: fmul 56; CHECK-NOT: fsub 57define float @readsAndScalarsHoisting(float %d, float* %min, float* %max, float* %a) { 58entry: 59 %div = fdiv float 1.000000e+00, %d 60 %cmp = fcmp oge float %div, 0.000000e+00 61 br i1 %cmp, label %if.then, label %if.else 62 63if.then: ; preds = %entry 64 %A = getelementptr float, float* %min, i32 1 65 %0 = load float, float* %A, align 4 66 %1 = load float, float* %a, align 4 67 %sub = fsub float %0, %1 68 %mul = fmul float %sub, %div 69 %2 = load float, float* %max, align 4 70 %sub1 = fsub float %2, %1 71 %mul2 = fmul float %sub1, %div 72 br label %if.end 73 74if.else: ; preds = %entry 75 %3 = load float, float* %max, align 4 76 %4 = load float, float* %a, align 4 77 %sub3 = fsub float %3, %4 78 %mul4 = fmul float %sub3, %div 79 %B = getelementptr float, float* %min, i32 1 80 %5 = load float, float* %B, align 4 81 %sub5 = fsub float %5, %4 82 %mul6 = fmul float %sub5, %div 83 br label %if.end 84 85if.end: ; preds = %if.else, %if.then 86 %tmax.0 = phi float [ %mul2, %if.then ], [ %mul6, %if.else ] 87 %tmin.0 = phi float [ %mul, %if.then ], [ %mul4, %if.else ] 88 %add = fadd float %tmax.0, %tmin.0 89 ret float %add 90} 91 92; Check that we do not hoist loads after a store: the first two loads will be 93; hoisted, and then the third load will not be hoisted. 94; 95; CHECK-LABEL: @readsAndWrites 96; CHECK: load 97; CHECK: load 98; CHECK: fsub 99; CHECK: fmul 100; CHECK: store 101; CHECK: load 102; CHECK: fsub 103; CHECK: fmul 104; CHECK: load 105; CHECK: fsub 106; CHECK: fmul 107; CHECK-NOT: load 108; CHECK-NOT: fmul 109; CHECK-NOT: fsub 110define float @readsAndWrites(float %d, float* %min, float* %max, float* %a) { 111entry: 112 %div = fdiv float 1.000000e+00, %d 113 %cmp = fcmp oge float %div, 0.000000e+00 114 br i1 %cmp, label %if.then, label %if.else 115 116if.then: ; preds = %entry 117 %0 = load float, float* %min, align 4 118 %1 = load float, float* %a, align 4 119 store float %0, float* @GlobalVar 120 %sub = fsub float %0, %1 121 %mul = fmul float %sub, %div 122 %2 = load float, float* %max, align 4 123 %sub1 = fsub float %2, %1 124 %mul2 = fmul float %sub1, %div 125 br label %if.end 126 127if.else: ; preds = %entry 128 %3 = load float, float* %max, align 4 129 %4 = load float, float* %a, align 4 130 %sub3 = fsub float %3, %4 131 %mul4 = fmul float %sub3, %div 132 %5 = load float, float* %min, align 4 133 %sub5 = fsub float %5, %4 134 %mul6 = fmul float %sub5, %div 135 br label %if.end 136 137if.end: ; preds = %if.else, %if.then 138 %tmax.0 = phi float [ %mul2, %if.then ], [ %mul6, %if.else ] 139 %tmin.0 = phi float [ %mul, %if.then ], [ %mul4, %if.else ] 140 %add = fadd float %tmax.0, %tmin.0 141 ret float %add 142} 143 144; Check that we do hoist loads when the store is above the insertion point. 145; 146; CHECK-LABEL: @readsAndWriteAboveInsertPt 147; CHECK: load 148; CHECK: load 149; CHECK: load 150; CHECK: fsub 151; CHECK: fmul 152; CHECK: fsub 153; CHECK: fmul 154; CHECK-NOT: load 155; CHECK-NOT: fmul 156; CHECK-NOT: fsub 157define float @readsAndWriteAboveInsertPt(float %d, float* %min, float* %max, float* %a) { 158entry: 159 %div = fdiv float 1.000000e+00, %d 160 store float 0.000000e+00, float* @GlobalVar 161 %cmp = fcmp oge float %div, 0.000000e+00 162 br i1 %cmp, label %if.then, label %if.else 163 164if.then: ; preds = %entry 165 %0 = load float, float* %min, align 4 166 %1 = load float, float* %a, align 4 167 %sub = fsub float %0, %1 168 %mul = fmul float %sub, %div 169 %2 = load float, float* %max, align 4 170 %sub1 = fsub float %2, %1 171 %mul2 = fmul float %sub1, %div 172 br label %if.end 173 174if.else: ; preds = %entry 175 %3 = load float, float* %max, align 4 176 %4 = load float, float* %a, align 4 177 %sub3 = fsub float %3, %4 178 %mul4 = fmul float %sub3, %div 179 %5 = load float, float* %min, align 4 180 %sub5 = fsub float %5, %4 181 %mul6 = fmul float %sub5, %div 182 br label %if.end 183 184if.end: ; preds = %if.else, %if.then 185 %tmax.0 = phi float [ %mul2, %if.then ], [ %mul6, %if.else ] 186 %tmin.0 = phi float [ %mul, %if.then ], [ %mul4, %if.else ] 187 %add = fadd float %tmax.0, %tmin.0 188 ret float %add 189} 190 191; Check that dependent expressions are hoisted. 192; CHECK-LABEL: @dependentScalarsHoisting 193; CHECK: fsub 194; CHECK: fadd 195; CHECK: fdiv 196; CHECK: fmul 197; CHECK-NOT: fsub 198; CHECK-NOT: fadd 199; CHECK-NOT: fdiv 200; CHECK-NOT: fmul 201define float @dependentScalarsHoisting(float %a, float %b, i1 %c) { 202entry: 203 br i1 %c, label %if.then, label %if.else 204 205if.then: 206 %d = fsub float %b, %a 207 %e = fadd float %d, %a 208 %f = fdiv float %e, %a 209 %g = fmul float %f, %a 210 br label %if.end 211 212if.else: 213 %h = fsub float %b, %a 214 %i = fadd float %h, %a 215 %j = fdiv float %i, %a 216 %k = fmul float %j, %a 217 br label %if.end 218 219if.end: 220 %r = phi float [ %g, %if.then ], [ %k, %if.else ] 221 ret float %r 222} 223 224; Check that all independent expressions are hoisted. 225; CHECK-LABEL: @independentScalarsHoisting 226; CHECK: fsub 227; CHECK: fdiv 228; CHECK: fmul 229; CHECK: fadd 230; CHECK-NOT: fsub 231; CHECK-NOT: fdiv 232; CHECK-NOT: fmul 233define float @independentScalarsHoisting(float %a, float %b, i1 %c) { 234entry: 235 br i1 %c, label %if.then, label %if.else 236 237if.then: 238 %d = fadd float %b, %a 239 %e = fsub float %b, %a 240 %f = fdiv float %b, %a 241 %g = fmul float %b, %a 242 br label %if.end 243 244if.else: 245 %i = fadd float %b, %a 246 %h = fsub float %b, %a 247 %j = fdiv float %b, %a 248 %k = fmul float %b, %a 249 br label %if.end 250 251if.end: 252 %p = phi float [ %d, %if.then ], [ %i, %if.else ] 253 %q = phi float [ %e, %if.then ], [ %h, %if.else ] 254 %r = phi float [ %f, %if.then ], [ %j, %if.else ] 255 %s = phi float [ %g, %if.then ], [ %k, %if.else ] 256 %t = fadd float %p, %q 257 %u = fadd float %r, %s 258 %v = fadd float %t, %u 259 ret float %v 260} 261 262; Check that we hoist load and scalar expressions in triangles. 263; CHECK-LABEL: @triangleHoisting 264; CHECK: load 265; CHECK: load 266; CHECK: load 267; CHECK: fsub 268; CHECK: fmul 269; CHECK: fsub 270; CHECK: fmul 271; CHECK-NOT: load 272; CHECK-NOT: fmul 273; CHECK-NOT: fsub 274define float @triangleHoisting(float %d, float* %min, float* %max, float* %a) { 275entry: 276 %div = fdiv float 1.000000e+00, %d 277 %cmp = fcmp oge float %div, 0.000000e+00 278 br i1 %cmp, label %if.then, label %if.end 279 280if.then: ; preds = %entry 281 %0 = load float, float* %min, align 4 282 %1 = load float, float* %a, align 4 283 %sub = fsub float %0, %1 284 %mul = fmul float %sub, %div 285 %2 = load float, float* %max, align 4 286 %sub1 = fsub float %2, %1 287 %mul2 = fmul float %sub1, %div 288 br label %if.end 289 290if.end: ; preds = %entry 291 %p1 = phi float [ %mul2, %if.then ], [ 0.000000e+00, %entry ] 292 %p2 = phi float [ %mul, %if.then ], [ 0.000000e+00, %entry ] 293 %3 = load float, float* %max, align 4 294 %4 = load float, float* %a, align 4 295 %sub3 = fsub float %3, %4 296 %mul4 = fmul float %sub3, %div 297 %5 = load float, float* %min, align 4 298 %sub5 = fsub float %5, %4 299 %mul6 = fmul float %sub5, %div 300 301 %x = fadd float %p1, %mul6 302 %y = fadd float %p2, %mul4 303 %z = fadd float %x, %y 304 ret float %z 305} 306 307; Check that we do not hoist loads past stores within a same basic block. 308; CHECK-LABEL: @noHoistInSingleBBWithStore 309; CHECK: load 310; CHECK: store 311; CHECK: load 312; CHECK: store 313define i32 @noHoistInSingleBBWithStore() { 314entry: 315 %D = alloca i32, align 4 316 %0 = bitcast i32* %D to i8* 317 %bf = load i8, i8* %0, align 4 318 %bf.clear = and i8 %bf, -3 319 store i8 %bf.clear, i8* %0, align 4 320 %bf1 = load i8, i8* %0, align 4 321 %bf.clear1 = and i8 %bf1, 1 322 store i8 %bf.clear1, i8* %0, align 4 323 ret i32 0 324} 325 326; Check that we do not hoist loads past calls within a same basic block. 327; CHECK-LABEL: @noHoistInSingleBBWithCall 328; CHECK: load 329; CHECK: call 330; CHECK: load 331declare void @foo() 332define i32 @noHoistInSingleBBWithCall() { 333entry: 334 %D = alloca i32, align 4 335 %0 = bitcast i32* %D to i8* 336 %bf = load i8, i8* %0, align 4 337 %bf.clear = and i8 %bf, -3 338 call void @foo() 339 %bf1 = load i8, i8* %0, align 4 340 %bf.clear1 = and i8 %bf1, 1 341 ret i32 0 342} 343 344; Check that we do not hoist loads past stores in any branch of a diamond. 345; CHECK-LABEL: @noHoistInDiamondWithOneStore1 346; CHECK: fdiv 347; CHECK: fcmp 348; CHECK: br 349define float @noHoistInDiamondWithOneStore1(float %d, float* %min, float* %max, float* %a) { 350entry: 351 %div = fdiv float 1.000000e+00, %d 352 %cmp = fcmp oge float %div, 0.000000e+00 353 br i1 %cmp, label %if.then, label %if.else 354 355if.then: ; preds = %entry 356 store float 0.000000e+00, float* @GlobalVar 357 %0 = load float, float* %min, align 4 358 %1 = load float, float* %a, align 4 359 %sub = fsub float %0, %1 360 %mul = fmul float %sub, %div 361 %2 = load float, float* %max, align 4 362 %sub1 = fsub float %2, %1 363 %mul2 = fmul float %sub1, %div 364 br label %if.end 365 366if.else: ; preds = %entry 367 ; There are no side effects on the if.else branch. 368 %3 = load float, float* %max, align 4 369 %4 = load float, float* %a, align 4 370 %sub3 = fsub float %3, %4 371 %mul4 = fmul float %sub3, %div 372 %5 = load float, float* %min, align 4 373 %sub5 = fsub float %5, %4 374 %mul6 = fmul float %sub5, %div 375 br label %if.end 376 377if.end: ; preds = %if.else, %if.then 378 %tmax.0 = phi float [ %mul2, %if.then ], [ %mul6, %if.else ] 379 %tmin.0 = phi float [ %mul, %if.then ], [ %mul4, %if.else ] 380 381 %6 = load float, float* %max, align 4 382 %7 = load float, float* %a, align 4 383 %sub6 = fsub float %6, %7 384 %mul7 = fmul float %sub6, %div 385 %8 = load float, float* %min, align 4 386 %sub8 = fsub float %8, %7 387 %mul9 = fmul float %sub8, %div 388 389 %add = fadd float %tmax.0, %tmin.0 390 ret float %add 391} 392 393; Check that we do not hoist loads past stores from half diamond. 394; CHECK-LABEL: @noHoistInHalfDiamondPastStore 395; CHECK: load 396; CHECK-NEXT: load 397; CHECK-NEXT: store 398; CHECK-NEXT: br 399; CHECK: load 400; CHECK: load 401; CHECK: load 402; CHECK: br 403define float @noHoistInHalfDiamondPastStore(float %d, float* %min, float* %max, float* %a) { 404entry: 405 %div = fdiv float 1.000000e+00, %d 406 %cmp = fcmp oge float %div, 0.000000e+00 407 %0 = load float, float* %min, align 4 408 %1 = load float, float* %a, align 4 409 410 ; Loads should not be hoisted above this store. 411 store float 0.000000e+00, float* @GlobalVar 412 413 br i1 %cmp, label %if.then, label %if.end 414 415if.then: 416 ; There are no side effects on the if.then branch. 417 %2 = load float, float* %max, align 4 418 %3 = load float, float* %a, align 4 419 %sub3 = fsub float %2, %3 420 %mul4 = fmul float %sub3, %div 421 %4 = load float, float* %min, align 4 422 %sub5 = fsub float %4, %3 423 %mul6 = fmul float %sub5, %div 424 br label %if.end 425 426if.end: 427 %tmax.0 = phi float [ %mul4, %if.then ], [ %0, %entry ] 428 %tmin.0 = phi float [ %mul6, %if.then ], [ %1, %entry ] 429 430 %add = fadd float %tmax.0, %tmin.0 431 ret float %add 432} 433 434; Check that we do not hoist loads past a store in any branch of a diamond. 435; CHECK-LABEL: @noHoistInDiamondWithOneStore2 436; CHECK: fdiv 437; CHECK: fcmp 438; CHECK: br 439define float @noHoistInDiamondWithOneStore2(float %d, float* %min, float* %max, float* %a) { 440entry: 441 %div = fdiv float 1.000000e+00, %d 442 %cmp = fcmp oge float %div, 0.000000e+00 443 br i1 %cmp, label %if.then, label %if.else 444 445if.then: ; preds = %entry 446 ; There are no side effects on the if.then branch. 447 %0 = load float, float* %min, align 4 448 %1 = load float, float* %a, align 4 449 %sub = fsub float %0, %1 450 %mul = fmul float %sub, %div 451 %2 = load float, float* %max, align 4 452 %sub1 = fsub float %2, %1 453 %mul2 = fmul float %sub1, %div 454 br label %if.end 455 456if.else: ; preds = %entry 457 store float 0.000000e+00, float* @GlobalVar 458 %3 = load float, float* %max, align 4 459 %4 = load float, float* %a, align 4 460 %sub3 = fsub float %3, %4 461 %mul4 = fmul float %sub3, %div 462 %5 = load float, float* %min, align 4 463 %sub5 = fsub float %5, %4 464 %mul6 = fmul float %sub5, %div 465 br label %if.end 466 467if.end: ; preds = %if.else, %if.then 468 %tmax.0 = phi float [ %mul2, %if.then ], [ %mul6, %if.else ] 469 %tmin.0 = phi float [ %mul, %if.then ], [ %mul4, %if.else ] 470 471 %6 = load float, float* %max, align 4 472 %7 = load float, float* %a, align 4 473 %sub6 = fsub float %6, %7 474 %mul7 = fmul float %sub6, %div 475 %8 = load float, float* %min, align 4 476 %sub8 = fsub float %8, %7 477 %mul9 = fmul float %sub8, %div 478 479 %add = fadd float %tmax.0, %tmin.0 480 ret float %add 481} 482 483; Check that we do not hoist loads outside a loop containing stores. 484; CHECK-LABEL: @noHoistInLoopsWithStores 485; CHECK: fdiv 486; CHECK: fcmp 487; CHECK: br 488define float @noHoistInLoopsWithStores(float %d, float* %min, float* %max, float* %a) { 489entry: 490 %div = fdiv float 1.000000e+00, %d 491 %cmp = fcmp oge float %div, 0.000000e+00 492 br i1 %cmp, label %do.body, label %if.else 493 494do.body: 495 %0 = load float, float* %min, align 4 496 %1 = load float, float* %a, align 4 497 498 ; It is unsafe to hoist the loads outside the loop because of the store. 499 store float 0.000000e+00, float* @GlobalVar 500 501 %sub = fsub float %0, %1 502 %mul = fmul float %sub, %div 503 %2 = load float, float* %max, align 4 504 %sub1 = fsub float %2, %1 505 %mul2 = fmul float %sub1, %div 506 br label %while.cond 507 508while.cond: 509 %cmp1 = fcmp oge float %mul2, 0.000000e+00 510 br i1 %cmp1, label %if.end, label %do.body 511 512if.else: 513 %3 = load float, float* %max, align 4 514 %4 = load float, float* %a, align 4 515 %sub3 = fsub float %3, %4 516 %mul4 = fmul float %sub3, %div 517 %5 = load float, float* %min, align 4 518 %sub5 = fsub float %5, %4 519 %mul6 = fmul float %sub5, %div 520 br label %if.end 521 522if.end: 523 %tmax.0 = phi float [ %mul2, %while.cond ], [ %mul6, %if.else ] 524 %tmin.0 = phi float [ %mul, %while.cond ], [ %mul4, %if.else ] 525 526 %add = fadd float %tmax.0, %tmin.0 527 ret float %add 528} 529 530; Check that we hoist stores: all the instructions from the then branch 531; should be hoisted. 532; CHECK-LABEL: @hoistStores 533; CHECK: zext 534; CHECK-NEXT: trunc 535; CHECK-NEXT: getelementptr 536; CHECK-NEXT: load 537; CHECK-NEXT: getelementptr 538; CHECK-NEXT: getelementptr 539; CHECK-NEXT: store 540; CHECK-NEXT: load 541; CHECK-NEXT: load 542; CHECK-NEXT: zext 543; CHECK-NEXT: add 544; CHECK-NEXT: store 545; CHECK-NEXT: br 546; CHECK: if.then 547; CHECK: br 548 549%struct.foo = type { i16* } 550 551define void @hoistStores(%struct.foo* %s, i32* %coord, i1 zeroext %delta) { 552entry: 553 %frombool = zext i1 %delta to i8 554 %tobool = trunc i8 %frombool to i1 555 br i1 %tobool, label %if.then, label %if.else 556 557if.then: ; preds = %entry 558 %p = getelementptr inbounds %struct.foo, %struct.foo* %s, i32 0, i32 0 559 %0 = load i16*, i16** %p, align 8 560 %incdec.ptr = getelementptr inbounds i16, i16* %0, i32 1 561 store i16* %incdec.ptr, i16** %p, align 8 562 %1 = load i16, i16* %0, align 2 563 %conv = zext i16 %1 to i32 564 %2 = load i32, i32* %coord, align 4 565 %add = add i32 %2, %conv 566 store i32 %add, i32* %coord, align 4 567 br label %if.end 568 569if.else: ; preds = %entry 570 %p1 = getelementptr inbounds %struct.foo, %struct.foo* %s, i32 0, i32 0 571 %3 = load i16*, i16** %p1, align 8 572 %incdec.ptr2 = getelementptr inbounds i16, i16* %3, i32 1 573 store i16* %incdec.ptr2, i16** %p1, align 8 574 %4 = load i16, i16* %3, align 2 575 %conv3 = zext i16 %4 to i32 576 %5 = load i32, i32* %coord, align 4 577 %add4 = add i32 %5, %conv3 578 store i32 %add4, i32* %coord, align 4 579 %6 = load i16*, i16** %p1, align 8 580 %incdec.ptr6 = getelementptr inbounds i16, i16* %6, i32 1 581 store i16* %incdec.ptr6, i16** %p1, align 8 582 %7 = load i16, i16* %6, align 2 583 %conv7 = zext i16 %7 to i32 584 %shl = shl i32 %conv7, 8 585 %8 = load i32, i32* %coord, align 4 586 %add8 = add i32 %8, %shl 587 store i32 %add8, i32* %coord, align 4 588 br label %if.end 589 590if.end: ; preds = %if.else, %if.then 591 ret void 592} 593 594define i32 @mergeAlignments(i1 %b, i32* %y) { 595entry: 596 br i1 %b, label %if.then, label %if.end 597 598if.then: ; preds = %entry 599 %l1 = load i32, i32* %y, align 4 600 br label %return 601 602if.end: ; preds = %entry 603 %l2 = load i32, i32* %y, align 1 604 br label %return 605 606return: ; preds = %if.end, %if.then 607 %retval.0 = phi i32 [ %l1, %if.then ], [ %l2, %if.end ] 608 ret i32 %retval.0 609} 610; CHECK-LABEL: define i32 @mergeAlignments( 611; CHECK: %[[load:.*]] = load i32, i32* %y, align 1 612; CHECK: %[[phi:.*]] = phi i32 [ %[[load]], %{{.*}} ], [ %[[load]], %{{.*}} ] 613; CHECK: i32 %[[phi]] 614 615 616declare i8 @pr30991_f() nounwind readonly 617declare void @pr30991_f1(i8) 618define i8 @pr30991(i8* %sp, i8* %word, i1 %b1, i1 %b2) { 619entry: 620 br i1 %b1, label %a, label %b 621 622a: 623 %r0 = load i8, i8* %word, align 1 624 %incdec.ptr = getelementptr i8, i8* %sp, i32 1 625 %rr0 = call i8 @pr30991_f() nounwind readonly 626 call void @pr30991_f1(i8 %r0) 627 ret i8 %rr0 628 629b: 630 br i1 %b2, label %c, label %x 631 632c: 633 %r1 = load i8, i8* %word, align 1 634 %incdec.ptr115 = getelementptr i8, i8* %sp, i32 1 635 %rr1 = call i8 @pr30991_f() nounwind readonly 636 call void @pr30991_f1(i8 %r1) 637 ret i8 %rr1 638 639x: 640 %r2 = load i8, i8* %word, align 1 641 ret i8 %r2 642} 643 644; CHECK-LABEL: define i8 @pr30991 645; CHECK: %r0 = load i8, i8* %word, align 1 646; CHECK-NEXT: br i1 %b1, label %a, label %b 647