Unbounded stack growth during interpretation

[Matt Giuca]

Something is causing interpret.m to be non-tail-recursive, which means each time the execution enters a new basic block, the Mercury stack is pushed.

This means execution uses O(n) space after time n, which is incredibly bad. It means Mars can't handle programs which run for any real length of time.

A quick scan of interpret.m doesn't help -- everything appears to be tail-recursive.

This bug may just wait until a new execution engine is written (interpretation of a bytecode in C, or something along those lines).

[Matt Giuca (mgiuca)]

A detailed study of interpret.m shows the following relationships:

exec_block:
    exec_block_body
exec_block_body:
    foldl(exec_instr)
    exec_block

The mutual recursion between exec_block and exec_block_body is causing problems with the last-call optimizer in Mercury. It seems like a bug in Mercury but it's pretty hard to tell (it's some kind of heuristic). From experimenting, commenting out the calls to exec_instr fixes the problem (which makes no sense -- it isn't involved in either lastcall). Also it appears to be the call to exec_block_body which is pushing the stack; the call to exec_block extends the stack by 0, while the call to exec_block_body extends it by 96 bytes.

From what I have gathered from these experiments, Mercury *always* handles self-recursion properly but doesn't always handle mutual recursion if there are other complex calls. (It handles mutual recursion in some cases though). The solution should just be to manually inline exec_block_body into exec_block, making it self-recursion.

[Matt Giuca (mgiuca)]

Also note that there is a second issue which affects stack usage for execution: each instruction in a block is executed at a different stack location (actually the stack addresses *ascend* rather than descending, meaning the stack is shrinking). That's because the instructions in a block are executed in a foldr (in exec_block_body) rather than a foldl.

Obviously not ideal (it means linear stack space is used rather than constant), but it's still linear in the size of the block, which is constant in the runtime of the program (it's a nuisance, but it doesn't cause this bug).

Note that you can use context.debug_stackframe to print out these stackframes.

[Matt Giuca (mgiuca)]

Fixed in trunk r891 (manually inlined exec_block_body into exec_block).
Note that this does *not* make Mars programs tail-call-safe (Mars programs themselves will experience unbounded stack growth on recursion). But it makes iteration in Mars (while loops) execute in constant space.