third_party/wasm2c/src/ir.cc

   1 /*
   2  * Copyright 2016 WebAssembly Community Group participants
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include "wabt/ir.h"
  18
  19 #include <cassert>
  20 #include <cstddef>
  21 #include <numeric>
  22
  23 #include "wabt/cast.h"
  24
  25 namespace {
  26
  27 const char* ExprTypeName[] = {
  28     "AtomicFence",
  29     "AtomicLoad",
  30     "AtomicRmw",
  31     "AtomicRmwCmpxchg",
  32     "AtomicStore",
  33     "AtomicNotify",
  34     "AtomicWait",
  35     "Binary",
  36     "Block",
  37     "Br",
  38     "BrIf",
  39     "BrTable",
  40     "Call",
  41     "CallIndirect",
  42     "CallRef",
  43     "CodeMetadata",
  44     "Compare",
  45     "Const",
  46     "Convert",
  47     "Drop",
  48     "GlobalGet",
  49     "GlobalSet",
  50     "If",
  51     "Load",
  52     "LocalGet",
  53     "LocalSet",
  54     "LocalTee",
  55     "Loop",
  56     "MemoryCopy",
  57     "DataDrop",
  58     "MemoryFill",
  59     "MemoryGrow",
  60     "MemoryInit",
  61     "MemorySize",
  62     "Nop",
  63     "RefIsNull",
  64     "RefFunc",
  65     "RefNull",
  66     "Rethrow",
  67     "Return",
  68     "ReturnCall",
  69     "ReturnCallIndirect",
  70     "Select",
  71     "SimdLaneOp",
  72     "SimdLoadLane",
  73     "SimdStoreLane",
  74     "SimdShuffleOp",
  75     "LoadSplat",
  76     "LoadZero",
  77     "Store",
  78     "TableCopy",
  79     "ElemDrop",
  80     "TableInit",
  81     "TableGet",
  82     "TableGrow",
  83     "TableSize",
  84     "TableSet",
  85     "TableFill",
  86     "Ternary",
  87     "Throw",
  88     "Try",
  89     "Unary",
  90     "Unreachable",
  91 };
  92
  93 }  // end of anonymous namespace
  94
  95 namespace wabt {
  96
  97 const char* GetExprTypeName(ExprType type) {
  98   static_assert(WABT_ENUM_COUNT(ExprType) == WABT_ARRAY_SIZE(ExprTypeName),
  99                 "Malformed ExprTypeName array");
 100   return ExprTypeName[size_t(type)];
 101 }
 102
 103 const char* GetExprTypeName(const Expr& expr) {
 104   return GetExprTypeName(expr.type());
 105 }
 106
 107 bool FuncSignature::operator==(const FuncSignature& rhs) const {
 108   return param_types == rhs.param_types && result_types == rhs.result_types;
 109 }
 110
 111 const Export* Module::GetExport(std::string_view name) const {
 112   Index index = export_bindings.FindIndex(name);
 113   if (index >= exports.size()) {
 114     return nullptr;
 115   }
 116   return exports[index];
 117 }
 118
 119 Index Module::GetFuncIndex(const Var& var) const {
 120   return func_bindings.FindIndex(var);
 121 }
 122
 123 Index Module::GetGlobalIndex(const Var& var) const {
 124   return global_bindings.FindIndex(var);
 125 }
 126
 127 Index Module::GetTableIndex(const Var& var) const {
 128   return table_bindings.FindIndex(var);
 129 }
 130
 131 Index Module::GetMemoryIndex(const Var& var) const {
 132   return memory_bindings.FindIndex(var);
 133 }
 134
 135 Index Module::GetFuncTypeIndex(const Var& var) const {
 136   return type_bindings.FindIndex(var);
 137 }
 138
 139 Index Module::GetTagIndex(const Var& var) const {
 140   return tag_bindings.FindIndex(var);
 141 }
 142
 143 Index Module::GetDataSegmentIndex(const Var& var) const {
 144   return data_segment_bindings.FindIndex(var);
 145 }
 146
 147 Index Module::GetElemSegmentIndex(const Var& var) const {
 148   return elem_segment_bindings.FindIndex(var);
 149 }
 150
 151 bool Module::IsImport(ExternalKind kind, const Var& var) const {
 152   switch (kind) {
 153     case ExternalKind::Func:
 154       return GetFuncIndex(var) < num_func_imports;
 155
 156     case ExternalKind::Global:
 157       return GetGlobalIndex(var) < num_global_imports;
 158
 159     case ExternalKind::Memory:
 160       return GetMemoryIndex(var) < num_memory_imports;
 161
 162     case ExternalKind::Table:
 163       return GetTableIndex(var) < num_table_imports;
 164
 165     case ExternalKind::Tag:
 166       return GetTagIndex(var) < num_tag_imports;
 167
 168     default:
 169       return false;
 170   }
 171 }
 172
 173 void LocalTypes::Set(const TypeVector& types) {
 174   decls_.clear();
 175   if (types.empty()) {
 176     return;
 177   }
 178
 179   Type type = types[0];
 180   Index count = 1;
 181   for (Index i = 1; i < types.size(); ++i) {
 182     if (types[i] != type) {
 183       decls_.emplace_back(type, count);
 184       type = types[i];
 185       count = 1;
 186     } else {
 187       ++count;
 188     }
 189   }
 190   decls_.emplace_back(type, count);
 191 }
 192
 193 Index LocalTypes::size() const {
 194   return std::accumulate(
 195       decls_.begin(), decls_.end(), 0,
 196       [](Index sum, const Decl& decl) { return sum + decl.second; });
 197 }
 198
 199 Type LocalTypes::operator[](Index i) const {
 200   Index count = 0;
 201   for (auto decl : decls_) {
 202     if (i < count + decl.second) {
 203       return decl.first;
 204     }
 205     count += decl.second;
 206   }
 207   assert(i < count);
 208   return Type::Any;
 209 }
 210
 211 Type Func::GetLocalType(Index index) const {
 212   Index num_params = decl.GetNumParams();
 213   if (index < num_params) {
 214     return GetParamType(index);
 215   } else {
 216     index -= num_params;
 217     assert(index < local_types.size());
 218     return local_types[index];
 219   }
 220 }
 221
 222 Type Func::GetLocalType(const Var& var) const {
 223   return GetLocalType(GetLocalIndex(var));
 224 }
 225
 226 Index Func::GetLocalIndex(const Var& var) const {
 227   if (var.is_index()) {
 228     return var.index();
 229   }
 230   return bindings.FindIndex(var);
 231 }
 232
 233 const Func* Module::GetFunc(const Var& var) const {
 234   return const_cast<Module*>(this)->GetFunc(var);
 235 }
 236
 237 Func* Module::GetFunc(const Var& var) {
 238   Index index = func_bindings.FindIndex(var);
 239   if (index >= funcs.size()) {
 240     return nullptr;
 241   }
 242   return funcs[index];
 243 }
 244
 245 const Global* Module::GetGlobal(const Var& var) const {
 246   return const_cast<Module*>(this)->GetGlobal(var);
 247 }
 248
 249 Global* Module::GetGlobal(const Var& var) {
 250   Index index = global_bindings.FindIndex(var);
 251   if (index >= globals.size()) {
 252     return nullptr;
 253   }
 254   return globals[index];
 255 }
 256
 257 const Table* Module::GetTable(const Var& var) const {
 258   return const_cast<Module*>(this)->GetTable(var);
 259 }
 260
 261 Table* Module::GetTable(const Var& var) {
 262   Index index = table_bindings.FindIndex(var);
 263   if (index >= tables.size()) {
 264     return nullptr;
 265   }
 266   return tables[index];
 267 }
 268
 269 const Memory* Module::GetMemory(const Var& var) const {
 270   return const_cast<Module*>(this)->GetMemory(var);
 271 }
 272
 273 Memory* Module::GetMemory(const Var& var) {
 274   Index index = memory_bindings.FindIndex(var);
 275   if (index >= memories.size()) {
 276     return nullptr;
 277   }
 278   return memories[index];
 279 }
 280
 281 Tag* Module::GetTag(const Var& var) const {
 282   Index index = GetTagIndex(var);
 283   if (index >= tags.size()) {
 284     return nullptr;
 285   }
 286   return tags[index];
 287 }
 288
 289 const DataSegment* Module::GetDataSegment(const Var& var) const {
 290   return const_cast<Module*>(this)->GetDataSegment(var);
 291 }
 292
 293 DataSegment* Module::GetDataSegment(const Var& var) {
 294   Index index = data_segment_bindings.FindIndex(var);
 295   if (index >= data_segments.size()) {
 296     return nullptr;
 297   }
 298   return data_segments[index];
 299 }
 300
 301 const ElemSegment* Module::GetElemSegment(const Var& var) const {
 302   return const_cast<Module*>(this)->GetElemSegment(var);
 303 }
 304
 305 ElemSegment* Module::GetElemSegment(const Var& var) {
 306   Index index = elem_segment_bindings.FindIndex(var);
 307   if (index >= elem_segments.size()) {
 308     return nullptr;
 309   }
 310   return elem_segments[index];
 311 }
 312
 313 const FuncType* Module::GetFuncType(const Var& var) const {
 314   return const_cast<Module*>(this)->GetFuncType(var);
 315 }
 316
 317 FuncType* Module::GetFuncType(const Var& var) {
 318   Index index = type_bindings.FindIndex(var);
 319   if (index >= types.size()) {
 320     return nullptr;
 321   }
 322   return dyn_cast<FuncType>(types[index]);
 323 }
 324
 325 Index Module::GetFuncTypeIndex(const FuncSignature& sig) const {
 326   for (size_t i = 0; i < types.size(); ++i) {
 327     if (auto* func_type = dyn_cast<FuncType>(types[i])) {
 328       if (func_type->sig == sig) {
 329         return i;
 330       }
 331     }
 332   }
 333   return kInvalidIndex;
 334 }
 335
 336 Index Module::GetFuncTypeIndex(const FuncDeclaration& decl) const {
 337   if (decl.has_func_type) {
 338     return GetFuncTypeIndex(decl.type_var);
 339   } else {
 340     return GetFuncTypeIndex(decl.sig);
 341   }
 342 }
 343
 344 void Module::AppendField(std::unique_ptr<DataSegmentModuleField> field) {
 345   DataSegment& data_segment = field->data_segment;
 346   if (!data_segment.name.empty()) {
 347     data_segment_bindings.emplace(data_segment.name,
 348                                   Binding(field->loc, data_segments.size()));
 349   }
 350   data_segments.push_back(&data_segment);
 351   fields.push_back(std::move(field));
 352 }
 353
 354 void Module::AppendField(std::unique_ptr<ElemSegmentModuleField> field) {
 355   ElemSegment& elem_segment = field->elem_segment;
 356   if (!elem_segment.name.empty()) {
 357     elem_segment_bindings.emplace(elem_segment.name,
 358                                   Binding(field->loc, elem_segments.size()));
 359   }
 360   elem_segments.push_back(&elem_segment);
 361   fields.push_back(std::move(field));
 362 }
 363
 364 void Module::AppendField(std::unique_ptr<TagModuleField> field) {
 365   Tag& tag = field->tag;
 366   if (!tag.name.empty()) {
 367     tag_bindings.emplace(tag.name, Binding(field->loc, tags.size()));
 368   }
 369   tags.push_back(&tag);
 370   fields.push_back(std::move(field));
 371 }
 372
 373 void Module::AppendField(std::unique_ptr<ExportModuleField> field) {
 374   // Exported names are allowed to be empty.
 375   Export& export_ = field->export_;
 376   export_bindings.emplace(export_.name, Binding(field->loc, exports.size()));
 377   exports.push_back(&export_);
 378   fields.push_back(std::move(field));
 379 }
 380
 381 void Module::AppendField(std::unique_ptr<FuncModuleField> field) {
 382   Func& func = field->func;
 383   if (!func.name.empty()) {
 384     func_bindings.emplace(func.name, Binding(field->loc, funcs.size()));
 385   }
 386   funcs.push_back(&func);
 387   fields.push_back(std::move(field));
 388 }
 389
 390 void Module::AppendField(std::unique_ptr<TypeModuleField> field) {
 391   TypeEntry& type = *field->type;
 392   if (!type.name.empty()) {
 393     type_bindings.emplace(type.name, Binding(field->loc, types.size()));
 394   }
 395   types.push_back(&type);
 396   fields.push_back(std::move(field));
 397 }
 398
 399 void Module::AppendField(std::unique_ptr<GlobalModuleField> field) {
 400   Global& global = field->global;
 401   if (!global.name.empty()) {
 402     global_bindings.emplace(global.name, Binding(field->loc, globals.size()));
 403   }
 404   globals.push_back(&global);
 405   fields.push_back(std::move(field));
 406 }
 407
 408 void Module::AppendField(std::unique_ptr<ImportModuleField> field) {
 409   Import* import = field->import.get();
 410   const std::string* name = nullptr;
 411   BindingHash* bindings = nullptr;
 412   Index index = kInvalidIndex;
 413
 414   switch (import->kind()) {
 415     case ExternalKind::Func: {
 416       Func& func = cast<FuncImport>(import)->func;
 417       name = &func.name;
 418       bindings = &func_bindings;
 419       index = funcs.size();
 420       funcs.push_back(&func);
 421       ++num_func_imports;
 422       break;
 423     }
 424
 425     case ExternalKind::Table: {
 426       Table& table = cast<TableImport>(import)->table;
 427       name = &table.name;
 428       bindings = &table_bindings;
 429       index = tables.size();
 430       tables.push_back(&table);
 431       ++num_table_imports;
 432       break;
 433     }
 434
 435     case ExternalKind::Memory: {
 436       Memory& memory = cast<MemoryImport>(import)->memory;
 437       name = &memory.name;
 438       bindings = &memory_bindings;
 439       index = memories.size();
 440       memories.push_back(&memory);
 441       ++num_memory_imports;
 442       break;
 443     }
 444
 445     case ExternalKind::Global: {
 446       Global& global = cast<GlobalImport>(import)->global;
 447       name = &global.name;
 448       bindings = &global_bindings;
 449       index = globals.size();
 450       globals.push_back(&global);
 451       ++num_global_imports;
 452       break;
 453     }
 454
 455     case ExternalKind::Tag: {
 456       Tag& tag = cast<TagImport>(import)->tag;
 457       name = &tag.name;
 458       bindings = &tag_bindings;
 459       index = tags.size();
 460       tags.push_back(&tag);
 461       ++num_tag_imports;
 462       break;
 463     }
 464   }
 465
 466   assert(name && bindings && index != kInvalidIndex);
 467   if (!name->empty()) {
 468     bindings->emplace(*name, Binding(field->loc, index));
 469   }
 470   imports.push_back(import);
 471   fields.push_back(std::move(field));
 472 }
 473
 474 void Module::AppendField(std::unique_ptr<MemoryModuleField> field) {
 475   Memory& memory = field->memory;
 476   if (!memory.name.empty()) {
 477     memory_bindings.emplace(memory.name, Binding(field->loc, memories.size()));
 478   }
 479   memories.push_back(&memory);
 480   fields.push_back(std::move(field));
 481 }
 482
 483 void Module::AppendField(std::unique_ptr<StartModuleField> field) {
 484   starts.push_back(&field->start);
 485   fields.push_back(std::move(field));
 486 }
 487
 488 void Module::AppendField(std::unique_ptr<TableModuleField> field) {
 489   Table& table = field->table;
 490   if (!table.name.empty()) {
 491     table_bindings.emplace(table.name, Binding(field->loc, tables.size()));
 492   }
 493   tables.push_back(&table);
 494   fields.push_back(std::move(field));
 495 }
 496
 497 void Module::AppendField(std::unique_ptr<ModuleField> field) {
 498   switch (field->type()) {
 499     case ModuleFieldType::Func:
 500       AppendField(cast<FuncModuleField>(std::move(field)));
 501       break;
 502
 503     case ModuleFieldType::Global:
 504       AppendField(cast<GlobalModuleField>(std::move(field)));
 505       break;
 506
 507     case ModuleFieldType::Import:
 508       AppendField(cast<ImportModuleField>(std::move(field)));
 509       break;
 510
 511     case ModuleFieldType::Export:
 512       AppendField(cast<ExportModuleField>(std::move(field)));
 513       break;
 514
 515     case ModuleFieldType::Type:
 516       AppendField(cast<TypeModuleField>(std::move(field)));
 517       break;
 518
 519     case ModuleFieldType::Table:
 520       AppendField(cast<TableModuleField>(std::move(field)));
 521       break;
 522
 523     case ModuleFieldType::ElemSegment:
 524       AppendField(cast<ElemSegmentModuleField>(std::move(field)));
 525       break;
 526
 527     case ModuleFieldType::Memory:
 528       AppendField(cast<MemoryModuleField>(std::move(field)));
 529       break;
 530
 531     case ModuleFieldType::DataSegment:
 532       AppendField(cast<DataSegmentModuleField>(std::move(field)));
 533       break;
 534
 535     case ModuleFieldType::Start:
 536       AppendField(cast<StartModuleField>(std::move(field)));
 537       break;
 538
 539     case ModuleFieldType::Tag:
 540       AppendField(cast<TagModuleField>(std::move(field)));
 541       break;
 542   }
 543 }
 544
 545 void Module::AppendFields(ModuleFieldList* fields) {
 546   while (!fields->empty())
 547     AppendField(std::unique_ptr<ModuleField>(fields->extract_front()));
 548 }
 549
 550 const Module* Script::GetFirstModule() const {
 551   return const_cast<Script*>(this)->GetFirstModule();
 552 }
 553
 554 Module* Script::GetFirstModule() {
 555   for (const std::unique_ptr<Command>& command : commands) {
 556     if (auto* module_command = dyn_cast<ModuleCommand>(command.get())) {
 557       return &module_command->module;
 558     }
 559   }
 560   return nullptr;
 561 }
 562
 563 const Module* Script::GetModule(const Var& var) const {
 564   Index index = module_bindings.FindIndex(var);
 565   if (index >= commands.size()) {
 566     return nullptr;
 567   }
 568   auto* command = commands[index].get();
 569   if (isa<ModuleCommand>(command)) {
 570     return &cast<ModuleCommand>(command)->module;
 571   } else if (isa<ScriptModuleCommand>(command)) {
 572     return &cast<ScriptModuleCommand>(command)->module;
 573   }
 574   return nullptr;
 575 }
 576
 577 void MakeTypeBindingReverseMapping(
 578     size_t num_types,
 579     const BindingHash& bindings,
 580     std::vector<std::string>* out_reverse_mapping) {
 581   out_reverse_mapping->clear();
 582   out_reverse_mapping->resize(num_types);
 583   for (const auto& [name, binding] : bindings) {
 584     assert(static_cast<size_t>(binding.index) < out_reverse_mapping->size());
 585     (*out_reverse_mapping)[binding.index] = name;
 586   }
 587 }
 588
 589 Var::Var() : Var(kInvalidIndex, Location()) {}
 590
 591 Var::Var(Index index, const Location& loc)
 592     : loc(loc), type_(VarType::Index), index_(index) {}
 593
 594 Var::Var(std::string_view name, const Location& loc)
 595     : loc(loc), type_(VarType::Name), name_(name) {}
 596
 597 Var::Var(Var&& rhs) : Var() {
 598   *this = std::move(rhs);
 599 }
 600
 601 Var::Var(const Var& rhs) : Var() {
 602   *this = rhs;
 603 }
 604
 605 Var& Var::operator=(Var&& rhs) {
 606   loc = rhs.loc;
 607   if (rhs.is_index()) {
 608     set_index(rhs.index_);
 609   } else {
 610     set_name(rhs.name_);
 611   }
 612   return *this;
 613 }
 614
 615 Var& Var::operator=(const Var& rhs) {
 616   loc = rhs.loc;
 617   if (rhs.is_index()) {
 618     set_index(rhs.index_);
 619   } else {
 620     set_name(rhs.name_);
 621   }
 622   return *this;
 623 }
 624
 625 Var::~Var() {
 626   Destroy();
 627 }
 628
 629 void Var::set_index(Index index) {
 630   Destroy();
 631   type_ = VarType::Index;
 632   index_ = index;
 633 }
 634
 635 void Var::set_name(std::string&& name) {
 636   Destroy();
 637   type_ = VarType::Name;
 638   Construct(name_, std::move(name));
 639 }
 640
 641 void Var::set_name(std::string_view name) {
 642   set_name(std::string(name));
 643 }
 644
 645 void Var::Destroy() {
 646   if (is_name()) {
 647     Destruct(name_);
 648   }
 649 }
 650
 651 uint8_t ElemSegment::GetFlags(const Module* module) const {
 652   uint8_t flags = 0;
 653
 654   switch (kind) {
 655     case SegmentKind::Active: {
 656       Index table_index = module->GetTableIndex(table_var);
 657       if (elem_type != Type::FuncRef || table_index != 0) {
 658         flags |= SegExplicitIndex;
 659       }
 660       break;
 661     }
 662
 663     case SegmentKind::Passive:
 664       flags |= SegPassive;
 665       break;
 666
 667     case SegmentKind::Declared:
 668       flags |= SegDeclared;
 669       break;
 670   }
 671
 672   bool all_ref_func =
 673       elem_type == Type::FuncRef &&
 674       std::all_of(elem_exprs.begin(), elem_exprs.end(),
 675                   [](const ExprList& elem_expr) {
 676                     return elem_expr.front().type() == ExprType::RefFunc;
 677                   });
 678
 679   if (!all_ref_func) {
 680     flags |= SegUseElemExprs;
 681   }
 682
 683   return flags;
 684 }
 685
 686 uint8_t DataSegment::GetFlags(const Module* module) const {
 687   uint8_t flags = 0;
 688
 689   if (kind == SegmentKind::Passive) {
 690     flags |= SegPassive;
 691   }
 692
 693   Index memory_index = module->GetMemoryIndex(memory_var);
 694   if (memory_index != 0) {
 695     flags |= SegExplicitIndex;
 696   }
 697
 698   return flags;
 699 }
 700
 701 }  // namespace wabt