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 'fp'.
  44 func (ffa *funcFlagsAnalyzer) setResults(fp *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         fp.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         for i := range list {
 152                 n := list[i]
 153                 psi := ffa.getstate(n)
 154                 if debugTrace&debugTraceFuncFlags != 0 {
 155                         fmt.Fprintf(os.Stderr, "=-= %v: stateForList n=%s ps=%s\n",
 156                                 ir.Line(n), n.Op().String(), psi.String())
 157                 }
 158                 st = blockCombine(st, psi)
 159                 ffa.updatestate(n, st)
 160         }
 161         if st == psTop {
 162                 st = psNoInfo
 163         }
 164         return st
 165 }
 166
 167 func isMainMain(fn *ir.Func) bool {
 168         s := fn.Sym()
 169         return (s.Pkg.Name == "main" && s.Name == "main")
 170 }
 171
 172 func isWellKnownFunc(s *types.Sym, pkg, name string) bool {
 173         return s.Pkg.Path == pkg && s.Name == name
 174 }
 175
 176 // isExitCall reports TRUE if the node itself is an unconditional
 177 // call to os.Exit(), a panic, or a function that does likewise.
 178 func isExitCall(n ir.Node) bool {
 179         if n.Op() != ir.OCALLFUNC {
 180                 return false
 181         }
 182         cx := n.(*ir.CallExpr)
 183         name := ir.StaticCalleeName(cx.X)
 184         if name == nil {
 185                 return false
 186         }
 187         s := name.Sym()
 188         if isWellKnownFunc(s, "os", "Exit") ||
 189                 isWellKnownFunc(s, "runtime", "throw") {
 190                 return true
 191         }
 192         if fp := propsForFunc(name.Func); fp != nil {
 193                 if fp.Flags&FuncPropNeverReturns != 0 {
 194                         return true
 195                 }
 196         }
 197         return name.Func.NeverReturns()
 198 }
 199
 200 // pessimize is called to record the fact that we saw something in the
 201 // function that renders it entirely impossible to analyze.
 202 func (ffa *funcFlagsAnalyzer) pessimize() {
 203         ffa.noInfo = true
 204 }
 205
 206 // shouldVisit reports TRUE if this is an interesting node from the
 207 // perspective of computing function flags. NB: due to the fact that
 208 // ir.CallExpr implements the Stmt interface, we wind up visiting
 209 // a lot of nodes that we don't really need to, but these can
 210 // simply be screened out as part of the visit.
 211 func shouldVisit(n ir.Node) bool {
 212         _, isStmt := n.(ir.Stmt)
 213         return n.Op() != ir.ODCL &&
 214                 (isStmt || n.Op() == ir.OCALLFUNC || n.Op() == ir.OPANIC)
 215 }
 216
 217 // nodeVisitPost helps implement the propAnalyzer interface; when
 218 // called on a given node, it decides the disposition of that node
 219 // based on the state(s) of the node's children.
 220 func (ffa *funcFlagsAnalyzer) nodeVisitPost(n ir.Node) {
 221         if debugTrace&debugTraceFuncFlags != 0 {
 222                 fmt.Fprintf(os.Stderr, "=+= nodevis %v %s should=%v\n",
 223                         ir.Line(n), n.Op().String(), shouldVisit(n))
 224         }
 225         if !shouldVisit(n) {
 226                 // invoke soft set, since node may be shared (e.g. ONAME)
 227                 ffa.setstateSoft(n, psNoInfo)
 228                 return
 229         }
 230         var st pstate
 231         switch n.Op() {
 232         case ir.OCALLFUNC:
 233                 if isExitCall(n) {
 234                         st = psCallsPanic
 235                 }
 236         case ir.OPANIC:
 237                 st = psCallsPanic
 238         case ir.ORETURN:
 239                 st = psMayReturn
 240         case ir.OBREAK, ir.OCONTINUE:
 241                 // FIXME: this handling of break/continue is sub-optimal; we
 242                 // have them as "mayReturn" in order to help with this case:
 243                 //
 244                 //   for {
 245                 //     if q() { break }
 246                 //     panic(...)
 247                 //   }
 248                 //
 249                 // where the effect of the 'break' is to cause the subsequent
 250                 // panic to be skipped. One possible improvement would be to
 251                 // track whether the currently enclosing loop is a "for {" or
 252                 // a for/range with condition, then use mayReturn only for the
 253                 // former. Note also that "break X" or "continue X" is treated
 254                 // the same as "goto", since we don't have a good way to track
 255                 // the target of the branch.
 256                 st = psMayReturn
 257                 n := n.(*ir.BranchStmt)
 258                 if n.Label != nil {
 259                         ffa.pessimize()
 260                 }
 261         case ir.OBLOCK:
 262                 n := n.(*ir.BlockStmt)
 263                 st = ffa.stateForList(n.List)
 264         case ir.OCASE:
 265                 if ccst, ok := n.(*ir.CaseClause); ok {
 266                         st = ffa.stateForList(ccst.Body)
 267                 } else if ccst, ok := n.(*ir.CommClause); ok {
 268                         st = ffa.stateForList(ccst.Body)
 269                 } else {
 270                         panic("unexpected")
 271                 }
 272         case ir.OIF:
 273                 n := n.(*ir.IfStmt)
 274                 st = branchCombine(ffa.stateForList(n.Body), ffa.stateForList(n.Else))
 275         case ir.OFOR:
 276                 // Treat for { XXX } like a block.
 277                 // Treat for <cond> { XXX } like an if statement with no else.
 278                 n := n.(*ir.ForStmt)
 279                 bst := ffa.stateForList(n.Body)
 280                 if n.Cond == nil {
 281                         st = bst
 282                 } else {
 283                         if bst == psMayReturn {
 284                                 st = psMayReturn
 285                         }
 286                 }
 287         case ir.ORANGE:
 288                 // Treat for range { XXX } like an if statement with no else.
 289                 n := n.(*ir.RangeStmt)
 290                 if ffa.stateForList(n.Body) == psMayReturn {
 291                         st = psMayReturn
 292                 }
 293         case ir.OGOTO:
 294                 // punt if we see even one goto. if we built a control
 295                 // flow graph we could do more, but this is just a tree walk.
 296                 ffa.pessimize()
 297         case ir.OSELECT:
 298                 // process selects for "may return" but not "always panics",
 299                 // the latter case seems very improbable.
 300                 n := n.(*ir.SelectStmt)
 301                 if len(n.Cases) != 0 {
 302                         st = psTop
 303                         for _, c := range n.Cases {
 304                                 st = branchCombine(ffa.stateForList(c.Body), st)
 305                         }
 306                 }
 307         case ir.OSWITCH:
 308                 n := n.(*ir.SwitchStmt)
 309                 if len(n.Cases) != 0 {
 310                         st = psTop
 311                         for _, c := range n.Cases {
 312                                 st = branchCombine(ffa.stateForList(c.Body), st)
 313                         }
 314                 }
 315
 316                 st, fall := psTop, psNoInfo
 317                 for i := len(n.Cases) - 1; i >= 0; i-- {
 318                         cas := n.Cases[i]
 319                         cst := ffa.stateForList(cas.Body)
 320                         endsInFallthrough := false
 321                         if len(cas.Body) != 0 {
 322                                 endsInFallthrough = cas.Body[0].Op() == ir.OFALL
 323                         }
 324                         if endsInFallthrough {
 325                                 cst = blockCombine(cst, fall)
 326                         }
 327                         st = branchCombine(st, cst)
 328                         fall = cst
 329                 }
 330         case ir.OFALL:
 331                 // Not important.
 332         case ir.ODCLFUNC, ir.ORECOVER, ir.OAS, ir.OAS2, ir.OAS2FUNC, ir.OASOP,
 333                 ir.OPRINTN, ir.OPRINT, ir.OLABEL, ir.OCALLINTER, ir.ODEFER,
 334                 ir.OSEND, ir.ORECV, ir.OSELRECV2, ir.OGO, ir.OAPPEND, ir.OAS2DOTTYPE,
 335                 ir.OAS2MAPR, ir.OGETG, ir.ODELETE, ir.OINLMARK, ir.OAS2RECV,
 336                 ir.OMIN, ir.OMAX, ir.OMAKE, ir.ORECOVERFP, ir.OGETCALLERSP:
 337                 // these should all be benign/uninteresting
 338         case ir.OTAILCALL, ir.OJUMPTABLE, ir.OTYPESW:
 339                 // don't expect to see these at all.
 340                 base.Fatalf("unexpected op %s in func %s",
 341                         n.Op().String(), ir.FuncName(ffa.fn))
 342         default:
 343                 base.Fatalf("%v: unhandled op %s in func %v",
 344                         ir.Line(n), n.Op().String(), ir.FuncName(ffa.fn))
 345         }
 346         if debugTrace&debugTraceFuncFlags != 0 {
 347                 fmt.Fprintf(os.Stderr, "=-= %v: visit n=%s returns %s\n",
 348                         ir.Line(n), n.Op().String(), st.String())
 349         }
 350         ffa.setstate(n, st)
 351 }
 352
 353 func (ffa *funcFlagsAnalyzer) nodeVisitPre(n ir.Node) {
 354 }