cmd/compile: output DWARF lexical blocks for local variables

Change compiler and linker to emit DWARF lexical blocks in debug_info.
Version of debug_info is updated from DWARF v.2 to DWARF v.3 since version 2
does not allow lexical blocks with discontinuous ranges.

Second attempt at https://go-review.googlesource.com/#/c/29591/

Remaining open problems:
- scope information is removed from inlined functions
- variables in debug_info 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, before its declaration.

Updates golang/go#12899, golang/go#6913

Change-Id: I0e260a45b564d14a87b88974eb16c5387cb410a5
Reviewed-on: https://go-review.googlesource.com/36879
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

5 files changed, 215 insertions, 34 deletions

diff --git a/src/cmd/internal/dwarf/dwarf.go b/src/cmd/internal/dwarf/dwarf.go
index 7625149914..da419d8574 100644
--- a/src/cmd/internal/dwarf/dwarf.go
+++ b/src/cmd/internal/dwarf/dwarf.go
@@ -8,14 +8,20 @@
 package dwarf
 
 import (
+	"cmd/internal/src"
+	"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.
@@ -26,6 +32,63 @@ type Var struct {
 	Type   Sym
 }
 
+// A Scope represents a lexical scope, all variables contained in 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 {
+	src.Scope
+	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 len(out) == 0 {
+			out = append(out, cur)
+		} else {
+			last := &out[len(out)-1]
+			if cur.Start > last.End {
+				out = append(out, cur)
+			} else if cur.End > last.End {
+				last.End = cur.End
+			}
+		}
+	}
+
+	s.Ranges = out
+}
+
 // A Context specifies how to add data to a Sym.
 type Context interface {
 	PtrSize() int
@@ -153,6 +216,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
@@ -243,6 +308,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,
@@ -520,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)
@@ -550,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
@@ -601,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)
@@ -611,29 +693,72 @@ 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 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)
+}
+
+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
+		}
+
+		emptyscope := len(scope.Vars) == 0 || len(scope.Ranges) == 0
+
+		if !emptyscope {
+			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 _, pcrange := range scope.Ranges {
+					ctxt.AddAddress(ranges, nil, pcrange.Start)
+					ctxt.AddAddress(ranges, nil, pcrange.End)
+				}
+				ctxt.AddAddress(ranges, nil, 0)
+				ctxt.AddAddress(ranges, nil, 0)
+			}
+		}
+
+		curscope = putscope(ctxt, s, ranges, startPC, curscope, scopes, encbuf)
+
+		if !emptyscope {
+			Uleb128put(ctxt, s, 0)
 		}
-		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)
 	}
-	Uleb128put(ctxt, s, 0)
+	return curscope
 }
 
 // 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 114841dedb..7a19e3a38c 100644
--- a/src/cmd/internal/obj/data.go
+++ b/src/cmd/internal/obj/data.go
@@ -114,7 +114,7 @@ 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 {
+	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 fd07851f3b..e08d7a0340 100644
--- a/src/cmd/internal/obj/link.go
+++ b/src/cmd/internal/obj/link.go
@@ -483,6 +483,7 @@ const (
 	SHOSTOBJ
 	SDWARFSECT
 	SDWARFINFO
+	SDWARFRANGE
 	SSUB       = SymKind(1 << 8)
 	SMASK      = SymKind(SSUB - 1)
 	SHIDDEN    = SymKind(1 << 9)
@@ -739,7 +740,7 @@ type Link struct {
 	Armsize       int32
 	Pc            int64
 	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
 	Cursym        *LSym
 	Version       int
 	Errors        int
diff --git a/src/cmd/internal/obj/objfile.go b/src/cmd/internal/obj/objfile.go
index 6858143674..314c7a9de6 100644
--- a/src/cmd/internal/obj/objfile.go
+++ b/src/cmd/internal/obj/objfile.go
@@ -542,10 +542,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)
@@ -555,6 +559,10 @@ func (c dwCtxt) AddSectionOffset(s dwarf.Sym, size int, t interface{}, ofs int64
 	r.Type = R_DWARFREF
 }
 
+func (s *LSym) Len() int64 {
+	return s.Size
+}
+
 // makeFuncDebugEntry makes a DWARF Debugging Information Entry
 // for TEXT symbol s.
 func makeFuncDebugEntry(ctxt *Link, curfn interface{}, s *LSym) {
@@ -564,10 +572,21 @@ func makeFuncDebugEntry(ctxt *Link, curfn interface{}, s *LSym) {
 	}
 	dsym.Type = SDWARFINFO
 	dsym.Set(AttrDuplicateOK, s.DuplicateOK())
-	var vars []*dwarf.Var
+
+	drsym := ctxt.Lookup(dwarf.RangePrefix+s.Name, int(s.Version))
+	if drsym.Size != 0 {
+		return
+	}
+	drsym.Type = SDWARFRANGE
+	drsym.Set(AttrDuplicateOK, s.DuplicateOK())
+
+	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.Version == 0, 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.Version == 0, s, s.Size, vars)
-	ctxt.Data = append(ctxt.Data, dsym)
+	ctxt.Data = append(ctxt.Data, dsym, drsym)
 }
diff --git a/src/cmd/internal/src/scope.go b/src/cmd/internal/src/scope.go
new file mode 100644
index 0000000000..d9ca1f5bfa
--- /dev/null
+++ b/src/cmd/internal/src/scope.go
@@ -0,0 +1,36 @@
+// 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 src
+
+// Scope represents a lexical scope.
+type Scope struct {
+	Start, End XPos
+	Parent     int32
+}
+
+// Scopes represents a tree of lexical scopes
+type Scopes struct {
+	Scopes   []Scope // lexical scopes
+	curscope int32   // current scope index (during noding)
+}
+
+// Open starts a new scope, scopes.Curscope is the parent.
+func (scopes *Scopes) Open(posTable *PosTable, pos Pos) {
+	scope := Scope{Parent: scopes.curscope, Start: NoXPos, End: NoXPos}
+	if pos.IsKnown() {
+		scope.Start = posTable.XPos(pos)
+	}
+	scopes.Scopes = append(scopes.Scopes, scope)
+	scopes.curscope = int32(len(scopes.Scopes) - 1)
+}
+
+// Close ends the current scope.
+func (scopes *Scopes) Close(posTable *PosTable, pos Pos) {
+	scope := &scopes.Scopes[scopes.curscope]
+	if pos.IsKnown() {
+		scope.End = posTable.XPos(pos)
+	}
+	scopes.curscope = scope.Parent
+}