478 lines
11 KiB
Go
478 lines
11 KiB
Go
package codegen
|
|
|
|
import (
|
|
"errors"
|
|
"math/rand"
|
|
"strings"
|
|
"testing"
|
|
|
|
"github.com/zg/asm-calc/parser"
|
|
"github.com/zg/asm-calc/x64"
|
|
)
|
|
|
|
// runExpr compiles an expression and executes the emitted assembly on the
|
|
// simulator, returning the value left in RAX.
|
|
func runExpr(t *testing.T, expr string) (int64, error) {
|
|
t.Helper()
|
|
node, err := parser.Parse(expr)
|
|
if err != nil {
|
|
t.Fatalf("parse %q: %v", expr, err)
|
|
}
|
|
prog, err := New().Compile(node)
|
|
if err != nil {
|
|
return 0, err
|
|
}
|
|
m := x64.NewMachine()
|
|
return m.Run(prog)
|
|
}
|
|
|
|
func TestArithmetic(t *testing.T) {
|
|
tests := []struct {
|
|
expr string
|
|
want int64
|
|
}{
|
|
{"1", 1},
|
|
{"1 + 2", 3},
|
|
{"10 - 3", 7},
|
|
{"6 * 7", 42},
|
|
{"100 / 5", 20},
|
|
{"17 % 5", 2},
|
|
{"2 + 3 * 4", 14},
|
|
{"(2 + 3) * 4", 20},
|
|
{"-5", -5},
|
|
{"-5 + 3", -2},
|
|
{"--5", 5},
|
|
{"+7", 7},
|
|
{"2 ^ 8", 256},
|
|
{"2 ^ 0", 1},
|
|
{"2 ^ 1", 2},
|
|
{"3 ^ 3", 27},
|
|
{"1 + 2 + 3 + 4 + 5", 15},
|
|
{"100 - 50 - 25", 25}, // left-associative
|
|
{"100 / 10 / 2", 5}, // left-associative
|
|
{"2 ^ 3 ^ 2", 512}, // right-associative: 2^(3^2)
|
|
}
|
|
for _, tt := range tests {
|
|
t.Run(tt.expr, func(t *testing.T) {
|
|
got, err := runExpr(t, tt.expr)
|
|
if err != nil {
|
|
t.Fatalf("run: %v", err)
|
|
}
|
|
if got != tt.want {
|
|
t.Errorf("= %d, want %d", got, tt.want)
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
// Subtraction and division are not commutative, so the compiler must get
|
|
// the operand order right. Emitting them backwards is an easy mistake given
|
|
// the stack strategy, and one that commutative tests would never catch.
|
|
func TestNonCommutativeOperandOrder(t *testing.T) {
|
|
tests := []struct {
|
|
expr string
|
|
want int64
|
|
}{
|
|
{"10 - 3", 7}, // not -7
|
|
{"100 / 4", 25}, // not 0
|
|
{"17 % 5", 2}, // not 5
|
|
{"1 - 2 - 3", -4},
|
|
{"(10 - 3) - 2", 5},
|
|
{"10 - (3 - 2)", 9},
|
|
}
|
|
for _, tt := range tests {
|
|
t.Run(tt.expr, func(t *testing.T) {
|
|
got, err := runExpr(t, tt.expr)
|
|
if err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
if got != tt.want {
|
|
t.Errorf("= %d, want %d (operands may be reversed)", got, tt.want)
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
// idiv divides RDX:RAX, so RDX must be sign-extended from RAX first.
|
|
// Omitting cqo produces wrong answers only for negative dividends, which is
|
|
// exactly why it needs its own test.
|
|
func TestNegativeDivision(t *testing.T) {
|
|
tests := []struct {
|
|
expr string
|
|
want int64
|
|
}{
|
|
{"-10 / 2", -5},
|
|
{"10 / -2", -5},
|
|
{"-10 / -2", 5},
|
|
{"-17 % 5", -2},
|
|
{"17 % -5", 2},
|
|
{"-100 / 7", -14},
|
|
}
|
|
for _, tt := range tests {
|
|
t.Run(tt.expr, func(t *testing.T) {
|
|
got, err := runExpr(t, tt.expr)
|
|
if err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
if got != tt.want {
|
|
t.Errorf("= %d, want %d (is cqo missing before idiv?)", got, tt.want)
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
// evaluate is an independent reference implementation, used to check the
|
|
// generated code against something that shares none of its logic.
|
|
func evaluate(node parser.Node, vars map[string]int64) (int64, error) {
|
|
switch n := node.(type) {
|
|
case *parser.Number:
|
|
return n.Value, nil
|
|
case *parser.Variable:
|
|
v, ok := vars[n.Name]
|
|
if !ok {
|
|
return 0, errors.New("undefined variable")
|
|
}
|
|
return v, nil
|
|
case *parser.Assignment:
|
|
v, err := evaluate(n.Value, vars)
|
|
if err != nil {
|
|
return 0, err
|
|
}
|
|
vars[n.Name] = v
|
|
return v, nil
|
|
case *parser.UnaryOp:
|
|
v, err := evaluate(n.Operand, vars)
|
|
return -v, err
|
|
case *parser.BinaryOp:
|
|
l, err := evaluate(n.Left, vars)
|
|
if err != nil {
|
|
return 0, err
|
|
}
|
|
r, err := evaluate(n.Right, vars)
|
|
if err != nil {
|
|
return 0, err
|
|
}
|
|
switch n.Op.String() {
|
|
case "+":
|
|
return l + r, nil
|
|
case "-":
|
|
return l - r, nil
|
|
case "*":
|
|
return l * r, nil
|
|
case "/":
|
|
if r == 0 {
|
|
return 0, x64.ErrDivideByZero
|
|
}
|
|
return l / r, nil
|
|
case "%":
|
|
if r == 0 {
|
|
return 0, x64.ErrDivideByZero
|
|
}
|
|
return l % r, nil
|
|
case "^":
|
|
result := int64(1)
|
|
for range r {
|
|
result *= l
|
|
}
|
|
return result, nil
|
|
}
|
|
}
|
|
return 0, errors.New("unsupported node")
|
|
}
|
|
|
|
// Differential test: for thousands of random expressions, the assembly the
|
|
// compiler emits must compute exactly what a direct evaluator computes.
|
|
// This covers operand ordering, precedence and associativity together,
|
|
// across far more cases than a table could list.
|
|
func TestGeneratedCodeMatchesReferenceEvaluator(t *testing.T) {
|
|
rng := rand.New(rand.NewSource(1))
|
|
checked := 0
|
|
|
|
for range 3000 {
|
|
expr := randomExpression(rng, 3)
|
|
|
|
node, err := parser.Parse(expr)
|
|
if err != nil {
|
|
t.Fatalf("generated an unparseable expression %q: %v", expr, err)
|
|
}
|
|
|
|
want, wantErr := evaluate(node, map[string]int64{})
|
|
got, gotErr := runExpr(t, expr)
|
|
|
|
// Division by zero must fail in both, or in neither.
|
|
if (wantErr != nil) != (gotErr != nil) {
|
|
t.Fatalf("%q: reference err = %v, compiled err = %v", expr, wantErr, gotErr)
|
|
}
|
|
if wantErr != nil {
|
|
continue
|
|
}
|
|
if got != want {
|
|
t.Fatalf("%q: compiled gave %d, reference gave %d", expr, got, want)
|
|
}
|
|
checked++
|
|
}
|
|
if checked < 1000 {
|
|
t.Fatalf("only %d expressions actually compared", checked)
|
|
}
|
|
}
|
|
|
|
// randomExpression builds a random arithmetic expression of bounded depth.
|
|
func randomExpression(rng *rand.Rand, depth int) string {
|
|
if depth <= 0 || rng.Intn(4) == 0 {
|
|
return itoa(int64(rng.Intn(200) - 100))
|
|
}
|
|
ops := []string{"+", "-", "*", "/", "%"}
|
|
op := ops[rng.Intn(len(ops))]
|
|
left := randomExpression(rng, depth-1)
|
|
right := randomExpression(rng, depth-1)
|
|
return "(" + left + " " + op + " " + right + ")"
|
|
}
|
|
|
|
func itoa(v int64) string {
|
|
if v < 0 {
|
|
// Wrap negatives so they parse as unary minus rather than as part
|
|
// of the operator.
|
|
return "(0 - " + itoa(-v) + ")"
|
|
}
|
|
s := ""
|
|
if v == 0 {
|
|
return "0"
|
|
}
|
|
for v > 0 {
|
|
s = string(rune('0'+v%10)) + s
|
|
v /= 10
|
|
}
|
|
return s
|
|
}
|
|
|
|
func TestVariables(t *testing.T) {
|
|
c := New()
|
|
m := x64.NewMachine()
|
|
|
|
run := func(expr string) (int64, error) {
|
|
node, err := parser.Parse(expr)
|
|
if err != nil {
|
|
return 0, err
|
|
}
|
|
prog, err := c.Compile(node)
|
|
if err != nil {
|
|
return 0, err
|
|
}
|
|
return m.Run(prog)
|
|
}
|
|
|
|
if _, err := run("x = 10"); err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
if _, err := run("y = 32"); err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
got, err := run("x + y")
|
|
if err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
if got != 42 {
|
|
t.Errorf("x + y = %d, want 42", got)
|
|
}
|
|
|
|
// Reassignment must reuse the same slot, not allocate a new one.
|
|
before := len(c.Variables())
|
|
if _, err := run("x = 100"); err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
if after := len(c.Variables()); after != before {
|
|
t.Errorf("reassignment allocated a new slot: %d -> %d", before, after)
|
|
}
|
|
if got, _ := run("x"); got != 100 {
|
|
t.Errorf("x = %d, want 100", got)
|
|
}
|
|
}
|
|
|
|
func TestUndefinedVariable(t *testing.T) {
|
|
node, _ := parser.Parse("undefined_var + 1")
|
|
if _, err := New().Compile(node); err == nil {
|
|
t.Error("expected an error for an undefined variable")
|
|
}
|
|
}
|
|
|
|
func TestDivisionByZero(t *testing.T) {
|
|
for _, expr := range []string{"1 / 0", "1 % 0", "5 / (3 - 3)"} {
|
|
t.Run(expr, func(t *testing.T) {
|
|
_, err := runExpr(t, expr)
|
|
if !errors.Is(err, x64.ErrDivideByZero) {
|
|
t.Errorf("err = %v, want ErrDivideByZero", err)
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
func TestPowerErrors(t *testing.T) {
|
|
tests := []string{
|
|
"2 ^ -1", // no integer result
|
|
"2 ^ 100", // exponent too large
|
|
"2 ^ x", // exponent must be constant
|
|
}
|
|
for _, expr := range tests {
|
|
t.Run(expr, func(t *testing.T) {
|
|
node, err := parser.Parse(expr)
|
|
if err != nil {
|
|
return // a parse error is also an acceptable rejection
|
|
}
|
|
if _, err := New().Compile(node); err == nil {
|
|
t.Error("expected a compile error")
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
// A well-formed program balances its pushes and pops. An imbalance would
|
|
// corrupt the stack in real execution.
|
|
func TestStackIsBalanced(t *testing.T) {
|
|
exprs := []string{
|
|
"1 + 2",
|
|
"((1 + 2) * (3 + 4)) - ((5 * 6) / 2)",
|
|
"1 + 2 * 3 - 4 / 2 + 5 % 3",
|
|
"2 ^ 8",
|
|
"-((1 + 2) * 3)",
|
|
}
|
|
for _, expr := range exprs {
|
|
t.Run(expr, func(t *testing.T) {
|
|
node, _ := parser.Parse(expr)
|
|
prog, err := New().Compile(node)
|
|
if err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
m := x64.NewMachine()
|
|
if _, err := m.Run(prog); err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
if d := m.StackDepth(); d != 0 {
|
|
t.Errorf("stack depth after execution = %d, want 0", d)
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
// Deeply nested expressions must compile without running out of registers —
|
|
// which is the reason for using the stack rather than a register pair.
|
|
func TestDeepNesting(t *testing.T) {
|
|
expr := "1"
|
|
for range 200 {
|
|
expr = "(" + expr + " + 1)"
|
|
}
|
|
got, err := runExpr(t, expr)
|
|
if err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
if got != 201 {
|
|
t.Errorf("= %d, want 201", got)
|
|
}
|
|
}
|
|
|
|
func TestEmittedAssemblyIsReadable(t *testing.T) {
|
|
node, _ := parser.Parse("2 + 3 * 4")
|
|
prog, err := New().Compile(node)
|
|
if err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
asm := prog.String()
|
|
for _, want := range []string{"mov", "push", "pop", "imul", "add", ";"} {
|
|
if !strings.Contains(asm, want) {
|
|
t.Errorf("assembly missing %q:\n%s", want, asm)
|
|
}
|
|
}
|
|
}
|
|
|
|
// The wrapper must be a complete, assemblable source file.
|
|
func TestAssembleProducesCompleteSource(t *testing.T) {
|
|
node, _ := parser.Parse("x = 42")
|
|
c := New()
|
|
prog, err := c.Compile(node)
|
|
if err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
src := Assemble(prog, c.FrameSize())
|
|
for _, want := range []string{"bits 64", "section .text", "global _start", "_start:", "push rbp", "syscall"} {
|
|
if !strings.Contains(src, want) {
|
|
t.Errorf("assembled source missing %q:\n%s", want, src)
|
|
}
|
|
}
|
|
}
|
|
|
|
// The ABI requires 16-byte stack alignment; an unaligned frame crashes any
|
|
// callee that uses SSE.
|
|
func TestFrameIsAligned(t *testing.T) {
|
|
for _, size := range []int{8, 16, 24, 40} {
|
|
src := Assemble(x64.Program{}, size)
|
|
// Find the "sub rsp, N" line and check N is a multiple of 16.
|
|
for _, line := range strings.Split(src, "\n") {
|
|
if after, ok := strings.CutPrefix(strings.TrimSpace(line), "sub rsp, "); ok {
|
|
n := 0
|
|
for _, ch := range after {
|
|
n = n*10 + int(ch-'0')
|
|
}
|
|
if n%16 != 0 {
|
|
t.Errorf("frame size %d produced an unaligned sub rsp, %d", size, n)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// The exponent need not be a literal, only constant: 2^(3^2) and 2^(1+2)
|
|
// must both compile.
|
|
func TestConstantFoldedExponent(t *testing.T) {
|
|
tests := []struct {
|
|
expr string
|
|
want int64
|
|
}{
|
|
{"2 ^ (1 + 2)", 8},
|
|
{"2 ^ 3 ^ 2", 512},
|
|
{"3 ^ (4 - 2)", 9},
|
|
{"2 ^ (6 / 2)", 8},
|
|
{"2 ^ (-1 + 3)", 4},
|
|
}
|
|
for _, tt := range tests {
|
|
t.Run(tt.expr, func(t *testing.T) {
|
|
got, err := runExpr(t, tt.expr)
|
|
if err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
if got != tt.want {
|
|
t.Errorf("= %d, want %d", got, tt.want)
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
func TestConstFold(t *testing.T) {
|
|
tests := []struct {
|
|
expr string
|
|
want int64
|
|
ok bool
|
|
}{
|
|
{"42", 42, true},
|
|
{"1 + 2 * 3", 7, true},
|
|
{"-5", -5, true},
|
|
{"2 ^ 3", 8, true},
|
|
{"1 / 0", 0, false}, // refuses rather than panicking
|
|
{"1 % 0", 0, false},
|
|
{"x + 1", 0, false}, // depends on a variable
|
|
}
|
|
for _, tt := range tests {
|
|
t.Run(tt.expr, func(t *testing.T) {
|
|
node, err := parser.Parse(tt.expr)
|
|
if err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
got, ok := constFold(node)
|
|
if ok != tt.ok {
|
|
t.Fatalf("ok = %v, want %v", ok, tt.ok)
|
|
}
|
|
if ok && got != tt.want {
|
|
t.Errorf("= %d, want %d", got, tt.want)
|
|
}
|
|
})
|
|
}
|
|
}
|