Interactive and Symbolic Data Dependence Analysis Based on Renges of Expressions

Traditional data dependence testing algorithms have becomevery accurate and efficient for simple subscript expressions, but theycannot handle symbolic expressions because of the complexity ofdata-flow and lack of the semantic information of variables inprograms. In this paper, a range-based testing and query approach,called DDTQ, is proposed to eliminate data dependence between arrayreferences with symbolic subscripts. DDTQ firstly extracts datadependence information from the symbolic subscripts, a testingalgorithm is then used to disprove the dependence based on the rangesof expressions. The assumed dependence that cannot be handled by thedisprover will be converted into simple questions by a question engineso that the compiler can solve them by user interaction in a friendlyway. The experiment on perfect benchmarks indicates that DDTQ iseffective in improving the parallelizing capability of the compiler.