blob: 12ff1393408b3cd2e13386b400da9669dde5a4c0 [file] [log] [blame]
// Copyright (c) 2016 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "source/opt/types.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <sstream>
#include <string>
#include <unordered_set>
#include "source/util/hash_combine.h"
#include "source/util/make_unique.h"
namespace spvtools {
namespace opt {
namespace analysis {
using spvtools::utils::hash_combine;
using U32VecVec = std::vector<std::vector<uint32_t>>;
namespace {
// Returns true if the two vector of vectors are identical.
bool CompareTwoVectors(const U32VecVec a, const U32VecVec b) {
const auto size = a.size();
if (size != b.size()) return false;
if (size == 0) return true;
if (size == 1) return a.front() == b.front();
std::vector<const std::vector<uint32_t>*> a_ptrs, b_ptrs;
a_ptrs.reserve(size);
a_ptrs.reserve(size);
for (uint32_t i = 0; i < size; ++i) {
a_ptrs.push_back(&a[i]);
b_ptrs.push_back(&b[i]);
}
const auto cmp = [](const std::vector<uint32_t>* m,
const std::vector<uint32_t>* n) {
return m->front() < n->front();
};
std::sort(a_ptrs.begin(), a_ptrs.end(), cmp);
std::sort(b_ptrs.begin(), b_ptrs.end(), cmp);
for (uint32_t i = 0; i < size; ++i) {
if (*a_ptrs[i] != *b_ptrs[i]) return false;
}
return true;
}
} // namespace
std::string Type::GetDecorationStr() const {
std::ostringstream oss;
oss << "[[";
for (const auto& decoration : decorations_) {
oss << "(";
for (size_t i = 0; i < decoration.size(); ++i) {
oss << (i > 0 ? ", " : "");
oss << decoration.at(i);
}
oss << ")";
}
oss << "]]";
return oss.str();
}
bool Type::HasSameDecorations(const Type* that) const {
return CompareTwoVectors(decorations_, that->decorations_);
}
bool Type::IsUniqueType(bool allowVariablePointers) const {
switch (kind_) {
case kPointer:
return !allowVariablePointers;
case kStruct:
case kArray:
case kRuntimeArray:
return false;
default:
return true;
}
}
std::unique_ptr<Type> Type::Clone() const {
std::unique_ptr<Type> type;
switch (kind_) {
#define DeclareKindCase(kind) \
case k##kind: \
type = MakeUnique<kind>(*this->As##kind()); \
break
DeclareKindCase(Void);
DeclareKindCase(Bool);
DeclareKindCase(Integer);
DeclareKindCase(Float);
DeclareKindCase(Vector);
DeclareKindCase(Matrix);
DeclareKindCase(Image);
DeclareKindCase(Sampler);
DeclareKindCase(SampledImage);
DeclareKindCase(Array);
DeclareKindCase(RuntimeArray);
DeclareKindCase(Struct);
DeclareKindCase(Opaque);
DeclareKindCase(Pointer);
DeclareKindCase(Function);
DeclareKindCase(Event);
DeclareKindCase(DeviceEvent);
DeclareKindCase(ReserveId);
DeclareKindCase(Queue);
DeclareKindCase(Pipe);
DeclareKindCase(ForwardPointer);
DeclareKindCase(PipeStorage);
DeclareKindCase(NamedBarrier);
DeclareKindCase(AccelerationStructureNV);
DeclareKindCase(CooperativeMatrixNV);
DeclareKindCase(RayQueryKHR);
#undef DeclareKindCase
default:
assert(false && "Unhandled type");
}
return type;
}
std::unique_ptr<Type> Type::RemoveDecorations() const {
std::unique_ptr<Type> type(Clone());
type->ClearDecorations();
return type;
}
bool Type::operator==(const Type& other) const {
if (kind_ != other.kind_) return false;
switch (kind_) {
#define DeclareKindCase(kind) \
case k##kind: \
return As##kind()->IsSame(&other)
DeclareKindCase(Void);
DeclareKindCase(Bool);
DeclareKindCase(Integer);
DeclareKindCase(Float);
DeclareKindCase(Vector);
DeclareKindCase(Matrix);
DeclareKindCase(Image);
DeclareKindCase(Sampler);
DeclareKindCase(SampledImage);
DeclareKindCase(Array);
DeclareKindCase(RuntimeArray);
DeclareKindCase(Struct);
DeclareKindCase(Opaque);
DeclareKindCase(Pointer);
DeclareKindCase(Function);
DeclareKindCase(Event);
DeclareKindCase(DeviceEvent);
DeclareKindCase(ReserveId);
DeclareKindCase(Queue);
DeclareKindCase(Pipe);
DeclareKindCase(ForwardPointer);
DeclareKindCase(PipeStorage);
DeclareKindCase(NamedBarrier);
DeclareKindCase(AccelerationStructureNV);
DeclareKindCase(CooperativeMatrixNV);
DeclareKindCase(RayQueryKHR);
#undef DeclareKindCase
default:
assert(false && "Unhandled type");
return false;
}
}
size_t Type::ComputeHashValue(size_t hash, SeenTypes* seen) const {
// Linear search through a dense, cache coherent vector is faster than O(log
// n) search in a complex data structure (eg std::set) for the generally small
// number of nodes. It also skips the overhead of an new/delete per Type
// (when inserting/removing from a set).
if (std::find(seen->begin(), seen->end(), this) != seen->end()) {
return hash;
}
seen->push_back(this);
hash = hash_combine(hash, uint32_t(kind_));
for (const auto& d : decorations_) {
hash = hash_combine(hash, d);
}
switch (kind_) {
#define DeclareKindCase(type) \
case k##type: \
hash = As##type()->ComputeExtraStateHash(hash, seen); \
break
DeclareKindCase(Void);
DeclareKindCase(Bool);
DeclareKindCase(Integer);
DeclareKindCase(Float);
DeclareKindCase(Vector);
DeclareKindCase(Matrix);
DeclareKindCase(Image);
DeclareKindCase(Sampler);
DeclareKindCase(SampledImage);
DeclareKindCase(Array);
DeclareKindCase(RuntimeArray);
DeclareKindCase(Struct);
DeclareKindCase(Opaque);
DeclareKindCase(Pointer);
DeclareKindCase(Function);
DeclareKindCase(Event);
DeclareKindCase(DeviceEvent);
DeclareKindCase(ReserveId);
DeclareKindCase(Queue);
DeclareKindCase(Pipe);
DeclareKindCase(ForwardPointer);
DeclareKindCase(PipeStorage);
DeclareKindCase(NamedBarrier);
DeclareKindCase(AccelerationStructureNV);
DeclareKindCase(CooperativeMatrixNV);
DeclareKindCase(RayQueryKHR);
#undef DeclareKindCase
default:
assert(false && "Unhandled type");
break;
}
seen->pop_back();
return hash;
}
size_t Type::HashValue() const {
SeenTypes seen;
return ComputeHashValue(0, &seen);
}
uint64_t Type::NumberOfComponents() const {
switch (kind()) {
case kVector:
return AsVector()->element_count();
case kMatrix:
return AsMatrix()->element_count();
case kArray: {
Array::LengthInfo length_info = AsArray()->length_info();
if (length_info.words[0] != Array::LengthInfo::kConstant) {
return UINT64_MAX;
}
assert(length_info.words.size() <= 3 &&
"The size of the array could not fit size_t.");
uint64_t length = 0;
length |= length_info.words[1];
if (length_info.words.size() > 2) {
length |= static_cast<uint64_t>(length_info.words[2]) << 32;
}
return length;
}
case kRuntimeArray:
return UINT64_MAX;
case kStruct:
return AsStruct()->element_types().size();
default:
return 0;
}
}
bool Integer::IsSameImpl(const Type* that, IsSameCache*) const {
const Integer* it = that->AsInteger();
return it && width_ == it->width_ && signed_ == it->signed_ &&
HasSameDecorations(that);
}
std::string Integer::str() const {
std::ostringstream oss;
oss << (signed_ ? "s" : "u") << "int" << width_;
return oss.str();
}
size_t Integer::ComputeExtraStateHash(size_t hash, SeenTypes*) const {
return hash_combine(hash, width_, signed_);
}
bool Float::IsSameImpl(const Type* that, IsSameCache*) const {
const Float* ft = that->AsFloat();
return ft && width_ == ft->width_ && HasSameDecorations(that);
}
std::string Float::str() const {
std::ostringstream oss;
oss << "float" << width_;
return oss.str();
}
size_t Float::ComputeExtraStateHash(size_t hash, SeenTypes*) const {
return hash_combine(hash, width_);
}
Vector::Vector(const Type* type, uint32_t count)
: Type(kVector), element_type_(type), count_(count) {
assert(type->AsBool() || type->AsInteger() || type->AsFloat());
}
bool Vector::IsSameImpl(const Type* that, IsSameCache* seen) const {
const Vector* vt = that->AsVector();
if (!vt) return false;
return count_ == vt->count_ &&
element_type_->IsSameImpl(vt->element_type_, seen) &&
HasSameDecorations(that);
}
std::string Vector::str() const {
std::ostringstream oss;
oss << "<" << element_type_->str() << ", " << count_ << ">";
return oss.str();
}
size_t Vector::ComputeExtraStateHash(size_t hash, SeenTypes* seen) const {
// prefer form that doesn't require push/pop from stack: add state and
// make tail call.
hash = hash_combine(hash, count_);
return element_type_->ComputeHashValue(hash, seen);
}
Matrix::Matrix(const Type* type, uint32_t count)
: Type(kMatrix), element_type_(type), count_(count) {
assert(type->AsVector());
}
bool Matrix::IsSameImpl(const Type* that, IsSameCache* seen) const {
const Matrix* mt = that->AsMatrix();
if (!mt) return false;
return count_ == mt->count_ &&
element_type_->IsSameImpl(mt->element_type_, seen) &&
HasSameDecorations(that);
}
std::string Matrix::str() const {
std::ostringstream oss;
oss << "<" << element_type_->str() << ", " << count_ << ">";
return oss.str();
}
size_t Matrix::ComputeExtraStateHash(size_t hash, SeenTypes* seen) const {
hash = hash_combine(hash, count_);
return element_type_->ComputeHashValue(hash, seen);
}
Image::Image(Type* type, spv::Dim dimen, uint32_t d, bool array,
bool multisample, uint32_t sampling, spv::ImageFormat f,
spv::AccessQualifier qualifier)
: Type(kImage),
sampled_type_(type),
dim_(dimen),
depth_(d),
arrayed_(array),
ms_(multisample),
sampled_(sampling),
format_(f),
access_qualifier_(qualifier) {
// TODO(antiagainst): check sampled_type
}
bool Image::IsSameImpl(const Type* that, IsSameCache* seen) const {
const Image* it = that->AsImage();
if (!it) return false;
return dim_ == it->dim_ && depth_ == it->depth_ && arrayed_ == it->arrayed_ &&
ms_ == it->ms_ && sampled_ == it->sampled_ && format_ == it->format_ &&
access_qualifier_ == it->access_qualifier_ &&
sampled_type_->IsSameImpl(it->sampled_type_, seen) &&
HasSameDecorations(that);
}
std::string Image::str() const {
std::ostringstream oss;
oss << "image(" << sampled_type_->str() << ", " << uint32_t(dim_) << ", "
<< depth_ << ", " << arrayed_ << ", " << ms_ << ", " << sampled_ << ", "
<< uint32_t(format_) << ", " << uint32_t(access_qualifier_) << ")";
return oss.str();
}
size_t Image::ComputeExtraStateHash(size_t hash, SeenTypes* seen) const {
hash = hash_combine(hash, uint32_t(dim_), depth_, arrayed_, ms_, sampled_,
uint32_t(format_), uint32_t(access_qualifier_));
return sampled_type_->ComputeHashValue(hash, seen);
}
bool SampledImage::IsSameImpl(const Type* that, IsSameCache* seen) const {
const SampledImage* sit = that->AsSampledImage();
if (!sit) return false;
return image_type_->IsSameImpl(sit->image_type_, seen) &&
HasSameDecorations(that);
}
std::string SampledImage::str() const {
std::ostringstream oss;
oss << "sampled_image(" << image_type_->str() << ")";
return oss.str();
}
size_t SampledImage::ComputeExtraStateHash(size_t hash, SeenTypes* seen) const {
return image_type_->ComputeHashValue(hash, seen);
}
Array::Array(const Type* type, const Array::LengthInfo& length_info_arg)
: Type(kArray), element_type_(type), length_info_(length_info_arg) {
assert(type != nullptr);
assert(!type->AsVoid());
// We always have a word to say which case we're in, followed
// by at least one more word.
assert(length_info_arg.words.size() >= 2);
}
bool Array::IsSameImpl(const Type* that, IsSameCache* seen) const {
const Array* at = that->AsArray();
if (!at) return false;
bool is_same = element_type_->IsSameImpl(at->element_type_, seen);
is_same = is_same && HasSameDecorations(that);
is_same = is_same && (length_info_.words == at->length_info_.words);
return is_same;
}
std::string Array::str() const {
std::ostringstream oss;
oss << "[" << element_type_->str() << ", id(" << LengthId() << "), words(";
const char* spacer = "";
for (auto w : length_info_.words) {
oss << spacer << w;
spacer = ",";
}
oss << ")]";
return oss.str();
}
size_t Array::ComputeExtraStateHash(size_t hash, SeenTypes* seen) const {
hash = hash_combine(hash, length_info_.words);
return element_type_->ComputeHashValue(hash, seen);
}
void Array::ReplaceElementType(const Type* type) { element_type_ = type; }
Array::LengthInfo Array::GetConstantLengthInfo(uint32_t const_id,
uint32_t length) const {
std::vector<uint32_t> extra_words{LengthInfo::Case::kConstant, length};
return {const_id, extra_words};
}
RuntimeArray::RuntimeArray(const Type* type)
: Type(kRuntimeArray), element_type_(type) {
assert(!type->AsVoid());
}
bool RuntimeArray::IsSameImpl(const Type* that, IsSameCache* seen) const {
const RuntimeArray* rat = that->AsRuntimeArray();
if (!rat) return false;
return element_type_->IsSameImpl(rat->element_type_, seen) &&
HasSameDecorations(that);
}
std::string RuntimeArray::str() const {
std::ostringstream oss;
oss << "[" << element_type_->str() << "]";
return oss.str();
}
size_t RuntimeArray::ComputeExtraStateHash(size_t hash, SeenTypes* seen) const {
return element_type_->ComputeHashValue(hash, seen);
}
void RuntimeArray::ReplaceElementType(const Type* type) {
element_type_ = type;
}
Struct::Struct(const std::vector<const Type*>& types)
: Type(kStruct), element_types_(types) {
for (const auto* t : types) {
(void)t;
assert(!t->AsVoid());
}
}
void Struct::AddMemberDecoration(uint32_t index,
std::vector<uint32_t>&& decoration) {
if (index >= element_types_.size()) {
assert(0 && "index out of bound");
return;
}
element_decorations_[index].push_back(std::move(decoration));
}
bool Struct::IsSameImpl(const Type* that, IsSameCache* seen) const {
const Struct* st = that->AsStruct();
if (!st) return false;
if (element_types_.size() != st->element_types_.size()) return false;
const auto size = element_decorations_.size();
if (size != st->element_decorations_.size()) return false;
if (!HasSameDecorations(that)) return false;
for (size_t i = 0; i < element_types_.size(); ++i) {
if (!element_types_[i]->IsSameImpl(st->element_types_[i], seen))
return false;
}
for (const auto& p : element_decorations_) {
if (st->element_decorations_.count(p.first) == 0) return false;
if (!CompareTwoVectors(p.second, st->element_decorations_.at(p.first)))
return false;
}
return true;
}
std::string Struct::str() const {
std::ostringstream oss;
oss << "{";
const size_t count = element_types_.size();
for (size_t i = 0; i < count; ++i) {
oss << element_types_[i]->str();
if (i + 1 != count) oss << ", ";
}
oss << "}";
return oss.str();
}
size_t Struct::ComputeExtraStateHash(size_t hash, SeenTypes* seen) const {
for (auto* t : element_types_) {
hash = t->ComputeHashValue(hash, seen);
}
for (const auto& pair : element_decorations_) {
hash = hash_combine(hash, pair.first, pair.second);
}
return hash;
}
bool Opaque::IsSameImpl(const Type* that, IsSameCache*) const {
const Opaque* ot = that->AsOpaque();
if (!ot) return false;
return name_ == ot->name_ && HasSameDecorations(that);
}
std::string Opaque::str() const {
std::ostringstream oss;
oss << "opaque('" << name_ << "')";
return oss.str();
}
size_t Opaque::ComputeExtraStateHash(size_t hash, SeenTypes*) const {
return hash_combine(hash, name_);
}
Pointer::Pointer(const Type* type, spv::StorageClass sc)
: Type(kPointer), pointee_type_(type), storage_class_(sc) {}
bool Pointer::IsSameImpl(const Type* that, IsSameCache* seen) const {
const Pointer* pt = that->AsPointer();
if (!pt) return false;
if (storage_class_ != pt->storage_class_) return false;
auto p = seen->insert(std::make_pair(this, that->AsPointer()));
if (!p.second) {
return true;
}
bool same_pointee = pointee_type_->IsSameImpl(pt->pointee_type_, seen);
seen->erase(p.first);
if (!same_pointee) {
return false;
}
return HasSameDecorations(that);
}
std::string Pointer::str() const {
std::ostringstream os;
os << pointee_type_->str() << " " << static_cast<uint32_t>(storage_class_)
<< "*";
return os.str();
}
size_t Pointer::ComputeExtraStateHash(size_t hash, SeenTypes* seen) const {
hash = hash_combine(hash, uint32_t(storage_class_));
return pointee_type_->ComputeHashValue(hash, seen);
}
void Pointer::SetPointeeType(const Type* type) { pointee_type_ = type; }
Function::Function(const Type* ret_type, const std::vector<const Type*>& params)
: Type(kFunction), return_type_(ret_type), param_types_(params) {}
Function::Function(const Type* ret_type, std::vector<const Type*>& params)
: Type(kFunction), return_type_(ret_type), param_types_(params) {}
bool Function::IsSameImpl(const Type* that, IsSameCache* seen) const {
const Function* ft = that->AsFunction();
if (!ft) return false;
if (!return_type_->IsSameImpl(ft->return_type_, seen)) return false;
if (param_types_.size() != ft->param_types_.size()) return false;
for (size_t i = 0; i < param_types_.size(); ++i) {
if (!param_types_[i]->IsSameImpl(ft->param_types_[i], seen)) return false;
}
return HasSameDecorations(that);
}
std::string Function::str() const {
std::ostringstream oss;
const size_t count = param_types_.size();
oss << "(";
for (size_t i = 0; i < count; ++i) {
oss << param_types_[i]->str();
if (i + 1 != count) oss << ", ";
}
oss << ") -> " << return_type_->str();
return oss.str();
}
size_t Function::ComputeExtraStateHash(size_t hash, SeenTypes* seen) const {
for (const auto* t : param_types_) {
hash = t->ComputeHashValue(hash, seen);
}
return return_type_->ComputeHashValue(hash, seen);
}
void Function::SetReturnType(const Type* type) { return_type_ = type; }
bool Pipe::IsSameImpl(const Type* that, IsSameCache*) const {
const Pipe* pt = that->AsPipe();
if (!pt) return false;
return access_qualifier_ == pt->access_qualifier_ && HasSameDecorations(that);
}
std::string Pipe::str() const {
std::ostringstream oss;
oss << "pipe(" << uint32_t(access_qualifier_) << ")";
return oss.str();
}
size_t Pipe::ComputeExtraStateHash(size_t hash, SeenTypes*) const {
return hash_combine(hash, uint32_t(access_qualifier_));
}
bool ForwardPointer::IsSameImpl(const Type* that, IsSameCache*) const {
const ForwardPointer* fpt = that->AsForwardPointer();
if (!fpt) return false;
return (pointer_ && fpt->pointer_ ? *pointer_ == *fpt->pointer_
: target_id_ == fpt->target_id_) &&
storage_class_ == fpt->storage_class_ && HasSameDecorations(that);
}
std::string ForwardPointer::str() const {
std::ostringstream oss;
oss << "forward_pointer(";
if (pointer_ != nullptr) {
oss << pointer_->str();
} else {
oss << target_id_;
}
oss << ")";
return oss.str();
}
size_t ForwardPointer::ComputeExtraStateHash(size_t hash,
SeenTypes* seen) const {
hash = hash_combine(hash, target_id_, uint32_t(storage_class_));
if (pointer_) hash = pointer_->ComputeHashValue(hash, seen);
return hash;
}
CooperativeMatrixNV::CooperativeMatrixNV(const Type* type, const uint32_t scope,
const uint32_t rows,
const uint32_t columns)
: Type(kCooperativeMatrixNV),
component_type_(type),
scope_id_(scope),
rows_id_(rows),
columns_id_(columns) {
assert(type != nullptr);
assert(scope != 0);
assert(rows != 0);
assert(columns != 0);
}
std::string CooperativeMatrixNV::str() const {
std::ostringstream oss;
oss << "<" << component_type_->str() << ", " << scope_id_ << ", " << rows_id_
<< ", " << columns_id_ << ">";
return oss.str();
}
size_t CooperativeMatrixNV::ComputeExtraStateHash(size_t hash,
SeenTypes* seen) const {
hash = hash_combine(hash, scope_id_, rows_id_, columns_id_);
return component_type_->ComputeHashValue(hash, seen);
}
bool CooperativeMatrixNV::IsSameImpl(const Type* that,
IsSameCache* seen) const {
const CooperativeMatrixNV* mt = that->AsCooperativeMatrixNV();
if (!mt) return false;
return component_type_->IsSameImpl(mt->component_type_, seen) &&
scope_id_ == mt->scope_id_ && rows_id_ == mt->rows_id_ &&
columns_id_ == mt->columns_id_ && HasSameDecorations(that);
}
} // namespace analysis
} // namespace opt
} // namespace spvtools