[GlobalISel] Match LLVM legalization value tracking

1 files changed, 324 insertions, 406 deletions

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;