Source file src/cmd/compile/internal/slice/slice.go
1 // Copyright 2025 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package slice 6 7 // This file implements a stack-allocation optimization 8 // for the backing store of slices. 9 // 10 // Consider the code: 11 // 12 // var s []int 13 // for i := range ... { 14 // s = append(s, i) 15 // } 16 // return s 17 // 18 // Some of the append operations will need to do an allocation 19 // by calling growslice. This will happen on the 1st, 2nd, 4th, 20 // 8th, etc. append calls. The allocations done by all but the 21 // last growslice call will then immediately be garbage. 22 // 23 // We'd like to avoid doing some of those intermediate 24 // allocations if possible. 25 // 26 // If we can determine that the "return s" statement is the 27 // *only* way that the backing store for s escapes, then we 28 // can rewrite the code to something like: 29 // 30 // var s []int 31 // for i := range N { 32 // s = append(s, i) 33 // } 34 // s = move2heap(s) 35 // return s 36 // 37 // Using the move2heap runtime function, which does: 38 // 39 // move2heap(s): 40 // If s is not backed by a stackframe-allocated 41 // backing store, return s. Otherwise, copy s 42 // to the heap and return the copy. 43 // 44 // Now we can treat the backing store of s allocated at the 45 // append site as not escaping. Previous stack allocation 46 // optimizations now apply, which can use a fixed-size 47 // stack-allocated backing store for s when appending. 48 // (See ../ssagen/ssa.go:(*state).append) 49 // 50 // It is tricky to do this optimization safely. To describe 51 // our analysis, we first define what an "exclusive" slice 52 // variable is. 53 // 54 // A slice variable (a variable of slice type) is called 55 // "exclusive" if, when it has a reference to a 56 // stackframe-allocated backing store, it is the only 57 // variable with such a reference. 58 // 59 // In other words, a slice variable is exclusive if 60 // any of the following holds: 61 // 1) It points to a heap-allocated backing store 62 // 2) It points to a stack-allocated backing store 63 // for any parent frame. 64 // 3) It is the only variable that references its 65 // backing store. 66 // 4) It is nil. 67 // 68 // The nice thing about exclusive slice variables is that 69 // it is always safe to do 70 // s = move2heap(s) 71 // whenever s is an exclusive slice variable. Because no 72 // one else has a reference to the backing store, no one 73 // else can tell that we moved the backing store from one 74 // location to another. 75 // 76 // Note that exclusiveness is a dynamic property. A slice 77 // variable may be exclusive during some parts of execution 78 // and not exclusive during others. 79 // 80 // The following operations set or preserve the exclusivity 81 // of a slice variable s: 82 // s = nil 83 // s = append(s, ...) 84 // s = s[i:j] 85 // ... = s[i] 86 // s[i] = ... 87 // f(s) where f does not escape its argument 88 // Other operations destroy exclusivity. A non-exhaustive list includes: 89 // x = s 90 // *p = s 91 // f(s) where f escapes its argument 92 // return s 93 // To err on the safe side, we white list exclusivity-preserving 94 // operations and we asssume that any other operations that mention s 95 // destroy its exclusivity. 96 // 97 // Our strategy is to move the backing store of s to the heap before 98 // any exclusive->nonexclusive transition. That way, s will only ever 99 // have a reference to a stack backing store while it is exclusive. 100 // 101 // move2heap for a variable s is implemented with: 102 // if s points to within the stack frame { 103 // s2 := make([]T, s.len, s.cap) 104 // copy(s2[:s.cap], s[:s.cap]) 105 // s = s2 106 // } 107 // Note that in general we need to copy all of s[:cap(s)] elements when 108 // moving to the heap. As an optimization, we keep track of slice variables 109 // whose capacity, and the elements in s[len(s):cap(s)], are never accessed. 110 // For those slice variables, we can allocate to the next size class above 111 // the length, which saves memory and copying cost. 112 113 import ( 114 "cmd/compile/internal/base" 115 "cmd/compile/internal/escape" 116 "cmd/compile/internal/ir" 117 "cmd/compile/internal/reflectdata" 118 ) 119 120 func Funcs(all []*ir.Func) { 121 if base.Flag.N != 0 { 122 return 123 } 124 for _, fn := range all { 125 analyze(fn) 126 } 127 for _, fn := range all { 128 if ir.MatchAstDump(fn, "slice") { 129 ir.AstDump(fn, "slice, "+ir.FuncName(fn)) 130 } 131 } 132 } 133 134 func analyze(fn *ir.Func) { 135 type sliceInfo struct { 136 // Slice variable. 137 s *ir.Name 138 139 // Count of uses that this pass understands. 140 okUses int32 141 // Count of all uses found. 142 allUses int32 143 144 // A place where the slice variable transitions from 145 // exclusive to nonexclusive. 146 // We could keep track of more than one, but one is enough for now. 147 // Currently, this can be either a return statement or 148 // an assignment. 149 // TODO: other possible transitions? 150 transition ir.Stmt 151 152 // Each s = append(s, ...) instance we found. 153 appends []*ir.CallExpr 154 155 // Weight of the number of s = append(s, ...) instances we found. 156 // The optimizations we do are only really useful if there are at 157 // least weight 2. (Note: appends in loops have weight >= 2.) 158 appendWeight int 159 160 // Loop depth at declaration point. 161 // Use for heuristics only, it is not guaranteed to be correct 162 // in the presence of gotos. 163 declDepth int 164 165 // Whether we ever do cap(s), or other operations that use cap(s) 166 // (possibly implicitly), like s[i:j]. 167 capUsed bool 168 } 169 170 // Every variable (*ir.Name) that we are tracking will have 171 // a non-nil *sliceInfo in its Opt field. 172 haveLocalSlice := false 173 maxStackSize := int64(base.Debug.VariableMakeThreshold) 174 var namedRets []*ir.Name 175 for _, s := range fn.Dcl { 176 if !s.Type().IsSlice() { 177 continue 178 } 179 if s.Type().Elem().Size() > maxStackSize { 180 continue 181 } 182 if !base.VariableMakeHash.MatchPos(s.Pos(), nil) { 183 continue 184 } 185 s.Opt = &sliceInfo{s: s} // start tracking s 186 haveLocalSlice = true 187 if s.Class == ir.PPARAMOUT { 188 namedRets = append(namedRets, s) 189 } 190 } 191 if !haveLocalSlice { 192 return 193 } 194 195 // Keep track of loop depth while walking. 196 loopDepth := 0 197 198 // tracking returns the info for the slice variable if n is a slice 199 // variable that we're still considering, or nil otherwise. 200 tracking := func(n ir.Node) *sliceInfo { 201 if n == nil || n.Op() != ir.ONAME { 202 return nil 203 } 204 s := n.(*ir.Name) 205 if s.Opt == nil { 206 return nil 207 } 208 return s.Opt.(*sliceInfo) 209 } 210 211 // addTransition(n, loc) records that s experiences an exclusive->nonexclusive 212 // transition somewhere within loc. 213 addTransition := func(i *sliceInfo, loc ir.Stmt) { 214 if i.transition != nil { 215 // We only keep track of a single exclusive->nonexclusive transition 216 // for a slice variable. If we find more than one, give up. 217 // (More than one transition location would be fine, but we would 218 // start to get worried about introducing too much additional code.) 219 i.s.Opt = nil 220 return 221 } 222 if loopDepth > i.declDepth { 223 // Conservatively, we disable this optimization when the 224 // transition is inside a loop. This can result in adding 225 // overhead unnecessarily in cases like: 226 // func f(n int, p *[]byte) { 227 // var s []byte 228 // for i := range n { 229 // *p = s 230 // s = append(s, 0) 231 // } 232 // } 233 i.s.Opt = nil 234 return 235 } 236 i.transition = loc 237 } 238 239 // Examine an x = y assignment that occurs somewhere within statement stmt. 240 assign := func(x, y ir.Node, stmt ir.Stmt) { 241 if i := tracking(x); i != nil { 242 // s = y. Check for understood patterns for y. 243 if y == nil || y.Op() == ir.ONIL { 244 // s = nil is ok. 245 i.okUses++ 246 } else if y.Op() == ir.OSLICELIT { 247 // s = []{...} is ok. 248 // Note: this reveals capacity. Should it? 249 i.okUses++ 250 i.capUsed = true 251 } else if y.Op() == ir.OSLICE { 252 y := y.(*ir.SliceExpr) 253 if y.X == i.s { 254 // s = s[...:...] is ok 255 i.okUses += 2 256 i.capUsed = true 257 } 258 } else if y.Op() == ir.OAPPEND { 259 y := y.(*ir.CallExpr) 260 if y.Args[0] == i.s { 261 // s = append(s, ...) is ok 262 i.okUses += 2 263 i.appends = append(i.appends, y) 264 i.appendWeight += 1 + (loopDepth - i.declDepth) 265 } 266 // TODO: s = append(nil, ...)? 267 } 268 // Note that technically s = make([]T, ...) preserves exclusivity, but 269 // we don't track that because we assume users who wrote that know 270 // better than the compiler does. 271 272 // TODO: figure out how to handle s = fn(..., s, ...) 273 // It would be nice to maintain exclusivity of s in this situation. 274 // But unfortunately, fn can return one of its other arguments, which 275 // may be a slice with a stack-allocated backing store other than s. 276 // (which may have preexisting references to its backing store). 277 // 278 // Maybe we could do it if s is the only argument? 279 } 280 281 if i := tracking(y); i != nil { 282 // ... = s 283 // Treat this as an exclusive->nonexclusive transition. 284 i.okUses++ 285 addTransition(i, stmt) 286 } 287 } 288 289 // do walks n and everything below it, recording what happens to the 290 // slice variables we are tracking. It counts every mention of such a 291 // variable in allUses, and the subset of those mentions that this pass 292 // understands to preserve exclusivity in okUses. A variable whose two 293 // counts end up equal is only ever used in ways we understand; any 294 // other variable is dropped at the end of the analysis. Uses that 295 // definitely destroy exclusivity, like &s[i], stop the tracking right 296 // away by clearing s.Opt, which makes tracking report the variable as 297 // no longer being considered. 298 // 299 // It is always used as an ir.DoChildren visitor and always returns 300 // false, so that the whole function body is walked. 301 var do func(ir.Node) bool 302 do = func(n ir.Node) bool { 303 if n == nil { 304 return false 305 } 306 switch n.Op() { 307 case ir.ONAME: 308 if i := tracking(n); i != nil { 309 // A use of a slice variable. Count it. 310 i.allUses++ 311 } 312 case ir.ODCL: 313 n := n.(*ir.Decl) 314 if i := tracking(n.X); i != nil { 315 i.okUses++ 316 i.declDepth = loopDepth 317 } 318 case ir.OINDEX: 319 n := n.(*ir.IndexExpr) 320 if i := tracking(n.X); i != nil { 321 // s[i] is ok. 322 i.okUses++ 323 } 324 case ir.OLEN: 325 n := n.(*ir.UnaryExpr) 326 if i := tracking(n.X); i != nil { 327 // len(s) is ok 328 i.okUses++ 329 } 330 case ir.OCAP: 331 n := n.(*ir.UnaryExpr) 332 if i := tracking(n.X); i != nil { 333 // cap(s) is ok 334 i.okUses++ 335 i.capUsed = true 336 } 337 case ir.OADDR: 338 n := n.(*ir.AddrExpr) 339 // Walk down to the object whose interior we're taking the 340 // address of. Field selectors and array indexes don't leave 341 // that object, so &s[i], &s[i].f, and &s[i].f[j] all end up 342 // pointing into s's backing store. 343 // (We need this because s[i] is ok, but &s[i] is not.) 344 x := n.X 345 for x != nil { 346 switch x.Op() { 347 case ir.ODOT: 348 // &x.f points into x. 349 x = x.(*ir.SelectorExpr).X 350 continue 351 case ir.OINDEX: 352 idx := x.(*ir.IndexExpr) 353 if idx.X.Type().IsArray() { 354 // &a[i] points into a. 355 // Note: for a pointer to an array, or for a 356 // slice, the address points into a different 357 // object instead, so we stop here. 358 x = idx.X 359 continue 360 } 361 if i := tracking(idx.X); i != nil { 362 // &s[i] is definitely a nonexclusive transition. 363 i.s.Opt = nil 364 } 365 } 366 break 367 } 368 case ir.ORETURN: 369 n := n.(*ir.ReturnStmt) 370 for _, x := range n.Results { 371 if i := tracking(x); i != nil { 372 i.okUses++ 373 // We go exclusive->nonexclusive here 374 addTransition(i, n) 375 } 376 } 377 if len(n.Results) == 0 { 378 // Uses of named result variables are implicit here. 379 for _, x := range namedRets { 380 if i := tracking(x); i != nil { 381 addTransition(i, n) 382 } 383 } 384 } 385 case ir.OCALLFUNC: 386 n := n.(*ir.CallExpr) 387 for idx, arg := range n.Args { 388 if i := tracking(arg); i != nil { 389 if !argLeak(n, idx) { 390 // Passing s to a nonescaping arg is ok. 391 i.okUses++ 392 i.capUsed = true 393 } 394 } 395 } 396 case ir.ORANGE: 397 n := n.(*ir.RangeStmt) 398 if i := tracking(n.X); i != nil { 399 i.okUses++ 400 // Range over slice keeps a pointer to the backing store, see #79909. 401 addTransition(i, n) 402 } 403 case ir.OAS: 404 n := n.(*ir.AssignStmt) 405 assign(n.X, n.Y, n) 406 case ir.OAS2: 407 n := n.(*ir.AssignListStmt) 408 for i := range len(n.Lhs) { 409 assign(n.Lhs[i], n.Rhs[i], n) 410 } 411 case ir.OCLOSURE: 412 n := n.(*ir.ClosureExpr) 413 for _, v := range n.Func.ClosureVars { 414 do(v.Outer) 415 } 416 } 417 if n.Op() == ir.OFOR || n.Op() == ir.ORANGE { 418 // Note: loopDepth isn't really right for init portion 419 // of the for statement, but that's ok. Correctness 420 // does not depend on depth info. 421 loopDepth++ 422 defer func() { loopDepth-- }() 423 } 424 // Check all the children. 425 ir.DoChildren(n, do) 426 return false 427 } 428 429 // Run the analysis over the whole body. 430 for _, stmt := range fn.Body { 431 do(stmt) 432 } 433 434 // Process accumulated info to find slice variables 435 // that we can allocate on the stack. 436 for _, s := range fn.Dcl { 437 if s.Opt == nil { 438 continue 439 } 440 i := s.Opt.(*sliceInfo) 441 s.Opt = nil 442 if i.okUses != i.allUses { 443 // Some use of i.s that don't understand lurks. Give up. 444 continue 445 } 446 447 // At this point, we've decided that we *can* do 448 // the optimization. 449 450 if i.transition == nil { 451 // Exclusive for its whole lifetime. That means it 452 // didn't escape. We can already handle nonescaping 453 // slices without this pass. 454 continue 455 } 456 if i.appendWeight < 2 { 457 // This optimization only really helps if there is 458 // (dynamically) more than one append. 459 continue 460 } 461 462 // Commit point - at this point we've decided we *should* 463 // do the optimization. 464 465 // Insert a move2heap operation before the exclusive->nonexclusive 466 // transition. 467 move := ir.NewMoveToHeapExpr(i.transition.Pos(), i.s) 468 if i.capUsed { 469 move.PreserveCapacity = true 470 } 471 move.RType = reflectdata.AppendElemRType(i.transition.Pos(), i.appends[0]) 472 move.SetType(i.s.Type()) 473 move.SetTypecheck(1) 474 as := ir.NewAssignStmt(i.transition.Pos(), i.s, move) 475 as.SetTypecheck(1) 476 i.transition.PtrInit().Prepend(as) 477 // Note: we prepend because we need to put the move2heap 478 // operation first, before any other init work, as the transition 479 // might occur in the init work. 480 481 // Now that we've inserted a move2heap operation before every 482 // exclusive -> nonexclusive transition, appends can now use 483 // stack backing stores. 484 // (This is the whole point of this pass, to enable stack 485 // allocation of append backing stores.) 486 for _, a := range i.appends { 487 a.SetEsc(ir.EscNone) 488 if i.capUsed { 489 a.UseBuf = true 490 } 491 } 492 } 493 } 494 495 // argLeak reports if the idx'th argument to the call n escapes anywhere 496 // (to the heap, another argument, return value, etc.) 497 // If unknown returns true. 498 func argLeak(n *ir.CallExpr, idx int) bool { 499 if n.Op() != ir.OCALLFUNC { 500 return true 501 } 502 fn := ir.StaticCalleeName(ir.StaticValue(n.Fun)) 503 if fn == nil { 504 return true 505 } 506 fntype := fn.Type() 507 if recv := fntype.Recv(); recv != nil { 508 if idx == 0 { 509 return escape.ParseLeaks(recv.Note).Any() 510 } 511 idx-- 512 } 513 return escape.ParseLeaks(fntype.Params()[idx].Note).Any() 514 } 515