On Tue, Jun 30, 2026 at 4:41 AM Liu, Hongtao <[email protected]> wrote:
>
>
>
> > -----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?
It depends on the target. But then since conditional moves are not speculated
you still get the integer division latency, so what's the point?
IMO this is an optimization that should be done at RTL expansion time
(we should have value-ranges available there now).
>
> >
> > 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
