[Assembler] Implement symbol resolution
MODIFY
src/assembler/assembler.h
src/assembler/assembler.h
@@ -48,6 +48,15 @@ class AssemblerBase {
using PseudoInstrMap = std::map<QString, std::shared_ptr<PseudoInstr>>;
using PseudoInstrVec = std::vector<std::shared_ptr<PseudoInstr>>;
+ struct LinkRequest {
+ unsigned sourceLine; // Source location of code which resulted in the link request
+ uint32_t offset; // Offset of instruction which needs link resolution
+
+ // Reference to the immediate field which resolves the symbol and the requested symbol
+ FieldLinkRequest fieldRequest;
+ };
+ using LinkRequests = std::vector<LinkRequest>;
+
public:
AssembleResult assemble(const QString& program) const {
const auto programLines = program.split(QRegExp("[\r\n]"));
@@ -63,12 +72,17 @@ public:
// Pseudo instruction expansion
runPass(expandedLines, Program, pass1, tokenizedLines);
- // Assemble & generate symbol map
+ /** Assemble. During assembly, we generate:
+ * - symbolMap: Recoding the offset locations in the program of lines adorned with symbols
+ * - linkageMap: Recording offsets of instructions which require linkage with symbols
+ */
SymbolMap symbolMap;
- runPass(program, QByteArray, pass2, expandedLines, symbolMap);
+ LinkRequests needsLinkage;
+ runPass(program, QByteArray, pass2, expandedLines, symbolMap, needsLinkage);
// Symbol linkage
- runPass(unused, NoPassResult, pass3, program, symbolMap);
+ runPass(unused, NoPassResult, pass3, program, symbolMap, needsLinkage);
+
result.program = program;
return result;
}
@@ -195,56 +209,80 @@ private:
/**
* @brief pass2
- * Record output address and symbol positions in expanded program. If @return errors is empty, pass succeeded.
+ * Machine code translation. If @return errors is empty, pass succeeded.
+ * In the following, current size of the program is used as an analog for the offset of the to-be-assembled
+ * instruction in the program. This is then used for symbol resolution.
*/
- std::variant<Errors, SymbolMap> pass2(Program& tokenizedLines) const {
+ std::variant<Errors, QByteArray> pass2(const Program& tokenizedLines, SymbolMap& symbolMap,
+ LinkRequests& needsLinkage) const {
+ QByteArray program;
Errors errors;
- SymbolMap sm;
-
- // Unless otherwise specified, start at instruction segment
- uint32_t address;
- try {
- address = m_segmentPointers.at(dataSegment());
- } catch (std::out_of_range const&) {
- errors.push_back(Error(-1, "No base address specified for segment: " + instrSegment()));
- return {errors};
+ for (const auto& line : tokenizedLines) {
+ const uint32_t instr_offset = program.size();
+ for (const auto& s : line.symbols) {
+ if (symbolMap.count(s) != 0) {
+ errors.push_back(Error(line.sourceLine, "Multiple definitions of symbol '" + s + "'"));
+ } else {
+ symbolMap[s] = instr_offset;
+ }
}
- for (auto& line : tokenizedLines) {
+ runOperation(directiveBytes, std::optional<QByteArray>, assembleDirective, line);
+ if (!directiveBytes) {
+ std::weak_ptr<Instr> assembledWith;
+ runOperation(machineCode, InstrRes, assembleInstruction, line, assembledWith);
+
+ if (!machineCode.linksWithSymbol.symbol.isEmpty()) {
+ LinkRequest req;
+ req.sourceLine = line.sourceLine;
+ req.offset = instr_offset;
+ req.fieldRequest = machineCode.linksWithSymbol;
+ needsLinkage.push_back(req);
}
+ program.append(
+ QByteArray(reinterpret_cast<char*>(&machineCode.instruction), sizeof(machineCode.instruction)));
+ } else {
+ program.append(directiveBytes.value());
+ }
+ }
if (errors.size() != 0) {
return {errors};
} else {
- return {sm};
+ return {program};
}
}
- /**
- * @brief pass2
- * Machine code translation. If @return errors is empty, pass succeeded.
- */
- std::variant<Errors, QByteArray> pass2(const Program& tokenizedLines, SymbolMap& symbolMap) const {
- QByteArray program;
+ std::variant<Errors, NoPassResult> pass3(QByteArray& program, const SymbolMap& symbolMap,
+ const LinkRequests& needsLinkage) const {
Errors errors;
- for (const auto& line : tokenizedLines) {
- runOperation(directiveBytes, std::optional<QByteArray>, assembleDirective, line);
- if (!directiveBytes) {
- runOperation(machineCode, uint32_t, assembleInstruction, line);
- program.append(QByteArray(reinterpret_cast<char*>(&machineCode), sizeof(machineCode)));
+ for (const auto& linkRequest : needsLinkage) {
+ const auto& symbol = linkRequest.fieldRequest.symbol;
+ if (symbolMap.count(symbol) == 0) {
+ errors.push_back(Error(linkRequest.sourceLine, "Unknown symbol '" + symbol + "'"));
+ continue;
+ }
+
+ // Decode instruction at link-request position
+ assert(program.size() <= (linkRequest.offset + 4) &&
+ "Error: position of link request is not within program");
+ uint32_t instr = *reinterpret_cast<uint32_t*>(program.data() + linkRequest.offset);
+
+ // Re-apply immediate resolution using the value acquired from the symbol map
+ if (auto* immField = dynamic_cast<const Imm*>(linkRequest.fieldRequest.field)) {
+ immField->applySymbolResolution(symbolMap.at(symbol), instr, linkRequest.offset);
} else {
- program.append(directiveBytes.value());
+ assert(false && "Something other than an immediate field has requested linkage?");
}
+
+ // Finally, overwrite the instruction in the program
+ *reinterpret_cast<uint32_t*>(program.data() + linkRequest.offset) = instr;
}
if (errors.size() != 0) {
return {errors};
} else {
- return {program};
- }
+ return {NoPassResult()};
}
-
- std::variant<Errors, NoPassResult> pass3(QByteArray& program, const SymbolMap& symbolMap) const {
- return NoPassResult();
}
protected:
@@ -286,7 +324,7 @@ protected:
return splitQuotes(line.split(splitter));
}
- virtual AssembleRes assembleInstruction(const TokenizedSrcLine& line) const {
+ virtual AssembleRes assembleInstruction(const TokenizedSrcLine& line, std::weak_ptr<Instr>& assembledWith) const {
if (line.tokens.empty()) {
return {Error(line.sourceLine, "Empty source lines should be impossible at this point")};
}
@@ -294,6 +332,7 @@ protected:
if (m_instructionMap.count(opcode) == 0) {
return {Error(line.sourceLine, "Unknown opcode '" + opcode + "'")};
}
+ assembledWith = m_instructionMap.at(opcode);
return m_instructionMap.at(opcode)->assemble(line);
};
@@ -317,7 +356,12 @@ protected:
for (const auto& token : tokens) {
if (token.contains(':')) {
if (symbolStillAllowed) {
- symbols.insert(QString(token).remove(':'));
+ const QString cleanedSymbol = QString(token).remove(':');
+ if (symbols.count(cleanedSymbol) != 0) {
+ return Error(sourceLine, "Multiple definitions of symbol '" + cleanedSymbol + "'");
+ } else {
+ symbols.insert(cleanedSymbol);
+ }
} else {
return Error(sourceLine, "Stray ':' in line");
}

MODIFY
src/assembler/instruction.h
src/assembler/instruction.h
@@ -16,12 +16,6 @@ namespace Ripes {
namespace AssemblerTmp {
-namespace {
-using AssembleRes = std::variant<Error, uint32_t>;
-using PseudoExpandRes = std::variant<Error, std::optional<std::vector<AssemblerTmp::LineTokens>>>;
-using DisassembleRes = std::variant<Error, AssemblerTmp::LineTokens>;
-} // namespace
-
struct BitRange {
constexpr BitRange(unsigned _start, unsigned _stop, unsigned _N = 32) : start(_start), stop(_stop), N(_N) {
assert(isPowerOf2(_N) && "Bitrange N must be power of 2");
@@ -38,16 +32,35 @@ struct BitRange {
bool operator<(const BitRange& other) const { return this->start < other.start; }
};
+struct Field;
+struct FieldLinkRequest {
+ Field const* field = nullptr;
+ QString symbol = QString();
+};
+
struct Field {
Field() = default;
virtual ~Field() = default;
- virtual std::optional<AssemblerTmp::Error> apply(const AssemblerTmp::TokenizedSrcLine& line,
- uint32_t& instruction) const = 0;
+ virtual std::optional<AssemblerTmp::Error> apply(const AssemblerTmp::TokenizedSrcLine& line, uint32_t& instruction,
+ FieldLinkRequest& linksWithSymbol) const = 0;
virtual std::optional<AssemblerTmp::Error> decode(const uint32_t instruction, const uint32_t address,
const ReverseSymbolMap& symbolMap,
AssemblerTmp::LineTokens& line) const = 0;
};
+/**
+ * @brief The InstrRes struct is returned by any assembler. Contains the assembled instruction alongside a flag noting
+ * whether the instruction needs additional linkage (ie. for symbol resolution).
+ */
+struct InstrRes {
+ uint32_t instruction = 0;
+ FieldLinkRequest linksWithSymbol;
+};
+
+using AssembleRes = std::variant<Error, InstrRes>;
+using PseudoExpandRes = std::variant<Error, std::optional<std::vector<AssemblerTmp::LineTokens>>>;
+using DisassembleRes = std::variant<Error, AssemblerTmp::LineTokens>;
+
/** @brief OpPart
* A segment of an operation-identifying field of an instruction.
*/
@@ -70,8 +83,8 @@ struct Opcode : public Field {
*/
Opcode(const QString& _name, std::vector<OpPart> _opParts) : name(_name), opParts(_opParts) {}
- std::optional<AssemblerTmp::Error> apply(const AssemblerTmp::TokenizedSrcLine&,
- uint32_t& instruction) const override {
+ std::optional<AssemblerTmp::Error> apply(const AssemblerTmp::TokenizedSrcLine&, uint32_t& instruction,
+ FieldLinkRequest&) const override {
for (const auto& opPart : opParts) {
instruction |= opPart.range.apply(opPart.value);
}
@@ -98,8 +111,8 @@ struct Reg : public Field {
*/
Reg(unsigned tokenIndex, BitRange range) : m_tokenIndex(tokenIndex), m_range(range) {}
Reg(unsigned tokenIndex, unsigned _start, unsigned _stop) : m_tokenIndex(tokenIndex), m_range({_start, _stop}) {}
- std::optional<AssemblerTmp::Error> apply(const AssemblerTmp::TokenizedSrcLine& line,
- uint32_t& instruction) const override {
+ std::optional<AssemblerTmp::Error> apply(const AssemblerTmp::TokenizedSrcLine& line, uint32_t& instruction,
+ FieldLinkRequest&) const override {
bool success;
const QString& regToken = line.tokens[m_tokenIndex];
const uint32_t reg = ISA::instance()->regNumber(regToken, success);
@@ -146,8 +159,8 @@ struct Imm : public Field {
SymbolType _symbolType = SymbolType::None)
: tokenIndex(_tokenIndex), parts(_parts), width(_width), repr(_repr), symbolType(_symbolType) {}
- std::optional<AssemblerTmp::Error> apply(const AssemblerTmp::TokenizedSrcLine& line,
- uint32_t& instruction) const override {
+ std::optional<AssemblerTmp::Error> apply(const AssemblerTmp::TokenizedSrcLine& line, uint32_t& instruction,
+ FieldLinkRequest& linksWithSymbol) const override {
bool success;
const QString& immToken = line.tokens[tokenIndex];
@@ -167,7 +180,10 @@ struct Imm : public Field {
}
if (!success) {
- return AssemblerTmp::Error(line.sourceLine, "Malformed immediate value '" + immToken + "'");
+ // Could not directly resolve immediate. Register it as a symbol to link to.
+ linksWithSymbol.field = this;
+ linksWithSymbol.symbol = immToken;
+ return {};
}
if (!((repr == Repr::Signed && isInt(width, svalue)) || (isUInt(width, uvalue)))) {
@@ -180,6 +196,20 @@ struct Imm : public Field {
}
return {};
}
+
+ std::optional<AssemblerTmp::Error> applySymbolResolution(uint32_t symbolValue, uint32_t& instruction,
+ const uint32_t address) const {
+ long adjustedValue = symbolValue;
+ if (symbolType == SymbolType::Relative) {
+ adjustedValue -= address;
+ }
+
+ for (const auto& part : parts) {
+ part.apply(adjustedValue, instruction);
+ }
+ return {};
+ }
+
std::optional<AssemblerTmp::Error> decode(const uint32_t instruction, const uint32_t address,
const ReverseSymbolMap& symbolMap,
AssemblerTmp::LineTokens& line) const override {
@@ -221,15 +251,15 @@ public:
Instruction(Opcode opcode, const std::vector<std::shared_ptr<Field>>& fields)
: m_opcode(opcode), m_expectedTokens(1 /*opcode*/ + fields.size()), m_fields(fields) {
m_assembler = [](const Instruction& _this, const AssemblerTmp::TokenizedSrcLine& line) {
- uint32_t instruction = 0;
- _this.m_opcode.apply(line, instruction);
+ InstrRes res;
+ _this.m_opcode.apply(line, res.instruction, res.linksWithSymbol);
for (const auto& field : _this.m_fields) {
- auto err = field->apply(line, instruction);
+ auto err = field->apply(line, res.instruction, res.linksWithSymbol);
if (err) {
return AssembleRes(err.value());
}
}
- return AssembleRes(instruction);
+ return AssembleRes(res);
};
m_disassembler = [](const Instruction& _this, const uint32_t instruction, const uint32_t address,
const ReverseSymbolMap& symbolMap) {
@@ -251,7 +281,6 @@ public:
" tokens, but got " +
QString::number(line.tokens.length() - 1));
}
-
return m_assembler(*this, line);
}
DisassembleRes disassemble(const uint32_t instruction, const uint32_t address,

MODIFY
test/tst_assembler.cpp
test/tst_assembler.cpp
@@ -47,6 +47,7 @@ void tst_Assembler::tst_simpleWithBranch() {
<< "B:"
<< "addi a0 a0 -1"
<< "beqz a0 B";
+
auto res = assembler.assemble(program);
if (res.errors.size() != 0) {
res.errors.print();

[Assembler] Implement symbol resolution