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 5 package obj 6 7 import "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). 44 type InlTree struct { 45 nodes []InlinedCall 46 } 47 48 // InlinedCall is a node in an InlTree. 49 type 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. 58 func (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. 76 func (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 84 func (tree *InlTree) Parent(inlIndex int) int { 85 return tree.nodes[inlIndex].Parent 86 } 87 88 func (tree *InlTree) InlinedFunction(inlIndex int) *LSym { 89 return tree.nodes[inlIndex].Func 90 } 91 92 func (tree *InlTree) CallPos(inlIndex int) src.XPos { 93 return tree.nodes[inlIndex].Pos 94 } 95 96 func (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. 104 func (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. 123 func (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. 130 func (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 138 func 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