Hi,
Please find a patch to fix part of the bug PR analyzer/94362. This bug is a
false positive for a null dereference found when compiling openssl. The cause
is the constraint_manager not knowing that i >= 0 within the for block:
for ( ; i-- > 0; )
The bug can be further reduced to the constraint manager not knowing that i >= 0
within the if block:
if (i-- > 0)
which is not replicated for other operators, such as prefix decrement. The
cause is that the constraint is applied to the initial_svalue of i, while it
is a binop_svalue of i that enters the block (with op PLUS and arg1 -1). The
constraint_manager does not have any constraints for this svalue and has no
handler. A handler has been added that essentially recurs on the remaining arg
if the other arg and other side of the condition are both constants and the op
is PLUS_EXPR or MINUS_EXPR.
This in essence fixed the problem, except an off by one error had been hiding
in range::eval_condition. This error is hard to notice, because, for example,
the code
if(idx > 0)
__analyzer_eval(idx >= 1);
will compile as (check -fdump-ipa-analyzer to see)
void test (int idx)
{
_Bool _1;
int _2;
<bb 2> :
if (idx_4(D) > 0)
goto <bb 3>; [INV]
else
goto <bb 4>; [INV]
<bb 3> :
_1 = idx_4(D) > 0;
_2 = (int) _1;
__analyzer_eval (_2);
<bb 4> :
return;
}
and will print "TRUE" to the screen, but as you can see, it is for the wrong
reason, because we are not really testing the condition we wanted to test.
You can force the failure (i.e. "UNKNOWN") for yourself with the following:
void test(int idx)
{
int check = 1;
if(idx > 0)
__analyzer_eval(idx >= check);
}
which the compiler will not "fix" on us. An examination of range::eval_condition
should convince you that there is an off by one error. Incidentally, I might
recommend doing away with "open intervals of integers" entirely.
When running the initial bug (the for loop), you will find that the analyzer
prints "UNKNOWN" twice for the postfix operator, and "TRUE" "UNKNOWN" for other
operators. This patch reduces postfix to the same state as the other operators.
The second "UNKNOWN" seems to be due to a second "iterated" pass through the
loop with a widening_svalue. A full fix of the bug will need a handler for the
widening svalue, and much more critically, a correct merge of the constraints
at the loop entrance. That, unfortunately, looks to be a hard problem.
This patch fixes a few xfails as noted in the commit message. These were tests
that were evidently devised to test whether the analyzer would understand
arithmetic being done on constrained values. Addition and subtraction is now
working as expected, a handler for multiplication and division can be added.
As was noted in those test files, consideration at some point should be given to
overflow.
Thank you,
Brian
Sent with ProtonMail Secure Email.commit d4052e8c273ca267f6dcf782084d60acfc50a609
Author: Brian Sobulefsky <brian.sobulef...@protonmail.com>
Date: Sat Feb 27 00:36:40 2021 -0800
Changes to support eventual solution to bug PR analyzer/94362. This bug
originated with a false positive null dereference during compilation of
openssl. The bug is in effect caused by an error in constraint handling,
specifically that within the for block:
for ( ; i-- > 0; )
{
}
the constraint_manager should know i >= 0 but does not. A reduced form of
this bug was found where the constraint manager did not know within the if
block:
if (i-- > 0)
{
}
that i >= 0. This latter error was only present for the postfix
operators, and not for other forms, like --i > 0. It was due to the
constraint being set for the initial_svalue associated with i, but a
binop_svalue being what entered the if block for which no constraint
rules existed.
By adding handling logic for a binop_svalue that adds or
subtracts a constant, this problem was solved. This logic was added to
a new method, constraint_manager::maybe_fold_condition, with the
intent of eventually adding more cases there (unary_svalue and
widening_svalue for example). Additionally, an off by one error was
found in range::eval_condition that needed to be corrected to get
the expected result. Correction of this error was done in that
subroutine, resulting in no more calls to below_lower_bound and
above_upper_bound. As such, these functions were commented out and may
be removed if not needed for anything else.
This change does not entirely fix the initial bug pr94362, but it
reduces the postfix operator to the same state as other operators. In the
case of the for loop, there appears to be an "initial pass" through the
loop, which the analyzer will now understand for postfix, and then an
"iterated pass" with a widening_svalue that the analyzer does not
understand for any condition found. This seems to be due to the merging
of constraints and is under investigation.
While not the original intent of this change, during run of the
testsuite it was found that some errors that were marked xfail had been
corrected in the files testsuite/gcc.dg/analyzer/operations.c and
testsuite/gcc.dg/analyzer/params.c. These corrected errors were for
addition and subtraction manipulations of variables within a
conditional. Other manipulations, like multiply and divide, are still
failing as expected because no handler has been added.
gcc/analyzer/ChangeLog:
PR analyzer/94362
* analyzer/constraint-manager.cc
(constraint_manager::eval_condition(svalue *, op, svalue *)):
Add call to new function maybe_fold_condition.
* analyzer/constraint-manager.cc
(constraint_manager::maybe_fold_condition): New function.
* analyzer/constraint-manager.cc (range::eval_condition): Update
logic to correct off by one error
* analyzer/constraint-manager.cc (range::below_lower_bound):
Remove function as there are no longer any calls to it.
* analyzer/constraint-manager.cc (range::above_upper_bound):
Remove function as there are no longer any calls to it.
* analyzer/constraint-manager.h (class constraint_manager): Add
new function declaration maybe_fold_condition.
* analyzer/constraint-manager.h (class range): Remove
declarations of functions no longer called.
gcc/testsuite/ChangeLog:
PR analyzer/94362
* gcc.dg/analyzer/operations.c: remove "desired", "xfail" and
entire call to "bogus".
* gcc.dg/analyzer/params.c: remove "desired", "xfail" and
entire call to "bogus".
diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc
index 4dadd200bee..5184ead2b3f 100644
--- a/gcc/analyzer/constraint-manager.cc
+++ b/gcc/analyzer/constraint-manager.cc
@@ -181,24 +181,56 @@ range::eval_condition (enum tree_code op, tree rhs_const) const
if (tree single_element = copy.constrained_to_single_element ())
return compare_constants (single_element, op, rhs_const);
+ /* Corner case in which constrained_to_single_element will not convert the
+ bounds to closure (i.e., a bound with only one end point) */
+ if(copy.m_lower_bound.m_constant == NULL_TREE
+ && copy.m_upper_bound.m_constant != NULL_TREE
+ && INTEGRAL_TYPE_P (TREE_TYPE (copy.m_upper_bound.m_constant)))
+ copy.m_upper_bound.ensure_closed(true);
+ if(copy.m_upper_bound.m_constant == NULL_TREE
+ && copy.m_lower_bound.m_constant != NULL_TREE
+ && INTEGRAL_TYPE_P (TREE_TYPE (copy.m_lower_bound.m_constant)))
+ copy.m_lower_bound.ensure_closed(false);
+
switch (op)
{
+
case EQ_EXPR:
- if (below_lower_bound (rhs_const))
+ if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LT_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
return tristate (tristate::TS_FALSE);
- if (above_upper_bound (rhs_const))
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GT_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
return tristate (tristate::TS_FALSE);
break;
case LT_EXPR:
- case LE_EXPR:
- /* Qn: "X </<= RHS_CONST". */
+ /* Qn: "X </<= RHS_CONST". */
/* If RHS_CONST > upper bound, then it's true.
If RHS_CONST < lower bound, then it's false.
Otherwise unknown. */
- if (above_upper_bound (rhs_const))
+
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GT_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
+ return tristate (tristate::TS_TRUE);
+ else if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LE_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
+ return tristate (tristate::TS_FALSE);
+ break;
+
+ case LE_EXPR:
+
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GE_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
return tristate (tristate::TS_TRUE);
- if (below_lower_bound (rhs_const))
+ else if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LT_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
return tristate (tristate::TS_FALSE);
break;
@@ -207,18 +239,37 @@ range::eval_condition (enum tree_code op, tree rhs_const) const
/* If RHS_CONST < lower bound, then it's true.
If RHS_CONST > upper bound, then it's false.
Otherwise unknown. */
- if (below_lower_bound (rhs_const))
+ if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LT_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
return tristate (tristate::TS_TRUE);
- if (above_upper_bound (rhs_const))
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GT_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
return tristate (tristate::TS_TRUE);
break;
case GE_EXPR:
+
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GT_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
+ return tristate (tristate::TS_FALSE);
+ else if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LE_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
+ return tristate (tristate::TS_TRUE);
+ break;
+
case GT_EXPR:
- /* Qn: "X >=/> RHS_CONST". */
- if (above_upper_bound (rhs_const))
+
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GE_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
return tristate (tristate::TS_FALSE);
- if (below_lower_bound (rhs_const))
+ else if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LT_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
return tristate (tristate::TS_TRUE);
break;
@@ -229,9 +280,15 @@ range::eval_condition (enum tree_code op, tree rhs_const) const
return tristate (tristate::TS_UNKNOWN);
}
+
+/* Since updating range::eval_condition to fix the off by one errors, these two
+ subroutines are no longer called anywhere else so they are commented out to
+ suppress any compiler warnings. If they will not be used anymore, it can be
+ completely removed. */
+
/* Return true if RHS_CONST is below the lower bound of this range. */
-bool
+/*bool
range::below_lower_bound (tree rhs_const) const
{
if (!m_lower_bound.m_constant)
@@ -240,11 +297,11 @@ range::below_lower_bound (tree rhs_const) const
return compare_constants (rhs_const,
m_lower_bound.m_closed ? LT_EXPR : LE_EXPR,
m_lower_bound.m_constant).is_true ();
-}
+}*/
/* Return true if RHS_CONST is above the upper bound of this range. */
-bool
+/*bool
range::above_upper_bound (tree rhs_const) const
{
if (!m_upper_bound.m_constant)
@@ -253,7 +310,7 @@ range::above_upper_bound (tree rhs_const) const
return compare_constants (rhs_const,
m_upper_bound.m_closed ? GT_EXPR : GE_EXPR,
m_upper_bound.m_constant).is_true ();
-}
+}*/
/* class equiv_class. */
@@ -1499,6 +1556,167 @@ constraint_manager::eval_condition (const svalue *lhs,
}
}
+ /* Try folding the condition with any sub svalues */
+ {
+ tristate result_for_folding = maybe_fold_condition (lhs, op, rhs);
+ if (result_for_folding.is_known ())
+ return result_for_folding;
+ }
+
+ return tristate (tristate::TS_UNKNOWN);
+}
+
+/* Method to put logic for folding conditions. Currently contains logic for
+ folding a binop_svalue where one arg is a constant and the other side of
+ the condition is a constant. Inspiration was to handle the conditional
+ if (i-- > 0) __analyzer_eval (i >= 0);
+
+ Other cases may be added, including perhaps logic to handle unaryop_svalue
+ and widening_svalue. */
+
+tristate
+constraint_manager::maybe_fold_condition (const svalue *lhs,
+ enum tree_code op,
+ const svalue *rhs) const
+{
+
+ if (const binop_svalue *binop_sval = lhs->dyn_cast_binop_svalue ())
+ {
+ const constant_svalue *cst_arg;
+ const svalue *other_arg = NULL;
+ const constant_svalue *cst_cond;
+ const svalue *new_cond = NULL;
+ tree_code bin_op;
+ if ((cst_arg = binop_sval->get_arg0 ()->dyn_cast_constant_svalue ()))
+ {
+ if((cst_cond = rhs->dyn_cast_constant_svalue ()))
+ {
+ other_arg = binop_sval->get_arg0 ();
+ bin_op = binop_sval->get_op();
+ /* (CST_ARG +/- OTHER_ARG) OP CST_COND ==>
+ +: OTHER_ARG OP (CST_COND - CST_ARG)
+ -: (CST_ARG - CST_COND) OP OTHER_ARG */
+ if(bin_op == PLUS_EXPR)
+ {
+ new_cond
+ = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant (),
+ cst_arg->get_constant ()));
+ return eval_condition (other_arg, op, new_cond);
+ }
+ else if(bin_op == MINUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_arg->get_constant(),
+ cst_cond->get_constant()));
+ return eval_condition (new_cond, op, other_arg);
+ }
+ }
+ }
+ else if((cst_arg = binop_sval->get_arg1 ()->dyn_cast_constant_svalue ()))
+ {
+ if((cst_cond = rhs->dyn_cast_constant_svalue ()))
+ {
+ other_arg = binop_sval->get_arg0 ();
+ bin_op = binop_sval->get_op();
+ /* (OTHER_ARG +/- CST_ARG) OP CST_COND ==>
+ OTHER_ARG OP (CST_COND -/+ CST_ARG) */
+ if(bin_op == PLUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant(),
+ cst_arg->get_constant()));
+ }
+ else if(bin_op == MINUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ PLUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant(),
+ cst_arg->get_constant()));
+ }
+ if (other_arg && new_cond){
+ return eval_condition (other_arg, op, new_cond);
+ }
+
+ }
+ }
+ }
+ else if (const binop_svalue *binop_sval = rhs->dyn_cast_binop_svalue ())
+ {
+ const constant_svalue *cst_arg;
+ const svalue *other_arg = NULL;
+ const constant_svalue *cst_cond;
+ const svalue *new_cond = NULL;
+ tree_code bin_op;
+ if ((cst_arg = binop_sval->get_arg0 ()->dyn_cast_constant_svalue ()))
+ {
+ if((cst_cond = rhs->dyn_cast_constant_svalue ()))
+ {
+ other_arg = binop_sval->get_arg0 ();
+ bin_op = binop_sval->get_op();
+ /* CST_COND OP (CST_ARG +/- OTHER_ARG) ==>
+ +: (CST_COND - CST_ARG) OP OTHER_ARG
+ -: OTHER_ARG OP (CST_ARG - CST_COND) */
+ if(bin_op == PLUS_EXPR)
+ {
+ new_cond
+ = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant (),
+ cst_arg->get_constant ()));
+ return eval_condition (new_cond, op, other_arg);
+ }
+ else if(bin_op == MINUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_arg->get_constant(),
+ cst_cond->get_constant()));
+ return eval_condition (other_arg, op, new_cond);
+ }
+
+
+ }
+ }
+ else if((cst_arg = binop_sval->get_arg1 ()->dyn_cast_constant_svalue ()))
+ {
+ if((cst_cond = rhs->dyn_cast_constant_svalue ()))
+ {
+ other_arg = binop_sval->get_arg0 ();
+ bin_op = binop_sval->get_op();
+ /* CST_COND OP (OTHER_ARG +/- CST_ARG) ==>
+ (CST_COND -/+ CST_ARG) OP OTHER_ARG */
+ if(bin_op == PLUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant(),
+ cst_arg->get_constant()));
+ }
+ else if(bin_op == MINUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ PLUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant(),
+ cst_arg->get_constant()));
+ }
+ if (other_arg && new_cond)
+ return eval_condition (new_cond, op, other_arg);
+
+ }
+ }
+ }
return tristate (tristate::TS_UNKNOWN);
}
diff --git a/gcc/analyzer/constraint-manager.h b/gcc/analyzer/constraint-manager.h
index 3173610a723..9017a88ecac 100644
--- a/gcc/analyzer/constraint-manager.h
+++ b/gcc/analyzer/constraint-manager.h
@@ -57,8 +57,10 @@ struct range
tristate eval_condition (enum tree_code op,
tree rhs_const) const;
- bool below_lower_bound (tree rhs_const) const;
- bool above_upper_bound (tree rhs_const) const;
+
+ /* Commented out because no longer called from anywhere in program */
+ //bool below_lower_bound (tree rhs_const) const;
+ //bool above_upper_bound (tree rhs_const) const;
bound m_lower_bound;
bound m_upper_bound;
@@ -284,6 +286,9 @@ public:
auto_vec<constraint> m_constraints;
private:
+ tristate maybe_fold_condition (const svalue *lhs,
+ enum tree_code op,
+ const svalue *rhs) const;
void add_constraint_internal (equiv_class_id lhs_id,
enum constraint_op c_op,
equiv_class_id rhs_id);
diff --git a/gcc/testsuite/gcc.dg/analyzer/operations.c b/gcc/testsuite/gcc.dg/analyzer/operations.c
index 79e76bccc66..87b3703a3d9 100644
--- a/gcc/testsuite/gcc.dg/analyzer/operations.c
+++ b/gcc/testsuite/gcc.dg/analyzer/operations.c
@@ -9,14 +9,14 @@ void test (int i, int j)
i += 3;
- __analyzer_eval (i > 45); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
+ __analyzer_eval (i > 45); /* { dg-warning "TRUE" } */
+
/* TODO(xfail): do we really know this? what about overflow? */
i -= 1;
- __analyzer_eval (i > 44); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
+ __analyzer_eval (i > 44); /* { dg-warning "TRUE" } */
+
/* TODO(xfail): do we really know this? what about overflow? */
i = 3 * i;
diff --git a/gcc/testsuite/gcc.dg/analyzer/params.c b/gcc/testsuite/gcc.dg/analyzer/params.c
index 12bba70d6e4..a1c443b39eb 100644
--- a/gcc/testsuite/gcc.dg/analyzer/params.c
+++ b/gcc/testsuite/gcc.dg/analyzer/params.c
@@ -8,8 +8,8 @@ static int __analyzer_called_function(int j)
k = j - 1;
- __analyzer_eval (k > 3); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
+ __analyzer_eval (k > 3); /* { dg-warning "TRUE" } */
+
/* TODO(xfail): we're not then updating based on the assignment. */
return k;
@@ -25,8 +25,8 @@ void test(int i)
i = __analyzer_called_function(i);
- __analyzer_eval (i > 3); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
+ __analyzer_eval (i > 3); /* { dg-warning "TRUE" } */
+
/* TODO(xfail): we're not updating from the returned value. */
}
commit d4052e8c273ca267f6dcf782084d60acfc50a609
Author: Brian Sobulefsky <brian.sobulef...@protonmail.com>
Date: Sat Feb 27 00:36:40 2021 -0800
Changes to support eventual solution to bug PR analyzer/94362. This bug
originated with a false positive null dereference during compilation of
openssl. The bug is in effect caused by an error in constraint handling,
specifically that within the for block:
for ( ; i-- > 0; )
{
}
the constraint_manager should know i >= 0 but does not. A reduced form of
this bug was found where the constraint manager did not know within the if
block:
if (i-- > 0)
{
}
that i >= 0. This latter error was only present for the postfix
operators, and not for other forms, like --i > 0. It was due to the
constraint being set for the initial_svalue associated with i, but a
binop_svalue being what entered the if block for which no constraint
rules existed.
By adding handling logic for a binop_svalue that adds or
subtracts a constant, this problem was solved. This logic was added to
a new method, constraint_manager::maybe_fold_condition, with the
intent of eventually adding more cases there (unary_svalue and
widening_svalue for example). Additionally, an off by one error was
found in range::eval_condition that needed to be corrected to get
the expected result. Correction of this error was done in that
subroutine, resulting in no more calls to below_lower_bound and
above_upper_bound. As such, these functions were commented out and may
be removed if not needed for anything else.
This change does not entirely fix the initial bug pr94362, but it
reduces the postfix operator to the same state as other operators. In the
case of the for loop, there appears to be an "initial pass" through the
loop, which the analyzer will now understand for postfix, and then an
"iterated pass" with a widening_svalue that the analyzer does not
understand for any condition found. This seems to be due to the merging
of constraints and is under investigation.
While not the original intent of this change, during run of the
testsuite it was found that some errors that were marked xfail had been
corrected in the files testsuite/gcc.dg/analyzer/operations.c and
testsuite/gcc.dg/analyzer/params.c. These corrected errors were for
addition and subtraction manipulations of variables within a
conditional. Other manipulations, like multiply and divide, are still
failing as expected because no handler has been added.
gcc/analyzer/ChangeLog:
PR analyzer/94362
* analyzer/constraint-manager.cc
(constraint_manager::eval_condition(svalue *, op, svalue *)):
Add call to new function maybe_fold_condition.
* analyzer/constraint-manager.cc
(constraint_manager::maybe_fold_condition): New function.
* analyzer/constraint-manager.cc (range::eval_condition): Update
logic to correct off by one error
* analyzer/constraint-manager.cc (range::below_lower_bound):
Remove function as there are no longer any calls to it.
* analyzer/constraint-manager.cc (range::above_upper_bound):
Remove function as there are no longer any calls to it.
* analyzer/constraint-manager.h (class constraint_manager): Add
new function declaration maybe_fold_condition.
* analyzer/constraint-manager.h (class range): Remove
declarations of functions no longer called.
gcc/testsuite/ChangeLog:
PR analyzer/94362
* gcc.dg/analyzer/operations.c: remove "desired", "xfail" and
entire call to "bogus".
* gcc.dg/analyzer/params.c: remove "desired", "xfail" and
entire call to "bogus".
diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc
index 4dadd200bee..5184ead2b3f 100644
--- a/gcc/analyzer/constraint-manager.cc
+++ b/gcc/analyzer/constraint-manager.cc
@@ -181,24 +181,56 @@ range::eval_condition (enum tree_code op, tree rhs_const) const
if (tree single_element = copy.constrained_to_single_element ())
return compare_constants (single_element, op, rhs_const);
+ /* Corner case in which constrained_to_single_element will not convert the
+ bounds to closure (i.e., a bound with only one end point) */
+ if(copy.m_lower_bound.m_constant == NULL_TREE
+ && copy.m_upper_bound.m_constant != NULL_TREE
+ && INTEGRAL_TYPE_P (TREE_TYPE (copy.m_upper_bound.m_constant)))
+ copy.m_upper_bound.ensure_closed(true);
+ if(copy.m_upper_bound.m_constant == NULL_TREE
+ && copy.m_lower_bound.m_constant != NULL_TREE
+ && INTEGRAL_TYPE_P (TREE_TYPE (copy.m_lower_bound.m_constant)))
+ copy.m_lower_bound.ensure_closed(false);
+
switch (op)
{
+
case EQ_EXPR:
- if (below_lower_bound (rhs_const))
+ if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LT_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
return tristate (tristate::TS_FALSE);
- if (above_upper_bound (rhs_const))
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GT_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
return tristate (tristate::TS_FALSE);
break;
case LT_EXPR:
- case LE_EXPR:
- /* Qn: "X </<= RHS_CONST". */
+ /* Qn: "X </<= RHS_CONST". */
/* If RHS_CONST > upper bound, then it's true.
If RHS_CONST < lower bound, then it's false.
Otherwise unknown. */
- if (above_upper_bound (rhs_const))
+
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GT_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
+ return tristate (tristate::TS_TRUE);
+ else if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LE_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
+ return tristate (tristate::TS_FALSE);
+ break;
+
+ case LE_EXPR:
+
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GE_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
return tristate (tristate::TS_TRUE);
- if (below_lower_bound (rhs_const))
+ else if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LT_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
return tristate (tristate::TS_FALSE);
break;
@@ -207,18 +239,37 @@ range::eval_condition (enum tree_code op, tree rhs_const) const
/* If RHS_CONST < lower bound, then it's true.
If RHS_CONST > upper bound, then it's false.
Otherwise unknown. */
- if (below_lower_bound (rhs_const))
+ if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LT_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
return tristate (tristate::TS_TRUE);
- if (above_upper_bound (rhs_const))
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GT_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
return tristate (tristate::TS_TRUE);
break;
case GE_EXPR:
+
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GT_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
+ return tristate (tristate::TS_FALSE);
+ else if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LE_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
+ return tristate (tristate::TS_TRUE);
+ break;
+
case GT_EXPR:
- /* Qn: "X >=/> RHS_CONST". */
- if (above_upper_bound (rhs_const))
+
+ if (copy.m_upper_bound.m_constant
+ && compare_constants (rhs_const, GE_EXPR,
+ copy.m_upper_bound.m_constant).is_true())
return tristate (tristate::TS_FALSE);
- if (below_lower_bound (rhs_const))
+ else if (copy.m_lower_bound.m_constant
+ && compare_constants (rhs_const, LT_EXPR,
+ copy.m_lower_bound.m_constant).is_true())
return tristate (tristate::TS_TRUE);
break;
@@ -229,9 +280,15 @@ range::eval_condition (enum tree_code op, tree rhs_const) const
return tristate (tristate::TS_UNKNOWN);
}
+
+/* Since updating range::eval_condition to fix the off by one errors, these two
+ subroutines are no longer called anywhere else so they are commented out to
+ suppress any compiler warnings. If they will not be used anymore, it can be
+ completely removed. */
+
/* Return true if RHS_CONST is below the lower bound of this range. */
-bool
+/*bool
range::below_lower_bound (tree rhs_const) const
{
if (!m_lower_bound.m_constant)
@@ -240,11 +297,11 @@ range::below_lower_bound (tree rhs_const) const
return compare_constants (rhs_const,
m_lower_bound.m_closed ? LT_EXPR : LE_EXPR,
m_lower_bound.m_constant).is_true ();
-}
+}*/
/* Return true if RHS_CONST is above the upper bound of this range. */
-bool
+/*bool
range::above_upper_bound (tree rhs_const) const
{
if (!m_upper_bound.m_constant)
@@ -253,7 +310,7 @@ range::above_upper_bound (tree rhs_const) const
return compare_constants (rhs_const,
m_upper_bound.m_closed ? GT_EXPR : GE_EXPR,
m_upper_bound.m_constant).is_true ();
-}
+}*/
/* class equiv_class. */
@@ -1499,6 +1556,167 @@ constraint_manager::eval_condition (const svalue *lhs,
}
}
+ /* Try folding the condition with any sub svalues */
+ {
+ tristate result_for_folding = maybe_fold_condition (lhs, op, rhs);
+ if (result_for_folding.is_known ())
+ return result_for_folding;
+ }
+
+ return tristate (tristate::TS_UNKNOWN);
+}
+
+/* Method to put logic for folding conditions. Currently contains logic for
+ folding a binop_svalue where one arg is a constant and the other side of
+ the condition is a constant. Inspiration was to handle the conditional
+ if (i-- > 0) __analyzer_eval (i >= 0);
+
+ Other cases may be added, including perhaps logic to handle unaryop_svalue
+ and widening_svalue. */
+
+tristate
+constraint_manager::maybe_fold_condition (const svalue *lhs,
+ enum tree_code op,
+ const svalue *rhs) const
+{
+
+ if (const binop_svalue *binop_sval = lhs->dyn_cast_binop_svalue ())
+ {
+ const constant_svalue *cst_arg;
+ const svalue *other_arg = NULL;
+ const constant_svalue *cst_cond;
+ const svalue *new_cond = NULL;
+ tree_code bin_op;
+ if ((cst_arg = binop_sval->get_arg0 ()->dyn_cast_constant_svalue ()))
+ {
+ if((cst_cond = rhs->dyn_cast_constant_svalue ()))
+ {
+ other_arg = binop_sval->get_arg0 ();
+ bin_op = binop_sval->get_op();
+ /* (CST_ARG +/- OTHER_ARG) OP CST_COND ==>
+ +: OTHER_ARG OP (CST_COND - CST_ARG)
+ -: (CST_ARG - CST_COND) OP OTHER_ARG */
+ if(bin_op == PLUS_EXPR)
+ {
+ new_cond
+ = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant (),
+ cst_arg->get_constant ()));
+ return eval_condition (other_arg, op, new_cond);
+ }
+ else if(bin_op == MINUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_arg->get_constant(),
+ cst_cond->get_constant()));
+ return eval_condition (new_cond, op, other_arg);
+ }
+ }
+ }
+ else if((cst_arg = binop_sval->get_arg1 ()->dyn_cast_constant_svalue ()))
+ {
+ if((cst_cond = rhs->dyn_cast_constant_svalue ()))
+ {
+ other_arg = binop_sval->get_arg0 ();
+ bin_op = binop_sval->get_op();
+ /* (OTHER_ARG +/- CST_ARG) OP CST_COND ==>
+ OTHER_ARG OP (CST_COND -/+ CST_ARG) */
+ if(bin_op == PLUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant(),
+ cst_arg->get_constant()));
+ }
+ else if(bin_op == MINUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ PLUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant(),
+ cst_arg->get_constant()));
+ }
+ if (other_arg && new_cond){
+ return eval_condition (other_arg, op, new_cond);
+ }
+
+ }
+ }
+ }
+ else if (const binop_svalue *binop_sval = rhs->dyn_cast_binop_svalue ())
+ {
+ const constant_svalue *cst_arg;
+ const svalue *other_arg = NULL;
+ const constant_svalue *cst_cond;
+ const svalue *new_cond = NULL;
+ tree_code bin_op;
+ if ((cst_arg = binop_sval->get_arg0 ()->dyn_cast_constant_svalue ()))
+ {
+ if((cst_cond = rhs->dyn_cast_constant_svalue ()))
+ {
+ other_arg = binop_sval->get_arg0 ();
+ bin_op = binop_sval->get_op();
+ /* CST_COND OP (CST_ARG +/- OTHER_ARG) ==>
+ +: (CST_COND - CST_ARG) OP OTHER_ARG
+ -: OTHER_ARG OP (CST_ARG - CST_COND) */
+ if(bin_op == PLUS_EXPR)
+ {
+ new_cond
+ = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant (),
+ cst_arg->get_constant ()));
+ return eval_condition (new_cond, op, other_arg);
+ }
+ else if(bin_op == MINUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_arg->get_constant(),
+ cst_cond->get_constant()));
+ return eval_condition (other_arg, op, new_cond);
+ }
+
+
+ }
+ }
+ else if((cst_arg = binop_sval->get_arg1 ()->dyn_cast_constant_svalue ()))
+ {
+ if((cst_cond = rhs->dyn_cast_constant_svalue ()))
+ {
+ other_arg = binop_sval->get_arg0 ();
+ bin_op = binop_sval->get_op();
+ /* CST_COND OP (OTHER_ARG +/- CST_ARG) ==>
+ (CST_COND -/+ CST_ARG) OP OTHER_ARG */
+ if(bin_op == PLUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ MINUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant(),
+ cst_arg->get_constant()));
+ }
+ else if(bin_op == MINUS_EXPR)
+ {
+ new_cond = m_mgr->get_or_create_constant_svalue (fold_build2 (
+ PLUS_EXPR, TREE_TYPE (
+ cst_cond->get_constant ()),
+ cst_cond->get_constant(),
+ cst_arg->get_constant()));
+ }
+ if (other_arg && new_cond)
+ return eval_condition (new_cond, op, other_arg);
+
+ }
+ }
+ }
return tristate (tristate::TS_UNKNOWN);
}
diff --git a/gcc/analyzer/constraint-manager.h b/gcc/analyzer/constraint-manager.h
index 3173610a723..9017a88ecac 100644
--- a/gcc/analyzer/constraint-manager.h
+++ b/gcc/analyzer/constraint-manager.h
@@ -57,8 +57,10 @@ struct range
tristate eval_condition (enum tree_code op,
tree rhs_const) const;
- bool below_lower_bound (tree rhs_const) const;
- bool above_upper_bound (tree rhs_const) const;
+
+ /* Commented out because no longer called from anywhere in program */
+ //bool below_lower_bound (tree rhs_const) const;
+ //bool above_upper_bound (tree rhs_const) const;
bound m_lower_bound;
bound m_upper_bound;
@@ -284,6 +286,9 @@ public:
auto_vec<constraint> m_constraints;
private:
+ tristate maybe_fold_condition (const svalue *lhs,
+ enum tree_code op,
+ const svalue *rhs) const;
void add_constraint_internal (equiv_class_id lhs_id,
enum constraint_op c_op,
equiv_class_id rhs_id);
diff --git a/gcc/testsuite/gcc.dg/analyzer/operations.c b/gcc/testsuite/gcc.dg/analyzer/operations.c
index 79e76bccc66..87b3703a3d9 100644
--- a/gcc/testsuite/gcc.dg/analyzer/operations.c
+++ b/gcc/testsuite/gcc.dg/analyzer/operations.c
@@ -9,14 +9,14 @@ void test (int i, int j)
i += 3;
- __analyzer_eval (i > 45); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
+ __analyzer_eval (i > 45); /* { dg-warning "TRUE" } */
+
/* TODO(xfail): do we really know this? what about overflow? */
i -= 1;
- __analyzer_eval (i > 44); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
+ __analyzer_eval (i > 44); /* { dg-warning "TRUE" } */
+
/* TODO(xfail): do we really know this? what about overflow? */
i = 3 * i;
diff --git a/gcc/testsuite/gcc.dg/analyzer/params.c b/gcc/testsuite/gcc.dg/analyzer/params.c
index 12bba70d6e4..a1c443b39eb 100644
--- a/gcc/testsuite/gcc.dg/analyzer/params.c
+++ b/gcc/testsuite/gcc.dg/analyzer/params.c
@@ -8,8 +8,8 @@ static int __analyzer_called_function(int j)
k = j - 1;
- __analyzer_eval (k > 3); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
+ __analyzer_eval (k > 3); /* { dg-warning "TRUE" } */
+
/* TODO(xfail): we're not then updating based on the assignment. */
return k;
@@ -25,8 +25,8 @@ void test(int i)
i = __analyzer_called_function(i);
- __analyzer_eval (i > 3); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
+ __analyzer_eval (i > 3); /* { dg-warning "TRUE" } */
+
/* TODO(xfail): we're not updating from the returned value. */
}
