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.
7 // A note on line numbers: when working with line numbers, we always use the
8 // binary-visible relative line number. i.e., the line number as adjusted by
9 // //line directives (ctxt.InnermostPos(ir.Node.Pos()).RelLine()). Use
10 // NodeLineOffset to compute line offsets.
12 // If you are thinking, "wait, doesn't that just make things more complex than
13 // using the real line number?", then you are 100% correct. Unfortunately,
14 // pprof profiles generated by the runtime always contain line numbers as
15 // adjusted by //line directives (because that is what we put in pclntab). Thus
16 // for the best behavior when attempting to match the source with the profile
17 // it makes sense to use the same line number space.
19 // Some of the effects of this to keep in mind:
21 // - For files without //line directives there is no impact, as RelLine() ==
23 // - For functions entirely covered by the same //line directive (i.e., a
24 // directive before the function definition and no directives within the
25 // function), there should also be no impact, as line offsets within the
26 // function should be the same as the real line offsets.
27 // - Functions containing //line directives may be impacted. As fake line
28 // numbers need not be monotonic, we may compute negative line offsets. We
29 // should accept these and attempt to use them for best-effort matching, as
30 // these offsets should still match if the source is unchanged, and may
31 // continue to match with changed source depending on the impact of the
32 // changes on fake line numbers.
33 // - Functions containing //line directives may also contain duplicate lines,
34 // making it ambiguous which call the profile is referencing. This is a
35 // similar problem to multiple calls on a single real line, as we don't
36 // currently track column numbers.
38 // Long term it would be best to extend pprof profiles to include real line
39 // numbers. Until then, we have to live with these complexities. Luckily,
40 // //line directives that change line numbers in strange ways should be rare,
41 // and failing PGO matching on these files is not too big of a loss.
46 "cmd/compile/internal/base"
47 "cmd/compile/internal/ir"
48 "cmd/compile/internal/typecheck"
49 "cmd/compile/internal/types"
56 // IRGraph is the key data structure that is built from profile. It is
57 // essentially a call graph with nodes pointing to IRs of functions and edges
58 // carrying weights and callsite information. The graph is bidirectional that
59 // helps in removing nodes efficiently.
62 IRNodes map[string]*IRNode
67 // IRNode represents a node in the IRGraph.
69 // Pointer to the IR of the Function represented by this node.
71 // Flat weight of the IRNode, obtained from profile.
73 // Cumulative weight of the IRNode.
77 // IREdgeMap maps an IRNode to its successors.
78 type IREdgeMap map[*IRNode][]*IREdge
80 // IREdge represents a call edge in the IRGraph with source, destination,
81 // weight, callsite, and line number information.
83 // Source and destination of the edge in IRNode.
86 CallSiteOffset int // Line offset from function start line.
89 // NodeMapKey represents a hash key to identify unique call-edges in profile
90 // and in IR. Used for deduplication of call edges found in profile.
91 type NodeMapKey struct {
94 CallSiteOffset int // Line offset from function start line.
97 // Weights capture both node weight and edge weight.
104 // CallSiteInfo captures call-site information and its caller/callee.
105 type CallSiteInfo struct {
106 LineOffset int // Line offset from function start line.
111 // Profile contains the processed PGO profile and weighted call graph used for
112 // PGO optimizations.
113 type Profile struct {
114 // Aggregated NodeWeights and EdgeWeights across the profile. This
115 // helps us determine the percentage threshold for hot/cold
117 TotalNodeWeight int64
118 TotalEdgeWeight int64
120 // NodeMap contains all unique call-edges in the profile and their
121 // aggregated weight.
122 NodeMap map[NodeMapKey]*Weights
124 // WeightedCG represents the IRGraph built from profile, which we will
125 // update as part of inlining.
129 // New generates a profile-graph from the profile.
130 func New(profileFile string) *Profile {
131 f, err := os.Open(profileFile)
133 log.Fatal("failed to open file " + profileFile)
137 profile, err := profile.Parse(f)
139 log.Fatal("failed to Parse profile file.")
143 g := newGraph(profile, &Options{
145 SampleValue: func(v []int64) int64 { return v[1] },
149 NodeMap: make(map[NodeMapKey]*Weights),
150 WeightedCG: &IRGraph{
151 IRNodes: make(map[string]*IRNode),
155 // Build the node map and totals from the profile graph.
156 if !p.processprofileGraph(g) {
160 // Create package-level call graph with weights from profile and IR.
161 p.initializeIRGraph()
166 // processprofileGraph builds various maps from the profile-graph.
168 // It initializes NodeMap and Total{Node,Edge}Weight based on the name and
169 // callsite to compute node and edge weights which will be used later on to
170 // create edges for WeightedCG.
171 // Returns whether it successfully processed the profile.
172 func (p *Profile) processprofileGraph(g *Graph) bool {
173 nFlat := make(map[string]int64)
174 nCum := make(map[string]int64)
175 seenStartLine := false
177 // Accummulate weights for the same node.
178 for _, n := range g.Nodes {
179 canonicalName := n.Info.Name
180 nFlat[canonicalName] += n.FlatValue()
181 nCum[canonicalName] += n.CumValue()
184 // Process graph and build various node and edge maps which will
185 // be consumed by AST walk.
186 for _, n := range g.Nodes {
187 seenStartLine = seenStartLine || n.Info.StartLine != 0
189 p.TotalNodeWeight += n.FlatValue()
190 canonicalName := n.Info.Name
191 // Create the key to the nodeMapKey.
192 nodeinfo := NodeMapKey{
193 CallerName: canonicalName,
194 CallSiteOffset: n.Info.Lineno - n.Info.StartLine,
197 for _, e := range n.Out {
198 p.TotalEdgeWeight += e.WeightValue()
199 nodeinfo.CalleeName = e.Dest.Info.Name
200 if w, ok := p.NodeMap[nodeinfo]; ok {
201 w.EWeight += e.WeightValue()
203 weights := new(Weights)
204 weights.NFlat = nFlat[canonicalName]
205 weights.NCum = nCum[canonicalName]
206 weights.EWeight = e.WeightValue()
207 p.NodeMap[nodeinfo] = weights
212 if p.TotalNodeWeight == 0 || p.TotalEdgeWeight == 0 {
213 return false // accept but ignore profile with no sample
217 // TODO(prattic): If Function.start_line is missing we could
218 // fall back to using absolute line numbers, which is better
220 log.Fatal("PGO profile missing Function.start_line data (Go version of profiled application too old? Go 1.20+ automatically adds this to profiles)")
226 // initializeIRGraph builds the IRGraph by visiting all the ir.Func in decl list
228 func (p *Profile) initializeIRGraph() {
229 // Bottomup walk over the function to create IRGraph.
230 ir.VisitFuncsBottomUp(typecheck.Target.Decls, func(list []*ir.Func, recursive bool) {
231 for _, n := range list {
232 p.VisitIR(n, recursive)
237 // VisitIR traverses the body of each ir.Func and use NodeMap to determine if
238 // we need to add an edge from ir.Func and any node in the ir.Func body.
239 func (p *Profile) VisitIR(fn *ir.Func, recursive bool) {
242 if g.IRNodes == nil {
243 g.IRNodes = make(map[string]*IRNode)
245 if g.OutEdges == nil {
246 g.OutEdges = make(map[*IRNode][]*IREdge)
248 if g.InEdges == nil {
249 g.InEdges = make(map[*IRNode][]*IREdge)
251 name := ir.PkgFuncName(fn)
254 if g.IRNodes[name] == nil {
255 g.IRNodes[name] = node
257 // Create the key for the NodeMapKey.
258 nodeinfo := NodeMapKey{
263 // If the node exists, then update its node weight.
264 if weights, ok := p.NodeMap[nodeinfo]; ok {
265 g.IRNodes[name].Flat = weights.NFlat
266 g.IRNodes[name].Cum = weights.NCum
269 // Recursively walk over the body of the function to create IRGraph edges.
270 p.createIRGraphEdge(fn, g.IRNodes[name], name)
273 // NodeLineOffset returns the line offset of n in fn.
274 func NodeLineOffset(n ir.Node, fn *ir.Func) int {
275 // See "A note on line numbers" at the top of the file.
276 line := int(base.Ctxt.InnermostPos(n.Pos()).RelLine())
277 startLine := int(base.Ctxt.InnermostPos(fn.Pos()).RelLine())
278 return line - startLine
281 // addIREdge adds an edge between caller and new node that points to `callee`
282 // based on the profile-graph and NodeMap.
283 func (p *Profile) addIREdge(caller *IRNode, callername string, call ir.Node, callee *ir.Func) {
286 // Create an IRNode for the callee.
287 calleenode := new(IRNode)
288 calleenode.AST = callee
289 calleename := ir.PkgFuncName(callee)
291 // Create key for NodeMapKey.
292 nodeinfo := NodeMapKey{
293 CallerName: callername,
294 CalleeName: calleename,
295 CallSiteOffset: NodeLineOffset(call, caller.AST),
298 // Create the callee node with node weight.
299 if g.IRNodes[calleename] == nil {
300 g.IRNodes[calleename] = calleenode
301 nodeinfo2 := NodeMapKey{
302 CallerName: calleename,
306 if weights, ok := p.NodeMap[nodeinfo2]; ok {
307 g.IRNodes[calleename].Flat = weights.NFlat
308 g.IRNodes[calleename].Cum = weights.NCum
312 if weights, ok := p.NodeMap[nodeinfo]; ok {
313 caller.Flat = weights.NFlat
314 caller.Cum = weights.NCum
316 // Add edge in the IRGraph from caller to callee.
317 info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: weights.EWeight, CallSiteOffset: nodeinfo.CallSiteOffset}
318 g.OutEdges[caller] = append(g.OutEdges[caller], info)
319 g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
321 nodeinfo.CalleeName = ""
322 nodeinfo.CallSiteOffset = 0
323 if weights, ok := p.NodeMap[nodeinfo]; ok {
324 caller.Flat = weights.NFlat
325 caller.Cum = weights.NCum
326 info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: 0, CallSiteOffset: nodeinfo.CallSiteOffset}
327 g.OutEdges[caller] = append(g.OutEdges[caller], info)
328 g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
330 info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: 0, CallSiteOffset: nodeinfo.CallSiteOffset}
331 g.OutEdges[caller] = append(g.OutEdges[caller], info)
332 g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
337 // createIRGraphEdge traverses the nodes in the body of ir.Func and add edges between callernode which points to the ir.Func and the nodes in the body.
338 func (p *Profile) createIRGraphEdge(fn *ir.Func, callernode *IRNode, name string) {
339 var doNode func(ir.Node) bool
340 doNode = func(n ir.Node) bool {
343 ir.DoChildren(n, doNode)
345 call := n.(*ir.CallExpr)
346 // Find the callee function from the call site and add the edge.
347 callee := inlCallee(call.X)
349 p.addIREdge(callernode, name, n, callee)
352 call := n.(*ir.CallExpr)
353 // Find the callee method from the call site and add the edge.
354 callee := ir.MethodExprName(call.X).Func
355 p.addIREdge(callernode, name, n, callee)
362 // WeightInPercentage converts profile weights to a percentage.
363 func WeightInPercentage(value int64, total int64) float64 {
364 return (float64(value) / float64(total)) * 100
367 // PrintWeightedCallGraphDOT prints IRGraph in DOT format.
368 func (p *Profile) PrintWeightedCallGraphDOT(edgeThreshold float64) {
369 fmt.Printf("\ndigraph G {\n")
370 fmt.Printf("forcelabels=true;\n")
372 // List of functions in this package.
373 funcs := make(map[string]struct{})
374 ir.VisitFuncsBottomUp(typecheck.Target.Decls, func(list []*ir.Func, recursive bool) {
375 for _, f := range list {
376 name := ir.PkgFuncName(f)
377 funcs[name] = struct{}{}
381 // Determine nodes of DOT.
382 nodes := make(map[string]*ir.Func)
383 for name := range funcs {
384 if n, ok := p.WeightedCG.IRNodes[name]; ok {
385 for _, e := range p.WeightedCG.OutEdges[n] {
386 if _, ok := nodes[ir.PkgFuncName(e.Src.AST)]; !ok {
387 nodes[ir.PkgFuncName(e.Src.AST)] = e.Src.AST
389 if _, ok := nodes[ir.PkgFuncName(e.Dst.AST)]; !ok {
390 nodes[ir.PkgFuncName(e.Dst.AST)] = e.Dst.AST
393 if _, ok := nodes[ir.PkgFuncName(n.AST)]; !ok {
394 nodes[ir.PkgFuncName(n.AST)] = n.AST
400 for name, ast := range nodes {
401 if n, ok := p.WeightedCG.IRNodes[name]; ok {
402 nodeweight := WeightInPercentage(n.Flat, p.TotalNodeWeight)
405 fmt.Printf("\"%v\" [color=%v,label=\"%v,freq=%.2f,inl_cost=%d\"];\n", ir.PkgFuncName(ast), color, ir.PkgFuncName(ast), nodeweight, ast.Inl.Cost)
407 fmt.Printf("\"%v\" [color=%v, label=\"%v,freq=%.2f\"];\n", ir.PkgFuncName(ast), color, ir.PkgFuncName(ast), nodeweight)
412 ir.VisitFuncsBottomUp(typecheck.Target.Decls, func(list []*ir.Func, recursive bool) {
413 for _, f := range list {
414 name := ir.PkgFuncName(f)
415 if n, ok := p.WeightedCG.IRNodes[name]; ok {
416 for _, e := range p.WeightedCG.OutEdges[n] {
417 edgepercent := WeightInPercentage(e.Weight, p.TotalEdgeWeight)
418 if edgepercent > edgeThreshold {
419 fmt.Printf("edge [color=red, style=solid];\n")
421 fmt.Printf("edge [color=black, style=solid];\n")
424 fmt.Printf("\"%v\" -> \"%v\" [label=\"%.2f\"];\n", ir.PkgFuncName(n.AST), ir.PkgFuncName(e.Dst.AST), edgepercent)
432 // RedirectEdges deletes and redirects out-edges from node cur based on
433 // inlining information via inlinedCallSites.
435 // CallSiteInfo.Callee must be nil.
436 func (p *Profile) RedirectEdges(cur *IRNode, inlinedCallSites map[CallSiteInfo]struct{}) {
439 for i, outEdge := range g.OutEdges[cur] {
440 if _, found := inlinedCallSites[CallSiteInfo{LineOffset: outEdge.CallSiteOffset, Caller: cur.AST}]; !found {
441 for _, InEdge := range g.InEdges[cur] {
442 if _, ok := inlinedCallSites[CallSiteInfo{LineOffset: InEdge.CallSiteOffset, Caller: InEdge.Src.AST}]; ok {
443 weight := g.calculateWeight(InEdge.Src, cur)
444 g.redirectEdge(InEdge.Src, cur, outEdge, weight, i)
453 // redirectEdges deletes the cur node out-edges and redirect them so now these
454 // edges are the parent node out-edges.
455 func (g *IRGraph) redirectEdges(parent *IRNode, cur *IRNode) {
456 for _, outEdge := range g.OutEdges[cur] {
458 g.OutEdges[parent] = append(g.OutEdges[parent], outEdge)
460 delete(g.OutEdges, cur)
463 // redirectEdge deletes the cur-node's out-edges and redirect them so now these
464 // edges are the parent node out-edges.
465 func (g *IRGraph) redirectEdge(parent *IRNode, cur *IRNode, outEdge *IREdge, weight int64, idx int) {
467 outEdge.Weight = weight * outEdge.Weight
468 g.OutEdges[parent] = append(g.OutEdges[parent], outEdge)
472 // remove deletes the cur-node's out-edges at index idx.
473 func (g *IRGraph) remove(cur *IRNode, i int) {
474 if len(g.OutEdges[cur]) >= 2 {
475 g.OutEdges[cur][i] = g.OutEdges[cur][len(g.OutEdges[cur])-1]
476 g.OutEdges[cur] = g.OutEdges[cur][:len(g.OutEdges[cur])-1]
478 delete(g.OutEdges, cur)
482 // calculateWeight calculates the weight of the new redirected edge.
483 func (g *IRGraph) calculateWeight(parent *IRNode, cur *IRNode) int64 {
486 for _, InEdge := range g.InEdges[cur] {
488 if InEdge.Src == parent {
501 // inlCallee is same as the implementation for inl.go with one change. The change is that we do not invoke CanInline on a closure.
502 func inlCallee(fn ir.Node) *ir.Func {
503 fn = ir.StaticValue(fn)
506 fn := fn.(*ir.SelectorExpr)
507 n := ir.MethodExprName(fn)
508 // Check that receiver type matches fn.X.
509 // TODO(mdempsky): Handle implicit dereference
510 // of pointer receiver argument?
511 if n == nil || !types.Identical(n.Type().Recv().Type, fn.X.Type()) {
517 if fn.Class == ir.PFUNC {
521 fn := fn.(*ir.ClosureExpr)