// 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" "cmd/compile/internal/base" "cmd/compile/internal/bitvec" "cmd/compile/internal/ir" "cmd/compile/internal/objw" "cmd/compile/internal/ssa" "cmd/internal/obj" "cmd/internal/objabi" ) // 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, ok := a.Name.(*ir.Name) if !ok || 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() || !f.Frontend().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(objabi.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.OpVarKill, 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 }