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 "wasm.h"
18 #include "ir/branch-utils.h"
19 #include "wasm-printing.h"
20 #include "wasm-traversal.h"
21 
22 namespace wasm {
23 
24 // shared constants
25 
26 Name WASM("wasm");
27 Name RETURN_FLOW("*return:)*");
28 Name NONCONSTANT_FLOW("*nonconstant:)*");
29 
30 namespace BinaryConsts {
31 namespace UserSections {
32 const char* Name = "name";
33 const char* SourceMapUrl = "sourceMappingURL";
34 const char* Dylink = "dylink";
35 const char* Linking = "linking";
36 const char* Producers = "producers";
37 const char* TargetFeatures = "target_features";
38 const char* AtomicsFeature = "atomics";
39 const char* BulkMemoryFeature = "bulk-memory";
40 const char* ExceptionHandlingFeature = "exception-handling";
41 const char* MutableGlobalsFeature = "mutable-globals";
42 const char* TruncSatFeature = "nontrapping-fptoint";
43 const char* SignExtFeature = "sign-ext";
44 const char* SIMD128Feature = "simd128";
45 const char* TailCallFeature = "tail-call";
46 const char* ReferenceTypesFeature = "reference-types";
47 const char* MultivalueFeature = "multivalue";
48 const char* GCFeature = "gc";
49 const char* Memory64Feature = "memory64";
50 } // namespace UserSections
51 } // namespace BinaryConsts
52 
53 Name WASM_CALL_CTORS("__wasm_call_ctors");
54 Name MEMORY_BASE("__memory_base");
55 Name TABLE_BASE("__table_base");
56 Name STACK_POINTER("__stack_pointer");
57 Name GET_TEMP_RET0("getTempRet0");
58 Name SET_TEMP_RET0("setTempRet0");
59 Name NEW_SIZE("newSize");
60 Name MODULE("module");
61 Name START("start");
62 Name FUNC("func");
63 Name PARAM("param");
64 Name RESULT("result");
65 Name MEMORY("memory");
66 Name DATA("data");
67 Name PASSIVE("passive");
68 Name EXPORT("export");
69 Name IMPORT("import");
70 Name TABLE("table");
71 Name ELEM("elem");
72 Name LOCAL("local");
73 Name TYPE("type");
74 Name CALL("call");
75 Name CALL_INDIRECT("call_indirect");
76 Name BLOCK("block");
77 Name BR_IF("br_if");
78 Name THEN("then");
79 Name ELSE("else");
80 Name _NAN("NaN");
81 Name _INFINITY("Infinity");
82 Name NEG_INFINITY("-infinity");
83 Name NEG_NAN("-nan");
84 Name CASE("case");
85 Name BR("br");
86 Name FUNCREF("funcref");
87 Name FAKE_RETURN("fake_return_waka123");
88 Name MUT("mut");
89 Name SPECTEST("spectest");
90 Name PRINT("print");
91 Name EXIT("exit");
92 Name SHARED("shared");
93 Name EVENT("event");
94 Name ATTR("attr");
95 Name ASSIGN_GOT_ENTRIES("__assign_got_enties");
96 
97 // Expressions
98 
dump()99 void Expression::dump() {
100   WasmPrinter::printExpression(this,
101                                std::cerr,
102                                /*minify=*/false,
103                                /*full=*/true);
104 }
105 
getExpressionName(Expression * curr)106 const char* getExpressionName(Expression* curr) {
107   switch (curr->_id) {
108     case Expression::Id::InvalidId:
109       WASM_UNREACHABLE("invalid expr id");
110     case Expression::Id::BlockId:
111       return "block";
112     case Expression::Id::IfId:
113       return "if";
114     case Expression::Id::LoopId:
115       return "loop";
116     case Expression::Id::BreakId:
117       return "break";
118     case Expression::Id::SwitchId:
119       return "switch";
120     case Expression::Id::CallId:
121       return "call";
122     case Expression::Id::CallIndirectId:
123       return "call_indirect";
124     case Expression::Id::LocalGetId:
125       return "local.get";
126     case Expression::Id::LocalSetId:
127       return "local.set";
128     case Expression::Id::GlobalGetId:
129       return "global.get";
130     case Expression::Id::GlobalSetId:
131       return "global.set";
132     case Expression::Id::LoadId:
133       return "load";
134     case Expression::Id::StoreId:
135       return "store";
136     case Expression::Id::ConstId:
137       return "const";
138     case Expression::Id::UnaryId:
139       return "unary";
140     case Expression::Id::BinaryId:
141       return "binary";
142     case Expression::Id::SelectId:
143       return "select";
144     case Expression::Id::DropId:
145       return "drop";
146     case Expression::Id::ReturnId:
147       return "return";
148     case Expression::Id::MemorySizeId:
149       return "memory.size";
150     case Expression::Id::MemoryGrowId:
151       return "memory.grow";
152     case Expression::Id::NopId:
153       return "nop";
154     case Expression::Id::UnreachableId:
155       return "unreachable";
156     case Expression::Id::AtomicCmpxchgId:
157       return "atomic_cmpxchg";
158     case Expression::Id::AtomicRMWId:
159       return "atomic_rmw";
160     case Expression::Id::AtomicWaitId:
161       return "atomic_wait";
162     case Expression::Id::AtomicNotifyId:
163       return "atomic_notify";
164     case Expression::Id::AtomicFenceId:
165       return "atomic_fence";
166     case Expression::Id::SIMDExtractId:
167       return "simd_extract";
168     case Expression::Id::SIMDReplaceId:
169       return "simd_replace";
170     case Expression::Id::SIMDShuffleId:
171       return "simd_shuffle";
172     case Expression::Id::SIMDTernaryId:
173       return "simd_ternary";
174     case Expression::Id::SIMDShiftId:
175       return "simd_shift";
176     case Expression::Id::SIMDLoadId:
177       return "simd_load";
178     case Expression::Id::MemoryInitId:
179       return "memory_init";
180     case Expression::Id::DataDropId:
181       return "data_drop";
182     case Expression::Id::MemoryCopyId:
183       return "memory_copy";
184     case Expression::Id::MemoryFillId:
185       return "memory_fill";
186     case Expression::Id::PopId:
187       return "pop";
188     case Expression::Id::RefNullId:
189       return "ref.null";
190     case Expression::Id::RefIsNullId:
191       return "ref.is_null";
192     case Expression::Id::RefFuncId:
193       return "ref.func";
194     case Expression::Id::RefEqId:
195       return "ref.eq";
196     case Expression::Id::TryId:
197       return "try";
198     case Expression::Id::ThrowId:
199       return "throw";
200     case Expression::Id::RethrowId:
201       return "rethrow";
202     case Expression::Id::BrOnExnId:
203       return "br_on_exn";
204     case Expression::Id::TupleMakeId:
205       return "tuple.make";
206     case Expression::Id::TupleExtractId:
207       return "tuple.extract";
208     case Expression::Id::I31NewId:
209       return "i31.new";
210     case Expression::Id::I31GetId:
211       return "i31.get";
212     case Expression::Id::RefTestId:
213       return "ref.test";
214     case Expression::Id::RefCastId:
215       return "ref.cast";
216     case Expression::Id::BrOnCastId:
217       return "br_on_cast";
218     case Expression::Id::RttCanonId:
219       return "rtt.canon";
220     case Expression::Id::RttSubId:
221       return "rtt.sub";
222     case Expression::Id::StructNewId:
223       return "struct.new";
224     case Expression::Id::StructGetId:
225       return "struct.get";
226     case Expression::Id::StructSetId:
227       return "struct.set";
228     case Expression::Id::ArrayNewId:
229       return "array.new";
230     case Expression::Id::ArrayGetId:
231       return "array.get";
232     case Expression::Id::ArraySetId:
233       return "array.set";
234     case Expression::Id::ArrayLenId:
235       return "array.len";
236     case Expression::Id::NumExpressionIds:
237       WASM_UNREACHABLE("invalid expr id");
238   }
239   WASM_UNREACHABLE("invalid expr id");
240 }
241 
getLiteralFromConstExpression(Expression * curr)242 Literal getLiteralFromConstExpression(Expression* curr) {
243   // TODO: Do we need this function given that Properties::getLiteral
244   // (currently) does the same?
245   assert(Properties::isConstantExpression(curr));
246   return Properties::getLiteral(curr);
247 }
248 
getLiteralsFromConstExpression(Expression * curr)249 Literals getLiteralsFromConstExpression(Expression* curr) {
250   // TODO: Do we need this function given that Properties::getLiterals
251   // (currently) does the same?
252   if (auto* t = curr->dynCast<TupleMake>()) {
253     Literals values;
254     for (auto* operand : t->operands) {
255       values.push_back(getLiteralFromConstExpression(operand));
256     }
257     return values;
258   } else {
259     return {getLiteralFromConstExpression(curr)};
260   }
261 }
262 
263 // core AST type checking
264 
265 struct TypeSeeker : public PostWalker<TypeSeeker> {
266   Expression* target; // look for this one
267   Name targetName;
268   std::vector<Type> types;
269 
TypeSeekerwasm::TypeSeeker270   TypeSeeker(Expression* target, Name targetName)
271     : target(target), targetName(targetName) {
272     Expression* temp = target;
273     walk(temp);
274   }
275 
visitBreakwasm::TypeSeeker276   void visitBreak(Break* curr) {
277     if (curr->name == targetName) {
278       types.push_back(curr->value ? curr->value->type : Type::none);
279     }
280   }
281 
visitSwitchwasm::TypeSeeker282   void visitSwitch(Switch* curr) {
283     for (auto name : curr->targets) {
284       if (name == targetName) {
285         types.push_back(curr->value ? curr->value->type : Type::none);
286       }
287     }
288     if (curr->default_ == targetName) {
289       types.push_back(curr->value ? curr->value->type : Type::none);
290     }
291   }
292 
visitBrOnExnwasm::TypeSeeker293   void visitBrOnExn(BrOnExn* curr) {
294     if (curr->name == targetName) {
295       types.push_back(curr->sent);
296     }
297   }
298 
visitBlockwasm::TypeSeeker299   void visitBlock(Block* curr) {
300     if (curr == target) {
301       if (curr->list.size() > 0) {
302         types.push_back(curr->list.back()->type);
303       } else {
304         types.push_back(Type::none);
305       }
306     } else if (curr->name == targetName) {
307       // ignore all breaks til now, they were captured by someone with the same
308       // name
309       types.clear();
310     }
311   }
312 
visitLoopwasm::TypeSeeker313   void visitLoop(Loop* curr) {
314     if (curr == target) {
315       types.push_back(curr->body->type);
316     } else if (curr->name == targetName) {
317       // ignore all breaks til now, they were captured by someone with the same
318       // name
319       types.clear();
320     }
321   }
322 };
323 
324 // a block is unreachable if one of its elements is unreachable,
325 // and there are no branches to it
handleUnreachable(Block * block,bool breakabilityKnown=false,bool hasBreak=false)326 static void handleUnreachable(Block* block,
327                               bool breakabilityKnown = false,
328                               bool hasBreak = false) {
329   if (block->type == Type::unreachable) {
330     return; // nothing to do
331   }
332   if (block->list.size() == 0) {
333     return; // nothing to do
334   }
335   // if we are concrete, stop - even an unreachable child
336   // won't change that (since we have a break with a value,
337   // or the final child flows out a value)
338   if (block->type.isConcrete()) {
339     return;
340   }
341   // look for an unreachable child
342   for (auto* child : block->list) {
343     if (child->type == Type::unreachable) {
344       // there is an unreachable child, so we are unreachable, unless we have a
345       // break
346       if (!breakabilityKnown) {
347         hasBreak = BranchUtils::BranchSeeker::has(block, block->name);
348       }
349       if (!hasBreak) {
350         block->type = Type::unreachable;
351       }
352       return;
353     }
354   }
355 }
356 
finalize()357 void Block::finalize() {
358   if (!name.is()) {
359     if (list.size() > 0) {
360       // nothing branches here, so this is easy
361       // normally the type is the type of the final child
362       type = list.back()->type;
363       // and even if we have an unreachable child somewhere,
364       // we still mark ourselves as having that type,
365       // (block (result i32)
366       //  (return)
367       //  (i32.const 10)
368       // )
369       if (type.isConcrete()) {
370         return;
371       }
372       // if we are unreachable, we are done
373       if (type == Type::unreachable) {
374         return;
375       }
376       // we may still be unreachable if we have an unreachable
377       // child
378       for (auto* child : list) {
379         if (child->type == Type::unreachable) {
380           type = Type::unreachable;
381           return;
382         }
383       }
384     } else {
385       type = Type::none;
386     }
387     return;
388   }
389 
390   TypeSeeker seeker(this, this->name);
391   type = Type::mergeTypes(seeker.types);
392   handleUnreachable(this);
393 }
394 
finalize(Type type_)395 void Block::finalize(Type type_) {
396   type = type_;
397   if (type == Type::none && list.size() > 0) {
398     handleUnreachable(this);
399   }
400 }
401 
finalize(Type type_,bool hasBreak)402 void Block::finalize(Type type_, bool hasBreak) {
403   type = type_;
404   if (type == Type::none && list.size() > 0) {
405     handleUnreachable(this, true, hasBreak);
406   }
407 }
408 
finalize(Type type_)409 void If::finalize(Type type_) {
410   type = type_;
411   if (type == Type::none && (condition->type == Type::unreachable ||
412                              (ifFalse && ifTrue->type == Type::unreachable &&
413                               ifFalse->type == Type::unreachable))) {
414     type = Type::unreachable;
415   }
416 }
417 
finalize()418 void If::finalize() {
419   type = ifFalse ? Type::getLeastUpperBound(ifTrue->type, ifFalse->type)
420                  : Type::none;
421   // if the arms return a value, leave it even if the condition
422   // is unreachable, we still mark ourselves as having that type, e.g.
423   // (if (result i32)
424   //  (unreachable)
425   //  (i32.const 10)
426   //  (i32.const 20
427   // )
428   // otherwise, if the condition is unreachable, so is the if
429   if (type == Type::none && condition->type == Type::unreachable) {
430     type = Type::unreachable;
431   }
432 }
433 
finalize(Type type_)434 void Loop::finalize(Type type_) {
435   type = type_;
436   if (type == Type::none && body->type == Type::unreachable) {
437     type = Type::unreachable;
438   }
439 }
440 
finalize()441 void Loop::finalize() { type = body->type; }
442 
finalize()443 void Break::finalize() {
444   if (condition) {
445     if (condition->type == Type::unreachable) {
446       type = Type::unreachable;
447     } else if (value) {
448       type = value->type;
449     } else {
450       type = Type::none;
451     }
452   } else {
453     type = Type::unreachable;
454   }
455 }
456 
finalize()457 void Switch::finalize() { type = Type::unreachable; }
458 
handleUnreachableOperands(T * curr)459 template<typename T> void handleUnreachableOperands(T* curr) {
460   for (auto* child : curr->operands) {
461     if (child->type == Type::unreachable) {
462       curr->type = Type::unreachable;
463       break;
464     }
465   }
466 }
467 
finalize()468 void Call::finalize() {
469   handleUnreachableOperands(this);
470   if (isReturn) {
471     type = Type::unreachable;
472   }
473 }
474 
finalize()475 void CallIndirect::finalize() {
476   type = sig.results;
477   handleUnreachableOperands(this);
478   if (isReturn) {
479     type = Type::unreachable;
480   }
481   if (target->type == Type::unreachable) {
482     type = Type::unreachable;
483   }
484 }
485 
isTee() const486 bool LocalSet::isTee() const { return type != Type::none; }
487 
488 // Changes to local.tee. The type of the local should be given.
makeTee(Type type_)489 void LocalSet::makeTee(Type type_) {
490   type = type_;
491   finalize(); // type may need to be unreachable
492 }
493 
494 // Changes to local.set.
makeSet()495 void LocalSet::makeSet() {
496   type = Type::none;
497   finalize(); // type may need to be unreachable
498 }
499 
finalize()500 void LocalSet::finalize() {
501   if (value->type == Type::unreachable) {
502     type = Type::unreachable;
503   }
504 }
505 
finalize()506 void GlobalSet::finalize() {
507   if (value->type == Type::unreachable) {
508     type = Type::unreachable;
509   }
510 }
511 
finalize()512 void Load::finalize() {
513   if (ptr->type == Type::unreachable) {
514     type = Type::unreachable;
515   }
516 }
517 
finalize()518 void Store::finalize() {
519   assert(valueType != Type::none); // must be set
520   if (ptr->type == Type::unreachable || value->type == Type::unreachable) {
521     type = Type::unreachable;
522   } else {
523     type = Type::none;
524   }
525 }
526 
finalize()527 void AtomicRMW::finalize() {
528   if (ptr->type == Type::unreachable || value->type == Type::unreachable) {
529     type = Type::unreachable;
530   }
531 }
532 
finalize()533 void AtomicCmpxchg::finalize() {
534   if (ptr->type == Type::unreachable || expected->type == Type::unreachable ||
535       replacement->type == Type::unreachable) {
536     type = Type::unreachable;
537   }
538 }
539 
finalize()540 void AtomicWait::finalize() {
541   type = Type::i32;
542   if (ptr->type == Type::unreachable || expected->type == Type::unreachable ||
543       timeout->type == Type::unreachable) {
544     type = Type::unreachable;
545   }
546 }
547 
finalize()548 void AtomicNotify::finalize() {
549   type = Type::i32;
550   if (ptr->type == Type::unreachable ||
551       notifyCount->type == Type::unreachable) {
552     type = Type::unreachable;
553   }
554 }
555 
finalize()556 void AtomicFence::finalize() { type = Type::none; }
557 
finalize()558 void SIMDExtract::finalize() {
559   assert(vec);
560   switch (op) {
561     case ExtractLaneSVecI8x16:
562     case ExtractLaneUVecI8x16:
563     case ExtractLaneSVecI16x8:
564     case ExtractLaneUVecI16x8:
565     case ExtractLaneVecI32x4:
566       type = Type::i32;
567       break;
568     case ExtractLaneVecI64x2:
569       type = Type::i64;
570       break;
571     case ExtractLaneVecF32x4:
572       type = Type::f32;
573       break;
574     case ExtractLaneVecF64x2:
575       type = Type::f64;
576       break;
577     default:
578       WASM_UNREACHABLE("unexpected op");
579   }
580   if (vec->type == Type::unreachable) {
581     type = Type::unreachable;
582   }
583 }
584 
finalize()585 void SIMDReplace::finalize() {
586   assert(vec && value);
587   type = Type::v128;
588   if (vec->type == Type::unreachable || value->type == Type::unreachable) {
589     type = Type::unreachable;
590   }
591 }
592 
finalize()593 void SIMDShuffle::finalize() {
594   assert(left && right);
595   type = Type::v128;
596   if (left->type == Type::unreachable || right->type == Type::unreachable) {
597     type = Type::unreachable;
598   }
599 }
600 
finalize()601 void SIMDTernary::finalize() {
602   assert(a && b && c);
603   type = Type::v128;
604   if (a->type == Type::unreachable || b->type == Type::unreachable ||
605       c->type == Type::unreachable) {
606     type = Type::unreachable;
607   }
608 }
609 
finalize()610 void MemoryInit::finalize() {
611   assert(dest && offset && size);
612   type = Type::none;
613   if (dest->type == Type::unreachable || offset->type == Type::unreachable ||
614       size->type == Type::unreachable) {
615     type = Type::unreachable;
616   }
617 }
618 
finalize()619 void DataDrop::finalize() { type = Type::none; }
620 
finalize()621 void MemoryCopy::finalize() {
622   assert(dest && source && size);
623   type = Type::none;
624   if (dest->type == Type::unreachable || source->type == Type::unreachable ||
625       size->type == Type::unreachable) {
626     type = Type::unreachable;
627   }
628 }
629 
finalize()630 void MemoryFill::finalize() {
631   assert(dest && value && size);
632   type = Type::none;
633   if (dest->type == Type::unreachable || value->type == Type::unreachable ||
634       size->type == Type::unreachable) {
635     type = Type::unreachable;
636   }
637 }
638 
finalize()639 void SIMDShift::finalize() {
640   assert(vec && shift);
641   type = Type::v128;
642   if (vec->type == Type::unreachable || shift->type == Type::unreachable) {
643     type = Type::unreachable;
644   }
645 }
646 
finalize()647 void SIMDLoad::finalize() {
648   assert(ptr);
649   type = Type::v128;
650   if (ptr->type == Type::unreachable) {
651     type = Type::unreachable;
652   }
653 }
654 
getMemBytes()655 Index SIMDLoad::getMemBytes() {
656   switch (op) {
657     case LoadSplatVec8x16:
658       return 1;
659     case LoadSplatVec16x8:
660       return 2;
661     case LoadSplatVec32x4:
662     case Load32Zero:
663       return 4;
664     case LoadSplatVec64x2:
665     case LoadExtSVec8x8ToVecI16x8:
666     case LoadExtUVec8x8ToVecI16x8:
667     case LoadExtSVec16x4ToVecI32x4:
668     case LoadExtUVec16x4ToVecI32x4:
669     case LoadExtSVec32x2ToVecI64x2:
670     case LoadExtUVec32x2ToVecI64x2:
671     case Load64Zero:
672       return 8;
673   }
674   WASM_UNREACHABLE("unexpected op");
675 }
676 
set(Literal value_)677 Const* Const::set(Literal value_) {
678   value = value_;
679   type = value.type;
680   return this;
681 }
682 
finalize()683 void Const::finalize() { type = value.type; }
684 
isRelational()685 bool Unary::isRelational() { return op == EqZInt32 || op == EqZInt64; }
686 
finalize()687 void Unary::finalize() {
688   if (value->type == Type::unreachable) {
689     type = Type::unreachable;
690     return;
691   }
692   switch (op) {
693     case ClzInt32:
694     case CtzInt32:
695     case PopcntInt32:
696     case NegFloat32:
697     case AbsFloat32:
698     case CeilFloat32:
699     case FloorFloat32:
700     case TruncFloat32:
701     case NearestFloat32:
702     case SqrtFloat32:
703     case ClzInt64:
704     case CtzInt64:
705     case PopcntInt64:
706     case NegFloat64:
707     case AbsFloat64:
708     case CeilFloat64:
709     case FloorFloat64:
710     case TruncFloat64:
711     case NearestFloat64:
712     case SqrtFloat64:
713       type = value->type;
714       break;
715     case EqZInt32:
716     case EqZInt64:
717       type = Type::i32;
718       break;
719     case ExtendS8Int32:
720     case ExtendS16Int32:
721       type = Type::i32;
722       break;
723     case ExtendSInt32:
724     case ExtendUInt32:
725     case ExtendS8Int64:
726     case ExtendS16Int64:
727     case ExtendS32Int64:
728       type = Type::i64;
729       break;
730     case WrapInt64:
731       type = Type::i32;
732       break;
733     case PromoteFloat32:
734       type = Type::f64;
735       break;
736     case DemoteFloat64:
737       type = Type::f32;
738       break;
739     case TruncSFloat32ToInt32:
740     case TruncUFloat32ToInt32:
741     case TruncSFloat64ToInt32:
742     case TruncUFloat64ToInt32:
743     case TruncSatSFloat32ToInt32:
744     case TruncSatUFloat32ToInt32:
745     case TruncSatSFloat64ToInt32:
746     case TruncSatUFloat64ToInt32:
747     case ReinterpretFloat32:
748       type = Type::i32;
749       break;
750     case TruncSFloat32ToInt64:
751     case TruncUFloat32ToInt64:
752     case TruncSFloat64ToInt64:
753     case TruncUFloat64ToInt64:
754     case TruncSatSFloat32ToInt64:
755     case TruncSatUFloat32ToInt64:
756     case TruncSatSFloat64ToInt64:
757     case TruncSatUFloat64ToInt64:
758     case ReinterpretFloat64:
759       type = Type::i64;
760       break;
761     case ReinterpretInt32:
762     case ConvertSInt32ToFloat32:
763     case ConvertUInt32ToFloat32:
764     case ConvertSInt64ToFloat32:
765     case ConvertUInt64ToFloat32:
766       type = Type::f32;
767       break;
768     case ReinterpretInt64:
769     case ConvertSInt32ToFloat64:
770     case ConvertUInt32ToFloat64:
771     case ConvertSInt64ToFloat64:
772     case ConvertUInt64ToFloat64:
773       type = Type::f64;
774       break;
775     case SplatVecI8x16:
776     case SplatVecI16x8:
777     case SplatVecI32x4:
778     case SplatVecI64x2:
779     case SplatVecF32x4:
780     case SplatVecF64x2:
781     case NotVec128:
782     case AbsVecI8x16:
783     case AbsVecI16x8:
784     case AbsVecI32x4:
785     case NegVecI8x16:
786     case NegVecI16x8:
787     case NegVecI32x4:
788     case NegVecI64x2:
789     case AbsVecF32x4:
790     case NegVecF32x4:
791     case SqrtVecF32x4:
792     case CeilVecF32x4:
793     case FloorVecF32x4:
794     case TruncVecF32x4:
795     case NearestVecF32x4:
796     case AbsVecF64x2:
797     case NegVecF64x2:
798     case SqrtVecF64x2:
799     case CeilVecF64x2:
800     case FloorVecF64x2:
801     case TruncVecF64x2:
802     case NearestVecF64x2:
803     case TruncSatSVecF32x4ToVecI32x4:
804     case TruncSatUVecF32x4ToVecI32x4:
805     case TruncSatSVecF64x2ToVecI64x2:
806     case TruncSatUVecF64x2ToVecI64x2:
807     case ConvertSVecI32x4ToVecF32x4:
808     case ConvertUVecI32x4ToVecF32x4:
809     case ConvertSVecI64x2ToVecF64x2:
810     case ConvertUVecI64x2ToVecF64x2:
811     case WidenLowSVecI8x16ToVecI16x8:
812     case WidenHighSVecI8x16ToVecI16x8:
813     case WidenLowUVecI8x16ToVecI16x8:
814     case WidenHighUVecI8x16ToVecI16x8:
815     case WidenLowSVecI16x8ToVecI32x4:
816     case WidenHighSVecI16x8ToVecI32x4:
817     case WidenLowUVecI16x8ToVecI32x4:
818     case WidenHighUVecI16x8ToVecI32x4:
819       type = Type::v128;
820       break;
821     case AnyTrueVecI8x16:
822     case AnyTrueVecI16x8:
823     case AnyTrueVecI32x4:
824     case AnyTrueVecI64x2:
825     case AllTrueVecI8x16:
826     case AllTrueVecI16x8:
827     case AllTrueVecI32x4:
828     case AllTrueVecI64x2:
829     case BitmaskVecI8x16:
830     case BitmaskVecI16x8:
831     case BitmaskVecI32x4:
832       type = Type::i32;
833       break;
834 
835     case InvalidUnary:
836       WASM_UNREACHABLE("invalid unary op");
837   }
838 }
839 
isRelational()840 bool Binary::isRelational() {
841   switch (op) {
842     case EqInt32:
843     case NeInt32:
844     case LtSInt32:
845     case LtUInt32:
846     case LeSInt32:
847     case LeUInt32:
848     case GtSInt32:
849     case GtUInt32:
850     case GeSInt32:
851     case GeUInt32:
852     case EqInt64:
853     case NeInt64:
854     case LtSInt64:
855     case LtUInt64:
856     case LeSInt64:
857     case LeUInt64:
858     case GtSInt64:
859     case GtUInt64:
860     case GeSInt64:
861     case GeUInt64:
862     case EqFloat32:
863     case NeFloat32:
864     case LtFloat32:
865     case LeFloat32:
866     case GtFloat32:
867     case GeFloat32:
868     case EqFloat64:
869     case NeFloat64:
870     case LtFloat64:
871     case LeFloat64:
872     case GtFloat64:
873     case GeFloat64:
874       return true;
875     default:
876       return false;
877   }
878 }
879 
finalize()880 void Binary::finalize() {
881   assert(left && right);
882   if (left->type == Type::unreachable || right->type == Type::unreachable) {
883     type = Type::unreachable;
884   } else if (isRelational()) {
885     type = Type::i32;
886   } else {
887     type = left->type;
888   }
889 }
890 
finalize(Type type_)891 void Select::finalize(Type type_) { type = type_; }
892 
finalize()893 void Select::finalize() {
894   assert(ifTrue && ifFalse);
895   if (ifTrue->type == Type::unreachable || ifFalse->type == Type::unreachable ||
896       condition->type == Type::unreachable) {
897     type = Type::unreachable;
898   } else {
899     type = Type::getLeastUpperBound(ifTrue->type, ifFalse->type);
900   }
901 }
902 
finalize()903 void Drop::finalize() {
904   if (value->type == Type::unreachable) {
905     type = Type::unreachable;
906   } else {
907     type = Type::none;
908   }
909 }
910 
make64()911 void MemorySize::make64() { type = ptrType = Type::i64; }
finalize()912 void MemorySize::finalize() { type = ptrType; }
913 
make64()914 void MemoryGrow::make64() { type = ptrType = Type::i64; }
finalize()915 void MemoryGrow::finalize() {
916   if (delta->type == Type::unreachable) {
917     type = Type::unreachable;
918   } else {
919     type = ptrType;
920   }
921 }
922 
finalize(HeapType heapType)923 void RefNull::finalize(HeapType heapType) { type = Type(heapType, true); }
924 
finalize(Type type_)925 void RefNull::finalize(Type type_) {
926   assert(type_ == Type::unreachable || type_.isNullable());
927   type = type_;
928 }
929 
finalize()930 void RefNull::finalize() {
931   assert(type == Type::unreachable || type.isNullable());
932 }
933 
finalize()934 void RefIsNull::finalize() {
935   if (value->type == Type::unreachable) {
936     type = Type::unreachable;
937     return;
938   }
939   type = Type::i32;
940 }
941 
finalize()942 void RefFunc::finalize() { type = Type::funcref; }
943 
finalize()944 void RefEq::finalize() {
945   if (left->type == Type::unreachable || right->type == Type::unreachable) {
946     type = Type::unreachable;
947   } else {
948     type = Type::i32;
949   }
950 }
951 
finalize()952 void Try::finalize() {
953   type = Type::getLeastUpperBound(body->type, catchBody->type);
954 }
955 
finalize(Type type_)956 void Try::finalize(Type type_) {
957   type = type_;
958   if (type == Type::none && body->type == Type::unreachable &&
959       catchBody->type == Type::unreachable) {
960     type = Type::unreachable;
961   }
962 }
963 
finalize()964 void Throw::finalize() { type = Type::unreachable; }
965 
finalize()966 void Rethrow::finalize() { type = Type::unreachable; }
967 
finalize()968 void BrOnExn::finalize() {
969   if (exnref->type == Type::unreachable) {
970     type = Type::unreachable;
971   } else {
972     type = Type::exnref;
973   }
974 }
975 
finalize()976 void TupleMake::finalize() {
977   std::vector<Type> types;
978   for (auto* op : operands) {
979     if (op->type == Type::unreachable) {
980       type = Type::unreachable;
981       return;
982     }
983     types.push_back(op->type);
984   }
985   type = Type(types);
986 }
987 
finalize()988 void TupleExtract::finalize() {
989   if (tuple->type == Type::unreachable) {
990     type = Type::unreachable;
991   } else {
992     type = tuple->type[index];
993   }
994 }
995 
finalize()996 void I31New::finalize() {
997   if (value->type == Type::unreachable) {
998     type = Type::unreachable;
999   } else {
1000     type = Type::i31ref;
1001   }
1002 }
1003 
finalize()1004 void I31Get::finalize() {
1005   if (i31->type == Type::unreachable) {
1006     type = Type::unreachable;
1007   } else {
1008     type = Type::i32;
1009   }
1010 }
1011 
1012 // TODO (gc): ref.test
1013 // TODO (gc): ref.cast
1014 // TODO (gc): br_on_cast
1015 // TODO (gc): rtt.canon
1016 // TODO (gc): rtt.sub
1017 // TODO (gc): struct.new
1018 // TODO (gc): struct.get
1019 // TODO (gc): struct.set
1020 // TODO (gc): array.new
1021 // TODO (gc): array.get
1022 // TODO (gc): array.set
1023 // TODO (gc): array.len
1024 
getNumParams()1025 size_t Function::getNumParams() { return sig.params.size(); }
1026 
getNumVars()1027 size_t Function::getNumVars() { return vars.size(); }
1028 
getNumLocals()1029 size_t Function::getNumLocals() { return sig.params.size() + vars.size(); }
1030 
isParam(Index index)1031 bool Function::isParam(Index index) {
1032   size_t size = sig.params.size();
1033   assert(index < size + vars.size());
1034   return index < size;
1035 }
1036 
isVar(Index index)1037 bool Function::isVar(Index index) {
1038   auto base = getVarIndexBase();
1039   assert(index < base + vars.size());
1040   return index >= base;
1041 }
1042 
hasLocalName(Index index) const1043 bool Function::hasLocalName(Index index) const {
1044   return localNames.find(index) != localNames.end();
1045 }
1046 
getLocalName(Index index)1047 Name Function::getLocalName(Index index) { return localNames.at(index); }
1048 
setLocalName(Index index,Name name)1049 void Function::setLocalName(Index index, Name name) {
1050   assert(index < getNumLocals());
1051   localNames[index] = name;
1052 }
1053 
getLocalNameOrDefault(Index index)1054 Name Function::getLocalNameOrDefault(Index index) {
1055   auto nameIt = localNames.find(index);
1056   if (nameIt != localNames.end()) {
1057     return nameIt->second;
1058   }
1059   // this is an unnamed local
1060   return Name();
1061 }
1062 
getLocalNameOrGeneric(Index index)1063 Name Function::getLocalNameOrGeneric(Index index) {
1064   auto nameIt = localNames.find(index);
1065   if (nameIt != localNames.end()) {
1066     return nameIt->second;
1067   }
1068   return Name::fromInt(index);
1069 }
1070 
getLocalIndex(Name name)1071 Index Function::getLocalIndex(Name name) {
1072   auto iter = localIndices.find(name);
1073   if (iter == localIndices.end()) {
1074     Fatal() << "Function::getLocalIndex: " << name << " does not exist";
1075   }
1076   return iter->second;
1077 }
1078 
getVarIndexBase()1079 Index Function::getVarIndexBase() { return sig.params.size(); }
1080 
getLocalType(Index index)1081 Type Function::getLocalType(Index index) {
1082   auto numParams = sig.params.size();
1083   if (index < numParams) {
1084     return sig.params[index];
1085   } else if (isVar(index)) {
1086     return vars[index - numParams];
1087   } else {
1088     WASM_UNREACHABLE("invalid local index");
1089   }
1090 }
1091 
clearNames()1092 void Function::clearNames() { localNames.clear(); }
1093 
clearDebugInfo()1094 void Function::clearDebugInfo() {
1095   localIndices.clear();
1096   debugLocations.clear();
1097   prologLocation.clear();
1098   epilogLocation.clear();
1099 }
1100 
1101 template<typename Map>
1102 typename Map::mapped_type&
getModuleElement(Map & m,Name name,const std::string & funcName)1103 getModuleElement(Map& m, Name name, const std::string& funcName) {
1104   auto iter = m.find(name);
1105   if (iter == m.end()) {
1106     Fatal() << "Module::" << funcName << ": " << name << " does not exist";
1107   }
1108   return iter->second;
1109 }
1110 
getExport(Name name)1111 Export* Module::getExport(Name name) {
1112   return getModuleElement(exportsMap, name, "getExport");
1113 }
1114 
getFunction(Name name)1115 Function* Module::getFunction(Name name) {
1116   return getModuleElement(functionsMap, name, "getFunction");
1117 }
1118 
getGlobal(Name name)1119 Global* Module::getGlobal(Name name) {
1120   return getModuleElement(globalsMap, name, "getGlobal");
1121 }
1122 
getEvent(Name name)1123 Event* Module::getEvent(Name name) {
1124   return getModuleElement(eventsMap, name, "getEvent");
1125 }
1126 
1127 template<typename Map>
getModuleElementOrNull(Map & m,Name name)1128 typename Map::mapped_type getModuleElementOrNull(Map& m, Name name) {
1129   auto iter = m.find(name);
1130   if (iter == m.end()) {
1131     return nullptr;
1132   }
1133   return iter->second;
1134 }
1135 
getExportOrNull(Name name)1136 Export* Module::getExportOrNull(Name name) {
1137   return getModuleElementOrNull(exportsMap, name);
1138 }
1139 
getFunctionOrNull(Name name)1140 Function* Module::getFunctionOrNull(Name name) {
1141   return getModuleElementOrNull(functionsMap, name);
1142 }
1143 
getGlobalOrNull(Name name)1144 Global* Module::getGlobalOrNull(Name name) {
1145   return getModuleElementOrNull(globalsMap, name);
1146 }
1147 
getEventOrNull(Name name)1148 Event* Module::getEventOrNull(Name name) {
1149   return getModuleElementOrNull(eventsMap, name);
1150 }
1151 
1152 // TODO(@warchant): refactor all usages to use variant with unique_ptr
1153 template<typename Vector, typename Map, typename Elem>
addModuleElement(Vector & v,Map & m,Elem * curr,std::string funcName)1154 Elem* addModuleElement(Vector& v, Map& m, Elem* curr, std::string funcName) {
1155   if (!curr->name.is()) {
1156     Fatal() << "Module::" << funcName << ": empty name";
1157   }
1158   if (getModuleElementOrNull(m, curr->name)) {
1159     Fatal() << "Module::" << funcName << ": " << curr->name
1160             << " already exists";
1161   }
1162   v.push_back(std::unique_ptr<Elem>(curr));
1163   m[curr->name] = curr;
1164   return curr;
1165 }
1166 
1167 template<typename Vector, typename Map, typename Elem>
addModuleElement(Vector & v,Map & m,std::unique_ptr<Elem> curr,std::string funcName)1168 Elem* addModuleElement(Vector& v,
1169                        Map& m,
1170                        std::unique_ptr<Elem> curr,
1171                        std::string funcName) {
1172   if (!curr->name.is()) {
1173     Fatal() << "Module::" << funcName << ": empty name";
1174   }
1175   if (getModuleElementOrNull(m, curr->name)) {
1176     Fatal() << "Module::" << funcName << ": " << curr->name
1177             << " already exists";
1178   }
1179   auto* ret = m[curr->name] = curr.get();
1180   v.push_back(std::move(curr));
1181   return ret;
1182 }
1183 
addExport(Export * curr)1184 Export* Module::addExport(Export* curr) {
1185   return addModuleElement(exports, exportsMap, curr, "addExport");
1186 }
1187 
addFunction(Function * curr)1188 Function* Module::addFunction(Function* curr) {
1189   return addModuleElement(functions, functionsMap, curr, "addFunction");
1190 }
1191 
addGlobal(Global * curr)1192 Global* Module::addGlobal(Global* curr) {
1193   return addModuleElement(globals, globalsMap, curr, "addGlobal");
1194 }
1195 
addEvent(Event * curr)1196 Event* Module::addEvent(Event* curr) {
1197   return addModuleElement(events, eventsMap, curr, "addEvent");
1198 }
1199 
addExport(std::unique_ptr<Export> curr)1200 Export* Module::addExport(std::unique_ptr<Export> curr) {
1201   return addModuleElement(exports, exportsMap, std::move(curr), "addExport");
1202 }
1203 
addFunction(std::unique_ptr<Function> curr)1204 Function* Module::addFunction(std::unique_ptr<Function> curr) {
1205   return addModuleElement(
1206     functions, functionsMap, std::move(curr), "addFunction");
1207 }
1208 
addGlobal(std::unique_ptr<Global> curr)1209 Global* Module::addGlobal(std::unique_ptr<Global> curr) {
1210   return addModuleElement(globals, globalsMap, std::move(curr), "addGlobal");
1211 }
1212 
addEvent(std::unique_ptr<Event> curr)1213 Event* Module::addEvent(std::unique_ptr<Event> curr) {
1214   return addModuleElement(events, eventsMap, std::move(curr), "addEvent");
1215 }
1216 
addStart(const Name & s)1217 void Module::addStart(const Name& s) { start = s; }
1218 
1219 template<typename Vector, typename Map>
removeModuleElement(Vector & v,Map & m,Name name)1220 void removeModuleElement(Vector& v, Map& m, Name name) {
1221   m.erase(name);
1222   for (size_t i = 0; i < v.size(); i++) {
1223     if (v[i]->name == name) {
1224       v.erase(v.begin() + i);
1225       break;
1226     }
1227   }
1228 }
1229 
removeExport(Name name)1230 void Module::removeExport(Name name) {
1231   removeModuleElement(exports, exportsMap, name);
1232 }
removeFunction(Name name)1233 void Module::removeFunction(Name name) {
1234   removeModuleElement(functions, functionsMap, name);
1235 }
removeGlobal(Name name)1236 void Module::removeGlobal(Name name) {
1237   removeModuleElement(globals, globalsMap, name);
1238 }
removeEvent(Name name)1239 void Module::removeEvent(Name name) {
1240   removeModuleElement(events, eventsMap, name);
1241 }
1242 
1243 template<typename Vector, typename Map, typename Elem>
removeModuleElements(Vector & v,Map & m,std::function<bool (Elem * elem)> pred)1244 void removeModuleElements(Vector& v,
1245                           Map& m,
1246                           std::function<bool(Elem* elem)> pred) {
1247   for (auto it = m.begin(); it != m.end();) {
1248     if (pred(it->second)) {
1249       it = m.erase(it);
1250     } else {
1251       it++;
1252     }
1253   }
1254   v.erase(
1255     std::remove_if(v.begin(), v.end(), [&](auto& e) { return pred(e.get()); }),
1256     v.end());
1257 }
1258 
removeExports(std::function<bool (Export *)> pred)1259 void Module::removeExports(std::function<bool(Export*)> pred) {
1260   removeModuleElements(exports, exportsMap, pred);
1261 }
removeFunctions(std::function<bool (Function *)> pred)1262 void Module::removeFunctions(std::function<bool(Function*)> pred) {
1263   removeModuleElements(functions, functionsMap, pred);
1264 }
removeGlobals(std::function<bool (Global *)> pred)1265 void Module::removeGlobals(std::function<bool(Global*)> pred) {
1266   removeModuleElements(globals, globalsMap, pred);
1267 }
removeEvents(std::function<bool (Event *)> pred)1268 void Module::removeEvents(std::function<bool(Event*)> pred) {
1269   removeModuleElements(events, eventsMap, pred);
1270 }
1271 
updateMaps()1272 void Module::updateMaps() {
1273   functionsMap.clear();
1274   for (auto& curr : functions) {
1275     functionsMap[curr->name] = curr.get();
1276   }
1277   exportsMap.clear();
1278   for (auto& curr : exports) {
1279     exportsMap[curr->name] = curr.get();
1280   }
1281   globalsMap.clear();
1282   for (auto& curr : globals) {
1283     globalsMap[curr->name] = curr.get();
1284   }
1285   eventsMap.clear();
1286   for (auto& curr : events) {
1287     eventsMap[curr->name] = curr.get();
1288   }
1289 }
1290 
clearDebugInfo()1291 void Module::clearDebugInfo() { debugInfoFileNames.clear(); }
1292 
1293 } // namespace wasm
1294