Recursive algorithm support?

[ColonelPhantom]

Silice's algorithms are turned into FSM's internally, as I understand it.

Would it be possible to support (depth-limited) recursion by storing the FSM state on a stack, then popping on a return? I imagine this could be challenging as most conventional HLS tools don't do this, yet it could also make Silice a lot easier to express certain classes of algorithms in. And Silice's FSM way of working seems to me relatively easy ("call" state pushes current state, sets inputs to recursive call inputs, and goes to initial state. Then when done detect if we are inside a recursive call and if so pop the entire state again).

Tail recursion might also be nice to add.

[sylefeb]

Hi - sorry for not chiming in earlier, this is an interesting suggestion, thanks! At some point in the past, Silice had such a limited stack (which size could be specified when instantiating an algorithm, there's even still a stack: in the grammar). It was used for subroutines in particular, and subroutines could recurse. However there was a cost in logic, and in particular synthesis was no longer seeing and optimizing for an FSM. But there were upsides too, and this interacts with other ideas regarding chaining subroutines. I'll keep this issue open, let me think about it and see what can/could be done. (edit:typos)

[sylefeb]

Even though that is different from your suggestion, I just wanted to mention recursive instantiation (which I just improved, please test in the wip branch, fixes are not yet in master).

Here is an example of a recursive algorithm definition (if familiar with C++, think of it as a recursive template):

algorithm sum_N_first(input uint8 i,output uint8 o)
{
$$if N > 0 then
  sum_N_first s<N=$N-1$>; // recursive inclusion of the algorithm
  __display("calling %d\n",$N$);
  (o) <- s <- (i+$N$);    // recurse call
$$else
  o = i;                  // stopping case (recursion 'bottom')
$$end  
}

unit main(output uint8 leds)
{
  sum_N_first s<N=8>;    // top of the resursive instantiation
  algorithm {
    uint8 n(0);
    (n) <- s <- ();      // call
     __display("%d\n",n);
  }
}

(source)

This creates a chains of algorithm calls, which depth is controlled by N=8 in the main.

But of course this could be made without any calls, using a recursive unit with always blocks:

unit sum_N_first(output uint8 o(0)) // <- note the default value of 0
{
$$if N > 0 then
  sum_N_first s<N=$N-1$>;    // recursive inclusion of the unit
	always { o = s.o + $N$; }  // defines the output recursively
$$end  
}

unit main(output uint8 leds)
{
  sum_N_first s<N=8>;       // paramtererized instantiation
  algorithm {
     __display("%d\n",s.o); // show the result
  }
}

(source)