601 lines · cpp
1// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify=expected,default -std=c++17 -analyzer-config exploration_strategy=unexplored_first_queue %s2// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true,exploration_strategy=dfs -verify=expected,dfs -std=c++17 %s3 4void clang_analyzer_numTimesReached();5void clang_analyzer_warnIfReached();6 7int getNum();8void foo(int &);9 10int 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 21int 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 39int 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 50int 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 62int 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 {{2}}67 a[i] = 42;68 foo(i);69 }70 int b = 22 / (k - 42); // expected-warning {{Division by zero}}71 return 0;72}73 74int 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 {{2}}80 a[i] = 42;81 i += getNum();82 }83 int b = 22 / (k - 42); // expected-warning {{Division by zero}}84 return 0;85}86 87int 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-warning96 return 0;97}98 99int 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-warning109 return 0;110}111 112int 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-warning122 return 0;123}124 125int 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 133int 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 141int 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 149int 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 157int 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 165int 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 173int 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 181int 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 189int 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 197int 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 205int 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 213int 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 analyzer218 // won't make a new execution path but reuse the earlier nodes.219 }220 }221 clang_analyzer_warnIfReached(); // no-warning222 return 0;223}224 225int 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-warning234 return 0;235}236 237int 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-warning247 return 0;248}249 250 251int 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-warning261 return 0;262}263 264int 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-warning274 return 0;275}276 277int 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-warning287 return 0;288}289 290int 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 unrolled300 }301 a[i] = 42;302 }303 int b = 22 / (k - 42); // no-warning304 return 0;305}306 307int 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 {{2}}313 for (j = 0; j < 8; ++j) {314 clang_analyzer_numTimesReached(); // expected-warning {{16}}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 323int 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 339int simple_known_bound_loop() {340 // Iteration count visible: can be unrolled and fully executed.341 for (int i = 2; i < 12; i++) {342 // This function is inlined in nested_inlined_unroll1()343 clang_analyzer_numTimesReached(); // expected-warning {{90}}344 }345 return 0;346}347 348int simple_unknown_bound_loop() {349 // Iteration count unknown: unrolling won't happen and the execution will be350 // split two times:351 // (1) split between skipped loop (immediate exit) and entering the loop352 // (2) split between exit after 1 iteration and entering the second iteration353 // After these there is no third state split because the "don't assume third354 // iteration" logic in `ExprEngine::processBranch` prevents it; but the355 // `legacy-inlining-prevention` logic will put this function onto the list of356 // functions that may not be inlined in the future.357 // The exploration strategy apparently influences the number of times this358 // function can be inlined before it's placed on the "don't inline" list.359 for (int i = 2; i < getNum(); i++) {360 clang_analyzer_numTimesReached(); // default-warning {{4}} dfs-warning {{8}}361 }362 return 0;363}364 365int nested_inlined_unroll1() {366 // Here the analyzer can unroll and fully execute both the outer loop and the367 // inner loop within simple_known_bound_loop().368 int k;369 for (int i = 0; i < 9; i++) {370 clang_analyzer_numTimesReached(); // expected-warning {{9}}371 k = simple_known_bound_loop();372 }373 int a = 22 / k; // expected-warning {{Division by zero}}374 return 0;375}376 377int nested_inlined_no_unroll1() {378 // Here no unrolling happens and we only run `analyzer-max-loop` (= 4)379 // iterations of the loop within this function, but some state splits happen380 // in `simple_unknown_bound_loop()` calls.381 int k;382 for (int i = 0; i < 40; i++) {383 clang_analyzer_numTimesReached(); // default-warning {{9}} dfs-warning {{12}}384 k = simple_unknown_bound_loop(); 385 }386 int a = 22 / k; // no-warning387 return 0;388}389 390int recursion_unroll1(bool b) {391 int k = 2;392 for (int i = 0; i < 5; i++) {393 clang_analyzer_numTimesReached(); // expected-warning {{13}}394 if (i == 0 && b) // Splits the state in the first iteration but the recursion395 // call will be unrolled anyway since the condition is known there.396 recursion_unroll1(false);397 clang_analyzer_numTimesReached(); // expected-warning {{14}}398 }399 int a = 22 / k; // no-warning400 return 0;401}402 403int recursion_unroll2(bool b) {404 int k = 0;405 for (int i = 0; i < 5; i++) {406 clang_analyzer_numTimesReached(); // expected-warning {{9}}407 if (i == 0 && b)408 recursion_unroll2(false);409 clang_analyzer_numTimesReached(); // expected-warning {{9}}410 }411 int a = 22 / k; // expected-warning {{Division by zero}}412 return 0;413}414 415int recursion_unroll3(bool b) {416 int k = 2;417 for (int i = 0; i < 5; i++) {418 clang_analyzer_numTimesReached(); // expected-warning {{10}}419 if (i == 4 && b) {420 recursion_unroll3(false);421 break;422 }423 clang_analyzer_numTimesReached(); // expected-warning {{10}}424 }425 int a = 22 / k;426 return 0;427}428 429int recursion_unroll4(bool b) {430 int k = 2;431 for (int i = 0; i < 5; i++) {432 clang_analyzer_numTimesReached(); // expected-warning {{13}}433 if (i == 0 && b) {434 recursion_unroll4(false);435 continue;436 }437 clang_analyzer_numTimesReached(); // expected-warning {{13}}438 }439 int a = 22 / k;440 return 0;441}442 443int loop_exit_while_empty_loop_stack() {444 if (getNum())445 for (int i = 1; i < 8; i++)446 ;447 return 0;448}449 450int num_steps_on_limit() {451 for (int i = 0; i < 128; i++) {452 clang_analyzer_numTimesReached(); // expected-warning {{128}}453 }454 clang_analyzer_numTimesReached(); // expected-warning {{1}}455 return 0;456}457 458int num_steps_over_limit1() {459 for (int i = 0; i < 129; i++) {460 clang_analyzer_numTimesReached(); // expected-warning {{4}}461 }462 return 0;463}464 465int num_steps_on_limit2() {466 for (int i = 0; i < 2; i++) {467 for (int j = 0; j < 64; j++) {468 clang_analyzer_numTimesReached(); // expected-warning {{128}}469 }470 }471 return 0;472}473 474int num_steps_over_limit2() {475 for (int i = 0; i < 2; i++) {476 clang_analyzer_numTimesReached(); // expected-warning {{1}}477 for (int j = 0; j <= 64; j++) {478 clang_analyzer_numTimesReached(); // expected-warning {{4}}479 }480 }481 return 0;482}483 484int num_steps_on_limit3() {485 for (int i = 0; i < getNum(); i++) {486 clang_analyzer_numTimesReached(); // expected-warning {{2}}487 for (int j = 0; j < 32; j++) {488 // Here the loop unrollig logic calculates with four potential iterations489 // in the outer loop where it cannot determine the iteration count in490 // advance; but after two loops the analyzer conservatively assumes that491 // the (still opaque) loop condition is false.492 clang_analyzer_numTimesReached(); // expected-warning {{64}}493 }494 }495 return 0;496}497 498int num_steps_over_limit3() {499 for (int i = 0; i < getNum(); i++) {500 clang_analyzer_numTimesReached(); // expected-warning {{1}}501 for (int j = 0; j < 33; j++) {502 clang_analyzer_numTimesReached(); // expected-warning {{4}}503 }504 }505 return 0;506}507 508int num_steps_on_limit4() {509 for (int i = 0; i < 4; i++) {510 clang_analyzer_numTimesReached(); // expected-warning {{4}}511 for (int j = 0; j < 32; j++) {512 clang_analyzer_numTimesReached(); // expected-warning {{128}}513 }514 }515 return 0;516}517 518void pr34943() {519 for (int i = 0; i < 6L; ++i) {520 clang_analyzer_numTimesReached(); // expected-warning {{6}}521 }522}523 524void parm_by_value_as_loop_counter(int i) {525 for (i = 0; i < 10; ++i) {526 clang_analyzer_numTimesReached(); // expected-warning {{10}}527 }528}529 530void parm_by_ref_as_loop_counter(int &i) {531 for (i = 0; i < 10; ++i) {532 clang_analyzer_numTimesReached(); // expected-warning {{4}}533 }534}535 536void capture_by_value_as_loop_counter() {537 int out = 0;538 auto l = [i = out]() mutable {539 for (i = 0; i < 10; ++i) {540 clang_analyzer_numTimesReached(); // expected-warning {{10}}541 }542 };543}544 545void capture_by_ref_as_loop_counter() {546 int out = 0;547 auto l = [&i = out]() {548 for (i = 0; i < 10; ++i) {549 clang_analyzer_numTimesReached(); // expected-warning {{4}}550 }551 };552}553 554void capture_implicitly_by_value_as_loop_counter() {555 int i = 0;556 auto l = [=]() mutable {557 for (i = 0; i < 10; ++i) {558 clang_analyzer_numTimesReached(); // expected-warning {{10}}559 }560 };561}562 563void capture_implicitly_by_ref_as_loop_counter() {564 int i = 0;565 auto l = [&]() mutable {566 for (i = 0; i < 10; ++i) {567 clang_analyzer_numTimesReached(); // expected-warning {{4}}568 }569 };570}571 572 573void test_escaping_on_var_before_switch_case_no_crash(int c) {574 // https://github.com/llvm/llvm-project/issues/68819575 switch (c) {576 int i; // no-crash: The declaration of `i` is found here.577 case 0: {578 for (i = 0; i < 16; i++) {}579 break;580 }581 }582}583 584template <int Val> struct Integer {585 static constexpr int value = Val;586};587 588void complicated_compile_time_upper_bound() {589 static_assert((sizeof(char) * Integer<4>::value + 3) == 7);590 for (int i = 0; i < (sizeof(char) * Integer<4>::value + (((3)))); ++i) {591 clang_analyzer_numTimesReached(); // expected-warning {{7}}592 }593}594 595void complicated_compile_time_upper_bound_indirect() {596 using Seven = Integer<(sizeof(char) * Integer<4>::value + 3)>;597 for (int i = 0; i < ((Seven::value)); ++i) {598 clang_analyzer_numTimesReached(); // expected-warning {{7}}599 }600}601