blob: bd7794042a280b072705035cbe5d259398e483d8 [file] [log] [blame] [edit]
// 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, OpStructMake,
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)
}