From 3f60b0f7f43815f7cd38f744d3fbe56d04b6d8c3 Mon Sep 17 00:00:00 2001 From: Stefan Weigl-Bosker Date: Sat, 10 Jan 2026 19:16:52 -0500 Subject: feat: value abstraction (#1) - Instructions are values - Instructions that don't produce a value have void type --- willow/include/willow/IR/BasicBlock.h | 2 + willow/include/willow/IR/IRBuilder.h | 2 +- willow/include/willow/IR/Instruction.h | 222 +++++++++++++++++++++++++++++++-- willow/include/willow/IR/Types.h | 5 + willow/include/willow/IR/Value.h | 59 ++++++--- 5 files changed, 264 insertions(+), 26 deletions(-) (limited to 'willow/include') 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 Instruction *emplaceInstruction(Args &&...args) { body.push_back(std::make_unique(std::forward(args)...)); + body.back()->setParent(this); return body.back().get(); } @@ -89,6 +90,7 @@ Instruction *BasicBlock::leader() { Instruction *BasicBlock::addInstruction(std::unique_ptr 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 +#include +#include +#include +#include + 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 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 &getOperands() { return operands; } + const std::vector &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 #include +#include #include #include -#include +#include 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 uses; + std::unordered_map 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 &getUses() { return uses; } + const std::unordered_map &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 &getUses() const { return uses; } - std::vector &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 -- cgit v1.2.3