From ee59c06acb1cd0a119667fce57988801d3fdde4f Mon Sep 17 00:00:00 2001
From: Keith Randall <khr@google.com>
Date: Mon, 29 Apr 2019 12:19:30 -0700
Subject: [PATCH] cmd/compile: evaluate map initializers incrementally

For the code:

m := map[int]int {
  a(): b(),
  c(): d(),
  e(): f(),
}

We used to do:

t1 := a()
t2 := b()
t3 := c()
t4 := d()
t5 := e()
t6 := f()
m := map[int]int{}
m[t1] = t2
m[t3] = t4
m[t5] = t6

After this CL we do:

m := map[int]int{}
t1 := a()
t2 := b()
m[t1] = t2
t3 := c()
t4 := d()
m[t3] = t4
t5 := e()
t6 := f()
m[t5] = t6

Ordering the initialization this way limits the lifetime of the
temporaries involved.  In particular, for large maps the number of
simultaneously live temporaries goes from ~2*len(m) to ~2. This change
makes the compiler (regalloc, mostly) a lot happier. The compiler runs
faster and uses a lot less memory.

For #26546, changes compile time of a big map from 8 sec to 0.5 sec.

Fixes #26552

Update #26546

Change-Id: Ib7d202dead3feaf493a464779fd9611c63fcc25f
Reviewed-on: https://go-review.googlesource.com/c/go/+/174417
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
---
 src/cmd/compile/internal/gc/order.go | 52 ++++++++++++++++++++++++++++
 src/cmd/compile/internal/gc/sinit.go |  5 +++
 2 files changed, 57 insertions(+)

diff --git a/src/cmd/compile/internal/gc/order.go b/src/cmd/compile/internal/gc/order.go
index fd89254479..54e4a15681 100644
--- a/src/cmd/compile/internal/gc/order.go
+++ b/src/cmd/compile/internal/gc/order.go
@@ -1239,6 +1239,58 @@ func (o *Order) expr(n, lhs *Node) *Node {
 			n.Left = o.addrTemp(n.Left)
 			n.Right = o.addrTemp(n.Right)
 		}
+	case OMAPLIT:
+		// Order map by converting:
+		//   map[int]int{
+		//     a(): b(),
+		//     c(): d(),
+		//     e(): f(),
+		//   }
+		// to
+		//   m := map[int]int{}
+		//   m[a()] = b()
+		//   m[c()] = d()
+		//   m[e()] = f()
+		// Then order the result.
+		// Without this special case, order would otherwise compute all
+		// the keys and values before storing any of them to the map.
+		// See issue 26552.
+		entries := n.List.Slice()
+		statics := entries[:0]
+		var dynamics []*Node
+		for _, r := range entries {
+			if r.Op != OKEY {
+				Fatalf("OMAPLIT entry not OKEY: %v\n", r)
+			}
+			if isStaticCompositeLiteral(r.Left) && isStaticCompositeLiteral(r.Right) {
+				statics = append(statics, r)
+			} else {
+				dynamics = append(dynamics, r)
+			}
+		}
+		n.List.Set(statics)
+
+		// Note: we don't need to recursively call order on the statics.
+		// But do it anyway, just in case that's not true in the future.
+		o.exprList(n.List)
+
+		if len(dynamics) == 0 {
+			break
+		}
+
+		// Emit the creation of the map (with all its static entries).
+		m := o.newTemp(n.Type, false)
+		as := nod(OAS, m, n)
+		typecheck(as, ctxStmt)
+		o.stmt(as)
+		n = m
+
+		// Emit eval+insert of dynamic entries, one at a time.
+		for _, r := range dynamics {
+			as := nod(OAS, nod(OINDEX, n, r.Left), r.Right)
+			typecheck(as, ctxStmt) // Note: this converts the OINDEX to an OINDEXMAP
+			o.stmt(as)
+		}
 	}
 
 	lineno = lno
diff --git a/src/cmd/compile/internal/gc/sinit.go b/src/cmd/compile/internal/gc/sinit.go
index 6666e8bb5e..60183b9a32 100644
--- a/src/cmd/compile/internal/gc/sinit.go
+++ b/src/cmd/compile/internal/gc/sinit.go
@@ -1080,6 +1080,11 @@ func anylit(n *Node, var_ *Node, init *Nodes) {
 	default:
 		Fatalf("anylit: not lit, op=%v node=%v", n.Op, n)
 
+	case ONAME:
+		a := nod(OAS, var_, n)
+		a = typecheck(a, ctxStmt)
+		init.Append(a)
+
 	case OPTRLIT:
 		if !t.IsPtr() {
 			Fatalf("anylit: not ptr")
-- 
2.48.1