summaryrefslogtreecommitdiffstats
path: root/src/cmd/compile/internal/pkginit
diff options
context:
space:
mode:
Diffstat (limited to 'src/cmd/compile/internal/pkginit')
-rw-r--r--src/cmd/compile/internal/pkginit/init.go212
-rw-r--r--src/cmd/compile/internal/pkginit/initAsanGlobals.go241
-rw-r--r--src/cmd/compile/internal/pkginit/initorder.go377
3 files changed, 830 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..e13a7fb
--- /dev/null
+++ b/src/cmd/compile/internal/pkginit/init.go
@@ -0,0 +1,212 @@
+// 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/noder"
+ "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, 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())
+ }
+ if base.Flag.ASan {
+ // Make an initialization function to call runtime.asanregisterglobals to register an
+ // array of instrumented global variables when -asan is enabled. An instrumented global
+ // variable is described by a structure.
+ // See the _asan_global structure declared in src/runtime/asan/asan.go.
+ //
+ // func init {
+ // var globals []_asan_global {...}
+ // asanregisterglobals(&globals[0], len(globals))
+ // }
+ for _, n := range typecheck.Target.Externs {
+ if canInstrumentGlobal(n) {
+ name := n.Sym().Name
+ InstrumentGlobalsMap[name] = n
+ InstrumentGlobalsSlice = append(InstrumentGlobalsSlice, n)
+ }
+ }
+ ni := len(InstrumentGlobalsMap)
+ if ni != 0 {
+ // Make an init._ function.
+ base.Pos = base.AutogeneratedPos
+ typecheck.DeclContext = ir.PEXTERN
+ name := noder.Renameinit()
+ fnInit := typecheck.DeclFunc(name, nil, nil, nil)
+
+ // Get an array of intrumented global variables.
+ globals := instrumentGlobals(fnInit)
+
+ // Call runtime.asanregisterglobals function to poison redzones.
+ // runtime.asanregisterglobals(unsafe.Pointer(&globals[0]), ni)
+ asanf := typecheck.NewName(ir.Pkgs.Runtime.Lookup("asanregisterglobals"))
+ ir.MarkFunc(asanf)
+ asanf.SetType(types.NewSignature(types.NoPkg, nil, nil, []*types.Field{
+ types.NewField(base.Pos, nil, types.Types[types.TUNSAFEPTR]),
+ types.NewField(base.Pos, nil, types.Types[types.TUINTPTR]),
+ }, nil))
+ asancall := ir.NewCallExpr(base.Pos, ir.OCALL, asanf, nil)
+ asancall.Args.Append(typecheck.ConvNop(typecheck.NodAddr(
+ ir.NewIndexExpr(base.Pos, globals, ir.NewInt(0))), types.Types[types.TUNSAFEPTR]))
+ asancall.Args.Append(typecheck.ConvNop(ir.NewInt(int64(ni)), types.Types[types.TUINTPTR]))
+
+ fnInit.Body.Append(asancall)
+ typecheck.FinishFuncBody()
+ typecheck.Func(fnInit)
+ ir.CurFunc = fnInit
+ typecheck.Stmts(fnInit.Body)
+ ir.CurFunc = nil
+
+ typecheck.Target.Decls = append(typecheck.Target.Decls, fnInit)
+ typecheck.Target.Inits = append(typecheck.Target.Inits, fnInit)
+ }
+ }
+
+ // 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.Path != "main" && types.LocalPkg.Path != "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
+}
+
+// initRequiredForCoverage returns TRUE if we need to force creation
+// of an init function for the package so as to insert a coverage
+// runtime registration call.
+func initRequiredForCoverage(l []ir.Node) bool {
+ if base.Flag.Cfg.CoverageInfo == nil {
+ return false
+ }
+ for _, n := range l {
+ if n.Op() == ir.ODCLFUNC {
+ return true
+ }
+ }
+ return false
+}
diff --git a/src/cmd/compile/internal/pkginit/initAsanGlobals.go b/src/cmd/compile/internal/pkginit/initAsanGlobals.go
new file mode 100644
index 0000000..63aa361
--- /dev/null
+++ b/src/cmd/compile/internal/pkginit/initAsanGlobals.go
@@ -0,0 +1,241 @@
+// Copyright 2022 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 (
+ "strings"
+
+ "cmd/compile/internal/base"
+ "cmd/compile/internal/ir"
+ "cmd/compile/internal/typecheck"
+ "cmd/compile/internal/types"
+ "cmd/internal/src"
+)
+
+// instrumentGlobals declares a global array of _asan_global structures and initializes it.
+func instrumentGlobals(fn *ir.Func) *ir.Name {
+ asanGlobalStruct, asanLocationStruct, defStringstruct := createtypes()
+ lname := typecheck.Lookup
+ tconv := typecheck.ConvNop
+ // Make a global array of asanGlobalStruct type.
+ // var asanglobals []asanGlobalStruct
+ arraytype := types.NewArray(asanGlobalStruct, int64(len(InstrumentGlobalsMap)))
+ symG := lname(".asanglobals")
+ globals := typecheck.NewName(symG)
+ globals.SetType(arraytype)
+ globals.Class = ir.PEXTERN
+ symG.Def = globals
+ typecheck.Target.Externs = append(typecheck.Target.Externs, globals)
+ // Make a global array of asanLocationStruct type.
+ // var asanL []asanLocationStruct
+ arraytype = types.NewArray(asanLocationStruct, int64(len(InstrumentGlobalsMap)))
+ symL := lname(".asanL")
+ asanlocation := typecheck.NewName(symL)
+ asanlocation.SetType(arraytype)
+ asanlocation.Class = ir.PEXTERN
+ symL.Def = asanlocation
+ typecheck.Target.Externs = append(typecheck.Target.Externs, asanlocation)
+ // Make three global string variables to pass the global name and module name
+ // and the name of the source file that defines it.
+ // var asanName string
+ // var asanModulename string
+ // var asanFilename string
+ symL = lname(".asanName")
+ asanName := typecheck.NewName(symL)
+ asanName.SetType(types.Types[types.TSTRING])
+ asanName.Class = ir.PEXTERN
+ symL.Def = asanName
+ typecheck.Target.Externs = append(typecheck.Target.Externs, asanName)
+
+ symL = lname(".asanModulename")
+ asanModulename := typecheck.NewName(symL)
+ asanModulename.SetType(types.Types[types.TSTRING])
+ asanModulename.Class = ir.PEXTERN
+ symL.Def = asanModulename
+ typecheck.Target.Externs = append(typecheck.Target.Externs, asanModulename)
+
+ symL = lname(".asanFilename")
+ asanFilename := typecheck.NewName(symL)
+ asanFilename.SetType(types.Types[types.TSTRING])
+ asanFilename.Class = ir.PEXTERN
+ symL.Def = asanFilename
+ typecheck.Target.Externs = append(typecheck.Target.Externs, asanFilename)
+
+ var init ir.Nodes
+ var c ir.Node
+ // globals[i].odrIndicator = 0 is the default, no need to set it explicitly here.
+ for i, n := range InstrumentGlobalsSlice {
+ setField := func(f string, val ir.Node, i int) {
+ r := ir.NewAssignStmt(base.Pos, ir.NewSelectorExpr(base.Pos, ir.ODOT,
+ ir.NewIndexExpr(base.Pos, globals, ir.NewInt(int64(i))), lname(f)), val)
+ init.Append(typecheck.Stmt(r))
+ }
+ // globals[i].beg = uintptr(unsafe.Pointer(&n))
+ c = tconv(typecheck.NodAddr(n), types.Types[types.TUNSAFEPTR])
+ c = tconv(c, types.Types[types.TUINTPTR])
+ setField("beg", c, i)
+ // Assign globals[i].size.
+ g := n.(*ir.Name)
+ size := g.Type().Size()
+ c = tconv(ir.NewInt(size), types.Types[types.TUINTPTR])
+ setField("size", c, i)
+ // Assign globals[i].sizeWithRedzone.
+ rzSize := GetRedzoneSizeForGlobal(size)
+ sizeWithRz := rzSize + size
+ c = tconv(ir.NewInt(sizeWithRz), types.Types[types.TUINTPTR])
+ setField("sizeWithRedzone", c, i)
+ // The C string type is terminated by a null character "\0", Go should use three-digit
+ // octal "\000" or two-digit hexadecimal "\x00" to create null terminated string.
+ // asanName = symbol's linkname + "\000"
+ // globals[i].name = (*defString)(unsafe.Pointer(&asanName)).data
+ name := g.Linksym().Name
+ init.Append(typecheck.Stmt(ir.NewAssignStmt(base.Pos, asanName, ir.NewString(name+"\000"))))
+ c = tconv(typecheck.NodAddr(asanName), types.Types[types.TUNSAFEPTR])
+ c = tconv(c, types.NewPtr(defStringstruct))
+ c = ir.NewSelectorExpr(base.Pos, ir.ODOT, c, lname("data"))
+ setField("name", c, i)
+
+ // Set the name of package being compiled as a unique identifier of a module.
+ // asanModulename = pkgName + "\000"
+ init.Append(typecheck.Stmt(ir.NewAssignStmt(base.Pos, asanModulename, ir.NewString(types.LocalPkg.Name+"\000"))))
+ c = tconv(typecheck.NodAddr(asanModulename), types.Types[types.TUNSAFEPTR])
+ c = tconv(c, types.NewPtr(defStringstruct))
+ c = ir.NewSelectorExpr(base.Pos, ir.ODOT, c, lname("data"))
+ setField("moduleName", c, i)
+ // Assign asanL[i].filename, asanL[i].line, asanL[i].column
+ // and assign globals[i].location = uintptr(unsafe.Pointer(&asanL[i]))
+ asanLi := ir.NewIndexExpr(base.Pos, asanlocation, ir.NewInt(int64(i)))
+ filename := ir.NewString(base.Ctxt.PosTable.Pos(n.Pos()).Filename() + "\000")
+ init.Append(typecheck.Stmt(ir.NewAssignStmt(base.Pos, asanFilename, filename)))
+ c = tconv(typecheck.NodAddr(asanFilename), types.Types[types.TUNSAFEPTR])
+ c = tconv(c, types.NewPtr(defStringstruct))
+ c = ir.NewSelectorExpr(base.Pos, ir.ODOT, c, lname("data"))
+ init.Append(typecheck.Stmt(ir.NewAssignStmt(base.Pos, ir.NewSelectorExpr(base.Pos, ir.ODOT, asanLi, lname("filename")), c)))
+ line := ir.NewInt(int64(n.Pos().Line()))
+ init.Append(typecheck.Stmt(ir.NewAssignStmt(base.Pos, ir.NewSelectorExpr(base.Pos, ir.ODOT, asanLi, lname("line")), line)))
+ col := ir.NewInt(int64(n.Pos().Col()))
+ init.Append(typecheck.Stmt(ir.NewAssignStmt(base.Pos, ir.NewSelectorExpr(base.Pos, ir.ODOT, asanLi, lname("column")), col)))
+ c = tconv(typecheck.NodAddr(asanLi), types.Types[types.TUNSAFEPTR])
+ c = tconv(c, types.Types[types.TUINTPTR])
+ setField("sourceLocation", c, i)
+ }
+ fn.Body.Append(init...)
+ return globals
+}
+
+// createtypes creates the asanGlobal, asanLocation and defString struct type.
+// Go compiler does not refer to the C types, we represent the struct field
+// by a uintptr, then use type conversion to make copies of the data.
+// E.g., (*defString)(asanGlobal.name).data to C string.
+//
+// Keep in sync with src/runtime/asan/asan.go.
+// type asanGlobal struct {
+// beg uintptr
+// size uintptr
+// size_with_redzone uintptr
+// name uintptr
+// moduleName uintptr
+// hasDynamicInit uintptr
+// sourceLocation uintptr
+// odrIndicator uintptr
+// }
+//
+// type asanLocation struct {
+// filename uintptr
+// line int32
+// column int32
+// }
+//
+// defString is synthesized struct type meant to capture the underlying
+// implementations of string.
+// type defString struct {
+// data uintptr
+// len uintptr
+// }
+
+func createtypes() (*types.Type, *types.Type, *types.Type) {
+ up := types.Types[types.TUINTPTR]
+ i32 := types.Types[types.TINT32]
+ fname := typecheck.Lookup
+ nxp := src.NoXPos
+ nfield := types.NewField
+ asanGlobal := types.NewStruct(types.NoPkg, []*types.Field{
+ nfield(nxp, fname("beg"), up),
+ nfield(nxp, fname("size"), up),
+ nfield(nxp, fname("sizeWithRedzone"), up),
+ nfield(nxp, fname("name"), up),
+ nfield(nxp, fname("moduleName"), up),
+ nfield(nxp, fname("hasDynamicInit"), up),
+ nfield(nxp, fname("sourceLocation"), up),
+ nfield(nxp, fname("odrIndicator"), up),
+ })
+ types.CalcSize(asanGlobal)
+
+ asanLocation := types.NewStruct(types.NoPkg, []*types.Field{
+ nfield(nxp, fname("filename"), up),
+ nfield(nxp, fname("line"), i32),
+ nfield(nxp, fname("column"), i32),
+ })
+ types.CalcSize(asanLocation)
+
+ defString := types.NewStruct(types.NoPkg, []*types.Field{
+ types.NewField(nxp, fname("data"), up),
+ types.NewField(nxp, fname("len"), up),
+ })
+ types.CalcSize(defString)
+
+ return asanGlobal, asanLocation, defString
+}
+
+// Calculate redzone for globals.
+func GetRedzoneSizeForGlobal(size int64) int64 {
+ maxRZ := int64(1 << 18)
+ minRZ := int64(32)
+ redZone := (size / minRZ / 4) * minRZ
+ switch {
+ case redZone > maxRZ:
+ redZone = maxRZ
+ case redZone < minRZ:
+ redZone = minRZ
+ }
+ // Round up to multiple of minRZ.
+ if size%minRZ != 0 {
+ redZone += minRZ - (size % minRZ)
+ }
+ return redZone
+}
+
+// InstrumentGlobalsMap contains only package-local (and unlinknamed from somewhere else)
+// globals.
+// And the key is the object name. For example, in package p, a global foo would be in this
+// map as "foo".
+// Consider range over maps is nondeterministic, make a slice to hold all the values in the
+// InstrumentGlobalsMap and iterate over the InstrumentGlobalsSlice.
+var InstrumentGlobalsMap = make(map[string]ir.Node)
+var InstrumentGlobalsSlice = make([]ir.Node, 0, 0)
+
+func canInstrumentGlobal(g ir.Node) bool {
+ if g.Op() != ir.ONAME {
+ return false
+ }
+ n := g.(*ir.Name)
+ if n.Class == ir.PFUNC {
+ return false
+ }
+ if n.Sym().Pkg != types.LocalPkg {
+ return false
+ }
+ // Do not instrument any _cgo_ related global variables, because they are declared in C code.
+ if strings.Contains(n.Sym().Name, "cgo") {
+ return false
+ }
+
+ // Do not instrument globals that are linknamed, because their home package will do the work.
+ if n.Sym().Linkname != "" {
+ return false
+ }
+
+ return true
+}
diff --git a/src/cmd/compile/internal/pkginit/initorder.go b/src/cmd/compile/internal/pkginit/initorder.go
new file mode 100644
index 0000000..426d298
--- /dev/null
+++ b/src/cmd/compile/internal/pkginit/initorder.go
@@ -0,0 +1,377 @@
+// 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 (
+ "container/heap"
+ "fmt"
+ "strings"
+
+ "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 strings.Builder
+ 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
+ }
+
+ // Treat coverage counter variables effectively as invisible with
+ // respect to init order. If we don't do this, then the
+ // instrumentation vars can perturb the order of initialization
+ // away from the order of the original uninstrumented program.
+ // See issue #56293 for more details.
+ if n.CoverageCounter() || n.CoverageAuxVar() {
+ 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
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-01 19:13:20 +0000