




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、1Next Section: Pointer Analysis Outline: What is pointer analysis Intraprocedural pointer analysis Interprocedural pointer analysis (Wilson & Lam) Unification based interprocedural pointer analysis (Steensgaard)2Pointer and Alias Analysis Aliases: two expressions that denote the same memory loca
2、tion. Aliases are introduced by: pointers call-by-reference array indexing C unions3Useful for what? Improve the precision of analyses that require knowing what is modified or referenced (eg const prop, CSE ) Eliminate redundant loads/stores and dead stores. Parallelization of code can recursive cal
3、ls to quick_sort be run in parallel? Yes, provided that they reference distinct regions of the array. Identify objects to be tracked in error detection toolsx := *p;.y := *p; / replace with y := x?*x := .;/ is *x dead?x.lock();.y.unlock(); / same object as x?4Kinds of alias information Points-to inf
4、ormation (must or may versions) at program point, compute a set of pairs of the form p ! x, where p points to x. can represent this informationin a points-to graph Alias pairs at each program point, compute the set of of all pairs (e1,e2) where e1 and e2 must/may reference the same memory. Storage s
5、hape analysis at each program point, compute anabstract description of the pointer structure.pxyzp5Intraprocedural Points-to Analysis Want to compute may-points-to information Lattice:6Flow functionsx := a + binoutFx := a+b(in) =x := kinoutFx := k(in) =7Flow functionsx := &yinoutFx := &y(in)
6、 =x := yinoutFx := y(in) =8Flow functions*x := yinoutF*x := y(in) =x := *yinoutFx := *y(in) =9Intraprocedural Points-to Analysis Flow functions:10Example of using points-to information In constant propagation:11Example of using points-to information In constant propagation:12Pointers to dynamically-
7、allocated memory Handle statements of the form: x := new T One idea: generate a new variable each time the new statement is analyzed to stand for the new location:13Examplelst := new Consp := lstt := new Cons*p := tp := t14Example solvedl := new Consp := lt := new Cons*p := tp := tlpV1lpV1tV2lpV1tV2
8、ltV1pV2ltV1pV2ltV1pV2V3ltV1pV2V3ltV1pV2V315What went wrong? Lattice was infinitely tall! Instead, we need to summarize the infinitely many allocated objects in a finite way. introduce summary nodes, which will stand for a whole class of allocated objects. For example: For each new statement with lab
9、el L, introduce a summary node locL , which stands for the memory allocated by statement L. Summary nodes can use other criterion for merging.16Example revisitedS1: l := new Consp := lS2: t := new Cons*p := tp := t17Example revisited & solvedS1: l := new Consp := lS2: t := new Cons*p := tp := tl
10、pS1lpS1tS2lpS1tS2ltS1pS2ltS1pS2ltS1pL2ltS1pS2ltS1pS2ltS1pS2ltL1pL2ltS1pS2ltS1pS2Iter 1Iter 2Iter 318Array aliasing, and pointers to arrays Array indexing can cause aliasing: ai aliases bj if: a aliases b and i = j a and b overlap, and i = j + k, where k is the amount of overlap. Can have pointers to
11、 elements of an array p := &ai; .; p+; How can arrays be modeled? Could treat the whole array as one location. Could try to reason about the array index expressions: array dependence analysis.19Summary We just saw: intraprocedural points-to analysis handling dynamically allocated memory handling
12、 pointers to arrays But, intraprocedural pointer analysis is not enough. Sharing data structures across multiple procedures is one the big benefits of pointers: instead of passing the whole data structures around, just pass pointers to them (eg C pass by reference). So pointers end up pointing to st
13、ructures shared across procedures. If you dont do an interproc analysis, youll have to make conservative assumptions functions entries and function calls.20Conservative approximation on entry Say we dont have interprocedural pointer analysis. What should the information be at the input of the follow
14、ing procedure:global g;void p(x,y) .xyg21Conservative approximation on entry Here are a few solutions:xyglocationsfrom allocsites priorto thisinvocationglobal g;void p(x,y) . They are all very conservative! We can try to do better.x,y,g & locationsfrom allocsites priorto thisinvocation22Interpro
15、cedural pointer analysis for C Well look at Wilson & Lam PLDI 95, and focus on two problems solved by this paper: how to represent pointer information in the presence of casts, pointer arithmetic, unions, and all the rest of C. how to perform context-sensitive pointer analysis interprocedurally
16、in a way that provides good precision at reasonable costs.23Representing pointer information for C Problem: C types can be subverted by type casts: an int can in fact be a pointer. Pointer arithmetic can lead to subobject boundaries being crossed. So, ignore the type system and subobject boundaries. Instead use a
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 【正版授權(quán)】 ISO 13317-5:2025 EN Determination of particle size distribution by gravitational liquid sedimentation methods - Part 5: Photosedimentation techniques
- 2025年度人工智能產(chǎn)業(yè)擔(dān)保合作協(xié)議書(shū)
- 2025年度餐飲企業(yè)代理記賬與食品安全管理合同
- 2025年度電信設(shè)備采購(gòu)與維護(hù)服務(wù)合同范本
- 2025年度廠房租賃合同履約監(jiān)督管理服務(wù)合同
- 2025年度二手房無(wú)證房產(chǎn)買賣合同風(fēng)險(xiǎn)防范條款
- 2025年度工業(yè)用地場(chǎng)地租賃及設(shè)備安裝合同
- 2025年服裝、鞋帽加工機(jī)械項(xiàng)目合作計(jì)劃書(shū)
- 2025年電能表標(biāo)準(zhǔn)校驗(yàn)裝置項(xiàng)目建議書(shū)
- 幼兒園學(xué)期計(jì)劃五彩斑斕燦爛生活
- 2024年江蘇省衛(wèi)生健康委員會(huì)所屬事業(yè)單位招聘筆試真題
- 教育強(qiáng)國(guó)建設(shè)規(guī)劃綱要(2024-2035年)要點(diǎn)解讀(教育是強(qiáng)國(guó)建設(shè)民族復(fù)興之基)
- 廉潔知識(shí)培訓(xùn)課件
- 2025年電梯專用電機(jī)項(xiàng)目可行性研究報(bào)告
- 煤礦安全生產(chǎn)方針及法律法規(guī)課件
- 建筑行業(yè)新員工試用期考核制度
- 高職院校高水平現(xiàn)代物流管理專業(yè)群建設(shè)方案(現(xiàn)代物流管理專業(yè)群)
- 2024專升本英語(yǔ)答題卡浙江省
- 稿件修改說(shuō)明(模板)
- (完整版)50028-城鎮(zhèn)燃?xì)庠O(shè)計(jì)規(guī)范
- 古詩(shī)田字格模板
評(píng)論
0/150
提交評(píng)論