diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/passes/TypeSSA.cpp | 117 | ||||
| -rw-r--r-- | src/support/hash.h | 5 |
2 files changed, 100 insertions, 22 deletions
diff --git a/src/passes/TypeSSA.cpp b/src/passes/TypeSSA.cpp index 666eda942..33433083f 100644 --- a/src/passes/TypeSSA.cpp +++ b/src/passes/TypeSSA.cpp @@ -52,6 +52,7 @@ #include "ir/names.h" #include "ir/possible-constant.h" #include "pass.h" +#include "support/hash.h" #include "wasm-builder.h" #include "wasm.h" @@ -59,6 +60,96 @@ namespace wasm { namespace { +// Given some TypeBuilder items that we want to build new types with, this +// function builds the types in a new rec group. +// +// This is almost the same as just calling build(), but there is a risk of a +// collision with an existing rec group. This function handles that by finding a +// way to ensure that the new types are in fact in a new rec group. +// +// TODO: Move this outside if we find more uses. +std::vector<HeapType> ensureTypesAreInNewRecGroup(RecGroup recGroup, + Module& wasm) { + auto num = recGroup.size(); + + std::vector<HeapType> types; + types.reserve(num); + for (auto type : recGroup) { + types.push_back(type); + } + + // Find all the heap types present before we create the new ones. The new + // types must not appear in |existingSet|. + std::vector<HeapType> existing = ModuleUtils::collectHeapTypes(wasm); + std::unordered_set<HeapType> existingSet(existing.begin(), existing.end()); + + // Check for a collision with an existing rec group. Note that it is enough to + // check one of the types: either the entire rec group gets merged, so they + // are all merged, or not. + if (existingSet.count(types[0])) { + // Unfortunately there is a conflict. Handle it by adding a "hash" - a + // "random" extra item in the rec group that is so outlandish it will + // surely (?) never collide with anything. We must loop while doing so, + // until we find a hash that does not collide. + auto hashSize = num + 10; + size_t random = num; + while (1) { + // Make a builder and add a slot for the hash. + TypeBuilder builder(num + 1); + for (Index i = 0; i < num; i++) { + auto type = types[i]; + if (type.isStruct()) { + builder[i] = type.getStruct(); + } else { + // Atm this pass only needs struct and array types. If we refactor + // this function to be general purpose we'd need to extend that. TODO + assert(type.isArray()); + builder[i] = type.getArray(); + } + if (auto super = type.getSuperType()) { + builder[i].subTypeOf(*super); + } + } + + // Implement the hash as a struct with "random" fields, and add it. + Struct hashStruct; + for (Index i = 0; i < hashSize; i++) { + // TODO: a denser encoding? + auto type = (random & 1) ? Type::i32 : Type::f64; + hash_combine(random, hashSize + i); + hashStruct.fields.push_back(Field(type, Mutable)); + } + builder[num] = hashStruct; + + // Build and hope for the best. + builder.createRecGroup(0, num + 1); + auto result = builder.build(); + assert(!result.getError()); + types = *result; + assert(types.size() == num + 1); + + if (existingSet.count(types[0])) { + // There is still a collision. Exponentially use larger hashes to + // quickly find one that works. Note that we also use different + // pseudorandom values while doing so in the for-loop above. + hashSize *= 2; + } else { + // Success! Leave the loop. + break; + } + } + } + +#ifndef NDEBUG + // Verify the lack of a collision, just to be safe. + for (auto newType : types) { + assert(!existingSet.count(newType)); + } +#endif + + return types; +} + // A vector of struct.new or one of the variations on array.new. using News = std::vector<Expression*>; @@ -143,6 +234,8 @@ struct TypeSSA : public Pass { // instruction that we found. In the isorecursive type system there isn't an // explicit way to do so, but at least if the new rec group is very large // the risk of collision with another rec group in the program is small. + // (If a collision does happen, though, then that is very dangerous, as + // casts on the new types could succeed in ways the program doesn't expect.) // Note that the risk of collision with things outside of this module is // also a possibility, and so for that reason this pass is likely mostly // useful in the closed-world scenario. @@ -164,27 +257,9 @@ struct TypeSSA : public Pass { auto newTypes = *result; assert(newTypes.size() == num); - // The new types must not overlap with any existing ones. If they do, then - // it would be unsafe to apply this optimization (if casts exist to the - // existing types, the new types merged with them would now succeed on those - // casts). We could try to create a "weird" rec group to avoid this (e.g. we - // could make a rec group larger than any existing one, or with an initial - // member that is "random"), but hopefully this is rare, so just error for - // now. - // - // Note that it is enough to check one of the types: either the entire rec - // group gets merged, so they are all merged, or not. - std::vector<HeapType> typesVec = ModuleUtils::collectHeapTypes(*module); - std::unordered_set<HeapType> typesSet(typesVec.begin(), typesVec.end()); - if (typesSet.count(newTypes[0])) { - Fatal() << "Rec group collision in TypeSSA! Please file a bug"; - } -#ifndef NDEBUG - // Verify the above assumption, just to be safe. - for (auto newType : newTypes) { - assert(!typesSet.count(newType)); - } -#endif + // Make sure this is actually a new rec group. + auto recGroup = newTypes[0].getRecGroup(); + newTypes = ensureTypesAreInNewRecGroup(recGroup, *module); // Success: we can apply the new types. diff --git a/src/support/hash.h b/src/support/hash.h index fc8b358f2..b99902616 100644 --- a/src/support/hash.h +++ b/src/support/hash.h @@ -28,7 +28,10 @@ template<typename T> inline std::size_t hash(const T& value) { } // Combines two digests into the first digest. Use instead of `rehash` if -// `otherDigest` is another digest and not a `size_t` value. +// `otherDigest` is another digest and not a `size_t` value. This is also useful +// when you want deterministic behavior across systems, as this method does not +// call std::hash, so it does not depend on the behavior of the local machine's +// C++ standard library implementation. inline void hash_combine(std::size_t& digest, const std::size_t otherDigest) { // see: boost/container_hash/hash.hpp // The constant is the N-bits reciprocal of the golden ratio: |