1 Program Analysis via Graph Reachability Taken from Thomas Reps’ PLDI 2000 Tutorial Software Eng. Applications • Program understanding • Reengineering • Testing & Analysis2 Program Slicing • The backward slice w.r.t variable v at program point p – The program subset that may influence the value of variable v at point p. • The forward slice w.r.t variable v at program point p – The program subset that may be influenced by the value of variable v at point p. Weiser’s Slicing Algorithm • How does Weiser’s definition of a slice differ from Reps’?3 int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } Backward Slice Backward slice with respect to “printf(“%d\n”,i)” int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } Backward Slice Backward slice with respect to “printf(“%d\n”,i)”4 int main() { int i = 1; while (i < 11) { i = i + 1; } printf(“%d\n”,i); } Slice Extraction Backward slice with respect to “printf(“%d\n”,i)” Forward Slice int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } Forward slice with respect to “sum = 0”5 Forward slice with respect to “sum = 0” Forward Slice int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } What Are Slices Useful For? • Understanding Programs – What is affected by what? • Restructuring Programs – Isolation of separate “computational threads” • Program Specialization and Reuse – Slices = specialized programs – Only reuse needed slices • Program Differencing – Compare slices to identify changes • Testing – What new test cases would improve coverage? – What regression tests must be rerun after a change?6 Line-Character-Count Program void line_char_count(FILE *f) { int lines = 0; int chars; BOOL eof_flag = FALSE; int n; extern void scan_line(FILE *f, BOOL *bptr, int *iptr); scan_line(f, &eof_flag, &n); chars = n; while(eof_flag == FALSE){ lines = lines + 1; scan_line(f, &eof_flag, &n); chars = chars + n; } printf(“lines = %d\n”, lines); printf(“chars = %d\n”, chars); } Character-Count Program void char_count(FILE *f) { int lines = 0; int chars; BOOL eof_flag = FALSE; int n; extern void scan_line(FILE *f, BOOL *bptr, int *iptr); scan_line(f, &eof_flag, &n); chars = n; while(eof_flag == FALSE){ lines = lines + 1; scan_line(f, &eof_flag, &n); chars = chars + n; } printf(“lines = %d\n”, lines); printf(“chars = %d\n”, chars); }7 Line-Character-Count Program void line_char_count(FILE *f) { int lines = 0; int chars; BOOL eof_flag = FALSE; int n; extern void scan_line(FILE *f, BOOL *bptr, int *iptr); scan_line(f, &eof_flag, &n); chars = n; while(eof_flag == FALSE){ lines = lines + 1; scan_line(f, &eof_flag, &n); chars = chars + n; } printf(“lines = %d\n”, lines); printf(“chars = %d\n”, chars); } Line-Count Program void line_count(FILE *f) { int lines = 0; int chars; BOOL eof_flag = FALSE; int n; extern void scan_line2(FILE *f, BOOL *bptr, int *iptr); scan_line2(f, &eof_flag, &n); chars = n; while(eof_flag == FALSE){ lines = lines + 1; scan_line2(f, &eof_flag, &n); chars = chars + n; } printf(“lines = %d\n”, lines); printf(“chars = %d\n”, chars); }8 Specialization Via Slicing wc -lc wc -c wc -l How are Slices Computed? • Reachability in a Dependence Graph – Program Dependence Graph (PDG) • Dependences within one procedure • Intraprocedural slicing is reachability in one PDG – System Dependence Graph (SDG) • Dependences within entire system • Interprocedural slicing is reachability in the SDG9 How is a PDG Created? • Control Flow Graph (CFG) • PDG is union of: • Control Dependence Graph • Flow Dependence Graph computed from CFG Control Flow Graph Enter sum = 0 i = 1 while(i < 11) printf(sum) printf(i) sum = sum + i i = i + i T F int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); }10 q is reached from p if condition p is true (T), not otherwise. Control Dependence Graph Control dependence p q T p q F Similar for false (F). Enter sum = 0 i = 1 while(i < 11) printf(sum) printf(i) sum = sum + i i = i + i T T T T T T T T int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } Flow Dependence Graph int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } Enter sum = 0 printf(sum) printf(i) sum = sum + i i = i + i Flow dependence p q Value of variable assigned at p may be used at q. i = 1 while(i < 11)11 Program Dependence Graph (PDG) int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } Enter sum = 0 i = 1 while(i < 11) printf(sum) printf(i) sum = sum + i i = i + i T T T T T Control dependence Flow dependence T T T Program Dependence Graph (PDG) int main() { int i = 1; int sum = 0; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } Enter sum = 0 i = 1 while(i < 11) printf(sum) printf(i) sum = sum + i i = i + i T T T T T T T T Opposite Order Same PDG12 Backward Slice int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } Enter sum = 0 i = 1 while(i < 11) printf(sum) printf(i) sum = sum + i i = i + i T T T T T T T T Backward Slice (2) int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } Enter sum = 0 i = 1 while(i < 11) printf(sum) printf(i) sum = sum + i i = i + i T T T T T T T T13 Backward Slice (3) int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } Enter sum = 0 i = 1 while(i < 11) printf(sum) printf(i) sum = sum + i i = i