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