Added support for unsigned comparisons

Rationale: even though not directly supported in input graph,
           having the ability to express unsigned comparisons
           in HIR is useful for all sorts of optimizations.

Change-Id: I4543c96a8c1895c3d33aaf85685afbf80fe27d72

10 files changed, 593 insertions, 68 deletions

diff --git a/compiler/optimizing/boolean_simplifier.cc b/compiler/optimizing/boolean_simplifier.cc
index 5b346872b0..f985745e7a 100644
--- a/compiler/optimizing/boolean_simplifier.cc
+++ b/compiler/optimizing/boolean_simplifier.cc
@@ -69,19 +69,17 @@ static HInstruction* GetOppositeCondition(HInstruction* cond) {
   if (cond->IsCondition()) {
     HInstruction* lhs = cond->InputAt(0);
     HInstruction* rhs = cond->InputAt(1);
-    if (cond->IsEqual()) {
-      return new (allocator) HNotEqual(lhs, rhs);
-    } else if (cond->IsNotEqual()) {
-      return new (allocator) HEqual(lhs, rhs);
-    } else if (cond->IsLessThan()) {
-      return new (allocator) HGreaterThanOrEqual(lhs, rhs);
-    } else if (cond->IsLessThanOrEqual()) {
-      return new (allocator) HGreaterThan(lhs, rhs);
-    } else if (cond->IsGreaterThan()) {
-      return new (allocator) HLessThanOrEqual(lhs, rhs);
-    } else {
-      DCHECK(cond->IsGreaterThanOrEqual());
-      return new (allocator) HLessThan(lhs, rhs);
+    switch (cond->AsCondition()->GetOppositeCondition()) {  // get *opposite*
+      case kCondEQ: return new (allocator) HEqual(lhs, rhs);
+      case kCondNE: return new (allocator) HNotEqual(lhs, rhs);
+      case kCondLT: return new (allocator) HLessThan(lhs, rhs);
+      case kCondLE: return new (allocator) HLessThanOrEqual(lhs, rhs);
+      case kCondGT: return new (allocator) HGreaterThan(lhs, rhs);
+      case kCondGE: return new (allocator) HGreaterThanOrEqual(lhs, rhs);
+      case kCondB:  return new (allocator) HBelow(lhs, rhs);
+      case kCondBE: return new (allocator) HBelowOrEqual(lhs, rhs);
+      case kCondA:  return new (allocator) HAbove(lhs, rhs);
+      case kCondAE: return new (allocator) HAboveOrEqual(lhs, rhs);
     }
   } else if (cond->IsIntConstant()) {
     HIntConstant* int_const = cond->AsIntConstant();
@@ -91,11 +89,10 @@ static HInstruction* GetOppositeCondition(HInstruction* cond) {
       DCHECK(int_const->IsOne());
       return graph->GetIntConstant(0);
     }
-  } else {
-    // General case when 'cond' is another instruction of type boolean,
-    // as verified by SSAChecker.
-    return new (allocator) HBooleanNot(cond);
   }
+  // General case when 'cond' is another instruction of type boolean,
+  // as verified by SSAChecker.
+  return new (allocator) HBooleanNot(cond);
 }
 
 void HBooleanSimplifier::TryRemovingBooleanSelection(HBasicBlock* block) {
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index d172fba888..cac74c8da6 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -409,7 +409,7 @@ class ArraySetSlowPathARM : public SlowPathCode {
 #undef __
 #define __ down_cast<ArmAssembler*>(GetAssembler())->
 
-inline Condition ARMSignedOrFPCondition(IfCondition cond) {
+inline Condition ARMCondition(IfCondition cond) {
   switch (cond) {
     case kCondEQ: return EQ;
     case kCondNE: return NE;
@@ -417,19 +417,30 @@ inline Condition ARMSignedOrFPCondition(IfCondition cond) {
     case kCondLE: return LE;
     case kCondGT: return GT;
     case kCondGE: return GE;
+    case kCondB:  return LO;
+    case kCondBE: return LS;
+    case kCondA:  return HI;
+    case kCondAE: return HS;
   }
   LOG(FATAL) << "Unreachable";
   UNREACHABLE();
 }
 
+// Maps signed condition to unsigned condition.
 inline Condition ARMUnsignedCondition(IfCondition cond) {
   switch (cond) {
     case kCondEQ: return EQ;
     case kCondNE: return NE;
+    // Signed to unsigned.
     case kCondLT: return LO;
     case kCondLE: return LS;
     case kCondGT: return HI;
     case kCondGE: return HS;
+    // Unsigned remain unchanged.
+    case kCondB:  return LO;
+    case kCondBE: return LS;
+    case kCondA:  return HI;
+    case kCondAE: return HS;
   }
   LOG(FATAL) << "Unreachable";
   UNREACHABLE();
@@ -1149,12 +1160,13 @@ void InstructionCodeGeneratorARM::GenerateFPJumps(HCondition* cond,
                                                   Label* true_label,
                                                   Label* false_label) {
   __ vmstat();  // transfer FP status register to ARM APSR.
+  // TODO: merge into a single branch (except "equal or unordered" and "not equal")
   if (cond->IsFPConditionTrueIfNaN()) {
     __ b(true_label, VS);  // VS for unordered.
   } else if (cond->IsFPConditionFalseIfNaN()) {
     __ b(false_label, VS);  // VS for unordered.
   }
-  __ b(true_label, ARMSignedOrFPCondition(cond->GetCondition()));
+  __ b(true_label, ARMCondition(cond->GetCondition()));
 }
 
 void InstructionCodeGeneratorARM::GenerateLongComparesAndJumps(HCondition* cond,
@@ -1169,10 +1181,11 @@ void InstructionCodeGeneratorARM::GenerateLongComparesAndJumps(HCondition* cond,
   Register left_low = left.AsRegisterPairLow<Register>();
   IfCondition true_high_cond = if_cond;
   IfCondition false_high_cond = cond->GetOppositeCondition();
-  Condition final_condition = ARMUnsignedCondition(if_cond);
+  Condition final_condition = ARMUnsignedCondition(if_cond);  // unsigned on lower part
 
   // Set the conditions for the test, remembering that == needs to be
   // decided using the low words.
+  // TODO: consider avoiding jumps with temporary and CMP low+SBC high
   switch (if_cond) {
     case kCondEQ:
     case kCondNE:
@@ -1190,6 +1203,18 @@ void InstructionCodeGeneratorARM::GenerateLongComparesAndJumps(HCondition* cond,
     case kCondGE:
       true_high_cond = kCondGT;
       break;
+    case kCondB:
+      false_high_cond = kCondA;
+      break;
+    case kCondBE:
+      true_high_cond = kCondB;
+      break;
+    case kCondA:
+      false_high_cond = kCondB;
+      break;
+    case kCondAE:
+      true_high_cond = kCondA;
+      break;
   }
   if (right.IsConstant()) {
     int64_t value = right.GetConstant()->AsLongConstant()->GetValue();
@@ -1198,12 +1223,12 @@ void InstructionCodeGeneratorARM::GenerateLongComparesAndJumps(HCondition* cond,
 
     GenerateCompareWithImmediate(left_high, val_high);
     if (if_cond == kCondNE) {
-      __ b(true_label, ARMSignedOrFPCondition(true_high_cond));
+      __ b(true_label, ARMCondition(true_high_cond));
     } else if (if_cond == kCondEQ) {
-      __ b(false_label, ARMSignedOrFPCondition(false_high_cond));
+      __ b(false_label, ARMCondition(false_high_cond));
     } else {
-      __ b(true_label, ARMSignedOrFPCondition(true_high_cond));
-      __ b(false_label, ARMSignedOrFPCondition(false_high_cond));
+      __ b(true_label, ARMCondition(true_high_cond));
+      __ b(false_label, ARMCondition(false_high_cond));
     }
     // Must be equal high, so compare the lows.
     GenerateCompareWithImmediate(left_low, val_low);
@@ -1213,17 +1238,18 @@ void InstructionCodeGeneratorARM::GenerateLongComparesAndJumps(HCondition* cond,
 
     __ cmp(left_high, ShifterOperand(right_high));
     if (if_cond == kCondNE) {
-      __ b(true_label, ARMSignedOrFPCondition(true_high_cond));
+      __ b(true_label, ARMCondition(true_high_cond));
     } else if (if_cond == kCondEQ) {
-      __ b(false_label, ARMSignedOrFPCondition(false_high_cond));
+      __ b(false_label, ARMCondition(false_high_cond));
     } else {
-      __ b(true_label, ARMSignedOrFPCondition(true_high_cond));
-      __ b(false_label, ARMSignedOrFPCondition(false_high_cond));
+      __ b(true_label, ARMCondition(true_high_cond));
+      __ b(false_label, ARMCondition(false_high_cond));
     }
     // Must be equal high, so compare the lows.
     __ cmp(left_low, ShifterOperand(right_low));
   }
   // The last comparison might be unsigned.
+  // TODO: optimize cases where this is always true/false
   __ b(true_label, final_condition);
 }
 
@@ -1315,7 +1341,7 @@ void InstructionCodeGeneratorARM::GenerateTestAndBranch(HInstruction* instructio
         DCHECK(right.IsConstant());
         GenerateCompareWithImmediate(left, CodeGenerator::GetInt32ValueOf(right.GetConstant()));
       }
-      __ b(true_target, ARMSignedOrFPCondition(cond->AsCondition()->GetCondition()));
+      __ b(true_target, ARMCondition(cond->AsCondition()->GetCondition()));
     }
   }
   if (false_target != nullptr) {
@@ -1417,11 +1443,11 @@ void InstructionCodeGeneratorARM::VisitCondition(HCondition* cond) {
         GenerateCompareWithImmediate(left.AsRegister<Register>(),
                                      CodeGenerator::GetInt32ValueOf(right.GetConstant()));
       }
-      __ it(ARMSignedOrFPCondition(cond->GetCondition()), kItElse);
+      __ it(ARMCondition(cond->GetCondition()), kItElse);
       __ mov(locations->Out().AsRegister<Register>(), ShifterOperand(1),
-             ARMSignedOrFPCondition(cond->GetCondition()));
+             ARMCondition(cond->GetCondition()));
       __ mov(locations->Out().AsRegister<Register>(), ShifterOperand(0),
-             ARMSignedOrFPCondition(cond->GetOppositeCondition()));
+             ARMCondition(cond->GetOppositeCondition()));
       return;
     }
     case Primitive::kPrimLong:
@@ -1500,6 +1526,38 @@ void InstructionCodeGeneratorARM::VisitGreaterThanOrEqual(HGreaterThanOrEqual* c
   VisitCondition(comp);
 }
 
+void LocationsBuilderARM::VisitBelow(HBelow* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorARM::VisitBelow(HBelow* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderARM::VisitBelowOrEqual(HBelowOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorARM::VisitBelowOrEqual(HBelowOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderARM::VisitAbove(HAbove* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorARM::VisitAbove(HAbove* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderARM::VisitAboveOrEqual(HAboveOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorARM::VisitAboveOrEqual(HAboveOrEqual* comp) {
+  VisitCondition(comp);
+}
+
 void LocationsBuilderARM::VisitLocal(HLocal* local) {
   local->SetLocations(nullptr);
 }
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index c94da86d2c..4e33ee15da 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -77,6 +77,10 @@ inline Condition ARM64Condition(IfCondition cond) {
     case kCondLE: return le;
     case kCondGT: return gt;
     case kCondGE: return ge;
+    case kCondB:  return lo;
+    case kCondBE: return ls;
+    case kCondA:  return hi;
+    case kCondAE: return hs;
   }
   LOG(FATAL) << "Unreachable";
   UNREACHABLE();
@@ -1937,7 +1941,11 @@ void InstructionCodeGeneratorARM64::VisitCondition(HCondition* instruction) {
   M(LessThan)                                                                            \
   M(LessThanOrEqual)                                                                     \
   M(GreaterThan)                                                                         \
-  M(GreaterThanOrEqual)
+  M(GreaterThanOrEqual)                                                                  \
+  M(Below)                                                                               \
+  M(BelowOrEqual)                                                                        \
+  M(Above)                                                                               \
+  M(AboveOrEqual)
 #define DEFINE_CONDITION_VISITORS(Name)                                                  \
 void LocationsBuilderARM64::Visit##Name(H##Name* comp) { VisitCondition(comp); }         \
 void InstructionCodeGeneratorARM64::Visit##Name(H##Name* comp) { VisitCondition(comp); }
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index 1a08503cf9..eb20291e20 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -1778,6 +1778,9 @@ void InstructionCodeGeneratorMIPS64::VisitCondition(HCondition* instruction) {
     return;
   }
 
+  // TODO: generalize to long
+  DCHECK_NE(instruction->InputAt(0)->GetType(), Primitive::kPrimLong);
+
   LocationSummary* locations = instruction->GetLocations();
 
   GpuRegister dst = locations->Out().AsRegister<GpuRegister>();
@@ -1855,6 +1858,48 @@ void InstructionCodeGeneratorMIPS64::VisitCondition(HCondition* instruction) {
         }
       }
       break;
+
+    case kCondB:
+    case kCondAE:
+      if (use_imm && 0 <= rhs_imm && rhs_imm <= 0x7fff) {
+        __ Sltiu(dst, lhs, rhs_imm);
+      } else {
+        if (use_imm) {
+          rhs_reg = TMP;
+          __ LoadConst32(rhs_reg, rhs_imm);
+        }
+        __ Sltu(dst, lhs, rhs_reg);
+      }
+      if (if_cond == kCondAE) {
+        // Simulate lhs >= rhs via !(lhs < rhs) since there's
+        // only the sltu instruction but no sgeu.
+        __ Xori(dst, dst, 1);
+      }
+      break;
+
+    case kCondBE:
+    case kCondA:
+      if (use_imm && 0 <= rhs_imm && rhs_imm <= 0x7ffe) {
+        // Simulate lhs <= rhs via lhs < rhs + 1.
+        __ Sltiu(dst, lhs, rhs_imm + 1);
+        if (if_cond == kCondA) {
+          // Simulate lhs > rhs via !(lhs <= rhs) since there's
+          // only the sltiu instruction but no sgtiu.
+          __ Xori(dst, dst, 1);
+        }
+      } else {
+        if (use_imm) {
+          rhs_reg = TMP;
+          __ LoadConst32(rhs_reg, rhs_imm);
+        }
+        __ Sltu(dst, rhs_reg, lhs);
+        if (if_cond == kCondBE) {
+          // Simulate lhs <= rhs via !(rhs < lhs) since there's
+          // only the sltu instruction but no sleu.
+          __ Xori(dst, dst, 1);
+        }
+      }
+      break;
   }
 }
 
@@ -2072,6 +2117,17 @@ void InstructionCodeGeneratorMIPS64::GenerateTestAndBranch(HInstruction* instruc
         case kCondGT:
           __ Bgtzc(lhs, true_target);
           break;
+        case kCondB:
+          break;  // always false
+        case kCondBE:
+          __ Beqzc(lhs, true_target);  // <= 0 if zero
+          break;
+        case kCondA:
+          __ Bnezc(lhs, true_target);  // > 0 if non-zero
+          break;
+        case kCondAE:
+          __ B(true_target);  // always true
+          break;
       }
     } else {
       if (use_imm) {
@@ -2086,12 +2142,16 @@ void InstructionCodeGeneratorMIPS64::GenerateTestAndBranch(HInstruction* instruc
           case kCondEQ:
           case kCondGE:
           case kCondLE:
+          case kCondBE:
+          case kCondAE:
             // if lhs == rhs for a positive condition, then it is a branch
             __ B(true_target);
             break;
           case kCondNE:
           case kCondLT:
           case kCondGT:
+          case kCondB:
+          case kCondA:
             // if lhs == rhs for a negative condition, then it is a NOP
             break;
         }
@@ -2115,6 +2175,18 @@ void InstructionCodeGeneratorMIPS64::GenerateTestAndBranch(HInstruction* instruc
           case kCondGT:
             __ Bltc(rhs_reg, lhs, true_target);
             break;
+          case kCondB:
+            __ Bltuc(lhs, rhs_reg, true_target);
+            break;
+          case kCondAE:
+            __ Bgeuc(lhs, rhs_reg, true_target);
+            break;
+          case kCondBE:
+            __ Bgeuc(rhs_reg, lhs, true_target);
+            break;
+          case kCondA:
+            __ Bltuc(rhs_reg, lhs, true_target);
+            break;
         }
       }
     }
@@ -3462,6 +3534,38 @@ void InstructionCodeGeneratorMIPS64::VisitGreaterThanOrEqual(HGreaterThanOrEqual
   VisitCondition(comp);
 }
 
+void LocationsBuilderMIPS64::VisitBelow(HBelow* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorMIPS64::VisitBelow(HBelow* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderMIPS64::VisitBelowOrEqual(HBelowOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorMIPS64::VisitBelowOrEqual(HBelowOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderMIPS64::VisitAbove(HAbove* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorMIPS64::VisitAbove(HAbove* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderMIPS64::VisitAboveOrEqual(HAboveOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorMIPS64::VisitAboveOrEqual(HAboveOrEqual* comp) {
+  VisitCondition(comp);
+}
+
 void LocationsBuilderMIPS64::VisitFakeString(HFakeString* instruction) {
   DCHECK(codegen_->IsBaseline());
   LocationSummary* locations =
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index f8be21a06e..f385afaa7f 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -428,7 +428,7 @@ class ArraySetSlowPathX86 : public SlowPathCode {
 #undef __
 #define __ down_cast<X86Assembler*>(GetAssembler())->
 
-inline Condition X86SignedCondition(IfCondition cond) {
+inline Condition X86Condition(IfCondition cond) {
   switch (cond) {
     case kCondEQ: return kEqual;
     case kCondNE: return kNotEqual;
@@ -436,19 +436,30 @@ inline Condition X86SignedCondition(IfCondition cond) {
     case kCondLE: return kLessEqual;
     case kCondGT: return kGreater;
     case kCondGE: return kGreaterEqual;
+    case kCondB:  return kBelow;
+    case kCondBE: return kBelowEqual;
+    case kCondA:  return kAbove;
+    case kCondAE: return kAboveEqual;
   }
   LOG(FATAL) << "Unreachable";
   UNREACHABLE();
 }
 
+// Maps signed condition to unsigned condition and FP condition to x86 name.
 inline Condition X86UnsignedOrFPCondition(IfCondition cond) {
   switch (cond) {
     case kCondEQ: return kEqual;
     case kCondNE: return kNotEqual;
+    // Signed to unsigned, and FP to x86 name.
     case kCondLT: return kBelow;
     case kCondLE: return kBelowEqual;
     case kCondGT: return kAbove;
     case kCondGE: return kAboveEqual;
+    // Unsigned remain unchanged.
+    case kCondB:  return kBelow;
+    case kCondBE: return kBelowEqual;
+    case kCondA:  return kAbove;
+    case kCondAE: return kAboveEqual;
   }
   LOG(FATAL) << "Unreachable";
   UNREACHABLE();
@@ -1067,7 +1078,7 @@ void InstructionCodeGeneratorX86::GenerateLongComparesAndJumps(HCondition* cond,
   Register left_low = left.AsRegisterPairLow<Register>();
   IfCondition true_high_cond = if_cond;
   IfCondition false_high_cond = cond->GetOppositeCondition();
-  Condition final_condition = X86UnsignedOrFPCondition(if_cond);
+  Condition final_condition = X86UnsignedOrFPCondition(if_cond);  // unsigned on lower part
 
   // Set the conditions for the test, remembering that == needs to be
   // decided using the low words.
@@ -1088,6 +1099,18 @@ void InstructionCodeGeneratorX86::GenerateLongComparesAndJumps(HCondition* cond,
     case kCondGE:
       true_high_cond = kCondGT;
       break;
+    case kCondB:
+      false_high_cond = kCondA;
+      break;
+    case kCondBE:
+      true_high_cond = kCondB;
+      break;
+    case kCondA:
+      false_high_cond = kCondB;
+      break;
+    case kCondAE:
+      true_high_cond = kCondA;
+      break;
   }
 
   if (right.IsConstant()) {
@@ -1101,12 +1124,12 @@ void InstructionCodeGeneratorX86::GenerateLongComparesAndJumps(HCondition* cond,
       __ cmpl(left_high, Immediate(val_high));
     }
     if (if_cond == kCondNE) {
-      __ j(X86SignedCondition(true_high_cond), true_label);
+      __ j(X86Condition(true_high_cond), true_label);
     } else if (if_cond == kCondEQ) {
-      __ j(X86SignedCondition(false_high_cond), false_label);
+      __ j(X86Condition(false_high_cond), false_label);
     } else {
-      __ j(X86SignedCondition(true_high_cond), true_label);
-      __ j(X86SignedCondition(false_high_cond), false_label);
+      __ j(X86Condition(true_high_cond), true_label);
+      __ j(X86Condition(false_high_cond), false_label);
     }
     // Must be equal high, so compare the lows.
     if (val_low == 0) {
@@ -1120,12 +1143,12 @@ void InstructionCodeGeneratorX86::GenerateLongComparesAndJumps(HCondition* cond,
 
     __ cmpl(left_high, right_high);
     if (if_cond == kCondNE) {
-      __ j(X86SignedCondition(true_high_cond), true_label);
+      __ j(X86Condition(true_high_cond), true_label);
     } else if (if_cond == kCondEQ) {
-      __ j(X86SignedCondition(false_high_cond), false_label);
+      __ j(X86Condition(false_high_cond), false_label);
     } else {
-      __ j(X86SignedCondition(true_high_cond), true_label);
-      __ j(X86SignedCondition(false_high_cond), false_label);
+      __ j(X86Condition(true_high_cond), true_label);
+      __ j(X86Condition(false_high_cond), false_label);
     }
     // Must be equal high, so compare the lows.
     __ cmpl(left_low, right_low);
@@ -1214,7 +1237,7 @@ void InstructionCodeGeneratorX86::GenerateTestAndBranch(HInstruction* instructio
         }
         __ j(kNotEqual, true_target);
       } else {
-        __ j(X86SignedCondition(cond->AsCondition()->GetCondition()), true_target);
+        __ j(X86Condition(cond->AsCondition()->GetCondition()), true_target);
       }
     } else {
       // Condition has not been materialized, use its inputs as the
@@ -1247,7 +1270,7 @@ void InstructionCodeGeneratorX86::GenerateTestAndBranch(HInstruction* instructio
       } else {
         __ cmpl(lhs.AsRegister<Register>(), Address(ESP, rhs.GetStackIndex()));
       }
-      __ j(X86SignedCondition(cond->AsCondition()->GetCondition()), true_target);
+      __ j(X86Condition(cond->AsCondition()->GetCondition()), true_target);
     }
   }
   if (false_target != nullptr) {
@@ -1405,7 +1428,7 @@ void InstructionCodeGeneratorX86::VisitCondition(HCondition* cond) {
       } else {
         __ cmpl(lhs.AsRegister<Register>(), Address(ESP, rhs.GetStackIndex()));
       }
-      __ setb(X86SignedCondition(cond->GetCondition()), reg);
+      __ setb(X86Condition(cond->GetCondition()), reg);
       return;
     }
     case Primitive::kPrimLong:
@@ -1483,6 +1506,38 @@ void InstructionCodeGeneratorX86::VisitGreaterThanOrEqual(HGreaterThanOrEqual* c
   VisitCondition(comp);
 }
 
+void LocationsBuilderX86::VisitBelow(HBelow* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorX86::VisitBelow(HBelow* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderX86::VisitBelowOrEqual(HBelowOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorX86::VisitBelowOrEqual(HBelowOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderX86::VisitAbove(HAbove* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorX86::VisitAbove(HAbove* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderX86::VisitAboveOrEqual(HAboveOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorX86::VisitAboveOrEqual(HAboveOrEqual* comp) {
+  VisitCondition(comp);
+}
+
 void LocationsBuilderX86::VisitIntConstant(HIntConstant* constant) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(constant, LocationSummary::kNoCall);
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 21c3fb89c0..5757787f98 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -452,11 +452,16 @@ inline Condition X86_64IntegerCondition(IfCondition cond) {
     case kCondLE: return kLessEqual;
     case kCondGT: return kGreater;
     case kCondGE: return kGreaterEqual;
+    case kCondB:  return kBelow;
+    case kCondBE: return kBelowEqual;
+    case kCondA:  return kAbove;
+    case kCondAE: return kAboveEqual;
   }
   LOG(FATAL) << "Unreachable";
   UNREACHABLE();
 }
 
+// Maps FP condition to x86_64 name.
 inline Condition X86_64FPCondition(IfCondition cond) {
   switch (cond) {
     case kCondEQ: return kEqual;
@@ -465,6 +470,7 @@ inline Condition X86_64FPCondition(IfCondition cond) {
     case kCondLE: return kBelowEqual;
     case kCondGT: return kAbove;
     case kCondGE: return kAboveEqual;
+    default:      break;  // should not happen
   };
   LOG(FATAL) << "Unreachable";
   UNREACHABLE();
@@ -1477,6 +1483,38 @@ void InstructionCodeGeneratorX86_64::VisitGreaterThanOrEqual(HGreaterThanOrEqual
   VisitCondition(comp);
 }
 
+void LocationsBuilderX86_64::VisitBelow(HBelow* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorX86_64::VisitBelow(HBelow* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderX86_64::VisitBelowOrEqual(HBelowOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorX86_64::VisitBelowOrEqual(HBelowOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderX86_64::VisitAbove(HAbove* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorX86_64::VisitAbove(HAbove* comp) {
+  VisitCondition(comp);
+}
+
+void LocationsBuilderX86_64::VisitAboveOrEqual(HAboveOrEqual* comp) {
+  VisitCondition(comp);
+}
+
+void InstructionCodeGeneratorX86_64::VisitAboveOrEqual(HAboveOrEqual* comp) {
+  VisitCondition(comp);
+}
+
 void LocationsBuilderX86_64::VisitCompare(HCompare* compare) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(compare, LocationSummary::kNoCall);
diff --git a/compiler/optimizing/codegen_test.cc b/compiler/optimizing/codegen_test.cc
index 22f227c56a..fe5af2fc5e 100644
--- a/compiler/optimizing/codegen_test.cc
+++ b/compiler/optimizing/codegen_test.cc
@@ -761,4 +761,130 @@ TEST(CodegenTest, ReturnDivInt2Addr) {
   TestCode(data, true, 2);
 }
 
+// Helper method.
+static void TestComparison(IfCondition condition, int64_t i, int64_t j, Primitive::Type type) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = CreateGraph(&allocator);
+
+  HBasicBlock* entry_block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry_block);
+  graph->SetEntryBlock(entry_block);
+  entry_block->AddInstruction(new (&allocator) HGoto());
+
+  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+
+  HBasicBlock* exit_block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(exit_block);
+  graph->SetExitBlock(exit_block);
+  exit_block->AddInstruction(new (&allocator) HExit());
+
+  entry_block->AddSuccessor(block);
+  block->AddSuccessor(exit_block);
+
+  HInstruction* op1;
+  HInstruction* op2;
+  if (type == Primitive::kPrimInt) {
+    op1 = graph->GetIntConstant(i);
+    op2 = graph->GetIntConstant(j);
+  } else {
+    DCHECK_EQ(type, Primitive::kPrimLong);
+    op1 = graph->GetLongConstant(i);
+    op2 = graph->GetLongConstant(j);
+  }
+
+  HInstruction* comparison = nullptr;
+  bool expected_result = false;
+  const uint64_t x = i;
+  const uint64_t y = j;
+  switch (condition) {
+    case kCondEQ:
+      comparison = new (&allocator) HEqual(op1, op2);
+      expected_result = (i == j);
+      break;
+    case kCondNE:
+      comparison = new (&allocator) HNotEqual(op1, op2);
+      expected_result = (i != j);
+      break;
+    case kCondLT:
+      comparison = new (&allocator) HLessThan(op1, op2);
+      expected_result = (i < j);
+      break;
+    case kCondLE:
+      comparison = new (&allocator) HLessThanOrEqual(op1, op2);
+      expected_result = (i <= j);
+      break;
+    case kCondGT:
+      comparison = new (&allocator) HGreaterThan(op1, op2);
+      expected_result = (i > j);
+      break;
+    case kCondGE:
+      comparison = new (&allocator) HGreaterThanOrEqual(op1, op2);
+      expected_result = (i >= j);
+      break;
+    case kCondB:
+      comparison = new (&allocator) HBelow(op1, op2);
+      expected_result = (x < y);
+      break;
+    case kCondBE:
+      comparison = new (&allocator) HBelowOrEqual(op1, op2);
+      expected_result = (x <= y);
+      break;
+    case kCondA:
+      comparison = new (&allocator) HAbove(op1, op2);
+      expected_result = (x > y);
+      break;
+    case kCondAE:
+      comparison = new (&allocator) HAboveOrEqual(op1, op2);
+      expected_result = (x >= y);
+      break;
+  }
+  block->AddInstruction(comparison);
+  block->AddInstruction(new (&allocator) HReturn(comparison));
+
+  auto hook_before_codegen = [](HGraph*) {
+  };
+  RunCodeOptimized(graph, hook_before_codegen, true, expected_result);
+}
+
+TEST(CodegenTest, ComparisonsInt) {
+  for (int64_t i = -1; i <= 1; i++) {
+    for (int64_t j = -1; j <= 1; j++) {
+      TestComparison(kCondEQ, i, j, Primitive::kPrimInt);
+      TestComparison(kCondNE, i, j, Primitive::kPrimInt);
+      TestComparison(kCondLT, i, j, Primitive::kPrimInt);
+      TestComparison(kCondLE, i, j, Primitive::kPrimInt);
+      TestComparison(kCondGT, i, j, Primitive::kPrimInt);
+      TestComparison(kCondGE, i, j, Primitive::kPrimInt);
+      TestComparison(kCondB,  i, j, Primitive::kPrimInt);
+      TestComparison(kCondBE, i, j, Primitive::kPrimInt);
+      TestComparison(kCondA,  i, j, Primitive::kPrimInt);
+      TestComparison(kCondAE, i, j, Primitive::kPrimInt);
+    }
+  }
+}
+
+TEST(CodegenTest, ComparisonsLong) {
+  // TODO: make MIPS work for long
+  if (kRuntimeISA == kMips || kRuntimeISA == kMips64) {
+    return;
+  }
+
+  for (int64_t i = -1; i <= 1; i++) {
+    for (int64_t j = -1; j <= 1; j++) {
+      TestComparison(kCondEQ, i, j, Primitive::kPrimLong);
+      TestComparison(kCondNE, i, j, Primitive::kPrimLong);
+      TestComparison(kCondLT, i, j, Primitive::kPrimLong);
+      TestComparison(kCondLE, i, j, Primitive::kPrimLong);
+      TestComparison(kCondGT, i, j, Primitive::kPrimLong);
+      TestComparison(kCondGE, i, j, Primitive::kPrimLong);
+      TestComparison(kCondB,  i, j, Primitive::kPrimLong);
+      TestComparison(kCondBE, i, j, Primitive::kPrimLong);
+      TestComparison(kCondA,  i, j, Primitive::kPrimLong);
+      TestComparison(kCondAE, i, j, Primitive::kPrimLong);
+    }
+  }
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index cf0f3493fd..8968a44da8 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -650,8 +650,7 @@ bool HInductionVarAnalysis::IsTaken(InductionInfo* lower_expr,
       case kCondLE: return lower_value <= upper_value;
       case kCondGT: return lower_value >  upper_value;
       case kCondGE: return lower_value >= upper_value;
-      case kCondEQ:
-      case kCondNE: LOG(FATAL) << "CONDITION UNREACHABLE";
+      default:      LOG(FATAL) << "CONDITION UNREACHABLE";
     }
   }
   return false;  // not certain, may be untaken
@@ -680,8 +679,8 @@ bool HInductionVarAnalysis::IsFinite(InductionInfo* upper_expr,
           (IsIntAndGet(upper_expr, &value) && value >= (min - stride_value - 1));
     case kCondGE:
       return (IsIntAndGet(upper_expr, &value) && value >= (min - stride_value));
-    case kCondEQ:
-    case kCondNE: LOG(FATAL) << "CONDITION UNREACHABLE";
+    default:
+      LOG(FATAL) << "CONDITION UNREACHABLE";
   }
   return false;  // not certain, may be infinite
 }
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 078d8e5194..17c851cac9 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -615,6 +615,8 @@ void InstructionSimplifierVisitor::VisitLessThanOrEqual(HLessThanOrEqual* condit
   VisitCondition(condition);
 }
 
+// TODO: unsigned comparisons too?
+
 void InstructionSimplifierVisitor::VisitCondition(HCondition* condition) {
   // Try to fold an HCompare into this HCondition.
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index c126b59bcc..4cd5133e95 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -81,12 +81,19 @@ static constexpr InvokeType kInvalidInvokeType = static_cast<InvokeType>(-1);
 static constexpr uint32_t kNoDexPc = -1;
 
 enum IfCondition {
-  kCondEQ,
-  kCondNE,
-  kCondLT,
-  kCondLE,
-  kCondGT,
-  kCondGE,
+  // All types.
+  kCondEQ,  // ==
+  kCondNE,  // !=
+  // Signed integers and floating-point numbers.
+  kCondLT,  // <
+  kCondLE,  // <=
+  kCondGT,  // >
+  kCondGE,  // >=
+  // Unsigned integers.
+  kCondB,   // <
+  kCondBE,  // <=
+  kCondA,   // >
+  kCondAE,  // >=
 };
 
 class HInstructionList : public ValueObject {
@@ -988,11 +995,15 @@ class HLoopInformationOutwardIterator : public ValueObject {
 };
 
 #define FOR_EACH_CONCRETE_INSTRUCTION_COMMON(M)                         \
+  M(Above, Condition)                                                   \
+  M(AboveOrEqual, Condition)                                            \
   M(Add, BinaryOperation)                                               \
   M(And, BinaryOperation)                                               \
   M(ArrayGet, Instruction)                                              \
   M(ArrayLength, Instruction)                                           \
   M(ArraySet, Instruction)                                              \
+  M(Below, Condition)                                                   \
+  M(BelowOrEqual, Condition)                                            \
   M(BooleanNot, UnaryOperation)                                         \
   M(BoundsCheck, Instruction)                                           \
   M(BoundType, Instruction)                                             \
@@ -2631,8 +2642,6 @@ class HEqual : public HCondition {
 
   bool IsCommutative() const OVERRIDE { return true; }
 
-  template <typename T> bool Compute(T x, T y) const { return x == y; }
-
   HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
     return GetBlock()->GetGraph()->GetIntConstant(
         Compute(x->GetValue(), y->GetValue()), GetDexPc());
@@ -2653,6 +2662,8 @@ class HEqual : public HCondition {
   }
 
  private:
+  template <typename T> bool Compute(T x, T y) const { return x == y; }
+
   DISALLOW_COPY_AND_ASSIGN(HEqual);
 };
 
@@ -2663,8 +2674,6 @@ class HNotEqual : public HCondition {
 
   bool IsCommutative() const OVERRIDE { return true; }
 
-  template <typename T> bool Compute(T x, T y) const { return x != y; }
-
   HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
     return GetBlock()->GetGraph()->GetIntConstant(
         Compute(x->GetValue(), y->GetValue()), GetDexPc());
@@ -2685,6 +2694,8 @@ class HNotEqual : public HCondition {
   }
 
  private:
+  template <typename T> bool Compute(T x, T y) const { return x != y; }
+
   DISALLOW_COPY_AND_ASSIGN(HNotEqual);
 };
 
@@ -2693,8 +2704,6 @@ class HLessThan : public HCondition {
   HLessThan(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc)
       : HCondition(first, second, dex_pc) {}
 
-  template <typename T> bool Compute(T x, T y) const { return x < y; }
-
   HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
     return GetBlock()->GetGraph()->GetIntConstant(
         Compute(x->GetValue(), y->GetValue()), GetDexPc());
@@ -2715,6 +2724,8 @@ class HLessThan : public HCondition {
   }
 
  private:
+  template <typename T> bool Compute(T x, T y) const { return x < y; }
+
   DISALLOW_COPY_AND_ASSIGN(HLessThan);
 };
 
@@ -2723,8 +2734,6 @@ class HLessThanOrEqual : public HCondition {
   HLessThanOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc)
       : HCondition(first, second, dex_pc) {}
 
-  template <typename T> bool Compute(T x, T y) const { return x <= y; }
-
   HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
     return GetBlock()->GetGraph()->GetIntConstant(
         Compute(x->GetValue(), y->GetValue()), GetDexPc());
@@ -2745,6 +2754,8 @@ class HLessThanOrEqual : public HCondition {
   }
 
  private:
+  template <typename T> bool Compute(T x, T y) const { return x <= y; }
+
   DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual);
 };
 
@@ -2753,8 +2764,6 @@ class HGreaterThan : public HCondition {
   HGreaterThan(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc)
       : HCondition(first, second, dex_pc) {}
 
-  template <typename T> bool Compute(T x, T y) const { return x > y; }
-
   HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
     return GetBlock()->GetGraph()->GetIntConstant(
         Compute(x->GetValue(), y->GetValue()), GetDexPc());
@@ -2775,6 +2784,8 @@ class HGreaterThan : public HCondition {
   }
 
  private:
+  template <typename T> bool Compute(T x, T y) const { return x > y; }
+
   DISALLOW_COPY_AND_ASSIGN(HGreaterThan);
 };
 
@@ -2783,8 +2794,6 @@ class HGreaterThanOrEqual : public HCondition {
   HGreaterThanOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc)
       : HCondition(first, second, dex_pc) {}
 
-  template <typename T> bool Compute(T x, T y) const { return x >= y; }
-
   HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
     return GetBlock()->GetGraph()->GetIntConstant(
         Compute(x->GetValue(), y->GetValue()), GetDexPc());
@@ -2805,9 +2814,138 @@ class HGreaterThanOrEqual : public HCondition {
   }
 
  private:
+  template <typename T> bool Compute(T x, T y) const { return x >= y; }
+
   DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual);
 };
 
+class HBelow : public HCondition {
+ public:
+  HBelow(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc)
+      : HCondition(first, second, dex_pc) {}
+
+  HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
+    return GetBlock()->GetGraph()->GetIntConstant(
+        Compute(static_cast<uint32_t>(x->GetValue()),
+                static_cast<uint32_t>(y->GetValue())), GetDexPc());
+  }
+  HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE {
+    return GetBlock()->GetGraph()->GetIntConstant(
+        Compute(static_cast<uint64_t>(x->GetValue()),
+                static_cast<uint64_t>(y->GetValue())), GetDexPc());
+  }
+
+  DECLARE_INSTRUCTION(Below);
+
+  IfCondition GetCondition() const OVERRIDE {
+    return kCondB;
+  }
+
+  IfCondition GetOppositeCondition() const OVERRIDE {
+    return kCondAE;
+  }
+
+ private:
+  template <typename T> bool Compute(T x, T y) const { return x < y; }
+
+  DISALLOW_COPY_AND_ASSIGN(HBelow);
+};
+
+class HBelowOrEqual : public HCondition {
+ public:
+  HBelowOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc)
+      : HCondition(first, second, dex_pc) {}
+
+  HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
+    return GetBlock()->GetGraph()->GetIntConstant(
+        Compute(static_cast<uint32_t>(x->GetValue()),
+                static_cast<uint32_t>(y->GetValue())), GetDexPc());
+  }
+  HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE {
+    return GetBlock()->GetGraph()->GetIntConstant(
+        Compute(static_cast<uint64_t>(x->GetValue()),
+                static_cast<uint64_t>(y->GetValue())), GetDexPc());
+  }
+
+  DECLARE_INSTRUCTION(BelowOrEqual);
+
+  IfCondition GetCondition() const OVERRIDE {
+    return kCondBE;
+  }
+
+  IfCondition GetOppositeCondition() const OVERRIDE {
+    return kCondA;
+  }
+
+ private:
+  template <typename T> bool Compute(T x, T y) const { return x <= y; }
+
+  DISALLOW_COPY_AND_ASSIGN(HBelowOrEqual);
+};
+
+class HAbove : public HCondition {
+ public:
+  HAbove(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc)
+      : HCondition(first, second, dex_pc) {}
+
+  HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
+    return GetBlock()->GetGraph()->GetIntConstant(
+        Compute(static_cast<uint32_t>(x->GetValue()),
+                static_cast<uint32_t>(y->GetValue())), GetDexPc());
+  }
+  HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE {
+    return GetBlock()->GetGraph()->GetIntConstant(
+        Compute(static_cast<uint64_t>(x->GetValue()),
+                static_cast<uint64_t>(y->GetValue())), GetDexPc());
+  }
+
+  DECLARE_INSTRUCTION(Above);
+
+  IfCondition GetCondition() const OVERRIDE {
+    return kCondA;
+  }
+
+  IfCondition GetOppositeCondition() const OVERRIDE {
+    return kCondBE;
+  }
+
+ private:
+  template <typename T> bool Compute(T x, T y) const { return x > y; }
+
+  DISALLOW_COPY_AND_ASSIGN(HAbove);
+};
+
+class HAboveOrEqual : public HCondition {
+ public:
+  HAboveOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc)
+      : HCondition(first, second, dex_pc) {}
+
+  HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
+    return GetBlock()->GetGraph()->GetIntConstant(
+        Compute(static_cast<uint32_t>(x->GetValue()),
+                static_cast<uint32_t>(y->GetValue())), GetDexPc());
+  }
+  HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE {
+    return GetBlock()->GetGraph()->GetIntConstant(
+        Compute(static_cast<uint64_t>(x->GetValue()),
+                static_cast<uint64_t>(y->GetValue())), GetDexPc());
+  }
+
+  DECLARE_INSTRUCTION(AboveOrEqual);
+
+  IfCondition GetCondition() const OVERRIDE {
+    return kCondAE;
+  }
+
+  IfCondition GetOppositeCondition() const OVERRIDE {
+    return kCondB;
+  }
+
+ private:
+  template <typename T> bool Compute(T x, T y) const { return x >= y; }
+
+  DISALLOW_COPY_AND_ASSIGN(HAboveOrEqual);
+};
 
 // Instruction to check how two inputs compare to each other.
 // Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1.