llvm/test/Transforms/InstCombine/overflow-mul.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -S -passes=instcombine < %s | FileCheck %s
   3
   4 ; The last test needs this weird datalayout.
   5 target datalayout = "i32:8:8"
   6 ; Without it, InstCombine will align the pointed on 4 Bytes
   7 ; The KnownBitsZero that result from the alignment allows to
   8 ; turn:
   9 ;    and i32 %mul, 255
  10 ; to:
  11 ;    and i32 %mul, 252
  12 ; The mask is no longer in the form 2^n-1  and this prevents the transformation.
  13
  14 declare void @use.i64(i64)
  15
  16 ; return mul(zext x, zext y) > MAX
  17 define i32 @pr4917_1(i32 %x, i32 %y) nounwind {
  18 ; CHECK-LABEL: @pr4917_1(
  19 ; CHECK-NEXT:  entry:
  20 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
  21 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
  22 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
  23 ; CHECK-NEXT:    ret i32 [[RETVAL]]
  24 ;
  25 entry:
  26   %l = zext i32 %x to i64
  27   %r = zext i32 %y to i64
  28   %mul64 = mul i64 %l, %r
  29   %overflow = icmp ugt i64 %mul64, 4294967295
  30   %retval = zext i1 %overflow to i32
  31   ret i32 %retval
  32 }
  33
  34 ; return mul(zext x, zext y) >= MAX+1
  35 define i32 @pr4917_1a(i32 %x, i32 %y) nounwind {
  36 ; CHECK-LABEL: @pr4917_1a(
  37 ; CHECK-NEXT:  entry:
  38 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
  39 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
  40 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
  41 ; CHECK-NEXT:    ret i32 [[RETVAL]]
  42 ;
  43 entry:
  44   %l = zext i32 %x to i64
  45   %r = zext i32 %y to i64
  46   %mul64 = mul i64 %l, %r
  47   %overflow = icmp uge i64 %mul64, 4294967296
  48   %retval = zext i1 %overflow to i32
  49   ret i32 %retval
  50 }
  51
  52 ; mul(zext x, zext y) > MAX
  53 ; mul(x, y) is used
  54 define i32 @pr4917_2(i32 %x, i32 %y) nounwind {
  55 ; CHECK-LABEL: @pr4917_2(
  56 ; CHECK-NEXT:  entry:
  57 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
  58 ; CHECK-NEXT:    [[UMUL_VALUE:%.*]] = extractvalue { i32, i1 } [[UMUL]], 0
  59 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
  60 ; CHECK-NEXT:    [[RETVAL:%.*]] = select i1 [[OVERFLOW]], i32 [[UMUL_VALUE]], i32 111
  61 ; CHECK-NEXT:    ret i32 [[RETVAL]]
  62 ;
  63 entry:
  64   %l = zext i32 %x to i64
  65   %r = zext i32 %y to i64
  66   %mul64 = mul i64 %l, %r
  67   %overflow = icmp ugt i64 %mul64, 4294967295
  68   %mul32 = trunc i64 %mul64 to i32
  69   %retval = select i1 %overflow, i32 %mul32, i32 111
  70   ret i32 %retval
  71 }
  72
  73 ; return mul(zext x, zext y) > MAX
  74 ; mul is used in non-truncate
  75 define i64 @pr4917_3(i32 %x, i32 %y) nounwind {
  76 ; CHECK-LABEL: @pr4917_3(
  77 ; CHECK-NEXT:  entry:
  78 ; CHECK-NEXT:    [[L:%.*]] = zext i32 [[X:%.*]] to i64
  79 ; CHECK-NEXT:    [[R:%.*]] = zext i32 [[Y:%.*]] to i64
  80 ; CHECK-NEXT:    [[MUL64:%.*]] = mul nuw i64 [[L]], [[R]]
  81 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i64 [[MUL64]], 4294967295
  82 ; CHECK-NEXT:    [[RETVAL:%.*]] = select i1 [[OVERFLOW]], i64 [[MUL64]], i64 111
  83 ; CHECK-NEXT:    ret i64 [[RETVAL]]
  84 ;
  85 entry:
  86   %l = zext i32 %x to i64
  87   %r = zext i32 %y to i64
  88   %mul64 = mul i64 %l, %r
  89   %overflow = icmp ugt i64 %mul64, 4294967295
  90   %retval = select i1 %overflow, i64 %mul64, i64 111
  91   ret i64 %retval
  92 }
  93
  94 ; return mul(zext x, zext y) <= MAX
  95 define i32 @pr4917_4(i32 %x, i32 %y) nounwind {
  96 ; CHECK-LABEL: @pr4917_4(
  97 ; CHECK-NEXT:  entry:
  98 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
  99 ; CHECK-NEXT:    [[TMP0:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
 100 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = xor i1 [[TMP0]], true
 101 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
 102 ; CHECK-NEXT:    ret i32 [[RETVAL]]
 103 ;
 104 entry:
 105   %l = zext i32 %x to i64
 106   %r = zext i32 %y to i64
 107   %mul64 = mul i64 %l, %r
 108   %overflow = icmp ule i64 %mul64, 4294967295
 109   %retval = zext i1 %overflow to i32
 110   ret i32 %retval
 111 }
 112
 113 ; return mul(zext x, zext y) < MAX+1
 114 define i32 @pr4917_4a(i32 %x, i32 %y) nounwind {
 115 ; CHECK-LABEL: @pr4917_4a(
 116 ; CHECK-NEXT:  entry:
 117 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
 118 ; CHECK-NEXT:    [[TMP0:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
 119 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = xor i1 [[TMP0]], true
 120 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
 121 ; CHECK-NEXT:    ret i32 [[RETVAL]]
 122 ;
 123 entry:
 124   %l = zext i32 %x to i64
 125   %r = zext i32 %y to i64
 126   %mul64 = mul i64 %l, %r
 127   %overflow = icmp ult i64 %mul64, 4294967296
 128   %retval = zext i1 %overflow to i32
 129   ret i32 %retval
 130 }
 131
 132 ; operands of mul are of different size
 133 define i32 @pr4917_5(i32 %x, i8 %y) nounwind {
 134 ; CHECK-LABEL: @pr4917_5(
 135 ; CHECK-NEXT:  entry:
 136 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i8 [[Y:%.*]] to i32
 137 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[TMP0]])
 138 ; CHECK-NEXT:    [[UMUL_VALUE:%.*]] = extractvalue { i32, i1 } [[UMUL]], 0
 139 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
 140 ; CHECK-NEXT:    [[RETVAL:%.*]] = select i1 [[OVERFLOW]], i32 [[UMUL_VALUE]], i32 111
 141 ; CHECK-NEXT:    ret i32 [[RETVAL]]
 142 ;
 143 entry:
 144   %l = zext i32 %x to i64
 145   %r = zext i8 %y to i64
 146   %mul64 = mul i64 %l, %r
 147   %overflow = icmp ugt i64 %mul64, 4294967295
 148   %mul32 = trunc i64 %mul64 to i32
 149   %retval = select i1 %overflow, i32 %mul32, i32 111
 150   ret i32 %retval
 151 }
 152
 153 ; mul(zext x, zext y) != zext trunc mul
 154 define i32 @pr4918_1(i32 %x, i32 %y) nounwind {
 155 ; CHECK-LABEL: @pr4918_1(
 156 ; CHECK-NEXT:  entry:
 157 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
 158 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
 159 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
 160 ; CHECK-NEXT:    ret i32 [[RETVAL]]
 161 ;
 162 entry:
 163   %l = zext i32 %x to i64
 164   %r = zext i32 %y to i64
 165   %mul64 = mul i64 %l, %r
 166   %part32 = trunc i64 %mul64 to i32
 167   %part64 = zext i32 %part32 to i64
 168   %overflow = icmp ne i64 %mul64, %part64
 169   %retval = zext i1 %overflow to i32
 170   ret i32 %retval
 171 }
 172
 173 ; mul(zext x, zext y) == zext trunc mul
 174 define i32 @pr4918_2(i32 %x, i32 %y) nounwind {
 175 ; CHECK-LABEL: @pr4918_2(
 176 ; CHECK-NEXT:  entry:
 177 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
 178 ; CHECK-NEXT:    [[TMP0:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
 179 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = xor i1 [[TMP0]], true
 180 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
 181 ; CHECK-NEXT:    ret i32 [[RETVAL]]
 182 ;
 183 entry:
 184   %l = zext i32 %x to i64
 185   %r = zext i32 %y to i64
 186   %mul64 = mul i64 %l, %r
 187   %part32 = trunc i64 %mul64 to i32
 188   %part64 = zext i32 %part32 to i64
 189   %overflow = icmp eq i64 %mul64, %part64
 190   %retval = zext i1 %overflow to i32
 191   ret i32 %retval
 192 }
 193
 194 ; zext trunc mul != mul(zext x, zext y)
 195 define i32 @pr4918_3(i32 %x, i32 %y) nounwind {
 196 ; CHECK-LABEL: @pr4918_3(
 197 ; CHECK-NEXT:  entry:
 198 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
 199 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
 200 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
 201 ; CHECK-NEXT:    ret i32 [[RETVAL]]
 202 ;
 203 entry:
 204   %l = zext i32 %x to i64
 205   %r = zext i32 %y to i64
 206   %mul64 = mul i64 %l, %r
 207   %part32 = trunc i64 %mul64 to i32
 208   %part64 = zext i32 %part32 to i64
 209   %overflow = icmp ne i64 %part64, %mul64
 210   %retval = zext i1 %overflow to i32
 211   ret i32 %retval
 212 }
 213
 214 define <4 x i32> @pr20113(<4 x i16> %a, <4 x i16> %b) {
 215 ; CHECK-LABEL: @pr20113(
 216 ; CHECK-NEXT:    [[VMOVL_I_I726:%.*]] = zext <4 x i16> [[A:%.*]] to <4 x i32>
 217 ; CHECK-NEXT:    [[VMOVL_I_I712:%.*]] = zext <4 x i16> [[B:%.*]] to <4 x i32>
 218 ; CHECK-NEXT:    [[MUL_I703:%.*]] = mul nuw <4 x i32> [[VMOVL_I_I712]], [[VMOVL_I_I726]]
 219 ; CHECK-NEXT:    [[TMP:%.*]] = icmp sgt <4 x i32> [[MUL_I703]], splat (i32 -1)
 220 ; CHECK-NEXT:    [[VCGEZ_I:%.*]] = sext <4 x i1> [[TMP]] to <4 x i32>
 221 ; CHECK-NEXT:    ret <4 x i32> [[VCGEZ_I]]
 222 ;
 223   %vmovl.i.i726 = zext <4 x i16> %a to <4 x i32>
 224   %vmovl.i.i712 = zext <4 x i16> %b to <4 x i32>
 225   %mul.i703 = mul <4 x i32> %vmovl.i.i712, %vmovl.i.i726
 226   %tmp = icmp sge <4 x i32> %mul.i703, zeroinitializer
 227   %vcgez.i = sext <4 x i1> %tmp to <4 x i32>
 228   ret <4 x i32> %vcgez.i
 229 }
 230
 231
 232 @pr21445_data = external global i32
 233 define i1 @pr21445(i8 %a) {
 234 ; CHECK-LABEL: @pr21445(
 235 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[A:%.*]], i8 ptrtoint (ptr @pr21445_data to i8))
 236 ; CHECK-NEXT:    [[CMP:%.*]] = extractvalue { i8, i1 } [[UMUL]], 1
 237 ; CHECK-NEXT:    ret i1 [[CMP]]
 238 ;
 239   %ext = zext i8 %a to i32
 240   %ext2 = zext i8 ptrtoint (ptr @pr21445_data to i8) to i32
 241   %mul = mul i32 %ext, %ext2
 242   %and = and i32 %mul, 255
 243   %cmp = icmp ne i32 %mul, %and
 244   ret i1 %cmp
 245 }
 246
 247 ; Negative test: mul(zext x, zext y) may overflow.
 248 define i32 @mul_may_overflow(i32 %x, i32 %y) {
 249 ; CHECK-LABEL: @mul_may_overflow(
 250 ; CHECK-NEXT:  entry:
 251 ; CHECK-NEXT:    [[L:%.*]] = zext i32 [[X:%.*]] to i34
 252 ; CHECK-NEXT:    [[R:%.*]] = zext i32 [[Y:%.*]] to i34
 253 ; CHECK-NEXT:    [[MUL34:%.*]] = mul i34 [[L]], [[R]]
 254 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ult i34 [[MUL34]], 4294967296
 255 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
 256 ; CHECK-NEXT:    ret i32 [[RETVAL]]
 257 ;
 258 entry:
 259   %l = zext i32 %x to i34
 260   %r = zext i32 %y to i34
 261   %mul34 = mul i34 %l, %r
 262   %overflow = icmp ule i34 %mul34, 4294967295
 263   %retval = zext i1 %overflow to i32
 264   ret i32 %retval
 265 }
 266
 267 define i32 @mul_known_nuw(i32 %x, i32 %y) {
 268 ; CHECK-LABEL: @mul_known_nuw(
 269 ; CHECK-NEXT:  entry:
 270 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
 271 ; CHECK-NEXT:    [[TMP0:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
 272 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = xor i1 [[TMP0]], true
 273 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
 274 ; CHECK-NEXT:    ret i32 [[RETVAL]]
 275 ;
 276 entry:
 277   %l = zext i32 %x to i34
 278   %r = zext i32 %y to i34
 279   %mul34 = mul nuw i34 %l, %r
 280   %overflow = icmp ule i34 %mul34, 4294967295
 281   %retval = zext i1 %overflow to i32
 282   ret i32 %retval
 283 }
 284
 285 define i32 @extra_and_use(i32 %x, i32 %y) {
 286 ; CHECK-LABEL: @extra_and_use(
 287 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
 288 ; CHECK-NEXT:    [[UMUL_VALUE:%.*]] = extractvalue { i32, i1 } [[UMUL]], 0
 289 ; CHECK-NEXT:    [[AND:%.*]] = zext i32 [[UMUL_VALUE]] to i64
 290 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
 291 ; CHECK-NEXT:    call void @use.i64(i64 [[AND]])
 292 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
 293 ; CHECK-NEXT:    ret i32 [[RETVAL]]
 294 ;
 295   %l = zext i32 %x to i64
 296   %r = zext i32 %y to i64
 297   %mul64 = mul i64 %l, %r
 298   %overflow = icmp ugt i64 %mul64, 4294967295
 299   %and = and i64 %mul64, u0xffffffff
 300   call void @use.i64(i64 %and)
 301   %retval = zext i1 %overflow to i32
 302   ret i32 %retval
 303 }
 304
 305 define i32 @extra_and_use_small_mask(i32 %x, i32 %y) {
 306 ; CHECK-LABEL: @extra_and_use_small_mask(
 307 ; CHECK-NEXT:    [[UMUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
 308 ; CHECK-NEXT:    [[UMUL_VALUE:%.*]] = extractvalue { i32, i1 } [[UMUL]], 0
 309 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[UMUL_VALUE]], 268435455
 310 ; CHECK-NEXT:    [[AND:%.*]] = zext nneg i32 [[TMP1]] to i64
 311 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UMUL]], 1
 312 ; CHECK-NEXT:    call void @use.i64(i64 [[AND]])
 313 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
 314 ; CHECK-NEXT:    ret i32 [[RETVAL]]
 315 ;
 316   %l = zext i32 %x to i64
 317   %r = zext i32 %y to i64
 318   %mul64 = mul i64 %l, %r
 319   %overflow = icmp ugt i64 %mul64, 4294967295
 320   %and = and i64 %mul64, u0xfffffff
 321   call void @use.i64(i64 %and)
 322   %retval = zext i1 %overflow to i32
 323   ret i32 %retval
 324 }
 325
 326 define i32 @extra_and_use_mask_too_large(i32 %x, i32 %y) {
 327 ; CHECK-LABEL: @extra_and_use_mask_too_large(
 328 ; CHECK-NEXT:    [[L:%.*]] = zext i32 [[X:%.*]] to i64
 329 ; CHECK-NEXT:    [[R:%.*]] = zext i32 [[Y:%.*]] to i64
 330 ; CHECK-NEXT:    [[MUL64:%.*]] = mul nuw i64 [[L]], [[R]]
 331 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i64 [[MUL64]], 4294967295
 332 ; CHECK-NEXT:    [[AND:%.*]] = and i64 [[MUL64]], 68719476735
 333 ; CHECK-NEXT:    call void @use.i64(i64 [[AND]])
 334 ; CHECK-NEXT:    [[RETVAL:%.*]] = zext i1 [[OVERFLOW]] to i32
 335 ; CHECK-NEXT:    ret i32 [[RETVAL]]
 336 ;
 337   %l = zext i32 %x to i64
 338   %r = zext i32 %y to i64
 339   %mul64 = mul i64 %l, %r
 340   %overflow = icmp ugt i64 %mul64, 4294967295
 341   %and = and i64 %mul64, u0xfffffffff
 342   call void @use.i64(i64 %and)
 343   %retval = zext i1 %overflow to i32
 344   ret i32 %retval
 345 }