[GlobalISel] Match LLVM legalization value tracking

1 files changed, 406 insertions, 0 deletions

diff --git a/backend/lib/CodeGen/GlobalISel/Utils.cpp b/backend/lib/CodeGen/GlobalISel/Utils.cpp
new file mode 100644
index 0000000..6640694
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/Utils.cpp
@@ -0,0 +1,406 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/Utils.h"
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <cstdint>
+#include <numeric>
+#include <utility>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] bool hasProtectedAttachment(const MachineInstr &Instruction) noexcept {
+  return Instruction.flags().has(MachineInstrFlag::FrameSetup) ||
+         Instruction.flags().has(MachineInstrFlag::FrameDestroy) ||
+         Instruction.debugInstrNumber() != 0 || Instruction.preInstrSymbol().has_value() ||
+         Instruction.postInstrSymbol().has_value() || Instruction.heapAllocMarker().has_value() ||
+         Instruction.pcSections().has_value() || Instruction.mmra().has_value() ||
+         Instruction.cfiType().has_value() || Instruction.deactivationSymbol().has_value();
+}
+
+[[nodiscard]] bool wouldBeTriviallyDead(const MachineInstr &Instruction,
+                                        const InstructionDescriptor &Descriptor) noexcept {
+  switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
+  case GenericOpcode::LOCAL_ESCAPE:
+  case GenericOpcode::FAKE_USE:
+  case GenericOpcode::LIFETIME_START:
+  case GenericOpcode::LIFETIME_END:
+    return false;
+  default:
+    break;
+  }
+
+  const InstructionFlags Flags = Descriptor.Flags;
+  if (Flags.has(InstructionFlag::Phi))
+    return true;
+  if (Flags.has(InstructionFlag::Terminator) || Flags.has(InstructionFlag::Branch) ||
+      Flags.has(InstructionFlag::Call) || Flags.has(InstructionFlag::Return) ||
+      Flags.has(InstructionFlag::Barrier) || Flags.has(InstructionFlag::MayLoad) ||
+      Flags.has(InstructionFlag::MayStore) || Flags.has(InstructionFlag::HasSideEffects) ||
+      Flags.has(InstructionFlag::UnmodeledSideEffects) ||
+      Flags.has(InstructionFlag::MayRaiseFPException) || hasProtectedAttachment(Instruction))
+    return false;
+  return true;
+}
+
+[[nodiscard]] Expected<void> saveUsesAndErase(MachineInstr &Instruction, MachineRegisterInfo &MRI,
+                                              std::vector<MachineInstr *> &DeadChain) {
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    if (!Operand.isRegister() || !Operand.isUse())
+      continue;
+    const std::optional<Register> Reg = Operand.registerValue();
+    if (!Reg || !Reg->isVirtual())
+      continue;
+    MachineInstr *Definition = MRI.getVRegDef(*Reg);
+    if (Definition != nullptr && Definition != &Instruction)
+      DeadChain.push_back(Definition);
+  }
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return {};
+  return Block->removeInstruction(Instruction);
+}
+
+[[nodiscard]] Expected<LowLevelType> makeVectorType(std::uint64_t ElementCount, bool IsScalable,
+                                                    LowLevelType ElementType) {
+  if (!IsScalable && ElementCount == 1)
+    return ElementType;
+  return IsScalable ? LowLevelType::makeScalableVector(ElementCount, ElementType)
+                    : LowLevelType::makeFixedVector(ElementCount, ElementType);
+}
+
+[[nodiscard]] Expected<void> extractVectorParts(Register Reg, std::size_t ElementCount,
+                                                std::vector<Register> &Parts,
+                                                MachineIRBuilder &MIRBuilder,
+                                                MachineRegisterInfo &MRI) {
+  auto RegisterType = MRI.getType(Reg);
+  if (!RegisterType)
+    return std::unexpected(RegisterType.error());
+  if (!RegisterType->isVector() || RegisterType->isScalableVector() || ElementCount == 0) {
+    return makeUnexpected(
+        ErrorCode::InvalidArgument,
+        "vector part extraction requires a fixed vector and a nonzero element count");
+  }
+
+  const LowLevelType ElementType = *RegisterType->scalarElementType();
+  auto NarrowType = makeVectorType(ElementCount, false, ElementType);
+  if (!NarrowType)
+    return std::unexpected(NarrowType.error());
+  const std::size_t RegisterElementCount = RegisterType->minimumElementCount();
+  const std::size_t LeftoverElementCount = RegisterElementCount % ElementCount;
+  const std::size_t NarrowPartCount = RegisterElementCount / ElementCount;
+
+  if (LeftoverElementCount == 0)
+    return extractParts(Reg, *NarrowType, static_cast<int>(NarrowPartCount), Parts, MIRBuilder,
+                        MRI);
+
+  std::vector<Register> Elements;
+  auto Extracted = extractParts(Reg, ElementType, static_cast<int>(RegisterElementCount), Elements,
+                                MIRBuilder, MRI);
+  if (!Extracted)
+    return std::unexpected(Extracted.error());
+
+  std::size_t Offset = 0;
+  for (std::size_t Index = 0; Index != NarrowPartCount; ++Index, Offset += ElementCount) {
+    std::vector<Register> Piece(Elements.begin() + static_cast<std::ptrdiff_t>(Offset),
+                                Elements.begin() +
+                                    static_cast<std::ptrdiff_t>(Offset + ElementCount));
+    auto Part = MRI.createVirtualRegister(*NarrowType);
+    if (!Part)
+      return std::unexpected(Part.error());
+    auto Built = MIRBuilder.buildMergeLikeInstr(*Part, Piece);
+    if (!Built)
+      return std::unexpected(Built.error());
+    Parts.push_back(*Part);
+  }
+
+  if (LeftoverElementCount == 1) {
+    Parts.push_back(Elements[Offset]);
+    return {};
+  }
+
+  auto LeftoverType = LowLevelType::makeFixedVector(LeftoverElementCount, ElementType);
+  if (!LeftoverType)
+    return std::unexpected(LeftoverType.error());
+  std::vector<Register> LeftoverElements(Elements.begin() + static_cast<std::ptrdiff_t>(Offset),
+                                         Elements.end());
+  auto Leftover = MRI.createVirtualRegister(*LeftoverType);
+  if (!Leftover)
+    return std::unexpected(Leftover.error());
+  auto Built = MIRBuilder.buildMergeLikeInstr(*Leftover, LeftoverElements);
+  if (!Built)
+    return std::unexpected(Built.error());
+  Parts.push_back(*Leftover);
+  return {};
+}
+
+} // namespace
+
+bool isTriviallyDead(const MachineInstr &Instruction, const MachineRegisterInfo &MRI,
+                     const TargetDescription &Target) noexcept {
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    if (!Operand.isRegister() || !Operand.isDef())
+      continue;
+    const std::optional<Register> Reg = Operand.registerValue();
+    if (!Reg || Reg->isPhysical() || !MRI.useEmpty(*Reg, false))
+      return false;
+  }
+
+  const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
+  return Descriptor != nullptr && wouldBeTriviallyDead(Instruction, *Descriptor);
+}
+
+Expected<void> eraseInstrs(std::span<MachineInstr *const> Instructions, MachineRegisterInfo &MRI,
+                           const TargetDescription &Target) {
+  std::vector<MachineInstr *> DeadChain;
+  for (MachineInstr *Instruction : Instructions) {
+    if (Instruction == nullptr || Instruction->parent() == nullptr)
+      continue;
+    auto Removed = saveUsesAndErase(*Instruction, MRI, DeadChain);
+    if (!Removed)
+      return std::unexpected(Removed.error());
+  }
+
+  while (!DeadChain.empty()) {
+    MachineInstr *Instruction = DeadChain.back();
+    DeadChain.pop_back();
+    if (Instruction == nullptr || Instruction->parent() == nullptr ||
+        !isTriviallyDead(*Instruction, MRI, Target))
+      continue;
+    auto Removed = saveUsesAndErase(*Instruction, MRI, DeadChain);
+    if (!Removed)
+      return std::unexpected(Removed.error());
+  }
+  return {};
+}
+
+Expected<void> eraseInstr(MachineInstr &Instruction, MachineRegisterInfo &MRI,
+                          const TargetDescription &Target) {
+  MachineInstr *Instructions[] = {&Instruction};
+  return eraseInstrs(Instructions, MRI, Target);
+}
+
+Expected<void> extractParts(Register Reg, LowLevelType Type, int PartCount,
+                            std::vector<Register> &Parts, MachineIRBuilder &MIRBuilder,
+                            MachineRegisterInfo &MRI) {
+  std::vector<Register> NewParts;
+  if (PartCount < 0)
+    return makeUnexpected(ErrorCode::InvalidArgument, "part count cannot be negative");
+  NewParts.reserve(static_cast<std::size_t>(PartCount));
+  for (int Index = 0; Index != PartCount; ++Index) {
+    auto Part = MRI.createVirtualRegister(Type);
+    if (!Part)
+      return std::unexpected(Part.error());
+    NewParts.push_back(*Part);
+  }
+  auto Built = MIRBuilder.buildUnmergeValues(NewParts, Reg);
+  if (!Built)
+    return std::unexpected(Built.error());
+  Parts.insert(Parts.end(), NewParts.begin(), NewParts.end());
+  return {};
+}
+
+Expected<bool> extractParts(Register Reg, LowLevelType RegisterType, LowLevelType MainType,
+                            LowLevelType &LeftoverType, std::vector<Register> &Parts,
+                            std::vector<Register> &LeftoverParts, MachineIRBuilder &MIRBuilder,
+                            MachineRegisterInfo &MRI) {
+  if (LeftoverType.isValid()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "part extraction leftover type must be an output");
+  }
+
+  const std::uint64_t RegisterSize = RegisterType.minimumBitWidth();
+  const std::uint64_t MainSize = MainType.minimumBitWidth();
+  if (MainSize == 0 || MainSize > RegisterSize) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "part extraction requires a smaller nonzero main type");
+  }
+  const std::size_t PartCount = RegisterSize / MainSize;
+  const std::uint64_t LeftoverSize = RegisterSize - PartCount * MainSize;
+
+  if (LeftoverSize == 0) {
+    auto Extracted =
+        extractParts(Reg, MainType, static_cast<int>(PartCount), Parts, MIRBuilder, MRI);
+    if (!Extracted)
+      return std::unexpected(Extracted.error());
+    return true;
+  }
+
+  if (RegisterType.isVector() && MainType.isVector() && !RegisterType.isScalableVector() &&
+      !MainType.isScalableVector()) {
+    const std::size_t RegisterElementCount = RegisterType.minimumElementCount();
+    const std::size_t MainElementCount = MainType.minimumElementCount();
+    const std::size_t LeftoverElementCount = RegisterElementCount % MainElementCount;
+    if (LeftoverElementCount > 1 && MainElementCount % LeftoverElementCount == 0 &&
+        RegisterElementCount % LeftoverElementCount == 0 &&
+        RegisterType.scalarBitWidth() == MainType.scalarBitWidth()) {
+      auto Candidate =
+          LowLevelType::makeFixedVector(LeftoverElementCount, *RegisterType.scalarElementType());
+      if (!Candidate)
+        return std::unexpected(Candidate.error());
+      LeftoverType = *Candidate;
+
+      std::vector<Register> Unmerged;
+      auto Extracted = extractParts(Reg, LeftoverType,
+                                    static_cast<int>(RegisterElementCount / LeftoverElementCount),
+                                    Unmerged, MIRBuilder, MRI);
+      if (!Extracted)
+        return std::unexpected(Extracted.error());
+
+      const std::size_t LeftoversPerMain = MainElementCount / LeftoverElementCount;
+      const std::size_t LeftoverValueCount =
+          (RegisterElementCount % MainElementCount) / LeftoverElementCount;
+      std::vector<Register> MergeValues;
+      for (std::size_t Index = 0; Index != Unmerged.size() - LeftoverValueCount; ++Index) {
+        MergeValues.push_back(Unmerged[Index]);
+        if (MergeValues.size() != LeftoversPerMain)
+          continue;
+        auto Part = MRI.createVirtualRegister(MainType);
+        if (!Part)
+          return std::unexpected(Part.error());
+        auto Built = MIRBuilder.buildMergeLikeInstr(*Part, MergeValues);
+        if (!Built)
+          return std::unexpected(Built.error());
+        Parts.push_back(*Part);
+        MergeValues.clear();
+      }
+      LeftoverParts.insert(LeftoverParts.end(),
+                           Unmerged.end() - static_cast<std::ptrdiff_t>(LeftoverValueCount),
+                           Unmerged.end());
+      return true;
+    }
+  }
+
+  if (MainType.isVector()) {
+    std::vector<Register> RegisterPieces;
+    auto Extracted =
+        extractVectorParts(Reg, MainType.minimumElementCount(), RegisterPieces, MIRBuilder, MRI);
+    if (!Extracted)
+      return std::unexpected(Extracted.error());
+    Parts.insert(Parts.end(), RegisterPieces.begin(), std::prev(RegisterPieces.end()));
+    LeftoverParts.push_back(RegisterPieces.back());
+    auto Type = MRI.getType(LeftoverParts.front());
+    if (!Type)
+      return std::unexpected(Type.error());
+    LeftoverType = *Type;
+    return true;
+  }
+
+  auto ScalarLeftover = LowLevelType::makeCategoryNeutralScalar(LeftoverSize);
+  if (!ScalarLeftover)
+    return std::unexpected(ScalarLeftover.error());
+  LeftoverType = *ScalarLeftover;
+  for (std::size_t Index = 0; Index != PartCount; ++Index) {
+    auto Part = MRI.createVirtualRegister(MainType);
+    if (!Part)
+      return std::unexpected(Part.error());
+    auto Built = MIRBuilder.buildExtract(*Part, Reg, MainSize * Index);
+    if (!Built)
+      return std::unexpected(Built.error());
+    Parts.push_back(*Part);
+  }
+  for (std::uint64_t Offset = MainSize * PartCount; Offset < RegisterSize; Offset += LeftoverSize) {
+    auto Part = MRI.createVirtualRegister(LeftoverType);
+    if (!Part)
+      return std::unexpected(Part.error());
+    auto Built = MIRBuilder.buildExtract(*Part, Reg, Offset);
+    if (!Built)
+      return std::unexpected(Built.error());
+    LeftoverParts.push_back(*Part);
+  }
+  return true;
+}
+
+Expected<LowLevelType> getLCMType(LowLevelType OriginalType, LowLevelType TargetType) {
+  if (OriginalType.minimumBitWidth() == TargetType.minimumBitWidth())
+    return OriginalType;
+  if ((OriginalType.isScalableVector() && TargetType.isVector() &&
+       !TargetType.isScalableVector()) ||
+      (TargetType.isScalableVector() && OriginalType.isVector() &&
+       !OriginalType.isScalableVector())) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "LCM type is undefined between fixed and scalable vectors");
+  }
+
+  if (OriginalType.isVector() && TargetType.isVector()) {
+    const LowLevelType OriginalElement = *OriginalType.scalarElementType();
+    const LowLevelType TargetElement = *TargetType.scalarElementType();
+    if (OriginalElement.minimumBitWidth() == TargetElement.minimumBitWidth()) {
+      const std::uint64_t ElementCount =
+          std::lcm(static_cast<std::uint64_t>(OriginalType.minimumElementCount()),
+                   static_cast<std::uint64_t>(TargetType.minimumElementCount()));
+      return makeVectorType(ElementCount, OriginalType.isScalableVector(), OriginalElement);
+    }
+    const std::uint64_t Width =
+        std::lcm(OriginalType.minimumBitWidth(), TargetType.minimumBitWidth());
+    return makeVectorType(Width / OriginalElement.minimumBitWidth(),
+                          OriginalType.isScalableVector(), OriginalElement);
+  }
+
+  if (OriginalType.isVector() || TargetType.isVector()) {
+    const LowLevelType VectorType = OriginalType.isVector() ? OriginalType : TargetType;
+    const LowLevelType ScalarType = OriginalType.isVector() ? TargetType : OriginalType;
+    const LowLevelType VectorElement = *VectorType.scalarElementType();
+    const LowLevelType OriginalElement =
+        OriginalType.isVector() ? *OriginalType.scalarElementType() : OriginalType;
+    if (VectorElement.minimumBitWidth() == ScalarType.minimumBitWidth())
+      return makeVectorType(VectorType.minimumElementCount(), VectorType.isScalableVector(),
+                            OriginalElement);
+    const std::uint64_t Width =
+        std::lcm(VectorType.minimumBitWidth(), ScalarType.minimumBitWidth());
+    return makeVectorType(Width / OriginalElement.minimumBitWidth(), VectorType.isScalableVector(),
+                          OriginalElement);
+  }
+
+  const std::uint64_t Width =
+      std::lcm(OriginalType.minimumBitWidth(), TargetType.minimumBitWidth());
+  if (Width == OriginalType.minimumBitWidth())
+    return OriginalType;
+  if (Width == TargetType.minimumBitWidth())
+    return TargetType;
+  return LowLevelType::makeCategoryNeutralScalar(Width);
+}
+
+Expected<LowLevelType> getGCDType(LowLevelType OriginalType, LowLevelType TargetType) {
+  if (OriginalType.minimumBitWidth() == TargetType.minimumBitWidth())
+    return OriginalType;
+  if ((OriginalType.isScalableVector() && TargetType.isVector() &&
+       !TargetType.isScalableVector()) ||
+      (TargetType.isScalableVector() && OriginalType.isVector() &&
+       !OriginalType.isScalableVector())) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "GCD type is undefined between fixed and scalable vectors");
+  }
+
+  if (OriginalType.isVector() && TargetType.isVector()) {
+    const LowLevelType OriginalElement = *OriginalType.scalarElementType();
+    const std::uint64_t Width =
+        std::gcd(OriginalType.minimumBitWidth(), TargetType.minimumBitWidth());
+    if (Width == OriginalElement.minimumBitWidth())
+      return makeVectorType(1, OriginalType.isScalableVector(), OriginalElement);
+    if (Width < OriginalElement.minimumBitWidth())
+      return LowLevelType::makeCategoryNeutralScalar(Width);
+    return makeVectorType(Width / OriginalElement.minimumBitWidth(),
+                          OriginalType.isScalableVector(), OriginalElement);
+  }
+
+  if (OriginalType.isVector() && OriginalType.scalarBitWidth() == TargetType.minimumBitWidth())
+    return *OriginalType.scalarElementType();
+  if (TargetType.isVector() && TargetType.scalarBitWidth() == OriginalType.minimumBitWidth())
+    return OriginalType;
+
+  const std::uint64_t OriginalScalarWidth = OriginalType.scalarBitWidth();
+  const std::uint64_t TargetScalarWidth = TargetType.scalarBitWidth();
+  return LowLevelType::makeCategoryNeutralScalar(std::gcd(OriginalScalarWidth, TargetScalarWidth));
+}
+
+} // namespace rcc