Black Lives Matter. Support the Equal Justice Initiative.

Source file src/cmd/internal/obj/pcln.go

Documentation: cmd/internal/obj

     1  // Copyright 2013 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 obj
     6  
     7  import (
     8  	"cmd/internal/goobj"
     9  	"cmd/internal/objabi"
    10  	"encoding/binary"
    11  	"log"
    12  )
    13  
    14  // funcpctab writes to dst a pc-value table mapping the code in func to the values
    15  // returned by valfunc parameterized by arg. The invocation of valfunc to update the
    16  // current value is, for each p,
    17  //
    18  //	sym = valfunc(func, p, 0, arg);
    19  //	record sym.P as value at p->pc;
    20  //	sym = valfunc(func, p, 1, arg);
    21  //
    22  // where func is the function, val is the current value, p is the instruction being
    23  // considered, and arg can be used to further parameterize valfunc.
    24  func funcpctab(ctxt *Link, func_ *LSym, desc string, valfunc func(*Link, *LSym, int32, *Prog, int32, interface{}) int32, arg interface{}) *LSym {
    25  	dbg := desc == ctxt.Debugpcln
    26  	dst := []byte{}
    27  	sym := &LSym{
    28  		Type:      objabi.SRODATA,
    29  		Attribute: AttrContentAddressable,
    30  	}
    31  
    32  	if dbg {
    33  		ctxt.Logf("funcpctab %s [valfunc=%s]\n", func_.Name, desc)
    34  	}
    35  
    36  	val := int32(-1)
    37  	oldval := val
    38  	fn := func_.Func()
    39  	if fn.Text == nil {
    40  		// Return the emtpy symbol we've built so far.
    41  		return sym
    42  	}
    43  
    44  	pc := fn.Text.Pc
    45  
    46  	if dbg {
    47  		ctxt.Logf("%6x %6d %v\n", uint64(pc), val, fn.Text)
    48  	}
    49  
    50  	buf := make([]byte, binary.MaxVarintLen32)
    51  	started := false
    52  	for p := fn.Text; p != nil; p = p.Link {
    53  		// Update val. If it's not changing, keep going.
    54  		val = valfunc(ctxt, func_, val, p, 0, arg)
    55  
    56  		if val == oldval && started {
    57  			val = valfunc(ctxt, func_, val, p, 1, arg)
    58  			if dbg {
    59  				ctxt.Logf("%6x %6s %v\n", uint64(p.Pc), "", p)
    60  			}
    61  			continue
    62  		}
    63  
    64  		// If the pc of the next instruction is the same as the
    65  		// pc of this instruction, this instruction is not a real
    66  		// instruction. Keep going, so that we only emit a delta
    67  		// for a true instruction boundary in the program.
    68  		if p.Link != nil && p.Link.Pc == p.Pc {
    69  			val = valfunc(ctxt, func_, val, p, 1, arg)
    70  			if dbg {
    71  				ctxt.Logf("%6x %6s %v\n", uint64(p.Pc), "", p)
    72  			}
    73  			continue
    74  		}
    75  
    76  		// The table is a sequence of (value, pc) pairs, where each
    77  		// pair states that the given value is in effect from the current position
    78  		// up to the given pc, which becomes the new current position.
    79  		// To generate the table as we scan over the program instructions,
    80  		// we emit a "(value" when pc == func->value, and then
    81  		// each time we observe a change in value we emit ", pc) (value".
    82  		// When the scan is over, we emit the closing ", pc)".
    83  		//
    84  		// The table is delta-encoded. The value deltas are signed and
    85  		// transmitted in zig-zag form, where a complement bit is placed in bit 0,
    86  		// and the pc deltas are unsigned. Both kinds of deltas are sent
    87  		// as variable-length little-endian base-128 integers,
    88  		// where the 0x80 bit indicates that the integer continues.
    89  
    90  		if dbg {
    91  			ctxt.Logf("%6x %6d %v\n", uint64(p.Pc), val, p)
    92  		}
    93  
    94  		if started {
    95  			pcdelta := (p.Pc - pc) / int64(ctxt.Arch.MinLC)
    96  			n := binary.PutUvarint(buf, uint64(pcdelta))
    97  			dst = append(dst, buf[:n]...)
    98  			pc = p.Pc
    99  		}
   100  
   101  		delta := val - oldval
   102  		n := binary.PutVarint(buf, int64(delta))
   103  		dst = append(dst, buf[:n]...)
   104  		oldval = val
   105  		started = true
   106  		val = valfunc(ctxt, func_, val, p, 1, arg)
   107  	}
   108  
   109  	if started {
   110  		if dbg {
   111  			ctxt.Logf("%6x done\n", uint64(fn.Text.Pc+func_.Size))
   112  		}
   113  		v := (func_.Size - pc) / int64(ctxt.Arch.MinLC)
   114  		if v < 0 {
   115  			ctxt.Diag("negative pc offset: %v", v)
   116  		}
   117  		n := binary.PutUvarint(buf, uint64(v))
   118  		dst = append(dst, buf[:n]...)
   119  		// add terminating varint-encoded 0, which is just 0
   120  		dst = append(dst, 0)
   121  	}
   122  
   123  	if dbg {
   124  		ctxt.Logf("wrote %d bytes to %p\n", len(dst), dst)
   125  		for _, p := range dst {
   126  			ctxt.Logf(" %02x", p)
   127  		}
   128  		ctxt.Logf("\n")
   129  	}
   130  
   131  	sym.Size = int64(len(dst))
   132  	sym.P = dst
   133  	return sym
   134  }
   135  
   136  // pctofileline computes either the file number (arg == 0)
   137  // or the line number (arg == 1) to use at p.
   138  // Because p.Pos applies to p, phase == 0 (before p)
   139  // takes care of the update.
   140  func pctofileline(ctxt *Link, sym *LSym, oldval int32, p *Prog, phase int32, arg interface{}) int32 {
   141  	if p.As == ATEXT || p.As == ANOP || p.Pos.Line() == 0 || phase == 1 {
   142  		return oldval
   143  	}
   144  	f, l := getFileIndexAndLine(ctxt, p.Pos)
   145  	if arg == nil {
   146  		return l
   147  	}
   148  	pcln := arg.(*Pcln)
   149  	pcln.UsedFiles[goobj.CUFileIndex(f)] = struct{}{}
   150  	return int32(f)
   151  }
   152  
   153  // pcinlineState holds the state used to create a function's inlining
   154  // tree and the PC-value table that maps PCs to nodes in that tree.
   155  type pcinlineState struct {
   156  	globalToLocal map[int]int
   157  	localTree     InlTree
   158  }
   159  
   160  // addBranch adds a branch from the global inlining tree in ctxt to
   161  // the function's local inlining tree, returning the index in the local tree.
   162  func (s *pcinlineState) addBranch(ctxt *Link, globalIndex int) int {
   163  	if globalIndex < 0 {
   164  		return -1
   165  	}
   166  
   167  	localIndex, ok := s.globalToLocal[globalIndex]
   168  	if ok {
   169  		return localIndex
   170  	}
   171  
   172  	// Since tracebacks don't include column information, we could
   173  	// use one node for multiple calls of the same function on the
   174  	// same line (e.g., f(x) + f(y)). For now, we use one node for
   175  	// each inlined call.
   176  	call := ctxt.InlTree.nodes[globalIndex]
   177  	call.Parent = s.addBranch(ctxt, call.Parent)
   178  	localIndex = len(s.localTree.nodes)
   179  	s.localTree.nodes = append(s.localTree.nodes, call)
   180  	s.globalToLocal[globalIndex] = localIndex
   181  	return localIndex
   182  }
   183  
   184  func (s *pcinlineState) setParentPC(ctxt *Link, globalIndex int, pc int32) {
   185  	localIndex, ok := s.globalToLocal[globalIndex]
   186  	if !ok {
   187  		// We know where to unwind to when we need to unwind a body identified
   188  		// by globalIndex. But there may be no instructions generated by that
   189  		// body (it's empty, or its instructions were CSEd with other things, etc.).
   190  		// In that case, we don't need an unwind entry.
   191  		// TODO: is this really right? Seems to happen a whole lot...
   192  		return
   193  	}
   194  	s.localTree.setParentPC(localIndex, pc)
   195  }
   196  
   197  // pctoinline computes the index into the local inlining tree to use at p.
   198  // If p is not the result of inlining, pctoinline returns -1. Because p.Pos
   199  // applies to p, phase == 0 (before p) takes care of the update.
   200  func (s *pcinlineState) pctoinline(ctxt *Link, sym *LSym, oldval int32, p *Prog, phase int32, arg interface{}) int32 {
   201  	if phase == 1 {
   202  		return oldval
   203  	}
   204  
   205  	posBase := ctxt.PosTable.Pos(p.Pos).Base()
   206  	if posBase == nil {
   207  		return -1
   208  	}
   209  
   210  	globalIndex := posBase.InliningIndex()
   211  	if globalIndex < 0 {
   212  		return -1
   213  	}
   214  
   215  	if s.globalToLocal == nil {
   216  		s.globalToLocal = make(map[int]int)
   217  	}
   218  
   219  	return int32(s.addBranch(ctxt, globalIndex))
   220  }
   221  
   222  // pctospadj computes the sp adjustment in effect.
   223  // It is oldval plus any adjustment made by p itself.
   224  // The adjustment by p takes effect only after p, so we
   225  // apply the change during phase == 1.
   226  func pctospadj(ctxt *Link, sym *LSym, oldval int32, p *Prog, phase int32, arg interface{}) int32 {
   227  	if oldval == -1 { // starting
   228  		oldval = 0
   229  	}
   230  	if phase == 0 {
   231  		return oldval
   232  	}
   233  	if oldval+p.Spadj < -10000 || oldval+p.Spadj > 1100000000 {
   234  		ctxt.Diag("overflow in spadj: %d + %d = %d", oldval, p.Spadj, oldval+p.Spadj)
   235  		ctxt.DiagFlush()
   236  		log.Fatalf("bad code")
   237  	}
   238  
   239  	return oldval + p.Spadj
   240  }
   241  
   242  // pctopcdata computes the pcdata value in effect at p.
   243  // A PCDATA instruction sets the value in effect at future
   244  // non-PCDATA instructions.
   245  // Since PCDATA instructions have no width in the final code,
   246  // it does not matter which phase we use for the update.
   247  func pctopcdata(ctxt *Link, sym *LSym, oldval int32, p *Prog, phase int32, arg interface{}) int32 {
   248  	if phase == 0 || p.As != APCDATA || p.From.Offset != int64(arg.(uint32)) {
   249  		return oldval
   250  	}
   251  	if int64(int32(p.To.Offset)) != p.To.Offset {
   252  		ctxt.Diag("overflow in PCDATA instruction: %v", p)
   253  		ctxt.DiagFlush()
   254  		log.Fatalf("bad code")
   255  	}
   256  
   257  	return int32(p.To.Offset)
   258  }
   259  
   260  func linkpcln(ctxt *Link, cursym *LSym) {
   261  	pcln := &cursym.Func().Pcln
   262  	pcln.UsedFiles = make(map[goobj.CUFileIndex]struct{})
   263  
   264  	npcdata := 0
   265  	nfuncdata := 0
   266  	for p := cursym.Func().Text; p != nil; p = p.Link {
   267  		// Find the highest ID of any used PCDATA table. This ignores PCDATA table
   268  		// that consist entirely of "-1", since that's the assumed default value.
   269  		//   From.Offset is table ID
   270  		//   To.Offset is data
   271  		if p.As == APCDATA && p.From.Offset >= int64(npcdata) && p.To.Offset != -1 { // ignore -1 as we start at -1, if we only see -1, nothing changed
   272  			npcdata = int(p.From.Offset + 1)
   273  		}
   274  		// Find the highest ID of any FUNCDATA table.
   275  		//   From.Offset is table ID
   276  		if p.As == AFUNCDATA && p.From.Offset >= int64(nfuncdata) {
   277  			nfuncdata = int(p.From.Offset + 1)
   278  		}
   279  	}
   280  
   281  	pcln.Pcdata = make([]*LSym, npcdata)
   282  	pcln.Funcdata = make([]*LSym, nfuncdata)
   283  	pcln.Funcdataoff = make([]int64, nfuncdata)
   284  	pcln.Funcdataoff = pcln.Funcdataoff[:nfuncdata]
   285  
   286  	pcln.Pcsp = funcpctab(ctxt, cursym, "pctospadj", pctospadj, nil)
   287  	pcln.Pcfile = funcpctab(ctxt, cursym, "pctofile", pctofileline, pcln)
   288  	pcln.Pcline = funcpctab(ctxt, cursym, "pctoline", pctofileline, nil)
   289  
   290  	// Check that all the Progs used as inline markers are still reachable.
   291  	// See issue #40473.
   292  	fn := cursym.Func()
   293  	inlMarkProgs := make(map[*Prog]struct{}, len(fn.InlMarks))
   294  	for _, inlMark := range fn.InlMarks {
   295  		inlMarkProgs[inlMark.p] = struct{}{}
   296  	}
   297  	for p := fn.Text; p != nil; p = p.Link {
   298  		if _, ok := inlMarkProgs[p]; ok {
   299  			delete(inlMarkProgs, p)
   300  		}
   301  	}
   302  	if len(inlMarkProgs) > 0 {
   303  		ctxt.Diag("one or more instructions used as inline markers are no longer reachable")
   304  	}
   305  
   306  	pcinlineState := new(pcinlineState)
   307  	pcln.Pcinline = funcpctab(ctxt, cursym, "pctoinline", pcinlineState.pctoinline, nil)
   308  	for _, inlMark := range fn.InlMarks {
   309  		pcinlineState.setParentPC(ctxt, int(inlMark.id), int32(inlMark.p.Pc))
   310  	}
   311  	pcln.InlTree = pcinlineState.localTree
   312  	if ctxt.Debugpcln == "pctoinline" && len(pcln.InlTree.nodes) > 0 {
   313  		ctxt.Logf("-- inlining tree for %s:\n", cursym)
   314  		dumpInlTree(ctxt, pcln.InlTree)
   315  		ctxt.Logf("--\n")
   316  	}
   317  
   318  	// tabulate which pc and func data we have.
   319  	havepc := make([]uint32, (npcdata+31)/32)
   320  	havefunc := make([]uint32, (nfuncdata+31)/32)
   321  	for p := fn.Text; p != nil; p = p.Link {
   322  		if p.As == AFUNCDATA {
   323  			if (havefunc[p.From.Offset/32]>>uint64(p.From.Offset%32))&1 != 0 {
   324  				ctxt.Diag("multiple definitions for FUNCDATA $%d", p.From.Offset)
   325  			}
   326  			havefunc[p.From.Offset/32] |= 1 << uint64(p.From.Offset%32)
   327  		}
   328  
   329  		if p.As == APCDATA && p.To.Offset != -1 {
   330  			havepc[p.From.Offset/32] |= 1 << uint64(p.From.Offset%32)
   331  		}
   332  	}
   333  
   334  	// pcdata.
   335  	for i := 0; i < npcdata; i++ {
   336  		if (havepc[i/32]>>uint(i%32))&1 == 0 {
   337  			// use an empty symbol.
   338  			pcln.Pcdata[i] = &LSym{
   339  				Type:      objabi.SRODATA,
   340  				Attribute: AttrContentAddressable,
   341  			}
   342  		} else {
   343  			pcln.Pcdata[i] = funcpctab(ctxt, cursym, "pctopcdata", pctopcdata, interface{}(uint32(i)))
   344  		}
   345  	}
   346  
   347  	// funcdata
   348  	if nfuncdata > 0 {
   349  		for p := fn.Text; p != nil; p = p.Link {
   350  			if p.As != AFUNCDATA {
   351  				continue
   352  			}
   353  			i := int(p.From.Offset)
   354  			pcln.Funcdataoff[i] = p.To.Offset
   355  			if p.To.Type != TYPE_CONST {
   356  				// TODO: Dedup.
   357  				//funcdata_bytes += p->to.sym->size;
   358  				pcln.Funcdata[i] = p.To.Sym
   359  			}
   360  		}
   361  	}
   362  }
   363  
   364  // PCIter iterates over encoded pcdata tables.
   365  type PCIter struct {
   366  	p       []byte
   367  	PC      uint32
   368  	NextPC  uint32
   369  	PCScale uint32
   370  	Value   int32
   371  	start   bool
   372  	Done    bool
   373  }
   374  
   375  // newPCIter creates a PCIter with a scale factor for the PC step size.
   376  func NewPCIter(pcScale uint32) *PCIter {
   377  	it := new(PCIter)
   378  	it.PCScale = pcScale
   379  	return it
   380  }
   381  
   382  // Next advances it to the Next pc.
   383  func (it *PCIter) Next() {
   384  	it.PC = it.NextPC
   385  	if it.Done {
   386  		return
   387  	}
   388  	if len(it.p) == 0 {
   389  		it.Done = true
   390  		return
   391  	}
   392  
   393  	// Value delta
   394  	val, n := binary.Varint(it.p)
   395  	if n <= 0 {
   396  		log.Fatalf("bad Value varint in pciterNext: read %v", n)
   397  	}
   398  	it.p = it.p[n:]
   399  
   400  	if val == 0 && !it.start {
   401  		it.Done = true
   402  		return
   403  	}
   404  
   405  	it.start = false
   406  	it.Value += int32(val)
   407  
   408  	// pc delta
   409  	pc, n := binary.Uvarint(it.p)
   410  	if n <= 0 {
   411  		log.Fatalf("bad pc varint in pciterNext: read %v", n)
   412  	}
   413  	it.p = it.p[n:]
   414  
   415  	it.NextPC = it.PC + uint32(pc)*it.PCScale
   416  }
   417  
   418  // init prepares it to iterate over p,
   419  // and advances it to the first pc.
   420  func (it *PCIter) Init(p []byte) {
   421  	it.p = p
   422  	it.PC = 0
   423  	it.NextPC = 0
   424  	it.Value = -1
   425  	it.start = true
   426  	it.Done = false
   427  	it.Next()
   428  }
   429  

View as plain text