如何在LLVM中演示冗余删除？

问题描述：

我发现-gvn（全局值编号）从选择。我测试了下面的例子：

int foo(int a, int b) { 
    int c, d, e, f, g; 

    c = a + b; 
    d = a + b; 
    e = a; 
    f = e + b; 
    g = c + d + e + f; 

    return f; 
}

与这些过程：

clang -S -emit-llvm eg.c 
llvm-as eg.ll 
opt -gvn eg.ll -o eg_opt.ll

然而，我观察到的相同数目的添加操作如前。

eg.ll

define i32 @foo(i32 %a, i32 %b) #0 { 
entry: 
    %a.addr = alloca i32, align 4 
    %b.addr = alloca i32, align 4 
    %c = alloca i32, align 4 
    %d = alloca i32, align 4 
    %e = alloca i32, align 4 
    %f = alloca i32, align 4 
    %g = alloca i32, align 4 
    store i32 %a, i32* %a.addr, align 4 
    store i32 %b, i32* %b.addr, align 4 
    %0 = load i32, i32* %a.addr, align 4 
    %1 = load i32, i32* %b.addr, align 4 
    %add = add nsw i32 %0, %1 
    store i32 %add, i32* %c, align 4 
    %2 = load i32, i32* %a.addr, align 4 
    %3 = load i32, i32* %b.addr, align 4 
    %add1 = add nsw i32 %2, %3 
    store i32 %add1, i32* %d, align 4 
    %4 = load i32, i32* %a.addr, align 4 
    store i32 %4, i32* %e, align 4 
    %5 = load i32, i32* %e, align 4 
    %6 = load i32, i32* %b.addr, align 4 
    %add2 = add nsw i32 %5, %6 
    store i32 %add2, i32* %f, align 4 
    %7 = load i32, i32* %c, align 4 
    %8 = load i32, i32* %d, align 4 
    %add3 = add nsw i32 %7, %8 
    %9 = load i32, i32* %e, align 4 
    %add4 = add nsw i32 %add3, %9 
    %10 = load i32, i32* %f, align 4 
    %add5 = add nsw i32 %add4, %10 
    store i32 %add5, i32* %g, align 4 
    %11 = load i32, i32* %f, align 4 
    ret i32 %11 
}

eg_opt.ll

define i32 @foo(i32 %a, i32 %b) #0 { 
entry: 
    %a.addr = alloca i32, align 4 
    %b.addr = alloca i32, align 4 
    %c = alloca i32, align 4 
    %d = alloca i32, align 4 
    %e = alloca i32, align 4 
    %f = alloca i32, align 4 
    %g = alloca i32, align 4 
    store i32 %a, i32* %a.addr, align 4 
    store i32 %b, i32* %b.addr, align 4 
    %0 = load i32, i32* %a.addr, align 4 
    %add = add nsw i32 %0, %b 
    store i32 %add, i32* %c, align 4 
    %1 = load i32, i32* %a.addr, align 4 
    %2 = load i32, i32* %b.addr, align 4 
    %add1 = add nsw i32 %1, %2 
    store i32 %add1, i32* %d, align 4 
    %3 = load i32, i32* %a.addr, align 4 
    store i32 %3, i32* %e, align 4 
    %4 = load i32, i32* %b.addr, align 4 
    %add2 = add nsw i32 %3, %4 
    store i32 %add2, i32* %f, align 4 
    %5 = load i32, i32* %c, align 4 
    %6 = load i32, i32* %d, align 4 
    %add3 = add nsw i32 %5, %6 
    %7 = load i32, i32* %e, align 4 
    %add4 = add nsw i32 %add3, %7 
    %add5 = add nsw i32 %add4, %add2 
    store i32 %add5, i32* %g, align 4 
    %8 = load i32, i32* %f, align 4 
    ret i32 %8 
}

我错过了什么？

你用-basicaa试过了吗？没有别名分析，它不会触及那些加载存储。 –

或者，更好的是，使用mem2reg来获得SSA。它不仅更可能被优化，而且更容易遵循。 – delnan

答

我认为-instcombine通是你正在寻找。使用-instcombine优化您的代码会得到以下IR。

define i32 @foo(i32 %a, i32 %b) #0 { 
    %1 = add nsw i32 %a, %b 
    ret i32 %1 
}

Instcombine尝试从IR中删除尽可能多的冗余指令。

编辑： 但是，如果你想使用gvn，你必须首先把你的IR带到一个“更好”的SSA表单。

使用-mem2reg带给您的IR成完美的SSA形式：

define i32 @foo(i32 %a, i32 %b) #0 { 
    %1 = add nsw i32 %a, %b 
    %2 = add nsw i32 %a, %b 
    %3 = add nsw i32 %a, %b 
    %4 = add nsw i32 %1, %2 
    %5 = add nsw i32 %4, %a 
    %6 = add nsw i32 %5, %3 
    ret i32 %3 
    }

现在使用-gvn减少冗余的附加说明：

define i32 @foo(i32 %a, i32 %b) #0 { 
    %1 = add nsw i32 %a, %b 
    %2 = add nsw i32 %1, %1 
    %3 = add nsw i32 %2, %a 
    %4 = add nsw i32 %3, %1 
    ret i32 %1 
}

EDIT2：

从lazyCoder的评论：支持-gvn有别名分析也会导致重做丹西去除：

首先使用-basicaa结果如下IR：

define i32 @foo(i32 %a, i32 %b) #0 {          
    %1 = alloca i32, align 4               
    %2 = alloca i32, align 4              
    %c = alloca i32, align 4 
    %d = alloca i32, align 4 
    %e = alloca i32, align 4 
    %f = alloca i32, align 4 
    %g = alloca i32, align 4 
    store i32 %a, i32* %1, align 4 
    store i32 %b, i32* %2, align 4 
    %3 = add nsw i32 %a, %b 
    store i32 %3, i32* %c, align 4 
    store i32 %3, i32* %d, align 4 
    store i32 %a, i32* %e, align 4 
    store i32 %3, i32* %f, align 4 
    %4 = add nsw i32 %3, %3 
    %5 = add nsw i32 %4, %a 
    %6 = add nsw i32 %5, %3 
    store i32 %6, i32* %g, align 4 
    ret i32 %3 
}

如果负载和存储都被保留：

define i32 @foo(i32 %a, i32 %b) #0 { 
    %1 = alloca i32, align 4 
    %2 = alloca i32, align 4 
    %c = alloca i32, align 4 
    %d = alloca i32, align 4 
    %e = alloca i32, align 4 
    %f = alloca i32, align 4 
    %g = alloca i32, align 4 
    store i32 %a, i32* %1, align 4 
    store i32 %b, i32* %2, align 4 
    %3 = load i32, i32* %1, align 4 
    %4 = load i32, i32* %2, align 4 
    %5 = add nsw i32 %3, %4 
    store i32 %5, i32* %c, align 4 
    %6 = load i32, i32* %1, align 4 
    %7 = load i32, i32* %2, align 4 
    %8 = add nsw i32 %6, %7 
    store i32 %8, i32* %d, align 4 
    %9 = load i32, i32* %1, align 4 
    store i32 %9, i32* %e, align 4 
    %10 = load i32, i32* %e, align 4 
    %11 = load i32, i32* %2, align 4 
    %12 = add nsw i32 %10, %11 
    store i32 %12, i32* %f, align 4 
    %13 = load i32, i32* %c, align 4 
    %14 = load i32, i32* %d, align 4 
    %15 = add nsw i32 %13, %14 
    %16 = load i32, i32* %e, align 4 
    %17 = add nsw i32 %15, %16 
    %18 = load i32, i32* %f, align 4 
    %19 = add nsw i32 %17, %18 
    store i32 %19, i32* %g, align 4 
    %20 = load i32, i32* %f, align 4 
    ret i32 %20 
}

通过-gvn导致紧随其后。

如何在LLVM中演示冗余删除？

相关推荐