Repository: rust
Issue: Dead code elimination leads to performance regression
Labels: I-slow,T-compiler

I'm writing a [tiny virtual machine](https://github.com/overclockworked64/reaper/tree/rustc-issue) and am using a recursive `fib(40)` as the benchmark along the way.

I ran `cargo clippy` and noticed a 33% performance regression after implementing the fixes. The running time went from 15sec to 20sec. Then I rolled back the changes, and started applying the fixes individually and measuring the performance using `hyperfine --runs 5` along the way. I know it sounds silly, but it turned out that a simple dead code elimination is the culprit.

This is one of the runs prior to eliminating dead code:

```sh
alex@smartalex-pc:~/Repositories/reaper$ hyperfine --runs 5 './target/release/reaper'
Benchmark 1: ./target/release/reaper
  Time (mean ± σ):     15.353 s ±  0.222 s    [User: 15.329 s, System: 0.003 s]
  Range (min … max):   15.080 s … 15.648 s    5 runs
  ```

Then, a diff that shows the dead code elimination:

```diff
alex@smartalex-pc:~/Repositories/reaper$ git diff
diff --git a/src/compiler.rs b/src/compiler.rs
index c900a62..7737521 100644
--- a/src/compiler.rs
+++ b/src/compiler.rs
@@ -49,7 +49,7 @@ pub enum Opcode {
     Null,
     Not,
     False,
-    DirectJmp(isize),
+    // DirectJmp(isize),
     Jmp(isize),
     Jz(isize),
     Ip,
diff --git a/src/vm.rs b/src/vm.rs
index 802b76c..628b842 100644
--- a/src/vm.rs
+++ b/src/vm.rs
@@ -160,9 +160,9 @@ impl VM {
                         _ => unimplemented!(),
                     }
                 }
-                Opcode::DirectJmp(addr) => {
-                    self.ip = addr;
-                }
+                // Opcode::DirectJmp(addr) => {
+                //     self.ip = addr;
+                // }
                 Opcode::Ip => {
                     self.frame_ptrs.push(self.stack.len());
                     self.stack.push(Object::BytecodePtr(self.ip + 1));
```

Then I measure again:

```sh
alex@smartalex-pc:~/Repositories/reaper$ hyperfine --runs 5 './target/release/reaper'
Benchmark 1: ./target/release/reaper
  Time (mean ± σ):     20.814 s ±  0.598 s    [User: 20.735 s, System: 0.061 s]
  Range (min … max):   20.368 s … 21.861 s    5 runs
```

Then I ran:

```sh
valgrind --tool=cachegrind --cachegrind-out-file=before.txt ./target/release/reaper
```

...and similarly for after introducing the change.

Then I ran:

```sh
cg_diff before.txt after.txt > cachegrind_diff.txt
cg_annotate cachegrind.diff
```

This is the result:

```
alex@smartalex-pc:~/Repositories/reaper$ cg_annotate cachegrind_diff.txt
--------------------------------------------------------------------------------
Files compared:   before.txt; after.txt
Command:          ./target/release/reaper; ./target/release/reaper
Data file:        cachegrind_diff.txt
Events recorded:  Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Events shown:     Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Thresholds:       0.1 100 100 100 100 100 100 100 100
Include dirs:
User annotated:
Auto-annotation:  on

--------------------------------------------------------------------------------
Ir                 I1mr        ILmr        Dr              D1mr         DLmr       Dw              D1mw         DLmw
--------------------------------------------------------------------------------
2,690,649 (100.0%) 89 (100.0%) -1 (100.0%) -3,742 (100.0%) 283 (100.0%) 0          -5,703 (100.0%) 983 (100.0%) 0           PROGRAM TOTALS

--------------------------------------------------------------------------------
Ir                 I1mr         ILmr         Dr              D1mr           DLmr        Dw              D1mw         DLmw         file:function
--------------------------------------------------------------------------------
2,692,537 (100.1%)   0            0               0              1 ( 0.35%)  0               0            1 ( 0.10%)  0           ???:reaper::vm::VM::run
    4,309 ( 0.16%) -16 (-18.0%)   0           1,140 (-30.5%)   -66 (-23.3%)  0             732 (-12.8%)  24 ( 2.44%)  0           ./malloc/./malloc/malloc.c:malloc_consolidate
   -3,778 (-0.14%)  10 (11.24%)  -2 (200.0%) -6,812 (182.0%)    60 (21.20%)  0          -6,899 (121.0%) 543 (55.24%)  1 ( 0.00%)  ./string/../sysdeps/x86_64/multiarch/memmove-vec-unaligned-erms.S:__memcpy_avx_unaligned_erms
   -3,725 (-0.14%) -13 (-14.6%)   0           1,494 (-39.9%)   131 (46.29%)  0             469 (-8.22%)  27 ( 2.75%)  0           ./malloc/./malloc/malloc.c:_int_malloc
    2,846 ( 0.11%)   5 ( 5.62%)  5 (-500.0%)  1,122 (-30.0%)    21 ( 7.42%)  0             788 (-13.8%)   0           0           ???:_ZN6reaper6parser6Parser7advance17hb089a00bb9d701b5E.llvm.15398215340703958719
   -2,846 (-0.11%)  -5 (-5.62%)  -5 (500.0%) -1,122 (29.98%)   -21 (-7.42%)  0            -788 (13.82%)   0           0           ???:_ZN6reaper6parser6Parser7advance17hb089a00bb9d701b5E.llvm.3539562641597384957
      744 ( 0.03%)  35 (39.33%) 35 (-3500.0%)    250 (-6.68%)     1 ( 0.35%)  0             192 (-3.37%)   9 ( 0.92%)  0           ???:_ZN6reaper6parser6Parser15parse_statement17h6e655a759fcc80e1E.llvm.15398215340703958719
     -744 (-0.03%) -35 (-39.3%) -35 (3500.0%)   -250 ( 6.68%)    -1 (-0.35%)  0            -192 ( 3.37%)  -8 (-0.81%)  0           ???:_ZN6reaper6parser6Parser15parse_statement17h6e655a759fcc80e1E.llvm.3539562641597384957
     -672 (-0.02%) -14 (-15.7%)  -1 (100.0%)   -182 ( 4.86%)    -3 (-1.06%)  0            -168 ( 2.95%)   0           0           ???:_ZN5alloc7raw_vec11finish_grow17h79660387e70e3dacE.llvm.6763387729585670434
      672 ( 0.02%)  14 (15.73%)  1 (-100.0%)    182 (-4.86%)     2 ( 0.71%)  0             168 (-2.95%)   0           0           ???:_ZN5alloc7raw_vec11finish_grow17h79660387e70e3dacE.llvm.6537312952205804509

--------------------------------------------------------------------------------
The following files chosen for auto-annotation could not be found:
--------------------------------------------------------------------------------
  ./malloc/./malloc/malloc.c
  ./string/../sysdeps/x86_64/multiarch/memmove-vec-unaligned-erms.S
```

As far as I can see, the instruction count difference is around 2.7M.

I suppose it's a long shot that we have a compiler bug, but I'd still appreciate it if you looked at the issue, or at least gave me a pointer in the right direction as to where to look next.

P.S.

I tried reproducing the issue on a minimal example by eliminating the tokenizer, the parser, and the compiler, and just having the vm go through the bytecode, but I haven't been able to reproduce it.