[willow]: verifier work (#3)

16 files changed, 504 insertions, 116 deletions

diff --git a/willow/include/willow/IR/BasicBlock.h b/willow/include/willow/IR/BasicBlock.h
index 03d4fb8..dde432a 100644
--- a/willow/include/willow/IR/BasicBlock.h
+++ b/willow/include/willow/IR/BasicBlock.h
@@ -1,7 +1,8 @@
-#ifndef WILLOW_IR_BASIC_BLOCK_H
-#define WILLOW_IR_BASIC_BLOCK_H
+#ifndef WILLOW_INCLUDE_IR_BASIC_BLOCK_H
+#define WILLOW_INCLUDE_IR_BASIC_BLOCK_H
 
 #include <willow/IR/Instruction.h>
+#include <willow/IR/Location.h>
 
 #include <list>
 #include <memory>
@@ -20,6 +21,8 @@ class BasicBlock {
   std::string name;
   Function *parent = nullptr;
 
+  std::optional<Location> loc;
+
   std::list<std::unique_ptr<Instruction>> body;
 
   std::vector<BasicBlock *> preds;
@@ -53,6 +56,8 @@ public:
 
   Instruction *trailer();
   Instruction *leader();
+  const Instruction *trailer() const;
+  const Instruction *leader() const;
 
   Instruction *addInstruction(std::unique_ptr<Instruction> inst);
 
@@ -69,6 +74,8 @@ public:
   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
@@ -97,4 +104,4 @@ Instruction *BasicBlock::addInstruction(std::unique_ptr<Instruction> inst) {
 
 } // namespace willow
 
-#endif // WILLOW_IR_BASIC_BLOCK_H
+#endif // WILLOW_INCLUDE_IR_BASIC_BLOCK_H
diff --git a/willow/include/willow/IR/Context.h b/willow/include/willow/IR/Context.h
index 3468e8f..4f787ef 100644
--- a/willow/include/willow/IR/Context.h
+++ b/willow/include/willow/IR/Context.h
@@ -1,5 +1,5 @@
-#ifndef WILLOW_INCLUDE_CONTEXT_H
-#define WILLOW_INCLUDE_CONTEXT_H
+#ifndef WILLOW_INCLUDE_IR_CONTEXT_H
+#define WILLOW_INCLUDE_IR_CONTEXT_H
 
 #include <willow/IR/Module.h>
 #include <willow/IR/TypeContext.h>
@@ -15,4 +15,4 @@ class WillowContext {
 
 } // namespace willow
 
-#endif // WILLOW_INCLUDE_CONTEXT_H
+#endif // WILLOW_INCLUDE_IR_CONTEXT_H
diff --git a/willow/include/willow/IR/Diagnostic.h b/willow/include/willow/IR/Diagnostic.h
index 2a74898..538704c 100644
--- a/willow/include/willow/IR/Diagnostic.h
+++ b/willow/include/willow/IR/Diagnostic.h
@@ -1,30 +1,22 @@
 #ifndef WILLOW_INCLUDE_IR_DIAGNOSTIC_H
 #define WILLOW_INCLUDE_IR_DIAGNOSTIC_H
 
-#include <willow/IR/Module.h>
+#include <willow/IR/Location.h>
 
-#include <cstdint>
 #include <string>
+#include <vector>
 
 namespace willow {
 
 enum class Severity { Debug, Remark, Warning, Error };
 
-struct Location {
-  std::string filename;
-  int line;
-  int col;
-};
-
 struct Diagnostic {
   Severity severity;
   std::string message;
   std::optional<Location> location;
-  /// Extra lines that will be printed after the diagnostic. Call sites, extra
-  /// info, etc
-  std::vector<std::string> notes;
+  std::vector<Diagnostic> notes;
 };
 
 } // namespace willow
 
-#endif // WILLOW_INCLUDE_SUPPORT_DIAGNOSTICS_H
+#endif // WILLOW_INCLUDE_IR_DIAGNOSTIC_H
diff --git a/willow/include/willow/IR/DiagnosticEngine.h b/willow/include/willow/IR/DiagnosticEngine.h
index 2293734..a8735af 100644
--- a/willow/include/willow/IR/DiagnosticEngine.h
+++ b/willow/include/willow/IR/DiagnosticEngine.h
@@ -3,6 +3,9 @@
 
 /// \file DiagnosticEngine.h Portable diagnostic handling
 
+#include <functional>
+#include <utility>
+
 #include <willow/IR/Diagnostic.h>
 #include <willow/Util/LogicalResult.h>
 
@@ -12,16 +15,16 @@ namespace willow {
 
 class DiagnosticEngine {
 public:
-  using Handler = std::function<void(const Diagnostic &)>;
+  using Handler = std::function<void(Diagnostic)>;
 
   DiagnosticEngine() = default;
   explicit DiagnosticEngine(Handler h) : handler(std::move(h)) {}
 
   void setHandler(Handler h) { handler = std::move(h); }
 
-  void report(Diagnostic d) { // NOLINT(performance-unnecessary-value-param)
+  void report(Diagnostic d) {
     if (handler)
-      handler(d);
+      handler(std::move(d));
   }
 
 private:
@@ -42,7 +45,7 @@ public:
                     std::optional<Location> loc)
       : engine(&eng) {
     diag.severity = severity;
-    diag.location = std::move(loc);
+    diag.location = loc;
   }
 
   DiagnosticBuilder(DiagnosticBuilder &&other) noexcept
@@ -60,22 +63,23 @@ public:
   template <typename T>
   DiagnosticBuilder &operator<<(T &&x) {
     os << std::forward<T>(x);
+    return *this;
   }
 
   /// Add a note to the diagnostic. Will be printed on its own line, following
   /// the diagnostic itself.
-  DiagnosticBuilder &note(std::string n) {
-    diag.notes.push_back(std::move(n));
+  DiagnosticBuilder &note(Diagnostic note) {
+    diag.notes.push_back(std::move(note));
     return *this;
   }
 
-  operator LogicalResult() const { return LogicalResult::Failure; }
+  operator LogicalResult() const { return failure(); }
 };
 
 /// DiagnosticBuilder factory.
 inline DiagnosticBuilder emit(DiagnosticEngine &eng, Severity severity,
                               std::optional<Location> loc = std::nullopt) {
-  return DiagnosticBuilder(eng, severity, std::move(loc));
+  return DiagnosticBuilder(eng, severity, loc);
 }
 
 } // namespace willow
diff --git a/willow/include/willow/IR/Function.h b/willow/include/willow/IR/Function.h
index 97e4029..4b2bd94 100644
--- a/willow/include/willow/IR/Function.h
+++ b/willow/include/willow/IR/Function.h
@@ -1,5 +1,5 @@
-#ifndef WILLOW_IR_FUNCTION_H
-#define WILLOW_IR_FUNCTION_H
+#ifndef WILLOW_INCLUDE_IR_FUNCTION_H
+#define WILLOW_INCLUDE_IR_FUNCTION_H
 
 #include <willow/IR/BasicBlock.h>
 #include <willow/IR/Value.h>
@@ -101,4 +101,4 @@ BasicBlock *Function::entryBlock() {
 
 } // namespace willow
 
-#endif // WILLOW_IR_FUNCTION_H
+#endif // WILLOW_INCLUDE_IR_FUNCTION_H
diff --git a/willow/include/willow/IR/IRBuilder.h b/willow/include/willow/IR/IRBuilder.h
index b67d169..635c41b 100644
--- a/willow/include/willow/IR/IRBuilder.h
+++ b/willow/include/willow/IR/IRBuilder.h
@@ -1,5 +1,5 @@
-#ifndef WILLOW_IR_IR_BUILDER_H
-#define WILLOW_IR_IR_BUILDER_H
+#ifndef WILLOW_INCLUDE_IR_IR_BUILDER_H
+#define WILLOW_INCLUDE_IR_IR_BUILDER_H
 
 #include <willow/IR/BasicBlock.h>
 #include <willow/IR/Function.h>
@@ -17,4 +17,4 @@ public:
 
 } // namespace willow
 
-#endif // WILLOW_IR_IR_BUILDER_H
+#endif // WILLOW_INCLUDE_IR_IR_BUILDER_H
diff --git a/willow/include/willow/IR/Instruction.h b/willow/include/willow/IR/Instruction.h
index f1bd0e6..39e0469 100644
--- a/willow/include/willow/IR/Instruction.h
+++ b/willow/include/willow/IR/Instruction.h
@@ -1,10 +1,13 @@
-#ifndef WILLOW_IR_INSTRUCTION_HPP
-#define WILLOW_IR_INSTRUCTION_HPP
+#ifndef WILLOW_INCLUDE_Ia_INSTRUCTION_H
+#define WILLOW_INCLUDE_IR_INSTRUCTION_H
 
+#include <willow/IR/Location.h>
 #include <willow/IR/Value.h>
+#include <willow/Util/LogicalResult.h>
 
 #include <cassert>
 #include <cstddef>
+#include <optional>
 #include <utility>
 #include <vector>
 
@@ -14,10 +17,10 @@ class Value;
 class BasicBlock;
 class Function;
 
-/// Defines an SSA value or control-flow effect.
+/// Defines an IR instruction.
 class Instruction : public Value {
 public:
-  enum class Op {
+  enum class Opcode {
     Add,
     Mul,
     Sub,
@@ -25,6 +28,8 @@ public:
     Mod,
     Shl,
     Shr,
+    Ashl,
+    Ashr,
 
     Eq,
     Lt,
@@ -47,9 +52,11 @@ public:
 
 private:
   BasicBlock *parent = nullptr;
-  Op op;
+  Opcode op;
 
+  std::optional<Location> loc;
   std::vector<Value *> operands;
+  std::vector<BasicBlock *> successors;
 
 protected:
   void setOperand(std::size_t index, Value *operand) {
@@ -67,27 +74,70 @@ protected:
 public:
   /// \param op Opcode for this instruction.
   /// \param type Type of the result of this instruction
-  Instruction(Op op, Type type) : Value(ValueKind::Instruction, type), op(op) {}
+  /// \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) {}
 
   /// \param name Name of the ssa value produced by the instruction.
   /// \param op Opcode for the instruction.
   /// \param type Type of the result of the instruction.
-  Instruction(std::string name, Type type, Op op)
-      : Value(ValueKind::Instruction, std::move(name), type) {}
+  /// \param loc Source location of this instruction.
+  Instruction(std::string name, Type type, Opcode op,
+              std::optional<Location> loc = std::nullopt)
+      : Value(ValueKind::Instruction, std::move(name), type), op(op), loc(loc) {
+  }
 
   ~Instruction() override {
     for (Value *operand : operands)
       operand->delUse(this);
   }
 
-  virtual bool verify(std::ostream &os) = 0;
-
   bool hasParent() const { return parent != nullptr; }
   BasicBlock *getParent() { return parent; }
   const BasicBlock *getParent() const { return parent; }
   void setParent(BasicBlock *block) { parent = block; }
 
-  Op getOp() const { return op; }
+  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;
+    }
+  }
+
+  bool isTerminator() const { return isTerminatorOp(op); }
+
+  Opcode opcode() const { return op; }
   std::size_t getNumOperands() const { return operands.size(); }
 
   Value *getOperand(std::size_t index) {
@@ -109,11 +159,12 @@ public:
   }
 };
 
-/// The base class for unary arithemetic instructions
+/// The base class for unary integer arithemetic instructions
 class UnaryInst : public Instruction {
 public:
-  UnaryInst(std::string name, Type type, Op op, Value *value)
-      : Instruction(std::move(name), type, op) {
+  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);
   }
 
@@ -121,10 +172,12 @@ public:
   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, Op op, Value *lhs, Value *rhs)
-      : Instruction(std::move(name), type, op) {
+  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);
   }
@@ -138,127 +191,141 @@ public:
 
 class AddInst : public BinaryInst {
 public:
-  AddInst(std::string name, Type type, Value *lhs, Value *rhs)
-      : BinaryInst(std::move(name), type, Op::Add, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Mul, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Sub, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Div, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Mod, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Shl, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Shr, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Eq, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Lt, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Gt, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Le, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Ge, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::And, lhs, rhs) {}
+  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)
-      : BinaryInst(std::move(name), type, Op::Or, lhs, rhs) {}
+  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)
-      : UnaryInst(std::move(name), type, Op::Not, value) {}
+  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 {
-  BasicBlock *target;
-
 public:
-  JmpInst(Type type, BasicBlock *target)
-      : Instruction(Op::Jmp, type), target(target) {}
+  JmpInst(Type type, BasicBlock *target,
+          std::optional<Location> loc = std::nullopt)
+      : Instruction(Opcode::Jmp, type, loc) {
+    addSuccessor(target);
+  }
 
-  BasicBlock *getTarget() { return target; }
-  const BasicBlock *getTarget() const { return target; }
+  BasicBlock *getTarget() { return succs()[0]; }
+  const BasicBlock *getTarget() const { return succs()[0]; }
 };
 
 class BrInst : public Instruction {
-  BasicBlock *true_target;
-  BasicBlock *false_target;
-
 public:
   BrInst(Type type, Value *condition, BasicBlock *true_target,
-         BasicBlock *false_target)
-      : Instruction(Op::Br, type), true_target(true_target),
-        false_target(false_target) {
+         BasicBlock *false_target, std::optional<Location> loc = std::nullopt)
+      : Instruction(Opcode::Br, type, loc) {
     addOperand(condition);
+    addSuccessor(true_target);
+    addSuccessor(false_target);
   }
 
   Value *getCondition() { return getOperand(0); }
   const Value *getCondition() const { return getOperand(0); }
 
-  BasicBlock *getTrueTarget() { return true_target; }
-  const BasicBlock *getTrueTarget() const { return true_target; }
+  BasicBlock *getTrueTarget() { return succs()[0]; }
+  const BasicBlock *getTrueTarget() const { return succs()[0]; }
 
-  BasicBlock *getFalseTarget() { return false_target; }
-  const BasicBlock *getFalseTarget() const { return false_target; }
+  BasicBlock *getFalseTarget() { return succs()[1]; }
+  const BasicBlock *getFalseTarget() const { return succs()[1]; }
 };
 
 } // namespace willow
 
-#endif // WILLOW_IR_INSTRUCTION_HPP
+#endif // WILLOW_INCLUDE_IR_INSTRUCTION_H
diff --git a/willow/include/willow/IR/Location.h b/willow/include/willow/IR/Location.h
new file mode 100644
index 0000000..e0ce838
--- /dev/null
+++ b/willow/include/willow/IR/Location.h
@@ -0,0 +1,32 @@
+#ifndef WILLOW_INCLUDE_IR_LOCATION_H
+#define WILLOW_INCLUDE_IR_LOCATION_H
+
+#include <format>
+#include <string_view>
+
+namespace willow {
+
+/// A source location
+struct Location {
+  std::string_view filename;
+  int line;
+  int col;
+};
+
+} // namespace willow
+
+template <>
+struct std::formatter<willow::Location> {
+  constexpr auto parse(std::format_parse_context &ctx) { return ctx.begin(); }
+
+  auto format(const willow::Location &loc, std::format_context &ctx) const {
+    return std::format_to(ctx.out(), "{}:{}:{}", loc.filename, loc.line,
+                          loc.col);
+  }
+};
+
+std::ostream &operator<<(std::ostream &os, const willow::Location &loc) {
+  return os << std::format("{}", loc);
+}
+
+#endif // WILLOW_INCLUDE_IR_LOCATION_H
diff --git a/willow/include/willow/IR/Module.h b/willow/include/willow/IR/Module.h
index 2002a90..59fb6a4 100644
--- a/willow/include/willow/IR/Module.h
+++ b/willow/include/willow/IR/Module.h
@@ -1,5 +1,5 @@
-#ifndef WILLOW_IR_MODULE_H
-#define WILLOW_IR_MODULE_H
+#ifndef WILLOW_INCLUDE_IR_MODULE_H
+#define WILLOW_INCLUDE_IR_MODULE_H
 
 #include <willow/IR/Function.h>
 
@@ -51,4 +51,4 @@ Function *Module::addFunction(std::unique_ptr<Function> fn) {
 
 } // namespace willow
 
-#endif // WILLOW_IR_MODULE_H
+#endif // WILLOW_INCLUDE_IR_MODULE_H
diff --git a/willow/include/willow/IR/TypeContext.h b/willow/include/willow/IR/TypeContext.h
index d1323f0..12aaa02 100644
--- a/willow/include/willow/IR/TypeContext.h
+++ b/willow/include/willow/IR/TypeContext.h
@@ -1,5 +1,5 @@
-#ifndef _WILLOW_INCLUDE_TYPE_CONTEXT_H
-#define _WILLOW_INCLUDE_TYPE_CONTEXT_H
+#ifndef WILLOW_INCLUDE_IR_TYPE_CONTEXT_H
+#define WILLOW_INCLUDE_IR_TYPE_CONTEXT_H
 
 #include <willow/IR/Types.h>
 
@@ -54,4 +54,4 @@ Type TypeContext::getVoidType() { return Type(voidty.get()); }
 
 } // namespace willow
 
-#endif // _WILLOW_INCLUDE_TYPE_CONTEXT_H
+#endif // WILLOW_INCLUDE_IR_TYPE_CONTEXT_H
diff --git a/willow/include/willow/IR/Types.h b/willow/include/willow/IR/Types.h
index 6ca9f2a..54242ac 100644
--- a/willow/include/willow/IR/Types.h
+++ b/willow/include/willow/IR/Types.h
@@ -1,9 +1,9 @@
-#ifndef _WILLOW_IR_TYPES_H
-#define _WILLOW_IR_TYPES_H
+#ifndef WILLOW_INCLUDE_IR_TYPES_H
+#define WILLOW_INCLUDE_IR_TYPES_H
 
 #include <cstddef>
+#include <format>
 #include <functional>
-#include <ostream>
 
 namespace willow {
 
@@ -89,6 +89,8 @@ public:
   PtrTypeImpl(Type pointee_type, std::size_t size)
       : TypeImpl{TypeID::Ptr, size}, pointee{pointee_type.getImpl()} {}
 
+  Type getPointee() const { return Type{pointee.getImpl()}; }
+
   struct Key {
     Type pointee;
     explicit Key(Type pointee) : pointee{pointee} {}
@@ -108,6 +110,60 @@ public:
   VoidTypeImpl() : TypeImpl{TypeID::Void} {}
 };
 
+constexpr std::string_view primitiveTypeName(TypeID tid) {
+  using enum TypeID;
+  switch (tid) {
+  case TypeID::Void:
+    return "void";
+  case TypeID::Label:
+    return "label";
+  case TypeID::Int:
+    return "int";
+  case TypeID::Function:
+    return "function";
+  case TypeID::Ptr:
+    return "ptr";
+  case TypeID::Struct:
+    return "struct";
+  case TypeID::Vector:
+    return "vector";
+  }
+}
+
 }; // namespace willow
 
-#endif // _WILLOW_IR_TYPES_H
+template <>
+struct std::formatter<willow::Type> {
+  constexpr auto parse(std::format_parse_context &ctx) { return ctx.begin(); }
+
+  auto format(const willow::Type &ty, std::format_context &ctx) const {
+    using enum willow::TypeID;
+    switch (ty.kind()) {
+    case Void:
+    case Label:
+    case Function:
+      return std::format_to(ctx.out(), "{}",
+                            willow::primitiveTypeName(ty.kind()));
+    case Int: {
+      std::size_t num_bits = ty.getNumBits();
+      return std::format_to(ctx.out(), "i{}", num_bits);
+    }
+    case Ptr:
+      return std::format_to(
+          ctx.out(), "*{}",
+          (static_cast<willow::PtrTypeImpl *>(ty.getImpl())->getPointee()));
+    // TODO
+    // case Struct:
+    // case Vector:
+    default:
+      return std::format_to(ctx.out(), "{}",
+                            willow::primitiveTypeName(ty.kind()));
+    }
+  }
+};
+
+std::ostream &operator<<(std::ostream &os, willow::Type ty) {
+  return os << std::format("{}", ty);
+}
+
+#endif // WILLOW_INCLUDE_IR_TYPES_H
diff --git a/willow/include/willow/IR/Value.h b/willow/include/willow/IR/Value.h
index 1e07fe4..138b895 100644
--- a/willow/include/willow/IR/Value.h
+++ b/willow/include/willow/IR/Value.h
@@ -1,5 +1,5 @@
-#ifndef _WILLOW_IR_VALUE_HPP
-#define _WILLOW_IR_VALUE_HPP
+#ifndef WILLOW_INCLUDE_IR_VALUE_H
+#define WILLOW_INCLUDE_IR_VALUE_H
 
 #include <willow/IR/Types.h>
 
@@ -78,4 +78,4 @@ public:
 
 } // namespace willow
 
-#endif // _WILLOW_IR_VALUE_HPP
+#endif // WILLOW_INCLUDE_IR_VALUE_H
diff --git a/willow/include/willow/IR/Verifier.h b/willow/include/willow/IR/Verifier.h
new file mode 100644
index 0000000..b5df294
--- /dev/null
+++ b/willow/include/willow/IR/Verifier.h
@@ -0,0 +1,27 @@
+#ifndef WILLOW_INCLUDE_IR_VERIFIER_H
+#define WILLOW_INCLUDE_IR_VERIFIER_H
+
+/// \file These are generic helpers for verification of IR, that can be used to
+/// check the validity of a transformation.
+
+#include <willow/Util/LogicalResult.h>
+
+namespace willow {
+
+class Module;
+class DiagnosticEngine;
+class Function;
+class BasicBlock;
+class Instruction;
+class BinaryInst;
+
+LogicalResult verifyModule(const Module &, DiagnosticEngine &);
+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/LogicalResult.h b/willow/include/willow/Util/LogicalResult.h
index 3a345eb..c09310f 100644
--- a/willow/include/willow/Util/LogicalResult.h
+++ b/willow/include/willow/Util/LogicalResult.h
@@ -1,14 +1,34 @@
-#ifndef WILLOW_INCLUDE_LOGICAL_RESULT_H
-#define WILLOW_INCLUDE_LOGICAL_RESULT_H
-
-#include <cstdint>
+#ifndef WILLOW_INCLUDE_UTIL_LOGICAL_RESULT_H
+#define WILLOW_INCLUDE_UTIL_LOGICAL_RESULT_H
 
 namespace willow {
 
-enum class LogicalResult : uint8_t { Success, Failure };
-inline bool succeeded(LogicalResult r) { return r == LogicalResult::Success; }
-inline bool failed(LogicalResult r) { return r == LogicalResult::Failure; }
+struct [[nodiscard]] LogicalResult {
+  static LogicalResult success(bool is_success = true) {
+    return LogicalResult(is_success);
+  }
+  static LogicalResult failure(bool is_failure = true) {
+    return LogicalResult(!is_failure);
+  }
+
+  constexpr bool succeeded() const { return is_success; }
+  constexpr bool failed() const { return !is_success; }
+
+  LogicalResult(bool is_success) : is_success(is_success) {}
+
+private:
+  bool is_success;
+};
+
+inline LogicalResult success(bool is_success = true) {
+  return LogicalResult::success(is_success);
+}
+inline LogicalResult failure(bool is_failure = true) {
+  return LogicalResult::success(is_failure);
+}
+inline bool succeeded(LogicalResult r) { return r.succeeded(); }
+inline bool failed(LogicalResult r) { return r.failed(); }
 
 } // namespace willow
 
-#endif // WILLOW_INCLUDE_LOGICAL_RESULT_H
+#endif // WILLOW_INCLUDE_UTIL_LOGICAL_RESULT_H
diff --git a/willow/lib/IR/Instruction.cpp b/willow/lib/IR/Instruction.cpp
index 21a4cae..a61cd55 100644
--- a/willow/lib/IR/Instruction.cpp
+++ b/willow/lib/IR/Instruction.cpp
@@ -1 +1,3 @@
 #include <willow/IR/Instruction.h>
+
+namespace willow {};
diff --git a/willow/lib/IR/Verifier.cpp b/willow/lib/IR/Verifier.cpp
new file mode 100644
index 0000000..b692b2f
--- /dev/null
+++ b/willow/lib/IR/Verifier.cpp
@@ -0,0 +1,181 @@
+#include <willow/IR/BasicBlock.h>
+#include <willow/IR/Diagnostic.h>
+#include <willow/IR/DiagnosticEngine.h>
+#include <willow/IR/Module.h>
+#include <willow/IR/Verifier.h>
+
+namespace willow {
+
+/// Verify that an instruction defines an SSA result
+LogicalResult verifyResult(const Instruction &inst, DiagnosticEngine &diags);
+
+LogicalResult verifyNumOperands(const Instruction &inst,
+                                DiagnosticEngine &diags, std::size_t expected);
+
+LogicalResult verifyModule(const Module &module, DiagnosticEngine &diags) {
+  bool any_failure = false;
+
+  for (auto &func : module.getFunctions()) {
+    std::vector<Diagnostic> collected;
+    DiagnosticEngine eng(
+        [&](Diagnostic d) { collected.push_back(std::move(d)); });
+
+    auto r = verifyFunction(func, eng);
+
+    if (succeeded(r))
+      continue;
+
+    any_failure = true;
+
+    auto diag = emit(diags, Severity::Error, std::nullopt);
+    diag << "verification failed for function: '" << func.getName() << "'";
+
+    for (auto &d : collected)
+      diag.note(std::move(d));
+  }
+
+  return any_failure ? failure() : success();
+}
+
+// LogicalResult verifyFunction(const Function&function, DiagnosticEngine
+// &diags) {
+//   bool any_failure = false;
+// }
+
+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
+
+    for (auto &inst : BB.getBody()) {
+      // verify inst
+    }
+}
+
+// TODO: better instruction printing
+LogicalResult verifyInst(const Instruction &inst, DiagnosticEngine &diags) {
+  using enum Instruction::Opcode;
+  switch (inst.opcode()) {
+  case Add:
+  case Mul:
+  case Sub:
+  case Div:
+  case Mod:
+  case Shl:
+  case Shr:
+  case Ashl:
+  case Ashr:
+  case And:
+  case Or:
+    return verifyBinaryInst(inst, diags);
+  case Eq:
+  case Lt:
+  case Gt:
+  case Le:
+  case Ge: {
+    Type ty = inst.getType();
+    if (!ty.isInt() || ty.getNumBits() != 1)
+      return emit(diags, Severity::Error, inst.getLoc())
+             << std::format("unexpected result type '{}': compare "
+                            "instructions return i1",
+                            ty);
+
+    size_t num_operands = inst.getNumOperands();
+    if (num_operands != 2)
+      return emit(diags, Severity::Error, inst.getLoc())
+             << std::format("expected 2 operands, found {}", num_operands);
+
+    const Value *lhs = inst.getOperand(0);
+    const Value *rhs = inst.getOperand(1);
+
+    Type lty = lhs->getType(), rty = rhs->getType();
+
+    if (!lty.isInt())
+      return emit(diags, Severity::Error, inst.getLoc()) << std::format(
+                 "invalid operand type '{}': expected integral type", lty);
+
+    if (!rty.isInt())
+      return emit(diags, Severity::Error, inst.getLoc()) << std::format(
+                 "invalid operand type '{}': expected integral type", rty);
+
+    if (lty != rty)
+      return emit(diags, Severity::Error, inst.getLoc())
+             << "mismatched operand types";
+  }
+  case Not: {
+    Type ty = inst.getType();
+
+    if (failed(verifyResult(inst, diags)))
+      return failure();
+
+    const Value *operand = inst.getOperand(0);
+    if (!operand)
+      return emit(diags, Severity::Error, inst.getLoc())
+             << "instruction 'not' requires 1 operand";
+
+    Type oty = operand->getType();
+    if (ty != oty)
+      return emit(diags, Severity::Error, inst.getLoc())
+             << std::format("expected argument type '{}', got '{}'", ty, oty);
+  }
+  case Jmp:
+  case Br:
+  case Call:
+  case Ret:
+  case Phi:
+  case Alloca:
+  }
+}
+
+// TODO: better naming?
+LogicalResult verifyBinaryInst(const Instruction &inst,
+                               DiagnosticEngine &diags) {
+  Type ty = inst.getType();
+
+  // TODO non scalars
+  if (!ty.isInt())
+    return emit(diags, Severity::Error, inst.getLoc())
+           << "invalid instruction '" << inst << "': "
+           << "expected an integral type, got '" << ty << "'";
+
+  auto *lhs = inst.getOperand(0);
+  auto *rhs = inst.getOperand(1);
+
+  assert(lhs && "Binary op lacks LHS");
+  assert(rhs && "Binary op needs RHS");
+
+  if (lhs->getType() != ty) {
+    return emit(diags, Severity::Error, inst.getLoc()) << std::format(
+               "expected operand type '{}' got '{}'", ty, lhs->getType());
+  }
+
+  if (rhs->getType() != ty) {
+    return emit(diags, Severity::Error, inst.getLoc()) << std::format(
+               "expected operand type '{}' got '{}'", ty, rhs->getType());
+  }
+}
+
+LogicalResult verifyResult(const Instruction &inst, DiagnosticEngine &diags) {
+  if (inst.hasName())
+    return success();
+
+  return emit(diags, Severity::Error, inst.getLoc()) << "expected ssa result";
+}
+
+LogicalResult verifyNumOperands(const Instruction &inst,
+                                DiagnosticEngine &diags, std::size_t expected) {
+  if (inst.getNumOperands() != expected)
+    return emitE
+}
+
+} // namespace willow