Implement hierarchical evaluation (WIP)

7 files changed, 170 insertions, 70 deletions

diff --git a/asm/intel64/codes.cpp b/asm/intel64/codes.cpp
index 58d921f..9f82d37 100644
--- a/asm/intel64/codes.cpp
+++ b/asm/intel64/codes.cpp
@@ -1,5 +1,8 @@
 #include "codes.h"
 
+#include "minicc.h"
+#include "../operators.h"
+
 #include <exception>
 #include <unordered_map>
 
@@ -44,12 +47,13 @@ namespace {
   {"rdx", 2}, {"rdi", 7},
  };
 
-}
+} // namespace
 
 // Manual, page 530
 // Reg + Reg/Memory
-uint8_t ModRM(const std::string& reg, const std::string& rm) {
- uint8_t result{0b11000000}; // TODO: other than 11: Indexed forms of r/m
+std::vector<uint8_t> ModRM(const std::string& reg, const std::string& rm, int32_t disp) {
+ uint8_t result{}; // MOD is highest 2 bits, then 3 bits Reg, the 3 bits R/M
+ std::vector<uint8_t> displacement_bytes;
 
  size_t val_reg{};
  // reg
@@ -60,22 +64,35 @@ uint8_t ModRM(const std::string& reg, const std::string& rm) {
    throw std::runtime_error("ModRM: Bad digit in arg1: "s + reg);
   }
  } else { // reg
-  auto index1{ IndexOfRegister.find(reg) };
-  if (index1 == IndexOfRegister.end())
-   throw std::runtime_error("ModRM: Unknown register for arg1: "s + reg);
-  val_reg = index1->second;
+  val_reg = RegNo(reg);
  }
 
  result |= (val_reg << 3);
 
  // rm
- auto index2{ IndexOfRegister.find(rm) };
- if (index2 == IndexOfRegister.end())
-  throw std::runtime_error("Unknown register for arg2: "s + rm);
-
- result |= index2->second;
+ if (rm.size() > 2 && rm.front() == '[' && rm.back() == ']') { // indexed / MemPtr
+  uint8_t rm_bits {RegNo(rm.substr(1, rm.size() - 2))};
+  if (rm_bits == 4)
+   throw std::runtime_error("ICE: SIB byte not yet supported");
+
+  if (disp == 0 && rm_bits != 5) { // no displacement
+   // ignore: keep MOD == 00, no displacement bytes
+   if (rm_bits == 5)
+    throw std::runtime_error("ICE: [rbp] with now displacement is not supported"); // TODO: Support this, and SIB byte
+  } else if (disp >= -128 && disp < 128) {
+   result |= 0b01000000; // 8 bit displacement
+   displacement_bytes.push_back(uint8_t(disp));
+  } else {
+   result |= 0b10000000; // 32 bit displacement
+   displacement_bytes += to_little_endian(disp);
+  }
+  result |= rm_bits;
+ } else { // normal register access
+  result |= 0b11000000;
+  result |= RegNo(rm);
+ }
 
- return result;
+ return std::vector<uint8_t>{result} + displacement_bytes;
 }
 
 uint8_t RegNo(const std::string& reg)
diff --git a/asm/intel64/codes.h b/asm/intel64/codes.h
index 112eef4..ba378a6 100644
--- a/asm/intel64/codes.h
+++ b/asm/intel64/codes.h
@@ -9,7 +9,9 @@ std::vector<uint8_t> REX(const std::string& s);
 
 // Manual, page 530
 // Reg + Reg/Memory
-uint8_t ModRM(const std::string& reg, const std::string& rm);
+// disp: optional, only necessary in some cases, e.g. indexed memory access
+// returns: Encoded ModRM byte, followed by SIB and disp bytes, if appropriate
+std::vector<uint8_t> ModRM(const std::string& reg, const std::string& rm, int32_t disp = 0);
 
 // Just the number of reg, e.g. for encoding inside primary opcode
 uint8_t RegNo(const std::string& reg);
diff --git a/asm/intel64/encode.cpp b/asm/intel64/encode.cpp
index 681e407..0806b56 100644
--- a/asm/intel64/encode.cpp
+++ b/asm/intel64/encode.cpp
@@ -8,6 +8,113 @@
 
 #include <exception>
 
+namespace {
+
+std::shared_ptr<Op> makeLoadValue(FlowGraph::Data& data)
+{
+ if (data.type() != FlowGraph::DataType::Int) {
+  std::runtime_error("Bad type for operand: "s + std::to_string(int(data.type())));
+ }
+
+ if (!data.storage())
+  throw std::runtime_error("ICE: Operand storage is 0");
+
+ auto& data_storage{*data.storage()};
+ if (typeid(data_storage) == typeid(FlowGraph::Constant)) {
+  FlowGraph::Constant& value {dynamic_cast<FlowGraph::Constant&>(data_storage)};
+  if (value.value().size() < sizeof(uint32_t))
+   throw std::runtime_error("ICE: Int data from operand needs at least 4 bytes, got "s + std::to_string(value.value().size()));
+
+  uint32_t immediate = from_little_endian(value.value());
+
+  return makeOp("mov", Asm::Args{{Asm::Args::Register32("eax"), Asm::Args::Immediate32(immediate)}});
+ } else if (typeid(data_storage) == typeid(FlowGraph::TemporaryStorage)) {
+  FlowGraph::TemporaryStorage& storage {dynamic_cast<FlowGraph::TemporaryStorage&>(data_storage)};
+
+  index_t index { storage.indexOfStorage()};
+  return makeOp("mov", Asm::Args{{Asm::Args::Register32("eax"), Asm::Args::Mem32Ptr64("rbp", int32_t(index) * -4)}});
+ } else
+  throw std::runtime_error("ICE: Unsupported type for operand data at load: "s + demangle(typeid(data_storage)));
+}
+
+std::shared_ptr<Op> makeStoreValue(FlowGraph::Data& data)
+{
+ if (data.type() != FlowGraph::DataType::Int) {
+  std::runtime_error("Bad type for operand: "s + std::to_string(int(data.type())));
+ }
+
+ if (!data.storage())
+  throw std::runtime_error("ICE: Operand storage is 0");
+
+ auto& data_storage{*data.storage()};
+ if (typeid(data_storage) == typeid(FlowGraph::TemporaryStorage)) {
+  FlowGraph::TemporaryStorage& storage {dynamic_cast<FlowGraph::TemporaryStorage&>(data_storage)};
+
+  index_t index { storage.indexOfStorage()};
+  return makeOp("mov", Asm::Args{{Asm::Args::Mem32Ptr64("rbp", int32_t(index) * -4), Asm::Args::Register32("eax")}});
+ } else
+  throw std::runtime_error("ICE: Unsupported type for operand data at store: "s  + demangle(typeid(data_storage)));
+}
+
+std::shared_ptr<Op> makeAddValue(FlowGraph::Data& data)
+{
+ if (data.type() != FlowGraph::DataType::Int) {
+  std::runtime_error("Bad type for operand: "s + std::to_string(int(data.type())));
+ }
+
+ if (!data.storage())
+  throw std::runtime_error("ICE: Operand storage is 0");
+
+ auto& data_storage{*data.storage()};
+ if (typeid(data_storage) == typeid(FlowGraph::Constant)) {
+  FlowGraph::Constant& value {dynamic_cast<FlowGraph::Constant&>(data_storage)};
+  if (value.value().size() < sizeof(uint32_t))
+   throw std::runtime_error("ICE: Int data from operand needs at least 4 bytes, got "s + std::to_string(value.value().size()));
+
+  uint32_t immediate = from_little_endian(value.value());
+
+  return makeOp("add", Asm::Args{{Asm::Args::Register32("eax"), Asm::Args::Immediate32(immediate)}});
+ } else if (typeid(data_storage) == typeid(FlowGraph::TemporaryStorage)) {
+  FlowGraph::TemporaryStorage& storage {dynamic_cast<FlowGraph::TemporaryStorage&>(data_storage)};
+
+  index_t index { storage.indexOfStorage()};
+  return makeOp("add", Asm::Args{{Asm::Args::Register32("eax"), Asm::Args::Mem32Ptr64("rbp", int32_t(index) * -4)}});
+ } else
+  throw std::runtime_error("ICE: Unsupported type for operand data at add: "s + demangle(typeid(data_storage)));
+}
+
+std::vector<std::shared_ptr<Chunk>> makeMulValue(FlowGraph::Data& data)
+{
+ if (data.type() != FlowGraph::DataType::Int) {
+  std::runtime_error("Bad type for operand: "s + std::to_string(int(data.type())));
+ }
+
+ if (!data.storage())
+  throw std::runtime_error("ICE: Operand storage is 0");
+
+ auto& data_storage{*data.storage()};
+ if (typeid(data_storage) == typeid(FlowGraph::Constant)) {
+  FlowGraph::Constant& value {dynamic_cast<FlowGraph::Constant&>(data_storage)};
+  if (value.value().size() < sizeof(uint32_t))
+   throw std::runtime_error("ICE: Int data from operand needs at least 4 bytes, got "s + std::to_string(value.value().size()));
+
+  uint32_t immediate = from_little_endian(value.value());
+
+  return {{
+   makeOp("mov", Asm::Args{{Asm::Args::Register32("ebx"), Asm::Args::Immediate32(immediate)}}),
+   makeOp("mul", Asm::Args{{Asm::Args::Register32("ebx")}})
+  }};
+ } else if (typeid(data_storage) == typeid(FlowGraph::TemporaryStorage)) {
+  FlowGraph::TemporaryStorage& storage {dynamic_cast<FlowGraph::TemporaryStorage&>(data_storage)};
+
+  index_t index { storage.indexOfStorage()};
+  return {{makeOp("mul", Asm::Args{{Asm::Args::Mem32Ptr64("rbp", int32_t(index) * -4)}})}};
+ } else
+  throw std::runtime_error("ICE: Unsupported type for operand data at mul: "s + demangle(typeid(data_storage)));
+}
+
+} // namespace
+
 void Asm::toMachineCode(const FlowGraph::Graph& graph, Segment& segment)
 {
  segment.clear();
@@ -48,61 +155,14 @@ void Asm::toMachineCode(const FlowGraph::Graph& graph, Segment& segment)
 
     auto operands {op.operands()};
 
-#if 0
-    if (op.type() == FlowGraph::BinaryOperationType::Add) {
-     segment.push_back(loadmakeOp("add", Asm::Args{{Asm::Args::Register32("eax"), Asm::Args::Immediate32(immediate2)}}));
-    } else if (op.type() == FlowGraph::BinaryOperationType::Multiply) {
-     segment.push_back(makeOp("mov", Asm::Args{{Asm::Args::Register32("ebx"), Asm::Args::Immediate32(immediate2)}}));
-     segment.push_back(makeOp("mul", Asm::Args{{Asm::Args::Register32("ebx")}}));
-    } else
-     throw std::runtime_error("ICE: Asm: Unsupported binary operation type: "s + std::to_string(static_cast<int>(op.type())));
-#endif
-
-
-
-
-    if (operands[1].type() != FlowGraph::DataType::Int) {
-     std::runtime_error("Bad type for operand 1: "s + std::to_string(int(operands[1].type())));
-    }
-
-    if (operands[2].type() != FlowGraph::DataType::Int) {
-     std::runtime_error("Bad type for operand 2: "s + std::to_string(int(operands[2].type())));
-    }
-
-    if (!operands[1].storage())
-     throw std::runtime_error("ICE: Operand 1 storage is 0");
-    if (!operands[2].storage())
-     throw std::runtime_error("ICE: Operand 2 storage is 0");
-
-    uint32_t immediate1{};
-    try {
-     FlowGraph::Constant& value1 {dynamic_cast<FlowGraph::Constant&>(*operands[1].storage())};
-     if (value1.value().size() < sizeof(uint32_t))
-      throw std::runtime_error("ICE: Int data from operand 1 needs at least 4 bytes, got "s + std::to_string(value1.value().size()));
-
-     immediate1 = boost::endian::little_to_native(*(reinterpret_cast<const uint32_t*>(value1.value().data())));
-    } catch (const std::bad_cast& ex) {
-     std::runtime_error("Bad value for operand 1: Constant expected");
-    }
-    
-    uint32_t immediate2{};
-    try {
-     FlowGraph::Constant& value2 {dynamic_cast<FlowGraph::Constant&>(*operands[2].storage())};
-     if (value2.value().size() < sizeof(uint32_t))
-      throw std::runtime_error("ICE: Int data from operand 2 needs at least 4 bytes, got "s + std::to_string(value2.value().size()));
-
-     immediate2 = boost::endian::little_to_native(*(reinterpret_cast<const uint32_t*>(value2.value().data())));
-    } catch (const std::bad_cast& ex) {
-     std::runtime_error("Bad value for operand 2: Constant expected");
-    }
-    
-    segment.push_back(makeOp("mov", Asm::Args{{Asm::Args::Register32("eax"), Asm::Args::Immediate32(immediate1)}}));
-
     if (op.type() == FlowGraph::BinaryOperationType::Add) {
-     segment.push_back(makeOp("add", Asm::Args{{Asm::Args::Register32("eax"), Asm::Args::Immediate32(immediate2)}}));
+     segment.push_back(makeLoadValue(operands[1]));
+     segment.push_back(makeAddValue(operands[2]));
+     segment.push_back(makeStoreValue(operands[0]));
     } else if (op.type() == FlowGraph::BinaryOperationType::Multiply) {
-     segment.push_back(makeOp("mov", Asm::Args{{Asm::Args::Register32("ebx"), Asm::Args::Immediate32(immediate2)}}));
-     segment.push_back(makeOp("mul", Asm::Args{{Asm::Args::Register32("ebx")}}));
+     segment.push_back(makeLoadValue(operands[1]));
+     segment.append(makeMulValue(operands[2]));
+     segment.push_back(makeStoreValue(operands[0]));
     } else
      throw std::runtime_error("ICE: Asm: Unsupported binary operation type: "s + std::to_string(static_cast<int>(op.type())));
 
@@ -115,7 +175,7 @@ void Asm::toMachineCode(const FlowGraph::Graph& graph, Segment& segment)
     //FlowGraph::DestroyScopeOp& op {dynamic_cast<FlowGraph::DestroyScopeOp&>(*node)};
     segment.push_back(makeOp("pop", Asm::Args{{Asm::Args::Register64("rbp")}}));
 
-    // Move eax for exit() via rdi
+    // Move eax (still present from last operation) for exit() via rdi
     segment.push_back(makeOp("xor", Asm::Args{{Asm::Args::Register64("rdi"), Asm::Args::Register64("rdi")}}));
     segment.push_back(makeOp("mov", Asm::Args{{Asm::Args::Register32("edi"), Asm::Args::Register32("eax")}}));
    } else if (typeid(node_deref) == typeid(FlowGraph::DataNode)) {
diff --git a/asm/operators.cpp b/asm/operators.cpp
index 9f7d5d9..9cd02a1 100644
--- a/asm/operators.cpp
+++ b/asm/operators.cpp
@@ -1,13 +1,26 @@
 #include "operators.h"
 
 // binary code operators
-std::vector<uint8_t> operator+(std::vector<uint8_t> a, const std::vector<uint8_t>& b) {
+std::vector<uint8_t> operator+(std::vector<uint8_t> a, const std::vector<uint8_t>& b)
+{
  a.insert(a.end(), b.begin(), b.end());
  return a;
 }
 
-std::vector<uint8_t> operator+(std::vector<uint8_t> a, const uint8_t& b) {
+std::vector<uint8_t> operator+(std::vector<uint8_t> a, const uint8_t& b)
+{
  a.push_back(b);
  return a;
 }
 
+std::vector<uint8_t> operator+=(std::vector<uint8_t>& a, const std::vector<uint8_t>& b)
+{
+ a.insert(a.end(), b.begin(), b.end());
+ return a;
+}
+
+std::vector<uint8_t> operator+=(std::vector<uint8_t>& a, const uint8_t& b)
+{
+ a.push_back(b);
+ return a;
+}
diff --git a/asm/operators.h b/asm/operators.h
index 741ec72..280de58 100644
--- a/asm/operators.h
+++ b/asm/operators.h
@@ -8,3 +8,5 @@
 std::vector<uint8_t> operator+(std::vector<uint8_t> a, const std::vector<uint8_t>& b);
 std::vector<uint8_t> operator+(std::vector<uint8_t> a, const uint8_t& b);
 
+std::vector<uint8_t> operator+=(std::vector<uint8_t>& a, const std::vector<uint8_t>& b);
+std::vector<uint8_t> operator+=(std::vector<uint8_t>& a, const uint8_t& b);
diff --git a/asm/segment.cpp b/asm/segment.cpp
index d3050bb..9d439fd 100644
--- a/asm/segment.cpp
+++ b/asm/segment.cpp
@@ -9,6 +9,11 @@
 
 using namespace std::string_literals;
 
+void Segment::append(const std::vector<std::shared_ptr<Chunk>>& list)
+{
+ insert(end(), list.cbegin(), list.cend());
+}
+
 size_t Segment::getAddressOfLabel(const std::string& label)
 {
  size_t address{0};
diff --git a/asm/segment.h b/asm/segment.h
index 97e1670..b4b31f8 100644
--- a/asm/segment.h
+++ b/asm/segment.h
@@ -10,6 +10,7 @@
 class Segment: public std::vector<std::shared_ptr<Chunk>>
 {
 public:
+ void append(const std::vector<std::shared_ptr<Chunk>>& list);
  size_t getAddressOfLabel(const std::string& label);
  size_t getAddressOfIndex(size_t index);
  std::vector<uint8_t> getCode();