Reland "Use unsigned type bitsets to limit undefined behaviour"

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 "src/types.h"
 
 #include "src/ostreams.h"
 #include "src/types-inl.h"
 
 namespace v8 {
@@ skipping 12 matching lines @@
 static bool deq(double x, double y) {
   return dle(x, y) && dle(y, x);
 }
 
 
 // -----------------------------------------------------------------------------
 // Glb and lub computation.
 
 // The largest bitset subsumed by this type.
 template<class Config>
-int TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
+typename TypeImpl<Config>::bitset
+TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
   DisallowHeapAllocation no_allocation;
   if (type->IsBitset()) {
     return type->AsBitset();
   } else if (type->IsUnion()) {
     UnionHandle unioned = handle(type->AsUnion());
     DCHECK(unioned->Wellformed());
     return unioned->Get(0)->BitsetGlb();  // Other BitsetGlb's are kNone anyway.
   } else {
     return kNone;
   }
 }
 
 
 // The smallest bitset subsuming this type.
 template<class Config>
-int TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
+typename TypeImpl<Config>::bitset
+TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
   DisallowHeapAllocation no_allocation;
   if (type->IsBitset()) {
     return type->AsBitset();
   } else if (type->IsUnion()) {
     UnionHandle unioned = handle(type->AsUnion());
-    int bitset = kNone;
+    bitset result = kNone;
     for (int i = 0; i < unioned->Length(); ++i) {
-      bitset |= unioned->Get(i)->BitsetLub();
+      result |= unioned->Get(i)->BitsetLub();
     }
-    return bitset;
+    return result;
   } 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();
   } else if (type->IsRange()) {
     return type->AsRange()->Bound()->AsBitset();
   } 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();
   } else {
     UNREACHABLE();
     return kNone;
   }
 }
 
 
 // The smallest bitset subsuming this type, ignoring explicit bounds.
 template<class Config>
-int TypeImpl<Config>::BitsetType::InherentLub(TypeImpl* type) {
+typename TypeImpl<Config>::bitset
+TypeImpl<Config>::BitsetType::InherentLub(TypeImpl* type) {
   DisallowHeapAllocation no_allocation;
   if (type->IsBitset()) {
     return type->AsBitset();
   } else if (type->IsUnion()) {
     UnionHandle unioned = handle(type->AsUnion());
-    int bitset = kNone;
+    bitset result = kNone;
     for (int i = 0; i < unioned->Length(); ++i) {
-      bitset |= unioned->Get(i)->InherentBitsetLub();
+      result |= unioned->Get(i)->InherentBitsetLub();
     }
-    return bitset;
+    return result;
   } else if (type->IsClass()) {
     return Lub(*type->AsClass()->Map());
   } else if (type->IsConstant()) {
     return Lub(*type->AsConstant()->Value());
   } else if (type->IsRange()) {
     return Lub(type->AsRange()->Min(), type->AsRange()->Max());
   } else if (type->IsContext()) {
     return kInternal & kTaggedPtr;
   } else if (type->IsArray()) {
     return kArray;
   } else if (type->IsFunction()) {
     return kFunction;
   } else {
     UNREACHABLE();
     return kNone;
   }
 }
 
 
 template<class Config>
-int TypeImpl<Config>::BitsetType::Lub(i::Object* value) {
+typename TypeImpl<Config>::bitset
+TypeImpl<Config>::BitsetType::Lub(i::Object* value) {
   DisallowHeapAllocation no_allocation;
   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) {
+typename TypeImpl<Config>::bitset
+TypeImpl<Config>::BitsetType::Lub(double value) {
   DisallowHeapAllocation no_allocation;
   if (i::IsMinusZero(value)) return kMinusZero;
   if (std::isnan(value)) return kNaN;
   if (IsUint32Double(value)) return Lub(FastD2UI(value));
   if (IsInt32Double(value)) return Lub(FastD2I(value));
   return kOtherNumber;
 }
 
 
 template<class Config>
-int TypeImpl<Config>::BitsetType::Lub(double min, double max) {
+typename TypeImpl<Config>::bitset
+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;
+  bitset result = BitsetType::kNumber ^ SEMANTIC(BitsetType::kNaN);
+  if (dle(0, min) || max < 0) result ^= SEMANTIC(BitsetType::kMinusZero);
+  return result;
   // TODO(neis): Could refine this further by doing more checks on min/max.
 }
 
 
 template<class Config>
-int TypeImpl<Config>::BitsetType::Lub(int32_t value) {
+typename TypeImpl<Config>::bitset
+TypeImpl<Config>::BitsetType::Lub(int32_t value) {
   if (value >= 0x40000000) {
     return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
   }
   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) {
+typename TypeImpl<Config>::bitset
+TypeImpl<Config>::BitsetType::Lub(uint32_t value) {
   DisallowHeapAllocation no_allocation;
   if (value >= 0x80000000u) return kOtherUnsigned32;
   if (value >= 0x40000000u) {
     return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
   }
   return kUnsignedSmall;
 }
 
 
 template<class Config>
-int TypeImpl<Config>::BitsetType::Lub(i::Map* map) {
+typename TypeImpl<Config>::bitset
+TypeImpl<Config>::BitsetType::Lub(i::Map* map) {
   DisallowHeapAllocation no_allocation;
   switch (map->instance_type()) {
     case STRING_TYPE:
     case ONE_BYTE_STRING_TYPE:
     case CONS_STRING_TYPE:
     case CONS_ONE_BYTE_STRING_TYPE:
     case SLICED_STRING_TYPE:
     case SLICED_ONE_BYTE_STRING_TYPE:
     case EXTERNAL_STRING_TYPE:
     case EXTERNAL_ONE_BYTE_STRING_TYPE:
@@ skipping 270 matching lines @@
   }
   return true;
 }
 
 
 // -----------------------------------------------------------------------------
 // Union and intersection
 
 template<class Config>
 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Rebound(
-    int bitset, Region* region) {
-  TypeHandle bound = BitsetType::New(bitset, region);
+    bitset bitset_bound, Region* region) {
+  TypeHandle bound = BitsetType::New(bitset_bound, region);
   if (this->IsClass()) {
     return ClassType::New(this->AsClass()->Map(), bound, region);
   } else if (this->IsConstant()) {
     return ConstantType::New(this->AsConstant()->Value(), bound, region);
   } else if (this->IsRange()) {
     return RangeType::New(
         this->AsRange()->Min(), this->AsRange()->Max(), bound, region);
   } 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()) {
     FunctionHandle function = Config::handle(this->AsFunction());
     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) {
+typename TypeImpl<Config>::bitset TypeImpl<Config>::BoundBy(TypeImpl* that) {
   DCHECK(!this->IsUnion());
   if (that->IsUnion()) {
     UnionType* unioned = that->AsUnion();
     int length = unioned->Length();
-    int bitset = BitsetType::kNone;
+    bitset result = BitsetType::kNone;
     for (int i = 0; i < length; ++i) {
-      bitset |= BoundBy(unioned->Get(i)->unhandle());
+      result |= BoundBy(unioned->Get(i)->unhandle());
     }
-    return bitset;
+    return result;
   } 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) {
+    bitset bound, UnionHandle unioned, int current_size) {
   DCHECK(!this->IsUnion());
   for (int i = 0; i < current_size; ++i) {
     TypeHandle that = unioned->Get(i);
     if (that->IsBitset()) {
       if (BitsetType::Is(bound, that->AsBitset())) return i;
     } 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;
     }
   }
   return -1;
 }
 
 
 // Get non-bitsets from type, bounded by upper.
 // Store at result starting at index. Returns updated index.
 template<class Config>
 int TypeImpl<Config>::ExtendUnion(
     UnionHandle result, int size, TypeHandle type,
     TypeHandle other, bool is_intersect, Region* region) {
   if (type->IsUnion()) {
-    UnionHandle unioned = handle(type->AsUnion());
+    UnionHandle unioned = Config::template cast<UnionType>(type);
     for (int i = 0; i < unioned->Length(); ++i) {
       TypeHandle type_i = unioned->Get(i);
       DCHECK(i == 0 || !(type_i->IsBitset() || type_i->Is(unioned->Get(0))));
       if (!type_i->IsBitset()) {
         size = ExtendUnion(result, size, type_i, other, is_intersect, region);
       }
     }
   } else if (!type->IsBitset()) {
     DCHECK(type->IsClass() || type->IsConstant() || type->IsRange() ||
            type->IsContext() || type->IsArray() || type->IsFunction());
-    int inherent_bound = type->InherentBitsetLub();
-    int old_bound = type->BitsetLub();
-    int other_bound = type->BoundBy(other->unhandle()) & inherent_bound;
-    int new_bound =
+    bitset inherent_bound = type->InherentBitsetLub();
+    bitset old_bound = type->BitsetLub();
+    bitset other_bound = type->BoundBy(other->unhandle()) & inherent_bound;
+    bitset new_bound =
         is_intersect ? (old_bound & other_bound) : (old_bound | other_bound);
     if (new_bound != BitsetType::kNone) {
       int i = type->IndexInUnion(new_bound, result, size);
       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();
+        bitset type_i_bound = result->Get(i)->BitsetLub();
         new_bound |= type_i_bound;
         if (new_bound == type_i_bound) return size;
       }
       if (new_bound != old_bound) type = type->Rebound(new_bound, region);
       result->Set(i, type);
     }
   }
   return size;
 }
 
@@ skipping 18 matching lines @@
   }
 
   // Slow case: may need to produce a Unioned object.
   int size = 0;
   if (!type1->IsBitset()) {
     size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1);
   }
   if (!type2->IsBitset()) {
     size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1);
   }
-  int bitset = type1->BitsetGlb() | type2->BitsetGlb();
-  if (bitset != BitsetType::kNone) ++size;
+  bitset bits = type1->BitsetGlb() | type2->BitsetGlb();
+  if (bits != BitsetType::kNone) ++size;
   DCHECK(size >= 1);
 
   UnionHandle unioned = UnionType::New(size, region);
   size = 0;
-  if (bitset != BitsetType::kNone) {
-    unioned->Set(size++, BitsetType::New(bitset, region));
+  if (bits != BitsetType::kNone) {
+    unioned->Set(size++, BitsetType::New(bits, region));
   }
   size = ExtendUnion(unioned, size, type1, type2, false, region);
   size = ExtendUnion(unioned, size, type2, type1, false, region);
 
   if (size == 1) {
     return unioned->Get(0);
   } else {
     unioned->Shrink(size);
     DCHECK(unioned->Wellformed());
     return unioned;
@@ skipping 21 matching lines @@
   }
 
   // Slow case: may need to produce a Unioned object.
   int size = 0;
   if (!type1->IsBitset()) {
     size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1);
   }
   if (!type2->IsBitset()) {
     size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1);
   }
-  int bitset = type1->BitsetGlb() & type2->BitsetGlb();
-  if (bitset != BitsetType::kNone) ++size;
+  bitset bits = type1->BitsetGlb() & type2->BitsetGlb();
+  if (bits != BitsetType::kNone) ++size;
   DCHECK(size >= 1);
 
   UnionHandle unioned = UnionType::New(size, region);
   size = 0;
-  if (bitset != BitsetType::kNone) {
-    unioned->Set(size++, BitsetType::New(bitset, region));
+  if (bits != BitsetType::kNone) {
+    unioned->Set(size++, BitsetType::New(bits, region));
   }
   size = ExtendUnion(unioned, size, type1, type2, true, region);
   size = ExtendUnion(unioned, size, type2, type1, true, region);
 
   if (size == 0) {
     return None(region);
   } else if (size == 1) {
     return unioned->Get(0);
   } else {
     unioned->Shrink(size);
@@ skipping 88 matching lines @@
 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());
+    UnionHandle unioned = Config::template cast<UnionType>(type_);
     for (; index_ < unioned->Length(); ++index_) {
       if (matches(unioned->Get(index_))) return;
     }
   } else if (index_ == 0 && matches(type_)) {
     return;
   }
   index_ = -1;
 }
 
 
@@ skipping 48 matching lines @@
     UNREACHABLE();
     return None(region);
   }
 }
 
 
 // -----------------------------------------------------------------------------
 // Printing.
 
 template<class Config>
-const char* TypeImpl<Config>::BitsetType::Name(int bitset) {
-  switch (bitset) {
+const char* TypeImpl<Config>::BitsetType::Name(bitset bits) {
+  switch (bits) {
     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
 
     #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
 
     default:
       return NULL;
   }
 }
 
 
 template <class Config>
 void TypeImpl<Config>::BitsetType::Print(OStream& os,  // NOLINT
-                                         int bitset) {
+                                         bitset bits) {
   DisallowHeapAllocation no_allocation;
-  const char* name = Name(bitset);
+  const char* name = Name(bits);
   if (name != NULL) {
     os << name;
     return;
   }
 
-  static const int named_bitsets[] = {
+  static const bitset named_bitsets[] = {
 #define BITSET_CONSTANT(type, value) REPRESENTATION(k##type),
       REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
 #undef BITSET_CONSTANT
 
 #define BITSET_CONSTANT(type, value) SEMANTIC(k##type),
       SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
 #undef BITSET_CONSTANT
   };
 
   bool is_first = true;
   os << "(";
-  for (int i(arraysize(named_bitsets) - 1); bitset != 0 && i >= 0; --i) {
-    int subset = named_bitsets[i];
-    if ((bitset & subset) == subset) {
+  for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
+    bitset subset = named_bitsets[i];
+    if ((bits & subset) == subset) {
       if (!is_first) os << " | ";
       is_first = false;
       os << Name(subset);
-      bitset -= subset;
+      bits -= subset;
     }
   }
-  DCHECK(bitset == 0);
+  DCHECK(bits == 0);
   os << ")";
 }
 
 
 template <class Config>
 void TypeImpl<Config>::PrintTo(OStream& os, PrintDimension dim) {  // NOLINT
   DisallowHeapAllocation no_allocation;
   if (dim != REPRESENTATION_DIM) {
     if (this->IsBitset()) {
       BitsetType::Print(os, SEMANTIC(this->AsBitset()));
@@ skipping 73 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