Open ColonelPhantom opened 2 years ago
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)
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)
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.