2 * sparse/smatch_conditions.c
4 * Copyright (C) 2006,2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
11 * The simplest type of condition is
14 * The next simplest kind of conditions is
16 * In that case 'a' is true when we get to 'b' and both are true
19 * Or's are a little more complicated.
21 * We know 'a' is not true when we get to 'b' but it may be true
24 * If we mix and's and or's that's even more complicated.
25 * if (a && b && c || a && d) { d ;
26 * 'a' is true when we evaluate 'b', and 'd'.
27 * 'b' is true when we evaluate 'c' but otherwise we don't.
29 * The other thing that complicates matters is if we negate
32 * Smatch has passes the un-negated version to the client and flip
33 * the true and false values internally. This makes it easier
36 * And negations can be part of a compound.
37 * if (a && !(b || c)) { d;
38 * In that situation we multiply the negative through to simplify
39 * stuff so that we can remove the parens like this:
40 * if (a && !b && !c) { d;
42 * One other thing is that:
44 * that's basically the same as testing for just 'a' and we simplify
45 * comparisons with zero before passing it to the script.
50 #include "smatch_slist.h"
51 #include "smatch_extra.h"
52 #include "smatch_expression_stacks.h"
54 extern int __expr_stmt_count
;
56 static void split_conditions(struct expression
*expr
);
58 static int is_logical_and(struct expression
*expr
)
60 if (expr
->op
== SPECIAL_LOGICAL_AND
)
65 static int handle_zero_comparisons(struct expression
*expr
)
67 struct expression
*tmp
= NULL
;
69 // if left is zero or right is zero
70 if (is_zero(expr
->left
))
72 else if (is_zero(expr
->right
))
77 // "if (foo != 0)" is the same as "if (foo)"
78 if (expr
->op
== SPECIAL_NOTEQUAL
) {
79 split_conditions(tmp
);
83 // "if (foo == 0)" is the same as "if (!foo)"
84 if (expr
->op
== SPECIAL_EQUAL
) {
85 split_conditions(tmp
);
86 __negate_cond_stacks();
94 * This function is for handling calls to likely/unlikely
97 static int ignore_builtin_expect(struct expression
*expr
)
99 if (sym_name_is("__builtin_expect", expr
->fn
)) {
100 split_conditions(first_ptr_list((struct ptr_list
*) expr
->args
));
107 * handle_compound_stmt() is for: foo = ({blah; blah; blah; 1})
110 static void handle_compound_stmt(struct statement
*stmt
)
112 struct expression
*expr
= NULL
;
113 struct statement
*last
;
116 last
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
117 if (last
->type
!= STMT_EXPRESSION
)
120 expr
= last
->expression
;
122 FOR_EACH_PTR(stmt
->stmts
, s
) {
125 } END_FOR_EACH_PTR(s
);
126 split_conditions(expr
);
130 static int handle_preop(struct expression
*expr
)
132 struct statement
*stmt
;
134 if (expr
->op
== '!') {
135 split_conditions(expr
->unop
);
136 __negate_cond_stacks();
139 stmt
= get_expression_statement(expr
);
141 handle_compound_stmt(stmt
);
147 static void handle_logical(struct expression
*expr
)
150 * If we come to an "and" expr then:
151 * We split the left side.
152 * We keep all the current states.
153 * We split the right side.
154 * We keep all the states from both true sides.
156 * If it's an "or" expr then:
157 * We save the current slist.
158 * We split the left side.
159 * We use the false states for the right side.
160 * We split the right side.
161 * We save all the states that are the same on both sides.
164 split_conditions(expr
->left
);
165 __process_post_op_stack();
167 if (!is_logical_and(expr
))
168 __use_cond_false_states();
170 __push_cond_stacks();
172 __save_pre_cond_states();
173 split_conditions(expr
->right
);
174 __process_post_op_stack();
175 __discard_pre_cond_states();
177 if (is_logical_and(expr
))
182 __use_cond_true_states();
185 static struct state_list
*combine(struct state_list
*orig
, struct state_list
*fake
,
186 struct state_list
*new)
188 struct state_list
*ret
= NULL
;
190 overwrite_slist(orig
, &ret
);
191 overwrite_slist(fake
, &ret
);
192 overwrite_slist(new, &ret
);
200 * if ((aaa()?bbb():ccc())) { ...
202 * This is almost the same as:
203 * if ((aaa() && bbb()) || (!aaa() && ccc())) { ...
205 * It's a bit complicated because we shouldn't pass aaa()
206 * to the clients more than once.
209 static void handle_select(struct expression
*expr
)
211 struct state_list
*a_T
= NULL
;
212 struct state_list
*a_F
= NULL
;
213 struct state_list
*a_T_b_T
= NULL
;
214 struct state_list
*a_T_b_F
= NULL
;
215 struct state_list
*a_T_b_fake
= NULL
;
216 struct state_list
*a_F_c_T
= NULL
;
217 struct state_list
*a_F_c_F
= NULL
;
218 struct state_list
*a_F_c_fake
= NULL
;
222 * Imagine we have this: if (a ? b : c) { ...
224 * The condition is true if "a" is true and "b" is true or
225 * "a" is false and "c" is true. It's false if "a" is true
226 * and "b" is false or "a" is false and "c" is false.
228 * The variable name "a_T_b_T" stands for "a true b true" etc.
230 * But if we know "b" is true then we can simpilify things.
231 * The condition is true if "a" is true or if "a" is false and
232 * "c" is true. The only way the condition can be false is if
233 * "a" is false and "c" is false.
235 * The remaining thing is the "a_T_b_fake". When we simplify
236 * the equations we have to take into consideration that other
237 * states may have changed that don't play into the true false
238 * equation. Take the following example:
240 * (flags) = __raw_local_irq_save();
241 * _spin_trylock(lock) ? 1 :
242 * ({ raw_local_irq_restore(flags); 0; });
244 * Smatch has to record that the irq flags were restored on the
249 __save_pre_cond_states();
251 split_conditions(expr
->conditional
);
253 a_T
= __copy_cond_true_states();
254 a_F
= __copy_cond_false_states();
256 __push_cond_stacks();
257 __push_fake_cur_slist();
258 split_conditions(expr
->cond_true
);
259 __process_post_op_stack();
260 a_T_b_fake
= __pop_fake_cur_slist();
261 a_T_b_T
= combine(a_T
, a_T_b_fake
, __pop_cond_true_stack());
262 a_T_b_F
= combine(a_T
, a_T_b_fake
, __pop_cond_false_stack());
264 __use_cond_false_states();
266 __push_cond_stacks();
267 __push_fake_cur_slist();
268 split_conditions(expr
->cond_false
);
269 a_F_c_fake
= __pop_fake_cur_slist();
270 a_F_c_T
= combine(a_F
, a_F_c_fake
, __pop_cond_true_stack());
271 a_F_c_F
= combine(a_F
, a_F_c_fake
, __pop_cond_false_stack());
273 /* We have to restore the pre condition states so that
274 implied_condition_true() will use the right cur_slist */
275 __use_pre_cond_states();
277 if (implied_condition_true(expr
->cond_true
)) {
278 free_slist(&a_T_b_T
);
279 free_slist(&a_T_b_F
);
280 a_T_b_T
= clone_slist(a_T
);
281 overwrite_slist(a_T_b_fake
, &a_T_b_T
);
283 if (implied_condition_false(expr
->cond_true
)) {
284 free_slist(&a_T_b_T
);
285 free_slist(&a_T_b_F
);
286 a_T_b_F
= clone_slist(a_T
);
287 overwrite_slist(a_T_b_fake
, &a_T_b_F
);
289 if (implied_condition_true(expr
->cond_false
)) {
290 free_slist(&a_F_c_T
);
291 free_slist(&a_F_c_F
);
292 a_F_c_T
= clone_slist(a_F
);
293 overwrite_slist(a_F_c_fake
, &a_F_c_T
);
295 if (implied_condition_false(expr
->cond_false
)) {
296 free_slist(&a_F_c_T
);
297 free_slist(&a_F_c_F
);
298 a_F_c_F
= clone_slist(a_F
);
299 overwrite_slist(a_F_c_fake
, &a_F_c_F
);
302 merge_slist(&a_T_b_T
, a_F_c_T
);
303 merge_slist(&a_T_b_F
, a_F_c_F
);
305 __pop_cond_true_stack();
306 __pop_cond_false_stack();
307 __push_cond_stacks();
308 FOR_EACH_PTR(a_T_b_T
, sm
) {
309 __set_true_false_sm(sm
, NULL
);
310 } END_FOR_EACH_PTR(sm
);
311 FOR_EACH_PTR(a_T_b_F
, sm
) {
312 __set_true_false_sm(NULL
, sm
);
313 } END_FOR_EACH_PTR(sm
);
315 free_slist(&a_T_b_fake
);
316 free_slist(&a_F_c_fake
);
319 static int make_op_unsigned(int op
)
323 return SPECIAL_UNSIGNED_LT
;
325 return SPECIAL_UNSIGNED_LTE
;
327 return SPECIAL_UNSIGNED_GT
;
329 return SPECIAL_UNSIGNED_GTE
;
334 static void hackup_unsigned_compares(struct expression
*expr
)
336 if (expr
->type
!= EXPR_COMPARE
)
339 if (type_unsigned(get_type(expr
)))
340 expr
->op
= make_op_unsigned(expr
->op
);
343 static void split_conditions(struct expression
*expr
)
346 char *cond
= expr_to_str(expr
);
348 sm_debug("%d in split_conditions (%s)\n", get_lineno(), cond
);
352 expr
= strip_expr(expr
);
356 switch (expr
->type
) {
358 __pass_to_client(expr
, LOGIC_HOOK
);
359 handle_logical(expr
);
362 hackup_unsigned_compares(expr
);
363 if (handle_zero_comparisons(expr
))
367 if (ignore_builtin_expect(expr
))
371 if (handle_preop(expr
))
374 case EXPR_CONDITIONAL
:
380 /* fixme: this should be in smatch_flow.c
381 but because of the funny stuff we do with conditions
382 it's awkward to put it there. We would need to
383 call CONDITION_HOOK in smatch_flow as well.
385 push_expression(&big_expression_stack
, expr
);
386 if (expr
->type
== EXPR_COMPARE
) {
387 if (expr
->left
->type
!= EXPR_POSTOP
)
388 __split_expr(expr
->left
);
389 if (expr
->right
->type
!= EXPR_POSTOP
)
390 __split_expr(expr
->right
);
391 } else if (expr
->type
!= EXPR_POSTOP
) {
394 __pass_to_client(expr
, CONDITION_HOOK
);
395 if (expr
->type
== EXPR_COMPARE
) {
396 if (expr
->left
->type
== EXPR_POSTOP
)
397 __split_expr(expr
->left
);
398 if (expr
->right
->type
== EXPR_POSTOP
)
399 __split_expr(expr
->right
);
400 } else if (expr
->type
== EXPR_POSTOP
) {
403 __process_post_op_stack();
404 pop_expression(&big_expression_stack
);
407 static int inside_condition
;
408 void __split_whole_condition(struct expression
*expr
)
410 sm_debug("%d in __split_whole_condition\n", get_lineno());
412 __save_pre_cond_states();
413 __push_cond_stacks();
414 /* it's a hack, but it's sometimes handy to have this stuff
415 on the big_expression_stack. */
416 push_expression(&big_expression_stack
, expr
);
418 split_conditions(expr
);
420 __pass_to_client(expr
, WHOLE_CONDITION_HOOK
);
421 pop_expression(&big_expression_stack
);
423 sm_debug("%d done __split_whole_condition\n", get_lineno());
426 void __handle_logic(struct expression
*expr
)
428 sm_debug("%d in __handle_logic\n", get_lineno());
430 __save_pre_cond_states();
431 __push_cond_stacks();
432 /* it's a hack, but it's sometimes handy to have this stuff
433 on the big_expression_stack. */
434 push_expression(&big_expression_stack
, expr
);
436 split_conditions(expr
);
438 __pass_to_client(expr
, WHOLE_CONDITION_HOOK
);
439 pop_expression(&big_expression_stack
);
440 __merge_false_states();
442 sm_debug("%d done __handle_logic\n", get_lineno());
445 int is_condition(struct expression
*expr
)
448 expr
= strip_expr(expr
);
452 switch (expr
->type
) {
463 int __handle_condition_assigns(struct expression
*expr
)
465 struct expression
*right
;
467 right
= strip_expr(expr
->right
);
468 if (!is_condition(expr
->right
))
471 sm_debug("%d in __handle_condition_assigns\n", get_lineno());
473 __save_pre_cond_states();
474 __push_cond_stacks();
475 /* it's a hack, but it's sometimes handy to have this stuff
476 on the big_expression_stack. */
477 push_expression(&big_expression_stack
, right
);
478 split_conditions(right
);
480 set_extra_expr_mod(expr
->left
, alloc_estate_sval(sval_type_val(get_type(expr
->left
), 1)));
481 __pass_to_client(right
, WHOLE_CONDITION_HOOK
);
482 pop_expression(&big_expression_stack
);
484 sm_debug("%d done __handle_condition_assigns\n", get_lineno());
486 __push_true_states();
487 __use_false_states();
488 set_extra_expr_mod(expr
->left
, alloc_estate_sval(sval_type_val(get_type(expr
->left
), 0)));
489 __merge_true_states();
490 __pass_to_client(expr
, ASSIGNMENT_HOOK
);
494 static int is_select_assign(struct expression
*expr
)
496 struct expression
*right
;
500 right
= strip_expr(expr
->right
);
501 if (right
->type
== EXPR_CONDITIONAL
)
503 if (right
->type
== EXPR_SELECT
)
508 static void set_fake_assign(struct expression
*new,
509 struct expression
*left
, int op
, struct expression
*right
)
512 new->pos
= left
->pos
;
514 new->type
= EXPR_ASSIGNMENT
;
519 int __handle_select_assigns(struct expression
*expr
)
521 struct expression
*right
;
522 struct state_list
*final_states
= NULL
;
527 if (!is_select_assign(expr
))
529 sm_debug("%d in __handle_ternary_assigns\n", get_lineno());
530 right
= strip_expr(expr
->right
);
532 is_true
= implied_condition_true(right
->conditional
);
533 is_false
= implied_condition_false(right
->conditional
);
535 /* hah hah. the ultra fake out */
536 __save_pre_cond_states();
537 __split_whole_condition(right
->conditional
);
540 struct expression fake_expr
;
542 if (right
->cond_true
)
543 set_fake_assign(&fake_expr
, expr
->left
, expr
->op
, right
->cond_true
);
545 set_fake_assign(&fake_expr
, expr
->left
, expr
->op
, right
->conditional
);
546 __split_expr(&fake_expr
);
547 final_states
= clone_slist(__get_cur_slist());
550 __use_false_states();
552 struct expression fake_expr
;
554 set_fake_assign(&fake_expr
, expr
->left
, expr
->op
, right
->cond_false
);
555 __split_expr(&fake_expr
);
556 merge_slist(&final_states
, __get_cur_slist());
559 __use_pre_cond_states();
561 FOR_EACH_PTR(final_states
, sm
) {
563 } END_FOR_EACH_PTR(sm
);
565 free_slist(&final_states
);
567 sm_debug("%d done __handle_ternary_assigns\n", get_lineno());
572 static struct statement
*split_then_return_last(struct statement
*stmt
)
574 struct statement
*tmp
;
575 struct statement
*last_stmt
;
577 last_stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
581 __push_scope_hooks();
582 FOR_EACH_PTR(stmt
->stmts
, tmp
) {
583 if (tmp
== last_stmt
)
586 } END_FOR_EACH_PTR(tmp
);
590 int __handle_expr_statement_assigns(struct expression
*expr
)
592 struct expression
*right
;
593 struct statement
*stmt
;
596 if (right
->type
== EXPR_PREOP
&& right
->op
== '(')
598 if (right
->type
!= EXPR_STATEMENT
)
602 stmt
= right
->statement
;
603 if (stmt
->type
== STMT_COMPOUND
) {
604 struct statement
*last_stmt
;
605 struct expression fake_assign
;
606 struct expression fake_expr_stmt
;
608 last_stmt
= split_then_return_last(stmt
);
614 fake_expr_stmt
.pos
= last_stmt
->pos
;
615 fake_expr_stmt
.type
= EXPR_STATEMENT
;
616 fake_expr_stmt
.statement
= last_stmt
;
618 fake_assign
.pos
= last_stmt
->pos
;
619 fake_assign
.op
= expr
->op
;
620 fake_assign
.type
= EXPR_ASSIGNMENT
;
621 fake_assign
.left
= expr
->left
;
622 fake_assign
.right
= &fake_expr_stmt
;
624 __split_expr(&fake_assign
);
626 __call_scope_hooks();
627 } else if (stmt
->type
== STMT_EXPRESSION
) {
628 struct expression fake_assign
;
630 fake_assign
.pos
= stmt
->pos
;
631 fake_assign
.op
= expr
->op
;
632 fake_assign
.type
= EXPR_ASSIGNMENT
;
633 fake_assign
.left
= expr
->left
;
634 fake_assign
.right
= stmt
->expression
;
636 __split_expr(&fake_assign
);
645 int in_condition(void)
647 return inside_condition
;