1 // Copyright 2012 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 #ifndef V8_UTILS_H_ 29 #define V8_UTILS_H_ 30 31 #include <stdlib.h> 32 #include <string.h> 33 #include <algorithm> 34 #include <climits> 35 36 #include "allocation.h" 37 #include "checks.h" 38 #include "globals.h" 39 40 namespace v8 { 41 namespace internal { 42 43 // ---------------------------------------------------------------------------- 44 // General helper functions 45 46 #define IS_POWER_OF_TWO(x) (((x) & ((x) - 1)) == 0) 47 48 // Returns true iff x is a power of 2 (or zero). Cannot be used with the 49 // maximally negative value of the type T (the -1 overflows). 50 template <typename T> 51 inline bool IsPowerOf2(T x) { 52 return IS_POWER_OF_TWO(x); 53 } 54 55 56 // X must be a power of 2. Returns the number of trailing zeros. 57 inline int WhichPowerOf2(uint32_t x) { 58 ASSERT(IsPowerOf2(x)); 59 ASSERT(x != 0); 60 int bits = 0; 61 #ifdef DEBUG 62 int original_x = x; 63 #endif 64 if (x >= 0x10000) { 65 bits += 16; 66 x >>= 16; 67 } 68 if (x >= 0x100) { 69 bits += 8; 70 x >>= 8; 71 } 72 if (x >= 0x10) { 73 bits += 4; 74 x >>= 4; 75 } 76 switch (x) { 77 default: UNREACHABLE(); 78 case 8: bits++; // Fall through. 79 case 4: bits++; // Fall through. 80 case 2: bits++; // Fall through. 81 case 1: break; 82 } 83 ASSERT_EQ(1 << bits, original_x); 84 return bits; 85 return 0; 86 } 87 88 89 inline int MostSignificantBit(uint32_t x) { 90 static const int msb4[] = {0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4}; 91 int nibble = 0; 92 if (x & 0xffff0000) { 93 nibble += 16; 94 x >>= 16; 95 } 96 if (x & 0xff00) { 97 nibble += 8; 98 x >>= 8; 99 } 100 if (x & 0xf0) { 101 nibble += 4; 102 x >>= 4; 103 } 104 return nibble + msb4[x]; 105 } 106 107 108 // Magic numbers for integer division. 109 // These are kind of 2's complement reciprocal of the divisors. 110 // Details and proofs can be found in: 111 // - Hacker's Delight, Henry S. Warren, Jr. 112 // - The PowerPC Compiler Writers Guide 113 // and probably many others. 114 // See details in the implementation of the algorithm in 115 // lithium-codegen-arm.cc : LCodeGen::TryEmitSignedIntegerDivisionByConstant(). 116 struct DivMagicNumbers { 117 unsigned M; 118 unsigned s; 119 }; 120 121 const DivMagicNumbers InvalidDivMagicNumber= {0, 0}; 122 const DivMagicNumbers DivMagicNumberFor3 = {0x55555556, 0}; 123 const DivMagicNumbers DivMagicNumberFor5 = {0x66666667, 1}; 124 const DivMagicNumbers DivMagicNumberFor7 = {0x92492493, 2}; 125 const DivMagicNumbers DivMagicNumberFor9 = {0x38e38e39, 1}; 126 const DivMagicNumbers DivMagicNumberFor11 = {0x2e8ba2e9, 1}; 127 const DivMagicNumbers DivMagicNumberFor25 = {0x51eb851f, 3}; 128 const DivMagicNumbers DivMagicNumberFor125 = {0x10624dd3, 3}; 129 const DivMagicNumbers DivMagicNumberFor625 = {0x68db8bad, 8}; 130 131 const DivMagicNumbers DivMagicNumberFor(int32_t divisor); 132 133 134 // The C++ standard leaves the semantics of '>>' undefined for 135 // negative signed operands. Most implementations do the right thing, 136 // though. 137 inline int ArithmeticShiftRight(int x, int s) { 138 return x >> s; 139 } 140 141 142 // Compute the 0-relative offset of some absolute value x of type T. 143 // This allows conversion of Addresses and integral types into 144 // 0-relative int offsets. 145 template <typename T> 146 inline intptr_t OffsetFrom(T x) { 147 return x - static_cast<T>(0); 148 } 149 150 151 // Compute the absolute value of type T for some 0-relative offset x. 152 // This allows conversion of 0-relative int offsets into Addresses and 153 // integral types. 154 template <typename T> 155 inline T AddressFrom(intptr_t x) { 156 return static_cast<T>(static_cast<T>(0) + x); 157 } 158 159 160 // Return the largest multiple of m which is <= x. 161 template <typename T> 162 inline T RoundDown(T x, intptr_t m) { 163 ASSERT(IsPowerOf2(m)); 164 return AddressFrom<T>(OffsetFrom(x) & -m); 165 } 166 167 168 // Return the smallest multiple of m which is >= x. 169 template <typename T> 170 inline T RoundUp(T x, intptr_t m) { 171 return RoundDown<T>(static_cast<T>(x + m - 1), m); 172 } 173 174 175 template <typename T> 176 int Compare(const T& a, const T& b) { 177 if (a == b) 178 return 0; 179 else if (a < b) 180 return -1; 181 else 182 return 1; 183 } 184 185 186 template <typename T> 187 int PointerValueCompare(const T* a, const T* b) { 188 return Compare<T>(*a, *b); 189 } 190 191 192 // Compare function to compare the object pointer value of two 193 // handlified objects. The handles are passed as pointers to the 194 // handles. 195 template<typename T> class Handle; // Forward declaration. 196 template <typename T> 197 int HandleObjectPointerCompare(const Handle<T>* a, const Handle<T>* b) { 198 return Compare<T*>(*(*a), *(*b)); 199 } 200 201 202 // Returns the smallest power of two which is >= x. If you pass in a 203 // number that is already a power of two, it is returned as is. 204 // Implementation is from "Hacker's Delight" by Henry S. Warren, Jr., 205 // figure 3-3, page 48, where the function is called clp2. 206 inline uint32_t RoundUpToPowerOf2(uint32_t x) { 207 ASSERT(x <= 0x80000000u); 208 x = x - 1; 209 x = x | (x >> 1); 210 x = x | (x >> 2); 211 x = x | (x >> 4); 212 x = x | (x >> 8); 213 x = x | (x >> 16); 214 return x + 1; 215 } 216 217 218 inline uint32_t RoundDownToPowerOf2(uint32_t x) { 219 uint32_t rounded_up = RoundUpToPowerOf2(x); 220 if (rounded_up > x) return rounded_up >> 1; 221 return rounded_up; 222 } 223 224 225 template <typename T, typename U> 226 inline bool IsAligned(T value, U alignment) { 227 return (value & (alignment - 1)) == 0; 228 } 229 230 231 // Returns true if (addr + offset) is aligned. 232 inline bool IsAddressAligned(Address addr, 233 intptr_t alignment, 234 int offset = 0) { 235 intptr_t offs = OffsetFrom(addr + offset); 236 return IsAligned(offs, alignment); 237 } 238 239 240 // Returns the maximum of the two parameters. 241 template <typename T> 242 T Max(T a, T b) { 243 return a < b ? b : a; 244 } 245 246 247 // Returns the minimum of the two parameters. 248 template <typename T> 249 T Min(T a, T b) { 250 return a < b ? a : b; 251 } 252 253 254 // Returns the absolute value of its argument. 255 template <typename T> 256 T Abs(T a) { 257 return a < 0 ? -a : a; 258 } 259 260 261 // Returns the negative absolute value of its argument. 262 template <typename T> 263 T NegAbs(T a) { 264 return a < 0 ? a : -a; 265 } 266 267 268 inline int StrLength(const char* string) { 269 size_t length = strlen(string); 270 ASSERT(length == static_cast<size_t>(static_cast<int>(length))); 271 return static_cast<int>(length); 272 } 273 274 275 // ---------------------------------------------------------------------------- 276 // BitField is a help template for encoding and decode bitfield with 277 // unsigned content. 278 279 template<class T, int shift, int size, class U> 280 class BitFieldBase { 281 public: 282 // A type U mask of bit field. To use all bits of a type U of x bits 283 // in a bitfield without compiler warnings we have to compute 2^x 284 // without using a shift count of x in the computation. 285 static const U kOne = static_cast<U>(1U); 286 static const U kMask = ((kOne << shift) << size) - (kOne << shift); 287 static const U kShift = shift; 288 static const U kSize = size; 289 290 // Value for the field with all bits set. 291 static const T kMax = static_cast<T>((1U << size) - 1); 292 293 // Tells whether the provided value fits into the bit field. 294 static bool is_valid(T value) { 295 return (static_cast<U>(value) & ~static_cast<U>(kMax)) == 0; 296 } 297 298 // Returns a type U with the bit field value encoded. 299 static U encode(T value) { 300 ASSERT(is_valid(value)); 301 return static_cast<U>(value) << shift; 302 } 303 304 // Returns a type U with the bit field value updated. 305 static U update(U previous, T value) { 306 return (previous & ~kMask) | encode(value); 307 } 308 309 // Extracts the bit field from the value. 310 static T decode(U value) { 311 return static_cast<T>((value & kMask) >> shift); 312 } 313 }; 314 315 316 template<class T, int shift, int size> 317 class BitField : public BitFieldBase<T, shift, size, uint32_t> { }; 318 319 320 template<class T, int shift, int size> 321 class BitField64 : public BitFieldBase<T, shift, size, uint64_t> { }; 322 323 324 // ---------------------------------------------------------------------------- 325 // Hash function. 326 327 static const uint32_t kZeroHashSeed = 0; 328 329 // Thomas Wang, Integer Hash Functions. 330 // http://www.concentric.net/~Ttwang/tech/inthash.htm 331 inline uint32_t ComputeIntegerHash(uint32_t key, uint32_t seed) { 332 uint32_t hash = key; 333 hash = hash ^ seed; 334 hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1; 335 hash = hash ^ (hash >> 12); 336 hash = hash + (hash << 2); 337 hash = hash ^ (hash >> 4); 338 hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11); 339 hash = hash ^ (hash >> 16); 340 return hash; 341 } 342 343 344 inline uint32_t ComputeLongHash(uint64_t key) { 345 uint64_t hash = key; 346 hash = ~hash + (hash << 18); // hash = (hash << 18) - hash - 1; 347 hash = hash ^ (hash >> 31); 348 hash = hash * 21; // hash = (hash + (hash << 2)) + (hash << 4); 349 hash = hash ^ (hash >> 11); 350 hash = hash + (hash << 6); 351 hash = hash ^ (hash >> 22); 352 return static_cast<uint32_t>(hash); 353 } 354 355 356 inline uint32_t ComputePointerHash(void* ptr) { 357 return ComputeIntegerHash( 358 static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr)), 359 v8::internal::kZeroHashSeed); 360 } 361 362 363 // ---------------------------------------------------------------------------- 364 // Miscellaneous 365 366 // A static resource holds a static instance that can be reserved in 367 // a local scope using an instance of Access. Attempts to re-reserve 368 // the instance will cause an error. 369 template <typename T> 370 class StaticResource { 371 public: 372 StaticResource() : is_reserved_(false) {} 373 374 private: 375 template <typename S> friend class Access; 376 T instance_; 377 bool is_reserved_; 378 }; 379 380 381 // Locally scoped access to a static resource. 382 template <typename T> 383 class Access { 384 public: 385 explicit Access(StaticResource<T>* resource) 386 : resource_(resource) 387 , instance_(&resource->instance_) { 388 ASSERT(!resource->is_reserved_); 389 resource->is_reserved_ = true; 390 } 391 392 ~Access() { 393 resource_->is_reserved_ = false; 394 resource_ = NULL; 395 instance_ = NULL; 396 } 397 398 T* value() { return instance_; } 399 T* operator -> () { return instance_; } 400 401 private: 402 StaticResource<T>* resource_; 403 T* instance_; 404 }; 405 406 407 template <typename T> 408 class Vector { 409 public: 410 Vector() : start_(NULL), length_(0) {} 411 Vector(T* data, int length) : start_(data), length_(length) { 412 ASSERT(length == 0 || (length > 0 && data != NULL)); 413 } 414 415 static Vector<T> New(int length) { 416 return Vector<T>(NewArray<T>(length), length); 417 } 418 419 // Returns a vector using the same backing storage as this one, 420 // spanning from and including 'from', to but not including 'to'. 421 Vector<T> SubVector(int from, int to) { 422 SLOW_ASSERT(to <= length_); 423 SLOW_ASSERT(from < to); 424 ASSERT(0 <= from); 425 return Vector<T>(start() + from, to - from); 426 } 427 428 // Returns the length of the vector. 429 int length() const { return length_; } 430 431 // Returns whether or not the vector is empty. 432 bool is_empty() const { return length_ == 0; } 433 434 // Returns the pointer to the start of the data in the vector. 435 T* start() const { return start_; } 436 437 // Access individual vector elements - checks bounds in debug mode. 438 T& operator[](int index) const { 439 ASSERT(0 <= index && index < length_); 440 return start_[index]; 441 } 442 443 const T& at(int index) const { return operator[](index); } 444 445 T& first() { return start_[0]; } 446 447 T& last() { return start_[length_ - 1]; } 448 449 // Returns a clone of this vector with a new backing store. 450 Vector<T> Clone() const { 451 T* result = NewArray<T>(length_); 452 for (int i = 0; i < length_; i++) result[i] = start_[i]; 453 return Vector<T>(result, length_); 454 } 455 456 void Sort(int (*cmp)(const T*, const T*)) { 457 std::sort(start(), start() + length(), RawComparer(cmp)); 458 } 459 460 void Sort() { 461 std::sort(start(), start() + length()); 462 } 463 464 void Truncate(int length) { 465 ASSERT(length <= length_); 466 length_ = length; 467 } 468 469 // Releases the array underlying this vector. Once disposed the 470 // vector is empty. 471 void Dispose() { 472 DeleteArray(start_); 473 start_ = NULL; 474 length_ = 0; 475 } 476 477 inline Vector<T> operator+(int offset) { 478 ASSERT(offset < length_); 479 return Vector<T>(start_ + offset, length_ - offset); 480 } 481 482 // Factory method for creating empty vectors. 483 static Vector<T> empty() { return Vector<T>(NULL, 0); } 484 485 template<typename S> 486 static Vector<T> cast(Vector<S> input) { 487 return Vector<T>(reinterpret_cast<T*>(input.start()), 488 input.length() * sizeof(S) / sizeof(T)); 489 } 490 491 protected: 492 void set_start(T* start) { start_ = start; } 493 494 private: 495 T* start_; 496 int length_; 497 498 class RawComparer { 499 public: 500 explicit RawComparer(int (*cmp)(const T*, const T*)) : cmp_(cmp) {} 501 bool operator()(const T& a, const T& b) { 502 return cmp_(&a, &b) < 0; 503 } 504 505 private: 506 int (*cmp_)(const T*, const T*); 507 }; 508 }; 509 510 511 // A pointer that can only be set once and doesn't allow NULL values. 512 template<typename T> 513 class SetOncePointer { 514 public: 515 SetOncePointer() : pointer_(NULL) { } 516 517 bool is_set() const { return pointer_ != NULL; } 518 519 T* get() const { 520 ASSERT(pointer_ != NULL); 521 return pointer_; 522 } 523 524 void set(T* value) { 525 ASSERT(pointer_ == NULL && value != NULL); 526 pointer_ = value; 527 } 528 529 private: 530 T* pointer_; 531 }; 532 533 534 template <typename T, int kSize> 535 class EmbeddedVector : public Vector<T> { 536 public: 537 EmbeddedVector() : Vector<T>(buffer_, kSize) { } 538 539 explicit EmbeddedVector(T initial_value) : Vector<T>(buffer_, kSize) { 540 for (int i = 0; i < kSize; ++i) { 541 buffer_[i] = initial_value; 542 } 543 } 544 545 // When copying, make underlying Vector to reference our buffer. 546 EmbeddedVector(const EmbeddedVector& rhs) 547 : Vector<T>(rhs) { 548 // TODO(jkummerow): Refactor #includes and use OS::MemCopy() instead. 549 memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 550 set_start(buffer_); 551 } 552 553 EmbeddedVector& operator=(const EmbeddedVector& rhs) { 554 if (this == &rhs) return *this; 555 Vector<T>::operator=(rhs); 556 // TODO(jkummerow): Refactor #includes and use OS::MemCopy() instead. 557 memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 558 this->set_start(buffer_); 559 return *this; 560 } 561 562 private: 563 T buffer_[kSize]; 564 }; 565 566 567 template <typename T> 568 class ScopedVector : public Vector<T> { 569 public: 570 explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { } 571 ~ScopedVector() { 572 DeleteArray(this->start()); 573 } 574 575 private: 576 DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector); 577 }; 578 579 #define STATIC_ASCII_VECTOR(x) \ 580 v8::internal::Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(x), \ 581 ARRAY_SIZE(x)-1) 582 583 inline Vector<const char> CStrVector(const char* data) { 584 return Vector<const char>(data, StrLength(data)); 585 } 586 587 inline Vector<const uint8_t> OneByteVector(const char* data, int length) { 588 return Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), length); 589 } 590 591 inline Vector<const uint8_t> OneByteVector(const char* data) { 592 return OneByteVector(data, StrLength(data)); 593 } 594 595 inline Vector<char> MutableCStrVector(char* data) { 596 return Vector<char>(data, StrLength(data)); 597 } 598 599 inline Vector<char> MutableCStrVector(char* data, int max) { 600 int length = StrLength(data); 601 return Vector<char>(data, (length < max) ? length : max); 602 } 603 604 605 /* 606 * A class that collects values into a backing store. 607 * Specialized versions of the class can allow access to the backing store 608 * in different ways. 609 * There is no guarantee that the backing store is contiguous (and, as a 610 * consequence, no guarantees that consecutively added elements are adjacent 611 * in memory). The collector may move elements unless it has guaranteed not 612 * to. 613 */ 614 template <typename T, int growth_factor = 2, int max_growth = 1 * MB> 615 class Collector { 616 public: 617 explicit Collector(int initial_capacity = kMinCapacity) 618 : index_(0), size_(0) { 619 current_chunk_ = Vector<T>::New(initial_capacity); 620 } 621 622 virtual ~Collector() { 623 // Free backing store (in reverse allocation order). 624 current_chunk_.Dispose(); 625 for (int i = chunks_.length() - 1; i >= 0; i--) { 626 chunks_.at(i).Dispose(); 627 } 628 } 629 630 // Add a single element. 631 inline void Add(T value) { 632 if (index_ >= current_chunk_.length()) { 633 Grow(1); 634 } 635 current_chunk_[index_] = value; 636 index_++; 637 size_++; 638 } 639 640 // Add a block of contiguous elements and return a Vector backed by the 641 // memory area. 642 // A basic Collector will keep this vector valid as long as the Collector 643 // is alive. 644 inline Vector<T> AddBlock(int size, T initial_value) { 645 ASSERT(size > 0); 646 if (size > current_chunk_.length() - index_) { 647 Grow(size); 648 } 649 T* position = current_chunk_.start() + index_; 650 index_ += size; 651 size_ += size; 652 for (int i = 0; i < size; i++) { 653 position[i] = initial_value; 654 } 655 return Vector<T>(position, size); 656 } 657 658 659 // Add a contiguous block of elements and return a vector backed 660 // by the added block. 661 // A basic Collector will keep this vector valid as long as the Collector 662 // is alive. 663 inline Vector<T> AddBlock(Vector<const T> source) { 664 if (source.length() > current_chunk_.length() - index_) { 665 Grow(source.length()); 666 } 667 T* position = current_chunk_.start() + index_; 668 index_ += source.length(); 669 size_ += source.length(); 670 for (int i = 0; i < source.length(); i++) { 671 position[i] = source[i]; 672 } 673 return Vector<T>(position, source.length()); 674 } 675 676 677 // Write the contents of the collector into the provided vector. 678 void WriteTo(Vector<T> destination) { 679 ASSERT(size_ <= destination.length()); 680 int position = 0; 681 for (int i = 0; i < chunks_.length(); i++) { 682 Vector<T> chunk = chunks_.at(i); 683 for (int j = 0; j < chunk.length(); j++) { 684 destination[position] = chunk[j]; 685 position++; 686 } 687 } 688 for (int i = 0; i < index_; i++) { 689 destination[position] = current_chunk_[i]; 690 position++; 691 } 692 } 693 694 // Allocate a single contiguous vector, copy all the collected 695 // elements to the vector, and return it. 696 // The caller is responsible for freeing the memory of the returned 697 // vector (e.g., using Vector::Dispose). 698 Vector<T> ToVector() { 699 Vector<T> new_store = Vector<T>::New(size_); 700 WriteTo(new_store); 701 return new_store; 702 } 703 704 // Resets the collector to be empty. 705 virtual void Reset(); 706 707 // Total number of elements added to collector so far. 708 inline int size() { return size_; } 709 710 protected: 711 static const int kMinCapacity = 16; 712 List<Vector<T> > chunks_; 713 Vector<T> current_chunk_; // Block of memory currently being written into. 714 int index_; // Current index in current chunk. 715 int size_; // Total number of elements in collector. 716 717 // Creates a new current chunk, and stores the old chunk in the chunks_ list. 718 void Grow(int min_capacity) { 719 ASSERT(growth_factor > 1); 720 int new_capacity; 721 int current_length = current_chunk_.length(); 722 if (current_length < kMinCapacity) { 723 // The collector started out as empty. 724 new_capacity = min_capacity * growth_factor; 725 if (new_capacity < kMinCapacity) new_capacity = kMinCapacity; 726 } else { 727 int growth = current_length * (growth_factor - 1); 728 if (growth > max_growth) { 729 growth = max_growth; 730 } 731 new_capacity = current_length + growth; 732 if (new_capacity < min_capacity) { 733 new_capacity = min_capacity + growth; 734 } 735 } 736 NewChunk(new_capacity); 737 ASSERT(index_ + min_capacity <= current_chunk_.length()); 738 } 739 740 // Before replacing the current chunk, give a subclass the option to move 741 // some of the current data into the new chunk. The function may update 742 // the current index_ value to represent data no longer in the current chunk. 743 // Returns the initial index of the new chunk (after copied data). 744 virtual void NewChunk(int new_capacity) { 745 Vector<T> new_chunk = Vector<T>::New(new_capacity); 746 if (index_ > 0) { 747 chunks_.Add(current_chunk_.SubVector(0, index_)); 748 } else { 749 current_chunk_.Dispose(); 750 } 751 current_chunk_ = new_chunk; 752 index_ = 0; 753 } 754 }; 755 756 757 /* 758 * A collector that allows sequences of values to be guaranteed to 759 * stay consecutive. 760 * If the backing store grows while a sequence is active, the current 761 * sequence might be moved, but after the sequence is ended, it will 762 * not move again. 763 * NOTICE: Blocks allocated using Collector::AddBlock(int) can move 764 * as well, if inside an active sequence where another element is added. 765 */ 766 template <typename T, int growth_factor = 2, int max_growth = 1 * MB> 767 class SequenceCollector : public Collector<T, growth_factor, max_growth> { 768 public: 769 explicit SequenceCollector(int initial_capacity) 770 : Collector<T, growth_factor, max_growth>(initial_capacity), 771 sequence_start_(kNoSequence) { } 772 773 virtual ~SequenceCollector() {} 774 775 void StartSequence() { 776 ASSERT(sequence_start_ == kNoSequence); 777 sequence_start_ = this->index_; 778 } 779 780 Vector<T> EndSequence() { 781 ASSERT(sequence_start_ != kNoSequence); 782 int sequence_start = sequence_start_; 783 sequence_start_ = kNoSequence; 784 if (sequence_start == this->index_) return Vector<T>(); 785 return this->current_chunk_.SubVector(sequence_start, this->index_); 786 } 787 788 // Drops the currently added sequence, and all collected elements in it. 789 void DropSequence() { 790 ASSERT(sequence_start_ != kNoSequence); 791 int sequence_length = this->index_ - sequence_start_; 792 this->index_ = sequence_start_; 793 this->size_ -= sequence_length; 794 sequence_start_ = kNoSequence; 795 } 796 797 virtual void Reset() { 798 sequence_start_ = kNoSequence; 799 this->Collector<T, growth_factor, max_growth>::Reset(); 800 } 801 802 private: 803 static const int kNoSequence = -1; 804 int sequence_start_; 805 806 // Move the currently active sequence to the new chunk. 807 virtual void NewChunk(int new_capacity) { 808 if (sequence_start_ == kNoSequence) { 809 // Fall back on default behavior if no sequence has been started. 810 this->Collector<T, growth_factor, max_growth>::NewChunk(new_capacity); 811 return; 812 } 813 int sequence_length = this->index_ - sequence_start_; 814 Vector<T> new_chunk = Vector<T>::New(sequence_length + new_capacity); 815 ASSERT(sequence_length < new_chunk.length()); 816 for (int i = 0; i < sequence_length; i++) { 817 new_chunk[i] = this->current_chunk_[sequence_start_ + i]; 818 } 819 if (sequence_start_ > 0) { 820 this->chunks_.Add(this->current_chunk_.SubVector(0, sequence_start_)); 821 } else { 822 this->current_chunk_.Dispose(); 823 } 824 this->current_chunk_ = new_chunk; 825 this->index_ = sequence_length; 826 sequence_start_ = 0; 827 } 828 }; 829 830 831 // Compare ASCII/16bit chars to ASCII/16bit chars. 832 template <typename lchar, typename rchar> 833 inline int CompareCharsUnsigned(const lchar* lhs, 834 const rchar* rhs, 835 int chars) { 836 const lchar* limit = lhs + chars; 837 #ifdef V8_HOST_CAN_READ_UNALIGNED 838 if (sizeof(*lhs) == sizeof(*rhs)) { 839 // Number of characters in a uintptr_t. 840 static const int kStepSize = sizeof(uintptr_t) / sizeof(*lhs); // NOLINT 841 while (lhs <= limit - kStepSize) { 842 if (*reinterpret_cast<const uintptr_t*>(lhs) != 843 *reinterpret_cast<const uintptr_t*>(rhs)) { 844 break; 845 } 846 lhs += kStepSize; 847 rhs += kStepSize; 848 } 849 } 850 #endif 851 while (lhs < limit) { 852 int r = static_cast<int>(*lhs) - static_cast<int>(*rhs); 853 if (r != 0) return r; 854 ++lhs; 855 ++rhs; 856 } 857 return 0; 858 } 859 860 template<typename lchar, typename rchar> 861 inline int CompareChars(const lchar* lhs, const rchar* rhs, int chars) { 862 ASSERT(sizeof(lchar) <= 2); 863 ASSERT(sizeof(rchar) <= 2); 864 if (sizeof(lchar) == 1) { 865 if (sizeof(rchar) == 1) { 866 return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs), 867 reinterpret_cast<const uint8_t*>(rhs), 868 chars); 869 } else { 870 return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs), 871 reinterpret_cast<const uint16_t*>(rhs), 872 chars); 873 } 874 } else { 875 if (sizeof(rchar) == 1) { 876 return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs), 877 reinterpret_cast<const uint8_t*>(rhs), 878 chars); 879 } else { 880 return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs), 881 reinterpret_cast<const uint16_t*>(rhs), 882 chars); 883 } 884 } 885 } 886 887 888 // Calculate 10^exponent. 889 inline int TenToThe(int exponent) { 890 ASSERT(exponent <= 9); 891 ASSERT(exponent >= 1); 892 int answer = 10; 893 for (int i = 1; i < exponent; i++) answer *= 10; 894 return answer; 895 } 896 897 898 // The type-based aliasing rule allows the compiler to assume that pointers of 899 // different types (for some definition of different) never alias each other. 900 // Thus the following code does not work: 901 // 902 // float f = foo(); 903 // int fbits = *(int*)(&f); 904 // 905 // The compiler 'knows' that the int pointer can't refer to f since the types 906 // don't match, so the compiler may cache f in a register, leaving random data 907 // in fbits. Using C++ style casts makes no difference, however a pointer to 908 // char data is assumed to alias any other pointer. This is the 'memcpy 909 // exception'. 910 // 911 // Bit_cast uses the memcpy exception to move the bits from a variable of one 912 // type of a variable of another type. Of course the end result is likely to 913 // be implementation dependent. Most compilers (gcc-4.2 and MSVC 2005) 914 // will completely optimize BitCast away. 915 // 916 // There is an additional use for BitCast. 917 // Recent gccs will warn when they see casts that may result in breakage due to 918 // the type-based aliasing rule. If you have checked that there is no breakage 919 // you can use BitCast to cast one pointer type to another. This confuses gcc 920 // enough that it can no longer see that you have cast one pointer type to 921 // another thus avoiding the warning. 922 923 // We need different implementations of BitCast for pointer and non-pointer 924 // values. We use partial specialization of auxiliary struct to work around 925 // issues with template functions overloading. 926 template <class Dest, class Source> 927 struct BitCastHelper { 928 STATIC_ASSERT(sizeof(Dest) == sizeof(Source)); 929 930 INLINE(static Dest cast(const Source& source)) { 931 Dest dest; 932 // TODO(jkummerow): Refactor #includes and use OS::MemCopy() instead. 933 memcpy(&dest, &source, sizeof(dest)); 934 return dest; 935 } 936 }; 937 938 template <class Dest, class Source> 939 struct BitCastHelper<Dest, Source*> { 940 INLINE(static Dest cast(Source* source)) { 941 return BitCastHelper<Dest, uintptr_t>:: 942 cast(reinterpret_cast<uintptr_t>(source)); 943 } 944 }; 945 946 template <class Dest, class Source> 947 INLINE(Dest BitCast(const Source& source)); 948 949 template <class Dest, class Source> 950 inline Dest BitCast(const Source& source) { 951 return BitCastHelper<Dest, Source>::cast(source); 952 } 953 954 955 template<typename ElementType, int NumElements> 956 class EmbeddedContainer { 957 public: 958 EmbeddedContainer() : elems_() { } 959 960 int length() const { return NumElements; } 961 const ElementType& operator[](int i) const { 962 ASSERT(i < length()); 963 return elems_[i]; 964 } 965 ElementType& operator[](int i) { 966 ASSERT(i < length()); 967 return elems_[i]; 968 } 969 970 private: 971 ElementType elems_[NumElements]; 972 }; 973 974 975 template<typename ElementType> 976 class EmbeddedContainer<ElementType, 0> { 977 public: 978 int length() const { return 0; } 979 const ElementType& operator[](int i) const { 980 UNREACHABLE(); 981 static ElementType t = 0; 982 return t; 983 } 984 ElementType& operator[](int i) { 985 UNREACHABLE(); 986 static ElementType t = 0; 987 return t; 988 } 989 }; 990 991 992 // Helper class for building result strings in a character buffer. The 993 // purpose of the class is to use safe operations that checks the 994 // buffer bounds on all operations in debug mode. 995 // This simple base class does not allow formatted output. 996 class SimpleStringBuilder { 997 public: 998 // Create a string builder with a buffer of the given size. The 999 // buffer is allocated through NewArray<char> and must be 1000 // deallocated by the caller of Finalize(). 1001 explicit SimpleStringBuilder(int size); 1002 1003 SimpleStringBuilder(char* buffer, int size) 1004 : buffer_(buffer, size), position_(0) { } 1005 1006 ~SimpleStringBuilder() { if (!is_finalized()) Finalize(); } 1007 1008 int size() const { return buffer_.length(); } 1009 1010 // Get the current position in the builder. 1011 int position() const { 1012 ASSERT(!is_finalized()); 1013 return position_; 1014 } 1015 1016 // Reset the position. 1017 void Reset() { position_ = 0; } 1018 1019 // Add a single character to the builder. It is not allowed to add 1020 // 0-characters; use the Finalize() method to terminate the string 1021 // instead. 1022 void AddCharacter(char c) { 1023 ASSERT(c != '\0'); 1024 ASSERT(!is_finalized() && position_ < buffer_.length()); 1025 buffer_[position_++] = c; 1026 } 1027 1028 // Add an entire string to the builder. Uses strlen() internally to 1029 // compute the length of the input string. 1030 void AddString(const char* s); 1031 1032 // Add the first 'n' characters of the given string 's' to the 1033 // builder. The input string must have enough characters. 1034 void AddSubstring(const char* s, int n); 1035 1036 // Add character padding to the builder. If count is non-positive, 1037 // nothing is added to the builder. 1038 void AddPadding(char c, int count); 1039 1040 // Add the decimal representation of the value. 1041 void AddDecimalInteger(int value); 1042 1043 // Finalize the string by 0-terminating it and returning the buffer. 1044 char* Finalize(); 1045 1046 protected: 1047 Vector<char> buffer_; 1048 int position_; 1049 1050 bool is_finalized() const { return position_ < 0; } 1051 1052 private: 1053 DISALLOW_IMPLICIT_CONSTRUCTORS(SimpleStringBuilder); 1054 }; 1055 1056 1057 // A poor man's version of STL's bitset: A bit set of enums E (without explicit 1058 // values), fitting into an integral type T. 1059 template <class E, class T = int> 1060 class EnumSet { 1061 public: 1062 explicit EnumSet(T bits = 0) : bits_(bits) {} 1063 bool IsEmpty() const { return bits_ == 0; } 1064 bool Contains(E element) const { return (bits_ & Mask(element)) != 0; } 1065 bool ContainsAnyOf(const EnumSet& set) const { 1066 return (bits_ & set.bits_) != 0; 1067 } 1068 void Add(E element) { bits_ |= Mask(element); } 1069 void Add(const EnumSet& set) { bits_ |= set.bits_; } 1070 void Remove(E element) { bits_ &= ~Mask(element); } 1071 void Remove(const EnumSet& set) { bits_ &= ~set.bits_; } 1072 void RemoveAll() { bits_ = 0; } 1073 void Intersect(const EnumSet& set) { bits_ &= set.bits_; } 1074 T ToIntegral() const { return bits_; } 1075 bool operator==(const EnumSet& set) { return bits_ == set.bits_; } 1076 bool operator!=(const EnumSet& set) { return bits_ != set.bits_; } 1077 EnumSet<E, T> operator|(const EnumSet& set) const { 1078 return EnumSet<E, T>(bits_ | set.bits_); 1079 } 1080 1081 private: 1082 T Mask(E element) const { 1083 // The strange typing in ASSERT is necessary to avoid stupid warnings, see: 1084 // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43680 1085 ASSERT(static_cast<int>(element) < static_cast<int>(sizeof(T) * CHAR_BIT)); 1086 return static_cast<T>(1) << element; 1087 } 1088 1089 T bits_; 1090 }; 1091 1092 1093 class TypeFeedbackId { 1094 public: 1095 explicit TypeFeedbackId(int id) : id_(id) { } 1096 int ToInt() const { return id_; } 1097 1098 static TypeFeedbackId None() { return TypeFeedbackId(kNoneId); } 1099 bool IsNone() const { return id_ == kNoneId; } 1100 1101 private: 1102 static const int kNoneId = -1; 1103 1104 int id_; 1105 }; 1106 1107 1108 class BailoutId { 1109 public: 1110 explicit BailoutId(int id) : id_(id) { } 1111 int ToInt() const { return id_; } 1112 1113 static BailoutId None() { return BailoutId(kNoneId); } 1114 static BailoutId FunctionEntry() { return BailoutId(kFunctionEntryId); } 1115 static BailoutId Declarations() { return BailoutId(kDeclarationsId); } 1116 static BailoutId FirstUsable() { return BailoutId(kFirstUsableId); } 1117 static BailoutId StubEntry() { return BailoutId(kStubEntryId); } 1118 1119 bool IsNone() const { return id_ == kNoneId; } 1120 bool operator==(const BailoutId& other) const { return id_ == other.id_; } 1121 1122 private: 1123 static const int kNoneId = -1; 1124 1125 // Using 0 could disguise errors. 1126 static const int kFunctionEntryId = 2; 1127 1128 // This AST id identifies the point after the declarations have been visited. 1129 // We need it to capture the environment effects of declarations that emit 1130 // code (function declarations). 1131 static const int kDeclarationsId = 3; 1132 1133 // Every FunctionState starts with this id. 1134 static const int kFirstUsableId = 4; 1135 1136 // Every compiled stub starts with this id. 1137 static const int kStubEntryId = 5; 1138 1139 int id_; 1140 }; 1141 1142 } } // namespace v8::internal 1143 1144 #endif // V8_UTILS_H_ 1145