test/Transforms/LoopUnroll/scevunroll.ll

   1 ; RUN: opt < %s -S -indvars -loop-unroll -verify-loop-info | FileCheck %s
   2 ;
   3 ; Unit tests for loop unrolling using ScalarEvolution to compute trip counts.
   4 ;
   5 ; Indvars is run first to generate an "old" SCEV result. Some unit
   6 ; tests may check that SCEV is properly invalidated between passes.
   7
   8 ; Completely unroll loops without a canonical IV.
   9 ;
  10 ; CHECK: @sansCanonical
  11 ; CHECK-NOT: phi
  12 ; CHECK-NOT: icmp
  13 ; CHECK: ret
  14 define i32 @sansCanonical(i32* %base) nounwind {
  15 entry:
  16   br label %while.body
  17
  18 while.body:
  19   %iv = phi i64 [ 10, %entry ], [ %iv.next, %while.body ]
  20   %sum = phi i32 [ 0, %entry ], [ %sum.next, %while.body ]
  21   %iv.next = add i64 %iv, -1
  22   %adr = getelementptr inbounds i32* %base, i64 %iv.next
  23   %tmp = load i32* %adr, align 8
  24   %sum.next = add i32 %sum, %tmp
  25   %iv.narrow = trunc i64 %iv.next to i32
  26   %cmp.i65 = icmp sgt i32 %iv.narrow, 0
  27   br i1 %cmp.i65, label %while.body, label %exit
  28
  29 exit:
  30   ret i32 %sum
  31 }
  32
  33 ; SCEV unrolling properly handles loops with multiple exits. In this
  34 ; case, the computed trip count based on a canonical IV is *not* for a
  35 ; latch block. Canonical unrolling incorrectly unrolls it, but SCEV
  36 ; unrolling does not.
  37 ;
  38 ; CHECK: @earlyLoopTest
  39 ; CHECK: tail:
  40 ; CHECK-NOT: br
  41 ; CHECK: br i1 %cmp2, label %loop, label %exit2
  42 define i64 @earlyLoopTest(i64* %base) nounwind {
  43 entry:
  44   br label %loop
  45
  46 loop:
  47   %iv = phi i64 [ 0, %entry ], [ %inc, %tail ]
  48   %s = phi i64 [ 0, %entry ], [ %s.next, %tail ]
  49   %adr = getelementptr i64* %base, i64 %iv
  50   %val = load i64* %adr
  51   %s.next = add i64 %s, %val
  52   %inc = add i64 %iv, 1
  53   %cmp = icmp ne i64 %inc, 4
  54   br i1 %cmp, label %tail, label %exit1
  55
  56 tail:
  57   %cmp2 = icmp ne i64 %val, 0
  58   br i1 %cmp2, label %loop, label %exit2
  59
  60 exit1:
  61   ret i64 %s
  62
  63 exit2:
  64   ret i64 %s.next
  65 }
  66
  67 ; SCEV properly unrolls multi-exit loops.
  68 ;
  69 ; SCEV cannot currently unroll this loop.
  70 ; It should ideally detect a trip count of 5.
  71 ; rdar:14038809 [SCEV]: Optimize trip count computation for multi-exit loops.
  72 ; CHECK: @multiExit
  73 ; CHECKFIXME: getelementptr i32* %base, i32 10
  74 ; CHECKFIXME-NEXT: load i32*
  75 ; CHECKFIXME: br i1 false, label %l2.10, label %exit1
  76 ; CHECKFIXME: l2.10:
  77 ; CHECKFIXME-NOT: br
  78 ; CHECKFIXME: ret i32
  79 define i32 @multiExit(i32* %base) nounwind {
  80 entry:
  81   br label %l1
  82 l1:
  83   %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l2 ]
  84   %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l2 ]
  85   %inc1 = add i32 %iv1, 1
  86   %inc2 = add i32 %iv2, 1
  87   %adr = getelementptr i32* %base, i32 %iv1
  88   %val = load i32* %adr
  89   %cmp1 = icmp slt i32 %iv1, 5
  90   br i1 %cmp1, label %l2, label %exit1
  91 l2:
  92   %cmp2 = icmp slt i32 %iv2, 10
  93   br i1 %cmp2, label %l1, label %exit2
  94 exit1:
  95   ret i32 1
  96 exit2:
  97   ret i32 %val
  98 }
  99
 100
 101 ; SCEV should not unroll a multi-exit loops unless the latch block has
 102 ; a known trip count, regardless of the early exit trip counts. The
 103 ; LoopUnroll utility uses this assumption to optimize the latch
 104 ; block's branch.
 105 ;
 106 ; CHECK: @multiExitIncomplete
 107 ; CHECK: l3:
 108 ; CHECK-NOT: br
 109 ; CHECK:   br i1 %cmp3, label %l1, label %exit3
 110 define i32 @multiExitIncomplete(i32* %base) nounwind {
 111 entry:
 112   br label %l1
 113 l1:
 114   %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l3 ]
 115   %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l3 ]
 116   %inc1 = add i32 %iv1, 1
 117   %inc2 = add i32 %iv2, 1
 118   %adr = getelementptr i32* %base, i32 %iv1
 119   %val = load i32* %adr
 120   %cmp1 = icmp slt i32 %iv1, 5
 121   br i1 %cmp1, label %l2, label %exit1
 122 l2:
 123   %cmp2 = icmp slt i32 %iv2, 10
 124   br i1 %cmp2, label %l3, label %exit2
 125 l3:
 126   %cmp3 = icmp ne i32 %val, 0
 127   br i1 %cmp3, label %l1, label %exit3
 128
 129 exit1:
 130   ret i32 1
 131 exit2:
 132   ret i32 2
 133 exit3:
 134   ret i32 3
 135 }
 136
 137 ; When loop unroll merges a loop exit with one of its parent loop's
 138 ; exits, SCEV must forget its ExitNotTaken info.
 139 ;
 140 ; CHECK: @nestedUnroll
 141 ; CHECK-NOT: br i1
 142 ; CHECK: for.body87:
 143 define void @nestedUnroll() nounwind {
 144 entry:
 145   br label %for.inc
 146
 147 for.inc:
 148   br i1 false, label %for.inc, label %for.body38.preheader
 149
 150 for.body38.preheader:
 151   br label %for.body38
 152
 153 for.body38:
 154   %i.113 = phi i32 [ %inc76, %for.inc74 ], [ 0, %for.body38.preheader ]
 155   %mul48 = mul nsw i32 %i.113, 6
 156   br label %for.body43
 157
 158 for.body43:
 159   %j.011 = phi i32 [ 0, %for.body38 ], [ %inc72, %for.body43 ]
 160   %add49 = add nsw i32 %j.011, %mul48
 161   %sh_prom50 = zext i32 %add49 to i64
 162   %inc72 = add nsw i32 %j.011, 1
 163   br i1 false, label %for.body43, label %for.inc74
 164
 165 for.inc74:
 166   %inc76 = add nsw i32 %i.113, 1
 167   br i1 false, label %for.body38, label %for.body87.preheader
 168
 169 for.body87.preheader:
 170   br label %for.body87
 171
 172 for.body87:
 173   br label %for.body87
 174 }
 175
 176 ; PR16130: clang produces incorrect code with loop/expression at -O2
 177 ; rdar:14036816 loop-unroll makes assumptions about undefined behavior
 178 ;
 179 ; The loop latch is assumed to exit after the first iteration because
 180 ; of the induction variable's NSW flag. However, the loop latch's
 181 ; equality test is skipped and the loop exits after the second
 182 ; iteration via the early exit. So loop unrolling cannot assume that
 183 ; the loop latch's exit count of zero is an upper bound on the number
 184 ; of iterations.
 185 ;
 186 ; CHECK: @nsw_latch
 187 ; CHECK: for.body:
 188 ; CHECK: %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ]
 189 ; CHECK: return:
 190 ; CHECK: %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ]
 191 define void @nsw_latch(i32* %a) nounwind {
 192 entry:
 193   br label %for.body
 194
 195 for.body:                                         ; preds = %for.cond, %entry
 196   %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ]
 197   %tobool = icmp eq i32 %b.03, 0
 198   %add = add nsw i32 %b.03, 8
 199   br i1 %tobool, label %for.cond, label %return
 200
 201 for.cond:                                         ; preds = %for.body
 202   %cmp = icmp eq i32 %add, 13
 203   br i1 %cmp, label %return, label %for.body
 204
 205 return:                                           ; preds = %for.body, %for.cond
 206   %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ]
 207   %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ]
 208   store i32 %b.03.lcssa, i32* %a, align 4
 209   ret void
 210 }