cmd/compile: index line number tables by source file to improve sparsity

This reduces allocations and also resolves some
lurking inliner/inlinee line-number match problems.
However, it does add about 1.5% to compile time.

This fixes compiler OOMs seen compiling some large protobuf-
derived inputs.  For compiling the compiler itself,

compilebench -pkg cmd/compile/internal/ssa -memprofile withcl.prof

the numberlines-related memory consumption is reduced from 129MB
to 29MB (about a 5% overall reduction in allocation).

Additionally modified after going over changes with Austin
to remove unused code (nobody called size()) and correct
the cache-clearing code.

I've attempted to speed this up by not using maps, and have
not succeeded.  I'd rather get correct code in now, speed it
up later if I can.

Updates #27739.
Fixes #29279.

Change-Id: I098005de4e45196a5f5b10c0886a49f88e9f8fd5
Reviewed-on: https://go-review.googlesource.com/c/go/+/154617
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

1 files changed, 21 insertions, 13 deletions

diff --git a/src/cmd/compile/internal/ssa/numberlines.go b/src/cmd/compile/internal/ssa/numberlines.go
index 9bdb357d35..6ff337ce6f 100644
--- a/src/cmd/compile/internal/ssa/numberlines.go
+++ b/src/cmd/compile/internal/ssa/numberlines.go
@@ -7,7 +7,6 @@ package ssa
 import (
 	"cmd/internal/obj"
 	"cmd/internal/src"
-	"math"
 )
 
 func isPoorStatementOp(op Op) bool {
@@ -51,7 +50,7 @@ func nextGoodStatementIndex(v *Value, i int, b *Block) int {
 		if b.Values[j].Pos.IsStmt() == src.PosNotStmt { // ignore non-statements
 			continue
 		}
-		if b.Values[j].Pos.Line() == v.Pos.Line() {
+		if b.Values[j].Pos.Line() == v.Pos.Line() && v.Pos.SameFile(b.Values[j].Pos) {
 			return j
 		}
 		return i
@@ -86,14 +85,22 @@ func (b *Block) FirstPossibleStmtValue() *Value {
 func numberLines(f *Func) {
 	po := f.Postorder()
 	endlines := make(map[ID]src.XPos)
-	last := uint(0)              // uint follows type of XPos.Line()
-	first := uint(math.MaxInt32) // unsigned, but large valid int when cast
-	note := func(line uint) {
-		if line < first {
-			first = line
+	ranges := make(map[int]lineRange)
+	note := func(p src.XPos) {
+		line := uint32(p.Line())
+		i := int(p.FileIndex())
+		lp, found := ranges[i]
+		change := false
+		if line < lp.first || !found {
+			lp.first = line
+			change = true
 		}
-		if line > last {
-			last = line
+		if line > lp.last {
+			lp.last = line
+			change = true
+		}
+		if change {
+			ranges[i] = lp
 		}
 	}
 
@@ -104,12 +111,12 @@ func numberLines(f *Func) {
 		firstPos := src.NoXPos
 		firstPosIndex := -1
 		if b.Pos.IsStmt() != src.PosNotStmt {
-			note(b.Pos.Line())
+			note(b.Pos)
 		}
 		for i := 0; i < len(b.Values); i++ {
 			v := b.Values[i]
 			if v.Pos.IsStmt() != src.PosNotStmt {
-				note(v.Pos.Line())
+				note(v.Pos)
 				// skip ahead to better instruction for this line if possible
 				i = nextGoodStatementIndex(v, i, b)
 				v = b.Values[i]
@@ -161,7 +168,7 @@ func numberLines(f *Func) {
 			if v.Pos.IsStmt() == src.PosNotStmt {
 				continue
 			}
-			note(v.Pos.Line())
+			note(v.Pos)
 			// skip ahead if possible
 			i = nextGoodStatementIndex(v, i, b)
 			v = b.Values[i]
@@ -178,5 +185,6 @@ func numberLines(f *Func) {
 		}
 		endlines[b.ID] = firstPos
 	}
-	f.cachedLineStarts = newBiasedSparseMap(int(first), int(last))
+	// cachedLineStarts is an empty sparse map for values that are included within ranges.
+	f.cachedLineStarts = newXposmap(ranges)
 }