1 // Copyright 2016 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef SRC_ASMJS_ASM_TYPER_H_
6 #define SRC_ASMJS_ASM_TYPER_H_
7 
8 #include <cstdint>
9 #include <string>
10 #include <unordered_map>
11 #include <unordered_set>
12 
13 #include "src/allocation.h"
14 #include "src/asmjs/asm-types.h"
15 #include "src/ast/ast-type-bounds.h"
16 #include "src/ast/ast-types.h"
17 #include "src/ast/ast.h"
18 #include "src/effects.h"
19 #include "src/messages.h"
20 #include "src/type-info.h"
21 #include "src/zone/zone-containers.h"
22 #include "src/zone/zone.h"
23 
24 namespace v8 {
25 namespace internal {
26 namespace wasm {
27 
28 class AsmType;
29 class AsmTyperHarnessBuilder;
30 class SourceLayoutTracker;
31 
32 class AsmTyper final {
33  public:
34   enum StandardMember {
35     kHeap = -4,
36     kFFI = -3,
37     kStdlib = -2,
38     kModule = -1,
39     kNone = 0,
40     kInfinity,
41     kNaN,
42     kMathAcos,
43     kMathAsin,
44     kMathAtan,
45     kMathCos,
46     kMathSin,
47     kMathTan,
48     kMathExp,
49     kMathLog,
50     kMathCeil,
51     kMathFloor,
52     kMathSqrt,
53     kMathAbs,
54     kMathClz32,
55     kMathMin,
56     kMathMax,
57     kMathAtan2,
58     kMathPow,
59     kMathImul,
60     kMathFround,
61     kMathE,
62     kMathLN10,
63     kMathLN2,
64     kMathLOG2E,
65     kMathLOG10E,
66     kMathPI,
67     kMathSQRT1_2,
68     kMathSQRT2,
69   };
70 
71   ~AsmTyper() = default;
72   AsmTyper(Isolate* isolate, Zone* zone, Handle<Script> script,
73            FunctionLiteral* root);
74 
75   bool Validate();
76   // Do asm.js validation in phases (to interleave with conversion to wasm).
77   bool ValidateBeforeFunctionsPhase();
78   bool ValidateInnerFunction(FunctionDeclaration* decl);
79   bool ValidateAfterFunctionsPhase();
80   void ClearFunctionNodeTypes();
81 
error_message()82   Handle<JSMessageObject> error_message() const { return error_message_; }
message_location()83   const MessageLocation* message_location() const { return &message_location_; }
84 
85   AsmType* TriggerParsingError();
86 
87   AsmType* TypeOf(AstNode* node) const;
88   AsmType* TypeOf(Variable* v) const;
89   StandardMember VariableAsStandardMember(Variable* var);
90 
91   // Allow the asm-wasm-builder to trigger failures (for interleaved
92   // validating).
93   AsmType* FailWithMessage(const char* text);
94 
95   typedef std::unordered_set<StandardMember, std::hash<int> > StdlibSet;
96 
StdlibUses()97   StdlibSet StdlibUses() const { return stdlib_uses_; }
98 
99   // Each FFI import has a usage-site signature associated with it.
100   struct FFIUseSignature {
101     Variable* var;
102     ZoneVector<AsmType*> arg_types_;
103     AsmType* return_type_;
FFIUseSignatureFFIUseSignature104     FFIUseSignature(Variable* v, Zone* zone)
105         : var(v), arg_types_(zone), return_type_(nullptr) {}
106   };
107 
FFIUseSignatures()108   const ZoneVector<FFIUseSignature>& FFIUseSignatures() {
109     return ffi_use_signatures_;
110   }
111 
112  private:
113   friend class v8::internal::wasm::AsmTyperHarnessBuilder;
114 
115   class VariableInfo : public ZoneObject {
116    public:
117     enum Mutability {
118       kInvalidMutability,
119       kLocal,
120       kMutableGlobal,
121       // *VIOLATION* We support const variables in asm.js, as per the
122       //
123       // https://discourse.wicg.io/t/allow-const-global-variables/684
124       //
125       // Global const variables are treated as if they were numeric literals,
126       // and can be used anywhere a literal can be used.
127       kConstGlobal,
128       kImmutableGlobal,
129     };
130 
VariableInfo(AsmType * t)131     explicit VariableInfo(AsmType* t) : type_(t) {}
132 
133     VariableInfo* Clone(Zone* zone) const;
134 
IsMutable()135     bool IsMutable() const {
136       return mutability_ == kLocal || mutability_ == kMutableGlobal;
137     }
138 
IsGlobal()139     bool IsGlobal() const {
140       return mutability_ == kImmutableGlobal || mutability_ == kConstGlobal ||
141              mutability_ == kMutableGlobal;
142     }
143 
IsStdlib()144     bool IsStdlib() const { return standard_member_ == kStdlib; }
IsFFI()145     bool IsFFI() const { return standard_member_ == kFFI; }
IsHeap()146     bool IsHeap() const { return standard_member_ == kHeap; }
147 
MarkDefined()148     void MarkDefined() { missing_definition_ = false; }
149     void SetFirstForwardUse(const MessageLocation& source_location);
150 
standard_member()151     StandardMember standard_member() const { return standard_member_; }
set_standard_member(StandardMember standard_member)152     void set_standard_member(StandardMember standard_member) {
153       standard_member_ = standard_member;
154     }
155 
type()156     AsmType* type() const { return type_; }
set_type(AsmType * type)157     void set_type(AsmType* type) { type_ = type; }
158 
mutability()159     Mutability mutability() const { return mutability_; }
set_mutability(Mutability mutability)160     void set_mutability(Mutability mutability) { mutability_ = mutability; }
161 
missing_definition()162     bool missing_definition() const { return missing_definition_; }
163 
source_location()164     const MessageLocation* source_location() { return &source_location_; }
165 
166     static VariableInfo* ForSpecialSymbol(Zone* zone,
167                                           StandardMember standard_member);
168 
169    private:
170     AsmType* type_;
171     StandardMember standard_member_ = kNone;
172     Mutability mutability_ = kInvalidMutability;
173     // missing_definition_ is set to true for forward definition - i.e., use
174     // before definition.
175     bool missing_definition_ = false;
176     // Used for error messages.
177     MessageLocation source_location_;
178   };
179 
180   // RAII-style manager for the in_function_ member variable.
181   struct FunctionScope {
FunctionScopeFunctionScope182     explicit FunctionScope(AsmTyper* typer) : typer_(typer) {
183       DCHECK(!typer_->in_function_);
184       typer_->in_function_ = true;
185       typer_->local_scope_.Clear();
186       typer_->return_type_ = AsmType::None();
187     }
188 
~FunctionScopeFunctionScope189     ~FunctionScope() {
190       DCHECK(typer_->in_function_);
191       typer_->in_function_ = false;
192     }
193 
194     AsmTyper* typer_;
195   };
196 
197   // FlattenedStatements is an iterator class for ZoneList<Statement*> that
198   // flattens the Block construct in the AST. This is here because we need it in
199   // the tests.
200   class FlattenedStatements {
201    public:
202     explicit FlattenedStatements(Zone* zone, ZoneList<Statement*>* s);
203     Statement* Next();
204 
205    private:
206     struct Context {
ContextContext207       explicit Context(ZoneList<Statement*>* s) : statements_(s) {}
208       ZoneList<Statement*>* statements_;
209       int next_index_ = 0;
210     };
211 
212     ZoneVector<Context> context_stack_;
213 
214     DISALLOW_IMPLICIT_CONSTRUCTORS(FlattenedStatements);
215   };
216 
217   class SourceLayoutTracker {
218    public:
219     SourceLayoutTracker() = default;
220     bool IsValid() const;
AddUseAsm(const AstNode & node)221     void AddUseAsm(const AstNode& node) { use_asm_.AddNewElement(node); }
AddGlobal(const AstNode & node)222     void AddGlobal(const AstNode& node) { globals_.AddNewElement(node); }
AddFunction(const AstNode & node)223     void AddFunction(const AstNode& node) { functions_.AddNewElement(node); }
AddTable(const AstNode & node)224     void AddTable(const AstNode& node) { tables_.AddNewElement(node); }
AddExport(const AstNode & node)225     void AddExport(const AstNode& node) { exports_.AddNewElement(node); }
226 
227    private:
228     class Section {
229      public:
230       Section() = default;
231       Section(const Section&) = default;
232       Section& operator=(const Section&) = default;
233 
234       void AddNewElement(const AstNode& node);
235       bool IsPrecededBy(const Section& other) const;
236 
237      private:
238       int start_ = kNoSourcePosition;
239       int end_ = kNoSourcePosition;
240     };
241 
242     Section use_asm_;
243     Section globals_;
244     Section functions_;
245     Section tables_;
246     Section exports_;
247 
248     DISALLOW_COPY_AND_ASSIGN(SourceLayoutTracker);
249   };
250 
251   using ObjectTypeMap = ZoneMap<std::string, VariableInfo*>;
252   void InitializeStdlib();
253   void SetTypeOf(AstNode* node, AsmType* type);
254 
255   void AddForwardReference(VariableProxy* proxy, VariableInfo* info);
256   bool AddGlobal(Variable* global, VariableInfo* info);
257   bool AddLocal(Variable* global, VariableInfo* info);
258   // Used for 5.5 GlobalVariableTypeAnnotations
259   VariableInfo* ImportLookup(Property* expr);
260   // 3.3 Environment Lookup
261   // NOTE: In the spec, the lookup function's prototype is
262   //
263   //   Lookup(Delta, Gamma, x)
264   //
265   // Delta is the global_scope_ member, and Gamma, local_scope_.
266   VariableInfo* Lookup(Variable* variable) const;
267 
268   // All of the ValidateXXX methods below return AsmType::None() in case of
269   // validation failure.
270 
271   // 6.1 ValidateModule
272   AsmType* ValidateModuleBeforeFunctionsPhase(FunctionLiteral* fun);
273   AsmType* ValidateModuleFunction(FunctionDeclaration* fun_decl);
274   AsmType* ValidateModuleFunctions(FunctionLiteral* fun);
275   AsmType* ValidateModuleAfterFunctionsPhase(FunctionLiteral* fun);
276   AsmType* ValidateGlobalDeclaration(Assignment* assign);
277   // 6.2 ValidateExport
278   AsmType* ExportType(VariableProxy* fun_export);
279   AsmType* ValidateExport(ReturnStatement* exports);
280   // 6.3 ValidateFunctionTable
281   AsmType* ValidateFunctionTable(Assignment* assign);
282   // 6.4 ValidateFunction
283   AsmType* ValidateFunction(FunctionDeclaration* fun_decl);
284   // 6.5 ValidateStatement
285   AsmType* ValidateStatement(Statement* statement);
286   // 6.5.1 BlockStatement
287   AsmType* ValidateBlockStatement(Block* block);
288   // 6.5.2 ExpressionStatement
289   AsmType* ValidateExpressionStatement(ExpressionStatement* expr);
290   // 6.5.3 EmptyStatement
291   AsmType* ValidateEmptyStatement(EmptyStatement* empty);
292   // 6.5.4 IfStatement
293   AsmType* ValidateIfStatement(IfStatement* if_stmt);
294   // 6.5.5 ReturnStatement
295   AsmType* ValidateReturnStatement(ReturnStatement* ret_stmt);
296   // 6.5.6 IterationStatement
297   // 6.5.6.a WhileStatement
298   AsmType* ValidateWhileStatement(WhileStatement* while_stmt);
299   // 6.5.6.b DoWhileStatement
300   AsmType* ValidateDoWhileStatement(DoWhileStatement* do_while);
301   // 6.5.6.c ForStatement
302   AsmType* ValidateForStatement(ForStatement* for_stmt);
303   // 6.5.7 BreakStatement
304   AsmType* ValidateBreakStatement(BreakStatement* brk_stmt);
305   // 6.5.8 ContinueStatement
306   AsmType* ValidateContinueStatement(ContinueStatement* cont_stmt);
307   // 6.5.9 LabelledStatement
308   // NOTE: we don't need to handle these: Labelled statements are
309   // BreakableStatements in our AST, but BreakableStatement is not a concrete
310   // class -- and we're handling all of BreakableStatement's subclasses.
311   // 6.5.10 SwitchStatement
312   AsmType* ValidateSwitchStatement(SwitchStatement* stmt);
313   // 6.6 ValidateCase
314   AsmType* ValidateCase(CaseClause* label, int32_t* case_lbl);
315   // 6.7 ValidateDefault
316   AsmType* ValidateDefault(CaseClause* label);
317   // 6.8 ValidateExpression
318   AsmType* ValidateExpression(Expression* expr);
319   AsmType* ValidateCompareOperation(CompareOperation* cmp);
320   AsmType* ValidateBinaryOperation(BinaryOperation* binop);
321   // 6.8.1 Expression
322   AsmType* ValidateCommaExpression(BinaryOperation* comma);
323   // 6.8.2 NumericLiteral
324   AsmType* ValidateNumericLiteral(Literal* literal);
325   // 6.8.3 Identifier
326   AsmType* ValidateIdentifier(VariableProxy* proxy);
327   // 6.8.4 CallExpression
328   AsmType* ValidateCallExpression(Call* call);
329   // 6.8.5 MemberExpression
330   AsmType* ValidateMemberExpression(Property* prop);
331   // 6.8.6 AssignmentExpression
332   AsmType* ValidateAssignmentExpression(Assignment* assignment);
333   // 6.8.7 UnaryExpression
334   AsmType* ValidateUnaryExpression(UnaryOperation* unop);
335   // 6.8.8 MultiplicativeExpression
336   AsmType* ValidateMultiplicativeExpression(BinaryOperation* binop);
337   // 6.8.9 AdditiveExpression
338   AsmType* ValidateAdditiveExpression(BinaryOperation* binop,
339                                       uint32_t intish_count);
340   // 6.8.10 ShiftExpression
341   AsmType* ValidateShiftExpression(BinaryOperation* binop);
342   // 6.8.11 RelationalExpression
343   AsmType* ValidateRelationalExpression(CompareOperation* cmpop);
344   // 6.8.12 EqualityExpression
345   AsmType* ValidateEqualityExpression(CompareOperation* cmpop);
346   // 6.8.13 BitwiseANDExpression
347   AsmType* ValidateBitwiseANDExpression(BinaryOperation* binop);
348   // 6.8.14 BitwiseXORExpression
349   AsmType* ValidateBitwiseXORExpression(BinaryOperation* binop);
350   // 6.8.15 BitwiseORExpression
351   AsmType* ValidateBitwiseORExpression(BinaryOperation* binop);
352   // 6.8.16 ConditionalExpression
353   AsmType* ValidateConditionalExpression(Conditional* cond);
354   // 6.9 ValidateCall
355   AsmType* ValidateCall(AsmType* return_type, Call* call);
356   // 6.10 ValidateHeapAccess
357   enum HeapAccessType { LoadFromHeap, StoreToHeap };
358   AsmType* ValidateHeapAccess(Property* heap, HeapAccessType access_type);
359   // 6.11 ValidateFloatCoercion
360   bool IsCallToFround(Call* call);
361   AsmType* ValidateFloatCoercion(Call* call);
362 
363   // 5.1 ParameterTypeAnnotations
364   AsmType* ParameterTypeAnnotations(Variable* parameter,
365                                     Expression* annotation);
366   // 5.2 ReturnTypeAnnotations
367   AsmType* ReturnTypeAnnotations(Expression* ret_expr);
368   // 5.4 VariableTypeAnnotations
369   // 5.5 GlobalVariableTypeAnnotations
370   AsmType* VariableTypeAnnotations(
371       Expression* initializer,
372       VariableInfo::Mutability global = VariableInfo::kLocal);
373   AsmType* ImportExpression(Property* import);
374   AsmType* NewHeapView(CallNew* new_heap_view);
375 
376   Isolate* isolate_;
377   Zone* zone_;
378   Handle<Script> script_;
379   FunctionLiteral* root_;
380   bool in_function_ = false;
381 
382   AsmType* return_type_ = nullptr;
383 
384   ZoneVector<VariableInfo*> forward_definitions_;
385   ZoneVector<FFIUseSignature> ffi_use_signatures_;
386   ObjectTypeMap stdlib_types_;
387   ObjectTypeMap stdlib_math_types_;
388 
389   // The ASM module name. This member is used to prevent globals from redefining
390   // the module name.
391   VariableInfo* module_info_;
392   Handle<String> module_name_;
393 
394   // 3 Environments
395   ZoneHashMap global_scope_;  // 3.1 Global environment
396   ZoneHashMap local_scope_;   // 3.2 Variable environment
397 
398   std::uintptr_t stack_limit_;
399   bool stack_overflow_ = false;
400   std::unordered_map<AstNode*, AsmType*> module_node_types_;
401   std::unordered_map<AstNode*, AsmType*> function_node_types_;
402   static const int kErrorMessageLimit = 128;
403   AsmType* fround_type_;
404   AsmType* ffi_type_;
405   Handle<JSMessageObject> error_message_;
406   MessageLocation message_location_;
407   StdlibSet stdlib_uses_;
408 
409   SourceLayoutTracker source_layout_;
410   ReturnStatement* module_return_;
411   ZoneVector<Assignment*> function_pointer_tables_;
412 
413   DISALLOW_IMPLICIT_CONSTRUCTORS(AsmTyper);
414 };
415 
416 }  // namespace wasm
417 }  // namespace internal
418 }  // namespace v8
419 
420 #endif  // SRC_ASMJS_ASM_TYPER_H_
421