fspl/llvm/constant.go

package llvm

import "fmt"
import "log"
import "math"
import "strings"
import "math/big"

import "github.com/mewmew/float"
import "github.com/mewmew/float/binary128"
import "github.com/mewmew/float/binary16"
import "github.com/mewmew/float/float128ppc"
import "github.com/mewmew/float/float80x86"

type Const interface {
	Value
	IsConstant ()
}

type ConstArray struct {
	Ty       *TypeArray
	Elements []Const
}
func (*ConstArray) IsConstant () { }
func (this *ConstArray) Type () Type { return this.Ty }
func (this *ConstArray) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstArray) Name () string { return this.Identifier() }
func (this *ConstArray) Identifier () string {
	buf := &strings.Builder{}
	buf.WriteString("[")
	for i, elem := range this.Elements {
		if i != 0 {
			buf.WriteString(", ")
		}
		buf.WriteString(elem.String())
	}
	buf.WriteString("]")
	return buf.String()
}

type ConstBlockAddress struct {
	Function Const
	Block    Value
}
func (*ConstBlockAddress) IsConstant ( ) { }
func (this *ConstBlockAddress) Type () Type { return &TypePointer { } }
func (this *ConstBlockAddress) String () string {
	return fmt.Sprintf("%v %v", &TypePointer { }, this.Identifier())
}
func (this *ConstBlockAddress) Name () string { return this.Identifier() }
func (this *ConstBlockAddress) Identifier () string {
	return fmt.Sprintf("blockaddress(%s, %s)", this.Function.Name(), this.Block.Name())
}

type ConstCharArray struct {
	Ty       *TypeArray
	Elements []byte
}
func (*ConstCharArray) IsConstant () { }
func (this *ConstCharArray) Type () Type { return this.Ty }
func (this *ConstCharArray) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstCharArray) Name () string { return this.Identifier() }
func (this *ConstCharArray) Identifier () string {
	return "c" + EscapeQuoteString(this.Elements)
}

type ConstDSOLocalEquivalent struct {
	Function Const
}
func (*ConstDSOLocalEquivalent) IsConstant () { }
func (this *ConstDSOLocalEquivalent) Type () Type { return this.Function.Type() }
func (this *ConstDSOLocalEquivalent) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstDSOLocalEquivalent) Name () string { return this.Identifier() }
func (this *ConstDSOLocalEquivalent) Identifier () string {
	return fmt.Sprintf("dso_local_equivalent %s", this.Function.Name())
}

type ConstFloat struct {
	Ty    *TypeFloat
	Value *big.Float
	NaN   bool
}
func NewConstFloat (ty *TypeFloat, value float64) *ConstFloat {
	if math.IsNaN(value) {
		f := &ConstFloat { Ty: ty, Value: &big.Float { }, NaN: true }
		// Store sign of NaN.
		if math.Signbit(value) {
			f.Value.SetFloat64(-1)
		}
		return f
	}
	return &ConstFloat {
		Ty:    ty,
		Value: big.NewFloat(value),
	}
}
func (*ConstFloat) IsConstant () { }
func (this *ConstFloat) Type () Type { return this.Ty }
func (this *ConstFloat) Name () string { return this.Identifier() }
func (this *ConstFloat) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstFloat) Identifier () string {
	// FloatLit
	//
	// Print hexadecimal representation of floating-point literal if NaN, Inf,
	// inexact or extended precision (x86_fp80, fp128 or ppc_fp128).
	switch this.Ty.Kind {
	// half (IEEE 754 half precision)
	case FloatKindHalf:
		const hexPrefix = 'H'
		if this.NaN {
			bits := binary16.NaN.Bits()
			if this.Value != nil && this.Value.Signbit() {
				bits = binary16.NegNaN.Bits()
			}
			return fmt.Sprintf("0x%c%04X", hexPrefix, bits)
		}
		if this.Value.IsInf() || !float.IsExact16(this.Value) {
			f, acc := binary16.NewFromBig(this.Value)
			if acc != big.Exact {
				log.Printf("unable to represent floating-point constant %v of type %v exactly; please submit a bug report to fspl with this error message", this.Value, this.Type())
			}
			bits := f.Bits()
			return fmt.Sprintf("0x%c%04X", hexPrefix, bits)
		}
		// c is representable without loss as floating-point literal, this case is
		// handled for half, float and double below the switch statement.
	// float (IEEE 754 single precision)
	case FloatKindFloat:
		// ref: https://groups.google.com/d/msg/llvm-dev/IlqV3TbSk6M/27dAggZOMb0J
		//
		// The exact bit representation of the float is laid out with the
		// corresponding bitwise representation of a double: the sign bit is
		// copied over, the exponent is encoded in the larger width, and the 23
		// bits of significand fills in the top 23 bits of significand in the
		// double. A double has 52 bits of significand, so this means that the
		// last 29 bits of significand will always be ignored. As an error
		// detection measure, the IR parser requires them to be zero.
		if this.NaN {
			f := math.NaN()
			if this.Value != nil && this.Value.Signbit() {
				f = math.Copysign(f, -1)
			}
			bits := math.Float64bits(f)
			// zero out last 29 bits.
			bits &^= 0x1FFFFFFF
			return fmt.Sprintf("0x%X", bits)
		}
		if this.Value.IsInf() || !float.IsExact32(this.Value) {
			f, _ := this.Value.Float64()
			bits := math.Float64bits(f)
			// Note, to match Clang output we do not zero-pad the hexadecimal
			// output.
			// zero out last 29 bits.
			bits &^= 0x1FFFFFFF
			return fmt.Sprintf("0x%X", bits)
		}
		// c is representable without loss as floating-point literal, this case is
		// handled for half, float and double below the switch statement.
	// double (IEEE 754 double precision)
	case FloatKindDouble:
		if this.NaN {
			// To use the same cannonical representation as LLVM IR for NaN values, we
			// explicitly a qNaN value (quiet NaN) with the leading bit in the mantissa
			// set, rather than the trailing bit as used for the cannonical
			// representation in Go (see math.NaN).
			//
			// For further background, see https://github.com/llir/llvm/issues/133
			//
			//      exponent    mantissa
			//    s 11111111111 1xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx = quiet     (qNaN)
			//    s 11111111111 0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx = signaling (sNaN) **
			//                  ^ quiet bit
			//
			// Where ** denote that at least one of the 'x' bits has to be set, since the
			// mantissa must be non-zero to denote NaN.
			//
			// quiet NaN:
			//    0x7FF8000000000000 = 0b0_11111111111_100000000000000000000000000000000000000000000000000
			f := math.Float64frombits(0x7FF8000000000000) // quiet NaN
			if this.Value != nil && this.Value.Signbit() {
				f = math.Copysign(f, -1)
			}
			bits := math.Float64bits(f)
			return fmt.Sprintf("0x%X", bits)
		}
		if this.Value.IsInf() || !float.IsExact64(this.Value) {
			f, _ := this.Value.Float64()
			bits := math.Float64bits(f)
			// Note, to match Clang output we do not zero-pad the hexadecimal
			// output.
			return fmt.Sprintf("0x%X", bits)
		}
		// c is representable without loss as floating-point literal, this case is
		// handled for half, float and double below the switch statement.
	// x86_fp80 (x86 extended precision)
	case FloatKindX86_FP80:
		// always represent x86_fp80 in hexadecimal floating-point notation.
		const hexPrefix = 'K'
		if this.NaN {
			se, m := float80x86.NaN.Bits()
			if this.Value != nil && this.Value.Signbit() {
				se, m = float80x86.NegNaN.Bits()
			}
			return fmt.Sprintf("0x%c%04X%016X", hexPrefix, se, m)
		}
		f, acc := float80x86.NewFromBig(this.Value)
		if acc != big.Exact {
			log.Printf("unable to represent floating-point constant %v of type %v exactly; please submit a bug report to fspl with this error message", this.Value, this.Type())
		}
		se, m := f.Bits()
		return fmt.Sprintf("0x%c%04X%016X", hexPrefix, se, m)
	// fp128 (IEEE 754 quadruple precision)
	case FloatKindFP128:
		// always represent fp128 in hexadecimal floating-point notation.
		const hexPrefix = 'L'
		if this.NaN {
			a, b := binary128.NaN.Bits()
			if this.Value != nil && this.Value.Signbit() {
				a, b = binary128.NegNaN.Bits()
			}
			return fmt.Sprintf("0x%c%016X%016X", hexPrefix, a, b)
		}
		f, acc := binary128.NewFromBig(this.Value)
		if acc != big.Exact {
			log.Printf("unable to represent floating-point constant %v of type %v exactly; please submit a bug report to fspl with this error message", this.Value, this.Type())
		}
		a, b := f.Bits()
		return fmt.Sprintf("0x%c%016X%016X", hexPrefix, a, b)
	// ppc_fp128 (PowerPC double-double arithmetic)
	case FloatKindPPC_FP128:
		// always represent ppc_fp128 in hexadecimal floating-point notation.
		const hexPrefix = 'M'
		if this.NaN {
			a, b := float128ppc.NaN.Bits()
			if this.Value != nil && this.Value.Signbit() {
				a, b = float128ppc.NegNaN.Bits()
			}
			return fmt.Sprintf("0x%c%016X%016X", hexPrefix, a, b)
		}
		f, acc := float128ppc.NewFromBig(this.Value)
		if acc != big.Exact {
			log.Printf("unable to represent floating-point constant %v of type %v exactly; please submit a bug report to fspl with this error message", this.Value, this.Type())
		}
		a, b := f.Bits()
		return fmt.Sprintf("0x%c%016X%016X", hexPrefix, a, b)
	default:
		panic(fmt.Errorf("support for floating-point kind %v not yet implemented", this.Ty.Kind))
	}
	// Insert decimal point if not present.
	//    3e4 -> 3.0e4
	//    42  -> 42.0
	s := this.Value.Text('g', -1)
	if !strings.ContainsRune(s, '.') {
		if pos := strings.IndexByte(s, 'e'); pos != -1 {
			s = s[:pos] + ".0" + s[pos:]
		} else {
			s += ".0"
		}
	}
	return s
}

type ConstIndex struct {
	Const
	InRange bool
}
func (this *ConstIndex) Name () string { return this.Identifier() }
func (this *ConstIndex) Identifier () string {
	// OptInrange Type Constant
	if this.InRange {
		return fmt.Sprintf("inrange %s", this.Const)
	}
	return this.Const.String()
}

type ConstInt struct {
	Ty    *TypeInt
	Value *big.Int
}
func NewConstInt (ty *TypeInt, value int64) *ConstInt {
	return &ConstInt {
		Ty:    ty,
		Value: big.NewInt(value),
	}
}
func NewConstBool (value bool) *ConstInt {
	var intVal int64
	if value { intVal = 1 }
	return NewConstInt(I1, intVal)
}
func (*ConstInt) IsConstant () { }
func (this *ConstInt) Type () Type { return this.Ty }
func (this *ConstInt) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstInt) Name () string { return this.Identifier() }
func (this *ConstInt) Identifier () string {
	// IntLit
	if this.Ty.BitSize == 1 {
		// "true"
		// "false"
		switch x := this.Value.Int64(); x {
		case 0:
			return "false"
		case 1:
			return "true"
		default:
			panic(fmt.Errorf("invalid integer value of boolean type; expected 0 or 1, got %d", x))
		}
	}
	// Output x in hexadecimal notation if x is positive, greater than or equal
	// to 0x1000 and has a significantly lower entropy than decimal notation.

	// Minimum difference between entropy of decimal and hexadecimal notation to
	// output x in hexadecimal notation.
	const minEntropyDiff = 0.2
	// Maximum allowed entropy of hexadecimal notation to output x in hexadecimal
	// notation.
	//
	// This is useful as some hex values, while lower entropy than their decimal
	// counter-part do not improve readability.
	//
	// For instance, the decimal entropy of 7240739780546808700 is 9/10 = 0.9 and
	// the hexadecimal entropy of 0x647C4677A2884B7C is 8/16 = 0.5. As such the
	// entropy difference is 0.9-0.5 = 0.4, but the hexadecimal notation does not
	// improve readability. Thus we add an upper bound on the hexadecimal entropy,
	// and if the entropy is above this bound, output in decimal notation
	// instead.
	hexLength := len(this.Value.Text(16))
	maxHexEntropy := calcMaxHexEntropy(hexLength)
	threshold := big.NewInt(0x1000) // 4096
	// Check entropy if x >= 0x1000.
	if this.Value.Cmp(threshold) >= 0 {
		hexentropy := hexEntropy(this.Value)
		decentropy := decimalEntropy(this.Value)
		if hexentropy <= maxHexEntropy+0.01 && decentropy >= hexentropy+minEntropyDiff {
			return "u0x" + strings.ToUpper(this.Value.Text(16))
		}
	}
	return this.Value.String()
}
func calcMaxHexEntropy (length int) float64 {
	if length > 16 {
		length = 16
	}
	switch {
	case length < 4:
		return 0
	case 4 <= length && length <= 6:
		return 2.0 / float64(length)
	case 7 <= length && length <= 10:
		return 3.0 / float64(length)
	// length >= 11
	default:
		return 4.0 / float64(length)
	}
}
func hexEntropy(x *big.Int) float64 {
	const base = 16
	return intEntropy(x, base)
}
func decimalEntropy(x *big.Int) float64 {
	const base = 10
	return intEntropy(x, base)
}
func intEntropy(x *big.Int, base int) float64 {
	if base < 2 || base > 62 {
		panic(fmt.Errorf("invalid base; expected 2 <= base <= 62, got %d", base))
	}
	const maxBase = 62
	var digits [maxBase]bool
	s := x.Text(base)
	// Locate unique digits.
	for i := 0; i < len(s); i++ {
		b := s[i]
		if b == '-' {
			// skip sign.
			continue
		}
		d := digitValue(b)
		digits[d] = true
	}
	// Count unique digits.
	uniqueDigits := 0
	for i := 0; i < base; i++ {
		if digits[i] {
			uniqueDigits++
		}
	}
	length := len(s)
	if length > base {
		length = base
	}
	return float64(uniqueDigits) / float64(length)
}
func digitValue(b byte) int {
	switch {
	case '0' <= b && b <= '9':
		return 0 + int(b-'0')
	case 'a' <= b && b <= 'z':
		return 10 + int(b-'a')
	case 'A' <= b && b <= 'Z':
		return 36 + int(b-'A')
	default:
		panic(fmt.Errorf("invalid digit byte; expected [0-9a-zA-Z], got %#U", b))
	}
}

type ConstNoCFI struct {
	Function Const
}
func (*ConstNoCFI) IsConstant () { }
func (this *ConstNoCFI) Type () Type { return this.Function.Type() }
func (this *ConstNoCFI) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstNoCFI) Name () string { return this.Identifier() }
func (this *ConstNoCFI) Identifier () string {
	return fmt.Sprintf("no_cfi %s", this.Function.Identifier())
}

type ConstNull struct { }
func (*ConstNull) IsConstant () { }
func (*ConstNull) Type () Type { return &TypePointer { } }
func (this *ConstNull) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstNull) Name () string { return this.Identifier() }
func (this *ConstNull) Identifier () string { return "null" }

type ConstPoison struct {
	Ty Type
}
func (*ConstPoison) IsConstant () { }
func (this *ConstPoison) Type () Type { return this.Ty }
func (this *ConstPoison) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstPoison) Name () string { return this.Identifier() }
func (this *ConstPoison) Identifier () string { return "poison" }

type ConstStruct struct {
	Ty     *TypeStruct
	Fields []Const
}
func (*ConstStruct) IsConstant () { }
func (this *ConstStruct) Type () Type { return this.Ty }
func (this *ConstStruct) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstStruct) Name () string { return this.Identifier() }
func (this *ConstStruct) Identifier () string {
	buf := &strings.Builder{}
	if this.Ty.Packed {
		buf.WriteString("<")
	}
	buf.WriteString("{ ")
	for i, field := range this.Fields {
		if i != 0 {
			buf.WriteString(", ")
		}
		buf.WriteString(field.String())
	}
	buf.WriteString(" }")
	if this.Ty.Packed {
		buf.WriteString(">")
	}
	return buf.String()
}

type ConstUndef struct {
	Ty Type
}
func (*ConstUndef) IsConstant () { }
func (this *ConstUndef) Type () Type { return this.Ty }
func (this *ConstUndef) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstUndef) Name () string { return this.Identifier() }
func (this *ConstUndef) Identifier () string { return "undef" }

type ConstVector struct {
	Ty       *TypeVector
	Elements []Const
}
func (*ConstVector) IsConstant () { }
func (this *ConstVector) Type () Type { return this.Ty }
func (this *ConstVector) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstVector) Name () string { return this.Identifier() }
func (this *ConstVector) Identifier () string {
	buf := &strings.Builder{}
	buf.WriteString("<")
	for i, elem := range this.Elements {
		if i != 0 {
			buf.WriteString(", ")
		}
		buf.WriteString(elem.String())
	}
	buf.WriteString(">")
	return buf.String()
}

type ConstZeroInitializer struct {
	Ty Type
}
func NewConstZeroInitializer (ty Type) *ConstZeroInitializer {
	return &ConstZeroInitializer {
		Ty: ty,
	}
}
func (*ConstZeroInitializer) IsConstant () { }
func (this *ConstZeroInitializer) Type () Type { return this.Ty }
func (this *ConstZeroInitializer) String () string {
	return fmt.Sprintf("%v %v", this.Type(), this.Identifier())
}
func (this *ConstZeroInitializer) Name () string { return this.Identifier() }
func (this *ConstZeroInitializer) Identifier () string { return "zeroinitializer" }