From ad744d11a70136459256f28380ec99c9274fb77d Mon Sep 17 00:00:00 2001 From: Stefan Weigl-Bosker Date: Mon, 12 Jan 2026 20:04:04 -0500 Subject: [willow]: verifier work (#3) --- willow/lib/IR/Instruction.cpp | 2 + willow/lib/IR/Verifier.cpp | 181 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 183 insertions(+) create mode 100644 willow/lib/IR/Verifier.cpp (limited to 'willow/lib') diff --git a/willow/lib/IR/Instruction.cpp b/willow/lib/IR/Instruction.cpp index 21a4cae..a61cd55 100644 --- a/willow/lib/IR/Instruction.cpp +++ b/willow/lib/IR/Instruction.cpp @@ -1 +1,3 @@ #include + +namespace willow {}; diff --git a/willow/lib/IR/Verifier.cpp b/willow/lib/IR/Verifier.cpp new file mode 100644 index 0000000..b692b2f --- /dev/null +++ b/willow/lib/IR/Verifier.cpp @@ -0,0 +1,181 @@ +#include +#include +#include +#include +#include + +namespace willow { + +/// Verify that an instruction defines an SSA result +LogicalResult verifyResult(const Instruction &inst, DiagnosticEngine &diags); + +LogicalResult verifyNumOperands(const Instruction &inst, + DiagnosticEngine &diags, std::size_t expected); + +LogicalResult verifyModule(const Module &module, DiagnosticEngine &diags) { + bool any_failure = false; + + for (auto &func : module.getFunctions()) { + std::vector collected; + DiagnosticEngine eng( + [&](Diagnostic d) { collected.push_back(std::move(d)); }); + + auto r = verifyFunction(func, eng); + + if (succeeded(r)) + continue; + + any_failure = true; + + auto diag = emit(diags, Severity::Error, std::nullopt); + diag << "verification failed for function: '" << func.getName() << "'"; + + for (auto &d : collected) + diag.note(std::move(d)); + } + + return any_failure ? failure() : success(); +} + +// LogicalResult verifyFunction(const Function&function, DiagnosticEngine +// &diags) { +// bool any_failure = false; +// } + +LogicalResult verifyBasicBlock(const BasicBlock &BB, DiagnosticEngine &diags) { + bool any_failure = false; + + if (BB.empty()) + return emit(diags, Severity::Error, BB.getLoc()) + << "Basic block '" << BB.getName() << "' has an empty body"; + + auto *trailer = BB.trailer(); + + if (!trailer->isTerminator()) { + } + + if (!BB.trailer()->isTerminator()) + // TODO: terminator check + + for (auto &inst : BB.getBody()) { + // verify inst + } +} + +// TODO: better instruction printing +LogicalResult verifyInst(const Instruction &inst, DiagnosticEngine &diags) { + using enum Instruction::Opcode; + switch (inst.opcode()) { + case Add: + case Mul: + case Sub: + case Div: + case Mod: + case Shl: + case Shr: + case Ashl: + case Ashr: + case And: + case Or: + return verifyBinaryInst(inst, diags); + case Eq: + case Lt: + case Gt: + case Le: + case Ge: { + Type ty = inst.getType(); + if (!ty.isInt() || ty.getNumBits() != 1) + return emit(diags, Severity::Error, inst.getLoc()) + << std::format("unexpected result type '{}': compare " + "instructions return i1", + ty); + + size_t num_operands = inst.getNumOperands(); + if (num_operands != 2) + return emit(diags, Severity::Error, inst.getLoc()) + << std::format("expected 2 operands, found {}", num_operands); + + const Value *lhs = inst.getOperand(0); + const Value *rhs = inst.getOperand(1); + + Type lty = lhs->getType(), rty = rhs->getType(); + + if (!lty.isInt()) + return emit(diags, Severity::Error, inst.getLoc()) << std::format( + "invalid operand type '{}': expected integral type", lty); + + if (!rty.isInt()) + return emit(diags, Severity::Error, inst.getLoc()) << std::format( + "invalid operand type '{}': expected integral type", rty); + + if (lty != rty) + return emit(diags, Severity::Error, inst.getLoc()) + << "mismatched operand types"; + } + case Not: { + Type ty = inst.getType(); + + if (failed(verifyResult(inst, diags))) + return failure(); + + const Value *operand = inst.getOperand(0); + if (!operand) + return emit(diags, Severity::Error, inst.getLoc()) + << "instruction 'not' requires 1 operand"; + + Type oty = operand->getType(); + if (ty != oty) + return emit(diags, Severity::Error, inst.getLoc()) + << std::format("expected argument type '{}', got '{}'", ty, oty); + } + case Jmp: + case Br: + case Call: + case Ret: + case Phi: + case Alloca: + } +} + +// TODO: better naming? +LogicalResult verifyBinaryInst(const Instruction &inst, + DiagnosticEngine &diags) { + Type ty = inst.getType(); + + // TODO non scalars + if (!ty.isInt()) + return emit(diags, Severity::Error, inst.getLoc()) + << "invalid instruction '" << inst << "': " + << "expected an integral type, got '" << ty << "'"; + + auto *lhs = inst.getOperand(0); + auto *rhs = inst.getOperand(1); + + assert(lhs && "Binary op lacks LHS"); + assert(rhs && "Binary op needs RHS"); + + if (lhs->getType() != ty) { + return emit(diags, Severity::Error, inst.getLoc()) << std::format( + "expected operand type '{}' got '{}'", ty, lhs->getType()); + } + + if (rhs->getType() != ty) { + return emit(diags, Severity::Error, inst.getLoc()) << std::format( + "expected operand type '{}' got '{}'", ty, rhs->getType()); + } +} + +LogicalResult verifyResult(const Instruction &inst, DiagnosticEngine &diags) { + if (inst.hasName()) + return success(); + + return emit(diags, Severity::Error, inst.getLoc()) << "expected ssa result"; +} + +LogicalResult verifyNumOperands(const Instruction &inst, + DiagnosticEngine &diags, std::size_t expected) { + if (inst.getNumOperands() != expected) + return emitE +} + +} // namespace willow -- cgit v1.2.3