V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
types.cc
1 // Copyright 2014 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 #include <iomanip>
6 
7 #include "src/compiler/types.h"
8 
9 #include "src/handles-inl.h"
10 #include "src/objects-inl.h"
11 #include "src/ostreams.h"
12 
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16 
17 // -----------------------------------------------------------------------------
18 // Range-related helper functions.
19 
20 bool RangeType::Limits::IsEmpty() { return this->min > this->max; }
21 
22 RangeType::Limits RangeType::Limits::Intersect(Limits lhs, Limits rhs) {
23  DisallowHeapAllocation no_allocation;
24  Limits result(lhs);
25  if (lhs.min < rhs.min) result.min = rhs.min;
26  if (lhs.max > rhs.max) result.max = rhs.max;
27  return result;
28 }
29 
30 RangeType::Limits RangeType::Limits::Union(Limits lhs, Limits rhs) {
31  DisallowHeapAllocation no_allocation;
32  if (lhs.IsEmpty()) return rhs;
33  if (rhs.IsEmpty()) return lhs;
34  Limits result(lhs);
35  if (lhs.min > rhs.min) result.min = rhs.min;
36  if (lhs.max < rhs.max) result.max = rhs.max;
37  return result;
38 }
39 
40 bool Type::Overlap(const RangeType* lhs, const RangeType* rhs) {
41  DisallowHeapAllocation no_allocation;
42  return !RangeType::Limits::Intersect(RangeType::Limits(lhs),
43  RangeType::Limits(rhs))
44  .IsEmpty();
45 }
46 
47 bool Type::Contains(const RangeType* lhs, const RangeType* rhs) {
48  DisallowHeapAllocation no_allocation;
49  return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
50 }
51 
52 // -----------------------------------------------------------------------------
53 // Min and Max computation.
54 
55 double Type::Min() const {
56  DCHECK(this->Is(Number()));
57  DCHECK(!this->Is(NaN()));
58  if (this->IsBitset()) return BitsetType::Min(this->AsBitset());
59  if (this->IsUnion()) {
60  double min = +V8_INFINITY;
61  for (int i = 1, n = AsUnion()->Length(); i < n; ++i) {
62  min = std::min(min, AsUnion()->Get(i).Min());
63  }
64  Type bitset = AsUnion()->Get(0);
65  if (!bitset.Is(NaN())) min = std::min(min, bitset.Min());
66  return min;
67  }
68  if (this->IsRange()) return this->AsRange()->Min();
69  DCHECK(this->IsOtherNumberConstant());
70  return this->AsOtherNumberConstant()->Value();
71 }
72 
73 double Type::Max() const {
74  DCHECK(this->Is(Number()));
75  DCHECK(!this->Is(NaN()));
76  if (this->IsBitset()) return BitsetType::Max(this->AsBitset());
77  if (this->IsUnion()) {
78  double max = -V8_INFINITY;
79  for (int i = 1, n = this->AsUnion()->Length(); i < n; ++i) {
80  max = std::max(max, this->AsUnion()->Get(i).Max());
81  }
82  Type bitset = this->AsUnion()->Get(0);
83  if (!bitset.Is(NaN())) max = std::max(max, bitset.Max());
84  return max;
85  }
86  if (this->IsRange()) return this->AsRange()->Max();
87  DCHECK(this->IsOtherNumberConstant());
88  return this->AsOtherNumberConstant()->Value();
89 }
90 
91 // -----------------------------------------------------------------------------
92 // Glb and lub computation.
93 
94 // The largest bitset subsumed by this type.
95 Type::bitset Type::BitsetGlb() const {
96  DisallowHeapAllocation no_allocation;
97  // Fast case.
98  if (IsBitset()) {
99  return AsBitset();
100  } else if (IsUnion()) {
101  SLOW_DCHECK(AsUnion()->Wellformed());
102  return AsUnion()->Get(0).BitsetGlb() |
103  AsUnion()->Get(1).BitsetGlb(); // Shortcut.
104  } else if (IsRange()) {
105  bitset glb = BitsetType::Glb(AsRange()->Min(), AsRange()->Max());
106  return glb;
107  } else {
108  return BitsetType::kNone;
109  }
110 }
111 
112 // The smallest bitset subsuming this type, possibly not a proper one.
113 Type::bitset Type::BitsetLub() const {
114  DisallowHeapAllocation no_allocation;
115  if (IsBitset()) return AsBitset();
116  if (IsUnion()) {
117  // Take the representation from the first element, which is always
118  // a bitset.
119  int bitset = AsUnion()->Get(0).BitsetLub();
120  for (int i = 0, n = AsUnion()->Length(); i < n; ++i) {
121  // Other elements only contribute their semantic part.
122  bitset |= AsUnion()->Get(i).BitsetLub();
123  }
124  return bitset;
125  }
126  if (IsHeapConstant()) return AsHeapConstant()->Lub();
127  if (IsOtherNumberConstant()) {
128  return AsOtherNumberConstant()->Lub();
129  }
130  if (IsRange()) return AsRange()->Lub();
131  if (IsTuple()) return BitsetType::kOtherInternal;
132  UNREACHABLE();
133 }
134 
135 // TODO(neis): Once the broker mode kDisabled is gone, change the input type to
136 // MapRef and get rid of the HeapObjectType class.
137 template <typename MapRefLike>
138 Type::bitset BitsetType::Lub(const MapRefLike& map) {
139  switch (map.instance_type()) {
140  case CONS_STRING_TYPE:
141  case CONS_ONE_BYTE_STRING_TYPE:
142  case THIN_STRING_TYPE:
143  case THIN_ONE_BYTE_STRING_TYPE:
144  case SLICED_STRING_TYPE:
145  case SLICED_ONE_BYTE_STRING_TYPE:
146  case EXTERNAL_STRING_TYPE:
147  case EXTERNAL_ONE_BYTE_STRING_TYPE:
148  case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
149  case UNCACHED_EXTERNAL_STRING_TYPE:
150  case UNCACHED_EXTERNAL_ONE_BYTE_STRING_TYPE:
151  case UNCACHED_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
152  case STRING_TYPE:
153  case ONE_BYTE_STRING_TYPE:
154  return kString;
155  case EXTERNAL_INTERNALIZED_STRING_TYPE:
156  case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
157  case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
158  case UNCACHED_EXTERNAL_INTERNALIZED_STRING_TYPE:
159  case UNCACHED_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
160  case UNCACHED_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
161  case INTERNALIZED_STRING_TYPE:
162  case ONE_BYTE_INTERNALIZED_STRING_TYPE:
163  return kInternalizedString;
164  case SYMBOL_TYPE:
165  return kSymbol;
166  case BIGINT_TYPE:
167  return kBigInt;
168  case ODDBALL_TYPE:
169  switch (map.oddball_type()) {
170  case OddballType::kNone:
171  break;
172  case OddballType::kHole:
173  return kHole;
174  case OddballType::kBoolean:
175  return kBoolean;
176  case OddballType::kNull:
177  return kNull;
178  case OddballType::kUndefined:
179  return kUndefined;
180  case OddballType::kUninitialized:
181  case OddballType::kOther:
182  // TODO(neis): We should add a kOtherOddball type.
183  return kOtherInternal;
184  }
185  UNREACHABLE();
186  case HEAP_NUMBER_TYPE:
187  return kNumber;
188  case JS_OBJECT_TYPE:
189  case JS_ARGUMENTS_TYPE:
190  case JS_ERROR_TYPE:
191  case JS_GLOBAL_OBJECT_TYPE:
192  case JS_GLOBAL_PROXY_TYPE:
193  case JS_API_OBJECT_TYPE:
194  case JS_SPECIAL_API_OBJECT_TYPE:
195  if (map.is_undetectable()) {
196  // Currently we assume that every undetectable receiver is also
197  // callable, which is what we need to support document.all. We
198  // could add another Type bit to support other use cases in the
199  // future if necessary.
200  DCHECK(map.is_callable());
201  return kOtherUndetectable;
202  }
203  if (map.is_callable()) {
204  return kOtherCallable;
205  }
206  return kOtherObject;
207  case JS_ARRAY_TYPE:
208  return kArray;
209  case JS_VALUE_TYPE:
210  case JS_MESSAGE_OBJECT_TYPE:
211  case JS_DATE_TYPE:
212 #ifdef V8_INTL_SUPPORT
213  case JS_INTL_V8_BREAK_ITERATOR_TYPE:
214  case JS_INTL_COLLATOR_TYPE:
215  case JS_INTL_DATE_TIME_FORMAT_TYPE:
216  case JS_INTL_LIST_FORMAT_TYPE:
217  case JS_INTL_LOCALE_TYPE:
218  case JS_INTL_NUMBER_FORMAT_TYPE:
219  case JS_INTL_PLURAL_RULES_TYPE:
220  case JS_INTL_RELATIVE_TIME_FORMAT_TYPE:
221  case JS_INTL_SEGMENT_ITERATOR_TYPE:
222  case JS_INTL_SEGMENTER_TYPE:
223 #endif // V8_INTL_SUPPORT
224  case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
225  case JS_GENERATOR_OBJECT_TYPE:
226  case JS_ASYNC_FUNCTION_OBJECT_TYPE:
227  case JS_ASYNC_GENERATOR_OBJECT_TYPE:
228  case JS_MODULE_NAMESPACE_TYPE:
229  case JS_ARRAY_BUFFER_TYPE:
230  case JS_ARRAY_ITERATOR_TYPE:
231  case JS_REGEXP_TYPE: // TODO(rossberg): there should be a RegExp type.
232  case JS_REGEXP_STRING_ITERATOR_TYPE:
233  case JS_TYPED_ARRAY_TYPE:
234  case JS_DATA_VIEW_TYPE:
235  case JS_SET_TYPE:
236  case JS_MAP_TYPE:
237  case JS_SET_KEY_VALUE_ITERATOR_TYPE:
238  case JS_SET_VALUE_ITERATOR_TYPE:
239  case JS_MAP_KEY_ITERATOR_TYPE:
240  case JS_MAP_KEY_VALUE_ITERATOR_TYPE:
241  case JS_MAP_VALUE_ITERATOR_TYPE:
242  case JS_STRING_ITERATOR_TYPE:
243  case JS_ASYNC_FROM_SYNC_ITERATOR_TYPE:
244  case JS_WEAK_CELL_TYPE:
245  case JS_WEAK_FACTORY_TYPE:
246  case JS_WEAK_FACTORY_CLEANUP_ITERATOR_TYPE:
247  case JS_WEAK_MAP_TYPE:
248  case JS_WEAK_REF_TYPE:
249  case JS_WEAK_SET_TYPE:
250  case JS_PROMISE_TYPE:
251  case WASM_EXCEPTION_TYPE:
252  case WASM_GLOBAL_TYPE:
253  case WASM_INSTANCE_TYPE:
254  case WASM_MEMORY_TYPE:
255  case WASM_MODULE_TYPE:
256  case WASM_TABLE_TYPE:
257  DCHECK(!map.is_callable());
258  DCHECK(!map.is_undetectable());
259  return kOtherObject;
260  case JS_BOUND_FUNCTION_TYPE:
261  DCHECK(!map.is_undetectable());
262  return kBoundFunction;
263  case JS_FUNCTION_TYPE:
264  DCHECK(!map.is_undetectable());
265  return kFunction;
266  case JS_PROXY_TYPE:
267  DCHECK(!map.is_undetectable());
268  if (map.is_callable()) return kCallableProxy;
269  return kOtherProxy;
270  case MAP_TYPE:
271  case ALLOCATION_SITE_TYPE:
272  case ACCESSOR_INFO_TYPE:
273  case SHARED_FUNCTION_INFO_TYPE:
274  case FUNCTION_TEMPLATE_INFO_TYPE:
275  case FUNCTION_TEMPLATE_RARE_DATA_TYPE:
276  case ACCESSOR_PAIR_TYPE:
277  case EMBEDDER_DATA_ARRAY_TYPE:
278  case FIXED_ARRAY_TYPE:
279  case HASH_TABLE_TYPE:
280  case ORDERED_HASH_MAP_TYPE:
281  case ORDERED_HASH_SET_TYPE:
282  case ORDERED_NAME_DICTIONARY_TYPE:
283  case NAME_DICTIONARY_TYPE:
284  case GLOBAL_DICTIONARY_TYPE:
285  case NUMBER_DICTIONARY_TYPE:
286  case SIMPLE_NUMBER_DICTIONARY_TYPE:
287  case STRING_TABLE_TYPE:
288  case EPHEMERON_HASH_TABLE_TYPE:
289  case WEAK_FIXED_ARRAY_TYPE:
290  case WEAK_ARRAY_LIST_TYPE:
291  case FIXED_DOUBLE_ARRAY_TYPE:
292  case FEEDBACK_METADATA_TYPE:
293  case BYTE_ARRAY_TYPE:
294  case BYTECODE_ARRAY_TYPE:
295  case OBJECT_BOILERPLATE_DESCRIPTION_TYPE:
296  case ARRAY_BOILERPLATE_DESCRIPTION_TYPE:
297  case DESCRIPTOR_ARRAY_TYPE:
298  case TRANSITION_ARRAY_TYPE:
299  case FEEDBACK_CELL_TYPE:
300  case FEEDBACK_VECTOR_TYPE:
301  case PROPERTY_ARRAY_TYPE:
302  case FOREIGN_TYPE:
303  case SCOPE_INFO_TYPE:
304  case SCRIPT_CONTEXT_TABLE_TYPE:
305  case AWAIT_CONTEXT_TYPE:
306  case BLOCK_CONTEXT_TYPE:
307  case CATCH_CONTEXT_TYPE:
308  case DEBUG_EVALUATE_CONTEXT_TYPE:
309  case EVAL_CONTEXT_TYPE:
310  case FUNCTION_CONTEXT_TYPE:
311  case MODULE_CONTEXT_TYPE:
312  case NATIVE_CONTEXT_TYPE:
313  case SCRIPT_CONTEXT_TYPE:
314  case WITH_CONTEXT_TYPE:
315  case SCRIPT_TYPE:
316  case CODE_TYPE:
317  case PROPERTY_CELL_TYPE:
318  case MODULE_TYPE:
319  case MODULE_INFO_ENTRY_TYPE:
320  case CELL_TYPE:
321  case PRE_PARSED_SCOPE_DATA_TYPE:
322  case UNCOMPILED_DATA_WITHOUT_PRE_PARSED_SCOPE_TYPE:
323  case UNCOMPILED_DATA_WITH_PRE_PARSED_SCOPE_TYPE:
324  return kOtherInternal;
325 
326  // Remaining instance types are unsupported for now. If any of them do
327  // require bit set types, they should get kOtherInternal.
328  case MUTABLE_HEAP_NUMBER_TYPE:
329  case FREE_SPACE_TYPE:
330 #define FIXED_TYPED_ARRAY_CASE(Type, type, TYPE, ctype) \
331  case FIXED_##TYPE##_ARRAY_TYPE:
332 
333  TYPED_ARRAYS(FIXED_TYPED_ARRAY_CASE)
334 #undef FIXED_TYPED_ARRAY_CASE
335  case FILLER_TYPE:
336  case ACCESS_CHECK_INFO_TYPE:
337  case ASM_WASM_DATA_TYPE:
338  case CALL_HANDLER_INFO_TYPE:
339  case INTERCEPTOR_INFO_TYPE:
340  case OBJECT_TEMPLATE_INFO_TYPE:
341  case ALLOCATION_MEMENTO_TYPE:
342  case ALIASED_ARGUMENTS_ENTRY_TYPE:
343  case PROMISE_CAPABILITY_TYPE:
344  case PROMISE_REACTION_TYPE:
345  case DEBUG_INFO_TYPE:
346  case STACK_FRAME_INFO_TYPE:
347  case SMALL_ORDERED_HASH_MAP_TYPE:
348  case SMALL_ORDERED_HASH_SET_TYPE:
349  case SMALL_ORDERED_NAME_DICTIONARY_TYPE:
350  case PROTOTYPE_INFO_TYPE:
351  case INTERPRETER_DATA_TYPE:
352  case TUPLE2_TYPE:
353  case TUPLE3_TYPE:
354  case WASM_DEBUG_INFO_TYPE:
355  case WASM_EXPORTED_FUNCTION_DATA_TYPE:
356  case LOAD_HANDLER_TYPE:
357  case STORE_HANDLER_TYPE:
358  case ASYNC_GENERATOR_REQUEST_TYPE:
359  case CODE_DATA_CONTAINER_TYPE:
360  case CALLBACK_TASK_TYPE:
361  case CALLABLE_TASK_TYPE:
362  case PROMISE_FULFILL_REACTION_JOB_TASK_TYPE:
363  case PROMISE_REJECT_REACTION_JOB_TASK_TYPE:
364  case PROMISE_RESOLVE_THENABLE_JOB_TASK_TYPE:
365  case WEAK_FACTORY_CLEANUP_JOB_TASK_TYPE:
366  UNREACHABLE();
367  }
368  UNREACHABLE();
369 }
370 
371 // Explicit instantiation.
372 template Type::bitset BitsetType::Lub<MapRef>(const MapRef& map);
373 
374 Type::bitset BitsetType::Lub(double value) {
375  DisallowHeapAllocation no_allocation;
376  if (IsMinusZero(value)) return kMinusZero;
377  if (std::isnan(value)) return kNaN;
378  if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value);
379  return kOtherNumber;
380 }
381 
382 // Minimum values of plain numeric bitsets.
383 const BitsetType::Boundary BitsetType::BoundariesArray[] = {
384  {kOtherNumber, kPlainNumber, -V8_INFINITY},
385  {kOtherSigned32, kNegative32, kMinInt},
386  {kNegative31, kNegative31, -0x40000000},
387  {kUnsigned30, kUnsigned30, 0},
388  {kOtherUnsigned31, kUnsigned31, 0x40000000},
389  {kOtherUnsigned32, kUnsigned32, 0x80000000},
390  {kOtherNumber, kPlainNumber, static_cast<double>(kMaxUInt32) + 1}};
391 
392 const BitsetType::Boundary* BitsetType::Boundaries() { return BoundariesArray; }
393 
394 size_t BitsetType::BoundariesSize() {
395  // Windows doesn't like arraysize here.
396  // return arraysize(BoundariesArray);
397  return 7;
398 }
399 
400 Type::bitset BitsetType::ExpandInternals(Type::bitset bits) {
401  DCHECK_IMPLIES(bits & kOtherString, (bits & kString) == kString);
402  DisallowHeapAllocation no_allocation;
403  if (!(bits & kPlainNumber)) return bits; // Shortcut.
404  const Boundary* boundaries = Boundaries();
405  for (size_t i = 0; i < BoundariesSize(); ++i) {
406  DCHECK(BitsetType::Is(boundaries[i].internal, boundaries[i].external));
407  if (bits & boundaries[i].internal) bits |= boundaries[i].external;
408  }
409  return bits;
410 }
411 
412 Type::bitset BitsetType::Lub(double min, double max) {
413  DisallowHeapAllocation no_allocation;
414  int lub = kNone;
415  const Boundary* mins = Boundaries();
416 
417  for (size_t i = 1; i < BoundariesSize(); ++i) {
418  if (min < mins[i].min) {
419  lub |= mins[i - 1].internal;
420  if (max < mins[i].min) return lub;
421  }
422  }
423  return lub | mins[BoundariesSize() - 1].internal;
424 }
425 
426 Type::bitset BitsetType::NumberBits(bitset bits) { return bits & kPlainNumber; }
427 
428 Type::bitset BitsetType::Glb(double min, double max) {
429  DisallowHeapAllocation no_allocation;
430  int glb = kNone;
431  const Boundary* mins = Boundaries();
432 
433  // If the range does not touch 0, the bound is empty.
434  if (max < -1 || min > 0) return glb;
435 
436  for (size_t i = 1; i + 1 < BoundariesSize(); ++i) {
437  if (min <= mins[i].min) {
438  if (max + 1 < mins[i + 1].min) break;
439  glb |= mins[i].external;
440  }
441  }
442  // OtherNumber also contains float numbers, so it can never be
443  // in the greatest lower bound.
444  return glb & ~(kOtherNumber);
445 }
446 
447 double BitsetType::Min(bitset bits) {
448  DisallowHeapAllocation no_allocation;
449  DCHECK(Is(bits, kNumber));
450  DCHECK(!Is(bits, kNaN));
451  const Boundary* mins = Boundaries();
452  bool mz = bits & kMinusZero;
453  for (size_t i = 0; i < BoundariesSize(); ++i) {
454  if (Is(mins[i].internal, bits)) {
455  return mz ? std::min(0.0, mins[i].min) : mins[i].min;
456  }
457  }
458  DCHECK(mz);
459  return 0;
460 }
461 
462 double BitsetType::Max(bitset bits) {
463  DisallowHeapAllocation no_allocation;
464  DCHECK(Is(bits, kNumber));
465  DCHECK(!Is(bits, kNaN));
466  const Boundary* mins = Boundaries();
467  bool mz = bits & kMinusZero;
468  if (BitsetType::Is(mins[BoundariesSize() - 1].internal, bits)) {
469  return +V8_INFINITY;
470  }
471  for (size_t i = BoundariesSize() - 1; i-- > 0;) {
472  if (Is(mins[i].internal, bits)) {
473  return mz ? std::max(0.0, mins[i + 1].min - 1) : mins[i + 1].min - 1;
474  }
475  }
476  DCHECK(mz);
477  return 0;
478 }
479 
480 // static
481 bool OtherNumberConstantType::IsOtherNumberConstant(double value) {
482  // Not an integer, not NaN, and not -0.
483  return !std::isnan(value) && !RangeType::IsInteger(value) &&
484  !IsMinusZero(value);
485 }
486 
487 HeapConstantType::HeapConstantType(BitsetType::bitset bitset,
488  const HeapObjectRef& heap_ref)
489  : TypeBase(kHeapConstant), bitset_(bitset), heap_ref_(heap_ref) {}
490 
491 Handle<HeapObject> HeapConstantType::Value() const {
492  return heap_ref_.object();
493 }
494 
495 // -----------------------------------------------------------------------------
496 // Predicates.
497 
498 bool Type::SimplyEquals(Type that) const {
499  DisallowHeapAllocation no_allocation;
500  if (this->IsHeapConstant()) {
501  return that.IsHeapConstant() &&
502  this->AsHeapConstant()->Value().address() ==
503  that.AsHeapConstant()->Value().address();
504  }
505  if (this->IsOtherNumberConstant()) {
506  return that.IsOtherNumberConstant() &&
507  this->AsOtherNumberConstant()->Value() ==
508  that.AsOtherNumberConstant()->Value();
509  }
510  if (this->IsRange()) {
511  if (that.IsHeapConstant() || that.IsOtherNumberConstant()) return false;
512  }
513  if (this->IsTuple()) {
514  if (!that.IsTuple()) return false;
515  const TupleType* this_tuple = this->AsTuple();
516  const TupleType* that_tuple = that.AsTuple();
517  if (this_tuple->Arity() != that_tuple->Arity()) {
518  return false;
519  }
520  for (int i = 0, n = this_tuple->Arity(); i < n; ++i) {
521  if (!this_tuple->Element(i).Equals(that_tuple->Element(i))) return false;
522  }
523  return true;
524  }
525  UNREACHABLE();
526 }
527 
528 // Check if [this] <= [that].
529 bool Type::SlowIs(Type that) const {
530  DisallowHeapAllocation no_allocation;
531 
532  // Fast bitset cases
533  if (that.IsBitset()) {
534  return BitsetType::Is(this->BitsetLub(), that.AsBitset());
535  }
536 
537  if (this->IsBitset()) {
538  return BitsetType::Is(this->AsBitset(), that.BitsetGlb());
539  }
540 
541  // (T1 \/ ... \/ Tn) <= T if (T1 <= T) /\ ... /\ (Tn <= T)
542  if (this->IsUnion()) {
543  for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
544  if (!this->AsUnion()->Get(i).Is(that)) return false;
545  }
546  return true;
547  }
548 
549  // T <= (T1 \/ ... \/ Tn) if (T <= T1) \/ ... \/ (T <= Tn)
550  if (that.IsUnion()) {
551  for (int i = 0, n = that.AsUnion()->Length(); i < n; ++i) {
552  if (this->Is(that.AsUnion()->Get(i))) return true;
553  if (i > 1 && this->IsRange()) return false; // Shortcut.
554  }
555  return false;
556  }
557 
558  if (that.IsRange()) {
559  return (this->IsRange() && Contains(that.AsRange(), this->AsRange()));
560  }
561  if (this->IsRange()) return false;
562 
563  return this->SimplyEquals(that);
564 }
565 
566 // Check if [this] and [that] overlap.
567 bool Type::Maybe(Type that) const {
568  DisallowHeapAllocation no_allocation;
569 
570  if (BitsetType::IsNone(this->BitsetLub() & that.BitsetLub())) return false;
571 
572  // (T1 \/ ... \/ Tn) overlaps T if (T1 overlaps T) \/ ... \/ (Tn overlaps T)
573  if (this->IsUnion()) {
574  for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
575  if (this->AsUnion()->Get(i).Maybe(that)) return true;
576  }
577  return false;
578  }
579 
580  // T overlaps (T1 \/ ... \/ Tn) if (T overlaps T1) \/ ... \/ (T overlaps Tn)
581  if (that.IsUnion()) {
582  for (int i = 0, n = that.AsUnion()->Length(); i < n; ++i) {
583  if (this->Maybe(that.AsUnion()->Get(i))) return true;
584  }
585  return false;
586  }
587 
588  if (this->IsBitset() && that.IsBitset()) return true;
589 
590  if (this->IsRange()) {
591  if (that.IsRange()) {
592  return Overlap(this->AsRange(), that.AsRange());
593  }
594  if (that.IsBitset()) {
595  bitset number_bits = BitsetType::NumberBits(that.AsBitset());
596  if (number_bits == BitsetType::kNone) {
597  return false;
598  }
599  double min = std::max(BitsetType::Min(number_bits), this->Min());
600  double max = std::min(BitsetType::Max(number_bits), this->Max());
601  return min <= max;
602  }
603  }
604  if (that.IsRange()) {
605  return that.Maybe(*this); // This case is handled above.
606  }
607 
608  if (this->IsBitset() || that.IsBitset()) return true;
609 
610  return this->SimplyEquals(that);
611 }
612 
613 // Return the range in [this], or [nullptr].
614 Type Type::GetRange() const {
615  DisallowHeapAllocation no_allocation;
616  if (this->IsRange()) return *this;
617  if (this->IsUnion() && this->AsUnion()->Get(1).IsRange()) {
618  return this->AsUnion()->Get(1);
619  }
620  return nullptr;
621 }
622 
623 bool UnionType::Wellformed() const {
624  DisallowHeapAllocation no_allocation;
625  // This checks the invariants of the union representation:
626  // 1. There are at least two elements.
627  // 2. The first element is a bitset, no other element is a bitset.
628  // 3. At most one element is a range, and it must be the second one.
629  // 4. No element is itself a union.
630  // 5. No element (except the bitset) is a subtype of any other.
631  // 6. If there is a range, then the bitset type does not contain
632  // plain number bits.
633  DCHECK_LE(2, this->Length()); // (1)
634  DCHECK(this->Get(0).IsBitset()); // (2a)
635 
636  for (int i = 0; i < this->Length(); ++i) {
637  if (i != 0) DCHECK(!this->Get(i).IsBitset()); // (2b)
638  if (i != 1) DCHECK(!this->Get(i).IsRange()); // (3)
639  DCHECK(!this->Get(i).IsUnion()); // (4)
640  for (int j = 0; j < this->Length(); ++j) {
641  if (i != j && i != 0) DCHECK(!this->Get(i).Is(this->Get(j))); // (5)
642  }
643  }
644  DCHECK(!this->Get(1).IsRange() ||
645  (BitsetType::NumberBits(this->Get(0).AsBitset()) ==
646  BitsetType::kNone)); // (6)
647  return true;
648 }
649 
650 // -----------------------------------------------------------------------------
651 // Union and intersection
652 
653 Type Type::Intersect(Type type1, Type type2, Zone* zone) {
654  // Fast case: bit sets.
655  if (type1.IsBitset() && type2.IsBitset()) {
656  return NewBitset(type1.AsBitset() & type2.AsBitset());
657  }
658 
659  // Fast case: top or bottom types.
660  if (type1.IsNone() || type2.IsAny()) return type1; // Shortcut.
661  if (type2.IsNone() || type1.IsAny()) return type2; // Shortcut.
662 
663  // Semi-fast case.
664  if (type1.Is(type2)) return type1;
665  if (type2.Is(type1)) return type2;
666 
667  // Slow case: create union.
668 
669  // Semantic subtyping check - this is needed for consistency with the
670  // semi-fast case above.
671  if (type1.Is(type2)) {
672  type2 = Any();
673  } else if (type2.Is(type1)) {
674  type1 = Any();
675  }
676 
677  bitset bits = type1.BitsetGlb() & type2.BitsetGlb();
678  int size1 = type1.IsUnion() ? type1.AsUnion()->Length() : 1;
679  int size2 = type2.IsUnion() ? type2.AsUnion()->Length() : 1;
680  int size;
681  if (base::bits::SignedAddOverflow32(size1, size2, &size)) return Any();
682  if (base::bits::SignedAddOverflow32(size, 2, &size)) return Any();
683  UnionType* result = UnionType::New(size, zone);
684  size = 0;
685 
686  // Deal with bitsets.
687  result->Set(size++, NewBitset(bits));
688 
689  RangeType::Limits lims = RangeType::Limits::Empty();
690  size = IntersectAux(type1, type2, result, size, &lims, zone);
691 
692  // If the range is not empty, then insert it into the union and
693  // remove the number bits from the bitset.
694  if (!lims.IsEmpty()) {
695  size = UpdateRange(Type::Range(lims, zone), result, size, zone);
696 
697  // Remove the number bits.
698  bitset number_bits = BitsetType::NumberBits(bits);
699  bits &= ~number_bits;
700  result->Set(0, NewBitset(bits));
701  }
702  return NormalizeUnion(result, size, zone);
703 }
704 
705 int Type::UpdateRange(Type range, UnionType* result, int size, Zone* zone) {
706  if (size == 1) {
707  result->Set(size++, range);
708  } else {
709  // Make space for the range.
710  result->Set(size++, result->Get(1));
711  result->Set(1, range);
712  }
713 
714  // Remove any components that just got subsumed.
715  for (int i = 2; i < size;) {
716  if (result->Get(i).Is(range)) {
717  result->Set(i, result->Get(--size));
718  } else {
719  ++i;
720  }
721  }
722  return size;
723 }
724 
725 RangeType::Limits Type::ToLimits(bitset bits, Zone* zone) {
726  bitset number_bits = BitsetType::NumberBits(bits);
727 
728  if (number_bits == BitsetType::kNone) {
729  return RangeType::Limits::Empty();
730  }
731 
732  return RangeType::Limits(BitsetType::Min(number_bits),
733  BitsetType::Max(number_bits));
734 }
735 
736 RangeType::Limits Type::IntersectRangeAndBitset(Type range, Type bitset,
737  Zone* zone) {
738  RangeType::Limits range_lims(range.AsRange());
739  RangeType::Limits bitset_lims = ToLimits(bitset.AsBitset(), zone);
740  return RangeType::Limits::Intersect(range_lims, bitset_lims);
741 }
742 
743 int Type::IntersectAux(Type lhs, Type rhs, UnionType* result, int size,
744  RangeType::Limits* lims, Zone* zone) {
745  if (lhs.IsUnion()) {
746  for (int i = 0, n = lhs.AsUnion()->Length(); i < n; ++i) {
747  size = IntersectAux(lhs.AsUnion()->Get(i), rhs, result, size, lims, zone);
748  }
749  return size;
750  }
751  if (rhs.IsUnion()) {
752  for (int i = 0, n = rhs.AsUnion()->Length(); i < n; ++i) {
753  size = IntersectAux(lhs, rhs.AsUnion()->Get(i), result, size, lims, zone);
754  }
755  return size;
756  }
757 
758  if (BitsetType::IsNone(lhs.BitsetLub() & rhs.BitsetLub())) return size;
759 
760  if (lhs.IsRange()) {
761  if (rhs.IsBitset()) {
762  RangeType::Limits lim = IntersectRangeAndBitset(lhs, rhs, zone);
763 
764  if (!lim.IsEmpty()) {
765  *lims = RangeType::Limits::Union(lim, *lims);
766  }
767  return size;
768  }
769  if (rhs.IsRange()) {
770  RangeType::Limits lim = RangeType::Limits::Intersect(
771  RangeType::Limits(lhs.AsRange()), RangeType::Limits(rhs.AsRange()));
772  if (!lim.IsEmpty()) {
773  *lims = RangeType::Limits::Union(lim, *lims);
774  }
775  }
776  return size;
777  }
778  if (rhs.IsRange()) {
779  // This case is handled symmetrically above.
780  return IntersectAux(rhs, lhs, result, size, lims, zone);
781  }
782  if (lhs.IsBitset() || rhs.IsBitset()) {
783  return AddToUnion(lhs.IsBitset() ? rhs : lhs, result, size, zone);
784  }
785  if (lhs.SimplyEquals(rhs)) {
786  return AddToUnion(lhs, result, size, zone);
787  }
788  return size;
789 }
790 
791 // Make sure that we produce a well-formed range and bitset:
792 // If the range is non-empty, the number bits in the bitset should be
793 // clear. Moreover, if we have a canonical range (such as Signed32),
794 // we want to produce a bitset rather than a range.
795 Type Type::NormalizeRangeAndBitset(Type range, bitset* bits, Zone* zone) {
796  // Fast path: If the bitset does not mention numbers, we can just keep the
797  // range.
798  bitset number_bits = BitsetType::NumberBits(*bits);
799  if (number_bits == 0) {
800  return range;
801  }
802 
803  // If the range is semantically contained within the bitset, return None and
804  // leave the bitset untouched.
805  bitset range_lub = range.BitsetLub();
806  if (BitsetType::Is(range_lub, *bits)) {
807  return None();
808  }
809 
810  // Slow path: reconcile the bitset range and the range.
811  double bitset_min = BitsetType::Min(number_bits);
812  double bitset_max = BitsetType::Max(number_bits);
813 
814  double range_min = range.Min();
815  double range_max = range.Max();
816 
817  // Remove the number bits from the bitset, they would just confuse us now.
818  // NOTE: bits contains OtherNumber iff bits contains PlainNumber, in which
819  // case we already returned after the subtype check above.
820  *bits &= ~number_bits;
821 
822  if (range_min <= bitset_min && range_max >= bitset_max) {
823  // Bitset is contained within the range, just return the range.
824  return range;
825  }
826 
827  if (bitset_min < range_min) {
828  range_min = bitset_min;
829  }
830  if (bitset_max > range_max) {
831  range_max = bitset_max;
832  }
833  return Type::Range(range_min, range_max, zone);
834 }
835 
836 Type Type::NewConstant(double value, Zone* zone) {
837  if (RangeType::IsInteger(value)) {
838  return Range(value, value, zone);
839  } else if (IsMinusZero(value)) {
840  return Type::MinusZero();
841  } else if (std::isnan(value)) {
842  return Type::NaN();
843  }
844 
845  DCHECK(OtherNumberConstantType::IsOtherNumberConstant(value));
846  return OtherNumberConstant(value, zone);
847 }
848 
849 Type Type::NewConstant(JSHeapBroker* broker, Handle<i::Object> value,
850  Zone* zone) {
851  ObjectRef ref(broker, value);
852  if (ref.IsSmi()) {
853  return NewConstant(static_cast<double>(ref.AsSmi()), zone);
854  }
855  if (ref.IsHeapNumber()) {
856  return NewConstant(ref.AsHeapNumber().value(), zone);
857  }
858  if (ref.IsString() && !ref.IsInternalizedString()) {
859  return Type::String();
860  }
861  return HeapConstant(ref.AsHeapObject(), zone);
862 }
863 
864 Type Type::Union(Type type1, Type type2, Zone* zone) {
865  // Fast case: bit sets.
866  if (type1.IsBitset() && type2.IsBitset()) {
867  return NewBitset(type1.AsBitset() | type2.AsBitset());
868  }
869 
870  // Fast case: top or bottom types.
871  if (type1.IsAny() || type2.IsNone()) return type1;
872  if (type2.IsAny() || type1.IsNone()) return type2;
873 
874  // Semi-fast case.
875  if (type1.Is(type2)) return type2;
876  if (type2.Is(type1)) return type1;
877 
878  // Slow case: create union.
879  int size1 = type1.IsUnion() ? type1.AsUnion()->Length() : 1;
880  int size2 = type2.IsUnion() ? type2.AsUnion()->Length() : 1;
881  int size;
882  if (base::bits::SignedAddOverflow32(size1, size2, &size)) return Any();
883  if (base::bits::SignedAddOverflow32(size, 2, &size)) return Any();
884  UnionType* result = UnionType::New(size, zone);
885  size = 0;
886 
887  // Compute the new bitset.
888  bitset new_bitset = type1.BitsetGlb() | type2.BitsetGlb();
889 
890  // Deal with ranges.
891  Type range = None();
892  Type range1 = type1.GetRange();
893  Type range2 = type2.GetRange();
894  if (range1 != nullptr && range2 != nullptr) {
895  RangeType::Limits lims =
896  RangeType::Limits::Union(RangeType::Limits(range1.AsRange()),
897  RangeType::Limits(range2.AsRange()));
898  Type union_range = Type::Range(lims, zone);
899  range = NormalizeRangeAndBitset(union_range, &new_bitset, zone);
900  } else if (range1 != nullptr) {
901  range = NormalizeRangeAndBitset(range1, &new_bitset, zone);
902  } else if (range2 != nullptr) {
903  range = NormalizeRangeAndBitset(range2, &new_bitset, zone);
904  }
905  Type bits = NewBitset(new_bitset);
906  result->Set(size++, bits);
907  if (!range.IsNone()) result->Set(size++, range);
908 
909  size = AddToUnion(type1, result, size, zone);
910  size = AddToUnion(type2, result, size, zone);
911  return NormalizeUnion(result, size, zone);
912 }
913 
914 // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
915 // Return new size of [result].
916 int Type::AddToUnion(Type type, UnionType* result, int size, Zone* zone) {
917  if (type.IsBitset() || type.IsRange()) return size;
918  if (type.IsUnion()) {
919  for (int i = 0, n = type.AsUnion()->Length(); i < n; ++i) {
920  size = AddToUnion(type.AsUnion()->Get(i), result, size, zone);
921  }
922  return size;
923  }
924  for (int i = 0; i < size; ++i) {
925  if (type.Is(result->Get(i))) return size;
926  }
927  result->Set(size++, type);
928  return size;
929 }
930 
931 Type Type::NormalizeUnion(UnionType* unioned, int size, Zone* zone) {
932  DCHECK_LE(1, size);
933  DCHECK(unioned->Get(0).IsBitset());
934  // If the union has just one element, return it.
935  if (size == 1) {
936  return unioned->Get(0);
937  }
938  bitset bits = unioned->Get(0).AsBitset();
939  // If the union only consists of a range, we can get rid of the union.
940  if (size == 2 && bits == BitsetType::kNone) {
941  if (unioned->Get(1).IsRange()) {
942  return Type::Range(unioned->Get(1).AsRange()->Min(),
943  unioned->Get(1).AsRange()->Max(), zone);
944  }
945  }
946  unioned->Shrink(size);
947  SLOW_DCHECK(unioned->Wellformed());
948  return Type(unioned);
949 }
950 
951 int Type::NumConstants() const {
952  DisallowHeapAllocation no_allocation;
953  if (this->IsHeapConstant() || this->IsOtherNumberConstant()) {
954  return 1;
955  } else if (this->IsUnion()) {
956  int result = 0;
957  for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
958  if (this->AsUnion()->Get(i).IsHeapConstant()) ++result;
959  }
960  return result;
961  } else {
962  return 0;
963  }
964 }
965 
966 // -----------------------------------------------------------------------------
967 // Printing.
968 
969 const char* BitsetType::Name(bitset bits) {
970  switch (bits) {
971 #define RETURN_NAMED_TYPE(type, value) \
972  case k##type: \
973  return #type;
974  PROPER_BITSET_TYPE_LIST(RETURN_NAMED_TYPE)
975  INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_TYPE)
976 #undef RETURN_NAMED_TYPE
977 
978  default:
979  return nullptr;
980  }
981 }
982 
983 void BitsetType::Print(std::ostream& os, // NOLINT
984  bitset bits) {
985  DisallowHeapAllocation no_allocation;
986  const char* name = Name(bits);
987  if (name != nullptr) {
988  os << name;
989  return;
990  }
991 
992  // clang-format off
993  static const bitset named_bitsets[] = {
994 #define BITSET_CONSTANT(type, value) k##type,
995  INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
996  PROPER_BITSET_TYPE_LIST(BITSET_CONSTANT)
997 #undef BITSET_CONSTANT
998  };
999  // clang-format on
1000 
1001  bool is_first = true;
1002  os << "(";
1003  for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
1004  bitset subset = named_bitsets[i];
1005  if ((bits & subset) == subset) {
1006  if (!is_first) os << " | ";
1007  is_first = false;
1008  os << Name(subset);
1009  bits -= subset;
1010  }
1011  }
1012  DCHECK_EQ(0, bits);
1013  os << ")";
1014 }
1015 
1016 void Type::PrintTo(std::ostream& os) const {
1017  DisallowHeapAllocation no_allocation;
1018  if (this->IsBitset()) {
1019  BitsetType::Print(os, this->AsBitset());
1020  } else if (this->IsHeapConstant()) {
1021  os << "HeapConstant(" << Brief(*this->AsHeapConstant()->Value()) << ")";
1022  } else if (this->IsOtherNumberConstant()) {
1023  os << "OtherNumberConstant(" << this->AsOtherNumberConstant()->Value()
1024  << ")";
1025  } else if (this->IsRange()) {
1026  std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed);
1027  std::streamsize saved_precision = os.precision(0);
1028  os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max()
1029  << ")";
1030  os.flags(saved_flags);
1031  os.precision(saved_precision);
1032  } else if (this->IsUnion()) {
1033  os << "(";
1034  for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1035  Type type_i = this->AsUnion()->Get(i);
1036  if (i > 0) os << " | ";
1037  os << type_i;
1038  }
1039  os << ")";
1040  } else if (this->IsTuple()) {
1041  os << "<";
1042  for (int i = 0, n = this->AsTuple()->Arity(); i < n; ++i) {
1043  Type type_i = this->AsTuple()->Element(i);
1044  if (i > 0) os << ", ";
1045  os << type_i;
1046  }
1047  os << ">";
1048  } else {
1049  UNREACHABLE();
1050  }
1051 }
1052 
1053 #ifdef DEBUG
1054 void Type::Print() const {
1055  StdoutStream os;
1056  PrintTo(os);
1057  os << std::endl;
1058 }
1059 void BitsetType::Print(bitset bits) {
1060  StdoutStream os;
1061  Print(os, bits);
1062  os << std::endl;
1063 }
1064 #endif
1065 
1066 BitsetType::bitset BitsetType::SignedSmall() {
1067  return SmiValuesAre31Bits() ? kSigned31 : kSigned32;
1068 }
1069 
1070 BitsetType::bitset BitsetType::UnsignedSmall() {
1071  return SmiValuesAre31Bits() ? kUnsigned30 : kUnsigned31;
1072 }
1073 
1074 // static
1075 Type Type::Tuple(Type first, Type second, Type third, Zone* zone) {
1076  TupleType* tuple = TupleType::New(3, zone);
1077  tuple->InitElement(0, first);
1078  tuple->InitElement(1, second);
1079  tuple->InitElement(2, third);
1080  return FromTypeBase(tuple);
1081 }
1082 
1083 // static
1084 Type Type::OtherNumberConstant(double value, Zone* zone) {
1085  return FromTypeBase(OtherNumberConstantType::New(value, zone));
1086 }
1087 
1088 // static
1089 Type Type::HeapConstant(JSHeapBroker* broker, Handle<i::Object> value,
1090  Zone* zone) {
1091  return FromTypeBase(
1092  HeapConstantType::New(HeapObjectRef(broker, value), zone));
1093 }
1094 
1095 // static
1096 Type Type::HeapConstant(const HeapObjectRef& value, Zone* zone) {
1097  return HeapConstantType::New(value, zone);
1098 }
1099 
1100 // static
1101 Type Type::Range(double min, double max, Zone* zone) {
1102  return FromTypeBase(RangeType::New(min, max, zone));
1103 }
1104 
1105 // static
1106 Type Type::Range(RangeType::Limits lims, Zone* zone) {
1107  return FromTypeBase(RangeType::New(lims, zone));
1108 }
1109 
1110 // static
1111 Type Type::Union(int length, Zone* zone) {
1112  return FromTypeBase(UnionType::New(length, zone));
1113 }
1114 
1115 const HeapConstantType* Type::AsHeapConstant() const {
1116  DCHECK(IsKind(TypeBase::kHeapConstant));
1117  return static_cast<const HeapConstantType*>(ToTypeBase());
1118 }
1119 
1120 const OtherNumberConstantType* Type::AsOtherNumberConstant() const {
1121  DCHECK(IsKind(TypeBase::kOtherNumberConstant));
1122  return static_cast<const OtherNumberConstantType*>(ToTypeBase());
1123 }
1124 
1125 const RangeType* Type::AsRange() const {
1126  DCHECK(IsKind(TypeBase::kRange));
1127  return static_cast<const RangeType*>(ToTypeBase());
1128 }
1129 
1130 const TupleType* Type::AsTuple() const {
1131  DCHECK(IsKind(TypeBase::kTuple));
1132  return static_cast<const TupleType*>(ToTypeBase());
1133 }
1134 
1135 const UnionType* Type::AsUnion() const {
1136  DCHECK(IsKind(TypeBase::kUnion));
1137  return static_cast<const UnionType*>(ToTypeBase());
1138 }
1139 
1140 std::ostream& operator<<(std::ostream& os, Type type) {
1141  type.PrintTo(os);
1142  return os;
1143 }
1144 
1145 } // namespace compiler
1146 } // namespace internal
1147 } // namespace v8
Definition: libplatform.h:13
Definition: v8.h:3134