算法
编译器
LLVM

LVN和SVN算法在LLVM中的实现？

LVN和SVN算法在LLVM是怎么实现的呢？具体文件是哪个呢？看了算法描述实在是太抽象了，我想看看具体的实现流程。
关注者
68
被浏览
8,838
登录后你可以
不限量看优质回答私信答主深度交流精彩内容一键收藏
查看全部 3 个回答

VN就是Value Numbering. 给一个BB内部的操作进行编号，可以很好的消除common expression以及支持常量折叠等。

先说下算法的大概流程：

Data structure:
VALUES = Table of
    expression /* [OP, valnum1, valnum2] */
    var /* name of variable currently holding expr */

For each instruction (dst = src1 OP src2) in execution order
    valnum1=var2value(src1); valnum2=var2value(src2)
    IF [OP, valnum1, valnum2] is in VALUES
        v = the index of expression
        Replace instruction with: dst = VALUES[v].var
    ELSE
        Add 
            expression = [OP, valnum1, valnum2]
            var = tv
        to VALUES
        v = index of new entry; tv is new temporary for v
        Replace instruction with: tv = VALUES[valnum1].var OP VALUES[valnum2].var
        dst = tv
     set_var2value (dst, v)

其中var2value是获得操作数的value number，可以用Map或者HashTable实现。其中每个变量的value number初始化为按照变量的出现顺序动态编号。

举个实际的例子：

a = b+c  //t4 = b + c;   tv = VALUES[valnum1].var OP VALUES[valnum2].var; 
         //a = t4;       dst = tv
b = a-d  //t5 = t4 - d;  
         //b = t5;
c = b+c  //t6 = t5 + c;
         //c = t6
d = a-d  //t5 = d;       dst = VALUES[v].var

因此，对于上面例子，画出VN图如下：

可见在这个图里面是不存在common expression的。


参考： cs.cmu.edu/~15745/lectu

查看全部 3 个回答