src/cmd/compile/internal/ssa/func.go - go - Git at Google

 // 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 (
 	"cmd/compile/internal/types"
 	"cmd/internal/src"
 	"crypto/sha1"
 	"fmt"
 	"io"
 	"math"
 	"os"
 	"strings"
 )

 type writeSyncer interface {
 	io.Writer
 	Sync() error
 }

 // A Func represents a Go func declaration (or function literal) and its body.
 // This package compiles each Func independently.
 // Funcs are single-use; a new Func must be created for every compiled function.
 type Func struct {
 	Config *Config     // architecture information
 	Cache  *Cache      // re-usable cache
 	fe     Frontend    // frontend state associated with this Func, callbacks into compiler frontend
 	pass   *pass       // current pass information (name, options, etc.)
 	Name   string      // e.g. bytes·Compare
 	Type   *types.Type // type signature of the function.
 	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

 	// Given an environment variable used for debug hash match,
 	// what file (if any) receives the yes/no logging?
 	logfiles   map[string]writeSyncer
 	HTMLWriter *HTMLWriter // html writer, for debugging
 	DebugTest  bool        // default true unless $GOSSAHASH != ""; as a debugging aid, make new code conditional on this and use GOSSAHASH to binary search for failing cases

 	scheduled bool // Values in Blocks are in final order
 	NoSplit   bool // true if function is marked as nosplit.  Used by schedule check pass.

 	// 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.

 	cachedPostorder []*Block   // cached postorder traversal
 	cachedIdom      []*Block   // cached immediate dominators
 	cachedSdom      SparseTree // cached dominator tree
 	cachedLoopnest  *loopnest  // cached loop nest information

 	auxmap auxmap // map from aux values to opaque ids used by CSE

 	constants map[int64][]*Value // constants cache, keyed by constant value; users must check value's Op and Type
 }

 // NewFunc returns a new, empty function object.
 // Caller must set f.Config and f.Cache before using f.
 func NewFunc(fe Frontend) *Func {
 	return &Func{fe: fe, NamedValues: make(map[LocalSlot][]*Value)}
 }

 // 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.Cache.scrSparse {
 		if scr != nil && scr.cap() >= n {
 			f.Cache.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.Cache.scrSparse {
 		if scr == nil {
 			f.Cache.scrSparse[i] = ss
 			return
 		}
 	}
 	f.Cache.scrSparse = append(f.Cache.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 *types.Type, b *Block, pos src.XPos) *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.Cache.values) {
 			v = &f.Cache.values[ID]
 			v.ID = ID
 		} else {
 			v = &Value{ID: ID}
 		}
 	}
 	v.Op = op
 	v.Type = t
 	v.Block = b
 	v.Pos = pos
 	b.Values = append(b.Values, v)
 	return v
 }

 // newValueNoBlock allocates a new Value with the given fields.
 // The returned value is not placed in any block.  Once the caller
 // decides on a block b, it must set b.Block and append
 // the returned value to b.Values.
 func (f *Func) newValueNoBlock(op Op, t *types.Type, pos src.XPos) *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.Cache.values) {
 			v = &f.Cache.values[ID]
 			v.ID = ID
 		} else {
 			v = &Value{ID: ID}
 		}
 	}
 	v.Op = op
 	v.Type = t
 	v.Block = nil // caller must fix this.
 	v.Pos = pos
 	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 = strings.Replace(f.pass.name, " ", "_", -1)
 	}
 	f.Warnl(f.Entry.Pos, "\t%s\t%s%s\t%s", n, key, value, f.Name)
 }

 // freeValue frees a value. It must no longer be referenced or have any args.
 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)
 	}
 	if len(v.Args) != 0 {
 		f.Fatalf("value %s still has %d args", v, len(v.Args))
 	}
 	// Clear everything but ID (which we reuse).
 	id := v.ID

 	// Values with zero arguments and OpOffPtr values might be cached, so remove them there.
 	nArgs := opcodeTable[v.Op].argLen
 	if nArgs == 0 || v.Op == OpOffPtr {
 		vv := f.constants[v.AuxInt]
 		for i, cv := range vv {
 			if v == cv {
 				vv[i] = vv[len(vv)-1]
 				vv[len(vv)-1] = nil
 				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.Cache.blocks) {
 			b = &f.Cache.blocks[ID]
 			b.ID = 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)
 	f.invalidateCFG()
 	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(pos src.XPos, op Op, t *types.Type) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	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(pos src.XPos, op Op, t *types.Type, auxint int64) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	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(pos src.XPos, op Op, t *types.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, pos)
 	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(pos src.XPos, op Op, t *types.Type, auxint int64, aux interface{}) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	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(pos src.XPos, op Op, t *types.Type, arg *Value) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	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(pos src.XPos, op Op, t *types.Type, auxint int64, arg *Value) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	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(pos src.XPos, op Op, t *types.Type, aux interface{}, arg *Value) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	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(pos src.XPos, op Op, t *types.Type, auxint int64, aux interface{}, arg *Value) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	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(pos src.XPos, op Op, t *types.Type, arg0, arg1 *Value) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	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(pos src.XPos, op Op, t *types.Type, auxint int64, arg0, arg1 *Value) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	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(pos src.XPos, op Op, t *types.Type, arg0, arg1, arg2 *Value) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	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(pos src.XPos, op Op, t *types.Type, auxint int64, arg0, arg1, arg2 *Value) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	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
 }

 // NewValue3A returns a new value in the block with three argument and an aux value.
 func (b *Block) NewValue3A(pos src.XPos, op Op, t *types.Type, aux interface{}, arg0, arg1, arg2 *Value) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	v.AuxInt = 0
 	v.Aux = aux
 	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
 }

 // NewValue4 returns a new value in the block with four arguments and zero aux values.
 func (b *Block) NewValue4(pos src.XPos, op Op, t *types.Type, arg0, arg1, arg2, arg3 *Value) *Value {
 	v := b.Func.newValue(op, t, b, pos)
 	v.AuxInt = 0
 	v.Args = []*Value{arg0, arg1, arg2, arg3}
 	arg0.Uses++
 	arg1.Uses++
 	arg2.Uses++
 	arg3.Uses++
 	return v
 }

 // constVal returns a constant value for c.
 func (f *Func) constVal(pos src.XPos, op Op, t *types.Type, c int64, setAuxInt bool) *Value {
 	// TODO remove unused pos parameter, both here and in *func.ConstXXX callers.
 	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) == types.CMPeq {
 			if setAuxInt && v.AuxInt != c {
 				panic(fmt.Sprintf("cached const %s should have AuxInt of %d", v.LongString(), c))
 			}
 			return v
 		}
 	}
 	var v *Value
 	if setAuxInt {
 		v = f.Entry.NewValue0I(src.NoXPos, op, t, c)
 	} else {
 		v = f.Entry.NewValue0(src.NoXPos, 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(pos src.XPos, t *types.Type, c bool) *Value {
 	i := int64(0)
 	if c {
 		i = 1
 	}
 	return f.constVal(pos, OpConstBool, t, i, true)
 }
 func (f *Func) ConstInt8(pos src.XPos, t *types.Type, c int8) *Value {
 	return f.constVal(pos, OpConst8, t, int64(c), true)
 }
 func (f *Func) ConstInt16(pos src.XPos, t *types.Type, c int16) *Value {
 	return f.constVal(pos, OpConst16, t, int64(c), true)
 }
 func (f *Func) ConstInt32(pos src.XPos, t *types.Type, c int32) *Value {
 	return f.constVal(pos, OpConst32, t, int64(c), true)
 }
 func (f *Func) ConstInt64(pos src.XPos, t *types.Type, c int64) *Value {
 	return f.constVal(pos, OpConst64, t, c, true)
 }
 func (f *Func) ConstFloat32(pos src.XPos, t *types.Type, c float64) *Value {
 	return f.constVal(pos, OpConst32F, t, int64(math.Float64bits(float64(float32(c)))), true)
 }
 func (f *Func) ConstFloat64(pos src.XPos, t *types.Type, c float64) *Value {
 	return f.constVal(pos, OpConst64F, t, int64(math.Float64bits(c)), true)
 }

 func (f *Func) ConstSlice(pos src.XPos, t *types.Type) *Value {
 	return f.constVal(pos, OpConstSlice, t, constSliceMagic, false)
 }
 func (f *Func) ConstInterface(pos src.XPos, t *types.Type) *Value {
 	return f.constVal(pos, OpConstInterface, t, constInterfaceMagic, false)
 }
 func (f *Func) ConstNil(pos src.XPos, t *types.Type) *Value {
 	return f.constVal(pos, OpConstNil, t, constNilMagic, false)
 }
 func (f *Func) ConstEmptyString(pos src.XPos, t *types.Type) *Value {
 	v := f.constVal(pos, OpConstString, t, constEmptyStringMagic, false)
 	v.Aux = ""
 	return v
 }
 func (f *Func) ConstOffPtrSP(pos src.XPos, t *types.Type, c int64, sp *Value) *Value {
 	v := f.constVal(pos, OpOffPtr, t, c, true)
 	if len(v.Args) == 0 {
 		v.AddArg(sp)
 	}
 	return v

 }

 func (f *Func) Frontend() Frontend                                  { return f.fe }
 func (f *Func) Warnl(pos src.XPos, msg string, args ...interface{}) { f.fe.Warnl(pos, msg, args...) }
 func (f *Func) Logf(msg string, args ...interface{})                { f.fe.Logf(msg, args...) }
 func (f *Func) Log() bool                                           { return f.fe.Log() }
 func (f *Func) Fatalf(msg string, args ...interface{})              { f.fe.Fatalf(f.Entry.Pos, msg, args...) }

 // postorder returns the reachable blocks in f in a postorder traversal.
 func (f *Func) postorder() []*Block {
 	if f.cachedPostorder == nil {
 		f.cachedPostorder = postorder(f)
 	}
 	return f.cachedPostorder
 }

 func (f *Func) Postorder() []*Block {
 	return f.postorder()
 }

 // Idom returns a map from block ID to the immediate dominator of that block.
 // f.Entry.ID maps to nil. Unreachable blocks map to nil as well.
 func (f *Func) Idom() []*Block {
 	if f.cachedIdom == nil {
 		f.cachedIdom = dominators(f)
 	}
 	return f.cachedIdom
 }

 // sdom returns a sparse tree representing the dominator relationships
 // among the blocks of f.
 func (f *Func) sdom() SparseTree {
 	if f.cachedSdom == nil {
 		f.cachedSdom = newSparseTree(f, f.Idom())
 	}
 	return f.cachedSdom
 }

 // loopnest returns the loop nest information for f.
 func (f *Func) loopnest() *loopnest {
 	if f.cachedLoopnest == nil {
 		f.cachedLoopnest = loopnestfor(f)
 	}
 	return f.cachedLoopnest
 }

 // invalidateCFG tells f that its CFG has changed.
 func (f *Func) invalidateCFG() {
 	f.cachedPostorder = nil
 	f.cachedIdom = nil
 	f.cachedSdom = nil
 	f.cachedLoopnest = nil
 }

 // DebugHashMatch returns true if environment variable evname
 // 1) is empty (this is a special more-quickly implemented case of 3)
 // 2) is "y" or "Y"
 // 3) is a suffix of the sha1 hash of name
 // 4) is a suffix of the environment variable
 //    fmt.Sprintf("%s%d", evname, n)
 //    provided that all such variables are nonempty for 0 <= i <= n
 // Otherwise it returns false.
 // When true is returned the message
 //  "%s triggered %s\n", evname, name
 // is printed on the file named in environment variable
 //  GSHS_LOGFILE
 // or standard out if that is empty or there is an error
 // opening the file.
 func (f *Func) DebugHashMatch(evname, name string) bool {
 	evhash := os.Getenv(evname)
 	switch evhash {
 	case "":
 		return true // default behavior with no EV is "on"
 	case "y", "Y":
 		f.logDebugHashMatch(evname, name)
 		return true
 	case "n", "N":
 		return false
 	}
 	// Check the hash of the name against a partial input hash.
 	// We use this feature to do a binary search to
 	// find a function that is incorrectly compiled.
 	hstr := ""
 	for _, b := range sha1.Sum([]byte(name)) {
 		hstr += fmt.Sprintf("%08b", b)
 	}

 	if strings.HasSuffix(hstr, evhash) {
 		f.logDebugHashMatch(evname, name)
 		return true
 	}

 	// Iteratively try additional hashes to allow tests for multi-point
 	// failure.
 	for i := 0; true; i++ {
 		ev := fmt.Sprintf("%s%d", evname, i)
 		evv := os.Getenv(ev)
 		if evv == "" {
 			break
 		}
 		if strings.HasSuffix(hstr, evv) {
 			f.logDebugHashMatch(ev, name)
 			return true
 		}
 	}
 	return false
 }

 func (f *Func) logDebugHashMatch(evname, name string) {
 	if f.logfiles == nil {
 		f.logfiles = make(map[string]writeSyncer)
 	}
 	file := f.logfiles[evname]
 	if file == nil {
 		file = os.Stdout
 		if tmpfile := os.Getenv("GSHS_LOGFILE"); tmpfile != "" {
 			var err error
 			file, err = os.Create(tmpfile)
 			if err != nil {
 				f.Fatalf("could not open hash-testing logfile %s", tmpfile)
 			}
 		}
 		f.logfiles[evname] = file
 	}
 	fmt.Fprintf(file, "%s triggered %s\n", evname, name)
 	file.Sync()
 }

 func DebugNameMatch(evname, name string) bool {
 	return os.Getenv(evname) == name
 }
	// 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 (
	"cmd/compile/internal/types"
	"cmd/internal/src"
	"crypto/sha1"
	"fmt"
	"io"
	"math"
	"os"
	"strings"
	)

	type writeSyncer interface {
	io.Writer
	Sync() error
	}

	// A Func represents a Go func declaration (or function literal) and its body.
	// This package compiles each Func independently.
	// Funcs are single-use; a new Func must be created for every compiled function.
	type Func struct {
	Config *Config // architecture information
	Cache *Cache // re-usable cache
	fe Frontend // frontend state associated with this Func, callbacks into compiler frontend
	pass *pass // current pass information (name, options, etc.)
	Name string // e.g. bytes·Compare
	Type *types.Type // type signature of the function.
	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

	// Given an environment variable used for debug hash match,
	// what file (if any) receives the yes/no logging?
	logfiles map[string]writeSyncer
	HTMLWriter *HTMLWriter // html writer, for debugging
	DebugTest bool // default true unless $GOSSAHASH != ""; as a debugging aid, make new code conditional on this and use GOSSAHASH to binary search for failing cases

	scheduled bool // Values in Blocks are in final order
	NoSplit bool // true if function is marked as nosplit. Used by schedule check pass.

	// 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.

	cachedPostorder []*Block // cached postorder traversal
	cachedIdom []*Block // cached immediate dominators
	cachedSdom SparseTree // cached dominator tree
	cachedLoopnest *loopnest // cached loop nest information

	auxmap auxmap // map from aux values to opaque ids used by CSE

	constants map[int64][]*Value // constants cache, keyed by constant value; users must check value's Op and Type
	}

	// NewFunc returns a new, empty function object.
	// Caller must set f.Config and f.Cache before using f.
	func NewFunc(fe Frontend) *Func {
	return &Func{fe: fe, NamedValues: make(map[LocalSlot][]*Value)}
	}

	// 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.Cache.scrSparse {
	if scr != nil && scr.cap() >= n {
	f.Cache.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.Cache.scrSparse {
	if scr == nil {
	f.Cache.scrSparse[i] = ss
	return
	}
	}
	f.Cache.scrSparse = append(f.Cache.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 types.Type, b Block, pos src.XPos) 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.Cache.values) {
	v = &f.Cache.values[ID]
	v.ID = ID
	} else {
	v = &Value{ID: ID}
	}
	}
	v.Op = op
	v.Type = t
	v.Block = b
	v.Pos = pos
	b.Values = append(b.Values, v)
	return v
	}

	// newValueNoBlock allocates a new Value with the given fields.
	// The returned value is not placed in any block. Once the caller
	// decides on a block b, it must set b.Block and append
	// the returned value to b.Values.
	func (f Func) newValueNoBlock(op Op, t types.Type, pos src.XPos) *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.Cache.values) {
	v = &f.Cache.values[ID]
	v.ID = ID
	} else {
	v = &Value{ID: ID}
	}
	}
	v.Op = op
	v.Type = t
	v.Block = nil // caller must fix this.
	v.Pos = pos
	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 = strings.Replace(f.pass.name, " ", "_", -1)
	}
	f.Warnl(f.Entry.Pos, "\t%s\t%s%s\t%s", n, key, value, f.Name)
	}

	// freeValue frees a value. It must no longer be referenced or have any args.
	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)
	}
	if len(v.Args) != 0 {
	f.Fatalf("value %s still has %d args", v, len(v.Args))
	}
	// Clear everything but ID (which we reuse).
	id := v.ID

	// Values with zero arguments and OpOffPtr values might be cached, so remove them there.
	nArgs := opcodeTable[v.Op].argLen
	if nArgs == 0 \|\| v.Op == OpOffPtr {
	vv := f.constants[v.AuxInt]
	for i, cv := range vv {
	if v == cv {
	vv[i] = vv[len(vv)-1]
	vv[len(vv)-1] = nil
	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.Cache.blocks) {
	b = &f.Cache.blocks[ID]
	b.ID = 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)
	f.invalidateCFG()
	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(pos src.XPos, op Op, t types.Type) *Value {
	v := b.Func.newValue(op, t, b, pos)
	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(pos src.XPos, op Op, t types.Type, auxint int64) *Value {
	v := b.Func.newValue(op, t, b, pos)
	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(pos src.XPos, op Op, t types.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, pos)
	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(pos src.XPos, op Op, t types.Type, auxint int64, aux interface{}) *Value {
	v := b.Func.newValue(op, t, b, pos)
	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(pos src.XPos, op Op, t types.Type, arg Value) Value {
	v := b.Func.newValue(op, t, b, pos)
	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(pos src.XPos, op Op, t types.Type, auxint int64, arg Value) Value {
	v := b.Func.newValue(op, t, b, pos)
	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(pos src.XPos, op Op, t types.Type, aux interface{}, arg Value) Value {
	v := b.Func.newValue(op, t, b, pos)
	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(pos src.XPos, op Op, t types.Type, auxint int64, aux interface{}, arg Value) Value {
	v := b.Func.newValue(op, t, b, pos)
	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(pos src.XPos, op Op, t types.Type, arg0, arg1 Value) Value {
	v := b.Func.newValue(op, t, b, pos)
	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(pos src.XPos, op Op, t types.Type, auxint int64, arg0, arg1 Value) Value {
	v := b.Func.newValue(op, t, b, pos)
	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(pos src.XPos, op Op, t types.Type, arg0, arg1, arg2 Value) Value {
	v := b.Func.newValue(op, t, b, pos)
	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(pos src.XPos, op Op, t types.Type, auxint int64, arg0, arg1, arg2 Value) Value {
	v := b.Func.newValue(op, t, b, pos)
	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
	}

	// NewValue3A returns a new value in the block with three argument and an aux value.
	func (b Block) NewValue3A(pos src.XPos, op Op, t types.Type, aux interface{}, arg0, arg1, arg2 Value) Value {
	v := b.Func.newValue(op, t, b, pos)
	v.AuxInt = 0
	v.Aux = aux
	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
	}

	// NewValue4 returns a new value in the block with four arguments and zero aux values.
	func (b Block) NewValue4(pos src.XPos, op Op, t types.Type, arg0, arg1, arg2, arg3 Value) Value {
	v := b.Func.newValue(op, t, b, pos)
	v.AuxInt = 0
	v.Args = []*Value{arg0, arg1, arg2, arg3}
	arg0.Uses++
	arg1.Uses++
	arg2.Uses++
	arg3.Uses++
	return v
	}

	// constVal returns a constant value for c.
	func (f Func) constVal(pos src.XPos, op Op, t types.Type, c int64, setAuxInt bool) *Value {
	// TODO remove unused pos parameter, both here and in *func.ConstXXX callers.
	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) == types.CMPeq {
	if setAuxInt && v.AuxInt != c {
	panic(fmt.Sprintf("cached const %s should have AuxInt of %d", v.LongString(), c))
	}
	return v
	}
	}
	var v *Value
	if setAuxInt {
	v = f.Entry.NewValue0I(src.NoXPos, op, t, c)
	} else {
	v = f.Entry.NewValue0(src.NoXPos, 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(pos src.XPos, t types.Type, c bool) *Value {
	i := int64(0)
	if c {
	i = 1
	}
	return f.constVal(pos, OpConstBool, t, i, true)
	}
	func (f Func) ConstInt8(pos src.XPos, t types.Type, c int8) *Value {
	return f.constVal(pos, OpConst8, t, int64(c), true)
	}
	func (f Func) ConstInt16(pos src.XPos, t types.Type, c int16) *Value {
	return f.constVal(pos, OpConst16, t, int64(c), true)
	}
	func (f Func) ConstInt32(pos src.XPos, t types.Type, c int32) *Value {
	return f.constVal(pos, OpConst32, t, int64(c), true)
	}
	func (f Func) ConstInt64(pos src.XPos, t types.Type, c int64) *Value {
	return f.constVal(pos, OpConst64, t, c, true)
	}
	func (f Func) ConstFloat32(pos src.XPos, t types.Type, c float64) *Value {
	return f.constVal(pos, OpConst32F, t, int64(math.Float64bits(float64(float32(c)))), true)
	}
	func (f Func) ConstFloat64(pos src.XPos, t types.Type, c float64) *Value {
	return f.constVal(pos, OpConst64F, t, int64(math.Float64bits(c)), true)
	}

	func (f Func) ConstSlice(pos src.XPos, t types.Type) *Value {
	return f.constVal(pos, OpConstSlice, t, constSliceMagic, false)
	}
	func (f Func) ConstInterface(pos src.XPos, t types.Type) *Value {
	return f.constVal(pos, OpConstInterface, t, constInterfaceMagic, false)
	}
	func (f Func) ConstNil(pos src.XPos, t types.Type) *Value {
	return f.constVal(pos, OpConstNil, t, constNilMagic, false)
	}
	func (f Func) ConstEmptyString(pos src.XPos, t types.Type) *Value {
	v := f.constVal(pos, OpConstString, t, constEmptyStringMagic, false)
	v.Aux = ""
	return v
	}
	func (f Func) ConstOffPtrSP(pos src.XPos, t types.Type, c int64, sp Value) Value {
	v := f.constVal(pos, OpOffPtr, t, c, true)
	if len(v.Args) == 0 {
	v.AddArg(sp)
	}
	return v

	}

	func (f *Func) Frontend() Frontend { return f.fe }
	func (f *Func) Warnl(pos src.XPos, msg string, args ...interface{}) { f.fe.Warnl(pos, msg, args...) }
	func (f *Func) Logf(msg string, args ...interface{}) { f.fe.Logf(msg, args...) }
	func (f *Func) Log() bool { return f.fe.Log() }
	func (f *Func) Fatalf(msg string, args ...interface{}) { f.fe.Fatalf(f.Entry.Pos, msg, args...) }

	// postorder returns the reachable blocks in f in a postorder traversal.
	func (f Func) postorder() []Block {
	if f.cachedPostorder == nil {
	f.cachedPostorder = postorder(f)
	}
	return f.cachedPostorder
	}

	func (f Func) Postorder() []Block {
	return f.postorder()
	}

	// Idom returns a map from block ID to the immediate dominator of that block.
	// f.Entry.ID maps to nil. Unreachable blocks map to nil as well.
	func (f Func) Idom() []Block {
	if f.cachedIdom == nil {
	f.cachedIdom = dominators(f)
	}
	return f.cachedIdom
	}

	// sdom returns a sparse tree representing the dominator relationships
	// among the blocks of f.
	func (f *Func) sdom() SparseTree {
	if f.cachedSdom == nil {
	f.cachedSdom = newSparseTree(f, f.Idom())
	}
	return f.cachedSdom
	}

	// loopnest returns the loop nest information for f.
	func (f Func) loopnest() loopnest {
	if f.cachedLoopnest == nil {
	f.cachedLoopnest = loopnestfor(f)
	}
	return f.cachedLoopnest
	}

	// invalidateCFG tells f that its CFG has changed.
	func (f *Func) invalidateCFG() {
	f.cachedPostorder = nil
	f.cachedIdom = nil
	f.cachedSdom = nil
	f.cachedLoopnest = nil
	}

	// DebugHashMatch returns true if environment variable evname
	// 1) is empty (this is a special more-quickly implemented case of 3)
	// 2) is "y" or "Y"
	// 3) is a suffix of the sha1 hash of name
	// 4) is a suffix of the environment variable
	// fmt.Sprintf("%s%d", evname, n)
	// provided that all such variables are nonempty for 0 <= i <= n
	// Otherwise it returns false.
	// When true is returned the message
	// "%s triggered %s\n", evname, name
	// is printed on the file named in environment variable
	// GSHS_LOGFILE
	// or standard out if that is empty or there is an error
	// opening the file.
	func (f *Func) DebugHashMatch(evname, name string) bool {
	evhash := os.Getenv(evname)
	switch evhash {
	case "":
	return true // default behavior with no EV is "on"
	case "y", "Y":
	f.logDebugHashMatch(evname, name)
	return true
	case "n", "N":
	return false
	}
	// Check the hash of the name against a partial input hash.
	// We use this feature to do a binary search to
	// find a function that is incorrectly compiled.
	hstr := ""
	for _, b := range sha1.Sum([]byte(name)) {
	hstr += fmt.Sprintf("%08b", b)
	}

	if strings.HasSuffix(hstr, evhash) {
	f.logDebugHashMatch(evname, name)
	return true
	}

	// Iteratively try additional hashes to allow tests for multi-point
	// failure.
	for i := 0; true; i++ {
	ev := fmt.Sprintf("%s%d", evname, i)
	evv := os.Getenv(ev)
	if evv == "" {
	break
	}
	if strings.HasSuffix(hstr, evv) {
	f.logDebugHashMatch(ev, name)
	return true
	}
	}
	return false
	}

	func (f *Func) logDebugHashMatch(evname, name string) {
	if f.logfiles == nil {
	f.logfiles = make(map[string]writeSyncer)
	}
	file := f.logfiles[evname]
	if file == nil {
	file = os.Stdout
	if tmpfile := os.Getenv("GSHS_LOGFILE"); tmpfile != "" {
	var err error
	file, err = os.Create(tmpfile)
	if err != nil {
	f.Fatalf("could not open hash-testing logfile %s", tmpfile)
	}
	}
	f.logfiles[evname] = file
	}
	fmt.Fprintf(file, "%s triggered %s\n", evname, name)
	file.Sync()
	}

	func DebugNameMatch(evname, name string) bool {
	return os.Getenv(evname) == name
	}