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.
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.
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.
17 // Some of the effects of this to keep in mind:
19 // - For files without //line directives there is no impact, as RelLine() ==
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.
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.
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"
54 // IRGraph is a call graph with nodes pointing to IRs of functions and edges
55 // carrying weights and callsite information.
57 // Nodes for indirect calls may have missing IR (IRNode.AST == nil) if the node
58 // is not visible from this package (e.g., not in the transitive deps). Keeping
59 // these nodes allows determining the hottest edge from a call even if that
60 // callee is not available.
62 // TODO(prattmic): Consider merging this data structure with Graph. This is
63 // effectively a copy of Graph aggregated to line number and pointing to IR.
66 IRNodes map[string]*IRNode
69 // IRNode represents a node (function) in the IRGraph.
71 // Pointer to the IR of the Function represented by this node.
73 // Linker symbol name of the Function represented by this node.
74 // Populated only if AST == nil.
75 LinkerSymbolName string
77 // Set of out-edges in the callgraph. The map uniquely identifies each
78 // edge based on the callsite and callee, for fast lookup.
79 OutEdges map[NodeMapKey]*IREdge
82 // Name returns the symbol name of this function.
83 func (i *IRNode) Name() string {
85 return ir.LinkFuncName(i.AST)
87 return i.LinkerSymbolName
90 // IREdge represents a call edge in the IRGraph with source, destination,
91 // weight, callsite, and line number information.
93 // Source and destination of the edge in IRNode.
96 CallSiteOffset int // Line offset from function start line.
99 // NodeMapKey represents a hash key to identify unique call-edges in profile
100 // and in IR. Used for deduplication of call edges found in profile.
102 // TODO(prattmic): rename to something more descriptive.
103 type NodeMapKey struct {
106 CallSiteOffset int // Line offset from function start line.
109 // Weights capture both node weight and edge weight.
110 type Weights struct {
116 // CallSiteInfo captures call-site information and its caller/callee.
117 type CallSiteInfo struct {
118 LineOffset int // Line offset from function start line.
123 // Profile contains the processed PGO profile and weighted call graph used for
124 // PGO optimizations.
125 type Profile struct {
126 // Aggregated NodeWeights and EdgeWeights across the profile. This
127 // helps us determine the percentage threshold for hot/cold
129 TotalNodeWeight int64
130 TotalEdgeWeight int64
132 // NodeMap contains all unique call-edges in the profile and their
133 // aggregated weight.
134 NodeMap map[NodeMapKey]*Weights
136 // WeightedCG represents the IRGraph built from profile, which we will
137 // update as part of inlining.
141 // New generates a profile-graph from the profile.
142 func New(profileFile string) (*Profile, error) {
143 f, err := os.Open(profileFile)
145 return nil, fmt.Errorf("error opening profile: %w", err)
148 profile, err := profile.Parse(f)
150 return nil, fmt.Errorf("error parsing profile: %w", err)
153 if len(profile.Sample) == 0 {
154 // We accept empty profiles, but there is nothing to do.
159 for i, s := range profile.SampleType {
160 // Samples count is the raw data collected, and CPU nanoseconds is just
161 // a scaled version of it, so either one we can find is fine.
162 if (s.Type == "samples" && s.Unit == "count") ||
163 (s.Type == "cpu" && s.Unit == "nanoseconds") {
169 if valueIndex == -1 {
170 return nil, fmt.Errorf(`profile does not contain a sample index with value/type "samples/count" or cpu/nanoseconds"`)
173 g := graph.NewGraph(profile, &graph.Options{
174 SampleValue: func(v []int64) int64 { return v[valueIndex] },
178 NodeMap: make(map[NodeMapKey]*Weights),
179 WeightedCG: &IRGraph{
180 IRNodes: make(map[string]*IRNode),
184 // Build the node map and totals from the profile graph.
185 if err := p.processprofileGraph(g); err != nil {
189 if p.TotalNodeWeight == 0 || p.TotalEdgeWeight == 0 {
190 return nil, nil // accept but ignore profile with no samples.
193 // Create package-level call graph with weights from profile and IR.
194 p.initializeIRGraph()
199 // processprofileGraph builds various maps from the profile-graph.
201 // It initializes NodeMap and Total{Node,Edge}Weight based on the name and
202 // callsite to compute node and edge weights which will be used later on to
203 // create edges for WeightedCG.
205 // Caller should ignore the profile if p.TotalNodeWeight == 0 || p.TotalEdgeWeight == 0.
206 func (p *Profile) processprofileGraph(g *graph.Graph) error {
207 nFlat := make(map[string]int64)
208 nCum := make(map[string]int64)
209 seenStartLine := false
211 // Accummulate weights for the same node.
212 for _, n := range g.Nodes {
213 canonicalName := n.Info.Name
214 nFlat[canonicalName] += n.FlatValue()
215 nCum[canonicalName] += n.CumValue()
218 // Process graph and build various node and edge maps which will
219 // be consumed by AST walk.
220 for _, n := range g.Nodes {
221 seenStartLine = seenStartLine || n.Info.StartLine != 0
223 p.TotalNodeWeight += n.FlatValue()
224 canonicalName := n.Info.Name
225 // Create the key to the nodeMapKey.
226 nodeinfo := NodeMapKey{
227 CallerName: canonicalName,
228 CallSiteOffset: n.Info.Lineno - n.Info.StartLine,
231 for _, e := range n.Out {
232 p.TotalEdgeWeight += e.WeightValue()
233 nodeinfo.CalleeName = e.Dest.Info.Name
234 if w, ok := p.NodeMap[nodeinfo]; ok {
235 w.EWeight += e.WeightValue()
237 weights := new(Weights)
238 weights.NFlat = nFlat[canonicalName]
239 weights.NCum = nCum[canonicalName]
240 weights.EWeight = e.WeightValue()
241 p.NodeMap[nodeinfo] = weights
246 if p.TotalNodeWeight == 0 || p.TotalEdgeWeight == 0 {
247 return nil // accept but ignore profile with no samples.
251 // TODO(prattmic): If Function.start_line is missing we could
252 // fall back to using absolute line numbers, which is better
254 return fmt.Errorf("profile missing Function.start_line data (Go version of profiled application too old? Go 1.20+ automatically adds this to profiles)")
260 // initializeIRGraph builds the IRGraph by visiting all the ir.Func in decl list
262 func (p *Profile) initializeIRGraph() {
263 // Bottomup walk over the function to create IRGraph.
264 ir.VisitFuncsBottomUp(typecheck.Target.Funcs, func(list []*ir.Func, recursive bool) {
265 for _, fn := range list {
270 // Add additional edges for indirect calls. This must be done second so
271 // that IRNodes is fully populated (see the dummy node TODO in
272 // addIndirectEdges).
274 // TODO(prattmic): VisitIR above populates the graph via direct calls
275 // discovered via the IR. addIndirectEdges populates the graph via
276 // calls discovered via the profile. This combination of opposite
277 // approaches is a bit awkward, particularly because direct calls are
278 // discoverable via the profile as well. Unify these into a single
283 // VisitIR traverses the body of each ir.Func and use NodeMap to determine if
284 // we need to add an edge from ir.Func and any node in the ir.Func body.
285 func (p *Profile) VisitIR(fn *ir.Func) {
288 if g.IRNodes == nil {
289 g.IRNodes = make(map[string]*IRNode)
292 name := ir.LinkFuncName(fn)
293 node, ok := g.IRNodes[name]
298 g.IRNodes[name] = node
301 // Recursively walk over the body of the function to create IRGraph edges.
302 p.createIRGraphEdge(fn, node, name)
305 // NodeLineOffset returns the line offset of n in fn.
306 func NodeLineOffset(n ir.Node, fn *ir.Func) int {
307 // See "A note on line numbers" at the top of the file.
308 line := int(base.Ctxt.InnermostPos(n.Pos()).RelLine())
309 startLine := int(base.Ctxt.InnermostPos(fn.Pos()).RelLine())
310 return line - startLine
313 // addIREdge adds an edge between caller and new node that points to `callee`
314 // based on the profile-graph and NodeMap.
315 func (p *Profile) addIREdge(callerNode *IRNode, callerName string, call ir.Node, callee *ir.Func) {
318 calleeName := ir.LinkFuncName(callee)
319 calleeNode, ok := g.IRNodes[calleeName]
321 calleeNode = &IRNode{
324 g.IRNodes[calleeName] = calleeNode
327 nodeinfo := NodeMapKey{
328 CallerName: callerName,
329 CalleeName: calleeName,
330 CallSiteOffset: NodeLineOffset(call, callerNode.AST),
334 if weights, ok := p.NodeMap[nodeinfo]; ok {
335 weight = weights.EWeight
338 // Add edge in the IRGraph from caller to callee.
343 CallSiteOffset: nodeinfo.CallSiteOffset,
346 if callerNode.OutEdges == nil {
347 callerNode.OutEdges = make(map[NodeMapKey]*IREdge)
349 callerNode.OutEdges[nodeinfo] = edge
352 // addIndirectEdges adds indirect call edges found in the profile to the graph,
353 // to be used for devirtualization.
355 // N.B. despite the name, addIndirectEdges will add any edges discovered via
356 // the profile. We don't know for sure that they are indirect, but assume they
357 // are since direct calls would already be added. (e.g., direct calls that have
358 // been deleted from source since the profile was taken would be added here).
360 // TODO(prattmic): Devirtualization runs before inlining, so we can't devirtualize
361 // calls inside inlined call bodies. If we did add that, we'd need edges from
362 // inlined bodies as well.
363 func (p *Profile) addIndirectEdges() {
366 // g.IRNodes is populated with the set of functions in the local
367 // package build by VisitIR. We want to filter for local functions
368 // below, but we also add unknown callees to IRNodes as we go. So make
369 // an initial copy of IRNodes to recall just the local functions.
370 localNodes := make(map[string]*IRNode, len(g.IRNodes))
371 for k, v := range g.IRNodes {
375 for key, weights := range p.NodeMap {
376 // All callers in the local package build were added to IRNodes
377 // in VisitIR. If a caller isn't in the local package build we
378 // can skip adding edges, since we won't be devirtualizing in
379 // them anyway. This keeps the graph smaller.
380 callerNode, ok := localNodes[key.CallerName]
385 // Already handled this edge?
386 if _, ok := callerNode.OutEdges[key]; ok {
390 calleeNode, ok := g.IRNodes[key.CalleeName]
392 // IR is missing for this callee. Most likely this is
393 // because the callee isn't in the transitive deps of
396 // Record this call anyway. If this is the hottest,
397 // then we want to skip devirtualization rather than
398 // devirtualizing to the second most common callee.
400 // TODO(prattmic): VisitIR populates IRNodes with all
401 // of the functions discovered via local package
402 // function declarations and calls. Thus we could miss
403 // functions that are available in export data of
404 // transitive deps, but aren't directly reachable. We
405 // need to do a lookup directly from package export
406 // data to get complete coverage.
407 calleeNode = &IRNode{
408 LinkerSymbolName: key.CalleeName,
409 // TODO: weights? We don't need them.
411 // Add dummy node back to IRNodes. We don't need this
412 // directly, but PrintWeightedCallGraphDOT uses these
414 g.IRNodes[key.CalleeName] = calleeNode
419 Weight: weights.EWeight,
420 CallSiteOffset: key.CallSiteOffset,
423 if callerNode.OutEdges == nil {
424 callerNode.OutEdges = make(map[NodeMapKey]*IREdge)
426 callerNode.OutEdges[key] = edge
430 // createIRGraphEdge traverses the nodes in the body of ir.Func and adds edges
431 // between the callernode which points to the ir.Func and the nodes in the
433 func (p *Profile) createIRGraphEdge(fn *ir.Func, callernode *IRNode, name string) {
434 ir.VisitList(fn.Body, func(n ir.Node) {
437 call := n.(*ir.CallExpr)
438 // Find the callee function from the call site and add the edge.
439 callee := DirectCallee(call.X)
441 p.addIREdge(callernode, name, n, callee)
444 call := n.(*ir.CallExpr)
445 // Find the callee method from the call site and add the edge.
446 callee := ir.MethodExprName(call.X).Func
447 p.addIREdge(callernode, name, n, callee)
452 // WeightInPercentage converts profile weights to a percentage.
453 func WeightInPercentage(value int64, total int64) float64 {
454 return (float64(value) / float64(total)) * 100
457 // PrintWeightedCallGraphDOT prints IRGraph in DOT format.
458 func (p *Profile) PrintWeightedCallGraphDOT(edgeThreshold float64) {
459 fmt.Printf("\ndigraph G {\n")
460 fmt.Printf("forcelabels=true;\n")
462 // List of functions in this package.
463 funcs := make(map[string]struct{})
464 ir.VisitFuncsBottomUp(typecheck.Target.Funcs, func(list []*ir.Func, recursive bool) {
465 for _, f := range list {
466 name := ir.LinkFuncName(f)
467 funcs[name] = struct{}{}
471 // Determine nodes of DOT.
473 // Note that ir.Func may be nil for functions not visible from this
475 nodes := make(map[string]*ir.Func)
476 for name := range funcs {
477 if n, ok := p.WeightedCG.IRNodes[name]; ok {
478 for _, e := range n.OutEdges {
479 if _, ok := nodes[e.Src.Name()]; !ok {
480 nodes[e.Src.Name()] = e.Src.AST
482 if _, ok := nodes[e.Dst.Name()]; !ok {
483 nodes[e.Dst.Name()] = e.Dst.AST
486 if _, ok := nodes[n.Name()]; !ok {
487 nodes[n.Name()] = n.AST
493 for name, ast := range nodes {
494 if _, ok := p.WeightedCG.IRNodes[name]; ok {
500 if ast != nil && ast.Inl != nil {
501 fmt.Printf("\"%v\" [color=black, style=%s, label=\"%v,inl_cost=%d\"];\n", name, style, name, ast.Inl.Cost)
503 fmt.Printf("\"%v\" [color=black, style=%s, label=\"%v\"];\n", name, style, name)
508 ir.VisitFuncsBottomUp(typecheck.Target.Funcs, func(list []*ir.Func, recursive bool) {
509 for _, f := range list {
510 name := ir.LinkFuncName(f)
511 if n, ok := p.WeightedCG.IRNodes[name]; ok {
512 for _, e := range n.OutEdges {
514 if e.Dst.AST == nil {
518 edgepercent := WeightInPercentage(e.Weight, p.TotalEdgeWeight)
519 if edgepercent > edgeThreshold {
523 fmt.Printf("edge [color=%s, style=%s];\n", color, style)
524 fmt.Printf("\"%v\" -> \"%v\" [label=\"%.2f\"];\n", n.Name(), e.Dst.Name(), edgepercent)
532 // DirectCallee takes a function-typed expression and returns the underlying
533 // function that it refers to if statically known. Otherwise, it returns nil.
535 // Equivalent to inline.inlCallee without calling CanInline on closures.
536 func DirectCallee(fn ir.Node) *ir.Func {
537 fn = ir.StaticValue(fn)
540 fn := fn.(*ir.SelectorExpr)
541 n := ir.MethodExprName(fn)
542 // Check that receiver type matches fn.X.
543 // TODO(mdempsky): Handle implicit dereference
544 // of pointer receiver argument?
545 if n == nil || !types.Identical(n.Type().Recv().Type, fn.X.Type()) {
551 if fn.Class == ir.PFUNC {
555 fn := fn.(*ir.ClosureExpr)