2 files changed, 512 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/pkginit/init.go b/src/cmd/compile/internal/pkginit/init.go
new file mode 100644
index 0000000..40f1408
--- /dev/null
+++ b/src/cmd/compile/internal/pkginit/init.go
@@ -0,0 +1,144 @@
+// Copyright 2009 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 pkginit
+
+import (
+	"cmd/compile/internal/base"
+	"cmd/compile/internal/ir"
+	"cmd/compile/internal/objw"
+	"cmd/compile/internal/staticinit"
+	"cmd/compile/internal/typecheck"
+	"cmd/compile/internal/types"
+	"cmd/internal/obj"
+	"cmd/internal/src"
+)
+
+// MakeInit creates a synthetic init function to handle any
+// package-scope initialization statements.
+//
+// TODO(mdempsky): Move into noder, so that the types2-based frontends
+// can use Info.InitOrder instead.
+func MakeInit() {
+	nf := initOrder(typecheck.Target.Decls)
+	if len(nf) == 0 {
+		return
+	}
+
+	// Make a function that contains all the initialization statements.
+	base.Pos = nf[0].Pos() // prolog/epilog gets line number of first init stmt
+	initializers := typecheck.Lookup("init")
+	fn := typecheck.DeclFunc(initializers, ir.NewFuncType(base.Pos, nil, nil, nil))
+	for _, dcl := range typecheck.InitTodoFunc.Dcl {
+		dcl.Curfn = fn
+	}
+	fn.Dcl = append(fn.Dcl, typecheck.InitTodoFunc.Dcl...)
+	typecheck.InitTodoFunc.Dcl = nil
+
+	// Suppress useless "can inline" diagnostics.
+	// Init functions are only called dynamically.
+	fn.SetInlinabilityChecked(true)
+
+	fn.Body = nf
+	typecheck.FinishFuncBody()
+
+	typecheck.Func(fn)
+	ir.WithFunc(fn, func() {
+		typecheck.Stmts(nf)
+	})
+	typecheck.Target.Decls = append(typecheck.Target.Decls, fn)
+
+	// Prepend to Inits, so it runs first, before any user-declared init
+	// functions.
+	typecheck.Target.Inits = append([]*ir.Func{fn}, typecheck.Target.Inits...)
+
+	if typecheck.InitTodoFunc.Dcl != nil {
+		// We only generate temps using InitTodoFunc if there
+		// are package-scope initialization statements, so
+		// something's weird if we get here.
+		base.Fatalf("InitTodoFunc still has declarations")
+	}
+	typecheck.InitTodoFunc = nil
+}
+
+// Task makes and returns an initialization record for the package.
+// See runtime/proc.go:initTask for its layout.
+// The 3 tasks for initialization are:
+//   1) Initialize all of the packages the current package depends on.
+//   2) Initialize all the variables that have initializers.
+//   3) Run any init functions.
+func Task() *ir.Name {
+	var deps []*obj.LSym // initTask records for packages the current package depends on
+	var fns []*obj.LSym  // functions to call for package initialization
+
+	// Find imported packages with init tasks.
+	for _, pkg := range typecheck.Target.Imports {
+		n := typecheck.Resolve(ir.NewIdent(base.Pos, pkg.Lookup(".inittask")))
+		if n.Op() == ir.ONONAME {
+			continue
+		}
+		if n.Op() != ir.ONAME || n.(*ir.Name).Class != ir.PEXTERN {
+			base.Fatalf("bad inittask: %v", n)
+		}
+		deps = append(deps, n.(*ir.Name).Linksym())
+	}
+
+	// Record user init functions.
+	for _, fn := range typecheck.Target.Inits {
+		if fn.Sym().Name == "init" {
+			// Synthetic init function for initialization of package-scope
+			// variables. We can use staticinit to optimize away static
+			// assignments.
+			s := staticinit.Schedule{
+				Plans: make(map[ir.Node]*staticinit.Plan),
+				Temps: make(map[ir.Node]*ir.Name),
+			}
+			for _, n := range fn.Body {
+				s.StaticInit(n)
+			}
+			fn.Body = s.Out
+			ir.WithFunc(fn, func() {
+				typecheck.Stmts(fn.Body)
+			})
+
+			if len(fn.Body) == 0 {
+				fn.Body = []ir.Node{ir.NewBlockStmt(src.NoXPos, nil)}
+			}
+		}
+
+		// Skip init functions with empty bodies.
+		if len(fn.Body) == 1 {
+			if stmt := fn.Body[0]; stmt.Op() == ir.OBLOCK && len(stmt.(*ir.BlockStmt).List) == 0 {
+				continue
+			}
+		}
+		fns = append(fns, fn.Nname.Linksym())
+	}
+
+	if len(deps) == 0 && len(fns) == 0 && types.LocalPkg.Name != "main" && types.LocalPkg.Name != "runtime" {
+		return nil // nothing to initialize
+	}
+
+	// Make an .inittask structure.
+	sym := typecheck.Lookup(".inittask")
+	task := typecheck.NewName(sym)
+	task.SetType(types.Types[types.TUINT8]) // fake type
+	task.Class = ir.PEXTERN
+	sym.Def = task
+	lsym := task.Linksym()
+	ot := 0
+	ot = objw.Uintptr(lsym, ot, 0) // state: not initialized yet
+	ot = objw.Uintptr(lsym, ot, uint64(len(deps)))
+	ot = objw.Uintptr(lsym, ot, uint64(len(fns)))
+	for _, d := range deps {
+		ot = objw.SymPtr(lsym, ot, d, 0)
+	}
+	for _, f := range fns {
+		ot = objw.SymPtr(lsym, ot, f, 0)
+	}
+	// An initTask has pointers, but none into the Go heap.
+	// It's not quite read only, the state field must be modifiable.
+	objw.Global(lsym, int32(ot), obj.NOPTR)
+	return task
+}
diff --git a/src/cmd/compile/internal/pkginit/initorder.go b/src/cmd/compile/internal/pkginit/initorder.go
new file mode 100644
index 0000000..a509753
--- /dev/null
+++ b/src/cmd/compile/internal/pkginit/initorder.go
@@ -0,0 +1,368 @@
+// Copyright 2019 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 pkginit
+
+import (
+	"bytes"
+	"container/heap"
+	"fmt"
+
+	"cmd/compile/internal/base"
+	"cmd/compile/internal/ir"
+)
+
+// Package initialization
+//
+// Here we implement the algorithm for ordering package-level variable
+// initialization. The spec is written in terms of variable
+// initialization, but multiple variables initialized by a single
+// assignment are handled together, so here we instead focus on
+// ordering initialization assignments. Conveniently, this maps well
+// to how we represent package-level initializations using the Node
+// AST.
+//
+// Assignments are in one of three phases: NotStarted, Pending, or
+// Done. For assignments in the Pending phase, we use Xoffset to
+// record the number of unique variable dependencies whose
+// initialization assignment is not yet Done. We also maintain a
+// "blocking" map that maps assignments back to all of the assignments
+// that depend on it.
+//
+// For example, for an initialization like:
+//
+//     var x = f(a, b, b)
+//     var a, b = g()
+//
+// the "x = f(a, b, b)" assignment depends on two variables (a and b),
+// so its Xoffset will be 2. Correspondingly, the "a, b = g()"
+// assignment's "blocking" entry will have two entries back to x's
+// assignment.
+//
+// Logically, initialization works by (1) taking all NotStarted
+// assignments, calculating their dependencies, and marking them
+// Pending; (2) adding all Pending assignments with Xoffset==0 to a
+// "ready" priority queue (ordered by variable declaration position);
+// and (3) iteratively processing the next Pending assignment from the
+// queue, decreasing the Xoffset of assignments it's blocking, and
+// adding them to the queue if decremented to 0.
+//
+// As an optimization, we actually apply each of these three steps for
+// each assignment. This yields the same order, but keeps queue size
+// down and thus also heap operation costs.
+
+// Static initialization phase.
+// These values are stored in two bits in Node.flags.
+const (
+	InitNotStarted = iota
+	InitDone
+	InitPending
+)
+
+type InitOrder struct {
+	// blocking maps initialization assignments to the assignments
+	// that depend on it.
+	blocking map[ir.Node][]ir.Node
+
+	// ready is the queue of Pending initialization assignments
+	// that are ready for initialization.
+	ready declOrder
+
+	order map[ir.Node]int
+}
+
+// initOrder computes initialization order for a list l of
+// package-level declarations (in declaration order) and outputs the
+// corresponding list of statements to include in the init() function
+// body.
+func initOrder(l []ir.Node) []ir.Node {
+	var res ir.Nodes
+	o := InitOrder{
+		blocking: make(map[ir.Node][]ir.Node),
+		order:    make(map[ir.Node]int),
+	}
+
+	// Process all package-level assignment in declaration order.
+	for _, n := range l {
+		switch n.Op() {
+		case ir.OAS, ir.OAS2DOTTYPE, ir.OAS2FUNC, ir.OAS2MAPR, ir.OAS2RECV:
+			o.processAssign(n)
+			o.flushReady(func(n ir.Node) { res.Append(n) })
+		case ir.ODCLCONST, ir.ODCLFUNC, ir.ODCLTYPE:
+			// nop
+		default:
+			base.Fatalf("unexpected package-level statement: %v", n)
+		}
+	}
+
+	// Check that all assignments are now Done; if not, there must
+	// have been a dependency cycle.
+	for _, n := range l {
+		switch n.Op() {
+		case ir.OAS, ir.OAS2DOTTYPE, ir.OAS2FUNC, ir.OAS2MAPR, ir.OAS2RECV:
+			if o.order[n] != orderDone {
+				// If there have already been errors
+				// printed, those errors may have
+				// confused us and there might not be
+				// a loop. Let the user fix those
+				// first.
+				base.ExitIfErrors()
+
+				o.findInitLoopAndExit(firstLHS(n), new([]*ir.Name), new(ir.NameSet))
+				base.Fatalf("initialization unfinished, but failed to identify loop")
+			}
+		}
+	}
+
+	// Invariant consistency check. If this is non-zero, then we
+	// should have found a cycle above.
+	if len(o.blocking) != 0 {
+		base.Fatalf("expected empty map: %v", o.blocking)
+	}
+
+	return res
+}
+
+func (o *InitOrder) processAssign(n ir.Node) {
+	if _, ok := o.order[n]; ok {
+		base.Fatalf("unexpected state: %v, %v", n, o.order[n])
+	}
+	o.order[n] = 0
+
+	// Compute number of variable dependencies and build the
+	// inverse dependency ("blocking") graph.
+	for dep := range collectDeps(n, true) {
+		defn := dep.Defn
+		// Skip dependencies on functions (PFUNC) and
+		// variables already initialized (InitDone).
+		if dep.Class != ir.PEXTERN || o.order[defn] == orderDone {
+			continue
+		}
+		o.order[n]++
+		o.blocking[defn] = append(o.blocking[defn], n)
+	}
+
+	if o.order[n] == 0 {
+		heap.Push(&o.ready, n)
+	}
+}
+
+const orderDone = -1000
+
+// flushReady repeatedly applies initialize to the earliest (in
+// declaration order) assignment ready for initialization and updates
+// the inverse dependency ("blocking") graph.
+func (o *InitOrder) flushReady(initialize func(ir.Node)) {
+	for o.ready.Len() != 0 {
+		n := heap.Pop(&o.ready).(ir.Node)
+		if order, ok := o.order[n]; !ok || order != 0 {
+			base.Fatalf("unexpected state: %v, %v, %v", n, ok, order)
+		}
+
+		initialize(n)
+		o.order[n] = orderDone
+
+		blocked := o.blocking[n]
+		delete(o.blocking, n)
+
+		for _, m := range blocked {
+			if o.order[m]--; o.order[m] == 0 {
+				heap.Push(&o.ready, m)
+			}
+		}
+	}
+}
+
+// findInitLoopAndExit searches for an initialization loop involving variable
+// or function n. If one is found, it reports the loop as an error and exits.
+//
+// path points to a slice used for tracking the sequence of
+// variables/functions visited. Using a pointer to a slice allows the
+// slice capacity to grow and limit reallocations.
+func (o *InitOrder) findInitLoopAndExit(n *ir.Name, path *[]*ir.Name, ok *ir.NameSet) {
+	for i, x := range *path {
+		if x == n {
+			reportInitLoopAndExit((*path)[i:])
+			return
+		}
+	}
+
+	// There might be multiple loops involving n; by sorting
+	// references, we deterministically pick the one reported.
+	refers := collectDeps(n.Defn, false).Sorted(func(ni, nj *ir.Name) bool {
+		return ni.Pos().Before(nj.Pos())
+	})
+
+	*path = append(*path, n)
+	for _, ref := range refers {
+		// Short-circuit variables that were initialized.
+		if ref.Class == ir.PEXTERN && o.order[ref.Defn] == orderDone || ok.Has(ref) {
+			continue
+		}
+
+		o.findInitLoopAndExit(ref, path, ok)
+	}
+
+	// n is not involved in a cycle.
+	// Record that fact to avoid checking it again when reached another way,
+	// or else this traversal will take exponential time traversing all paths
+	// through the part of the package's call graph implicated in the cycle.
+	ok.Add(n)
+
+	*path = (*path)[:len(*path)-1]
+}
+
+// reportInitLoopAndExit reports and initialization loop as an error
+// and exits. However, if l is not actually an initialization loop, it
+// simply returns instead.
+func reportInitLoopAndExit(l []*ir.Name) {
+	// Rotate loop so that the earliest variable declaration is at
+	// the start.
+	i := -1
+	for j, n := range l {
+		if n.Class == ir.PEXTERN && (i == -1 || n.Pos().Before(l[i].Pos())) {
+			i = j
+		}
+	}
+	if i == -1 {
+		// False positive: loop only involves recursive
+		// functions. Return so that findInitLoop can continue
+		// searching.
+		return
+	}
+	l = append(l[i:], l[:i]...)
+
+	// TODO(mdempsky): Method values are printed as "T.m-fm"
+	// rather than "T.m". Figure out how to avoid that.
+
+	var msg bytes.Buffer
+	fmt.Fprintf(&msg, "initialization loop:\n")
+	for _, n := range l {
+		fmt.Fprintf(&msg, "\t%v: %v refers to\n", ir.Line(n), n)
+	}
+	fmt.Fprintf(&msg, "\t%v: %v", ir.Line(l[0]), l[0])
+
+	base.ErrorfAt(l[0].Pos(), msg.String())
+	base.ErrorExit()
+}
+
+// collectDeps returns all of the package-level functions and
+// variables that declaration n depends on. If transitive is true,
+// then it also includes the transitive dependencies of any depended
+// upon functions (but not variables).
+func collectDeps(n ir.Node, transitive bool) ir.NameSet {
+	d := initDeps{transitive: transitive}
+	switch n.Op() {
+	case ir.OAS:
+		n := n.(*ir.AssignStmt)
+		d.inspect(n.Y)
+	case ir.OAS2DOTTYPE, ir.OAS2FUNC, ir.OAS2MAPR, ir.OAS2RECV:
+		n := n.(*ir.AssignListStmt)
+		d.inspect(n.Rhs[0])
+	case ir.ODCLFUNC:
+		n := n.(*ir.Func)
+		d.inspectList(n.Body)
+	default:
+		base.Fatalf("unexpected Op: %v", n.Op())
+	}
+	return d.seen
+}
+
+type initDeps struct {
+	transitive bool
+	seen       ir.NameSet
+	cvisit     func(ir.Node)
+}
+
+func (d *initDeps) cachedVisit() func(ir.Node) {
+	if d.cvisit == nil {
+		d.cvisit = d.visit // cache closure
+	}
+	return d.cvisit
+}
+
+func (d *initDeps) inspect(n ir.Node)      { ir.Visit(n, d.cachedVisit()) }
+func (d *initDeps) inspectList(l ir.Nodes) { ir.VisitList(l, d.cachedVisit()) }
+
+// visit calls foundDep on any package-level functions or variables
+// referenced by n, if any.
+func (d *initDeps) visit(n ir.Node) {
+	switch n.Op() {
+	case ir.ONAME:
+		n := n.(*ir.Name)
+		switch n.Class {
+		case ir.PEXTERN, ir.PFUNC:
+			d.foundDep(n)
+		}
+
+	case ir.OCLOSURE:
+		n := n.(*ir.ClosureExpr)
+		d.inspectList(n.Func.Body)
+
+	case ir.ODOTMETH, ir.OMETHVALUE, ir.OMETHEXPR:
+		d.foundDep(ir.MethodExprName(n))
+	}
+}
+
+// foundDep records that we've found a dependency on n by adding it to
+// seen.
+func (d *initDeps) foundDep(n *ir.Name) {
+	// Can happen with method expressions involving interface
+	// types; e.g., fixedbugs/issue4495.go.
+	if n == nil {
+		return
+	}
+
+	// Names without definitions aren't interesting as far as
+	// initialization ordering goes.
+	if n.Defn == nil {
+		return
+	}
+
+	if d.seen.Has(n) {
+		return
+	}
+	d.seen.Add(n)
+	if d.transitive && n.Class == ir.PFUNC {
+		d.inspectList(n.Defn.(*ir.Func).Body)
+	}
+}
+
+// declOrder implements heap.Interface, ordering assignment statements
+// by the position of their first LHS expression.
+//
+// N.B., the Pos of the first LHS expression is used because because
+// an OAS node's Pos may not be unique. For example, given the
+// declaration "var a, b = f(), g()", "a" must be ordered before "b",
+// but both OAS nodes use the "=" token's position as their Pos.
+type declOrder []ir.Node
+
+func (s declOrder) Len() int { return len(s) }
+func (s declOrder) Less(i, j int) bool {
+	return firstLHS(s[i]).Pos().Before(firstLHS(s[j]).Pos())
+}
+func (s declOrder) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
+
+func (s *declOrder) Push(x interface{}) { *s = append(*s, x.(ir.Node)) }
+func (s *declOrder) Pop() interface{} {
+	n := (*s)[len(*s)-1]
+	*s = (*s)[:len(*s)-1]
+	return n
+}
+
+// firstLHS returns the first expression on the left-hand side of
+// assignment n.
+func firstLHS(n ir.Node) *ir.Name {
+	switch n.Op() {
+	case ir.OAS:
+		n := n.(*ir.AssignStmt)
+		return n.X.Name()
+	case ir.OAS2DOTTYPE, ir.OAS2FUNC, ir.OAS2RECV, ir.OAS2MAPR:
+		n := n.(*ir.AssignListStmt)
+		return n.Lhs[0].Name()
+	}
+
+	base.Fatalf("unexpected Op: %v", n.Op())
+	return nil
+}