Andrea Flexeder, Markus Müller-Olm, Michael Petter and Helmut Seidl. Fast Interprocedural Linear Two-Variable Equalities. ACM Trans. Program. Lang. Syst., 33(6), 2011.

In this paper we provide an interprocedural analysis of linear two-variable equalities. In contrast to the corresponding approach based on full linear algebra, the novel algorithm saves a factor of $k^4$ in the worst-case complexity ( ${\cal O}(n \cdot k^4)$ ), where $k$ is the number of variables and $n$ is the program size. We also indicate how the practical runtime can be further reduced significantly. The analysis can be applied, e.g., for register coalescing, for identifying local variables and thus for interprocedurally observing stack pointer modifications as well as for an analysis of array index expressions --- when analysing low-level code.

Download: PDF Reference: Bibtex Electronic Copy: DOI