From af3d0ad1926eb825f64152cf217fc9a4777f0be3 Mon Sep 17 00:00:00 2001 From: Stefan Weigl-Bosker Date: Thu, 19 Feb 2026 18:45:44 -0500 Subject: [willow]: more cleanup, tests --- willow/lib/IR/BasicBlock.cpp | 54 ++++++++++++++++++++++++++++++++ willow/lib/IR/Constant.cpp | 53 +++++++++++++++++++++++++++++++ willow/lib/IR/ConstantPool.cpp | 26 ++++++++++++++++ willow/lib/IR/Diagnostic.cpp | 10 ++++++ willow/lib/IR/DiagnosticEngine.cpp | 28 +++++++++++++++++ willow/lib/IR/Function.cpp | 26 ++++++++++++++++ willow/lib/IR/IRBuilder.cpp | 52 +++++++++++++++---------------- willow/lib/IR/Instruction.cpp | 12 +++++++ willow/lib/IR/Instructions.cpp | 64 ++++++++++++++++++++++++++++++++++++++ willow/lib/IR/Value.cpp | 50 ++++++++++++++--------------- willow/lib/IR/Verifier.cpp | 10 ++++-- 11 files changed, 329 insertions(+), 56 deletions(-) create mode 100644 willow/lib/IR/BasicBlock.cpp create mode 100644 willow/lib/IR/Constant.cpp create mode 100644 willow/lib/IR/ConstantPool.cpp create mode 100644 willow/lib/IR/Diagnostic.cpp create mode 100644 willow/lib/IR/DiagnosticEngine.cpp create mode 100644 willow/lib/IR/Function.cpp create mode 100644 willow/lib/IR/Instructions.cpp (limited to 'willow/lib/IR') diff --git a/willow/lib/IR/BasicBlock.cpp b/willow/lib/IR/BasicBlock.cpp new file mode 100644 index 0000000..ceb4653 --- /dev/null +++ b/willow/lib/IR/BasicBlock.cpp @@ -0,0 +1,54 @@ +#include + +namespace willow { + +void BasicBlock::push_back(Instruction &inst) { + assert(!inst.hasParent() && "Instruction is already parented"); + body.push_back(inst); + inst.setParent(this); +} + +void BasicBlock::push_front(Instruction &inst) { + assert(!inst.hasParent() && "Instruction is already parented"); + body.push_front(inst); + inst.setParent(this); +} + +BasicBlock::Iterator BasicBlock::insert(Iterator pos, Instruction &inst) { + assert(!inst.hasParent() && "Instruction is already parented"); + auto it = body.insert(pos, inst); + inst.setParent(this); + return it; +} + +BasicBlock::Iterator BasicBlock::erase(BasicBlock::Iterator pos) { + Instruction &I = *pos; + I.setParent(nullptr); + return body.erase(pos); +} + +BasicBlock::Iterator BasicBlock::eraseAndDelete(BasicBlock::Iterator pos) { + Instruction &inst = *pos; + pos->setParent(nullptr); + auto it = body.erase(pos); + delete &inst; + return it; +} + +void BasicBlock::addPred(BasicBlock *bb) { + auto [it, inserted] = predecessors.try_emplace(bb, 1); + + if (!inserted) + it->second += 1; +} + +void BasicBlock::delPred(BasicBlock *bb) { + auto it = preds().find(bb); + + it->second -= 1; + + if (it->second <= 0) + preds().erase(it); +} + +} // namespace willow diff --git a/willow/lib/IR/Constant.cpp b/willow/lib/IR/Constant.cpp new file mode 100644 index 0000000..b9c15c7 --- /dev/null +++ b/willow/lib/IR/Constant.cpp @@ -0,0 +1,53 @@ +#include +#include +#include +#include + +namespace willow { + +ConstantInt::ConstantInt(Type ty, uint64_t val) + : Constant(ty, ConstantKind::Int) { + const size_t w = ty.getNumBits(); + assert(w <= 64 && "Come back when im less lazy"); + // assert(!(val >> w) && "Truncated constant"); + + if (w == 64) + bits = val; + else { + const uint64_t m = (uint64_t{1} << w) - 1; + bits = val & m; + } +} + +int64_t ConstantInt::getSExtVal() const { + const size_t w = getType().getNumBits(); + + if (w == 64) + return static_cast(bits); + + unsigned sh = 64 - w; + return (static_cast(bits << sh)) >> sh; +} + +size_t ConstantInt::Hash::operator()(const ConstantInt::Key &k) const noexcept { + auto h1 = std::hash{}(k.ty); + auto h2 = std::hash{}(k.bits); + + return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2)); +} + +} // namespace willow + +// TODO +std::ostream &operator<<(std::ostream &os, const willow::Constant &c) { + if (c.isPoison()) + return os << "poison"; + + if (c.isInt()) { + return os << static_cast(&c)->getSExtVal(); + } + + std::unreachable(); + + return os; +} diff --git a/willow/lib/IR/ConstantPool.cpp b/willow/lib/IR/ConstantPool.cpp new file mode 100644 index 0000000..d880913 --- /dev/null +++ b/willow/lib/IR/ConstantPool.cpp @@ -0,0 +1,26 @@ +#include + +#include + +namespace willow { + +ConstantInt *ConstantPool::getInt(Type ty, uint64_t val) { + assert(ty.isInt() && "Expected integer type"); + ConstantInt::Key &&k{ty.getImpl(), ty.getNumBits()}; + std::lock_guard lock(int_mutex); + + auto [it, _] = icache.try_emplace(k, std::make_unique(ty, val)); + + return it->second.get(); +} + +PoisonVal *ConstantPool::getPoisonVal(Type ty) { + std::lock_guard lock(poison_mutex); + + auto [it, _] = + pcache.try_emplace(ty.getImpl(), std::make_unique(ty)); + + return it->second.get(); +} + +} diff --git a/willow/lib/IR/Diagnostic.cpp b/willow/lib/IR/Diagnostic.cpp new file mode 100644 index 0000000..0e2c8bd --- /dev/null +++ b/willow/lib/IR/Diagnostic.cpp @@ -0,0 +1,10 @@ +#include +#include + +//TODO +std::ostream &operator<<(std::ostream &os, const willow::Diagnostic &diagnostic) { + if (diagnostic.location) + return os << diagnostic.location.value() << ": " << diagnostic.message; + else + return os << ": " << diagnostic.message; +} diff --git a/willow/lib/IR/DiagnosticEngine.cpp b/willow/lib/IR/DiagnosticEngine.cpp new file mode 100644 index 0000000..f0cc280 --- /dev/null +++ b/willow/lib/IR/DiagnosticEngine.cpp @@ -0,0 +1,28 @@ +#include + +namespace willow { + +void DiagnosticEngine::report(Diagnostic d) { + if (handler) + handler(std::move(d)); +} + +DiagnosticBuilder::DiagnosticBuilder(DiagnosticBuilder &&other) noexcept + : engine(std::exchange(other.engine, nullptr)), diag(std::move(other.diag)), + os(std::move(other.os)) {} +DiagnosticBuilder::~DiagnosticBuilder() { + if (!engine) // was moved from + return; + + diag.message += os.str(); + engine->report(std::move(diag)); +} + +DiagnosticBuilder::DiagnosticBuilder(DiagnosticEngine &eng, Severity severity, + std::optional loc) + : engine(&eng) { + diag.severity = severity; + diag.location = loc; +} + +} // namespace willow diff --git a/willow/lib/IR/Function.cpp b/willow/lib/IR/Function.cpp new file mode 100644 index 0000000..500d917 --- /dev/null +++ b/willow/lib/IR/Function.cpp @@ -0,0 +1,26 @@ +#include + +namespace willow { + +BasicBlock *Function::addBlock(std::unique_ptr block) { + auto p = block.get(); + blocks.push_back(std::move(block)); + p->setParent(this); + return p; +} + +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 diff --git a/willow/lib/IR/IRBuilder.cpp b/willow/lib/IR/IRBuilder.cpp index 62e7a98..ab62082 100644 --- a/willow/lib/IR/IRBuilder.cpp +++ b/willow/lib/IR/IRBuilder.cpp @@ -2,7 +2,7 @@ namespace willow { -AddInst *IRBuilder::BuildAdd(Type type, Value *lhs, Value *rhs, +AddInst *IRBuilder::buildAdd(Type type, Value *lhs, Value *rhs, std::optional loc) { auto *inst = new AddInst{type, lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -11,7 +11,7 @@ AddInst *IRBuilder::BuildAdd(Type type, Value *lhs, Value *rhs, return inst; } -MulInst *IRBuilder::BuildMul(Type type, Value *lhs, Value *rhs, +MulInst *IRBuilder::buildMul(Type type, Value *lhs, Value *rhs, std::optional loc) { auto *inst = new MulInst{type, lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -20,7 +20,7 @@ MulInst *IRBuilder::BuildMul(Type type, Value *lhs, Value *rhs, return inst; } -SubInst *IRBuilder::BuildSub(Type type, Value *lhs, Value *rhs, +SubInst *IRBuilder::buildSub(Type type, Value *lhs, Value *rhs, std::optional loc) { auto *inst = new SubInst{type, lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -29,7 +29,7 @@ SubInst *IRBuilder::BuildSub(Type type, Value *lhs, Value *rhs, return inst; } -DivInst *IRBuilder::BuildDiv(Type type, Value *lhs, Value *rhs, +DivInst *IRBuilder::buildDiv(Type type, Value *lhs, Value *rhs, std::optional loc) { auto *inst = new DivInst{type, lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -38,7 +38,7 @@ DivInst *IRBuilder::BuildDiv(Type type, Value *lhs, Value *rhs, return inst; } -ModInst *IRBuilder::BuildMod(Type type, Value *lhs, Value *rhs, +ModInst *IRBuilder::buildMod(Type type, Value *lhs, Value *rhs, std::optional loc) { auto *inst = new ModInst{type, lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -47,7 +47,7 @@ ModInst *IRBuilder::BuildMod(Type type, Value *lhs, Value *rhs, return inst; } -ShlInst *IRBuilder::BuildShl(Type type, Value *lhs, Value *rhs, +ShlInst *IRBuilder::buildShl(Type type, Value *lhs, Value *rhs, std::optional loc) { auto *inst = new ShlInst{type, lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -56,7 +56,7 @@ ShlInst *IRBuilder::BuildShl(Type type, Value *lhs, Value *rhs, return inst; } -ShrInst *IRBuilder::BuildShr(Type type, Value *lhs, Value *rhs, +ShrInst *IRBuilder::buildShr(Type type, Value *lhs, Value *rhs, std::optional loc) { auto *inst = new ShrInst{type, lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -65,7 +65,7 @@ ShrInst *IRBuilder::BuildShr(Type type, Value *lhs, Value *rhs, return inst; } -AshlInst *IRBuilder::BuildAshl(Type type, Value *lhs, Value *rhs, +AshlInst *IRBuilder::buildAshl(Type type, Value *lhs, Value *rhs, std::optional loc) { auto *inst = new AshlInst{type, lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -74,7 +74,7 @@ AshlInst *IRBuilder::BuildAshl(Type type, Value *lhs, Value *rhs, return inst; } -AshrInst *IRBuilder::BuildAshr(Type type, Value *lhs, Value *rhs, +AshrInst *IRBuilder::buildAshr(Type type, Value *lhs, Value *rhs, std::optional loc) { auto *inst = new AshrInst{type, lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -83,7 +83,7 @@ AshrInst *IRBuilder::BuildAshr(Type type, Value *lhs, Value *rhs, return inst; } -EqInst *IRBuilder::BuildEq(Value *lhs, Value *rhs, +EqInst *IRBuilder::buildEq(Value *lhs, Value *rhs, std::optional loc) { auto *inst = new EqInst{ctx.types().IntType(1), lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -92,7 +92,7 @@ EqInst *IRBuilder::BuildEq(Value *lhs, Value *rhs, return inst; } -LtInst *IRBuilder::BuildLt(Value *lhs, Value *rhs, +LtInst *IRBuilder::buildLt(Value *lhs, Value *rhs, std::optional loc) { auto *inst = new LtInst{ctx.types().IntType(1), lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -101,7 +101,7 @@ LtInst *IRBuilder::BuildLt(Value *lhs, Value *rhs, return inst; } -GtInst *IRBuilder::BuildGt(Value *lhs, Value *rhs, +GtInst *IRBuilder::buildGt(Value *lhs, Value *rhs, std::optional loc) { auto *inst = new GtInst{ctx.types().IntType(1), lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -110,7 +110,7 @@ GtInst *IRBuilder::BuildGt(Value *lhs, Value *rhs, return inst; } -LeInst *IRBuilder::BuildLe(Value *lhs, Value *rhs, +LeInst *IRBuilder::buildLe(Value *lhs, Value *rhs, std::optional loc) { auto *inst = new LeInst{ctx.types().IntType(1), lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -119,7 +119,7 @@ LeInst *IRBuilder::BuildLe(Value *lhs, Value *rhs, return inst; } -GeInst *IRBuilder::BuildGe(Value *lhs, Value *rhs, +GeInst *IRBuilder::buildGe(Value *lhs, Value *rhs, std::optional loc) { auto *inst = new GeInst{ctx.types().IntType(1), lhs, rhs, loc}; insert_point->insertAfter(*inst); @@ -128,33 +128,33 @@ GeInst *IRBuilder::BuildGe(Value *lhs, Value *rhs, return inst; } -AndInst *IRBuilder::BuildAnd(Value *lhs, Value *rhs, +AndInst *IRBuilder::buildAnd(Type type, Value *lhs, Value *rhs, std::optional loc) { - auto *inst = new AndInst{ctx.types().IntType(1), lhs, rhs, loc}; + auto *inst = new AndInst{type, lhs, rhs, loc}; insert_point->insertAfter(*inst); insert_point++; return inst; } -OrInst *IRBuilder::BuildOr(Value *lhs, Value *rhs, +OrInst *IRBuilder::buildOr(Type type, Value *lhs, Value *rhs, std::optional loc) { - auto *inst = new OrInst{ctx.types().IntType(1), lhs, rhs, loc}; + auto *inst = new OrInst{type, lhs, rhs, loc}; insert_point->insertAfter(*inst); insert_point++; return inst; } -NotInst *IRBuilder::BuildNot(Value *val, std::optional loc) { - auto *inst = new NotInst{ctx.types().IntType(1), val, loc}; +NotInst *IRBuilder::buildNot(Type type, Value *val, std::optional loc) { + auto *inst = new NotInst{type, val, loc}; insert_point->insertAfter(*inst); insert_point++; return inst; } -JmpInst *IRBuilder::BuildJmp(BasicBlock *dst, std::optional loc) { +JmpInst *IRBuilder::buildJmp(BasicBlock *dst, std::optional loc) { auto *inst = new JmpInst{ctx.types().VoidType(), dst, loc}; insert_point->insertAfter(*inst); @@ -163,7 +163,7 @@ JmpInst *IRBuilder::BuildJmp(BasicBlock *dst, std::optional loc) { return inst; } -BrInst *IRBuilder::BuildBr(Value *predicate, BasicBlock *truedst, +BrInst *IRBuilder::buildBr(Value *predicate, BasicBlock *truedst, BasicBlock *falsedst, std::optional loc) { auto *inst = new BrInst{ctx.types().VoidType(), predicate, truedst, falsedst, loc}; @@ -173,14 +173,14 @@ BrInst *IRBuilder::BuildBr(Value *predicate, BasicBlock *truedst, return inst; } -RetInst *IRBuilder::BuildRet(Value *val, std::optional loc) { +RetInst *IRBuilder::buildRet(Value *val, std::optional loc) { auto *inst = new RetInst{ctx.types().VoidType(), val, loc}; insert_point->insertAfter(*inst); insert_point++; return inst; } -RetInst *IRBuilder::BuildRet(std::optional loc) { +RetInst *IRBuilder::buildRet(std::optional loc) { auto *inst = new RetInst{ctx.types().VoidType(), loc}; insert_point->insertAfter(*inst); insert_point++; @@ -188,7 +188,7 @@ RetInst *IRBuilder::BuildRet(std::optional loc) { return inst; } -PhiInst *IRBuilder::BuildPhi( +PhiInst *IRBuilder::buildPhi( Type ty, std::initializer_list> args, std::optional loc) { auto *inst = new PhiInst(ty, args, loc); @@ -198,7 +198,7 @@ PhiInst *IRBuilder::BuildPhi( return inst; } -AllocaInst *IRBuilder::BuildAlloca(Type ty, std::optional loc) { +AllocaInst *IRBuilder::buildAlloca(Type ty, std::optional loc) { Type pty = ctx.types().PtrType(ty); auto *inst = new AllocaInst(pty, loc); insert_point->insertAfter(*inst); diff --git a/willow/lib/IR/Instruction.cpp b/willow/lib/IR/Instruction.cpp index a6e0c9b..517b6f9 100644 --- a/willow/lib/IR/Instruction.cpp +++ b/willow/lib/IR/Instruction.cpp @@ -34,6 +34,18 @@ bool Instruction::isTerminatorOp(Opcode op) { } } +void Instruction::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); +} + Successors Instruction::succs() { using enum Opcode; switch (op) { diff --git a/willow/lib/IR/Instructions.cpp b/willow/lib/IR/Instructions.cpp new file mode 100644 index 0000000..15e6786 --- /dev/null +++ b/willow/lib/IR/Instructions.cpp @@ -0,0 +1,64 @@ +#include + +namespace willow { + +UnaryInst::UnaryInst(Opcode op, Type type, Value *value, + std::optional loc) + : Instruction(op, type, loc) { + addOperand(value); +} + +BinaryInst::BinaryInst(Opcode op, Type type, Value *lhs, Value *rhs, + std::optional loc) + : Instruction(op, type, loc) { + addOperand(lhs); + addOperand(rhs); +} + +BrInst::BrInst(Type type, Value *condition, BasicBlock *true_target, + BasicBlock *false_target, std::optional loc) + : Instruction(Opcode::Br, type, loc) { + addOperand(condition); + addOperand(true_target); + addOperand(false_target); +} + +Value *BrInst::getCondition() { return getOperand(0); } + +const Value *BrInst::getCondition() const { return getOperand(0); } + +BasicBlock *BrInst::getTrueTarget() { + return static_cast(getOperand(1)); +} + +const BasicBlock *BrInst::getTrueTarget() const { + return static_cast(getOperand(1)); +} + +BasicBlock *BrInst::getFalseTarget() { + return static_cast(getOperand(2)); +} + +const BasicBlock *BrInst::getFalseTarget() const { + return static_cast(getOperand(2)); +} + +RetInst::RetInst(Type voidty, std::optional loc) + : Instruction(Opcode::Ret, voidty, loc) {} + +RetInst::RetInst(Type voidty, Value *val, std::optional loc) + : Instruction(Opcode::Ret, voidty, loc) { + addOperand(val); +} + +PhiInst::PhiInst(Type type, + std::initializer_list> args, + std::optional loc) + : Instruction(Opcode::Phi, type, loc) { + for (auto [bb, v] : args) { + addOperand(static_cast(bb)); + addOperand(v); + } +} + +} // namespace willow diff --git a/willow/lib/IR/Value.cpp b/willow/lib/IR/Value.cpp index 0bd1079..703e807 100644 --- a/willow/lib/IR/Value.cpp +++ b/willow/lib/IR/Value.cpp @@ -1,27 +1,23 @@ -// #include -// #include -// #include -// -// std::ostream &operator<<(std::ostream &os, const willow::Value &v) { -// using willow::ValueKind; -// auto ty = v.getType(); -// if (!v.isVoid()) -// os << ty << " "; -// -// switch (v.getValueKind()) { -// case ValueKind::Parameter: -// [[fallthrough]]; -// case ValueKind::Instruction: { -// return os << "%" << v.getName(); -// } -// case ValueKind::BasicBlock: { -// return os << "^" << v.getName(); -// } -// case ValueKind::Function: { -// return os << "@" << v.getName(); -// } -// case ValueKind::Constant: { -// return os << *static_cast(&v); -// } -// } -// } +#include +#include + +#include + +namespace willow { + +void Value::addUse(Instruction *instruction) { + auto [it, inserted] = uses.try_emplace(instruction, 1); + + if (!inserted) + it->second += 1; +} + +void Value::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); +} + +} // namespace willow diff --git a/willow/lib/IR/Verifier.cpp b/willow/lib/IR/Verifier.cpp index b622f10..125f7bc 100644 --- a/willow/lib/IR/Verifier.cpp +++ b/willow/lib/IR/Verifier.cpp @@ -8,6 +8,7 @@ namespace willow { +namespace { /// Verify that an instruction defines an SSA result LogicalResult verifyResult(const Instruction &inst, DiagnosticEngine &diags); /// Verify that an instruction does not define an ssa result @@ -18,9 +19,9 @@ LogicalResult verifyNumOperands(const Instruction &inst, DiagnosticEngine &diags, std::size_t expected); /// Verify operand type -LogicalResult expectOperandType(const Instruction &inst, - DiagnosticEngine &diags, std::size_t opidx, - Type expected); +// LogicalResult expectOperandType(const Instruction &inst, +// DiagnosticEngine &diags, std::size_t opidx, +// Type expected); LogicalResult expectOperandType(const Instruction &inst, DiagnosticEngine &diags, const Value *operand, Type expected); @@ -31,6 +32,7 @@ LogicalResult expectResultType(const Instruction &inst, DiagnosticEngine &diags, LogicalResult verifyBinaryIntegerInst(const Instruction &, DiagnosticEngine &); LogicalResult verifyBinaryIntegerCmp(WillowContext &ctx, const Instruction &, DiagnosticEngine &); +} LogicalResult verifyModule(WillowContext &ctx, const Module &module, DiagnosticEngine &diags) { @@ -282,6 +284,7 @@ LogicalResult verifyInst(WillowContext &ctx, const Instruction &inst, return success(); } +namespace { LogicalResult verifyBinaryIntegerInst(const Instruction &inst, DiagnosticEngine &diags) { Type ty = inst.getType(); @@ -402,5 +405,6 @@ LogicalResult expectResultType(const Instruction &inst, DiagnosticEngine &diags, return emit(diags, Severity::Error) << std::format( "unexpected result type: expected '{}', found '{}'", expected, ty); } +} } // namespace willow -- cgit v1.2.3