[GlobalISel] Match LLVM legalization value tracking

19 files changed, 2712 insertions, 478 deletions

diff --git a/backend/include/rcc/ADT/APInt.h b/backend/include/rcc/ADT/APInt.h
index 22ecf62..8b869be 100644
--- a/backend/include/rcc/ADT/APInt.h
+++ b/backend/include/rcc/ADT/APInt.h
@@ -43,7 +43,14 @@ public:
   [[nodiscard]] bool isNegative() const noexcept;
   [[nodiscard]] std::size_t activeBitWidth() const noexcept;
   [[nodiscard]] std::size_t countrZero() const noexcept;
+  [[nodiscard]] std::size_t countlOne() const noexcept;
+  [[nodiscard]] bool isAllOnes() const noexcept;
+  [[nodiscard]] bool testBit(std::size_t Bit) const noexcept;
   [[nodiscard]] std::uint64_t word(std::size_t Index) const noexcept;
+  [[nodiscard]] Expected<APInt> bitwiseAnd(const APInt &Other) const;
+  [[nodiscard]] Expected<APInt> bitwiseOr(const APInt &Other) const;
+  [[nodiscard]] Expected<APInt> bitwiseXor(const APInt &Other) const;
+  [[nodiscard]] Expected<APInt> bitwiseNot() const;
   [[nodiscard]] Expected<APInt> trunc(std::uint32_t NewBitWidth) const;
   [[nodiscard]] Expected<APInt> zext(std::uint32_t NewBitWidth) const;
   [[nodiscard]] Expected<APInt> sext(std::uint32_t NewBitWidth) const;
diff --git a/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h b/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h
new file mode 100644
index 0000000..aa02fe3
--- /dev/null
+++ b/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h
@@ -0,0 +1,53 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_GLOBALISEL_GISELVALUETRACKING_H
+#define RCC_CODEGEN_GLOBALISEL_GISELVALUETRACKING_H
+
+#include "rcc/ADT/APInt.h"
+#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+
+namespace rcc {
+
+class MachineFunction;
+class MachineRegisterInfo;
+class TargetDescription;
+
+class GISelValueTracking final : public GISelChangeObserver {
+public:
+  GISelValueTracking(MachineFunction &Function, const TargetDescription &Target,
+                     unsigned MaxDepth = 6) noexcept;
+
+  [[nodiscard]] const MachineFunction &getMachineFunction() const noexcept {
+    return Function;
+  }
+
+  [[nodiscard]] Expected<APInt> getKnownZeroes(Register Reg) const;
+  [[nodiscard]] Expected<std::uint32_t> computeNumSignBits(Register Reg, unsigned Depth = 0) const;
+
+  void erasingInstr(MachineInstr &) override {}
+  void createdInstr(MachineInstr &) override {}
+  void changingInstr(MachineInstr &) override {}
+  void changedInstr(MachineInstr &) override {}
+
+private:
+  struct KnownBits final {
+    APInt Zero;
+    APInt One;
+  };
+
+  [[nodiscard]] Expected<KnownBits> makeUnknown(std::uint32_t BitWidth) const;
+  [[nodiscard]] Expected<KnownBits> getKnownBits(Register Reg, unsigned Depth = 0) const;
+
+  MachineFunction &Function;
+  MachineRegisterInfo &MRI;
+  const TargetDescription &Target;
+  unsigned MaxDepth;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_GLOBALISEL_GISELVALUETRACKING_H
diff --git a/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h b/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
index c3f8d0b..7e2961d 100644
--- a/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
+++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
@@ -4,8 +4,9 @@
 #define RCC_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H
 
 #include "rcc/CodeGen/GenericOpcodes.h"
-#include "rcc/CodeGen/GlobalISel/GenericMachineInstrs.h"
 #include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+#include "rcc/CodeGen/GlobalISel/GISelValueTracking.h"
+#include "rcc/CodeGen/GlobalISel/GenericMachineInstrs.h"
 #include "rcc/CodeGen/GlobalISel/LegalizerInfo.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineIRBuilder.h"
@@ -30,6 +31,7 @@ class LegalizationArtifactCombiner final {
   MachineIRBuilder &Builder;
   MachineRegisterInfo &MRI;
   const LegalizerInfo &LI;
+  GISelValueTracking *VT;
 
   [[nodiscard]] static bool isArtifactCast(Opcode InstructionOpcode) noexcept {
     switch (static_cast<GenericOpcode>(InstructionOpcode.value())) {
@@ -45,13 +47,13 @@ class LegalizationArtifactCombiner final {
 
 public:
   LegalizationArtifactCombiner(MachineIRBuilder &Builder, MachineRegisterInfo &MRI,
-                               const LegalizerInfo &Info)
-      : Builder(Builder), MRI(MRI), LI(Info) {}
+                               const LegalizerInfo &Info,
+                               GISelValueTracking *ValueTracking = nullptr)
+      : Builder(Builder), MRI(MRI), LI(Info), VT(ValueTracking) {}
 
-  [[nodiscard]] Expected<bool>
-  tryCombineInstruction(MachineInstr &Instruction,
-                        std::vector<MachineInstr *> &DeadInstructions,
-                        GISelObserverWrapper &Observer) {
+  [[nodiscard]] Expected<bool> tryCombineInstruction(MachineInstr &Instruction,
+                                                     std::vector<MachineInstr *> &DeadInstructions,
+                                                     GISelObserverWrapper &Observer) {
     if (!DeadInstructions.empty()) {
       auto Deleted = deleteMarkedDeadInsts(DeadInstructions, Observer);
       if (!Deleted)
@@ -77,9 +79,23 @@ public:
       break;
     case GenericOpcode::G_MERGE_VALUES:
     case GenericOpcode::G_BUILD_VECTOR:
-    case GenericOpcode::G_CONCAT_VECTORS:
+    case GenericOpcode::G_CONCAT_VECTORS: {
+      const auto Destination = Instruction.operandAt(0)->registerValue();
+      if (Destination) {
+        for (MachineOperand &Use : MRI.useOperands(*Destination)) {
+          MachineInstr *User = Use.parent();
+          if (User == nullptr)
+            continue;
+          if (User->opcode() == opcode(GenericOpcode::G_UNMERGE_VALUES) ||
+              User->opcode() == opcode(GenericOpcode::G_TRUNC)) {
+            UpdatedDefs.push_back(*Destination);
+            break;
+          }
+        }
+      }
       Changed = tryCombineMergeLike(Instruction, DeadInstructions, UpdatedDefs, Observer);
       break;
+    }
     case GenericOpcode::G_EXTRACT:
       Changed = tryCombineExtract(Instruction, DeadInstructions, UpdatedDefs);
       break;
@@ -114,14 +130,12 @@ public:
         case GenericOpcode::G_ASSERT_SEXT:
         case GenericOpcode::G_ASSERT_ZEXT:
         case GenericOpcode::G_ASSERT_ALIGN:
-          if (const auto Copy = Use->operandAt(0)->registerValue();
-              Copy && Copy->isVirtual())
+          if (const auto Copy = Use->operandAt(0)->registerValue(); Copy && Copy->isVirtual())
             UpdatedDefs.push_back(*Copy);
           break;
         default:
           if (Use->opcode() == opcode(GenericOpcode::COPY)) {
-            if (const auto Copy = Use->operandAt(0)->registerValue();
-                Copy && Copy->isVirtual())
+            if (const auto Copy = Use->operandAt(0)->registerValue(); Copy && Copy->isVirtual())
               UpdatedDefs.push_back(*Copy);
           }
           break;
@@ -134,128 +148,107 @@ public:
 private:
   class ArtifactValueFinder final {
   public:
-    explicit ArtifactValueFinder(LegalizationArtifactCombiner &Combiner)
-        : Combiner(Combiner) {}
+    explicit ArtifactValueFinder(LegalizationArtifactCombiner &Combiner) : Combiner(Combiner) {}
 
-    [[nodiscard]] Expected<Register> findValueFromDef(Register DefReg,
-                                                      std::uint64_t StartBit,
+    [[nodiscard]] Expected<Register> findValueFromDef(Register DefReg, std::uint64_t StartBit,
                                                       std::uint64_t Size,
                                                       LowLevelType DestinationType);
+    [[nodiscard]] Expected<bool> tryCombineUnmergeDefs(GUnmerge &Instruction,
+                                                       GISelChangeObserver &Observer,
+                                                       std::vector<Register> &UpdatedDefs);
+    [[nodiscard]] Expected<GUnmerge *> findUnmergeThatDefinesReg(Register Reg, std::uint64_t Size,
+                                                                 std::size_t &DefOperandIndex);
     [[nodiscard]] Expected<bool>
-    tryCombineUnmergeDefs(GUnmerge &Instruction,
-                          GISelChangeObserver &Observer,
-                          std::vector<Register> &UpdatedDefs);
-    [[nodiscard]] Expected<GUnmerge *>
-    findUnmergeThatDefinesReg(Register Reg, std::uint64_t Size,
-                              std::size_t &DefOperandIndex);
-    [[nodiscard]] Expected<bool>
-    isSequenceFromUnmerge(GMergeLikeInstr &Instruction,
-                          std::size_t MergeStartIndex, GUnmerge *Unmerge,
-                          std::size_t UnmergeStartIndex,
-                          std::size_t ElementCount, std::uint64_t ElementSize,
-                          bool AllowUndef);
-    [[nodiscard]] Expected<bool>
-    tryCombineMergeLike(GMergeLikeInstr &Instruction,
-                        std::vector<MachineInstr *> &DeadInstructions,
-                        std::vector<Register> &UpdatedDefs,
-                        GISelChangeObserver &Observer);
+    isSequenceFromUnmerge(GMergeLikeInstr &Instruction, std::size_t MergeStartIndex,
+                          GUnmerge *Unmerge, std::size_t UnmergeStartIndex,
+                          std::size_t ElementCount, std::uint64_t ElementSize, bool AllowUndef);
+    [[nodiscard]] Expected<bool> tryCombineMergeLike(GMergeLikeInstr &Instruction,
+                                                     std::vector<MachineInstr *> &DeadInstructions,
+                                                     std::vector<Register> &UpdatedDefs,
+                                                     GISelChangeObserver &Observer);
 
   private:
+    [[nodiscard]] Expected<Register> findValueFromDefImpl(Register DefReg, std::uint64_t StartBit,
+                                                          std::uint64_t Size,
+                                                          LowLevelType DestinationType);
+    [[nodiscard]] Expected<Register> findValueFromConcat(GConcatVectors &Instruction,
+                                                         std::uint64_t StartBit, std::uint64_t Size,
+                                                         LowLevelType DestinationType);
     [[nodiscard]] Expected<Register>
-    findValueFromDefImpl(Register DefReg, std::uint64_t StartBit,
-                         std::uint64_t Size, LowLevelType DestinationType);
-    [[nodiscard]] Expected<Register>
-    findValueFromConcat(GConcatVectors &Instruction,
-                        std::uint64_t StartBit, std::uint64_t Size,
-                        LowLevelType DestinationType);
-    [[nodiscard]] Expected<Register>
-    findValueFromBuildVector(GBuildVector &Instruction,
-                             std::uint64_t StartBit, std::uint64_t Size);
-    [[nodiscard]] Expected<Register>
-    findValueFromInsert(MachineInstr &Instruction, std::uint64_t StartBit,
-                        std::uint64_t Size, LowLevelType DestinationType);
-    [[nodiscard]] Expected<Register>
-    findValueFromExtension(MachineInstr &Instruction,
-                           std::uint64_t StartBit, std::uint64_t Size,
-                           LowLevelType DestinationType);
-    [[nodiscard]] Expected<Register>
-    findValueFromTrunc(MachineInstr &Instruction, std::uint64_t StartBit,
-                       std::uint64_t Size, LowLevelType DestinationType);
+    findValueFromBuildVector(GBuildVector &Instruction, std::uint64_t StartBit, std::uint64_t Size);
+    [[nodiscard]] Expected<Register> findValueFromInsert(MachineInstr &Instruction,
+                                                         std::uint64_t StartBit, std::uint64_t Size,
+                                                         LowLevelType DestinationType);
+    [[nodiscard]] Expected<Register> findValueFromExtension(MachineInstr &Instruction,
+                                                            std::uint64_t StartBit,
+                                                            std::uint64_t Size,
+                                                            LowLevelType DestinationType);
+    [[nodiscard]] Expected<Register> findValueFromTrunc(MachineInstr &Instruction,
+                                                        std::uint64_t StartBit, std::uint64_t Size,
+                                                        LowLevelType DestinationType);
 
     LegalizationArtifactCombiner &Combiner;
     Register CurrentBest;
     std::unordered_set<Register> Visited;
   };
 
+  [[nodiscard]] Expected<bool> tryCombineAnyExt(MachineInstr &Instruction,
+                                                std::vector<MachineInstr *> &DeadInstructions,
+                                                std::vector<Register> &UpdatedDefs,
+                                                GISelObserverWrapper &Observer);
+  [[nodiscard]] Expected<bool> tryCombineZExt(MachineInstr &Instruction,
+                                              std::vector<MachineInstr *> &DeadInstructions,
+                                              std::vector<Register> &UpdatedDefs,
+                                              GISelObserverWrapper &Observer);
+  [[nodiscard]] Expected<bool> tryCombineSExt(MachineInstr &Instruction,
+                                              std::vector<MachineInstr *> &DeadInstructions,
+                                              std::vector<Register> &UpdatedDefs,
+                                              GISelObserverWrapper &Observer);
+  [[nodiscard]] Expected<bool> tryCombineTrunc(MachineInstr &Instruction,
+                                               std::vector<MachineInstr *> &DeadInstructions,
+                                               std::vector<Register> &UpdatedDefs,
+                                               GISelObserverWrapper &Observer);
   [[nodiscard]] Expected<bool>
-  tryCombineAnyExt(MachineInstr &Instruction,
-                   std::vector<MachineInstr *> &DeadInstructions,
-                   std::vector<Register> &UpdatedDefs,
-                   GISelObserverWrapper &Observer);
-  [[nodiscard]] Expected<bool>
-  tryCombineZExt(MachineInstr &Instruction,
-                 std::vector<MachineInstr *> &DeadInstructions,
-                 std::vector<Register> &UpdatedDefs,
-                 GISelObserverWrapper &Observer);
-  [[nodiscard]] Expected<bool>
-  tryCombineSExt(MachineInstr &Instruction,
-                 std::vector<MachineInstr *> &DeadInstructions,
-                 std::vector<Register> &UpdatedDefs,
-                 GISelObserverWrapper &Observer);
-  [[nodiscard]] Expected<bool>
-  tryCombineTrunc(MachineInstr &Instruction,
-                  std::vector<MachineInstr *> &DeadInstructions,
-                  std::vector<Register> &UpdatedDefs,
-                  GISelObserverWrapper &Observer);
-  [[nodiscard]] Expected<bool>
-  tryCombineUnmergeValues(MachineInstr &Instruction,
-                          std::vector<MachineInstr *> &DeadInstructions,
-                          std::vector<Register> &UpdatedDefs,
-                          GISelObserverWrapper &Observer);
-  [[nodiscard]] Expected<bool>
-  tryCombineExtract(MachineInstr &Instruction,
-                    std::vector<MachineInstr *> &DeadInstructions,
-                    std::vector<Register> &UpdatedDefs);
-  [[nodiscard]] Expected<bool>
-  tryCombineMergeLike(MachineInstr &Instruction,
-                      std::vector<MachineInstr *> &DeadInstructions,
-                      std::vector<Register> &UpdatedDefs,
-                      GISelObserverWrapper &Observer);
-  [[nodiscard]] Expected<bool> tryFoldImplicitDef(
-      MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions,
-      std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer);
+  tryCombineUnmergeValues(MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions,
+                          std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer);
+  [[nodiscard]] Expected<bool> tryCombineExtract(MachineInstr &Instruction,
+                                                 std::vector<MachineInstr *> &DeadInstructions,
+                                                 std::vector<Register> &UpdatedDefs);
+  [[nodiscard]] Expected<bool> tryCombineMergeLike(MachineInstr &Instruction,
+                                                   std::vector<MachineInstr *> &DeadInstructions,
+                                                   std::vector<Register> &UpdatedDefs,
+                                                   GISelObserverWrapper &Observer);
+  [[nodiscard]] Expected<bool> tryFoldImplicitDef(MachineInstr &Instruction,
+                                                  std::vector<MachineInstr *> &DeadInstructions,
+                                                  std::vector<Register> &UpdatedDefs,
+                                                  GISelObserverWrapper &Observer);
 
   [[nodiscard]] Expected<MachineInstr *> buildUnary(GenericOpcode InstructionOpcode,
-                                                    Register Destination,
-                                                    Register Source);
-  [[nodiscard]] Expected<MachineInstr *>
-  buildMergeLike(Register Destination, const std::vector<Register> &Sources);
+                                                    Register Destination, Register Source);
+  [[nodiscard]] Expected<MachineInstr *> buildMergeLike(Register Destination,
+                                                        const std::vector<Register> &Sources);
   [[nodiscard]] Expected<void> buildConstant(Register Destination, APInt Value);
   [[nodiscard]] Expected<Register> buildConstant(LowLevelType Type, APInt Value);
   [[nodiscard]] Expected<bool> isConstantUnsupported(LowLevelType Type) const;
-  [[nodiscard]] static std::optional<std::int64_t>
-  immediateOperand(const MachineInstr &Instruction, std::size_t Index);
-  [[nodiscard]] static std::size_t getDefIndex(const MachineInstr &Instruction,
-                                               Register SearchDef);
+  [[nodiscard]] static std::optional<std::int64_t> immediateOperand(const MachineInstr &Instruction,
+                                                                    std::size_t Index);
+  [[nodiscard]] static std::size_t getDefIndex(const MachineInstr &Instruction, Register SearchDef);
   [[nodiscard]] Expected<std::pair<MachineInstr *, Register>>
   definitionIgnoringCopies(Register Reg) const;
-  [[nodiscard]] Expected<std::vector<Register>>
-  buildOrFindUnmerge(LowLevelType DestinationType, Register Source);
-  [[nodiscard]] Expected<LowLevelType> divideType(LowLevelType Type,
-                                                  std::size_t Parts) const;
-  [[nodiscard]] Expected<bool>
-  tryFoldUnmergeCast(MachineInstr &Instruction, MachineInstr &Cast,
-                     std::vector<MachineInstr *> &DeadInstructions,
-                     std::vector<Register> &UpdatedDefs);
+  [[nodiscard]] Expected<std::vector<Register>> buildOrFindUnmerge(LowLevelType DestinationType,
+                                                                   Register Source);
+  [[nodiscard]] Expected<LowLevelType> divideType(LowLevelType Type, std::size_t Parts) const;
+  [[nodiscard]] Expected<bool> tryFoldUnmergeCast(MachineInstr &Instruction, MachineInstr &Cast,
+                                                  std::vector<MachineInstr *> &DeadInstructions,
+                                                  std::vector<Register> &UpdatedDefs);
   [[nodiscard]] static bool canFoldMergeOpcode(Opcode MergeOpcode,
                                                std::optional<Opcode> ConvertOpcode,
                                                LowLevelType OperandType,
                                                LowLevelType DestinationType);
 
-  [[nodiscard]] Expected<void>
-  replaceRegOrBuildCopy(Register Destination, Register Source,
-                        std::vector<Register> &UpdatedDefs,
-                        GISelChangeObserver &Observer) {
+  [[nodiscard]] Expected<void> replaceRegOrBuildCopy(Register Destination, Register Source,
+                                                     std::vector<Register> &UpdatedDefs,
+                                                     GISelChangeObserver &Observer) {
     auto DestinationType = MRI.getType(Destination);
     if (!DestinationType)
       return std::unexpected(DestinationType.error());
@@ -288,8 +281,7 @@ private:
 
   [[nodiscard]] Register lookThroughCopyInstrs(Register Reg) const {
     while (MachineInstr *Definition = MRI.getVRegDef(Reg)) {
-      if (Definition->opcode() != opcode(GenericOpcode::COPY) ||
-          Definition->operandCount() < 2)
+      if (Definition->opcode() != opcode(GenericOpcode::COPY) || Definition->operandCount() < 2)
         break;
       const auto Source = Definition->operandAt(1)->registerValue();
       if (!Source || !Source->isVirtual())
@@ -299,8 +291,8 @@ private:
     return Reg;
   }
 
-  [[nodiscard]] static std::optional<Register>
-  registerOperand(const MachineInstr &Instruction, std::size_t Index) {
+  [[nodiscard]] static std::optional<Register> registerOperand(const MachineInstr &Instruction,
+                                                               std::size_t Index) {
     const MachineOperand *Operand = Instruction.operandAt(Index);
     return Operand == nullptr ? std::nullopt : Operand->registerValue();
   }
@@ -311,8 +303,7 @@ private:
   }
 
   void markDefDead(MachineInstr &Instruction, MachineInstr &Definition,
-                   std::vector<MachineInstr *> &DeadInstructions,
-                   std::size_t DefIndex = 0) {
+                   std::vector<MachineInstr *> &DeadInstructions, std::size_t DefIndex = 0) {
     MachineInstr *Previous = &Instruction;
     while (Previous != &Definition) {
       const auto Source = artifactSourceRegister(*Previous);
@@ -347,15 +338,13 @@ private:
   }
 
   void markInstAndDefDead(MachineInstr &Instruction, MachineInstr &Definition,
-                          std::vector<MachineInstr *> &DeadInstructions,
-                          std::size_t DefIndex = 0) {
+                          std::vector<MachineInstr *> &DeadInstructions, std::size_t DefIndex = 0) {
     DeadInstructions.push_back(&Instruction);
     markDefDead(Instruction, Definition, DeadInstructions, DefIndex);
   }
 
-  [[nodiscard]] Expected<void>
-  deleteMarkedDeadInsts(std::vector<MachineInstr *> &DeadInstructions,
-                        GISelObserverWrapper &) {
+  [[nodiscard]] Expected<void> deleteMarkedDeadInsts(std::vector<MachineInstr *> &DeadInstructions,
+                                                     GISelObserverWrapper &) {
     for (MachineInstr *Dead : DeadInstructions) {
       if (Dead == nullptr || Dead->parent() == nullptr)
         continue;
@@ -395,12 +384,10 @@ private:
   [[nodiscard]] Expected<bool> isInstLegal(LegalizationQuery Query) const {
     return LI.isLegal(Query);
   }
-
 };
 
 inline Expected<MachineInstr *>
-LegalizationArtifactCombiner::buildUnary(GenericOpcode InstructionOpcode,
-                                         Register Destination,
+LegalizationArtifactCombiner::buildUnary(GenericOpcode InstructionOpcode, Register Destination,
                                          Register Source) {
   auto Pending = Builder.buildInstr(opcode(InstructionOpcode));
   if (!Pending)
@@ -412,8 +399,9 @@ LegalizationArtifactCombiner::buildUnary(GenericOpcode InstructionOpcode,
   return Pending->build();
 }
 
-inline Expected<MachineInstr *> LegalizationArtifactCombiner::buildMergeLike(
-    Register Destination, const std::vector<Register> &Sources) {
+inline Expected<MachineInstr *>
+LegalizationArtifactCombiner::buildMergeLike(Register Destination,
+                                             const std::vector<Register> &Sources) {
   if (Sources.empty())
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "merge-like instruction requires source registers");
@@ -426,8 +414,8 @@ inline Expected<MachineInstr *> LegalizationArtifactCombiner::buildMergeLike(
 
   GenericOpcode InstructionOpcode = GenericOpcode::G_MERGE_VALUES;
   if (DestinationType->isVector())
-    InstructionOpcode = SourceType->isVector() ? GenericOpcode::G_CONCAT_VECTORS
-                                               : GenericOpcode::G_BUILD_VECTOR;
+    InstructionOpcode =
+        SourceType->isVector() ? GenericOpcode::G_CONCAT_VECTORS : GenericOpcode::G_BUILD_VECTOR;
   auto Pending = Builder.buildInstr(opcode(InstructionOpcode));
   if (!Pending)
     return std::unexpected(Pending.error());
@@ -440,16 +428,16 @@ inline Expected<MachineInstr *> LegalizationArtifactCombiner::buildMergeLike(
   return Pending->build();
 }
 
-inline Expected<void>
-LegalizationArtifactCombiner::buildConstant(Register Destination, APInt Value) {
+inline Expected<void> LegalizationArtifactCombiner::buildConstant(Register Destination,
+                                                                  APInt Value) {
   auto Built = Builder.buildConstant(Destination, std::move(Value));
   if (!Built)
     return std::unexpected(Built.error());
   return {};
 }
 
-inline Expected<Register>
-LegalizationArtifactCombiner::buildConstant(LowLevelType Type, APInt Value) {
+inline Expected<Register> LegalizationArtifactCombiner::buildConstant(LowLevelType Type,
+                                                                      APInt Value) {
   auto Destination = MRI.createVirtualRegister(Type);
   if (!Destination)
     return std::unexpected(Destination.error());
@@ -459,25 +447,22 @@ LegalizationArtifactCombiner::buildConstant(LowLevelType Type, APInt Value) {
   return *Destination;
 }
 
-inline Expected<bool>
-LegalizationArtifactCombiner::isConstantUnsupported(LowLevelType Type) const {
+inline Expected<bool> LegalizationArtifactCombiner::isConstantUnsupported(LowLevelType Type) const {
   if (!Type.isVector())
-    return isInstUnsupported(
-        LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {Type}));
+    return isInstUnsupported(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {Type}));
   const auto ElementType = Type.scalarElementType();
   if (!ElementType)
     return true;
-  auto ConstantUnsupported = isInstUnsupported(
-      LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*ElementType}));
+  auto ConstantUnsupported =
+      isInstUnsupported(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*ElementType}));
   if (!ConstantUnsupported || *ConstantUnsupported)
     return ConstantUnsupported;
-  return isInstUnsupported(LegalizationQuery(
-      opcode(GenericOpcode::G_BUILD_VECTOR), {Type, *ElementType}));
+  return isInstUnsupported(
+      LegalizationQuery(opcode(GenericOpcode::G_BUILD_VECTOR), {Type, *ElementType}));
 }
 
 inline std::optional<std::int64_t>
-LegalizationArtifactCombiner::immediateOperand(const MachineInstr &Instruction,
-                                               std::size_t Index) {
+LegalizationArtifactCombiner::immediateOperand(const MachineInstr &Instruction, std::size_t Index) {
   const MachineOperand *Operand = Instruction.operandAt(Index);
   if (Operand == nullptr)
     return std::nullopt;
@@ -486,9 +471,8 @@ LegalizationArtifactCombiner::immediateOperand(const MachineInstr &Instruction,
   return std::nullopt;
 }
 
-inline std::size_t
-LegalizationArtifactCombiner::getDefIndex(const MachineInstr &Instruction,
-                                          Register SearchDef) {
+inline std::size_t LegalizationArtifactCombiner::getDefIndex(const MachineInstr &Instruction,
+                                                             Register SearchDef) {
   std::size_t Index = 0;
   for (const MachineOperand &Operand : Instruction.operands()) {
     if (!Operand.isDef())
@@ -517,9 +501,8 @@ LegalizationArtifactCombiner::definitionIgnoringCopies(Register Reg) const {
   return std::pair<MachineInstr *, Register>{nullptr, Reg};
 }
 
-inline Expected<LowLevelType>
-LegalizationArtifactCombiner::divideType(LowLevelType Type,
-                                         std::size_t Parts) const {
+inline Expected<LowLevelType> LegalizationArtifactCombiner::divideType(LowLevelType Type,
+                                                                       std::size_t Parts) const {
   if (Parts == 0 || Type.minimumBitWidth() % Parts != 0)
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "LowLevelType cannot be divided into equal parts");
@@ -530,20 +513,16 @@ LegalizationArtifactCombiner::divideType(LowLevelType Type,
                           "vector element count cannot be divided into equal parts");
   const auto ElementType = Type.scalarElementType();
   if (!ElementType)
-    return makeUnexpected(ErrorCode::InvalidArgument,
-                          "vector has no scalar element type");
-  const std::uint32_t Elements =
-      Type.minimumElementCount() / static_cast<std::uint32_t>(Parts);
+    return makeUnexpected(ErrorCode::InvalidArgument, "vector has no scalar element type");
+  const std::uint32_t Elements = Type.minimumElementCount() / static_cast<std::uint32_t>(Parts);
   if (Elements == 1)
     return *ElementType;
-  return Type.isScalableVector()
-             ? LowLevelType::makeScalableVector(Elements, *ElementType)
-             : LowLevelType::makeFixedVector(Elements, *ElementType);
+  return Type.isScalableVector() ? LowLevelType::makeScalableVector(Elements, *ElementType)
+                                 : LowLevelType::makeFixedVector(Elements, *ElementType);
 }
 
 inline Expected<std::vector<Register>>
-LegalizationArtifactCombiner::buildOrFindUnmerge(LowLevelType DestinationType,
-                                                 Register Source) {
+LegalizationArtifactCombiner::buildOrFindUnmerge(LowLevelType DestinationType, Register Source) {
   auto SourceType = MRI.getType(Source);
   if (!SourceType)
     return std::unexpected(SourceType.error());
@@ -551,8 +530,8 @@ LegalizationArtifactCombiner::buildOrFindUnmerge(LowLevelType DestinationType,
       SourceType->minimumBitWidth() % DestinationType.minimumBitWidth() != 0)
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "unmerge destination does not tile the source type");
-  const std::size_t Count = static_cast<std::size_t>(
-      SourceType->minimumBitWidth() / DestinationType.minimumBitWidth());
+  const std::size_t Count =
+      static_cast<std::size_t>(SourceType->minimumBitWidth() / DestinationType.minimumBitWidth());
 
   for (MachineOperand &Use : MRI.useOperands(Source)) {
     MachineInstr *Candidate = Use.parent();
@@ -592,17 +571,17 @@ LegalizationArtifactCombiner::buildOrFindUnmerge(LowLevelType DestinationType,
   return Destinations;
 }
 
-inline bool LegalizationArtifactCombiner::canFoldMergeOpcode(
-    Opcode MergeOpcode, std::optional<Opcode> ConvertOpcode,
-    LowLevelType OperandType, LowLevelType DestinationType) {
+inline bool LegalizationArtifactCombiner::canFoldMergeOpcode(Opcode MergeOpcode,
+                                                             std::optional<Opcode> ConvertOpcode,
+                                                             LowLevelType OperandType,
+                                                             LowLevelType DestinationType) {
   const auto Generic = static_cast<GenericOpcode>(MergeOpcode.value());
-  if (Generic == GenericOpcode::G_BUILD_VECTOR ||
-      Generic == GenericOpcode::G_MERGE_VALUES) {
+  if (Generic == GenericOpcode::G_BUILD_VECTOR || Generic == GenericOpcode::G_MERGE_VALUES) {
     if (!ConvertOpcode)
       return true;
     const auto ElementType = OperandType.scalarElementType();
-    return !DestinationType.isVector() && OperandType.isVector() &&
-           ElementType && DestinationType == *ElementType;
+    return !DestinationType.isVector() && OperandType.isVector() && ElementType &&
+           DestinationType == *ElementType;
   }
   if (Generic != GenericOpcode::G_CONCAT_VECTORS)
     return false;
@@ -619,14 +598,12 @@ inline bool LegalizationArtifactCombiner::canFoldMergeOpcode(
 }
 
 inline Expected<bool> LegalizationArtifactCombiner::tryCombineAnyExt(
-    MachineInstr &Instruction,
-    std::vector<MachineInstr *> &DeadInstructions,
+    MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions,
     std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) {
   const auto Destination = registerOperand(Instruction, 0);
   const auto OriginalSource = registerOperand(Instruction, 1);
   if (!Destination || !OriginalSource)
-    return makeUnexpected(ErrorCode::VerificationError,
-                          "G_ANYEXT has invalid register operands");
+    return makeUnexpected(ErrorCode::VerificationError, "G_ANYEXT has invalid register operands");
   const Register Source = lookThroughCopyInstrs(*OriginalSource);
   MachineInstr *SourceDefinition = MRI.getVRegDef(Source);
   if (SourceDefinition == nullptr)
@@ -645,8 +622,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineAnyExt(
     if (!TruncSourceType)
       return std::unexpected(TruncSourceType.error());
     if (*DestinationType == *TruncSourceType) {
-      auto Replaced = replaceRegOrBuildCopy(*Destination, *TruncSource,
-                                            UpdatedDefs, Observer);
+      auto Replaced = replaceRegOrBuildCopy(*Destination, *TruncSource, UpdatedDefs, Observer);
       if (!Replaced)
         return std::unexpected(Replaced.error());
     } else {
@@ -665,9 +641,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineAnyExt(
     const auto ExtensionSource = registerOperand(*SourceDefinition, 1);
     if (!ExtensionSource)
       return false;
-    auto Built = buildUnary(
-        static_cast<GenericOpcode>(SourceDefinition->opcode().value()),
-        *Destination, *ExtensionSource);
+    auto Built = buildUnary(static_cast<GenericOpcode>(SourceDefinition->opcode().value()),
+                            *Destination, *ExtensionSource);
     if (!Built)
       return std::unexpected(Built.error());
     UpdatedDefs.push_back(*Destination);
@@ -679,12 +654,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineAnyExt(
     auto DestinationType = MRI.getType(*Destination);
     if (!DestinationType)
       return std::unexpected(DestinationType.error());
-    auto Legal = isInstLegal(LegalizationQuery(
-        opcode(GenericOpcode::G_CONSTANT), {*DestinationType}));
+    auto Legal =
+        isInstLegal(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*DestinationType}));
     if (!Legal)
       return std::unexpected(Legal.error());
-    const auto *Immediate =
-        SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>();
+    const auto *Immediate = SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>();
     if (*Legal && Immediate != nullptr) {
       auto Extended = Immediate->Value.sext(DestinationType->scalarBitWidth());
       if (!Extended)
@@ -697,19 +671,16 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineAnyExt(
       return true;
     }
   }
-  return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs,
-                            Observer);
+  return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, Observer);
 }
 
 inline Expected<bool> LegalizationArtifactCombiner::tryCombineZExt(
-    MachineInstr &Instruction,
-    std::vector<MachineInstr *> &DeadInstructions,
+    MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions,
     std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) {
   const auto Destination = registerOperand(Instruction, 0);
   const auto OriginalSource = registerOperand(Instruction, 1);
   if (!Destination || !OriginalSource)
-    return makeUnexpected(ErrorCode::VerificationError,
-                          "G_ZEXT has invalid register operands");
+    return makeUnexpected(ErrorCode::VerificationError, "G_ZEXT has invalid register operands");
   const Register Source = lookThroughCopyInstrs(*OriginalSource);
   MachineInstr *SourceDefinition = MRI.getVRegDef(Source);
   if (SourceDefinition == nullptr)
@@ -728,8 +699,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineZExt(
     auto SourceType = MRI.getType(Source);
     if (!SourceType)
       return std::unexpected(SourceType.error());
-    auto AndUnsupported = isInstUnsupported(
-        LegalizationQuery(opcode(GenericOpcode::G_AND), {*DestinationType}));
+    auto AndUnsupported =
+        isInstUnsupported(LegalizationQuery(opcode(GenericOpcode::G_AND), {*DestinationType}));
     if (!AndUnsupported)
       return std::unexpected(AndUnsupported.error());
     auto ConstantUnsupported = isConstantUnsupported(*DestinationType);
@@ -753,16 +724,32 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineZExt(
         return std::unexpected(Built.error());
       WideSource = *Wide;
     }
-    auto Mask = APInt::getLowBitsSet(DestinationType->scalarBitWidth(),
-                                     SourceType->scalarBitWidth());
+    auto Mask =
+        APInt::getLowBitsSet(DestinationType->scalarBitWidth(), SourceType->scalarBitWidth());
     if (!Mask)
       return std::unexpected(Mask.error());
-    auto MaskRegister = buildConstant(*DestinationType, std::move(*Mask));
-    if (!MaskRegister)
-      return std::unexpected(MaskRegister.error());
-    auto Built = Builder.buildAnd(*Destination, WideSource, *MaskRegister);
-    if (!Built)
-      return std::unexpected(Built.error());
+    bool ElideAnd = false;
+    if (VT != nullptr) {
+      auto KnownZeroes = VT->getKnownZeroes(WideSource);
+      if (!KnownZeroes)
+        return std::unexpected(KnownZeroes.error());
+      auto CoveredBits = KnownZeroes->bitwiseOr(*Mask);
+      if (!CoveredBits)
+        return std::unexpected(CoveredBits.error());
+      ElideAnd = CoveredBits->isAllOnes();
+    }
+    if (ElideAnd) {
+      auto Replaced = replaceRegOrBuildCopy(*Destination, WideSource, UpdatedDefs, Observer);
+      if (!Replaced)
+        return std::unexpected(Replaced.error());
+    } else {
+      auto MaskRegister = buildConstant(*DestinationType, std::move(*Mask));
+      if (!MaskRegister)
+        return std::unexpected(MaskRegister.error());
+      auto Built = Builder.buildAnd(*Destination, WideSource, *MaskRegister);
+      if (!Built)
+        return std::unexpected(Built.error());
+    }
     UpdatedDefs.push_back(*Destination);
     markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions);
     return true;
@@ -786,12 +773,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineZExt(
     auto DestinationType = MRI.getType(*Destination);
     if (!DestinationType)
       return std::unexpected(DestinationType.error());
-    auto Legal = isInstLegal(LegalizationQuery(
-        opcode(GenericOpcode::G_CONSTANT), {*DestinationType}));
+    auto Legal =
+        isInstLegal(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*DestinationType}));
     if (!Legal)
       return std::unexpected(Legal.error());
-    const auto *Immediate =
-        SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>();
+    const auto *Immediate = SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>();
     if (*Legal && Immediate != nullptr) {
       auto Extended = Immediate->Value.zext(DestinationType->scalarBitWidth());
       if (!Extended)
@@ -804,19 +790,16 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineZExt(
       return true;
     }
   }
-  return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs,
-                            Observer);
+  return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, Observer);
 }
 
 inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt(
-    MachineInstr &Instruction,
-    std::vector<MachineInstr *> &DeadInstructions,
+    MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions,
     std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) {
   const auto Destination = registerOperand(Instruction, 0);
   const auto OriginalSource = registerOperand(Instruction, 1);
   if (!Destination || !OriginalSource)
-    return makeUnexpected(ErrorCode::VerificationError,
-                          "G_SEXT has invalid register operands");
+    return makeUnexpected(ErrorCode::VerificationError, "G_SEXT has invalid register operands");
   const Register Source = lookThroughCopyInstrs(*OriginalSource);
   MachineInstr *SourceDefinition = MRI.getVRegDef(Source);
   if (SourceDefinition == nullptr)
@@ -834,8 +817,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt(
     auto SourceType = MRI.getType(Source);
     if (!SourceType)
       return std::unexpected(SourceType.error());
-    auto Unsupported = isInstUnsupported(LegalizationQuery(
-        opcode(GenericOpcode::G_SEXT_INREG), {*DestinationType}));
+    auto Unsupported = isInstUnsupported(
+        LegalizationQuery(opcode(GenericOpcode::G_SEXT_INREG), {*DestinationType}));
     if (!Unsupported)
       return std::unexpected(Unsupported.error());
     if (*Unsupported)
@@ -853,10 +836,22 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt(
         return std::unexpected(Built.error());
       WideSource = *Wide;
     }
-    auto Built = Builder.buildSExtInReg(*Destination, WideSource,
-                                        SourceType->scalarBitWidth());
-    if (!Built)
-      return std::unexpected(Built.error());
+    bool ElideSExtInReg = false;
+    if (VT != nullptr) {
+      auto SignBits = VT->computeNumSignBits(WideSource);
+      if (!SignBits)
+        return std::unexpected(SignBits.error());
+      ElideSExtInReg = *SignBits > DestinationType->scalarBitWidth() - SourceType->scalarBitWidth();
+    }
+    if (ElideSExtInReg) {
+      auto Replaced = replaceRegOrBuildCopy(*Destination, WideSource, UpdatedDefs, Observer);
+      if (!Replaced)
+        return std::unexpected(Replaced.error());
+    } else {
+      auto Built = Builder.buildSExtInReg(*Destination, WideSource, SourceType->scalarBitWidth());
+      if (!Built)
+        return std::unexpected(Built.error());
+    }
     UpdatedDefs.push_back(*Destination);
     markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions);
     return true;
@@ -867,9 +862,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt(
     const auto ExtensionSource = registerOperand(*SourceDefinition, 1);
     if (!ExtensionSource)
       return false;
-    auto Built = buildUnary(
-        static_cast<GenericOpcode>(SourceDefinition->opcode().value()),
-        *Destination, *ExtensionSource);
+    auto Built = buildUnary(static_cast<GenericOpcode>(SourceDefinition->opcode().value()),
+                            *Destination, *ExtensionSource);
     if (!Built)
       return std::unexpected(Built.error());
     UpdatedDefs.push_back(*Destination);
@@ -881,12 +875,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt(
     auto DestinationType = MRI.getType(*Destination);
     if (!DestinationType)
       return std::unexpected(DestinationType.error());
-    auto Legal = isInstLegal(LegalizationQuery(
-        opcode(GenericOpcode::G_CONSTANT), {*DestinationType}));
+    auto Legal =
+        isInstLegal(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*DestinationType}));
     if (!Legal)
       return std::unexpected(Legal.error());
-    const auto *Immediate =
-        SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>();
+    const auto *Immediate = SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>();
     if (*Legal && Immediate != nullptr) {
       auto Extended = Immediate->Value.sext(DestinationType->scalarBitWidth());
       if (!Extended)
@@ -899,13 +892,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt(
       return true;
     }
   }
-  return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs,
-                            Observer);
+  return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, Observer);
 }
 
 inline Expected<bool> LegalizationArtifactCombiner::tryFoldImplicitDef(
-    MachineInstr &Instruction,
-    std::vector<MachineInstr *> &DeadInstructions,
+    MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions,
     std::vector<Register> &UpdatedDefs, GISelObserverWrapper &) {
   const auto Destination = registerOperand(Instruction, 0);
   const auto Source = registerOperand(Instruction, 1);
@@ -920,8 +911,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryFoldImplicitDef(
   if (auto Point = Builder.setInsertPointBefore(Instruction); !Point)
     return std::unexpected(Point.error());
   if (Instruction.opcode() == opcode(GenericOpcode::G_ANYEXT)) {
-    auto Legal = isInstLegal(LegalizationQuery(
-        opcode(GenericOpcode::G_IMPLICIT_DEF), {*DestinationType}));
+    auto Legal =
+        isInstLegal(LegalizationQuery(opcode(GenericOpcode::G_IMPLICIT_DEF), {*DestinationType}));
     if (!Legal)
       return std::unexpected(Legal.error());
     if (!*Legal)
@@ -945,14 +936,12 @@ inline Expected<bool> LegalizationArtifactCombiner::tryFoldImplicitDef(
 }
 
 inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc(
-    MachineInstr &Instruction,
-    std::vector<MachineInstr *> &DeadInstructions,
+    MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions,
     std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) {
   const auto Destination = registerOperand(Instruction, 0);
   const auto OriginalSource = registerOperand(Instruction, 1);
   if (!Destination || !OriginalSource)
-    return makeUnexpected(ErrorCode::VerificationError,
-                          "G_TRUNC has invalid register operands");
+    return makeUnexpected(ErrorCode::VerificationError, "G_TRUNC has invalid register operands");
   const Register Source = lookThroughCopyInstrs(*OriginalSource);
   MachineInstr *SourceDefinition = MRI.getVRegDef(Source);
   if (SourceDefinition == nullptr)
@@ -964,12 +953,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc(
     return std::unexpected(Point.error());
 
   if (hasOpcode(SourceDefinition, GenericOpcode::G_CONSTANT)) {
-    auto Legal = isInstLegal(LegalizationQuery(
-        opcode(GenericOpcode::G_CONSTANT), {*DestinationType}));
+    auto Legal =
+        isInstLegal(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*DestinationType}));
     if (!Legal)
       return std::unexpected(Legal.error());
-    const auto *Immediate =
-        SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>();
+    const auto *Immediate = SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>();
     if (*Legal && Immediate != nullptr) {
       auto Truncated = Immediate->Value.trunc(DestinationType->scalarBitWidth());
       if (!Truncated)
@@ -991,15 +979,13 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc(
     auto FirstSourceType = MRI.getType(FirstSource);
     if (!FirstSourceType)
       return std::unexpected(FirstSourceType.error());
-    if (!DestinationType->isCategoryNeutralScalar() ||
-        !FirstSourceType->isCategoryNeutralScalar())
+    if (!DestinationType->isCategoryNeutralScalar() || !FirstSourceType->isCategoryNeutralScalar())
       return false;
     const std::uint64_t DestinationSize = DestinationType->minimumBitWidth();
     const std::uint64_t SourceSize = FirstSourceType->minimumBitWidth();
     if (DestinationSize < SourceSize) {
-      auto Unsupported = isInstUnsupported(LegalizationQuery(
-          opcode(GenericOpcode::G_TRUNC),
-          {*DestinationType, *FirstSourceType}));
+      auto Unsupported = isInstUnsupported(
+          LegalizationQuery(opcode(GenericOpcode::G_TRUNC), {*DestinationType, *FirstSourceType}));
       if (!Unsupported)
         return std::unexpected(Unsupported.error());
       if (*Unsupported)
@@ -1009,18 +995,15 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc(
         return std::unexpected(Built.error());
       UpdatedDefs.push_back(*Destination);
     } else if (DestinationSize == SourceSize) {
-      auto Replaced = replaceRegOrBuildCopy(*Destination, FirstSource,
-                                            UpdatedDefs, Observer);
+      auto Replaced = replaceRegOrBuildCopy(*Destination, FirstSource, UpdatedDefs, Observer);
       if (!Replaced)
         return std::unexpected(Replaced.error());
     } else if (DestinationSize % SourceSize == 0) {
-      const std::size_t SourceCount =
-          static_cast<std::size_t>(DestinationSize / SourceSize);
+      const std::size_t SourceCount = static_cast<std::size_t>(DestinationSize / SourceSize);
       if (SourceCount >= Merge.getNumSources())
         return false;
-      auto Unsupported = isInstUnsupported(LegalizationQuery(
-          opcode(GenericOpcode::G_MERGE_VALUES),
-          {*DestinationType, *FirstSourceType}));
+      auto Unsupported = isInstUnsupported(LegalizationQuery(opcode(GenericOpcode::G_MERGE_VALUES),
+                                                             {*DestinationType, *FirstSourceType}));
       if (!Unsupported)
         return std::unexpected(Unsupported.error());
       if (*Unsupported)
@@ -1053,8 +1036,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc(
   }
 
   ArtifactValueFinder Finder(*this);
-  auto Found = Finder.findValueFromDef(*Destination, 0,
-                                       DestinationType->minimumBitWidth(),
+  auto Found = Finder.findValueFromDef(*Destination, 0, DestinationType->minimumBitWidth(),
                                        *DestinationType);
   if (!Found)
     return std::unexpected(Found.error());
@@ -1063,8 +1045,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc(
     if (!FoundType)
       return std::unexpected(FoundType.error());
     if (*FoundType == *DestinationType) {
-      auto Replaced = replaceRegOrBuildCopy(*Destination, *Found, UpdatedDefs,
-                                            Observer);
+      auto Replaced = replaceRegOrBuildCopy(*Destination, *Found, UpdatedDefs, Observer);
       if (!Replaced)
         return std::unexpected(Replaced.error());
       markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions);
@@ -1074,10 +1055,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc(
   return false;
 }
 
-inline Expected<bool>
-LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike(
-    GMergeLikeInstr &Instruction,
-    std::vector<MachineInstr *> &DeadInstructions,
+inline Expected<bool> LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike(
+    GMergeLikeInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions,
     std::vector<Register> &UpdatedDefs, GISelChangeObserver &Observer) {
   if (Instruction.getNumSources() == 0)
     return false;
@@ -1087,8 +1066,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike(
     return std::unexpected(ElementType.error());
   const std::uint64_t ElementSize = ElementType->minimumBitWidth();
   std::size_t FirstUnmergeIndex = 0;
-  auto UnmergeResult =
-      findUnmergeThatDefinesReg(FirstElement, ElementSize, FirstUnmergeIndex);
+  auto UnmergeResult = findUnmergeThatDefinesReg(FirstElement, ElementSize, FirstUnmergeIndex);
   if (!UnmergeResult)
     return std::unexpected(UnmergeResult.error());
   GUnmerge *Unmerge = *UnmergeResult;
@@ -1106,15 +1084,14 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike(
   const std::size_t SourceCount = Instruction.getNumSources();
 
   if (*DestinationType == *UnmergeSourceType && FirstUnmergeIndex == 0) {
-    auto Sequence = isSequenceFromUnmerge(
-        Instruction, 0, Unmerge, 0, SourceCount, ElementSize,
-        DestinationType->isVector());
+    auto Sequence = isSequenceFromUnmerge(Instruction, 0, Unmerge, 0, SourceCount, ElementSize,
+                                          DestinationType->isVector());
     if (!Sequence)
       return std::unexpected(Sequence.error());
     if (!*Sequence)
       return false;
-    auto Replaced = Combiner.replaceRegOrBuildCopy(
-        Destination, UnmergeSource, UpdatedDefs, Observer);
+    auto Replaced =
+        Combiner.replaceRegOrBuildCopy(Destination, UnmergeSource, UpdatedDefs, Observer);
     if (!Replaced)
       return std::unexpected(Replaced.error());
     DeadInstructions.push_back(&Instruction);
@@ -1124,29 +1101,23 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike(
   const bool MatchingDomains =
       (!DestinationType->isVector() && !UnmergeSourceType->isVector()) ||
       (DestinationType->isVector() && UnmergeSourceType->isVector() &&
-       DestinationType->scalarElementType() ==
-           UnmergeSourceType->scalarElementType());
+       DestinationType->scalarElementType() == UnmergeSourceType->scalarElementType());
   if (MatchingDomains && FirstUnmergeIndex % SourceCount == 0 &&
-      UnmergeSourceType->minimumBitWidth() %
-              DestinationType->minimumBitWidth() ==
-          0) {
-    auto Sequence = isSequenceFromUnmerge(
-        Instruction, 0, Unmerge, FirstUnmergeIndex, SourceCount, ElementSize,
-        false);
+      UnmergeSourceType->minimumBitWidth() % DestinationType->minimumBitWidth() == 0) {
+    auto Sequence = isSequenceFromUnmerge(Instruction, 0, Unmerge, FirstUnmergeIndex, SourceCount,
+                                          ElementSize, false);
     if (!Sequence)
       return std::unexpected(Sequence.error());
     if (*Sequence) {
-      auto NewUnmerge = Combiner.buildOrFindUnmerge(*DestinationType,
-                                                   UnmergeSource);
+      auto NewUnmerge = Combiner.buildOrFindUnmerge(*DestinationType, UnmergeSource);
       if (!NewUnmerge)
         return std::unexpected(NewUnmerge.error());
       const std::size_t DestinationIndex = static_cast<std::size_t>(
-          (FirstUnmergeIndex * ElementSize) /
-          DestinationType->minimumBitWidth());
+          (FirstUnmergeIndex * ElementSize) / DestinationType->minimumBitWidth());
       if (DestinationIndex >= NewUnmerge->size())
         return false;
-      auto Replaced = Combiner.replaceRegOrBuildCopy(
-          Destination, (*NewUnmerge)[DestinationIndex], UpdatedDefs, Observer);
+      auto Replaced = Combiner.replaceRegOrBuildCopy(Destination, (*NewUnmerge)[DestinationIndex],
+                                                     UpdatedDefs, Observer);
       if (!Replaced)
         return std::unexpected(Replaced.error());
       DeadInstructions.push_back(&Instruction);
@@ -1155,27 +1126,22 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike(
   }
 
   if (DestinationType->isVector() == UnmergeSourceType->isVector() &&
-      DestinationType->minimumBitWidth() %
-              UnmergeSourceType->minimumBitWidth() ==
-          0) {
+      DestinationType->minimumBitWidth() % UnmergeSourceType->minimumBitWidth() == 0) {
     const std::size_t UnmergeElementCount = Unmerge->getNumDefs();
     if (UnmergeElementCount == 0 || SourceCount % UnmergeElementCount != 0)
       return false;
     std::vector<Register> MergeSources;
-    for (std::size_t Start = 0; Start < SourceCount;
-         Start += UnmergeElementCount) {
+    for (std::size_t Start = 0; Start < SourceCount; Start += UnmergeElementCount) {
       std::size_t SourceDefIndex = 0;
-      auto SourceUnmerge = findUnmergeThatDefinesReg(
-          Instruction.getSourceReg(Start), ElementSize, SourceDefIndex);
+      auto SourceUnmerge =
+          findUnmergeThatDefinesReg(Instruction.getSourceReg(Start), ElementSize, SourceDefIndex);
       if (!SourceUnmerge)
         return std::unexpected(SourceUnmerge.error());
-      if (*SourceUnmerge == nullptr ||
-          (*SourceUnmerge)->getNumDefs() != UnmergeElementCount ||
+      if (*SourceUnmerge == nullptr || (*SourceUnmerge)->getNumDefs() != UnmergeElementCount ||
           SourceDefIndex != 0)
         return false;
-      auto Sequence = isSequenceFromUnmerge(
-          Instruction, Start, *SourceUnmerge, 0, UnmergeElementCount,
-          ElementSize, false);
+      auto Sequence = isSequenceFromUnmerge(Instruction, Start, *SourceUnmerge, 0,
+                                            UnmergeElementCount, ElementSize, false);
       if (!Sequence)
         return std::unexpected(Sequence.error());
       if (!*Sequence)
@@ -1193,23 +1159,20 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike(
 }
 
 inline Expected<bool> LegalizationArtifactCombiner::tryCombineMergeLike(
-    MachineInstr &Instruction,
-    std::vector<MachineInstr *> &DeadInstructions,
+    MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions,
     std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) {
   if (!GMergeLikeInstr::classof(&Instruction))
     return false;
   ArtifactValueFinder Finder(*this);
-  return Finder.tryCombineMergeLike(
-      castGenericMachineInstr<GMergeLikeInstr>(Instruction), DeadInstructions,
-      UpdatedDefs, Observer);
+  return Finder.tryCombineMergeLike(castGenericMachineInstr<GMergeLikeInstr>(Instruction),
+                                    DeadInstructions, UpdatedDefs, Observer);
 }
 
-inline Expected<bool> LegalizationArtifactCombiner::tryFoldUnmergeCast(
-    MachineInstr &Instruction, MachineInstr &Cast,
-    std::vector<MachineInstr *> &DeadInstructions,
-    std::vector<Register> &UpdatedDefs) {
-  if (!isArtifactCast(Cast.opcode()) ||
-      Cast.opcode() != opcode(GenericOpcode::G_TRUNC))
+inline Expected<bool>
+LegalizationArtifactCombiner::tryFoldUnmergeCast(MachineInstr &Instruction, MachineInstr &Cast,
+                                                 std::vector<MachineInstr *> &DeadInstructions,
+                                                 std::vector<Register> &UpdatedDefs) {
+  if (!isArtifactCast(Cast.opcode()) || Cast.opcode() != opcode(GenericOpcode::G_TRUNC))
     return false;
   const auto CastSource = registerOperand(Cast, 1);
   if (!CastSource)
@@ -1227,20 +1190,16 @@ inline Expected<bool> LegalizationArtifactCombiner::tryFoldUnmergeCast(
   if (!DestinationType)
     return std::unexpected(DestinationType.error());
   if (DestinationType->isVector() || !CastSourceType->isCategoryNeutralScalar() ||
-      CastSourceType->minimumBitWidth() %
-              DestinationType->minimumBitWidth() !=
-          0)
+      CastSourceType->minimumBitWidth() % DestinationType->minimumBitWidth() != 0)
     return false;
-  auto Unsupported = isInstUnsupported(LegalizationQuery(
-      opcode(GenericOpcode::G_UNMERGE_VALUES),
-      {*DestinationType, *CastSourceType}));
+  auto Unsupported = isInstUnsupported(LegalizationQuery(opcode(GenericOpcode::G_UNMERGE_VALUES),
+                                                         {*DestinationType, *CastSourceType}));
   if (!Unsupported)
     return std::unexpected(Unsupported.error());
   if (*Unsupported)
     return false;
-  const std::size_t NewDefCount = static_cast<std::size_t>(
-      CastSourceType->minimumBitWidth() /
-      DestinationType->minimumBitWidth());
+  const std::size_t NewDefCount = static_cast<std::size_t>(CastSourceType->minimumBitWidth() /
+                                                           DestinationType->minimumBitWidth());
   std::vector<Register> Destinations;
   Destinations.reserve(NewDefCount);
   for (std::size_t Index = 0; Index < NewDefCount; ++Index) {
@@ -1262,15 +1221,13 @@ inline Expected<bool> LegalizationArtifactCombiner::tryFoldUnmergeCast(
   if (!Built)
     return std::unexpected(Built.error());
   UpdatedDefs.insert(UpdatedDefs.end(), Destinations.begin(),
-                     Destinations.begin() +
-                         static_cast<std::ptrdiff_t>(OriginalDefCount));
+                     Destinations.begin() + static_cast<std::ptrdiff_t>(OriginalDefCount));
   markInstAndDefDead(Instruction, Cast, DeadInstructions);
   return true;
 }
 
 inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues(
-    MachineInstr &Instruction,
-    std::vector<MachineInstr *> &DeadInstructions,
+    MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions,
     std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) {
   if (!GUnmerge::classof(&Instruction))
     return false;
@@ -1284,8 +1241,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues(
   MachineInstr *SourceDefinition = Definition->first;
   if (SourceDefinition == nullptr)
     return false;
-  const std::size_t SourceDefIndex = getDefIndex(*SourceDefinition,
-                                                Definition->second);
+  const std::size_t SourceDefIndex = getDefIndex(*SourceDefinition, Definition->second);
   auto OperandType = MRI.getType(Source);
   if (!OperandType)
     return std::unexpected(OperandType.error());
@@ -1296,13 +1252,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues(
     return std::unexpected(Point.error());
 
   ArtifactValueFinder Finder(*this);
-  auto AllCombined = Finder.tryCombineUnmergeDefs(Unmerge, Observer,
-                                                  UpdatedDefs);
+  auto AllCombined = Finder.tryCombineUnmergeDefs(Unmerge, Observer, UpdatedDefs);
   if (!AllCombined)
     return std::unexpected(AllCombined.error());
   if (*AllCombined) {
-    markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions,
-                       SourceDefIndex);
+    markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions, SourceDefIndex);
     return true;
   }
 
@@ -1319,14 +1273,12 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues(
     if (BaseIndex + Unmerge.getNumDefs() > NewUnmerge->size())
       return false;
     for (std::size_t Index = 0; Index < Unmerge.getNumDefs(); ++Index) {
-      auto Replaced = replaceRegOrBuildCopy(
-          Unmerge.getReg(Index), (*NewUnmerge)[BaseIndex + Index], UpdatedDefs,
-          Observer);
+      auto Replaced = replaceRegOrBuildCopy(Unmerge.getReg(Index), (*NewUnmerge)[BaseIndex + Index],
+                                            UpdatedDefs, Observer);
       if (!Replaced)
         return std::unexpected(Replaced.error());
     }
-    markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions,
-                       SourceDefIndex);
+    markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions, SourceDefIndex);
     return true;
   }
 
@@ -1343,10 +1295,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues(
     Merge = CastDefinition->first;
   }
   if (Merge == nullptr ||
-      !canFoldMergeOpcode(Merge->opcode(), ConvertOpcode, *OperandType,
-                          *DestinationType))
-    return tryFoldUnmergeCast(Instruction, *SourceDefinition,
-                              DeadInstructions, UpdatedDefs);
+      !canFoldMergeOpcode(Merge->opcode(), ConvertOpcode, *OperandType, *DestinationType))
+    return tryFoldUnmergeCast(Instruction, *SourceDefinition, DeadInstructions, UpdatedDefs);
 
   const std::size_t MergeSourceCount = Merge->operandCount() - 1;
   const std::size_t DefCount = Unmerge.getNumDefs();
@@ -1354,13 +1304,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues(
     if (DefCount % MergeSourceCount != 0)
       return false;
     const std::size_t NewDefCount = DefCount / MergeSourceCount;
-    for (std::size_t SourceIndex = 0; SourceIndex < MergeSourceCount;
-         ++SourceIndex) {
+    for (std::size_t SourceIndex = 0; SourceIndex < MergeSourceCount; ++SourceIndex) {
       std::vector<Register> Destinations;
       Destinations.reserve(NewDefCount);
       for (std::size_t Index = 0; Index < NewDefCount; ++Index)
-        Destinations.push_back(
-            Unmerge.getReg(SourceIndex * NewDefCount + Index));
+        Destinations.push_back(Unmerge.getReg(SourceIndex * NewDefCount + Index));
       Register SplitSource = *registerOperand(*Merge, SourceIndex + 1);
       if (ConvertOpcode) {
         auto ConvertedType = divideType(*OperandType, MergeSourceCount);
@@ -1369,9 +1317,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues(
         auto Converted = MRI.createVirtualRegister(*ConvertedType);
         if (!Converted)
           return std::unexpected(Converted.error());
-        auto Built = buildUnary(
-            static_cast<GenericOpcode>(ConvertOpcode->value()), *Converted,
-            SplitSource);
+        auto Built =
+            buildUnary(static_cast<GenericOpcode>(ConvertOpcode->value()), *Converted, SplitSource);
         if (!Built)
           return std::unexpected(Built.error());
         SplitSource = *Converted;
@@ -1379,8 +1326,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues(
       auto Built = Builder.buildUnmergeValues(Destinations, SplitSource);
       if (!Built)
         return std::unexpected(Built.error());
-      UpdatedDefs.insert(UpdatedDefs.end(), Destinations.begin(),
-                         Destinations.end());
+      UpdatedDefs.insert(UpdatedDefs.end(), Destinations.begin(), Destinations.end());
     }
   } else if (MergeSourceCount > DefCount) {
     if (ConvertOpcode || MergeSourceCount % DefCount != 0)
@@ -1390,8 +1336,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues(
       std::vector<Register> Sources;
       Sources.reserve(SourcesPerDef);
       for (std::size_t Index = 0; Index < SourcesPerDef; ++Index) {
-        const auto SourceReg = registerOperand(
-            *Merge, 1 + DefIndex * SourcesPerDef + Index);
+        const auto SourceReg = registerOperand(*Merge, 1 + DefIndex * SourcesPerDef + Index);
         if (!SourceReg)
           return false;
         Sources.push_back(*SourceReg);
@@ -1422,16 +1367,15 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues(
         return false;
       if (ConvertOpcode) {
         if (!MRI.useEmpty(Unmerge.getReg(Index))) {
-          auto Built = buildUnary(
-              static_cast<GenericOpcode>(ConvertOpcode->value()),
-              Unmerge.getReg(Index), *MergeSource);
+          auto Built = buildUnary(static_cast<GenericOpcode>(ConvertOpcode->value()),
+                                  Unmerge.getReg(Index), *MergeSource);
           if (!Built)
             return std::unexpected(Built.error());
           UpdatedDefs.push_back(Unmerge.getReg(Index));
         }
       } else {
-        auto Replaced = replaceRegOrBuildCopy(
-            Unmerge.getReg(Index), *MergeSource, UpdatedDefs, Observer);
+        auto Replaced =
+            replaceRegOrBuildCopy(Unmerge.getReg(Index), *MergeSource, UpdatedDefs, Observer);
         if (!Replaced)
           return std::unexpected(Replaced.error());
       }
@@ -1441,10 +1385,10 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues(
   return true;
 }
 
-inline Expected<bool> LegalizationArtifactCombiner::tryCombineExtract(
-    MachineInstr &Instruction,
-    std::vector<MachineInstr *> &DeadInstructions,
-    std::vector<Register> &UpdatedDefs) {
+inline Expected<bool>
+LegalizationArtifactCombiner::tryCombineExtract(MachineInstr &Instruction,
+                                                std::vector<MachineInstr *> &DeadInstructions,
+                                                std::vector<Register> &UpdatedDefs) {
   const auto Destination = registerOperand(Instruction, 0);
   const auto OriginalSource = registerOperand(Instruction, 1);
   const auto OffsetValue = immediateOperand(Instruction, 2);
@@ -1475,21 +1419,18 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineExtract(
   const std::size_t SourceCount = Merge->operandCount() - 1;
   if (SourceCount == 0)
     return false;
-  const std::uint64_t MergeSourceSize =
-      SourceType->minimumBitWidth() / SourceCount;
+  const std::uint64_t MergeSourceSize = SourceType->minimumBitWidth() / SourceCount;
   const std::uint64_t Offset = static_cast<std::uint64_t>(*OffsetValue);
-  const std::size_t FirstSource =
-      static_cast<std::size_t>(Offset / MergeSourceSize);
-  const std::size_t LastSource = static_cast<std::size_t>(
-      (Offset + DestinationType->minimumBitWidth() - 1) / MergeSourceSize);
+  const std::size_t FirstSource = static_cast<std::size_t>(Offset / MergeSourceSize);
+  const std::size_t LastSource =
+      static_cast<std::size_t>((Offset + DestinationType->minimumBitWidth() - 1) / MergeSourceSize);
   if (FirstSource != LastSource || FirstSource >= SourceCount)
     return false;
   const auto MergeSource = registerOperand(*Merge, FirstSource + 1);
   if (!MergeSource)
     return false;
-  auto Built = Builder.buildExtract(
-      *Destination, *MergeSource,
-      Offset - FirstSource * MergeSourceSize);
+  auto Built =
+      Builder.buildExtract(*Destination, *MergeSource, Offset - FirstSource * MergeSourceSize);
   if (!Built)
     return std::unexpected(Built.error());
   UpdatedDefs.push_back(*Destination);
@@ -1497,10 +1438,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineExtract(
   return true;
 }
 
-inline Expected<Register>
-LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDef(
-    Register DefReg, std::uint64_t StartBit, std::uint64_t Size,
-    LowLevelType DestinationType) {
+inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDef(
+    Register DefReg, std::uint64_t StartBit, std::uint64_t Size, LowLevelType DestinationType) {
   CurrentBest = {};
   Visited.clear();
   auto Found = findValueFromDefImpl(DefReg, StartBit, Size, DestinationType);
@@ -1509,8 +1448,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDef(
   return *Found == DefReg ? Register{} : *Found;
 }
 
-inline Expected<Register>
-LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromConcat(
+inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromConcat(
     GConcatVectors &Instruction, std::uint64_t StartBit, std::uint64_t Size,
     LowLevelType DestinationType) {
   if (Instruction.getNumSources() == 0)
@@ -1524,8 +1462,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromConcat(
     return CurrentBest;
   const std::size_t SourceIndex = static_cast<std::size_t>(StartBit / SourceSize);
   const std::uint64_t SourceOffset = StartBit % SourceSize;
-  if (SourceIndex >= Instruction.getNumSources() ||
-      SourceOffset + Size > SourceSize)
+  if (SourceIndex >= Instruction.getNumSources() || SourceOffset + Size > SourceSize)
     return CurrentBest;
   const Register Source = Instruction.getSourceReg(SourceIndex);
   if (SourceOffset == 0 && Size == SourceSize)
@@ -1543,8 +1480,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromBuildVector(
   if (!FirstType)
     return std::unexpected(FirstType.error());
   const std::uint64_t SourceSize = FirstType->minimumBitWidth();
-  if (SourceSize == 0 || StartBit % SourceSize != 0 || Size < SourceSize ||
-      Size % SourceSize != 0)
+  if (SourceSize == 0 || StartBit % SourceSize != 0 || Size < SourceSize || Size % SourceSize != 0)
     return CurrentBest;
   const std::size_t FirstIndex = static_cast<std::size_t>(StartBit / SourceSize);
   const std::size_t SourceCount = static_cast<std::size_t>(Size / SourceSize);
@@ -1558,8 +1494,8 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromBuildVector(
   auto VectorType = LowLevelType::makeFixedVector(SourceCount, *FirstType);
   if (!VectorType)
     return std::unexpected(VectorType.error());
-  auto Legal = Combiner.isInstLegal(LegalizationQuery(
-      opcode(GenericOpcode::G_BUILD_VECTOR), {*VectorType, *FirstType}));
+  auto Legal = Combiner.isInstLegal(
+      LegalizationQuery(opcode(GenericOpcode::G_BUILD_VECTOR), {*VectorType, *FirstType}));
   if (!Legal)
     return std::unexpected(Legal.error());
   if (!*Legal)
@@ -1567,8 +1503,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromBuildVector(
 
   std::vector<Register> Sources;
   Sources.reserve(SourceCount);
-  for (std::size_t Index = FirstIndex; Index < FirstIndex + SourceCount;
-       ++Index)
+  for (std::size_t Index = FirstIndex; Index < FirstIndex + SourceCount; ++Index)
     Sources.push_back(Instruction.getSourceReg(Index));
   auto Destination = Combiner.MRI.createVirtualRegister(*VectorType);
   if (!Destination)
@@ -1579,8 +1514,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromBuildVector(
   return *Destination;
 }
 
-inline Expected<Register>
-LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromInsert(
+inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromInsert(
     MachineInstr &Instruction, std::uint64_t StartBit, std::uint64_t Size,
     LowLevelType DestinationType) {
   const auto Container = registerOperand(Instruction, 1);
@@ -1605,8 +1539,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromInsert(
   return Register{};
 }
 
-inline Expected<Register>
-LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromExtension(
+inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromExtension(
     MachineInstr &Instruction, std::uint64_t StartBit, std::uint64_t Size,
     LowLevelType DestinationType) {
   const auto Source = registerOperand(Instruction, 1);
@@ -1615,16 +1548,14 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromExtension(
   auto SourceType = Combiner.MRI.getType(*Source);
   if (!SourceType)
     return std::unexpected(SourceType.error());
-  if (!SourceType->isCategoryNeutralScalar() ||
-      StartBit + Size > SourceType->minimumBitWidth())
+  if (!SourceType->isCategoryNeutralScalar() || StartBit + Size > SourceType->minimumBitWidth())
     return CurrentBest;
   if (StartBit == 0 && SourceType->minimumBitWidth() == Size)
     CurrentBest = *Source;
   return findValueFromDefImpl(*Source, StartBit, Size, DestinationType);
 }
 
-inline Expected<Register>
-LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromTrunc(
+inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromTrunc(
     MachineInstr &Instruction, std::uint64_t StartBit, std::uint64_t Size,
     LowLevelType DestinationType) {
   const auto Source = registerOperand(Instruction, 1);
@@ -1638,10 +1569,8 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromTrunc(
   return findValueFromDefImpl(*Source, StartBit, Size, DestinationType);
 }
 
-inline Expected<Register>
-LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl(
-    Register DefReg, std::uint64_t StartBit, std::uint64_t Size,
-    LowLevelType DestinationType) {
+inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl(
+    Register DefReg, std::uint64_t StartBit, std::uint64_t Size, LowLevelType DestinationType) {
   if (!DefReg.isVirtual() || !Visited.insert(DefReg).second)
     return CurrentBest;
   auto Definition = Combiner.definitionIgnoringCopies(DefReg);
@@ -1654,21 +1583,18 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl(
 
   switch (static_cast<GenericOpcode>(Instruction->opcode().value())) {
   case GenericOpcode::G_CONCAT_VECTORS:
-    return findValueFromConcat(
-        castGenericMachineInstr<GConcatVectors>(*Instruction), StartBit, Size,
-        DestinationType);
+    return findValueFromConcat(castGenericMachineInstr<GConcatVectors>(*Instruction), StartBit,
+                               Size, DestinationType);
   case GenericOpcode::G_UNMERGE_VALUES: {
     auto DefType = Combiner.MRI.getType(DefReg);
     if (!DefType)
       return std::unexpected(DefType.error());
     const std::size_t DefIndex = getDefIndex(*Instruction, DefReg);
-    const auto Source = registerOperand(*Instruction,
-                                        Instruction->operandCount() - 1);
+    const auto Source = registerOperand(*Instruction, Instruction->operandCount() - 1);
     if (!Source)
       return CurrentBest;
-    auto Found = findValueFromDefImpl(
-        *Source, StartBit + DefIndex * DefType->minimumBitWidth(), Size,
-        DestinationType);
+    auto Found = findValueFromDefImpl(*Source, StartBit + DefIndex * DefType->minimumBitWidth(),
+                                      Size, DestinationType);
     if (!Found)
       return std::unexpected(Found.error());
     if (!Found->isNoRegister())
@@ -1678,8 +1604,8 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl(
     return CurrentBest;
   }
   case GenericOpcode::G_BUILD_VECTOR:
-    return findValueFromBuildVector(
-        castGenericMachineInstr<GBuildVector>(*Instruction), StartBit, Size);
+    return findValueFromBuildVector(castGenericMachineInstr<GBuildVector>(*Instruction), StartBit,
+                                    Size);
   case GenericOpcode::G_INSERT:
     return findValueFromInsert(*Instruction, StartBit, Size, DestinationType);
   case GenericOpcode::G_TRUNC:
@@ -1687,8 +1613,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl(
   case GenericOpcode::G_SEXT:
   case GenericOpcode::G_ZEXT:
   case GenericOpcode::G_ANYEXT:
-    return findValueFromExtension(*Instruction, StartBit, Size,
-                                  DestinationType);
+    return findValueFromExtension(*Instruction, StartBit, Size, DestinationType);
   case GenericOpcode::G_IMPLICIT_DEF: {
     auto Type = Combiner.MRI.getType(DefReg);
     if (!Type)
@@ -1708,10 +1633,8 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl(
   }
 }
 
-inline Expected<bool>
-LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineUnmergeDefs(
-    GUnmerge &Instruction, GISelChangeObserver &Observer,
-    std::vector<Register> &UpdatedDefs) {
+inline Expected<bool> LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineUnmergeDefs(
+    GUnmerge &Instruction, GISelChangeObserver &Observer, std::vector<Register> &UpdatedDefs) {
   if (Instruction.getNumDefs() == 0)
     return false;
   auto DestinationType = Combiner.MRI.getType(Instruction.getReg(0));
@@ -1722,8 +1645,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineUnmergeDefs(
     const Register Def = Instruction.getReg(Index);
     if (Combiner.MRI.useEmpty(Def))
       continue;
-    auto Found = findValueFromDef(Def, 0, DestinationType->minimumBitWidth(),
-                                  *DestinationType);
+    auto Found = findValueFromDef(Def, 0, DestinationType->minimumBitWidth(), *DestinationType);
     if (!Found)
       return std::unexpected(Found.error());
     if (Found->isNoRegister()) {
@@ -1737,8 +1659,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineUnmergeDefs(
       AllDead = false;
       continue;
     }
-    auto Replaced = Combiner.replaceRegOrBuildCopy(Def, *Found, UpdatedDefs,
-                                                   Observer);
+    auto Replaced = Combiner.replaceRegOrBuildCopy(Def, *Found, UpdatedDefs, Observer);
     if (!Replaced)
       return std::unexpected(Replaced.error());
     Observer.changingInstr(Instruction);
@@ -1772,16 +1693,14 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findUnmergeThatDefinesReg(
   return &castGenericMachineInstr<GUnmerge>(*Definition->first);
 }
 
-inline Expected<bool>
-LegalizationArtifactCombiner::ArtifactValueFinder::isSequenceFromUnmerge(
-    GMergeLikeInstr &Instruction, std::size_t MergeStartIndex,
-    GUnmerge *Unmerge, std::size_t UnmergeStartIndex,
-    std::size_t ElementCount, std::uint64_t ElementSize, bool AllowUndef) {
+inline Expected<bool> LegalizationArtifactCombiner::ArtifactValueFinder::isSequenceFromUnmerge(
+    GMergeLikeInstr &Instruction, std::size_t MergeStartIndex, GUnmerge *Unmerge,
+    std::size_t UnmergeStartIndex, std::size_t ElementCount, std::uint64_t ElementSize,
+    bool AllowUndef) {
   for (std::size_t Index = 0; Index < ElementCount; ++Index) {
     const Register Source = Instruction.getSourceReg(MergeStartIndex + Index);
     std::size_t SourceDefIndex = 0;
-    auto SourceUnmerge =
-        findUnmergeThatDefinesReg(Source, ElementSize, SourceDefIndex);
+    auto SourceUnmerge = findUnmergeThatDefinesReg(Source, ElementSize, SourceDefIndex);
     if (!SourceUnmerge)
       return std::unexpected(SourceUnmerge.error());
     if (*SourceUnmerge == Unmerge) {
@@ -1790,8 +1709,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::isSequenceFromUnmerge(
       continue;
     }
     MachineInstr *Definition = Combiner.MRI.getVRegDef(Source);
-    if (!AllowUndef ||
-        !hasOpcode(Definition, GenericOpcode::G_IMPLICIT_DEF))
+    if (!AllowUndef || !hasOpcode(Definition, GenericOpcode::G_IMPLICIT_DEF))
       return false;
   }
   return true;
diff --git a/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h b/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h
index 9a34898..19b3345 100644
--- a/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h
+++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h
@@ -8,6 +8,8 @@
 #include "rcc/CodeGen/MachineIRBuilder.h"
 #include "rcc/Support/Error.h"
 
+#include <vector>
+
 namespace rcc {
 
 class MachineFunction;
@@ -36,7 +38,36 @@ public:
                                               std::size_t OperandIndex = 0,
                                               GenericOpcode TruncOpcode = GenericOpcode::G_TRUNC);
 
+  [[nodiscard]] Expected<void> narrowScalar(MachineInstr &Instruction, std::size_t TypeIndex,
+                                            LowLevelType NarrowType);
+
 private:
+  [[nodiscard]] Expected<void> widenScalarMergeValues(MachineInstr &Instruction,
+                                                      std::size_t TypeIndex, LowLevelType WideType);
+  [[nodiscard]] Expected<void>
+  widenScalarUnmergeValues(MachineInstr &Instruction, std::size_t TypeIndex, LowLevelType WideType);
+  [[nodiscard]] Expected<void> insertParts(Register Destination, LowLevelType ResultType,
+                                           LowLevelType PartType,
+                                           const std::vector<Register> &PartRegisters,
+                                           LowLevelType LeftoverType = {},
+                                           const std::vector<Register> &LeftoverRegisters = {});
+  [[nodiscard]] Expected<void> extractGCDType(std::vector<Register> &Parts, LowLevelType GCDType,
+                                              Register Source);
+  [[nodiscard]] Expected<LowLevelType> extractGCDType(std::vector<Register> &Parts,
+                                                      LowLevelType DestinationType,
+                                                      LowLevelType NarrowType, Register Source);
+  [[nodiscard]] Expected<LowLevelType>
+  buildLCMMergePieces(LowLevelType DestinationType, LowLevelType NarrowType, LowLevelType GCDType,
+                      std::vector<Register> &Registers,
+                      GenericOpcode PadStrategy = GenericOpcode::G_ANYEXT);
+  [[nodiscard]] Expected<void>
+  buildWidenedRemergeToDst(Register Destination, LowLevelType LCMType,
+                           const std::vector<Register> &RemergeRegisters);
+  [[nodiscard]] Expected<void> narrowScalarAddSub(MachineInstr &Instruction, std::size_t TypeIndex,
+                                                  LowLevelType NarrowType);
+  [[nodiscard]] Expected<void> narrowScalarExt(MachineInstr &Instruction, std::size_t TypeIndex,
+                                               LowLevelType NarrowType);
+
   MachineFunction &Function;
   MachineRegisterInfo &MRI;
   const LegalizerInfo &Info;
diff --git a/backend/include/rcc/CodeGen/GlobalISel/Utils.h b/backend/include/rcc/CodeGen/GlobalISel/Utils.h
new file mode 100644
index 0000000..5af2fb4
--- /dev/null
+++ b/backend/include/rcc/CodeGen/GlobalISel/Utils.h
@@ -0,0 +1,54 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_GLOBALISEL_UTILS_H
+#define RCC_CODEGEN_GLOBALISEL_UTILS_H
+
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <span>
+#include <vector>
+
+namespace rcc {
+
+class MachineIRBuilder;
+class MachineInstr;
+class MachineRegisterInfo;
+class TargetDescription;
+
+/// Check whether an instruction only defines dead virtual registers and has no
+/// observable side effects.
+[[nodiscard]] bool isTriviallyDead(const MachineInstr &Instruction,
+                                   const MachineRegisterInfo &MRI,
+                                   const TargetDescription &Target) noexcept;
+
+[[nodiscard]] Expected<void> eraseInstrs(std::span<MachineInstr *const> Instructions,
+                                         MachineRegisterInfo &MRI,
+                                         const TargetDescription &Target);
+
+[[nodiscard]] Expected<void> eraseInstr(MachineInstr &Instruction,
+                                        MachineRegisterInfo &MRI,
+                                        const TargetDescription &Target);
+
+[[nodiscard]] Expected<void> extractParts(Register Reg, LowLevelType Type,
+                                          int PartCount,
+                                          std::vector<Register> &Parts,
+                                          MachineIRBuilder &MIRBuilder,
+                                          MachineRegisterInfo &MRI);
+
+[[nodiscard]] Expected<bool>
+extractParts(Register Reg, LowLevelType RegisterType, LowLevelType MainType,
+             LowLevelType &LeftoverType, std::vector<Register> &Parts,
+             std::vector<Register> &LeftoverParts,
+             MachineIRBuilder &MIRBuilder, MachineRegisterInfo &MRI);
+
+[[nodiscard]] Expected<LowLevelType> getLCMType(LowLevelType OriginalType,
+                                                LowLevelType TargetType);
+[[nodiscard]] Expected<LowLevelType> getGCDType(LowLevelType OriginalType,
+                                                LowLevelType TargetType);
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_GLOBALISEL_UTILS_H
diff --git a/backend/include/rcc/CodeGen/MachineIRBuilder.h b/backend/include/rcc/CodeGen/MachineIRBuilder.h
index 01cd648..70a313a 100644
--- a/backend/include/rcc/CodeGen/MachineIRBuilder.h
+++ b/backend/include/rcc/CodeGen/MachineIRBuilder.h
@@ -11,6 +11,7 @@
 
 #include <cstddef>
 #include <cstdint>
+#include <initializer_list>
 #include <memory>
 #include <optional>
 #include <string>
@@ -178,17 +179,20 @@ public:
   }
 
   [[nodiscard]] Expected<MachineInstrBuilder> buildInstr(Opcode InstructionOpcode) const;
+  [[nodiscard]] Expected<MachineInstr *> buildInstr(Opcode InstructionOpcode,
+                                                    std::initializer_list<Register> Destinations,
+                                                    std::initializer_list<Register> Sources) const;
   [[nodiscard]] Expected<MachineInstr *> buildTrunc(Register Destination, Register Source) const;
   [[nodiscard]] Expected<MachineInstr *> buildCopy(Register Destination, Register Source) const;
   [[nodiscard]] Expected<MachineInstr *> buildImplicitDef(Register Destination) const;
-  [[nodiscard]] Expected<MachineInstr *> buildAnyExt(Register Destination,
-                                                     Register Source) const;
+  [[nodiscard]] Expected<MachineInstr *> buildAnyExt(Register Destination, Register Source) const;
   [[nodiscard]] Expected<MachineInstr *> buildZExt(Register Destination, Register Source) const;
   [[nodiscard]] Expected<MachineInstr *> buildSExt(Register Destination, Register Source) const;
+  [[nodiscard]] Expected<MachineInstr *> buildUndef(Register Destination) const;
   [[nodiscard]] Expected<MachineInstr *> buildAnyExtOrTrunc(Register Destination,
                                                             Register Source) const;
   [[nodiscard]] Expected<MachineInstr *> buildSExtOrTrunc(Register Destination,
-                                                         Register Source) const;
+                                                          Register Source) const;
   [[nodiscard]] Expected<MachineInstr *> buildConstant(Register Destination, APInt Value) const;
   [[nodiscard]] Expected<MachineInstr *> buildConstant(Register Destination,
                                                        std::int64_t Value) const;
@@ -196,23 +200,40 @@ public:
                                                         std::uint32_t Width) const;
   [[nodiscard]] Expected<MachineInstr *> buildAnd(Register Destination, Register Left,
                                                   Register Right) const;
-  [[nodiscard]] Expected<MachineInstr *> buildMergeValues(
-      Register Destination, const std::vector<Register> &Sources) const;
-  [[nodiscard]] Expected<MachineInstr *> buildUnmergeValues(
-      const std::vector<Register> &Destinations, Register Source) const;
+  [[nodiscard]] Expected<MachineInstr *> buildOr(Register Destination, Register Left,
+                                                 Register Right) const;
+  [[nodiscard]] Expected<MachineInstr *> buildAdd(Register Destination, Register Left,
+                                                  Register Right) const;
+  [[nodiscard]] Expected<MachineInstr *> buildSub(Register Destination, Register Left,
+                                                  Register Right) const;
+  [[nodiscard]] Expected<MachineInstr *> buildShl(Register Destination, Register Left,
+                                                  Register Right) const;
+  [[nodiscard]] Expected<MachineInstr *> buildLShr(Register Destination, Register Left,
+                                                   Register Right) const;
+  [[nodiscard]] Expected<MachineInstr *> buildAShr(Register Destination, Register Left,
+                                                   Register Right) const;
+  [[nodiscard]] Expected<MachineInstr *> buildPtrToInt(Register Destination, Register Source) const;
+  [[nodiscard]] Expected<MachineInstr *> buildIntToPtr(Register Destination, Register Source) const;
+  [[nodiscard]] Expected<MachineInstr *> buildICmp(IntegerPredicate Predicate, Register Destination,
+                                                   Register Left, Register Right) const;
+  [[nodiscard]] Expected<MachineInstr *>
+  buildMergeLikeInstr(Register Destination, const std::vector<Register> &Sources) const;
+  [[nodiscard]] Expected<MachineInstr *>
+  buildMergeValues(Register Destination, const std::vector<Register> &Sources) const;
+  [[nodiscard]] Expected<MachineInstr *>
+  buildUnmergeValues(const std::vector<Register> &Destinations, Register Source) const;
   [[nodiscard]] Expected<MachineInstr *> buildExtract(Register Destination, Register Source,
                                                       std::uint64_t Offset) const;
+  [[nodiscard]] Expected<MachineInstr *> buildInsert(Register Destination, Register Source,
+                                                     Register Inserted, std::uint64_t Offset) const;
 
 private:
-  [[nodiscard]] Expected<MachineInstr *> buildUnary(Opcode InstructionOpcode,
-                                                    Register Destination,
+  [[nodiscard]] Expected<MachineInstr *> buildUnary(Opcode InstructionOpcode, Register Destination,
                                                     Register Source) const;
-  [[nodiscard]] Expected<MachineInstr *> buildBinary(Opcode InstructionOpcode,
-                                                     Register Destination, Register Left,
-                                                     Register Right) const;
-  [[nodiscard]] Expected<MachineInstr *> buildExtOrTrunc(Opcode ExtensionOpcode,
-                                                         Register Destination,
-                                                         Register Source) const;
+  [[nodiscard]] Expected<MachineInstr *> buildBinary(Opcode InstructionOpcode, Register Destination,
+                                                     Register Left, Register Right) const;
+  [[nodiscard]] Expected<MachineInstr *>
+  buildExtOrTrunc(Opcode ExtensionOpcode, Register Destination, Register Source) const;
   [[nodiscard]] Expected<LowLevelType> registerType(Register Reg) const;
   [[nodiscard]] Expected<void> validateBlock(const MachineBasicBlock &Block) const;
   [[nodiscard]] Expected<void> validateInstruction(const MachineInstr &Instruction) const;
diff --git a/backend/include/rcc/CodeGen/MachineRegisterInfo.h b/backend/include/rcc/CodeGen/MachineRegisterInfo.h
index 456115f..d0353b3 100644
--- a/backend/include/rcc/CodeGen/MachineRegisterInfo.h
+++ b/backend/include/rcc/CodeGen/MachineRegisterInfo.h
@@ -109,6 +109,7 @@ public:
 
   [[nodiscard]] Expected<Register> createVirtualRegister();
   [[nodiscard]] Expected<Register> createVirtualRegister(LowLevelType Type);
+  [[nodiscard]] Expected<Register> cloneVirtualRegister(Register Reg);
   [[nodiscard]] Expected<void> eraseVirtualRegister(Register Reg);
 
   [[nodiscard]] bool isKnownVirtualRegister(Register Reg) const noexcept;
diff --git a/backend/include/rcc/CodeGen/TargetDescription.h b/backend/include/rcc/CodeGen/TargetDescription.h
index 7e41a58..56d328e 100644
--- a/backend/include/rcc/CodeGen/TargetDescription.h
+++ b/backend/include/rcc/CodeGen/TargetDescription.h
@@ -8,6 +8,7 @@
 #include "rcc/CodeGen/TargetRegisterInfo.h"
 #include "rcc/Support/Error.h"
 
+#include <cstdint>
 #include <optional>
 #include <span>
 #include <utility>
@@ -23,6 +24,18 @@ class MachineMemOperand;
 class MachineRegisterInfo;
 struct VirtualRegisterInfo;
 
+enum class BooleanContent : std::uint8_t {
+  Undefined,
+  ZeroOrOne,
+  ZeroOrNegativeOne,
+};
+
+struct TargetBooleanContentInfo final {
+  BooleanContent ScalarInteger = BooleanContent::Undefined;
+  BooleanContent ScalarFloatingPoint = BooleanContent::Undefined;
+  BooleanContent Vector = BooleanContent::Undefined;
+};
+
 class TargetDescription final {
 public:
   TargetDescription(const TargetDescription &) = delete;
@@ -31,9 +44,9 @@ public:
   TargetDescription &operator=(TargetDescription &&) noexcept = default;
   ~TargetDescription() = default;
 
-  [[nodiscard]] static Expected<TargetDescription> create(InstructionSet Instructions,
-                                                          TargetRegisterInfo Registers,
-                                                          TargetMIRTextInfoDesc MIRText = {});
+  [[nodiscard]] static Expected<TargetDescription>
+  create(InstructionSet Instructions, TargetRegisterInfo Registers,
+         TargetMIRTextInfoDesc MIRText = {}, TargetBooleanContentInfo BooleanInfo = {});
 
   [[nodiscard]] const InstructionSet &instructions() const noexcept {
     return Instructions;
@@ -47,6 +60,13 @@ public:
     return MIRText;
   }
 
+  [[nodiscard]] BooleanContent getBooleanContents(bool IsVector,
+                                                  bool IsFloatingPoint) const noexcept {
+    if (IsVector)
+      return BooleanInfo.Vector;
+    return IsFloatingPoint ? BooleanInfo.ScalarFloatingPoint : BooleanInfo.ScalarInteger;
+  }
+
   [[nodiscard]] const InstructionDescriptor *
   instructionDescriptor(Opcode InstructionOpcode) const noexcept {
     return Instructions.descriptor(InstructionOpcode);
@@ -87,9 +107,9 @@ public:
 
 private:
   TargetDescription(InstructionSet Instructions, TargetRegisterInfo Registers,
-                    TargetMIRTextInfo MIRText)
+                    TargetMIRTextInfo MIRText, TargetBooleanContentInfo BooleanInfo)
       : Instructions(std::move(Instructions)), Registers(std::move(Registers)),
-        MIRText(std::move(MIRText)) {}
+        MIRText(std::move(MIRText)), BooleanInfo(BooleanInfo) {}
 
   [[nodiscard]] Expected<void> validateTargetOperand(const OperandDescriptor *Descriptor,
                                                      const MachineOperand &Operand,
@@ -101,6 +121,7 @@ private:
   InstructionSet Instructions;
   TargetRegisterInfo Registers;
   TargetMIRTextInfo MIRText;
+  TargetBooleanContentInfo BooleanInfo;
 };
 
 } // namespace rcc
diff --git a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
index b7064e3..3b01e9b 100644
--- a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
+++ b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
@@ -3,16 +3,19 @@
 set(
   RCCBackendGlobalISelSources
   GISelChangeObserver.cpp
+  GISelValueTracking.cpp
   InstructionSelect.cpp
   Legalizer.cpp
   LegalizerHelper.cpp
   LegalizerInfo.cpp
   RegBankSelect.cpp
+  Utils.cpp
 )
 
 set(
   RCCBackendGlobalISelHeaders
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelWorkList.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/InstructionSelect.h"
@@ -22,25 +25,30 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/RegBankSelect.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/Utils.h"
 )
 
 target_sources(RCCBackendCodeGen PRIVATE ${RCCBackendGlobalISelSources})
 
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerHelper.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/Utils.cpp"
   ${RCCBackendGlobalISelHeaders}
 )
 
 rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerHelper.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/Utils.cpp"
 )
diff --git a/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp
new file mode 100644
index 0000000..fe694ab
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp
@@ -0,0 +1,514 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/GISelValueTracking.h"
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] std::optional<Register> registerOperand(const MachineInstr &Instruction,
+                                                      std::size_t Index) noexcept {
+  const MachineOperand *Operand = Instruction.operandAt(Index);
+  return Operand == nullptr ? std::nullopt : Operand->registerValue();
+}
+
+[[nodiscard]] Expected<APInt> zero(std::uint32_t BitWidth) {
+  return APInt::fromUnsigned(BitWidth, 0);
+}
+
+[[nodiscard]] Expected<APInt> resizeMask(const APInt &Value, std::uint32_t BitWidth) {
+  if (Value.bitWidth() == BitWidth)
+    return Value;
+  if (Value.bitWidth() == 0)
+    return zero(BitWidth);
+  if (Value.bitWidth() < BitWidth)
+    return Value.zext(BitWidth);
+  return Value.trunc(BitWidth);
+}
+
+[[nodiscard]] Expected<APInt> highBitsMask(std::uint32_t BitWidth, std::uint32_t LowBitCount) {
+  auto LowBits = APInt::getLowBitsSet(BitWidth, LowBitCount);
+  if (!LowBits)
+    return std::unexpected(LowBits.error());
+  return LowBits->bitwiseNot();
+}
+
+[[nodiscard]] Expected<APInt> mergeMasks(const APInt &Left, const APInt &Right) {
+  return Left.bitwiseOr(Right);
+}
+
+[[nodiscard]] Expected<APInt> intersectMasks(const APInt &Left, const APInt &Right) {
+  return Left.bitwiseAnd(Right);
+}
+
+[[nodiscard]] Expected<APInt> constantAtWidth(const APInt &Value, std::uint32_t BitWidth) {
+  return resizeMask(Value, BitWidth);
+}
+
+[[nodiscard]] std::optional<std::uint32_t>
+constantShiftAmount(Register Reg, const MachineRegisterInfo &MRI, std::uint32_t BitWidth) {
+  const MachineInstr *Definition = MRI.getVRegDef(Reg);
+  if (Definition == nullptr || Definition->opcode() != opcode(GenericOpcode::G_CONSTANT))
+    return std::nullopt;
+  const MachineOperand *ValueOperand = Definition->operandAt(1);
+  const auto *Immediate =
+      ValueOperand == nullptr ? nullptr : ValueOperand->getIf<IntegerImmediateOperand>();
+  if (Immediate == nullptr || Immediate->Value.activeBitWidth() > 32)
+    return std::nullopt;
+  const std::uint64_t Amount = Immediate->Value.word(0);
+  if (Amount >= BitWidth)
+    return std::nullopt;
+  return static_cast<std::uint32_t>(Amount);
+}
+
+[[nodiscard]] Expected<APInt> shiftMaskLeft(const APInt &Value, std::uint32_t Amount) {
+  std::vector<std::uint64_t> Words(Value.words().size(), 0);
+  for (std::uint32_t Bit = 0; Bit + Amount < Value.bitWidth(); ++Bit) {
+    if (Value.testBit(Bit)) {
+      const std::uint32_t DestinationBit = Bit + Amount;
+      Words[DestinationBit / 64U] |= std::uint64_t{1} << (DestinationBit % 64U);
+    }
+  }
+  return APInt::create(Value.bitWidth(), Words);
+}
+
+[[nodiscard]] Expected<APInt> shiftMaskRight(const APInt &Value, std::uint32_t Amount) {
+  std::vector<std::uint64_t> Words(Value.words().size(), 0);
+  for (std::uint32_t Bit = Amount; Bit < Value.bitWidth(); ++Bit) {
+    if (Value.testBit(Bit)) {
+      const std::uint32_t DestinationBit = Bit - Amount;
+      Words[DestinationBit / 64U] |= std::uint64_t{1} << (DestinationBit % 64U);
+    }
+  }
+  return APInt::create(Value.bitWidth(), Words);
+}
+
+[[nodiscard]] std::uint32_t constantNumSignBits(const APInt &Value) noexcept {
+  if (Value.bitWidth() == 0)
+    return 1;
+  if (Value.isNegative())
+    return static_cast<std::uint32_t>(Value.countlOne());
+  auto Inverted = Value.bitwiseNot();
+  return Inverted ? static_cast<std::uint32_t>(Inverted->countlOne()) : 1U;
+}
+
+} // namespace
+
+GISelValueTracking::GISelValueTracking(MachineFunction &Function, const TargetDescription &Target,
+                                       unsigned MaxDepth) noexcept
+    : Function(Function), MRI(Function.registerInfo()), Target(Target), MaxDepth(MaxDepth) {}
+
+Expected<GISelValueTracking::KnownBits>
+GISelValueTracking::makeUnknown(std::uint32_t BitWidth) const {
+  auto Zero = zero(BitWidth);
+  if (!Zero)
+    return std::unexpected(Zero.error());
+  auto One = zero(BitWidth);
+  if (!One)
+    return std::unexpected(One.error());
+  return KnownBits{.Zero = std::move(*Zero), .One = std::move(*One)};
+}
+
+Expected<GISelValueTracking::KnownBits> GISelValueTracking::getKnownBits(Register Reg,
+                                                                         unsigned Depth) const {
+  auto Type = MRI.getType(Reg);
+  if (!Type)
+    return std::unexpected(Type.error());
+  const std::uint32_t BitWidth = Type->scalarBitWidth();
+  auto Unknown = makeUnknown(BitWidth);
+  if (!Unknown)
+    return std::unexpected(Unknown.error());
+  if (Depth >= MaxDepth)
+    return Unknown;
+
+  const MachineInstr *Definition = MRI.getVRegDef(Reg);
+  if (Definition == nullptr)
+    return Unknown;
+
+  const auto Opcode = static_cast<GenericOpcode>(Definition->opcode().value());
+  if (Opcode == GenericOpcode::G_CONSTANT) {
+    const MachineOperand *ValueOperand = Definition->operandAt(1);
+    const auto *Immediate =
+        ValueOperand == nullptr ? nullptr : ValueOperand->getIf<IntegerImmediateOperand>();
+    if (Immediate == nullptr)
+      return Unknown;
+    auto Value = constantAtWidth(Immediate->Value, BitWidth);
+    if (!Value)
+      return std::unexpected(Value.error());
+    auto KnownZero = Value->bitwiseNot();
+    if (!KnownZero)
+      return std::unexpected(KnownZero.error());
+    return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*Value)};
+  }
+
+  if (Opcode == GenericOpcode::COPY) {
+    const auto Source = registerOperand(*Definition, 1);
+    if (!Source || !Source->isVirtual())
+      return Unknown;
+    auto SourceBits = getKnownBits(*Source, Depth);
+    if (!SourceBits)
+      return std::unexpected(SourceBits.error());
+    auto KnownZero = resizeMask(SourceBits->Zero, BitWidth);
+    if (!KnownZero)
+      return std::unexpected(KnownZero.error());
+    auto KnownOne = resizeMask(SourceBits->One, BitWidth);
+    if (!KnownOne)
+      return std::unexpected(KnownOne.error());
+    return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+  }
+
+  if (Opcode == GenericOpcode::G_ICMP || Opcode == GenericOpcode::G_FCMP) {
+    if (!Type->isVector() && BitWidth > 1 &&
+        Target.getBooleanContents(false, Opcode == GenericOpcode::G_FCMP) ==
+            BooleanContent::ZeroOrOne) {
+      auto KnownZero = highBitsMask(BitWidth, 1);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      Unknown->Zero = std::move(*KnownZero);
+    }
+    return Unknown;
+  }
+
+  switch (Opcode) {
+  case GenericOpcode::G_UADDO:
+  case GenericOpcode::G_UADDE:
+  case GenericOpcode::G_USUBO:
+  case GenericOpcode::G_USUBE:
+  case GenericOpcode::G_SADDO:
+  case GenericOpcode::G_SADDE:
+  case GenericOpcode::G_SSUBO:
+  case GenericOpcode::G_SSUBE:
+  case GenericOpcode::G_UMULO:
+  case GenericOpcode::G_SMULO: {
+    const auto BooleanResult = registerOperand(*Definition, 1);
+    if (BooleanResult && *BooleanResult == Reg && !Type->isVector() && BitWidth > 1 &&
+        Target.getBooleanContents(false, false) == BooleanContent::ZeroOrOne) {
+      auto KnownZero = highBitsMask(BitWidth, 1);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      Unknown->Zero = std::move(*KnownZero);
+    }
+    return Unknown;
+  }
+  default:
+    break;
+  }
+
+  const auto Source = registerOperand(*Definition, 1);
+  if (!Source)
+    return Unknown;
+
+  if (Opcode == GenericOpcode::G_TRUNC || Opcode == GenericOpcode::G_ANYEXT ||
+      Opcode == GenericOpcode::G_ZEXT || Opcode == GenericOpcode::G_SEXT ||
+      Opcode == GenericOpcode::G_ASSERT_ZEXT || Opcode == GenericOpcode::G_ASSERT_SEXT ||
+      Opcode == GenericOpcode::G_SEXT_INREG) {
+    auto SourceBits = getKnownBits(*Source, Depth + 1U);
+    if (!SourceBits)
+      return std::unexpected(SourceBits.error());
+    auto SourceType = MRI.getType(*Source);
+    if (!SourceType)
+      return std::unexpected(SourceType.error());
+    const std::uint32_t SourceWidth = SourceType->scalarBitWidth();
+    auto KnownZero = resizeMask(SourceBits->Zero, BitWidth);
+    if (!KnownZero)
+      return std::unexpected(KnownZero.error());
+    auto KnownOne = resizeMask(SourceBits->One, BitWidth);
+    if (!KnownOne)
+      return std::unexpected(KnownOne.error());
+
+    if (Opcode == GenericOpcode::G_ZEXT && SourceWidth < BitWidth) {
+      auto HighZero = highBitsMask(BitWidth, SourceWidth);
+      if (!HighZero)
+        return std::unexpected(HighZero.error());
+      KnownZero = mergeMasks(*KnownZero, *HighZero);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+    }
+
+    std::uint32_t ExtendedFrom = SourceWidth;
+    if (Opcode == GenericOpcode::G_ASSERT_ZEXT || Opcode == GenericOpcode::G_ASSERT_SEXT ||
+        Opcode == GenericOpcode::G_SEXT_INREG) {
+      const MachineOperand *WidthOperand = Definition->operandAt(2);
+      const auto *Width = WidthOperand == nullptr ? nullptr : WidthOperand->getIf<std::int64_t>();
+      if (Width == nullptr || *Width <= 0 || static_cast<std::uint64_t>(*Width) > BitWidth)
+        return Unknown;
+      ExtendedFrom = static_cast<std::uint32_t>(*Width);
+    }
+
+    if (Opcode == GenericOpcode::G_ASSERT_ZEXT) {
+      auto HighZero = highBitsMask(BitWidth, ExtendedFrom);
+      if (!HighZero)
+        return std::unexpected(HighZero.error());
+      KnownZero = mergeMasks(*KnownZero, *HighZero);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+    }
+
+    if ((Opcode == GenericOpcode::G_SEXT || Opcode == GenericOpcode::G_ASSERT_SEXT ||
+         Opcode == GenericOpcode::G_SEXT_INREG) &&
+        ExtendedFrom < BitWidth) {
+      auto HighBits = highBitsMask(BitWidth, ExtendedFrom);
+      if (!HighBits)
+        return std::unexpected(HighBits.error());
+      if (KnownZero->testBit(ExtendedFrom - 1U)) {
+        KnownZero = mergeMasks(*KnownZero, *HighBits);
+        if (!KnownZero)
+          return std::unexpected(KnownZero.error());
+      } else if (KnownOne->testBit(ExtendedFrom - 1U)) {
+        KnownOne = mergeMasks(*KnownOne, *HighBits);
+        if (!KnownOne)
+          return std::unexpected(KnownOne.error());
+      }
+    }
+
+    return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+  }
+
+  if (Opcode == GenericOpcode::G_AND || Opcode == GenericOpcode::G_OR ||
+      Opcode == GenericOpcode::G_XOR) {
+    const auto Right = registerOperand(*Definition, 2);
+    if (!Right)
+      return Unknown;
+    auto LeftBits = getKnownBits(*Source, Depth + 1U);
+    if (!LeftBits)
+      return std::unexpected(LeftBits.error());
+    auto RightBits = getKnownBits(*Right, Depth + 1U);
+    if (!RightBits)
+      return std::unexpected(RightBits.error());
+
+    if (Opcode == GenericOpcode::G_AND) {
+      auto KnownZero = mergeMasks(LeftBits->Zero, RightBits->Zero);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      auto KnownOne = intersectMasks(LeftBits->One, RightBits->One);
+      if (!KnownOne)
+        return std::unexpected(KnownOne.error());
+      return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+    }
+    if (Opcode == GenericOpcode::G_OR) {
+      auto KnownZero = intersectMasks(LeftBits->Zero, RightBits->Zero);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      auto KnownOne = mergeMasks(LeftBits->One, RightBits->One);
+      if (!KnownOne)
+        return std::unexpected(KnownOne.error());
+      return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+    }
+
+    auto BothZero = intersectMasks(LeftBits->Zero, RightBits->Zero);
+    if (!BothZero)
+      return std::unexpected(BothZero.error());
+    auto BothOne = intersectMasks(LeftBits->One, RightBits->One);
+    if (!BothOne)
+      return std::unexpected(BothOne.error());
+    auto KnownZero = mergeMasks(*BothZero, *BothOne);
+    if (!KnownZero)
+      return std::unexpected(KnownZero.error());
+    auto LeftZeroRightOne = intersectMasks(LeftBits->Zero, RightBits->One);
+    if (!LeftZeroRightOne)
+      return std::unexpected(LeftZeroRightOne.error());
+    auto LeftOneRightZero = intersectMasks(LeftBits->One, RightBits->Zero);
+    if (!LeftOneRightZero)
+      return std::unexpected(LeftOneRightZero.error());
+    auto KnownOne = mergeMasks(*LeftZeroRightOne, *LeftOneRightZero);
+    if (!KnownOne)
+      return std::unexpected(KnownOne.error());
+    return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+  }
+
+  if (Opcode == GenericOpcode::G_SHL || Opcode == GenericOpcode::G_LSHR ||
+      Opcode == GenericOpcode::G_ASHR) {
+    const auto AmountReg = registerOperand(*Definition, 2);
+    if (!AmountReg)
+      return Unknown;
+    const auto Amount = constantShiftAmount(*AmountReg, MRI, BitWidth);
+    if (!Amount)
+      return Unknown;
+    auto SourceBits = getKnownBits(*Source, Depth + 1U);
+    if (!SourceBits)
+      return std::unexpected(SourceBits.error());
+
+    if (Opcode == GenericOpcode::G_SHL) {
+      auto KnownZero = shiftMaskLeft(SourceBits->Zero, *Amount);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      auto LowZero = APInt::getLowBitsSet(BitWidth, *Amount);
+      if (!LowZero)
+        return std::unexpected(LowZero.error());
+      KnownZero = mergeMasks(*KnownZero, *LowZero);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+      auto KnownOne = shiftMaskLeft(SourceBits->One, *Amount);
+      if (!KnownOne)
+        return std::unexpected(KnownOne.error());
+      return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+    }
+
+    auto KnownZero = shiftMaskRight(SourceBits->Zero, *Amount);
+    if (!KnownZero)
+      return std::unexpected(KnownZero.error());
+    auto KnownOne = shiftMaskRight(SourceBits->One, *Amount);
+    if (!KnownOne)
+      return std::unexpected(KnownOne.error());
+    auto HighBits = highBitsMask(BitWidth, BitWidth - *Amount);
+    if (!HighBits)
+      return std::unexpected(HighBits.error());
+    if (Opcode == GenericOpcode::G_LSHR || SourceBits->Zero.testBit(BitWidth - 1U)) {
+      KnownZero = mergeMasks(*KnownZero, *HighBits);
+      if (!KnownZero)
+        return std::unexpected(KnownZero.error());
+    } else if (SourceBits->One.testBit(BitWidth - 1U)) {
+      KnownOne = mergeMasks(*KnownOne, *HighBits);
+      if (!KnownOne)
+        return std::unexpected(KnownOne.error());
+    }
+    return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)};
+  }
+
+  return Unknown;
+}
+
+Expected<APInt> GISelValueTracking::getKnownZeroes(Register Reg) const {
+  auto Known = getKnownBits(Reg);
+  if (!Known)
+    return std::unexpected(Known.error());
+  return std::move(Known->Zero);
+}
+
+Expected<std::uint32_t> GISelValueTracking::computeNumSignBits(Register Reg, unsigned Depth) const {
+  auto Type = MRI.getType(Reg);
+  if (!Type)
+    return std::unexpected(Type.error());
+  const std::uint32_t BitWidth = Type->scalarBitWidth();
+  if (Depth >= MaxDepth)
+    return 1U;
+
+  const MachineInstr *Definition = MRI.getVRegDef(Reg);
+  if (Definition == nullptr)
+    return 1U;
+  const auto Opcode = static_cast<GenericOpcode>(Definition->opcode().value());
+
+  if (Opcode == GenericOpcode::G_CONSTANT) {
+    const MachineOperand *ValueOperand = Definition->operandAt(1);
+    const auto *Immediate =
+        ValueOperand == nullptr ? nullptr : ValueOperand->getIf<IntegerImmediateOperand>();
+    if (Immediate == nullptr)
+      return 1U;
+    auto Value = constantAtWidth(Immediate->Value, BitWidth);
+    if (!Value)
+      return std::unexpected(Value.error());
+    return constantNumSignBits(*Value);
+  }
+
+  const auto Source = registerOperand(*Definition, 1);
+  if (Opcode == GenericOpcode::COPY && Source && Source->isVirtual())
+    return computeNumSignBits(*Source, Depth);
+
+  if (Opcode == GenericOpcode::G_SEXT && Source) {
+    auto SourceType = MRI.getType(*Source);
+    if (!SourceType)
+      return std::unexpected(SourceType.error());
+    auto SourceSignBits = computeNumSignBits(*Source, Depth + 1U);
+    if (!SourceSignBits)
+      return std::unexpected(SourceSignBits.error());
+    return std::min(BitWidth, *SourceSignBits + BitWidth - SourceType->scalarBitWidth());
+  }
+
+  if ((Opcode == GenericOpcode::G_ASSERT_SEXT || Opcode == GenericOpcode::G_SEXT_INREG) && Source) {
+    const MachineOperand *WidthOperand = Definition->operandAt(2);
+    const auto *Width = WidthOperand == nullptr ? nullptr : WidthOperand->getIf<std::int64_t>();
+    if (Width != nullptr && *Width > 0 && static_cast<std::uint64_t>(*Width) <= BitWidth) {
+      auto SourceSignBits = computeNumSignBits(*Source, Depth + 1U);
+      if (!SourceSignBits)
+        return std::unexpected(SourceSignBits.error());
+      return std::max(*SourceSignBits, BitWidth - static_cast<std::uint32_t>(*Width) + 1U);
+    }
+  }
+
+  if ((Opcode == GenericOpcode::G_AND || Opcode == GenericOpcode::G_OR ||
+       Opcode == GenericOpcode::G_XOR) &&
+      Source) {
+    const auto Right = registerOperand(*Definition, 2);
+    if (Right) {
+      auto LeftSignBits = computeNumSignBits(*Source, Depth + 1U);
+      if (!LeftSignBits)
+        return std::unexpected(LeftSignBits.error());
+      if (*LeftSignBits != 1) {
+        auto RightSignBits = computeNumSignBits(*Right, Depth + 1U);
+        if (!RightSignBits)
+          return std::unexpected(RightSignBits.error());
+        if (*RightSignBits != 1)
+          return std::min(*LeftSignBits, *RightSignBits);
+      }
+    }
+  }
+
+  if (Opcode == GenericOpcode::G_TRUNC && Source) {
+    auto SourceType = MRI.getType(*Source);
+    if (!SourceType)
+      return std::unexpected(SourceType.error());
+    const std::uint32_t SourceWidth = SourceType->scalarBitWidth();
+    auto SourceSignBits = computeNumSignBits(*Source, Depth + 1U);
+    if (!SourceSignBits)
+      return std::unexpected(SourceSignBits.error());
+    if (SourceWidth > BitWidth && *SourceSignBits > SourceWidth - BitWidth)
+      return *SourceSignBits - (SourceWidth - BitWidth);
+  }
+
+  if (Opcode == GenericOpcode::G_ICMP || Opcode == GenericOpcode::G_FCMP) {
+    if (BitWidth > 1) {
+      const BooleanContent Contents =
+          Target.getBooleanContents(Type->isVector(), Opcode == GenericOpcode::G_FCMP);
+      if (Contents == BooleanContent::ZeroOrNegativeOne)
+        return BitWidth;
+      if (Contents == BooleanContent::ZeroOrOne)
+        return BitWidth - 1U;
+    }
+  }
+
+  switch (Opcode) {
+  case GenericOpcode::G_UADDO:
+  case GenericOpcode::G_UADDE:
+  case GenericOpcode::G_USUBO:
+  case GenericOpcode::G_USUBE:
+  case GenericOpcode::G_SADDO:
+  case GenericOpcode::G_SADDE:
+  case GenericOpcode::G_SSUBO:
+  case GenericOpcode::G_SSUBE:
+  case GenericOpcode::G_UMULO:
+  case GenericOpcode::G_SMULO: {
+    const auto BooleanResult = registerOperand(*Definition, 1);
+    if (BooleanResult && *BooleanResult == Reg &&
+        Target.getBooleanContents(Type->isVector(), false) == BooleanContent::ZeroOrNegativeOne)
+      return BitWidth;
+    break;
+  }
+  default:
+    break;
+  }
+
+  auto Known = getKnownBits(Reg, Depth);
+  if (!Known)
+    return std::unexpected(Known.error());
+  std::uint32_t KnownSignBits = 1;
+  if (Known->Zero.testBit(BitWidth - 1U))
+    KnownSignBits = static_cast<std::uint32_t>(Known->Zero.countlOne());
+  else if (Known->One.testBit(BitWidth - 1U))
+    KnownSignBits = static_cast<std::uint32_t>(Known->One.countlOne());
+  return std::max(1U, KnownSignBits);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
index d971b42..c749039 100644
--- a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
+++ b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
@@ -4,9 +4,11 @@
 
 #include "rcc/CodeGen/GenericOpcodes.h"
 #include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+#include "rcc/CodeGen/GlobalISel/GISelValueTracking.h"
 #include "rcc/CodeGen/GlobalISel/GISelWorkList.h"
 #include "rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
 #include "rcc/CodeGen/GlobalISel/LegalizerHelper.h"
+#include "rcc/CodeGen/GlobalISel/Utils.h"
 #include "rcc/CodeGen/LiveVariables.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineFunction.h"
@@ -295,7 +297,9 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi
   MachineFunctionDelegateInstaller ObserverInstaller(Function, Observer);
   MachineIRBuilder Builder(Function, Target);
   LegalizerHelper Helper(Function, *Info, Observer, Builder);
-  LegalizationArtifactCombiner ArtifactCombiner(Builder, Function.registerInfo(), *Info);
+  GISelValueTracking ValueTracking(Function, Target);
+  LegalizationArtifactCombiner ArtifactCombiner(Builder, Function.registerInfo(), *Info,
+                                                &ValueTracking);
 
   do {
     while (!InstructionWorklist.empty()) {
@@ -303,6 +307,15 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi
       if (Instruction == nullptr || Instruction->parent() == nullptr)
         continue;
 
+      if (isTriviallyDead(*Instruction, Function.registerInfo(), Target)) {
+        auto Removed = eraseInstr(*Instruction, Function.registerInfo(), Target);
+        if (!Removed)
+          return std::unexpected(Removed.error());
+        Result.Changed = true;
+        Result.Changes.add(MachinePassChange::Instructions);
+        continue;
+      }
+
       const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
       if (Descriptor == nullptr)
         return std::unexpected(
@@ -381,19 +394,23 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi
       MachineInstr *Instruction = ArtifactWorklist.popBack();
       if (Instruction == nullptr || Instruction->parent() == nullptr)
         continue;
+      if (isTriviallyDead(*Instruction, Function.registerInfo(), Target)) {
+        auto Removed = eraseInstr(*Instruction, Function.registerInfo(), Target);
+        if (!Removed)
+          return std::unexpected(Removed.error());
+        Result.Changed = true;
+        Result.Changes.add(MachinePassChange::Instructions);
+        continue;
+      }
       std::vector<MachineInstr *> DeadInstructions;
       auto Combined =
           ArtifactCombiner.tryCombineInstruction(*Instruction, DeadInstructions, Observer);
       if (!Combined)
         return std::unexpected(Combined.error());
       if (*Combined) {
-        for (MachineInstr *Dead : DeadInstructions) {
-          if (Dead == nullptr || Dead->parent() == nullptr)
-            continue;
-          auto Removed = Dead->parent()->removeInstruction(*Dead);
-          if (!Removed)
-            return std::unexpected(Removed.error());
-        }
+        auto Removed = eraseInstrs(DeadInstructions, Function.registerInfo(), Target);
+        if (!Removed)
+          return std::unexpected(Removed.error());
         Result.Changed = true;
         Result.Changes.add(MachinePassChange::Instructions);
         continue;
diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp
index 1e52214..0ea3783 100644
--- a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp
+++ b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp
@@ -3,6 +3,7 @@
 #include "rcc/CodeGen/GlobalISel/LegalizerHelper.h"
 
 #include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+#include "rcc/CodeGen/GlobalISel/Utils.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineInstr.h"
@@ -14,7 +15,9 @@
 #include <bit>
 #include <cstddef>
 #include <cstdint>
+#include <numeric>
 #include <optional>
+#include <span>
 #include <utility>
 
 namespace rcc {
@@ -113,6 +116,539 @@ LegalizerHelper::LegalizerHelper(MachineFunction &Function, const LegalizerInfo
     : MIRBuilder(MIRBuilder), Observer(Observer), Function(Function), MRI(Function.registerInfo()),
       Info(Info) {}
 
+Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction,
+                                                       std::size_t TypeIndex,
+                                                       LowLevelType WideType) {
+  if (TypeIndex != 1)
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "G_MERGE_VALUES widening requires type index one");
+  if (Instruction.operandCount() < 3)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "G_MERGE_VALUES requires a destination and sources");
+
+  const Register *Destination = Instruction.operandAt(0)->getIf<Register>();
+  const Register *FirstSource = Instruction.operandAt(1)->getIf<Register>();
+  if (Destination == nullptr || FirstSource == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "G_MERGE_VALUES requires register operands");
+  auto DestinationType = MRI.getType(*Destination);
+  auto SourceType = MRI.getType(*FirstSource);
+  if (!DestinationType)
+    return std::unexpected(DestinationType.error());
+  if (!SourceType)
+    return std::unexpected(SourceType.error());
+  if (DestinationType->isVector())
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "vector G_MERGE_VALUES widening is not supported");
+
+  const std::uint64_t DestinationSize = DestinationType->minimumBitWidth();
+  const std::uint64_t SourceSize = SourceType->minimumBitWidth();
+  const std::uint64_t WideSize = WideType.minimumBitWidth();
+  const std::uint64_t MergeCount = (DestinationSize + WideSize - 1U) / WideSize;
+  const std::size_t SourceCount = Instruction.operandCount() - 1U;
+  const std::uint64_t PartSize = DestinationSize / SourceCount;
+
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+
+  if (WideSize >= DestinationSize) {
+    auto Result = MRI.createVirtualRegister(WideType);
+    if (!Result)
+      return std::unexpected(Result.error());
+    if (auto Built = MIRBuilder.buildZExt(*Result, *FirstSource); !Built)
+      return std::unexpected(Built.error());
+    Register ResultRegister = *Result;
+
+    for (std::size_t Index = 2; Index != Instruction.operandCount(); ++Index) {
+      const Register *Source = Instruction.operandAt(Index)->getIf<Register>();
+      if (Source == nullptr)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "G_MERGE_VALUES requires register sources");
+      auto ActualSourceType = MRI.getType(*Source);
+      if (!ActualSourceType)
+        return std::unexpected(ActualSourceType.error());
+      if (*ActualSourceType != *SourceType || ActualSourceType->minimumBitWidth() != PartSize)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "G_MERGE_VALUES source types are inconsistent");
+
+      auto ExtendedInput = MRI.createVirtualRegister(WideType);
+      auto ShiftAmount = MRI.createVirtualRegister(WideType);
+      auto ShiftedInput = MRI.createVirtualRegister(WideType);
+      if (!ExtendedInput)
+        return std::unexpected(ExtendedInput.error());
+      if (!ShiftAmount)
+        return std::unexpected(ShiftAmount.error());
+      if (!ShiftedInput)
+        return std::unexpected(ShiftedInput.error());
+      if (auto Built = MIRBuilder.buildZExt(*ExtendedInput, *Source); !Built)
+        return std::unexpected(Built.error());
+      if (auto Built = MIRBuilder.buildConstant(*ShiftAmount,
+                                                static_cast<std::int64_t>((Index - 1U) * PartSize));
+          !Built)
+        return std::unexpected(Built.error());
+      if (auto Built = MIRBuilder.buildShl(*ShiftedInput, *ExtendedInput, *ShiftAmount); !Built)
+        return std::unexpected(Built.error());
+
+      Register NextResult = *Destination;
+      if (Index + 1U != Instruction.operandCount() || WideType != *DestinationType) {
+        auto NewResult = MRI.createVirtualRegister(WideType);
+        if (!NewResult)
+          return std::unexpected(NewResult.error());
+        NextResult = *NewResult;
+      }
+      if (auto Built = MIRBuilder.buildOr(NextResult, ResultRegister, *ShiftedInput); !Built)
+        return std::unexpected(Built.error());
+      ResultRegister = NextResult;
+    }
+
+    if (WideSize > DestinationSize) {
+      if (auto Built = MIRBuilder.buildTrunc(*Destination, ResultRegister); !Built)
+        return std::unexpected(Built.error());
+    } else if (DestinationType->isPointer()) {
+      if (auto Built = MIRBuilder.buildIntToPtr(*Destination, ResultRegister); !Built)
+        return std::unexpected(Built.error());
+    }
+
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError,
+                            "G_MERGE_VALUES became detached during widening");
+    return Block->removeInstruction(Instruction);
+  }
+
+  auto GCDType = LowLevelType::makeCategoryNeutralScalar(std::gcd(SourceSize, WideSize));
+  auto WideDestinationType = LowLevelType::makeCategoryNeutralScalar(MergeCount * WideSize);
+  if (!GCDType)
+    return std::unexpected(GCDType.error());
+  if (!WideDestinationType)
+    return std::unexpected(WideDestinationType.error());
+
+  std::vector<Register> UnmergedRegisters;
+  for (std::size_t Index = 1; Index != Instruction.operandCount(); ++Index) {
+    const Register *Source = Instruction.operandAt(Index)->getIf<Register>();
+    if (Source == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "G_MERGE_VALUES requires register sources");
+    if (GCDType->minimumBitWidth() == SourceSize) {
+      UnmergedRegisters.push_back(*Source);
+      continue;
+    }
+    auto Extracted = extractGCDType(UnmergedRegisters, *GCDType, *Source);
+    if (!Extracted)
+      return std::unexpected(Extracted.error());
+  }
+
+  const std::uint64_t RequiredPartCount = MergeCount * WideSize;
+  if (UnmergedRegisters.size() != RequiredPartCount) {
+    auto UndefRegister = MRI.createVirtualRegister(*GCDType);
+    if (!UndefRegister)
+      return std::unexpected(UndefRegister.error());
+    if (auto Built = MIRBuilder.buildUndef(*UndefRegister); !Built)
+      return std::unexpected(Built.error());
+    while (UnmergedRegisters.size() != RequiredPartCount)
+      UnmergedRegisters.push_back(*UndefRegister);
+  }
+
+  const std::size_t PartsPerGCD = static_cast<std::size_t>(WideSize / GCDType->minimumBitWidth());
+  std::vector<Register> NewMergeRegisters;
+  NewMergeRegisters.reserve(static_cast<std::size_t>(MergeCount));
+  for (std::size_t Index = 0; Index != MergeCount; ++Index) {
+    std::vector<Register> Parts(
+        UnmergedRegisters.begin() + static_cast<std::ptrdiff_t>(Index * PartsPerGCD),
+        UnmergedRegisters.begin() + static_cast<std::ptrdiff_t>((Index + 1U) * PartsPerGCD));
+    auto MergeRegister = MRI.createVirtualRegister(WideType);
+    if (!MergeRegister)
+      return std::unexpected(MergeRegister.error());
+    if (auto Built = MIRBuilder.buildMergeLikeInstr(*MergeRegister, Parts); !Built)
+      return std::unexpected(Built.error());
+    NewMergeRegisters.push_back(*MergeRegister);
+  }
+
+  if (DestinationSize == WideDestinationType->minimumBitWidth()) {
+    if (auto Built = MIRBuilder.buildMergeLikeInstr(*Destination, NewMergeRegisters); !Built)
+      return std::unexpected(Built.error());
+  } else {
+    auto FinalMerge = MRI.createVirtualRegister(*WideDestinationType);
+    if (!FinalMerge)
+      return std::unexpected(FinalMerge.error());
+    if (auto Built = MIRBuilder.buildMergeLikeInstr(*FinalMerge, NewMergeRegisters); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildTrunc(*Destination, *FinalMerge); !Built)
+      return std::unexpected(Built.error());
+  }
+
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "G_MERGE_VALUES became detached during widening");
+  return Block->removeInstruction(Instruction);
+}
+
+Expected<void> LegalizerHelper::widenScalarUnmergeValues(MachineInstr &Instruction,
+                                                         std::size_t TypeIndex,
+                                                         LowLevelType WideType) {
+  if (TypeIndex != 0)
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "G_UNMERGE_VALUES widening requires type index zero");
+  if (Instruction.operandCount() < 2)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "G_UNMERGE_VALUES requires destinations and a source");
+
+  const std::size_t DestinationCount = Instruction.operandCount() - 1U;
+  const Register *Source = Instruction.operandAt(DestinationCount)->getIf<Register>();
+  const Register *FirstDestination = Instruction.operandAt(0)->getIf<Register>();
+  if (Source == nullptr || FirstDestination == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "G_UNMERGE_VALUES requires register operands");
+  auto SourceType = MRI.getType(*Source);
+  auto DestinationType = MRI.getType(*FirstDestination);
+  if (!SourceType)
+    return std::unexpected(SourceType.error());
+  if (!DestinationType)
+    return std::unexpected(DestinationType.error());
+  if (SourceType->isVector() || !DestinationType->isCategoryNeutralScalar())
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "G_UNMERGE_VALUES widening requires scalar types");
+
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+
+  Register SourceRegister = *Source;
+  if (WideType.minimumBitWidth() >= SourceType->minimumBitWidth()) {
+    if (SourceType->isPointer()) {
+      auto IntegerSourceType =
+          LowLevelType::makeCategoryNeutralScalar(SourceType->minimumBitWidth());
+      if (!IntegerSourceType)
+        return std::unexpected(IntegerSourceType.error());
+      auto IntegerSource = MRI.createVirtualRegister(*IntegerSourceType);
+      if (!IntegerSource)
+        return std::unexpected(IntegerSource.error());
+      if (auto Built = MIRBuilder.buildPtrToInt(*IntegerSource, SourceRegister); !Built)
+        return std::unexpected(Built.error());
+      *SourceType = *IntegerSourceType;
+      SourceRegister = *IntegerSource;
+    }
+
+    if (WideType.minimumBitWidth() > SourceType->minimumBitWidth()) {
+      auto WideSource = MRI.createVirtualRegister(WideType);
+      if (!WideSource)
+        return std::unexpected(WideSource.error());
+      if (auto Built = MIRBuilder.buildAnyExt(*WideSource, SourceRegister); !Built)
+        return std::unexpected(Built.error());
+      *SourceType = WideType;
+      SourceRegister = *WideSource;
+    }
+
+    const std::uint64_t DestinationSize = DestinationType->minimumBitWidth();
+    if (auto Built = MIRBuilder.buildTrunc(*FirstDestination, SourceRegister); !Built)
+      return std::unexpected(Built.error());
+    for (std::size_t Index = 1; Index != DestinationCount; ++Index) {
+      const Register *Destination = Instruction.operandAt(Index)->getIf<Register>();
+      if (Destination == nullptr)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "G_UNMERGE_VALUES requires register destinations");
+      auto ShiftAmount = MRI.createVirtualRegister(*SourceType);
+      auto ShiftedSource = MRI.createVirtualRegister(*SourceType);
+      if (!ShiftAmount)
+        return std::unexpected(ShiftAmount.error());
+      if (!ShiftedSource)
+        return std::unexpected(ShiftedSource.error());
+      if (auto Built = MIRBuilder.buildConstant(*ShiftAmount,
+                                                static_cast<std::int64_t>(DestinationSize * Index));
+          !Built)
+        return std::unexpected(Built.error());
+      if (auto Built = MIRBuilder.buildLShr(*ShiftedSource, SourceRegister, *ShiftAmount); !Built)
+        return std::unexpected(Built.error());
+      if (auto Built = MIRBuilder.buildTrunc(*Destination, *ShiftedSource); !Built)
+        return std::unexpected(Built.error());
+    }
+
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError,
+                            "G_UNMERGE_VALUES became detached during widening");
+    return Block->removeInstruction(Instruction);
+  }
+
+  auto LCMType = getLCMType(*SourceType, WideType);
+  if (!LCMType)
+    return std::unexpected(LCMType.error());
+  Register WideSource = SourceRegister;
+  if (LCMType->minimumBitWidth() != SourceType->minimumBitWidth()) {
+    if (SourceType->isPointer())
+      return makeUnexpected(ErrorCode::Unsupported,
+                            "widening a pointer G_UNMERGE_VALUES source is not implemented");
+    auto ExtendedSource = MRI.createVirtualRegister(*LCMType);
+    if (!ExtendedSource)
+      return std::unexpected(ExtendedSource.error());
+    if (auto Built = MIRBuilder.buildAnyExt(*ExtendedSource, WideSource); !Built)
+      return std::unexpected(Built.error());
+    WideSource = *ExtendedSource;
+  }
+
+  const std::size_t UnmergeCount =
+      static_cast<std::size_t>(LCMType->minimumBitWidth() / WideType.minimumBitWidth());
+  std::vector<Register> UnmergeRegisters;
+  UnmergeRegisters.reserve(UnmergeCount);
+  for (std::size_t Index = 0; Index != UnmergeCount; ++Index) {
+    auto Part = MRI.createVirtualRegister(WideType);
+    if (!Part)
+      return std::unexpected(Part.error());
+    UnmergeRegisters.push_back(*Part);
+  }
+  if (auto Built = MIRBuilder.buildUnmergeValues(UnmergeRegisters, WideSource); !Built)
+    return std::unexpected(Built.error());
+
+  auto GCDType = getGCDType(WideType, *DestinationType);
+  if (!GCDType)
+    return std::unexpected(GCDType.error());
+  const std::size_t PartsPerRemerge =
+      static_cast<std::size_t>(DestinationType->minimumBitWidth() / GCDType->minimumBitWidth());
+
+  if (PartsPerRemerge == 1) {
+    const std::size_t PartsPerUnmerge =
+        static_cast<std::size_t>(WideType.minimumBitWidth() / DestinationType->minimumBitWidth());
+    for (std::size_t Index = 0; Index != UnmergeRegisters.size(); ++Index) {
+      std::vector<Register> Destinations;
+      Destinations.reserve(PartsPerUnmerge);
+      for (std::size_t PartIndex = 0; PartIndex != PartsPerUnmerge; ++PartIndex) {
+        const std::size_t DestinationIndex = Index * PartsPerUnmerge + PartIndex;
+        if (DestinationIndex < DestinationCount) {
+          const Register *Destination = Instruction.operandAt(DestinationIndex)->getIf<Register>();
+          if (Destination == nullptr)
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "G_UNMERGE_VALUES requires register destinations");
+          Destinations.push_back(*Destination);
+        } else {
+          auto DeadDestination = MRI.createVirtualRegister(*DestinationType);
+          if (!DeadDestination)
+            return std::unexpected(DeadDestination.error());
+          Destinations.push_back(*DeadDestination);
+        }
+      }
+      if (auto Built = MIRBuilder.buildUnmergeValues(Destinations, UnmergeRegisters[Index]); !Built)
+        return std::unexpected(Built.error());
+    }
+  } else {
+    std::vector<Register> Parts;
+    for (Register UnmergeRegister : UnmergeRegisters) {
+      auto Extracted = extractGCDType(Parts, *GCDType, UnmergeRegister);
+      if (!Extracted)
+        return std::unexpected(Extracted.error());
+    }
+    for (std::size_t Index = 0; Index != DestinationCount; ++Index) {
+      const Register *Destination = Instruction.operandAt(Index)->getIf<Register>();
+      if (Destination == nullptr)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "G_UNMERGE_VALUES requires register destinations");
+      std::vector<Register> RemergeParts(
+          Parts.begin() + static_cast<std::ptrdiff_t>(Index * PartsPerRemerge),
+          Parts.begin() + static_cast<std::ptrdiff_t>((Index + 1U) * PartsPerRemerge));
+      if (auto Built = MIRBuilder.buildMergeLikeInstr(*Destination, RemergeParts); !Built)
+        return std::unexpected(Built.error());
+    }
+  }
+
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "G_UNMERGE_VALUES became detached during widening");
+  return Block->removeInstruction(Instruction);
+}
+
+Expected<void> LegalizerHelper::insertParts(Register Destination, LowLevelType ResultType,
+                                            LowLevelType PartType,
+                                            const std::vector<Register> &PartRegisters,
+                                            LowLevelType LeftoverType,
+                                            const std::vector<Register> &LeftoverRegisters) {
+  if (!LeftoverType.isValid()) {
+    if (!LeftoverRegisters.empty())
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "leftover registers require a leftover type");
+    return MIRBuilder.buildMergeLikeInstr(Destination, PartRegisters).transform([](MachineInstr *) {
+    });
+  }
+
+  if (ResultType.isVector()) {
+    if (LeftoverRegisters.size() != 1)
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "mixed subvector merge requires one leftover register");
+    std::vector<Register> AllRegisters = PartRegisters;
+    AllRegisters.insert(AllRegisters.end(), LeftoverRegisters.begin(), LeftoverRegisters.end());
+    return MIRBuilder.buildMergeLikeInstr(Destination, AllRegisters).transform([](MachineInstr *) {
+    });
+  }
+
+  std::vector<Register> GCDRegisters;
+  auto FirstGCD = getGCDType(ResultType, LeftoverType);
+  if (!FirstGCD)
+    return std::unexpected(FirstGCD.error());
+  auto GCDType = getGCDType(*FirstGCD, PartType);
+  if (!GCDType)
+    return std::unexpected(GCDType.error());
+  for (Register Part : PartRegisters) {
+    auto Extracted = extractGCDType(GCDRegisters, *GCDType, Part);
+    if (!Extracted)
+      return std::unexpected(Extracted.error());
+  }
+  for (Register Part : LeftoverRegisters) {
+    auto Extracted = extractGCDType(GCDRegisters, *GCDType, Part);
+    if (!Extracted)
+      return std::unexpected(Extracted.error());
+  }
+  auto LCMType = buildLCMMergePieces(ResultType, LeftoverType, *GCDType, GCDRegisters);
+  if (!LCMType)
+    return std::unexpected(LCMType.error());
+  return buildWidenedRemergeToDst(Destination, *LCMType, GCDRegisters);
+}
+
+Expected<void> LegalizerHelper::extractGCDType(std::vector<Register> &Parts, LowLevelType GCDType,
+                                               Register Source) {
+  auto SourceType = MRI.getType(Source);
+  if (!SourceType)
+    return std::unexpected(SourceType.error());
+  if (*SourceType == GCDType) {
+    Parts.push_back(Source);
+    return {};
+  }
+  const std::uint64_t SourceSize = SourceType->minimumBitWidth();
+  const std::uint64_t GCDSize = GCDType.minimumBitWidth();
+  if (GCDSize == 0 || SourceSize % GCDSize != 0)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "GCD type does not evenly divide the source type");
+  return extractParts(Source, GCDType, static_cast<int>(SourceSize / GCDSize), Parts, MIRBuilder,
+                      MRI);
+}
+
+Expected<LowLevelType> LegalizerHelper::extractGCDType(std::vector<Register> &Parts,
+                                                       LowLevelType DestinationType,
+                                                       LowLevelType NarrowType, Register Source) {
+  auto SourceType = MRI.getType(Source);
+  if (!SourceType)
+    return std::unexpected(SourceType.error());
+  auto FirstGCD = getGCDType(*SourceType, NarrowType);
+  if (!FirstGCD)
+    return std::unexpected(FirstGCD.error());
+  auto GCDType = getGCDType(*FirstGCD, DestinationType);
+  if (!GCDType)
+    return std::unexpected(GCDType.error());
+  auto Extracted = extractGCDType(Parts, *GCDType, Source);
+  if (!Extracted)
+    return std::unexpected(Extracted.error());
+  return *GCDType;
+}
+
+Expected<LowLevelType> LegalizerHelper::buildLCMMergePieces(LowLevelType DestinationType,
+                                                            LowLevelType NarrowType,
+                                                            LowLevelType GCDType,
+                                                            std::vector<Register> &Registers,
+                                                            GenericOpcode PadStrategy) {
+  auto LCMType = getLCMType(DestinationType, NarrowType);
+  if (!LCMType)
+    return std::unexpected(LCMType.error());
+  const int PartCount = static_cast<int>(LCMType->minimumBitWidth() / NarrowType.minimumBitWidth());
+  const int SubPartCount =
+      static_cast<int>(NarrowType.minimumBitWidth() / GCDType.minimumBitWidth());
+  const int OriginalSourceCount = static_cast<int>(Registers.size());
+
+  Register PadRegister;
+  if (OriginalSourceCount < PartCount * SubPartCount) {
+    auto NewPad = MRI.createVirtualRegister(GCDType);
+    if (!NewPad)
+      return std::unexpected(NewPad.error());
+    PadRegister = *NewPad;
+    Expected<MachineInstr *> Built = PadStrategy == GenericOpcode::G_ZEXT
+                                         ? MIRBuilder.buildConstant(PadRegister, 0)
+                                         : MIRBuilder.buildUndef(PadRegister);
+    if (!Built)
+      return std::unexpected(Built.error());
+  }
+
+  std::vector<Register> Remerge(static_cast<std::size_t>(PartCount));
+  std::vector<Register> SubMerge(static_cast<std::size_t>(SubPartCount));
+  Register AllPadRegister;
+  for (int PartIndex = 0; PartIndex != PartCount; ++PartIndex) {
+    bool AllMergePartsArePadding = true;
+    for (int SubPartIndex = 0; SubPartIndex != SubPartCount; ++SubPartIndex) {
+      const int Index = PartIndex * SubPartCount + SubPartIndex;
+      if (Index >= OriginalSourceCount) {
+        SubMerge[static_cast<std::size_t>(SubPartIndex)] = PadRegister;
+        continue;
+      }
+      SubMerge[static_cast<std::size_t>(SubPartIndex)] = Registers[static_cast<std::size_t>(Index)];
+      AllMergePartsArePadding = false;
+    }
+
+    if (AllMergePartsArePadding && AllPadRegister.isNoRegister()) {
+      auto Pad = MRI.createVirtualRegister(NarrowType);
+      if (!Pad)
+        return std::unexpected(Pad.error());
+      AllPadRegister = *Pad;
+      Expected<MachineInstr *> Built = PadStrategy == GenericOpcode::G_ZEXT
+                                           ? MIRBuilder.buildConstant(AllPadRegister, 0)
+                                           : MIRBuilder.buildUndef(AllPadRegister);
+      if (!Built)
+        return std::unexpected(Built.error());
+    }
+    if (!AllPadRegister.isNoRegister()) {
+      Remerge[static_cast<std::size_t>(PartIndex)] = AllPadRegister;
+      continue;
+    }
+    if (SubPartCount == 1) {
+      Remerge[static_cast<std::size_t>(PartIndex)] = SubMerge.front();
+    } else {
+      auto RemergeRegister = MRI.createVirtualRegister(NarrowType);
+      if (!RemergeRegister)
+        return std::unexpected(RemergeRegister.error());
+      auto Built = MIRBuilder.buildMergeLikeInstr(*RemergeRegister, SubMerge);
+      if (!Built)
+        return std::unexpected(Built.error());
+      Remerge[static_cast<std::size_t>(PartIndex)] = *RemergeRegister;
+    }
+    if (AllMergePartsArePadding && AllPadRegister.isNoRegister())
+      AllPadRegister = Remerge[static_cast<std::size_t>(PartIndex)];
+  }
+  Registers = std::move(Remerge);
+  return *LCMType;
+}
+
+Expected<void>
+LegalizerHelper::buildWidenedRemergeToDst(Register Destination, LowLevelType LCMType,
+                                          const std::vector<Register> &RemergeRegisters) {
+  auto DestinationType = MRI.getType(Destination);
+  if (!DestinationType)
+    return std::unexpected(DestinationType.error());
+  if (*DestinationType == LCMType)
+    return MIRBuilder.buildMergeLikeInstr(Destination, RemergeRegisters)
+        .transform([](MachineInstr *) {});
+
+  auto Remerge = MRI.createVirtualRegister(LCMType);
+  if (!Remerge)
+    return std::unexpected(Remerge.error());
+  auto BuiltMerge = MIRBuilder.buildMergeLikeInstr(*Remerge, RemergeRegisters);
+  if (!BuiltMerge)
+    return std::unexpected(BuiltMerge.error());
+  if (!DestinationType->isVector() && !LCMType.isVector())
+    return MIRBuilder.buildTrunc(Destination, *Remerge).transform([](MachineInstr *) {});
+
+  if (LCMType.isVector()) {
+    const std::size_t DefinitionCount =
+        static_cast<std::size_t>(LCMType.minimumBitWidth() / DestinationType->minimumBitWidth());
+    std::vector<Register> Definitions;
+    Definitions.reserve(DefinitionCount);
+    Definitions.push_back(Destination);
+    for (std::size_t Index = 1; Index != DefinitionCount; ++Index) {
+      auto Definition = MRI.createVirtualRegister(*DestinationType);
+      if (!Definition)
+        return std::unexpected(Definition.error());
+      Definitions.push_back(*Definition);
+    }
+    return MIRBuilder.buildUnmergeValues(Definitions, *Remerge).transform([](MachineInstr *) {});
+  }
+  return makeUnexpected(ErrorCode::Unsupported,
+                        "widened remerge has an unsupported type combination");
+}
+
 Expected<void> LegalizerHelper::widenScalarSrc(MachineInstr &Instruction, LowLevelType WideType,
                                                std::size_t OperandIndex,
                                                GenericOpcode ExtensionOpcode) {
@@ -192,6 +728,10 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
 
   Observer.changingInstr(Instruction);
   switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
+  case GenericOpcode::G_MERGE_VALUES:
+    return widenScalarMergeValues(Instruction, TypeIndex, WideType);
+  case GenericOpcode::G_UNMERGE_VALUES:
+    return widenScalarUnmergeValues(Instruction, TypeIndex, WideType);
   case GenericOpcode::G_ATOMICRMW_XCHG:
   case GenericOpcode::G_ATOMICRMW_ADD:
   case GenericOpcode::G_ATOMICRMW_SUB:
@@ -408,6 +948,232 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size
   return {};
 }
 
+Expected<void> LegalizerHelper::narrowScalarAddSub(MachineInstr &Instruction, std::size_t TypeIndex,
+                                                   LowLevelType NarrowType) {
+  if (TypeIndex != 0)
+    return makeUnexpected(ErrorCode::Unsupported, "add/sub narrowing requires type index zero");
+
+  const MachineOperand *DestinationOperand = Instruction.operandAt(0);
+  const Register *Destination =
+      DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+  if (Destination == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "add/sub narrowing requires a register destination");
+  auto DestinationType = MRI.getType(*Destination);
+  if (!DestinationType)
+    return std::unexpected(DestinationType.error());
+  if (DestinationType->isVector())
+    return makeUnexpected(ErrorCode::Unsupported, "vector add/sub narrowing is not implemented");
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+
+  GenericOpcode FirstOpcode;
+  GenericOpcode MiddleOpcode;
+  GenericOpcode FinalOpcode;
+  switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
+  case GenericOpcode::G_SADDO:
+  case GenericOpcode::G_SADDE:
+  case GenericOpcode::G_UADDO:
+  case GenericOpcode::G_UADDE:
+  case GenericOpcode::G_ADD:
+    FirstOpcode = GenericOpcode::G_UADDO;
+    MiddleOpcode = GenericOpcode::G_UADDE;
+    FinalOpcode = Instruction.opcode() == opcode(GenericOpcode::G_SADDO) ||
+                          Instruction.opcode() == opcode(GenericOpcode::G_SADDE)
+                      ? GenericOpcode::G_SADDE
+                      : GenericOpcode::G_UADDE;
+    break;
+  case GenericOpcode::G_SSUBO:
+  case GenericOpcode::G_SSUBE:
+  case GenericOpcode::G_USUBO:
+  case GenericOpcode::G_USUBE:
+  case GenericOpcode::G_SUB:
+    FirstOpcode = GenericOpcode::G_USUBO;
+    MiddleOpcode = GenericOpcode::G_USUBE;
+    FinalOpcode = Instruction.opcode() == opcode(GenericOpcode::G_SSUBO) ||
+                          Instruction.opcode() == opcode(GenericOpcode::G_SSUBE)
+                      ? GenericOpcode::G_SSUBE
+                      : GenericOpcode::G_USUBE;
+    break;
+  default:
+    return makeUnexpected(ErrorCode::InternalError,
+                          "unexpected add/sub opcode during scalar narrowing");
+  }
+
+  const InstructionDescriptor *Descriptor =
+      MIRBuilder.target().instructionDescriptor(Instruction.opcode());
+  if (Descriptor == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "add/sub narrowing has no instruction descriptor");
+  const std::size_t DefinitionCount = Descriptor->NumExplicitDefs;
+  const MachineOperand *FirstSourceOperand = Instruction.operandAt(DefinitionCount);
+  const MachineOperand *SecondSourceOperand = Instruction.operandAt(DefinitionCount + 1);
+  const Register *FirstSource =
+      FirstSourceOperand == nullptr ? nullptr : FirstSourceOperand->getIf<Register>();
+  const Register *SecondSource =
+      SecondSourceOperand == nullptr ? nullptr : SecondSourceOperand->getIf<Register>();
+  if (FirstSource == nullptr || SecondSource == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "add/sub narrowing requires two register sources");
+
+  Register CarryDestination;
+  Register CarryIn;
+  if (DefinitionCount == 2) {
+    const MachineOperand *CarryOperand = Instruction.operandAt(1);
+    const Register *Carry = CarryOperand == nullptr ? nullptr : CarryOperand->getIf<Register>();
+    if (Carry == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "add/sub narrowing has an invalid carry destination");
+    CarryDestination = *Carry;
+  }
+  if (Instruction.operandCount() == DefinitionCount + 3) {
+    const MachineOperand *CarryOperand = Instruction.operandAt(DefinitionCount + 2);
+    const Register *Carry = CarryOperand == nullptr ? nullptr : CarryOperand->getIf<Register>();
+    if (Carry == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "add/sub narrowing has an invalid carry input");
+    CarryIn = *Carry;
+  }
+
+  LowLevelType LeftoverType;
+  LowLevelType DummyType;
+  std::vector<Register> FirstParts;
+  std::vector<Register> SecondParts;
+  std::vector<Register> FirstLeftovers;
+  std::vector<Register> SecondLeftovers;
+  std::vector<Register> DestinationParts;
+  auto FirstExtracted = extractParts(*FirstSource, *DestinationType, NarrowType, LeftoverType,
+                                     FirstParts, FirstLeftovers, MIRBuilder, MRI);
+  if (!FirstExtracted)
+    return std::unexpected(FirstExtracted.error());
+  auto SecondExtracted = extractParts(*SecondSource, *DestinationType, NarrowType, DummyType,
+                                      SecondParts, SecondLeftovers, MIRBuilder, MRI);
+  if (!SecondExtracted)
+    return std::unexpected(SecondExtracted.error());
+
+  const std::size_t NarrowPartCount = FirstParts.size();
+  FirstParts.insert(FirstParts.end(), FirstLeftovers.begin(), FirstLeftovers.end());
+  SecondParts.insert(SecondParts.end(), SecondLeftovers.begin(), SecondLeftovers.end());
+  if (FirstParts.size() != SecondParts.size())
+    return makeUnexpected(ErrorCode::InternalError,
+                          "add/sub source splits have different part counts");
+  DestinationParts.reserve(FirstParts.size());
+
+  auto BooleanType = LowLevelType::makeCategoryNeutralScalar(1);
+  if (!BooleanType)
+    return std::unexpected(BooleanType.error());
+  for (std::size_t Index = 0; Index != FirstParts.size(); ++Index) {
+    auto PartType = MRI.getType(FirstParts[Index]);
+    if (!PartType)
+      return std::unexpected(PartType.error());
+    auto PartDestination = MRI.createVirtualRegister(*PartType);
+    if (!PartDestination)
+      return std::unexpected(PartDestination.error());
+
+    Register CarryOut;
+    if (Index + 1 == FirstParts.size() && !CarryDestination.isNoRegister()) {
+      CarryOut = CarryDestination;
+    } else {
+      auto NewCarry = MRI.createVirtualRegister(*BooleanType);
+      if (!NewCarry)
+        return std::unexpected(NewCarry.error());
+      CarryOut = *NewCarry;
+    }
+
+    Expected<MachineInstr *> Built;
+    if (CarryIn.isNoRegister()) {
+      Built = MIRBuilder.buildInstr(opcode(FirstOpcode), {*PartDestination, CarryOut},
+                                    {FirstParts[Index], SecondParts[Index]});
+    } else if (Index + 1 == FirstParts.size()) {
+      Built = MIRBuilder.buildInstr(opcode(FinalOpcode), {*PartDestination, CarryOut},
+                                    {FirstParts[Index], SecondParts[Index], CarryIn});
+    } else {
+      Built = MIRBuilder.buildInstr(opcode(MiddleOpcode), {*PartDestination, CarryOut},
+                                    {FirstParts[Index], SecondParts[Index], CarryIn});
+    }
+    if (!Built)
+      return std::unexpected(Built.error());
+    DestinationParts.push_back(*PartDestination);
+    CarryIn = CarryOut;
+  }
+
+  std::vector<Register> MainDestinations(DestinationParts.begin(),
+                                         DestinationParts.begin() +
+                                             static_cast<std::ptrdiff_t>(NarrowPartCount));
+  std::vector<Register> LeftoverDestinations(DestinationParts.begin() +
+                                                 static_cast<std::ptrdiff_t>(NarrowPartCount),
+                                             DestinationParts.end());
+  auto Inserted = insertParts(*Destination, *DestinationType, NarrowType, MainDestinations,
+                              LeftoverType, LeftoverDestinations);
+  if (!Inserted)
+    return std::unexpected(Inserted.error());
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "add/sub instruction became detached during narrowing");
+  return Block->removeInstruction(Instruction);
+}
+
+Expected<void> LegalizerHelper::narrowScalarExt(MachineInstr &Instruction, std::size_t TypeIndex,
+                                                LowLevelType NarrowType) {
+  if (TypeIndex != 0)
+    return makeUnexpected(ErrorCode::Unsupported, "extension narrowing requires type index zero");
+
+  const auto Destination = Instruction.operandAt(0)->registerValue();
+  const auto Source = Instruction.operandAt(1)->registerValue();
+  if (!Destination || !Source)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "extension narrowing requires register operands");
+
+  auto DestinationType = MRI.getType(*Destination);
+  if (!DestinationType)
+    return std::unexpected(DestinationType.error());
+  if (DestinationType->isVector())
+    return makeUnexpected(ErrorCode::Unsupported, "vector extension narrowing is not implemented");
+
+  std::vector<Register> Parts;
+  auto GCDType = extractGCDType(Parts, *DestinationType, NarrowType, *Source);
+  if (!GCDType)
+    return std::unexpected(GCDType.error());
+  auto LCMType = buildLCMMergePieces(*DestinationType, NarrowType, *GCDType, Parts,
+                                     static_cast<GenericOpcode>(Instruction.opcode().value()));
+  if (!LCMType)
+    return std::unexpected(LCMType.error());
+  auto Remerged = buildWidenedRemergeToDst(*Destination, *LCMType, Parts);
+  if (!Remerged)
+    return std::unexpected(Remerged.error());
+
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "extension instruction became detached during narrowing");
+  return Block->removeInstruction(Instruction);
+}
+
+Expected<void> LegalizerHelper::narrowScalar(MachineInstr &Instruction, std::size_t TypeIndex,
+                                             LowLevelType NarrowType) {
+  switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
+  case GenericOpcode::G_ADD:
+  case GenericOpcode::G_SUB:
+  case GenericOpcode::G_SADDO:
+  case GenericOpcode::G_SSUBO:
+  case GenericOpcode::G_SADDE:
+  case GenericOpcode::G_SSUBE:
+  case GenericOpcode::G_UADDO:
+  case GenericOpcode::G_USUBO:
+  case GenericOpcode::G_UADDE:
+  case GenericOpcode::G_USUBE:
+    return narrowScalarAddSub(Instruction, TypeIndex, NarrowType);
+  case GenericOpcode::G_SEXT:
+  case GenericOpcode::G_ZEXT:
+  case GenericOpcode::G_ANYEXT:
+    return narrowScalarExt(Instruction, TypeIndex, NarrowType);
+  default:
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "scalar narrowing is not implemented for this opcode");
+  }
+}
+
 Expected<void> LegalizerHelper::lowerVAArg(MachineInstr &Instruction) {
   if (Instruction.opcode() != opcode(GenericOpcode::G_VAARG) || Instruction.operandCount() != 3 ||
       !Instruction.memOperands().empty()) {
@@ -550,6 +1316,166 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
   switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
   case GenericOpcode::G_VAARG:
     return lowerVAArg(Instruction);
+  case GenericOpcode::G_UADDO: {
+    const Register Result = *Instruction.operandAt(0)->getIf<Register>();
+    const Register CarryOut = *Instruction.operandAt(1)->getIf<Register>();
+    const Register Left = *Instruction.operandAt(2)->getIf<Register>();
+    const Register Right = *Instruction.operandAt(3)->getIf<Register>();
+    auto NewResult = MRI.cloneVirtualRegister(Result);
+    if (!NewResult)
+      return std::unexpected(NewResult.error());
+    if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+      return std::unexpected(Point.error());
+    if (auto Built = MIRBuilder.buildAdd(*NewResult, Left, Right); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built =
+            MIRBuilder.buildICmp(IntegerPredicate::UnsignedLessThan, CarryOut, *NewResult, Right);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildCopy(Result, *NewResult); !Built)
+      return std::unexpected(Built.error());
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "G_UADDO became detached during lowering");
+    return Block->removeInstruction(Instruction);
+  }
+  case GenericOpcode::G_UADDE: {
+    const Register Result = *Instruction.operandAt(0)->getIf<Register>();
+    const Register CarryOut = *Instruction.operandAt(1)->getIf<Register>();
+    const Register Left = *Instruction.operandAt(2)->getIf<Register>();
+    const Register Right = *Instruction.operandAt(3)->getIf<Register>();
+    const Register CarryIn = *Instruction.operandAt(4)->getIf<Register>();
+    auto ResultType = MRI.getType(Result);
+    auto ConditionType = MRI.getType(CarryOut);
+    if (!ResultType)
+      return std::unexpected(ResultType.error());
+    if (!ConditionType)
+      return std::unexpected(ConditionType.error());
+    auto NewResult = MRI.cloneVirtualRegister(Result);
+    auto TemporaryResult = MRI.createVirtualRegister(*ResultType);
+    auto Carry = MRI.createVirtualRegister(*ConditionType);
+    auto ExtendedCarryIn = MRI.createVirtualRegister(*ResultType);
+    auto Zero = MRI.createVirtualRegister(*ResultType);
+    auto ResultIsZero = MRI.createVirtualRegister(*ConditionType);
+    auto SecondCarry = MRI.createVirtualRegister(*ConditionType);
+    if (!NewResult)
+      return std::unexpected(NewResult.error());
+    if (!TemporaryResult)
+      return std::unexpected(TemporaryResult.error());
+    if (!Carry)
+      return std::unexpected(Carry.error());
+    if (!ExtendedCarryIn)
+      return std::unexpected(ExtendedCarryIn.error());
+    if (!Zero)
+      return std::unexpected(Zero.error());
+    if (!ResultIsZero)
+      return std::unexpected(ResultIsZero.error());
+    if (!SecondCarry)
+      return std::unexpected(SecondCarry.error());
+    if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+      return std::unexpected(Point.error());
+    if (auto Built = MIRBuilder.buildAdd(*TemporaryResult, Left, Right); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::UnsignedLessThan, *Carry,
+                                          *TemporaryResult, Left);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildZExt(*ExtendedCarryIn, CarryIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildAdd(*NewResult, *TemporaryResult, *ExtendedCarryIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildConstant(*Zero, 0); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built =
+            MIRBuilder.buildICmp(IntegerPredicate::Equal, *ResultIsZero, *NewResult, *Zero);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildAnd(*SecondCarry, *ResultIsZero, CarryIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildOr(CarryOut, *Carry, *SecondCarry); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildCopy(Result, *NewResult); !Built)
+      return std::unexpected(Built.error());
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "G_UADDE became detached during lowering");
+    return Block->removeInstruction(Instruction);
+  }
+  case GenericOpcode::G_USUBO: {
+    const Register Result = *Instruction.operandAt(0)->getIf<Register>();
+    const Register BorrowOut = *Instruction.operandAt(1)->getIf<Register>();
+    const Register Left = *Instruction.operandAt(2)->getIf<Register>();
+    const Register Right = *Instruction.operandAt(3)->getIf<Register>();
+    if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+      return std::unexpected(Point.error());
+    if (auto Built = MIRBuilder.buildSub(Result, Left, Right); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built =
+            MIRBuilder.buildICmp(IntegerPredicate::UnsignedLessThan, BorrowOut, Left, Right);
+        !Built)
+      return std::unexpected(Built.error());
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "G_USUBO became detached during lowering");
+    return Block->removeInstruction(Instruction);
+  }
+  case GenericOpcode::G_USUBE: {
+    const Register Result = *Instruction.operandAt(0)->getIf<Register>();
+    const Register BorrowOut = *Instruction.operandAt(1)->getIf<Register>();
+    const Register Left = *Instruction.operandAt(2)->getIf<Register>();
+    const Register Right = *Instruction.operandAt(3)->getIf<Register>();
+    const Register BorrowIn = *Instruction.operandAt(4)->getIf<Register>();
+    auto ResultType = MRI.getType(Result);
+    auto ConditionType = MRI.getType(BorrowOut);
+    if (!ResultType)
+      return std::unexpected(ResultType.error());
+    if (!ConditionType)
+      return std::unexpected(ConditionType.error());
+    auto TemporaryResult = MRI.createVirtualRegister(*ResultType);
+    auto Borrow = MRI.createVirtualRegister(*ConditionType);
+    auto ExtendedBorrowIn = MRI.createVirtualRegister(*ResultType);
+    auto Zero = MRI.createVirtualRegister(*ResultType);
+    auto TemporaryResultIsZero = MRI.createVirtualRegister(*ConditionType);
+    auto SecondBorrow = MRI.createVirtualRegister(*ConditionType);
+    if (!TemporaryResult)
+      return std::unexpected(TemporaryResult.error());
+    if (!Borrow)
+      return std::unexpected(Borrow.error());
+    if (!ExtendedBorrowIn)
+      return std::unexpected(ExtendedBorrowIn.error());
+    if (!Zero)
+      return std::unexpected(Zero.error());
+    if (!TemporaryResultIsZero)
+      return std::unexpected(TemporaryResultIsZero.error());
+    if (!SecondBorrow)
+      return std::unexpected(SecondBorrow.error());
+    if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+      return std::unexpected(Point.error());
+    if (auto Built = MIRBuilder.buildSub(*TemporaryResult, Left, Right); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::UnsignedGreaterThan, *Borrow,
+                                          *TemporaryResult, Left);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildZExt(*ExtendedBorrowIn, BorrowIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildSub(Result, *TemporaryResult, *ExtendedBorrowIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildConstant(*Zero, 0); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::Equal, *TemporaryResultIsZero,
+                                          *TemporaryResult, *Zero);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildAnd(*SecondBorrow, *TemporaryResultIsZero, BorrowIn); !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = MIRBuilder.buildOr(BorrowOut, *Borrow, *SecondBorrow); !Built)
+      return std::unexpected(Built.error());
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "G_USUBE became detached during lowering");
+    return Block->removeInstruction(Instruction);
+  }
   default: {
     const InstructionDescriptor *Descriptor =
         MIRBuilder.target().instructionDescriptor(Instruction.opcode());
@@ -564,9 +1490,14 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
 
 Expected<void> LegalizerHelper::legalize(MachineInstr &Instruction,
                                          const LegalizationDecision &Decision) {
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+
   switch (Decision.Action) {
   case LegalizationAction::WidenScalar:
     return widenScalar(Instruction, Decision.TypeIndex, Decision.NewType);
+  case LegalizationAction::NarrowScalar:
+    return narrowScalar(Instruction, Decision.TypeIndex, Decision.NewType);
   case LegalizationAction::Custom:
     return Info.legalizeCustom(*this, Instruction, Decision);
   case LegalizationAction::Lower:
@@ -575,7 +1506,6 @@ Expected<void> LegalizerHelper::legalize(MachineInstr &Instruction,
     return {};
   case LegalizationAction::Unsupported:
   case LegalizationAction::Libcall:
-  case LegalizationAction::NarrowScalar:
   case LegalizationAction::MoreElements:
   case LegalizationAction::FewerElements:
   case LegalizationAction::Bitcast:
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
diff --git a/backend/lib/CodeGen/MachineIRBuilder.cpp b/backend/lib/CodeGen/MachineIRBuilder.cpp
index 9195d1a..d5be3af 100644
--- a/backend/lib/CodeGen/MachineIRBuilder.cpp
+++ b/backend/lib/CodeGen/MachineIRBuilder.cpp
@@ -708,6 +708,23 @@ Expected<MachineInstrBuilder> MachineIRBuilder::buildInstr(Opcode InstructionOpc
   return MachineInstrBuilder(*Function, *Target, *Descriptor, *InsertBlock, InsertBefore);
 }
 
+Expected<MachineInstr *>
+MachineIRBuilder::buildInstr(Opcode InstructionOpcode, std::initializer_list<Register> Destinations,
+                             std::initializer_list<Register> Sources) const {
+  auto Pending = buildInstr(InstructionOpcode);
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  for (Register Destination : Destinations) {
+    if (auto Added = Pending->addDef(Destination); !Added)
+      return std::unexpected(Added.error());
+  }
+  for (Register Source : Sources) {
+    if (auto Added = Pending->addUse(Source); !Added)
+      return std::unexpected(Added.error());
+  }
+  return Pending->build();
+}
+
 Expected<LowLevelType> MachineIRBuilder::registerType(Register Reg) const {
   if (!Reg.isVirtual())
     return makeUnexpected(ErrorCode::InvalidArgument,
@@ -722,8 +739,7 @@ Expected<LowLevelType> MachineIRBuilder::registerType(Register Reg) const {
 }
 
 Expected<MachineInstr *> MachineIRBuilder::buildUnary(Opcode InstructionOpcode,
-                                                      Register Destination,
-                                                      Register Source) const {
+                                                      Register Destination, Register Source) const {
   auto Pending = buildInstr(InstructionOpcode);
   if (!Pending)
     return std::unexpected(Pending.error());
@@ -749,13 +765,11 @@ Expected<MachineInstr *> MachineIRBuilder::buildBinary(Opcode InstructionOpcode,
   return Pending->build();
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildTrunc(Register Destination,
-                                                      Register Source) const {
+Expected<MachineInstr *> MachineIRBuilder::buildTrunc(Register Destination, Register Source) const {
   return buildUnary(opcode(GenericOpcode::G_TRUNC), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildCopy(Register Destination,
-                                                     Register Source) const {
+Expected<MachineInstr *> MachineIRBuilder::buildCopy(Register Destination, Register Source) const {
   return buildUnary(opcode(GenericOpcode::COPY), Destination, Source);
 }
 
@@ -773,16 +787,18 @@ Expected<MachineInstr *> MachineIRBuilder::buildAnyExt(Register Destination,
   return buildUnary(opcode(GenericOpcode::G_ANYEXT), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildZExt(Register Destination,
-                                                     Register Source) const {
+Expected<MachineInstr *> MachineIRBuilder::buildZExt(Register Destination, Register Source) const {
   return buildUnary(opcode(GenericOpcode::G_ZEXT), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildSExt(Register Destination,
-                                                     Register Source) const {
+Expected<MachineInstr *> MachineIRBuilder::buildSExt(Register Destination, Register Source) const {
   return buildUnary(opcode(GenericOpcode::G_SEXT), Destination, Source);
 }
 
+Expected<MachineInstr *> MachineIRBuilder::buildUndef(Register Destination) const {
+  return buildImplicitDef(Destination);
+}
+
 Expected<MachineInstr *> MachineIRBuilder::buildExtOrTrunc(Opcode ExtensionOpcode,
                                                            Register Destination,
                                                            Register Source) const {
@@ -807,12 +823,11 @@ Expected<MachineInstr *> MachineIRBuilder::buildAnyExtOrTrunc(Register Destinati
 }
 
 Expected<MachineInstr *> MachineIRBuilder::buildSExtOrTrunc(Register Destination,
-                                                           Register Source) const {
+                                                            Register Source) const {
   return buildExtOrTrunc(opcode(GenericOpcode::G_SEXT), Destination, Source);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination,
-                                                         APInt Value) const {
+Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination, APInt Value) const {
   auto Pending = buildInstr(opcode(GenericOpcode::G_CONSTANT));
   if (!Pending)
     return std::unexpected(Pending.error());
@@ -834,8 +849,7 @@ Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination,
   return buildConstant(Destination, std::move(*Immediate));
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildSExtInReg(Register Destination,
-                                                          Register Source,
+Expected<MachineInstr *> MachineIRBuilder::buildSExtInReg(Register Destination, Register Source,
                                                           std::uint32_t Width) const {
   auto Pending = buildInstr(opcode(GenericOpcode::G_SEXT_INREG));
   if (!Pending)
@@ -854,8 +868,94 @@ Expected<MachineInstr *> MachineIRBuilder::buildAnd(Register Destination, Regist
   return buildBinary(opcode(GenericOpcode::G_AND), Destination, Left, Right);
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildMergeValues(
-    Register Destination, const std::vector<Register> &Sources) const {
+Expected<MachineInstr *> MachineIRBuilder::buildOr(Register Destination, Register Left,
+                                                   Register Right) const {
+  return buildBinary(opcode(GenericOpcode::G_OR), Destination, Left, Right);
+}
+
+Expected<MachineInstr *> MachineIRBuilder::buildAdd(Register Destination, Register Left,
+                                                    Register Right) const {
+  return buildBinary(opcode(GenericOpcode::G_ADD), Destination, Left, Right);
+}
+
+Expected<MachineInstr *> MachineIRBuilder::buildSub(Register Destination, Register Left,
+                                                    Register Right) const {
+  return buildBinary(opcode(GenericOpcode::G_SUB), Destination, Left, Right);
+}
+
+Expected<MachineInstr *> MachineIRBuilder::buildShl(Register Destination, Register Left,
+                                                    Register Right) const {
+  return buildBinary(opcode(GenericOpcode::G_SHL), Destination, Left, Right);
+}
+
+Expected<MachineInstr *> MachineIRBuilder::buildLShr(Register Destination, Register Left,
+                                                     Register Right) const {
+  return buildBinary(opcode(GenericOpcode::G_LSHR), Destination, Left, Right);
+}
+
+Expected<MachineInstr *> MachineIRBuilder::buildAShr(Register Destination, Register Left,
+                                                     Register Right) const {
+  return buildBinary(opcode(GenericOpcode::G_ASHR), Destination, Left, Right);
+}
+
+Expected<MachineInstr *> MachineIRBuilder::buildPtrToInt(Register Destination,
+                                                         Register Source) const {
+  return buildUnary(opcode(GenericOpcode::G_PTRTOINT), Destination, Source);
+}
+
+Expected<MachineInstr *> MachineIRBuilder::buildIntToPtr(Register Destination,
+                                                         Register Source) const {
+  return buildUnary(opcode(GenericOpcode::G_INTTOPTR), Destination, Source);
+}
+
+Expected<MachineInstr *> MachineIRBuilder::buildICmp(IntegerPredicate Predicate,
+                                                     Register Destination, Register Left,
+                                                     Register Right) const {
+  auto Pending = buildInstr(opcode(GenericOpcode::G_ICMP));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  if (auto Added = Pending->addDef(Destination); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = Pending->addIntegerPredicate(Predicate); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = Pending->addUse(Left); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = Pending->addUse(Right); !Added)
+    return std::unexpected(Added.error());
+  return Pending->build();
+}
+
+Expected<MachineInstr *>
+MachineIRBuilder::buildMergeLikeInstr(Register Destination,
+                                      const std::vector<Register> &Sources) const {
+  auto DestinationType = registerType(Destination);
+  if (!DestinationType)
+    return std::unexpected(DestinationType.error());
+  if (!DestinationType->isVector())
+    return buildMergeValues(Destination, Sources);
+  if (Sources.empty())
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "merge-like instruction requires source registers");
+  auto SourceType = registerType(Sources.front());
+  if (!SourceType)
+    return std::unexpected(SourceType.error());
+  const GenericOpcode MergeOpcode =
+      SourceType->isVector() ? GenericOpcode::G_CONCAT_VECTORS : GenericOpcode::G_BUILD_VECTOR;
+  auto Pending = buildInstr(opcode(MergeOpcode));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  if (auto Added = Pending->addDef(Destination); !Added)
+    return std::unexpected(Added.error());
+  for (Register Source : Sources) {
+    if (auto Added = Pending->addUse(Source); !Added)
+      return std::unexpected(Added.error());
+  }
+  return Pending->build();
+}
+
+Expected<MachineInstr *>
+MachineIRBuilder::buildMergeValues(Register Destination,
+                                   const std::vector<Register> &Sources) const {
   auto Pending = buildInstr(opcode(GenericOpcode::G_MERGE_VALUES));
   if (!Pending)
     return std::unexpected(Pending.error());
@@ -868,8 +968,9 @@ Expected<MachineInstr *> MachineIRBuilder::buildMergeValues(
   return Pending->build();
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildUnmergeValues(
-    const std::vector<Register> &Destinations, Register Source) const {
+Expected<MachineInstr *>
+MachineIRBuilder::buildUnmergeValues(const std::vector<Register> &Destinations,
+                                     Register Source) const {
   auto Pending = buildInstr(opcode(GenericOpcode::G_UNMERGE_VALUES));
   if (!Pending)
     return std::unexpected(Pending.error());
@@ -882,8 +983,7 @@ Expected<MachineInstr *> MachineIRBuilder::buildUnmergeValues(
   return Pending->build();
 }
 
-Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register Destination,
-                                                        Register Source,
+Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register Destination, Register Source,
                                                         std::uint64_t Offset) const {
   if (Offset > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
     return makeUnexpected(ErrorCode::InvalidArgument,
@@ -900,4 +1000,24 @@ Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register Destination,
   return Pending->build();
 }
 
+Expected<MachineInstr *> MachineIRBuilder::buildInsert(Register Destination, Register Source,
+                                                       Register Inserted,
+                                                       std::uint64_t Offset) const {
+  if (Offset > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "generic insert offset does not fit a machine immediate");
+  auto Pending = buildInstr(opcode(GenericOpcode::G_INSERT));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  if (auto Added = Pending->addDef(Destination); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = Pending->addUse(Source); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = Pending->addUse(Inserted); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = Pending->addImmediate(static_cast<std::int64_t>(Offset)); !Added)
+    return std::unexpected(Added.error());
+  return Pending->build();
+}
+
 } // namespace rcc
diff --git a/backend/lib/CodeGen/MachineRegisterInfo.cpp b/backend/lib/CodeGen/MachineRegisterInfo.cpp
index 4627f9e..cc1cbdb 100644
--- a/backend/lib/CodeGen/MachineRegisterInfo.cpp
+++ b/backend/lib/CodeGen/MachineRegisterInfo.cpp
@@ -81,6 +81,20 @@ Expected<Register> MachineRegisterInfo::createVirtualRegister(LowLevelType Type)
   return *Reg;
 }
 
+Expected<Register> MachineRegisterInfo::cloneVirtualRegister(Register Reg) {
+  auto Source = virtualRegisterInfo(Reg);
+  if (!Source)
+    return std::unexpected(Source.error());
+  auto Clone = createVirtualRegister();
+  if (!Clone)
+    return std::unexpected(Clone.error());
+  VirtualRegisters.back() = Source->get();
+  VirtualRegisters.back().Name.reset();
+  VirtualRegisters.back().AllocationHints.clear();
+  VirtualRegisters.back().IsTombstone = false;
+  return *Clone;
+}
+
 Expected<void> MachineRegisterInfo::eraseVirtualRegister(Register Reg) {
   auto Info = virtualRegisterInfo(Reg);
   if (!Info)
@@ -313,8 +327,7 @@ const MachineOperand *MachineRegisterInfo::getUniqueVRegDef(Register Reg) const
 
 MachineInstr *MachineRegisterInfo::getVRegDef(Register Reg) noexcept {
   const MachineOperand *Definition = getUniqueVRegDef(Reg);
-  return Definition == nullptr ? nullptr
-                               : const_cast<MachineInstr *>(Definition->parent());
+  return Definition == nullptr ? nullptr : const_cast<MachineInstr *>(Definition->parent());
 }
 
 const MachineInstr *MachineRegisterInfo::getVRegDef(Register Reg) const noexcept {
@@ -327,8 +340,7 @@ Expected<LowLevelType> MachineRegisterInfo::getType(Register Reg) const {
   if (!Info)
     return std::unexpected(Info.error());
   if (!Info->get().Type)
-    return makeUnexpected(ErrorCode::InvalidArgument,
-                          "virtual register has no LowLevelType");
+    return makeUnexpected(ErrorCode::InvalidArgument, "virtual register has no LowLevelType");
   return *Info->get().Type;
 }
 
diff --git a/backend/lib/CodeGen/TargetDescription.cpp b/backend/lib/CodeGen/TargetDescription.cpp
index b9569be..2a64a02 100644
--- a/backend/lib/CodeGen/TargetDescription.cpp
+++ b/backend/lib/CodeGen/TargetDescription.cpp
@@ -51,7 +51,8 @@ namespace {
 
 Expected<TargetDescription> TargetDescription::create(InstructionSet Instructions,
                                                       TargetRegisterInfo Registers,
-                                                      TargetMIRTextInfoDesc MIRTextDescription) {
+                                                      TargetMIRTextInfoDesc MIRTextDescription,
+                                                      TargetBooleanContentInfo BooleanInfo) {
   auto MIRText = TargetMIRTextInfo::create(std::move(MIRTextDescription), Registers);
   if (!MIRText)
     return std::unexpected(MIRText.error());
@@ -122,7 +123,8 @@ Expected<TargetDescription> TargetDescription::create(InstructionSet Instruction
     }
   }
 
-  return TargetDescription(std::move(Instructions), std::move(Registers), std::move(*MIRText));
+  return TargetDescription(std::move(Instructions), std::move(Registers), std::move(*MIRText),
+                           BooleanInfo);
 }
 
 Expected<void> TargetDescription::validateVirtualRegister(Register Reg,
diff --git a/backend/lib/Support/APInt.cpp b/backend/lib/Support/APInt.cpp
index d54a4c2..74cbc56 100644
--- a/backend/lib/Support/APInt.cpp
+++ b/backend/lib/Support/APInt.cpp
@@ -138,16 +138,13 @@ Expected<APInt> APInt::fromSigned(std::uint32_t BitWidth, std::int64_t Value) {
   return create(BitWidth, Words);
 }
 
-Expected<APInt> APInt::getLowBitsSet(std::uint32_t BitWidth,
-                                     std::uint32_t SetBitCount) {
+Expected<APInt> APInt::getLowBitsSet(std::uint32_t BitWidth, std::uint32_t SetBitCount) {
   if (BitWidth == 0 || BitWidth > MaxBitWidth || SetBitCount > BitWidth)
-    return makeUnexpected(ErrorCode::InvalidArgument,
-                          "APInt low-bit mask has an invalid width");
+    return makeUnexpected(ErrorCode::InvalidArgument, "APInt low-bit mask has an invalid width");
   std::vector<std::uint64_t> Words(wordCount(BitWidth), 0);
   const std::size_t FullWords = SetBitCount / 64U;
-  std::ranges::fill_n(
-      Words.begin(),
-      static_cast<std::vector<std::uint64_t>::difference_type>(FullWords),
+  std::ranges::fill_n(Words.begin(),
+                      static_cast<std::vector<std::uint64_t>::difference_type>(FullWords),
                       std::numeric_limits<std::uint64_t>::max());
   const std::uint32_t RemainingBits = SetBitCount % 64U;
   if (RemainingBits != 0)
@@ -256,20 +253,74 @@ std::size_t APInt::countrZero() const noexcept {
   return Result;
 }
 
+std::size_t APInt::countlOne() const noexcept {
+  std::size_t Result = 0;
+  for (std::size_t Bit = BitWidth; Bit != 0 && testBit(Bit - 1U); --Bit)
+    ++Result;
+  return Result;
+}
+
+bool APInt::isAllOnes() const noexcept {
+  return BitWidth != 0 && countlOne() == BitWidth;
+}
+
+bool APInt::testBit(std::size_t Bit) const noexcept {
+  return Bit < BitWidth && (Words[Bit / 64U] & (std::uint64_t{1} << (Bit % 64U))) != 0;
+}
+
 std::uint64_t APInt::word(std::size_t Index) const noexcept {
   return Index < Words.size() ? Words[Index] : 0;
 }
 
+Expected<APInt> APInt::bitwiseAnd(const APInt &Other) const {
+  if (BitWidth == 0 || BitWidth != Other.BitWidth)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "APInt bitwise operands must have the same nonzero width");
+  std::vector<std::uint64_t> ResultWords(Words.size(), 0);
+  for (std::size_t Index = 0; Index != Words.size(); ++Index)
+    ResultWords[Index] = Words[Index] & Other.Words[Index];
+  return create(BitWidth, ResultWords);
+}
+
+Expected<APInt> APInt::bitwiseOr(const APInt &Other) const {
+  if (BitWidth == 0 || BitWidth != Other.BitWidth)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "APInt bitwise operands must have the same nonzero width");
+  std::vector<std::uint64_t> ResultWords(Words.size(), 0);
+  for (std::size_t Index = 0; Index != Words.size(); ++Index)
+    ResultWords[Index] = Words[Index] | Other.Words[Index];
+  return create(BitWidth, ResultWords);
+}
+
+Expected<APInt> APInt::bitwiseXor(const APInt &Other) const {
+  if (BitWidth == 0 || BitWidth != Other.BitWidth)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "APInt bitwise operands must have the same nonzero width");
+  std::vector<std::uint64_t> ResultWords(Words.size(), 0);
+  for (std::size_t Index = 0; Index != Words.size(); ++Index)
+    ResultWords[Index] = Words[Index] ^ Other.Words[Index];
+  return create(BitWidth, ResultWords);
+}
+
+Expected<APInt> APInt::bitwiseNot() const {
+  if (BitWidth == 0)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "APInt bitwise complement requires a nonzero width");
+  std::vector<std::uint64_t> ResultWords(Words.size(), 0);
+  for (std::size_t Index = 0; Index != Words.size(); ++Index)
+    ResultWords[Index] = ~Words[Index];
+  ResultWords.back() &= highWordMask(BitWidth);
+  return create(BitWidth, ResultWords);
+}
+
 Expected<APInt> APInt::trunc(std::uint32_t NewBitWidth) const {
   if (NewBitWidth == 0 || NewBitWidth >= BitWidth)
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "APInt truncation requires a smaller nonzero width");
   std::vector<std::uint64_t> ResultWords(wordCount(NewBitWidth), 0);
-  std::ranges::copy_n(
-      Words.begin(),
-      static_cast<std::vector<std::uint64_t>::difference_type>(
-          ResultWords.size()),
-      ResultWords.begin());
+  std::ranges::copy_n(Words.begin(),
+                      static_cast<std::vector<std::uint64_t>::difference_type>(ResultWords.size()),
+                      ResultWords.begin());
   ResultWords.back() &= highWordMask(NewBitWidth);
   return create(NewBitWidth, ResultWords);
 }
@@ -287,9 +338,9 @@ Expected<APInt> APInt::sext(std::uint32_t NewBitWidth) const {
   if (NewBitWidth <= BitWidth || NewBitWidth > MaxBitWidth)
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "APInt sign extension requires a larger supported width");
-  std::vector<std::uint64_t> ResultWords(
-      wordCount(NewBitWidth),
-      isNegative() ? std::numeric_limits<std::uint64_t>::max() : std::uint64_t{0});
+  std::vector<std::uint64_t> ResultWords(wordCount(NewBitWidth),
+                                         isNegative() ? std::numeric_limits<std::uint64_t>::max()
+                                                      : std::uint64_t{0});
   std::ranges::copy(Words, ResultWords.begin());
   if (isNegative() && BitWidth % 64U != 0)
     ResultWords[wordCount(BitWidth) - 1U] |= ~highWordMask(BitWidth);
diff --git a/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp b/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp
index 4d81404..f1d2fac 100644
--- a/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp
+++ b/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp
@@ -4,6 +4,7 @@
 
 #include "RISCVImmediateMaterialization.h"
 #include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "rcc/CodeGen/GlobalISel/LegalizerHelper.h"
 #include "rcc/CodeGen/LowLevelType.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
@@ -1093,6 +1094,69 @@ Expected<void> RISCVLegalizerInfo::legalizeCustom(LegalizerHelper &Helper,
 
   MachineFunction &Function = Helper.MIRBuilder.function();
   const TargetDescription &Target = Helper.MIRBuilder.target();
+  if (Instruction.opcode() == opcode(GenericOpcode::G_ADD) ||
+      Instruction.opcode() == opcode(GenericOpcode::G_SUB)) {
+    auto XLenType = LowLevelType::makeCategoryNeutralScalar(64);
+    if (!XLenType)
+      return std::unexpected(XLenType.error());
+
+    Helper.Observer.changingInstr(Instruction);
+    if (auto Widened = Helper.widenScalarSrc(Instruction, *XLenType, 1, GenericOpcode::G_ANYEXT);
+        !Widened)
+      return std::unexpected(Widened.error());
+    if (auto Widened = Helper.widenScalarSrc(Instruction, *XLenType, 2, GenericOpcode::G_ANYEXT);
+        !Widened)
+      return std::unexpected(Widened.error());
+
+    auto ALUDestination = Function.registerInfo().createVirtualRegister(*XLenType);
+    if (!ALUDestination)
+      return std::unexpected(ALUDestination.error());
+    auto SignExtendedDestination = Function.registerInfo().createVirtualRegister(*XLenType);
+    if (!SignExtendedDestination)
+      return std::unexpected(SignExtendedDestination.error());
+
+    MachineOperand *DestinationOperand = Instruction.operandAt(0);
+    const Register *Destination =
+        DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+    if (Destination == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "RISC-V word arithmetic requires a register destination");
+    const Register OriginalDestination = *Destination;
+    if (auto Point = Helper.MIRBuilder.setInsertPointAfter(Instruction); !Point)
+      return std::unexpected(Point.error());
+    if (auto Built =
+            Helper.MIRBuilder.buildSExtInReg(*SignExtendedDestination, *ALUDestination, 32);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Built = Helper.MIRBuilder.buildTrunc(OriginalDestination, *SignExtendedDestination);
+        !Built)
+      return std::unexpected(Built.error());
+    if (auto Changed = DestinationOperand->setRegister(*ALUDestination); !Changed)
+      return std::unexpected(Changed.error());
+    Helper.Observer.changedInstr(Instruction);
+    return {};
+  }
+  if (Instruction.opcode() == opcode(GenericOpcode::G_SEXT_INREG)) {
+    const MachineOperand *DestinationOperand = Instruction.operandAt(0);
+    const MachineOperand *SizeOperand = Instruction.operandAt(2);
+    const Register *Destination =
+        DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+    const std::int64_t *Size =
+        SizeOperand == nullptr ? nullptr : SizeOperand->getIf<std::int64_t>();
+    if (Destination == nullptr || Size == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "RISC-V G_SEXT_INREG has invalid operands");
+    auto DestinationType = Function.registerInfo().getType(*Destination);
+    if (!DestinationType)
+      return std::unexpected(DestinationType.error());
+    if (DestinationType->minimumBitWidth() == 64 && *Size == 32)
+      return {};
+    return Helper.lower(Instruction, LegalizationDecision{
+                                         .Action = LegalizationAction::Lower,
+                                         .TypeIndex = 0,
+                                         .NewType = {},
+                                     });
+  }
   if (Instruction.opcode() == opcode(GenericOpcode::G_ICMP))
     return lowerIntegerCompare(Instruction, Function, Target);
   if (Instruction.opcode() == opcode(GenericOpcode::G_ATOMIC_CMPXCHG))
diff --git a/backend/lib/Target/RISCV/RISCVTarget.cpp b/backend/lib/Target/RISCV/RISCVTarget.cpp
index 8bdea20..1735386 100644
--- a/backend/lib/Target/RISCV/RISCVTarget.cpp
+++ b/backend/lib/Target/RISCV/RISCVTarget.cpp
@@ -241,8 +241,12 @@ Expected<TargetDescription> createTargetDescription() {
   TargetMIRTextInfoDesc MIRText;
   appendGeneratedMIRTextInfo(MIRText);
   configureFunctionInfoMIRSchema(MIRText);
+  TargetBooleanContentInfo BooleanInfo{
+      .ScalarInteger = BooleanContent::ZeroOrOne,
+      .ScalarFloatingPoint = BooleanContent::ZeroOrOne,
+  };
   return TargetDescription::create(std::move(*Instructions), std::move(*Registers),
-                                   std::move(MIRText));
+                                   std::move(MIRText), BooleanInfo);
 }
 
 std::shared_ptr<const RegisterMask> createCallPreservedMask(CallingConvention Convention) {