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 }
  70
  71 // IREdgeMap maps an IRNode to its successors.
  72 type IREdgeMap map[*IRNode][]*IREdge
  73
  74 // IREdge represents a call edge in the IRGraph with source, destination,
  75 // weight, callsite, and line number information.
  76 type IREdge struct {
  77         // Source and destination of the edge in IRNode.
  78         Src, Dst       *IRNode
  79         Weight         int64
  80         CallSiteOffset int // Line offset from function start line.
  81 }
  82
  83 // NodeMapKey represents a hash key to identify unique call-edges in profile
  84 // and in IR. Used for deduplication of call edges found in profile.
  85 type NodeMapKey struct {
  86         CallerName     string
  87         CalleeName     string
  88         CallSiteOffset int // Line offset from function start line.
  89 }
  90
  91 // Weights capture both node weight and edge weight.
  92 type Weights struct {
  93         NFlat   int64
  94         NCum    int64
  95         EWeight int64
  96 }
  97
  98 // CallSiteInfo captures call-site information and its caller/callee.
  99 type CallSiteInfo struct {
 100         LineOffset int // Line offset from function start line.
 101         Caller     *ir.Func
 102         Callee     *ir.Func
 103 }
 104
 105 // Profile contains the processed PGO profile and weighted call graph used for
 106 // PGO optimizations.
 107 type Profile struct {
 108         // Aggregated NodeWeights and EdgeWeights across the profile. This
 109         // helps us determine the percentage threshold for hot/cold
 110         // partitioning.
 111         TotalNodeWeight int64
 112         TotalEdgeWeight int64
 113
 114         // NodeMap contains all unique call-edges in the profile and their
 115         // aggregated weight.
 116         NodeMap map[NodeMapKey]*Weights
 117
 118         // WeightedCG represents the IRGraph built from profile, which we will
 119         // update as part of inlining.
 120         WeightedCG *IRGraph
 121 }
 122
 123 // New generates a profile-graph from the profile.
 124 func New(profileFile string) (*Profile, error) {
 125         f, err := os.Open(profileFile)
 126         if err != nil {
 127                 return nil, fmt.Errorf("error opening profile: %w", err)
 128         }
 129         defer f.Close()
 130         profile, err := profile.Parse(f)
 131         if err != nil {
 132                 return nil, fmt.Errorf("error parsing profile: %w", err)
 133         }
 134
 135         if len(profile.Sample) == 0 {
 136                 // We accept empty profiles, but there is nothing to do.
 137                 return nil, nil
 138         }
 139
 140         valueIndex := -1
 141         for i, s := range profile.SampleType {
 142                 // Samples count is the raw data collected, and CPU nanoseconds is just
 143                 // a scaled version of it, so either one we can find is fine.
 144                 if (s.Type == "samples" && s.Unit == "count") ||
 145                         (s.Type == "cpu" && s.Unit == "nanoseconds") {
 146                         valueIndex = i
 147                         break
 148                 }
 149         }
 150
 151         if valueIndex == -1 {
 152                 return nil, fmt.Errorf(`profile does not contain a sample index with value/type "samples/count" or cpu/nanoseconds"`)
 153         }
 154
 155         g := graph.NewGraph(profile, &graph.Options{
 156                 SampleValue: func(v []int64) int64 { return v[valueIndex] },
 157         })
 158
 159         p := &Profile{
 160                 NodeMap: make(map[NodeMapKey]*Weights),
 161                 WeightedCG: &IRGraph{
 162                         IRNodes: make(map[string]*IRNode),
 163                 },
 164         }
 165
 166         // Build the node map and totals from the profile graph.
 167         if err := p.processprofileGraph(g); err != nil {
 168                 return nil, err
 169         }
 170
 171         if p.TotalNodeWeight == 0 || p.TotalEdgeWeight == 0 {
 172                 return nil, nil // accept but ignore profile with no samples.
 173         }
 174
 175         // Create package-level call graph with weights from profile and IR.
 176         p.initializeIRGraph()
 177
 178         return p, nil
 179 }
 180
 181 // processprofileGraph builds various maps from the profile-graph.
 182 //
 183 // It initializes NodeMap and Total{Node,Edge}Weight based on the name and
 184 // callsite to compute node and edge weights which will be used later on to
 185 // create edges for WeightedCG.
 186 //
 187 // Caller should ignore the profile if p.TotalNodeWeight == 0 || p.TotalEdgeWeight == 0.
 188 func (p *Profile) processprofileGraph(g *graph.Graph) error {
 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 nil // accept but ignore profile with no samples.
 230         }
 231
 232         if !seenStartLine {
 233                 // TODO(prattmic): If Function.start_line is missing we could
 234                 // fall back to using absolute line numbers, which is better
 235                 // than nothing.
 236                 return fmt.Errorf("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 nil
 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)
 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) {
 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.LinkFuncName(fn)
 268         node, ok := g.IRNodes[name]
 269         if !ok {
 270                 node = &IRNode{
 271                         AST: fn,
 272                 }
 273                 g.IRNodes[name] = node
 274         }
 275
 276         // Recursively walk over the body of the function to create IRGraph edges.
 277         p.createIRGraphEdge(fn, node, name)
 278 }
 279
 280 // NodeLineOffset returns the line offset of n in fn.
 281 func NodeLineOffset(n ir.Node, fn *ir.Func) int {
 282         // See "A note on line numbers" at the top of the file.
 283         line := int(base.Ctxt.InnermostPos(n.Pos()).RelLine())
 284         startLine := int(base.Ctxt.InnermostPos(fn.Pos()).RelLine())
 285         return line - startLine
 286 }
 287
 288 // addIREdge adds an edge between caller and new node that points to `callee`
 289 // based on the profile-graph and NodeMap.
 290 func (p *Profile) addIREdge(callerNode *IRNode, callerName string, call ir.Node, callee *ir.Func) {
 291         g := p.WeightedCG
 292
 293         calleeName := ir.LinkFuncName(callee)
 294         calleeNode, ok := g.IRNodes[calleeName]
 295         if !ok {
 296                 calleeNode = &IRNode{
 297                         AST: callee,
 298                 }
 299                 g.IRNodes[calleeName] = calleeNode
 300         }
 301
 302         nodeinfo := NodeMapKey{
 303                 CallerName:     callerName,
 304                 CalleeName:     calleeName,
 305                 CallSiteOffset: NodeLineOffset(call, callerNode.AST),
 306         }
 307
 308         var weight int64
 309         if weights, ok := p.NodeMap[nodeinfo]; ok {
 310                 weight = weights.EWeight
 311         }
 312
 313         // Add edge in the IRGraph from caller to callee.
 314         edge := &IREdge{
 315                 Src:            callerNode,
 316                 Dst:            calleeNode,
 317                 Weight:         weight,
 318                 CallSiteOffset: nodeinfo.CallSiteOffset,
 319         }
 320         g.OutEdges[callerNode] = append(g.OutEdges[callerNode], edge)
 321         g.InEdges[calleeNode] = append(g.InEdges[calleeNode], edge)
 322 }
 323
 324 // 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.
 325 func (p *Profile) createIRGraphEdge(fn *ir.Func, callernode *IRNode, name string) {
 326         var doNode func(ir.Node) bool
 327         doNode = func(n ir.Node) bool {
 328                 switch n.Op() {
 329                 default:
 330                         ir.DoChildren(n, doNode)
 331                 case ir.OCALLFUNC:
 332                         call := n.(*ir.CallExpr)
 333                         // Find the callee function from the call site and add the edge.
 334                         callee := inlCallee(call.X)
 335                         if callee != nil {
 336                                 p.addIREdge(callernode, name, n, callee)
 337                         }
 338                 case ir.OCALLMETH:
 339                         call := n.(*ir.CallExpr)
 340                         // Find the callee method from the call site and add the edge.
 341                         callee := ir.MethodExprName(call.X).Func
 342                         p.addIREdge(callernode, name, n, callee)
 343                 }
 344                 return false
 345         }
 346         doNode(fn)
 347 }
 348
 349 // WeightInPercentage converts profile weights to a percentage.
 350 func WeightInPercentage(value int64, total int64) float64 {
 351         return (float64(value) / float64(total)) * 100
 352 }
 353
 354 // PrintWeightedCallGraphDOT prints IRGraph in DOT format.
 355 func (p *Profile) PrintWeightedCallGraphDOT(edgeThreshold float64) {
 356         fmt.Printf("\ndigraph G {\n")
 357         fmt.Printf("forcelabels=true;\n")
 358
 359         // List of functions in this package.
 360         funcs := make(map[string]struct{})
 361         ir.VisitFuncsBottomUp(typecheck.Target.Decls, func(list []*ir.Func, recursive bool) {
 362                 for _, f := range list {
 363                         name := ir.LinkFuncName(f)
 364                         funcs[name] = struct{}{}
 365                 }
 366         })
 367
 368         // Determine nodes of DOT.
 369         nodes := make(map[string]*ir.Func)
 370         for name := range funcs {
 371                 if n, ok := p.WeightedCG.IRNodes[name]; ok {
 372                         for _, e := range p.WeightedCG.OutEdges[n] {
 373                                 if _, ok := nodes[ir.LinkFuncName(e.Src.AST)]; !ok {
 374                                         nodes[ir.LinkFuncName(e.Src.AST)] = e.Src.AST
 375                                 }
 376                                 if _, ok := nodes[ir.LinkFuncName(e.Dst.AST)]; !ok {
 377                                         nodes[ir.LinkFuncName(e.Dst.AST)] = e.Dst.AST
 378                                 }
 379                         }
 380                         if _, ok := nodes[ir.LinkFuncName(n.AST)]; !ok {
 381                                 nodes[ir.LinkFuncName(n.AST)] = n.AST
 382                         }
 383                 }
 384         }
 385
 386         // Print nodes.
 387         for name, ast := range nodes {
 388                 if _, ok := p.WeightedCG.IRNodes[name]; ok {
 389                         color := "black"
 390                         if ast.Inl != nil {
 391                                 fmt.Printf("\"%v\" [color=%v,label=\"%v,inl_cost=%d\"];\n", ir.LinkFuncName(ast), color, ir.LinkFuncName(ast), ast.Inl.Cost)
 392                         } else {
 393                                 fmt.Printf("\"%v\" [color=%v, label=\"%v\"];\n", ir.LinkFuncName(ast), color, ir.LinkFuncName(ast))
 394                         }
 395                 }
 396         }
 397         // Print edges.
 398         ir.VisitFuncsBottomUp(typecheck.Target.Decls, func(list []*ir.Func, recursive bool) {
 399                 for _, f := range list {
 400                         name := ir.LinkFuncName(f)
 401                         if n, ok := p.WeightedCG.IRNodes[name]; ok {
 402                                 for _, e := range p.WeightedCG.OutEdges[n] {
 403                                         edgepercent := WeightInPercentage(e.Weight, p.TotalEdgeWeight)
 404                                         if edgepercent > edgeThreshold {
 405                                                 fmt.Printf("edge [color=red, style=solid];\n")
 406                                         } else {
 407                                                 fmt.Printf("edge [color=black, style=solid];\n")
 408                                         }
 409
 410                                         fmt.Printf("\"%v\" -> \"%v\" [label=\"%.2f\"];\n", ir.LinkFuncName(n.AST), ir.LinkFuncName(e.Dst.AST), edgepercent)
 411                                 }
 412                         }
 413                 }
 414         })
 415         fmt.Printf("}\n")
 416 }
 417
 418 // inlCallee is same as the implementation for inl.go with one change. The change is that we do not invoke CanInline on a closure.
 419 func inlCallee(fn ir.Node) *ir.Func {
 420         fn = ir.StaticValue(fn)
 421         switch fn.Op() {
 422         case ir.OMETHEXPR:
 423                 fn := fn.(*ir.SelectorExpr)
 424                 n := ir.MethodExprName(fn)
 425                 // Check that receiver type matches fn.X.
 426                 // TODO(mdempsky): Handle implicit dereference
 427                 // of pointer receiver argument?
 428                 if n == nil || !types.Identical(n.Type().Recv().Type, fn.X.Type()) {
 429                         return nil
 430                 }
 431                 return n.Func
 432         case ir.ONAME:
 433                 fn := fn.(*ir.Name)
 434                 if fn.Class == ir.PFUNC {
 435                         return fn.Func
 436                 }
 437         case ir.OCLOSURE:
 438                 fn := fn.(*ir.ClosureExpr)
 439                 c := fn.Func
 440                 return c
 441         }
 442         return nil
 443 }