aboutsummaryrefslogtreecommitdiff
path: root/backend/lib/MIR
diff options
context:
space:
mode:
Diffstat (limited to 'backend/lib/MIR')
-rw-r--r--backend/lib/MIR/CMakeLists.txt67
-rw-r--r--backend/lib/MIR/EmbeddedIR.cpp944
-rw-r--r--backend/lib/MIR/ReachingDefPrinter.cpp81
3 files changed, 1092 insertions, 0 deletions
diff --git a/backend/lib/MIR/CMakeLists.txt b/backend/lib/MIR/CMakeLists.txt
new file mode 100644
index 0000000..1d5165f
--- /dev/null
+++ b/backend/lib/MIR/CMakeLists.txt
@@ -0,0 +1,67 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+set(
+ RCCBackendMIRSources
+ EmbeddedIR.cpp
+ ReachingDefPrinter.cpp
+ "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MILexer.cpp"
+ "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MIParser.cpp"
+ "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MIRParser.cpp"
+ "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRPrinter.cpp"
+ "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRYamlMapping.cpp"
+)
+set(
+ RCCBackendMIRHeaders
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MIRParser/MIParser.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MIRParser/MIRParser.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MIRPrinter.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MIRYamlMapping.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MIR/EmbeddedIR.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MIR/ReachingDefPrinter.h"
+)
+
+add_library(RCCBackendMIR ${RCCBackendMIRSources})
+add_library(RCCBackend::MIR ALIAS RCCBackendMIR)
+
+rcc_backend_configure_target(RCCBackendMIR)
+
+target_include_directories(
+ RCCBackendMIR
+ PUBLIC
+ "$<BUILD_INTERFACE:${RCC_BACKEND_SOURCE_DIR}/include>"
+ "$<INSTALL_INTERFACE:${CMAKE_INSTALL_INCLUDEDIR}>"
+)
+target_link_libraries(
+ RCCBackendMIR
+ PUBLIC
+ RCCBackend::AsmParser
+ RCCBackend::CodeGen
+ RCCBackend::IR
+)
+
+set_target_properties(
+ RCCBackendMIR
+ PROPERTIES
+ EXPORT_NAME MIR
+ OUTPUT_NAME RCCBackendMIR
+)
+
+install(
+ TARGETS RCCBackendMIR
+ EXPORT RCCBackendTargets
+ ARCHIVE DESTINATION "${CMAKE_INSTALL_LIBDIR}"
+ LIBRARY DESTINATION "${CMAKE_INSTALL_LIBDIR}"
+ RUNTIME DESTINATION "${CMAKE_INSTALL_BINDIR}"
+)
+
+rcc_backend_register_format_files(
+ "${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIR.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/ReachingDefPrinter.cpp"
+ "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MILexer.cpp"
+ "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MILexer.h"
+ "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MIParser.cpp"
+ "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MIRParser.cpp"
+ "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRPrinter.cpp"
+ "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRYamlMapping.cpp"
+ ${RCCBackendMIRHeaders}
+)
diff --git a/backend/lib/MIR/EmbeddedIR.cpp b/backend/lib/MIR/EmbeddedIR.cpp
new file mode 100644
index 0000000..67b91e2
--- /dev/null
+++ b/backend/lib/MIR/EmbeddedIR.cpp
@@ -0,0 +1,944 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/MIR/EmbeddedIR.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <string>
+#include <string_view>
+#include <unordered_set>
+#include <utility>
+
+namespace rcc::mir {
+namespace {
+
+struct ParsedIdentifier final {
+ std::string Name;
+ TextRange Range;
+ std::size_t End = 0;
+ bool IsNumericSlot = false;
+};
+
+[[nodiscard]] bool isHorizontalSpace(char Character) noexcept {
+ return Character == ' ' || Character == '\t';
+}
+
+[[nodiscard]] bool isHexDigit(char Character) noexcept {
+ return (Character >= '0' && Character <= '9') || (Character >= 'a' && Character <= 'f') ||
+ (Character >= 'A' && Character <= 'F');
+}
+
+[[nodiscard]] unsigned hexValue(char Character) noexcept {
+ if (Character >= '0' && Character <= '9')
+ return static_cast<unsigned>(Character - '0');
+ if (Character >= 'a' && Character <= 'f')
+ return static_cast<unsigned>(Character - 'a') + 10U;
+ return static_cast<unsigned>(Character - 'A') + 10U;
+}
+
+[[nodiscard]] bool isIdentifierStart(char Character) noexcept {
+ return (Character >= 'a' && Character <= 'z') || (Character >= 'A' && Character <= 'Z') ||
+ Character == '-' || Character == '$' || Character == '.' || Character == '_';
+}
+
+[[nodiscard]] bool isIdentifierBody(char Character) noexcept {
+ return isIdentifierStart(Character) || (Character >= '0' && Character <= '9');
+}
+
+[[nodiscard]] bool isWordBody(char Character) noexcept {
+ return (Character >= 'a' && Character <= 'z') || (Character >= 'A' && Character <= 'Z') ||
+ (Character >= '0' && Character <= '9') || Character == '_';
+}
+
+[[nodiscard]] std::size_t skipHorizontalSpace(std::string_view Line, std::size_t Position,
+ std::size_t End) noexcept {
+ while (Position < End && isHorizontalSpace(Line[Position]))
+ ++Position;
+ return Position;
+}
+
+[[nodiscard]] bool startsWord(std::string_view Line, std::size_t Position, std::size_t End,
+ std::string_view Word) noexcept {
+ if (End - Position < Word.size() || Line.substr(Position, Word.size()) != Word)
+ return false;
+ const std::size_t WordEnd = Position + Word.size();
+ return WordEnd == End || !isWordBody(Line[WordEnd]);
+}
+
+[[nodiscard]] bool containsWord(std::string_view Line, std::size_t End,
+ std::string_view Word) noexcept {
+ std::size_t Position = 0;
+ while ((Position = Line.find(Word, Position)) != std::string_view::npos && Position < End) {
+ const bool BeginsWord = Position == 0 || !isWordBody(Line[Position - 1]);
+ if (BeginsWord && startsWord(Line, Position, End, Word))
+ return true;
+ Position += Word.size();
+ }
+ return false;
+}
+
+} // namespace
+
+const EmbeddedIRReference *EmbeddedIRFunction::block(std::string_view QueryName) const noexcept {
+ const auto Position = BlockNameToIndex.find(QueryName);
+ if (Position == BlockNameToIndex.end())
+ return nullptr;
+ return &Blocks[Position->second];
+}
+
+const EmbeddedIRReference *EmbeddedIRFunction::alloca(std::string_view QueryName) const noexcept {
+ const auto Position = AllocaNameToIndex.find(QueryName);
+ if (Position == AllocaNameToIndex.end())
+ return nullptr;
+ return &Allocas[Position->second];
+}
+
+const EmbeddedIRReference *EmbeddedIRFunction::value(std::string_view QueryName) const noexcept {
+ const auto Position = ValueNameToIndex.find(QueryName);
+ if (Position == ValueNameToIndex.end())
+ return nullptr;
+ return &Values[Position->second];
+}
+
+const EmbeddedIRFunction *EmbeddedIRReferenceIndex::function(std::string_view Name) const noexcept {
+ const auto Position = FunctionNameToIndex.find(Name);
+ if (Position == FunctionNameToIndex.end())
+ return nullptr;
+ return &Functions[Position->second];
+}
+
+const EmbeddedIRFunction *
+EmbeddedIRReferenceIndex::unnamedFunction(std::size_t Ordinal) const noexcept {
+ for (const EmbeddedIRFunction &Function : Functions) {
+ if (!Function.isUnnamed())
+ continue;
+ if (Ordinal == 0)
+ return &Function;
+ --Ordinal;
+ }
+ return nullptr;
+}
+
+const EmbeddedIRReference *
+EmbeddedIRReferenceIndex::globalObject(std::string_view Name) const noexcept {
+ const auto Position = GlobalNameToIndex.find(Name);
+ if (Position == GlobalNameToIndex.end())
+ return nullptr;
+ return &GlobalObjects[Position->second];
+}
+
+std::optional<GlobalValueProperties>
+EmbeddedIRReferenceIndex::globalObjectProperties(std::string_view Name) const noexcept {
+ const auto Position = GlobalProperties.find(Name);
+ if (Position == GlobalProperties.end())
+ return std::nullopt;
+ return Position->second;
+}
+
+const EmbeddedIRMetadataDefinition *
+EmbeddedIRReferenceIndex::metadata(std::string_view Name) const noexcept {
+ const auto Position = MetadataNameToIndex.find(Name);
+ if (Position == MetadataNameToIndex.end())
+ return nullptr;
+ return &MetadataDefinitions[Position->second];
+}
+
+const EmbeddedIRTypeDefinition *
+EmbeddedIRReferenceIndex::typeDefinition(std::string_view Name) const noexcept {
+ const auto Position = TypeNameToIndex.find(Name);
+ if (Position == TypeNameToIndex.end())
+ return nullptr;
+ return &TypeDefinitions[Position->second];
+}
+
+class EmbeddedIRIndexer final {
+public:
+ EmbeddedIRIndexer(std::string SourceName, std::string SourceText)
+ : Index(std::move(SourceName), std::move(SourceText)) {}
+
+ [[nodiscard]] EmbeddedIRIndexResult run() {
+ const std::size_t NulOffset = Index.Source.text().find('\0');
+ if (NulOffset != std::string_view::npos) {
+ diagnose(NulOffset, NulOffset + 1, "NUL bytes are not allowed in embedded LLVM IR");
+ return failureResult();
+ }
+
+ for (std::size_t LineNumber = 1; LineNumber <= Index.Source.lineCount(); ++LineNumber) {
+ const std::string_view Line = Index.Source.line(LineNumber);
+ const std::size_t LineOffset = Index.Source.lineOffsets()[LineNumber - 1];
+ const std::size_t ContentEnd = findCommentStart(Line);
+ if (ActiveFunction) {
+ parseActiveFunctionLine(Line, LineOffset, ContentEnd);
+ } else {
+ parseTopLevelLine(Line, LineOffset, ContentEnd);
+ }
+ if (Failed)
+ return failureResult();
+ }
+
+ if (ActiveFunction) {
+ const EmbeddedIRFunction &Function = Index.Functions[ActiveFunction.value()];
+ diagnose(Function.nameRange().Begin.Offset, Function.nameRange().End.Offset,
+ "embedded LLVM IR function definition has no closing brace");
+ return failureResult();
+ }
+
+ resolveFunctionAttributes();
+ validateLocalReferences();
+ if (Failed)
+ return failureResult();
+
+ EmbeddedIRIndexResult Result;
+ Result.Index.emplace(std::move(Index));
+ return Result;
+ }
+
+private:
+ [[nodiscard]] EmbeddedIRIndexResult failureResult() {
+ EmbeddedIRIndexResult Result;
+ Result.Diagnostics = std::move(Diagnostics);
+ return Result;
+ }
+
+ void diagnose(std::size_t Begin, std::size_t End, std::string Message) {
+ if (Failed)
+ return;
+ Failed = true;
+ Diagnostics.push_back(TextDiagnostic{
+ .Severity = DiagnosticSeverity::Error,
+ .Category = "mir-embedded-ir",
+ .Message = std::move(Message),
+ .SourceName = std::string(Index.Source.name()),
+ .Range = Index.Source.range(Begin, End),
+ });
+ }
+
+ [[nodiscard]] std::size_t findCommentStart(std::string_view Line) const noexcept {
+ bool InQuote = false;
+ for (std::size_t Position = 0; Position < Line.size(); ++Position) {
+ const char Character = Line[Position];
+ if (InQuote && Character == '\\' && Position + 2 < Line.size() &&
+ isHexDigit(Line[Position + 1]) && isHexDigit(Line[Position + 2])) {
+ Position += 2;
+ continue;
+ }
+ if (Character == '"') {
+ InQuote = !InQuote;
+ continue;
+ }
+ if (!InQuote && Character == ';')
+ return Position;
+ }
+ return Line.size();
+ }
+
+ [[nodiscard]] std::optional<ParsedIdentifier>
+ parseIdentifier(std::string_view Line, std::size_t LineOffset, std::size_t Position,
+ std::size_t End, std::optional<char> Prefix) {
+ const std::size_t Begin = Position;
+ if (Prefix) {
+ if (Position >= End || Line[Position] != *Prefix)
+ return std::nullopt;
+ ++Position;
+ }
+ if (Position >= End)
+ return std::nullopt;
+
+ std::string Name;
+ bool IsNumericSlot = false;
+ if (Line[Position] == '"') {
+ ++Position;
+ while (Position < End && Line[Position] != '"') {
+ const char Character = Line[Position++];
+ if (Character != '\\') {
+ if (static_cast<unsigned char>(Character) < 0x20U) {
+ diagnose(LineOffset + Position - 1, LineOffset + Position,
+ "control character is not allowed in quoted LLVM IR identifier");
+ return std::nullopt;
+ }
+ Name.push_back(Character);
+ continue;
+ }
+ if (End - Position < 2 || !isHexDigit(Line[Position]) || !isHexDigit(Line[Position + 1])) {
+ diagnose(LineOffset + Position - 1, LineOffset + std::min(Position + 2, End),
+ "LLVM IR identifier escape must contain two hexadecimal digits");
+ return std::nullopt;
+ }
+ const unsigned Value = (hexValue(Line[Position]) << 4U) | hexValue(Line[Position + 1]);
+ Name.push_back(static_cast<char>(Value));
+ Position += 2;
+ }
+ if (Position >= End || Line[Position] != '"') {
+ diagnose(LineOffset + Begin, LineOffset + End, "unterminated quoted LLVM IR identifier");
+ return std::nullopt;
+ }
+ ++Position;
+ } else if (Line[Position] >= '0' && Line[Position] <= '9') {
+ IsNumericSlot = true;
+ const std::size_t NameBegin = Position;
+ while (Position < End && Line[Position] >= '0' && Line[Position] <= '9')
+ ++Position;
+ Name = std::string(Line.substr(NameBegin, Position - NameBegin));
+ } else if (isIdentifierStart(Line[Position])) {
+ const std::size_t NameBegin = Position;
+ while (Position < End && isIdentifierBody(Line[Position]))
+ ++Position;
+ Name = std::string(Line.substr(NameBegin, Position - NameBegin));
+ } else {
+ return std::nullopt;
+ }
+
+ return ParsedIdentifier{
+ .Name = std::move(Name),
+ .Range = Index.Source.range(LineOffset + Begin, LineOffset + Position),
+ .End = Position,
+ .IsNumericSlot = IsNumericSlot,
+ };
+ }
+
+ [[nodiscard]] std::optional<std::pair<std::string, TextRange>>
+ parseStringLiteral(std::string_view Line, std::size_t LineOffset, std::size_t &Position,
+ std::size_t End) {
+ if (Position >= End || Line[Position] != '"')
+ return std::nullopt;
+ const std::size_t Begin = Position++;
+ std::string Value;
+ while (Position < End && Line[Position] != '"') {
+ const char Character = Line[Position++];
+ if (Character != '\\') {
+ if (static_cast<unsigned char>(Character) < 0x20U) {
+ diagnose(LineOffset + Position - 1, LineOffset + Position,
+ "control character is not allowed in LLVM IR string");
+ return std::nullopt;
+ }
+ Value.push_back(Character);
+ continue;
+ }
+ if (End - Position < 2 || !isHexDigit(Line[Position]) || !isHexDigit(Line[Position + 1])) {
+ diagnose(LineOffset + Position - 1, LineOffset + std::min(Position + 2, End),
+ "LLVM IR string escape must contain two hexadecimal digits");
+ return std::nullopt;
+ }
+ const unsigned Decoded = (hexValue(Line[Position]) << 4U) | hexValue(Line[Position + 1]);
+ Value.push_back(static_cast<char>(Decoded));
+ Position += 2;
+ }
+ if (Position >= End || Line[Position] != '"') {
+ diagnose(LineOffset + Begin, LineOffset + End, "unterminated LLVM IR string");
+ return std::nullopt;
+ }
+ ++Position;
+ return std::pair<std::string, TextRange>(
+ std::move(Value), Index.Source.range(LineOffset + Begin, LineOffset + Position));
+ }
+
+ void parseTopLevelLine(std::string_view Line, std::size_t LineOffset, std::size_t End) {
+ std::size_t Position = skipHorizontalSpace(Line, 0, End);
+ if (Position == End)
+ return;
+
+ if (startsWord(Line, Position, End, "target")) {
+ parseTargetFact(Line, LineOffset, Position, End);
+ return;
+ }
+ if (startsWord(Line, Position, End, "define")) {
+ parseFunctionHeader(Line, LineOffset, Position, End, true);
+ return;
+ }
+ if (startsWord(Line, Position, End, "declare")) {
+ parseFunctionHeader(Line, LineOffset, Position, End, false);
+ return;
+ }
+ if (startsWord(Line, Position, End, "attributes")) {
+ parseAttributeGroup(Line, LineOffset, Position, End);
+ return;
+ }
+ if (Line[Position] == '@') {
+ parseGlobalObject(Line, LineOffset, Position, End);
+ return;
+ }
+ if (Line[Position] == '%') {
+ parseTypeDefinition(Line, LineOffset, Position, End);
+ return;
+ }
+ if (Line[Position] == '!')
+ parseMetadataDefinition(Line, LineOffset, Position, End);
+ }
+
+ void parseTypeDefinition(std::string_view Line, std::size_t LineOffset, std::size_t Position,
+ std::size_t End) {
+ auto Name = parseIdentifier(Line, LineOffset, Position, End, '%');
+ if (!Name || Failed)
+ return;
+ Position = skipHorizontalSpace(Line, Name->End, End);
+ if (Position >= End || Line[Position] != '=')
+ return;
+ ++Position;
+ Position = skipHorizontalSpace(Line, Position, End);
+ if (!startsWord(Line, Position, End, "type"))
+ return;
+ Position += std::string_view("type").size();
+ Position = skipHorizontalSpace(Line, Position, End);
+ std::size_t DefinitionEnd = End;
+ while (DefinitionEnd > Position && isHorizontalSpace(Line[DefinitionEnd - 1]))
+ --DefinitionEnd;
+ if (Position == DefinitionEnd) {
+ diagnose(Name->Range.Begin.Offset, Name->Range.End.Offset,
+ "embedded LLVM IR type definition is empty");
+ return;
+ }
+ if (Index.TypeNameToIndex.contains(Name->Name)) {
+ diagnose(Name->Range.Begin.Offset, Name->Range.End.Offset,
+ "duplicate embedded LLVM IR type definition");
+ return;
+ }
+ const std::size_t TypeIndex = Index.TypeDefinitions.size();
+ const bool NumericName =
+ !Name->Name.empty() && Name->Name.front() >= '0' && Name->Name.front() <= '9';
+ Index.TypeNameToIndex.emplace(Name->Name, TypeIndex);
+ Index.TypeDefinitions.push_back(EmbeddedIRTypeDefinition{
+ .Name = std::move(Name->Name),
+ .Range = Name->Range,
+ .Definition = std::string(Line.substr(Position, DefinitionEnd - Position)),
+ .DefinitionRange = Index.Source.range(LineOffset + Position, LineOffset + DefinitionEnd),
+ .NumericName = NumericName,
+ });
+ }
+
+ void parseTargetFact(std::string_view Line, std::size_t LineOffset, std::size_t Position,
+ std::size_t End) {
+ Position += std::string_view("target").size();
+ Position = skipHorizontalSpace(Line, Position, End);
+ const bool IsTriple = startsWord(Line, Position, End, "triple");
+ const bool IsDataLayout = startsWord(Line, Position, End, "datalayout");
+ if (!IsTriple && !IsDataLayout)
+ return;
+ Position +=
+ IsTriple ? std::string_view("triple").size() : std::string_view("datalayout").size();
+ Position = skipHorizontalSpace(Line, Position, End);
+ if (Position >= End || Line[Position] != '=') {
+ diagnose(LineOffset + Position, LineOffset + std::min(Position + 1, End),
+ "expected '=' in embedded LLVM IR target fact");
+ return;
+ }
+ ++Position;
+ Position = skipHorizontalSpace(Line, Position, End);
+ auto Value = parseStringLiteral(Line, LineOffset, Position, End);
+ if (!Value)
+ return;
+ Position = skipHorizontalSpace(Line, Position, End);
+ if (Position != End) {
+ diagnose(LineOffset + Position, LineOffset + End,
+ "unexpected content after embedded LLVM IR target fact");
+ return;
+ }
+
+ std::optional<std::string> &Storage = IsTriple ? Index.TargetTriple : Index.DataLayout;
+ std::optional<TextRange> &Range = IsTriple ? Index.TargetTripleRange : Index.DataLayoutRange;
+ if (Storage) {
+ diagnose(Value->second.Begin.Offset, Value->second.End.Offset,
+ IsTriple ? "duplicate embedded LLVM IR target triple"
+ : "duplicate embedded LLVM IR data layout");
+ return;
+ }
+ Storage = std::move(Value->first);
+ Range = Value->second;
+ }
+
+ void parseFunctionHeader(std::string_view Line, std::size_t LineOffset, std::size_t Position,
+ std::size_t End, bool IsDefinition) {
+ Position +=
+ IsDefinition ? std::string_view("define").size() : std::string_view("declare").size();
+ std::optional<ParsedIdentifier> Name;
+ while (Position < End) {
+ if (Line[Position] == '"') {
+ std::size_t StringPosition = Position;
+ auto Ignored = parseStringLiteral(Line, LineOffset, StringPosition, End);
+ if (!Ignored)
+ return;
+ Position = StringPosition;
+ continue;
+ }
+ if (Line[Position] == '@') {
+ Name = parseIdentifier(Line, LineOffset, Position, End, '@');
+ break;
+ }
+ ++Position;
+ }
+ if (!Name) {
+ diagnose(LineOffset, LineOffset + End,
+ "embedded LLVM IR function header has no global identifier");
+ return;
+ }
+
+ auto FunctionIndex = addFunction(*Name, IsDefinition);
+ if (!FunctionIndex || Failed || !IsDefinition)
+ return;
+ EmbeddedIRFunction &Function = Index.Functions[*FunctionIndex];
+ Function.HasLinkOnceODRLinkage = containsWord(Line, End, "linkonce_odr");
+ Function.HasSection = containsWord(Line, End, "section");
+ Function.HasComdat = containsWord(Line, End, "comdat");
+ Function.HasSectionPrefix = containsWord(Line, End, "section_prefix");
+ ActiveFunction = FunctionIndex;
+ HeaderParenthesisDepth = 0;
+ parseFunctionHeaderRemainder(Line, LineOffset, Name->End, End);
+ }
+
+ [[nodiscard]] std::optional<std::size_t> addFunction(const ParsedIdentifier &Name,
+ bool IsDefinition) {
+ if (Index.GlobalNameToIndex.contains(Name.Name)) {
+ diagnose(Name.Range.Begin.Offset, Name.Range.End.Offset,
+ "embedded LLVM IR name is used by both a function and a global object");
+ return std::nullopt;
+ }
+
+ const auto Existing = Index.FunctionNameToIndex.find(Name.Name);
+ if (Existing != Index.FunctionNameToIndex.end()) {
+ EmbeddedIRFunction &Function = Index.Functions[Existing->second];
+ if (IsDefinition && Function.IsDefinition) {
+ diagnose(Name.Range.Begin.Offset, Name.Range.End.Offset,
+ "duplicate embedded LLVM IR function definition");
+ return std::nullopt;
+ }
+ if (IsDefinition) {
+ Function.IsDefinition = true;
+ Function.NameRange = Name.Range;
+ }
+ return Existing->second;
+ }
+
+ const std::size_t IndexValue = Index.Functions.size();
+ EmbeddedIRFunction Function;
+ Function.Name = Name.Name;
+ Function.NameRange = Name.Range;
+ Function.IsDefinition = IsDefinition;
+ Function.IsUnnamed = Name.IsNumericSlot;
+ Index.Functions.push_back(std::move(Function));
+ Index.FunctionNameToIndex.emplace(Name.Name, IndexValue);
+ return IndexValue;
+ }
+
+ void parseFunctionHeaderRemainder(std::string_view Line, std::size_t LineOffset,
+ std::size_t Position, std::size_t End) {
+ bool InQuote = false;
+ for (; Position < End; ++Position) {
+ const char Character = Line[Position];
+ if (InQuote && Character == '\\' && Position + 2 < End && isHexDigit(Line[Position + 1]) &&
+ isHexDigit(Line[Position + 2])) {
+ Position += 2;
+ continue;
+ }
+ if (Character == '"') {
+ InQuote = !InQuote;
+ continue;
+ }
+ if (InQuote)
+ continue;
+ if (HeaderParenthesisDepth == 0 && startsWord(Line, Position, End, "minsize")) {
+ Index.Functions[ActiveFunction.value()].HasMinSize = true;
+ Position += std::string_view("minsize").size() - 1U;
+ continue;
+ }
+ if (HeaderParenthesisDepth == 0 && Character == '#') {
+ auto Group = parseIdentifier(Line, LineOffset, Position, End, '#');
+ if (!Group || Failed)
+ return;
+ Index.Functions[ActiveFunction.value()].AttributeGroup = std::move(Group->Name);
+ Position = Group->End - 1U;
+ continue;
+ }
+ if (Character == '%' && HeaderParenthesisDepth != 0 && ActiveFunction) {
+ const std::size_t IdentifierBegin = Position;
+ auto Name = parseIdentifier(Line, LineOffset, Position, End, '%');
+ if (!Name || Failed)
+ return;
+ const std::size_t Following = skipHorizontalSpace(Line, Name->End, End);
+ recordLocalReference(*Name, Index.Functions[ActiveFunction.value()]);
+ if (Failed)
+ return;
+ std::size_t Previous = IdentifierBegin;
+ while (Previous > 0 && isHorizontalSpace(Line[Previous - 1]))
+ --Previous;
+ const bool HasTypeBefore =
+ Previous != 0 && Line[Previous - 1] != '(' && Line[Previous - 1] != ',';
+ const bool EndsParameter =
+ Following == End || Line[Following] == ',' || Line[Following] == ')';
+ if (HasTypeBefore && EndsParameter)
+ addLocalValue(*Name, Index.Functions[ActiveFunction.value()]);
+ Position = Name->End - 1;
+ continue;
+ }
+ if (Character == '(') {
+ ++HeaderParenthesisDepth;
+ continue;
+ }
+ if (Character == ')') {
+ if (HeaderParenthesisDepth == 0) {
+ diagnose(LineOffset + Position, LineOffset + Position + 1,
+ "unmatched ')' in embedded LLVM IR function header");
+ return;
+ }
+ --HeaderParenthesisDepth;
+ continue;
+ }
+ if (Character == '{' && HeaderParenthesisDepth == 0) {
+ FunctionBraceDepth = 1;
+ parseFunctionBodySegment(Line, LineOffset, Position + 1, End);
+ return;
+ }
+ }
+ }
+
+ void addLocalValue(const ParsedIdentifier &Name, EmbeddedIRFunction &Function) {
+ if (Function.ValueNameToIndex.contains(Name.Name) ||
+ Function.BlockNameToIndex.contains(Name.Name)) {
+ diagnose(Name.Range.Begin.Offset, Name.Range.End.Offset,
+ "duplicate embedded LLVM IR local value or basic block name");
+ return;
+ }
+ const std::size_t ValueIndex = Function.Values.size();
+ Function.ValueNameToIndex.emplace(Name.Name, ValueIndex);
+ Function.Values.push_back(EmbeddedIRReference{
+ .Name = Name.Name,
+ .Range = Name.Range,
+ });
+ observeNumericSlot(Name, Function);
+ }
+
+ void parseActiveFunctionLine(std::string_view Line, std::size_t LineOffset, std::size_t End) {
+ if (FunctionBraceDepth == 0) {
+ parseFunctionHeaderRemainder(Line, LineOffset, 0, End);
+ return;
+ }
+ parseFunctionBodySegment(Line, LineOffset, 0, End);
+ }
+
+ void parseFunctionBodySegment(std::string_view Line, std::size_t LineOffset, std::size_t Begin,
+ std::size_t End) {
+ std::size_t BodyEnd = End;
+ bool InQuote = false;
+ std::size_t Depth = FunctionBraceDepth;
+ for (std::size_t Position = Begin; Position < End; ++Position) {
+ const char Character = Line[Position];
+ if (InQuote && Character == '\\' && Position + 2 < End && isHexDigit(Line[Position + 1]) &&
+ isHexDigit(Line[Position + 2])) {
+ Position += 2;
+ continue;
+ }
+ if (Character == '"') {
+ InQuote = !InQuote;
+ continue;
+ }
+ if (InQuote)
+ continue;
+ if (Character == '{') {
+ ++Depth;
+ } else if (Character == '}') {
+ if (Depth == 0) {
+ diagnose(LineOffset + Position, LineOffset + Position + 1,
+ "unmatched '}' in embedded LLVM IR function");
+ return;
+ }
+ --Depth;
+ if (Depth == 0) {
+ BodyEnd = Position;
+ break;
+ }
+ }
+ }
+
+ if (!ActiveFunction) {
+ diagnose(LineOffset + Begin, LineOffset + BodyEnd,
+ "internal embedded LLVM IR function indexing state is invalid");
+ return;
+ }
+ EmbeddedIRFunction &Function = Index.Functions[ActiveFunction.value()];
+ const std::size_t PreviousBlockCount = Function.Blocks.size();
+ parseBlockLabel(Line, LineOffset, Begin, BodyEnd, Function);
+ if (Failed)
+ return;
+ const std::size_t FirstContent = skipHorizontalSpace(Line, Begin, BodyEnd);
+ if (Function.Blocks.empty() && Function.Blocks.size() == PreviousBlockCount &&
+ FirstContent < BodyEnd) {
+ addImplicitEntryBlock(LineOffset + FirstContent, Function);
+ if (Failed)
+ return;
+ }
+ parseLocalValueDefinition(Line, LineOffset, Begin, BodyEnd, Function);
+ if (Failed)
+ return;
+ parseLocalReferences(Line, LineOffset, Begin, BodyEnd, Function);
+ if (Failed)
+ return;
+
+ FunctionBraceDepth = Depth;
+ if (FunctionBraceDepth == 0)
+ ActiveFunction.reset();
+ }
+
+ void parseBlockLabel(std::string_view Line, std::size_t LineOffset, std::size_t Begin,
+ std::size_t End, EmbeddedIRFunction &Function) {
+ std::size_t Position = skipHorizontalSpace(Line, Begin, End);
+ if (Position >= End)
+ return;
+ auto Name = parseIdentifier(Line, LineOffset, Position, End, std::nullopt);
+ if (!Name || Failed)
+ return;
+ Position = skipHorizontalSpace(Line, Name->End, End);
+ if (Position >= End || Line[Position] != ':')
+ return;
+
+ if (Function.BlockNameToIndex.contains(Name->Name)) {
+ diagnose(Name->Range.Begin.Offset, Name->Range.End.Offset,
+ "duplicate embedded LLVM IR basic block label");
+ return;
+ }
+ if (Function.ValueNameToIndex.contains(Name->Name)) {
+ diagnose(Name->Range.Begin.Offset, Name->Range.End.Offset,
+ "duplicate embedded LLVM IR local value or basic block name");
+ return;
+ }
+ const std::size_t BlockIndex = Function.Blocks.size();
+ Function.BlockNameToIndex.emplace(Name->Name, BlockIndex);
+ Function.Blocks.push_back(EmbeddedIRReference{
+ .Name = Name->Name,
+ .Range = Name->Range,
+ });
+ observeNumericSlot(*Name, Function);
+ }
+
+ void addImplicitEntryBlock(std::size_t Offset, EmbeddedIRFunction &Function) {
+ const std::string Name = std::to_string(Function.NextUnnamedSlot++);
+ if (Function.BlockNameToIndex.contains(Name) || Function.ValueNameToIndex.contains(Name)) {
+ diagnose(Offset, Offset, "embedded LLVM IR unnamed entry block slot is already in use");
+ return;
+ }
+ const std::size_t BlockIndex = Function.Blocks.size();
+ Function.BlockNameToIndex.emplace(Name, BlockIndex);
+ Function.Blocks.push_back(EmbeddedIRReference{
+ .Name = Name,
+ .Range = Index.Source.range(Offset, Offset),
+ });
+ }
+
+ void observeNumericSlot(const ParsedIdentifier &Name, EmbeddedIRFunction &Function) {
+ if (!Name.IsNumericSlot)
+ return;
+ std::uint64_t Slot = 0;
+ for (const char Digit : Name.Name) {
+ const std::uint64_t Value = static_cast<std::uint64_t>(Digit - '0');
+ if (Slot > (std::numeric_limits<std::uint64_t>::max() - Value) / 10U) {
+ diagnose(Name.Range.Begin.Offset, Name.Range.End.Offset,
+ "embedded LLVM IR numeric slot is too large");
+ return;
+ }
+ Slot = Slot * 10U + Value;
+ }
+ if (Slot == std::numeric_limits<std::uint64_t>::max()) {
+ diagnose(Name.Range.Begin.Offset, Name.Range.End.Offset,
+ "embedded LLVM IR numeric slot is too large");
+ return;
+ }
+ Function.NextUnnamedSlot = std::max(Function.NextUnnamedSlot, Slot + 1U);
+ }
+
+ void parseLocalValueDefinition(std::string_view Line, std::size_t LineOffset, std::size_t Begin,
+ std::size_t End, EmbeddedIRFunction &Function) {
+ std::size_t Position = skipHorizontalSpace(Line, Begin, End);
+ if (Position >= End || Line[Position] != '%')
+ return;
+ auto Name = parseIdentifier(Line, LineOffset, Position, End, '%');
+ if (!Name || Failed)
+ return;
+ Position = skipHorizontalSpace(Line, Name->End, End);
+ if (Position >= End || Line[Position] != '=')
+ return;
+ ++Position;
+ Position = skipHorizontalSpace(Line, Position, End);
+
+ addLocalValue(*Name, Function);
+ if (Failed)
+ return;
+
+ if (!startsWord(Line, Position, End, "alloca"))
+ return;
+ const std::size_t AllocaIndex = Function.Allocas.size();
+ Function.AllocaNameToIndex.emplace(Name->Name, AllocaIndex);
+ Function.Allocas.push_back(EmbeddedIRReference{
+ .Name = std::move(Name->Name),
+ .Range = Name->Range,
+ });
+ }
+
+ void recordLocalReference(const ParsedIdentifier &Name, EmbeddedIRFunction &Function) {
+ Function.LocalReferences.push_back(EmbeddedIRReference{
+ .Name = Name.Name,
+ .Range = Name.Range,
+ });
+ }
+
+ void parseLocalReferences(std::string_view Line, std::size_t LineOffset, std::size_t Begin,
+ std::size_t End, EmbeddedIRFunction &Function) {
+ bool InQuote = false;
+ for (std::size_t Position = Begin; Position < End; ++Position) {
+ const char Character = Line[Position];
+ if (InQuote && Character == '\\' && Position + 2 < End && isHexDigit(Line[Position + 1]) &&
+ isHexDigit(Line[Position + 2])) {
+ Position += 2;
+ continue;
+ }
+ if (Character == '"') {
+ InQuote = !InQuote;
+ continue;
+ }
+ if (InQuote || Character != '%')
+ continue;
+ auto Name = parseIdentifier(Line, LineOffset, Position, End, '%');
+ if (!Name || Failed)
+ continue;
+ recordLocalReference(*Name, Function);
+ Position = Name->End - 1;
+ }
+ }
+
+ void validateLocalReferences() {
+ for (const EmbeddedIRFunction &Function : Index.Functions) {
+ if (!Function.IsDefinition)
+ continue;
+ for (const EmbeddedIRReference &Reference : Function.LocalReferences) {
+ if (Function.ValueNameToIndex.contains(Reference.Name) ||
+ Function.BlockNameToIndex.contains(Reference.Name) ||
+ Index.TypeNameToIndex.contains(Reference.Name))
+ continue;
+ diagnose(Reference.Range.Begin.Offset, Reference.Range.End.Offset,
+ "use of undefined value '%" + Reference.Name + "'");
+ return;
+ }
+ }
+ }
+
+ void parseAttributeGroup(std::string_view Line, std::size_t LineOffset, std::size_t Position,
+ std::size_t End) {
+ Position += std::string_view("attributes").size();
+ Position = skipHorizontalSpace(Line, Position, End);
+ auto Group = parseIdentifier(Line, LineOffset, Position, End, '#');
+ if (!Group || Failed)
+ return;
+ if (containsWord(Line, End, "minsize"))
+ MinSizeAttributeGroups.insert(std::move(Group->Name));
+ }
+
+ void resolveFunctionAttributes() {
+ for (EmbeddedIRFunction &Function : Index.Functions) {
+ if (Function.AttributeGroup && MinSizeAttributeGroups.contains(*Function.AttributeGroup)) {
+ Function.HasMinSize = true;
+ }
+ }
+ }
+
+ void parseGlobalObject(std::string_view Line, std::size_t LineOffset, std::size_t Position,
+ std::size_t End) {
+ auto Name = parseIdentifier(Line, LineOffset, Position, End, '@');
+ if (!Name || Failed)
+ return;
+ Position = skipHorizontalSpace(Line, Name->End, End);
+ if (Position >= End || Line[Position] != '=')
+ return;
+ if (Index.FunctionNameToIndex.contains(Name->Name)) {
+ diagnose(Name->Range.Begin.Offset, Name->Range.End.Offset,
+ "embedded LLVM IR name is used by both a global object and a function");
+ return;
+ }
+ if (Index.GlobalNameToIndex.contains(Name->Name)) {
+ diagnose(Name->Range.Begin.Offset, Name->Range.End.Offset,
+ "duplicate embedded LLVM IR global object");
+ return;
+ }
+ ++Position;
+ GlobalValueProperties Properties;
+ while (Position < End) {
+ while (Position < End && !isIdentifierStart(Line[Position]))
+ ++Position;
+ const std::size_t WordBegin = Position;
+ while (Position < End && isIdentifierBody(Line[Position]))
+ ++Position;
+ if (WordBegin == Position)
+ continue;
+ const std::string_view Word = Line.substr(WordBegin, Position - WordBegin);
+ if (Word == "dso_local" || Word == "internal" || Word == "private")
+ Properties.DSOLocal = true;
+ else if (Word == "extern_weak")
+ Properties.ExternalWeak = true;
+ else if (Word == "thread_local")
+ Properties.ThreadLocal = true;
+ }
+ const std::size_t GlobalIndex = Index.GlobalObjects.size();
+ Index.GlobalNameToIndex.emplace(Name->Name, GlobalIndex);
+ Index.GlobalObjects.push_back(EmbeddedIRReference{
+ .Name = std::move(Name->Name),
+ .Range = Name->Range,
+ });
+ Index.GlobalProperties.emplace(Index.GlobalObjects.back().Name, Properties);
+ }
+
+ void parseMetadataDefinition(std::string_view Line, std::size_t LineOffset, std::size_t Position,
+ std::size_t End) {
+ auto Name = parseIdentifier(Line, LineOffset, Position, End, '!');
+ if (!Name || Failed)
+ return;
+ Position = skipHorizontalSpace(Line, Name->End, End);
+ if (Position >= End || Line[Position] != '=')
+ return;
+ ++Position;
+ Position = skipHorizontalSpace(Line, Position, End);
+ if (startsWord(Line, Position, End, "distinct")) {
+ Position += std::string_view("distinct").size();
+ Position = skipHorizontalSpace(Line, Position, End);
+ }
+
+ std::string DynamicType;
+ if (Position < End && Line[Position] == '!') {
+ ++Position;
+ if (Position < End && Line[Position] == '{') {
+ DynamicType = "MDTuple";
+ } else if (Position < End && Line[Position] == '"') {
+ DynamicType = "MDString";
+ } else {
+ const std::size_t TypeBegin = Position;
+ while (Position < End && isIdentifierBody(Line[Position]))
+ ++Position;
+ if (Position != TypeBegin)
+ DynamicType = std::string(Line.substr(TypeBegin, Position - TypeBegin));
+ }
+ }
+ if (Index.MetadataNameToIndex.contains(Name->Name)) {
+ diagnose(Name->Range.Begin.Offset, Name->Range.End.Offset,
+ "duplicate embedded LLVM IR metadata definition");
+ return;
+ }
+ const std::size_t MetadataIndex = Index.MetadataDefinitions.size();
+ Index.MetadataNameToIndex.emplace(Name->Name, MetadataIndex);
+ Index.MetadataDefinitions.push_back(EmbeddedIRMetadataDefinition{
+ .Name = std::move(Name->Name),
+ .Range = Name->Range,
+ .DynamicType = std::move(DynamicType),
+ });
+ }
+
+ EmbeddedIRReferenceIndex Index;
+ std::vector<TextDiagnostic> Diagnostics;
+ std::optional<std::size_t> ActiveFunction;
+ std::unordered_set<std::string> MinSizeAttributeGroups;
+ std::size_t HeaderParenthesisDepth = 0;
+ std::size_t FunctionBraceDepth = 0;
+ bool Failed = false;
+};
+
+EmbeddedIRIndexResult indexEmbeddedIR(std::string SourceName, std::string SourceText) {
+ return EmbeddedIRIndexer(std::move(SourceName), std::move(SourceText)).run();
+}
+
+} // namespace rcc::mir
diff --git a/backend/lib/MIR/ReachingDefPrinter.cpp b/backend/lib/MIR/ReachingDefPrinter.cpp
new file mode 100644
index 0000000..5687590
--- /dev/null
+++ b/backend/lib/MIR/ReachingDefPrinter.cpp
@@ -0,0 +1,81 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/MIR/ReachingDefPrinter.h"
+
+#include "rcc/CodeGen/MIRPrinter.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/ReachingDefAnalysis.h"
+
+#include <iostream>
+#include <optional>
+
+namespace rcc::mir {
+
+const MachinePassContract &ReachingDefPrinterPass::contract() const noexcept {
+ static const MachinePassContract Contract = [] {
+ MachinePassContract Value{
+ .Name = std::string(name()),
+ .Requires = {MachineFunctionProperty::NoVRegs},
+ .Sets = {},
+ .Clears = {},
+ .RequiredAnalyses = {MachineFunctionAnalysisManager::id<ReachingDefAnalysis>()},
+ .VerificationStage = std::nullopt,
+ };
+ Value.DeclaredChanges = {};
+ return Value;
+ }();
+ return Contract;
+}
+
+Expected<MachinePassResult> ReachingDefPrinterPass::run(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineFunctionAnalysisManager &Analyses) {
+ auto ReachingDefinitions = Analyses.getResult<ReachingDefAnalysis>(Function, Target);
+ if (!ReachingDefinitions)
+ return std::unexpected(ReachingDefinitions.error());
+ auto Context = createMachineFunctionPrintContext(Function);
+ if (!Context)
+ return std::unexpected(Context.error());
+
+ std::cerr << "Reaching definitions for for machine function: " << Function.name() << '\n';
+ for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) {
+ std::cerr << "%bb." << Block->denseNumber().value_or(0) << ":\n";
+ for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ for (const MachineOperand &Operand : Instruction->operands()) {
+ if (Operand.isRegister()) {
+ const std::optional<Register> Reg = Operand.registerValue();
+ if (Operand.isDef() || !Reg || Reg->isNoRegister())
+ continue;
+ } else if (Operand.kind() != MachineOperand::Kind::FrameIndex) {
+ continue;
+ }
+
+ auto PrintedOperand = printMachineOperand(Operand, Target, *Context);
+ if (!PrintedOperand)
+ return std::unexpected(PrintedOperand.error());
+ std::cerr << *PrintedOperand << ":{ ";
+ for (const MachineInstr *Definition :
+ (*ReachingDefinitions)->reachingDefinitions(Operand)) {
+ std::cerr << (*ReachingDefinitions)->instructionNumber(*Definition) << ' ';
+ }
+ std::cerr << "}\n";
+ }
+
+ auto PrintedInstruction = printMachineInstruction(*Instruction, Target, *Context);
+ if (!PrintedInstruction)
+ return std::unexpected(PrintedInstruction.error());
+ std::cerr << (*ReachingDefinitions)->instructionNumber(*Instruction) << ": "
+ << *PrintedInstruction << "\n\n";
+ }
+ }
+
+ MachinePassResult Result;
+ Result.Preserved = PreservedAnalyses::all();
+ return Result;
+}
+
+} // namespace rcc::mir
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-30 07:18:22 +0000