aboutsummaryrefslogtreecommitdiff
path: root/src/cmd/compile/internal/ssa/debug.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/cmd/compile/internal/ssa/debug.go')
-rw-r--r--src/cmd/compile/internal/ssa/debug.go559
1 files changed, 559 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/debug.go b/src/cmd/compile/internal/ssa/debug.go
new file mode 100644
index 0000000000..55db45b642
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/debug.go
@@ -0,0 +1,559 @@
+// 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")
+ }
+
+}
7apu2bq3rhoylwmucxizk54afw5jyda7pho4j5zdcqpwkufke7zdzwad.onion