On Tue, Jun 30, 2026 at 3:42 PM Richard Biener
<[email protected]> wrote:
>
> 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?
N/N(+1) is integer constant which is compile-time known, op0/N,
op0/(N+1) will be optimized to *shift* or *a sequence of magic
multiply*, and there won't be any division left.(the case below)
>
> 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
Here.
> >
> > 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
--
BR,
Hongtao
