[willow]: more cleanup, tests (#12)

24 files changed, 574 insertions, 362 deletions

diff --git a/willow/include/willow/IR/BasicBlock.h b/willow/include/willow/IR/BasicBlock.h
index eb08c5d..7a3a947 100644
--- a/willow/include/willow/IR/BasicBlock.h
+++ b/willow/include/willow/IR/BasicBlock.h
@@ -54,38 +54,12 @@ public:
 
   Instruction *addInstruction(std::unique_ptr<Instruction> inst);
 
-  void push_back(Instruction &inst) {
-    assert(!inst.hasParent() && "Instruction is already parented");
-    body.push_back(inst);
-    inst.setParent(this);
-  }
-
-  void push_front(Instruction &inst) {
-    assert(!inst.hasParent() && "Instruction is already parented");
-    body.push_front(inst);
-    inst.setParent(this);
-  }
-
-  Iterator insert(Iterator pos, Instruction &inst) {
-    assert(!inst.hasParent() && "Instruction is already parented");
-    auto it = body.insert(pos, inst);
-    inst.setParent(this);
-    return it;
-  }
-
-  Iterator erase(Iterator pos) {
-    Instruction &I = *pos;
-    I.setParent(nullptr);
-    return body.erase(pos);
-  }
+  void push_back(Instruction &inst);
+  void push_front(Instruction &inst);
+  Iterator insert(Iterator pos, Instruction &inst);
 
-  Iterator eraseAndDelete(Iterator pos) {
-    Instruction &inst = *pos;
-    pos->setParent(nullptr);
-    auto it = body.erase(pos);
-    delete &inst;
-    return it;
-  }
+  Iterator erase(Iterator pos);
+  Iterator eraseAndDelete(Iterator pos);
 
   std::optional<Location> getLoc() const { return loc; }
 
@@ -94,21 +68,8 @@ public:
     return predecessors;
   }
 
-  void addPred(BasicBlock *bb) {
-    auto [it, inserted] = predecessors.try_emplace(bb, 1);
-
-    if (!inserted)
-      it->second += 1;
-  }
-
-  void delPred(BasicBlock *bb) {
-    auto it = preds().find(bb);
-
-    it->second -= 1;
-
-    if (it->second <= 0)
-      preds().erase(it);
-  }
+  void addPred(BasicBlock *bb);
+  void delPred(BasicBlock *bb);
 };
 
 } // namespace willow
diff --git a/willow/include/willow/IR/Constant.h b/willow/include/willow/IR/Constant.h
index 4e2a3d7..acdc75c 100644
--- a/willow/include/willow/IR/Constant.h
+++ b/willow/include/willow/IR/Constant.h
@@ -1,14 +1,12 @@
 #ifndef WILLOW_INCLUDE_IR_CONSTANT_H
 #define WILLOW_INCLUDE_IR_CONSTANT_H
 
-#include <utility>
 #include <willow/IR/Value.h>
 
 namespace willow {
 
 enum class ConstantKind {
   Int,    //< Integer value with known bits
-  Undef,  //< Known undef
   Poison, //< Known poison
 };
 
@@ -23,7 +21,6 @@ public:
   Constant(const Constant &) = delete;
   Constant &operator=(const Constant &) = delete;
 
-  bool isUndef() const { return kind == ConstantKind::Undef; }
   bool isPoison() const { return kind == ConstantKind::Poison; }
   bool isInt() const { return kind == ConstantKind::Int; }
 };
@@ -34,29 +31,9 @@ class ConstantInt final : public Constant {
   uint64_t bits = 0;
 
 public:
-  explicit ConstantInt(Type ty, uint64_t val)
-      : Constant(ty, ConstantKind::Int) {
-    const size_t w = ty.getNumBits();
-    assert(w <= 64 && "Come back when im less lazy");
-    // assert(!(val >> w) && "Truncated constant");
-
-    if (w == 64)
-      bits = val;
-    else {
-      const uint64_t m = (uint64_t{1} << w) - 1;
-      bits = val & m;
-    }
-  }
-
-  int64_t getSExtVal() const {
-    const size_t w = getType().getNumBits();
-
-    if (w == 64)
-      return static_cast<int64_t>(bits);
-
-    unsigned sh = 64 - w;
-    return (static_cast<int64_t>(bits << sh)) >> sh;
-  }
+  explicit ConstantInt(Type ty, uint64_t val);
+
+  int64_t getSExtVal() const;
 
   uint64_t getZExtVal() const { return bits; }
 
@@ -67,21 +44,10 @@ public:
   };
 
   struct Hash {
-    size_t operator()(const ConstantInt::Key &k) const noexcept {
-      auto h1 = std::hash<TypeImpl *>{}(k.ty);
-      auto h2 = std::hash<uint64_t>{}(k.bits);
-
-      return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2));
-    }
+    size_t operator()(const ConstantInt::Key &k) const noexcept;
   };
 };
 
-/// Represents a constant value that is entirely undef.
-class UndefVal final : public Constant {
-public:
-  explicit UndefVal(Type ty) : Constant(ty, ConstantKind::Undef) {}
-};
-
 /// Represents a constant value that is entirely poison.
 class PoisonVal final : public Constant {
 public:
@@ -90,19 +56,6 @@ 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();
-}
+std::ostream &operator<<(std::ostream &os, const willow::Constant &c);
 
 #endif // WILLOW_INCLUDE_IR_CONSTANT_H
diff --git a/willow/include/willow/IR/ConstantPool.h b/willow/include/willow/IR/ConstantPool.h
index 7d5347b..dd93997 100644
--- a/willow/include/willow/IR/ConstantPool.h
+++ b/willow/include/willow/IR/ConstantPool.h
@@ -1,8 +1,8 @@
 #ifndef WILLOW_INCLUDE_IR_CONSTANT_POOL_H
 #define WILLOW_INCLUDE_IR_CONSTANT_POOL_H
 
-#include <memory>
 #include <willow/IR/Constant.h>
+#include <memory>
 
 namespace willow {
 
@@ -14,8 +14,6 @@ public:
 
   /// Get a uniqued integer constant with the specified type and value.
   ConstantInt *getInt(Type ty, uint64_t val);
-  /// Get a uniqued undef value for the specified type \p ty.
-  UndefVal *getUndefVal(Type ty);
   /// Get a uniqued poison value for the specified type \p ty.
   PoisonVal *getPoisonVal(Type ty);
 
@@ -25,41 +23,10 @@ private:
                      ConstantInt::Hash>
       icache;
 
-  std::mutex undef_mutex;
-  std::unordered_map<TypeImpl *, std::unique_ptr<UndefVal>> ucache;
-
   std::mutex poison_mutex;
   std::unordered_map<TypeImpl *, std::unique_ptr<PoisonVal>> pcache;
 };
 
-inline ConstantInt *ConstantPool::getInt(Type ty, uint64_t val) {
-  assert(ty.isInt() && "Expected integer type");
-  ConstantInt::Key &&k{ty.getImpl(), ty.getNumBits()};
-  std::lock_guard<std::mutex> lock(int_mutex);
-
-  auto [it, _] = icache.try_emplace(k, std::make_unique<ConstantInt>(ty, val));
-
-  return it->second.get();
-}
-
-inline UndefVal *ConstantPool::getUndefVal(Type ty) {
-  std::lock_guard<std::mutex> lock(undef_mutex);
-
-  auto [it, _] =
-      ucache.try_emplace(ty.getImpl(), std::make_unique<UndefVal>(ty));
-
-  return it->second.get();
-}
-
-inline PoisonVal *ConstantPool::getPoisonVal(Type ty) {
-  std::lock_guard<std::mutex> lock(poison_mutex);
-
-  auto [it, _] =
-      pcache.try_emplace(ty.getImpl(), std::make_unique<PoisonVal>(ty));
-
-  return it->second.get();
-}
-
 }; // namespace willow
 
 #endif // WILLOW_INCLUDE_IR_CONSTANT_POOL_H
diff --git a/willow/include/willow/IR/Diagnostic.h b/willow/include/willow/IR/Diagnostic.h
index 538704c..68483d9 100644
--- a/willow/include/willow/IR/Diagnostic.h
+++ b/willow/include/willow/IR/Diagnostic.h
@@ -5,6 +5,7 @@
 
 #include <string>
 #include <vector>
+#include <ostream>
 
 namespace willow {
 
@@ -19,4 +20,6 @@ struct Diagnostic {
 
 } // namespace willow
 
+std::ostream &operator<<(std::ostream &os, const willow::Diagnostic &diagnostic);
+
 #endif // WILLOW_INCLUDE_IR_DIAGNOSTIC_H
diff --git a/willow/include/willow/IR/DiagnosticEngine.h b/willow/include/willow/IR/DiagnosticEngine.h
index a8735af..06dcc3c 100644
--- a/willow/include/willow/IR/DiagnosticEngine.h
+++ b/willow/include/willow/IR/DiagnosticEngine.h
@@ -21,11 +21,7 @@ public:
   explicit DiagnosticEngine(Handler h) : handler(std::move(h)) {}
 
   void setHandler(Handler h) { handler = std::move(h); }
-
-  void report(Diagnostic d) {
-    if (handler)
-      handler(std::move(d));
-  }
+  void report(Diagnostic d);
 
 private:
   Handler handler;
@@ -42,23 +38,11 @@ public:
   DiagnosticBuilder &operator=(const DiagnosticBuilder &) = delete;
 
   DiagnosticBuilder(DiagnosticEngine &eng, Severity severity,
-                    std::optional<Location> loc)
-      : engine(&eng) {
-    diag.severity = severity;
-    diag.location = loc;
-  }
+                    std::optional<Location> loc = std::nullopt);
 
-  DiagnosticBuilder(DiagnosticBuilder &&other) noexcept
-      : engine(std::exchange(other.engine, nullptr)),
-        diag(std::move(other.diag)), os(std::move(other.os)) {}
+  DiagnosticBuilder(DiagnosticBuilder &&other) noexcept;
 
-  ~DiagnosticBuilder() {
-    if (!engine) // was moved from
-      return;
-
-    diag.message += os.str();
-    engine->report(std::move(diag));
-  }
+  ~DiagnosticBuilder();
 
   template <typename T>
   DiagnosticBuilder &operator<<(T &&x) {
diff --git a/willow/include/willow/IR/Function.h b/willow/include/willow/IR/Function.h
index bd6ef3d..817abd2 100644
--- a/willow/include/willow/IR/Function.h
+++ b/willow/include/willow/IR/Function.h
@@ -8,7 +8,6 @@
 #include <memory>
 #include <ranges>
 #include <string>
-#include <string_view>
 #include <utility>
 #include <vector>
 
@@ -83,32 +82,16 @@ public:
 
   std::size_t getNumParams() const { return params.size(); }
 
-  /// \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;
-  }
+  BasicBlock *addBlock(std::unique_ptr<BasicBlock> block);
 
   /// 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();
+    return addBlock(std::make_unique<BasicBlock>(std::forward<Args>(args)...));
   }
 
   Type getReturnType() const {
@@ -119,20 +102,6 @@ public:
   }
 };
 
-inline const BasicBlock *Function::entryBlock() const {
-  if (blocks.empty())
-    return nullptr;
-  else
-    return blocks.front().get();
-}
-
-inline BasicBlock *Function::entryBlock() {
-  if (blocks.empty())
-    return nullptr;
-  else
-    return blocks.front().get();
-}
-
 } // namespace willow
 
 #endif // WILLOW_INCLUDE_IR_FUNCTION_H
diff --git a/willow/include/willow/IR/IRBuilder.h b/willow/include/willow/IR/IRBuilder.h
index f2f36f2..1c637a7 100644
--- a/willow/include/willow/IR/IRBuilder.h
+++ b/willow/include/willow/IR/IRBuilder.h
@@ -21,69 +21,75 @@ public:
                      BasicBlock::Iterator insertion_point)
       : insert_point(insertion_point), ctx(ctx) {}
 
-  void SetInsertPoint(BasicBlock::Iterator point) { insert_point = point; }
+  void setInsertPoint(BasicBlock::Iterator point) { insert_point = point; }
 
-  AddInst *BuildAdd(Type type, Value *lhs, Value *rhs,
+  AddInst *buildAdd(Type type, Value *lhs, Value *rhs,
                     std::optional<Location> loc = std::nullopt);
-  MulInst *BuildMul(Type type, Value *lhs, Value *rhs,
+  MulInst *buildMul(Type type, Value *lhs, Value *rhs,
                     std::optional<Location> loc = std::nullopt);
-  SubInst *BuildSub(Type type, Value *lhs, Value *rhs,
+  SubInst *buildSub(Type type, Value *lhs, Value *rhs,
                     std::optional<Location> loc = std::nullopt);
-  DivInst *BuildDiv(Type type, Value *lhs, Value *rhs,
+  DivInst *buildDiv(Type type, Value *lhs, Value *rhs,
                     std::optional<Location> loc = std::nullopt);
-  ModInst *BuildMod(Type type, Value *lhs, Value *rhs,
+  ModInst *buildMod(Type type, Value *lhs, Value *rhs,
                     std::optional<Location> loc = std::nullopt);
-  ShlInst *BuildShl(Type type, Value *lhs, Value *rhs,
+  ShlInst *buildShl(Type type, Value *lhs, Value *rhs,
                     std::optional<Location> loc = std::nullopt);
-  ShrInst *BuildShr(Type type, Value *lhs, Value *rhs,
+  ShrInst *buildShr(Type type, Value *lhs, Value *rhs,
                     std::optional<Location> loc = std::nullopt);
-  AshlInst *BuildAshl(Type type, Value *lhs, Value *rhs,
+  AshlInst *buildAshl(Type type, Value *lhs, Value *rhs,
                       std::optional<Location> loc = std::nullopt);
-  AshrInst *BuildAshr(Type type, Value *lhs, Value *rhs,
+  AshrInst *buildAshr(Type type, Value *lhs, Value *rhs,
                       std::optional<Location> loc = std::nullopt);
 
-  EqInst *BuildEq(Value *lhs, Value *rhs,
+  EqInst *buildEq(Value *lhs, Value *rhs,
                   std::optional<Location> loc = std::nullopt);
-  LtInst *BuildLt(Value *lhs, Value *rhs,
+  LtInst *buildLt(Value *lhs, Value *rhs,
                   std::optional<Location> loc = std::nullopt);
-  GtInst *BuildGt(Value *lhs, Value *rhs,
+  GtInst *buildGt(Value *lhs, Value *rhs,
                   std::optional<Location> loc = std::nullopt);
-  LeInst *BuildLe(Value *lhs, Value *rhs,
+  LeInst *buildLe(Value *lhs, Value *rhs,
                   std::optional<Location> loc = std::nullopt);
-  GeInst *BuildGe(Value *lhs, Value *rhs,
+  GeInst *buildGe(Value *lhs, Value *rhs,
                   std::optional<Location> loc = std::nullopt);
 
-  AndInst *BuildAnd(Value *lhs, Value *rhs,
+  AndInst *buildAnd(Type type, Value *lhs, Value *rhs,
                     std::optional<Location> loc = std::nullopt);
-  OrInst *BuildOr(Value *lhs, Value *rhs,
+  OrInst *buildOr(Type type, Value *lhs, Value *rhs,
                   std::optional<Location> loc = std::nullopt);
-  NotInst *BuildNot(Value *val, std::optional<Location> loc = std::nullopt);
+  NotInst *buildNot(Type type, Value *val,
+                    std::optional<Location> loc = std::nullopt);
 
-  JmpInst *BuildJmp(BasicBlock *dst,
+  JmpInst *buildJmp(BasicBlock *dst,
                     std::optional<Location> loc = std::nullopt);
-  BrInst *BuildBr(Value *predicate, BasicBlock *truedst, BasicBlock *falsedst,
+  BrInst *buildBr(Value *predicate, BasicBlock *truedst, BasicBlock *falsedst,
                   std::optional<Location> loc = std::nullopt);
   template <typename... Args>
-  CallInst *BuildCall(Type rty, Function *func,
+  CallInst *buildCall(Type rty, Function *func,
                       std::optional<Location> loc = std::nullopt,
-                      Args &&...args) {
-    auto *inst = new CallInst(rty, func, std::forward<Args>(args)...);
-    assert(inst);
-    insert_point->insertAfter(*inst);
-    insert_point++;
+                      Args &&...args);
 
-    return inst;
-  }
-  RetInst *BuildRet(Value *val, std::optional<Location> loc = std::nullopt);
-  RetInst *BuildRet(std::optional<Location> loc = std::nullopt);
+  RetInst *buildRet(Value *val, std::optional<Location> loc = std::nullopt);
+  RetInst *buildRet(std::optional<Location> loc = std::nullopt);
 
   PhiInst *
-  BuildPhi(Type ty,
+  buildPhi(Type ty,
            std::initializer_list<std::pair<BasicBlock *, Value *>> args,
            std::optional<Location> loc = std::nullopt);
-  AllocaInst *BuildAlloca(Type ty, std::optional<Location> loc = std::nullopt);
+  AllocaInst *buildAlloca(Type ty, std::optional<Location> loc = std::nullopt);
 };
 
+template <typename... Args>
+CallInst *IRBuilder::buildCall(Type rty, Function *func,
+                               std::optional<Location> loc, Args &&...args) {
+  auto *inst = new CallInst(rty, func, std::forward<Args>(args)...);
+  assert(inst);
+  insert_point->insertAfter(*inst);
+  insert_point++;
+
+  return inst;
+}
+
 } // namespace willow
 
 #endif // WILLOW_INCLUDE_IR_IR_BUILDER_H*
diff --git a/willow/include/willow/IR/Instruction.h b/willow/include/willow/IR/Instruction.h
index e02e308..34bf584 100644
--- a/willow/include/willow/IR/Instruction.h
+++ b/willow/include/willow/IR/Instruction.h
@@ -83,18 +83,7 @@ private:
   std::vector<Value *> operands;
 
 protected:
-  void setOperand(std::size_t index, Value *operand) {
-    assert(index < operands.size() && "Operand index out of bounds");
-    assert(operand && "Operand cannot be null");
-    Value *old = operands[index];
-    if (old == operand)
-      return;
-
-    old->delUse(this);
-    operands[index] = operand;
-    operand->addUse(this);
-  }
-
+  void setOperand(std::size_t index, Value *operand);
 public:
   /// \param op Opcode for this instruction.
   /// \param type Type of the result of this instruction.
diff --git a/willow/include/willow/IR/Instructions.h b/willow/include/willow/IR/Instructions.h
index 753ea70..fd48b2c 100644
--- a/willow/include/willow/IR/Instructions.h
+++ b/willow/include/willow/IR/Instructions.h
@@ -11,10 +11,7 @@ namespace willow {
 class UnaryInst : public Instruction {
 public:
   UnaryInst(Opcode op, Type type, Value *value,
-            std::optional<Location> loc = std::nullopt)
-      : Instruction(op, type, loc) {
-    addOperand(value);
-  }
+            std::optional<Location> loc = std::nullopt);
 
   Value *getValue() { return getOperand(0); }
   const Value *getValue() const { return getOperand(0); }
@@ -24,11 +21,7 @@ public:
 class BinaryInst : public Instruction {
 public:
   BinaryInst(Opcode op, Type type, Value *lhs, Value *rhs,
-             std::optional<Location> loc = std::nullopt)
-      : Instruction(op, type, loc) {
-    addOperand(lhs);
-    addOperand(rhs);
-  }
+             std::optional<Location> loc = std::nullopt);
 
   Value *getLHS() { return getOperand(0); }
   const Value *getLHS() const { return getOperand(0); }
@@ -248,29 +241,14 @@ public:
   /// \p true_target. The basic block to jump to if the condition is true
   /// \p false_target. The basic block to jump to if the condition is false
   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));
-  }
+         BasicBlock *false_target, std::optional<Location> loc = std::nullopt);
+
+  Value *getCondition();
+  const Value *getCondition() const;
+  BasicBlock *getTrueTarget();
+  const BasicBlock *getTrueTarget() const;
+  BasicBlock *getFalseTarget();
+  const BasicBlock *getFalseTarget() const;
 };
 
 /// Call another function
@@ -292,12 +270,8 @@ public:
 /// Return instruction
 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);
-  }
+  RetInst(Type voidty, std::optional<Location> loc);
+  RetInst(Type voidty, Value *val, std::optional<Location> loc = std::nullopt);
 };
 
 /// Select a control-flow variant value
@@ -307,13 +281,7 @@ public:
   /// \p args List of (predecessor block, value to take) pairs
   PhiInst(Type type,
           std::initializer_list<std::pair<BasicBlock *, Value *>> args,
-          std::optional<Location> loc)
-      : Instruction(Opcode::Phi, type, loc) {
-    for (auto [bb, v] : args) {
-      addOperand(static_cast<Value *>(bb));
-      addOperand(v);
-    }
-  }
+          std::optional<Location> loc = std::nullopt);
 
   auto incomings() {
     auto ops = std::span<Value *>{getOperands()};
diff --git a/willow/include/willow/IR/Value.h b/willow/include/willow/IR/Value.h
index e252fa2..dc98373 100644
--- a/willow/include/willow/IR/Value.h
+++ b/willow/include/willow/IR/Value.h
@@ -3,9 +3,7 @@
 
 #include <willow/IR/Types.h>
 
-#include <cassert>
 #include <unordered_map>
-#include <ostream>
 
 namespace willow {
 
@@ -13,6 +11,8 @@ class Instruction;
 class BasicBlock;
 class Constant;
 
+using UseList = std::unordered_map<Instruction *, std::size_t>;
+
 enum class ValueKind {
   Instruction, ///< the identified result of an instruction
   Parameter,   ///< the named parameter to a function
@@ -43,27 +43,15 @@ public:
 
   /// Get the instructions that use this value, and the number of times they use
   /// it.
-  ///
-  /// \return map of Instruction* -> num uses
-  std::unordered_map<Instruction *, std::size_t> &getUses() { return uses; }
-  const std::unordered_map<Instruction *, std::size_t> &getUses() const {
-    return uses;
-  }
-
-  void addUse(Instruction *i) {
-    auto [it, inserted] = uses.try_emplace(i, 1);
-
-    if (!inserted)
-      it->second += 1;
-  }
-
-  /// Remove a use of the instruction from te use list.
-  void delUse(Instruction *instruction) {
-    assert(uses.contains(instruction) && "No uses to remove");
-    auto it = uses.find(instruction);
-    it->second -= 1;
-    if (it->second == 0)
-      uses.erase(it);
+  UseList &getUses() { return uses; }
+  const UseList &getUses() const { return uses; }
+
+  /// Add the instruction \p i as a user of this value
+  void addUse(Instruction *instruction);
+  /// Remove the instruction \p i as a user of this value
+  void delUse(Instruction *instruction);
+  bool hasUse(Instruction *instruction) const {
+    return uses.contains(instruction);
   }
 };
 
diff --git a/willow/lib/IR/BasicBlock.cpp b/willow/lib/IR/BasicBlock.cpp
new file mode 100644
index 0000000..ceb4653
--- /dev/null
+++ b/willow/lib/IR/BasicBlock.cpp
@@ -0,0 +1,54 @@
+#include <willow/IR/BasicBlock.h>
+
+namespace willow {
+
+void BasicBlock::push_back(Instruction &inst) {
+  assert(!inst.hasParent() && "Instruction is already parented");
+  body.push_back(inst);
+  inst.setParent(this);
+}
+
+void BasicBlock::push_front(Instruction &inst) {
+  assert(!inst.hasParent() && "Instruction is already parented");
+  body.push_front(inst);
+  inst.setParent(this);
+}
+
+BasicBlock::Iterator BasicBlock::insert(Iterator pos, Instruction &inst) {
+  assert(!inst.hasParent() && "Instruction is already parented");
+  auto it = body.insert(pos, inst);
+  inst.setParent(this);
+  return it;
+}
+
+BasicBlock::Iterator BasicBlock::erase(BasicBlock::Iterator pos) {
+  Instruction &I = *pos;
+  I.setParent(nullptr);
+  return body.erase(pos);
+}
+
+BasicBlock::Iterator BasicBlock::eraseAndDelete(BasicBlock::Iterator pos) {
+  Instruction &inst = *pos;
+  pos->setParent(nullptr);
+  auto it = body.erase(pos);
+  delete &inst;
+  return it;
+}
+
+void BasicBlock::addPred(BasicBlock *bb) {
+  auto [it, inserted] = predecessors.try_emplace(bb, 1);
+
+  if (!inserted)
+    it->second += 1;
+}
+
+void BasicBlock::delPred(BasicBlock *bb) {
+  auto it = preds().find(bb);
+
+  it->second -= 1;
+
+  if (it->second <= 0)
+    preds().erase(it);
+}
+
+} // namespace willow
diff --git a/willow/lib/IR/Constant.cpp b/willow/lib/IR/Constant.cpp
new file mode 100644
index 0000000..b9c15c7
--- /dev/null
+++ b/willow/lib/IR/Constant.cpp
@@ -0,0 +1,53 @@
+#include <willow/IR/Constant.h>
+#include <utility>
+#include <cassert>
+#include <ostream>
+
+namespace willow {
+
+ConstantInt::ConstantInt(Type ty, uint64_t val)
+    : Constant(ty, ConstantKind::Int) {
+  const size_t w = ty.getNumBits();
+  assert(w <= 64 && "Come back when im less lazy");
+  // assert(!(val >> w) && "Truncated constant");
+
+  if (w == 64)
+    bits = val;
+  else {
+    const uint64_t m = (uint64_t{1} << w) - 1;
+    bits = val & m;
+  }
+}
+
+int64_t ConstantInt::getSExtVal() const {
+  const size_t w = getType().getNumBits();
+
+  if (w == 64)
+    return static_cast<int64_t>(bits);
+
+  unsigned sh = 64 - w;
+  return (static_cast<int64_t>(bits << sh)) >> sh;
+}
+
+size_t ConstantInt::Hash::operator()(const ConstantInt::Key &k) const noexcept {
+  auto h1 = std::hash<TypeImpl *>{}(k.ty);
+  auto h2 = std::hash<uint64_t>{}(k.bits);
+
+  return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2));
+}
+
+} // namespace willow
+
+// TODO
+std::ostream &operator<<(std::ostream &os, const willow::Constant &c) {
+  if (c.isPoison())
+    return os << "poison";
+
+  if (c.isInt()) {
+    return os << static_cast<const willow::ConstantInt *>(&c)->getSExtVal();
+  }
+
+  std::unreachable();
+
+  return os;
+}
diff --git a/willow/lib/IR/ConstantPool.cpp b/willow/lib/IR/ConstantPool.cpp
new file mode 100644
index 0000000..d880913
--- /dev/null
+++ b/willow/lib/IR/ConstantPool.cpp
@@ -0,0 +1,26 @@
+#include <willow/IR/ConstantPool.h>
+
+#include <cassert>
+
+namespace willow {
+
+ConstantInt *ConstantPool::getInt(Type ty, uint64_t val) {
+  assert(ty.isInt() && "Expected integer type");
+  ConstantInt::Key &&k{ty.getImpl(), ty.getNumBits()};
+  std::lock_guard<std::mutex> lock(int_mutex);
+
+  auto [it, _] = icache.try_emplace(k, std::make_unique<ConstantInt>(ty, val));
+
+  return it->second.get();
+}
+
+PoisonVal *ConstantPool::getPoisonVal(Type ty) {
+  std::lock_guard<std::mutex> lock(poison_mutex);
+
+  auto [it, _] =
+      pcache.try_emplace(ty.getImpl(), std::make_unique<PoisonVal>(ty));
+
+  return it->second.get();
+}
+
+}
diff --git a/willow/lib/IR/Diagnostic.cpp b/willow/lib/IR/Diagnostic.cpp
new file mode 100644
index 0000000..0e2c8bd
--- /dev/null
+++ b/willow/lib/IR/Diagnostic.cpp
@@ -0,0 +1,10 @@
+#include <willow/IR/Diagnostic.h>
+#include <ostream>
+
+//TODO
+std::ostream &operator<<(std::ostream &os, const willow::Diagnostic &diagnostic) {
+  if (diagnostic.location)
+    return os << diagnostic.location.value() << ": " << diagnostic.message;
+  else 
+    return os << "<unknown>: " << diagnostic.message;
+}
diff --git a/willow/lib/IR/DiagnosticEngine.cpp b/willow/lib/IR/DiagnosticEngine.cpp
new file mode 100644
index 0000000..f0cc280
--- /dev/null
+++ b/willow/lib/IR/DiagnosticEngine.cpp
@@ -0,0 +1,28 @@
+#include <willow/IR/DiagnosticEngine.h>
+
+namespace willow {
+
+void DiagnosticEngine::report(Diagnostic d) {
+  if (handler)
+    handler(std::move(d));
+}
+
+DiagnosticBuilder::DiagnosticBuilder(DiagnosticBuilder &&other) noexcept
+    : engine(std::exchange(other.engine, nullptr)), diag(std::move(other.diag)),
+      os(std::move(other.os)) {}
+DiagnosticBuilder::~DiagnosticBuilder() {
+  if (!engine) // was moved from
+    return;
+
+  diag.message += os.str();
+  engine->report(std::move(diag));
+}
+
+DiagnosticBuilder::DiagnosticBuilder(DiagnosticEngine &eng, Severity severity,
+                                     std::optional<Location> loc)
+    : engine(&eng) {
+  diag.severity = severity;
+  diag.location = loc;
+}
+
+} // namespace willow
diff --git a/willow/lib/IR/Function.cpp b/willow/lib/IR/Function.cpp
new file mode 100644
index 0000000..500d917
--- /dev/null
+++ b/willow/lib/IR/Function.cpp
@@ -0,0 +1,26 @@
+#include <willow/IR/Function.h>
+
+namespace willow {
+
+BasicBlock *Function::addBlock(std::unique_ptr<BasicBlock> block) {
+  auto p = block.get();
+  blocks.push_back(std::move(block));
+  p->setParent(this);
+  return p;
+}
+
+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
diff --git a/willow/lib/IR/IRBuilder.cpp b/willow/lib/IR/IRBuilder.cpp
index 62e7a98..ab62082 100644
--- a/willow/lib/IR/IRBuilder.cpp
+++ b/willow/lib/IR/IRBuilder.cpp
@@ -2,7 +2,7 @@
 
 namespace willow {
 
-AddInst *IRBuilder::BuildAdd(Type type, Value *lhs, Value *rhs,
+AddInst *IRBuilder::buildAdd(Type type, Value *lhs, Value *rhs,
                              std::optional<Location> loc) {
   auto *inst = new AddInst{type, lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -11,7 +11,7 @@ AddInst *IRBuilder::BuildAdd(Type type, Value *lhs, Value *rhs,
   return inst;
 }
 
-MulInst *IRBuilder::BuildMul(Type type, Value *lhs, Value *rhs,
+MulInst *IRBuilder::buildMul(Type type, Value *lhs, Value *rhs,
                              std::optional<Location> loc) {
   auto *inst = new MulInst{type, lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -20,7 +20,7 @@ MulInst *IRBuilder::BuildMul(Type type, Value *lhs, Value *rhs,
   return inst;
 }
 
-SubInst *IRBuilder::BuildSub(Type type, Value *lhs, Value *rhs,
+SubInst *IRBuilder::buildSub(Type type, Value *lhs, Value *rhs,
                              std::optional<Location> loc) {
   auto *inst = new SubInst{type, lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -29,7 +29,7 @@ SubInst *IRBuilder::BuildSub(Type type, Value *lhs, Value *rhs,
   return inst;
 }
 
-DivInst *IRBuilder::BuildDiv(Type type, Value *lhs, Value *rhs,
+DivInst *IRBuilder::buildDiv(Type type, Value *lhs, Value *rhs,
                              std::optional<Location> loc) {
   auto *inst = new DivInst{type, lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -38,7 +38,7 @@ DivInst *IRBuilder::BuildDiv(Type type, Value *lhs, Value *rhs,
   return inst;
 }
 
-ModInst *IRBuilder::BuildMod(Type type, Value *lhs, Value *rhs,
+ModInst *IRBuilder::buildMod(Type type, Value *lhs, Value *rhs,
                              std::optional<Location> loc) {
   auto *inst = new ModInst{type, lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -47,7 +47,7 @@ ModInst *IRBuilder::BuildMod(Type type, Value *lhs, Value *rhs,
   return inst;
 }
 
-ShlInst *IRBuilder::BuildShl(Type type, Value *lhs, Value *rhs,
+ShlInst *IRBuilder::buildShl(Type type, Value *lhs, Value *rhs,
                              std::optional<Location> loc) {
   auto *inst = new ShlInst{type, lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -56,7 +56,7 @@ ShlInst *IRBuilder::BuildShl(Type type, Value *lhs, Value *rhs,
   return inst;
 }
 
-ShrInst *IRBuilder::BuildShr(Type type, Value *lhs, Value *rhs,
+ShrInst *IRBuilder::buildShr(Type type, Value *lhs, Value *rhs,
                              std::optional<Location> loc) {
   auto *inst = new ShrInst{type, lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -65,7 +65,7 @@ ShrInst *IRBuilder::BuildShr(Type type, Value *lhs, Value *rhs,
   return inst;
 }
 
-AshlInst *IRBuilder::BuildAshl(Type type, Value *lhs, Value *rhs,
+AshlInst *IRBuilder::buildAshl(Type type, Value *lhs, Value *rhs,
                                std::optional<Location> loc) {
   auto *inst = new AshlInst{type, lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -74,7 +74,7 @@ AshlInst *IRBuilder::BuildAshl(Type type, Value *lhs, Value *rhs,
   return inst;
 }
 
-AshrInst *IRBuilder::BuildAshr(Type type, Value *lhs, Value *rhs,
+AshrInst *IRBuilder::buildAshr(Type type, Value *lhs, Value *rhs,
                                std::optional<Location> loc) {
   auto *inst = new AshrInst{type, lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -83,7 +83,7 @@ AshrInst *IRBuilder::BuildAshr(Type type, Value *lhs, Value *rhs,
   return inst;
 }
 
-EqInst *IRBuilder::BuildEq(Value *lhs, Value *rhs,
+EqInst *IRBuilder::buildEq(Value *lhs, Value *rhs,
                            std::optional<Location> loc) {
   auto *inst = new EqInst{ctx.types().IntType(1), lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -92,7 +92,7 @@ EqInst *IRBuilder::BuildEq(Value *lhs, Value *rhs,
   return inst;
 }
 
-LtInst *IRBuilder::BuildLt(Value *lhs, Value *rhs,
+LtInst *IRBuilder::buildLt(Value *lhs, Value *rhs,
                            std::optional<Location> loc) {
   auto *inst = new LtInst{ctx.types().IntType(1), lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -101,7 +101,7 @@ LtInst *IRBuilder::BuildLt(Value *lhs, Value *rhs,
   return inst;
 }
 
-GtInst *IRBuilder::BuildGt(Value *lhs, Value *rhs,
+GtInst *IRBuilder::buildGt(Value *lhs, Value *rhs,
                            std::optional<Location> loc) {
   auto *inst = new GtInst{ctx.types().IntType(1), lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -110,7 +110,7 @@ GtInst *IRBuilder::BuildGt(Value *lhs, Value *rhs,
   return inst;
 }
 
-LeInst *IRBuilder::BuildLe(Value *lhs, Value *rhs,
+LeInst *IRBuilder::buildLe(Value *lhs, Value *rhs,
                            std::optional<Location> loc) {
   auto *inst = new LeInst{ctx.types().IntType(1), lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -119,7 +119,7 @@ LeInst *IRBuilder::BuildLe(Value *lhs, Value *rhs,
   return inst;
 }
 
-GeInst *IRBuilder::BuildGe(Value *lhs, Value *rhs,
+GeInst *IRBuilder::buildGe(Value *lhs, Value *rhs,
                            std::optional<Location> loc) {
   auto *inst = new GeInst{ctx.types().IntType(1), lhs, rhs, loc};
   insert_point->insertAfter(*inst);
@@ -128,33 +128,33 @@ GeInst *IRBuilder::BuildGe(Value *lhs, Value *rhs,
   return inst;
 }
 
-AndInst *IRBuilder::BuildAnd(Value *lhs, Value *rhs,
+AndInst *IRBuilder::buildAnd(Type type, Value *lhs, Value *rhs,
                              std::optional<Location> loc) {
-  auto *inst = new AndInst{ctx.types().IntType(1), lhs, rhs, loc};
+  auto *inst = new AndInst{type, lhs, rhs, loc};
   insert_point->insertAfter(*inst);
   insert_point++;
 
   return inst;
 }
 
-OrInst *IRBuilder::BuildOr(Value *lhs, Value *rhs,
+OrInst *IRBuilder::buildOr(Type type, Value *lhs, Value *rhs,
                            std::optional<Location> loc) {
-  auto *inst = new OrInst{ctx.types().IntType(1), lhs, rhs, loc};
+  auto *inst = new OrInst{type, lhs, rhs, loc};
   insert_point->insertAfter(*inst);
   insert_point++;
 
   return inst;
 }
 
-NotInst *IRBuilder::BuildNot(Value *val, std::optional<Location> loc) {
-  auto *inst = new NotInst{ctx.types().IntType(1), val, loc};
+NotInst *IRBuilder::buildNot(Type type, Value *val, std::optional<Location> loc) {
+  auto *inst = new NotInst{type, val, loc};
   insert_point->insertAfter(*inst);
   insert_point++;
 
   return inst;
 }
 
-JmpInst *IRBuilder::BuildJmp(BasicBlock *dst, std::optional<Location> loc) {
+JmpInst *IRBuilder::buildJmp(BasicBlock *dst, std::optional<Location> loc) {
 
   auto *inst = new JmpInst{ctx.types().VoidType(), dst, loc};
   insert_point->insertAfter(*inst);
@@ -163,7 +163,7 @@ JmpInst *IRBuilder::BuildJmp(BasicBlock *dst, std::optional<Location> loc) {
   return inst;
 }
 
-BrInst *IRBuilder::BuildBr(Value *predicate, BasicBlock *truedst,
+BrInst *IRBuilder::buildBr(Value *predicate, BasicBlock *truedst,
                            BasicBlock *falsedst, std::optional<Location> loc) {
   auto *inst =
       new BrInst{ctx.types().VoidType(), predicate, truedst, falsedst, loc};
@@ -173,14 +173,14 @@ BrInst *IRBuilder::BuildBr(Value *predicate, BasicBlock *truedst,
   return inst;
 }
 
-RetInst *IRBuilder::BuildRet(Value *val, std::optional<Location> loc) {
+RetInst *IRBuilder::buildRet(Value *val, std::optional<Location> loc) {
   auto *inst = new RetInst{ctx.types().VoidType(), val, loc};
   insert_point->insertAfter(*inst);
   insert_point++;
 
   return inst;
 }
-RetInst *IRBuilder::BuildRet(std::optional<Location> loc) {
+RetInst *IRBuilder::buildRet(std::optional<Location> loc) {
   auto *inst = new RetInst{ctx.types().VoidType(), loc};
   insert_point->insertAfter(*inst);
   insert_point++;
@@ -188,7 +188,7 @@ RetInst *IRBuilder::BuildRet(std::optional<Location> loc) {
   return inst;
 }
 
-PhiInst *IRBuilder::BuildPhi(
+PhiInst *IRBuilder::buildPhi(
     Type ty, std::initializer_list<std::pair<BasicBlock *, Value *>> args,
     std::optional<Location> loc) {
   auto *inst = new PhiInst(ty, args, loc);
@@ -198,7 +198,7 @@ PhiInst *IRBuilder::BuildPhi(
   return inst;
 }
 
-AllocaInst *IRBuilder::BuildAlloca(Type ty, std::optional<Location> loc) {
+AllocaInst *IRBuilder::buildAlloca(Type ty, std::optional<Location> loc) {
   Type pty = ctx.types().PtrType(ty);
   auto *inst = new AllocaInst(pty, loc);
   insert_point->insertAfter(*inst);
diff --git a/willow/lib/IR/Instruction.cpp b/willow/lib/IR/Instruction.cpp
index a6e0c9b..517b6f9 100644
--- a/willow/lib/IR/Instruction.cpp
+++ b/willow/lib/IR/Instruction.cpp
@@ -34,6 +34,18 @@ bool Instruction::isTerminatorOp(Opcode op) {
   }
 }
 
+void Instruction::setOperand(std::size_t index, Value *operand) {
+  assert(index < operands.size() && "Operand index out of bounds");
+  assert(operand && "Operand cannot be null");
+  Value *old = operands[index];
+  if (old == operand)
+    return;
+
+  old->delUse(this);
+  operands[index] = operand;
+  operand->addUse(this);
+}
+
 Successors Instruction::succs() {
   using enum Opcode;
   switch (op) {
diff --git a/willow/lib/IR/Instructions.cpp b/willow/lib/IR/Instructions.cpp
new file mode 100644
index 0000000..15e6786
--- /dev/null
+++ b/willow/lib/IR/Instructions.cpp
@@ -0,0 +1,64 @@
+#include <willow/IR/Instructions.h>
+
+namespace willow {
+
+UnaryInst::UnaryInst(Opcode op, Type type, Value *value,
+                     std::optional<Location> loc)
+    : Instruction(op, type, loc) {
+  addOperand(value);
+}
+
+BinaryInst::BinaryInst(Opcode op, Type type, Value *lhs, Value *rhs,
+                       std::optional<Location> loc)
+    : Instruction(op, type, loc) {
+  addOperand(lhs);
+  addOperand(rhs);
+}
+
+BrInst::BrInst(Type type, Value *condition, BasicBlock *true_target,
+               BasicBlock *false_target, std::optional<Location> loc)
+    : Instruction(Opcode::Br, type, loc) {
+  addOperand(condition);
+  addOperand(true_target);
+  addOperand(false_target);
+}
+
+Value *BrInst::getCondition() { return getOperand(0); }
+
+const Value *BrInst::getCondition() const { return getOperand(0); }
+
+BasicBlock *BrInst::getTrueTarget() {
+  return static_cast<BasicBlock *>(getOperand(1));
+}
+
+const BasicBlock *BrInst::getTrueTarget() const {
+  return static_cast<const BasicBlock *>(getOperand(1));
+}
+
+BasicBlock *BrInst::getFalseTarget() {
+  return static_cast<BasicBlock *>(getOperand(2));
+}
+
+const BasicBlock *BrInst::getFalseTarget() const {
+  return static_cast<const BasicBlock *>(getOperand(2));
+}
+
+RetInst::RetInst(Type voidty, std::optional<Location> loc)
+    : Instruction(Opcode::Ret, voidty, loc) {}
+
+RetInst::RetInst(Type voidty, Value *val, std::optional<Location> loc)
+    : Instruction(Opcode::Ret, voidty, loc) {
+  addOperand(val);
+}
+
+PhiInst::PhiInst(Type type,
+                 std::initializer_list<std::pair<BasicBlock *, Value *>> args,
+                 std::optional<Location> loc)
+    : Instruction(Opcode::Phi, type, loc) {
+  for (auto [bb, v] : args) {
+    addOperand(static_cast<Value *>(bb));
+    addOperand(v);
+  }
+}
+
+} // namespace willow
diff --git a/willow/lib/IR/Value.cpp b/willow/lib/IR/Value.cpp
index 0bd1079..703e807 100644
--- a/willow/lib/IR/Value.cpp
+++ b/willow/lib/IR/Value.cpp
@@ -1,27 +1,23 @@
-// #include <willow/IR/Value.h>
-// #include <willow/IR/Constant.h>
-// #include <ostream>
-//
-// std::ostream &operator<<(std::ostream &os, const willow::Value &v) {
-//   using willow::ValueKind;
-//   auto ty = v.getType();
-//   if (!v.isVoid())
-//     os << ty << " ";
-//
-//   switch (v.getValueKind()) {
-//   case ValueKind::Parameter:
-//     [[fallthrough]];
-//   case ValueKind::Instruction: {
-//     return os << "%" << v.getName();
-//   }
-//   case ValueKind::BasicBlock: {
-//     return os << "^" << v.getName();
-//   }
-//   case ValueKind::Function: {
-//     return os << "@" << v.getName();
-//   }
-//   case ValueKind::Constant: {
-//     return os << *static_cast<const willow::Constant*>(&v);
-//   }
-//   }
-// }
+#include <willow/IR/Constant.h>
+#include <willow/IR/Value.h>
+
+#include <cassert>
+
+namespace willow {
+
+void Value::addUse(Instruction *instruction) {
+  auto [it, inserted] = uses.try_emplace(instruction, 1);
+
+  if (!inserted)
+    it->second += 1;
+}
+
+void Value::delUse(Instruction *instruction) {
+  assert(uses.contains(instruction) && "No uses to remove");
+  auto it = uses.find(instruction);
+  it->second -= 1;
+  if (it->second == 0)
+    uses.erase(it);
+}
+
+} // namespace willow
diff --git a/willow/lib/IR/Verifier.cpp b/willow/lib/IR/Verifier.cpp
index b622f10..125f7bc 100644
--- a/willow/lib/IR/Verifier.cpp
+++ b/willow/lib/IR/Verifier.cpp
@@ -8,6 +8,7 @@
 
 namespace willow {
 
+namespace {
 /// Verify that an instruction defines an SSA result
 LogicalResult verifyResult(const Instruction &inst, DiagnosticEngine &diags);
 /// Verify that an instruction does not define an ssa result
@@ -18,9 +19,9 @@ LogicalResult verifyNumOperands(const Instruction &inst,
                                 DiagnosticEngine &diags, std::size_t expected);
 
 /// Verify operand type
-LogicalResult expectOperandType(const Instruction &inst,
-                                DiagnosticEngine &diags, std::size_t opidx,
-                                Type expected);
+// LogicalResult expectOperandType(const Instruction &inst,
+//                                 DiagnosticEngine &diags, std::size_t opidx,
+//                                 Type expected);
 LogicalResult expectOperandType(const Instruction &inst,
                                 DiagnosticEngine &diags, const Value *operand,
                                 Type expected);
@@ -31,6 +32,7 @@ LogicalResult expectResultType(const Instruction &inst, DiagnosticEngine &diags,
 LogicalResult verifyBinaryIntegerInst(const Instruction &, DiagnosticEngine &);
 LogicalResult verifyBinaryIntegerCmp(WillowContext &ctx, const Instruction &,
                                      DiagnosticEngine &);
+}
 
 LogicalResult verifyModule(WillowContext &ctx, const Module &module,
                            DiagnosticEngine &diags) {
@@ -282,6 +284,7 @@ LogicalResult verifyInst(WillowContext &ctx, const Instruction &inst,
   return success();
 }
 
+namespace {
 LogicalResult verifyBinaryIntegerInst(const Instruction &inst,
                                       DiagnosticEngine &diags) {
   Type ty = inst.getType();
@@ -402,5 +405,6 @@ LogicalResult expectResultType(const Instruction &inst, DiagnosticEngine &diags,
   return emit(diags, Severity::Error) << std::format(
              "unexpected result type: expected '{}', found '{}'", expected, ty);
 }
+}
 
 } // namespace willow
diff --git a/willow/unittest/IR/BUILD.bazel b/willow/unittest/IR/BUILD.bazel
index b41dfcd..e25efbf 100644
--- a/willow/unittest/IR/BUILD.bazel
+++ b/willow/unittest/IR/BUILD.bazel
@@ -8,9 +8,20 @@ cc_test(
   tags = ["ir"]
 )
 
+cc_test(
+  name = "instructions",
+  srcs = ["InstructionsTest.cpp"],
+  deps = [
+    "//willow",
+    "@catch2//:catch2_main"
+  ],
+  tags = ["ir"]
+)
+
 test_suite(
   name = "ir_tests",
   tests = [
-    ":verifier"
+    ":verifier",
+    ":instructions"
   ],
 )
diff --git a/willow/unittest/IR/InstructionsTest.cpp b/willow/unittest/IR/InstructionsTest.cpp
new file mode 100644
index 0000000..acb83a1
--- /dev/null
+++ b/willow/unittest/IR/InstructionsTest.cpp
@@ -0,0 +1,141 @@
+#include <catch2/catch_test_macros.hpp>
+
+#include <willow/IR/Context.h>
+#include <willow/IR/Diagnostic.h>
+#include <willow/IR/DiagnosticEngine.h>
+#include <willow/IR/IRBuilder.h>
+#include <willow/IR/Instructions.h>
+#include <willow/IR/Verifier.h>
+
+#include <iostream>
+
+using namespace willow;
+
+TEST_CASE("valid arithmetic instructions") {
+  WillowContext ctx;
+  DiagnosticEngine eng;
+  TypeContext &types = ctx.types();
+  ConstantPool &consts = ctx.constants();
+
+  Type i64Ty = types.IntType(64);
+  Type i34Ty = types.IntType(34);
+  Type voidTy = types.VoidType();
+  Type voidFnTy = types.FunctionType(voidTy, {});
+
+  Value *one64 = consts.getInt(i64Ty, 1);
+  Value *two64 = consts.getInt(i64Ty, 2);
+  Value *twelve34 = consts.getInt(i34Ty, 12);
+
+  Module *m = ctx.addModule("testmod");
+
+  Function *fn = m->emplaceFunction("fn", m, voidFnTy);
+
+  eng.setHandler([](const Diagnostic& d) { std::cout << d << "\n"; });
+
+  BasicBlock *bb =
+      fn->addBlock(std::make_unique<BasicBlock>(fn, types.BasicBlockType()));
+  IRBuilder builder{ctx, *bb, bb->begin()};
+
+  SECTION("Valid add instruction") {
+    auto &inst = *builder.buildAdd(i64Ty, one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Add);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid mul instruction") {
+    auto &inst = *builder.buildMul(i34Ty, twelve34, twelve34);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Mul);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid sub instruction") {
+    auto &inst = *builder.buildSub(i64Ty, one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Sub);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid div instruction") {
+    auto &inst = *builder.buildDiv(i64Ty, one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Div);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid mod instruction") {
+    auto &inst = *builder.buildMod(i64Ty, one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Mod);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid shl instruction") {
+    auto &inst = *builder.buildShl(i64Ty, one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Shl);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid shr instruction") {
+    auto &inst = *builder.buildShr(i64Ty, one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Shr);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid ashl instruction") {
+    auto &inst = *builder.buildAshl(i64Ty, one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Ashl);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid ashr instruction") {
+    auto &inst = *builder.buildAshr(i64Ty, one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Ashr);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid and instruction") {
+    auto &inst = *builder.buildAnd(i64Ty, one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::And);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid not instruction") {
+    auto &inst = *builder.buildNot(i34Ty, twelve34);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Not);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid or instruction") {
+    auto &inst = *builder.buildOr(i64Ty, one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Or);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid eq Instruction") {
+    auto &inst = *builder.buildEq(one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Eq);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid lt Instruction") {
+    auto &inst = *builder.buildEq(one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Eq);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid gt instruction") {
+    auto &inst = *builder.buildGt(one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Gt);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid le instruction") {
+    auto &inst = *builder.buildLe(one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Le);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+  SECTION("Valid ge instruction") {
+    auto &inst = *builder.buildGe(one64, two64);
+    REQUIRE(inst.opcode() == Instruction::Opcode::Ge);
+    REQUIRE(succeeded(verifyInst(ctx, inst, eng)));
+  }
+
+}
diff --git a/willow/unittest/IR/VerifierTest.cpp b/willow/unittest/IR/VerifierTest.cpp
index efe34db..1b71eb8 100644
--- a/willow/unittest/IR/VerifierTest.cpp
+++ b/willow/unittest/IR/VerifierTest.cpp
@@ -38,8 +38,7 @@ TEST_CASE("valid function", "[verifier]") {
 
 TEST_CASE("invalid basic block", "[verifier]") {
   WillowContext ctx;
-  std::vector<Diagnostic> diags;
-  DiagnosticEngine eng([&](Diagnostic d) { diags.push_back(std::move(d)); });
+  DiagnosticEngine eng;
 
   Type i64Ty = ctx.types().IntType(64);
   Type voidTy = ctx.types().VoidType();
@@ -60,22 +59,22 @@ TEST_CASE("invalid basic block", "[verifier]") {
   }
 
   SECTION("Basic block with no terminator") {
-    builder.BuildAdd(i64Ty, one, one);
+    builder.buildAdd(i64Ty, one, one);
     REQUIRE(failed(verifyBasicBlock(ctx, *bb, eng)));
   }
 
   SECTION("Teminator must be the last instruction in a basic block") {
-    builder.BuildCall(i64Ty, &fn2);
-    builder.BuildAdd(i64Ty, one, one);
+    builder.buildCall(i64Ty, &fn2);
+    builder.buildAdd(i64Ty, one, one);
     REQUIRE(failed(verifyBasicBlock(ctx, *bb, eng)));
   }
 
   SECTION("Basic block with invalid instruction") {
     auto *bb2 = fn.addBlock(
         std::make_unique<BasicBlock>(&fn, ctx.types().BasicBlockType()));
-    builder.SetInsertPoint(bb2->end());
-    builder.BuildAdd(voidTy, one, one);
-    builder.BuildRet();
+    builder.setInsertPoint(bb2->end());
+    builder.buildAdd(voidTy, one, one);
+    builder.buildRet();
 
     REQUIRE(failed(verifyBasicBlock(ctx, *bb, eng)));
   }