Home | History | Annotate | Download | only in asmjs 
      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 
     82   Handle<JSMessageObject> error_message() const { return error_message_; }
     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 
     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_;
    104     FFIUseSignature(Variable* v, Zone* zone)
    105         : var(v), arg_types_(zone), return_type_(nullptr) {}
    106   };
    107 
    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 
    131     explicit VariableInfo(AsmType* t) : type_(t) {}
    132 
    133     VariableInfo* Clone(Zone* zone) const;
    134 
    135     bool IsMutable() const {
    136       return mutability_ == kLocal || mutability_ == kMutableGlobal;
    137     }
    138 
    139     bool IsGlobal() const {
    140       return mutability_ == kImmutableGlobal || mutability_ == kConstGlobal ||
    141              mutability_ == kMutableGlobal;
    142     }
    143 
    144     bool IsStdlib() const { return standard_member_ == kStdlib; }
    145     bool IsFFI() const { return standard_member_ == kFFI; }
    146     bool IsHeap() const { return standard_member_ == kHeap; }
    147 
    148     void MarkDefined() { missing_definition_ = false; }
    149     void SetFirstForwardUse(const MessageLocation& source_location);
    150 
    151     StandardMember standard_member() const { return standard_member_; }
    152     void set_standard_member(StandardMember standard_member) {
    153       standard_member_ = standard_member;
    154     }
    155 
    156     AsmType* type() const { return type_; }
    157     void set_type(AsmType* type) { type_ = type; }
    158 
    159     Mutability mutability() const { return mutability_; }
    160     void set_mutability(Mutability mutability) { mutability_ = mutability; }
    161 
    162     bool missing_definition() const { return missing_definition_; }
    163 
    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 {
    182     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 
    189     ~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 {
    207       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;
    221     void AddUseAsm(const AstNode& node) { use_asm_.AddNewElement(node); }
    222     void AddGlobal(const AstNode& node) { globals_.AddNewElement(node); }
    223     void AddFunction(const AstNode& node) { functions_.AddNewElement(node); }
    224     void AddTable(const AstNode& node) { tables_.AddNewElement(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