/
debug.go
574 lines (517 loc) · 16.7 KB
/
debug.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
// Copyright 2017 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package ssa
import (
"cmd/internal/obj"
"fmt"
"strings"
)
type SlotID int32
// A FuncDebug contains all the debug information for the variables in a
// function. Variables are identified by their LocalSlot, which may be the
// result of decomposing a larger variable.
type FuncDebug struct {
// Slots is all the slots used in the debug info, indexed by their SlotID.
// Use this when getting a LocalSlot from a SlotID.
Slots []*LocalSlot
// VarSlots is the slots that represent part of user variables.
// Use this when iterating over all the slots to generate debug information.
VarSlots []*LocalSlot
// The blocks in the function, in program text order.
Blocks []*BlockDebug
// The registers of the current architecture, indexed by Register.num.
Registers []Register
}
func (f *FuncDebug) BlockString(b *BlockDebug) string {
var vars []string
for slot := range f.VarSlots {
if len(b.Variables[slot].Locations) == 0 {
continue
}
vars = append(vars, fmt.Sprintf("%v = %v", f.Slots[slot], b.Variables[slot]))
}
return fmt.Sprintf("{%v}", strings.Join(vars, ", "))
}
func (f *FuncDebug) SlotLocsString(id SlotID) string {
var locs []string
for _, block := range f.Blocks {
for _, loc := range block.Variables[id].Locations {
locs = append(locs, block.LocString(loc))
}
}
return strings.Join(locs, " ")
}
type BlockDebug struct {
// The SSA block that this tracks. For debug logging only.
Block *Block
// The variables in this block, indexed by their SlotID.
Variables []VarLocList
}
func (b *BlockDebug) LocString(loc *VarLoc) string {
registers := b.Block.Func.Config.registers
var storage []string
if loc.OnStack {
storage = append(storage, "stack")
}
for reg := 0; reg < 64; reg++ {
if loc.Registers&(1<<uint8(reg)) == 0 {
continue
}
if registers != nil {
storage = append(storage, registers[reg].String())
} else {
storage = append(storage, fmt.Sprintf("reg%d", reg))
}
}
if len(storage) == 0 {
storage = append(storage, "!!!no storage!!!")
}
pos := func(v *Value, p *obj.Prog, pc int64) string {
if v == nil {
return "?"
}
vStr := fmt.Sprintf("v%d", v.ID)
if v == BlockStart {
vStr = fmt.Sprintf("b%dStart", b.Block.ID)
}
if v == BlockEnd {
vStr = fmt.Sprintf("b%dEnd", b.Block.ID)
}
if p == nil {
return vStr
}
return fmt.Sprintf("%s/%x", vStr, pc)
}
start := pos(loc.Start, loc.StartProg, loc.StartPC)
end := pos(loc.End, loc.EndProg, loc.EndPC)
return fmt.Sprintf("%v-%v@%s", start, end, strings.Join(storage, ","))
}
// append adds a location to the location list for slot.
func (b *BlockDebug) append(slot SlotID, loc *VarLoc) {
b.Variables[slot].append(loc)
}
// lastLoc returns the last VarLoc for slot, or nil if it has none.
func (b *BlockDebug) lastLoc(slot SlotID) *VarLoc {
return b.Variables[slot].last()
}
// A VarLocList contains the locations for a variable, in program text order.
// It will often have gaps.
type VarLocList struct {
Locations []*VarLoc
}
func (l *VarLocList) append(loc *VarLoc) {
l.Locations = append(l.Locations, loc)
}
// last returns the last location in the list.
func (l *VarLocList) last() *VarLoc {
if l == nil || len(l.Locations) == 0 {
return nil
}
return l.Locations[len(l.Locations)-1]
}
// A VarLoc describes a variable's location in a single contiguous range
// of program text. It is generated from the SSA representation, but it
// refers to the generated machine code, so the Values referenced are better
// understood as PCs than actual Values, and the ranges can cross blocks.
// The range is defined first by Values, which are then mapped to Progs
// during genssa and finally to function PCs after assembly.
// A variable can be on the stack and in any number of registers.
type VarLoc struct {
// Inclusive -- the first SSA value that the range covers. The value
// doesn't necessarily have anything to do with the variable; it just
// identifies a point in the program text.
// The special sentinel value BlockStart indicates that the range begins
// at the beginning of the containing block, even if the block doesn't
// actually have a Value to use to indicate that.
Start *Value
// Exclusive -- the first SSA value after start that the range doesn't
// cover. A location with start == end is empty.
// The special sentinel value BlockEnd indicates that the variable survives
// to the end of the of the containing block, after all its Values and any
// control flow instructions added later.
End *Value
// The prog/PCs corresponding to Start and End above. These are for the
// convenience of later passes, since code generation isn't done when
// BuildFuncDebug runs.
// Control flow instructions don't correspond to a Value, so EndProg
// may point to a Prog in the next block if SurvivedBlock is true. For
// the last block, where there's no later Prog, it will be nil to indicate
// the end of the function.
StartProg, EndProg *obj.Prog
StartPC, EndPC int64
// The registers this variable is available in. There can be more than
// one in various situations, e.g. it's being moved between registers.
Registers RegisterSet
// OnStack indicates that the variable is on the stack in the LocalSlot
// identified by StackLocation.
OnStack bool
StackLocation SlotID
}
var BlockStart = &Value{
ID: -10000,
Op: OpInvalid,
Aux: "BlockStart",
}
var BlockEnd = &Value{
ID: -20000,
Op: OpInvalid,
Aux: "BlockEnd",
}
// RegisterSet is a bitmap of registers, indexed by Register.num.
type RegisterSet uint64
// unexpected is used to indicate an inconsistency or bug in the debug info
// generation process. These are not fixable by users. At time of writing,
// changing this to a Fprintf(os.Stderr) and running make.bash generates
// thousands of warnings.
func (s *debugState) unexpected(v *Value, msg string, args ...interface{}) {
s.f.Logf("unexpected at "+fmt.Sprint(v.ID)+":"+msg, args...)
}
func (s *debugState) logf(msg string, args ...interface{}) {
s.f.Logf(msg, args...)
}
type debugState struct {
loggingEnabled bool
slots []*LocalSlot
varSlots []*LocalSlot
f *Func
cache *Cache
numRegisters int
// working storage for BuildFuncDebug, reused between blocks.
registerContents [][]SlotID
}
// getHomeSlot returns the SlotID of the home slot for v, adding to s.slots
// if necessary.
func (s *debugState) getHomeSlot(v *Value) SlotID {
home := s.f.getHome(v.ID).(LocalSlot)
for id, slot := range s.slots {
if *slot == home {
return SlotID(id)
}
}
// This slot wasn't in the NamedValue table so it needs to be added.
s.slots = append(s.slots, &home)
return SlotID(len(s.slots) - 1)
}
func (s *debugState) BlockString(b *BlockDebug) string {
f := &FuncDebug{
Slots: s.slots,
VarSlots: s.varSlots,
Registers: s.f.Config.registers,
}
return f.BlockString(b)
}
// BuildFuncDebug returns debug information for f.
// f must be fully processed, so that each Value is where it will be when
// machine code is emitted.
func BuildFuncDebug(f *Func, loggingEnabled bool) *FuncDebug {
if f.RegAlloc == nil {
f.Fatalf("BuildFuncDebug on func %v that has not been fully processed", f)
}
state := &debugState{
loggingEnabled: loggingEnabled,
slots: make([]*LocalSlot, len(f.Names)),
cache: f.Cache,
f: f,
numRegisters: len(f.Config.registers),
registerContents: make([][]SlotID, len(f.Config.registers)),
}
// TODO: consider storing this in Cache and reusing across functions.
valueNames := make([][]SlotID, f.NumValues())
for i, slot := range f.Names {
slot := slot
state.slots[i] = &slot
if isSynthetic(&slot) {
continue
}
for _, value := range f.NamedValues[slot] {
valueNames[value.ID] = append(valueNames[value.ID], SlotID(i))
}
}
// state.varSlots is never changed, and state.slots is only appended to,
// so aliasing is safe.
state.varSlots = state.slots
if state.loggingEnabled {
var names []string
for i, name := range f.Names {
names = append(names, fmt.Sprintf("%d = %s", i, name))
}
state.logf("Name table: %v\n", strings.Join(names, ", "))
}
// Build up block states, starting with the first block, then
// processing blocks once their predecessors have been processed.
// Location list entries for each block.
blockLocs := make([]*BlockDebug, f.NumBlocks())
// Reverse postorder: visit a block after as many as possible of its
// predecessors have been visited.
po := f.Postorder()
for i := len(po) - 1; i >= 0; i-- {
b := po[i]
// Build the starting state for the block from the final
// state of its predecessors.
locs := state.mergePredecessors(b, blockLocs)
if state.loggingEnabled {
state.logf("Processing %v, initial locs %v, regs %v\n", b, state.BlockString(locs), state.registerContents)
}
// Update locs/registers with the effects of each Value.
// The location list generated here needs to be slightly adjusted for use by gdb.
// These adjustments are applied in genssa.
for _, v := range b.Values {
slots := valueNames[v.ID]
// Loads and stores inherit the names of their sources.
var source *Value
switch v.Op {
case OpStoreReg:
source = v.Args[0]
case OpLoadReg:
switch a := v.Args[0]; a.Op {
case OpArg:
source = a
case OpStoreReg:
source = a.Args[0]
default:
state.unexpected(v, "load with unexpected source op %v", a)
}
}
if source != nil {
slots = append(slots, valueNames[source.ID]...)
// As of writing, the compiler never uses a load/store as a
// source of another load/store, so there's no reason this should
// ever be consulted. Update just in case, and so that when
// valueNames is cached, we can reuse the memory.
valueNames[v.ID] = slots
}
if len(slots) == 0 {
continue
}
reg, _ := f.getHome(v.ID).(*Register)
state.processValue(locs, v, slots, reg)
}
// The block is done; mark any live locations as ending with the block.
for _, locList := range locs.Variables {
last := locList.last()
if last == nil || last.End != nil {
continue
}
last.End = BlockEnd
}
if state.loggingEnabled {
f.Logf("Block done: locs %v, regs %v\n", state.BlockString(locs), state.registerContents)
}
blockLocs[b.ID] = locs
}
info := &FuncDebug{
Slots: state.slots,
VarSlots: state.varSlots,
Registers: f.Config.registers,
}
// Consumers want the information in textual order, not by block ID.
for _, b := range f.Blocks {
info.Blocks = append(info.Blocks, blockLocs[b.ID])
}
if state.loggingEnabled {
f.Logf("Final result:\n")
for slot := range info.VarSlots {
f.Logf("\t%v => %v\n", info.Slots[slot], info.SlotLocsString(SlotID(slot)))
}
}
return info
}
// isSynthetic reports whether if slot represents a compiler-inserted variable,
// e.g. an autotmp or an anonymous return value that needed a stack slot.
func isSynthetic(slot *LocalSlot) bool {
c := slot.String()[0]
return c == '.' || c == '~'
}
// mergePredecessors takes the end state of each of b's predecessors and
// intersects them to form the starting state for b.
// The registers slice (the second return value) will be reused for each call to mergePredecessors.
func (state *debugState) mergePredecessors(b *Block, blockLocs []*BlockDebug) *BlockDebug {
live := make([]VarLocList, len(state.slots))
// Filter out back branches.
var preds []*Block
for _, pred := range b.Preds {
if blockLocs[pred.b.ID] != nil {
preds = append(preds, pred.b)
}
}
if len(preds) > 0 {
p := preds[0]
for slot, locList := range blockLocs[p.ID].Variables {
last := locList.last()
if last == nil || last.End != BlockEnd {
continue
}
loc := state.cache.NewVarLoc()
loc.Start = BlockStart
loc.OnStack = last.OnStack
loc.StackLocation = last.StackLocation
loc.Registers = last.Registers
live[slot].append(loc)
}
}
if state.loggingEnabled && len(b.Preds) > 1 {
state.logf("Starting merge with state from %v: %v\n", b.Preds[0].b, state.BlockString(blockLocs[b.Preds[0].b.ID]))
}
for i := 1; i < len(preds); i++ {
p := preds[i]
if state.loggingEnabled {
state.logf("Merging in state from %v: %v &= %v\n", p, live, state.BlockString(blockLocs[p.ID]))
}
for slot, liveVar := range live {
liveLoc := liveVar.last()
if liveLoc == nil {
continue
}
predLoc := blockLocs[p.ID].Variables[SlotID(slot)].last()
// Clear out slots missing/dead in p.
if predLoc == nil || predLoc.End != BlockEnd {
live[slot].Locations = nil
continue
}
// Unify storage locations.
if !liveLoc.OnStack || !predLoc.OnStack || liveLoc.StackLocation != predLoc.StackLocation {
liveLoc.OnStack = false
liveLoc.StackLocation = 0
}
liveLoc.Registers &= predLoc.Registers
}
}
// Create final result.
locs := &BlockDebug{Variables: live}
if state.loggingEnabled {
locs.Block = b
}
for reg := range state.registerContents {
state.registerContents[reg] = state.registerContents[reg][:0]
}
for slot, locList := range live {
loc := locList.last()
if loc == nil {
continue
}
for reg := 0; reg < state.numRegisters; reg++ {
if loc.Registers&(1<<uint8(reg)) != 0 {
state.registerContents[reg] = append(state.registerContents[reg], SlotID(slot))
}
}
}
return locs
}
// processValue updates locs and state.registerContents to reflect v, a value with
// the names in vSlots and homed in vReg. "v" becomes visible after execution of
// the instructions evaluating it.
func (state *debugState) processValue(locs *BlockDebug, v *Value, vSlots []SlotID, vReg *Register) {
switch {
case v.Op == OpRegKill:
if state.loggingEnabled {
existingSlots := make([]bool, len(state.slots))
for _, slot := range state.registerContents[vReg.num] {
existingSlots[slot] = true
}
for _, slot := range vSlots {
if existingSlots[slot] {
existingSlots[slot] = false
} else {
state.unexpected(v, "regkill of unassociated name %v\n", state.slots[slot])
}
}
for slot, live := range existingSlots {
if live {
state.unexpected(v, "leftover register name: %v\n", state.slots[slot])
}
}
}
state.registerContents[vReg.num] = nil
for _, slot := range vSlots {
last := locs.lastLoc(slot)
if last == nil {
state.unexpected(v, "regkill of already dead %s, %+v\n", vReg, state.slots[slot])
continue
}
if state.loggingEnabled {
state.logf("at %v: %v regkilled out of %s\n", v.ID, state.slots[slot], vReg)
}
if last.End != nil {
state.unexpected(v, "regkill of dead slot, died at %v\n", last.End)
}
last.End = v
regs := last.Registers &^ (1 << uint8(vReg.num))
if !last.OnStack && regs == 0 {
continue
}
loc := state.cache.NewVarLoc()
loc.Start = v
loc.OnStack = last.OnStack
loc.StackLocation = last.StackLocation
loc.Registers = regs
locs.append(slot, loc)
}
case v.Op == OpArg:
for _, slot := range vSlots {
if last := locs.lastLoc(slot); last != nil {
state.unexpected(v, "Arg op on already-live slot %v", state.slots[slot])
last.End = v
}
loc := state.cache.NewVarLoc()
loc.Start = v
loc.OnStack = true
loc.StackLocation = state.getHomeSlot(v)
locs.append(slot, loc)
if state.loggingEnabled {
state.logf("at %v: arg %v now on stack in location %v\n", v.ID, state.slots[slot], state.slots[loc.StackLocation])
}
}
case v.Op == OpStoreReg:
for _, slot := range vSlots {
last := locs.lastLoc(slot)
if last == nil {
state.unexpected(v, "spill of unnamed register %s\n", vReg)
break
}
last.End = v
loc := state.cache.NewVarLoc()
loc.Start = v
loc.OnStack = true
loc.StackLocation = state.getHomeSlot(v)
loc.Registers = last.Registers
locs.append(slot, loc)
if state.loggingEnabled {
state.logf("at %v: %v spilled to stack location %v\n", v.ID, state.slots[slot], state.slots[loc.StackLocation])
}
}
case vReg != nil:
if state.loggingEnabled {
newSlots := make([]bool, len(state.slots))
for _, slot := range vSlots {
newSlots[slot] = true
}
for _, slot := range state.registerContents[vReg.num] {
if !newSlots[slot] {
state.unexpected(v, "%v clobbered\n", state.slots[slot])
}
}
}
for _, slot := range vSlots {
if state.loggingEnabled {
state.logf("at %v: %v now in %s\n", v.ID, state.slots[slot], vReg)
}
last := locs.lastLoc(slot)
if last != nil && last.End == nil {
last.End = v
}
state.registerContents[vReg.num] = append(state.registerContents[vReg.num], slot)
loc := state.cache.NewVarLoc()
loc.Start = v
if last != nil {
loc.OnStack = last.OnStack
loc.StackLocation = last.StackLocation
loc.Registers = last.Registers
}
loc.Registers |= 1 << uint8(vReg.num)
locs.append(slot, loc)
}
default:
state.unexpected(v, "named value with no reg\n")
}
}