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