1// Copyright 2017 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.
4
5package obj
6
7import "cmd/internal/src"
8
9// InlTree is a collection of inlined calls. The Parent field of an
10// InlinedCall is the index of another InlinedCall in InlTree.
11//
12// The compiler maintains a global inlining tree and adds a node to it
13// every time a function is inlined. For example, suppose f() calls g()
14// and g has two calls to h(), and that f, g, and h are inlineable:
15//
16//	 1 func main() {
17//	 2     f()
18//	 3 }
19//	 4 func f() {
20//	 5     g()
21//	 6 }
22//	 7 func g() {
23//	 8     h()
24//	 9     h()
25//	10 }
26//	11 func h() {
27//	12     println("H")
28//	13 }
29//
30// Assuming the global tree starts empty, inlining will produce the
31// following tree:
32//
33//	[]InlinedCall{
34//	  {Parent: -1, Func: "f", Pos: <line 2>},
35//	  {Parent:  0, Func: "g", Pos: <line 5>},
36//	  {Parent:  1, Func: "h", Pos: <line 8>},
37//	  {Parent:  1, Func: "h", Pos: <line 9>},
38//	}
39//
40// The nodes of h inlined into main will have inlining indexes 2 and 3.
41//
42// Eventually, the compiler extracts a per-function inlining tree from
43// the global inlining tree (see pcln.go).
44type InlTree struct {
45	nodes []InlinedCall
46}
47
48// InlinedCall is a node in an InlTree.
49type InlinedCall struct {
50	Parent   int      // index of the parent in the InlTree or < 0 if outermost call
51	Pos      src.XPos // position of the inlined call
52	Func     *LSym    // function that was inlined
53	Name     string   // bare name of the function (w/o package prefix)
54	ParentPC int32    // PC of instruction just before inlined body. Only valid in local trees.
55}
56
57// Add adds a new call to the tree, returning its index.
58func (tree *InlTree) Add(parent int, pos src.XPos, func_ *LSym, name string) int {
59	r := len(tree.nodes)
60	call := InlinedCall{
61		Parent: parent,
62		Pos:    pos,
63		Func:   func_,
64		Name:   name,
65	}
66	tree.nodes = append(tree.nodes, call)
67	return r
68}
69
70// AllParents invokes do on each InlinedCall in the inlining call
71// stack, from outermost to innermost.
72//
73// That is, if inlIndex corresponds to f inlining g inlining h,
74// AllParents invokes do with the call for inlining g into f, and then
75// inlining h into g.
76func (tree *InlTree) AllParents(inlIndex int, do func(InlinedCall)) {
77	if inlIndex >= 0 {
78		call := tree.nodes[inlIndex]
79		tree.AllParents(call.Parent, do)
80		do(call)
81	}
82}
83
84func (tree *InlTree) Parent(inlIndex int) int {
85	return tree.nodes[inlIndex].Parent
86}
87
88func (tree *InlTree) InlinedFunction(inlIndex int) *LSym {
89	return tree.nodes[inlIndex].Func
90}
91
92func (tree *InlTree) CallPos(inlIndex int) src.XPos {
93	return tree.nodes[inlIndex].Pos
94}
95
96func (tree *InlTree) setParentPC(inlIndex int, pc int32) {
97	tree.nodes[inlIndex].ParentPC = pc
98}
99
100// OutermostPos returns the outermost position corresponding to xpos,
101// which is where xpos was ultimately inlined to. In the example for
102// InlTree, main() contains inlined AST nodes from h(), but the
103// outermost position for those nodes is line 2.
104func (ctxt *Link) OutermostPos(xpos src.XPos) src.Pos {
105	pos := ctxt.InnermostPos(xpos)
106
107	outerxpos := xpos
108	for ix := pos.Base().InliningIndex(); ix >= 0; {
109		call := ctxt.InlTree.nodes[ix]
110		ix = call.Parent
111		outerxpos = call.Pos
112	}
113	return ctxt.PosTable.Pos(outerxpos)
114}
115
116// InnermostPos returns the innermost position corresponding to xpos,
117// that is, the code that is inlined and that inlines nothing else.
118// In the example for InlTree above, the code for println within h
119// would have an innermost position with line number 12, whether
120// h was not inlined, inlined into g, g-then-f, or g-then-f-then-main.
121// This corresponds to what someone debugging main, f, g, or h might
122// expect to see while single-stepping.
123func (ctxt *Link) InnermostPos(xpos src.XPos) src.Pos {
124	return ctxt.PosTable.Pos(xpos)
125}
126
127// AllPos invokes do with every position in the inlining call stack for xpos,
128// from outermost to innermost. That is, xpos corresponds to f inlining g inlining h,
129// AllPos invokes do with the position in f, then the position in g, then the position in h.
130func (ctxt *Link) AllPos(xpos src.XPos, do func(src.Pos)) {
131	pos := ctxt.InnermostPos(xpos)
132	ctxt.InlTree.AllParents(pos.Base().InliningIndex(), func(call InlinedCall) {
133		do(ctxt.InnermostPos(call.Pos))
134	})
135	do(pos)
136}
137
138func dumpInlTree(ctxt *Link, tree InlTree) {
139	for i, call := range tree.nodes {
140		pos := ctxt.PosTable.Pos(call.Pos)
141		ctxt.Logf("%0d | %0d | %s (%s) pc=%d\n", i, call.Parent, call.Func, pos, call.ParentPC)
142	}
143}
144