test/Analysis/ScalarEvolution/nsw.ll

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