Revision: 13226
Author: [email protected]
Date: Mon Dec 17 02:23:52 2012
Log: Use a filter instead of a visitor to deoptimize selected
functions in a context.
This makes the DeoptimizeAll function O(n) instead of O(n^2) where n in the
number of optimized functions.
Before this change, DeoptimizeAll iterated over the optimized function list
and called DeoptimizingVisitor for each function. The visitor iterated over
the optimized function list again to remove the functions that share the
same optimized code.
This change partitions the optimized function list into one or more lists
of related functions in one pass over the optimized function list.
[email protected]
Review URL: https://chromiumcodereview.appspot.com/11547015
http://code.google.com/p/v8/source/detail?r=13226
Modified:
/branches/bleeding_edge/src/arm/deoptimizer-arm.cc
/branches/bleeding_edge/src/deoptimizer.cc
/branches/bleeding_edge/src/deoptimizer.h
/branches/bleeding_edge/src/ia32/deoptimizer-ia32.cc
/branches/bleeding_edge/src/liveedit.cc
/branches/bleeding_edge/src/mips/deoptimizer-mips.cc
/branches/bleeding_edge/src/objects-inl.h
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/src/x64/deoptimizer-x64.cc
=======================================
--- /branches/bleeding_edge/src/arm/deoptimizer-arm.cc Mon Dec 10 03:09:12
2012
+++ /branches/bleeding_edge/src/arm/deoptimizer-arm.cc Mon Dec 17 02:23:52
2012
@@ -44,11 +44,14 @@
}
-void Deoptimizer::DeoptimizeFunction(JSFunction* function) {
- HandleScope scope;
+void Deoptimizer::DeoptimizeFunctionWithPreparedFunctionList(
+ JSFunction* function) {
+ Isolate* isolate = function->GetIsolate();
+ HandleScope scope(isolate);
AssertNoAllocation no_allocation;
- if (!function->IsOptimized()) return;
+ ASSERT(function->IsOptimized());
+ ASSERT(function->FunctionsInFunctionListShareSameCode());
// The optimized code is going to be patched, so we cannot use it
// any more. Play safe and reset the whole cache.
@@ -90,8 +93,6 @@
prev_call_address = call_address;
#endif
}
-
- Isolate* isolate = code->GetIsolate();
// Add the deoptimizing code to the list.
DeoptimizingCodeListNode* node = new DeoptimizingCodeListNode(code);
=======================================
--- /branches/bleeding_edge/src/deoptimizer.cc Mon Dec 10 03:09:12 2012
+++ /branches/bleeding_edge/src/deoptimizer.cc Mon Dec 17 02:23:52 2012
@@ -245,45 +245,6 @@
TableEntryGenerator generator(masm, type, count);
generator.Generate();
}
-
-
-class DeoptimizingVisitor : public OptimizedFunctionVisitor {
- public:
- virtual void EnterContext(Context* context) {
- if (FLAG_trace_deopt) {
- PrintF("[deoptimize context: %" V8PRIxPTR "]\n",
- reinterpret_cast<intptr_t>(context));
- }
- }
-
- virtual void VisitFunction(JSFunction* function) {
- Deoptimizer::DeoptimizeFunction(function);
- }
-
- virtual void LeaveContext(Context* context) {
- context->ClearOptimizedFunctions();
- }
-};
-
-
-void Deoptimizer::DeoptimizeAll() {
- AssertNoAllocation no_allocation;
-
- if (FLAG_trace_deopt) {
- PrintF("[deoptimize all contexts]\n");
- }
-
- DeoptimizingVisitor visitor;
- VisitAllOptimizedFunctions(&visitor);
-}
-
-
-void Deoptimizer::DeoptimizeGlobalObject(JSObject* object) {
- AssertNoAllocation no_allocation;
-
- DeoptimizingVisitor visitor;
- VisitAllOptimizedFunctionsForGlobalObject(object, &visitor);
-}
void Deoptimizer::VisitAllOptimizedFunctionsForContext(
@@ -315,36 +276,151 @@
}
-void Deoptimizer::VisitAllOptimizedFunctionsForGlobalObject(
- JSObject* object, OptimizedFunctionVisitor* visitor) {
+void Deoptimizer::VisitAllOptimizedFunctions(
+ OptimizedFunctionVisitor* visitor) {
+ AssertNoAllocation no_allocation;
+
+ // Run through the list of all native contexts and deoptimize.
+ Object* context = Isolate::Current()->heap()->native_contexts_list();
+ while (!context->IsUndefined()) {
+ VisitAllOptimizedFunctionsForContext(Context::cast(context), visitor);
+ context = Context::cast(context)->get(Context::NEXT_CONTEXT_LINK);
+ }
+}
+
+
+// Removes the functions selected by the given filter from the optimized
+// function list of the given context and partitions the removed functions
+// into one or more lists such that all functions in a list share the same
+// code. The head of each list is written in the deoptimizing_functions
field
+// of the corresponding code object.
+// The found code objects are returned in the given zone list.
+static void PartitionOptimizedFunctions(Context* context,
+ OptimizedFunctionFilter* filter,
+ ZoneList<Code*>* partitions,
+ Zone* zone,
+ Object* undefined) {
+ AssertNoAllocation no_allocation;
+ Object* current = context->get(Context::OPTIMIZED_FUNCTIONS_LIST);
+ Object* remainder_head = undefined;
+ Object* remainder_tail = undefined;
+ ASSERT_EQ(0, partitions->length());
+ while (current != undefined) {
+ JSFunction* function = JSFunction::cast(current);
+ current = function->next_function_link();
+ if (filter->TakeFunction(function)) {
+ Code* code = function->code();
+ if (code->deoptimizing_functions() == undefined) {
+ partitions->Add(code, zone);
+ } else {
+ ASSERT(partitions->Contains(code));
+ }
+ function->set_next_function_link(code->deoptimizing_functions());
+ code->set_deoptimizing_functions(function);
+ } else {
+ if (remainder_head == undefined) {
+ remainder_head = function;
+ } else {
+ JSFunction::cast(remainder_tail)->set_next_function_link(function);
+ }
+ remainder_tail = function;
+ }
+ }
+ if (remainder_tail != undefined) {
+ JSFunction::cast(remainder_tail)->set_next_function_link(undefined);
+ }
+ context->set(Context::OPTIMIZED_FUNCTIONS_LIST, remainder_head);
+}
+
+
+class DeoptimizeAllFilter : public OptimizedFunctionFilter {
+ public:
+ virtual bool TakeFunction(JSFunction* function) {
+ return true;
+ }
+};
+
+
+class DeoptimizeWithMatchingCodeFilter : public OptimizedFunctionFilter {
+ public:
+ explicit DeoptimizeWithMatchingCodeFilter(Code* code) : code_(code) {}
+ virtual bool TakeFunction(JSFunction* function) {
+ return function->code() == code_;
+ }
+ private:
+ Code* code_;
+};
+
+
+void Deoptimizer::DeoptimizeAll() {
AssertNoAllocation no_allocation;
+ if (FLAG_trace_deopt) {
+ PrintF("[deoptimize all contexts]\n");
+ }
+
+ DeoptimizeAllFilter filter;
+ DeoptimizeAllFunctionsWith(&filter);
+}
+
+
+void Deoptimizer::DeoptimizeGlobalObject(JSObject* object) {
+ AssertNoAllocation no_allocation;
+ DeoptimizeAllFilter filter;
if (object->IsJSGlobalProxy()) {
Object* proto = object->GetPrototype();
ASSERT(proto->IsJSGlobalObject());
- VisitAllOptimizedFunctionsForContext(
- GlobalObject::cast(proto)->native_context(), visitor);
+ DeoptimizeAllFunctionsForContext(
+ GlobalObject::cast(proto)->native_context(), &filter);
} else if (object->IsGlobalObject()) {
- VisitAllOptimizedFunctionsForContext(
- GlobalObject::cast(object)->native_context(), visitor);
+ DeoptimizeAllFunctionsForContext(
+ GlobalObject::cast(object)->native_context(), &filter);
+ }
+}
+
+
+void Deoptimizer::DeoptimizeFunction(JSFunction* function) {
+ if (!function->IsOptimized()) return;
+ Code* code = function->code();
+ Context* context = function->context()->native_context();
+ Isolate* isolate = context->GetIsolate();
+ Object* undefined = isolate->heap()->undefined_value();
+ Zone* zone = isolate->runtime_zone();
+ ZoneScope zone_scope(zone, DELETE_ON_EXIT);
+ ZoneList<Code*> codes(1, zone);
+ DeoptimizeWithMatchingCodeFilter filter(code);
+ PartitionOptimizedFunctions(context, &filter, &codes, zone, undefined);
+ ASSERT_EQ(1, codes.length());
+ DeoptimizeFunctionWithPreparedFunctionList(
+ JSFunction::cast(codes.at(0)->deoptimizing_functions()));
+ codes.at(0)->set_deoptimizing_functions(undefined);
+}
+
+
+void Deoptimizer::DeoptimizeAllFunctionsForContext(
+ Context* context, OptimizedFunctionFilter* filter) {
+ ASSERT(context->IsNativeContext());
+ Isolate* isolate = context->GetIsolate();
+ Object* undefined = isolate->heap()->undefined_value();
+ Zone* zone = isolate->runtime_zone();
+ ZoneScope zone_scope(zone, DELETE_ON_EXIT);
+ ZoneList<Code*> codes(1, zone);
+ PartitionOptimizedFunctions(context, filter, &codes, zone, undefined);
+ for (int i = 0; i < codes.length(); ++i) {
+ DeoptimizeFunctionWithPreparedFunctionList(
+ JSFunction::cast(codes.at(i)->deoptimizing_functions()));
+ codes.at(i)->set_deoptimizing_functions(undefined);
}
}
-void Deoptimizer::VisitAllOptimizedFunctions(
- OptimizedFunctionVisitor* visitor) {
+void Deoptimizer::DeoptimizeAllFunctionsWith(OptimizedFunctionFilter*
filter) {
AssertNoAllocation no_allocation;
// Run through the list of all native contexts and deoptimize.
Object* context = Isolate::Current()->heap()->native_contexts_list();
while (!context->IsUndefined()) {
- // GC can happen when the context is not fully initialized,
- // so the global field of the context can be undefined.
- Object* global =
Context::cast(context)->get(Context::GLOBAL_OBJECT_INDEX);
- if (!global->IsUndefined()) {
- VisitAllOptimizedFunctionsForGlobalObject(JSObject::cast(global),
- visitor);
- }
+ DeoptimizeAllFunctionsForContext(Context::cast(context), filter);
context = Context::cast(context)->get(Context::NEXT_CONTEXT_LINK);
}
}
@@ -1474,46 +1550,13 @@
// to be removed once and only once.
UNREACHABLE();
}
-
-
-static Object* CutOutRelatedFunctionsList(Context* context,
- Code* code,
- Object* undefined) {
- Object* result_list_head = undefined;
- Object* head;
- Object* current;
- current = head = context->get(Context::OPTIMIZED_FUNCTIONS_LIST);
- JSFunction* prev = NULL;
- while (current != undefined) {
- JSFunction* func = JSFunction::cast(current);
- current = func->next_function_link();
- if (func->code() == code) {
- func->set_next_function_link(result_list_head);
- result_list_head = func;
- if (prev) {
- prev->set_next_function_link(current);
- } else {
- head = current;
- }
- } else {
- prev = func;
- }
- }
- if (head != context->get(Context::OPTIMIZED_FUNCTIONS_LIST)) {
- context->set(Context::OPTIMIZED_FUNCTIONS_LIST, head);
- }
- return result_list_head;
-}
void Deoptimizer::ReplaceCodeForRelatedFunctions(JSFunction* function,
Code* code) {
- Context* context = function->context()->native_context();
-
SharedFunctionInfo* shared = function->shared();
-
Object* undefined = Isolate::Current()->heap()->undefined_value();
- Object* current = CutOutRelatedFunctionsList(context, code, undefined);
+ Object* current = function;
while (current != undefined) {
JSFunction* func = JSFunction::cast(current);
=======================================
--- /branches/bleeding_edge/src/deoptimizer.h Mon Dec 10 03:09:12 2012
+++ /branches/bleeding_edge/src/deoptimizer.h Mon Dec 17 02:23:52 2012
@@ -87,6 +87,14 @@
};
+class OptimizedFunctionFilter BASE_EMBEDDED {
+ public:
+ virtual ~OptimizedFunctionFilter() {}
+
+ virtual bool TakeFunction(JSFunction* function) = 0;
+};
+
+
class Deoptimizer;
@@ -177,12 +185,14 @@
static void DeoptimizeGlobalObject(JSObject* object);
+ static void DeoptimizeAllFunctionsWith(OptimizedFunctionFilter* filter);
+
+ static void DeoptimizeAllFunctionsForContext(
+ Context* context, OptimizedFunctionFilter* filter);
+
static void VisitAllOptimizedFunctionsForContext(
Context* context, OptimizedFunctionVisitor* visitor);
- static void VisitAllOptimizedFunctionsForGlobalObject(
- JSObject* object, OptimizedFunctionVisitor* visitor);
-
static void VisitAllOptimizedFunctions(OptimizedFunctionVisitor*
visitor);
// The size in bytes of the code required at a lazy deopt patch site.
@@ -353,6 +363,10 @@
static Code* FindDeoptimizingCodeFromAddress(Address addr);
static void RemoveDeoptimizingCode(Code* code);
+ // Deoptimize function assuming that function->next_function_link()
points
+ // to a list that contains all functions that share the same optimized
code.
+ static void DeoptimizeFunctionWithPreparedFunctionList(JSFunction*
function);
+
// Fill the input from from a JavaScript frame. This is used when
// the debugger needs to inspect an optimized frame. For normal
// deoptimizations the input frame is filled in generated code.
=======================================
--- /branches/bleeding_edge/src/ia32/deoptimizer-ia32.cc Mon Dec 10
03:09:12 2012
+++ /branches/bleeding_edge/src/ia32/deoptimizer-ia32.cc Mon Dec 17
02:23:52 2012
@@ -114,17 +114,19 @@
}
-void Deoptimizer::DeoptimizeFunction(JSFunction* function) {
- if (!function->IsOptimized()) return;
+void Deoptimizer::DeoptimizeFunctionWithPreparedFunctionList(
+ JSFunction* function) {
+ Isolate* isolate = function->GetIsolate();
+ HandleScope scope(isolate);
+ AssertNoAllocation no_allocation;
+
+ ASSERT(function->IsOptimized());
+ ASSERT(function->FunctionsInFunctionListShareSameCode());
// The optimized code is going to be patched, so we cannot use it
// any more. Play safe and reset the whole cache.
function->shared()->ClearOptimizedCodeMap();
- Isolate* isolate = function->GetIsolate();
- HandleScope scope(isolate);
- AssertNoAllocation no_allocation;
-
// Get the optimized code.
Code* code = function->code();
Address code_start_address = code->instruction_start();
=======================================
--- /branches/bleeding_edge/src/liveedit.cc Tue Dec 4 02:15:19 2012
+++ /branches/bleeding_edge/src/liveedit.cc Mon Dec 17 02:23:52 2012
@@ -1223,23 +1223,15 @@
}
-class DependentFunctionsDeoptimizingVisitor : public
OptimizedFunctionVisitor {
+class DependentFunctionFilter : public OptimizedFunctionFilter {
public:
- explicit DependentFunctionsDeoptimizingVisitor(
+ explicit DependentFunctionFilter(
SharedFunctionInfo* function_info)
: function_info_(function_info) {}
- virtual void EnterContext(Context* context) {
- }
-
- virtual void VisitFunction(JSFunction* function) {
- if (function->shared() == function_info_ ||
- IsInlined(function, function_info_)) {
- Deoptimizer::DeoptimizeFunction(function);
- }
- }
-
- virtual void LeaveContext(Context* context) {
+ virtual bool TakeFunction(JSFunction* function) {
+ return (function->shared() == function_info_ ||
+ IsInlined(function, function_info_));
}
private:
@@ -1250,8 +1242,8 @@
static void DeoptimizeDependentFunctions(SharedFunctionInfo*
function_info) {
AssertNoAllocation no_allocation;
- DependentFunctionsDeoptimizingVisitor visitor(function_info);
- Deoptimizer::VisitAllOptimizedFunctions(&visitor);
+ DependentFunctionFilter filter(function_info);
+ Deoptimizer::DeoptimizeAllFunctionsWith(&filter);
}
=======================================
--- /branches/bleeding_edge/src/mips/deoptimizer-mips.cc Fri Dec 7
00:55:06 2012
+++ /branches/bleeding_edge/src/mips/deoptimizer-mips.cc Mon Dec 17
02:23:52 2012
@@ -42,11 +42,14 @@
}
-void Deoptimizer::DeoptimizeFunction(JSFunction* function) {
- HandleScope scope;
+void Deoptimizer::DeoptimizeFunctionWithPreparedFunctionList(
+ JSFunction* function) {
+ Isolate* isolate = function->GetIsolate();
+ HandleScope scope(isolate);
AssertNoAllocation no_allocation;
- if (!function->IsOptimized()) return;
+ ASSERT(function->IsOptimized());
+ ASSERT(function->FunctionsInFunctionListShareSameCode());
// The optimized code is going to be patched, so we cannot use it
// any more. Play safe and reset the whole cache.
@@ -86,8 +89,6 @@
prev_call_address = call_address;
#endif
}
-
- Isolate* isolate = code->GetIsolate();
// Add the deoptimizing code to the list.
DeoptimizingCodeListNode* node = new DeoptimizingCodeListNode(code);
=======================================
--- /branches/bleeding_edge/src/objects-inl.h Fri Dec 14 06:19:18 2012
+++ /branches/bleeding_edge/src/objects-inl.h Mon Dec 17 02:23:52 2012
@@ -4809,6 +4809,18 @@
ASSERT(kind() == COMPARE_IC || kind() == BINARY_OP_IC);
WRITE_FIELD(this, kTypeFeedbackInfoOffset, Smi::FromInt(value));
}
+
+
+void Code::set_deoptimizing_functions(Object* value) {
+ ASSERT(kind() == OPTIMIZED_FUNCTION);
+ WRITE_FIELD(this, kTypeFeedbackInfoOffset, value);
+}
+
+
+Object* Code::deoptimizing_functions() {
+ ASSERT(kind() == OPTIMIZED_FUNCTION);
+ return Object::cast(READ_FIELD(this, kTypeFeedbackInfoOffset));
+}
ACCESSORS(Code, gc_metadata, Object, kGCMetadataOffset)
=======================================
--- /branches/bleeding_edge/src/objects.h Fri Dec 14 06:19:18 2012
+++ /branches/bleeding_edge/src/objects.h Mon Dec 17 02:23:52 2012
@@ -4254,13 +4254,18 @@
// [deoptimization_data]: Array containing data for deopt.
DECL_ACCESSORS(deoptimization_data, FixedArray)
- // [type_feedback_info]: Struct containing type feedback information.
+ // [type_feedback_info]: Struct containing type feedback information for
+ // unoptimized code. Optimized code can temporarily store the head of
+ // the list of the dependent optimized functions during deoptimization.
// STUBs can use this slot to store arbitrary information as a Smi.
- // Will contain either a TypeFeedbackInfo object, or undefined, or a Smi.
+ // Will contain either a TypeFeedbackInfo object, or JSFunction object,
+ // or undefined, or a Smi.
DECL_ACCESSORS(type_feedback_info, Object)
inline void InitializeTypeFeedbackInfoNoWriteBarrier(Object* value);
inline int stub_info();
inline void set_stub_info(int info);
+ inline Object* deoptimizing_functions();
+ inline void set_deoptimizing_functions(Object* value);
// [gc_metadata]: Field used to hold GC related metadata. The contents
of this
// field does not have to be traced during garbage collection since
@@ -5125,8 +5130,7 @@
kConstructorOffset + kPointerSize;
static const int kDescriptorsOffset =
kTransitionsOrBackPointerOffset + kPointerSize;
- static const int kCodeCacheOffset =
- kDescriptorsOffset + kPointerSize;
+ static const int kCodeCacheOffset = kDescriptorsOffset + kPointerSize;
static const int kBitField3Offset = kCodeCacheOffset + kPointerSize;
static const int kSize = kBitField3Offset + kPointerSize;
@@ -6148,6 +6152,18 @@
// Retrieve the native context from a function's literal array.
static Context* NativeContextFromLiterals(FixedArray* literals);
+#ifdef DEBUG
+ bool FunctionsInFunctionListShareSameCode() {
+ Object* current = this;
+ while (!current->IsUndefined()) {
+ JSFunction* function = JSFunction::cast(current);
+ current = function->next_function_link();
+ if (function->code() != this->code()) return false;
+ }
+ return true;
+ }
+#endif
+
// Layout descriptors. The last property (from kNonWeakFieldsEndOffset to
// kSize) is weak and has special handling during garbage collection.
static const int kCodeEntryOffset = JSObject::kHeaderSize;
=======================================
--- /branches/bleeding_edge/src/x64/deoptimizer-x64.cc Mon Dec 10 03:09:12
2012
+++ /branches/bleeding_edge/src/x64/deoptimizer-x64.cc Mon Dec 17 02:23:52
2012
@@ -46,11 +46,14 @@
}
-void Deoptimizer::DeoptimizeFunction(JSFunction* function) {
- HandleScope scope;
+void Deoptimizer::DeoptimizeFunctionWithPreparedFunctionList(
+ JSFunction* function) {
+ Isolate* isolate = function->GetIsolate();
+ HandleScope scope(isolate);
AssertNoAllocation no_allocation;
- if (!function->IsOptimized()) return;
+ ASSERT(function->IsOptimized());
+ ASSERT(function->FunctionsInFunctionListShareSameCode());
// The optimized code is going to be patched, so we cannot use it
// any more. Play safe and reset the whole cache.
@@ -90,8 +93,6 @@
prev_call_address = call_address;
#endif
}
-
- Isolate* isolate = code->GetIsolate();
// Add the deoptimizing code to the list.
DeoptimizingCodeListNode* node = new DeoptimizingCodeListNode(code);
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
