test/Transforms/IndVarSimplify/elim-extend.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -indvars -S | FileCheck %s
   3
   4 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
   5
   6 ; IV with constant start, preinc and postinc sign extends, with and without NSW.
   7 ; IV rewrite only removes one sext. WidenIVs removes all three.
   8 define void @postincConstIV(i8* %base, i32 %limit) nounwind {
   9 ; CHECK-LABEL: @postincConstIV(
  10 ; CHECK-NEXT:  entry:
  11 ; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[LIMIT:%.*]] to i64
  12 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  13 ; CHECK:       loop:
  14 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
  15 ; CHECK-NEXT:    [[PREADR:%.*]] = getelementptr i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
  16 ; CHECK-NEXT:    store i8 0, i8* [[PREADR]]
  17 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
  18 ; CHECK-NEXT:    [[POSTADR:%.*]] = getelementptr i8, i8* [[BASE]], i64 [[INDVARS_IV_NEXT]]
  19 ; CHECK-NEXT:    store i8 0, i8* [[POSTADR]]
  20 ; CHECK-NEXT:    [[POSTADRNSW:%.*]] = getelementptr inbounds i8, i8* [[BASE]], i64 [[INDVARS_IV_NEXT]]
  21 ; CHECK-NEXT:    store i8 0, i8* [[POSTADRNSW]]
  22 ; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i64 [[TMP0]], [[INDVARS_IV]]
  23 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
  24 ; CHECK:       exit:
  25 ; CHECK-NEXT:    br label [[RETURN:%.*]]
  26 ; CHECK:       return:
  27 ; CHECK-NEXT:    ret void
  28 ;
  29 entry:
  30   br label %loop
  31 loop:
  32   %iv = phi i32 [ %postiv, %loop ], [ 0, %entry ]
  33   %ivnsw = phi i32 [ %postivnsw, %loop ], [ 0, %entry ]
  34   %preofs = sext i32 %iv to i64
  35   %preadr = getelementptr i8, i8* %base, i64 %preofs
  36   store i8 0, i8* %preadr
  37   %postiv = add i32 %iv, 1
  38   %postofs = sext i32 %postiv to i64
  39   %postadr = getelementptr i8, i8* %base, i64 %postofs
  40   store i8 0, i8* %postadr
  41   %postivnsw = add nsw i32 %ivnsw, 1
  42   %postofsnsw = sext i32 %postivnsw to i64
  43   %postadrnsw = getelementptr inbounds i8, i8* %base, i64 %postofsnsw
  44   store i8 0, i8* %postadrnsw
  45   %cond = icmp sgt i32 %limit, %iv
  46   br i1 %cond, label %loop, label %exit
  47 exit:
  48   br label %return
  49 return:
  50   ret void
  51 }
  52
  53 ; IV with nonconstant start, preinc and postinc sign extends,
  54 ; with and without NSW.
  55 ; As with postincConstIV, WidenIVs removes all three sexts.
  56 define void @postincVarIV(i8* %base, i32 %init, i32 %limit) nounwind {
  57 ; CHECK-LABEL: @postincVarIV(
  58 ; CHECK-NEXT:  entry:
  59 ; CHECK-NEXT:    [[PRECOND:%.*]] = icmp sgt i32 [[LIMIT:%.*]], [[INIT:%.*]]
  60 ; CHECK-NEXT:    br i1 [[PRECOND]], label [[LOOP_PREHEADER:%.*]], label [[RETURN:%.*]]
  61 ; CHECK:       loop.preheader:
  62 ; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[INIT]] to i64
  63 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = sext i32 [[LIMIT]] to i64
  64 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  65 ; CHECK:       loop:
  66 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP0]], [[LOOP_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ]
  67 ; CHECK-NEXT:    [[PREADR:%.*]] = getelementptr i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
  68 ; CHECK-NEXT:    store i8 0, i8* [[PREADR]]
  69 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
  70 ; CHECK-NEXT:    [[POSTADR:%.*]] = getelementptr i8, i8* [[BASE]], i64 [[INDVARS_IV_NEXT]]
  71 ; CHECK-NEXT:    store i8 0, i8* [[POSTADR]]
  72 ; CHECK-NEXT:    [[POSTADRNSW:%.*]] = getelementptr i8, i8* [[BASE]], i64 [[INDVARS_IV_NEXT]]
  73 ; CHECK-NEXT:    store i8 0, i8* [[POSTADRNSW]]
  74 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
  75 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
  76 ; CHECK:       exit:
  77 ; CHECK-NEXT:    br label [[RETURN]]
  78 ; CHECK:       return:
  79 ; CHECK-NEXT:    ret void
  80 ;
  81 entry:
  82   %precond = icmp sgt i32 %limit, %init
  83   br i1 %precond, label %loop, label %return
  84 loop:
  85   %iv = phi i32 [ %postiv, %loop ], [ %init, %entry ]
  86   %ivnsw = phi i32 [ %postivnsw, %loop ], [ %init, %entry ]
  87   %preofs = sext i32 %iv to i64
  88   %preadr = getelementptr i8, i8* %base, i64 %preofs
  89   store i8 0, i8* %preadr
  90   %postiv = add i32 %iv, 1
  91   %postofs = sext i32 %postiv to i64
  92   %postadr = getelementptr i8, i8* %base, i64 %postofs
  93   store i8 0, i8* %postadr
  94   %postivnsw = add nsw i32 %ivnsw, 1
  95   %postofsnsw = sext i32 %postivnsw to i64
  96   %postadrnsw = getelementptr i8, i8* %base, i64 %postofsnsw
  97   store i8 0, i8* %postadrnsw
  98   %cond = icmp sgt i32 %limit, %postiv
  99   br i1 %cond, label %loop, label %exit
 100 exit:
 101   br label %return
 102 return:
 103   ret void
 104 }
 105
 106 ; Test sign extend elimination in the inner and outer loop.
 107 ; %outercount is straightforward to widen, besides being in an outer loop.
 108 ; %innercount is currently blocked by lcssa, so is not widened.
 109 ; %inneriv can be widened only after proving it has no signed-overflow
 110 ;   based on the loop test.
 111 define void @nestedIV(i8* %address, i32 %limit) nounwind {
 112 ; CHECK-LABEL: @nestedIV(
 113 ; CHECK-NEXT:  entry:
 114 ; CHECK-NEXT:    [[LIMITDEC:%.*]] = add i32 [[LIMIT:%.*]], -1
 115 ; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[LIMITDEC]] to i64
 116 ; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[LIMIT]] to i64
 117 ; CHECK-NEXT:    br label [[OUTERLOOP:%.*]]
 118 ; CHECK:       outerloop:
 119 ; CHECK-NEXT:    [[INDVARS_IV1:%.*]] = phi i64 [ [[INDVARS_IV_NEXT2:%.*]], [[OUTERMERGE:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 120 ; CHECK-NEXT:    [[INNERCOUNT:%.*]] = phi i32 [ [[INNERCOUNT_MERGE:%.*]], [[OUTERMERGE]] ], [ 0, [[ENTRY]] ]
 121 ; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i64 [[INDVARS_IV1]], -1
 122 ; CHECK-NEXT:    [[ADR1:%.*]] = getelementptr i8, i8* [[ADDRESS:%.*]], i64 [[TMP2]]
 123 ; CHECK-NEXT:    store i8 0, i8* [[ADR1]]
 124 ; CHECK-NEXT:    br label [[INNERPREHEADER:%.*]]
 125 ; CHECK:       innerpreheader:
 126 ; CHECK-NEXT:    [[INNERPRECMP:%.*]] = icmp sgt i32 [[LIMITDEC]], [[INNERCOUNT]]
 127 ; CHECK-NEXT:    br i1 [[INNERPRECMP]], label [[INNERLOOP_PREHEADER:%.*]], label [[OUTERMERGE]]
 128 ; CHECK:       innerloop.preheader:
 129 ; CHECK-NEXT:    [[TMP3:%.*]] = sext i32 [[INNERCOUNT]] to i64
 130 ; CHECK-NEXT:    br label [[INNERLOOP:%.*]]
 131 ; CHECK:       innerloop:
 132 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP3]], [[INNERLOOP_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[INNERLOOP]] ]
 133 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 134 ; CHECK-NEXT:    [[ADR2:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV]]
 135 ; CHECK-NEXT:    store i8 0, i8* [[ADR2]]
 136 ; CHECK-NEXT:    [[ADR3:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV_NEXT]]
 137 ; CHECK-NEXT:    store i8 0, i8* [[ADR3]]
 138 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[TMP0]]
 139 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[INNERLOOP]], label [[INNEREXIT:%.*]]
 140 ; CHECK:       innerexit:
 141 ; CHECK-NEXT:    [[INNERCOUNT_LCSSA_WIDE:%.*]] = phi i64 [ [[INDVARS_IV_NEXT]], [[INNERLOOP]] ]
 142 ; CHECK-NEXT:    [[TMP4:%.*]] = trunc i64 [[INNERCOUNT_LCSSA_WIDE]] to i32
 143 ; CHECK-NEXT:    br label [[OUTERMERGE]]
 144 ; CHECK:       outermerge:
 145 ; CHECK-NEXT:    [[INNERCOUNT_MERGE]] = phi i32 [ [[TMP4]], [[INNEREXIT]] ], [ [[INNERCOUNT]], [[INNERPREHEADER]] ]
 146 ; CHECK-NEXT:    [[ADR4:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV1]]
 147 ; CHECK-NEXT:    store i8 0, i8* [[ADR4]]
 148 ; CHECK-NEXT:    [[OFS5:%.*]] = sext i32 [[INNERCOUNT_MERGE]] to i64
 149 ; CHECK-NEXT:    [[ADR5:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[OFS5]]
 150 ; CHECK-NEXT:    store i8 0, i8* [[ADR5]]
 151 ; CHECK-NEXT:    [[INDVARS_IV_NEXT2]] = add nuw nsw i64 [[INDVARS_IV1]], 1
 152 ; CHECK-NEXT:    [[TMP47:%.*]] = icmp slt i64 [[INDVARS_IV_NEXT2]], [[TMP1]]
 153 ; CHECK-NEXT:    br i1 [[TMP47]], label [[OUTERLOOP]], label [[RETURN:%.*]]
 154 ; CHECK:       return:
 155 ; CHECK-NEXT:    ret void
 156 ;
 157 entry:
 158   %limitdec = add i32 %limit, -1
 159   br label %outerloop
 160
 161 ; Eliminate %ofs1 after widening outercount.
 162 ; IV rewriting hoists a gep into this block. We don't like that.
 163 outerloop:
 164   %outercount   = phi i32 [ %outerpostcount, %outermerge ], [ 0, %entry ]
 165   %innercount = phi i32 [ %innercount.merge, %outermerge ], [ 0, %entry ]
 166
 167   %outercountdec = add i32 %outercount, -1
 168   %ofs1 = sext i32 %outercountdec to i64
 169   %adr1 = getelementptr i8, i8* %address, i64 %ofs1
 170   store i8 0, i8* %adr1
 171
 172   br label %innerpreheader
 173
 174 innerpreheader:
 175   %innerprecmp = icmp sgt i32 %limitdec, %innercount
 176   br i1 %innerprecmp, label %innerloop, label %outermerge
 177
 178 ; Eliminate %ofs2 after widening inneriv.
 179 ; Eliminate %ofs3 after normalizing sext(innerpostiv)
 180 ; FIXME: We should check that indvars does not increase the number of
 181 ; IVs in this loop. sext elimination plus LFTR currently results in 2 final
 182 ; IVs. Waiting to remove LFTR.
 183 innerloop:
 184   %inneriv = phi i32 [ %innerpostiv, %innerloop ], [ %innercount, %innerpreheader ]
 185   %innerpostiv = add i32 %inneriv, 1
 186
 187   %ofs2 = sext i32 %inneriv to i64
 188   %adr2 = getelementptr i8, i8* %address, i64 %ofs2
 189   store i8 0, i8* %adr2
 190
 191   %ofs3 = sext i32 %innerpostiv to i64
 192   %adr3 = getelementptr i8, i8* %address, i64 %ofs3
 193   store i8 0, i8* %adr3
 194
 195   %innercmp = icmp sgt i32 %limitdec, %innerpostiv
 196   br i1 %innercmp, label %innerloop, label %innerexit
 197
 198 innerexit:
 199   %innercount.lcssa = phi i32 [ %innerpostiv, %innerloop ]
 200   br label %outermerge
 201
 202 ; Eliminate %ofs4 after widening outercount
 203 ; TODO: Eliminate %ofs5 after removing lcssa
 204 outermerge:
 205   %innercount.merge = phi i32 [ %innercount.lcssa, %innerexit ], [ %innercount, %innerpreheader ]
 206
 207   %ofs4 = sext i32 %outercount to i64
 208   %adr4 = getelementptr i8, i8* %address, i64 %ofs4
 209   store i8 0, i8* %adr4
 210
 211   %ofs5 = sext i32 %innercount.merge to i64
 212   %adr5 = getelementptr i8, i8* %address, i64 %ofs5
 213   store i8 0, i8* %adr5
 214
 215   %outerpostcount = add i32 %outercount, 1
 216   %tmp47 = icmp slt i32 %outerpostcount, %limit
 217   br i1 %tmp47, label %outerloop, label %return
 218
 219 return:
 220   ret void
 221 }