Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(371)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/types.cc

Issue 251753005: Establish distributivity for type union & intersection (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Eps Created 6 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« src/types.h ('K') | « src/types.h ('k') | src/types-inl.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/types.cc
diff --git a/src/types.cc b/src/types.cc
index 394f7726791b8cd81a9c8ae17a838d6cc47703e3..eae5f38320d25ac58945f7d3639197a564718e43 100644
--- a/src/types.cc
+++ b/src/types.cc
@@ -139,11 +139,39 @@ int TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
}
return bitset;
} else if (type->IsClass()) {
- int bitset = Config::lub_bitset(type);
- return bitset ? bitset : Lub(*type->AsClass()->Map());
+ // 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()) {
- int bitset = Config::lub_bitset(type);
- return bitset ? bitset : Lub(*type->AsConstant()->Value());
+ return type->AsConstant()->Bound()->AsBitset();
+ } else if (type->IsArray()) {
+ return type->AsArray()->Bound()->AsBitset();
+ } else if (type->IsFunction()) {
+ return type->AsFunction()->Bound()->AsBitset();
+ } else {
+ UNREACHABLE();
+ return kNone;
+ }
+}
+
+
+// Get the smallest bitset subsuming this type, ignoring current bounds.
+template<class Config>
+int 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;
+ for (int i = 0; i < unioned->Length(); ++i) {
+ bitset |= unioned->Get(i)->InherentBitsetLub();
+ }
+ return bitset;
+ } else if (type->IsClass()) {
+ return Lub(*type->AsClass()->Map());
+ } else if (type->IsConstant()) {
+ return Lub(*type->AsConstant()->Value());
} else if (type->IsArray()) {
return kArray;
} else if (type->IsFunction()) {
@@ -287,11 +315,15 @@ bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
if (that->IsClass()) {
return this->IsClass()
- && *this->AsClass()->Map() == *that->AsClass()->Map();
+ && *this->AsClass()->Map() == *that->AsClass()->Map()
+ && ((Config::is_class(that) && Config::is_class(this)) ||
+ BitsetType::New(this->BitsetLub())->Is(
+ BitsetType::New(that->BitsetLub())));
}
if (that->IsConstant()) {
return this->IsConstant()
- && *this->AsConstant()->Value() == *that->AsConstant()->Value();
+ && *this->AsConstant()->Value() == *that->AsConstant()->Value()
+ && this->AsConstant()->Bound()->Is(that->AsConstant()->Bound());
}
if (that->IsArray()) {
return this->IsArray()
@@ -424,7 +456,6 @@ bool TypeImpl<Config>::Maybe(TypeImpl* that) {
template<class Config>
bool TypeImpl<Config>::Contains(i::Object* value) {
DisallowHeapAllocation no_allocation;
-
for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
if (*it.Current() == value) return true;
}
@@ -433,43 +464,138 @@ bool TypeImpl<Config>::Contains(i::Object* value) {
template<class Config>
-bool TypeImpl<Config>::InUnion(UnionHandle unioned, int current_size) {
+bool TypeImpl<Config>::UnionType::Wellformed() {
+ ASSERT(this->Length() >= 2);
Benedikt Meurer 2014/05/23 05:09:00 This function always returns true, so the return t
+ for (int i = 0; i < this->Length(); ++i) {
+ ASSERT(!this->Get(i)->IsUnion());
+ if (i > 0) ASSERT(!this->Get(i)->IsBitset());
+ for (int j = 0; j < this->Length(); ++j) {
+ if (i != j) ASSERT(!this->Get(i)->Is(this->Get(j)));
+ }
+ }
+ return true;
+}
+
+
+template<class Config>
+typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Narrow(
+ 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);
+ } else if (this->IsArray()) {
+ return ArrayType::New(this->AsArray()->Element(), bound, region);
+ } else if (this->IsFunction()) {
+ FunctionType* function = 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) {
+ ASSERT(!this->IsUnion());
+ if (that->IsBitset()) {
+ return that->AsBitset() & this->InherentBitsetLub();
+ } else 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->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 BitsetType::kNone;
+}
+
+
+template<class Config>
+int TypeImpl<Config>::IndexInUnion(
+ int bound, UnionHandle unioned, int current_size) {
ASSERT(!this->IsUnion());
for (int i = 0; i < current_size; ++i) {
- if (this->Is(unioned->Get(i))) return true;
+ TypeHandle that = unioned->Get(i);
+ if (that->IsBitset()) {
+ if ((bound | that->AsBitset()) == 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->IsArray() && this->IsArray()) {
+ if (this->Is(that)) return i;
+ } else if (that->IsFunction() && this->IsFunction()) {
+ if (this->Is(that)) return i;
+ }
}
- return false;
+ return -1;
}
-// Get non-bitsets from this which are not subsumed by union, store at result,
-// starting at index. Returns updated index.
+// 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, TypeHandle type, int current_size) {
- int old_size = current_size;
+ UnionHandle result, int size, TypeHandle type,
+ TypeHandle other, bool is_intersect, Region* region) {
+ int old_size = size;
if (type->IsUnion()) {
UnionHandle unioned = handle(type->AsUnion());
for (int i = 0; i < unioned->Length(); ++i) {
- TypeHandle type = unioned->Get(i);
- ASSERT(i == 0 || !(type->IsBitset() || type->Is(unioned->Get(0))));
- if (!type->IsBitset() && !type->InUnion(result, old_size)) {
- result->Set(current_size++, type);
+ TypeHandle type_i = unioned->Get(i);
+ ASSERT(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()) {
- // For all structural types, subtyping implies equivalence.
ASSERT(type->IsClass() || type->IsConstant() ||
type->IsArray() || type->IsFunction());
- if (!type->InUnion(result, old_size)) {
- result->Set(current_size++, type);
+ int old_bound = type->BitsetLub();
+ int other_bound = type->BoundBy(other->unhandle());
+ int new_bound =
+ is_intersect ? (old_bound & other_bound) : (old_bound | other_bound);
+ if (new_bound != BitsetType::kNone) {
+ int i = type->IndexInUnion(new_bound, result, old_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();
+ new_bound |= type_i_bound;
+ if (new_bound == type_i_bound) return size;
+ }
+ if (new_bound != old_bound) type = type->Narrow(new_bound, region);
+ result->Set(i, type);
}
}
- return current_size;
+ return size;
}
-// Union is O(1) on simple bit unions, but O(n*m) on structured unions.
+// Union is O(1) on simple bitsets, but O(n*m) on structured unions.
template<class Config>
typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
TypeHandle type1, TypeHandle type2, Region* region) {
@@ -505,47 +631,21 @@ typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
if (bitset != BitsetType::kNone) {
unioned->Set(size++, BitsetType::New(bitset, region));
}
- size = ExtendUnion(unioned, type1, size);
- size = ExtendUnion(unioned, type2, size);
+
+ 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);
+ ASSERT(unioned->Wellformed());
return unioned;
}
}
-// Get non-bitsets from type which are also in other, store at result,
-// starting at index. Returns updated index.
-template<class Config>
-int TypeImpl<Config>::ExtendIntersection(
- UnionHandle result, TypeHandle type, TypeHandle other, int current_size) {
- int old_size = current_size;
- if (type->IsUnion()) {
- UnionHandle unioned = handle(type->AsUnion());
- for (int i = 0; i < unioned->Length(); ++i) {
- TypeHandle type = unioned->Get(i);
- ASSERT(i == 0 || !(type->IsBitset() || type->Is(unioned->Get(0))));
- if (!type->IsBitset() && type->Is(other) &&
- !type->InUnion(result, old_size)) {
- result->Set(current_size++, type);
- }
- }
- } else if (!type->IsBitset()) {
- // For all structural types, subtyping implies equivalence.
- ASSERT(type->IsClass() || type->IsConstant() ||
- type->IsArray() || type->IsFunction());
- if (type->Is(other) && !type->InUnion(result, old_size)) {
- result->Set(current_size++, type);
- }
- }
- return current_size;
-}
-
-
-// Intersection is O(1) on simple bit unions, but O(n*m) on structured unions.
+// Intersection is O(1) on simple bitsets, but O(n*m) on structured unions.
template<class Config>
typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
TypeHandle type1, TypeHandle type2, Region* region) {
@@ -581,8 +681,8 @@ typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
if (bitset != BitsetType::kNone) {
unioned->Set(size++, BitsetType::New(bitset, region));
}
- size = ExtendIntersection(unioned, type1, type2, size);
- size = ExtendIntersection(unioned, type2, type1, size);
+ size = ExtendUnion(unioned, size, type1, type2, true, region);
+ size = ExtendUnion(unioned, size, type2, type1, true, region);
if (size == 0) {
return None(region);
@@ -590,6 +690,7 @@ typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
return unioned->Get(0);
} else {
unioned->Shrink(size);
+ ASSERT(unioned->Wellformed());
return unioned;
}
}
@@ -602,9 +703,13 @@ typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
if (type->IsBitset()) {
return BitsetType::New(type->AsBitset(), region);
} else if (type->IsClass()) {
- return ClassType::New(type->AsClass()->Map(), region);
+ return ClassType::New(
+ type->AsClass()->Map(),
+ BitsetType::New(type->BitsetLub(), region), region);
} else if (type->IsConstant()) {
- return ConstantType::New(type->AsConstant()->Value(), region);
+ return ConstantType::New(
+ type->AsConstant()->Value(),
+ Convert<OtherType>(type->AsConstant()->Bound(), region), region);
} else if (type->IsUnion()) {
int length = type->AsUnion()->Length();
UnionHandle unioned = UnionType::New(length, region);
@@ -614,11 +719,13 @@ typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
return unioned;
} else if (type->IsArray()) {
return ArrayType::New(
- Convert<OtherType>(type->AsArray()->Element(), region), region);
+ Convert<OtherType>(type->AsArray()->Element(), region),
+ Convert<OtherType>(type->AsArray()->Bound(), region), region);
} else if (type->IsFunction()) {
FunctionHandle function = FunctionType::New(
Convert<OtherType>(type->AsFunction()->Result(), region),
Convert<OtherType>(type->AsFunction()->Receiver(), region),
+ Convert<OtherType>(type->AsFunction()->Bound(), region),
type->AsFunction()->Arity(), region);
for (int i = 0; i < function->Arity(); ++i) {
function->InitParameter(i,
« src/types.h ('K') | « src/types.h ('k') | src/types-inl.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698