Black Lives Matter. Support the Equal Justice Initiative.

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

View as plain text