Skip to content

Commit a3055af

Browse files
randall77randall77
committed
[dev.ssa] cmd/compile: strength-reduce 64-bit constant divides
The frontend does this for 32 bits and below, but SSA needs to do it for 64 bits. The algorithms are all copied from cgen.go:cgen_div. Speeds up TimeFormat substantially: ~40% slower to ~10% slower. Change-Id: I023ea2eb6040df98ccd9105e15ca6ea695610a7a Reviewed-on: https://go-review.googlesource.com/19302 Run-TryBot: Keith Randall <[email protected]> TryBot-Result: Gobot Gobot <[email protected]> Reviewed-by: Todd Neal <[email protected]>
1 parent aebf661 commit a3055af

9 files changed

Lines changed: 795 additions & 3 deletions

File tree

‎src/cmd/compile/internal/gc/ssa.go‎

Lines changed: 29 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3904,10 +3904,11 @@ func (s *genState) genValue(v *ssa.Value) {
39043904
j2.To.Val = Pc
39053905
}
39063906

3907-
case ssa.OpAMD64HMULL, ssa.OpAMD64HMULW, ssa.OpAMD64HMULB,
3908-
ssa.OpAMD64HMULLU, ssa.OpAMD64HMULWU, ssa.OpAMD64HMULBU:
3907+
case ssa.OpAMD64HMULQ, ssa.OpAMD64HMULL, ssa.OpAMD64HMULW, ssa.OpAMD64HMULB,
3908+
ssa.OpAMD64HMULQU, ssa.OpAMD64HMULLU, ssa.OpAMD64HMULWU, ssa.OpAMD64HMULBU:
39093909
// the frontend rewrites constant division by 8/16/32 bit integers into
39103910
// HMUL by a constant
3911+
// SSA rewrites generate the 64 bit versions
39113912

39123913
// Arg[0] is already in AX as it's the only register we allow
39133914
// and DX is the only output we care about (the high bits)
@@ -3925,6 +3926,32 @@ func (s *genState) genValue(v *ssa.Value) {
39253926
m.To.Reg = x86.REG_DX
39263927
}
39273928

3929+
case ssa.OpAMD64AVGQU:
3930+
// compute (x+y)/2 unsigned.
3931+
// Do a 64-bit add, the overflow goes into the carry.
3932+
// Shift right once and pull the carry back into the 63rd bit.
3933+
r := regnum(v)
3934+
x := regnum(v.Args[0])
3935+
y := regnum(v.Args[1])
3936+
if x != r && y != r {
3937+
opregreg(moveByType(v.Type), r, x)
3938+
x = r
3939+
}
3940+
p := Prog(x86.AADDQ)
3941+
p.From.Type = obj.TYPE_REG
3942+
p.To.Type = obj.TYPE_REG
3943+
p.To.Reg = r
3944+
if x == r {
3945+
p.From.Reg = y
3946+
} else {
3947+
p.From.Reg = x
3948+
}
3949+
p = Prog(x86.ARCRQ)
3950+
p.From.Type = obj.TYPE_CONST
3951+
p.From.Offset = 1
3952+
p.To.Type = obj.TYPE_REG
3953+
p.To.Reg = r
3954+
39283955
case ssa.OpAMD64SHLQ, ssa.OpAMD64SHLL, ssa.OpAMD64SHLW, ssa.OpAMD64SHLB,
39293956
ssa.OpAMD64SHRQ, ssa.OpAMD64SHRL, ssa.OpAMD64SHRW, ssa.OpAMD64SHRB,
39303957
ssa.OpAMD64SARQ, ssa.OpAMD64SARL, ssa.OpAMD64SARW, ssa.OpAMD64SARB:

‎src/cmd/compile/internal/ssa/gen/AMD64.rules‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -45,13 +45,17 @@
4545
(Div8 x y) -> (DIVW (SignExt8to16 x) (SignExt8to16 y))
4646
(Div8u x y) -> (DIVWU (ZeroExt8to16 x) (ZeroExt8to16 y))
4747

48+
(Hmul64 x y) -> (HMULQ x y)
49+
(Hmul64u x y) -> (HMULQU x y)
4850
(Hmul32 x y) -> (HMULL x y)
4951
(Hmul32u x y) -> (HMULLU x y)
5052
(Hmul16 x y) -> (HMULW x y)
5153
(Hmul16u x y) -> (HMULWU x y)
5254
(Hmul8 x y) -> (HMULB x y)
5355
(Hmul8u x y) -> (HMULBU x y)
5456

57+
(Avg64u x y) -> (AVGQU x y)
58+
5559
(Mod64 x y) -> (MODQ x y)
5660
(Mod64u x y) -> (MODQU x y)
5761
(Mod32 x y) -> (MODL x y)

‎src/cmd/compile/internal/ssa/gen/AMD64Ops.go‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -193,13 +193,17 @@ func init() {
193193
{name: "MULWconst", reg: gp11, asm: "IMULW", aux: "Int16"}, // arg0 * auxint
194194
{name: "MULBconst", reg: gp11, asm: "IMULW", aux: "Int8"}, // arg0 * auxint
195195

196+
{name: "HMULQ", reg: gp11hmul, asm: "IMULQ"}, // (arg0 * arg1) >> width
196197
{name: "HMULL", reg: gp11hmul, asm: "IMULL"}, // (arg0 * arg1) >> width
197198
{name: "HMULW", reg: gp11hmul, asm: "IMULW"}, // (arg0 * arg1) >> width
198199
{name: "HMULB", reg: gp11hmul, asm: "IMULB"}, // (arg0 * arg1) >> width
200+
{name: "HMULQU", reg: gp11hmul, asm: "MULQ"}, // (arg0 * arg1) >> width
199201
{name: "HMULLU", reg: gp11hmul, asm: "MULL"}, // (arg0 * arg1) >> width
200202
{name: "HMULWU", reg: gp11hmul, asm: "MULW"}, // (arg0 * arg1) >> width
201203
{name: "HMULBU", reg: gp11hmul, asm: "MULB"}, // (arg0 * arg1) >> width
202204

205+
{name: "AVGQU", reg: gp21}, // (arg0 + arg1) / 2 as unsigned, all 64 result bits
206+
203207
{name: "DIVQ", reg: gp11div, asm: "IDIVQ"}, // arg0 / arg1
204208
{name: "DIVL", reg: gp11div, asm: "IDIVL"}, // arg0 / arg1
205209
{name: "DIVW", reg: gp11div, asm: "IDIVW"}, // arg0 / arg1

‎src/cmd/compile/internal/ssa/gen/generic.rules‎

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -514,3 +514,100 @@
514514
(Arg <t.FieldType(1)> {n} [off+t.FieldOff(1)])
515515
(Arg <t.FieldType(2)> {n} [off+t.FieldOff(2)])
516516
(Arg <t.FieldType(3)> {n} [off+t.FieldOff(3)]))
517+
518+
// strength reduction of divide by a constant.
519+
// Note: frontend does <=32 bits. We only need to do 64 bits here.
520+
// TODO: Do them all here?
521+
522+
// Div/mod by 1. Currently handled by frontend.
523+
//(Div64 n (Const64 [1])) -> n
524+
//(Div64u n (Const64 [1])) -> n
525+
//(Mod64 n (Const64 [1])) -> (Const64 [0])
526+
//(Mod64u n (Const64 [1])) -> (Const64 [0])
527+
528+
// Unsigned divide by power of 2. Currently handled by frontend.
529+
//(Div64u <t> n (Const64 [c])) && isPowerOfTwo(c) -> (Rsh64Ux64 n (Const64 <t> [log2(c)]))
530+
//(Mod64u <t> n (Const64 [c])) && isPowerOfTwo(c) -> (And64 n (Const64 <t> [c-1]))
531+
532+
// Signed divide by power of 2. Currently handled by frontend.
533+
// n / c = n >> log(c) if n >= 0
534+
// = (n+c-1) >> log(c) if n < 0
535+
// We conditionally add c-1 by adding n>>63>>(64-log(c)) (first shift signed, second shift unsigned).
536+
//(Div64 <t> n (Const64 [c])) && isPowerOfTwo(c) ->
537+
// (Rsh64x64
538+
// (Add64 <t>
539+
// n
540+
// (Rsh64Ux64 <t>
541+
// (Rsh64x64 <t> n (Const64 <t> [63]))
542+
// (Const64 <t> [64-log2(c)])))
543+
// (Const64 <t> [log2(c)]))
544+
545+
// Unsigned divide, not a power of 2. Strength reduce to a multiply.
546+
(Div64u <t> x (Const64 [c])) && umagic64ok(c) && !umagic64a(c) ->
547+
(Rsh64Ux64
548+
(Hmul64u <t>
549+
(Const64 <t> [umagic64m(c)])
550+
x)
551+
(Const64 <t> [umagic64s(c)]))
552+
(Div64u <t> x (Const64 [c])) && umagic64ok(c) && umagic64a(c) ->
553+
(Rsh64Ux64
554+
(Avg64u <t>
555+
(Hmul64u <t>
556+
x
557+
(Const64 <t> [umagic64m(c)]))
558+
x)
559+
(Const64 <t> [umagic64s(c)-1]))
560+
561+
// Signed divide, not a power of 2. Strength reduce to a multiply.
562+
(Div64 <t> x (Const64 [c])) && c > 0 && smagic64ok(c) && smagic64m(c) > 0 ->
563+
(Sub64 <t>
564+
(Rsh64x64 <t>
565+
(Hmul64 <t>
566+
(Const64 <t> [smagic64m(c)])
567+
x)
568+
(Const64 <t> [smagic64s(c)]))
569+
(Rsh64x64 <t>
570+
x
571+
(Const64 <t> [63])))
572+
(Div64 <t> x (Const64 [c])) && c > 0 && smagic64ok(c) && smagic64m(c) < 0 ->
573+
(Sub64 <t>
574+
(Rsh64x64 <t>
575+
(Add64 <t>
576+
(Hmul64 <t>
577+
(Const64 <t> [smagic64m(c)])
578+
x)
579+
x)
580+
(Const64 <t> [smagic64s(c)]))
581+
(Rsh64x64 <t>
582+
x
583+
(Const64 <t> [63])))
584+
(Div64 <t> x (Const64 [c])) && c < 0 && smagic64ok(c) && smagic64m(c) > 0 ->
585+
(Neg64 <t>
586+
(Sub64 <t>
587+
(Rsh64x64 <t>
588+
(Hmul64 <t>
589+
(Const64 <t> [smagic64m(c)])
590+
x)
591+
(Const64 <t> [smagic64s(c)]))
592+
(Rsh64x64 <t>
593+
x
594+
(Const64 <t> [63]))))
595+
(Div64 <t> x (Const64 [c])) && c < 0 && smagic64ok(c) && smagic64m(c) < 0 ->
596+
(Neg64 <t>
597+
(Sub64 <t>
598+
(Rsh64x64 <t>
599+
(Add64 <t>
600+
(Hmul64 <t>
601+
(Const64 <t> [smagic64m(c)])
602+
x)
603+
x)
604+
(Const64 <t> [smagic64s(c)]))
605+
(Rsh64x64 <t>
606+
x
607+
(Const64 <t> [63]))))
608+
609+
// A%B = A-(A/B*B).
610+
// This implements % with two * and a bunch of ancillary ops.
611+
// One of the * is free if the user's code also computes A/B.
612+
(Mod64 <t> x (Const64 [c])) && smagic64ok(c) -> (Sub64 x (Mul64 <t> (Div64 <t> x (Const64 <t> [c])) (Const64 <t> [c])))
613+
(Mod64u <t> x (Const64 [c])) && umagic64ok(c) -> (Sub64 x (Mul64 <t> (Div64u <t> x (Const64 <t> [c])) (Const64 <t> [c])))

‎src/cmd/compile/internal/ssa/gen/genericOps.go‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,11 @@ var genericOps = []opData{
4141
{name: "Hmul16u"},
4242
{name: "Hmul32"},
4343
{name: "Hmul32u"},
44-
// frontend currently doesn't generate a 64 bit hmul
44+
{name: "Hmul64"},
45+
{name: "Hmul64u"},
46+
47+
// Weird special instruction for strength reduction of divides.
48+
{name: "Avg64u"}, // (uint64(arg0) + uint64(arg1)) / 2, correct to all 64 bits.
4549

4650
{name: "Div8"}, // arg0 / arg1
4751
{name: "Div8u"},

0 commit comments

Comments
 (0)