ISU Electrical and Computer Engineering Archives

Context-Sensitive Control Flow Graph

Ng, Jim-Carl (2004) Context-Sensitive Control Flow Graph. Masters thesis, Iowa State University.

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

Control Flow Graph (CFG) is known to be essential in compiler optimizations, and quite useful in program comprehension. But visualizing and understanding CFG is hard because the CFG is often too large. The problem becomes harder if one were to understand inter-procedural CFG. Often the user wants to understand specific aspects of the CFG. Hence omitting parts of CFG irrelevant to the user's current interest becomes a desirable approach in working with CFG. We formalize an approach of constructing and visualizing CFG that takes users' interest into account. Users have to specify the program artifacts that are of interest to them, then we define the Context-Sensitive CFG that is relevant to the artifacts. The Context-Sensitive CFG is much smaller in size. The actual compression depends on the context and its spread in the given code. We show some results using the XINU operating system code as the test case. While the Context-Sensitive CFG captures only the relevant details, it could still be of substantial size and complexity. We propose query capability as a next step to help the user by extracting details related to a specific question. For example, the user can apply a query to check if there is an execution path in the CFG along which there is a missing memory deallocation and thus a possible memory leak. This thesis only implements queries that operate only within the scope of a method (intra-procedural). We have built a proof-of-concept tool that allows the user to visualize Context-Sensitive CFG and make queries.

EPrint Type:Thesis (Masters)
Uncontrolled Keywords:Visualizing Control Flow Analysis
Subjects:Computer Engineering > SOFTWARE SYSTEMS > Software Engineering
ID Code:110
Identification Number:TR-2004-11-6
Deposited By:Mr. Jim-Carl Ng
Deposited On:18 November 2004

Archive Staff Only: edit this record