On the complexity of function pointer may-alias analysis

Robert Muth, Saumya Debray

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

3 Scopus citations


This paper considers the complexity of interprocedural function pointer may-alias analysis, i.e., determining the set of functions that a function pointer (in a language such as C) can point to at a point in a program. This information is necessary, for example, in order to construct the control flow graphs of programs that use function pointers, which in turn is fundamental for most dataflow analyses and optimizations. We show that the general problem is complete for deterministic exponential time. We then consider two natural simplifications to the basic (precise) analysis and examine their complexity. The approach described can be used to readily obtain similar complexity results for related analyses such as reachability and recursiveness.

Original languageEnglish (US)
Title of host publicationTAPSOFT 1997
Subtitle of host publicationTheory and Practice of Software Development - 7th International Joint Conference CAAP/FASE, Proceedings
EditorsMichel Bidoit, Michel Bidoit, Max Dauchet, Max Dauchet
Number of pages12
ISBN (Print)9783540627814, 9783540627814
StatePublished - 1997
Event7th International Joint Conference on Theory and Practice of Software Development, TAPSOFT 1997 - Lille, France
Duration: Apr 14 1997Apr 18 1997

Publication series

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


Other7th International Joint Conference on Theory and Practice of Software Development, TAPSOFT 1997

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the complexity of function pointer may-alias analysis'. Together they form a unique fingerprint.

Cite this