// Copyright 2013 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.
// Garbage collector liveness bitmap generation.
// The command line flag -live causes this code to print debug information.
// The levels are:
//
// -live (aka -live=1): print liveness lists as code warnings at safe points
// -live=2: print an assembly listing with liveness annotations
// -live=3: print information during each computation phase (much chattier)
//
// Each level includes the earlier output as well.
package gc
import (
"cmd/internal/obj"
"fmt"
"sort"
)
const (
UNVISITED = 0
VISITED = 1
)
// An ordinary basic block.
//
// Instructions are threaded together in a doubly-linked list. To iterate in
// program order follow the link pointer from the first node and stop after the
// last node has been visited
//
// for(p = bb->first;; p = p->link) {
// ...
// if(p == bb->last)
// break;
// }
//
// To iterate in reverse program order by following the opt pointer from the
// last node
//
// for(p = bb->last; p != nil; p = p->opt) {
// ...
// }
type BasicBlock struct {
pred []*BasicBlock // predecessors; if none, probably start of CFG
succ []*BasicBlock // successors; if none, probably ends in return statement
first *obj.Prog // first instruction in block
last *obj.Prog // last instruction in block
rpo int // reverse post-order number (also index in cfg)
mark int // mark bit for traversals
lastbitmapindex int // for livenessepilogue
// Summary sets of block effects.
// Computed during livenessprologue using only the content of
// individual blocks:
//
// uevar: upward exposed variables (used before set in block)
// varkill: killed variables (set in block)
// avarinit: addrtaken variables set or used (proof of initialization)
uevar Bvec
varkill Bvec
avarinit Bvec
// Computed during livenesssolve using control flow information:
//
// livein: variables live at block entry
// liveout: variables live at block exit
// avarinitany: addrtaken variables possibly initialized at block exit
// (initialized in block or at exit from any predecessor block)
// avarinitall: addrtaken variables certainly initialized at block exit
// (initialized in block or at exit from all predecessor blocks)
livein Bvec
liveout Bvec
avarinitany Bvec
avarinitall Bvec
}
// A collection of global state used by liveness analysis.
type Liveness struct {
fn *Node
ptxt *obj.Prog
vars []*Node
cfg []*BasicBlock
// An array with a bit vector for each safe point tracking live pointers
// in the arguments and locals area, indexed by bb.rpo.
argslivepointers []Bvec
livepointers []Bvec
}
func xmalloc(size uint32) interface{} {
result := (interface{})(make([]byte, size))
if result == nil {
Fatal("malloc failed")
}
return result
}
// Constructs a new basic block containing a single instruction.
func newblock(prog *obj.Prog) *BasicBlock {
if prog == nil {
Fatal("newblock: prog cannot be nil")
}
result := new(BasicBlock)
result.rpo = -1
result.mark = UNVISITED
result.first = prog
result.last = prog
result.pred = make([]*BasicBlock, 0, 2)
result.succ = make([]*BasicBlock, 0, 2)
return result
}
// Frees a basic block and all of its leaf data structures.
func freeblock(bb *BasicBlock) {
if bb == nil {
Fatal("freeblock: cannot free nil")
}
}
// Adds an edge between two basic blocks by making from a predecessor of to and
// to a successor of from.
func addedge(from *BasicBlock, to *BasicBlock) {
if from == nil {
Fatal("addedge: from is nil")
}
if to == nil {
Fatal("addedge: to is nil")
}
from.succ = append(from.succ, to)
to.pred = append(to.pred, from)
}
// Inserts prev before curr in the instruction
// stream. Any control flow, such as branches or fall throughs, that target the
// existing instruction are adjusted to target the new instruction.
func splicebefore(lv *Liveness, bb *BasicBlock, prev *obj.Prog, curr *obj.Prog) {
// There may be other instructions pointing at curr,
// and we want them to now point at prev. Instead of
// trying to find all such instructions, swap the contents
// so that the problem becomes inserting next after curr.
// The "opt" field is the backward link in the linked list.
// Overwrite curr's data with prev, but keep the list links.
tmp := *curr
*curr = *prev
curr.Opt = tmp.Opt
curr.Link = tmp.Link
// Overwrite prev (now next) with curr's old data.
next := prev
*next = tmp
next.Opt = nil
next.Link = nil
// Now insert next after curr.
next.Link = curr.Link
next.Opt = curr
curr.Link = next
if next.Link != nil && next.Link.Opt == curr {
next.Link.Opt = next
}
if bb.last == curr {
bb.last = next
}
}
// A pretty printer for basic blocks.
func printblock(bb *BasicBlock) {
fmt.Printf("basic block %d\n", bb.rpo)
fmt.Printf("\tpred:")
for _, pred := range bb.pred {
fmt.Printf(" %d", pred.rpo)
}
fmt.Printf("\n")
fmt.Printf("\tsucc:")
for _, succ := range bb.succ {
fmt.Printf(" %d", succ.rpo)
}
fmt.Printf("\n")
fmt.Printf("\tprog:\n")
for prog := bb.first; ; prog = prog.Link {
fmt.Printf("\t\t%v\n", prog)
if prog == bb.last {
break
}
}
}
// Iterates over a basic block applying a callback to each instruction. There
// are two criteria for termination. If the end of basic block is reached a
// value of zero is returned. If the callback returns a non-zero value, the
// iteration is stopped and the value of the callback is returned.
func blockany(bb *BasicBlock, f func(*obj.Prog) bool) bool {
for p := bb.last; p != nil; p = p.Opt.(*obj.Prog) {
if f(p) {
return true
}
}
return false
}
// Collects and returns and array of Node*s for functions arguments and local
// variables.
func getvariables(fn *Node) []*Node {
result := make([]*Node, 0, 0)
for ll := fn.Func.Dcl; ll != nil; ll = ll.Next {
if ll.N.Op == ONAME {
// In order for GODEBUG=gcdead=1 to work, each bitmap needs
// to contain information about all variables covered by the bitmap.
// For local variables, the bitmap only covers the stkptrsize
// bytes in the frame where variables containing pointers live.
// For arguments and results, the bitmap covers all variables,
// so we must include all the variables, even the ones without
// pointers.
//
// The Node.opt field is available for use by optimization passes.
// We use it to hold the index of the node in the variables array, plus 1
// (so that 0 means the Node is not in the variables array).
// Each pass should clear opt when done, but you never know,
// so clear them all ourselves too.
// The Node.curfn field is supposed to be set to the current function
// already, but for some compiler-introduced names it seems not to be,
// so fix that here.
// Later, when we want to find the index of a node in the variables list,
// we will check that n->curfn == curfn and n->opt > 0. Then n->opt - 1
// is the index in the variables list.
ll.N.SetOpt(nil)
// The compiler doesn't emit initializations for zero-width parameters or results.
if ll.N.Type.Width == 0 {
continue
}
ll.N.Name.Curfn = Curfn
switch ll.N.Class {
case PAUTO:
if haspointers(ll.N.Type) {
ll.N.SetOpt(int32(len(result)))
result = append(result, ll.N)
}
case PPARAM, PPARAMOUT:
ll.N.SetOpt(int32(len(result)))
result = append(result, ll.N)
}
}
}
return result
}
// A pretty printer for control flow graphs. Takes an array of BasicBlock*s.
func printcfg(cfg []*BasicBlock) {
for _, bb := range cfg {
printblock(bb)
}
}
// Assigns a reverse post order number to each connected basic block using the
// standard algorithm. Unconnected blocks will not be affected.
func reversepostorder(root *BasicBlock, rpo *int32) {
root.mark = VISITED
for _, bb := range root.succ {
if bb.mark == UNVISITED {
reversepostorder(bb, rpo)
}
}
*rpo -= 1
root.rpo = int(*rpo)
}
// Comparison predicate used for sorting basic blocks by their rpo in ascending
// order.
type blockrpocmp []*BasicBlock
func (x blockrpocmp) Len() int { return len(x) }
func (x blockrpocmp) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
func (x blockrpocmp) Less(i, j int) bool { return x[i].rpo < x[j].rpo }
// A pattern matcher for call instructions. Returns true when the instruction
// is a call to a specific package qualified function name.
func iscall(prog *obj.Prog, name *obj.LSym) bool {
if prog == nil {
Fatal("iscall: prog is nil")
}
if name == nil {
Fatal("iscall: function name is nil")
}
if prog.As != obj.ACALL {
return false
}
return name == prog.To.Sym
}
// Returns true for instructions that call a runtime function implementing a
// select communication clause.
var selectNames [4]*obj.LSym
func isselectcommcasecall(prog *obj.Prog) bool {
if selectNames[0] == nil {
selectNames[0] = Linksym(Pkglookup("selectsend", Runtimepkg))
selectNames[1] = Linksym(Pkglookup("selectrecv", Runtimepkg))
selectNames[2] = Linksym(Pkglookup("selectrecv2", Runtimepkg))
selectNames[3] = Linksym(Pkglookup("selectdefault", Runtimepkg))
}
for _, name := range selectNames {
if iscall(prog, name) {
return true
}
}
return false
}
// Returns true for call instructions that target runtime·newselect.
var isnewselect_sym *obj.LSym
func isnewselect(prog *obj.Prog) bool {
if isnewselect_sym == nil {
isnewselect_sym = Linksym(Pkglookup("newselect", Runtimepkg))
}
return iscall(prog, isnewselect_sym)
}
// Returns true for call instructions that target runtime·selectgo.
var isselectgocall_sym *obj.LSym
func isselectgocall(prog *obj.Prog) bool {
if isselectgocall_sym == nil {
isselectgocall_sym = Linksym(Pkglookup("selectgo", Runtimepkg))
}
return iscall(prog, isselectgocall_sym)
}
var isdeferreturn_sym *obj.LSym
func isdeferreturn(prog *obj.Prog) bool {
if isdeferreturn_sym == nil {
isdeferreturn_sym = Linksym(Pkglookup("deferreturn", Runtimepkg))
}
return iscall(prog, isdeferreturn_sym)
}
// Walk backwards from a runtime·selectgo call up to its immediately dominating
// runtime·newselect call. Any successor nodes of communication clause nodes
// are implicit successors of the runtime·selectgo call node. The goal of this
// analysis is to add these missing edges to complete the control flow graph.
func addselectgosucc(selectgo *BasicBlock) {
var succ *BasicBlock
pred := selectgo
for {
if len(pred.pred) == 0 {
Fatal("selectgo does not have a newselect")
}
pred = pred.pred[0]
if blockany(pred, isselectcommcasecall) {
// A select comm case block should have exactly one
// successor.
if len(pred.succ) != 1 {
Fatal("select comm case has too many successors")
}
succ = pred.succ[0]
// Its successor should have exactly two successors.
// The drop through should flow to the selectgo block
// and the branch should lead to the select case
// statements block.
if len(succ.succ) != 2 {
Fatal("select comm case successor has too many successors")
}
// Add the block as a successor of the selectgo block.
addedge(selectgo, succ)
}
if blockany(pred, isnewselect) {
// Reached the matching newselect.
break
}
}
}
// The entry point for the missing selectgo control flow algorithm. Takes an
// array of BasicBlock*s containing selectgo calls.
func fixselectgo(selectgo []*BasicBlock) {
for _, bb := range selectgo {
addselectgosucc(bb)
}
}
// Constructs a control flow graph from a sequence of instructions. This
// procedure is complicated by various sources of implicit control flow that are
// not accounted for using the standard cfg construction algorithm. Returns an
// array of BasicBlock*s in control flow graph form (basic blocks ordered by
// their RPO number).
func newcfg(firstp *obj.Prog) []*BasicBlock {
// Reset the opt field of each prog to nil. In the first and second
// passes, instructions that are labels temporarily use the opt field to
// point to their basic block. In the third pass, the opt field reset
// to point to the predecessor of an instruction in its basic block.
for p := firstp; p != nil; p = p.Link {
p.Opt = nil
}
// Allocate an array to remember where we have seen selectgo calls.
// These blocks will be revisited to add successor control flow edges.
selectgo := make([]*BasicBlock, 0, 0)
// Loop through all instructions identifying branch targets
// and fall-throughs and allocate basic blocks.
cfg := make([]*BasicBlock, 0, 0)
bb := newblock(firstp)
cfg = append(cfg, bb)
for p := firstp; p != nil; p = p.Link {
Thearch.Proginfo(p)
if p.To.Type == obj.TYPE_BRANCH {
if p.To.Val == nil {
Fatal("prog branch to nil")
}
if p.To.Val.(*obj.Prog).Opt == nil {
p.To.Val.(*obj.Prog).Opt = newblock(p.To.Val.(*obj.Prog))
cfg = append(cfg, p.To.Val.(*obj.Prog).Opt.(*BasicBlock))
}
if p.As != obj.AJMP && p.Link != nil && p.Link.Opt == nil {
p.Link.Opt = newblock(p.Link)
cfg = append(cfg, p.Link.Opt.(*BasicBlock))
}
} else if isselectcommcasecall(p) || isselectgocall(p) {
// Accommodate implicit selectgo control flow.
if p.Link.Opt == nil {
p.Link.Opt = newblock(p.Link)
cfg = append(cfg, p.Link.Opt.(*BasicBlock))
}
}
}
// Loop through all basic blocks maximally growing the list of
// contained instructions until a label is reached. Add edges
// for branches and fall-through instructions.
for _, bb := range cfg {
for p := bb.last; p != nil; p = p.Link {
if p.Opt != nil && p != bb.last {
break
}
bb.last = p
// Stop before an unreachable RET, to avoid creating
// unreachable control flow nodes.
if p.Link != nil && p.Link.As == obj.ARET && p.Link.Mode == 1 {
break
}
// Collect basic blocks with selectgo calls.
if isselectgocall(p) {
selectgo = append(selectgo, bb)
}
}
if bb.last.To.Type == obj.TYPE_BRANCH {
addedge(bb, bb.last.To.Val.(*obj.Prog).Opt.(*BasicBlock))
}
if bb.last.Link != nil {
// Add a fall-through when the instruction is
// not an unconditional control transfer.
if bb.last.As != obj.AJMP && bb.last.As != obj.ARET && bb.last.As != obj.AUNDEF {
addedge(bb, bb.last.Link.Opt.(*BasicBlock))
}
}
}
// Add back links so the instructions in a basic block can be traversed
// backward. This is the final state of the instruction opt field.
for _, bb := range cfg {
p := bb.first
var prev *obj.Prog
for {
p.Opt = prev
if p == bb.last {
break
}
prev = p
p = p.Link
}
}
// Add missing successor edges to the selectgo blocks.
if len(selectgo) != 0 {
fixselectgo([]*BasicBlock(selectgo))
}
// Find a depth-first order and assign a depth-first number to
// all basic blocks.
for _, bb := range cfg {
bb.mark = UNVISITED
}
bb = cfg[0]
rpo := int32(len(cfg))
reversepostorder(bb, &rpo)
// Sort the basic blocks by their depth first number. The
// array is now a depth-first spanning tree with the first
// node being the root.
sort.Sort(blockrpocmp(cfg))
// Unreachable control flow nodes are indicated by a -1 in the rpo
// field. If we see these nodes something must have gone wrong in an
// upstream compilation phase.
bb = cfg[0]
if bb.rpo == -1 {
fmt.Printf("newcfg: unreachable basic block for %v\n", bb.last)
printcfg(cfg)
Fatal("newcfg: invalid control flow graph")
}
return cfg
}
// Frees a control flow graph (an array of BasicBlock*s) and all of its leaf
// data structures.
func freecfg(cfg []*BasicBlock) {
if len(cfg) > 0 {
bb0 := cfg[0]
for p := bb0.first; p != nil; p = p.Link {
p.Opt = nil
}
}
}
// Returns true if the node names a variable that is otherwise uninteresting to
// the liveness computation.
func isfunny(n *Node) bool {
return n.Sym != nil && (n.Sym.Name == ".fp" || n.Sym.Name == ".args")
}
// Computes the effects of an instruction on a set of
// variables. The vars argument is an array of Node*s.
//
// The output vectors give bits for variables:
// uevar - used by this instruction
// varkill - killed by this instruction
// for variables without address taken, means variable was set
// for variables with address taken, means variable was marked dead
// avarinit - initialized or referred to by this instruction,
// only for variables with address taken but not escaping to heap
//
// The avarinit output serves as a signal that the data has been
// initialized, because any use of a variable must come after its
// initialization.
func progeffects(prog *obj.Prog, vars []*Node, uevar Bvec, varkill Bvec, avarinit Bvec) {
bvresetall(uevar)
bvresetall(varkill)
bvresetall(avarinit)
if prog.As == obj.ARET {
// Return instructions implicitly read all the arguments. For
// the sake of correctness, out arguments must be read. For the
// sake of backtrace quality, we read in arguments as well.
//
// A return instruction with a p->to is a tail return, which brings
// the stack pointer back up (if it ever went down) and then jumps
// to a new function entirely. That form of instruction must read
// all the parameters for correctness, and similarly it must not
// read the out arguments - they won't be set until the new
// function runs.
for i, node := range vars {
switch node.Class &^ PHEAP {
case PPARAM:
bvset(uevar, int32(i))
// If the result had its address taken, it is being tracked
// by the avarinit code, which does not use uevar.
// If we added it to uevar too, we'd not see any kill
// and decide that the variable was live entry, which it is not.
// So only use uevar in the non-addrtaken case.
// The p->to.type == thearch.D_NONE limits the bvset to
// non-tail-call return instructions; see note above
// the for loop for details.
case PPARAMOUT:
if !node.Addrtaken && prog.To.Type == obj.TYPE_NONE {
bvset(uevar, int32(i))
}
}
}
return
}
if prog.As == obj.ATEXT {
// A text instruction marks the entry point to a function and
// the definition point of all in arguments.
for i, node := range vars {
switch node.Class &^ PHEAP {
case PPARAM:
if node.Addrtaken {
bvset(avarinit, int32(i))
}
bvset(varkill, int32(i))
}
}
return
}
if prog.Info.Flags&(LeftRead|LeftWrite|LeftAddr) != 0 {
from := &prog.From
if from.Node != nil && from.Sym != nil && ((from.Node).(*Node)).Name.Curfn == Curfn {
switch ((from.Node).(*Node)).Class &^ PHEAP {
case PAUTO, PPARAM, PPARAMOUT:
pos, ok := from.Node.(*Node).Opt().(int32) // index in vars
if !ok {
goto Next
}
if pos >= int32(len(vars)) || vars[pos] != from.Node {
Fatal("bad bookkeeping in liveness %v %d", Nconv(from.Node.(*Node), 0), pos)
}
if ((from.Node).(*Node)).Addrtaken {
bvset(avarinit, pos)
} else {
if prog.Info.Flags&(LeftRead|LeftAddr) != 0 {
bvset(uevar, pos)
}
if prog.Info.Flags&LeftWrite != 0 {
if from.Node != nil && !Isfat(((from.Node).(*Node)).Type) {
bvset(varkill, pos)
}
}
}
}
}
}
Next:
if prog.Info.Flags&(RightRead|RightWrite|RightAddr) != 0 {
to := &prog.To
if to.Node != nil && to.Sym != nil && ((to.Node).(*Node)).Name.Curfn == Curfn {
switch ((to.Node).(*Node)).Class &^ PHEAP {
case PAUTO, PPARAM, PPARAMOUT:
pos, ok := to.Node.(*Node).Opt().(int32) // index in vars
if !ok {
return
}
if pos >= int32(len(vars)) || vars[pos] != to.Node {
Fatal("bad bookkeeping in liveness %v %d", Nconv(to.Node.(*Node), 0), pos)
}
if ((to.Node).(*Node)).Addrtaken {
if prog.As != obj.AVARKILL {
bvset(avarinit, pos)
}
if prog.As == obj.AVARDEF || prog.As == obj.AVARKILL {
bvset(varkill, pos)
}
} else {
// RightRead is a read, obviously.
// RightAddr by itself is also implicitly a read.
//
// RightAddr|RightWrite means that the address is being taken
// but only so that the instruction can write to the value.
// It is not a read. It is equivalent to RightWrite except that
// having the RightAddr bit set keeps the registerizer from
// trying to substitute a register for the memory location.
if (prog.Info.Flags&RightRead != 0) || prog.Info.Flags&(RightAddr|RightWrite) == RightAddr {
bvset(uevar, pos)
}
if prog.Info.Flags&RightWrite != 0 {
if to.Node != nil && (!Isfat(((to.Node).(*Node)).Type) || prog.As == obj.AVARDEF) {
bvset(varkill, pos)
}
}
}
}
}
}
}
// Constructs a new liveness structure used to hold the global state of the
// liveness computation. The cfg argument is an array of BasicBlock*s and the
// vars argument is an array of Node*s.
func newliveness(fn *Node, ptxt *obj.Prog, cfg []*BasicBlock, vars []*Node) *Liveness {
result := new(Liveness)
result.fn = fn
result.ptxt = ptxt
result.cfg = cfg
result.vars = vars
nblocks := int32(len(cfg))
nvars := int32(len(vars))
bulk := bvbulkalloc(nvars, nblocks*7)
for _, bb := range cfg {
bb.uevar = bulk.next()
bb.varkill = bulk.next()
bb.livein = bulk.next()
bb.liveout = bulk.next()
bb.avarinit = bulk.next()
bb.avarinitany = bulk.next()
bb.avarinitall = bulk.next()
}
result.livepointers = make([]Bvec, 0, 0)
result.argslivepointers = make([]Bvec, 0, 0)
return result
}
// Frees the liveness structure and all of its leaf data structures.
func freeliveness(lv *Liveness) {
if lv == nil {
Fatal("freeliveness: cannot free nil")
}
}
func printeffects(p *obj.Prog, uevar Bvec, varkill Bvec, avarinit Bvec) {
fmt.Printf("effects of %v", p)
fmt.Printf("\nuevar: ")
bvprint(uevar)
fmt.Printf("\nvarkill: ")
bvprint(varkill)
fmt.Printf("\navarinit: ")
bvprint(avarinit)
fmt.Printf("\n")
}
// Pretty print a variable node. Uses Pascal like conventions for pointers and
// addresses to avoid confusing the C like conventions used in the node variable
// names.
func printnode(node *Node) {
p := ""
if haspointers(node.Type) {
p = "^"
}
a := ""
if node.Addrtaken {
a = "@"
}
fmt.Printf(" %v%s%s", node, p, a)
}
// Pretty print a list of variables. The vars argument is an array of Node*s.
func printvars(name string, bv Bvec, vars []*Node) {
fmt.Printf("%s:", name)
for i, node := range vars {
if bvget(bv, int32(i)) != 0 {
printnode(node)
}
}
fmt.Printf("\n")
}
// Prints a basic block annotated with the information computed by liveness
// analysis.
func livenessprintblock(lv *Liveness, bb *BasicBlock) {
fmt.Printf("basic block %d\n", bb.rpo)
fmt.Printf("\tpred:")
for _, pred := range bb.pred {
fmt.Printf(" %d", pred.rpo)
}
fmt.Printf("\n")
fmt.Printf("\tsucc:")
for _, succ := range bb.succ {
fmt.Printf(" %d", succ.rpo)
}
fmt.Printf("\n")
printvars("\tuevar", bb.uevar, []*Node(lv.vars))
printvars("\tvarkill", bb.varkill, []*Node(lv.vars))
printvars("\tlivein", bb.livein, []*Node(lv.vars))
printvars("\tliveout", bb.liveout, []*Node(lv.vars))
printvars("\tavarinit", bb.avarinit, []*Node(lv.vars))
printvars("\tavarinitany", bb.avarinitany, []*Node(lv.vars))
printvars("\tavarinitall", bb.avarinitall, []*Node(lv.vars))
fmt.Printf("\tprog:\n")
for prog := bb.first; ; prog = prog.Link {
fmt.Printf("\t\t%v", prog)
if prog.As == obj.APCDATA && prog.From.Offset == obj.PCDATA_StackMapIndex {
pos := int32(prog.To.Offset)
live := lv.livepointers[pos]
fmt.Printf(" ")
bvprint(live)
}
fmt.Printf("\n")
if prog == bb.last {
break
}
}
}
// Prints a control flow graph annotated with any information computed by
// liveness analysis.
func livenessprintcfg(lv *Liveness) {
for _, bb := range lv.cfg {
livenessprintblock(lv, bb)
}
}
func checkauto(fn *Node, p *obj.Prog, n *Node) {
for l := fn.Func.Dcl; l != nil; l = l.Next {
if l.N.Op == ONAME && l.N.Class == PAUTO && l.N == n {
return
}
}
if n == nil {
fmt.Printf("%v: checkauto %v: nil node in %v\n", p.Line(), Curfn, p)
return
}
fmt.Printf("checkauto %v: %v (%p; class=%d) not found in %v\n", Curfn, n, n, n.Class, p)
for l := fn.Func.Dcl; l != nil; l = l.Next {
fmt.Printf("\t%v (%p; class=%d)\n", l.N, l.N, l.N.Class)
}
Yyerror("checkauto: invariant lost")
}
func checkparam(fn *Node, p *obj.Prog, n *Node) {
if isfunny(n) {
return
}
var a *Node
var class uint8
for l := fn.Func.Dcl; l != nil; l = l.Next {
a = l.N
class = a.Class &^ PHEAP
if a.Op == ONAME && (class == PPARAM || class == PPARAMOUT) && a == n {
return
}
}
fmt.Printf("checkparam %v: %v (%p; class=%d) not found in %v\n", Curfn, n, n, n.Class, p)
for l := fn.Func.Dcl; l != nil; l = l.Next {
fmt.Printf("\t%v (%p; class=%d)\n", l.N, l.N, l.N.Class)
}
Yyerror("checkparam: invariant lost")
}
func checkprog(fn *Node, p *obj.Prog) {
if p.From.Name == obj.NAME_AUTO {
checkauto(fn, p, p.From.Node.(*Node))
}
if p.From.Name == obj.NAME_PARAM {
checkparam(fn, p, p.From.Node.(*Node))
}
if p.To.Name == obj.NAME_AUTO {
checkauto(fn, p, p.To.Node.(*Node))
}
if p.To.Name == obj.NAME_PARAM {
checkparam(fn, p, p.To.Node.(*Node))
}
}
// Check instruction invariants. We assume that the nodes corresponding to the
// sources and destinations of memory operations will be declared in the
// function. This is not strictly true, as is the case for the so-called funny
// nodes and there are special cases to skip over that stuff. The analysis will
// fail if this invariant blindly changes.
func checkptxt(fn *Node, firstp *obj.Prog) {
if debuglive == 0 {
return
}
for p := firstp; p != nil; p = p.Link {
if false {
fmt.Printf("analyzing '%v'\n", p)
}
if p.As != obj.ADATA && p.As != obj.AGLOBL && p.As != obj.ATYPE {
checkprog(fn, p)
}
}
}
// NOTE: The bitmap for a specific type t should be cached in t after the first run
// and then simply copied into bv at the correct offset on future calls with
// the same type t. On https://rsc.googlecode.com/hg/testdata/slow.go, onebitwalktype1
// accounts for 40% of the 6g execution time.
func onebitwalktype1(t *Type, xoffset *int64, bv Bvec) {
if t.Align > 0 && *xoffset&int64(t.Align-1) != 0 {
Fatal("onebitwalktype1: invalid initial alignment, %v", t)
}
switch t.Etype {
case TINT8,
TUINT8,
TINT16,
TUINT16,
TINT32,
TUINT32,
TINT64,
TUINT64,
TINT,
TUINT,
TUINTPTR,
TBOOL,
TFLOAT32,
TFLOAT64,
TCOMPLEX64,
TCOMPLEX128:
*xoffset += t.Width
case TPTR32,
TPTR64,
TUNSAFEPTR,
TFUNC,
TCHAN,
TMAP:
if *xoffset&int64(Widthptr-1) != 0 {
Fatal("onebitwalktype1: invalid alignment, %v", t)
}
bvset(bv, int32(*xoffset/int64(Widthptr))) // pointer
*xoffset += t.Width
case TSTRING:
// struct { byte *str; intgo len; }
if *xoffset&int64(Widthptr-1) != 0 {
Fatal("onebitwalktype1: invalid alignment, %v", t)
}
bvset(bv, int32(*xoffset/int64(Widthptr))) //pointer in first slot
*xoffset += t.Width
case TINTER:
// struct { Itab *tab; void *data; }
// or, when isnilinter(t)==true:
// struct { Type *type; void *data; }
if *xoffset&int64(Widthptr-1) != 0 {
Fatal("onebitwalktype1: invalid alignment, %v", t)
}
bvset(bv, int32(*xoffset/int64(Widthptr))) // pointer in first slot
bvset(bv, int32(*xoffset/int64(Widthptr)+1)) // pointer in second slot
*xoffset += t.Width
case TARRAY:
// The value of t->bound is -1 for slices types and >=0 for
// for fixed array types. All other values are invalid.
if t.Bound < -1 {
Fatal("onebitwalktype1: invalid bound, %v", t)
}
if Isslice(t) {
// struct { byte *array; uintgo len; uintgo cap; }
if *xoffset&int64(Widthptr-1) != 0 {
Fatal("onebitwalktype1: invalid TARRAY alignment, %v", t)
}
bvset(bv, int32(*xoffset/int64(Widthptr))) // pointer in first slot (BitsPointer)
*xoffset += t.Width
} else {
for i := int64(0); i < t.Bound; i++ {
onebitwalktype1(t.Type, xoffset, bv)
}
}
case TSTRUCT:
o := int64(0)
var fieldoffset int64
for t1 := t.Type; t1 != nil; t1 = t1.Down {
fieldoffset = t1.Width
*xoffset += fieldoffset - o
onebitwalktype1(t1.Type, xoffset, bv)
o = fieldoffset + t1.Type.Width
}
*xoffset += t.Width - o
default:
Fatal("onebitwalktype1: unexpected type, %v", t)
}
}
// Returns the number of words of local variables.
func localswords() int32 {
return int32(stkptrsize / int64(Widthptr))
}
// Returns the number of words of in and out arguments.
func argswords() int32 {
return int32(Curfn.Type.Argwid / int64(Widthptr))
}
// Generates live pointer value maps for arguments and local variables. The
// this argument and the in arguments are always assumed live. The vars
// argument is an array of Node*s.
func onebitlivepointermap(lv *Liveness, liveout Bvec, vars []*Node, args Bvec, locals Bvec) {
var node *Node
var xoffset int64
for i := int32(0); ; i++ {
i = int32(bvnext(liveout, i))
if i < 0 {
break
}
node = vars[i]
switch node.Class {
case PAUTO:
xoffset = node.Xoffset + stkptrsize
onebitwalktype1(node.Type, &xoffset, locals)
case PPARAM, PPARAMOUT:
xoffset = node.Xoffset
onebitwalktype1(node.Type, &xoffset, args)
}
}
// The node list only contains declared names.
// If the receiver or arguments are unnamed, they will be omitted
// from the list above. Preserve those values - even though they are unused -
// in order to keep their addresses live for use in stack traces.
thisargtype := getthisx(lv.fn.Type)
if thisargtype != nil {
xoffset = 0
onebitwalktype1(thisargtype, &xoffset, args)
}
inargtype := getinargx(lv.fn.Type)
if inargtype != nil {
xoffset = 0
onebitwalktype1(inargtype, &xoffset, args)
}
}
// Construct a disembodied instruction.
func unlinkedprog(as int) *obj.Prog {
p := Ctxt.NewProg()
Clearp(p)
p.As = int16(as)
return p
}
// Construct a new PCDATA instruction associated with and for the purposes of
// covering an existing instruction.
func newpcdataprog(prog *obj.Prog, index int32) *obj.Prog {
var from Node
var to Node
Nodconst(&from, Types[TINT32], obj.PCDATA_StackMapIndex)
Nodconst(&to, Types[TINT32], int64(index))
pcdata := unlinkedprog(obj.APCDATA)
pcdata.Lineno = prog.Lineno
Naddr(&pcdata.From, &from)
Naddr(&pcdata.To, &to)
return pcdata
}
// Returns true for instructions that are safe points that must be annotated
// with liveness information.
func issafepoint(prog *obj.Prog) bool {
return prog.As == obj.ATEXT || prog.As == obj.ACALL
}
// Initializes the sets for solving the live variables. Visits all the
// instructions in each basic block to summarizes the information at each basic
// block
func livenessprologue(lv *Liveness) {
nvars := int32(len(lv.vars))
uevar := bvalloc(nvars)
varkill := bvalloc(nvars)
avarinit := bvalloc(nvars)
for _, bb := range lv.cfg {
// Walk the block instructions backward and update the block
// effects with the each prog effects.
for p := bb.last; p != nil; p = p.Opt.(*obj.Prog) {
progeffects(p, []*Node(lv.vars), uevar, varkill, avarinit)
if debuglive >= 3 {
printeffects(p, uevar, varkill, avarinit)
}
bvor(bb.varkill, bb.varkill, varkill)
bvandnot(bb.uevar, bb.uevar, varkill)
bvor(bb.uevar, bb.uevar, uevar)
}
// Walk the block instructions forward to update avarinit bits.
// avarinit describes the effect at the end of the block, not the beginning.
bvresetall(varkill)
for p := bb.first; ; p = p.Link {
progeffects(p, []*Node(lv.vars), uevar, varkill, avarinit)
if debuglive >= 3 {
printeffects(p, uevar, varkill, avarinit)
}
bvandnot(bb.avarinit, bb.avarinit, varkill)
bvor(bb.avarinit, bb.avarinit, avarinit)
if p == bb.last {
break
}
}
}
}
// Solve the liveness dataflow equations.
func livenesssolve(lv *Liveness) {
// These temporary bitvectors exist to avoid successive allocations and
// frees within the loop.
newlivein := bvalloc(int32(len(lv.vars)))
newliveout := bvalloc(int32(len(lv.vars)))
any := bvalloc(int32(len(lv.vars)))
all := bvalloc(int32(len(lv.vars)))
// Push avarinitall, avarinitany forward.
// avarinitall says the addressed var is initialized along all paths reaching the block exit.
// avarinitany says the addressed var is initialized along some path reaching the block exit.
for i, bb := range lv.cfg {
if i == 0 {
bvcopy(bb.avarinitall, bb.avarinit)
} else {
bvresetall(bb.avarinitall)
bvnot(bb.avarinitall)
}
bvcopy(bb.avarinitany, bb.avarinit)
}
change := int32(1)
for change != 0 {
change = 0
for _, bb := range lv.cfg {
bvresetall(any)
bvresetall(all)
for j, pred := range bb.pred {
if j == 0 {
bvcopy(any, pred.avarinitany)
bvcopy(all, pred.avarinitall)
} else {
bvor(any, any, pred.avarinitany)
bvand(all, all, pred.avarinitall)
}
}
bvandnot(any, any, bb.varkill)
bvandnot(all, all, bb.varkill)
bvor(any, any, bb.avarinit)
bvor(all, all, bb.avarinit)
if bvcmp(any, bb.avarinitany) != 0 {
change = 1
bvcopy(bb.avarinitany, any)
}
if bvcmp(all, bb.avarinitall) != 0 {
change = 1
bvcopy(bb.avarinitall, all)
}
}
}
// Iterate through the blocks in reverse round-robin fashion. A work
// queue might be slightly faster. As is, the number of iterations is
// so low that it hardly seems to be worth the complexity.
change = 1
for change != 0 {
change = 0
// Walk blocks in the general direction of propagation. This
// improves convergence.
for i := len(lv.cfg) - 1; i >= 0; i-- {
bb := lv.cfg[i]
// A variable is live on output from this block
// if it is live on input to some successor.
//
// out[b] = \bigcup_{s \in succ[b]} in[s]
bvresetall(newliveout)
for _, succ := range bb.succ {
bvor(newliveout, newliveout, succ.livein)
}
if bvcmp(bb.liveout, newliveout) != 0 {
change = 1
bvcopy(bb.liveout, newliveout)
}
// A variable is live on input to this block
// if it is live on output from this block and
// not set by the code in this block.
//
// in[b] = uevar[b] \cup (out[b] \setminus varkill[b])
bvandnot(newlivein, bb.liveout, bb.varkill)
bvor(bb.livein, newlivein, bb.uevar)
}
}
}
// This function is slow but it is only used for generating debug prints.
// Check whether n is marked live in args/locals.
func islive(n *Node, args Bvec, locals Bvec) bool {
switch n.Class {
case PPARAM, PPARAMOUT:
for i := 0; int64(i) < n.Type.Width/int64(Widthptr); i++ {
if bvget(args, int32(n.Xoffset/int64(Widthptr)+int64(i))) != 0 {
return true
}
}
case PAUTO:
for i := 0; int64(i) < n.Type.Width/int64(Widthptr); i++ {
if bvget(locals, int32((n.Xoffset+stkptrsize)/int64(Widthptr)+int64(i))) != 0 {
return true
}
}
}
return false
}
// Visits all instructions in a basic block and computes a bit vector of live
// variables at each safe point locations.
func livenessepilogue(lv *Liveness) {
var pred *BasicBlock
var args Bvec
var locals Bvec
var n *Node
var p *obj.Prog
var j int32
var pos int32
var xoffset int64
nvars := int32(len(lv.vars))
livein := bvalloc(nvars)
liveout := bvalloc(nvars)
uevar := bvalloc(nvars)
varkill := bvalloc(nvars)
avarinit := bvalloc(nvars)
any := bvalloc(nvars)
all := bvalloc(nvars)
ambig := bvalloc(localswords())
nmsg := int32(0)
startmsg := int32(0)
for _, bb := range lv.cfg {
// Compute avarinitany and avarinitall for entry to block.
// This duplicates information known during livenesssolve
// but avoids storing two more vectors for each block.
bvresetall(any)
bvresetall(all)
for j = 0; j < int32(len(bb.pred)); j++ {
pred = bb.pred[j]
if j == 0 {
bvcopy(any, pred.avarinitany)
bvcopy(all, pred.avarinitall)
} else {
bvor(any, any, pred.avarinitany)
bvand(all, all, pred.avarinitall)
}
}
// Walk forward through the basic block instructions and
// allocate liveness maps for those instructions that need them.
// Seed the maps with information about the addrtaken variables.
for p = bb.first; ; p = p.Link {
progeffects(p, []*Node(lv.vars), uevar, varkill, avarinit)
bvandnot(any, any, varkill)
bvandnot(all, all, varkill)
bvor(any, any, avarinit)
bvor(all, all, avarinit)
if issafepoint(p) {
// Annotate ambiguously live variables so that they can
// be zeroed at function entry.
// livein and liveout are dead here and used as temporaries.
bvresetall(livein)
bvandnot(liveout, any, all)
if !bvisempty(liveout) {
for pos = 0; pos < liveout.n; pos++ {
if bvget(liveout, pos) == 0 {
continue
}
bvset(all, pos) // silence future warnings in this block
n = lv.vars[pos]
if !n.Name.Needzero {
n.Name.Needzero = true
if debuglive >= 1 {
Warnl(int(p.Lineno), "%v: %v is ambiguously live", Curfn.Func.Nname, Nconv(n, obj.FmtLong))
}
// Record in 'ambiguous' bitmap.
xoffset = n.Xoffset + stkptrsize
onebitwalktype1(n.Type, &xoffset, ambig)
}
}
}
// Allocate a bit vector for each class and facet of
// value we are tracking.
// Live stuff first.
args = bvalloc(argswords())
lv.argslivepointers = append(lv.argslivepointers, args)
locals = bvalloc(localswords())
lv.livepointers = append(lv.livepointers, locals)
if debuglive >= 3 {
fmt.Printf("%v\n", p)
printvars("avarinitany", any, lv.vars)
}
// Record any values with an "address taken" reaching
// this code position as live. Must do now instead of below
// because the any/all calculation requires walking forward
// over the block (as this loop does), while the liveout
// requires walking backward (as the next loop does).
onebitlivepointermap(lv, any, lv.vars, args, locals)
}
if p == bb.last {
break
}
}
bb.lastbitmapindex = len(lv.livepointers) - 1
}
var fmt_ string
var next *obj.Prog
var numlive int32
var msg []string
for _, bb := range lv.cfg {
if debuglive >= 1 && Curfn.Func.Nname.Sym.Name != "init" && Curfn.Func.Nname.Sym.Name[0] != '.' {
nmsg = int32(len(lv.livepointers))
startmsg = nmsg
msg = make([]string, nmsg)
for j = 0; j < nmsg; j++ {
msg[j] = ""
}
}
// walk backward, emit pcdata and populate the maps
pos = int32(bb.lastbitmapindex)
if pos < 0 {
// the first block we encounter should have the ATEXT so
// at no point should pos ever be less than zero.
Fatal("livenessepilogue")
}
bvcopy(livein, bb.liveout)
for p = bb.last; p != nil; p = next {
next = p.Opt.(*obj.Prog) // splicebefore modifies p->opt
// Propagate liveness information
progeffects(p, lv.vars, uevar, varkill, avarinit)
bvcopy(liveout, livein)
bvandnot(livein, liveout, varkill)
bvor(livein, livein, uevar)
if debuglive >= 3 && issafepoint(p) {
fmt.Printf("%v\n", p)
printvars("uevar", uevar, lv.vars)
printvars("varkill", varkill, lv.vars)
printvars("livein", livein, lv.vars)
printvars("liveout", liveout, lv.vars)
}
if issafepoint(p) {
// Found an interesting instruction, record the
// corresponding liveness information.
// Useful sanity check: on entry to the function,
// the only things that can possibly be live are the
// input parameters.
if p.As == obj.ATEXT {
for j = 0; j < liveout.n; j++ {
if bvget(liveout, j) == 0 {
continue
}
n = lv.vars[j]
if n.Class != PPARAM {
yyerrorl(int(p.Lineno), "internal error: %v %v recorded as live on entry", Curfn.Func.Nname, Nconv(n, obj.FmtLong))
}
}
}
// Record live pointers.
args = lv.argslivepointers[pos]
locals = lv.livepointers[pos]
onebitlivepointermap(lv, liveout, lv.vars, args, locals)
// Ambiguously live variables are zeroed immediately after
// function entry. Mark them live for all the non-entry bitmaps
// so that GODEBUG=gcdead=1 mode does not poison them.
if p.As == obj.ACALL {
bvor(locals, locals, ambig)
}
// Show live pointer bitmaps.
// We're interpreting the args and locals bitmap instead of liveout so that we
// include the bits added by the avarinit logic in the
// previous loop.
if msg != nil {
fmt_ = ""
fmt_ += fmt.Sprintf("%v: live at ", p.Line())
if p.As == obj.ACALL && p.To.Node != nil {
fmt_ += fmt.Sprintf("call to %s:", ((p.To.Node).(*Node)).Sym.Name)
} else if p.As == obj.ACALL {
fmt_ += "indirect call:"
} else {
fmt_ += fmt.Sprintf("entry to %s:", ((p.From.Node).(*Node)).Sym.Name)
}
numlive = 0
for j = 0; j < int32(len(lv.vars)); j++ {
n = lv.vars[j]
if islive(n, args, locals) {
fmt_ += fmt.Sprintf(" %v", n)
numlive++
}
}
fmt_ += "\n"
if numlive == 0 { // squelch message
} else {
startmsg--
msg[startmsg] = fmt_
}
}
// Only CALL instructions need a PCDATA annotation.
// The TEXT instruction annotation is implicit.
if p.As == obj.ACALL {
if isdeferreturn(p) {
// runtime.deferreturn modifies its return address to return
// back to the CALL, not to the subsequent instruction.
// Because the return comes back one instruction early,
// the PCDATA must begin one instruction early too.
// The instruction before a call to deferreturn is always a
// no-op, to keep PC-specific data unambiguous.
splicebefore(lv, bb, newpcdataprog(p.Opt.(*obj.Prog), pos), p.Opt.(*obj.Prog))
} else {
splicebefore(lv, bb, newpcdataprog(p, pos), p)
}
}
pos--
}
}
if msg != nil {
for j = startmsg; j < nmsg; j++ {
if msg[j] != "" {
fmt.Printf("%s", msg[j])
}
}
msg = nil
nmsg = 0
startmsg = 0
}
}
Flusherrors()
}
// FNV-1 hash function constants.
const (
H0 = 2166136261
Hp = 16777619
)
func hashbitmap(h uint32, bv Bvec) uint32 {
var w uint32
n := int((bv.n + 31) / 32)
for i := 0; i < n; i++ {
w = bv.b[i]
h = (h * Hp) ^ (w & 0xff)
h = (h * Hp) ^ ((w >> 8) & 0xff)
h = (h * Hp) ^ ((w >> 16) & 0xff)
h = (h * Hp) ^ ((w >> 24) & 0xff)
}
return h
}
// Compact liveness information by coalescing identical per-call-site bitmaps.
// The merging only happens for a single function, not across the entire binary.
//
// There are actually two lists of bitmaps, one list for the local variables and one
// list for the function arguments. Both lists are indexed by the same PCDATA
// index, so the corresponding pairs must be considered together when
// merging duplicates. The argument bitmaps change much less often during
// function execution than the local variable bitmaps, so it is possible that
// we could introduce a separate PCDATA index for arguments vs locals and
// then compact the set of argument bitmaps separately from the set of
// local variable bitmaps. As of 2014-04-02, doing this to the godoc binary
// is actually a net loss: we save about 50k of argument bitmaps but the new
// PCDATA tables cost about 100k. So for now we keep using a single index for
// both bitmap lists.
func livenesscompact(lv *Liveness) {
// Linear probing hash table of bitmaps seen so far.
// The hash table has 4n entries to keep the linear
// scan short. An entry of -1 indicates an empty slot.
n := len(lv.livepointers)
tablesize := 4 * n
table := make([]int, tablesize)
for i := range table {
table[i] = -1
}
// remap[i] = the new index of the old bit vector #i.
remap := make([]int, n)
for i := range remap {
remap[i] = -1
}
uniq := 0 // unique tables found so far
// Consider bit vectors in turn.
// If new, assign next number using uniq,
// record in remap, record in lv->livepointers and lv->argslivepointers
// under the new index, and add entry to hash table.
// If already seen, record earlier index in remap and free bitmaps.
var jarg Bvec
var j int
var h uint32
var arg Bvec
var jlocal Bvec
var local Bvec
for i := 0; i < n; i++ {
local = lv.livepointers[i]
arg = lv.argslivepointers[i]
h = hashbitmap(hashbitmap(H0, local), arg) % uint32(tablesize)
for {
j = table[h]
if j < 0 {
break
}
jlocal = lv.livepointers[j]
jarg = lv.argslivepointers[j]
if bvcmp(local, jlocal) == 0 && bvcmp(arg, jarg) == 0 {
remap[i] = j
goto Next
}
h++
if h == uint32(tablesize) {
h = 0
}
}
table[h] = uniq
remap[i] = uniq
lv.livepointers[uniq] = local
lv.argslivepointers[uniq] = arg
uniq++
Next:
}
// We've already reordered lv->livepointers[0:uniq]
// and lv->argslivepointers[0:uniq] and freed the bitmaps
// we don't need anymore. Clear the pointers later in the
// array so that we can tell where the coalesced bitmaps stop
// and so that we don't double-free when cleaning up.
for j := uniq; j < n; j++ {
lv.livepointers[j] = Bvec{}
lv.argslivepointers[j] = Bvec{}
}
// Rewrite PCDATA instructions to use new numbering.
var i int
for p := lv.ptxt; p != nil; p = p.Link {
if p.As == obj.APCDATA && p.From.Offset == obj.PCDATA_StackMapIndex {
i = int(p.To.Offset)
if i >= 0 {
p.To.Offset = int64(remap[i])
}
}
}
}
func printbitset(printed int, name string, vars []*Node, bits Bvec) int {
started := 0
for i, n := range vars {
if bvget(bits, int32(i)) == 0 {
continue
}
if started == 0 {
if printed == 0 {
fmt.Printf("\t")
} else {
fmt.Printf(" ")
}
started = 1
printed = 1
fmt.Printf("%s=", name)
} else {
fmt.Printf(",")
}
fmt.Printf("%s", n.Sym.Name)
}
return printed
}
// Prints the computed liveness information and inputs, for debugging.
// This format synthesizes the information used during the multiple passes
// into a single presentation.
func livenessprintdebug(lv *Liveness) {
var j int
var printed int
var p *obj.Prog
var args Bvec
var locals Bvec
var n *Node
fmt.Printf("liveness: %s\n", Curfn.Func.Nname.Sym.Name)
uevar := bvalloc(int32(len(lv.vars)))
varkill := bvalloc(int32(len(lv.vars)))
avarinit := bvalloc(int32(len(lv.vars)))
pcdata := 0
for i, bb := range lv.cfg {
if i > 0 {
fmt.Printf("\n")
}
// bb#0 pred=1,2 succ=3,4
fmt.Printf("bb#%d pred=", i)
for j = 0; j < len(bb.pred); j++ {
if j > 0 {
fmt.Printf(",")
}
fmt.Printf("%d", (bb.pred[j]).rpo)
}
fmt.Printf(" succ=")
for j = 0; j < len(bb.succ); j++ {
if j > 0 {
fmt.Printf(",")
}
fmt.Printf("%d", (bb.succ[j]).rpo)
}
fmt.Printf("\n")
// initial settings
printed = 0
printed = printbitset(printed, "uevar", lv.vars, bb.uevar)
printed = printbitset(printed, "livein", lv.vars, bb.livein)
if printed != 0 {
fmt.Printf("\n")
}
// program listing, with individual effects listed
for p = bb.first; ; p = p.Link {
fmt.Printf("%v\n", p)
if p.As == obj.APCDATA && p.From.Offset == obj.PCDATA_StackMapIndex {
pcdata = int(p.To.Offset)
}
progeffects(p, lv.vars, uevar, varkill, avarinit)
printed = 0
printed = printbitset(printed, "uevar", lv.vars, uevar)
printed = printbitset(printed, "varkill", lv.vars, varkill)
printed = printbitset(printed, "avarinit", lv.vars, avarinit)
if printed != 0 {
fmt.Printf("\n")
}
if issafepoint(p) {
args = lv.argslivepointers[pcdata]
locals = lv.livepointers[pcdata]
fmt.Printf("\tlive=")
printed = 0
for j = 0; j < len(lv.vars); j++ {
n = lv.vars[j]
if islive(n, args, locals) {
tmp9 := printed
printed++
if tmp9 != 0 {
fmt.Printf(",")
}
fmt.Printf("%v", n)
}
}
fmt.Printf("\n")
}
if p == bb.last {
break
}
}
// bb bitsets
fmt.Printf("end\n")
printed = printbitset(printed, "varkill", lv.vars, bb.varkill)
printed = printbitset(printed, "liveout", lv.vars, bb.liveout)
printed = printbitset(printed, "avarinit", lv.vars, bb.avarinit)
printed = printbitset(printed, "avarinitany", lv.vars, bb.avarinitany)
printed = printbitset(printed, "avarinitall", lv.vars, bb.avarinitall)
if printed != 0 {
fmt.Printf("\n")
}
}
fmt.Printf("\n")
}
// Dumps an array of bitmaps to a symbol as a sequence of uint32 values. The
// first word dumped is the total number of bitmaps. The second word is the
// length of the bitmaps. All bitmaps are assumed to be of equal length. The
// words that are followed are the raw bitmap words. The arr argument is an
// array of Node*s.
func onebitwritesymbol(arr []Bvec, sym *Sym) {
var i int
var j int
var word uint32
n := len(arr)
off := 0
off += 4 // number of bitmaps, to fill in later
bv := arr[0]
off = duint32(sym, off, uint32(bv.n)) // number of bits in each bitmap
for i = 0; i < n; i++ {
// bitmap words
bv = arr[i]
if bv.b == nil {
break
}
for j = 0; int32(j) < bv.n; j += 32 {
word = bv.b[j/32]
// Runtime reads the bitmaps as byte arrays. Oblige.
off = duint8(sym, off, uint8(word))
off = duint8(sym, off, uint8(word>>8))
off = duint8(sym, off, uint8(word>>16))
off = duint8(sym, off, uint8(word>>24))
}
}
duint32(sym, 0, uint32(i)) // number of bitmaps
ggloblsym(sym, int32(off), obj.RODATA)
}
func printprog(p *obj.Prog) {
for p != nil {
fmt.Printf("%v\n", p)
p = p.Link
}
}
// Entry pointer for liveness analysis. Constructs a complete CFG, solves for
// the liveness of pointer variables in the function, and emits a runtime data
// structure read by the garbage collector.
func liveness(fn *Node, firstp *obj.Prog, argssym *Sym, livesym *Sym) {
// Change name to dump debugging information only for a specific function.
debugdelta := 0
if Curfn.Func.Nname.Sym.Name == "!" {
debugdelta = 2
}
debuglive += debugdelta
if debuglive >= 3 {
fmt.Printf("liveness: %s\n", Curfn.Func.Nname.Sym.Name)
printprog(firstp)
}
checkptxt(fn, firstp)
// Construct the global liveness state.
cfg := newcfg(firstp)
if debuglive >= 3 {
printcfg([]*BasicBlock(cfg))
}
vars := getvariables(fn)
lv := newliveness(fn, firstp, cfg, vars)
// Run the dataflow framework.
livenessprologue(lv)
if debuglive >= 3 {
livenessprintcfg(lv)
}
livenesssolve(lv)
if debuglive >= 3 {
livenessprintcfg(lv)
}
livenessepilogue(lv)
if debuglive >= 3 {
livenessprintcfg(lv)
}
livenesscompact(lv)
if debuglive >= 2 {
livenessprintdebug(lv)
}
// Emit the live pointer map data structures
onebitwritesymbol(lv.livepointers, livesym)
onebitwritesymbol(lv.argslivepointers, argssym)
// Free everything.
for l := fn.Func.Dcl; l != nil; l = l.Next {
if l.N != nil {
l.N.SetOpt(nil)
}
}
freeliveness(lv)
freecfg([]*BasicBlock(cfg))
debuglive -= debugdelta
}