--- a/js/src/jspropertycache.cpp
+++ b/js/src/jspropertycache.cpp
@@ -72,16 +72,25 @@ PropertyCache::fill(JSContext *cx, JSObj
      * from pobj (via unwatch or delete, e.g.).
      */
     if (!pobj->nativeContains(*shape)) {
         PCMETER(oddfills++);
         return JS_NO_PROP_CACHE_FILL;
     }
 
     /*
+     * Dictionary-mode objects have unique shapes, so there is no way to cache
+     * a prediction of the next shape when adding.
+     */
+    if (adding && obj->inDictionaryMode()) {
+        PCMETER(add2dictfills++);
+        return JS_NO_PROP_CACHE_FILL;
+    }
+
+    /*
      * Check for overdeep scope and prototype chain. Because resolve, getter,
      * and setter hooks can change the prototype chain using JS_SetPrototype
      * after js_LookupPropertyWithFlags has returned the nominal protoIndex,
      * we have to validate protoIndex if it is non-zero. If it is zero, then
      * we know thanks to the pobj->nativeContains test above, combined with the
      * fact that obj == pobj, that protoIndex is invariant.
      *
      * The scopeIndex can't be wrong. We require JS_SetParent calls to happen
@@ -437,16 +446,17 @@ PropertyCache::purge(JSContext *cx)
         fprintf(fp, "GC %u\n", cx->runtime->gcNumber);
 
 # define P(mem) fprintf(fp, "%11s %10lu\n", #mem, (unsigned long)mem)
         P(fills);
         P(nofills);
         P(rofills);
         P(disfills);
         P(oddfills);
+        P(add2dictfills);
         P(modfills);
         P(brandfills);
         P(noprotos);
         P(longchains);
         P(recycles);
         P(tests);
         P(pchits);
         P(protopchits);

--- a/js/src/jspropertycache.h
+++ b/js/src/jspropertycache.h
@@ -171,16 +171,17 @@ class PropertyCache
 #ifdef JS_PROPERTY_CACHE_METERING
   public:
     PropertyCacheEntry  *pctestentry;   /* entry of the last PC-based test */
     uint32              fills;          /* number of cache entry fills */
     uint32              nofills;        /* couldn't fill (e.g. default get) */
     uint32              rofills;        /* set on read-only prop can't fill */
     uint32              disfills;       /* fill attempts on disabled cache */
     uint32              oddfills;       /* fill attempt after setter deleted */
+    uint32              add2dictfills;  /* fill attempt on dictionary object */
     uint32              modfills;       /* fill that rehashed to a new entry */
     uint32              brandfills;     /* scope brandings to type structural
                                            method fills */
     uint32              noprotos;       /* resolve-returned non-proto pobj */
     uint32              longchains;     /* overlong scope and/or proto chain */
     uint32              recycles;       /* cache entries recycled by fills */
     uint32              tests;          /* cache probes */
     uint32              pchits;         /* fast-path polymorphic op hits */

--- a/js/src/jsscope.cpp
+++ b/js/src/jsscope.cpp
@@ -1102,21 +1102,22 @@ JSObject::removeProperty(JSContext *cx, 
                 for (int n = 50; --n >= 0 && aprop->parent; aprop = aprop->parent)
                     JS_ASSERT_IF(aprop != shape, nativeContains(*aprop));
 #endif
             }
         }
 
         /*
          * Remove shape from its non-circular doubly linked list, setting this
-         * object's shape first if shape is not lastProp so the updateShape(cx)
-         * after this if-else will generate a fresh shape for this scope.
+         * object's shape first so the updateShape(cx) after this if-else will
+         * generate a fresh shape for this scope. We need a fresh shape for all
+         * deletions, even of lastProp. Otherwise, a shape number can replay
+         * and caches may return get deleted DictionaryShapes! See bug 595365.
          */
-        if (shape != lastProp)
-            setOwnShape(lastProp->shape);
+        setOwnShape(lastProp->shape);
 
         Shape *oldLastProp = lastProp;
         shape->removeFromDictionary(this);
         if (table) {
             if (shape == oldLastProp) {
                 JS_ASSERT(shape->table == table);
                 JS_ASSERT(shape->parent == lastProp);
                 JS_ASSERT(shape->slotSpan >= lastProp->slotSpan);

--- a/js/src/tests/js1_8_5/regress/jstests.list
+++ b/js/src/tests/js1_8_5/regress/jstests.list
@@ -27,8 +27,10 @@ script regress-571014.js
 script regress-577648-1.js
 script regress-577648-2.js
 script regress-583429.js
 script regress-584355.js
 script regress-588339.js
 script regress-yarr-regexp.js
 script regress-592556-c35.js
 script regress-593256.js
+script regress-595365-1.js
+script regress-595365-2.js

new file mode 100644
--- /dev/null
+++ b/js/src/tests/js1_8_5/regress/regress-595365-1.js
@@ -0,0 +1,31 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/*
+ * Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/licenses/publicdomain/
+ */
+
+/*
+ * NB: this test hardcodes the value of MAX_PROPERTY_TREE_HEIGHT.
+ */
+var i = 0;
+function add0to64(o) {
+  o.p00 = ++i;o.p01 = ++i;o.p02 = ++i;o.p03 = ++i;o.p04 = ++i;o.p05 = ++i;o.p06 = ++i;o.p07 = ++i;
+  o.p10 = ++i;o.p11 = ++i;o.p12 = ++i;o.p13 = ++i;o.p14 = ++i;o.p15 = ++i;o.p16 = ++i;o.p17 = ++i;
+  o.p20 = ++i;o.p21 = ++i;o.p22 = ++i;o.p23 = ++i;o.p24 = ++i;o.p25 = ++i;o.p26 = ++i;o.p27 = ++i;
+  o.p30 = ++i;o.p31 = ++i;o.p32 = ++i;o.p33 = ++i;o.p34 = ++i;o.p35 = ++i;o.p36 = ++i;o.p37 = ++i;
+  o.p40 = ++i;o.p41 = ++i;o.p42 = ++i;o.p43 = ++i;o.p44 = ++i;o.p45 = ++i;o.p46 = ++i;o.p47 = ++i;
+  o.p50 = ++i;o.p51 = ++i;o.p52 = ++i;o.p53 = ++i;o.p54 = ++i;o.p55 = ++i;o.p56 = ++i;o.p57 = ++i;
+  o.p60 = ++i;o.p61 = ++i;o.p62 = ++i;o.p63 = ++i;o.p64 = ++i;o.p65 = ++i;o.p66 = ++i;o.p67 = ++i;
+  o.p70 = ++i;o.p71 = ++i;o.p72 = ++i;o.p73 = ++i;o.p74 = ++i;o.p75 = ++i;o.p76 = ++i;o.p77 = ++i;
+  o.p100 = ++i;
+  return o;
+}
+function add65th(o) {
+  o.p101 = ++i;
+}
+var o = add0to64({});
+add65th(o);
+delete o.p101;
+add65th(o);
+
+reportCompare(true, true, "don't crash");

new file mode 100644
--- /dev/null
+++ b/js/src/tests/js1_8_5/regress/regress-595365-2.js
@@ -0,0 +1,39 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/*
+ * Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/licenses/publicdomain/
+ */
+
+/*
+ * NB: this test hardcodes the value of MAX_PROPERTY_TREE_HEIGHT.
+ */
+var i = 0;
+function add0to64(o) {
+  o.p00 = ++i;o.p01 = ++i;o.p02 = ++i;o.p03 = ++i;o.p04 = ++i;o.p05 = ++i;o.p06 = ++i;o.p07 = ++i;
+  o.p10 = ++i;o.p11 = ++i;o.p12 = ++i;o.p13 = ++i;o.p14 = ++i;o.p15 = ++i;o.p16 = ++i;o.p17 = ++i;
+  o.p20 = ++i;o.p21 = ++i;o.p22 = ++i;o.p23 = ++i;o.p24 = ++i;o.p25 = ++i;o.p26 = ++i;o.p27 = ++i;
+  o.p30 = ++i;o.p31 = ++i;o.p32 = ++i;o.p33 = ++i;o.p34 = ++i;o.p35 = ++i;o.p36 = ++i;o.p37 = ++i;
+  o.p40 = ++i;o.p41 = ++i;o.p42 = ++i;o.p43 = ++i;o.p44 = ++i;o.p45 = ++i;o.p46 = ++i;o.p47 = ++i;
+  o.p50 = ++i;o.p51 = ++i;o.p52 = ++i;o.p53 = ++i;o.p54 = ++i;o.p55 = ++i;o.p56 = ++i;o.p57 = ++i;
+  o.p60 = ++i;o.p61 = ++i;o.p62 = ++i;o.p63 = ++i;o.p64 = ++i;o.p65 = ++i;o.p66 = ++i;o.p67 = ++i;
+  o.p70 = ++i;o.p71 = ++i;o.p72 = ++i;o.p73 = ++i;o.p74 = ++i;o.p75 = ++i;o.p76 = ++i;o.p77 = ++i;
+  o.p100 = ++i;
+  return o;
+}
+function add65th(o) {
+  o.p101 = ++i;
+}
+var o = add0to64({});
+var o2 = add0to64({});
+var o_shape64 = shapeOf(o);
+assertEq(o_shape64, shapeOf(o2));
+add65th(o);
+add65th(o2);
+var o_shape65 = shapeOf(o);
+assertEq(false, o_shape65 === shapeOf(o2));
+delete o.p101;
+assertEq(false, shapeOf(o) === o_shape64);
+add65th(o);
+assertEq(false, shapeOf(o) === o_shape65);
+
+reportCompare(true, true, "don't crash");