debug.go

     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  	"fmt"
     9  	"strings"
    10  
    11  	"cmd/compile/internal/abt"
    12  	"cmd/compile/internal/ir"
    13  	"cmd/compile/internal/ssa/ssabase"
    14  	"cmd/compile/internal/ssa/ssaop"
    15  	"cmd/internal/dwarf"
    16  	"cmd/internal/obj"
    17  )
    18  
    19  type slotSet = abt.T[*liveSlot]
    20  
    21  type BlockDebug struct {
    22  	// State at the start and end of the block. These are initialized,
    23  	// and updated from new information that flows on back edges.
    24  	startState, endState slotSet
    25  	// Use these to avoid excess work in the merge. If none of the
    26  	// predecessors has changed since the last check, the old answer is
    27  	// still good.
    28  	lastCheckedTime, lastChangedTime int32
    29  	// Whether the block had any changes to user variables at all.
    30  	relevant bool
    31  	// false until the block has been processed at least once. This
    32  	// affects how the merge is done; the goal is to maximize sharing
    33  	// and avoid allocation.
    34  	everProcessed bool
    35  }
    36  
    37  var BlockEnd = &Value{
    38  	ID:  -20000,
    39  	Op:  ssaop.OpInvalid,
    40  	Aux: StringToAux("BlockEnd"),
    41  }
    42  
    43  var BlockStart = &Value{
    44  	ID:  -10000,
    45  	Op:  ssaop.OpInvalid,
    46  	Aux: StringToAux("BlockStart"),
    47  }
    48  
    49  type DebugState struct {
    50  	// See FuncDebug.
    51  	Slots    []LocalSlot
    52  	Vars     []*ir.Name
    53  	VarSlots [][]SlotID
    54  	Lists    [][]LocListEntry
    55  
    56  	// The user variable that each slot rolls up to, indexed by SlotID.
    57  	SlotVars []VarID
    58  
    59  	F             *Func
    60  	LoggingLevel  int
    61  	ConvergeCount int // testing; iterate over block debug state this many times
    62  	Registers     []ssabase.Register
    63  	StackOffset   func(LocalSlot) int32
    64  	Ctxt          *obj.Link
    65  
    66  	// The names (slots) associated with each value, indexed by Value ID.
    67  	ValueNames [][]SlotID
    68  
    69  	// The current state of whatever analysis is running.
    70  	currentState StateAtPC
    71  	changedVars  *SparseSet
    72  	changedSlots *SparseSet
    73  
    74  	// The pending location list entry for each user variable, indexed by VarID.
    75  	pendingEntries []pendingEntry
    76  
    77  	VarParts        map[*ir.Name][]SlotID
    78  	blockDebug      []BlockDebug
    79  	pendingSlotLocs []VarLoc
    80  }
    81  
    82  var FuncEnd = &Value{
    83  	ID:  -30000,
    84  	Op:  ssaop.OpInvalid,
    85  	Aux: StringToAux("FuncEnd"),
    86  }
    87  
    88  // IsVarWantedForDebug returns true if the debug info for the node should
    89  // be generated.
    90  // For example, internal variables for range-over-func loops have little
    91  // value to users, so we don't generate debug info for them.
    92  func IsVarWantedForDebug(n ir.Node) bool {
    93  	name := n.Sym().Name
    94  	if len(name) > 0 && name[0] == '&' {
    95  		name = name[1:]
    96  	}
    97  	if len(name) > 0 && name[0] == '#' {
    98  		// #yield is used by delve.
    99  		return strings.HasPrefix(name, "#yield")
   100  	}
   101  	return true
   102  }
   103  
   104  // LocListEntry represents a single entry in a location list.
   105  // StartBlock/StartValue and EndBlock/EndValue are SSA coordinates
   106  // that get resolved to PCs during final encoding.
   107  type LocListEntry struct {
   108  	StartBlock, StartValue ID
   109  	EndBlock, EndValue     ID
   110  	Expr                   []byte // DWARF location expression (DW_OP_*)
   111  }
   112  
   113  // RegisterSet is a bitmap of registers, indexed by Register.num.
   114  type RegisterSet = ssaop.RegMask
   115  
   116  type SlotID int32
   117  
   118  // StackOffset encodes whether a value is on the stack and if so, where.
   119  // It is a 31-bit integer followed by a presence flag at the low-order
   120  // bit.
   121  type StackOffset int32
   122  
   123  // StateAtPC is the current state of all variables at some point.
   124  type StateAtPC struct {
   125  	// The location of each known slot, indexed by SlotID.
   126  	slots []VarLoc
   127  	// The slots present in each register, indexed by register number.
   128  	registers [][]SlotID
   129  }
   130  
   131  type VarID int32
   132  
   133  // A VarLoc describes the storage for part of a user variable.
   134  type VarLoc struct {
   135  	// The registers this variable is available in. There can be more than
   136  	// one in various situations, e.g. it's being moved between registers.
   137  	Registers RegisterSet
   138  
   139  	StackOffset
   140  }
   141  
   142  // canMerge reports whether a new location description is a superset
   143  // of the (non-empty) pending location description, if so, the two
   144  // can be merged (i.e., pending is still a valid and useful location
   145  // description).
   146  func canMerge(pending, new VarLoc) bool {
   147  	if pending.absent() && new.absent() {
   148  		return true
   149  	}
   150  	if pending.absent() || new.absent() {
   151  		return false
   152  	}
   153  	// pending is not absent, therefore it has either a stack mapping,
   154  	// or registers, or both.
   155  	if pending.onStack() && pending.StackOffset != new.StackOffset {
   156  		// if pending has a stack offset, then new must also, and it
   157  		// must be the same (StackOffset encodes onStack).
   158  		return false
   159  	}
   160  	if pending.Registers.Intersect(new.Registers) != pending.Registers {
   161  		// There is at least one register in pending not mentioned in new.
   162  		return false
   163  	}
   164  	return true
   165  }
   166  
   167  // firstReg returns the first register in set that is present.
   168  func firstReg(set RegisterSet) uint8 {
   169  	if set.Empty() {
   170  		// This is wrong, but there seem to be some situations where we
   171  		// produce locations with no storage.
   172  		return 0
   173  	}
   174  	return uint8(set.PickReg())
   175  }
   176  
   177  // A liveSlot is a slot that's live in loc at entry/exit of a block.
   178  type liveSlot struct {
   179  	VarLoc
   180  }
   181  
   182  // A pendingEntry represents the beginning of a location list entry, missing
   183  // only its end coordinate.
   184  type pendingEntry struct {
   185  	present                bool
   186  	startBlock, startValue ID
   187  	// The location of each piece of the variable, in the same order as the
   188  	// SlotIDs in varParts.
   189  	pieces []VarLoc
   190  }
   191  
   192  func (ls *liveSlot) String() string {
   193  	return fmt.Sprintf("[%v].%d.%d", ls.Registers, ls.stackOffsetValue(), int32(ls.StackOffset)&1)
   194  }
   195  
   196  func (s StackOffset) onStack() bool {
   197  	return s != 0
   198  }
   199  
   200  func (s StackOffset) stackOffsetValue() int32 {
   201  	return int32(s) >> 1
   202  }
   203  
   204  // reset fills state with the live variables from live.
   205  func (state *StateAtPC) reset(live slotSet) {
   206  	slots, registers := state.slots, state.registers
   207  	clear(slots)
   208  	for i := range registers {
   209  		registers[i] = registers[i][:0]
   210  	}
   211  	for it := live.Iterator(); !it.Done(); {
   212  		k, live := it.Next()
   213  		slots[k] = live.VarLoc
   214  		if live.VarLoc.Registers.Empty() {
   215  			continue
   216  		}
   217  
   218  		mask := live.VarLoc.Registers
   219  		for !mask.Empty() {
   220  			reg := uint8(mask.PickReg())
   221  			mask = mask.RemoveReg(ssaop.Register(reg))
   222  			registers[reg] = append(registers[reg], SlotID(k))
   223  		}
   224  	}
   225  	state.slots, state.registers = slots, registers
   226  }
   227  
   228  func (s *DebugState) LocString(loc VarLoc) string {
   229  	if loc.absent() {
   230  		return "<nil>"
   231  	}
   232  
   233  	var storage []string
   234  	if loc.onStack() {
   235  		storage = append(storage, fmt.Sprintf("@%+d", loc.stackOffsetValue()))
   236  	}
   237  
   238  	mask := loc.Registers
   239  	for !mask.Empty() {
   240  		reg := uint8(mask.PickReg())
   241  		mask = mask.RemoveReg(ssaop.Register(reg))
   242  		storage = append(storage, s.Registers[reg].String())
   243  	}
   244  	return strings.Join(storage, ",")
   245  }
   246  
   247  func (loc VarLoc) absent() bool {
   248  	return loc.Registers.Empty() && !loc.onStack()
   249  }
   250  
   251  func (loc VarLoc) intersect(other VarLoc) VarLoc {
   252  	if !loc.onStack() || !other.onStack() || loc.StackOffset != other.StackOffset {
   253  		loc.StackOffset = 0
   254  	}
   255  	loc.Registers = loc.Registers.Intersect(other.Registers)
   256  	return loc
   257  }
   258  
   259  // Logf prints debug-specific logging to stdout (always stdout) if the
   260  // current function is tagged by GOSSAFUNC (for ssa output directed
   261  // either to stdout or html).
   262  func (s *DebugState) Logf(msg string, args ...any) {
   263  	if s.F.PrintOrHtmlSSA {
   264  		fmt.Printf(msg, args...)
   265  	}
   266  }
   267  
   268  func (state *DebugState) InitializeCache(f *Func, numVars, numSlots int) {
   269  	// One blockDebug per block. Initialized in allocBlock.
   270  	if cap(state.blockDebug) < f.NumBlocks() {
   271  		state.blockDebug = make([]BlockDebug, f.NumBlocks())
   272  	} else {
   273  		clear(state.blockDebug[:f.NumBlocks()])
   274  	}
   275  
   276  	// A list of slots per Value. Reuse the previous child slices.
   277  	if cap(state.ValueNames) < f.NumValues() {
   278  		old := state.ValueNames
   279  		state.ValueNames = make([][]SlotID, f.NumValues())
   280  		copy(state.ValueNames, old)
   281  	}
   282  	vn := state.ValueNames[:f.NumValues()]
   283  	for i := range vn {
   284  		vn[i] = vn[i][:0]
   285  	}
   286  
   287  	// Slot and register contents for currentState. Cleared by reset().
   288  	if cap(state.currentState.slots) < numSlots {
   289  		state.currentState.slots = make([]VarLoc, numSlots)
   290  	} else {
   291  		state.currentState.slots = state.currentState.slots[:numSlots]
   292  	}
   293  	if cap(state.currentState.registers) < len(state.Registers) {
   294  		state.currentState.registers = make([][]SlotID, len(state.Registers))
   295  	} else {
   296  		state.currentState.registers = state.currentState.registers[:len(state.Registers)]
   297  	}
   298  
   299  	// A relatively small slice, but used many times as the return from processValue.
   300  	state.changedVars = NewSparseSet(numVars)
   301  	state.changedSlots = NewSparseSet(numSlots)
   302  
   303  	// A pending entry per user variable, with space to track each of its pieces.
   304  	numPieces := 0
   305  	for i := range state.VarSlots {
   306  		numPieces += len(state.VarSlots[i])
   307  	}
   308  	if cap(state.pendingSlotLocs) < numPieces {
   309  		state.pendingSlotLocs = make([]VarLoc, numPieces)
   310  	} else {
   311  		clear(state.pendingSlotLocs[:numPieces])
   312  	}
   313  	if cap(state.pendingEntries) < numVars {
   314  		state.pendingEntries = make([]pendingEntry, numVars)
   315  	}
   316  	pe := state.pendingEntries[:numVars]
   317  	freePieceIdx := 0
   318  	for varID, slots := range state.VarSlots {
   319  		pe[varID] = pendingEntry{
   320  			pieces: state.pendingSlotLocs[freePieceIdx : freePieceIdx+len(slots)],
   321  		}
   322  		freePieceIdx += len(slots)
   323  	}
   324  	state.pendingEntries = pe
   325  
   326  	if cap(state.Lists) < numVars {
   327  		state.Lists = make([][]LocListEntry, numVars)
   328  	} else {
   329  		state.Lists = state.Lists[:numVars]
   330  		clear(state.Lists)
   331  	}
   332  }
   333  
   334  func (state *DebugState) allocBlock(b *Block) *BlockDebug {
   335  	return &state.blockDebug[b.ID]
   336  }
   337  
   338  func (s *DebugState) blockEndStateString(b *BlockDebug) string {
   339  	endState := StateAtPC{slots: make([]VarLoc, len(s.Slots)), registers: make([][]SlotID, len(s.Registers))}
   340  	endState.reset(b.endState)
   341  	return s.stateString(endState)
   342  }
   343  
   344  func (s *DebugState) stateString(state StateAtPC) string {
   345  	var strs []string
   346  	for slotID, loc := range state.slots {
   347  		if !loc.absent() {
   348  			strs = append(strs, fmt.Sprintf("\t%v = %v\n", s.Slots[slotID], s.LocString(loc)))
   349  		}
   350  	}
   351  
   352  	strs = append(strs, "\n")
   353  	for reg, slots := range state.registers {
   354  		if len(slots) != 0 {
   355  			var slotStrs []string
   356  			for _, slot := range slots {
   357  				slotStrs = append(slotStrs, s.Slots[slot].String())
   358  			}
   359  			strs = append(strs, fmt.Sprintf("\t%v = %v\n", &s.Registers[reg], slotStrs))
   360  		}
   361  	}
   362  
   363  	if len(strs) == 1 {
   364  		return "(no vars)\n"
   365  	}
   366  	return strings.Join(strs, "")
   367  }
   368  
   369  // Liveness walks the function in control flow order, calculating the start
   370  // and end state of each block.
   371  func (state *DebugState) Liveness() []*BlockDebug {
   372  	blockLocs := make([]*BlockDebug, state.F.NumBlocks())
   373  	counterTime := int32(1)
   374  
   375  	// Reverse postorder: visit a block after as many as possible of its
   376  	// predecessors have been visited.
   377  	po := state.F.Postorder()
   378  	converged := false
   379  
   380  	// The iteration rule is that by default, run until converged, but
   381  	// if a particular iteration count is specified, run that many
   382  	// iterations, no more, no less.  A count is specified as the
   383  	// thousands digit of the location lists debug flag,
   384  	// e.g. -d=locationlists=4000
   385  	keepGoing := func(k int) bool {
   386  		if state.ConvergeCount == 0 {
   387  			return !converged
   388  		}
   389  		return k < state.ConvergeCount
   390  	}
   391  	for k := 0; keepGoing(k); k++ {
   392  		if state.LoggingLevel > 0 {
   393  			state.Logf("Liveness pass %d\n", k)
   394  		}
   395  		converged = true
   396  		for i := len(po) - 1; i >= 0; i-- {
   397  			b := po[i]
   398  			locs := blockLocs[b.ID]
   399  			if locs == nil {
   400  				locs = state.allocBlock(b)
   401  				blockLocs[b.ID] = locs
   402  			}
   403  
   404  			// Build the starting state for the block from the final
   405  			// state of its predecessors.
   406  			startState, blockChanged := state.mergePredecessors(b, blockLocs, nil, false)
   407  			locs.lastCheckedTime = counterTime
   408  			counterTime++
   409  			if state.LoggingLevel > 1 {
   410  				state.Logf("Processing %v, block changed %v, initial state:\n%v", b, blockChanged, state.stateString(state.currentState))
   411  			}
   412  
   413  			if blockChanged {
   414  				// If the start did not change, then the old endState is good
   415  				converged = false
   416  				changed := false
   417  				state.changedSlots.Clear()
   418  
   419  				// Update locs/registers with the effects of each Value.
   420  				for _, v := range b.Values {
   421  					slots := state.ValueNames[v.ID]
   422  
   423  					// Loads and stores inherit the names of their sources.
   424  					var source *Value
   425  					switch v.Op {
   426  					case ssaop.OpStoreReg:
   427  						source = v.Args[0]
   428  					case ssaop.OpLoadReg:
   429  						switch a := v.Args[0]; a.Op {
   430  						case ssaop.OpArg, ssaop.OpPhi:
   431  							source = a
   432  						case ssaop.OpStoreReg:
   433  							source = a.Args[0]
   434  						default:
   435  							if state.LoggingLevel > 1 {
   436  								state.Logf("at %v: load with unexpected source op: %v (%v)\n", v, a.Op, a)
   437  							}
   438  						}
   439  					}
   440  					// Update valueNames with the source so that later steps
   441  					// don't need special handling.
   442  					if source != nil && k == 0 {
   443  						// limit to k == 0 otherwise there are duplicates.
   444  						slots = append(slots, state.ValueNames[source.ID]...)
   445  						state.ValueNames[v.ID] = slots
   446  					}
   447  
   448  					reg, _ := state.F.GetHome(v.ID).(*ssabase.Register)
   449  					c := state.processValue(v, slots, reg)
   450  					changed = changed || c
   451  				}
   452  
   453  				if state.LoggingLevel > 1 {
   454  					state.Logf("Block %v done, locs:\n%v", b, state.stateString(state.currentState))
   455  				}
   456  
   457  				locs.relevant = locs.relevant || changed
   458  				if !changed {
   459  					locs.endState = startState
   460  				} else {
   461  					for _, id := range state.changedSlots.Contents() {
   462  						slotID := SlotID(id)
   463  						slotLoc := state.currentState.slots[slotID]
   464  						if slotLoc.absent() {
   465  							startState.Delete(int32(slotID))
   466  							continue
   467  						}
   468  						old := startState.Find(int32(slotID)) // do NOT replace existing values
   469  						if old == nil || old.VarLoc != slotLoc {
   470  							startState.Insert(int32(slotID),
   471  								&liveSlot{VarLoc: slotLoc})
   472  						}
   473  					}
   474  					locs.endState = startState
   475  				}
   476  				locs.lastChangedTime = counterTime
   477  			}
   478  			counterTime++
   479  		}
   480  	}
   481  	return blockLocs
   482  }
   483  
   484  // mergePredecessors takes the end state of each of b's predecessors and
   485  // intersects them to form the starting state for b. It puts that state
   486  // in blockLocs[b.ID].startState, and fills state.currentState with it.
   487  // It returns the start state and whether this is changed from the
   488  // previously approximated value of startState for this block.  After
   489  // the first call, subsequent calls can only shrink startState.
   490  //
   491  // Passing forLocationLists=true enables additional side-effects that
   492  // are necessary for building location lists but superfluous while still
   493  // iterating to an answer.
   494  //
   495  // If previousBlock is non-nil, it registers changes vs. that block's
   496  // end state in state.changedVars. Note that previousBlock will often
   497  // not be a predecessor.
   498  //
   499  // Note that mergePredecessors behaves slightly differently between
   500  // first and subsequent calls for a block.  For the first call, the
   501  // starting state is approximated by taking the state from the
   502  // predecessor whose state is smallest, and removing any elements not
   503  // in all the other predecessors; this makes the smallest number of
   504  // changes and shares the most state.  On subsequent calls the old
   505  // value of startState is adjusted with new information; this is judged
   506  // to do the least amount of extra work.
   507  //
   508  // To improve performance, each block's state information is marked with
   509  // lastChanged and lastChecked "times" so unchanged predecessors can be
   510  // skipped on after-the-first iterations.  Doing this allows extra
   511  // iterations by the caller to be almost free.
   512  //
   513  // It is important to know that the set representation used for
   514  // startState, endState, and merges can share data for two sets where
   515  // one is a small delta from the other.  Doing this does require a
   516  // little care in how sets are updated, both in mergePredecessors, and
   517  // using its result.
   518  func (state *DebugState) mergePredecessors(b *Block, blockLocs []*BlockDebug, previousBlock *Block, forLocationLists bool) (slotSet, bool) {
   519  	// Filter out back branches.
   520  	var predsBuf [10]*Block
   521  
   522  	preds := predsBuf[:0]
   523  	locs := blockLocs[b.ID]
   524  
   525  	blockChanged := !locs.everProcessed // the first time it always changes.
   526  	updating := locs.everProcessed
   527  
   528  	// For the first merge, exclude predecessors that have not been seen yet.
   529  	// I.e., backedges.
   530  	for _, pred := range b.Preds {
   531  		if bl := blockLocs[pred.B.ID]; bl != nil && bl.everProcessed {
   532  			// crucially, a self-edge has bl != nil, but bl.everProcessed is false the first time.
   533  			preds = append(preds, pred.B)
   534  		}
   535  	}
   536  
   537  	locs.everProcessed = true
   538  
   539  	if state.LoggingLevel > 1 {
   540  		// The logf below would cause preds to be heap-allocated if
   541  		// it were passed directly.
   542  		preds2 := make([]*Block, len(preds))
   543  		copy(preds2, preds)
   544  		state.Logf("Merging %v into %v (changed=%d, checked=%d)\n", preds2, b, locs.lastChangedTime, locs.lastCheckedTime)
   545  	}
   546  
   547  	state.changedVars.Clear()
   548  
   549  	markChangedVars := func(slots, merged slotSet) {
   550  		if !forLocationLists {
   551  			return
   552  		}
   553  		// Fill changedVars with those that differ between the previous
   554  		// block (in the emit order, not necessarily a flow predecessor)
   555  		// and the start state for this block.
   556  		for it := slots.Iterator(); !it.Done(); {
   557  			k, v := it.Next()
   558  			m := merged.Find(k)
   559  			if m == nil || v.VarLoc != m.VarLoc {
   560  				state.changedVars.Add(ID(state.SlotVars[k]))
   561  			}
   562  		}
   563  	}
   564  
   565  	reset := func(ourStartState slotSet) {
   566  		if !(forLocationLists || blockChanged) {
   567  			// there is no change and this is not for location lists, do
   568  			// not bother to reset currentState because it will not be
   569  			// examined.
   570  			return
   571  		}
   572  		state.currentState.reset(ourStartState)
   573  	}
   574  
   575  	// Zero predecessors
   576  	if len(preds) == 0 {
   577  		if previousBlock != nil {
   578  			state.F.Fatalf("Function %v, block %s with no predecessors is not first block, has previous %s", state.F, b.String(), previousBlock.String())
   579  		}
   580  		// startState is empty
   581  		reset(slotSet{})
   582  		return slotSet{}, blockChanged
   583  	}
   584  
   585  	// One predecessor
   586  	l0 := blockLocs[preds[0].ID]
   587  	p0 := l0.endState
   588  	if len(preds) == 1 {
   589  		if previousBlock != nil && preds[0].ID != previousBlock.ID {
   590  			// Change from previous block is its endState minus the predecessor's endState
   591  			markChangedVars(blockLocs[previousBlock.ID].endState, p0)
   592  		}
   593  		locs.startState = p0
   594  		blockChanged = blockChanged || l0.lastChangedTime > locs.lastCheckedTime
   595  		reset(p0)
   596  		return p0, blockChanged
   597  	}
   598  
   599  	// More than one predecessor
   600  
   601  	if updating {
   602  		// After the first approximation, i.e., when updating, results
   603  		// can only get smaller, because initially backedge
   604  		// predecessors do not participate in the intersection.  This
   605  		// means that for the update, given the prior approximation of
   606  		// startState, there is no need to re-intersect with unchanged
   607  		// blocks.  Therefore remove unchanged blocks from the
   608  		// predecessor list.
   609  		for i := len(preds) - 1; i >= 0; i-- {
   610  			pred := preds[i]
   611  			if blockLocs[pred.ID].lastChangedTime > locs.lastCheckedTime {
   612  				continue // keep this predecessor
   613  			}
   614  			preds[i] = preds[len(preds)-1]
   615  			preds = preds[:len(preds)-1]
   616  			if state.LoggingLevel > 2 {
   617  				state.Logf("Pruned b%d, lastChanged was %d but b%d lastChecked is %d\n", pred.ID, blockLocs[pred.ID].lastChangedTime, b.ID, locs.lastCheckedTime)
   618  			}
   619  		}
   620  		// Check for an early out; this should always hit for the update
   621  		// if there are no cycles.
   622  		if len(preds) == 0 {
   623  			blockChanged = false
   624  
   625  			reset(locs.startState)
   626  			if state.LoggingLevel > 2 {
   627  				state.Logf("Early out, no predecessors changed since last check\n")
   628  			}
   629  			if previousBlock != nil {
   630  				markChangedVars(blockLocs[previousBlock.ID].endState, locs.startState)
   631  			}
   632  			return locs.startState, blockChanged
   633  		}
   634  	}
   635  
   636  	baseID := preds[0].ID
   637  	baseState := p0
   638  
   639  	// Choose the predecessor with the smallest endState for intersection work
   640  	for _, pred := range preds[1:] {
   641  		if blockLocs[pred.ID].endState.Size() < baseState.Size() {
   642  			baseState = blockLocs[pred.ID].endState
   643  			baseID = pred.ID
   644  		}
   645  	}
   646  
   647  	if state.LoggingLevel > 2 {
   648  		state.Logf("Starting %v with state from b%v:\n%v", b, baseID, state.blockEndStateString(blockLocs[baseID]))
   649  		for _, pred := range preds {
   650  			if pred.ID == baseID {
   651  				continue
   652  			}
   653  			state.Logf("Merging in state from %v:\n%v", pred, state.blockEndStateString(blockLocs[pred.ID]))
   654  		}
   655  	}
   656  
   657  	state.currentState.reset(slotSet{})
   658  	// The normal logic of "reset" is included in the intersection loop below.
   659  
   660  	slotLocs := state.currentState.slots
   661  
   662  	// If this is the first call, do updates on the "baseState"; if this
   663  	// is a subsequent call, tweak the startState instead. Note that
   664  	// these "set" values are values; there are no side effects to
   665  	// other values as these are modified.
   666  	newState := baseState
   667  	if updating {
   668  		newState = blockLocs[b.ID].startState
   669  	}
   670  
   671  	for it := newState.Iterator(); !it.Done(); {
   672  		k, thisSlot := it.Next()
   673  		x := thisSlot.VarLoc
   674  		x0 := x // initial value in newState
   675  
   676  		// Intersect this slot with the slot in all the predecessors
   677  		for _, other := range preds {
   678  			if !updating && other.ID == baseID {
   679  				continue
   680  			}
   681  			otherSlot := blockLocs[other.ID].endState.Find(k)
   682  			if otherSlot == nil {
   683  				x = VarLoc{}
   684  				break
   685  			}
   686  			y := otherSlot.VarLoc
   687  			x = x.intersect(y)
   688  			if x.absent() {
   689  				x = VarLoc{}
   690  				break
   691  			}
   692  		}
   693  
   694  		// Delete if necessary, but not otherwise (in order to maximize sharing).
   695  		if x.absent() {
   696  			if !x0.absent() {
   697  				blockChanged = true
   698  				newState.Delete(k)
   699  			}
   700  			slotLocs[k] = VarLoc{}
   701  			continue
   702  		}
   703  		if x != x0 {
   704  			blockChanged = true
   705  			newState.Insert(k, &liveSlot{VarLoc: x})
   706  		}
   707  
   708  		slotLocs[k] = x
   709  		mask := x.Registers
   710  		for !mask.Empty() {
   711  			reg := uint8(mask.PickReg())
   712  			mask = mask.RemoveReg(ssaop.Register(reg))
   713  			state.currentState.registers[reg] = append(state.currentState.registers[reg], SlotID(k))
   714  		}
   715  	}
   716  
   717  	if previousBlock != nil {
   718  		markChangedVars(blockLocs[previousBlock.ID].endState, newState)
   719  	}
   720  	locs.startState = newState
   721  	return newState, blockChanged
   722  }
   723  
   724  // processValue updates locs and state.registerContents to reflect v, a
   725  // value with the names in vSlots and homed in vReg.  "v" becomes
   726  // visible after execution of the instructions evaluating it. It
   727  // returns which VarIDs were modified by the Value's execution.
   728  func (state *DebugState) processValue(v *Value, vSlots []SlotID, vReg *ssabase.Register) bool {
   729  	locs := state.currentState
   730  	changed := false
   731  	setSlot := func(slot SlotID, loc VarLoc) {
   732  		changed = true
   733  		state.changedVars.Add(ID(state.SlotVars[slot]))
   734  		state.changedSlots.Add(ID(slot))
   735  		state.currentState.slots[slot] = loc
   736  	}
   737  
   738  	// Handle any register clobbering. Call operations, for example,
   739  	// clobber all registers even though they don't explicitly write to
   740  	// them.
   741  	clobbers := ssaop.OpcodeTable[v.Op].Reg.Clobbers
   742  	for {
   743  		if clobbers.Empty() {
   744  			break
   745  		}
   746  		reg := clobbers.PickReg()
   747  		clobbers = clobbers.RemoveReg(reg)
   748  
   749  		for _, slot := range locs.registers[reg] {
   750  			if state.LoggingLevel > 1 {
   751  				state.Logf("at %v: %v clobbered out of %v\n", v, state.Slots[slot], &state.Registers[reg])
   752  			}
   753  
   754  			last := locs.slots[slot]
   755  			if last.absent() {
   756  				state.F.Fatalf("at %v: slot %v in register %v with no location entry", v, state.Slots[slot], &state.Registers[reg])
   757  				continue
   758  			}
   759  			regs := last.Registers.RemoveReg(ssaop.Register(reg))
   760  			setSlot(slot, VarLoc{regs, last.StackOffset})
   761  		}
   762  
   763  		locs.registers[reg] = locs.registers[reg][:0]
   764  	}
   765  
   766  	switch {
   767  	case v.Op == ssaop.OpVarDef:
   768  		n := v.Aux.(*ir.Name)
   769  		if ir.IsSynthetic(n) || !IsVarWantedForDebug(n) {
   770  			break
   771  		}
   772  
   773  		slotID := state.VarParts[n][0]
   774  		var stackOffset StackOffset
   775  		if v.Op == ssaop.OpVarDef {
   776  			stackOffset = StackOffset(state.StackOffset(state.Slots[slotID])<<1 | 1)
   777  		}
   778  		setSlot(slotID, VarLoc{RegisterSet{}, stackOffset})
   779  		if state.LoggingLevel > 1 {
   780  			if v.Op == ssaop.OpVarDef {
   781  				state.Logf("at %v: stack-only var %v now live\n", v, state.Slots[slotID])
   782  			} else {
   783  				state.Logf("at %v: stack-only var %v now dead\n", v, state.Slots[slotID])
   784  			}
   785  		}
   786  
   787  	case v.Op == ssaop.OpArg:
   788  		home := state.F.GetHome(v.ID).(LocalSlot)
   789  		stackOffset := state.StackOffset(home)<<1 | 1
   790  		for _, slot := range vSlots {
   791  			if state.LoggingLevel > 1 {
   792  				state.Logf("at %v: arg %v now on stack in location %v\n", v, state.Slots[slot], home)
   793  				if last := locs.slots[slot]; !last.absent() {
   794  					state.Logf("at %v: unexpected arg op on already-live slot %v\n", v, state.Slots[slot])
   795  				}
   796  			}
   797  
   798  			setSlot(slot, VarLoc{RegisterSet{}, StackOffset(stackOffset)})
   799  		}
   800  
   801  	case v.Op == ssaop.OpStoreReg:
   802  		home := state.F.GetHome(v.ID).(LocalSlot)
   803  		stackOffset := state.StackOffset(home)<<1 | 1
   804  		for _, slot := range vSlots {
   805  			last := locs.slots[slot]
   806  			if last.absent() {
   807  				if state.LoggingLevel > 1 {
   808  					state.Logf("at %v: unexpected spill of unnamed register %s\n", v, vReg)
   809  				}
   810  				break
   811  			}
   812  
   813  			setSlot(slot, VarLoc{last.Registers, StackOffset(stackOffset)})
   814  			if state.LoggingLevel > 1 {
   815  				state.Logf("at %v: %v spilled to stack location %v@%d\n", v, state.Slots[slot], home, state.StackOffset(home))
   816  			}
   817  		}
   818  
   819  	case vReg != nil:
   820  		if state.LoggingLevel > 1 {
   821  			newSlots := make([]bool, len(state.Slots))
   822  			for _, slot := range vSlots {
   823  				newSlots[slot] = true
   824  			}
   825  
   826  			for _, slot := range locs.registers[vReg.Num] {
   827  				if !newSlots[slot] {
   828  					state.Logf("at %v: overwrote %v in register %v\n", v, state.Slots[slot], vReg)
   829  				}
   830  			}
   831  		}
   832  
   833  		for _, slot := range locs.registers[vReg.Num] {
   834  			last := locs.slots[slot]
   835  			setSlot(slot, VarLoc{last.Registers.RemoveReg(ssaop.Register(vReg.Num)), last.StackOffset})
   836  		}
   837  		locs.registers[vReg.Num] = locs.registers[vReg.Num][:0]
   838  		locs.registers[vReg.Num] = append(locs.registers[vReg.Num], vSlots...)
   839  		for _, slot := range vSlots {
   840  			if state.LoggingLevel > 1 {
   841  				state.Logf("at %v: %v now in %s\n", v, state.Slots[slot], vReg)
   842  			}
   843  
   844  			last := locs.slots[slot]
   845  			setSlot(slot, VarLoc{last.Registers.AddReg(ssaop.Register(vReg.Num)), last.StackOffset})
   846  		}
   847  	}
   848  	return changed
   849  }
   850  
   851  func (e *pendingEntry) clear() {
   852  	e.present = false
   853  	e.startBlock = 0
   854  	e.startValue = 0
   855  	clear(e.pieces)
   856  }
   857  
   858  // BuildLocationLists builds location lists for all the user variables
   859  // in state.f, using the information about block state in blockLocs.
   860  // The returned location lists are not fully complete. They are in
   861  // terms of SSA values rather than PCs, and have no base address/end
   862  // entries. They will be finished by PutLocationList.
   863  func (state *DebugState) BuildLocationLists(blockLocs []*BlockDebug) {
   864  	// Run through the function in program text order, building up location
   865  	// lists as we go. The heavy lifting has mostly already been done.
   866  
   867  	var prevBlock *Block
   868  	for _, b := range state.F.Blocks {
   869  		state.mergePredecessors(b, blockLocs, prevBlock, true)
   870  
   871  		// Handle any differences among predecessor blocks and previous block (perhaps not a predecessor)
   872  		for _, varID := range state.changedVars.Contents() {
   873  			state.updateVar(VarID(varID), b, BlockStart)
   874  		}
   875  		state.changedVars.Clear()
   876  
   877  		if !blockLocs[b.ID].relevant {
   878  			continue
   879  		}
   880  
   881  		mustBeFirst := func(v *Value) bool {
   882  			return v.Op == ssaop.OpPhi || v.Op.IsLoweredGetClosurePtr() ||
   883  				v.Op == ssaop.OpArgIntReg || v.Op == ssaop.OpArgFloatReg
   884  		}
   885  
   886  		blockPrologComplete := func(v *Value) bool {
   887  			if b.ID != state.F.Entry.ID {
   888  				return !ssaop.OpcodeTable[v.Op].ZeroWidth
   889  			} else {
   890  				return v.Op == ssaop.OpInitMem
   891  			}
   892  		}
   893  
   894  		// Examine the prolog portion of the block to process special
   895  		// zero-width ops such as Arg, Phi, LoweredGetClosurePtr (etc)
   896  		// whose lifetimes begin at the block starting point. In an
   897  		// entry block, allow for the possibility that we may see Arg
   898  		// ops that appear _after_ other non-zero-width operations.
   899  		// Example:
   900  		//
   901  		//   v33 = ArgIntReg <uintptr> {foo+0} [0] : AX (foo)
   902  		//   v34 = ArgIntReg <uintptr> {bar+0} [0] : BX (bar)
   903  		//   ...
   904  		//   v77 = StoreReg <unsafe.Pointer> v67 : ctx+8[unsafe.Pointer]
   905  		//   v78 = StoreReg <unsafe.Pointer> v68 : ctx[unsafe.Pointer]
   906  		//   v79 = Arg <*uint8> {args} : args[*uint8] (args[*uint8])
   907  		//   v80 = Arg <int> {args} [8] : args+8[int] (args+8[int])
   908  		//   ...
   909  		//   v1 = InitMem <mem>
   910  		//
   911  		// We can stop scanning the initial portion of the block when
   912  		// we either see the InitMem op (for entry blocks) or the
   913  		// first non-zero-width op (for other blocks).
   914  		for idx := 0; idx < len(b.Values); idx++ {
   915  			v := b.Values[idx]
   916  			if blockPrologComplete(v) {
   917  				break
   918  			}
   919  			// Consider only "lifetime begins at block start" ops.
   920  			if !mustBeFirst(v) && v.Op != ssaop.OpArg {
   921  				continue
   922  			}
   923  			slots := state.ValueNames[v.ID]
   924  			reg, _ := state.F.GetHome(v.ID).(*ssabase.Register)
   925  			changed := state.processValue(v, slots, reg) // changed == added to state.changedVars
   926  			if changed {
   927  				for _, varID := range state.changedVars.Contents() {
   928  					state.updateVar(VarID(varID), v.Block, BlockStart)
   929  				}
   930  				state.changedVars.Clear()
   931  			}
   932  		}
   933  
   934  		// Now examine the block again, handling things other than the
   935  		// "begins at block start" lifetimes.
   936  		zeroWidthPending := false
   937  		prologComplete := false
   938  		// expect to see values in pattern (apc)* (zerowidth|real)*
   939  		for _, v := range b.Values {
   940  			if blockPrologComplete(v) {
   941  				prologComplete = true
   942  			}
   943  			slots := state.ValueNames[v.ID]
   944  			reg, _ := state.F.GetHome(v.ID).(*ssabase.Register)
   945  			changed := state.processValue(v, slots, reg) // changed == added to state.changedVars
   946  
   947  			if ssaop.OpcodeTable[v.Op].ZeroWidth {
   948  				if prologComplete && mustBeFirst(v) {
   949  					panic(fmt.Errorf("Unexpected placement of op '%s' appearing after non-pseudo-op at beginning of block %s in %s\n%s", v.LongString(), b, b.Func.Name, b.Func))
   950  				}
   951  				if changed {
   952  					if mustBeFirst(v) || v.Op == ssaop.OpArg {
   953  						// already taken care of above
   954  						continue
   955  					}
   956  					zeroWidthPending = true
   957  				}
   958  				continue
   959  			}
   960  			if !changed && !zeroWidthPending {
   961  				continue
   962  			}
   963  
   964  			// Not zero-width; i.e., a "real" instruction.
   965  			zeroWidthPending = false
   966  			for _, varID := range state.changedVars.Contents() {
   967  				state.updateVar(VarID(varID), v.Block, v)
   968  			}
   969  			state.changedVars.Clear()
   970  		}
   971  		for _, varID := range state.changedVars.Contents() {
   972  			state.updateVar(VarID(varID), b, BlockEnd)
   973  		}
   974  
   975  		prevBlock = b
   976  	}
   977  
   978  	if state.LoggingLevel > 0 {
   979  		state.Logf("location lists:\n")
   980  	}
   981  
   982  	// Flush any leftover entries live at the end of the last block.
   983  	for varID := range state.Lists {
   984  		state.writePendingEntry(VarID(varID), -1, FuncEnd.ID)
   985  		list := state.Lists[varID]
   986  		if state.LoggingLevel > 0 {
   987  			if len(list) == 0 {
   988  				state.Logf("\t%v : empty list\n", state.Vars[varID])
   989  			} else {
   990  				state.Logf("\t%v : %d entries\n", state.Vars[varID], len(list))
   991  			}
   992  		}
   993  	}
   994  }
   995  
   996  // updateVar updates the pending location list entry for varID to
   997  // reflect the new locations in curLoc, beginning at v in block b.
   998  // v may be one of the special values indicating block start or end.
   999  func (state *DebugState) updateVar(varID VarID, b *Block, v *Value) {
  1000  	curLoc := state.currentState.slots
  1001  	// Assemble the location list entry with whatever's live.
  1002  	empty := true
  1003  	for _, slotID := range state.VarSlots[varID] {
  1004  		if !curLoc[slotID].absent() {
  1005  			empty = false
  1006  			break
  1007  		}
  1008  	}
  1009  	pending := &state.pendingEntries[varID]
  1010  	if empty {
  1011  		state.writePendingEntry(varID, b.ID, v.ID)
  1012  		pending.clear()
  1013  		return
  1014  	}
  1015  
  1016  	// Extend the previous entry if possible.
  1017  	if pending.present {
  1018  		merge := true
  1019  		for i, slotID := range state.VarSlots[varID] {
  1020  			if !canMerge(pending.pieces[i], curLoc[slotID]) {
  1021  				merge = false
  1022  				break
  1023  			}
  1024  		}
  1025  		if merge {
  1026  			return
  1027  		}
  1028  	}
  1029  
  1030  	state.writePendingEntry(varID, b.ID, v.ID)
  1031  	pending.present = true
  1032  	pending.startBlock = b.ID
  1033  	pending.startValue = v.ID
  1034  	for i, slot := range state.VarSlots[varID] {
  1035  		pending.pieces[i] = curLoc[slot]
  1036  	}
  1037  }
  1038  
  1039  // writePendingEntry writes out the pending entry for varID, if any,
  1040  // terminated at endBlock/Value.
  1041  func (state *DebugState) writePendingEntry(varID VarID, endBlock, endValue ID) {
  1042  	pending := state.pendingEntries[varID]
  1043  	if !pending.present {
  1044  		return
  1045  	}
  1046  
  1047  	// Skip zero-width entries where start and end coordinates are identical.
  1048  	if pending.startBlock == endBlock && pending.startValue == endValue {
  1049  		if state.LoggingLevel > 1 {
  1050  			state.Logf("Skipping empty location list for %v in %s\n", state.Vars[varID], state.F.Name)
  1051  		}
  1052  		return
  1053  	}
  1054  
  1055  	if state.LoggingLevel > 1 {
  1056  		var partStrs []string
  1057  		for i, slot := range state.VarSlots[varID] {
  1058  			partStrs = append(partStrs, fmt.Sprintf("%v@%v", state.Slots[slot], state.LocString(pending.pieces[i])))
  1059  		}
  1060  		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, " "))
  1061  	}
  1062  
  1063  	// Build the DWARF location expression.
  1064  	var expr []byte
  1065  	for i, slotID := range state.VarSlots[varID] {
  1066  		loc := pending.pieces[i]
  1067  		slot := state.Slots[slotID]
  1068  
  1069  		if !loc.absent() {
  1070  			if loc.onStack() {
  1071  				if loc.stackOffsetValue() == 0 {
  1072  					expr = append(expr, dwarf.DW_OP_call_frame_cfa)
  1073  				} else {
  1074  					expr = append(expr, dwarf.DW_OP_fbreg)
  1075  					expr = dwarf.AppendSleb128(expr, int64(loc.stackOffsetValue()))
  1076  				}
  1077  			} else {
  1078  				regnum := state.Ctxt.Arch.DWARFRegisters[state.Registers[firstReg(loc.Registers)].ObjNum]
  1079  				if regnum < 32 {
  1080  					expr = append(expr, dwarf.DW_OP_reg0+byte(regnum))
  1081  				} else {
  1082  					expr = append(expr, dwarf.DW_OP_regx)
  1083  					expr = dwarf.AppendUleb128(expr, uint64(regnum))
  1084  				}
  1085  			}
  1086  		}
  1087  
  1088  		if len(state.VarSlots[varID]) > 1 {
  1089  			expr = append(expr, dwarf.DW_OP_piece)
  1090  			expr = dwarf.AppendUleb128(expr, uint64(slot.Type.Size()))
  1091  		}
  1092  	}
  1093  
  1094  	entry := LocListEntry{
  1095  		StartBlock: pending.startBlock,
  1096  		StartValue: pending.startValue,
  1097  		EndBlock:   endBlock,
  1098  		EndValue:   endValue,
  1099  		Expr:       expr,
  1100  	}
  1101  	state.Lists[varID] = append(state.Lists[varID], entry)
  1102  }
  1103
View as plain text