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 var do func(ir.Node) bool 290 do = func(n ir.Node) bool { 291 if n == nil { 292 return false 293 } 294 switch n.Op() { 295 case ir.ONAME: 296 if i := tracking(n); i != nil { 297 // A use of a slice variable. Count it. 298 i.allUses++ 299 } 300 case ir.ODCL: 301 n := n.(*ir.Decl) 302 if i := tracking(n.X); i != nil { 303 i.okUses++ 304 i.declDepth = loopDepth 305 } 306 case ir.OINDEX: 307 n := n.(*ir.IndexExpr) 308 if i := tracking(n.X); i != nil { 309 // s[i] is ok. 310 i.okUses++ 311 } 312 case ir.OLEN: 313 n := n.(*ir.UnaryExpr) 314 if i := tracking(n.X); i != nil { 315 // len(s) is ok 316 i.okUses++ 317 } 318 case ir.OCAP: 319 n := n.(*ir.UnaryExpr) 320 if i := tracking(n.X); i != nil { 321 // cap(s) is ok 322 i.okUses++ 323 i.capUsed = true 324 } 325 case ir.OADDR: 326 n := n.(*ir.AddrExpr) 327 if n.X.Op() == ir.OINDEX { 328 n := n.X.(*ir.IndexExpr) 329 if i := tracking(n.X); i != nil { 330 // &s[i] is definitely a nonexclusive transition. 331 // (We need this case because s[i] is ok, but &s[i] is not.) 332 i.s.Opt = nil 333 } 334 } 335 case ir.ORETURN: 336 n := n.(*ir.ReturnStmt) 337 for _, x := range n.Results { 338 if i := tracking(x); i != nil { 339 i.okUses++ 340 // We go exclusive->nonexclusive here 341 addTransition(i, n) 342 } 343 } 344 if len(n.Results) == 0 { 345 // Uses of named result variables are implicit here. 346 for _, x := range namedRets { 347 if i := tracking(x); i != nil { 348 addTransition(i, n) 349 } 350 } 351 } 352 case ir.OCALLFUNC: 353 n := n.(*ir.CallExpr) 354 for idx, arg := range n.Args { 355 if i := tracking(arg); i != nil { 356 if !argLeak(n, idx) { 357 // Passing s to a nonescaping arg is ok. 358 i.okUses++ 359 i.capUsed = true 360 } 361 } 362 } 363 case ir.ORANGE: 364 // Range over slice is ok. 365 n := n.(*ir.RangeStmt) 366 if i := tracking(n.X); i != nil { 367 i.okUses++ 368 } 369 case ir.OAS: 370 n := n.(*ir.AssignStmt) 371 assign(n.X, n.Y, n) 372 case ir.OAS2: 373 n := n.(*ir.AssignListStmt) 374 for i := range len(n.Lhs) { 375 assign(n.Lhs[i], n.Rhs[i], n) 376 } 377 case ir.OCLOSURE: 378 n := n.(*ir.ClosureExpr) 379 for _, v := range n.Func.ClosureVars { 380 do(v.Outer) 381 } 382 } 383 if n.Op() == ir.OFOR || n.Op() == ir.ORANGE { 384 // Note: loopDepth isn't really right for init portion 385 // of the for statement, but that's ok. Correctness 386 // does not depend on depth info. 387 loopDepth++ 388 defer func() { loopDepth-- }() 389 } 390 // Check all the children. 391 ir.DoChildren(n, do) 392 return false 393 } 394 395 // Run the analysis over the whole body. 396 for _, stmt := range fn.Body { 397 do(stmt) 398 } 399 400 // Process accumulated info to find slice variables 401 // that we can allocate on the stack. 402 for _, s := range fn.Dcl { 403 if s.Opt == nil { 404 continue 405 } 406 i := s.Opt.(*sliceInfo) 407 s.Opt = nil 408 if i.okUses != i.allUses { 409 // Some use of i.s that don't understand lurks. Give up. 410 continue 411 } 412 413 // At this point, we've decided that we *can* do 414 // the optimization. 415 416 if i.transition == nil { 417 // Exclusive for its whole lifetime. That means it 418 // didn't escape. We can already handle nonescaping 419 // slices without this pass. 420 continue 421 } 422 if i.appendWeight < 2 { 423 // This optimization only really helps if there is 424 // (dynamically) more than one append. 425 continue 426 } 427 428 // Commit point - at this point we've decided we *should* 429 // do the optimization. 430 431 // Insert a move2heap operation before the exclusive->nonexclusive 432 // transition. 433 move := ir.NewMoveToHeapExpr(i.transition.Pos(), i.s) 434 if i.capUsed { 435 move.PreserveCapacity = true 436 } 437 move.RType = reflectdata.AppendElemRType(i.transition.Pos(), i.appends[0]) 438 move.SetType(i.s.Type()) 439 move.SetTypecheck(1) 440 as := ir.NewAssignStmt(i.transition.Pos(), i.s, move) 441 as.SetTypecheck(1) 442 i.transition.PtrInit().Prepend(as) 443 // Note: we prepend because we need to put the move2heap 444 // operation first, before any other init work, as the transition 445 // might occur in the init work. 446 447 // Now that we've inserted a move2heap operation before every 448 // exclusive -> nonexclusive transition, appends can now use 449 // stack backing stores. 450 // (This is the whole point of this pass, to enable stack 451 // allocation of append backing stores.) 452 for _, a := range i.appends { 453 a.SetEsc(ir.EscNone) 454 if i.capUsed { 455 a.UseBuf = true 456 } 457 } 458 } 459 } 460 461 // argLeak reports if the idx'th argument to the call n escapes anywhere 462 // (to the heap, another argument, return value, etc.) 463 // If unknown returns true. 464 func argLeak(n *ir.CallExpr, idx int) bool { 465 if n.Op() != ir.OCALLFUNC { 466 return true 467 } 468 fn := ir.StaticCalleeName(ir.StaticValue(n.Fun)) 469 if fn == nil { 470 return true 471 } 472 fntype := fn.Type() 473 if recv := fntype.Recv(); recv != nil { 474 if idx == 0 { 475 return escape.ParseLeaks(recv.Note).Any() 476 } 477 idx-- 478 } 479 return escape.ParseLeaks(fntype.Params()[idx].Note).Any() 480 } 481