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