### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 587 Class Note for CS 50200 with Professor Jagannathan at Purdue

### View Full Document

## 49

## 0

## Popular in Course

## Popular in Department

This 24 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Purdue University taught by a professor in Fall. Since its upload, it has received 49 views.

## Similar to Course at Purdue

## Reviews for 587 Class Note for CS 50200 with Professor Jagannathan at Purdue

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Shape Analysis III Obtain a finite representation of the shape of the program heap at different program points I Consider a language with pointers and references El Utility l Aliasing and sharing El Can be u3ed for more efficient code generation I Inlining constantfolding method dispatch etc El Identify possible nullpointer dereferences El Program verification l reverSe transforms a noncyclic list to a noncyclic list 3 Poin rer Analysis El Goal wha l objects can a pointer poin l lo El S la lically undecidable in general I What are good approxima lions El Can be used To infer aliaSes I if a points To b and b poin ls To c Then El ltabgt ltbcgt gt ltacgt and Thus a and b are aliases El Fundamen lally an in lerprocedural analysis I A poin ler variable can be supplied as arguments or returned as a resul l from a procedure Flowinsensi live vs flowsensi live con leX lsensi livi39ly shape analysis field sensi livi39ly S rr39a regies El Example p malloc q malloc fp ampp fp ampq fp El Flowinsensitive equalitybased heap1 heap2 Equali ry based Analyses III Example xampa yamph pampx pampw add edge collapse x and y collapse a and b Typebased Formula rion III Running example x ampa yamph I0 ampX pampw Assign each variable a Type x r1y r2a r3b r4p r5 E D Cons rr39uc r ini rial cons rr39ain rs l x ampa T1 r39ef r3 l y ampb T2 r39ef r4 l p ampy T5 r39efT1 l p ampy T5 ref2 Typebased formula rioncon r III Solve and unify The constraints l T4 r39ef r1 r39ef r2 III Mer ge T1 and 2 info 1 I x T1 y T1 1 T3 b r4 p 5 I T1 r39ef r3 T1 r39ef r4 T5 r39ef r1 III Repea r The process I T1 r39ef r3 r39ef r4 El Merge l T1 r39ef r3 T5 r39ef r1 S rr39a regies p malloc III Example q mallow fp ampp fp ampq fp El Flowinsensitive subsetbased p gt heap1 39 fp q gt heap2 Subset based inclusion El Example q ampx qampy pq qampz qampx 1 X qampy 1v X g y pq X 139 3 q 2 y 3 p V Dotted line indicates that the pointsto set for q must be a subset of the pointsto set for p 10 Subset based inclusion q 362 X 1 V3 3 239 y p 4 i z q 362 Subset constraint dotted line indicates that an edge must be established between p and 2 as well What is the runningtime complexity of these two analyses 11 Shape Analysis Syn rax CL I Example 0amp8 1 p 71 a1 Opa a2 nil a 3356 true false not b b1 Opb 2 a1 Opr a2 Opp p pael Skipv 31 32 if b6 then 31 else 32 while be do 8 malloc pe ynil1 while not isnilx2 do zy3 yx4 xxcdr5 ycdrz6 znil7 12 Cdr Cdr Cdr Cdr w o Cdr 1 Y0 X CEEcdrCEQCdrfzcdrCE CdrCEQCdrO O Yaltgt Reversal heap s rr39uc rur39e a r differen r i rer39a rions of The loop X 24gtltgt Z Cdr Cdr x O Cdr Cdr Cdr 3 y 0 Cdr Cdr Cdr X 0 Cdr Cdr 2 y 0 Z Z Cdr X 0 Cdr Cdr Cdr Cdr Cdr 1ltgt Y 5 E Cdr CdrE Cdr cdrltgt 4Y 13 Analysis III To analyze da ra s rruc rures of This form develop an approximation To The ac rual run rime s rruc rure of The heap III Approach l Firs r develop a seman rics rha r describes changes To The heap as The program execu res l Second develop a conserva rive approxima rion To This seman rics l The approxima re s ra re of The heap at different program poin rs is The resul r of The analysis 14 Semantics A configurations consists of o a state a E State 2 Van gt Z Loc 0 mapping variables to values locations in the heap or the nil value o a heap H E Heap 2 Loc gtlt Sel gt n Z Loc 0 mapping pairs of locations and selectors to values locations in the heap or the nil value 15 Defining Pointers p PExp gt State gtlt Heap gt n Z ltgt Loc is defined by meH 000 Haxse if 0x 6 Loc and H is defined on 0xse p xse0 H undefined otherwise Arithmetic and boolean expressions A Z AExp gt State gtlt Heap gt n Z Loc ltgt 8 BEXp gt State gtlt Heap gt n T 16 Assignmen r and Selec rion Clauses for assignments ltmza 0Hgt gt lt0m I gt Aa0H7 gt if AaaH is defined ltmsea 0Hgt gt lt0Hax sel gt AaUHgt if 0x E Loc and AaaH iS defined Clauses for malloc malloc x aHgt gt ltax I gt ELH where 5 does not occur in a or H malloc xse 0Hgt s lt0HUm sel H 51gt where 5 does not occur in a or H and 0x 6 Loc 17 Shape Graphs The analysis will operate on shape graphs 5 H is consisting of 0 an abstract state S 0 an abstract heap H and 0 sharing information is for the abstract locations The nodes of the shape graphs are abstract locations ALoc nX X g Van Note there will only be finitely many abstract locations 18 Example Abstract Locations In the semantics d d d X C r C r C r 0 The abstract location nX represents y a o the location 0x if x E X Z The abstract location n0 is called the abstract summary location n0 rep resents all the locations that cannot be reached directly from the state without consulting the heap In the analysis cdr x fmw Invariant 1 If two abstract locations cdr Y n nX and my occur In the same shape Z graph then either X Y or XmY V 19 Abstract States and Heaps S e AState 73VargtltAL0c abstract states H E AHeap 73ALoc gtlt Sel gtlt ALoc abstract heap Invariant 2 If 1 is mapped to nX by cdr X M the abstract state S then 1 e X Y n Invariant 3 Whenever nVSenw Z J and nVSenW are in the abstract heap H then either V Q or W W 20 Lis r Reversal afTer successive i rer39a rions Cdr O Xawr 1 Y1 Cdr X 4 Car X an Cdr Car 2 Y 3 Y sum 2 J z Cdr Cdr Cdr Car 4 Yam 5 BraCiquot ZJ 2 21 Sharing x tir L x ti L C r C r 4amp0 lcdr 55 cdr O y Give rise to the same shape graph is the abstract locations that might be shared due to pointers in the cdr xen nq eaPi nX is included in is if it might repre Y an cdr sents a location that is the target of more than one pointer in the heap 22 Examples x ai icdr lcdr y Cgs cdr ltgt x aii icdr ltgt y ii icdr X 51 cdr cdr ltgt y cdr xan Y4 cdr cdr xan y4 cdr cdr 23 Sharing Invariants The implicit sharing information of the abstract heap must be consistent with the explicit sharing information Invariant 4 If nX e is then either d o n senX is in the abstract heap for C r X an i3 some Se or lcdi o there are two distinct triples nV se1nX Y cdr and nWSe2nX in the abstract heap Invariant 5 Whenever there are two distinct triples nVSe1nX and nWse2 nX in the abstract heap and X 72 Q then nX E is 24

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.