import * as a from '../parser/ast' ; import { wat2wasm , convertMiBToPage } from '../wasm' ; import { CodegenContext } from './context' ; import { SExp , beautify } from 's-exify' ; export function genWASM ( mod , opts ) { return wat2wasm ( genWAT ( mod , opts ) ) ; } export function genWAT ( mod , opts ) { return beautify ( codegenModule ( mod , new CodegenContext ( ) , { exports : opts . exports , pageCount : convertMiBToPage ( opts . memorySize ) , } ) ) ; } const exp = ( ... nodes ) : SExp => nodes ; const str = ( raw ) => `"${ raw . replace ( '"' , '\\"' ) }"` ; const wat = ( name ) => `$${ name }` ; const sys = ( name ) => wat ( `/${ name }` ) ; function codegenModule ( mod , ctx , opts ) { const modE = exp ( 'module' ) ; modE . push ( exp ( 'import' , str ( 'js' ) , str ( 'memory' ) , exp ( 'memory' , String ( opts . pageCount ) ) ) ) ; modE . push ( ... codegenRegistry ( ctx ) ) ; for ( const decl of mod . value . decls ) { ctx . pushName ( decl . value . name . value ) ; } for ( const decl of mod . value . decls ) { const declE = codegenGlobalDecl ( decl , ctx ) ; if ( declE ) modE . push ( declE ) ; } modE . push ( ... codegenStartFunc ( ctx ) ) ; for ( const [ name , { types , sizes } ] of ctx . tupleConstructors . entries ( ) ) { modE . push ( codegenTupleConstructor ( name , types , sizes ) ) ; } for ( const exportName of opts . exports ) { const watName = ctx . getGlobalWATName ( exportName ) ! ; modE . push ( exp ( 'export' , str ( exportName ) , exp ( 'func' , wat ( watName ) ) ) ) ; } return modE ; } function * codegenRegistry ( ctx ) { const reg = ( name , ty ) => exp ( 'global' , sys ( name ) , exp ( 'mut' , ty ) , exp ( `${ ty }.const` , '0' ) ) ; yield reg ( 'reg/addr' , 'i32' ) ; yield reg ( 'reg/i32/1' , 'i32' ) ; yield reg ( 'reg/i32/2' , 'i32' ) ; yield reg ( 'reg/f64/1' , 'f64' ) ; yield reg ( 'reg/f64/2' , 'f64' ) ; } function * codegenStartFunc ( ctx ) { if ( ctx . globalInitializers . length === 0 ) { return ; } const funcE = exp ( 'func' , sys ( 'start' ) ) ; for ( const { watName , expr } of ctx . globalInitializers ) { funcE . push ( ... codegenExpr ( expr , ctx ) ) ; funcE . push ( exp ( 'set_global' , wat ( watName ) ) ) ; } yield funcE ; yield exp ( 'start' , sys ( 'start' ) ) ; } function codegenGlobalDecl ( decl , ctx ) { const expr = decl . value . expr ; if ( expr instanceof a . FuncExpr ) { return codegenFunction ( decl . value . name . value , decl . value . expr , ctx ) ; } else if ( expr instanceof a . IdentExpr && expr . type instanceof a . FuncType ) { ctx . pushAlias ( decl . value . name . value , expr . value . value ) ; return null ; } else { return codegenGlobalVar ( decl , ctx ) ; } } function codegenFunction ( origName , func , ctx ) { const name = ctx . pushName ( origName ) ; const funcE = exp ( 'func' , wat ( name ) ) ; ctx . enterFunction ( ) ; for ( const param of func . value . params . items ) { funcE . push ( exp ( 'param' , wat ( ctx . pushName ( param . name . value ) ) , codegenType ( param . type , ctx ) ) ) ; } funcE . push ( exp ( 'result' , codegenType ( func . value . returnType , ctx ) ) ) ; funcE . push ( ... codegenBlock ( func . value . body , true , ctx ) ) ; ctx . leaveFunction ( ) ; return funcE ; } function codegenType ( ty , ctx ) { if ( ty instanceof a . IntType ) { return 'i32' ; } else if ( ty instanceof a . FloatType ) { return 'f64' ; } else if ( ty instanceof a . BoolType ) { return 'i32' ; } else if ( ty instanceof a . CharType ) { return 'i32' ; } else if ( ty instanceof a . VoidType ) { return '' ; } else { return 'i32' ; } } function getByteSizeOfType ( ty ) { if ( ty instanceof a . FloatType ) { return 8 ; } else if ( ty instanceof a . VoidType ) { return 0 ; } else { return 4 ; } } function * codegenBlock ( block , isFunction , ctx ) { if ( isFunction ) { yield * codegenLocalVarDef ( block , ctx ) ; ctx . resetScopeID ( ) ; } else { ctx . enterBlock ( ) ; } for ( const body of block . value . bodies ) { if ( body instanceof a . Expr ) { yield * codegenExpr ( body , ctx ) ; } else if ( body instanceof a . Decl ) { yield * codegenLocalVarDecl ( body , ctx ) ; } else if ( body instanceof a . Assign ) { yield * codegenAssign ( body , ctx ) ; } else { yield codegenBreak ( body , ctx ) ; } } if ( isFunction ) { yield exp ( 'return' ) ; } else { ctx . leaveBlock ( ) ; } } function codegenBlockType ( block , ctx ) { if ( block . value . returnVoid ) { return '' ; } else { const lastExpr = block . value . bodies [ block . value . bodies . length - 1 ] as any ; return codegenType ( lastExpr . type ! , ctx ) ; } } function * codegenExpr ( expr , ctx ) { if ( expr instanceof a . LitExpr ) { yield codegenLiteral ( expr . value , ctx ) ; } else if ( expr instanceof a . IdentExpr ) { yield codegenIdent ( expr . value , ctx ) ; } else if ( expr instanceof a . CallExpr ) { yield * codegenCallExpr ( expr , ctx ) ; } else if ( expr instanceof a . UnaryExpr ) { yield * codegenUnaryExpr ( expr , ctx ) ; } else if ( expr instanceof a . BinaryExpr ) { yield * codegenBinaryExpr ( expr , ctx ) ; } else if ( expr instanceof a . CondExpr ) { yield * codegenCondExpr ( expr , ctx ) ; } else if ( expr instanceof a . TupleExpr ) { yield * codegenTupleExpr ( expr , ctx ) ; } else if ( expr instanceof a . ArrayExpr ) { yield * codegenArrayExpr ( expr , ctx ) ; } else if ( expr instanceof a . IndexExpr ) { yield * codegenIndexExpr ( expr , ctx ) ; } else if ( expr instanceof a . NewExpr ) { yield * codegenNewExpr ( expr , ctx ) ; } else if ( expr instanceof a . LoopExpr ) { yield codegenLoopExpr ( expr , ctx ) ; } } function codegenLiteral ( lit , ctx ) { if ( lit instanceof a . IntLit ) { return exp ( 'i32.const' , String ( lit . value ) ) ; } else if ( lit instanceof a . FloatLit ) { const rep = lit . value . startsWith ( '.' ) ? '0' + lit . value : lit . value ; return exp ( 'f64.const' , rep ) ; } else if ( lit instanceof a . StrLit ) { return exp ( 'i32.const' , '0' ) ; } else if ( lit instanceof a . CharLit ) { return exp ( 'i32.const' , String ( lit . parsedValue . codePointAt ( 0 ) ) ) ; } else if ( lit instanceof a . BoolLit ) { return exp ( 'i32.const' , lit . parsedValue ? '1' : '0' ) ; } else { return exp ( 'unreachable' ) ; } } function codegenInitialValForType ( lit , ctx ) { if ( lit instanceof a . IntType ) { return exp ( 'i32.const' , '0' ) ; } else if ( lit instanceof a . FloatType ) { return exp ( 'f64.const' , '0' ) ; } else if ( lit instanceof a . CharType ) { return exp ( 'i32.const' , '0' ) ; } else if ( lit instanceof a . BoolType ) { return exp ( 'i32.const' , '0' ) ; } else { return exp ( 'i32.const' , '0' ) ; } } function codegenIdent ( ident , ctx ) { let name = ctx . getLocalWATName ( ident . value ) ; if ( name ) { return exp ( 'get_local' , wat ( name ) ) ; } else { name = ctx . getGlobalWATName ( ident . value ) ! ; return exp ( 'get_global' , wat ( name ) ) ; } } function * codegenCallExpr ( call , ctx ) { if ( ! ( call . value . func instanceof a . IdentExpr ) ) { return ; } if ( call . value . args instanceof a . TupleExpr ) { for ( const arg of call . value . args . value . items ) { yield * codegenExpr ( arg , ctx ) ; } } else { yield * codegenExpr ( call . value . args , ctx ) ; } const funcName = ctx . getGlobalWATName ( call . value . func . value . value ) ; if ( typeof funcName === 'string' ) { yield exp ( 'call' , wat ( funcName ) ) ; } else { const stdFunc = ctx . getStdFunc ( call . value . func . value . value ) ! ; if ( stdFunc . expr ) { yield * stdFunc . expr ; } } } function * codegenUnaryExpr ( unary , ctx ) { const op = unary . value . op ; const right = unary . value . right ; let ty = codegenType ( right . type ! , ctx ) ; if ( op . value === '-' ) { yield exp ( `${ ty }.const` , '0' ) ; } yield * codegenExpr ( right , ctx ) ; if ( op . value === '-' ) { yield exp ( `${ ty }.sub` ) ; } else if ( op . value === '!' ) { yield exp ( 'i32.eqz' ) ; } } function * codegenBinaryExpr ( binary , ctx ) { const op = binary . value . op ; const left = binary . value . left ; const right = binary . value . right ; const ty = codegenType ( right . type ! , ctx ) ; const signed = ty === 'i32' ? '_s' : '' ; switch ( op . value ) { case '==' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( `${ ty }.eq` ) ; break ; case '!=' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( `${ ty }.ne` ) ; break ; case '<' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( `${ ty }.lt${ signed }` ) ; break ; case '<=' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( `${ ty }.le${ signed }` ) ; break ; case '>' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( `${ ty }.gt${ signed }` ) ; break ; case '>=' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( `${ ty }.ge${ signed }` ) ; break ; case '+' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( `${ ty }.add` ) ; break ; case '-' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( `${ ty }.sub` ) ; break ; case '^' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( 'i32.xor' ) ; break ; case '&' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( 'i32.and' ) ; break ; case '|' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( 'i32.or' ) ; break ; case '*' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( `${ ty }.mul` ) ; break ; case '/' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( `${ ty }.div${ signed }` ) ; break ; case '%' : yield * codegenExpr ( left , ctx ) ; yield * codegenExpr ( right , ctx ) ; yield exp ( 'i32.rem_s' ) ; break ; case '&&' : yield * codegenExpr ( left , ctx ) ; yield exp ( 'if' , exp ( 'result' , 'i32' ) , exp ( 'then' , ... codegenExpr ( right , ctx ) ) , exp ( 'else' , exp ( 'i32.const' , '0' ) ) ) ; break ; case '||' : yield * codegenExpr ( left , ctx ) ; yield exp ( 'if' , exp ( 'result' , 'i32' ) , exp ( 'then' , exp ( 'i32.const' , '1' ) ) , exp ( 'else' , ... codegenExpr ( right , ctx ) ) ) ; break ; } } function * codegenCondExpr ( cond , ctx ) { yield * codegenExpr ( cond . value . if , ctx ) ; yield exp ( 'if' , exp ( 'result' , codegenBlockType ( cond . value . then , ctx ) ) , exp ( 'then' , ... codegenBlock ( cond . value . then , false , ctx ) ) , exp ( 'else' , ... codegenBlock ( cond . value . else , false , ctx ) ) ) ; } function * codegenGetCurrentHeapPointer ( ) { yield exp ( 'i32.const' , '0' ) ; yield exp ( 'i32.load' ) ; } function * codegenSetCurrentHeapPointer ( ) { yield exp ( 'i32.const' , '0' ) ; yield * codegenSwapStackTop ( 'i32' ) ; yield exp ( 'i32.store' ) ; } function * codegenSwapStackTop ( ty1 , ty2 = ty1 ) { yield exp ( 'set_global' , sys ( `reg/${ ty1 }/1` ) ) ; yield exp ( 'set_global' , sys ( `reg/${ ty2 }/2` ) ) ; yield exp ( 'get_global' , sys ( `reg/${ ty1 }/1` ) ) ; yield exp ( 'get_global' , sys ( `reg/${ ty2 }/2` ) ) ; } function * codegenMemoryAllocation ( size ? ) { if ( typeof size === 'number' ) { yield exp ( 'i32.const' , String ( size ) ) ; } yield * codegenGetCurrentHeapPointer ( ) ; yield exp ( 'set_global' , sys ( 'reg/addr' ) ) ; yield exp ( 'get_global' , sys ( 'reg/addr' ) ) ; yield exp ( 'i32.add' ) ; yield * codegenSetCurrentHeapPointer ( ) ; yield exp ( 'get_global' , sys ( 'reg/addr' ) ) ; } function * codegenTupleExpr ( tuple , ctx ) { if ( tuple . value . size === 0 ) { yield exp ( 'i32.const' , '0' ) ; return ; } for ( let i = 0 ; i < tuple . value . size ; i ++ ) { const expr = tuple . value . items [ i ] ; yield * codegenExpr ( expr , ctx ) ; } const tupleTy = tuple . type as any ; const types = tupleTy . value . items . map ( ty => codegenType ( ty , ctx ) ) ; const sizes = tupleTy . value . items . map ( getByteSizeOfType ) ; const constName = ctx . useTupleConstructor ( types , sizes ) ; yield exp ( 'call' , sys ( constName ) ) ; } function * codegenArrayExpr ( array , ctx ) { const arrTy = array . type ! as a . ArrayType ; const ty = codegenType ( arrTy . value , ctx ) ; const size = getByteSizeOfType ( arrTy . value ) ; const len = array . value . length ; yield * codegenMemoryAllocation ( 4 + size * len ) ; yield exp ( 'set_global' , sys ( 'reg/i32/1' ) ) ; for ( let i = 0 ; i < len + 2 ; i ++ ) { yield exp ( 'get_global' , sys ( 'reg/i32/1' ) ) ; } let offset = 4 ; yield exp ( 'i32.const' , String ( len ) ) ; yield exp ( 'i32.store' ) ; yield exp ( 'i32.const' , String ( offset ) ) ; yield exp ( 'i32.add' ) ; for ( let i = 0 ; i < len ; i ++ ) { yield * codegenExpr ( array . value [ i ] , ctx ) ; yield exp ( `${ ty }.store` ) ; if ( i < len - 1 ) { offset += size ; yield exp ( 'i32.const' , String ( offset ) ) ; yield exp ( 'i32.add' ) ; } } } function codegenTupleConstructor ( name , types , sizes ) { const funcE = exp ( 'func' , sys ( name ) ) ; for ( let i = 0 ; i < types . length ; i ++ ) { funcE . push ( exp ( 'param' , types [ i ] ) ) ; } funcE . push ( exp ( 'result' , 'i32' ) ) ; const offset = wat ( 'offset' ) ; funcE . push ( exp ( 'local' , wat ( 'offset' ) , 'i32' ) ) ; funcE . push ( ... codegenMemoryAllocation ( sizes . reduce ( ( x , y ) => x + y ) ) ) ; funcE . push ( exp ( 'set_local' , offset ) ) ; funcE . push ( exp ( 'get_local' , offset ) ) ; for ( let i = 0 ; i < types . length ; i ++ ) { funcE . push ( exp ( 'get_local' , offset ) ) ; funcE . push ( exp ( 'get_local' , String ( i ) ) ) ; funcE . push ( exp ( `${ types [ i ] }.store` ) ) ; funcE . push ( exp ( 'get_local' , offset ) ) ; funcE . push ( exp ( 'i32.const' , String ( sizes [ i ] ) ) ) ; funcE . push ( exp ( 'i32.add' ) ) ; funcE . push ( exp ( 'set_local' , offset ) ) ; } return funcE ; } function getTupleIdx ( expr ) { const idxLit = expr . value . index . value as any ; return idxLit . parsedValue ; } function * codegenTupleAddr ( target , idx , ctx ) { yield * codegenExpr ( target , ctx ) ; const tupleTy = target . type ! as a . TupleType ; let offset = 0 ; for ( let i = 0 ; i < idx ; i ++ ) { offset += getByteSizeOfType ( tupleTy . value . items [ i ] ) ; } yield exp ( 'i32.const' , String ( offset ) ) ; yield exp ( 'i32.add' ) ; } function * codegenArrayAddr ( target , index , byteSize , ctx ) { yield * codegenExpr ( target , ctx ) ; yield exp ( 'i32.const' , '4' ) ; yield exp ( 'i32.add' ) ; yield * codegenExpr ( index , ctx ) ; yield exp ( 'i32.const' , String ( byteSize ) ) ; yield exp ( 'i32.mul' ) ; yield exp ( 'i32.add' ) ; } function * codegenIndexExpr ( expr , ctx ) { const target = expr . value . target ; if ( target . type instanceof a . ArrayType ) { const byteSize = getByteSizeOfType ( target . type . value ) ; yield * codegenArrayAddr ( target , expr . value . index , byteSize , ctx ) ; const ty = codegenType ( target . type . value , ctx ) ; yield exp ( `${ ty }.load` ) ; } else if ( target . type instanceof a . TupleType ) { const idx = getTupleIdx ( expr ) ; yield * codegenTupleAddr ( target , idx , ctx ) ; const ty = codegenType ( target . type . value . items [ idx ] , ctx ) ; yield exp ( `${ ty }.load` ) ; } } function * codegenNewExpr ( expr , ctx ) { const size = getByteSizeOfType ( expr . value . type ) ; yield * codegenExpr ( expr . value . length , ctx ) ; yield exp ( 'set_global' , sys ( 'reg/i32/1' ) ) ; yield exp ( 'get_global' , sys ( 'reg/i32/1' ) ) ; yield exp ( 'get_global' , sys ( 'reg/i32/1' ) ) ; yield exp ( 'i32.const' , String ( size ) ) ; yield exp ( 'i32.mul' ) ; yield exp ( 'i32.const' , '4' ) ; yield exp ( 'i32.add' ) ; yield * codegenMemoryAllocation ( ) ; yield exp ( 'set_global' , sys ( 'reg/addr' ) ) ; yield exp ( 'get_global' , sys ( 'reg/addr' ) ) ; yield * codegenSwapStackTop ( 'i32' ) ; yield exp ( 'i32.store' ) ; yield exp ( 'get_global' , sys ( 'reg/addr' ) ) ; } function codegenLoopExpr ( expr , ctx ) { return exp ( 'block' , exp ( 'loop' , ... codegenExpr ( expr . value . while , ctx ) , exp ( 'if' , exp ( 'then' , ... codegenBlock ( expr . value . body , false , ctx ) , exp ( 'br' , '1' ) ) ) ) ) ; } function * codegenLocalVarDef ( block , ctx ) { for ( const body of block . value . bodies ) { if ( body instanceof a . Decl ) { const origName = body . value . name . value ; const expr = body . value . expr ; if ( expr instanceof a . IdentExpr && expr . type instanceof a . FuncType ) { continue ; } const name = ctx . convertLocalName ( origName ) ; yield exp ( 'local' , wat ( name ) , codegenType ( expr . type ! , ctx ) ) ; } else if ( body instanceof a . CondExpr ) { ctx . enterBlock ( ) ; yield * codegenLocalVarDef ( body . value . then , ctx ) ; ctx . leaveBlock ( ) ; ctx . enterBlock ( ) ; yield * codegenLocalVarDef ( body . value . else , ctx ) ; ctx . leaveBlock ( ) ; } else if ( body instanceof a . LoopExpr ) { ctx . enterBlock ( ) ; yield * codegenLocalVarDef ( body . value . body , ctx ) ; ctx . leaveBlock ( ) ; } } } function * codegenLocalVarDecl ( decl , ctx ) { const origName = decl . value . name . value ; const expr = decl . value . expr ; if ( expr instanceof a . IdentExpr && expr . type instanceof a . FuncType ) { ctx . pushAlias ( origName , ctx . getGlobalWATName ( expr . value . value ) ! ) ; } else { yield * codegenExpr ( expr , ctx ) ; const name = ctx . pushName ( origName ) ; yield exp ( 'set_local' , wat ( name ) ) ; } } function codegenGlobalVar ( decl , ctx ) { const name = ctx . getGlobalWATName ( decl . value . name . value ) ! ; const varE = exp ( 'global' , wat ( name ) ) ; const expr = decl . value . expr ; varE . push ( exp ( 'mut' , codegenType ( expr . type ! , ctx ) ) ) ; if ( expr instanceof a . LitExpr ) { varE . push ( ... codegenLiteral ( expr . value , ctx ) ) ; } else { varE . push ( codegenInitialValForType ( expr . type ! , ctx ) ) ; ctx . pushInitializer ( name , expr ) ; } return varE ; } function * codegenAssign ( assign , ctx ) { yield * codegenExpr ( assign . value . expr , ctx ) ; const lVal = assign . value . lVal ; if ( lVal instanceof a . IdentExpr ) { const ident = lVal . value ; let name = ctx . getLocalWATName ( ident . value ) ; if ( name ) { yield exp ( 'set_local' , wat ( name ) ) ; } else { name = ctx . getGlobalWATName ( ident . value ) ! ; yield exp ( 'set_global' , wat ( name ) ) ; } } else { const target = lVal . value . target ; if ( target . type instanceof a . ArrayType ) { const byteSize = getByteSizeOfType ( target . type . value ) ; yield * codegenArrayAddr ( target , lVal . value . index , byteSize , ctx ) ; const ty = codegenType ( target . type . value , ctx ) ; yield * codegenSwapStackTop ( 'i32' , ty ) ; yield exp ( `${ ty }.store` ) ; } else if ( target . type instanceof a . TupleType ) { const idx = getTupleIdx ( lVal ) ; yield * codegenTupleAddr ( target , idx , ctx ) ; const ty = codegenType ( target . type . value . items [ idx ] , ctx ) ; yield * codegenSwapStackTop ( 'i32' , ty ) ; yield exp ( `${ ty }.store` ) ; } } } function codegenBreak ( break_ , ctx ) { return exp ( 'br' , '1' ) ; }