Global Value Numbering: A Precise and Efficient Algorithm
| Autor: | Pai, Rekha R |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Global Value Numbering (GVN) is an important static analysis to detect equivalent expressions in a program. We present an iterative data-flow analysis GVN algorithm in SSA for the purpose of detecting total redundancies. The central challenge is defining a join operation to detect equivalences at a join point in polynomial time such that later occurrences of redundant expressions could be detected. For this purpose, we introduce the novel concept of value $\phi$-function. We claim the algorithm is precise and takes only polynomial time. Comment: 6 pages, 3 figures, an extended version to be submitted to journal |
| Databáze: | arXiv |
| Externí odkaz: |
|