201 lines · c
1// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify=expected,default %s2// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config inline-functions-with-ambiguous-loops=true -verify=expected,enabled %s3 4// This file tests some heuristics in the engine that put functions on a5// "do not inline" list if their analyisis reaches the `analyzer-max-loop`6// limit (by default 4 iterations) in a loop. This was almost surely intended7// as memoization optimization for the "retry without inlining" fallback (if we8// had to retry once, next time don't even try inlining), but aggressively9// oversteps the "natural" scope: reaching 4 iterations on _one particular_10// execution path does not imply that each path would need "retry without11// inlining" especially if a different call receives different arguments.12//13// This heuristic significantly affects the scope/depth of the analysis (and14// therefore the execution time) because without this limitation on the15// inlining significantly more entry points would be able to exhaust their16// `max-nodes` quota. (Trivial thin wrappers around big complex functions are17// common in many projects.)18//19// Unfortunately, this arbitrary heuristic strongly relies on the current loop20// handling model and its many limitations, so improvements in loop handling21// can cause surprising slowdowns by reducing the "do not inline" blacklist.22// In the tests "FIXME-BUT-NEEDED" comments mark "problematic" (aka buggy)23// analyzer behavior which cannot be fixed without also improving the24// heuristics for (not) inlining large functions.25 26 int getNum(void); // Get an unknown symbolic number.27 28void clang_analyzer_dump(int arg);29 30//-----------------------------------------------------------------------------31// Simple case: inlined function never reaches `analyzer-max-loop`, so it is32// always inlined.33 34int inner_simple(int callIdx) {35 clang_analyzer_dump(callIdx); // expected-warning {{1 S32}}36 // expected-warning@-1 {{2 S32}}37 return 42;38}39 40int outer_simple(void) {41 int x = inner_simple(1);42 int y = inner_simple(2);43 return 53 / (x - y); // expected-warning {{Division by zero}}44}45 46//-----------------------------------------------------------------------------47// Inlined function always reaches `analyzer-max-loop`, which stops the48// analysis on that path and puts the function on the "do not inline" list.49 50int inner_fixed_loop_1(int callIdx) {51 int i;52 clang_analyzer_dump(callIdx); // expected-warning {{1 S32}}53 for (i = 0; i < 10; i++); // FIXME-BUT-NEEDED: This stops the analysis.54 clang_analyzer_dump(callIdx); // no-warning55 return 42;56}57 58int outer_fixed_loop_1(void) {59 int x = inner_fixed_loop_1(1);60 int y = inner_fixed_loop_1(2);61 62 // FIXME-BUT-NEEDED: The analysis doesn't reach this zero division.63 return 53 / (x - y); // no-warning64}65 66//-----------------------------------------------------------------------------67// Inlined function always reaches `analyzer-max-loop`; inlining is prevented68// even for different entry points.69// NOTE: the analyzer happens to analyze the entry points in a reversed order,70// so `outer_2_fixed_loop_2` is analyzed first and it will be the one which is71// able to inline the inner function.72 73int inner_fixed_loop_2(int callIdx) {74 // Identical copy of inner_fixed_loop_1.75 int i;76 clang_analyzer_dump(callIdx); // expected-warning {{2 S32}}77 for (i = 0; i < 10; i++); // FIXME-BUT-NEEDED: This stops the analysis.78 clang_analyzer_dump(callIdx); // no-warning79 return 42;80}81 82int outer_1_fixed_loop_2(void) {83 return inner_fixed_loop_2(1);84}85 86int outer_2_fixed_loop_2(void) {87 return inner_fixed_loop_2(2);88}89 90//-----------------------------------------------------------------------------91// Inlined function reaches `analyzer-max-loop` only in its second call. The92// function is inlined twice but the second call doesn't finish and ends up93// being conservatively evaluated.94 95int inner_parametrized_loop_1(int count) {96 int i;97 clang_analyzer_dump(count); // expected-warning {{2 S32}}98 // expected-warning@-1 {{10 S32}}99 for (i = 0; i < count; i++);100 // FIXME-BUT-NEEDED: This loop stops the analysis when count >=4.101 clang_analyzer_dump(count); // expected-warning {{2 S32}}102 return 42;103}104 105int outer_parametrized_loop_1(void) {106 int x = inner_parametrized_loop_1(2);107 int y = inner_parametrized_loop_1(10);108 109 // FIXME-BUT-NEEDED: The analysis doesn't reach this zero division.110 return 53 / (x - y); // no-warning111}112 113//-----------------------------------------------------------------------------114// Inlined function reaches `analyzer-max-loop` on its first call, so the115// second call isn't inlined (although it could be fully evaluated).116 117int inner_parametrized_loop_2(int count) {118 // Identical copy of inner_parametrized_loop_1.119 int i;120 clang_analyzer_dump(count); // expected-warning {{10 S32}}121 for (i = 0; i < count; i++);122 // FIXME-BUT-NEEDED: This loop stops the analysis when count >=4.123 clang_analyzer_dump(count); // no-warning124 return 42;125}126 127int outer_parametrized_loop_2(void) {128 int y = inner_parametrized_loop_2(10);129 int x = inner_parametrized_loop_2(2);130 131 // FIXME-BUT-NEEDED: The analysis doesn't reach this zero division.132 return 53 / (x - y); // no-warning133}134 135//-----------------------------------------------------------------------------136// Inlined function may or may not reach `analyzer-max-loop` depending on an137// ambiguous check before the loop. This is very similar to the "fixed loop"138// cases: the function is placed on the "don't inline" list when any execution139// path reaches `analyzer-max-loop` (even if other execution paths reach the140// end of the function).141// NOTE: This is tested with two separate entry points to ensure that one142// inlined call is fully evaluated before we try to inline the other call.143// NOTE: the analyzer happens to analyze the entry points in a reversed order,144// so `outer_2_conditional_loop` is analyzed first and it will be the one which145// is able to inline the inner function.146 147int inner_conditional_loop(int callIdx) {148 int i;149 clang_analyzer_dump(callIdx); // expected-warning {{2 S32}}150 if (getNum() == 777) {151 for (i = 0; i < 10; i++);152 }153 clang_analyzer_dump(callIdx); // expected-warning {{2 S32}}154 return 42;155}156 157int outer_1_conditional_loop(void) {158 return inner_conditional_loop(1);159}160 161int outer_2_conditional_loop(void) {162 return inner_conditional_loop(2);163}164 165//-----------------------------------------------------------------------------166// Inlined function executes an ambiguous loop that may or may not reach167// `analyzer-max-loop`. Historically, before the "don't assume third iteration"168// commit (bb27d5e5c6b194a1440b8ac4e5ace68d0ee2a849) this worked like the169// `conditional_loop` cases: the analyzer was able to find a path reaching170// `analyzer-max-loop` so inlining was disabled. After that commit the analyzer171// does not _assume_ a third (or later) iteration (i.e. does not enter those172// iterations if the loop condition is an unknown value), so e.g. this test173// function does not reach `analyzer-max-loop` iterations and the inlining is174// not disabled.175// Unfortunately this change significantly increased the workload and176// runtime of the analyzer (more entry points used up their budget), so the177// option `inline-functions-with-ambiguous-loops` was introduced and disabled178// by default to suppress the inlining in situations where the "don't assume179// third iteration" logic activates.180// NOTE: This is tested with two separate entry points to ensure that one181// inlined call is fully evaluated before we try to inline the other call.182// NOTE: the analyzer happens to analyze the entry points in a reversed order,183// so `outer_2_ambiguous_loop` is analyzed first and it will be the one which184// is able to inline the inner function.185 186int inner_ambiguous_loop(int callIdx) {187 int i;188 clang_analyzer_dump(callIdx); // default-warning {{2 S32}}189 // enabled-warning@-1 {{1 S32}}190 // enabled-warning@-2 {{2 S32}}191 for (i = 0; i < getNum(); i++);192 return i;193}194 195int outer_1_ambiguous_loop(void) {196 return inner_ambiguous_loop(1);197}198int outer_2_ambiguous_loop(void) {199 return inner_ambiguous_loop(2);200}201