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