From add95b14f74e6dbe04a6efe98ff0f20424930b73 Mon Sep 17 00:00:00 2001 From: Stefan Weigl-Bosker Date: Tue, 3 Feb 2026 14:59:53 -0500 Subject: [willow]: initial frontend work, unit tests (#8) --- willow/include/willow/ADT/IList.h | 76 ++++++++++++++++++++++++++++++++++ willow/include/willow/IR/BasicBlock.h | 24 ++++++++--- willow/include/willow/IR/Constant.h | 16 +++++++ willow/include/willow/IR/Context.h | 7 ++++ willow/include/willow/IR/Function.h | 7 +++- willow/include/willow/IR/IRBuilder.h | 3 ++ willow/include/willow/IR/Instruction.h | 28 +++++++++---- willow/include/willow/IR/Location.h | 2 +- willow/include/willow/IR/Types.h | 23 +++++----- willow/include/willow/IR/Value.h | 4 ++ 10 files changed, 165 insertions(+), 25 deletions(-) create mode 100644 willow/include/willow/ADT/IList.h (limited to 'willow/include') diff --git a/willow/include/willow/ADT/IList.h b/willow/include/willow/ADT/IList.h new file mode 100644 index 0000000..0c55ad5 --- /dev/null +++ b/willow/include/willow/ADT/IList.h @@ -0,0 +1,76 @@ +#ifndef WILLOW_INCLUDE_ADT_ILIST_H +#define WILLOW_INCLUDE_ADT_ILIST_H + +#include + +namespace willow { + +template +class IList; + +/// An instrusive list node +template +class IListTrait { + friend class IList; + +public: + IListTrait() = default; + IListTrait(const IListTrait &) = delete; + IListTrait &operator=(const IListTrait &) = delete; + IListTrait(IListTrait &&) = delete; + IListTrait &operator=(IListTrait &&) = delete; + + T *getNext() const { return static_cast(next); } + T *getNext() { return static_cast(next); } + T *getPrev() const { return static_cast(prev); } + T *getPrev() { return static_cast(prev); } + + void insertAfter(IListTrait &node) { + auto old = this->next; + this->next = &node; + node->prev = this; + node->next = old; + }; + + void insertBefore(IListTrait &node) { + auto old = this->prev; + this->prev = node; + node->next = this; + node->prev = old; + }; + + /// Erase the node from the list. Return a pointer to the unliked node + T *removeFromList() { + prev->next = next; + next->prev = prev; + prev = nullptr; + next = nullptr; + return static_cast(this); + } + +private: + IListTrait *prev = nullptr; + IListTrait *next = nullptr; +}; + +/// Instrusive list +template +class IList { + static_assert(std::is_base_of_v, T>, + "T must implement IListTrait"); + using node = IListTrait; + +public: + IList() : dummyBegin{nullptr, &dummyEnd}, dummyEnd{&dummyBegin, dummyEnd} {} + IList(const IList &) = delete; + IList(IList &&) = delete; + +private: + // yes we could save 16 bytes, no i dont really care + node dummyBegin; + node dummyEnd; +}; + +} // namespace willow + +#endif // WILLOW_INCLUDE_ADT_ILIST_H diff --git a/willow/include/willow/IR/BasicBlock.h b/willow/include/willow/IR/BasicBlock.h index c18dfc2..5db8538 100644 --- a/willow/include/willow/IR/BasicBlock.h +++ b/willow/include/willow/IR/BasicBlock.h @@ -70,14 +70,14 @@ public: std::unordered_map& preds() { return predecessors; } const std::unordered_map& preds() const { return predecessors; } - inline void addPred(BasicBlock *bb) { + void addPred(BasicBlock *bb) { auto [it, inserted] = predecessors.try_emplace(bb, 1); if (!inserted) it->second += 1; } - inline void delPred(BasicBlock *bb) { + void delPred(BasicBlock *bb) { auto it = preds().find(bb); it->second -= 1; @@ -87,21 +87,35 @@ public: } }; -Instruction *BasicBlock::trailer() { +inline Instruction *BasicBlock::trailer() { if (empty()) return nullptr; else return body.back().get(); } -Instruction *BasicBlock::leader() { +inline Instruction *BasicBlock::leader() { if (empty()) return nullptr; else return body.back().get(); } -Instruction *BasicBlock::addInstruction(std::unique_ptr inst) { +inline const Instruction *BasicBlock::trailer() const { + if (empty()) + return nullptr; + else + return body.back().get(); +} + +inline const Instruction *BasicBlock::leader() const { + if (empty()) + return nullptr; + else + return body.back().get(); +} + +inline Instruction *BasicBlock::addInstruction(std::unique_ptr inst) { Instruction *p = inst.get(); p->setParent(this); body.push_back(std::move(inst)); diff --git a/willow/include/willow/IR/Constant.h b/willow/include/willow/IR/Constant.h index d93d65d..4e2a3d7 100644 --- a/willow/include/willow/IR/Constant.h +++ b/willow/include/willow/IR/Constant.h @@ -1,6 +1,7 @@ #ifndef WILLOW_INCLUDE_IR_CONSTANT_H #define WILLOW_INCLUDE_IR_CONSTANT_H +#include #include namespace willow { @@ -89,4 +90,19 @@ 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(&c)->getSExtVal(); + } + + std::unreachable(); +} + #endif // WILLOW_INCLUDE_IR_CONSTANT_H diff --git a/willow/include/willow/IR/Context.h b/willow/include/willow/IR/Context.h index 3f4f2ba..eda0241 100644 --- a/willow/include/willow/IR/Context.h +++ b/willow/include/willow/IR/Context.h @@ -17,6 +17,13 @@ class WillowContext { public: TypeContext &types() { return typectx; } ConstantPool &constants() { return constantpool; } + + template + [[nodiscard]] + Module *addModule(Args&&...args) { + modules.push_back(std::make_unique(std::forward(args)...)); + return modules.back().get(); + } }; } // namespace willow diff --git a/willow/include/willow/IR/Function.h b/willow/include/willow/IR/Function.h index 4be4de7..43a301b 100644 --- a/willow/include/willow/IR/Function.h +++ b/willow/include/willow/IR/Function.h @@ -38,6 +38,9 @@ public: : Value(ValueKind::Function, std::move(name), fty), parent(parent), params(std::move(params)) {} + Function(std::string name, Module *parent, Type fty) + : Value(ValueKind::Function, std::move(name), fty), parent(parent) {} + /// \return Parent module or nullptr. Module *getParent() { return parent; } const Module *getParent() const { return parent; } @@ -112,14 +115,14 @@ public: } }; -const BasicBlock *Function::entryBlock() const { +inline const BasicBlock *Function::entryBlock() const { if (blocks.empty()) return nullptr; else return blocks.front().get(); } -BasicBlock *Function::entryBlock() { +inline BasicBlock *Function::entryBlock() { if (blocks.empty()) return nullptr; else diff --git a/willow/include/willow/IR/IRBuilder.h b/willow/include/willow/IR/IRBuilder.h index 635c41b..6036e33 100644 --- a/willow/include/willow/IR/IRBuilder.h +++ b/willow/include/willow/IR/IRBuilder.h @@ -1,6 +1,7 @@ #ifndef WILLOW_INCLUDE_IR_IR_BUILDER_H #define WILLOW_INCLUDE_IR_IR_BUILDER_H +#include #include #include #include @@ -9,6 +10,8 @@ namespace willow { /// Helper for constructing and modifiying IR. class IRBuilder { + WillowContext &ctx; + const Module &mod; BasicBlock *block = nullptr; public: diff --git a/willow/include/willow/IR/Instruction.h b/willow/include/willow/IR/Instruction.h index a74c409..1198546 100644 --- a/willow/include/willow/IR/Instruction.h +++ b/willow/include/willow/IR/Instruction.h @@ -25,7 +25,11 @@ class Function; class Successors { friend class Instruction; std::array data; - uint8_t n = 0; + uint8_t n; + + Successors() : data{}, n{0} {} + explicit Successors(BasicBlock *a) : data{a}, n{1} {} + Successors(BasicBlock *a, BasicBlock *b) : data{a, b}, n{2} {} public: auto begin() { return data.data(); } @@ -198,6 +202,8 @@ constexpr std::string_view Instruction::opcodeName(Instruction::Opcode op) { case Alloca: return "alloca"; } + + std::unreachable(); } } // namespace willow @@ -212,11 +218,19 @@ struct std::formatter { } }; -// std::ostream& operator<<(std::ostream &os, const willow::Instruction &inst) { -// auto vty = inst.getType(); -// -// // int add %i % -// os << vty << " " << inst.opcode() << " " -// } +inline std::ostream& operator<<(std::ostream &os, const willow::Instruction::Opcode op) { + return os << willow::Instruction::opcodeName(op); +} + +inline std::ostream& operator<<(std::ostream &os, const willow::Instruction &inst) { + auto vty = inst.getType(); + + os << vty << " " << willow::Instruction::opcodeName(inst.opcode()); + + for (auto *operand : inst.getOperands()) + os << " " << operand; + + return os; +} #endif // WILLOW_INCLUDE_IR_INSTRUCTION_H diff --git a/willow/include/willow/IR/Location.h b/willow/include/willow/IR/Location.h index e0ce838..c3c241d 100644 --- a/willow/include/willow/IR/Location.h +++ b/willow/include/willow/IR/Location.h @@ -25,7 +25,7 @@ struct std::formatter { } }; -std::ostream &operator<<(std::ostream &os, const willow::Location &loc) { +inline std::ostream &operator<<(std::ostream &os, const willow::Location &loc) { return os << std::format("{}", loc); } diff --git a/willow/include/willow/IR/Types.h b/willow/include/willow/IR/Types.h index 9a4f868..40bb098 100644 --- a/willow/include/willow/IR/Types.h +++ b/willow/include/willow/IR/Types.h @@ -4,6 +4,7 @@ #include #include #include +#include #include @@ -118,23 +119,25 @@ public: }; constexpr std::string_view primitiveTypeName(TypeID tid) { + using namespace std::string_view_literals; using enum TypeID; switch (tid) { case TypeID::Void: - return "void"; + return "void"sv; case TypeID::BasicBlock: - return "label"; + return "label"sv; case TypeID::Int: - return "int"; + return "int"sv; case TypeID::Function: - return "function"; + return "function"sv; case TypeID::Ptr: - return "ptr"; + return "ptr"sv; case TypeID::Struct: - return "struct"; + return "struct"sv; case TypeID::Vector: - return "vector"; + return "vector"sv; } + std::unreachable(); } class BasicBlockTypeImpl : public TypeImpl { @@ -162,10 +165,10 @@ public: struct Hash { size_t operator()(const Key &k) const noexcept { std::size_t seed = 0; - willow::hashing::combine(seed, k.ret); + willow::hashing::combine(seed, k.ret.getImpl()); willow::hashing::combine(seed, k.params.size()); for (const auto &ty : k.params) - willow::hashing::combine(seed, ty); + willow::hashing::combine(seed, ty.getImpl()); return seed; } @@ -204,7 +207,7 @@ struct std::formatter { } }; -std::ostream &operator<<(std::ostream &os, willow::Type ty) { +inline std::ostream &operator<<(std::ostream &os, willow::Type ty) { return os << std::format("{}", ty); } diff --git a/willow/include/willow/IR/Value.h b/willow/include/willow/IR/Value.h index c219788..650e773 100644 --- a/willow/include/willow/IR/Value.h +++ b/willow/include/willow/IR/Value.h @@ -7,11 +7,13 @@ #include #include #include +#include namespace willow { class Instruction; class BasicBlock; +class Constant; enum class ValueKind { Instruction, ///< the identified result of an instruction @@ -82,4 +84,6 @@ public: } // namespace willow +inline std::ostream &operator<<(std::ostream &os, const willow::Value &v); + #endif // WILLOW_INCLUDE_IR_VALUE_H -- cgit v1.2.3