Developing a software tool to identify and eliminate aliases inc programs for data dependency analysis

Loading...
Thumbnail Image
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
Citation