cmd/compile: output DWARF lexical blocks for local variables

Change compiler and linker to emit DWARF lexical blocks in .debug_info
section when compiling with -N -l.

Version of debug_info is updated from DWARF v2 to DWARF v3 since
version 2 does not allow lexical blocks with discontinuous PC ranges.

Remaining open problems:
- scope information is removed from inlined functions
- variables records do not have DW_AT_start_scope attributes so a
variable will shadow other variables with the same name as soon as its
containing scope begins, even before its declaration.

Updates #6913.
Updates #12899.

Change-Id: Idc6808788512ea20e7e45bcf782453acb416fb49
Reviewed-on: https://go-review.googlesource.com/40095
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

7 files changed, 184 insertions, 49 deletions

diff --git a/src/cmd/internal/dwarf/dwarf.go b/src/cmd/internal/dwarf/dwarf.go
index 042a79b5a6..2974bf5092 100644
--- a/src/cmd/internal/dwarf/dwarf.go
+++ b/src/cmd/internal/dwarf/dwarf.go
@@ -8,14 +8,19 @@
 package dwarf
 
 import (
+	"errors"
 	"fmt"
 )
 
 // InfoPrefix is the prefix for all the symbols containing DWARF info entries.
 const InfoPrefix = "go.info."
 
+// RangePrefix is the prefix for all the symbols containing DWARF range lists.
+const RangePrefix = "go.range."
+
 // Sym represents a symbol.
 type Sym interface {
+	Len() int64
 }
 
 // A Var represents a local variable or a function parameter.
@@ -23,9 +28,62 @@ type Var struct {
 	Name   string
 	Abbrev int // Either DW_ABRV_AUTO or DW_ABRV_PARAM
 	Offset int32
+	Scope  int32
 	Type   Sym
 }
 
+// A Scope represents a lexical scope. All variables declared within a
+// scope will only be visible to instructions covered by the scope.
+// Lexical scopes are contiguous in source files but can end up being
+// compiled to discontiguous blocks of instructions in the executable.
+// The Ranges field lists all the blocks of instructions that belong
+// in this scope.
+type Scope struct {
+	Parent int32
+	Ranges []Range
+	Vars   []*Var
+}
+
+// A Range represents a half-open interval [Start, End).
+type Range struct {
+	Start, End int64
+}
+
+// UnifyRanges merges the list of ranges of c into the list of ranges of s
+func (s *Scope) UnifyRanges(c *Scope) {
+	out := make([]Range, 0, len(s.Ranges)+len(c.Ranges))
+
+	i, j := 0, 0
+	for {
+		var cur Range
+		if i < len(s.Ranges) && j < len(c.Ranges) {
+			if s.Ranges[i].Start < c.Ranges[j].Start {
+				cur = s.Ranges[i]
+				i++
+			} else {
+				cur = c.Ranges[j]
+				j++
+			}
+		} else if i < len(s.Ranges) {
+			cur = s.Ranges[i]
+			i++
+		} else if j < len(c.Ranges) {
+			cur = c.Ranges[j]
+			j++
+		} else {
+			break
+		}
+
+		if n := len(out); n > 0 && cur.Start <= out[n-1].End {
+			out[n-1].End = cur.End
+		} else {
+			out = append(out, cur)
+		}
+	}
+
+	s.Ranges = out
+}
+
 // A Context specifies how to add data to a Sym.
 type Context interface {
 	PtrSize() int
@@ -156,6 +214,8 @@ const (
 	DW_ABRV_VARIABLE
 	DW_ABRV_AUTO
 	DW_ABRV_PARAM
+	DW_ABRV_LEXICAL_BLOCK_RANGES
+	DW_ABRV_LEXICAL_BLOCK_SIMPLE
 	DW_ABRV_STRUCTFIELD
 	DW_ABRV_FUNCTYPEPARAM
 	DW_ABRV_DOTDOTDOT
@@ -247,6 +307,25 @@ var abbrevs = [DW_NABRV]dwAbbrev{
 		},
 	},
 
+	/* LEXICAL_BLOCK_RANGES */
+	{
+		DW_TAG_lexical_block,
+		DW_CHILDREN_yes,
+		[]dwAttrForm{
+			{DW_AT_ranges, DW_FORM_data4}, // replace with DW_FORM_sec_offset in DWARFv4.
+		},
+	},
+
+	/* LEXICAL_BLOCK_SIMPLE */
+	{
+		DW_TAG_lexical_block,
+		DW_CHILDREN_yes,
+		[]dwAttrForm{
+			{DW_AT_low_pc, DW_FORM_addr},
+			{DW_AT_high_pc, DW_FORM_addr},
+		},
+	},
+
 	/* STRUCTFIELD */
 	{
 		DW_TAG_member,
@@ -525,8 +604,8 @@ func putattr(ctxt Context, s Sym, abbrev int, form int, cls int, value int64, da
 		ctxt.AddInt(s, 2, value)
 
 	case DW_FORM_data4: // constant, {line,loclist,mac,rangelist}ptr
-		if cls == DW_CLS_PTR { // DW_AT_stmt_list
-			ctxt.AddSectionOffset(s, 4, data, 0)
+		if cls == DW_CLS_PTR { // DW_AT_stmt_list and DW_AT_ranges
+			ctxt.AddSectionOffset(s, 4, data, value)
 			break
 		}
 		ctxt.AddInt(s, 4, value)
@@ -555,15 +634,13 @@ func putattr(ctxt Context, s Sym, abbrev int, form int, cls int, value int64, da
 			ctxt.AddInt(s, 1, 0)
 		}
 
-	// In DWARF 2 (which is what we claim to generate),
-	// the ref_addr is the same size as a normal address.
-	// In DWARF 3 it is always 32 bits, unless emitting a large
+	// In DWARF 3 the ref_addr is always 32 bits, unless emitting a large
 	// (> 4 GB of debug info aka "64-bit") unit, which we don't implement.
 	case DW_FORM_ref_addr: // reference to a DIE in the .info section
 		if data == nil {
 			return fmt.Errorf("dwarf: null reference in %d", abbrev)
 		} else {
-			ctxt.AddSectionOffset(s, ctxt.PtrSize(), data, 0)
+			ctxt.AddSectionOffset(s, 4, data, 0)
 		}
 
 	case DW_FORM_ref1, // reference within the compilation unit
@@ -606,7 +683,7 @@ func HasChildren(die *DWDie) bool {
 
 // PutFunc writes a DIE for a function to s.
 // It also writes child DIEs for each variable in vars.
-func PutFunc(ctxt Context, s Sym, name string, external bool, startPC Sym, size int64, vars []*Var) {
+func PutFunc(ctxt Context, s, ranges Sym, name string, external bool, startPC Sym, size int64, scopes []Scope) error {
 	Uleb128put(ctxt, s, DW_ABRV_FUNCTION)
 	putattr(ctxt, s, DW_ABRV_FUNCTION, DW_FORM_string, DW_CLS_STRING, int64(len(name)), name)
 	putattr(ctxt, s, DW_ABRV_FUNCTION, DW_FORM_addr, DW_CLS_ADDRESS, 0, startPC)
@@ -616,29 +693,67 @@ func PutFunc(ctxt Context, s Sym, name string, external bool, startPC Sym, size
 		ev = 1
 	}
 	putattr(ctxt, s, DW_ABRV_FUNCTION, DW_FORM_flag, DW_CLS_FLAG, ev, 0)
-	names := make(map[string]bool)
-	var encbuf [20]byte
-	for _, v := range vars {
-		var n string
-		if names[v.Name] {
-			n = fmt.Sprintf("%s#%d", v.Name, len(names))
-		} else {
-			n = v.Name
+	if len(scopes) > 0 {
+		var encbuf [20]byte
+		if putscope(ctxt, s, ranges, startPC, 0, scopes, encbuf[:0]) < int32(len(scopes)) {
+			return errors.New("multiple toplevel scopes")
 		}
-		names[n] = true
+	}
+
+	Uleb128put(ctxt, s, 0)
+	return nil
+}
 
-		Uleb128put(ctxt, s, int64(v.Abbrev))
-		putattr(ctxt, s, v.Abbrev, DW_FORM_string, DW_CLS_STRING, int64(len(n)), n)
-		loc := append(encbuf[:0], DW_OP_call_frame_cfa)
-		if v.Offset != 0 {
-			loc = append(loc, DW_OP_consts)
-			loc = AppendSleb128(loc, int64(v.Offset))
-			loc = append(loc, DW_OP_plus)
+func putscope(ctxt Context, s, ranges Sym, startPC Sym, curscope int32, scopes []Scope, encbuf []byte) int32 {
+	for _, v := range scopes[curscope].Vars {
+		putvar(ctxt, s, v, encbuf)
+	}
+	this := curscope
+	curscope++
+	for curscope < int32(len(scopes)) {
+		scope := scopes[curscope]
+		if scope.Parent != this {
+			return curscope
 		}
-		putattr(ctxt, s, v.Abbrev, DW_FORM_block1, DW_CLS_BLOCK, int64(len(loc)), loc)
-		putattr(ctxt, s, v.Abbrev, DW_FORM_ref_addr, DW_CLS_REFERENCE, 0, v.Type)
+
+		if len(scope.Ranges) == 1 {
+			Uleb128put(ctxt, s, DW_ABRV_LEXICAL_BLOCK_SIMPLE)
+			putattr(ctxt, s, DW_ABRV_LEXICAL_BLOCK_SIMPLE, DW_FORM_addr, DW_CLS_ADDRESS, scope.Ranges[0].Start, startPC)
+			putattr(ctxt, s, DW_ABRV_LEXICAL_BLOCK_SIMPLE, DW_FORM_addr, DW_CLS_ADDRESS, scope.Ranges[0].End, startPC)
+		} else {
+			Uleb128put(ctxt, s, DW_ABRV_LEXICAL_BLOCK_RANGES)
+			putattr(ctxt, s, DW_ABRV_LEXICAL_BLOCK_RANGES, DW_FORM_data4, DW_CLS_PTR, ranges.Len(), ranges)
+
+			ctxt.AddAddress(ranges, nil, -1)
+			ctxt.AddAddress(ranges, startPC, 0)
+			for _, r := range scope.Ranges {
+				ctxt.AddAddress(ranges, nil, r.Start)
+				ctxt.AddAddress(ranges, nil, r.End)
+			}
+			ctxt.AddAddress(ranges, nil, 0)
+			ctxt.AddAddress(ranges, nil, 0)
+		}
+
+		curscope = putscope(ctxt, s, ranges, startPC, curscope, scopes, encbuf)
+
+		Uleb128put(ctxt, s, 0)
 	}
-	Uleb128put(ctxt, s, 0)
+	return curscope
+}
+
+func putvar(ctxt Context, s Sym, v *Var, encbuf []byte) {
+	n := v.Name
+
+	Uleb128put(ctxt, s, int64(v.Abbrev))
+	putattr(ctxt, s, v.Abbrev, DW_FORM_string, DW_CLS_STRING, int64(len(n)), n)
+	loc := append(encbuf[:0], DW_OP_call_frame_cfa)
+	if v.Offset != 0 {
+		loc = append(loc, DW_OP_consts)
+		loc = AppendSleb128(loc, int64(v.Offset))
+		loc = append(loc, DW_OP_plus)
+	}
+	putattr(ctxt, s, v.Abbrev, DW_FORM_block1, DW_CLS_BLOCK, int64(len(loc)), loc)
+	putattr(ctxt, s, v.Abbrev, DW_FORM_ref_addr, DW_CLS_REFERENCE, 0, v.Type)
 }
 
 // VarsByOffset attaches the methods of sort.Interface to []*Var,
diff --git a/src/cmd/internal/obj/data.go b/src/cmd/internal/obj/data.go
index 8b1bdb1056..23d1809e0c 100644
--- a/src/cmd/internal/obj/data.go
+++ b/src/cmd/internal/obj/data.go
@@ -120,7 +120,8 @@ func (s *LSym) WriteInt(ctxt *Link, off int64, siz int, i int64) {
 // WriteAddr writes an address of size siz into s at offset off.
 // rsym and roff specify the relocation for the address.
 func (s *LSym) WriteAddr(ctxt *Link, off int64, siz int, rsym *LSym, roff int64) {
-	if siz != ctxt.Arch.PtrSize {
+	// Allow 4-byte addresses for DWARF.
+	if siz != ctxt.Arch.PtrSize && siz != 4 {
 		ctxt.Diag("WriteAddr: bad address size %d in %s", siz, s.Name)
 	}
 	s.prepwrite(ctxt, off, siz)
diff --git a/src/cmd/internal/obj/link.go b/src/cmd/internal/obj/link.go
index 8bdc3f55e9..d49bc8c564 100644
--- a/src/cmd/internal/obj/link.go
+++ b/src/cmd/internal/obj/link.go
@@ -324,12 +324,15 @@ type LSym struct {
 
 // A FuncInfo contains extra fields for STEXT symbols.
 type FuncInfo struct {
-	Args     int32
-	Locals   int32
-	Text     *Prog
-	Autom    []*Auto
-	Pcln     Pcln
-	dwarfSym *LSym
+	Args   int32
+	Locals int32
+	Text   *Prog
+	Autom  []*Auto
+	Pcln   Pcln
+
+	dwarfSym       *LSym
+	dwarfRangesSym *LSym
+
 	GCArgs   LSym
 	GCLocals LSym
 }
@@ -490,7 +493,7 @@ type Link struct {
 	InlTree       InlTree // global inlining tree used by gc/inl.go
 	Imports       []string
 	DiagFunc      func(string, ...interface{})
-	DebugInfo     func(fn *LSym, curfn interface{}) []*dwarf.Var // if non-nil, curfn is a *gc.Node
+	DebugInfo     func(fn *LSym, curfn interface{}) []dwarf.Scope // if non-nil, curfn is a *gc.Node
 	Errors        int
 
 	Framepointer_enabled bool
diff --git a/src/cmd/internal/obj/objfile.go b/src/cmd/internal/obj/objfile.go
index dc22eacdf4..e309c5f7e7 100644
--- a/src/cmd/internal/obj/objfile.go
+++ b/src/cmd/internal/obj/objfile.go
@@ -447,10 +447,14 @@ func (c dwCtxt) SymValue(s dwarf.Sym) int64 {
 	return 0
 }
 func (c dwCtxt) AddAddress(s dwarf.Sym, data interface{}, value int64) {
-	rsym := data.(*LSym)
 	ls := s.(*LSym)
 	size := c.PtrSize()
-	ls.WriteAddr(c.Link, ls.Size, size, rsym, value)
+	if data != nil {
+		rsym := data.(*LSym)
+		ls.WriteAddr(c.Link, ls.Size, size, rsym, value)
+	} else {
+		ls.WriteInt(c.Link, ls.Size, size, value)
+	}
 }
 func (c dwCtxt) AddSectionOffset(s dwarf.Sym, size int, t interface{}, ofs int64) {
 	ls := s.(*LSym)
@@ -460,27 +464,35 @@ func (c dwCtxt) AddSectionOffset(s dwarf.Sym, size int, t interface{}, ofs int64
 	r.Type = objabi.R_DWARFREF
 }
 
-// dwarfSym returns the DWARF symbol for TEXT symbol.
-func (ctxt *Link) dwarfSym(s *LSym) *LSym {
+// dwarfSym returns the DWARF symbols for TEXT symbol.
+func (ctxt *Link) dwarfSym(s *LSym) (dwarfInfoSym, dwarfRangesSym *LSym) {
 	if s.Type != objabi.STEXT {
 		ctxt.Diag("dwarfSym of non-TEXT %v", s)
 	}
 	if s.Func.dwarfSym == nil {
 		s.Func.dwarfSym = ctxt.LookupDerived(s, dwarf.InfoPrefix+s.Name)
+		s.Func.dwarfRangesSym = ctxt.LookupDerived(s, dwarf.RangePrefix+s.Name)
 	}
-	return s.Func.dwarfSym
+	return s.Func.dwarfSym, s.Func.dwarfRangesSym
 }
 
-// populateDWARF fills in the DWARF Debugging Information Entry for TEXT symbol s.
-// The DWARF symbol must already have been initialized in InitTextSym.
+func (s *LSym) Len() int64 {
+	return s.Size
+}
+
+// populateDWARF fills in the DWARF Debugging Information Entries for TEXT symbol s.
+// The DWARFs symbol must already have been initialized in InitTextSym.
 func (ctxt *Link) populateDWARF(curfn interface{}, s *LSym) {
-	dsym := ctxt.dwarfSym(s)
+	dsym, drsym := ctxt.dwarfSym(s)
 	if dsym.Size != 0 {
 		ctxt.Diag("makeFuncDebugEntry double process %v", s)
 	}
-	var vars []*dwarf.Var
+	var scopes []dwarf.Scope
 	if ctxt.DebugInfo != nil {
-		vars = ctxt.DebugInfo(s, curfn)
+		scopes = ctxt.DebugInfo(s, curfn)
+	}
+	err := dwarf.PutFunc(dwCtxt{ctxt}, dsym, drsym, s.Name, !s.Static(), s, s.Size, scopes)
+	if err != nil {
+		ctxt.Diag("emitting DWARF for %s failed: %v", s.Name, err)
 	}
-	dwarf.PutFunc(dwCtxt{ctxt}, dsym, s.Name, !s.Static(), s, s.Size, vars)
 }
diff --git a/src/cmd/internal/obj/plist.go b/src/cmd/internal/obj/plist.go
index 5c86c20e73..861da88703 100644
--- a/src/cmd/internal/obj/plist.go
+++ b/src/cmd/internal/obj/plist.go
@@ -135,11 +135,14 @@ func (ctxt *Link) InitTextSym(s *LSym, flag int) {
 	s.Type = objabi.STEXT
 	ctxt.Text = append(ctxt.Text, s)
 
-	// Set up DWARF entry for s.
-	dsym := ctxt.dwarfSym(s)
+	// Set up DWARF entries for s.
+	dsym, drsym := ctxt.dwarfSym(s)
 	dsym.Type = objabi.SDWARFINFO
 	dsym.Set(AttrDuplicateOK, s.DuplicateOK())
+	drsym.Type = objabi.SDWARFRANGE
+	drsym.Set(AttrDuplicateOK, s.DuplicateOK())
 	ctxt.Data = append(ctxt.Data, dsym)
+	ctxt.Data = append(ctxt.Data, drsym)
 
 	// Set up the function's gcargs and gclocals.
 	// They will be filled in later if needed.
diff --git a/src/cmd/internal/objabi/symkind.go b/src/cmd/internal/objabi/symkind.go
index 62a7efd964..b037e9e4ed 100644
--- a/src/cmd/internal/objabi/symkind.go
+++ b/src/cmd/internal/objabi/symkind.go
@@ -56,4 +56,5 @@ const (
 	STLSBSS
 	// Debugging data
 	SDWARFINFO
+	SDWARFRANGE
 )
diff --git a/src/cmd/internal/objabi/symkind_string.go b/src/cmd/internal/objabi/symkind_string.go
index aabcfd2d54..5123dc7097 100644
--- a/src/cmd/internal/objabi/symkind_string.go
+++ b/src/cmd/internal/objabi/symkind_string.go
@@ -4,9 +4,9 @@ package objabi
 
 import "fmt"
 
-const _SymKind_name = "SxxxSTEXTSRODATASNOPTRDATASDATASBSSSNOPTRBSSSTLSBSSSDWARFINFO"
+const _SymKind_name = "SxxxSTEXTSRODATASNOPTRDATASDATASBSSSNOPTRBSSSTLSBSSSDWARFINFOSDWARFRANGE"
 
-var _SymKind_index = [...]uint8{0, 4, 9, 16, 26, 31, 35, 44, 51, 61}
+var _SymKind_index = [...]uint8{0, 4, 9, 16, 26, 31, 35, 44, 51, 61, 72}
 
 func (i SymKind) String() string {
 	if i >= SymKind(len(_SymKind_index)-1) {