| Message ID | 87y4fdacx5.fsf@e105548-lin.cambridge.arm.com |
|---|---|
| State | New |
| Headers | show |
On Thu, Oct 8, 2015 at 12:10 PM, Richard Sandiford <richard.sandiford@arm.com> wrote: > Richard Biener <richard.guenther@gmail.com> writes: >> On Mon, Oct 5, 2015 at 5:02 PM, Richard Sandiford >> <richard.sandiford@arm.com> wrote: >>> The upcoming patch to move sqrt and cbrt simplifications to match.pd >>> caused a regression because the (abs @0)->@0 simplification didn't >>> trigger for: >>> >>> (abs (convert (abs X))) >>> >>> The simplification is based on tree_expr_nonnegative_p, which is >>> pretty weak for gimple (it gives up if it sees an SSA_NAME). >>> >>> We have the stronger gimple_val_nonnegative_real_p, but (a) as its >>> name implies, it's specific to reals and (b) in its current form it >>> doesn't handle converts. This patch: >>> >>> - generalises the routine all types >>> - reuses tree_{unary,binary,call}_nonnegative_warnv_p for the leaf cases >>> - makes the routine handle CONVERT_EXPR >>> - allows a nesting depth of 1 for CONVERT_EXPR >>> - uses the routine instead of tree_expr_nonnegative_p for gimple. >>> >>> Limiting the depth to 1 is a little arbitrary but adding a param seemed >>> over the top. >>> >>> Bootstrapped & regression-tested on x86_64-linux-gnu. I didn't write >>> a specific test because this is already covered by the testsuite if >>> the follow-on patch is also applied. OK to install? >> >> Hmm. I don't like having essentially two copies of the same machinery. >> Can you instead fold gimple_val_nonnegative_real_p into a >> tree_ssa_name_nonnegative_warnv_p used by tree_expr_nonnegative_warnv_p? >> For integers it's also possible to look at SSA name range info. >> You'd still limit recursion appropriately (by passing down a depth arg >> everywhere, >> defaulted to 0 I guess). > > OK. I wanted to combine the functions originally but, with > gimple_val_nonnegative_real_p being an obvious partial cut-&-paste > of fold-const.c, I assumed things were the way they were because > having a single routine would be breaking some abstraction barrier. > > This patch moves the vrp code for querying gimple statements to > gimple-fold.c, adds a function to fold-const.c for querying SSA names, > and adds a depth parameter to both sets of functions. As discussed > on IRC, it has the downside that gimple-fold.c calls fold-const.c > and fold-const.c calls gimple-fold.c. > > Also as discussed on IRC, a knock-on effect is that we can now prove > _i_589 < 0 is false in sequences like: > > i_1917 = ASSERT_EXPR <i_1075, i_1075 == 0>; > _i_589 = (const int) i_1917; > _i_1507 = ASSERT_EXPR <_i_589, _i_589 < 0>; > > This defeats an assert in tree-vrp.c that ASSERT_EXPR conditions > are never known to be false. Previously the assert only ever used > local knowledge and so would be limited to cases like x != x for > integer x. Now that we use global knowledge it's possible to prove > the assertion condition is false in blocks that are in practice > unreachable. I've removed the assert in the patch below. > > (FWIW the first hit was during stage2 of a bootstrap, in cfgcleanup.c) > >> Note that the comment in gimple_val_nonnegative_real_p is correct in >> that we really shouldn't recurse (but maybe handle fixed patterns - >> like you do here) as the appropriate way is to have a "nonnegative" >> lattice. SSA name range info may already provide enough info here >> (well, not for reals - time to add basic real range support to VRP!). > > I retained a form of this comment in tree_ssa_name_nonnegative_warnv_p. > > Bootstrapped & regression-tested on x86_64-linux-gnu. I didn't write > a specific test because this is already covered by the testsuite if > the follow-on patch is also applied. OK to install? Ok. Thanks, Richard. > Thanks, > Richard > > > gcc/ > * params.def (PARAM_MAX_SSA_NAME_QUERY_DEPTH): New param. > * doc/invoke.texi (--param max-ssa-name-query-depth): Document. > * fold-const.h (tree_unary_nonnegative_warnv_p) > (tree_single_nonnegative_warnv_p, tree_call_nonnegative_warnv_p) > (tree_expr_nonnegative_warnv_p): Add depth parameters. > * fold-const.c: Include gimple-fold.h and params.h. > (tree_ssa_name_nonnegative_warnv_p): New function. > (tree_unary_nonnegative_warnv_p, tree_binary_nonnegative_warnv_p) > (tree_single_nonnegative_warnv_p, tree_call_nonnegative_warnv_p) > (tree_invalid_nonnegative_warnv_p, tree_expr_nonnegative_warnv_p): > Add a depth parameter and increment it for recursive calls to > tree_expr_nonnegative_warnv_p. Use tree_ssa_name_nonnegative_warnv_p > to handle SSA names. > * gimple-fold.h (gimple_val_nonnegative_real_p): Delete. > (gimple_stmt_nonnegative_warnv_p): Declare. > * tree-vrp.c (remove_range_assertions): Remove assert that condition > cannot be proven false. > (gimple_assign_nonnegative_warnv_p, gimple_call_nonnegative_warnv_p) > (gimple_stmt_nonnegative_warnv_p): Move to... > * gimple-fold.c: ...here. Add depth parameters and pass them > down to the tree routines. Accept statements that aren't > assignments or calls but just return false for them. > (gimple_val_nonnegative_real_p): Delete. > * tree-ssa-math-opts.c (gimple_expand_builtin_pow): Use > tree_expr_nonnegative_p instead of gimple_val_nonnegative_real_p. > Check HONOR_NANs first. > > Index: gcc/params.def > =================================================================== > --- gcc/params.def 2015-10-05 20:45:49.164957708 +0100 > +++ gcc/params.def 2015-10-08 10:59:12.904576852 +0100 > @@ -1152,6 +1152,12 @@ DEFPARAM (PARAM_PARLOOPS_CHUNK_SIZE, > "parloops-chunk-size", > "Chunk size of omp schedule for loops parallelized by parloops", > 0, 0, 0) > + > +DEFPARAM (PARAM_MAX_SSA_NAME_QUERY_DEPTH, > + "max-ssa-name-query-depth", > + "Maximum recursion depth allowed when querying a property of an" > + " SSA name", > + 2, 1, 0) > /* > > Local variables: > Index: gcc/doc/invoke.texi > =================================================================== > --- gcc/doc/invoke.texi 2015-10-07 09:07:20.758346426 +0100 > +++ gcc/doc/invoke.texi 2015-10-08 10:59:12.904576852 +0100 > @@ -11132,6 +11132,10 @@ automaton. The default is 50. > Chunk size of omp schedule for loops parallelized by parloops. The default > is 0. > > +@item max-ssa-name-query-depth > +Maximum depth of recursion when querying properties of SSA names in things > +like fold routines. One level of recursion corresponds to following a > +use-def chain. > @end table > @end table > > Index: gcc/fold-const.h > =================================================================== > --- gcc/fold-const.h 2015-09-25 12:49:13.080824131 +0100 > +++ gcc/fold-const.h 2015-10-08 10:59:12.904576852 +0100 > @@ -132,11 +132,13 @@ extern bool tree_unary_nonzero_warnv_p ( > extern bool tree_binary_nonzero_warnv_p (enum tree_code, tree, tree, tree op1, > bool *); > extern bool tree_single_nonzero_warnv_p (tree, bool *); > -extern bool tree_unary_nonnegative_warnv_p (enum tree_code, tree, tree, bool *); > +extern bool tree_unary_nonnegative_warnv_p (enum tree_code, tree, tree, > + bool *, int); > extern bool tree_binary_nonnegative_warnv_p (enum tree_code, tree, tree, tree, > - bool *); > -extern bool tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p); > -extern bool tree_call_nonnegative_warnv_p (tree, tree, tree, tree, bool *); > + bool *, int); > +extern bool tree_single_nonnegative_warnv_p (tree, bool *, int); > +extern bool tree_call_nonnegative_warnv_p (tree, tree, tree, tree, bool *, > + int); > > extern bool fold_real_zero_addition_p (const_tree, const_tree, int); > extern tree combine_comparisons (location_t, enum tree_code, enum tree_code, > @@ -160,7 +162,7 @@ #define non_lvalue(T) non_lvalue_loc (UN > extern tree non_lvalue_loc (location_t, tree); > > extern bool tree_expr_nonnegative_p (tree); > -extern bool tree_expr_nonnegative_warnv_p (tree, bool *); > +extern bool tree_expr_nonnegative_warnv_p (tree, bool *, int = 0); > extern tree make_range (tree, int *, tree *, tree *, bool *); > extern tree make_range_step (location_t, enum tree_code, tree, tree, tree, > tree *, tree *, int *, bool *); > Index: gcc/fold-const.c > =================================================================== > --- gcc/fold-const.c 2015-10-05 12:31:58.565944573 +0100 > +++ gcc/fold-const.c 2015-10-08 10:59:12.904576852 +0100 > @@ -77,6 +77,8 @@ Software Foundation; either version 3, o > #include "cgraph.h" > #include "generic-match.h" > #include "optabs-query.h" > +#include "gimple-fold.h" > +#include "params.h" > > #ifndef LOAD_EXTEND_OP > #define LOAD_EXTEND_OP(M) UNKNOWN > @@ -12749,6 +12751,12 @@ multiple_of_p (tree type, const_tree top > } > } > > +#define tree_expr_nonnegative_warnv_p(X, Y) \ > + _Pragma ("GCC error \"Use RECURSE for recursive calls\"") 0 > + > +#define RECURSE(X) \ > + ((tree_expr_nonnegative_warnv_p) (X, strict_overflow_p, depth + 1)) > + > /* Return true if CODE or TYPE is known to be non-negative. */ > > static bool > @@ -12765,11 +12773,11 @@ tree_simple_nonnegative_warnv_p (enum tr > /* Return true if (CODE OP0) is known to be non-negative. If the return > value is based on the assumption that signed overflow is undefined, > set *STRICT_OVERFLOW_P to true; otherwise, don't change > - *STRICT_OVERFLOW_P. */ > + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ > > bool > tree_unary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0, > - bool *strict_overflow_p) > + bool *strict_overflow_p, int depth) > { > if (TYPE_UNSIGNED (type)) > return true; > @@ -12791,8 +12799,7 @@ tree_unary_nonnegative_warnv_p (enum tre > case NON_LVALUE_EXPR: > case FLOAT_EXPR: > case FIX_TRUNC_EXPR: > - return tree_expr_nonnegative_warnv_p (op0, > - strict_overflow_p); > + return RECURSE (op0); > > CASE_CONVERT: > { > @@ -12802,21 +12809,18 @@ tree_unary_nonnegative_warnv_p (enum tre > if (TREE_CODE (outer_type) == REAL_TYPE) > { > if (TREE_CODE (inner_type) == REAL_TYPE) > - return tree_expr_nonnegative_warnv_p (op0, > - strict_overflow_p); > + return RECURSE (op0); > if (INTEGRAL_TYPE_P (inner_type)) > { > if (TYPE_UNSIGNED (inner_type)) > return true; > - return tree_expr_nonnegative_warnv_p (op0, > - strict_overflow_p); > + return RECURSE (op0); > } > } > else if (INTEGRAL_TYPE_P (outer_type)) > { > if (TREE_CODE (inner_type) == REAL_TYPE) > - return tree_expr_nonnegative_warnv_p (op0, > - strict_overflow_p); > + return RECURSE (op0); > if (INTEGRAL_TYPE_P (inner_type)) > return TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type) > && TYPE_UNSIGNED (inner_type); > @@ -12835,11 +12839,12 @@ tree_unary_nonnegative_warnv_p (enum tre > /* Return true if (CODE OP0 OP1) is known to be non-negative. If the return > value is based on the assumption that signed overflow is undefined, > set *STRICT_OVERFLOW_P to true; otherwise, don't change > - *STRICT_OVERFLOW_P. */ > + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ > > bool > tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0, > - tree op1, bool *strict_overflow_p) > + tree op1, bool *strict_overflow_p, > + int depth) > { > if (TYPE_UNSIGNED (type)) > return true; > @@ -12849,10 +12854,7 @@ tree_binary_nonnegative_warnv_p (enum tr > case POINTER_PLUS_EXPR: > case PLUS_EXPR: > if (FLOAT_TYPE_P (type)) > - return (tree_expr_nonnegative_warnv_p (op0, > - strict_overflow_p) > - && tree_expr_nonnegative_warnv_p (op1, > - strict_overflow_p)); > + return RECURSE (op0) && RECURSE (op1); > > /* zero_extend(x) + zero_extend(y) is non-negative if x and y are > both unsigned and at least 2 bits shorter than the result. */ > @@ -12878,8 +12880,7 @@ tree_binary_nonnegative_warnv_p (enum tr > /* x * x is always non-negative for floating point x > or without overflow. */ > if (operand_equal_p (op0, op1, 0) > - || (tree_expr_nonnegative_warnv_p (op0, strict_overflow_p) > - && tree_expr_nonnegative_warnv_p (op1, strict_overflow_p))) > + || (RECURSE (op0) && RECURSE (op1))) > { > if (ANY_INTEGRAL_TYPE_P (type) > && TYPE_OVERFLOW_UNDEFINED (type)) > @@ -12928,10 +12929,7 @@ tree_binary_nonnegative_warnv_p (enum tr > > case BIT_AND_EXPR: > case MAX_EXPR: > - return (tree_expr_nonnegative_warnv_p (op0, > - strict_overflow_p) > - || tree_expr_nonnegative_warnv_p (op1, > - strict_overflow_p)); > + return RECURSE (op0) || RECURSE (op1); > > case BIT_IOR_EXPR: > case BIT_XOR_EXPR: > @@ -12941,17 +12939,14 @@ tree_binary_nonnegative_warnv_p (enum tr > case CEIL_DIV_EXPR: > case FLOOR_DIV_EXPR: > case ROUND_DIV_EXPR: > - return (tree_expr_nonnegative_warnv_p (op0, > - strict_overflow_p) > - && tree_expr_nonnegative_warnv_p (op1, > - strict_overflow_p)); > + return RECURSE (op0) && RECURSE (op1); > > case TRUNC_MOD_EXPR: > case CEIL_MOD_EXPR: > case FLOOR_MOD_EXPR: > case ROUND_MOD_EXPR: > - return tree_expr_nonnegative_warnv_p (op0, > - strict_overflow_p); > + return RECURSE (op0); > + > default: > return tree_simple_nonnegative_warnv_p (code, type); > } > @@ -12960,13 +12955,32 @@ tree_binary_nonnegative_warnv_p (enum tr > return false; > } > > +/* Return true if SSA name T is known to be non-negative. If the return > + value is based on the assumption that signed overflow is undefined, > + set *STRICT_OVERFLOW_P to true; otherwise, don't change > + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ > + > +static bool > +tree_ssa_name_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth) > +{ > + /* Limit the depth of recursion to avoid quadratic behavior. > + This is expected to catch almost all occurrences in practice. > + If this code misses important cases that unbounded recursion > + would not, passes that need this information could be revised > + to provide it through dataflow propagation. */ > + if (depth < PARAM_VALUE (PARAM_MAX_SSA_NAME_QUERY_DEPTH)) > + return gimple_stmt_nonnegative_warnv_p (SSA_NAME_DEF_STMT (t), > + strict_overflow_p, depth); > + return tree_simple_nonnegative_warnv_p (TREE_CODE (t), TREE_TYPE (t)); > +} > + > /* Return true if T is known to be non-negative. If the return > value is based on the assumption that signed overflow is undefined, > set *STRICT_OVERFLOW_P to true; otherwise, don't change > - *STRICT_OVERFLOW_P. */ > + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ > > bool > -tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p) > +tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth) > { > if (TYPE_UNSIGNED (TREE_TYPE (t))) > return true; > @@ -12983,26 +12997,24 @@ tree_single_nonnegative_warnv_p (tree t, > return ! FIXED_VALUE_NEGATIVE (TREE_FIXED_CST (t)); > > case COND_EXPR: > - return (tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 1), > - strict_overflow_p) > - && tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 2), > - strict_overflow_p)); > + return RECURSE (TREE_OPERAND (t, 1)) && RECURSE (TREE_OPERAND (t, 2)); > + > + case SSA_NAME: > + return tree_ssa_name_nonnegative_warnv_p (t, strict_overflow_p, depth); > + > default: > - return tree_simple_nonnegative_warnv_p (TREE_CODE (t), > - TREE_TYPE (t)); > + return tree_simple_nonnegative_warnv_p (TREE_CODE (t), TREE_TYPE (t)); > } > - /* We don't know sign of `t', so be conservative and return false. */ > - return false; > } > > /* Return true if T is known to be non-negative. If the return > value is based on the assumption that signed overflow is undefined, > set *STRICT_OVERFLOW_P to true; otherwise, don't change > - *STRICT_OVERFLOW_P. */ > + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ > > bool > -tree_call_nonnegative_warnv_p (tree type, tree fndecl, > - tree arg0, tree arg1, bool *strict_overflow_p) > +tree_call_nonnegative_warnv_p (tree type, tree fndecl, tree arg0, tree arg1, > + bool *strict_overflow_p, int depth) > { > if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL) > switch (DECL_FUNCTION_CODE (fndecl)) > @@ -13033,8 +13045,7 @@ tree_call_nonnegative_warnv_p (tree type > /* sqrt(-0.0) is -0.0. */ > if (!HONOR_SIGNED_ZEROS (element_mode (type))) > return true; > - return tree_expr_nonnegative_warnv_p (arg0, > - strict_overflow_p); > + return RECURSE (arg0); > > CASE_FLT_FN (BUILT_IN_ASINH): > CASE_FLT_FN (BUILT_IN_ATAN): > @@ -13072,27 +13083,19 @@ tree_call_nonnegative_warnv_p (tree type > CASE_FLT_FN (BUILT_IN_TANH): > CASE_FLT_FN (BUILT_IN_TRUNC): > /* True if the 1st argument is nonnegative. */ > - return tree_expr_nonnegative_warnv_p (arg0, > - strict_overflow_p); > + return RECURSE (arg0); > > CASE_FLT_FN (BUILT_IN_FMAX): > /* True if the 1st OR 2nd arguments are nonnegative. */ > - return (tree_expr_nonnegative_warnv_p (arg0, > - strict_overflow_p) > - || (tree_expr_nonnegative_warnv_p (arg1, > - strict_overflow_p))); > + return RECURSE (arg0) || RECURSE (arg1); > > CASE_FLT_FN (BUILT_IN_FMIN): > /* True if the 1st AND 2nd arguments are nonnegative. */ > - return (tree_expr_nonnegative_warnv_p (arg0, > - strict_overflow_p) > - && (tree_expr_nonnegative_warnv_p (arg1, > - strict_overflow_p))); > + return RECURSE (arg0) && RECURSE (arg1); > > CASE_FLT_FN (BUILT_IN_COPYSIGN): > /* True if the 2nd argument is nonnegative. */ > - return tree_expr_nonnegative_warnv_p (arg1, > - strict_overflow_p); > + return RECURSE (arg1); > > CASE_FLT_FN (BUILT_IN_POWI): > /* True if the 1st argument is nonnegative or the second > @@ -13100,8 +13103,7 @@ tree_call_nonnegative_warnv_p (tree type > if (TREE_CODE (arg1) == INTEGER_CST > && (TREE_INT_CST_LOW (arg1) & 1) == 0) > return true; > - return tree_expr_nonnegative_warnv_p (arg0, > - strict_overflow_p); > + return RECURSE (arg0); > > CASE_FLT_FN (BUILT_IN_POW): > /* True if the 1st argument is nonnegative or the second > @@ -13121,23 +13123,21 @@ tree_call_nonnegative_warnv_p (tree type > return true; > } > } > - return tree_expr_nonnegative_warnv_p (arg0, > - strict_overflow_p); > + return RECURSE (arg0); > > default: > break; > } > - return tree_simple_nonnegative_warnv_p (CALL_EXPR, > - type); > + return tree_simple_nonnegative_warnv_p (CALL_EXPR, type); > } > > /* Return true if T is known to be non-negative. If the return > value is based on the assumption that signed overflow is undefined, > set *STRICT_OVERFLOW_P to true; otherwise, don't change > - *STRICT_OVERFLOW_P. */ > + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ > > static bool > -tree_invalid_nonnegative_warnv_p (tree t, bool *strict_overflow_p) > +tree_invalid_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth) > { > enum tree_code code = TREE_CODE (t); > if (TYPE_UNSIGNED (TREE_TYPE (t))) > @@ -13153,7 +13153,7 @@ tree_invalid_nonnegative_warnv_p (tree t > /* If the initializer is non-void, then it's a normal expression > that will be assigned to the slot. */ > if (!VOID_TYPE_P (t)) > - return tree_expr_nonnegative_warnv_p (t, strict_overflow_p); > + return RECURSE (t); > > /* Otherwise, the initializer sets the slot in some way. One common > way is an assignment statement at the end of the initializer. */ > @@ -13171,8 +13171,7 @@ tree_invalid_nonnegative_warnv_p (tree t > } > if (TREE_CODE (t) == MODIFY_EXPR > && TREE_OPERAND (t, 0) == temp) > - return tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 1), > - strict_overflow_p); > + return RECURSE (TREE_OPERAND (t, 1)); > > return false; > } > @@ -13186,35 +13185,33 @@ tree_invalid_nonnegative_warnv_p (tree t > get_callee_fndecl (t), > arg0, > arg1, > - strict_overflow_p); > + strict_overflow_p, depth); > } > case COMPOUND_EXPR: > case MODIFY_EXPR: > - return tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 1), > - strict_overflow_p); > + return RECURSE (TREE_OPERAND (t, 1)); > + > case BIND_EXPR: > - return tree_expr_nonnegative_warnv_p (expr_last (TREE_OPERAND (t, 1)), > - strict_overflow_p); > + return RECURSE (expr_last (TREE_OPERAND (t, 1))); > + > case SAVE_EXPR: > - return tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 0), > - strict_overflow_p); > + return RECURSE (TREE_OPERAND (t, 0)); > > default: > - return tree_simple_nonnegative_warnv_p (TREE_CODE (t), > - TREE_TYPE (t)); > + return tree_simple_nonnegative_warnv_p (TREE_CODE (t), TREE_TYPE (t)); > } > - > - /* We don't know sign of `t', so be conservative and return false. */ > - return false; > } > > +#undef RECURSE > +#undef tree_expr_nonnegative_warnv_p > + > /* Return true if T is known to be non-negative. If the return > value is based on the assumption that signed overflow is undefined, > set *STRICT_OVERFLOW_P to true; otherwise, don't change > - *STRICT_OVERFLOW_P. */ > + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ > > bool > -tree_expr_nonnegative_warnv_p (tree t, bool *strict_overflow_p) > +tree_expr_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth) > { > enum tree_code code; > if (t == error_mark_node) > @@ -13229,18 +13226,18 @@ tree_expr_nonnegative_warnv_p (tree t, b > TREE_TYPE (t), > TREE_OPERAND (t, 0), > TREE_OPERAND (t, 1), > - strict_overflow_p); > + strict_overflow_p, depth); > > case tcc_unary: > return tree_unary_nonnegative_warnv_p (TREE_CODE (t), > TREE_TYPE (t), > TREE_OPERAND (t, 0), > - strict_overflow_p); > + strict_overflow_p, depth); > > case tcc_constant: > case tcc_declaration: > case tcc_reference: > - return tree_single_nonnegative_warnv_p (t, strict_overflow_p); > + return tree_single_nonnegative_warnv_p (t, strict_overflow_p, depth); > > default: > break; > @@ -13255,12 +13252,12 @@ tree_expr_nonnegative_warnv_p (tree t, b > TREE_TYPE (t), > TREE_OPERAND (t, 0), > TREE_OPERAND (t, 1), > - strict_overflow_p); > + strict_overflow_p, depth); > case TRUTH_NOT_EXPR: > return tree_unary_nonnegative_warnv_p (TREE_CODE (t), > TREE_TYPE (t), > TREE_OPERAND (t, 0), > - strict_overflow_p); > + strict_overflow_p, depth); > > case COND_EXPR: > case CONSTRUCTOR: > @@ -13269,10 +13266,10 @@ tree_expr_nonnegative_warnv_p (tree t, b > case ADDR_EXPR: > case WITH_SIZE_EXPR: > case SSA_NAME: > - return tree_single_nonnegative_warnv_p (t, strict_overflow_p); > + return tree_single_nonnegative_warnv_p (t, strict_overflow_p, depth); > > default: > - return tree_invalid_nonnegative_warnv_p (t, strict_overflow_p); > + return tree_invalid_nonnegative_warnv_p (t, strict_overflow_p, depth); > } > } > > Index: gcc/gimple-fold.h > =================================================================== > --- gcc/gimple-fold.h 2015-09-25 12:49:13.928814656 +0100 > +++ gcc/gimple-fold.h 2015-10-08 10:59:12.904576852 +0100 > @@ -48,7 +48,6 @@ extern tree gimple_get_virt_method_for_b > extern tree gimple_get_virt_method_for_vtable (HOST_WIDE_INT, tree, > unsigned HOST_WIDE_INT, > bool *can_refer = NULL); > -extern bool gimple_val_nonnegative_real_p (tree); > extern tree gimple_fold_indirect_ref (tree); > extern bool arith_code_with_undefined_signed_overflow (tree_code); > extern gimple_seq rewrite_to_defined_overflow (gimple *); > @@ -113,6 +112,8 @@ gimple_convert (gimple_seq *seq, tree ty > return gimple_convert (seq, UNKNOWN_LOCATION, type, op); > } > > +extern bool gimple_stmt_nonnegative_warnv_p (gimple *, bool *, int = 0); > + > /* In gimple-match.c. */ > extern tree gimple_simplify (enum tree_code, tree, tree, > gimple_seq *, tree (*)(tree)); > Index: gcc/tree-vrp.c > =================================================================== > --- gcc/tree-vrp.c 2015-10-05 20:45:48.964959975 +0100 > +++ gcc/tree-vrp.c 2015-10-08 10:59:12.908576806 +0100 > @@ -1007,80 +1007,6 @@ usable_range_p (value_range *vr, bool *s > return true; > } > > - > -/* Return true if the result of assignment STMT is know to be non-negative. > - If the return value is based on the assumption that signed overflow is > - undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change > - *STRICT_OVERFLOW_P.*/ > - > -static bool > -gimple_assign_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p) > -{ > - enum tree_code code = gimple_assign_rhs_code (stmt); > - switch (get_gimple_rhs_class (code)) > - { > - case GIMPLE_UNARY_RHS: > - return tree_unary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt), > - gimple_expr_type (stmt), > - gimple_assign_rhs1 (stmt), > - strict_overflow_p); > - case GIMPLE_BINARY_RHS: > - return tree_binary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt), > - gimple_expr_type (stmt), > - gimple_assign_rhs1 (stmt), > - gimple_assign_rhs2 (stmt), > - strict_overflow_p); > - case GIMPLE_TERNARY_RHS: > - return false; > - case GIMPLE_SINGLE_RHS: > - return tree_single_nonnegative_warnv_p (gimple_assign_rhs1 (stmt), > - strict_overflow_p); > - case GIMPLE_INVALID_RHS: > - gcc_unreachable (); > - default: > - gcc_unreachable (); > - } > -} > - > -/* Return true if return value of call STMT is know to be non-negative. > - If the return value is based on the assumption that signed overflow is > - undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change > - *STRICT_OVERFLOW_P.*/ > - > -static bool > -gimple_call_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p) > -{ > - tree arg0 = gimple_call_num_args (stmt) > 0 ? > - gimple_call_arg (stmt, 0) : NULL_TREE; > - tree arg1 = gimple_call_num_args (stmt) > 1 ? > - gimple_call_arg (stmt, 1) : NULL_TREE; > - > - return tree_call_nonnegative_warnv_p (gimple_expr_type (stmt), > - gimple_call_fndecl (stmt), > - arg0, > - arg1, > - strict_overflow_p); > -} > - > -/* Return true if STMT is know to compute a non-negative value. > - If the return value is based on the assumption that signed overflow is > - undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change > - *STRICT_OVERFLOW_P.*/ > - > -static bool > -gimple_stmt_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p) > -{ > - switch (gimple_code (stmt)) > - { > - case GIMPLE_ASSIGN: > - return gimple_assign_nonnegative_warnv_p (stmt, strict_overflow_p); > - case GIMPLE_CALL: > - return gimple_call_nonnegative_warnv_p (stmt, strict_overflow_p); > - default: > - gcc_unreachable (); > - } > -} > - > /* Return true if the result of assignment STMT is know to be non-zero. > If the return value is based on the assumption that signed overflow is > undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change > @@ -6858,12 +6784,9 @@ remove_range_assertions (void) > tree lhs = gimple_assign_lhs (stmt); > tree rhs = gimple_assign_rhs1 (stmt); > tree var; > - tree cond = fold (ASSERT_EXPR_COND (rhs)); > use_operand_p use_p; > imm_use_iterator iter; > > - gcc_assert (cond != boolean_false_node); > - > var = ASSERT_EXPR_VAR (rhs); > gcc_assert (TREE_CODE (var) == SSA_NAME); > > Index: gcc/gimple-fold.c > =================================================================== > --- gcc/gimple-fold.c 2015-10-07 09:07:21.198341367 +0100 > +++ gcc/gimple-fold.c 2015-10-08 10:59:12.904576852 +0100 > @@ -5773,137 +5773,6 @@ gimple_get_virt_method_for_binfo (HOST_W > return gimple_get_virt_method_for_vtable (token, v, offset, can_refer); > } > > -/* Return true iff VAL is a gimple expression that is known to be > - non-negative. Restricted to floating-point inputs. */ > - > -bool > -gimple_val_nonnegative_real_p (tree val) > -{ > - gimple *def_stmt; > - > - gcc_assert (val && SCALAR_FLOAT_TYPE_P (TREE_TYPE (val))); > - > - /* Use existing logic for non-gimple trees. */ > - if (tree_expr_nonnegative_p (val)) > - return true; > - > - if (TREE_CODE (val) != SSA_NAME) > - return false; > - > - /* Currently we look only at the immediately defining statement > - to make this determination, since recursion on defining > - statements of operands can lead to quadratic behavior in the > - worst case. This is expected to catch almost all occurrences > - in practice. It would be possible to implement limited-depth > - recursion if important cases are lost. Alternatively, passes > - that need this information (such as the pow/powi lowering code > - in the cse_sincos pass) could be revised to provide it through > - dataflow propagation. */ > - > - def_stmt = SSA_NAME_DEF_STMT (val); > - > - if (is_gimple_assign (def_stmt)) > - { > - tree op0, op1; > - > - /* See fold-const.c:tree_expr_nonnegative_p for additional > - cases that could be handled with recursion. */ > - > - switch (gimple_assign_rhs_code (def_stmt)) > - { > - case ABS_EXPR: > - /* Always true for floating-point operands. */ > - return true; > - > - case MULT_EXPR: > - /* True if the two operands are identical (since we are > - restricted to floating-point inputs). */ > - op0 = gimple_assign_rhs1 (def_stmt); > - op1 = gimple_assign_rhs2 (def_stmt); > - > - if (op0 == op1 > - || operand_equal_p (op0, op1, 0)) > - return true; > - > - default: > - return false; > - } > - } > - else if (is_gimple_call (def_stmt)) > - { > - tree fndecl = gimple_call_fndecl (def_stmt); > - if (fndecl > - && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL) > - { > - tree arg1; > - > - switch (DECL_FUNCTION_CODE (fndecl)) > - { > - CASE_FLT_FN (BUILT_IN_ACOS): > - CASE_FLT_FN (BUILT_IN_ACOSH): > - CASE_FLT_FN (BUILT_IN_CABS): > - CASE_FLT_FN (BUILT_IN_COSH): > - CASE_FLT_FN (BUILT_IN_ERFC): > - CASE_FLT_FN (BUILT_IN_EXP): > - CASE_FLT_FN (BUILT_IN_EXP10): > - CASE_FLT_FN (BUILT_IN_EXP2): > - CASE_FLT_FN (BUILT_IN_FABS): > - CASE_FLT_FN (BUILT_IN_FDIM): > - CASE_FLT_FN (BUILT_IN_HYPOT): > - CASE_FLT_FN (BUILT_IN_POW10): > - return true; > - > - CASE_FLT_FN (BUILT_IN_SQRT): > - /* sqrt(-0.0) is -0.0, and sqrt is not defined over other > - nonnegative inputs. */ > - if (!HONOR_SIGNED_ZEROS (val)) > - return true; > - > - break; > - > - CASE_FLT_FN (BUILT_IN_POWI): > - /* True if the second argument is an even integer. */ > - arg1 = gimple_call_arg (def_stmt, 1); > - > - if (TREE_CODE (arg1) == INTEGER_CST > - && (TREE_INT_CST_LOW (arg1) & 1) == 0) > - return true; > - > - break; > - > - CASE_FLT_FN (BUILT_IN_POW): > - /* True if the second argument is an even integer-valued > - real. */ > - arg1 = gimple_call_arg (def_stmt, 1); > - > - if (TREE_CODE (arg1) == REAL_CST) > - { > - REAL_VALUE_TYPE c; > - HOST_WIDE_INT n; > - > - c = TREE_REAL_CST (arg1); > - n = real_to_integer (&c); > - > - if ((n & 1) == 0) > - { > - REAL_VALUE_TYPE cint; > - real_from_integer (&cint, VOIDmode, n, SIGNED); > - if (real_identical (&c, &cint)) > - return true; > - } > - } > - > - break; > - > - default: > - return false; > - } > - } > - } > - > - return false; > -} > - > /* Given a pointer value OP0, return a simplified version of an > indirection through OP0, or NULL_TREE if no simplification is > possible. Note that the resulting type may be different from > @@ -6280,3 +6149,80 @@ gimple_convert (gimple_seq *seq, locatio > return op; > return gimple_build (seq, loc, NOP_EXPR, type, op); > } > + > +/* Return true if the result of assignment STMT is known to be non-negative. > + If the return value is based on the assumption that signed overflow is > + undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change > + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ > + > +static bool > +gimple_assign_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p, > + int depth) > +{ > + enum tree_code code = gimple_assign_rhs_code (stmt); > + switch (get_gimple_rhs_class (code)) > + { > + case GIMPLE_UNARY_RHS: > + return tree_unary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt), > + gimple_expr_type (stmt), > + gimple_assign_rhs1 (stmt), > + strict_overflow_p, depth); > + case GIMPLE_BINARY_RHS: > + return tree_binary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt), > + gimple_expr_type (stmt), > + gimple_assign_rhs1 (stmt), > + gimple_assign_rhs2 (stmt), > + strict_overflow_p, depth); > + case GIMPLE_TERNARY_RHS: > + return false; > + case GIMPLE_SINGLE_RHS: > + return tree_single_nonnegative_warnv_p (gimple_assign_rhs1 (stmt), > + strict_overflow_p, depth); > + case GIMPLE_INVALID_RHS: > + break; > + } > + gcc_unreachable (); > +} > + > +/* Return true if return value of call STMT is known to be non-negative. > + If the return value is based on the assumption that signed overflow is > + undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change > + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ > + > +static bool > +gimple_call_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p, > + int depth) > +{ > + tree arg0 = gimple_call_num_args (stmt) > 0 ? > + gimple_call_arg (stmt, 0) : NULL_TREE; > + tree arg1 = gimple_call_num_args (stmt) > 1 ? > + gimple_call_arg (stmt, 1) : NULL_TREE; > + > + return tree_call_nonnegative_warnv_p (gimple_expr_type (stmt), > + gimple_call_fndecl (stmt), > + arg0, > + arg1, > + strict_overflow_p, depth); > +} > + > +/* Return true if STMT is known to compute a non-negative value. > + If the return value is based on the assumption that signed overflow is > + undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change > + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ > + > +bool > +gimple_stmt_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p, > + int depth) > +{ > + switch (gimple_code (stmt)) > + { > + case GIMPLE_ASSIGN: > + return gimple_assign_nonnegative_warnv_p (stmt, strict_overflow_p, > + depth); > + case GIMPLE_CALL: > + return gimple_call_nonnegative_warnv_p (stmt, strict_overflow_p, > + depth); > + default: > + return false; > + } > +} > Index: gcc/tree-ssa-math-opts.c > =================================================================== > --- gcc/tree-ssa-math-opts.c 2015-10-05 12:34:55.923949581 +0100 > +++ gcc/tree-ssa-math-opts.c 2015-10-08 10:59:12.908576806 +0100 > @@ -1526,7 +1526,7 @@ gimple_expand_builtin_pow (gimple_stmt_i > > if (flag_unsafe_math_optimizations > && cbrtfn > - && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode)) > + && (!HONOR_NANS (mode) || tree_expr_nonnegative_p (arg0)) > && real_equal (&c, &dconst1_3)) > return build_and_insert_call (gsi, loc, cbrtfn, arg0); > > @@ -1538,7 +1538,7 @@ gimple_expand_builtin_pow (gimple_stmt_i > if (flag_unsafe_math_optimizations > && sqrtfn > && cbrtfn > - && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode)) > + && (!HONOR_NANS (mode) || tree_expr_nonnegative_p (arg0)) > && speed_p > && hw_sqrt_exists > && real_equal (&c, &dconst1_6)) > @@ -1594,7 +1594,7 @@ gimple_expand_builtin_pow (gimple_stmt_i > > if (flag_unsafe_math_optimizations > && cbrtfn > - && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode)) > + && (!HONOR_NANS (mode) || tree_expr_nonnegative_p (arg0)) > && real_identical (&c2, &c) > && !c2_is_int > && optimize_function_for_speed_p (cfun) >
Index: gcc/params.def =================================================================== --- gcc/params.def 2015-10-05 20:45:49.164957708 +0100 +++ gcc/params.def 2015-10-08 10:59:12.904576852 +0100 @@ -1152,6 +1152,12 @@ DEFPARAM (PARAM_PARLOOPS_CHUNK_SIZE, "parloops-chunk-size", "Chunk size of omp schedule for loops parallelized by parloops", 0, 0, 0) + +DEFPARAM (PARAM_MAX_SSA_NAME_QUERY_DEPTH, + "max-ssa-name-query-depth", + "Maximum recursion depth allowed when querying a property of an" + " SSA name", + 2, 1, 0) /* Local variables: Index: gcc/doc/invoke.texi =================================================================== --- gcc/doc/invoke.texi 2015-10-07 09:07:20.758346426 +0100 +++ gcc/doc/invoke.texi 2015-10-08 10:59:12.904576852 +0100 @@ -11132,6 +11132,10 @@ automaton. The default is 50. Chunk size of omp schedule for loops parallelized by parloops. The default is 0. +@item max-ssa-name-query-depth +Maximum depth of recursion when querying properties of SSA names in things +like fold routines. One level of recursion corresponds to following a +use-def chain. @end table @end table Index: gcc/fold-const.h =================================================================== --- gcc/fold-const.h 2015-09-25 12:49:13.080824131 +0100 +++ gcc/fold-const.h 2015-10-08 10:59:12.904576852 +0100 @@ -132,11 +132,13 @@ extern bool tree_unary_nonzero_warnv_p ( extern bool tree_binary_nonzero_warnv_p (enum tree_code, tree, tree, tree op1, bool *); extern bool tree_single_nonzero_warnv_p (tree, bool *); -extern bool tree_unary_nonnegative_warnv_p (enum tree_code, tree, tree, bool *); +extern bool tree_unary_nonnegative_warnv_p (enum tree_code, tree, tree, + bool *, int); extern bool tree_binary_nonnegative_warnv_p (enum tree_code, tree, tree, tree, - bool *); -extern bool tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p); -extern bool tree_call_nonnegative_warnv_p (tree, tree, tree, tree, bool *); + bool *, int); +extern bool tree_single_nonnegative_warnv_p (tree, bool *, int); +extern bool tree_call_nonnegative_warnv_p (tree, tree, tree, tree, bool *, + int); extern bool fold_real_zero_addition_p (const_tree, const_tree, int); extern tree combine_comparisons (location_t, enum tree_code, enum tree_code, @@ -160,7 +162,7 @@ #define non_lvalue(T) non_lvalue_loc (UN extern tree non_lvalue_loc (location_t, tree); extern bool tree_expr_nonnegative_p (tree); -extern bool tree_expr_nonnegative_warnv_p (tree, bool *); +extern bool tree_expr_nonnegative_warnv_p (tree, bool *, int = 0); extern tree make_range (tree, int *, tree *, tree *, bool *); extern tree make_range_step (location_t, enum tree_code, tree, tree, tree, tree *, tree *, int *, bool *); Index: gcc/fold-const.c =================================================================== --- gcc/fold-const.c 2015-10-05 12:31:58.565944573 +0100 +++ gcc/fold-const.c 2015-10-08 10:59:12.904576852 +0100 @@ -77,6 +77,8 @@ Software Foundation; either version 3, o #include "cgraph.h" #include "generic-match.h" #include "optabs-query.h" +#include "gimple-fold.h" +#include "params.h" #ifndef LOAD_EXTEND_OP #define LOAD_EXTEND_OP(M) UNKNOWN @@ -12749,6 +12751,12 @@ multiple_of_p (tree type, const_tree top } } +#define tree_expr_nonnegative_warnv_p(X, Y) \ + _Pragma ("GCC error \"Use RECURSE for recursive calls\"") 0 + +#define RECURSE(X) \ + ((tree_expr_nonnegative_warnv_p) (X, strict_overflow_p, depth + 1)) + /* Return true if CODE or TYPE is known to be non-negative. */ static bool @@ -12765,11 +12773,11 @@ tree_simple_nonnegative_warnv_p (enum tr /* Return true if (CODE OP0) is known to be non-negative. If the return value is based on the assumption that signed overflow is undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change - *STRICT_OVERFLOW_P. */ + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ bool tree_unary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0, - bool *strict_overflow_p) + bool *strict_overflow_p, int depth) { if (TYPE_UNSIGNED (type)) return true; @@ -12791,8 +12799,7 @@ tree_unary_nonnegative_warnv_p (enum tre case NON_LVALUE_EXPR: case FLOAT_EXPR: case FIX_TRUNC_EXPR: - return tree_expr_nonnegative_warnv_p (op0, - strict_overflow_p); + return RECURSE (op0); CASE_CONVERT: { @@ -12802,21 +12809,18 @@ tree_unary_nonnegative_warnv_p (enum tre if (TREE_CODE (outer_type) == REAL_TYPE) { if (TREE_CODE (inner_type) == REAL_TYPE) - return tree_expr_nonnegative_warnv_p (op0, - strict_overflow_p); + return RECURSE (op0); if (INTEGRAL_TYPE_P (inner_type)) { if (TYPE_UNSIGNED (inner_type)) return true; - return tree_expr_nonnegative_warnv_p (op0, - strict_overflow_p); + return RECURSE (op0); } } else if (INTEGRAL_TYPE_P (outer_type)) { if (TREE_CODE (inner_type) == REAL_TYPE) - return tree_expr_nonnegative_warnv_p (op0, - strict_overflow_p); + return RECURSE (op0); if (INTEGRAL_TYPE_P (inner_type)) return TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type) && TYPE_UNSIGNED (inner_type); @@ -12835,11 +12839,12 @@ tree_unary_nonnegative_warnv_p (enum tre /* Return true if (CODE OP0 OP1) is known to be non-negative. If the return value is based on the assumption that signed overflow is undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change - *STRICT_OVERFLOW_P. */ + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ bool tree_binary_nonnegative_warnv_p (enum tree_code code, tree type, tree op0, - tree op1, bool *strict_overflow_p) + tree op1, bool *strict_overflow_p, + int depth) { if (TYPE_UNSIGNED (type)) return true; @@ -12849,10 +12854,7 @@ tree_binary_nonnegative_warnv_p (enum tr case POINTER_PLUS_EXPR: case PLUS_EXPR: if (FLOAT_TYPE_P (type)) - return (tree_expr_nonnegative_warnv_p (op0, - strict_overflow_p) - && tree_expr_nonnegative_warnv_p (op1, - strict_overflow_p)); + return RECURSE (op0) && RECURSE (op1); /* zero_extend(x) + zero_extend(y) is non-negative if x and y are both unsigned and at least 2 bits shorter than the result. */ @@ -12878,8 +12880,7 @@ tree_binary_nonnegative_warnv_p (enum tr /* x * x is always non-negative for floating point x or without overflow. */ if (operand_equal_p (op0, op1, 0) - || (tree_expr_nonnegative_warnv_p (op0, strict_overflow_p) - && tree_expr_nonnegative_warnv_p (op1, strict_overflow_p))) + || (RECURSE (op0) && RECURSE (op1))) { if (ANY_INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_UNDEFINED (type)) @@ -12928,10 +12929,7 @@ tree_binary_nonnegative_warnv_p (enum tr case BIT_AND_EXPR: case MAX_EXPR: - return (tree_expr_nonnegative_warnv_p (op0, - strict_overflow_p) - || tree_expr_nonnegative_warnv_p (op1, - strict_overflow_p)); + return RECURSE (op0) || RECURSE (op1); case BIT_IOR_EXPR: case BIT_XOR_EXPR: @@ -12941,17 +12939,14 @@ tree_binary_nonnegative_warnv_p (enum tr case CEIL_DIV_EXPR: case FLOOR_DIV_EXPR: case ROUND_DIV_EXPR: - return (tree_expr_nonnegative_warnv_p (op0, - strict_overflow_p) - && tree_expr_nonnegative_warnv_p (op1, - strict_overflow_p)); + return RECURSE (op0) && RECURSE (op1); case TRUNC_MOD_EXPR: case CEIL_MOD_EXPR: case FLOOR_MOD_EXPR: case ROUND_MOD_EXPR: - return tree_expr_nonnegative_warnv_p (op0, - strict_overflow_p); + return RECURSE (op0); + default: return tree_simple_nonnegative_warnv_p (code, type); } @@ -12960,13 +12955,32 @@ tree_binary_nonnegative_warnv_p (enum tr return false; } +/* Return true if SSA name T is known to be non-negative. If the return + value is based on the assumption that signed overflow is undefined, + set *STRICT_OVERFLOW_P to true; otherwise, don't change + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ + +static bool +tree_ssa_name_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth) +{ + /* Limit the depth of recursion to avoid quadratic behavior. + This is expected to catch almost all occurrences in practice. + If this code misses important cases that unbounded recursion + would not, passes that need this information could be revised + to provide it through dataflow propagation. */ + if (depth < PARAM_VALUE (PARAM_MAX_SSA_NAME_QUERY_DEPTH)) + return gimple_stmt_nonnegative_warnv_p (SSA_NAME_DEF_STMT (t), + strict_overflow_p, depth); + return tree_simple_nonnegative_warnv_p (TREE_CODE (t), TREE_TYPE (t)); +} + /* Return true if T is known to be non-negative. If the return value is based on the assumption that signed overflow is undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change - *STRICT_OVERFLOW_P. */ + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ bool -tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p) +tree_single_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth) { if (TYPE_UNSIGNED (TREE_TYPE (t))) return true; @@ -12983,26 +12997,24 @@ tree_single_nonnegative_warnv_p (tree t, return ! FIXED_VALUE_NEGATIVE (TREE_FIXED_CST (t)); case COND_EXPR: - return (tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 1), - strict_overflow_p) - && tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 2), - strict_overflow_p)); + return RECURSE (TREE_OPERAND (t, 1)) && RECURSE (TREE_OPERAND (t, 2)); + + case SSA_NAME: + return tree_ssa_name_nonnegative_warnv_p (t, strict_overflow_p, depth); + default: - return tree_simple_nonnegative_warnv_p (TREE_CODE (t), - TREE_TYPE (t)); + return tree_simple_nonnegative_warnv_p (TREE_CODE (t), TREE_TYPE (t)); } - /* We don't know sign of `t', so be conservative and return false. */ - return false; } /* Return true if T is known to be non-negative. If the return value is based on the assumption that signed overflow is undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change - *STRICT_OVERFLOW_P. */ + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ bool -tree_call_nonnegative_warnv_p (tree type, tree fndecl, - tree arg0, tree arg1, bool *strict_overflow_p) +tree_call_nonnegative_warnv_p (tree type, tree fndecl, tree arg0, tree arg1, + bool *strict_overflow_p, int depth) { if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL) switch (DECL_FUNCTION_CODE (fndecl)) @@ -13033,8 +13045,7 @@ tree_call_nonnegative_warnv_p (tree type /* sqrt(-0.0) is -0.0. */ if (!HONOR_SIGNED_ZEROS (element_mode (type))) return true; - return tree_expr_nonnegative_warnv_p (arg0, - strict_overflow_p); + return RECURSE (arg0); CASE_FLT_FN (BUILT_IN_ASINH): CASE_FLT_FN (BUILT_IN_ATAN): @@ -13072,27 +13083,19 @@ tree_call_nonnegative_warnv_p (tree type CASE_FLT_FN (BUILT_IN_TANH): CASE_FLT_FN (BUILT_IN_TRUNC): /* True if the 1st argument is nonnegative. */ - return tree_expr_nonnegative_warnv_p (arg0, - strict_overflow_p); + return RECURSE (arg0); CASE_FLT_FN (BUILT_IN_FMAX): /* True if the 1st OR 2nd arguments are nonnegative. */ - return (tree_expr_nonnegative_warnv_p (arg0, - strict_overflow_p) - || (tree_expr_nonnegative_warnv_p (arg1, - strict_overflow_p))); + return RECURSE (arg0) || RECURSE (arg1); CASE_FLT_FN (BUILT_IN_FMIN): /* True if the 1st AND 2nd arguments are nonnegative. */ - return (tree_expr_nonnegative_warnv_p (arg0, - strict_overflow_p) - && (tree_expr_nonnegative_warnv_p (arg1, - strict_overflow_p))); + return RECURSE (arg0) && RECURSE (arg1); CASE_FLT_FN (BUILT_IN_COPYSIGN): /* True if the 2nd argument is nonnegative. */ - return tree_expr_nonnegative_warnv_p (arg1, - strict_overflow_p); + return RECURSE (arg1); CASE_FLT_FN (BUILT_IN_POWI): /* True if the 1st argument is nonnegative or the second @@ -13100,8 +13103,7 @@ tree_call_nonnegative_warnv_p (tree type if (TREE_CODE (arg1) == INTEGER_CST && (TREE_INT_CST_LOW (arg1) & 1) == 0) return true; - return tree_expr_nonnegative_warnv_p (arg0, - strict_overflow_p); + return RECURSE (arg0); CASE_FLT_FN (BUILT_IN_POW): /* True if the 1st argument is nonnegative or the second @@ -13121,23 +13123,21 @@ tree_call_nonnegative_warnv_p (tree type return true; } } - return tree_expr_nonnegative_warnv_p (arg0, - strict_overflow_p); + return RECURSE (arg0); default: break; } - return tree_simple_nonnegative_warnv_p (CALL_EXPR, - type); + return tree_simple_nonnegative_warnv_p (CALL_EXPR, type); } /* Return true if T is known to be non-negative. If the return value is based on the assumption that signed overflow is undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change - *STRICT_OVERFLOW_P. */ + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ static bool -tree_invalid_nonnegative_warnv_p (tree t, bool *strict_overflow_p) +tree_invalid_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth) { enum tree_code code = TREE_CODE (t); if (TYPE_UNSIGNED (TREE_TYPE (t))) @@ -13153,7 +13153,7 @@ tree_invalid_nonnegative_warnv_p (tree t /* If the initializer is non-void, then it's a normal expression that will be assigned to the slot. */ if (!VOID_TYPE_P (t)) - return tree_expr_nonnegative_warnv_p (t, strict_overflow_p); + return RECURSE (t); /* Otherwise, the initializer sets the slot in some way. One common way is an assignment statement at the end of the initializer. */ @@ -13171,8 +13171,7 @@ tree_invalid_nonnegative_warnv_p (tree t } if (TREE_CODE (t) == MODIFY_EXPR && TREE_OPERAND (t, 0) == temp) - return tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 1), - strict_overflow_p); + return RECURSE (TREE_OPERAND (t, 1)); return false; } @@ -13186,35 +13185,33 @@ tree_invalid_nonnegative_warnv_p (tree t get_callee_fndecl (t), arg0, arg1, - strict_overflow_p); + strict_overflow_p, depth); } case COMPOUND_EXPR: case MODIFY_EXPR: - return tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 1), - strict_overflow_p); + return RECURSE (TREE_OPERAND (t, 1)); + case BIND_EXPR: - return tree_expr_nonnegative_warnv_p (expr_last (TREE_OPERAND (t, 1)), - strict_overflow_p); + return RECURSE (expr_last (TREE_OPERAND (t, 1))); + case SAVE_EXPR: - return tree_expr_nonnegative_warnv_p (TREE_OPERAND (t, 0), - strict_overflow_p); + return RECURSE (TREE_OPERAND (t, 0)); default: - return tree_simple_nonnegative_warnv_p (TREE_CODE (t), - TREE_TYPE (t)); + return tree_simple_nonnegative_warnv_p (TREE_CODE (t), TREE_TYPE (t)); } - - /* We don't know sign of `t', so be conservative and return false. */ - return false; } +#undef RECURSE +#undef tree_expr_nonnegative_warnv_p + /* Return true if T is known to be non-negative. If the return value is based on the assumption that signed overflow is undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change - *STRICT_OVERFLOW_P. */ + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ bool -tree_expr_nonnegative_warnv_p (tree t, bool *strict_overflow_p) +tree_expr_nonnegative_warnv_p (tree t, bool *strict_overflow_p, int depth) { enum tree_code code; if (t == error_mark_node) @@ -13229,18 +13226,18 @@ tree_expr_nonnegative_warnv_p (tree t, b TREE_TYPE (t), TREE_OPERAND (t, 0), TREE_OPERAND (t, 1), - strict_overflow_p); + strict_overflow_p, depth); case tcc_unary: return tree_unary_nonnegative_warnv_p (TREE_CODE (t), TREE_TYPE (t), TREE_OPERAND (t, 0), - strict_overflow_p); + strict_overflow_p, depth); case tcc_constant: case tcc_declaration: case tcc_reference: - return tree_single_nonnegative_warnv_p (t, strict_overflow_p); + return tree_single_nonnegative_warnv_p (t, strict_overflow_p, depth); default: break; @@ -13255,12 +13252,12 @@ tree_expr_nonnegative_warnv_p (tree t, b TREE_TYPE (t), TREE_OPERAND (t, 0), TREE_OPERAND (t, 1), - strict_overflow_p); + strict_overflow_p, depth); case TRUTH_NOT_EXPR: return tree_unary_nonnegative_warnv_p (TREE_CODE (t), TREE_TYPE (t), TREE_OPERAND (t, 0), - strict_overflow_p); + strict_overflow_p, depth); case COND_EXPR: case CONSTRUCTOR: @@ -13269,10 +13266,10 @@ tree_expr_nonnegative_warnv_p (tree t, b case ADDR_EXPR: case WITH_SIZE_EXPR: case SSA_NAME: - return tree_single_nonnegative_warnv_p (t, strict_overflow_p); + return tree_single_nonnegative_warnv_p (t, strict_overflow_p, depth); default: - return tree_invalid_nonnegative_warnv_p (t, strict_overflow_p); + return tree_invalid_nonnegative_warnv_p (t, strict_overflow_p, depth); } } Index: gcc/gimple-fold.h =================================================================== --- gcc/gimple-fold.h 2015-09-25 12:49:13.928814656 +0100 +++ gcc/gimple-fold.h 2015-10-08 10:59:12.904576852 +0100 @@ -48,7 +48,6 @@ extern tree gimple_get_virt_method_for_b extern tree gimple_get_virt_method_for_vtable (HOST_WIDE_INT, tree, unsigned HOST_WIDE_INT, bool *can_refer = NULL); -extern bool gimple_val_nonnegative_real_p (tree); extern tree gimple_fold_indirect_ref (tree); extern bool arith_code_with_undefined_signed_overflow (tree_code); extern gimple_seq rewrite_to_defined_overflow (gimple *); @@ -113,6 +112,8 @@ gimple_convert (gimple_seq *seq, tree ty return gimple_convert (seq, UNKNOWN_LOCATION, type, op); } +extern bool gimple_stmt_nonnegative_warnv_p (gimple *, bool *, int = 0); + /* In gimple-match.c. */ extern tree gimple_simplify (enum tree_code, tree, tree, gimple_seq *, tree (*)(tree)); Index: gcc/tree-vrp.c =================================================================== --- gcc/tree-vrp.c 2015-10-05 20:45:48.964959975 +0100 +++ gcc/tree-vrp.c 2015-10-08 10:59:12.908576806 +0100 @@ -1007,80 +1007,6 @@ usable_range_p (value_range *vr, bool *s return true; } - -/* Return true if the result of assignment STMT is know to be non-negative. - If the return value is based on the assumption that signed overflow is - undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change - *STRICT_OVERFLOW_P.*/ - -static bool -gimple_assign_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p) -{ - enum tree_code code = gimple_assign_rhs_code (stmt); - switch (get_gimple_rhs_class (code)) - { - case GIMPLE_UNARY_RHS: - return tree_unary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt), - gimple_expr_type (stmt), - gimple_assign_rhs1 (stmt), - strict_overflow_p); - case GIMPLE_BINARY_RHS: - return tree_binary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt), - gimple_expr_type (stmt), - gimple_assign_rhs1 (stmt), - gimple_assign_rhs2 (stmt), - strict_overflow_p); - case GIMPLE_TERNARY_RHS: - return false; - case GIMPLE_SINGLE_RHS: - return tree_single_nonnegative_warnv_p (gimple_assign_rhs1 (stmt), - strict_overflow_p); - case GIMPLE_INVALID_RHS: - gcc_unreachable (); - default: - gcc_unreachable (); - } -} - -/* Return true if return value of call STMT is know to be non-negative. - If the return value is based on the assumption that signed overflow is - undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change - *STRICT_OVERFLOW_P.*/ - -static bool -gimple_call_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p) -{ - tree arg0 = gimple_call_num_args (stmt) > 0 ? - gimple_call_arg (stmt, 0) : NULL_TREE; - tree arg1 = gimple_call_num_args (stmt) > 1 ? - gimple_call_arg (stmt, 1) : NULL_TREE; - - return tree_call_nonnegative_warnv_p (gimple_expr_type (stmt), - gimple_call_fndecl (stmt), - arg0, - arg1, - strict_overflow_p); -} - -/* Return true if STMT is know to compute a non-negative value. - If the return value is based on the assumption that signed overflow is - undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change - *STRICT_OVERFLOW_P.*/ - -static bool -gimple_stmt_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p) -{ - switch (gimple_code (stmt)) - { - case GIMPLE_ASSIGN: - return gimple_assign_nonnegative_warnv_p (stmt, strict_overflow_p); - case GIMPLE_CALL: - return gimple_call_nonnegative_warnv_p (stmt, strict_overflow_p); - default: - gcc_unreachable (); - } -} - /* Return true if the result of assignment STMT is know to be non-zero. If the return value is based on the assumption that signed overflow is undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change @@ -6858,12 +6784,9 @@ remove_range_assertions (void) tree lhs = gimple_assign_lhs (stmt); tree rhs = gimple_assign_rhs1 (stmt); tree var; - tree cond = fold (ASSERT_EXPR_COND (rhs)); use_operand_p use_p; imm_use_iterator iter; - gcc_assert (cond != boolean_false_node); - var = ASSERT_EXPR_VAR (rhs); gcc_assert (TREE_CODE (var) == SSA_NAME); Index: gcc/gimple-fold.c =================================================================== --- gcc/gimple-fold.c 2015-10-07 09:07:21.198341367 +0100 +++ gcc/gimple-fold.c 2015-10-08 10:59:12.904576852 +0100 @@ -5773,137 +5773,6 @@ gimple_get_virt_method_for_binfo (HOST_W return gimple_get_virt_method_for_vtable (token, v, offset, can_refer); } -/* Return true iff VAL is a gimple expression that is known to be - non-negative. Restricted to floating-point inputs. */ - -bool -gimple_val_nonnegative_real_p (tree val) -{ - gimple *def_stmt; - - gcc_assert (val && SCALAR_FLOAT_TYPE_P (TREE_TYPE (val))); - - /* Use existing logic for non-gimple trees. */ - if (tree_expr_nonnegative_p (val)) - return true; - - if (TREE_CODE (val) != SSA_NAME) - return false; - - /* Currently we look only at the immediately defining statement - to make this determination, since recursion on defining - statements of operands can lead to quadratic behavior in the - worst case. This is expected to catch almost all occurrences - in practice. It would be possible to implement limited-depth - recursion if important cases are lost. Alternatively, passes - that need this information (such as the pow/powi lowering code - in the cse_sincos pass) could be revised to provide it through - dataflow propagation. */ - - def_stmt = SSA_NAME_DEF_STMT (val); - - if (is_gimple_assign (def_stmt)) - { - tree op0, op1; - - /* See fold-const.c:tree_expr_nonnegative_p for additional - cases that could be handled with recursion. */ - - switch (gimple_assign_rhs_code (def_stmt)) - { - case ABS_EXPR: - /* Always true for floating-point operands. */ - return true; - - case MULT_EXPR: - /* True if the two operands are identical (since we are - restricted to floating-point inputs). */ - op0 = gimple_assign_rhs1 (def_stmt); - op1 = gimple_assign_rhs2 (def_stmt); - - if (op0 == op1 - || operand_equal_p (op0, op1, 0)) - return true; - - default: - return false; - } - } - else if (is_gimple_call (def_stmt)) - { - tree fndecl = gimple_call_fndecl (def_stmt); - if (fndecl - && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL) - { - tree arg1; - - switch (DECL_FUNCTION_CODE (fndecl)) - { - CASE_FLT_FN (BUILT_IN_ACOS): - CASE_FLT_FN (BUILT_IN_ACOSH): - CASE_FLT_FN (BUILT_IN_CABS): - CASE_FLT_FN (BUILT_IN_COSH): - CASE_FLT_FN (BUILT_IN_ERFC): - CASE_FLT_FN (BUILT_IN_EXP): - CASE_FLT_FN (BUILT_IN_EXP10): - CASE_FLT_FN (BUILT_IN_EXP2): - CASE_FLT_FN (BUILT_IN_FABS): - CASE_FLT_FN (BUILT_IN_FDIM): - CASE_FLT_FN (BUILT_IN_HYPOT): - CASE_FLT_FN (BUILT_IN_POW10): - return true; - - CASE_FLT_FN (BUILT_IN_SQRT): - /* sqrt(-0.0) is -0.0, and sqrt is not defined over other - nonnegative inputs. */ - if (!HONOR_SIGNED_ZEROS (val)) - return true; - - break; - - CASE_FLT_FN (BUILT_IN_POWI): - /* True if the second argument is an even integer. */ - arg1 = gimple_call_arg (def_stmt, 1); - - if (TREE_CODE (arg1) == INTEGER_CST - && (TREE_INT_CST_LOW (arg1) & 1) == 0) - return true; - - break; - - CASE_FLT_FN (BUILT_IN_POW): - /* True if the second argument is an even integer-valued - real. */ - arg1 = gimple_call_arg (def_stmt, 1); - - if (TREE_CODE (arg1) == REAL_CST) - { - REAL_VALUE_TYPE c; - HOST_WIDE_INT n; - - c = TREE_REAL_CST (arg1); - n = real_to_integer (&c); - - if ((n & 1) == 0) - { - REAL_VALUE_TYPE cint; - real_from_integer (&cint, VOIDmode, n, SIGNED); - if (real_identical (&c, &cint)) - return true; - } - } - - break; - - default: - return false; - } - } - } - - return false; -} - /* Given a pointer value OP0, return a simplified version of an indirection through OP0, or NULL_TREE if no simplification is possible. Note that the resulting type may be different from @@ -6280,3 +6149,80 @@ gimple_convert (gimple_seq *seq, locatio return op; return gimple_build (seq, loc, NOP_EXPR, type, op); } + +/* Return true if the result of assignment STMT is known to be non-negative. + If the return value is based on the assumption that signed overflow is + undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ + +static bool +gimple_assign_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p, + int depth) +{ + enum tree_code code = gimple_assign_rhs_code (stmt); + switch (get_gimple_rhs_class (code)) + { + case GIMPLE_UNARY_RHS: + return tree_unary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt), + gimple_expr_type (stmt), + gimple_assign_rhs1 (stmt), + strict_overflow_p, depth); + case GIMPLE_BINARY_RHS: + return tree_binary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt), + gimple_expr_type (stmt), + gimple_assign_rhs1 (stmt), + gimple_assign_rhs2 (stmt), + strict_overflow_p, depth); + case GIMPLE_TERNARY_RHS: + return false; + case GIMPLE_SINGLE_RHS: + return tree_single_nonnegative_warnv_p (gimple_assign_rhs1 (stmt), + strict_overflow_p, depth); + case GIMPLE_INVALID_RHS: + break; + } + gcc_unreachable (); +} + +/* Return true if return value of call STMT is known to be non-negative. + If the return value is based on the assumption that signed overflow is + undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ + +static bool +gimple_call_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p, + int depth) +{ + tree arg0 = gimple_call_num_args (stmt) > 0 ? + gimple_call_arg (stmt, 0) : NULL_TREE; + tree arg1 = gimple_call_num_args (stmt) > 1 ? + gimple_call_arg (stmt, 1) : NULL_TREE; + + return tree_call_nonnegative_warnv_p (gimple_expr_type (stmt), + gimple_call_fndecl (stmt), + arg0, + arg1, + strict_overflow_p, depth); +} + +/* Return true if STMT is known to compute a non-negative value. + If the return value is based on the assumption that signed overflow is + undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change + *STRICT_OVERFLOW_P. DEPTH is the current nesting depth of the query. */ + +bool +gimple_stmt_nonnegative_warnv_p (gimple *stmt, bool *strict_overflow_p, + int depth) +{ + switch (gimple_code (stmt)) + { + case GIMPLE_ASSIGN: + return gimple_assign_nonnegative_warnv_p (stmt, strict_overflow_p, + depth); + case GIMPLE_CALL: + return gimple_call_nonnegative_warnv_p (stmt, strict_overflow_p, + depth); + default: + return false; + } +} Index: gcc/tree-ssa-math-opts.c =================================================================== --- gcc/tree-ssa-math-opts.c 2015-10-05 12:34:55.923949581 +0100 +++ gcc/tree-ssa-math-opts.c 2015-10-08 10:59:12.908576806 +0100 @@ -1526,7 +1526,7 @@ gimple_expand_builtin_pow (gimple_stmt_i if (flag_unsafe_math_optimizations && cbrtfn - && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode)) + && (!HONOR_NANS (mode) || tree_expr_nonnegative_p (arg0)) && real_equal (&c, &dconst1_3)) return build_and_insert_call (gsi, loc, cbrtfn, arg0); @@ -1538,7 +1538,7 @@ gimple_expand_builtin_pow (gimple_stmt_i if (flag_unsafe_math_optimizations && sqrtfn && cbrtfn - && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode)) + && (!HONOR_NANS (mode) || tree_expr_nonnegative_p (arg0)) && speed_p && hw_sqrt_exists && real_equal (&c, &dconst1_6)) @@ -1594,7 +1594,7 @@ gimple_expand_builtin_pow (gimple_stmt_i if (flag_unsafe_math_optimizations && cbrtfn - && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode)) + && (!HONOR_NANS (mode) || tree_expr_nonnegative_p (arg0)) && real_identical (&c2, &c) && !c2_is_int && optimize_function_for_speed_p (cfun)