clang/test/Analysis/domtest.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 %s
   6
   7 // Test the DominatorsTree implementation with various control flows
   8 int 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 //                          V
  34 //                         [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
  68 int 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 //                  /               V
  91 // [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
 120 int 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
 181 int 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
 260 int 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)