clang/test/Analysis/loop-unrolling.cpp

   1 // RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify -std=c++14 -analyzer-config exploration_strategy=unexplored_first_queue %s
   2 // RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true,exploration_strategy=dfs -verify -std=c++14 -DDFS=1 %s
   3
   4 void clang_analyzer_numTimesReached();
   5 void clang_analyzer_warnIfReached();
   6
   7 int getNum();
   8 void foo(int &);
   9
  10 int simple_unroll1() {
  11   int a[9];
  12   int k = 42;
  13   for (int i = 0; i < 9; i++) {
  14     clang_analyzer_numTimesReached(); // expected-warning {{9}}
  15     a[i] = 42;
  16   }
  17   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
  18   return 0;
  19 }
  20
  21 int simple_unroll2() {
  22   int a[9];
  23   int k = 42;
  24   int i;
  25   for (i = 0; i < 9; i++) {
  26     clang_analyzer_numTimesReached(); // expected-warning {{9}}
  27     a[i] = 42;
  28   }
  29
  30   for (int j = 0; j <= 9; ++j) {
  31     clang_analyzer_numTimesReached(); // expected-warning {{10}}
  32     a[j] = 42;
  33   }
  34
  35   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
  36   return 0;
  37 }
  38
  39 int simple_unroll3_unsigned() {
  40   int a[9];
  41   int k = 42;
  42   for (unsigned i = 0; i < 9; i++) {
  43     clang_analyzer_numTimesReached(); // expected-warning {{9}}
  44     a[i] = 42;
  45   }
  46   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
  47   return 0;
  48 }
  49
  50 int simple_unroll4_unsigned() {
  51   int a[9];
  52   int k = 42;
  53   unsigned i;
  54   for (i = (0); i < 9; i++) {
  55     clang_analyzer_numTimesReached(); // expected-warning {{9}}
  56     a[i] = 42;
  57   }
  58   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
  59   return 0;
  60 }
  61
  62 int simple_no_unroll1() {
  63   int a[9];
  64   int k = 42;
  65   for (int i = 0; i < 9; i++) {
  66     clang_analyzer_numTimesReached(); // expected-warning {{4}}
  67     a[i] = 42;
  68     foo(i);
  69   }
  70   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
  71   return 0;
  72 }
  73
  74 int simple_no_unroll2() {
  75   int a[9];
  76   int k = 42;
  77   int i;
  78   for (i = 0; i < 9; i++) {
  79     clang_analyzer_numTimesReached(); // expected-warning {{4}}
  80     a[i] = 42;
  81     i += getNum();
  82   }
  83   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
  84   return 0;
  85 }
  86
  87 int simple_no_unroll3() {
  88   int a[9];
  89   int k = 42;
  90   for (int i = 0; i < 9; i++) {
  91     clang_analyzer_numTimesReached(); // expected-warning {{4}}
  92     a[i] = 42;
  93     (void)&i;
  94   }
  95   int b = 22 / (k - 42); // no-warning
  96   return 0;
  97 }
  98
  99 int simple_no_unroll4() {
 100   int a[9];
 101   int k = 42;
 102   int i;
 103   for (i = 0; i < 9; i++) {
 104     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 105     a[i] = 42;
 106     int &j = i;
 107   }
 108   int b = 22 / (k - 42); // no-warning
 109   return 0;
 110 }
 111
 112 int simple_no_unroll5() {
 113   int a[9];
 114   int k = 42;
 115   int i;
 116   for (i = 0; i < 9; i++) {
 117     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 118     a[i] = 42;
 119     int &j{i};
 120   }
 121   int b = 22 / (k - 42); // no-warning
 122   return 0;
 123 }
 124
 125 int no_unroll_assignment() {
 126   for (int i = 0; i < 9; i++) {
 127     i = i + 1;
 128     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 129   }
 130   return 0;
 131 }
 132
 133 int no_unroll_assignment2() {
 134   for (int i = 0; i < 9; i++) {
 135     i *= 2;
 136     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 137   }
 138   return 0;
 139 }
 140
 141 int no_unroll_assignment3() {
 142   for (int i = 128; i > 0; i--) {
 143     i /= 2;
 144     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 145   }
 146   return 0;
 147 }
 148
 149 int no_unroll_assignment4() {
 150   for (int i = 0; i < 9; i++) {
 151     i -= 2;
 152     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 153   }
 154   return 0;
 155 }
 156
 157 int no_unroll_assignment5() {
 158   for (int i = 0; i < 9; i++) {
 159     i += 1;
 160     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 161   }
 162   return 0;
 163 }
 164
 165 int no_unroll_assignment6() {
 166   for (int i = 128; i > 0; i--) {
 167     i >>= 1;
 168     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 169   }
 170   return 0;
 171 }
 172
 173 int no_unroll_assignment7() {
 174   for (int i = 0; i < 512; i++) {
 175     i <<= 1;
 176     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 177   }
 178   return 0;
 179 }
 180
 181 int no_unroll_assignment8() {
 182   for (int i = 0; i < 9; i++) {
 183     i %= 8;
 184     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 185   }
 186   return 0;
 187 }
 188
 189 int no_unroll_assignment9() {
 190   for (int i = 0; i < 9; i++) {
 191     i &= 31;
 192     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 193   }
 194   return 0;
 195 }
 196
 197 int no_unroll_assignment10() {
 198   for (int i = 0; i < 9; i++) {
 199     i |= 2;
 200     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 201   }
 202   return 0;
 203 }
 204
 205 int no_unroll_assignment11() {
 206   for (int i = 0; i < 9; i++) {
 207     i ^= 2;
 208     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 209   }
 210   return 0;
 211 }
 212
 213 int make_new_branches_loop_cached() {
 214   for (int i = 0; i < 8; i++) {
 215     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 216     if (getNum()) {
 217       (void)i; // Since this Stmt does not change the State the analyzer
 218                // won't make a new execution path but reuse the earlier nodes.
 219     }
 220   }
 221   clang_analyzer_warnIfReached(); // no-warning
 222   return 0;
 223 }
 224
 225 int make_new_branches_loop_uncached() {
 226   int l = 2;
 227   for (int i = 0; i < 8; i++) {
 228     clang_analyzer_numTimesReached(); // expected-warning {{10}}
 229     if (getNum()) {
 230       ++l;
 231     }
 232   }
 233   clang_analyzer_warnIfReached(); // no-warning
 234   return 0;
 235 }
 236
 237 int make_new_branches_loop_uncached2() {
 238   int l = 2;
 239   for (int i = 0; i < 8; i++) {
 240     clang_analyzer_numTimesReached(); // expected-warning {{10}}
 241     if (getNum()) {
 242       ++l;
 243     }
 244     (void)&i; // This ensures that the loop won't be unrolled.
 245   }
 246   clang_analyzer_warnIfReached(); // no-warning
 247   return 0;
 248 }
 249
 250
 251 int escape_before_loop_no_unroll1() {
 252   int a[9];
 253   int k = 42;
 254   int i;
 255   int &j = i;
 256   for (i = 0; i < 9; i++) {
 257     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 258     a[i] = 42;
 259   }
 260   int b = 22 / (k - 42); // no-warning
 261   return 0;
 262 }
 263
 264 int escape_before_loop_no_unroll2() {
 265   int a[9];
 266   int k = 42;
 267   int i;
 268   int *p = &i;
 269   for (i = 0; i < 9; i++) {
 270     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 271     a[i] = 42;
 272   }
 273   int b = 22 / (k - 42); // no-warning
 274   return 0;
 275 }
 276
 277 int escape_before_loop_no_unroll3() {
 278   int a[9];
 279   int k = 42;
 280   int i;
 281   foo(i);
 282   for (i = 0; i < 9; i++) {
 283     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 284     a[i] = 42;
 285   }
 286   int b = 22 / (k - 42); // no-warning
 287   return 0;
 288 }
 289
 290 int nested_outer_unrolled() {
 291   int a[9];
 292   int k = 42;
 293   int j = 0;
 294   for (int i = 0; i < 9; i++) {
 295     clang_analyzer_numTimesReached(); // expected-warning {{1}}
 296     for (j = 0; j < 9; ++j) {
 297       clang_analyzer_numTimesReached(); // expected-warning {{4}}
 298       a[j] = 22;
 299       (void)&j; // ensures that the inner loop won't be unrolled
 300     }
 301     a[i] = 42;
 302   }
 303   int b = 22 / (k - 42); // no-warning
 304   return 0;
 305 }
 306
 307 int nested_inner_unrolled() {
 308   int a[9];
 309   int k = 42;
 310   int j = 0;
 311   for (int i = 0; i < getNum(); i++) {
 312     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 313     for (j = 0; j < 8; ++j) {
 314       clang_analyzer_numTimesReached(); // expected-warning {{32}}
 315       a[j] = 22;
 316     }
 317     a[i] = 42;
 318   }
 319   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
 320   return 0;
 321 }
 322
 323 int nested_both_unrolled() {
 324   int a[9];
 325   int k = 42;
 326   int j = 0;
 327   for (int i = 0; i < 7; i++) {
 328     clang_analyzer_numTimesReached(); // expected-warning {{7}}
 329     for (j = 0; j < 6; ++j) {
 330       clang_analyzer_numTimesReached(); // expected-warning {{42}}
 331       a[j] = 22;
 332     }
 333     a[i] = 42;
 334   }
 335   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
 336   return 0;
 337 }
 338
 339 int simple_known_bound_loop() {
 340   for (int i = 2; i < 12; i++) {
 341     // This function is inlined in nested_inlined_unroll1()
 342     clang_analyzer_numTimesReached(); // expected-warning {{90}}
 343   }
 344   return 0;
 345 }
 346
 347 int simple_unknown_bound_loop() {
 348   for (int i = 2; i < getNum(); i++) {
 349 #ifdef DFS
 350     clang_analyzer_numTimesReached(); // expected-warning {{16}}
 351 #else
 352     clang_analyzer_numTimesReached(); // expected-warning {{8}}
 353 #endif
 354   }
 355   return 0;
 356 }
 357
 358 int nested_inlined_unroll1() {
 359   int k;
 360   for (int i = 0; i < 9; i++) {
 361     clang_analyzer_numTimesReached(); // expected-warning {{9}}
 362     k = simple_known_bound_loop();    // no reevaluation without inlining
 363   }
 364   int a = 22 / k; // expected-warning {{Division by zero}}
 365   return 0;
 366 }
 367
 368 int nested_inlined_no_unroll1() {
 369   int k;
 370   for (int i = 0; i < 9; i++) {
 371 #ifdef DFS
 372     clang_analyzer_numTimesReached(); // expected-warning {{18}}
 373 #else
 374     clang_analyzer_numTimesReached(); // expected-warning {{14}}
 375 #endif
 376     k = simple_unknown_bound_loop();  // reevaluation without inlining, splits the state as well
 377   }
 378   int a = 22 / k; // no-warning
 379   return 0;
 380 }
 381
 382 int recursion_unroll1(bool b) {
 383   int k = 2;
 384   for (int i = 0; i < 5; i++) {
 385     clang_analyzer_numTimesReached(); // expected-warning {{13}}
 386     if (i == 0 && b)                  // Splits the state in the first iteration but the recursion
 387                                       // call will be unrolled anyway since the condition is known there.
 388       recursion_unroll1(false);
 389     clang_analyzer_numTimesReached(); // expected-warning {{14}}
 390   }
 391   int a = 22 / k; // no-warning
 392   return 0;
 393 }
 394
 395 int recursion_unroll2(bool b) {
 396   int k = 0;
 397   for (int i = 0; i < 5; i++) {
 398     clang_analyzer_numTimesReached(); // expected-warning {{9}}
 399     if (i == 0 && b)
 400       recursion_unroll2(false);
 401     clang_analyzer_numTimesReached(); // expected-warning {{9}}
 402   }
 403   int a = 22 / k; // expected-warning {{Division by zero}}
 404   return 0;
 405 }
 406
 407 int recursion_unroll3(bool b) {
 408   int k = 2;
 409   for (int i = 0; i < 5; i++) {
 410     clang_analyzer_numTimesReached(); // expected-warning {{10}}
 411     if (i == 4 && b) {
 412       recursion_unroll3(false);
 413       break;
 414     }
 415     clang_analyzer_numTimesReached(); // expected-warning {{10}}
 416   }
 417   int a = 22 / k;
 418   return 0;
 419 }
 420
 421 int recursion_unroll4(bool b) {
 422   int k = 2;
 423   for (int i = 0; i < 5; i++) {
 424     clang_analyzer_numTimesReached(); // expected-warning {{13}}
 425     if (i == 0 && b) {
 426       recursion_unroll4(false);
 427       continue;
 428     }
 429     clang_analyzer_numTimesReached(); // expected-warning {{13}}
 430   }
 431   int a = 22 / k;
 432   return 0;
 433 }
 434
 435 int loop_exit_while_empty_loop_stack() {
 436   if (getNum())
 437     for (int i = 1; i < 8; i++)
 438       ;
 439   return 0;
 440 }
 441
 442 int num_steps_on_limit() {
 443   for (int i = 0; i < 128; i++) {
 444     clang_analyzer_numTimesReached(); // expected-warning {{128}}
 445   }
 446   clang_analyzer_numTimesReached(); // expected-warning {{1}}
 447   return 0;
 448 }
 449
 450 int num_steps_over_limit1() {
 451   for (int i = 0; i < 129; i++) {
 452     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 453   }
 454   return 0;
 455 }
 456
 457 int num_steps_on_limit2() {
 458   for (int i = 0; i < 2; i++) {
 459     for (int j = 0; j < 64; j++) {
 460       clang_analyzer_numTimesReached(); // expected-warning {{128}}
 461     }
 462   }
 463   return 0;
 464 }
 465
 466 int num_steps_over_limit2() {
 467   for (int i = 0; i < 2; i++) {
 468     clang_analyzer_numTimesReached(); // expected-warning {{1}}
 469     for (int j = 0; j <= 64; j++) {
 470       clang_analyzer_numTimesReached(); // expected-warning {{4}}
 471     }
 472   }
 473   return 0;
 474 }
 475
 476 int num_steps_on_limit3() {
 477   for (int i = 0; i < getNum(); i++) {
 478     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 479     for (int j = 0; j < 32; j++) {
 480       clang_analyzer_numTimesReached(); // expected-warning {{128}}
 481     }
 482   }
 483   return 0;
 484 }
 485
 486 int num_steps_over_limit3() {
 487   for (int i = 0; i < getNum(); i++) {
 488     clang_analyzer_numTimesReached(); // expected-warning {{1}}
 489     for (int j = 0; j < 33; j++) {
 490       clang_analyzer_numTimesReached(); // expected-warning {{4}}
 491     }
 492   }
 493   return 0;
 494 }
 495
 496
 497 void pr34943() {
 498   for (int i = 0; i < 6L; ++i) {
 499     clang_analyzer_numTimesReached(); // expected-warning {{6}}
 500   }
 501 }
 502
 503 void parm_by_value_as_loop_counter(int i) {
 504   for (i = 0; i < 10; ++i) {
 505     clang_analyzer_numTimesReached(); // expected-warning {{10}}
 506   }
 507 }
 508
 509 void parm_by_ref_as_loop_counter(int &i) {
 510   for (i = 0; i < 10; ++i) {
 511     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 512   }
 513 }
 514
 515 void capture_by_value_as_loop_counter() {
 516   int out = 0;
 517   auto l = [i = out]() mutable {
 518     for (i = 0; i < 10; ++i) {
 519       clang_analyzer_numTimesReached(); // expected-warning {{10}}
 520     }
 521   };
 522 }
 523
 524 void capture_by_ref_as_loop_counter() {
 525   int out = 0;
 526   auto l = [&i = out]() {
 527     for (i = 0; i < 10; ++i) {
 528       clang_analyzer_numTimesReached(); // expected-warning {{4}}
 529     }
 530   };
 531 }
 532
 533 void capture_implicitly_by_value_as_loop_counter() {
 534   int i = 0;
 535   auto l = [=]() mutable {
 536     for (i = 0; i < 10; ++i) {
 537       clang_analyzer_numTimesReached(); // expected-warning {{10}}
 538     }
 539   };
 540 }
 541
 542 void capture_implicitly_by_ref_as_loop_counter() {
 543   int i = 0;
 544   auto l = [&]() mutable {
 545     for (i = 0; i < 10; ++i) {
 546       clang_analyzer_numTimesReached(); // expected-warning {{4}}
 547     }
 548   };
 549 }