[GCC11] PR tree-optimization/103603 - Directly resolve range_of_stmt dependencies. (Port of PR 103231/103464)
Commit Message
The following patch is a slight rework of the 2 patches which flatten
rangers call stack. It needed some tweaking since some of the routines
have changed name or been adjusted.
This has been bootstrapped on x86_64-pc-linux-gnu with no regressions.
OK for gcc-11 release branch?
Andrew
Comments
Test result from RISC-V, tested on riscv64-unknown-elf and
riscv64-unknown-linux-gnu with no regressions.
Thanks :)
On Wed, Dec 8, 2021 at 4:19 AM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> The following patch is a slight rework of the 2 patches which flatten
> rangers call stack. It needed some tweaking since some of the routines
> have changed name or been adjusted.
>
> This has been bootstrapped on x86_64-pc-linux-gnu with no regressions.
> OK for gcc-11 release branch?
>
> Andrew
>
On 12/7/21 15:19, Andrew MacLeod wrote:
> The following patch is a slight rework of the 2 patches which flatten
> rangers call stack. It needed some tweaking since some of the
> routines have changed name or been adjusted.
>
> This has been bootstrapped on x86_64-pc-linux-gnu with no
> regressions. OK for gcc-11 release branch?
>
> Andrew
>
ping. I don't think anyone OK'd this.
Andrew
On Fri, Jan 7, 2022 at 6:40 PM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> On 12/7/21 15:19, Andrew MacLeod wrote:
> > The following patch is a slight rework of the 2 patches which flatten
> > rangers call stack. It needed some tweaking since some of the
> > routines have changed name or been adjusted.
> >
> > This has been bootstrapped on x86_64-pc-linux-gnu with no
> > regressions. OK for gcc-11 release branch?
> >
> > Andrew
> >
> ping. I don't think anyone OK'd this.
OK.
Thanks,
Richard.
> Andrew
>
commit 027ee39a809addd9ecd577ea894de6c8987c0914
Author: Andrew MacLeod <amacleod@redhat.com>
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.
@@ -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<gphi *> (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<gphi *> (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 <gphi *> (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.
@@ -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<tree> m_stmt_list;
private:
bool range_of_phi (irange &r, gphi *phi);
bool range_of_address (irange &r, gimple *s);