scopeinfo.cc revision 69a99ed0b2b2ef69d393c371b03db3a98aaf880e
1// Copyright 2011 the V8 project authors. All rights reserved. 2// Redistribution and use in source and binary forms, with or without 3// modification, are permitted provided that the following conditions are 4// met: 5// 6// * Redistributions of source code must retain the above copyright 7// notice, this list of conditions and the following disclaimer. 8// * Redistributions in binary form must reproduce the above 9// copyright notice, this list of conditions and the following 10// disclaimer in the documentation and/or other materials provided 11// with the distribution. 12// * Neither the name of Google Inc. nor the names of its 13// contributors may be used to endorse or promote products derived 14// from this software without specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28#include <stdlib.h> 29 30#include "v8.h" 31 32#include "scopeinfo.h" 33#include "scopes.h" 34 35#include "allocation-inl.h" 36 37namespace v8 { 38namespace internal { 39 40 41static int CompareLocal(Variable* const* v, Variable* const* w) { 42 Slot* s = (*v)->AsSlot(); 43 Slot* t = (*w)->AsSlot(); 44 // We may have rewritten parameters (that are in the arguments object) 45 // and which may have a NULL slot... - find a better solution... 46 int x = (s != NULL ? s->index() : 0); 47 int y = (t != NULL ? t->index() : 0); 48 // Consider sorting them according to type as well? 49 return x - y; 50} 51 52 53template<class Allocator> 54ScopeInfo<Allocator>::ScopeInfo(Scope* scope) 55 : function_name_(FACTORY->empty_symbol()), 56 calls_eval_(scope->calls_eval()), 57 is_strict_mode_(scope->is_strict_mode()), 58 parameters_(scope->num_parameters()), 59 stack_slots_(scope->num_stack_slots()), 60 context_slots_(scope->num_heap_slots()), 61 context_modes_(scope->num_heap_slots()) { 62 // Add parameters. 63 for (int i = 0; i < scope->num_parameters(); i++) { 64 ASSERT(parameters_.length() == i); 65 parameters_.Add(scope->parameter(i)->name()); 66 } 67 68 // Add stack locals and collect heap locals. 69 // We are assuming that the locals' slots are allocated in 70 // increasing order, so we can simply add them to the 71 // ScopeInfo lists. However, due to usage analysis, this is 72 // not true for context-allocated locals: Some of them 73 // may be parameters which are allocated before the 74 // non-parameter locals. When the non-parameter locals are 75 // sorted according to usage, the allocated slot indices may 76 // not be in increasing order with the variable list anymore. 77 // Thus, we first collect the context-allocated locals, and then 78 // sort them by context slot index before adding them to the 79 // ScopeInfo list. 80 List<Variable*, Allocator> locals(32); // 32 is a wild guess 81 ASSERT(locals.is_empty()); 82 scope->CollectUsedVariables(&locals); 83 locals.Sort(&CompareLocal); 84 85 List<Variable*, Allocator> heap_locals(locals.length()); 86 for (int i = 0; i < locals.length(); i++) { 87 Variable* var = locals[i]; 88 if (var->is_used()) { 89 Slot* slot = var->AsSlot(); 90 if (slot != NULL) { 91 switch (slot->type()) { 92 case Slot::PARAMETER: 93 // explicitly added to parameters_ above - ignore 94 break; 95 96 case Slot::LOCAL: 97 ASSERT(stack_slots_.length() == slot->index()); 98 stack_slots_.Add(var->name()); 99 break; 100 101 case Slot::CONTEXT: 102 heap_locals.Add(var); 103 break; 104 105 case Slot::LOOKUP: 106 // This is currently not used. 107 UNREACHABLE(); 108 break; 109 } 110 } 111 } 112 } 113 114 // Add heap locals. 115 if (scope->num_heap_slots() > 0) { 116 // Add user-defined slots. 117 for (int i = 0; i < heap_locals.length(); i++) { 118 ASSERT(heap_locals[i]->AsSlot()->index() - Context::MIN_CONTEXT_SLOTS == 119 context_slots_.length()); 120 ASSERT(heap_locals[i]->AsSlot()->index() - Context::MIN_CONTEXT_SLOTS == 121 context_modes_.length()); 122 context_slots_.Add(heap_locals[i]->name()); 123 context_modes_.Add(heap_locals[i]->mode()); 124 } 125 126 } else { 127 ASSERT(heap_locals.length() == 0); 128 } 129 130 // Add the function context slot, if present. 131 // For now, this must happen at the very end because of the 132 // ordering of the scope info slots and the respective slot indices. 133 if (scope->is_function_scope()) { 134 Variable* var = scope->function(); 135 if (var != NULL && 136 var->is_used() && 137 var->AsSlot()->type() == Slot::CONTEXT) { 138 function_name_ = var->name(); 139 // Note that we must not find the function name in the context slot 140 // list - instead it must be handled separately in the 141 // Contexts::Lookup() function. Thus record an empty symbol here so we 142 // get the correct number of context slots. 143 ASSERT(var->AsSlot()->index() - Context::MIN_CONTEXT_SLOTS == 144 context_slots_.length()); 145 ASSERT(var->AsSlot()->index() - Context::MIN_CONTEXT_SLOTS == 146 context_modes_.length()); 147 context_slots_.Add(FACTORY->empty_symbol()); 148 context_modes_.Add(Variable::INTERNAL); 149 } 150 } 151} 152 153 154// Encoding format in a FixedArray object: 155// 156// - function name 157// 158// - calls eval boolean flag 159// 160// - number of variables in the context object (smi) (= function context 161// slot index + 1) 162// - list of pairs (name, Var mode) of context-allocated variables (starting 163// with context slot 0) 164// 165// - number of parameters (smi) 166// - list of parameter names (starting with parameter 0 first) 167// 168// - number of variables on the stack (smi) 169// - list of names of stack-allocated variables (starting with stack slot 0) 170 171// The ScopeInfo representation could be simplified and the ScopeInfo 172// re-implemented (with almost the same interface). Here is a 173// suggestion for the new format: 174// 175// - have a single list with all variable names (parameters, stack locals, 176// context locals), followed by a list of non-Object* values containing 177// the variables information (what kind, index, attributes) 178// - searching the linear list of names is fast and yields an index into the 179// list if the variable name is found 180// - that list index is then used to find the variable information in the 181// subsequent list 182// - the list entries don't have to be in any particular order, so all the 183// current sorting business can go away 184// - the ScopeInfo lookup routines can be reduced to perhaps a single lookup 185// which returns all information at once 186// - when gathering the information from a Scope, we only need to iterate 187// through the local variables (parameters and context info is already 188// present) 189 190 191static inline Object** ReadInt(Object** p, int* x) { 192 *x = (reinterpret_cast<Smi*>(*p++))->value(); 193 return p; 194} 195 196 197static inline Object** ReadBool(Object** p, bool* x) { 198 *x = (reinterpret_cast<Smi*>(*p++))->value() != 0; 199 return p; 200} 201 202 203static inline Object** ReadSymbol(Object** p, Handle<String>* s) { 204 *s = Handle<String>(reinterpret_cast<String*>(*p++)); 205 return p; 206} 207 208 209template <class Allocator> 210static Object** ReadList(Object** p, List<Handle<String>, Allocator >* list) { 211 ASSERT(list->is_empty()); 212 int n; 213 p = ReadInt(p, &n); 214 while (n-- > 0) { 215 Handle<String> s; 216 p = ReadSymbol(p, &s); 217 list->Add(s); 218 } 219 return p; 220} 221 222 223template <class Allocator> 224static Object** ReadList(Object** p, 225 List<Handle<String>, Allocator>* list, 226 List<Variable::Mode, Allocator>* modes) { 227 ASSERT(list->is_empty()); 228 int n; 229 p = ReadInt(p, &n); 230 while (n-- > 0) { 231 Handle<String> s; 232 int m; 233 p = ReadSymbol(p, &s); 234 p = ReadInt(p, &m); 235 list->Add(s); 236 modes->Add(static_cast<Variable::Mode>(m)); 237 } 238 return p; 239} 240 241 242template<class Allocator> 243ScopeInfo<Allocator>::ScopeInfo(SerializedScopeInfo* data) 244 : function_name_(FACTORY->empty_symbol()), 245 parameters_(4), 246 stack_slots_(8), 247 context_slots_(8), 248 context_modes_(8) { 249 if (data->length() > 0) { 250 Object** p0 = data->data_start(); 251 Object** p = p0; 252 p = ReadSymbol(p, &function_name_); 253 p = ReadBool(p, &calls_eval_); 254 p = ReadBool(p, &is_strict_mode_); 255 p = ReadList<Allocator>(p, &context_slots_, &context_modes_); 256 p = ReadList<Allocator>(p, ¶meters_); 257 p = ReadList<Allocator>(p, &stack_slots_); 258 ASSERT((p - p0) == FixedArray::cast(data)->length()); 259 } 260} 261 262 263static inline Object** WriteInt(Object** p, int x) { 264 *p++ = Smi::FromInt(x); 265 return p; 266} 267 268 269static inline Object** WriteBool(Object** p, bool b) { 270 *p++ = Smi::FromInt(b ? 1 : 0); 271 return p; 272} 273 274 275static inline Object** WriteSymbol(Object** p, Handle<String> s) { 276 *p++ = *s; 277 return p; 278} 279 280 281template <class Allocator> 282static Object** WriteList(Object** p, List<Handle<String>, Allocator >* list) { 283 const int n = list->length(); 284 p = WriteInt(p, n); 285 for (int i = 0; i < n; i++) { 286 p = WriteSymbol(p, list->at(i)); 287 } 288 return p; 289} 290 291 292template <class Allocator> 293static Object** WriteList(Object** p, 294 List<Handle<String>, Allocator>* list, 295 List<Variable::Mode, Allocator>* modes) { 296 const int n = list->length(); 297 p = WriteInt(p, n); 298 for (int i = 0; i < n; i++) { 299 p = WriteSymbol(p, list->at(i)); 300 p = WriteInt(p, modes->at(i)); 301 } 302 return p; 303} 304 305 306template<class Allocator> 307Handle<SerializedScopeInfo> ScopeInfo<Allocator>::Serialize() { 308 // function name, calls eval, is_strict_mode, length for 3 tables: 309 const int extra_slots = 1 + 1 + 1 + 3; 310 int length = extra_slots + 311 context_slots_.length() * 2 + 312 parameters_.length() + 313 stack_slots_.length(); 314 315 Handle<SerializedScopeInfo> data( 316 SerializedScopeInfo::cast(*FACTORY->NewSerializedScopeInfo(length))); 317 AssertNoAllocation nogc; 318 319 Object** p0 = data->data_start(); 320 Object** p = p0; 321 p = WriteSymbol(p, function_name_); 322 p = WriteBool(p, calls_eval_); 323 p = WriteBool(p, is_strict_mode_); 324 p = WriteList(p, &context_slots_, &context_modes_); 325 p = WriteList(p, ¶meters_); 326 p = WriteList(p, &stack_slots_); 327 ASSERT((p - p0) == length); 328 329 return data; 330} 331 332 333template<class Allocator> 334Handle<String> ScopeInfo<Allocator>::LocalName(int i) const { 335 // A local variable can be allocated either on the stack or in the context. 336 // For variables allocated in the context they are always preceded by 337 // Context::MIN_CONTEXT_SLOTS of fixed allocated slots in the context. 338 if (i < number_of_stack_slots()) { 339 return stack_slot_name(i); 340 } else { 341 return context_slot_name(i - number_of_stack_slots() + 342 Context::MIN_CONTEXT_SLOTS); 343 } 344} 345 346 347template<class Allocator> 348int ScopeInfo<Allocator>::NumberOfLocals() const { 349 int number_of_locals = number_of_stack_slots(); 350 if (number_of_context_slots() > 0) { 351 ASSERT(number_of_context_slots() >= Context::MIN_CONTEXT_SLOTS); 352 number_of_locals += number_of_context_slots() - Context::MIN_CONTEXT_SLOTS; 353 } 354 return number_of_locals; 355} 356 357 358Handle<SerializedScopeInfo> SerializedScopeInfo::Create(Scope* scope) { 359 ScopeInfo<ZoneListAllocationPolicy> sinfo(scope); 360 return sinfo.Serialize(); 361} 362 363 364SerializedScopeInfo* SerializedScopeInfo::Empty() { 365 return reinterpret_cast<SerializedScopeInfo*>(HEAP->empty_fixed_array()); 366} 367 368 369Object** SerializedScopeInfo::ContextEntriesAddr() { 370 ASSERT(length() > 0); 371 // +3 for function name, calls eval, strict mode. 372 return data_start() + 3; 373} 374 375 376Object** SerializedScopeInfo::ParameterEntriesAddr() { 377 ASSERT(length() > 0); 378 Object** p = ContextEntriesAddr(); 379 int number_of_context_slots; 380 p = ReadInt(p, &number_of_context_slots); 381 return p + number_of_context_slots*2; // *2 for pairs 382} 383 384 385Object** SerializedScopeInfo::StackSlotEntriesAddr() { 386 ASSERT(length() > 0); 387 Object** p = ParameterEntriesAddr(); 388 int number_of_parameter_slots; 389 p = ReadInt(p, &number_of_parameter_slots); 390 return p + number_of_parameter_slots; 391} 392 393 394bool SerializedScopeInfo::CallsEval() { 395 if (length() > 0) { 396 Object** p = data_start() + 1; // +1 for function name. 397 bool calls_eval; 398 p = ReadBool(p, &calls_eval); 399 return calls_eval; 400 } 401 return false; 402} 403 404 405bool SerializedScopeInfo::IsStrictMode() { 406 if (length() > 0) { 407 Object** p = data_start() + 2; // +2 for function name, calls eval. 408 bool strict_mode; 409 p = ReadBool(p, &strict_mode); 410 return strict_mode; 411 } 412 return false; 413} 414 415 416int SerializedScopeInfo::NumberOfStackSlots() { 417 if (length() > 0) { 418 Object** p = StackSlotEntriesAddr(); 419 int number_of_stack_slots; 420 ReadInt(p, &number_of_stack_slots); 421 return number_of_stack_slots; 422 } 423 return 0; 424} 425 426 427int SerializedScopeInfo::NumberOfContextSlots() { 428 if (length() > 0) { 429 Object** p = ContextEntriesAddr(); 430 int number_of_context_slots; 431 ReadInt(p, &number_of_context_slots); 432 return number_of_context_slots + Context::MIN_CONTEXT_SLOTS; 433 } 434 return 0; 435} 436 437 438bool SerializedScopeInfo::HasHeapAllocatedLocals() { 439 if (length() > 0) { 440 Object** p = ContextEntriesAddr(); 441 int number_of_context_slots; 442 ReadInt(p, &number_of_context_slots); 443 return number_of_context_slots > 0; 444 } 445 return false; 446} 447 448 449int SerializedScopeInfo::StackSlotIndex(String* name) { 450 ASSERT(name->IsSymbol()); 451 if (length() > 0) { 452 // Slots start after length entry. 453 Object** p0 = StackSlotEntriesAddr(); 454 int number_of_stack_slots; 455 p0 = ReadInt(p0, &number_of_stack_slots); 456 Object** p = p0; 457 Object** end = p0 + number_of_stack_slots; 458 while (p != end) { 459 if (*p == name) return static_cast<int>(p - p0); 460 p++; 461 } 462 } 463 return -1; 464} 465 466int SerializedScopeInfo::ContextSlotIndex(String* name, Variable::Mode* mode) { 467 ASSERT(name->IsSymbol()); 468 Isolate* isolate = GetIsolate(); 469 int result = isolate->context_slot_cache()->Lookup(this, name, mode); 470 if (result != ContextSlotCache::kNotFound) return result; 471 if (length() > 0) { 472 // Slots start after length entry. 473 Object** p0 = ContextEntriesAddr(); 474 int number_of_context_slots; 475 p0 = ReadInt(p0, &number_of_context_slots); 476 Object** p = p0; 477 Object** end = p0 + number_of_context_slots * 2; 478 while (p != end) { 479 if (*p == name) { 480 ASSERT(((p - p0) & 1) == 0); 481 int v; 482 ReadInt(p + 1, &v); 483 Variable::Mode mode_value = static_cast<Variable::Mode>(v); 484 if (mode != NULL) *mode = mode_value; 485 result = static_cast<int>((p - p0) >> 1) + Context::MIN_CONTEXT_SLOTS; 486 isolate->context_slot_cache()->Update(this, name, mode_value, result); 487 return result; 488 } 489 p += 2; 490 } 491 } 492 isolate->context_slot_cache()->Update(this, name, Variable::INTERNAL, -1); 493 return -1; 494} 495 496 497int SerializedScopeInfo::ParameterIndex(String* name) { 498 ASSERT(name->IsSymbol()); 499 if (length() > 0) { 500 // We must read parameters from the end since for 501 // multiply declared parameters the value of the 502 // last declaration of that parameter is used 503 // inside a function (and thus we need to look 504 // at the last index). Was bug# 1110337. 505 // 506 // Eventually, we should only register such parameters 507 // once, with corresponding index. This requires a new 508 // implementation of the ScopeInfo code. See also other 509 // comments in this file regarding this. 510 Object** p = ParameterEntriesAddr(); 511 int number_of_parameter_slots; 512 Object** p0 = ReadInt(p, &number_of_parameter_slots); 513 p = p0 + number_of_parameter_slots; 514 while (p > p0) { 515 p--; 516 if (*p == name) return static_cast<int>(p - p0); 517 } 518 } 519 return -1; 520} 521 522 523int SerializedScopeInfo::FunctionContextSlotIndex(String* name) { 524 ASSERT(name->IsSymbol()); 525 if (length() > 0) { 526 Object** p = data_start(); 527 if (*p == name) { 528 p = ContextEntriesAddr(); 529 int number_of_context_slots; 530 ReadInt(p, &number_of_context_slots); 531 ASSERT(number_of_context_slots != 0); 532 // The function context slot is the last entry. 533 return number_of_context_slots + Context::MIN_CONTEXT_SLOTS - 1; 534 } 535 } 536 return -1; 537} 538 539 540int ContextSlotCache::Hash(Object* data, String* name) { 541 // Uses only lower 32 bits if pointers are larger. 542 uintptr_t addr_hash = 543 static_cast<uint32_t>(reinterpret_cast<uintptr_t>(data)) >> 2; 544 return static_cast<int>((addr_hash ^ name->Hash()) % kLength); 545} 546 547 548int ContextSlotCache::Lookup(Object* data, 549 String* name, 550 Variable::Mode* mode) { 551 int index = Hash(data, name); 552 Key& key = keys_[index]; 553 if ((key.data == data) && key.name->Equals(name)) { 554 Value result(values_[index]); 555 if (mode != NULL) *mode = result.mode(); 556 return result.index() + kNotFound; 557 } 558 return kNotFound; 559} 560 561 562void ContextSlotCache::Update(Object* data, 563 String* name, 564 Variable::Mode mode, 565 int slot_index) { 566 String* symbol; 567 ASSERT(slot_index > kNotFound); 568 if (HEAP->LookupSymbolIfExists(name, &symbol)) { 569 int index = Hash(data, symbol); 570 Key& key = keys_[index]; 571 key.data = data; 572 key.name = symbol; 573 // Please note value only takes a uint as index. 574 values_[index] = Value(mode, slot_index - kNotFound).raw(); 575#ifdef DEBUG 576 ValidateEntry(data, name, mode, slot_index); 577#endif 578 } 579} 580 581 582void ContextSlotCache::Clear() { 583 for (int index = 0; index < kLength; index++) keys_[index].data = NULL; 584} 585 586 587#ifdef DEBUG 588 589void ContextSlotCache::ValidateEntry(Object* data, 590 String* name, 591 Variable::Mode mode, 592 int slot_index) { 593 String* symbol; 594 if (HEAP->LookupSymbolIfExists(name, &symbol)) { 595 int index = Hash(data, name); 596 Key& key = keys_[index]; 597 ASSERT(key.data == data); 598 ASSERT(key.name->Equals(name)); 599 Value result(values_[index]); 600 ASSERT(result.mode() == mode); 601 ASSERT(result.index() + kNotFound == slot_index); 602 } 603} 604 605 606template <class Allocator> 607static void PrintList(const char* list_name, 608 int nof_internal_slots, 609 List<Handle<String>, Allocator>& list) { 610 if (list.length() > 0) { 611 PrintF("\n // %s\n", list_name); 612 if (nof_internal_slots > 0) { 613 PrintF(" %2d - %2d [internal slots]\n", 0 , nof_internal_slots - 1); 614 } 615 for (int i = 0; i < list.length(); i++) { 616 PrintF(" %2d ", i + nof_internal_slots); 617 list[i]->ShortPrint(); 618 PrintF("\n"); 619 } 620 } 621} 622 623 624template<class Allocator> 625void ScopeInfo<Allocator>::Print() { 626 PrintF("ScopeInfo "); 627 if (function_name_->length() > 0) 628 function_name_->ShortPrint(); 629 else 630 PrintF("/* no function name */"); 631 PrintF("{"); 632 633 PrintList<Allocator>("parameters", 0, parameters_); 634 PrintList<Allocator>("stack slots", 0, stack_slots_); 635 PrintList<Allocator>("context slots", Context::MIN_CONTEXT_SLOTS, 636 context_slots_); 637 638 PrintF("}\n"); 639} 640#endif // DEBUG 641 642 643// Make sure the classes get instantiated by the template system. 644template class ScopeInfo<FreeStoreAllocationPolicy>; 645template class ScopeInfo<PreallocatedStorage>; 646template class ScopeInfo<ZoneListAllocationPolicy>; 647 648} } // namespace v8::internal 649