如何在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 
}

我錯過了什麼？

來源

2016-02-28 JackWM

你用-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導致緊隨其後。

來源

2016-03-01 07:15:13

如何在LLVM中演示冗餘刪除？

回答

相關問題