ROSE 編譯器框架/指標分析

別名關係

訪問路徑：由變數、指標解引用運算子和結構體欄位選擇運算子構成的表示式的左值。

對於 C："*" 解引用，"." 欄位選擇，"->" 解引用和欄位選擇

當存在多個訪問路徑指向同一個儲存位置時，就會發生別名現象。訪問路徑是由變數、指標間接定址運算子和結構體欄位選擇運算子構成的表示式的左值。例如，在 C 語言中包括 “*” 解引用運算子、“.”、“->” 運算子等。考慮以下語句

 p = &r;

在這個語句之後，*p 和 r 指向同一個儲存位置，因此它們成為彼此的別名，可以表示為關係 <*p, r>。

有兩個訪問路徑

在語句 S 中必須是別名，如果它們在 S 的所有執行例項中都指向同一個儲存位置。
在 S 中可能是別名，如果它們在 S 的某些執行例項中指向同一個儲存位置。

對於所有訪問路徑 x，平凡的別名 <x, x> 都成立，前提是 x 不會導致對空指標的解引用。

語義：x 自身是自身別名
如果 x 和 y 是非空指標，則 <x,y> 意味著 <*x, *y>

緊湊表示

每個別名關係都使用緊湊表示

演算法

當前實現實現了 Michael Hind、Michael Burke、Paul Carini 和 Jong-Deok Choi。1999. 跨過程指標別名分析。ACM 程式語言系統彙刊。21，4（1999 年 7 月），848-894。連結。

特性

過程內分析：總結每個函式的別名資訊
- 流敏感：考慮控制流路徑
跨過程分析：考慮呼叫圖，以在呼叫圖中傳播別名資訊，以確定物件的“型別”
- 上下文不敏感：忽略呼叫棧資訊
複雜度：計算指標別名被認為是一個 NP-Hard 問題；因此，該演算法使用近似方法來計算別名。
使用緊湊表示圖來表示別名資訊。

測試

make check 規則

[/path/build_rose/tests/roseTests/programAnalysisTests/generalDataFlowAnalysisTests]make verify-pointerAliasAnalysis

我們使用一種原始方法來測試正確性。

輸入測試程式碼：我們新增編譯指示來指示預期結果
測試翻譯器：將分析生成的格與編譯指示資訊進行比較。

示例輸入程式碼

// test_ptr2.C
int a;

void foo(int* &x)
{
    int b  = 10;  
    x = &b;
   // x has an alias set {b}
    #pragma rose x:Aliases:{b}{}b:Aliases:{}{}  

}
    
void main()
{   
    int *p;
    a = 20;
    foo(p);
   // p has an alias set {b} due to function call. 
    #pragma rose a:Aliases:{}{}p:Aliases:{b}{}  
}

沒有精確的字串匹配

由於以下原因，不使用精確的字串匹配

The reason I did that is because unlike other analysis whose lattices contain exact information such as constantPropagation 

(Ex: [VarsExprsProductLattice: level=uninitialized
d: ConstantPropagationLattice:[level: constantValue, val = 9]
] ) my analysis contains temporary memory addresses(since it is a per variable lattice) which may be specific only to that run.

For e.g.,: [VarsExprsProductLattice: level=uninitialized
__expression_0x107b80200-SgIntVal: Aliases:{ }{}
__expression_0x107b80268-SgIntVal: Aliases:{ }{}
__expression_0x107b802d0-SgIntVal: Aliases:{ }{}
__expression_0x107b99a00-SgAssignOp: Aliases:{ }{}
__expression_0x107b99a70-SgAssignOp: Aliases:{ }{("p",p,0) ("a",a,-1)}
__expression_0x107b99ae0-SgAssignOp: Aliases:{ }{("p",p,0) ("b",b,-1)}
__expression_0x107b99b50-SgAssignOp: Aliases:{ }{}
__expression_0x107b99bc0-SgAssignOp: Aliases:{ }{("q",q,0) ("p",p,0)}
__expression_0x107bca800-SgAddressOfOp: Aliases:{ }{}
__expression_0x107bca868-SgAddressOfOp: Aliases:{ }{}
__expression_0x107bca8d0-SgAddressOfOp: Aliases:{ }{}
__expression_0x107c20a00-SgCastExp: Aliases:{ }{}
a: Aliases:{ }{}
b: Aliases:{ }{}
c: Aliases:{ }{}
p: Aliases:{ b }{}
q: Aliases:{ b }{}
x: Aliases:{ }{}
]

In order to verify the correctness of this output, all we need to check is the pointer aliases for the pointer variables -->
a: Aliases:{ }{}
b: Aliases:{ }{}
c: Aliases:{ }{}
p: Aliases:{ b }{}
q: Aliases:{ b }{}
x: Aliases:{ }{}

Since this is only the substring of the complete lattice, I used substr find rather than the exact string match.

I hope this clarifies your question. I will put a note in the code too.

Thanks
Akshatha

待辦事項

列表

移動到 rose/src。
為每個新表示式建立臨時變數可能沒有必要，因為 GDF 支援臨時表示式作為物件。

參考文獻

相關論文列表

David Bacon 和 Peter Sweeney，“C++ 虛擬函式呼叫的快速靜態分析”，OOPSLA'96
Michael Burke、Paul Carini、Jong-Deok Choi 和 Michael Hind，“跨過程指標別名分析”，TOPLAS ‘99
Paul Carini Harini Srinivasan，“C++ 的流敏感跨過程型別分析”，TechReport ‘95
David J. Pearce、Paul H.J. Kelly、Chris Hankin，“C 的高效欄位敏感指標分析”，ACM 程式語言和系統彙刊 (TOPLAS)，第 30 卷第 1 期，第 4-es 頁，2007 年 11 月