Adding upstream version 1.21.8.upstream/1.21.8

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 566 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..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
+}