src/cmd/compile/internal/pgo/irgraph.go

   1 // Copyright 2022 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 // WORK IN PROGRESS
   6
   7 package pgo
   8
   9 import (
  10         "cmd/compile/internal/ir"
  11         "cmd/compile/internal/typecheck"
  12         "cmd/compile/internal/types"
  13         "fmt"
  14         "internal/profile"
  15         "log"
  16         "os"
  17         "strconv"
  18         "strings"
  19 )
  20
  21 // IRGraph is the key datastrcture that is built from profile. It is essentially a call graph with nodes pointing to IRs of functions and edges carrying weights and callsite information. The graph is bidirectional that helps in removing nodes efficiently.
  22 type IRGraph struct {
  23         // Nodes of the graph
  24         IRNodes  map[string]*IRNode
  25         OutEdges IREdgeMap
  26         InEdges  IREdgeMap
  27 }
  28
  29 // IRNode represents a node in the IRGraph.
  30 type IRNode struct {
  31         // Pointer to the IR of the Function represented by this node.
  32         AST *ir.Func
  33         // Flat weight of the IRNode, obtained from profile.
  34         Flat int64
  35         // Cumulative weight of the IRNode.
  36         Cum int64
  37 }
  38
  39 // IREdgeMap maps an IRNode to its successors.
  40 type IREdgeMap map[*IRNode][]*IREdge
  41
  42 // IREdge represents a call edge in the IRGraph with source, destination, weight, callsite, and line number information.
  43 type IREdge struct {
  44         // Source and destination of the edge in IRNode.
  45         Src, Dst *IRNode
  46         Weight   int64
  47         CallSite int
  48 }
  49
  50 // NodeMapKey represents a hash key to identify unique call-edges in profile and in IR. Used for deduplication of call edges found in profile.
  51 type NodeMapKey struct {
  52         CallerName string
  53         CalleeName string
  54         CallSite   int
  55 }
  56
  57 // Weights capture both node weight and edge weight.
  58 type Weights struct {
  59         NFlat   int64
  60         NCum    int64
  61         EWeight int64
  62 }
  63
  64 // CallSiteInfo captures call-site information and its caller/callee.
  65 type CallSiteInfo struct {
  66         Line   int
  67         Caller *ir.Func
  68         Callee *ir.Func
  69 }
  70
  71 var (
  72         // Aggregated NodeWeights and EdgeWeights across profiles. This helps us determine the percentage threshold for hot/cold partitioning.
  73         GlobalTotalNodeWeight = int64(0)
  74         GlobalTotalEdgeWeight = int64(0)
  75
  76         // Global node and their aggregated weight information.
  77         GlobalNodeMap = make(map[NodeMapKey]*Weights)
  78
  79         // WeightedCG represents the IRGraph built from profile, which we will update as part of inlining.
  80         WeightedCG *IRGraph
  81
  82         // Original profile-graph.
  83         ProfileGraph *Graph
  84
  85         // Per-caller data structure to track the list of hot call sites. This gets rewritten every caller leaving it to GC for cleanup.
  86         ListOfHotCallSites = make(map[CallSiteInfo]struct{})
  87 )
  88
  89 // BuildProfileGraph generates a profile-graph from the profile.
  90 func BuildProfileGraph(profileFile string) {
  91
  92         // if possible, we should cache the profile-graph.
  93         if ProfileGraph != nil {
  94                 return
  95         }
  96
  97         // open the profile file.
  98         f, err := os.Open(profileFile)
  99         if err != nil {
 100                 log.Fatal("failed to open file " + profileFile)
 101                 return
 102         }
 103         defer f.Close()
 104         p, err := profile.Parse(f)
 105         if err != nil {
 106                 log.Fatal("failed to Parse profile file.")
 107                 return
 108         }
 109         // Build the options.
 110         opt := &Options{
 111                 CallTree:    false,
 112                 SampleValue: func(v []int64) int64 { return v[1] },
 113         }
 114         // Build the graph using profile package.
 115         ProfileGraph = New(p, opt)
 116
 117         // Build various global maps from profile.
 118         preprocessProfileGraph()
 119
 120 }
 121
 122 // BuildWeightedCallGraph generates a weighted callgraph from the profile for the current package.
 123 func BuildWeightedCallGraph() {
 124
 125         // Bail if there is no profile-graph available.
 126         if ProfileGraph == nil {
 127                 return
 128         }
 129
 130         // Create package-level call graph with weights from profile and IR.
 131         WeightedCG = createIRGraph()
 132 }
 133
 134 // ConvertLine2Int converts ir.Line string to integer.
 135 func ConvertLine2Int(line string) int {
 136         splits := strings.Split(line, ":")
 137         cs, _ := strconv.ParseInt(splits[len(splits)-2], 0, 64)
 138         return int(cs)
 139 }
 140
 141 // preprocessProfileGraph builds various maps from the profile-graph. It builds GlobalNodeMap and other information based on the name and callsite to compute node and edge weights which will be used later on to create edges for WeightedCG.
 142 func preprocessProfileGraph() {
 143         nFlat := make(map[string]int64)
 144         nCum := make(map[string]int64)
 145
 146         // Accummulate weights for the same node.
 147         for _, n := range ProfileGraph.Nodes {
 148                 canonicalName := n.Info.Name
 149                 nFlat[canonicalName] += n.FlatValue()
 150                 nCum[canonicalName] += n.CumValue()
 151         }
 152
 153         // Process ProfileGraph and build various node and edge maps which will be consumed by AST walk.
 154         for _, n := range ProfileGraph.Nodes {
 155                 GlobalTotalNodeWeight += n.FlatValue()
 156                 canonicalName := n.Info.Name
 157                 // Create the key to the NodeMapKey.
 158                 nodeinfo := NodeMapKey{
 159                         CallerName: canonicalName,
 160                         CallSite:   n.Info.Lineno,
 161                 }
 162
 163                 for _, e := range n.Out {
 164                         GlobalTotalEdgeWeight += e.WeightValue()
 165                         nodeinfo.CalleeName = e.Dest.Info.Name
 166                         if w, ok := GlobalNodeMap[nodeinfo]; ok {
 167                                 w.EWeight += e.WeightValue()
 168                         } else {
 169                                 weights := new(Weights)
 170                                 weights.NFlat = nFlat[canonicalName]
 171                                 weights.NCum = nCum[canonicalName]
 172                                 weights.EWeight = e.WeightValue()
 173                                 GlobalNodeMap[nodeinfo] = weights
 174                         }
 175                 }
 176         }
 177 }
 178
 179 // createIRGraph builds the IRGraph by visting all the ir.Func in decl list of a package.
 180 func createIRGraph() *IRGraph {
 181         var g IRGraph
 182         // Bottomup walk over the function to create IRGraph.
 183         ir.VisitFuncsBottomUp(typecheck.Target.Decls, func(list []*ir.Func, recursive bool) {
 184                 for _, n := range list {
 185                         g.Visit(n, recursive)
 186                 }
 187         })
 188         return &g
 189 }
 190
 191 // Visit traverses the body of each ir.Func and use GlobalNodeMap to determine if we need to add an edge from ir.Func and any node in the ir.Func body.
 192 func (g *IRGraph) Visit(fn *ir.Func, recursive bool) {
 193         if g.IRNodes == nil {
 194                 g.IRNodes = make(map[string]*IRNode)
 195         }
 196         if g.OutEdges == nil {
 197                 g.OutEdges = make(map[*IRNode][]*IREdge)
 198         }
 199         if g.InEdges == nil {
 200                 g.InEdges = make(map[*IRNode][]*IREdge)
 201         }
 202         name := ir.PkgFuncName(fn)
 203         node := new(IRNode)
 204         node.AST = fn
 205         if g.IRNodes[name] == nil {
 206                 g.IRNodes[name] = node
 207         }
 208         // Create the key for the NodeMapKey.
 209         nodeinfo := NodeMapKey{
 210                 CallerName: name,
 211                 CalleeName: "",
 212                 CallSite:   -1,
 213         }
 214         // If the node exists, then update its node weight.
 215         if weights, ok := GlobalNodeMap[nodeinfo]; ok {
 216                 g.IRNodes[name].Flat = weights.NFlat
 217                 g.IRNodes[name].Cum = weights.NCum
 218         }
 219
 220         // Recursively walk over the body of the function to create IRGraph edges.
 221         g.createIRGraphEdge(fn, g.IRNodes[name], name)
 222 }
 223
 224 // addEdge adds an edge between caller and new node that points to `callee` based on the profile-graph and GlobalNodeMap.
 225 func (g *IRGraph) addEdge(caller *IRNode, callee *ir.Func, n *ir.Node, callername string, line int) {
 226
 227         // Create an IRNode for the callee.
 228         calleenode := new(IRNode)
 229         calleenode.AST = callee
 230         calleename := ir.PkgFuncName(callee)
 231
 232         // Create key for NodeMapKey.
 233         nodeinfo := NodeMapKey{
 234                 CallerName: callername,
 235                 CalleeName: calleename,
 236                 CallSite:   line,
 237         }
 238
 239         // Create the callee node with node weight.
 240         if g.IRNodes[calleename] == nil {
 241                 g.IRNodes[calleename] = calleenode
 242                 nodeinfo2 := NodeMapKey{
 243                         CallerName: calleename,
 244                         CalleeName: "",
 245                         CallSite:   -1,
 246                 }
 247                 if weights, ok := GlobalNodeMap[nodeinfo2]; ok {
 248                         g.IRNodes[calleename].Flat = weights.NFlat
 249                         g.IRNodes[calleename].Cum = weights.NCum
 250                 }
 251         }
 252
 253         if weights, ok := GlobalNodeMap[nodeinfo]; ok {
 254                 caller.Flat = weights.NFlat
 255                 caller.Cum = weights.NCum
 256
 257                 // Add edge in the IRGraph from caller to callee.
 258                 info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: weights.EWeight, CallSite: line}
 259                 g.OutEdges[caller] = append(g.OutEdges[caller], info)
 260                 g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
 261         } else {
 262                 nodeinfo.CalleeName = ""
 263                 nodeinfo.CallSite = -1
 264                 if weights, ok := GlobalNodeMap[nodeinfo]; ok {
 265                         caller.Flat = weights.NFlat
 266                         caller.Cum = weights.NCum
 267                         info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: 0, CallSite: line}
 268                         g.OutEdges[caller] = append(g.OutEdges[caller], info)
 269                         g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
 270                 } else {
 271                         info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: 0, CallSite: line}
 272                         g.OutEdges[caller] = append(g.OutEdges[caller], info)
 273                         g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
 274                 }
 275         }
 276 }
 277
 278 // createIRGraphEdge traverses the nodes in the body of ir.Func and add edges between callernode which points to the ir.Func and the nodes in the body.
 279 func (g *IRGraph) createIRGraphEdge(fn *ir.Func, callernode *IRNode, name string) {
 280         var doNode func(ir.Node) bool
 281         doNode = func(n ir.Node) bool {
 282                 switch n.Op() {
 283                 default:
 284                         ir.DoChildren(n, doNode)
 285                 case ir.OCALLFUNC:
 286                         call := n.(*ir.CallExpr)
 287                         line := ConvertLine2Int(ir.Line(n))
 288                         // Find the callee function from the call site and add the edge.
 289                         f := inlCallee(call.X)
 290                         if f != nil {
 291                                 g.addEdge(callernode, f, &n, name, line)
 292                         }
 293                 case ir.OCALLMETH:
 294                         call := n.(*ir.CallExpr)
 295                         // Find the callee method from the call site and add the edge.
 296                         fn2 := ir.MethodExprName(call.X).Func
 297                         line := ConvertLine2Int(ir.Line(n))
 298                         g.addEdge(callernode, fn2, &n, name, line)
 299                 }
 300                 return false
 301         }
 302         doNode(fn)
 303 }
 304
 305 // WeightInPercentage converts profile weights to a percentage.
 306 func WeightInPercentage(value int64, total int64) float64 {
 307         var ratio float64
 308         if total != 0 {
 309                 ratio = (float64(value) / float64(total)) * 100
 310         }
 311         return ratio
 312 }
 313
 314 // PrintWeightedCallGraphDOT prints IRGraph in DOT format.
 315 func PrintWeightedCallGraphDOT(nodeThreshold float64, edgeThreshold float64) {
 316         fmt.Printf("\ndigraph G {\n")
 317         fmt.Printf("forcelabels=true;\n")
 318
 319         // List of functions in this package.
 320         funcs := make(map[string]struct{})
 321         ir.VisitFuncsBottomUp(typecheck.Target.Decls, func(list []*ir.Func, recursive bool) {
 322                 for _, f := range list {
 323                         name := ir.PkgFuncName(f)
 324                         funcs[name] = struct{}{}
 325                 }
 326         })
 327
 328         // Determine nodes of DOT.
 329         nodes := make(map[string]*ir.Func)
 330         for name, _ := range funcs {
 331                 if n, ok := WeightedCG.IRNodes[name]; ok {
 332                         for _, e := range WeightedCG.OutEdges[n] {
 333                                 if _, ok := nodes[ir.PkgFuncName(e.Src.AST)]; !ok {
 334                                         nodes[ir.PkgFuncName(e.Src.AST)] = e.Src.AST
 335                                 }
 336                                 if _, ok := nodes[ir.PkgFuncName(e.Dst.AST)]; !ok {
 337                                         nodes[ir.PkgFuncName(e.Dst.AST)] = e.Dst.AST
 338                                 }
 339                         }
 340                         if _, ok := nodes[ir.PkgFuncName(n.AST)]; !ok {
 341                                 nodes[ir.PkgFuncName(n.AST)] = n.AST
 342                         }
 343                 }
 344         }
 345
 346         // Print nodes.
 347         for name, ast := range nodes {
 348                 if n, ok := WeightedCG.IRNodes[name]; ok {
 349                         nodeweight := WeightInPercentage(n.Flat, GlobalTotalNodeWeight)
 350                         color := "black"
 351                         if nodeweight > nodeThreshold {
 352                                 color = "red"
 353                         }
 354                         if ast.Inl != nil {
 355                                 fmt.Printf("\"%v\" [color=%v,label=\"%v,freq=%.2f,inl_cost=%d\"];\n", ir.PkgFuncName(ast), color, ir.PkgFuncName(ast), nodeweight, ast.Inl.Cost)
 356                         } else {
 357                                 fmt.Printf("\"%v\" [color=%v, label=\"%v,freq=%.2f\"];\n", ir.PkgFuncName(ast), color, ir.PkgFuncName(ast), nodeweight)
 358                         }
 359                 }
 360         }
 361         // Print edges.
 362         ir.VisitFuncsBottomUp(typecheck.Target.Decls, func(list []*ir.Func, recursive bool) {
 363                 for _, f := range list {
 364                         name := ir.PkgFuncName(f)
 365                         if n, ok := WeightedCG.IRNodes[name]; ok {
 366                                 for _, e := range WeightedCG.OutEdges[n] {
 367                                         edgepercent := WeightInPercentage(e.Weight, GlobalTotalEdgeWeight)
 368                                         if edgepercent > edgeThreshold {
 369                                                 fmt.Printf("edge [color=red, style=solid];\n")
 370                                         } else {
 371                                                 fmt.Printf("edge [color=black, style=solid];\n")
 372                                         }
 373
 374                                         fmt.Printf("\"%v\" -> \"%v\" [label=\"%.2f\"];\n", ir.PkgFuncName(n.AST), ir.PkgFuncName(e.Dst.AST), edgepercent)
 375                                 }
 376                         }
 377                 }
 378         })
 379         fmt.Printf("}\n")
 380 }
 381
 382 // redirectEdges deletes the cur node out-edges and redirect them so now these edges are the parent node out-edges.
 383 func redirectEdges(g *IRGraph, parent *IRNode, cur *IRNode) {
 384         for _, outEdge := range g.OutEdges[cur] {
 385                 outEdge.Src = parent
 386                 g.OutEdges[parent] = append(g.OutEdges[parent], outEdge)
 387         }
 388         delete(g.OutEdges, cur)
 389 }
 390
 391 // RedirectEdges deletes and redirects out-edges from node cur based on inlining information via inlinedCallSites.
 392 func RedirectEdges(cur *IRNode, inlinedCallSites map[CallSiteInfo]struct{}) {
 393         g := WeightedCG
 394         for i, outEdge := range g.OutEdges[cur] {
 395                 if _, found := inlinedCallSites[CallSiteInfo{Line: outEdge.CallSite, Caller: cur.AST}]; !found {
 396                         for _, InEdge := range g.InEdges[cur] {
 397                                 if _, ok := inlinedCallSites[CallSiteInfo{Line: InEdge.CallSite, Caller: InEdge.Src.AST}]; ok {
 398                                         weight := calculateweight(g, InEdge.Src, cur)
 399                                         redirectEdge(g, InEdge.Src, cur, outEdge, weight, i)
 400                                 }
 401                         }
 402                 } else {
 403                         remove(g, cur, i, outEdge.Dst.AST.Nname)
 404                 }
 405         }
 406         removeall(g, cur)
 407 }
 408
 409 // calculateweight calculates the weight of the new redirected edge.
 410 func calculateweight(g *IRGraph, parent *IRNode, cur *IRNode) int64 {
 411         sum := int64(0)
 412         pw := int64(0)
 413         for _, InEdge := range g.InEdges[cur] {
 414                 sum = sum + InEdge.Weight
 415                 if InEdge.Src == parent {
 416                         pw = InEdge.Weight
 417                 }
 418         }
 419         weight := int64(0)
 420         if sum != 0 {
 421                 weight = pw / sum
 422         } else {
 423                 weight = pw
 424         }
 425         return weight
 426 }
 427
 428 // redirectEdge deletes the cur-node's out-edges and redirect them so now these edges are the parent node out-edges.
 429 func redirectEdge(g *IRGraph, parent *IRNode, cur *IRNode, outEdge *IREdge, weight int64, idx int) {
 430         outEdge.Src = parent
 431         outEdge.Weight = weight * outEdge.Weight
 432         g.OutEdges[parent] = append(g.OutEdges[parent], outEdge)
 433         remove(g, cur, idx, outEdge.Dst.AST.Nname)
 434 }
 435
 436 // remove deletes the cur-node's out-edges at index idx.
 437 func remove(g *IRGraph, cur *IRNode, idx int, name *ir.Name) {
 438         if len(g.OutEdges[cur]) >= 2 {
 439                 g.OutEdges[cur][idx] = &IREdge{CallSite: -1}
 440         } else {
 441                 delete(g.OutEdges, cur)
 442         }
 443 }
 444
 445 // removeall deletes all cur-node's out-edges that marked to be removed .
 446 func removeall(g *IRGraph, cur *IRNode) {
 447         for i := len(g.OutEdges[cur]) - 1; i >= 0; i-- {
 448                 if g.OutEdges[cur][i].CallSite == -1 {
 449                         g.OutEdges[cur][i] = g.OutEdges[cur][len(g.OutEdges[cur])-1]
 450                         g.OutEdges[cur] = g.OutEdges[cur][:len(g.OutEdges[cur])-1]
 451                 }
 452         }
 453 }
 454
 455 // inlCallee is same as the implementation for inl.go with one change. The change is that we do not invoke CanInline on a closure.
 456 func inlCallee(fn ir.Node) *ir.Func {
 457         fn = ir.StaticValue(fn)
 458         switch fn.Op() {
 459         case ir.OMETHEXPR:
 460                 fn := fn.(*ir.SelectorExpr)
 461                 n := ir.MethodExprName(fn)
 462                 // Check that receiver type matches fn.X.
 463                 // TODO(mdempsky): Handle implicit dereference
 464                 // of pointer receiver argument?
 465                 if n == nil || !types.Identical(n.Type().Recv().Type, fn.X.Type()) {
 466                         return nil
 467                 }
 468                 return n.Func
 469         case ir.ONAME:
 470                 fn := fn.(*ir.Name)
 471                 if fn.Class == ir.PFUNC {
 472                         return fn.Func
 473                 }
 474         case ir.OCLOSURE:
 475                 fn := fn.(*ir.ClosureExpr)
 476                 c := fn.Func
 477                 return c
 478         }
 479         return nil
 480 }