Record Details

Access Path Based Dataflow Analysis For Sequential And Concurrent Programs

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Access Path Based Dataflow Analysis For Sequential And Concurrent Programs
 
Creator Arnab De, *
 
Subject 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
Computer Science
 
Description 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.
 
Contributor D'souza, Deepak
 
Date 2016-09-14T06:50:04Z
2016-09-14T06:50:04Z
2016-09-14
2012-12
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/handle/2005/2564
http://etd.ncsi.iisc.ernet.in/abstracts/3331/G25774-Abs.pdf
 
Language en_US
 
Relation G25774