Missed canonicalization: shared-use `urem(x, C)` compared with `x` when `x - urem(x, C)` already exists

[ParkHanbum]

Summary

LLVM currently leaves optimized IR with an unsigned remainder result compared
back to its own dividend even when the same remainder also feeds
x - urem(x, C).

For unsigned positive constant C:

%rem = urem T %x, C
%rounded = sub nuw T %x, %rem
%cmp = icmp eq T %x, %rem

%cmp is equivalent to %rounded == 0. The ne form is equivalent to
%rounded != 0.

This is not a standalone urem deletion opportunity for the reviewed corpus
rows, because %rem remains needed by %rounded. The issue is a narrower
canonicalization / combined-transform opportunity: when %rounded already
exists, the branch condition can be expressed through that value instead of
comparing the dividend against the remainder.

Example

One representative corpus row in bench/faiss/optimized/test_cppcontrib_sa_decode.ll:

%478 = urem i64 %0, 3
%479 = sub nuw i64 %0, %478
%.not1067 = icmp eq i64 %0, %478
br i1 %.not1067, label %.loopexit, label %.preheader.lr.ph

The compare can be represented as:

%.not1067 = icmp eq i64 %479, 0

because %479 = %0 - (%0 % 3), so %479 is zero exactly when %0 < 3, which
is also exactly when %0 % 3 == %0.

The same relation applies to ne:

%cmp = icmp ne T %x, %rem

can be represented as:

%cmp = icmp ne T %rounded, 0

when %rounded = sub nuw T %x, %rem is already present.

Corpus Evidence

The source exploration scanned the full optimized corpus:

• 38,659 optimized .ll files scanned;
• 38 raw target-relation rows;
• 8 files;
• 7 projects.

Review result:

• all 38 rows are shared-use rows;
• 0 rows are compare-only urem deletion candidates;
• each reviewed row has the urem result compared with the dividend and also
  used in x - urem(x, C).

Distribution:

Dimension	Values
Projects	faiss: 29, folly: 2, node: 2, opencv: 2, linux: 1, llvm: 1, mold: 1
Divisors	3: 34, 96: 2, 384: 1, 24: 1
Predicates	eq: 36, ne: 2

Representative rows:

Source	Shape
bench/faiss/optimized/test_cppcontrib_sa_decode.ll:5186	%478 = urem i64 %0, 3; %479 = sub nuw i64 %0, %478; icmp eq i64 %0, %478
bench/folly/optimized/SpookyHashV1.ll:938	%220 = urem i64 %.0, 96; %.idx = sub nuw i64 %.0, %220; icmp eq i64 %.0, %220
bench/node/optimized/libnode.string_bytes.ll:2373	%0 = urem i64 %cond, 3; compare uses ne against %cond

Expected Canonicalization

Initial scope:

%rem = urem T %x, C
%rounded = sub nuw T %x, %rem
%cmp = icmp eq T %x, %rem

to:

%cmp = icmp eq T %rounded, 0

and:

%cmp = icmp ne T %x, %rem

to:

%cmp = icmp ne T %rounded, 0

The transform should require that %rounded already exists or that creating it
is profitable for another use. It should not create a new sub solely to
rewrite the comparison.

Profitability Notes

A local POC separates two cases:

• compare-only urem(x, C) vs x, where deleting urem would be clearly
  profitable;
• shared-use corpus shape, where urem remains live for x - urem(x, C).

The reviewed corpus evidence is the second case.

Local llvm-mca Measurements

Each row is measured as a separate function body with llvm-mca, 100
iterations.

Compare-only contrast, not corpus evidence:

Target model	Function	Instructions / 100 iters	Total cycles / 100 iters	Total uOps / 100 iters	Block RThroughput
x86-64 x86-64	current urem i64 x, 3 + compare	800	308	900	2.3
x86-64 x86-64	folded x < 3 compare	300	104	300	1.0
AArch64 generic	current urem i64 x, 3 + compare	800	1202	800	2.7
AArch64 generic	folded x < 3 compare	300	201	300	1.0
RISC-V rocket-rv64	current urem i64 x, 3 + compare	1200	11001	1300	13.0
RISC-V rocket-rv64	folded x < 3 compare	200	201	200	2.0

Shared-use corpus shape:

Target model	Function	Instructions / 100 iters	Total cycles / 100 iters	Total uOps / 100 iters	Block RThroughput
x86-64 x86-64	current shared-use form	800	346	1000	2.5
x86-64 x86-64	compare canonicalized, urem still live	800	343	1000	2.5
AArch64 generic	current shared-use form	800	1202	800	2.7
AArch64 generic	compare canonicalized, urem still live	800	1102	800	2.7
RISC-V rocket-rv64	current shared-use form	1400	11201	1500	15.0
RISC-V rocket-rv64	compare canonicalized, urem still live	1300	11101	1400	14.0

These measurements suggest the shared-use canonicalization is modest by itself,
but it exposes the existing rounded-down multiple and avoids expressing the
branch condition through the remainder value directly. It may be more valuable
as a canonical form for subsequent simplification or target lowering.

Legality Notes

For unsigned remainder by positive constant C, %rem = urem %x, C satisfies
0 <= %rem < C. Therefore:

%rem == %x  <=>  %x < C

and, when %rounded = %x - %rem:

%rounded == 0  <=>  %x < C  <=>  %rem == %x

The sub nuw form seen in the corpus is consistent with %rem <= %x.

Initial guards:

• urem divisor is a positive nonzero constant;
• compare is same-SSA dividend against the urem result;
• predicate is eq or ne;
• %rounded = sub nuw %x, %rem already exists;
• do not introduce a new %rounded solely for this rewrite unless a separate
  profitability rule justifies it.

Scope Boundaries

This issue is not a request for:

• signed remainder (srem);
• modulo-zero divisibility tests;
• variable divisors;
• deleting urem when the remainder still has non-comparison uses;
• creating new x - urem(x, C) expressions solely to rewrite a compare;
• LLVM patch authoring;
• LLVM test authoring.

Reproduction Data

Local source exploration packet:

optimization_attempts/attempts/2026-07-03-urem-result-dividend-compare-exploration/

Key artifacts:

• 2026-07-03-urem-result-dividend-compare-raw.jsonl
• 2026-07-03-urem-result-dividend-compare-summary.md
• 2026-07-03-urem-cost-poc.ll
• 2026-07-03-urem-cost-poc.md
• 2026-07-03-urem-cost-poc.x86_64.s
• 2026-07-03-urem-cost-poc.aarch64.s
• 2026-07-03-urem-cost-poc.riscv64.s

Local issue draft packet:

optimization_attempts/attempts/2026-07-04-urem-result-dividend-shared-use-issue-draft/

Key artifacts:

• 2026-07-04-llvm-issue-urem-result-dividend-shared-use.md
• 2026-07-04-urem-cost-measurement.md

Non-Goals

This local draft does not include an LLVM patch, LLVM test, full backend
benchmark, or implementation plan. It is intended for human review before any
external issue submission.

AliveProof : https://alive2.llvm.org/ce/z/FP8UQy
Compiler-explorer: https://compiler-explorer.com/z/TrcMvPr39