Line data Source code
1 : // Copyright 2012 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_UTILS_H_
6 : #define V8_UTILS_H_
7 :
8 : #include <limits.h>
9 : #include <stdlib.h>
10 : #include <string.h>
11 : #include <cmath>
12 : #include <string>
13 : #include <type_traits>
14 :
15 : #include "include/v8.h"
16 : #include "src/allocation.h"
17 : #include "src/base/bits.h"
18 : #include "src/base/compiler-specific.h"
19 : #include "src/base/logging.h"
20 : #include "src/base/macros.h"
21 : #include "src/base/platform/platform.h"
22 : #include "src/base/v8-fallthrough.h"
23 : #include "src/globals.h"
24 : #include "src/third_party/siphash/halfsiphash.h"
25 : #include "src/vector.h"
26 :
27 : #if defined(V8_OS_AIX)
28 : #include <fenv.h> // NOLINT(build/c++11)
29 : #endif
30 :
31 : namespace v8 {
32 : namespace internal {
33 :
34 : // ----------------------------------------------------------------------------
35 : // General helper functions
36 :
37 : // Returns the value (0 .. 15) of a hexadecimal character c.
38 : // If c is not a legal hexadecimal character, returns a value < 0.
39 : inline int HexValue(uc32 c) {
40 72467110 : c -= '0';
41 72467110 : if (static_cast<unsigned>(c) <= 9) return c;
42 8769035 : c = (c | 0x20) - ('a' - '0'); // detect 0x11..0x16 and 0x31..0x36.
43 8769035 : if (static_cast<unsigned>(c) <= 5) return c + 10;
44 : return -1;
45 : }
46 :
47 : inline char HexCharOfValue(int value) {
48 : DCHECK(0 <= value && value <= 16);
49 8202248 : if (value < 10) return value + '0';
50 533771 : return value - 10 + 'A';
51 : }
52 :
53 37025 : inline int BoolToInt(bool b) { return b ? 1 : 0; }
54 :
55 : // Same as strcmp, but can handle NULL arguments.
56 : inline bool CStringEquals(const char* s1, const char* s2) {
57 : return (s1 == s2) || (s1 != nullptr && s2 != nullptr && strcmp(s1, s2) == 0);
58 : }
59 :
60 : // Checks if value is in range [lower_limit, higher_limit] using a single
61 : // branch.
62 : template <typename T, typename U>
63 2322421606 : inline constexpr bool IsInRange(T value, U lower_limit, U higher_limit) {
64 : #if V8_CAN_HAVE_DCHECK_IN_CONSTEXPR
65 : DCHECK(lower_limit <= higher_limit);
66 : #endif
67 : STATIC_ASSERT(sizeof(U) <= sizeof(T));
68 : typedef typename std::make_unsigned<T>::type unsigned_T;
69 : // Use static_cast to support enum classes.
70 : return static_cast<unsigned_T>(static_cast<unsigned_T>(value) -
71 : static_cast<unsigned_T>(lower_limit)) <=
72 : static_cast<unsigned_T>(static_cast<unsigned_T>(higher_limit) -
73 8128169660 : static_cast<unsigned_T>(lower_limit));
74 : }
75 :
76 : // Checks if [index, index+length) is in range [0, max). Note that this check
77 : // works even if {index+length} would wrap around.
78 : inline constexpr bool IsInBounds(size_t index, size_t length, size_t max) {
79 7942805 : return length <= max && index <= (max - length);
80 : }
81 :
82 : // X must be a power of 2. Returns the number of trailing zeros.
83 : template <typename T,
84 : typename = typename std::enable_if<std::is_integral<T>::value>::type>
85 21437 : inline int WhichPowerOf2(T x) {
86 : DCHECK(base::bits::IsPowerOfTwo(x));
87 : int bits = 0;
88 : #ifdef DEBUG
89 : const T original_x = x;
90 : #endif
91 : constexpr int max_bits = sizeof(T) * 8;
92 : static_assert(max_bits <= 64, "integral types are not bigger than 64 bits");
93 : // Avoid shifting by more than the bit width of x to avoid compiler warnings.
94 : #define CHECK_BIGGER(s) \
95 : if (max_bits > s && x >= T{1} << (max_bits > s ? s : 0)) { \
96 : bits += s; \
97 : x >>= max_bits > s ? s : 0; \
98 : }
99 18618 : CHECK_BIGGER(32)
100 21437 : CHECK_BIGGER(16)
101 21437 : CHECK_BIGGER(8)
102 21437 : CHECK_BIGGER(4)
103 : #undef CHECK_BIGGER
104 21437 : switch (x) {
105 0 : default: UNREACHABLE();
106 : case 8:
107 8979 : bits++;
108 : V8_FALLTHROUGH;
109 : case 4:
110 9446 : bits++;
111 : V8_FALLTHROUGH;
112 : case 2:
113 13211 : bits++;
114 : V8_FALLTHROUGH;
115 : case 1: break;
116 : }
117 : DCHECK_EQ(T{1} << bits, original_x);
118 21437 : return bits;
119 : }
120 :
121 : inline int MostSignificantBit(uint32_t x) {
122 : static const int msb4[] = {0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4};
123 : int nibble = 0;
124 : if (x & 0xffff0000) {
125 : nibble += 16;
126 : x >>= 16;
127 : }
128 : if (x & 0xff00) {
129 : nibble += 8;
130 : x >>= 8;
131 : }
132 : if (x & 0xf0) {
133 : nibble += 4;
134 : x >>= 4;
135 : }
136 : return nibble + msb4[x];
137 : }
138 :
139 : template <typename T>
140 29940 : static T ArithmeticShiftRight(T x, int shift) {
141 : DCHECK_LE(0, shift);
142 30314 : if (x < 0) {
143 : // Right shift of signed values is implementation defined. Simulate a
144 : // true arithmetic right shift by adding leading sign bits.
145 : using UnsignedT = typename std::make_unsigned<T>::type;
146 6990 : UnsignedT mask = ~(static_cast<UnsignedT>(~0) >> shift);
147 6990 : return (static_cast<UnsignedT>(x) >> shift) | mask;
148 : } else {
149 23324 : return x >> shift;
150 : }
151 : }
152 :
153 : template <typename T>
154 : int Compare(const T& a, const T& b) {
155 3935 : if (a == b)
156 : return 0;
157 3935 : else if (a < b)
158 : return -1;
159 : else
160 : return 1;
161 : }
162 :
163 : // Compare function to compare the object pointer value of two
164 : // handlified objects. The handles are passed as pointers to the
165 : // handles.
166 : template<typename T> class Handle; // Forward declaration.
167 : template <typename T>
168 : int HandleObjectPointerCompare(const Handle<T>* a, const Handle<T>* b) {
169 : return Compare<T*>(*(*a), *(*b));
170 : }
171 :
172 : // Returns the maximum of the two parameters.
173 : template <typename T>
174 59685 : constexpr T Max(T a, T b) {
175 156335351 : return a < b ? b : a;
176 : }
177 :
178 :
179 : // Returns the minimum of the two parameters.
180 : template <typename T>
181 8435439 : constexpr T Min(T a, T b) {
182 306053792 : return a < b ? a : b;
183 : }
184 :
185 : // Returns the maximum of the two parameters according to JavaScript semantics.
186 : template <typename T>
187 543810 : T JSMax(T x, T y) {
188 543810 : if (std::isnan(x)) return x;
189 532205 : if (std::isnan(y)) return y;
190 1041770 : if (std::signbit(x) < std::signbit(y)) return x;
191 393265 : return x > y ? x : y;
192 : }
193 :
194 : // Returns the maximum of the two parameters according to JavaScript semantics.
195 : template <typename T>
196 543810 : T JSMin(T x, T y) {
197 543810 : if (std::isnan(x)) return x;
198 532205 : if (std::isnan(y)) return y;
199 1041770 : if (std::signbit(x) < std::signbit(y)) return y;
200 393265 : return x > y ? y : x;
201 : }
202 :
203 : // Returns the absolute value of its argument.
204 : template <typename T,
205 : typename = typename std::enable_if<std::is_signed<T>::value>::type>
206 : typename std::make_unsigned<T>::type Abs(T a) {
207 : // This is a branch-free implementation of the absolute value function and is
208 : // described in Warren's "Hacker's Delight", chapter 2. It avoids undefined
209 : // behavior with the arithmetic negation operation on signed values as well.
210 : typedef typename std::make_unsigned<T>::type unsignedT;
211 7490 : unsignedT x = static_cast<unsignedT>(a);
212 7490 : unsignedT y = static_cast<unsignedT>(a >> (sizeof(T) * 8 - 1));
213 7490 : return (x ^ y) - y;
214 : }
215 :
216 : // Returns the negative absolute value of its argument.
217 : template <typename T,
218 : typename = typename std::enable_if<std::is_signed<T>::value>::type>
219 : T Nabs(T a) {
220 : return a < 0 ? a : -a;
221 : }
222 :
223 : // Floor(-0.0) == 0.0
224 : inline double Floor(double x) {
225 : #if V8_CC_MSVC
226 : if (x == 0) return x; // Fix for issue 3477.
227 : #endif
228 144842 : return std::floor(x);
229 : }
230 :
231 : inline double Modulo(double x, double y) {
232 : #if defined(V8_OS_WIN)
233 : // Workaround MS fmod bugs. ECMA-262 says:
234 : // dividend is finite and divisor is an infinity => result equals dividend
235 : // dividend is a zero and divisor is nonzero finite => result equals dividend
236 : if (!(std::isfinite(x) && (!std::isfinite(y) && !std::isnan(y))) &&
237 : !(x == 0 && (y != 0 && std::isfinite(y)))) {
238 : double result = fmod(x, y);
239 : // Workaround MS bug in VS CRT in some OS versions, https://crbug.com/915045
240 : // fmod(-17, +/-1) should equal -0.0 but now returns 0.0.
241 : if (x < 0 && result == 0) result = -0.0;
242 : x = result;
243 : }
244 : return x;
245 : #elif defined(V8_OS_AIX)
246 : // AIX raises an underflow exception for (Number.MIN_VALUE % Number.MAX_VALUE)
247 : feclearexcept(FE_ALL_EXCEPT);
248 : double result = std::fmod(x, y);
249 : int exception = fetestexcept(FE_UNDERFLOW);
250 : return (exception ? x : result);
251 : #else
252 729146 : return std::fmod(x, y);
253 : #endif
254 : }
255 :
256 65700 : inline double Pow(double x, double y) {
257 65700 : if (y == 0.0) return 1.0;
258 67318 : if (std::isnan(y) || ((x == 1 || x == -1) && std::isinf(y))) {
259 : return std::numeric_limits<double>::quiet_NaN();
260 : }
261 : #if (defined(__MINGW64_VERSION_MAJOR) && \
262 : (!defined(__MINGW64_VERSION_RC) || __MINGW64_VERSION_RC < 1)) || \
263 : defined(V8_OS_AIX)
264 : // MinGW64 and AIX have a custom implementation for pow. This handles certain
265 : // special cases that are different.
266 : if ((x == 0.0 || std::isinf(x)) && y != 0.0 && std::isfinite(y)) {
267 : double f;
268 : double result = ((x == 0.0) ^ (y > 0)) ? V8_INFINITY : 0;
269 : /* retain sign if odd integer exponent */
270 : return ((std::modf(y, &f) == 0.0) && (static_cast<int64_t>(y) & 1))
271 : ? copysign(result, x)
272 : : result;
273 : }
274 :
275 : if (x == 2.0) {
276 : int y_int = static_cast<int>(y);
277 : if (y == y_int) {
278 : return std::ldexp(1.0, y_int);
279 : }
280 : }
281 : #endif
282 63183 : return std::pow(x, y);
283 : }
284 :
285 : template <typename T>
286 11322 : T SaturateAdd(T a, T b) {
287 : if (std::is_signed<T>::value) {
288 11322 : if (a > 0 && b > 0) {
289 2694 : if (a > std::numeric_limits<T>::max() - b) {
290 : return std::numeric_limits<T>::max();
291 : }
292 8628 : } else if (a < 0 && b < 0) {
293 2037 : if (a < std::numeric_limits<T>::min() - b) {
294 : return std::numeric_limits<T>::min();
295 : }
296 : }
297 : } else {
298 : CHECK(std::is_unsigned<T>::value);
299 11313 : if (a > std::numeric_limits<T>::max() - b) {
300 : return std::numeric_limits<T>::max();
301 : }
302 : }
303 15424 : return a + b;
304 : }
305 :
306 : template <typename T>
307 11384 : T SaturateSub(T a, T b) {
308 : if (std::is_signed<T>::value) {
309 11384 : if (a >= 0 && b < 0) {
310 2724 : if (a > std::numeric_limits<T>::max() + b) {
311 : return std::numeric_limits<T>::max();
312 : }
313 8660 : } else if (a < 0 && b > 0) {
314 2225 : if (a < std::numeric_limits<T>::min() + b) {
315 : return std::numeric_limits<T>::min();
316 : }
317 : }
318 : } else {
319 : CHECK(std::is_unsigned<T>::value);
320 11313 : if (a < b) {
321 : return static_cast<T>(0);
322 : }
323 : }
324 15161 : return a - b;
325 : }
326 :
327 : // ----------------------------------------------------------------------------
328 : // BitField is a help template for encoding and decode bitfield with
329 : // unsigned content.
330 :
331 : template<class T, int shift, int size, class U>
332 : class BitFieldBase {
333 : public:
334 : typedef T FieldType;
335 :
336 : // A type U mask of bit field. To use all bits of a type U of x bits
337 : // in a bitfield without compiler warnings we have to compute 2^x
338 : // without using a shift count of x in the computation.
339 : static const U kOne = static_cast<U>(1U);
340 : static const U kMask = ((kOne << shift) << size) - (kOne << shift);
341 : static const U kShift = shift;
342 : static const U kSize = size;
343 : static const U kNext = kShift + kSize;
344 : static const U kNumValues = kOne << size;
345 :
346 : // Value for the field with all bits set.
347 : static const T kMax = static_cast<T>(kNumValues - 1);
348 :
349 : // Tells whether the provided value fits into the bit field.
350 : static constexpr bool is_valid(T value) {
351 79349809 : return (static_cast<U>(value) & ~static_cast<U>(kMax)) == 0;
352 : }
353 :
354 : // Returns a type U with the bit field value encoded.
355 : static constexpr U encode(T value) {
356 : #if V8_CAN_HAVE_DCHECK_IN_CONSTEXPR
357 : DCHECK(is_valid(value));
358 : #endif
359 5764608690 : return static_cast<U>(value) << shift;
360 : }
361 :
362 : // Returns a type U with the bit field value updated.
363 : static constexpr U update(U previous, T value) {
364 6739070263 : return (previous & ~kMask) | encode(value);
365 : }
366 :
367 : // Extracts the bit field from the value.
368 27026799 : static constexpr T decode(U value) {
369 45142244661 : return static_cast<T>((value & kMask) >> shift);
370 : }
371 :
372 : STATIC_ASSERT((kNext - 1) / 8 < sizeof(U));
373 : };
374 :
375 : template <class T, int shift, int size>
376 : class BitField8 : public BitFieldBase<T, shift, size, uint8_t> {};
377 :
378 :
379 : template <class T, int shift, int size>
380 : class BitField16 : public BitFieldBase<T, shift, size, uint16_t> {};
381 :
382 :
383 : template<class T, int shift, int size>
384 : class BitField : public BitFieldBase<T, shift, size, uint32_t> { };
385 :
386 :
387 : template<class T, int shift, int size>
388 : class BitField64 : public BitFieldBase<T, shift, size, uint64_t> { };
389 :
390 : // Helper macros for defining a contiguous sequence of bit fields. Example:
391 : // (backslashes at the ends of respective lines of this multi-line macro
392 : // definition are omitted here to please the compiler)
393 : //
394 : // #define MAP_BIT_FIELD1(V, _)
395 : // V(IsAbcBit, bool, 1, _)
396 : // V(IsBcdBit, bool, 1, _)
397 : // V(CdeBits, int, 5, _)
398 : // V(DefBits, MutableMode, 1, _)
399 : //
400 : // DEFINE_BIT_FIELDS(MAP_BIT_FIELD1)
401 : // or
402 : // DEFINE_BIT_FIELDS_64(MAP_BIT_FIELD1)
403 : //
404 : #define DEFINE_BIT_FIELD_RANGE_TYPE(Name, Type, Size, _) \
405 : k##Name##Start, k##Name##End = k##Name##Start + Size - 1,
406 :
407 : #define DEFINE_BIT_RANGES(LIST_MACRO) \
408 : struct LIST_MACRO##_Ranges { \
409 : enum { LIST_MACRO(DEFINE_BIT_FIELD_RANGE_TYPE, _) kBitsCount }; \
410 : };
411 :
412 : #define DEFINE_BIT_FIELD_TYPE(Name, Type, Size, RangesName) \
413 : typedef BitField<Type, RangesName::k##Name##Start, Size> Name;
414 :
415 : #define DEFINE_BIT_FIELD_64_TYPE(Name, Type, Size, RangesName) \
416 : typedef BitField64<Type, RangesName::k##Name##Start, Size> Name;
417 :
418 : #define DEFINE_BIT_FIELDS(LIST_MACRO) \
419 : DEFINE_BIT_RANGES(LIST_MACRO) \
420 : LIST_MACRO(DEFINE_BIT_FIELD_TYPE, LIST_MACRO##_Ranges)
421 :
422 : #define DEFINE_BIT_FIELDS_64(LIST_MACRO) \
423 : DEFINE_BIT_RANGES(LIST_MACRO) \
424 : LIST_MACRO(DEFINE_BIT_FIELD_64_TYPE, LIST_MACRO##_Ranges)
425 :
426 : // ----------------------------------------------------------------------------
427 : // BitSetComputer is a help template for encoding and decoding information for
428 : // a variable number of items in an array.
429 : //
430 : // To encode boolean data in a smi array you would use:
431 : // typedef BitSetComputer<bool, 1, kSmiValueSize, uint32_t> BoolComputer;
432 : //
433 : template <class T, int kBitsPerItem, int kBitsPerWord, class U>
434 : class BitSetComputer {
435 : public:
436 : static const int kItemsPerWord = kBitsPerWord / kBitsPerItem;
437 : static const int kMask = (1 << kBitsPerItem) - 1;
438 :
439 : // The number of array elements required to embed T information for each item.
440 : static int word_count(int items) {
441 17275526 : if (items == 0) return 0;
442 17263602 : return (items - 1) / kItemsPerWord + 1;
443 : }
444 :
445 : // The array index to look at for item.
446 : static int index(int base_index, int item) {
447 66593621 : return base_index + item / kItemsPerWord;
448 : }
449 :
450 : // Extract T data for a given item from data.
451 : static T decode(U data, int item) {
452 42503681 : return static_cast<T>((data >> shift(item)) & kMask);
453 : }
454 :
455 : // Return the encoding for a store of value for item in previous.
456 : static U encode(U previous, int item, T value) {
457 : int shift_value = shift(item);
458 24094215 : int set_bits = (static_cast<int>(value) << shift_value);
459 24094215 : return (previous & ~(kMask << shift_value)) | set_bits;
460 : }
461 :
462 66593621 : static int shift(int item) { return (item % kItemsPerWord) * kBitsPerItem; }
463 : };
464 :
465 : // Helper macros for defining a contiguous sequence of field offset constants.
466 : // Example: (backslashes at the ends of respective lines of this multi-line
467 : // macro definition are omitted here to please the compiler)
468 : //
469 : // #define MAP_FIELDS(V)
470 : // V(kField1Offset, kTaggedSize)
471 : // V(kField2Offset, kIntSize)
472 : // V(kField3Offset, kIntSize)
473 : // V(kField4Offset, kSystemPointerSize)
474 : // V(kSize, 0)
475 : //
476 : // DEFINE_FIELD_OFFSET_CONSTANTS(HeapObject::kHeaderSize, MAP_FIELDS)
477 : //
478 : #define DEFINE_ONE_FIELD_OFFSET(Name, Size) Name, Name##End = Name + (Size)-1,
479 :
480 : #define DEFINE_FIELD_OFFSET_CONSTANTS(StartOffset, LIST_MACRO) \
481 : enum { \
482 : LIST_MACRO##_StartOffset = StartOffset - 1, \
483 : LIST_MACRO(DEFINE_ONE_FIELD_OFFSET) \
484 : };
485 :
486 : // Size of the field defined by DEFINE_FIELD_OFFSET_CONSTANTS
487 : #define FIELD_SIZE(Name) (Name##End + 1 - Name)
488 :
489 : // ----------------------------------------------------------------------------
490 : // Hash function.
491 :
492 : static const uint64_t kZeroHashSeed = 0;
493 :
494 : // Thomas Wang, Integer Hash Functions.
495 : // http://www.concentric.net/~Ttwang/tech/inthash.htm`
496 : inline uint32_t ComputeUnseededHash(uint32_t key) {
497 : uint32_t hash = key;
498 91039154 : hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1;
499 91039154 : hash = hash ^ (hash >> 12);
500 91039154 : hash = hash + (hash << 2);
501 91039154 : hash = hash ^ (hash >> 4);
502 91039154 : hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11);
503 91039154 : hash = hash ^ (hash >> 16);
504 91039154 : return hash & 0x3fffffff;
505 : }
506 :
507 : inline uint32_t ComputeLongHash(uint64_t key) {
508 : uint64_t hash = key;
509 151208302 : hash = ~hash + (hash << 18); // hash = (hash << 18) - hash - 1;
510 151208302 : hash = hash ^ (hash >> 31);
511 151208302 : hash = hash * 21; // hash = (hash + (hash << 2)) + (hash << 4);
512 151208302 : hash = hash ^ (hash >> 11);
513 151208302 : hash = hash + (hash << 6);
514 151208302 : hash = hash ^ (hash >> 22);
515 151208302 : return static_cast<uint32_t>(hash & 0x3fffffff);
516 : }
517 :
518 : inline uint32_t ComputeSeededHash(uint32_t key, uint64_t seed) {
519 : #ifdef V8_USE_SIPHASH
520 : return halfsiphash(key, seed);
521 : #else
522 147175710 : return ComputeLongHash(static_cast<uint64_t>(key) ^ seed);
523 : #endif // V8_USE_SIPHASH
524 : }
525 :
526 : inline uint32_t ComputePointerHash(void* ptr) {
527 : return ComputeUnseededHash(
528 21520 : static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr)));
529 : }
530 :
531 : inline uint32_t ComputeAddressHash(Address address) {
532 10505998 : return ComputeUnseededHash(static_cast<uint32_t>(address & 0xFFFFFFFFul));
533 : }
534 :
535 : // ----------------------------------------------------------------------------
536 : // Miscellaneous
537 :
538 : // Memory offset for lower and higher bits in a 64 bit integer.
539 : #if defined(V8_TARGET_LITTLE_ENDIAN)
540 : static const int kInt64LowerHalfMemoryOffset = 0;
541 : static const int kInt64UpperHalfMemoryOffset = 4;
542 : #elif defined(V8_TARGET_BIG_ENDIAN)
543 : static const int kInt64LowerHalfMemoryOffset = 4;
544 : static const int kInt64UpperHalfMemoryOffset = 0;
545 : #endif // V8_TARGET_LITTLE_ENDIAN
546 :
547 : // A static resource holds a static instance that can be reserved in
548 : // a local scope using an instance of Access. Attempts to re-reserve
549 : // the instance will cause an error.
550 : template <typename T>
551 : class StaticResource {
552 : public:
553 62883 : StaticResource() : is_reserved_(false) {}
554 :
555 : private:
556 : template <typename S> friend class Access;
557 : T instance_;
558 : bool is_reserved_;
559 : };
560 :
561 :
562 : // Locally scoped access to a static resource.
563 : template <typename T>
564 : class Access {
565 : public:
566 : explicit Access(StaticResource<T>* resource)
567 : : resource_(resource)
568 5821 : , instance_(&resource->instance_) {
569 : DCHECK(!resource->is_reserved_);
570 5821 : resource->is_reserved_ = true;
571 : }
572 :
573 : ~Access() {
574 5821 : resource_->is_reserved_ = false;
575 : resource_ = nullptr;
576 : instance_ = nullptr;
577 : }
578 :
579 : T* value() { return instance_; }
580 : T* operator -> () { return instance_; }
581 :
582 : private:
583 : StaticResource<T>* resource_;
584 : T* instance_;
585 : };
586 :
587 : // A pointer that can only be set once and doesn't allow NULL values.
588 : template<typename T>
589 : class SetOncePointer {
590 : public:
591 : SetOncePointer() = default;
592 :
593 7462381 : bool is_set() const { return pointer_ != nullptr; }
594 :
595 : T* get() const {
596 : DCHECK_NOT_NULL(pointer_);
597 10639906 : return pointer_;
598 : }
599 :
600 : void set(T* value) {
601 : DCHECK(pointer_ == nullptr && value != nullptr);
602 1925975 : pointer_ = value;
603 : }
604 :
605 : T* operator=(T* value) {
606 : set(value);
607 : return value;
608 : }
609 :
610 108272 : bool operator==(std::nullptr_t) const { return pointer_ == nullptr; }
611 : bool operator!=(std::nullptr_t) const { return pointer_ != nullptr; }
612 :
613 : private:
614 : T* pointer_ = nullptr;
615 : };
616 :
617 :
618 : template <typename T, int kSize>
619 : class EmbeddedVector : public Vector<T> {
620 : public:
621 1467778764 : EmbeddedVector() : Vector<T>(buffer_, kSize) { }
622 :
623 : explicit EmbeddedVector(T initial_value) : Vector<T>(buffer_, kSize) {
624 1024 : for (int i = 0; i < kSize; ++i) {
625 1024 : buffer_[i] = initial_value;
626 : }
627 : }
628 :
629 : // When copying, make underlying Vector to reference our buffer.
630 : EmbeddedVector(const EmbeddedVector& rhs) V8_NOEXCEPT : Vector<T>(rhs) {
631 : MemCopy(buffer_, rhs.buffer_, sizeof(T) * kSize);
632 : this->set_start(buffer_);
633 : }
634 :
635 : EmbeddedVector& operator=(const EmbeddedVector& rhs) V8_NOEXCEPT {
636 : if (this == &rhs) return *this;
637 : Vector<T>::operator=(rhs);
638 : MemCopy(buffer_, rhs.buffer_, sizeof(T) * kSize);
639 : this->set_start(buffer_);
640 : return *this;
641 : }
642 :
643 : private:
644 : T buffer_[kSize];
645 : };
646 :
647 : // Compare 8bit/16bit chars to 8bit/16bit chars.
648 : template <typename lchar, typename rchar>
649 : inline int CompareCharsUnsigned(const lchar* lhs, const rchar* rhs,
650 : size_t chars) {
651 815834 : const lchar* limit = lhs + chars;
652 : if (sizeof(*lhs) == sizeof(char) && sizeof(*rhs) == sizeof(char)) {
653 : // memcmp compares byte-by-byte, yielding wrong results for two-byte
654 : // strings on little-endian systems.
655 147710336 : return memcmp(lhs, rhs, chars);
656 : }
657 3914910 : while (lhs < limit) {
658 3116968 : int r = static_cast<int>(*lhs) - static_cast<int>(*rhs);
659 3116968 : if (r != 0) return r;
660 3099076 : ++lhs;
661 3099076 : ++rhs;
662 : }
663 : return 0;
664 : }
665 :
666 : template <typename lchar, typename rchar>
667 : inline int CompareChars(const lchar* lhs, const rchar* rhs, size_t chars) {
668 : DCHECK_LE(sizeof(lchar), 2);
669 : DCHECK_LE(sizeof(rchar), 2);
670 : if (sizeof(lchar) == 1) {
671 : if (sizeof(rchar) == 1) {
672 : return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
673 : reinterpret_cast<const uint8_t*>(rhs),
674 : chars);
675 : } else {
676 : return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
677 : reinterpret_cast<const uint16_t*>(rhs),
678 : chars);
679 : }
680 : } else {
681 : if (sizeof(rchar) == 1) {
682 : return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
683 : reinterpret_cast<const uint8_t*>(rhs),
684 : chars);
685 : } else {
686 : return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
687 : reinterpret_cast<const uint16_t*>(rhs),
688 : chars);
689 : }
690 : }
691 : }
692 :
693 :
694 : // Calculate 10^exponent.
695 : inline int TenToThe(int exponent) {
696 : DCHECK_LE(exponent, 9);
697 : DCHECK_GE(exponent, 1);
698 : int answer = 10;
699 : for (int i = 1; i < exponent; i++) answer *= 10;
700 : return answer;
701 : }
702 :
703 :
704 : template<typename ElementType, int NumElements>
705 : class EmbeddedContainer {
706 : public:
707 : EmbeddedContainer() : elems_() { }
708 :
709 : int length() const { return NumElements; }
710 : const ElementType& operator[](int i) const {
711 : DCHECK(i < length());
712 : return elems_[i];
713 : }
714 : ElementType& operator[](int i) {
715 : DCHECK(i < length());
716 : return elems_[i];
717 : }
718 :
719 : private:
720 : ElementType elems_[NumElements];
721 : };
722 :
723 :
724 : template<typename ElementType>
725 : class EmbeddedContainer<ElementType, 0> {
726 : public:
727 : int length() const { return 0; }
728 : const ElementType& operator[](int i) const {
729 : UNREACHABLE();
730 : static ElementType t = 0;
731 : return t;
732 : }
733 : ElementType& operator[](int i) {
734 : UNREACHABLE();
735 : static ElementType t = 0;
736 : return t;
737 : }
738 : };
739 :
740 :
741 : // Helper class for building result strings in a character buffer. The
742 : // purpose of the class is to use safe operations that checks the
743 : // buffer bounds on all operations in debug mode.
744 : // This simple base class does not allow formatted output.
745 : class SimpleStringBuilder {
746 : public:
747 : // Create a string builder with a buffer of the given size. The
748 : // buffer is allocated through NewArray<char> and must be
749 : // deallocated by the caller of Finalize().
750 : explicit SimpleStringBuilder(int size);
751 :
752 : SimpleStringBuilder(char* buffer, int size)
753 2253656 : : buffer_(buffer, size), position_(0) { }
754 :
755 1136772 : ~SimpleStringBuilder() { if (!is_finalized()) Finalize(); }
756 :
757 : int size() const { return buffer_.length(); }
758 :
759 : // Get the current position in the builder.
760 : int position() const {
761 : DCHECK(!is_finalized());
762 : return position_;
763 : }
764 :
765 : // Reset the position.
766 0 : void Reset() { position_ = 0; }
767 :
768 : // Add a single character to the builder. It is not allowed to add
769 : // 0-characters; use the Finalize() method to terminate the string
770 : // instead.
771 : void AddCharacter(char c) {
772 : DCHECK_NE(c, '\0');
773 : DCHECK(!is_finalized() && position_ < buffer_.length());
774 4220922 : buffer_[position_++] = c;
775 : }
776 :
777 : // Add an entire string to the builder. Uses strlen() internally to
778 : // compute the length of the input string.
779 : void AddString(const char* s);
780 :
781 : // Add the first 'n' characters of the given 0-terminated string 's' to the
782 : // builder. The input string must have enough characters.
783 : void AddSubstring(const char* s, int n);
784 :
785 : // Add character padding to the builder. If count is non-positive,
786 : // nothing is added to the builder.
787 : void AddPadding(char c, int count);
788 :
789 : // Add the decimal representation of the value.
790 : void AddDecimalInteger(int value);
791 :
792 : // Finalize the string by 0-terminating it and returning the buffer.
793 : char* Finalize();
794 :
795 : protected:
796 : Vector<char> buffer_;
797 : int position_;
798 :
799 : bool is_finalized() const { return position_ < 0; }
800 :
801 : private:
802 : DISALLOW_IMPLICIT_CONSTRUCTORS(SimpleStringBuilder);
803 : };
804 :
805 : // Bit field extraction.
806 : inline uint32_t unsigned_bitextract_32(int msb, int lsb, uint32_t x) {
807 : return (x >> lsb) & ((1 << (1 + msb - lsb)) - 1);
808 : }
809 :
810 : inline uint64_t unsigned_bitextract_64(int msb, int lsb, uint64_t x) {
811 : return (x >> lsb) & ((static_cast<uint64_t>(1) << (1 + msb - lsb)) - 1);
812 : }
813 :
814 : inline int32_t signed_bitextract_32(int msb, int lsb, int32_t x) {
815 : return (x << (31 - msb)) >> (lsb + 31 - msb);
816 : }
817 :
818 : inline int signed_bitextract_64(int msb, int lsb, int x) {
819 : // TODO(jbramley): This is broken for big bitfields.
820 : return (x << (63 - msb)) >> (lsb + 63 - msb);
821 : }
822 :
823 : // Check number width.
824 : inline bool is_intn(int64_t x, unsigned n) {
825 : DCHECK((0 < n) && (n < 64));
826 : int64_t limit = static_cast<int64_t>(1) << (n - 1);
827 67997268 : return (-limit <= x) && (x < limit);
828 : }
829 :
830 : inline bool is_uintn(int64_t x, unsigned n) {
831 : DCHECK((0 < n) && (n < (sizeof(x) * kBitsPerByte)));
832 19929285 : return !(x >> n);
833 : }
834 :
835 : template <class T>
836 : inline T truncate_to_intn(T x, unsigned n) {
837 : DCHECK((0 < n) && (n < (sizeof(x) * kBitsPerByte)));
838 : return (x & ((static_cast<T>(1) << n) - 1));
839 : }
840 :
841 : #define INT_1_TO_63_LIST(V) \
842 : V(1) V(2) V(3) V(4) V(5) V(6) V(7) V(8) \
843 : V(9) V(10) V(11) V(12) V(13) V(14) V(15) V(16) \
844 : V(17) V(18) V(19) V(20) V(21) V(22) V(23) V(24) \
845 : V(25) V(26) V(27) V(28) V(29) V(30) V(31) V(32) \
846 : V(33) V(34) V(35) V(36) V(37) V(38) V(39) V(40) \
847 : V(41) V(42) V(43) V(44) V(45) V(46) V(47) V(48) \
848 : V(49) V(50) V(51) V(52) V(53) V(54) V(55) V(56) \
849 : V(57) V(58) V(59) V(60) V(61) V(62) V(63)
850 :
851 : #define DECLARE_IS_INT_N(N) \
852 : inline bool is_int##N(int64_t x) { return is_intn(x, N); }
853 : #define DECLARE_IS_UINT_N(N) \
854 : template <class T> \
855 : inline bool is_uint##N(T x) { return is_uintn(x, N); }
856 : #define DECLARE_TRUNCATE_TO_INT_N(N) \
857 : template <class T> \
858 : inline T truncate_to_int##N(T x) { return truncate_to_intn(x, N); }
859 : INT_1_TO_63_LIST(DECLARE_IS_INT_N)
860 6068894 : INT_1_TO_63_LIST(DECLARE_IS_UINT_N)
861 : INT_1_TO_63_LIST(DECLARE_TRUNCATE_TO_INT_N)
862 : #undef DECLARE_IS_INT_N
863 : #undef DECLARE_IS_UINT_N
864 : #undef DECLARE_TRUNCATE_TO_INT_N
865 :
866 : // clang-format off
867 : #define INT_0_TO_127_LIST(V) \
868 : V(0) V(1) V(2) V(3) V(4) V(5) V(6) V(7) V(8) V(9) \
869 : V(10) V(11) V(12) V(13) V(14) V(15) V(16) V(17) V(18) V(19) \
870 : V(20) V(21) V(22) V(23) V(24) V(25) V(26) V(27) V(28) V(29) \
871 : V(30) V(31) V(32) V(33) V(34) V(35) V(36) V(37) V(38) V(39) \
872 : V(40) V(41) V(42) V(43) V(44) V(45) V(46) V(47) V(48) V(49) \
873 : V(50) V(51) V(52) V(53) V(54) V(55) V(56) V(57) V(58) V(59) \
874 : V(60) V(61) V(62) V(63) V(64) V(65) V(66) V(67) V(68) V(69) \
875 : V(70) V(71) V(72) V(73) V(74) V(75) V(76) V(77) V(78) V(79) \
876 : V(80) V(81) V(82) V(83) V(84) V(85) V(86) V(87) V(88) V(89) \
877 : V(90) V(91) V(92) V(93) V(94) V(95) V(96) V(97) V(98) V(99) \
878 : V(100) V(101) V(102) V(103) V(104) V(105) V(106) V(107) V(108) V(109) \
879 : V(110) V(111) V(112) V(113) V(114) V(115) V(116) V(117) V(118) V(119) \
880 : V(120) V(121) V(122) V(123) V(124) V(125) V(126) V(127)
881 : // clang-format on
882 :
883 : class FeedbackSlot {
884 : public:
885 259545335 : FeedbackSlot() : id_(kInvalidSlot) {}
886 2111217 : explicit FeedbackSlot(int id) : id_(id) {}
887 :
888 1494749 : int ToInt() const { return id_; }
889 :
890 : static FeedbackSlot Invalid() { return FeedbackSlot(); }
891 2857146 : bool IsInvalid() const { return id_ == kInvalidSlot; }
892 :
893 15 : bool operator==(FeedbackSlot that) const { return this->id_ == that.id_; }
894 : bool operator!=(FeedbackSlot that) const { return !(*this == that); }
895 :
896 0 : friend size_t hash_value(FeedbackSlot slot) { return slot.ToInt(); }
897 : friend std::ostream& operator<<(std::ostream& os, FeedbackSlot);
898 :
899 : private:
900 : static const int kInvalidSlot = -1;
901 :
902 : int id_;
903 : };
904 :
905 :
906 : class BailoutId {
907 : public:
908 7128432 : explicit BailoutId(int id) : id_(id) { }
909 3308157 : int ToInt() const { return id_; }
910 :
911 : static BailoutId None() { return BailoutId(kNoneId); }
912 : static BailoutId ScriptContext() { return BailoutId(kScriptContextId); }
913 : static BailoutId FunctionContext() { return BailoutId(kFunctionContextId); }
914 : static BailoutId FunctionEntry() { return BailoutId(kFunctionEntryId); }
915 : static BailoutId Declarations() { return BailoutId(kDeclarationsId); }
916 : static BailoutId FirstUsable() { return BailoutId(kFirstUsableId); }
917 : static BailoutId StubEntry() { return BailoutId(kStubEntryId); }
918 :
919 : // Special bailout id support for deopting into the {JSConstructStub} stub.
920 : // The following hard-coded deoptimization points are supported by the stub:
921 : // - {ConstructStubCreate} maps to {construct_stub_create_deopt_pc_offset}.
922 : // - {ConstructStubInvoke} maps to {construct_stub_invoke_deopt_pc_offset}.
923 : static BailoutId ConstructStubCreate() { return BailoutId(1); }
924 : static BailoutId ConstructStubInvoke() { return BailoutId(2); }
925 : bool IsValidForConstructStub() const {
926 : return id_ == ConstructStubCreate().ToInt() ||
927 : id_ == ConstructStubInvoke().ToInt();
928 : }
929 :
930 12120362 : bool IsNone() const { return id_ == kNoneId; }
931 2 : bool operator==(const BailoutId& other) const { return id_ == other.id_; }
932 : bool operator!=(const BailoutId& other) const { return id_ != other.id_; }
933 : friend size_t hash_value(BailoutId);
934 : V8_EXPORT_PRIVATE friend std::ostream& operator<<(std::ostream&, BailoutId);
935 :
936 : private:
937 : friend class Builtins;
938 :
939 : static const int kNoneId = -1;
940 :
941 : // Using 0 could disguise errors.
942 : static const int kScriptContextId = 1;
943 : static const int kFunctionContextId = 2;
944 : static const int kFunctionEntryId = 3;
945 :
946 : // This AST id identifies the point after the declarations have been visited.
947 : // We need it to capture the environment effects of declarations that emit
948 : // code (function declarations).
949 : static const int kDeclarationsId = 4;
950 :
951 : // Every FunctionState starts with this id.
952 : static const int kFirstUsableId = 5;
953 :
954 : // Every compiled stub starts with this id.
955 : static const int kStubEntryId = 6;
956 :
957 : // Builtin continuations bailout ids start here. If you need to add a
958 : // non-builtin BailoutId, add it before this id so that this Id has the
959 : // highest number.
960 : static const int kFirstBuiltinContinuationId = 7;
961 :
962 : int id_;
963 : };
964 :
965 :
966 : // ----------------------------------------------------------------------------
967 : // I/O support.
968 :
969 : // Our version of printf().
970 : V8_EXPORT_PRIVATE void PRINTF_FORMAT(1, 2) PrintF(const char* format, ...);
971 : void PRINTF_FORMAT(2, 3) PrintF(FILE* out, const char* format, ...);
972 :
973 : // Prepends the current process ID to the output.
974 : void PRINTF_FORMAT(1, 2) PrintPID(const char* format, ...);
975 :
976 : // Prepends the current process ID and given isolate pointer to the output.
977 : void PRINTF_FORMAT(2, 3) PrintIsolate(void* isolate, const char* format, ...);
978 :
979 : // Safe formatting print. Ensures that str is always null-terminated.
980 : // Returns the number of chars written, or -1 if output was truncated.
981 : int PRINTF_FORMAT(2, 3) SNPrintF(Vector<char> str, const char* format, ...);
982 : V8_EXPORT_PRIVATE int PRINTF_FORMAT(2, 0)
983 : VSNPrintF(Vector<char> str, const char* format, va_list args);
984 :
985 : void StrNCpy(Vector<char> dest, const char* src, size_t n);
986 :
987 : // Our version of fflush.
988 : void Flush(FILE* out);
989 :
990 : inline void Flush() {
991 : Flush(stdout);
992 : }
993 :
994 :
995 : // Read a line of characters after printing the prompt to stdout. The resulting
996 : // char* needs to be disposed off with DeleteArray by the caller.
997 : char* ReadLine(const char* prompt);
998 :
999 :
1000 : // Append size chars from str to the file given by filename.
1001 : // The file is overwritten. Returns the number of chars written.
1002 : int AppendChars(const char* filename,
1003 : const char* str,
1004 : int size,
1005 : bool verbose = true);
1006 :
1007 :
1008 : // Write size chars from str to the file given by filename.
1009 : // The file is overwritten. Returns the number of chars written.
1010 : int WriteChars(const char* filename,
1011 : const char* str,
1012 : int size,
1013 : bool verbose = true);
1014 :
1015 :
1016 : // Write size bytes to the file given by filename.
1017 : // The file is overwritten. Returns the number of bytes written.
1018 : int WriteBytes(const char* filename,
1019 : const byte* bytes,
1020 : int size,
1021 : bool verbose = true);
1022 :
1023 :
1024 : // Write the C code
1025 : // const char* <varname> = "<str>";
1026 : // const int <varname>_len = <len>;
1027 : // to the file given by filename. Only the first len chars are written.
1028 : int WriteAsCFile(const char* filename, const char* varname,
1029 : const char* str, int size, bool verbose = true);
1030 :
1031 :
1032 : // Simple support to read a file into std::string.
1033 : // On return, *exits tells whether the file existed.
1034 : V8_EXPORT_PRIVATE std::string ReadFile(const char* filename, bool* exists,
1035 : bool verbose = true);
1036 : std::string ReadFile(FILE* file, bool* exists, bool verbose = true);
1037 :
1038 : class StringBuilder : public SimpleStringBuilder {
1039 : public:
1040 : explicit StringBuilder(int size) : SimpleStringBuilder(size) { }
1041 : StringBuilder(char* buffer, int size) : SimpleStringBuilder(buffer, size) { }
1042 :
1043 : // Add formatted contents to the builder just like printf().
1044 : void PRINTF_FORMAT(2, 3) AddFormatted(const char* format, ...);
1045 :
1046 : // Add formatted contents like printf based on a va_list.
1047 : void PRINTF_FORMAT(2, 0) AddFormattedList(const char* format, va_list list);
1048 :
1049 : private:
1050 : DISALLOW_IMPLICIT_CONSTRUCTORS(StringBuilder);
1051 : };
1052 :
1053 :
1054 : bool DoubleToBoolean(double d);
1055 :
1056 : template <typename Char>
1057 : bool TryAddIndexChar(uint32_t* index, Char c);
1058 :
1059 : template <typename Stream>
1060 : bool StringToArrayIndex(Stream* stream, uint32_t* index);
1061 :
1062 : // Returns the current stack top. Works correctly with ASAN and SafeStack.
1063 : // GetCurrentStackPosition() should not be inlined, because it works on stack
1064 : // frames if it were inlined into a function with a huge stack frame it would
1065 : // return an address significantly above the actual current stack position.
1066 : V8_NOINLINE uintptr_t GetCurrentStackPosition();
1067 :
1068 : template <typename V>
1069 : static inline V ByteReverse(V value) {
1070 : size_t size_of_v = sizeof(value);
1071 : switch (size_of_v) {
1072 : case 2:
1073 : #if V8_HAS_BUILTIN_BSWAP16
1074 : return static_cast<V>(__builtin_bswap16(static_cast<uint16_t>(value)));
1075 : #else
1076 : return value << 8 | (value >> 8 & 0x00FF);
1077 : #endif
1078 : case 4:
1079 : #if V8_HAS_BUILTIN_BSWAP32
1080 : return static_cast<V>(__builtin_bswap32(static_cast<uint32_t>(value)));
1081 : #else
1082 : {
1083 : size_t bits_of_v = size_of_v * kBitsPerByte;
1084 : return value << (bits_of_v - 8) |
1085 : ((value << (bits_of_v - 24)) & 0x00FF0000) |
1086 : ((value >> (bits_of_v - 24)) & 0x0000FF00) |
1087 : ((value >> (bits_of_v - 8)) & 0x00000FF);
1088 : }
1089 : #endif
1090 : case 8:
1091 : #if V8_HAS_BUILTIN_BSWAP64
1092 : return static_cast<V>(__builtin_bswap64(static_cast<uint64_t>(value)));
1093 : #else
1094 : {
1095 : size_t bits_of_v = size_of_v * kBitsPerByte;
1096 : return value << (bits_of_v - 8) |
1097 : ((value << (bits_of_v - 24)) & 0x00FF000000000000) |
1098 : ((value << (bits_of_v - 40)) & 0x0000FF0000000000) |
1099 : ((value << (bits_of_v - 56)) & 0x000000FF00000000) |
1100 : ((value >> (bits_of_v - 56)) & 0x00000000FF000000) |
1101 : ((value >> (bits_of_v - 40)) & 0x0000000000FF0000) |
1102 : ((value >> (bits_of_v - 24)) & 0x000000000000FF00) |
1103 : ((value >> (bits_of_v - 8)) & 0x00000000000000FF);
1104 : }
1105 : #endif
1106 : default:
1107 : UNREACHABLE();
1108 : }
1109 : }
1110 :
1111 : V8_EXPORT_PRIVATE bool PassesFilter(Vector<const char> name,
1112 : Vector<const char> filter);
1113 :
1114 : // Zap the specified area with a specific byte pattern. This currently defaults
1115 : // to int3 on x64 and ia32. On other architectures this will produce unspecified
1116 : // instruction sequences.
1117 : // TODO(jgruber): Better support for other architectures.
1118 : V8_INLINE void ZapCode(Address addr, size_t size_in_bytes) {
1119 : static constexpr int kZapByte = 0xCC;
1120 0 : std::memset(reinterpret_cast<void*>(addr), kZapByte, size_in_bytes);
1121 : }
1122 :
1123 : } // namespace internal
1124 : } // namespace v8
1125 :
1126 : #endif // V8_UTILS_H_
|
