init

wip

wip, pt2

wip, pt3

8 files changed, 552 insertions, 0 deletions

diff --git a/willow/include/willow/IR/BasicBlock.h b/willow/include/willow/IR/BasicBlock.h
new file mode 100644
index 0000000..d783a5b
--- /dev/null
+++ b/willow/include/willow/IR/BasicBlock.h
@@ -0,0 +1,98 @@
+#ifndef WILLOW_IR_BASIC_BLOCK_H
+#define WILLOW_IR_BASIC_BLOCK_H
+
+#include <willow/IR/Instruction.h>
+
+#include <list>
+#include <memory>
+#include <ranges>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace willow {
+
+class Function;
+
+/// A group of consecutive instructions.
+class BasicBlock {
+  std::string name;
+  Function *parent = nullptr;
+
+  std::list<std::unique_ptr<Instruction>> body;
+
+  std::vector<BasicBlock *> preds;
+  std::vector<BasicBlock *> succs;
+
+public:
+  // ~BasicBlock() = TODO
+  /// Create a basic block with a name and parent function.
+  BasicBlock(std::string name, Function *parent)
+      : name(std::move(name)), parent(parent) {}
+
+  std::string_view getName() const { return name; }
+  void setName(std::string name) { this->name = std::move(name); }
+
+  Function *getParent() const { return parent; }
+  bool hasParent() const { return parent; }
+  void setParent(Function *parent) { this->parent = parent; }
+
+  bool empty() const { return body.empty(); }
+  std::size_t size() { return body.size(); }
+
+  auto getBody() {
+    return body |
+           std::views::transform([](auto &p) -> Instruction & { return *p; });
+  }
+
+  auto getBody() const {
+    return body | std::views::transform(
+                      [](auto &p) -> const Instruction & { return *p; });
+  }
+
+  Instruction *trailer();
+  Instruction *leader();
+
+  Instruction *addInstruction(std::unique_ptr<Instruction> inst);
+
+  template <typename... Args>
+  Instruction *emplaceInstruction(Args &&...args) {
+    body.push_back(std::make_unique<Instruction>(std::forward(args)...));
+    return body.back().get();
+  }
+
+  const std::vector<BasicBlock *> &predecessors() const { return preds; }
+  std::vector<BasicBlock *> &predecessors() { return preds; }
+
+  const std::vector<BasicBlock *> &successors() const { return succs; }
+  std::vector<BasicBlock *> &successors() { return succs; }
+
+  void addPredecessor(BasicBlock *pred) { preds.push_back(pred); }
+  void addSuccessor(BasicBlock *succ) { succs.push_back(succ); }
+  // TODO: add/remove preds
+};
+
+Instruction *BasicBlock::trailer() {
+  if (empty())
+    return nullptr;
+  else
+    return body.back().get();
+}
+
+Instruction *BasicBlock::leader() {
+  if (empty())
+    return nullptr;
+  else
+    return body.back().get();
+}
+
+Instruction *BasicBlock::addInstruction(std::unique_ptr<Instruction> inst) {
+  Instruction *p = inst.get();
+  body.push_back(std::move(inst));
+  return p;
+}
+
+} // namespace willow
+
+#endif // WILLOW_IR_BASIC_BLOCK_H
diff --git a/willow/include/willow/IR/Function.h b/willow/include/willow/IR/Function.h
new file mode 100644
index 0000000..97e4029
--- /dev/null
+++ b/willow/include/willow/IR/Function.h
@@ -0,0 +1,104 @@
+#ifndef WILLOW_IR_FUNCTION_H
+#define WILLOW_IR_FUNCTION_H
+
+#include <willow/IR/BasicBlock.h>
+#include <willow/IR/Value.h>
+
+#include <memory>
+#include <ranges>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace willow {
+
+class Module;
+
+/// Groups basic blocks and the values they define.
+class Function {
+  std::string name;
+  Module *parent = nullptr;
+
+  std::vector<std::unique_ptr<BasicBlock>> blocks;
+  std::vector<std::unique_ptr<Value>> values;
+
+public:
+  /// Create a function with a name and its owning module.
+  /// \param name Function identifier.
+  /// \param parent Owning module.
+  Function(std::string name, Module *parent)
+      : name(std::move(name)), parent(parent) {}
+
+  std::string_view getName() const { return name; }
+  void setName(std::string name) { this->name = std::move(name); }
+
+  /// \return Parent module or nullptr.
+  Module *getParent() { return parent; }
+  const Module *getParent() const { return parent; }
+  void setParent(Module *parent) { this->parent = parent; }
+
+  /// \return Entry block or nullptr.
+  BasicBlock *entryBlock();
+  const BasicBlock *entryBlock() const;
+
+  bool empty() const { return blocks.empty(); }
+  std::size_t numBlocks() const { return blocks.size(); }
+
+  /// \return The blocks that make up this function.
+  auto getBlocks() {
+    return blocks |
+           std::views::transform([](auto &p) -> BasicBlock & { return *p; });
+  }
+
+  auto getBlocks() const {
+    return blocks | std::views::transform(
+                        [](auto &p) -> const BasicBlock & { return *p; });
+  }
+
+  /// \return The SSA values that exist in this block.
+  auto getValues() {
+    return blocks |
+           std::views::transform([](auto &p) -> Value & { return *p; });
+  }
+  auto getValues() const {
+    return blocks |
+           std::views::transform([](auto &p) -> const Value & { return *p; });
+  }
+
+  /// Append an existing block, transferring ownership.
+  /// \param block Basic block to append.
+  /// \return Raw pointer to the appended block.
+  BasicBlock *addBlock(std::unique_ptr<BasicBlock> block) {
+    auto p = block.get();
+    blocks.push_back(std::move(block));
+    p->setParent(this);
+    return p;
+  }
+
+  /// Construct a new block in-place and append it.
+  /// \return Raw pointer to the appended block.
+  template <typename... Args>
+  BasicBlock *createBlock(Args &&...args) {
+    blocks.push_back(std::make_unique<BasicBlock>(std::forward<Args>(args)...));
+    return blocks.back().get();
+  }
+};
+
+const BasicBlock *Function::entryBlock() const {
+  if (blocks.empty())
+    return nullptr;
+  else
+    return blocks.front().get();
+}
+
+BasicBlock *Function::entryBlock() {
+  if (blocks.empty())
+    return nullptr;
+  else
+    return blocks.front().get();
+}
+
+} // namespace willow
+
+#endif // WILLOW_IR_FUNCTION_H
diff --git a/willow/include/willow/IR/IRBuilder.h b/willow/include/willow/IR/IRBuilder.h
new file mode 100644
index 0000000..79d3bb3
--- /dev/null
+++ b/willow/include/willow/IR/IRBuilder.h
@@ -0,0 +1,20 @@
+#ifndef WILLOW_IR_IR_BUILDER_H
+#define WILLOW_IR_IR_BUILDER_H
+
+#include <willow/IR/BasicBlock.h>
+#include <willow/IR/Function.h>
+#include <willow/IR/Instruction.h>
+
+namespace willow {
+
+/// Helper for constructing and modifiying IR.
+class IRBuilder {
+  BasicBlock *block = nullptr;
+
+public:
+  explicit IRBuilder(BasicBlock *block) : block(block);
+};
+
+} // namespace willow
+
+#endif // WILLOW_IR_IR_BUILDER_H
diff --git a/willow/include/willow/IR/Instruction.h b/willow/include/willow/IR/Instruction.h
new file mode 100644
index 0000000..c7756bb
--- /dev/null
+++ b/willow/include/willow/IR/Instruction.h
@@ -0,0 +1,61 @@
+#ifndef WILLOW_IR_INSTRUCTION_HPP
+#define WILLOW_IR_INSTRUCTION_HPP
+
+#include <willow/IR/Value.h>
+
+namespace willow {
+
+class Value;
+
+/// Defines an SSA value or control-flow effect.
+class Instruction : Value {
+public:
+  enum class Op {
+    Const,
+
+    Add,
+    Mul,
+    Sub,
+    Div,
+    Mod,
+    Shl,
+    Shr,
+
+    Eq,
+    Lt,
+    Gt,
+    Le,
+    Ge,
+
+    Not,
+    And,
+    Or,
+
+    Jmp,
+    Br,
+    Call,
+    Ret,
+
+    Phi,
+    Alloca
+  };
+
+private:
+  class BasicBlock *parent = nullptr;
+  Op op;
+
+public:
+  /// \param op Opcode for this instruction.
+  /// \param val SSA value defined by this instruction (may be nullptr).
+  Instruction(Op op, Value *val);
+
+  Op getOp() const { return op; }
+
+  const Value *getValue() const { return value; }
+  Value *getValue() { return value; }
+  bool hasValue() const { return value; }
+};
+
+} // namespace willow
+
+#endif // WILLOW_IR_INST_HPP
diff --git a/willow/include/willow/IR/Module.h b/willow/include/willow/IR/Module.h
new file mode 100644
index 0000000..2002a90
--- /dev/null
+++ b/willow/include/willow/IR/Module.h
@@ -0,0 +1,54 @@
+#ifndef WILLOW_IR_MODULE_H
+#define WILLOW_IR_MODULE_H
+
+#include <willow/IR/Function.h>
+
+namespace willow {
+
+/// Represents a compilation unit.
+class Module {
+  std::string name;
+  std::vector<std::unique_ptr<Function>> functions;
+
+public:
+  explicit Module(std::string name) : name(std::move(name)) {}
+
+  /// Moves a Function to this module, transfering ownership.
+  /// \param fn The function to move.
+  /// \return A raw pointer to the function.
+  Function *addFunction(std::unique_ptr<Function> fn);
+
+  template <typename... Args>
+  Function *emplaceFunction(Args &&...args) {
+    functions.push_back(
+        std::make_unique<Function>(std::forward<Args>(args)...));
+    auto *fn = functions.back().get();
+    fn->setParent(this);
+    return fn;
+  }
+
+  std::string_view getName() const { return name; }
+  void setName(std::string name) { this->name = std::move(name); }
+
+  std::size_t numFunctions() const { return functions.size(); }
+
+  auto getFunctions() {
+    return functions |
+           std::views::transform([](auto &p) -> Function & { return *p; });
+  }
+  auto getFunctions() const {
+    return functions | std::views::transform(
+                           [](auto &p) -> const Function & { return *p; });
+  }
+};
+
+Function *Module::addFunction(std::unique_ptr<Function> fn) {
+  auto p = fn.get();
+  functions.push_back(std::move(fn));
+  p->setParent(this);
+  return p;
+}
+
+} // namespace willow
+
+#endif // WILLOW_IR_MODULE_H
diff --git a/willow/include/willow/IR/TypeContext.h b/willow/include/willow/IR/TypeContext.h
new file mode 100644
index 0000000..d1323f0
--- /dev/null
+++ b/willow/include/willow/IR/TypeContext.h
@@ -0,0 +1,57 @@
+#ifndef _WILLOW_INCLUDE_TYPE_CONTEXT_H
+#define _WILLOW_INCLUDE_TYPE_CONTEXT_H
+
+#include <willow/IR/Types.h>
+
+#include <memory>
+#include <unordered_map>
+
+namespace willow {
+
+/// Context that owns and uniques type instances.
+class TypeContext {
+public:
+  TypeContext() = default;
+  TypeContext(const TypeContext &) = delete;
+  TypeContext &operator=(const TypeContext &) = delete;
+
+  /// \param width Bit width of the integer type.
+  /// \return Uniqued integer type for the requested width.
+  Type getIntType(std::size_t width);
+
+  /// \param pointee Type of the pointee.
+  /// \param size Size in bits of the pointer representation.
+  /// \return Uniqued pointer type.
+  Type getPtrType(Type pointee, std::size_t size);
+
+  /// \return Uniqued void type.
+  Type getVoidType();
+
+private:
+  std::unordered_map<IntTypeImpl::Key, std::unique_ptr<IntTypeImpl>,
+                     IntTypeImpl::Hash>
+      icache;
+  std::unordered_map<PtrTypeImpl::Key, std::unique_ptr<PtrTypeImpl>,
+                     PtrTypeImpl::Hash>
+      pcache;
+  std::unique_ptr<VoidTypeImpl> voidty;
+};
+
+Type TypeContext::getIntType(std::size_t width) {
+  auto [it, _] = icache.try_emplace(IntTypeImpl::Key{width});
+
+  return Type(it->second.get());
+}
+
+Type TypeContext::getPtrType(Type pointee, std::size_t size) {
+  auto [it, _] = pcache.try_emplace(
+      PtrTypeImpl::Key{pointee}, std::make_unique<PtrTypeImpl>(pointee, size));
+
+  return Type(it->second.get());
+}
+
+Type TypeContext::getVoidType() { return Type(voidty.get()); }
+
+} // namespace willow
+
+#endif // _WILLOW_INCLUDE_TYPE_CONTEXT_H
diff --git a/willow/include/willow/IR/Types.h b/willow/include/willow/IR/Types.h
new file mode 100644
index 0000000..85f4a67
--- /dev/null
+++ b/willow/include/willow/IR/Types.h
@@ -0,0 +1,108 @@
+#ifndef _WILLOW_IR_TYPES_H
+#define _WILLOW_IR_TYPES_H
+
+#include <cstddef>
+#include <functional>
+#include <ostream>
+
+namespace willow {
+
+/// IDs of all base types.
+enum class TypeID {
+  // Primitive types
+  Void,  ///< Void type
+  Label, ///< Label type
+
+  // Parameterized types
+  Int,      ///< Integer type of any bit width
+  Function, ///< A Function symbol
+  Ptr,      ///< Parameterized pointer type
+  Struct,   ///< Aggregate struct type
+  Vector,   ///< Vector type
+};
+
+class TypeImpl;
+
+class TypeImpl {
+  friend class TypeContext;
+  TypeID kind;
+  std::size_t num_bits;
+
+protected:
+  explicit TypeImpl(TypeID kind) : kind{kind} {}
+  explicit TypeImpl(TypeID kind, size_t num_bits)
+      : kind{kind}, num_bits{num_bits} {}
+
+public:
+  virtual ~TypeImpl() = default;
+  TypeID getTypeKind() const { return kind; }
+  std::size_t getNumBits() const { return num_bits; }
+};
+
+/// Instances of Type represent uniqued, immutable datatypes.
+///
+/// Internally, Type instances wrap a pointer to a TypeImpl, so they should be
+/// passed by value.
+class Type {
+  friend class TypeContext;
+  TypeImpl *impl;
+
+public:
+  explicit Type(TypeImpl *impl) : impl(impl) {}
+
+  bool operator==(const Type &other) const { return impl == other.impl; }
+  bool operator!=(const Type &other) const { return impl != other.impl; }
+  // Type() : impl(nullptr) {}
+
+  TypeID kind() const { return impl->getTypeKind(); };
+  std::size_t getNumBits() const { return impl->getNumBits(); };
+  TypeImpl *getImpl() const { return this->impl; }
+
+  bool isInt() const { return kind() == TypeID::Int; }
+  bool isPtr() const { return kind() == TypeID::Ptr; }
+  bool isVoid() const { return kind() == TypeID::Void; }
+};
+
+class IntTypeImpl : public TypeImpl {
+public:
+  explicit IntTypeImpl(std::size_t num_bits)
+      : TypeImpl{TypeID::Int, num_bits} {}
+
+  struct Key {
+    std::size_t num_bits;
+    Key(std::size_t w) : num_bits(w) {}
+
+    bool operator==(const Key &k) const { return this->num_bits == k.num_bits; }
+  };
+
+  struct Hash {
+    std::size_t operator()(const Key &k) const noexcept {
+      return std::hash<size_t>{}(k.num_bits);
+    }
+  };
+};
+
+class PtrTypeImpl : public TypeImpl {
+  Type pointee;
+
+public:
+  PtrTypeImpl(Type pointee_type, std::size_t size)
+      : TypeImpl{TypeID::Ptr, size}, pointee{pointee_type.getImpl()} {}
+
+  struct Key {
+    Type pointee;
+    explicit Key(Type pointee) : pointee{pointee} {}
+
+    bool operator==(const Key &k) const { return this->pointee == k.pointee; }
+  };
+
+  struct Hash {
+    std::size_t operator()(const Key &k) const noexcept {
+      return std::hash<TypeImpl *>{}(k.pointee.getImpl());
+    }
+  };
+};
+
+}; // namespace willow
+
+#endif // _WILLOW_IR_TYPES_H
diff --git a/willow/include/willow/IR/Value.h b/willow/include/willow/IR/Value.h
new file mode 100644
index 0000000..a819b53
--- /dev/null
+++ b/willow/include/willow/IR/Value.h
@@ -0,0 +1,50 @@
+#ifndef _WILLOW_IR_VALUE_HPP
+#define _WILLOW_IR_VALUE_HPP
+
+// #include <willow/IR/Instruction.h>
+#include <willow/IR/Types.h>
+
+#include <string>
+#include <string_view>
+#include <vector>
+
+namespace willow {
+
+class Instruction;
+
+enum class ValueType {
+  Result,    ///< the identified result of an instruction
+  Parameter, ///< the named parameter to a function
+  Literal,   ///< an anonymous typed literal
+};
+
+/// An SSA value that may be used.
+class Value {
+  std::string name;
+  ValueType value_type;
+  Type type;
+
+  // Instructions that use this value
+  std::vector<Instruction *> uses;
+
+public:
+  Value(std::string name, Type type) : name(std::move(name)), type(type) {}
+  explicit Value(Type type) : type(type) {}
+
+  bool hasName() const { return !name.empty(); }
+
+  std::string_view getName() const { return name; }
+  void setName(std::string name) { this->name = std::move(name); }
+
+  Type getType() const { return type; }
+  ValueType getValueType() const { return value_type; }
+
+  bool isVoid() const { return type->is }
+
+  const std::vector<Instruction *> &getUses() const { return uses; }
+  std::vector<Instruction *> &getUses() { return uses; }
+};
+
+} // namespace willow
+
+#endif // _WILLOW_IR_VALUE_HPP