blob: 1d60bb606ad226101c57c95de5757e9a22f671a2 [file] [log] [blame]
// Copyright 2015 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 (
"fmt"
"math"
)
// A Func represents a Go func declaration (or function literal) and
// its body. This package compiles each Func independently.
type Func struct {
Config *Config // architecture information
pass *pass // current pass information (name, options, etc.)
Name string // e.g. bytes·Compare
Type Type // type signature of the function.
StaticData interface{} // associated static data, untouched by the ssa package
Blocks []*Block // unordered set of all basic blocks (note: not indexable by ID)
Entry *Block // the entry basic block
bid idAlloc // block ID allocator
vid idAlloc // value ID allocator
scheduled bool // Values in Blocks are in final order
// when register allocation is done, maps value ids to locations
RegAlloc []Location
// map from LocalSlot to set of Values that we want to store in that slot.
NamedValues map[LocalSlot][]*Value
// Names is a copy of NamedValues.Keys. We keep a separate list
// of keys to make iteration order deterministic.
Names []LocalSlot
freeValues *Value // free Values linked by argstorage[0]. All other fields except ID are 0/nil.
freeBlocks *Block // free Blocks linked by succstorage[0].b. All other fields except ID are 0/nil.
idom []*Block // precomputed immediate dominators
sdom SparseTree // precomputed dominator tree
constants map[int64][]*Value // constants cache, keyed by constant value; users must check value's Op and Type
}
// NumBlocks returns an integer larger than the id of any Block in the Func.
func (f *Func) NumBlocks() int {
return f.bid.num()
}
// NumValues returns an integer larger than the id of any Value in the Func.
func (f *Func) NumValues() int {
return f.vid.num()
}
// newSparseSet returns a sparse set that can store at least up to n integers.
func (f *Func) newSparseSet(n int) *sparseSet {
for i, scr := range f.Config.scrSparse {
if scr != nil && scr.cap() >= n {
f.Config.scrSparse[i] = nil
scr.clear()
return scr
}
}
return newSparseSet(n)
}
// retSparseSet returns a sparse set to the config's cache of sparse sets to be reused by f.newSparseSet.
func (f *Func) retSparseSet(ss *sparseSet) {
for i, scr := range f.Config.scrSparse {
if scr == nil {
f.Config.scrSparse[i] = ss
return
}
}
f.Config.scrSparse = append(f.Config.scrSparse, ss)
}
// newValue allocates a new Value with the given fields and places it at the end of b.Values.
func (f *Func) newValue(op Op, t Type, b *Block, line int32) *Value {
var v *Value
if f.freeValues != nil {
v = f.freeValues
f.freeValues = v.argstorage[0]
v.argstorage[0] = nil
} else {
ID := f.vid.get()
if int(ID) < len(f.Config.values) {
v = &f.Config.values[ID]
} else {
v = &Value{ID: ID}
}
}
v.Op = op
v.Type = t
v.Block = b
v.Line = line
b.Values = append(b.Values, v)
return v
}
// logPassStat writes a string key and int value as a warning in a
// tab-separated format easily handled by spreadsheets or awk.
// file names, lines, and function names are included to provide enough (?)
// context to allow item-by-item comparisons across runs.
// For example:
// awk 'BEGIN {FS="\t"} $3~/TIME/{sum+=$4} END{print "t(ns)=",sum}' t.log
func (f *Func) LogStat(key string, args ...interface{}) {
value := ""
for _, a := range args {
value += fmt.Sprintf("\t%v", a)
}
n := "missing_pass"
if f.pass != nil {
n = f.pass.name
}
f.Config.Warnl(f.Entry.Line, "\t%s\t%s%s\t%s", n, key, value, f.Name)
}
// freeValue frees a value. It must no longer be referenced.
func (f *Func) freeValue(v *Value) {
if v.Block == nil {
f.Fatalf("trying to free an already freed value")
}
if v.Uses != 0 {
f.Fatalf("value %s still has %d uses", v, v.Uses)
}
// Clear everything but ID (which we reuse).
id := v.ID
// Zero argument values might be cached, so remove them there.
nArgs := opcodeTable[v.Op].argLen
if nArgs == 0 {
vv := f.constants[v.AuxInt]
for i, cv := range vv {
if v == cv {
vv[i] = vv[len(vv)-1]
f.constants[v.AuxInt] = vv[0 : len(vv)-1]
break
}
}
}
*v = Value{}
v.ID = id
v.argstorage[0] = f.freeValues
f.freeValues = v
}
// newBlock allocates a new Block of the given kind and places it at the end of f.Blocks.
func (f *Func) NewBlock(kind BlockKind) *Block {
var b *Block
if f.freeBlocks != nil {
b = f.freeBlocks
f.freeBlocks = b.succstorage[0].b
b.succstorage[0].b = nil
} else {
ID := f.bid.get()
if int(ID) < len(f.Config.blocks) {
b = &f.Config.blocks[ID]
} else {
b = &Block{ID: ID}
}
}
b.Kind = kind
b.Func = f
b.Preds = b.predstorage[:0]
b.Succs = b.succstorage[:0]
b.Values = b.valstorage[:0]
f.Blocks = append(f.Blocks, b)
return b
}
func (f *Func) freeBlock(b *Block) {
if b.Func == nil {
f.Fatalf("trying to free an already freed block")
}
// Clear everything but ID (which we reuse).
id := b.ID
*b = Block{}
b.ID = id
b.succstorage[0].b = f.freeBlocks
f.freeBlocks = b
}
// NewValue0 returns a new value in the block with no arguments and zero aux values.
func (b *Block) NewValue0(line int32, op Op, t Type) *Value {
v := b.Func.newValue(op, t, b, line)
v.AuxInt = 0
v.Args = v.argstorage[:0]
return v
}
// NewValue returns a new value in the block with no arguments and an auxint value.
func (b *Block) NewValue0I(line int32, op Op, t Type, auxint int64) *Value {
v := b.Func.newValue(op, t, b, line)
v.AuxInt = auxint
v.Args = v.argstorage[:0]
return v
}
// NewValue returns a new value in the block with no arguments and an aux value.
func (b *Block) NewValue0A(line int32, op Op, t Type, aux interface{}) *Value {
if _, ok := aux.(int64); ok {
// Disallow int64 aux values. They should be in the auxint field instead.
// Maybe we want to allow this at some point, but for now we disallow it
// to prevent errors like using NewValue1A instead of NewValue1I.
b.Fatalf("aux field has int64 type op=%s type=%s aux=%v", op, t, aux)
}
v := b.Func.newValue(op, t, b, line)
v.AuxInt = 0
v.Aux = aux
v.Args = v.argstorage[:0]
return v
}
// NewValue returns a new value in the block with no arguments and both an auxint and aux values.
func (b *Block) NewValue0IA(line int32, op Op, t Type, auxint int64, aux interface{}) *Value {
v := b.Func.newValue(op, t, b, line)
v.AuxInt = auxint
v.Aux = aux
v.Args = v.argstorage[:0]
return v
}
// NewValue1 returns a new value in the block with one argument and zero aux values.
func (b *Block) NewValue1(line int32, op Op, t Type, arg *Value) *Value {
v := b.Func.newValue(op, t, b, line)
v.AuxInt = 0
v.Args = v.argstorage[:1]
v.argstorage[0] = arg
arg.Uses++
return v
}
// NewValue1I returns a new value in the block with one argument and an auxint value.
func (b *Block) NewValue1I(line int32, op Op, t Type, auxint int64, arg *Value) *Value {
v := b.Func.newValue(op, t, b, line)
v.AuxInt = auxint
v.Args = v.argstorage[:1]
v.argstorage[0] = arg
arg.Uses++
return v
}
// NewValue1A returns a new value in the block with one argument and an aux value.
func (b *Block) NewValue1A(line int32, op Op, t Type, aux interface{}, arg *Value) *Value {
v := b.Func.newValue(op, t, b, line)
v.AuxInt = 0
v.Aux = aux
v.Args = v.argstorage[:1]
v.argstorage[0] = arg
arg.Uses++
return v
}
// NewValue1IA returns a new value in the block with one argument and both an auxint and aux values.
func (b *Block) NewValue1IA(line int32, op Op, t Type, auxint int64, aux interface{}, arg *Value) *Value {
v := b.Func.newValue(op, t, b, line)
v.AuxInt = auxint
v.Aux = aux
v.Args = v.argstorage[:1]
v.argstorage[0] = arg
arg.Uses++
return v
}
// NewValue2 returns a new value in the block with two arguments and zero aux values.
func (b *Block) NewValue2(line int32, op Op, t Type, arg0, arg1 *Value) *Value {
v := b.Func.newValue(op, t, b, line)
v.AuxInt = 0
v.Args = v.argstorage[:2]
v.argstorage[0] = arg0
v.argstorage[1] = arg1
arg0.Uses++
arg1.Uses++
return v
}
// NewValue2I returns a new value in the block with two arguments and an auxint value.
func (b *Block) NewValue2I(line int32, op Op, t Type, auxint int64, arg0, arg1 *Value) *Value {
v := b.Func.newValue(op, t, b, line)
v.AuxInt = auxint
v.Args = v.argstorage[:2]
v.argstorage[0] = arg0
v.argstorage[1] = arg1
arg0.Uses++
arg1.Uses++
return v
}
// NewValue3 returns a new value in the block with three arguments and zero aux values.
func (b *Block) NewValue3(line int32, op Op, t Type, arg0, arg1, arg2 *Value) *Value {
v := b.Func.newValue(op, t, b, line)
v.AuxInt = 0
v.Args = v.argstorage[:3]
v.argstorage[0] = arg0
v.argstorage[1] = arg1
v.argstorage[2] = arg2
arg0.Uses++
arg1.Uses++
arg2.Uses++
return v
}
// NewValue3I returns a new value in the block with three arguments and an auxint value.
func (b *Block) NewValue3I(line int32, op Op, t Type, auxint int64, arg0, arg1, arg2 *Value) *Value {
v := b.Func.newValue(op, t, b, line)
v.AuxInt = auxint
v.Args = v.argstorage[:3]
v.argstorage[0] = arg0
v.argstorage[1] = arg1
v.argstorage[2] = arg2
arg0.Uses++
arg1.Uses++
arg2.Uses++
return v
}
// constVal returns a constant value for c.
func (f *Func) constVal(line int32, op Op, t Type, c int64, setAux bool) *Value {
if f.constants == nil {
f.constants = make(map[int64][]*Value)
}
vv := f.constants[c]
for _, v := range vv {
if v.Op == op && v.Type.Compare(t) == CMPeq {
if setAux && v.AuxInt != c {
panic(fmt.Sprintf("cached const %s should have AuxInt of %d", v.LongString(), c))
}
return v
}
}
var v *Value
if setAux {
v = f.Entry.NewValue0I(line, op, t, c)
} else {
v = f.Entry.NewValue0(line, op, t)
}
f.constants[c] = append(vv, v)
return v
}
// These magic auxint values let us easily cache non-numeric constants
// using the same constants map while making collisions unlikely.
// These values are unlikely to occur in regular code and
// are easy to grep for in case of bugs.
const (
constSliceMagic = 1122334455
constInterfaceMagic = 2233445566
constNilMagic = 3344556677
constEmptyStringMagic = 4455667788
)
// ConstInt returns an int constant representing its argument.
func (f *Func) ConstBool(line int32, t Type, c bool) *Value {
i := int64(0)
if c {
i = 1
}
return f.constVal(line, OpConstBool, t, i, true)
}
func (f *Func) ConstInt8(line int32, t Type, c int8) *Value {
return f.constVal(line, OpConst8, t, int64(c), true)
}
func (f *Func) ConstInt16(line int32, t Type, c int16) *Value {
return f.constVal(line, OpConst16, t, int64(c), true)
}
func (f *Func) ConstInt32(line int32, t Type, c int32) *Value {
return f.constVal(line, OpConst32, t, int64(c), true)
}
func (f *Func) ConstInt64(line int32, t Type, c int64) *Value {
return f.constVal(line, OpConst64, t, c, true)
}
func (f *Func) ConstFloat32(line int32, t Type, c float64) *Value {
return f.constVal(line, OpConst32F, t, int64(math.Float64bits(float64(float32(c)))), true)
}
func (f *Func) ConstFloat64(line int32, t Type, c float64) *Value {
return f.constVal(line, OpConst64F, t, int64(math.Float64bits(c)), true)
}
func (f *Func) ConstSlice(line int32, t Type) *Value {
return f.constVal(line, OpConstSlice, t, constSliceMagic, false)
}
func (f *Func) ConstInterface(line int32, t Type) *Value {
return f.constVal(line, OpConstInterface, t, constInterfaceMagic, false)
}
func (f *Func) ConstNil(line int32, t Type) *Value {
return f.constVal(line, OpConstNil, t, constNilMagic, false)
}
func (f *Func) ConstEmptyString(line int32, t Type) *Value {
v := f.constVal(line, OpConstString, t, constEmptyStringMagic, false)
v.Aux = ""
return v
}
func (f *Func) Logf(msg string, args ...interface{}) { f.Config.Logf(msg, args...) }
func (f *Func) Log() bool { return f.Config.Log() }
func (f *Func) Fatalf(msg string, args ...interface{}) { f.Config.Fatalf(f.Entry.Line, msg, args...) }
func (f *Func) Unimplementedf(msg string, args ...interface{}) {
f.Config.Unimplementedf(f.Entry.Line, msg, args...)
}
func (f *Func) Free() {
// Clear values.
n := f.vid.num()
if n > len(f.Config.values) {
n = len(f.Config.values)
}
for i := 1; i < n; i++ {
f.Config.values[i] = Value{}
f.Config.values[i].ID = ID(i)
}
// Clear blocks.
n = f.bid.num()
if n > len(f.Config.blocks) {
n = len(f.Config.blocks)
}
for i := 1; i < n; i++ {
f.Config.blocks[i] = Block{}
f.Config.blocks[i].ID = ID(i)
}
// Unregister from config.
if f.Config.curFunc != f {
f.Fatalf("free of function which isn't the last one allocated")
}
f.Config.curFunc = nil
*f = Func{} // just in case
}