舍 Basic Block Defn Basic Block:A consecutive sequence of instructions/ code such that control is“straight'" (no jump targets except at the beginning, no jumps except at the end) 1.x=y+Z 2.z=t+I 3.jmp 3 4.x=y+Z 3 basic blocks 5.z=t+i 6.jmp 1 7.jmp 4 6
Defn Basic Block: A consecutive sequence of instructions / code such that • the instruction in each position always executes before (dominates) all those in later positions, and • no outside instruction can execute between two instructions in the sequence control is “straight” (no jump targets except at the beginning, no jumps except at the end) Basic Block 6 1. x = y + z 2. z = t + I 3. jmp 3 4. x = y + z 5. z = t + i 6. jmp 1 7. jmp 4 3 basic blocks
CFG Definition A static Control Flow Graph is a graph where each vertex v;is a basic block,and there is an edge (vi v)if there may be a transfer of control from block vi to block vi Historically,the scope of a "CFG"is limited to a function or procedure,i.e.,intra-procedural. 7
CFG Definition A static Control Flow Graphis a graph where – each vertex vi is a basic block, and – there is an edge (vi , vj ) if there may be a transfer of control from block vi to block vj . Historically, the scope of a “CFG” is limited to a function or procedure, i.e., intra-procedural. 7
Super Graph Superimpose CFGs of all procedures over the call graph void orange() void red(int x) void green() { { { 1.red(1): green ( 2.red(2); orange () 3.green(); } 1 1:red A context sensitive 2 super-graph for 3 2:red orange lines 1 and 2. 8
Super Graph • Superimpose CFGs of all procedures over the call graph 1: red 1 2 3 2: red A context sensitive super-graph for orange lines 1 and 2. void orange() { 1. red(1); 2. red(2); 3. green(); } void red(int x) { .. } void green() { green(); orange(); } 8
最需 Precision:Sensitive or Insensitiv The more precise the analysis,the more accurate it reflects the "real"program behavior. More precise more time to compute More precise more space Limited by soundness/completeness tradeoff Common Terminology in any Static Analysis: -Context sensitive vs.context insensitive Flow sensitive vs.flow insensitive Path sensitive vs.path insensitive 9
Precision: Sensitive or Insensitive The more precise the analysis, the more accurate it reflects the “real” program behavior. – More precise = more time to compute – More precise = more space – Limited by soundness/completeness tradeoff Common Terminology in any Static Analysis: – Context sensitive vs. context insensitive – Flow sensitive vs. flow insensitive – Path sensitive vs. path insensitive 9
最剔 Context Sensitive Whether different calling contexts are distinguished void yellow()void red(int x) void green ( { { 1.red(1): green () 2.red(2); yellow(); 3.green(); Context sensitive distinguishes 2 different calls to red(-) 10
Context Sensitive Whether different calling contexts are distinguished void yellow() { 1. red(1); 2. red(2); 3. green(); } void red(int x) { .. } void green() { green(); yellow(); } Context sensitive distinguishes 2 different calls to red(-) 10