High-level synthesis compile optimization algorithm for recursive functions

Based on function call graph (FCG) and branch decision strategy, this paper presents an optimization algorithm during high-level synthesis (HLS) to handle recursion. Firstly, FCG is proposed to eliminate the recursive calls within the LLVM compiler infrastructure, then construction rules of the decision tree is introduced to remove branch condition judgment and non-called branch. Finally sub-function reuse and dynamic resource pre-evaluation is adopted to prevent code explosion. Compared with the inline algorithm RecursionHW, experimental results show that the presented algorithm can get an average resource reduction by 63%, and the maximum clock frequency can be increased 3.2 times averagely. Moreover, the HLS time is reduced exponentially with the increase of recursion depth.