A polynomial-time algorithm for global value numbering
| Autor: | George C. Necula, Sumit Gulwani |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
Global value numbering
Computer science Uninterpreted functions Value (computer science) Abstract interpretation 020207 software engineering 02 engineering and technology Exponential function Set (abstract data type) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Algorithm Time complexity Herbrand equivalences Software |
| Zdroj: | Science of Computer Programming. 64:97-114 |
| ISSN: | 0167-6423 |
| DOI: | 10.1016/j.scico.2006.03.005 |
| Popis: | We describe a polynomial-time algorithm for global value numbering, which is the problem of discovering equivalences among program sub-expressions. We treat all conditionals as non-deterministic and all program operators as uninterpreted. We show that there are programs for which the set of all equivalences contains terms whose value graph representation requires exponential size. Our algorithm discovers all equivalences among terms of size at most s in time that grows linearly with s. For global value numbering, it suffices to choose s to be the size of the program. Earlier deterministic algorithms for the same problem are either incomplete or take exponential time. We provide a detailed analytical comparison of some of these algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect