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. 5target 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 14declare void @use.i64(i64) 15 16; return mul(zext x, zext y) > MAX 17define 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; 25entry: 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 35define 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; 43entry: 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 54define 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; 63entry: 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 75define 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; 85entry: 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 95define 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; 104entry: 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 114define 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; 123entry: 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 133define 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; 143entry: 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 154define 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; 162entry: 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 174define 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; 183entry: 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) 195define 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; 203entry: 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 214define <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 233define 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. 248define 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; 258entry: 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 267define 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; 276entry: 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 285define 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 305define 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 326define 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} 346