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