A polynomial-time algorithm for global value numbering

详细信息    查看全文

• 关键词：Global value numbering ; Uninterpreted functions ; Abstract interpretation ; Herbrand equivalences
• 刊名：Science of Computer Programming
• 出版年：2007
• 出版时间：1 January 2007
• 年：2007
• 卷：64
• 期：1
• 页码：97-114
• 全文大小：952 K

文摘

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 73481a34472d71be615f03f39e7e5aa7"" title=""Click to view the MathML source"">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.