On Tue, Jun 30, 2026 at 10:52 AM Hongtao Liu <[email protected]> wrote: > > On Tue, Jun 30, 2026 at 4:13 PM Richard Biener > <[email protected]> wrote: > > > > On Tue, Jun 30, 2026 at 9:50 AM Hongtao Liu <[email protected]> wrote: > > > > > > 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. > > > > But the cmov will still serialize this? So the point is that > > the longer non-power-of-two sequence (plus the cmov) is > > faster than the idiv? That's a pretty target specific > > thing, so again I think this is something for RTL expansion > > where we evaluate division-by-constant costs appropriately > > To be conservative, perhaps I should first only handle the cases of 1 > and 2, so that a / (2 - bool) can be converted from a division into a > conditional shift, which should be profitable for all targets.
Maybe. I still wouldn't do this from GIMPLE. > > > > > > > > > > > > > > > > > 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 > > > > -- > BR, > Hongtao
