[InstCombine] InstCombine gets stuck when simplifying selects

[dtcxzyw]

Reduced test case: https://godbolt.org/z/ds9eq96db

define i16 @func(i16 noundef %p_12) {
entry:
  %cmp1 = icmp ult i16 %p_12, 2
  %and1 = and i16 %p_12, 1
  %and2 = select i1 %cmp1, i16 %and1, i16 0
  %cmp2 = icmp eq i16 %and2, %p_12
  %and3 = select i1 %cmp2, i16 %and1, i16 0
  ret i16 %and3
}

ADD:   %and3 = select i1 %cmp2, i16 %and2, i16 0
ADD:   %and2 = select i1 %cmp1, i16 %and1, i16 0
ADD:   %and1 = and i16 %p_12, 1
IC: Visiting:   %and1 = and i16 %p_12, 1
IC: Visiting:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %and3 = select i1 %cmp2, i16 %and2, i16 0
ADD DEFERRED:   %and2 = select i1 %cmp1, i16 %and1, i16 0
ADD DEFERRED:   %cmp2 = icmp eq i16 %and2, %p_12
IC: Mod =   %and3 = select i1 %cmp2, i16 %and2, i16 0
    New =   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD:   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD:   %cmp2 = icmp eq i16 %and2, %p_12
ADD:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %cmp2 = icmp eq i16 %and2, %p_12
IC: Visiting:   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD DEFERRED:   %and1 = and i16 %p_12, 1
ADD DEFERRED:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Mod =   %and3 = select i1 %cmp2, i16 %and1, i16 0
    New =   %and3 = select i1 %cmp2, i16 %and2, i16 0


ADD:   %and3 = select i1 %cmp2, i16 %and2, i16 0
ADD:   %and2 = select i1 %cmp1, i16 %and1, i16 0
ADD:   %and1 = and i16 %p_12, 1
IC: Visiting:   %and1 = and i16 %p_12, 1
IC: Visiting:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %and3 = select i1 %cmp2, i16 %and2, i16 0
ADD DEFERRED:   %and2 = select i1 %cmp1, i16 %and1, i16 0
ADD DEFERRED:   %cmp2 = icmp eq i16 %and2, %p_12
IC: Mod =   %and3 = select i1 %cmp2, i16 %and2, i16 0
    New =   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD:   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD:   %cmp2 = icmp eq i16 %and2, %p_12
ADD:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %cmp2 = icmp eq i16 %and2, %p_12
IC: Visiting:   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD DEFERRED:   %and1 = and i16 %p_12, 1
ADD DEFERRED:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Mod =   %and3 = select i1 %cmp2, i16 %and1, i16 0
    New =   %and3 = select i1 %cmp2, i16 %and2, i16 0

...

[dtcxzyw]

Another reproducer: https://godbolt.org/z/7MEYTe9cq

declare void @use(i32,i32)

define void @func(ptr %p) {
  %1 = load i32, ptr %p, align 4
  %2 = sext i32 %1 to i64
  %3 = icmp slt i64 %2, 2
  %4 = zext i1 %3 to i32
  %5 = and i32 %4, %1
  %6 = icmp eq i32 %5, %1
  %7 = zext i1 %6 to i32
  %8 = and i32 %7, %1
  call void @use(i32 %8, i32 noundef %1)
  ret void
}

[dtcxzyw]

Third reproducer: https://godbolt.org/z/8f8b4xved

define i8 @func(i32 noundef %p_38) {
entry:
  %conv393 = trunc i32 %p_38 to i8
  %0 = call i8 @llvm.bitreverse.i8(i8 %conv393)
  %conv394 = zext i8 %0 to i32
  %cmp395 = icmp eq i32 %conv394, %p_38
  %conv397 = zext i1 %cmp395 to i8
  %mul.i = mul i8 %conv393, %conv397
  ret i8 %mul.i
}

[dtcxzyw]

Third reproducer: https://godbolt.org/z/8f8b4xved

define i8 @func(i32 noundef %p_38) {
entry:
  %conv393 = trunc i32 %p_38 to i8
  %0 = call i8 @llvm.bitreverse.i8(i8 %conv393)
  %conv394 = zext i8 %0 to i32
  %cmp395 = icmp eq i32 %conv394, %p_38
  %conv397 = zext i1 %cmp395 to i8
  %mul.i = mul i8 %conv393, %conv397
  ret i8 %mul.i
}

A simpler testcase:

define i8 @func(i32 noundef %x) {
entry:
  %trunc = trunc i32 %x to i8
  %rev = call i8 @llvm.bitreverse.i8(i8 %trunc)
  %ext = zext i8 %rev to i32
  %cmp = icmp eq i32 %ext, %x
  %sel = select i1 %cmp, i8 %trunc, i8 0
  ret i8 %sel
}

@nikic I have no idea how to fix it in foldSelectValueEquivalence/simplifyWithOpReplaced. simplifyWithOpReplaced may replace the input x with a more complicated value f(x).

[dtcxzyw]

@nikic Ping.