Source file src/cmd/compile/internal/pgoir/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 pgoir assosciates a PGO profile with the IR of the current package 42 // compilation. 43 package pgoir 44 45 import ( 46 "bufio" 47 "cmd/compile/internal/base" 48 "cmd/compile/internal/ir" 49 "cmd/compile/internal/typecheck" 50 "cmd/compile/internal/types" 51 "cmd/internal/pgo" 52 "fmt" 53 "os" 54 ) 55 56 // IRGraph is a call graph with nodes pointing to IRs of functions and edges 57 // carrying weights and callsite information. 58 // 59 // Nodes for indirect calls may have missing IR (IRNode.AST == nil) if the node 60 // is not visible from this package (e.g., not in the transitive deps). Keeping 61 // these nodes allows determining the hottest edge from a call even if that 62 // callee is not available. 63 // 64 // TODO(prattmic): Consider merging this data structure with Graph. This is 65 // effectively a copy of Graph aggregated to line number and pointing to IR. 66 type IRGraph struct { 67 // Nodes of the graph. Each node represents a function, keyed by linker 68 // symbol name. 69 IRNodes map[string]*IRNode 70 } 71 72 // IRNode represents a node (function) in the IRGraph. 73 type IRNode struct { 74 // Pointer to the IR of the Function represented by this node. 75 AST *ir.Func 76 // Linker symbol name of the Function represented by this node. 77 // Populated only if AST == nil. 78 LinkerSymbolName string 79 80 // Set of out-edges in the callgraph. The map uniquely identifies each 81 // edge based on the callsite and callee, for fast lookup. 82 OutEdges map[pgo.NamedCallEdge]*IREdge 83 } 84 85 // Name returns the symbol name of this function. 86 func (i *IRNode) Name() string { 87 if i.AST != nil { 88 return ir.LinkFuncName(i.AST) 89 } 90 return i.LinkerSymbolName 91 } 92 93 // IREdge represents a call edge in the IRGraph with source, destination, 94 // weight, callsite, and line number information. 95 type IREdge struct { 96 // Source and destination of the edge in IRNode. 97 Src, Dst *IRNode 98 Weight int64 99 CallSiteOffset int // Line offset from function start line. 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 // Profile is the base data from the raw profile, without IR attribution. 113 *pgo.Profile 114 115 // WeightedCG represents the IRGraph built from profile, which we will 116 // update as part of inlining. 117 WeightedCG *IRGraph 118 } 119 120 // New generates a profile-graph from the profile or pre-processed profile. 121 func New(profileFile string) (*Profile, error) { 122 f, err := os.Open(profileFile) 123 if err != nil { 124 return nil, fmt.Errorf("error opening profile: %w", err) 125 } 126 defer f.Close() 127 r := bufio.NewReader(f) 128 129 isSerialized, err := pgo.IsSerialized(r) 130 if err != nil { 131 return nil, fmt.Errorf("error processing profile header: %w", err) 132 } 133 134 var base *pgo.Profile 135 if isSerialized { 136 base, err = pgo.FromSerialized(r) 137 if err != nil { 138 return nil, fmt.Errorf("error processing serialized PGO profile: %w", err) 139 } 140 } else { 141 base, err = pgo.FromPProf(r) 142 if err != nil { 143 return nil, fmt.Errorf("error processing pprof PGO profile: %w", err) 144 } 145 } 146 147 if base.TotalWeight == 0 { 148 return nil, nil // accept but ignore profile with no samples. 149 } 150 151 // Create package-level call graph with weights from profile and IR. 152 wg := createIRGraph(base.NamedEdgeMap) 153 154 return &Profile{ 155 Profile: base, 156 WeightedCG: wg, 157 }, nil 158 } 159 160 // initializeIRGraph builds the IRGraph by visiting all the ir.Func in decl list 161 // of a package. 162 func createIRGraph(namedEdgeMap pgo.NamedEdgeMap) *IRGraph { 163 g := &IRGraph{ 164 IRNodes: make(map[string]*IRNode), 165 } 166 167 // Bottomup walk over the function to create IRGraph. 168 ir.VisitFuncsBottomUp(typecheck.Target.Funcs, func(list []*ir.Func, recursive bool) { 169 for _, fn := range list { 170 visitIR(fn, namedEdgeMap, g) 171 } 172 }) 173 174 // Add additional edges for indirect calls. This must be done second so 175 // that IRNodes is fully populated (see the dummy node TODO in 176 // addIndirectEdges). 177 // 178 // TODO(prattmic): visitIR above populates the graph via direct calls 179 // discovered via the IR. addIndirectEdges populates the graph via 180 // calls discovered via the profile. This combination of opposite 181 // approaches is a bit awkward, particularly because direct calls are 182 // discoverable via the profile as well. Unify these into a single 183 // approach. 184 addIndirectEdges(g, namedEdgeMap) 185 186 return g 187 } 188 189 // visitIR traverses the body of each ir.Func adds edges to g from ir.Func to 190 // any called function in the body. 191 func visitIR(fn *ir.Func, namedEdgeMap pgo.NamedEdgeMap, g *IRGraph) { 192 name := ir.LinkFuncName(fn) 193 node, ok := g.IRNodes[name] 194 if !ok { 195 node = &IRNode{ 196 AST: fn, 197 } 198 g.IRNodes[name] = node 199 } 200 201 // Recursively walk over the body of the function to create IRGraph edges. 202 createIRGraphEdge(fn, node, name, namedEdgeMap, g) 203 } 204 205 // createIRGraphEdge traverses the nodes in the body of ir.Func and adds edges 206 // between the callernode which points to the ir.Func and the nodes in the 207 // body. 208 func createIRGraphEdge(fn *ir.Func, callernode *IRNode, name string, namedEdgeMap pgo.NamedEdgeMap, g *IRGraph) { 209 ir.VisitList(fn.Body, func(n ir.Node) { 210 switch n.Op() { 211 case ir.OCALLFUNC: 212 call := n.(*ir.CallExpr) 213 // Find the callee function from the call site and add the edge. 214 callee := DirectCallee(call.Fun) 215 if callee != nil { 216 addIREdge(callernode, name, n, callee, namedEdgeMap, g) 217 } 218 case ir.OCALLMETH: 219 call := n.(*ir.CallExpr) 220 // Find the callee method from the call site and add the edge. 221 callee := ir.MethodExprName(call.Fun).Func 222 addIREdge(callernode, name, n, callee, namedEdgeMap, g) 223 } 224 }) 225 } 226 227 // NodeLineOffset returns the line offset of n in fn. 228 func NodeLineOffset(n ir.Node, fn *ir.Func) int { 229 // See "A note on line numbers" at the top of the file. 230 line := int(base.Ctxt.InnermostPos(n.Pos()).RelLine()) 231 startLine := int(base.Ctxt.InnermostPos(fn.Pos()).RelLine()) 232 return line - startLine 233 } 234 235 // addIREdge adds an edge between caller and new node that points to `callee` 236 // based on the profile-graph and NodeMap. 237 func addIREdge(callerNode *IRNode, callerName string, call ir.Node, callee *ir.Func, namedEdgeMap pgo.NamedEdgeMap, g *IRGraph) { 238 calleeName := ir.LinkFuncName(callee) 239 calleeNode, ok := g.IRNodes[calleeName] 240 if !ok { 241 calleeNode = &IRNode{ 242 AST: callee, 243 } 244 g.IRNodes[calleeName] = calleeNode 245 } 246 247 namedEdge := pgo.NamedCallEdge{ 248 CallerName: callerName, 249 CalleeName: calleeName, 250 CallSiteOffset: NodeLineOffset(call, callerNode.AST), 251 } 252 253 // Add edge in the IRGraph from caller to callee. 254 edge := &IREdge{ 255 Src: callerNode, 256 Dst: calleeNode, 257 Weight: namedEdgeMap.Weight[namedEdge], 258 CallSiteOffset: namedEdge.CallSiteOffset, 259 } 260 261 if callerNode.OutEdges == nil { 262 callerNode.OutEdges = make(map[pgo.NamedCallEdge]*IREdge) 263 } 264 callerNode.OutEdges[namedEdge] = edge 265 } 266 267 // LookupFunc looks up a function or method in export data. It is expected to 268 // be overridden by package noder, to break a dependency cycle. 269 var LookupFunc = func(fullName string) (*ir.Func, error) { 270 base.Fatalf("pgoir.LookupMethodFunc not overridden") 271 panic("unreachable") 272 } 273 274 // PostLookupCleanup performs any remaining cleanup operations needed 275 // after a series of calls to LookupFunc, specifically reading in the 276 // bodies of functions that may have been delayed due being encountered 277 // in a stage where the reader's curfn state was not set up. 278 var PostLookupCleanup = func() { 279 base.Fatalf("pgoir.PostLookupCleanup not overridden") 280 panic("unreachable") 281 } 282 283 // addIndirectEdges adds indirect call edges found in the profile to the graph, 284 // to be used for devirtualization. 285 // 286 // N.B. despite the name, addIndirectEdges will add any edges discovered via 287 // the profile. We don't know for sure that they are indirect, but assume they 288 // are since direct calls would already be added. (e.g., direct calls that have 289 // been deleted from source since the profile was taken would be added here). 290 // 291 // TODO(prattmic): Devirtualization runs before inlining, so we can't devirtualize 292 // calls inside inlined call bodies. If we did add that, we'd need edges from 293 // inlined bodies as well. 294 func addIndirectEdges(g *IRGraph, namedEdgeMap pgo.NamedEdgeMap) { 295 // g.IRNodes is populated with the set of functions in the local 296 // package build by VisitIR. We want to filter for local functions 297 // below, but we also add unknown callees to IRNodes as we go. So make 298 // an initial copy of IRNodes to recall just the local functions. 299 localNodes := make(map[string]*IRNode, len(g.IRNodes)) 300 for k, v := range g.IRNodes { 301 localNodes[k] = v 302 } 303 304 // N.B. We must consider edges in a stable order because export data 305 // lookup order (LookupMethodFunc, below) can impact the export data of 306 // this package, which must be stable across different invocations for 307 // reproducibility. 308 // 309 // The weight ordering of ByWeight is irrelevant, it just happens to be 310 // an ordered list of edges that is already available. 311 for _, key := range namedEdgeMap.ByWeight { 312 weight := namedEdgeMap.Weight[key] 313 // All callers in the local package build were added to IRNodes 314 // in VisitIR. If a caller isn't in the local package build we 315 // can skip adding edges, since we won't be devirtualizing in 316 // them anyway. This keeps the graph smaller. 317 callerNode, ok := localNodes[key.CallerName] 318 if !ok { 319 continue 320 } 321 322 // Already handled this edge? 323 if _, ok := callerNode.OutEdges[key]; ok { 324 continue 325 } 326 327 calleeNode, ok := g.IRNodes[key.CalleeName] 328 if !ok { 329 // IR is missing for this callee. VisitIR populates 330 // IRNodes with all functions discovered via local 331 // package function declarations and calls. This 332 // function may still be available from export data of 333 // a transitive dependency. 334 // 335 // TODO(prattmic): Parameterized types/functions are 336 // not supported. 337 // 338 // TODO(prattmic): This eager lookup during graph load 339 // is simple, but wasteful. We are likely to load many 340 // functions that we never need. We could delay load 341 // until we actually need the method in 342 // devirtualization. Instantiation of generic functions 343 // will likely need to be done at the devirtualization 344 // site, if at all. 345 if base.Debug.PGODebug >= 3 { 346 fmt.Printf("addIndirectEdges: %s attempting export data lookup\n", key.CalleeName) 347 } 348 fn, err := LookupFunc(key.CalleeName) 349 if err == nil { 350 if base.Debug.PGODebug >= 3 { 351 fmt.Printf("addIndirectEdges: %s found in export data\n", key.CalleeName) 352 } 353 calleeNode = &IRNode{AST: fn} 354 355 // N.B. we could call createIRGraphEdge to add 356 // direct calls in this newly-imported 357 // function's body to the graph. Similarly, we 358 // could add to this function's queue to add 359 // indirect calls. However, those would be 360 // useless given the visit order of inlining, 361 // and the ordering of PGO devirtualization and 362 // inlining. This function can only be used as 363 // an inlined body. We will never do PGO 364 // devirtualization inside an inlined call. Nor 365 // will we perform inlining inside an inlined 366 // call. 367 } else { 368 // Still not found. Most likely this is because 369 // the callee isn't in the transitive deps of 370 // this package. 371 // 372 // Record this call anyway. If this is the hottest, 373 // then we want to skip devirtualization rather than 374 // devirtualizing to the second most common callee. 375 if base.Debug.PGODebug >= 3 { 376 fmt.Printf("addIndirectEdges: %s not found in export data: %v\n", key.CalleeName, err) 377 } 378 calleeNode = &IRNode{LinkerSymbolName: key.CalleeName} 379 } 380 381 // Add dummy node back to IRNodes. We don't need this 382 // directly, but PrintWeightedCallGraphDOT uses these 383 // to print nodes. 384 g.IRNodes[key.CalleeName] = calleeNode 385 } 386 edge := &IREdge{ 387 Src: callerNode, 388 Dst: calleeNode, 389 Weight: weight, 390 CallSiteOffset: key.CallSiteOffset, 391 } 392 393 if callerNode.OutEdges == nil { 394 callerNode.OutEdges = make(map[pgo.NamedCallEdge]*IREdge) 395 } 396 callerNode.OutEdges[key] = edge 397 } 398 399 PostLookupCleanup() 400 } 401 402 // PrintWeightedCallGraphDOT prints IRGraph in DOT format. 403 func (p *Profile) PrintWeightedCallGraphDOT(edgeThreshold float64) { 404 fmt.Printf("\ndigraph G {\n") 405 fmt.Printf("forcelabels=true;\n") 406 407 // List of functions in this package. 408 funcs := make(map[string]struct{}) 409 ir.VisitFuncsBottomUp(typecheck.Target.Funcs, func(list []*ir.Func, recursive bool) { 410 for _, f := range list { 411 name := ir.LinkFuncName(f) 412 funcs[name] = struct{}{} 413 } 414 }) 415 416 // Determine nodes of DOT. 417 // 418 // Note that ir.Func may be nil for functions not visible from this 419 // package. 420 nodes := make(map[string]*ir.Func) 421 for name := range funcs { 422 if n, ok := p.WeightedCG.IRNodes[name]; ok { 423 for _, e := range n.OutEdges { 424 if _, ok := nodes[e.Src.Name()]; !ok { 425 nodes[e.Src.Name()] = e.Src.AST 426 } 427 if _, ok := nodes[e.Dst.Name()]; !ok { 428 nodes[e.Dst.Name()] = e.Dst.AST 429 } 430 } 431 if _, ok := nodes[n.Name()]; !ok { 432 nodes[n.Name()] = n.AST 433 } 434 } 435 } 436 437 // Print nodes. 438 for name, ast := range nodes { 439 if _, ok := p.WeightedCG.IRNodes[name]; ok { 440 style := "solid" 441 if ast == nil { 442 style = "dashed" 443 } 444 445 if ast != nil && ast.Inl != nil { 446 fmt.Printf("\"%v\" [color=black, style=%s, label=\"%v,inl_cost=%d\"];\n", name, style, name, ast.Inl.Cost) 447 } else { 448 fmt.Printf("\"%v\" [color=black, style=%s, label=\"%v\"];\n", name, style, name) 449 } 450 } 451 } 452 // Print edges. 453 ir.VisitFuncsBottomUp(typecheck.Target.Funcs, func(list []*ir.Func, recursive bool) { 454 for _, f := range list { 455 name := ir.LinkFuncName(f) 456 if n, ok := p.WeightedCG.IRNodes[name]; ok { 457 for _, e := range n.OutEdges { 458 style := "solid" 459 if e.Dst.AST == nil { 460 style = "dashed" 461 } 462 color := "black" 463 edgepercent := pgo.WeightInPercentage(e.Weight, p.TotalWeight) 464 if edgepercent > edgeThreshold { 465 color = "red" 466 } 467 468 fmt.Printf("edge [color=%s, style=%s];\n", color, style) 469 fmt.Printf("\"%v\" -> \"%v\" [label=\"%.2f\"];\n", n.Name(), e.Dst.Name(), edgepercent) 470 } 471 } 472 } 473 }) 474 fmt.Printf("}\n") 475 } 476 477 // DirectCallee takes a function-typed expression and returns the underlying 478 // function that it refers to if statically known. Otherwise, it returns nil. 479 // 480 // Equivalent to inline.inlCallee without calling CanInline on closures. 481 func DirectCallee(fn ir.Node) *ir.Func { 482 fn = ir.StaticValue(fn) 483 switch fn.Op() { 484 case ir.OMETHEXPR: 485 fn := fn.(*ir.SelectorExpr) 486 n := ir.MethodExprName(fn) 487 // Check that receiver type matches fn.X. 488 // TODO(mdempsky): Handle implicit dereference 489 // of pointer receiver argument? 490 if n == nil || !types.Identical(n.Type().Recv().Type, fn.X.Type()) { 491 return nil 492 } 493 return n.Func 494 case ir.ONAME: 495 fn := fn.(*ir.Name) 496 if fn.Class == ir.PFUNC { 497 return fn.Func 498 } 499 case ir.OCLOSURE: 500 fn := fn.(*ir.ClosureExpr) 501 c := fn.Func 502 return c 503 } 504 return nil 505 } 506