test/Transforms/NewGVN/completeness.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -basicaa -newgvn -S | FileCheck %s
   3 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
   4
   5 define i32 @test1(i32, i8**) {
   6 ; CHECK-LABEL: @test1(
   7 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP0:%.*]], 0
   8 ; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP5:%.*]]
   9 ; CHECK:         br label [[TMP6:%.*]]
  10 ; CHECK:         br label [[TMP6]]
  11 ; CHECK:         [[TMP7:%.*]] = phi i32 [ 75, [[TMP4]] ], [ 105, [[TMP5]] ]
  12 ; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ 5, [[TMP4]] ], [ 7, [[TMP5]] ]
  13 ; CHECK-NEXT:    ret i32 [[TMP7]]
  14 ;
  15   %3 = icmp ne i32 %0, 0
  16   br i1 %3, label %4, label %5
  17
  18 ; <label>:4:                                      ; preds = %2
  19   br label %6
  20
  21 ; <label>:5:                                      ; preds = %2
  22   br label %6
  23
  24 ; <label>:6:                                      ; preds = %5, %4
  25   %.0 = phi i32 [ 5, %4 ], [ 7, %5 ]
  26   %7 = mul nsw i32 %.0, 15
  27   ret i32 %7
  28 }
  29
  30 define i32 @test2(i32) {
  31 ; CHECK-LABEL: @test2(
  32 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP0:%.*]], 0
  33 ; CHECK-NEXT:    br i1 [[TMP2]], label [[TMP3:%.*]], label [[TMP4:%.*]]
  34 ; CHECK:         br label [[TMP5:%.*]]
  35 ; CHECK:         br label [[TMP5]]
  36 ; CHECK:         [[DOT01:%.*]] = phi i32 [ 3, [[TMP3]] ], [ 2, [[TMP4]] ]
  37 ; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ 2, [[TMP3]] ], [ 3, [[TMP4]] ]
  38 ; CHECK-NEXT:    ret i32 5
  39 ;
  40   %2 = icmp ne i32 %0, 0
  41   br i1 %2, label %3, label %4
  42
  43 ; <label>:3:                                      ; preds = %1
  44   br label %5
  45
  46 ; <label>:4:                                      ; preds = %1
  47   br label %5
  48
  49 ; <label>:5:                                      ; preds = %4, %3
  50   %.01 = phi i32 [ 3, %3 ], [ 2, %4 ]
  51   %.0 = phi i32 [ 2, %3 ], [ 3, %4 ]
  52   %6 = add nsw i32 %.01, %.0
  53   ret i32 %6
  54 }
  55 define i32 @test3(i1 %which) {
  56 ; CHECK-LABEL: @test3(
  57 ; CHECK-NEXT:  entry:
  58 ; CHECK-NEXT:    br i1 [[WHICH:%.*]], label [[FINAL:%.*]], label [[DELAY:%.*]]
  59 ; CHECK:       delay:
  60 ; CHECK-NEXT:    br label [[FINAL]]
  61 ; CHECK:       final:
  62 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ -877, [[ENTRY:%.*]] ], [ 113, [[DELAY]] ]
  63 ; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 1000, [[ENTRY]] ], [ 10, [[DELAY]] ]
  64 ; CHECK-NEXT:    ret i32 [[TMP0]]
  65 ;
  66
  67 entry:
  68   br i1 %which, label %final, label %delay
  69
  70 delay:
  71   br label %final
  72
  73 final:
  74   %A = phi i32 [ 1000, %entry ], [ 10, %delay ]
  75   %value = sub i32 123, %A
  76   ret i32 %value
  77 }
  78
  79 define <2 x i32> @test3vec(i1 %which) {
  80 ; CHECK-LABEL: @test3vec(
  81 ; CHECK-NEXT:  entry:
  82 ; CHECK-NEXT:    br i1 [[WHICH:%.*]], label [[FINAL:%.*]], label [[DELAY:%.*]]
  83 ; CHECK:       delay:
  84 ; CHECK-NEXT:    br label [[FINAL]]
  85 ; CHECK:       final:
  86 ; CHECK-NEXT:    [[TMP0:%.*]] = phi <2 x i32> [ <i32 -877, i32 -877>, [[ENTRY:%.*]] ], [ <i32 113, i32 113>, [[DELAY]] ]
  87 ; CHECK-NEXT:    [[A:%.*]] = phi <2 x i32> [ <i32 1000, i32 1000>, [[ENTRY]] ], [ <i32 10, i32 10>, [[DELAY]] ]
  88 ; CHECK-NEXT:    ret <2 x i32> [[TMP0]]
  89 ;
  90
  91 entry:
  92   br i1 %which, label %final, label %delay
  93
  94 delay:
  95   br label %final
  96
  97 final:
  98   %A = phi <2 x i32> [ <i32 1000, i32 1000>, %entry ], [ <i32 10, i32 10>, %delay ]
  99   %value = sub <2 x i32> <i32 123, i32 123>, %A
 100   ret <2 x i32> %value
 101 }
 102
 103 define <2 x i32> @test3vec2(i1 %which) {
 104 ; CHECK-LABEL: @test3vec2(
 105 ; CHECK-NEXT:  entry:
 106 ; CHECK-NEXT:    br i1 [[WHICH:%.*]], label [[FINAL:%.*]], label [[DELAY:%.*]]
 107 ; CHECK:       delay:
 108 ; CHECK-NEXT:    br label [[FINAL]]
 109 ; CHECK:       final:
 110 ; CHECK-NEXT:    [[TMP0:%.*]] = phi <2 x i32> [ <i32 -877, i32 -2167>, [[ENTRY:%.*]] ], [ <i32 113, i32 303>, [[DELAY]] ]
 111 ; CHECK-NEXT:    [[A:%.*]] = phi <2 x i32> [ <i32 1000, i32 2500>, [[ENTRY]] ], [ <i32 10, i32 30>, [[DELAY]] ]
 112 ; CHECK-NEXT:    ret <2 x i32> [[TMP0]]
 113 ;
 114
 115 entry:
 116   br i1 %which, label %final, label %delay
 117
 118 delay:
 119   br label %final
 120
 121 final:
 122   %A = phi <2 x i32> [ <i32 1000, i32 2500>, %entry ], [ <i32 10, i32 30>, %delay ]
 123   %value = sub <2 x i32> <i32 123, i32 333>, %A
 124   ret <2 x i32> %value
 125 }
 126
 127 ;; This example is a bit contrived because we can't create fake memoryuses, so we use two loads in the if blocks
 128 define i32 @test4(i32, i8**, i32* noalias, i32* noalias) {
 129 ; CHECK-LABEL: @test4(
 130 ; CHECK-NEXT:    store i32 5, i32* [[TMP2:%.*]], align 4
 131 ; CHECK-NEXT:    store i32 7, i32* [[TMP3:%.*]], align 4
 132 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i32 [[TMP0:%.*]], 0
 133 ; CHECK-NEXT:    br i1 [[TMP5]], label [[TMP6:%.*]], label [[TMP7:%.*]]
 134 ; CHECK:         br label [[TMP8:%.*]]
 135 ; CHECK:         br label [[TMP8]]
 136 ; CHECK:         [[DOT01:%.*]] = phi i32 [ 5, [[TMP6]] ], [ 7, [[TMP7]] ]
 137 ; CHECK-NEXT:    [[DOT0:%.*]] = phi i32* [ [[TMP2]], [[TMP6]] ], [ [[TMP3]], [[TMP7]] ]
 138 ; CHECK-NEXT:    [[TMP9:%.*]] = load i32, i32* [[DOT0]], align 4
 139 ; CHECK-NEXT:    [[TMP10:%.*]] = mul nsw i32 [[TMP9]], 15
 140 ; CHECK-NEXT:    [[TMP11:%.*]] = mul nsw i32 [[TMP10]], [[DOT01]]
 141 ; CHECK-NEXT:    ret i32 [[TMP11]]
 142 ;
 143   store i32 5, i32* %2, align 4
 144   store i32 7, i32* %3, align 4
 145   %5 = icmp ne i32 %0, 0
 146   br i1 %5, label %6, label %8
 147
 148 ; <label>:6:                                      ; preds = %4
 149   %7 = load i32, i32* %2, align 4
 150   br label %10
 151
 152 ; <label>:8:                                      ; preds = %4
 153   %9 = load i32, i32* %3, align 4
 154   br label %10
 155
 156 ; <label>:10:                                     ; preds = %8, %6
 157   %.01 = phi i32 [ %7, %6 ], [ %9, %8 ]
 158   %.0 = phi i32* [ %2, %6 ], [ %3, %8 ]
 159   %11 = load i32, i32* %.0, align 4
 160   %12 = mul nsw i32 %11, 15
 161   %13 = mul nsw i32 %12, %.01
 162   ret i32 %13
 163 }
 164
 165 @global = common global [100 x i64] zeroinitializer, align 16
 166 @global.1 = common global [100 x i64] zeroinitializer, align 16
 167 define i64 @test5(i64 %arg) {
 168 ; CHECK-LABEL: @test5(
 169 ; CHECK-NEXT:  bb:
 170 ; CHECK-NEXT:    [[TMP:%.*]] = alloca i64, align 8
 171 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[ARG:%.*]], 0
 172 ; CHECK-NEXT:    br i1 [[TMP1]], label [[BB28:%.*]], label [[BB2:%.*]]
 173 ; CHECK:       bb2:
 174 ; CHECK-NEXT:    br label [[BB7:%.*]]
 175 ; CHECK:       bb4:
 176 ; CHECK-NEXT:    br label [[BB5:%.*]]
 177 ; CHECK:       bb5:
 178 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i64 [[TMP9:%.*]], 0
 179 ; CHECK-NEXT:    br i1 [[TMP6]], label [[BB27:%.*]], label [[BB7]]
 180 ; CHECK:       bb7:
 181 ; CHECK-NEXT:    [[TMP8:%.*]] = phi i64 [ [[ARG]], [[BB2]] ], [ [[TMP9]], [[BB5]] ]
 182 ; CHECK-NEXT:    [[TMP9]] = add nsw i64 [[TMP8]], -1
 183 ; CHECK-NEXT:    [[TMP10:%.*]] = load i64, i64* getelementptr inbounds ([100 x i64], [100 x i64]* @global, i64 0, i64 0), align 16
 184 ; CHECK-NEXT:    [[TMP11:%.*]] = load i64, i64* getelementptr inbounds ([100 x i64], [100 x i64]* @global.1, i64 0, i64 0), align 16
 185 ; CHECK-NEXT:    [[TMP12:%.*]] = mul nsw i64 [[TMP11]], [[TMP10]]
 186 ; CHECK-NEXT:    [[TMP13:%.*]] = icmp eq i64 [[TMP12]], 0
 187 ; CHECK-NEXT:    br i1 [[TMP13]], label [[BB5]], label [[BB14:%.*]]
 188 ; CHECK:       bb14:
 189 ; CHECK-NEXT:    br label [[BB15:%.*]]
 190 ; CHECK:       bb15:
 191 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i64 [ [[TMP25:%.*]], [[BB15]] ], [ [[TMP12]], [[BB14]] ]
 192 ; CHECK-NEXT:    [[TMP16:%.*]] = phi i64 [ [[TMP24:%.*]], [[BB15]] ], [ [[TMP11]], [[BB14]] ]
 193 ; CHECK-NEXT:    [[TMP17:%.*]] = phi i64 [ [[TMP22:%.*]], [[BB15]] ], [ [[TMP10]], [[BB14]] ]
 194 ; CHECK-NEXT:    [[TMP18:%.*]] = phi i64 [ [[TMP20:%.*]], [[BB15]] ], [ 0, [[BB14]] ]
 195 ; CHECK-NEXT:    store i64 [[TMP0]], i64* [[TMP]], align 8
 196 ; CHECK-NEXT:    [[TMP20]] = add nuw nsw i64 [[TMP18]], 1
 197 ; CHECK-NEXT:    [[TMP21:%.*]] = getelementptr inbounds [100 x i64], [100 x i64]* @global, i64 0, i64 [[TMP20]]
 198 ; CHECK-NEXT:    [[TMP22]] = load i64, i64* [[TMP21]], align 8
 199 ; CHECK-NEXT:    [[TMP23:%.*]] = getelementptr inbounds [100 x i64], [100 x i64]* @global.1, i64 0, i64 [[TMP20]]
 200 ; CHECK-NEXT:    [[TMP24]] = load i64, i64* [[TMP23]], align 8
 201 ; CHECK-NEXT:    [[TMP25]] = mul nsw i64 [[TMP24]], [[TMP22]]
 202 ; CHECK-NEXT:    [[TMP26:%.*]] = icmp eq i64 [[TMP20]], [[TMP25]]
 203 ; CHECK-NEXT:    br i1 [[TMP26]], label [[BB4:%.*]], label [[BB15]]
 204 ; CHECK:       bb27:
 205 ; CHECK-NEXT:    br label [[BB28]]
 206 ; CHECK:       bb28:
 207 ; CHECK-NEXT:    ret i64 0
 208 ;
 209 bb:
 210   %tmp = alloca i64, align 8
 211   %tmp1 = icmp eq i64 %arg, 0
 212   br i1 %tmp1, label %bb28, label %bb2
 213
 214 bb2:                                              ; preds = %bb
 215   %tmp3 = bitcast i64* %tmp to i8*
 216   br label %bb7
 217
 218 bb4:                                              ; preds = %bb15
 219   br label %bb5
 220
 221 bb5:                                              ; preds = %bb7, %bb4
 222   %tmp6 = icmp eq i64 %tmp9, 0
 223   br i1 %tmp6, label %bb27, label %bb7
 224
 225 bb7:                                              ; preds = %bb5, %bb2
 226   %tmp8 = phi i64 [ %arg, %bb2 ], [ %tmp9, %bb5 ]
 227   %tmp9 = add nsw i64 %tmp8, -1
 228   %tmp10 = load i64, i64* getelementptr inbounds ([100 x i64], [100 x i64]* @global, i64 0, i64 0), align 16
 229   %tmp11 = load i64, i64* getelementptr inbounds ([100 x i64], [100 x i64]* @global.1, i64 0, i64 0), align 16
 230   %tmp12 = mul nsw i64 %tmp11, %tmp10
 231   %tmp13 = icmp eq i64 %tmp12, 0
 232   br i1 %tmp13, label %bb5, label %bb14
 233
 234 bb14:                                             ; preds = %bb7
 235   br label %bb15
 236
 237 bb15:                                             ; preds = %bb15, %bb14
 238   %tmp16 = phi i64 [ %tmp24, %bb15 ], [ %tmp11, %bb14 ]
 239   %tmp17 = phi i64 [ %tmp22, %bb15 ], [ %tmp10, %bb14 ]
 240   %tmp18 = phi i64 [ %tmp20, %bb15 ], [ 0, %bb14 ]
 241 ;; This multiply is an op of phis which is really equivalent to phi(tmp25, tmp12)
 242   %tmp19 = mul nsw i64 %tmp16, %tmp17
 243   store i64 %tmp19, i64* %tmp, align 8
 244   %tmp20 = add nuw nsw i64 %tmp18, 1
 245   %tmp21 = getelementptr inbounds [100 x i64], [100 x i64]* @global, i64 0, i64 %tmp20
 246   %tmp22 = load i64, i64* %tmp21, align 8
 247   %tmp23 = getelementptr inbounds [100 x i64], [100 x i64]* @global.1, i64 0, i64 %tmp20
 248   %tmp24 = load i64, i64* %tmp23, align 8
 249   %tmp25 = mul nsw i64 %tmp24, %tmp22
 250   %tmp26 = icmp eq i64 %tmp20, %tmp25
 251   br i1 %tmp26, label %bb4, label %bb15
 252
 253 bb27:                                             ; preds = %bb5
 254   br label %bb28
 255
 256 bb28:                                             ; preds = %bb27, %bb
 257   ret i64 0
 258 }
 259
 260 ;; These icmps are all equivalent to phis of constants
 261 define i8 @test6(i8* %addr) {
 262 ; CHECK-LABEL: @test6(
 263 ; CHECK-NEXT:  entry-block:
 264 ; CHECK-NEXT:    br label %main-loop
 265 ; CHECK:       main-loop:
 266 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ true, %entry-block ], [ false, [[CORE:%.*]] ]
 267 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ false, %entry-block ], [ true, [[CORE]] ]
 268 ; CHECK-NEXT:    [[PHI:%.*]] = phi i8 [ 0, %entry-block ], [ 1, [[CORE]] ]
 269 ; CHECK-NEXT:    store volatile i8 0, i8* [[ADDR:%.*]]
 270 ; CHECK-NEXT:    br i1 [[TMP0]], label %busy-wait-phi-0, label [[EXIT:%.*]]
 271 ; CHECK:       busy-wait-phi-0:
 272 ; CHECK-NEXT:    [[LOAD:%.*]] = load volatile i8, i8* [[ADDR]]
 273 ; CHECK-NEXT:    [[ICMP:%.*]] = icmp eq i8 [[LOAD]], 0
 274 ; CHECK-NEXT:    br i1 [[ICMP]], label %busy-wait-phi-0, label [[CORE]]
 275 ; CHECK:       core:
 276 ; CHECK-NEXT:    br i1 [[TMP1]], label [[TRAP:%.*]], label %main-loop
 277 ; CHECK:       trap:
 278 ; CHECK-NEXT:    ret i8 1
 279 ; CHECK:       exit:
 280 ; CHECK-NEXT:    ret i8 0
 281 ;
 282 entry-block:
 283   br label %main-loop
 284
 285 main-loop:
 286   %phi = phi i8 [ 0, %entry-block ], [ 1, %core ]
 287   %switch_0 = icmp eq i8 %phi, 0
 288   store volatile i8 0, i8* %addr
 289   br i1 %switch_0, label %busy-wait-phi-0, label %exit
 290
 291 busy-wait-phi-0:
 292   %load = load volatile i8, i8* %addr
 293   %icmp = icmp eq i8 %load, 0
 294   br i1 %icmp, label %busy-wait-phi-0, label %core
 295
 296 core:
 297   %switch_1 = icmp eq i8 %phi, 1
 298   br i1 %switch_1, label %trap, label %main-loop
 299
 300 trap:
 301   ret i8 1
 302
 303 exit:
 304   ret i8 0
 305 }
 306
 307 ; Test that we don't infinite loop simplifying
 308 ; an undefined value that can go both ways.
 309 define void @test7() {
 310 ; CHECK-LABEL: @test7(
 311 ; CHECK-NEXT:  bb:
 312 ; CHECK-NEXT:    br label [[BB1:%.*]]
 313 ; CHECK:       bb1:
 314 ; CHECK-NEXT:    br label [[BB1]]
 315 ;
 316 bb:
 317   br label %bb1
 318
 319 bb1:                                              ; preds = %bb1, %bb
 320   %tmp = phi i32 [ undef, %bb ], [ %tmp3, %bb1 ]
 321   %tmp2 = icmp eq i32 %tmp, 0
 322   %tmp3 = select i1 %tmp2, i32 1, i32 %tmp
 323   br label %bb1
 324 }
 325
 326
 327
 328 ; Test that we get a consistent answer about what the
 329 ; value of this undefined select is.
 330 define void @test8() {
 331 ; CHECK-LABEL: @test8(
 332 ; CHECK-NEXT:  bb:
 333 ; CHECK-NEXT:    br label [[BB1:%.*]]
 334 ; CHECK:       bb1:
 335 ; CHECK-NEXT:    br label [[BB1]]
 336 ;
 337 bb:
 338   %tmp = select i1 undef, i8 0, i8 1
 339   br label %bb1
 340
 341 bb1:                                              ; preds = %bb1, %bb
 342   %tmp2 = phi i8 [ %tmp4, %bb1 ], [ %tmp, %bb ]
 343   %tmp3 = icmp eq i8 %tmp2, 0
 344   %tmp4 = select i1 %tmp3, i8 1, i8 %tmp2
 345   br label %bb1
 346 }
 347
 348
 349 ;; Make sure we handle the case where we later come up with an expression that we need
 350 ;; for a phi of ops.
 351 define void @test9() {
 352 ; CHECK-LABEL: @test9(
 353 ; CHECK-NEXT:  bb:
 354 ; CHECK-NEXT:    br label [[BB1:%.*]]
 355 ; CHECK:       bb1:
 356 ; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB2:%.*]]
 357 ; CHECK:       bb2:
 358 ; CHECK-NEXT:    br label [[BB6:%.*]]
 359 ; CHECK:       bb6:
 360 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ -13, [[BB2]] ], [ [[TMP11:%.*]], [[BB6]] ]
 361 ; CHECK-NEXT:    [[TMP7:%.*]] = phi i32 [ 1, [[BB2]] ], [ [[TMP8:%.*]], [[BB6]] ]
 362 ; CHECK-NEXT:    [[TMP8]] = add nuw nsw i32 [[TMP7]], 1
 363 ; CHECK-NEXT:    [[TMP11]] = add i32 -14, [[TMP8]]
 364 ; CHECK-NEXT:    br label [[BB6]]
 365 ;
 366 bb:
 367   br label %bb1
 368
 369 bb1:                                              ; preds = %bb1, %bb
 370   br i1 undef, label %bb1, label %bb2
 371
 372 bb2:                                              ; preds = %bb1
 373   %tmp = select i1 true, i32 -14, i32 -10
 374   %tmp3 = add i32 %tmp, 0
 375   %tmp4 = select i1 true, i32 -14, i32 -10
 376   %tmp5 = add i32 %tmp4, 0
 377   br label %bb6
 378
 379 bb6:                                              ; preds = %bb6, %bb2
 380   %tmp7 = phi i32 [ 1, %bb2 ], [ %tmp13, %bb6 ]
 381   %tmp8 = add nuw nsw i32 %tmp7, 1
 382   %tmp9 = add i32 %tmp3, %tmp7
 383   %tmp10 = select i1 false, i32 undef, i32 %tmp9
 384   %tmp11 = add i32 %tmp5, %tmp8
 385   %tmp12 = select i1 undef, i32 undef, i32 %tmp11
 386   %tmp13 = add nuw nsw i32 %tmp7, 1
 387   br label %bb6
 388 }
 389
 390 ;; Ensure that we revisit predicateinfo operands at the right points in time.
 391 define void @test10() {
 392 b:
 393   %m = getelementptr i32, i32* null, i64 8
 394   br label %g
 395
 396 g:                                                ; preds = %i, %b
 397   %n = phi i32* [ %h, %i ], [ null, %b ]
 398   %h = getelementptr i32, i32* %n, i64 1
 399   %j = icmp eq i32* %h, %m
 400   br i1 %j, label %c, label %i
 401
 402 i:                                                ; preds = %g
 403   br i1 undef, label %k, label %g
 404
 405 k:                                                ; preds = %i
 406   %l = icmp eq i32* %n, %m
 407   br i1 %l, label %c, label %o
 408
 409 o:                                                ; preds = %k
 410   br label %c
 411
 412 c:                                                ; preds = %o, %k, %g
 413   %0 = phi i32* [ undef, %o ], [ %m, %k ], [ %m, %g ]
 414   ret void
 415 }