[CodeGen] Match LLVM machine combiner semantics

6 files changed, 179 insertions, 343 deletions

diff --git a/backend/include/rcc/CodeGen/MachineCombiner.h b/backend/include/rcc/CodeGen/MachineCombiner.h
index 3850b91..42ca301 100644
--- a/backend/include/rcc/CodeGen/MachineCombiner.h
+++ b/backend/include/rcc/CodeGen/MachineCombiner.h
@@ -17,9 +17,9 @@ struct MachineCombinerOptions final {
 
 class MachineCombinerPass final : public MachineFunctionPass {
 public:
-  MachineCombinerPass(const TargetMachineCombinerInfo &Info, MachineCombinerStage Stage,
+  MachineCombinerPass(const TargetMachineCombinerInfo &Info,
                       MachineCombinerOptions Options = {}) noexcept
-      : Info(&Info), Stage(Stage), Options(Options) {}
+      : Info(&Info), Options(Options) {}
 
   [[nodiscard]] const MachinePassContract &contract() const noexcept override;
   [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
@@ -32,7 +32,6 @@ private:
                                                               MachineActionReplay &Actions) const;
 
   const TargetMachineCombinerInfo *Info;
-  MachineCombinerStage Stage;
   MachineCombinerOptions Options;
 };
 
diff --git a/backend/include/rcc/CodeGen/MachineCombinerPattern.h b/backend/include/rcc/CodeGen/MachineCombinerPattern.h
index 62819ef..3d590f9 100644
--- a/backend/include/rcc/CodeGen/MachineCombinerPattern.h
+++ b/backend/include/rcc/CodeGen/MachineCombinerPattern.h
@@ -7,7 +7,6 @@
 #include "rcc/Support/Error.h"
 
 #include <cstddef>
-#include <cstdint>
 #include <span>
 #include <string>
 #include <unordered_map>
@@ -15,51 +14,13 @@
 
 namespace rcc {
 
-enum class MachineCombinerStage : std::uint8_t {
-  PreLegalizer,
-  SelectedSSA,
-  PreRegisterAllocation,
-  PostRegisterAllocation,
-};
-
-using MachineCombinerStageMask = std::uint8_t;
-
-[[nodiscard]] constexpr MachineCombinerStageMask
-machineCombinerStageMask(MachineCombinerStage Stage) noexcept {
-  return static_cast<MachineCombinerStageMask>(1U << static_cast<std::uint8_t>(Stage));
-}
-
-enum class MachineCombinerPredicateKind : std::uint8_t {
-  ImmediateEquals,
-  RegisterEquals,
-  PhysicalRegisterEquals,
-  RegisterIsVirtual,
-  RegisterIsPhysical,
-};
-
-struct MachineCombinerPredicate final {
-  MachineCombinerPredicateKind Kind = MachineCombinerPredicateKind::ImmediateEquals;
-  std::size_t Operand = 0;
-  std::size_t OtherOperand = 0;
-  std::int64_t Value = 0;
-};
-
-enum class MachineCombinerActionKind : std::uint8_t {
-  ReplaceDefWithOperandAndErase,
-};
-
-struct MachineCombinerAction final {
-  MachineCombinerActionKind Kind = MachineCombinerActionKind::ReplaceDefWithOperandAndErase;
-  std::size_t DefinitionOperand = 0;
-  std::size_t SourceOperand = 0;
-};
-
 struct MachineCombinerPattern final {
   std::string Name;
   Opcode RootOpcode;
-  MachineCombinerStageMask Stages = 0;
-  std::vector<MachineCombinerPredicate> Predicates;
-  MachineCombinerAction Action;
+  Opcode ProducerOpcode;
+  Opcode ReplacementOpcode;
+  std::size_t ProducerOperand = 0;
+  std::size_t AddendOperand = 0;
 };
 
 class TargetMachineCombinerInfo final {
diff --git a/backend/lib/CodeGen/MachineCombiner.cpp b/backend/lib/CodeGen/MachineCombiner.cpp
index 1075180..1c0bc62 100644
--- a/backend/lib/CodeGen/MachineCombiner.cpp
+++ b/backend/lib/CodeGen/MachineCombiner.cpp
@@ -2,50 +2,31 @@
 
 #include "rcc/CodeGen/MachineCombiner.h"
 
-#include "rcc/CodeGen/InstructionDescriptor.h"
-#include "rcc/CodeGen/LiveVariables.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineFunctionCloner.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 "rcc/CodeGen/TargetRegisterInfo.h"
 
 #include <cstddef>
 #include <cstdint>
 #include <optional>
-#include <span>
 #include <string>
-#include <utility>
-#include <vector>
 
 namespace rcc {
 namespace {
 
-[[nodiscard]] const MachinePassContract &combinerContract(MachineCombinerStage Stage) {
-  static const MachinePassContract PreLegalizer = [] {
+[[nodiscard]] const MachinePassContract &combinerContract() {
+  static const MachinePassContract Contract = [] {
     MachinePassContract Value{
-        .Name = "riscv-prelegalizer-combiner",
+        .Name = "machine-combiner",
         .Requires = {MachineFunctionProperty::IsSSA},
         .Sets = {},
         .Clears = {},
         .RequiredAnalyses = {},
-        .VerificationStage = PipelineStage::MachineIRInput,
-    };
-    Value.ThreadSafety = PassThreadSafety::ThreadSafe;
-    Value.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands,
-                             MachinePassChange::Registers};
-    return Value;
-  }();
-  static const MachinePassContract SelectedSSA = [] {
-    MachinePassContract Value{
-        .Name = "machine-combiner-selected-ssa",
-        .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::IsSSA},
-        .Sets = {},
-        .Clears = {},
-        .RequiredAnalyses = {},
         .VerificationStage = PipelineStage::Selected,
     };
     Value.ThreadSafety = PassThreadSafety::ThreadSafe;
@@ -53,46 +34,7 @@ namespace {
                              MachinePassChange::Registers};
     return Value;
   }();
-  static const MachinePassContract PreRA = [] {
-    MachinePassContract Value{
-        .Name = "machine-combiner-pre-ra",
-        .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
-                     MachineFunctionProperty::TiedOpsRewritten},
-        .Sets = {},
-        .Clears = {},
-        .RequiredAnalyses = {},
-        .VerificationStage = PipelineStage::TiedOpsRewritten,
-    };
-    Value.ThreadSafety = PassThreadSafety::ThreadSafe;
-    Value.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands,
-                             MachinePassChange::Registers};
-    return Value;
-  }();
-  static const MachinePassContract PostRA = [] {
-    MachinePassContract Value{
-        .Name = "machine-combiner-post-ra",
-        .Requires = {},
-        .Sets = {},
-        .Clears = {},
-        .RequiredAnalyses = {},
-        .VerificationStage = PipelineStage::RegisterAllocated,
-    };
-    Value.ThreadSafety = PassThreadSafety::ThreadSafe;
-    Value.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands,
-                             MachinePassChange::Registers};
-    return Value;
-  }();
-  switch (Stage) {
-  case MachineCombinerStage::PreLegalizer:
-    return PreLegalizer;
-  case MachineCombinerStage::SelectedSSA:
-    return SelectedSSA;
-  case MachineCombinerStage::PreRegisterAllocation:
-    return PreRA;
-  case MachineCombinerStage::PostRegisterAllocation:
-    return PostRA;
-  }
-  return PreLegalizer;
+  return Contract;
 }
 
 [[nodiscard]] bool hasProtectedAttachment(const MachineInstr &Instruction) noexcept {
@@ -104,170 +46,159 @@ namespace {
          Instruction.cfiType().has_value() || Instruction.deactivationSymbol().has_value();
 }
 
-[[nodiscard]] bool matchesPredicate(const MachineInstr &Instruction,
-                                    const MachineCombinerPredicate &Predicate) {
-  const MachineOperand *Operand = Instruction.operandAt(Predicate.Operand);
-  if (Operand == nullptr)
-    return false;
-  switch (Predicate.Kind) {
-  case MachineCombinerPredicateKind::ImmediateEquals: {
-    const auto *Immediate = Operand->getIf<std::int64_t>();
-    return Immediate != nullptr && *Immediate == Predicate.Value;
-  }
-  case MachineCombinerPredicateKind::RegisterEquals: {
-    const MachineOperand *Other = Instruction.operandAt(Predicate.OtherOperand);
-    const Register *LeftReg = Operand->getIf<Register>();
-    const Register *RightReg = Other == nullptr ? nullptr : Other->getIf<Register>();
-    return LeftReg != nullptr && RightReg != nullptr && *LeftReg == *RightReg &&
-           Operand->subReg() == Other->subReg();
+[[nodiscard]] MachineInstrFlags intersectFlags(MachineInstrFlags Left,
+                                               MachineInstrFlags Right) noexcept {
+  MachineInstrFlags Result;
+  for (std::uint32_t Index = 0; Index < static_cast<std::uint32_t>(MachineInstrFlag::Count);
+       ++Index) {
+    const auto Flag = static_cast<MachineInstrFlag>(Index);
+    if (Left.has(Flag) && Right.has(Flag))
+      Result.set(Flag);
   }
-  case MachineCombinerPredicateKind::PhysicalRegisterEquals: {
-    const Register *Reg = Operand->getIf<Register>();
-    const std::optional<PhysicalRegister> Physical =
-        Reg == nullptr ? std::nullopt : Reg->physicalRegister();
-    return Physical && Physical->number() == static_cast<std::uint32_t>(Predicate.Value);
+  return Result;
+}
+
+[[nodiscard]] bool hasEqualRoundingMode(const MachineInstr &Root,
+                                        const MachineInstr &Producer) noexcept {
+  const MachineOperand *RootMode = Root.operandAt(3);
+  const MachineOperand *ProducerMode = Producer.operandAt(3);
+  const auto *RootImmediate = RootMode == nullptr ? nullptr : RootMode->getIf<std::int64_t>();
+  const auto *ProducerImmediate =
+      ProducerMode == nullptr ? nullptr : ProducerMode->getIf<std::int64_t>();
+  return RootImmediate != nullptr && ProducerImmediate != nullptr &&
+         *RootImmediate == *ProducerImmediate;
+}
+
+[[nodiscard]] MachineInstr *findProducer(MachineInstr &Root,
+                                         const MachineCombinerPattern &Pattern) noexcept {
+  const MachineOperand *ProducerUse = Root.operandAt(Pattern.ProducerOperand);
+  const Register *ProducerRegister =
+      ProducerUse == nullptr ? nullptr : ProducerUse->getIf<Register>();
+  if (ProducerRegister == nullptr || !ProducerUse->isUse() || !ProducerRegister->isVirtual()) {
+    return nullptr;
   }
-  case MachineCombinerPredicateKind::RegisterIsVirtual: {
-    const Register *Reg = Operand->getIf<Register>();
-    return Reg != nullptr && Reg->isVirtual();
+  MachineInstr *Producer = Root.function().registerInfo().getVRegDef(*ProducerRegister);
+  if (Producer == nullptr || Producer->opcode() != Pattern.ProducerOpcode ||
+      Producer->parent() != Root.parent() || Producer->operandCount() < 4 ||
+      hasProtectedAttachment(*Producer)) {
+    return nullptr;
   }
-  case MachineCombinerPredicateKind::RegisterIsPhysical: {
-    const Register *Reg = Operand->getIf<Register>();
-    return Reg != nullptr && Reg->isPhysical();
+  const MachineOperand *Definition = Producer->operandAt(0);
+  const Register *DefinedRegister = Definition == nullptr ? nullptr : Definition->getIf<Register>();
+  if (DefinedRegister == nullptr || !Definition->isDef() || Definition->isUse() ||
+      *DefinedRegister != *ProducerRegister) {
+    return nullptr;
   }
+  if (!Root.flags().has(MachineInstrFlag::FastMathAllowContract) ||
+      !Producer->flags().has(MachineInstrFlag::FastMathAllowContract) ||
+      !hasEqualRoundingMode(Root, *Producer)) {
+    return nullptr;
   }
-  return false;
+  return Producer;
 }
 
-[[nodiscard]] bool matchesPattern(const MachineInstr &Instruction,
-                                  const MachineCombinerPattern &Pattern,
-                                  MachineCombinerStage Stage) {
-  if ((Pattern.Stages & machineCombinerStageMask(Stage)) == 0)
-    return false;
-  for (const MachineCombinerPredicate &Predicate : Pattern.Predicates) {
-    if (!matchesPredicate(Instruction, Predicate))
-      return false;
+[[nodiscard]] Expected<void> clearKillFlags(MachineRegisterInfo &Registers, Register Reg) {
+  for (MachineOperand &Operand : Registers.regOperands(Reg)) {
+    RegisterOperandFlags Flags = Operand.registerFlags();
+    if (!Flags.has(RegisterOperandFlag::Kill))
+      continue;
+    Flags.clear(RegisterOperandFlag::Kill);
+    auto Changed = Operand.setRegisterFlags(Flags);
+    if (!Changed)
+      return std::unexpected(Changed.error());
   }
-  return true;
+  return {};
 }
 
-[[nodiscard]] bool compatibleReplacement(Register Destination, Register Source,
-                                         const MachineFunction &Function,
-                                         const TargetDescription &Target) {
-  if (!Destination.isVirtual() || Source.isNoRegister())
-    return false;
-  auto DestinationInfo = Function.registerInfo().virtualRegisterInfo(Destination);
-  if (!DestinationInfo)
-    return false;
-  const VirtualRegisterInfo &DestinationValue = DestinationInfo->get();
-  if (Source.isPhysical()) {
-    const std::optional<PhysicalRegister> Physical = Source.physicalRegister();
-    if (!Physical)
-      return false;
-    if (DestinationValue.RegClass &&
-        !Target.registers().registerClassContains(*DestinationValue.RegClass, *Physical)) {
-      return false;
-    }
-    return !DestinationValue.Bank ||
-           Target.registers().bankContainsRegister(*DestinationValue.Bank, *Physical);
-  }
-  auto SourceInfo = Function.registerInfo().virtualRegisterInfo(Source);
-  if (!SourceInfo)
-    return false;
-  const VirtualRegisterInfo &SourceValue = SourceInfo->get();
-  if (DestinationValue.Type != SourceValue.Type)
-    return false;
-  if (DestinationValue.Bank &&
-      (!SourceValue.Bank ||
-       !Target.registers().registerBanksOverlap(*DestinationValue.Bank, *SourceValue.Bank))) {
+[[nodiscard]] Expected<bool> combineFusedMultiplyAdd(MachineInstr &Root, MachineInstr &Producer,
+                                                     const MachineCombinerPattern &Pattern,
+                                                     MachineFunction &Function,
+                                                     const TargetDescription &Target) {
+  const MachineOperand *RootDefinition = Root.operandAt(0);
+  const MachineOperand *MultiplyLeft = Producer.operandAt(1);
+  const MachineOperand *MultiplyRight = Producer.operandAt(2);
+  const MachineOperand *Addend = Root.operandAt(Pattern.AddendOperand);
+  const Register *ProducerResult = Producer.operandAt(0)->getIf<Register>();
+  const Register *MultiplyLeftRegister =
+      MultiplyLeft == nullptr ? nullptr : MultiplyLeft->getIf<Register>();
+  const Register *MultiplyRightRegister =
+      MultiplyRight == nullptr ? nullptr : MultiplyRight->getIf<Register>();
+  if (RootDefinition == nullptr || MultiplyLeftRegister == nullptr ||
+      MultiplyRightRegister == nullptr || Addend == nullptr || ProducerResult == nullptr) {
     return false;
   }
-  if (DestinationValue.RegClass &&
-      (!SourceValue.RegClass || !Target.registers().registerClassesOverlap(
-                                    *DestinationValue.RegClass, *SourceValue.RegClass))) {
-    return false;
-  }
-  return true;
-}
 
-[[nodiscard]] Expected<bool> executeReplacement(MachineInstr &Instruction,
-                                                const MachineCombinerAction &Action,
-                                                MachineFunction &Function,
-                                                const TargetDescription &Target) {
-  MachineOperand *Definition = Instruction.operandAt(Action.DefinitionOperand);
-  const MachineOperand *SourceOperand = Instruction.operandAt(Action.SourceOperand);
-  const Register *Destination = Definition == nullptr ? nullptr : Definition->getIf<Register>();
-  const Register *Source = SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>();
-  if (Destination == nullptr || Source == nullptr || !Definition->isDef() || Definition->isUse() ||
-      !SourceOperand->isUse() || Definition->subReg().value() != 0 ||
-      SourceOperand->subReg().value() != 0 || Destination->isNoRegister() ||
-      Source->isNoRegister()) {
-    return false;
-  }
-  MachineBasicBlock *Block = Instruction.parent();
-  if (Block == nullptr)
-    return makeUnexpected(ErrorCode::InternalError, "machine combiner root is detached");
+  MachineRegisterInfo &Registers = Function.registerInfo();
+  const bool EraseProducer = Registers.hasOneUse(*ProducerResult, false);
+  auto Cleared = clearKillFlags(Registers, *MultiplyLeftRegister);
+  if (!Cleared)
+    return std::unexpected(Cleared.error());
+  Cleared = clearKillFlags(Registers, *MultiplyRightRegister);
+  if (!Cleared)
+    return std::unexpected(Cleared.error());
 
-  if (*Destination == *Source) {
-    auto Removed = Block->removeInstruction(Instruction);
-    if (!Removed)
-      return std::unexpected(Removed.error());
-    return true;
+  MachineIRBuilder Builder(Function, Target);
+  auto Point = Builder.setInsertPointBefore(Root);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(Pattern.ReplacementOpcode);
+  if (!Pending)
+    return std::unexpected(Pending.error());
+
+  auto Added = Pending->addOperand(RootDefinition->cloneDetached());
+  if (!Added)
+    return std::unexpected(Added.error());
+  Added = Pending->addOperand(MultiplyLeft->cloneDetached());
+  if (!Added)
+    return std::unexpected(Added.error());
+  Added = Pending->addOperand(MultiplyRight->cloneDetached());
+  if (!Added)
+    return std::unexpected(Added.error());
+  Added = Pending->addOperand(Addend->cloneDetached());
+  if (!Added)
+    return std::unexpected(Added.error());
+  Added = Pending->addOperand(Root.operandAt(3)->cloneDetached());
+  if (!Added)
+    return std::unexpected(Added.error());
+  for (std::size_t Index = 4; Index < Root.operandCount(); ++Index) {
+    Added = Pending->addImplicitOperand(Root.operandAt(Index)->cloneDetached());
+    if (!Added)
+      return std::unexpected(Added.error());
   }
-  if (!Destination->isVirtual() ||
-      Function.registerInfo().getUniqueVRegDef(*Destination) != Definition ||
-      !compatibleReplacement(*Destination, *Source, Function, Target)) {
-    return false;
+  Added = Pending->setFlags(intersectFlags(Root.flags(), Producer.flags()));
+  if (!Added)
+    return std::unexpected(Added.error());
+  if (Root.debugLocation()) {
+    Added = Pending->setDebugLocation(*Root.debugLocation());
+    if (!Added)
+      return std::unexpected(Added.error());
   }
+  auto Fused = Pending->build();
+  if (!Fused)
+    return std::unexpected(Fused.error());
 
-  std::vector<MachineOperand *> Uses;
-  for (MachineOperand &Use : Function.registerInfo().useOperands(*Destination, true))
-    Uses.push_back(&Use);
-  for (MachineOperand *Use : Uses) {
-    auto Replaced = Use->setRegister(*Source);
-    if (!Replaced)
-      return std::unexpected(Replaced.error());
-  }
-  auto Removed = Block->removeInstruction(Instruction);
+  MachineBasicBlock *Block = Root.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError, "machine combiner root is detached");
+  auto Removed = Block->removeInstruction(Root);
   if (!Removed)
     return std::unexpected(Removed.error());
-  if (!Function.registerInfo().useEmpty(*Destination, true) ||
-      Function.registerInfo().getUniqueVRegDef(*Destination) != nullptr) {
-    return makeUnexpected(ErrorCode::InternalError,
-                          "machine combiner left references to a replaced result");
+  if (EraseProducer) {
+    MachineBasicBlock *ProducerBlock = Producer.parent();
+    if (ProducerBlock == nullptr) {
+      return makeUnexpected(ErrorCode::InternalError, "machine combiner producer is detached");
+    }
+    Removed = ProducerBlock->removeInstruction(Producer);
+    if (!Removed)
+      return std::unexpected(Removed.error());
   }
-  auto Erased = Function.registerInfo().eraseVirtualRegister(*Destination);
-  if (!Erased)
-    return std::unexpected(Erased.error());
   return true;
 }
 
-[[nodiscard]] Expected<bool> executePattern(MachineInstr &Instruction,
-                                            const MachineCombinerPattern &Pattern,
-                                            MachineFunction &Function,
-                                            const TargetDescription &Target) {
-  const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
-  if (Descriptor == nullptr)
-    return makeUnexpected(ErrorCode::VerificationError, "machine combiner root has no descriptor");
-  const InstructionFlags Flags = Descriptor->Flags;
-  if (Flags.has(InstructionFlag::Terminator) || Flags.has(InstructionFlag::Call) ||
-      Flags.has(InstructionFlag::Barrier) || Flags.has(InstructionFlag::MayLoad) ||
-      Flags.has(InstructionFlag::MayStore) || Flags.has(InstructionFlag::HasSideEffects) ||
-      Flags.has(InstructionFlag::UnmodeledSideEffects) || !Instruction.memOperands().empty() ||
-      hasProtectedAttachment(Instruction)) {
-    return false;
-  }
-  switch (Pattern.Action.Kind) {
-  case MachineCombinerActionKind::ReplaceDefWithOperandAndErase:
-    return executeReplacement(Instruction, Pattern.Action, Function, Target);
-  }
-  return false;
-}
-
 } // namespace
 
 const MachinePassContract &MachineCombinerPass::contract() const noexcept {
-  return combinerContract(Stage);
+  return combinerContract();
 }
 
 Expected<MachinePassResult> MachineCombinerPass::run(MachineFunction &Function,
@@ -275,7 +206,7 @@ Expected<MachinePassResult> MachineCombinerPass::run(MachineFunction &Function,
                                                      MachineFunctionAnalysisManager &Analyses) {
   if (!Function.properties().containsAll(contract().Requires)) {
     return makeUnexpected(ErrorCode::VerificationError,
-                          "machine combiner input does not satisfy its stage contract");
+                          "machine combiner input does not satisfy its pass contract");
   }
   auto Trial = cloneMachineFunction(
       Function, Target,
@@ -315,10 +246,13 @@ MachineCombinerPass::runImplementation(MachineFunction &Function, const TargetDe
       for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;) {
         MachineInstr *Next = Instruction->next();
         for (const MachineCombinerPattern &Pattern : Info->patterns(Instruction->opcode())) {
-          if (!matchesPattern(*Instruction, Pattern, Stage))
-            continue;
           if (Rewrites == Options.MaximumRewrites)
             break;
+          if (hasProtectedAttachment(*Instruction) || Instruction->operandCount() < 4)
+            continue;
+          MachineInstr *Producer = findProducer(*Instruction, Pattern);
+          if (Producer == nullptr)
+            continue;
           std::string Rule = "combine.";
           Rule.append(Pattern.Name);
           auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
@@ -326,7 +260,8 @@ MachineCombinerPass::runImplementation(MachineFunction &Function, const TargetDe
             return std::unexpected(Accepted.error());
           if (!*Accepted)
             continue;
-          auto Executed = executePattern(*Instruction, Pattern, Function, Target);
+          auto Executed =
+              combineFusedMultiplyAdd(*Instruction, *Producer, Pattern, Function, Target);
           if (!Executed)
             return std::unexpected(Executed.error());
           if (!*Executed)
@@ -347,11 +282,6 @@ MachineCombinerPass::runImplementation(MachineFunction &Function, const TargetDe
     Result.Preserved = PreservedAnalyses::all();
     return Result;
   }
-  if (Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
-    auto Rebuilt = rebuildMachineLiveness(Function, Target);
-    if (!Rebuilt)
-      return std::unexpected(Rebuilt.error());
-  }
   Result.Changes = {MachinePassChange::Instructions, MachinePassChange::Operands,
                     MachinePassChange::Registers};
   Result.Preserved = PreservedAnalyses::none();
diff --git a/backend/lib/CodeGen/MachineCombinerPattern.cpp b/backend/lib/CodeGen/MachineCombinerPattern.cpp
index b1c3c96..f13ba73 100644
--- a/backend/lib/CodeGen/MachineCombinerPattern.cpp
+++ b/backend/lib/CodeGen/MachineCombinerPattern.cpp
@@ -2,8 +2,6 @@
 
 #include "rcc/CodeGen/MachineCombinerPattern.h"
 
-#include <cstddef>
-#include <ranges>
 #include <string>
 #include <unordered_set>
 #include <utility>
@@ -15,25 +13,12 @@ TargetMachineCombinerInfo::create(std::vector<MachineCombinerPattern> Patterns)
   TargetMachineCombinerInfo Result(std::move(Patterns));
   std::unordered_set<std::string> Names;
   for (const MachineCombinerPattern &Pattern : Result.Patterns) {
-    if (Pattern.Name.empty() || !Pattern.RootOpcode.isValid() || Pattern.Stages == 0 ||
-        !Names.insert(Pattern.Name).second) {
+    if (Pattern.Name.empty() || !Pattern.RootOpcode.isValid() ||
+        !Pattern.ProducerOpcode.isValid() || !Pattern.ReplacementOpcode.isValid() ||
+        Pattern.ProducerOperand == 0 || Pattern.AddendOperand == 0 ||
+        Pattern.ProducerOperand == Pattern.AddendOperand || !Names.insert(Pattern.Name).second) {
       return makeUnexpected(ErrorCode::InvalidArgument,
-                            "machine combiner pattern has an invalid identity or stage mask");
-    }
-    for (const MachineCombinerPredicate &Predicate : Pattern.Predicates) {
-      switch (Predicate.Kind) {
-      case MachineCombinerPredicateKind::ImmediateEquals:
-      case MachineCombinerPredicateKind::PhysicalRegisterEquals:
-      case MachineCombinerPredicateKind::RegisterIsVirtual:
-      case MachineCombinerPredicateKind::RegisterIsPhysical:
-        break;
-      case MachineCombinerPredicateKind::RegisterEquals:
-        if (Predicate.Operand == Predicate.OtherOperand) {
-          return makeUnexpected(ErrorCode::InvalidArgument,
-                                "register equality pattern compares an operand with itself");
-        }
-        break;
-      }
+                            "machine combiner pattern has an invalid target pattern");
     }
     Result.MatchTable[Pattern.RootOpcode].push_back(Pattern);
   }
diff --git a/backend/lib/CodeGen/MachineOptimizationPipeline.cpp b/backend/lib/CodeGen/MachineOptimizationPipeline.cpp
index 2badb78..812d78c 100644
--- a/backend/lib/CodeGen/MachineOptimizationPipeline.cpp
+++ b/backend/lib/CodeGen/MachineOptimizationPipeline.cpp
@@ -47,8 +47,7 @@ Expected<void> registerMachineOptimizationAnalyses(MachineFunctionAnalysisManage
 Expected<void>
 addSelectedSSAOptimizationPipeline(MachineFunctionPassManager &Pipeline,
                                    const MachineOptimizationPipelineTargetInfo &TargetInfo) {
-  auto Added = addPass<MachineCombinerPass>(Pipeline, TargetInfo.Combiner,
-                                            MachineCombinerStage::SelectedSSA);
+  auto Added = addPass<MachineCombinerPass>(Pipeline, TargetInfo.Combiner);
   if (!Added)
     return std::unexpected(Added.error());
   Added = addPass<MachineMemoryFoldingPass>(Pipeline, TargetInfo.MemoryFolding);
@@ -74,10 +73,6 @@ addSelectedSSAOptimizationPipeline(MachineFunctionPassManager &Pipeline,
 
 Expected<void> addPreRegisterAllocationOptimizationPipeline(
     MachineFunctionPassManager &Pipeline, const MachineOptimizationPipelineTargetInfo &TargetInfo) {
-  auto Added = addPass<MachineCombinerPass>(Pipeline, TargetInfo.Combiner,
-                                            MachineCombinerStage::PreRegisterAllocation);
-  if (!Added)
-    return std::unexpected(Added.error());
   return addPass<MachineSchedulerPass>(Pipeline, TargetInfo.SchedulingModel,
                                        TargetInfo.SchedulerOptions);
 }
@@ -89,10 +84,6 @@ addPostRegisterAllocationPipeline(MachineFunctionPassManager &Pipeline,
   auto Added = addPass<MachineStackSlotColoringPass>(Pipeline);
   if (!Added)
     return std::unexpected(Added.error());
-  Added = addPass<MachineCombinerPass>(Pipeline, TargetInfo.Combiner,
-                                       MachineCombinerStage::PostRegisterAllocation);
-  if (!Added)
-    return std::unexpected(Added.error());
   Added = addPass<MachineLICMPass>(Pipeline, MachineCodeMotionStage::PostRegisterAllocation);
   if (!Added)
     return std::unexpected(Added.error());
diff --git a/backend/lib/Target/RISCV/RISCVMachineCombiner.cpp b/backend/lib/Target/RISCV/RISCVMachineCombiner.cpp
index ffc27b0..dbb637e 100644
--- a/backend/lib/Target/RISCV/RISCVMachineCombiner.cpp
+++ b/backend/lib/Target/RISCV/RISCVMachineCombiner.cpp
@@ -3,77 +3,47 @@
 #include "RISCV.h"
 #include "rcc/Target/RISCV/RISCVTarget.h"
 
-#include <cstdint>
 #include <cstdlib>
-#include <string>
-#include <utility>
 #include <vector>
 
 namespace rcc::riscv {
 namespace {
 
-[[nodiscard]] constexpr MachineCombinerStageMask allOptimizationStages() noexcept {
-  return machineCombinerStageMask(MachineCombinerStage::SelectedSSA) |
-         machineCombinerStageMask(MachineCombinerStage::PreRegisterAllocation) |
-         machineCombinerStageMask(MachineCombinerStage::PostRegisterAllocation);
-}
-
-[[nodiscard]] MachineCombinerPattern immediateIdentity(InstructionOpcode OpcodeValue,
-                                                       std::string Name, std::int64_t Immediate) {
-  return {
-      .Name = std::move(Name),
-      .RootOpcode = instructionOpcode(OpcodeValue),
-      .Stages = allOptimizationStages(),
-      .Predicates = {{MachineCombinerPredicateKind::ImmediateEquals, 2, 0, Immediate}},
-      .Action = {MachineCombinerActionKind::ReplaceDefWithOperandAndErase, 0, 1},
-  };
-}
-
-[[nodiscard]] MachineCombinerPattern zeroRegisterIdentity(InstructionOpcode OpcodeValue,
-                                                          std::string Name, std::size_t ZeroOperand,
-                                                          std::size_t SourceOperand) {
+[[nodiscard]] MachineCombinerPattern
+fusedMultiplyAdd(const char *Name, InstructionOpcode RootOpcode, InstructionOpcode ProducerOpcode,
+                 InstructionOpcode ReplacementOpcode, std::size_t ProducerOperand,
+                 std::size_t AddendOperand) {
   return {
-      .Name = std::move(Name),
-      .RootOpcode = instructionOpcode(OpcodeValue),
-      .Stages = allOptimizationStages(),
-      .Predicates = {{MachineCombinerPredicateKind::PhysicalRegisterEquals, ZeroOperand, 0,
-                      static_cast<std::int64_t>(PhysicalRegisterID::X0)}},
-      .Action = {MachineCombinerActionKind::ReplaceDefWithOperandAndErase, 0, SourceOperand},
+      .Name = Name,
+      .RootOpcode = instructionOpcode(RootOpcode),
+      .ProducerOpcode = instructionOpcode(ProducerOpcode),
+      .ReplacementOpcode = instructionOpcode(ReplacementOpcode),
+      .ProducerOperand = ProducerOperand,
+      .AddendOperand = AddendOperand,
   };
 }
 
-[[nodiscard]] MachineCombinerPattern equalSourceIdentity(InstructionOpcode OpcodeValue,
-                                                         std::string Name) {
+[[nodiscard]] std::vector<MachineCombinerPattern> createPatterns() {
   return {
-      .Name = std::move(Name),
-      .RootOpcode = instructionOpcode(OpcodeValue),
-      .Stages = allOptimizationStages(),
-      .Predicates = {{MachineCombinerPredicateKind::RegisterEquals, 1, 2, 0}},
-      .Action = {MachineCombinerActionKind::ReplaceDefWithOperandAndErase, 0, 1},
+      fusedMultiplyAdd("fmadd-s-ax", InstructionOpcode::FADD_S, InstructionOpcode::FMUL_S,
+                       InstructionOpcode::FMADD_S, 1, 2),
+      fusedMultiplyAdd("fmadd-s-xa", InstructionOpcode::FADD_S, InstructionOpcode::FMUL_S,
+                       InstructionOpcode::FMADD_S, 2, 1),
+      fusedMultiplyAdd("fmsub-s", InstructionOpcode::FSUB_S, InstructionOpcode::FMUL_S,
+                       InstructionOpcode::FMSUB_S, 1, 2),
+      fusedMultiplyAdd("fnmsub-s", InstructionOpcode::FSUB_S, InstructionOpcode::FMUL_S,
+                       InstructionOpcode::FNMSUB_S, 2, 1),
+      fusedMultiplyAdd("fmadd-d-ax", InstructionOpcode::FADD_D, InstructionOpcode::FMUL_D,
+                       InstructionOpcode::FMADD_D, 1, 2),
+      fusedMultiplyAdd("fmadd-d-xa", InstructionOpcode::FADD_D, InstructionOpcode::FMUL_D,
+                       InstructionOpcode::FMADD_D, 2, 1),
+      fusedMultiplyAdd("fmsub-d", InstructionOpcode::FSUB_D, InstructionOpcode::FMUL_D,
+                       InstructionOpcode::FMSUB_D, 1, 2),
+      fusedMultiplyAdd("fnmsub-d", InstructionOpcode::FSUB_D, InstructionOpcode::FMUL_D,
+                       InstructionOpcode::FNMSUB_D, 2, 1),
   };
 }
 
-[[nodiscard]] std::vector<MachineCombinerPattern> createPatterns() {
-  std::vector<MachineCombinerPattern> Patterns;
-  Patterns.push_back(immediateIdentity(InstructionOpcode::ADDI, "addi-zero", 0));
-  Patterns.push_back(immediateIdentity(InstructionOpcode::XORI, "xori-zero", 0));
-  Patterns.push_back(immediateIdentity(InstructionOpcode::ORI, "ori-zero", 0));
-  Patterns.push_back(immediateIdentity(InstructionOpcode::ANDI, "andi-all-ones", -1));
-  Patterns.push_back(immediateIdentity(InstructionOpcode::SLLI, "slli-zero", 0));
-  Patterns.push_back(immediateIdentity(InstructionOpcode::SRLI, "srli-zero", 0));
-  Patterns.push_back(immediateIdentity(InstructionOpcode::SRAI, "srai-zero", 0));
-  Patterns.push_back(zeroRegisterIdentity(InstructionOpcode::ADD, "add-zero-right", 2, 1));
-  Patterns.push_back(zeroRegisterIdentity(InstructionOpcode::ADD, "add-zero-left", 1, 2));
-  Patterns.push_back(zeroRegisterIdentity(InstructionOpcode::OR, "or-zero-right", 2, 1));
-  Patterns.push_back(zeroRegisterIdentity(InstructionOpcode::OR, "or-zero-left", 1, 2));
-  Patterns.push_back(zeroRegisterIdentity(InstructionOpcode::XOR, "xor-zero-right", 2, 1));
-  Patterns.push_back(zeroRegisterIdentity(InstructionOpcode::XOR, "xor-zero-left", 1, 2));
-  Patterns.push_back(zeroRegisterIdentity(InstructionOpcode::SUB, "sub-zero-right", 2, 1));
-  Patterns.push_back(equalSourceIdentity(InstructionOpcode::FSGNJ_S, "fsgnj-s-copy"));
-  Patterns.push_back(equalSourceIdentity(InstructionOpcode::FSGNJ_D, "fsgnj-d-copy"));
-  return Patterns;
-}
-
 } // namespace
 
 const TargetMachineCombinerInfo &machineCombinerInfo() noexcept {