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