Week 3 Static Analysis Examples
Constant Propagation (demo)
· Flat lattice of integer values
· Rules are same as Sign analysis, but with wider lattice.
Copyright By PowCoder代写 加微信 powcoder
· Note: this is a Forward analysis
var x,y,z; [x->T, y->T, z->T]
x = 27; [
y = input; [
z = 2*x+y; [
if (x < 0) ?
{ y = z-3; } [
{ y = 12; } [
Live variables analysis
· A variable is live at a program point if its current value may be read in the remaining execution.
· (see Slide 7 in 4-flow-sensitive-analysis.pdf)
· Note: Backward May analysis! JOIN = union.
Iteration 1 Iteration 2
var x,y,z; {
x = input; {
while (x>1) { {
y = x/2; {
if (y>3) {
x = x-y; {
z = x-4; {
if (z>0) {
x = x/2; {
z = z-1; {
output x; {
exit {
Available expressions analysis
· a nontrivial expression is available at a program point if its current value must have already been computed earlier in the execution
· (see Slide 18 in 4-flow-sensitive-analysis.pdf)
· Note: FORWARDS analysis! JOIN=intersection (a MUST analysis)
var x,y,z,a,b; {
z = a+b; {
y = a+b; {
while (y > a) { {
a = a+1; {
x = a*b; {
Very busy expressions analysis
· a nontrivial expression is very busy if it will definitely be evaluated before its value changes
· (see Slide 28 in 4-flow-sensitive-analysis.pdf)
· Note: Backwards analysis! JOIN=intersection (a MUST analysis)
· (same style of lattice as previous analysis, but with expressions from this program)
var x,a,b; {
x = input; {
a = x-1; {
b = x-2; {
while (x > 0) { {
output a*b-x; {
x = x-1; {
output a*b; {
Reaching definitions analysis (def-use)
· The reaching definitions for a program point are those assignments that may define the current values of variables.
· (see Slide 35 in 4-flow-sensitive-analysis.pdf)
· Note: FORWARDS analysis! JOIN=union (a MAY analysis)
var x,y,z; {
x = input; {
while (x > 1) {
y = x/2; {
x = x-y; {
z = x-4; {
x = x/2; {
z = z-1; {
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com