copy-propagation causes regression in juvix-stdlib test suite

[paulcadman]

To Reproduce

• Install juvix at current main or the commit 235d88f3037abbe12b980d9994c6dc742e7b590c (i.e the commit for #2828 - Copy propagation in JuvixReg)
• Run the test suite in the juvix-stdlib test suite:

$ cd juvix-stldib
$ make test
...
...
[101 of 101] Compiling /home/paul/code/juvix/juvix-stdlib/test/Test.juvix
od -An -N2 -t u2 /dev/urandom | xargs | ./build/Test
Killed
make[1]: *** [Makefile:10: test] Error 137
make[1]: Leaving directory '/home/paul/code/juvix/juvix-stdlib/test'

This is an out-of-memory error.

Running without copy-propagation works

The juvix-stdlib test suite runs successfully, and only uses a small amount of memory if it run with the copy-propagation transformation disabled (either by using the commit immediately before the copy-propagation PR, or by manually removing the CopyPropogation transformationId from the toCTransformations list in the Juvix reg pipeline definition.

/usr/bin/time -v od -An -N2 -t u2 /dev/urandom | xargs |./test/build/Test
    Command being timed: "od -An -N2 -t u2 /dev/urandom"
    User time (seconds): 0.00
    System time (seconds): 0.00
    Percent of CPU this job got: 50%
    Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.00
    Average shared text size (kbytes): 0
    Average unshared data size (kbytes): 0
    Average stack size (kbytes): 0
    Average total size (kbytes): 0
    Maximum resident set size (kbytes): 1832
    Average resident set size (kbytes): 0
    Major (requiring I/O) page faults: 0
    Minor (reclaiming a frame) page faults: 91
    Voluntary context switches: 1
    Involuntary context switches: 0
    Swaps: 0
    File system inputs: 0
    File system outputs: 0
    Socket messages sent: 0
    Socket messages received: 0
    Signals delivered: 0
    Page size (bytes): 4096
    Exit status: 0
'partition: recombination of the output equals the input': success
'reverse preserves length': success
'reverse of reverse is identity': success
'splitAt: recombination of the output is equal to the input list': success
'splitAt: Check lengths of output if the input Nat is greater than the length of the input list': success
'merge: sum of the lengths of input lists is equal to the length of output list': success
'tail: length of output is one less than input unless empty': success
'equal Nats compare to EQ': success
'zip properties': success
'zipWith properties': success
'snoc properties': success
'drop properties': success
'sort properties: mergeSort': success
'sort properties: quickSort': success
'transpose: recrangular matrix has property transpose . transpose = id': success
'transpose: transpose swaps dimensions': success
All tests passed

[lukaszcz]

The comment at https://github.com/anoma/juvix/blob/main/src/Juvix/Compiler/Reg/Data/TransformationId.hs#L25 is not correct. In fact, copy propagation cannot be used in the C pipeline without adjusting the live variables afterwards. It's not true that all variables are considered live: only the ones representing the current stack in JuvixAsm. Consider the situation when a stack was bigger before and then popped, e.g. the top of it got translated to a variable tmp[n+1] which was later assigned to tmp[n], then there was a call with variables up to tmp[n] saved (but not tmp[n+1]), then tmp[n] is used. After copy propagation tmp[n+1] is used after the call instead of tmp[n], but because the live variables for the call (which are supposed to be saved) didn't get adjusted, this is not correct - tmp[n+1] contains an unspecified value.

[lukaszcz]

Copy propagation should be removed from the C pipeline until we have liveness computation in JuvixReg. I'll add a test which exposes this in the test suite.

[lukaszcz]

Actually, our test suite catches this, but we just didn't run the JuvixReg transformations when compiling in the test suite (in contrast to compiling via CLI). In the tests, we used regToMiniC' (https://github.com/anoma/juvix/blob/main/src/Juvix/Compiler/Pipeline.hs#L379), which doesn't call Reg.toC unlike regToMiniC (https://github.com/anoma/juvix/blob/main/src/Juvix/Compiler/Pipeline.hs#L344) used in the CLI. So copy propagation was never performed in the tests.