feat: value abstraction (#1)

- Instructions are values
- Instructions that don't produce a value have void type

5 files changed, 264 insertions, 26 deletions

diff --git a/willow/include/willow/IR/BasicBlock.h b/willow/include/willow/IR/BasicBlock.h
index d783a5b..03d4fb8 100644
--- a/willow/include/willow/IR/BasicBlock.h
+++ b/willow/include/willow/IR/BasicBlock.h
@@ -59,6 +59,7 @@ public:
   template <typename... Args>
   Instruction *emplaceInstruction(Args &&...args) {
     body.push_back(std::make_unique<Instruction>(std::forward(args)...));
+    body.back()->setParent(this);
     return body.back().get();
   }
 
@@ -89,6 +90,7 @@ Instruction *BasicBlock::leader() {
 
 Instruction *BasicBlock::addInstruction(std::unique_ptr<Instruction> inst) {
   Instruction *p = inst.get();
+  p->setParent(this);
   body.push_back(std::move(inst));
   return p;
 }
diff --git a/willow/include/willow/IR/IRBuilder.h b/willow/include/willow/IR/IRBuilder.h
index 79d3bb3..b67d169 100644
--- a/willow/include/willow/IR/IRBuilder.h
+++ b/willow/include/willow/IR/IRBuilder.h
@@ -12,7 +12,7 @@ class IRBuilder {
   BasicBlock *block = nullptr;
 
 public:
-  explicit IRBuilder(BasicBlock *block) : block(block);
+  explicit IRBuilder(BasicBlock *block) : block(block) {}
 };
 
 } // namespace willow
diff --git a/willow/include/willow/IR/Instruction.h b/willow/include/willow/IR/Instruction.h
index c7756bb..a4dfbbb 100644
--- a/willow/include/willow/IR/Instruction.h
+++ b/willow/include/willow/IR/Instruction.h
@@ -3,16 +3,21 @@
 
 #include <willow/IR/Value.h>
 
+#include <cassert>
+#include <cstddef>
+#include <utility>
+#include <vector>
+
 namespace willow {
 
 class Value;
+class BasicBlock;
+class Function;
 
 /// Defines an SSA value or control-flow effect.
-class Instruction : Value {
+class Instruction : public Value {
 public:
   enum class Op {
-    Const,
-
     Add,
     Mul,
     Sub,
@@ -27,9 +32,9 @@ public:
     Le,
     Ge,
 
-    Not,
     And,
     Or,
+    Not,
 
     Jmp,
     Br,
@@ -41,21 +46,216 @@ public:
   };
 
 private:
-  class BasicBlock *parent = nullptr;
+  BasicBlock *parent = nullptr;
   Op op;
 
+  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);
+  }
+
 public:
   /// \param op Opcode for this instruction.
-  /// \param val SSA value defined by this instruction (may be nullptr).
-  Instruction(Op op, Value *val);
+  /// \param type Type of the result of this instruction
+  Instruction(Op op, Type type) : Value(ValueKind::Instruction, type), op(op) {}
+
+  /// \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) {}
+
+  ~Instruction() override {
+    for (Value *operand : operands)
+      operand->delUse(this);
+  }
+
+  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::size_t getNumOperands() const { return operands.size(); }
+
+  Value *getOperand(std::size_t index) {
+    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];
+  }
+
+  std::vector<Value *> &getOperands() { return operands; }
+  const std::vector<Value *> &getOperands() const { return operands; }
+
+  void addOperand(Value *operand) {
+    assert(operand && "Operand cannot be null");
+    operands.push_back(operand);
+    operand->addUse(this);
+  }
+};
+
+class UnaryInst : public Instruction {
+public:
+  UnaryInst(std::string name, Type type, Op op, Value *value)
+      : Instruction(std::move(name), type, op) {
+    addOperand(value);
+  }
+
+  Value *getValue() { return getOperand(0); }
+  const Value *getValue() const { return getOperand(0); }
+};
+
+class BinaryInst : public Instruction {
+public:
+  BinaryInst(std::string name, Type type, Op op, Value *lhs, Value *rhs)
+      : Instruction(std::move(name), type, op) {
+    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)
+      : BinaryInst(std::move(name), type, Op::Add, lhs, rhs) {}
+};
+
+class MulInst : public BinaryInst {
+public:
+  MulInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Mul, lhs, rhs) {}
+};
+
+class SubInst : public BinaryInst {
+public:
+  SubInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Sub, lhs, rhs) {}
+};
+
+class DivInst : public BinaryInst {
+public:
+  DivInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Div, lhs, rhs) {}
+};
+
+class ModInst : public BinaryInst {
+public:
+  ModInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Mod, lhs, rhs) {}
+};
+
+class ShlInst : public BinaryInst {
+public:
+  ShlInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Shl, lhs, rhs) {}
+};
+
+class ShrInst : public BinaryInst {
+public:
+  ShrInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Shr, lhs, rhs) {}
+};
+
+class EqInst : public BinaryInst {
+public:
+  EqInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Eq, lhs, rhs) {}
+};
+
+class LtInst : public BinaryInst {
+public:
+  LtInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Lt, lhs, rhs) {}
+};
+
+class GtInst : public BinaryInst {
+public:
+  GtInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Gt, lhs, rhs) {}
+};
+
+class LeInst : public BinaryInst {
+public:
+  LeInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Le, lhs, rhs) {}
+};
+
+class GeInst : public BinaryInst {
+public:
+  GeInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Ge, lhs, rhs) {}
+};
+
+class AndInst : public BinaryInst {
+public:
+  AndInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::And, lhs, rhs) {}
+};
+
+class OrInst : public BinaryInst {
+public:
+  OrInst(std::string name, Type type, Value *lhs, Value *rhs)
+      : BinaryInst(std::move(name), type, Op::Or, lhs, rhs) {}
+};
+
+class NotInst : public UnaryInst {
+public:
+  explicit NotInst(std::string name, Type type, Value *value)
+      : UnaryInst(std::move(name), type, Op::Not, value) {}
+};
+
+class JmpInst : public Instruction {
+  BasicBlock *target;
+
+public:
+  JmpInst(Type type, BasicBlock *target)
+      : Instruction(Op::Jmp, type), target(target) {}
+
+  BasicBlock *getTarget() { return target; }
+  const BasicBlock *getTarget() const { return target; }
+};
+
+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) {
+    addOperand(condition);
+  }
+
+  Value *getCondition() { return getOperand(0); }
+  const Value *getCondition() const { return getOperand(0); }
+
+  BasicBlock *getTrueTarget() { return true_target; }
+  const BasicBlock *getTrueTarget() const { return true_target; }
 
-  const Value *getValue() const { return value; }
-  Value *getValue() { return value; }
-  bool hasValue() const { return value; }
+  BasicBlock *getFalseTarget() { return false_target; }
+  const BasicBlock *getFalseTarget() const { return false_target; }
 };
 
 } // namespace willow
 
-#endif // WILLOW_IR_INST_HPP
+#endif // WILLOW_IR_INSTRUCTION_HPP
diff --git a/willow/include/willow/IR/Types.h b/willow/include/willow/IR/Types.h
index 85f4a67..6ca9f2a 100644
--- a/willow/include/willow/IR/Types.h
+++ b/willow/include/willow/IR/Types.h
@@ -103,6 +103,11 @@ public:
   };
 };
 
+class VoidTypeImpl : public TypeImpl {
+public:
+  VoidTypeImpl() : TypeImpl{TypeID::Void} {}
+};
+
 }; // namespace willow
 
 #endif // _WILLOW_IR_TYPES_H
diff --git a/willow/include/willow/IR/Value.h b/willow/include/willow/IR/Value.h
index a819b53..1e07fe4 100644
--- a/willow/include/willow/IR/Value.h
+++ b/willow/include/willow/IR/Value.h
@@ -1,35 +1,38 @@
 #ifndef _WILLOW_IR_VALUE_HPP
 #define _WILLOW_IR_VALUE_HPP
 
-// #include <willow/IR/Instruction.h>
 #include <willow/IR/Types.h>
 
+#include <cassert>
 #include <string>
 #include <string_view>
-#include <vector>
+#include <unordered_map>
 
 namespace willow {
 
 class Instruction;
 
-enum class ValueType {
-  Result,    ///< the identified result of an instruction
-  Parameter, ///< the named parameter to a function
-  Literal,   ///< an anonymous typed literal
+enum class ValueKind {
+  Instruction, ///< the identified result of an instruction
+  Parameter,   ///< the named parameter to a function
+  Literal,     ///< an anonymous typed literal
 };
 
 /// An SSA value that may be used.
 class Value {
+  ValueKind value_type;
   std::string name;
-  ValueType value_type;
   Type type;
 
   // Instructions that use this value
-  std::vector<Instruction *> uses;
+  std::unordered_map<Instruction *, std::size_t> uses;
 
 public:
-  Value(std::string name, Type type) : name(std::move(name)), type(type) {}
-  explicit Value(Type type) : type(type) {}
+  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) {}
 
   bool hasName() const { return !name.empty(); }
 
@@ -37,12 +40,40 @@ public:
   void setName(std::string name) { this->name = std::move(name); }
 
   Type getType() const { return type; }
-  ValueType getValueType() const { return value_type; }
+  ValueKind getValueType() const { return value_type; }
+
+  bool isVoid() const { return type.isVoid(); }
+
+  /// 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);
 
-  bool isVoid() const { return type->is }
+    if (!inserted)
+      it->second += 1;
+  }
 
-  const std::vector<Instruction *> &getUses() const { return uses; }
-  std::vector<Instruction *> &getUses() { return uses; }
+  /// 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);
+  }
+};
+
+class Parameter : public Value {
+public:
+  Parameter(std::string name, Type type)
+      : Value(ValueKind::Parameter, std::move(name), type) {}
 };
 
 } // namespace willow