From c72951a36d6cb9775dc1ecd9bc26bc13e796f10c Mon Sep 17 00:00:00 2001 From: Julian Blake Kongslie Date: Sat, 2 Jul 2022 13:45:09 -0700 Subject: Dropping the async interface, and adding some real uarch. --- Makefile | 3 +- aisa/aisa.cpp | 6 ++ aisa/aisa.h | 20 +---- aisa/async.h | 225 ------------------------------------------------- aisa/coroutine.h | 119 -------------------------- aisa/simple-models.cpp | 49 +++++++++++ aisa/simple-models.h | 39 ++------- fib/fib.cpp | 51 ++++++++--- fib/fib.h | 1 + main.cpp | 116 +++++-------------------- sim/queue.h | 87 +++++++++++++++++++ sim/sim.cpp | 83 ++++++++++++++++++ sim/sim.d | 1 + sim/sim.h | 44 ++++++++++ uarch/exec.cpp | 138 ++++++++++++++++++++++++++++++ uarch/exec.h | 29 +++++++ uarch/fetch.cpp | 129 ++++++++++++++++++++++++++++ uarch/fetch.h | 28 ++++++ uarch/memory.cpp | 46 ++++++++++ uarch/memory.h | 21 +++++ uarch/types.h | 30 +++++++ uarch/uarch.d | 2 + util/assert.cpp | 12 +++ util/assert.h | 3 + 24 files changed, 777 insertions(+), 505 deletions(-) delete mode 100644 aisa/async.h delete mode 100644 aisa/coroutine.h create mode 100644 aisa/simple-models.cpp create mode 100644 sim/queue.h create mode 100644 sim/sim.cpp create mode 100644 sim/sim.d create mode 100644 sim/sim.h create mode 100644 uarch/exec.cpp create mode 100644 uarch/exec.h create mode 100644 uarch/fetch.cpp create mode 100644 uarch/fetch.h create mode 100644 uarch/memory.cpp create mode 100644 uarch/memory.h create mode 100644 uarch/types.h create mode 100644 uarch/uarch.d create mode 100644 util/assert.cpp create mode 100644 util/assert.h diff --git a/Makefile b/Makefile index 0d154a8..f8e983b 100644 --- a/Makefile +++ b/Makefile @@ -85,11 +85,10 @@ $(foreach part,${PARTS},$(eval $(call mklib,${part}))) ifdef iwyu -build/iwyu.cpp: +build/iwyu.cpp: $(wildcard *.h) @mkdir -p $(dir $@) @tools/iwyu-header $(wildcard *.h) > $@ @$(call iwyu,$@) -.PHONY: build/iwyu.cpp IWYU_CPPS += build/iwyu.cpp diff --git a/aisa/aisa.cpp b/aisa/aisa.cpp index 811c882..8c8cd1e 100644 --- a/aisa/aisa.cpp +++ b/aisa/aisa.cpp @@ -6,6 +6,12 @@ namespace aisa { + ISA::~ISA() { } + + Task::~Task() { } + + Step::~Step() { } + std::optional, regval_t>> Task::step(regval_t environment_val) const { return {}; } MemInfo Step::meminfo(const Wires &wires) const { return {}; } diff --git a/aisa/aisa.h b/aisa/aisa.h index e4e1074..a986cd7 100644 --- a/aisa/aisa.h +++ b/aisa/aisa.h @@ -17,7 +17,7 @@ namespace aisa { struct Task; struct ISA { - virtual ~ISA() { } + virtual ~ISA(); virtual std::pair, regval_t> initial_task() const = 0; }; @@ -27,7 +27,7 @@ namespace aisa { struct Task { regnum_t environment; - virtual ~Task() { } + virtual ~Task(); virtual std::string disasm() const = 0; @@ -58,24 +58,10 @@ namespace aisa { std::vector source_regs; std::vector destination_regs; - virtual ~Step() { } + virtual ~Step(); virtual std::string disasm(const Wires *w = nullptr) const = 0; - std::optional predicate_reg() const - { - if (predicate.has_value()) - return predicate->first; - return {}; - } - - std::optional expected_predicate_val() const - { - if (predicate.has_value()) - return predicate->second; - return {}; - } - MOp mop = MOp::NONE; virtual MemInfo meminfo(const Wires &wires) const; diff --git a/aisa/async.h b/aisa/async.h deleted file mode 100644 index 42e99e7..0000000 --- a/aisa/async.h +++ /dev/null @@ -1,225 +0,0 @@ -#pragma once - -#include -#include -#include -#include -#include - -#include "aisa/aisa.h" -#include "aisa/coroutine.h" // IWYU pragma: export - -namespace aisa { - - template struct AsyncEval { - CRTP & crtp() noexcept { return static_cast(*this); } - - task 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 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 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 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 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 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 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 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 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 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 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 async_push_task(std::unique_ptr &&task) - { - while (true) { - if (crtp().push_task(std::move(task))) - co_return; - co_await std::suspend_always{}; - } - } - - task async_new_task(std::unique_ptr &&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 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 async_top_task() - { - while (true) { - if (auto rv = crtp().top_task(); rv.has_value()) - co_return &**rv; - co_await std::suspend_always{}; - } - } - - task async_pop_task() - { - while (true) { - if (crtp().pop_task()) - co_return; - co_await std::suspend_always{}; - } - } - - task>> 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, 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 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 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 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 async_run(const ISA &isa) - { - co_await crtp().async_setup_initial_task(isa); - - co_await crtp().async_run_subtree(); - } - - }; - -} diff --git a/aisa/coroutine.h b/aisa/coroutine.h deleted file mode 100644 index 1b55362..0000000 --- a/aisa/coroutine.h +++ /dev/null @@ -1,119 +0,0 @@ -#pragma once - -#include -#include - -namespace aisa { - - template struct task_promise; - - template struct task : public std::coroutine_handle> { - using handle = std::coroutine_handle>; - using promise_type = task_promise; - bool await_ready() const noexcept { return handle::done(); } - result_t await_resume() const noexcept; - template void await_suspend(std::coroutine_handle> h) const noexcept; - std::optional operator()() noexcept; - }; - - template<> struct task : public std::coroutine_handle> { - using handle = std::coroutine_handle>; - using promise_type = task_promise; - bool await_ready() const noexcept { return handle::done(); } - void await_resume() const noexcept; - template void await_suspend(std::coroutine_handle> h) const noexcept; - bool operator()() noexcept; - }; - - template struct task_promise { - std::coroutine_handle<> precursor; - std::optional result; - task_promise() = default; - task_promise(const task_promise &) = delete; - task get_return_object() noexcept { return task{std::coroutine_handle>::from_promise(*this)}; } - std::suspend_never initial_suspend() const noexcept { return {}; } - std::suspend_always final_suspend() const noexcept { return {}; } - void unhandled_exception() { } - void return_value(result_t x) noexcept { result = std::move(x); } - }; - - template<> struct task_promise { - std::coroutine_handle<> precursor; - task_promise() = default; - task_promise(const task_promise &) = delete; - task get_return_object() noexcept { return task{std::coroutine_handle>::from_promise(*this)}; } - std::suspend_never initial_suspend() const noexcept { return {}; } - std::suspend_always final_suspend() const noexcept { return {}; } - void unhandled_exception() { } - void return_void() noexcept { } - }; - - template result_t task::await_resume() const noexcept - { - auto x = std::move(handle::promise().result.value()); - handle::destroy(); - return x; - } - - template template void task::await_suspend(std::coroutine_handle> h) const noexcept - { - h.promise().precursor = *this; - } - - template std::optional task::operator()() noexcept - { - if (!handle::operator bool()) - return {}; - if (!handle::done()) { - auto &precursor = handle::promise().precursor; - if (precursor) { - if (!precursor.done()) - precursor.resume(); - if (precursor.done()) - precursor = nullptr; - } - if (!precursor) - handle::resume(); - } - if (handle::done()) { - auto x = await_resume(); - handle::operator=(nullptr); - return x; - } - return {}; - } - - inline void task::await_resume() const noexcept - { - handle::destroy(); - } - - template void task::await_suspend(std::coroutine_handle> h) const noexcept - { - h.promise().precursor = *this; - } - - inline bool task::operator()() noexcept - { - if (!handle::operator bool()) - return true; - if (!handle::done()) { - auto &precursor = handle::promise().precursor; - if (precursor) { - if (!precursor.done()) - precursor.resume(); - if (precursor.done()) - precursor = nullptr; - } - if (!precursor) - handle::resume(); - } - if (handle::done()) { - await_resume(); - handle::operator=(nullptr); - return true; - } - return false; - } - -} diff --git a/aisa/simple-models.cpp b/aisa/simple-models.cpp new file mode 100644 index 0000000..b69dcb7 --- /dev/null +++ b/aisa/simple-models.cpp @@ -0,0 +1,49 @@ +#include +#include +#include +#include +#include +#include + +#include "aisa/aisa.h" +#include "aisa/simple-models.h" + +namespace aisa { + + bool TaskStack::pop_task() + { + if (tasks.empty()) + return false; + tasks.pop_back(); + return true; + } + + bool TaskStack::push_task(std::unique_ptr &&task) + { + tasks.emplace_back(std::move(task)); + return true; + } + + std::optional TaskStack::top_task() + { + if (tasks.empty()) + return {}; + return tasks.back().get(); + } + + std::optional VectorRF::load_reg(regnum_t rn) const + { + if (rf.size() <= rn) + return {}; + return rf[rn]; + } + + bool VectorRF::store_reg(regnum_t rn, regval_t rv) + { + if (rf.size() <= rn) + rf.resize(rn + 1); + rf[rn] = rv; + return true; + } + +} diff --git a/aisa/simple-models.h b/aisa/simple-models.h index 62b5388..a94f010 100644 --- a/aisa/simple-models.h +++ b/aisa/simple-models.h @@ -7,7 +7,6 @@ #include #include #include -#include #include #include "aisa/aisa.h" @@ -51,45 +50,17 @@ namespace aisa { struct TaskStack { std::deque> tasks; - bool pop_task() - { - if (tasks.empty()) - return false; - tasks.pop_back(); - return true; - } - - bool push_task(std::unique_ptr &&task) - { - tasks.emplace_back(std::move(task)); - return true; - } + bool pop_task(); + bool push_task(std::unique_ptr &&task); - std::optional top_task() - { - if (tasks.empty()) - return {}; - return tasks.back().get(); - } + std::optional top_task(); }; struct VectorRF { std::vector> rf; - std::optional 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; - } + std::optional load_reg(regnum_t rn) const; + bool store_reg(regnum_t rn, regval_t rv); }; } diff --git a/fib/fib.cpp b/fib/fib.cpp index 8ff7718..8e0cdf2 100644 --- a/fib/fib.cpp +++ b/fib/fib.cpp @@ -225,12 +225,39 @@ namespace fib { std::optional, aisa::regval_t>> step(aisa::regval_t env) const override { switch (env) { - case 0: return {{std::make_unique>(Reg::A, Reg::PC), env+1}}; - case 1: return {{std::make_unique(Reg::PC, Reg::PC, 1), env+1}}; - case 2: return {{std::make_unique>(Reg::B, Reg::PC), env+1}}; - case 3: return {{std::make_unique(Reg::AREG, Reg::PC, 1), env+1}}; - case 4: return {{std::make_unique(Reg::Q, Reg::A, Reg::B), env+1}}; - case 5: return {{std::make_unique>(Reg::AREG, Reg::Q), env+1}}; + case 0: return {{std::make_unique(Reg::AREG, Reg::PC), env+1}}; + case 1: return {{std::make_unique>(Reg::A, Reg::AREG), env+1}}; + case 2: return {{std::make_unique(Reg::AREG, Reg::AREG, 1), env+1}}; + case 3: return {{std::make_unique>(Reg::B, Reg::AREG), env+1}}; + case 4: return {{std::make_unique(Reg::AREG, Reg::AREG, 1), env+1}}; + case 5: return {{std::make_unique(Reg::Q, Reg::A, Reg::B), env+1}}; + case 6: return {{std::make_unique>(Reg::AREG, Reg::Q), env+1}}; + } + + return {}; + } + }; + + template struct TaskInit : public aisa::Task { + TaskInit() + { + environment = Reg::ENV_INIT; + } + + std::string disasm() const override + { + return "init"; + } + + std::optional, aisa::regval_t>> step(aisa::regval_t env) const override + { + switch(env) { + case 0: return {{std::make_unique(Reg::AREG, 0), env+1}}; + case 1: return {{std::make_unique(Reg::ATMP, 0), env+1}}; + case 2: return {{std::make_unique>(Reg::AREG, Reg::ATMP), env+1}}; + case 3: return {{std::make_unique(Reg::AREG, 1), env+1}}; + case 4: return {{std::make_unique(Reg::ATMP, 1), env+1}}; + case 5: return {{std::make_unique>(Reg::AREG, Reg::ATMP), env+1}}; } return {}; @@ -251,14 +278,10 @@ namespace fib { std::optional, aisa::regval_t>> step(aisa::regval_t env) const override { switch (env) { - case 0: return {{std::make_unique(Reg::PC, 0), env+1}}; - case 1: return {{std::make_unique(Reg::AREG, 0), env+1}}; - case 2: return {{std::make_unique(Reg::ATMP, 0), env+1}}; - case 3: return {{std::make_unique>(Reg::AREG, Reg::ATMP), env+1}}; - case 4: return {{std::make_unique(Reg::AREG, 1), env+1}}; - case 5: return {{std::make_unique(Reg::ATMP, 1), env+1}}; - case 6: return {{std::make_unique>(Reg::AREG, Reg::ATMP), env+1}}; - case 7: return {{std::make_unique>>(), env}}; + case 0: return {{std::make_unique>>(), env+1}}; + case 1: return {{std::make_unique(Reg::PC, 0), env+1}}; + case 2: return {{std::make_unique>>(), env+1}}; + case 3: return {{std::make_unique(Reg::PC, Reg::PC, 1), env-1}}; } return {}; diff --git a/fib/fib.h b/fib/fib.h index 6719d06..25afdc4 100644 --- a/fib/fib.h +++ b/fib/fib.h @@ -11,6 +11,7 @@ namespace fib { enum { ENV_TOP, + ENV_INIT, ENV_FIB, AREG, diff --git a/main.cpp b/main.cpp index edb0d56..358b954 100644 --- a/main.cpp +++ b/main.cpp @@ -1,113 +1,41 @@ -#include #include -#include -#include #include -#include "aisa/aisa.h" -#include "aisa/async.h" -#include "aisa/simple-models.h" #include "fib/fib.h" #include "git-tag.h" - -const unsigned int max_steps = 300; -const bool show_mem_fetch = false; -const bool show_mem_store = true; -const bool show_regs = false; -const bool show_steps = false; -const bool show_tasks = false; +#include "sim/sim.h" +#include "sim/queue.h" +#include "uarch/exec.h" +#include "uarch/fetch.h" +#include "uarch/memory.h" +#include "uarch/types.h" int main(int argc, const char *argv[]) { std::cout << "Version " << GIT_TAG << "\n"; - struct Eval : public aisa::AsyncEval, aisa::PagedMem<>, aisa::TaskStack, aisa::VectorRF { - bool fetch_mem(aisa::byte_t *bytes, aisa::addr_t addr, aisa::addr_t size) - { - if (aisa::PagedMem<>::fetch_mem(bytes, addr, size)) { - if (show_mem_fetch) { - fmt::print("\t\t\t"); - for (; size; --size) - fmt::print("{:02x} ", *bytes++); - fmt::print("= [{:x}]\n", addr); - } - return true; - } - return false; - } - - bool store_mem(aisa::addr_t addr, const aisa::byte_t *bytes, aisa::addr_t size) - { - if (aisa::PagedMem<>::store_mem(addr, bytes, size)) { - if (show_mem_store) { - fmt::print("\t\t\t[{:x}] =", addr); - for (; size; --size) - fmt::print(" {:02x}", *bytes++); - fmt::print("\n"); - } - return true; - } - return false; - } - - bool store_reg(aisa::regnum_t rn, aisa::regval_t rv) - { - if (aisa::VectorRF::store_reg(rn, rv)) { - if (show_regs) - fmt::print(".{} = {}\n", fib::Reg::disasm(rn), rv); - return true; - } - return false; - } - - bool push_task(std::unique_ptr &&task) - { - auto d = task->disasm(); - if (aisa::TaskStack::push_task(std::move(task))) { - if (show_tasks) - fmt::print("\t\t*** ENTER {} ***\n", d); - return true; - } - return false; - } + fib::Fib<3> fib; - bool pop_task() - { - if (aisa::TaskStack::pop_task()) { - if (show_tasks) - fmt::print("\t\t *** LEAVE ***\n"); - return true; - } - return false; - } - } eval; + sim::Scheduler sched; - fib::Fib<3> fib; + sim::Queue fillreqq(sched, 1); + sim::Queue fillfetchq(sched, 0); + sim::Queue fillexecq(sched, 0); + sim::Queue storeq(sched, 1); + sim::Queue execq(sched, 0); - if (!eval.async_setup_initial_task(fib)()) { - fmt::print("Failed to complete initial setup.\n"); - return 1; - } + auto fetch = new uarch::FetchStage(sched, fib, fillreqq, fillfetchq, execq); + auto exec = new uarch::ExecStage(sched, execq, fillreqq, fillexecq, storeq); + auto mem = new uarch::MemStage(sched, fillreqq, {&fillfetchq, &fillexecq}, storeq); - for (unsigned int i = 0; i < max_steps; ++i) { - auto res = eval.async_fetch_and_run_step()(); - if (res.has_value()) { - auto &es = *res; - if (es.first) { - auto &step = *es.first; - auto &w = es.second; - if (show_steps) - fmt::print("\t{}\n", step.disasm(&w)); - } else { - break; - } - } else { - fmt::print("Failed to complete step.\n"); - return 2; - } + while (true) { + std::cout << "\n*** cycle " << sched.now << "\n\n"; + sched.clock(); } - fmt::print("Functional model exited.\n"); + delete fetch; + delete exec; + delete mem; return 0; } diff --git a/sim/queue.h b/sim/queue.h new file mode 100644 index 0000000..890beb6 --- /dev/null +++ b/sim/queue.h @@ -0,0 +1,87 @@ +#pragma once + +#include +#include // IWYU pragma: keep +#include +#include + +#include "sim/sim.h" +#include "util/assert.h" + +namespace sim { + + template struct Queue { + Scheduler &scheduler; + + Schedulable *reader = nullptr; + std::set writers; + + unsigned int min_latency; + + std::multimap waiting; + + Queue(Scheduler &scheduler, unsigned int min_latency) + : scheduler(scheduler) + , min_latency(min_latency) + { } + + void add_reader(Schedulable *x) + { + ASSERT(&x->scheduler == &scheduler, "Reader associated with incorrect Scheduler"); + ASSERT(!reader, "Already have a reader"); + reader = x; + if (min_latency == 0) { + for (const auto &w : writers) + scheduler.constrain(w, reader); + } + } + + void add_writer(Schedulable *x) + { + ASSERT(&x->scheduler == &scheduler, "Writer associated with incorrect Scheduler"); + writers.emplace(x); + if (min_latency == 0 && reader) + scheduler.constrain(x, reader); + } + + void write(Element &&x) + { + write(std::move(x), min_latency); + } + + void write(Element &&x, unsigned int latency) + { + ASSERT(latency >= min_latency, "Latency too low"); + ASSERT(!scheduler.current_schedulable || writers.count(scheduler.current_schedulable), "Write lacks permission"); + waiting.emplace(scheduler.now + min_latency, std::move(x)); + } + + unsigned int available() + { + ASSERT(!scheduler.current_schedulable || reader == scheduler.current_schedulable, "Read lacks permission"); + unsigned int c = 0; + for (auto x = waiting.begin(); x != waiting.end() && x->first <= scheduler.now; ++x) + ++c; + return c; + } + + Element &peek(unsigned int i=0) + { + ASSERT(i < available(), "Peek past available elements"); + auto x = waiting.begin(); + std::advance(x, i); + return x->second; + } + + Element read(unsigned int i=0) + { + ASSERT(i < available(), "Read past available elements"); + auto x = waiting.begin(); + std::advance(x, i); + Element e{std::move(x->second)}; + waiting.erase(x); + return e; + } + }; + +} diff --git a/sim/sim.cpp b/sim/sim.cpp new file mode 100644 index 0000000..e8f84ee --- /dev/null +++ b/sim/sim.cpp @@ -0,0 +1,83 @@ +#include + +#include "sim/sim.h" +#include "util/assert.h" + +namespace sim { + + void Scheduler::add_schedulable(Schedulable *schedulable) + { + unsorted_schedulables.emplace(schedulable); + sort_needed = true; + } + + void Scheduler::remove_schedulable(Schedulable *schedulable) + { + unsorted_schedulables.erase(schedulable); + std::erase_if(constraints, [schedulable](const auto &item) { return item.first == schedulable || item.second == schedulable; }); + sort_needed = true; + } + + void Scheduler::constrain(Schedulable *prior, Schedulable *later) + { + ASSERT(unsorted_schedulables.count(prior), "Constraint prior is not associated with this Scheduler"); + ASSERT(unsorted_schedulables.count(later), "Constraint later is not associated with this Scheduler"); + constraints.emplace(later, prior); + sort_needed = true; + } + + void Scheduler::topo_sort(std::set &live, std::set &waiting, Schedulable *candidate) + { + ASSERT(!live.count(candidate), "Dependency loop"); + for (auto prereq = constraints.find(candidate); prereq != constraints.end() && prereq->first == candidate; ++prereq) { + if (prereq->second != candidate && waiting.count(prereq->second)) { + live.emplace(candidate); + topo_sort(live, waiting, prereq->second); + } + } + sorted_schedulables.emplace_back(candidate); + waiting.erase(candidate); + } + + void Scheduler::sort() + { + sorted_schedulables.clear(); + sorted_schedulables.reserve(unsorted_schedulables.size()); + auto waiting = unsorted_schedulables; + while (!waiting.empty()) { + std::set live; + topo_sort(live, waiting, *waiting.begin()); + } + ASSERT(sorted_schedulables.size() == unsorted_schedulables.size(), "Did not sort every schedulable"); + sort_needed = false; + } + + void Scheduler::clock() + { + if (sort_needed) + sort(); + for (const auto &s : sorted_schedulables) { + current_schedulable = s; + s->clock(); + } + current_schedulable = nullptr; + ++now; + } + + Schedulable::Schedulable(Scheduler &scheduler) + : scheduler(scheduler) + { + scheduler.add_schedulable(this); + } + + Schedulable::~Schedulable() + { + scheduler.remove_schedulable(this); + } + + std::uint64_t Schedulable::now() + { + return scheduler.now; + } + +} diff --git a/sim/sim.d b/sim/sim.d new file mode 100644 index 0000000..d8953fb --- /dev/null +++ b/sim/sim.d @@ -0,0 +1 @@ +sim_SODEPS += build/libutil.so diff --git a/sim/sim.h b/sim/sim.h new file mode 100644 index 0000000..399832a --- /dev/null +++ b/sim/sim.h @@ -0,0 +1,44 @@ +#pragma once + +#include +#include +#include +#include + +namespace sim { + + struct Schedulable; + + struct Scheduler { + std::set unsorted_schedulables; + std::vector sorted_schedulables; + bool sort_needed = false; + + std::multimap constraints; + + Schedulable *current_schedulable = nullptr; + std::uint64_t now = 0; + + void add_schedulable(Schedulable *schedulable); + void remove_schedulable(Schedulable *schedulable); + + void constrain(Schedulable *prior, Schedulable *later); + + void topo_sort(std::set &live, std::set &waiting, Schedulable *candidate); + void sort(); + + void clock(); + }; + + struct Schedulable { + Scheduler &scheduler; + + Schedulable(Scheduler &scheduler); + virtual ~Schedulable(); + + virtual void clock() = 0; + + std::uint64_t now(); + }; + +} diff --git a/uarch/exec.cpp b/uarch/exec.cpp new file mode 100644 index 0000000..e40813b --- /dev/null +++ b/uarch/exec.cpp @@ -0,0 +1,138 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "uarch/exec.h" +#include "util/assert.h" + +namespace uarch { + + ExecStage::ExecStage(sim::Scheduler &scheduler, sim::Queue &execq, sim::Queue &fillreqq, sim::Queue &fillq, sim::Queue &storeq) + : sim::Schedulable(scheduler) + , execq(execq) + , fillreqq(fillreqq) + , fillq(fillq) + , storeq(storeq) + { + execq.add_reader(this); + fillreqq.add_writer(this); + fillq.add_reader(this); + storeq.add_writer(this); + } + + void ExecStage::clock() + { + if (tasks.empty() && !step && execq.available()) { + auto uop = execq.read(); + std::cout << "exec accepts uop " << uop.top_task().value()->disasm() << "\n"; + aisa::TaskStack::operator=(std::move(uop)); + aisa::VectorRF::operator=(std::move(uop)); + } + + bool sent_store = false; + while (!sent_store) { + while (!step) { + auto t = top_task(); + if (!t) + goto no_work; + const auto &task = **t; + auto s = task.step(load_reg(task.environment).value()); + if (s.has_value()) { + step = std::move(s->first); + std::cout << "exec step " << step->disasm() << "\n"; + wires = {}; + outstanding_fill = false; + fill_complete = false; + ASSERT(store_reg(task.environment, s->second), "Could not write next environment value"); + } else { + pop_task(); + if (tasks.empty()) + std::cout << "exec completes uop\n"; + } + } + + if (step->predicate.has_value()) { + auto x = load_reg(step->predicate->first); + if (x.has_value()) { + if (*x != step->predicate->second) + goto nextstep; + } else { + std::cout << "exec stalls on predicate register"; + break; + } + } + + wires.source_vals.reserve(step->source_regs.size()); + for (unsigned int i = wires.source_vals.size(); i < step->source_regs.size(); ++i) { + auto x = load_reg(step->source_regs[i]); + if (!x.has_value()) { + std::cout << "exec stalls on source register"; + break; + } + wires.source_vals.emplace_back(*x); + } + + if (step->mop == aisa::MOp::LOAD && !fill_complete) { + auto mi = step->meminfo(wires); + if (outstanding_fill) { + for (unsigned int i = 0; i < fillq.available(); ++i) { + auto &fill = fillq.peek(i); + if (fill.physical_addr == mi.physical_addr) { + std::cout << "exec fills\n"; + wires.memory_val = std::move(fill.bytes); + outstanding_fill = false; + fill_complete = true; + } + } + if (!fill_complete) + break; + } else { + std::cout << "exec sends fill request\n"; + FillReq req; + req.fillq = &fillq; + req.physical_addr = mi.physical_addr; + req.size = mi.size; + fillreqq.write(std::move(req)); + outstanding_fill = true; + fill_complete = false; + break; + } + } + + step->evaluate(wires); + + for (unsigned int i = 0; i < step->destination_regs.size(); ++i) + ASSERT(store_reg(step->destination_regs[i], wires.destination_vals[i]), "Could not write destination register"); + + if (step->mop == aisa::MOp::STORE) { + std::cout << "exec sends store\n"; + auto mi = step->meminfo(wires); + Store store; + store.physical_addr = mi.physical_addr; + store.bytes = std::move(wires.memory_val); + storeq.write(std::move(store)); + //sent_store = true; + } + +nextstep: + step = nullptr; + wires = {}; + outstanding_fill = false; + fill_complete = false; + } + +no_work: + + while (fillq.available()) { + std::cout << "exec consumes fill\n"; + fillq.read(); + } + } + +} diff --git a/uarch/exec.h b/uarch/exec.h new file mode 100644 index 0000000..1cfc525 --- /dev/null +++ b/uarch/exec.h @@ -0,0 +1,29 @@ +#pragma once + +#include + +#include "aisa/aisa.h" +#include "aisa/simple-models.h" +#include "sim/sim.h" +#include "sim/queue.h" +#include "uarch/types.h" + +namespace uarch { + + struct ExecStage : public sim::Schedulable, aisa::TaskStack, aisa::VectorRF { + sim::Queue &execq; + sim::Queue &fillreqq; + sim::Queue &fillq; + sim::Queue &storeq; + + std::unique_ptr step; + aisa::Wires wires; + bool outstanding_fill = false; + bool fill_complete = false; + + ExecStage(sim::Scheduler &scheduler, sim::Queue &execq, sim::Queue &fillreqq, sim::Queue &fillq, sim::Queue &storeq); + + void clock() override; + }; + +} diff --git a/uarch/fetch.cpp b/uarch/fetch.cpp new file mode 100644 index 0000000..3b84d82 --- /dev/null +++ b/uarch/fetch.cpp @@ -0,0 +1,129 @@ +#include +#include +#include +#include +#include +#include +#include + +#include "sim/sim.h" +#include "sim/queue.h" +#include "uarch/fetch.h" +#include "uarch/types.h" +#include "util/assert.h" + +namespace uarch { + + FetchStage::FetchStage(sim::Scheduler &scheduler, const aisa::ISA &isa, sim::Queue &fillreqq, sim::Queue &fillq, sim::Queue &uopq) + : sim::Schedulable(scheduler) + , fillreqq(fillreqq) + , fillq(fillq) + , uopq(uopq) + { + fillreqq.add_writer(this); + fillq.add_reader(this); + uopq.add_writer(this); + + auto [task, env] = isa.initial_task(); + store_reg(task->environment, env); + push_task(std::move(task)); + } + + void FetchStage::clock() + { + bool sent_uop = false; + while (!sent_uop) { + while (!step) { + const auto &task = *top_task().value(); + auto s = task.step(load_reg(task.environment).value()); + if (s.has_value()) { + step = std::move(s->first); + std::cout << "fetch step " << step->disasm() << "\n"; + wires = {}; + outstanding_fill = false; + fill_complete = false; + ASSERT(store_reg(task.environment, s->second), "Could not write next environment value"); + } else { + pop_task(); + } + } + + if (step->predicate.has_value()) { + auto x = load_reg(step->predicate->first); + if (x.has_value()) { + if (*x != step->predicate->second) + goto nextstep; + } else { + std::cout << "fetch stalls on predicate register"; + break; + } + } + + wires.source_vals.reserve(step->source_regs.size()); + for (unsigned int i = wires.source_vals.size(); i < step->source_regs.size(); ++i) { + auto x = load_reg(step->source_regs[i]); + if (!x.has_value()) { + std::cout << "fetch stalls on source register"; + break; + } + wires.source_vals.emplace_back(*x); + } + + if (step->mop == aisa::MOp::LOAD && !fill_complete) { + auto mi = step->meminfo(wires); + if (outstanding_fill) { + for (unsigned int i = 0; i < fillq.available(); ++i) { + auto &fill = fillq.peek(i); + if (fill.physical_addr == mi.physical_addr) { + std::cout << "fetch fills\n"; + wires.memory_val = std::move(fill.bytes); + outstanding_fill = false; + fill_complete = true; + } + } + if (!fill_complete) + break; + } else { + std::cout << "fetch sends fill request\n"; + FillReq req; + req.fillq = &fillq; + req.physical_addr = mi.physical_addr; + req.size = mi.size; + fillreqq.write(std::move(req)); + outstanding_fill = true; + fill_complete = false; + break; + } + } + + step->evaluate(wires); + + for (unsigned int i = 0; i < step->destination_regs.size(); ++i) + ASSERT(store_reg(step->destination_regs[i], wires.destination_vals[i]), "Could not write destination register"); + + ASSERT(step->mop != aisa::MOp::STORE, "No stores allowed in fetch"); + + if (wires.new_task.has_value()) { + std::cout << "fetch sends subtask " << wires.new_task->first->disasm() << " downstream\n"; + Uop uop; + static_cast(uop) = *this; + ASSERT(uop.store_reg(wires.new_task->first->environment, wires.new_task->second), "Could not write initial environment to uop"); + ASSERT(uop.push_task(std::move(wires.new_task->first)), "Could not push subtask to uop"); + uopq.write(std::move(uop)); + sent_uop = true; + } + +nextstep: + step = nullptr; + wires = {}; + outstanding_fill = false; + fill_complete = false; + } + + while (fillq.available()) { + std::cout << "fetch consumes fill\n"; + fillq.read(); + } + } + +} diff --git a/uarch/fetch.h b/uarch/fetch.h new file mode 100644 index 0000000..452b207 --- /dev/null +++ b/uarch/fetch.h @@ -0,0 +1,28 @@ +#pragma once + +#include + +#include "aisa/aisa.h" +#include "aisa/simple-models.h" +#include "sim/sim.h" +#include "sim/queue.h" +#include "uarch/types.h" + +namespace uarch { + + struct FetchStage : public sim::Schedulable, aisa::TaskStack, aisa::VectorRF { + sim::Queue &fillreqq; + sim::Queue &fillq; + sim::Queue &uopq; + + std::unique_ptr step; + aisa::Wires wires; + bool outstanding_fill = false; + bool fill_complete = false; + + FetchStage(sim::Scheduler &scheduler, const aisa::ISA &isa, sim::Queue &fillreqq, sim::Queue &fillq, sim::Queue &uopq); + + void clock() override; + }; + +} diff --git a/uarch/memory.cpp b/uarch/memory.cpp new file mode 100644 index 0000000..5cf9920 --- /dev/null +++ b/uarch/memory.cpp @@ -0,0 +1,46 @@ +#include +#include +#include +#include +#include +#include +#include + +#include "aisa/aisa.h" +#include "uarch/memory.h" +#include "util/assert.h" + +namespace uarch { + + MemStage::MemStage(sim::Scheduler &scheduler, sim::Queue &fillreqq, const std::initializer_list *> &fillqs, sim::Queue &storeq) + : sim::Schedulable(scheduler) + , fillreqq(fillreqq) + , storeq(storeq) + { + fillreqq.add_reader(this); + for (const auto &q : fillqs) + q->add_writer(this); + storeq.add_reader(this); + } + + void MemStage::clock() + { + if (storeq.available()) { + auto s = storeq.read(); + std::uint64_t x = 0; + for (unsigned int i = 0; i < s.bytes.size(); ++i) + x |= static_cast(s.bytes[i]) << 8 * i; + std::cout << "mem stores " << s.bytes.size() << " bytes to " << s.physical_addr << " <- " << x << "\n"; + ASSERT(store_mem(s.physical_addr, s.bytes.data(), s.bytes.size()), "Could not complete store"); + } else if (fillreqq.available()) { + auto r = fillreqq.read(); + std::cout << "mem fills " << r.size << " bytes from " << r.physical_addr << "\n"; + Fill f; + f.physical_addr = r.physical_addr; + f.bytes.resize(r.size); + ASSERT(fetch_mem(f.bytes.data(), r.physical_addr, r.size), "Could not complete fill"); + r.fillq->write(std::move(f)); + } + } + +} diff --git a/uarch/memory.h b/uarch/memory.h new file mode 100644 index 0000000..f36e375 --- /dev/null +++ b/uarch/memory.h @@ -0,0 +1,21 @@ +#pragma once + +#include + +#include "aisa/simple-models.h" +#include "sim/sim.h" +#include "sim/queue.h" +#include "uarch/types.h" + +namespace uarch { + + struct MemStage : public sim::Schedulable, aisa::PagedMem<> { + sim::Queue &fillreqq; + sim::Queue &storeq; + + MemStage(sim::Scheduler &scheduler, sim::Queue &fillreqq, const std::initializer_list *> &fillqs, sim::Queue &storeq); + + void clock() override; + }; + +} diff --git a/uarch/types.h b/uarch/types.h new file mode 100644 index 0000000..481b8fe --- /dev/null +++ b/uarch/types.h @@ -0,0 +1,30 @@ +#pragma once + +#include + +#include "aisa/aisa.h" +#include "aisa/simple-models.h" +#include "sim/queue.h" + +namespace uarch { + + struct Fill { + aisa::addr_t physical_addr; + std::vector bytes; + }; + + struct FillReq { + sim::Queue *fillq; + aisa::addr_t physical_addr; + aisa::addr_t size; + }; + + struct Store { + aisa::addr_t physical_addr; + std::vector bytes; + }; + + struct Uop : public aisa::TaskStack, aisa::VectorRF { + }; + +} diff --git a/uarch/uarch.d b/uarch/uarch.d new file mode 100644 index 0000000..e99bf71 --- /dev/null +++ b/uarch/uarch.d @@ -0,0 +1,2 @@ +uarch_SODEPS += build/libaisa.so +uarch_SODEPS += build/libsim.so diff --git a/util/assert.cpp b/util/assert.cpp new file mode 100644 index 0000000..5b57d67 --- /dev/null +++ b/util/assert.cpp @@ -0,0 +1,12 @@ +#include +#include + +#include "util/assert.h" + +void ASSERT(bool cond, const char *msg) +{ + if (cond) + return; + std::cout << "Assertion failed: " << msg << "\n"; + std::terminate(); +} diff --git a/util/assert.h b/util/assert.h new file mode 100644 index 0000000..84bd44c --- /dev/null +++ b/util/assert.h @@ -0,0 +1,3 @@ +#pragma once + +void ASSERT(bool cond, const char *msg); -- cgit v1.2.3