3020 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 52; RUN: opt < %s -passes=aggressive-instcombine,instcombine -S | FileCheck %s3 4; https://alive2.llvm.org/ce/z/KuJPnU5define i64 @umulh(i64 %x, i64 %y) {6; CHECK-LABEL: define i64 @umulh(7; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {8; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i1289; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i12810; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]11; CHECK-NEXT: [[TMP5:%.*]] = lshr i128 [[TMP3]], 6412; CHECK-NEXT: [[TMP4:%.*]] = trunc nuw i128 [[TMP5]] to i6413; CHECK-NEXT: ret i64 [[TMP4]]14;15 ; Extract low and high 32 bits16 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff17 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff18 %x_hi = lshr i64 %x, 32 ; x >> 3219 %y_hi = lshr i64 %y, 32 ; y >> 3220 21 ; Cross products22 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi23 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi24 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo25 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo26 27 ; Add cross terms28 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum29 30 ; Carry if overflowed31 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi32 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 3233 34 ; High 32 bits of low product35 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 3236 37 ; Low and high 32 bits of cross_sum38 %cross_sum_lo = and i64 %cross_sum, 429496729539 %cross_sum_hi = lshr i64 %cross_sum, 3240 41 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi42 43 ; Final result accumulation44 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi45 %low_accum_hi = lshr i64 %low_accum, 3246 %intermediate_plus_carry = add i64 %intermediate, %carry47 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi48 49 ret i64 %hw6450}51 52; Commutative ops should match in any order. Ops where operand order has been53; reversed from above are marked 'commuted'. As per instcombine contributors54; guide, constants are always canonicalized to RHS, so don't bother commuting55; constants.56define i64 @umulh__commuted(i64 %x, i64 %y) {57; CHECK-LABEL: define i64 @umulh__commuted(58; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {59; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i12860; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i12861; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]62; CHECK-NEXT: [[TMP5:%.*]] = lshr i128 [[TMP3]], 6463; CHECK-NEXT: [[TMP4:%.*]] = trunc nuw i128 [[TMP5]] to i6464; CHECK-NEXT: ret i64 [[TMP4]]65;66 ; Extract low and high 32 bits67 %x_lo = and i64 %x, 429496729568 %y_lo = and i64 %y, 429496729569 %x_hi = lshr i64 %x, 32 ; x >> 3270 %y_hi = lshr i64 %y, 32 ; y >> 3271 72 ; Cross products73 %y_lo_x_hi = mul nuw i64 %x_hi, %y_lo ; commuted74 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi75 %y_hi_x_lo = mul nuw i64 %x_lo, %y_hi ; commuted76 %y_lo_x_lo = mul nuw i64 %x_lo, %y_lo ; commuted77 78 ; Add cross terms79 %cross_sum = add i64 %y_lo_x_hi, %y_hi_x_lo ; commuted80 81 ; Carry if overflowed82 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi83 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 3284 85 ; High 32 bits of low product86 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 3287 88 ; Low and high 32 bits of cross_sum89 %cross_sum_lo = and i64 %cross_sum, 429496729590 %cross_sum_hi = lshr i64 %cross_sum, 3291 92 %low_accum = add nuw nsw i64 %y_lo_x_lo_hi, %cross_sum_lo ; commuted93 94 ; Final result accumulation95 %intermediate = add nuw i64 %y_hi_x_hi, %cross_sum_hi ; commuted96 %low_accum_hi = lshr i64 %low_accum, 3297 %intermediate_plus_carry = add i64 %carry, %intermediate ; commuted98 %hw64 = add i64 %low_accum_hi, %intermediate_plus_carry ; commuted99 100 ret i64 %hw64101}102 103define i32 @mulh_src32(i32 %x, i32 %y) {104 ; Extract low and high 16 bits105; CHECK-LABEL: define i32 @mulh_src32(106; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {107; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[X]] to i64108; CHECK-NEXT: [[TMP2:%.*]] = zext i32 [[Y]] to i64109; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i64 [[TMP1]], [[TMP2]]110; CHECK-NEXT: [[TMP4:%.*]] = lshr i64 [[TMP3]], 32111; CHECK-NEXT: [[TMP5:%.*]] = trunc nuw i64 [[TMP4]] to i32112; CHECK-NEXT: ret i32 [[TMP5]]113;114 %x_lo = and i32 %x, u0xffff ; x & 0xffffffff115 %y_lo = and i32 %y, u0xffff ; y & 0xffffffff116 %x_hi = lshr i32 %x, 16 ; x >> 16117 %y_hi = lshr i32 %y, 16 ; y >> 16118 119 ; Cross products120 %y_lo_x_hi = mul nuw i32 %y_lo, %x_hi ; y_lo * x_hi121 %y_hi_x_hi = mul nuw i32 %y_hi, %x_hi ; y_hi * x_hi122 %y_hi_x_lo = mul nuw i32 %y_hi, %x_lo ; y_hi * x_lo123 %y_lo_x_lo = mul nuw i32 %y_lo, %x_lo ; y_lo * x_lo124 125 ; Add cross terms126 %cross_sum = add i32 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum127 128 ; Carry if overflowed129 %carry_out = icmp ult i32 %cross_sum, %y_lo_x_hi130 %carry = select i1 %carry_out, i32 u0x10000, i32 0 ; if overflow, add 1 << 16131 132 ; High 16 bits of low product133 %y_lo_x_lo_hi = lshr i32 %y_lo_x_lo, 16134 135 ; Low and high 16 bits of cross_sum136 %cross_sum_lo = and i32 %cross_sum, u0xffff137 %cross_sum_hi = lshr i32 %cross_sum, 16138 139 %low_accum = add nuw nsw i32 %cross_sum_lo, %y_lo_x_lo_hi140 141 ; Final result accumulation142 %intermediate = add nuw i32 %cross_sum_hi, %y_hi_x_hi143 %low_accum_hi = lshr i32 %low_accum, 16144 %intermediate_plus_carry = add i32 %intermediate, %carry145 %hw64 = add i32 %intermediate_plus_carry, %low_accum_hi146 147 ret i32 %hw64148}149 150define i128 @mulh_src128(i128 %x, i128 %y) {151 ; Extract low and high 64 bits152; CHECK-LABEL: define i128 @mulh_src128(153; CHECK-SAME: i128 [[X:%.*]], i128 [[Y:%.*]]) {154; CHECK-NEXT: [[TMP1:%.*]] = zext i128 [[X]] to i256155; CHECK-NEXT: [[TMP2:%.*]] = zext i128 [[Y]] to i256156; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i256 [[TMP1]], [[TMP2]]157; CHECK-NEXT: [[TMP4:%.*]] = lshr i256 [[TMP3]], 128158; CHECK-NEXT: [[HW64:%.*]] = trunc nuw i256 [[TMP4]] to i128159; CHECK-NEXT: ret i128 [[HW64]]160;161 %x_lo = and i128 %x, u0xffffffffffffffff ; x & 0xffffffff162 %y_lo = and i128 %y, u0xffffffffffffffff ; y & 0xffffffff163 %x_hi = lshr i128 %x, 64 ; x >> 16164 %y_hi = lshr i128 %y, 64 ; y >> 16165 166 ; Cross products167 %y_lo_x_hi = mul nuw i128 %y_lo, %x_hi ; y_lo * x_hi168 %y_hi_x_hi = mul nuw i128 %y_hi, %x_hi ; y_hi * x_hi169 %y_hi_x_lo = mul nuw i128 %y_hi, %x_lo ; y_hi * x_lo170 %y_lo_x_lo = mul nuw i128 %y_lo, %x_lo ; y_lo * x_lo171 172 ; Add cross terms173 %cross_sum = add i128 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum174 175 ; Carry if overflowed176 %carry_out = icmp ult i128 %cross_sum, %y_lo_x_hi177 %carry = select i1 %carry_out, i128 u0x10000000000000000, i128 0 ; if overflow, add 1 << 16178 179 ; High 16 bits of low product180 %y_lo_x_lo_hi = lshr i128 %y_lo_x_lo, 64181 182 ; Low and high 16 bits of cross_sum183 %cross_sum_lo = and i128 %cross_sum, u0xffffffffffffffff184 %cross_sum_hi = lshr i128 %cross_sum, 64185 186 %low_accum = add nuw nsw i128 %cross_sum_lo, %y_lo_x_lo_hi187 188 ; Final result accumulation189 %intermediate = add nuw i128 %cross_sum_hi, %y_hi_x_hi190 %low_accum_hi = lshr i128 %low_accum, 64191 %intermediate_plus_carry = add i128 %intermediate, %carry192 %hw64 = add i128 %intermediate_plus_carry, %low_accum_hi193 194 ret i128 %hw64195}196 197define <2 x i32> @mulh_v2i32(<2 x i32> %x, <2 x i32> %y) {198 ; Extract low and high 16 bits199; CHECK-LABEL: define <2 x i32> @mulh_v2i32(200; CHECK-SAME: <2 x i32> [[X:%.*]], <2 x i32> [[Y:%.*]]) {201; CHECK-NEXT: [[TMP1:%.*]] = zext <2 x i32> [[X]] to <2 x i64>202; CHECK-NEXT: [[TMP2:%.*]] = zext <2 x i32> [[Y]] to <2 x i64>203; CHECK-NEXT: [[TMP3:%.*]] = mul nuw <2 x i64> [[TMP1]], [[TMP2]]204; CHECK-NEXT: [[TMP4:%.*]] = lshr <2 x i64> [[TMP3]], splat (i64 32)205; CHECK-NEXT: [[HW64:%.*]] = trunc nuw <2 x i64> [[TMP4]] to <2 x i32>206; CHECK-NEXT: ret <2 x i32> [[HW64]]207;208 %x_lo = and <2 x i32> %x, <i32 u0xffff, i32 u0xffff>209 %y_lo = and <2 x i32> %y, <i32 u0xffff, i32 u0xffff>210 %x_hi = lshr <2 x i32> %x, <i32 16, i32 16>211 %y_hi = lshr <2 x i32> %y, <i32 16, i32 16>212 213 ; Cross products214 %y_lo_x_hi = mul nuw <2 x i32> %y_lo, %x_hi ; y_lo * x_hi215 %y_hi_x_hi = mul nuw <2 x i32> %y_hi, %x_hi ; y_hi * x_hi216 %y_hi_x_lo = mul nuw <2 x i32> %y_hi, %x_lo ; y_hi * x_lo217 %y_lo_x_lo = mul nuw <2 x i32> %y_lo, %x_lo ; y_lo * x_lo218 219 ; Add cross terms220 %cross_sum = add <2 x i32> %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum221 222 ; Carry if overflowed223 %carry_out = icmp ult <2 x i32> %cross_sum, %y_lo_x_hi224 %carry = select <2 x i1> %carry_out, <2 x i32> <i32 u0x10000, i32 u0x10000>, <2 x i32> <i32 0, i32 0>225 226 ; High 16 bits of low product227 %y_lo_x_lo_hi = lshr <2 x i32> %y_lo_x_lo, <i32 16, i32 16>228 229 ; Low and high 16 bits of cross_sum230 %cross_sum_lo = and <2 x i32> %cross_sum, <i32 u0xffff, i32 u0xffff>231 %cross_sum_hi = lshr <2 x i32> %cross_sum, <i32 16, i32 16>232 233 %low_accum = add nuw nsw <2 x i32> %cross_sum_lo, %y_lo_x_lo_hi234 235 ; Final result accumulation236 %intermediate = add nuw <2 x i32> %cross_sum_hi, %y_hi_x_hi237 %low_accum_hi = lshr <2 x i32> %low_accum, <i32 16, i32 16>238 %intermediate_plus_carry = add <2 x i32> %intermediate, %carry239 %hw64 = add <2 x i32> %intermediate_plus_carry, %low_accum_hi240 241 ret <2 x i32> %hw64242}243 244; https://alive2.llvm.org/ce/z/PPXtkR245define void @full_mul_int128(i64 %x, i64 %y, ptr %p) {246; CHECK-LABEL: define void @full_mul_int128(247; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {248; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i128249; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i128250; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]251; CHECK-NEXT: [[TMP5:%.*]] = lshr i128 [[TMP3]], 64252; CHECK-NEXT: [[TMP4:%.*]] = trunc nuw i128 [[TMP5]] to i64253; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 8254; CHECK-NEXT: store i64 [[TMP4]], ptr [[HI_PTR]], align 8255; CHECK-NEXT: [[TMP8:%.*]] = mul i64 [[X]], [[Y]]256; CHECK-NEXT: store i64 [[TMP8]], ptr [[P]], align 8257; CHECK-NEXT: ret void258;259 ; Extract low and high 32 bits260 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff261 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff262 %x_hi = lshr i64 %x, 32 ; x >> 32263 %y_hi = lshr i64 %y, 32 ; y >> 32264 265 ; Cross products266 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi267 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi268 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo269 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo270 271 ; Add cross terms272 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum273 274 ; Carry if overflowed275 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi276 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 32277 278 ; High 32 bits of low product279 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32280 281 ; Low and high 32 bits of cross_sum282 %cross_sum_lo = and i64 %cross_sum, 4294967295283 %cross_sum_hi = lshr i64 %cross_sum, 32284 285 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi286 287 ; Final result accumulation288 %upper_mid = add nuw i64 %y_hi_x_hi, %carry289 %low_accum_hi = lshr i64 %low_accum, 32290 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi291 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi292 293 ; Store high 64 bits294 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 8295 store i64 %hw64, ptr %hi_ptr, align 8296 297 ; Reconstruct low 64 bits298 %low_accum_shifted = shl i64 %low_accum, 32299 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 4294967295300 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo301 302 ; Store low 64 bits303 store i64 %lw64, ptr %p, align 8304 305 ret void306}307 308 309; Negative tests310 311define i64 @umulh_notandx(i64 %x, i64 %y) {312; CHECK-LABEL: define i64 @umulh_notandx(313; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {314; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 4294967294315; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 4294967295316; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 32317; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 32318; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]319; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]320; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]321; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]322; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]323; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]324; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 0325; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 32326; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 4294967295327; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 32328; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]329; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]330; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 32331; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]332; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]333; CHECK-NEXT: ret i64 [[HW64]]334;335 ; Extract low and high 32 bits336 %x_lo = and i64 %x, 4294967294 ; x & 0xfffffffe337 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff338 %x_hi = lshr i64 %x, 32 ; x >> 32339 %y_hi = lshr i64 %y, 32 ; y >> 32340 341 ; Cross products342 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi343 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi344 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo345 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo346 347 ; Add cross terms348 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum349 350 ; Carry if overflowed351 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi352 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 32353 354 ; High 32 bits of low product355 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32356 357 ; Low and high 32 bits of cross_sum358 %cross_sum_lo = and i64 %cross_sum, 4294967295359 %cross_sum_hi = lshr i64 %cross_sum, 32360 361 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi362 363 ; Final result accumulation364 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi365 %low_accum_hi = lshr i64 %low_accum, 32366 %intermediate_plus_carry = add i64 %intermediate, %carry367 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi368 369 ret i64 %hw64370}371 372define i64 @umulh_notandy(i64 %x, i64 %y) {373; CHECK-LABEL: define i64 @umulh_notandy(374; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {375; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 4294967295376; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 4294967294377; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 32378; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 32379; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]380; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]381; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]382; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]383; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]384; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]385; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 0386; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 32387; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 4294967295388; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 32389; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]390; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]391; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 32392; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]393; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]394; CHECK-NEXT: ret i64 [[HW64]]395;396 ; Extract low and high 32 bits397 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff398 %y_lo = and i64 %y, 4294967294 ; y & 0xfffffffe399 %x_hi = lshr i64 %x, 32 ; x >> 32400 %y_hi = lshr i64 %y, 32 ; y >> 32401 402 ; Cross products403 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi404 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi405 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo406 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo407 408 ; Add cross terms409 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum410 411 ; Carry if overflowed412 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi413 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 32414 415 ; High 32 bits of low product416 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32417 418 ; Low and high 32 bits of cross_sum419 %cross_sum_lo = and i64 %cross_sum, 4294967295420 %cross_sum_hi = lshr i64 %cross_sum, 32421 422 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi423 424 ; Final result accumulation425 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi426 %low_accum_hi = lshr i64 %low_accum, 32427 %intermediate_plus_carry = add i64 %intermediate, %carry428 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi429 430 ret i64 %hw64431}432 433define i64 @umulh_notshiftx(i64 %x, i64 %y) {434; CHECK-LABEL: define i64 @umulh_notshiftx(435; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {436; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 4294967295437; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 4294967295438; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 16439; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 32440; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]441; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]442; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]443; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]444; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]445; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]446; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 0447; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 32448; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 4294967295449; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 32450; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]451; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]452; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 32453; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]454; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]455; CHECK-NEXT: ret i64 [[HW64]]456;457 ; Extract low and high 32 bits458 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff459 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff460 %x_hi = lshr i64 %x, 16 ; x >> 16461 %y_hi = lshr i64 %y, 32 ; y >> 32462 463 ; Cross products464 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi465 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi466 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo467 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo468 469 ; Add cross terms470 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum471 472 ; Carry if overflowed473 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi474 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 32475 476 ; High 32 bits of low product477 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32478 479 ; Low and high 32 bits of cross_sum480 %cross_sum_lo = and i64 %cross_sum, 4294967295481 %cross_sum_hi = lshr i64 %cross_sum, 32482 483 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi484 485 ; Final result accumulation486 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi487 %low_accum_hi = lshr i64 %low_accum, 32488 %intermediate_plus_carry = add i64 %intermediate, %carry489 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi490 491 ret i64 %hw64492}493 494define i64 @umulh_notshifty(i64 %x, i64 %y) {495; CHECK-LABEL: define i64 @umulh_notshifty(496; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {497; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 4294967295498; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 4294967295499; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 32500; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 16501; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]502; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]503; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]504; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]505; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]506; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]507; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 0508; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 32509; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 4294967295510; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 32511; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]512; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]513; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 32514; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]515; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]516; CHECK-NEXT: ret i64 [[HW64]]517;518 ; Extract low and high 32 bits519 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff520 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff521 %x_hi = lshr i64 %x, 32 ; x >> 32522 %y_hi = lshr i64 %y, 16 ; y >> 16523 524 ; Cross products525 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi526 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi527 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo528 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo529 530 ; Add cross terms531 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum532 533 ; Carry if overflowed534 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi535 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 32536 537 ; High 32 bits of low product538 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32539 540 ; Low and high 32 bits of cross_sum541 %cross_sum_lo = and i64 %cross_sum, 4294967295542 %cross_sum_hi = lshr i64 %cross_sum, 32543 544 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi545 546 ; Final result accumulation547 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi548 %low_accum_hi = lshr i64 %low_accum, 32549 %intermediate_plus_carry = add i64 %intermediate, %carry550 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi551 552 ret i64 %hw64553}554 555define i64 @umulh_notcarry(i64 %x, i64 %y) {556; CHECK-LABEL: define i64 @umulh_notcarry(557; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {558; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 4294967295559; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 4294967295560; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 32561; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 32562; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]563; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]564; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]565; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]566; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]567; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]568; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967295, i64 0569; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 32570; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 4294967295571; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 32572; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]573; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]574; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 32575; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]576; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]577; CHECK-NEXT: ret i64 [[HW64]]578;579 ; Extract low and high 32 bits580 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff581 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff582 %x_hi = lshr i64 %x, 32 ; x >> 32583 %y_hi = lshr i64 %y, 32 ; y >> 32584 585 ; Cross products586 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi587 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi588 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo589 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo590 591 ; Add cross terms592 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum593 594 ; Carry if overflowed595 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi596 %carry = select i1 %carry_out, i64 4294967295, i64 0 ; if overflow, add wrong value597 598 ; High 32 bits of low product599 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32600 601 ; Low and high 32 bits of cross_sum602 %cross_sum_lo = and i64 %cross_sum, 4294967295603 %cross_sum_hi = lshr i64 %cross_sum, 32604 605 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi606 607 ; Final result accumulation608 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi609 %low_accum_hi = lshr i64 %low_accum, 32610 %intermediate_plus_carry = add i64 %intermediate, %carry611 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi612 613 ret i64 %hw64614}615 616define i64 @umulh_notxlo(i64 %x, i64 %y) {617; CHECK-LABEL: define i64 @umulh_notxlo(618; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {619; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 4294967295620; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 4294967295621; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 32622; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 32623; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]624; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]625; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]626; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X]]627; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]628; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]629; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 0630; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 32631; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 4294967295632; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 32633; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]634; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]635; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 32636; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]637; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]638; CHECK-NEXT: ret i64 [[HW64]]639;640 ; Extract low and high 32 bits641 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff642 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff643 %x_hi = lshr i64 %x, 32 ; x >> 32644 %y_hi = lshr i64 %y, 32 ; y >> 32645 646 ; Cross products647 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi648 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi649 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo650 %y_lo_x_lo = mul nuw i64 %y_lo, %x ; y_lo * x651 652 ; Add cross terms653 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum654 655 ; Carry if overflowed656 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi657 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 32658 659 ; High 32 bits of low product660 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32661 662 ; Low and high 32 bits of cross_sum663 %cross_sum_lo = and i64 %cross_sum, 4294967295664 %cross_sum_hi = lshr i64 %cross_sum, 32665 666 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi667 668 ; Final result accumulation669 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi670 %low_accum_hi = lshr i64 %low_accum, 32671 %intermediate_plus_carry = add i64 %intermediate, %carry672 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi673 674 ret i64 %hw64675}676 677define i64 @umulh_notcrosssum(i64 %x, i64 %y) {678; CHECK-LABEL: define i64 @umulh_notcrosssum(679; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {680; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 4294967295681; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 4294967295682; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 32683; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 32684; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]685; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]686; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]687; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]688; CHECK-NEXT: [[CROSS_SUM:%.*]] = shl i64 [[Y_HI_X_LO]], 1689; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]690; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 0691; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 32692; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 4294967294693; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 32694; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]695; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]696; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 32697; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]698; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]699; CHECK-NEXT: ret i64 [[HW64]]700;701 ; Extract low and high 32 bits702 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff703 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff704 %x_hi = lshr i64 %x, 32 ; x >> 32705 %y_hi = lshr i64 %y, 32 ; y >> 32706 707 ; Cross products708 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi709 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi710 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo711 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo712 713 ; Add cross terms714 %cross_sum = add i64 %y_hi_x_lo, %y_hi_x_lo ; wrong crosssum715 716 ; Carry if overflowed717 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi718 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 32719 720 ; High 32 bits of low product721 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32722 723 ; Low and high 32 bits of cross_sum724 %cross_sum_lo = and i64 %cross_sum, 4294967295725 %cross_sum_hi = lshr i64 %cross_sum, 32726 727 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi728 729 ; Final result accumulation730 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi731 %low_accum_hi = lshr i64 %low_accum, 32732 %intermediate_plus_carry = add i64 %intermediate, %carry733 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi734 735 ret i64 %hw64736}737 738 739 740; Uses tests.741 742; 'x_lo' can have more than 2 uses.743define i64 @umulh__mul_use__x_lo(i64 %x, i64 %y) {744; CHECK-LABEL: define i64 @umulh__mul_use__x_lo(745; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {746; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 4294967295747; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[X_LO]])748; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i128749; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i128750; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]751; CHECK-NEXT: [[TMP4:%.*]] = lshr i128 [[TMP3]], 64752; CHECK-NEXT: [[HW64:%.*]] = trunc nuw i128 [[TMP4]] to i64753; CHECK-NEXT: ret i64 [[HW64]]754;755 ; Extract low and high 32 bits756 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff757 call void (...) @llvm.fake.use(i64 %x_lo)758 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff759 %x_hi = lshr i64 %x, 32 ; x >> 32760 %y_hi = lshr i64 %y, 32 ; y >> 32761 762 ; Cross products763 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi764 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi765 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo766 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo767 768 ; Add cross terms769 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum770 771 ; Carry if overflowed772 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi773 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 32774 775 ; High 32 bits of low product776 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32777 778 ; Low and high 32 bits of cross_sum779 %cross_sum_lo = and i64 %cross_sum, 4294967295780 %cross_sum_hi = lshr i64 %cross_sum, 32781 782 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi783 784 ; Final result accumulation785 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi786 %low_accum_hi = lshr i64 %low_accum, 32787 %intermediate_plus_carry = add i64 %intermediate, %carry788 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi789 790 ret i64 %hw64791}792 793; 'y_hi' can have more than 2 uses.794define i64 @umulh__mul_use__y_hi(i64 %x, i64 %y) {795; CHECK-LABEL: define i64 @umulh__mul_use__y_hi(796; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {797; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 32798; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_HI]])799; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i128800; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i128801; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]802; CHECK-NEXT: [[TMP4:%.*]] = lshr i128 [[TMP3]], 64803; CHECK-NEXT: [[HW64:%.*]] = trunc nuw i128 [[TMP4]] to i64804; CHECK-NEXT: ret i64 [[HW64]]805;806 ; Extract low and high 32 bits807 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff808 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff809 %x_hi = lshr i64 %x, 32 ; x >> 32810 %y_hi = lshr i64 %y, 32 ; y >> 32811 call void (...) @llvm.fake.use(i64 %y_hi)812 813 ; Cross products814 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi815 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi816 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo817 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo818 819 ; Add cross terms820 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum821 822 ; Carry if overflowed823 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi824 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 32825 826 ; High 32 bits of low product827 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32828 829 ; Low and high 32 bits of cross_sum830 %cross_sum_lo = and i64 %cross_sum, 4294967295831 %cross_sum_hi = lshr i64 %cross_sum, 32832 833 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi834 835 ; Final result accumulation836 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi837 %low_accum_hi = lshr i64 %low_accum, 32838 %intermediate_plus_carry = add i64 %intermediate, %carry839 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi840 841 ret i64 %hw64842}843 844; 'y_hi * x_hi' must have no more than 2 uses.845define i64 @umulh__mul_use__y_lo_x_hi(i64 %x, i64 %y) {846; CHECK-LABEL: define i64 @umulh__mul_use__y_lo_x_hi(847; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {848; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 4294967295849; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 4294967295850; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 32851; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 32852; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]853; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_LO_X_HI]])854; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]855; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]856; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]857; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]858; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]859; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 0860; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 32861; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 4294967295862; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 32863; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]864; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]865; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 32866; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]867; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]868; CHECK-NEXT: ret i64 [[HW64]]869;870 ; Extract low and high 32 bits871 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff872 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff873 %x_hi = lshr i64 %x, 32 ; x >> 32874 %y_hi = lshr i64 %y, 32 ; y >> 32875 876 ; Cross products877 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi878 call void (...) @llvm.fake.use(i64 %y_lo_x_hi)879 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi880 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo881 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo882 883 ; Add cross terms884 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum885 886 ; Carry if overflowed887 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi888 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 32889 890 ; High 32 bits of low product891 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32892 893 ; Low and high 32 bits of cross_sum894 %cross_sum_lo = and i64 %cross_sum, 4294967295895 %cross_sum_hi = lshr i64 %cross_sum, 32896 897 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi898 899 ; Final result accumulation900 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi901 %low_accum_hi = lshr i64 %low_accum, 32902 %intermediate_plus_carry = add i64 %intermediate, %carry903 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi904 905 ret i64 %hw64906}907 908; 'y_hi * x_hi' must have single use.909define i64 @umulh__mul_use__y_hi_x_hi(i64 %x, i64 %y) {910; CHECK-LABEL: define i64 @umulh__mul_use__y_hi_x_hi(911; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {912; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 4294967295913; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 4294967295914; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 32915; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 32916; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]917; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]918; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_HI_X_HI]])919; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]920; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]921; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]922; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]923; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 0924; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 32925; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 4294967295926; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 32927; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]928; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]929; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 32930; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]931; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]932; CHECK-NEXT: ret i64 [[HW64]]933;934 ; Extract low and high 32 bits935 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff936 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff937 %x_hi = lshr i64 %x, 32 ; x >> 32938 %y_hi = lshr i64 %y, 32 ; y >> 32939 940 ; Cross products941 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi942 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi943 call void (...) @llvm.fake.use(i64 %y_hi_x_hi)944 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo945 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo946 947 ; Add cross terms948 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum949 950 ; Carry if overflowed951 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi952 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 32953 954 ; High 32 bits of low product955 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 32956 957 ; Low and high 32 bits of cross_sum958 %cross_sum_lo = and i64 %cross_sum, 4294967295959 %cross_sum_hi = lshr i64 %cross_sum, 32960 961 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi962 963 ; Final result accumulation964 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi965 %low_accum_hi = lshr i64 %low_accum, 32966 %intermediate_plus_carry = add i64 %intermediate, %carry967 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi968 969 ret i64 %hw64970}971 972; 'y_hi * x_lo' must have single use.973define i64 @umulh__mul_use__y_hi_x_lo(i64 %x, i64 %y) {974; CHECK-LABEL: define i64 @umulh__mul_use__y_hi_x_lo(975; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {976; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 4294967295977; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 4294967295978; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 32979; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 32980; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]981; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]982; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]983; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_HI_X_LO]])984; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]985; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]986; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]987; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 0988; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 32989; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 4294967295990; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 32991; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]992; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]993; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 32994; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]995; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]996; CHECK-NEXT: ret i64 [[HW64]]997;998 ; Extract low and high 32 bits999 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1000 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1001 %x_hi = lshr i64 %x, 32 ; x >> 321002 %y_hi = lshr i64 %y, 32 ; y >> 321003 1004 ; Cross products1005 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1006 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1007 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1008 call void (...) @llvm.fake.use(i64 %y_hi_x_lo)1009 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1010 1011 ; Add cross terms1012 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1013 1014 ; Carry if overflowed1015 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1016 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321017 1018 ; High 32 bits of low product1019 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321020 1021 ; Low and high 32 bits of cross_sum1022 %cross_sum_lo = and i64 %cross_sum, 42949672951023 %cross_sum_hi = lshr i64 %cross_sum, 321024 1025 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1026 1027 ; Final result accumulation1028 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1029 %low_accum_hi = lshr i64 %low_accum, 321030 %intermediate_plus_carry = add i64 %intermediate, %carry1031 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1032 1033 ret i64 %hw641034}1035 1036; 'y_lo * x_lo' has a single use if only doing high part of multiply and 2 uses1037; when doing both low/high parts. Doing the optimization when only doing the1038; high part and there's a 2nd unrelated use here still results in less1039; instructions and is likely profitable, so this seems ok.1040define i64 @umulh__mul_use__y_lo_x_lo(i64 %x, i64 %y) {1041; CHECK-LABEL: define i64 @umulh__mul_use__y_lo_x_lo(1042; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {1043; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951044; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951045; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1046; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_LO_X_LO]])1047; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i1281048; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i1281049; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]1050; CHECK-NEXT: [[TMP4:%.*]] = lshr i128 [[TMP3]], 641051; CHECK-NEXT: [[TMP5:%.*]] = trunc nuw i128 [[TMP4]] to i641052; CHECK-NEXT: ret i64 [[TMP5]]1053;1054 ; Extract low and high 32 bits1055 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1056 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1057 %x_hi = lshr i64 %x, 32 ; x >> 321058 %y_hi = lshr i64 %y, 32 ; y >> 321059 1060 ; Cross products1061 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1062 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1063 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1064 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1065 call void (...) @llvm.fake.use(i64 %y_lo_x_lo)1066 1067 ; Add cross terms1068 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1069 1070 ; Carry if overflowed1071 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1072 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321073 1074 ; High 32 bits of low product1075 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321076 1077 ; Low and high 32 bits of cross_sum1078 %cross_sum_lo = and i64 %cross_sum, 42949672951079 %cross_sum_hi = lshr i64 %cross_sum, 321080 1081 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1082 1083 ; Final result accumulation1084 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1085 %low_accum_hi = lshr i64 %low_accum, 321086 %intermediate_plus_carry = add i64 %intermediate, %carry1087 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1088 1089 ret i64 %hw641090}1091 1092; 'cross_sum' must have no more than 3 uses.1093define i64 @umulh__mul_use__cross_sum(i64 %x, i64 %y) {1094; CHECK-LABEL: define i64 @umulh__mul_use__cross_sum(1095; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {1096; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951097; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951098; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321099; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321100; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]1101; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]1102; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]1103; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1104; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]1105; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[CROSS_SUM]])1106; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]1107; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 01108; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 321109; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672951110; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 321111; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]1112; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]1113; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 321114; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]1115; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]1116; CHECK-NEXT: ret i64 [[HW64]]1117;1118 ; Extract low and high 32 bits1119 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1120 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1121 %x_hi = lshr i64 %x, 32 ; x >> 321122 %y_hi = lshr i64 %y, 32 ; y >> 321123 1124 ; Cross products1125 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1126 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1127 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1128 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1129 1130 ; Add cross terms1131 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1132 1133 call void (...) @llvm.fake.use(i64 %cross_sum)1134 1135 ; Carry if overflowed1136 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1137 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321138 1139 ; High 32 bits of low product1140 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321141 1142 ; Low and high 32 bits of cross_sum1143 %cross_sum_lo = and i64 %cross_sum, 42949672951144 %cross_sum_hi = lshr i64 %cross_sum, 321145 1146 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1147 1148 ; Final result accumulation1149 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1150 %low_accum_hi = lshr i64 %low_accum, 321151 %intermediate_plus_carry = add i64 %intermediate, %carry1152 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1153 1154 ret i64 %hw641155}1156 1157; 'carry_out' must have single use.1158define i64 @umulh__mul_use__carry_out(i64 %x, i64 %y) {1159; CHECK-LABEL: define i64 @umulh__mul_use__carry_out(1160; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {1161; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951162; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951163; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321164; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321165; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]1166; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]1167; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]1168; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1169; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]1170; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]1171; CHECK-NEXT: call void (...) @llvm.fake.use(i1 [[CARRY_OUT]])1172; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 01173; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 321174; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672951175; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 321176; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]1177; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]1178; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 321179; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]1180; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]1181; CHECK-NEXT: ret i64 [[HW64]]1182;1183 ; Extract low and high 32 bits1184 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1185 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1186 %x_hi = lshr i64 %x, 32 ; x >> 321187 %y_hi = lshr i64 %y, 32 ; y >> 321188 1189 ; Cross products1190 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1191 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1192 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1193 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1194 1195 ; Add cross terms1196 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1197 1198 ; Carry if overflowed1199 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1200 call void (...) @llvm.fake.use(i1 %carry_out)1201 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321202 1203 ; High 32 bits of low product1204 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321205 1206 ; Low and high 32 bits of cross_sum1207 %cross_sum_lo = and i64 %cross_sum, 42949672951208 %cross_sum_hi = lshr i64 %cross_sum, 321209 1210 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1211 1212 ; Final result accumulation1213 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1214 %low_accum_hi = lshr i64 %low_accum, 321215 %intermediate_plus_carry = add i64 %intermediate, %carry1216 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1217 1218 ret i64 %hw641219}1220 1221; 'carry' must have single use.1222define i64 @umulh__mul_use__carry(i64 %x, i64 %y) {1223; CHECK-LABEL: define i64 @umulh__mul_use__carry(1224; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {1225; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951226; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951227; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321228; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321229; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]1230; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]1231; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]1232; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1233; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]1234; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]1235; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 01236; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[CARRY]])1237; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 321238; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672951239; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 321240; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]1241; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]1242; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 321243; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]1244; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]1245; CHECK-NEXT: ret i64 [[HW64]]1246;1247 ; Extract low and high 32 bits1248 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1249 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1250 %x_hi = lshr i64 %x, 32 ; x >> 321251 %y_hi = lshr i64 %y, 32 ; y >> 321252 1253 ; Cross products1254 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1255 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1256 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1257 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1258 1259 ; Add cross terms1260 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1261 1262 ; Carry if overflowed1263 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1264 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321265 call void (...) @llvm.fake.use(i64 %carry)1266 1267 ; High 32 bits of low product1268 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321269 1270 ; Low and high 32 bits of cross_sum1271 %cross_sum_lo = and i64 %cross_sum, 42949672951272 %cross_sum_hi = lshr i64 %cross_sum, 321273 1274 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1275 1276 ; Final result accumulation1277 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1278 %low_accum_hi = lshr i64 %low_accum, 321279 %intermediate_plus_carry = add i64 %intermediate, %carry1280 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1281 1282 ret i64 %hw641283}1284 1285; 'y_lo_x_lo_hi' must have single use.1286define i64 @umulh__mul_use__y_lo_x_lo_hi(i64 %x, i64 %y) {1287; CHECK-LABEL: define i64 @umulh__mul_use__y_lo_x_lo_hi(1288; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {1289; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951290; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951291; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321292; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321293; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]1294; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]1295; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]1296; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1297; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]1298; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]1299; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 01300; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 321301; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_LO_X_LO_HI]])1302; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672951303; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 321304; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]1305; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]1306; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 321307; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]1308; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]1309; CHECK-NEXT: ret i64 [[HW64]]1310;1311 ; Extract low and high 32 bits1312 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1313 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1314 %x_hi = lshr i64 %x, 32 ; x >> 321315 %y_hi = lshr i64 %y, 32 ; y >> 321316 1317 ; Cross products1318 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1319 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1320 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1321 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1322 1323 ; Add cross terms1324 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1325 1326 ; Carry if overflowed1327 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1328 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321329 1330 ; High 32 bits of low product1331 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321332 call void (...) @llvm.fake.use(i64 %y_lo_x_lo_hi)1333 1334 ; Low and high 32 bits of cross_sum1335 %cross_sum_lo = and i64 %cross_sum, 42949672951336 %cross_sum_hi = lshr i64 %cross_sum, 321337 1338 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1339 1340 ; Final result accumulation1341 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1342 %low_accum_hi = lshr i64 %low_accum, 321343 %intermediate_plus_carry = add i64 %intermediate, %carry1344 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1345 1346 ret i64 %hw641347}1348 1349; 'cross_sum_lo' must have single use.1350define i64 @umulh__mul_use__cross_sum_lo(i64 %x, i64 %y) {1351; CHECK-LABEL: define i64 @umulh__mul_use__cross_sum_lo(1352; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {1353; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951354; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951355; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321356; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321357; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]1358; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]1359; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]1360; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1361; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]1362; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]1363; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 01364; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 321365; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672951366; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[CROSS_SUM_LO]])1367; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 321368; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]1369; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]1370; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 321371; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]1372; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]1373; CHECK-NEXT: ret i64 [[HW64]]1374;1375 ; Extract low and high 32 bits1376 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1377 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1378 %x_hi = lshr i64 %x, 32 ; x >> 321379 %y_hi = lshr i64 %y, 32 ; y >> 321380 1381 ; Cross products1382 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1383 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1384 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1385 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1386 1387 ; Add cross terms1388 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1389 1390 ; Carry if overflowed1391 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1392 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321393 1394 ; High 32 bits of low product1395 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321396 1397 ; Low and high 32 bits of cross_sum1398 %cross_sum_lo = and i64 %cross_sum, 42949672951399 call void (...) @llvm.fake.use(i64 %cross_sum_lo)1400 %cross_sum_hi = lshr i64 %cross_sum, 321401 1402 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1403 1404 ; Final result accumulation1405 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1406 %low_accum_hi = lshr i64 %low_accum, 321407 %intermediate_plus_carry = add i64 %intermediate, %carry1408 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1409 1410 ret i64 %hw641411}1412 1413; 'cross_sum_hi' must have single use.1414define i64 @umulh__mul_use__cross_sum_hi(i64 %x, i64 %y) {1415; CHECK-LABEL: define i64 @umulh__mul_use__cross_sum_hi(1416; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {1417; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951418; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951419; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321420; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321421; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]1422; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]1423; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]1424; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1425; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]1426; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]1427; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 01428; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 321429; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672951430; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 321431; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[CROSS_SUM_HI]])1432; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]1433; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]1434; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 321435; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]1436; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]1437; CHECK-NEXT: ret i64 [[HW64]]1438;1439 ; Extract low and high 32 bits1440 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1441 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1442 %x_hi = lshr i64 %x, 32 ; x >> 321443 %y_hi = lshr i64 %y, 32 ; y >> 321444 1445 ; Cross products1446 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1447 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1448 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1449 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1450 1451 ; Add cross terms1452 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1453 1454 ; Carry if overflowed1455 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1456 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321457 1458 ; High 32 bits of low product1459 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321460 1461 ; Low and high 32 bits of cross_sum1462 %cross_sum_lo = and i64 %cross_sum, 42949672951463 %cross_sum_hi = lshr i64 %cross_sum, 321464 call void (...) @llvm.fake.use(i64 %cross_sum_hi)1465 1466 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1467 1468 ; Final result accumulation1469 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1470 %low_accum_hi = lshr i64 %low_accum, 321471 %intermediate_plus_carry = add i64 %intermediate, %carry1472 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1473 1474 ret i64 %hw641475}1476 1477; 'low_accum' has a single use if only doing high part of multiply and 2 uses1478; when doing both low/high parts. Unrelated use here, but still seems1479; profitable.1480define i64 @umulh__mul_use__low_accum(i64 %x, i64 %y) {1481; CHECK-LABEL: define i64 @umulh__mul_use__low_accum(1482; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {1483; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951484; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951485; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321486; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321487; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul i64 [[Y]], [[X_HI]]1488; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul i64 [[Y_HI]], [[X]]1489; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1490; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]1491; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 321492; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672951493; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]1494; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[LOW_ACCUM]])1495; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i1281496; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i1281497; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]1498; CHECK-NEXT: [[TMP4:%.*]] = lshr i128 [[TMP3]], 641499; CHECK-NEXT: [[TMP5:%.*]] = trunc nuw i128 [[TMP4]] to i641500; CHECK-NEXT: ret i64 [[TMP5]]1501;1502 ; Extract low and high 32 bits1503 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1504 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1505 %x_hi = lshr i64 %x, 32 ; x >> 321506 %y_hi = lshr i64 %y, 32 ; y >> 321507 1508 ; Cross products1509 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1510 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1511 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1512 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1513 1514 ; Add cross terms1515 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1516 1517 ; Carry if overflowed1518 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1519 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321520 1521 ; High 32 bits of low product1522 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321523 1524 ; Low and high 32 bits of cross_sum1525 %cross_sum_lo = and i64 %cross_sum, 42949672951526 %cross_sum_hi = lshr i64 %cross_sum, 321527 1528 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1529 call void (...) @llvm.fake.use(i64 %low_accum)1530 1531 ; Final result accumulation1532 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1533 %low_accum_hi = lshr i64 %low_accum, 321534 %intermediate_plus_carry = add i64 %intermediate, %carry1535 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1536 1537 ret i64 %hw641538}1539 1540; 'intermediate' must have single use.1541define i64 @umulh__mul_use__intermediate(i64 %x, i64 %y) {1542; CHECK-LABEL: define i64 @umulh__mul_use__intermediate(1543; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {1544; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951545; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951546; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321547; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321548; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]1549; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]1550; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]1551; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1552; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]1553; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]1554; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 01555; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 321556; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672951557; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 321558; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]1559; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]1560; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[INTERMEDIATE]])1561; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 321562; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]1563; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]1564; CHECK-NEXT: ret i64 [[HW64]]1565;1566 ; Extract low and high 32 bits1567 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1568 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1569 %x_hi = lshr i64 %x, 32 ; x >> 321570 %y_hi = lshr i64 %y, 32 ; y >> 321571 1572 ; Cross products1573 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1574 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1575 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1576 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1577 1578 ; Add cross terms1579 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1580 1581 ; Carry if overflowed1582 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1583 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321584 1585 ; High 32 bits of low product1586 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321587 1588 ; Low and high 32 bits of cross_sum1589 %cross_sum_lo = and i64 %cross_sum, 42949672951590 %cross_sum_hi = lshr i64 %cross_sum, 321591 1592 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1593 1594 ; Final result accumulation1595 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1596 call void (...) @llvm.fake.use(i64 %intermediate)1597 %low_accum_hi = lshr i64 %low_accum, 321598 %intermediate_plus_carry = add i64 %intermediate, %carry1599 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1600 1601 ret i64 %hw641602}1603 1604; 'low_accum_hi' must have single use.1605define i64 @umulh__mul_use__low_accum_hi(i64 %x, i64 %y) {1606; CHECK-LABEL: define i64 @umulh__mul_use__low_accum_hi(1607; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {1608; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951609; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951610; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321611; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321612; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]1613; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]1614; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]1615; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1616; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]1617; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]1618; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 01619; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 321620; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672951621; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 321622; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]1623; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]1624; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 321625; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[LOW_ACCUM_HI]])1626; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]1627; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]1628; CHECK-NEXT: ret i64 [[HW64]]1629;1630 ; Extract low and high 32 bits1631 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1632 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1633 %x_hi = lshr i64 %x, 32 ; x >> 321634 %y_hi = lshr i64 %y, 32 ; y >> 321635 1636 ; Cross products1637 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1638 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1639 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1640 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1641 1642 ; Add cross terms1643 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1644 1645 ; Carry if overflowed1646 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1647 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321648 1649 ; High 32 bits of low product1650 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321651 1652 ; Low and high 32 bits of cross_sum1653 %cross_sum_lo = and i64 %cross_sum, 42949672951654 %cross_sum_hi = lshr i64 %cross_sum, 321655 1656 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1657 1658 ; Final result accumulation1659 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1660 %low_accum_hi = lshr i64 %low_accum, 321661 call void (...) @llvm.fake.use(i64 %low_accum_hi)1662 %intermediate_plus_carry = add i64 %intermediate, %carry1663 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1664 1665 ret i64 %hw641666}1667 1668; 'intermediate_plus_carry' must have single use.1669define i64 @umulh__mul_use__intermediate_plus_carry(i64 %x, i64 %y) {1670; CHECK-LABEL: define i64 @umulh__mul_use__intermediate_plus_carry(1671; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) {1672; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951673; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951674; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321675; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321676; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]1677; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]1678; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]1679; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1680; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]1681; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]1682; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 01683; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 321684; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672951685; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 321686; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]1687; CHECK-NEXT: [[INTERMEDIATE:%.*]] = add nuw i64 [[CROSS_SUM_HI]], [[Y_HI_X_HI]]1688; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 321689; CHECK-NEXT: [[INTERMEDIATE_PLUS_CARRY:%.*]] = add i64 [[INTERMEDIATE]], [[CARRY]]1690; CHECK-NEXT: [[HW64:%.*]] = add i64 [[INTERMEDIATE_PLUS_CARRY]], [[LOW_ACCUM_HI]]1691; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[INTERMEDIATE_PLUS_CARRY]])1692; CHECK-NEXT: ret i64 [[HW64]]1693;1694 ; Extract low and high 32 bits1695 %x_lo = and i64 %x, 4294967295 ; x & 0xffffffff1696 %y_lo = and i64 %y, 4294967295 ; y & 0xffffffff1697 %x_hi = lshr i64 %x, 32 ; x >> 321698 %y_hi = lshr i64 %y, 32 ; y >> 321699 1700 ; Cross products1701 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi ; y_lo * x_hi1702 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi ; y_hi * x_hi1703 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo ; y_hi * x_lo1704 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo ; y_lo * x_lo1705 1706 ; Add cross terms1707 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi ; full 64-bit sum1708 1709 ; Carry if overflowed1710 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1711 %carry = select i1 %carry_out, i64 4294967296, i64 0 ; if overflow, add 1 << 321712 1713 ; High 32 bits of low product1714 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321715 1716 ; Low and high 32 bits of cross_sum1717 %cross_sum_lo = and i64 %cross_sum, 42949672951718 %cross_sum_hi = lshr i64 %cross_sum, 321719 1720 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1721 1722 ; Final result accumulation1723 %intermediate = add nuw i64 %cross_sum_hi, %y_hi_x_hi1724 %low_accum_hi = lshr i64 %low_accum, 321725 %intermediate_plus_carry = add i64 %intermediate, %carry1726 %hw64 = add i64 %intermediate_plus_carry, %low_accum_hi1727 call void (...) @llvm.fake.use(i64 %intermediate_plus_carry)1728 1729 ret i64 %hw641730}1731 1732 1733; 'x_lo' can have multiple uses.1734define void @full_mul_int128__mul_use__x_lo(i64 %x, i64 %y, ptr %p) {1735; CHECK-LABEL: define void @full_mul_int128__mul_use__x_lo(1736; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {1737; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951738; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[X_LO]])1739; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i1281740; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i1281741; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]1742; CHECK-NEXT: [[TMP4:%.*]] = lshr i128 [[TMP3]], 641743; CHECK-NEXT: [[HW64:%.*]] = trunc nuw i128 [[TMP4]] to i641744; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 81745; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 81746; CHECK-NEXT: [[LW64:%.*]] = mul i64 [[X]], [[Y]]1747; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 81748; CHECK-NEXT: ret void1749;1750 %x_lo = and i64 %x, 42949672951751 call void (...) @llvm.fake.use(i64 %x_lo)1752 %y_lo = and i64 %y, 42949672951753 %x_hi = lshr i64 %x, 321754 %y_hi = lshr i64 %y, 321755 1756 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi1757 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi1758 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo1759 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo1760 1761 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi1762 1763 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1764 %carry = select i1 %carry_out, i64 4294967296, i64 01765 1766 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321767 1768 %cross_sum_lo = and i64 %cross_sum, 42949672951769 %cross_sum_hi = lshr i64 %cross_sum, 321770 1771 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1772 1773 %upper_mid = add nuw i64 %y_hi_x_hi, %carry1774 %low_accum_hi = lshr i64 %low_accum, 321775 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi1776 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi1777 1778 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 81779 store i64 %hw64, ptr %hi_ptr, align 81780 1781 %low_accum_shifted = shl i64 %low_accum, 321782 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672951783 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo1784 1785 store i64 %lw64, ptr %p, align 81786 1787 ret void1788}1789 1790; 'y_lo' can have multiple uses.1791define void @full_mul_int128__mul_use__y_lo(i64 %x, i64 %y, ptr %p) {1792; CHECK-LABEL: define void @full_mul_int128__mul_use__y_lo(1793; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {1794; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951795; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_LO]])1796; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i1281797; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i1281798; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]1799; CHECK-NEXT: [[TMP4:%.*]] = lshr i128 [[TMP3]], 641800; CHECK-NEXT: [[HW64:%.*]] = trunc nuw i128 [[TMP4]] to i641801; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 81802; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 81803; CHECK-NEXT: [[LW64:%.*]] = mul i64 [[X]], [[Y]]1804; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 81805; CHECK-NEXT: ret void1806;1807 %x_lo = and i64 %x, 42949672951808 %y_lo = and i64 %y, 42949672951809 call void (...) @llvm.fake.use(i64 %y_lo)1810 %x_hi = lshr i64 %x, 321811 %y_hi = lshr i64 %y, 321812 1813 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi1814 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi1815 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo1816 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo1817 1818 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi1819 1820 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1821 %carry = select i1 %carry_out, i64 4294967296, i64 01822 1823 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321824 1825 %cross_sum_lo = and i64 %cross_sum, 42949672951826 %cross_sum_hi = lshr i64 %cross_sum, 321827 1828 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1829 1830 %upper_mid = add nuw i64 %y_hi_x_hi, %carry1831 %low_accum_hi = lshr i64 %low_accum, 321832 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi1833 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi1834 1835 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 81836 store i64 %hw64, ptr %hi_ptr, align 81837 1838 %low_accum_shifted = shl i64 %low_accum, 321839 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672951840 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo1841 1842 store i64 %lw64, ptr %p, align 81843 1844 ret void1845}1846 1847; 'x_hi' can have multiple uses.1848define void @full_mul_int128__mul_use__x_hi(i64 %x, i64 %y, ptr %p) {1849; CHECK-LABEL: define void @full_mul_int128__mul_use__x_hi(1850; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {1851; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321852; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[X_HI]])1853; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i1281854; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i1281855; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]1856; CHECK-NEXT: [[TMP4:%.*]] = lshr i128 [[TMP3]], 641857; CHECK-NEXT: [[HW64:%.*]] = trunc nuw i128 [[TMP4]] to i641858; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 81859; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 81860; CHECK-NEXT: [[LW64:%.*]] = mul i64 [[X]], [[Y]]1861; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 81862; CHECK-NEXT: ret void1863;1864 %x_lo = and i64 %x, 42949672951865 %y_lo = and i64 %y, 42949672951866 %x_hi = lshr i64 %x, 321867 call void (...) @llvm.fake.use(i64 %x_hi)1868 %y_hi = lshr i64 %y, 321869 1870 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi1871 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi1872 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo1873 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo1874 1875 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi1876 1877 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1878 %carry = select i1 %carry_out, i64 4294967296, i64 01879 1880 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321881 1882 %cross_sum_lo = and i64 %cross_sum, 42949672951883 %cross_sum_hi = lshr i64 %cross_sum, 321884 1885 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1886 1887 %upper_mid = add nuw i64 %y_hi_x_hi, %carry1888 %low_accum_hi = lshr i64 %low_accum, 321889 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi1890 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi1891 1892 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 81893 store i64 %hw64, ptr %hi_ptr, align 81894 1895 %low_accum_shifted = shl i64 %low_accum, 321896 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672951897 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo1898 1899 store i64 %lw64, ptr %p, align 81900 1901 ret void1902}1903 1904; 'y_hi' can have multiple uses.1905define void @full_mul_int128__mul_use__y_hi(i64 %x, i64 %y, ptr %p) {1906; CHECK-LABEL: define void @full_mul_int128__mul_use__y_hi(1907; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {1908; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321909; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_HI]])1910; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i1281911; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i1281912; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]1913; CHECK-NEXT: [[TMP4:%.*]] = lshr i128 [[TMP3]], 641914; CHECK-NEXT: [[HW64:%.*]] = trunc nuw i128 [[TMP4]] to i641915; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 81916; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 81917; CHECK-NEXT: [[LW64:%.*]] = mul i64 [[X]], [[Y]]1918; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 81919; CHECK-NEXT: ret void1920;1921 %x_lo = and i64 %x, 42949672951922 %y_lo = and i64 %y, 42949672951923 %x_hi = lshr i64 %x, 321924 %y_hi = lshr i64 %y, 321925 call void (...) @llvm.fake.use(i64 %y_hi)1926 1927 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi1928 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi1929 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo1930 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo1931 1932 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi1933 1934 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi1935 %carry = select i1 %carry_out, i64 4294967296, i64 01936 1937 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 321938 1939 %cross_sum_lo = and i64 %cross_sum, 42949672951940 %cross_sum_hi = lshr i64 %cross_sum, 321941 1942 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi1943 1944 %upper_mid = add nuw i64 %y_hi_x_hi, %carry1945 %low_accum_hi = lshr i64 %low_accum, 321946 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi1947 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi1948 1949 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 81950 store i64 %hw64, ptr %hi_ptr, align 81951 1952 %low_accum_shifted = shl i64 %low_accum, 321953 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672951954 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo1955 1956 store i64 %lw64, ptr %p, align 81957 1958 ret void1959}1960 1961; 'y_lo_x_hi' must have exactly 2 uses.1962define void @full_mul_int128__mul_use__y_lo_x_hi(i64 %x, i64 %y, ptr %p) {1963; CHECK-LABEL: define void @full_mul_int128__mul_use__y_lo_x_hi(1964; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {1965; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672951966; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672951967; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 321968; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 321969; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]1970; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_LO_X_HI]])1971; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]1972; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]1973; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]1974; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]1975; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]1976; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 01977; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 321978; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672951979; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 321980; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]1981; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]1982; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 321983; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]1984; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]1985; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 81986; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 81987; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 321988; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672951989; CHECK-NEXT: [[LW64:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]1990; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 81991; CHECK-NEXT: ret void1992;1993 %x_lo = and i64 %x, 42949672951994 %y_lo = and i64 %y, 42949672951995 %x_hi = lshr i64 %x, 321996 %y_hi = lshr i64 %y, 321997 1998 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi1999 call void (...) @llvm.fake.use(i64 %y_lo_x_hi)2000 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2001 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2002 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2003 2004 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2005 2006 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2007 %carry = select i1 %carry_out, i64 4294967296, i64 02008 2009 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322010 2011 %cross_sum_lo = and i64 %cross_sum, 42949672952012 %cross_sum_hi = lshr i64 %cross_sum, 322013 2014 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2015 2016 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2017 %low_accum_hi = lshr i64 %low_accum, 322018 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2019 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2020 2021 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82022 store i64 %hw64, ptr %hi_ptr, align 82023 2024 %low_accum_shifted = shl i64 %low_accum, 322025 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952026 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2027 2028 store i64 %lw64, ptr %p, align 82029 2030 ret void2031}2032 2033; 'y_hi_x_hi' must have single use.2034define void @full_mul_int128__mul_use__y_hi_x_hi(i64 %x, i64 %y, ptr %p) {2035; CHECK-LABEL: define void @full_mul_int128__mul_use__y_hi_x_hi(2036; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2037; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952038; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952039; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322040; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322041; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2042; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2043; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_HI_X_HI]])2044; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2045; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2046; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2047; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2048; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02049; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322050; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952051; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322052; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2053; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2054; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322055; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2056; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2057; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82058; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 82059; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322060; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952061; CHECK-NEXT: [[TMP4:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2062; CHECK-NEXT: store i64 [[TMP4]], ptr [[P]], align 82063; CHECK-NEXT: ret void2064;2065 %x_lo = and i64 %x, 42949672952066 %y_lo = and i64 %y, 42949672952067 %x_hi = lshr i64 %x, 322068 %y_hi = lshr i64 %y, 322069 2070 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2071 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2072 call void (...) @llvm.fake.use(i64 %y_hi_x_hi)2073 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2074 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2075 2076 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2077 2078 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2079 %carry = select i1 %carry_out, i64 4294967296, i64 02080 2081 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322082 2083 %cross_sum_lo = and i64 %cross_sum, 42949672952084 %cross_sum_hi = lshr i64 %cross_sum, 322085 2086 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2087 2088 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2089 %low_accum_hi = lshr i64 %low_accum, 322090 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2091 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2092 2093 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82094 store i64 %hw64, ptr %hi_ptr, align 82095 2096 %low_accum_shifted = shl i64 %low_accum, 322097 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952098 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2099 2100 store i64 %lw64, ptr %p, align 82101 2102 ret void2103}2104 2105; 'y_hi_x_lo' must have single use.2106define void @full_mul_int128__mul_use__y_hi_x_lo(i64 %x, i64 %y, ptr %p) {2107; CHECK-LABEL: define void @full_mul_int128__mul_use__y_hi_x_lo(2108; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2109; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952110; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952111; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322112; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322113; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2114; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2115; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2116; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_HI_X_LO]])2117; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2118; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2119; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2120; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02121; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322122; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952123; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322124; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2125; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2126; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322127; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2128; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2129; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82130; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 82131; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322132; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952133; CHECK-NEXT: [[LW64:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2134; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 82135; CHECK-NEXT: ret void2136;2137 %x_lo = and i64 %x, 42949672952138 %y_lo = and i64 %y, 42949672952139 %x_hi = lshr i64 %x, 322140 %y_hi = lshr i64 %y, 322141 2142 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2143 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2144 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2145 call void (...) @llvm.fake.use(i64 %y_hi_x_lo)2146 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2147 2148 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2149 2150 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2151 %carry = select i1 %carry_out, i64 4294967296, i64 02152 2153 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322154 2155 %cross_sum_lo = and i64 %cross_sum, 42949672952156 %cross_sum_hi = lshr i64 %cross_sum, 322157 2158 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2159 2160 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2161 %low_accum_hi = lshr i64 %low_accum, 322162 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2163 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2164 2165 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82166 store i64 %hw64, ptr %hi_ptr, align 82167 2168 %low_accum_shifted = shl i64 %low_accum, 322169 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952170 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2171 2172 store i64 %lw64, ptr %p, align 82173 2174 ret void2175}2176 2177; 'y_lo_x_lo' we allow multiple uses on y_lo_x_lo.2178; TODO does not simplify like it should?2179define void @full_mul_int128__mul_use__y_lo_x_lo(i64 %x, i64 %y, ptr %p) {2180; CHECK-LABEL: define void @full_mul_int128__mul_use__y_lo_x_lo(2181; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2182; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952183; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952184; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322185; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322186; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = mul i64 [[Y]], [[X_HI]]2187; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = mul i64 [[Y_HI]], [[X]]2188; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2189; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_LO_X_LO]])2190; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2191; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i1282192; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i1282193; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]2194; CHECK-NEXT: [[TMP4:%.*]] = lshr i128 [[TMP3]], 642195; CHECK-NEXT: [[TMP5:%.*]] = trunc nuw i128 [[TMP4]] to i642196; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82197; CHECK-NEXT: store i64 [[TMP5]], ptr [[HI_PTR]], align 82198; CHECK-NEXT: [[LOW_ACCUM1:%.*]] = shl i64 [[TMP6]], 322199; CHECK-NEXT: [[LW64:%.*]] = add i64 [[Y_LO_X_LO]], [[LOW_ACCUM1]]2200; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 82201; CHECK-NEXT: ret void2202;2203 %x_lo = and i64 %x, 42949672952204 %y_lo = and i64 %y, 42949672952205 %x_hi = lshr i64 %x, 322206 %y_hi = lshr i64 %y, 322207 2208 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2209 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2210 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2211 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2212 call void (...) @llvm.fake.use(i64 %y_lo_x_lo)2213 2214 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2215 2216 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2217 %carry = select i1 %carry_out, i64 4294967296, i64 02218 2219 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322220 2221 %cross_sum_lo = and i64 %cross_sum, 42949672952222 %cross_sum_hi = lshr i64 %cross_sum, 322223 2224 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2225 2226 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2227 %low_accum_hi = lshr i64 %low_accum, 322228 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2229 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2230 2231 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82232 store i64 %hw64, ptr %hi_ptr, align 82233 2234 %low_accum_shifted = shl i64 %low_accum, 322235 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952236 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2237 2238 store i64 %lw64, ptr %p, align 82239 2240 ret void2241}2242 2243; 'cross_sum' must have no more than 3 uses.2244define void @full_mul_int128__mul_use__cross_sum(i64 %x, i64 %y, ptr %p) {2245; CHECK-LABEL: define void @full_mul_int128__mul_use__cross_sum(2246; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2247; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952248; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952249; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322250; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322251; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2252; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2253; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2254; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2255; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2256; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[CROSS_SUM]])2257; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2258; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02259; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322260; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952261; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322262; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2263; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2264; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322265; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2266; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2267; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82268; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 82269; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322270; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952271; CHECK-NEXT: [[LW64:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2272; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 82273; CHECK-NEXT: ret void2274;2275 %x_lo = and i64 %x, 42949672952276 %y_lo = and i64 %y, 42949672952277 %x_hi = lshr i64 %x, 322278 %y_hi = lshr i64 %y, 322279 2280 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2281 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2282 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2283 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2284 2285 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2286 call void (...) @llvm.fake.use(i64 %cross_sum)2287 2288 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2289 %carry = select i1 %carry_out, i64 4294967296, i64 02290 2291 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322292 2293 %cross_sum_lo = and i64 %cross_sum, 42949672952294 %cross_sum_hi = lshr i64 %cross_sum, 322295 2296 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2297 2298 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2299 %low_accum_hi = lshr i64 %low_accum, 322300 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2301 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2302 2303 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82304 store i64 %hw64, ptr %hi_ptr, align 82305 2306 %low_accum_shifted = shl i64 %low_accum, 322307 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952308 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2309 2310 store i64 %lw64, ptr %p, align 82311 2312 ret void2313}2314 2315; 'carry_out' must have single use.2316define void @full_mul_int128__mul_use__carry_out(i64 %x, i64 %y, ptr %p) {2317; CHECK-LABEL: define void @full_mul_int128__mul_use__carry_out(2318; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2319; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952320; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952321; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322322; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322323; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2324; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2325; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2326; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2327; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2328; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2329; CHECK-NEXT: call void (...) @llvm.fake.use(i1 [[CARRY_OUT]])2330; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02331; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322332; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952333; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322334; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2335; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2336; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322337; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2338; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2339; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82340; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 82341; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322342; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952343; CHECK-NEXT: [[TMP4:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2344; CHECK-NEXT: store i64 [[TMP4]], ptr [[P]], align 82345; CHECK-NEXT: ret void2346;2347 %x_lo = and i64 %x, 42949672952348 %y_lo = and i64 %y, 42949672952349 %x_hi = lshr i64 %x, 322350 %y_hi = lshr i64 %y, 322351 2352 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2353 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2354 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2355 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2356 2357 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2358 2359 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2360 call void (...) @llvm.fake.use(i1 %carry_out)2361 %carry = select i1 %carry_out, i64 4294967296, i64 02362 2363 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322364 2365 %cross_sum_lo = and i64 %cross_sum, 42949672952366 %cross_sum_hi = lshr i64 %cross_sum, 322367 2368 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2369 2370 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2371 %low_accum_hi = lshr i64 %low_accum, 322372 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2373 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2374 2375 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82376 store i64 %hw64, ptr %hi_ptr, align 82377 2378 %low_accum_shifted = shl i64 %low_accum, 322379 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952380 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2381 2382 store i64 %lw64, ptr %p, align 82383 2384 ret void2385}2386 2387; 'carry' must have single use.2388define void @full_mul_int128__mul_use__carry(i64 %x, i64 %y, ptr %p) {2389; CHECK-LABEL: define void @full_mul_int128__mul_use__carry(2390; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2391; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952392; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952393; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322394; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322395; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2396; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2397; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2398; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2399; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2400; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2401; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02402; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[CARRY]])2403; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322404; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952405; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322406; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2407; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2408; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322409; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2410; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2411; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82412; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 82413; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322414; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952415; CHECK-NEXT: [[TMP4:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2416; CHECK-NEXT: store i64 [[TMP4]], ptr [[P]], align 82417; CHECK-NEXT: ret void2418;2419 %x_lo = and i64 %x, 42949672952420 %y_lo = and i64 %y, 42949672952421 %x_hi = lshr i64 %x, 322422 %y_hi = lshr i64 %y, 322423 2424 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2425 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2426 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2427 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2428 2429 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2430 2431 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2432 %carry = select i1 %carry_out, i64 4294967296, i64 02433 call void (...) @llvm.fake.use(i64 %carry)2434 2435 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322436 2437 %cross_sum_lo = and i64 %cross_sum, 42949672952438 %cross_sum_hi = lshr i64 %cross_sum, 322439 2440 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2441 2442 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2443 %low_accum_hi = lshr i64 %low_accum, 322444 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2445 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2446 2447 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82448 store i64 %hw64, ptr %hi_ptr, align 82449 2450 %low_accum_shifted = shl i64 %low_accum, 322451 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952452 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2453 2454 store i64 %lw64, ptr %p, align 82455 2456 ret void2457}2458 2459; 'y_lo_x_lo_hi' must have single use.2460define void @full_mul_int128__mul_use__y_lo_x_lo_hi(i64 %x, i64 %y, ptr %p) {2461; CHECK-LABEL: define void @full_mul_int128__mul_use__y_lo_x_lo_hi(2462; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2463; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952464; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952465; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322466; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322467; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2468; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2469; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2470; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2471; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2472; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2473; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02474; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322475; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[Y_LO_X_LO_HI]])2476; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952477; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322478; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2479; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2480; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322481; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2482; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2483; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82484; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 82485; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322486; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952487; CHECK-NEXT: [[LW64:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2488; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 82489; CHECK-NEXT: ret void2490;2491 %x_lo = and i64 %x, 42949672952492 %y_lo = and i64 %y, 42949672952493 %x_hi = lshr i64 %x, 322494 %y_hi = lshr i64 %y, 322495 2496 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2497 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2498 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2499 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2500 2501 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2502 2503 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2504 %carry = select i1 %carry_out, i64 4294967296, i64 02505 2506 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322507 call void (...) @llvm.fake.use(i64 %y_lo_x_lo_hi)2508 2509 %cross_sum_lo = and i64 %cross_sum, 42949672952510 %cross_sum_hi = lshr i64 %cross_sum, 322511 2512 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2513 2514 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2515 %low_accum_hi = lshr i64 %low_accum, 322516 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2517 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2518 2519 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82520 store i64 %hw64, ptr %hi_ptr, align 82521 2522 %low_accum_shifted = shl i64 %low_accum, 322523 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952524 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2525 2526 store i64 %lw64, ptr %p, align 82527 2528 ret void2529}2530 2531; 'cross_sum_lo' must have single use.2532define void @full_mul_int128__mul_use__cross_sum_lo(i64 %x, i64 %y, ptr %p) {2533; CHECK-LABEL: define void @full_mul_int128__mul_use__cross_sum_lo(2534; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2535; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952536; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952537; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322538; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322539; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2540; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2541; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2542; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2543; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2544; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2545; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02546; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322547; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952548; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[CROSS_SUM_LO]])2549; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322550; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2551; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2552; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322553; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2554; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2555; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82556; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 82557; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322558; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952559; CHECK-NEXT: [[LW64:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2560; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 82561; CHECK-NEXT: ret void2562;2563 %x_lo = and i64 %x, 42949672952564 %y_lo = and i64 %y, 42949672952565 %x_hi = lshr i64 %x, 322566 %y_hi = lshr i64 %y, 322567 2568 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2569 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2570 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2571 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2572 2573 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2574 2575 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2576 %carry = select i1 %carry_out, i64 4294967296, i64 02577 2578 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322579 2580 %cross_sum_lo = and i64 %cross_sum, 42949672952581 call void (...) @llvm.fake.use(i64 %cross_sum_lo)2582 %cross_sum_hi = lshr i64 %cross_sum, 322583 2584 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2585 2586 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2587 %low_accum_hi = lshr i64 %low_accum, 322588 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2589 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2590 2591 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82592 store i64 %hw64, ptr %hi_ptr, align 82593 2594 %low_accum_shifted = shl i64 %low_accum, 322595 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952596 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2597 2598 store i64 %lw64, ptr %p, align 82599 2600 ret void2601}2602 2603; 'cross_sum_hi' must have single use.2604define void @full_mul_int128__mul_use__cross_sum_hi(i64 %x, i64 %y, ptr %p) {2605; CHECK-LABEL: define void @full_mul_int128__mul_use__cross_sum_hi(2606; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2607; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952608; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952609; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322610; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322611; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2612; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2613; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2614; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2615; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2616; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2617; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02618; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322619; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952620; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322621; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[CROSS_SUM_HI]])2622; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2623; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2624; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322625; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2626; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2627; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82628; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 82629; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322630; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952631; CHECK-NEXT: [[TMP4:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2632; CHECK-NEXT: store i64 [[TMP4]], ptr [[P]], align 82633; CHECK-NEXT: ret void2634;2635 %x_lo = and i64 %x, 42949672952636 %y_lo = and i64 %y, 42949672952637 %x_hi = lshr i64 %x, 322638 %y_hi = lshr i64 %y, 322639 2640 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2641 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2642 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2643 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2644 2645 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2646 2647 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2648 %carry = select i1 %carry_out, i64 4294967296, i64 02649 2650 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322651 2652 %cross_sum_lo = and i64 %cross_sum, 42949672952653 %cross_sum_hi = lshr i64 %cross_sum, 322654 call void (...) @llvm.fake.use(i64 %cross_sum_hi)2655 2656 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2657 2658 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2659 %low_accum_hi = lshr i64 %low_accum, 322660 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2661 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2662 2663 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82664 store i64 %hw64, ptr %hi_ptr, align 82665 2666 %low_accum_shifted = shl i64 %low_accum, 322667 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952668 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2669 2670 store i64 %lw64, ptr %p, align 82671 2672 ret void2673}2674 2675; 'low_accum' must have exactly 2 uses if doing high multiply.2676define void @full_mul_int128__mul_use__low_accum(i64 %x, i64 %y, ptr %p) {2677; CHECK-LABEL: define void @full_mul_int128__mul_use__low_accum(2678; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2679; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952680; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952681; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322682; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322683; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2684; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2685; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2686; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2687; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2688; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2689; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02690; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322691; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952692; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322693; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2694; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[LOW_ACCUM]])2695; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2696; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322697; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2698; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2699; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82700; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 82701; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322702; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952703; CHECK-NEXT: [[LW64:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2704; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 82705; CHECK-NEXT: ret void2706;2707 %x_lo = and i64 %x, 42949672952708 %y_lo = and i64 %y, 42949672952709 %x_hi = lshr i64 %x, 322710 %y_hi = lshr i64 %y, 322711 2712 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2713 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2714 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2715 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2716 2717 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2718 2719 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2720 %carry = select i1 %carry_out, i64 4294967296, i64 02721 2722 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322723 2724 %cross_sum_lo = and i64 %cross_sum, 42949672952725 %cross_sum_hi = lshr i64 %cross_sum, 322726 2727 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2728 call void (...) @llvm.fake.use(i64 %low_accum)2729 2730 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2731 %low_accum_hi = lshr i64 %low_accum, 322732 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2733 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2734 2735 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82736 store i64 %hw64, ptr %hi_ptr, align 82737 2738 %low_accum_shifted = shl i64 %low_accum, 322739 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952740 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2741 2742 store i64 %lw64, ptr %p, align 82743 2744 ret void2745}2746 2747; 'upper_mid' must have single use.2748define void @full_mul_int128__mul_use__upper_mid(i64 %x, i64 %y, ptr %p) {2749; CHECK-LABEL: define void @full_mul_int128__mul_use__upper_mid(2750; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2751; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952752; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952753; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322754; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322755; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2756; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2757; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2758; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2759; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2760; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2761; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02762; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322763; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952764; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322765; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2766; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2767; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[UPPER_MID]])2768; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322769; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2770; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2771; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82772; CHECK-NEXT: store i64 [[TMP5]], ptr [[HI_PTR]], align 82773; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322774; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952775; CHECK-NEXT: [[TMP9:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2776; CHECK-NEXT: store i64 [[TMP9]], ptr [[P]], align 82777; CHECK-NEXT: ret void2778;2779 %x_lo = and i64 %x, 42949672952780 %y_lo = and i64 %y, 42949672952781 %x_hi = lshr i64 %x, 322782 %y_hi = lshr i64 %y, 322783 2784 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2785 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2786 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2787 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2788 2789 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2790 2791 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2792 %carry = select i1 %carry_out, i64 4294967296, i64 02793 2794 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322795 2796 %cross_sum_lo = and i64 %cross_sum, 42949672952797 %cross_sum_hi = lshr i64 %cross_sum, 322798 2799 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2800 2801 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2802 call void (...) @llvm.fake.use(i64 %upper_mid)2803 %low_accum_hi = lshr i64 %low_accum, 322804 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2805 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2806 2807 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82808 store i64 %hw64, ptr %hi_ptr, align 82809 2810 %low_accum_shifted = shl i64 %low_accum, 322811 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952812 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2813 2814 store i64 %lw64, ptr %p, align 82815 2816 ret void2817}2818 2819; 'low_accum_hi' must have single use.2820define void @full_mul_int128__mul_use__low_accum_hi(i64 %x, i64 %y, ptr %p) {2821; CHECK-LABEL: define void @full_mul_int128__mul_use__low_accum_hi(2822; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2823; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952824; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952825; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322826; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322827; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2828; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2829; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2830; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2831; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2832; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2833; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02834; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322835; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952836; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322837; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2838; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2839; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322840; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[LOW_ACCUM_HI]])2841; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2842; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2843; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82844; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 82845; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322846; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952847; CHECK-NEXT: [[TMP4:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2848; CHECK-NEXT: store i64 [[TMP4]], ptr [[P]], align 82849; CHECK-NEXT: ret void2850;2851 %x_lo = and i64 %x, 42949672952852 %y_lo = and i64 %y, 42949672952853 %x_hi = lshr i64 %x, 322854 %y_hi = lshr i64 %y, 322855 2856 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2857 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2858 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2859 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2860 2861 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2862 2863 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2864 %carry = select i1 %carry_out, i64 4294967296, i64 02865 2866 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322867 2868 %cross_sum_lo = and i64 %cross_sum, 42949672952869 %cross_sum_hi = lshr i64 %cross_sum, 322870 2871 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2872 2873 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2874 %low_accum_hi = lshr i64 %low_accum, 322875 call void (...) @llvm.fake.use(i64 %low_accum_hi)2876 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2877 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2878 2879 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82880 store i64 %hw64, ptr %hi_ptr, align 82881 2882 %low_accum_shifted = shl i64 %low_accum, 322883 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952884 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2885 2886 store i64 %lw64, ptr %p, align 82887 2888 ret void2889}2890 2891; 'upper_mid_with_cross' must have single use.2892define void @full_mul_int128__mul_use__upper_mid_with_cross(i64 %x, i64 %y, ptr %p) {2893; CHECK-LABEL: define void @full_mul_int128__mul_use__upper_mid_with_cross(2894; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2895; CHECK-NEXT: [[X_LO:%.*]] = and i64 [[X]], 42949672952896; CHECK-NEXT: [[Y_LO:%.*]] = and i64 [[Y]], 42949672952897; CHECK-NEXT: [[X_HI:%.*]] = lshr i64 [[X]], 322898; CHECK-NEXT: [[Y_HI:%.*]] = lshr i64 [[Y]], 322899; CHECK-NEXT: [[Y_LO_X_HI:%.*]] = mul nuw i64 [[Y_LO]], [[X_HI]]2900; CHECK-NEXT: [[Y_HI_X_HI:%.*]] = mul nuw i64 [[Y_HI]], [[X_HI]]2901; CHECK-NEXT: [[Y_HI_X_LO:%.*]] = mul nuw i64 [[Y_HI]], [[X_LO]]2902; CHECK-NEXT: [[Y_LO_X_LO:%.*]] = mul nuw i64 [[Y_LO]], [[X_LO]]2903; CHECK-NEXT: [[CROSS_SUM:%.*]] = add i64 [[Y_HI_X_LO]], [[Y_LO_X_HI]]2904; CHECK-NEXT: [[CARRY_OUT:%.*]] = icmp ult i64 [[CROSS_SUM]], [[Y_LO_X_HI]]2905; CHECK-NEXT: [[CARRY:%.*]] = select i1 [[CARRY_OUT]], i64 4294967296, i64 02906; CHECK-NEXT: [[Y_LO_X_LO_HI:%.*]] = lshr i64 [[Y_LO_X_LO]], 322907; CHECK-NEXT: [[CROSS_SUM_LO:%.*]] = and i64 [[CROSS_SUM]], 42949672952908; CHECK-NEXT: [[CROSS_SUM_HI:%.*]] = lshr i64 [[CROSS_SUM]], 322909; CHECK-NEXT: [[LOW_ACCUM:%.*]] = add nuw nsw i64 [[CROSS_SUM_LO]], [[Y_LO_X_LO_HI]]2910; CHECK-NEXT: [[UPPER_MID:%.*]] = add nuw i64 [[Y_HI_X_HI]], [[CARRY]]2911; CHECK-NEXT: [[LOW_ACCUM_HI:%.*]] = lshr i64 [[LOW_ACCUM]], 322912; CHECK-NEXT: [[UPPER_MID_WITH_CROSS:%.*]] = add i64 [[UPPER_MID]], [[CROSS_SUM_HI]]2913; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[LOW_ACCUM_HI]])2914; CHECK-NEXT: [[HW64:%.*]] = add i64 [[UPPER_MID_WITH_CROSS]], [[LOW_ACCUM_HI]]2915; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82916; CHECK-NEXT: store i64 [[HW64]], ptr [[HI_PTR]], align 82917; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = shl i64 [[LOW_ACCUM]], 322918; CHECK-NEXT: [[Y_LO_X_LO_LO:%.*]] = and i64 [[Y_LO_X_LO]], 42949672952919; CHECK-NEXT: [[TMP4:%.*]] = or disjoint i64 [[LOW_ACCUM_SHIFTED]], [[Y_LO_X_LO_LO]]2920; CHECK-NEXT: store i64 [[TMP4]], ptr [[P]], align 82921; CHECK-NEXT: ret void2922;2923 %x_lo = and i64 %x, 42949672952924 %y_lo = and i64 %y, 42949672952925 %x_hi = lshr i64 %x, 322926 %y_hi = lshr i64 %y, 322927 2928 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2929 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2930 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2931 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2932 2933 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2934 2935 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2936 %carry = select i1 %carry_out, i64 4294967296, i64 02937 2938 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322939 2940 %cross_sum_lo = and i64 %cross_sum, 42949672952941 %cross_sum_hi = lshr i64 %cross_sum, 322942 2943 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi2944 2945 %upper_mid = add nuw i64 %y_hi_x_hi, %carry2946 %low_accum_hi = lshr i64 %low_accum, 322947 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi2948 call void (...) @llvm.fake.use(i64 %low_accum_hi)2949 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi2950 2951 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 82952 store i64 %hw64, ptr %hi_ptr, align 82953 2954 %low_accum_shifted = shl i64 %low_accum, 322955 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672952956 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo2957 2958 store i64 %lw64, ptr %p, align 82959 2960 ret void2961}2962 2963; 'low_accum_shifted' can have multiple uses.2964define void @full_mul_int128__mul_use__low_accum_shifted(i64 %x, i64 %y, ptr %p) {2965; CHECK-LABEL: define void @full_mul_int128__mul_use__low_accum_shifted(2966; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]], ptr [[P:%.*]]) {2967; CHECK-NEXT: [[TMP1:%.*]] = zext i64 [[X]] to i1282968; CHECK-NEXT: [[TMP2:%.*]] = zext i64 [[Y]] to i1282969; CHECK-NEXT: [[TMP3:%.*]] = mul nuw i128 [[TMP1]], [[TMP2]]2970; CHECK-NEXT: [[TMP4:%.*]] = lshr i128 [[TMP3]], 642971; CHECK-NEXT: [[TMP5:%.*]] = trunc nuw i128 [[TMP4]] to i642972; CHECK-NEXT: [[HI_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 82973; CHECK-NEXT: store i64 [[TMP5]], ptr [[HI_PTR]], align 82974; CHECK-NEXT: [[LW64:%.*]] = mul i64 [[X]], [[Y]]2975; CHECK-NEXT: [[LOW_ACCUM_SHIFTED:%.*]] = and i64 [[LW64]], -42949672962976; CHECK-NEXT: call void (...) @llvm.fake.use(i64 [[LOW_ACCUM_SHIFTED]])2977; CHECK-NEXT: store i64 [[LW64]], ptr [[P]], align 82978; CHECK-NEXT: ret void2979;2980 %x_lo = and i64 %x, 42949672952981 %y_lo = and i64 %y, 42949672952982 %x_hi = lshr i64 %x, 322983 %y_hi = lshr i64 %y, 322984 2985 %y_lo_x_hi = mul nuw i64 %y_lo, %x_hi2986 %y_hi_x_hi = mul nuw i64 %y_hi, %x_hi2987 %y_hi_x_lo = mul nuw i64 %y_hi, %x_lo2988 %y_lo_x_lo = mul nuw i64 %y_lo, %x_lo2989 2990 %cross_sum = add i64 %y_hi_x_lo, %y_lo_x_hi2991 2992 %carry_out = icmp ult i64 %cross_sum, %y_lo_x_hi2993 %carry = select i1 %carry_out, i64 4294967296, i64 02994 2995 %y_lo_x_lo_hi = lshr i64 %y_lo_x_lo, 322996 2997 %cross_sum_lo = and i64 %cross_sum, 42949672952998 %cross_sum_hi = lshr i64 %cross_sum, 322999 3000 %low_accum = add nuw nsw i64 %cross_sum_lo, %y_lo_x_lo_hi3001 3002 %upper_mid = add nuw i64 %y_hi_x_hi, %carry3003 %low_accum_hi = lshr i64 %low_accum, 323004 %upper_mid_with_cross = add i64 %upper_mid, %cross_sum_hi3005 %hw64 = add i64 %upper_mid_with_cross, %low_accum_hi3006 3007 %hi_ptr = getelementptr inbounds i8, ptr %p, i64 83008 store i64 %hw64, ptr %hi_ptr, align 83009 3010 %low_accum_shifted = shl i64 %low_accum, 323011 call void (...) @llvm.fake.use(i64 %low_accum_shifted)3012 %y_lo_x_lo_lo = and i64 %y_lo_x_lo, 42949672953013 %lw64 = or disjoint i64 %low_accum_shifted, %y_lo_x_lo_lo3014 3015 store i64 %lw64, ptr %p, align 83016 3017 ret void3018}3019 3020