From 3f1bcc58b32dbbf7f27fbe0984b95036ddb249b9 Mon Sep 17 00:00:00 2001 From: Cherry Mui Date: Tue, 15 Nov 2022 13:32:32 -0500 Subject: [PATCH] cmd/compile: simplify PGO hot caller/callee computation Currently, we use CDF to compute a weight threshold and then use the weight threshold to determine whether a call site is hot. As when we compute the CDF we already have a list of hot call sites that make up the given percentage of the CDF, just use that list. Also, when computing the CDF threshold, include the very last node that makes it to go over the threshold. (I.e. if the CDF threshold is 50% and one hot node takes 60% of weight, we should include that node instead of excluding it. In practice it rarely matters, probably only for testing and micro-benchmarks.) Change-Id: I535ae9cd6b679609e247c3d0d9ee572c1a1187cc Reviewed-on: https://go-review.googlesource.com/c/go/+/450737 Reviewed-by: Austin Clements TryBot-Result: Gopher Robot Run-TryBot: Cherry Mui --- src/cmd/compile/internal/inline/inl.go | 59 ++++++++++++-------------- 1 file changed, 28 insertions(+), 31 deletions(-) diff --git a/src/cmd/compile/internal/inline/inl.go b/src/cmd/compile/internal/inline/inl.go index 028b6c0e83..84e61f34a2 100644 --- a/src/cmd/compile/internal/inline/inl.go +++ b/src/cmd/compile/internal/inline/inl.go @@ -84,11 +84,15 @@ var ( // pgoInlinePrologue records the hot callsites from ir-graph. func pgoInlinePrologue(p *pgo.Profile, decls []ir.Node) { - if s, err := strconv.ParseFloat(base.Debug.PGOInlineCDFThreshold, 64); err == nil { - inlineCDFHotCallSiteThresholdPercent = s + if base.Debug.PGOInlineCDFThreshold != "" { + if s, err := strconv.ParseFloat(base.Debug.PGOInlineCDFThreshold, 64); err == nil && s >= 0 && s <= 100 { + inlineCDFHotCallSiteThresholdPercent = s + } else { + base.Fatalf("invalid PGOInlineCDFThreshold, must be between 0 and 100") + } } var hotCallsites []pgo.NodeMapKey - inlineHotCallSiteThresholdPercent, hotCallsites = computeThresholdFromCDF(p) + inlineHotCallSiteThresholdPercent, hotCallsites = hotNodesFromCDF(p) if base.Debug.PGOInline > 0 { fmt.Printf("hot-callsite-thres-from-CDF=%v\n", inlineHotCallSiteThresholdPercent) } @@ -97,41 +101,31 @@ func pgoInlinePrologue(p *pgo.Profile, decls []ir.Node) { inlineHotMaxBudget = int32(x) } - // mark inlineable callees from hot edges for _, n := range hotCallsites { - if fn := p.WeightedCG.IRNodes[n.CalleeName]; fn != nil { - candHotCalleeMap[fn] = struct{}{} + // mark inlineable callees from hot edges + if callee := p.WeightedCG.IRNodes[n.CalleeName]; callee != nil { + candHotCalleeMap[callee] = struct{}{} } - } - // mark hot call sites - ir.VisitFuncsBottomUp(decls, func(list []*ir.Func, recursive bool) { - for _, f := range list { - name := ir.PkgFuncName(f) - if n, ok := p.WeightedCG.IRNodes[name]; ok { - for _, e := range p.WeightedCG.OutEdges[n] { - if e.Weight != 0 { - edgeweightpercent := pgo.WeightInPercentage(e.Weight, p.TotalEdgeWeight) - if edgeweightpercent > inlineHotCallSiteThresholdPercent { - csi := pgo.CallSiteInfo{LineOffset: e.CallSiteOffset, Caller: n.AST} - if _, ok := candHotEdgeMap[csi]; !ok { - candHotEdgeMap[csi] = struct{}{} - } - } - } - } - } + // mark hot call sites + if caller := p.WeightedCG.IRNodes[n.CallerName]; caller != nil { + csi := pgo.CallSiteInfo{LineOffset: n.CallSiteOffset, Caller: caller.AST} + candHotEdgeMap[csi] = struct{}{} } - }) + } + if base.Debug.PGOInline >= 2 { fmt.Printf("hot-cg before inline in dot format:") p.PrintWeightedCallGraphDOT(inlineHotCallSiteThresholdPercent) } } -// computeThresholdFromCDF computes an edge weight threshold based on the -// CDF of edge weights from the profile. Returns the threshold, and the -// list of edges that make up the given percentage of the CDF. -func computeThresholdFromCDF(p *pgo.Profile) (float64, []pgo.NodeMapKey) { +// hotNodesFromCDF computes an edge weight threshold and the list of hot +// nodes that make up the given percentage of the CDF. The threshold, as +// a percent, is the lower bound of weight for nodes to be considered hot +// (currently only used in debug prints) (in case of equal weights, +// comparing with the threshold may not accurately reflect which nodes are +// considiered hot). +func hotNodesFromCDF(p *pgo.Profile) (float64, []pgo.NodeMapKey) { nodes := make([]pgo.NodeMapKey, len(p.NodeMap)) i := 0 for n := range p.NodeMap { @@ -157,10 +151,13 @@ func computeThresholdFromCDF(p *pgo.Profile) (float64, []pgo.NodeMapKey) { w := p.NodeMap[n].EWeight cum += w if pgo.WeightInPercentage(cum, p.TotalEdgeWeight) > inlineCDFHotCallSiteThresholdPercent { - return pgo.WeightInPercentage(w, p.TotalEdgeWeight), nodes[:i] + // nodes[:i+1] to include the very last node that makes it to go over the threshold. + // (Say, if the CDF threshold is 50% and one hot node takes 60% of weight, we want to + // include that node instead of excluding it.) + return pgo.WeightInPercentage(w, p.TotalEdgeWeight), nodes[:i+1] } } - return 100, nil + return 0, nodes } // pgoInlineEpilogue updates IRGraph after inlining. -- 2.50.0