Developing a software tool to identify and eliminate aliases inc programs for data dependency analysis
Loading...
Date
1997
Authors
Raja Gopal, Parimaladevi
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The development of parallel computers has raised the need for parallel programs.
The lack of suitable software is the major obstacle for the full utilisation of the parallel
architectures. Developing a parallelizing compiler would be the best solution to reuse all
the existing sequential programs in the parallel platform.
The conversion from sequential to parallel code needs a detailed study on the data
being used in the sequential programs. The data dependencies that exist in a sequential
program have to be detected and proper actions should be taken in order to get the accurate
parallel code.
Data dependency analysis becomes a tough task to be handled when the variables ยท
in the program refer to the same memory location. Having the same memory address makes
the corresponding variables be aliases to each other and any changes made on the value of
one of them will also change the value of the other variable. In other words, although the
variables have their own different names, but this does not guarantee that they are
independent variables as they may refer to the same memory addresses.
Data dependencies that exist in the sequential programs could go undetected due to
the alias names of the variables. Performing a data dependency analysis without the
knowledge of alias information will only lead to the inaccurate result. This thesis
contributes in performing an independent alias analysis on C programs. Using this tool,
the data dependency analyzer could perform an accurate data dependency analysis on the
sequential programs.
First of all this tool, converts the inputted C program into a command list. This list
contains all the statements together with the variables involved in each line of the program.
This list later will be used by the data dependency analyzer for further analysis.
This tool handles both static and dynamic aliases. Upon fmding the alias names
during function calls, the. tool records the alias names in the alias table together with the
calling level. Then the tool performs an in-line expansion on the called function and at the
same time records the statements in the command list. During this conversion the tool
removes the alias names by replacing them with a single main name.
The tool handles the dynamic aliases caused by the recursive data structures by
collecting the paths taken by .the pointer variables in the structure. Dynamic data structures
such as general tree, binary tree and two way link lists are handled by this tool. The tool
records the path taken by each variable along the structures with respect to the root or head
of the structure. To distinguish the structures and the links of a dynamic structure, the tool
communicates with the user with simple clarifying questions. Since these aliases could not
be removed, this part of the tool will work together with the data dependency analyzer.
Description
Keywords
Eliminate aliases , Dependency analysis