[INFER] Fix quadratic behavior when repeatedly attempting to expand inline frames, bug 657412.
authorBrian Hackett <bhackett1024@gmail.com>
Mon, 06 Jun 2011 16:14:09 -0700
changeset 75146 1b5429edb553cab294f7648036cfb8981a6989d8
parent 75145 334428e1d5aac565a771d1bbb1a785797fd89f81
child 75147 09d3a39c186a098ab626e21c2c94abf5c037e673
push id2
push userbsmedberg@mozilla.com
push dateFri, 19 Aug 2011 14:38:13 +0000
bugs657412
milestone6.0a1
[INFER] Fix quadratic behavior when repeatedly attempting to expand inline frames, bug 657412.
js/src/methodjit/Retcon.cpp
js/src/vm/Stack-inl.h
js/src/vm/Stack.cpp
js/src/vm/Stack.h
--- a/js/src/methodjit/Retcon.cpp
+++ b/js/src/methodjit/Retcon.cpp
@@ -322,18 +322,21 @@ ExpandInlineFrames(JSContext *cx, bool a
         for (StackFrame *fp = f->fp(); fp != end; fp = fp->prev()) {
             mjit::CallSite *inlined;
             fp->pcQuadratic(cx, next, &inlined);
             if (next && inlined) {
                 mjit::Recompiler::expandInlineFrames(cx, fp, inlined, next, f);
                 fp = next;
                 next = NULL;
             } else {
+                if (fp->downFramesExpanded())
+                    break;
                 next = fp;
             }
+            fp->setDownFramesExpanded();
         }
     }
 }
 
 Recompiler::Recompiler(JSContext *cx, JSScript *script)
   : cx(cx), script(script)
 {    
 }
--- a/js/src/vm/Stack-inl.h
+++ b/js/src/vm/Stack-inl.h
@@ -362,17 +362,18 @@ StackFrame::resetInvokeCallFrame()
                            OVERRIDE_ARGS |
                            HAS_PREVPC |
                            HAS_RVAL |
                            HAS_SCOPECHAIN |
                            HAS_ANNOTATION |
                            HAS_HOOK_DATA |
                            HAS_CALL_OBJ |
                            HAS_ARGS_OBJ |
-                           FINISHED_IN_INTERP)));
+                           FINISHED_IN_INTERP |
+                           DOWN_FRAMES_EXPANDED)));
 
     /*
      * Since the stack frame is usually popped after PutActivationObjects,
      * these bits aren't cleared. The activation objects must have actually
      * been put, though.
      */
     JS_ASSERT_IF(flags_ & HAS_CALL_OBJ, callObj().getPrivate() == NULL);
     JS_ASSERT_IF(flags_ & HAS_ARGS_OBJ, argsObj().getPrivate() == NULL);
@@ -1083,24 +1084,24 @@ ContextStack::findFrameAtLevel(uintN tar
         fp = fp->prev();
     }
     return fp;
 }
 
 inline JSScript *
 ContextStack::currentScript(jsbytecode **ppc) const
 {
-    StackFrame *fp = regs_->fp();
+    StackFrame *fp = regs_ ? regs_->fp() : NULL;
+    while (fp && fp->isDummyFrame())
+        fp = fp->prev();
     if (!fp) {
         if (ppc)
             *ppc = NULL;
         return NULL;
     }
-    while (fp->isDummyFrame())
-        fp = fp->prev();
 
 #ifdef JS_METHODJIT
     mjit::CallSite *inlined = regs_->inlined();
     if (inlined) {
         JS_ASSERT(inlined->inlineIndex < fp->jit()->nInlineFrames);
         mjit::InlineFrame *frame = &fp->jit()->inlineFrames()[inlined->inlineIndex];
         if (ppc)
             *ppc = frame->fun->script()->code + inlined->pcOffset;
--- a/js/src/vm/Stack.cpp
+++ b/js/src/vm/Stack.cpp
@@ -128,27 +128,33 @@ StackSegment::contains(const StackFrame 
     if (isActive())
         start = stack_->fp();
     else
         start = suspendedRegs_->fp();
 
     if (fp > start)
         return false;
 
+    /*
+     * :XXX: Disabled. Including this check changes the asymptotic complexity
+     * of code which calls this function.
+     */
+#if 0
 #ifdef DEBUG
     bool found = false;
     StackFrame *stop = initialFrame_->prev();
     for (StackFrame *f = start; !found && f != stop; f = f->prev()) {
         if (f == fp) {
             found = true;
             break;
         }
     }
     JS_ASSERT(found);
 #endif
+#endif
 
     return true;
 }
 
 StackFrame *
 StackSegment::computeNextFrame(StackFrame *fp) const
 {
     JS_ASSERT(contains(fp));
--- a/js/src/vm/Stack.h
+++ b/js/src/vm/Stack.h
@@ -260,17 +260,19 @@ class StackFrame
         /* Lazy frame initialization */
         HAS_IMACRO_PC      =     0x2000,  /* frame has imacpc value available */
         HAS_CALL_OBJ       =     0x4000,  /* frame has a callobj reachable from scopeChain_ */
         HAS_ARGS_OBJ       =     0x8000,  /* frame has an argsobj in StackFrame::args */
         HAS_HOOK_DATA      =    0x10000,  /* frame has hookData_ set */
         HAS_ANNOTATION     =    0x20000,  /* frame has annotation_ set */
         HAS_RVAL           =    0x40000,  /* frame has rval_ set */
         HAS_SCOPECHAIN     =    0x80000,  /* frame has scopeChain_ set */
-        HAS_PREVPC         =   0x100000   /* frame has prevpc_ and prevInline_ set */
+        HAS_PREVPC         =   0x100000,  /* frame has prevpc_ and prevInline_ set */
+
+        DOWN_FRAMES_EXPANDED = 0x200000   /* inlining in down frames has been expanded */
     };
 
   private:
     mutable uint32      flags_;         /* bits described by Flags */
     union {                             /* describes what code is executing in a */
         JSScript        *script;        /*   global frame */
         JSFunction      *fun;           /*   function frame, pre GetScopeChain */
     } exec;
@@ -796,16 +798,26 @@ class StackFrame
     JSRejoinState rejoin() const {
         return rejoin_;
     }
 
     void setRejoin(JSRejoinState state) {
         rejoin_ = state;
     }
 
+    /* Down frame expansion state */
+
+    void setDownFramesExpanded() {
+        flags_ |= DOWN_FRAMES_EXPANDED;
+    }
+
+    bool downFramesExpanded() {
+        return flags_ & DOWN_FRAMES_EXPANDED;
+    }
+
     /* Debugger hook data */
 
     bool hasHookData() const {
         return !!(flags_ & HAS_HOOK_DATA);
     }
 
     void* hookData() const {
         JS_ASSERT(hasHookData());