From d4b629cc275769c2553db819643849cda2395a17 Mon Sep 17 00:00:00 2001 From: Stefan Weigl-Bosker Date: Mon, 5 Jan 2026 12:40:09 -0500 Subject: init wip wip, pt2 wip, pt3 --- willow/include/willow/IR/BasicBlock.h | 98 ++++++++++++++++++++++++++++++ willow/include/willow/IR/Function.h | 104 +++++++++++++++++++++++++++++++ willow/include/willow/IR/IRBuilder.h | 20 ++++++ willow/include/willow/IR/Instruction.h | 61 +++++++++++++++++++ willow/include/willow/IR/Module.h | 54 +++++++++++++++++ willow/include/willow/IR/TypeContext.h | 57 +++++++++++++++++ willow/include/willow/IR/Types.h | 108 +++++++++++++++++++++++++++++++++ willow/include/willow/IR/Value.h | 50 +++++++++++++++ 8 files changed, 552 insertions(+) create mode 100644 willow/include/willow/IR/BasicBlock.h create mode 100644 willow/include/willow/IR/Function.h create mode 100644 willow/include/willow/IR/IRBuilder.h create mode 100644 willow/include/willow/IR/Instruction.h create mode 100644 willow/include/willow/IR/Module.h create mode 100644 willow/include/willow/IR/TypeContext.h create mode 100644 willow/include/willow/IR/Types.h create mode 100644 willow/include/willow/IR/Value.h (limited to 'willow/include') diff --git a/willow/include/willow/IR/BasicBlock.h b/willow/include/willow/IR/BasicBlock.h new file mode 100644 index 0000000..d783a5b --- /dev/null +++ b/willow/include/willow/IR/BasicBlock.h @@ -0,0 +1,98 @@ +#ifndef WILLOW_IR_BASIC_BLOCK_H +#define WILLOW_IR_BASIC_BLOCK_H + +#include + +#include +#include +#include +#include +#include +#include +#include + +namespace willow { + +class Function; + +/// A group of consecutive instructions. +class BasicBlock { + std::string name; + Function *parent = nullptr; + + std::list> body; + + std::vector preds; + std::vector succs; + +public: + // ~BasicBlock() = TODO + /// Create a basic block with a name and parent function. + BasicBlock(std::string name, Function *parent) + : name(std::move(name)), parent(parent) {} + + std::string_view getName() const { return name; } + void setName(std::string name) { this->name = std::move(name); } + + Function *getParent() const { return parent; } + bool hasParent() const { return parent; } + void setParent(Function *parent) { this->parent = parent; } + + bool empty() const { return body.empty(); } + std::size_t size() { return body.size(); } + + auto getBody() { + return body | + std::views::transform([](auto &p) -> Instruction & { return *p; }); + } + + auto getBody() const { + return body | std::views::transform( + [](auto &p) -> const Instruction & { return *p; }); + } + + Instruction *trailer(); + Instruction *leader(); + + Instruction *addInstruction(std::unique_ptr inst); + + template + Instruction *emplaceInstruction(Args &&...args) { + body.push_back(std::make_unique(std::forward(args)...)); + return body.back().get(); + } + + const std::vector &predecessors() const { return preds; } + std::vector &predecessors() { return preds; } + + const std::vector &successors() const { return succs; } + std::vector &successors() { return succs; } + + void addPredecessor(BasicBlock *pred) { preds.push_back(pred); } + void addSuccessor(BasicBlock *succ) { succs.push_back(succ); } + // TODO: add/remove preds +}; + +Instruction *BasicBlock::trailer() { + if (empty()) + return nullptr; + else + return body.back().get(); +} + +Instruction *BasicBlock::leader() { + if (empty()) + return nullptr; + else + return body.back().get(); +} + +Instruction *BasicBlock::addInstruction(std::unique_ptr inst) { + Instruction *p = inst.get(); + body.push_back(std::move(inst)); + return p; +} + +} // namespace willow + +#endif // WILLOW_IR_BASIC_BLOCK_H diff --git a/willow/include/willow/IR/Function.h b/willow/include/willow/IR/Function.h new file mode 100644 index 0000000..97e4029 --- /dev/null +++ b/willow/include/willow/IR/Function.h @@ -0,0 +1,104 @@ +#ifndef WILLOW_IR_FUNCTION_H +#define WILLOW_IR_FUNCTION_H + +#include +#include + +#include +#include +#include +#include +#include +#include + +namespace willow { + +class Module; + +/// Groups basic blocks and the values they define. +class Function { + std::string name; + Module *parent = nullptr; + + std::vector> blocks; + std::vector> values; + +public: + /// Create a function with a name and its owning module. + /// \param name Function identifier. + /// \param parent Owning module. + Function(std::string name, Module *parent) + : name(std::move(name)), parent(parent) {} + + std::string_view getName() const { return name; } + void setName(std::string name) { this->name = std::move(name); } + + /// \return Parent module or nullptr. + Module *getParent() { return parent; } + const Module *getParent() const { return parent; } + void setParent(Module *parent) { this->parent = parent; } + + /// \return Entry block or nullptr. + BasicBlock *entryBlock(); + const BasicBlock *entryBlock() const; + + bool empty() const { return blocks.empty(); } + std::size_t numBlocks() const { return blocks.size(); } + + /// \return The blocks that make up this function. + auto getBlocks() { + return blocks | + std::views::transform([](auto &p) -> BasicBlock & { return *p; }); + } + + auto getBlocks() const { + return blocks | std::views::transform( + [](auto &p) -> const BasicBlock & { return *p; }); + } + + /// \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 block) { + auto p = block.get(); + blocks.push_back(std::move(block)); + p->setParent(this); + return p; + } + + /// Construct a new block in-place and append it. + /// \return Raw pointer to the appended block. + template + BasicBlock *createBlock(Args &&...args) { + blocks.push_back(std::make_unique(std::forward(args)...)); + return blocks.back().get(); + } +}; + +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 + +#endif // WILLOW_IR_FUNCTION_H diff --git a/willow/include/willow/IR/IRBuilder.h b/willow/include/willow/IR/IRBuilder.h new file mode 100644 index 0000000..79d3bb3 --- /dev/null +++ b/willow/include/willow/IR/IRBuilder.h @@ -0,0 +1,20 @@ +#ifndef WILLOW_IR_IR_BUILDER_H +#define WILLOW_IR_IR_BUILDER_H + +#include +#include +#include + +namespace willow { + +/// Helper for constructing and modifiying IR. +class IRBuilder { + BasicBlock *block = nullptr; + +public: + explicit IRBuilder(BasicBlock *block) : block(block); +}; + +} // namespace willow + +#endif // WILLOW_IR_IR_BUILDER_H diff --git a/willow/include/willow/IR/Instruction.h b/willow/include/willow/IR/Instruction.h new file mode 100644 index 0000000..c7756bb --- /dev/null +++ b/willow/include/willow/IR/Instruction.h @@ -0,0 +1,61 @@ +#ifndef WILLOW_IR_INSTRUCTION_HPP +#define WILLOW_IR_INSTRUCTION_HPP + +#include + +namespace willow { + +class Value; + +/// Defines an SSA value or control-flow effect. +class Instruction : Value { +public: + enum class Op { + Const, + + Add, + Mul, + Sub, + Div, + Mod, + Shl, + Shr, + + Eq, + Lt, + Gt, + Le, + Ge, + + Not, + And, + Or, + + Jmp, + Br, + Call, + Ret, + + Phi, + Alloca + }; + +private: + class BasicBlock *parent = nullptr; + Op op; + +public: + /// \param op Opcode for this instruction. + /// \param val SSA value defined by this instruction (may be nullptr). + Instruction(Op op, Value *val); + + Op getOp() const { return op; } + + const Value *getValue() const { return value; } + Value *getValue() { return value; } + bool hasValue() const { return value; } +}; + +} // namespace willow + +#endif // WILLOW_IR_INST_HPP diff --git a/willow/include/willow/IR/Module.h b/willow/include/willow/IR/Module.h new file mode 100644 index 0000000..2002a90 --- /dev/null +++ b/willow/include/willow/IR/Module.h @@ -0,0 +1,54 @@ +#ifndef WILLOW_IR_MODULE_H +#define WILLOW_IR_MODULE_H + +#include + +namespace willow { + +/// Represents a compilation unit. +class Module { + std::string name; + std::vector> functions; + +public: + explicit Module(std::string name) : name(std::move(name)) {} + + /// Moves a Function to this module, transfering ownership. + /// \param fn The function to move. + /// \return A raw pointer to the function. + Function *addFunction(std::unique_ptr fn); + + template + Function *emplaceFunction(Args &&...args) { + functions.push_back( + std::make_unique(std::forward(args)...)); + auto *fn = functions.back().get(); + fn->setParent(this); + return fn; + } + + std::string_view getName() const { return name; } + void setName(std::string name) { this->name = std::move(name); } + + std::size_t numFunctions() const { return functions.size(); } + + auto getFunctions() { + return functions | + std::views::transform([](auto &p) -> Function & { return *p; }); + } + auto getFunctions() const { + return functions | std::views::transform( + [](auto &p) -> const Function & { return *p; }); + } +}; + +Function *Module::addFunction(std::unique_ptr fn) { + auto p = fn.get(); + functions.push_back(std::move(fn)); + p->setParent(this); + return p; +} + +} // namespace willow + +#endif // WILLOW_IR_MODULE_H diff --git a/willow/include/willow/IR/TypeContext.h b/willow/include/willow/IR/TypeContext.h new file mode 100644 index 0000000..d1323f0 --- /dev/null +++ b/willow/include/willow/IR/TypeContext.h @@ -0,0 +1,57 @@ +#ifndef _WILLOW_INCLUDE_TYPE_CONTEXT_H +#define _WILLOW_INCLUDE_TYPE_CONTEXT_H + +#include + +#include +#include + +namespace willow { + +/// Context that owns and uniques type instances. +class TypeContext { +public: + TypeContext() = default; + TypeContext(const TypeContext &) = delete; + TypeContext &operator=(const TypeContext &) = delete; + + /// \param width Bit width of the integer type. + /// \return Uniqued integer type for the requested width. + Type getIntType(std::size_t width); + + /// \param pointee Type of the pointee. + /// \param size Size in bits of the pointer representation. + /// \return Uniqued pointer type. + Type getPtrType(Type pointee, std::size_t size); + + /// \return Uniqued void type. + Type getVoidType(); + +private: + std::unordered_map, + IntTypeImpl::Hash> + icache; + std::unordered_map, + PtrTypeImpl::Hash> + pcache; + std::unique_ptr voidty; +}; + +Type TypeContext::getIntType(std::size_t width) { + auto [it, _] = icache.try_emplace(IntTypeImpl::Key{width}); + + return Type(it->second.get()); +} + +Type TypeContext::getPtrType(Type pointee, std::size_t size) { + auto [it, _] = pcache.try_emplace( + PtrTypeImpl::Key{pointee}, std::make_unique(pointee, size)); + + return Type(it->second.get()); +} + +Type TypeContext::getVoidType() { return Type(voidty.get()); } + +} // namespace willow + +#endif // _WILLOW_INCLUDE_TYPE_CONTEXT_H diff --git a/willow/include/willow/IR/Types.h b/willow/include/willow/IR/Types.h new file mode 100644 index 0000000..85f4a67 --- /dev/null +++ b/willow/include/willow/IR/Types.h @@ -0,0 +1,108 @@ +#ifndef _WILLOW_IR_TYPES_H +#define _WILLOW_IR_TYPES_H + +#include +#include +#include + +namespace willow { + +/// IDs of all base types. +enum class TypeID { + // Primitive types + Void, ///< Void type + Label, ///< Label type + + // Parameterized types + Int, ///< Integer type of any bit width + Function, ///< A Function symbol + Ptr, ///< Parameterized pointer type + Struct, ///< Aggregate struct type + Vector, ///< Vector type +}; + +class TypeImpl; + +class TypeImpl { + friend class TypeContext; + TypeID kind; + std::size_t num_bits; + +protected: + explicit TypeImpl(TypeID kind) : kind{kind} {} + explicit TypeImpl(TypeID kind, size_t num_bits) + : kind{kind}, num_bits{num_bits} {} + +public: + virtual ~TypeImpl() = default; + TypeID getTypeKind() const { return kind; } + std::size_t getNumBits() const { return num_bits; } +}; + +/// Instances of Type represent uniqued, immutable datatypes. +/// +/// Internally, Type instances wrap a pointer to a TypeImpl, so they should be +/// passed by value. +class Type { + friend class TypeContext; + TypeImpl *impl; + +public: + explicit Type(TypeImpl *impl) : impl(impl) {} + + bool operator==(const Type &other) const { return impl == other.impl; } + bool operator!=(const Type &other) const { return impl != other.impl; } + // Type() : impl(nullptr) {} + + TypeID kind() const { return impl->getTypeKind(); }; + std::size_t getNumBits() const { return impl->getNumBits(); }; + TypeImpl *getImpl() const { return this->impl; } + + bool isInt() const { return kind() == TypeID::Int; } + bool isPtr() const { return kind() == TypeID::Ptr; } + bool isVoid() const { return kind() == TypeID::Void; } +}; + +class IntTypeImpl : public TypeImpl { +public: + explicit IntTypeImpl(std::size_t num_bits) + : TypeImpl{TypeID::Int, num_bits} {} + + struct Key { + std::size_t num_bits; + Key(std::size_t w) : num_bits(w) {} + + bool operator==(const Key &k) const { return this->num_bits == k.num_bits; } + }; + + struct Hash { + std::size_t operator()(const Key &k) const noexcept { + return std::hash{}(k.num_bits); + } + }; +}; + +class PtrTypeImpl : public TypeImpl { + Type pointee; + +public: + PtrTypeImpl(Type pointee_type, std::size_t size) + : TypeImpl{TypeID::Ptr, size}, pointee{pointee_type.getImpl()} {} + + struct Key { + Type pointee; + explicit Key(Type pointee) : pointee{pointee} {} + + bool operator==(const Key &k) const { return this->pointee == k.pointee; } + }; + + struct Hash { + std::size_t operator()(const Key &k) const noexcept { + return std::hash{}(k.pointee.getImpl()); + } + }; +}; + +}; // namespace willow + +#endif // _WILLOW_IR_TYPES_H diff --git a/willow/include/willow/IR/Value.h b/willow/include/willow/IR/Value.h new file mode 100644 index 0000000..a819b53 --- /dev/null +++ b/willow/include/willow/IR/Value.h @@ -0,0 +1,50 @@ +#ifndef _WILLOW_IR_VALUE_HPP +#define _WILLOW_IR_VALUE_HPP + +// #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 +}; + +/// An SSA value that may be used. +class Value { + std::string name; + ValueType value_type; + Type type; + + // Instructions that use this value + std::vector uses; + +public: + Value(std::string name, Type type) : name(std::move(name)), type(type) {} + explicit Value(Type type) : type(type) {} + + bool hasName() const { return !name.empty(); } + + std::string_view getName() const { return name; } + void setName(std::string name) { this->name = std::move(name); } + + Type getType() const { return type; } + ValueType getValueType() const { return value_type; } + + bool isVoid() const { return type->is } + + const std::vector &getUses() const { return uses; } + std::vector &getUses() { return uses; } +}; + +} // namespace willow + +#endif // _WILLOW_IR_VALUE_HPP -- cgit v1.2.3