Instancewise Array Dependence Test for Recursive Programs

International audienceStarting from a generalization of induction variables,we present a dependence test framework for recursive programs. For a restricted class of programs, a statically computable function maps every run-time instance of a programstatement to the data-structure elements it accesses. Statement instances and data structure layouts are describedthrough formal language tools.This framework is applied to the automatic detection ofdata and control parallelism. We extend the concept of instancewise data dependences to recursive programs and wefurther investigate a dependence test for recursive programsoperating on arrays. This test is interpreted as a flow problem in a directed graph with weighted edges; and the problem is shown to be NP-complete. We provide an exponentialbut efficient algorithm based on integer linear programmingand explore simple examples