Support coroutines in LLVM lowering for Robot/Turtle animation

[resetius]

Motivation

Currently, Robot and Turtle executor programs run synchronously -- all movements happen instantly, making it impossible to see the animation step by step. Users want to see the robot moving cell by cell with visual feedback.

Current Workaround

The existing animation implementation uses a history-based replay approach:

1. The WASM program runs to completion synchronously
2. All robot movements are recorded in a history array (__robotHistory)
3. After execution completes, JavaScript replays the history with delays between steps

This workaround has significant limitations:

• No interactivity: User cannot pause/step through during actual execution
• Memory overhead: Entire history must be stored
• No infinite loops: Programs with infinite loops (e.g., нц пока истина) hang the browser
• Delayed errors: Runtime errors (e.g., hitting a wall) are detected during replay, not during actual logic execution
• Two-phase execution: Confusing separation between "run" and "animate" phases

Desired Behavior

With coroutines:

• Each robot/turtle command yields control back to JavaScript
• JavaScript controls timing between steps (animation delay)
• User can pause, step, or stop execution at any point
• Infinite loops work correctly -- each iteration yields
• Errors are reported immediately at the point they occur

Architecture Overview

1. Type System Extension

Introduce Future<T> type to mark functions that may suspend:

// Runtime functions that cause suspension
declare Future<void> @robot_up()
declare Future<void> @robot_down()
declare Future<void> @robot_left()
declare Future<void> @robot_right()
declare Future<void> @robot_paint()
declare Future<void> @turtle_forward(double)
declare Future<void> @turtle_back(double)
declare Future<void> @turtle_left(double)
declare Future<void> @turtle_right(double)
// ... etc

// User functions that transitively call suspend points become coroutines automatically
// алг цел f()  →  Future<int> f()  (if f calls robot_up transitively)

2. AST/Semantic Analysis Phase

Transitive analysis:

• Build call graph
• Mark all functions that (directly or indirectly) call Future<T> functions
• Transform return type from T to Future<T> for such functions

Call site transformation:

• Mark calls to Future<T> functions as await points

Example transformation:

// Original Kumir
алг цел f()
нач
  вверх
  знач := 42
кон

// After type annotation
алг Future<цел> f()
нач
  await вверх      // marked as await point
  знач := 42
кон

3. IR Lowering Phase

Transform function calls based on callee type:

// Regular call (non-coroutine)
%result = call i32 @regular_func()

// Await call (coroutine) — new IR node or annotation
%result = await_call Future<i32> @coro_func()

4. LLVM Codegen Phase

Generate LLVM coroutine intrinsics:

define ptr @f() presplitcoroutine {
entry:
  %promise = alloca i32  ; result slot for return value
  %id = call token @llvm.coro.id(i32 0, ptr %promise, ptr null, ptr null)
  %size = call i32 @llvm.coro.size.i32()
  %alloc = call ptr @malloc(i32 %size)
  %hdl = call ptr @llvm.coro.begin(token %id, ptr %alloc)

  ; Call child coroutine and await
  %child = call ptr @robot_up_coro()
  br label %await_child

await_child:
  %child_resume = load ptr, ptr %child
  %child_done = icmp eq ptr %child_resume, null
  br i1 %child_done, label %after_child, label %resume_child

resume_child:
  call void %child_resume(ptr %child)
  %s1 = call i8 @llvm.coro.suspend(token none, i1 false)
  switch i8 %s1, label %suspend [i8 0, label %await_child
                                  i8 1, label %cleanup]

after_child:
  ; Destroy child coroutine
  %child_destroy = getelementptr ptr, ptr %child, i32 1
  %destroy_fn = load ptr, ptr %child_destroy
  call void %destroy_fn(ptr %child)

  ; Store result before final suspend
  store i32 42, ptr %promise

  ; Final suspend
  %sf = call i8 @llvm.coro.suspend(token none, i1 true)
  switch i8 %sf, label %suspend [i8 0, label %suspend
                                  i8 1, label %cleanup]

cleanup:
  %mem = call ptr @llvm.coro.free(token %id, ptr %hdl)
  call void @free(ptr %mem)
  br label %suspend

suspend:
  call i1 @llvm.coro.end(ptr %hdl, i1 false, token none)
  ret ptr %hdl
}

; Helper to get result from completed coroutine
define i32 @f_get_result(ptr %hdl) {
  %promise = call ptr @llvm.coro.promise(ptr %hdl, i32 4, i1 false)
  %result = load i32, ptr %promise
  ret i32 %result
}

5. JavaScript Runtime

async function runCoroutine(instance) {
  const mainHandle = instance.exports.main();
  const memory = instance.exports.memory;
  const table = instance.exports.__indirect_function_table;

  const isDone = (handle) => {
    const resumePtr = new Uint32Array(memory.buffer, handle, 1)[0];
    return resumePtr === 0;
  };

  const resume = (handle) => {
    const resumeIdx = new Uint32Array(memory.buffer, handle, 1)[0];
    const resumeFn = table.get(resumeIdx);
    resumeFn(handle);
  };

  const destroy = (handle) => {
    const destroyIdx = new Uint32Array(memory.buffer, handle + 4, 1)[0];
    const destroyFn = table.get(destroyIdx);
    destroyFn(handle);
  };

  // Animation loop
  while (!isDone(mainHandle)) {
    resume(mainHandle);
    renderRobotField();
    await new Promise(r => setTimeout(r, animationDelay));
  }

  const result = instance.exports.main_get_result(mainHandle);
  destroy(mainHandle);
  return result;
}

Subtasks

• Type annotation pass: Analyze call graph, mark transitive coroutine functions, transform types to Future<T>
• IR representation: Add await_call node or annotation to distinguish coroutine calls from regular calls
• LLVM lowering: Generate presplitcoroutine functions with proper suspend/resume/await patterns
• Result passing: Implement llvm.coro.promise for returning values from coroutines
• JS runtime update: Modify robot.js/turtle.js to handle coroutine-based execution with animation control
• Runtime function markers: Define which imported functions return Future<T> (robot_, turtle_)
• Remove history workaround: Delete replay-based animation code once coroutines work

Technical Notes

LLVM Coroutine Passes

Required optimization passes:

opt -passes='coro-early,coro-split,coro-elide,coro-cleanup'

Coroutine Frame Structure

After lowering, LLVM creates a frame structure:

%coro.Frame = type { ptr, ptr, i2, ... }
;                    │     │    │
;                    │     │    └── state (suspend point index)
;                    │     └── destroy function pointer
;                    └── resume function pointer

• resume_fn_ptr == NULL indicates coroutine is at final suspend (done)
• Promise/result is stored at known offset in frame

WASM Considerations

• WASM uses function table (__indirect_function_table) for indirect calls
• Resume and destroy functions are called via table indices
• Memory layout must be consistent between LLVM codegen and JS runtime

References

• LLVM Coroutines Documentation
• Coroutines in LLVM (talk)
• paolosev/wasm-llvm-coro — Minimal WASM coroutine example (fork with working code)