calleefx.go

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package inline
     6  
     7  // This file defines the analysis of callee effects.
     8  
     9  import (
    10  	"go/ast"
    11  	"go/token"
    12  	"go/types"
    13  
    14  	"golang.org/x/tools/internal/typesinternal"
    15  )
    16  
    17  const (
    18  	rinf = -1 //  R∞: arbitrary read from memory
    19  	winf = -2 //  W∞: arbitrary write to memory (or unknown control)
    20  )
    21  
    22  // calleefx returns a list of parameter indices indicating the order
    23  // in which parameters are first referenced during evaluation of the
    24  // callee, relative both to each other and to other effects of the
    25  // callee (if any), such as arbitrary reads (rinf) and arbitrary
    26  // effects (winf), including unknown control flow. Each parameter
    27  // that is referenced appears once in the list.
    28  //
    29  // For example, the effects list of this function:
    30  //
    31  //	func f(x, y, z int) int {
    32  //	    return y + x + g() + z
    33  //	}
    34  //
    35  // is [1 0 -2 2], indicating reads of y and x, followed by the unknown
    36  // effects of the g() call, and finally the read of parameter z. This
    37  // information is used during inlining to ascertain when it is safe
    38  // for parameter references to be replaced by their corresponding
    39  // argument expressions. Such substitutions are permitted only when
    40  // they do not cause "write" operations (those with effects) to
    41  // commute with "read" operations (those that have no effect but are
    42  // not pure). Impure operations may be reordered with other impure
    43  // operations, and pure operations may be reordered arbitrarily.
    44  //
    45  // The analysis ignores the effects of runtime panics, on the
    46  // assumption that well-behaved programs shouldn't encounter them.
    47  func calleefx(info *types.Info, body *ast.BlockStmt, paramInfos map[*types.Var]*paramInfo) []int {
    48  	// This traversal analyzes the callee's statements (in syntax
    49  	// form, though one could do better with SSA) to compute the
    50  	// sequence of events of the following kinds:
    51  	//
    52  	// 1  read of a parameter variable.
    53  	// 2. reads from other memory.
    54  	// 3. writes to memory
    55  
    56  	var effects []int // indices of parameters, or rinf/winf (-ve)
    57  	seen := make(map[int]bool)
    58  	effect := func(i int) {
    59  		if !seen[i] {
    60  			seen[i] = true
    61  			effects = append(effects, i)
    62  		}
    63  	}
    64  
    65  	// unknown is called for statements of unknown effects (or control).
    66  	unknown := func() {
    67  		effect(winf)
    68  
    69  		// Ensure that all remaining parameters are "seen"
    70  		// after we go into the unknown (unless they are
    71  		// unreferenced by the function body). This lets us
    72  		// not bother implementing the complete traversal into
    73  		// control structures.
    74  		//
    75  		// TODO(adonovan): add them in a deterministic order.
    76  		// (This is not a bug but determinism is good.)
    77  		for _, pinfo := range paramInfos {
    78  			if !pinfo.IsResult && len(pinfo.Refs) > 0 {
    79  				effect(pinfo.Index)
    80  			}
    81  		}
    82  	}
    83  
    84  	var visitExpr func(n ast.Expr)
    85  	var visitStmt func(n ast.Stmt) bool
    86  	visitExpr = func(n ast.Expr) {
    87  		switch n := n.(type) {
    88  		case *ast.Ident:
    89  			if v, ok := info.Uses[n].(*types.Var); ok && !v.IsField() {
    90  				// Use of global?
    91  				if v.Parent() == v.Pkg().Scope() {
    92  					effect(rinf) // read global var
    93  				}
    94  
    95  				// Use of parameter?
    96  				if pinfo, ok := paramInfos[v]; ok && !pinfo.IsResult {
    97  					effect(pinfo.Index) // read parameter var
    98  				}
    99  
   100  				// Use of local variables is ok.
   101  			}
   102  
   103  		case *ast.BasicLit:
   104  			// no effect
   105  
   106  		case *ast.FuncLit:
   107  			// A func literal has no read or write effect
   108  			// until called, and (most) function calls are
   109  			// considered to have arbitrary effects.
   110  			// So, no effect.
   111  
   112  		case *ast.CompositeLit:
   113  			for _, elt := range n.Elts {
   114  				visitExpr(elt) // note: visits KeyValueExpr
   115  			}
   116  
   117  		case *ast.ParenExpr:
   118  			visitExpr(n.X)
   119  
   120  		case *ast.SelectorExpr:
   121  			if seln, ok := info.Selections[n]; ok {
   122  				visitExpr(n.X)
   123  
   124  				// See types.SelectionKind for background.
   125  				switch seln.Kind() {
   126  				case types.MethodExpr:
   127  					// A method expression T.f acts like a
   128  					// reference to a func decl,
   129  					// so it doesn't read x until called.
   130  
   131  				case types.MethodVal, types.FieldVal:
   132  					// A field or method value selection x.f
   133  					// reads x if the selection indirects a pointer.
   134  
   135  					if indirectSelection(seln) {
   136  						effect(rinf)
   137  					}
   138  				}
   139  			} else {
   140  				// qualified identifier: treat like unqualified
   141  				visitExpr(n.Sel)
   142  			}
   143  
   144  		case *ast.IndexExpr:
   145  			if tv := info.Types[n.Index]; tv.IsType() {
   146  				// no effect (G[T] instantiation)
   147  			} else {
   148  				visitExpr(n.X)
   149  				visitExpr(n.Index)
   150  				switch tv.Type.Underlying().(type) {
   151  				case *types.Slice, *types.Pointer: // []T, *[n]T (not string, [n]T)
   152  					effect(rinf) // indirect read of slice/array element
   153  				}
   154  			}
   155  
   156  		case *ast.IndexListExpr:
   157  			// no effect (M[K,V] instantiation)
   158  
   159  		case *ast.SliceExpr:
   160  			visitExpr(n.X)
   161  			visitExpr(n.Low)
   162  			visitExpr(n.High)
   163  			visitExpr(n.Max)
   164  
   165  		case *ast.TypeAssertExpr:
   166  			visitExpr(n.X)
   167  
   168  		case *ast.CallExpr:
   169  			if info.Types[n.Fun].IsType() {
   170  				// conversion T(x)
   171  				visitExpr(n.Args[0])
   172  			} else {
   173  				// call f(args)
   174  				visitExpr(n.Fun)
   175  				for i, arg := range n.Args {
   176  					if i == 0 && info.Types[arg].IsType() {
   177  						continue // new(T), make(T, n)
   178  					}
   179  					visitExpr(arg)
   180  				}
   181  
   182  				// The pure built-ins have no effects beyond
   183  				// those of their operands (not even memory reads).
   184  				// All other calls have unknown effects.
   185  				if !typesinternal.CallsPureBuiltin(info, n) {
   186  					unknown() // arbitrary effects
   187  				}
   188  			}
   189  
   190  		case *ast.StarExpr:
   191  			visitExpr(n.X)
   192  			effect(rinf) // *ptr load or store depends on state of heap
   193  
   194  		case *ast.UnaryExpr: // + - ! ^ & ~ <-
   195  			visitExpr(n.X)
   196  			if n.Op == token.ARROW {
   197  				unknown() // effect: channel receive
   198  			}
   199  
   200  		case *ast.BinaryExpr:
   201  			visitExpr(n.X)
   202  			visitExpr(n.Y)
   203  
   204  		case *ast.KeyValueExpr:
   205  			visitExpr(n.Key) // may be a struct field
   206  			visitExpr(n.Value)
   207  
   208  		case *ast.BadExpr:
   209  			// no effect
   210  
   211  		case nil:
   212  			// optional subtree
   213  
   214  		default:
   215  			// type syntax: unreachable given traversal
   216  			panic(n)
   217  		}
   218  	}
   219  
   220  	// visitStmt's result indicates the continuation:
   221  	// false for return, true for the next statement.
   222  	//
   223  	// We could treat return as an unknown, but this way
   224  	// yields definite effects for simple sequences like
   225  	// {S1; S2; return}, so unreferenced parameters are
   226  	// not spuriously added to the effects list, and thus
   227  	// not spuriously disqualified from elimination.
   228  	visitStmt = func(n ast.Stmt) bool {
   229  		switch n := n.(type) {
   230  		case *ast.DeclStmt:
   231  			decl := n.Decl.(*ast.GenDecl)
   232  			for _, spec := range decl.Specs {
   233  				switch spec := spec.(type) {
   234  				case *ast.ValueSpec:
   235  					for _, v := range spec.Values {
   236  						visitExpr(v)
   237  					}
   238  
   239  				case *ast.TypeSpec:
   240  					// no effect
   241  				}
   242  			}
   243  
   244  		case *ast.LabeledStmt:
   245  			return visitStmt(n.Stmt)
   246  
   247  		case *ast.ExprStmt:
   248  			visitExpr(n.X)
   249  
   250  		case *ast.SendStmt:
   251  			visitExpr(n.Chan)
   252  			visitExpr(n.Value)
   253  			unknown() // effect: channel send
   254  
   255  		case *ast.IncDecStmt:
   256  			visitExpr(n.X)
   257  			unknown() // effect: variable increment
   258  
   259  		case *ast.AssignStmt:
   260  			for _, lhs := range n.Lhs {
   261  				visitExpr(lhs)
   262  			}
   263  			for _, rhs := range n.Rhs {
   264  				visitExpr(rhs)
   265  			}
   266  			for _, lhs := range n.Lhs {
   267  				id, _ := lhs.(*ast.Ident)
   268  				if id != nil && id.Name == "_" {
   269  					continue // blank assign has no effect
   270  				}
   271  				if n.Tok == token.DEFINE && id != nil && info.Defs[id] != nil {
   272  					continue // new var declared by := has no effect
   273  				}
   274  				unknown() // assignment to existing var
   275  				break
   276  			}
   277  
   278  		case *ast.GoStmt:
   279  			visitExpr(n.Call.Fun)
   280  			for _, arg := range n.Call.Args {
   281  				visitExpr(arg)
   282  			}
   283  			unknown() // effect: create goroutine
   284  
   285  		case *ast.DeferStmt:
   286  			visitExpr(n.Call.Fun)
   287  			for _, arg := range n.Call.Args {
   288  				visitExpr(arg)
   289  			}
   290  			unknown() // effect: push defer
   291  
   292  		case *ast.ReturnStmt:
   293  			for _, res := range n.Results {
   294  				visitExpr(res)
   295  			}
   296  			return false
   297  
   298  		case *ast.BlockStmt:
   299  			for _, stmt := range n.List {
   300  				if !visitStmt(stmt) {
   301  					return false
   302  				}
   303  			}
   304  
   305  		case *ast.BranchStmt:
   306  			unknown() // control flow
   307  
   308  		case *ast.IfStmt:
   309  			visitStmt(n.Init)
   310  			visitExpr(n.Cond)
   311  			unknown() // control flow
   312  
   313  		case *ast.SwitchStmt:
   314  			visitStmt(n.Init)
   315  			visitExpr(n.Tag)
   316  			unknown() // control flow
   317  
   318  		case *ast.TypeSwitchStmt:
   319  			visitStmt(n.Init)
   320  			visitStmt(n.Assign)
   321  			unknown() // control flow
   322  
   323  		case *ast.SelectStmt:
   324  			unknown() // control flow
   325  
   326  		case *ast.ForStmt:
   327  			visitStmt(n.Init)
   328  			visitExpr(n.Cond)
   329  			unknown() // control flow
   330  
   331  		case *ast.RangeStmt:
   332  			visitExpr(n.X)
   333  			unknown() // control flow
   334  
   335  		case *ast.EmptyStmt, *ast.BadStmt:
   336  			// no effect
   337  
   338  		case nil:
   339  			// optional subtree
   340  
   341  		default:
   342  			panic(n)
   343  		}
   344  		return true
   345  	}
   346  	visitStmt(body)
   347  
   348  	return effects
   349  }
   350
View as plain text