internal/refactor/inline/calleefx.go - tools.git - Git at Google

 // Copyright 2023 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 inline

 // This file defines the analysis of callee effects.

 import (
 	"go/ast"
 	"go/token"
 	"go/types"
 )

 const (
 	rinf = -1 //  R∞: arbitrary read from memory
 	winf = -2 //  W∞: arbitrary write to memory (or unknown control)
 )

 // calleefx returns a list of parameter indices indicating the order
 // in which parameters are first referenced during evaluation of the
 // callee, relative both to each other and to other effects of the
 // callee (if any), such as arbitrary reads (rinf) and arbitrary
 // effects (winf), including unknown control flow. Each parameter
 // that is referenced appears once in the list.
 //
 // For example, the effects list of this function:
 //
 //	func f(x, y, z int) int {
 //	    return y + x + g() + z
 //	}
 //
 // is [1 0 -2 2], indicating reads of y and x, followed by the unknown
 // effects of the g() call. and finally the read of parameter z. This
 // information is used during inlining to ascertain when it is safe
 // for parameter references to be replaced by their corresponding
 // argument expressions. Such substitutions are permitted only when
 // they do not cause "write" operations (those with effects) to
 // commute with "read" operations (those that have no effect but are
 // not pure). Impure operations may be reordered with other impure
 // operations, and pure operations may be reordered arbitrarily.
 //
 // The analysis ignores the effects of runtime panics, on the
 // assumption that well-behaved programs shouldn't encounter them.
 func calleefx(info *types.Info, body *ast.BlockStmt, paramInfos map[*types.Var]*paramInfo) []int {
 	// This traversal analyzes the callee's statements (in syntax
 	// form, though one could do better with SSA) to compute the
 	// sequence of events of the following kinds:
 	//
 	// 1  read of a parameter variable.
 	// 2. reads from other memory.
 	// 3. writes to memory

 	var effects []int // indices of parameters, or rinf/winf (-ve)
 	seen := make(map[int]bool)
 	effect := func(i int) {
 		if !seen[i] {
 			seen[i] = true
 			effects = append(effects, i)
 		}
 	}

 	// unknown is called for statements of unknown effects (or control).
 	unknown := func() {
 		effect(winf)

 		// Ensure that all remaining parameters are "seen"
 		// after we go into the unknown (unless they are
 		// unreferenced by the function body). This lets us
 		// not bother implementing the complete traversal into
 		// control structures.
 		//
 		// TODO(adonovan): add them in a deterministic order.
 		// (This is not a bug but determinism is good.)
 		for _, pinfo := range paramInfos {
 			if !pinfo.IsResult && len(pinfo.Refs) > 0 {
 				effect(pinfo.Index)
 			}
 		}
 	}

 	var visitExpr func(n ast.Expr)
 	var visitStmt func(n ast.Stmt) bool
 	visitExpr = func(n ast.Expr) {
 		switch n := n.(type) {
 		case *ast.Ident:
 			if v, ok := info.Uses[n].(*types.Var); ok && !v.IsField() {
 				// Use of global?
 				if v.Parent() == v.Pkg().Scope() {
 					effect(rinf) // read global var
 				}

 				// Use of parameter?
 				if pinfo, ok := paramInfos[v]; ok && !pinfo.IsResult {
 					effect(pinfo.Index) // read parameter var
 				}

 				// Use of local variables is ok.
 			}

 		case *ast.BasicLit:
 			// no effect

 		case *ast.FuncLit:
 			// A func literal has no read or write effect
 			// until called, and (most) function calls are
 			// considered to have arbitrary effects.
 			// So, no effect.

 		case *ast.CompositeLit:
 			for _, elt := range n.Elts {
 				visitExpr(elt) // note: visits KeyValueExpr
 			}

 		case *ast.ParenExpr:
 			visitExpr(n.X)

 		case *ast.SelectorExpr:
 			if seln, ok := info.Selections[n]; ok {
 				visitExpr(n.X)

 				// See types.SelectionKind for background.
 				switch seln.Kind() {
 				case types.MethodExpr:
 					// A method expression T.f acts like a
 					// reference to a func decl,
 					// so it doesn't read x until called.

 				case types.MethodVal, types.FieldVal:
 					// A field or method value selection x.f
 					// reads x if the selection indirects a pointer.

 					if indirectSelection(seln) {
 						effect(rinf)
 					}
 				}
 			} else {
 				// qualified identifier: treat like unqualified
 				visitExpr(n.Sel)
 			}

 		case *ast.IndexExpr:
 			if tv := info.Types[n.Index]; tv.IsType() {
 				// no effect (G[T] instantiation)
 			} else {
 				visitExpr(n.X)
 				visitExpr(n.Index)
 				switch tv.Type.Underlying().(type) {
 				case *types.Slice, *types.Pointer: // []T, *[n]T (not string, [n]T)
 					effect(rinf) // indirect read of slice/array element
 				}
 			}

 		case *ast.IndexListExpr:
 			// no effect (M[K,V] instantiation)

 		case *ast.SliceExpr:
 			visitExpr(n.X)
 			visitExpr(n.Low)
 			visitExpr(n.High)
 			visitExpr(n.Max)

 		case *ast.TypeAssertExpr:
 			visitExpr(n.X)

 		case *ast.CallExpr:
 			if info.Types[n.Fun].IsType() {
 				// conversion T(x)
 				visitExpr(n.Args[0])
 			} else {
 				// call f(args)
 				visitExpr(n.Fun)
 				for i, arg := range n.Args {
 					if i == 0 && info.Types[arg].IsType() {
 						continue // new(T), make(T, n)
 					}
 					visitExpr(arg)
 				}

 				// The pure built-ins have no effects beyond
 				// those of their operands (not even memory reads).
 				// All other calls have unknown effects.
 				if !callsPureBuiltin(info, n) {
 					unknown() // arbitrary effects
 				}
 			}

 		case *ast.StarExpr:
 			visitExpr(n.X)
 			effect(rinf) // *ptr load or store depends on state of heap

 		case *ast.UnaryExpr: // + - ! ^ & ~ <-
 			visitExpr(n.X)
 			if n.Op == token.ARROW {
 				unknown() // effect: channel receive
 			}

 		case *ast.BinaryExpr:
 			visitExpr(n.X)
 			visitExpr(n.Y)

 		case *ast.KeyValueExpr:
 			visitExpr(n.Key) // may be a struct field
 			visitExpr(n.Value)

 		case *ast.BadExpr:
 			// no effect

 		case nil:
 			// optional subtree

 		default:
 			// type syntax: unreachable given traversal
 			panic(n)
 		}
 	}

 	// visitStmt's result indicates the continuation:
 	// false for return, true for the next statement.
 	//
 	// We could treat return as an unknown, but this way
 	// yields definite effects for simple sequences like
 	// {S1; S2; return}, so unreferenced parameters are
 	// not spuriously added to the effects list, and thus
 	// not spuriously disqualified from elimination.
 	visitStmt = func(n ast.Stmt) bool {
 		switch n := n.(type) {
 		case *ast.DeclStmt:
 			decl := n.Decl.(*ast.GenDecl)
 			for _, spec := range decl.Specs {
 				switch spec := spec.(type) {
 				case *ast.ValueSpec:
 					for _, v := range spec.Values {
 						visitExpr(v)
 					}

 				case *ast.TypeSpec:
 					// no effect
 				}
 			}

 		case *ast.LabeledStmt:
 			return visitStmt(n.Stmt)

 		case *ast.ExprStmt:
 			visitExpr(n.X)

 		case *ast.SendStmt:
 			visitExpr(n.Chan)
 			visitExpr(n.Value)
 			unknown() // effect: channel send

 		case *ast.IncDecStmt:
 			visitExpr(n.X)
 			unknown() // effect: variable increment

 		case *ast.AssignStmt:
 			for _, lhs := range n.Lhs {
 				visitExpr(lhs)
 			}
 			for _, rhs := range n.Rhs {
 				visitExpr(rhs)
 			}
 			for _, lhs := range n.Lhs {
 				id, _ := lhs.(*ast.Ident)
 				if id != nil && id.Name == "_" {
 					continue // blank assign has no effect
 				}
 				if n.Tok == token.DEFINE && id != nil && info.Defs[id] != nil {
 					continue // new var declared by := has no effect
 				}
 				unknown() // assignment to existing var
 				break
 			}

 		case *ast.GoStmt:
 			visitExpr(n.Call.Fun)
 			for _, arg := range n.Call.Args {
 				visitExpr(arg)
 			}
 			unknown() // effect: create goroutine

 		case *ast.DeferStmt:
 			visitExpr(n.Call.Fun)
 			for _, arg := range n.Call.Args {
 				visitExpr(arg)
 			}
 			unknown() // effect: push defer

 		case *ast.ReturnStmt:
 			for _, res := range n.Results {
 				visitExpr(res)
 			}
 			return false

 		case *ast.BlockStmt:
 			for _, stmt := range n.List {
 				if !visitStmt(stmt) {
 					return false
 				}
 			}

 		case *ast.BranchStmt:
 			unknown() // control flow

 		case *ast.IfStmt:
 			visitStmt(n.Init)
 			visitExpr(n.Cond)
 			unknown() // control flow

 		case *ast.SwitchStmt:
 			visitStmt(n.Init)
 			visitExpr(n.Tag)
 			unknown() // control flow

 		case *ast.TypeSwitchStmt:
 			visitStmt(n.Init)
 			visitStmt(n.Assign)
 			unknown() // control flow

 		case *ast.SelectStmt:
 			unknown() // control flow

 		case *ast.ForStmt:
 			visitStmt(n.Init)
 			visitExpr(n.Cond)
 			unknown() // control flow

 		case *ast.RangeStmt:
 			visitExpr(n.X)
 			unknown() // control flow

 		case *ast.EmptyStmt, *ast.BadStmt:
 			// no effect

 		case nil:
 			// optional subtree

 		default:
 			panic(n)
 		}
 		return true
 	}
 	visitStmt(body)

 	return effects
 }
	// Copyright 2023 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 inline

	// This file defines the analysis of callee effects.

	import (
	"go/ast"
	"go/token"
	"go/types"
	)

	const (
	rinf = -1 // R∞: arbitrary read from memory
	winf = -2 // W∞: arbitrary write to memory (or unknown control)
	)

	// calleefx returns a list of parameter indices indicating the order
	// in which parameters are first referenced during evaluation of the
	// callee, relative both to each other and to other effects of the
	// callee (if any), such as arbitrary reads (rinf) and arbitrary
	// effects (winf), including unknown control flow. Each parameter
	// that is referenced appears once in the list.
	//
	// For example, the effects list of this function:
	//
	// func f(x, y, z int) int {
	// return y + x + g() + z
	// }
	//
	// is [1 0 -2 2], indicating reads of y and x, followed by the unknown
	// effects of the g() call. and finally the read of parameter z. This
	// information is used during inlining to ascertain when it is safe
	// for parameter references to be replaced by their corresponding
	// argument expressions. Such substitutions are permitted only when
	// they do not cause "write" operations (those with effects) to
	// commute with "read" operations (those that have no effect but are
	// not pure). Impure operations may be reordered with other impure
	// operations, and pure operations may be reordered arbitrarily.
	//
	// The analysis ignores the effects of runtime panics, on the
	// assumption that well-behaved programs shouldn't encounter them.
	func calleefx(info types.Info, body ast.BlockStmt, paramInfos map[types.Var]paramInfo) []int {
	// This traversal analyzes the callee's statements (in syntax
	// form, though one could do better with SSA) to compute the
	// sequence of events of the following kinds:
	//
	// 1 read of a parameter variable.
	// 2. reads from other memory.
	// 3. writes to memory

	var effects []int // indices of parameters, or rinf/winf (-ve)
	seen := make(map[int]bool)
	effect := func(i int) {
	if !seen[i] {
	seen[i] = true
	effects = append(effects, i)
	}
	}

	// unknown is called for statements of unknown effects (or control).
	unknown := func() {
	effect(winf)

	// Ensure that all remaining parameters are "seen"
	// after we go into the unknown (unless they are
	// unreferenced by the function body). This lets us
	// not bother implementing the complete traversal into
	// control structures.
	//
	// TODO(adonovan): add them in a deterministic order.
	// (This is not a bug but determinism is good.)
	for _, pinfo := range paramInfos {
	if !pinfo.IsResult && len(pinfo.Refs) > 0 {
	effect(pinfo.Index)
	}
	}
	}

	var visitExpr func(n ast.Expr)
	var visitStmt func(n ast.Stmt) bool
	visitExpr = func(n ast.Expr) {
	switch n := n.(type) {
	case *ast.Ident:
	if v, ok := info.Uses[n].(*types.Var); ok && !v.IsField() {
	// Use of global?
	if v.Parent() == v.Pkg().Scope() {
	effect(rinf) // read global var
	}

	// Use of parameter?
	if pinfo, ok := paramInfos[v]; ok && !pinfo.IsResult {
	effect(pinfo.Index) // read parameter var
	}

	// Use of local variables is ok.
	}

	case *ast.BasicLit:
	// no effect

	case *ast.FuncLit:
	// A func literal has no read or write effect
	// until called, and (most) function calls are
	// considered to have arbitrary effects.
	// So, no effect.

	case *ast.CompositeLit:
	for _, elt := range n.Elts {
	visitExpr(elt) // note: visits KeyValueExpr
	}

	case *ast.ParenExpr:
	visitExpr(n.X)

	case *ast.SelectorExpr:
	if seln, ok := info.Selections[n]; ok {
	visitExpr(n.X)

	// See types.SelectionKind for background.
	switch seln.Kind() {
	case types.MethodExpr:
	// A method expression T.f acts like a
	// reference to a func decl,
	// so it doesn't read x until called.

	case types.MethodVal, types.FieldVal:
	// A field or method value selection x.f
	// reads x if the selection indirects a pointer.

	if indirectSelection(seln) {
	effect(rinf)
	}
	}
	} else {
	// qualified identifier: treat like unqualified
	visitExpr(n.Sel)
	}

	case *ast.IndexExpr:
	if tv := info.Types[n.Index]; tv.IsType() {
	// no effect (G[T] instantiation)
	} else {
	visitExpr(n.X)
	visitExpr(n.Index)
	switch tv.Type.Underlying().(type) {
	case types.Slice, types.Pointer: // []T, *[n]T (not string, [n]T)
	effect(rinf) // indirect read of slice/array element
	}
	}

	case *ast.IndexListExpr:
	// no effect (M[K,V] instantiation)

	case *ast.SliceExpr:
	visitExpr(n.X)
	visitExpr(n.Low)
	visitExpr(n.High)
	visitExpr(n.Max)

	case *ast.TypeAssertExpr:
	visitExpr(n.X)

	case *ast.CallExpr:
	if info.Types[n.Fun].IsType() {
	// conversion T(x)
	visitExpr(n.Args[0])
	} else {
	// call f(args)
	visitExpr(n.Fun)
	for i, arg := range n.Args {
	if i == 0 && info.Types[arg].IsType() {
	continue // new(T), make(T, n)
	}
	visitExpr(arg)
	}

	// The pure built-ins have no effects beyond
	// those of their operands (not even memory reads).
	// All other calls have unknown effects.
	if !callsPureBuiltin(info, n) {
	unknown() // arbitrary effects
	}
	}

	case *ast.StarExpr:
	visitExpr(n.X)
	effect(rinf) // *ptr load or store depends on state of heap

	case *ast.UnaryExpr: // + - ! ^ & ~ <-
	visitExpr(n.X)
	if n.Op == token.ARROW {
	unknown() // effect: channel receive
	}

	case *ast.BinaryExpr:
	visitExpr(n.X)
	visitExpr(n.Y)

	case *ast.KeyValueExpr:
	visitExpr(n.Key) // may be a struct field
	visitExpr(n.Value)

	case *ast.BadExpr:
	// no effect

	case nil:
	// optional subtree

	default:
	// type syntax: unreachable given traversal
	panic(n)
	}
	}

	// visitStmt's result indicates the continuation:
	// false for return, true for the next statement.
	//
	// We could treat return as an unknown, but this way
	// yields definite effects for simple sequences like
	// {S1; S2; return}, so unreferenced parameters are
	// not spuriously added to the effects list, and thus
	// not spuriously disqualified from elimination.
	visitStmt = func(n ast.Stmt) bool {
	switch n := n.(type) {
	case *ast.DeclStmt:
	decl := n.Decl.(*ast.GenDecl)
	for _, spec := range decl.Specs {
	switch spec := spec.(type) {
	case *ast.ValueSpec:
	for _, v := range spec.Values {
	visitExpr(v)
	}

	case *ast.TypeSpec:
	// no effect
	}
	}

	case *ast.LabeledStmt:
	return visitStmt(n.Stmt)

	case *ast.ExprStmt:
	visitExpr(n.X)

	case *ast.SendStmt:
	visitExpr(n.Chan)
	visitExpr(n.Value)
	unknown() // effect: channel send

	case *ast.IncDecStmt:
	visitExpr(n.X)
	unknown() // effect: variable increment

	case *ast.AssignStmt:
	for _, lhs := range n.Lhs {
	visitExpr(lhs)
	}
	for _, rhs := range n.Rhs {
	visitExpr(rhs)
	}
	for _, lhs := range n.Lhs {
	id, _ := lhs.(*ast.Ident)
	if id != nil && id.Name == "_" {
	continue // blank assign has no effect
	}
	if n.Tok == token.DEFINE && id != nil && info.Defs[id] != nil {
	continue // new var declared by := has no effect
	}
	unknown() // assignment to existing var
	break
	}

	case *ast.GoStmt:
	visitExpr(n.Call.Fun)
	for _, arg := range n.Call.Args {
	visitExpr(arg)
	}
	unknown() // effect: create goroutine

	case *ast.DeferStmt:
	visitExpr(n.Call.Fun)
	for _, arg := range n.Call.Args {
	visitExpr(arg)
	}
	unknown() // effect: push defer

	case *ast.ReturnStmt:
	for _, res := range n.Results {
	visitExpr(res)
	}
	return false

	case *ast.BlockStmt:
	for _, stmt := range n.List {
	if !visitStmt(stmt) {
	return false
	}
	}

	case *ast.BranchStmt:
	unknown() // control flow

	case *ast.IfStmt:
	visitStmt(n.Init)
	visitExpr(n.Cond)
	unknown() // control flow

	case *ast.SwitchStmt:
	visitStmt(n.Init)
	visitExpr(n.Tag)
	unknown() // control flow

	case *ast.TypeSwitchStmt:
	visitStmt(n.Init)
	visitStmt(n.Assign)
	unknown() // control flow

	case *ast.SelectStmt:
	unknown() // control flow

	case *ast.ForStmt:
	visitStmt(n.Init)
	visitExpr(n.Cond)
	unknown() // control flow

	case *ast.RangeStmt:
	visitExpr(n.X)
	unknown() // control flow

	case ast.EmptyStmt, ast.BadStmt:
	// no effect

	case nil:
	// optional subtree

	default:
	panic(n)
	}
	return true
	}
	visitStmt(body)

	return effects
	}