bits: move is_loop_iterator() earlier
[smatch.git] / smatch_bits.c
blob21aa0775b44f54dcdfcdda74344cce0c2de15dae
1 /*
2 * Copyright (C) 2015 Oracle.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
19 * This is to track when variables are masked away.
23 #include "smatch.h"
24 #include "smatch_extra.h"
25 #include "smatch_slist.h"
27 static int my_id;
29 static const struct bit_info unknown_bit_info = {
30 .possible = -1ULL,
33 ALLOCATOR(bit_info, "bit data");
34 static struct bit_info *alloc_bit_info(unsigned long long set, unsigned long long possible)
36 struct bit_info *bit_info = __alloc_bit_info(0);
38 bit_info->set = set;
39 bit_info->possible = possible;
41 return bit_info;
44 static struct smatch_state *alloc_bstate(unsigned long long set, unsigned long long possible)
46 struct smatch_state *state;
47 char buf[64];
49 state = __alloc_smatch_state(0);
50 snprintf(buf, sizeof(buf), "0x%llx + 0x%llx", set, possible);
51 state->name = alloc_sname(buf);
52 state->data = alloc_bit_info(set, possible);
54 return state;
57 struct bit_info *rl_to_binfo(struct range_list *rl)
59 struct bit_info *ret = __alloc_bit_info(0);
60 sval_t sval;
62 if (rl_to_sval(rl, &sval)) {
63 ret->set = sval.uvalue;
64 ret->possible = sval.uvalue;
66 return ret;
69 ret->set = 0;
70 ret->possible = sval_fls_mask(rl_max(rl));
71 // FIXME: what about negatives?
73 return ret;
76 static int is_unknown_binfo(struct symbol *type, struct bit_info *binfo)
78 if (!type)
79 type = &ullong_ctype;
81 if (binfo->set != 0)
82 return 0;
83 if (binfo->possible < (-1ULL >> (64 - type_bits(type))))
84 return 0;
86 return 1;
89 static struct smatch_state *unmatched_state(struct sm_state *sm)
91 struct smatch_state *estate;
92 struct symbol *type;
93 unsigned long long possible;
94 struct bit_info *p;
96 estate = get_state(SMATCH_EXTRA, sm->name, sm->sym);
97 if (estate_rl(estate)) {
98 p = rl_to_binfo(estate_rl(estate));
99 return alloc_bstate(p->set, p->possible);
102 type = estate_type(estate);
103 if (!type)
104 return alloc_bstate(0, -1ULL);
106 if (type_bits(type) == 64)
107 possible = -1ULL;
108 else
109 possible = (1ULL << type_bits(type)) - 1;
111 return alloc_bstate(0, possible);
114 static bool is_loop_iterator(struct expression *expr)
116 struct statement *pre_stmt, *loop_stmt;
118 pre_stmt = expr_get_parent_stmt(expr);
119 if (!pre_stmt || pre_stmt->type != STMT_EXPRESSION)
120 return false;
122 loop_stmt = stmt_get_parent_stmt(pre_stmt);
123 if (!loop_stmt || loop_stmt->type != STMT_ITERATOR)
124 return false;
125 if (loop_stmt->iterator_pre_statement != pre_stmt)
126 return false;
128 return true;
131 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
133 // FIXME: we really need to store the type
135 set_state(my_id, sm->name, sm->sym, alloc_bstate(0, -1ULL));
138 static int binfo_equiv(struct bit_info *one, struct bit_info *two)
140 if (one->set == two->set &&
141 one->possible == two->possible)
142 return 1;
143 return 0;
146 static struct smatch_state *merge_bstates(struct smatch_state *one_state, struct smatch_state *two_state)
148 struct bit_info *one, *two;
150 one = one_state->data;
151 two = two_state->data;
153 if (binfo_equiv(one, two))
154 return one_state;
156 return alloc_bstate(one->set & two->set, one->possible | two->possible);
160 * The combine_bit_info() takes two bit_infos and takes creates the most
161 * accurate picture we can assuming both are true. Or it returns unknown if
162 * the information is logically impossible.
164 * Which means that it takes the | of the ->set bits and the & of the possibly
165 * set bits, which is the opposite of what merge_bstates() does.
168 static struct bit_info *combine_bit_info(struct bit_info *one, struct bit_info *two)
170 struct bit_info *ret = __alloc_bit_info(0);
172 if ((one->set & two->possible) != one->set)
173 return alloc_bit_info(0, -1ULL);
174 if ((two->set & one->possible) != two->set)
175 return alloc_bit_info(0, -1ULL);
177 ret->set = one->set | two->set;
178 ret->possible = one->possible & two->possible;
180 return ret;
183 static struct bit_info *binfo_AND(struct bit_info *left, struct bit_info *right)
185 unsigned long long set = 0;
186 unsigned long long possible = -1ULL;
188 if (!left && !right) {
189 /* nothing */
190 } else if (!left) {
191 possible = right->possible;
192 } else if (!right) {
193 possible = left->possible;
194 } else {
195 set = left->set & right->set;
196 possible = left->possible & right->possible;
199 return alloc_bit_info(set, possible);
202 static struct bit_info *binfo_OR(struct bit_info *left, struct bit_info *right)
204 unsigned long long set = 0;
205 unsigned long long possible = -1ULL;
207 if (!left && !right) {
208 /* nothing */
209 } else if (!left) {
210 set = right->set;
211 } else if (!right) {
212 set = left->set;
213 } else {
214 set = left->set | right->set;
215 possible = left->possible | right->possible;
218 return alloc_bit_info(set, possible);
221 struct bit_info *get_bit_info(struct expression *expr)
223 struct range_list *rl;
224 struct smatch_state *bstate;
225 struct bit_info tmp;
226 struct bit_info *extra_info;
227 struct bit_info *bit_info;
228 sval_t known;
230 expr = strip_parens(expr);
232 if (get_implied_value(expr, &known))
233 return alloc_bit_info(known.value, known.value);
235 if (expr->type == EXPR_BINOP) {
236 if (expr->op == '&')
237 return binfo_AND(get_bit_info(expr->left),
238 get_bit_info(expr->right));
239 if (expr->op == '|')
240 return binfo_OR(get_bit_info(expr->left),
241 get_bit_info(expr->right));
244 if (get_implied_rl(expr, &rl))
245 extra_info = rl_to_binfo(rl);
246 else {
247 struct symbol *type;
249 tmp = unknown_bit_info;
250 extra_info = &tmp;
252 type = get_type(expr);
253 if (!type)
254 type = &ullong_ctype;
255 if (type_bits(type) == 64)
256 extra_info->possible = -1ULL;
257 else
258 extra_info->possible = (1ULL << type_bits(type)) - 1;
261 bstate = get_state_expr(my_id, expr);
262 if (bstate)
263 bit_info = bstate->data;
264 else
265 bit_info = (struct bit_info *)&unknown_bit_info;
267 return combine_bit_info(extra_info, bit_info);
270 static int is_single_bit(sval_t sval)
272 int i;
273 int count = 0;
275 for (i = 0; i < 64; i++) {
276 if (sval.uvalue & 1ULL << i &&
277 count++)
278 return 0;
280 if (count == 1)
281 return 1;
282 return 0;
285 static void match_compare(struct expression *expr)
287 sval_t val;
289 if (expr->type != EXPR_COMPARE)
290 return;
291 if (expr->op != SPECIAL_EQUAL &&
292 expr->op != SPECIAL_NOTEQUAL)
293 return;
295 if (!get_implied_value(expr->right, &val))
296 return;
298 set_true_false_states_expr(my_id, expr->left,
299 (expr->op == SPECIAL_EQUAL) ? alloc_bstate(val.uvalue, val.uvalue) : NULL,
300 (expr->op == SPECIAL_EQUAL) ? NULL : alloc_bstate(val.uvalue, val.uvalue));
303 static void match_assign(struct expression *expr)
305 struct bit_info *binfo;
307 if (expr->op != '=')
308 return;
309 if (__in_fake_assign)
310 return;
311 if (is_loop_iterator(expr))
312 return;
314 binfo = get_bit_info(expr->right);
315 if (!binfo)
316 return;
317 if (is_unknown_binfo(get_type(expr->left), binfo))
318 return;
319 set_state_expr(my_id, expr->left, alloc_bstate(binfo->set, binfo->possible));
322 static void match_condition(struct expression *expr)
324 struct bit_info *orig;
325 struct bit_info true_info;
326 struct bit_info false_info;
327 sval_t right;
329 if (expr->type != EXPR_BINOP ||
330 expr->op != '&')
331 return;
333 if (!get_value(expr->right, &right))
334 return;
336 orig = get_bit_info(expr->left);
337 true_info = *orig;
338 false_info = *orig;
340 if (right.uvalue == 0 || is_single_bit(right))
341 true_info.set &= right.uvalue;
343 true_info.possible &= right.uvalue;
344 false_info.possible &= ~right.uvalue;
346 set_true_false_states_expr(my_id, expr->left,
347 alloc_bstate(true_info.set, true_info.possible),
348 alloc_bstate(false_info.set, false_info.possible));
351 static void match_call_info(struct expression *expr)
353 struct bit_info *binfo, *rl_binfo;
354 struct expression *arg;
355 struct range_list *rl;
356 char buf[64];
357 int i;
359 i = -1;
360 FOR_EACH_PTR(expr->args, arg) {
361 i++;
362 binfo = get_bit_info(arg);
363 if (!binfo)
364 continue;
365 if (is_unknown_binfo(get_type(arg), binfo))
366 continue;
367 if (get_implied_rl(arg, &rl)) {
368 rl_binfo = rl_to_binfo(rl);
369 if (binfo_equiv(rl_binfo, binfo))
370 continue;
372 // If is just non-negative continue
373 // If ->set == ->possible continue
374 snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
375 sql_insert_caller_info(expr, BIT_INFO, i, "$", buf);
376 } END_FOR_EACH_PTR(arg);
379 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
381 struct bit_info *binfo = sm->state->data;
382 struct smatch_state *estate;
383 struct bit_info *implied_binfo;
384 char buf[64];
386 if (!binfo)
387 return;
389 /* This means it can only be one value, so it's handled by smatch_extra. */
390 if (binfo->set == binfo->possible)
391 return;
393 estate = get_state(SMATCH_EXTRA, sm->name, sm->sym);
394 if (is_unknown_binfo(estate_type(estate), binfo))
395 return;
397 if (estate_rl(estate)) {
398 sval_t sval;
400 if (estate_get_single_value(estate, &sval))
401 return;
403 implied_binfo = rl_to_binfo(estate_rl(estate));
404 if (binfo_equiv(implied_binfo, binfo))
405 return;
408 snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
409 sql_insert_caller_info(call, BIT_INFO, param, printed_name, buf);
412 static void set_param_bits(const char *name, struct symbol *sym, char *key, char *value)
414 char fullname[256];
415 unsigned long long set, possible;
417 if (strcmp(key, "*$") == 0)
418 snprintf(fullname, sizeof(fullname), "*%s", name);
419 else if (strncmp(key, "$", 1) == 0)
420 snprintf(fullname, 256, "%s%s", name, key + 1);
421 else
422 return;
424 set = strtoull(value, &value, 16);
425 if (*value != ',')
426 return;
427 value++;
428 possible = strtoull(value, &value, 16);
430 set_state(my_id, fullname, sym, alloc_bstate(set, possible));
433 void register_bits(int id)
435 my_id = id;
437 set_dynamic_states(my_id);
439 add_unmatched_state_hook(my_id, &unmatched_state);
440 add_merge_hook(my_id, &merge_bstates);
442 add_hook(&match_condition, CONDITION_HOOK);
443 add_hook(&match_compare, CONDITION_HOOK);
444 add_hook(&match_assign, ASSIGNMENT_HOOK);
445 add_modification_hook(my_id, &match_modify);
447 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
448 add_member_info_callback(my_id, struct_member_callback);
449 select_caller_info_hook(set_param_bits, BIT_INFO);