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