src/cmd/compile/internal/liveness/arg.go - toolchain/go - Git at Google

 // Copyright 2021 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 package liveness

 import (
 	"fmt"
 	"internal/abi"

 	"cmd/compile/internal/base"
 	"cmd/compile/internal/bitvec"
 	"cmd/compile/internal/ir"
 	"cmd/compile/internal/objw"
 	"cmd/compile/internal/ssa"
 	"cmd/internal/obj"
 )

 // Argument liveness tracking.
 //
 // For arguments passed in registers, this file tracks if their spill slots
 // are live for runtime traceback. An argument spill slot is live at a PC
 // if we know that an actual value has stored into it at or before this point.
 //
 // Stack args are always live and not tracked in this code. Stack args are
 // laid out before register spill slots, so we emit the smallest offset that
 // needs tracking. Slots before that offset are always live. That offset is
 // usually the offset of the first spill slot. But if the first spill slot is
 // always live (e.g. if it is address-taken), it will be the offset of a later
 // one.
 //
 // The liveness information is emitted as a FUNCDATA and a PCDATA.
 //
 // FUNCDATA format:
 // - start (smallest) offset that needs tracking (1 byte)
 // - a list of bitmaps.
 //   In a bitmap bit i is set if the i-th spill slot is live.
 //
 // At a PC where the liveness info changes, a PCDATA indicates the
 // byte offset of the liveness map in the FUNCDATA. PCDATA -1 is a
 // special case indicating all slots are live (for binary size
 // saving).

 const allLiveIdx = -1

 // name and offset
 type nameOff struct {
 	n   *ir.Name
 	off int64
 }

 func (a nameOff) FrameOffset() int64 { return a.n.FrameOffset() + a.off }
 func (a nameOff) String() string     { return fmt.Sprintf("%v+%d", a.n, a.off) }

 type blockArgEffects struct {
 	livein  bitvec.BitVec // variables live at block entry
 	liveout bitvec.BitVec // variables live at block exit
 }

 type argLiveness struct {
 	fn   *ir.Func
 	f    *ssa.Func
 	args []nameOff         // name and offset of spill slots
 	idx  map[nameOff]int32 // index in args

 	be []blockArgEffects // indexed by block ID

 	bvset bvecSet // Set of liveness bitmaps, used for uniquifying.

 	// Liveness map indices at each Value (where it changes) and Block entry.
 	// During the computation the indices are temporarily index to bvset.
 	// At the end they will be index (offset) to the output funcdata (changed
 	// in (*argLiveness).emit).
 	blockIdx map[ssa.ID]int
 	valueIdx map[ssa.ID]int
 }

 // ArgLiveness computes the liveness information of register argument spill slots.
 // An argument's spill slot is "live" if we know it contains a meaningful value,
 // that is, we have stored the register value to it.
 // Returns the liveness map indices at each Block entry and at each Value (where
 // it changes).
 func ArgLiveness(fn *ir.Func, f *ssa.Func, pp *objw.Progs) (blockIdx, valueIdx map[ssa.ID]int) {
 	if f.OwnAux.ABIInfo().InRegistersUsed() == 0 || base.Flag.N != 0 {
 		// No register args. Nothing to emit.
 		// Or if -N is used we spill everything upfront so it is always live.
 		return nil, nil
 	}

 	lv := &argLiveness{
 		fn:       fn,
 		f:        f,
 		idx:      make(map[nameOff]int32),
 		be:       make([]blockArgEffects, f.NumBlocks()),
 		blockIdx: make(map[ssa.ID]int),
 		valueIdx: make(map[ssa.ID]int),
 	}
 	// Gather all register arg spill slots.
 	for _, a := range f.OwnAux.ABIInfo().InParams() {
 		n := a.Name
 		if n == nil || len(a.Registers) == 0 {
 			continue
 		}
 		_, offs := a.RegisterTypesAndOffsets()
 		for _, off := range offs {
 			if n.FrameOffset()+off > 0xff {
 				// We only print a limited number of args, with stack
 				// offsets no larger than 255.
 				continue
 			}
 			lv.args = append(lv.args, nameOff{n, off})
 		}
 	}
 	if len(lv.args) > 10 {
 		lv.args = lv.args[:10] // We print no more than 10 args.
 	}

 	// We spill address-taken or non-SSA-able value upfront, so they are always live.
 	alwaysLive := func(n *ir.Name) bool { return n.Addrtaken() || !ssa.CanSSA(n.Type()) }

 	// We'll emit the smallest offset for the slots that need liveness info.
 	// No need to include a slot with a lower offset if it is always live.
 	for len(lv.args) > 0 && alwaysLive(lv.args[0].n) {
 		lv.args = lv.args[1:]
 	}
 	if len(lv.args) == 0 {
 		return // everything is always live
 	}

 	for i, a := range lv.args {
 		lv.idx[a] = int32(i)
 	}

 	nargs := int32(len(lv.args))
 	bulk := bitvec.NewBulk(nargs, int32(len(f.Blocks)*2))
 	for _, b := range f.Blocks {
 		be := &lv.be[b.ID]
 		be.livein = bulk.Next()
 		be.liveout = bulk.Next()

 		// initialize to all 1s, so we can AND them
 		be.livein.Not()
 		be.liveout.Not()
 	}

 	entrybe := &lv.be[f.Entry.ID]
 	entrybe.livein.Clear()
 	for i, a := range lv.args {
 		if alwaysLive(a.n) {
 			entrybe.livein.Set(int32(i))
 		}
 	}

 	// Visit blocks in reverse-postorder, compute block effects.
 	po := f.Postorder()
 	for i := len(po) - 1; i >= 0; i-- {
 		b := po[i]
 		be := &lv.be[b.ID]

 		// A slot is live at block entry if it is live in all predecessors.
 		for _, pred := range b.Preds {
 			pb := pred.Block()
 			be.livein.And(be.livein, lv.be[pb.ID].liveout)
 		}

 		be.liveout.Copy(be.livein)
 		for _, v := range b.Values {
 			lv.valueEffect(v, be.liveout)
 		}
 	}

 	// Coalesce identical live vectors. Compute liveness indices at each PC
 	// where it changes.
 	live := bitvec.New(nargs)
 	addToSet := func(bv bitvec.BitVec) (int, bool) {
 		if bv.Count() == int(nargs) { // special case for all live
 			return allLiveIdx, false
 		}
 		return lv.bvset.add(bv)
 	}
 	for _, b := range lv.f.Blocks {
 		be := &lv.be[b.ID]
 		lv.blockIdx[b.ID], _ = addToSet(be.livein)

 		live.Copy(be.livein)
 		var lastv *ssa.Value
 		for i, v := range b.Values {
 			if lv.valueEffect(v, live) {
 				// Record that liveness changes but not emit a map now.
 				// For a sequence of StoreRegs we only need to emit one
 				// at last.
 				lastv = v
 			}
 			if lastv != nil && (mayFault(v) || i == len(b.Values)-1) {
 				// Emit the liveness map if it may fault or at the end of
 				// the block. We may need a traceback if the instruction
 				// may cause a panic.
 				var added bool
 				lv.valueIdx[lastv.ID], added = addToSet(live)
 				if added {
 					// live is added to bvset and we cannot modify it now.
 					// Make a copy.
 					t := live
 					live = bitvec.New(nargs)
 					live.Copy(t)
 				}
 				lastv = nil
 			}
 		}

 		// Sanity check.
 		if !live.Eq(be.liveout) {
 			panic("wrong arg liveness map at block end")
 		}
 	}

 	// Emit funcdata symbol, update indices to offsets in the symbol data.
 	lsym := lv.emit()
 	fn.LSym.Func().ArgLiveInfo = lsym

 	//lv.print()

 	p := pp.Prog(obj.AFUNCDATA)
 	p.From.SetConst(abi.FUNCDATA_ArgLiveInfo)
 	p.To.Type = obj.TYPE_MEM
 	p.To.Name = obj.NAME_EXTERN
 	p.To.Sym = lsym

 	return lv.blockIdx, lv.valueIdx
 }

 // valueEffect applies the effect of v to live, return whether it is changed.
 func (lv *argLiveness) valueEffect(v *ssa.Value, live bitvec.BitVec) bool {
 	if v.Op != ssa.OpStoreReg { // TODO: include other store instructions?
 		return false
 	}
 	n, off := ssa.AutoVar(v)
 	if n.Class != ir.PPARAM {
 		return false
 	}
 	i, ok := lv.idx[nameOff{n, off}]
 	if !ok || live.Get(i) {
 		return false
 	}
 	live.Set(i)
 	return true
 }

 func mayFault(v *ssa.Value) bool {
 	switch v.Op {
 	case ssa.OpLoadReg, ssa.OpStoreReg, ssa.OpCopy, ssa.OpPhi,
 		ssa.OpVarDef, ssa.OpVarLive, ssa.OpKeepAlive,
 		ssa.OpSelect0, ssa.OpSelect1, ssa.OpSelectN, ssa.OpMakeResult,
 		ssa.OpConvert, ssa.OpInlMark, ssa.OpGetG:
 		return false
 	}
 	if len(v.Args) == 0 {
 		return false // assume constant op cannot fault
 	}
 	return true // conservatively assume all other ops could fault
 }

 func (lv *argLiveness) print() {
 	fmt.Println("argument liveness:", lv.f.Name)
 	live := bitvec.New(int32(len(lv.args)))
 	for _, b := range lv.f.Blocks {
 		be := &lv.be[b.ID]

 		fmt.Printf("%v: live in: ", b)
 		lv.printLivenessVec(be.livein)
 		if idx, ok := lv.blockIdx[b.ID]; ok {
 			fmt.Printf("   #%d", idx)
 		}
 		fmt.Println()

 		for _, v := range b.Values {
 			if lv.valueEffect(v, live) {
 				fmt.Printf("  %v: ", v)
 				lv.printLivenessVec(live)
 				if idx, ok := lv.valueIdx[v.ID]; ok {
 					fmt.Printf("   #%d", idx)
 				}
 				fmt.Println()
 			}
 		}

 		fmt.Printf("%v: live out: ", b)
 		lv.printLivenessVec(be.liveout)
 		fmt.Println()
 	}
 	fmt.Println("liveness maps data:", lv.fn.LSym.Func().ArgLiveInfo.P)
 }

 func (lv *argLiveness) printLivenessVec(bv bitvec.BitVec) {
 	for i, a := range lv.args {
 		if bv.Get(int32(i)) {
 			fmt.Printf("%v ", a)
 		}
 	}
 }

 func (lv *argLiveness) emit() *obj.LSym {
 	livenessMaps := lv.bvset.extractUnique()

 	// stack offsets of register arg spill slots
 	argOffsets := make([]uint8, len(lv.args))
 	for i, a := range lv.args {
 		off := a.FrameOffset()
 		if off > 0xff {
 			panic("offset too large")
 		}
 		argOffsets[i] = uint8(off)
 	}

 	idx2off := make([]int, len(livenessMaps))

 	lsym := base.Ctxt.Lookup(lv.fn.LSym.Name + ".argliveinfo")
 	lsym.Set(obj.AttrContentAddressable, true)

 	off := objw.Uint8(lsym, 0, argOffsets[0]) // smallest offset that needs liveness info.
 	for idx, live := range livenessMaps {
 		idx2off[idx] = off
 		off = objw.BitVec(lsym, off, live)
 	}

 	// Update liveness indices to offsets.
 	for i, x := range lv.blockIdx {
 		if x != allLiveIdx {
 			lv.blockIdx[i] = idx2off[x]
 		}
 	}
 	for i, x := range lv.valueIdx {
 		if x != allLiveIdx {
 			lv.valueIdx[i] = idx2off[x]
 		}
 	}

 	return lsym
 }
	// Copyright 2021 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	package liveness

	import (
	"fmt"
	"internal/abi"

	"cmd/compile/internal/base"
	"cmd/compile/internal/bitvec"
	"cmd/compile/internal/ir"
	"cmd/compile/internal/objw"
	"cmd/compile/internal/ssa"
	"cmd/internal/obj"
	)

	// Argument liveness tracking.
	//
	// For arguments passed in registers, this file tracks if their spill slots
	// are live for runtime traceback. An argument spill slot is live at a PC
	// if we know that an actual value has stored into it at or before this point.
	//
	// Stack args are always live and not tracked in this code. Stack args are
	// laid out before register spill slots, so we emit the smallest offset that
	// needs tracking. Slots before that offset are always live. That offset is
	// usually the offset of the first spill slot. But if the first spill slot is
	// always live (e.g. if it is address-taken), it will be the offset of a later
	// one.
	//
	// The liveness information is emitted as a FUNCDATA and a PCDATA.
	//
	// FUNCDATA format:
	// - start (smallest) offset that needs tracking (1 byte)
	// - a list of bitmaps.
	// In a bitmap bit i is set if the i-th spill slot is live.
	//
	// At a PC where the liveness info changes, a PCDATA indicates the
	// byte offset of the liveness map in the FUNCDATA. PCDATA -1 is a
	// special case indicating all slots are live (for binary size
	// saving).

	const allLiveIdx = -1

	// name and offset
	type nameOff struct {
	n *ir.Name
	off int64
	}

	func (a nameOff) FrameOffset() int64 { return a.n.FrameOffset() + a.off }
	func (a nameOff) String() string { return fmt.Sprintf("%v+%d", a.n, a.off) }

	type blockArgEffects struct {
	livein bitvec.BitVec // variables live at block entry
	liveout bitvec.BitVec // variables live at block exit
	}

	type argLiveness struct {
	fn *ir.Func
	f *ssa.Func
	args []nameOff // name and offset of spill slots
	idx map[nameOff]int32 // index in args

	be []blockArgEffects // indexed by block ID

	bvset bvecSet // Set of liveness bitmaps, used for uniquifying.

	// Liveness map indices at each Value (where it changes) and Block entry.
	// During the computation the indices are temporarily index to bvset.
	// At the end they will be index (offset) to the output funcdata (changed
	// in (*argLiveness).emit).
	blockIdx map[ssa.ID]int
	valueIdx map[ssa.ID]int
	}

	// ArgLiveness computes the liveness information of register argument spill slots.
	// An argument's spill slot is "live" if we know it contains a meaningful value,
	// that is, we have stored the register value to it.
	// Returns the liveness map indices at each Block entry and at each Value (where
	// it changes).
	func ArgLiveness(fn ir.Func, f ssa.Func, pp *objw.Progs) (blockIdx, valueIdx map[ssa.ID]int) {
	if f.OwnAux.ABIInfo().InRegistersUsed() == 0 \|\| base.Flag.N != 0 {
	// No register args. Nothing to emit.
	// Or if -N is used we spill everything upfront so it is always live.
	return nil, nil
	}

	lv := &argLiveness{
	fn: fn,
	f: f,
	idx: make(map[nameOff]int32),
	be: make([]blockArgEffects, f.NumBlocks()),
	blockIdx: make(map[ssa.ID]int),
	valueIdx: make(map[ssa.ID]int),
	}
	// Gather all register arg spill slots.
	for _, a := range f.OwnAux.ABIInfo().InParams() {
	n := a.Name
	if n == nil \|\| len(a.Registers) == 0 {
	continue
	}
	_, offs := a.RegisterTypesAndOffsets()
	for _, off := range offs {
	if n.FrameOffset()+off > 0xff {
	// We only print a limited number of args, with stack
	// offsets no larger than 255.
	continue
	}
	lv.args = append(lv.args, nameOff{n, off})
	}
	}
	if len(lv.args) > 10 {
	lv.args = lv.args[:10] // We print no more than 10 args.
	}

	// We spill address-taken or non-SSA-able value upfront, so they are always live.
	alwaysLive := func(n *ir.Name) bool { return n.Addrtaken() \|\| !ssa.CanSSA(n.Type()) }

	// We'll emit the smallest offset for the slots that need liveness info.
	// No need to include a slot with a lower offset if it is always live.
	for len(lv.args) > 0 && alwaysLive(lv.args[0].n) {
	lv.args = lv.args[1:]
	}
	if len(lv.args) == 0 {
	return // everything is always live
	}

	for i, a := range lv.args {
	lv.idx[a] = int32(i)
	}

	nargs := int32(len(lv.args))
	bulk := bitvec.NewBulk(nargs, int32(len(f.Blocks)*2))
	for _, b := range f.Blocks {
	be := &lv.be[b.ID]
	be.livein = bulk.Next()
	be.liveout = bulk.Next()

	// initialize to all 1s, so we can AND them
	be.livein.Not()
	be.liveout.Not()
	}

	entrybe := &lv.be[f.Entry.ID]
	entrybe.livein.Clear()
	for i, a := range lv.args {
	if alwaysLive(a.n) {
	entrybe.livein.Set(int32(i))
	}
	}

	// Visit blocks in reverse-postorder, compute block effects.
	po := f.Postorder()
	for i := len(po) - 1; i >= 0; i-- {
	b := po[i]
	be := &lv.be[b.ID]

	// A slot is live at block entry if it is live in all predecessors.
	for _, pred := range b.Preds {
	pb := pred.Block()
	be.livein.And(be.livein, lv.be[pb.ID].liveout)
	}

	be.liveout.Copy(be.livein)
	for _, v := range b.Values {
	lv.valueEffect(v, be.liveout)
	}
	}

	// Coalesce identical live vectors. Compute liveness indices at each PC
	// where it changes.
	live := bitvec.New(nargs)
	addToSet := func(bv bitvec.BitVec) (int, bool) {
	if bv.Count() == int(nargs) { // special case for all live
	return allLiveIdx, false
	}
	return lv.bvset.add(bv)
	}
	for _, b := range lv.f.Blocks {
	be := &lv.be[b.ID]
	lv.blockIdx[b.ID], _ = addToSet(be.livein)

	live.Copy(be.livein)
	var lastv *ssa.Value
	for i, v := range b.Values {
	if lv.valueEffect(v, live) {
	// Record that liveness changes but not emit a map now.
	// For a sequence of StoreRegs we only need to emit one
	// at last.
	lastv = v
	}
	if lastv != nil && (mayFault(v) \|\| i == len(b.Values)-1) {
	// Emit the liveness map if it may fault or at the end of
	// the block. We may need a traceback if the instruction
	// may cause a panic.
	var added bool
	lv.valueIdx[lastv.ID], added = addToSet(live)
	if added {
	// live is added to bvset and we cannot modify it now.
	// Make a copy.
	t := live
	live = bitvec.New(nargs)
	live.Copy(t)
	}
	lastv = nil
	}
	}

	// Sanity check.
	if !live.Eq(be.liveout) {
	panic("wrong arg liveness map at block end")
	}
	}

	// Emit funcdata symbol, update indices to offsets in the symbol data.
	lsym := lv.emit()
	fn.LSym.Func().ArgLiveInfo = lsym

	//lv.print()

	p := pp.Prog(obj.AFUNCDATA)
	p.From.SetConst(abi.FUNCDATA_ArgLiveInfo)
	p.To.Type = obj.TYPE_MEM
	p.To.Name = obj.NAME_EXTERN
	p.To.Sym = lsym

	return lv.blockIdx, lv.valueIdx
	}

	// valueEffect applies the effect of v to live, return whether it is changed.
	func (lv argLiveness) valueEffect(v ssa.Value, live bitvec.BitVec) bool {
	if v.Op != ssa.OpStoreReg { // TODO: include other store instructions?
	return false
	}
	n, off := ssa.AutoVar(v)
	if n.Class != ir.PPARAM {
	return false
	}
	i, ok := lv.idx[nameOff{n, off}]
	if !ok \|\| live.Get(i) {
	return false
	}
	live.Set(i)
	return true
	}

	func mayFault(v *ssa.Value) bool {
	switch v.Op {
	case ssa.OpLoadReg, ssa.OpStoreReg, ssa.OpCopy, ssa.OpPhi,
	ssa.OpVarDef, ssa.OpVarLive, ssa.OpKeepAlive,
	ssa.OpSelect0, ssa.OpSelect1, ssa.OpSelectN, ssa.OpMakeResult,
	ssa.OpConvert, ssa.OpInlMark, ssa.OpGetG:
	return false
	}
	if len(v.Args) == 0 {
	return false // assume constant op cannot fault
	}
	return true // conservatively assume all other ops could fault
	}

	func (lv *argLiveness) print() {
	fmt.Println("argument liveness:", lv.f.Name)
	live := bitvec.New(int32(len(lv.args)))
	for _, b := range lv.f.Blocks {
	be := &lv.be[b.ID]

	fmt.Printf("%v: live in: ", b)
	lv.printLivenessVec(be.livein)
	if idx, ok := lv.blockIdx[b.ID]; ok {
	fmt.Printf(" #%d", idx)
	}
	fmt.Println()

	for _, v := range b.Values {
	if lv.valueEffect(v, live) {
	fmt.Printf(" %v: ", v)
	lv.printLivenessVec(live)
	if idx, ok := lv.valueIdx[v.ID]; ok {
	fmt.Printf(" #%d", idx)
	}
	fmt.Println()
	}
	}

	fmt.Printf("%v: live out: ", b)
	lv.printLivenessVec(be.liveout)
	fmt.Println()
	}
	fmt.Println("liveness maps data:", lv.fn.LSym.Func().ArgLiveInfo.P)
	}

	func (lv *argLiveness) printLivenessVec(bv bitvec.BitVec) {
	for i, a := range lv.args {
	if bv.Get(int32(i)) {
	fmt.Printf("%v ", a)
	}
	}
	}

	func (lv argLiveness) emit() obj.LSym {
	livenessMaps := lv.bvset.extractUnique()

	// stack offsets of register arg spill slots
	argOffsets := make([]uint8, len(lv.args))
	for i, a := range lv.args {
	off := a.FrameOffset()
	if off > 0xff {
	panic("offset too large")
	}
	argOffsets[i] = uint8(off)
	}

	idx2off := make([]int, len(livenessMaps))

	lsym := base.Ctxt.Lookup(lv.fn.LSym.Name + ".argliveinfo")
	lsym.Set(obj.AttrContentAddressable, true)

	off := objw.Uint8(lsym, 0, argOffsets[0]) // smallest offset that needs liveness info.
	for idx, live := range livenessMaps {
	idx2off[idx] = off
	off = objw.BitVec(lsym, off, live)
	}

	// Update liveness indices to offsets.
	for i, x := range lv.blockIdx {
	if x != allLiveIdx {
	lv.blockIdx[i] = idx2off[x]
	}
	}
	for i, x := range lv.valueIdx {
	if x != allLiveIdx {
	lv.valueIdx[i] = idx2off[x]
	}
	}

	return lsym
	}