[willow]: initial frontend work, unit tests (#8)dev/stefan

10 files changed, 165 insertions, 25 deletions

diff --git a/willow/include/willow/ADT/IList.h b/willow/include/willow/ADT/IList.h
new file mode 100644
index 0000000..0c55ad5
--- /dev/null
+++ b/willow/include/willow/ADT/IList.h
@@ -0,0 +1,76 @@
+#ifndef WILLOW_INCLUDE_ADT_ILIST_H
+#define WILLOW_INCLUDE_ADT_ILIST_H
+
+#include <type_traits>
+
+namespace willow {
+
+template <typename T>
+class IList;
+
+/// An instrusive list node
+template <typename T>
+class IListTrait {
+  friend class IList<T>;
+
+public:
+  IListTrait() = default;
+  IListTrait(const IListTrait &) = delete;
+  IListTrait &operator=(const IListTrait &) = delete;
+  IListTrait(IListTrait &&) = delete;
+  IListTrait &operator=(IListTrait &&) = delete;
+
+  T *getNext() const { return static_cast<T *>(next); }
+  T *getNext() { return static_cast<T *>(next); }
+  T *getPrev() const { return static_cast<T *>(prev); }
+  T *getPrev() { return static_cast<T *>(prev); }
+
+  void insertAfter(IListTrait<T> &node) {
+    auto old = this->next;
+    this->next = &node;
+    node->prev = this;
+    node->next = old;
+  };
+
+  void insertBefore(IListTrait<T> &node) {
+    auto old = this->prev;
+    this->prev = node;
+    node->next = this;
+    node->prev = old;
+  };
+
+  /// Erase the node from the list. Return a pointer to the unliked node
+  T *removeFromList() {
+    prev->next = next;
+    next->prev = prev;
+    prev = nullptr;
+    next = nullptr;
+    return static_cast<T *>(this);
+  }
+
+private:
+  IListTrait<T> *prev = nullptr;
+  IListTrait<T> *next = nullptr;
+};
+
+/// Instrusive list
+template <typename T>
+class IList {
+  static_assert(std::is_base_of_v<IListTrait<T>, T>,
+                "T must implement IListTrait");
+  using node = IListTrait<T>;
+
+public:
+  IList() : dummyBegin{nullptr, &dummyEnd}, dummyEnd{&dummyBegin, dummyEnd} {}
+  IList(const IList &) = delete;
+  IList(IList &&) = delete;
+
+private:
+  // yes we could save 16 bytes, no i dont really care
+  node dummyBegin;
+  node dummyEnd;
+};
+
+} // namespace willow
+
+#endif // WILLOW_INCLUDE_ADT_ILIST_H
diff --git a/willow/include/willow/IR/BasicBlock.h b/willow/include/willow/IR/BasicBlock.h
index c18dfc2..5db8538 100644
--- a/willow/include/willow/IR/BasicBlock.h
+++ b/willow/include/willow/IR/BasicBlock.h
@@ -70,14 +70,14 @@ public:
   std::unordered_map<BasicBlock*, size_t>& preds() { return predecessors; }
   const std::unordered_map<BasicBlock*, size_t>& preds() const { return predecessors; }
 
-  inline void addPred(BasicBlock *bb) {
+  void addPred(BasicBlock *bb) {
     auto [it, inserted] = predecessors.try_emplace(bb, 1);
 
     if (!inserted)
       it->second += 1;
   }
 
-  inline void delPred(BasicBlock *bb) {
+  void delPred(BasicBlock *bb) {
     auto it = preds().find(bb);
 
     it->second -= 1;
@@ -87,21 +87,35 @@ public:
   }
 };
 
-Instruction *BasicBlock::trailer() {
+inline Instruction *BasicBlock::trailer() {
   if (empty())
     return nullptr;
   else
     return body.back().get();
 }
 
-Instruction *BasicBlock::leader() {
+inline Instruction *BasicBlock::leader() {
   if (empty())
     return nullptr;
   else
     return body.back().get();
 }
 
-Instruction *BasicBlock::addInstruction(std::unique_ptr<Instruction> inst) {
+inline const Instruction *BasicBlock::trailer() const {
+  if (empty())
+    return nullptr;
+  else
+    return body.back().get();
+}
+
+inline const Instruction *BasicBlock::leader() const {
+  if (empty())
+    return nullptr;
+  else
+    return body.back().get();
+}
+
+inline Instruction *BasicBlock::addInstruction(std::unique_ptr<Instruction> inst) {
   Instruction *p = inst.get();
   p->setParent(this);
   body.push_back(std::move(inst));
diff --git a/willow/include/willow/IR/Constant.h b/willow/include/willow/IR/Constant.h
index d93d65d..4e2a3d7 100644
--- a/willow/include/willow/IR/Constant.h
+++ b/willow/include/willow/IR/Constant.h
@@ -1,6 +1,7 @@
 #ifndef WILLOW_INCLUDE_IR_CONSTANT_H
 #define WILLOW_INCLUDE_IR_CONSTANT_H
 
+#include <utility>
 #include <willow/IR/Value.h>
 
 namespace willow {
@@ -89,4 +90,19 @@ public:
 
 } // namespace willow
 
+// TODO lol
+inline std::ostream& operator<<(std::ostream &os, const willow::Constant& c) {
+  if (c.isPoison())
+    return os << "poison";
+
+  if (c.isUndef())
+    return os << "undef";
+
+  if (c.isInt()) {
+    return os << static_cast<const willow::ConstantInt*>(&c)->getSExtVal();
+  }
+
+  std::unreachable();
+}
+
 #endif // WILLOW_INCLUDE_IR_CONSTANT_H
diff --git a/willow/include/willow/IR/Context.h b/willow/include/willow/IR/Context.h
index 3f4f2ba..eda0241 100644
--- a/willow/include/willow/IR/Context.h
+++ b/willow/include/willow/IR/Context.h
@@ -17,6 +17,13 @@ class WillowContext {
 public:
   TypeContext &types() { return typectx; }
   ConstantPool &constants() { return constantpool; }
+
+  template<typename ...Args>
+  [[nodiscard]]
+  Module *addModule(Args&&...args) {
+    modules.push_back(std::make_unique<Module>(std::forward<Args>(args)...));
+    return modules.back().get();
+  }
 };
 
 } // namespace willow
diff --git a/willow/include/willow/IR/Function.h b/willow/include/willow/IR/Function.h
index 4be4de7..43a301b 100644
--- a/willow/include/willow/IR/Function.h
+++ b/willow/include/willow/IR/Function.h
@@ -38,6 +38,9 @@ public:
       : Value(ValueKind::Function, std::move(name), fty), parent(parent),
         params(std::move(params)) {}
 
+  Function(std::string name, Module *parent, Type fty)
+      : Value(ValueKind::Function, std::move(name), fty), parent(parent) {}
+
   /// \return Parent module or nullptr.
   Module *getParent() { return parent; }
   const Module *getParent() const { return parent; }
@@ -112,14 +115,14 @@ public:
   }
 };
 
-const BasicBlock *Function::entryBlock() const {
+inline const BasicBlock *Function::entryBlock() const {
   if (blocks.empty())
     return nullptr;
   else
     return blocks.front().get();
 }
 
-BasicBlock *Function::entryBlock() {
+inline BasicBlock *Function::entryBlock() {
   if (blocks.empty())
     return nullptr;
   else
diff --git a/willow/include/willow/IR/IRBuilder.h b/willow/include/willow/IR/IRBuilder.h
index 635c41b..6036e33 100644
--- a/willow/include/willow/IR/IRBuilder.h
+++ b/willow/include/willow/IR/IRBuilder.h
@@ -1,6 +1,7 @@
 #ifndef WILLOW_INCLUDE_IR_IR_BUILDER_H
 #define WILLOW_INCLUDE_IR_IR_BUILDER_H
 
+#include <willow/IR/Context.h>
 #include <willow/IR/BasicBlock.h>
 #include <willow/IR/Function.h>
 #include <willow/IR/Instruction.h>
@@ -9,6 +10,8 @@ namespace willow {
 
 /// Helper for constructing and modifiying IR.
 class IRBuilder {
+  WillowContext &ctx;
+  const Module &mod;
   BasicBlock *block = nullptr;
 
 public:
diff --git a/willow/include/willow/IR/Instruction.h b/willow/include/willow/IR/Instruction.h
index a74c409..1198546 100644
--- a/willow/include/willow/IR/Instruction.h
+++ b/willow/include/willow/IR/Instruction.h
@@ -25,7 +25,11 @@ class Function;
 class Successors {
   friend class Instruction;
   std::array<BasicBlock *, 2> data;
-  uint8_t n = 0;
+  uint8_t n;
+
+  Successors() : data{}, n{0} {}
+  explicit Successors(BasicBlock *a) : data{a}, n{1} {}
+  Successors(BasicBlock *a, BasicBlock *b) : data{a, b}, n{2} {}
 
 public:
   auto begin() { return data.data(); }
@@ -198,6 +202,8 @@ constexpr std::string_view Instruction::opcodeName(Instruction::Opcode op) {
   case Alloca:
     return "alloca";
   }
+
+  std::unreachable();
 }
 
 } // namespace willow
@@ -212,11 +218,19 @@ struct std::formatter<willow::Instruction::Opcode> {
   }
 };
 
-// std::ostream& operator<<(std::ostream &os, const willow::Instruction &inst) {
-//   auto vty = inst.getType();
-//
-//   // int add %i %
-//   os << vty << " " << inst.opcode() << " "
-// }
+inline std::ostream& operator<<(std::ostream &os, const willow::Instruction::Opcode op) {
+  return os << willow::Instruction::opcodeName(op);
+}
+
+inline std::ostream& operator<<(std::ostream &os, const willow::Instruction &inst) {
+  auto vty = inst.getType();
+
+  os << vty << " " << willow::Instruction::opcodeName(inst.opcode());
+
+  for (auto *operand : inst.getOperands())
+    os << " " << operand;
+
+  return os;
+}
 
 #endif // WILLOW_INCLUDE_IR_INSTRUCTION_H
diff --git a/willow/include/willow/IR/Location.h b/willow/include/willow/IR/Location.h
index e0ce838..c3c241d 100644
--- a/willow/include/willow/IR/Location.h
+++ b/willow/include/willow/IR/Location.h
@@ -25,7 +25,7 @@ struct std::formatter<willow::Location> {
   }
 };
 
-std::ostream &operator<<(std::ostream &os, const willow::Location &loc) {
+inline std::ostream &operator<<(std::ostream &os, const willow::Location &loc) {
   return os << std::format("{}", loc);
 }
 
diff --git a/willow/include/willow/IR/Types.h b/willow/include/willow/IR/Types.h
index 9a4f868..40bb098 100644
--- a/willow/include/willow/IR/Types.h
+++ b/willow/include/willow/IR/Types.h
@@ -4,6 +4,7 @@
 #include <cstddef>
 #include <format>
 #include <functional>
+#include <utility>
 
 #include <willow/Util/Hashing.h>
 
@@ -118,23 +119,25 @@ public:
 };
 
 constexpr std::string_view primitiveTypeName(TypeID tid) {
+  using namespace std::string_view_literals;
   using enum TypeID;
   switch (tid) {
   case TypeID::Void:
-    return "void";
+    return "void"sv;
   case TypeID::BasicBlock:
-    return "label";
+    return "label"sv;
   case TypeID::Int:
-    return "int";
+    return "int"sv;
   case TypeID::Function:
-    return "function";
+    return "function"sv;
   case TypeID::Ptr:
-    return "ptr";
+    return "ptr"sv;
   case TypeID::Struct:
-    return "struct";
+    return "struct"sv;
   case TypeID::Vector:
-    return "vector";
+    return "vector"sv;
   }
+  std::unreachable();
 }
 
 class BasicBlockTypeImpl : public TypeImpl {
@@ -162,10 +165,10 @@ public:
   struct Hash {
     size_t operator()(const Key &k) const noexcept {
       std::size_t seed = 0;
-      willow::hashing::combine(seed, k.ret);
+      willow::hashing::combine(seed, k.ret.getImpl());
       willow::hashing::combine(seed, k.params.size());
       for (const auto &ty : k.params)
-        willow::hashing::combine(seed, ty);
+        willow::hashing::combine(seed, ty.getImpl());
 
       return seed;
     }
@@ -204,7 +207,7 @@ struct std::formatter<willow::Type> {
   }
 };
 
-std::ostream &operator<<(std::ostream &os, willow::Type ty) {
+inline std::ostream &operator<<(std::ostream &os, willow::Type ty) {
   return os << std::format("{}", ty);
 }
 
diff --git a/willow/include/willow/IR/Value.h b/willow/include/willow/IR/Value.h
index c219788..650e773 100644
--- a/willow/include/willow/IR/Value.h
+++ b/willow/include/willow/IR/Value.h
@@ -7,11 +7,13 @@
 #include <string>
 #include <string_view>
 #include <unordered_map>
+#include <ostream>
 
 namespace willow {
 
 class Instruction;
 class BasicBlock;
+class Constant;
 
 enum class ValueKind {
   Instruction, ///< the identified result of an instruction
@@ -82,4 +84,6 @@ public:
 
 } // namespace willow
 
+inline std::ostream &operator<<(std::ostream &os, const willow::Value &v);
+
 #endif // WILLOW_INCLUDE_IR_VALUE_H