cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 
pafisep
Visitor
Visitor
9,104 Views
Registered: ‎01-14-2010

Vivado HLS and Tail Recursive Functions

Jump to solution

 

Reading  the  PDF of "Vivado Design Suite User Guide - High-Level Synthesis - UG902 (v2012.2) July 25, 2012", on page 53 it says: 

 

"Tail recursion is synthesizable."

 

But on page 286 it says: 

 

"Tail recursion, where there are a finite number of function calls, is also not supported:" 

 

There is only one example for both: 

 

unsigned foo (unsigned m, unsigned n)

                   {

                   if (m == 0) return n;

                   if (n == 0) return m;

                   return foo(n, m%n);

                   }

 

Am I missing something, or is the manual wrong? 

 

Is tail recursion supported or not?

 

Many Thanks

 

Paulo Ferreira

 

0 Kudos
1 Solution

Accepted Solutions
herver
Xilinx Employee
Xilinx Employee
10,897 Views
Registered: ‎08-17-2011

Hello Paulo,

 

 

I double checked on that following your last post and yes effectively, the support for tail recursive functions have been removed. The tool will error out on them.

 

Since tail recursion is basically a loop in disguise, the simple functions can easily be transformed as the gcd example from the UG you highlighted:

 

    while( m!=0 & n!=0 ) {    //or same: while( m>0 & n>0 ) {
        unsigned int mmodn=m%n;
        m=n;
        n=mmodn;
    }

   if (m == 0) return n;
   else return m;

 

Please note that the example with the classes should still work as this is all static and determined at compile time.

 

I hope this helps.

- Hervé

SIGNATURE:
* New Dedicated Vivado HLS forums* http://forums.xilinx.com/t5/High-Level-Synthesis-HLS/bd-p/hls
* Readme/Guidance* http://forums.xilinx.com/t5/New-Users-Forum/README-first-Help-for-new-users/td-p/219369

* Please mark the Answer as "Accept as solution" if information provided is helpful.
* Give Kudos to a post which you think is helpful and reply oriented.

View solution in original post

7 Replies
bassman59
Historian
Historian
9,094 Views
Registered: ‎02-25-2008

What does this have to do with Synthesis?

----------------------------Yes, I do this for a living.
0 Kudos
herver
Xilinx Employee
Xilinx Employee
9,091 Views
Registered: ‎08-17-2011

Hello Paulo,



The tail recursion is supported - AFAIK the statement you point on page 286 is incorrect: if you ignore it, all the references to tail recursion make sense and are consistent.

The "normal" recursion is not supported for the reasons explained in UG902.

There is a another tail recursion in C++ later at page 293.

- Hervé

SIGNATURE:
* New Dedicated Vivado HLS forums* http://forums.xilinx.com/t5/High-Level-Synthesis-HLS/bd-p/hls
* Readme/Guidance* http://forums.xilinx.com/t5/New-Users-Forum/README-first-Help-for-new-users/td-p/219369

* Please mark the Answer as "Accept as solution" if information provided is helpful.
* Give Kudos to a post which you think is helpful and reply oriented.
herver
Xilinx Employee
Xilinx Employee
9,088 Views
Registered: ‎08-17-2011
true.. at the moment HLS posts could go into the "Design Tools - Others" board.
- Hervé

SIGNATURE:
* New Dedicated Vivado HLS forums* http://forums.xilinx.com/t5/High-Level-Synthesis-HLS/bd-p/hls
* Readme/Guidance* http://forums.xilinx.com/t5/New-Users-Forum/README-first-Help-for-new-users/td-p/219369

* Please mark the Answer as "Accept as solution" if information provided is helpful.
* Give Kudos to a post which you think is helpful and reply oriented.
0 Kudos
pafisep
Visitor
Visitor
9,065 Views
Registered: ‎01-14-2010

 

Sorry for having placed the question in this forum, but on the description of this forum there is the mention of  Vivado HLS...

 

And many thanks for the answer!

 

Paulo Ferreira

0 Kudos
herver
Xilinx Employee
Xilinx Employee
9,045 Views
Registered: ‎08-17-2011

No problems about the location.. The description for the synthesis folder has been updated to remove the HLS mention.

Users can still post there but they should use the "design tools - others" folder / board.

 

About the tail recursion: glad that helped to clarify the situation. Let us know if you have any issues with that/other.

- Hervé

SIGNATURE:
* New Dedicated Vivado HLS forums* http://forums.xilinx.com/t5/High-Level-Synthesis-HLS/bd-p/hls
* Readme/Guidance* http://forums.xilinx.com/t5/New-Users-Forum/README-first-Help-for-new-users/td-p/219369

* Please mark the Answer as "Accept as solution" if information provided is helpful.
* Give Kudos to a post which you think is helpful and reply oriented.
0 Kudos
pafisep
Visitor
Visitor
8,821 Views
Registered: ‎01-14-2010

Well, I fiinally got a license for Vivado_HLS, and trying the examples from tthe manual, it says that recursion is not supported.  

 

Reading the "fine" manual  with lots of care it seems that "tail recursion" was "supported" on the first releease(s) but now  there is no support for tail recursion.

 

The mention of "tail recursion" being supported  has disappeared on the change from  version 2012.2 to version 2012..3  of the High Level Synthesis User Guide...    

 

So, I  will need to do it, in another way.

 

So, the last word is: on  Vivado HLS  2012.4  tail recursive functions are not supported..

 

 My best regrads

Paulo Ferreira 

 

 

 

0 Kudos
herver
Xilinx Employee
Xilinx Employee
10,898 Views
Registered: ‎08-17-2011

Hello Paulo,

 

 

I double checked on that following your last post and yes effectively, the support for tail recursive functions have been removed. The tool will error out on them.

 

Since tail recursion is basically a loop in disguise, the simple functions can easily be transformed as the gcd example from the UG you highlighted:

 

    while( m!=0 & n!=0 ) {    //or same: while( m>0 & n>0 ) {
        unsigned int mmodn=m%n;
        m=n;
        n=mmodn;
    }

   if (m == 0) return n;
   else return m;

 

Please note that the example with the classes should still work as this is all static and determined at compile time.

 

I hope this helps.

- Hervé

SIGNATURE:
* New Dedicated Vivado HLS forums* http://forums.xilinx.com/t5/High-Level-Synthesis-HLS/bd-p/hls
* Readme/Guidance* http://forums.xilinx.com/t5/New-Users-Forum/README-first-Help-for-new-users/td-p/219369

* Please mark the Answer as "Accept as solution" if information provided is helpful.
* Give Kudos to a post which you think is helpful and reply oriented.

View solution in original post