Parametric and termination-sensitive control dependence

Feng Chen, Grigore Rosu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A parametric approach to control dependence is presented, where the parameter is any prefix-invariant property on paths in the control-flow graph (CFG). Existing control dependencies, both direct and indirect, can be obtained as instances of the parametric framework for particular properties on paths. A novel control dependence relation, called termination-sensitive control dependence, is obtained also as an instance of the parametric framework. This control dependence is sensitive to the termination information of loops, which can be given via annotations. If all loops are annotated as terminating then it becomes the classic control dependence, while if all loops are annotated as non-terminating then it becomes the weak control dependence; since in practice some loops are terminating and others are not, termination-sensitive control dependence is expected to improve the precision of analysis tools using it. The unifying formal framework for direct and indirect control dependence suggests also, in a natural way, a unifying terminology for the various notions of control dependence, which is also proposed in this paper. Finally, a worst-case O(n2) algorithm to compute the indirect termination-sensitive control dependence for languages that allow only "structured" jumps (i.e., ones that do not jump into the middle of a different block), such as Java and C#, is given, avoiding the O(n3) complexity of the trivial algorithm calculating the transitive closure of the direct dependence.

Original languageEnglish (US)
Title of host publicationStatic Analysis - 13th International Symposium, SAS 2006, Proceedings
PublisherSpringer-Verlag
Pages387-404
Number of pages18
ISBN (Print)3540377565, 9783540377566
StatePublished - Jan 1 2006
Event13th International Symposium on Static Analysis, SAS 2006 - Seoul, Korea, Republic of
Duration: Aug 29 2006Aug 31 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4134 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Symposium on Static Analysis, SAS 2006
CountryKorea, Republic of
CitySeoul
Period8/29/068/31/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Parametric and termination-sensitive control dependence'. Together they form a unique fingerprint.

  • Cite this

    Chen, F., & Rosu, G. (2006). Parametric and termination-sensitive control dependence. In Static Analysis - 13th International Symposium, SAS 2006, Proceedings (pp. 387-404). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4134 LNCS). Springer-Verlag.