[willow]: iron out design (#6)

14 files changed, 573 insertions, 280 deletions

diff --git a/nix/flake.nix b/nix/flake.nix
index 240619c..91ec511 100644
--- a/nix/flake.nix
+++ b/nix/flake.nix
@@ -33,6 +33,7 @@
             nix
             git
             gcc
+            graphviz
 
             doxygen
             ccache
diff --git a/willow/docs/doxygen/Doxyfile b/willow/docs/doxygen/Doxyfile
index 3587e1b..7983449 100644
--- a/willow/docs/doxygen/Doxyfile
+++ b/willow/docs/doxygen/Doxyfile
@@ -18,3 +18,5 @@ HTML_HEADER = willow/docs/doxygen/header.html
 HTML_EXTRA_FILES = willow/docs/doxygen/doxygen-awesome-darkmode-toggle.js
 HTML_COLORSTYLE = LIGHT
 HTML_COPY_CLIPBOARD = NO
+HAVE_DOT=YES
+DOT_IMAGE_FORMAT = svg
diff --git a/willow/include/willow/IR/BasicBlock.h b/willow/include/willow/IR/BasicBlock.h
index dde432a..753c04a 100644
--- a/willow/include/willow/IR/BasicBlock.h
+++ b/willow/include/willow/IR/BasicBlock.h
@@ -3,6 +3,7 @@
 
 #include <willow/IR/Instruction.h>
 #include <willow/IR/Location.h>
+#include <willow/IR/Value.h>
 
 #include <list>
 #include <memory>
@@ -16,26 +17,21 @@ namespace willow {
 
 class Function;
 
-/// A group of consecutive instructions.
-class BasicBlock {
-  std::string name;
+/// A sequence of consecutively executed instructions, followed by a terminator.
+class BasicBlock : public Value {
   Function *parent = nullptr;
 
   std::optional<Location> loc;
 
   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); }
+  BasicBlock(std::string name, Function *parent, Type bbty,
+             std::optional<Location> loc)
+      : Value(ValueKind::BasicBlock, std::move(name), bbty), parent(parent),
+        loc(loc) {}
 
   Function *getParent() const { return parent; }
   bool hasParent() const { return parent; }
@@ -68,17 +64,7 @@ public:
     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; }
-
   std::optional<Location> getLoc() const { return loc; }
-
-  void addPredecessor(BasicBlock *pred) { preds.push_back(pred); }
-  void addSuccessor(BasicBlock *succ) { succs.push_back(succ); }
-  // TODO: add/remove preds
 };
 
 Instruction *BasicBlock::trailer() {
diff --git a/willow/include/willow/IR/Constant.h b/willow/include/willow/IR/Constant.h
index d93d65d..4476ac6 100644
--- a/willow/include/willow/IR/Constant.h
+++ b/willow/include/willow/IR/Constant.h
@@ -9,6 +9,7 @@ enum class ConstantKind {
   Int,    //< Integer value with known bits
   Undef,  //< Known undef
   Poison, //< Known poison
+  Label,  //< Known reference to a BasicBlock
 };
 
 class Constant : public Value {
@@ -87,6 +88,11 @@ public:
   explicit PoisonVal(Type ty) : Constant(ty, ConstantKind::Poison) {}
 };
 
+class BlockRef final : public Constant {
+public:
+  explicit BlockRef(Type ty, Block *b) : Constant(ty, ConstantKind::Label) {}
+};
+
 } // namespace willow
 
 #endif // WILLOW_INCLUDE_IR_CONSTANT_H
diff --git a/willow/include/willow/IR/Function.h b/willow/include/willow/IR/Function.h
index 4b2bd94..dd11553 100644
--- a/willow/include/willow/IR/Function.h
+++ b/willow/include/willow/IR/Function.h
@@ -2,6 +2,7 @@
 #define WILLOW_INCLUDE_IR_FUNCTION_H
 
 #include <willow/IR/BasicBlock.h>
+#include <willow/IR/Types.h>
 #include <willow/IR/Value.h>
 
 #include <memory>
@@ -16,22 +17,26 @@ namespace willow {
 class Module;
 
 /// Groups basic blocks and the values they define.
-class Function {
-  std::string name;
+class Function : public Value {
   Module *parent = nullptr;
 
   std::vector<std::unique_ptr<BasicBlock>> blocks;
   std::vector<std::unique_ptr<Value>> values;
+  std::vector<std::unique_ptr<Parameter>> params;
 
 public:
   /// Create a function with a name and its owning module.
-  /// \param name Function identifier.
+  ///
+  /// This should usually not be called directly.
+  /// \param name   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); }
+  /// \param ty     Signature. Should be
+  /// \param params List of named parameters to the function. Should match \p
+  /// ty.
+  Function(std::string name, Module *parent, Type fty,
+           std::vector<std::unique_ptr<Parameter>> params)
+      : Value(ValueKind::Function, std::move(name), fty), parent(parent),
+        params(std::move(params)) {}
 
   /// \return Parent module or nullptr.
   Module *getParent() { return parent; }
@@ -83,6 +88,13 @@ public:
     blocks.push_back(std::make_unique<BasicBlock>(std::forward<Args>(args)...));
     return blocks.back().get();
   }
+
+  Type getReturnType() const {
+    assert(getType().isFunction() && "Function has non-function type.");
+    auto *impl = static_cast<FunctionTypeImpl *>(getType().getImpl());
+
+    return impl->rty;
+  }
 };
 
 const BasicBlock *Function::entryBlock() const {
diff --git a/willow/include/willow/IR/Instruction.h b/willow/include/willow/IR/Instruction.h
index 0702b20..17981ea 100644
--- a/willow/include/willow/IR/Instruction.h
+++ b/willow/include/willow/IR/Instruction.h
@@ -2,12 +2,14 @@
 #define WILLOW_INCLUDE_IR_INSTRUCTION_H
 
 #include <willow/IR/Location.h>
+#include <willow/IR/Types.h>
 #include <willow/IR/Value.h>
 #include <willow/Util/LogicalResult.h>
 
 #include <cassert>
 #include <cstddef>
 #include <optional>
+#include <ostream>
 #include <utility>
 #include <vector>
 
@@ -17,37 +19,55 @@ class Value;
 class BasicBlock;
 class Function;
 
+/// Helper structure for passing around the successors of a block
+///
+/// A terminator can induce at most two succesors, so no need to allocate.
+class Successors {
+  friend class Instruction;
+  std::array<BasicBlock *, 2> data;
+  uint8_t n = 0;
+
+public:
+  auto begin() { return data.data(); }
+  auto begin() const { return data.data(); }
+  auto end() { return data.data() + n; }
+  auto end() const { return data.data() + n; }
+  size_t size() const { return n; }
+
+  BasicBlock *operator[](std::size_t i) const { return data[i]; }
+};
+
 /// Defines an IR instruction.
 class Instruction : public Value {
 public:
   enum class Opcode {
-    Add,
-    Mul,
-    Sub,
-    Div,
-    Mod,
-    Shl,
-    Shr,
-    Ashl,
-    Ashr,
-
-    Eq,
-    Lt,
-    Gt,
-    Le,
-    Ge,
-
-    And,
-    Or,
-    Not,
-
-    Jmp,
-    Br,
-    Call,
-    Ret,
-
-    Phi,
-    Alloca
+    Add,  ///< Int addition
+    Mul,  ///< Int multiplication
+    Sub,  ///< Int subtraction
+    Div,  ///< Int division
+    Mod,  ///< Int modulo
+    Shl,  ///< Int shift left
+    Shr,  ///< Int shift right
+    Ashl, ///< Int shift left arithmetic
+    Ashr, ///< Int shift right arithmetic
+
+    Eq, ///< %0 == %1
+    Lt, ///< %0 <  %1
+    Gt, ///< %0 >  %1
+    Le, ///< %0 <= %1
+    Ge, ///< %0 >= %1
+
+    And, ///< logical and
+    Or,  ///< logical or
+    Not, ///< logical not
+
+    Jmp,  ///< goto %0
+    Br,   ///< goto (%0 ? %1 : %2)
+    Call, ///< call %0 <args>
+    Ret,  ///< ret val?
+
+    Phi,   ///< phi ^label1 %val1 ^label2 %val2 ...
+    Alloca ///< %a : ptr<type> = alloca type
   };
 
 private:
@@ -56,7 +76,6 @@ private:
 
   std::optional<Location> loc;
   std::vector<Value *> operands;
-  std::vector<BasicBlock *> successors;
 
 protected:
   void setOperand(std::size_t index, Value *operand) {
@@ -73,7 +92,7 @@ protected:
 
 public:
   /// \param op Opcode for this instruction.
-  /// \param type Type of the result of this instruction
+  /// \param type Type of the result of this instruction.
   /// \param loc Source location of this instruction.
   Instruction(Opcode op, Type type, std::optional<Location> loc = std::nullopt)
       : Value(ValueKind::Instruction, type), op(op), loc(loc) {}
@@ -82,7 +101,7 @@ public:
   /// \param op Opcode for the instruction.
   /// \param type Type of the result of the instruction.
   /// \param loc Source location of this instruction.
-  Instruction(std::string name, Type type, Opcode op,
+  Instruction(std::string name, Opcode op, Type type,
               std::optional<Location> loc = std::nullopt)
       : Value(ValueKind::Instruction, std::move(name), type), op(op), loc(loc) {
   }
@@ -99,41 +118,8 @@ public:
 
   std::optional<Location> getLoc() const { return loc; }
 
-  const std::vector<BasicBlock *> &succs() const { return successors; }
-  std::vector<BasicBlock *> &succs() { return successors; }
-
-  void addSuccessor(BasicBlock *successor) { successors.push_back(successor); }
-
-  static bool isTerminatorOp(Opcode op) {
-    using enum Opcode;
-    switch (op) {
-    case Jmp:
-    case Br:
-    case Call:
-    case Ret:
-      return true;
-    case Add:
-    case Mul:
-    case Sub:
-    case Div:
-    case Mod:
-    case Shl:
-    case Shr:
-    case Ashl:
-    case Ashr:
-    case Eq:
-    case Lt:
-    case Gt:
-    case Le:
-    case Ge:
-    case And:
-    case Or:
-    case Not:
-    case Phi:
-    case Alloca:
-      return false;
-    }
-  }
+  static bool isTerminatorOp(Opcode op);
+  Successors succs();
 
   bool isTerminator() const { return isTerminatorOp(op); }
 
@@ -144,6 +130,7 @@ public:
     assert(index < operands.size() && "Operand index out of bounds");
     return operands[index];
   }
+
   const Value *getOperand(std::size_t index) const {
     assert(index < operands.size() && "Operand index out of bounds");
     return operands[index];
@@ -157,175 +144,79 @@ public:
     operands.push_back(operand);
     operand->addUse(this);
   }
-};
-
-/// The base class for unary integer arithemetic instructions
-class UnaryInst : public Instruction {
-public:
-  UnaryInst(std::string name, Type type, Opcode op, Value *value,
-            std::optional<Location> loc = std::nullopt)
-      : Instruction(std::move(name), type, op, loc) {
-    addOperand(value);
-  }
 
-  Value *getValue() { return getOperand(0); }
-  const Value *getValue() const { return getOperand(0); }
-};
-
-/// The base class for binary integer arithemetic instructions
-class BinaryInst : public Instruction {
-public:
-  BinaryInst(std::string name, Type type, Opcode op, Value *lhs, Value *rhs,
-             std::optional<Location> loc = std::nullopt)
-      : Instruction(std::move(name), type, op, loc) {
-    addOperand(lhs);
-    addOperand(rhs);
+  static constexpr std::string_view opcodeName(Opcode op);
+};
+
+constexpr std::string_view Instruction::opcodeName(Instruction::Opcode op) {
+  using enum Instruction::Opcode;
+  switch (op) {
+  case Add:
+    return "add";
+  case Mul:
+    return "mul";
+  case Sub:
+    return "sub";
+  case Div:
+    return "div";
+  case Mod:
+    return "mod";
+  case Shl:
+    return "shl";
+  case Shr:
+    return "shr";
+  case Ashl:
+    return "ashl";
+  case Ashr:
+    return "ashr";
+  case Eq:
+    return "eq";
+  case Lt:
+    return "lt";
+  case Gt:
+    return "gt";
+  case Le:
+    return "le";
+  case Ge:
+    return "ge";
+  case And:
+    return "and";
+  case Or:
+    return "or";
+  case Not:
+    return "not";
+  case Jmp:
+    return "jmp";
+  case Br:
+    return "br";
+  case Call:
+    return "call";
+  case Ret:
+    return "ret";
+  case Phi:
+    return "phi";
+  case Alloca:
+    return "alloca";
   }
+}
 
-  Value *getLHS() { return getOperand(0); }
-  const Value *getLHS() const { return getOperand(0); }
-
-  Value *getRHS() { return getOperand(1); }
-  const Value *getRHS() const { return getOperand(1); }
-};
-
-class AddInst : public BinaryInst {
-public:
-  AddInst(std::string name, Type type, Value *lhs, Value *rhs,
-          std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Add, lhs, rhs, loc) {}
-};
-
-class MulInst : public BinaryInst {
-public:
-  MulInst(std::string name, Type type, Value *lhs, Value *rhs,
-          std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Mul, lhs, rhs, loc) {}
-};
-
-class SubInst : public BinaryInst {
-public:
-  SubInst(std::string name, Type type, Value *lhs, Value *rhs,
-          std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Sub, lhs, rhs, loc) {}
-};
-
-class DivInst : public BinaryInst {
-public:
-  DivInst(std::string name, Type type, Value *lhs, Value *rhs,
-          std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Div, lhs, rhs, loc) {}
-};
-
-class ModInst : public BinaryInst {
-public:
-  ModInst(std::string name, Type type, Value *lhs, Value *rhs,
-          std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Mod, lhs, rhs, loc) {}
-};
-
-class ShlInst : public BinaryInst {
-public:
-  ShlInst(std::string name, Type type, Value *lhs, Value *rhs,
-          std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Shl, lhs, rhs, loc) {}
-};
-
-class ShrInst : public BinaryInst {
-public:
-  ShrInst(std::string name, Type type, Value *lhs, Value *rhs,
-          std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Shr, lhs, rhs, loc) {}
-};
-
-class EqInst : public BinaryInst {
-public:
-  EqInst(std::string name, Type type, Value *lhs, Value *rhs,
-         std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Eq, lhs, rhs, loc) {}
-};
-
-class LtInst : public BinaryInst {
-public:
-  LtInst(std::string name, Type type, Value *lhs, Value *rhs,
-         std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Lt, lhs, rhs, loc) {}
-};
-
-class GtInst : public BinaryInst {
-public:
-  GtInst(std::string name, Type type, Value *lhs, Value *rhs,
-         std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Gt, lhs, rhs, loc) {}
-};
-
-class LeInst : public BinaryInst {
-public:
-  LeInst(std::string name, Type type, Value *lhs, Value *rhs,
-         std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Le, lhs, rhs, loc) {}
-};
-
-class GeInst : public BinaryInst {
-public:
-  GeInst(std::string name, Type type, Value *lhs, Value *rhs,
-         std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Ge, lhs, rhs, loc) {}
-};
-
-class AndInst : public BinaryInst {
-public:
-  AndInst(std::string name, Type type, Value *lhs, Value *rhs,
-          std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::And, lhs, rhs, loc) {}
-};
-
-class OrInst : public BinaryInst {
-public:
-  OrInst(std::string name, Type type, Value *lhs, Value *rhs,
-         std::optional<Location> loc = std::nullopt)
-      : BinaryInst(std::move(name), type, Opcode::Or, lhs, rhs, loc) {}
-};
-
-class NotInst : public UnaryInst {
-public:
-  explicit NotInst(std::string name, Type type, Value *value,
-                   std::optional<Location> loc = std::nullopt)
-      : UnaryInst(std::move(name), type, Opcode::Not, value, loc) {}
-};
-
-class JmpInst : public Instruction {
-public:
-  JmpInst(Type type, BasicBlock *target,
-          std::optional<Location> loc = std::nullopt)
-      : Instruction(Opcode::Jmp, type, loc) {
-    addSuccessor(target);
-  }
+} // namespace willow
 
-  BasicBlock *getTarget() { return succs()[0]; }
-  const BasicBlock *getTarget() const { return succs()[0]; }
-};
+template <>
+struct std::formatter<willow::Instruction::Opcode> {
+  constexpr auto parse(std::format_parse_context &ctx) { return ctx.begin(); }
 
-class BrInst : public Instruction {
-public:
-  BrInst(Type type, Value *condition, BasicBlock *true_target,
-         BasicBlock *false_target, std::optional<Location> loc = std::nullopt)
-      : Instruction(Opcode::Br, type, loc) {
-    addOperand(condition);
-    addSuccessor(true_target);
-    addSuccessor(false_target);
+  constexpr auto format(const willow::Instruction::Opcode &op,
+                        std::format_context &ctx) const {
+    return std::format_to(ctx.out(), "{}", willow::Instruction::opcodeName(op));
   }
-
-  Value *getCondition() { return getOperand(0); }
-  const Value *getCondition() const { return getOperand(0); }
-
-  BasicBlock *getTrueTarget() { return succs()[0]; }
-  const BasicBlock *getTrueTarget() const { return succs()[0]; }
-
-  BasicBlock *getFalseTarget() { return succs()[1]; }
-  const BasicBlock *getFalseTarget() const { return succs()[1]; }
 };
 
-} // namespace willow
+// std::ostream& operator<<(std::ostream &os, const willow::Instruction &inst) {
+//   auto vty = inst.getType();
+//
+//   // int add %i %
+//   os << vty << " " << inst.opcode() << " "
+// }
 
 #endif // WILLOW_INCLUDE_IR_INSTRUCTION_H
diff --git a/willow/include/willow/IR/Instructions.h b/willow/include/willow/IR/Instructions.h
new file mode 100644
index 0000000..d1d41fa
--- /dev/null
+++ b/willow/include/willow/IR/Instructions.h
@@ -0,0 +1,257 @@
+#ifndef WILLOW_INCLUDE_IR_INSTRUCTIONS_H
+#define WILLOW_INCLUDE_IR_INSTRUCTIONS_H
+
+#include <willow/IR/BasicBlock.h>
+#include <willow/IR/Function.h>
+#include <willow/IR/Instruction.h>
+
+namespace willow {
+
+/// The base class for unary instructions
+class UnaryInst : public Instruction {
+public:
+  UnaryInst(std::string name, Opcode op, Type type, Value *value,
+            std::optional<Location> loc = std::nullopt)
+      : Instruction(std::move(name), op, type, loc) {
+    addOperand(value);
+  }
+  UnaryInst(Opcode op, Type type, Value *value,
+            std::optional<Location> loc = std::nullopt)
+      : Instruction(op, type, loc) {
+    addOperand(value);
+  }
+
+  Value *getValue() { return getOperand(0); }
+  const Value *getValue() const { return getOperand(0); }
+};
+
+/// The base class for binary instructions
+class BinaryInst : public Instruction {
+public:
+  BinaryInst(std::string name, Opcode op, Type type, Value *lhs, Value *rhs,
+             std::optional<Location> loc = std::nullopt)
+      : Instruction(std::move(name), op, type, loc) {
+    addOperand(lhs);
+    addOperand(rhs);
+  }
+
+  Value *getLHS() { return getOperand(0); }
+  const Value *getLHS() const { return getOperand(0); }
+
+  Value *getRHS() { return getOperand(1); }
+  const Value *getRHS() const { return getOperand(1); }
+};
+
+class AddInst : public BinaryInst {
+public:
+  AddInst(std::string name, Type type, Value *lhs, Value *rhs,
+          std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Add, type, lhs, rhs, loc) {}
+};
+
+class MulInst : public BinaryInst {
+public:
+  MulInst(std::string name, Type type, Value *lhs, Value *rhs,
+          std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Mul, type, lhs, rhs, loc) {}
+};
+
+class SubInst : public BinaryInst {
+public:
+  SubInst(std::string name, Type type, Value *lhs, Value *rhs,
+          std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Sub, type, lhs, rhs, loc) {}
+};
+
+class DivInst : public BinaryInst {
+public:
+  DivInst(std::string name, Type type, Value *lhs, Value *rhs,
+          std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Div, type, lhs, rhs, loc) {}
+};
+
+class ModInst : public BinaryInst {
+public:
+  ModInst(std::string name, Type type, Value *lhs, Value *rhs,
+          std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Mod, type, lhs, rhs, loc) {}
+};
+
+class ShlInst : public BinaryInst {
+public:
+  ShlInst(std::string name, Type type, Value *lhs, Value *rhs,
+          std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Shl, type, lhs, rhs, loc) {}
+};
+
+class ShrInst : public BinaryInst {
+public:
+  ShrInst(std::string name, Type type, Value *lhs, Value *rhs,
+          std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Shr, type, lhs, rhs, loc) {}
+};
+
+class AshlInst : public BinaryInst {
+public:
+  AshlInst(std::string name, Type type, Value *lhs, Value *rhs,
+           std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Ashl, type, lhs, rhs, loc) {}
+};
+
+class AshrInst : public BinaryInst {
+public:
+  AshrInst(std::string name, Type type, Value *lhs, Value *rhs,
+           std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Ashr, type, lhs, rhs, loc) {}
+};
+
+class EqInst : public BinaryInst {
+public:
+  EqInst(std::string name, Type type, Value *lhs, Value *rhs,
+         std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Eq, type, lhs, rhs, loc) {}
+};
+
+class LtInst : public BinaryInst {
+public:
+  LtInst(std::string name, Type type, Value *lhs, Value *rhs,
+         std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Lt, type, lhs, rhs, loc) {}
+};
+
+class GtInst : public BinaryInst {
+public:
+  GtInst(std::string name, Type type, Value *lhs, Value *rhs,
+         std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Gt, type, lhs, rhs, loc) {}
+};
+
+class LeInst : public BinaryInst {
+public:
+  LeInst(std::string name, Type type, Value *lhs, Value *rhs,
+         std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Le, type, lhs, rhs, loc) {}
+};
+
+class GeInst : public BinaryInst {
+public:
+  GeInst(std::string name, Type type, Value *lhs, Value *rhs,
+         std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Ge, type, lhs, rhs, loc) {}
+};
+
+class AndInst : public BinaryInst {
+public:
+  AndInst(std::string name, Type type, Value *lhs, Value *rhs,
+          std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::And, type, lhs, rhs, loc) {}
+};
+
+class OrInst : public BinaryInst {
+public:
+  OrInst(std::string name, Type type, Value *lhs, Value *rhs,
+         std::optional<Location> loc = std::nullopt)
+      : BinaryInst(std::move(name), Opcode::Or, type, lhs, rhs, loc) {}
+};
+
+class NotInst : public UnaryInst {
+public:
+  explicit NotInst(std::string name, Type type, Value *value,
+                   std::optional<Location> loc = std::nullopt)
+      : UnaryInst(std::move(name), Opcode::Not, type, value, loc) {}
+};
+
+class JmpInst : public UnaryInst {
+public:
+  JmpInst(Type type, BasicBlock *target,
+          std::optional<Location> loc = std::nullopt)
+      : UnaryInst(Opcode::Jmp, type, static_cast<Value *>(target), loc) {}
+
+  BasicBlock *getTarget() { return static_cast<BasicBlock *>(getValue()); }
+  const BasicBlock *getTarget() const {
+    return static_cast<const BasicBlock *>(getValue());
+  }
+};
+
+class BrInst : public Instruction {
+public:
+  BrInst(Type type, Value *condition, BasicBlock *true_target,
+         BasicBlock *false_target, std::optional<Location> loc = std::nullopt)
+      : Instruction(Opcode::Br, type, loc) {
+    addOperand(condition);
+    addOperand(true_target);
+    addOperand(false_target);
+  }
+
+  Value *getCondition() { return getOperand(0); }
+  const Value *getCondition() const { return getOperand(0); }
+
+  BasicBlock *getTrueTarget() {
+    return static_cast<BasicBlock *>(getOperand(1));
+  }
+  const BasicBlock *getTrueTarget() const {
+    return static_cast<const BasicBlock *>(getOperand(1));
+  }
+
+  BasicBlock *getFalseTarget() {
+    return static_cast<BasicBlock *>(getOperand(2));
+  }
+  const BasicBlock *getFalseTarget() const {
+    return static_cast<const BasicBlock *>(getOperand(2));
+  }
+};
+
+class CallInst : public Instruction {
+public:
+  CallInst(std::string name, Type rty, Function *func,
+           std::initializer_list<Value *> args,
+           std::optional<Location> loc = std::nullopt)
+      : Instruction(std::move(name), Opcode::Call, rty, loc) {
+    addOperand(func);
+    for (auto a : args)
+      addOperand(a);
+  }
+  CallInst(Function *func, Type voidty, std::initializer_list<Value *> args,
+           std::optional<Location> loc = std::nullopt)
+      : Instruction(Opcode::Call, voidty, loc) {
+    addOperand(func);
+    for (auto a : args)
+      addOperand(a);
+  }
+};
+
+class RetInst : public Instruction {
+public:
+  RetInst(Type voidty, std::optional<Location> loc)
+      : Instruction(Opcode::Ret, voidty, loc) {}
+  RetInst(Type voidty, Value *val, std::optional<Location> loc = std::nullopt)
+      : Instruction(Opcode::Ret, voidty, loc) {
+    addOperand(val);
+  }
+};
+
+class PhiInst : public Instruction {
+public:
+  PhiInst(std::string name, Type type,
+          std::initializer_list<std::pair<BasicBlock *, Value *>> args,
+          std::optional<Location> loc)
+      : Instruction(std::move(name), Opcode::Phi, type, loc) {
+    for (auto [bb, v] : args) {
+      addOperand(static_cast<Value *>(bb));
+      addOperand(v);
+    }
+  }
+};
+
+class AllocaInst : public Instruction {
+public:
+  /// \p type The pointer type to allocate.
+  AllocaInst(std::string name, Type type, std::optional<Location> loc)
+      : Instruction(std::move(name), Opcode::Alloca, type, loc) {
+    assert(type.isPtr() && "alloca must return a pointer");
+  }
+};
+
+} // namespace willow
+
+#endif // WILLOW_INCLUDE_IR_INSTRUCTIONS_H
diff --git a/willow/include/willow/IR/TypeContext.h b/willow/include/willow/IR/TypeContext.h
index 3d414b1..665369d 100644
--- a/willow/include/willow/IR/TypeContext.h
+++ b/willow/include/willow/IR/TypeContext.h
@@ -11,7 +11,9 @@ namespace willow {
 /// Context that owns and uniques type instances.
 class TypeContext {
 public:
-  TypeContext() = default;
+  TypeContext()
+      : voidty(std::make_unique<VoidTypeImpl>()),
+        labelty(std::make_unique<LabelTypeImpl>()) {}
   TypeContext(const TypeContext &) = delete;
   TypeContext &operator=(const TypeContext &) = delete;
 
@@ -27,6 +29,13 @@ public:
   /// \return Uniqued void type.
   Type getVoidType();
 
+  /// \return Uniqued label type.
+  Type getLabelType();
+
+  /// \param ret Return type of the function
+  /// \param params Parameter types of the function
+  Type getFunctionType(Type ret, std::initializer_list<Type> params);
+
 private:
   std::unordered_map<IntTypeImpl::Key, std::unique_ptr<IntTypeImpl>,
                      IntTypeImpl::Hash>
@@ -34,7 +43,11 @@ private:
   std::unordered_map<PtrTypeImpl::Key, std::unique_ptr<PtrTypeImpl>,
                      PtrTypeImpl::Hash>
       pcache;
+  std::unordered_map<FunctionTypeImpl::Key, std::unique_ptr<FunctionTypeImpl>,
+                     FunctionTypeImpl::Hash>
+      fncache;
   std::unique_ptr<VoidTypeImpl> voidty;
+  std::unique_ptr<LabelTypeImpl> labelty;
 };
 
 Type TypeContext::getIntType(std::size_t width) {
@@ -53,6 +66,17 @@ Type TypeContext::getPtrType(Type pointee, std::size_t size) {
 
 Type TypeContext::getVoidType() { return Type(voidty.get()); }
 
+Type TypeContext::getLabelType() { return Type{labelty.get()}; }
+
+Type TypeContext::getFunctionType(Type ret,
+                                  std::initializer_list<Type> params) {
+  auto [it, _] =
+      fncache.try_emplace(FunctionTypeImpl::Key{ret, params},
+                          std::make_unique<FunctionTypeImpl>(ret, params));
+
+  return Type(it->second.get());
+};
+
 } // namespace willow
 
 #endif // WILLOW_INCLUDE_IR_TYPE_CONTEXT_H
diff --git a/willow/include/willow/IR/Types.h b/willow/include/willow/IR/Types.h
index 54242ac..886c3d5 100644
--- a/willow/include/willow/IR/Types.h
+++ b/willow/include/willow/IR/Types.h
@@ -5,6 +5,8 @@
 #include <format>
 #include <functional>
 
+#include <willow/Util/Hashing.h>
+
 namespace willow {
 
 /// IDs of all base types.
@@ -26,7 +28,7 @@ class TypeImpl;
 class TypeImpl {
   friend class TypeContext;
   TypeID kind;
-  std::size_t num_bits;
+  std::size_t num_bits = 0;
 
 protected:
   explicit TypeImpl(TypeID kind) : kind{kind} {}
@@ -61,6 +63,7 @@ public:
   bool isInt() const { return kind() == TypeID::Int; }
   bool isPtr() const { return kind() == TypeID::Ptr; }
   bool isVoid() const { return kind() == TypeID::Void; }
+  bool isFunction() const { return kind() == TypeID::Function; }
 };
 
 class IntTypeImpl : public TypeImpl {
@@ -130,6 +133,41 @@ constexpr std::string_view primitiveTypeName(TypeID tid) {
   }
 }
 
+class LabelTypeImpl : public TypeImpl {
+public:
+  LabelTypeImpl() : TypeImpl{TypeID::Label} {}
+};
+
+class FunctionTypeImpl : public TypeImpl {
+  friend class Function;
+  Type rty;
+  std::vector<Type> params;
+
+public:
+  FunctionTypeImpl(Type rty, std::vector<Type> params)
+      : TypeImpl(TypeID::Function), rty(rty), params(std::move(params)) {}
+
+  struct Key {
+    Type ret;
+    std::vector<Type> params;
+    bool operator==(const Key &o) const {
+      return ret == o.ret && params == o.params;
+    }
+  };
+
+  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.params.size());
+      for (const auto &ty : k.params)
+        willow::hashing::combine(seed, ty);
+
+      return seed;
+    }
+  };
+};
+
 }; // namespace willow
 
 template <>
diff --git a/willow/include/willow/IR/Value.h b/willow/include/willow/IR/Value.h
index 7c93728..636fcf4 100644
--- a/willow/include/willow/IR/Value.h
+++ b/willow/include/willow/IR/Value.h
@@ -11,16 +11,19 @@
 namespace willow {
 
 class Instruction;
+class BasicBlock;
 
 enum class ValueKind {
   Instruction, ///< the identified result of an instruction
   Parameter,   ///< the named parameter to a function
   Constant,    ///< an anonymous typed constant
+  BasicBlock,  ///< a basic block
+  Function,    ///< a function signature
 };
 
 /// An SSA value that may be used.
 class Value {
-  ValueKind value_type;
+  ValueKind valuekind;
   std::string name;
   Type type;
 
@@ -30,9 +33,9 @@ class Value {
 public:
   virtual ~Value() = default;
 
-  Value(ValueKind valuetype, std::string name, Type type)
-      : value_type(valuetype), name(std::move(name)), type(type) {}
-  Value(ValueKind valuetype, Type type) : value_type(valuetype), type(type) {}
+  Value(ValueKind valuekind, std::string name, Type type)
+      : valuekind(valuekind), name(std::move(name)), type(type) {}
+  Value(ValueKind valuekind, Type type) : valuekind(valuekind), type(type) {}
 
   bool hasName() const { return !name.empty(); }
 
@@ -40,8 +43,7 @@ public:
   void setName(std::string name) { this->name = std::move(name); }
 
   Type getType() const { return type; }
-  // TODO: less confusing name
-  ValueKind getValueType() const { return value_type; }
+  ValueKind getValueKind() const { return valuekind; }
 
   bool isVoid() const { return type.isVoid(); }
 
diff --git a/willow/include/willow/IR/Verifier.h b/willow/include/willow/IR/Verifier.h
index 9fe1618..cdd1747 100644
--- a/willow/include/willow/IR/Verifier.h
+++ b/willow/include/willow/IR/Verifier.h
@@ -20,8 +20,6 @@ LogicalResult verifyFunction(const Function &, DiagnosticEngine &);
 LogicalResult verifyBasicBlock(const BasicBlock &, DiagnosticEngine &);
 LogicalResult verifyInst(const Instruction &, DiagnosticEngine &);
 
-LogicalResult verifyBinaryInst(const Instruction &, DiagnosticEngine &);
-
 } // namespace willow
 
 #endif // WILLOW_INCLUDE_IR_VERIFIER_H
diff --git a/willow/include/willow/Util/Hashing.h b/willow/include/willow/Util/Hashing.h
new file mode 100644
index 0000000..6268965
--- /dev/null
+++ b/willow/include/willow/Util/Hashing.h
@@ -0,0 +1,33 @@
+#ifndef WILLOW_INCLUDE_UTIL_HASHING_H
+#define WILLOW_INCLUDE_UTIL_HASHING_H
+
+#include <cstddef>
+#include <functional>
+#include <span>
+
+namespace willow::hashing {
+
+inline void combine(std::size_t &seed, std::size_t value) noexcept {
+  constexpr std::size_t k =
+      sizeof(std::size_t) == 8 ? 0x9e3779b97f4a7c15ULL : 0x9e3779b9U;
+  seed ^= value + k + (seed << 6) + (seed >> 2);
+}
+
+template <typename T>
+inline void combine(std::size_t &seed, const T &V) noexcept {
+  combine(seed, std::hash<T>{}(V));
+}
+
+/// Order sensitive collection hashing
+template <class T>
+inline std::size_t hash_range(std::span<const T> xs) noexcept {
+  std::size_t seed = 0;
+  combine(seed, xs.size()); // length
+  for (const auto &x : xs)
+    combine(seed, x);
+  return seed;
+}
+
+} // namespace willow::hashing
+
+#endif // WILLOW_INCLUDE_UTIL_HASHING_H
diff --git a/willow/lib/IR/Instruction.cpp b/willow/lib/IR/Instruction.cpp
index a61cd55..587736d 100644
--- a/willow/lib/IR/Instruction.cpp
+++ b/willow/lib/IR/Instruction.cpp
@@ -1,3 +1,38 @@
 #include <willow/IR/Instruction.h>
 
-namespace willow {};
+namespace willow {
+
+bool Instruction::isTerminatorOp(Opcode op) {
+  using enum Opcode;
+  switch (op) {
+  case Jmp:
+  case Br:
+  case Call:
+  case Ret:
+    return true;
+  case Add:
+  case Mul:
+  case Sub:
+  case Div:
+  case Mod:
+  case Shl:
+  case Shr:
+  case Ashl:
+  case Ashr:
+  case Eq:
+  case Lt:
+  case Gt:
+  case Le:
+  case Ge:
+  case And:
+  case Or:
+  case Not:
+  case Phi:
+  case Alloca:
+    return false;
+  }
+}
+
+Successors Instruction::succs();
+
+}; // namespace willow
diff --git a/willow/lib/IR/Verifier.cpp b/willow/lib/IR/Verifier.cpp
index 459989a..f016bbb 100644
--- a/willow/lib/IR/Verifier.cpp
+++ b/willow/lib/IR/Verifier.cpp
@@ -9,9 +9,12 @@ namespace willow {
 /// Verify that an instruction defines an SSA result
 LogicalResult verifyResult(const Instruction &inst, DiagnosticEngine &diags);
 
+/// Verify that an instruction has the expected number of operands
 LogicalResult verifyNumOperands(const Instruction &inst,
                                 DiagnosticEngine &diags, std::size_t expected);
 
+LogicalResult verifyBinaryInst(const Instruction &, DiagnosticEngine &);
+
 LogicalResult verifyModule(const Module &module, DiagnosticEngine &diags) {
   bool any_failure = false;
 
@@ -43,23 +46,24 @@ LogicalResult verifyModule(const Module &module, DiagnosticEngine &diags) {
 // }
 
 LogicalResult verifyBasicBlock(const BasicBlock &BB, DiagnosticEngine &diags) {
-  bool any_failure = false;
-
   if (BB.empty())
     return emit(diags, Severity::Error, BB.getLoc())
            << "Basic block '" << BB.getName() << "' has an empty body";
 
-  auto *trailer = BB.trailer();
-
-  if (!trailer->isTerminator()) {
-  }
-
   if (!BB.trailer()->isTerminator())
-    // TODO: terminator check
+    return emit(diags, Severity::Error, BB.getLoc())
+           << "Basic block '" << BB.getName()
+           << "' does not end with a terminator";
 
-    for (auto &inst : BB.getBody()) {
-      // verify inst
-    }
+  for (auto &inst : BB.getBody()) {
+    // verify inst
+    if (failed(verifyInst(inst, diags)))
+      return failure();
+
+    if (&inst != BB.trailer() && inst.isTerminator())
+      return emit(diags, Severity::Error, BB.getLoc())
+             << "Illegal terminator in the middle of a block";
+  }
 }
 
 // TODO: better instruction printing
@@ -149,6 +153,9 @@ LogicalResult verifyBinaryInst(const Instruction &inst,
            << "invalid instruction '" << inst << "': "
            << "expected an integral type, got '" << ty << "'";
 
+  if (failed(verifyNumOperands(inst, diags, 2)))
+    return failure();
+
   auto *lhs = inst.getOperand(0);
   auto *rhs = inst.getOperand(1);
 
@@ -177,8 +184,9 @@ LogicalResult verifyNumOperands(const Instruction &inst,
                                 DiagnosticEngine &diags, std::size_t expected) {
   std::size_t num_operands = inst.getNumOperands();
   if (num_operands != expected)
-    return emit(diags, Severity::Error, inst.getLoc()) << std::format(
-               "expected {} operands, but got {}", expected, num_operands);
+    return emit(diags, Severity::Error, inst.getLoc())
+           << std::format("'{}':, expected {} operands, got {}", inst.opcode(),
+                          expected, num_operands);
 
   return success();
 }