首页|Global Value Numbering using Random Interpretation

Global Value Numbering using Random Interpretation

扫码查看
原文链接
  • NETL
We present a polynomial time randomized algorithm for global value numbering。 Our algorithm is complete when conditionals are treated as non-deterministic and all operators are treated as uninter-preted functions。 We are not aware of any complete polynomial-time deterministic algorithm for the same problem。 The algorithm does not require symbolic manipulations and hence is simpler to implement than the deterministic symbolic algorithms。 The price for these benefits is that there is a probability that the algorithm can report a false equality。 We prove that this probability can be made arbitrarily small by controlling various parameters of the algorithm。 Our algorithm is based on the idea of random interpretation， which relies on executing a program on a number of random inputs and discovering relationships from the computed values。 The computations are done by giving random linear interpretations to the operators in the program。 Both branches of a conditional are executed。 At join points， the program states are combined using a random affine combination。 We discuss ways in which this algorithm can be made more precise by using more accurate interpretations for the linear arithmetic operators and other language constructs。

global value numberingherbrand equivalencesrandom interpretationrandomized algorithmuninterpreted functions

Sumit Gulwani、George C. Necula

展开 >

Department of Electrical Engineering and Computer Science University of California, Berkeley Berkeley, CA 94720-1776

The 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2004)

Venice, Italy

The 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2004); Jan 14-16, 2003; Venice, Italy

p.342-352

2003