Index: include/llvm/CodeGen/GlobalISel/LegalizerInfo.h
===================================================================
--- include/llvm/CodeGen/GlobalISel/LegalizerInfo.h
+++ include/llvm/CodeGen/GlobalISel/LegalizerInfo.h
@@ -104,6 +104,19 @@
   /// before any query is made or incorrect results may be returned.
   void computeTables();
 
+  static bool NeedsLegalizingToDifferentSize(const LegalizeAction Action) {
+    switch (Action) {
+    case NarrowScalar:
+    case WidenScalar:
+    case FewerElements:
+    case MoreElements:
+    case Unsupported:
+      return true;
+    default:
+      return false;
+    }
+  }
+
   /// More friendly way to set an action for common types that have an LLT
   /// representation.
   void setAction(const InstrAspect &Aspect, LegalizeAction Action) {
@@ -144,9 +157,9 @@
   getAction(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
 
   /// Iterate the given function (typically something like doubling the width)
-  /// on Ty until we find a legal type for this operation.
-  LLT findLegalType(const InstrAspect &Aspect,
-                    function_ref<LLT(LLT)> NextType) const {
+  /// on Ty until we find a legalizable size for this operation.
+  LLT findLegalizableSize(const InstrAspect &Aspect,
+                          function_ref<LLT(LLT)> NextType) const {
     LegalizeAction Action;
     const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx];
     LLT Ty = Aspect.Type;
@@ -157,7 +170,7 @@
         Action = DefaultActions.find(Aspect.Opcode)->second;
       else
         Action = ActionIt->second;
-    } while(Action != Legal);
+    } while(NeedsLegalizingToDifferentSize(Action));
     return Ty;
   }
 
Index: lib/CodeGen/GlobalISel/LegalizerInfo.cpp
===================================================================
--- lib/CodeGen/GlobalISel/LegalizerInfo.cpp
+++ lib/CodeGen/GlobalISel/LegalizerInfo.cpp
@@ -173,21 +173,21 @@
   case Custom:
     return Aspect.Type;
   case NarrowScalar: {
-    return findLegalType(Aspect,
-                         [&](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
+    return findLegalizableSize(
+        Aspect, [&](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
   }
   case WidenScalar: {
-    return findLegalType(Aspect, [&](LLT Ty) -> LLT {
+    return findLegalizableSize(Aspect, [&](LLT Ty) -> LLT {
       return Ty.getSizeInBits() < 8 ? LLT::scalar(8) : Ty.doubleScalarSize();
     });
   }
   case FewerElements: {
-    return findLegalType(Aspect,
-                         [&](LLT Ty) -> LLT { return Ty.halfElements(); });
+    return findLegalizableSize(
+        Aspect, [&](LLT Ty) -> LLT { return Ty.halfElements(); });
   }
   case MoreElements: {
-    return findLegalType(Aspect,
-                         [&](LLT Ty) -> LLT { return Ty.doubleElements(); });
+    return findLegalizableSize(
+        Aspect, [&](LLT Ty) -> LLT { return Ty.doubleElements(); });
   }
   }
 }
Index: lib/Target/ARM/ARMLegalizerInfo.h
===================================================================
--- lib/Target/ARM/ARMLegalizerInfo.h
+++ lib/Target/ARM/ARMLegalizerInfo.h
@@ -24,9 +24,6 @@
 class ARMLegalizerInfo : public LegalizerInfo {
 public:
   ARMLegalizerInfo(const ARMSubtarget &ST);
-
-  bool legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
-                      MachineIRBuilder &MIRBuilder) const override;
 };
 } // End llvm namespace.
 #endif
Index: lib/Target/ARM/ARMLegalizerInfo.cpp
===================================================================
--- lib/Target/ARM/ARMLegalizerInfo.cpp
+++ lib/Target/ARM/ARMLegalizerInfo.cpp
@@ -51,10 +51,7 @@
 
   for (unsigned Op : {G_SDIV, G_UDIV}) {
     for (auto Ty : {s8, s16})
-      // FIXME: We need WidenScalar here, but in the case of targets with
-      // software division we'll also need Libcall afterwards. Treat as Custom
-      // until we have better support for chaining legalization actions.
-      setAction({Op, Ty}, Custom);
+      setAction({Op, Ty}, WidenScalar);
     if (ST.hasDivideInARMMode())
       setAction({Op, s32}, Legal);
     else
@@ -89,48 +86,3 @@
 
   computeTables();
 }
-
-bool ARMLegalizerInfo::legalizeCustom(MachineInstr &MI,
-                                      MachineRegisterInfo &MRI,
-                                      MachineIRBuilder &MIRBuilder) const {
-  using namespace TargetOpcode;
-
-  switch (MI.getOpcode()) {
-  default:
-    return false;
-  case G_SDIV:
-  case G_UDIV: {
-    LLT Ty = MRI.getType(MI.getOperand(0).getReg());
-    if (Ty != LLT::scalar(16) && Ty != LLT::scalar(8))
-      return false;
-
-    // We need to widen to 32 bits and then maybe, if the target requires,
-    // transform into a libcall.
-    LegalizerHelper Helper(MIRBuilder.getMF());
-
-    MachineInstr *NewMI = nullptr;
-    Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
-      // Store the new, 32-bit div instruction.
-      if (MI->getOpcode() == G_SDIV || MI->getOpcode() == G_UDIV)
-        NewMI = MI;
-    });
-
-    auto Result = Helper.widenScalar(MI, 0, LLT::scalar(32));
-    Helper.MIRBuilder.stopRecordingInsertions();
-    if (Result == LegalizerHelper::UnableToLegalize) {
-      return false;
-    }
-    assert(NewMI && "Couldn't find widened instruction");
-    assert((NewMI->getOpcode() == G_SDIV || NewMI->getOpcode() == G_UDIV) &&
-           "Unexpected widened instruction");
-    assert(MRI.getType(NewMI->getOperand(0).getReg()).getSizeInBits() == 32 &&
-           "Unexpected type for the widened instruction");
-
-    Result = Helper.legalizeInstrStep(*NewMI);
-    if (Result == LegalizerHelper::UnableToLegalize) {
-      return false;
-    }
-    return true;
-  }
-  }
-}
Index: unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp
===================================================================
--- unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp
+++ unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp
@@ -117,4 +117,23 @@
   ASSERT_EQ(L.getAction({G_PTRTOINT, 1, p0}),
             std::make_pair(LegalizerInfo::Legal, p0));
 }
+
+TEST(LegalizerInfoTest, MultipleSteps) {
+  using namespace TargetOpcode;
+  LegalizerInfo L;
+  LLT s16 = LLT::scalar(16);
+  LLT s32 = LLT::scalar(32);
+  LLT s64 = LLT::scalar(64);
+
+  L.setAction({G_UREM, 0, s16}, LegalizerInfo::WidenScalar);
+  L.setAction({G_UREM, 0, s32}, LegalizerInfo::Lower);
+  L.setAction({G_UREM, 0, s64}, LegalizerInfo::Lower);
+
+  L.computeTables();
+
+  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(16)}),
+            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
+  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(32)}),
+            std::make_pair(LegalizerInfo::Lower, LLT::scalar(32)));
+}
 }