src/cmd/compile/internal/pgo/irgraph.go - go - Git at Google

 // 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.

 // WORK IN PROGRESS

 // 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/typecheck"
 	"cmd/compile/internal/types"
 	"fmt"
 	"internal/profile"
 	"log"
 	"os"
 )

 // IRGraph is the key datastrcture that is built from profile. It is
 // essentially a call graph with nodes pointing to IRs of functions and edges
 // carrying weights and callsite information. The graph is bidirectional that
 // helps in removing nodes efficiently.
 type IRGraph struct {
 	// Nodes of the graph
 	IRNodes  map[string]*IRNode
 	OutEdges IREdgeMap
 	InEdges  IREdgeMap
 }

 // IRNode represents a node in the IRGraph.
 type IRNode struct {
 	// Pointer to the IR of the Function represented by this node.
 	AST *ir.Func
 	// Flat weight of the IRNode, obtained from profile.
 	Flat int64
 	// Cumulative weight of the IRNode.
 	Cum int64
 }

 // IREdgeMap maps an IRNode to its successors.
 type IREdgeMap map[*IRNode][]*IREdge

 // 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.
 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 {
 	f, err := os.Open(profileFile)
 	if err != nil {
 		log.Fatal("failed to open file " + profileFile)
 		return nil
 	}
 	defer f.Close()
 	profile, err := profile.Parse(f)
 	if err != nil {
 		log.Fatal("failed to Parse profile file.")
 		return nil
 	}

 	g := newGraph(profile, &Options{
 		CallTree:    false,
 		SampleValue: func(v []int64) int64 { return v[1] },
 	})

 	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 !p.processprofileGraph(g) {
 		return nil
 	}

 	// Create package-level call graph with weights from profile and IR.
 	p.initializeIRGraph()

 	return p
 }

 // 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.
 // Returns whether it successfully processed the profile.
 func (p *Profile) processprofileGraph(g *Graph) bool {
 	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 false // accept but ignore profile with no sample
 	}

 	if !seenStartLine {
 		// TODO(prattic): If Function.start_line is missing we could
 		// fall back to using absolute line numbers, which is better
 		// than nothing.
 		log.Fatal("PGO profile missing Function.start_line data")
 	}

 	return true
 }

 // initializeIRGraph builds the IRGraph by visting 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 _, n := range list {
 			p.VisitIR(n, recursive)
 		}
 	})
 }

 // 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, recursive bool) {
 	g := p.WeightedCG

 	if g.IRNodes == nil {
 		g.IRNodes = make(map[string]*IRNode)
 	}
 	if g.OutEdges == nil {
 		g.OutEdges = make(map[*IRNode][]*IREdge)
 	}
 	if g.InEdges == nil {
 		g.InEdges = make(map[*IRNode][]*IREdge)
 	}
 	name := ir.PkgFuncName(fn)
 	node := new(IRNode)
 	node.AST = fn
 	if g.IRNodes[name] == nil {
 		g.IRNodes[name] = node
 	}
 	// Create the key for the NodeMapKey.
 	nodeinfo := NodeMapKey{
 		CallerName:     name,
 		CalleeName:     "",
 		CallSiteOffset: 0,
 	}
 	// If the node exists, then update its node weight.
 	if weights, ok := p.NodeMap[nodeinfo]; ok {
 		g.IRNodes[name].Flat = weights.NFlat
 		g.IRNodes[name].Cum = weights.NCum
 	}

 	// Recursively walk over the body of the function to create IRGraph edges.
 	p.createIRGraphEdge(fn, g.IRNodes[name], 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(caller *IRNode, callername string, call ir.Node, callee *ir.Func) {
 	g := p.WeightedCG

 	// Create an IRNode for the callee.
 	calleenode := new(IRNode)
 	calleenode.AST = callee
 	calleename := ir.PkgFuncName(callee)

 	// Create key for NodeMapKey.
 	nodeinfo := NodeMapKey{
 		CallerName:     callername,
 		CalleeName:     calleename,
 		CallSiteOffset: NodeLineOffset(call, caller.AST),
 	}

 	// Create the callee node with node weight.
 	if g.IRNodes[calleename] == nil {
 		g.IRNodes[calleename] = calleenode
 		nodeinfo2 := NodeMapKey{
 			CallerName:     calleename,
 			CalleeName:     "",
 			CallSiteOffset: 0,
 		}
 		if weights, ok := p.NodeMap[nodeinfo2]; ok {
 			g.IRNodes[calleename].Flat = weights.NFlat
 			g.IRNodes[calleename].Cum = weights.NCum
 		}
 	}

 	if weights, ok := p.NodeMap[nodeinfo]; ok {
 		caller.Flat = weights.NFlat
 		caller.Cum = weights.NCum

 		// Add edge in the IRGraph from caller to callee.
 		info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: weights.EWeight, CallSiteOffset: nodeinfo.CallSiteOffset}
 		g.OutEdges[caller] = append(g.OutEdges[caller], info)
 		g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
 	} else {
 		nodeinfo.CalleeName = ""
 		nodeinfo.CallSiteOffset = 0
 		if weights, ok := p.NodeMap[nodeinfo]; ok {
 			caller.Flat = weights.NFlat
 			caller.Cum = weights.NCum
 			info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: 0, CallSiteOffset: nodeinfo.CallSiteOffset}
 			g.OutEdges[caller] = append(g.OutEdges[caller], info)
 			g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
 		} else {
 			info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: 0, CallSiteOffset: nodeinfo.CallSiteOffset}
 			g.OutEdges[caller] = append(g.OutEdges[caller], info)
 			g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
 		}
 	}
 }

 // 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.
 func (p *Profile) createIRGraphEdge(fn *ir.Func, callernode *IRNode, name string) {
 	var doNode func(ir.Node) bool
 	doNode = func(n ir.Node) bool {
 		switch n.Op() {
 		default:
 			ir.DoChildren(n, doNode)
 		case ir.OCALLFUNC:
 			call := n.(*ir.CallExpr)
 			// Find the callee function from the call site and add the edge.
 			callee := inlCallee(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)
 		}
 		return false
 	}
 	doNode(fn)
 }

 // 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.PkgFuncName(f)
 			funcs[name] = struct{}{}
 		}
 	})

 	// Determine nodes of DOT.
 	nodes := make(map[string]*ir.Func)
 	for name, _ := range funcs {
 		if n, ok := p.WeightedCG.IRNodes[name]; ok {
 			for _, e := range p.WeightedCG.OutEdges[n] {
 				if _, ok := nodes[ir.PkgFuncName(e.Src.AST)]; !ok {
 					nodes[ir.PkgFuncName(e.Src.AST)] = e.Src.AST
 				}
 				if _, ok := nodes[ir.PkgFuncName(e.Dst.AST)]; !ok {
 					nodes[ir.PkgFuncName(e.Dst.AST)] = e.Dst.AST
 				}
 			}
 			if _, ok := nodes[ir.PkgFuncName(n.AST)]; !ok {
 				nodes[ir.PkgFuncName(n.AST)] = n.AST
 			}
 		}
 	}

 	// Print nodes.
 	for name, ast := range nodes {
 		if n, ok := p.WeightedCG.IRNodes[name]; ok {
 			nodeweight := WeightInPercentage(n.Flat, p.TotalNodeWeight)
 			color := "black"
 			if ast.Inl != nil {
 				fmt.Printf("\"%v\" [color=%v,label=\"%v,freq=%.2f,inl_cost=%d\"];\n", ir.PkgFuncName(ast), color, ir.PkgFuncName(ast), nodeweight, ast.Inl.Cost)
 			} else {
 				fmt.Printf("\"%v\" [color=%v, label=\"%v,freq=%.2f\"];\n", ir.PkgFuncName(ast), color, ir.PkgFuncName(ast), nodeweight)
 			}
 		}
 	}
 	// Print edges.
 	ir.VisitFuncsBottomUp(typecheck.Target.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] {
 					edgepercent := WeightInPercentage(e.Weight, p.TotalEdgeWeight)
 					if edgepercent > edgeThreshold {
 						fmt.Printf("edge [color=red, style=solid];\n")
 					} else {
 						fmt.Printf("edge [color=black, style=solid];\n")
 					}

 					fmt.Printf("\"%v\" -> \"%v\" [label=\"%.2f\"];\n", ir.PkgFuncName(n.AST), ir.PkgFuncName(e.Dst.AST), edgepercent)
 				}
 			}
 		}
 	})
 	fmt.Printf("}\n")
 }

 // RedirectEdges deletes and redirects out-edges from node cur based on
 // inlining information via inlinedCallSites.
 //
 // CallSiteInfo.Callee must be nil.
 func (p *Profile) RedirectEdges(cur *IRNode, inlinedCallSites map[CallSiteInfo]struct{}) {
 	g := p.WeightedCG

 	for i, outEdge := range g.OutEdges[cur] {
 		if _, found := inlinedCallSites[CallSiteInfo{LineOffset: outEdge.CallSiteOffset, Caller: cur.AST}]; !found {
 			for _, InEdge := range g.InEdges[cur] {
 				if _, ok := inlinedCallSites[CallSiteInfo{LineOffset: InEdge.CallSiteOffset, Caller: InEdge.Src.AST}]; ok {
 					weight := g.calculateWeight(InEdge.Src, cur)
 					g.redirectEdge(InEdge.Src, cur, outEdge, weight, i)
 				}
 			}
 		} else {
 			g.remove(cur, i)
 		}
 	}
 }

 // redirectEdges deletes the cur node out-edges and redirect them so now these
 // edges are the parent node out-edges.
 func (g *IRGraph) redirectEdges(parent *IRNode, cur *IRNode) {
 	for _, outEdge := range g.OutEdges[cur] {
 		outEdge.Src = parent
 		g.OutEdges[parent] = append(g.OutEdges[parent], outEdge)
 	}
 	delete(g.OutEdges, cur)
 }

 // redirectEdge deletes the cur-node's out-edges and redirect them so now these
 // edges are the parent node out-edges.
 func (g *IRGraph) redirectEdge(parent *IRNode, cur *IRNode, outEdge *IREdge, weight int64, idx int) {
 	outEdge.Src = parent
 	outEdge.Weight = weight * outEdge.Weight
 	g.OutEdges[parent] = append(g.OutEdges[parent], outEdge)
 	g.remove(cur, idx)
 }

 // remove deletes the cur-node's out-edges at index idx.
 func (g *IRGraph) remove(cur *IRNode, i int) {
 	if len(g.OutEdges[cur]) >= 2 {
 		g.OutEdges[cur][i] = g.OutEdges[cur][len(g.OutEdges[cur])-1]
 		g.OutEdges[cur] = g.OutEdges[cur][:len(g.OutEdges[cur])-1]
 	} else {
 		delete(g.OutEdges, cur)
 	}
 }

 // calculateWeight calculates the weight of the new redirected edge.
 func (g *IRGraph) calculateWeight(parent *IRNode, cur *IRNode) int64 {
 	sum := int64(0)
 	pw := int64(0)
 	for _, InEdge := range g.InEdges[cur] {
 		sum = sum + InEdge.Weight
 		if InEdge.Src == parent {
 			pw = InEdge.Weight
 		}
 	}
 	weight := int64(0)
 	if sum != 0 {
 		weight = pw / sum
 	} else {
 		weight = pw
 	}
 	return weight
 }

 // inlCallee is same as the implementation for inl.go with one change. The change is that we do not invoke CanInline on a closure.
 func inlCallee(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
 }
	// 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.

	// WORK IN PROGRESS

	// 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/typecheck"
	"cmd/compile/internal/types"
	"fmt"
	"internal/profile"
	"log"
	"os"
	)

	// IRGraph is the key datastrcture that is built from profile. It is
	// essentially a call graph with nodes pointing to IRs of functions and edges
	// carrying weights and callsite information. The graph is bidirectional that
	// helps in removing nodes efficiently.
	type IRGraph struct {
	// Nodes of the graph
	IRNodes map[string]*IRNode
	OutEdges IREdgeMap
	InEdges IREdgeMap
	}

	// IRNode represents a node in the IRGraph.
	type IRNode struct {
	// Pointer to the IR of the Function represented by this node.
	AST *ir.Func
	// Flat weight of the IRNode, obtained from profile.
	Flat int64
	// Cumulative weight of the IRNode.
	Cum int64
	}

	// IREdgeMap maps an IRNode to its successors.
	type IREdgeMap map[IRNode][]IREdge

	// 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.
	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 {
	f, err := os.Open(profileFile)
	if err != nil {
	log.Fatal("failed to open file " + profileFile)
	return nil
	}
	defer f.Close()
	profile, err := profile.Parse(f)
	if err != nil {
	log.Fatal("failed to Parse profile file.")
	return nil
	}

	g := newGraph(profile, &Options{
	CallTree: false,
	SampleValue: func(v []int64) int64 { return v[1] },
	})

	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 !p.processprofileGraph(g) {
	return nil
	}

	// Create package-level call graph with weights from profile and IR.
	p.initializeIRGraph()

	return p
	}

	// 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.
	// Returns whether it successfully processed the profile.
	func (p Profile) processprofileGraph(g Graph) bool {
	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 false // accept but ignore profile with no sample
	}

	if !seenStartLine {
	// TODO(prattic): If Function.start_line is missing we could
	// fall back to using absolute line numbers, which is better
	// than nothing.
	log.Fatal("PGO profile missing Function.start_line data")
	}

	return true
	}

	// initializeIRGraph builds the IRGraph by visting 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 _, n := range list {
	p.VisitIR(n, recursive)
	}
	})
	}

	// 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, recursive bool) {
	g := p.WeightedCG

	if g.IRNodes == nil {
	g.IRNodes = make(map[string]*IRNode)
	}
	if g.OutEdges == nil {
	g.OutEdges = make(map[IRNode][]IREdge)
	}
	if g.InEdges == nil {
	g.InEdges = make(map[IRNode][]IREdge)
	}
	name := ir.PkgFuncName(fn)
	node := new(IRNode)
	node.AST = fn
	if g.IRNodes[name] == nil {
	g.IRNodes[name] = node
	}
	// Create the key for the NodeMapKey.
	nodeinfo := NodeMapKey{
	CallerName: name,
	CalleeName: "",
	CallSiteOffset: 0,
	}
	// If the node exists, then update its node weight.
	if weights, ok := p.NodeMap[nodeinfo]; ok {
	g.IRNodes[name].Flat = weights.NFlat
	g.IRNodes[name].Cum = weights.NCum
	}

	// Recursively walk over the body of the function to create IRGraph edges.
	p.createIRGraphEdge(fn, g.IRNodes[name], 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(caller IRNode, callername string, call ir.Node, callee *ir.Func) {
	g := p.WeightedCG

	// Create an IRNode for the callee.
	calleenode := new(IRNode)
	calleenode.AST = callee
	calleename := ir.PkgFuncName(callee)

	// Create key for NodeMapKey.
	nodeinfo := NodeMapKey{
	CallerName: callername,
	CalleeName: calleename,
	CallSiteOffset: NodeLineOffset(call, caller.AST),
	}

	// Create the callee node with node weight.
	if g.IRNodes[calleename] == nil {
	g.IRNodes[calleename] = calleenode
	nodeinfo2 := NodeMapKey{
	CallerName: calleename,
	CalleeName: "",
	CallSiteOffset: 0,
	}
	if weights, ok := p.NodeMap[nodeinfo2]; ok {
	g.IRNodes[calleename].Flat = weights.NFlat
	g.IRNodes[calleename].Cum = weights.NCum
	}
	}

	if weights, ok := p.NodeMap[nodeinfo]; ok {
	caller.Flat = weights.NFlat
	caller.Cum = weights.NCum

	// Add edge in the IRGraph from caller to callee.
	info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: weights.EWeight, CallSiteOffset: nodeinfo.CallSiteOffset}
	g.OutEdges[caller] = append(g.OutEdges[caller], info)
	g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
	} else {
	nodeinfo.CalleeName = ""
	nodeinfo.CallSiteOffset = 0
	if weights, ok := p.NodeMap[nodeinfo]; ok {
	caller.Flat = weights.NFlat
	caller.Cum = weights.NCum
	info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: 0, CallSiteOffset: nodeinfo.CallSiteOffset}
	g.OutEdges[caller] = append(g.OutEdges[caller], info)
	g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
	} else {
	info := &IREdge{Src: caller, Dst: g.IRNodes[calleename], Weight: 0, CallSiteOffset: nodeinfo.CallSiteOffset}
	g.OutEdges[caller] = append(g.OutEdges[caller], info)
	g.InEdges[g.IRNodes[calleename]] = append(g.InEdges[g.IRNodes[calleename]], info)
	}
	}
	}

	// 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.
	func (p Profile) createIRGraphEdge(fn ir.Func, callernode *IRNode, name string) {
	var doNode func(ir.Node) bool
	doNode = func(n ir.Node) bool {
	switch n.Op() {
	default:
	ir.DoChildren(n, doNode)
	case ir.OCALLFUNC:
	call := n.(*ir.CallExpr)
	// Find the callee function from the call site and add the edge.
	callee := inlCallee(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)
	}
	return false
	}
	doNode(fn)
	}

	// 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.PkgFuncName(f)
	funcs[name] = struct{}{}
	}
	})

	// Determine nodes of DOT.
	nodes := make(map[string]*ir.Func)
	for name, _ := range funcs {
	if n, ok := p.WeightedCG.IRNodes[name]; ok {
	for _, e := range p.WeightedCG.OutEdges[n] {
	if _, ok := nodes[ir.PkgFuncName(e.Src.AST)]; !ok {
	nodes[ir.PkgFuncName(e.Src.AST)] = e.Src.AST
	}
	if _, ok := nodes[ir.PkgFuncName(e.Dst.AST)]; !ok {
	nodes[ir.PkgFuncName(e.Dst.AST)] = e.Dst.AST
	}
	}
	if _, ok := nodes[ir.PkgFuncName(n.AST)]; !ok {
	nodes[ir.PkgFuncName(n.AST)] = n.AST
	}
	}
	}

	// Print nodes.
	for name, ast := range nodes {
	if n, ok := p.WeightedCG.IRNodes[name]; ok {
	nodeweight := WeightInPercentage(n.Flat, p.TotalNodeWeight)
	color := "black"
	if ast.Inl != nil {
	fmt.Printf("\"%v\" [color=%v,label=\"%v,freq=%.2f,inl_cost=%d\"];\n", ir.PkgFuncName(ast), color, ir.PkgFuncName(ast), nodeweight, ast.Inl.Cost)
	} else {
	fmt.Printf("\"%v\" [color=%v, label=\"%v,freq=%.2f\"];\n", ir.PkgFuncName(ast), color, ir.PkgFuncName(ast), nodeweight)
	}
	}
	}
	// Print edges.
	ir.VisitFuncsBottomUp(typecheck.Target.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] {
	edgepercent := WeightInPercentage(e.Weight, p.TotalEdgeWeight)
	if edgepercent > edgeThreshold {
	fmt.Printf("edge [color=red, style=solid];\n")
	} else {
	fmt.Printf("edge [color=black, style=solid];\n")
	}

	fmt.Printf("\"%v\" -> \"%v\" [label=\"%.2f\"];\n", ir.PkgFuncName(n.AST), ir.PkgFuncName(e.Dst.AST), edgepercent)
	}
	}
	}
	})
	fmt.Printf("}\n")
	}

	// RedirectEdges deletes and redirects out-edges from node cur based on
	// inlining information via inlinedCallSites.
	//
	// CallSiteInfo.Callee must be nil.
	func (p Profile) RedirectEdges(cur IRNode, inlinedCallSites map[CallSiteInfo]struct{}) {
	g := p.WeightedCG

	for i, outEdge := range g.OutEdges[cur] {
	if _, found := inlinedCallSites[CallSiteInfo{LineOffset: outEdge.CallSiteOffset, Caller: cur.AST}]; !found {
	for _, InEdge := range g.InEdges[cur] {
	if _, ok := inlinedCallSites[CallSiteInfo{LineOffset: InEdge.CallSiteOffset, Caller: InEdge.Src.AST}]; ok {
	weight := g.calculateWeight(InEdge.Src, cur)
	g.redirectEdge(InEdge.Src, cur, outEdge, weight, i)
	}
	}
	} else {
	g.remove(cur, i)
	}
	}
	}

	// redirectEdges deletes the cur node out-edges and redirect them so now these
	// edges are the parent node out-edges.
	func (g IRGraph) redirectEdges(parent IRNode, cur *IRNode) {
	for _, outEdge := range g.OutEdges[cur] {
	outEdge.Src = parent
	g.OutEdges[parent] = append(g.OutEdges[parent], outEdge)
	}
	delete(g.OutEdges, cur)
	}

	// redirectEdge deletes the cur-node's out-edges and redirect them so now these
	// edges are the parent node out-edges.
	func (g IRGraph) redirectEdge(parent IRNode, cur IRNode, outEdge IREdge, weight int64, idx int) {
	outEdge.Src = parent
	outEdge.Weight = weight * outEdge.Weight
	g.OutEdges[parent] = append(g.OutEdges[parent], outEdge)
	g.remove(cur, idx)
	}

	// remove deletes the cur-node's out-edges at index idx.
	func (g IRGraph) remove(cur IRNode, i int) {
	if len(g.OutEdges[cur]) >= 2 {
	g.OutEdges[cur][i] = g.OutEdges[cur][len(g.OutEdges[cur])-1]
	g.OutEdges[cur] = g.OutEdges[cur][:len(g.OutEdges[cur])-1]
	} else {
	delete(g.OutEdges, cur)
	}
	}

	// calculateWeight calculates the weight of the new redirected edge.
	func (g IRGraph) calculateWeight(parent IRNode, cur *IRNode) int64 {
	sum := int64(0)
	pw := int64(0)
	for _, InEdge := range g.InEdges[cur] {
	sum = sum + InEdge.Weight
	if InEdge.Src == parent {
	pw = InEdge.Weight
	}
	}
	weight := int64(0)
	if sum != 0 {
	weight = pw / sum
	} else {
	weight = pw
	}
	return weight
	}

	// inlCallee is same as the implementation for inl.go with one change. The change is that we do not invoke CanInline on a closure.
	func inlCallee(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
	}