.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201105173854-bc9fc8d8c4bc/go/pointer/opt.go

   1 // Copyright 2013 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 pointer
   6
   7 // This file implements renumbering, a pre-solver optimization to
   8 // improve the efficiency of the solver's points-to set representation.
   9 //
  10 // TODO(adonovan): rename file "renumber.go"
  11
  12 import "fmt"
  13
  14 // renumber permutes a.nodes so that all nodes within an addressable
  15 // object appear before all non-addressable nodes, maintaining the
  16 // order of nodes within the same object (as required by offsetAddr).
  17 //
  18 // renumber must update every nodeid in the analysis (constraints,
  19 // Pointers, callgraph, etc) to reflect the new ordering.
  20 //
  21 // This is an optimisation to increase the locality and efficiency of
  22 // sparse representations of points-to sets.  (Typically only about
  23 // 20% of nodes are within an object.)
  24 //
  25 // NB: nodes added during solving (e.g. for reflection, SetFinalizer)
  26 // will be appended to the end.
  27 //
  28 // Renumbering makes the PTA log inscrutable.  To aid debugging, later
  29 // phases (e.g. HVN) must not rely on it having occurred.
  30 //
  31 func (a *analysis) renumber() {
  32         if a.log != nil {
  33                 fmt.Fprintf(a.log, "\n\n==== Renumbering\n\n")
  34         }
  35
  36         N := nodeid(len(a.nodes))
  37         newNodes := make([]*node, N)
  38         renumbering := make([]nodeid, N) // maps old to new
  39
  40         var i, j nodeid
  41
  42         // The zero node is special.
  43         newNodes[j] = a.nodes[i]
  44         renumbering[i] = j
  45         i++
  46         j++
  47
  48         // Pass 1: object nodes.
  49         for i < N {
  50                 obj := a.nodes[i].obj
  51                 if obj == nil {
  52                         i++
  53                         continue
  54                 }
  55
  56                 end := i + nodeid(obj.size)
  57                 for i < end {
  58                         newNodes[j] = a.nodes[i]
  59                         renumbering[i] = j
  60                         i++
  61                         j++
  62                 }
  63         }
  64         nobj := j
  65
  66         // Pass 2: non-object nodes.
  67         for i = 1; i < N; {
  68                 obj := a.nodes[i].obj
  69                 if obj != nil {
  70                         i += nodeid(obj.size)
  71                         continue
  72                 }
  73
  74                 newNodes[j] = a.nodes[i]
  75                 renumbering[i] = j
  76                 i++
  77                 j++
  78         }
  79
  80         if j != N {
  81                 panic(fmt.Sprintf("internal error: j=%d, N=%d", j, N))
  82         }
  83
  84         // Log the remapping table.
  85         if a.log != nil {
  86                 fmt.Fprintf(a.log, "Renumbering nodes to improve density:\n")
  87                 fmt.Fprintf(a.log, "(%d object nodes of %d total)\n", nobj, N)
  88                 for old, new := range renumbering {
  89                         fmt.Fprintf(a.log, "\tn%d -> n%d\n", old, new)
  90                 }
  91         }
  92
  93         // Now renumber all existing nodeids to use the new node permutation.
  94         // It is critical that all reachable nodeids are accounted for!
  95
  96         // Renumber nodeids in queried Pointers.
  97         for v, ptr := range a.result.Queries {
  98                 ptr.n = renumbering[ptr.n]
  99                 a.result.Queries[v] = ptr
 100         }
 101         for v, ptr := range a.result.IndirectQueries {
 102                 ptr.n = renumbering[ptr.n]
 103                 a.result.IndirectQueries[v] = ptr
 104         }
 105         for _, queries := range a.config.extendedQueries {
 106                 for _, query := range queries {
 107                         if query.ptr != nil {
 108                                 query.ptr.n = renumbering[query.ptr.n]
 109                         }
 110                 }
 111         }
 112
 113         // Renumber nodeids in global objects.
 114         for v, id := range a.globalobj {
 115                 a.globalobj[v] = renumbering[id]
 116         }
 117
 118         // Renumber nodeids in constraints.
 119         for _, c := range a.constraints {
 120                 c.renumber(renumbering)
 121         }
 122
 123         // Renumber nodeids in the call graph.
 124         for _, cgn := range a.cgnodes {
 125                 cgn.obj = renumbering[cgn.obj]
 126                 for _, site := range cgn.sites {
 127                         site.targets = renumbering[site.targets]
 128                 }
 129         }
 130
 131         a.nodes = newNodes
 132 }