Mercurial > hg > CbC > CbC_gcc
diff gcc/gimple-ssa-evrp-analyze.c @ 131:84e7813d76e9
gcc-8.2
author | mir3636 |
---|---|
date | Thu, 25 Oct 2018 07:37:49 +0900 |
parents | |
children | 1830386684a0 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gcc/gimple-ssa-evrp-analyze.c Thu Oct 25 07:37:49 2018 +0900 @@ -0,0 +1,439 @@ +/* Support routines for Value Range Propagation (VRP). + Copyright (C) 2005-2018 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "tree-pass.h" +#include "ssa.h" +#include "gimple-pretty-print.h" +#include "cfganal.h" +#include "gimple-fold.h" +#include "tree-eh.h" +#include "gimple-iterator.h" +#include "tree-cfg.h" +#include "tree-ssa-loop-manip.h" +#include "tree-ssa-loop.h" +#include "cfgloop.h" +#include "tree-scalar-evolution.h" +#include "tree-ssa-propagate.h" +#include "alloc-pool.h" +#include "domwalk.h" +#include "tree-cfgcleanup.h" +#include "vr-values.h" +#include "gimple-ssa-evrp-analyze.h" + +evrp_range_analyzer::evrp_range_analyzer () : stack (10) +{ + edge e; + edge_iterator ei; + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + bb->flags &= ~BB_VISITED; + FOR_EACH_EDGE (e, ei, bb->preds) + e->flags |= EDGE_EXECUTABLE; + } + vr_values = new class vr_values; +} + +/* Push an unwinding marker onto the unwinding stack. */ + +void +evrp_range_analyzer::push_marker () +{ + stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL)); +} + +/* Analyze ranges as we enter basic block BB. */ + +void +evrp_range_analyzer::enter (basic_block bb) +{ + if (!optimize) + return; + push_marker (); + record_ranges_from_incoming_edge (bb); + record_ranges_from_phis (bb); + bb->flags |= BB_VISITED; +} + +/* Find new range for NAME such that (OP CODE LIMIT) is true. */ +value_range * +evrp_range_analyzer::try_find_new_range (tree name, + tree op, tree_code code, tree limit) +{ + value_range vr; + value_range *old_vr = get_value_range (name); + + /* Discover VR when condition is true. */ + vr_values->extract_range_for_var_from_comparison_expr (name, code, op, + limit, &vr); + /* If we found any usable VR, set the VR to ssa_name and create a + PUSH old value in the stack with the old VR. */ + if (!vr.undefined_p () && !vr.varying_p ()) + { + if (old_vr->kind () == vr.kind () + && vrp_operand_equal_p (old_vr->min (), vr.min ()) + && vrp_operand_equal_p (old_vr->max (), vr.max ())) + return NULL; + value_range *new_vr = vr_values->allocate_value_range (); + *new_vr = vr; + return new_vr; + } + return NULL; +} + +/* For LHS record VR in the SSA info. */ +void +evrp_range_analyzer::set_ssa_range_info (tree lhs, value_range *vr) +{ + /* Set the SSA with the value range. */ + if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))) + { + if (vr->constant_p ()) + set_range_info (lhs, vr->kind (), + wi::to_wide (vr->min ()), + wi::to_wide (vr->max ())); + } + else if (POINTER_TYPE_P (TREE_TYPE (lhs)) + && range_includes_zero_p (vr) == 0) + set_ptr_nonnull (lhs); +} + +/* Return true if all uses of NAME are dominated by STMT or feed STMT + via a chain of single immediate uses. */ + +static bool +all_uses_feed_or_dominated_by_stmt (tree name, gimple *stmt) +{ + use_operand_p use_p, use2_p; + imm_use_iterator iter; + basic_block stmt_bb = gimple_bb (stmt); + + FOR_EACH_IMM_USE_FAST (use_p, iter, name) + { + gimple *use_stmt = USE_STMT (use_p), *use_stmt2; + if (use_stmt == stmt + || is_gimple_debug (use_stmt) + || (gimple_bb (use_stmt) != stmt_bb + && dominated_by_p (CDI_DOMINATORS, + gimple_bb (use_stmt), stmt_bb))) + continue; + while (use_stmt != stmt + && is_gimple_assign (use_stmt) + && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME + && single_imm_use (gimple_assign_lhs (use_stmt), + &use2_p, &use_stmt2)) + use_stmt = use_stmt2; + if (use_stmt != stmt) + return false; + } + return true; +} + +void +evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb) +{ + edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false); + if (pred_e) + { + gimple *stmt = last_stmt (pred_e->src); + tree op0 = NULL_TREE; + + if (stmt + && gimple_code (stmt) == GIMPLE_COND + && (op0 = gimple_cond_lhs (stmt)) + && TREE_CODE (op0) == SSA_NAME + && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))) + || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Visiting controlling predicate "); + print_gimple_stmt (dump_file, stmt, 0); + } + /* Entering a new scope. Try to see if we can find a VR + here. */ + tree op1 = gimple_cond_rhs (stmt); + if (TREE_OVERFLOW_P (op1)) + op1 = drop_tree_overflow (op1); + tree_code code = gimple_cond_code (stmt); + + auto_vec<assert_info, 8> asserts; + register_edge_assert_for (op0, pred_e, code, op0, op1, asserts); + if (TREE_CODE (op1) == SSA_NAME) + register_edge_assert_for (op1, pred_e, code, op0, op1, asserts); + + auto_vec<std::pair<tree, value_range *>, 8> vrs; + for (unsigned i = 0; i < asserts.length (); ++i) + { + value_range *vr = try_find_new_range (asserts[i].name, + asserts[i].expr, + asserts[i].comp_code, + asserts[i].val); + if (vr) + vrs.safe_push (std::make_pair (asserts[i].name, vr)); + } + + /* If pred_e is really a fallthru we can record value ranges + in SSA names as well. */ + bool is_fallthru = assert_unreachable_fallthru_edge_p (pred_e); + + /* Push updated ranges only after finding all of them to avoid + ordering issues that can lead to worse ranges. */ + for (unsigned i = 0; i < vrs.length (); ++i) + { + /* But make sure we do not weaken ranges like when + getting first [64, +INF] and then ~[0, 0] from + conditions like (s & 0x3cc0) == 0). */ + value_range *old_vr = get_value_range (vrs[i].first); + value_range tem (old_vr->kind (), old_vr->min (), old_vr->max ()); + tem.intersect (vrs[i].second); + if (tem.ignore_equivs_equal_p (*old_vr)) + continue; + push_value_range (vrs[i].first, vrs[i].second); + if (is_fallthru + && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt)) + { + set_ssa_range_info (vrs[i].first, vrs[i].second); + maybe_set_nonzero_bits (pred_e, vrs[i].first); + } + } + } + } +} + +void +evrp_range_analyzer::record_ranges_from_phis (basic_block bb) +{ + /* Visit PHI stmts and discover any new VRs possible. */ + bool has_unvisited_preds = false; + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, bb->preds) + if (e->flags & EDGE_EXECUTABLE + && !(e->src->flags & BB_VISITED)) + { + has_unvisited_preds = true; + break; + } + + for (gphi_iterator gpi = gsi_start_phis (bb); + !gsi_end_p (gpi); gsi_next (&gpi)) + { + gphi *phi = gpi.phi (); + tree lhs = PHI_RESULT (phi); + if (virtual_operand_p (lhs)) + continue; + + value_range vr_result; + bool interesting = stmt_interesting_for_vrp (phi); + if (!has_unvisited_preds && interesting) + vr_values->extract_range_from_phi_node (phi, &vr_result); + else + { + set_value_range_to_varying (&vr_result); + /* When we have an unvisited executable predecessor we can't + use PHI arg ranges which may be still UNDEFINED but have + to use VARYING for them. But we can still resort to + SCEV for loop header PHIs. */ + struct loop *l; + if (scev_initialized_p () + && interesting + && (l = loop_containing_stmt (phi)) + && l->header == gimple_bb (phi)) + vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs); + } + vr_values->update_value_range (lhs, &vr_result); + + /* Set the SSA with the value range. */ + set_ssa_range_info (lhs, &vr_result); + } +} + +/* Record ranges from STMT into our VR_VALUES class. If TEMPORARY is + true, then this is a temporary equivalence and should be recorded + into the unwind table. Othewise record the equivalence into the + global table. */ + +void +evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary) +{ + tree output = NULL_TREE; + + if (!optimize) + return; + + if (dyn_cast <gcond *> (stmt)) + ; + else if (stmt_interesting_for_vrp (stmt)) + { + edge taken_edge; + value_range vr; + vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr); + if (output) + { + /* Set the SSA with the value range. There are two cases to + consider. First (the the most common) is we are processing + STMT in a context where its resulting range globally holds + and thus it can be reflected into the global ranges and need + not be unwound as we leave scope. + + The second case occurs if we are processing a statement in + a context where the resulting range must not be reflected + into the global tables and must be unwound as we leave + the current context. This happens in jump threading for + example. */ + if (!temporary) + { + /* Case one. We can just update the underlying range + information as well as the global information. */ + vr_values->update_value_range (output, &vr); + set_ssa_range_info (output, &vr); + } + else + { + /* We're going to need to unwind this range. We can + not use VR as that's a stack object. We have to allocate + a new range and push the old range onto the stack. We + also have to be very careful about sharing the underlying + bitmaps. Ugh. */ + value_range *new_vr = vr_values->allocate_value_range (); + *new_vr = vr; + new_vr->equiv_clear (); + push_value_range (output, new_vr); + } + } + else + vr_values->set_defs_to_varying (stmt); + } + else + vr_values->set_defs_to_varying (stmt); + + /* See if we can derive a range for any of STMT's operands. */ + tree op; + ssa_op_iter i; + FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) + { + tree value; + enum tree_code comp_code; + + /* If OP is used in such a way that we can infer a value + range for it, and we don't find a previous assertion for + it, create a new assertion location node for OP. */ + if (infer_value_range (stmt, op, &comp_code, &value)) + { + /* If we are able to infer a nonzero value range for OP, + then walk backwards through the use-def chain to see if OP + was set via a typecast. + If so, then we can also infer a nonzero value range + for the operand of the NOP_EXPR. */ + if (comp_code == NE_EXPR && integer_zerop (value)) + { + tree t = op; + gimple *def_stmt = SSA_NAME_DEF_STMT (t); + while (is_gimple_assign (def_stmt) + && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)) + && TREE_CODE + (gimple_assign_rhs1 (def_stmt)) == SSA_NAME + && POINTER_TYPE_P + (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))) + { + t = gimple_assign_rhs1 (def_stmt); + def_stmt = SSA_NAME_DEF_STMT (t); + + /* Add VR when (T COMP_CODE value) condition is + true. */ + value_range *op_range + = try_find_new_range (t, t, comp_code, value); + if (op_range) + push_value_range (t, op_range); + } + } + /* Add VR when (OP COMP_CODE value) condition is true. */ + value_range *op_range = try_find_new_range (op, op, + comp_code, value); + if (op_range) + push_value_range (op, op_range); + } + } +} + +/* Unwind recorded ranges to their most recent state. */ + +void +evrp_range_analyzer::pop_to_marker (void) +{ + gcc_checking_assert (!stack.is_empty ()); + while (stack.last ().first != NULL_TREE) + pop_value_range (stack.last ().first); + stack.pop (); +} + +/* Restore/pop VRs valid only for BB when we leave BB. */ + +void +evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED) +{ + if (!optimize) + return; + pop_to_marker (); +} + + +/* Push the Value Range of VAR to the stack and update it with new VR. */ + +void +evrp_range_analyzer::push_value_range (tree var, value_range *vr) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "pushing new range for "); + print_generic_expr (dump_file, var); + fprintf (dump_file, ": "); + dump_value_range (dump_file, vr); + fprintf (dump_file, "\n"); + } + stack.safe_push (std::make_pair (var, get_value_range (var))); + vr_values->set_vr_value (var, vr); +} + +/* Pop the Value Range from the vrp_stack and update VAR with it. */ + +value_range * +evrp_range_analyzer::pop_value_range (tree var) +{ + value_range *vr = stack.last ().second; + gcc_checking_assert (var == stack.last ().first); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "popping range for "); + print_generic_expr (dump_file, var); + fprintf (dump_file, ", restoring "); + dump_value_range (dump_file, vr); + fprintf (dump_file, "\n"); + } + vr_values->set_vr_value (var, vr); + stack.pop (); + return vr; +}