Program Analysis with Set Constraints
Program Analysis
with Set Constraints
Ravi Chugh
Set-constraint based analysis
•
Another technique for computing information
about program variables
•
Phase 1: constraint generation
–
Create set variables corresponding to program
–
Add inclusion constraints between these sets
–
Usually a local, syntax-directed process (ASTs vs CFGs)
•
Phase 2: constraint resolution
–
Solve for values of all set variables
•
Extends naturally to inter-procedural analysis
Constant propagation
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
•
Want to determine
whether
x
and
y
are
constant values when
they are used
•
We will build a flow-
insensitive analysis
Set constraints
•
Terms
t := c
(constant)
| X
(set variable)
| C(t
1
,...,t
n
)
(constructed term)
•
Constraints
t
1
t
2
(set inclusion)
•
Constructors
–
C(v
1
,...,v
n
)
is an n-arg ctor
C
with variances
v
i
–
v
i
is either
+
(covariant) or
–
(contravariant)
–
Covariance corresponds to “forwards flow”
–
Contravariance corresponds to “backwards flow”
Additional constraints
•
Implicit constraints added by following rules:
•
1) Transitivity
if
t
1
t
2
and
t
2
t
3
then
t
1
t
3
•
2) Variance through constructed terms
if
C(...,t
i
,...)
C(...,u
i
,...)
then
t
i
u
i
for covariant positions of
C
u
i
t
i
for contravariant positions of
C
Constraint graphs
•
1
X
•
X
Y
•
Ctor(A,B,C)
Ctor(D,E,F)
where
Ctor(+,-,+)
Function calls
•
Define ctor
Fun(-,+)
for one input/one output
•
To encode a function def/call:
int z = id(2);
Fun(i,r)
id
Fun(2,z)
•
By contravariance, the actual
2
flows to
i
•
By covariance, the return value of
id
flows to
z
id
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
abs
int abs(int i) { if (...) { return i;
}
else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
abs
int abs(int i) { if (...) { return i;
}
else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
abs
int abs(int i) { if (...) { return i; } else { return –i;
}
}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
abs
int abs(int i) { if (...) { return i; } else { return –i;
}
}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
T
r1
abs
T
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
T
r1
abs
T
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
id
abs
T
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
id
abs
T
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
j
r2
id
abs
T
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
j
r2
id
abs
T
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
j
r2
1
a
2
b
id
b
2
abs
a
1
T
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
j
r2
1
a
2
b
id
b
2
abs
a
1
T
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
j
r2
1
a
2
b
abs
Fun(a,x)
id
b
2
abs
a
1
T
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
j
r2
1
a
2
b
abs
Fun(a,x)
id
b
2
abs
a
1
T
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
... use x ...
... use y ...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
j
r2
1
a
2
b
abs
Fun(a,x)
id
Fun(b,y)
id
b
2
abs
a
1
T
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
...
use x
...
...
use y
...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
j
r2
1
a
2
b
abs
Fun(a,x)
id
Fun(b,y)
id
b
2
abs
a
1
T
??
x
??
y
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
...
use x
...
...
use y
...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
j
r2
1
a
2
b
abs
Fun(a,x)
id
Fun(b,y)
id
b
2
abs
a
1
T
{1,T}
x
??
y
int abs(int i) { if (...) { return i; } else { return –i; }}
int id(int j) {return j;
}
void main() {int a = 1, b = 2;
int x = abs(a);
int y = id(b);
...
use x
...
...
use y
...
}
Fun(i,r1)
abs
i
r1
T
r1
Fun(j,r2)
id
j
r2
1
a
2
b
abs
Fun(a,x)
id
Fun(b,y)
id
b
2
abs
a
1
T
{1,T}
x
{2}
y
Pointers
•
Handle pointers with a
Ref(-,+)
constructor
•
Two args correspond to set and get operations
int i =
1;
int
*p = &i;
*p
= 2;
int
j = *p;
1
i
Pointers
•
Handle pointers with a
Ref(-,+)
constructor
•
Two args correspond to set and get operations
int i =
1;
int
*p =
&i
;
*p
= 2;
int
j = *p;
1
Pointers
•
Handle pointers with a
Ref(-,+)
constructor
•
Two args correspond to set and get operations
int i =
1;
int
*p = &i;
*p
= 2;
int
j = *p;
p
1
Pointers
•
Handle pointers with a
Ref(-,+)
constructor
•
Two args correspond to set and get operations
int i =
1;
int
*p = &i;
*p
= 2;
int
j = *p;
p
1
Pointers
•
Handle pointers with a
Ref(-,+)
constructor
•
Two args correspond to set and get operations
int i =
1;
int
*p = &i;
*p
= 2;
int
j = *p;
p
1
Pointers
•
Handle pointers with a
Ref(-,+)
constructor
•
Two args correspond to set and get operations
int i =
1;
int
*p = &i;
*p
= 2;
int
j = *p;
p
1
More on functions
•
This encoding supports higher-order functions
–
Passing around
Fun
terms just like constants
•
Function pointers also work
int (*funcPtr)(int);
int id(int j) { return j };funcPtr = &id;
int x = (*funcPtr)(0);
id
More on functions
•
This encoding supports higher-order functions
–
Passing around
Fun
terms just like constants
•
Function pointers also work
int (*funcPtr)(int);
int id(int j) { return j };funcPtr =
&id
;
int x = (*funcPtr)(0);
id
More on functions
•
This encoding supports higher-order functions
–
Passing around
Fun
terms just like constants
•
Function pointers also work
int (*funcPtr)(int);
int id(int j) { return j };funcPtr = &id;
int x = (*funcPtr)(0);
Ref
More on functions
•
This encoding supports higher-order functions
–
Passing around
Fun
terms just like constants
•
Function pointers also work
int (*funcPtr)(int);
int id(int j) { return j };funcPtr = &id;
int x = (*funcPtr)(0);
funcPtr
Context (in)sensitivity
•
Multiple call sites
int x = id(1);
int y = id(2);
id
{1,2}
x{1,2}
y
Context sensitivity
•
Multiple call sites
int x = id
1
(1);
int y = id
2
(2);
•
Option 1: Specialization
•
Each call
id
i
gets a new copy of
id
•
Eliminates smearing but increases graph size
id
2
id
1
{1}
x
{2}
y
Context sensitivity
•
Option 2: Unique labeled edges for each call site
•
Not using
Fun
constructor
•
There is flow only if there is a path that spells a
substring of a well-bracketed string
–
[
a
[
b
]
b
]
a
and [
a
]
a
[
b
are valid; [
a
[
b
]
a
]
b
is not
•
For both options, if there are higher-order
functions or function pointers, need a first pass to
compute pointer targets
[
1
]
1
[
2
]
2
1
x
2
y
j
r
Field sensitivity
•
For each field
f
, define
Fld
f
(-,+)
constructor
obj o = { f:3; g:4 };int readG(obj p) { return p.g; }int w = id(o.f);
int z = readG(o);
o
id
Field sensitivity
•
For each field
f
, define
Fld
f
(-,+)
constructor
obj o = { f:3; g:4 };int readG(obj p) { return p.g; }int w = id(o.f);
int z = readG(o);
o
id
Field sensitivity
•
For each field
f
, define
Fld
f
(-,+)
constructor
obj o = { f:3; g:4 };int readG(obj p) { return p.g; }int w = id(o.f);
int z = readG(o);
id
readG
o
Field sensitivity
•
For each field
f
, define
Fld
f
(-,+)
constructor
obj o = { f:3; g:4 };int readG(obj p) { return p.g; }int w = id(o.f);
int z = readG(o);
id
readG
o
Field sensitivity
•
For each field
f
, define
Fld
f
(-,+)
constructor
obj o = { f:3; g:4 };int readG(obj p) { return p.g; }int w = id(o.f);
int z = readG(o);
id
readG
o
Field sensitivity
•
For each field
f
, define
Fld
f
(-,+)
constructor
obj o = { f:3; g:4 };int readG(obj p) { return p.g; }int w = id(o.f);
int z = readG(o);
id
readG
o
Field sensitivity
•
For each field
f
, define
Fld
f
(-,+)
constructor
obj o = { f:3; g:4 };int readG(obj p) { return p.g; }int w = id(o.f);
int z = readG(o);
id
readG
o
Scalability
•
Constraint graph for entire program is in memory
•
Even for flow-insensitive analyses, this can
become a bottleneck
•
Even worse for flow-sensitive analyses
•
Techniques for analyzing parts of program in
isolation and storing summaries of their
observable effects
Summary
•
Set constraints a natural way to express various
program analyses
–
Constant propagation, pointer analysis
–
Closure analysis
–
Receiver class analysis, prototype-based inheritance
–
Information flow
•
Rich literature on solving systems of constraints
•
Non-trivial to extend to flow-sensitive or
summary-based analyses
•
Interference between functions and references
Explore the concept of program analysis with set constraints, delving into techniques like set-variable-based analysis, constant propagation, and constraint graphs. Learn about term constraints, additional implicit constraints, and function calls in the context of set-constraint based analysis. Gain insights into how constraint resolution plays a key role in determining program variables and values using set constraints.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Program Analysis with Set Constraints Ravi Chugh
Set-constraint based analysis Another technique for computing information about program variables Phase 1: constraint generation Create set variables corresponding to program Add inclusion constraints between these sets Usually a local, syntax-directed process (ASTs vs CFGs) Phase 2: constraint resolution Solve for values of all set variables Extends naturally to inter-procedural analysis
Constant propagation Want to determine whether x and y are constant values when they are used int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } We will build a flow- insensitive analysis
Set constraints Terms t := c (constant) (set variable) (constructed term) | X | C(t1,...,tn) Constraints t1 t2 Constructors C(v1,...,vn) is an n-arg ctor C with variances vi viis either + (covariant) or (contravariant) Covariance corresponds to forwards flow Contravariance corresponds to backwards flow (set inclusion)
Additional constraints Implicit constraints added by following rules: 1) Transitivity if t1 t2and t2 t3then t1 t3 2) Variance through constructed terms if C(...,ti,...) C(...,ui,...) then ti uifor covariant positions of C ui tifor contravariant positions of C
Constraint graphs 1 X 1 X X Y Y B C A Ctor Ctor(A,B,C) Ctor(D,E,F) where Ctor(+,-,+) E F D Ctor
Function calls Define ctor Fun(-,+) for one input/one output To encode a function def/call: int z = id(2); Fun(i,r) id Fun(2,z) By contravariance, the actual 2 flows to i By covariance, the return value of id flows to z r i Fun id z 2 Fun
int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... }
int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... }
Fun(i,r1) abs int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } i Fun r1 abs
Fun(i,r1) abs int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } i Fun r1 abs
Fun(i,r1) abs i r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } i Fun r1 abs
Fun(i,r1) abs i r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } i Fun r1 abs
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } T i Fun r1 abs
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } T i Fun r1 abs
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id T i j Fun Fun r1 r2 abs id
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id T i j Fun Fun r1 r2 abs id
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id j r2 T i j Fun Fun r1 r2 abs id
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id j r2 T i j Fun Fun r1 r2 abs id
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id j r2 1 a 2 b T i j Fun Fun r1 r2 abs id a b 1 2
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id j r2 1 a 2 b T i j Fun Fun r1 r2 abs id a b 1 2
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id j r2 1 a 2 b abs Fun(a,x) T i j Fun Fun r1 r2 abs id x Fun a b 1 2
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id j r2 1 a 2 b abs Fun(a,x) T i j Fun Fun r1 r2 abs id x Fun a b 1 2
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id j r2 1 a 2 b abs Fun(a,x) id Fun(b,y) T i j Fun Fun r1 r2 abs id x y Fun Fun a b 1 2
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id j r2 ?? x ?? y 1 a 2 b abs Fun(a,x) id Fun(b,y) T i j Fun Fun r1 r2 abs id x y Fun Fun a b 1 2
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id j r2 {1,T} x ?? y 1 a 2 b abs Fun(a,x) id Fun(b,y) T i j Fun Fun r1 r2 abs id x y Fun Fun a b 1 2
Fun(i,r1) abs i r1 T r1 int abs(int i) { if (...) { return i; } else { return i; } } int id(int j) { return j; } void main() { int a = 1, b = 2; int x = abs(a); int y = id(b); ... use x ... ... use y ... } Fun(j,r2) id j r2 {1,T} x {2} y 1 a 2 b abs Fun(a,x) id Fun(b,y) T i j Fun Fun r1 r2 abs id x y Fun Fun a b 1 2
Pointers Handle pointers with a Ref(-,+) constructor Two args correspond to set and get operations i 1 int i = 1; int *p = &i; *p = 2; int j = *p;
Pointers Handle pointers with a Ref(-,+) constructor Two args correspond to set and get operations i 1 Ref int i = 1; int *p = &i; *p = 2; int j = *p;
Pointers Handle pointers with a Ref(-,+) constructor Two args correspond to set and get operations i 1 Ref int i = 1; int *p = &i; *p = 2; int j = *p; p
Pointers Handle pointers with a Ref(-,+) constructor Two args correspond to set and get operations i 1 Ref int i = 1; int *p = &i; *p = 2; int j = *p; p 2 Ref
Pointers Handle pointers with a Ref(-,+) constructor Two args correspond to set and get operations i 1 Ref int i = 1; int *p = &i; *p = 2; int j = *p; p j Ref 2 Ref
Pointers Handle pointers with a Ref(-,+) constructor Two args correspond to set and get operations i 1 Ref int i = 1; int *p = &i; *p = 2; int j = *p; p j Ref 2 Ref
More on functions This encoding supports higher-order functions Passing around Fun terms just like constants Function pointers also work int (*funcPtr)(int); int id(int j) { return j }; funcPtr = &id; int x = (*funcPtr)(0); j Fun id
More on functions This encoding supports higher-order functions Passing around Fun terms just like constants Function pointers also work int (*funcPtr)(int); int id(int j) { return j }; funcPtr = &id; int x = (*funcPtr)(0); j Fun id id Ref
More on functions This encoding supports higher-order functions Passing around Fun terms just like constants Function pointers also work int (*funcPtr)(int); int id(int j) { return j }; funcPtr = &id; int x = (*funcPtr)(0); j Fun id Ref funcPtr
More on functions This encoding supports higher-order functions Passing around Fun terms just like constants Function pointers also work int (*funcPtr)(int); int id(int j) { return j }; funcPtr = &id; int x = (*funcPtr)(0); j Fun id Ref funcPtr Ref x 0 Fun
Context (in)sensitivity Multiple call sites int x = id(1); int y = id(2); {1,2} x{1,2} y r id j Fun x y 1 2 Fun Fun
Context sensitivity Multiple call sites int x = id1(1); int y = id2(2); Option 1: Specialization Each call idi gets a new copy of id {1} x {2} y r2 Fun j2 r1 Fun j1 id2 id1 y 2 Fun x 1 Fun Eliminates smearing but increases graph size
Context sensitivity Option 2: Unique labeled edges for each call site Not using Fun constructor j r [1 ]1 [2 ]2 1 x 2 y There is flow only if there is a path that spells a substring of a well-bracketed string [a[b]b]a and [a]a[b are valid; [a[b]a]b is not For both options, if there are higher-order functions or function pointers, need a first pass to compute pointer targets
Field sensitivity For each field f, define Fldf(-,+)constructor obj o = { f:3; g:4 }; int readG(obj p) { return p.g; } int w = id(o.f); int z = readG(o); r j Fun id o.f o.g Fldf Fldg o 3 Fldf 4 Fldg
Field sensitivity For each field f, define Fldf(-,+)constructor obj o = { f:3; g:4 }; int readG(obj p) { return p.g; } int w = id(o.f); int z = readG(o); r j Fun id o.f o.g Fldf Fldg o 3 Fldf 4 Fldg
Field sensitivity For each field f, define Fldf(-,+)constructor obj o = { f:3; g:4 }; int readG(obj p) { return p.g; } int w = id(o.f); int z = readG(o); Fldg r j Fun id r3 p Fun o.f o.g Fldf Fldg readG o 3 Fldf 4 Fldg
Field sensitivity For each field f, define Fldf(-,+)constructor obj o = { f:3; g:4 }; int readG(obj p) { return p.g; } int w = id(o.f); int z = readG(o); Fldg r j Fun id r3 p Fun o.f o.g Fldf Fldg w Fun readG Fldf o 3 Fldf 4 Fldg
Field sensitivity For each field f, define Fldf(-,+)constructor obj o = { f:3; g:4 }; int readG(obj p) { return p.g; } int w = id(o.f); int z = readG(o); Fldg r j Fun id r3 p Fun o.f o.g Fldf Fldg w Fun readG Fldf o 3 Fldf 4 Fldg
Field sensitivity For each field f, define Fldf(-,+)constructor obj o = { f:3; g:4 }; int readG(obj p) { return p.g; } int w = id(o.f); int z = readG(o); Fldg r j Fun id r3 p Fun o.f o.g Fldf Fldg w Fun readG z Fun Fldf o 3 Fldf 4 Fldg
Field sensitivity For each field f, define Fldf(-,+)constructor obj o = { f:3; g:4 }; int readG(obj p) { return p.g; } int w = id(o.f); int z = readG(o); Fldg r j Fun id r3 p Fun o.f o.g Fldf Fldg w Fun readG z Fun Fldf o 3 Fldf 4 Fldg
Scalability Constraint graph for entire program is in memory Even for flow-insensitive analyses, this can become a bottleneck Even worse for flow-sensitive analyses Techniques for analyzing parts of program in isolation and storing summaries of their observable effects
Summary Set constraints a natural way to express various program analyses Constant propagation, pointer analysis Closure analysis Receiver class analysis, prototype-based inheritance Information flow Rich literature on solving systems of constraints Non-trivial to extend to flow-sensitive or summary-based analyses Interference between functions and references
![Read⚡ebook✔[PDF] Life in the Universe: Expectations and Constraints (Springer P](/thumb/21626/read-ebook-pdf-life-in-the-universe-expectations-and-constraints-springer-p.jpg)
