WASM to X86 Backend

[ubaidsk]

There is an idea to implement a wasm to x86 backend. We have to benchmark ASR->x86 and ASR->WASM->x86. If the performance difference is not much, then the big advantage of WASM->x86 would (hopefully) be that it would be a easier and quicker for us to deliver a working backend.

• We can start with 32bit, since it is already figured out, unless it is more complicated,then we can just do 64 bit.

*Notes:

• This was first discussed at Add wasm to wat backend certik/test_wasm#4 (comment) (last line) and Add wasm to wat backend certik/test_wasm#4 (comment) (last paragraph).

[ubaidsk]

For x86 do we need the binary format or text based format or both?

[certik]

I think you can use the X86 assembler, which just generates a binary, but in Debug mode it can also do a text format.

Alternatively, we just do a binary, and then do x86 -> text assembly.

[ubaidsk]

lpython/src/libasr/codegen/asr_to_wasm.cpp

Lines 1935 to 1949 in fc08c06

	} else if (t->type == ASR::ttypeType::Character) {
	// the string location is already on function stack
	// now, push the string length onto stack
	wasm::emit_i32_const(
	m_code_section, m_al,
	ASR::down_cast<ASR::Character_t>(t)->m_len);
	// call JavaScript print_str
	wasm::emit_call(
	m_code_section, m_al,
	m_func_name_idx_map[get_hash(
	m_import_func_asr_map["print_str"])]
	->index);
	}

In wasm, when printing strings, we have the length of the string and its location in memory onto the stack. In x86 as well, when there is a call to print string, we would be having the length of the string and its memory location onto the x86 stack. The concern here is that the memory location of the string is not available with the wasm->x86 backend (during compile-time), but instead is available with x86 (during runtime, since the location is already onto the stack). Thus, if we (somehow) create a label for each string, we are unable to reference the label for a particular string (the label and the string's memory might not be same or we might not be able to create a relation between them). It seems we might need to dynamically allocate strings in x86.

[ubaidsk]

In wasm, when printing strings, we have the length of the string and its location in memory onto the stack.

This idea of printing strings using its length and memory location is more of our own concept/choice. It is possible that WASI might have different mechanism of printing string. At the moment, we do not have support for WASI.

[ubaidsk]

Prospective Roadmap:

• support printing strings (WASM_X86: Initial support for print_str #1265)
• support if else (thus support assert) (Implement if-else in wasm_to_x86 backend #1264)
• support stop and error stop (we need error stop for CI tests)
• support wasm_x86 at the CI (CI: Support integration_tests for X86 and WASM_X86 backends #1262)
• support printing negative integers (WASM_X86: Support printing negative integers #1311)
• support loops (hopefully including continue and break) (Implement Loop statement #1290)
• support floating point numbers (and operations on them)

[Thirumalai-Shaktivel]

@Shaikh-Ubaid sorry, I was a little busy with this PR: #1256.
So, were you able to figure out a way for the comment?
I'm interested in working on this issue alongside with you! What are you working now?

[certik]

Here is how to benchmark:

N = 10000

A_functions = ""
calls = ""
for i in range(N):
    func_A = f"""
def A{i}(x: i32) -> i32:
    y: i32
    z: i32
    y = {i}
    z = 5
    x = x + y * z
    return x
"""
    A_functions += func_A
    calls += f"    y = A{i}(y)\n"

source = f"""\
from ltypes import i32

{A_functions}

def Driver(radius: i32) -> i32:
    y: i32
    y = radius
{calls}
    return y

def Main0():
    print(Driver(5))

Main0()
"""

print(source)

[ubaidsk]

So, were you able to figure out a way for the #1222 (comment)?

There is a hackish idea to support printing strings in the wasm_x86 backend. I am not sure if it would work but I am positive.

I'm interested in working on this issue alongside with you! What are you working now?

Sure, we can work together. I am hoping to follow the roadmap shared here #1222 (comment). You can proceed with supporting if else in the wasm_x86. Please feel free to get in touch for any clarification/query related to wasm or wasm_x86 backends.

[certik]

Here are the timing results. With N = 10000, the above script produces a file with 90,015 lines. Here are the results (best timing each):

$ time lpython --backend=llvm a.py -o a_llvm.x
lpython --backend=llvm a.py -o a_llvm.x  2.94s user 0.10s system 99% cpu 3.034 total
$ time lpython --backend=x86 a.py -o a_x86.x
lpython --backend=x86 a.py -o a_x86.x  0.09s user 0.01s system 93% cpu 0.104 total
$ time lpython --backend=wasm_x86 a.py -o a_wasm_x86.x
lpython --backend=wasm_x86 a.py -o a_wasm_x86.x  0.11s user 0.01s system 95% cpu 0.129 total

The programs runs on x86 Linux:

$ ./a_wasm_x86.x 
249975005$ ./a_x86.x 
249975005
$ 

Summary for this particular example:

Backend	Time	Speedup over LLVM	Lines / s
LLVM	3.034	1x	29,668
WASM x86	0.129	23.5x	697,790
x86	0.104	29.2x	865,528

The WASM x86 backend is roughly 25% slower than the direct x86 backend, which is not bad, given that both are over 20x faster than LLVM. The timings include parsing and semantics too, so the relative speeds of the backends themselves are larger, but the above is a good start to get an idea of the performance.

[certik]

@Shaikh-Ubaid can you please submit a PR with the script in #1222 (comment) and put it into src/bin? That way we can use it for benchmarking.

[ubaidsk]

@Shaikh-Ubaid can you please submit a PR with the script in #1222 (comment) and put it into src/bin? That way we can use it for benchmarking.

Submitted here #1260

[ubaidsk]

Debug Mode Benchmark results for N = 10000 on AMD Ryzen 5 2500U with Radeon Vega Mobile Gfx @1.6GHz

(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ time python bench.py 
249975005

real    0m0.461s
user    0m0.396s
sys     0m0.064s
(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ time lpython bench.py --backend llvm
249975005

real    1m55.329s
user    1m55.093s
sys     0m0.154s
(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ time lpython bench.py --backend x86

real    0m24.622s
user    0m24.588s
sys     0m0.028s
(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ time lpython bench.py --backend wasm_x86

real    0m48.122s
user    0m47.993s
sys     0m0.081s

---

Release Mode Benchmark results for N = 10000 on AMD Ryzen 5 2500U with Radeon Vega Mobile Gfx @1.6GHz

(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ time python bench.py 
249975005

real    0m0.511s
user    0m0.412s
sys     0m0.095s
(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ time lpython bench.py --backend llvm
249975005

real    0m6.126s
user    0m6.021s
sys     0m0.084s
(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ time lpython bench.py --backend x86

real    0m0.282s
user    0m0.241s
sys     0m0.040s
(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ time lpython bench.py --backend wasm_x86

real    0m0.369s
user    0m0.308s
sys     0m0.061s

---

Note: The above results (of both Debug mode and Release mode) are for single time execution.

[Thirumalai-Shaktivel]

This might help with printing negative numbers, I looking for some other resources.