Name
Abstract | ||
|---|---|---|
In this article we provide an interprocedural analysis of linear two-variable equalities. The novel algorithm has a worst-case complexity of 𝒪(n ⋅ k4), where k is the number of variables and n is the program size. Thus, it saves a factor of k4 in comparison to a related algorithm based on full linear algebra. We also indicate how the practical runtime can be further reduced significantly. The analysis can be applied, for example, 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 analyzing low-level code. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2049706.2049710 | ACM Trans. Program. Lang. Syst. |
Keywords | Field | DocType |
array index expression,practical runtime,pointer modification,interprocedural analysis,local variable,full linear algebra,linear two-variable equality,interprocedural linear two-variable equality,novel algorithm,low-level code,related algorithm,linear algebra,static analysis,indexation | Linear algebra,Array data structure,Expression (mathematics),Computer science,Abstract interpretation,Call stack,Static analysis,Algorithm,Local variable | Journal |
Volume | Issue | ISSN |
33 | 6 | 0164-0925 |
Citations | PageRank | References |
3 | 0.38 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea Flexeder | 1 | 13 | 1.64 |
| Markus Müller-Olm | 2 | 607 | 39.73 |
| Michael Petter | 3 | 13 | 1.64 |
| Helmut Seidl | 4 | 1468 | 103.61 |