1 // Copyright (c) 2016 Google Inc. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include <algorithm> 16 #include <cassert> 17 #include <sstream> 18 19 #include "types.h" 20 21 namespace spvtools { 22 namespace opt { 23 namespace analysis { 24 25 using U32VecVec = std::vector<std::vector<uint32_t>>; 26 27 namespace { 28 29 // Returns true if the two vector of vectors are identical. 30 bool CompareTwoVectors(const U32VecVec a, const U32VecVec b) { 31 const auto size = a.size(); 32 if (size != b.size()) return false; 33 34 if (size == 0) return true; 35 if (size == 1) return a.front() == b.front(); 36 37 std::vector<const std::vector<uint32_t>*> a_ptrs, b_ptrs; 38 a_ptrs.reserve(size); 39 a_ptrs.reserve(size); 40 for (uint32_t i = 0; i < size; ++i) { 41 a_ptrs.push_back(&a[i]); 42 b_ptrs.push_back(&b[i]); 43 } 44 45 const auto cmp = 46 [](const std::vector<uint32_t>* m, const std::vector<uint32_t>* n) { 47 return m->front() < n->front(); 48 }; 49 50 std::sort(a_ptrs.begin(), a_ptrs.end(), cmp); 51 std::sort(b_ptrs.begin(), b_ptrs.end(), cmp); 52 53 for (uint32_t i = 0; i < size; ++i) { 54 if (*a_ptrs[i] != *b_ptrs[i]) return false; 55 } 56 return true; 57 } 58 59 } // anonymous namespace 60 61 std::string Type::GetDecorationStr() const { 62 std::ostringstream oss; 63 oss << "[["; 64 for (const auto& decoration : decorations_) { 65 oss << "("; 66 for (size_t i = 0; i < decoration.size(); ++i) { 67 oss << (i > 0 ? ", " : ""); 68 oss << decoration.at(i); 69 } 70 oss << ")"; 71 } 72 oss << "]]"; 73 return oss.str(); 74 } 75 76 bool Type::HasSameDecorations(const Type* that) const { 77 return CompareTwoVectors(decorations_, that->decorations_); 78 } 79 80 bool Integer::IsSame(Type* that) const { 81 const Integer* it = that->AsInteger(); 82 return it && width_ == it->width_ && signed_ == it->signed_ && 83 HasSameDecorations(that); 84 } 85 86 std::string Integer::str() const { 87 std::ostringstream oss; 88 oss << (signed_ ? "s" : "u") << "int" << width_; 89 return oss.str(); 90 } 91 92 bool Float::IsSame(Type* that) const { 93 const Float* ft = that->AsFloat(); 94 return ft && width_ == ft->width_ && HasSameDecorations(that); 95 } 96 97 std::string Float::str() const { 98 std::ostringstream oss; 99 oss << "float" << width_; 100 return oss.str(); 101 } 102 103 Vector::Vector(Type* type, uint32_t count) 104 : element_type_(type), count_(count) { 105 assert(type->AsBool() || type->AsInteger() || type->AsFloat()); 106 } 107 108 bool Vector::IsSame(Type* that) const { 109 const Vector* vt = that->AsVector(); 110 if (!vt) return false; 111 return count_ == vt->count_ && element_type_->IsSame(vt->element_type_) && 112 HasSameDecorations(that); 113 } 114 115 std::string Vector::str() const { 116 std::ostringstream oss; 117 oss << "<" << element_type_->str() << ", " << count_ << ">"; 118 return oss.str(); 119 } 120 121 Matrix::Matrix(Type* type, uint32_t count) 122 : element_type_(type), count_(count) { 123 assert(type->AsVector()); 124 } 125 126 bool Matrix::IsSame(Type* that) const { 127 const Matrix* mt = that->AsMatrix(); 128 if (!mt) return false; 129 return count_ == mt->count_ && element_type_->IsSame(mt->element_type_) && 130 HasSameDecorations(that); 131 } 132 133 std::string Matrix::str() const { 134 std::ostringstream oss; 135 oss << "<" << element_type_->str() << ", " << count_ << ">"; 136 return oss.str(); 137 } 138 139 Image::Image(Type* sampled_type, SpvDim dim, uint32_t depth, uint32_t arrayed, 140 uint32_t ms, uint32_t sampled, SpvImageFormat format, 141 SpvAccessQualifier access_qualifier) 142 : sampled_type_(sampled_type), 143 dim_(dim), 144 depth_(depth), 145 arrayed_(arrayed), 146 ms_(ms), 147 sampled_(sampled), 148 format_(format), 149 access_qualifier_(access_qualifier) { 150 // TODO(antiagainst): check sampled_type 151 } 152 153 bool Image::IsSame(Type* that) const { 154 const Image* it = that->AsImage(); 155 if (!it) return false; 156 return dim_ == it->dim_ && depth_ == it->depth_ && arrayed_ == it->arrayed_ && 157 ms_ == it->ms_ && sampled_ == it->sampled_ && format_ == it->format_ && 158 access_qualifier_ == it->access_qualifier_ && 159 sampled_type_->IsSame(it->sampled_type_) && HasSameDecorations(that); 160 } 161 162 std::string Image::str() const { 163 std::ostringstream oss; 164 oss << "image(" << sampled_type_->str() << ", " << dim_ << ", " << depth_ 165 << ", " << arrayed_ << ", " << ms_ << ", " << sampled_ << ", " << format_ 166 << ", " << access_qualifier_ << ")"; 167 return oss.str(); 168 } 169 170 bool SampledImage::IsSame(Type* that) const { 171 const SampledImage* sit = that->AsSampledImage(); 172 if (!sit) return false; 173 return image_type_->IsSame(sit->image_type_) && HasSameDecorations(that); 174 } 175 176 std::string SampledImage::str() const { 177 std::ostringstream oss; 178 oss << "sampled_image(" << image_type_->str() << ")"; 179 return oss.str(); 180 } 181 182 Array::Array(Type* type, uint32_t length_id) 183 : element_type_(type), length_id_(length_id) { 184 assert(!type->AsVoid()); 185 } 186 187 bool Array::IsSame(Type* that) const { 188 const Array* at = that->AsArray(); 189 if (!at) return false; 190 return length_id_ == at->length_id_ && 191 element_type_->IsSame(at->element_type_) && HasSameDecorations(that); 192 } 193 194 std::string Array::str() const { 195 std::ostringstream oss; 196 oss << "[" << element_type_->str() << ", id(" << length_id_ << ")]"; 197 return oss.str(); 198 } 199 200 RuntimeArray::RuntimeArray(Type* type) : element_type_(type) { 201 assert(!type->AsVoid()); 202 } 203 204 bool RuntimeArray::IsSame(Type* that) const { 205 const RuntimeArray* rat = that->AsRuntimeArray(); 206 if (!rat) return false; 207 return element_type_->IsSame(rat->element_type_) && HasSameDecorations(that); 208 } 209 210 std::string RuntimeArray::str() const { 211 std::ostringstream oss; 212 oss << "[" << element_type_->str() << "]"; 213 return oss.str(); 214 } 215 216 Struct::Struct(const std::vector<Type*>& types) : element_types_(types) { 217 for (auto* t : types) { 218 (void)t; 219 assert(!t->AsVoid()); 220 } 221 } 222 223 void Struct::AddMemberDecoration(uint32_t index, 224 std::vector<uint32_t>&& decoration) { 225 if (index >= element_types_.size()) { 226 assert(0 && "index out of bound"); 227 return; 228 } 229 230 element_decorations_[index].push_back(std::move(decoration)); 231 } 232 233 bool Struct::IsSame(Type* that) const { 234 const Struct* st = that->AsStruct(); 235 if (!st) return false; 236 if (element_types_.size() != st->element_types_.size()) return false; 237 const auto size = element_decorations_.size(); 238 if (size != st->element_decorations_.size()) return false; 239 if (!HasSameDecorations(that)) return false; 240 241 for (size_t i = 0; i < element_types_.size(); ++i) { 242 if (!element_types_[i]->IsSame(st->element_types_[i])) return false; 243 } 244 for (const auto& p : element_decorations_) { 245 if (st->element_decorations_.count(p.first) == 0) return false; 246 if (!CompareTwoVectors(p.second, st->element_decorations_.at(p.first))) 247 return false; 248 } 249 return true; 250 } 251 252 std::string Struct::str() const { 253 std::ostringstream oss; 254 oss << "{"; 255 const size_t count = element_types_.size(); 256 for (size_t i = 0; i < count; ++i) { 257 oss << element_types_[i]->str(); 258 if (i + 1 != count) oss << ", "; 259 } 260 oss << "}"; 261 return oss.str(); 262 } 263 264 bool Opaque::IsSame(Type* that) const { 265 const Opaque* ot = that->AsOpaque(); 266 if (!ot) return false; 267 return name_ == ot->name_ && HasSameDecorations(that); 268 } 269 270 std::string Opaque::str() const { 271 std::ostringstream oss; 272 oss << "opaque('" << name_ << "')"; 273 return oss.str(); 274 } 275 276 Pointer::Pointer(Type* type, SpvStorageClass storage_class) 277 : pointee_type_(type), storage_class_(storage_class) { 278 assert(!type->AsVoid()); 279 } 280 281 bool Pointer::IsSame(Type* that) const { 282 const Pointer* pt = that->AsPointer(); 283 if (!pt) return false; 284 if (storage_class_ != pt->storage_class_) return false; 285 if (!pointee_type_->IsSame(pt->pointee_type_)) return false; 286 return HasSameDecorations(that); 287 } 288 289 std::string Pointer::str() const { return pointee_type_->str() + "*"; } 290 291 Function::Function(Type* return_type, const std::vector<Type*>& param_types) 292 : return_type_(return_type), param_types_(param_types) { 293 for (auto* t : param_types) { 294 (void)t; 295 assert(!t->AsVoid()); 296 } 297 } 298 299 bool Function::IsSame(Type* that) const { 300 const Function* ft = that->AsFunction(); 301 if (!ft) return false; 302 if (!return_type_->IsSame(ft->return_type_)) return false; 303 if (param_types_.size() != ft->param_types_.size()) return false; 304 for (size_t i = 0; i < param_types_.size(); ++i) { 305 if (!param_types_[i]->IsSame(ft->param_types_[i])) return false; 306 } 307 return HasSameDecorations(that); 308 } 309 310 std::string Function::str() const { 311 std::ostringstream oss; 312 const size_t count = param_types_.size(); 313 oss << "("; 314 for (size_t i = 0; i < count; ++i) { 315 oss << param_types_[i]->str(); 316 if (i + 1 != count) oss << ", "; 317 } 318 oss << ") -> " << return_type_->str(); 319 return oss.str(); 320 } 321 322 bool Pipe::IsSame(Type* that) const { 323 const Pipe* pt = that->AsPipe(); 324 if (!pt) return false; 325 return access_qualifier_ == pt->access_qualifier_ && HasSameDecorations(that); 326 } 327 328 std::string Pipe::str() const { 329 std::ostringstream oss; 330 oss << "pipe(" << access_qualifier_ << ")"; 331 return oss.str(); 332 } 333 334 bool ForwardPointer::IsSame(Type* that) const { 335 const ForwardPointer* fpt = that->AsForwardPointer(); 336 if (!fpt) return false; 337 return target_id_ == fpt->target_id_ && 338 storage_class_ == fpt->storage_class_ && HasSameDecorations(that); 339 } 340 341 std::string ForwardPointer::str() const { 342 std::ostringstream oss; 343 oss << "forward_pointer("; 344 if (pointer_ != nullptr) { 345 oss << pointer_->str(); 346 } else { 347 oss << target_id_; 348 } 349 oss << ")"; 350 return oss.str(); 351 } 352 353 } // namespace analysis 354 } // namespace opt 355 } // namespace spvtools 356