diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 4c9c25f..54793fd 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -3221,7 +3221,7 @@
   if (rhs.IsConstant()) {
     uint64_t rot = CodeGenerator::GetInt64ValueOf(rhs.GetConstant());
     // Map all rotations to +ve. equivalents on the interval [0,63].
-    rot &= kMaxLongShiftValue;
+    rot &= kMaxLongShiftDistance;
     // For rotates over a word in size, 'pre-rotate' by 32-bits to keep rotate
     // logic below to a simple pair of binary orr.
     // (e.g. 34 bits == in_reg swap + 2 bits right.)
@@ -3374,7 +3374,7 @@
       if (second.IsRegister()) {
         Register second_reg = second.AsRegister<Register>();
         // ARM doesn't mask the shift count so we need to do it ourselves.
-        __ and_(out_reg, second_reg, ShifterOperand(kMaxIntShiftValue));
+        __ and_(out_reg, second_reg, ShifterOperand(kMaxIntShiftDistance));
         if (op->IsShl()) {
           __ Lsl(out_reg, first_reg, out_reg);
         } else if (op->IsShr()) {
@@ -3384,7 +3384,7 @@
         }
       } else {
         int32_t cst = second.GetConstant()->AsIntConstant()->GetValue();
-        uint32_t shift_value = static_cast<uint32_t>(cst & kMaxIntShiftValue);
+        uint32_t shift_value = cst & kMaxIntShiftDistance;
         if (shift_value == 0) {  // ARM does not support shifting with 0 immediate.
           __ Mov(out_reg, first_reg);
         } else if (op->IsShl()) {
@@ -3410,7 +3410,7 @@
         Register second_reg = second.AsRegister<Register>();
 
         if (op->IsShl()) {
-          __ and_(o_l, second_reg, ShifterOperand(kMaxLongShiftValue));
+          __ and_(o_l, second_reg, ShifterOperand(kMaxLongShiftDistance));
           // Shift the high part
           __ Lsl(o_h, high, o_l);
           // Shift the low part and `or` what overflew on the high part
@@ -3424,7 +3424,7 @@
           // Shift the low part
           __ Lsl(o_l, low, o_l);
         } else if (op->IsShr()) {
-          __ and_(o_h, second_reg, ShifterOperand(kMaxLongShiftValue));
+          __ and_(o_h, second_reg, ShifterOperand(kMaxLongShiftDistance));
           // Shift the low part
           __ Lsr(o_l, low, o_h);
           // Shift the high part and `or` what underflew on the low part
@@ -3438,7 +3438,7 @@
           // Shift the high part
           __ Asr(o_h, high, o_h);
         } else {
-          __ and_(o_h, second_reg, ShifterOperand(kMaxLongShiftValue));
+          __ and_(o_h, second_reg, ShifterOperand(kMaxLongShiftDistance));
           // same as Shr except we use `Lsr`s and not `Asr`s
           __ Lsr(o_l, low, o_h);
           __ rsb(temp, o_h, ShifterOperand(kArmBitsPerWord));
@@ -3454,7 +3454,7 @@
         DCHECK_NE(o_l, high);
         DCHECK_NE(o_h, low);
         int32_t cst = second.GetConstant()->AsIntConstant()->GetValue();
-        uint32_t shift_value = static_cast<uint32_t>(cst & kMaxLongShiftValue);
+        uint32_t shift_value = cst & kMaxLongShiftDistance;
         if (shift_value > 32) {
           if (op->IsShl()) {
             __ Lsl(o_h, low, shift_value - 32);
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 088dbb3..46fd852 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -1818,9 +1818,8 @@
       Register lhs = InputRegisterAt(instr, 0);
       Operand rhs = InputOperandAt(instr, 1);
       if (rhs.IsImmediate()) {
-        uint32_t shift_value = (type == Primitive::kPrimInt)
-          ? static_cast<uint32_t>(rhs.immediate() & kMaxIntShiftValue)
-          : static_cast<uint32_t>(rhs.immediate() & kMaxLongShiftValue);
+        uint32_t shift_value = rhs.immediate() &
+            (type == Primitive::kPrimInt ? kMaxIntShiftDistance : kMaxLongShiftDistance);
         if (instr->IsShl()) {
           __ Lsl(dst, lhs, shift_value);
         } else if (instr->IsShr()) {
@@ -1921,9 +1920,8 @@
   // conversion) can have a different type from the current instruction's type,
   // so we manually indicate the type.
   Register right_reg = RegisterFrom(instruction->GetLocations()->InAt(1), type);
-  int64_t shift_amount = (type == Primitive::kPrimInt)
-    ? static_cast<uint32_t>(instruction->GetShiftAmount() & kMaxIntShiftValue)
-    : static_cast<uint32_t>(instruction->GetShiftAmount() & kMaxLongShiftValue);
+  int64_t shift_amount = instruction->GetShiftAmount() &
+      (type == Primitive::kPrimInt ? kMaxIntShiftDistance : kMaxLongShiftDistance);
 
   Operand right_operand(0);
 
diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc
index 4c92063..684d89f 100644
--- a/compiler/optimizing/code_generator_mips.cc
+++ b/compiler/optimizing/code_generator_mips.cc
@@ -1455,9 +1455,8 @@
   bool use_imm = rhs_location.IsConstant();
   Register rhs_reg = use_imm ? ZERO : rhs_location.AsRegister<Register>();
   int64_t rhs_imm = use_imm ? CodeGenerator::GetInt64ValueOf(rhs_location.GetConstant()) : 0;
-  const uint32_t shift_mask = (type == Primitive::kPrimInt)
-      ? kMaxIntShiftValue
-      : kMaxLongShiftValue;
+  const uint32_t shift_mask =
+      (type == Primitive::kPrimInt) ? kMaxIntShiftDistance : kMaxLongShiftDistance;
   const uint32_t shift_value = rhs_imm & shift_mask;
   // Are the INS (Insert Bit Field) and ROTR instructions supported?
   bool has_ins_rotr = codegen_->GetInstructionSetFeatures().IsMipsIsaRevGreaterThanEqual2();
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index 955c9a4..0276a07 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -1208,9 +1208,8 @@
       }
 
       if (use_imm) {
-        uint32_t shift_value = (type == Primitive::kPrimInt)
-          ? static_cast<uint32_t>(rhs_imm & kMaxIntShiftValue)
-          : static_cast<uint32_t>(rhs_imm & kMaxLongShiftValue);
+        uint32_t shift_value = rhs_imm &
+            (type == Primitive::kPrimInt ? kMaxIntShiftDistance : kMaxLongShiftDistance);
 
         if (shift_value == 0) {
           if (dst != lhs) {
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index fb3216c..3123c8b 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -3775,7 +3775,7 @@
           __ shrl(first_reg, second_reg);
         }
       } else {
-        int32_t shift = second.GetConstant()->AsIntConstant()->GetValue() & kMaxIntShiftValue;
+        int32_t shift = second.GetConstant()->AsIntConstant()->GetValue() & kMaxIntShiftDistance;
         if (shift == 0) {
           return;
         }
@@ -3803,7 +3803,7 @@
         }
       } else {
         // Shift by a constant.
-        int shift = second.GetConstant()->AsIntConstant()->GetValue() & kMaxLongShiftValue;
+        int32_t shift = second.GetConstant()->AsIntConstant()->GetValue() & kMaxLongShiftDistance;
         // Nothing to do if the shift is 0, as the input is already the output.
         if (shift != 0) {
           if (op->IsShl()) {
@@ -3960,7 +3960,7 @@
       Register second_reg = second.AsRegister<Register>();
       __ rorl(first_reg, second_reg);
     } else {
-      Immediate imm(second.GetConstant()->AsIntConstant()->GetValue() & kMaxIntShiftValue);
+      Immediate imm(second.GetConstant()->AsIntConstant()->GetValue() & kMaxIntShiftDistance);
       __ rorl(first_reg, imm);
     }
     return;
@@ -3981,7 +3981,7 @@
     __ cmovl(kNotEqual, first_reg_hi, first_reg_lo);
     __ cmovl(kNotEqual, first_reg_lo, temp_reg);
   } else {
-    int32_t shift_amt = CodeGenerator::GetInt64ValueOf(second.GetConstant()) & kMaxLongShiftValue;
+    int32_t shift_amt = second.GetConstant()->AsIntConstant()->GetValue() & kMaxLongShiftDistance;
     if (shift_amt == 0) {
       // Already fine.
       return;
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 7648f61..b3b98be 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -3799,7 +3799,7 @@
           __ shrl(first_reg, second_reg);
         }
       } else {
-        Immediate imm(second.GetConstant()->AsIntConstant()->GetValue() & kMaxIntShiftValue);
+        Immediate imm(second.GetConstant()->AsIntConstant()->GetValue() & kMaxIntShiftDistance);
         if (op->IsShl()) {
           __ shll(first_reg, imm);
         } else if (op->IsShr()) {
@@ -3821,7 +3821,7 @@
           __ shrq(first_reg, second_reg);
         }
       } else {
-        Immediate imm(second.GetConstant()->AsIntConstant()->GetValue() & kMaxLongShiftValue);
+        Immediate imm(second.GetConstant()->AsIntConstant()->GetValue() & kMaxLongShiftDistance);
         if (op->IsShl()) {
           __ shlq(first_reg, imm);
         } else if (op->IsShr()) {
@@ -3868,7 +3868,7 @@
         CpuRegister second_reg = second.AsRegister<CpuRegister>();
         __ rorl(first_reg, second_reg);
       } else {
-        Immediate imm(second.GetConstant()->AsIntConstant()->GetValue() & kMaxIntShiftValue);
+        Immediate imm(second.GetConstant()->AsIntConstant()->GetValue() & kMaxIntShiftDistance);
         __ rorl(first_reg, imm);
       }
       break;
@@ -3877,7 +3877,7 @@
         CpuRegister second_reg = second.AsRegister<CpuRegister>();
         __ rorq(first_reg, second_reg);
       } else {
-        Immediate imm(second.GetConstant()->AsIntConstant()->GetValue() & kMaxLongShiftValue);
+        Immediate imm(second.GetConstant()->AsIntConstant()->GetValue() & kMaxLongShiftDistance);
         __ rorq(first_reg, imm);
       }
       break;
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 0c22903..528fe44 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -937,9 +937,12 @@
   Primitive::Type lhs_type = op->InputAt(0)->GetType();
   Primitive::Type rhs_type = op->InputAt(1)->GetType();
   Primitive::Type result_type = op->GetType();
+
+  // Type consistency between inputs.
   if (op->IsUShr() || op->IsShr() || op->IsShl() || op->IsRor()) {
     if (Primitive::PrimitiveKind(rhs_type) != Primitive::kPrimInt) {
-      AddError(StringPrintf("Shift operation %s %d has a non-int kind second input: %s of type %s.",
+      AddError(StringPrintf("Shift/rotate operation %s %d has a non-int kind second input: "
+                            "%s of type %s.",
                             op->DebugName(), op->GetId(),
                             op->InputAt(1)->DebugName(),
                             Primitive::PrettyDescriptor(rhs_type)));
@@ -953,21 +956,38 @@
     }
   }
 
+  // Type consistency between result and input(s).
   if (op->IsCompare()) {
     if (result_type != Primitive::kPrimInt) {
       AddError(StringPrintf("Compare operation %d has a non-int result type: %s.",
                             op->GetId(),
                             Primitive::PrettyDescriptor(result_type)));
     }
-  } else {
-    // Use the first input, so that we can also make this check for shift and rotate operations.
-    if (Primitive::PrimitiveKind(result_type) != Primitive::PrimitiveKind(lhs_type)) {
-      AddError(StringPrintf("Binary operation %s %d has a result kind different "
-                            "from its input kind: %s vs %s.",
+  } else if (op->IsUShr() || op->IsShr() || op->IsShl() || op->IsRor()) {
+    // Only check the first input (value), as the second one (distance)
+    // must invariably be of kind `int`.
+    if (result_type != Primitive::PrimitiveKind(lhs_type)) {
+      AddError(StringPrintf("Shift/rotate operation %s %d has a result type different "
+                            "from its left-hand side (value) input kind: %s vs %s.",
                             op->DebugName(), op->GetId(),
                             Primitive::PrettyDescriptor(result_type),
                             Primitive::PrettyDescriptor(lhs_type)));
     }
+  } else {
+    if (Primitive::PrimitiveKind(result_type) != Primitive::PrimitiveKind(lhs_type)) {
+      AddError(StringPrintf("Binary operation %s %d has a result kind different "
+                            "from its left-hand side input kind: %s vs %s.",
+                            op->DebugName(), op->GetId(),
+                            Primitive::PrettyDescriptor(result_type),
+                            Primitive::PrettyDescriptor(lhs_type)));
+    }
+    if (Primitive::PrimitiveKind(result_type) != Primitive::PrimitiveKind(rhs_type)) {
+      AddError(StringPrintf("Binary operation %s %d has a result kind different "
+                            "from its right-hand side input kind: %s vs %s.",
+                            op->DebugName(), op->GetId(),
+                            Primitive::PrettyDescriptor(result_type),
+                            Primitive::PrettyDescriptor(rhs_type)));
+    }
   }
 }
 
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 4f1e90c..3a9d242 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -382,6 +382,8 @@
   void VisitArraySet(HArraySet* array_set) OVERRIDE {
     StartAttributeStream("value_can_be_null") << std::boolalpha
         << array_set->GetValueCanBeNull() << std::noboolalpha;
+    StartAttributeStream("needs_type_check") << std::boolalpha
+        << array_set->NeedsTypeCheck() << std::noboolalpha;
   }
 
   void VisitCompare(HCompare* compare) OVERRIDE {
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 820c696..5b263b3 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -240,8 +240,9 @@
 
   if (input_cst != nullptr) {
     int64_t cst = Int64FromConstant(input_cst);
-    int64_t mask =
-        (input_other->GetType() == Primitive::kPrimLong) ? kMaxLongShiftValue : kMaxIntShiftValue;
+    int64_t mask = (input_other->GetType() == Primitive::kPrimLong)
+        ? kMaxLongShiftDistance
+        : kMaxIntShiftDistance;
     if ((cst & mask) == 0) {
       // Replace code looking like
       //    SHL dst, src, 0
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index c83340b..e08e8fb 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -162,7 +162,7 @@
   // (6) Compute the dominance information and the reverse post order.
   ComputeDominanceInformation();
 
-  // (7) Analyze loops discover through back edge analysis, and
+  // (7) Analyze loops discovered through back edge analysis, and
   //     set the loop information on each block.
   GraphAnalysisResult result = AnalyzeLoops();
   if (result != kAnalysisSuccess) {
@@ -247,7 +247,7 @@
   }
 
   // Populate `dominated_blocks_` information after computing all dominators.
-  // The potential presence of irreducible loops require to do it after.
+  // The potential presence of irreducible loops requires to do it after.
   for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     if (!block->IsEntryBlock()) {
@@ -460,7 +460,7 @@
     if (block->IsLoopHeader()) {
       SimplifyLoop(block);
     } else if (!block->IsEntryBlock() && block->GetFirstInstruction()->IsSuspendCheck()) {
-      // We are being called by the dead code elimiation pass, and what used to be
+      // We are being called by the dead code elimination pass, and what used to be
       // a loop got dismantled. Just remove the suspend check.
       block->RemoveInstruction(block->GetFirstInstruction());
     }
@@ -2373,7 +2373,7 @@
   env_uses_.Clear();
 }
 
-// Returns an instruction with the opposite boolean value from 'cond'.
+// Returns an instruction with the opposite Boolean value from 'cond'.
 HInstruction* HGraph::InsertOppositeCondition(HInstruction* cond, HInstruction* cursor) {
   ArenaAllocator* allocator = GetArena();
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index a09ad00..521bd14 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -72,8 +72,10 @@
 static const int kDefaultNumberOfDominatedBlocks = 1;
 static const int kDefaultNumberOfBackEdges = 1;
 
-static constexpr uint32_t kMaxIntShiftValue = 0x1f;
-static constexpr uint64_t kMaxLongShiftValue = 0x3f;
+// The maximum (meaningful) distance (31) that can be used in an integer shift/rotate operation.
+static constexpr int32_t kMaxIntShiftDistance = 0x1f;
+// The maximum (meaningful) distance (63) that can be used in a long shift/rotate operation.
+static constexpr int32_t kMaxLongShiftDistance = 0x3f;
 
 static constexpr uint32_t kUnknownFieldIndex = static_cast<uint32_t>(-1);
 static constexpr uint16_t kUnknownClassDefIndex = static_cast<uint16_t>(-1);
@@ -3442,10 +3444,8 @@
                          SideEffectsForArchRuntimeCalls(comparison_type),
                          dex_pc) {
     SetPackedField<ComparisonBiasField>(bias);
-    if (kIsDebugBuild) {
-      DCHECK_EQ(comparison_type, Primitive::PrimitiveKind(first->GetType()));
-      DCHECK_EQ(comparison_type, Primitive::PrimitiveKind(second->GetType()));
-    }
+    DCHECK_EQ(comparison_type, Primitive::PrimitiveKind(first->GetType()));
+    DCHECK_EQ(comparison_type, Primitive::PrimitiveKind(second->GetType()));
   }
 
   template <typename T>
@@ -4447,37 +4447,39 @@
 class HShl : public HBinaryOperation {
  public:
   HShl(Primitive::Type result_type,
-       HInstruction* left,
-       HInstruction* right,
+       HInstruction* value,
+       HInstruction* distance,
        uint32_t dex_pc = kNoDexPc)
-      : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {}
-
-  template <typename T, typename U, typename V>
-  T Compute(T x, U y, V max_shift_value) const {
-    static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value,
-                  "V is not the unsigned integer type corresponding to T");
-    return x << (y & max_shift_value);
+      : HBinaryOperation(result_type, value, distance, SideEffects::None(), dex_pc) {
+    DCHECK_EQ(result_type, Primitive::PrimitiveKind(value->GetType()));
+    DCHECK_EQ(Primitive::kPrimInt, Primitive::PrimitiveKind(distance->GetType()));
   }
 
-  HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
+  template <typename T>
+  T Compute(T value, int32_t distance, int32_t max_shift_distance) const {
+    return value << (distance & max_shift_distance);
+  }
+
+  HConstant* Evaluate(HIntConstant* value, HIntConstant* distance) const OVERRIDE {
     return GetBlock()->GetGraph()->GetIntConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue), GetDexPc());
+        Compute(value->GetValue(), distance->GetValue(), kMaxIntShiftDistance), GetDexPc());
   }
-  HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE {
+  HConstant* Evaluate(HLongConstant* value, HIntConstant* distance) const OVERRIDE {
     return GetBlock()->GetGraph()->GetLongConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc());
+        Compute(value->GetValue(), distance->GetValue(), kMaxLongShiftDistance), GetDexPc());
   }
-  HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE {
-    return GetBlock()->GetGraph()->GetLongConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc());
+  HConstant* Evaluate(HLongConstant* value ATTRIBUTE_UNUSED,
+                      HLongConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
+    LOG(FATAL) << DebugName() << " is not defined for the (long, long) case.";
+    UNREACHABLE();
   }
-  HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED,
-                      HFloatConstant* y ATTRIBUTE_UNUSED) const OVERRIDE {
+  HConstant* Evaluate(HFloatConstant* value ATTRIBUTE_UNUSED,
+                      HFloatConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
     LOG(FATAL) << DebugName() << " is not defined for float values";
     UNREACHABLE();
   }
-  HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED,
-                      HDoubleConstant* y ATTRIBUTE_UNUSED) const OVERRIDE {
+  HConstant* Evaluate(HDoubleConstant* value ATTRIBUTE_UNUSED,
+                      HDoubleConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
     LOG(FATAL) << DebugName() << " is not defined for double values";
     UNREACHABLE();
   }
@@ -4491,37 +4493,39 @@
 class HShr : public HBinaryOperation {
  public:
   HShr(Primitive::Type result_type,
-       HInstruction* left,
-       HInstruction* right,
+       HInstruction* value,
+       HInstruction* distance,
        uint32_t dex_pc = kNoDexPc)
-      : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {}
-
-  template <typename T, typename U, typename V>
-  T Compute(T x, U y, V max_shift_value) const {
-    static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value,
-                  "V is not the unsigned integer type corresponding to T");
-    return x >> (y & max_shift_value);
+      : HBinaryOperation(result_type, value, distance, SideEffects::None(), dex_pc) {
+    DCHECK_EQ(result_type, Primitive::PrimitiveKind(value->GetType()));
+    DCHECK_EQ(Primitive::kPrimInt, Primitive::PrimitiveKind(distance->GetType()));
   }
 
-  HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
+  template <typename T>
+  T Compute(T value, int32_t distance, int32_t max_shift_distance) const {
+    return value >> (distance & max_shift_distance);
+  }
+
+  HConstant* Evaluate(HIntConstant* value, HIntConstant* distance) const OVERRIDE {
     return GetBlock()->GetGraph()->GetIntConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue), GetDexPc());
+        Compute(value->GetValue(), distance->GetValue(), kMaxIntShiftDistance), GetDexPc());
   }
-  HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE {
+  HConstant* Evaluate(HLongConstant* value, HIntConstant* distance) const OVERRIDE {
     return GetBlock()->GetGraph()->GetLongConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc());
+        Compute(value->GetValue(), distance->GetValue(), kMaxLongShiftDistance), GetDexPc());
   }
-  HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE {
-    return GetBlock()->GetGraph()->GetLongConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc());
+  HConstant* Evaluate(HLongConstant* value ATTRIBUTE_UNUSED,
+                      HLongConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
+    LOG(FATAL) << DebugName() << " is not defined for the (long, long) case.";
+    UNREACHABLE();
   }
-  HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED,
-                      HFloatConstant* y ATTRIBUTE_UNUSED) const OVERRIDE {
+  HConstant* Evaluate(HFloatConstant* value ATTRIBUTE_UNUSED,
+                      HFloatConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
     LOG(FATAL) << DebugName() << " is not defined for float values";
     UNREACHABLE();
   }
-  HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED,
-                      HDoubleConstant* y ATTRIBUTE_UNUSED) const OVERRIDE {
+  HConstant* Evaluate(HDoubleConstant* value ATTRIBUTE_UNUSED,
+                      HDoubleConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
     LOG(FATAL) << DebugName() << " is not defined for double values";
     UNREACHABLE();
   }
@@ -4535,38 +4539,41 @@
 class HUShr : public HBinaryOperation {
  public:
   HUShr(Primitive::Type result_type,
-        HInstruction* left,
-        HInstruction* right,
+        HInstruction* value,
+        HInstruction* distance,
         uint32_t dex_pc = kNoDexPc)
-      : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {}
-
-  template <typename T, typename U, typename V>
-  T Compute(T x, U y, V max_shift_value) const {
-    static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value,
-                  "V is not the unsigned integer type corresponding to T");
-    V ux = static_cast<V>(x);
-    return static_cast<T>(ux >> (y & max_shift_value));
+      : HBinaryOperation(result_type, value, distance, SideEffects::None(), dex_pc) {
+    DCHECK_EQ(result_type, Primitive::PrimitiveKind(value->GetType()));
+    DCHECK_EQ(Primitive::kPrimInt, Primitive::PrimitiveKind(distance->GetType()));
   }
 
-  HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
+  template <typename T>
+  T Compute(T value, int32_t distance, int32_t max_shift_distance) const {
+    typedef typename std::make_unsigned<T>::type V;
+    V ux = static_cast<V>(value);
+    return static_cast<T>(ux >> (distance & max_shift_distance));
+  }
+
+  HConstant* Evaluate(HIntConstant* value, HIntConstant* distance) const OVERRIDE {
     return GetBlock()->GetGraph()->GetIntConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue), GetDexPc());
+        Compute(value->GetValue(), distance->GetValue(), kMaxIntShiftDistance), GetDexPc());
   }
-  HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE {
+  HConstant* Evaluate(HLongConstant* value, HIntConstant* distance) const OVERRIDE {
     return GetBlock()->GetGraph()->GetLongConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc());
+        Compute(value->GetValue(), distance->GetValue(), kMaxLongShiftDistance), GetDexPc());
   }
-  HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE {
-    return GetBlock()->GetGraph()->GetLongConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc());
+  HConstant* Evaluate(HLongConstant* value ATTRIBUTE_UNUSED,
+                      HLongConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
+    LOG(FATAL) << DebugName() << " is not defined for the (long, long) case.";
+    UNREACHABLE();
   }
-  HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED,
-                      HFloatConstant* y ATTRIBUTE_UNUSED) const OVERRIDE {
+  HConstant* Evaluate(HFloatConstant* value ATTRIBUTE_UNUSED,
+                      HFloatConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
     LOG(FATAL) << DebugName() << " is not defined for float values";
     UNREACHABLE();
   }
-  HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED,
-                      HDoubleConstant* y ATTRIBUTE_UNUSED) const OVERRIDE {
+  HConstant* Evaluate(HDoubleConstant* value ATTRIBUTE_UNUSED,
+                      HDoubleConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
     LOG(FATAL) << DebugName() << " is not defined for double values";
     UNREACHABLE();
   }
@@ -4692,45 +4699,43 @@
  public:
   HRor(Primitive::Type result_type, HInstruction* value, HInstruction* distance)
     : HBinaryOperation(result_type, value, distance) {
-    if (kIsDebugBuild) {
-      DCHECK_EQ(result_type, Primitive::PrimitiveKind(value->GetType()));
-      DCHECK_EQ(Primitive::kPrimInt, Primitive::PrimitiveKind(distance->GetType()));
-    }
+    DCHECK_EQ(result_type, Primitive::PrimitiveKind(value->GetType()));
+    DCHECK_EQ(Primitive::kPrimInt, Primitive::PrimitiveKind(distance->GetType()));
   }
 
-  template <typename T, typename U, typename V>
-  T Compute(T x, U y, V max_shift_value) const {
-    static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value,
-                  "V is not the unsigned integer type corresponding to T");
-    V ux = static_cast<V>(x);
-    if ((y & max_shift_value) == 0) {
+  template <typename T>
+  T Compute(T value, int32_t distance, int32_t max_shift_value) const {
+    typedef typename std::make_unsigned<T>::type V;
+    V ux = static_cast<V>(value);
+    if ((distance & max_shift_value) == 0) {
       return static_cast<T>(ux);
     } else {
       const V reg_bits = sizeof(T) * 8;
-      return static_cast<T>(ux >> (y & max_shift_value)) |
-                           (x << (reg_bits - (y & max_shift_value)));
+      return static_cast<T>(ux >> (distance & max_shift_value)) |
+                           (value << (reg_bits - (distance & max_shift_value)));
     }
   }
 
-  HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE {
+  HConstant* Evaluate(HIntConstant* value, HIntConstant* distance) const OVERRIDE {
     return GetBlock()->GetGraph()->GetIntConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue), GetDexPc());
+        Compute(value->GetValue(), distance->GetValue(), kMaxIntShiftDistance), GetDexPc());
   }
-  HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE {
+  HConstant* Evaluate(HLongConstant* value, HIntConstant* distance) const OVERRIDE {
     return GetBlock()->GetGraph()->GetLongConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc());
+        Compute(value->GetValue(), distance->GetValue(), kMaxLongShiftDistance), GetDexPc());
   }
-  HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE {
-    return GetBlock()->GetGraph()->GetLongConstant(
-        Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc());
+  HConstant* Evaluate(HLongConstant* value ATTRIBUTE_UNUSED,
+                      HLongConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
+    LOG(FATAL) << DebugName() << " is not defined for the (long, long) case.";
+    UNREACHABLE();
   }
-  HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED,
-                      HFloatConstant* y ATTRIBUTE_UNUSED) const OVERRIDE {
+  HConstant* Evaluate(HFloatConstant* value ATTRIBUTE_UNUSED,
+                      HFloatConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
     LOG(FATAL) << DebugName() << " is not defined for float values";
     UNREACHABLE();
   }
-  HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED,
-                      HDoubleConstant* y ATTRIBUTE_UNUSED) const OVERRIDE {
+  HConstant* Evaluate(HDoubleConstant* value ATTRIBUTE_UNUSED,
+                      HDoubleConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE {
     LOG(FATAL) << DebugName() << " is not defined for double values";
     UNREACHABLE();
   }
diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc
index 0ad104e..fc72727 100644
--- a/compiler/optimizing/prepare_for_register_allocation.cc
+++ b/compiler/optimizing/prepare_for_register_allocation.cc
@@ -47,6 +47,19 @@
   bound_type->GetBlock()->RemoveInstruction(bound_type);
 }
 
+void PrepareForRegisterAllocation::VisitArraySet(HArraySet* instruction) {
+  HInstruction* value = instruction->GetValue();
+  // PrepareForRegisterAllocation::VisitBoundType may have replaced a
+  // BoundType (as value input of this ArraySet) with a NullConstant.
+  // If so, this ArraySet no longer needs a type check.
+  if (value->IsNullConstant()) {
+    DCHECK_EQ(value->GetType(), Primitive::kPrimNot);
+    if (instruction->NeedsTypeCheck()) {
+      instruction->ClearNeedsTypeCheck();
+    }
+  }
+}
+
 void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) {
   // Try to find a static invoke or a new-instance from which this check originated.
   HInstruction* implicit_clinit = nullptr;
diff --git a/compiler/optimizing/prepare_for_register_allocation.h b/compiler/optimizing/prepare_for_register_allocation.h
index c90724c..a679148 100644
--- a/compiler/optimizing/prepare_for_register_allocation.h
+++ b/compiler/optimizing/prepare_for_register_allocation.h
@@ -40,6 +40,7 @@
   void VisitDivZeroCheck(HDivZeroCheck* check) OVERRIDE;
   void VisitBoundsCheck(HBoundsCheck* check) OVERRIDE;
   void VisitBoundType(HBoundType* bound_type) OVERRIDE;
+  void VisitArraySet(HArraySet* instruction) OVERRIDE;
   void VisitClinitCheck(HClinitCheck* check) OVERRIDE;
   void VisitCondition(HCondition* condition) OVERRIDE;
   void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE;
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 34d9af1..44bede8 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1927,7 +1927,13 @@
         BitVector* live = liveness_.GetLiveInSet(*block);
         for (uint32_t idx : live->Indexes()) {
           LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval();
-          DCHECK(!interval->GetSiblingAt(block->GetLifetimeStart())->HasRegister());
+          LiveInterval* sibling = interval->GetSiblingAt(block->GetLifetimeStart());
+          // `GetSiblingAt` returns the sibling that contains a position, but there could be
+          // a lifetime hole in it. `CoversSlow` returns whether the interval is live at that
+          // position.
+          if (sibling->CoversSlow(block->GetLifetimeStart())) {
+            DCHECK(!sibling->HasRegister());
+          }
         }
       }
     } else {
diff --git a/test/588-checker-irreducible-lifetime-hole/expected.txt b/test/588-checker-irreducible-lifetime-hole/expected.txt
new file mode 100644
index 0000000..d81cc07
--- /dev/null
+++ b/test/588-checker-irreducible-lifetime-hole/expected.txt
@@ -0,0 +1 @@
+42
diff --git a/test/588-checker-irreducible-lifetime-hole/info.txt b/test/588-checker-irreducible-lifetime-hole/info.txt
new file mode 100644
index 0000000..a2861a9
--- /dev/null
+++ b/test/588-checker-irreducible-lifetime-hole/info.txt
@@ -0,0 +1,3 @@
+Regression test for optimizing that used to have a too
+strong DCHECK in the presence of a combination of irreducible loops
+and try/catch.
diff --git a/test/588-checker-irreducible-lifetime-hole/smali/IrreducibleLoop.smali b/test/588-checker-irreducible-lifetime-hole/smali/IrreducibleLoop.smali
new file mode 100644
index 0000000..207c77e
--- /dev/null
+++ b/test/588-checker-irreducible-lifetime-hole/smali/IrreducibleLoop.smali
@@ -0,0 +1,71 @@
+# Copyright (C) 2016 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+.class public LIrreducibleLoop;
+
+.super Ljava/lang/Object;
+
+## CHECK-START-X86: int IrreducibleLoop.simpleLoop(int) dead_code_elimination (before)
+## CHECK-DAG: <<Method:(i|j)\d+>> CurrentMethod
+## CHECK-DAG: <<Constant:i\d+>>   IntConstant 42
+## CHECK-DAG:                     Goto irreducible:true
+## CHECK-DAG:                     InvokeStaticOrDirect [<<Constant>>,<<Method>>] loop:none
+## CHECK-DAG:                     InvokeStaticOrDirect [{{i\d+}},<<Method>>] loop:none
+.method public static simpleLoop(I)I
+   .registers 3
+   const/16 v0, 42
+   invoke-static {v0}, LIrreducibleLoop;->$noinline$m(I)V
+   if-eqz p0, :b22
+   goto :b34
+
+   :b34
+   goto :b20
+
+   :b20
+   if-nez p0, :b45
+   goto :b46
+
+   :b46
+   goto :b21
+
+   :b21
+   goto :b34
+
+   :b22
+   :try_start
+   div-int v0, v0, v0
+   :try_end
+   .catchall {:try_start .. :try_end} :b34
+   goto :b20
+
+   :b45
+   invoke-static {v0}, LIrreducibleLoop;->$noinline$m(I)V
+   goto :b26
+
+   :b26
+   return v0
+.end method
+
+.method public static $noinline$m(I)V
+   .registers 3
+   const/16 v0, 0
+   sget-boolean v1,LIrreducibleLoop;->doThrow:Z
+   if-eqz v1, :exit
+   # Prevent inlining.
+   throw v0
+   :exit
+   return-void
+.end method
+
+.field public static doThrow:Z
diff --git a/test/588-checker-irreducible-lifetime-hole/src/Main.java b/test/588-checker-irreducible-lifetime-hole/src/Main.java
new file mode 100644
index 0000000..94e3357
--- /dev/null
+++ b/test/588-checker-irreducible-lifetime-hole/src/Main.java
@@ -0,0 +1,29 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.lang.reflect.Method;
+
+public class Main {
+  // Workaround for b/18051191.
+  class InnerClass {}
+
+  public static void main(String[] args) throws Exception {
+    Class<?> c = Class.forName("IrreducibleLoop");
+    Method m = c.getMethod("simpleLoop", int.class);
+    Object[] arguments = { 42 };
+    System.out.println(m.invoke(null, arguments));
+  }
+}
diff --git a/test/590-checker-array-set-null-regression/expected.txt b/test/590-checker-array-set-null-regression/expected.txt
new file mode 100644
index 0000000..b0aad4d
--- /dev/null
+++ b/test/590-checker-array-set-null-regression/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/590-checker-array-set-null-regression/info.txt b/test/590-checker-array-set-null-regression/info.txt
new file mode 100644
index 0000000..fe173a3
--- /dev/null
+++ b/test/590-checker-array-set-null-regression/info.txt
@@ -0,0 +1,11 @@
+Regression test for art::PrepareForRegisterAllocation, which replaces
+
+  ArraySet[array, index, BoundType[NullConstant]]
+
+with
+
+  ArraySet[array, index, NullConstant]
+
+but used to forget to remove the "need for a type check" bit in the
+ArraySet, thus failing "!may_need_runtime_call_for_type_check"
+assertions in code generators.
diff --git a/test/590-checker-array-set-null-regression/src/Main.java b/test/590-checker-array-set-null-regression/src/Main.java
new file mode 100644
index 0000000..792ee4e
--- /dev/null
+++ b/test/590-checker-array-set-null-regression/src/Main.java
@@ -0,0 +1,68 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class Main {
+
+  public static void main(String args[]) {
+    Element[] elements = new Element[51];
+    testArraySetCheckCastNull(elements);
+
+    System.out.println("passed");
+  }
+
+  /// CHECK-START: void Main.testArraySetCheckCastNull(Main$Element[]) builder (after)
+  /// CHECK:         <<Array:l\d+>>         ParameterValue
+  /// CHECK-DAG:     <<Index:i\d+>>         IntConstant 42
+  /// CHECK-DAG:     <<Null:l\d+>>          NullConstant
+  /// CHECK-DAG:     <<Class:l\d+>>         LoadClass
+  /// CHECK-DAG:                            CheckCast [<<Null>>,<<Class>>]
+  /// CHECK-DAG:     <<CheckedValue:l\d+>>  BoundType [<<Null>>] klass:Main$Element can_be_null:true
+  /// CHECK-DAG:     <<CheckedArray:l\d+>>  NullCheck [<<Array>>]
+  /// CHECK-DAG:     <<Length:i\d+>>        ArrayLength [<<CheckedArray>>]
+  /// CHECK-DAG:     <<CheckedIndex:i\d+>>  BoundsCheck [<<Index>>,<<Length>>]
+  /// CHECK-DAG:     <<ArraySet:v\d+>>      ArraySet [<<CheckedArray>>,<<CheckedIndex>>,<<CheckedValue>>] needs_type_check:true
+
+  /// CHECK-START: void Main.testArraySetCheckCastNull(Main$Element[]) instruction_simplifier (after)
+  /// CHECK-NOT:                            CheckCast
+
+  /// CHECK-START: void Main.testArraySetCheckCastNull(Main$Element[]) prepare_for_register_allocation (before)
+  /// CHECK:         <<Array:l\d+>>         ParameterValue
+  /// CHECK-DAG:     <<Index:i\d+>>         IntConstant 42
+  /// CHECK-DAG:     <<Null:l\d+>>          NullConstant
+  /// CHECK-DAG:     <<Class:l\d+>>         LoadClass
+  /// CHECK-DAG:     <<CheckedValue:l\d+>>  BoundType [<<Null>>]
+  /// CHECK-DAG:     <<CheckedArray:l\d+>>  NullCheck [<<Array>>]
+  /// CHECK-DAG:     <<Length:i\d+>>        ArrayLength [<<CheckedArray>>]
+  /// CHECK-DAG:     <<CheckedIndex:i\d+>>  BoundsCheck [<<Index>>,<<Length>>]
+  /// CHECK-DAG:     <<ArraySet:v\d+>>      ArraySet [<<CheckedArray>>,<<CheckedIndex>>,<<CheckedValue>>] needs_type_check:true
+
+  /// CHECK-START: void Main.testArraySetCheckCastNull(Main$Element[]) prepare_for_register_allocation (after)
+  /// CHECK:         <<Array:l\d+>>         ParameterValue
+  /// CHECK-DAG:     <<Index:i\d+>>         IntConstant 42
+  /// CHECK-DAG:     <<Null:l\d+>>          NullConstant
+  /// CHECK-DAG:     <<Class:l\d+>>         LoadClass
+  /// CHECK-DAG:     <<Length:i\d+>>        ArrayLength [<<Array>>]
+  /// CHECK-DAG:     <<ArraySet:v\d+>>      ArraySet [<<Array>>,<<Index>>,<<Null>>] needs_type_check:false
+
+  static void testArraySetCheckCastNull(Element[] elements) {
+    Object object = null;
+    Element element = (Element) object;
+    elements[42] = element;
+  }
+
+  class Element {}
+
+}