Compiling factor.bf returns incorrect results with full optimisations

[Wilfred]

$ ./bfc14 --opt 0 sample_programs/factor.bf
$ echo 1333337 | ./factor
1333337: 617 2161
$ ./bfc14 --opt 1 sample_programs/factor.bf
$ echo 1333337 | ./factor
1333337: 1333337

# minimal bad passes
cargo run -- --passes=multiply,zeroing_loop --opt=1 --llvm-opt=2 sample_programs/factor.bf

[Wilfred]

Running with LLVM optimisations 0 or 1 works:

/bfc14 sample_programs/factor.bf --llvm-opt 1
$ echo 1333337 | ./factor 
1333337: 617 2161

As does this, oddly:

$ ./bfc14 sample_programs/factor.bf --opt 0 --llvm-opt 3
$ echo 1333337 | ./factor
1333337: 617 2161

[Wilfred]

The optimised build can factor up to 8, but nothing beyond that.

[Wilfred]

(require 'ob-sh)

#+BEGIN_SRC bash :results verbatim
  cargo run -- --passes=combine_inc sample_programs/factor.bf
  echo 1337 | ./factor
#+END_SRC

#+RESULTS:
:      Running `target/debug/bfc --passes=combine_inc sample_programs/factor.bf`
: 1337: 7 191

#+BEGIN_SRC bash :results verbatim
  cargo run -- --passes=combine_inc,combine_ptr,known_zero,multiply,zeroing_loop,combine_set --opt=1 --llvm-opt=2 sample_programs/factor.bf
  echo 1337 | ./factor
#+END_SRC

#+RESULTS:
:      Running `target/debug/bfc --passes=combine_inc,combine_ptr,known_zero,multiply,zeroing_loop,combine_set --opt=1 --llvm-opt=2 sample_programs/factor.bf`
: 1337: 1337

At this point it's becoming very slow. We skip speculative execution
and lower LLVM optimisation to O3. This still reproduces the issue,
but marginally reduces the work necessary.

Question: are we hitting an infinite loop in the bfc optimisation?
We are! We should bail out in this situation, with a warning.

#+BEGIN_SRC bash :results verbatim
  cargo run -- --passes=combine_inc,combine_ptr,known_zero,multiply --opt=1 --llvm-opt=2 sample_programs/factor.bf
  echo 1337 | ./factor
#+END_SRC

[Wilfred]

Minimal failing example:

#+BEGIN_SRC bash :results verbatim
  cargo run -- --passes=zeroing_loop,multiply --opt=1 --llvm-opt=2 sample_programs/factor.bf
  echo 1337 | ./factor
#+END_SRC

#+RESULTS:
:      Running `target/debug/bfc --passes=zeroing_loop,multiply --opt=1 --llvm-opt=2 sample_programs/factor.bf`
: 1337: 1337

[Wilfred]

Interestingly, it's the zeroing_loop pass that seems to be necessary. Everything works without it:

#+BEGIN_SRC bash :results verbatim
  cargo run -- --passes=combine_inc,combine_ptr,known_zero,multiply,combine_set,dead_loop,redundant_set,read_clobber,pure_removal,offset_sort sample_programs/factor.bf
  echo 1337 | ./factor
#+END_SRC

#+RESULTS:
:      Running `target/debug/bfc --passes=combine_inc,combine_ptr,known_zero,multiply,combine_set,dead_loop,redundant_set,read_clobber,pure_removal,offset_sort sample_programs/factor.bf`
: 1337: 7 191

[Wilfred]

bugpoint should be able to help us here. Something like:

bugpoint -llc-safe -input input.txt with_zeroing.ll

[Wilfred]

Minimal example thanks to bugpoint

opt -S -basicaa -instcombine -licm -instcombine -gvn with_zeroing.ll -o with_zeroing_all.ll

which sadly segfaults when trying to debug, but the command run was:

$ cat input.txt 
1337
$ bugpoint with_zeroing.ll -input input.txt -safe-run-llc -basicaa -instcombine -licm -instcombine -gvn

(file is available at https://gist.github.com/Wilfred/dde83b701d9bb8d7207a )

[Wilfred]

I can't reproduce this on LLVM trunk.

[Wilfred]

Fixed in LLVM 3.8.0rc1 too.

[Wilfred]

This is an LLVM bug. For future reference, you can reproduce it with:

$ opt -O2 -S with_zeroing.ll -o with_zeroing_o2.ll
$ echo 1337 | lli with_zeroing_o2.ll
1337: 1337

with_zeroing.ll is available in this gist.

[Wilfred]

I'm struggling to reproduce this on a Debug build of LLVM. I'm going to confirm that a Release build of LLVM 3.8.0 does not exhibit this bug.

[Wilfred]

Happily, LLVM 3.8.0 fixes this even on Release builds. I haven't managed to replicate the bug with a Debug build of LLVM commits between 3.7 and 3.8, so I was either unlucky or it doesn't occur on Debug builds.

[Wilfred]

I've inadvertently built bfc v1.5 against a debug build of LLVM. Doesn't seem to be a major problem.