...
Run Format

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

View as plain text