| // Copyright 2017 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 ssa |
| |
| import ( |
| "cmd/internal/obj" |
| "fmt" |
| "strings" |
| ) |
| |
| type SlotID int32 |
| |
| // A FuncDebug contains all the debug information for the variables in a |
| // function. Variables are identified by their LocalSlot, which may be the |
| // result of decomposing a larger variable. |
| type FuncDebug struct { |
| Slots []*LocalSlot |
| Variables []VarLocList |
| Registers []Register |
| } |
| |
| // append adds a location to the location list for slot. |
| func (f *FuncDebug) append(slot SlotID, loc *VarLoc) { |
| f.Variables[slot].append(loc) |
| } |
| |
| // lastLoc returns the last VarLoc for slot, or nil if it has none. |
| func (f *FuncDebug) lastLoc(slot SlotID) *VarLoc { |
| return f.Variables[slot].last() |
| } |
| |
| func (f *FuncDebug) String() string { |
| var vars []string |
| for slot, list := range f.Variables { |
| if len(list.Locations) == 0 { |
| continue |
| } |
| vars = append(vars, fmt.Sprintf("%v = %v", f.Slots[slot], list)) |
| } |
| return fmt.Sprintf("{%v}", strings.Join(vars, ", ")) |
| } |
| |
| // A VarLocList contains the locations for a variable, in program text order. |
| // It will often have gaps. |
| type VarLocList struct { |
| Locations []*VarLoc |
| } |
| |
| func (l *VarLocList) append(loc *VarLoc) { |
| l.Locations = append(l.Locations, loc) |
| } |
| |
| // last returns the last location in the list. |
| func (l *VarLocList) last() *VarLoc { |
| if l == nil || len(l.Locations) == 0 { |
| return nil |
| } |
| return l.Locations[len(l.Locations)-1] |
| } |
| |
| // A VarLoc describes a variable's location in a single contiguous range |
| // of program text. It is generated from the SSA representation, but it |
| // refers to the generated machine code, so the Values referenced are better |
| // understood as PCs than actual Values, and the ranges can cross blocks. |
| // The range is defined first by Values, which are then mapped to Progs |
| // during genssa and finally to function PCs after assembly. |
| // A variable can be on the stack and in any number of registers. |
| type VarLoc struct { |
| // Inclusive -- the first SSA value that the range covers. The value |
| // doesn't necessarily have anything to do with the variable; it just |
| // identifies a point in the program text. |
| Start *Value |
| // Exclusive -- the first SSA value after start that the range doesn't |
| // cover. A location with start == end is empty. |
| End *Value |
| // The prog/PCs corresponding to Start and End above. These are for the |
| // convenience of later passes, since code generation isn't done when |
| // BuildFuncDebug runs. |
| StartProg, EndProg *obj.Prog |
| StartPC, EndPC int64 |
| |
| // The registers this variable is available in. There can be more than |
| // one in various situations, e.g. it's being moved between registers. |
| Registers RegisterSet |
| // Indicates whether the variable is on the stack. The stack position is |
| // stored in the associated gc.Node. |
| OnStack bool |
| |
| // Used only during generation. Indicates whether this location lasts |
| // past the block's end. Without this, there would be no way to distinguish |
| // between a range that ended on the last Value of a block and one that |
| // didn't end at all. |
| survivedBlock bool |
| } |
| |
| // RegisterSet is a bitmap of registers, indexed by Register.num. |
| type RegisterSet uint64 |
| |
| func (v *VarLoc) String() string { |
| var registers []Register |
| if v.Start != nil { |
| registers = v.Start.Block.Func.Config.registers |
| } |
| loc := "" |
| if !v.OnStack && v.Registers == 0 { |
| loc = "!!!no location!!!" |
| } |
| if v.OnStack { |
| loc += "stack," |
| } |
| var regnames []string |
| for reg := 0; reg < 64; reg++ { |
| if v.Registers&(1<<uint8(reg)) == 0 { |
| continue |
| } |
| if registers != nil { |
| regnames = append(regnames, registers[reg].Name()) |
| } else { |
| regnames = append(regnames, fmt.Sprintf("reg%v", reg)) |
| } |
| } |
| loc += strings.Join(regnames, ",") |
| pos := func(v *Value, p *obj.Prog, pc int64) string { |
| if v == nil { |
| return "?" |
| } |
| if p == nil { |
| return fmt.Sprintf("v%v", v.ID) |
| } |
| return fmt.Sprintf("v%v/%x", v.ID, pc) |
| } |
| surv := "" |
| if v.survivedBlock { |
| surv = "+" |
| } |
| return fmt.Sprintf("%v-%v%s@%s", pos(v.Start, v.StartProg, v.StartPC), pos(v.End, v.EndProg, v.EndPC), surv, loc) |
| } |
| |
| // unexpected is used to indicate an inconsistency or bug in the debug info |
| // generation process. These are not fixable by users. At time of writing, |
| // changing this to a Fprintf(os.Stderr) and running make.bash generates |
| // thousands of warnings. |
| func (s *debugState) unexpected(v *Value, msg string, args ...interface{}) { |
| s.f.Logf("unexpected at "+fmt.Sprint(v.ID)+":"+msg, args...) |
| } |
| |
| func (s *debugState) logf(msg string, args ...interface{}) { |
| s.f.Logf(msg, args...) |
| } |
| |
| type debugState struct { |
| loggingEnabled bool |
| slots []*LocalSlot |
| f *Func |
| cache *Cache |
| numRegisters int |
| |
| // working storage for BuildFuncDebug, reused between blocks. |
| registerContents [][]SlotID |
| } |
| |
| // BuildFuncDebug returns debug information for f. |
| // f must be fully processed, so that each Value is where it will be when |
| // machine code is emitted. |
| func BuildFuncDebug(f *Func, loggingEnabled bool) *FuncDebug { |
| if f.RegAlloc == nil { |
| f.Fatalf("BuildFuncDebug on func %v that has not been fully processed", f) |
| } |
| state := &debugState{ |
| loggingEnabled: loggingEnabled, |
| slots: make([]*LocalSlot, len(f.Names)), |
| cache: f.Cache, |
| f: f, |
| numRegisters: len(f.Config.registers), |
| registerContents: make([][]SlotID, len(f.Config.registers)), |
| } |
| // TODO: consider storing this in Cache and reusing across functions. |
| valueNames := make([][]SlotID, f.NumValues()) |
| |
| for i, slot := range f.Names { |
| slot := slot |
| state.slots[i] = &slot |
| |
| if isSynthetic(&slot) { |
| continue |
| } |
| for _, value := range f.NamedValues[slot] { |
| valueNames[value.ID] = append(valueNames[value.ID], SlotID(i)) |
| } |
| } |
| |
| if state.loggingEnabled { |
| var names []string |
| for i, name := range f.Names { |
| names = append(names, fmt.Sprintf("%v = %v", i, name)) |
| } |
| state.logf("Name table: %v\n", strings.Join(names, ", ")) |
| } |
| |
| // Build up block states, starting with the first block, then |
| // processing blocks once their predecessors have been processed. |
| |
| // TODO: use a reverse post-order traversal instead of the work queue. |
| |
| // Location list entries for each block. |
| blockLocs := make([]*FuncDebug, f.NumBlocks()) |
| |
| // Work queue of blocks to visit. Some of them may already be processed. |
| work := []*Block{f.Entry} |
| |
| for len(work) > 0 { |
| b := work[0] |
| work = work[1:] |
| if blockLocs[b.ID] != nil { |
| continue // already processed |
| } |
| if !state.predecessorsDone(b, blockLocs) { |
| continue // not ready yet |
| } |
| |
| for _, edge := range b.Succs { |
| if blockLocs[edge.Block().ID] != nil { |
| continue |
| } |
| work = append(work, edge.Block()) |
| } |
| |
| // Build the starting state for the block from the final |
| // state of its predecessors. |
| locs := state.mergePredecessors(b, blockLocs) |
| if state.loggingEnabled { |
| state.logf("Processing %v, initial locs %v, regs %v\n", b, locs, state.registerContents) |
| } |
| // Update locs/registers with the effects of each Value. |
| for _, v := range b.Values { |
| slots := valueNames[v.ID] |
| |
| // Loads and stores inherit the names of their sources. |
| var source *Value |
| switch v.Op { |
| case OpStoreReg: |
| source = v.Args[0] |
| case OpLoadReg: |
| switch a := v.Args[0]; a.Op { |
| case OpArg: |
| source = a |
| case OpStoreReg: |
| source = a.Args[0] |
| default: |
| state.unexpected(v, "load with unexpected source op %v", a) |
| } |
| } |
| if source != nil { |
| slots = append(slots, valueNames[source.ID]...) |
| // As of writing, the compiler never uses a load/store as a |
| // source of another load/store, so there's no reason this should |
| // ever be consulted. Update just in case, and so that when |
| // valueNames is cached, we can reuse the memory. |
| valueNames[v.ID] = slots |
| } |
| |
| if len(slots) == 0 { |
| continue |
| } |
| |
| reg, _ := f.getHome(v.ID).(*Register) |
| state.processValue(locs, v, slots, reg) |
| |
| } |
| |
| // The block is done; end the locations for all its slots. |
| for _, locList := range locs.Variables { |
| last := locList.last() |
| if last == nil || last.End != nil { |
| continue |
| } |
| if len(b.Values) != 0 { |
| last.End = b.Values[len(b.Values)-1] |
| } else { |
| // This happens when a value survives into an empty block from its predecessor. |
| // Just carry it forward for liveness's sake. |
| last.End = last.Start |
| } |
| last.survivedBlock = true |
| } |
| if state.loggingEnabled { |
| f.Logf("Block done: locs %v, regs %v. work = %+v\n", locs, state.registerContents, work) |
| } |
| blockLocs[b.ID] = locs |
| } |
| |
| // Build the complete debug info by concatenating each of the blocks' |
| // locations together. |
| info := &FuncDebug{ |
| Variables: make([]VarLocList, len(state.slots)), |
| Slots: state.slots, |
| Registers: f.Config.registers, |
| } |
| for _, b := range f.Blocks { |
| // Ignore empty blocks; there will be some records for liveness |
| // but they're all useless. |
| if len(b.Values) == 0 { |
| continue |
| } |
| if blockLocs[b.ID] == nil { |
| state.unexpected(b.Values[0], "Never processed block %v\n", b) |
| continue |
| } |
| for slot, blockLocList := range blockLocs[b.ID].Variables { |
| for _, loc := range blockLocList.Locations { |
| if !loc.OnStack && loc.Registers == 0 { |
| state.unexpected(loc.Start, "Location for %v with no storage: %+v\n", state.slots[slot], loc) |
| continue // don't confuse downstream with our bugs |
| } |
| if loc.Start == nil || loc.End == nil { |
| state.unexpected(b.Values[0], "Location for %v missing start or end: %v\n", state.slots[slot], loc) |
| continue |
| } |
| info.append(SlotID(slot), loc) |
| } |
| } |
| } |
| if state.loggingEnabled { |
| f.Logf("Final result:\n") |
| for slot, locList := range info.Variables { |
| f.Logf("\t%v => %v\n", state.slots[slot], locList) |
| } |
| } |
| return info |
| } |
| |
| // isSynthetic reports whether if slot represents a compiler-inserted variable, |
| // e.g. an autotmp or an anonymous return value that needed a stack slot. |
| func isSynthetic(slot *LocalSlot) bool { |
| c := slot.Name()[0] |
| return c == '.' || c == '~' |
| } |
| |
| // predecessorsDone reports whether block is ready to be processed. |
| func (state *debugState) predecessorsDone(b *Block, blockLocs []*FuncDebug) bool { |
| f := b.Func |
| for _, edge := range b.Preds { |
| // Ignore back branches, e.g. the continuation of a for loop. |
| // This may not work for functions with mutual gotos, which are not |
| // reducible, in which case debug information will be missing for any |
| // code after that point in the control flow. |
| if f.sdom().isAncestorEq(b, edge.b) { |
| if state.loggingEnabled { |
| f.Logf("ignoring back branch from %v to %v\n", edge.b, b) |
| } |
| continue // back branch |
| } |
| if blockLocs[edge.b.ID] == nil { |
| if state.loggingEnabled { |
| f.Logf("%v is not ready because %v isn't done\n", b, edge.b) |
| } |
| return false |
| } |
| } |
| return true |
| } |
| |
| // mergePredecessors takes the end state of each of b's predecessors and |
| // intersects them to form the starting state for b. |
| // The registers slice (the second return value) will be reused for each call to mergePredecessors. |
| func (state *debugState) mergePredecessors(b *Block, blockLocs []*FuncDebug) *FuncDebug { |
| live := make([]VarLocList, len(state.slots)) |
| |
| // Filter out back branches. |
| var preds []*Block |
| for _, pred := range b.Preds { |
| if blockLocs[pred.b.ID] != nil { |
| preds = append(preds, pred.b) |
| } |
| } |
| |
| if len(preds) > 0 { |
| p := preds[0] |
| for slot, locList := range blockLocs[p.ID].Variables { |
| last := locList.last() |
| if last == nil || !last.survivedBlock { |
| continue |
| } |
| // If this block is empty, carry forward the end value for liveness. |
| // It'll be ignored later. |
| start := last.End |
| if len(b.Values) != 0 { |
| start = b.Values[0] |
| } |
| loc := state.cache.NewVarLoc() |
| loc.Start = start |
| loc.OnStack = last.OnStack |
| loc.Registers = last.Registers |
| live[slot].append(loc) |
| } |
| } |
| if state.loggingEnabled && len(b.Preds) > 1 { |
| state.logf("Starting merge with state from %v: %v\n", b.Preds[0].b, blockLocs[b.Preds[0].b.ID]) |
| } |
| for i := 1; i < len(preds); i++ { |
| p := preds[i] |
| if state.loggingEnabled { |
| state.logf("Merging in state from %v: %v &= %v\n", p, live, blockLocs[p.ID]) |
| } |
| |
| for slot, liveVar := range live { |
| liveLoc := liveVar.last() |
| if liveLoc == nil { |
| continue |
| } |
| |
| predLoc := blockLocs[p.ID].lastLoc(SlotID(slot)) |
| // Clear out slots missing/dead in p. |
| if predLoc == nil || !predLoc.survivedBlock { |
| live[slot].Locations = nil |
| continue |
| } |
| |
| // Unify storage locations. |
| liveLoc.OnStack = liveLoc.OnStack && predLoc.OnStack |
| liveLoc.Registers &= predLoc.Registers |
| } |
| } |
| |
| // Create final result. |
| locs := &FuncDebug{Variables: live, Slots: state.slots} |
| for reg := range state.registerContents { |
| state.registerContents[reg] = state.registerContents[reg][:0] |
| } |
| for slot, locList := range live { |
| loc := locList.last() |
| if loc == nil { |
| continue |
| } |
| for reg := 0; reg < state.numRegisters; reg++ { |
| if loc.Registers&(1<<uint8(reg)) != 0 { |
| state.registerContents[reg] = append(state.registerContents[reg], SlotID(slot)) |
| } |
| } |
| } |
| return locs |
| } |
| |
| // processValue updates locs and state.registerContents to reflect v, a value with |
| // the names in vSlots and homed in vReg. |
| func (state *debugState) processValue(locs *FuncDebug, v *Value, vSlots []SlotID, vReg *Register) { |
| switch { |
| case v.Op == OpRegKill: |
| if state.loggingEnabled { |
| existingSlots := make([]bool, len(state.slots)) |
| for _, slot := range state.registerContents[vReg.num] { |
| existingSlots[slot] = true |
| } |
| for _, slot := range vSlots { |
| if existingSlots[slot] { |
| existingSlots[slot] = false |
| } else { |
| state.unexpected(v, "regkill of unassociated name %v\n", state.slots[slot]) |
| } |
| } |
| for slot, live := range existingSlots { |
| if live { |
| state.unexpected(v, "leftover register name: %v\n", state.slots[slot]) |
| } |
| } |
| } |
| state.registerContents[vReg.num] = nil |
| |
| for _, slot := range vSlots { |
| last := locs.lastLoc(slot) |
| if last == nil { |
| state.unexpected(v, "regkill of already dead %v, %+v\n", vReg, state.slots[slot]) |
| continue |
| } |
| if state.loggingEnabled { |
| state.logf("at %v: %v regkilled out of %v\n", v.ID, state.slots[slot], vReg.Name()) |
| } |
| if last.End != nil { |
| state.unexpected(v, "regkill of dead slot, died at %v\n", last.End) |
| } |
| last.End = v |
| |
| regs := last.Registers &^ (1 << uint8(vReg.num)) |
| if !last.OnStack && regs == 0 { |
| continue |
| } |
| loc := state.cache.NewVarLoc() |
| loc.Start = v |
| loc.OnStack = last.OnStack |
| loc.Registers = regs |
| locs.append(slot, loc) |
| } |
| case v.Op == OpArg: |
| for _, slot := range vSlots { |
| if state.loggingEnabled { |
| state.logf("at %v: %v now on stack from arg\n", v.ID, state.slots[slot]) |
| } |
| loc := state.cache.NewVarLoc() |
| loc.Start = v |
| loc.OnStack = true |
| locs.append(slot, loc) |
| } |
| |
| case v.Op == OpStoreReg: |
| for _, slot := range vSlots { |
| if state.loggingEnabled { |
| state.logf("at %v: %v spilled to stack\n", v.ID, state.slots[slot]) |
| } |
| last := locs.lastLoc(slot) |
| if last == nil { |
| state.unexpected(v, "spill of unnamed register %v\n", vReg) |
| break |
| } |
| last.End = v |
| loc := state.cache.NewVarLoc() |
| loc.Start = v |
| loc.OnStack = true |
| loc.Registers = last.Registers |
| locs.append(slot, loc) |
| } |
| |
| case vReg != nil: |
| if state.loggingEnabled { |
| newSlots := make([]bool, len(state.slots)) |
| for _, slot := range vSlots { |
| newSlots[slot] = true |
| } |
| |
| for _, slot := range state.registerContents[vReg.num] { |
| if !newSlots[slot] { |
| state.unexpected(v, "%v clobbered\n", state.slots[slot]) |
| } |
| } |
| } |
| |
| for _, slot := range vSlots { |
| if state.loggingEnabled { |
| state.logf("at %v: %v now in %v\n", v.ID, state.slots[slot], vReg.Name()) |
| } |
| last := locs.lastLoc(slot) |
| if last != nil && last.End == nil { |
| last.End = v |
| } |
| state.registerContents[vReg.num] = append(state.registerContents[vReg.num], slot) |
| loc := state.cache.NewVarLoc() |
| loc.Start = v |
| if last != nil { |
| loc.OnStack = last.OnStack |
| loc.Registers = last.Registers |
| } |
| loc.Registers |= 1 << uint8(vReg.num) |
| locs.append(slot, loc) |
| } |
| default: |
| state.unexpected(v, "named value with no reg\n") |
| } |
| |
| } |