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

; Tests involving repeated operations on the same value.

define i8 @nilpotent(i8 %x) {
; CHECK-LABEL: define i8 @nilpotent(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    ret i8 0
;
  %tmp = xor i8 %x, %x
  ret i8 %tmp
}

define i2 @idempotent(i2 %x) {
; CHECK-LABEL: define i2 @idempotent(
; CHECK-SAME: i2 [[X:%.*]]) {
; CHECK-NEXT:    ret i2 [[X]]
;
  %tmp1 = and i2 %x, %x
  %tmp2 = and i2 %tmp1, %x
  %tmp3 = and i2 %tmp2, %x
  ret i2 %tmp3
}

define i2 @add(i2 %x) {
; CHECK-LABEL: define i2 @add(
; CHECK-SAME: i2 [[X:%.*]]) {
; CHECK-NEXT:    ret i2 0
;
  %tmp1 = add i2 %x, %x
  %tmp2 = add i2 %tmp1, %x
  %tmp3 = add i2 %tmp2, %x
  ret i2 %tmp3
}

define i2 @cst_add() {
; CHECK-LABEL: define i2 @cst_add() {
; CHECK-NEXT:    ret i2 -1
;
  %tmp1 = add i2 1, 1
  %tmp2 = add i2 %tmp1, 1
  ret i2 %tmp2
}

define i8 @cst_mul() {
; CHECK-LABEL: define i8 @cst_mul() {
; CHECK-NEXT:    ret i8 -13
;
  %tmp1 = mul i8 3, 3
  %tmp2 = mul i8 %tmp1, 3
  %tmp3 = mul i8 %tmp2, 3
  %tmp4 = mul i8 %tmp3, 3
  ret i8 %tmp4
}

define i3 @foo3x5(i3 %x) {
; Can be done with two multiplies.
; CHECK-LABEL: define i3 @foo3x5(
; CHECK-SAME: i3 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP3:%.*]] = mul i3 [[X]], [[X]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i3 [[TMP3]], [[X]]
; CHECK-NEXT:    [[TMP5:%.*]] = mul i3 [[TMP4]], [[TMP3]]
; CHECK-NEXT:    ret i3 [[TMP5]]
;
  %tmp1 = mul i3 %x, %x
  %tmp2 = mul i3 %tmp1, %x
  %tmp3 = mul i3 %tmp2, %x
  %tmp4 = mul i3 %tmp3, %x
  ret i3 %tmp4
}

define i3 @foo3x5_nsw(i3 %x) {
; Can be done with two multiplies.
; CHECK-LABEL: define i3 @foo3x5_nsw(
; CHECK-SAME: i3 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP3:%.*]] = mul i3 [[X]], [[X]]
; CHECK-NEXT:    [[TMP2:%.*]] = mul i3 [[TMP3]], [[X]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i3 [[TMP2]], [[TMP3]]
; CHECK-NEXT:    ret i3 [[TMP4]]
;
  %tmp1 = mul i3 %x, %x
  %tmp2 = mul i3 %tmp1, %x
  %tmp3 = mul i3 %tmp2, %x
  %tmp4 = mul nsw i3 %tmp3, %x
  ret i3 %tmp4
}

define i3 @foo3x6(i3 %x) {
; Can be done with two multiplies.
; CHECK-LABEL: define i3 @foo3x6(
; CHECK-SAME: i3 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = mul i3 [[X]], [[X]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i3 [[TMP1]], [[X]]
; CHECK-NEXT:    [[TMP2:%.*]] = mul i3 [[TMP3]], [[TMP3]]
; CHECK-NEXT:    ret i3 [[TMP2]]
;
  %tmp1 = mul i3 %x, %x
  %tmp2 = mul i3 %tmp1, %x
  %tmp3 = mul i3 %tmp2, %x
  %tmp4 = mul i3 %tmp3, %x
  %tmp5 = mul i3 %tmp4, %x
  ret i3 %tmp5
}

define i3 @foo3x7(i3 %x) {
; Can be done with two multiplies.
; CHECK-LABEL: define i3 @foo3x7(
; CHECK-SAME: i3 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP5:%.*]] = mul i3 [[X]], [[X]]
; CHECK-NEXT:    [[TMP6:%.*]] = mul i3 [[TMP5]], [[X]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i3 [[TMP6]], [[X]]
; CHECK-NEXT:    [[TMP7:%.*]] = mul i3 [[TMP3]], [[TMP6]]
; CHECK-NEXT:    ret i3 [[TMP7]]
;
  %tmp1 = mul i3 %x, %x
  %tmp2 = mul i3 %tmp1, %x
  %tmp3 = mul i3 %tmp2, %x
  %tmp4 = mul i3 %tmp3, %x
  %tmp5 = mul i3 %tmp4, %x
  %tmp6 = mul i3 %tmp5, %x
  ret i3 %tmp6
}

define i4 @foo4x8(i4 %x) {
; Can be done with two multiplies.
; CHECK-LABEL: define i4 @foo4x8(
; CHECK-SAME: i4 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = mul i4 [[X]], [[X]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i4 [[TMP1]], [[TMP1]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i4 [[TMP4]], [[TMP4]]
; CHECK-NEXT:    ret i4 [[TMP3]]
;
  %tmp1 = mul i4 %x, %x
  %tmp2 = mul i4 %tmp1, %x
  %tmp3 = mul i4 %tmp2, %x
  %tmp4 = mul i4 %tmp3, %x
  %tmp5 = mul i4 %tmp4, %x
  %tmp6 = mul i4 %tmp5, %x
  %tmp7 = mul i4 %tmp6, %x
  ret i4 %tmp7
}

define i4 @foo4x9(i4 %x) {
; Can be done with three multiplies.
; CHECK-LABEL: define i4 @foo4x9(
; CHECK-SAME: i4 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = mul i4 [[X]], [[X]]
; CHECK-NEXT:    [[TMP2:%.*]] = mul i4 [[TMP1]], [[TMP1]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i4 [[TMP2]], [[X]]
; CHECK-NEXT:    [[TMP8:%.*]] = mul i4 [[TMP3]], [[TMP2]]
; CHECK-NEXT:    ret i4 [[TMP8]]
;
  %tmp1 = mul i4 %x, %x
  %tmp2 = mul i4 %tmp1, %x
  %tmp3 = mul i4 %tmp2, %x
  %tmp4 = mul i4 %tmp3, %x
  %tmp5 = mul i4 %tmp4, %x
  %tmp6 = mul i4 %tmp5, %x
  %tmp7 = mul i4 %tmp6, %x
  %tmp8 = mul i4 %tmp7, %x
  ret i4 %tmp8
}

define i4 @foo4x10(i4 %x) {
; Can be done with three multiplies.
; CHECK-LABEL: define i4 @foo4x10(
; CHECK-SAME: i4 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = mul i4 [[X]], [[X]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i4 [[TMP1]], [[TMP1]]
; CHECK-NEXT:    [[TMP2:%.*]] = mul i4 [[TMP4]], [[X]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i4 [[TMP2]], [[TMP2]]
; CHECK-NEXT:    ret i4 [[TMP3]]
;
  %tmp1 = mul i4 %x, %x
  %tmp2 = mul i4 %tmp1, %x
  %tmp3 = mul i4 %tmp2, %x
  %tmp4 = mul i4 %tmp3, %x
  %tmp5 = mul i4 %tmp4, %x
  %tmp6 = mul i4 %tmp5, %x
  %tmp7 = mul i4 %tmp6, %x
  %tmp8 = mul i4 %tmp7, %x
  %tmp9 = mul i4 %tmp8, %x
  ret i4 %tmp9
}

define i4 @foo4x11(i4 %x) {
; Can be done with four multiplies.
; CHECK-LABEL: define i4 @foo4x11(
; CHECK-SAME: i4 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = mul i4 [[X]], [[X]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i4 [[TMP1]], [[TMP1]]
; CHECK-NEXT:    [[TMP2:%.*]] = mul i4 [[TMP4]], [[X]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i4 [[TMP2]], [[X]]
; CHECK-NEXT:    [[TMP10:%.*]] = mul i4 [[TMP3]], [[TMP2]]
; CHECK-NEXT:    ret i4 [[TMP10]]
;
  %tmp1 = mul i4 %x, %x
  %tmp2 = mul i4 %tmp1, %x
  %tmp3 = mul i4 %tmp2, %x
  %tmp4 = mul i4 %tmp3, %x
  %tmp5 = mul i4 %tmp4, %x
  %tmp6 = mul i4 %tmp5, %x
  %tmp7 = mul i4 %tmp6, %x
  %tmp8 = mul i4 %tmp7, %x
  %tmp9 = mul i4 %tmp8, %x
  %tmp10 = mul i4 %tmp9, %x
  ret i4 %tmp10
}

define i4 @foo4x12(i4 %x) {
; Can be done with two multiplies.
; CHECK-LABEL: define i4 @foo4x12(
; CHECK-SAME: i4 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = mul i4 [[X]], [[X]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i4 [[TMP1]], [[X]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i4 [[TMP4]], [[TMP4]]
; CHECK-NEXT:    [[TMP2:%.*]] = mul i4 [[TMP3]], [[TMP3]]
; CHECK-NEXT:    ret i4 [[TMP2]]
;
  %tmp1 = mul i4 %x, %x
  %tmp2 = mul i4 %tmp1, %x
  %tmp3 = mul i4 %tmp2, %x
  %tmp4 = mul i4 %tmp3, %x
  %tmp5 = mul i4 %tmp4, %x
  %tmp6 = mul i4 %tmp5, %x
  %tmp7 = mul i4 %tmp6, %x
  %tmp8 = mul i4 %tmp7, %x
  %tmp9 = mul i4 %tmp8, %x
  %tmp10 = mul i4 %tmp9, %x
  %tmp11 = mul i4 %tmp10, %x
  ret i4 %tmp11
}

define i4 @foo4x13(i4 %x) {
; Can be done with three multiplies.
; CHECK-LABEL: define i4 @foo4x13(
; CHECK-SAME: i4 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = mul i4 [[X]], [[X]]
; CHECK-NEXT:    [[TMP2:%.*]] = mul i4 [[TMP1]], [[X]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i4 [[TMP2]], [[TMP2]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i4 [[TMP3]], [[X]]
; CHECK-NEXT:    [[TMP12:%.*]] = mul i4 [[TMP4]], [[TMP3]]
; CHECK-NEXT:    ret i4 [[TMP12]]
;
  %tmp1 = mul i4 %x, %x
  %tmp2 = mul i4 %tmp1, %x
  %tmp3 = mul i4 %tmp2, %x
  %tmp4 = mul i4 %tmp3, %x
  %tmp5 = mul i4 %tmp4, %x
  %tmp6 = mul i4 %tmp5, %x
  %tmp7 = mul i4 %tmp6, %x
  %tmp8 = mul i4 %tmp7, %x
  %tmp9 = mul i4 %tmp8, %x
  %tmp10 = mul i4 %tmp9, %x
  %tmp11 = mul i4 %tmp10, %x
  %tmp12 = mul i4 %tmp11, %x
  ret i4 %tmp12
}

define i4 @foo4x14(i4 %x) {
; Can be done with three multiplies.
; CHECK-LABEL: define i4 @foo4x14(
; CHECK-SAME: i4 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = mul i4 [[X]], [[X]]
; CHECK-NEXT:    [[TMP6:%.*]] = mul i4 [[TMP1]], [[X]]
; CHECK-NEXT:    [[TMP7:%.*]] = mul i4 [[TMP6]], [[TMP6]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i4 [[TMP7]], [[X]]
; CHECK-NEXT:    [[TMP5:%.*]] = mul i4 [[TMP4]], [[TMP4]]
; CHECK-NEXT:    ret i4 [[TMP5]]
;
  %tmp1 = mul i4 %x, %x
  %tmp2 = mul i4 %tmp1, %x
  %tmp3 = mul i4 %tmp2, %x
  %tmp4 = mul i4 %tmp3, %x
  %tmp5 = mul i4 %tmp4, %x
  %tmp6 = mul i4 %tmp5, %x
  %tmp7 = mul i4 %tmp6, %x
  %tmp8 = mul i4 %tmp7, %x
  %tmp9 = mul i4 %tmp8, %x
  %tmp10 = mul i4 %tmp9, %x
  %tmp11 = mul i4 %tmp10, %x
  %tmp12 = mul i4 %tmp11, %x
  %tmp13 = mul i4 %tmp12, %x
  ret i4 %tmp13
}

define i4 @foo4x15(i4 %x) {
; Can be done with four multiplies.
; CHECK-LABEL: define i4 @foo4x15(
; CHECK-SAME: i4 [[X:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = mul i4 [[X]], [[X]]
; CHECK-NEXT:    [[TMP6:%.*]] = mul i4 [[TMP1]], [[X]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i4 [[TMP6]], [[TMP6]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i4 [[TMP3]], [[X]]
; CHECK-NEXT:    [[TMP5:%.*]] = mul i4 [[TMP4]], [[X]]
; CHECK-NEXT:    [[TMP14:%.*]] = mul i4 [[TMP5]], [[TMP4]]
; CHECK-NEXT:    ret i4 [[TMP14]]
;
  %tmp1 = mul i4 %x, %x
  %tmp2 = mul i4 %tmp1, %x
  %tmp3 = mul i4 %tmp2, %x
  %tmp4 = mul i4 %tmp3, %x
  %tmp5 = mul i4 %tmp4, %x
  %tmp6 = mul i4 %tmp5, %x
  %tmp7 = mul i4 %tmp6, %x
  %tmp8 = mul i4 %tmp7, %x
  %tmp9 = mul i4 %tmp8, %x
  %tmp10 = mul i4 %tmp9, %x
  %tmp11 = mul i4 %tmp10, %x
  %tmp12 = mul i4 %tmp11, %x
  %tmp13 = mul i4 %tmp12, %x
  %tmp14 = mul i4 %tmp13, %x
  ret i4 %tmp14
}