2013-10-17 23 views
2

比方說,我開始與功能,foo(),這是正確的,但風格不佳:證明兩個代碼塊在功能上是相同的?

int foo(void) 
{ 
    // Some comment 
    int b; 
    int a; 

    getAandB(&a, &b); 

    return a+b; 
} 

我要重新格式化該代碼塊不做任何功能上的改變:

int foo(void) 
{ 
    // A more descriptive comment 
    int a, b; 

    getAandB(&a, &b); 

    return a + b; 
} 

是否有工具我可以用來證明這兩個塊在功能上是等同的?讓我們假設重新構建整個代碼庫不是一個選項,我想單獨測試這個代碼塊。我將無法鏈接它,因爲getAandB()是在其他地方定義的。

在這種情況下是否可以使用某些工具組合來證明功能對等?

+11

檢查它是否符合相同的asm? – user2802841

+2

@ user2802841這確實是一個選項。我們必須牢記,它很容易產生假陰性。 – Angew

+2

爲了真正證明這些變體是功能上相同的(即做同樣的事情),使用迴歸測試。 –

回答

5

你必須有點PROBL的他們在這裏。假設getAandB這樣定義:

void getAandB(int *a, int *b) { 
    if std::less<int*>()(a, b) { 
     *a = 1; 
     *b = 2; 
    } else { 
     *a = 2; 
     *b = 3; 
    } 
} 

然後改變你發揮功能foo很可能會令到活動的差異(因爲改變變量聲明的順序可以切換他們堆棧上的位置)。

現在公認的行爲,它的變化是不確定的,而且很有可能有很多,你可以作出foo會改變局部變量是如何在棧上的佈局,從而改變這種情況下的行爲無傷大雅的變化特有的getAandB。但是你可能用來測試等價性的任何工具都不知道你是否在意這種可能性(儘管可以用getAandB的定義來排除它)。

您可以使用允許未指定行爲更改的「等效」定義 - 例如「as-if」規則。在優化器中,根據「as-if」規則瞭解代碼是否等價,但通常它們通過應用一系列已知正確的轉換來工作,而不是通過獲取兩位代碼並對其進行測試。

+0

比較指向同一數組(或數組末尾)的指針會調用未定義的行爲。 –

+1

@Anonymous:如果使用'std :: less ()'來比較它們,則不會。 –

+0

哦!有趣! (和upvoted) –

1

測試類的好工具是單元測試,像boost::testcppunit。測試相同的類是否以相同的方式通過測試,然後它們在功能上是等同的。顯然,你必須選擇適當的測試。

1

我想通過比較翻譯你的2個函數後編譯器產生的AST得到的最好結果。可能最簡單的方法是使用clang,因爲它可以輕鬆訪問AST並根據它製作工具。

+0

就像生成的asm的比較一樣,這可能會導致很多錯誤的否定:在這個例子中,我想這個clang會顯示當地人'a'和'b'是以相反的順序聲明的。 – Virgile

+4

@ Virgile:*所有*解決方案要麼產生假陰性,要麼有時不能停止。否則,我可以通過編寫兩個簡單函數並測試它們的等價性來確定哥德巴赫猜想的真實性或虛假性;-)在這種情況下,困難在於確定AST上的哪些轉換在功能上等同並且與「重新格式化「過程。 –

0

如果您想要檢查生成的裝配方法,請按照以下步驟操作。

我假設你的兩個功能被放入兩個文件,a.cb.c

$ gcc -O0 -S a.c 
$ gcc -O0 -S b.c 
$ diff a.s b.s 
1c1 
< .file "a.c" 
--- 
> .file "b.c" 
13,14c13,14 
< leaq -4(%rbp), %rsi 
< leaq -8(%rbp), %rdi 
--- 
> leaq -8(%rbp), %rsi 
> leaq -4(%rbp), %rdi 
17,18c17,18 
< movl -8(%rbp), %edx 
< movl -4(%rbp), %eax 
--- 
> movl -4(%rbp), %edx 
> movl -8(%rbp), %eax 
$ 

我們把任何優化(-O0),以防止任何優化文物。

所以有點令人驚訝的gcc(4.1.2)的輸出是略有不同的這兩個功能。但仔細看看這一點,我們可以看到爲什麼 - 在第一個函數中,b的聲明在a之前,因此b在堆棧上的a以上,但在第二個函數中,它是相反的。

所以,如果我換ab我現在看到生成的組件實際上是相同的:

$ gcc -O0 -S b1.c 
$ diff a.s b1.s 
1c1 
< .file "a.c" 
--- 
> .file "b1.c" 
$ 

另外,如果你只關心生成的程序集是否是不同的,而不是什麼生成的程序集實際上是,那麼你就可以做到這一切在一個花式schmancy bash命令:

$ diff --brief <(cat a.c | gcc -O0 -S -xc - -o-) <(cat b.c | gcc -O0 -S -xc - -o-) 
Files /dev/fd/63 and /dev/fd/62 differ 
$ echo $? 
1 
$ diff --brief <(cat a.c | gcc -O0 -S -xc - -o-) <(cat b1.c | gcc -O0 -S -xc - -o-) 
$ echo $? 
0 
$ 
+0

如果您對差異不感興趣,您可以使用'cmp'而不是'diff'。 – Virgile