Source file src/pkg/cmd/compile/internal/ssa/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/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