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