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