; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=instcombine -S | FileCheck %s

target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
target triple = "i386-unknown-linux-gnu"

define { i64, i64 } @mul_full_64(i64 %x, i64 %y) {
; CHECK-LABEL: @mul_full_64(
; CHECK-NEXT:    [[XL:%.*]] = and i64 [[X:%.*]], 4294967295
; CHECK-NEXT:    [[XH:%.*]] = lshr i64 [[X]], 32
; CHECK-NEXT:    [[YL:%.*]] = and i64 [[Y:%.*]], 4294967295
; CHECK-NEXT:    [[YH:%.*]] = lshr i64 [[Y]], 32
; CHECK-NEXT:    [[T0:%.*]] = mul nuw i64 [[YL]], [[XL]]
; CHECK-NEXT:    [[T1:%.*]] = mul nuw i64 [[YL]], [[XH]]
; CHECK-NEXT:    [[T2:%.*]] = mul nuw i64 [[YH]], [[XL]]
; CHECK-NEXT:    [[T3:%.*]] = mul nuw i64 [[YH]], [[XH]]
; CHECK-NEXT:    [[T0L:%.*]] = and i64 [[T0]], 4294967295
; CHECK-NEXT:    [[T0H:%.*]] = lshr i64 [[T0]], 32
; CHECK-NEXT:    [[U0:%.*]] = add i64 [[T0H]], [[T1]]
; CHECK-NEXT:    [[U0L:%.*]] = and i64 [[U0]], 4294967295
; CHECK-NEXT:    [[U0H:%.*]] = lshr i64 [[U0]], 32
; CHECK-NEXT:    [[U1:%.*]] = add i64 [[U0L]], [[T2]]
; CHECK-NEXT:    [[U1LS:%.*]] = shl i64 [[U1]], 32
; CHECK-NEXT:    [[U1H:%.*]] = lshr i64 [[U1]], 32
; CHECK-NEXT:    [[U2:%.*]] = add i64 [[U0H]], [[T3]]
; CHECK-NEXT:    [[LO:%.*]] = or i64 [[U1LS]], [[T0L]]
; CHECK-NEXT:    [[HI:%.*]] = add i64 [[U2]], [[U1H]]
; CHECK-NEXT:    [[RES_LO:%.*]] = insertvalue { i64, i64 } undef, i64 [[LO]], 0
; CHECK-NEXT:    [[RES:%.*]] = insertvalue { i64, i64 } [[RES_LO]], i64 [[HI]], 1
; CHECK-NEXT:    ret { i64, i64 } [[RES]]
;
  %xl = and i64 %x, 4294967295
  %xh = lshr i64 %x, 32
  %yl = and i64 %y, 4294967295
  %yh = lshr i64 %y, 32

  %t0 = mul nuw i64 %yl, %xl
  %t1 = mul nuw i64 %yl, %xh
  %t2 = mul nuw i64 %yh, %xl
  %t3 = mul nuw i64 %yh, %xh

  %t0l = and i64 %t0, 4294967295
  %t0h = lshr i64 %t0, 32

  %u0 = add i64 %t0h, %t1
  %u0l = and i64 %u0, 4294967295
  %u0h = lshr i64 %u0, 32

  %u1 = add i64 %u0l, %t2
  %u1ls = shl i64 %u1, 32
  %u1h = lshr i64 %u1, 32

  %u2 = add i64 %u0h, %t3

  %lo = or i64 %u1ls, %t0l
  %hi = add i64 %u2, %u1h

  %res_lo = insertvalue { i64, i64 } undef, i64 %lo, 0
  %res = insertvalue { i64, i64 } %res_lo, i64 %hi, 1
  ret { i64, i64 } %res
}

define { i32, i32 } @mul_full_32(i32 %x, i32 %y) {
; CHECK-LABEL: @mul_full_32(
; CHECK-NEXT:    [[XL:%.*]] = and i32 [[X:%.*]], 65535
; CHECK-NEXT:    [[XH:%.*]] = lshr i32 [[X]], 16
; CHECK-NEXT:    [[YL:%.*]] = and i32 [[Y:%.*]], 65535
; CHECK-NEXT:    [[YH:%.*]] = lshr i32 [[Y]], 16
; CHECK-NEXT:    [[T0:%.*]] = mul nuw i32 [[YL]], [[XL]]
; CHECK-NEXT:    [[T1:%.*]] = mul nuw i32 [[YL]], [[XH]]
; CHECK-NEXT:    [[T2:%.*]] = mul nuw i32 [[YH]], [[XL]]
; CHECK-NEXT:    [[T3:%.*]] = mul nuw i32 [[YH]], [[XH]]
; CHECK-NEXT:    [[T0L:%.*]] = and i32 [[T0]], 65535
; CHECK-NEXT:    [[T0H:%.*]] = lshr i32 [[T0]], 16
; CHECK-NEXT:    [[U0:%.*]] = add i32 [[T0H]], [[T1]]
; CHECK-NEXT:    [[U0L:%.*]] = and i32 [[U0]], 65535
; CHECK-NEXT:    [[U0H:%.*]] = lshr i32 [[U0]], 16
; CHECK-NEXT:    [[U1:%.*]] = add i32 [[U0L]], [[T2]]
; CHECK-NEXT:    [[U1LS:%.*]] = shl i32 [[U1]], 16
; CHECK-NEXT:    [[U1H:%.*]] = lshr i32 [[U1]], 16
; CHECK-NEXT:    [[U2:%.*]] = add i32 [[U0H]], [[T3]]
; CHECK-NEXT:    [[LO:%.*]] = or i32 [[U1LS]], [[T0L]]
; CHECK-NEXT:    [[HI:%.*]] = add i32 [[U2]], [[U1H]]
; CHECK-NEXT:    [[RES_LO:%.*]] = insertvalue { i32, i32 } undef, i32 [[LO]], 0
; CHECK-NEXT:    [[RES:%.*]] = insertvalue { i32, i32 } [[RES_LO]], i32 [[HI]], 1
; CHECK-NEXT:    ret { i32, i32 } [[RES]]
;
  %xl = and i32 %x, 65535
  %xh = lshr i32 %x, 16
  %yl = and i32 %y, 65535
  %yh = lshr i32 %y, 16

  %t0 = mul nuw i32 %yl, %xl
  %t1 = mul nuw i32 %yl, %xh
  %t2 = mul nuw i32 %yh, %xl
  %t3 = mul nuw i32 %yh, %xh

  %t0l = and i32 %t0, 65535
  %t0h = lshr i32 %t0, 16

  %u0 = add i32 %t0h, %t1
  %u0l = and i32 %u0, 65535
  %u0h = lshr i32 %u0, 16

  %u1 = add i32 %u0l, %t2
  %u1ls = shl i32 %u1, 16
  %u1h = lshr i32 %u1, 16

  %u2 = add i32 %u0h, %t3

  %lo = or i32 %u1ls, %t0l
  %hi = add i32 %u2, %u1h

  %res_lo = insertvalue { i32, i32 } undef, i32 %lo, 0
  %res = insertvalue { i32, i32 } %res_lo, i32 %hi, 1
  ret { i32, i32 } %res
}