test/Transforms/IndVarSimplify/exit_value_tests.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -indvars -loop-deletion -simplifycfg -S | FileCheck %s
   3
   4 ; Test that we can evaluate the exit values of various expression types.  Since
   5 ; these loops all have predictable exit values we can replace the use outside
   6 ; of the loop with a closed-form computation.
   7
   8 define i32 @polynomial_constant() {
   9 ; <label>:0
  10 ; CHECK-LABEL: @polynomial_constant(
  11 ; CHECK-NEXT:  Out:
  12 ; CHECK-NEXT:    ret i32 500500
  13 ;
  14   br label %Loop
  15
  16 Loop:           ; preds = %Loop, %0
  17   %A1 = phi i32 [ 0, %0 ], [ %A2, %Loop ]               ; <i32> [#uses=3]
  18   %B1 = phi i32 [ 0, %0 ], [ %B2, %Loop ]               ; <i32> [#uses=1]
  19   %A2 = add i32 %A1, 1          ; <i32> [#uses=1]
  20   %B2 = add i32 %B1, %A1                ; <i32> [#uses=2]
  21   %C = icmp eq i32 %A1, 1000            ; <i1> [#uses=1]
  22   br i1 %C, label %Out, label %Loop
  23
  24 Out:            ; preds = %Loop
  25   ret i32 %B2
  26 }
  27
  28 define i32 @NSquare(i32 %N) {
  29 ; <label>:0
  30 ; CHECK-LABEL: @NSquare(
  31 ; CHECK-NEXT:  Out:
  32 ; CHECK-NEXT:    [[Y:%.*]] = mul i32 [[N:%.*]], [[N]]
  33 ; CHECK-NEXT:    ret i32 [[Y]]
  34 ;
  35   br label %Loop
  36
  37 Loop:           ; preds = %Loop, %0
  38   %X = phi i32 [ 0, %0 ], [ %X2, %Loop ]                ; <i32> [#uses=4]
  39   %X2 = add i32 %X, 1           ; <i32> [#uses=1]
  40   %c = icmp eq i32 %X, %N               ; <i1> [#uses=1]
  41   br i1 %c, label %Out, label %Loop
  42
  43 Out:            ; preds = %Loop
  44   %Y = mul i32 %X, %X           ; <i32> [#uses=1]
  45   ret i32 %Y
  46 }
  47
  48 define i32 @NSquareOver2(i32 %N) {
  49 ; <label>:0
  50 ; CHECK-LABEL: @NSquareOver2(
  51 ; CHECK-NEXT:  Out:
  52 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[N:%.*]] to i33
  53 ; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[N]], -1
  54 ; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[TMP1]] to i33
  55 ; CHECK-NEXT:    [[TMP3:%.*]] = mul i33 [[TMP0]], [[TMP2]]
  56 ; CHECK-NEXT:    [[TMP4:%.*]] = lshr i33 [[TMP3]], 1
  57 ; CHECK-NEXT:    [[TMP5:%.*]] = trunc i33 [[TMP4]] to i32
  58 ; CHECK-NEXT:    [[TMP6:%.*]] = add i32 [[N]], [[TMP5]]
  59 ; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[TMP6]], 15
  60 ; CHECK-NEXT:    ret i32 [[TMP7]]
  61 ;
  62   br label %Loop
  63
  64 Loop:           ; preds = %Loop, %0
  65   %X = phi i32 [ 0, %0 ], [ %X2, %Loop ]                ; <i32> [#uses=3]
  66   %Y = phi i32 [ 15, %0 ], [ %Y2, %Loop ]               ; <i32> [#uses=1]
  67   %Y2 = add i32 %Y, %X          ; <i32> [#uses=2]
  68   %X2 = add i32 %X, 1           ; <i32> [#uses=1]
  69   %c = icmp eq i32 %X, %N               ; <i1> [#uses=1]
  70   br i1 %c, label %Out, label %Loop
  71
  72 Out:            ; preds = %Loop
  73   ret i32 %Y2
  74 }
  75
  76 define i32 @strength_reduced() {
  77 ; <label>:0
  78 ; CHECK-LABEL: @strength_reduced(
  79 ; CHECK-NEXT:  Out:
  80 ; CHECK-NEXT:    ret i32 500500
  81 ;
  82   br label %Loop
  83
  84 Loop:           ; preds = %Loop, %0
  85   %A1 = phi i32 [ 0, %0 ], [ %A2, %Loop ]               ; <i32> [#uses=3]
  86   %B1 = phi i32 [ 0, %0 ], [ %B2, %Loop ]               ; <i32> [#uses=1]
  87   %A2 = add i32 %A1, 1          ; <i32> [#uses=1]
  88   %B2 = add i32 %B1, %A1                ; <i32> [#uses=2]
  89   %C = icmp eq i32 %A1, 1000            ; <i1> [#uses=1]
  90   br i1 %C, label %Out, label %Loop
  91
  92 Out:            ; preds = %Loop
  93   ret i32 %B2
  94 }
  95
  96 define i32 @chrec_equals() {
  97 ; CHECK-LABEL: @chrec_equals(
  98 ; CHECK-NEXT:  entry:
  99 ; CHECK-NEXT:    ret i32 101
 100 ;
 101 entry:
 102   br label %no_exit
 103
 104 no_exit:                ; preds = %no_exit, %entry
 105   %i0 = phi i32 [ 0, %entry ], [ %i1, %no_exit ]                ; <i32> [#uses=3]
 106   %ISq = mul i32 %i0, %i0               ; <i32> [#uses=1]
 107   %i1 = add i32 %i0, 1          ; <i32> [#uses=2]
 108   %tmp.1 = icmp ne i32 %ISq, 10000              ; <i1> [#uses=1]
 109   br i1 %tmp.1, label %no_exit, label %loopexit
 110
 111 loopexit:               ; preds = %no_exit
 112   ret i32 %i1
 113 }
 114
 115 define i16 @cast_chrec_test() {
 116 ; <label>:0
 117 ; CHECK-LABEL: @cast_chrec_test(
 118 ; CHECK-NEXT:  Out:
 119 ; CHECK-NEXT:    ret i16 1000
 120 ;
 121   br label %Loop
 122
 123 Loop:           ; preds = %Loop, %0
 124   %A1 = phi i32 [ 0, %0 ], [ %A2, %Loop ]               ; <i32> [#uses=2]
 125   %B1 = trunc i32 %A1 to i16            ; <i16> [#uses=2]
 126   %A2 = add i32 %A1, 1          ; <i32> [#uses=1]
 127   %C = icmp eq i16 %B1, 1000            ; <i1> [#uses=1]
 128   br i1 %C, label %Out, label %Loop
 129
 130 Out:            ; preds = %Loop
 131   ret i16 %B1
 132 }
 133
 134 define i32 @linear_div_fold() {
 135 ; CHECK-LABEL: @linear_div_fold(
 136 ; CHECK-NEXT:  entry:
 137 ; CHECK-NEXT:    ret i32 34
 138 ;
 139 entry:
 140   br label %loop
 141
 142 loop:           ; preds = %loop, %entry
 143   %i = phi i32 [ 4, %entry ], [ %i.next, %loop ]                ; <i32> [#uses=3]
 144   %i.next = add i32 %i, 8               ; <i32> [#uses=1]
 145   %RV = udiv i32 %i, 2          ; <i32> [#uses=1]
 146   %c = icmp ne i32 %i, 68               ; <i1> [#uses=1]
 147   br i1 %c, label %loop, label %loopexit
 148
 149 loopexit:               ; preds = %loop
 150   ret i32 %RV
 151 }
 152
 153 define i32 @unroll_phi_select_constant_nonzero(i32 %arg1, i32 %arg2) {
 154 ; CHECK-LABEL: @unroll_phi_select_constant_nonzero(
 155 ; CHECK-NEXT:  entry:
 156 ; CHECK-NEXT:    ret i32 [[ARG2:%.*]]
 157 ;
 158 entry:
 159   br label %loop
 160
 161 loop:
 162   %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 163   %selector = phi i32 [%arg1, %entry], [%arg2, %loop]
 164   %i.next = add nsw nuw i32 %i, 1
 165   %c = icmp ult i32 %i, 4
 166   br i1 %c, label %loop, label %loopexit
 167
 168 loopexit:
 169   ret i32 %selector
 170 }
 171
 172 declare i32 @f()
 173
 174 ; After LCSSA formation, there's no LCSSA phi for %f since it isn't directly
 175 ; used outside the loop, and thus we can't directly replace %selector w/ %f.
 176 define i32 @neg_unroll_phi_select_constant_nonzero(i32 %arg) {
 177 ; CHECK-LABEL: @neg_unroll_phi_select_constant_nonzero(
 178 ; CHECK-NEXT:  entry:
 179 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 180 ; CHECK:       loop:
 181 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
 182 ; CHECK-NEXT:    [[SELECTOR:%.*]] = phi i32 [ [[ARG:%.*]], [[ENTRY]] ], [ [[F:%.*]], [[LOOP]] ]
 183 ; CHECK-NEXT:    [[F]] = call i32 @f()
 184 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
 185 ; CHECK-NEXT:    [[C:%.*]] = icmp ult i32 [[I]], 4
 186 ; CHECK-NEXT:    br i1 [[C]], label [[LOOP]], label [[LOOPEXIT:%.*]]
 187 ; CHECK:       loopexit:
 188 ; CHECK-NEXT:    [[SELECTOR_LCSSA:%.*]] = phi i32 [ [[SELECTOR]], [[LOOP]] ]
 189 ; CHECK-NEXT:    ret i32 [[SELECTOR_LCSSA]]
 190 ;
 191 entry:
 192   br label %loop
 193
 194 loop:
 195   %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 196   %selector = phi i32 [%arg, %entry], [%f, %loop]
 197   %f = call i32 @f()
 198   %i.next = add nsw nuw i32 %i, 1
 199   %c = icmp ult i32 %i, 4
 200   br i1 %c, label %loop, label %loopexit
 201
 202 loopexit:
 203   ret i32 %selector
 204 }
 205
 206
 207 define i32 @unroll_phi_select_constant_zero(i32 %arg1, i32 %arg2) {
 208 ; CHECK-LABEL: @unroll_phi_select_constant_zero(
 209 ; CHECK-NEXT:  entry:
 210 ; CHECK-NEXT:    ret i32 [[ARG1:%.*]]
 211 ;
 212 entry:
 213   br label %loop
 214
 215 loop:
 216   %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 217   %selector = phi i32 [%arg1, %entry], [%arg2, %loop]
 218   %i.next = add i32 %i, 1
 219   %c = icmp ne i32 %i, 0
 220   br i1 %c, label %loop, label %loopexit
 221
 222 loopexit:
 223   ret i32 %selector
 224 }
 225
 226 define i32 @unroll_phi_select(i32 %arg1, i32 %arg2, i16 %len) {
 227 ; CHECK-LABEL: @unroll_phi_select(
 228 ; CHECK-NEXT:  entry:
 229 ; CHECK-NEXT:    [[LENGTH:%.*]] = zext i16 [[LEN:%.*]] to i32
 230 ; CHECK-NEXT:    ret i32 [[ARG2:%.*]]
 231 ;
 232 entry:
 233   %length = zext i16 %len to i32
 234   br label %loop
 235
 236 loop:
 237   %i = phi i32 [ -1, %entry ], [ %i.next, %loop ]
 238   %selector = phi i32 [%arg1, %entry], [%arg2, %loop]
 239   %i.next = add nsw i32 %i, 1
 240   %c = icmp slt i32 %i, %length
 241   br i1 %c, label %loop, label %loopexit
 242
 243 loopexit:
 244   ret i32 %selector
 245 }
 246