From bbaf58c9fd0f485266d86868dc35f1d2be3589cd Mon Sep 17 00:00:00 2001
From: Julian Blake Kongslie
Date: Sun, 26 Jun 2022 16:24:13 -0700
Subject: Significant changes, and a working "ISA" that just computes fib(n).

---
 aisa/aisa.h          |  52 +++++++++++-
 aisa/async.h         | 225 +++++++++++++++++++++++++++++++++++++++++++++++++++
 aisa/eval.h          |  65 ---------------
 aisa/simple-models.h |  95 ++++++++++++++++++++++
 4 files changed, 371 insertions(+), 66 deletions(-)
 create mode 100644 aisa/async.h
 delete mode 100644 aisa/eval.h
 create mode 100644 aisa/simple-models.h

(limited to 'aisa')

diff --git a/aisa/aisa.h b/aisa/aisa.h
index 3c260c1..4488529 100644
--- a/aisa/aisa.h
+++ b/aisa/aisa.h
@@ -1,20 +1,67 @@
 #pragma once
 
 #include <cstdint>
+#include <memory>
 #include <optional>
+#include <string>
 #include <utility>
 #include <vector>
 
 namespace aisa {
 
+    using addr_t = std::uint64_t;
+    using byte_t = std::uint8_t;
     using regnum_t = std::uint_fast64_t;
     using regval_t = std::uint64_t;
 
+    struct Task;
+
+    struct ISA {
+        virtual ~ISA() { }
+
+        virtual std::pair<std::unique_ptr<const Task>, regval_t> initial_task() const = 0;
+    };
+
+    struct Step;
+
+    struct Task {
+        regnum_t environment;
+
+        virtual ~Task() { }
+
+        virtual std::string disasm() const = 0;
+
+        virtual std::optional<std::pair<std::unique_ptr<const Step>, regval_t>> step(regval_t environment_val) const { return {}; }
+    };
+
+    struct MemInfo {
+        addr_t physical_addr;
+        addr_t size;
+    };
+
+    struct Wires {
+        std::vector<regval_t> source_vals;
+        std::vector<byte_t> memory_val;
+        bool aborted = false;
+        std::vector<regval_t> destination_vals;
+        std::optional<std::pair<std::unique_ptr<const Task>, regval_t>> new_task;
+    };
+
+    enum class MOp {
+        NONE,
+        LOAD,
+        STORE,
+    };
+
     struct Step {
         std::optional<std::pair<regnum_t, regval_t>> predicate;
         std::vector<regnum_t> source_regs;
         std::vector<regnum_t> destination_regs;
 
+        virtual ~Step() { }
+
+        virtual std::string disasm(const Wires *w = nullptr) const = 0;
+
         std::optional<regnum_t> predicate_reg() const
         {
             if (predicate.has_value())
@@ -29,7 +76,10 @@ namespace aisa {
             return {};
         }
 
-        virtual std::vector<regval_t> compute_destinations(const std::vector<regval_t> &source_vals) const = 0;
+        MOp mop = MOp::NONE;
+
+        virtual MemInfo meminfo(const Wires &wires) const { return {}; }
+        virtual void evaluate(Wires &wires) const { };
     };
 
 }
diff --git a/aisa/async.h b/aisa/async.h
new file mode 100644
index 0000000..42e99e7
--- /dev/null
+++ b/aisa/async.h
@@ -0,0 +1,225 @@
+#pragma once
+
+#include <coroutine>
+#include <optional>
+#include <utility>
+#include <memory>
+#include <vector>
+
+#include "aisa/aisa.h"
+#include "aisa/coroutine.h" // IWYU pragma: export
+
+namespace aisa {
+
+    template<typename CRTP> struct AsyncEval {
+        CRTP & crtp() noexcept { return static_cast<CRTP &>(*this); }
+
+        task<regval_t> async_load_reg(regnum_t rn)
+        {
+            while (true) {
+                if (auto rv = crtp().load_reg(rn); rv.has_value())
+                    co_return *rv;
+                co_await std::suspend_always{};
+            }
+        }
+
+        task<void> async_store_reg(regnum_t rn, regval_t rv)
+        {
+            while (true) {
+                if (crtp().store_reg(rn, rv))
+                    co_return;
+                co_await std::suspend_always{};
+            }
+        }
+
+        task<void> async_fetch_mem(byte_t *bytes, addr_t physical_addr, addr_t size)
+        {
+            while (true) {
+                if (crtp().fetch_mem(bytes, physical_addr, size))
+                    co_return;
+                co_await std::suspend_always{};
+            }
+        }
+
+        task<void> async_store_mem(addr_t physical_addr, const byte_t *bytes, addr_t size)
+        {
+            while (true) {
+                if (crtp().store_mem(physical_addr, bytes, size))
+                    co_return;
+                co_await std::suspend_always{};
+            }
+        }
+
+        task<bool> async_predicate(const Step &step)
+        {
+            if (step.predicate.has_value()) {
+                regval_t pval = co_await crtp().async_load_reg(step.predicate->first);
+                co_return pval == step.predicate->second;
+            }
+            co_return true;
+        }
+
+        task<void> async_load_source_registers(const Step &step, Wires &w)
+        {
+            w.source_vals.resize(step.source_regs.size());
+            for (unsigned int i = 0; i < step.source_regs.size(); ++i)
+                w.source_vals[i] = co_await crtp().async_load_reg(step.source_regs[i]);
+        }
+
+        task<void> async_load_source_memory(const Step &step, const MemInfo &mi, Wires &w)
+        {
+            w.memory_val.resize(mi.size);
+            co_await crtp().async_fetch_mem(w.memory_val.data(), mi.physical_addr, mi.size);
+        }
+
+        task<void> async_load_sources(const Step &step, Wires &w)
+        {
+            co_await crtp().async_load_source_registers(step, w);
+
+            if (step.mop == MOp::LOAD) {
+                auto mi = step.meminfo(w);
+                co_await crtp().async_load_source_memory(step, mi, w);
+            }
+        }
+
+        task<void> async_write_destination_registers(const Step &step, const Wires &w)
+        {
+            for (unsigned int i = 0; i < step.destination_regs.size(); ++i)
+                co_await crtp().async_store_reg(step.destination_regs[i], w.destination_vals[i]);
+        }
+
+        task<void> async_write_destination_memory(const Step &step, const MemInfo &mi, const Wires &w)
+        {
+            co_await crtp().async_store_mem(mi.physical_addr, w.memory_val.data(), mi.size);
+        }
+
+        task<void> async_write_destinations(const Step &step, const Wires &w)
+        {
+            if (w.aborted)
+                co_return;
+
+            co_await crtp().async_write_destination_registers(step, w);
+
+            if (step.mop == MOp::STORE) {
+                auto mi = step.meminfo(w);
+                co_await crtp().async_write_destination_memory(step, mi, w);
+            }
+        }
+
+        task<void> async_push_task(std::unique_ptr<const Task> &&task)
+        {
+            while (true) {
+                if (crtp().push_task(std::move(task)))
+                    co_return;
+                co_await std::suspend_always{};
+            }
+        }
+
+        task<void> async_new_task(std::unique_ptr<const Task> &&task, regval_t environment_val)
+        {
+            auto rn = task->environment;
+            co_await crtp().async_push_task(std::move(task));
+            co_await crtp().async_store_reg(rn, environment_val);
+        }
+
+        task<Wires> async_run_step(const Step &step)
+        {
+            Wires w;
+
+            if (!co_await crtp().async_predicate(step))
+                co_return std::move(w);
+
+            co_await crtp().async_load_sources(step, w);
+
+            step.evaluate(w);
+
+            co_await crtp().async_write_destinations(step, w);
+
+            if (w.new_task.has_value())
+                co_await crtp().async_new_task(std::move(w.new_task->first), w.new_task->second);
+
+            co_return std::move(w);
+        }
+
+        task<const Task *> async_top_task()
+        {
+            while (true) {
+                if (auto rv = crtp().top_task(); rv.has_value())
+                    co_return &**rv;
+                co_await std::suspend_always{};
+            }
+        }
+
+        task<void> async_pop_task()
+        {
+            while (true) {
+                if (crtp().pop_task())
+                    co_return;
+                co_await std::suspend_always{};
+            }
+        }
+
+        task<std::optional<std::unique_ptr<const Step>>> async_fetch_step()
+        {
+            auto task = co_await crtp().async_top_task();
+
+            auto rn = task->environment;
+            auto rv = co_await crtp().async_load_reg(rn);
+
+            auto step = task->step(rv);
+            if (step.has_value()) {
+                co_await crtp().async_store_reg(rn, step->second);
+                co_return std::move(step->first);
+            } else {
+                co_await crtp().async_pop_task();
+                co_return {};
+            }
+        }
+
+        task<std::pair<std::unique_ptr<const Step>, Wires>> async_fetch_and_run_step()
+        {
+            while (true) {
+                if (auto step = co_await crtp().async_fetch_step(); step.has_value()) {
+                    auto wires = co_await crtp().async_run_step(**step);
+                    co_return {std::move(*step), std::move(wires)};
+                }
+            }
+        }
+
+        task<void> async_run_subtree()
+        {
+            while (true) {
+                if (auto step = co_await crtp().async_fetch_step(); step.has_value())
+                    co_await crtp().async_run_step_and_subtree(**step);
+                else
+                    break;
+            }
+        }
+
+        task<Wires> async_run_step_and_subtree(const Step &step)
+        {
+            auto w = co_await crtp().async_run_step(step);
+
+            if (w.new_task.has_value())
+                co_await crtp().async_run_subtree();
+
+            co_return std::move(w);
+        }
+
+        task<void> async_setup_initial_task(const ISA &isa)
+        {
+            auto task = isa.initial_task();
+
+            co_await crtp().async_new_task(std::move(task.first), task.second);
+        }
+
+        task<void> async_run(const ISA &isa)
+        {
+            co_await crtp().async_setup_initial_task(isa);
+
+            co_await crtp().async_run_subtree();
+        }
+
+    };
+
+}
diff --git a/aisa/eval.h b/aisa/eval.h
deleted file mode 100644
index a301e93..0000000
--- a/aisa/eval.h
+++ /dev/null
@@ -1,65 +0,0 @@
-#pragma once
-
-#include <coroutine>
-#include <memory>
-#include <optional>
-#include <utility>
-#include <vector>
-
-#include "aisa/aisa.h"
-#include "aisa/coroutine.h" // IWYU pragma: export
-
-namespace aisa {
-
-    template<typename CRTP> struct EvalState {
-        struct EvalContext {
-            task<void> coroutine;
-
-            bool resume() { return coroutine(); }
-        };
-
-        CRTP & crtp() noexcept { return static_cast<CRTP &>(*this); }
-
-        task<regval_t> async_load_reg(regnum_t rn)
-        {
-            while (true) {
-                if (auto rv = crtp().load_reg(rn); rv.has_value())
-                    co_return *rv;
-                co_await std::suspend_always{};
-            }
-        }
-
-        task<void> async_store_reg(regnum_t rn, regval_t rv)
-        {
-            while (true) {
-                if (crtp().store_reg(rn, rv))
-                    co_return;
-                co_await std::suspend_always{};
-            }
-        }
-
-        task<void> async_evaluate(EvalContext &contex, const Step &step)
-        {
-            if (step.predicate.has_value()) {
-                regval_t pval = co_await async_load_reg(step.predicate->first);
-                if (pval != step.predicate->second)
-                    co_return;
-            }
-            std::vector<regval_t> source_vals;
-            source_vals.reserve(step.source_regs.size());
-            for (unsigned int i = 0; i < step.source_regs.size(); ++i)
-                source_vals.emplace_back(co_await async_load_reg(step.source_regs[i]));
-            auto destination_vals = step.compute_destinations(source_vals);
-            for (unsigned int i = 0; i < step.destination_regs.size(); ++i)
-                co_await async_store_reg(step.destination_regs[i], destination_vals[i]);
-        }
-
-        std::unique_ptr<EvalContext> operator()(const Step &step)
-        {
-            auto context = std::make_unique<EvalContext>();
-            context->coroutine = async_evaluate(*context, step);
-            return context;
-        }
-    };
-
-}
diff --git a/aisa/simple-models.h b/aisa/simple-models.h
new file mode 100644
index 0000000..89e8752
--- /dev/null
+++ b/aisa/simple-models.h
@@ -0,0 +1,95 @@
+#pragma once
+
+#include <algorithm>
+#include <array>
+#include <cstring>
+#include <deque>
+#include <map>
+#include <memory>
+#include <optional>
+#include <utility>
+#include <vector>
+
+#include "aisa/aisa.h"
+
+namespace aisa {
+
+    template<unsigned int PAGE_BITS=10> struct PagedMem {
+        using page_t = std::array<byte_t, 1 << PAGE_BITS>;
+
+        static const addr_t PAGE_SIZE = 1 << PAGE_BITS;
+        static const addr_t PAGE_MASK = PAGE_SIZE - 1;
+
+        std::map<addr_t, page_t> pages;
+
+        bool fetch_mem(byte_t *bytes, addr_t addr, addr_t size)
+        {
+            if (size == 0)
+                return true;
+            auto page_base = addr >> PAGE_BITS;
+            auto page_offset = addr & PAGE_MASK;
+            auto size_here = std::min(size, PAGE_SIZE - page_offset);
+            if (auto page = pages.find(page_base); page != pages.end())
+                std::memcpy(bytes, page->second.data() + page_offset, size_here);
+            else
+                std::memset(bytes, 0, size_here);
+            return fetch_mem(bytes + size_here, addr + size_here, size - size_here);
+        }
+
+        bool store_mem(addr_t addr, const byte_t *bytes, addr_t size)
+        {
+            if (size == 0)
+                return true;
+            auto page_base = addr >> PAGE_BITS;
+            auto page_offset = addr & PAGE_MASK;
+            auto size_here = std::min(size, PAGE_SIZE - page_offset);
+            std::memcpy(pages[page_base].data() + page_offset, bytes, size_here);
+            return store_mem(addr + size_here, bytes + size_here, size - size_here);
+        }
+    };
+
+    struct TaskStack {
+        std::deque<std::unique_ptr<const Task>> tasks;
+
+        bool pop_task()
+        {
+            if (tasks.empty())
+                return false;
+            tasks.pop_back();
+            return true;
+        }
+
+        bool push_task(std::unique_ptr<const Task> &&task)
+        {
+            tasks.emplace_back(std::move(task));
+            return true;
+        }
+
+        std::optional<const Task *> top_task()
+        {
+            if (tasks.empty())
+                return {};
+            return tasks.back().get();
+        }
+    };
+
+    struct VectorRF {
+        std::vector<std::optional<regval_t>> rf;
+
+        std::optional<regval_t> load_reg(regnum_t rn) const
+        {
+            if (rf.size() <= rn)
+                return {};
+            return rf[rn];
+        }
+
+        bool store_reg(regnum_t rn, regval_t rv)
+        {
+            if (rf.size() <= rn)
+                rf.resize(rn + 1);
+            rf[rn] = rv;
+            return true;
+        }
+    };
+
+}
-- 
cgit v1.2.3