[enhancement] Infinite loops in DSLX

[rw1nkler]

What's hard to do? (limit 100 words)

There are no infinite loops in DSLX. Having them would vastly improve expressiveness of the language, and would make it more software-like.

We've observed that procs with a simple, linear data flow (without state) are efficiently pipelined by the toolchain. To keep our designs simple, we found ourselves moving looping logic to auxiliary procs, allowing the main (parent) proc to remain "stateless" while the auxiliary proc maintains the minimal state needed for the loop. This approach is particularly useful for implementing sequential logic with multiple loops.

Current best alternative workaround (limit 100 words)

When the number of iteration is unknown, one is forced to use proc, and preserve the iterator (or any other variable) in a state, to later use it to finish looping and send back the result.

Your view of the "best case XLS enhancement" (limit 100 words)

DSLX could support infinite loops by translating them into separate procs underneath. These "loop" procs could then be scheduled independently, simplifying data flow in the parent proc and eliminating the need for auxiliary procs.

Here are some examples of procs with infinite loops with a recipe how to translate them to procs.

Simple example

This example shows a simple proc without any IOs in the loop.

proc SimpleExample {
    next(state: ()) {
        let (tok, init_val) = recv(join(), input_r);

        let result = loop (i: u32) {
           if i % u32:2 == 0 {
               trace_fmt!("Even");
           } else {
               trace_fmt!("Odd");
           };

           if i > 10 {
               break i;
           };
           i + 1
       }(init_val)

       send(tok, result_s, result);
   }
}

This can be later translated to the following code:

struct LoopState {
    // an auxiliary variable indicating if the loop is active
    // used to prevent reading from input if we are executing the loop logic
    active: bool,

    // other state variables
    i: u32,
}

proc Loop {
   init_r: chan<u32> in;
   result_s: chan<u32> out;

   init { zero!<LoopState>() }

   config (
       init_r: chan<u32> in,
       result_s: chan<u32> out,
   ) {
       (init_r, result_s)
   }

   next(state: LoopState) {
       // The proc should receive initial values for all state variables
       let (tok, i) = recv_if(join(), init_r, !state.active, state.i);

       // this is the main logic of the loop
       if i % u32:2 == u32:0 {
           trace_fmt!("Even")
       } else {
           trace_fmt!("Odd")
       };

       // condition of break is used to send the result...
       let cond = i > u32:100;
       let tok = send_if(tok, result_s, cond, i);

       // .. and reset the loop proc to its initial state
       if cond {
           zero!<LoopState>()
       } else {
           LoopState { active:true, i: i + u32:1 }
       }
   }
}

The SimpleExample proc with an infinite loop can be transformed to the following code, to make use of the Loop proc:

proc TransformedSimpleExample {
    input_r: chan<u32> in;
    result_s: chan<u32> out;
    loop_input_s: chan<u32> out;
    loop_result_r: chan<u32> in;

    init {}

    config(
        input_r: chan<u32> in,
        result_s: chan<u32> out,
    ) {
        let (loop_input_s, loop_input_r) = chan<u32>("loop_input");
        let (loop_result_s, loop_result_r) = chan<u32>("loop_result");

        spawn Loop(loop_input_r, loop_result_s);

        (
            input_r, result_s,
            loop_input_s, loop_result_r,
        )
    }

    next(state: ()) {
        let (tok, init_val) = recv(join(), input_r);

        // the parent proc should send all input variables to the loop proc
        let tok = send(tok, loop_input_s, init_val);
        // later it should block on receiving the result of the loop
        let (tok, result) = recv(tok, loop_result_r);

        send(tok, result_s, result);
    }
}

This example together with a test proc can be found here, to run it use:

bazel run -- //xls/examples:inf_loop_simple_dslx_test --logtostderr

IO example

The following example uses IO operations in the infinite loop. All of the channels used in the loop should be forwarded to the Loop proc.

Here is a proc with the loop:

proc IOExample {

    input_r: chan<u32> in;
    result_s: chan<u32> out;
    data_r: chan<u32> in;

    init {}

    config(
        input_r: chan<u32> in,
        result_s: chan<u32> out,
        data_r: chan<u32> in,
    ) {
        (input_r, result_s, data_r,)
    }

    next() {
        let (tok, init_val) = recv(join(), input_r);

        let result = loop (u32: sum) {
            let (_, data) = recv(tok, data_r);
            let sum = sum + data;

            if sum > 100 {
                break sum;
            } else {};

            sum
        }(init_val);

        send(tok, result_s, result);
    }
}

The following snippet shows the equivalent implementation that uses a "Loop" proc:

struct LoopState {
    // An auxiliary variable indicating if the loop is active.
    // It is used to prevent reading from input when we are executing the loop logic
    active: bool,

    // other state variables
    sum: u32,
}

proc Loop {
    input_r: chan<u32> in;
    result_s: chan<u32> out;
    data_r: chan<u32> in;

    init { zero!<LoopState>() }

    config (
        input_r: chan<u32> in,
        result_s: chan<u32> out,

        // All the channels used in the loop should be forwarded to the "Loop" proc
        data_r: chan<u32> in,
    ) {
        (input_r, result_s, data_r)
    }

    next(state: LoopState) {
        // The proc should receive initial values for all state variables
        let (tok, sum) = recv_if(join(), input_r, !state.active, state.sum);

        // this is the main logic of the loop
        let (_, data) = recv(tok, data_r);
        let sum = sum + data;

        // condition before the break is used to send the result...
        let cond = sum > u32:100;
        let tok = send_if(tok, result_s, cond, sum);

        // .. and reset the loop proc to its initial state
        if cond {
            zero!<LoopState>()
        } else {
            LoopState { sum, active:true }
        }
    }
}

proc TranslatedIOExample {
    input_r: chan<u32> in;
    result_s: chan<u32> out;
    loop_input_s: chan<u32> out;
    loop_result_r: chan<u32> in;

    init {}

    config(
        input_r: chan<u32> in,
        result_s: chan<u32> out,
        data_r: chan<u32> in,
    ) {
        let (loop_input_s, loop_input_r) = chan<u32>("input");
        let (loop_result_s, loop_result_r) = chan<u32>("result");

        spawn Loop(
            loop_input_r, loop_result_s,
            // Channels used in the infinite loop should be forwarded to the "Loop" proc
            data_r
        );

        (
            input_r, result_s,
            loop_input_s, loop_result_r,
        )
    }

This example together with a test proc can be found here, to run it use:

bazel run -- //xls/examples:inf_loop_io_dslx_test --logtostderr

FYI @richmckeever @proppy