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