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)->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 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->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 // 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->var_uses()->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 189 static inline Object** ReadInt(Object** p, int* x) { 190 *x = (reinterpret_cast<Smi*>(*p++))->value(); 191 return p; 192 } 193 194 195 static inline Object** ReadBool(Object** p, bool* x) { 196 *x = (reinterpret_cast<Smi*>(*p++))->value() != 0; 197 return p; 198 } 199 200 201 static inline Object** ReadSymbol(Object** p, Handle<String>* s) { 202 *s = Handle<String>(reinterpret_cast<String*>(*p++)); 203 return p; 204 } 205 206 207 static inline Object** ReadSentinel(Object** p) { 208 ASSERT(*p == NULL); 209 return p + 1; 210 } 211 212 213 template <class Allocator> 214 static 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 227 template <class Allocator> 228 static 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 246 template<class Allocator> 247 ScopeInfo<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 266 static inline Object** WriteInt(Object** p, int x) { 267 *p++ = Smi::FromInt(x); 268 return p; 269 } 270 271 272 static inline Object** WriteBool(Object** p, bool b) { 273 *p++ = Smi::FromInt(b ? 1 : 0); 274 return p; 275 } 276 277 278 static inline Object** WriteSymbol(Object** p, Handle<String> s) { 279 *p++ = *s; 280 return p; 281 } 282 283 284 static inline Object** WriteSentinel(Object** p) { 285 *p++ = NULL; 286 return p; 287 } 288 289 290 template <class Allocator> 291 static 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 301 template <class Allocator> 302 static 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 315 template<class Allocator> 316 int 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 340 template<class Allocator> 341 void 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 348 static 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 355 static 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 364 static 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 373 template<class Allocator> 374 bool 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 386 template<class Allocator> 387 int 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 398 template<class Allocator> 399 int 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 410 template<class Allocator> 411 int ScopeInfo<Allocator>::StackSlotIndex(Code* code, String* name) { 412 ASSERT(name->IsSymbol()); 413 if (code->sinfo_size() > 0) { 414 // Loop below depends on the NULL sentinel after the stack slot names. 415 ASSERT(NumberOfStackSlots(code) > 0 || 416 *(StackSlotEntriesAddr(code) + 1) == NULL); 417 // slots start after length entry 418 Object** p0 = StackSlotEntriesAddr(code) + 1; 419 Object** p = p0; 420 while (*p != NULL) { 421 if (*p == name) return static_cast<int>(p - p0); 422 p++; 423 } 424 } 425 return -1; 426 } 427 428 429 template<class Allocator> 430 int ScopeInfo<Allocator>::ContextSlotIndex(Code* code, 431 String* name, 432 Variable::Mode* mode) { 433 ASSERT(name->IsSymbol()); 434 int result = ContextSlotCache::Lookup(code, name, mode); 435 if (result != ContextSlotCache::kNotFound) return result; 436 if (code->sinfo_size() > 0) { 437 // Loop below depends on the NULL sentinel after the context slot names. 438 ASSERT(NumberOfContextSlots(code) >= Context::MIN_CONTEXT_SLOTS || 439 *(ContextEntriesAddr(code) + 1) == NULL); 440 441 // slots start after length entry 442 Object** p0 = ContextEntriesAddr(code) + 1; 443 Object** p = p0; 444 // contexts may have no variable slots (in the presence of eval()). 445 while (*p != NULL) { 446 if (*p == name) { 447 ASSERT(((p - p0) & 1) == 0); 448 int v; 449 ReadInt(p + 1, &v); 450 Variable::Mode mode_value = static_cast<Variable::Mode>(v); 451 if (mode != NULL) *mode = mode_value; 452 result = static_cast<int>((p - p0) >> 1) + Context::MIN_CONTEXT_SLOTS; 453 ContextSlotCache::Update(code, name, mode_value, result); 454 return result; 455 } 456 p += 2; 457 } 458 } 459 ContextSlotCache::Update(code, name, Variable::INTERNAL, -1); 460 return -1; 461 } 462 463 464 template<class Allocator> 465 int ScopeInfo<Allocator>::ParameterIndex(Code* code, String* name) { 466 ASSERT(name->IsSymbol()); 467 if (code->sinfo_size() > 0) { 468 // We must read parameters from the end since for 469 // multiply declared parameters the value of the 470 // last declaration of that parameter is used 471 // inside a function (and thus we need to look 472 // at the last index). Was bug# 1110337. 473 // 474 // Eventually, we should only register such parameters 475 // once, with corresponding index. This requires a new 476 // implementation of the ScopeInfo code. See also other 477 // comments in this file regarding this. 478 Object** p = ParameterEntriesAddr(code); 479 int n; // number of parameters 480 Object** p0 = ReadInt(p, &n); 481 p = p0 + n; 482 while (p > p0) { 483 p--; 484 if (*p == name) return static_cast<int>(p - p0); 485 } 486 } 487 return -1; 488 } 489 490 491 template<class Allocator> 492 int ScopeInfo<Allocator>::FunctionContextSlotIndex(Code* code, String* name) { 493 ASSERT(name->IsSymbol()); 494 if (code->sinfo_size() > 0) { 495 Object** p = &Memory::Object_at(code->sinfo_start()); 496 if (*p == name) { 497 p = ContextEntriesAddr(code); 498 int n; // number of context slots 499 ReadInt(p, &n); 500 ASSERT(n != 0); 501 // The function context slot is the last entry. 502 return n + Context::MIN_CONTEXT_SLOTS - 1; 503 } 504 } 505 return -1; 506 } 507 508 509 template<class Allocator> 510 Handle<String> ScopeInfo<Allocator>::LocalName(int i) const { 511 // A local variable can be allocated either on the stack or in the context. 512 // For variables allocated in the context they are always preceded by the 513 // number Context::MIN_CONTEXT_SLOTS number of fixed allocated slots in the 514 // context. 515 if (i < number_of_stack_slots()) { 516 return stack_slot_name(i); 517 } else { 518 return context_slot_name(i - number_of_stack_slots() + 519 Context::MIN_CONTEXT_SLOTS); 520 } 521 } 522 523 524 template<class Allocator> 525 int ScopeInfo<Allocator>::NumberOfLocals() const { 526 int number_of_locals = number_of_stack_slots(); 527 if (number_of_context_slots() > 0) { 528 ASSERT(number_of_context_slots() >= Context::MIN_CONTEXT_SLOTS); 529 number_of_locals += number_of_context_slots() - Context::MIN_CONTEXT_SLOTS; 530 } 531 return number_of_locals; 532 } 533 534 535 int ContextSlotCache::Hash(Code* code, String* name) { 536 // Uses only lower 32 bits if pointers are larger. 537 uintptr_t addr_hash = 538 static_cast<uint32_t>(reinterpret_cast<uintptr_t>(code)) >> 2; 539 return static_cast<int>((addr_hash ^ name->Hash()) % kLength); 540 } 541 542 543 int ContextSlotCache::Lookup(Code* code, 544 String* name, 545 Variable::Mode* mode) { 546 int index = Hash(code, name); 547 Key& key = keys_[index]; 548 if ((key.code == code) && key.name->Equals(name)) { 549 Value result(values_[index]); 550 if (mode != NULL) *mode = result.mode(); 551 return result.index() + kNotFound; 552 } 553 return kNotFound; 554 } 555 556 557 void ContextSlotCache::Update(Code* code, 558 String* name, 559 Variable::Mode mode, 560 int slot_index) { 561 String* symbol; 562 ASSERT(slot_index > kNotFound); 563 if (Heap::LookupSymbolIfExists(name, &symbol)) { 564 int index = Hash(code, symbol); 565 Key& key = keys_[index]; 566 key.code = code; 567 key.name = symbol; 568 // Please note value only takes a uint as index. 569 values_[index] = Value(mode, slot_index - kNotFound).raw(); 570 #ifdef DEBUG 571 ValidateEntry(code, name, mode, slot_index); 572 #endif 573 } 574 } 575 576 577 void ContextSlotCache::Clear() { 578 for (int index = 0; index < kLength; index++) keys_[index].code = NULL; 579 } 580 581 582 ContextSlotCache::Key ContextSlotCache::keys_[ContextSlotCache::kLength]; 583 584 585 uint32_t ContextSlotCache::values_[ContextSlotCache::kLength]; 586 587 588 #ifdef DEBUG 589 590 void ContextSlotCache::ValidateEntry(Code* code, 591 String* name, 592 Variable::Mode mode, 593 int slot_index) { 594 String* symbol; 595 if (Heap::LookupSymbolIfExists(name, &symbol)) { 596 int index = Hash(code, name); 597 Key& key = keys_[index]; 598 ASSERT(key.code == code); 599 ASSERT(key.name->Equals(name)); 600 Value result(values_[index]); 601 ASSERT(result.mode() == mode); 602 ASSERT(result.index() + kNotFound == slot_index); 603 } 604 } 605 606 607 template <class Allocator> 608 static void PrintList(const char* list_name, 609 int nof_internal_slots, 610 List<Handle<String>, Allocator>& list) { 611 if (list.length() > 0) { 612 PrintF("\n // %s\n", list_name); 613 if (nof_internal_slots > 0) { 614 PrintF(" %2d - %2d [internal slots]\n", 0 , nof_internal_slots - 1); 615 } 616 for (int i = 0; i < list.length(); i++) { 617 PrintF(" %2d ", i + nof_internal_slots); 618 list[i]->ShortPrint(); 619 PrintF("\n"); 620 } 621 } 622 } 623 624 625 template<class Allocator> 626 void ScopeInfo<Allocator>::Print() { 627 PrintF("ScopeInfo "); 628 if (function_name_->length() > 0) 629 function_name_->ShortPrint(); 630 else 631 PrintF("/* no function name */"); 632 PrintF("{"); 633 634 PrintList<Allocator>("parameters", 0, parameters_); 635 PrintList<Allocator>("stack slots", 0, stack_slots_); 636 PrintList<Allocator>("context slots", Context::MIN_CONTEXT_SLOTS, 637 context_slots_); 638 639 PrintF("}\n"); 640 } 641 #endif // DEBUG 642 643 644 // Make sure the classes get instantiated by the template system. 645 template class ScopeInfo<FreeStoreAllocationPolicy>; 646 template class ScopeInfo<PreallocatedStorage>; 647 template class ScopeInfo<ZoneListAllocationPolicy>; 648 649 } } // namespace v8::internal 650