[turbofan] Separate representation type operations from the semantic types.

src/types.cc

 // 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.
 
 #include <iomanip>
 
 #include "src/types.h"
 
 #include "src/ostreams.h"
 #include "src/types-inl.h"
@@ skipping 10 matching lines @@
 // Range-related helper functions.
 
 // The result may be invalid (max < min).
 template<class Config>
 typename TypeImpl<Config>::Limits TypeImpl<Config>::Intersect(
     Limits lhs, Limits rhs) {
   DisallowHeapAllocation no_allocation;
   Limits result(lhs);
   if (lhs.min < rhs.min) result.min = rhs.min;
   if (lhs.max > rhs.max) result.max = rhs.max;
-  result.representation = lhs.representation & rhs.representation;
   return result;
 }
 
 
 template <class Config>
 bool TypeImpl<Config>::IsEmpty(Limits lim) {
   return lim.min > lim.max;
 }
 
 
 template <class Config>
 typename TypeImpl<Config>::Limits TypeImpl<Config>::Union(Limits lhs,
                                                           Limits rhs) {
   DisallowHeapAllocation no_allocation;
+  if (IsEmpty(lhs)) return rhs;
+  if (IsEmpty(rhs)) return lhs;
   Limits result(lhs);
   if (lhs.min > rhs.min) result.min = rhs.min;
   if (lhs.max < rhs.max) result.max = rhs.max;
-  result.representation = lhs.representation | rhs.representation;
   return result;
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::Overlap(
     typename TypeImpl<Config>::RangeType* lhs,
     typename TypeImpl<Config>::RangeType* rhs) {
   DisallowHeapAllocation no_allocation;
   typename TypeImpl<Config>::Limits lim = Intersect(Limits(lhs), Limits(rhs));
   return lim.min <= lim.max;
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::Contains(
     typename TypeImpl<Config>::RangeType* lhs,
     typename TypeImpl<Config>::RangeType* rhs) {
   DisallowHeapAllocation no_allocation;
-  return BitsetType::Is(rhs->Bound(), lhs->Bound()) &&
-         lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
+  return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
 }
 
 
 template <class Config>
 bool TypeImpl<Config>::Contains(typename TypeImpl<Config>::RangeType* lhs,
                                 typename TypeImpl<Config>::ConstantType* rhs) {
   DisallowHeapAllocation no_allocation;
   return IsInteger(*rhs->Value()) &&
-         BitsetType::Is(rhs->Bound()->AsBitset(), lhs->Bound()) &&
          lhs->Min() <= rhs->Value()->Number() &&
          rhs->Value()->Number() <= lhs->Max();
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::Contains(
     typename TypeImpl<Config>::RangeType* range, i::Object* val) {
   DisallowHeapAllocation no_allocation;
   return IsInteger(val) &&
-         BitsetType::Is(BitsetType::Lub(val), range->Bound()) &&
          range->Min() <= val->Number() && val->Number() <= range->Max();
 }
 
 
 // -----------------------------------------------------------------------------
 // Min and Max computation.
 
 template<class Config>
 double TypeImpl<Config>::Min() {
-  DCHECK(this->Is(Number()));
+  DCHECK(this->SemanticIs(Number()));
   if (this->IsBitset()) return BitsetType::Min(this->AsBitset());
   if (this->IsUnion()) {
     double min = +V8_INFINITY;
     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
       min = std::min(min, this->AsUnion()->Get(i)->Min());
     }
     return min;
   }
   if (this->IsRange()) return this->AsRange()->Min();
   if (this->IsConstant()) return this->AsConstant()->Value()->Number();
   UNREACHABLE();
   return 0;
 }
 
 
 template<class Config>
 double TypeImpl<Config>::Max() {
-  DCHECK(this->Is(Number()));
+  DCHECK(this->SemanticIs(Number()));
   if (this->IsBitset()) return BitsetType::Max(this->AsBitset());
   if (this->IsUnion()) {
     double max = -V8_INFINITY;
     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
       max = std::max(max, this->AsUnion()->Get(i)->Max());
     }
     return max;
   }
   if (this->IsRange()) return this->AsRange()->Max();
   if (this->IsConstant()) return this->AsConstant()->Value()->Number();
   UNREACHABLE();
   return 0;
 }
 
 
 // -----------------------------------------------------------------------------
 // Glb and lub computation.
 
 
 // The largest bitset subsumed by this type.
 template<class Config>
 typename TypeImpl<Config>::bitset
 TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
   DisallowHeapAllocation no_allocation;
+  // Fast case.
   if (type->IsBitset()) {
     return type->AsBitset();
   } else if (type->IsUnion()) {
     SLOW_DCHECK(type->AsUnion()->Wellformed());
     return type->AsUnion()->Get(0)->BitsetGlb() |
-           type->AsUnion()->Get(1)->BitsetGlb();  // Shortcut.
+           SEMANTIC(type->AsUnion()->Get(1)->BitsetGlb());  // Shortcut.
   } else if (type->IsRange()) {
     bitset glb = SEMANTIC(
         BitsetType::Glb(type->AsRange()->Min(), type->AsRange()->Max()));
-    if (glb == 0) {
-      return kNone;
-    } else {
-      return glb | REPRESENTATION(type->BitsetLub());
-    }
+    return glb | REPRESENTATION(type->BitsetLub());
   } else {
-    // (The remaining BitsetGlb's are None anyway).
-    return kNone;
+    return type->GetRepresentation();
   }
 }
 
 
 // The smallest bitset subsuming this type.
 template<class Config>
 typename TypeImpl<Config>::bitset
 TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
   DisallowHeapAllocation no_allocation;
   if (type->IsBitset()) return type->AsBitset();
   if (type->IsUnion()) {
-    int bitset = kNone;
+    // Take the representation from the first element.

[rossberg, 2015/02/11 12:34:10]

Nit: add "..., which always is a bitset."

[Jarin, 2015/02/11 16:10:47]

Done.

+    int bitset = type->AsUnion()->Get(0)->BitsetLub();
     for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
-      bitset |= type->AsUnion()->Get(i)->BitsetLub();
+      // Other elements only contribute the semantic part.

[rossberg, 2015/02/11 12:34:10]

Nit: either "contribute to the" or "contribute their"

[Jarin, 2015/02/11 16:10:47]

Done.

+      bitset |= SEMANTIC(type->AsUnion()->Get(i)->BitsetLub());
     }
     return bitset;
   }
   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();
   }
   if (type->IsConstant()) return type->AsConstant()->Bound()->AsBitset();
   if (type->IsRange()) return type->AsRange()->Bound();
@@ skipping 216 matching lines @@
   // in the greatest lower bound. (There is also the small trouble
   // of kOtherNumber having a range hole, which we can conveniently
   // ignore here.)
   return glb & ~(SEMANTIC(kOtherNumber));
 }
 
 
 template <class Config>
 double TypeImpl<Config>::BitsetType::Min(bitset bits) {
   DisallowHeapAllocation no_allocation;
-  DCHECK(Is(bits, kNumber));
+  DCHECK(Is(SEMANTIC(bits), kNumber));
   const Boundary* mins = Boundaries();
   bool mz = SEMANTIC(bits & kMinusZero);
   for (size_t i = 0; i < BoundariesSize(); ++i) {
     if (Is(SEMANTIC(mins[i].bits), bits)) {
       return mz ? std::min(0.0, mins[i].min) : mins[i].min;
     }
   }
   if (mz) return 0;
   return std::numeric_limits<double>::quiet_NaN();
 }
 
 
 template<class Config>
 double TypeImpl<Config>::BitsetType::Max(bitset bits) {
   DisallowHeapAllocation no_allocation;
-  DCHECK(Is(bits, kNumber));
+  DCHECK(Is(SEMANTIC(bits), kNumber));
   const Boundary* mins = Boundaries();
   bool mz = SEMANTIC(bits & kMinusZero);
   if (BitsetType::Is(SEMANTIC(mins[BoundariesSize() - 1].bits), bits)) {
     return +V8_INFINITY;
   }
   for (size_t i = BoundariesSize() - 1; i-- > 0;) {
     if (Is(SEMANTIC(mins[i].bits), bits)) {
       return mz ?
           std::max(0.0, mins[i+1].min - 1) : mins[i+1].min - 1;
     }
@@ skipping 38 matching lines @@
     for (int i = 0, n = this_fun->Arity(); i < n; ++i) {
       if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false;
     }
     return true;
   }
   UNREACHABLE();
   return false;
 }
 
 
+template <class Config>
+typename TypeImpl<Config>::bitset TypeImpl<Config>::GetRepresentation() {
+  return REPRESENTATION(this->BitsetLub());
+}
+
+
 // Check if [this] <= [that].
 template<class Config>
 bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
   DisallowHeapAllocation no_allocation;
 
+  // Fast bitset cases
   if (that->IsBitset()) {
     return BitsetType::Is(this->BitsetLub(), that->AsBitset());
   }
+
   if (this->IsBitset()) {
     return BitsetType::Is(this->AsBitset(), that->BitsetGlb());
   }
 
+  // Check the representations.
+  if (!BitsetType::Is(GetRepresentation(), that->GetRepresentation())) {
+    return false;
+  }
+
+  // Check the semantic part.
+  return SemanticIs(that);
+}
+
+
+// Check if SEMANTIC([this]) <= SEMANTIC([that]). The result of the method
+// should be independent of the representation axis of the types.
+template <class Config>
+bool TypeImpl<Config>::SemanticIs(TypeImpl* that) {
+  DisallowHeapAllocation no_allocation;
+
+  if (this == that) return true;
+
+  if (that->IsBitset()) {
+    return BitsetType::Is(SEMANTIC(this->BitsetLub()), that->AsBitset());

[rossberg, 2015/02/11 12:34:10]

Don't you need SEMANTIC on 'that' as well?

[Jarin, 2015/02/11 16:10:47]

I do not think so. That is purely because the representation of the right hand
side cannot possibly affect the result (left hand side representation is empty,
so it is always subtype of the right hand side representation). I agree that
this is not quite obvious, and perhaps a premature optimization.

[rossberg, 2015/02/12 14:39:15]

Ah, right.

+  }
+  if (this->IsBitset()) {
+    return BitsetType::Is(SEMANTIC(this->AsBitset()), that->BitsetGlb());

[rossberg, 2015/02/11 12:34:10]

Similarly here?

[Jarin, 2015/02/11 16:10:47]

See above.

+  }
+
   // (T1 \/ ... \/ Tn) <= T  if  (T1 <= T) /\ ... /\ (Tn <= T)
   if (this->IsUnion()) {
     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
-      if (!this->AsUnion()->Get(i)->Is(that)) return false;
+      if (!this->AsUnion()->Get(i)->SemanticIs(that)) return false;
     }
     return true;
   }
 
   // T <= (T1 \/ ... \/ Tn)  if  (T <= T1) \/ ... \/ (T <= Tn)
   if (that->IsUnion()) {
     for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
-      if (this->Is(that->AsUnion()->Get(i))) return true;
+      if (this->SemanticIs(that->AsUnion()->Get(i)->unhandle())) return true;
       if (i > 1 && this->IsRange()) return false;  // Shortcut.
     }
     return false;
   }
 
   if (that->IsRange()) {
     return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) ||
            (this->IsConstant() &&
             Contains(that->AsRange(), this->AsConstant()));
   }
@@ skipping 32 matching lines @@
   }
   return true;
 }
 
 
 // Check if [this] and [that] overlap.
 template<class Config>
 bool TypeImpl<Config>::Maybe(TypeImpl* that) {
   DisallowHeapAllocation no_allocation;
 
+  // Take care of the representation part (and also approximate
+  // the semantic part).
+  if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
+    return false;
+
+  return SemanticMaybe(that);
+}
+
+template <class Config>
+bool TypeImpl<Config>::SemanticMaybe(TypeImpl* that) {
+  DisallowHeapAllocation no_allocation;
+
   // (T1 \/ ... \/ Tn) overlaps T  if  (T1 overlaps T) \/ ... \/ (Tn overlaps T)
   if (this->IsUnion()) {
     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
-      if (this->AsUnion()->Get(i)->Maybe(that)) return true;
+      if (this->AsUnion()->Get(i)->SemanticMaybe(that)) return true;
     }
     return false;
   }
 
   // T overlaps (T1 \/ ... \/ Tn)  if  (T overlaps T1) \/ ... \/ (T overlaps Tn)
   if (that->IsUnion()) {
     for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
-      if (this->Maybe(that->AsUnion()->Get(i))) return true;
+      if (this->SemanticMaybe(that->AsUnion()->Get(i)->unhandle())) return true;
     }
     return false;
   }
 
-  if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
+  if (!BitsetType::SemanticIsInhabited(this->BitsetLub() & that->BitsetLub()))
     return false;
 
   if (this->IsBitset() && that->IsBitset()) return true;
 
   if (this->IsClass() != that->IsClass()) return true;
 
   if (this->IsRange()) {
     if (that->IsConstant()) {
       return Contains(this->AsRange(), that->AsConstant());
     }
     if (that->IsRange()) {
       return Overlap(this->AsRange(), that->AsRange());
     }
     if (that->IsBitset()) {
       bitset number_bits = BitsetType::NumberBits(that->AsBitset());
       if (number_bits == BitsetType::kNone) {
         return false;
       }
       double min = std::max(BitsetType::Min(number_bits), this->Min());
       double max = std::min(BitsetType::Max(number_bits), this->Max());
       return min <= max;
     }
   }
   if (that->IsRange()) {
-    return that->Maybe(this);  // This case is handled above.
+    return that->SemanticMaybe(this);  // This case is handled above.
   }
 
   if (this->IsBitset() || that->IsBitset()) return true;
 
   return this->SimplyEquals(that);
 }
 
 
 // Return the range in [this], or [NULL].
 template<class Config>
@@ skipping 19 matching lines @@
   }
   return BitsetType::New(BitsetType::Lub(value))->Is(this);
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::UnionType::Wellformed() {
   DisallowHeapAllocation no_allocation;
   // This checks the invariants of the union representation:
   // 1. There are at least two elements.
-  // 2. At most one element is a bitset, and it must be the first one.
+  // 2. The first element is a bitset, no other element is a bitset.
   // 3. At most one element is a range, and it must be the second one
   //    (even when the first element is not a bitset).

[rossberg, 2015/02/11 12:34:10]

This line is obsolete now.

[Jarin, 2015/02/11 16:10:47]

Done.

   // 4. No element is itself a union.
-  // 5. No element is a subtype of any other.
+  // 5. No element (except the bitset) is a subtype of any other.
   // 6. If there is a range, then the bitset type does not contain
   //    plain number bits.
   DCHECK(this->Length() >= 2);  // (1)
-
-  bitset number_bits = this->Get(0)->IsBitset()
-      ? BitsetType::NumberBits(this->Get(0)->AsBitset()) : 0;
-  USE(number_bits);
+  DCHECK(this->Get(0)->IsBitset());  // (2a)
 
   for (int i = 0; i < this->Length(); ++i) {
-    if (i != 0) DCHECK(!this->Get(i)->IsBitset());  // (2)
+    if (i != 0) DCHECK(!this->Get(i)->IsBitset());  // (2b)
     if (i != 1) DCHECK(!this->Get(i)->IsRange());   // (3)
     DCHECK(!this->Get(i)->IsUnion());               // (4)
     for (int j = 0; j < this->Length(); ++j) {
-      if (i != j) DCHECK(!this->Get(i)->Is(this->Get(j)));  // (5)
+      if (i != j && i != 0)
+        DCHECK(!this->Get(i)->SemanticIs(this->Get(j)->unhandle()));  // (5)
     }
   }
-  DCHECK(!this->Get(1)->IsRange() || (number_bits == 0));  // (6)
+  DCHECK(!this->Get(1)->IsRange() ||
+         (BitsetType::NumberBits(this->Get(0)->AsBitset()) ==
+          BitsetType::kNone));  // (6)
   return true;
 }
 
 
 // -----------------------------------------------------------------------------
 // Union and intersection
 
 
 static bool AddIsSafe(int x, int y) {
   return x >= 0 ?
       y <= std::numeric_limits<int>::max() - x :
       y >= std::numeric_limits<int>::min() - x;
 }
 
 
 template<class Config>
 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
     TypeHandle type1, TypeHandle type2, Region* region) {
-  bitset bits = type1->BitsetGlb() & type2->BitsetGlb();
-  if (!BitsetType::IsInhabited(bits)) bits = BitsetType::kNone;
 
   // Fast case: bit sets.
   if (type1->IsBitset() && type2->IsBitset()) {
-    return BitsetType::New(bits, region);
+    return BitsetType::New(type1->AsBitset() & type2->AsBitset(), region);
   }
 
   // Fast case: top or bottom types.
   if (type1->IsNone() || type2->IsAny()) return type1;  // Shortcut.
   if (type2->IsNone() || type1->IsAny()) return type2;  // Shortcut.
 
   // Semi-fast case.
   if (type1->Is(type2)) return type1;
   if (type2->Is(type1)) return type2;
 
   // Slow case: create union.
+
+  // Figure out the representation of the result first.
+  // The rest of the method should not change this representation and
+  // it should make any decisions based on representations (i.e.,

[rossberg, 2015/02/11 12:34:10]

"should not make"?

[Jarin, 2015/02/11 16:10:47]

Done.

+  // it should only use the semantic part of types).
+  const bitset representation =
+      type1->GetRepresentation() & type2->GetRepresentation();
+
+  // Semantic subtyping check - this is needed for consistency with the
+  // semi-fast case above - we should behave the same way regardless of
+  // representations. Intersection with a universal bitset should only update
+  // the representations.
+  if (type1->SemanticIs(type2->unhandle())) {
+    type2 = Any(region);
+  } else if (type2->SemanticIs(type1->unhandle())) {
+    type1 = Any(region);
+  }
+
+  bitset bits =
+      SEMANTIC(type1->BitsetGlb() & type2->BitsetGlb()) | representation;
   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
   if (!AddIsSafe(size1, size2)) return Any(region);
   int size = size1 + size2;
   if (!AddIsSafe(size, 2)) return Any(region);
   size += 2;
   UnionHandle result = UnionType::New(size, region);
   size = 0;
 
   // Deal with bitsets.
   result->Set(size++, BitsetType::New(bits, region));
-  // Insert a placeholder for the range.
-  result->Set(size++, None(region));
 
   Limits lims = Limits::Empty(region);
   size = IntersectAux(type1, type2, result, size, &lims, region);
 
   // If the range is not empty, then insert it into the union and
   // remove the number bits from the bitset.
   if (!IsEmpty(lims)) {
-    size = UpdateRange(RangeType::New(lims, region), result, size, region);
+    size = UpdateRange(RangeType::New(lims, representation, region), result,
+                       size, region);
 
     // Remove the number bits.
     bitset number_bits = BitsetType::NumberBits(bits);
     bits &= ~number_bits;
-    if (SEMANTIC(bits) == BitsetType::kNone) {
-      bits = BitsetType::kNone;
-    }
     result->Set(0, BitsetType::New(bits, region));
   }
   return NormalizeUnion(result, size);
 }
 
 
 template<class Config>
 int TypeImpl<Config>::UpdateRange(
     RangeHandle range, UnionHandle result, int size, Region* region) {
-  TypeHandle old_range = result->Get(1);
-  DCHECK(old_range->IsRange() || old_range->IsNone());
-  if (range->Is(old_range)) return size;
-  if (!old_range->Is(range->unhandle())) {
-    range = RangeType::New(
-        Union(Limits(range->AsRange()), Limits(old_range->AsRange())), region);
+  if (size == 1) {
+    result->Set(size++, range);
+  } else {
+    // Make space for the range.
+    result->Set(size++, result->Get(1));
+    result->Set(1, range);
   }
-  result->Set(1, range);
 
   // Remove any components that just got subsumed.
   for (int i = 2; i < size; ) {
-    if (result->Get(i)->Is(range->unhandle())) {
+    if (result->Get(i)->SemanticIs(range->unhandle())) {
       result->Set(i, result->Get(--size));
     } else {
       ++i;
     }
   }
   return size;
 }
 
 
 template <class Config>
 typename TypeImpl<Config>::Limits TypeImpl<Config>::ToLimits(bitset bits,
                                                              Region* region) {
-  bitset representation = REPRESENTATION(bits);
   bitset number_bits = BitsetType::NumberBits(bits);
 
-  if (representation == BitsetType::kNone && number_bits == BitsetType::kNone) {
+  if (number_bits == BitsetType::kNone) {
     return Limits::Empty(region);
   }
 
-  return Limits(BitsetType::Min(number_bits), BitsetType::Max(number_bits),
-                representation);
+  return Limits(BitsetType::Min(number_bits), BitsetType::Max(number_bits));
 }
 
 
 template <class Config>
 typename TypeImpl<Config>::Limits TypeImpl<Config>::IntersectRangeAndBitset(
     TypeHandle range, TypeHandle bitset, Region* region) {
   Limits range_lims(range->AsRange());
   Limits bitset_lims = ToLimits(bitset->AsBitset(), region);
   return Intersect(range_lims, bitset_lims);
 }
@@ skipping 11 matching lines @@
     return size;
   }
   if (rhs->IsUnion()) {
     for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) {
       size =
           IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, region);
     }
     return size;
   }
 
-  if (!BitsetType::IsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
+  if (!BitsetType::SemanticIsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
     return size;
   }
 
   if (lhs->IsRange()) {
     if (rhs->IsBitset()) {
       Limits lim = IntersectRangeAndBitset(lhs, rhs, region);
 
       if (!IsEmpty(lim)) {
         *lims = Union(lim, *lims);
       }
@@ skipping 39 matching lines @@
     RangeHandle range, bitset* bits, Region* region) {
   // Fast path: If the bitset does not mention numbers, we can just keep the
   // range.
   bitset number_bits = BitsetType::NumberBits(*bits);
   if (number_bits == 0) {
     return range;
   }
 
   // If the range is contained within the bitset, return an empty range
   // (but make sure we take the representation).
-  bitset range_lub = range->BitsetLub();
+  bitset range_lub = SEMANTIC(range->BitsetLub());
   if (BitsetType::Is(BitsetType::NumberBits(range_lub), *bits)) {
-    *bits |= range_lub;
     return None(region);
   }
 
   // Slow path: reconcile the bitset range and the range.
   double bitset_min = BitsetType::Min(number_bits);
   double bitset_max = BitsetType::Max(number_bits);
 
   double range_min = range->Min();
   double range_max = range->Max();
 
-  bitset range_representation = REPRESENTATION(range->BitsetLub());
-  bitset bits_representation = REPRESENTATION(*bits);
-  bitset representation =
-      (bits_representation | range_representation) & BitsetType::kNumber;
-
   // Remove the number bits from the bitset, they would just confuse us now.
   *bits &= ~number_bits;
-  if (bits_representation == *bits) {
-    *bits = BitsetType::kNone;
-  }
 
-  if (representation == range_representation && range_min <= bitset_min &&
-      range_max >= bitset_max) {
+  if (range_min <= bitset_min && range_max >= bitset_max) {
     // Bitset is contained within the range, just return the range.
     return range;
   }
 
   if (bitset_min < range_min) {
     range_min = bitset_min;
   }
   if (bitset_max > range_max) {
     range_max = bitset_max;
   }
   return RangeType::New(range_min, range_max,
-                        BitsetType::New(representation, region), region);
+                        BitsetType::New(BitsetType::kNone, region), region);
 }
 
 
 template<class Config>
 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
     TypeHandle type1, TypeHandle type2, Region* region) {
-
   // Fast case: bit sets.
   if (type1->IsBitset() && type2->IsBitset()) {
     return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region);
   }
 
   // Fast case: top or bottom types.
   if (type1->IsAny() || type2->IsNone()) return type1;
   if (type2->IsAny() || type1->IsNone()) return type2;
 
   // Semi-fast case.
   if (type1->Is(type2)) return type2;
   if (type2->Is(type1)) return type1;
 
+  // Figure out the representation of the result.
+  // The rest of the method should not change this representation and
+  // it should make any decisions based on representations (i.e.,
+  // it should only use the semantic part of types).
+  const bitset representation =
+      type1->GetRepresentation() | type2->GetRepresentation();
+
   // Slow case: create union.
   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
   if (!AddIsSafe(size1, size2)) return Any(region);
   int size = size1 + size2;
   if (!AddIsSafe(size, 2)) return Any(region);
   size += 2;
   UnionHandle result = UnionType::New(size, region);
   size = 0;
 
   // Compute the new bitset.
-  bitset new_bitset = type1->BitsetGlb() | type2->BitsetGlb();
+  bitset new_bitset = SEMANTIC(type1->BitsetGlb() | type2->BitsetGlb());
 
   // Deal with ranges.
   TypeHandle range = None(region);
   RangeType* range1 = type1->GetRange();
   RangeType* range2 = type2->GetRange();
   if (range1 != NULL && range2 != NULL) {
     Limits lims = Union(Limits(range1), Limits(range2));
-    RangeHandle union_range = RangeType::New(lims, region);
+    RangeHandle union_range = RangeType::New(lims, representation, region);
     range = NormalizeRangeAndBitset(union_range, &new_bitset, region);
   } else if (range1 != NULL) {
     range = NormalizeRangeAndBitset(handle(range1), &new_bitset, region);
   } else if (range2 != NULL) {
     range = NormalizeRangeAndBitset(handle(range2), &new_bitset, region);
   }
+  new_bitset = SEMANTIC(new_bitset) | representation;
   TypeHandle bits = BitsetType::New(new_bitset, region);
   result->Set(size++, bits);
-  result->Set(size++, range);
+  if (!range->IsNone()) {
+    result->Set(size++, range);

[rossberg, 2015/02/11 12:34:10]

Nit: single line

[Jarin, 2015/02/11 16:10:47]

Done.

+  }
 
   size = AddToUnion(type1, result, size, region);
   size = AddToUnion(type2, result, size, region);
   return NormalizeUnion(result, size);
 }
 
 
 // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
 // Return new size of [result].
 template<class Config>
 int TypeImpl<Config>::AddToUnion(
     TypeHandle type, UnionHandle result, int size, Region* region) {
   if (type->IsBitset() || type->IsRange()) return size;
   if (type->IsUnion()) {
     for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
       size = AddToUnion(type->AsUnion()->Get(i), result, size, region);
     }
     return size;
   }
   for (int i = 0; i < size; ++i) {
-    if (type->Is(result->Get(i))) return size;
+    if (type->SemanticIs(result->Get(i)->unhandle())) return size;
   }
   result->Set(size++, type);
   return size;
 }
 
 
 template<class Config>
 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeUnion(
     UnionHandle unioned, int size) {
-  DCHECK(size >= 2);
-  // If range is subsumed by bitset, use its place for a different type.
-  if (unioned->Get(1)->Is(unioned->Get(0))) {
-    unioned->Set(1, unioned->Get(--size));
+  DCHECK(size >= 1);
+  DCHECK(unioned->Get(0)->IsBitset());
+  // If the union has just one element, return it.
+  if (size == 1) {
+    return unioned->Get(0);
   }
-  // If bitset is None, use its place for a different type.
-  if (size >= 2 && unioned->Get(0)->IsNone()) {
-    unioned->Set(0, unioned->Get(--size));
+  bitset bits = unioned->Get(0)->AsBitset();
+  // If the union only consists of a range, we can get rid of the union.
+  if (size == 2 && SEMANTIC(bits) == BitsetType::kNone) {
+    bitset representation = REPRESENTATION(bits);
+    if (representation == unioned->Get(1)->GetRepresentation()) {
+      return unioned->Get(1);
+    }
+    // TODO(jarin) If the element at 1 is range of constant, slap
+    // the representation on it and return that.
   }
-  if (size == 1) return unioned->Get(0);
   unioned->Shrink(size);
   SLOW_DCHECK(unioned->Wellformed());
   return unioned;
 }
 
 
 // -----------------------------------------------------------------------------
 // Iteration.
 
 template<class Config>
@@ skipping 290 matching lines @@
 template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>;
 
 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*);
 
 } }  // namespace v8::internal