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