commit 205df2979f1d31b3475d396b4ba26a499d2e3b39
parent 581de5ac65753b00541086820ebd15f3eaf2d7e3
Author: Mohammad-Reza Nabipoor <mnabipoor@gnu.org>
Date: Sat, 28 May 2022 00:49:18 +0430
Implement Jitter codegen with env
Diffstat:
| M | Makefile | | | 9 | +++++---- |
| M | cgen.cpp | | | 176 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------- |
| M | cgen.hpp | | | 10 | ++++++++-- |
| M | cgen.test.cpp | | | 124 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------ |
| A | env.cpp | | | 56 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | env.hpp | | | 23 | +++++++++++++++++++++++ |
| M | toctave.jitter | | | 62 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- |
7 files changed, 428 insertions(+), 32 deletions(-)
diff --git a/Makefile b/Makefile
@@ -2,6 +2,7 @@
JITTER_DISPATCH = switch
JITTER_PREFIX ?= $(HOME)/usr
+CFLAGS += -std=gnu99
CXXFLAGS += -Wall -Wextra -std=c++17 -g3 -fsanitize=address
CPPFLAGS += -I . -I $(JITTER_PREFIX)/include/
LDFLAGS += -lm
@@ -24,10 +25,10 @@ all: $(BINS)
ast.test: ast.test.cpp ast.cpp ast.hpp
$(CXX) -o $@ $(CPPFLAGS) $(CXXFLAGS) $< ast.cpp
-cgen.test: cgen.hpp
-cgen.test: cgen.test.cpp cgen.cpp ast.cpp ast.hpp $(VM_OBJS)
- $(CXX) -o $@ $(CPPFLAGS) $(CXXFLAGS) $< cgen.cpp ast.cpp $(VM_OBJS) \
- $(JCPPFLAGS) $(JLDFLAGS)
+cgen.test: cgen.hpp ast.hpp env.hpp
+cgen.test: cgen.test.cpp cgen.cpp ast.cpp env.cpp $(VM_OBJS)
+ $(CXX) -o $@ $(CPPFLAGS) $(CXXFLAGS) $< cgen.cpp ast.cpp env.cpp \
+ $(VM_OBJS) $(JCPPFLAGS) $(JLDFLAGS)
$(VM) &: toctave.jitter
$(J) -o vm/ $<
diff --git a/cgen.cpp b/cgen.cpp
@@ -1,6 +1,7 @@
#include "cgen.hpp"
+#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <cstring>
@@ -119,19 +120,23 @@ JExecRoutine::JExecRoutine(struct toctave_mutable_routine* r)
{}
void
-JExecRoutine::exec()
+JExecRoutine::exec(env::Env& e)
{
+ TOCTAVE_STATE_RUNTIME_FIELD(state.get(), env) = reinterpret_cast<void*>(&e);
toctave_execute_executable_routine(er.get(), state.get());
+ TOCTAVE_STATE_RUNTIME_FIELD(state.get(), env) = nullptr;
}
bool
-JExecRoutine::exec_continue()
+JExecRoutine::exec_continue(env::Env& e)
{
auto point{ TOCTAVE_STATE_RUNTIME_FIELD(state.get(), point) };
if (point == nullptr)
return false;
+ TOCTAVE_STATE_RUNTIME_FIELD(state.get(), env) = reinterpret_cast<void*>(&e);
toctave_branch_to_program_point(point, state.get());
+ TOCTAVE_STATE_RUNTIME_FIELD(state.get(), env) = nullptr;
return true;
}
@@ -229,6 +234,75 @@ JRoutine::sub()
TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), sub);
}
+namespace {
+
+double
+nan_box(uintptr_t p)
+{
+ static const uintptr_t mask{ ((uint64_t)1 << 51) - 1 };
+ uint64_t n;
+ double d;
+
+ assert((p & 7) == 0); // This is true on GNU systems
+ p >>= 3;
+ assert((~mask & p) == 0); // We're doing nan-boxing, so we only have 51 bits!
+ // This is true, at least, on x86_64.
+ n = ((uint64_t)0xfff8 << 51) | (p & mask); // this a qNAN
+ memcpy(&d, &n, sizeof(n));
+ return d;
+}
+
+#if 0
+uintptr_t
+nan_unbox(double d)
+{
+ static const uintptr_t mask{ ((uint64_t)1 << 51) - 1 };
+ uintptr_t p;
+
+ memcpy(&p, &d, sizeof(d));
+ p &= mask;
+ p <<= 3;
+ return p;
+}
+#endif
+
+uintptr_t
+nan_box_as_uint(uintptr_t p)
+{
+ double d{ nan_box(p) };
+ uintptr_t n;
+
+ memcpy(&n, &d, sizeof(d));
+ return n;
+}
+
+}
+
+void
+JRoutine::pushvar(const char* var)
+{
+ auto n{ nan_box_as_uint(reinterpret_cast<uintptr_t>(var)) };
+
+ TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), pushvar);
+ toctave_mutable_routine_append_unsigned_literal_parameter(r.get(), n);
+}
+
+void
+JRoutine::popvar(const char* var)
+{
+ auto n{ nan_box_as_uint(reinterpret_cast<uintptr_t>(var)) };
+
+ TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), popvar);
+ toctave_mutable_routine_append_unsigned_literal_parameter(r.get(), n);
+}
+
+void
+JRoutine::call(const char* func)
+{
+ (void)func;
+ assert(0 && "not implemented yet");
+}
+
std::string
disasm(const JRoutine& r)
{
@@ -250,26 +324,96 @@ disasm(const JExecRoutine& er)
//--- codegen
-JRoutine
-jitter(ast::NodesIter first, ast::NodesIter last)
-{
- JRoutine r;
+namespace {
+void
+jitter_(JRoutine& r,
+ ast::NodesIter first,
+ ast::NodesIter last,
+ bool toplevel = false)
+{
+ // Post-order traversal
while (first != last) {
- for (const auto& stmt : stlab::child_range(stlab::leading_of(first))) {
- std::visit(overloaded{
- [&](const ast::Num&) {},
- [&](const ast::Op&) {},
- [&](const ast::Id&) {},
- [&](const ast::Str&) {},
- [&](const ast::As&) {},
- [&](const ast::Call&) {},
+ std::visit(overloaded{
+ [&](const ast::Num& n) {
+ r.push(n.num);
+ if (toplevel)
+ r.pop();
},
- stmt);
- }
+ [&](const ast::Op& op) {
+ auto f{ ++stlab::leading_of(first) };
+ auto l{ stlab::trailing_of(first) };
+ auto count{ 0u };
+
+ // first visit the operands
+ while (f != l) {
+ auto n{ ++stlab::trailing_of(f) };
+ jitter_(r, f, n);
+ f = n;
+ ++count;
+ }
+ assert(count == 2);
+ switch (op.op) {
+ case '^':
+ r.pow();
+ break;
+ case '*':
+ r.mul();
+ break;
+ case '/':
+ r.div();
+ break;
+ case '+':
+ r.add();
+ break;
+ case '-':
+ r.sub();
+ break;
+ default:
+ assert(0 && "unknown operator");
+ }
+ if (toplevel)
+ r.pop();
+ },
+ [&](const ast::Id& id) { r.pushvar(id.id.c_str()); },
+ [&](const ast::Str&) { assert(0 && "invalid entity"); },
+ [&](const ast::As& as) {
+ auto f{ ++stlab::leading_of(first) };
+ auto l{ stlab::trailing_of(first) };
+
+ assert(stlab::has_children(first));
+
+ jitter_(r, f, ++stlab::trailing_of(f)); // visit children
+ r.popvar(as.id.id.c_str()); // move the value to variable
+ },
+ [&](const ast::Call& call) {
+ auto f{ ++stlab::leading_of(first) };
+ auto l{ stlab::trailing_of(first) };
+
+ assert(stlab::has_children(first));
+
+ while (f != l) {
+ auto n{ ++stlab::trailing_of(f) };
+ jitter_(r, f, n); // visit children
+ f = n;
+ }
+ r.call(call.id.id.c_str());
+ },
+ },
+ *first);
+
first = ++stlab::trailing_of(first);
}
+}
+
+} // namespace }
+
+JRoutine
+jitter(ast::NodesIter first, ast::NodesIter last)
+{
+ JRoutine r;
+ jitter_(r, first, last, true);
return r;
}
diff --git a/cgen.hpp b/cgen.hpp
@@ -4,6 +4,7 @@
#include <memory>
#include "ast.hpp"
+#include "env.hpp"
// Use the VM generated by Jitter
extern "C"
@@ -42,8 +43,8 @@ public:
friend std::string disasm(const JExecRoutine& er);
- void exec();
- bool exec_continue();
+ void exec(env::Env&);
+ bool exec_continue(env::Env&);
double result();
};
@@ -85,6 +86,11 @@ public:
// branching
// ...
+
+ // Pointer should stay valid until the end of execution
+ void call(const char* func);
+ void pushvar(const char* var); // move value from variable to stack
+ void popvar(const char* var); // move value from stack to variable
};
// Generates code for the VM generated by Jitter
diff --git a/cgen.test.cpp b/cgen.test.cpp
@@ -4,6 +4,8 @@
#include <cassert>
#include <iostream>
+#include "env.hpp"
+
namespace {
void
@@ -57,6 +59,7 @@ cgen_jroutine()
{
cgen::JRoutine r;
+ env::Env e;
r.push(1.0);
r.push(2.0);
@@ -74,12 +77,14 @@ cgen_jroutine()
auto er{ r.mkexec() };
- er.exec();
+ er.exec(e);
assert(er.result() == 3.0);
+ assert(e.empty());
}
{
cgen::JRoutine r;
+ env::Env e;
r.push(3.0);
r.push(4.0);
@@ -101,8 +106,82 @@ cgen_jroutine()
auto er{ r.mkexec() };
- er.exec();
+ er.exec(e);
assert(er.result() == 35.0);
+ assert(e.empty());
+ }
+
+ {
+ cgen::JRoutine r;
+ env::Env e;
+
+ r.push(3.0);
+ r.push(4.0);
+ r.add();
+ r.popvar("x");
+ r.push(2.0);
+ r.pushvar("x");
+ r.mul();
+ r.pop();
+
+ auto d{ cgen::disasm(r) };
+
+ p(d);
+ assert(d == R"( push 3.000000
+ push 4.000000
+ add
+ popvar x
+ push 2.000000
+ pushvar x
+ mul
+ pop
+)");
+
+ auto er{ r.mkexec() };
+
+ er.exec(e);
+ assert(er.result() == 14.0);
+ assert(e.size() == 1);
+ assert(e[0].name == "x");
+ assert(e[0].val == 7.0);
+ }
+
+ {
+ cgen::JRoutine r;
+ env::Env e{ { "y", 10.0 } };
+
+ r.push(3.0);
+ r.push(4.0);
+ r.pow();
+ r.popvar("y");
+ r.push(2.0);
+ r.pushvar("y");
+ r.mul();
+ r.pop();
+
+ auto d{ cgen::disasm(r) };
+
+ p(d);
+ assert(d == R"( push 3.000000
+ push 4.000000
+ pow
+ popvar y
+ push 2.000000
+ pushvar y
+ mul
+ pop
+)");
+
+ auto er{ r.mkexec() };
+
+ assert(e.size() == 1);
+ assert(e[0].name == "y");
+ assert(e[0].val == 10.0);
+ er.exec(e);
+ assert(er.result() == 162.0);
+ assert(e.size() == 1);
+ assert(e[0].name == "y");
+ assert(e[0].val == 81.0);
}
}
@@ -111,14 +190,34 @@ cgen_jitter()
{
auto i{ 0 };
auto p = [&](const auto& s) {
- std::cout << "# " << i << " {\n" << s << "\n# " << i << " }\n";
+ std::cout << "# Generated code " << i << " {\n"
+ << s << "# Generated code " << i << " }\n";
++i;
};
{
+ ast::Nodes num1{ ast::mknum(120) };
+ auto j{ cgen::jitter(num1.begin(), num1.end()) };
+ auto s{ cgen::disasm(j) };
+
+ p(s);
+ assert(s == R"( push 120.000000
+ pop
+)");
+ }
+
+ {
ast::Nodes binop1{ ast::mkop(
ast::Op{ '+' }, ast::mknum(1), ast::mknum(2)) };
auto j{ cgen::jitter(binop1.begin(), binop1.end()) };
+ auto s{ cgen::disasm(j) };
+
+ p(s);
+ assert(s == R"( push 1.000000
+ push 2.000000
+ add
+ pop
+)");
}
{
@@ -127,19 +226,28 @@ cgen_jitter()
ast::mkop(ast::Op{ '+' },
ast::mkop(ast::Op{ '/' }, ast::mknum(1), ast::mknum(2)),
ast::mkop(ast::Op{ '*' }, ast::mknum(3), ast::mknum(4)))) };
- auto s{ cgen::sexpr(ass1.begin(), ass1.end()) };
+ auto j{ cgen::jitter(ass1.begin(), ass1.end()) };
+ auto s{ cgen::disasm(j) };
p(s);
- assert(s == "(setq x (+ (/ 1 2) (* 3 4)))");
+ assert(s == R"( push 1.000000
+ push 2.000000
+ div
+ push 3.000000
+ push 4.000000
+ mul
+ add
+ popvar x
+)");
}
- {
+ if (0) {
ast::Nodes eval1{ ast::mkcall(ast::Id{ "eval" },
ast::mkstr(ast::Str{ "y = 1 + x" })) };
- auto s{ cgen::sexpr(eval1.begin(), eval1.end()) };
+ auto j{ cgen::jitter(eval1.begin(), eval1.end()) };
+ auto s{ cgen::disasm(j) };
p(s);
- assert(s == "(eval \"y = 1 + x\")");
}
}
diff --git a/env.cpp b/env.cpp
@@ -0,0 +1,56 @@
+
+#include "env.hpp"
+
+#include <algorithm>
+#include <cassert>
+#include <cmath>
+#include <utility>
+
+namespace {
+
+using VarIter = env::Env::iterator;
+
+std::pair<bool, VarIter>
+vars_find(env::Env& env, const std::string& name)
+{
+ auto f{ std::begin(env) };
+ auto l{ std::end(env) };
+ auto it{ std::lower_bound(
+ f, l, name, [](const auto& x, const auto& y) { return x.name < y; }) };
+
+ return std::make_pair(it != l, it);
+}
+
+} // anonymous namespace
+
+extern "C" double
+toctave_var(void* env, const char* name)
+{
+ assert(env);
+
+ std::string n{ name };
+ auto [found, it] = vars_find(*reinterpret_cast<env::Env*>(env), n);
+
+ if (!found)
+ return std::nan("");
+
+ auto& var{ *it };
+
+ assert(var.name == n);
+ return var.val;
+}
+
+extern "C" void
+toctave_var_set(void* environ, const char* name, double val)
+{
+ assert(environ);
+
+ auto& env{ *reinterpret_cast<env::Env*>(environ) };
+ std::string n{ name };
+ auto [found, it] = vars_find(env, n);
+
+ if (found)
+ it->val = val;
+ else
+ env.insert(it, env::Var{ n, val });
+}
diff --git a/env.hpp b/env.hpp
@@ -0,0 +1,23 @@
+
+#pragma once
+
+#include <string>
+#include <vector>
+
+extern "C"
+{
+ double toctave_var(void*, const char* name);
+ void toctave_var_set(void*, const char* name, double val);
+}
+
+namespace env {
+
+struct Var
+{
+ std::string name;
+ double val;
+};
+
+using Env = std::vector<Var>;
+
+} // namespace env
diff --git a/toctave.jitter b/toctave.jitter
@@ -16,7 +16,9 @@ end
wrapped-functions
pow
memcpy
- toctave_result
+ nan_unbox
+ toctave_var
+ toctave_var_set
end
state-struct-runtime-c
@@ -25,6 +27,7 @@ state-struct-runtime-c
jitter_program_point point;
int status;
+ void* env;
end
end
@@ -40,6 +43,21 @@ early-header-c
code
#include <math.h>
#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+
+double toctave_var(void* env, const char* name);
+void toctave_var_set(void* env, const char* name, double val);
+
+union double_uint64
+{
+ double d;
+ uint64_t u64;
+};
+
+#define nan_unbox_uint(p) (((p) & /*mask*/(((uint64_t)1 << 51) - 1)) << 3)
+#define nan_unbox(dbl) nan_unbox_uint(((union double_uint64){ .d = (dbl) }).u64)
+
end
end
@@ -57,11 +75,23 @@ double_literal_printer(jitter_print_context ctx, uintptr_t n)
jitter_print_double(ctx, d);
}
+static void
+var_literal_printer(jitter_print_context ctx, uintptr_t n)
+{
+ double d;
+
+ memcpy(&d, &n, sizeof(n));
+ n = nan_unbox(d); // reusing `n`
+ jitter_print_char_star(ctx, (const char*)n);
+}
+
end
end
# Stack manipulation
+# Push a double on the stack
+# Stack: ( -- a)
instruction push (?n double_literal_printer)
code
uintptr_t n = JITTER_ARGN0;
@@ -72,19 +102,47 @@ instruction push (?n double_literal_printer)
end
end
+# Pop the value on stack and save it into `result` field
+# Stack: (a -- )
instruction pop ()
code
- TOCTAVE_STATE_RUNTIME_FIELD (result) = TOCTAVE_TOP_MAINSTACK();
+ TOCTAVE_STATE_RUNTIME_FIELD(result) = TOCTAVE_TOP_MAINSTACK();
TOCTAVE_DROP_MAINSTACK();
end
end
+# Drop the value on stack
+# Stack: (a -- )
instruction drop ()
code
TOCTAVE_DROP_MAINSTACK();
end
end
+# Push the value of variable onto the stack
+# Stack: ( -- a)
+instruction pushvar (?n var_literal_printer)
+ code
+ const char* name = (const char*)nan_unbox_uint(JITTER_ARGN0);
+ // For simplicity, we assume the variable is defined
+ double d = toctave_var(TOCTAVE_STATE_RUNTIME_FIELD(env), name);
+
+ TOCTAVE_PUSH_MAINSTACK(d);
+ end
+end
+
+# Pop the value on the stack and save it into variable
+# Stack: (a -- )
+instruction popvar (?n var_literal_printer)
+ code
+ const char* name = (const char*)nan_unbox_uint(JITTER_ARGN0);
+
+ toctave_var_set(
+ TOCTAVE_STATE_RUNTIME_FIELD(env), name, TOCTAVE_TOP_MAINSTACK());
+ TOCTAVE_DROP_MAINSTACK();
+ end
+end
+
# Arithmetic
# Stack: (a b -- a^b)
