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 InlineCalls 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         "fmt"
  31         "go/constant"
  32         "strings"
  33
  34         "cmd/compile/internal/base"
  35         "cmd/compile/internal/ir"
  36         "cmd/compile/internal/logopt"
  37         "cmd/compile/internal/typecheck"
  38         "cmd/compile/internal/types"
  39         "cmd/internal/obj"
  40         "cmd/internal/src"
  41 )
  42
  43 // Inlining budget parameters, gathered in one place
  44 const (
  45         inlineMaxBudget       = 80
  46         inlineExtraAppendCost = 0
  47         // default is to inline if there's at most one call. -l=4 overrides this by using 1 instead.
  48         inlineExtraCallCost  = 57              // 57 was benchmarked to provided most benefit with no bad surprises; see https://github.com/golang/go/issues/19348#issuecomment-439370742
  49         inlineExtraPanicCost = 1               // do not penalize inlining panics.
  50         inlineExtraThrowCost = inlineMaxBudget // with current (2018-05/1.11) code, inlining runtime.throw does not help.
  51
  52         inlineBigFunctionNodes   = 5000 // Functions with this many nodes are considered "big".
  53         inlineBigFunctionMaxCost = 20   // Max cost of inlinee when inlining into a "big" function.
  54 )
  55
  56 // InlinePackage finds functions that can be inlined and clones them before walk expands them.
  57 func InlinePackage() {
  58         ir.VisitFuncsBottomUp(typecheck.Target.Decls, func(list []*ir.Func, recursive bool) {
  59                 numfns := numNonClosures(list)
  60                 for _, n := range list {
  61                         if !recursive || numfns > 1 {
  62                                 // We allow inlining if there is no
  63                                 // recursion, or the recursion cycle is
  64                                 // across more than one function.
  65                                 CanInline(n)
  66                         } else {
  67                                 if base.Flag.LowerM > 1 {
  68                                         fmt.Printf("%v: cannot inline %v: recursive\n", ir.Line(n), n.Nname)
  69                                 }
  70                         }
  71                         InlineCalls(n)
  72                 }
  73         })
  74 }
  75
  76 // CanInline determines whether fn is inlineable.
  77 // If so, CanInline saves copies of fn.Body and fn.Dcl in fn.Inl.
  78 // fn and fn.Body will already have been typechecked.
  79 func CanInline(fn *ir.Func) {
  80         if fn.Nname == nil {
  81                 base.Fatalf("CanInline no nname %+v", fn)
  82         }
  83
  84         var reason string // reason, if any, that the function was not inlined
  85         if base.Flag.LowerM > 1 || logopt.Enabled() {
  86                 defer func() {
  87                         if reason != "" {
  88                                 if base.Flag.LowerM > 1 {
  89                                         fmt.Printf("%v: cannot inline %v: %s\n", ir.Line(fn), fn.Nname, reason)
  90                                 }
  91                                 if logopt.Enabled() {
  92                                         logopt.LogOpt(fn.Pos(), "cannotInlineFunction", "inline", ir.FuncName(fn), reason)
  93                                 }
  94                         }
  95                 }()
  96         }
  97
  98         // If marked "go:noinline", don't inline
  99         if fn.Pragma&ir.Noinline != 0 {
 100                 reason = "marked go:noinline"
 101                 return
 102         }
 103
 104         // If marked "go:norace" and -race compilation, don't inline.
 105         if base.Flag.Race && fn.Pragma&ir.Norace != 0 {
 106                 reason = "marked go:norace with -race compilation"
 107                 return
 108         }
 109
 110         // If marked "go:nocheckptr" and -d checkptr compilation, don't inline.
 111         if base.Debug.Checkptr != 0 && fn.Pragma&ir.NoCheckPtr != 0 {
 112                 reason = "marked go:nocheckptr"
 113                 return
 114         }
 115
 116         // If marked "go:cgo_unsafe_args", don't inline, since the
 117         // function makes assumptions about its argument frame layout.
 118         if fn.Pragma&ir.CgoUnsafeArgs != 0 {
 119                 reason = "marked go:cgo_unsafe_args"
 120                 return
 121         }
 122
 123         // If marked as "go:uintptrkeepalive", don't inline, since the
 124         // keep alive information is lost during inlining.
 125         //
 126         // TODO(prattmic): This is handled on calls during escape analysis,
 127         // which is after inlining. Move prior to inlining so the keep-alive is
 128         // maintained after inlining.
 129         if fn.Pragma&ir.UintptrKeepAlive != 0 {
 130                 reason = "marked as having a keep-alive uintptr argument"
 131                 return
 132         }
 133
 134         // If marked as "go:uintptrescapes", don't inline, since the
 135         // escape information is lost during inlining.
 136         if fn.Pragma&ir.UintptrEscapes != 0 {
 137                 reason = "marked as having an escaping uintptr argument"
 138                 return
 139         }
 140
 141         // The nowritebarrierrec checker currently works at function
 142         // granularity, so inlining yeswritebarrierrec functions can
 143         // confuse it (#22342). As a workaround, disallow inlining
 144         // them for now.
 145         if fn.Pragma&ir.Yeswritebarrierrec != 0 {
 146                 reason = "marked go:yeswritebarrierrec"
 147                 return
 148         }
 149
 150         // If fn has no body (is defined outside of Go), cannot inline it.
 151         if len(fn.Body) == 0 {
 152                 reason = "no function body"
 153                 return
 154         }
 155
 156         if fn.Typecheck() == 0 {
 157                 base.Fatalf("CanInline on non-typechecked function %v", fn)
 158         }
 159
 160         n := fn.Nname
 161         if n.Func.InlinabilityChecked() {
 162                 return
 163         }
 164         defer n.Func.SetInlinabilityChecked(true)
 165
 166         cc := int32(inlineExtraCallCost)
 167         if base.Flag.LowerL == 4 {
 168                 cc = 1 // this appears to yield better performance than 0.
 169         }
 170
 171         // At this point in the game the function we're looking at may
 172         // have "stale" autos, vars that still appear in the Dcl list, but
 173         // which no longer have any uses in the function body (due to
 174         // elimination by deadcode). We'd like to exclude these dead vars
 175         // when creating the "Inline.Dcl" field below; to accomplish this,
 176         // the hairyVisitor below builds up a map of used/referenced
 177         // locals, and we use this map to produce a pruned Inline.Dcl
 178         // list. See issue 25249 for more context.
 179
 180         visitor := hairyVisitor{
 181                 budget:        inlineMaxBudget,
 182                 extraCallCost: cc,
 183         }
 184         if visitor.tooHairy(fn) {
 185                 reason = visitor.reason
 186                 return
 187         }
 188
 189         n.Func.Inl = &ir.Inline{
 190                 Cost: inlineMaxBudget - visitor.budget,
 191                 Dcl:  pruneUnusedAutos(n.Defn.(*ir.Func).Dcl, &visitor),
 192                 Body: inlcopylist(fn.Body),
 193
 194                 CanDelayResults: canDelayResults(fn),
 195         }
 196
 197         if base.Flag.LowerM > 1 {
 198                 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))
 199         } else if base.Flag.LowerM != 0 {
 200                 fmt.Printf("%v: can inline %v\n", ir.Line(fn), n)
 201         }
 202         if logopt.Enabled() {
 203                 logopt.LogOpt(fn.Pos(), "canInlineFunction", "inline", ir.FuncName(fn), fmt.Sprintf("cost: %d", inlineMaxBudget-visitor.budget))
 204         }
 205 }
 206
 207 // canDelayResults reports whether inlined calls to fn can delay
 208 // declaring the result parameter until the "return" statement.
 209 func canDelayResults(fn *ir.Func) bool {
 210         // We can delay declaring+initializing result parameters if:
 211         // (1) there's exactly one "return" statement in the inlined function;
 212         // (2) it's not an empty return statement (#44355); and
 213         // (3) the result parameters aren't named.
 214
 215         nreturns := 0
 216         ir.VisitList(fn.Body, func(n ir.Node) {
 217                 if n, ok := n.(*ir.ReturnStmt); ok {
 218                         nreturns++
 219                         if len(n.Results) == 0 {
 220                                 nreturns++ // empty return statement (case 2)
 221                         }
 222                 }
 223         })
 224
 225         if nreturns != 1 {
 226                 return false // not exactly one return statement (case 1)
 227         }
 228
 229         // temporaries for return values.
 230         for _, param := range fn.Type().Results().FieldSlice() {
 231                 if sym := types.OrigSym(param.Sym); sym != nil && !sym.IsBlank() {
 232                         return false // found a named result parameter (case 3)
 233                 }
 234         }
 235
 236         return true
 237 }
 238
 239 // hairyVisitor visits a function body to determine its inlining
 240 // hairiness and whether or not it can be inlined.
 241 type hairyVisitor struct {
 242         budget        int32
 243         reason        string
 244         extraCallCost int32
 245         usedLocals    ir.NameSet
 246         do            func(ir.Node) bool
 247 }
 248
 249 func (v *hairyVisitor) tooHairy(fn *ir.Func) bool {
 250         v.do = v.doNode // cache closure
 251         if ir.DoChildren(fn, v.do) {
 252                 return true
 253         }
 254         if v.budget < 0 {
 255                 v.reason = fmt.Sprintf("function too complex: cost %d exceeds budget %d", inlineMaxBudget-v.budget, inlineMaxBudget)
 256                 return true
 257         }
 258         return false
 259 }
 260
 261 func (v *hairyVisitor) doNode(n ir.Node) bool {
 262         if n == nil {
 263                 return false
 264         }
 265         switch n.Op() {
 266         // Call is okay if inlinable and we have the budget for the body.
 267         case ir.OCALLFUNC:
 268                 n := n.(*ir.CallExpr)
 269                 // Functions that call runtime.getcaller{pc,sp} can not be inlined
 270                 // because getcaller{pc,sp} expect a pointer to the caller's first argument.
 271                 //
 272                 // runtime.throw is a "cheap call" like panic in normal code.
 273                 if n.X.Op() == ir.ONAME {
 274                         name := n.X.(*ir.Name)
 275                         if name.Class == ir.PFUNC && types.IsRuntimePkg(name.Sym().Pkg) {
 276                                 fn := name.Sym().Name
 277                                 if fn == "getcallerpc" || fn == "getcallersp" {
 278                                         v.reason = "call to " + fn
 279                                         return true
 280                                 }
 281                                 if fn == "throw" {
 282                                         v.budget -= inlineExtraThrowCost
 283                                         break
 284                                 }
 285                         }
 286                 }
 287                 if n.X.Op() == ir.OMETHEXPR {
 288                         if meth := ir.MethodExprName(n.X); meth != nil {
 289                                 if fn := meth.Func; fn != nil {
 290                                         s := fn.Sym()
 291                                         var cheap bool
 292                                         if types.IsRuntimePkg(s.Pkg) && s.Name == "heapBits.nextArena" {
 293                                                 // Special case: explicitly allow mid-stack inlining of
 294                                                 // runtime.heapBits.next even though it calls slow-path
 295                                                 // runtime.heapBits.nextArena.
 296                                                 cheap = true
 297                                         }
 298                                         // Special case: on architectures that can do unaligned loads,
 299                                         // explicitly mark encoding/binary methods as cheap,
 300                                         // because in practice they are, even though our inlining
 301                                         // budgeting system does not see that. See issue 42958.
 302                                         if base.Ctxt.Arch.CanMergeLoads && s.Pkg.Path == "encoding/binary" {
 303                                                 switch s.Name {
 304                                                 case "littleEndian.Uint64", "littleEndian.Uint32", "littleEndian.Uint16",
 305                                                         "bigEndian.Uint64", "bigEndian.Uint32", "bigEndian.Uint16",
 306                                                         "littleEndian.PutUint64", "littleEndian.PutUint32", "littleEndian.PutUint16",
 307                                                         "bigEndian.PutUint64", "bigEndian.PutUint32", "bigEndian.PutUint16",
 308                                                         "littleEndian.AppendUint64", "littleEndian.AppendUint32", "littleEndian.AppendUint16",
 309                                                         "bigEndian.AppendUint64", "bigEndian.AppendUint32", "bigEndian.AppendUint16":
 310                                                         cheap = true
 311                                                 }
 312                                         }
 313                                         if cheap {
 314                                                 break // treat like any other node, that is, cost of 1
 315                                         }
 316                                 }
 317                         }
 318                 }
 319
 320                 if ir.IsIntrinsicCall(n) {
 321                         // Treat like any other node.
 322                         break
 323                 }
 324
 325                 if fn := inlCallee(n.X); fn != nil && typecheck.HaveInlineBody(fn) {
 326                         v.budget -= fn.Inl.Cost
 327                         break
 328                 }
 329
 330                 // Call cost for non-leaf inlining.
 331                 v.budget -= v.extraCallCost
 332
 333         case ir.OCALLMETH:
 334                 base.FatalfAt(n.Pos(), "OCALLMETH missed by typecheck")
 335
 336         // Things that are too hairy, irrespective of the budget
 337         case ir.OCALL, ir.OCALLINTER:
 338                 // Call cost for non-leaf inlining.
 339                 v.budget -= v.extraCallCost
 340
 341         case ir.OPANIC:
 342                 n := n.(*ir.UnaryExpr)
 343                 if n.X.Op() == ir.OCONVIFACE && n.X.(*ir.ConvExpr).Implicit() {
 344                         // Hack to keep reflect.flag.mustBe inlinable for TestIntendedInlining.
 345                         // Before CL 284412, these conversions were introduced later in the
 346                         // compiler, so they didn't count against inlining budget.
 347                         v.budget++
 348                 }
 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                 v.reason = "call to recover"
 355                 return true
 356
 357         case ir.OCLOSURE:
 358                 if base.Debug.InlFuncsWithClosures == 0 {
 359                         v.reason = "not inlining functions with closures"
 360                         return true
 361                 }
 362
 363                 // TODO(danscales): Maybe make budget proportional to number of closure
 364                 // variables, e.g.:
 365                 //v.budget -= int32(len(n.(*ir.ClosureExpr).Func.ClosureVars) * 3)
 366                 v.budget -= 15
 367                 // Scan body of closure (which DoChildren doesn't automatically
 368                 // do) to check for disallowed ops in the body and include the
 369                 // body in the budget.
 370                 if doList(n.(*ir.ClosureExpr).Func.Body, v.do) {
 371                         return true
 372                 }
 373
 374         case ir.OGO,
 375                 ir.ODEFER,
 376                 ir.ODCLTYPE, // can't print yet
 377                 ir.OTAILCALL:
 378                 v.reason = "unhandled op " + n.Op().String()
 379                 return true
 380
 381         case ir.OAPPEND:
 382                 v.budget -= inlineExtraAppendCost
 383
 384         case ir.OADDR:
 385                 n := n.(*ir.AddrExpr)
 386                 // Make "&s.f" cost 0 when f's offset is zero.
 387                 if dot, ok := n.X.(*ir.SelectorExpr); ok && (dot.Op() == ir.ODOT || dot.Op() == ir.ODOTPTR) {
 388                         if _, ok := dot.X.(*ir.Name); ok && dot.Selection.Offset == 0 {
 389                                 v.budget += 2 // undo ir.OADDR+ir.ODOT/ir.ODOTPTR
 390                         }
 391                 }
 392
 393         case ir.ODEREF:
 394                 // *(*X)(unsafe.Pointer(&x)) is low-cost
 395                 n := n.(*ir.StarExpr)
 396
 397                 ptr := n.X
 398                 for ptr.Op() == ir.OCONVNOP {
 399                         ptr = ptr.(*ir.ConvExpr).X
 400                 }
 401                 if ptr.Op() == ir.OADDR {
 402                         v.budget += 1 // undo half of default cost of ir.ODEREF+ir.OADDR
 403                 }
 404
 405         case ir.OCONVNOP:
 406                 // This doesn't produce code, but the children might.
 407                 v.budget++ // undo default cost
 408
 409         case ir.ODCLCONST, ir.OFALL:
 410                 // These nodes don't produce code; omit from inlining budget.
 411                 return false
 412
 413         case ir.OIF:
 414                 n := n.(*ir.IfStmt)
 415                 if ir.IsConst(n.Cond, constant.Bool) {
 416                         // This if and the condition cost nothing.
 417                         if doList(n.Init(), v.do) {
 418                                 return true
 419                         }
 420                         if ir.BoolVal(n.Cond) {
 421                                 return doList(n.Body, v.do)
 422                         } else {
 423                                 return doList(n.Else, v.do)
 424                         }
 425                 }
 426
 427         case ir.ONAME:
 428                 n := n.(*ir.Name)
 429                 if n.Class == ir.PAUTO {
 430                         v.usedLocals.Add(n)
 431                 }
 432
 433         case ir.OBLOCK:
 434                 // The only OBLOCK we should see at this point is an empty one.
 435                 // In any event, let the visitList(n.List()) below take care of the statements,
 436                 // and don't charge for the OBLOCK itself. The ++ undoes the -- below.
 437                 v.budget++
 438
 439         case ir.OMETHVALUE, ir.OSLICELIT:
 440                 v.budget-- // Hack for toolstash -cmp.
 441
 442         case ir.OMETHEXPR:
 443                 v.budget++ // Hack for toolstash -cmp.
 444
 445         case ir.OAS2:
 446                 n := n.(*ir.AssignListStmt)
 447
 448                 // Unified IR unconditionally rewrites:
 449                 //
 450                 //      a, b = f()
 451                 //
 452                 // into:
 453                 //
 454                 //      DCL tmp1
 455                 //      DCL tmp2
 456                 //      tmp1, tmp2 = f()
 457                 //      a, b = tmp1, tmp2
 458                 //
 459                 // so that it can insert implicit conversions as necessary. To
 460                 // minimize impact to the existing inlining heuristics (in
 461                 // particular, to avoid breaking the existing inlinability regress
 462                 // tests), we need to compensate for this here.
 463                 if base.Debug.Unified != 0 {
 464                         if init := n.Rhs[0].Init(); len(init) == 1 {
 465                                 if _, ok := init[0].(*ir.AssignListStmt); ok {
 466                                         // 4 for each value, because each temporary variable now
 467                                         // appears 3 times (DCL, LHS, RHS), plus an extra DCL node.
 468                                         //
 469                                         // 1 for the extra "tmp1, tmp2 = f()" assignment statement.
 470                                         v.budget += 4*int32(len(n.Lhs)) + 1
 471                                 }
 472                         }
 473                 }
 474         }
 475
 476         v.budget--
 477
 478         // When debugging, don't stop early, to get full cost of inlining this function
 479         if v.budget < 0 && base.Flag.LowerM < 2 && !logopt.Enabled() {
 480                 v.reason = "too expensive"
 481                 return true
 482         }
 483
 484         return ir.DoChildren(n, v.do)
 485 }
 486
 487 func isBigFunc(fn *ir.Func) bool {
 488         budget := inlineBigFunctionNodes
 489         return ir.Any(fn, func(n ir.Node) bool {
 490                 budget--
 491                 return budget <= 0
 492         })
 493 }
 494
 495 // inlcopylist (together with inlcopy) recursively copies a list of nodes, except
 496 // that it keeps the same ONAME, OTYPE, and OLITERAL nodes. It is used for copying
 497 // the body and dcls of an inlineable function.
 498 func inlcopylist(ll []ir.Node) []ir.Node {
 499         s := make([]ir.Node, len(ll))
 500         for i, n := range ll {
 501                 s[i] = inlcopy(n)
 502         }
 503         return s
 504 }
 505
 506 // inlcopy is like DeepCopy(), but does extra work to copy closures.
 507 func inlcopy(n ir.Node) ir.Node {
 508         var edit func(ir.Node) ir.Node
 509         edit = func(x ir.Node) ir.Node {
 510                 switch x.Op() {
 511                 case ir.ONAME, ir.OTYPE, ir.OLITERAL, ir.ONIL:
 512                         return x
 513                 }
 514                 m := ir.Copy(x)
 515                 ir.EditChildren(m, edit)
 516                 if x.Op() == ir.OCLOSURE {
 517                         x := x.(*ir.ClosureExpr)
 518                         // Need to save/duplicate x.Func.Nname,
 519                         // x.Func.Nname.Ntype, x.Func.Dcl, x.Func.ClosureVars, and
 520                         // x.Func.Body for iexport and local inlining.
 521                         oldfn := x.Func
 522                         newfn := ir.NewFunc(oldfn.Pos())
 523                         m.(*ir.ClosureExpr).Func = newfn
 524                         newfn.Nname = ir.NewNameAt(oldfn.Nname.Pos(), oldfn.Nname.Sym())
 525                         // XXX OK to share fn.Type() ??
 526                         newfn.Nname.SetType(oldfn.Nname.Type())
 527                         newfn.Body = inlcopylist(oldfn.Body)
 528                         // Make shallow copy of the Dcl and ClosureVar slices
 529                         newfn.Dcl = append([]*ir.Name(nil), oldfn.Dcl...)
 530                         newfn.ClosureVars = append([]*ir.Name(nil), oldfn.ClosureVars...)
 531                 }
 532                 return m
 533         }
 534         return edit(n)
 535 }
 536
 537 // InlineCalls/inlnode walks fn's statements and expressions and substitutes any
 538 // calls made to inlineable functions. This is the external entry point.
 539 func InlineCalls(fn *ir.Func) {
 540         savefn := ir.CurFunc
 541         ir.CurFunc = fn
 542         maxCost := int32(inlineMaxBudget)
 543         if isBigFunc(fn) {
 544                 maxCost = inlineBigFunctionMaxCost
 545         }
 546         var inlCalls []*ir.InlinedCallExpr
 547         var edit func(ir.Node) ir.Node
 548         edit = func(n ir.Node) ir.Node {
 549                 return inlnode(n, maxCost, &inlCalls, edit)
 550         }
 551         ir.EditChildren(fn, edit)
 552
 553         // If we inlined any calls, we want to recursively visit their
 554         // bodies for further inlining. However, we need to wait until
 555         // *after* the original function body has been expanded, or else
 556         // inlCallee can have false positives (e.g., #54632).
 557         for len(inlCalls) > 0 {
 558                 call := inlCalls[0]
 559                 inlCalls = inlCalls[1:]
 560                 ir.EditChildren(call, edit)
 561         }
 562
 563         ir.CurFunc = savefn
 564 }
 565
 566 // inlnode recurses over the tree to find inlineable calls, which will
 567 // be turned into OINLCALLs by mkinlcall. When the recursion comes
 568 // back up will examine left, right, list, rlist, ninit, ntest, nincr,
 569 // nbody and nelse and use one of the 4 inlconv/glue functions above
 570 // to turn the OINLCALL into an expression, a statement, or patch it
 571 // in to this nodes list or rlist as appropriate.
 572 // NOTE it makes no sense to pass the glue functions down the
 573 // recursion to the level where the OINLCALL gets created because they
 574 // have to edit /this/ n, so you'd have to push that one down as well,
 575 // but then you may as well do it here.  so this is cleaner and
 576 // shorter and less complicated.
 577 // The result of inlnode MUST be assigned back to n, e.g.
 578 //
 579 //      n.Left = inlnode(n.Left)
 580 func inlnode(n ir.Node, maxCost int32, inlCalls *[]*ir.InlinedCallExpr, edit func(ir.Node) ir.Node) ir.Node {
 581         if n == nil {
 582                 return n
 583         }
 584
 585         switch n.Op() {
 586         case ir.ODEFER, ir.OGO:
 587                 n := n.(*ir.GoDeferStmt)
 588                 switch call := n.Call; call.Op() {
 589                 case ir.OCALLMETH:
 590                         base.FatalfAt(call.Pos(), "OCALLMETH missed by typecheck")
 591                 case ir.OCALLFUNC:
 592                         call := call.(*ir.CallExpr)
 593                         call.NoInline = true
 594                 }
 595         case ir.OTAILCALL:
 596                 n := n.(*ir.TailCallStmt)
 597                 n.Call.NoInline = true // Not inline a tail call for now. Maybe we could inline it just like RETURN fn(arg)?
 598
 599         // TODO do them here (or earlier),
 600         // so escape analysis can avoid more heapmoves.
 601         case ir.OCLOSURE:
 602                 return n
 603         case ir.OCALLMETH:
 604                 base.FatalfAt(n.Pos(), "OCALLMETH missed by typecheck")
 605         case ir.OCALLFUNC:
 606                 n := n.(*ir.CallExpr)
 607                 if n.X.Op() == ir.OMETHEXPR {
 608                         // Prevent inlining some reflect.Value methods when using checkptr,
 609                         // even when package reflect was compiled without it (#35073).
 610                         if meth := ir.MethodExprName(n.X); meth != nil {
 611                                 s := meth.Sym()
 612                                 if base.Debug.Checkptr != 0 && types.IsReflectPkg(s.Pkg) && (s.Name == "Value.UnsafeAddr" || s.Name == "Value.Pointer") {
 613                                         return n
 614                                 }
 615                         }
 616                 }
 617         }
 618
 619         lno := ir.SetPos(n)
 620
 621         ir.EditChildren(n, edit)
 622
 623         // with all the branches out of the way, it is now time to
 624         // transmogrify this node itself unless inhibited by the
 625         // switch at the top of this function.
 626         switch n.Op() {
 627         case ir.OCALLMETH:
 628                 base.FatalfAt(n.Pos(), "OCALLMETH missed by typecheck")
 629
 630         case ir.OCALLFUNC:
 631                 call := n.(*ir.CallExpr)
 632                 if call.NoInline {
 633                         break
 634                 }
 635                 if base.Flag.LowerM > 3 {
 636                         fmt.Printf("%v:call to func %+v\n", ir.Line(n), call.X)
 637                 }
 638                 if ir.IsIntrinsicCall(call) {
 639                         break
 640                 }
 641                 if fn := inlCallee(call.X); fn != nil && typecheck.HaveInlineBody(fn) {
 642                         n = mkinlcall(call, fn, maxCost, inlCalls, edit)
 643                 }
 644         }
 645
 646         base.Pos = lno
 647
 648         return n
 649 }
 650
 651 // inlCallee takes a function-typed expression and returns the underlying function ONAME
 652 // that it refers to if statically known. Otherwise, it returns nil.
 653 func inlCallee(fn ir.Node) *ir.Func {
 654         fn = ir.StaticValue(fn)
 655         switch fn.Op() {
 656         case ir.OMETHEXPR:
 657                 fn := fn.(*ir.SelectorExpr)
 658                 n := ir.MethodExprName(fn)
 659                 // Check that receiver type matches fn.X.
 660                 // TODO(mdempsky): Handle implicit dereference
 661                 // of pointer receiver argument?
 662                 if n == nil || !types.Identical(n.Type().Recv().Type, fn.X.Type()) {
 663                         return nil
 664                 }
 665                 return n.Func
 666         case ir.ONAME:
 667                 fn := fn.(*ir.Name)
 668                 if fn.Class == ir.PFUNC {
 669                         return fn.Func
 670                 }
 671         case ir.OCLOSURE:
 672                 fn := fn.(*ir.ClosureExpr)
 673                 c := fn.Func
 674                 CanInline(c)
 675                 return c
 676         }
 677         return nil
 678 }
 679
 680 func inlParam(t *types.Field, as ir.InitNode, inlvars map[*ir.Name]*ir.Name) ir.Node {
 681         if t.Nname == nil {
 682                 return ir.BlankNode
 683         }
 684         n := t.Nname.(*ir.Name)
 685         if ir.IsBlank(n) {
 686                 return ir.BlankNode
 687         }
 688         inlvar := inlvars[n]
 689         if inlvar == nil {
 690                 base.Fatalf("missing inlvar for %v", n)
 691         }
 692         as.PtrInit().Append(ir.NewDecl(base.Pos, ir.ODCL, inlvar))
 693         inlvar.Name().Defn = as
 694         return inlvar
 695 }
 696
 697 var inlgen int
 698
 699 // SSADumpInline gives the SSA back end a chance to dump the function
 700 // when producing output for debugging the compiler itself.
 701 var SSADumpInline = func(*ir.Func) {}
 702
 703 // InlineCall allows the inliner implementation to be overridden.
 704 // If it returns nil, the function will not be inlined.
 705 var InlineCall = oldInlineCall
 706
 707 // If n is a OCALLFUNC node, and fn is an ONAME node for a
 708 // function with an inlinable body, return an OINLCALL node that can replace n.
 709 // The returned node's Ninit has the parameter assignments, the Nbody is the
 710 // inlined function body, and (List, Rlist) contain the (input, output)
 711 // parameters.
 712 // The result of mkinlcall MUST be assigned back to n, e.g.
 713 //
 714 //      n.Left = mkinlcall(n.Left, fn, isddd)
 715 func mkinlcall(n *ir.CallExpr, fn *ir.Func, maxCost int32, inlCalls *[]*ir.InlinedCallExpr, edit func(ir.Node) ir.Node) ir.Node {
 716         if fn.Inl == nil {
 717                 if logopt.Enabled() {
 718                         logopt.LogOpt(n.Pos(), "cannotInlineCall", "inline", ir.FuncName(ir.CurFunc),
 719                                 fmt.Sprintf("%s cannot be inlined", ir.PkgFuncName(fn)))
 720                 }
 721                 return n
 722         }
 723         if fn.Inl.Cost > maxCost {
 724                 // The inlined function body is too big. Typically we use this check to restrict
 725                 // inlining into very big functions.  See issue 26546 and 17566.
 726                 if logopt.Enabled() {
 727                         logopt.LogOpt(n.Pos(), "cannotInlineCall", "inline", ir.FuncName(ir.CurFunc),
 728                                 fmt.Sprintf("cost %d of %s exceeds max large caller cost %d", fn.Inl.Cost, ir.PkgFuncName(fn), maxCost))
 729                 }
 730                 return n
 731         }
 732
 733         if fn == ir.CurFunc {
 734                 // Can't recursively inline a function into itself.
 735                 if logopt.Enabled() {
 736                         logopt.LogOpt(n.Pos(), "cannotInlineCall", "inline", fmt.Sprintf("recursive call to %s", ir.FuncName(ir.CurFunc)))
 737                 }
 738                 return n
 739         }
 740
 741         // The non-unified frontend has issues with inlining and shape parameters.
 742         if base.Debug.Unified == 0 {
 743                 // Don't inline a function fn that has no shape parameters, but is passed at
 744                 // least one shape arg. This means we must be inlining a non-generic function
 745                 // fn that was passed into a generic function, and can be called with a shape
 746                 // arg because it matches an appropriate type parameters. But fn may include
 747                 // an interface conversion (that may be applied to a shape arg) that was not
 748                 // apparent when we first created the instantiation of the generic function.
 749                 // We can't handle this if we actually do the inlining, since we want to know
 750                 // all interface conversions immediately after stenciling. So, we avoid
 751                 // inlining in this case, see issue #49309. (1)
 752                 //
 753                 // See discussion on go.dev/cl/406475 for more background.
 754                 if !fn.Type().Params().HasShape() {
 755                         for _, arg := range n.Args {
 756                                 if arg.Type().HasShape() {
 757                                         if logopt.Enabled() {
 758                                                 logopt.LogOpt(n.Pos(), "cannotInlineCall", "inline", ir.FuncName(ir.CurFunc),
 759                                                         fmt.Sprintf("inlining function %v has no-shape params with shape args", ir.FuncName(fn)))
 760                                         }
 761                                         return n
 762                                 }
 763                         }
 764                 } else {
 765                         // Don't inline a function fn that has shape parameters, but is passed no shape arg.
 766                         // See comments (1) above, and issue #51909.
 767                         inlineable := len(n.Args) == 0 // Function has shape in type, with no arguments can always be inlined.
 768                         for _, arg := range n.Args {
 769                                 if arg.Type().HasShape() {
 770                                         inlineable = true
 771                                         break
 772                                 }
 773                         }
 774                         if !inlineable {
 775                                 if logopt.Enabled() {
 776                                         logopt.LogOpt(n.Pos(), "cannotInlineCall", "inline", ir.FuncName(ir.CurFunc),
 777                                                 fmt.Sprintf("inlining function %v has shape params with no-shape args", ir.FuncName(fn)))
 778                                 }
 779                                 return n
 780                         }
 781                 }
 782         }
 783
 784         if base.Flag.Cfg.Instrumenting && types.IsRuntimePkg(fn.Sym().Pkg) {
 785                 // Runtime package must not be instrumented.
 786                 // Instrument skips runtime package. However, some runtime code can be
 787                 // inlined into other packages and instrumented there. To avoid this,
 788                 // we disable inlining of runtime functions when instrumenting.
 789                 // The example that we observed is inlining of LockOSThread,
 790                 // which lead to false race reports on m contents.
 791                 return n
 792         }
 793
 794         parent := base.Ctxt.PosTable.Pos(n.Pos()).Base().InliningIndex()
 795         sym := fn.Linksym()
 796
 797         // Check if we've already inlined this function at this particular
 798         // call site, in order to stop inlining when we reach the beginning
 799         // of a recursion cycle again. We don't inline immediately recursive
 800         // functions, but allow inlining if there is a recursion cycle of
 801         // many functions. Most likely, the inlining will stop before we
 802         // even hit the beginning of the cycle again, but this catches the
 803         // unusual case.
 804         for inlIndex := parent; inlIndex >= 0; inlIndex = base.Ctxt.InlTree.Parent(inlIndex) {
 805                 if base.Ctxt.InlTree.InlinedFunction(inlIndex) == sym {
 806                         if base.Flag.LowerM > 1 {
 807                                 fmt.Printf("%v: cannot inline %v into %v: repeated recursive cycle\n", ir.Line(n), fn, ir.FuncName(ir.CurFunc))
 808                         }
 809                         return n
 810                 }
 811         }
 812
 813         typecheck.FixVariadicCall(n)
 814
 815         inlIndex := base.Ctxt.InlTree.Add(parent, n.Pos(), sym)
 816
 817         if base.Flag.GenDwarfInl > 0 {
 818                 if !sym.WasInlined() {
 819                         base.Ctxt.DwFixups.SetPrecursorFunc(sym, fn)
 820                         sym.Set(obj.AttrWasInlined, true)
 821                 }
 822         }
 823
 824         if base.Flag.LowerM != 0 {
 825                 fmt.Printf("%v: inlining call to %v\n", ir.Line(n), fn)
 826         }
 827         if base.Flag.LowerM > 2 {
 828                 fmt.Printf("%v: Before inlining: %+v\n", ir.Line(n), n)
 829         }
 830
 831         res := InlineCall(n, fn, inlIndex)
 832         if res == nil {
 833                 base.FatalfAt(n.Pos(), "inlining call to %v failed", fn)
 834         }
 835
 836         if base.Flag.LowerM > 2 {
 837                 fmt.Printf("%v: After inlining %+v\n\n", ir.Line(res), res)
 838         }
 839
 840         *inlCalls = append(*inlCalls, res)
 841
 842         return res
 843 }
 844
 845 // CalleeEffects appends any side effects from evaluating callee to init.
 846 func CalleeEffects(init *ir.Nodes, callee ir.Node) {
 847         for {
 848                 init.Append(ir.TakeInit(callee)...)
 849
 850                 switch callee.Op() {
 851                 case ir.ONAME, ir.OCLOSURE, ir.OMETHEXPR:
 852                         return // done
 853
 854                 case ir.OCONVNOP:
 855                         conv := callee.(*ir.ConvExpr)
 856                         callee = conv.X
 857
 858                 case ir.OINLCALL:
 859                         ic := callee.(*ir.InlinedCallExpr)
 860                         init.Append(ic.Body.Take()...)
 861                         callee = ic.SingleResult()
 862
 863                 default:
 864                         base.FatalfAt(callee.Pos(), "unexpected callee expression: %v", callee)
 865                 }
 866         }
 867 }
 868
 869 // oldInlineCall creates an InlinedCallExpr to replace the given call
 870 // expression. fn is the callee function to be inlined. inlIndex is
 871 // the inlining tree position index, for use with src.NewInliningBase
 872 // when rewriting positions.
 873 func oldInlineCall(call *ir.CallExpr, fn *ir.Func, inlIndex int) *ir.InlinedCallExpr {
 874         if base.Debug.TypecheckInl == 0 {
 875                 typecheck.ImportedBody(fn)
 876         }
 877
 878         SSADumpInline(fn)
 879
 880         ninit := call.Init()
 881
 882         // For normal function calls, the function callee expression
 883         // may contain side effects. Make sure to preserve these,
 884         // if necessary (#42703).
 885         if call.Op() == ir.OCALLFUNC {
 886                 CalleeEffects(&ninit, call.X)
 887         }
 888
 889         // Make temp names to use instead of the originals.
 890         inlvars := make(map[*ir.Name]*ir.Name)
 891
 892         // record formals/locals for later post-processing
 893         var inlfvars []*ir.Name
 894
 895         for _, ln := range fn.Inl.Dcl {
 896                 if ln.Op() != ir.ONAME {
 897                         continue
 898                 }
 899                 if ln.Class == ir.PPARAMOUT { // return values handled below.
 900                         continue
 901                 }
 902                 inlf := typecheck.Expr(inlvar(ln)).(*ir.Name)
 903                 inlvars[ln] = inlf
 904                 if base.Flag.GenDwarfInl > 0 {
 905                         if ln.Class == ir.PPARAM {
 906                                 inlf.Name().SetInlFormal(true)
 907                         } else {
 908                                 inlf.Name().SetInlLocal(true)
 909                         }
 910                         inlf.SetPos(ln.Pos())
 911                         inlfvars = append(inlfvars, inlf)
 912                 }
 913         }
 914
 915         // We can delay declaring+initializing result parameters if:
 916         // temporaries for return values.
 917         var retvars []ir.Node
 918         for i, t := range fn.Type().Results().Fields().Slice() {
 919                 var m *ir.Name
 920                 if nn := t.Nname; nn != nil && !ir.IsBlank(nn.(*ir.Name)) && !strings.HasPrefix(nn.Sym().Name, "~r") {
 921                         n := nn.(*ir.Name)
 922                         m = inlvar(n)
 923                         m = typecheck.Expr(m).(*ir.Name)
 924                         inlvars[n] = m
 925                 } else {
 926                         // anonymous return values, synthesize names for use in assignment that replaces return
 927                         m = retvar(t, i)
 928                 }
 929
 930                 if base.Flag.GenDwarfInl > 0 {
 931                         // Don't update the src.Pos on a return variable if it
 932                         // was manufactured by the inliner (e.g. "~R2"); such vars
 933                         // were not part of the original callee.
 934                         if !strings.HasPrefix(m.Sym().Name, "~R") {
 935                                 m.Name().SetInlFormal(true)
 936                                 m.SetPos(t.Pos)
 937                                 inlfvars = append(inlfvars, m)
 938                         }
 939                 }
 940
 941                 retvars = append(retvars, m)
 942         }
 943
 944         // Assign arguments to the parameters' temp names.
 945         as := ir.NewAssignListStmt(base.Pos, ir.OAS2, nil, nil)
 946         as.Def = true
 947         if call.Op() == ir.OCALLMETH {
 948                 base.FatalfAt(call.Pos(), "OCALLMETH missed by typecheck")
 949         }
 950         as.Rhs.Append(call.Args...)
 951
 952         if recv := fn.Type().Recv(); recv != nil {
 953                 as.Lhs.Append(inlParam(recv, as, inlvars))
 954         }
 955         for _, param := range fn.Type().Params().Fields().Slice() {
 956                 as.Lhs.Append(inlParam(param, as, inlvars))
 957         }
 958
 959         if len(as.Rhs) != 0 {
 960                 ninit.Append(typecheck.Stmt(as))
 961         }
 962
 963         if !fn.Inl.CanDelayResults {
 964                 // Zero the return parameters.
 965                 for _, n := range retvars {
 966                         ninit.Append(ir.NewDecl(base.Pos, ir.ODCL, n.(*ir.Name)))
 967                         ras := ir.NewAssignStmt(base.Pos, n, nil)
 968                         ninit.Append(typecheck.Stmt(ras))
 969                 }
 970         }
 971
 972         retlabel := typecheck.AutoLabel(".i")
 973
 974         inlgen++
 975
 976         // Add an inline mark just before the inlined body.
 977         // This mark is inline in the code so that it's a reasonable spot
 978         // to put a breakpoint. Not sure if that's really necessary or not
 979         // (in which case it could go at the end of the function instead).
 980         // Note issue 28603.
 981         ninit.Append(ir.NewInlineMarkStmt(call.Pos().WithIsStmt(), int64(inlIndex)))
 982
 983         subst := inlsubst{
 984                 retlabel:    retlabel,
 985                 retvars:     retvars,
 986                 inlvars:     inlvars,
 987                 defnMarker:  ir.NilExpr{},
 988                 bases:       make(map[*src.PosBase]*src.PosBase),
 989                 newInlIndex: inlIndex,
 990                 fn:          fn,
 991         }
 992         subst.edit = subst.node
 993
 994         body := subst.list(ir.Nodes(fn.Inl.Body))
 995
 996         lab := ir.NewLabelStmt(base.Pos, retlabel)
 997         body = append(body, lab)
 998
 999         if base.Flag.GenDwarfInl > 0 {
1000                 for _, v := range inlfvars {
1001                         v.SetPos(subst.updatedPos(v.Pos()))
1002                 }
1003         }
1004
1005         //dumplist("ninit post", ninit);
1006
1007         res := ir.NewInlinedCallExpr(base.Pos, body, retvars)
1008         res.SetInit(ninit)
1009         res.SetType(call.Type())
1010         res.SetTypecheck(1)
1011         return res
1012 }
1013
1014 // Every time we expand a function we generate a new set of tmpnames,
1015 // PAUTO's in the calling functions, and link them off of the
1016 // PPARAM's, PAUTOS and PPARAMOUTs of the called function.
1017 func inlvar(var_ *ir.Name) *ir.Name {
1018         if base.Flag.LowerM > 3 {
1019                 fmt.Printf("inlvar %+v\n", var_)
1020         }
1021
1022         n := typecheck.NewName(var_.Sym())
1023         n.SetType(var_.Type())
1024         n.SetTypecheck(1)
1025         n.Class = ir.PAUTO
1026         n.SetUsed(true)
1027         n.SetAutoTemp(var_.AutoTemp())
1028         n.Curfn = ir.CurFunc // the calling function, not the called one
1029         n.SetAddrtaken(var_.Addrtaken())
1030
1031         ir.CurFunc.Dcl = append(ir.CurFunc.Dcl, n)
1032         return n
1033 }
1034
1035 // Synthesize a variable to store the inlined function's results in.
1036 func retvar(t *types.Field, i int) *ir.Name {
1037         n := typecheck.NewName(typecheck.LookupNum("~R", i))
1038         n.SetType(t.Type)
1039         n.SetTypecheck(1)
1040         n.Class = ir.PAUTO
1041         n.SetUsed(true)
1042         n.Curfn = ir.CurFunc // the calling function, not the called one
1043         ir.CurFunc.Dcl = append(ir.CurFunc.Dcl, n)
1044         return n
1045 }
1046
1047 // The inlsubst type implements the actual inlining of a single
1048 // function call.
1049 type inlsubst struct {
1050         // Target of the goto substituted in place of a return.
1051         retlabel *types.Sym
1052
1053         // Temporary result variables.
1054         retvars []ir.Node
1055
1056         inlvars map[*ir.Name]*ir.Name
1057         // defnMarker is used to mark a Node for reassignment.
1058         // inlsubst.clovar set this during creating new ONAME.
1059         // inlsubst.node will set the correct Defn for inlvar.
1060         defnMarker ir.NilExpr
1061
1062         // bases maps from original PosBase to PosBase with an extra
1063         // inlined call frame.
1064         bases map[*src.PosBase]*src.PosBase
1065
1066         // newInlIndex is the index of the inlined call frame to
1067         // insert for inlined nodes.
1068         newInlIndex int
1069
1070         edit func(ir.Node) ir.Node // cached copy of subst.node method value closure
1071
1072         // If non-nil, we are inside a closure inside the inlined function, and
1073         // newclofn is the Func of the new inlined closure.
1074         newclofn *ir.Func
1075
1076         fn *ir.Func // For debug -- the func that is being inlined
1077
1078         // If true, then don't update source positions during substitution
1079         // (retain old source positions).
1080         noPosUpdate bool
1081 }
1082
1083 // list inlines a list of nodes.
1084 func (subst *inlsubst) list(ll ir.Nodes) []ir.Node {
1085         s := make([]ir.Node, 0, len(ll))
1086         for _, n := range ll {
1087                 s = append(s, subst.node(n))
1088         }
1089         return s
1090 }
1091
1092 // fields returns a list of the fields of a struct type representing receiver,
1093 // params, or results, after duplicating the field nodes and substituting the
1094 // Nname nodes inside the field nodes.
1095 func (subst *inlsubst) fields(oldt *types.Type) []*types.Field {
1096         oldfields := oldt.FieldSlice()
1097         newfields := make([]*types.Field, len(oldfields))
1098         for i := range oldfields {
1099                 newfields[i] = oldfields[i].Copy()
1100                 if oldfields[i].Nname != nil {
1101                         newfields[i].Nname = subst.node(oldfields[i].Nname.(*ir.Name))
1102                 }
1103         }
1104         return newfields
1105 }
1106
1107 // clovar creates a new ONAME node for a local variable or param of a closure
1108 // inside a function being inlined.
1109 func (subst *inlsubst) clovar(n *ir.Name) *ir.Name {
1110         m := ir.NewNameAt(n.Pos(), n.Sym())
1111         m.Class = n.Class
1112         m.SetType(n.Type())
1113         m.SetTypecheck(1)
1114         if n.IsClosureVar() {
1115                 m.SetIsClosureVar(true)
1116         }
1117         if n.Addrtaken() {
1118                 m.SetAddrtaken(true)
1119         }
1120         if n.Used() {
1121                 m.SetUsed(true)
1122         }
1123         m.Defn = n.Defn
1124
1125         m.Curfn = subst.newclofn
1126
1127         switch defn := n.Defn.(type) {
1128         case nil:
1129                 // ok
1130         case *ir.Name:
1131                 if !n.IsClosureVar() {
1132                         base.FatalfAt(n.Pos(), "want closure variable, got: %+v", n)
1133                 }
1134                 if n.Sym().Pkg != types.LocalPkg {
1135                         // If the closure came from inlining a function from
1136                         // another package, must change package of captured
1137                         // variable to localpkg, so that the fields of the closure
1138                         // struct are local package and can be accessed even if
1139                         // name is not exported. If you disable this code, you can
1140                         // reproduce the problem by running 'go test
1141                         // go/internal/srcimporter'. TODO(mdempsky) - maybe change
1142                         // how we create closure structs?
1143                         m.SetSym(types.LocalPkg.Lookup(n.Sym().Name))
1144                 }
1145                 // Make sure any inlvar which is the Defn
1146                 // of an ONAME closure var is rewritten
1147                 // during inlining. Don't substitute
1148                 // if Defn node is outside inlined function.
1149                 if subst.inlvars[n.Defn.(*ir.Name)] != nil {
1150                         m.Defn = subst.node(n.Defn)
1151                 }
1152         case *ir.AssignStmt, *ir.AssignListStmt:
1153                 // Mark node for reassignment at the end of inlsubst.node.
1154                 m.Defn = &subst.defnMarker
1155         case *ir.TypeSwitchGuard:
1156                 // TODO(mdempsky): Set m.Defn properly. See discussion on #45743.
1157         case *ir.RangeStmt:
1158                 // TODO: Set m.Defn properly if we support inlining range statement in the future.
1159         default:
1160                 base.FatalfAt(n.Pos(), "unexpected Defn: %+v", defn)
1161         }
1162
1163         if n.Outer != nil {
1164                 // Either the outer variable is defined in function being inlined,
1165                 // and we will replace it with the substituted variable, or it is
1166                 // defined outside the function being inlined, and we should just
1167                 // skip the outer variable (the closure variable of the function
1168                 // being inlined).
1169                 s := subst.node(n.Outer).(*ir.Name)
1170                 if s == n.Outer {
1171                         s = n.Outer.Outer
1172                 }
1173                 m.Outer = s
1174         }
1175         return m
1176 }
1177
1178 // closure does the necessary substitions for a ClosureExpr n and returns the new
1179 // closure node.
1180 func (subst *inlsubst) closure(n *ir.ClosureExpr) ir.Node {
1181         // Prior to the subst edit, set a flag in the inlsubst to indicate
1182         // that we don't want to update the source positions in the new
1183         // closure function. If we do this, it will appear that the
1184         // closure itself has things inlined into it, which is not the
1185         // case. See issue #46234 for more details. At the same time, we
1186         // do want to update the position in the new ClosureExpr (which is
1187         // part of the function we're working on). See #49171 for an
1188         // example of what happens if we miss that update.
1189         newClosurePos := subst.updatedPos(n.Pos())
1190         defer func(prev bool) { subst.noPosUpdate = prev }(subst.noPosUpdate)
1191         subst.noPosUpdate = true
1192
1193         //fmt.Printf("Inlining func %v with closure into %v\n", subst.fn, ir.FuncName(ir.CurFunc))
1194
1195         oldfn := n.Func
1196         newfn := ir.NewClosureFunc(oldfn.Pos(), true)
1197
1198         if subst.newclofn != nil {
1199                 //fmt.Printf("Inlining a closure with a nested closure\n")
1200         }
1201         prevxfunc := subst.newclofn
1202
1203         // Mark that we are now substituting within a closure (within the
1204         // inlined function), and create new nodes for all the local
1205         // vars/params inside this closure.
1206         subst.newclofn = newfn
1207         newfn.Dcl = nil
1208         newfn.ClosureVars = nil
1209         for _, oldv := range oldfn.Dcl {
1210                 newv := subst.clovar(oldv)
1211                 subst.inlvars[oldv] = newv
1212                 newfn.Dcl = append(newfn.Dcl, newv)
1213         }
1214         for _, oldv := range oldfn.ClosureVars {
1215                 newv := subst.clovar(oldv)
1216                 subst.inlvars[oldv] = newv
1217                 newfn.ClosureVars = append(newfn.ClosureVars, newv)
1218         }
1219
1220         // Need to replace ONAME nodes in
1221         // newfn.Type().FuncType().Receiver/Params/Results.FieldSlice().Nname
1222         oldt := oldfn.Type()
1223         newrecvs := subst.fields(oldt.Recvs())
1224         var newrecv *types.Field
1225         if len(newrecvs) > 0 {
1226                 newrecv = newrecvs[0]
1227         }
1228         newt := types.NewSignature(oldt.Pkg(), newrecv,
1229                 nil, subst.fields(oldt.Params()), subst.fields(oldt.Results()))
1230
1231         newfn.Nname.SetType(newt)
1232         newfn.Body = subst.list(oldfn.Body)
1233
1234         // Remove the nodes for the current closure from subst.inlvars
1235         for _, oldv := range oldfn.Dcl {
1236                 delete(subst.inlvars, oldv)
1237         }
1238         for _, oldv := range oldfn.ClosureVars {
1239                 delete(subst.inlvars, oldv)
1240         }
1241         // Go back to previous closure func
1242         subst.newclofn = prevxfunc
1243
1244         // Actually create the named function for the closure, now that
1245         // the closure is inlined in a specific function.
1246         newclo := newfn.OClosure
1247         newclo.SetPos(newClosurePos)
1248         newclo.SetInit(subst.list(n.Init()))
1249         return typecheck.Expr(newclo)
1250 }
1251
1252 // node recursively copies a node from the saved pristine body of the
1253 // inlined function, substituting references to input/output
1254 // parameters with ones to the tmpnames, and substituting returns with
1255 // assignments to the output.
1256 func (subst *inlsubst) node(n ir.Node) ir.Node {
1257         if n == nil {
1258                 return nil
1259         }
1260
1261         switch n.Op() {
1262         case ir.ONAME:
1263                 n := n.(*ir.Name)
1264
1265                 // Handle captured variables when inlining closures.
1266                 if n.IsClosureVar() && subst.newclofn == nil {
1267                         o := n.Outer
1268
1269                         // Deal with case where sequence of closures are inlined.
1270                         // TODO(danscales) - write test case to see if we need to
1271                         // go up multiple levels.
1272                         if o.Curfn != ir.CurFunc {
1273                                 o = o.Outer
1274                         }
1275
1276                         // make sure the outer param matches the inlining location
1277                         if o == nil || o.Curfn != ir.CurFunc {
1278                                 base.Fatalf("%v: unresolvable capture %v\n", ir.Line(n), n)
1279                         }
1280
1281                         if base.Flag.LowerM > 2 {
1282                                 fmt.Printf("substituting captured name %+v  ->  %+v\n", n, o)
1283                         }
1284                         return o
1285                 }
1286
1287                 if inlvar := subst.inlvars[n]; inlvar != nil { // These will be set during inlnode
1288                         if base.Flag.LowerM > 2 {
1289                                 fmt.Printf("substituting name %+v  ->  %+v\n", n, inlvar)
1290                         }
1291                         return inlvar
1292                 }
1293
1294                 if base.Flag.LowerM > 2 {
1295                         fmt.Printf("not substituting name %+v\n", n)
1296                 }
1297                 return n
1298
1299         case ir.OMETHEXPR:
1300                 n := n.(*ir.SelectorExpr)
1301                 return n
1302
1303         case ir.OLITERAL, ir.ONIL, ir.OTYPE:
1304                 // If n is a named constant or type, we can continue
1305                 // using it in the inline copy. Otherwise, make a copy
1306                 // so we can update the line number.
1307                 if n.Sym() != nil {
1308                         return n
1309                 }
1310
1311         case ir.ORETURN:
1312                 if subst.newclofn != nil {
1313                         // Don't do special substitutions if inside a closure
1314                         break
1315                 }
1316                 // Because of the above test for subst.newclofn,
1317                 // this return is guaranteed to belong to the current inlined function.
1318                 n := n.(*ir.ReturnStmt)
1319                 init := subst.list(n.Init())
1320                 if len(subst.retvars) != 0 && len(n.Results) != 0 {
1321                         as := ir.NewAssignListStmt(base.Pos, ir.OAS2, nil, nil)
1322
1323                         // Make a shallow copy of retvars.
1324                         // Otherwise OINLCALL.Rlist will be the same list,
1325                         // and later walk and typecheck may clobber it.
1326                         for _, n := range subst.retvars {
1327                                 as.Lhs.Append(n)
1328                         }
1329                         as.Rhs = subst.list(n.Results)
1330
1331                         if subst.fn.Inl.CanDelayResults {
1332                                 for _, n := range as.Lhs {
1333                                         as.PtrInit().Append(ir.NewDecl(base.Pos, ir.ODCL, n.(*ir.Name)))
1334                                         n.Name().Defn = as
1335                                 }
1336                         }
1337
1338                         init = append(init, typecheck.Stmt(as))
1339                 }
1340                 init = append(init, ir.NewBranchStmt(base.Pos, ir.OGOTO, subst.retlabel))
1341                 typecheck.Stmts(init)
1342                 return ir.NewBlockStmt(base.Pos, init)
1343
1344         case ir.OGOTO, ir.OBREAK, ir.OCONTINUE:
1345                 if subst.newclofn != nil {
1346                         // Don't do special substitutions if inside a closure
1347                         break
1348                 }
1349                 n := n.(*ir.BranchStmt)
1350                 m := ir.Copy(n).(*ir.BranchStmt)
1351                 m.SetPos(subst.updatedPos(m.Pos()))
1352                 m.SetInit(nil)
1353                 m.Label = translateLabel(n.Label)
1354                 return m
1355
1356         case ir.OLABEL:
1357                 if subst.newclofn != nil {
1358                         // Don't do special substitutions if inside a closure
1359                         break
1360                 }
1361                 n := n.(*ir.LabelStmt)
1362                 m := ir.Copy(n).(*ir.LabelStmt)
1363                 m.SetPos(subst.updatedPos(m.Pos()))
1364                 m.SetInit(nil)
1365                 m.Label = translateLabel(n.Label)
1366                 return m
1367
1368         case ir.OCLOSURE:
1369                 return subst.closure(n.(*ir.ClosureExpr))
1370
1371         }
1372
1373         m := ir.Copy(n)
1374         m.SetPos(subst.updatedPos(m.Pos()))
1375         ir.EditChildren(m, subst.edit)
1376
1377         if subst.newclofn == nil {
1378                 // Translate any label on FOR, RANGE loops, SWITCH or SELECT
1379                 switch m.Op() {
1380                 case ir.OFOR:
1381                         m := m.(*ir.ForStmt)
1382                         m.Label = translateLabel(m.Label)
1383                         return m
1384
1385                 case ir.ORANGE:
1386                         m := m.(*ir.RangeStmt)
1387                         m.Label = translateLabel(m.Label)
1388                         return m
1389
1390                 case ir.OSWITCH:
1391                         m := m.(*ir.SwitchStmt)
1392                         m.Label = translateLabel(m.Label)
1393                         return m
1394
1395                 case ir.OSELECT:
1396                         m := m.(*ir.SelectStmt)
1397                         m.Label = translateLabel(m.Label)
1398                         return m
1399                 }
1400         }
1401
1402         switch m := m.(type) {
1403         case *ir.AssignStmt:
1404                 if lhs, ok := m.X.(*ir.Name); ok && lhs.Defn == &subst.defnMarker {
1405                         lhs.Defn = m
1406                 }
1407         case *ir.AssignListStmt:
1408                 for _, lhs := range m.Lhs {
1409                         if lhs, ok := lhs.(*ir.Name); ok && lhs.Defn == &subst.defnMarker {
1410                                 lhs.Defn = m
1411                         }
1412                 }
1413         }
1414
1415         return m
1416 }
1417
1418 // translateLabel makes a label from an inlined function (if non-nil) be unique by
1419 // adding "·inlgen".
1420 func translateLabel(l *types.Sym) *types.Sym {
1421         if l == nil {
1422                 return nil
1423         }
1424         p := fmt.Sprintf("%s·%d", l.Name, inlgen)
1425         return typecheck.Lookup(p)
1426 }
1427
1428 func (subst *inlsubst) updatedPos(xpos src.XPos) src.XPos {
1429         if subst.noPosUpdate {
1430                 return xpos
1431         }
1432         pos := base.Ctxt.PosTable.Pos(xpos)
1433         oldbase := pos.Base() // can be nil
1434         newbase := subst.bases[oldbase]
1435         if newbase == nil {
1436                 newbase = src.NewInliningBase(oldbase, subst.newInlIndex)
1437                 subst.bases[oldbase] = newbase
1438         }
1439         pos.SetBase(newbase)
1440         return base.Ctxt.PosTable.XPos(pos)
1441 }
1442
1443 func pruneUnusedAutos(ll []*ir.Name, vis *hairyVisitor) []*ir.Name {
1444         s := make([]*ir.Name, 0, len(ll))
1445         for _, n := range ll {
1446                 if n.Class == ir.PAUTO {
1447                         if !vis.usedLocals.Has(n) {
1448                                 continue
1449                         }
1450                 }
1451                 s = append(s, n)
1452         }
1453         return s
1454 }
1455
1456 // numNonClosures returns the number of functions in list which are not closures.
1457 func numNonClosures(list []*ir.Func) int {
1458         count := 0
1459         for _, fn := range list {
1460                 if fn.OClosure == nil {
1461                         count++
1462                 }
1463         }
1464         return count
1465 }
1466
1467 func doList(list []ir.Node, do func(ir.Node) bool) bool {
1468         for _, x := range list {
1469                 if x != nil {
1470                         if do(x) {
1471                                 return true
1472                         }
1473                 }
1474         }
1475         return false
1476 }