From 3621600c9207adc9d493e4f60ff74069d58518ca Mon Sep 17 00:00:00 2001 From: Matthew Dempsky Date: Fri, 11 Mar 2016 00:23:37 -0800 Subject: [PATCH] cmd/compile: give "magic" code its own source file This code is an eye sore to keep scrolling past in subr.go, so move it out of the way. Change-Id: I8eafc1725d868a4924ee7ca9b7738cce309f9eff Reviewed-on: https://go-review.googlesource.com/20592 Reviewed-by: Dave Cheney --- src/cmd/compile/internal/gc/go.go | 17 --- src/cmd/compile/internal/gc/magic.go | 220 +++++++++++++++++++++++++++ src/cmd/compile/internal/gc/subr.go | 196 ------------------------ 3 files changed, 220 insertions(+), 213 deletions(-) create mode 100644 src/cmd/compile/internal/gc/magic.go diff --git a/src/cmd/compile/internal/gc/go.go b/src/cmd/compile/internal/gc/go.go index c98637c893..bd7114d033 100644 --- a/src/cmd/compile/internal/gc/go.go +++ b/src/cmd/compile/internal/gc/go.go @@ -191,23 +191,6 @@ type Sig struct { offset int32 } -// argument passing to/from -// smagic and umagic -type Magic struct { - W int // input for both - width - S int // output for both - shift - Bad int // output for both - unexpected failure - - // magic multiplier for signed literal divisors - Sd int64 // input - literal divisor - Sm int64 // output - multiplier - - // magic multiplier for unsigned literal divisors - Ud uint64 // input - literal divisor - Um uint64 // output - multiplier - Ua int // output - adder -} - // note this is the runtime representation // of the compilers arrays. // diff --git a/src/cmd/compile/internal/gc/magic.go b/src/cmd/compile/internal/gc/magic.go new file mode 100644 index 0000000000..f8eb18208f --- /dev/null +++ b/src/cmd/compile/internal/gc/magic.go @@ -0,0 +1,220 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package gc + +// Transmogrify slow integer division into fast multiplication using magic. + +// argument passing to/from +// smagic and umagic +type Magic struct { + W int // input for both - width + S int // output for both - shift + Bad int // output for both - unexpected failure + + // magic multiplier for signed literal divisors + Sd int64 // input - literal divisor + Sm int64 // output - multiplier + + // magic multiplier for unsigned literal divisors + Ud uint64 // input - literal divisor + Um uint64 // output - multiplier + Ua int // output - adder +} + +// magic number for signed division +// see hacker's delight chapter 10 +func Smagic(m *Magic) { + var mask uint64 + + m.Bad = 0 + switch m.W { + default: + m.Bad = 1 + return + + case 8: + mask = 0xff + + case 16: + mask = 0xffff + + case 32: + mask = 0xffffffff + + case 64: + mask = 0xffffffffffffffff + } + + two31 := mask ^ (mask >> 1) + + p := m.W - 1 + ad := uint64(m.Sd) + if m.Sd < 0 { + ad = -uint64(m.Sd) + } + + // bad denominators + if ad == 0 || ad == 1 || ad == two31 { + m.Bad = 1 + return + } + + t := two31 + ad &= mask + + anc := t - 1 - t%ad + anc &= mask + + q1 := two31 / anc + r1 := two31 - q1*anc + q1 &= mask + r1 &= mask + + q2 := two31 / ad + r2 := two31 - q2*ad + q2 &= mask + r2 &= mask + + var delta uint64 + for { + p++ + q1 <<= 1 + r1 <<= 1 + q1 &= mask + r1 &= mask + if r1 >= anc { + q1++ + r1 -= anc + q1 &= mask + r1 &= mask + } + + q2 <<= 1 + r2 <<= 1 + q2 &= mask + r2 &= mask + if r2 >= ad { + q2++ + r2 -= ad + q2 &= mask + r2 &= mask + } + + delta = ad - r2 + delta &= mask + if q1 < delta || (q1 == delta && r1 == 0) { + continue + } + + break + } + + m.Sm = int64(q2 + 1) + if uint64(m.Sm)&two31 != 0 { + m.Sm |= ^int64(mask) + } + m.S = p - m.W +} + +// magic number for unsigned division +// see hacker's delight chapter 10 +func Umagic(m *Magic) { + var mask uint64 + + m.Bad = 0 + m.Ua = 0 + + switch m.W { + default: + m.Bad = 1 + return + + case 8: + mask = 0xff + + case 16: + mask = 0xffff + + case 32: + mask = 0xffffffff + + case 64: + mask = 0xffffffffffffffff + } + + two31 := mask ^ (mask >> 1) + + m.Ud &= mask + if m.Ud == 0 || m.Ud == two31 { + m.Bad = 1 + return + } + + nc := mask - (-m.Ud&mask)%m.Ud + p := m.W - 1 + + q1 := two31 / nc + r1 := two31 - q1*nc + q1 &= mask + r1 &= mask + + q2 := (two31 - 1) / m.Ud + r2 := (two31 - 1) - q2*m.Ud + q2 &= mask + r2 &= mask + + var delta uint64 + for { + p++ + if r1 >= nc-r1 { + q1 <<= 1 + q1++ + r1 <<= 1 + r1 -= nc + } else { + q1 <<= 1 + r1 <<= 1 + } + + q1 &= mask + r1 &= mask + if r2+1 >= m.Ud-r2 { + if q2 >= two31-1 { + m.Ua = 1 + } + + q2 <<= 1 + q2++ + r2 <<= 1 + r2++ + r2 -= m.Ud + } else { + if q2 >= two31 { + m.Ua = 1 + } + + q2 <<= 1 + r2 <<= 1 + r2++ + } + + q2 &= mask + r2 &= mask + + delta = m.Ud - 1 - r2 + delta &= mask + + if p < m.W+m.W { + if q1 < delta || (q1 == delta && r1 == 0) { + continue + } + } + + break + } + + m.Um = q2 + 1 + m.S = p - m.W +} diff --git a/src/cmd/compile/internal/gc/subr.go b/src/cmd/compile/internal/gc/subr.go index 2933d90555..9a7e6b68c2 100644 --- a/src/cmd/compile/internal/gc/subr.go +++ b/src/cmd/compile/internal/gc/subr.go @@ -2286,202 +2286,6 @@ func tounsigned(t *Type) *Type { return t } -// magic number for signed division -// see hacker's delight chapter 10 -func Smagic(m *Magic) { - var mask uint64 - - m.Bad = 0 - switch m.W { - default: - m.Bad = 1 - return - - case 8: - mask = 0xff - - case 16: - mask = 0xffff - - case 32: - mask = 0xffffffff - - case 64: - mask = 0xffffffffffffffff - } - - two31 := mask ^ (mask >> 1) - - p := m.W - 1 - ad := uint64(m.Sd) - if m.Sd < 0 { - ad = -uint64(m.Sd) - } - - // bad denominators - if ad == 0 || ad == 1 || ad == two31 { - m.Bad = 1 - return - } - - t := two31 - ad &= mask - - anc := t - 1 - t%ad - anc &= mask - - q1 := two31 / anc - r1 := two31 - q1*anc - q1 &= mask - r1 &= mask - - q2 := two31 / ad - r2 := two31 - q2*ad - q2 &= mask - r2 &= mask - - var delta uint64 - for { - p++ - q1 <<= 1 - r1 <<= 1 - q1 &= mask - r1 &= mask - if r1 >= anc { - q1++ - r1 -= anc - q1 &= mask - r1 &= mask - } - - q2 <<= 1 - r2 <<= 1 - q2 &= mask - r2 &= mask - if r2 >= ad { - q2++ - r2 -= ad - q2 &= mask - r2 &= mask - } - - delta = ad - r2 - delta &= mask - if q1 < delta || (q1 == delta && r1 == 0) { - continue - } - - break - } - - m.Sm = int64(q2 + 1) - if uint64(m.Sm)&two31 != 0 { - m.Sm |= ^int64(mask) - } - m.S = p - m.W -} - -// magic number for unsigned division -// see hacker's delight chapter 10 -func Umagic(m *Magic) { - var mask uint64 - - m.Bad = 0 - m.Ua = 0 - - switch m.W { - default: - m.Bad = 1 - return - - case 8: - mask = 0xff - - case 16: - mask = 0xffff - - case 32: - mask = 0xffffffff - - case 64: - mask = 0xffffffffffffffff - } - - two31 := mask ^ (mask >> 1) - - m.Ud &= mask - if m.Ud == 0 || m.Ud == two31 { - m.Bad = 1 - return - } - - nc := mask - (-m.Ud&mask)%m.Ud - p := m.W - 1 - - q1 := two31 / nc - r1 := two31 - q1*nc - q1 &= mask - r1 &= mask - - q2 := (two31 - 1) / m.Ud - r2 := (two31 - 1) - q2*m.Ud - q2 &= mask - r2 &= mask - - var delta uint64 - for { - p++ - if r1 >= nc-r1 { - q1 <<= 1 - q1++ - r1 <<= 1 - r1 -= nc - } else { - q1 <<= 1 - r1 <<= 1 - } - - q1 &= mask - r1 &= mask - if r2+1 >= m.Ud-r2 { - if q2 >= two31-1 { - m.Ua = 1 - } - - q2 <<= 1 - q2++ - r2 <<= 1 - r2++ - r2 -= m.Ud - } else { - if q2 >= two31 { - m.Ua = 1 - } - - q2 <<= 1 - r2 <<= 1 - r2++ - } - - q2 &= mask - r2 &= mask - - delta = m.Ud - 1 - r2 - delta &= mask - - if p < m.W+m.W { - if q1 < delta || (q1 == delta && r1 == 0) { - continue - } - } - - break - } - - m.Um = q2 + 1 - m.S = p - m.W -} - func ngotype(n *Node) *Sym { if n.Type != nil { return typenamesym(n.Type) -- 2.48.1