IISc Logo    Title

etd AT Indian Institute of Science >
Division of Electrical Sciences >
Computer Science and Automation (csa) >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2005/2564

Title: Access Path Based Dataflow Analysis For Sequential And Concurrent Programs
Authors: Arnab De, *
Advisors: D'souza, Deepak
Keywords: Dataflow Analysis
Java (Computer Program Language)
Concurrent Programs - Syntax and Semantics
Concurrent Programs - Dataflow Analysis
Flow-Sensitive Pointer Analysis
Null-Pointer Analysis
Sequential Programs - Syntax and Semantics
Flow-Sensitive Dataflow Analysis
Concurrent Java Programs
Sequential Programs - Dataflow Analysis
Acess Path Based Dataflow Analysis
Relaxed Memory Model
Java Memory Model
Submitted Date: Dec-2012
Series/Report no.: G25774
Abstract: In this thesis, we have developed a flow-sensitive data flow analysis framework for value set analyses for Java-like languages. Our analysis frame work is based on access paths—a variable followed by zero or more field accesses. We express our abstract states as maps from bounded access paths to abstract value sets. Using access paths instead of allocation sites enables us to perform strong updates on assignments to dynamically allocated memory locations. We also describe several optimizations to reduce the number of access paths that need to be tracked in our analysis. We have instantiated this frame work for flow-sensitive pointer and null-pointer analysis for Java. We have implemented our analysis inside the Chord frame work. A major part of our implementation is written declaratively using Datalog. We leverage the use of BDDs in Chord for keeping our memory usage low. We show that our analysis is much more precise and faster than traditional flow-sensitive and flow-insensitive pointer and null-pointer analysis for Java. We further extend our access path based analysis frame work to concurrent Java programs. We use the synchronization structure of the programs to transfer abstract states from one thread to another. Therefore, we do not need to make conservative assumptions about reads or writes to shared memory. We prove our analysis to be sound for the happens-before memory model, which is weaker than most common memory models, including sequential consistency and the Java Memory Model. We implement a null-pointer analysis for concurrent Java programs and show it to be more precise than the traditional analysis.
Abstract file URL: http://etd.ncsi.iisc.ernet.in/abstracts/3331/G25774-Abs.pdf
URI: http://etd.iisc.ernet.in/handle/2005/2564
Appears in Collections:Computer Science and Automation (csa)

Files in This Item:

File Description SizeFormat
G25774.pdf1.27 MBAdobe PDFView/Open

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.


etd@IISc is a joint service of SERC & IISc Library ||
|| Powered by DSpace || Compliant to OAI-PMH V 2.0 and ETD-MS V 1.01