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 > > > > > > > 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
