Index: lib/Target/ARM/ARMCodeGenPrepare.cpp
===================================================================
--- lib/Target/ARM/ARMCodeGenPrepare.cpp
+++ lib/Target/ARM/ARMCodeGenPrepare.cpp
@@ -119,7 +119,7 @@
   // This defines the max range of the values that we allow in the promoted
   // tree.
   IntegerType *OrigTy = nullptr;
-  SmallPtrSetImpl<Value*> *Visited;
+  SetVector<Value*> *Visited;
   SmallPtrSetImpl<Value*> *Sources;
   SmallPtrSetImpl<Instruction*> *Sinks;
   SmallPtrSetImpl<Instruction*> *SafeToPromote;
@@ -138,7 +138,7 @@
 
 
   void Mutate(Type *OrigTy,
-              SmallPtrSetImpl<Value*> &Visited,
+              SetVector<Value*> &Visited,
               SmallPtrSetImpl<Value*> &Sources,
               SmallPtrSetImpl<Instruction*> &Sinks,
               SmallPtrSetImpl<Instruction*> &SafeToPromote);
@@ -498,7 +498,7 @@
 
       if (auto *Const = dyn_cast<ConstantInt>(I->getOperand(1))) {
         if (!Const->isNegative())
-          break;
+          continue;
 
         unsigned Opc = I->getOpcode();
         if (Opc != Instruction::Add && Opc != Instruction::Sub)
@@ -755,7 +755,7 @@
 }
 
 void IRPromoter::Mutate(Type *OrigTy,
-                        SmallPtrSetImpl<Value*> &Visited,
+                        SetVector<Value*> &Visited,
                         SmallPtrSetImpl<Value*> &Sources,
                         SmallPtrSetImpl<Instruction*> &Sinks,
                         SmallPtrSetImpl<Instruction*> &SafeToPromote) {
@@ -935,7 +935,7 @@
   SetVector<Value*> WorkList;
   SmallPtrSet<Value*, 8> Sources;
   SmallPtrSet<Instruction*, 4> Sinks;
-  SmallPtrSet<Value*, 16> CurrentVisited;
+  SetVector<Value*> CurrentVisited;
   WorkList.insert(V);
 
   // Return true if V was added to the worklist as a supported instruction,
Index: test/CodeGen/ARM/CGP/arm-cgp-overflow.ll
===================================================================
--- test/CodeGen/ARM/CGP/arm-cgp-overflow.ll
+++ test/CodeGen/ARM/CGP/arm-cgp-overflow.ll
@@ -230,3 +230,20 @@
   %conv4 = zext i1 %cmp to i32
   ret i32 %conv4
 }
+
+; CHECK-LABEL: convert_add_order
+; CHECK: orr{{.*}}, #1
+; CHECK: sub{{.*}}, #40
+; CHECK-NOT: uxt
+define i8 @convert_add_order(i8 zeroext %arg) {
+  %mask.0 = and i8 %arg, 1
+  %mask.1 = and i8 %arg, 2
+  %shl = or i8 %arg, 1
+  %add = add nuw i8 %shl, 10
+  %cmp.0 = icmp ult i8 %add, 60
+  %sub = add nsw i8 %shl, -40
+  %cmp.1 = icmp ult i8 %sub, 20
+  %mask.sel = select i1 %cmp.1, i8 %mask.0, i8 %mask.1
+  %res = select i1 %cmp.0, i8 %mask.sel, i8 %arg
+  ret i8 %res
+}