Index: llvm/trunk/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h
===================================================================
--- llvm/trunk/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h
+++ llvm/trunk/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h
@@ -107,6 +107,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) {
@@ -147,8 +160,8 @@
 
   /// Iterate the given function (typically something like doubling the width)
   /// on Ty until we find a legal type for this operation.
-  Optional<LLT> findLegalType(const InstrAspect &Aspect,
-                    function_ref<LLT(LLT)> NextType) const {
+  Optional<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;
@@ -160,10 +173,9 @@
         if (DefaultIt == DefaultActions.end())
           return None;
         Action = DefaultIt->second;
-      }
-      else
+      } else
         Action = ActionIt->second;
-    } while(Action != Legal);
+    } while (needsLegalizingToDifferentSize(Action));
     return Ty;
   }
 
Index: llvm/trunk/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
===================================================================
--- llvm/trunk/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
+++ llvm/trunk/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
@@ -178,19 +178,23 @@
   case Libcall:
   case Custom:
     return Aspect.Type;
-  case NarrowScalar:
-    return findLegalType(Aspect,
-                         [](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
-  case WidenScalar:
-    return findLegalType(Aspect, [](LLT Ty) -> LLT {
+  case NarrowScalar: {
+    return findLegalizableSize(
+        Aspect, [&](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
+  }
+  case WidenScalar: {
+    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(); });
-  case MoreElements:
-    return findLegalType(Aspect,
-                         [](LLT Ty) -> LLT { return Ty.doubleElements(); });
+  }
+  case FewerElements: {
+    return findLegalizableSize(
+        Aspect, [&](LLT Ty) -> LLT { return Ty.halfElements(); });
+  }
+  case MoreElements: {
+    return findLegalizableSize(
+        Aspect, [&](LLT Ty) -> LLT { return Ty.doubleElements(); });
+  }
   }
 }
 
Index: llvm/trunk/lib/Target/ARM/ARMLegalizerInfo.cpp
===================================================================
--- llvm/trunk/lib/Target/ARM/ARMLegalizerInfo.cpp
+++ llvm/trunk/lib/Target/ARM/ARMLegalizerInfo.cpp
@@ -55,10 +55,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
@@ -122,40 +119,6 @@
   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;
-  }
   case G_SREM:
   case G_UREM: {
     unsigned OriginalResult = MI.getOperand(0).getReg();
Index: llvm/trunk/unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp
===================================================================
--- llvm/trunk/unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp
+++ llvm/trunk/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)));
+}
 }