Source file src/cmd/compile/internal/ssa/numberlines.go

Documentation: cmd/compile/internal/ssa

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

View as plain text