inl.go

     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
View as plain text