Heap Reference Analysis

XSB Based Prototype Implementation of Heap Reference Analysis

Amey Karkare,
(karkare [AT] cse.iitb.ac.in)
Indian Institute of Technology, Bombay

This directory contains the prototype implementation of heap reference analysis (HRA) which has been defined in

Uday Khedker, Amitabha Sanyal, Amey Karkare. Heap Reference Analysis Using Access Graphs, Department of Computer Science & Engg., IIT Bombay. 2005 (In Preparation). (Abstract)

The resources here have been provided in good faith without any warranty, explicit or implied, towards anything. All copyrights are held by IIT Bombay. For more details, please contact Uday Khedker.

Dependencies

To run the implementation, you will need to install XSB from here.
To view the liveness and alias information as Postscript files, you will need to install Graphviz.

Download

You can download HRA implementation files as a tar-zipped archive from here.

Installation

unzip-untar downloaded hra_code.tgz. This will create a directory named Prolog, with various files required to run the analysis.

Running

Details about running XSB can be found in XSB Manual. After running XSB, at the prompt ( ?- ), you will need to load the file run.P. It will automatically take care of loading rest of the files. Typical session with XSB is as follows :

$ xsb [xsb_configuration loaded] [sysinitrc loaded] XSB Version 2.7.1 (Kinryo) of March 5, 2005 [i686-pc-linux-gnu; mode: optimal; engine: slg-wam; gc: indirection; scheduling: local] | ?- [run]. [run loaded] [ag_test loaded] [utils loaded] [prog loaded] [ag loaded] [alias loaded] [live loaded] [av loaded] [ant loaded] [null loaded] [test loaded] [bm loaded] ... <snip> ... | ?- test(1). ... <snip> ... Time Taken = 0.1900 | ?- halt. End XSB (cputime 0.04 secs, elapsetime 69.99 secs)

Contents of the Implementation Directory

README.html: This File :).
utils.P: utilities for set, list, printing the data structures in dot (graphviz) format etc.
ag.P: Access Graph structure and operations.
ag_test.P: Some tests to exercise ag.P routines.
alias.P: Code to do the alias analysis.
live.P: Code to do the liveness analysis. Does both Explicit and Implicit liveness analysis, along with addition of potentially nullable nodes.
av.P: Code to do the availability analysis.
ant.P: Code to do the anticipability analysis.
null.P: Code for null-assignment insertion.
prog.P: representation of the program as used by the prototype. Also defines accessor functions for program components.
run.P: toplevel file to load all ther files.
test.P: few testcases, and related routines.
bm.P: Prolog code for benchmarks.
java/: directory containing the java code of benchmarks.
- original/: contains the original java code for benchmarks.
- modified/: contains the modified java code (i.e., with null insertions) for benchmarks.

Output files containing data flow values are generated in the directory output/. Following files are generated:

cfg.ps contains the cfg of the program (to make sure the program is correctly encoded in XSB-Prolog).

alias_in.ps and alias_out.ps contain alias analysis information. live_in.ps and live_out.ps contain complete (explicit and implicit) liveness information. anticip_out.txt and anticip_in.txt contain anticipability information. avail_in.txt and avail_out.txt contain availability information.

Last Updated by $author: karkare$ on $Date: Tue Sep 13 09:00:18 IST 2005$.