From ccd992355df7192993c666236047820244914598 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Tue, 16 Apr 2024 21:19:13 +0200 Subject: Adding upstream version 1.21.8. Signed-off-by: Daniel Baumann --- src/cmd/compile/internal/pgo/irgraph.go | 566 ++++++++++++++++++++++++++++++++ 1 file changed, 566 insertions(+) create mode 100644 src/cmd/compile/internal/pgo/irgraph.go (limited to 'src/cmd/compile/internal/pgo/irgraph.go') diff --git a/src/cmd/compile/internal/pgo/irgraph.go b/src/cmd/compile/internal/pgo/irgraph.go new file mode 100644 index 0000000..074f4a5 --- /dev/null +++ b/src/cmd/compile/internal/pgo/irgraph.go @@ -0,0 +1,566 @@ +// 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" + "fmt" + "internal/profile" + "os" +) + +// 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 + 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[NodeMapKey]*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. +} + +// NodeMapKey represents a hash key to identify unique call-edges in profile +// and in IR. Used for deduplication of call edges found in profile. +// +// TODO(prattmic): rename to something more descriptive. +type NodeMapKey struct { + CallerName string + CalleeName string + CallSiteOffset int // Line offset from function start line. +} + +// Weights capture both node weight and edge weight. +type Weights struct { + NFlat int64 + NCum int64 + EWeight int64 +} + +// 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 NodeWeights and EdgeWeights across the profile. This + // helps us determine the percentage threshold for hot/cold + // partitioning. + TotalNodeWeight int64 + TotalEdgeWeight int64 + + // NodeMap contains all unique call-edges in the profile and their + // aggregated weight. + NodeMap map[NodeMapKey]*Weights + + // 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() + profile, err := profile.Parse(f) + if err != nil { + return nil, fmt.Errorf("error parsing profile: %w", err) + } + + if len(profile.Sample) == 0 { + // We accept empty profiles, but there is nothing to do. + return nil, nil + } + + valueIndex := -1 + for i, s := range profile.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(profile, &graph.Options{ + SampleValue: func(v []int64) int64 { return v[valueIndex] }, + }) + + p := &Profile{ + NodeMap: make(map[NodeMapKey]*Weights), + WeightedCG: &IRGraph{ + IRNodes: make(map[string]*IRNode), + }, + } + + // Build the node map and totals from the profile graph. + if err := p.processprofileGraph(g); err != nil { + return nil, err + } + + if p.TotalNodeWeight == 0 || p.TotalEdgeWeight == 0 { + return nil, nil // accept but ignore profile with no samples. + } + + // Create package-level call graph with weights from profile and IR. + p.initializeIRGraph() + + return p, nil +} + +// processprofileGraph builds various maps from the profile-graph. +// +// It initializes NodeMap and Total{Node,Edge}Weight based on the name and +// callsite to compute node and edge weights which will be used later on to +// create edges for WeightedCG. +// +// Caller should ignore the profile if p.TotalNodeWeight == 0 || p.TotalEdgeWeight == 0. +func (p *Profile) processprofileGraph(g *graph.Graph) error { + nFlat := make(map[string]int64) + nCum := make(map[string]int64) + seenStartLine := false + + // Accummulate weights for the same node. + for _, n := range g.Nodes { + canonicalName := n.Info.Name + nFlat[canonicalName] += n.FlatValue() + nCum[canonicalName] += n.CumValue() + } + + // Process graph and build various node and edge maps which will + // be consumed by AST walk. + for _, n := range g.Nodes { + seenStartLine = seenStartLine || n.Info.StartLine != 0 + + p.TotalNodeWeight += n.FlatValue() + canonicalName := n.Info.Name + // Create the key to the nodeMapKey. + nodeinfo := NodeMapKey{ + CallerName: canonicalName, + CallSiteOffset: n.Info.Lineno - n.Info.StartLine, + } + + for _, e := range n.Out { + p.TotalEdgeWeight += e.WeightValue() + nodeinfo.CalleeName = e.Dest.Info.Name + if w, ok := p.NodeMap[nodeinfo]; ok { + w.EWeight += e.WeightValue() + } else { + weights := new(Weights) + weights.NFlat = nFlat[canonicalName] + weights.NCum = nCum[canonicalName] + weights.EWeight = e.WeightValue() + p.NodeMap[nodeinfo] = weights + } + } + } + + if p.TotalNodeWeight == 0 || p.TotalEdgeWeight == 0 { + return 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 fmt.Errorf("profile missing Function.start_line data (Go version of profiled application too old? Go 1.20+ automatically adds this to profiles)") + } + + return nil +} + +// initializeIRGraph builds the IRGraph by visiting all the ir.Func in decl list +// of a package. +func (p *Profile) initializeIRGraph() { + // Bottomup walk over the function to create IRGraph. + ir.VisitFuncsBottomUp(typecheck.Target.Decls, func(list []*ir.Func, recursive bool) { + for _, fn := range list { + p.VisitIR(fn) + } + }) + + // 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. + p.addIndirectEdges() +} + +// VisitIR traverses the body of each ir.Func and use NodeMap to determine if +// we need to add an edge from ir.Func and any node in the ir.Func body. +func (p *Profile) VisitIR(fn *ir.Func) { + g := p.WeightedCG + + if g.IRNodes == nil { + g.IRNodes = make(map[string]*IRNode) + } + + 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. + p.createIRGraphEdge(fn, node, name) +} + +// 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 (p *Profile) addIREdge(callerNode *IRNode, callerName string, call ir.Node, callee *ir.Func) { + g := p.WeightedCG + + calleeName := ir.LinkFuncName(callee) + calleeNode, ok := g.IRNodes[calleeName] + if !ok { + calleeNode = &IRNode{ + AST: callee, + } + g.IRNodes[calleeName] = calleeNode + } + + nodeinfo := NodeMapKey{ + CallerName: callerName, + CalleeName: calleeName, + CallSiteOffset: NodeLineOffset(call, callerNode.AST), + } + + var weight int64 + if weights, ok := p.NodeMap[nodeinfo]; ok { + weight = weights.EWeight + } + + // Add edge in the IRGraph from caller to callee. + edge := &IREdge{ + Src: callerNode, + Dst: calleeNode, + Weight: weight, + CallSiteOffset: nodeinfo.CallSiteOffset, + } + + if callerNode.OutEdges == nil { + callerNode.OutEdges = make(map[NodeMapKey]*IREdge) + } + callerNode.OutEdges[nodeinfo] = edge +} + +// addIndirectEdges adds indirect call edges found in the profile to the graph, +// to be used for devirtualization. +// +// targetDeclFuncs is the set of functions in typecheck.Target.Decls. Only +// edges from these functions will be added. +// +// Devirtualization is only applied to typecheck.Target.Decls functions, so there +// is no need to add edges from other functions. +// +// 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 (p *Profile) addIndirectEdges() { + g := p.WeightedCG + + // 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 + } + + for key, weights := range p.NodeMap { + // 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. 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. + // + // TODO(prattmic): VisitIR populates IRNodes with all + // of the functions discovered via local package + // function declarations and calls. Thus we could miss + // functions that are available in export data of + // transitive deps, but aren't directly reachable. We + // need to do a lookup directly from package export + // data to get complete coverage. + calleeNode = &IRNode{ + LinkerSymbolName: key.CalleeName, + // TODO: weights? We don't need them. + } + // 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: weights.EWeight, + CallSiteOffset: key.CallSiteOffset, + } + + if callerNode.OutEdges == nil { + callerNode.OutEdges = make(map[NodeMapKey]*IREdge) + } + callerNode.OutEdges[key] = edge + } +} + +// 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 (p *Profile) createIRGraphEdge(fn *ir.Func, callernode *IRNode, name string) { + 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.X) + if callee != nil { + p.addIREdge(callernode, name, n, callee) + } + case ir.OCALLMETH: + call := n.(*ir.CallExpr) + // Find the callee method from the call site and add the edge. + callee := ir.MethodExprName(call.X).Func + p.addIREdge(callernode, name, n, callee) + } + }) +} + +// 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.Decls, 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.Decls, 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.TotalEdgeWeight) + 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 +} -- cgit v1.2.3