scopeinfo.cc revision 9dcf7e2f83591d471e88bf7d230651900b8e424b
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)->slot(); 41 Slot* t = (*w)->slot(); 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->slot(); 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]->slot()->index() - Context::MIN_CONTEXT_SLOTS == 116 context_slots_.length()); 117 ASSERT(heap_locals[i]->slot()->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->slot()->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->slot()->index() - Context::MIN_CONTEXT_SLOTS == 141 context_slots_.length()); 142 ASSERT(var->slot()->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 the Code 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 207static inline Object** ReadSentinel(Object** p) { 208 ASSERT(*p == NULL); 209 return p + 1; 210} 211 212 213template <class Allocator> 214static Object** ReadList(Object** p, List<Handle<String>, Allocator >* list) { 215 ASSERT(list->is_empty()); 216 int n; 217 p = ReadInt(p, &n); 218 while (n-- > 0) { 219 Handle<String> s; 220 p = ReadSymbol(p, &s); 221 list->Add(s); 222 } 223 return ReadSentinel(p); 224} 225 226 227template <class Allocator> 228static Object** ReadList(Object** p, 229 List<Handle<String>, Allocator>* list, 230 List<Variable::Mode, Allocator>* modes) { 231 ASSERT(list->is_empty()); 232 int n; 233 p = ReadInt(p, &n); 234 while (n-- > 0) { 235 Handle<String> s; 236 int m; 237 p = ReadSymbol(p, &s); 238 p = ReadInt(p, &m); 239 list->Add(s); 240 modes->Add(static_cast<Variable::Mode>(m)); 241 } 242 return ReadSentinel(p); 243} 244 245 246template<class Allocator> 247ScopeInfo<Allocator>::ScopeInfo(Code* code) 248 : function_name_(Factory::empty_symbol()), 249 parameters_(4), 250 stack_slots_(8), 251 context_slots_(8), 252 context_modes_(8) { 253 if (code == NULL || code->sinfo_size() == 0) return; 254 255 Object** p0 = &Memory::Object_at(code->sinfo_start()); 256 Object** p = p0; 257 p = ReadSymbol(p, &function_name_); 258 p = ReadBool(p, &calls_eval_); 259 p = ReadList<Allocator>(p, &context_slots_, &context_modes_); 260 p = ReadList<Allocator>(p, ¶meters_); 261 p = ReadList<Allocator>(p, &stack_slots_); 262 ASSERT((p - p0) * kPointerSize == code->sinfo_size()); 263} 264 265 266static inline Object** WriteInt(Object** p, int x) { 267 *p++ = Smi::FromInt(x); 268 return p; 269} 270 271 272static inline Object** WriteBool(Object** p, bool b) { 273 *p++ = Smi::FromInt(b ? 1 : 0); 274 return p; 275} 276 277 278static inline Object** WriteSymbol(Object** p, Handle<String> s) { 279 *p++ = *s; 280 return p; 281} 282 283 284static inline Object** WriteSentinel(Object** p) { 285 *p++ = NULL; 286 return p; 287} 288 289 290template <class Allocator> 291static Object** WriteList(Object** p, List<Handle<String>, Allocator >* list) { 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 } 297 return WriteSentinel(p); 298} 299 300 301template <class Allocator> 302static Object** WriteList(Object** p, 303 List<Handle<String>, Allocator>* list, 304 List<Variable::Mode, Allocator>* modes) { 305 const int n = list->length(); 306 p = WriteInt(p, n); 307 for (int i = 0; i < n; i++) { 308 p = WriteSymbol(p, list->at(i)); 309 p = WriteInt(p, modes->at(i)); 310 } 311 return WriteSentinel(p); 312} 313 314 315template<class Allocator> 316int ScopeInfo<Allocator>::Serialize(Code* code) { 317 // function name, calls eval, length & sentinel for 3 tables: 318 const int extra_slots = 1 + 1 + 2 * 3; 319 int size = (extra_slots + 320 context_slots_.length() * 2 + 321 parameters_.length() + 322 stack_slots_.length()) * kPointerSize; 323 324 if (code != NULL) { 325 CHECK(code->sinfo_size() == size); 326 Object** p0 = &Memory::Object_at(code->sinfo_start()); 327 Object** p = p0; 328 p = WriteSymbol(p, function_name_); 329 p = WriteBool(p, calls_eval_); 330 p = WriteList(p, &context_slots_, &context_modes_); 331 p = WriteList(p, ¶meters_); 332 p = WriteList(p, &stack_slots_); 333 ASSERT((p - p0) * kPointerSize == size); 334 } 335 336 return size; 337} 338 339 340template<class Allocator> 341void ScopeInfo<Allocator>::IterateScopeInfo(Code* code, ObjectVisitor* v) { 342 Object** start = &Memory::Object_at(code->sinfo_start()); 343 Object** end = &Memory::Object_at(code->sinfo_start() + code->sinfo_size()); 344 v->VisitPointers(start, end); 345} 346 347 348static Object** ContextEntriesAddr(Code* code) { 349 ASSERT(code->sinfo_size() > 0); 350 // +2 for function name and calls eval: 351 return &Memory::Object_at(code->sinfo_start()) + 2; 352} 353 354 355static Object** ParameterEntriesAddr(Code* code) { 356 ASSERT(code->sinfo_size() > 0); 357 Object** p = ContextEntriesAddr(code); 358 int n; // number of context slots; 359 p = ReadInt(p, &n); 360 return p + n*2 + 1; // *2 for pairs, +1 for sentinel 361} 362 363 364static Object** StackSlotEntriesAddr(Code* code) { 365 ASSERT(code->sinfo_size() > 0); 366 Object** p = ParameterEntriesAddr(code); 367 int n; // number of parameter slots; 368 p = ReadInt(p, &n); 369 return p + n + 1; // +1 for sentinel 370} 371 372 373template<class Allocator> 374bool ScopeInfo<Allocator>::CallsEval(Code* code) { 375 if (code->sinfo_size() > 0) { 376 // +1 for function name: 377 Object** p = &Memory::Object_at(code->sinfo_start()) + 1; 378 bool calls_eval; 379 p = ReadBool(p, &calls_eval); 380 return calls_eval; 381 } 382 return true; 383} 384 385 386template<class Allocator> 387int ScopeInfo<Allocator>::NumberOfStackSlots(Code* code) { 388 if (code->sinfo_size() > 0) { 389 Object** p = StackSlotEntriesAddr(code); 390 int n; // number of stack slots; 391 ReadInt(p, &n); 392 return n; 393 } 394 return 0; 395} 396 397 398template<class Allocator> 399int ScopeInfo<Allocator>::NumberOfContextSlots(Code* code) { 400 if (code->sinfo_size() > 0) { 401 Object** p = ContextEntriesAddr(code); 402 int n; // number of context slots; 403 ReadInt(p, &n); 404 return n + Context::MIN_CONTEXT_SLOTS; 405 } 406 return 0; 407} 408 409 410template<class Allocator> 411bool ScopeInfo<Allocator>::HasHeapAllocatedLocals(Code* code) { 412 if (code->sinfo_size() > 0) { 413 Object** p = ContextEntriesAddr(code); 414 int n; // number of context slots; 415 ReadInt(p, &n); 416 return n > 0; 417 } 418 return false; 419} 420 421 422template<class Allocator> 423int ScopeInfo<Allocator>::StackSlotIndex(Code* code, String* name) { 424 ASSERT(name->IsSymbol()); 425 if (code->sinfo_size() > 0) { 426 // Loop below depends on the NULL sentinel after the stack slot names. 427 ASSERT(NumberOfStackSlots(code) > 0 || 428 *(StackSlotEntriesAddr(code) + 1) == NULL); 429 // slots start after length entry 430 Object** p0 = StackSlotEntriesAddr(code) + 1; 431 Object** p = p0; 432 while (*p != NULL) { 433 if (*p == name) return static_cast<int>(p - p0); 434 p++; 435 } 436 } 437 return -1; 438} 439 440 441template<class Allocator> 442int ScopeInfo<Allocator>::ContextSlotIndex(Code* code, 443 String* name, 444 Variable::Mode* mode) { 445 ASSERT(name->IsSymbol()); 446 int result = ContextSlotCache::Lookup(code, name, mode); 447 if (result != ContextSlotCache::kNotFound) return result; 448 if (code->sinfo_size() > 0) { 449 // Loop below depends on the NULL sentinel after the context slot names. 450 ASSERT(NumberOfContextSlots(code) >= Context::MIN_CONTEXT_SLOTS || 451 *(ContextEntriesAddr(code) + 1) == NULL); 452 453 // slots start after length entry 454 Object** p0 = ContextEntriesAddr(code) + 1; 455 Object** p = p0; 456 // contexts may have no variable slots (in the presence of eval()). 457 while (*p != NULL) { 458 if (*p == name) { 459 ASSERT(((p - p0) & 1) == 0); 460 int v; 461 ReadInt(p + 1, &v); 462 Variable::Mode mode_value = static_cast<Variable::Mode>(v); 463 if (mode != NULL) *mode = mode_value; 464 result = static_cast<int>((p - p0) >> 1) + Context::MIN_CONTEXT_SLOTS; 465 ContextSlotCache::Update(code, name, mode_value, result); 466 return result; 467 } 468 p += 2; 469 } 470 } 471 ContextSlotCache::Update(code, name, Variable::INTERNAL, -1); 472 return -1; 473} 474 475 476template<class Allocator> 477int ScopeInfo<Allocator>::ParameterIndex(Code* code, String* name) { 478 ASSERT(name->IsSymbol()); 479 if (code->sinfo_size() > 0) { 480 // We must read parameters from the end since for 481 // multiply declared parameters the value of the 482 // last declaration of that parameter is used 483 // inside a function (and thus we need to look 484 // at the last index). Was bug# 1110337. 485 // 486 // Eventually, we should only register such parameters 487 // once, with corresponding index. This requires a new 488 // implementation of the ScopeInfo code. See also other 489 // comments in this file regarding this. 490 Object** p = ParameterEntriesAddr(code); 491 int n; // number of parameters 492 Object** p0 = ReadInt(p, &n); 493 p = p0 + n; 494 while (p > p0) { 495 p--; 496 if (*p == name) return static_cast<int>(p - p0); 497 } 498 } 499 return -1; 500} 501 502 503template<class Allocator> 504int ScopeInfo<Allocator>::FunctionContextSlotIndex(Code* code, String* name) { 505 ASSERT(name->IsSymbol()); 506 if (code->sinfo_size() > 0) { 507 Object** p = &Memory::Object_at(code->sinfo_start()); 508 if (*p == name) { 509 p = ContextEntriesAddr(code); 510 int n; // number of context slots 511 ReadInt(p, &n); 512 ASSERT(n != 0); 513 // The function context slot is the last entry. 514 return n + Context::MIN_CONTEXT_SLOTS - 1; 515 } 516 } 517 return -1; 518} 519 520 521template<class Allocator> 522Handle<String> ScopeInfo<Allocator>::LocalName(int i) const { 523 // A local variable can be allocated either on the stack or in the context. 524 // For variables allocated in the context they are always preceded by the 525 // number Context::MIN_CONTEXT_SLOTS number of fixed allocated slots in the 526 // context. 527 if (i < number_of_stack_slots()) { 528 return stack_slot_name(i); 529 } else { 530 return context_slot_name(i - number_of_stack_slots() + 531 Context::MIN_CONTEXT_SLOTS); 532 } 533} 534 535 536template<class Allocator> 537int ScopeInfo<Allocator>::NumberOfLocals() const { 538 int number_of_locals = number_of_stack_slots(); 539 if (number_of_context_slots() > 0) { 540 ASSERT(number_of_context_slots() >= Context::MIN_CONTEXT_SLOTS); 541 number_of_locals += number_of_context_slots() - Context::MIN_CONTEXT_SLOTS; 542 } 543 return number_of_locals; 544} 545 546 547int ContextSlotCache::Hash(Code* code, String* name) { 548 // Uses only lower 32 bits if pointers are larger. 549 uintptr_t addr_hash = 550 static_cast<uint32_t>(reinterpret_cast<uintptr_t>(code)) >> 2; 551 return static_cast<int>((addr_hash ^ name->Hash()) % kLength); 552} 553 554 555int ContextSlotCache::Lookup(Code* code, 556 String* name, 557 Variable::Mode* mode) { 558 int index = Hash(code, name); 559 Key& key = keys_[index]; 560 if ((key.code == code) && key.name->Equals(name)) { 561 Value result(values_[index]); 562 if (mode != NULL) *mode = result.mode(); 563 return result.index() + kNotFound; 564 } 565 return kNotFound; 566} 567 568 569void ContextSlotCache::Update(Code* code, 570 String* name, 571 Variable::Mode mode, 572 int slot_index) { 573 String* symbol; 574 ASSERT(slot_index > kNotFound); 575 if (Heap::LookupSymbolIfExists(name, &symbol)) { 576 int index = Hash(code, symbol); 577 Key& key = keys_[index]; 578 key.code = code; 579 key.name = symbol; 580 // Please note value only takes a uint as index. 581 values_[index] = Value(mode, slot_index - kNotFound).raw(); 582#ifdef DEBUG 583 ValidateEntry(code, name, mode, slot_index); 584#endif 585 } 586} 587 588 589void ContextSlotCache::Clear() { 590 for (int index = 0; index < kLength; index++) keys_[index].code = NULL; 591} 592 593 594ContextSlotCache::Key ContextSlotCache::keys_[ContextSlotCache::kLength]; 595 596 597uint32_t ContextSlotCache::values_[ContextSlotCache::kLength]; 598 599 600#ifdef DEBUG 601 602void ContextSlotCache::ValidateEntry(Code* code, 603 String* name, 604 Variable::Mode mode, 605 int slot_index) { 606 String* symbol; 607 if (Heap::LookupSymbolIfExists(name, &symbol)) { 608 int index = Hash(code, name); 609 Key& key = keys_[index]; 610 ASSERT(key.code == code); 611 ASSERT(key.name->Equals(name)); 612 Value result(values_[index]); 613 ASSERT(result.mode() == mode); 614 ASSERT(result.index() + kNotFound == slot_index); 615 } 616} 617 618 619template <class Allocator> 620static void PrintList(const char* list_name, 621 int nof_internal_slots, 622 List<Handle<String>, Allocator>& list) { 623 if (list.length() > 0) { 624 PrintF("\n // %s\n", list_name); 625 if (nof_internal_slots > 0) { 626 PrintF(" %2d - %2d [internal slots]\n", 0 , nof_internal_slots - 1); 627 } 628 for (int i = 0; i < list.length(); i++) { 629 PrintF(" %2d ", i + nof_internal_slots); 630 list[i]->ShortPrint(); 631 PrintF("\n"); 632 } 633 } 634} 635 636 637template<class Allocator> 638void ScopeInfo<Allocator>::Print() { 639 PrintF("ScopeInfo "); 640 if (function_name_->length() > 0) 641 function_name_->ShortPrint(); 642 else 643 PrintF("/* no function name */"); 644 PrintF("{"); 645 646 PrintList<Allocator>("parameters", 0, parameters_); 647 PrintList<Allocator>("stack slots", 0, stack_slots_); 648 PrintList<Allocator>("context slots", Context::MIN_CONTEXT_SLOTS, 649 context_slots_); 650 651 PrintF("}\n"); 652} 653#endif // DEBUG 654 655 656// Make sure the classes get instantiated by the template system. 657template class ScopeInfo<FreeStoreAllocationPolicy>; 658template class ScopeInfo<PreallocatedStorage>; 659template class ScopeInfo<ZoneListAllocationPolicy>; 660 661} } // namespace v8::internal 662