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