sampsyo / bril

an educational compiler intermediate representation
https://capra.cs.cornell.edu/bril/
MIT License
557 stars 231 forks source link

brilirs fails on seemingly well-formed program #295

Closed SanjitBasker closed 1 year ago

SanjitBasker commented 1 year ago

As part of my dataflow analysis lesson task, I came up with some funky Bril programs to stress the worklist algorithm. The following program (which is easier to understand when the order of the basic blocks is reversed) fails with brilirs -p false false but passes brili -p false false and brilck. It also seems to obey the list of rules given in the Bril documentation.

@main(b0: bool, b1: bool) {
    jmp .start;
  .end:
    print x_0_2;
    print x_1_2;
    ret;
  .l_1_3:
    jmp .end;
  .l_1_2:
    x_1_2 : int = const 0;
    jmp .l_1_3;
  .l_1_1:
    x_1_1 : int = const 1;
    jmp .l_1_3;
  .l_0_3:
    br b1 .l_1_1 .l_1_2;
  .l_0_2:
    x_0_2 : int = const 2;
    jmp .l_0_3;
  .l_0_1:
    x_0_1 : int = const 3;
    jmp .l_0_3;
  .start:
    br b0 .l_0_1 .l_0_2;
}

For reference, here is the Python code I used to generate the program. brilirs has been super useful thus far, but I'm not super familiar with Rust so it'd be nice if a Rustacean could help us out here :)

Pat-Lafon commented 1 year ago

Thanks a bunch for report this! It turned out to be a simple fix in brilirs. Non-standard test cases like the one you provided are super helpful. Let me know if you have any more issues.

Try out the fix for yourself, let me know what else you run into(or any random questions). brilirs -t -f test/interp/core/non_linear_control_flow.bril false false

sampsyo commented 1 year ago

Awesome; many thanks to both of you! @Pat-Lafon beat me to it, but FWIW here is a reduced test case that elicits the same issue:

@main() {
  jmp .start;
.lab:
  ret;
.start:
  jmp .lab;
}

I can confirm that #296 fixes this! A round of applause for @Pat-Lafon. :clap: