internal/ssa/numberlines.go

// Copyright 2018 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package ssa

import (
	"cmd/internal/src"
	"fmt"
	"sort"
)

func isPoorStatementOp(op Op) bool {
	switch op {
	// Note that Nilcheck often vanishes, but when it doesn't, you'd love to start the statement there
	// so that a debugger-user sees the stop before the panic, and can examine the value.
	case OpAddr, OpLocalAddr, OpOffPtr, OpStructSelect, OpPhi, OpITab, OpIData,
		OpIMake, OpStringMake, OpSliceMake, OpStructMake0, OpStructMake1, OpStructMake2, OpStructMake3, OpStructMake4,
		OpConstBool, OpConst8, OpConst16, OpConst32, OpConst64, OpConst32F, OpConst64F, OpSB, OpSP,
		OpArgIntReg, OpArgFloatReg:
		return true
	}
	return false
}

// nextGoodStatementIndex returns an index at i or later that is believed
// to be a good place to start the statement for b.  This decision is
// based on v's Op, the possibility of a better later operation, and
// whether the values following i are the same line as v.
// If a better statement index isn't found, then i is returned.
func nextGoodStatementIndex(v *Value, i int, b *Block) int {
	// If the value is the last one in the block, too bad, it will have to do
	// (this assumes that the value ordering vaguely corresponds to the source
	// program execution order, which tends to be true directly after ssa is
	// first built).
	if i >= len(b.Values)-1 {
		return i
	}
	// Skip the likely-ephemeral/fragile opcodes expected to vanish in a rewrite.
	if !isPoorStatementOp(v.Op) {
		return i
	}
	// Look ahead to see what the line number is on the next thing that could be a boundary.
	for j := i + 1; j < len(b.Values); j++ {
		u := b.Values[j]
		if u.Pos.IsStmt() == src.PosNotStmt { // ignore non-statements
			continue
		}
		if u.Pos.SameFileAndLine(v.Pos) {
			if isPoorStatementOp(u.Op) {
				continue // Keep looking, this is also not a good statement op
			}
			return j
		}
		return i
	}
	return i
}

// notStmtBoundary reports whether a value with opcode op can never be a statement
// boundary. Such values don't correspond to a user's understanding of a
// statement boundary.
func notStmtBoundary(op Op) bool {
	switch op {
	case OpCopy, OpPhi, OpVarDef, OpVarLive, OpUnknown, OpFwdRef, OpArg, OpArgIntReg, OpArgFloatReg:
		return true
	}
	return false
}

func (b *Block) FirstPossibleStmtValue() *Value {
	for _, v := range b.Values {
		if notStmtBoundary(v.Op) {
			continue
		}
		return v
	}
	return nil
}

func flc(p src.XPos) string {
	if p == src.NoXPos {
		return "none"
	}
	return fmt.Sprintf("(%d):%d:%d", p.FileIndex(), p.Line(), p.Col())
}

type fileAndPair struct {
	f  int32
	lp lineRange
}

type fileAndPairs []fileAndPair

func (fap fileAndPairs) Len() int {
	return len(fap)
}
func (fap fileAndPairs) Less(i, j int) bool {
	return fap[i].f < fap[j].f
}
func (fap fileAndPairs) Swap(i, j int) {
	fap[i], fap[j] = fap[j], fap[i]
}

// -d=ssa/number_lines/stats=1 (that bit) for line and file distribution statistics
// -d=ssa/number_lines/debug for information about why particular values are marked as statements.
func numberLines(f *Func) {
	po := f.Postorder()
	endlines := make(map[ID]src.XPos)
	ranges := make(map[int]lineRange)
	note := func(p src.XPos) {
		line := uint32(p.Line())
		i := int(p.FileIndex())
		lp, found := ranges[i]
		change := false
		if line < lp.first || !found {
			lp.first = line
			change = true
		}
		if line > lp.last {
			lp.last = line
			change = true
		}
		if change {
			ranges[i] = lp
		}
	}

	// Visit in reverse post order so that all non-loop predecessors come first.
	for j := len(po) - 1; j >= 0; j-- {
		b := po[j]
		// Find the first interesting position and check to see if it differs from any predecessor
		firstPos := src.NoXPos
		firstPosIndex := -1
		if b.Pos.IsStmt() != src.PosNotStmt {
			note(b.Pos)
		}
		for i := 0; i < len(b.Values); i++ {
			v := b.Values[i]
			if v.Pos.IsStmt() != src.PosNotStmt {
				note(v.Pos)
				// skip ahead to better instruction for this line if possible
				i = nextGoodStatementIndex(v, i, b)
				v = b.Values[i]
				firstPosIndex = i
				firstPos = v.Pos
				v.Pos = firstPos.WithDefaultStmt() // default to default
				break
			}
		}

		if firstPosIndex == -1 { // Effectively empty block, check block's own Pos, consider preds.
			line := src.NoXPos
			for _, p := range b.Preds {
				pbi := p.Block().ID
				if !endlines[pbi].SameFileAndLine(line) {
					if line == src.NoXPos {
						line = endlines[pbi]
						continue
					} else {
						line = src.NoXPos
						break
					}

				}
			}
			// If the block has no statement itself and is effectively empty, tag it w/ predecessor(s) but not as a statement
			if b.Pos.IsStmt() == src.PosNotStmt {
				b.Pos = line
				endlines[b.ID] = line
				continue
			}
			// If the block differs from its predecessors, mark it as a statement
			if line == src.NoXPos || !line.SameFileAndLine(b.Pos) {
				b.Pos = b.Pos.WithIsStmt()
				if f.pass.debug > 0 {
					fmt.Printf("Mark stmt effectively-empty-block %s %s %s\n", f.Name, b, flc(b.Pos))
				}
			}
			endlines[b.ID] = b.Pos
			continue
		}
		// check predecessors for any difference; if firstPos differs, then it is a boundary.
		if len(b.Preds) == 0 { // Don't forget the entry block
			b.Values[firstPosIndex].Pos = firstPos.WithIsStmt()
			if f.pass.debug > 0 {
				fmt.Printf("Mark stmt entry-block %s %s %s %s\n", f.Name, b, b.Values[firstPosIndex], flc(firstPos))
			}
		} else { // differing pred
			for _, p := range b.Preds {
				pbi := p.Block().ID
				if !endlines[pbi].SameFileAndLine(firstPos) {
					b.Values[firstPosIndex].Pos = firstPos.WithIsStmt()
					if f.pass.debug > 0 {
						fmt.Printf("Mark stmt differing-pred %s %s %s %s, different=%s ending %s\n",
							f.Name, b, b.Values[firstPosIndex], flc(firstPos), p.Block(), flc(endlines[pbi]))
					}
					break
				}
			}
		}
		// iterate forward setting each new (interesting) position as a statement boundary.
		for i := firstPosIndex + 1; i < len(b.Values); i++ {
			v := b.Values[i]
			if v.Pos.IsStmt() == src.PosNotStmt {
				continue
			}
			note(v.Pos)
			// skip ahead if possible
			i = nextGoodStatementIndex(v, i, b)
			v = b.Values[i]
			if !v.Pos.SameFileAndLine(firstPos) {
				if f.pass.debug > 0 {
					fmt.Printf("Mark stmt new line %s %s %s %s prev pos = %s\n", f.Name, b, v, flc(v.Pos), flc(firstPos))
				}
				firstPos = v.Pos
				v.Pos = v.Pos.WithIsStmt()
			} else {
				v.Pos = v.Pos.WithDefaultStmt()
			}
		}
		if b.Pos.IsStmt() != src.PosNotStmt && !b.Pos.SameFileAndLine(firstPos) {
			if f.pass.debug > 0 {
				fmt.Printf("Mark stmt end of block differs %s %s %s prev pos = %s\n", f.Name, b, flc(b.Pos), flc(firstPos))
			}
			b.Pos = b.Pos.WithIsStmt()
			firstPos = b.Pos
		}
		endlines[b.ID] = firstPos
	}
	if f.pass.stats&1 != 0 {
		// Report summary statistics on the shape of the sparse map about to be constructed
		// TODO use this information to make sparse maps faster.
		var entries fileAndPairs
		for k, v := range ranges {
			entries = append(entries, fileAndPair{int32(k), v})
		}
		sort.Sort(entries)
		total := uint64(0)            // sum over files of maxline(file) - minline(file)
		maxfile := int32(0)           // max(file indices)
		minline := uint32(0xffffffff) // min over files of minline(file)
		maxline := uint32(0)          // max over files of maxline(file)
		for _, v := range entries {
			if f.pass.stats > 1 {
				f.LogStat("file", v.f, "low", v.lp.first, "high", v.lp.last)
			}
			total += uint64(v.lp.last - v.lp.first)
			if maxfile < v.f {
				maxfile = v.f
			}
			if minline > v.lp.first {
				minline = v.lp.first
			}
			if maxline < v.lp.last {
				maxline = v.lp.last
			}
		}
		f.LogStat("SUM_LINE_RANGE", total, "MAXMIN_LINE_RANGE", maxline-minline, "MAXFILE", maxfile, "NFILES", len(entries))
	}
	// cachedLineStarts is an empty sparse map for values that are included within ranges.
	f.cachedLineStarts = newXposmap(ranges)
}