src/cmd/compile/internal/escape/graph.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         "cmd/compile/internal/base"
   9         "cmd/compile/internal/ir"
  10         "cmd/compile/internal/logopt"
  11         "cmd/compile/internal/types"
  12         "fmt"
  13 )
  14
  15 // Below we implement the methods for walking the AST and recording
  16 // data flow edges. Note that because a sub-expression might have
  17 // side-effects, it's important to always visit the entire AST.
  18 //
  19 // For example, write either:
  20 //
  21 //     if x {
  22 //         e.discard(n.Left)
  23 //     } else {
  24 //         e.value(k, n.Left)
  25 //     }
  26 //
  27 // or
  28 //
  29 //     if x {
  30 //         k = e.discardHole()
  31 //     }
  32 //     e.value(k, n.Left)
  33 //
  34 // Do NOT write:
  35 //
  36 //    // BAD: possibly loses side-effects within n.Left
  37 //    if !x {
  38 //        e.value(k, n.Left)
  39 //    }
  40
  41 // An location represents an abstract location that stores a Go
  42 // variable.
  43 type location struct {
  44         n         ir.Node  // represented variable or expression, if any
  45         curfn     *ir.Func // enclosing function
  46         edges     []edge   // incoming edges
  47         loopDepth int      // loopDepth at declaration
  48
  49         // resultIndex records the tuple index (starting at 1) for
  50         // PPARAMOUT variables within their function's result type.
  51         // For non-PPARAMOUT variables it's 0.
  52         resultIndex int
  53
  54         // derefs and walkgen are used during walkOne to track the
  55         // minimal dereferences from the walk root.
  56         derefs  int // >= -1
  57         walkgen uint32
  58
  59         // dst and dstEdgeindex track the next immediate assignment
  60         // destination location during walkone, along with the index
  61         // of the edge pointing back to this location.
  62         dst        *location
  63         dstEdgeIdx int
  64
  65         // queued is used by walkAll to track whether this location is
  66         // in the walk queue.
  67         queued bool
  68
  69         // attrs is a bitset of location attributes.
  70         attrs locAttr
  71
  72         // paramEsc records the represented parameter's leak set.
  73         paramEsc leaks
  74
  75         captured   bool // has a closure captured this variable?
  76         reassigned bool // has this variable been reassigned?
  77         addrtaken  bool // has this variable's address been taken?
  78 }
  79
  80 type locAttr uint8
  81
  82 const (
  83         // attrEscapes indicates whether the represented variable's address
  84         // escapes; that is, whether the variable must be heap allocated.
  85         attrEscapes locAttr = 1 << iota
  86
  87         // attrPersists indicates whether the represented expression's
  88         // address outlives the statement; that is, whether its storage
  89         // cannot be immediately reused.
  90         attrPersists
  91 )
  92
  93 func (l *location) hasAttr(attr locAttr) bool { return l.attrs&attr != 0 }
  94
  95 // An edge represents an assignment edge between two Go variables.
  96 type edge struct {
  97         src    *location
  98         derefs int // >= -1
  99         notes  *note
 100 }
 101
 102 func (l *location) asHole() hole {
 103         return hole{dst: l}
 104 }
 105
 106 // leak records that parameter l leaks to sink.
 107 func (l *location) leakTo(sink *location, derefs int) {
 108         // If sink is a result parameter that doesn't escape (#44614)
 109         // and we can fit return bits into the escape analysis tag,
 110         // then record as a result leak.
 111         if !sink.hasAttr(attrEscapes) && sink.isName(ir.PPARAMOUT) && sink.curfn == l.curfn {
 112                 ri := sink.resultIndex - 1
 113                 if ri < numEscResults {
 114                         // Leak to result parameter.
 115                         l.paramEsc.AddResult(ri, derefs)
 116                         return
 117                 }
 118         }
 119
 120         // Otherwise, record as heap leak.
 121         l.paramEsc.AddHeap(derefs)
 122 }
 123
 124 func (l *location) isName(c ir.Class) bool {
 125         return l.n != nil && l.n.Op() == ir.ONAME && l.n.(*ir.Name).Class == c
 126 }
 127
 128 // A hole represents a context for evaluation of a Go
 129 // expression. E.g., when evaluating p in "x = **p", we'd have a hole
 130 // with dst==x and derefs==2.
 131 type hole struct {
 132         dst    *location
 133         derefs int // >= -1
 134         notes  *note
 135
 136         // addrtaken indicates whether this context is taking the address of
 137         // the expression, independent of whether the address will actually
 138         // be stored into a variable.
 139         addrtaken bool
 140 }
 141
 142 type note struct {
 143         next  *note
 144         where ir.Node
 145         why   string
 146 }
 147
 148 func (k hole) note(where ir.Node, why string) hole {
 149         if where == nil || why == "" {
 150                 base.Fatalf("note: missing where/why")
 151         }
 152         if base.Flag.LowerM >= 2 || logopt.Enabled() {
 153                 k.notes = &note{
 154                         next:  k.notes,
 155                         where: where,
 156                         why:   why,
 157                 }
 158         }
 159         return k
 160 }
 161
 162 func (k hole) shift(delta int) hole {
 163         k.derefs += delta
 164         if k.derefs < -1 {
 165                 base.Fatalf("derefs underflow: %v", k.derefs)
 166         }
 167         k.addrtaken = delta < 0
 168         return k
 169 }
 170
 171 func (k hole) deref(where ir.Node, why string) hole { return k.shift(1).note(where, why) }
 172 func (k hole) addr(where ir.Node, why string) hole  { return k.shift(-1).note(where, why) }
 173
 174 func (k hole) dotType(t *types.Type, where ir.Node, why string) hole {
 175         if !t.IsInterface() && !types.IsDirectIface(t) {
 176                 k = k.shift(1)
 177         }
 178         return k.note(where, why)
 179 }
 180
 181 func (b *batch) flow(k hole, src *location) {
 182         if k.addrtaken {
 183                 src.addrtaken = true
 184         }
 185
 186         dst := k.dst
 187         if dst == &b.blankLoc {
 188                 return
 189         }
 190         if dst == src && k.derefs >= 0 { // dst = dst, dst = *dst, ...
 191                 return
 192         }
 193         if dst.hasAttr(attrEscapes) && k.derefs < 0 { // dst = &src
 194                 if base.Flag.LowerM >= 2 || logopt.Enabled() {
 195                         pos := base.FmtPos(src.n.Pos())
 196                         if base.Flag.LowerM >= 2 {
 197                                 fmt.Printf("%s: %v escapes to heap:\n", pos, src.n)
 198                         }
 199                         explanation := b.explainFlow(pos, dst, src, k.derefs, k.notes, []*logopt.LoggedOpt{})
 200                         if logopt.Enabled() {
 201                                 var e_curfn *ir.Func // TODO(mdempsky): Fix.
 202                                 logopt.LogOpt(src.n.Pos(), "escapes", "escape", ir.FuncName(e_curfn), fmt.Sprintf("%v escapes to heap", src.n), explanation)
 203                         }
 204
 205                 }
 206                 src.attrs |= attrEscapes
 207                 return
 208         }
 209
 210         // TODO(mdempsky): Deduplicate edges?
 211         dst.edges = append(dst.edges, edge{src: src, derefs: k.derefs, notes: k.notes})
 212 }
 213
 214 func (b *batch) heapHole() hole    { return b.heapLoc.asHole() }
 215 func (b *batch) discardHole() hole { return b.blankLoc.asHole() }
 216
 217 func (b *batch) oldLoc(n *ir.Name) *location {
 218         if n.Canonical().Opt == nil {
 219                 base.Fatalf("%v has no location", n)
 220         }
 221         return n.Canonical().Opt.(*location)
 222 }
 223
 224 func (e *escape) newLoc(n ir.Node, persists bool) *location {
 225         if e.curfn == nil {
 226                 base.Fatalf("e.curfn isn't set")
 227         }
 228         if n != nil && n.Type() != nil && n.Type().NotInHeap() {
 229                 base.ErrorfAt(n.Pos(), 0, "%v is incomplete (or unallocatable); stack allocation disallowed", n.Type())
 230         }
 231
 232         if n != nil && n.Op() == ir.ONAME {
 233                 if canon := n.(*ir.Name).Canonical(); n != canon {
 234                         base.Fatalf("newLoc on non-canonical %v (canonical is %v)", n, canon)
 235                 }
 236         }
 237         loc := &location{
 238                 n:         n,
 239                 curfn:     e.curfn,
 240                 loopDepth: e.loopDepth,
 241         }
 242         if persists {
 243                 loc.attrs |= attrPersists
 244         }
 245         e.allLocs = append(e.allLocs, loc)
 246         if n != nil {
 247                 if n.Op() == ir.ONAME {
 248                         n := n.(*ir.Name)
 249                         if n.Class == ir.PPARAM && n.Curfn == nil {
 250                                 // ok; hidden parameter
 251                         } else if n.Curfn != e.curfn {
 252                                 base.Fatalf("curfn mismatch: %v != %v for %v", n.Curfn, e.curfn, n)
 253                         }
 254
 255                         if n.Opt != nil {
 256                                 base.Fatalf("%v already has a location", n)
 257                         }
 258                         n.Opt = loc
 259                 }
 260         }
 261         return loc
 262 }
 263
 264 // teeHole returns a new hole that flows into each hole of ks,
 265 // similar to the Unix tee(1) command.
 266 func (e *escape) teeHole(ks ...hole) hole {
 267         if len(ks) == 0 {
 268                 return e.discardHole()
 269         }
 270         if len(ks) == 1 {
 271                 return ks[0]
 272         }
 273         // TODO(mdempsky): Optimize if there's only one non-discard hole?
 274
 275         // Given holes "l1 = _", "l2 = **_", "l3 = *_", ..., create a
 276         // new temporary location ltmp, wire it into place, and return
 277         // a hole for "ltmp = _".
 278         loc := e.newLoc(nil, false)
 279         for _, k := range ks {
 280                 // N.B., "p = &q" and "p = &tmp; tmp = q" are not
 281                 // semantically equivalent. To combine holes like "l1
 282                 // = _" and "l2 = &_", we'd need to wire them as "l1 =
 283                 // *ltmp" and "l2 = ltmp" and return "ltmp = &_"
 284                 // instead.
 285                 if k.derefs < 0 {
 286                         base.Fatalf("teeHole: negative derefs")
 287                 }
 288
 289                 e.flow(k, loc)
 290         }
 291         return loc.asHole()
 292 }
 293
 294 // later returns a new hole that flows into k, but some time later.
 295 // Its main effect is to prevent immediate reuse of temporary
 296 // variables introduced during Order.
 297 func (e *escape) later(k hole) hole {
 298         loc := e.newLoc(nil, true)
 299         e.flow(k, loc)
 300         return loc.asHole()
 301 }
 302
 303 // Fmt is called from node printing to print information about escape analysis results.
 304 func Fmt(n ir.Node) string {
 305         text := ""
 306         switch n.Esc() {
 307         case ir.EscUnknown:
 308                 break
 309
 310         case ir.EscHeap:
 311                 text = "esc(h)"
 312
 313         case ir.EscNone:
 314                 text = "esc(no)"
 315
 316         case ir.EscNever:
 317                 text = "esc(N)"
 318
 319         default:
 320                 text = fmt.Sprintf("esc(%d)", n.Esc())
 321         }
 322
 323         if n.Op() == ir.ONAME {
 324                 n := n.(*ir.Name)
 325                 if loc, ok := n.Opt.(*location); ok && loc.loopDepth != 0 {
 326                         if text != "" {
 327                                 text += " "
 328                         }
 329                         text += fmt.Sprintf("ld(%d)", loc.loopDepth)
 330                 }
 331         }
 332
 333         return text
 334 }