> -----Original Message-----
> From: Jeffrey Law <[email protected]>
> Sent: Tuesday, June 30, 2026 4:01 AM
> To: Liu, Hongtao <[email protected]>; [email protected]
> Cc: [email protected]
> Subject: Re: [PATCH] tree-ssa: Split divisions by near power-of-two ranges [PR
> middle-end/125708]
>
>
>
> On 6/29/2026 12:14 AM, liuhongt wrote:
> > When op1's range is [N, N + 1] and one of N or N + 1 is a power of
> > two, split a TRUNC_DIV_EXPR into two divisions by constants selected
> > by a compare:
> >
> > op0 / op1 -> op1 == N ? op0 / N : op0 / (N + 1)
> >
> > Each arm divides by a constant, so expansion strength-reduces it (a
> > shift on the power-of-two arm) and the divide instruction is avoided.
> >
> > This grows code, so gate it on optimize_bb_for_speed_p.
> >
> > Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}.
> > Ok for trunk?
> >
> > PR middle-end/125708
> >
> > gcc/ChangeLog:
> >
> > * vr-values.cc
> > (simplify_using_ranges::simplify_div_or_mod_using_ranges):
> > Compute op1's upper bound for all codes and add the
> > near-power-of-two TRUNC_DIV_EXPR split, guarded on
> > optimize_bb_for_speed_p.
> >
> > gcc/testsuite/ChangeLog:
> >
> > * gcc.dg/tree-ssa/pr125708-1.c: New test.
> > * gcc.target/i386/pr125708-2.c: New test.
> Note that you're introducing a conditional branch into the mix as well. If
> it's a
> poorly predicted branch, then you could end up burning more cycles on the
> branch mispredict than the division would have taken.
I assume COND_EXPR op1 == N ? op0 / N : op0 / (N + 1) will be expanded into a
conditional move at rtl w/o branch, maybe I should also add
can_conditionally_move_p to guard the optimization?
>
> I'd kind of want to get a better sense of whether or not we're actually making
> an improvement here.
>
> If we're selecting across 1/2 for the divisor and the dividend is a suitable
> type,
> then this really becomes a conditional right shift by 1, right? That seems
> likely
> to have a generally profitable synthesis. But an arbitary n, n+1 where one of
> them is a power of two isn't as obvious to me.
Yes, for the original case in the PR(divisor is 2 - bool), it's a conditional
shift which should be profitable.
For an arbitrary, when divisor is pow2 +- 1, since divisor now is constant,
division by any nonzero compile-time constant is always strength-reduced with
magic multiply.
So, it's *shift + magic multiply + compare + conditional move* vs. *original
division*
.i.e
int
foo (int a, bool b)
{
return a / ((1 << 20) - b);
}
Before optimization
mov eax, edi
movzx esi, sil
mov ecx, 1048576
sub ecx, esi
cdq
idiv ecx
After optimization
movslq %edi, %rax
movl %edi, %edx
imulq $-2147481599, %rax, %rax
sarl $31, %edx
shrq $32, %rax
addl %edi, %eax
sarl $19, %eax
subl %edx, %eax
testl %edi, %edi
leal 1048575(%rdi), %edx
cmovns %edi, %edx
sarl $20, %edx
testb %sil, %sil
cmove %edx, %eax
ret
Since division is strength-reduced to magic multiply(so the multiplication
sequence should be cheaper the division), the extra cost here is *shift +
compare + conditional move*, I think it's profitable(guarded by
optimize_bb_for_speed_p).
>
> jeff
