llvm/test/Transforms/LoopStrengthReduce/X86/bin_power.ll

   1 ; RUN: opt < %s -scalar-evolution-huge-expr-threshold=1000000 -loop-reduce -S | FileCheck %s
   2
   3 target datalayout = "e-m:e-i32:64-f80:128-n8:16:32:64-S128"
   4 target triple = "x86_64-unknown-linux-gnu"
   5
   6 ; Show that the b^2 is expanded correctly.
   7 define i32 @test_01(i32 %a) {
   8 ; CHECK-LABEL: @test_01
   9 ; CHECK:       entry:
  10 ; CHECK-NEXT:  br label %loop
  11 ; CHECK:       loop:
  12 ; CHECK-NEXT:  [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
  13 ; CHECK-NEXT:  [[IV_INC]] = add nsw i32 [[IV]], -1
  14 ; CHECK-NEXT:  [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
  15 ; CHECK-NEXT:  br i1 [[EXITCOND]], label %exit, label %loop
  16 ; CHECK:       exit:
  17 ; CHECK-NEXT:  [[B:[^ ]+]] = add i32 %a, 1
  18 ; CHECK-NEXT:  [[B2:[^ ]+]] = mul i32 [[B]], [[B]]
  19 ; CHECK-NEXT:  [[R1:[^ ]+]] = add i32 [[B2]], -1
  20 ; CHECK-NEXT:  [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]
  21 ; CHECK-NEXT:  ret i32 [[R2]]
  22
  23 entry:
  24   br label %loop
  25
  26 loop:                                           ; preds = %loop, %entry
  27   %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
  28   %b = add i32 %a, 1
  29   %b.pow.2 = mul i32 %b, %b
  30   %result = add i32 %b.pow.2, %indvars.iv
  31   %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
  32   %exitcond = icmp eq i32 %indvars.iv.next, 80
  33   br i1 %exitcond, label %exit, label %loop
  34
  35 exit:                                             ; preds = %loop
  36   ret i32 %result
  37 }
  38
  39 ; Show that b^8 is expanded correctly.
  40 define i32 @test_02(i32 %a) {
  41 ; CHECK-LABEL: @test_02
  42 ; CHECK:       entry:
  43 ; CHECK-NEXT:  br label %loop
  44 ; CHECK:       loop:
  45 ; CHECK-NEXT:  [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
  46 ; CHECK-NEXT:  [[IV_INC]] = add nsw i32 [[IV]], -1
  47 ; CHECK-NEXT:  [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
  48 ; CHECK-NEXT:  br i1 [[EXITCOND]], label %exit, label %loop
  49 ; CHECK:       exit:
  50 ; CHECK-NEXT:  [[B:[^ ]+]] = add i32 %a, 1
  51 ; CHECK-NEXT:  [[B2:[^ ]+]] = mul i32 [[B]], [[B]]
  52 ; CHECK-NEXT:  [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]
  53 ; CHECK-NEXT:  [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]
  54 ; CHECK-NEXT:  [[R1:[^ ]+]] = add i32 [[B8]], -1
  55 ; CHECK-NEXT:  [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]
  56 ; CHECK-NEXT:  ret i32 [[R2]]
  57 entry:
  58   br label %loop
  59
  60 loop:                                           ; preds = %loop, %entry
  61   %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
  62   %b = add i32 %a, 1
  63   %b.pow.2 = mul i32 %b, %b
  64   %b.pow.4 = mul i32 %b.pow.2, %b.pow.2
  65   %b.pow.8 = mul i32 %b.pow.4, %b.pow.4
  66   %result = add i32 %b.pow.8, %indvars.iv
  67   %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
  68   %exitcond = icmp eq i32 %indvars.iv.next, 80
  69   br i1 %exitcond, label %exit, label %loop
  70
  71 exit:                                             ; preds = %loop
  72   ret i32 %result
  73 }
  74
  75 ; Show that b^27 (27 = 1 + 2 + 8 + 16) is expanded correctly.
  76 define i32 @test_03(i32 %a) {
  77 ; CHECK-LABEL: @test_03
  78 ; CHECK:       entry:
  79 ; CHECK-NEXT:  br label %loop
  80 ; CHECK:       loop:
  81 ; CHECK-NEXT:  [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
  82 ; CHECK-NEXT:  [[IV_INC]] = add nsw i32 [[IV]], -1
  83 ; CHECK-NEXT:  [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
  84 ; CHECK-NEXT:  br i1 [[EXITCOND]], label %exit, label %loop
  85 ; CHECK:       exit:
  86 ; CHECK-NEXT:  [[B:[^ ]+]] = add i32 %a, 1
  87 ; CHECK-NEXT:  [[B2:[^ ]+]] = mul i32 [[B]], [[B]]
  88 ; CHECK-NEXT:  [[B3:[^ ]+]] = mul i32 [[B]], [[B2]]
  89 ; CHECK-NEXT:  [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]
  90 ; CHECK-NEXT:  [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]
  91 ; CHECK-NEXT:  [[B11:[^ ]+]] = mul i32 [[B3]], [[B8]]
  92 ; CHECK-NEXT:  [[B16:[^ ]+]] = mul i32 [[B8]], [[B8]]
  93 ; CHECK-NEXT:  [[B27:[^ ]+]] = mul i32 [[B11]], [[B16]]
  94 ; CHECK-NEXT:  [[R1:[^ ]+]] = add i32 [[B27]], -1
  95 ; CHECK-NEXT:  [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]
  96 ; CHECK-NEXT:  ret i32 [[R2]]
  97 entry:
  98   br label %loop
  99
 100 loop:                                           ; preds = %loop, %entry
 101   %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
 102   %b = add i32 %a, 1
 103   %b.pow.2 = mul i32 %b, %b
 104   %b.pow.4 = mul i32 %b.pow.2, %b.pow.2
 105   %b.pow.8 = mul i32 %b.pow.4, %b.pow.4
 106   %b.pow.16 = mul i32 %b.pow.8, %b.pow.8
 107   %b.pow.24 = mul i32 %b.pow.16, %b.pow.8
 108   %b.pow.25 = mul i32 %b.pow.24, %b
 109   %b.pow.26 = mul i32 %b.pow.25, %b
 110   %b.pow.27 = mul i32 %b.pow.26, %b
 111   %result = add i32 %b.pow.27, %indvars.iv
 112   %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
 113   %exitcond = icmp eq i32 %indvars.iv.next, 80
 114   br i1 %exitcond, label %exit, label %loop
 115
 116 exit:                                             ; preds = %loop
 117   ret i32 %result
 118 }
 119
 120 ; Show how linear calculation of b^16 is turned into logarithmic.
 121 define i32 @test_04(i32 %a) {
 122 ; CHECK-LABEL: @test_04
 123 ; CHECK:       entry:
 124 ; CHECK-NEXT:  br label %loop
 125 ; CHECK:       loop:
 126 ; CHECK-NEXT:  [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
 127 ; CHECK-NEXT:  [[IV_INC]] = add nsw i32 [[IV]], -1
 128 ; CHECK-NEXT:  [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
 129 ; CHECK-NEXT:  br i1 [[EXITCOND]], label %exit, label %loop
 130 ; CHECK:       exit:
 131 ; CHECK-NEXT:  [[B:[^ ]+]] = add i32 %a, 1
 132 ; CHECK-NEXT:  [[B2:[^ ]+]] = mul i32 [[B]], [[B]]
 133 ; CHECK-NEXT:  [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]
 134 ; CHECK-NEXT:  [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]
 135 ; CHECK-NEXT:  [[B16:[^ ]+]] = mul i32 [[B8]], [[B8]]
 136 ; CHECK-NEXT:  [[R1:[^ ]+]] = add i32 [[B16]], -1
 137 ; CHECK-NEXT:  [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]
 138 ; CHECK-NEXT:  ret i32 [[R2]]
 139 entry:
 140   br label %loop
 141
 142 loop:                                           ; preds = %loop, %entry
 143   %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
 144   %b = add i32 %a, 1
 145   %b.pow.2 = mul i32 %b, %b
 146   %b.pow.3 = mul i32 %b.pow.2, %b
 147   %b.pow.4 = mul i32 %b.pow.3, %b
 148   %b.pow.5 = mul i32 %b.pow.4, %b
 149   %b.pow.6 = mul i32 %b.pow.5, %b
 150   %b.pow.7 = mul i32 %b.pow.6, %b
 151   %b.pow.8 = mul i32 %b.pow.7, %b
 152   %b.pow.9 = mul i32 %b.pow.8, %b
 153   %b.pow.10 = mul i32 %b.pow.9, %b
 154   %b.pow.11 = mul i32 %b.pow.10, %b
 155   %b.pow.12 = mul i32 %b.pow.11, %b
 156   %b.pow.13 = mul i32 %b.pow.12, %b
 157   %b.pow.14 = mul i32 %b.pow.13, %b
 158   %b.pow.15 = mul i32 %b.pow.14, %b
 159   %b.pow.16 = mul i32 %b.pow.15, %b
 160   %result = add i32 %b.pow.16, %indvars.iv
 161   %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
 162   %exitcond = icmp eq i32 %indvars.iv.next, 80
 163   br i1 %exitcond, label %exit, label %loop
 164
 165 exit:                                             ; preds = %loop
 166   ret i32 %result
 167 }
 168
 169 ; The output here is reasonably big, we just check that the amount of expanded
 170 ; instructions is sane.
 171 define i32 @test_05(i32 %a) {
 172 ; CHECK-LABEL: @test_05
 173 ; CHECK:       entry:
 174 ; CHECK-NEXT:  br label %loop
 175 ; CHECK:       loop:
 176 ; CHECK-NEXT:  [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
 177 ; CHECK-NEXT:  [[IV_INC]] = add nsw i32 [[IV]], -1
 178 ; CHECK-NEXT:  [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
 179 ; CHECK-NEXT:  br i1 [[EXITCOND]], label %exit, label %loop
 180 ; CHECK:       exit:
 181 ; CHECK:       %100
 182 ; CHECK-NOT:   %150
 183
 184 entry:
 185   br label %loop
 186
 187 loop:                                           ; preds = %loop, %entry
 188   %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
 189   %tmp3 = add i32 %a, 1
 190   %tmp4 = mul i32 %tmp3, %tmp3
 191   %tmp5 = mul i32 %tmp4, %tmp4
 192   %tmp6 = mul i32 %tmp5, %tmp5
 193   %tmp7 = mul i32 %tmp6, %tmp6
 194   %tmp8 = mul i32 %tmp7, %tmp7
 195   %tmp9 = mul i32 %tmp8, %tmp8
 196   %tmp10 = mul i32 %tmp9, %tmp9
 197   %tmp11 = mul i32 %tmp10, %tmp10
 198   %tmp12 = mul i32 %tmp11, %tmp11
 199   %tmp13 = mul i32 %tmp12, %tmp12
 200   %tmp14 = mul i32 %tmp13, %tmp13
 201   %tmp15 = mul i32 %tmp14, %tmp14
 202   %tmp16 = mul i32 %tmp15, %tmp15
 203   %tmp17 = mul i32 %tmp16, %tmp16
 204   %tmp18 = mul i32 %tmp17, %tmp17
 205   %tmp19 = mul i32 %tmp18, %tmp18
 206   %tmp20 = mul i32 %tmp19, %tmp19
 207   %tmp22 = add i32 %tmp20, %indvars.iv
 208   %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
 209   %exitcond = icmp eq i32 %indvars.iv.next, 80
 210   br i1 %exitcond, label %exit, label %loop
 211
 212 exit:                                             ; preds = %loop
 213   ret i32 %tmp22
 214 }
 215
 216 ; Show that the transformation works even if the calculation involves different
 217 ; values inside.
 218 define i32 @test_06(i32 %a, i32 %c) {
 219 ; CHECK-LABEL: @test_06
 220 ; CHECK:       entry:
 221 ; CHECK-NEXT:  br label %loop
 222 ; CHECK:       loop:
 223 ; CHECK-NEXT:  [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
 224 ; CHECK-NEXT:  [[IV_INC]] = add nsw i32 [[IV]], -1
 225 ; CHECK-NEXT:  [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
 226 ; CHECK-NEXT:  br i1 [[EXITCOND]], label %exit, label %loop
 227 ; CHECK:       exit:
 228 ; CHECK:       [[B:[^ ]+]] = add i32 %a, 1
 229 ; CHECK-NEXT:  [[B2:[^ ]+]] = mul i32 [[B]], [[B]]
 230 ; CHECK-NEXT:  [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]
 231 ; CHECK-NEXT:  [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]
 232 ; CHECK-NEXT:  [[B16:[^ ]+]] = mul i32 [[B8]], [[B8]]
 233 entry:
 234   br label %loop
 235
 236 loop:                                           ; preds = %loop, %entry
 237   %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
 238   %b = add i32 %a, 1
 239   %b.pow.2.tmp = mul i32 %b, %b
 240   %b.pow.2 = mul i32 %b.pow.2.tmp, %c
 241   %b.pow.3 = mul i32 %b.pow.2, %b
 242   %b.pow.4 = mul i32 %b.pow.3, %b
 243   %b.pow.5 = mul i32 %b.pow.4, %b
 244   %b.pow.6.tmp = mul i32 %b.pow.5, %b
 245   %b.pow.6 = mul i32 %b.pow.6.tmp, %c
 246   %b.pow.7 = mul i32 %b.pow.6, %b
 247   %b.pow.8 = mul i32 %b.pow.7, %b
 248   %b.pow.9 = mul i32 %b.pow.8, %b
 249   %b.pow.10 = mul i32 %b.pow.9, %b
 250   %b.pow.11 = mul i32 %b.pow.10, %b
 251   %b.pow.12.tmp = mul i32 %b.pow.11, %b
 252   %b.pow.12 = mul i32 %c, %b.pow.12.tmp
 253   %b.pow.13 = mul i32 %b.pow.12, %b
 254   %b.pow.14 = mul i32 %b.pow.13, %b
 255   %b.pow.15 = mul i32 %b.pow.14, %b
 256   %b.pow.16 = mul i32 %b.pow.15, %b
 257   %result = add i32 %b.pow.16, %indvars.iv
 258   %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
 259   %exitcond = icmp eq i32 %indvars.iv.next, 80
 260   br i1 %exitcond, label %exit, label %loop
 261
 262 exit:                                             ; preds = %loop
 263   ret i32 %result
 264 }