Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
3 changes: 3 additions & 0 deletions integration_tests/CMakeLists.txt
Original file line number Diff line number Diff line change
Expand Up @@ -210,6 +210,9 @@ RUN(NAME expr_13 LABELS llvm c
EXTRAFILES expr_13b.c)
RUN(NAME expr_14 LABELS cpython llvm c)
RUN(NAME loop_01 LABELS cpython llvm c)
RUN(NAME loop_02 LABELS cpython llvm wasm wasm_x86)
RUN(NAME if_01 LABELS cpython llvm wasm wasm_x86)
RUN(NAME if_02 LABELS cpython llvm wasm wasm_x86)
RUN(NAME print_02 LABELS cpython llvm)
RUN(NAME test_types_01 LABELS cpython llvm c)
RUN(NAME test_str_01 LABELS cpython llvm c)
Expand Down
29 changes: 15 additions & 14 deletions integration_tests/if_01.py
Original file line number Diff line number Diff line change
@@ -1,45 +1,46 @@
def Test_if_01():
z: i32 = 0
if True:
print(1)
assert True

if False:
print(0)
assert False

if 1 < 0:
print(0)
assert False
else:
print(1)
assert True

if 1 > 0:
print(1)
assert True
else:
print(0)
assert False

if 1 < 0:
print(1)
assert False
elif 1 > 0:
print(1)
assert True
else:
print(0)
assert False

def Test_if_02():
if True:
print(1)
if True:
print(2)
if False:
print(3)
assert False
elif True:
print(4)
else:
print(5)
assert False
else:
print(6)
assert False

if True:
print(7)
if False:
print(8)
assert False
if False:
print(9)
else:
Expand All @@ -48,7 +49,7 @@ def Test_if_02():
if True:
print(11)
else:
print(12)
assert False
print(13)
print(14)

Expand Down
5 changes: 2 additions & 3 deletions integration_tests/if_02.py
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
from ltypes import bool, i32
from ltypes import i32

def test_if_01():
x: bool = True
Expand Down Expand Up @@ -33,8 +33,7 @@ def test_if_01():
if y >= 2:
z += 1

# TODO: replace this an assert statement
print(z)
assert z == 9

def verify():
test_if_01()
Expand Down
84 changes: 84 additions & 0 deletions integration_tests/loop_02.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,84 @@
from ltypes import i32
def test_loop_01():
i: i32 = 0
j: i32 = 0

while False:
assert False

while i < 0:
assert False

while i < 10:
i += 1
assert i == 10

while i < 20:
while i < 15:
i += 1
i += 1
assert i == 20

for i in range(5):
assert i == j
j += 1

def test_loop_02():
i: i32 = 0
j: i32 = 0

j = 0
for i in range(10, 0, -1):
j = j + i
assert j == 55

for i in range(5):
if i == 3:
break
assert i == 3

j = 0
for i in range(5):
if i == 3:
continue
j += 1
assert j == 4

def test_loop_03():
i: i32 = 0
j: i32 = 0
k: i32 = 0
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

i = 0; j = 0; k = 0
while i < 10:
j = 0
while j < 10:
k += i + j
if i == 5:
if j == 4:
break
else:
j += 1
j += 1
i += 1
assert k == 826


def verify():
test_loop_01()
test_loop_02()
test_loop_03()

verify()
1 change: 1 addition & 0 deletions src/libasr/codegen/asr_to_wasm.cpp
Original file line number Diff line number Diff line change
Expand Up @@ -2032,6 +2032,7 @@ class ASRToWASMVisitor : public ASR::BaseVisitor<ASRToWASMVisitor> {
m_code_section, m_al,
nesting_level -
cur_loop_nesting_level); // emit_branch and label the loop
wasm::emit_b8(m_code_section, m_al, 0x05); // starting of else
wasm::emit_expr_end(m_code_section, m_al); // end if

nesting_level--;
Expand Down
58 changes: 49 additions & 9 deletions src/libasr/codegen/wasm_to_x86.cpp
Original file line number Diff line number Diff line change
Expand Up @@ -32,7 +32,8 @@ class X86Visitor : public WASMDecoder<X86Visitor>,
public:
X86Assembler &m_a;
uint32_t cur_func_idx;
std::vector<std::string> unique_id;
std::vector<std::string> if_unique_id;
std::vector<std::string> loop_unique_id;
int32_t last_vis_i32_const, last_last_vis_i32_const;
std::unordered_map<int32_t, std::string> loc_to_str;

Expand Down Expand Up @@ -129,23 +130,59 @@ class X86Visitor : public WASMDecoder<X86Visitor>,

void visit_EmtpyBlockType() {}

void visit_Br(uint32_t label_index) {
// Branch is used to jump to the `loop.head` or `loop.end`.
if (if_unique_id.size() - loop_unique_id.size() == label_index - 1) {
// cycle/continue or loop.end
m_a.asm_jmp_label(".loop.head_" + loop_unique_id.back());
} else {
// exit/break
m_a.asm_jmp_label(".loop.end_" + loop_unique_id.back());
}
Comment on lines +135 to +141

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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?

@Thirumalai-Shaktivel Thirumalai-Shaktivel Nov 14, 2022

Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

@Thirumalai-Shaktivel Thirumalai-Shaktivel Nov 14, 2022

Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

@Thirumalai-Shaktivel Thirumalai-Shaktivel Nov 14, 2022

Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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).

@Thirumalai-Shaktivel Thirumalai-Shaktivel Nov 14, 2022

Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

}

void visit_Loop() {
loop_unique_id.push_back(std::to_string(offset));
/*
The loop statement starts with `loop.head`. The `loop.body` and
`loop.branch` are enclosed within the `if.block`. If the condition
fails, the loop is exited through `else.block`.
.head
.If
# Statements
.Br
.Else
.endIf
.end
*/
Comment on lines +146 to +157

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

m_a.add_label(".loop.head_" + loop_unique_id.back());
{
decode_instructions();
}
// end
m_a.add_label(".loop.end_" + loop_unique_id.back());
loop_unique_id.pop_back();
}

void visit_If() {
unique_id.push_back(std::to_string(offset));
if_unique_id.push_back(std::to_string(offset));
// `eax` contains the logical value (true = 1, false = 0)
// of the if condition
m_a.asm_pop_r32(X86Reg::eax);
m_a.asm_cmp_r32_imm8(LFortran::X86Reg::eax, 1);
m_a.asm_je_label(".then_" + unique_id.back());
m_a.asm_jmp_label(".else_" + unique_id.back());
m_a.add_label(".then_" + unique_id.back());
m_a.asm_je_label(".then_" + if_unique_id.back());
m_a.asm_jmp_label(".else_" + if_unique_id.back());
m_a.add_label(".then_" + if_unique_id.back());
{
decode_instructions();
}
m_a.add_label(".endif_" + unique_id.back());
unique_id.pop_back();
m_a.add_label(".endif_" + if_unique_id.back());
if_unique_id.pop_back();
}

void visit_Else() {
m_a.asm_jmp_label(".endif_" + unique_id.back());
m_a.add_label(".else_" + unique_id.back());
m_a.asm_jmp_label(".endif_" + if_unique_id.back());
m_a.add_label(".else_" + if_unique_id.back());
}

void visit_LocalGet(uint32_t localidx) {
Expand Down Expand Up @@ -225,6 +262,7 @@ class X86Visitor : public WASMDecoder<X86Visitor>,
std::string label = std::to_string(offset);
m_a.asm_pop_r32(X86Reg::ebx);
m_a.asm_pop_r32(X86Reg::eax);
// `eax` and `ebx` contain the left and right operands, respectively
m_a.asm_cmp_r32_r32(X86Reg::eax, X86Reg::ebx);
if (compare_op == "Eq") {
m_a.asm_je_label(".compare_1" + label);
Expand All @@ -241,6 +279,8 @@ class X86Visitor : public WASMDecoder<X86Visitor>,
} else {
throw CodeGenError("Comparison operator not implemented");
}
// if the `compare` condition in `true`, jump to compare_1
// and assign `1` else assign `0`
m_a.asm_push_imm8(0);
m_a.asm_jmp_label(".compare.end_" + label);
m_a.add_label(".compare_1" + label);
Expand Down
2 changes: 1 addition & 1 deletion tests/reference/wat-loop1-e0046d4.json
Original file line number Diff line number Diff line change
Expand Up @@ -6,7 +6,7 @@
"outfile": null,
"outfile_hash": null,
"stdout": "wat-loop1-e0046d4.stdout",
"stdout_hash": "72c18793b437f96f1f96c9f8fc8cc253601fb360929216a4de1cb2f1",
"stdout_hash": "f2518c3df21a94fba3afb27274ecfae56de7beaaaa8b54b4c1fd84fa",
"stderr": null,
"stderr_hash": null,
"returncode": 0
Expand Down
3 changes: 3 additions & 0 deletions tests/reference/wat-loop1-e0046d4.stdout
Original file line number Diff line number Diff line change
Expand Up @@ -48,6 +48,7 @@
i32.sub
local.set 0
br 1
else
end
end
local.get 2
Expand Down Expand Up @@ -83,6 +84,7 @@
i32.mul
local.set 3
br 1
else
end
end
local.get 3
Expand Down Expand Up @@ -121,6 +123,7 @@
i32.sub
local.set 0
br 1
else
end
end
local.get 2
Expand Down