types.cc 31.5 KB
Newer Older
1 2 3
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/types.h"
6

7
#include "src/ostreams.h"
8
#include "src/types-inl.h"
9 10 11 12

namespace v8 {
namespace internal {

13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

// -----------------------------------------------------------------------------
// Range-related custom order on doubles.
// We want -0 to be less than +0.

static bool dle(double x, double y) {
  return x <= y && (x != 0 || IsMinusZero(x) || !IsMinusZero(y));
}


static bool deq(double x, double y) {
  return dle(x, y) && dle(y, x);
}


28 29
// -----------------------------------------------------------------------------
// Glb and lub computation.
30

31
// The largest bitset subsumed by this type.
32
template<class Config>
33
int TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
34
  DisallowHeapAllocation no_allocation;
35 36 37 38
  if (type->IsBitset()) {
    return type->AsBitset();
  } else if (type->IsUnion()) {
    UnionHandle unioned = handle(type->AsUnion());
39 40
    DCHECK(unioned->Wellformed());
    return unioned->Get(0)->BitsetGlb();  // Other BitsetGlb's are kNone anyway.
41
  } else {
42
    return kNone;
43 44 45 46
  }
}


47
// The smallest bitset subsuming this type.
48
template<class Config>
49
int TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
50 51 52 53
  DisallowHeapAllocation no_allocation;
  if (type->IsBitset()) {
    return type->AsBitset();
  } else if (type->IsUnion()) {
54 55 56 57 58 59 60 61 62 63 64 65
    UnionHandle unioned = handle(type->AsUnion());
    int bitset = kNone;
    for (int i = 0; i < unioned->Length(); ++i) {
      bitset |= unioned->Get(i)->BitsetLub();
    }
    return bitset;
  } else if (type->IsClass()) {
    // Little hack to avoid the need for a region for handlification here...
    return Config::is_class(type) ? Lub(*Config::as_class(type)) :
        type->AsClass()->Bound(NULL)->AsBitset();
  } else if (type->IsConstant()) {
    return type->AsConstant()->Bound()->AsBitset();
66 67
  } else if (type->IsRange()) {
    return type->AsRange()->Bound()->AsBitset();
68 69 70 71 72 73
  } else if (type->IsContext()) {
    return type->AsContext()->Bound()->AsBitset();
  } else if (type->IsArray()) {
    return type->AsArray()->Bound()->AsBitset();
  } else if (type->IsFunction()) {
    return type->AsFunction()->Bound()->AsBitset();
74
  } else {
75
    UNREACHABLE();
76 77 78 79 80
    return kNone;
  }
}


81
// The smallest bitset subsuming this type, ignoring explicit bounds.
82
template<class Config>
83
int TypeImpl<Config>::BitsetType::InherentLub(TypeImpl* type) {
84 85 86 87 88
  DisallowHeapAllocation no_allocation;
  if (type->IsBitset()) {
    return type->AsBitset();
  } else if (type->IsUnion()) {
    UnionHandle unioned = handle(type->AsUnion());
89
    int bitset = kNone;
90
    for (int i = 0; i < unioned->Length(); ++i) {
91
      bitset |= unioned->Get(i)->InherentBitsetLub();
92 93
    }
    return bitset;
94
  } else if (type->IsClass()) {
95
    return Lub(*type->AsClass()->Map());
96
  } else if (type->IsConstant()) {
97
    return Lub(*type->AsConstant()->Value());
98 99
  } else if (type->IsRange()) {
    return Lub(type->AsRange()->Min(), type->AsRange()->Max());
100 101
  } else if (type->IsContext()) {
    return kInternal & kTaggedPtr;
102 103 104 105
  } else if (type->IsArray()) {
    return kArray;
  } else if (type->IsFunction()) {
    return kFunction;
106
  } else {
107 108
    UNREACHABLE();
    return kNone;
109 110 111 112
  }
}


113
template<class Config>
114 115
int TypeImpl<Config>::BitsetType::Lub(i::Object* value) {
  DisallowHeapAllocation no_allocation;
116 117 118 119 120 121 122 123 124 125 126 127
  if (value->IsNumber()) {
    return Lub(value->Number()) & (value->IsSmi() ? kTaggedInt : kTaggedPtr);
  }
  return Lub(i::HeapObject::cast(value)->map());
}


template<class Config>
int TypeImpl<Config>::BitsetType::Lub(double value) {
  DisallowHeapAllocation no_allocation;
  if (i::IsMinusZero(value)) return kMinusZero;
  if (std::isnan(value)) return kNaN;
128 129 130 131 132 133
  if (IsUint32Double(value)) return Lub(FastD2UI(value));
  if (IsInt32Double(value)) return Lub(FastD2I(value));
  return kOtherNumber;
}


134 135 136 137 138 139 140 141 142 143 144 145
template<class Config>
int TypeImpl<Config>::BitsetType::Lub(double min, double max) {
  DisallowHeapAllocation no_allocation;
  DCHECK(dle(min, max));
  if (deq(min, max)) return BitsetType::Lub(min);  // Singleton range.
  int bitset = BitsetType::kNumber ^ SEMANTIC(BitsetType::kNaN);
  if (dle(0, min) || max < 0) bitset ^= SEMANTIC(BitsetType::kMinusZero);
  return bitset;
  // TODO(neis): Could refine this further by doing more checks on min/max.
}


146 147 148 149
template<class Config>
int TypeImpl<Config>::BitsetType::Lub(int32_t value) {
  if (value >= 0x40000000) {
    return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
150
  }
151 152 153 154 155 156 157 158 159 160 161 162
  if (value >= 0) return kUnsignedSmall;
  if (value >= -0x40000000) return kOtherSignedSmall;
  return i::SmiValuesAre31Bits() ? kOtherSigned32 : kOtherSignedSmall;
}


template<class Config>
int TypeImpl<Config>::BitsetType::Lub(uint32_t value) {
  DisallowHeapAllocation no_allocation;
  if (value >= 0x80000000u) return kOtherUnsigned32;
  if (value >= 0x40000000u) {
    return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
163
  }
164
  return kUnsignedSmall;
165 166 167
}


168
template<class Config>
169 170
int TypeImpl<Config>::BitsetType::Lub(i::Map* map) {
  DisallowHeapAllocation no_allocation;
171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194
  switch (map->instance_type()) {
    case STRING_TYPE:
    case ASCII_STRING_TYPE:
    case CONS_STRING_TYPE:
    case CONS_ASCII_STRING_TYPE:
    case SLICED_STRING_TYPE:
    case SLICED_ASCII_STRING_TYPE:
    case EXTERNAL_STRING_TYPE:
    case EXTERNAL_ASCII_STRING_TYPE:
    case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
    case SHORT_EXTERNAL_STRING_TYPE:
    case SHORT_EXTERNAL_ASCII_STRING_TYPE:
    case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
    case INTERNALIZED_STRING_TYPE:
    case ASCII_INTERNALIZED_STRING_TYPE:
    case EXTERNAL_INTERNALIZED_STRING_TYPE:
    case EXTERNAL_ASCII_INTERNALIZED_STRING_TYPE:
    case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
    case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE:
    case SHORT_EXTERNAL_ASCII_INTERNALIZED_STRING_TYPE:
    case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
      return kString;
    case SYMBOL_TYPE:
      return kSymbol;
195 196 197 198 199
    case ODDBALL_TYPE: {
      Heap* heap = map->GetHeap();
      if (map == heap->undefined_map()) return kUndefined;
      if (map == heap->null_map()) return kNull;
      if (map == heap->boolean_map()) return kBoolean;
200
      DCHECK(map == heap->the_hole_map() ||
201
             map == heap->uninitialized_map() ||
202
             map == heap->no_interceptor_result_sentinel_map() ||
203 204 205 206
             map == heap->termination_exception_map() ||
             map == heap->arguments_marker_map());
      return kInternal & kTaggedPtr;
    }
207
    case HEAP_NUMBER_TYPE:
208
      return kNumber & kTaggedPtr;
209 210 211 212 213 214 215 216 217 218 219 220 221 222
    case JS_VALUE_TYPE:
    case JS_DATE_TYPE:
    case JS_OBJECT_TYPE:
    case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
    case JS_GENERATOR_OBJECT_TYPE:
    case JS_MODULE_TYPE:
    case JS_GLOBAL_OBJECT_TYPE:
    case JS_BUILTINS_OBJECT_TYPE:
    case JS_GLOBAL_PROXY_TYPE:
    case JS_ARRAY_BUFFER_TYPE:
    case JS_TYPED_ARRAY_TYPE:
    case JS_DATA_VIEW_TYPE:
    case JS_SET_TYPE:
    case JS_MAP_TYPE:
223 224
    case JS_SET_ITERATOR_TYPE:
    case JS_MAP_ITERATOR_TYPE:
225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250
    case JS_WEAK_MAP_TYPE:
    case JS_WEAK_SET_TYPE:
      if (map->is_undetectable()) return kUndetectable;
      return kOtherObject;
    case JS_ARRAY_TYPE:
      return kArray;
    case JS_FUNCTION_TYPE:
      return kFunction;
    case JS_REGEXP_TYPE:
      return kRegExp;
    case JS_PROXY_TYPE:
    case JS_FUNCTION_PROXY_TYPE:
      return kProxy;
    case MAP_TYPE:
      // When compiling stub templates, the meta map is used as a place holder
      // for the actual map with which the template is later instantiated.
      // We treat it as a kind of type variable whose upper bound is Any.
      // TODO(rossberg): for caching of CompareNilIC stubs to work correctly,
      // we must exclude Undetectable here. This makes no sense, really,
      // because it means that the template isn't actually parametric.
      // Also, it doesn't apply elsewhere. 8-(
      // We ought to find a cleaner solution for compiling stubs parameterised
      // over type or class variables, esp ones with bounds...
      return kDetectable;
    case DECLARED_ACCESSOR_INFO_TYPE:
    case EXECUTABLE_ACCESSOR_INFO_TYPE:
251
    case SHARED_FUNCTION_INFO_TYPE:
252 253
    case ACCESSOR_PAIR_TYPE:
    case FIXED_ARRAY_TYPE:
254
    case FOREIGN_TYPE:
255
    case CODE_TYPE:
256
      return kInternal & kTaggedPtr;
257 258 259
    default:
      UNREACHABLE();
      return kNone;
260 261 262 263
  }
}


264 265
// -----------------------------------------------------------------------------
// Predicates.
266

267
// Check this <= that.
268 269
template<class Config>
bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
270 271
  DisallowHeapAllocation no_allocation;

272
  // Fast path for bitsets.
273 274
  if (this->IsNone()) return true;
  if (that->IsBitset()) {
275
    return BitsetType::Is(BitsetType::Lub(this), that->AsBitset());
276 277
  }

278
  if (that->IsClass()) {
279
    return this->IsClass()
280 281 282 283
        && *this->AsClass()->Map() == *that->AsClass()->Map()
        && ((Config::is_class(that) && Config::is_class(this)) ||
            BitsetType::New(this->BitsetLub())->Is(
                BitsetType::New(that->BitsetLub())));
284
  }
285
  if (that->IsConstant()) {
286
    return this->IsConstant()
287 288
        && *this->AsConstant()->Value() == *that->AsConstant()->Value()
        && this->AsConstant()->Bound()->Is(that->AsConstant()->Bound());
289
  }
290 291 292 293 294 295
  if (that->IsRange()) {
    return this->IsRange()
        && this->AsRange()->Bound()->Is(that->AsRange()->Bound())
        && dle(that->AsRange()->Min(), this->AsRange()->Min())
        && dle(this->AsRange()->Max(), that->AsRange()->Max());
  }
296 297 298 299
  if (that->IsContext()) {
    return this->IsContext()
        && this->AsContext()->Outer()->Equals(that->AsContext()->Outer());
  }
300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318
  if (that->IsArray()) {
    return this->IsArray()
        && this->AsArray()->Element()->Equals(that->AsArray()->Element());
  }
  if (that->IsFunction()) {
    // We currently do not allow for any variance here, in order to keep
    // Union and Intersect operations simple.
    if (!this->IsFunction()) return false;
    FunctionType* this_fun = this->AsFunction();
    FunctionType* that_fun = that->AsFunction();
    if (this_fun->Arity() != that_fun->Arity() ||
        !this_fun->Result()->Equals(that_fun->Result()) ||
        !that_fun->Receiver()->Equals(this_fun->Receiver())) {
      return false;
    }
    for (int i = 0; i < this_fun->Arity(); ++i) {
      if (!that_fun->Parameter(i)->Equals(this_fun->Parameter(i))) return false;
    }
    return true;
319 320 321
  }

  // (T1 \/ ... \/ Tn) <= T  <=>  (T1 <= T) /\ ... /\ (Tn <= T)
322
  if (this->IsUnion()) {
323 324 325
    UnionHandle unioned = handle(this->AsUnion());
    for (int i = 0; i < unioned->Length(); ++i) {
      if (!unioned->Get(i)->Is(that)) return false;
326 327 328 329 330 331
    }
    return true;
  }

  // T <= (T1 \/ ... \/ Tn)  <=>  (T <= T1) \/ ... \/ (T <= Tn)
  // (iff T is not a union)
332
  DCHECK(!this->IsUnion() && that->IsUnion());
333 334 335 336
  UnionHandle unioned = handle(that->AsUnion());
  for (int i = 0; i < unioned->Length(); ++i) {
    if (this->Is(unioned->Get(i))) return true;
    if (this->IsBitset()) break;  // Fast fail, only first field is a bitset.
337 338 339 340 341
  }
  return false;
}


342
template<class Config>
343
bool TypeImpl<Config>::NowIs(TypeImpl* that) {
344 345
  DisallowHeapAllocation no_allocation;

346 347 348
  // TODO(rossberg): this is incorrect for
  //   Union(Constant(V), T)->NowIs(Class(M))
  // but fuzzing does not cover that!
349
  if (this->IsConstant()) {
350
    i::Object* object = *this->AsConstant()->Value();
351 352 353 354 355
    if (object->IsHeapObject()) {
      i::Map* map = i::HeapObject::cast(object)->map();
      for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) {
        if (*it.Current() == map) return true;
      }
356 357
    }
  }
358
  return this->Is(that);
359 360 361
}


362 363 364 365 366 367 368 369 370 371 372
// Check if this contains only (currently) stable classes.
template<class Config>
bool TypeImpl<Config>::NowStable() {
  DisallowHeapAllocation no_allocation;
  for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) {
    if (!it.Current()->is_stable()) return false;
  }
  return true;
}


373
// Check this overlaps that.
374 375
template<class Config>
bool TypeImpl<Config>::Maybe(TypeImpl* that) {
376 377
  DisallowHeapAllocation no_allocation;

378
  // (T1 \/ ... \/ Tn) overlaps T <=> (T1 overlaps T) \/ ... \/ (Tn overlaps T)
379
  if (this->IsUnion()) {
380 381 382
    UnionHandle unioned = handle(this->AsUnion());
    for (int i = 0; i < unioned->Length(); ++i) {
      if (unioned->Get(i)->Maybe(that)) return true;
383 384 385 386 387
    }
    return false;
  }

  // T overlaps (T1 \/ ... \/ Tn) <=> (T overlaps T1) \/ ... \/ (T overlaps Tn)
388
  if (that->IsUnion()) {
389 390 391
    UnionHandle unioned = handle(that->AsUnion());
    for (int i = 0; i < unioned->Length(); ++i) {
      if (this->Maybe(unioned->Get(i))) return true;
392 393 394 395
    }
    return false;
  }

396
  DCHECK(!this->IsUnion() && !that->IsUnion());
397 398
  if (this->IsBitset() || that->IsBitset()) {
    return BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub());
399
  }
400
  if (this->IsClass()) {
401 402
    return that->IsClass()
        && *this->AsClass()->Map() == *that->AsClass()->Map();
403
  }
404
  if (this->IsConstant()) {
405 406 407
    return that->IsConstant()
        && *this->AsConstant()->Value() == *that->AsConstant()->Value();
  }
408 409 410
  if (this->IsContext()) {
    return this->Equals(that);
  }
411 412 413 414 415 416 417
  if (this->IsArray()) {
    // There is no variance!
    return this->Equals(that);
  }
  if (this->IsFunction()) {
    // There is no variance!
    return this->Equals(that);
418 419
  }

420 421 422 423
  return false;
}


424
// Check if value is contained in (inhabits) type.
425 426
template<class Config>
bool TypeImpl<Config>::Contains(i::Object* value) {
427
  DisallowHeapAllocation no_allocation;
428 429 430 431 432 433
  if (this->IsRange()) {
    return value->IsNumber() &&
           dle(this->AsRange()->Min(), value->Number()) &&
           dle(value->Number(), this->AsRange()->Max()) &&
           BitsetType::Is(BitsetType::Lub(value), this->BitsetLub());
  }
434 435
  for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
    if (*it.Current() == value) return true;
436
  }
437
  return BitsetType::New(BitsetType::Lub(value))->Is(this);
438 439 440
}


441
template<class Config>
442
bool TypeImpl<Config>::UnionType::Wellformed() {
443
  DCHECK(this->Length() >= 2);
444
  for (int i = 0; i < this->Length(); ++i) {
445 446
    DCHECK(!this->Get(i)->IsUnion());
    if (i > 0) DCHECK(!this->Get(i)->IsBitset());
447
    for (int j = 0; j < this->Length(); ++j) {
448
      if (i != j) DCHECK(!this->Get(i)->Is(this->Get(j)));
449 450 451 452 453 454 455 456 457 458
    }
  }
  return true;
}


// -----------------------------------------------------------------------------
// Union and intersection

template<class Config>
459
typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Rebound(
460 461 462 463 464 465
    int bitset, Region* region) {
  TypeHandle bound = BitsetType::New(bitset, region);
  if (this->IsClass()) {
    return ClassType::New(this->AsClass()->Map(), bound, region);
  } else if (this->IsConstant()) {
    return ConstantType::New(this->AsConstant()->Value(), bound, region);
466 467 468
  } else if (this->IsRange()) {
    return RangeType::New(
        this->AsRange()->Min(), this->AsRange()->Max(), bound, region);
469 470 471 472 473
  } else if (this->IsContext()) {
    return ContextType::New(this->AsContext()->Outer(), bound, region);
  } else if (this->IsArray()) {
    return ArrayType::New(this->AsArray()->Element(), bound, region);
  } else if (this->IsFunction()) {
474
    FunctionHandle function = Config::handle(this->AsFunction());
475 476 477 478 479 480 481 482 483 484 485 486 487 488 489
    int arity = function->Arity();
    FunctionHandle type = FunctionType::New(
        function->Result(), function->Receiver(), bound, arity, region);
    for (int i = 0; i < arity; ++i) {
      type->InitParameter(i, function->Parameter(i));
    }
    return type;
  }
  UNREACHABLE();
  return TypeHandle();
}


template<class Config>
int TypeImpl<Config>::BoundBy(TypeImpl* that) {
490
  DCHECK(!this->IsUnion());
491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518
  if (that->IsUnion()) {
    UnionType* unioned = that->AsUnion();
    int length = unioned->Length();
    int bitset = BitsetType::kNone;
    for (int i = 0; i < length; ++i) {
      bitset |= BoundBy(unioned->Get(i)->unhandle());
    }
    return bitset;
  } else if (that->IsClass() && this->IsClass() &&
      *this->AsClass()->Map() == *that->AsClass()->Map()) {
    return that->BitsetLub();
  } else if (that->IsConstant() && this->IsConstant() &&
      *this->AsConstant()->Value() == *that->AsConstant()->Value()) {
    return that->AsConstant()->Bound()->AsBitset();
  } else if (that->IsContext() && this->IsContext() && this->Is(that)) {
    return that->AsContext()->Bound()->AsBitset();
  } else if (that->IsArray() && this->IsArray() && this->Is(that)) {
    return that->AsArray()->Bound()->AsBitset();
  } else if (that->IsFunction() && this->IsFunction() && this->Is(that)) {
    return that->AsFunction()->Bound()->AsBitset();
  }
  return that->BitsetGlb();
}


template<class Config>
int TypeImpl<Config>::IndexInUnion(
    int bound, UnionHandle unioned, int current_size) {
519
  DCHECK(!this->IsUnion());
520
  for (int i = 0; i < current_size; ++i) {
521 522
    TypeHandle that = unioned->Get(i);
    if (that->IsBitset()) {
523
      if (BitsetType::Is(bound, that->AsBitset())) return i;
524 525 526 527 528 529 530 531 532 533 534 535
    } else if (that->IsClass() && this->IsClass()) {
      if (*this->AsClass()->Map() == *that->AsClass()->Map()) return i;
    } else if (that->IsConstant() && this->IsConstant()) {
      if (*this->AsConstant()->Value() == *that->AsConstant()->Value())
        return i;
    } else if (that->IsContext() && this->IsContext()) {
      if (this->Is(that)) return i;
    } else if (that->IsArray() && this->IsArray()) {
      if (this->Is(that)) return i;
    } else if (that->IsFunction() && this->IsFunction()) {
      if (this->Is(that)) return i;
    }
536
  }
537
  return -1;
538 539
}

540

541 542
// Get non-bitsets from type, bounded by upper.
// Store at result starting at index. Returns updated index.
543
template<class Config>
544
int TypeImpl<Config>::ExtendUnion(
545 546
    UnionHandle result, int size, TypeHandle type,
    TypeHandle other, bool is_intersect, Region* region) {
547 548 549
  if (type->IsUnion()) {
    UnionHandle unioned = handle(type->AsUnion());
    for (int i = 0; i < unioned->Length(); ++i) {
550
      TypeHandle type_i = unioned->Get(i);
551
      DCHECK(i == 0 || !(type_i->IsBitset() || type_i->Is(unioned->Get(0))));
552 553
      if (!type_i->IsBitset()) {
        size = ExtendUnion(result, size, type_i, other, is_intersect, region);
554
      }
555
    }
556
  } else if (!type->IsBitset()) {
557 558
    DCHECK(type->IsClass() || type->IsConstant() || type->IsRange() ||
           type->IsContext() || type->IsArray() || type->IsFunction());
559 560 561 562 563 564
    int inherent_bound = type->InherentBitsetLub();
    int old_bound = type->BitsetLub();
    int other_bound = type->BoundBy(other->unhandle()) & inherent_bound;
    int new_bound =
        is_intersect ? (old_bound & other_bound) : (old_bound | other_bound);
    if (new_bound != BitsetType::kNone) {
565
      int i = type->IndexInUnion(new_bound, result, size);
566 567 568 569 570 571 572 573 574
      if (i == -1) {
        i = size++;
      } else if (result->Get(i)->IsBitset()) {
        return size;  // Already fully subsumed.
      } else {
        int type_i_bound = result->Get(i)->BitsetLub();
        new_bound |= type_i_bound;
        if (new_bound == type_i_bound) return size;
      }
575
      if (new_bound != old_bound) type = type->Rebound(new_bound, region);
576
      result->Set(i, type);
577
    }
578
  }
579
  return size;
580 581 582
}


583
// Union is O(1) on simple bitsets, but O(n*m) on structured unions.
584 585 586
template<class Config>
typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
    TypeHandle type1, TypeHandle type2, Region* region) {
587
  // Fast case: bit sets.
588
  if (type1->IsBitset() && type2->IsBitset()) {
589
    return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region);
590 591
  }

592
  // Fast case: top or bottom types.
593 594
  if (type1->IsAny() || type2->IsNone()) return type1;
  if (type2->IsAny() || type1->IsNone()) return type2;
595

596
  // Semi-fast case: Unioned objects are neither involved nor produced.
597 598 599
  if (!(type1->IsUnion() || type2->IsUnion())) {
    if (type1->Is(type2)) return type2;
    if (type2->Is(type1)) return type1;
600 601 602
  }

  // Slow case: may need to produce a Unioned object.
603
  int size = 0;
604
  if (!type1->IsBitset()) {
605
    size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1);
606
  }
607
  if (!type2->IsBitset()) {
608
    size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1);
609
  }
610 611
  int bitset = type1->BitsetGlb() | type2->BitsetGlb();
  if (bitset != BitsetType::kNone) ++size;
612
  DCHECK(size >= 1);
613

614
  UnionHandle unioned = UnionType::New(size, region);
615
  size = 0;
616 617
  if (bitset != BitsetType::kNone) {
    unioned->Set(size++, BitsetType::New(bitset, region));
618
  }
619 620
  size = ExtendUnion(unioned, size, type1, type2, false, region);
  size = ExtendUnion(unioned, size, type2, type1, false, region);
621 622

  if (size == 1) {
623
    return unioned->Get(0);
624
  } else {
625
    unioned->Shrink(size);
626
    DCHECK(unioned->Wellformed());
627
    return unioned;
628 629 630 631
  }
}


632
// Intersection is O(1) on simple bitsets, but O(n*m) on structured unions.
633 634 635
template<class Config>
typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
    TypeHandle type1, TypeHandle type2, Region* region) {
636
  // Fast case: bit sets.
637
  if (type1->IsBitset() && type2->IsBitset()) {
638
    return BitsetType::New(type1->AsBitset() & type2->AsBitset(), region);
639 640
  }

641
  // Fast case: top or bottom types.
642 643
  if (type1->IsNone() || type2->IsAny()) return type1;
  if (type2->IsNone() || type1->IsAny()) return type2;
644

645
  // Semi-fast case: Unioned objects are neither involved nor produced.
646 647 648
  if (!(type1->IsUnion() || type2->IsUnion())) {
    if (type1->Is(type2)) return type1;
    if (type2->Is(type1)) return type2;
649 650 651
  }

  // Slow case: may need to produce a Unioned object.
652
  int size = 0;
653
  if (!type1->IsBitset()) {
654
    size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1);
655
  }
656
  if (!type2->IsBitset()) {
657
    size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1);
658
  }
659 660
  int bitset = type1->BitsetGlb() & type2->BitsetGlb();
  if (bitset != BitsetType::kNone) ++size;
661
  DCHECK(size >= 1);
662

663
  UnionHandle unioned = UnionType::New(size, region);
664
  size = 0;
665 666
  if (bitset != BitsetType::kNone) {
    unioned->Set(size++, BitsetType::New(bitset, region));
667
  }
668 669
  size = ExtendUnion(unioned, size, type1, type2, true, region);
  size = ExtendUnion(unioned, size, type2, type1, true, region);
670 671

  if (size == 0) {
672
    return None(region);
673
  } else if (size == 1) {
674
    return unioned->Get(0);
675
  } else {
676
    unioned->Shrink(size);
677
    DCHECK(unioned->Wellformed());
678
    return unioned;
679
  }
680 681
}

682

683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724
// -----------------------------------------------------------------------------
// Iteration.

template<class Config>
int TypeImpl<Config>::NumClasses() {
  DisallowHeapAllocation no_allocation;
  if (this->IsClass()) {
    return 1;
  } else if (this->IsUnion()) {
    UnionHandle unioned = handle(this->AsUnion());
    int result = 0;
    for (int i = 0; i < unioned->Length(); ++i) {
      if (unioned->Get(i)->IsClass()) ++result;
    }
    return result;
  } else {
    return 0;
  }
}


template<class Config>
int TypeImpl<Config>::NumConstants() {
  DisallowHeapAllocation no_allocation;
  if (this->IsConstant()) {
    return 1;
  } else if (this->IsUnion()) {
    UnionHandle unioned = handle(this->AsUnion());
    int result = 0;
    for (int i = 0; i < unioned->Length(); ++i) {
      if (unioned->Get(i)->IsConstant()) ++result;
    }
    return result;
  } else {
    return 0;
  }
}


template<class Config> template<class T>
typename TypeImpl<Config>::TypeHandle
TypeImpl<Config>::Iterator<T>::get_type() {
725
  DCHECK(!Done());
726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788
  return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_;
}


// C++ cannot specialise nested templates, so we have to go through this
// contortion with an auxiliary template to simulate it.
template<class Config, class T>
struct TypeImplIteratorAux {
  static bool matches(typename TypeImpl<Config>::TypeHandle type);
  static i::Handle<T> current(typename TypeImpl<Config>::TypeHandle type);
};

template<class Config>
struct TypeImplIteratorAux<Config, i::Map> {
  static bool matches(typename TypeImpl<Config>::TypeHandle type) {
    return type->IsClass();
  }
  static i::Handle<i::Map> current(typename TypeImpl<Config>::TypeHandle type) {
    return type->AsClass()->Map();
  }
};

template<class Config>
struct TypeImplIteratorAux<Config, i::Object> {
  static bool matches(typename TypeImpl<Config>::TypeHandle type) {
    return type->IsConstant();
  }
  static i::Handle<i::Object> current(
      typename TypeImpl<Config>::TypeHandle type) {
    return type->AsConstant()->Value();
  }
};

template<class Config> template<class T>
bool TypeImpl<Config>::Iterator<T>::matches(TypeHandle type) {
  return TypeImplIteratorAux<Config, T>::matches(type);
}

template<class Config> template<class T>
i::Handle<T> TypeImpl<Config>::Iterator<T>::Current() {
  return TypeImplIteratorAux<Config, T>::current(get_type());
}


template<class Config> template<class T>
void TypeImpl<Config>::Iterator<T>::Advance() {
  DisallowHeapAllocation no_allocation;
  ++index_;
  if (type_->IsUnion()) {
    UnionHandle unioned = handle(type_->AsUnion());
    for (; index_ < unioned->Length(); ++index_) {
      if (matches(unioned->Get(index_))) return;
    }
  } else if (index_ == 0 && matches(type_)) {
    return;
  }
  index_ = -1;
}


// -----------------------------------------------------------------------------
// Conversion between low-level representations.

789 790 791 792 793
template<class Config>
template<class OtherType>
typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
    typename OtherType::TypeHandle type, Region* region) {
  if (type->IsBitset()) {
794
    return BitsetType::New(type->AsBitset(), region);
795
  } else if (type->IsClass()) {
796 797
    TypeHandle bound = BitsetType::New(type->BitsetLub(), region);
    return ClassType::New(type->AsClass()->Map(), bound, region);
798
  } else if (type->IsConstant()) {
799 800
    TypeHandle bound = Convert<OtherType>(type->AsConstant()->Bound(), region);
    return ConstantType::New(type->AsConstant()->Value(), bound, region);
801 802 803 804
  } else if (type->IsRange()) {
    TypeHandle bound = Convert<OtherType>(type->AsRange()->Bound(), region);
    return RangeType::New(
        type->AsRange()->Min(), type->AsRange()->Max(), bound, region);
805
  } else if (type->IsContext()) {
806
    TypeHandle bound = Convert<OtherType>(type->AsContext()->Bound(), region);
807
    TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region);
808
    return ContextType::New(outer, bound, region);
809 810 811
  } else if (type->IsUnion()) {
    int length = type->AsUnion()->Length();
    UnionHandle unioned = UnionType::New(length, region);
812
    for (int i = 0; i < length; ++i) {
813 814
      TypeHandle t = Convert<OtherType>(type->AsUnion()->Get(i), region);
      unioned->Set(i, t);
815 816 817
    }
    return unioned;
  } else if (type->IsArray()) {
818 819 820
    TypeHandle element = Convert<OtherType>(type->AsArray()->Element(), region);
    TypeHandle bound = Convert<OtherType>(type->AsArray()->Bound(), region);
    return ArrayType::New(element, bound, region);
821
  } else if (type->IsFunction()) {
822 823 824
    TypeHandle res = Convert<OtherType>(type->AsFunction()->Result(), region);
    TypeHandle rcv = Convert<OtherType>(type->AsFunction()->Receiver(), region);
    TypeHandle bound = Convert<OtherType>(type->AsFunction()->Bound(), region);
825
    FunctionHandle function = FunctionType::New(
826
        res, rcv, bound, type->AsFunction()->Arity(), region);
827
    for (int i = 0; i < function->Arity(); ++i) {
828 829 830
      TypeHandle param = Convert<OtherType>(
          type->AsFunction()->Parameter(i), region);
      function->InitParameter(i, param);
831
    }
832 833 834 835
    return function;
  } else {
    UNREACHABLE();
    return None(region);
836 837 838 839
  }
}


840 841
// -----------------------------------------------------------------------------
// Printing.
842

843
template<class Config>
844
const char* TypeImpl<Config>::BitsetType::Name(int bitset) {
845
  switch (bitset) {
846 847 848 849 850
    case REPRESENTATION(kAny): return "Any";
    #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \
    case REPRESENTATION(k##type): return #type;
    REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE)
    #undef RETURN_NAMED_REPRESENTATION_TYPE
851

852 853 854 855
    #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \
    case SEMANTIC(k##type): return #type;
    SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
    #undef RETURN_NAMED_SEMANTIC_TYPE
856

857 858 859 860 861 862
    default:
      return NULL;
  }
}


863 864 865
template <class Config>
void TypeImpl<Config>::BitsetType::Print(OStream& os,  // NOLINT
                                         int bitset) {
866 867
  DisallowHeapAllocation no_allocation;
  const char* name = Name(bitset);
868
  if (name != NULL) {
869 870 871 872 873 874
    os << name;
    return;
  }

  static const int named_bitsets[] = {
#define BITSET_CONSTANT(type, value) REPRESENTATION(k##type),
875
      REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
876
#undef BITSET_CONSTANT
877

878
#define BITSET_CONSTANT(type, value) SEMANTIC(k##type),
879
      SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
880 881 882 883 884
#undef BITSET_CONSTANT
  };

  bool is_first = true;
  os << "(";
885
  for (int i(arraysize(named_bitsets) - 1); bitset != 0 && i >= 0; --i) {
886 887 888 889 890 891
    int subset = named_bitsets[i];
    if ((bitset & subset) == subset) {
      if (!is_first) os << " | ";
      is_first = false;
      os << Name(subset);
      bitset -= subset;
892 893
    }
  }
894
  DCHECK(bitset == 0);
895
  os << ")";
896 897 898
}


899 900
template <class Config>
void TypeImpl<Config>::PrintTo(OStream& os, PrintDimension dim) {  // NOLINT
901
  DisallowHeapAllocation no_allocation;
902 903
  if (dim != REPRESENTATION_DIM) {
    if (this->IsBitset()) {
904
      BitsetType::Print(os, SEMANTIC(this->AsBitset()));
905
    } else if (this->IsClass()) {
906
      os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < ";
907
      BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim);
908
      os << ")";
909
    } else if (this->IsConstant()) {
910 911 912 913
      os << "Constant(" << static_cast<void*>(*this->AsConstant()->Value())
         << " : ";
      BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim);
      os << ")";
914 915 916 917 918
    } else if (this->IsRange()) {
      os << "Range(" << this->AsRange()->Min()
         << ".." << this->AsRange()->Max() << " : ";
      BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim);
      os << ")";
919
    } else if (this->IsContext()) {
920 921 922
      os << "Context(";
      this->AsContext()->Outer()->PrintTo(os, dim);
      os << ")";
923
    } else if (this->IsUnion()) {
924
      os << "(";
925 926 927
      UnionHandle unioned = handle(this->AsUnion());
      for (int i = 0; i < unioned->Length(); ++i) {
        TypeHandle type_i = unioned->Get(i);
928 929
        if (i > 0) os << " | ";
        type_i->PrintTo(os, dim);
930
      }
931
      os << ")";
932
    } else if (this->IsArray()) {
933 934 935
      os << "Array(";
      AsArray()->Element()->PrintTo(os, dim);
      os << ")";
936 937
    } else if (this->IsFunction()) {
      if (!this->AsFunction()->Receiver()->IsAny()) {
938 939
        this->AsFunction()->Receiver()->PrintTo(os, dim);
        os << ".";
940
      }
941
      os << "(";
942
      for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
943 944
        if (i > 0) os << ", ";
        this->AsFunction()->Parameter(i)->PrintTo(os, dim);
945
      }
946 947
      os << ")->";
      this->AsFunction()->Result()->PrintTo(os, dim);
948 949
    } else {
      UNREACHABLE();
950
    }
951
  }
952
  if (dim == BOTH_DIMS) os << "/";
953
  if (dim != SEMANTIC_DIM) {
954
    BitsetType::Print(os, REPRESENTATION(this->BitsetLub()));
955 956 957 958
  }
}


959 960 961 962 963 964 965 966 967 968
#ifdef DEBUG
template <class Config>
void TypeImpl<Config>::Print() {
  OFStream os(stdout);
  PrintTo(os);
  os << endl;
}
#endif


969 970 971
// -----------------------------------------------------------------------------
// Instantiations.

972 973 974 975
template class TypeImpl<ZoneTypeConfig>;
template class TypeImpl<ZoneTypeConfig>::Iterator<i::Map>;
template class TypeImpl<ZoneTypeConfig>::Iterator<i::Object>;

976 977 978 979
template class TypeImpl<HeapTypeConfig>;
template class TypeImpl<HeapTypeConfig>::Iterator<i::Map>;
template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>;

980 981 982 983 984 985 986
template TypeImpl<ZoneTypeConfig>::TypeHandle
  TypeImpl<ZoneTypeConfig>::Convert<HeapType>(
    TypeImpl<HeapTypeConfig>::TypeHandle, TypeImpl<ZoneTypeConfig>::Region*);
template TypeImpl<HeapTypeConfig>::TypeHandle
  TypeImpl<HeapTypeConfig>::Convert<Type>(
    TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*);

987
} }  // namespace v8::internal