- Similarly for negation. */
- if ((rhs_code == BIT_NOT_EXPR || rhs_code == NEGATE_EXPR)
- && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
- {
- /* Get the definition statement for our RHS. */
- tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
-
- /* See if the RHS_DEF_STMT has the same form as our statement. */
- if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR
- && TREE_CODE (TREE_OPERAND (rhs_def_stmt, 1)) == rhs_code)
- {
- tree rhs_def_operand;
-
- rhs_def_operand = TREE_OPERAND (TREE_OPERAND (rhs_def_stmt, 1), 0);
-
- /* Verify that RHS_DEF_OPERAND is a suitable SSA variable. */
- if (TREE_CODE (rhs_def_operand) == SSA_NAME
- && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
- result = update_rhs_and_lookup_avail_expr (stmt,
- rhs_def_operand,
- insert);
- }
- }
-
- /* If we have z = (x OP C1), see if we earlier had x = y OP C2.
- If OP is associative, create and fold (y OP C2) OP C1 which
- should result in (y OP C3), use that as the RHS for the
- assignment. Add minus to this, as we handle it specially below. */
- if ((associative_tree_code (rhs_code) || rhs_code == MINUS_EXPR)
- && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
- && is_gimple_min_invariant (TREE_OPERAND (rhs, 1)))
- {
- tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
-
- /* If the statement defines an induction variable, do not propagate
- its value, so that we do not create overlapping life ranges. */
- if (simple_iv_increment_p (rhs_def_stmt))
- goto dont_fold_assoc;
-
- /* See if the RHS_DEF_STMT has the same form as our statement. */
- if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR)
- {
- tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
- enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
-
- if ((rhs_code == rhs_def_code && unsafe_associative_fp_binop (rhs))
- || (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
- || (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
- {
- tree def_stmt_op0 = TREE_OPERAND (rhs_def_rhs, 0);
- tree def_stmt_op1 = TREE_OPERAND (rhs_def_rhs, 1);
-
- if (TREE_CODE (def_stmt_op0) == SSA_NAME
- && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_stmt_op0)
- && is_gimple_min_invariant (def_stmt_op1))
- {
- tree outer_const = TREE_OPERAND (rhs, 1);
- tree type = TREE_TYPE (TREE_OPERAND (stmt, 0));
- tree t;
-
- /* If we care about correct floating point results, then
- don't fold x + c1 - c2. Note that we need to take both
- the codes and the signs to figure this out. */
- if (FLOAT_TYPE_P (type)
- && !flag_unsafe_math_optimizations
- && (rhs_def_code == PLUS_EXPR
- || rhs_def_code == MINUS_EXPR))
- {
- bool neg = false;
-
- neg ^= (rhs_code == MINUS_EXPR);
- neg ^= (rhs_def_code == MINUS_EXPR);
- neg ^= real_isneg (TREE_REAL_CST_PTR (outer_const));
- neg ^= real_isneg (TREE_REAL_CST_PTR (def_stmt_op1));
-
- if (neg)
- goto dont_fold_assoc;
- }
-
- /* Ho hum. So fold will only operate on the outermost
- thingy that we give it, so we have to build the new
- expression in two pieces. This requires that we handle
- combinations of plus and minus. */
- if (rhs_def_code != rhs_code)
- {
- if (rhs_def_code == MINUS_EXPR)
- t = build (MINUS_EXPR, type, outer_const, def_stmt_op1);
- else
- t = build (MINUS_EXPR, type, def_stmt_op1, outer_const);
- rhs_code = PLUS_EXPR;
- }
- else if (rhs_def_code == MINUS_EXPR)
- t = build (PLUS_EXPR, type, def_stmt_op1, outer_const);
- else
- t = build (rhs_def_code, type, def_stmt_op1, outer_const);
- t = local_fold (t);
- t = build (rhs_code, type, def_stmt_op0, t);
- t = local_fold (t);
-
- /* If the result is a suitable looking gimple expression,
- then use it instead of the original for STMT. */
- if (TREE_CODE (t) == SSA_NAME
- || (UNARY_CLASS_P (t)
- && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
- || ((BINARY_CLASS_P (t) || COMPARISON_CLASS_P (t))
- && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
- && is_gimple_val (TREE_OPERAND (t, 1))))
- result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
- }
- }
- }
- dont_fold_assoc:;
- }
-
- /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
- and BIT_AND_EXPR respectively if the first operand is greater
- than zero and the second operand is an exact power of two. */
- if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
- && integer_pow2p (TREE_OPERAND (rhs, 1)))
- {
- tree val;
- tree op = TREE_OPERAND (rhs, 0);
-
- if (TYPE_UNSIGNED (TREE_TYPE (op)))
- {
- val = integer_one_node;
- }
- else
- {
- tree dummy_cond = walk_data->global_data;
-
- if (! dummy_cond)
- {
- dummy_cond = build (GT_EXPR, boolean_type_node,
- op, integer_zero_node);
- dummy_cond = build (COND_EXPR, void_type_node,
- dummy_cond, NULL, NULL);
- walk_data->global_data = dummy_cond;
- }
- else
- {
- TREE_SET_CODE (COND_EXPR_COND (dummy_cond), GT_EXPR);
- TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
- TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
- = integer_zero_node;
- }
- val = simplify_cond_and_lookup_avail_expr (dummy_cond, NULL, false);
- }
-
- if (val && integer_onep (val))
- {
- tree t;
- tree op0 = TREE_OPERAND (rhs, 0);
- tree op1 = TREE_OPERAND (rhs, 1);
-
- if (rhs_code == TRUNC_DIV_EXPR)
- t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0,
- build_int_cst (NULL_TREE, tree_log2 (op1)));
- else
- t = build (BIT_AND_EXPR, TREE_TYPE (op0), op0,
- local_fold (build (MINUS_EXPR, TREE_TYPE (op1),
- op1, integer_one_node)));
-
- result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
- }
- }
-
- /* Transform ABS (X) into X or -X as appropriate. */
- if (rhs_code == ABS_EXPR
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
- {
- tree val;
- tree op = TREE_OPERAND (rhs, 0);
- tree type = TREE_TYPE (op);
-
- if (TYPE_UNSIGNED (type))
- {
- val = integer_zero_node;
- }
- else
- {
- tree dummy_cond = walk_data->global_data;
-
- if (! dummy_cond)
- {
- dummy_cond = build (LE_EXPR, boolean_type_node,
- op, integer_zero_node);
- dummy_cond = build (COND_EXPR, void_type_node,
- dummy_cond, NULL, NULL);
- walk_data->global_data = dummy_cond;
- }
- else
- {
- TREE_SET_CODE (COND_EXPR_COND (dummy_cond), LE_EXPR);
- TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
- TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
- = build_int_cst (type, 0);
- }
- val = simplify_cond_and_lookup_avail_expr (dummy_cond, NULL, false);
-
- if (!val)
- {
- TREE_SET_CODE (COND_EXPR_COND (dummy_cond), GE_EXPR);
- TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
- TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
- = build_int_cst (type, 0);
-
- val = simplify_cond_and_lookup_avail_expr (dummy_cond,
- NULL, false);
-
- if (val)
- {
- if (integer_zerop (val))
- val = integer_one_node;
- else if (integer_onep (val))
- val = integer_zero_node;
- }
- }
- }
-
- if (val
- && (integer_onep (val) || integer_zerop (val)))
- {
- tree t;
-
- if (integer_onep (val))
- t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
- else
- t = op;
-
- result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
- }
- }
-
- /* Optimize *"foo" into 'f'. This is done here rather than
- in fold to avoid problems with stuff like &*"foo". */
- if (TREE_CODE (rhs) == INDIRECT_REF || TREE_CODE (rhs) == ARRAY_REF)
- {
- tree t = fold_read_from_constant_string (rhs);
-
- if (t)
- result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
- }
-
- return result;
-}
-
-/* COND is a condition of the form:
-
- x == const or x != const
-
- Look back to x's defining statement and see if x is defined as
-
- x = (type) y;
-
- If const is unchanged if we convert it to type, then we can build
- the equivalent expression:
-
-
- y == const or y != const
-
- Which may allow further optimizations.
-
- Return the equivalent comparison or NULL if no such equivalent comparison
- was found. */
-
-static tree
-find_equivalent_equality_comparison (tree cond)
-{
- tree op0 = TREE_OPERAND (cond, 0);
- tree op1 = TREE_OPERAND (cond, 1);
- tree def_stmt = SSA_NAME_DEF_STMT (op0);
-
- /* OP0 might have been a parameter, so first make sure it
- was defined by a MODIFY_EXPR. */
- if (def_stmt && TREE_CODE (def_stmt) == MODIFY_EXPR)
- {
- tree def_rhs = TREE_OPERAND (def_stmt, 1);
-
- /* Now make sure the RHS of the MODIFY_EXPR is a typecast. */
- if ((TREE_CODE (def_rhs) == NOP_EXPR
- || TREE_CODE (def_rhs) == CONVERT_EXPR)
- && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME)
- {
- tree def_rhs_inner = TREE_OPERAND (def_rhs, 0);
- tree def_rhs_inner_type = TREE_TYPE (def_rhs_inner);
- tree new;
-
- if (TYPE_PRECISION (def_rhs_inner_type)
- > TYPE_PRECISION (TREE_TYPE (def_rhs)))
- return NULL;
-
- /* What we want to prove is that if we convert OP1 to
- the type of the object inside the NOP_EXPR that the
- result is still equivalent to SRC.
-
- If that is true, the build and return new equivalent
- condition which uses the source of the typecast and the
- new constant (which has only changed its type). */
- new = build1 (TREE_CODE (def_rhs), def_rhs_inner_type, op1);
- new = local_fold (new);
- if (is_gimple_val (new) && tree_int_cst_equal (new, op1))
- return build (TREE_CODE (cond), TREE_TYPE (cond),
- def_rhs_inner, new);
- }
- }
- return NULL;
-}
-
-/* STMT is a COND_EXPR for which we could not trivially determine its
- result. This routine attempts to find equivalent forms of the
- condition which we may be able to optimize better. It also
- uses simple value range propagation to optimize conditionals. */
-
-static tree
-simplify_cond_and_lookup_avail_expr (tree stmt,
- stmt_ann_t ann,
- int insert)
-{
- tree cond = COND_EXPR_COND (stmt);
-
- if (COMPARISON_CLASS_P (cond))
- {
- tree op0 = TREE_OPERAND (cond, 0);
- tree op1 = TREE_OPERAND (cond, 1);
-
- if (TREE_CODE (op0) == SSA_NAME && is_gimple_min_invariant (op1))
- {
- int limit;
- tree low, high, cond_low, cond_high;
- int lowequal, highequal, swapped, no_overlap, subset, cond_inverted;
- varray_type vrp_records;
- struct vrp_element *element;
- struct vrp_hash_elt vrp_hash_elt, *vrp_hash_elt_p;
- void **slot;
-
- /* First see if we have test of an SSA_NAME against a constant
- where the SSA_NAME is defined by an earlier typecast which
- is irrelevant when performing tests against the given
- constant. */
- if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
- {
- tree new_cond = find_equivalent_equality_comparison (cond);
-
- if (new_cond)
- {
- /* Update the statement to use the new equivalent
- condition. */
- COND_EXPR_COND (stmt) = new_cond;
-
- /* If this is not a real stmt, ann will be NULL and we
- avoid processing the operands. */
- if (ann)
- modify_stmt (stmt);
-
- /* Lookup the condition and return its known value if it
- exists. */
- new_cond = lookup_avail_expr (stmt, insert);
- if (new_cond)
- return new_cond;
-
- /* The operands have changed, so update op0 and op1. */
- op0 = TREE_OPERAND (cond, 0);
- op1 = TREE_OPERAND (cond, 1);
- }
- }
-
- /* Consult the value range records for this variable (if they exist)
- to see if we can eliminate or simplify this conditional.
-
- Note two tests are necessary to determine no records exist.
- First we have to see if the virtual array exists, if it
- exists, then we have to check its active size.
-
- Also note the vast majority of conditionals are not testing
- a variable which has had its range constrained by an earlier
- conditional. So this filter avoids a lot of unnecessary work. */
- vrp_hash_elt.var = op0;
- vrp_hash_elt.records = NULL;
- slot = htab_find_slot (vrp_data, &vrp_hash_elt, NO_INSERT);
- if (slot == NULL)
- return NULL;
-
- vrp_hash_elt_p = (struct vrp_hash_elt *) *slot;
- vrp_records = vrp_hash_elt_p->records;
- if (vrp_records == NULL)
- return NULL;
-
- limit = VARRAY_ACTIVE_SIZE (vrp_records);
-
- /* If we have no value range records for this variable, or we are
- unable to extract a range for this condition, then there is
- nothing to do. */
- if (limit == 0
- || ! extract_range_from_cond (cond, &cond_high,
- &cond_low, &cond_inverted))
- return NULL;
-
- /* We really want to avoid unnecessary computations of range
- info. So all ranges are computed lazily; this avoids a
- lot of unnecessary work. i.e., we record the conditional,
- but do not process how it constrains the variable's
- potential values until we know that processing the condition
- could be helpful.
-
- However, we do not want to have to walk a potentially long
- list of ranges, nor do we want to compute a variable's
- range more than once for a given path.
-
- Luckily, each time we encounter a conditional that can not
- be otherwise optimized we will end up here and we will
- compute the necessary range information for the variable
- used in this condition.
-
- Thus you can conclude that there will never be more than one
- conditional associated with a variable which has not been
- processed. So we never need to merge more than one new
- conditional into the current range.
-
- These properties also help us avoid unnecessary work. */
- element
- = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records, limit - 1);
-
- if (element->high && element->low)
- {
- /* The last element has been processed, so there is no range
- merging to do, we can simply use the high/low values
- recorded in the last element. */
- low = element->low;
- high = element->high;
- }
- else
- {
- tree tmp_high, tmp_low;
- int dummy;
-
- /* The last element has not been processed. Process it now.
- record_range should ensure for cond inverted is not set.
- This call can only fail if cond is x < min or x > max,
- which fold should have optimized into false.
- If that doesn't happen, just pretend all values are
- in the range. */
- if (! extract_range_from_cond (element->cond, &tmp_high,
- &tmp_low, &dummy))
- gcc_unreachable ();
- else
- gcc_assert (dummy == 0);
-
- /* If this is the only element, then no merging is necessary,
- the high/low values from extract_range_from_cond are all
- we need. */
- if (limit == 1)
- {
- low = tmp_low;
- high = tmp_high;
- }
- else
- {
- /* Get the high/low value from the previous element. */
- struct vrp_element *prev
- = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records,
- limit - 2);
- low = prev->low;
- high = prev->high;
-
- /* Merge in this element's range with the range from the
- previous element.
-
- The low value for the merged range is the maximum of
- the previous low value and the low value of this record.
-
- Similarly the high value for the merged range is the
- minimum of the previous high value and the high value of
- this record. */
- low = (tree_int_cst_compare (low, tmp_low) == 1
- ? low : tmp_low);
- high = (tree_int_cst_compare (high, tmp_high) == -1
- ? high : tmp_high);
- }
-
- /* And record the computed range. */
- element->low = low;
- element->high = high;
-
- }
-
- /* After we have constrained this variable's potential values,
- we try to determine the result of the given conditional.
-
- To simplify later tests, first determine if the current
- low value is the same low value as the conditional.
- Similarly for the current high value and the high value
- for the conditional. */
- lowequal = tree_int_cst_equal (low, cond_low);
- highequal = tree_int_cst_equal (high, cond_high);
-
- if (lowequal && highequal)
- return (cond_inverted ? boolean_false_node : boolean_true_node);
-
- /* To simplify the overlap/subset tests below we may want
- to swap the two ranges so that the larger of the two
- ranges occurs "first". */
- swapped = 0;
- if (tree_int_cst_compare (low, cond_low) == 1
- || (lowequal
- && tree_int_cst_compare (cond_high, high) == 1))
- {
- tree temp;
-
- swapped = 1;
- temp = low;
- low = cond_low;
- cond_low = temp;
- temp = high;
- high = cond_high;
- cond_high = temp;
- }
-
- /* Now determine if there is no overlap in the ranges
- or if the second range is a subset of the first range. */
- no_overlap = tree_int_cst_lt (high, cond_low);
- subset = tree_int_cst_compare (cond_high, high) != 1;
-
- /* If there was no overlap in the ranges, then this conditional
- always has a false value (unless we had to invert this
- conditional, in which case it always has a true value). */
- if (no_overlap)
- return (cond_inverted ? boolean_true_node : boolean_false_node);
-
- /* If the current range is a subset of the condition's range,
- then this conditional always has a true value (unless we
- had to invert this conditional, in which case it always
- has a true value). */
- if (subset && swapped)
- return (cond_inverted ? boolean_false_node : boolean_true_node);
-
- /* We were unable to determine the result of the conditional.
- However, we may be able to simplify the conditional. First
- merge the ranges in the same manner as range merging above. */
- low = tree_int_cst_compare (low, cond_low) == 1 ? low : cond_low;
- high = tree_int_cst_compare (high, cond_high) == -1 ? high : cond_high;
-
- /* If the range has converged to a single point, then turn this
- into an equality comparison. */
- if (TREE_CODE (cond) != EQ_EXPR
- && TREE_CODE (cond) != NE_EXPR
- && tree_int_cst_equal (low, high))
- {
- TREE_SET_CODE (cond, EQ_EXPR);
- TREE_OPERAND (cond, 1) = high;
- }
- }
- }
- return 0;
-}
-
-/* STMT is a SWITCH_EXPR for which we could not trivially determine its
- result. This routine attempts to find equivalent forms of the
- condition which we may be able to optimize better. */
-
-static tree
-simplify_switch_and_lookup_avail_expr (tree stmt, int insert)
-{
- tree cond = SWITCH_COND (stmt);
- tree def, to, ti;
-
- /* The optimization that we really care about is removing unnecessary
- casts. That will let us do much better in propagating the inferred
- constant at the switch target. */
- if (TREE_CODE (cond) == SSA_NAME)
- {
- def = SSA_NAME_DEF_STMT (cond);
- if (TREE_CODE (def) == MODIFY_EXPR)
- {
- def = TREE_OPERAND (def, 1);
- if (TREE_CODE (def) == NOP_EXPR)
- {
- int need_precision;
- bool fail;
-
- def = TREE_OPERAND (def, 0);
-
-#ifdef ENABLE_CHECKING
- /* ??? Why was Jeff testing this? We are gimple... */
- gcc_assert (is_gimple_val (def));
-#endif
-
- to = TREE_TYPE (cond);
- ti = TREE_TYPE (def);
-
- /* If we have an extension that preserves value, then we
- can copy the source value into the switch. */
-
- need_precision = TYPE_PRECISION (ti);
- fail = false;
- if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
- fail = true;
- else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
- need_precision += 1;
- if (TYPE_PRECISION (to) < need_precision)
- fail = true;
-
- if (!fail)
- {
- SWITCH_COND (stmt) = def;
- modify_stmt (stmt);
-
- return lookup_avail_expr (stmt, insert);
- }
- }
- }
- }
-
- return 0;
-}
-
-
-/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
- known value for that SSA_NAME (or NULL if no value is known).
-
- NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
- even if we don't know their precise value.
-
- Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
- nodes of the successors of BB. */
-
-static void
-cprop_into_successor_phis (basic_block bb, bitmap nonzero_vars)
-{
- edge e;
- edge_iterator ei;
-
- FOR_EACH_EDGE (e, ei, bb->succs)