all: make copyright headers consistent with one space after period

[gostls13.git] / src / cmd / compile / internal / gc / reg.go

// Derived from Inferno utils/6c/reg.c
// http://code.google.com/p/inferno-os/source/browse/utils/6c/reg.c
//
//      Copyright © 1994-1999 Lucent Technologies Inc.  All rights reserved.
//      Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net)
//      Portions Copyright © 1997-1999 Vita Nuova Limited
//      Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com)
//      Portions Copyright © 2004,2006 Bruce Ellis
//      Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net)
//      Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
//      Portions Copyright © 2009 The Go Authors. All rights reserved.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

package gc

import (
        "bytes"
        "cmd/internal/obj"
        "cmd/internal/sys"
        "fmt"
        "sort"
        "strings"
)

// A Var represents a single variable that may be stored in a register.
// That variable may itself correspond to a hardware register,
// to represent the use of registers in the unoptimized instruction stream.
type Var struct {
        offset     int64
        node       *Node
        nextinnode *Var
        width      int
        id         int // index in vars
        name       int8
        etype      EType
        addr       int8
}

// Bits represents a set of Vars, stored as a bit set of var numbers
// (the index in vars, or equivalently v.id).
type Bits struct {
        b [BITS]uint64
}

const (
        BITS = 3
        NVAR = BITS * 64
)

var (
        vars [NVAR]Var // variables under consideration
        nvar int       // number of vars

        regbits uint64 // bits for hardware registers

        zbits   Bits // zero
        externs Bits // global variables
        params  Bits // function parameters and results
        ivar    Bits // function parameters (inputs)
        ovar    Bits // function results (outputs)
        consts  Bits // constant values
        addrs   Bits // variables with address taken
)

// A Reg is a wrapper around a single Prog (one instruction) that holds
// register optimization information while the optimizer runs.
// r->prog is the instruction.
type Reg struct {
        set  Bits // regopt variables written by this instruction.
        use1 Bits // regopt variables read by prog->from.
        use2 Bits // regopt variables read by prog->to.

        // refahead/refbehind are the regopt variables whose current
        // value may be used in the following/preceding instructions
        // up to a CALL (or the value is clobbered).
        refbehind Bits
        refahead  Bits

        // calahead/calbehind are similar, but for variables in
        // instructions that are reachable after hitting at least one
        // CALL.
        calbehind Bits
        calahead  Bits

        regdiff Bits
        act     Bits
        regu    uint64 // register used bitmap
}

// A Rgn represents a single regopt variable over a region of code
// where a register could potentially be dedicated to that variable.
// The code encompassed by a Rgn is defined by the flow graph,
// starting at enter, flood-filling forward while varno is refahead
// and backward while varno is refbehind, and following branches.
// A single variable may be represented by multiple disjoint Rgns and
// each Rgn may choose a different register for that variable.
// Registers are allocated to regions greedily in order of descending
// cost.
type Rgn struct {
        enter *Flow
        cost  int16
        varno int16
        regno int16
}

// The Plan 9 C compilers used a limit of 600 regions,
// but the yacc-generated parser in y.go has 3100 regions.
// We set MaxRgn large enough to handle that.
// There's not a huge cost to having too many regions:
// the main processing traces the live area for each variable,
// which is limited by the number of variables times the area,
// not the raw region count. If there are many regions, they
// are almost certainly small and easy to trace.
// The only operation that scales with region count is the
// sorting by cost, which uses sort.Sort and is therefore
// guaranteed n log n.
const MaxRgn = 6000

var (
        region  []Rgn
        nregion int
)

type rcmp []Rgn

func (x rcmp) Len() int {
        return len(x)
}

func (x rcmp) Swap(i, j int) {
        x[i], x[j] = x[j], x[i]
}

func (x rcmp) Less(i, j int) bool {
        p1 := &x[i]
        p2 := &x[j]
        if p1.cost != p2.cost {
                return int(p2.cost)-int(p1.cost) < 0
        }
        if p1.varno != p2.varno {
                return int(p2.varno)-int(p1.varno) < 0
        }
        if p1.enter != p2.enter {
                return int(p2.enter.Id-p1.enter.Id) < 0
        }
        return false
}

func setaddrs(bit Bits) {
        var i int
        var n int
        var v *Var
        var node *Node

        for bany(&bit) {
                // convert each bit to a variable
                i = bnum(&bit)

                node = vars[i].node
                n = int(vars[i].name)
                biclr(&bit, uint(i))

                // disable all pieces of that variable
                for i = 0; i < nvar; i++ {
                        v = &vars[i]
                        if v.node == node && int(v.name) == n {
                                v.addr = 2
                        }
                }
        }
}

var regnodes [64]*Node

func walkvardef(n *Node, f *Flow, active int) {
        var f1 *Flow
        var bn int
        var v *Var

        for f1 = f; f1 != nil; f1 = f1.S1 {
                if f1.Active == int32(active) {
                        break
                }
                f1.Active = int32(active)
                if f1.Prog.As == obj.AVARKILL && f1.Prog.To.Node == n {
                        break
                }
                for v, _ = n.Opt().(*Var); v != nil; v = v.nextinnode {
                        bn = v.id
                        biset(&(f1.Data.(*Reg)).act, uint(bn))
                }

                if f1.Prog.As == obj.ACALL {
                        break
                }
        }

        for f2 := f; f2 != f1; f2 = f2.S1 {
                if f2.S2 != nil {
                        walkvardef(n, f2.S2, active)
                }
        }
}

// add mov b,rn
// just after r
func addmove(r *Flow, bn int, rn int, f int) {
        p1 := Ctxt.NewProg()
        Clearp(p1)
        p1.Pc = 9999

        p := r.Prog
        p1.Link = p.Link
        p.Link = p1
        p1.Lineno = p.Lineno

        v := &vars[bn]

        a := &p1.To
        a.Offset = v.offset
        a.Etype = uint8(v.etype)
        a.Type = obj.TYPE_MEM
        a.Name = v.name
        a.Node = v.node
        a.Sym = Linksym(v.node.Sym)

        /* NOTE(rsc): 9g did
        if(a->etype == TARRAY)
                a->type = TYPE_ADDR;
        else if(a->sym == nil)
                a->type = TYPE_CONST;
        */
        p1.As = Thearch.Optoas(OAS, Types[uint8(v.etype)])

        // TODO(rsc): Remove special case here.
        if Thearch.LinkArch.InFamily(sys.MIPS64, sys.ARM, sys.ARM64, sys.PPC64) && v.etype == TBOOL {
                p1.As = Thearch.Optoas(OAS, Types[TUINT8])
        }
        p1.From.Type = obj.TYPE_REG
        p1.From.Reg = int16(rn)
        p1.From.Name = obj.NAME_NONE
        if f == 0 {
                p1.From = *a
                *a = obj.Addr{}
                a.Type = obj.TYPE_REG
                a.Reg = int16(rn)
        }

        if Debug['R'] != 0 && Debug['v'] != 0 {
                fmt.Printf("%v ===add=== %v\n", p, p1)
        }
        Ostats.Nspill++
}

func overlap_reg(o1 int64, w1 int, o2 int64, w2 int) bool {
        t1 := o1 + int64(w1)
        t2 := o2 + int64(w2)

        if t1 <= o2 || t2 <= o1 {
                return false
        }

        return true
}

func mkvar(f *Flow, a *obj.Addr) Bits {
        // mark registers used
        if a.Type == obj.TYPE_NONE {
                return zbits
        }

        r := f.Data.(*Reg)
        r.use1.b[0] |= Thearch.Doregbits(int(a.Index)) // TODO: Use RtoB

        var n int
        switch a.Type {
        default:
                regu := Thearch.Doregbits(int(a.Reg)) | Thearch.RtoB(int(a.Reg)) // TODO: Use RtoB
                if regu == 0 {
                        return zbits
                }
                bit := zbits
                bit.b[0] = regu
                return bit

                // TODO(rsc): Remove special case here.
        case obj.TYPE_ADDR:
                var bit Bits
                if Thearch.LinkArch.InFamily(sys.MIPS64, sys.ARM, sys.ARM64, sys.PPC64) {
                        goto memcase
                }
                a.Type = obj.TYPE_MEM
                bit = mkvar(f, a)
                setaddrs(bit)
                a.Type = obj.TYPE_ADDR
                Ostats.Naddr++
                return zbits

        memcase:
                fallthrough

        case obj.TYPE_MEM:
                if r != nil {
                        r.use1.b[0] |= Thearch.RtoB(int(a.Reg))
                }

                /* NOTE: 5g did
                if(r->f.prog->scond & (C_PBIT|C_WBIT))
                        r->set.b[0] |= RtoB(a->reg);
                */
                switch a.Name {
                default:
                        // Note: This case handles NAME_EXTERN and NAME_STATIC.
                        // We treat these as requiring eager writes to memory, due to
                        // the possibility of a fault handler looking at them, so there is
                        // not much point in registerizing the loads.
                        // If we later choose the set of candidate variables from a
                        // larger list, these cases could be deprioritized instead of
                        // removed entirely.
                        return zbits

                case obj.NAME_PARAM,
                        obj.NAME_AUTO:
                        n = int(a.Name)
                }
        }

        node, _ := a.Node.(*Node)
        if node == nil || node.Op != ONAME || node.Orig == nil {
                return zbits
        }
        node = node.Orig
        if node.Orig != node {
                Fatalf("%v: bad node", Ctxt.Dconv(a))
        }
        if node.Sym == nil || node.Sym.Name[0] == '.' {
                return zbits
        }
        et := EType(a.Etype)
        o := a.Offset
        w := a.Width
        if w < 0 {
                Fatalf("bad width %d for %v", w, Ctxt.Dconv(a))
        }

        flag := 0
        var v *Var
        for i := 0; i < nvar; i++ {
                v = &vars[i]
                if v.node == node && int(v.name) == n {
                        if v.offset == o {
                                if v.etype == et {
                                        if int64(v.width) == w {
                                                // TODO(rsc): Remove special case for arm here.
                                                if flag == 0 || Thearch.LinkArch.Family != sys.ARM {
                                                        return blsh(uint(i))
                                                }
                                        }
                                }
                        }

                        // if they overlap, disable both
                        if overlap_reg(v.offset, v.width, o, int(w)) {
                                //                              print("disable overlap %s %d %d %d %d, %E != %E\n", s->name, v->offset, v->width, o, w, v->etype, et);
                                v.addr = 1

                                flag = 1
                        }
                }
        }

        switch et {
        case 0, TFUNC:
                return zbits
        }

        if nvar >= NVAR {
                if Debug['w'] > 1 && node != nil {
                        Fatalf("variable not optimized: %v", Nconv(node, FmtSharp))
                }
                if Debug['v'] > 0 {
                        Warn("variable not optimized: %v", Nconv(node, FmtSharp))
                }

                // If we're not tracking a word in a variable, mark the rest as
                // having its address taken, so that we keep the whole thing
                // live at all calls. otherwise we might optimize away part of
                // a variable but not all of it.
                var v *Var
                for i := 0; i < nvar; i++ {
                        v = &vars[i]
                        if v.node == node {
                                v.addr = 1
                        }
                }

                return zbits
        }

        i := nvar
        nvar++
        v = &vars[i]
        v.id = i
        v.offset = o
        v.name = int8(n)
        v.etype = et
        v.width = int(w)
        v.addr = int8(flag) // funny punning
        v.node = node

        // node->opt is the head of a linked list
        // of Vars within the given Node, so that
        // we can start at a Var and find all the other
        // Vars in the same Go variable.
        v.nextinnode, _ = node.Opt().(*Var)

        node.SetOpt(v)

        bit := blsh(uint(i))
        if n == obj.NAME_EXTERN || n == obj.NAME_STATIC {
                for z := 0; z < BITS; z++ {
                        externs.b[z] |= bit.b[z]
                }
        }
        if n == obj.NAME_PARAM {
                for z := 0; z < BITS; z++ {
                        params.b[z] |= bit.b[z]
                }
        }

        if node.Class == PPARAM {
                for z := 0; z < BITS; z++ {
                        ivar.b[z] |= bit.b[z]
                }
        }
        if node.Class == PPARAMOUT {
                for z := 0; z < BITS; z++ {
                        ovar.b[z] |= bit.b[z]
                }
        }

        // Treat values with their address taken as live at calls,
        // because the garbage collector's liveness analysis in plive.go does.
        // These must be consistent or else we will elide stores and the garbage
        // collector will see uninitialized data.
        // The typical case where our own analysis is out of sync is when the
        // node appears to have its address taken but that code doesn't actually
        // get generated and therefore doesn't show up as an address being
        // taken when we analyze the instruction stream.
        // One instance of this case is when a closure uses the same name as
        // an outer variable for one of its own variables declared with :=.
        // The parser flags the outer variable as possibly shared, and therefore
        // sets addrtaken, even though it ends up not being actually shared.
        // If we were better about _ elision, _ = &x would suffice too.
        // The broader := in a closure problem is mentioned in a comment in
        // closure.go:/^typecheckclosure and dcl.go:/^oldname.
        if node.Addrtaken {
                v.addr = 1
        }

        // Disable registerization for globals, because:
        // (1) we might panic at any time and we want the recovery code
        // to see the latest values (issue 1304).
        // (2) we don't know what pointers might point at them and we want
        // loads via those pointers to see updated values and vice versa (issue 7995).
        //
        // Disable registerization for results if using defer, because the deferred func
        // might recover and return, causing the current values to be used.
        if node.Class == PEXTERN || (hasdefer && node.Class == PPARAMOUT) {
                v.addr = 1
        }

        if Debug['R'] != 0 {
                fmt.Printf("bit=%2d et=%v w=%d+%d %v %v flag=%d\n", i, et, o, w, Nconv(node, FmtSharp), Ctxt.Dconv(a), v.addr)
        }
        Ostats.Nvar++

        return bit
}

var change int

func prop(f *Flow, ref Bits, cal Bits) {
        var f1 *Flow
        var r1 *Reg
        var z int
        var i int
        var v *Var
        var v1 *Var

        for f1 = f; f1 != nil; f1 = f1.P1 {
                r1 = f1.Data.(*Reg)
                for z = 0; z < BITS; z++ {
                        ref.b[z] |= r1.refahead.b[z]
                        if ref.b[z] != r1.refahead.b[z] {
                                r1.refahead.b[z] = ref.b[z]
                                change = 1
                        }

                        cal.b[z] |= r1.calahead.b[z]
                        if cal.b[z] != r1.calahead.b[z] {
                                r1.calahead.b[z] = cal.b[z]
                                change = 1
                        }
                }

                switch f1.Prog.As {
                case obj.ACALL:
                        if Noreturn(f1.Prog) {
                                break
                        }

                        // Mark all input variables (ivar) as used, because that's what the
                        // liveness bitmaps say. The liveness bitmaps say that so that a
                        // panic will not show stale values in the parameter dump.
                        // Mark variables with a recent VARDEF (r1->act) as used,
                        // so that the optimizer flushes initializations to memory,
                        // so that if a garbage collection happens during this CALL,
                        // the collector will see initialized memory. Again this is to
                        // match what the liveness bitmaps say.
                        for z = 0; z < BITS; z++ {
                                cal.b[z] |= ref.b[z] | externs.b[z] | ivar.b[z] | r1.act.b[z]
                                ref.b[z] = 0
                        }

                        // cal.b is the current approximation of what's live across the call.
                        // Every bit in cal.b is a single stack word. For each such word,
                        // find all the other tracked stack words in the same Go variable
                        // (struct/slice/string/interface) and mark them live too.
                        // This is necessary because the liveness analysis for the garbage
                        // collector works at variable granularity, not at word granularity.
                        // It is fundamental for slice/string/interface: the garbage collector
                        // needs the whole value, not just some of the words, in order to
                        // interpret the other bits correctly. Specifically, slice needs a consistent
                        // ptr and cap, string needs a consistent ptr and len, and interface
                        // needs a consistent type word and data word.
                        for z = 0; z < BITS; z++ {
                                if cal.b[z] == 0 {
                                        continue
                                }
                                for i = 0; i < 64; i++ {
                                        if z*64+i >= nvar || (cal.b[z]>>uint(i))&1 == 0 {
                                                continue
                                        }
                                        v = &vars[z*64+i]
                                        if v.node.Opt() == nil { // v represents fixed register, not Go variable
                                                continue
                                        }

                                        // v->node->opt is the head of a linked list of Vars
                                        // corresponding to tracked words from the Go variable v->node.
                                        // Walk the list and set all the bits.
                                        // For a large struct this could end up being quadratic:
                                        // after the first setting, the outer loop (for z, i) would see a 1 bit
                                        // for all of the remaining words in the struct, and for each such
                                        // word would go through and turn on all the bits again.
                                        // To avoid the quadratic behavior, we only turn on the bits if
                                        // v is the head of the list or if the head's bit is not yet turned on.
                                        // This will set the bits at most twice, keeping the overall loop linear.
                                        v1, _ = v.node.Opt().(*Var)

                                        if v == v1 || !btest(&cal, uint(v1.id)) {
                                                for ; v1 != nil; v1 = v1.nextinnode {
                                                        biset(&cal, uint(v1.id))
                                                }
                                        }
                                }
                        }

                case obj.ATEXT:
                        for z = 0; z < BITS; z++ {
                                cal.b[z] = 0
                                ref.b[z] = 0
                        }

                case obj.ARET:
                        for z = 0; z < BITS; z++ {
                                cal.b[z] = externs.b[z] | ovar.b[z]
                                ref.b[z] = 0
                        }
                }

                for z = 0; z < BITS; z++ {
                        ref.b[z] = ref.b[z]&^r1.set.b[z] | r1.use1.b[z] | r1.use2.b[z]
                        cal.b[z] &^= (r1.set.b[z] | r1.use1.b[z] | r1.use2.b[z])
                        r1.refbehind.b[z] = ref.b[z]
                        r1.calbehind.b[z] = cal.b[z]
                }

                if f1.Active != 0 {
                        break
                }
                f1.Active = 1
        }

        var r *Reg
        var f2 *Flow
        for ; f != f1; f = f.P1 {
                r = f.Data.(*Reg)
                for f2 = f.P2; f2 != nil; f2 = f2.P2link {
                        prop(f2, r.refbehind, r.calbehind)
                }
        }
}

func synch(f *Flow, dif Bits) {
        var r1 *Reg
        var z int

        for f1 := f; f1 != nil; f1 = f1.S1 {
                r1 = f1.Data.(*Reg)
                for z = 0; z < BITS; z++ {
                        dif.b[z] = dif.b[z]&^(^r1.refbehind.b[z]&r1.refahead.b[z]) | r1.set.b[z] | r1.regdiff.b[z]
                        if dif.b[z] != r1.regdiff.b[z] {
                                r1.regdiff.b[z] = dif.b[z]
                                change = 1
                        }
                }

                if f1.Active != 0 {
                        break
                }
                f1.Active = 1
                for z = 0; z < BITS; z++ {
                        dif.b[z] &^= (^r1.calbehind.b[z] & r1.calahead.b[z])
                }
                if f1.S2 != nil {
                        synch(f1.S2, dif)
                }
        }
}

func allreg(b uint64, r *Rgn) uint64 {
        v := &vars[r.varno]
        r.regno = 0
        switch v.etype {
        default:
                Fatalf("unknown etype %d/%v", Bitno(b), v.etype)

        case TINT8,
                TUINT8,
                TINT16,
                TUINT16,
                TINT32,
                TUINT32,
                TINT64,
                TUINT64,
                TINT,
                TUINT,
                TUINTPTR,
                TBOOL,
                TPTR32,
                TPTR64:
                i := Thearch.BtoR(^b)
                if i != 0 && r.cost > 0 {
                        r.regno = int16(i)
                        return Thearch.RtoB(i)
                }

        case TFLOAT32, TFLOAT64:
                i := Thearch.BtoF(^b)
                if i != 0 && r.cost > 0 {
                        r.regno = int16(i)
                        return Thearch.FtoB(i)
                }
        }

        return 0
}

func LOAD(r *Reg, z int) uint64 {
        return ^r.refbehind.b[z] & r.refahead.b[z]
}

func STORE(r *Reg, z int) uint64 {
        return ^r.calbehind.b[z] & r.calahead.b[z]
}

// Cost parameters
const (
        CLOAD = 5 // cost of load
        CREF  = 5 // cost of reference if not registerized
        LOOP  = 3 // loop execution count (applied in popt.go)
)

func paint1(f *Flow, bn int) {
        z := bn / 64
        bb := uint64(1 << uint(bn%64))
        r := f.Data.(*Reg)
        if r.act.b[z]&bb != 0 {
                return
        }
        var f1 *Flow
        var r1 *Reg
        for {
                if r.refbehind.b[z]&bb == 0 {
                        break
                }
                f1 = f.P1
                if f1 == nil {
                        break
                }
                r1 = f1.Data.(*Reg)
                if r1.refahead.b[z]&bb == 0 {
                        break
                }
                if r1.act.b[z]&bb != 0 {
                        break
                }
                f = f1
                r = r1
        }

        if LOAD(r, z)&^(r.set.b[z]&^(r.use1.b[z]|r.use2.b[z]))&bb != 0 {
                change -= CLOAD * int(f.Loop)
        }

        for {
                r.act.b[z] |= bb

                if f.Prog.As != obj.ANOP { // don't give credit for NOPs
                        if r.use1.b[z]&bb != 0 {
                                change += CREF * int(f.Loop)
                        }
                        if (r.use2.b[z]|r.set.b[z])&bb != 0 {
                                change += CREF * int(f.Loop)
                        }
                }

                if STORE(r, z)&r.regdiff.b[z]&bb != 0 {
                        change -= CLOAD * int(f.Loop)
                }

                if r.refbehind.b[z]&bb != 0 {
                        for f1 = f.P2; f1 != nil; f1 = f1.P2link {
                                if (f1.Data.(*Reg)).refahead.b[z]&bb != 0 {
                                        paint1(f1, bn)
                                }
                        }
                }

                if r.refahead.b[z]&bb == 0 {
                        break
                }
                f1 = f.S2
                if f1 != nil {
                        if (f1.Data.(*Reg)).refbehind.b[z]&bb != 0 {
                                paint1(f1, bn)
                        }
                }
                f = f.S1
                if f == nil {
                        break
                }
                r = f.Data.(*Reg)
                if r.act.b[z]&bb != 0 {
                        break
                }
                if r.refbehind.b[z]&bb == 0 {
                        break
                }
        }
}

func paint2(f *Flow, bn int, depth int) uint64 {
        z := bn / 64
        bb := uint64(1 << uint(bn%64))
        vreg := regbits
        r := f.Data.(*Reg)
        if r.act.b[z]&bb == 0 {
                return vreg
        }
        var r1 *Reg
        var f1 *Flow
        for {
                if r.refbehind.b[z]&bb == 0 {
                        break
                }
                f1 = f.P1
                if f1 == nil {
                        break
                }
                r1 = f1.Data.(*Reg)
                if r1.refahead.b[z]&bb == 0 {
                        break
                }
                if r1.act.b[z]&bb == 0 {
                        break
                }
                f = f1
                r = r1
        }

        for {
                if Debug['R'] != 0 && Debug['v'] != 0 {
                        fmt.Printf("  paint2 %d %v\n", depth, f.Prog)
                }

                r.act.b[z] &^= bb

                vreg |= r.regu

                if r.refbehind.b[z]&bb != 0 {
                        for f1 = f.P2; f1 != nil; f1 = f1.P2link {
                                if (f1.Data.(*Reg)).refahead.b[z]&bb != 0 {
                                        vreg |= paint2(f1, bn, depth+1)
                                }
                        }
                }

                if r.refahead.b[z]&bb == 0 {
                        break
                }
                f1 = f.S2
                if f1 != nil {
                        if (f1.Data.(*Reg)).refbehind.b[z]&bb != 0 {
                                vreg |= paint2(f1, bn, depth+1)
                        }
                }
                f = f.S1
                if f == nil {
                        break
                }
                r = f.Data.(*Reg)
                if r.act.b[z]&bb == 0 {
                        break
                }
                if r.refbehind.b[z]&bb == 0 {
                        break
                }
        }

        return vreg
}

func paint3(f *Flow, bn int, rb uint64, rn int) {
        z := bn / 64
        bb := uint64(1 << uint(bn%64))
        r := f.Data.(*Reg)
        if r.act.b[z]&bb != 0 {
                return
        }
        var r1 *Reg
        var f1 *Flow
        for {
                if r.refbehind.b[z]&bb == 0 {
                        break
                }
                f1 = f.P1
                if f1 == nil {
                        break
                }
                r1 = f1.Data.(*Reg)
                if r1.refahead.b[z]&bb == 0 {
                        break
                }
                if r1.act.b[z]&bb != 0 {
                        break
                }
                f = f1
                r = r1
        }

        if LOAD(r, z)&^(r.set.b[z]&^(r.use1.b[z]|r.use2.b[z]))&bb != 0 {
                addmove(f, bn, rn, 0)
        }
        var p *obj.Prog
        for {
                r.act.b[z] |= bb
                p = f.Prog

                if r.use1.b[z]&bb != 0 {
                        if Debug['R'] != 0 && Debug['v'] != 0 {
                                fmt.Printf("%v", p)
                        }
                        addreg(&p.From, rn)
                        if Debug['R'] != 0 && Debug['v'] != 0 {
                                fmt.Printf(" ===change== %v\n", p)
                        }
                }

                if (r.use2.b[z]|r.set.b[z])&bb != 0 {
                        if Debug['R'] != 0 && Debug['v'] != 0 {
                                fmt.Printf("%v", p)
                        }
                        addreg(&p.To, rn)
                        if Debug['R'] != 0 && Debug['v'] != 0 {
                                fmt.Printf(" ===change== %v\n", p)
                        }
                }

                if STORE(r, z)&r.regdiff.b[z]&bb != 0 {
                        addmove(f, bn, rn, 1)
                }
                r.regu |= rb

                if r.refbehind.b[z]&bb != 0 {
                        for f1 = f.P2; f1 != nil; f1 = f1.P2link {
                                if (f1.Data.(*Reg)).refahead.b[z]&bb != 0 {
                                        paint3(f1, bn, rb, rn)
                                }
                        }
                }

                if r.refahead.b[z]&bb == 0 {
                        break
                }
                f1 = f.S2
                if f1 != nil {
                        if (f1.Data.(*Reg)).refbehind.b[z]&bb != 0 {
                                paint3(f1, bn, rb, rn)
                        }
                }
                f = f.S1
                if f == nil {
                        break
                }
                r = f.Data.(*Reg)
                if r.act.b[z]&bb != 0 {
                        break
                }
                if r.refbehind.b[z]&bb == 0 {
                        break
                }
        }
}

func addreg(a *obj.Addr, rn int) {
        a.Sym = nil
        a.Node = nil
        a.Offset = 0
        a.Type = obj.TYPE_REG
        a.Reg = int16(rn)
        a.Name = 0

        Ostats.Ncvtreg++
}

func dumpone(f *Flow, isreg int) {
        fmt.Printf("%d:%v", f.Loop, f.Prog)
        if isreg != 0 {
                r := f.Data.(*Reg)
                var bit Bits
                for z := 0; z < BITS; z++ {
                        bit.b[z] = r.set.b[z] | r.use1.b[z] | r.use2.b[z] | r.refbehind.b[z] | r.refahead.b[z] | r.calbehind.b[z] | r.calahead.b[z] | r.regdiff.b[z] | r.act.b[z] | 0
                }
                if bany(&bit) {
                        fmt.Printf("\t")
                        if bany(&r.set) {
                                fmt.Printf(" s:%v", &r.set)
                        }
                        if bany(&r.use1) {
                                fmt.Printf(" u1:%v", &r.use1)
                        }
                        if bany(&r.use2) {
                                fmt.Printf(" u2:%v", &r.use2)
                        }
                        if bany(&r.refbehind) {
                                fmt.Printf(" rb:%v ", &r.refbehind)
                        }
                        if bany(&r.refahead) {
                                fmt.Printf(" ra:%v ", &r.refahead)
                        }
                        if bany(&r.calbehind) {
                                fmt.Printf(" cb:%v ", &r.calbehind)
                        }
                        if bany(&r.calahead) {
                                fmt.Printf(" ca:%v ", &r.calahead)
                        }
                        if bany(&r.regdiff) {
                                fmt.Printf(" d:%v ", &r.regdiff)
                        }
                        if bany(&r.act) {
                                fmt.Printf(" a:%v ", &r.act)
                        }
                }
        }

        fmt.Printf("\n")
}

func Dumpit(str string, r0 *Flow, isreg int) {
        var r1 *Flow

        fmt.Printf("\n%s\n", str)
        for r := r0; r != nil; r = r.Link {
                dumpone(r, isreg)
                r1 = r.P2
                if r1 != nil {
                        fmt.Printf("\tpred:")
                        for ; r1 != nil; r1 = r1.P2link {
                                fmt.Printf(" %.4d", uint(int(r1.Prog.Pc)))
                        }
                        if r.P1 != nil {
                                fmt.Printf(" (and %.4d)", uint(int(r.P1.Prog.Pc)))
                        } else {
                                fmt.Printf(" (only)")
                        }
                        fmt.Printf("\n")
                }

                // Print successors if it's not just the next one
                if r.S1 != r.Link || r.S2 != nil {
                        fmt.Printf("\tsucc:")
                        if r.S1 != nil {
                                fmt.Printf(" %.4d", uint(int(r.S1.Prog.Pc)))
                        }
                        if r.S2 != nil {
                                fmt.Printf(" %.4d", uint(int(r.S2.Prog.Pc)))
                        }
                        fmt.Printf("\n")
                }
        }
}

func regopt(firstp *obj.Prog) {
        mergetemp(firstp)

        // control flow is more complicated in generated go code
        // than in generated c code.  define pseudo-variables for
        // registers, so we have complete register usage information.
        var nreg int
        regnames := Thearch.Regnames(&nreg)

        nvar = nreg
        for i := 0; i < nreg; i++ {
                vars[i] = Var{}
        }
        for i := 0; i < nreg; i++ {
                if regnodes[i] == nil {
                        regnodes[i] = newname(Lookup(regnames[i]))
                }
                vars[i].node = regnodes[i]
        }

        regbits = Thearch.Excludedregs()
        externs = zbits
        params = zbits
        consts = zbits
        addrs = zbits
        ivar = zbits
        ovar = zbits

        // pass 1
        // build aux data structure
        // allocate pcs
        // find use and set of variables
        g := Flowstart(firstp, func() interface{} { return new(Reg) })
        if g == nil {
                for i := 0; i < nvar; i++ {
                        vars[i].node.SetOpt(nil)
                }
                return
        }

        firstf := g.Start

        for f := firstf; f != nil; f = f.Link {
                p := f.Prog
                // AVARLIVE must be considered a use, do not skip it.
                // Otherwise the variable will be optimized away,
                // and the whole point of AVARLIVE is to keep it on the stack.
                if p.As == obj.AVARDEF || p.As == obj.AVARKILL {
                        continue
                }

                // Avoid making variables for direct-called functions.
                if p.As == obj.ACALL && p.To.Type == obj.TYPE_MEM && p.To.Name == obj.NAME_EXTERN {
                        continue
                }

                // from vs to doesn't matter for registers.
                r := f.Data.(*Reg)
                r.use1.b[0] |= p.Info.Reguse | p.Info.Regindex
                r.set.b[0] |= p.Info.Regset

                bit := mkvar(f, &p.From)
                if bany(&bit) {
                        if p.Info.Flags&LeftAddr != 0 {
                                setaddrs(bit)
                        }
                        if p.Info.Flags&LeftRead != 0 {
                                for z := 0; z < BITS; z++ {
                                        r.use1.b[z] |= bit.b[z]
                                }
                        }
                        if p.Info.Flags&LeftWrite != 0 {
                                for z := 0; z < BITS; z++ {
                                        r.set.b[z] |= bit.b[z]
                                }
                        }
                }

                // Compute used register for reg
                if p.Info.Flags&RegRead != 0 {
                        r.use1.b[0] |= Thearch.RtoB(int(p.Reg))
                }

                // Currently we never generate three register forms.
                // If we do, this will need to change.
                if p.From3Type() != obj.TYPE_NONE && p.From3Type() != obj.TYPE_CONST {
                        Fatalf("regopt not implemented for from3")
                }

                bit = mkvar(f, &p.To)
                if bany(&bit) {
                        if p.Info.Flags&RightAddr != 0 {
                                setaddrs(bit)
                        }
                        if p.Info.Flags&RightRead != 0 {
                                for z := 0; z < BITS; z++ {
                                        r.use2.b[z] |= bit.b[z]
                                }
                        }
                        if p.Info.Flags&RightWrite != 0 {
                                for z := 0; z < BITS; z++ {
                                        r.set.b[z] |= bit.b[z]
                                }
                        }
                }
        }

        for i := 0; i < nvar; i++ {
                v := &vars[i]
                if v.addr != 0 {
                        bit := blsh(uint(i))
                        for z := 0; z < BITS; z++ {
                                addrs.b[z] |= bit.b[z]
                        }
                }

                if Debug['R'] != 0 && Debug['v'] != 0 {
                        fmt.Printf("bit=%2d addr=%d et=%v w=%-2d s=%v + %d\n", i, v.addr, v.etype, v.width, v.node, v.offset)
                }
        }

        if Debug['R'] != 0 && Debug['v'] != 0 {
                Dumpit("pass1", firstf, 1)
        }

        // pass 2
        // find looping structure
        flowrpo(g)

        if Debug['R'] != 0 && Debug['v'] != 0 {
                Dumpit("pass2", firstf, 1)
        }

        // pass 2.5
        // iterate propagating fat vardef covering forward
        // r->act records vars with a VARDEF since the last CALL.
        // (r->act will be reused in pass 5 for something else,
        // but we'll be done with it by then.)
        active := 0

        for f := firstf; f != nil; f = f.Link {
                f.Active = 0
                r := f.Data.(*Reg)
                r.act = zbits
        }

        for f := firstf; f != nil; f = f.Link {
                p := f.Prog
                if p.As == obj.AVARDEF && Isfat(((p.To.Node).(*Node)).Type) && ((p.To.Node).(*Node)).Opt() != nil {
                        active++
                        walkvardef(p.To.Node.(*Node), f, active)
                }
        }

        // pass 3
        // iterate propagating usage
        //      back until flow graph is complete
        var f1 *Flow
        var i int
        var f *Flow
loop1:
        change = 0

        for f = firstf; f != nil; f = f.Link {
                f.Active = 0
        }
        for f = firstf; f != nil; f = f.Link {
                if f.Prog.As == obj.ARET {
                        prop(f, zbits, zbits)
                }
        }

        // pick up unreachable code
loop11:
        i = 0

        for f = firstf; f != nil; f = f1 {
                f1 = f.Link
                if f1 != nil && f1.Active != 0 && f.Active == 0 {
                        prop(f, zbits, zbits)
                        i = 1
                }
        }

        if i != 0 {
                goto loop11
        }
        if change != 0 {
                goto loop1
        }

        if Debug['R'] != 0 && Debug['v'] != 0 {
                Dumpit("pass3", firstf, 1)
        }

        // pass 4
        // iterate propagating register/variable synchrony
        //      forward until graph is complete
loop2:
        change = 0

        for f = firstf; f != nil; f = f.Link {
                f.Active = 0
        }
        synch(firstf, zbits)
        if change != 0 {
                goto loop2
        }

        if Debug['R'] != 0 && Debug['v'] != 0 {
                Dumpit("pass4", firstf, 1)
        }

        // pass 4.5
        // move register pseudo-variables into regu.
        mask := uint64((1 << uint(nreg)) - 1)
        for f := firstf; f != nil; f = f.Link {
                r := f.Data.(*Reg)
                r.regu = (r.refbehind.b[0] | r.set.b[0]) & mask
                r.set.b[0] &^= mask
                r.use1.b[0] &^= mask
                r.use2.b[0] &^= mask
                r.refbehind.b[0] &^= mask
                r.refahead.b[0] &^= mask
                r.calbehind.b[0] &^= mask
                r.calahead.b[0] &^= mask
                r.regdiff.b[0] &^= mask
                r.act.b[0] &^= mask
        }

        if Debug['R'] != 0 && Debug['v'] != 0 {
                Dumpit("pass4.5", firstf, 1)
        }

        // pass 5
        // isolate regions
        // calculate costs (paint1)
        var bit Bits
        if f := firstf; f != nil {
                r := f.Data.(*Reg)
                for z := 0; z < BITS; z++ {
                        bit.b[z] = (r.refahead.b[z] | r.calahead.b[z]) &^ (externs.b[z] | params.b[z] | addrs.b[z] | consts.b[z])
                }
                if bany(&bit) && !f.Refset {
                        // should never happen - all variables are preset
                        if Debug['w'] != 0 {
                                fmt.Printf("%v: used and not set: %v\n", f.Prog.Line(), &bit)
                        }
                        f.Refset = true
                }
        }

        for f := firstf; f != nil; f = f.Link {
                (f.Data.(*Reg)).act = zbits
        }
        nregion = 0
        region = region[:0]
        for f := firstf; f != nil; f = f.Link {
                r := f.Data.(*Reg)
                for z := 0; z < BITS; z++ {
                        bit.b[z] = r.set.b[z] &^ (r.refahead.b[z] | r.calahead.b[z] | addrs.b[z])
                }
                if bany(&bit) && !f.Refset {
                        if Debug['w'] != 0 {
                                fmt.Printf("%v: set and not used: %v\n", f.Prog.Line(), &bit)
                        }
                        f.Refset = true
                        Thearch.Excise(f)
                }

                for z := 0; z < BITS; z++ {
                        bit.b[z] = LOAD(r, z) &^ (r.act.b[z] | addrs.b[z])
                }
                for bany(&bit) {
                        i = bnum(&bit)
                        change = 0
                        paint1(f, i)
                        biclr(&bit, uint(i))
                        if change <= 0 {
                                continue
                        }
                        if nregion >= MaxRgn {
                                nregion++
                                continue
                        }

                        region = append(region, Rgn{
                                enter: f,
                                cost:  int16(change),
                                varno: int16(i),
                        })
                        nregion++
                }
        }

        if false && Debug['v'] != 0 && strings.Contains(Curfn.Func.Nname.Sym.Name, "Parse") {
                Warn("regions: %d\n", nregion)
        }
        if nregion >= MaxRgn {
                if Debug['v'] != 0 {
                        Warn("too many regions: %d\n", nregion)
                }
                nregion = MaxRgn
        }

        sort.Sort(rcmp(region[:nregion]))

        if Debug['R'] != 0 && Debug['v'] != 0 {
                Dumpit("pass5", firstf, 1)
        }

        // pass 6
        // determine used registers (paint2)
        // replace code (paint3)
        if Debug['R'] != 0 && Debug['v'] != 0 {
                fmt.Printf("\nregisterizing\n")
        }
        for i := 0; i < nregion; i++ {
                rgp := &region[i]
                if Debug['R'] != 0 && Debug['v'] != 0 {
                        fmt.Printf("region %d: cost %d varno %d enter %d\n", i, rgp.cost, rgp.varno, rgp.enter.Prog.Pc)
                }
                bit = blsh(uint(rgp.varno))
                usedreg := paint2(rgp.enter, int(rgp.varno), 0)
                vreg := allreg(usedreg, rgp)
                if rgp.regno != 0 {
                        if Debug['R'] != 0 && Debug['v'] != 0 {
                                v := &vars[rgp.varno]
                                fmt.Printf("registerize %v+%d (bit=%2d et=%v) in %v usedreg=%#x vreg=%#x\n", v.node, v.offset, rgp.varno, v.etype, obj.Rconv(int(rgp.regno)), usedreg, vreg)
                        }

                        paint3(rgp.enter, int(rgp.varno), vreg, int(rgp.regno))
                }
        }

        // free aux structures. peep allocates new ones.
        for i := 0; i < nvar; i++ {
                vars[i].node.SetOpt(nil)
        }
        Flowend(g)
        firstf = nil

        if Debug['R'] != 0 && Debug['v'] != 0 {
                // Rebuild flow graph, since we inserted instructions
                g := Flowstart(firstp, nil)
                firstf = g.Start
                Dumpit("pass6", firstf, 0)
                Flowend(g)
                firstf = nil
        }

        // pass 7
        // peep-hole on basic block
        if Debug['R'] == 0 || Debug['P'] != 0 {
                Thearch.Peep(firstp)
        }

        // eliminate nops
        for p := firstp; p != nil; p = p.Link {
                for p.Link != nil && p.Link.As == obj.ANOP {
                        p.Link = p.Link.Link
                }
                if p.To.Type == obj.TYPE_BRANCH {
                        for p.To.Val.(*obj.Prog) != nil && p.To.Val.(*obj.Prog).As == obj.ANOP {
                                p.To.Val = p.To.Val.(*obj.Prog).Link
                        }
                }
        }

        if Debug['R'] != 0 {
                if Ostats.Ncvtreg != 0 || Ostats.Nspill != 0 || Ostats.Nreload != 0 || Ostats.Ndelmov != 0 || Ostats.Nvar != 0 || Ostats.Naddr != 0 || false {
                        fmt.Printf("\nstats\n")
                }

                if Ostats.Ncvtreg != 0 {
                        fmt.Printf("\t%4d cvtreg\n", Ostats.Ncvtreg)
                }
                if Ostats.Nspill != 0 {
                        fmt.Printf("\t%4d spill\n", Ostats.Nspill)
                }
                if Ostats.Nreload != 0 {
                        fmt.Printf("\t%4d reload\n", Ostats.Nreload)
                }
                if Ostats.Ndelmov != 0 {
                        fmt.Printf("\t%4d delmov\n", Ostats.Ndelmov)
                }
                if Ostats.Nvar != 0 {
                        fmt.Printf("\t%4d var\n", Ostats.Nvar)
                }
                if Ostats.Naddr != 0 {
                        fmt.Printf("\t%4d addr\n", Ostats.Naddr)
                }

                Ostats = OptStats{}
        }
}

// bany reports whether any bits in a are set.
func bany(a *Bits) bool {
        for _, x := range &a.b { // & to avoid making a copy of a.b
                if x != 0 {
                        return true
                }
        }
        return false
}

// bnum reports the lowest index of a 1 bit in a.
func bnum(a *Bits) int {
        for i, x := range &a.b { // & to avoid making a copy of a.b
                if x != 0 {
                        return 64*i + Bitno(x)
                }
        }

        Fatalf("bad in bnum")
        return 0
}

// blsh returns a Bits with 1 at index n, 0 elsewhere (1<<n).
func blsh(n uint) Bits {
        c := zbits
        c.b[n/64] = 1 << (n % 64)
        return c
}

// btest reports whether bit n is 1.
func btest(a *Bits, n uint) bool {
        return a.b[n/64]&(1<<(n%64)) != 0
}

// biset sets bit n to 1.
func biset(a *Bits, n uint) {
        a.b[n/64] |= 1 << (n % 64)
}

// biclr sets bit n to 0.
func biclr(a *Bits, n uint) {
        a.b[n/64] &^= (1 << (n % 64))
}

// Bitno reports the lowest index of a 1 bit in b.
// It calls Fatalf if there is no 1 bit.
func Bitno(b uint64) int {
        if b == 0 {
                Fatalf("bad in bitno")
        }
        n := 0
        if b&(1<<32-1) == 0 {
                n += 32
                b >>= 32
        }
        if b&(1<<16-1) == 0 {
                n += 16
                b >>= 16
        }
        if b&(1<<8-1) == 0 {
                n += 8
                b >>= 8
        }
        if b&(1<<4-1) == 0 {
                n += 4
                b >>= 4
        }
        if b&(1<<2-1) == 0 {
                n += 2
                b >>= 2
        }
        if b&1 == 0 {
                n++
        }
        return n
}

// String returns a space-separated list of the variables represented by bits.
func (bits Bits) String() string {
        // Note: This method takes a value receiver, both for convenience
        // and to make it safe to modify the bits as we process them.
        // Even so, most prints above use &bits, because then the value
        // being stored in the interface{} is a pointer and does not require
        // an allocation and copy to create the interface{}.
        var buf bytes.Buffer
        sep := ""
        for bany(&bits) {
                i := bnum(&bits)
                buf.WriteString(sep)
                sep = " "
                v := &vars[i]
                if v.node == nil || v.node.Sym == nil {
                        fmt.Fprintf(&buf, "$%d", i)
                } else {
                        fmt.Fprintf(&buf, "%s(%d)", v.node.Sym.Name, i)
                        if v.offset != 0 {
                                fmt.Fprintf(&buf, "%+d", v.offset)
                        }
                }
                biclr(&bits, uint(i))
        }
        return buf.String()
}