Implement Loop statement - #1290

What is the use of branch?
@Shaikh-Ubaid

I see, the label_index is not constant, it changes based on the statements inside the loop.

What is the use of branch?

It is like a jump instruction. Everytime we wish to continue a loop in wasm, we need to branch (only if the loop condition is true) to the loop.

https://samrat.me/posts/2020-03-29-webassembly-control-instr-examples/ offers a good explanation.

I see, the label_index is not constant, it changes based on the statements inside the loop.

Yes, the label_index is used as the target of the branch.

As shared in the above comment, the label index counts from the inner most block (A block could be a loop or an if-else construct). In our case, a label_index of 0 points to the if-else condition (which is the loop condition) and a label_index of 1 points to the actual loop.

Also, on branching to a loop, the control passes to the beginning of the loop, where as on branching to an if block, the control passes to the end of it.

// Unlike with other index spaces, indexing of labels is relative by
// nesting depth, that is, label 0 refers to the innermost structured
// control instruction enclosing the referring branch instruction, while
// increasing indices refer to those farther out.

The following example should (hopefully) explain the above more clearly.

// Code in some dummy language, (might) not be exactly in `WebAssembly Text Format`

(loop // label index = 3
    (if // label index = 2
        (if // label index = 1
            (if // label index = 0
                br some_label_index
            )
        )
    )
) 

Depending on where we would like to branch, we can have appropriate value for some_label_index.

I got it, great explanation. Thanks

Great note, Thirumalai !. It explains the loop structure very beautifully. Thank you so much for it.

This if-else condition inside the visit_Br() is not clear to me. @Thirumalai-Shaktivel, please, could you possibly share how this if-else works and chooses whether to iterate the loop or end it?

Consider this example:

while i < 10:
    j = 0
    while j < 10:
        k += 1
        if i == 0:
            if j == 3:
                continue
            else:
                j += 1
        j += 1
    i += 1
assert k == 95

Output printed using:

diff --git a/src/libasr/codegen/wasm_to_x86.cpp b/src/libasr/codegen/wasm_to_x86.cpp
index 9db9d2b4b..48f947076 100644
--- a/src/libasr/codegen/wasm_to_x86.cpp
+++ b/src/libasr/codegen/wasm_to_x86.cpp
@@ -131,6 +131,9 @@ class X86Visitor : public WASMDecoder<X86Visitor>,
     void visit_EmtpyBlockType() {}
 
     void visit_Br(uint32_t label_index) {
+std::cout << "label_index: " << label_index << "\n";
+std::cout << "Loop_size: " << loop_unique_id.size() << "\n";
+std::cout << "If_size: " << if_unique_id.size() << "\n";
         // Branch is used to jump to the `loop.head` or `loop.end`.

$ lpython examples/expr2.py --backend wasm_x86 && ./expr2.out
label_index: 3
Loop_size: 2
If_size: 4
label_index: 1
Loop_size: 2
If_size: 2
label_index: 1
Loop_size: 1
If_size: 1

We have 2 loops and 2 if's. But in the backend, we get 2 loops and 4 ifs, right?
The first br comes from the continue, if we subtract 4 if's with 2 loops: we get the actual 2 if's. the label_index is 3, we do 3 - 1 = 2: jump to head and So on...

But if the break is encountered the label_index is 2, So we jump to the end of the loop
Any doubts, please ask

how this if-else works and chooses whether to iterate the loop or end it?

Every time, the loop is iterated using the Br. Also, I didn't analyze how the loop is being exited. I will look into it soon.

I see, the Loop is exited through the else block:

.loop.head_297:
    mov eax, [ebp-4]
    push eax
    push 0x0000000a
    pop ebx
    pop eax
    cmp eax, ebx
    jl .compare_1303
    push 0x00
    jmp .compare.end_303
.compare_1303:
    push 0x01
.compare.end_303:
    pop eax
    cmp eax, 0x01
    je .then_304
    jmp .else_304
.then_304:
    mov eax, [ebp-4]
    push eax
    push 0x00000001
    pop ebx
    pop eax
    add eax, ebx
    push eax
    pop eax
    mov [ebp-4], eax
    jmp .loop.head_297
    jmp .endif_304
.else_304:
.endif_304:
.loop.end_297:
    mov esp, ebp
    pop ebp
    ret

I have a doubt, here the jump and label .endif_304 is useless? is it ok? @Shaikh-Ubaid

@Shaikh-Ubaid, were you able to understand or get the point?

I have a doubt, here the jump and label .endif_304 is useless? is it ok? @Shaikh-Ubaid

I think for the moment that should be fine.

@Shaikh-Ubaid, were you able to understand or get the point?

Yup, thank you so much for the explanation, Thirumalai.

It seems this condition (if_unique_id.size() - loop_unique_id.size() == label_index - 1) might not be perfect to determine to continue or end the loop. Consider the following example where we have a loop inside an if construct:

def main0():
    x: i32
    x = (2+3)*5
    j: i32 = 0
    if True:
        while x > 0:
            j += 2
            x -= 1
    print(x)
    print(j)

main0()

Output:

(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ lpython examples/expr2.py
0
50
(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ lpython examples/expr2.py --backend wasm_x86 -o loop
(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ ./loop 
24
2
(lp) ubaid@ubaid-Lenovo-ideapad-330-15ARR:~/OpenSource/lpython$ 

The loop in this case just executes once and then exits. This is because in this case (when visit_Br() is visited) the if count would be 2 and loop count would be 1. The label_index would be 1. The condition would be 2 - 1 == 1 - 1, that is 1 == 0, which is not true and hence the loop exits.

I think we might need to simulate how wasm works in x86. We might need to use same label indexes (or same label index space) for if's and loop's (just like wasm does).

It seems this condition (if_unique_id.size() - loop_unique_id.size() == label_index - 1) might not be perfect to determine to continue or end the loop.

+1; I agree with this.
Also, I didn't test the loop within the if statement.
There you go, you've found the actual bug in the loop statement.
Thank you for testing this. I will make this a new issue. Let's work on this and fix it.