diff options
Diffstat (limited to 'src/wasm')
-rw-r--r-- | src/wasm/literal.cpp | 3 | ||||
-rw-r--r-- | src/wasm/wasm-binary.cpp | 6 | ||||
-rw-r--r-- | src/wasm/wasm-stack.cpp | 2 | ||||
-rw-r--r-- | src/wasm/wasm-type.cpp | 489 | ||||
-rw-r--r-- | src/wasm/wasm-validator.cpp | 16 |
5 files changed, 438 insertions, 78 deletions
diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp index 205d65b84..ffb007cf3 100644 --- a/src/wasm/literal.cpp +++ b/src/wasm/literal.cpp @@ -1435,8 +1435,7 @@ Literal Literal::shuffleV8x16(const Literal& other, return Literal(bytes); } -template<Type::ValueType Ty, int Lanes> -static Literal splat(const Literal& val) { +template<Type::BasicID Ty, int Lanes> static Literal splat(const Literal& val) { assert(val.type == Ty); LaneArray<Lanes> lanes; lanes.fill(val); diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp index 0f7647b72..ae10687fb 100644 --- a/src/wasm/wasm-binary.cpp +++ b/src/wasm/wasm-binary.cpp @@ -1793,7 +1793,7 @@ void WasmBinaryBuilder::skipUnreachableCode() { } void WasmBinaryBuilder::pushExpression(Expression* curr) { - if (curr->type.isMulti()) { + if (curr->type.isTuple()) { // Store tuple to local and push individual extracted values Builder builder(wasm); Index tuple = builder.addVar(currFunction, curr->type); @@ -1822,7 +1822,7 @@ Expression* WasmBinaryBuilder::popExpression() { } // the stack is not empty, and we would not be going out of the current block auto ret = expressionStack.back(); - assert(!ret->type.isMulti()); + assert(!ret->type.isTuple()); expressionStack.pop_back(); return ret; } @@ -1885,7 +1885,7 @@ Expression* WasmBinaryBuilder::popTuple(size_t numElems) { Expression* WasmBinaryBuilder::popTypedExpression(Type type) { if (type.isSingle()) { return popNonVoidExpression(); - } else if (type.isMulti()) { + } else if (type.isTuple()) { return popTuple(type.size()); } else { WASM_UNREACHABLE("Invalid popped type"); diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp index eedac4e95..88f90378c 100644 --- a/src/wasm/wasm-stack.cpp +++ b/src/wasm/wasm-stack.cpp @@ -23,7 +23,7 @@ namespace wasm { void BinaryInstWriter::emitResultType(Type type) { if (type == Type::unreachable) { o << binaryType(Type::none); - } else if (type.isMulti()) { + } else if (type.isTuple()) { o << S32LEB(parent.getTypeIndex(Signature(Type::none, type))); } else { o << binaryType(type); diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp index 8e6903642..5247ebb6f 100644 --- a/src/wasm/wasm-type.cpp +++ b/src/wasm/wasm-type.cpp @@ -25,29 +25,215 @@ #include "wasm-features.h" #include "wasm-type.h" +namespace wasm { + +struct TypeInfo { + enum Kind { TupleKind, SignatureRefKind, StructRefKind, ArrayRefKind } kind; + struct SignatureRef { + Signature signature; + bool nullable; + }; + struct StructRef { + Struct struct_; + bool nullable; + }; + struct ArrayRef { + Array array; + bool nullable; + }; + union { + Tuple tuple; + SignatureRef signatureRef; + StructRef structRef; + ArrayRef arrayRef; + }; + + TypeInfo(const Tuple& tuple) : kind(TupleKind), tuple(tuple) {} + TypeInfo(Tuple&& tuple) : kind(TupleKind), tuple(std::move(tuple)) {} + TypeInfo(const Signature& signature, bool nullable) + : kind(SignatureRefKind), signatureRef{signature, nullable} {} + TypeInfo(const Struct& struct_, bool nullable) + : kind(StructRefKind), structRef{struct_, nullable} {} + TypeInfo(const Array& array, bool nullable) + : kind(ArrayRefKind), arrayRef{array, nullable} {} + TypeInfo(const TypeInfo& other) { + kind = other.kind; + switch (kind) { + case TupleKind: + new (&tuple) auto(other.tuple); + return; + case SignatureRefKind: + new (&signatureRef) auto(other.signatureRef); + return; + case StructRefKind: + new (&structRef) auto(other.structRef); + return; + case ArrayRefKind: + new (&arrayRef) auto(other.arrayRef); + return; + } + WASM_UNREACHABLE("unexpected kind"); + } + ~TypeInfo() { + switch (kind) { + case TupleKind: { + tuple.~Tuple(); + return; + } + case SignatureRefKind: { + signatureRef.~SignatureRef(); + return; + } + case StructRefKind: { + structRef.~StructRef(); + return; + } + case ArrayRefKind: { + arrayRef.~ArrayRef(); + return; + } + } + WASM_UNREACHABLE("unexpected kind"); + } + + constexpr bool isTuple() const { return kind == TupleKind; } + constexpr bool isSignatureRef() const { return kind == SignatureRefKind; } + constexpr bool isStructRef() const { return kind == StructRefKind; } + constexpr bool isArrayRef() const { return kind == ArrayRefKind; } + + bool isNullable() const { + switch (kind) { + case TupleKind: + return false; + case SignatureRefKind: + return signatureRef.nullable; + case StructRefKind: + return structRef.nullable; + case ArrayRefKind: + return arrayRef.nullable; + } + WASM_UNREACHABLE("unexpected kind"); + } + + bool operator==(const TypeInfo& other) const { + if (kind != other.kind) { + return false; + } + switch (kind) { + case TupleKind: + return tuple == other.tuple; + case SignatureRefKind: + return signatureRef.nullable == other.signatureRef.nullable && + signatureRef.signature == other.signatureRef.signature; + case StructRefKind: + return structRef.nullable == other.structRef.nullable && + structRef.struct_ == other.structRef.struct_; + case ArrayRefKind: + return arrayRef.nullable == other.arrayRef.nullable && + arrayRef.array == other.arrayRef.array; + } + WASM_UNREACHABLE("unexpected kind"); + } + bool operator!=(const TypeInfo& other) const { return !(*this == other); } + TypeInfo& operator=(const TypeInfo& other) { + if (&other != this) { + this->~TypeInfo(); + new (this) auto(other); + } + return *this; + } + + std::string toString() const; +}; + +std::ostream& operator<<(std::ostream&, TypeInfo); + +} // namespace wasm + namespace std { -template<> class hash<vector<wasm::Type>> { +template<> class hash<wasm::TypeList> { public: - size_t operator()(const vector<wasm::Type>& types) const { + size_t operator()(const wasm::TypeList& types) const { auto digest = wasm::hash(types.size()); - for (auto t : types) { - wasm::rehash(digest, t.getID()); + for (auto type : types) { + wasm::rehash(digest, type); } return digest; } }; +template<> class hash<wasm::FieldList> { +public: + size_t operator()(const wasm::FieldList& fields) const { + auto digest = wasm::hash(fields.size()); + for (auto field : fields) { + wasm::rehash(digest, field); + } + return digest; + } +}; + +template<> class hash<wasm::TypeInfo> { +public: + size_t operator()(const wasm::TypeInfo& info) const { + auto digest = wasm::hash(info.kind); + switch (info.kind) { + case wasm::TypeInfo::TupleKind: { + wasm::rehash(digest, info.tuple.types); + return digest; + } + case wasm::TypeInfo::SignatureRefKind: { + wasm::rehash(digest, info.signatureRef.signature); + wasm::rehash(digest, info.signatureRef.nullable); + return digest; + } + case wasm::TypeInfo::StructRefKind: { + wasm::rehash(digest, info.structRef.struct_); + wasm::rehash(digest, info.structRef.nullable); + return digest; + } + case wasm::TypeInfo::ArrayRefKind: { + wasm::rehash(digest, info.arrayRef.array); + wasm::rehash(digest, info.arrayRef.nullable); + return digest; + } + } + WASM_UNREACHABLE("unexpected kind"); + } +}; + size_t hash<wasm::Type>::operator()(const wasm::Type& type) const { return wasm::hash(type.getID()); } +size_t hash<wasm::Tuple>::operator()(const wasm::Tuple& tuple) const { + return wasm::hash(tuple.types); +} + size_t hash<wasm::Signature>::operator()(const wasm::Signature& sig) const { - auto digest = wasm::hash(sig.params.getID()); - wasm::rehash(digest, sig.results.getID()); + auto digest = wasm::hash(sig.params); + wasm::rehash(digest, sig.results); + return digest; +} + +size_t hash<wasm::Field>::operator()(const wasm::Field& field) const { + auto digest = wasm::hash(field.type); + wasm::rehash(digest, field.packedType); + wasm::rehash(digest, field.mutable_); return digest; } +size_t hash<wasm::Struct>::operator()(const wasm::Struct& struct_) const { + auto digest = wasm::hash(0); + wasm::rehash(digest, struct_.fields); + return digest; +} + +size_t hash<wasm::Array>::operator()(const wasm::Array& array) const { + return wasm::hash(array.element); +} + } // namespace std namespace wasm { @@ -57,32 +243,58 @@ namespace { std::mutex mutex; // Track unique_ptrs for constructed types to avoid leaks -std::vector<std::unique_ptr<std::vector<Type>>> constructedTypes; - -// Maps from type vectors to the canonical Type ID -std::unordered_map<std::vector<Type>, uintptr_t> indices = { - {{}, Type::none}, - {{Type::unreachable}, Type::unreachable}, - {{Type::i32}, Type::i32}, - {{Type::i64}, Type::i64}, - {{Type::f32}, Type::f32}, - {{Type::f64}, Type::f64}, - {{Type::v128}, Type::v128}, - {{Type::funcref}, Type::funcref}, - {{Type::externref}, Type::externref}, - {{Type::nullref}, Type::nullref}, - {{Type::exnref}, Type::exnref}, +std::vector<std::unique_ptr<TypeInfo>> constructedTypes; + +// Maps from constructed types to the canonical Type ID. +std::unordered_map<TypeInfo, uintptr_t> indices = { + // If a Type is constructed from a list of types, the list of types becomes + // implicitly converted to a TypeInfo before canonicalizing its id. This is + // also the case if a list of just one type is provided, even though such a + // list of types will be canonicalized to the BasicID of the single type. As + // such, the following entries are solely placeholders to enable the lookup + // of lists of just one type to the BasicID of the single type. + {TypeInfo(Tuple()), Type::none}, + {TypeInfo({Type::unreachable}), Type::unreachable}, + {TypeInfo({Type::i32}), Type::i32}, + {TypeInfo({Type::i64}), Type::i64}, + {TypeInfo({Type::f32}), Type::f32}, + {TypeInfo({Type::f64}), Type::f64}, + {TypeInfo({Type::v128}), Type::v128}, + {TypeInfo({Type::funcref}), Type::funcref}, + {TypeInfo({Type::externref}), Type::externref}, + {TypeInfo({Type::nullref}), Type::nullref}, + {TypeInfo({Type::exnref}), Type::exnref}, }; } // anonymous namespace -void Type::init(const std::vector<Type>& types) { +static uintptr_t canonicalize(const TypeInfo& info) { + std::lock_guard<std::mutex> lock(mutex); + auto indexIt = indices.find(info); + if (indexIt != indices.end()) { + return indexIt->second; + } + auto ptr = std::make_unique<TypeInfo>(info); + auto id = uintptr_t(ptr.get()); + constructedTypes.push_back(std::move(ptr)); + assert(id > Type::_last_basic_id); + indices[info] = id; + return id; +} + +static TypeInfo* getTypeInfo(const Type& type) { + return (TypeInfo*)type.getID(); +} + +Type::Type(std::initializer_list<Type> types) : Type(Tuple(types)) {} + +Type::Type(const Tuple& tuple) { + auto& types = tuple.types; #ifndef NDEBUG for (Type t : types) { - assert(!t.isMulti() && t.isConcrete()); + assert(t.isSingle()); } #endif - if (types.size() == 0) { id = none; return; @@ -91,28 +303,62 @@ void Type::init(const std::vector<Type>& types) { *this = types[0]; return; } + id = canonicalize(TypeInfo(tuple)); +} - // Add a new type if it hasn't been added concurrently - std::lock_guard<std::mutex> lock(mutex); - auto indexIt = indices.find(types); - if (indexIt != indices.end()) { - id = indexIt->second; +Type::Type(const Signature signature, bool nullable) { + id = canonicalize(TypeInfo(signature, nullable)); +} + +Type::Type(const Struct& struct_, bool nullable) { +#ifndef NDEBUG + for (Field f : struct_.fields) { + assert(f.type.isSingle()); + } +#endif + id = canonicalize(TypeInfo(struct_, nullable)); +} + +Type::Type(const Array& array, bool nullable) { + assert(array.element.type.isSingle()); + id = canonicalize(TypeInfo(array, nullable)); +} + +bool Type::isTuple() const { + if (isBasic()) { + return false; } else { - auto vec = std::make_unique<std::vector<Type>>(types); - id = uintptr_t(vec.get()); - constructedTypes.push_back(std::move(vec)); - assert(id > _last_value_type); - indices[types] = id; + return getTypeInfo(*this)->isTuple(); } } -Type::Type(std::initializer_list<Type> types) { init(types); } +bool Type::isRef() const { + if (isBasic()) { + return id >= funcref && id <= exnref; + } else { + switch (getTypeInfo(*this)->kind) { + case TypeInfo::TupleKind: + return false; + case TypeInfo::SignatureRefKind: + case TypeInfo::StructRefKind: + case TypeInfo::ArrayRefKind: + return true; + } + WASM_UNREACHABLE("unexpected kind"); + } +} -Type::Type(const std::vector<Type>& types) { init(types); } +bool Type::isNullable() const { + if (isBasic()) { + return id >= funcref && id <= exnref; + } else { + return getTypeInfo(*this)->isNullable(); + } +} bool Type::operator<(const Type& other) const { - return std::lexicographical_compare((*this).begin(), - (*this).end(), + return std::lexicographical_compare(begin(), + end(), other.begin(), other.end(), [](const Type& a, const Type& b) { @@ -145,7 +391,7 @@ unsigned Type::getByteSize() const { WASM_UNREACHABLE("invalid type"); }; - if (isMulti()) { + if (isTuple()) { unsigned size = 0; for (const auto& t : *this) { size += getSingleByteSize(t); @@ -156,8 +402,8 @@ unsigned Type::getByteSize() const { } Type Type::reinterpret() const { - auto singleType = *(*this).begin(); - switch (singleType.getBasic()) { + assert(!isTuple() && "Unexpected tuple type"); + switch ((*begin()).getBasic()) { case Type::i32: return f32; case Type::i64: @@ -166,16 +412,9 @@ Type Type::reinterpret() const { return i32; case Type::f64: return i64; - case Type::v128: - case Type::funcref: - case Type::externref: - case Type::nullref: - case Type::exnref: - case Type::none: - case Type::unreachable: + default: WASM_UNREACHABLE("invalid type"); } - WASM_UNREACHABLE("invalid type"); } FeatureSet Type::getFeatures() const { @@ -195,7 +434,7 @@ FeatureSet Type::getFeatures() const { } }; - if (isMulti()) { + if (isTuple()) { FeatureSet feats = FeatureSet::Multivalue; for (const auto& t : *this) { feats |= getSingleFeatures(t); @@ -229,7 +468,7 @@ bool Type::isSubType(Type left, Type right) { (right == Type::externref || left == Type::nullref)) { return true; } - if (left.isMulti() && right.isMulti()) { + if (left.isTuple() && right.isTuple()) { if (left.size() != right.size()) { return false; } @@ -256,8 +495,8 @@ Type Type::getLeastUpperBound(Type a, Type b) { if (a.size() != b.size()) { return Type::none; // a poison value that must not be consumed } - if (a.isMulti()) { - std::vector<Type> types; + if (a.isTuple()) { + TypeList types; types.resize(a.size()); for (size_t i = 0; i < types.size(); ++i) { types[i] = getLeastUpperBound(a[i], b[i]); @@ -279,6 +518,35 @@ Type Type::getLeastUpperBound(Type a, Type b) { return Type::externref; } +Type::Iterator Type::end() const { + if (isTuple()) { + return Iterator(this, getTypeInfo(*this)->tuple.types.size()); + } else { + // TODO: unreachable is special and expands to {unreachable} currently. + // see also: https://github.com/WebAssembly/binaryen/issues/3062 + return Iterator(this, size_t(id != Type::none)); + } +} + +const Type& Type::Iterator::operator*() const { + if (parent->isTuple()) { + return getTypeInfo(*parent)->tuple.types[index]; + } else { + // TODO: see comment in Type::end() + assert(index == 0 && parent->id != Type::none && "Index out of bounds"); + return *parent; + } +} + +const Type& Type::operator[](size_t index) const { + if (isTuple()) { + return getTypeInfo(*this)->tuple.types[index]; + } else { + assert(index == 0 && "Index out of bounds"); + return *begin(); + } +} + namespace { std::ostream& @@ -305,6 +573,16 @@ std::string ParamType::toString() const { return genericToString(*this); } std::string ResultType::toString() const { return genericToString(*this); } +std::string Tuple::toString() const { return genericToString(*this); } + +std::string Signature::toString() const { return genericToString(*this); } + +std::string Struct::toString() const { return genericToString(*this); } + +std::string Array::toString() const { return genericToString(*this); } + +std::string TypeInfo::toString() const { return genericToString(*this); } + bool Signature::operator<(const Signature& other) const { if (results < other.results) { return true; @@ -316,16 +594,7 @@ bool Signature::operator<(const Signature& other) const { } std::ostream& operator<<(std::ostream& os, Type type) { - if (type.isMulti()) { - os << '('; - auto sep = ""; - for (const auto& t : type) { - os << sep << t; - sep = ", "; - } - os << ')'; - } else { - TODO_SINGLE_COMPOUND(type); + if (type.isBasic()) { switch (type.getBasic()) { case Type::none: os << "none"; @@ -361,6 +630,8 @@ std::ostream& operator<<(std::ostream& os, Type type) { os << "exnref"; break; } + } else { + os << *getTypeInfo(type); } return os; } @@ -373,8 +644,98 @@ std::ostream& operator<<(std::ostream& os, ResultType param) { return printPrefixedTypes(os, "result", param.type); } +std::ostream& operator<<(std::ostream& os, Tuple tuple) { + auto& types = tuple.types; + auto size = types.size(); + os << "("; + if (size) { + os << types[0]; + for (size_t i = 1; i < size; ++i) { + os << " " << types[i]; + } + } + return os << ")"; +} + std::ostream& operator<<(std::ostream& os, Signature sig) { - return os << "Signature(" << sig.params << " => " << sig.results << ")"; + os << "(func"; + if (sig.params.getID() != Type::none) { + os << " "; + printPrefixedTypes(os, "param", sig.params); + } + if (sig.results.getID() != Type::none) { + os << " "; + printPrefixedTypes(os, "result", sig.results); + } + return os << ")"; +} + +std::ostream& operator<<(std::ostream& os, Field field) { + if (field.mutable_) { + os << "(mut "; + } + if (field.isPacked()) { + auto packedType = field.packedType; + if (packedType == Field::PackedType::i8) { + os << "i8"; + } else if (packedType == Field::PackedType::i16) { + os << "i16"; + } else { + WASM_UNREACHABLE("unexpected packed type"); + } + } else { + os << field.type; + } + if (field.mutable_) { + os << ")"; + } + return os; +}; + +std::ostream& operator<<(std::ostream& os, Struct struct_) { + os << "(struct"; + if (struct_.fields.size()) { + os << " (field"; + for (auto f : struct_.fields) { + os << " " << f; + } + os << ")"; + } + return os << ")"; +} + +std::ostream& operator<<(std::ostream& os, Array array) { + return os << "(array " << array.element << ")"; +} + +std::ostream& operator<<(std::ostream& os, TypeInfo info) { + switch (info.kind) { + case TypeInfo::TupleKind: { + return os << info.tuple; + } + case TypeInfo::SignatureRefKind: { + os << "(ref "; + if (info.signatureRef.nullable) { + os << "null "; + } + return os << info.signatureRef.signature << ")"; + } + case TypeInfo::StructRefKind: { + os << "(ref "; + if (info.structRef.nullable) { + os << "null "; + } + return os << info.structRef.struct_ << ")"; + } + case TypeInfo::ArrayRefKind: { + os << "(ref "; + if (info.arrayRef.nullable) { + os << "null "; + } + return os << info.arrayRef.array << ")"; + } + } + WASM_UNREACHABLE("unexpected kind"); } } // namespace wasm diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp index 6e7ef3301..8410cc0b2 100644 --- a/src/wasm/wasm-validator.cpp +++ b/src/wasm/wasm-validator.cpp @@ -389,7 +389,7 @@ void FunctionValidator::noteLabelName(Name name) { void FunctionValidator::visitBlock(Block* curr) { if (!getModule()->features.hasMultivalue()) { - shouldBeTrue(!curr->type.isMulti(), + shouldBeTrue(!curr->type.isTuple(), curr, "Multivalue block type (multivalue is not enabled)"); } @@ -1773,11 +1773,11 @@ void FunctionValidator::visitSelect(Select* curr) { "select condition must be valid"); if (curr->ifTrue->type != Type::unreachable) { shouldBeFalse( - curr->ifTrue->type.isMulti(), curr, "select value may not be a tuple"); + curr->ifTrue->type.isTuple(), curr, "select value may not be a tuple"); } if (curr->ifFalse->type != Type::unreachable) { shouldBeFalse( - curr->ifFalse->type.isMulti(), curr, "select value may not be a tuple"); + curr->ifFalse->type.isTuple(), curr, "select value may not be a tuple"); } if (curr->type != Type::unreachable) { shouldBeTrue(Type::isSubType(curr->ifTrue->type, curr->type), @@ -1969,7 +1969,7 @@ void FunctionValidator::visitTupleExtract(TupleExtract* curr) { } void FunctionValidator::visitFunction(Function* curr) { - if (curr->sig.results.isMulti()) { + if (curr->sig.results.isTuple()) { shouldBeTrue(getModule()->features.hasMultivalue(), curr->body, "Multivalue function results (multivalue is not enabled)"); @@ -2137,7 +2137,7 @@ static void validateBinaryenIR(Module& wasm, ValidationInfo& info) { static void validateImports(Module& module, ValidationInfo& info) { ModuleUtils::iterImportedFunctions(module, [&](Function* curr) { - if (curr->sig.results.isMulti()) { + if (curr->sig.results.isTuple()) { info.shouldBeTrue(module.features.hasMultivalue(), curr->name, "Imported multivalue function " @@ -2164,7 +2164,7 @@ static void validateImports(Module& module, ValidationInfo& info) { curr->mutable_, curr->name, "Imported global cannot be mutable"); } info.shouldBeFalse( - curr->type.isMulti(), curr->name, "Imported global cannot be tuple"); + curr->type.isTuple(), curr->name, "Imported global cannot be tuple"); }); } @@ -2194,7 +2194,7 @@ static void validateExports(Module& module, ValidationInfo& info) { g->mutable_, g->name, "Exported global cannot be mutable"); } info.shouldBeFalse( - g->type.isMulti(), g->name, "Exported global cannot be tuple"); + g->type.isTuple(), g->name, "Exported global cannot be tuple"); } } } @@ -2347,7 +2347,7 @@ static void validateEvents(Module& module, ValidationInfo& info) { Type(Type::none), curr->name, "Event type's result type should be none"); - if (curr->sig.params.isMulti()) { + if (curr->sig.params.isTuple()) { info.shouldBeTrue(module.features.hasMultivalue(), curr->name, "Multivalue event type (multivalue is not enabled)"); |