ceremonyclient/bedlam/compiler/ast/ssagen.go

//
// Copyright (c) 2019-2024 Markku Rossi
//
// All rights reserved.
//

package ast

import (
	"fmt"
	"os"
	"slices"

	"github.com/markkurossi/tabulate"
	"source.quilibrium.com/quilibrium/monorepo/bedlam/compiler/ssa"
	"source.quilibrium.com/quilibrium/monorepo/bedlam/types"
)

const (
	debugConstFold = false
)

// SSA implements the compiler.ast.AST.SSA for list statements.
func (ast List) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	var err error

	for _, b := range ast {
		if block.Dead {
			warn := true
			ret, ok := b.(*Return)
			if ok && ret.AutoGenerated {
				warn = false
			}
			if warn {
				ctx.Warningf(b, "unreachable code")
			}
			break
		}
		block, _, err = b.SSA(block, ctx, gen)
		if err != nil {
			return nil, nil, err
		}
	}

	return block, nil, nil
}

// SSA implements the compiler.ast.AST.SSA for function definitions.
func (ast *Func) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	ctx.Start().Name = fmt.Sprintf("%s#%d", ast.Name, ast.NumInstances)
	ctx.Return().Name = fmt.Sprintf("%s.ret#%d", ast.Name, ast.NumInstances)
	ast.NumInstances++

	// Define return variables.
	for idx, ret := range ast.Return {
		if len(ret.Name) == 0 {
			ret.Name = fmt.Sprintf("%%ret%d", idx)
		}
		typeInfo, err := ret.Type.Resolve(NewEnv(block), ctx, gen)
		if err != nil {
			return nil, nil, ctx.Errorf(ret, "invalid return type: %s", err)
		}
		r := gen.NewVal(ret.Name, typeInfo, ctx.Scope())
		block.Bindings.Define(r, nil)
	}

	ast.Body = append(ast.Body, &Return{
		Point:         ast.End,
		AutoGenerated: true,
	})

	block, _, err := ast.Body.SSA(block, ctx, gen)
	if err != nil {
		return nil, nil, err
	}

	// Select return variables.
	var vars []ssa.Value
	var diff bool
	for _, ret := range ast.Return {
		v, d, ok := ctx.Start().ReturnBinding(ssa.NewReturnBindingCTX(),
			ret.Name, ctx.Return(), gen)
		if !ok {
			return nil, nil, ctx.Errorf(ast, "undefined variable '%s'",
				ret.Name)
		}
		if d {
			diff = true
		}
		vars = append(vars, v)
	}
	if diff {
		ctx.Warningf(ast, "function %s returns different sized values",
			ast.Name)
		tab := tabulate.New(tabulate.Plain)
		tab.Header("Return").SetAlign(tabulate.ML)
		for idx, r := range ast.Return {
			name := r.Name
			if len(name) == 0 {
				name = fmt.Sprintf("r%v", idx)
			}
			tab.Header(name).SetAlign(tabulate.MR)
		}
		maxBits := make([]types.Size, len(ast.Return))
		for _, r := range ast.Returns {
			row := tab.Row()
			row.Column(fmt.Sprintf("\u251C\u2574%s",
				r.Return.Location().ShortString()))
			for idx, t := range r.Types {
				row.Column(fmt.Sprintf("%v", t.Bits))
				if t.Bits > maxBits[idx] {
					maxBits[idx] = t.Bits
				}
			}
		}
		row := tab.Row()
		row.Column("\u2514\u2574Returns").SetFormat(tabulate.FmtBold)
		for _, bits := range maxBits {
			row.Column(fmt.Sprintf("%v", bits)).SetFormat(tabulate.FmtBold)
		}
		tab.Print(os.Stdout)
	}

	caller := ctx.Caller()
	if caller == nil {
		ctx.Return().AddInstr(ssa.NewRetInstr(vars))
	}

	return block, vars, nil
}

// SSA implements the compiler.ast.AST.SSA for variable definitions.
func (ast *VariableDef) SSA(block *ssa.Block, ctx *Codegen,
	gen *ssa.Generator) (*ssa.Block, []ssa.Value, error) {

	typeInfo, err := ast.Type.Resolve(NewEnv(block), ctx, gen)
	if err != nil {
		return nil, nil, ctx.Errorf(ast, "invalid variable type: %s", err)
	}

	for _, n := range ast.Names {
		var init ssa.Value
		if ast.Init == nil {
			if typeInfo.Undefined() {
				return nil, nil, ctx.Errorf(ast, "undefined variable")
			}
			if !typeInfo.Concrete() {
				if typeInfo.Type != types.TSlice {
					return nil, nil, ctx.Errorf(ast.Type,
						"unspecified size for type %v", ast.Type)
				}
				// Empty slices can be instantiated in variable
				// declaration time.
				typeInfo.SetConcrete(true)
			}
			initVal, err := initValue(typeInfo)
			if err != nil {
				return nil, nil, ctx.Error(ast, err.Error())
			}
			init = gen.Constant(initVal, typeInfo)
			gen.AddConstant(init)
		} else {
			// Check if the init value is constant.
			env := NewEnv(block)
			constVal, ok, err := ast.Init.Eval(env, ctx, gen)
			if err != nil {
				return nil, nil, err
			}

			if ok {
				gen.AddConstant(constVal)
				init = constVal
			} else {
				var v []ssa.Value
				block, v, err = ast.Init.SSA(block, ctx, gen)
				if err != nil {
					return nil, nil, err
				}
				if len(v) != 1 {
					return nil, nil, ctx.Errorf(ast,
						"multiple-value %s used in single-value context",
						ast.Init)
				}
				init = v[0]
			}
		}

		if typeInfo.Undefined() {
			typeInfo = init.Type
		}
		if !typeInfo.Concrete() {
			typeInfo.Bits = init.Type.Bits
			typeInfo.SetConcrete(true)
		}
		if !typeInfo.CanAssignConst(init.Type) {
			return nil, nil, ctx.Errorf(ast,
				"cannot use %s (type %s) as type %s in assignment",
				init, init.Type, typeInfo)
		}

		lValue := gen.NewVal(n, typeInfo, ctx.Scope())
		block.Bindings.Define(lValue, nil)

		// Constant init values can be shared between different
		// instances so let's move the init to the new variable value.
		block.AddInstr(ssa.NewMovInstr(init, lValue))
	}
	return block, nil, nil
}

func initValue(typeInfo types.Info) (interface{}, error) {
	switch typeInfo.Type {
	case types.TBool:
		return false, nil
	case types.TInt, types.TUint:
		return int64(0), nil
	case types.TString:
		return "", nil
	case types.TStruct:
		var init []interface{}
		for _, field := range typeInfo.Struct {
			fieldInit, err := initValue(field.Type)
			if err != nil {
				return nil, err
			}
			init = append(init, fieldInit)
		}
		return init, nil
	case types.TArray, types.TSlice:
		elInit, err := initValue(*typeInfo.ElementType)
		if err != nil {
			return nil, err
		}
		init := make([]interface{}, typeInfo.ArraySize)
		for i := types.Size(0); i < typeInfo.ArraySize; i++ {
			init[i] = elInit
		}
		return init, nil
	default:
		return nil, fmt.Errorf("unsupported variable type: %s", typeInfo.Type)
	}
}

// SSA implements the compiler.ast.AST.SSA for assignment expressions.
func (ast *Assign) SSA(block *ssa.Block, ctx *Codegen,
	gen *ssa.Generator) (*ssa.Block, []ssa.Value, error) {

	var values []ssa.Value

	for _, expr := range ast.Exprs {
		// Check if init value is constant.
		env := NewEnv(block)
		constVal, ok, err := expr.Eval(env, ctx, gen)
		if err != nil {
			return nil, nil, err
		}
		if ok {
			gen.AddConstant(constVal)
			values = append(values, constVal)
		} else {
			var v []ssa.Value
			block, v, err = expr.SSA(block, ctx, gen)
			if err != nil {
				return nil, nil, err
			}
			if len(v) == 0 {
				return nil, nil, ctx.Errorf(expr, "%s used as value", expr)
			}
			values = append(values, v...)
		}
	}
	if len(ast.LValues) != len(values) {
		return nil, nil, ctx.Errorf(ast,
			"assignment mismatch: %d variables but %d value",
			len(values), len(ast.LValues))
	}

	var defined bool

	for idx, lvalue := range ast.LValues {
		rv := values[idx]
		switch lv := lvalue.(type) {
		case *VariableRef:
			lrv, _, df, err := ctx.LookupVar(block, gen, block.Bindings, lv)
			if err != nil {
				if !ast.Define || !df {
					// Not := or lvalue can't be defined.
					return nil, nil, ctx.Errorf(lv,
						"a non-name %s on left side of :=", lv)
				}
				// Defining lvalue.
				if !rv.Type.Concrete() {
					return nil, nil, ctx.Errorf(ast,
						"unspecified size for type %v", rv.Type)
				}
				lValue := gen.NewVal(lv.Name.Name, rv.Type, ctx.Scope())
				if rv.Type.Type == types.TPtr {
					lValue.PtrInfo = rv.PtrInfo
				}
				defined = true
				block.Bindings.Define(lValue, &rv)
				block.AddInstr(ssa.NewMovInstr(rv, lValue))
				continue
			}

			err = lrv.Set(rv)
			if err != nil {
				return nil, nil, ctx.Error(lvalue, err.Error())
			}

		case *Index:
			if ast.Define {
				return nil, nil, ctx.Errorf(ast,
					"a non-name %s on left side of :=", lv)
			}
			var err error
			var v []ssa.Value
			var indices []arrayIndex
			var lrv *LRValue
			idx := lv

			for lrv == nil {
				block, v, err = idx.Index.SSA(block, ctx, gen)
				if err != nil {
					return nil, nil, err
				}
				if len(v) != 1 {
					return nil, nil, ctx.Errorf(idx.Index, "invalid index")
				}
				index, err := v[0].ConstInt()
				if err != nil {
					return nil, nil, ctx.Error(idx.Index, err.Error())
				}
				indices = append(indices, arrayIndex{
					i:   index,
					ast: idx.Index,
				})
				switch i := idx.Expr.(type) {
				case *Index:
					idx = i

				case *VariableRef:
					lrv, _, _, err = ctx.LookupVar(block, gen,
						block.Bindings, i)
					if err != nil {
						return nil, nil, err
					}

				default:
					return nil, nil, ctx.Errorf(idx.Expr,
						"invalid operation: cannot index %v (%T)",
						idx.Expr, idx.Expr)

				}
			}
			slices.Reverse(indices)

			lrv = lrv.Indirect()
			t := lrv.ValueType()
			var offset types.Size

			for _, index := range indices {
				if !t.Type.Array() {
					return nil, nil, ctx.Errorf(index.ast,
						"setting elements of non-array %s (%s)", lv.Expr, t)
				}
				if index.i >= t.ArraySize {
					return nil, nil, ctx.Errorf(index.ast,
						"invalid array index %d (out of bounds for %d-element array)",
						index.i, t.ArraySize)
				}
				offset += index.i * t.ElementType.Bits
				t = *t.ElementType
			}

			if !ssa.CanAssign(t, rv) {
				return nil, nil, ctx.Errorf(lvalue,
					"cannot assign %v to variable of type %v", rv.Type, t)
			}

			val := gen.AnonVal(lrv.ValueType())
			fromConst := gen.Constant(int64(offset), types.Undefined)
			toConst := gen.Constant(int64(offset+t.Bits), types.Undefined)
			block.AddInstr(ssa.NewAmovInstr(rv, lrv.RValue(), fromConst,
				toConst, val))

			err = lrv.Set(val)
			if err != nil {
				return nil, nil, ctx.Error(lvalue, err.Error())
			}

		case *Unary:
			if ast.Define {
				return nil, nil, ctx.Errorf(ast,
					"a non-name %s on left side of :=", lv)
			}
			if lv.Type != UnaryPtr {
				return nil, nil, ctx.Errorf(ast, "cannot assign to %s", lv)
			}
			switch ptr := lv.Expr.(type) {
			case *VariableRef:
				b, ok := block.Bindings.Get(ptr.Name.Name)
				if !ok {
					return nil, nil, ctx.Errorf(ast, "undefined: %s", ptr.Name)
				}

				if b.Type.Type != types.TPtr {
					return nil, nil, ctx.Errorf(ast,
						"cannot assign non-pointer: %s", ptr.Name)
				}
				v := b.Value(block, gen)
				dstName := v.PtrInfo.Name
				dstType := v.PtrInfo.ContainerType
				dstScope := v.PtrInfo.Scope
				dstBindings := v.PtrInfo.Bindings
				b, ok = dstBindings.Get(dstName)
				if !ok {
					return nil, nil, ctx.Errorf(ast, "undefined: %s", ptr.Name)
				}

				lValue := gen.NewVal(dstName, dstType, dstScope)
				if v.Type.CanAssignConst(rv.Type) {
					// Pointer to value type.
					block.AddInstr(ssa.NewMovInstr(rv, lValue))
				} else if v.Type.ElementType.CanAssignConst(rv.Type) {
					// Pointer to element of value type.
					from := int64(v.PtrInfo.Offset)
					to := from + int64(v.Type.ElementType.Bits)
					fromConst := gen.Constant(from, types.Undefined)
					toConst := gen.Constant(to, types.Undefined)

					bv := b.Value(block, gen)

					block.AddInstr(ssa.NewAmovInstr(rv,
						bv, fromConst, toConst, lValue))
				} else {
					return nil, nil, ctx.Errorf(ast,
						"can't assign %s with value of type %s",
						lValue.Type.ElementType, rv.Type)
				}
				err := dstBindings.Set(lValue, nil)
				if err != nil {
					return nil, nil, ctx.Error(ast, err.Error())
				}

			default:
				return nil, nil, ctx.Errorf(ast,
					"assignment to pointer to %T not supported", ptr)
			}

		default:
			return nil, nil, ctx.Errorf(ast, "cannot assign to %s (%T)", lv, lv)
		}
	}
	if ast.Define && !defined {
		return nil, nil, ctx.Errorf(ast, "no new variables on left side of :=")
	}

	return block, values, nil
}

type arrayIndex struct {
	i   types.Size
	ast AST
}

func (i arrayIndex) String() string {
	return fmt.Sprintf("%d", i.i)
}

// SSA implements the compiler.ast.AST.SSA for if statements.
func (ast *If) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	env := NewEnv(block)
	constVal, ok, err := ast.Expr.Eval(env, ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	if ok {
		block.Bindings = env.Bindings
		val, ok := constVal.ConstValue.(bool)
		if !ok {
			return nil, nil, ctx.Errorf(ast.Expr,
				"condition is not boolean expression")
		}
		if val {
			return ast.True.SSA(block, ctx, gen)
		} else if ast.False != nil {
			return ast.False.SSA(block, ctx, gen)
		}
		return block, nil, nil
	}

	block, e, err := ast.Expr.SSA(block, ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	if len(e) == 0 {
		return nil, nil, ctx.Errorf(ast.Expr, "%s used as value", ast.Expr)
	} else if len(e) > 1 {
		return nil, nil, ctx.Errorf(ast.Expr,
			"multiple-value %s used in single-value context", ast.Expr)
	}
	if e[0].Type.Type != types.TBool {
		return nil, nil, ctx.Errorf(ast.Expr,
			"non-bool %s (type %s) used as if condition", ast.Expr, e[0].Type)
	}

	block.BranchCond = e[0]

	// Branch.
	tBlock := gen.BranchBlock(block)

	// True branch.
	tNext, _, err := ast.True.SSA(tBlock, ctx, gen)
	if err != nil {
		return nil, nil, err
	}

	// False (else) branch.
	if ast.False == nil {
		// No else branch.
		if tNext.Dead {
			// True branch terminated.
			tNext = gen.NextBlock(block)
		} else {
			tNext.Bindings = tNext.Bindings.Merge(e[0], block.Bindings)
			block.SetNext(tNext)
		}

		return tNext, nil, nil
	}

	fBlock := gen.NextBlock(block)

	fNext, _, err := ast.False.SSA(fBlock, ctx, gen)
	if err != nil {
		return nil, nil, err
	}

	if fNext.Dead && tNext.Dead {
		// Both branches terminate.
		next := gen.Block()
		next.Dead = true
		return next, nil, nil
	} else if fNext.Dead {
		// False-branch terminates.
		return tNext, nil, nil
	} else if tNext.Dead {
		// True-branch terminates.
		return fNext, nil, nil
	}

	// Both branches continue.

	next := gen.Block()
	tNext.SetNext(next)

	fNext.SetNext(next)

	next.Bindings = tNext.Bindings.Merge(e[0], fNext.Bindings)

	return next, nil, nil
}

// SSA implements the compiler.ast.AST.SSA for call expressions.
func (ast *Call) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	// Generate call values.

	var callValues [][]ssa.Value
	var v []ssa.Value
	var err error

	env := NewEnv(block)

	for _, expr := range ast.Exprs {
		constVal, ok, err := expr.Eval(env, ctx, gen)
		if err != nil {
			return nil, nil, err
		}
		if ok {
			gen.AddConstant(constVal)
			v = []ssa.Value{constVal}
		} else {
			block, v, err = expr.SSA(block, ctx, gen)
			if err != nil {
				return nil, nil, err
			}
		}
		callValues = append(callValues, v)
	}

	// Resolve called.
	called, err := ctx.LookupFunc(block, ast.Ref)
	if err != nil {
		return nil, nil, err
	}
	if called == nil {
		// Check builtin functions.
		bi, ok := builtins[ast.Ref.Name.Name]
		if ok {
			// Flatten arguments.
			var args []ssa.Value
			for _, arg := range callValues {
				args = append(args, arg...)
			}
			return bi.SSA(block, ctx, gen, args, ast.Location())
		}

		// Resolve name as type.
		typeName := &TypeInfo{
			Point: ast.Point,
			Type:  TypeName,
			Name:  ast.Ref.Name,
		}
		typeInfo, err := typeName.Resolve(NewEnv(block), ctx, gen)
		if err != nil {
			return nil, nil, err
		}
		if len(callValues) != 1 {
			return nil, nil, ctx.Errorf(ast, "undefined: %s", ast.Ref)
		}
		if len(callValues[0]) == 0 {
			return nil, nil, ctx.Errorf(ast.Exprs[0],
				"%s used as value", ast.Exprs[0])
		}
		if len(callValues[0]) > 1 {
			return nil, nil, ctx.Errorf(ast.Exprs[0],
				"multiple-value %s in single-value context", ast.Exprs[0])
		}
		cv := callValues[0][0]

		// Cast value to type.
		return ast.cast(block, ctx, gen, typeInfo, cv)
	}

	var args []ssa.Value

	if len(callValues) == 0 {
		if len(called.Args) != 0 {
			return nil, nil, ast.error(ctx, "not enough arguments",
				callValues, called.Args)
		}
	} else if len(callValues) == 1 {
		if len(callValues[0]) < len(called.Args) {
			return nil, nil, ast.error(ctx, "not enough arguments",
				callValues, called.Args)
		} else if len(callValues[0]) > len(called.Args) {
			return nil, nil, ast.error(ctx, "too many arguments",
				callValues, called.Args)
		}
		args = callValues[0]
	} else {
		if len(callValues) < len(called.Args) {
			return nil, nil, ast.error(ctx, "not enough arguments",
				callValues, called.Args)
		} else if len(callValues) > len(called.Args) {
			return nil, nil, ast.error(ctx, "too many arguments",
				callValues, called.Args)
		} else {
			for idx, ca := range callValues {
				expr := ast.Exprs[idx]
				if len(ca) == 0 {
					return nil, nil, ctx.Errorf(expr, "%s used as value", expr)
				} else if len(ca) > 1 {
					return nil, nil, ctx.Errorf(expr,
						"multiple-value %s in single-value context", expr)
				}
				args = append(args, ca[0])
			}
		}
	}

	// Return block.
	rblock := gen.Block()
	rblock.Bindings = block.Bindings.Clone()

	ctx.PushCompilation(gen.Block(), gen.Block(), rblock, called)

	// Define arguments.
	for idx, arg := range called.Args {
		typeInfo, err := arg.Type.Resolve(NewEnv(block), ctx, gen)
		if err != nil {
			return nil, nil, ctx.Errorf(arg, "invalid argument type: %s", err)
		}
		// Instantiate argument types of template functions.
		if !typeInfo.Concrete() && !typeInfo.Instantiate(args[idx].Type) {
			return nil, nil, ctx.Errorf(ast.Exprs[idx],
				"cannot use %v as type %s in argument to %s",
				args[idx].Type, typeInfo, called.Name)
		}
		if !ssa.CanAssign(typeInfo, args[idx]) {
			return nil, nil, ctx.Errorf(ast,
				"cannot use %v as type %s in argument to %s",
				args[idx].Type, typeInfo, called.Name)
		}
		a := gen.NewVal(arg.Name, args[idx].Type, ctx.Scope())
		a.PtrInfo = args[idx].PtrInfo
		ctx.Start().Bindings.Define(a, &args[idx])

		block.AddInstr(ssa.NewMovInstr(args[idx], a))
	}
	// This for method calls.
	if called.This != nil {
		typeInfo, err := called.This.Type.Resolve(env, ctx, gen)
		if err != nil {
			return nil, nil, err
		}
		var this ssa.Value
		var bindings *ssa.Bindings

		// First check block bindings.
		b, ok := block.Bindings.Get(ast.Ref.Name.Package)
		if ok {
			bindings = block.Bindings
		} else {
			// Check names in the current package.
			b, ok = ctx.Package.Bindings.Get(ast.Ref.Name.Package)
			if ok {
				bindings = ctx.Package.Bindings
			} else {
				return nil, nil, ctx.Errorf(ast, "undefined: %s",
					ast.Ref.Name.Package)
			}
		}

		// XXX only one level of pointers.
		if typeInfo.Type == types.TPtr && b.Type.Type != types.TPtr {
			// Pointer receiver.
			this = gen.AnonVal(types.Info{
				Type:        types.TPtr,
				IsConcrete:  true,
				Bits:        b.Type.Bits,
				MinBits:     b.Type.Bits,
				ElementType: &b.Type,
			})
			this.PtrInfo = &ssa.PtrInfo{
				Name:          ast.Ref.Name.Package,
				Bindings:      bindings,
				Scope:         b.Scope,
				ContainerType: b.Type,
			}
		} else {
			// Value receiver.
			this = b.Value(block, gen)
		}
		a := gen.NewVal(called.This.Name, typeInfo, ctx.Scope())
		a.PtrInfo = this.PtrInfo
		if a.TypeCompatible(this) == nil {
			return nil, nil, ctx.Errorf(ast,
				"cannot use %v as type %s in receiver to %s",
				this.Type, typeInfo, called.Name)
		}
		ctx.Start().Bindings.Define(a, &this)
		block.AddInstr(ssa.NewMovInstr(this, a))
	}

	// Instantiate called function.
	_, returnValues, err := called.SSA(ctx.Start(), ctx, gen)
	if err != nil {
		return nil, nil, err
	}

	block.SetNext(ctx.Start())

	rblock.Bindings = block.Bindings.Clone()

	ctx.Return().SetNext(rblock)
	block = rblock

	ctx.PopCompilation()

	return block, returnValues, nil
}

func (ast *Call) cast(block *ssa.Block, ctx *Codegen, gen *ssa.Generator,
	typeInfo types.Info, cv ssa.Value) (*ssa.Block, []ssa.Value, error) {

	if !typeInfo.Concrete() {
		if !cv.Type.Concrete() {
			return nil, nil, ctx.Errorf(ast.Ref,
				"casting to non-concrete type %s", ast.Ref)
		}
		typeInfo.Bits = cv.Type.Bits
		typeInfo.SetConcrete(true)
	}

	var t ssa.Value

castTargetType:
	switch typeInfo.Type {
	case types.TString:
		switch cv.Type.Type {
		case types.TUint, types.TInt:
			if cv.Type.MinBits > 8 {
				ctx.Warningf(ast,
					"cast from %v to %v truncates value of %v bits",
					cv.Type, typeInfo.Type, cv.Type.MinBits)
			}
			typeInfo.Bits = 8
			typeInfo.SetConcrete(true)

		case types.TString:
			typeInfo.Bits = cv.Type.Bits
			typeInfo.SetConcrete(true)

		case types.TArray, types.TSlice:
			switch cv.Type.ElementType.Type {
			case types.TUint:
				if cv.Type.ElementType.Bits != 8 {
					break castTargetType
				}
				typeInfo.Bits = cv.Type.ElementType.Bits * cv.Type.ArraySize
				typeInfo.SetConcrete(true)

			default:
				break castTargetType
			}

		default:
			break castTargetType
		}
		t = gen.AnonVal(typeInfo)

	default:
		t = gen.AnonVal(typeInfo)
	}
	if t.Type.Undefined() {
		return nil, nil, ctx.Errorf(ast.Exprs[0], "cast from %v to %v",
			cv.Type, typeInfo)
	}

	if cv.Type.Type == types.TInt && typeInfo.Type == types.TInt &&
		typeInfo.Bits > cv.Type.Bits {
		// The src and dst are signed integers and we are casting to
		// bigger bit size. Use sign-extension version smov.
		block.AddInstr(ssa.NewSmovInstr(cv, t))
	} else {
		block.AddInstr(ssa.NewMovInstr(cv, t))
	}

	return block, []ssa.Value{t}, nil
}

func (ast *Call) error(ctx *Codegen, message string, have [][]ssa.Value,
	want []*Variable) error {

	message += fmt.Sprintf(" in call to %s", ast.Ref)
	message += "\n\thave ("
	switch len(have) {
	case 0:

	case 1:
		for i, v := range have[0] {
			if i > 0 {
				message += ", "
			}
			message += v.Type.Type.String()
		}

	default:
		for i, vi := range have {
			if i > 0 {
				message += ", "
			}
			if len(vi) > 0 {
				message += "("
			}
			for j, vj := range vi {
				if j > 0 {
					message += ", "
				}
				message += vj.Type.Type.String()
			}
			if len(vi) > 0 {
				message += ")"
			}
		}
	}
	message += ")\n\twant ("
	for i, v := range want {
		if i > 0 {
			message += ", "
		}
		message += v.Type.String()
	}
	return ctx.Errorf(ast, "%s)", message)
}

// SSA implements the compiler.ast.AST.SSA.
func (ast *ArrayCast) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	// Value being cast.

	var v []ssa.Value
	var err error

	env := NewEnv(block)
	constVal, ok, err := ast.Expr.Eval(env, ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	if ok {
		gen.AddConstant(constVal)
		v = []ssa.Value{constVal}
	} else {
		block, v, err = ast.Expr.SSA(block, ctx, gen)
		if err != nil {
			return nil, nil, err
		}
	}
	if len(v) == 0 {
		return nil, nil, ctx.Errorf(ast.Expr, "%s used as value", ast.Expr)
	}
	if len(v) > 1 {
		return nil, nil, ctx.Errorf(ast.Expr,
			"multiple-value %s used in single-value context", ast.Expr)
	}
	cv := v[0]

	// Type to cast.
	typeInfo, err := ast.TypeInfo.Resolve(env, ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	if !typeInfo.Type.Array() {
		return nil, nil, ctx.Errorf(ast.Expr, "array cast to non-array type %v",
			typeInfo)
	}

	var t ssa.Value

	switch cv.Type.Type {
	case types.TString:
		if cv.Type.Bits%8 != 0 {
			return nil, nil, ctx.Errorf(ast.Expr, "invalid string length %v",
				cv.Type.Bits)
		}
		chars := cv.Type.Bits / 8
		et := typeInfo.ElementType
		if et.Bits != 8 || et.Type != types.TUint {
			return nil, nil, ctx.Errorf(ast.Expr, "cast from %v to %v",
				cv.Type, ast.TypeInfo)
		}

		if typeInfo.Concrete() {
			if typeInfo.ArraySize != chars || typeInfo.Bits != cv.Type.Bits {
				return nil, nil, ctx.Errorf(ast.Expr, "cast from %v to %v",
					cv.Type, ast.TypeInfo)
			}
		} else {
			typeInfo.Bits = cv.Type.Bits
			typeInfo.MinBits = typeInfo.Bits
			typeInfo.ArraySize = chars
			typeInfo.SetConcrete(true)
		}

		t = gen.AnonVal(typeInfo)

	default:
		return nil, nil, ctx.Errorf(ast.Expr, "cast from %v to %v",
			cv.Type, ast.TypeInfo)
	}

	block.AddInstr(ssa.NewMovInstr(cv, t))

	return block, []ssa.Value{t}, nil
}

// SSA implements the compiler.ast.AST.SSA for return statements.
func (ast *Return) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	f := ctx.Func()
	if f == nil {
		return nil, nil, ctx.Errorf(ast, "return outside function")
	}
	if ast.AutoGenerated && len(f.Return) > 0 {
		return nil, nil, ctx.Errorf(ast,
			"missing return at the end of function")
	}
	info := &ReturnInfo{
		Return: ast,
	}
	f.Returns = append(f.Returns, info)

	var exprs []AST
	var rValues [][]ssa.Value
	var result []ssa.Value
	var v []ssa.Value
	var err error

	// Compute return values.
	if f.NamedReturn && len(ast.Exprs) == 0 {
		for _, ret := range f.Return {
			expr := &VariableRef{
				Point: ret.Point,
				Name: Identifier{
					Name: ret.Name,
				},
			}
			exprs = append(exprs, expr)
			block, v, err = expr.SSA(block, ctx, gen)
			if err != nil {
				return nil, nil, err
			}
			rValues = append(rValues, v)
		}
	} else {
		for _, expr := range ast.Exprs {
			exprs = append(exprs, expr)
			block, v, err = expr.SSA(block, ctx, gen)
			if err != nil {
				return nil, nil, err
			}
			rValues = append(rValues, v)
		}
	}
	if len(rValues) == 0 {
		if len(f.Return) != 0 {
			return nil, nil, ast.error(ctx, "not enough arguments to return",
				rValues, f.Return)
		}
	} else if len(rValues) == 1 {
		if len(rValues[0]) < len(f.Return) {
			return nil, nil, ast.error(ctx, "not enough arguments to return",
				rValues, f.Return)
		} else if len(rValues[0]) > len(f.Return) {
			return nil, nil, ast.error(ctx, "too many aruments to return",
				rValues, f.Return)
		}
		result = rValues[0]
	} else {
		if len(rValues) < len(f.Return) {
			return nil, nil, ast.error(ctx, "not enough arguments to return",
				rValues, f.Return)
		} else if len(rValues) > len(f.Return) {
			return nil, nil, ast.error(ctx, "too many aruments to return",
				rValues, f.Return)
		} else {
			if len(exprs) != len(rValues) {
				return nil, nil, ctx.Errorf(ast,
					"invalid number of return values: got %d, expected %d",
					exprs, len(rValues))
			}
			for idx, rv := range rValues {
				expr := exprs[idx]
				if len(rv) == 0 {
					return nil, nil, ctx.Errorf(expr, "%s used as value", expr)
				} else if len(rv) > 1 {
					return nil, nil, ctx.Errorf(expr,
						"multiple-value %s in single-value context", expr)
				}
				result = append(result, rv[0])
			}
		}
	}

	for idx, r := range f.Return {
		typeInfo, err := r.Type.Resolve(NewEnv(block), ctx, gen)
		if err != nil {
			return nil, nil, ctx.Errorf(r, "invalid return type: %s", err)
		}
		// Instantiate result values for template functions.
		if !typeInfo.Concrete() && !typeInfo.Instantiate(result[idx].Type) {
			return nil, nil, ctx.Errorf(ast,
				"invalid value %v for return value %v",
				result[idx].Type, typeInfo)
		}
		info.Types = append(info.Types, typeInfo)
		v := gen.NewVal(r.Name, typeInfo, ctx.Scope())
		if result[idx].Type.Type == types.TPtr {
			v.PtrInfo = result[idx].PtrInfo
		}

		// The native() returns undefined values.
		if result[idx].Type.Undefined() {
			result[idx].Type.Type = typeInfo.Type
		}

		if !ssa.CanAssign(typeInfo, result[idx]) {
			return nil, nil, ctx.Errorf(ast,
				"invalid value %v for return value %v",
				result[idx].Type, v.Type)
		}

		block.AddInstr(ssa.NewMovInstr(result[idx], v))
		err = block.Bindings.Set(v, nil)
		if err != nil {
			return nil, nil, ctx.Error(ast, err.Error())
		}
	}

	block.SetNext(ctx.Return())
	block.Dead = true

	return block, nil, nil
}

func (ast *Return) error(ctx *Codegen, message string, have [][]ssa.Value,
	want []*Variable) error {

	message += "\n\thave ("
	switch len(have) {
	case 0:

	case 1:
		for i, v := range have[0] {
			if i > 0 {
				message += ", "
			}
			message += v.Type.Type.String()
		}

	default:
		for i, vi := range have {
			if i > 0 {
				message += ", "
			}
			if len(vi) > 0 {
				message += "("
			}
			for j, vj := range vi {
				if j > 0 {
					message += ", "
				}
				message += vj.Type.Type.String()
			}
			if len(vi) > 0 {
				message += ")"
			}
		}
	}
	message += ")\n\twant ("
	for i, v := range want {
		if i > 0 {
			message += ", "
		}
		message += v.Type.String()
	}
	return ctx.Errorf(ast, "%s)", message)
}

// SSA implements the compiler.ast.AST.SSA for for statements.
func (ast *For) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	// Use the same env for the whole for-loop unrolling.
	env := NewEnv(block)

	// Init loop.
	if ast.Init != nil {
		_, ok, err := ast.Init.Eval(env, ctx, gen)
		if err != nil {
			return nil, nil, err
		}
		if !ok {
			return nil, nil, ctx.Errorf(ast.Init,
				"init statement is not compile-time constant: %s", ast.Init)
		}
	}

	// Expand body as long as condition is true.
	for i := 0; ; i++ {
		if i >= gen.Params.MaxLoopUnroll {
			return nil, nil, ctx.Errorf(ast,
				"for-loop unroll limit exceeded: %d", i)
		}
		constVal, ok, err := ast.Cond.Eval(env, ctx, gen)
		if err != nil {
			return nil, nil, err
		}
		if !ok {
			return nil, nil, ctx.Errorf(ast.Cond,
				"condition is not compile-time constant: %s", ast.Cond)
		}
		val, ok := constVal.ConstValue.(bool)
		if !ok {
			return nil, nil, ctx.Errorf(ast.Cond,
				"condition is not boolean expression")
		}
		if !val {
			// Loop completed.
			break
		}

		// Expand block.
		block.Bindings = env.Bindings
		block, _, err = ast.Body.SSA(block, ctx, gen)
		if err != nil {
			return nil, nil, err
		}
		env.Bindings = block.Bindings

		// Increment.
		if ast.Inc != nil {
			env = NewEnv(block)
			_, ok, err = ast.Inc.Eval(env, ctx, gen)
			if err != nil {
				return nil, nil, err
			}
			if !ok {
				return nil, nil, ctx.Errorf(ast.Init,
					"increment statement is not compile-time constant: %s",
					ast.Inc)
			}
		}
	}

	// Store env bindings to block after for-loop unroll.
	block.Bindings = env.Bindings

	return block, nil, nil
}

// SSA implements the compiler.ast.AST.SSA for for statements.
func (ast *ForRange) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	if len(ast.ExprList) > 2 {
		return nil, nil, ctx.Errorf(ast.ExprList[2],
			"range clause permits at most two iteration variables")
	}
	var idxVar, valVar string
	for idx, expr := range ast.ExprList {
		ref, ok := expr.(*VariableRef)
		if !ok {
			return nil, nil, ctx.Errorf(expr,
				"range clause supports only identifiers")
		}
		name := ref.Name.Name
		if name == "_" {
			name = ""
		}
		switch idx {
		case 0:
			idxVar = name
		case 1:
			valVar = name
		}
	}

	var v []ssa.Value
	var err error

	block, v, err = ast.Expr.SSA(block, ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	if len(v) == 0 {
		return nil, nil, ctx.Errorf(ast.Expr, "%s used as value", ast.Expr)
	}
	if len(v) > 1 {
		return nil, nil, ctx.Errorf(ast.Expr,
			"multiple-value %s used in single-value context", ast.Expr)
	}
	values := v[0]

	var count int
	var it types.Info
	var ptrInfo ssa.PtrInfo
	if values.Type.Type == types.TPtr {
		it = *values.Type.ElementType
		ptrInfo = *values.PtrInfo
		b, ok := ptrInfo.Bindings.Get(ptrInfo.Name)
		if !ok {
			return nil, nil, ctx.Errorf(ast.Expr, "undefined: %s", ptrInfo.Name)
		}
		values = b.Value(block, gen)
	} else {
		it = values.Type
	}

	switch it.Type {
	case types.TArray, types.TSlice:
		count = int(values.Type.ArraySize)
		it = *it.ElementType
	default:
		return nil, nil, ctx.Errorf(ast.Expr,
			"cannot range over %v (%v)", ast.Expr, it)
	}
	if !it.Concrete() {
		return nil, nil, ctx.Errorf(ast.Expr,
			"cannot range over unspecified element type %v", it)
	}

	// Expand body for each element in value.
	for i := 0; i < count; i++ {
		// Index variable.
		if len(idxVar) > 0 {
			idxConst := gen.Constant(int64(i), types.Undefined)
			var lValue ssa.Value
			b, ok := block.Bindings.Get(idxVar)
			if ast.Def {
				if ok {
					lValue = gen.NewVal(b.Name, b.Type, ctx.Scope())
				} else {
					lValue = gen.NewVal(idxVar, idxConst.Type, ctx.Scope())
					block.Bindings.Define(lValue, nil)
				}
			} else {
				if !ok {
					return nil, nil, ctx.Errorf(ast.ExprList[0],
						"undefined: %s", idxVar)
				}
				lValue = gen.NewVal(idxVar, idxConst.Type, ctx.Scope())
			}
			block.AddInstr(ssa.NewMovInstr(idxConst, lValue))
			err = block.Bindings.Set(lValue, &idxConst)
			if err != nil {
				return nil, nil, ctx.Error(ast.ExprList[0], err.Error())
			}
		}

		// Value variable.
		if len(valVar) > 0 {
			r := gen.AnonVal(it)

			switch values.Type.Type {
			case types.TArray, types.TSlice:
				from := int64(types.Size(i)*it.Bits + ptrInfo.Offset)
				to := int64(types.Size(i+1)*it.Bits + ptrInfo.Offset)

				if to > from {
					fromConst := gen.Constant(from, types.Undefined)
					toConst := gen.Constant(to, types.Undefined)
					block.AddInstr(ssa.NewSliceInstr(values, fromConst, toConst,
						r))
				}

			default:
				return nil, nil, ctx.Errorf(ast.Expr,
					"cannot range over %v (%v)", ast.Expr, values.Type)
			}

			var lValue ssa.Value
			b, ok := block.Bindings.Get(valVar)
			if ast.Def {
				if ok {
					lValue = gen.NewVal(b.Name, b.Type, ctx.Scope())
				} else {
					lValue = gen.NewVal(valVar, r.Type, ctx.Scope())
					block.Bindings.Define(lValue, nil)
				}
			} else {
				if !ok {
					return nil, nil, ctx.Errorf(ast.ExprList[1],
						"undefined: %s", valVar)
				}
				lValue = gen.NewVal(valVar, r.Type, ctx.Scope())
			}

			block.AddInstr(ssa.NewMovInstr(r, lValue))
			err = block.Bindings.Set(lValue, &r)
			if err != nil {
				return nil, nil, ctx.Error(ast.ExprList[1], err.Error())
			}
		}

		// Expand block.
		block, _, err = ast.Body.SSA(block, ctx, gen)
		if err != nil {
			return nil, nil, err
		}
	}

	return block, nil, nil
}

func isPowerOf2(ast AST, env *Env, ctx *Codegen, gen *ssa.Generator) (
	int64, bool) {

	v, ok, err := ast.Eval(env, ctx, gen)
	if err != nil || !ok {
		return 0, false
	}
	switch val := v.ConstValue.(type) {
	case int64:
		i := val
		var count int
		for i > 0 {
			if i&1 == 1 {
				count++
			}
			i >>= 1
		}
		return val, count <= 1

	default:
		return 0, false
	}
}

// SSA implements the compiler.ast.AST.SSA for binary expressions.
func (ast *Binary) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	// Check constant folding.
	env := NewEnv(block)
	constVal, ok, err := ast.Eval(env, ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	if ok {
		if ctx.Verbose && debugConstFold {
			fmt.Printf("ConstFold: %v %s %v => %v\n",
				ast.Left, ast.Op, ast.Right, constVal)
		}
		gen.AddConstant(constVal)
		return block, []ssa.Value{constVal}, nil
	}
	lPow2, lConst := isPowerOf2(ast.Left, env, ctx, gen)
	rPow2, rConst := isPowerOf2(ast.Right, env, ctx, gen)
	if lConst || rConst {
		switch ast.Op {
		case BinaryMul:
			// Multiplication is commutative.
			if rConst {
				block, l, err := ast.value(env, ast.Left, block, ctx, gen)
				if err != nil {
					return nil, nil, err
				}
				return ast.constMult(l, rPow2, block, ctx, gen)
			}
			if lConst {
				block, r, err := ast.value(env, ast.Right, block, ctx, gen)
				if err != nil {
					return nil, nil, err
				}
				return ast.constMult(r, lPow2, block, ctx, gen)
			}

		case BinaryAdd:
			if rConst && rPow2 == 0 {
				block, l, err := ast.value(env, ast.Left, block, ctx, gen)
				if err != nil {
					return nil, nil, err
				}
				return block, []ssa.Value{l}, nil
			}
			if lConst && lPow2 == 0 {
				block, r, err := ast.value(env, ast.Right, block, ctx, gen)
				if err != nil {
					return nil, nil, err
				}
				return block, []ssa.Value{r}, nil
			}

		case BinarySub:
			if rConst && rPow2 == 0 {
				block, l, err := ast.value(env, ast.Left, block, ctx, gen)
				if err != nil {
					return nil, nil, err
				}
				return block, []ssa.Value{l}, nil
			}

		case BinaryLshift, BinaryRshift:

		default:
			if false {
				if lConst {
					fmt.Printf(" - %v %s\n", lPow2, ast.Op)
				}
				if rConst {
					fmt.Printf(" - %s %v\n", ast.Op, rPow2)
				}
			}
		}
	}

	// Check that l and r are of same type.
	block, l, err := ast.value(env, ast.Left, block, ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	block, r, err := ast.value(env, ast.Right, block, ctx, gen)
	if err != nil {
		return nil, nil, err
	}

	// Resolve target type.
	resultType, err := ast.resultType(ctx, l, r)
	if err != nil {
		return nil, nil, err
	}
	t := gen.AnonVal(resultType)

	var instr ssa.Instr
	switch ast.Op {
	case BinaryMul:
		instr, err = ssa.NewMultInstr(l.Type, l, r, t)
	case BinaryDiv:
		instr, err = ssa.NewDivInstr(l.Type, l, r, t)
	case BinaryMod:
		instr, err = ssa.NewModInstr(l.Type, l, r, t)
	case BinaryLshift:
		instr = ssa.NewLshiftInstr(l, r, t)
	case BinaryRshift:
		if l.Type.Type == types.TInt {
			// Use sign-extension version srshift.
			instr = ssa.NewSrshiftInstr(l, r, t)
		} else {
			instr = ssa.NewRshiftInstr(l, r, t)
		}
	case BinaryBand:
		instr, err = ssa.NewBandInstr(l, r, t)
	case BinaryBclear:
		instr, err = ssa.NewBclrInstr(l, r, t)
	case BinaryAdd:
		instr, err = ssa.NewAddInstr(l.Type, l, r, t)
	case BinarySub:
		instr, err = ssa.NewSubInstr(l.Type, l, r, t)
	case BinaryBor:
		instr, err = ssa.NewBorInstr(l, r, t)
	case BinaryBxor:
		instr, err = ssa.NewBxorInstr(l, r, t)
	case BinaryEq:
		instr, err = ssa.NewEqInstr(l, r, t)
	case BinaryNeq:
		instr, err = ssa.NewNeqInstr(l, r, t)
	case BinaryLt:
		instr, err = ssa.NewLtInstr(l.Type, l, r, t)
	case BinaryLe:
		instr, err = ssa.NewLeInstr(l.Type, l, r, t)
	case BinaryGt:
		instr, err = ssa.NewGtInstr(l.Type, l, r, t)
	case BinaryGe:
		instr, err = ssa.NewGeInstr(l.Type, l, r, t)
	case BinaryAnd:
		instr, err = ssa.NewAndInstr(l, r, t)
	case BinaryOr:
		instr, err = ssa.NewOrInstr(l, r, t)
	default:
		fmt.Printf("%s %s %s\n", l, ast.Op, r)
		return nil, nil, ctx.Errorf(ast, "Binary.SSA: '%s' not implemented yet",
			ast.Op)
	}
	if err != nil {
		return nil, nil, err
	}

	block.AddInstr(instr)

	return block, []ssa.Value{t}, nil
}

func (ast *Binary) resultType(ctx *Codegen, l, r ssa.Value) (
	types.Info, error) {

	var resultType types.Info
	switch ast.Op {
	case BinaryMul, BinaryDiv, BinaryMod, BinaryBand, BinaryBclear,
		BinarySub, BinaryBor, BinaryBxor:
		superType := l.TypeCompatible(r)
		if superType == nil {
			return types.Undefined, ctx.Errorf(ast, "invalid types: %s %s %s",
				l.Type, ast.Op, r.Type)
		}
		resultType = *superType

	case BinaryAdd:
		// Binary addition is handled separately since we must handle
		// string and array concatenation.
		if l.Type.Type == types.TString && r.Type.Type == types.TString {
			resultType = l.Type
			resultType.Bits += r.Type.Bits
		} else if l.Type.Type.Array() && r.Type.Type.Array() &&
			l.Type.ElementType.Equal(*r.Type.ElementType) {
			if r.Type.Type == types.TSlice {
				resultType = r.Type
			} else {
				resultType = l.Type
			}
			resultType.Bits += r.Type.Bits
			resultType.ArraySize += r.Type.ArraySize
		} else {
			superType := l.TypeCompatible(r)
			if superType == nil {
				return types.Undefined,
					ctx.Errorf(ast, "invalid types: %s %s %s",
						l.Type, ast.Op, r.Type)
			}
			resultType = *superType
		}

	case BinaryLshift, BinaryRshift:
		if !l.IntegerLike() || !r.IntegerLike() {
			return types.Undefined, ctx.Errorf(ast, "invalid types: %s %s %s",
				l.Type, ast.Op, r.Type)
		}
		resultType = l.Type

	case BinaryLt, BinaryLe, BinaryGt, BinaryGe, BinaryEq, BinaryNeq,
		BinaryAnd, BinaryOr:
		resultType = types.Bool

	default:
		fmt.Printf("%s %s %s\n", l, ast.Op, r)
		return types.Undefined,
			ctx.Errorf(ast, "Binary.SSA: '%s' not implemented yet", ast.Op)
	}
	return resultType, nil
}

func (ast *Binary) value(env *Env, val AST, block *ssa.Block, ctx *Codegen,
	gen *ssa.Generator) (*ssa.Block, ssa.Value, error) {

	// Check if value is constant.
	v, c, err := val.Eval(env, ctx, gen)
	if err != nil {
		return block, v, err
	}
	if c {
		gen.AddConstant(v)
		return block, v, nil
	}

	block, arr, err := val.SSA(block, ctx, gen)
	if err != nil {
		return nil, ssa.Value{}, err
	}
	if len(arr) == 0 {
		return nil, ssa.Value{}, ctx.Errorf(val, "%s used as value", val)
	}
	if len(arr) > 1 {
		return nil, ssa.Value{}, ctx.Errorf(val,
			"multiple-value %s in single-value context", val)
	}
	return block, arr[0], nil
}

func (ast *Binary) constMult(v ssa.Value, c int64, block *ssa.Block,
	ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	if c == 0 {
		r := gen.Constant(c, v.Type)
		gen.AddConstant(r)
		return block, []ssa.Value{r}, nil
	} else if c == 1 {
		return block, []ssa.Value{v}, nil
	}

	var count int
	for c > 1 {
		count++
		c >>= 1
	}

	shift := gen.Constant(int64(count), types.Undefined)

	t := gen.AnonVal(v.Type)
	instr := ssa.NewLshiftInstr(v, shift, t)
	block.AddInstr(instr)

	return block, []ssa.Value{t}, nil
}

// SSA implements the compiler.ast.AST.SSA for unary expressions.
func (ast *Unary) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	constVal, ok, err := ast.Eval(NewEnv(block), ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	if ok {
		if ctx.Verbose && debugConstFold {
			fmt.Printf("ConstFold: %v => %v\n", ast, constVal)
		}
		gen.AddConstant(constVal)
		return block, []ssa.Value{constVal}, nil
	}

	switch ast.Type {
	case UnaryMinus:
		block, exprs, err := ast.Expr.SSA(block, ctx, gen)
		if err != nil {
			return nil, nil, err
		}
		if len(exprs) != 1 {
			return nil, nil, ctx.Errorf(ast,
				"multiple-value %s used in single-value context", ast.Expr)
		}
		expr := exprs[0]

		t := gen.AnonVal(expr.Type)
		switch expr.Type.Type {
		case types.TInt, types.TUint:
			zero := gen.Constant(int64(0), types.Undefined)
			gen.AddConstant(zero)
			instr, err := ssa.NewSubInstr(expr.Type, zero, expr, t)
			if err != nil {
				return nil, nil, err
			}
			block.AddInstr(instr)
			return block, []ssa.Value{t}, nil

		default:
			return nil, nil, ctx.Errorf(ast, "%s not supported", ast)
		}

	case UnaryNot:
		block, exprs, err := ast.Expr.SSA(block, ctx, gen)
		if err != nil {
			return nil, nil, err
		}
		if len(exprs) != 1 {
			return nil, nil, ctx.Errorf(ast,
				"multiple-value %s used in single-value context", ast.Expr)
		}
		expr := exprs[0]
		if expr.Type.Type != types.TBool {
			return nil, nil, ctx.Errorf(ast,
				"invalid operation: operator ! not defined on %v (%v)",
				ast.Expr, expr.Type)
		}
		t := gen.AnonVal(expr.Type)
		instr, err := ssa.NewNotInstr(expr, t)
		if err != nil {
			return nil, nil, err
		}
		block.AddInstr(instr)
		return block, []ssa.Value{t}, nil

	case UnaryAddr:
		switch v := ast.Expr.(type) {
		case *VariableRef:
			lrv, _, _, err := ctx.LookupVar(block, gen, block.Bindings, v)
			if err != nil {
				return nil, nil, ctx.Error(v, err.Error())
			}
			valueType := lrv.ValueType()

			t := gen.AnonVal(types.Info{
				Type:        types.TPtr,
				IsConcrete:  true,
				Bits:        valueType.Bits,
				MinBits:     valueType.MinBits,
				ElementType: &valueType,
			})
			bpi := lrv.BasePtrInfo()
			t.PtrInfo = &ssa.PtrInfo{
				Name:          bpi.Name,
				Scope:         bpi.Scope,
				Bindings:      bpi.Bindings,
				ContainerType: bpi.ContainerType,
				Offset:        valueType.Offset,
			}
			return block, []ssa.Value{t}, nil

		case *Index:
			lrv, ptrType, offset, err := ast.addrIndex(block, ctx, gen, v)
			if err != nil {
				return nil, nil, err
			}
			t := gen.AnonVal(types.Info{
				Type:        types.TPtr,
				IsConcrete:  true,
				Bits:        ptrType.Bits,
				MinBits:     ptrType.Bits,
				ElementType: ptrType,
			})
			t.PtrInfo = lrv.BasePtrInfo()
			t.PtrInfo.Offset += offset
			return block, []ssa.Value{t}, nil

		default:
			return nil, nil, ctx.Errorf(ast, "Unary.SSA: '%T' not supported", v)
		}

	default:
		return nil, nil, ctx.Errorf(ast, "Unary.SSA not implemented yet: %v",
			ast)
	}
}

func (ast *Unary) addrIndex(block *ssa.Block, ctx *Codegen, gen *ssa.Generator,
	index *Index) (
	lrv *LRValue, ptrType *types.Info, offset types.Size, err error) {

	switch indexed := index.Expr.(type) {
	case *VariableRef:
		lrv, _, _, err = ctx.LookupVar(block, gen, block.Bindings, indexed)
		if err != nil {
			err = ctx.Error(indexed, err.Error())
			return
		}
		vt := lrv.ValueType()
		if !vt.Type.Array() {
			return nil, nil, 0, ctx.Errorf(indexed,
				"invalid operation: %s (type %s does not support indexing)",
				index, ptrType)
		}
		ptrType = &vt

	case *Index:
		lrv, ptrType, offset, err = ast.addrIndex(block, ctx, gen, indexed)

	default:
		return nil, nil, 0,
			ctx.Errorf(ast, "&%s not supported (%T)", index, indexed)
	}

	var indices []ssa.Value
	block, indices, err = index.Index.SSA(block, ctx, gen)
	if err != nil {
		return
	}
	if len(indices) != 1 {
		return nil, nil, 0, ctx.Errorf(index, "invalid index")
	}
	var ival types.Size
	ival, err = indices[0].ConstInt()
	if err != nil {
		err = ctx.Errorf(index.Index, "%s", err)
		return
	}
	if ival < 0 || ival >= ptrType.ArraySize {
		return nil, nil, 0, ctx.Errorf(index.Index,
			"invalid array index %d (out of bounds for %d-element string)",
			ival, ptrType.ArraySize)
	}
	return lrv, ptrType.ElementType, offset + ival*ptrType.ElementType.Bits, nil
}

// SSA implements the compiler.ast.AST.SSA for slice expressions.
func (ast *Slice) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	block, exprs, err := ast.Expr.SSA(block, ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	if len(exprs) != 1 {
		return nil, nil, ctx.Errorf(ast, "invalid expression")
	}
	expr := exprs[0]
	arrayType := expr.IndirectType()
	if !arrayType.Type.Array() {
		return nil, nil, ctx.Errorf(ast, "invalid operation: cannot slice %v",
			expr.Type.Type)
	}
	elementSize := arrayType.ElementType.Bits

	var from, to types.Size
	block, from, to, err = ast.limitsSSA(block, ctx, gen, arrayType)
	if err != nil {
		return nil, nil, err
	}

	bits := (to - from) * elementSize

	var t ssa.Value

	if expr.Type.Type == types.TPtr {
		// Take a copy of the PtrInfo and adjust its offset.
		ptrInfo := *expr.PtrInfo
		ptrInfo.Offset += from * elementSize

		et := arrayType
		et.Type = types.TSlice
		et.ID = 0
		et.ArraySize = to - from

		ti := types.Info{
			Type:        types.TPtr,
			IsConcrete:  true,
			Bits:        bits,
			MinBits:     bits,
			ElementType: &et,
		}
		t = gen.AnonVal(ti)
		t.PtrInfo = &ptrInfo
	} else {
		ti := types.Info{
			Type:       arrayType.Type,
			IsConcrete: true,
			Bits:       bits,
			MinBits:    bits,
		}
		ti.Type = types.TSlice
		ti.ElementType = arrayType.ElementType
		ti.ArraySize = ti.Bits / ti.ElementType.Bits

		t = gen.AnonVal(ti)
	}
	if bits > 0 {
		fromConst := gen.Constant(int64(from*elementSize), types.Undefined)
		toConst := gen.Constant(int64(to*elementSize), types.Undefined)
		block.AddInstr(ssa.NewSliceInstr(expr, fromConst, toConst, t))
	}

	return block, []ssa.Value{t}, nil
}

func (ast *Slice) limitsSSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator,
	t types.Info) (*ssa.Block, types.Size, types.Size, error) {

	elementCount := t.ArraySize

	var err error
	var val []ssa.Value
	var from types.Size

	if ast.From == nil {
		from = 0
	} else {
		block, val, err = ast.From.SSA(block, ctx, gen)
		if err != nil {
			return nil, 0, 0, err
		}
		if len(val) != 1 {
			return nil, 0, 0, ctx.Errorf(ast.From, "invalid from index")
		}
		from, err = val[0].ConstInt()
		if err != nil {
			return nil, 0, 0, ctx.Errorf(ast.From, "%s", err)
		}
	}
	var to types.Size
	if ast.To == nil {
		to = elementCount
	} else {
		block, val, err = ast.To.SSA(block, ctx, gen)
		if err != nil {
			return nil, 0, 0, err
		}
		if len(val) != 1 {
			return nil, 0, 0, ctx.Errorf(ast.To, "invalid to index")
		}
		to, err = val[0].ConstInt()
		if err != nil {
			return nil, 0, 0, ctx.Errorf(ast.To, "%s", err)
		}
	}
	if ast.From != nil && ast.To != nil &&
		(from >= elementCount || from > to) {
		return nil, 0, 0, ctx.Errorf(ast, "slice bounds out of range [%d:%d]",
			from, to)
	}

	return block, from, to, nil
}

// SSA implements the compiler.ast.AST.SSA for index expressions.
func (ast *Index) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	block, exprs, err := ast.Expr.SSA(block, ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	if len(exprs) != 1 {
		return nil, nil, ctx.Errorf(ast, "invalid expression")
	}
	expr := exprs[0]

	block, val, err := ast.Index.SSA(block, ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	if len(val) != 1 {
		return nil, nil, ctx.Errorf(ast.Index, "invalid index")
	}
	if val[0].Const {
		return ast.constIndex(block, ctx, gen, expr, val[0])
	}
	return ast.index(block, ctx, gen, expr, val[0])
}

func (ast *Index) constIndex(block *ssa.Block, ctx *Codegen, gen *ssa.Generator,
	expr, ival ssa.Value) (*ssa.Block, []ssa.Value, error) {

	index, err := ival.ConstInt()
	if err != nil {
		return nil, nil, ctx.Errorf(ast.Index, "%s", err)
	}

	var it types.Info
	var ptrInfo ssa.PtrInfo
	if expr.Type.Type == types.TPtr {
		it = *expr.Type.ElementType
		ptrInfo = *expr.PtrInfo
		b, ok := ptrInfo.Bindings.Get(ptrInfo.Name)
		if !ok {
			return nil, nil, ctx.Errorf(ast.Index, "undefined: %s",
				ptrInfo.Name)
		}
		expr = b.Value(block, gen)
	} else {
		it = expr.Type
	}

	switch it.Type {
	case types.TString:
		length := it.Bits / types.ByteBits
		if index < 0 || index >= length {
			return nil, nil, ctx.Errorf(ast.Index,
				"invalid array index %d (out of bounds for %d-element string)",
				index, length)
		}
		from := int64(index*types.ByteBits + ptrInfo.Offset)
		to := int64((index+1)*types.ByteBits + ptrInfo.Offset)

		indexType := types.Info{
			Type:       types.TUint,
			IsConcrete: true,
			Bits:       types.ByteBits,
			MinBits:    types.ByteBits,
		}

		t := gen.AnonVal(indexType)
		if to > from {
			fromConst := gen.Constant(from, types.Undefined)
			toConst := gen.Constant(to, types.Undefined)
			block.AddInstr(ssa.NewSliceInstr(expr, fromConst, toConst, t))
		}

		return block, []ssa.Value{t}, nil

	case types.TArray, types.TSlice:
		if index < 0 || index >= it.ArraySize {
			return nil, nil, ctx.Errorf(ast.Index,
				"invalid array index %d (out of bounds for %d-element array)",
				index, it.ArraySize)
		}
		from := int64(index*it.ElementType.Bits + ptrInfo.Offset)
		to := int64((index+1)*it.ElementType.Bits + ptrInfo.Offset)

		t := gen.AnonVal(*it.ElementType)
		if to > from {
			fromConst := gen.Constant(from, types.Undefined)
			toConst := gen.Constant(to, types.Undefined)
			block.AddInstr(ssa.NewSliceInstr(expr, fromConst, toConst, t))
		}

		return block, []ssa.Value{t}, nil

	default:
		return nil, nil, ctx.Errorf(ast,
			"invalid operation: %s[%d] (type %s does not support indexing)",
			ast.Expr, index, expr.Type)
	}
}

func (ast *Index) index(block *ssa.Block, ctx *Codegen, gen *ssa.Generator,
	expr, index ssa.Value) (*ssa.Block, []ssa.Value, error) {

	var it types.Info
	var ptrInfo ssa.PtrInfo
	if expr.Type.Type == types.TPtr {
		it = *expr.Type.ElementType
		ptrInfo = *expr.PtrInfo
		b, ok := ptrInfo.Bindings.Get(ptrInfo.Name)
		if !ok {
			return nil, nil, ctx.Errorf(ast.Index, "undefined: %s",
				ptrInfo.Name)
		}
		expr = b.Value(block, gen)
	} else {
		it = expr.Type
	}

	switch it.Type {
	case types.TArray, types.TSlice:
		offset := gen.Constant(int64(ptrInfo.Offset), types.Undefined)
		t := gen.AnonVal(*it.ElementType)
		block.AddInstr(ssa.NewIndexInstr(expr, offset, index, t))
		return block, []ssa.Value{t}, nil

	default:
		return nil, nil, ctx.Errorf(ast,
			"invalid operation: %s[%v] (type %s does not support non-cost indexing)",
			ast.Expr, index, expr.Type)
	}
}

// SSA implements the compiler.ast.AST.SSA for variable references.
func (ast *VariableRef) SSA(block *ssa.Block, ctx *Codegen,
	gen *ssa.Generator) (*ssa.Block, []ssa.Value, error) {

	lrv, _, _, err := ctx.LookupVar(block, gen, block.Bindings, ast)
	if err != nil {
		return nil, nil, ctx.Error(ast, err.Error())
	}

	value := lrv.RValue()
	if value.Const {
		gen.AddConstant(value)
	}

	return block, []ssa.Value{value}, nil
}

// SSA implements the compiler.ast.AST.SSA for constant values.
func (ast *BasicLit) SSA(block *ssa.Block, ctx *Codegen,
	gen *ssa.Generator) (*ssa.Block, []ssa.Value, error) {

	v := gen.Constant(ast.Value, types.Undefined)
	gen.AddConstant(v)

	return block, []ssa.Value{v}, nil
}

// SSA implements the compiler.ast.AST.SSA for constant values.
func (ast *CompositeLit) SSA(block *ssa.Block, ctx *Codegen,
	gen *ssa.Generator) (*ssa.Block, []ssa.Value, error) {
	return nil, nil, ctx.Errorf(ast, "CompositeLit.SSA not implemented yet")
}

// SSA implements the compiler.ast.AST.SSA for the builtin function make.
func (ast *Make) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	if len(ast.Exprs) != 1 {
		return nil, nil, ctx.Errorf(ast,
			"invalid amount of argument in call to make")
	}
	env := NewEnv(block)
	typeInfo, err := ast.Type.Resolve(env, ctx, gen)
	if err != nil {
		return nil, nil, ctx.Errorf(ast.Type, "%s is not a type", ast.Type)
	}
	if !typeInfo.Type.Array() {
		return nil, nil, ctx.Errorf(ast.Type,
			"can't make instance of type %s", typeInfo)
	}
	if typeInfo.Bits != 0 {
		return nil, nil, ctx.Errorf(ast.Type,
			"can't make specified type %s", typeInfo)
	}
	constVal, _, err := ast.Exprs[0].Eval(env, ctx, gen)
	if err != nil {
		return nil, nil, ctx.Error(ast.Exprs[0], err.Error())
	}
	length, err := constVal.ConstInt()
	if err != nil {
		return nil, nil, ctx.Errorf(ast.Exprs[0],
			"non-integer (%T) len argument in %s: %s", constVal, ast, err)
	}

	if !typeInfo.ElementType.Concrete() {
		return nil, nil, ctx.Errorf(ast.Type,
			"unspecified array element type: %s", typeInfo.ElementType)
	}
	typeInfo.IsConcrete = true
	typeInfo.ArraySize = length
	typeInfo.Bits = typeInfo.ElementType.Bits * length
	typeInfo.MinBits = typeInfo.Bits

	initVal, err := initValue(typeInfo)
	if err != nil {
		return nil, nil, ctx.Error(ast, err.Error())
	}
	init := gen.Constant(initVal, typeInfo)
	gen.AddConstant(init)

	v := gen.AnonVal(typeInfo)
	block.AddInstr(ssa.NewMovInstr(init, v))

	return block, []ssa.Value{v}, nil
}

// SSA implements the compiler.ast.AST.SSA for the builtin function copy.
func (ast *Copy) SSA(block *ssa.Block, ctx *Codegen, gen *ssa.Generator) (
	*ssa.Block, []ssa.Value, error) {

	var lrv *LRValue
	var err error
	var dst ssa.Value
	var dstTo, dstFrom types.Size

	// Resolve destination.
	switch lv := ast.Dst.(type) {
	case *VariableRef:
		lrv, _, _, err = ctx.LookupVar(block, gen, block.Bindings, lv)
		if err != nil {
			return nil, nil, ctx.Error(ast.Dst, err.Error())
		}
		lrv = lrv.Indirect()
		dst = lrv.RValue()
		if !dst.Type.Type.Array() {
			return nil, nil, ast.errf(ctx, ast.Dst, "got %v", dst.Type)
		}
		dstFrom = 0
		dstTo = dst.Type.ArraySize

	case *Slice:
		// Slice specifies the copy limits for the
		// destination. Slice's expr must be a variable reference.
		sexpr, ok := lv.Expr.(*VariableRef)
		if !ok {
			return nil, nil, ast.errf(ctx, ast.Dst, "got %T", lv.Expr)
		}
		lrv, _, _, err = ctx.LookupVar(block, gen, block.Bindings, sexpr)
		if err != nil {
			return nil, nil, ctx.Error(ast.Dst, err.Error())
		}
		lrv = lrv.Indirect()
		dst = lrv.RValue()
		if !dst.Type.Type.Array() {
			return nil, nil, ast.errf(ctx, ast.Dst, "got %v", dst.Type)
		}

		block, dstFrom, dstTo, err = lv.limitsSSA(block, ctx, gen, dst.Type)
		if err != nil {
			return nil, nil, ctx.Error(ast.Dst, err.Error())
		}

	default:
		return nil, nil, ast.errf(ctx, ast.Dst, "got %T", ast.Dst)
	}
	dstCount := dstTo - dstFrom
	elSize := dst.Type.ElementType.Bits

	// Resolve source.
	block, v, err := ast.Src.SSA(block, ctx, gen)
	if err != nil {
		return nil, nil, err
	}
	if len(v) != 1 {
		return nil, nil, ast.errf(ctx, ast.Src, "got multivalue %T", ast.Src)
	}
	src := v[0]
	src = src.Indirect(block, gen)
	if !src.Type.Type.Array() {
		return nil, nil, ast.errf(ctx, ast.Src, "got %v", src.Type)
	}
	if !dst.Type.ElementType.Equal(*src.Type.ElementType) {
		return nil, nil, ctx.Errorf(ast,
			"arguments to copy have different element types: %s and %s",
			dst.Type.ElementType, src.Type.ElementType)
	}
	srcCount := src.Type.ArraySize

	var ret ssa.Value

	if dstFrom == 0 && srcCount >= dstCount {
		// Src overwrites dst fully.
		bits := dstCount * elSize
		ti := types.Info{
			Type:        dst.Type.Type,
			IsConcrete:  true,
			Bits:        bits,
			MinBits:     bits,
			ElementType: dst.Type.ElementType,
			ArraySize:   dstCount,
		}
		fromConst := gen.Constant(int64(0), types.Undefined)
		toConst := gen.Constant(int64(dstCount*elSize), types.Undefined)
		ret = gen.Constant(int64(dstCount), types.Undefined)

		tmp := gen.AnonVal(ti)
		block.AddInstr(ssa.NewSliceInstr(src, fromConst, toConst, tmp))
		err := lrv.Set(tmp)
		if err != nil {
			return nil, nil, ctx.Error(ast, err.Error())
		}
	} else {
		// Src overwrites part of dst.
		tmp := gen.AnonVal(dst.Type)
		block.AddInstr(ssa.NewMovInstr(dst, tmp))

		count := srcCount
		if count > dstCount {
			count = dstCount
		}
		ret = gen.Constant(int64(count), types.Undefined)

		// The amov sets tmp[from:to]=src i.e. it automatically slices
		// src to to-from bits.

		tmp2 := gen.AnonVal(dst.Type)
		fromConst := gen.Constant(int64(dstFrom*elSize), types.Undefined)
		toConst := gen.Constant(int64((dstFrom+count)*elSize), types.Undefined)
		block.AddInstr(ssa.NewAmovInstr(src, tmp, fromConst, toConst, tmp2))

		err := lrv.Set(tmp2)
		if err != nil {
			return nil, nil, ctx.Error(ast, err.Error())
		}
	}

	return block, []ssa.Value{ret}, nil
}

func (ast *Copy) errf(ctx *Codegen, offending AST, format string,
	a ...interface{}) error {
	msg := fmt.Sprintf(format, a...)
	return ctx.Errorf(offending,
		"invalid argument: copy expects slice arguments: %s", msg)
}