| // RUN: %clang_analyze_cc1 %s \ |
| // RUN: -analyzer-checker=debug.DumpDominators \ |
| // RUN: -analyzer-checker=debug.DumpPostDominators \ |
| // RUN: -analyzer-checker=debug.DumpControlDependencies \ |
| // RUN: 2>&1 | FileCheck %s |
| |
| // Test the DominatorsTree implementation with various control flows |
| int test1() |
| { |
| int x = 6; |
| int y = x/2; |
| int z; |
| |
| while(y > 0) { |
| if(y < x) { |
| x = x/y; |
| y = y-1; |
| }else{ |
| z = x - y; |
| } |
| x = x - 1; |
| x = x - 1; |
| } |
| z = x+y; |
| z = 3; |
| return 0; |
| } |
| |
| // [B9 (ENTRY)] -> [B8] -> [B7] -> [B6] -> [B5] -> [B3] -> [B2] |
| // |\ \ / / |
| // | \ ---> [B4] ---> / |
| // | <--------------------------- |
| // V |
| // [B1] -> [B0 (EXIT)] |
| |
| // CHECK: Control dependencies (Node#,Dependency#): |
| // CHECK-NEXT: (2,7) |
| // CHECK-NEXT: (3,7) |
| // CHECK-NEXT: (4,6) |
| // CHECK-NEXT: (4,7) |
| // CHECK-NEXT: (5,6) |
| // CHECK-NEXT: (5,7) |
| // CHECK-NEXT: (6,7) |
| // CHECK-NEXT: (7,7) |
| // CHECK-NEXT: Immediate dominance tree (Node#,IDom#): |
| // CHECK-NEXT: (0,1) |
| // CHECK-NEXT: (1,7) |
| // CHECK-NEXT: (2,3) |
| // CHECK-NEXT: (3,6) |
| // CHECK-NEXT: (4,6) |
| // CHECK-NEXT: (5,6) |
| // CHECK-NEXT: (6,7) |
| // CHECK-NEXT: (7,8) |
| // CHECK-NEXT: (8,9) |
| // CHECK-NEXT: (9,9) |
| // CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): |
| // CHECK-NEXT: (0,0) |
| // CHECK-NEXT: (1,0) |
| // CHECK-NEXT: (2,7) |
| // CHECK-NEXT: (3,2) |
| // CHECK-NEXT: (4,3) |
| // CHECK-NEXT: (5,3) |
| // CHECK-NEXT: (6,3) |
| // CHECK-NEXT: (7,1) |
| // CHECK-NEXT: (8,7) |
| // CHECK-NEXT: (9,8) |
| |
| int test2() |
| { |
| int x,y,z; |
| |
| x = 10; y = 100; |
| if(x > 0){ |
| y = 1; |
| }else{ |
| while(x<=0){ |
| x++; |
| y++; |
| } |
| } |
| z = y; |
| |
| return 0; |
| } |
| |
| // <------------- |
| // / \ |
| // -----------> [B4] -> [B3] -> [B2] |
| // / | |
| // / V |
| // [B7 (ENTRY)] -> [B6] -> [B5] -> [B1] -> [B0 (EXIT)] |
| |
| // CHECK: Control dependencies (Node#,Dependency#): |
| // CHECK-NEXT: (2,4) |
| // CHECK-NEXT: (2,6) |
| // CHECK-NEXT: (3,4) |
| // CHECK-NEXT: (3,6) |
| // CHECK-NEXT: (4,6) |
| // CHECK-NEXT: (4,4) |
| // CHECK-NEXT: (5,6) |
| // CHECK-NEXT: Immediate dominance tree (Node#,IDom#): |
| // CHECK-NEXT: (0,1) |
| // CHECK-NEXT: (1,6) |
| // CHECK-NEXT: (2,3) |
| // CHECK-NEXT: (3,4) |
| // CHECK-NEXT: (4,6) |
| // CHECK-NEXT: (5,6) |
| // CHECK-NEXT: (6,7) |
| // CHECK-NEXT: (7,7) |
| // CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): |
| // CHECK-NEXT: (0,0) |
| // CHECK-NEXT: (1,0) |
| // CHECK-NEXT: (2,4) |
| // CHECK-NEXT: (3,2) |
| // CHECK-NEXT: (4,1) |
| // CHECK-NEXT: (5,1) |
| // CHECK-NEXT: (6,1) |
| // CHECK-NEXT: (7,6) |
| |
| int test3() |
| { |
| int x,y,z; |
| |
| x = y = z = 1; |
| if(x>0) { |
| while(x>=0){ |
| while(y>=x) { |
| x = x-1; |
| y = y/2; |
| } |
| } |
| } |
| z = y; |
| |
| return 0; |
| } |
| |
| // <- [B2] <- |
| // / \ |
| // [B8 (ENTRY)] -> [B7] -> [B6] ---> [B5] -> [B4] -> [B3] |
| // \ | \ / |
| // \ | <------------- |
| // \ \ |
| // --------> [B1] -> [B0 (EXIT)] |
| |
| // CHECK: Control dependencies (Node#,Dependency#): |
| // CHECK-NEXT: (2,6) |
| // CHECK-NEXT: (2,7) |
| // CHECK-NEXT: (3,5) |
| // CHECK-NEXT: (3,6) |
| // CHECK-NEXT: (3,7) |
| // CHECK-NEXT: (4,5) |
| // CHECK-NEXT: (4,6) |
| // CHECK-NEXT: (4,7) |
| // CHECK-NEXT: (5,6) |
| // CHECK-NEXT: (5,5) |
| // CHECK-NEXT: (5,7) |
| // CHECK-NEXT: (6,7) |
| // CHECK-NEXT: (6,6) |
| // CHECK-NEXT: Immediate dominance tree (Node#,IDom#): |
| // CHECK-NEXT: (0,1) |
| // CHECK-NEXT: (1,7) |
| // CHECK-NEXT: (2,5) |
| // CHECK-NEXT: (3,4) |
| // CHECK-NEXT: (4,5) |
| // CHECK-NEXT: (5,6) |
| // CHECK-NEXT: (6,7) |
| // CHECK-NEXT: (7,8) |
| // CHECK-NEXT: (8,8) |
| // CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): |
| // CHECK-NEXT: (0,0) |
| // CHECK-NEXT: (1,0) |
| // CHECK-NEXT: (2,6) |
| // CHECK-NEXT: (3,5) |
| // CHECK-NEXT: (4,3) |
| // CHECK-NEXT: (5,2) |
| // CHECK-NEXT: (6,1) |
| // CHECK-NEXT: (7,1) |
| // CHECK-NEXT: (8,7) |
| |
| int test4() |
| { |
| int y = 3; |
| while(y > 0) { |
| if(y < 3) { |
| while(y>0) |
| y ++; |
| }else{ |
| while(y<10) |
| y ++; |
| } |
| } |
| return 0; |
| } |
| |
| // <---------------------------------- |
| // / <----------------- \ |
| // / / \ \ |
| // [B12 (ENTRY)] -> [B11] -> [B10]-> [B9] -> [B8] ---> [B7] -> [B6] | |
| // | \ \ / |
| // | \ -----> [B2] --------/ |
| // | \ / |
| // | -> [B5] -> [B4] -> [B3] |
| // | \ / |
| // | <------------ |
| // \ |
| // -> [B1] -> [B0 (EXIT)] |
| |
| // CHECK: Control dependencies (Node#,Dependency#): |
| // CHECK-NEXT: (2,10) |
| // CHECK-NEXT: (3,5) |
| // CHECK-NEXT: (3,9) |
| // CHECK-NEXT: (3,10) |
| // CHECK-NEXT: (4,5) |
| // CHECK-NEXT: (4,9) |
| // CHECK-NEXT: (4,10) |
| // CHECK-NEXT: (5,9) |
| // CHECK-NEXT: (5,5) |
| // CHECK-NEXT: (5,10) |
| // CHECK-NEXT: (6,8) |
| // CHECK-NEXT: (6,9) |
| // CHECK-NEXT: (6,10) |
| // CHECK-NEXT: (7,8) |
| // CHECK-NEXT: (7,9) |
| // CHECK-NEXT: (7,10) |
| // CHECK-NEXT: (8,9) |
| // CHECK-NEXT: (8,8) |
| // CHECK-NEXT: (8,10) |
| // CHECK-NEXT: (9,10) |
| // CHECK-NEXT: (10,10) |
| // CHECK-NEXT: Immediate dominance tree (Node#,IDom#): |
| // CHECK-NEXT: (0,1) |
| // CHECK-NEXT: (1,10) |
| // CHECK-NEXT: (2,9) |
| // CHECK-NEXT: (3,4) |
| // CHECK-NEXT: (4,5) |
| // CHECK-NEXT: (5,9) |
| // CHECK-NEXT: (6,7) |
| // CHECK-NEXT: (7,8) |
| // CHECK-NEXT: (8,9) |
| // CHECK-NEXT: (9,10) |
| // CHECK-NEXT: (10,11) |
| // CHECK-NEXT: (11,12) |
| // CHECK-NEXT: (12,12) |
| // CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): |
| // CHECK-NEXT: (0,0) |
| // CHECK-NEXT: (1,0) |
| // CHECK-NEXT: (2,10) |
| // CHECK-NEXT: (3,5) |
| // CHECK-NEXT: (4,3) |
| // CHECK-NEXT: (5,2) |
| // CHECK-NEXT: (6,8) |
| // CHECK-NEXT: (7,6) |
| // CHECK-NEXT: (8,2) |
| // CHECK-NEXT: (9,2) |
| // CHECK-NEXT: (10,1) |
| // CHECK-NEXT: (11,10) |
| // CHECK-NEXT: (12,11) |
| |
| int test5() |
| { |
| int x,y,z,a,b,c; |
| x = 1; |
| y = 2; |
| z = 3; |
| a = 4; |
| b = 5; |
| c = 6; |
| if ( x < 10 ) { |
| if ( y < 10 ) { |
| if ( z < 10 ) { |
| x = 4; |
| } else { |
| x = 5; |
| } |
| a = 10; |
| } else { |
| x = 6; |
| } |
| b = 10; |
| } else { |
| x = 7; |
| } |
| c = 11; |
| return 0; |
| } |
| |
| // [B0 (EXIT)] <-- |
| // \ |
| // [B11 (ENTY)] -> [B10] -> [B9] -> [B8] -> [B7] -> [B5] -> [B3] -> [B1] |
| // | | | / / / |
| // | | V / / / |
| // | V [B6] --> / / |
| // V [B4] -----------------> / |
| // [B2]---------------------------------> |
| |
| // CHECK: Control dependencies (Node#,Dependency#): |
| // CHECK-NEXT: (2,10) |
| // CHECK-NEXT: (3,10) |
| // CHECK-NEXT: (4,9) |
| // CHECK-NEXT: (4,10) |
| // CHECK-NEXT: (5,9) |
| // CHECK-NEXT: (5,10) |
| // CHECK-NEXT: (6,8) |
| // CHECK-NEXT: (6,9) |
| // CHECK-NEXT: (6,10) |
| // CHECK-NEXT: (7,8) |
| // CHECK-NEXT: (7,9) |
| // CHECK-NEXT: (7,10) |
| // CHECK-NEXT: (8,9) |
| // CHECK-NEXT: (8,10) |
| // CHECK-NEXT: (9,10) |
| // CHECK-NEXT: Immediate dominance tree (Node#,IDom#): |
| // CHECK-NEXT: (0,1) |
| // CHECK-NEXT: (1,10) |
| // CHECK-NEXT: (2,10) |
| // CHECK-NEXT: (3,9) |
| // CHECK-NEXT: (4,9) |
| // CHECK-NEXT: (5,8) |
| // CHECK-NEXT: (6,8) |
| // CHECK-NEXT: (7,8) |
| // CHECK-NEXT: (8,9) |
| // CHECK-NEXT: (9,10) |
| // CHECK-NEXT: (10,11) |
| // CHECK-NEXT: (11,11) |
| // CHECK-NEXT: Immediate post dominance tree (Node#,IDom#): |
| // CHECK-NEXT: (0,0) |
| // CHECK-NEXT: (1,0) |
| // CHECK-NEXT: (2,1) |
| // CHECK-NEXT: (3,1) |
| // CHECK-NEXT: (4,3) |
| // CHECK-NEXT: (5,3) |
| // CHECK-NEXT: (6,5) |
| // CHECK-NEXT: (7,5) |
| // CHECK-NEXT: (8,5) |
| // CHECK-NEXT: (9,3) |
| // CHECK-NEXT: (10,1) |
| // CHECK-NEXT: (11,10) |
