On 9/27/26 7:26 AM, Nguyen Tran wrote:
For divisions by a compile-time-constant divisor, expand_divmod calls
choose_multiplier with the dividend's full type precision (size or
size - 1). When the dividend's value range is known to be narrower
than the type, choose_multiplier could pick a smaller multiplier and
post-shift, but expand_divmod has no path to receive that range
information.
This patch threads the VRP-derived value range from the GIMPLE side
into expand_divmod and forwards it to choose_multiplier:
* expand_expr_divmod (gcc/expr.cc) computes a dividend precision from
treeop0's range via a new helper determine_value_range, which
queries the active range_query during pass_expand.
* For unsigned (or non-negative-known signed) operands the precision
is wi::min_precision(max_val, UNSIGNED). For signed operands with
possibly negative values it is wi::min_precision of the larger
of -(min + 1) and max under unsigned interpretation, the bound
choose_multiplier itself relies on.
* expand_divmod gets a new dividend_prec parameter and an inline
helper adjusted_dividend_prec that passes it to choose_multiplier
raised to LGUP, so the lgup <= precision precondition is preserved.
The helper is invoked at three call sites: unsigned TRUNC, signed
TRUNC, and signed FLOOR. Passing -1 selects the dividend's full
type precision and reproduces the baseline codegen. dividend_prec
is a required parameter, placed before the optional methods
argument; all callers other than expand_expr_divmod pass -1.
For the example in PR target/91883,
unsigned g (unsigned a) {
if (a > 1000000) __builtin_unreachable ();
return a / 10;
}
baseline -O2 emits
movl %edi, %eax
movl $3435973837, %edx
imulq %rdx, %rax
shrq $35, %rax
with this patch:
movl %edi, %eax
imulq $429497139, %rax, %rax
shrq $32, %rax
The smaller multiplier fits imulq's 32-bit signed immediate, saving
the separate movl, and the post-shift drops from 35 to 32. Similar
effects for /3, /7, /100. For signed /7, codegen also shifts from
the long path (addl-fixup) to the short path, reducing seven
instructions to five.
Functions without VRP range information pass -1 and are unaffected.
gcc.target/i386/pr115910.c is updated. The test has two functions
both doing x / 3U: foo with __builtin_unreachable when x < 0, and
bar with no range information. Previously both produced identical
codegen; the test asserted 2 imulq + 2 shrq $33. With this patch foo's
__builtin_unreachable narrows x to [0, INT_MAX] giving VRP-derived
precision 31, so choose_multiplier picks a smaller M (1431655766,
fits imulq's 32-bit immediate) and post-shift 32 instead of 33.
bar is unchanged. The dg-final assertions are split: still 2 imulq,
plus 1 shrq $32 (foo) and 1 shrq $33 (bar).
One drawback of this patch is some code bloat: the same
divisor at two call sites with different ranges produces different
assembly instructions. Unmodified GCC produces the same assembly
instructions regardless of range, allowing the linker's identical-
code-folding (ICF) pass to merge the two function bodies into a
single copy in the final binary. With this patch the bodies differ,
so ICF cannot fold them. Clang has the same drawback: it also
produces different assembly instructions for the same divisor at
different ranges, which ICF cannot fold.
For example, consider /3 at two different ranges:
unsigned int f3 (unsigned int a) {
if (a > 65535) __builtin_unreachable ();
return a / 3;
}
unsigned int f (unsigned int a) {
if (a > 655356) __builtin_unreachable ();
return a / 3;
}
Unmodified GCC produces byte-identical assembly instructions for
both functions, which ICF folds into a single copy:
f3:
mov eax, edi
mov edx, 2863311531
imul rax, rdx
shr rax, 33
ret
f:
mov eax, edi
mov edx, 2863311531
imul rax, rdx
shr rax, 33
ret
Clang produces different assembly instructions; ICF cannot fold them:
f3:
imul eax, edi, 43691
shr eax, 17
ret
f:
mov ecx, edi
mov eax, 2863311531
imul rax, rcx
shr rax, 33
ret
Patched GCC produces different assembly instructions; ICF cannot
fold them:
f3:
mov eax, edi
imul rax, rax, 1431677610
shr rax, 32
ret
f:
mov eax, edi
imul rax, rax, 1431657130
shr rax, 32
ret
A live demonstration:https://godbolt.org/z/75r6axnvG, compiled with
-O2 -ffunction-sections -fuse-ld=gold -Wl,--icf=all
The flags:
-ffunction-sections put each function into its own section, so
the linker can compare and fold them
individually
-fuse-ld=gold use the gold linker (the default linker
does not support ICF)
-Wl,--icf=all enable ICF in the linker
Under unmodified GCC, f3 and f end up at the same address. Under
clang and patched GCC, they end up at different addresses.
Under default compiler/linker flags this patch likely has no meaningful
downside: ICF is not enabled by default, so unmodified and patched
both keep two copies of the body in .text. We consider this an
acceptable tradeoff: each individual division is at least as small
as before, and clang accepts the same one.
Bootstrapped on x86_64-pc-linux-gnu with the default language set
(c, c++, fortran, objc, obj-c++, lto): "make bootstrap" followed by
"make -k check" from the top of the build tree. Stage-2 vs. stage-3
binary comparison successful (the two compilers GCC produces of itself
are byte-identical). No new regressions in the testsuite, and all
dg-final assertions across the seven new gcc.target/i386/divmod-range-*.c
tests pass.
gcc/ChangeLog:
PR target/91883
* explow.cc (round_push, align_dynamic_address): Pass -1 for
dividend_prec.
* expmed.cc (choose_multiplier): Prepend comment stating the
multiply-shift formula it computes.
(adjusted_dividend_prec): New helper.
(expand_divmod): Add dividend_prec parameter. Forward to
adjusted_dividend_prec at the unsigned TRUNC, signed TRUNC,
and signed FLOOR XOR-sign-flip call sites. Pass -1 at the
recursive calls.
* expmed.h (expand_divmod): Add dividend_prec parameter.
* expr.cc (force_operand): Pass -1 for dividend_prec.
(determine_value_range): New helper, queries range_query
during pass_expand.
(expand_expr_divmod): Compute dividend_prec from treeop0's
range and forward to expand_divmod.
* optabs.cc (expand_doubleword_mod, expand_doubleword_divmod):
Pass -1 for dividend_prec.
gcc/testsuite/ChangeLog:
PR target/91883
* gcc.target/i386/pr115910.c: Adjust shrq assertions for
VRP-narrowed multiplier on foo.
* gcc.target/i386/divmod-range-1.c: New test: VRP-narrowed
multiplier for unsigned /10.
* gcc.target/i386/divmod-range-2.c: New test: VRP-narrowed
multiplier for unsigned %10.
* gcc.target/i386/divmod-range-3.c: New test: VRP-narrowed
multiplier for signed /10.
* gcc.target/i386/divmod-range-4.c: New test: VRP shifts
signed /7 from the long (addl-fixup) path to the short path.
* gcc.target/i386/divmod-range-5.c: New test: regression guard,
no narrower range preserves baseline unsigned divmod codegen.
* gcc.target/i386/divmod-range-6.c: New test: regression guard,
no narrower range preserves signed /7 long-path codegen.
* gcc.target/i386/divmod-range-7.c: New test: VRP-narrowed
multiplier for signed FLOOR_DIV (uses GIMPLE Front End since
FLOOR_DIV_EXPR cannot be produced from C source).
Signed-off-by: Nguyen Tran<[email protected]>
Thanks for reraising this, it got lost and when you reraised you did so
right as folks were traveling for Cauldron/LPC. Sorry for all that.
---
This is v3 of the patch. v2 was posted here:
https://gcc.gnu.org/pipermail/gcc-patches/2026-June/721044.html
Jeff asked for a rebase and repost. v3 changes:
1. Rebased onto current trunk. The two expand_divmod calls added by
r17-2970 (near-power-of-two divisor split) pass -1 for dividend_prec.
2. Dropped the value-query.h / value-range.h includes from expr.cc.
r17-2970 added gimple-range.h there, which includes value-query.h,
and value-range.h already comes in through gimple.h.
3. Bootstrapped and regression-tested on x86_64-pc-linux-gnu (languages:
c, c++, fortran, objc, obj-c++, lto). "make bootstrap" + "make -k
check" from the top of the build tree; stage-2 vs. stage-3 comparison
is clean (byte-identical), no new regressions.
diff --git a/gcc/expmed.h b/gcc/expmed.h
index b4b44bba1d7..0ea14724c5b 100644
--- a/gcc/expmed.h
+++ b/gcc/expmed.h
@@ -713,7 +713,8 @@ extern rtx maybe_expand_shift (enum tree_code,
machine_mode, rtx, int, rtx,
int);
#ifdef GCC_OPTABS_H
extern rtx expand_divmod (int, enum tree_code, machine_mode, rtx, rtx,
- rtx, int, enum optab_methods = OPTAB_LIB_WIDEN);
+ rtx, int, int,
+ enum optab_methods = OPTAB_LIB_WIDEN);
#endif
#endif
So I know this isn't something you introduced, but I'm not a fan of
default arguments like this. Especially when there aren't a ton of call
sites.
While you did the right thing and updated every call site to include the
new dividend precision argument, it's possible there's out of tree
ports/languages we can't see and which would still build now -- but they
run the risk of their optab_methods argument being interpreted as
dividend precision.
Given you're adjusting every known call site to handle the new required
argument, can you make sure every site as an optab_methods argument and
drop the default from the prototype (defaulting to OPTAB_LIB_WIDEN if
none is already provided). At least with that setup an out of tree
language or target would fail to build rather than silently doing the
wrong thing. If you'd prefer that to be a followup patch, that's fine
with me too, but given this patch touches them all, it seems more
natural as part of this patch.
Let me know your preference. I'm ready to ACK this if you commit to do
the followup or to ACK a V4 with that change.
Jeff
