diff options
Diffstat (limited to 'src/cmd/compile/internal/pgo/irgraph.go')
| -rw-r--r-- | src/cmd/compile/internal/pgo/irgraph.go | 603 |
1 files changed, 603 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/pgo/irgraph.go b/src/cmd/compile/internal/pgo/irgraph.go new file mode 100644 index 0000000..96485e3 --- /dev/null +++ b/src/cmd/compile/internal/pgo/irgraph.go @@ -0,0 +1,603 @@ +// Copyright 2022 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// A note on line numbers: when working with line numbers, we always use the +// binary-visible relative line number. i.e., the line number as adjusted by +// //line directives (ctxt.InnermostPos(ir.Node.Pos()).RelLine()). Use +// NodeLineOffset to compute line offsets. +// +// If you are thinking, "wait, doesn't that just make things more complex than +// using the real line number?", then you are 100% correct. Unfortunately, +// pprof profiles generated by the runtime always contain line numbers as +// adjusted by //line directives (because that is what we put in pclntab). Thus +// for the best behavior when attempting to match the source with the profile +// it makes sense to use the same line number space. +// +// Some of the effects of this to keep in mind: +// +// - For files without //line directives there is no impact, as RelLine() == +// Line(). +// - For functions entirely covered by the same //line directive (i.e., a +// directive before the function definition and no directives within the +// function), there should also be no impact, as line offsets within the +// function should be the same as the real line offsets. +// - Functions containing //line directives may be impacted. As fake line +// numbers need not be monotonic, we may compute negative line offsets. We +// should accept these and attempt to use them for best-effort matching, as +// these offsets should still match if the source is unchanged, and may +// continue to match with changed source depending on the impact of the +// changes on fake line numbers. +// - Functions containing //line directives may also contain duplicate lines, +// making it ambiguous which call the profile is referencing. This is a +// similar problem to multiple calls on a single real line, as we don't +// currently track column numbers. +// +// Long term it would be best to extend pprof profiles to include real line +// numbers. Until then, we have to live with these complexities. Luckily, +// //line directives that change line numbers in strange ways should be rare, +// and failing PGO matching on these files is not too big of a loss. + +package pgo + +import ( + "cmd/compile/internal/base" + "cmd/compile/internal/ir" + "cmd/compile/internal/pgo/internal/graph" + "cmd/compile/internal/typecheck" + "cmd/compile/internal/types" + "errors" + "fmt" + "internal/profile" + "os" + "sort" +) + +// IRGraph is a call graph with nodes pointing to IRs of functions and edges +// carrying weights and callsite information. +// +// Nodes for indirect calls may have missing IR (IRNode.AST == nil) if the node +// is not visible from this package (e.g., not in the transitive deps). Keeping +// these nodes allows determining the hottest edge from a call even if that +// callee is not available. +// +// TODO(prattmic): Consider merging this data structure with Graph. This is +// effectively a copy of Graph aggregated to line number and pointing to IR. +type IRGraph struct { + // Nodes of the graph. Each node represents a function, keyed by linker + // symbol name. + IRNodes map[string]*IRNode +} + +// IRNode represents a node (function) in the IRGraph. +type IRNode struct { + // Pointer to the IR of the Function represented by this node. + AST *ir.Func + // Linker symbol name of the Function represented by this node. + // Populated only if AST == nil. + LinkerSymbolName string + + // Set of out-edges in the callgraph. The map uniquely identifies each + // edge based on the callsite and callee, for fast lookup. + OutEdges map[NamedCallEdge]*IREdge +} + +// Name returns the symbol name of this function. +func (i *IRNode) Name() string { + if i.AST != nil { + return ir.LinkFuncName(i.AST) + } + return i.LinkerSymbolName +} + +// IREdge represents a call edge in the IRGraph with source, destination, +// weight, callsite, and line number information. +type IREdge struct { + // Source and destination of the edge in IRNode. + Src, Dst *IRNode + Weight int64 + CallSiteOffset int // Line offset from function start line. +} + +// NamedCallEdge identifies a call edge by linker symbol names and call site +// offset. +type NamedCallEdge struct { + CallerName string + CalleeName string + CallSiteOffset int // Line offset from function start line. +} + +// NamedEdgeMap contains all unique call edges in the profile and their +// edge weight. +type NamedEdgeMap struct { + Weight map[NamedCallEdge]int64 + + // ByWeight lists all keys in Weight, sorted by edge weight. + ByWeight []NamedCallEdge +} + +// CallSiteInfo captures call-site information and its caller/callee. +type CallSiteInfo struct { + LineOffset int // Line offset from function start line. + Caller *ir.Func + Callee *ir.Func +} + +// Profile contains the processed PGO profile and weighted call graph used for +// PGO optimizations. +type Profile struct { + // Aggregated edge weights across the profile. This helps us determine + // the percentage threshold for hot/cold partitioning. + TotalWeight int64 + + // NamedEdgeMap contains all unique call edges in the profile and their + // edge weight. + NamedEdgeMap NamedEdgeMap + + // WeightedCG represents the IRGraph built from profile, which we will + // update as part of inlining. + WeightedCG *IRGraph +} + +// New generates a profile-graph from the profile. +func New(profileFile string) (*Profile, error) { + f, err := os.Open(profileFile) + if err != nil { + return nil, fmt.Errorf("error opening profile: %w", err) + } + defer f.Close() + p, err := profile.Parse(f) + if errors.Is(err, profile.ErrNoData) { + // Treat a completely empty file the same as a profile with no + // samples: nothing to do. + return nil, nil + } else if err != nil { + return nil, fmt.Errorf("error parsing profile: %w", err) + } + + if len(p.Sample) == 0 { + // We accept empty profiles, but there is nothing to do. + return nil, nil + } + + valueIndex := -1 + for i, s := range p.SampleType { + // Samples count is the raw data collected, and CPU nanoseconds is just + // a scaled version of it, so either one we can find is fine. + if (s.Type == "samples" && s.Unit == "count") || + (s.Type == "cpu" && s.Unit == "nanoseconds") { + valueIndex = i + break + } + } + + if valueIndex == -1 { + return nil, fmt.Errorf(`profile does not contain a sample index with value/type "samples/count" or cpu/nanoseconds"`) + } + + g := graph.NewGraph(p, &graph.Options{ + SampleValue: func(v []int64) int64 { return v[valueIndex] }, + }) + + namedEdgeMap, totalWeight, err := createNamedEdgeMap(g) + if err != nil { + return nil, err + } + + if totalWeight == 0 { + return nil, nil // accept but ignore profile with no samples. + } + + // Create package-level call graph with weights from profile and IR. + wg := createIRGraph(namedEdgeMap) + + return &Profile{ + TotalWeight: totalWeight, + NamedEdgeMap: namedEdgeMap, + WeightedCG: wg, + }, nil +} + +// createNamedEdgeMap builds a map of callsite-callee edge weights from the +// profile-graph. +// +// Caller should ignore the profile if totalWeight == 0. +func createNamedEdgeMap(g *graph.Graph) (edgeMap NamedEdgeMap, totalWeight int64, err error) { + seenStartLine := false + + // Process graph and build various node and edge maps which will + // be consumed by AST walk. + weight := make(map[NamedCallEdge]int64) + for _, n := range g.Nodes { + seenStartLine = seenStartLine || n.Info.StartLine != 0 + + canonicalName := n.Info.Name + // Create the key to the nodeMapKey. + namedEdge := NamedCallEdge{ + CallerName: canonicalName, + CallSiteOffset: n.Info.Lineno - n.Info.StartLine, + } + + for _, e := range n.Out { + totalWeight += e.WeightValue() + namedEdge.CalleeName = e.Dest.Info.Name + // Create new entry or increment existing entry. + weight[namedEdge] += e.WeightValue() + } + } + + if totalWeight == 0 { + return NamedEdgeMap{}, 0, nil // accept but ignore profile with no samples. + } + + if !seenStartLine { + // TODO(prattmic): If Function.start_line is missing we could + // fall back to using absolute line numbers, which is better + // than nothing. + return NamedEdgeMap{}, 0, fmt.Errorf("profile missing Function.start_line data (Go version of profiled application too old? Go 1.20+ automatically adds this to profiles)") + } + + byWeight := make([]NamedCallEdge, 0, len(weight)) + for namedEdge := range weight { + byWeight = append(byWeight, namedEdge) + } + sort.Slice(byWeight, func(i, j int) bool { + ei, ej := byWeight[i], byWeight[j] + if wi, wj := weight[ei], weight[ej]; wi != wj { + return wi > wj // want larger weight first + } + // same weight, order by name/line number + if ei.CallerName != ej.CallerName { + return ei.CallerName < ej.CallerName + } + if ei.CalleeName != ej.CalleeName { + return ei.CalleeName < ej.CalleeName + } + return ei.CallSiteOffset < ej.CallSiteOffset + }) + + edgeMap = NamedEdgeMap{ + Weight: weight, + ByWeight: byWeight, + } + + return edgeMap, totalWeight, nil +} + +// initializeIRGraph builds the IRGraph by visiting all the ir.Func in decl list +// of a package. +func createIRGraph(namedEdgeMap NamedEdgeMap) *IRGraph { + g := &IRGraph{ + IRNodes: make(map[string]*IRNode), + } + + // Bottomup walk over the function to create IRGraph. + ir.VisitFuncsBottomUp(typecheck.Target.Funcs, func(list []*ir.Func, recursive bool) { + for _, fn := range list { + visitIR(fn, namedEdgeMap, g) + } + }) + + // Add additional edges for indirect calls. This must be done second so + // that IRNodes is fully populated (see the dummy node TODO in + // addIndirectEdges). + // + // TODO(prattmic): visitIR above populates the graph via direct calls + // discovered via the IR. addIndirectEdges populates the graph via + // calls discovered via the profile. This combination of opposite + // approaches is a bit awkward, particularly because direct calls are + // discoverable via the profile as well. Unify these into a single + // approach. + addIndirectEdges(g, namedEdgeMap) + + return g +} + +// visitIR traverses the body of each ir.Func adds edges to g from ir.Func to +// any called function in the body. +func visitIR(fn *ir.Func, namedEdgeMap NamedEdgeMap, g *IRGraph) { + name := ir.LinkFuncName(fn) + node, ok := g.IRNodes[name] + if !ok { + node = &IRNode{ + AST: fn, + } + g.IRNodes[name] = node + } + + // Recursively walk over the body of the function to create IRGraph edges. + createIRGraphEdge(fn, node, name, namedEdgeMap, g) +} + +// createIRGraphEdge traverses the nodes in the body of ir.Func and adds edges +// between the callernode which points to the ir.Func and the nodes in the +// body. +func createIRGraphEdge(fn *ir.Func, callernode *IRNode, name string, namedEdgeMap NamedEdgeMap, g *IRGraph) { + ir.VisitList(fn.Body, func(n ir.Node) { + switch n.Op() { + case ir.OCALLFUNC: + call := n.(*ir.CallExpr) + // Find the callee function from the call site and add the edge. + callee := DirectCallee(call.Fun) + if callee != nil { + addIREdge(callernode, name, n, callee, namedEdgeMap, g) + } + case ir.OCALLMETH: + call := n.(*ir.CallExpr) + // Find the callee method from the call site and add the edge. + callee := ir.MethodExprName(call.Fun).Func + addIREdge(callernode, name, n, callee, namedEdgeMap, g) + } + }) +} + +// NodeLineOffset returns the line offset of n in fn. +func NodeLineOffset(n ir.Node, fn *ir.Func) int { + // See "A note on line numbers" at the top of the file. + line := int(base.Ctxt.InnermostPos(n.Pos()).RelLine()) + startLine := int(base.Ctxt.InnermostPos(fn.Pos()).RelLine()) + return line - startLine +} + +// addIREdge adds an edge between caller and new node that points to `callee` +// based on the profile-graph and NodeMap. +func addIREdge(callerNode *IRNode, callerName string, call ir.Node, callee *ir.Func, namedEdgeMap NamedEdgeMap, g *IRGraph) { + calleeName := ir.LinkFuncName(callee) + calleeNode, ok := g.IRNodes[calleeName] + if !ok { + calleeNode = &IRNode{ + AST: callee, + } + g.IRNodes[calleeName] = calleeNode + } + + namedEdge := NamedCallEdge{ + CallerName: callerName, + CalleeName: calleeName, + CallSiteOffset: NodeLineOffset(call, callerNode.AST), + } + + // Add edge in the IRGraph from caller to callee. + edge := &IREdge{ + Src: callerNode, + Dst: calleeNode, + Weight: namedEdgeMap.Weight[namedEdge], + CallSiteOffset: namedEdge.CallSiteOffset, + } + + if callerNode.OutEdges == nil { + callerNode.OutEdges = make(map[NamedCallEdge]*IREdge) + } + callerNode.OutEdges[namedEdge] = edge +} + +// LookupFunc looks up a function or method in export data. It is expected to +// be overridden by package noder, to break a dependency cycle. +var LookupFunc = func(fullName string) (*ir.Func, error) { + base.Fatalf("pgo.LookupMethodFunc not overridden") + panic("unreachable") +} + +// addIndirectEdges adds indirect call edges found in the profile to the graph, +// to be used for devirtualization. +// +// N.B. despite the name, addIndirectEdges will add any edges discovered via +// the profile. We don't know for sure that they are indirect, but assume they +// are since direct calls would already be added. (e.g., direct calls that have +// been deleted from source since the profile was taken would be added here). +// +// TODO(prattmic): Devirtualization runs before inlining, so we can't devirtualize +// calls inside inlined call bodies. If we did add that, we'd need edges from +// inlined bodies as well. +func addIndirectEdges(g *IRGraph, namedEdgeMap NamedEdgeMap) { + // g.IRNodes is populated with the set of functions in the local + // package build by VisitIR. We want to filter for local functions + // below, but we also add unknown callees to IRNodes as we go. So make + // an initial copy of IRNodes to recall just the local functions. + localNodes := make(map[string]*IRNode, len(g.IRNodes)) + for k, v := range g.IRNodes { + localNodes[k] = v + } + + // N.B. We must consider edges in a stable order because export data + // lookup order (LookupMethodFunc, below) can impact the export data of + // this package, which must be stable across different invocations for + // reproducibility. + // + // The weight ordering of ByWeight is irrelevant, it just happens to be + // an ordered list of edges that is already available. + for _, key := range namedEdgeMap.ByWeight { + weight := namedEdgeMap.Weight[key] + // All callers in the local package build were added to IRNodes + // in VisitIR. If a caller isn't in the local package build we + // can skip adding edges, since we won't be devirtualizing in + // them anyway. This keeps the graph smaller. + callerNode, ok := localNodes[key.CallerName] + if !ok { + continue + } + + // Already handled this edge? + if _, ok := callerNode.OutEdges[key]; ok { + continue + } + + calleeNode, ok := g.IRNodes[key.CalleeName] + if !ok { + // IR is missing for this callee. VisitIR populates + // IRNodes with all functions discovered via local + // package function declarations and calls. This + // function may still be available from export data of + // a transitive dependency. + // + // TODO(prattmic): Parameterized types/functions are + // not supported. + // + // TODO(prattmic): This eager lookup during graph load + // is simple, but wasteful. We are likely to load many + // functions that we never need. We could delay load + // until we actually need the method in + // devirtualization. Instantiation of generic functions + // will likely need to be done at the devirtualization + // site, if at all. + fn, err := LookupFunc(key.CalleeName) + if err == nil { + if base.Debug.PGODebug >= 3 { + fmt.Printf("addIndirectEdges: %s found in export data\n", key.CalleeName) + } + calleeNode = &IRNode{AST: fn} + + // N.B. we could call createIRGraphEdge to add + // direct calls in this newly-imported + // function's body to the graph. Similarly, we + // could add to this function's queue to add + // indirect calls. However, those would be + // useless given the visit order of inlining, + // and the ordering of PGO devirtualization and + // inlining. This function can only be used as + // an inlined body. We will never do PGO + // devirtualization inside an inlined call. Nor + // will we perform inlining inside an inlined + // call. + } else { + // Still not found. Most likely this is because + // the callee isn't in the transitive deps of + // this package. + // + // Record this call anyway. If this is the hottest, + // then we want to skip devirtualization rather than + // devirtualizing to the second most common callee. + if base.Debug.PGODebug >= 3 { + fmt.Printf("addIndirectEdges: %s not found in export data: %v\n", key.CalleeName, err) + } + calleeNode = &IRNode{LinkerSymbolName: key.CalleeName} + } + + // Add dummy node back to IRNodes. We don't need this + // directly, but PrintWeightedCallGraphDOT uses these + // to print nodes. + g.IRNodes[key.CalleeName] = calleeNode + } + edge := &IREdge{ + Src: callerNode, + Dst: calleeNode, + Weight: weight, + CallSiteOffset: key.CallSiteOffset, + } + + if callerNode.OutEdges == nil { + callerNode.OutEdges = make(map[NamedCallEdge]*IREdge) + } + callerNode.OutEdges[key] = edge + } +} + +// WeightInPercentage converts profile weights to a percentage. +func WeightInPercentage(value int64, total int64) float64 { + return (float64(value) / float64(total)) * 100 +} + +// PrintWeightedCallGraphDOT prints IRGraph in DOT format. +func (p *Profile) PrintWeightedCallGraphDOT(edgeThreshold float64) { + fmt.Printf("\ndigraph G {\n") + fmt.Printf("forcelabels=true;\n") + + // List of functions in this package. + funcs := make(map[string]struct{}) + ir.VisitFuncsBottomUp(typecheck.Target.Funcs, func(list []*ir.Func, recursive bool) { + for _, f := range list { + name := ir.LinkFuncName(f) + funcs[name] = struct{}{} + } + }) + + // Determine nodes of DOT. + // + // Note that ir.Func may be nil for functions not visible from this + // package. + nodes := make(map[string]*ir.Func) + for name := range funcs { + if n, ok := p.WeightedCG.IRNodes[name]; ok { + for _, e := range n.OutEdges { + if _, ok := nodes[e.Src.Name()]; !ok { + nodes[e.Src.Name()] = e.Src.AST + } + if _, ok := nodes[e.Dst.Name()]; !ok { + nodes[e.Dst.Name()] = e.Dst.AST + } + } + if _, ok := nodes[n.Name()]; !ok { + nodes[n.Name()] = n.AST + } + } + } + + // Print nodes. + for name, ast := range nodes { + if _, ok := p.WeightedCG.IRNodes[name]; ok { + style := "solid" + if ast == nil { + style = "dashed" + } + + if ast != nil && ast.Inl != nil { + fmt.Printf("\"%v\" [color=black, style=%s, label=\"%v,inl_cost=%d\"];\n", name, style, name, ast.Inl.Cost) + } else { + fmt.Printf("\"%v\" [color=black, style=%s, label=\"%v\"];\n", name, style, name) + } + } + } + // Print edges. + ir.VisitFuncsBottomUp(typecheck.Target.Funcs, func(list []*ir.Func, recursive bool) { + for _, f := range list { + name := ir.LinkFuncName(f) + if n, ok := p.WeightedCG.IRNodes[name]; ok { + for _, e := range n.OutEdges { + style := "solid" + if e.Dst.AST == nil { + style = "dashed" + } + color := "black" + edgepercent := WeightInPercentage(e.Weight, p.TotalWeight) + if edgepercent > edgeThreshold { + color = "red" + } + + fmt.Printf("edge [color=%s, style=%s];\n", color, style) + fmt.Printf("\"%v\" -> \"%v\" [label=\"%.2f\"];\n", n.Name(), e.Dst.Name(), edgepercent) + } + } + } + }) + fmt.Printf("}\n") +} + +// DirectCallee takes a function-typed expression and returns the underlying +// function that it refers to if statically known. Otherwise, it returns nil. +// +// Equivalent to inline.inlCallee without calling CanInline on closures. +func DirectCallee(fn ir.Node) *ir.Func { + fn = ir.StaticValue(fn) + switch fn.Op() { + case ir.OMETHEXPR: + fn := fn.(*ir.SelectorExpr) + n := ir.MethodExprName(fn) + // Check that receiver type matches fn.X. + // TODO(mdempsky): Handle implicit dereference + // of pointer receiver argument? + if n == nil || !types.Identical(n.Type().Recv().Type, fn.X.Type()) { + return nil + } + return n.Func + case ir.ONAME: + fn := fn.(*ir.Name) + if fn.Class == ir.PFUNC { + return fn.Func + } + case ir.OCLOSURE: + fn := fn.(*ir.ClosureExpr) + c := fn.Func + return c + } + return nil +} |