llvm/test/Transforms/LoopUnroll/scevunroll.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -S -indvars -loop-unroll -verify-loop-info | FileCheck %s
   3 ;
   4 ; Unit tests for loop unrolling using ScalarEvolution to compute trip counts.
   5 ;
   6 ; Indvars is run first to generate an "old" SCEV result. Some unit
   7 ; tests may check that SCEV is properly invalidated between passes.
   8
   9 ; Completely unroll loops without a canonical IV.
  10 define i32 @sansCanonical(i32* %base) nounwind {
  11 ; CHECK-LABEL: @sansCanonical(
  12 ; CHECK-NEXT:  entry:
  13 ; CHECK-NEXT:    br label [[WHILE_BODY:%.*]]
  14 ; CHECK:       while.body:
  15 ; CHECK-NEXT:    [[ADR:%.*]] = getelementptr inbounds i32, i32* [[BASE:%.*]], i64 9
  16 ; CHECK-NEXT:    [[TMP:%.*]] = load i32, i32* [[ADR]], align 8
  17 ; CHECK-NEXT:    [[ADR_1:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 8
  18 ; CHECK-NEXT:    [[TMP_1:%.*]] = load i32, i32* [[ADR_1]], align 8
  19 ; CHECK-NEXT:    [[SUM_NEXT_1:%.*]] = add i32 [[TMP]], [[TMP_1]]
  20 ; CHECK-NEXT:    [[ADR_2:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 7
  21 ; CHECK-NEXT:    [[TMP_2:%.*]] = load i32, i32* [[ADR_2]], align 8
  22 ; CHECK-NEXT:    [[SUM_NEXT_2:%.*]] = add i32 [[SUM_NEXT_1]], [[TMP_2]]
  23 ; CHECK-NEXT:    [[ADR_3:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 6
  24 ; CHECK-NEXT:    [[TMP_3:%.*]] = load i32, i32* [[ADR_3]], align 8
  25 ; CHECK-NEXT:    [[SUM_NEXT_3:%.*]] = add i32 [[SUM_NEXT_2]], [[TMP_3]]
  26 ; CHECK-NEXT:    [[ADR_4:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 5
  27 ; CHECK-NEXT:    [[TMP_4:%.*]] = load i32, i32* [[ADR_4]], align 8
  28 ; CHECK-NEXT:    [[SUM_NEXT_4:%.*]] = add i32 [[SUM_NEXT_3]], [[TMP_4]]
  29 ; CHECK-NEXT:    [[ADR_5:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 4
  30 ; CHECK-NEXT:    [[TMP_5:%.*]] = load i32, i32* [[ADR_5]], align 8
  31 ; CHECK-NEXT:    [[SUM_NEXT_5:%.*]] = add i32 [[SUM_NEXT_4]], [[TMP_5]]
  32 ; CHECK-NEXT:    [[ADR_6:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 3
  33 ; CHECK-NEXT:    [[TMP_6:%.*]] = load i32, i32* [[ADR_6]], align 8
  34 ; CHECK-NEXT:    [[SUM_NEXT_6:%.*]] = add i32 [[SUM_NEXT_5]], [[TMP_6]]
  35 ; CHECK-NEXT:    [[ADR_7:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 2
  36 ; CHECK-NEXT:    [[TMP_7:%.*]] = load i32, i32* [[ADR_7]], align 8
  37 ; CHECK-NEXT:    [[SUM_NEXT_7:%.*]] = add i32 [[SUM_NEXT_6]], [[TMP_7]]
  38 ; CHECK-NEXT:    [[ADR_8:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 1
  39 ; CHECK-NEXT:    [[TMP_8:%.*]] = load i32, i32* [[ADR_8]], align 8
  40 ; CHECK-NEXT:    [[SUM_NEXT_8:%.*]] = add i32 [[SUM_NEXT_7]], [[TMP_8]]
  41 ; CHECK-NEXT:    ret i32 [[SUM_NEXT_8]]
  42 ;
  43 entry:
  44   br label %while.body
  45
  46 while.body:
  47   %iv = phi i64 [ 10, %entry ], [ %iv.next, %while.body ]
  48   %sum = phi i32 [ 0, %entry ], [ %sum.next, %while.body ]
  49   %iv.next = add i64 %iv, -1
  50   %adr = getelementptr inbounds i32, i32* %base, i64 %iv.next
  51   %tmp = load i32, i32* %adr, align 8
  52   %sum.next = add i32 %sum, %tmp
  53   %iv.narrow = trunc i64 %iv.next to i32
  54   %cmp.i65 = icmp sgt i32 %iv.narrow, 0
  55   br i1 %cmp.i65, label %while.body, label %exit
  56
  57 exit:
  58   ret i32 %sum
  59 }
  60
  61 ; SCEV unrolling properly handles loops with multiple exits. In this
  62 ; case, the computed trip count based on a canonical IV is *not* for a
  63 ; latch block.
  64 define i64 @earlyLoopTest(i64* %base) nounwind {
  65 ; CHECK-LABEL: @earlyLoopTest(
  66 ; CHECK-NEXT:  entry:
  67 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  68 ; CHECK:       loop:
  69 ; CHECK-NEXT:    [[VAL:%.*]] = load i64, i64* [[BASE:%.*]], align 4
  70 ; CHECK-NEXT:    br label [[TAIL:%.*]]
  71 ; CHECK:       tail:
  72 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[VAL]], 0
  73 ; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP_1:%.*]], label [[EXIT2:%.*]]
  74 ; CHECK:       exit1:
  75 ; CHECK-NEXT:    [[S_LCSSA:%.*]] = phi i64 [ [[S_NEXT_2:%.*]], [[LOOP_3:%.*]] ]
  76 ; CHECK-NEXT:    ret i64 [[S_LCSSA]]
  77 ; CHECK:       exit2:
  78 ; CHECK-NEXT:    [[S_NEXT_LCSSA1:%.*]] = phi i64 [ [[VAL]], [[TAIL]] ], [ [[S_NEXT_1:%.*]], [[TAIL_1:%.*]] ], [ [[S_NEXT_2]], [[TAIL_2:%.*]] ], [ [[S_NEXT_3:%.*]], [[TAIL_3:%.*]] ]
  79 ; CHECK-NEXT:    ret i64 [[S_NEXT_LCSSA1]]
  80 ; CHECK:       loop.1:
  81 ; CHECK-NEXT:    [[ADR_1:%.*]] = getelementptr i64, i64* [[BASE]], i64 1
  82 ; CHECK-NEXT:    [[VAL_1:%.*]] = load i64, i64* [[ADR_1]], align 4
  83 ; CHECK-NEXT:    [[S_NEXT_1]] = add i64 [[VAL]], [[VAL_1]]
  84 ; CHECK-NEXT:    br label [[TAIL_1]]
  85 ; CHECK:       tail.1:
  86 ; CHECK-NEXT:    [[CMP2_1:%.*]] = icmp ne i64 [[VAL_1]], 0
  87 ; CHECK-NEXT:    br i1 [[CMP2_1]], label [[LOOP_2:%.*]], label [[EXIT2]]
  88 ; CHECK:       loop.2:
  89 ; CHECK-NEXT:    [[ADR_2:%.*]] = getelementptr i64, i64* [[BASE]], i64 2
  90 ; CHECK-NEXT:    [[VAL_2:%.*]] = load i64, i64* [[ADR_2]], align 4
  91 ; CHECK-NEXT:    [[S_NEXT_2]] = add i64 [[S_NEXT_1]], [[VAL_2]]
  92 ; CHECK-NEXT:    br label [[TAIL_2]]
  93 ; CHECK:       tail.2:
  94 ; CHECK-NEXT:    [[CMP2_2:%.*]] = icmp ne i64 [[VAL_2]], 0
  95 ; CHECK-NEXT:    br i1 [[CMP2_2]], label [[LOOP_3]], label [[EXIT2]]
  96 ; CHECK:       loop.3:
  97 ; CHECK-NEXT:    [[ADR_3:%.*]] = getelementptr i64, i64* [[BASE]], i64 3
  98 ; CHECK-NEXT:    [[VAL_3:%.*]] = load i64, i64* [[ADR_3]], align 4
  99 ; CHECK-NEXT:    [[S_NEXT_3]] = add i64 [[S_NEXT_2]], [[VAL_3]]
 100 ; CHECK-NEXT:    br i1 false, label [[TAIL_3]], label [[EXIT1:%.*]]
 101 ; CHECK:       tail.3:
 102 ; CHECK-NEXT:    br label [[EXIT2]]
 103 ;
 104 entry:
 105   br label %loop
 106
 107 loop:
 108   %iv = phi i64 [ 0, %entry ], [ %inc, %tail ]
 109   %s = phi i64 [ 0, %entry ], [ %s.next, %tail ]
 110   %adr = getelementptr i64, i64* %base, i64 %iv
 111   %val = load i64, i64* %adr
 112   %s.next = add i64 %s, %val
 113   %inc = add i64 %iv, 1
 114   %cmp = icmp ne i64 %inc, 4
 115   br i1 %cmp, label %tail, label %exit1
 116
 117 tail:
 118   %cmp2 = icmp ne i64 %val, 0
 119   br i1 %cmp2, label %loop, label %exit2
 120
 121 exit1:
 122   ret i64 %s
 123
 124 exit2:
 125   ret i64 %s.next
 126 }
 127
 128 ; SCEV properly unrolls multi-exit loops.
 129 define i32 @multiExit(i32* %base) nounwind {
 130 ; CHECK-LABEL: @multiExit(
 131 ; CHECK-NEXT:  entry:
 132 ; CHECK-NEXT:    br label [[L1:%.*]]
 133 ; CHECK:       l1:
 134 ; CHECK-NEXT:    [[VAL:%.*]] = load i32, i32* [[BASE:%.*]], align 4
 135 ; CHECK-NEXT:    br i1 false, label [[L2:%.*]], label [[EXIT1:%.*]]
 136 ; CHECK:       l2:
 137 ; CHECK-NEXT:    ret i32 [[VAL]]
 138 ; CHECK:       exit1:
 139 ; CHECK-NEXT:    ret i32 1
 140 ;
 141 entry:
 142   br label %l1
 143 l1:
 144   %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l2 ]
 145   %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l2 ]
 146   %inc1 = add i32 %iv1, 1
 147   %inc2 = add i32 %iv2, 1
 148   %adr = getelementptr i32, i32* %base, i32 %iv1
 149   %val = load i32, i32* %adr
 150   %cmp1 = icmp slt i32 %iv1, 5
 151   br i1 %cmp1, label %l2, label %exit1
 152 l2:
 153   %cmp2 = icmp slt i32 %iv2, 10
 154   br i1 %cmp2, label %l1, label %exit2
 155 exit1:
 156   ret i32 1
 157 exit2:
 158   ret i32 %val
 159 }
 160
 161
 162 ; SCEV can unroll a multi-exit loops even if the latch block has no
 163 ; known trip count, but an early exit has a known trip count. In this
 164 ; case we must be careful not to optimize the latch branch away.
 165 define i32 @multiExitIncomplete(i32* %base) nounwind {
 166 ; CHECK-LABEL: @multiExitIncomplete(
 167 ; CHECK-NEXT:  entry:
 168 ; CHECK-NEXT:    br label [[L1:%.*]]
 169 ; CHECK:       l1:
 170 ; CHECK-NEXT:    [[VAL:%.*]] = load i32, i32* [[BASE:%.*]], align 4
 171 ; CHECK-NEXT:    br label [[L2:%.*]]
 172 ; CHECK:       l2:
 173 ; CHECK-NEXT:    br label [[L3:%.*]]
 174 ; CHECK:       l3:
 175 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i32 [[VAL]], 0
 176 ; CHECK-NEXT:    br i1 [[CMP3]], label [[L1_1:%.*]], label [[EXIT3:%.*]]
 177 ; CHECK:       exit1:
 178 ; CHECK-NEXT:    ret i32 1
 179 ; CHECK:       exit2:
 180 ; CHECK-NEXT:    ret i32 2
 181 ; CHECK:       exit3:
 182 ; CHECK-NEXT:    ret i32 3
 183 ; CHECK:       l1.1:
 184 ; CHECK-NEXT:    [[ADR_1:%.*]] = getelementptr i32, i32* [[BASE]], i32 1
 185 ; CHECK-NEXT:    [[VAL_1:%.*]] = load i32, i32* [[ADR_1]], align 4
 186 ; CHECK-NEXT:    br label [[L2_1:%.*]]
 187 ; CHECK:       l2.1:
 188 ; CHECK-NEXT:    br label [[L3_1:%.*]]
 189 ; CHECK:       l3.1:
 190 ; CHECK-NEXT:    [[CMP3_1:%.*]] = icmp ne i32 [[VAL_1]], 0
 191 ; CHECK-NEXT:    br i1 [[CMP3_1]], label [[L1_2:%.*]], label [[EXIT3]]
 192 ; CHECK:       l1.2:
 193 ; CHECK-NEXT:    [[ADR_2:%.*]] = getelementptr i32, i32* [[BASE]], i32 2
 194 ; CHECK-NEXT:    [[VAL_2:%.*]] = load i32, i32* [[ADR_2]], align 4
 195 ; CHECK-NEXT:    br label [[L2_2:%.*]]
 196 ; CHECK:       l2.2:
 197 ; CHECK-NEXT:    br label [[L3_2:%.*]]
 198 ; CHECK:       l3.2:
 199 ; CHECK-NEXT:    [[CMP3_2:%.*]] = icmp ne i32 [[VAL_2]], 0
 200 ; CHECK-NEXT:    br i1 [[CMP3_2]], label [[L1_3:%.*]], label [[EXIT3]]
 201 ; CHECK:       l1.3:
 202 ; CHECK-NEXT:    [[ADR_3:%.*]] = getelementptr i32, i32* [[BASE]], i32 3
 203 ; CHECK-NEXT:    [[VAL_3:%.*]] = load i32, i32* [[ADR_3]], align 4
 204 ; CHECK-NEXT:    br label [[L2_3:%.*]]
 205 ; CHECK:       l2.3:
 206 ; CHECK-NEXT:    br label [[L3_3:%.*]]
 207 ; CHECK:       l3.3:
 208 ; CHECK-NEXT:    [[CMP3_3:%.*]] = icmp ne i32 [[VAL_3]], 0
 209 ; CHECK-NEXT:    br i1 [[CMP3_3]], label [[L1_4:%.*]], label [[EXIT3]]
 210 ; CHECK:       l1.4:
 211 ; CHECK-NEXT:    [[ADR_4:%.*]] = getelementptr i32, i32* [[BASE]], i32 4
 212 ; CHECK-NEXT:    [[VAL_4:%.*]] = load i32, i32* [[ADR_4]], align 4
 213 ; CHECK-NEXT:    br label [[L2_4:%.*]]
 214 ; CHECK:       l2.4:
 215 ; CHECK-NEXT:    br label [[L3_4:%.*]]
 216 ; CHECK:       l3.4:
 217 ; CHECK-NEXT:    [[CMP3_4:%.*]] = icmp ne i32 [[VAL_4]], 0
 218 ; CHECK-NEXT:    br i1 [[CMP3_4]], label [[L1_5:%.*]], label [[EXIT3]]
 219 ; CHECK:       l1.5:
 220 ; CHECK-NEXT:    br i1 false, label [[L2_5:%.*]], label [[EXIT1:%.*]]
 221 ; CHECK:       l2.5:
 222 ; CHECK-NEXT:    br i1 true, label [[L3_5:%.*]], label [[EXIT2:%.*]]
 223 ; CHECK:       l3.5:
 224 ; CHECK-NEXT:    br label [[EXIT3]]
 225 ;
 226 entry:
 227   br label %l1
 228 l1:
 229   %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l3 ]
 230   %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l3 ]
 231   %inc1 = add i32 %iv1, 1
 232   %inc2 = add i32 %iv2, 1
 233   %adr = getelementptr i32, i32* %base, i32 %iv1
 234   %val = load i32, i32* %adr
 235   %cmp1 = icmp slt i32 %iv1, 5
 236   br i1 %cmp1, label %l2, label %exit1
 237 l2:
 238   %cmp2 = icmp slt i32 %iv2, 10
 239   br i1 %cmp2, label %l3, label %exit2
 240 l3:
 241   %cmp3 = icmp ne i32 %val, 0
 242   br i1 %cmp3, label %l1, label %exit3
 243
 244 exit1:
 245   ret i32 1
 246 exit2:
 247   ret i32 2
 248 exit3:
 249   ret i32 3
 250 }
 251
 252 ; When loop unroll merges a loop exit with one of its parent loop's
 253 ; exits, SCEV must forget its ExitNotTaken info.
 254 define void @nestedUnroll() nounwind {
 255 ; CHECK-LABEL: @nestedUnroll(
 256 ; CHECK-NEXT:  entry:
 257 ; CHECK-NEXT:    br label [[FOR_INC:%.*]]
 258 ; CHECK:       for.inc:
 259 ; CHECK-NEXT:    br label [[FOR_BODY38:%.*]]
 260 ; CHECK:       for.body38:
 261 ; CHECK-NEXT:    br label [[FOR_BODY43:%.*]]
 262 ; CHECK:       for.body43:
 263 ; CHECK-NEXT:    br label [[FOR_BODY87:%.*]]
 264 ; CHECK:       for.body87:
 265 ; CHECK-NEXT:    br label [[FOR_BODY87]]
 266 ;
 267 entry:
 268   br label %for.inc
 269
 270 for.inc:
 271   br i1 false, label %for.inc, label %for.body38.preheader
 272
 273 for.body38.preheader:
 274   br label %for.body38
 275
 276 for.body38:
 277   %i.113 = phi i32 [ %inc76, %for.inc74 ], [ 0, %for.body38.preheader ]
 278   %mul48 = mul nsw i32 %i.113, 6
 279   br label %for.body43
 280
 281 for.body43:
 282   %j.011 = phi i32 [ 0, %for.body38 ], [ %inc72, %for.body43 ]
 283   %add49 = add nsw i32 %j.011, %mul48
 284   %sh_prom50 = zext i32 %add49 to i64
 285   %inc72 = add nsw i32 %j.011, 1
 286   br i1 false, label %for.body43, label %for.inc74
 287
 288 for.inc74:
 289   %inc76 = add nsw i32 %i.113, 1
 290   br i1 false, label %for.body38, label %for.body87.preheader
 291
 292 for.body87.preheader:
 293   br label %for.body87
 294
 295 for.body87:
 296   br label %for.body87
 297 }
 298
 299 ; PR16130: clang produces incorrect code with loop/expression at -O2
 300 ; rdar:14036816 loop-unroll makes assumptions about undefined behavior
 301 ;
 302 ; The loop latch is assumed to exit after the first iteration because
 303 ; of the induction variable's NSW flag. However, the loop latch's
 304 ; equality test is skipped and the loop exits after the second
 305 ; iteration via the early exit. So loop unrolling cannot assume that
 306 ; the loop latch's exit count of zero is an upper bound on the number
 307 ; of iterations.
 308 define void @nsw_latch(i32* %a) nounwind {
 309 ; CHECK-LABEL: @nsw_latch(
 310 ; CHECK-NEXT:  entry:
 311 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 312 ; CHECK:       for.body:
 313 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 314 ; CHECK:       for.cond:
 315 ; CHECK-NEXT:    br i1 false, label [[RETURN:%.*]], label [[FOR_BODY_1:%.*]]
 316 ; CHECK:       return:
 317 ; CHECK-NEXT:    [[B_03_LCSSA:%.*]] = phi i32 [ 0, [[FOR_COND]] ], [ 8, [[FOR_BODY_1]] ], [ 0, [[FOR_COND_1:%.*]] ]
 318 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ 0, [[FOR_COND]] ], [ 1, [[FOR_BODY_1]] ], [ 0, [[FOR_COND_1]] ]
 319 ; CHECK-NEXT:    store i32 [[B_03_LCSSA]], i32* [[A:%.*]], align 4
 320 ; CHECK-NEXT:    ret void
 321 ; CHECK:       for.body.1:
 322 ; CHECK-NEXT:    br i1 false, label [[FOR_COND_1]], label [[RETURN]]
 323 ; CHECK:       for.cond.1:
 324 ; CHECK-NEXT:    br label [[RETURN]]
 325 ;
 326 entry:
 327   br label %for.body
 328
 329 for.body:                                         ; preds = %for.cond, %entry
 330   %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ]
 331   %tobool = icmp eq i32 %b.03, 0
 332   %add = add nsw i32 %b.03, 8
 333   br i1 %tobool, label %for.cond, label %return
 334
 335 for.cond:                                         ; preds = %for.body
 336   %cmp = icmp eq i32 %add, 13
 337   br i1 %cmp, label %return, label %for.body
 338
 339 return:                                           ; preds = %for.body, %for.cond
 340   %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ]
 341   %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ]
 342   store i32 %b.03.lcssa, i32* %a, align 4
 343   ret void
 344 }