Context Sensitive Example a id(4): →void id(intz) Context-Sensitive return z;} (color denotes b=id(5); matching call/ret) Context sensitive can tell one call returns 4,the other 5 a=id(4); →void id(intz) Context-Insensitive return z;} (note merging) b=id(5); Context insensitive will say both callsreturn {4,5} 11
Context Sensitive Example a = id(4); b = id(5); void id(int z) { return z; } Context-Sensitive (color denotes matching call/ret) a = id(4); b = id(5); void id(int z) { return z; } Context-Insensitive (note merging) 11 Context sensitive can tell one call returns 4, the other 5 Context insensitive will say both calls return {4,5}
Flow Sensitive A flow sensitive analysis considers the order (flow)of statements Flow insensitive usually linear-type algorithm Flow sensitive consider the dataflow Examples: Type checking is flow insensitive since a variable has a single type regardless of the order of statements Detecting uninitialized variables requires flow sensitivity X 4 Flow sensitive can distinguish values of x, X 5 flow insensitive cannot 12
Flow Sensitive • A flow sensitive analysis considers the order (flow) of statements – Flow insensitive = usually linear-type algorithm – Flow sensitive = consider the dataflow • Examples: – Type checking is flow insensitive since a variable has a single type regardless of the order of statements – Detecting uninitialized variables requires flow sensitivity x = 4; .... x = 5; Flow sensitive can distinguish values of x, flow insensitive cannot 12
发需 Flow Sensitive Example Flow sensitive: 1.x 4 x is the constant 4 at line 1, x is the constant 5 at line n n.x 5; Flow insensitive: x is not a constant 13
Flow Sensitive Example 1. x = 4; .... n. x = 5; Flow sensitive: x is the constant 4 at line 1, x is the constant 5 at line n Flow insensitive: x is not a constant 13
Path Sensitive A path sensitive analysis maintains branch conditions along each execution path path-sensitive analysis computes different pieces of analysis information dependent on the predicates at conditional branch instructions. For instance,if a branch contains a condition x>0 then on the fall-through path,the analysis would assume that x<=0 and on the target of the branch it would assume that indeed x>0 holds. 14
Path Sensitive A path sensitive analysis maintains branch conditions along each execution path – path-sensitive analysis computes different pieces of analysis information dependent on the predicates at conditional branch instructions. For instance, if a branch contains a condition x>0, then on the fall-through path, the analysis would assume that x<=0 and on the target of the branch it would assume that indeed x>0 holds. 14
最 Path Sensitive Example path sensitive: 1.if(x>=0) y>=0 at line 2, 2 y-xi y>0 at line 4 3. else 4. y=-X; path insensitive: y is not a constant 15
Path Sensitive Example 1. if(x >= 0) 2. y = x; 3. else 4. y = -x; path sensitive: y >= 0 at line 2, y > 0 at line 4 path insensitive: y is not a constant 15