analyze_func_flags.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 inlheur
     6  
     7  import (
     8  	"cmd/compile/internal/base"
     9  	"cmd/compile/internal/ir"
    10  	"cmd/compile/internal/types"
    11  	"fmt"
    12  	"os"
    13  )
    14  
    15  // funcFlagsAnalyzer computes the "Flags" value for the FuncProps
    16  // object we're computing. The main item of interest here is "nstate",
    17  // which stores the disposition of a given ir Node with respect to the
    18  // flags/properties we're trying to compute.
    19  type funcFlagsAnalyzer struct {
    20  	fn     *ir.Func
    21  	nstate map[ir.Node]pstate
    22  	noInfo bool // set if we see something inscrutable/un-analyzable
    23  }
    24  
    25  // pstate keeps track of the disposition of a given node and its
    26  // children with respect to panic/exit calls.
    27  type pstate int
    28  
    29  const (
    30  	psNoInfo     pstate = iota // nothing interesting about this node
    31  	psCallsPanic               // node causes call to panic or os.Exit
    32  	psMayReturn                // executing node may trigger a "return" stmt
    33  	psTop                      // dataflow lattice "top" element
    34  )
    35  
    36  func makeFuncFlagsAnalyzer(fn *ir.Func) *funcFlagsAnalyzer {
    37  	return &funcFlagsAnalyzer{
    38  		fn:     fn,
    39  		nstate: make(map[ir.Node]pstate),
    40  	}
    41  }
    42  
    43  // setResults transfers func flag results to 'funcProps'.
    44  func (ffa *funcFlagsAnalyzer) setResults(funcProps *FuncProps) {
    45  	var rv FuncPropBits
    46  	if !ffa.noInfo && ffa.stateForList(ffa.fn.Body) == psCallsPanic {
    47  		rv = FuncPropNeverReturns
    48  	}
    49  	// This is slightly hacky and not at all required, but include a
    50  	// special case for main.main, which often ends in a call to
    51  	// os.Exit. People who write code like this (very common I
    52  	// imagine)
    53  	//
    54  	//   func main() {
    55  	//     rc = perform()
    56  	//     ...
    57  	//     foo()
    58  	//     os.Exit(rc)
    59  	//   }
    60  	//
    61  	// will be constantly surprised when foo() is inlined in many
    62  	// other spots in the program but not in main().
    63  	if isMainMain(ffa.fn) {
    64  		rv &^= FuncPropNeverReturns
    65  	}
    66  	funcProps.Flags = rv
    67  }
    68  
    69  func (ffa *funcFlagsAnalyzer) getState(n ir.Node) pstate {
    70  	return ffa.nstate[n]
    71  }
    72  
    73  func (ffa *funcFlagsAnalyzer) setState(n ir.Node, st pstate) {
    74  	if st != psNoInfo {
    75  		ffa.nstate[n] = st
    76  	}
    77  }
    78  
    79  func (ffa *funcFlagsAnalyzer) updateState(n ir.Node, st pstate) {
    80  	if st == psNoInfo {
    81  		delete(ffa.nstate, n)
    82  	} else {
    83  		ffa.nstate[n] = st
    84  	}
    85  }
    86  
    87  func (ffa *funcFlagsAnalyzer) panicPathTable() map[ir.Node]pstate {
    88  	return ffa.nstate
    89  }
    90  
    91  // blockCombine merges together states as part of a linear sequence of
    92  // statements, where 'pred' and 'succ' are analysis results for a pair
    93  // of consecutive statements. Examples:
    94  //
    95  //	case 1:             case 2:
    96  //	    panic("foo")      if q { return x }        <-pred
    97  //	    return x          panic("boo")             <-succ
    98  //
    99  // In case 1, since the pred state is "always panic" it doesn't matter
   100  // what the succ state is, hence the state for the combination of the
   101  // two blocks is "always panics". In case 2, because there is a path
   102  // to return that avoids the panic in succ, the state for the
   103  // combination of the two statements is "may return".
   104  func blockCombine(pred, succ pstate) pstate {
   105  	switch succ {
   106  	case psTop:
   107  		return pred
   108  	case psMayReturn:
   109  		if pred == psCallsPanic {
   110  			return psCallsPanic
   111  		}
   112  		return psMayReturn
   113  	case psNoInfo:
   114  		return pred
   115  	case psCallsPanic:
   116  		if pred == psMayReturn {
   117  			return psMayReturn
   118  		}
   119  		return psCallsPanic
   120  	}
   121  	panic("should never execute")
   122  }
   123  
   124  // branchCombine combines two states at a control flow branch point where
   125  // either p1 or p2 executes (as in an "if" statement).
   126  func branchCombine(p1, p2 pstate) pstate {
   127  	if p1 == psCallsPanic && p2 == psCallsPanic {
   128  		return psCallsPanic
   129  	}
   130  	if p1 == psMayReturn || p2 == psMayReturn {
   131  		return psMayReturn
   132  	}
   133  	return psNoInfo
   134  }
   135  
   136  // stateForList walks through a list of statements and computes the
   137  // state/disposition for the entire list as a whole, as well
   138  // as updating disposition of intermediate nodes.
   139  func (ffa *funcFlagsAnalyzer) stateForList(list ir.Nodes) pstate {
   140  	st := psTop
   141  	// Walk the list backwards so that we can update the state for
   142  	// earlier list elements based on what we find out about their
   143  	// successors. Example:
   144  	//
   145  	//        if ... {
   146  	//  L10:    foo()
   147  	//  L11:    <stmt>
   148  	//  L12:    panic(...)
   149  	//        }
   150  	//
   151  	// After combining the dispositions for line 11 and 12, we want to
   152  	// update the state for the call at line 10 based on that combined
   153  	// disposition (if L11 has no path to "return", then the call at
   154  	// line 10 will be on a panic path).
   155  	for i := len(list) - 1; i >= 0; i-- {
   156  		n := list[i]
   157  		psi := ffa.getState(n)
   158  		if debugTrace&debugTraceFuncFlags != 0 {
   159  			fmt.Fprintf(os.Stderr, "=-= %v: stateForList n=%s ps=%s\n",
   160  				ir.Line(n), n.Op().String(), psi.String())
   161  		}
   162  		st = blockCombine(psi, st)
   163  		ffa.updateState(n, st)
   164  	}
   165  	if st == psTop {
   166  		st = psNoInfo
   167  	}
   168  	return st
   169  }
   170  
   171  func isMainMain(fn *ir.Func) bool {
   172  	s := fn.Sym()
   173  	return (s.Pkg.Name == "main" && s.Name == "main")
   174  }
   175  
   176  func isWellKnownFunc(s *types.Sym, pkg, name string) bool {
   177  	return s.Pkg.Path == pkg && s.Name == name
   178  }
   179  
   180  // isExitCall reports TRUE if the node itself is an unconditional
   181  // call to os.Exit(), a panic, or a function that does likewise.
   182  func isExitCall(n ir.Node) bool {
   183  	if n.Op() != ir.OCALLFUNC {
   184  		return false
   185  	}
   186  	cx := n.(*ir.CallExpr)
   187  	name := ir.StaticCalleeName(cx.Fun)
   188  	if name == nil {
   189  		return false
   190  	}
   191  	s := name.Sym()
   192  	if isWellKnownFunc(s, "os", "Exit") ||
   193  		isWellKnownFunc(s, "runtime", "throw") {
   194  		return true
   195  	}
   196  	if funcProps := propsForFunc(name.Func); funcProps != nil {
   197  		if funcProps.Flags&FuncPropNeverReturns != 0 {
   198  			return true
   199  		}
   200  	}
   201  	return name.Func.NeverReturns()
   202  }
   203  
   204  // pessimize is called to record the fact that we saw something in the
   205  // function that renders it entirely impossible to analyze.
   206  func (ffa *funcFlagsAnalyzer) pessimize() {
   207  	ffa.noInfo = true
   208  }
   209  
   210  // shouldVisit reports TRUE if this is an interesting node from the
   211  // perspective of computing function flags. NB: due to the fact that
   212  // ir.CallExpr implements the Stmt interface, we wind up visiting
   213  // a lot of nodes that we don't really need to, but these can
   214  // simply be screened out as part of the visit.
   215  func shouldVisit(n ir.Node) bool {
   216  	_, isStmt := n.(ir.Stmt)
   217  	return n.Op() != ir.ODCL &&
   218  		(isStmt || n.Op() == ir.OCALLFUNC || n.Op() == ir.OPANIC)
   219  }
   220  
   221  // nodeVisitPost helps implement the propAnalyzer interface; when
   222  // called on a given node, it decides the disposition of that node
   223  // based on the state(s) of the node's children.
   224  func (ffa *funcFlagsAnalyzer) nodeVisitPost(n ir.Node) {
   225  	if debugTrace&debugTraceFuncFlags != 0 {
   226  		fmt.Fprintf(os.Stderr, "=+= nodevis %v %s should=%v\n",
   227  			ir.Line(n), n.Op().String(), shouldVisit(n))
   228  	}
   229  	if !shouldVisit(n) {
   230  		return
   231  	}
   232  	var st pstate
   233  	switch n.Op() {
   234  	case ir.OCALLFUNC:
   235  		if isExitCall(n) {
   236  			st = psCallsPanic
   237  		}
   238  	case ir.OPANIC:
   239  		st = psCallsPanic
   240  	case ir.ORETURN:
   241  		st = psMayReturn
   242  	case ir.OBREAK, ir.OCONTINUE:
   243  		// FIXME: this handling of break/continue is sub-optimal; we
   244  		// have them as "mayReturn" in order to help with this case:
   245  		//
   246  		//   for {
   247  		//     if q() { break }
   248  		//     panic(...)
   249  		//   }
   250  		//
   251  		// where the effect of the 'break' is to cause the subsequent
   252  		// panic to be skipped. One possible improvement would be to
   253  		// track whether the currently enclosing loop is a "for {" or
   254  		// a for/range with condition, then use mayReturn only for the
   255  		// former. Note also that "break X" or "continue X" is treated
   256  		// the same as "goto", since we don't have a good way to track
   257  		// the target of the branch.
   258  		st = psMayReturn
   259  		n := n.(*ir.BranchStmt)
   260  		if n.Label != nil {
   261  			ffa.pessimize()
   262  		}
   263  	case ir.OBLOCK:
   264  		n := n.(*ir.BlockStmt)
   265  		st = ffa.stateForList(n.List)
   266  	case ir.OCASE:
   267  		if ccst, ok := n.(*ir.CaseClause); ok {
   268  			st = ffa.stateForList(ccst.Body)
   269  		} else if ccst, ok := n.(*ir.CommClause); ok {
   270  			st = ffa.stateForList(ccst.Body)
   271  		} else {
   272  			panic("unexpected")
   273  		}
   274  	case ir.OIF:
   275  		n := n.(*ir.IfStmt)
   276  		st = branchCombine(ffa.stateForList(n.Body), ffa.stateForList(n.Else))
   277  	case ir.OFOR:
   278  		// Treat for { XXX } like a block.
   279  		// Treat for <cond> { XXX } like an if statement with no else.
   280  		n := n.(*ir.ForStmt)
   281  		bst := ffa.stateForList(n.Body)
   282  		if n.Cond == nil {
   283  			st = bst
   284  		} else {
   285  			if bst == psMayReturn {
   286  				st = psMayReturn
   287  			}
   288  		}
   289  	case ir.ORANGE:
   290  		// Treat for range { XXX } like an if statement with no else.
   291  		n := n.(*ir.RangeStmt)
   292  		if ffa.stateForList(n.Body) == psMayReturn {
   293  			st = psMayReturn
   294  		}
   295  	case ir.OGOTO:
   296  		// punt if we see even one goto. if we built a control
   297  		// flow graph we could do more, but this is just a tree walk.
   298  		ffa.pessimize()
   299  	case ir.OSELECT:
   300  		// process selects for "may return" but not "always panics",
   301  		// the latter case seems very improbable.
   302  		n := n.(*ir.SelectStmt)
   303  		if len(n.Cases) != 0 {
   304  			st = psTop
   305  			for _, c := range n.Cases {
   306  				st = branchCombine(ffa.stateForList(c.Body), st)
   307  			}
   308  		}
   309  	case ir.OSWITCH:
   310  		n := n.(*ir.SwitchStmt)
   311  		if len(n.Cases) != 0 {
   312  			st = psTop
   313  			for _, c := range n.Cases {
   314  				st = branchCombine(ffa.stateForList(c.Body), st)
   315  			}
   316  		}
   317  
   318  		st, fall := psTop, psNoInfo
   319  		for i := len(n.Cases) - 1; i >= 0; i-- {
   320  			cas := n.Cases[i]
   321  			cst := ffa.stateForList(cas.Body)
   322  			endsInFallthrough := false
   323  			if len(cas.Body) != 0 {
   324  				endsInFallthrough = cas.Body[0].Op() == ir.OFALL
   325  			}
   326  			if endsInFallthrough {
   327  				cst = blockCombine(cst, fall)
   328  			}
   329  			st = branchCombine(st, cst)
   330  			fall = cst
   331  		}
   332  	case ir.OFALL:
   333  		// Not important.
   334  	case ir.ODCLFUNC, ir.ORECOVER, ir.OAS, ir.OAS2, ir.OAS2FUNC, ir.OASOP,
   335  		ir.OPRINTLN, ir.OPRINT, ir.OLABEL, ir.OCALLINTER, ir.ODEFER,
   336  		ir.OSEND, ir.ORECV, ir.OSELRECV2, ir.OGO, ir.OAPPEND, ir.OAS2DOTTYPE,
   337  		ir.OAS2MAPR, ir.OGETG, ir.ODELETE, ir.OINLMARK, ir.OAS2RECV,
   338  		ir.OMIN, ir.OMAX, ir.OMAKE, ir.ORECOVERFP, ir.OGETCALLERSP:
   339  		// these should all be benign/uninteresting
   340  	case ir.OTAILCALL, ir.OJUMPTABLE, ir.OTYPESW:
   341  		// don't expect to see these at all.
   342  		base.Fatalf("unexpected op %s in func %s",
   343  			n.Op().String(), ir.FuncName(ffa.fn))
   344  	default:
   345  		base.Fatalf("%v: unhandled op %s in func %v",
   346  			ir.Line(n), n.Op().String(), ir.FuncName(ffa.fn))
   347  	}
   348  	if debugTrace&debugTraceFuncFlags != 0 {
   349  		fmt.Fprintf(os.Stderr, "=-= %v: visit n=%s returns %s\n",
   350  			ir.Line(n), n.Op().String(), st.String())
   351  	}
   352  	ffa.setState(n, st)
   353  }
   354  
   355  func (ffa *funcFlagsAnalyzer) nodeVisitPre(n ir.Node) {
   356  }
   357
View as plain text