src/cmd/compile/internal/inline/inl.go

   1 // Copyright 2011 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 // The inlining facility makes 2 passes: first caninl determines which
   6 // functions are suitable for inlining, and for those that are it
   7 // saves a copy of the body. Then inlcalls walks each function body to
   8 // expand calls to inlinable functions.
   9 //
  10 // The Debug.l flag controls the aggressiveness. Note that main() swaps level 0 and 1,
  11 // making 1 the default and -l disable. Additional levels (beyond -l) may be buggy and
  12 // are not supported.
  13 //      0: disabled
  14 //      1: 80-nodes leaf functions, oneliners, panic, lazy typechecking (default)
  15 //      2: (unassigned)
  16 //      3: (unassigned)
  17 //      4: allow non-leaf functions
  18 //
  19 // At some point this may get another default and become switch-offable with -N.
  20 //
  21 // The -d typcheckinl flag enables early typechecking of all imported bodies,
  22 // which is useful to flush out bugs.
  23 //
  24 // The Debug.m flag enables diagnostic output.  a single -m is useful for verifying
  25 // which calls get inlined or not, more is for debugging, and may go away at any point.
  26
  27 package inline
  28
  29 import (
  30         "errors"
  31         "fmt"
  32         "go/constant"
  33         "strings"
  34
  35         "cmd/compile/internal/base"
  36         "cmd/compile/internal/ir"
  37         "cmd/compile/internal/logopt"
  38         "cmd/compile/internal/typecheck"
  39         "cmd/compile/internal/types"
  40         "cmd/internal/obj"
  41         "cmd/internal/src"
  42 )
  43
  44 // Inlining budget parameters, gathered in one place
  45 const (
  46         inlineMaxBudget       = 80
  47         inlineExtraAppendCost = 0
  48         // default is to inline if there's at most one call. -l=4 overrides this by using 1 instead.
  49         inlineExtraCallCost  = 57              // 57 was benchmarked to provided most benefit with no bad surprises; see https://github.com/golang/go/issues/19348#issuecomment-439370742
  50         inlineExtraPanicCost = 1               // do not penalize inlining panics.
  51         inlineExtraThrowCost = inlineMaxBudget // with current (2018-05/1.11) code, inlining runtime.throw does not help.
  52
  53         inlineBigFunctionNodes   = 5000 // Functions with this many nodes are considered "big".
  54         inlineBigFunctionMaxCost = 20   // Max cost of inlinee when inlining into a "big" function.
  55 )
  56
  57 func InlinePackage() {
  58         // Find functions that can be inlined and clone them before walk expands them.
  59         ir.VisitFuncsBottomUp(typecheck.Target.Decls, func(list []*ir.Func, recursive bool) {
  60                 numfns := numNonClosures(list)
  61                 for _, n := range list {
  62                         if !recursive || numfns > 1 {
  63                                 // We allow inlining if there is no
  64                                 // recursion, or the recursion cycle is
  65                                 // across more than one function.
  66                                 CanInline(n)
  67                         } else {
  68                                 if base.Flag.LowerM > 1 {
  69                                         fmt.Printf("%v: cannot inline %v: recursive\n", ir.Line(n), n.Nname)
  70                                 }
  71                         }
  72                         InlineCalls(n)
  73                 }
  74         })
  75 }
  76
  77 // Caninl determines whether fn is inlineable.
  78 // If so, CanInline saves fn->nbody in fn->inl and substitutes it with a copy.
  79 // fn and ->nbody will already have been typechecked.
  80 func CanInline(fn *ir.Func) {
  81         if fn.Nname == nil {
  82                 base.Fatalf("caninl no nname %+v", fn)
  83         }
  84
  85         var reason string // reason, if any, that the function was not inlined
  86         if base.Flag.LowerM > 1 || logopt.Enabled() {
  87                 defer func() {
  88                         if reason != "" {
  89                                 if base.Flag.LowerM > 1 {
  90                                         fmt.Printf("%v: cannot inline %v: %s\n", ir.Line(fn), fn.Nname, reason)
  91                                 }
  92                                 if logopt.Enabled() {
  93                                         logopt.LogOpt(fn.Pos(), "cannotInlineFunction", "inline", ir.FuncName(fn), reason)
  94                                 }
  95                         }
  96                 }()
  97         }
  98
  99         // If marked "go:noinline", don't inline
 100         if fn.Pragma&ir.Noinline != 0 {
 101                 reason = "marked go:noinline"
 102                 return
 103         }
 104
 105         // If marked "go:norace" and -race compilation, don't inline.
 106         if base.Flag.Race && fn.Pragma&ir.Norace != 0 {
 107                 reason = "marked go:norace with -race compilation"
 108                 return
 109         }
 110
 111         // If marked "go:nocheckptr" and -d checkptr compilation, don't inline.
 112         if base.Debug.Checkptr != 0 && fn.Pragma&ir.NoCheckPtr != 0 {
 113                 reason = "marked go:nocheckptr"
 114                 return
 115         }
 116
 117         // If marked "go:cgo_unsafe_args", don't inline, since the
 118         // function makes assumptions about its argument frame layout.
 119         if fn.Pragma&ir.CgoUnsafeArgs != 0 {
 120                 reason = "marked go:cgo_unsafe_args"
 121                 return
 122         }
 123
 124         // If marked as "go:uintptrescapes", don't inline, since the
 125         // escape information is lost during inlining.
 126         if fn.Pragma&ir.UintptrEscapes != 0 {
 127                 reason = "marked as having an escaping uintptr argument"
 128                 return
 129         }
 130
 131         // The nowritebarrierrec checker currently works at function
 132         // granularity, so inlining yeswritebarrierrec functions can
 133         // confuse it (#22342). As a workaround, disallow inlining
 134         // them for now.
 135         if fn.Pragma&ir.Yeswritebarrierrec != 0 {
 136                 reason = "marked go:yeswritebarrierrec"
 137                 return
 138         }
 139
 140         // If fn has no body (is defined outside of Go), cannot inline it.
 141         if len(fn.Body) == 0 {
 142                 reason = "no function body"
 143                 return
 144         }
 145
 146         if fn.Typecheck() == 0 {
 147                 base.Fatalf("caninl on non-typechecked function %v", fn)
 148         }
 149
 150         n := fn.Nname
 151         if n.Func.InlinabilityChecked() {
 152                 return
 153         }
 154         defer n.Func.SetInlinabilityChecked(true)
 155
 156         cc := int32(inlineExtraCallCost)
 157         if base.Flag.LowerL == 4 {
 158                 cc = 1 // this appears to yield better performance than 0.
 159         }
 160
 161         // At this point in the game the function we're looking at may
 162         // have "stale" autos, vars that still appear in the Dcl list, but
 163         // which no longer have any uses in the function body (due to
 164         // elimination by deadcode). We'd like to exclude these dead vars
 165         // when creating the "Inline.Dcl" field below; to accomplish this,
 166         // the hairyVisitor below builds up a map of used/referenced
 167         // locals, and we use this map to produce a pruned Inline.Dcl
 168         // list. See issue 25249 for more context.
 169
 170         visitor := hairyVisitor{
 171                 budget:        inlineMaxBudget,
 172                 extraCallCost: cc,
 173                 usedLocals:    make(map[*ir.Name]bool),
 174         }
 175         if visitor.tooHairy(fn) {
 176                 reason = visitor.reason
 177                 return
 178         }
 179
 180         n.Func.Inl = &ir.Inline{
 181                 Cost: inlineMaxBudget - visitor.budget,
 182                 Dcl:  pruneUnusedAutos(n.Defn.(*ir.Func).Dcl, &visitor),
 183                 Body: ir.DeepCopyList(src.NoXPos, fn.Body),
 184         }
 185
 186         if base.Flag.LowerM > 1 {
 187                 fmt.Printf("%v: can inline %v with cost %d as: %v { %v }\n", ir.Line(fn), n, inlineMaxBudget-visitor.budget, fn.Type(), ir.Nodes(n.Func.Inl.Body))
 188         } else if base.Flag.LowerM != 0 {
 189                 fmt.Printf("%v: can inline %v\n", ir.Line(fn), n)
 190         }
 191         if logopt.Enabled() {
 192                 logopt.LogOpt(fn.Pos(), "canInlineFunction", "inline", ir.FuncName(fn), fmt.Sprintf("cost: %d", inlineMaxBudget-visitor.budget))
 193         }
 194 }
 195
 196 // Inline_Flood marks n's inline body for export and recursively ensures
 197 // all called functions are marked too.
 198 func Inline_Flood(n *ir.Name, exportsym func(*ir.Name)) {
 199         if n == nil {
 200                 return
 201         }
 202         if n.Op() != ir.ONAME || n.Class != ir.PFUNC {
 203                 base.Fatalf("inlFlood: unexpected %v, %v, %v", n, n.Op(), n.Class)
 204         }
 205         fn := n.Func
 206         if fn == nil {
 207                 base.Fatalf("inlFlood: missing Func on %v", n)
 208         }
 209         if fn.Inl == nil {
 210                 return
 211         }
 212
 213         if fn.ExportInline() {
 214                 return
 215         }
 216         fn.SetExportInline(true)
 217
 218         typecheck.ImportedBody(fn)
 219
 220         // Recursively identify all referenced functions for
 221         // reexport. We want to include even non-called functions,
 222         // because after inlining they might be callable.
 223         ir.VisitList(ir.Nodes(fn.Inl.Body), func(n ir.Node) {
 224                 switch n.Op() {
 225                 case ir.OMETHEXPR, ir.ODOTMETH:
 226                         Inline_Flood(ir.MethodExprName(n), exportsym)
 227
 228                 case ir.ONAME:
 229                         n := n.(*ir.Name)
 230                         switch n.Class {
 231                         case ir.PFUNC:
 232                                 Inline_Flood(n, exportsym)
 233                                 exportsym(n)
 234                         case ir.PEXTERN:
 235                                 exportsym(n)
 236                         }
 237
 238                 case ir.OCALLPART:
 239                         // Okay, because we don't yet inline indirect
 240                         // calls to method values.
 241                 case ir.OCLOSURE:
 242                         // If the closure is inlinable, we'll need to
 243                         // flood it too. But today we don't support
 244                         // inlining functions that contain closures.
 245                         //
 246                         // When we do, we'll probably want:
 247                         //     inlFlood(n.Func.Closure.Func.Nname)
 248                         base.Fatalf("unexpected closure in inlinable function")
 249                 }
 250         })
 251 }
 252
 253 // hairyVisitor visits a function body to determine its inlining
 254 // hairiness and whether or not it can be inlined.
 255 type hairyVisitor struct {
 256         budget        int32
 257         reason        string
 258         extraCallCost int32
 259         usedLocals    map[*ir.Name]bool
 260         do            func(ir.Node) error
 261 }
 262
 263 var errBudget = errors.New("too expensive")
 264
 265 func (v *hairyVisitor) tooHairy(fn *ir.Func) bool {
 266         v.do = v.doNode // cache closure
 267
 268         err := errChildren(fn, v.do)
 269         if err != nil {
 270                 v.reason = err.Error()
 271                 return true
 272         }
 273         if v.budget < 0 {
 274                 v.reason = fmt.Sprintf("function too complex: cost %d exceeds budget %d", inlineMaxBudget-v.budget, inlineMaxBudget)
 275                 return true
 276         }
 277         return false
 278 }
 279
 280 func (v *hairyVisitor) doNode(n ir.Node) error {
 281         if n == nil {
 282                 return nil
 283         }
 284
 285         switch n.Op() {
 286         // Call is okay if inlinable and we have the budget for the body.
 287         case ir.OCALLFUNC:
 288                 n := n.(*ir.CallExpr)
 289                 // Functions that call runtime.getcaller{pc,sp} can not be inlined
 290                 // because getcaller{pc,sp} expect a pointer to the caller's first argument.
 291                 //
 292                 // runtime.throw is a "cheap call" like panic in normal code.
 293                 if n.X.Op() == ir.ONAME {
 294                         name := n.X.(*ir.Name)
 295                         if name.Class == ir.PFUNC && types.IsRuntimePkg(name.Sym().Pkg) {
 296                                 fn := name.Sym().Name
 297                                 if fn == "getcallerpc" || fn == "getcallersp" {
 298                                         return errors.New("call to " + fn)
 299                                 }
 300                                 if fn == "throw" {
 301                                         v.budget -= inlineExtraThrowCost
 302                                         break
 303                                 }
 304                         }
 305                 }
 306
 307                 if ir.IsIntrinsicCall(n) {
 308                         // Treat like any other node.
 309                         break
 310                 }
 311
 312                 if fn := inlCallee(n.X); fn != nil && fn.Inl != nil {
 313                         v.budget -= fn.Inl.Cost
 314                         break
 315                 }
 316
 317                 // Call cost for non-leaf inlining.
 318                 v.budget -= v.extraCallCost
 319
 320         // Call is okay if inlinable and we have the budget for the body.
 321         case ir.OCALLMETH:
 322                 n := n.(*ir.CallExpr)
 323                 t := n.X.Type()
 324                 if t == nil {
 325                         base.Fatalf("no function type for [%p] %+v\n", n.X, n.X)
 326                 }
 327                 fn := ir.MethodExprName(n.X).Func
 328                 if types.IsRuntimePkg(fn.Sym().Pkg) && fn.Sym().Name == "heapBits.nextArena" {
 329                         // Special case: explicitly allow
 330                         // mid-stack inlining of
 331                         // runtime.heapBits.next even though
 332                         // it calls slow-path
 333                         // runtime.heapBits.nextArena.
 334                         break
 335                 }
 336                 if fn.Inl != nil {
 337                         v.budget -= fn.Inl.Cost
 338                         break
 339                 }
 340                 // Call cost for non-leaf inlining.
 341                 v.budget -= v.extraCallCost
 342
 343         // Things that are too hairy, irrespective of the budget
 344         case ir.OCALL, ir.OCALLINTER:
 345                 // Call cost for non-leaf inlining.
 346                 v.budget -= v.extraCallCost
 347
 348         case ir.OPANIC:
 349                 v.budget -= inlineExtraPanicCost
 350
 351         case ir.ORECOVER:
 352                 // recover matches the argument frame pointer to find
 353                 // the right panic value, so it needs an argument frame.
 354                 return errors.New("call to recover")
 355
 356         case ir.OCLOSURE,
 357                 ir.ORANGE,
 358                 ir.OSELECT,
 359                 ir.OGO,
 360                 ir.ODEFER,
 361                 ir.ODCLTYPE, // can't print yet
 362                 ir.ORETJMP:
 363                 return errors.New("unhandled op " + n.Op().String())
 364
 365         case ir.OAPPEND:
 366                 v.budget -= inlineExtraAppendCost
 367
 368         case ir.ODCLCONST, ir.OFALL:
 369                 // These nodes don't produce code; omit from inlining budget.
 370                 return nil
 371
 372         case ir.OFOR, ir.OFORUNTIL:
 373                 n := n.(*ir.ForStmt)
 374                 if n.Label != nil {
 375                         return errors.New("labeled control")
 376                 }
 377         case ir.OSWITCH:
 378                 n := n.(*ir.SwitchStmt)
 379                 if n.Label != nil {
 380                         return errors.New("labeled control")
 381                 }
 382         // case ir.ORANGE, ir.OSELECT in "unhandled" above
 383
 384         case ir.OBREAK, ir.OCONTINUE:
 385                 n := n.(*ir.BranchStmt)
 386                 if n.Label != nil {
 387                         // Should have short-circuited due to labeled control error above.
 388                         base.Fatalf("unexpected labeled break/continue: %v", n)
 389                 }
 390
 391         case ir.OIF:
 392                 n := n.(*ir.IfStmt)
 393                 if ir.IsConst(n.Cond, constant.Bool) {
 394                         // This if and the condition cost nothing.
 395                         // TODO(rsc): It seems strange that we visit the dead branch.
 396                         if err := errList(n.Init(), v.do); err != nil {
 397                                 return err
 398                         }
 399                         if err := errList(n.Body, v.do); err != nil {
 400                                 return err
 401                         }
 402                         if err := errList(n.Else, v.do); err != nil {
 403                                 return err
 404                         }
 405                         return nil
 406                 }
 407
 408         case ir.ONAME:
 409                 n := n.(*ir.Name)
 410                 if n.Class == ir.PAUTO {
 411                         v.usedLocals[n] = true
 412                 }
 413
 414         case ir.OBLOCK:
 415                 // The only OBLOCK we should see at this point is an empty one.
 416                 // In any event, let the visitList(n.List()) below take care of the statements,
 417                 // and don't charge for the OBLOCK itself. The ++ undoes the -- below.
 418                 v.budget++
 419
 420         case ir.OCALLPART, ir.OSLICELIT:
 421                 v.budget-- // Hack for toolstash -cmp.
 422
 423         case ir.OMETHEXPR:
 424                 v.budget++ // Hack for toolstash -cmp.
 425         }
 426
 427         v.budget--
 428
 429         // When debugging, don't stop early, to get full cost of inlining this function
 430         if v.budget < 0 && base.Flag.LowerM < 2 && !logopt.Enabled() {
 431                 return errBudget
 432         }
 433
 434         return errChildren(n, v.do)
 435 }
 436
 437 func isBigFunc(fn *ir.Func) bool {
 438         budget := inlineBigFunctionNodes
 439         return ir.Any(fn, func(n ir.Node) bool {
 440                 budget--
 441                 return budget <= 0
 442         })
 443 }
 444
 445 // Inlcalls/nodelist/node walks fn's statements and expressions and substitutes any
 446 // calls made to inlineable functions. This is the external entry point.
 447 func InlineCalls(fn *ir.Func) {
 448         savefn := ir.CurFunc
 449         ir.CurFunc = fn
 450         maxCost := int32(inlineMaxBudget)
 451         if isBigFunc(fn) {
 452                 maxCost = inlineBigFunctionMaxCost
 453         }
 454         // Map to keep track of functions that have been inlined at a particular
 455         // call site, in order to stop inlining when we reach the beginning of a
 456         // recursion cycle again. We don't inline immediately recursive functions,
 457         // but allow inlining if there is a recursion cycle of many functions.
 458         // Most likely, the inlining will stop before we even hit the beginning of
 459         // the cycle again, but the map catches the unusual case.
 460         inlMap := make(map[*ir.Func]bool)
 461         var edit func(ir.Node) ir.Node
 462         edit = func(n ir.Node) ir.Node {
 463                 return inlnode(n, maxCost, inlMap, edit)
 464         }
 465         ir.EditChildren(fn, edit)
 466         ir.CurFunc = savefn
 467 }
 468
 469 // Turn an OINLCALL into a statement.
 470 func inlconv2stmt(inlcall *ir.InlinedCallExpr) ir.Node {
 471         n := ir.NewBlockStmt(inlcall.Pos(), nil)
 472         n.List = inlcall.Init()
 473         n.List.Append(inlcall.Body.Take()...)
 474         return n
 475 }
 476
 477 // Turn an OINLCALL into a single valued expression.
 478 // The result of inlconv2expr MUST be assigned back to n, e.g.
 479 //      n.Left = inlconv2expr(n.Left)
 480 func inlconv2expr(n *ir.InlinedCallExpr) ir.Node {
 481         r := n.ReturnVars[0]
 482         return ir.InitExpr(append(n.Init(), n.Body...), r)
 483 }
 484
 485 // Turn the rlist (with the return values) of the OINLCALL in
 486 // n into an expression list lumping the ninit and body
 487 // containing the inlined statements on the first list element so
 488 // order will be preserved. Used in return, oas2func and call
 489 // statements.
 490 func inlconv2list(n *ir.InlinedCallExpr) []ir.Node {
 491         if n.Op() != ir.OINLCALL || len(n.ReturnVars) == 0 {
 492                 base.Fatalf("inlconv2list %+v\n", n)
 493         }
 494
 495         s := n.ReturnVars
 496         s[0] = ir.InitExpr(append(n.Init(), n.Body...), s[0])
 497         return s
 498 }
 499
 500 // inlnode recurses over the tree to find inlineable calls, which will
 501 // be turned into OINLCALLs by mkinlcall. When the recursion comes
 502 // back up will examine left, right, list, rlist, ninit, ntest, nincr,
 503 // nbody and nelse and use one of the 4 inlconv/glue functions above
 504 // to turn the OINLCALL into an expression, a statement, or patch it
 505 // in to this nodes list or rlist as appropriate.
 506 // NOTE it makes no sense to pass the glue functions down the
 507 // recursion to the level where the OINLCALL gets created because they
 508 // have to edit /this/ n, so you'd have to push that one down as well,
 509 // but then you may as well do it here.  so this is cleaner and
 510 // shorter and less complicated.
 511 // The result of inlnode MUST be assigned back to n, e.g.
 512 //      n.Left = inlnode(n.Left)
 513 func inlnode(n ir.Node, maxCost int32, inlMap map[*ir.Func]bool, edit func(ir.Node) ir.Node) ir.Node {
 514         if n == nil {
 515                 return n
 516         }
 517
 518         switch n.Op() {
 519         case ir.ODEFER, ir.OGO:
 520                 n := n.(*ir.GoDeferStmt)
 521                 switch call := n.Call; call.Op() {
 522                 case ir.OCALLFUNC, ir.OCALLMETH:
 523                         call := call.(*ir.CallExpr)
 524                         call.NoInline = true
 525                 }
 526
 527         // TODO do them here (or earlier),
 528         // so escape analysis can avoid more heapmoves.
 529         case ir.OCLOSURE:
 530                 return n
 531         case ir.OCALLMETH:
 532                 // Prevent inlining some reflect.Value methods when using checkptr,
 533                 // even when package reflect was compiled without it (#35073).
 534                 n := n.(*ir.CallExpr)
 535                 if s := ir.MethodExprName(n.X).Sym(); base.Debug.Checkptr != 0 && types.IsReflectPkg(s.Pkg) && (s.Name == "Value.UnsafeAddr" || s.Name == "Value.Pointer") {
 536                         return n
 537                 }
 538         }
 539
 540         lno := ir.SetPos(n)
 541
 542         ir.EditChildren(n, edit)
 543
 544         if as := n; as.Op() == ir.OAS2FUNC {
 545                 as := as.(*ir.AssignListStmt)
 546                 if as.Rhs[0].Op() == ir.OINLCALL {
 547                         as.Rhs = inlconv2list(as.Rhs[0].(*ir.InlinedCallExpr))
 548                         as.SetOp(ir.OAS2)
 549                         as.SetTypecheck(0)
 550                         n = typecheck.Stmt(as)
 551                 }
 552         }
 553
 554         // with all the branches out of the way, it is now time to
 555         // transmogrify this node itself unless inhibited by the
 556         // switch at the top of this function.
 557         switch n.Op() {
 558         case ir.OCALLFUNC, ir.OCALLMETH:
 559                 n := n.(*ir.CallExpr)
 560                 if n.NoInline {
 561                         return n
 562                 }
 563         }
 564
 565         var call *ir.CallExpr
 566         switch n.Op() {
 567         case ir.OCALLFUNC:
 568                 call = n.(*ir.CallExpr)
 569                 if base.Flag.LowerM > 3 {
 570                         fmt.Printf("%v:call to func %+v\n", ir.Line(n), call.X)
 571                 }
 572                 if ir.IsIntrinsicCall(call) {
 573                         break
 574                 }
 575                 if fn := inlCallee(call.X); fn != nil && fn.Inl != nil {
 576                         n = mkinlcall(call, fn, maxCost, inlMap, edit)
 577                 }
 578
 579         case ir.OCALLMETH:
 580                 call = n.(*ir.CallExpr)
 581                 if base.Flag.LowerM > 3 {
 582                         fmt.Printf("%v:call to meth %v\n", ir.Line(n), call.X.(*ir.SelectorExpr).Sel)
 583                 }
 584
 585                 // typecheck should have resolved ODOTMETH->type, whose nname points to the actual function.
 586                 if call.X.Type() == nil {
 587                         base.Fatalf("no function type for [%p] %+v\n", call.X, call.X)
 588                 }
 589
 590                 n = mkinlcall(call, ir.MethodExprName(call.X).Func, maxCost, inlMap, edit)
 591         }
 592
 593         base.Pos = lno
 594
 595         if n.Op() == ir.OINLCALL {
 596                 ic := n.(*ir.InlinedCallExpr)
 597                 switch call.Use {
 598                 default:
 599                         ir.Dump("call", call)
 600                         base.Fatalf("call missing use")
 601                 case ir.CallUseExpr:
 602                         n = inlconv2expr(ic)
 603                 case ir.CallUseStmt:
 604                         n = inlconv2stmt(ic)
 605                 case ir.CallUseList:
 606                         // leave for caller to convert
 607                 }
 608         }
 609
 610         return n
 611 }
 612
 613 // inlCallee takes a function-typed expression and returns the underlying function ONAME
 614 // that it refers to if statically known. Otherwise, it returns nil.
 615 func inlCallee(fn ir.Node) *ir.Func {
 616         fn = ir.StaticValue(fn)
 617         switch fn.Op() {
 618         case ir.OMETHEXPR:
 619                 fn := fn.(*ir.SelectorExpr)
 620                 n := ir.MethodExprName(fn)
 621                 // Check that receiver type matches fn.X.
 622                 // TODO(mdempsky): Handle implicit dereference
 623                 // of pointer receiver argument?
 624                 if n == nil || !types.Identical(n.Type().Recv().Type, fn.X.Type()) {
 625                         return nil
 626                 }
 627                 return n.Func
 628         case ir.ONAME:
 629                 fn := fn.(*ir.Name)
 630                 if fn.Class == ir.PFUNC {
 631                         return fn.Func
 632                 }
 633         case ir.OCLOSURE:
 634                 fn := fn.(*ir.ClosureExpr)
 635                 c := fn.Func
 636                 CanInline(c)
 637                 return c
 638         }
 639         return nil
 640 }
 641
 642 func inlParam(t *types.Field, as ir.InitNode, inlvars map[*ir.Name]*ir.Name) ir.Node {
 643         if t.Nname == nil {
 644                 return ir.BlankNode
 645         }
 646         n := t.Nname.(*ir.Name)
 647         if ir.IsBlank(n) {
 648                 return ir.BlankNode
 649         }
 650         inlvar := inlvars[n]
 651         if inlvar == nil {
 652                 base.Fatalf("missing inlvar for %v", n)
 653         }
 654         as.PtrInit().Append(ir.NewDecl(base.Pos, ir.ODCL, inlvar))
 655         inlvar.Name().Defn = as
 656         return inlvar
 657 }
 658
 659 var inlgen int
 660
 661 // SSADumpInline gives the SSA back end a chance to dump the function
 662 // when producing output for debugging the compiler itself.
 663 var SSADumpInline = func(*ir.Func) {}
 664
 665 // If n is a call node (OCALLFUNC or OCALLMETH), and fn is an ONAME node for a
 666 // function with an inlinable body, return an OINLCALL node that can replace n.
 667 // The returned node's Ninit has the parameter assignments, the Nbody is the
 668 // inlined function body, and (List, Rlist) contain the (input, output)
 669 // parameters.
 670 // The result of mkinlcall MUST be assigned back to n, e.g.
 671 //      n.Left = mkinlcall(n.Left, fn, isddd)
 672 func mkinlcall(n *ir.CallExpr, fn *ir.Func, maxCost int32, inlMap map[*ir.Func]bool, edit func(ir.Node) ir.Node) ir.Node {
 673         if fn.Inl == nil {
 674                 if logopt.Enabled() {
 675                         logopt.LogOpt(n.Pos(), "cannotInlineCall", "inline", ir.FuncName(ir.CurFunc),
 676                                 fmt.Sprintf("%s cannot be inlined", ir.PkgFuncName(fn)))
 677                 }
 678                 return n
 679         }
 680         if fn.Inl.Cost > maxCost {
 681                 // The inlined function body is too big. Typically we use this check to restrict
 682                 // inlining into very big functions.  See issue 26546 and 17566.
 683                 if logopt.Enabled() {
 684                         logopt.LogOpt(n.Pos(), "cannotInlineCall", "inline", ir.FuncName(ir.CurFunc),
 685                                 fmt.Sprintf("cost %d of %s exceeds max large caller cost %d", fn.Inl.Cost, ir.PkgFuncName(fn), maxCost))
 686                 }
 687                 return n
 688         }
 689
 690         if fn == ir.CurFunc {
 691                 // Can't recursively inline a function into itself.
 692                 if logopt.Enabled() {
 693                         logopt.LogOpt(n.Pos(), "cannotInlineCall", "inline", fmt.Sprintf("recursive call to %s", ir.FuncName(ir.CurFunc)))
 694                 }
 695                 return n
 696         }
 697
 698         if base.Flag.Cfg.Instrumenting && types.IsRuntimePkg(fn.Sym().Pkg) {
 699                 // Runtime package must not be instrumented.
 700                 // Instrument skips runtime package. However, some runtime code can be
 701                 // inlined into other packages and instrumented there. To avoid this,
 702                 // we disable inlining of runtime functions when instrumenting.
 703                 // The example that we observed is inlining of LockOSThread,
 704                 // which lead to false race reports on m contents.
 705                 return n
 706         }
 707
 708         if inlMap[fn] {
 709                 if base.Flag.LowerM > 1 {
 710                         fmt.Printf("%v: cannot inline %v into %v: repeated recursive cycle\n", ir.Line(n), fn, ir.FuncName(ir.CurFunc))
 711                 }
 712                 return n
 713         }
 714         inlMap[fn] = true
 715         defer func() {
 716                 inlMap[fn] = false
 717         }()
 718         if base.Debug.TypecheckInl == 0 {
 719                 typecheck.ImportedBody(fn)
 720         }
 721
 722         // We have a function node, and it has an inlineable body.
 723         if base.Flag.LowerM > 1 {
 724                 fmt.Printf("%v: inlining call to %v %v { %v }\n", ir.Line(n), fn.Sym(), fn.Type(), ir.Nodes(fn.Inl.Body))
 725         } else if base.Flag.LowerM != 0 {
 726                 fmt.Printf("%v: inlining call to %v\n", ir.Line(n), fn)
 727         }
 728         if base.Flag.LowerM > 2 {
 729                 fmt.Printf("%v: Before inlining: %+v\n", ir.Line(n), n)
 730         }
 731
 732         SSADumpInline(fn)
 733
 734         ninit := n.Init()
 735
 736         // For normal function calls, the function callee expression
 737         // may contain side effects (e.g., added by addinit during
 738         // inlconv2expr or inlconv2list). Make sure to preserve these,
 739         // if necessary (#42703).
 740         if n.Op() == ir.OCALLFUNC {
 741                 callee := n.X
 742                 for callee.Op() == ir.OCONVNOP {
 743                         conv := callee.(*ir.ConvExpr)
 744                         ninit.Append(ir.TakeInit(conv)...)
 745                         callee = conv.X
 746                 }
 747                 if callee.Op() != ir.ONAME && callee.Op() != ir.OCLOSURE && callee.Op() != ir.OMETHEXPR {
 748                         base.Fatalf("unexpected callee expression: %v", callee)
 749                 }
 750         }
 751
 752         // Make temp names to use instead of the originals.
 753         inlvars := make(map[*ir.Name]*ir.Name)
 754
 755         // record formals/locals for later post-processing
 756         var inlfvars []*ir.Name
 757
 758         for _, ln := range fn.Inl.Dcl {
 759                 if ln.Op() != ir.ONAME {
 760                         continue
 761                 }
 762                 if ln.Class == ir.PPARAMOUT { // return values handled below.
 763                         continue
 764                 }
 765                 if ir.IsParamStackCopy(ln) { // ignore the on-stack copy of a parameter that moved to the heap
 766                         // TODO(mdempsky): Remove once I'm confident
 767                         // this never actually happens. We currently
 768                         // perform inlining before escape analysis, so
 769                         // nothing should have moved to the heap yet.
 770                         base.Fatalf("impossible: %v", ln)
 771                 }
 772                 inlf := typecheck.Expr(inlvar(ln)).(*ir.Name)
 773                 inlvars[ln] = inlf
 774                 if base.Flag.GenDwarfInl > 0 {
 775                         if ln.Class == ir.PPARAM {
 776                                 inlf.Name().SetInlFormal(true)
 777                         } else {
 778                                 inlf.Name().SetInlLocal(true)
 779                         }
 780                         inlf.SetPos(ln.Pos())
 781                         inlfvars = append(inlfvars, inlf)
 782                 }
 783         }
 784
 785         nreturns := 0
 786         ir.VisitList(ir.Nodes(fn.Inl.Body), func(n ir.Node) {
 787                 if n != nil && n.Op() == ir.ORETURN {
 788                         nreturns++
 789                 }
 790         })
 791
 792         // We can delay declaring+initializing result parameters if:
 793         // (1) there's only one "return" statement in the inlined
 794         // function, and (2) the result parameters aren't named.
 795         delayretvars := nreturns == 1
 796
 797         // temporaries for return values.
 798         var retvars []ir.Node
 799         for i, t := range fn.Type().Results().Fields().Slice() {
 800                 var m *ir.Name
 801                 if nn := t.Nname; nn != nil && !ir.IsBlank(nn.(*ir.Name)) && !strings.HasPrefix(nn.Sym().Name, "~r") {
 802                         n := nn.(*ir.Name)
 803                         m = inlvar(n)
 804                         m = typecheck.Expr(m).(*ir.Name)
 805                         inlvars[n] = m
 806                         delayretvars = false // found a named result parameter
 807                 } else {
 808                         // anonymous return values, synthesize names for use in assignment that replaces return
 809                         m = retvar(t, i)
 810                 }
 811
 812                 if base.Flag.GenDwarfInl > 0 {
 813                         // Don't update the src.Pos on a return variable if it
 814                         // was manufactured by the inliner (e.g. "~R2"); such vars
 815                         // were not part of the original callee.
 816                         if !strings.HasPrefix(m.Sym().Name, "~R") {
 817                                 m.Name().SetInlFormal(true)
 818                                 m.SetPos(t.Pos)
 819                                 inlfvars = append(inlfvars, m)
 820                         }
 821                 }
 822
 823                 retvars = append(retvars, m)
 824         }
 825
 826         // Assign arguments to the parameters' temp names.
 827         as := ir.NewAssignListStmt(base.Pos, ir.OAS2, nil, nil)
 828         as.Def = true
 829         if n.Op() == ir.OCALLMETH {
 830                 sel := n.X.(*ir.SelectorExpr)
 831                 if sel.X == nil {
 832                         base.Fatalf("method call without receiver: %+v", n)
 833                 }
 834                 as.Rhs.Append(sel.X)
 835         }
 836         as.Rhs.Append(n.Args...)
 837
 838         // For non-dotted calls to variadic functions, we assign the
 839         // variadic parameter's temp name separately.
 840         var vas *ir.AssignStmt
 841
 842         if recv := fn.Type().Recv(); recv != nil {
 843                 as.Lhs.Append(inlParam(recv, as, inlvars))
 844         }
 845         for _, param := range fn.Type().Params().Fields().Slice() {
 846                 // For ordinary parameters or variadic parameters in
 847                 // dotted calls, just add the variable to the
 848                 // assignment list, and we're done.
 849                 if !param.IsDDD() || n.IsDDD {
 850                         as.Lhs.Append(inlParam(param, as, inlvars))
 851                         continue
 852                 }
 853
 854                 // Otherwise, we need to collect the remaining values
 855                 // to pass as a slice.
 856
 857                 x := len(as.Lhs)
 858                 for len(as.Lhs) < len(as.Rhs) {
 859                         as.Lhs.Append(argvar(param.Type, len(as.Lhs)))
 860                 }
 861                 varargs := as.Lhs[x:]
 862
 863                 vas = ir.NewAssignStmt(base.Pos, nil, nil)
 864                 vas.X = inlParam(param, vas, inlvars)
 865                 if len(varargs) == 0 {
 866                         vas.Y = typecheck.NodNil()
 867                         vas.Y.SetType(param.Type)
 868                 } else {
 869                         lit := ir.NewCompLitExpr(base.Pos, ir.OCOMPLIT, ir.TypeNode(param.Type), nil)
 870                         lit.List = varargs
 871                         vas.Y = lit
 872                 }
 873         }
 874
 875         if len(as.Rhs) != 0 {
 876                 ninit.Append(typecheck.Stmt(as))
 877         }
 878
 879         if vas != nil {
 880                 ninit.Append(typecheck.Stmt(vas))
 881         }
 882
 883         if !delayretvars {
 884                 // Zero the return parameters.
 885                 for _, n := range retvars {
 886                         ninit.Append(ir.NewDecl(base.Pos, ir.ODCL, n.(*ir.Name)))
 887                         ras := ir.NewAssignStmt(base.Pos, n, nil)
 888                         ninit.Append(typecheck.Stmt(ras))
 889                 }
 890         }
 891
 892         retlabel := typecheck.AutoLabel(".i")
 893
 894         inlgen++
 895
 896         parent := -1
 897         if b := base.Ctxt.PosTable.Pos(n.Pos()).Base(); b != nil {
 898                 parent = b.InliningIndex()
 899         }
 900
 901         sym := fn.Linksym()
 902         newIndex := base.Ctxt.InlTree.Add(parent, n.Pos(), sym)
 903
 904         // Add an inline mark just before the inlined body.
 905         // This mark is inline in the code so that it's a reasonable spot
 906         // to put a breakpoint. Not sure if that's really necessary or not
 907         // (in which case it could go at the end of the function instead).
 908         // Note issue 28603.
 909         inlMark := ir.NewInlineMarkStmt(base.Pos, types.BADWIDTH)
 910         inlMark.SetPos(n.Pos().WithIsStmt())
 911         inlMark.Index = int64(newIndex)
 912         ninit.Append(inlMark)
 913
 914         if base.Flag.GenDwarfInl > 0 {
 915                 if !sym.WasInlined() {
 916                         base.Ctxt.DwFixups.SetPrecursorFunc(sym, fn)
 917                         sym.Set(obj.AttrWasInlined, true)
 918                 }
 919         }
 920
 921         subst := inlsubst{
 922                 retlabel:     retlabel,
 923                 retvars:      retvars,
 924                 delayretvars: delayretvars,
 925                 inlvars:      inlvars,
 926                 bases:        make(map[*src.PosBase]*src.PosBase),
 927                 newInlIndex:  newIndex,
 928         }
 929         subst.edit = subst.node
 930
 931         body := subst.list(ir.Nodes(fn.Inl.Body))
 932
 933         lab := ir.NewLabelStmt(base.Pos, retlabel)
 934         body = append(body, lab)
 935
 936         typecheck.Stmts(body)
 937
 938         if base.Flag.GenDwarfInl > 0 {
 939                 for _, v := range inlfvars {
 940                         v.SetPos(subst.updatedPos(v.Pos()))
 941                 }
 942         }
 943
 944         //dumplist("ninit post", ninit);
 945
 946         call := ir.NewInlinedCallExpr(base.Pos, nil, nil)
 947         *call.PtrInit() = ninit
 948         call.Body = body
 949         call.ReturnVars = retvars
 950         call.SetType(n.Type())
 951         call.SetTypecheck(1)
 952
 953         // transitive inlining
 954         // might be nice to do this before exporting the body,
 955         // but can't emit the body with inlining expanded.
 956         // instead we emit the things that the body needs
 957         // and each use must redo the inlining.
 958         // luckily these are small.
 959         ir.EditChildren(call, edit)
 960
 961         if base.Flag.LowerM > 2 {
 962                 fmt.Printf("%v: After inlining %+v\n\n", ir.Line(call), call)
 963         }
 964
 965         return call
 966 }
 967
 968 // Every time we expand a function we generate a new set of tmpnames,
 969 // PAUTO's in the calling functions, and link them off of the
 970 // PPARAM's, PAUTOS and PPARAMOUTs of the called function.
 971 func inlvar(var_ *ir.Name) *ir.Name {
 972         if base.Flag.LowerM > 3 {
 973                 fmt.Printf("inlvar %+v\n", var_)
 974         }
 975
 976         n := typecheck.NewName(var_.Sym())
 977         n.SetType(var_.Type())
 978         n.Class = ir.PAUTO
 979         n.SetUsed(true)
 980         n.Curfn = ir.CurFunc // the calling function, not the called one
 981         n.SetAddrtaken(var_.Addrtaken())
 982
 983         ir.CurFunc.Dcl = append(ir.CurFunc.Dcl, n)
 984         return n
 985 }
 986
 987 // Synthesize a variable to store the inlined function's results in.
 988 func retvar(t *types.Field, i int) *ir.Name {
 989         n := typecheck.NewName(typecheck.LookupNum("~R", i))
 990         n.SetType(t.Type)
 991         n.Class = ir.PAUTO
 992         n.SetUsed(true)
 993         n.Curfn = ir.CurFunc // the calling function, not the called one
 994         ir.CurFunc.Dcl = append(ir.CurFunc.Dcl, n)
 995         return n
 996 }
 997
 998 // Synthesize a variable to store the inlined function's arguments
 999 // when they come from a multiple return call.
1000 func argvar(t *types.Type, i int) ir.Node {
1001         n := typecheck.NewName(typecheck.LookupNum("~arg", i))
1002         n.SetType(t.Elem())
1003         n.Class = ir.PAUTO
1004         n.SetUsed(true)
1005         n.Curfn = ir.CurFunc // the calling function, not the called one
1006         ir.CurFunc.Dcl = append(ir.CurFunc.Dcl, n)
1007         return n
1008 }
1009
1010 // The inlsubst type implements the actual inlining of a single
1011 // function call.
1012 type inlsubst struct {
1013         // Target of the goto substituted in place of a return.
1014         retlabel *types.Sym
1015
1016         // Temporary result variables.
1017         retvars []ir.Node
1018
1019         // Whether result variables should be initialized at the
1020         // "return" statement.
1021         delayretvars bool
1022
1023         inlvars map[*ir.Name]*ir.Name
1024
1025         // bases maps from original PosBase to PosBase with an extra
1026         // inlined call frame.
1027         bases map[*src.PosBase]*src.PosBase
1028
1029         // newInlIndex is the index of the inlined call frame to
1030         // insert for inlined nodes.
1031         newInlIndex int
1032
1033         edit func(ir.Node) ir.Node // cached copy of subst.node method value closure
1034 }
1035
1036 // list inlines a list of nodes.
1037 func (subst *inlsubst) list(ll ir.Nodes) []ir.Node {
1038         s := make([]ir.Node, 0, len(ll))
1039         for _, n := range ll {
1040                 s = append(s, subst.node(n))
1041         }
1042         return s
1043 }
1044
1045 // node recursively copies a node from the saved pristine body of the
1046 // inlined function, substituting references to input/output
1047 // parameters with ones to the tmpnames, and substituting returns with
1048 // assignments to the output.
1049 func (subst *inlsubst) node(n ir.Node) ir.Node {
1050         if n == nil {
1051                 return nil
1052         }
1053
1054         switch n.Op() {
1055         case ir.ONAME:
1056                 n := n.(*ir.Name)
1057
1058                 // Handle captured variables when inlining closures.
1059                 if n.IsClosureVar() {
1060                         o := n.Outer
1061
1062                         // make sure the outer param matches the inlining location
1063                         // NB: if we enabled inlining of functions containing OCLOSURE or refined
1064                         // the reassigned check via some sort of copy propagation this would most
1065                         // likely need to be changed to a loop to walk up to the correct Param
1066                         if o == nil || o.Curfn != ir.CurFunc {
1067                                 base.Fatalf("%v: unresolvable capture %v\n", ir.Line(n), n)
1068                         }
1069
1070                         if base.Flag.LowerM > 2 {
1071                                 fmt.Printf("substituting captured name %+v  ->  %+v\n", n, o)
1072                         }
1073                         return o
1074                 }
1075
1076                 if inlvar := subst.inlvars[n]; inlvar != nil { // These will be set during inlnode
1077                         if base.Flag.LowerM > 2 {
1078                                 fmt.Printf("substituting name %+v  ->  %+v\n", n, inlvar)
1079                         }
1080                         return inlvar
1081                 }
1082
1083                 if base.Flag.LowerM > 2 {
1084                         fmt.Printf("not substituting name %+v\n", n)
1085                 }
1086                 return n
1087
1088         case ir.OMETHEXPR:
1089                 n := n.(*ir.SelectorExpr)
1090                 return n
1091
1092         case ir.OLITERAL, ir.ONIL, ir.OTYPE:
1093                 // If n is a named constant or type, we can continue
1094                 // using it in the inline copy. Otherwise, make a copy
1095                 // so we can update the line number.
1096                 if n.Sym() != nil {
1097                         return n
1098                 }
1099
1100         case ir.ORETURN:
1101                 // Since we don't handle bodies with closures,
1102                 // this return is guaranteed to belong to the current inlined function.
1103                 n := n.(*ir.ReturnStmt)
1104                 init := subst.list(n.Init())
1105                 if len(subst.retvars) != 0 && len(n.Results) != 0 {
1106                         as := ir.NewAssignListStmt(base.Pos, ir.OAS2, nil, nil)
1107
1108                         // Make a shallow copy of retvars.
1109                         // Otherwise OINLCALL.Rlist will be the same list,
1110                         // and later walk and typecheck may clobber it.
1111                         for _, n := range subst.retvars {
1112                                 as.Lhs.Append(n)
1113                         }
1114                         as.Rhs = subst.list(n.Results)
1115
1116                         if subst.delayretvars {
1117                                 for _, n := range as.Lhs {
1118                                         as.PtrInit().Append(ir.NewDecl(base.Pos, ir.ODCL, n.(*ir.Name)))
1119                                         n.Name().Defn = as
1120                                 }
1121                         }
1122
1123                         init = append(init, typecheck.Stmt(as))
1124                 }
1125                 init = append(init, ir.NewBranchStmt(base.Pos, ir.OGOTO, subst.retlabel))
1126                 typecheck.Stmts(init)
1127                 return ir.NewBlockStmt(base.Pos, init)
1128
1129         case ir.OGOTO:
1130                 n := n.(*ir.BranchStmt)
1131                 m := ir.Copy(n).(*ir.BranchStmt)
1132                 m.SetPos(subst.updatedPos(m.Pos()))
1133                 *m.PtrInit() = nil
1134                 p := fmt.Sprintf("%s·%d", n.Label.Name, inlgen)
1135                 m.Label = typecheck.Lookup(p)
1136                 return m
1137
1138         case ir.OLABEL:
1139                 n := n.(*ir.LabelStmt)
1140                 m := ir.Copy(n).(*ir.LabelStmt)
1141                 m.SetPos(subst.updatedPos(m.Pos()))
1142                 *m.PtrInit() = nil
1143                 p := fmt.Sprintf("%s·%d", n.Label.Name, inlgen)
1144                 m.Label = typecheck.Lookup(p)
1145                 return m
1146         }
1147
1148         if n.Op() == ir.OCLOSURE {
1149                 base.Fatalf("cannot inline function containing closure: %+v", n)
1150         }
1151
1152         m := ir.Copy(n)
1153         m.SetPos(subst.updatedPos(m.Pos()))
1154         ir.EditChildren(m, subst.edit)
1155         return m
1156 }
1157
1158 func (subst *inlsubst) updatedPos(xpos src.XPos) src.XPos {
1159         pos := base.Ctxt.PosTable.Pos(xpos)
1160         oldbase := pos.Base() // can be nil
1161         newbase := subst.bases[oldbase]
1162         if newbase == nil {
1163                 newbase = src.NewInliningBase(oldbase, subst.newInlIndex)
1164                 subst.bases[oldbase] = newbase
1165         }
1166         pos.SetBase(newbase)
1167         return base.Ctxt.PosTable.XPos(pos)
1168 }
1169
1170 func pruneUnusedAutos(ll []*ir.Name, vis *hairyVisitor) []*ir.Name {
1171         s := make([]*ir.Name, 0, len(ll))
1172         for _, n := range ll {
1173                 if n.Class == ir.PAUTO {
1174                         if _, found := vis.usedLocals[n]; !found {
1175                                 continue
1176                         }
1177                 }
1178                 s = append(s, n)
1179         }
1180         return s
1181 }
1182
1183 // numNonClosures returns the number of functions in list which are not closures.
1184 func numNonClosures(list []*ir.Func) int {
1185         count := 0
1186         for _, fn := range list {
1187                 if fn.OClosure == nil {
1188                         count++
1189                 }
1190         }
1191         return count
1192 }
1193
1194 // TODO(mdempsky): Update inl.go to use ir.DoChildren directly.
1195 func errChildren(n ir.Node, do func(ir.Node) error) (err error) {
1196         ir.DoChildren(n, func(x ir.Node) bool {
1197                 err = do(x)
1198                 return err != nil
1199         })
1200         return
1201 }
1202 func errList(list []ir.Node, do func(ir.Node) error) error {
1203         for _, x := range list {
1204                 if x != nil {
1205                         if err := do(x); err != nil {
1206                                 return err
1207                         }
1208                 }
1209         }
1210         return nil
1211 }