llvm/test/Analysis/ScalarEvolution/nsw.ll

   1 ; RUN: opt < %s -analyze -enable-new-pm=0 -scalar-evolution | FileCheck %s
   2 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
   3
   4 ; The addrecs in this loop are analyzable only by using nsw information.
   5
   6 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64"
   7
   8 ; CHECK: Classifying expressions for: @test1
   9 define void @test1(double* %p) nounwind {
  10 entry:
  11         %tmp = load double, double* %p, align 8         ; <double> [#uses=1]
  12         %tmp1 = fcmp ogt double %tmp, 2.000000e+00              ; <i1> [#uses=1]
  13         br i1 %tmp1, label %bb.nph, label %return
  14
  15 bb.nph:         ; preds = %entry
  16         br label %bb
  17
  18 bb:             ; preds = %bb1, %bb.nph
  19         %i.01 = phi i32 [ %tmp8, %bb1 ], [ 0, %bb.nph ]         ; <i32> [#uses=3]
  20 ; CHECK: %i.01
  21 ; CHECK-NEXT: -->  {0,+,1}<nuw><nsw><%bb>
  22         %tmp2 = sext i32 %i.01 to i64           ; <i64> [#uses=1]
  23         %tmp3 = getelementptr double, double* %p, i64 %tmp2             ; <double*> [#uses=1]
  24         %tmp4 = load double, double* %tmp3, align 8             ; <double> [#uses=1]
  25         %tmp5 = fmul double %tmp4, 9.200000e+00         ; <double> [#uses=1]
  26         %tmp6 = sext i32 %i.01 to i64           ; <i64> [#uses=1]
  27         %tmp7 = getelementptr double, double* %p, i64 %tmp6             ; <double*> [#uses=1]
  28 ; CHECK: %tmp7
  29 ; CHECK-NEXT:   -->  {%p,+,8}<%bb>
  30         store double %tmp5, double* %tmp7, align 8
  31         %tmp8 = add nsw i32 %i.01, 1            ; <i32> [#uses=2]
  32 ; CHECK: %tmp8
  33 ; CHECK-NEXT: -->  {1,+,1}<nuw><nsw><%bb>
  34         %p.gep = getelementptr double, double* %p, i32 %tmp8
  35         %p.val = load double, double* %p.gep
  36         br label %bb1
  37
  38 bb1:            ; preds = %bb
  39         %phitmp = sext i32 %tmp8 to i64         ; <i64> [#uses=1]
  40 ; CHECK: %phitmp
  41 ; CHECK-NEXT: -->  {1,+,1}<nuw><nsw><%bb>
  42         %tmp9 = getelementptr inbounds double, double* %p, i64 %phitmp          ; <double*> [#uses=1]
  43 ; CHECK: %tmp9
  44 ; CHECK-NEXT:  -->  {(8 + %p)<nuw>,+,8}<nuw><%bb>
  45         %tmp10 = load double, double* %tmp9, align 8            ; <double> [#uses=1]
  46         %tmp11 = fcmp ogt double %tmp10, 2.000000e+00           ; <i1> [#uses=1]
  47         br i1 %tmp11, label %bb, label %bb1.return_crit_edge
  48
  49 bb1.return_crit_edge:           ; preds = %bb1
  50         br label %return
  51
  52 return:         ; preds = %bb1.return_crit_edge, %entry
  53         ret void
  54 }
  55
  56 ; CHECK: Classifying expressions for: @test2
  57 define void @test2(i32* %begin, i32* %end) ssp {
  58 entry:
  59   %cmp1.i.i = icmp eq i32* %begin, %end
  60   br i1 %cmp1.i.i, label %_ZSt4fillIPiiEvT_S1_RKT0_.exit, label %for.body.lr.ph.i.i
  61
  62 for.body.lr.ph.i.i:                               ; preds = %entry
  63   br label %for.body.i.i
  64
  65 for.body.i.i:                                     ; preds = %for.body.i.i, %for.body.lr.ph.i.i
  66   %__first.addr.02.i.i = phi i32* [ %begin, %for.body.lr.ph.i.i ], [ %ptrincdec.i.i, %for.body.i.i ]
  67 ; CHECK: %__first.addr.02.i.i
  68 ; CHECK-NEXT: -->  {%begin,+,4}<nuw><%for.body.i.i>
  69   store i32 0, i32* %__first.addr.02.i.i, align 4
  70   %ptrincdec.i.i = getelementptr inbounds i32, i32* %__first.addr.02.i.i, i64 1
  71 ; CHECK: %ptrincdec.i.i
  72 ; CHECK-NEXT: -->  {(4 + %begin)<nuw>,+,4}<nuw><%for.body.i.i>
  73   %cmp.i.i = icmp eq i32* %ptrincdec.i.i, %end
  74   br i1 %cmp.i.i, label %for.cond.for.end_crit_edge.i.i, label %for.body.i.i
  75
  76 for.cond.for.end_crit_edge.i.i:                   ; preds = %for.body.i.i
  77   br label %_ZSt4fillIPiiEvT_S1_RKT0_.exit
  78
  79 _ZSt4fillIPiiEvT_S1_RKT0_.exit:                   ; preds = %entry, %for.cond.for.end_crit_edge.i.i
  80   ret void
  81 }
  82
  83 ; Various checks for inbounds geps.
  84 define void @test3(i32* %begin, i32* %end) nounwind ssp {
  85 entry:
  86   %cmp7.i.i = icmp eq i32* %begin, %end
  87   br i1 %cmp7.i.i, label %_ZSt4fillIPiiEvT_S1_RKT0_.exit, label %for.body.i.i
  88
  89 for.body.i.i:                                     ; preds = %entry, %for.body.i.i
  90   %indvar.i.i = phi i64 [ %tmp, %for.body.i.i ], [ 0, %entry ]
  91 ; CHECK: %indvar.i.i
  92 ; CHECK: {0,+,1}<nuw><nsw><%for.body.i.i>
  93   %tmp = add nsw i64 %indvar.i.i, 1
  94 ; CHECK: %tmp =
  95 ; CHECK: {1,+,1}<nuw><nsw><%for.body.i.i>
  96   %ptrincdec.i.i = getelementptr inbounds i32, i32* %begin, i64 %tmp
  97 ; CHECK: %ptrincdec.i.i =
  98 ; CHECK: {(4 + %begin)<nuw>,+,4}<nuw><%for.body.i.i>
  99   %__first.addr.08.i.i = getelementptr inbounds i32, i32* %begin, i64 %indvar.i.i
 100 ; CHECK: %__first.addr.08.i.i
 101 ; CHECK: {%begin,+,4}<nuw><%for.body.i.i>
 102   store i32 0, i32* %__first.addr.08.i.i, align 4
 103   %cmp.i.i = icmp eq i32* %ptrincdec.i.i, %end
 104   br i1 %cmp.i.i, label %_ZSt4fillIPiiEvT_S1_RKT0_.exit, label %for.body.i.i
 105 ; CHECK: Loop %for.body.i.i: backedge-taken count is ((-4 + (-1 * (ptrtoint i32* %begin to i64)) + (ptrtoint i32* %end to i64)) /u 4)
 106 ; CHECK: Loop %for.body.i.i: max backedge-taken count is 4611686018427387903
 107 _ZSt4fillIPiiEvT_S1_RKT0_.exit:                   ; preds = %for.body.i.i, %entry
 108   ret void
 109 }
 110
 111 ; A single AddExpr exists for (%a + %b), which is not always <nsw>.
 112 ; CHECK: @addnsw
 113 ; CHECK-NOT: --> (%a + %b)<nsw>
 114 define i32 @addnsw(i32 %a, i32 %b) nounwind ssp {
 115 entry:
 116   %tmp = add i32 %a, %b
 117   %cmp = icmp sgt i32 %tmp, 0
 118   br i1 %cmp, label %greater, label %exit
 119
 120 greater:
 121   %tmp2 = add nsw i32 %a, %b
 122   br label %exit
 123
 124 exit:
 125   %result = phi i32 [ %a, %entry ], [ %tmp2, %greater ]
 126   ret i32 %result
 127 }
 128
 129 ; CHECK-LABEL: PR12375
 130 ; CHECK: -->  {(4 + %arg)<nuw>,+,4}<nuw><%bb1>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (8 + %arg)<nuw>
 131
 132 define i32 @PR12375(i32* readnone %arg) {
 133 bb:
 134   %tmp = getelementptr inbounds i32, i32* %arg, i64 2
 135   br label %bb1
 136
 137 bb1:                                              ; preds = %bb1, %bb
 138   %tmp2 = phi i32* [ %arg, %bb ], [ %tmp5, %bb1 ]
 139   %tmp3 = phi i32 [ 0, %bb ], [ %tmp4, %bb1 ]
 140   %tmp4 = add nsw i32 %tmp3, 1
 141   %tmp5 = getelementptr inbounds i32, i32* %tmp2, i64 1
 142   %tmp6 = icmp ult i32* %tmp5, %tmp
 143   br i1 %tmp6, label %bb1, label %bb7
 144
 145 bb7:                                              ; preds = %bb1
 146   ret i32 %tmp4
 147 }
 148
 149 ; CHECK-LABEL: PR12376
 150 ; CHECK: -->  {(4 + %arg)<nuw>,+,4}<nuw><%bb2>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (4 + (4 * ((-1 + (-1 * (ptrtoint i32* %arg to i64)) + ((4 + (ptrtoint i32* %arg to i64))<nuw> umax (ptrtoint i32* %arg1 to i64))) /u 4))<nuw> + %arg)
 151 define void @PR12376(i32* nocapture %arg, i32* nocapture %arg1)  {
 152 bb:
 153   br label %bb2
 154
 155 bb2:                                              ; preds = %bb2, %bb
 156   %tmp = phi i32* [ %arg, %bb ], [ %tmp4, %bb2 ]
 157   %tmp4 = getelementptr inbounds i32, i32* %tmp, i64 1
 158   %tmp3 = icmp ult i32* %tmp4, %arg1
 159   br i1 %tmp3, label %bb2, label %bb5
 160
 161 bb5:                                              ; preds = %bb2
 162   ret void
 163 }
 164
 165 declare void @f(i32)
 166
 167 ; CHECK-LABEL: nswnowrap
 168 ; CHECK: --> {(1 + %v)<nsw>,+,1}<nsw><%for.body>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (1 + ((1 + %v)<nsw> smax %v))
 169 define void @nswnowrap(i32 %v, i32* %buf) {
 170 entry:
 171   %add = add nsw i32 %v, 1
 172   br label %for.body
 173
 174 for.body:
 175   %i.04 = phi i32 [ %v, %entry ], [ %inc, %for.body ]
 176   %inc = add nsw i32 %i.04, 1
 177   %buf.gep = getelementptr inbounds i32, i32* %buf, i32 %inc
 178   %buf.val = load i32, i32* %buf.gep
 179   %cmp = icmp slt i32 %i.04, %add
 180   tail call void @f(i32 %i.04)
 181   br i1 %cmp, label %for.body, label %for.end
 182
 183 for.end:
 184   ret void
 185 }
 186
 187 ; This test checks if no-wrap flags are propagated when folding {S,+,X}+T ==> {S+T,+,X}
 188 ; CHECK-LABEL: test4
 189 ; CHECK: %idxprom
 190 ; CHECK-NEXT: -->  {(-2 + (sext i32 %arg to i64))<nsw>,+,1}<nsw><%for.body>
 191 define void @test4(i32 %arg) {
 192 entry:
 193   %array = alloca [10 x i32], align 4
 194   br label %for.body
 195
 196 for.body:
 197   %index = phi i32 [ %inc5, %for.body ], [ %arg, %entry ]
 198   %sub = add nsw i32 %index, -2
 199   %idxprom = sext i32 %sub to i64
 200   %arrayidx = getelementptr inbounds [10 x i32], [10 x i32]* %array, i64 0, i64 %idxprom
 201   %data = load i32, i32* %arrayidx, align 4
 202   %inc5 = add nsw i32 %index, 1
 203   %cmp2 = icmp slt i32 %inc5, 10
 204   br i1 %cmp2, label %for.body, label %for.end
 205
 206 for.end:
 207   ret void
 208 }
 209
 210
 211 define void @bad_postinc_nsw_a(i32 %n) {
 212 ; CHECK-LABEL: Classifying expressions for: @bad_postinc_nsw_a
 213 entry:
 214   br label %loop
 215
 216 loop:
 217   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
 218   %iv.inc = add nsw i32 %iv, 7
 219 ; CHECK:    %iv.inc = add nsw i32 %iv, 7
 220 ; CHECK-NEXT:  -->  {7,+,7}<nuw><%loop>
 221   %becond = icmp ult i32 %iv, %n
 222   br i1 %becond, label %loop, label %leave
 223
 224 leave:
 225   ret void
 226 }
 227
 228 ; Unlike @bad_postinc_nsw_a(), the SCEV expression of %iv.inc has <nsw> flag
 229 ; because poison can be propagated through 'and %iv.inc, 0'.
 230 define void @postinc_poison_prop_through_and(i32 %n) {
 231 ; CHECK-LABEL: Classifying expressions for: @postinc_poison_prop_through_and
 232 entry:
 233   br label %loop
 234
 235 loop:
 236   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
 237   %iv.inc = add nsw i32 %iv, 7
 238   %iv.inc.and = and i32 %iv.inc, 0
 239 ; CHECK:    %iv.inc = add nsw i32 %iv, 7
 240 ; CHECK-NEXT:  -->  {7,+,7}<nuw><nsw><%loop>
 241   %becond = icmp ult i32 %iv.inc.and, %n
 242   br i1 %becond, label %loop, label %leave
 243
 244 leave:
 245   ret void
 246 }
 247
 248 declare void @may_exit() nounwind
 249
 250 define void @pr28012(i32 %n) {
 251 ; CHECK-LABEL: Classifying expressions for: @pr28012
 252 entry:
 253   br label %loop
 254
 255 loop:
 256   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
 257   %iv.inc = add nsw i32 %iv, 7
 258 ; CHECK:    %iv.inc = add nsw i32 %iv, 7
 259 ; CHECK-NEXT:  -->  {7,+,7}<nuw><%loop>
 260   %becond = icmp ult i32 %iv.inc, %n
 261   call void @may_exit()
 262   br i1 %becond, label %loop, label %leave
 263
 264 leave:
 265   ret void
 266 }