From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id 9971F38A9433; Tue, 11 Jan 2022 14:07:26 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9971F38A9433 MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Andrew Macleod To: gcc-cvs@gcc.gnu.org Subject: [gcc r11-9452] Directly resolve range_of_stmt dependencies. (Port of PR 103231/103464) X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/releases/gcc-11 X-Git-Oldrev: 4797472b32afa4da45c814431e5d57ebd188aee1 X-Git-Newrev: 3760d9d7b5410f16236ed15d02ec1d8a7d16fddb Message-Id: <20220111140726.9971F38A9433@sourceware.org> Date: Tue, 11 Jan 2022 14:07:26 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 11 Jan 2022 14:07:26 -0000 https://gcc.gnu.org/g:3760d9d7b5410f16236ed15d02ec1d8a7d16fddb commit r11-9452-g3760d9d7b5410f16236ed15d02ec1d8a7d16fddb Author: Andrew MacLeod Date: Tue Dec 7 12:09:33 2021 -0500 Directly resolve range_of_stmt dependencies. (Port of PR 103231/103464) All ranger API entries eventually call range_of_stmt to ensure there is an initial global value to work with. This can cause very deep call chains when satisfied via the normal API. Instead, push any dependencies onto a stack and evaluate them in a depth first manner, mirroring what would have happened via the normal API calls. PR tree-optimization/103603 gcc/ * gimple-range.cc (gimple_ranger::gimple_ranger): Create stmt stack. (gimple_ranger::~gimple_ranger): New. (gimple_ranger::range_of_stmt): Process dependencies if they have no global cache entry. (gimple_ranger::prefill_name): New. (gimple_ranger::prefill_stmt_dependencies): New. * gimple-range.h (class gimple_ranger): Add prototypes. Diff: --- gcc/gimple-range.cc | 124 ++++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/gimple-range.h | 6 ++- 2 files changed, 129 insertions(+), 1 deletion(-) diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index f71ee6663fd..f861459ed96 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -358,6 +358,22 @@ gimple_range_calc_op2 (irange &r, const gimple *stmt, op1_range); } +// Construct a gimple_ranger. + +gimple_ranger::gimple_ranger () : m_cache (*this) +{ + m_stmt_list.create (0); + m_stmt_list.safe_grow (num_ssa_names); + m_stmt_list.truncate (0); +} + +// Destruct a gimple_ranger. + +gimple_ranger::~gimple_ranger () +{ + m_stmt_list.release (); +} + // Calculate a range for statement S and return it in R. If NAME is provided it // represents the SSA_NAME on the LHS of the statement. It is only required // if there is more than one lhs/output. If a range cannot @@ -1069,6 +1085,9 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) if (m_cache.get_non_stale_global_range (r, name)) return true; + // Avoid deep recursive call chains. + prefill_stmt_dependencies (name); + // Otherwise calculate a new value. int_range_max tmp; calc_stmt (tmp, s, name); @@ -1087,6 +1106,111 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) return true; } +// Check if NAME is a dependency that needs resolving, and push it on the +// stack if so. R is a scratch range. + +inline void +gimple_ranger::prefill_name (irange &r, tree name) +{ + if (!gimple_range_ssa_p (name)) + return; + gimple *stmt = SSA_NAME_DEF_STMT (name); + // Only pre-process range-ops and PHIs. + if (!gimple_range_handler (stmt) && !is_a (stmt)) + return; + + // If this op has not been processed yet, then push it on the stack + if (!m_cache.get_global_range (r, name)) + { + // Set as current. + m_cache.get_non_stale_global_range (r, name); + m_stmt_list.safe_push (name); + } +} + +// This routine will seed the global cache with most of the depnedencies of +// NAME. This prevents excessive call depth through the normal API. + +void +gimple_ranger::prefill_stmt_dependencies (tree ssa) +{ + if (SSA_NAME_IS_DEFAULT_DEF (ssa)) + return; + + int_range_max r; + gimple *stmt = SSA_NAME_DEF_STMT (ssa); + gcc_checking_assert (stmt && gimple_bb (stmt)); + + // Only pre-process range-ops and PHIs. + if (!gimple_range_handler (stmt) && !is_a (stmt)) + return; + + // Mark where on the stack we are starting. + unsigned start = m_stmt_list.length (); + m_stmt_list.safe_push (ssa); + + if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) + { + fprintf (dump_file, "Range_of_stmt dependence fill starting at"); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + + // Loop until back at the start point. + while (m_stmt_list.length () > start) + { + tree name = m_stmt_list.last (); + // NULL is a marker which indicates the next name in the stack has now + // been fully resolved, so we can fold it. + if (!name) + { + // Pop the NULL, then pop the name. + m_stmt_list.pop (); + name = m_stmt_list.pop (); + // Don't fold initial request, it will be calculated upon return. + if (m_stmt_list.length () > start) + { + // Fold and save the value for NAME. + stmt = SSA_NAME_DEF_STMT (name); + calc_stmt (r, stmt, name); + m_cache.set_global_range (name, r); + } + continue; + } + + // Add marker indicating previous NAME in list should be folded + // when we get to this NULL. + m_stmt_list.safe_push (NULL_TREE); + stmt = SSA_NAME_DEF_STMT (name); + + if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) + { + fprintf(dump_file, " ROS dep fill ("); + print_generic_expr (dump_file, name, TDF_SLIM); + fputs (") at stmt ", dump_file); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + + gphi *phi = dyn_cast (stmt); + if (phi) + { + for (unsigned x = 0; x < gimple_phi_num_args (phi); x++) + prefill_name (r, gimple_phi_arg_def (phi, x)); + } + else + { + gcc_checking_assert (gimple_range_handler (stmt)); + tree op = gimple_range_operand2 (stmt); + if (op) + prefill_name (r, op); + op = gimple_range_operand1 (stmt); + if (op) + prefill_name (r, op); + } + } + if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) + fprintf (dump_file, "END range_of_stmt dependence fill\n"); +} + // This routine will export whatever global ranges are known to GCC // SSA_RANGE_NAME_INFO fields. diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index 5751b0937a0..caa12e4c4d5 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -46,7 +46,8 @@ along with GCC; see the file COPYING3. If not see class gimple_ranger : public range_query { public: - gimple_ranger () : m_cache (*this) { } + gimple_ranger (); + ~gimple_ranger (); virtual bool range_of_stmt (irange &r, gimple *, tree name = NULL) OVERRIDE; virtual bool range_of_expr (irange &r, tree name, gimple * = NULL) OVERRIDE; virtual bool range_on_edge (irange &r, edge e, tree name) OVERRIDE; @@ -55,11 +56,14 @@ public: void export_global_ranges (); void dump (FILE *f); protected: + void prefill_name (irange &r, tree name); + void prefill_stmt_dependencies (tree ssa); bool calc_stmt (irange &r, gimple *s, tree name = NULL_TREE); bool range_of_range_op (irange &r, gimple *s); bool range_of_call (irange &r, gcall *call); bool range_of_cond_expr (irange &r, gassign* cond); ranger_cache m_cache; + vec m_stmt_list; private: bool range_of_phi (irange &r, gphi *phi); bool range_of_address (irange &r, gimple *s);