src/cmd/compile/internal/escape/escape.go

   1 // Copyright 2018 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         "fmt"
   9
  10         "cmd/compile/internal/base"
  11         "cmd/compile/internal/ir"
  12         "cmd/compile/internal/logopt"
  13         "cmd/compile/internal/typecheck"
  14         "cmd/compile/internal/types"
  15         "cmd/internal/src"
  16 )
  17
  18 // Escape analysis.
  19 //
  20 // Here we analyze functions to determine which Go variables
  21 // (including implicit allocations such as calls to "new" or "make",
  22 // composite literals, etc.) can be allocated on the stack. The two
  23 // key invariants we have to ensure are: (1) pointers to stack objects
  24 // cannot be stored in the heap, and (2) pointers to a stack object
  25 // cannot outlive that object (e.g., because the declaring function
  26 // returned and destroyed the object's stack frame, or its space is
  27 // reused across loop iterations for logically distinct variables).
  28 //
  29 // We implement this with a static data-flow analysis of the AST.
  30 // First, we construct a directed weighted graph where vertices
  31 // (termed "locations") represent variables allocated by statements
  32 // and expressions, and edges represent assignments between variables
  33 // (with weights representing addressing/dereference counts).
  34 //
  35 // Next we walk the graph looking for assignment paths that might
  36 // violate the invariants stated above. If a variable v's address is
  37 // stored in the heap or elsewhere that may outlive it, then v is
  38 // marked as requiring heap allocation.
  39 //
  40 // To support interprocedural analysis, we also record data-flow from
  41 // each function's parameters to the heap and to its result
  42 // parameters. This information is summarized as "parameter tags",
  43 // which are used at static call sites to improve escape analysis of
  44 // function arguments.
  45
  46 // Constructing the location graph.
  47 //
  48 // Every allocating statement (e.g., variable declaration) or
  49 // expression (e.g., "new" or "make") is first mapped to a unique
  50 // "location."
  51 //
  52 // We also model every Go assignment as a directed edges between
  53 // locations. The number of dereference operations minus the number of
  54 // addressing operations is recorded as the edge's weight (termed
  55 // "derefs"). For example:
  56 //
  57 //     p = &q    // -1
  58 //     p = q     //  0
  59 //     p = *q    //  1
  60 //     p = **q   //  2
  61 //
  62 //     p = **&**&q  // 2
  63 //
  64 // Note that the & operator can only be applied to addressable
  65 // expressions, and the expression &x itself is not addressable, so
  66 // derefs cannot go below -1.
  67 //
  68 // Every Go language construct is lowered into this representation,
  69 // generally without sensitivity to flow, path, or context; and
  70 // without distinguishing elements within a compound variable. For
  71 // example:
  72 //
  73 //     var x struct { f, g *int }
  74 //     var u []*int
  75 //
  76 //     x.f = u[0]
  77 //
  78 // is modeled simply as
  79 //
  80 //     x = *u
  81 //
  82 // That is, we don't distinguish x.f from x.g, or u[0] from u[1],
  83 // u[2], etc. However, we do record the implicit dereference involved
  84 // in indexing a slice.
  85
  86 // A batch holds escape analysis state that's shared across an entire
  87 // batch of functions being analyzed at once.
  88 type batch struct {
  89         allLocs  []*location
  90         closures []closure
  91
  92         heapLoc    location
  93         mutatorLoc location
  94         calleeLoc  location
  95         blankLoc   location
  96 }
  97
  98 // A closure holds a closure expression and its spill hole (i.e.,
  99 // where the hole representing storing into its closure record).
 100 type closure struct {
 101         k   hole
 102         clo *ir.ClosureExpr
 103 }
 104
 105 // An escape holds state specific to a single function being analyzed
 106 // within a batch.
 107 type escape struct {
 108         *batch
 109
 110         curfn *ir.Func // function being analyzed
 111
 112         labels map[*types.Sym]labelState // known labels
 113
 114         // loopDepth counts the current loop nesting depth within
 115         // curfn. It increments within each "for" loop and at each
 116         // label with a corresponding backwards "goto" (i.e.,
 117         // unstructured loop).
 118         loopDepth int
 119 }
 120
 121 func Funcs(all []*ir.Func) {
 122         ir.VisitFuncsBottomUp(all, Batch)
 123 }
 124
 125 // Batch performs escape analysis on a minimal batch of
 126 // functions.
 127 func Batch(fns []*ir.Func, recursive bool) {
 128         for _, fn := range fns {
 129                 if fn.Op() != ir.ODCLFUNC {
 130                         base.Fatalf("unexpected node: %v", fn)
 131                 }
 132         }
 133
 134         var b batch
 135         b.heapLoc.attrs = attrEscapes | attrPersists | attrMutates | attrCalls
 136         b.mutatorLoc.attrs = attrMutates
 137         b.calleeLoc.attrs = attrCalls
 138
 139         // Construct data-flow graph from syntax trees.
 140         for _, fn := range fns {
 141                 if base.Flag.W > 1 {
 142                         s := fmt.Sprintf("\nbefore escape %v", fn)
 143                         ir.Dump(s, fn)
 144                 }
 145                 b.initFunc(fn)
 146         }
 147         for _, fn := range fns {
 148                 if !fn.IsHiddenClosure() {
 149                         b.walkFunc(fn)
 150                 }
 151         }
 152
 153         // We've walked the function bodies, so we've seen everywhere a
 154         // variable might be reassigned or have it's address taken. Now we
 155         // can decide whether closures should capture their free variables
 156         // by value or reference.
 157         for _, closure := range b.closures {
 158                 b.flowClosure(closure.k, closure.clo)
 159         }
 160         b.closures = nil
 161
 162         for _, loc := range b.allLocs {
 163                 if why := HeapAllocReason(loc.n); why != "" {
 164                         b.flow(b.heapHole().addr(loc.n, why), loc)
 165                 }
 166         }
 167
 168         b.walkAll()
 169         b.finish(fns)
 170 }
 171
 172 func (b *batch) with(fn *ir.Func) *escape {
 173         return &escape{
 174                 batch:     b,
 175                 curfn:     fn,
 176                 loopDepth: 1,
 177         }
 178 }
 179
 180 func (b *batch) initFunc(fn *ir.Func) {
 181         e := b.with(fn)
 182         if fn.Esc() != escFuncUnknown {
 183                 base.Fatalf("unexpected node: %v", fn)
 184         }
 185         fn.SetEsc(escFuncPlanned)
 186         if base.Flag.LowerM > 3 {
 187                 ir.Dump("escAnalyze", fn)
 188         }
 189
 190         // Allocate locations for local variables.
 191         for _, n := range fn.Dcl {
 192                 e.newLoc(n, true)
 193         }
 194
 195         // Also for hidden parameters (e.g., the ".this" parameter to a
 196         // method value wrapper).
 197         if fn.OClosure == nil {
 198                 for _, n := range fn.ClosureVars {
 199                         e.newLoc(n.Canonical(), true)
 200                 }
 201         }
 202
 203         // Initialize resultIndex for result parameters.
 204         for i, f := range fn.Type().Results().FieldSlice() {
 205                 e.oldLoc(f.Nname.(*ir.Name)).resultIndex = 1 + i
 206         }
 207 }
 208
 209 func (b *batch) walkFunc(fn *ir.Func) {
 210         e := b.with(fn)
 211         fn.SetEsc(escFuncStarted)
 212
 213         // Identify labels that mark the head of an unstructured loop.
 214         ir.Visit(fn, func(n ir.Node) {
 215                 switch n.Op() {
 216                 case ir.OLABEL:
 217                         n := n.(*ir.LabelStmt)
 218                         if n.Label.IsBlank() {
 219                                 break
 220                         }
 221                         if e.labels == nil {
 222                                 e.labels = make(map[*types.Sym]labelState)
 223                         }
 224                         e.labels[n.Label] = nonlooping
 225
 226                 case ir.OGOTO:
 227                         // If we visited the label before the goto,
 228                         // then this is a looping label.
 229                         n := n.(*ir.BranchStmt)
 230                         if e.labels[n.Label] == nonlooping {
 231                                 e.labels[n.Label] = looping
 232                         }
 233                 }
 234         })
 235
 236         e.block(fn.Body)
 237
 238         if len(e.labels) != 0 {
 239                 base.FatalfAt(fn.Pos(), "leftover labels after walkFunc")
 240         }
 241 }
 242
 243 func (b *batch) flowClosure(k hole, clo *ir.ClosureExpr) {
 244         for _, cv := range clo.Func.ClosureVars {
 245                 n := cv.Canonical()
 246                 loc := b.oldLoc(cv)
 247                 if !loc.captured {
 248                         base.FatalfAt(cv.Pos(), "closure variable never captured: %v", cv)
 249                 }
 250
 251                 // Capture by value for variables <= 128 bytes that are never reassigned.
 252                 n.SetByval(!loc.addrtaken && !loc.reassigned && n.Type().Size() <= 128)
 253                 if !n.Byval() {
 254                         n.SetAddrtaken(true)
 255                         if n.Sym().Name == typecheck.LocalDictName {
 256                                 base.FatalfAt(n.Pos(), "dictionary variable not captured by value")
 257                         }
 258                 }
 259
 260                 if base.Flag.LowerM > 1 {
 261                         how := "ref"
 262                         if n.Byval() {
 263                                 how = "value"
 264                         }
 265                         base.WarnfAt(n.Pos(), "%v capturing by %s: %v (addr=%v assign=%v width=%d)", n.Curfn, how, n, loc.addrtaken, loc.reassigned, n.Type().Size())
 266                 }
 267
 268                 // Flow captured variables to closure.
 269                 k := k
 270                 if !cv.Byval() {
 271                         k = k.addr(cv, "reference")
 272                 }
 273                 b.flow(k.note(cv, "captured by a closure"), loc)
 274         }
 275 }
 276
 277 func (b *batch) finish(fns []*ir.Func) {
 278         // Record parameter tags for package export data.
 279         for _, fn := range fns {
 280                 fn.SetEsc(escFuncTagged)
 281
 282                 narg := 0
 283                 for _, fs := range &types.RecvsParams {
 284                         for _, f := range fs(fn.Type()).Fields().Slice() {
 285                                 narg++
 286                                 f.Note = b.paramTag(fn, narg, f)
 287                         }
 288                 }
 289         }
 290
 291         for _, loc := range b.allLocs {
 292                 n := loc.n
 293                 if n == nil {
 294                         continue
 295                 }
 296
 297                 if n.Op() == ir.ONAME {
 298                         n := n.(*ir.Name)
 299                         n.Opt = nil
 300                 }
 301
 302                 // Update n.Esc based on escape analysis results.
 303
 304                 // Omit escape diagnostics for go/defer wrappers, at least for now.
 305                 // Historically, we haven't printed them, and test cases don't expect them.
 306                 // TODO(mdempsky): Update tests to expect this.
 307                 goDeferWrapper := n.Op() == ir.OCLOSURE && n.(*ir.ClosureExpr).Func.Wrapper()
 308
 309                 if loc.hasAttr(attrEscapes) {
 310                         if n.Op() == ir.ONAME {
 311                                 if base.Flag.CompilingRuntime {
 312                                         base.ErrorfAt(n.Pos(), 0, "%v escapes to heap, not allowed in runtime", n)
 313                                 }
 314                                 if base.Flag.LowerM != 0 {
 315                                         base.WarnfAt(n.Pos(), "moved to heap: %v", n)
 316                                 }
 317                         } else {
 318                                 if base.Flag.LowerM != 0 && !goDeferWrapper {
 319                                         base.WarnfAt(n.Pos(), "%v escapes to heap", n)
 320                                 }
 321                                 if logopt.Enabled() {
 322                                         var e_curfn *ir.Func // TODO(mdempsky): Fix.
 323                                         logopt.LogOpt(n.Pos(), "escape", "escape", ir.FuncName(e_curfn))
 324                                 }
 325                         }
 326                         n.SetEsc(ir.EscHeap)
 327                 } else {
 328                         if base.Flag.LowerM != 0 && n.Op() != ir.ONAME && !goDeferWrapper {
 329                                 base.WarnfAt(n.Pos(), "%v does not escape", n)
 330                         }
 331                         n.SetEsc(ir.EscNone)
 332                         if !loc.hasAttr(attrPersists) {
 333                                 switch n.Op() {
 334                                 case ir.OCLOSURE:
 335                                         n := n.(*ir.ClosureExpr)
 336                                         n.SetTransient(true)
 337                                 case ir.OMETHVALUE:
 338                                         n := n.(*ir.SelectorExpr)
 339                                         n.SetTransient(true)
 340                                 case ir.OSLICELIT:
 341                                         n := n.(*ir.CompLitExpr)
 342                                         n.SetTransient(true)
 343                                 }
 344                         }
 345                 }
 346
 347                 // If the result of a string->[]byte conversion is never mutated,
 348                 // then it can simply reuse the string's memory directly.
 349                 if base.Debug.ZeroCopy != 0 {
 350                         if n, ok := n.(*ir.ConvExpr); ok && n.Op() == ir.OSTR2BYTES && !loc.hasAttr(attrMutates) {
 351                                 if base.Flag.LowerM >= 1 {
 352                                         base.WarnfAt(n.Pos(), "zero-copy string->[]byte conversion")
 353                                 }
 354                                 n.SetOp(ir.OSTR2BYTESTMP)
 355                         }
 356                 }
 357         }
 358 }
 359
 360 // inMutualBatch reports whether function fn is in the batch of
 361 // mutually recursive functions being analyzed. When this is true,
 362 // fn has not yet been analyzed, so its parameters and results
 363 // should be incorporated directly into the flow graph instead of
 364 // relying on its escape analysis tagging.
 365 func (b *batch) inMutualBatch(fn *ir.Name) bool {
 366         if fn.Defn != nil && fn.Defn.Esc() < escFuncTagged {
 367                 if fn.Defn.Esc() == escFuncUnknown {
 368                         base.FatalfAt(fn.Pos(), "graph inconsistency: %v", fn)
 369                 }
 370                 return true
 371         }
 372         return false
 373 }
 374
 375 const (
 376         escFuncUnknown = 0 + iota
 377         escFuncPlanned
 378         escFuncStarted
 379         escFuncTagged
 380 )
 381
 382 // Mark labels that have no backjumps to them as not increasing e.loopdepth.
 383 type labelState int
 384
 385 const (
 386         looping labelState = 1 + iota
 387         nonlooping
 388 )
 389
 390 func (b *batch) paramTag(fn *ir.Func, narg int, f *types.Field) string {
 391         name := func() string {
 392                 if f.Sym != nil {
 393                         return f.Sym.Name
 394                 }
 395                 return fmt.Sprintf("arg#%d", narg)
 396         }
 397
 398         // Only report diagnostics for user code;
 399         // not for wrappers generated around them.
 400         // TODO(mdempsky): Generalize this.
 401         diagnose := base.Flag.LowerM != 0 && !(fn.Wrapper() || fn.Dupok())
 402
 403         if len(fn.Body) == 0 {
 404                 // Assume that uintptr arguments must be held live across the call.
 405                 // This is most important for syscall.Syscall.
 406                 // See golang.org/issue/13372.
 407                 // This really doesn't have much to do with escape analysis per se,
 408                 // but we are reusing the ability to annotate an individual function
 409                 // argument and pass those annotations along to importing code.
 410                 fn.Pragma |= ir.UintptrKeepAlive
 411
 412                 if f.Type.IsUintptr() {
 413                         if diagnose {
 414                                 base.WarnfAt(f.Pos, "assuming %v is unsafe uintptr", name())
 415                         }
 416                         return ""
 417                 }
 418
 419                 if !f.Type.HasPointers() { // don't bother tagging for scalars
 420                         return ""
 421                 }
 422
 423                 var esc leaks
 424
 425                 // External functions are assumed unsafe, unless
 426                 // //go:noescape is given before the declaration.
 427                 if fn.Pragma&ir.Noescape != 0 {
 428                         if diagnose && f.Sym != nil {
 429                                 base.WarnfAt(f.Pos, "%v does not escape", name())
 430                         }
 431                         esc.AddMutator(0)
 432                         esc.AddCallee(0)
 433                 } else {
 434                         if diagnose && f.Sym != nil {
 435                                 base.WarnfAt(f.Pos, "leaking param: %v", name())
 436                         }
 437                         esc.AddHeap(0)
 438                 }
 439
 440                 return esc.Encode()
 441         }
 442
 443         if fn.Pragma&ir.UintptrEscapes != 0 {
 444                 if f.Type.IsUintptr() {
 445                         if diagnose {
 446                                 base.WarnfAt(f.Pos, "marking %v as escaping uintptr", name())
 447                         }
 448                         return ""
 449                 }
 450                 if f.IsDDD() && f.Type.Elem().IsUintptr() {
 451                         // final argument is ...uintptr.
 452                         if diagnose {
 453                                 base.WarnfAt(f.Pos, "marking %v as escaping ...uintptr", name())
 454                         }
 455                         return ""
 456                 }
 457         }
 458
 459         if !f.Type.HasPointers() { // don't bother tagging for scalars
 460                 return ""
 461         }
 462
 463         // Unnamed parameters are unused and therefore do not escape.
 464         if f.Sym == nil || f.Sym.IsBlank() {
 465                 var esc leaks
 466                 return esc.Encode()
 467         }
 468
 469         n := f.Nname.(*ir.Name)
 470         loc := b.oldLoc(n)
 471         esc := loc.paramEsc
 472         esc.Optimize()
 473
 474         if diagnose && !loc.hasAttr(attrEscapes) {
 475                 b.reportLeaks(f.Pos, name(), esc, fn.Type())
 476         }
 477
 478         return esc.Encode()
 479 }
 480
 481 func (b *batch) reportLeaks(pos src.XPos, name string, esc leaks, sig *types.Type) {
 482         warned := false
 483         if x := esc.Heap(); x >= 0 {
 484                 if x == 0 {
 485                         base.WarnfAt(pos, "leaking param: %v", name)
 486                 } else {
 487                         // TODO(mdempsky): Mention level=x like below?
 488                         base.WarnfAt(pos, "leaking param content: %v", name)
 489                 }
 490                 warned = true
 491         }
 492         for i := 0; i < numEscResults; i++ {
 493                 if x := esc.Result(i); x >= 0 {
 494                         res := sig.Results().Field(i).Sym
 495                         base.WarnfAt(pos, "leaking param: %v to result %v level=%d", name, res, x)
 496                         warned = true
 497                 }
 498         }
 499
 500         if base.Debug.EscapeMutationsCalls <= 0 {
 501                 if !warned {
 502                         base.WarnfAt(pos, "%v does not escape", name)
 503                 }
 504                 return
 505         }
 506
 507         if x := esc.Mutator(); x >= 0 {
 508                 base.WarnfAt(pos, "mutates param: %v derefs=%v", name, x)
 509                 warned = true
 510         }
 511         if x := esc.Callee(); x >= 0 {
 512                 base.WarnfAt(pos, "calls param: %v derefs=%v", name, x)
 513                 warned = true
 514         }
 515
 516         if !warned {
 517                 base.WarnfAt(pos, "%v does not escape, mutate, or call", name)
 518         }
 519 }