cmd/compile: optimize conditional subtractions

[FiloSottile]

Here are two ways of doing the same thing, reducing a value in [0, 2q) mod q:

const q = 8380417 // 2²³ - 2¹³ + 1

// fieldElement is an integer modulo q, an element of ℤ_q. It is always reduced.
type fieldElement uint32

// fieldReduceOnce reduces a value a < 2q.
func fieldReduceOnce(a uint32) fieldElement {
	x, b := bits.Sub32(a, q, 0)
	return fieldElement(x + b*q)
}

// fieldReduceOnce reduces a value a < 2q.
func fieldReduceOnce2(a uint32) fieldElement {
	x, b := bits.Sub32(a, q, 0)
	return fieldElement(subtle.ConstantTimeSelect(int(b), int(x), int(a)))
}

They both generate awful code, when it could be just

        MOVL    AX, CX
        SUBL    $8380417, CX
        CMOVCC  CX, AX

Could the compiler pattern match one of those (or some other form I can use) and produce the more efficient code?

More generally, it might also be useful to detect using the carry/borrow from a math/bits function with subtle.ConstantTimeSelect in cases that are more complex than a conditional subtraction.

/cc @golang/compiler

[gabyhelp]

Related Issues

• cmd/compile: ARM64 CSE flags generation between `CMP 0$` and instruction already setting the flags according to the result #74878
• cmd/compile: inefficient compilation of (64 - x) #20677 (closed)
• cmd/compile: optimize comparisons to min/max (u)ints by checking for overflow #41664 (closed)
• cmd/compile/ssa: conditional select instructions #21391 (closed)
• cmd/compile: use better code for slicing #17638
• cmd/compile: optimize range comparisons like 'A' <= c && c <= 'Z' #17372 (closed)
• cmd/compile: teach prove that x ∈ [0, c) ⇒ c - x ∈ [0, c) #29477 (closed)
• cmd/compile: amd64 carry flag spilling uses SBBQ + NEGQ instead of SETCS #68961
• cmd/compile: emit (MAX|MIN)SD instead of UCOMISD when possible #31272 (closed)
• cmd/compile: Optimise branches that could be behind other branches, to avoid running those branches when known to be false #46711

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[gopherbot]

Change https://go.dev/cl/715044 mentions this issue: cmd/compile: rewrite proved multiplies by 0 or 1 into CondSelect

[gopherbot]

Change https://go.dev/cl/715045 mentions this issue: crypto/subtle,cmd/compile: add intrinsics for ConstantTimeSelect and *Eq

[mknyszek]

CC @golang/compiler