feat(tvix/eval): implement OpTailCall r/4783

If the last operation within a chunk is a function call, the call can
be executed in the same call frame without increasing the depth of the
call stack.

To enable this, a new OpTailCall instruction (similar to OpCall) is
introduced, but not yet emitted by the compiler.

Change-Id: I9ffbd7da6d2d6a8ec7a724646435dc6ee89712f2
Reviewed-on: https://cl.tvl.fyi/c/depot/+/6457
Tested-by: BuildkiteCI
Reviewed-by: sterni <sternenseemann@systemli.org>

1 files changed, 12 insertions, 0 deletions

diff --git a/tvix/eval/src/observer.rs b/tvix/eval/src/observer.rs
index 677c3f0811e7..8dc2a6a0ca96 100644
--- a/tvix/eval/src/observer.rs
+++ b/tvix/eval/src/observer.rs
@@ -41,6 +41,10 @@ pub trait Observer {
     /// Called when the runtime exits a call frame.
     fn observe_exit_frame(&mut self, _frame_at: usize) {}
 
+    /// Called when the runtime replaces the current call frame for a
+    /// tail call.
+    fn observe_tail_call(&mut self, _frame_at: usize, _: &Rc<Lambda>) {}
+
     /// Called when the runtime enters a builtin.
     fn observe_enter_builtin(&mut self, _name: &'static str) {}
 
@@ -150,6 +154,14 @@ impl<W: Write> Observer for TracingObserver<W> {
         let _ = writeln!(&mut self.writer, "=== exiting builtin {} ===", name);
     }
 
+    fn observe_tail_call(&mut self, frame_at: usize, lambda: &Rc<Lambda>) {
+        let _ = writeln!(
+            &mut self.writer,
+            "=== tail-calling {:p} in frame[{}] ===",
+            lambda, frame_at
+        );
+    }
+
     fn observe_execute_op(&mut self, ip: usize, op: &OpCode, stack: &[Value]) {
         let _ = write!(&mut self.writer, "{:04} {:?}\t[ ", ip, op);