Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
===================================================================
--- llvm/trunk/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ llvm/trunk/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -1447,6 +1447,14 @@
     return replaceInstUsesWith(I, Ext);
   }
 
+  // X urem C -> X < C ? X : X - C, where C >= signbit.
+  const APInt *DivisorC;
+  if (match(Op1, m_APInt(DivisorC)) && DivisorC->isNegative()) {
+    Value *Cmp = Builder->CreateICmpULT(Op0, Op1);
+    Value *Sub = Builder->CreateSub(Op0, Op1);
+    return SelectInst::Create(Cmp, Op0, Sub);
+  }
+
   return nullptr;
 }
 
Index: llvm/trunk/test/Transforms/InstCombine/urem.ll
===================================================================
--- llvm/trunk/test/Transforms/InstCombine/urem.ll
+++ llvm/trunk/test/Transforms/InstCombine/urem.ll
@@ -16,25 +16,33 @@
 
 define i8 @big_divisor(i8 %x) {
 ; CHECK-LABEL: @big_divisor(
-; CHECK-NEXT:    [[REM:%.*]] = urem i8 %x, -127
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 %x, -127
+; CHECK-NEXT:    [[TMP2:%.*]] = add i8 %x, 127
+; CHECK-NEXT:    [[REM:%.*]] = select i1 [[TMP1]], i8 %x, i8 [[TMP2]]
 ; CHECK-NEXT:    ret i8 [[REM]]
 ;
   %rem = urem i8 %x, 129
   ret i8 %rem
 }
 
+; TODO: Should this be zext+add instead of sext+sub?
 define i5 @biggest_divisor(i5 %x) {
 ; CHECK-LABEL: @biggest_divisor(
-; CHECK-NEXT:    [[REM:%.*]] = urem i5 %x, -1
+; CHECK-NEXT:    [[NOT_:%.*]] = icmp eq i5 %x, -1
+; CHECK-NEXT:    [[TMP1:%.*]] = sext i1 [[NOT_]] to i5
+; CHECK-NEXT:    [[REM:%.*]] = sub i5 %x, [[TMP1]]
 ; CHECK-NEXT:    ret i5 [[REM]]
 ;
   %rem = urem i5 %x, -1
   ret i5 %rem
 }
 
+; TODO: Should vector subtract of constant be canonicalized to add?
 define <2 x i4> @big_divisor_vec(<2 x i4> %x) {
 ; CHECK-LABEL: @big_divisor_vec(
-; CHECK-NEXT:    [[REM:%.*]] = urem <2 x i4> %x, <i4 -3, i4 -3>
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult <2 x i4> %x, <i4 -3, i4 -3>
+; CHECK-NEXT:    [[TMP2:%.*]] = sub <2 x i4> %x, <i4 -3, i4 -3>
+; CHECK-NEXT:    [[REM:%.*]] = select <2 x i1> [[TMP1]], <2 x i4> %x, <2 x i4> [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i4> [[REM]]
 ;
   %rem = urem <2 x i4> %x, <i4 13, i4 13>