arith: lower to specific architectures

[mmcloughlin]

Generate architecture-specific code from arithmetic IR.

• x86 via avo
• Pure Go with math/bits and crypto/subtle
• arm64
• s390x

Related #96

[mmcloughlin]

Thoughts for x86 lowering:

• Program needs to have only one carry bit live at a time so it can be lowered to legacy addition instructions, or two for the ADX extension
• Ad instructions must use the same carry register for input and output
• Add/sub instructions take two arguments in x86 but the IR takes three

[mmcloughlin]

Instruction Sets

Instruction set architectures for multi-precision arithmetic.

• test/codegen/mathbits.go shows instructions the math/bits intrinsics are lowered to.

go

• MOV: =
• CMOV: subtle.ConstantTimeSelect
• ADD: math/bits.Add
• SUB: math/bits.Sub
• MUL: math.bits.Mul
• SHL: <<
• SHR: >>

arm64

• MOV: MOV
• CMOV: CSEL
• ADD: ADCS
• SUB: SBCS
• MUL: UMULL, UMULH
• SHL: LSLV
• SHR: LSRV

Other:

• ADD (extended register): Add (extended register) adds a register value and a sign or zero-extended register value, followed by an optional left shift amount
• ADDS (shifted register): Add (shifted register), setting flags, adds a register value and an optionally-shifted register value, and writes the result to the destination register. It updates the condition flags based on the result.
• UMADDL: Unsigned Multiply-Add Long multiplies two 32-bit register values, adds a 64-bit register value, and writes the result to the 64-bit destination register.
• LDP: Load Pair of Registers

s390x

• MOV:
• CMOV: VSEL
• ADD: VAQ, VACQ, VACCQ, VACCCQ
• SUB: VSBIQ, VSCBIQ, VSBCBIQ
• MUL: VMLF, VMSLG, VMALF, VMALHF, VMLHF, VMSLEOG
• SHL: VSLDB
• SHR: VSRLB

Reference:

• z/Architecture Reference Summary
• z13 Vector Extension Facility (SIMD)

ppc64

• MOV: MOVD, MOVDU (go instructions)
• CMOV: stdcx
• ADD: addc, addco, adde, addeo, addze, addzeo, ...
• SUB: subfe, subfeo, subfze, subfzeo, ...
• MUL: mulld, mulhd
• SHL: sld
• SHR: srd

Registers:

• 32 general-purpose 64-bit registers
• Overflow flag OV, carry CA. Both can be used as carry bits.

Other:

• addme, addmeo: Add to Minus One Extended (and subtraction version)
• addze, addzeo: Add to Zero Extended (and subtraction version)
• Power also supports instructions with shifted arguments, like "shifted register" in ARM

Reference:

• Power ISA Version 2.07
• cmd/asm/internal/asm/testdata/ppc64.s
• math/big/arith_ppc64x.s

LLVM IR?

• MOV:
• CMOV: select
• ADD: add i128 (use zext, shl, lshr, trunc, ... to manipulate carries)
• SUB: sub i128 with methods similar to addition for borrow bits
• MUL: mul i128 with arguments zextended to i128
• SHL: shl
• SHR: lshr

Reference:

• LLVM Language Reference Manual
• @llvm.uadd.with.overflow.i64 unfortunately lacks "carry in"
• Generating Big Num addition code which uses ADC (add with carry) instructions