InstCombine: fold comparison of `shl` result with original operand

[ParkHanbum]

Summary

LLVM currently leaves comparisons of a left-shifted value with the original
operand in some cases:

%s = shl iN %x, C
%cmp = icmp eq iN %s, %x

For a nonzero constant shift amount C less than the bitwidth, this can be
folded to:

%cmp = icmp eq iN %x, 0

The ne form can similarly fold to icmp ne iN %x, 0.

Suggested fold

icmp eq (shl X, C), X  ->  icmp eq X, 0
icmp eq X, (shl X, C)  ->  icmp eq X, 0
icmp ne (shl X, C), X  ->  icmp ne X, 0
icmp ne X, (shl X, C)  ->  icmp ne X, 0

Required conditions:

• C is a nonzero integer constant.
• C < bitwidth(X).
• Start with plain scalar integer shl.
• If shl has nsw/nuw, check the fold under LLVM poison semantics before
  extending the implementation to those forms.

Why this is valid

For an N-bit integer and 0 < C < N, plain shl X, C is equivalent to
X * 2^C modulo 2^N.

If (X << C) == X, then:

X * (2^C - 1) == 0 mod 2^N

2^C - 1 is odd, so it is invertible modulo 2^N. Therefore the equality can
only hold when X == 0. The ne form is the inverse.

Minimized example

Current LLVM keeps the core shape in the planning-gate POC used by the local
exploration:

define i1 @src(i64 %x) {
entry:
  %s = shl i64 %x, 5
  %cmp = icmp eq i64 %s, %x
  ret i1 %cmp
}

Expected:

define i1 @tgt(i64 %x) {
entry:
  %cmp = icmp eq i64 %x, 0
  ret i1 %cmp
}

The ne form:

define i1 @src_ne(i64 %x) {
entry:
  %s = shl i64 %x, 5
  %cmp = icmp ne i64 %s, %x
  ret i1 %cmp
}

Expected:

define i1 @tgt_ne(i64 %x) {
entry:
  %cmp = icmp ne i64 %x, 0
  ret i1 %cmp
}

Corpus evidence

A full optimized-corpus scan found 2 reviewed true-positive rows.

1. bench/ffmpeg/optimized/elbg.ll:418

%40 = shl nsw i32 %24, 2
%.not.i80.i.i.i = icmp eq i32 %24, %40

This is the same result-vs-original comparison shape. Because the shift carries
nsw, implementation should check poison legality before covering this form.

2. bench/yosys/optimized/show.ll:69468

%6240 = xor i32 %6239, %6238
%6241 = shl i32 %6240, 5
%6242 = xor i32 %6241, %6240
store i32 %6242, ptr %6061, align 8, !tbaa !133
...
%6244 = icmp eq i32 %6241, %6240

The shifted value has another use, so this fold does not necessarily delete the
shl instruction in this corpus hit. It still replaces the compare input with a
zero test of the original operand.

Current local evidence

• Source exploration packet:
  optimization_attempts/attempts/2026-07-04-shl-result-operand-compare-exploration/
• Planning gate result: current default<O2> left the minimized current-form
  POC.
• Corpus result: 2 rows across 2 files and 2 projects.
• Manual review: both rows classified as true_positive.
• Cost measurement:
  optimization_attempts/attempts/2026-07-05-shl-result-operand-compare-issue-draft/2026-07-05-shl-cost-measurement.md

Cost measurement summary

The minimized plain-shl form was measured after default<O2> and llc on
x86-64/skylake, AArch64/neoverse-n1, and RISC-V/generic-rv64 with llvm-mca.

Target model	Variant	Instructions	Total cycles	Total uOps	Block RThroughput
x86-64 skylake	current shl result compare	500	161	700	1.2
x86-64 skylake	folded zero compare	300	110	500	1.0
AArch64 neoverse-n1	current shl result compare	300	303	300	1.0
AArch64 neoverse-n1	folded zero compare	300	203	300	1.0
RISC-V generic-rv64	current shl result compare	400	301	400	2.0
RISC-V generic-rv64	folded zero compare	200	101	200	1.0

The result is cost-positive for the minimized plain-shl compare. A real corpus
hit may still keep the shl for another use, but the compare itself becomes a
zero test.

Notes

This is a small InstCombine canonicalization opportunity. It should be
implemented with tests for both operand orders and both eq/ne predicates.
No-wrap flagged forms should be added only after the poison semantics are
checked.

https://compiler-explorer.com/z/Y7hzf985K