Changeset 37831 in webkit for trunk/JavaScriptCore/VM/CodeBlock.h

Timestamp:

Oct 23, 2008, 3:29:54 PM (17 years ago)

Author:

[email protected]

Message:

2008-10-23 Gavin Barraclough <​[email protected]>

Reviewed by Oliver Hunt.

Fix hideous pathological case performance when looking up repatch info, bug #21727.

When repatching JIT code to optimize we look up records providing information about
the generated code (also used to track recsources used in linking to be later released).
The lookup was being performed using a linear scan of all such records.

(1) Split up the different types of reptach information. This means we can search them

separately, and in some cases should reduce their size.

(2) In the case of property accesses, search with a binary chop over the data.
(3) In the case of calls, pass a pointer to the repatch info into the relink function.

• VM/CTI.cpp: (JSC::CTI::CTI): (JSC::CTI::compileOpCall): (JSC::CTI::privateCompileMainPass): (JSC::CTI::privateCompileSlowCases): (JSC::CTI::privateCompile): (JSC::CTI::unlinkCall): (JSC::CTI::linkCall):
• VM/CTI.h:
• VM/CodeBlock.cpp: (JSC::CodeBlock::dump): (JSC::CodeBlock::~CodeBlock): (JSC::CodeBlock::unlinkCallers): (JSC::CodeBlock::derefStructureIDs):
• VM/CodeBlock.h: (JSC::StructureStubInfo::StructureStubInfo): (JSC::CallLinkInfo::CallLinkInfo): (JSC::CallLinkInfo::setUnlinked): (JSC::CallLinkInfo::isLinked): (JSC::getStructureStubInfoReturnLocation): (JSC::binaryChop): (JSC::CodeBlock::addCaller): (JSC::CodeBlock::getStubInfo):
• VM/CodeGenerator.cpp: (JSC::CodeGenerator::emitResolve): (JSC::CodeGenerator::emitGetById): (JSC::CodeGenerator::emitPutById): (JSC::CodeGenerator::emitCall): (JSC::CodeGenerator::emitConstruct):
• VM/Machine.cpp: (JSC::Machine::cti_vm_lazyLinkCall):

File:

• trunk/JavaScriptCore/VM/CodeBlock.h (modified) (6 diffs)

trunk/JavaScriptCore/VM/CodeBlock.h

@@ -79 +79 @@
     };
 
-    struct CallLinkInfo;
-
     struct StructureStubInfo {
         StructureStubInfo(unsigned opcodeIndex)
@@ -87 +85 @@
             , callReturnLocation(0)
             , hotPathBegin(0)
-            , hotPathOther(0)
-            , coldPathOther(0)
-            , linkInfoPtr(0)
         {
         }
@@ -97 +92 @@
         void* callReturnLocation;
         void* hotPathBegin;
+    };
+
+    struct CallLinkInfo {
+        CallLinkInfo()
+            : callReturnLocation(0)
+            , hotPathBegin(0)
+            , hotPathOther(0)
+            , coldPathOther(0)
+            , callee(0)
+        {
+        }
+    
+        unsigned opcodeIndex;
+        void* callReturnLocation;
+        void* hotPathBegin;
         void* hotPathOther;
         void* coldPathOther;
-        CallLinkInfo* linkInfoPtr;
-    };
-
-    struct CallLinkInfo {
         CodeBlock* callee;
-        StructureStubInfo* callerStructureStubInfo;
         unsigned position;
-
-        CallLinkInfo(CodeBlock* c, StructureStubInfo* css)
-        {
-            callee = c;
-            callerStructureStubInfo = css;
-        }
-    };
+        
+        void setUnlinked() { callee = 0; }
+        bool isLinked() { return callee; }
+    };
+
+    inline void* getStructureStubInfoReturnLocation(StructureStubInfo* structureStubInfo)
+    {
+        return structureStubInfo->callReturnLocation;
+    }
+
+    // Binary chop algorithm, calls valueAtPosition on pre-sorted elements in array,
+    // compares result with key (KeyTypes should be comparable with '--', '<', '>').
+    // Optimized for cases where the array contains the key, checked by assertions.
+    template<typename ArrayType, typename KeyType, KeyType(*valueAtPosition)(ArrayType*)>
+    inline ArrayType* binaryChop(ArrayType* array, size_t size, KeyType key)
+    {
+        // The array must contain at least one element (pre-condition, array does conatin key).
+        // If the array only contains one element, no need to do the comparison.
+        while (size > 1) {
+            // Pick an element to check, half way through the array, and read the value.
+            int pos = (size - 1) >> 1;
+            KeyType val = valueAtPosition(&array[pos]);
+            
+            // If the key matches, success!
+            if (val == key)
+                return &array[pos];
+            // The item we are looking for is smaller than the item being check; reduce the value of 'size',
+            // chopping off the right hand half of the array.
+            else if (key < val)
+                size = pos;
+            // Discard all values in the left hand half of the array, up to and including the item at pos.
+            else {
+                size -= (pos + 1);
+                array += (pos + 1);
+            }
+
+            // 'size' should never reach zero.
+            ASSERT(size);
+        }
+        
+        // If we reach this point we've chopped down to one element, no need to check it matches
+        ASSERT(size == 1);
+        ASSERT(key == valueAtPosition(&array[0]));
+        return &array[0];
+    }
 
     struct StringJumpTable {
@@ -228 +271 @@
 #endif
 
-        void addCaller(StructureStubInfo* caller)
-        {
-            CallLinkInfo* callLinkInfo = new CallLinkInfo(this, caller);
-            caller->linkInfoPtr = callLinkInfo;
-            callLinkInfo->position = linkedCallerList.size();
-            linkedCallerList.append(callLinkInfo);
+        void addCaller(CallLinkInfo* caller)
+        {
+            caller->callee = this;
+            caller->position = linkedCallerList.size();
+            linkedCallerList.append(caller);
         }
 
@@ -264 +306 @@
         StructureStubInfo& getStubInfo(void* returnAddress)
         {
-            // FIXME: would a binary chop be faster here?
-            for (unsigned i = 0; ; ++i) {
-                ASSERT(i < structureIDInstructions.size());
-                if (structureIDInstructions[i].callReturnLocation == returnAddress)
-                    return structureIDInstructions[i];
-            }
+            return *(binaryChop<StructureStubInfo, void*, getStructureStubInfoReturnLocation>(propertyAccessInstructions.begin(), propertyAccessInstructions.size(), returnAddress));
         }
 
@@ -296 +333 @@
 
         Vector<Instruction> instructions;
-        Vector<StructureStubInfo> structureIDInstructions;
+        Vector<unsigned> globalResolveInstructions;
+        Vector<StructureStubInfo> propertyAccessInstructions;
+        Vector<CallLinkInfo> callLinkInfos;
         Vector<CallLinkInfo*> linkedCallerList;