search

google / xls

XLS: Accelerated HW Synthesis
http://google.github.io/xls/
Apache License 2.0
1.21k stars 178 forks source link

Specifying naturally recursive definitions without switching to iterative #510

Open cdleary opened 3 years ago

cdleary commented 3 years ago

Right now in the DSL recursive definitions are disallowed. This mostly makes sense: we don't support general recursion due to everything being fixed space, and we don't have any tail call detection / optimization facilities. However, there are a bunch of algorithms that lend themselves nicely to a recursive definition that we should find a way to express so we have have to force everything to be expressed iteratively; i.e. leading zeros detection with a balanced tree could be a good one: https://electronics.stackexchange.com/a/412278

hzeller commented 1 year ago

I am currently at such a point where this would be useful (leading zero anticipator based on Bruguera and Lang).

Like in the example you state, already useful would be just a subset of recursion where the recursive definition is just based on the template parameters and not any runtime values.

If we see that there is a return branch that is just based on a template parameter that will not it itself contain a recursive call, this could be the initial litmus test to allow the recursion (which then can be limited in the expansion at compile time to be less than some N to stop non-terminating recursions).

This would allow for the most useful class for recursive algorithms in hardware.