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 } 128 129 func analyze(fn *ir.Func) { 130 type sliceInfo struct { 131 // Slice variable. 132 s *ir.Name 133 134 // Count of uses that this pass understands. 135 okUses int32 136 // Count of all uses found. 137 allUses int32 138 139 // A place where the slice variable transitions from 140 // exclusive to nonexclusive. 141 // We could keep track of more than one, but one is enough for now. 142 // Currently, this can be either a return statement or 143 // an assignment. 144 // TODO: other possible transitions? 145 transition ir.Stmt 146 147 // Each s = append(s, ...) instance we found. 148 appends []*ir.CallExpr 149 150 // Weight of the number of s = append(s, ...) instances we found. 151 // The optimizations we do are only really useful if there are at 152 // least weight 2. (Note: appends in loops have weight >= 2.) 153 appendWeight int 154 155 // Whether we ever do cap(s), or other operations that use cap(s) 156 // (possibly implicitly), like s[i:j]. 157 capUsed bool 158 } 159 160 // Every variable (*ir.Name) that we are tracking will have 161 // a non-nil *sliceInfo in its Opt field. 162 haveLocalSlice := false 163 maxStackSize := int64(base.Debug.VariableMakeThreshold) 164 var namedRets []*ir.Name 165 for _, s := range fn.Dcl { 166 if !s.Type().IsSlice() { 167 continue 168 } 169 if s.Type().Elem().Size() > maxStackSize { 170 continue 171 } 172 if !base.VariableMakeHash.MatchPos(s.Pos(), nil) { 173 continue 174 } 175 s.Opt = &sliceInfo{s: s} // start tracking s 176 haveLocalSlice = true 177 if s.Class == ir.PPARAMOUT { 178 namedRets = append(namedRets, s) 179 } 180 } 181 if !haveLocalSlice { 182 return 183 } 184 185 // Keep track of loop depth while walking. 186 loopDepth := 0 187 188 // tracking returns the info for the slice variable if n is a slice 189 // variable that we're still considering, or nil otherwise. 190 tracking := func(n ir.Node) *sliceInfo { 191 if n == nil || n.Op() != ir.ONAME { 192 return nil 193 } 194 s := n.(*ir.Name) 195 if s.Opt == nil { 196 return nil 197 } 198 return s.Opt.(*sliceInfo) 199 } 200 201 // addTransition(n, loc) records that s experiences an exclusive->nonexclusive 202 // transition somewhere within loc. 203 addTransition := func(i *sliceInfo, loc ir.Stmt) { 204 if i.transition != nil { 205 // We only keep track of a single exclusive->nonexclusive transition 206 // for a slice variable. If we find more than one, give up. 207 // (More than one transition location would be fine, but we would 208 // start to get worried about introducing too much additional code.) 209 i.s.Opt = nil 210 return 211 } 212 i.transition = loc 213 } 214 215 // Examine an x = y assignment that occurs somewhere within statement stmt. 216 assign := func(x, y ir.Node, stmt ir.Stmt) { 217 if i := tracking(x); i != nil { 218 // s = y. Check for understood patterns for y. 219 if y == nil || y.Op() == ir.ONIL { 220 // s = nil is ok. 221 i.okUses++ 222 } else if y.Op() == ir.OSLICELIT { 223 // s = []{...} is ok. 224 // Note: this reveals capacity. Should it? 225 i.okUses++ 226 i.capUsed = true 227 } else if y.Op() == ir.OSLICE { 228 y := y.(*ir.SliceExpr) 229 if y.X == i.s { 230 // s = s[...:...] is ok 231 i.okUses += 2 232 i.capUsed = true 233 } 234 } else if y.Op() == ir.OAPPEND { 235 y := y.(*ir.CallExpr) 236 if y.Args[0] == i.s { 237 // s = append(s, ...) is ok 238 i.okUses += 2 239 i.appends = append(i.appends, y) 240 i.appendWeight += 1 + loopDepth 241 } 242 // TODO: s = append(nil, ...)? 243 } 244 // Note that technically s = make([]T, ...) preserves exclusivity, but 245 // we don't track that because we assume users who wrote that know 246 // better than the compiler does. 247 248 // TODO: figure out how to handle s = fn(..., s, ...) 249 // It would be nice to maintain exclusivity of s in this situation. 250 // But unfortunately, fn can return one of its other arguments, which 251 // may be a slice with a stack-allocated backing store other than s. 252 // (which may have preexisting references to its backing store). 253 // 254 // Maybe we could do it if s is the only argument? 255 } 256 257 if i := tracking(y); i != nil { 258 // ... = s 259 // Treat this as an exclusive->nonexclusive transition. 260 i.okUses++ 261 addTransition(i, stmt) 262 } 263 } 264 265 var do func(ir.Node) bool 266 do = func(n ir.Node) bool { 267 if n == nil { 268 return false 269 } 270 switch n.Op() { 271 case ir.ONAME: 272 if i := tracking(n); i != nil { 273 // A use of a slice variable. Count it. 274 i.allUses++ 275 } 276 case ir.ODCL: 277 n := n.(*ir.Decl) 278 if i := tracking(n.X); i != nil { 279 i.okUses++ 280 } 281 case ir.OINDEX: 282 n := n.(*ir.IndexExpr) 283 if i := tracking(n.X); i != nil { 284 // s[i] is ok. 285 i.okUses++ 286 } 287 case ir.OLEN: 288 n := n.(*ir.UnaryExpr) 289 if i := tracking(n.X); i != nil { 290 // len(s) is ok 291 i.okUses++ 292 } 293 case ir.OCAP: 294 n := n.(*ir.UnaryExpr) 295 if i := tracking(n.X); i != nil { 296 // cap(s) is ok 297 i.okUses++ 298 i.capUsed = true 299 } 300 case ir.OADDR: 301 n := n.(*ir.AddrExpr) 302 if n.X.Op() == ir.OINDEX { 303 n := n.X.(*ir.IndexExpr) 304 if i := tracking(n.X); i != nil { 305 // &s[i] is definitely a nonexclusive transition. 306 // (We need this case because s[i] is ok, but &s[i] is not.) 307 i.s.Opt = nil 308 } 309 } 310 case ir.ORETURN: 311 n := n.(*ir.ReturnStmt) 312 for _, x := range n.Results { 313 if i := tracking(x); i != nil { 314 i.okUses++ 315 // We go exclusive->nonexclusive here 316 addTransition(i, n) 317 } 318 } 319 if len(n.Results) == 0 { 320 // Uses of named result variables are implicit here. 321 for _, x := range namedRets { 322 if i := tracking(x); i != nil { 323 addTransition(i, n) 324 } 325 } 326 } 327 case ir.OCALLFUNC: 328 n := n.(*ir.CallExpr) 329 for idx, arg := range n.Args { 330 if i := tracking(arg); i != nil { 331 if !argLeak(n, idx) { 332 // Passing s to a nonescaping arg is ok. 333 i.okUses++ 334 i.capUsed = true 335 } 336 } 337 } 338 case ir.ORANGE: 339 // Range over slice is ok. 340 n := n.(*ir.RangeStmt) 341 if i := tracking(n.X); i != nil { 342 i.okUses++ 343 } 344 case ir.OAS: 345 n := n.(*ir.AssignStmt) 346 assign(n.X, n.Y, n) 347 case ir.OAS2: 348 n := n.(*ir.AssignListStmt) 349 for i := range len(n.Lhs) { 350 assign(n.Lhs[i], n.Rhs[i], n) 351 } 352 case ir.OCLOSURE: 353 n := n.(*ir.ClosureExpr) 354 for _, v := range n.Func.ClosureVars { 355 do(v.Outer) 356 } 357 } 358 if n.Op() == ir.OFOR || n.Op() == ir.ORANGE { 359 // Note: loopDepth isn't really right for init portion 360 // of the for statement, but that's ok. Correctness 361 // does not depend on depth info. 362 loopDepth++ 363 defer func() { loopDepth-- }() 364 } 365 // Check all the children. 366 ir.DoChildren(n, do) 367 return false 368 } 369 370 // Run the analysis over the whole body. 371 for _, stmt := range fn.Body { 372 do(stmt) 373 } 374 375 // Process accumulated info to find slice variables 376 // that we can allocate on the stack. 377 for _, s := range fn.Dcl { 378 if s.Opt == nil { 379 continue 380 } 381 i := s.Opt.(*sliceInfo) 382 s.Opt = nil 383 if i.okUses != i.allUses { 384 // Some use of i.s that don't understand lurks. Give up. 385 continue 386 } 387 388 // At this point, we've decided that we *can* do 389 // the optimization. 390 391 if i.transition == nil { 392 // Exclusive for its whole lifetime. That means it 393 // didn't escape. We can already handle nonescaping 394 // slices without this pass. 395 continue 396 } 397 if i.appendWeight < 2 { 398 // This optimization only really helps if there is 399 // (dynamically) more than one append. 400 continue 401 } 402 403 // Commit point - at this point we've decided we *should* 404 // do the optimization. 405 406 // Insert a move2heap operation before the exclusive->nonexclusive 407 // transition. 408 move := ir.NewMoveToHeapExpr(i.transition.Pos(), i.s) 409 if i.capUsed { 410 move.PreserveCapacity = true 411 } 412 move.RType = reflectdata.AppendElemRType(i.transition.Pos(), i.appends[0]) 413 move.SetType(i.s.Type()) 414 move.SetTypecheck(1) 415 as := ir.NewAssignStmt(i.transition.Pos(), i.s, move) 416 as.SetTypecheck(1) 417 i.transition.PtrInit().Prepend(as) 418 // Note: we prepend because we need to put the move2heap 419 // operation first, before any other init work, as the transition 420 // might occur in the init work. 421 422 // Now that we've inserted a move2heap operation before every 423 // exclusive -> nonexclusive transition, appends can now use 424 // stack backing stores. 425 // (This is the whole point of this pass, to enable stack 426 // allocation of append backing stores.) 427 for _, a := range i.appends { 428 a.SetEsc(ir.EscNone) 429 if i.capUsed { 430 a.UseBuf = true 431 } 432 } 433 } 434 } 435 436 // argLeak reports if the idx'th argument to the call n escapes anywhere 437 // (to the heap, another argument, return value, etc.) 438 // If unknown returns true. 439 func argLeak(n *ir.CallExpr, idx int) bool { 440 if n.Op() != ir.OCALLFUNC { 441 return true 442 } 443 fn := ir.StaticCalleeName(ir.StaticValue(n.Fun)) 444 if fn == nil { 445 return true 446 } 447 fntype := fn.Type() 448 if recv := fntype.Recv(); recv != nil { 449 if idx == 0 { 450 return escape.ParseLeaks(recv.Note).Any() 451 } 452 idx-- 453 } 454 return escape.ParseLeaks(fntype.Params()[idx].Note).Any() 455 } 456