test/Transforms/NewGVN/basic-cyclic-opt.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 ;; Function Attrs: nounwind ssp uwtable
   6 ;; We should eliminate the sub, and one of the phi nodes
   7 define void @vnum_test1(i32* %data) #0 {
   8 ; CHECK-LABEL: @vnum_test1(
   9 ; CHECK-NEXT:  bb:
  10 ; CHECK-NEXT:    [[TMP:%.*]] = getelementptr inbounds i32, i32* [[DATA:%.*]], i64 3
  11 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TMP]], align 4
  12 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 4
  13 ; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[TMP2]], align 4
  14 ; CHECK-NEXT:    br label [[BB4:%.*]]
  15 ; CHECK:       bb4:
  16 ; CHECK-NEXT:    [[M_0:%.*]] = phi i32 [ [[TMP3]], [[BB:%.*]] ], [ [[TMP15:%.*]], [[BB17:%.*]] ]
  17 ; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[BB]] ], [ [[TMP18:%.*]], [[BB17]] ]
  18 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp slt i32 [[I_0]], [[TMP1]]
  19 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB6:%.*]], label [[BB19:%.*]]
  20 ; CHECK:       bb6:
  21 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 2
  22 ; CHECK-NEXT:    [[TMP8:%.*]] = load i32, i32* [[TMP7]], align 4
  23 ; CHECK-NEXT:    [[TMP9:%.*]] = sext i32 [[TMP8]] to i64
  24 ; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 [[TMP9]]
  25 ; CHECK-NEXT:    store i32 2, i32* [[TMP10]], align 4
  26 ; CHECK-NEXT:    store i32 0, i32* [[DATA]], align 4
  27 ; CHECK-NEXT:    [[TMP13:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 1
  28 ; CHECK-NEXT:    [[TMP14:%.*]] = load i32, i32* [[TMP13]], align 4
  29 ; CHECK-NEXT:    [[TMP15]] = add nsw i32 [[M_0]], [[TMP14]]
  30 ; CHECK-NEXT:    br label [[BB17]]
  31 ; CHECK:       bb17:
  32 ; CHECK-NEXT:    [[TMP18]] = add nsw i32 [[I_0]], 1
  33 ; CHECK-NEXT:    br label [[BB4]]
  34 ; CHECK:       bb19:
  35 ; CHECK-NEXT:    ret void
  36 ;
  37 bb:
  38   %tmp = getelementptr inbounds i32, i32* %data, i64 3
  39   %tmp1 = load i32, i32* %tmp, align 4
  40   %tmp2 = getelementptr inbounds i32, i32* %data, i64 4
  41   %tmp3 = load i32, i32* %tmp2, align 4
  42   br label %bb4
  43
  44 bb4:                                              ; preds = %bb17, %bb
  45   %m.0 = phi i32 [ %tmp3, %bb ], [ %tmp15, %bb17 ]
  46   %i.0 = phi i32 [ 0, %bb ], [ %tmp18, %bb17 ]
  47   %n.0 = phi i32 [ %tmp3, %bb ], [ %tmp16, %bb17 ]
  48   %tmp5 = icmp slt i32 %i.0, %tmp1
  49   br i1 %tmp5, label %bb6, label %bb19
  50
  51 bb6:                                              ; preds = %bb4
  52   %tmp7 = getelementptr inbounds i32, i32* %data, i64 2
  53   %tmp8 = load i32, i32* %tmp7, align 4
  54   %tmp9 = sext i32 %tmp8 to i64
  55   %tmp10 = getelementptr inbounds i32, i32* %data, i64 %tmp9
  56   store i32 2, i32* %tmp10, align 4
  57   %tmp11 = sub nsw i32 %m.0, %n.0
  58   %tmp12 = getelementptr inbounds i32, i32* %data, i64 0
  59   store i32 %tmp11, i32* %tmp12, align 4
  60   %tmp13 = getelementptr inbounds i32, i32* %data, i64 1
  61   %tmp14 = load i32, i32* %tmp13, align 4
  62   %tmp15 = add nsw i32 %m.0, %tmp14
  63   %tmp16 = add nsw i32 %n.0, %tmp14
  64   br label %bb17
  65
  66 bb17:                                             ; preds = %bb6
  67   %tmp18 = add nsw i32 %i.0, 1
  68   br label %bb4
  69
  70 bb19:                                             ; preds = %bb4
  71   ret void
  72 }
  73
  74 ;; Function Attrs: nounwind ssp uwtable
  75 ;; We should eliminate the sub, one of the phi nodes, prove the store of the sub
  76 ;; and the load of data are equivalent, that the load always produces constant 0, and
  77 ;; delete the load replacing it with constant 0.
  78 define i32 @vnum_test2(i32* %data) #0 {
  79 ; CHECK-LABEL: @vnum_test2(
  80 ; CHECK-NEXT:  bb:
  81 ; CHECK-NEXT:    [[TMP:%.*]] = getelementptr inbounds i32, i32* [[DATA:%.*]], i64 3
  82 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TMP]], align 4
  83 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 4
  84 ; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[TMP2]], align 4
  85 ; CHECK-NEXT:    br label [[BB4:%.*]]
  86 ; CHECK:       bb4:
  87 ; CHECK-NEXT:    [[M_0:%.*]] = phi i32 [ [[TMP3]], [[BB:%.*]] ], [ [[TMP15:%.*]], [[BB19:%.*]] ]
  88 ; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[BB]] ], [ [[TMP20:%.*]], [[BB19]] ]
  89 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp slt i32 [[I_0]], [[TMP1]]
  90 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB6:%.*]], label [[BB21:%.*]]
  91 ; CHECK:       bb6:
  92 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 2
  93 ; CHECK-NEXT:    [[TMP8:%.*]] = load i32, i32* [[TMP7]], align 4
  94 ; CHECK-NEXT:    [[TMP9:%.*]] = sext i32 [[TMP8]] to i64
  95 ; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 [[TMP9]]
  96 ; CHECK-NEXT:    store i32 2, i32* [[TMP10]], align 4
  97 ; CHECK-NEXT:    store i32 0, i32* [[DATA]], align 4
  98 ; CHECK-NEXT:    [[TMP13:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 1
  99 ; CHECK-NEXT:    [[TMP14:%.*]] = load i32, i32* [[TMP13]], align 4
 100 ; CHECK-NEXT:    [[TMP15]] = add nsw i32 [[M_0]], [[TMP14]]
 101 ; CHECK-NEXT:    br label [[BB19]]
 102 ; CHECK:       bb19:
 103 ; CHECK-NEXT:    [[TMP20]] = add nsw i32 [[I_0]], 1
 104 ; CHECK-NEXT:    br label [[BB4]]
 105 ; CHECK:       bb21:
 106 ; CHECK-NEXT:    ret i32 0
 107 ;
 108 bb:
 109   %tmp = getelementptr inbounds i32, i32* %data, i64 3
 110   %tmp1 = load i32, i32* %tmp, align 4
 111   %tmp2 = getelementptr inbounds i32, i32* %data, i64 4
 112   %tmp3 = load i32, i32* %tmp2, align 4
 113   br label %bb4
 114
 115 bb4:                                              ; preds = %bb19, %bb
 116   %m.0 = phi i32 [ %tmp3, %bb ], [ %tmp15, %bb19 ]
 117   %n.0 = phi i32 [ %tmp3, %bb ], [ %tmp16, %bb19 ]
 118   %i.0 = phi i32 [ 0, %bb ], [ %tmp20, %bb19 ]
 119   %p.0 = phi i32 [ undef, %bb ], [ %tmp18, %bb19 ]
 120   %tmp5 = icmp slt i32 %i.0, %tmp1
 121   br i1 %tmp5, label %bb6, label %bb21
 122
 123 bb6:                                              ; preds = %bb4
 124   %tmp7 = getelementptr inbounds i32, i32* %data, i64 2
 125   %tmp8 = load i32, i32* %tmp7, align 4
 126   %tmp9 = sext i32 %tmp8 to i64
 127   %tmp10 = getelementptr inbounds i32, i32* %data, i64 %tmp9
 128   store i32 2, i32* %tmp10, align 4
 129   %tmp11 = sub nsw i32 %m.0, %n.0
 130   %tmp12 = getelementptr inbounds i32, i32* %data, i64 0
 131   store i32 %tmp11, i32* %tmp12, align 4
 132   %tmp13 = getelementptr inbounds i32, i32* %data, i64 1
 133   %tmp14 = load i32, i32* %tmp13, align 4
 134   %tmp15 = add nsw i32 %m.0, %tmp14
 135   %tmp16 = add nsw i32 %n.0, %tmp14
 136   %tmp17 = getelementptr inbounds i32, i32* %data, i64 0
 137   %tmp18 = load i32, i32* %tmp17, align 4
 138   br label %bb19
 139
 140 bb19:                                             ; preds = %bb6
 141   %tmp20 = add nsw i32 %i.0, 1
 142   br label %bb4
 143
 144 bb21:                                             ; preds = %bb4
 145   ret i32 %p.0
 146 }
 147
 148
 149 ; Function Attrs: nounwind ssp uwtable
 150 ;; Same as test 2, with a conditional store of m-n, so it has to also discover
 151 ;; that data ends up with the same value no matter what branch is taken.
 152 define i32 @vnum_test3(i32* %data) #0 {
 153 ; CHECK-LABEL: @vnum_test3(
 154 ; CHECK-NEXT:  bb:
 155 ; CHECK-NEXT:    [[TMP:%.*]] = getelementptr inbounds i32, i32* [[DATA:%.*]], i64 3
 156 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TMP]], align 4
 157 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 4
 158 ; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[TMP2]], align 4
 159 ; CHECK-NEXT:    br label [[BB4:%.*]]
 160 ; CHECK:       bb4:
 161 ; CHECK-NEXT:    [[N_0:%.*]] = phi i32 [ [[TMP3]], [[BB:%.*]] ], [ [[TMP19:%.*]], [[BB21:%.*]] ]
 162 ; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[BB]] ], [ [[TMP22:%.*]], [[BB21]] ]
 163 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp slt i32 [[I_0]], [[TMP1]]
 164 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB6:%.*]], label [[BB23:%.*]]
 165 ; CHECK:       bb6:
 166 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 2
 167 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 5
 168 ; CHECK-NEXT:    store i32 0, i32* [[TMP9]], align 4
 169 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp slt i32 [[I_0]], 30
 170 ; CHECK-NEXT:    br i1 [[TMP10]], label [[BB11:%.*]], label [[BB14:%.*]]
 171 ; CHECK:       bb11:
 172 ; CHECK-NEXT:    br label [[BB14]]
 173 ; CHECK:       bb14:
 174 ; CHECK-NEXT:    [[TMP17:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 1
 175 ; CHECK-NEXT:    [[TMP18:%.*]] = load i32, i32* [[TMP17]], align 4
 176 ; CHECK-NEXT:    [[TMP19]] = add nsw i32 [[N_0]], [[TMP18]]
 177 ; CHECK-NEXT:    br label [[BB21]]
 178 ; CHECK:       bb21:
 179 ; CHECK-NEXT:    [[TMP22]] = add nsw i32 [[I_0]], 1
 180 ; CHECK-NEXT:    br label [[BB4]]
 181 ; CHECK:       bb23:
 182 ; CHECK-NEXT:    ret i32 0
 183 ;
 184 bb:
 185   %tmp = getelementptr inbounds i32, i32* %data, i64 3
 186   %tmp1 = load i32, i32* %tmp, align 4
 187   %tmp2 = getelementptr inbounds i32, i32* %data, i64 4
 188   %tmp3 = load i32, i32* %tmp2, align 4
 189   br label %bb4
 190
 191 bb4:                                              ; preds = %bb21, %bb
 192   %n.0 = phi i32 [ %tmp3, %bb ], [ %tmp20, %bb21 ]
 193   %m.0 = phi i32 [ %tmp3, %bb ], [ %tmp19, %bb21 ]
 194   %p.0 = phi i32 [ 0, %bb ], [ %tmp16, %bb21 ]
 195   %i.0 = phi i32 [ 0, %bb ], [ %tmp22, %bb21 ]
 196   %tmp5 = icmp slt i32 %i.0, %tmp1
 197   br i1 %tmp5, label %bb6, label %bb23
 198
 199 bb6:                                              ; preds = %bb4
 200   %tmp7 = getelementptr inbounds i32, i32* %data, i64 2
 201   %tmp8 = load i32, i32* %tmp7, align 4
 202   %tmp9 = getelementptr inbounds i32, i32* %data, i64 5
 203   store i32 0, i32* %tmp9, align 4
 204   %tmp10 = icmp slt i32 %i.0, 30
 205   br i1 %tmp10, label %bb11, label %bb14
 206
 207 bb11:                                             ; preds = %bb6
 208   %tmp12 = sub nsw i32 %m.0, %n.0
 209   %tmp13 = getelementptr inbounds i32, i32* %data, i64 5
 210   store i32 %tmp12, i32* %tmp13, align 4
 211   br label %bb14
 212
 213 bb14:                                             ; preds = %bb11, %bb6
 214   %tmp15 = getelementptr inbounds i32, i32* %data, i64 5
 215   %tmp16 = load i32, i32* %tmp15, align 4
 216   %tmp17 = getelementptr inbounds i32, i32* %data, i64 1
 217   %tmp18 = load i32, i32* %tmp17, align 4
 218   %tmp19 = add nsw i32 %m.0, %tmp18
 219   %tmp20 = add nsw i32 %n.0, %tmp18
 220   br label %bb21
 221
 222 bb21:                                             ; preds = %bb14
 223   %tmp22 = add nsw i32 %i.0, 1
 224   br label %bb4
 225
 226 bb23:                                             ; preds = %bb4
 227   ret i32 %p.0
 228 }
 229
 230 ;; This is an irreducible test case that will cause a memoryphi node loop
 231 ;; in the two blocks.
 232 ;; It's equivalent to something like
 233 ;; *a = 0
 234 ;; if (<....>) goto loopmiddle
 235 ;; loopstart:
 236 ;; loopmiddle:
 237 ;; load *a
 238 ;; *a = 0
 239 ;; if (<....>) goto loopstart otherwise goto loopend
 240 ;; loopend:
 241 ;; load *a
 242 ;; add the results of the loads
 243 ;; return them
 244 ;;
 245 ;; Both loads should equal 0, but it requires being
 246 ;; completely optimistic about MemoryPhis, otherwise
 247 ;; we will not be able to see through the cycle.
 248 define i8 @irreducible_memoryphi(i8* noalias %arg, i8* noalias %arg2) {
 249 ; CHECK-LABEL: @irreducible_memoryphi(
 250 ; CHECK-NEXT:  bb:
 251 ; CHECK-NEXT:    store i8 0, i8* [[ARG:%.*]]
 252 ; CHECK-NEXT:    br i1 undef, label [[BB2:%.*]], label [[BB1:%.*]]
 253 ; CHECK:       bb1:
 254 ; CHECK-NEXT:    br label [[BB2]]
 255 ; CHECK:       bb2:
 256 ; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB3:%.*]]
 257 ; CHECK:       bb3:
 258 ; CHECK-NEXT:    ret i8 0
 259 ;
 260 bb:
 261   store i8 0, i8 *%arg
 262   br i1 undef, label %bb2, label %bb1
 263
 264 bb1:                                              ; preds = %bb2, %bb
 265   br label %bb2
 266
 267 bb2:                                              ; preds = %bb1, %bb
 268   %tmp2 = load i8, i8* %arg
 269   store i8 0, i8 *%arg
 270   br i1 undef, label %bb1, label %bb3
 271
 272 bb3:                                              ; preds = %bb2
 273   %tmp = load i8, i8* %arg
 274   %tmp3 = add i8 %tmp, %tmp2
 275   ret i8 %tmp3
 276 }
 277 ;; This is an irreducible test case that will cause a phi node loop
 278 ;; in the two blocks
 279 ;;
 280 ;; It should return 0, but it requires being
 281 ;; completely optimistic about phis, otherwise
 282 ;; we will not be able to see through the cycle.
 283 define i32 @irreducible_phi(i32 %arg) {
 284 ; CHECK-LABEL: @irreducible_phi(
 285 ; CHECK-NEXT:  bb:
 286 ; CHECK-NEXT:    br i1 undef, label [[BB2:%.*]], label [[BB1:%.*]]
 287 ; CHECK:       bb1:
 288 ; CHECK-NEXT:    br label [[BB2]]
 289 ; CHECK:       bb2:
 290 ; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB3:%.*]]
 291 ; CHECK:       bb3:
 292 ; CHECK-NEXT:    ret i32 0
 293 ;
 294 bb:
 295   %tmp = add i32 0, %arg
 296   br i1 undef, label %bb2, label %bb1
 297
 298 bb1:                                              ; preds = %bb2, %bb
 299   %phi1 = phi i32 [%tmp, %bb], [%phi2, %bb2]
 300   br label %bb2
 301
 302 bb2:                                              ; preds = %bb1, %bb
 303   %phi2 = phi i32 [%tmp, %bb], [%phi1, %bb1]
 304   br i1 undef, label %bb1, label %bb3
 305
 306 bb3:                                              ; preds = %bb2
 307   ; This should be zero
 308   %tmp3 = sub i32 %tmp, %phi2
 309   ret i32 %tmp3
 310 }
 311 attributes #0 = { nounwind ssp uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
 312
 313 !llvm.ident = !{!0, !0, !0}
 314
 315 !0 = !{!"Apple LLVM version 6.0 (clang-600.0.56) (based on LLVM 3.5svn)"}