diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 4d71cb7..0b59327 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -589,12 +589,14 @@
       if (locations->RegisterContainsObject(i)) {
         locations->SetStackBit(stack_offset / kVRegSize);
       }
+      DCHECK_LT(stack_offset, GetFrameSize() - FrameEntrySpillSize());
       stack_offset += SaveCoreRegister(stack_offset, i);
     }
   }
 
   for (size_t i = 0, e = GetNumberOfFloatingPointRegisters(); i < e; ++i) {
     if (register_set->ContainsFloatingPointRegister(i)) {
+      DCHECK_LT(stack_offset, GetFrameSize() - FrameEntrySpillSize());
       stack_offset += SaveFloatingPointRegister(stack_offset, i);
     }
   }
@@ -605,12 +607,14 @@
   size_t stack_offset = first_register_slot_in_slow_path_;
   for (size_t i = 0, e = GetNumberOfCoreRegisters(); i < e; ++i) {
     if (register_set->ContainsCoreRegister(i)) {
+      DCHECK_LT(stack_offset, GetFrameSize() - FrameEntrySpillSize());
       stack_offset += RestoreCoreRegister(stack_offset, i);
     }
   }
 
   for (size_t i = 0, e = GetNumberOfFloatingPointRegisters(); i < e; ++i) {
     if (register_set->ContainsFloatingPointRegister(i)) {
+      DCHECK_LT(stack_offset, GetFrameSize() - FrameEntrySpillSize());
       stack_offset += RestoreFloatingPointRegister(stack_offset, i);
     }
   }
diff --git a/compiler/optimizing/locations.h b/compiler/optimizing/locations.h
index d1555d4..e1c8e8e 100644
--- a/compiler/optimizing/locations.h
+++ b/compiler/optimizing/locations.h
@@ -391,6 +391,10 @@
     return (register_set & (1 << reg)) != 0;
   }
 
+  size_t GetNumberOfRegisters() const {
+    return __builtin_popcount(core_registers_) + __builtin_popcount(floating_point_registers_);
+  }
+
  private:
   uint32_t core_registers_;
   uint32_t floating_point_registers_;
@@ -503,6 +507,10 @@
     return &live_registers_;
   }
 
+  size_t GetNumberOfLiveRegisters() const {
+    return live_registers_.GetNumberOfRegisters();
+  }
+
   bool InputOverlapsWithOutputOrTemp(uint32_t input_index, bool is_environment) const {
     if (is_environment) return true;
     if ((input_index == 0)
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 4d6e664..2948496 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -215,9 +215,16 @@
       // By adding the following interval in the algorithm, we can compute this
       // maximum before updating locations.
       LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction);
-      interval->AddRange(position, position + 1);
-      unhandled_core_intervals_.Add(interval);
-      unhandled_fp_intervals_.Add(interval);
+      // The start of the interval must be after the position of the safepoint, so that
+      // we can just check the number of active registers at that position. Note that this
+      // will include the current interval in the computation of
+      // `maximum_number_of_live_registers`, so we need a better strategy if this becomes
+      // a problem.
+      // TODO: We could put the logic in AddSorted, to ensure the safepoint range is
+      // after all other intervals starting at that same position.
+      interval->AddRange(position + 1, position + 2);
+      AddSorted(&unhandled_core_intervals_, interval);
+      AddSorted(&unhandled_fp_intervals_, interval);
     }
   }
 
@@ -250,6 +257,7 @@
       : unhandled_fp_intervals_;
 
   DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek()));
+
   // Some instructions define their output in fixed register/stack slot. We need
   // to ensure we know these locations before doing register allocation. For a
   // given register, we create an interval that covers these locations. The register
@@ -475,6 +483,17 @@
     LiveInterval* current = unhandled_->Pop();
     DCHECK(!current->IsFixed() && !current->HasSpillSlot());
     DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() >= current->GetStart());
+
+    if (current->IsSlowPathSafepoint()) {
+      // Synthesized interval to record the maximum number of live registers
+      // at safepoints. No need to allocate a register for it.
+      // We know that current actives are all live at the safepoint (modulo
+      // the one created by the safepoint).
+      maximum_number_of_live_registers_ =
+          std::max(maximum_number_of_live_registers_, active_.Size());
+      continue;
+    }
+
     size_t position = current->GetStart();
 
     // Remember the inactive_ size here since the ones moved to inactive_ from
@@ -515,14 +534,6 @@
       }
     }
 
-    if (current->IsSlowPathSafepoint()) {
-      // Synthesized interval to record the maximum number of live registers
-      // at safepoints. No need to allocate a register for it.
-      maximum_number_of_live_registers_ =
-          std::max(maximum_number_of_live_registers_, active_.Size());
-      continue;
-    }
-
     // (4) Try to find an available register.
     bool success = TryAllocateFreeReg(current);
 
@@ -1062,6 +1073,7 @@
       switch (source.GetKind()) {
         case Location::kRegister: {
           locations->AddLiveRegister(source);
+          DCHECK_LE(locations->GetNumberOfLiveRegisters(), maximum_number_of_live_registers_);
           if (current->GetType() == Primitive::kPrimNot) {
             locations->SetRegisterBit(source.reg());
           }
diff --git a/test/430-live-register-slow-path/expected.txt b/test/430-live-register-slow-path/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/430-live-register-slow-path/expected.txt
diff --git a/test/430-live-register-slow-path/info.txt b/test/430-live-register-slow-path/info.txt
new file mode 100644
index 0000000..6f2af28
--- /dev/null
+++ b/test/430-live-register-slow-path/info.txt
@@ -0,0 +1,2 @@
+Regression test for the linear scan register allocator. It used
+to miscompute the number of live registers at a safepoint.
diff --git a/test/430-live-register-slow-path/src/Main.java b/test/430-live-register-slow-path/src/Main.java
new file mode 100644
index 0000000..b84e647
--- /dev/null
+++ b/test/430-live-register-slow-path/src/Main.java
@@ -0,0 +1,39 @@
+/*
+ * Copyright (C) 2014 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) {
+   $opt$TestSlowPath();
+  }
+
+  public static void $opt$TestSlowPath() {
+    Object[] o = bar();
+    assertEquals(0, o.length);
+    // The slowpath of the instanceof requires the live register
+    // holding `o` to be saved before going into runtime. The linear
+    // scan register allocator used to miscompute the number of
+    // live registers at a safepoint, so the place at which the register
+    // was saved was wrong.
+    doCall(o instanceof Interface[], o);
+  }
+
+  public static void assertEquals(int a, int b) {}
+  public static boolean doCall(boolean val, Object o) { return val; }
+
+  static Object[] bar() { return new Object[0]; }
+
+  static interface Interface {}
+}