toctave

t(iny)octave
git clone https://0xff.ir/g/toctave.git
Log | Files | Refs | README

cgen.cpp (10404B)

      1 // Code generator
      2 
      3 // Copyright (C) 2022, Mohammad-Reza Nabipoor
      4 // SPDX-License-Identifier: GPL-3.0-or-later
      5 
      6 #include "cgen.hpp"
      7 
      8 #include <cassert>
      9 #include <cstdint>
     10 #include <cstdlib>
     11 #include <cstring>
     12 #include <sstream>
     13 #include <vector>
     14 
     15 namespace {
     16 
     17 template<typename... Ts>
     18 struct overloaded : Ts...
     19 {
     20   using Ts::operator()...;
     21 };
     22 template<typename... Ts>
     23 overloaded(Ts...) -> overloaded<Ts...>;
     24 
     25 class JPrinter
     26 {
     27 private:
     28   std::unique_ptr<void, void (*)(void*)> pcontext;
     29 
     30 public:
     31   JPrinter()
     32     : pcontext(jitter_print_context_make_memory(), [](void* p) {
     33       auto ctx{ reinterpret_cast<jitter_print_context>(p) };
     34 
     35       jitter_print_context_destroy(ctx);
     36     })
     37   {}
     38 
     39   jitter_print_context ctx()
     40   {
     41     return reinterpret_cast<jitter_print_context>(pcontext.get());
     42   }
     43 
     44   std::string buffer()
     45   {
     46     auto str{ jitter_print_context_get_memory(ctx(), /*length_p*/ nullptr) };
     47     std::string s{ str };
     48 
     49     free(str);
     50     return s;
     51   }
     52 };
     53 
     54 } // anonymous namespace
     55 
     56 namespace cgen {
     57 
     58 std::string
     59 sexpr(ast::NodesIter first, ast::NodesIter last)
     60 {
     61   std::ostringstream oss;
     62 
     63   while (first != last) {
     64     std::visit(overloaded{
     65                  [&](const ast::Num& n) { oss << n.num; },
     66                  [&](const ast::Op& op) {
     67                    auto f{ ++stlab::leading_of(first) };
     68                    auto l{ stlab::trailing_of(first) };
     69                    auto count{ 0u };
     70 
     71                    oss << "(" << op.op;
     72                    while (f != l) {
     73                      auto n{ ++stlab::trailing_of(f) };
     74                      oss << " " << sexpr(f, n);
     75                      f = n;
     76                      ++count;
     77                    }
     78                    assert(count == 2);
     79                    oss << ")";
     80                  },
     81                  [&](const ast::Id& id) { oss << id.id; },
     82                  [&](const ast::Str& str) { oss << '"' << str.str << '"'; },
     83                  [&](const ast::Ass& as) {
     84                    auto f{ ++stlab::leading_of(first) };
     85                    auto l{ stlab::trailing_of(first) };
     86 
     87                    assert(stlab::has_children(first));
     88 
     89                    oss << "(setq " << as.id.id << " ";
     90                    oss << sexpr(f, ++stlab::trailing_of(f)) << ")";
     91                  },
     92                  [&](const ast::Call& call) {
     93                    auto f{ ++stlab::leading_of(first) };
     94                    auto l{ stlab::trailing_of(first) };
     95 
     96                    assert(stlab::has_children(first));
     97 
     98                    oss << "(" << call.id.id;
     99                    while (f != l) {
    100                      auto n{ ++stlab::trailing_of(f) };
    101                      oss << " " << sexpr(f, n);
    102                      f = n;
    103                    }
    104                    oss << ")";
    105                  },
    106                },
    107                *first);
    108 
    109     first = ++stlab::trailing_of(first);
    110   }
    111 
    112   return oss.str();
    113 }
    114 
    115 //--- Jittery VM
    116 
    117 JExecRoutine::JExecRoutine(struct toctave_mutable_routine* r)
    118   : er(toctave_make_executable_routine(r), toctave_destroy_executable_routine)
    119   , state(toctave_state_make(), toctave_state_destroy)
    120 {}
    121 
    122 bool
    123 JExecRoutine::exec(env::Env& e)
    124 {
    125   auto point{ TOCTAVE_STATE_RUNTIME_FIELD(state.get(), point) };
    126   auto status{ TOCTAVE_STATE_RUNTIME_FIELD(state.get(), status) };
    127 
    128   TOCTAVE_STATE_RUNTIME_FIELD(state.get(), env) = reinterpret_cast<void*>(&e);
    129   if (point) {
    130     assert(status == TOCTAVE_STATUS_YIELD);
    131     toctave_branch_to_program_point(point, state.get());
    132   } else {
    133     assert(status == -1);
    134     toctave_execute_executable_routine(er.get(), state.get());
    135   }
    136   TOCTAVE_STATE_RUNTIME_FIELD(state.get(), env) = nullptr;
    137   status = TOCTAVE_STATE_RUNTIME_FIELD(state.get(), status);
    138   assert(status != -1);
    139   return status == TOCTAVE_STATUS_DONE;
    140 }
    141 
    142 double
    143 JExecRoutine::result()
    144 {
    145   return TOCTAVE_STATE_RUNTIME_FIELD(state.get(), result);
    146 }
    147 
    148 //---
    149 
    150 JRoutine::JRoutine()
    151   : r(toctave_make_mutable_routine(), toctave_destroy_mutable_routine)
    152 {}
    153 
    154 JExecRoutine
    155 JRoutine::mkexec()
    156 {
    157   return JExecRoutine(r.get());
    158 }
    159 
    160 JRoutine::label_t
    161 JRoutine::mklabel()
    162 {
    163   return toctave_fresh_label(r.get());
    164 }
    165 
    166 JRoutine::label_t
    167 JRoutine::label(JRoutine::label_t l)
    168 {
    169   toctave_mutable_routine_append_label(r.get(), l);
    170   return l;
    171 }
    172 
    173 JRoutine::label_t
    174 JRoutine::label()
    175 {
    176   return label(mklabel());
    177 }
    178 
    179 void
    180 JRoutine::push(double d)
    181 {
    182   static_assert(sizeof(void*) == sizeof(double),
    183                 "We're using double as the type of stack elements; to make "
    184                 "the implementation easier, we expect a 64-bit platform");
    185   uintptr_t num;
    186 
    187   memcpy(&num, &d, sizeof(d)); // copy the bits of double into the uint
    188   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), push);
    189   toctave_mutable_routine_append_unsigned_literal_parameter(r.get(), num);
    190 }
    191 
    192 void
    193 JRoutine::pushnan()
    194 {
    195   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), pushnan);
    196 }
    197 
    198 void
    199 JRoutine::pop()
    200 {
    201   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), pop);
    202 }
    203 
    204 void
    205 JRoutine::drop()
    206 {
    207   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), drop);
    208 }
    209 
    210 void
    211 JRoutine::pow()
    212 {
    213   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), pow);
    214 }
    215 
    216 void
    217 JRoutine::mul()
    218 {
    219   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), mul);
    220 }
    221 
    222 void
    223 JRoutine::div()
    224 {
    225   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), div);
    226 }
    227 
    228 void
    229 JRoutine::add()
    230 {
    231   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), add);
    232 }
    233 
    234 void
    235 JRoutine::sub()
    236 {
    237   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), sub);
    238 }
    239 
    240 namespace {
    241 
    242 double
    243 nan_box(uintptr_t p)
    244 {
    245   static const uintptr_t mask{ ((uint64_t)1 << 51) - 1 };
    246   uint64_t n;
    247   double d;
    248 
    249   assert((p & 7) == 0); // This is true on GNU systems
    250   p >>= 3;
    251   assert((~mask & p) == 0); // We're doing nan-boxing, so we only have 51 bits!
    252                             // This is true, at least, on x86_64.
    253   n = ((uint64_t)0xfff8 << 51) | (p & mask); // this a qNAN
    254   memcpy(&d, &n, sizeof(n));
    255   return d;
    256 }
    257 
    258 #if 0
    259 uintptr_t
    260 nan_unbox(double d)
    261 {
    262   static const uintptr_t mask{ ((uint64_t)1 << 51) - 1 };
    263   uintptr_t p;
    264 
    265   memcpy(&p, &d, sizeof(d));
    266   p &= mask;
    267   p <<= 3;
    268   return p;
    269 }
    270 #endif
    271 
    272 uintptr_t
    273 nan_box_as_uint(uintptr_t p)
    274 {
    275   double d{ nan_box(p) };
    276   uintptr_t n;
    277 
    278   memcpy(&n, &d, sizeof(d));
    279   return n;
    280 }
    281 
    282 }
    283 
    284 void
    285 JRoutine::pushvar(const char* var)
    286 {
    287   auto n{ nan_box_as_uint(reinterpret_cast<uintptr_t>(var)) };
    288 
    289   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), pushvar);
    290   toctave_mutable_routine_append_unsigned_literal_parameter(r.get(), n);
    291 }
    292 
    293 void
    294 JRoutine::popvar(const char* var)
    295 {
    296   auto n{ nan_box_as_uint(reinterpret_cast<uintptr_t>(var)) };
    297 
    298   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), popvar);
    299   toctave_mutable_routine_append_unsigned_literal_parameter(r.get(), n);
    300 }
    301 
    302 void
    303 JRoutine::call(const char* func)
    304 {
    305   (void)func;
    306   assert(0 && "not implemented yet");
    307 }
    308 
    309 void
    310 JRoutine::yield(label_t l)
    311 {
    312   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), yield);
    313   toctave_mutable_routine_append_label_parameter(r.get(), l);
    314   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), exitvm);
    315 }
    316 
    317 void
    318 JRoutine::done()
    319 {
    320   TOCTAVE_MUTABLE_ROUTINE_APPEND_INSTRUCTION(r.get(), done);
    321 }
    322 
    323 std::string
    324 disasm(const JRoutine& r)
    325 {
    326   JPrinter jprinter;
    327 
    328   toctave_mutable_routine_print(jprinter.ctx(), r.r.get());
    329   return jprinter.buffer();
    330 }
    331 
    332 std::string
    333 disasm(const JExecRoutine& er)
    334 {
    335   JPrinter jprinter;
    336 
    337   toctave_executable_routine_disassemble(
    338     jprinter.ctx(), er.er.get(), true, "objdump", nullptr);
    339   return jprinter.buffer();
    340 }
    341 
    342 //--- codegen
    343 
    344 namespace {
    345 
    346 void
    347 jitter_(JRoutine& r,
    348         ast::NodesIter first,
    349         ast::NodesIter last,
    350         bool toplevel = false)
    351 {
    352   // Post-order traversal
    353   while (first != last) {
    354     std::visit(overloaded{
    355                  [&](const ast::Num& n) {
    356                    r.push(n.num);
    357                    if (toplevel)
    358                      r.pop();
    359                  },
    360                  [&](const ast::Op& op) {
    361                    auto f{ ++stlab::leading_of(first) };
    362                    auto l{ stlab::trailing_of(first) };
    363                    auto count{ 0u };
    364 
    365                    // first visit the operands
    366                    while (f != l) {
    367                      auto n{ ++stlab::trailing_of(f) };
    368                      jitter_(r, f, n);
    369                      f = n;
    370                      ++count;
    371                    }
    372                    assert(count == 2);
    373                    switch (op.op) {
    374                      case '^':
    375                        r.pow();
    376                        break;
    377                      case '*':
    378                        r.mul();
    379                        break;
    380                      case '/':
    381                        r.div();
    382                        break;
    383                      case '+':
    384                        r.add();
    385                        break;
    386                      case '-':
    387                        r.sub();
    388                        break;
    389                      default:
    390                        assert(0 && "unknown operator");
    391                    }
    392                    if (toplevel)
    393                      r.pop();
    394                  },
    395                  [&](const ast::Id& id) { r.pushvar(id.id.c_str()); },
    396                  [&](const ast::Str&) { assert(0 && "invalid entity"); },
    397                  [&](const ast::Ass& as) {
    398                    auto f{ ++stlab::leading_of(first) };
    399                    auto l{ stlab::trailing_of(first) };
    400 
    401                    assert(stlab::has_children(first));
    402 
    403                    jitter_(r, f, ++stlab::trailing_of(f)); // visit children
    404                    r.popvar(as.id.id.c_str()); // move the value to variable
    405                    if (toplevel) {
    406                      r.pushnan();
    407                      r.pop();
    408                    }
    409                  },
    410                  [&](const ast::Call& call) {
    411                    auto f{ ++stlab::leading_of(first) };
    412                    auto l{ stlab::trailing_of(first) };
    413 
    414                    assert(stlab::has_children(first));
    415 
    416                    while (f != l) {
    417                      auto n{ ++stlab::trailing_of(f) };
    418                      jitter_(r, f, n); // visit children
    419                      f = n;
    420                    }
    421                    r.call(call.id.id.c_str());
    422                  },
    423                },
    424                *first);
    425 
    426     first = ++stlab::trailing_of(first);
    427   }
    428 }
    429 
    430 } // namespace }
    431 
    432 JRoutine
    433 jitter(ast::NodesIter first, ast::NodesIter last)
    434 {
    435   JRoutine r;
    436 
    437   jitter_(r, first, last, true);
    438   r.done();
    439   return r;
    440 }
    441 
    442 } // namespace cgen