Home | History | Annotate | Download | only in gc 
      1 // Copyright 2017 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 gc
      6 
      7 import (
      8 	"cmd/internal/dwarf"
      9 	"cmd/internal/obj"
     10 	"cmd/internal/src"
     11 	"sort"
     12 )
     13 
     14 // See golang.org/issue/20390.
     15 func xposBefore(p, q src.XPos) bool {
     16 	return Ctxt.PosTable.Pos(p).Before(Ctxt.PosTable.Pos(q))
     17 }
     18 
     19 func findScope(marks []Mark, pos src.XPos) ScopeID {
     20 	i := sort.Search(len(marks), func(i int) bool {
     21 		return xposBefore(pos, marks[i].Pos)
     22 	})
     23 	if i == 0 {
     24 		return 0
     25 	}
     26 	return marks[i-1].Scope
     27 }
     28 
     29 func assembleScopes(fnsym *obj.LSym, fn *Node, dwarfVars []*dwarf.Var, varScopes []ScopeID) []dwarf.Scope {
     30 	// Initialize the DWARF scope tree based on lexical scopes.
     31 	dwarfScopes := make([]dwarf.Scope, 1+len(fn.Func.Parents))
     32 	for i, parent := range fn.Func.Parents {
     33 		dwarfScopes[i+1].Parent = int32(parent)
     34 	}
     35 
     36 	scopeVariables(dwarfVars, varScopes, dwarfScopes)
     37 	scopePCs(fnsym, fn.Func.Marks, dwarfScopes)
     38 	return compactScopes(dwarfScopes)
     39 }
     40 
     41 // scopeVariables assigns DWARF variable records to their scopes.
     42 func scopeVariables(dwarfVars []*dwarf.Var, varScopes []ScopeID, dwarfScopes []dwarf.Scope) {
     43 	sort.Stable(varsByScopeAndOffset{dwarfVars, varScopes})
     44 
     45 	i0 := 0
     46 	for i := range dwarfVars {
     47 		if varScopes[i] == varScopes[i0] {
     48 			continue
     49 		}
     50 		dwarfScopes[varScopes[i0]].Vars = dwarfVars[i0:i]
     51 		i0 = i
     52 	}
     53 	if i0 < len(dwarfVars) {
     54 		dwarfScopes[varScopes[i0]].Vars = dwarfVars[i0:]
     55 	}
     56 }
     57 
     58 // A scopedPCs represents a non-empty half-open interval of PCs that
     59 // share a common source position.
     60 type scopedPCs struct {
     61 	start, end int64
     62 	pos        src.XPos
     63 	scope      ScopeID
     64 }
     65 
     66 // scopePCs assigns PC ranges to their scopes.
     67 func scopePCs(fnsym *obj.LSym, marks []Mark, dwarfScopes []dwarf.Scope) {
     68 	// If there aren't any child scopes (in particular, when scope
     69 	// tracking is disabled), we can skip a whole lot of work.
     70 	if len(marks) == 0 {
     71 		return
     72 	}
     73 
     74 	// Break function text into scopedPCs.
     75 	var pcs []scopedPCs
     76 	p0 := fnsym.Func.Text
     77 	for p := fnsym.Func.Text; p != nil; p = p.Link {
     78 		if p.Pos == p0.Pos {
     79 			continue
     80 		}
     81 		if p0.Pc < p.Pc {
     82 			pcs = append(pcs, scopedPCs{start: p0.Pc, end: p.Pc, pos: p0.Pos})
     83 		}
     84 		p0 = p
     85 	}
     86 	if p0.Pc < fnsym.Size {
     87 		pcs = append(pcs, scopedPCs{start: p0.Pc, end: fnsym.Size, pos: p0.Pos})
     88 	}
     89 
     90 	// Sort PCs by source position, and walk in parallel with
     91 	// scope marks to assign a lexical scope to each PC interval.
     92 	sort.Sort(pcsByPos(pcs))
     93 	var marki int
     94 	var scope ScopeID
     95 	for i := range pcs {
     96 		for marki < len(marks) && !xposBefore(pcs[i].pos, marks[marki].Pos) {
     97 			scope = marks[marki].Scope
     98 			marki++
     99 		}
    100 		pcs[i].scope = scope
    101 	}
    102 
    103 	// Re-sort to create sorted PC ranges for each DWARF scope.
    104 	sort.Sort(pcsByPC(pcs))
    105 	for _, pc := range pcs {
    106 		r := &dwarfScopes[pc.scope].Ranges
    107 		if i := len(*r); i > 0 && (*r)[i-1].End == pc.start {
    108 			(*r)[i-1].End = pc.end
    109 		} else {
    110 			*r = append(*r, dwarf.Range{Start: pc.start, End: pc.end})
    111 		}
    112 	}
    113 }
    114 
    115 func compactScopes(dwarfScopes []dwarf.Scope) []dwarf.Scope {
    116 	// Forward pass to collapse empty scopes into parents.
    117 	remap := make([]int32, len(dwarfScopes))
    118 	j := int32(1)
    119 	for i := 1; i < len(dwarfScopes); i++ {
    120 		s := &dwarfScopes[i]
    121 		s.Parent = remap[s.Parent]
    122 		if len(s.Vars) == 0 {
    123 			dwarfScopes[s.Parent].UnifyRanges(s)
    124 			remap[i] = s.Parent
    125 			continue
    126 		}
    127 		remap[i] = j
    128 		dwarfScopes[j] = *s
    129 		j++
    130 	}
    131 	dwarfScopes = dwarfScopes[:j]
    132 
    133 	// Reverse pass to propagate PC ranges to parent scopes.
    134 	for i := len(dwarfScopes) - 1; i > 0; i-- {
    135 		s := &dwarfScopes[i]
    136 		dwarfScopes[s.Parent].UnifyRanges(s)
    137 	}
    138 
    139 	return dwarfScopes
    140 }
    141 
    142 type pcsByPC []scopedPCs
    143 
    144 func (s pcsByPC) Len() int      { return len(s) }
    145 func (s pcsByPC) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
    146 func (s pcsByPC) Less(i, j int) bool {
    147 	return s[i].start < s[j].start
    148 }
    149 
    150 type pcsByPos []scopedPCs
    151 
    152 func (s pcsByPos) Len() int      { return len(s) }
    153 func (s pcsByPos) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
    154 func (s pcsByPos) Less(i, j int) bool {
    155 	return xposBefore(s[i].pos, s[j].pos)
    156 }
    157 
    158 type varsByScopeAndOffset struct {
    159 	vars   []*dwarf.Var
    160 	scopes []ScopeID
    161 }
    162 
    163 func (v varsByScopeAndOffset) Len() int {
    164 	return len(v.vars)
    165 }
    166 
    167 func (v varsByScopeAndOffset) Less(i, j int) bool {
    168 	if v.scopes[i] != v.scopes[j] {
    169 		return v.scopes[i] < v.scopes[j]
    170 	}
    171 	return v.vars[i].StackOffset < v.vars[j].StackOffset
    172 }
    173 
    174 func (v varsByScopeAndOffset) Swap(i, j int) {
    175 	v.vars[i], v.vars[j] = v.vars[j], v.vars[i]
    176 	v.scopes[i], v.scopes[j] = v.scopes[j], v.scopes[i]
    177 }
    178