339 lines · c
1// RUN: %clang_analyze_cc1 %s \2// RUN: -analyzer-checker=debug.DumpDominators \3// RUN: -analyzer-checker=debug.DumpPostDominators \4// RUN: -analyzer-checker=debug.DumpControlDependencies \5// RUN: 2>&1 | FileCheck %s6 7// Test the DominatorsTree implementation with various control flows8int test1(void)9{10 int x = 6;11 int y = x/2;12 int z;13 14 while(y > 0) {15 if(y < x) {16 x = x/y;17 y = y-1;18 }else{19 z = x - y;20 }21 x = x - 1;22 x = x - 1;23 }24 z = x+y;25 z = 3;26 return 0;27}28 29// [B9 (ENTRY)] -> [B8] -> [B7] -> [B6] -> [B5] -> [B3] -> [B2]30// |\ \ / /31// | \ ---> [B4] ---> /32// | <---------------------------33// V34// [B1] -> [B0 (EXIT)]35 36// CHECK: Control dependencies (Node#,Dependency#):37// CHECK-NEXT: (2,7)38// CHECK-NEXT: (3,7)39// CHECK-NEXT: (4,6)40// CHECK-NEXT: (4,7)41// CHECK-NEXT: (5,6)42// CHECK-NEXT: (5,7)43// CHECK-NEXT: (6,7)44// CHECK-NEXT: (7,7)45// CHECK-NEXT: Immediate dominance tree (Node#,IDom#):46// CHECK-NEXT: (0,1)47// CHECK-NEXT: (1,7)48// CHECK-NEXT: (2,3)49// CHECK-NEXT: (3,6)50// CHECK-NEXT: (4,6)51// CHECK-NEXT: (5,6)52// CHECK-NEXT: (6,7)53// CHECK-NEXT: (7,8)54// CHECK-NEXT: (8,9)55// CHECK-NEXT: (9,9)56// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):57// CHECK-NEXT: (0,0)58// CHECK-NEXT: (1,0)59// CHECK-NEXT: (2,7)60// CHECK-NEXT: (3,2)61// CHECK-NEXT: (4,3)62// CHECK-NEXT: (5,3)63// CHECK-NEXT: (6,3)64// CHECK-NEXT: (7,1)65// CHECK-NEXT: (8,7)66// CHECK-NEXT: (9,8)67 68int test2(void)69{70 int x,y,z;71 72 x = 10; y = 100;73 if(x > 0){74 y = 1;75 }else{76 while(x<=0){77 x++;78 y++;79 }80 }81 z = y;82 83 return 0;84}85 86// <-------------87// / \88// -----------> [B4] -> [B3] -> [B2]89// / |90// / V91// [B7 (ENTRY)] -> [B6] -> [B5] -> [B1] -> [B0 (EXIT)]92 93// CHECK: Control dependencies (Node#,Dependency#):94// CHECK-NEXT: (2,4)95// CHECK-NEXT: (2,6)96// CHECK-NEXT: (3,4)97// CHECK-NEXT: (3,6)98// CHECK-NEXT: (4,6)99// CHECK-NEXT: (4,4)100// CHECK-NEXT: (5,6)101// CHECK-NEXT: Immediate dominance tree (Node#,IDom#):102// CHECK-NEXT: (0,1)103// CHECK-NEXT: (1,6)104// CHECK-NEXT: (2,3)105// CHECK-NEXT: (3,4)106// CHECK-NEXT: (4,6)107// CHECK-NEXT: (5,6)108// CHECK-NEXT: (6,7)109// CHECK-NEXT: (7,7)110// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):111// CHECK-NEXT: (0,0)112// CHECK-NEXT: (1,0)113// CHECK-NEXT: (2,4)114// CHECK-NEXT: (3,2)115// CHECK-NEXT: (4,1)116// CHECK-NEXT: (5,1)117// CHECK-NEXT: (6,1)118// CHECK-NEXT: (7,6)119 120int test3(void)121{122 int x,y,z;123 124 x = y = z = 1;125 if(x>0) {126 while(x>=0){127 while(y>=x) {128 x = x-1;129 y = y/2;130 }131 }132 }133 z = y;134 135 return 0;136}137 138// <- [B2] <-139// / \140// [B8 (ENTRY)] -> [B7] -> [B6] ---> [B5] -> [B4] -> [B3]141// \ | \ /142// \ | <-------------143// \ \144// --------> [B1] -> [B0 (EXIT)]145 146// CHECK: Control dependencies (Node#,Dependency#):147// CHECK-NEXT: (2,6)148// CHECK-NEXT: (2,7)149// CHECK-NEXT: (3,5)150// CHECK-NEXT: (3,6)151// CHECK-NEXT: (3,7)152// CHECK-NEXT: (4,5)153// CHECK-NEXT: (4,6)154// CHECK-NEXT: (4,7)155// CHECK-NEXT: (5,6)156// CHECK-NEXT: (5,5)157// CHECK-NEXT: (5,7)158// CHECK-NEXT: (6,7)159// CHECK-NEXT: (6,6)160// CHECK-NEXT: Immediate dominance tree (Node#,IDom#):161// CHECK-NEXT: (0,1)162// CHECK-NEXT: (1,7)163// CHECK-NEXT: (2,5)164// CHECK-NEXT: (3,4)165// CHECK-NEXT: (4,5)166// CHECK-NEXT: (5,6)167// CHECK-NEXT: (6,7)168// CHECK-NEXT: (7,8)169// CHECK-NEXT: (8,8)170// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):171// CHECK-NEXT: (0,0)172// CHECK-NEXT: (1,0)173// CHECK-NEXT: (2,6)174// CHECK-NEXT: (3,5)175// CHECK-NEXT: (4,3)176// CHECK-NEXT: (5,2)177// CHECK-NEXT: (6,1)178// CHECK-NEXT: (7,1)179// CHECK-NEXT: (8,7)180 181int test4(void)182{183 int y = 3;184 while(y > 0) {185 if(y < 3) {186 while(y>0)187 y ++;188 }else{189 while(y<10)190 y ++;191 }192 }193 return 0;194}195 196// <----------------------------------197// / <----------------- \198// / / \ \199// [B12 (ENTRY)] -> [B11] -> [B10]-> [B9] -> [B8] ---> [B7] -> [B6] |200// | \ \ /201// | \ -----> [B2] --------/202// | \ /203// | -> [B5] -> [B4] -> [B3]204// | \ /205// | <------------206// \207// -> [B1] -> [B0 (EXIT)]208 209// CHECK: Control dependencies (Node#,Dependency#):210// CHECK-NEXT: (2,10)211// CHECK-NEXT: (3,5)212// CHECK-NEXT: (3,9)213// CHECK-NEXT: (3,10)214// CHECK-NEXT: (4,5)215// CHECK-NEXT: (4,9)216// CHECK-NEXT: (4,10)217// CHECK-NEXT: (5,9)218// CHECK-NEXT: (5,5)219// CHECK-NEXT: (5,10)220// CHECK-NEXT: (6,8)221// CHECK-NEXT: (6,9)222// CHECK-NEXT: (6,10)223// CHECK-NEXT: (7,8)224// CHECK-NEXT: (7,9)225// CHECK-NEXT: (7,10)226// CHECK-NEXT: (8,9)227// CHECK-NEXT: (8,8)228// CHECK-NEXT: (8,10)229// CHECK-NEXT: (9,10)230// CHECK-NEXT: (10,10)231// CHECK-NEXT: Immediate dominance tree (Node#,IDom#):232// CHECK-NEXT: (0,1)233// CHECK-NEXT: (1,10)234// CHECK-NEXT: (2,9)235// CHECK-NEXT: (3,4)236// CHECK-NEXT: (4,5)237// CHECK-NEXT: (5,9)238// CHECK-NEXT: (6,7)239// CHECK-NEXT: (7,8)240// CHECK-NEXT: (8,9)241// CHECK-NEXT: (9,10)242// CHECK-NEXT: (10,11)243// CHECK-NEXT: (11,12)244// CHECK-NEXT: (12,12)245// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):246// CHECK-NEXT: (0,0)247// CHECK-NEXT: (1,0)248// CHECK-NEXT: (2,10)249// CHECK-NEXT: (3,5)250// CHECK-NEXT: (4,3)251// CHECK-NEXT: (5,2)252// CHECK-NEXT: (6,8)253// CHECK-NEXT: (7,6)254// CHECK-NEXT: (8,2)255// CHECK-NEXT: (9,2)256// CHECK-NEXT: (10,1)257// CHECK-NEXT: (11,10)258// CHECK-NEXT: (12,11)259 260int test5(void)261{262 int x,y,z,a,b,c;263 x = 1;264 y = 2;265 z = 3;266 a = 4;267 b = 5;268 c = 6;269 if ( x < 10 ) {270 if ( y < 10 ) {271 if ( z < 10 ) {272 x = 4;273 } else {274 x = 5;275 }276 a = 10;277 } else {278 x = 6;279 }280 b = 10;281 } else {282 x = 7;283 }284 c = 11;285 return 0;286}287 288// [B0 (EXIT)] <--289// \290// [B11 (ENTY)] -> [B10] -> [B9] -> [B8] -> [B7] -> [B5] -> [B3] -> [B1]291// | | | / / /292// | | V / / /293// | V [B6] --> / /294// V [B4] -----------------> /295// [B2]--------------------------------->296 297// CHECK: Control dependencies (Node#,Dependency#):298// CHECK-NEXT: (2,10)299// CHECK-NEXT: (3,10)300// CHECK-NEXT: (4,9)301// CHECK-NEXT: (4,10)302// CHECK-NEXT: (5,9)303// CHECK-NEXT: (5,10)304// CHECK-NEXT: (6,8)305// CHECK-NEXT: (6,9)306// CHECK-NEXT: (6,10)307// CHECK-NEXT: (7,8)308// CHECK-NEXT: (7,9)309// CHECK-NEXT: (7,10)310// CHECK-NEXT: (8,9)311// CHECK-NEXT: (8,10)312// CHECK-NEXT: (9,10)313// CHECK-NEXT: Immediate dominance tree (Node#,IDom#):314// CHECK-NEXT: (0,1)315// CHECK-NEXT: (1,10)316// CHECK-NEXT: (2,10)317// CHECK-NEXT: (3,9)318// CHECK-NEXT: (4,9)319// CHECK-NEXT: (5,8)320// CHECK-NEXT: (6,8)321// CHECK-NEXT: (7,8)322// CHECK-NEXT: (8,9)323// CHECK-NEXT: (9,10)324// CHECK-NEXT: (10,11)325// CHECK-NEXT: (11,11)326// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):327// CHECK-NEXT: (0,0)328// CHECK-NEXT: (1,0)329// CHECK-NEXT: (2,1)330// CHECK-NEXT: (3,1)331// CHECK-NEXT: (4,3)332// CHECK-NEXT: (5,3)333// CHECK-NEXT: (6,5)334// CHECK-NEXT: (7,5)335// CHECK-NEXT: (8,5)336// CHECK-NEXT: (9,3)337// CHECK-NEXT: (10,1)338// CHECK-NEXT: (11,10)339