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 35 namespace v8 { 36 namespace internal { 37 38 39 static 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 51 template<class Allocator> 52 ScopeInfo<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 // - calls eval boolean flag 156 // 157 // - number of variables in the context object (smi) (= function context 158 // slot index + 1) 159 // - list of pairs (name, Var mode) of context-allocated variables (starting 160 // with context slot 0) 161 // 162 // - number of parameters (smi) 163 // - list of parameter names (starting with parameter 0 first) 164 // 165 // - number of variables on the stack (smi) 166 // - list of names of stack-allocated variables (starting with stack slot 0) 167 168 // The ScopeInfo representation could be simplified and the ScopeInfo 169 // re-implemented (with almost the same interface). Here is a 170 // suggestion for the new format: 171 // 172 // - have a single list with all variable names (parameters, stack locals, 173 // context locals), followed by a list of non-Object* values containing 174 // the variables information (what kind, index, attributes) 175 // - searching the linear list of names is fast and yields an index into the 176 // list if the variable name is found 177 // - that list index is then used to find the variable information in the 178 // subsequent list 179 // - the list entries don't have to be in any particular order, so all the 180 // current sorting business can go away 181 // - the ScopeInfo lookup routines can be reduced to perhaps a single lookup 182 // which returns all information at once 183 // - when gathering the information from a Scope, we only need to iterate 184 // through the local variables (parameters and context info is already 185 // present) 186 187 188 static inline Object** ReadInt(Object** p, int* x) { 189 *x = (reinterpret_cast<Smi*>(*p++))->value(); 190 return p; 191 } 192 193 194 static inline Object** ReadBool(Object** p, bool* x) { 195 *x = (reinterpret_cast<Smi*>(*p++))->value() != 0; 196 return p; 197 } 198 199 200 static inline Object** ReadSymbol(Object** p, Handle<String>* s) { 201 *s = Handle<String>(reinterpret_cast<String*>(*p++)); 202 return p; 203 } 204 205 206 template <class Allocator> 207 static Object** ReadList(Object** p, List<Handle<String>, Allocator >* list) { 208 ASSERT(list->is_empty()); 209 int n; 210 p = ReadInt(p, &n); 211 while (n-- > 0) { 212 Handle<String> s; 213 p = ReadSymbol(p, &s); 214 list->Add(s); 215 } 216 return p; 217 } 218 219 220 template <class Allocator> 221 static Object** ReadList(Object** p, 222 List<Handle<String>, Allocator>* list, 223 List<Variable::Mode, Allocator>* modes) { 224 ASSERT(list->is_empty()); 225 int n; 226 p = ReadInt(p, &n); 227 while (n-- > 0) { 228 Handle<String> s; 229 int m; 230 p = ReadSymbol(p, &s); 231 p = ReadInt(p, &m); 232 list->Add(s); 233 modes->Add(static_cast<Variable::Mode>(m)); 234 } 235 return p; 236 } 237 238 239 template<class Allocator> 240 ScopeInfo<Allocator>::ScopeInfo(SerializedScopeInfo* data) 241 : function_name_(FACTORY->empty_symbol()), 242 parameters_(4), 243 stack_slots_(8), 244 context_slots_(8), 245 context_modes_(8) { 246 if (data->length() > 0) { 247 Object** p0 = data->data_start(); 248 Object** p = p0; 249 p = ReadSymbol(p, &function_name_); 250 p = ReadBool(p, &calls_eval_); 251 p = ReadList<Allocator>(p, &context_slots_, &context_modes_); 252 p = ReadList<Allocator>(p, ¶meters_); 253 p = ReadList<Allocator>(p, &stack_slots_); 254 ASSERT((p - p0) == FixedArray::cast(data)->length()); 255 } 256 } 257 258 259 static inline Object** WriteInt(Object** p, int x) { 260 *p++ = Smi::FromInt(x); 261 return p; 262 } 263 264 265 static inline Object** WriteBool(Object** p, bool b) { 266 *p++ = Smi::FromInt(b ? 1 : 0); 267 return p; 268 } 269 270 271 static inline Object** WriteSymbol(Object** p, Handle<String> s) { 272 *p++ = *s; 273 return p; 274 } 275 276 277 template <class Allocator> 278 static Object** WriteList(Object** p, List<Handle<String>, Allocator >* list) { 279 const int n = list->length(); 280 p = WriteInt(p, n); 281 for (int i = 0; i < n; i++) { 282 p = WriteSymbol(p, list->at(i)); 283 } 284 return p; 285 } 286 287 288 template <class Allocator> 289 static Object** WriteList(Object** p, 290 List<Handle<String>, Allocator>* list, 291 List<Variable::Mode, Allocator>* modes) { 292 const int n = list->length(); 293 p = WriteInt(p, n); 294 for (int i = 0; i < n; i++) { 295 p = WriteSymbol(p, list->at(i)); 296 p = WriteInt(p, modes->at(i)); 297 } 298 return p; 299 } 300 301 302 template<class Allocator> 303 Handle<SerializedScopeInfo> ScopeInfo<Allocator>::Serialize() { 304 // function name, calls eval, length for 3 tables: 305 const int extra_slots = 1 + 1 + 3; 306 int length = extra_slots + 307 context_slots_.length() * 2 + 308 parameters_.length() + 309 stack_slots_.length(); 310 311 Handle<SerializedScopeInfo> data( 312 SerializedScopeInfo::cast(*FACTORY->NewFixedArray(length, TENURED))); 313 AssertNoAllocation nogc; 314 315 Object** p0 = data->data_start(); 316 Object** p = p0; 317 p = WriteSymbol(p, function_name_); 318 p = WriteBool(p, calls_eval_); 319 p = WriteList(p, &context_slots_, &context_modes_); 320 p = WriteList(p, ¶meters_); 321 p = WriteList(p, &stack_slots_); 322 ASSERT((p - p0) == length); 323 324 return data; 325 } 326 327 328 template<class Allocator> 329 Handle<String> ScopeInfo<Allocator>::LocalName(int i) const { 330 // A local variable can be allocated either on the stack or in the context. 331 // For variables allocated in the context they are always preceded by 332 // Context::MIN_CONTEXT_SLOTS of fixed allocated slots in the context. 333 if (i < number_of_stack_slots()) { 334 return stack_slot_name(i); 335 } else { 336 return context_slot_name(i - number_of_stack_slots() + 337 Context::MIN_CONTEXT_SLOTS); 338 } 339 } 340 341 342 template<class Allocator> 343 int ScopeInfo<Allocator>::NumberOfLocals() const { 344 int number_of_locals = number_of_stack_slots(); 345 if (number_of_context_slots() > 0) { 346 ASSERT(number_of_context_slots() >= Context::MIN_CONTEXT_SLOTS); 347 number_of_locals += number_of_context_slots() - Context::MIN_CONTEXT_SLOTS; 348 } 349 return number_of_locals; 350 } 351 352 353 Handle<SerializedScopeInfo> SerializedScopeInfo::Create(Scope* scope) { 354 ScopeInfo<ZoneListAllocationPolicy> sinfo(scope); 355 return sinfo.Serialize(); 356 } 357 358 359 SerializedScopeInfo* SerializedScopeInfo::Empty() { 360 return reinterpret_cast<SerializedScopeInfo*>(HEAP->empty_fixed_array()); 361 } 362 363 364 Object** SerializedScopeInfo::ContextEntriesAddr() { 365 ASSERT(length() > 0); 366 return data_start() + 2; // +2 for function name and calls eval. 367 } 368 369 370 Object** SerializedScopeInfo::ParameterEntriesAddr() { 371 ASSERT(length() > 0); 372 Object** p = ContextEntriesAddr(); 373 int number_of_context_slots; 374 p = ReadInt(p, &number_of_context_slots); 375 return p + number_of_context_slots*2; // *2 for pairs 376 } 377 378 379 Object** SerializedScopeInfo::StackSlotEntriesAddr() { 380 ASSERT(length() > 0); 381 Object** p = ParameterEntriesAddr(); 382 int number_of_parameter_slots; 383 p = ReadInt(p, &number_of_parameter_slots); 384 return p + number_of_parameter_slots; 385 } 386 387 388 bool SerializedScopeInfo::CallsEval() { 389 if (length() > 0) { 390 Object** p = data_start() + 1; // +1 for function name. 391 bool calls_eval; 392 p = ReadBool(p, &calls_eval); 393 return calls_eval; 394 } 395 return true; 396 } 397 398 399 int SerializedScopeInfo::NumberOfStackSlots() { 400 if (length() > 0) { 401 Object** p = StackSlotEntriesAddr(); 402 int number_of_stack_slots; 403 ReadInt(p, &number_of_stack_slots); 404 return number_of_stack_slots; 405 } 406 return 0; 407 } 408 409 410 int SerializedScopeInfo::NumberOfContextSlots() { 411 if (length() > 0) { 412 Object** p = ContextEntriesAddr(); 413 int number_of_context_slots; 414 ReadInt(p, &number_of_context_slots); 415 return number_of_context_slots + Context::MIN_CONTEXT_SLOTS; 416 } 417 return 0; 418 } 419 420 421 bool SerializedScopeInfo::HasHeapAllocatedLocals() { 422 if (length() > 0) { 423 Object** p = ContextEntriesAddr(); 424 int number_of_context_slots; 425 ReadInt(p, &number_of_context_slots); 426 return number_of_context_slots > 0; 427 } 428 return false; 429 } 430 431 432 int SerializedScopeInfo::StackSlotIndex(String* name) { 433 ASSERT(name->IsSymbol()); 434 if (length() > 0) { 435 // Slots start after length entry. 436 Object** p0 = StackSlotEntriesAddr(); 437 int number_of_stack_slots; 438 p0 = ReadInt(p0, &number_of_stack_slots); 439 Object** p = p0; 440 Object** end = p0 + number_of_stack_slots; 441 while (p != end) { 442 if (*p == name) return static_cast<int>(p - p0); 443 p++; 444 } 445 } 446 return -1; 447 } 448 449 int SerializedScopeInfo::ContextSlotIndex(String* name, Variable::Mode* mode) { 450 ASSERT(name->IsSymbol()); 451 Isolate* isolate = GetIsolate(); 452 int result = isolate->context_slot_cache()->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 isolate->context_slot_cache()->Update(this, name, mode_value, result); 470 return result; 471 } 472 p += 2; 473 } 474 } 475 isolate->context_slot_cache()->Update(this, name, Variable::INTERNAL, -1); 476 return -1; 477 } 478 479 480 int 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 506 int 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 523 int 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 531 int 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 545 void 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 565 void ContextSlotCache::Clear() { 566 for (int index = 0; index < kLength; index++) keys_[index].data = NULL; 567 } 568 569 570 #ifdef DEBUG 571 572 void ContextSlotCache::ValidateEntry(Object* data, 573 String* name, 574 Variable::Mode mode, 575 int slot_index) { 576 String* symbol; 577 if (HEAP->LookupSymbolIfExists(name, &symbol)) { 578 int index = Hash(data, name); 579 Key& key = keys_[index]; 580 ASSERT(key.data == data); 581 ASSERT(key.name->Equals(name)); 582 Value result(values_[index]); 583 ASSERT(result.mode() == mode); 584 ASSERT(result.index() + kNotFound == slot_index); 585 } 586 } 587 588 589 template <class Allocator> 590 static void PrintList(const char* list_name, 591 int nof_internal_slots, 592 List<Handle<String>, Allocator>& list) { 593 if (list.length() > 0) { 594 PrintF("\n // %s\n", list_name); 595 if (nof_internal_slots > 0) { 596 PrintF(" %2d - %2d [internal slots]\n", 0 , nof_internal_slots - 1); 597 } 598 for (int i = 0; i < list.length(); i++) { 599 PrintF(" %2d ", i + nof_internal_slots); 600 list[i]->ShortPrint(); 601 PrintF("\n"); 602 } 603 } 604 } 605 606 607 template<class Allocator> 608 void ScopeInfo<Allocator>::Print() { 609 PrintF("ScopeInfo "); 610 if (function_name_->length() > 0) 611 function_name_->ShortPrint(); 612 else 613 PrintF("/* no function name */"); 614 PrintF("{"); 615 616 PrintList<Allocator>("parameters", 0, parameters_); 617 PrintList<Allocator>("stack slots", 0, stack_slots_); 618 PrintList<Allocator>("context slots", Context::MIN_CONTEXT_SLOTS, 619 context_slots_); 620 621 PrintF("}\n"); 622 } 623 #endif // DEBUG 624 625 626 // Make sure the classes get instantiated by the template system. 627 template class ScopeInfo<FreeStoreAllocationPolicy>; 628 template class ScopeInfo<PreallocatedStorage>; 629 template class ScopeInfo<ZoneListAllocationPolicy>; 630 631 } } // namespace v8::internal 632