• Inter-procedural Analysis
• function pointer
  • conservative
    • 22.pdf
  • Context-Sensitivity
    • interprocedural.pdf-1.5 Context Sensitive Analysis,
• Summary-Based Context-Sensitive Analysis
  • Datalog and Pointer Analysis

12/22_W14#11

Inter-procedural Analysis

• conservatively: 有結論才可以說能分析出某結論，若有任一不確定的因素存在於裏頭，就不能直接跳到該結論。
  因通常被分析的結論，會根據該結論做一些更積極，更普遍(pervasive) 的 orgnization 的程式最佳化。
• ex. for(int i = j+1; i < j ; i++) 此 code 不可能成立，這行 code 就可以不用 translate。
• alter the state of all the variables 此分析是在分析變數的狀態有幾種
• 在分析 variable states 時有個重點是 side effect(當一變數被改變就稱為 side effect。)
  side effect 某變數在 memory 的狀態被改變。

function pointer

conservative

• 所有可能性都考慮進去
  

• C1 為何是 fun1?
• 從 main 開始看，進入 fun2 後 pf(glbal variable) 變成指向 fun1，此後就都沒有改變，所以 c1 仍呼叫 fun1。

22.pdf

Context-Sensitivity

interprocedural.pdf-1.5 Context Sensitive Analysis,

• 用這個會比較精確，比較 powerful，但相對複雜多。
• 但 context-free 較簡便，可以用 parsing 的方式，適合程式設計的初手。
• 所以大多數能使用 context-free analysis 的 code 就用 context-free 解決；少數無法用 context-free 的例外，再將此例外用 context-sensitive 的方法解決

Context-Sensitivity

• 更複雜、更精確、更 powerful 分析。
• context-free 的分析較容易在 compiler 上實作(相對於context-sensitive較標準化)雖然會無法分析某些 code，所以需要在某些重要的點加入 context-sensitive 的分析
• 把 function code 當作 goto 來處理
• control-flow graph 會增加多個 additional edges

• 複製一份就叫做 clone
• 此範例複製了三次，一次呼叫一個 clone　… 看影片。
• 請問此範例可以普遍用到其他的例子？複製 4, 5, 6 次也可以嗎？

Summary-Based Context-Sensitive Analysis

• 根據 procedure 語意歸納出 summary(concise description )
• 有 summary 過後就不用重複分析，從 summary 分析即可
• 是接近完整 context-sensitive 的分析方法
• ex. 兩個 function 的名字都

Datalog and Pointer Analysis

• C 用 arbitrary computation 有能力分析 C 支援 '+', '-', 移動
• Pointer-alias 是指兩個 pointer 指向同個記憶體位置(location)，則彼此互為對方 alias
• Java 整理成 reference ，而 java 的 pointer 為 reference，不支援加減乘除的運算。(no arithmetic computation)也就是說，java 的 reference 不能用 '+' '-' 把 reference 往前或往後移動某 reference 指向的記憶體位置，但可以直接指到一個新的 memory address 或 object 的頭的位置。
• pointer-alias 必須做到 inter-procedural 才有最佳化的意義。否則，也必須假設他是在 conservative(保證每個情形都有正確解) 的情況下執行。

• 課本用假設把問題簡化

1. 宣告變數型態有 pointer to T 或 reference to T 兩種型態，在此處 T 為 type
2. object 的使用都是用 heap 的 memory(似java)，在 new 的時候，會將 memory 在 heap 中騰出一塊記憶體，讓 pointer 拿到指標或 reference 拿到參考的位置。
3. object 本身是一個 compound，為一完整的 data structure|class，非 int|char 的 variables，故每個 object 會裏頭有更細部且不同的 field(欄位)，而每個欄位也可以是 pointer 或 reference，讓 object 再繼續指向|參考其他 memory location。

• logical programming 的方式表達 Pointer Analysis

x = y.m(z)

• x 是一個 pointer | reference
• y pointer
• m 是 y 裡頭的一個 function
• 呼叫 m function 時，將 z 傳入當作該 function 的參數。

1. 決定此 method Invocation 的型態(type)
2. 看 method 的 formal parameter 傳遞的個數和方式有無指定。
3. return object 是甚麼型態

• 而分析則用 datalog 的方式
• 很像資料庫的分析
• p 代表 predicate(function block)
  • terms : 是 predicate 用到的參數，terms 可以是 variables 或 constant 來表達其關係
• predicate 只有 constants 的話(沒有任何參數)，就稱為 ground atom。

• 用 logical inferences 的方式表達 datalog 關係式的規則(datalog rules)
• 列舉出來是用 true fact，除非有標記 not 在前方，否則表達出的情形就是符合條件的情形，得到 true 時就是 subgoal
• subgoal: 每個項目(B1, B2,… Bn)
• head: 最前面的項目(term)
• 判斷 H 是否成立要看右邊的 B1~Bn 是否成立。
• First Order Logic 用的符號 ":-" = if 的概念

• 可以把複雜的 Flow-insensitive Pointer Analysis 簡化成這幾行

1. 宣告一變數 V，再 H 的位置宣告成 type T，就會有一個 pointer V 在 H 的位置。
2. V 得到的 pointer| reference 的位置從 W 來，W 在 Heap 裏頭的位置可以使用 2)的方法分析
3. 欄位:
   • V 本身有一個欄位為 F，把 W 的位置給 F 欄位
   • 得 W 在 heap 裏頭的位置為 G
   • 得 V 在 heap 裏頭的位置為 H
4. pts(V,H) 讀 pointer V H
   • V <看課本!-影片 2022/12/15(w14)-3（11:05）>