From 3a57627e59ba18b6f9f9aae7bb60c390c0d3575a Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sun, 9 Aug 2026 22:05:14 +0800 Subject: [MC] Implement RV64GC object emission --- backend/lib/MC/MCFixup.cpp | 177 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 177 insertions(+) create mode 100644 backend/lib/MC/MCFixup.cpp (limited to 'backend/lib/MC/MCFixup.cpp') diff --git a/backend/lib/MC/MCFixup.cpp b/backend/lib/MC/MCFixup.cpp new file mode 100644 index 0000000..8819cd4 --- /dev/null +++ b/backend/lib/MC/MCFixup.cpp @@ -0,0 +1,177 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/MC/MCFixup.h" + +#include +#include +#include +#include +#include +#include + +namespace rcc::mc { +namespace { + +[[nodiscard]] Expected checkedAdd(std::int64_t Left, std::int64_t Right) { + std::int64_t Result = 0; + if (__builtin_add_overflow(Left, Right, &Result)) + return makeUnexpected(ErrorCode::RelocationFailed, "MC expression addition overflows"); + return Result; +} + +[[nodiscard]] Expected checkedSubtract(std::int64_t Left, std::int64_t Right) { + std::int64_t Result = 0; + if (__builtin_sub_overflow(Left, Right, &Result)) + return makeUnexpected(ErrorCode::RelocationFailed, "MC expression subtraction overflows"); + return Result; +} + +[[nodiscard]] Expected combineLinearValues(const MCValue &Left, const MCValue &Right, + bool SubtractRight) { + struct SymbolTerm final { + MCSymbolRef Symbol; + int Coefficient = 0; + }; + std::vector Terms; + const auto AddTerm = [&Terms](const MCSymbolRef &Symbol, int Coefficient) -> Expected { + if (!Symbol) + return {}; + const auto Position = std::ranges::find(Terms, Symbol, &SymbolTerm::Symbol); + if (Position == Terms.end()) { + Terms.push_back(SymbolTerm{.Symbol = Symbol, .Coefficient = Coefficient}); + return {}; + } + Position->Coefficient += Coefficient; + if (Position->Coefficient < -1 || Position->Coefficient > 1) { + return makeUnexpected(ErrorCode::RelocationFailed, + "MC expression has a symbol coefficient outside -1 to 1"); + } + if (Position->Coefficient == 0) + Terms.erase(Position); + return {}; + }; + + for (const auto &[Symbol, Coefficient] : std::array, 4>{ + std::pair{Left.AddSymbol, 1}, + std::pair{Left.SubtractSymbol, -1}, + std::pair{Right.AddSymbol, SubtractRight ? -1 : 1}, + std::pair{Right.SubtractSymbol, SubtractRight ? 1 : -1}, + }) { + auto Added = AddTerm(Symbol, Coefficient); + if (!Added) + return std::unexpected(Added.error()); + } + + MCValue Result; + for (const SymbolTerm &Term : Terms) { + MCSymbolRef &Destination = Term.Coefficient > 0 ? Result.AddSymbol : Result.SubtractSymbol; + if (Destination) { + return makeUnexpected(ErrorCode::RelocationFailed, + "MC expression contains more than one symbol with the same sign"); + } + Destination = Term.Symbol; + } + auto Addend = SubtractRight ? checkedSubtract(Left.Addend, Right.Addend) + : checkedAdd(Left.Addend, Right.Addend); + if (!Addend) + return std::unexpected(Addend.error()); + Result.Addend = *Addend; + return Result; +} + +[[nodiscard]] Expected evaluate(const MCExpr &Expression, std::size_t Depth) { + if (Depth > 256) + return makeUnexpected(ErrorCode::RelocationFailed, "MC expression exceeds its depth limit"); + + switch (Expression.kind()) { + case MCExpr::Kind::Constant: + return MCValue{.AddSymbol = {}, + .SubtractSymbol = {}, + .Addend = *Expression.getIf(), + .TargetKind = 0}; + case MCExpr::Kind::SymbolRef: + return MCValue{.AddSymbol = Expression.getIf()->Symbol, + .SubtractSymbol = {}, + .Addend = 0, + .TargetKind = 0}; + case MCExpr::Kind::Target: { + const auto &Target = *Expression.getIf(); + auto Result = evaluate(*Target.Operand, Depth + 1); + if (!Result) + return std::unexpected(Result.error()); + if (Result->TargetKind != 0) { + return makeUnexpected(ErrorCode::RelocationFailed, + "nested target MC expressions are not relocatable"); + } + Result->TargetKind = Target.Kind; + return Result; + } + case MCExpr::Kind::Unary: { + const auto &Unary = *Expression.getIf(); + auto Operand = evaluate(*Unary.Operand, Depth + 1); + if (!Operand) + return std::unexpected(Operand.error()); + if (Unary.Operator == MCUnaryOperator::Plus) + return Operand; + if (Unary.Operator == MCUnaryOperator::Minus && Operand->isAbsolute()) { + if (Operand->Addend == std::numeric_limits::min()) { + return makeUnexpected(ErrorCode::RelocationFailed, "MC expression negation overflows"); + } + Operand->Addend = -Operand->Addend; + return Operand; + } + const auto Absolute = Expression.evaluateAbsolute(); + if (!Absolute) { + return makeUnexpected(ErrorCode::RelocationFailed, + "symbolic unary MC expression is not relocatable"); + } + return MCValue{.AddSymbol = {}, .SubtractSymbol = {}, .Addend = *Absolute, .TargetKind = 0}; + } + case MCExpr::Kind::Binary: { + const auto &Binary = *Expression.getIf(); + if (Binary.Operator != MCBinaryOperator::Add && Binary.Operator != MCBinaryOperator::Subtract) { + const auto Absolute = Expression.evaluateAbsolute(); + if (!Absolute) { + return makeUnexpected(ErrorCode::RelocationFailed, + "symbolic binary MC expression is not relocatable"); + } + return MCValue{.AddSymbol = {}, .SubtractSymbol = {}, .Addend = *Absolute, .TargetKind = 0}; + } + auto Left = evaluate(*Binary.Left, Depth + 1); + auto Right = evaluate(*Binary.Right, Depth + 1); + if (!Left) + return std::unexpected(Left.error()); + if (!Right) + return std::unexpected(Right.error()); + if (Left->TargetKind != 0 || Right->TargetKind != 0) { + return makeUnexpected(ErrorCode::RelocationFailed, + "target MC expression cannot participate in outer arithmetic"); + } + + return combineLinearValues(*Left, *Right, Binary.Operator == MCBinaryOperator::Subtract); + } + } + return makeUnexpected(ErrorCode::InternalError, "MC expression has an invalid kind"); +} + +} // namespace + +Expected MCFixup::verify() const { + if (Kind == fixup_kind::None) + return makeUnexpected(ErrorCode::InvalidArgument, "MC fixup has no kind"); + if (!Value) + return makeUnexpected(ErrorCode::InvalidArgument, "MC fixup has no value expression"); + auto Verification = Value->verify(); + if (!Verification) + return std::unexpected(Verification.error()); + return {}; +} + +Expected evaluateAsRelocatable(const MCExpr &Expression) { + auto Verification = Expression.verify(); + if (!Verification) + return std::unexpected(Verification.error()); + return evaluate(Expression, 0); +} + +} // namespace rcc::mc -- cgit v1.2.3