This series is mainly my notes on WASM research, which may be brief. The total includes:

  1. WebAssembly(1) Compilation
  2. The WebAssembly(2) Basic Api
  3. WebAssembly(3) Instructions
  4. WebAssembly(4) Validation
  5. WebAssembly(5) Memory
  6. WebAssembly(6) Binary Format
  7. WebAssembly(7) Future
  8. WebAssembly(8) Wasm in Rust (TODO)

How does JS parse?

Lexical analysis

JS code first needs to pass through a Lexer to generate tokens, such as a = 1 + 2 will be parsed into {a, =, 1, +, 2} five tokens

Syntax analysis

Then the AST is generated by Parser. For example, for E -> DPD, we can derive S -> veE into S -> vedpd

V8 Engine architecture

  1. Parser: Lexical analysis -> syntactic analysis -> semantic analysis (check whether function arguments are called correctly, etc.)
  2. Ignition Interpreter: Generates Bytecode based on AST
  3. TurboFan optimizer: Optimize code, Deoptimize if optimized code is not available

Strong and weak type

  1. Weak typing: Types are inferred at run time (such as JS), usually through JIT technology to improve runtime efficiency.
  2. Strong typing: Without inference, AOT optimization can be performed and compiled to binary machine code ahead of time.

JIT optimization in JS engine

JIT(Just-in-time) refers to the caching of some hot Path-generated binaries during dynamic compilation of code to improve efficiency. Dynamically typed languages are too liberal, so some of the writing cannot be JIT optimized. A good comparison of JIT optimization is the following example, where ARR1 is JIT optimized and ARR2 is frequently de-optimized: JIT-codesandbox

Can JS AOT?

Yes, through asm.js. Such as:

var asm = (function(stdlib, foreign, heap) {
  'use asm';
  function __z3addii($0, $1) {$0 = $0|0; // $0 is an integer
    $1 = $1|0; // $1 is an integer
    var $2 = 0, label = 0, sp = 0;
    $2 = (($1) + ($0)) |0;
    return ($2|0); // The return value is declared as an integer
  }
  return {
    add: __z3addii
  }
})(window.null.new ArrayBuffer(0x10000));
Copy the code

Note that:

  1. Annotation: x|0[32 integer],+x[double precision floating point],(x)Single-precision floating-point can only mark numerical values
  2. Stdlib: a reference object containing the js built-in standard library, generally can be passedwindow
  3. Foreign: reference to an external custom JS method.
  4. Heap: Where all external ASM data is stored before it can be read by the ASM module

Asm.js is fully compatible with JS and can be gracefully degraded. But the lack of 64-bit integers, which can only be annotated with numeric types, is too difficult to write. So there was no mass adoption.

WASM compilation base: LLVM

LLVM (Low Level Virtual Machine) general-purpose compiler infrastructure, which can be used to develop the front and back ends of compilers. Currently supports ActionScript, Ada, D, Fortran, GLSL, Haskell, Java bytecode, Objective-C, Swift, Python, Ruby, Rust, Scala, C# and other languages

  1. Front end: Convert programming language to intermediate form IR (C/C++,Haskell, Rust, Swift, etc.)
  2. Back end: Instruction set support (ARM, Qualcomm Hexagon, MIPS, etc.)

IR (intermediate Representation)

At the heart of LLVM is Intermediate Representation (IR), an assembly-like low-level language. IR is a strongly typed Reduced Instruction Set Computing (RISC) that abstracts the target Instruction Set. For example, the function call convention of the target instruction set is abstracted into call and RET instructions with explicit arguments. In addition, IR uses an infinite number of registers, such as %0, %1 and other forms of expression. LLVM supports three expressions:

  1. Human-readable compilation (*.ll)
  2. Object form in C++
  3. Serialized bitcode form (*.bc)

  1. The Frontend is responsible for compiling various types of source code into intermediate representation, also known as bitcode. In THE LLVM system, different languages have different compiler Frontend, such as CLang is responsible for C/C ++/ OC compilation, Flang is responsible for FORTRAN compilation. Swiftc is responsible for swift compilation and so on
  2. Optimizer (DeadStrip/SimplifyCFG) is responsible for various types of optimizations of bitcode. It performs logically equivalent transformations of bitcode to make it more efficient and smaller
  3. Backend, also called CodeGenerator, compiles optimized bitcode into the machine code of the specified target architecture. For example, X86Backend compiles bitcode into the machine code of the x86 instruction set
  4. Linker: Link resources (dynamic, static)

Bitcode

00000000 de c0 17 0b 00 00 00 00 14 00 00 00 08 0b 00 00 |................ | 00000010 07 00 00 01 42 43 c0 de 35 14 00 00 07 00 00 00 |.... BC.. 5... | 00000020 62 0c 30 24 96 96 a6 a5 f7 d7 7f 4d d3 b4 5f d7 |b.0$....... M.. _.| 00000030 3e 9e fb f9 4f 0b 51 80 4c 01 00 00 21 0c 00 00 |>... O.Q.L... ! . | 00000040 74 02 00 00 0b 02 21 00 02 00 00 00 13 00 00 00 |t..... ! . | 00000050 07 81 23 91 41 c8 04 49 06 10 32 39 92 01 84 0c |..#.A.. I.. 29... |00000060 25 05 08 19 1e 04 8b 62 80 10 45 02 42 92 0b 42 |%...... b.. E.B.. B| 00000070 84 10 32 14 38 08 18 4b 0a 32 42 88 48 90 14 20 |.. 2.8.. K.2B.H.. | 00000080 43 46 88 a5 00 19 32 42 04 49 0e 90 11 22 c4 50 |CF.... 2B.I...".P|
00000090  41 51 81 8c e1 83 e5 8a  04 21 46 06 51 18 00 00  |AQ.......!F.Q...|
Copy the code

Assembly Language

; ModuleID = 'test.c' source_filename = "test.c" target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-apple-macosx10.14.0" @. STR = private unnamed_addr constant [15 x i8] c"hello, world. Function Attrs: noinline nounwind optnone ssp uwtable define i32 @main() #0 { %1 = alloca i32, align 4 store i32 0, i32* %1, align 4 %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i32 0, i32 0)) ret i32 0 } declare i32 @printf(i8*, ...). #1 attributes #0 = { noinline nounwind optnone ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "Target - the features" = "+ cx16, + FXSR, + MMX, + sahf, + sse, + sse2, + sse3, + sse4.1, + ssse3, + x87" "unsafe - the fp - math" = "false" "use-soft-float"="false" } attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "Target - the features" = "+ cx16, + FXSR, + MMX, + sahf, + sse, + sse2, + sse3, + sse4.1, + ssse3, + x87" "unsafe - the fp - math" = "false" "use-soft-float"="false" } ! llvm.module.flags = ! {! 0,! 1}! llvm.ident = ! {! 2}! 0 =! {i32 1, !" wchar_size", i32 4} ! 1 =! {i32 7, !" PIC Level", i32 2} ! 2 =! {!" Apple LLVM Version 10.0.0 (clang-1000.11.45.5)"}Copy the code

Modules, functions, basicblocks, and instructions contain functions, which in turn contain code blocks, which in turn are composed of instructions. With the exception of modules, all structures are generated from values.

WASM compilation foundation: Emscripten

The ASM standard is strict and writing is difficult. You can use Emscripten to translate C/C++ code into ASMJS. Empscripten is based on the LLVM tool chain and consists of two parts:

  1. Frontend (emcc,Emscripten Compiler Frontend) : compile C/C++ into LLVM IR, why clang? Emcc will provide some unique features such as macro definition
  2. The back end (Fastcomp) compiles LLVM intermediate code to the target language (JS)

How does WASM compile?

C/C++ to WASM

  1. Ancient method: Use s2wASM (deprecated) to convert an Assembly into a webAssembly.C/C++ - {Clang} -> LLVM IR - {llc} -> *.s - {s2wasm} -> wasm
  2. Traditional method: compile to ASM.js and convert to webAssembly via ASm2wASM.C/C++ - {emcc/Fastcomp} -> ASM.js - {asm2wasm} -> wasm
  3. Modern method (2019.3+): Compile directly to webAssembly through LLVM 8.C/C++ - {Clang} -> LLVM IR - {llc && wasmld} -> wasm

Compile details for LLVM 8

LLVM 8 provides full WASM back-end support to convert LLVM IR directly to WASM. (target — wASM), all languages that can compile to LLVM IR can be easily converted to WASM

Target = wasm?

LLVM wASM documentation: Instructions – 1.0 WebAssembly WebAssembly LLD port – 10 documentationWebAssembly LLD and Dynamic Memory | Frank Rehberger

libc or libc++?

How to use malloc in C/C++? new? algorithm?

  1. Emcc (dlmalloc): emscripten/library_syscall.js at incoming · emscripten-core/emscripten · GitHub
  2. wasmception(musl-libc): GitHub – yurydelendik/wasmception: Minimal C/C++ language toolset for building wasm files demo: WebAssembly Studio
  3. wasi(dlmalloc): GitHub – CraneStation/wasi-libc: WASI libc implementation for WebAssembly

Compilation tools for other languages:

Binaryen

Webassembly’s official set of toolchains, provides a set of Binaryen IR with the back end, currently more famous front-end are:

  1. AssemblyScript: Typescript
  2. Asterius: Haskell
  3. asm2wasm: asm.js

rustc

Rust’s official compiler already supports target=wasm32-unknown-unknown. Rustc currently has a very good WASM memory allocation library wee_alloc, which can directly generate related WASM memory instructions without using glue code: