pcln.go

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