Source file src/cmd/compile/internal/escape/alias.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 escape 6 7 import ( 8 "cmd/compile/internal/base" 9 "cmd/compile/internal/ir" 10 "cmd/internal/src" 11 "fmt" 12 "maps" 13 "path/filepath" 14 ) 15 16 type aliasAnalysis struct { 17 // fn is the function being analyzed. 18 fn *ir.Func 19 20 // candidateSlices are declared slices that 21 // start unaliased and might still be unaliased. 22 candidateSlices map[*ir.Name]candidateSlice 23 24 // noAliasAppends are appends that have been 25 // proven to use an unaliased slice. 26 noAliasAppends []*ir.CallExpr 27 28 // loops is a stack of observed loops, 29 // each with a list of candidate appends. 30 loops [][]candidateAppend 31 32 // State for optional validation checking (doubleCheck mode): 33 processed map[ir.Node]int // count of times each node was processed, for doubleCheck mode 34 doubleCheck bool // whether to do doubleCheck mode 35 } 36 37 // candidateSlice tracks information about a declared slice 38 // that might be unaliased. 39 type candidateSlice struct { 40 loopDepth int // depth of loop when slice was declared 41 } 42 43 // candidateAppend tracks information about an OAPPEND that 44 // might be using an unaliased slice. 45 type candidateAppend struct { 46 s *ir.Name // the slice argument in 's = append(s, ...)' 47 call *ir.CallExpr // the append call 48 } 49 50 // aliasAnalysis looks for specific patterns of slice usage and proves 51 // that certain appends are operating on non-aliased slices. 52 // 53 // This allows us to emit calls to free the backing arrays for certain 54 // non-aliased slices at runtime when we know the memory is logically dead. 55 // 56 // The analysis is conservative, giving up on any operation we do not 57 // explicitly understand. 58 func (aa *aliasAnalysis) analyze(fn *ir.Func) { 59 // Walk the function body to discover slice declarations, their uses, 60 // and any append that we can prove is using an unaliased slice. 61 // 62 // An example is: 63 // 64 // var s []T 65 // for _, v := range input { 66 // f() 67 // s = append(s, g(v)) // s cannot be aliased here 68 // h() 69 // } 70 // return s 71 // 72 // Here, we can prove that the append to s is operating on an unaliased slice, 73 // and that conclusion is unaffected by s later being returned and escaping. 74 // 75 // In contrast, in this example, the aliasing of s in the loop body means the 76 // append can be operating on an aliased slice, so we do not record s as unaliased: 77 // 78 // var s []T 79 // var alias []T 80 // for _, v := range input { 81 // s = append(s, v) // s is aliased on second pass through loop body 82 // alias = s 83 // } 84 // 85 // Arbitrary uses of s after an append do not affect the aliasing conclusion 86 // for that append, but only if the append cannot be revisited at execution time 87 // via a loop or goto. 88 // 89 // We track the loop depth when a slice was declared and verify all uses of a slice 90 // are non-aliasing until we return to that depth. In other words, we make sure 91 // we have processed any possible execution-time revisiting of the slice prior 92 // to making our final determination. 93 // 94 // This approach helps for example with nested loops, such as: 95 // 96 // var s []int 97 // for range 10 { 98 // for range 10 { 99 // s = append(s, 0) // s is proven as non-aliased here 100 // } 101 // } 102 // alias = s // both loops are complete 103 // 104 // Or in contrast: 105 // 106 // var s []int 107 // for range 10 { 108 // for range 10 { 109 // s = append(s, 0) // s is treated as aliased here 110 // } 111 // alias = s // aliased, and outermost loop cycles back 112 // } 113 // 114 // As we walk the function, we look for things like: 115 // 116 // 1. Slice declarations (currently supporting 'var s []T', 's := make([]T, ...)', 117 // and 's := []T{...}'). 118 // 2. Appends to a slice of the form 's = append(s, ...)'. 119 // 3. Other uses of the slice, which we treat as potential aliasing outside 120 // of a few known safe cases. 121 // 4. A start of a loop, which we track in a stack so that 122 // any uses of a slice within a loop body are treated as potential 123 // aliasing, including statements in the loop body after an append. 124 // Candidate appends are stored in the loop stack at the loop depth of their 125 // corresponding slice declaration (rather than the loop depth of the append), 126 // which essentially postpones a decision about the candidate append. 127 // 5. An end of a loop, which pops the loop stack and allows us to 128 // conclusively treat candidate appends from the loop body based 129 // on the loop depth of the slice declaration. 130 // 131 // Note that as we pop a candidate append at the end of a loop, we know 132 // its corresponding slice was unaliased throughout the loop being popped 133 // if the slice is still in the candidate slice map (without having been 134 // removed for potential aliasing), and we know we can make a final decision 135 // about a candidate append if we have returned to the loop depth 136 // where its slice was declared. In other words, there is no unanalyzed 137 // control flow that could take us back at execution-time to the 138 // candidate append in the now analyzed loop. This helps for example 139 // with nested loops, such as in our examples just above. 140 // 141 // We give up on a particular candidate slice if we see any use of it 142 // that we don't explicitly understand, and we give up on all of 143 // our candidate slices if we see any goto or label, which could be 144 // unstructured control flow. (TODO(thepudds): we remove the goto/label 145 // restriction in a subsequent CL.) 146 // 147 // Note that the intended use is to indicate that a slice is safe to pass 148 // to runtime.freegc, which currently requires that the passed pointer 149 // point to the base of its heap object. 150 // 151 // Therefore, we currently do not allow any re-slicing of the slice, though we could 152 // potentially allow s[0:x] or s[:x] or similar. (Slice expressions that alter 153 // the capacity might be possible to allow with freegc changes, though they are 154 // currently disallowed here like all slice expressions). 155 // 156 // TODO(thepudds): we could support the slice being used as non-escaping function call parameter 157 // but to do that, we need to verify any creation of specials via user code triggers an escape, 158 // or mail better runtime.freegc support for specials, or have a temporary compile-time solution 159 // for specials. (Currently, this analysis side-steps specials because any use of a slice 160 // that might cause a user-created special will cause it to be treated as aliased, and 161 // separately, runtime.freegc handles profiling-related specials). 162 163 // Initialize. 164 aa.fn = fn 165 aa.candidateSlices = make(map[*ir.Name]candidateSlice) // slices that might be unaliased 166 167 // doubleCheck controls whether we do a sanity check of our processing logic 168 // by counting each node visited in our main pass, and then comparing those counts 169 // against a simple walk at the end. The main intent is to help catch missing 170 // any nodes squirreled away in some spot we forgot to examine in our main pass. 171 aa.doubleCheck = base.Debug.EscapeAliasCheck > 0 172 aa.processed = make(map[ir.Node]int) 173 174 if base.Debug.EscapeAlias >= 2 { 175 aa.diag(fn.Pos(), fn, "====== starting func", "======") 176 } 177 178 ir.DoChildren(fn, aa.visit) 179 180 for _, call := range aa.noAliasAppends { 181 if base.Debug.EscapeAlias >= 1 { 182 base.WarnfAt(call.Pos(), "alias analysis: append using non-aliased slice: %v in func %v", 183 call, fn) 184 } 185 if base.Debug.FreeAppend > 0 { 186 call.AppendNoAlias = true 187 } 188 } 189 190 if aa.doubleCheck { 191 doubleCheckProcessed(fn, aa.processed) 192 } 193 } 194 195 func (aa *aliasAnalysis) visit(n ir.Node) bool { 196 if n == nil { 197 return false 198 } 199 200 if base.Debug.EscapeAlias >= 3 { 201 fmt.Printf("%-25s alias analysis: visiting node: %12s %-18T %v\n", 202 fmtPosShort(n.Pos())+":", n.Op().String(), n, n) 203 } 204 205 // As we visit nodes, we want to ensure we handle all children 206 // without missing any (through ignorance or future changes). 207 // We do this by counting nodes as we visit them or otherwise 208 // declare a node to be fully processed. 209 // 210 // In particular, we want to ensure we don't miss the use 211 // of a slice in some expression that might be an aliasing usage. 212 // 213 // When doubleCheck is enabled, we compare the counts 214 // accumulated in our analysis against counts from a trivial walk, 215 // failing if there is any mismatch. 216 // 217 // This call here counts that we have visited this node n 218 // via our main visit method. (In contrast, some nodes won't 219 // be visited by the main visit method, but instead will be 220 // manually marked via countProcessed when we believe we have fully 221 // dealt with the node). 222 aa.countProcessed(n) 223 224 switch n.Op() { 225 case ir.ODCL: 226 decl := n.(*ir.Decl) 227 228 if decl.X != nil && decl.X.Type().IsSlice() && decl.X.Class == ir.PAUTO { 229 s := decl.X 230 if _, ok := aa.candidateSlices[s]; ok { 231 base.FatalfAt(n.Pos(), "candidate slice already tracked as candidate: %v", s) 232 } 233 if base.Debug.EscapeAlias >= 2 { 234 aa.diag(n.Pos(), s, "adding candidate slice", "(loop depth: %d)", len(aa.loops)) 235 } 236 aa.candidateSlices[s] = candidateSlice{loopDepth: len(aa.loops)} 237 } 238 // No children aside from the declared ONAME. 239 aa.countProcessed(decl.X) 240 return false 241 242 case ir.ONAME: 243 244 // We are seeing a name we have not already handled in another case, 245 // so remove any corresponding candidate slice. 246 if n.Type().IsSlice() { 247 name := n.(*ir.Name) 248 _, ok := aa.candidateSlices[name] 249 if ok { 250 delete(aa.candidateSlices, name) 251 if base.Debug.EscapeAlias >= 2 { 252 aa.diag(n.Pos(), name, "removing candidate slice", "") 253 } 254 } 255 } 256 // No children. 257 return false 258 259 case ir.OAS2: 260 n := n.(*ir.AssignListStmt) 261 aa.analyzeAssign(n, n.Lhs, n.Rhs) 262 return false 263 264 case ir.OAS: 265 assign := n.(*ir.AssignStmt) 266 aa.analyzeAssign(n, []ir.Node{assign.X}, []ir.Node{assign.Y}) 267 return false 268 269 case ir.OFOR, ir.ORANGE: 270 aa.visitList(n.Init()) 271 272 if n.Op() == ir.ORANGE { 273 // TODO(thepudds): previously we visited this range expression 274 // in the switch just below, after pushing the loop. This current placement 275 // is more correct, but generate a test or find an example in stdlib or similar 276 // where it matters. (Our current tests do not complain.) 277 aa.visit(n.(*ir.RangeStmt).X) 278 } 279 280 // Push a new loop. 281 aa.loops = append(aa.loops, nil) 282 283 // Process the loop. 284 switch n.Op() { 285 case ir.OFOR: 286 forstmt := n.(*ir.ForStmt) 287 aa.visit(forstmt.Cond) 288 aa.visitList(forstmt.Body) 289 aa.visit(forstmt.Post) 290 case ir.ORANGE: 291 rangestmt := n.(*ir.RangeStmt) 292 aa.visit(rangestmt.Key) 293 aa.visit(rangestmt.Value) 294 aa.visitList(rangestmt.Body) 295 default: 296 base.Fatalf("loop not OFOR or ORANGE: %v", n) 297 } 298 299 // Pop the loop. 300 var candidateAppends []candidateAppend 301 candidateAppends, aa.loops = aa.loops[len(aa.loops)-1], aa.loops[:len(aa.loops)-1] 302 for _, a := range candidateAppends { 303 // We are done with the loop, so we can validate any candidate appends 304 // that have not had their slice removed yet. We know a slice is unaliased 305 // throughout the loop if the slice is still in the candidate slice map. 306 if cs, ok := aa.candidateSlices[a.s]; ok { 307 if cs.loopDepth == len(aa.loops) { 308 // We've returned to the loop depth where the slice was declared and 309 // hence made it all the way through any loops that started after 310 // that declaration. 311 if base.Debug.EscapeAlias >= 2 { 312 aa.diag(n.Pos(), a.s, "proved non-aliased append", 313 "(completed loop, decl at depth: %d)", cs.loopDepth) 314 } 315 aa.noAliasAppends = append(aa.noAliasAppends, a.call) 316 } else if cs.loopDepth < len(aa.loops) { 317 if base.Debug.EscapeAlias >= 2 { 318 aa.diag(n.Pos(), a.s, "cannot prove non-aliased append", 319 "(completed loop, decl at depth: %d)", cs.loopDepth) 320 } 321 } else { 322 panic("impossible: candidate slice loopDepth > current loop depth") 323 } 324 } 325 } 326 return false 327 328 case ir.OLEN, ir.OCAP: 329 n := n.(*ir.UnaryExpr) 330 if n.X.Op() == ir.ONAME { 331 // This does not disqualify a candidate slice. 332 aa.visitList(n.Init()) 333 aa.countProcessed(n.X) 334 } else { 335 ir.DoChildren(n, aa.visit) 336 } 337 return false 338 339 case ir.OCLOSURE: 340 // Give up on all our in-progress slices. 341 closure := n.(*ir.ClosureExpr) 342 if base.Debug.EscapeAlias >= 2 { 343 aa.diag(n.Pos(), closure.Func, "clearing all in-progress slices due to OCLOSURE", 344 "(was %d in-progress slices)", len(aa.candidateSlices)) 345 } 346 clear(aa.candidateSlices) 347 return ir.DoChildren(n, aa.visit) 348 349 case ir.OLABEL, ir.OGOTO: 350 // Give up on all our in-progress slices. 351 if base.Debug.EscapeAlias >= 2 { 352 aa.diag(n.Pos(), n, "clearing all in-progress slices due to label or goto", 353 "(was %d in-progress slices)", len(aa.candidateSlices)) 354 } 355 clear(aa.candidateSlices) 356 return false 357 358 default: 359 return ir.DoChildren(n, aa.visit) 360 } 361 } 362 363 func (aa *aliasAnalysis) visitList(nodes []ir.Node) { 364 for _, n := range nodes { 365 aa.visit(n) 366 } 367 } 368 369 // analyzeAssign evaluates the assignment dsts... = srcs... 370 // 371 // assign is an *ir.AssignStmt or *ir.AssignListStmt. 372 func (aa *aliasAnalysis) analyzeAssign(assign ir.Node, dsts, srcs []ir.Node) { 373 aa.visitList(assign.Init()) 374 for i := range dsts { 375 dst := dsts[i] 376 src := srcs[i] 377 378 if dst.Op() != ir.ONAME || !dst.Type().IsSlice() { 379 // Nothing for us to do aside from visiting the remaining children. 380 aa.visit(dst) 381 aa.visit(src) 382 continue 383 } 384 385 // We have a slice being assigned to an ONAME. 386 387 // Check for simple zero value assignments to an ONAME, which we ignore. 388 if src == nil { 389 aa.countProcessed(dst) 390 continue 391 } 392 393 if base.Debug.EscapeAlias >= 4 { 394 srcfn := "" 395 if src.Op() == ir.ONAME { 396 srcfn = fmt.Sprintf("%v.", src.Name().Curfn) 397 } 398 aa.diag(assign.Pos(), assign, "visiting slice assignment", "%v.%v = %s%v (%s %T = %s %T)", 399 dst.Name().Curfn, dst, srcfn, src, dst.Op().String(), dst, src.Op().String(), src) 400 } 401 402 // Now check what we have on the RHS. 403 switch src.Op() { 404 // Cases: 405 406 // Check for s := make([]T, ...) or s := []T{...}, along with the '=' version 407 // of those which does not alias s as long as s is not used in the make. 408 // 409 // TODO(thepudds): we need to be sure that 's := []T{1,2,3}' does not end up backed by a 410 // global static. Ad-hoc testing indicates that example and similar seem to be 411 // stack allocated, but that was not exhaustive testing. We do have runtime.freegc 412 // able to throw if it finds a global static, but should test more. 413 // 414 // TODO(thepudds): could also possibly allow 's := append([]T(nil), ...)' 415 // and 's := append([]T{}, ...)'. 416 case ir.OMAKESLICE, ir.OSLICELIT: 417 name := dst.(*ir.Name) 418 if name.Class == ir.PAUTO { 419 if base.Debug.EscapeAlias > 1 { 420 aa.diag(assign.Pos(), assign, "assignment from make or slice literal", "") 421 } 422 // If this is Def=true, the ODCL in the init will causes this to be tracked 423 // as a candidate slice. We walk the init and RHS but avoid visiting the name 424 // in the LHS, which would remove the slice from the candidate list after it 425 // was just added. 426 aa.visit(src) 427 aa.countProcessed(name) 428 continue 429 } 430 431 // Check for s = append(s, <...>). 432 case ir.OAPPEND: 433 s := dst.(*ir.Name) 434 call := src.(*ir.CallExpr) 435 if call.Args[0] == s { 436 // Matches s = append(s, <...>). 437 // First visit other arguments in case they use s. 438 aa.visitList(call.Args[1:]) 439 // Mark the call as processed, and s twice. 440 aa.countProcessed(s, call, s) 441 442 // We have now examined all non-ONAME children of assign. 443 444 // This is now the heart of the analysis. 445 // Check to see if this slice is a live candidate. 446 cs, ok := aa.candidateSlices[s] 447 if ok { 448 if cs.loopDepth == len(aa.loops) { 449 // No new loop has started after the declaration of s, 450 // so this is definitive. 451 if base.Debug.EscapeAlias >= 2 { 452 aa.diag(assign.Pos(), assign, "proved non-aliased append", 453 "(loop depth: %d, equals decl depth)", len(aa.loops)) 454 } 455 aa.noAliasAppends = append(aa.noAliasAppends, call) 456 } else if cs.loopDepth < len(aa.loops) { 457 // A new loop has started since the declaration of s, 458 // so we can't validate this append yet, but 459 // remember it in case we can validate it later when 460 // all loops using s are done. 461 aa.loops[cs.loopDepth] = append(aa.loops[cs.loopDepth], 462 candidateAppend{s: s, call: call}) 463 } else { 464 panic("impossible: candidate slice loopDepth > current loop depth") 465 } 466 } 467 continue 468 } 469 } // End of switch on src.Op(). 470 471 // Reached bottom of the loop over assignments. 472 // If we get here, we need to visit the dst and src normally. 473 aa.visit(dst) 474 aa.visit(src) 475 } 476 } 477 478 func (aa *aliasAnalysis) countProcessed(nodes ...ir.Node) { 479 if aa.doubleCheck { 480 for _, n := range nodes { 481 aa.processed[n]++ 482 } 483 } 484 } 485 486 func (aa *aliasAnalysis) diag(pos src.XPos, n ir.Node, what string, format string, args ...any) { 487 fmt.Printf("%-25s alias analysis: %-30s %-20s %s\n", 488 fmtPosShort(pos)+":", 489 what+":", 490 fmt.Sprintf("%v", n), 491 fmt.Sprintf(format, args...)) 492 } 493 494 // doubleCheckProcessed does a sanity check for missed nodes in our visit. 495 func doubleCheckProcessed(fn *ir.Func, processed map[ir.Node]int) { 496 // Do a trivial walk while counting the nodes 497 // to compare against the counts in processed. 498 499 observed := make(map[ir.Node]int) 500 var walk func(n ir.Node) bool 501 walk = func(n ir.Node) bool { 502 observed[n]++ 503 return ir.DoChildren(n, walk) 504 } 505 ir.DoChildren(fn, walk) 506 507 if !maps.Equal(processed, observed) { 508 // The most likely mistake might be something was missed while building processed, 509 // so print extra details in that direction. 510 for n, observedCount := range observed { 511 processedCount, ok := processed[n] 512 if processedCount != observedCount || !ok { 513 base.WarnfAt(n.Pos(), 514 "alias analysis: mismatch for %T: %v: processed %d times, observed %d times", 515 n, n, processedCount, observedCount) 516 } 517 } 518 base.FatalfAt(fn.Pos(), "alias analysis: mismatch in visited nodes") 519 } 520 } 521 522 func fmtPosShort(xpos src.XPos) string { 523 // TODO(thepudds): I think I did this a simpler way a while ago? Or maybe add base.FmtPosShort 524 // or similar? Or maybe just use base.FmtPos and give up on nicely aligned log messages? 525 pos := base.Ctxt.PosTable.Pos(xpos) 526 shortLine := filepath.Base(pos.AbsFilename()) + ":" + pos.LineNumber() 527 return shortLine 528 } 529