blob: d86fd7d71b969aab742fbb7c939e8108da241e57 [file] [log] [blame] [edit]
// 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 inlheur
import (
"cmd/compile/internal/base"
"cmd/compile/internal/ir"
"cmd/compile/internal/types"
"fmt"
"os"
)
// funcFlagsAnalyzer computes the "Flags" value for the FuncProps
// object we're computing. The main item of interest here is "nstate",
// which stores the disposition of a given ir Node with respect to the
// flags/properties we're trying to compute.
type funcFlagsAnalyzer struct {
fn *ir.Func
nstate map[ir.Node]pstate
noInfo bool // set if we see something inscrutable/un-analyzable
}
// pstate keeps track of the disposition of a given node and its
// children with respect to panic/exit calls.
type pstate int
const (
psNoInfo pstate = iota // nothing interesting about this node
psCallsPanic // node causes call to panic or os.Exit
psMayReturn // executing node may trigger a "return" stmt
psTop // dataflow lattice "top" element
)
func makeFuncFlagsAnalyzer(fn *ir.Func) *funcFlagsAnalyzer {
return &funcFlagsAnalyzer{
fn: fn,
nstate: make(map[ir.Node]pstate),
}
}
// setResults transfers func flag results to 'funcProps'.
func (ffa *funcFlagsAnalyzer) setResults(funcProps *FuncProps) {
var rv FuncPropBits
if !ffa.noInfo && ffa.stateForList(ffa.fn.Body) == psCallsPanic {
rv = FuncPropNeverReturns
}
// This is slightly hacky and not at all required, but include a
// special case for main.main, which often ends in a call to
// os.Exit. People who write code like this (very common I
// imagine)
//
// func main() {
// rc = perform()
// ...
// foo()
// os.Exit(rc)
// }
//
// will be constantly surprised when foo() is inlined in many
// other spots in the program but not in main().
if isMainMain(ffa.fn) {
rv &^= FuncPropNeverReturns
}
funcProps.Flags = rv
}
func (ffa *funcFlagsAnalyzer) getState(n ir.Node) pstate {
return ffa.nstate[n]
}
func (ffa *funcFlagsAnalyzer) setState(n ir.Node, st pstate) {
if st != psNoInfo {
ffa.nstate[n] = st
}
}
func (ffa *funcFlagsAnalyzer) updateState(n ir.Node, st pstate) {
if st == psNoInfo {
delete(ffa.nstate, n)
} else {
ffa.nstate[n] = st
}
}
func (ffa *funcFlagsAnalyzer) panicPathTable() map[ir.Node]pstate {
return ffa.nstate
}
// blockCombine merges together states as part of a linear sequence of
// statements, where 'pred' and 'succ' are analysis results for a pair
// of consecutive statements. Examples:
//
// case 1: case 2:
// panic("foo") if q { return x } <-pred
// return x panic("boo") <-succ
//
// In case 1, since the pred state is "always panic" it doesn't matter
// what the succ state is, hence the state for the combination of the
// two blocks is "always panics". In case 2, because there is a path
// to return that avoids the panic in succ, the state for the
// combination of the two statements is "may return".
func blockCombine(pred, succ pstate) pstate {
switch succ {
case psTop:
return pred
case psMayReturn:
if pred == psCallsPanic {
return psCallsPanic
}
return psMayReturn
case psNoInfo:
return pred
case psCallsPanic:
if pred == psMayReturn {
return psMayReturn
}
return psCallsPanic
}
panic("should never execute")
}
// branchCombine combines two states at a control flow branch point where
// either p1 or p2 executes (as in an "if" statement).
func branchCombine(p1, p2 pstate) pstate {
if p1 == psCallsPanic && p2 == psCallsPanic {
return psCallsPanic
}
if p1 == psMayReturn || p2 == psMayReturn {
return psMayReturn
}
return psNoInfo
}
// stateForList walks through a list of statements and computes the
// state/disposition for the entire list as a whole, as well
// as updating disposition of intermediate nodes.
func (ffa *funcFlagsAnalyzer) stateForList(list ir.Nodes) pstate {
st := psTop
// Walk the list backwards so that we can update the state for
// earlier list elements based on what we find out about their
// successors. Example:
//
// if ... {
// L10: foo()
// L11: <stmt>
// L12: panic(...)
// }
//
// After combining the dispositions for line 11 and 12, we want to
// update the state for the call at line 10 based on that combined
// disposition (if L11 has no path to "return", then the call at
// line 10 will be on a panic path).
for i := len(list) - 1; i >= 0; i-- {
n := list[i]
psi := ffa.getState(n)
if debugTrace&debugTraceFuncFlags != 0 {
fmt.Fprintf(os.Stderr, "=-= %v: stateForList n=%s ps=%s\n",
ir.Line(n), n.Op().String(), psi.String())
}
st = blockCombine(psi, st)
ffa.updateState(n, st)
}
if st == psTop {
st = psNoInfo
}
return st
}
func isMainMain(fn *ir.Func) bool {
s := fn.Sym()
return (s.Pkg.Name == "main" && s.Name == "main")
}
func isWellKnownFunc(s *types.Sym, pkg, name string) bool {
return s.Pkg.Path == pkg && s.Name == name
}
// isExitCall reports TRUE if the node itself is an unconditional
// call to os.Exit(), a panic, or a function that does likewise.
func isExitCall(n ir.Node) bool {
if n.Op() != ir.OCALLFUNC {
return false
}
cx := n.(*ir.CallExpr)
name := ir.StaticCalleeName(cx.Fun)
if name == nil {
return false
}
s := name.Sym()
if isWellKnownFunc(s, "os", "Exit") ||
isWellKnownFunc(s, "runtime", "throw") {
return true
}
if funcProps := propsForFunc(name.Func); funcProps != nil {
if funcProps.Flags&FuncPropNeverReturns != 0 {
return true
}
}
return name.Func.NeverReturns()
}
// pessimize is called to record the fact that we saw something in the
// function that renders it entirely impossible to analyze.
func (ffa *funcFlagsAnalyzer) pessimize() {
ffa.noInfo = true
}
// shouldVisit reports TRUE if this is an interesting node from the
// perspective of computing function flags. NB: due to the fact that
// ir.CallExpr implements the Stmt interface, we wind up visiting
// a lot of nodes that we don't really need to, but these can
// simply be screened out as part of the visit.
func shouldVisit(n ir.Node) bool {
_, isStmt := n.(ir.Stmt)
return n.Op() != ir.ODCL &&
(isStmt || n.Op() == ir.OCALLFUNC || n.Op() == ir.OPANIC)
}
// nodeVisitPost helps implement the propAnalyzer interface; when
// called on a given node, it decides the disposition of that node
// based on the state(s) of the node's children.
func (ffa *funcFlagsAnalyzer) nodeVisitPost(n ir.Node) {
if debugTrace&debugTraceFuncFlags != 0 {
fmt.Fprintf(os.Stderr, "=+= nodevis %v %s should=%v\n",
ir.Line(n), n.Op().String(), shouldVisit(n))
}
if !shouldVisit(n) {
return
}
var st pstate
switch n.Op() {
case ir.OCALLFUNC:
if isExitCall(n) {
st = psCallsPanic
}
case ir.OPANIC:
st = psCallsPanic
case ir.ORETURN:
st = psMayReturn
case ir.OBREAK, ir.OCONTINUE:
// FIXME: this handling of break/continue is sub-optimal; we
// have them as "mayReturn" in order to help with this case:
//
// for {
// if q() { break }
// panic(...)
// }
//
// where the effect of the 'break' is to cause the subsequent
// panic to be skipped. One possible improvement would be to
// track whether the currently enclosing loop is a "for {" or
// a for/range with condition, then use mayReturn only for the
// former. Note also that "break X" or "continue X" is treated
// the same as "goto", since we don't have a good way to track
// the target of the branch.
st = psMayReturn
n := n.(*ir.BranchStmt)
if n.Label != nil {
ffa.pessimize()
}
case ir.OBLOCK:
n := n.(*ir.BlockStmt)
st = ffa.stateForList(n.List)
case ir.OCASE:
if ccst, ok := n.(*ir.CaseClause); ok {
st = ffa.stateForList(ccst.Body)
} else if ccst, ok := n.(*ir.CommClause); ok {
st = ffa.stateForList(ccst.Body)
} else {
panic("unexpected")
}
case ir.OIF:
n := n.(*ir.IfStmt)
st = branchCombine(ffa.stateForList(n.Body), ffa.stateForList(n.Else))
case ir.OFOR:
// Treat for { XXX } like a block.
// Treat for <cond> { XXX } like an if statement with no else.
n := n.(*ir.ForStmt)
bst := ffa.stateForList(n.Body)
if n.Cond == nil {
st = bst
} else {
if bst == psMayReturn {
st = psMayReturn
}
}
case ir.ORANGE:
// Treat for range { XXX } like an if statement with no else.
n := n.(*ir.RangeStmt)
if ffa.stateForList(n.Body) == psMayReturn {
st = psMayReturn
}
case ir.OGOTO:
// punt if we see even one goto. if we built a control
// flow graph we could do more, but this is just a tree walk.
ffa.pessimize()
case ir.OSELECT:
// process selects for "may return" but not "always panics",
// the latter case seems very improbable.
n := n.(*ir.SelectStmt)
if len(n.Cases) != 0 {
st = psTop
for _, c := range n.Cases {
st = branchCombine(ffa.stateForList(c.Body), st)
}
}
case ir.OSWITCH:
n := n.(*ir.SwitchStmt)
if len(n.Cases) != 0 {
st = psTop
for _, c := range n.Cases {
st = branchCombine(ffa.stateForList(c.Body), st)
}
}
st, fall := psTop, psNoInfo
for i := len(n.Cases) - 1; i >= 0; i-- {
cas := n.Cases[i]
cst := ffa.stateForList(cas.Body)
endsInFallthrough := false
if len(cas.Body) != 0 {
endsInFallthrough = cas.Body[0].Op() == ir.OFALL
}
if endsInFallthrough {
cst = blockCombine(cst, fall)
}
st = branchCombine(st, cst)
fall = cst
}
case ir.OFALL:
// Not important.
case ir.ODCLFUNC, ir.ORECOVER, ir.OAS, ir.OAS2, ir.OAS2FUNC, ir.OASOP,
ir.OPRINTLN, ir.OPRINT, ir.OLABEL, ir.OCALLINTER, ir.ODEFER,
ir.OSEND, ir.ORECV, ir.OSELRECV2, ir.OGO, ir.OAPPEND, ir.OAS2DOTTYPE,
ir.OAS2MAPR, ir.OGETG, ir.ODELETE, ir.OINLMARK, ir.OAS2RECV,
ir.OMIN, ir.OMAX, ir.OMAKE, ir.ORECOVERFP, ir.OGETCALLERSP:
// these should all be benign/uninteresting
case ir.OTAILCALL, ir.OJUMPTABLE, ir.OTYPESW:
// don't expect to see these at all.
base.Fatalf("unexpected op %s in func %s",
n.Op().String(), ir.FuncName(ffa.fn))
default:
base.Fatalf("%v: unhandled op %s in func %v",
ir.Line(n), n.Op().String(), ir.FuncName(ffa.fn))
}
if debugTrace&debugTraceFuncFlags != 0 {
fmt.Fprintf(os.Stderr, "=-= %v: visit n=%s returns %s\n",
ir.Line(n), n.Op().String(), st.String())
}
ffa.setState(n, st)
}
func (ffa *funcFlagsAnalyzer) nodeVisitPre(n ir.Node) {
}