Algorithm recognition based on demand-driven data-flow analysis

Algorithm recognition is an important problem in pro-gram analysis, optimization, and more particularly pro-gram comprehension. Basically, one would like to submit a piece of code, and get an answer like “Lines 10 to 23 are an implementation of Gauss-Jordan elimination”. Existing approaches often perform a bottom-up recognition, using a database describing many implementation variations of a given algorithm, in a format making them difficult to main-tain. In this paper, we present a new method to recognize al-gorithm templates in a program. We perform a top-down recognition, stopping at template variables and thus lim-iting the need for many program variations. The code to analyze is given in SSA form, and the -functions are com-puted on-demand, when computation is possible, along the candidate slices.