EXPLOITATION OF SYMBOLIC INFORMATION IN INTERPROCEDURAL DEPENDENCE ANALYSIS

The requirement for a very accurate dependence analysis to underpin so ftware tools to aid the generation of efficient parallel implementatio ns of scalar code is argued. The current status of dependence analysis is shown to be inadequate for the generation of efficient parallel co de, causing too many conservative assumptions to be made. This paper s ummarises the limitations of conventional dependence analysis techniqu es, and then describes a series of extensions which enable the product ion of a much more accurate dependence graph. The extensions include a nalysis of symbolic variables, the development of a symbolic inequalit y disproof algorithm and its exploitation in a symbolic Banerjee inequ ality test; the use of inference engine proofs; the exploitation of ex act dependence and dependence pre-domination attributes; interprocedur al array analysis; conditional variable definition tracing; integer ar ray tracing and division calculations. Analysis case studies on typica l numerical code is shown to reduce the total dependencies estimated f rom conventional analysis by up to 50%. The techniques described in th is paper have been embedded within a suite of tools, CAPTools, which c ombines analysis with user knowledge to produce efficient parallel imp lementations of numerical mesh based codes.