目錄：
- Motivation
- 指針分析介紹
- 影響指針分析的關(guān)鍵要素
- 分析哪些語句
重點(diǎn)：
什么是指針分析笋妥？影響指針分析的關(guān)鍵因素是什么硕噩？指針分析要分析哪些指令糊识？
1.Motivation
指針分析必要性：
2.指針分析
目標(biāo)：分析程序指針可以指向哪些內(nèi)存彩倚。對(duì)于Java等面向?qū)ο笳Z言姥卢，主要分析指針指向哪個(gè)對(duì)象卷要。
說明：指針分析屬于may analysis，分析的結(jié)果是某指針?biāo)锌赡苤赶蚰男?duì)象独榴，是個(gè)over-approximation集合却妨。
示例：面向?qū)ο笳Z言中的指針指向問題。對(duì)于setB()函數(shù)括眠，this指向new A()彪标，因?yàn)槭钦{(diào)用者是a.setB()；setB()中的b是x傳過來的掷豺，所以b指向new B()捞烟，A.b指向 new B()。
區(qū)別：
- 指針分析：分析指針?biāo)锌赡苤赶虻膶?duì)象当船。
- 別名分析：分析兩個(gè)指針是否指向相同的對(duì)象题画，可通過指針分析來推導(dǎo)得到。
應(yīng)用：基本信息（別名分析/調(diào)用圖）德频，編譯優(yōu)化（嵌入虛擬調(diào)用）苍息，漏洞（空指針），安全分析（信息流）壹置。
3.影響指針分析的關(guān)鍵要素
指標(biāo)：精度（precision）& 效率（efficiency）竞思。
影響因素：本課程，我們主要分析分配點(diǎn)的堆抽象技術(shù)钞护、上下文敏感/不敏感盖喷、流不敏感、全程序分析难咕。
| 因素 | 問題 | 選項(xiàng) |
|---|---|---|
| Heap abstraction | 如何建模堆內(nèi)存课梳？ | ? Allocation-site ? Storeless |
| Context sensitivity | 如何建模調(diào)用上下文？ | ? Context-sensitive ? Context-insensitive |
| Flow sensitivity | 如何建挠嗟瑁控制流暮刃？ | ? Flow-sensitive ? Flow-insensitive |
| Analysis scope | 分析哪部分程序？ | ? Whole-program ? Demand-driven |
（1）堆抽象（內(nèi)存建模）
問題：程序動(dòng)態(tài)執(zhí)行時(shí)爆土，堆對(duì)象個(gè)數(shù)理論上是無窮無盡的椭懊，但靜態(tài)分析無法處理這個(gè)問題。所以為保證指針分析可以終止雾消，我們采用堆抽象技術(shù)灾搏，將無窮的具體對(duì)象抽象成有限的抽象對(duì)象挫望。也即，將有共性的對(duì)象抽象成1個(gè)靜態(tài)對(duì)象狂窑，從而限制靜態(tài)分析對(duì)象的個(gè)數(shù)媳板。
// 示例
for (...) {
A a = new A();
}
技術(shù)概覽：
我們只學(xué)習(xí)Allocation-Site技術(shù)，最常見也最常被使用泉哈。
Allocation-Site原理：將動(dòng)態(tài)對(duì)象抽象成它們的創(chuàng)建點(diǎn)（Allocation-Site）蛉幸，來表示在該點(diǎn)創(chuàng)建的所有動(dòng)態(tài)對(duì)象。Allocation-Site個(gè)數(shù)是有限的丛晦。
示例：循環(huán)創(chuàng)建了3個(gè)對(duì)象奕纫，我們用O2來抽象表示這3個(gè)動(dòng)態(tài)對(duì)象。
（2）上下文敏感 Context Sensitivity
問題：考慮是否區(qū)分不同call-site對(duì)同一函數(shù)的調(diào)用烫沙。
- Context-sensitive：根據(jù)某函數(shù)調(diào)用上下文的不同匹层，多次分析同一函數(shù)。
-
Context-insensitive：每個(gè)函數(shù)只分析一次锌蓄。
6-3-3-上下文敏感示例.png
（3）流敏感 Flow Sensitivity
問題：考慮語句順序（控制流）的影響 vs 把程序當(dāng)做無序語句的集合升筏。
方法：流敏感會(huì)在每個(gè)程序點(diǎn)都保存一份指針指向關(guān)系映射，而流不敏感則對(duì)整個(gè)程序保存一份指向關(guān)系映射瘸爽。
說明：目前流敏感對(duì)Java提升不大您访，不過在C中很有效，本課程分析的是Java剪决，所以重點(diǎn)討論流不敏感技術(shù)灵汪。
指針分析示例：
（4）分析范圍 Analysis Scope
問題：分析程序的哪一部分？
- Whole-program 全程序：分析全程序的指向關(guān)系柑潦。
- Demand-driven 需求驅(qū)動(dòng)：只分析影響特定域的指針的指向關(guān)系享言。
4.分析哪些語句
問題：哪些語句會(huì)影響指針指向，那就只分析這些語句妒茬。
Java指針類型：
Lacal variable: x
Static field:C.f （有時(shí)稱為全局變量）——不分析
Instance field: x.f （對(duì)象的field）
-
Array element: array[i] ——不分析担锤，因?yàn)殪o態(tài)分析無法確定下標(biāo)蔚晨，所以將array中所有成員映射到一個(gè)field中乍钻，等價(jià)于Instance field，所以不重復(fù)分析铭腕。如下圖所示：
6-4-1-數(shù)組處理.png
影響指針指向的語句：
- New: x = new T()
- Assign：x = y
- Store： x.f = y
- Load： y = x.f
- Call： r = x.k(a,...)
- Static call： C.foo()
- Special call： super.foo() / x.<init>() / this.privateFoo()
- Virtual call：x.foo()
復(fù)雜的內(nèi)存訪問可以通過引入臨時(shí)變量银择，轉(zhuǎn)化為三地址代碼：
x.f.g.h = y;
// 轉(zhuǎn)化為
t1 = x.f;
t2 = t1.g;
t2.h = y;
