numberlines.go

     1  // Copyright 2018 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 ssacompile
     6  
     7  import (
     8  	"fmt"
     9  	"sort"
    10  
    11  	"cmd/compile/internal/ssa"
    12  	"cmd/compile/internal/ssa/ssaop"
    13  	"cmd/internal/src"
    14  )
    15  
    16  func isPoorStatementOp(op ssaop.Op) bool {
    17  	switch op {
    18  	// Note that Nilcheck often vanishes, but when it doesn't, you'd love to start the statement there
    19  	// so that a debugger-user sees the stop before the panic, and can examine the value.
    20  	case ssaop.OpAddr, ssaop.OpLocalAddr, ssaop.OpOffPtr, ssaop.OpStructSelect, ssaop.OpPhi, ssaop.OpITab, ssaop.OpIData,
    21  		ssaop.OpIMake, ssaop.OpStringMake, ssaop.OpSliceMake, ssaop.OpStructMake,
    22  		ssaop.OpConstBool, ssaop.OpConst8, ssaop.OpConst16, ssaop.OpConst32, ssaop.OpConst64, ssaop.OpConst32F, ssaop.OpConst64F, ssaop.OpSB, ssaop.OpSP,
    23  		ssaop.OpArgIntReg, ssaop.OpArgFloatReg:
    24  		return true
    25  	}
    26  	return false
    27  }
    28  
    29  // nextGoodStatementIndex returns an index at i or later that is believed
    30  // to be a good place to start the statement for b.  This decision is
    31  // based on v's Op, the possibility of a better later operation, and
    32  // whether the values following i are the same line as v.
    33  // If a better statement index isn't found, then i is returned.
    34  func nextGoodStatementIndex(v *ssa.Value, i int, b *ssa.Block) int {
    35  	// If the value is the last one in the block, too bad, it will have to do
    36  	// (this assumes that the value ordering vaguely corresponds to the source
    37  	// program execution order, which tends to be true directly after ssa is
    38  	// first built).
    39  	if i >= len(b.Values)-1 {
    40  		return i
    41  	}
    42  	// Skip the likely-ephemeral/fragile opcodes expected to vanish in a rewrite.
    43  	if !isPoorStatementOp(v.Op) {
    44  		return i
    45  	}
    46  	// Look ahead to see what the line number is on the next thing that could be a boundary.
    47  	for j := i + 1; j < len(b.Values); j++ {
    48  		u := b.Values[j]
    49  		if u.Pos.IsStmt() == src.PosNotStmt { // ignore non-statements
    50  			continue
    51  		}
    52  		if u.Pos.SameFileAndLine(v.Pos) {
    53  			if isPoorStatementOp(u.Op) {
    54  				continue // Keep looking, this is also not a good statement op
    55  			}
    56  			return j
    57  		}
    58  		return i
    59  	}
    60  	return i
    61  }
    62  
    63  func flc(p src.XPos) string {
    64  	if p == src.NoXPos {
    65  		return "none"
    66  	}
    67  	return fmt.Sprintf("(%d):%d:%d", p.FileIndex(), p.Line(), p.Col())
    68  }
    69  
    70  type fileAndPair struct {
    71  	f  int32
    72  	lp ssa.LineRange
    73  }
    74  
    75  type fileAndPairs []fileAndPair
    76  
    77  func (fap fileAndPairs) Len() int {
    78  	return len(fap)
    79  }
    80  func (fap fileAndPairs) Less(i, j int) bool {
    81  	return fap[i].f < fap[j].f
    82  }
    83  func (fap fileAndPairs) Swap(i, j int) {
    84  	fap[i], fap[j] = fap[j], fap[i]
    85  }
    86  
    87  // -d=ssa/number_lines/stats=1 (that bit) for line and file distribution statistics
    88  // -d=ssa/number_lines/debug for information about why particular values are marked as statements.
    89  func numberLines(f *ssa.Func) {
    90  	po := f.Postorder()
    91  	endlines := make(map[ssa.ID]src.XPos)
    92  	ranges := make(map[int]ssa.LineRange)
    93  	note := func(p src.XPos) {
    94  		line := uint32(p.Line())
    95  		i := int(p.FileIndex())
    96  		lp, found := ranges[i]
    97  		change := false
    98  		if line < lp.First || !found {
    99  			lp.First = line
   100  			change = true
   101  		}
   102  		if line > lp.Last {
   103  			lp.Last = line
   104  			change = true
   105  		}
   106  		if change {
   107  			ranges[i] = lp
   108  		}
   109  	}
   110  
   111  	// Visit in reverse post order so that all non-loop predecessors come first.
   112  	for j := len(po) - 1; j >= 0; j-- {
   113  		b := po[j]
   114  		// Find the first interesting position and check to see if it differs from any predecessor
   115  		firstPos := src.NoXPos
   116  		firstPosIndex := -1
   117  		if b.Pos.IsStmt() != src.PosNotStmt {
   118  			note(b.Pos)
   119  		}
   120  		for i := 0; i < len(b.Values); i++ {
   121  			v := b.Values[i]
   122  			if v.Pos.IsStmt() != src.PosNotStmt {
   123  				note(v.Pos)
   124  				// skip ahead to better instruction for this line if possible
   125  				i = nextGoodStatementIndex(v, i, b)
   126  				v = b.Values[i]
   127  				firstPosIndex = i
   128  				firstPos = v.Pos
   129  				v.Pos = firstPos.WithDefaultStmt() // default to default
   130  				break
   131  			}
   132  		}
   133  
   134  		if firstPosIndex == -1 { // Effectively empty block, check block's own Pos, consider preds.
   135  			line := src.NoXPos
   136  			for _, p := range b.Preds {
   137  				pbi := p.Block().ID
   138  				if !endlines[pbi].SameFileAndLine(line) {
   139  					if line == src.NoXPos {
   140  						line = endlines[pbi]
   141  						continue
   142  					} else {
   143  						line = src.NoXPos
   144  						break
   145  					}
   146  
   147  				}
   148  			}
   149  			// If the block has no statement itself and is effectively empty, tag it w/ predecessor(s) but not as a statement
   150  			if b.Pos.IsStmt() == src.PosNotStmt {
   151  				b.Pos = line
   152  				endlines[b.ID] = line
   153  				continue
   154  			}
   155  			// If the block differs from its predecessors, mark it as a statement
   156  			if line == src.NoXPos || !line.SameFileAndLine(b.Pos) {
   157  				b.Pos = b.Pos.WithIsStmt()
   158  				if f.Pass.Debug > 0 {
   159  					fmt.Printf("Mark stmt effectively-empty-block %s %s %s\n", f.Name, b, flc(b.Pos))
   160  				}
   161  			}
   162  			endlines[b.ID] = b.Pos
   163  			continue
   164  		}
   165  		// check predecessors for any difference; if firstPos differs, then it is a boundary.
   166  		if len(b.Preds) == 0 { // Don't forget the entry block
   167  			b.Values[firstPosIndex].Pos = firstPos.WithIsStmt()
   168  			if f.Pass.Debug > 0 {
   169  				fmt.Printf("Mark stmt entry-block %s %s %s %s\n", f.Name, b, b.Values[firstPosIndex], flc(firstPos))
   170  			}
   171  		} else { // differing pred
   172  			for _, p := range b.Preds {
   173  				pbi := p.Block().ID
   174  				if !endlines[pbi].SameFileAndLine(firstPos) {
   175  					b.Values[firstPosIndex].Pos = firstPos.WithIsStmt()
   176  					if f.Pass.Debug > 0 {
   177  						fmt.Printf("Mark stmt differing-pred %s %s %s %s, different=%s ending %s\n",
   178  							f.Name, b, b.Values[firstPosIndex], flc(firstPos), p.Block(), flc(endlines[pbi]))
   179  					}
   180  					break
   181  				}
   182  			}
   183  		}
   184  		// iterate forward setting each new (interesting) position as a statement boundary.
   185  		for i := firstPosIndex + 1; i < len(b.Values); i++ {
   186  			v := b.Values[i]
   187  			if v.Pos.IsStmt() == src.PosNotStmt {
   188  				continue
   189  			}
   190  			note(v.Pos)
   191  			// skip ahead if possible
   192  			i = nextGoodStatementIndex(v, i, b)
   193  			v = b.Values[i]
   194  			if !v.Pos.SameFileAndLine(firstPos) {
   195  				if f.Pass.Debug > 0 {
   196  					fmt.Printf("Mark stmt new line %s %s %s %s prev pos = %s\n", f.Name, b, v, flc(v.Pos), flc(firstPos))
   197  				}
   198  				firstPos = v.Pos
   199  				v.Pos = v.Pos.WithIsStmt()
   200  			} else {
   201  				v.Pos = v.Pos.WithDefaultStmt()
   202  			}
   203  		}
   204  		if b.Pos.IsStmt() != src.PosNotStmt && !b.Pos.SameFileAndLine(firstPos) {
   205  			if f.Pass.Debug > 0 {
   206  				fmt.Printf("Mark stmt end of block differs %s %s %s prev pos = %s\n", f.Name, b, flc(b.Pos), flc(firstPos))
   207  			}
   208  			b.Pos = b.Pos.WithIsStmt()
   209  			firstPos = b.Pos
   210  		}
   211  		endlines[b.ID] = firstPos
   212  	}
   213  	if f.Pass.Stats&1 != 0 {
   214  		// Report summary statistics on the shape of the sparse map about to be constructed
   215  		// TODO use this information to make sparse maps faster.
   216  		var entries fileAndPairs
   217  		for k, v := range ranges {
   218  			entries = append(entries, fileAndPair{int32(k), v})
   219  		}
   220  		sort.Sort(entries)
   221  		total := uint64(0)            // sum over files of maxline(file) - minline(file)
   222  		maxfile := int32(0)           // max(file indices)
   223  		minline := uint32(0xffffffff) // min over files of minline(file)
   224  		maxline := uint32(0)          // max over files of maxline(file)
   225  		for _, v := range entries {
   226  			if f.Pass.Stats > 1 {
   227  				f.LogStat("file", v.f, "low", v.lp.First, "high", v.lp.Last)
   228  			}
   229  			total += uint64(v.lp.Last - v.lp.First)
   230  			if maxfile < v.f {
   231  				maxfile = v.f
   232  			}
   233  			if minline > v.lp.First {
   234  				minline = v.lp.First
   235  			}
   236  			if maxline < v.lp.Last {
   237  				maxline = v.lp.Last
   238  			}
   239  		}
   240  		f.LogStat("SUM_LINE_RANGE", total, "MAXMIN_LINE_RANGE", maxline-minline, "MAXFILE", maxfile, "NFILES", len(entries))
   241  	}
   242  	// cachedLineStarts is an empty sparse map for values that are included within ranges.
   243  	f.CachedLineStarts = ssa.NewXPosMap(ranges)
   244  }
   245
View as plain text