Source file src/cmd/compile/internal/ssa/debug.go

Documentation: cmd/compile/internal/ssa

     1  // Copyright 2017 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package ssa
     6  
     7  import (
     8  	"cmd/internal/dwarf"
     9  	"cmd/internal/obj"
    10  	"encoding/hex"
    11  	"fmt"
    12  	"math/bits"
    13  	"sort"
    14  	"strings"
    15  )
    16  
    17  type SlotID int32
    18  type VarID int32
    19  
    20  // A FuncDebug contains all the debug information for the variables in a
    21  // function. Variables are identified by their LocalSlot, which may be the
    22  // result of decomposing a larger variable.
    23  type FuncDebug struct {
    24  	// Slots is all the slots used in the debug info, indexed by their SlotID.
    25  	Slots []LocalSlot
    26  	// The user variables, indexed by VarID.
    27  	Vars []GCNode
    28  	// The slots that make up each variable, indexed by VarID.
    29  	VarSlots [][]SlotID
    30  	// The location list data, indexed by VarID. Must be processed by PutLocationList.
    31  	LocationLists [][]byte
    32  
    33  	// Filled in by the user. Translates Block and Value ID to PC.
    34  	GetPC func(ID, ID) int64
    35  }
    36  
    37  type BlockDebug struct {
    38  	// Whether the block had any changes to user variables at all.
    39  	relevant bool
    40  	// State at the end of the block if it's fully processed. Immutable once initialized.
    41  	endState []liveSlot
    42  }
    43  
    44  // A liveSlot is a slot that's live in loc at entry/exit of a block.
    45  type liveSlot struct {
    46  	// An inlined VarLoc, so it packs into 16 bytes instead of 20.
    47  	Registers RegisterSet
    48  	StackOffset
    49  
    50  	slot SlotID
    51  }
    52  
    53  func (loc liveSlot) absent() bool {
    54  	return loc.Registers == 0 && !loc.onStack()
    55  }
    56  
    57  // StackOffset encodes whether a value is on the stack and if so, where. It is
    58  // a 31-bit integer followed by a presence flag at the low-order bit.
    59  type StackOffset int32
    60  
    61  func (s StackOffset) onStack() bool {
    62  	return s != 0
    63  }
    64  
    65  func (s StackOffset) stackOffsetValue() int32 {
    66  	return int32(s) >> 1
    67  }
    68  
    69  // stateAtPC is the current state of all variables at some point.
    70  type stateAtPC struct {
    71  	// The location of each known slot, indexed by SlotID.
    72  	slots []VarLoc
    73  	// The slots present in each register, indexed by register number.
    74  	registers [][]SlotID
    75  }
    76  
    77  // reset fills state with the live variables from live.
    78  func (state *stateAtPC) reset(live []liveSlot) {
    79  	slots, registers := state.slots, state.registers
    80  	for i := range slots {
    81  		slots[i] = VarLoc{}
    82  	}
    83  	for i := range registers {
    84  		registers[i] = registers[i][:0]
    85  	}
    86  	for _, live := range live {
    87  		slots[live.slot] = VarLoc{live.Registers, live.StackOffset}
    88  		if live.Registers == 0 {
    89  			continue
    90  		}
    91  
    92  		mask := uint64(live.Registers)
    93  		for {
    94  			if mask == 0 {
    95  				break
    96  			}
    97  			reg := uint8(bits.TrailingZeros64(mask))
    98  			mask &^= 1 << reg
    99  
   100  			registers[reg] = append(registers[reg], live.slot)
   101  		}
   102  	}
   103  	state.slots, state.registers = slots, registers
   104  }
   105  
   106  func (s *debugState) LocString(loc VarLoc) string {
   107  	if loc.absent() {
   108  		return "<nil>"
   109  	}
   110  
   111  	var storage []string
   112  	if loc.onStack() {
   113  		storage = append(storage, "stack")
   114  	}
   115  
   116  	mask := uint64(loc.Registers)
   117  	for {
   118  		if mask == 0 {
   119  			break
   120  		}
   121  		reg := uint8(bits.TrailingZeros64(mask))
   122  		mask &^= 1 << reg
   123  
   124  		storage = append(storage, s.registers[reg].String())
   125  	}
   126  	return strings.Join(storage, ",")
   127  }
   128  
   129  // A VarLoc describes the storage for part of a user variable.
   130  type VarLoc struct {
   131  	// The registers this variable is available in. There can be more than
   132  	// one in various situations, e.g. it's being moved between registers.
   133  	Registers RegisterSet
   134  
   135  	StackOffset
   136  }
   137  
   138  func (loc VarLoc) absent() bool {
   139  	return loc.Registers == 0 && !loc.onStack()
   140  }
   141  
   142  var BlockStart = &Value{
   143  	ID:  -10000,
   144  	Op:  OpInvalid,
   145  	Aux: "BlockStart",
   146  }
   147  
   148  var BlockEnd = &Value{
   149  	ID:  -20000,
   150  	Op:  OpInvalid,
   151  	Aux: "BlockEnd",
   152  }
   153  
   154  // RegisterSet is a bitmap of registers, indexed by Register.num.
   155  type RegisterSet uint64
   156  
   157  // logf prints debug-specific logging to stdout (always stdout) if the current
   158  // function is tagged by GOSSAFUNC (for ssa output directed either to stdout or html).
   159  func (s *debugState) logf(msg string, args ...interface{}) {
   160  	if s.f.PrintOrHtmlSSA {
   161  		fmt.Printf(msg, args...)
   162  	}
   163  }
   164  
   165  type debugState struct {
   166  	// See FuncDebug.
   167  	slots    []LocalSlot
   168  	vars     []GCNode
   169  	varSlots [][]SlotID
   170  	lists    [][]byte
   171  
   172  	// The user variable that each slot rolls up to, indexed by SlotID.
   173  	slotVars []VarID
   174  
   175  	f              *Func
   176  	loggingEnabled bool
   177  	registers      []Register
   178  	stackOffset    func(LocalSlot) int32
   179  	ctxt           *obj.Link
   180  
   181  	// The names (slots) associated with each value, indexed by Value ID.
   182  	valueNames [][]SlotID
   183  
   184  	// The current state of whatever analysis is running.
   185  	currentState stateAtPC
   186  	liveCount    []int
   187  	changedVars  *sparseSet
   188  
   189  	// The pending location list entry for each user variable, indexed by VarID.
   190  	pendingEntries []pendingEntry
   191  
   192  	varParts           map[GCNode][]SlotID
   193  	blockDebug         []BlockDebug
   194  	pendingSlotLocs    []VarLoc
   195  	liveSlots          []liveSlot
   196  	liveSlotSliceBegin int
   197  	partsByVarOffset   sort.Interface
   198  }
   199  
   200  func (state *debugState) initializeCache(f *Func, numVars, numSlots int) {
   201  	// One blockDebug per block. Initialized in allocBlock.
   202  	if cap(state.blockDebug) < f.NumBlocks() {
   203  		state.blockDebug = make([]BlockDebug, f.NumBlocks())
   204  	} else {
   205  		// This local variable, and the ones like it below, enable compiler
   206  		// optimizations. Don't inline them.
   207  		b := state.blockDebug[:f.NumBlocks()]
   208  		for i := range b {
   209  			b[i] = BlockDebug{}
   210  		}
   211  	}
   212  
   213  	// A list of slots per Value. Reuse the previous child slices.
   214  	if cap(state.valueNames) < f.NumValues() {
   215  		old := state.valueNames
   216  		state.valueNames = make([][]SlotID, f.NumValues())
   217  		copy(state.valueNames, old)
   218  	}
   219  	vn := state.valueNames[:f.NumValues()]
   220  	for i := range vn {
   221  		vn[i] = vn[i][:0]
   222  	}
   223  
   224  	// Slot and register contents for currentState. Cleared by reset().
   225  	if cap(state.currentState.slots) < numSlots {
   226  		state.currentState.slots = make([]VarLoc, numSlots)
   227  	} else {
   228  		state.currentState.slots = state.currentState.slots[:numSlots]
   229  	}
   230  	if cap(state.currentState.registers) < len(state.registers) {
   231  		state.currentState.registers = make([][]SlotID, len(state.registers))
   232  	} else {
   233  		state.currentState.registers = state.currentState.registers[:len(state.registers)]
   234  	}
   235  
   236  	// Used many times by mergePredecessors.
   237  	if cap(state.liveCount) < numSlots {
   238  		state.liveCount = make([]int, numSlots)
   239  	} else {
   240  		state.liveCount = state.liveCount[:numSlots]
   241  	}
   242  
   243  	// A relatively small slice, but used many times as the return from processValue.
   244  	state.changedVars = newSparseSet(numVars)
   245  
   246  	// A pending entry per user variable, with space to track each of its pieces.
   247  	numPieces := 0
   248  	for i := range state.varSlots {
   249  		numPieces += len(state.varSlots[i])
   250  	}
   251  	if cap(state.pendingSlotLocs) < numPieces {
   252  		state.pendingSlotLocs = make([]VarLoc, numPieces)
   253  	} else {
   254  		psl := state.pendingSlotLocs[:numPieces]
   255  		for i := range psl {
   256  			psl[i] = VarLoc{}
   257  		}
   258  	}
   259  	if cap(state.pendingEntries) < numVars {
   260  		state.pendingEntries = make([]pendingEntry, numVars)
   261  	}
   262  	pe := state.pendingEntries[:numVars]
   263  	freePieceIdx := 0
   264  	for varID, slots := range state.varSlots {
   265  		pe[varID] = pendingEntry{
   266  			pieces: state.pendingSlotLocs[freePieceIdx : freePieceIdx+len(slots)],
   267  		}
   268  		freePieceIdx += len(slots)
   269  	}
   270  	state.pendingEntries = pe
   271  
   272  	if cap(state.lists) < numVars {
   273  		state.lists = make([][]byte, numVars)
   274  	} else {
   275  		state.lists = state.lists[:numVars]
   276  		for i := range state.lists {
   277  			state.lists[i] = nil
   278  		}
   279  	}
   280  
   281  	state.liveSlots = state.liveSlots[:0]
   282  	state.liveSlotSliceBegin = 0
   283  }
   284  
   285  func (state *debugState) allocBlock(b *Block) *BlockDebug {
   286  	return &state.blockDebug[b.ID]
   287  }
   288  
   289  func (state *debugState) appendLiveSlot(ls liveSlot) {
   290  	state.liveSlots = append(state.liveSlots, ls)
   291  }
   292  
   293  func (state *debugState) getLiveSlotSlice() []liveSlot {
   294  	s := state.liveSlots[state.liveSlotSliceBegin:]
   295  	state.liveSlotSliceBegin = len(state.liveSlots)
   296  	return s
   297  }
   298  
   299  func (s *debugState) blockEndStateString(b *BlockDebug) string {
   300  	endState := stateAtPC{slots: make([]VarLoc, len(s.slots)), registers: make([][]SlotID, len(s.registers))}
   301  	endState.reset(b.endState)
   302  	return s.stateString(endState)
   303  }
   304  
   305  func (s *debugState) stateString(state stateAtPC) string {
   306  	var strs []string
   307  	for slotID, loc := range state.slots {
   308  		if !loc.absent() {
   309  			strs = append(strs, fmt.Sprintf("\t%v = %v\n", s.slots[slotID], s.LocString(loc)))
   310  		}
   311  	}
   312  
   313  	strs = append(strs, "\n")
   314  	for reg, slots := range state.registers {
   315  		if len(slots) != 0 {
   316  			var slotStrs []string
   317  			for _, slot := range slots {
   318  				slotStrs = append(slotStrs, s.slots[slot].String())
   319  			}
   320  			strs = append(strs, fmt.Sprintf("\t%v = %v\n", &s.registers[reg], slotStrs))
   321  		}
   322  	}
   323  
   324  	if len(strs) == 1 {
   325  		return "(no vars)\n"
   326  	}
   327  	return strings.Join(strs, "")
   328  }
   329  
   330  // BuildFuncDebug returns debug information for f.
   331  // f must be fully processed, so that each Value is where it will be when
   332  // machine code is emitted.
   333  func BuildFuncDebug(ctxt *obj.Link, f *Func, loggingEnabled bool, stackOffset func(LocalSlot) int32) *FuncDebug {
   334  	if f.RegAlloc == nil {
   335  		f.Fatalf("BuildFuncDebug on func %v that has not been fully processed", f)
   336  	}
   337  	state := &f.Cache.debugState
   338  	state.loggingEnabled = loggingEnabled
   339  	state.f = f
   340  	state.registers = f.Config.registers
   341  	state.stackOffset = stackOffset
   342  	state.ctxt = ctxt
   343  
   344  	if state.loggingEnabled {
   345  		state.logf("Generating location lists for function %q\n", f.Name)
   346  	}
   347  
   348  	if state.varParts == nil {
   349  		state.varParts = make(map[GCNode][]SlotID)
   350  	} else {
   351  		for n := range state.varParts {
   352  			delete(state.varParts, n)
   353  		}
   354  	}
   355  
   356  	// Recompose any decomposed variables, and establish the canonical
   357  	// IDs for each var and slot by filling out state.vars and state.slots.
   358  
   359  	state.slots = state.slots[:0]
   360  	state.vars = state.vars[:0]
   361  	for i, slot := range f.Names {
   362  		state.slots = append(state.slots, slot)
   363  		if slot.N.IsSynthetic() {
   364  			continue
   365  		}
   366  
   367  		topSlot := &slot
   368  		for topSlot.SplitOf != nil {
   369  			topSlot = topSlot.SplitOf
   370  		}
   371  		if _, ok := state.varParts[topSlot.N]; !ok {
   372  			state.vars = append(state.vars, topSlot.N)
   373  		}
   374  		state.varParts[topSlot.N] = append(state.varParts[topSlot.N], SlotID(i))
   375  	}
   376  
   377  	// Recreate the LocalSlot for each stack-only variable.
   378  	// This would probably be better as an output from stackframe.
   379  	for _, b := range f.Blocks {
   380  		for _, v := range b.Values {
   381  			if v.Op == OpVarDef || v.Op == OpVarKill {
   382  				n := v.Aux.(GCNode)
   383  				if n.IsSynthetic() {
   384  					continue
   385  				}
   386  
   387  				if _, ok := state.varParts[n]; !ok {
   388  					slot := LocalSlot{N: n, Type: v.Type, Off: 0}
   389  					state.slots = append(state.slots, slot)
   390  					state.varParts[n] = []SlotID{SlotID(len(state.slots) - 1)}
   391  					state.vars = append(state.vars, n)
   392  				}
   393  			}
   394  		}
   395  	}
   396  
   397  	// Fill in the var<->slot mappings.
   398  	if cap(state.varSlots) < len(state.vars) {
   399  		state.varSlots = make([][]SlotID, len(state.vars))
   400  	} else {
   401  		state.varSlots = state.varSlots[:len(state.vars)]
   402  		for i := range state.varSlots {
   403  			state.varSlots[i] = state.varSlots[i][:0]
   404  		}
   405  	}
   406  	if cap(state.slotVars) < len(state.slots) {
   407  		state.slotVars = make([]VarID, len(state.slots))
   408  	} else {
   409  		state.slotVars = state.slotVars[:len(state.slots)]
   410  	}
   411  
   412  	if state.partsByVarOffset == nil {
   413  		state.partsByVarOffset = &partsByVarOffset{}
   414  	}
   415  	for varID, n := range state.vars {
   416  		parts := state.varParts[n]
   417  		state.varSlots[varID] = parts
   418  		for _, slotID := range parts {
   419  			state.slotVars[slotID] = VarID(varID)
   420  		}
   421  		*state.partsByVarOffset.(*partsByVarOffset) = partsByVarOffset{parts, state.slots}
   422  		sort.Sort(state.partsByVarOffset)
   423  	}
   424  
   425  	state.initializeCache(f, len(state.varParts), len(state.slots))
   426  
   427  	for i, slot := range f.Names {
   428  		if slot.N.IsSynthetic() {
   429  			continue
   430  		}
   431  		for _, value := range f.NamedValues[slot] {
   432  			state.valueNames[value.ID] = append(state.valueNames[value.ID], SlotID(i))
   433  		}
   434  	}
   435  
   436  	blockLocs := state.liveness()
   437  	state.buildLocationLists(blockLocs)
   438  
   439  	return &FuncDebug{
   440  		Slots:         state.slots,
   441  		VarSlots:      state.varSlots,
   442  		Vars:          state.vars,
   443  		LocationLists: state.lists,
   444  	}
   445  }
   446  
   447  // liveness walks the function in control flow order, calculating the start
   448  // and end state of each block.
   449  func (state *debugState) liveness() []*BlockDebug {
   450  	blockLocs := make([]*BlockDebug, state.f.NumBlocks())
   451  
   452  	// Reverse postorder: visit a block after as many as possible of its
   453  	// predecessors have been visited.
   454  	po := state.f.Postorder()
   455  	for i := len(po) - 1; i >= 0; i-- {
   456  		b := po[i]
   457  
   458  		// Build the starting state for the block from the final
   459  		// state of its predecessors.
   460  		startState, startValid := state.mergePredecessors(b, blockLocs, nil)
   461  		changed := false
   462  		if state.loggingEnabled {
   463  			state.logf("Processing %v, initial state:\n%v", b, state.stateString(state.currentState))
   464  		}
   465  
   466  		// Update locs/registers with the effects of each Value.
   467  		for _, v := range b.Values {
   468  			slots := state.valueNames[v.ID]
   469  
   470  			// Loads and stores inherit the names of their sources.
   471  			var source *Value
   472  			switch v.Op {
   473  			case OpStoreReg:
   474  				source = v.Args[0]
   475  			case OpLoadReg:
   476  				switch a := v.Args[0]; a.Op {
   477  				case OpArg, OpPhi:
   478  					source = a
   479  				case OpStoreReg:
   480  					source = a.Args[0]
   481  				default:
   482  					if state.loggingEnabled {
   483  						state.logf("at %v: load with unexpected source op: %v (%v)\n", v, a.Op, a)
   484  					}
   485  				}
   486  			}
   487  			// Update valueNames with the source so that later steps
   488  			// don't need special handling.
   489  			if source != nil {
   490  				slots = append(slots, state.valueNames[source.ID]...)
   491  				state.valueNames[v.ID] = slots
   492  			}
   493  
   494  			reg, _ := state.f.getHome(v.ID).(*Register)
   495  			c := state.processValue(v, slots, reg)
   496  			changed = changed || c
   497  		}
   498  
   499  		if state.loggingEnabled {
   500  			state.f.Logf("Block %v done, locs:\n%v", b, state.stateString(state.currentState))
   501  		}
   502  
   503  		locs := state.allocBlock(b)
   504  		locs.relevant = changed
   505  		if !changed && startValid {
   506  			locs.endState = startState
   507  		} else {
   508  			for slotID, slotLoc := range state.currentState.slots {
   509  				if slotLoc.absent() {
   510  					continue
   511  				}
   512  				state.appendLiveSlot(liveSlot{slot: SlotID(slotID), Registers: slotLoc.Registers, StackOffset: slotLoc.StackOffset})
   513  			}
   514  			locs.endState = state.getLiveSlotSlice()
   515  		}
   516  		blockLocs[b.ID] = locs
   517  	}
   518  	return blockLocs
   519  }
   520  
   521  // mergePredecessors takes the end state of each of b's predecessors and
   522  // intersects them to form the starting state for b. It puts that state in
   523  // blockLocs, and fills state.currentState with it. If convenient, it returns
   524  // a reused []liveSlot, true that represents the starting state.
   525  // If previousBlock is non-nil, it registers changes vs. that block's end
   526  // state in state.changedVars. Note that previousBlock will often not be a
   527  // predecessor.
   528  func (state *debugState) mergePredecessors(b *Block, blockLocs []*BlockDebug, previousBlock *Block) ([]liveSlot, bool) {
   529  	// Filter out back branches.
   530  	var predsBuf [10]*Block
   531  	preds := predsBuf[:0]
   532  	for _, pred := range b.Preds {
   533  		if blockLocs[pred.b.ID] != nil {
   534  			preds = append(preds, pred.b)
   535  		}
   536  	}
   537  
   538  	if state.loggingEnabled {
   539  		// The logf below would cause preds to be heap-allocated if
   540  		// it were passed directly.
   541  		preds2 := make([]*Block, len(preds))
   542  		copy(preds2, preds)
   543  		state.logf("Merging %v into %v\n", preds2, b)
   544  	}
   545  
   546  	// TODO all the calls to this are overkill; only need to do this for slots that are not present in the merge.
   547  	markChangedVars := func(slots []liveSlot) {
   548  		for _, live := range slots {
   549  			state.changedVars.add(ID(state.slotVars[live.slot]))
   550  		}
   551  	}
   552  
   553  	if len(preds) == 0 {
   554  		if previousBlock != nil {
   555  			// Mark everything in previous block as changed because it is not a predecessor.
   556  			markChangedVars(blockLocs[previousBlock.ID].endState)
   557  		}
   558  		state.currentState.reset(nil)
   559  		return nil, true
   560  	}
   561  
   562  	p0 := blockLocs[preds[0].ID].endState
   563  	if len(preds) == 1 {
   564  		if previousBlock != nil && preds[0].ID != previousBlock.ID {
   565  			// Mark everything in previous block as changed because it is not a predecessor.
   566  			markChangedVars(blockLocs[previousBlock.ID].endState)
   567  		}
   568  		state.currentState.reset(p0)
   569  		return p0, true
   570  	}
   571  
   572  	baseID := preds[0].ID
   573  	baseState := p0
   574  
   575  	// If previous block is not a predecessor, its location information changes at boundary with this block.
   576  	previousBlockIsNotPredecessor := previousBlock != nil // If it's nil, no info to change.
   577  
   578  	if previousBlock != nil {
   579  		// Try to use previousBlock as the base state
   580  		// if possible.
   581  		for _, pred := range preds[1:] {
   582  			if pred.ID == previousBlock.ID {
   583  				baseID = pred.ID
   584  				baseState = blockLocs[pred.ID].endState
   585  				previousBlockIsNotPredecessor = false
   586  				break
   587  			}
   588  		}
   589  	}
   590  
   591  	if state.loggingEnabled {
   592  		state.logf("Starting %v with state from b%v:\n%v", b, baseID, state.blockEndStateString(blockLocs[baseID]))
   593  	}
   594  
   595  	slotLocs := state.currentState.slots
   596  	for _, predSlot := range baseState {
   597  		slotLocs[predSlot.slot] = VarLoc{predSlot.Registers, predSlot.StackOffset}
   598  		state.liveCount[predSlot.slot] = 1
   599  	}
   600  	for _, pred := range preds {
   601  		if pred.ID == baseID {
   602  			continue
   603  		}
   604  		if state.loggingEnabled {
   605  			state.logf("Merging in state from %v:\n%v", pred, state.blockEndStateString(blockLocs[pred.ID]))
   606  		}
   607  		for _, predSlot := range blockLocs[pred.ID].endState {
   608  			state.liveCount[predSlot.slot]++
   609  			liveLoc := slotLocs[predSlot.slot]
   610  			if !liveLoc.onStack() || !predSlot.onStack() || liveLoc.StackOffset != predSlot.StackOffset {
   611  				liveLoc.StackOffset = 0
   612  			}
   613  			liveLoc.Registers &= predSlot.Registers
   614  			slotLocs[predSlot.slot] = liveLoc
   615  		}
   616  	}
   617  
   618  	// Check if the final state is the same as the first predecessor's
   619  	// final state, and reuse it if so. In principle it could match any,
   620  	// but it's probably not worth checking more than the first.
   621  	unchanged := true
   622  	for _, predSlot := range baseState {
   623  		if state.liveCount[predSlot.slot] != len(preds) ||
   624  			slotLocs[predSlot.slot].Registers != predSlot.Registers ||
   625  			slotLocs[predSlot.slot].StackOffset != predSlot.StackOffset {
   626  			unchanged = false
   627  			break
   628  		}
   629  	}
   630  	if unchanged {
   631  		if state.loggingEnabled {
   632  			state.logf("After merge, %v matches b%v exactly.\n", b, baseID)
   633  		}
   634  		if previousBlockIsNotPredecessor {
   635  			// Mark everything in previous block as changed because it is not a predecessor.
   636  			markChangedVars(blockLocs[previousBlock.ID].endState)
   637  		}
   638  		state.currentState.reset(baseState)
   639  		return baseState, true
   640  	}
   641  
   642  	for reg := range state.currentState.registers {
   643  		state.currentState.registers[reg] = state.currentState.registers[reg][:0]
   644  	}
   645  
   646  	// A slot is live if it was seen in all predecessors, and they all had
   647  	// some storage in common.
   648  	for _, predSlot := range baseState {
   649  		slotLoc := slotLocs[predSlot.slot]
   650  
   651  		if state.liveCount[predSlot.slot] != len(preds) {
   652  			// Seen in only some predecessors. Clear it out.
   653  			slotLocs[predSlot.slot] = VarLoc{}
   654  			continue
   655  		}
   656  
   657  		// Present in all predecessors.
   658  		mask := uint64(slotLoc.Registers)
   659  		for {
   660  			if mask == 0 {
   661  				break
   662  			}
   663  			reg := uint8(bits.TrailingZeros64(mask))
   664  			mask &^= 1 << reg
   665  			state.currentState.registers[reg] = append(state.currentState.registers[reg], predSlot.slot)
   666  		}
   667  	}
   668  
   669  	if previousBlockIsNotPredecessor {
   670  		// Mark everything in previous block as changed because it is not a predecessor.
   671  		markChangedVars(blockLocs[previousBlock.ID].endState)
   672  
   673  	}
   674  	return nil, false
   675  }
   676  
   677  // processValue updates locs and state.registerContents to reflect v, a value with
   678  // the names in vSlots and homed in vReg.  "v" becomes visible after execution of
   679  // the instructions evaluating it. It returns which VarIDs were modified by the
   680  // Value's execution.
   681  func (state *debugState) processValue(v *Value, vSlots []SlotID, vReg *Register) bool {
   682  	locs := state.currentState
   683  	changed := false
   684  	setSlot := func(slot SlotID, loc VarLoc) {
   685  		changed = true
   686  		state.changedVars.add(ID(state.slotVars[slot]))
   687  		state.currentState.slots[slot] = loc
   688  	}
   689  
   690  	// Handle any register clobbering. Call operations, for example,
   691  	// clobber all registers even though they don't explicitly write to
   692  	// them.
   693  	clobbers := uint64(opcodeTable[v.Op].reg.clobbers)
   694  	for {
   695  		if clobbers == 0 {
   696  			break
   697  		}
   698  		reg := uint8(bits.TrailingZeros64(clobbers))
   699  		clobbers &^= 1 << reg
   700  
   701  		for _, slot := range locs.registers[reg] {
   702  			if state.loggingEnabled {
   703  				state.logf("at %v: %v clobbered out of %v\n", v, state.slots[slot], &state.registers[reg])
   704  			}
   705  
   706  			last := locs.slots[slot]
   707  			if last.absent() {
   708  				state.f.Fatalf("at %v: slot %v in register %v with no location entry", v, state.slots[slot], &state.registers[reg])
   709  				continue
   710  			}
   711  			regs := last.Registers &^ (1 << reg)
   712  			setSlot(slot, VarLoc{regs, last.StackOffset})
   713  		}
   714  
   715  		locs.registers[reg] = locs.registers[reg][:0]
   716  	}
   717  
   718  	switch {
   719  	case v.Op == OpVarDef, v.Op == OpVarKill:
   720  		n := v.Aux.(GCNode)
   721  		if n.IsSynthetic() {
   722  			break
   723  		}
   724  
   725  		slotID := state.varParts[n][0]
   726  		var stackOffset StackOffset
   727  		if v.Op == OpVarDef {
   728  			stackOffset = StackOffset(state.stackOffset(state.slots[slotID])<<1 | 1)
   729  		}
   730  		setSlot(slotID, VarLoc{0, stackOffset})
   731  		if state.loggingEnabled {
   732  			if v.Op == OpVarDef {
   733  				state.logf("at %v: stack-only var %v now live\n", v, state.slots[slotID])
   734  			} else {
   735  				state.logf("at %v: stack-only var %v now dead\n", v, state.slots[slotID])
   736  			}
   737  		}
   738  
   739  	case v.Op == OpArg:
   740  		home := state.f.getHome(v.ID).(LocalSlot)
   741  		stackOffset := state.stackOffset(home)<<1 | 1
   742  		for _, slot := range vSlots {
   743  			if state.loggingEnabled {
   744  				state.logf("at %v: arg %v now on stack in location %v\n", v, state.slots[slot], home)
   745  				if last := locs.slots[slot]; !last.absent() {
   746  					state.logf("at %v: unexpected arg op on already-live slot %v\n", v, state.slots[slot])
   747  				}
   748  			}
   749  
   750  			setSlot(slot, VarLoc{0, StackOffset(stackOffset)})
   751  		}
   752  
   753  	case v.Op == OpStoreReg:
   754  		home := state.f.getHome(v.ID).(LocalSlot)
   755  		stackOffset := state.stackOffset(home)<<1 | 1
   756  		for _, slot := range vSlots {
   757  			last := locs.slots[slot]
   758  			if last.absent() {
   759  				if state.loggingEnabled {
   760  					state.logf("at %v: unexpected spill of unnamed register %s\n", v, vReg)
   761  				}
   762  				break
   763  			}
   764  
   765  			setSlot(slot, VarLoc{last.Registers, StackOffset(stackOffset)})
   766  			if state.loggingEnabled {
   767  				state.logf("at %v: %v spilled to stack location %v\n", v, state.slots[slot], home)
   768  			}
   769  		}
   770  
   771  	case vReg != nil:
   772  		if state.loggingEnabled {
   773  			newSlots := make([]bool, len(state.slots))
   774  			for _, slot := range vSlots {
   775  				newSlots[slot] = true
   776  			}
   777  
   778  			for _, slot := range locs.registers[vReg.num] {
   779  				if !newSlots[slot] {
   780  					state.logf("at %v: overwrote %v in register %v\n", v, state.slots[slot], vReg)
   781  				}
   782  			}
   783  		}
   784  
   785  		for _, slot := range locs.registers[vReg.num] {
   786  			last := locs.slots[slot]
   787  			setSlot(slot, VarLoc{last.Registers &^ (1 << uint8(vReg.num)), last.StackOffset})
   788  		}
   789  		locs.registers[vReg.num] = locs.registers[vReg.num][:0]
   790  		locs.registers[vReg.num] = append(locs.registers[vReg.num], vSlots...)
   791  		for _, slot := range vSlots {
   792  			if state.loggingEnabled {
   793  				state.logf("at %v: %v now in %s\n", v, state.slots[slot], vReg)
   794  			}
   795  
   796  			last := locs.slots[slot]
   797  			setSlot(slot, VarLoc{1<<uint8(vReg.num) | last.Registers, last.StackOffset})
   798  		}
   799  	}
   800  	return changed
   801  }
   802  
   803  // varOffset returns the offset of slot within the user variable it was
   804  // decomposed from. This has nothing to do with its stack offset.
   805  func varOffset(slot LocalSlot) int64 {
   806  	offset := slot.Off
   807  	s := &slot
   808  	for ; s.SplitOf != nil; s = s.SplitOf {
   809  		offset += s.SplitOffset
   810  	}
   811  	return offset
   812  }
   813  
   814  type partsByVarOffset struct {
   815  	slotIDs []SlotID
   816  	slots   []LocalSlot
   817  }
   818  
   819  func (a partsByVarOffset) Len() int { return len(a.slotIDs) }
   820  func (a partsByVarOffset) Less(i, j int) bool {
   821  	return varOffset(a.slots[a.slotIDs[i]]) < varOffset(a.slots[a.slotIDs[j]])
   822  }
   823  func (a partsByVarOffset) Swap(i, j int) { a.slotIDs[i], a.slotIDs[j] = a.slotIDs[j], a.slotIDs[i] }
   824  
   825  // A pendingEntry represents the beginning of a location list entry, missing
   826  // only its end coordinate.
   827  type pendingEntry struct {
   828  	present                bool
   829  	startBlock, startValue ID
   830  	// The location of each piece of the variable, in the same order as the
   831  	// SlotIDs in varParts.
   832  	pieces []VarLoc
   833  }
   834  
   835  func (e *pendingEntry) clear() {
   836  	e.present = false
   837  	e.startBlock = 0
   838  	e.startValue = 0
   839  	for i := range e.pieces {
   840  		e.pieces[i] = VarLoc{}
   841  	}
   842  }
   843  
   844  // canMerge reports whether the location description for new is the same as
   845  // pending.
   846  func canMerge(pending, new VarLoc) bool {
   847  	if pending.absent() && new.absent() {
   848  		return true
   849  	}
   850  	if pending.absent() || new.absent() {
   851  		return false
   852  	}
   853  	if pending.onStack() {
   854  		return pending.StackOffset == new.StackOffset
   855  	}
   856  	if pending.Registers != 0 && new.Registers != 0 {
   857  		return firstReg(pending.Registers) == firstReg(new.Registers)
   858  	}
   859  	return false
   860  }
   861  
   862  // firstReg returns the first register in set that is present.
   863  func firstReg(set RegisterSet) uint8 {
   864  	if set == 0 {
   865  		// This is wrong, but there seem to be some situations where we
   866  		// produce locations with no storage.
   867  		return 0
   868  	}
   869  	return uint8(bits.TrailingZeros64(uint64(set)))
   870  }
   871  
   872  // buildLocationLists builds location lists for all the user variables in
   873  // state.f, using the information about block state in blockLocs.
   874  // The returned location lists are not fully complete. They are in terms of
   875  // SSA values rather than PCs, and have no base address/end entries. They will
   876  // be finished by PutLocationList.
   877  func (state *debugState) buildLocationLists(blockLocs []*BlockDebug) {
   878  	// Run through the function in program text order, building up location
   879  	// lists as we go. The heavy lifting has mostly already been done.
   880  
   881  	var prevBlock *Block
   882  	for _, b := range state.f.Blocks {
   883  		state.mergePredecessors(b, blockLocs, prevBlock)
   884  
   885  		if !blockLocs[b.ID].relevant {
   886  			// Handle any differences among predecessor blocks and previous block (perhaps not a predecessor)
   887  			for _, varID := range state.changedVars.contents() {
   888  				state.updateVar(VarID(varID), b, BlockStart)
   889  			}
   890  			continue
   891  		}
   892  
   893  		zeroWidthPending := false
   894  		apcChangedSize := 0 // size of changedVars for leading Args, Phi, ClosurePtr
   895  		// expect to see values in pattern (apc)* (zerowidth|real)*
   896  		for _, v := range b.Values {
   897  			slots := state.valueNames[v.ID]
   898  			reg, _ := state.f.getHome(v.ID).(*Register)
   899  			changed := state.processValue(v, slots, reg) // changed == added to state.changedVars
   900  
   901  			if opcodeTable[v.Op].zeroWidth {
   902  				if changed {
   903  					if v.Op == OpArg || v.Op == OpPhi || v.Op.isLoweredGetClosurePtr() {
   904  						// These ranges begin at true beginning of block, not after first instruction
   905  						if zeroWidthPending {
   906  							b.Func.Fatalf("Unexpected op mixed with OpArg/OpPhi/OpLoweredGetClosurePtr at beginning of block %s in %s\n%s", b, b.Func.Name, b.Func)
   907  						}
   908  						apcChangedSize = len(state.changedVars.contents())
   909  						continue
   910  					}
   911  					// Other zero-width ops must wait on a "real" op.
   912  					zeroWidthPending = true
   913  				}
   914  				continue
   915  			}
   916  
   917  			if !changed && !zeroWidthPending {
   918  				continue
   919  			}
   920  			// Not zero-width; i.e., a "real" instruction.
   921  
   922  			zeroWidthPending = false
   923  			for i, varID := range state.changedVars.contents() {
   924  				if i < apcChangedSize { // buffered true start-of-block changes
   925  					state.updateVar(VarID(varID), v.Block, BlockStart)
   926  				} else {
   927  					state.updateVar(VarID(varID), v.Block, v)
   928  				}
   929  			}
   930  			state.changedVars.clear()
   931  			apcChangedSize = 0
   932  		}
   933  		for i, varID := range state.changedVars.contents() {
   934  			if i < apcChangedSize { // buffered true start-of-block changes
   935  				state.updateVar(VarID(varID), b, BlockStart)
   936  			} else {
   937  				state.updateVar(VarID(varID), b, BlockEnd)
   938  			}
   939  		}
   940  
   941  		prevBlock = b
   942  	}
   943  
   944  	if state.loggingEnabled {
   945  		state.logf("location lists:\n")
   946  	}
   947  
   948  	// Flush any leftover entries live at the end of the last block.
   949  	for varID := range state.lists {
   950  		state.writePendingEntry(VarID(varID), state.f.Blocks[len(state.f.Blocks)-1].ID, BlockEnd.ID)
   951  		list := state.lists[varID]
   952  		if state.loggingEnabled {
   953  			if len(list) == 0 {
   954  				state.logf("\t%v : empty list\n", state.vars[varID])
   955  			} else {
   956  				state.logf("\t%v : %q\n", state.vars[varID], hex.EncodeToString(state.lists[varID]))
   957  			}
   958  		}
   959  	}
   960  }
   961  
   962  // updateVar updates the pending location list entry for varID to
   963  // reflect the new locations in curLoc, beginning at v in block b.
   964  // v may be one of the special values indicating block start or end.
   965  func (state *debugState) updateVar(varID VarID, b *Block, v *Value) {
   966  	curLoc := state.currentState.slots
   967  	// Assemble the location list entry with whatever's live.
   968  	empty := true
   969  	for _, slotID := range state.varSlots[varID] {
   970  		if !curLoc[slotID].absent() {
   971  			empty = false
   972  			break
   973  		}
   974  	}
   975  	pending := &state.pendingEntries[varID]
   976  	if empty {
   977  		state.writePendingEntry(varID, b.ID, v.ID)
   978  		pending.clear()
   979  		return
   980  	}
   981  
   982  	// Extend the previous entry if possible.
   983  	if pending.present {
   984  		merge := true
   985  		for i, slotID := range state.varSlots[varID] {
   986  			if !canMerge(pending.pieces[i], curLoc[slotID]) {
   987  				merge = false
   988  				break
   989  			}
   990  		}
   991  		if merge {
   992  			return
   993  		}
   994  	}
   995  
   996  	state.writePendingEntry(varID, b.ID, v.ID)
   997  	pending.present = true
   998  	pending.startBlock = b.ID
   999  	pending.startValue = v.ID
  1000  	for i, slot := range state.varSlots[varID] {
  1001  		pending.pieces[i] = curLoc[slot]
  1002  	}
  1003  }
  1004  
  1005  // writePendingEntry writes out the pending entry for varID, if any,
  1006  // terminated at endBlock/Value.
  1007  func (state *debugState) writePendingEntry(varID VarID, endBlock, endValue ID) {
  1008  	pending := state.pendingEntries[varID]
  1009  	if !pending.present {
  1010  		return
  1011  	}
  1012  
  1013  	// Pack the start/end coordinates into the start/end addresses
  1014  	// of the entry, for decoding by PutLocationList.
  1015  	start, startOK := encodeValue(state.ctxt, pending.startBlock, pending.startValue)
  1016  	end, endOK := encodeValue(state.ctxt, endBlock, endValue)
  1017  	if !startOK || !endOK {
  1018  		// If someone writes a function that uses >65K values,
  1019  		// they get incomplete debug info on 32-bit platforms.
  1020  		return
  1021  	}
  1022  	if start == end {
  1023  		if state.loggingEnabled {
  1024  			// Printf not logf so not gated by GOSSAFUNC; this should fire very rarely.
  1025  			fmt.Printf("Skipping empty location list for %v in %s\n", state.vars[varID], state.f.Name)
  1026  		}
  1027  		return
  1028  	}
  1029  
  1030  	list := state.lists[varID]
  1031  	list = appendPtr(state.ctxt, list, start)
  1032  	list = appendPtr(state.ctxt, list, end)
  1033  	// Where to write the length of the location description once
  1034  	// we know how big it is.
  1035  	sizeIdx := len(list)
  1036  	list = list[:len(list)+2]
  1037  
  1038  	if state.loggingEnabled {
  1039  		var partStrs []string
  1040  		for i, slot := range state.varSlots[varID] {
  1041  			partStrs = append(partStrs, fmt.Sprintf("%v@%v", state.slots[slot], state.LocString(pending.pieces[i])))
  1042  		}
  1043  		state.logf("Add entry for %v: \tb%vv%v-b%vv%v = \t%v\n", state.vars[varID], pending.startBlock, pending.startValue, endBlock, endValue, strings.Join(partStrs, " "))
  1044  	}
  1045  
  1046  	for i, slotID := range state.varSlots[varID] {
  1047  		loc := pending.pieces[i]
  1048  		slot := state.slots[slotID]
  1049  
  1050  		if !loc.absent() {
  1051  			if loc.onStack() {
  1052  				if loc.stackOffsetValue() == 0 {
  1053  					list = append(list, dwarf.DW_OP_call_frame_cfa)
  1054  				} else {
  1055  					list = append(list, dwarf.DW_OP_fbreg)
  1056  					list = dwarf.AppendSleb128(list, int64(loc.stackOffsetValue()))
  1057  				}
  1058  			} else {
  1059  				regnum := state.ctxt.Arch.DWARFRegisters[state.registers[firstReg(loc.Registers)].ObjNum()]
  1060  				if regnum < 32 {
  1061  					list = append(list, dwarf.DW_OP_reg0+byte(regnum))
  1062  				} else {
  1063  					list = append(list, dwarf.DW_OP_regx)
  1064  					list = dwarf.AppendUleb128(list, uint64(regnum))
  1065  				}
  1066  			}
  1067  		}
  1068  
  1069  		if len(state.varSlots[varID]) > 1 {
  1070  			list = append(list, dwarf.DW_OP_piece)
  1071  			list = dwarf.AppendUleb128(list, uint64(slot.Type.Size()))
  1072  		}
  1073  	}
  1074  	state.ctxt.Arch.ByteOrder.PutUint16(list[sizeIdx:], uint16(len(list)-sizeIdx-2))
  1075  	state.lists[varID] = list
  1076  }
  1077  
  1078  // PutLocationList adds list (a location list in its intermediate representation) to listSym.
  1079  func (debugInfo *FuncDebug) PutLocationList(list []byte, ctxt *obj.Link, listSym, startPC *obj.LSym) {
  1080  	getPC := debugInfo.GetPC
  1081  
  1082  	if ctxt.UseBASEntries {
  1083  		listSym.WriteInt(ctxt, listSym.Size, ctxt.Arch.PtrSize, ^0)
  1084  		listSym.WriteAddr(ctxt, listSym.Size, ctxt.Arch.PtrSize, startPC, 0)
  1085  	}
  1086  
  1087  	// Re-read list, translating its address from block/value ID to PC.
  1088  	for i := 0; i < len(list); {
  1089  		begin := getPC(decodeValue(ctxt, readPtr(ctxt, list[i:])))
  1090  		end := getPC(decodeValue(ctxt, readPtr(ctxt, list[i+ctxt.Arch.PtrSize:])))
  1091  
  1092  		// Horrible hack. If a range contains only zero-width
  1093  		// instructions, e.g. an Arg, and it's at the beginning of the
  1094  		// function, this would be indistinguishable from an
  1095  		// end entry. Fudge it.
  1096  		if begin == 0 && end == 0 {
  1097  			end = 1
  1098  		}
  1099  
  1100  		if ctxt.UseBASEntries {
  1101  			listSym.WriteInt(ctxt, listSym.Size, ctxt.Arch.PtrSize, int64(begin))
  1102  			listSym.WriteInt(ctxt, listSym.Size, ctxt.Arch.PtrSize, int64(end))
  1103  		} else {
  1104  			listSym.WriteCURelativeAddr(ctxt, listSym.Size, startPC, int64(begin))
  1105  			listSym.WriteCURelativeAddr(ctxt, listSym.Size, startPC, int64(end))
  1106  		}
  1107  
  1108  		i += 2 * ctxt.Arch.PtrSize
  1109  		datalen := 2 + int(ctxt.Arch.ByteOrder.Uint16(list[i:]))
  1110  		listSym.WriteBytes(ctxt, listSym.Size, list[i:i+datalen]) // copy datalen and location encoding
  1111  		i += datalen
  1112  	}
  1113  
  1114  	// Location list contents, now with real PCs.
  1115  	// End entry.
  1116  	listSym.WriteInt(ctxt, listSym.Size, ctxt.Arch.PtrSize, 0)
  1117  	listSym.WriteInt(ctxt, listSym.Size, ctxt.Arch.PtrSize, 0)
  1118  }
  1119  
  1120  // Pack a value and block ID into an address-sized uint, returning ~0 if they
  1121  // don't fit.
  1122  func encodeValue(ctxt *obj.Link, b, v ID) (uint64, bool) {
  1123  	if ctxt.Arch.PtrSize == 8 {
  1124  		result := uint64(b)<<32 | uint64(uint32(v))
  1125  		//ctxt.Logf("b %#x (%d) v %#x (%d) -> %#x\n", b, b, v, v, result)
  1126  		return result, true
  1127  	}
  1128  	if ctxt.Arch.PtrSize != 4 {
  1129  		panic("unexpected pointer size")
  1130  	}
  1131  	if ID(int16(b)) != b || ID(int16(v)) != v {
  1132  		return 0, false
  1133  	}
  1134  	return uint64(b)<<16 | uint64(uint16(v)), true
  1135  }
  1136  
  1137  // Unpack a value and block ID encoded by encodeValue.
  1138  func decodeValue(ctxt *obj.Link, word uint64) (ID, ID) {
  1139  	if ctxt.Arch.PtrSize == 8 {
  1140  		b, v := ID(word>>32), ID(word)
  1141  		//ctxt.Logf("%#x -> b %#x (%d) v %#x (%d)\n", word, b, b, v, v)
  1142  		return b, v
  1143  	}
  1144  	if ctxt.Arch.PtrSize != 4 {
  1145  		panic("unexpected pointer size")
  1146  	}
  1147  	return ID(word >> 16), ID(int16(word))
  1148  }
  1149  
  1150  // Append a pointer-sized uint to buf.
  1151  func appendPtr(ctxt *obj.Link, buf []byte, word uint64) []byte {
  1152  	if cap(buf) < len(buf)+20 {
  1153  		b := make([]byte, len(buf), 20+cap(buf)*2)
  1154  		copy(b, buf)
  1155  		buf = b
  1156  	}
  1157  	writeAt := len(buf)
  1158  	buf = buf[0 : len(buf)+ctxt.Arch.PtrSize]
  1159  	writePtr(ctxt, buf[writeAt:], word)
  1160  	return buf
  1161  }
  1162  
  1163  // Write a pointer-sized uint to the beginning of buf.
  1164  func writePtr(ctxt *obj.Link, buf []byte, word uint64) {
  1165  	switch ctxt.Arch.PtrSize {
  1166  	case 4:
  1167  		ctxt.Arch.ByteOrder.PutUint32(buf, uint32(word))
  1168  	case 8:
  1169  		ctxt.Arch.ByteOrder.PutUint64(buf, word)
  1170  	default:
  1171  		panic("unexpected pointer size")
  1172  	}
  1173  
  1174  }
  1175  
  1176  // Read a pointer-sized uint from the beginning of buf.
  1177  func readPtr(ctxt *obj.Link, buf []byte) uint64 {
  1178  	switch ctxt.Arch.PtrSize {
  1179  	case 4:
  1180  		return uint64(ctxt.Arch.ByteOrder.Uint32(buf))
  1181  	case 8:
  1182  		return ctxt.Arch.ByteOrder.Uint64(buf)
  1183  	default:
  1184  		panic("unexpected pointer size")
  1185  	}
  1186  
  1187  }
  1188  

View as plain text