Jeff has mentioned that it'll take a while longer to review the
threader rewrite, so I've decided to make some minor cleanups while he
gets to it.
There are few minor changes here:
1. I've renamed the solver to gimple-range-path.* which expresses
better that it's part of the ranger tools. The prefix tree-ssa-* is
somewhat outdated ;-).
2. I've made the folder a full blown range_query, which can be passed
around anywhere a range_query is accepted. It turns out, we were 99%
of the way there, so might as well share the same API. Now users will
be able use range_of_expr, range_of_stmt, and friends. This can come
in handy when passing a range_query to something like
simplify_using_ranges, something which I am considering for my
follow-up changes to the DOM threader.
3. Finally, I've renamed the class to path_range_query to make it
obvious that it's a range_query object.
There are no functional changes.
Tested on x86-64 Linux.
I will wait on Jeff's review of the tree-ssa-threadbackward.* changes
before committing this.
Aldy
On Fri, Jul 2, 2021 at 3:17 PM Andrew MacLeod <amacl...@redhat.com> wrote:
>
> On 7/2/21 4:13 AM, Aldy Hernandez wrote:
>
> +
> +// Return the range of STMT as it would be seen at the end of the path
> +// being analyzed. Anything but the final conditional in a BB will
> +// return VARYING.
> +
> +void
> +path_solver::range_in_path (irange &r, gimple *stmt)
> +{
> + if (gimple_code (stmt) == GIMPLE_COND && fold_range (r, stmt, this))
> + return;
> +
> + r.set_varying (gimple_expr_type (stmt));
> +}
>
> Not objecting to anything here other than to note that I think we have cases
> where there's a COND_EXPR on the RHS of statements within a block. We're (in
> general) not handling those well in DOM or jump threading.
>
>
> I guess I can put that on my TODO list :).
>
> note that we are no longer in the days of range-ops only processing...
> fold_range handles COND_EXPR (and every other kind of stmt) just fine.
>
> Andrew
From bb2d12abf7bab6306a38e143aed0f0a828f1c790 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <al...@redhat.com>
Date: Tue, 15 Jun 2021 12:20:43 +0200
Subject: [PATCH 2/5] Implement basic block path solver.
This is is the main basic block path solver for use in the ranger-based
backwards threader. Given a path of BBs, the class can solve the final
conditional or any SSA name used in calculating the final conditional.
gcc/ChangeLog:
* Makefile.in (OBJS): Add gimple-range-path.o.
* gimple-range-path.cc: New file.
* gimple-range-path.h: New file.
---
gcc/Makefile.in | 1 +
gcc/gimple-range-path.cc | 327 +++++++++++++++++++++++++++++++++++++++
gcc/gimple-range-path.h | 85 ++++++++++
3 files changed, 413 insertions(+)
create mode 100644 gcc/gimple-range-path.cc
create mode 100644 gcc/gimple-range-path.h
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 934b2a05327..863f1256811 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1649,6 +1649,7 @@ OBJS = \
tree-ssa-loop.o \
tree-ssa-math-opts.o \
tree-ssa-operands.o \
+ gimple-range-path.o \
tree-ssa-phiopt.o \
tree-ssa-phiprop.o \
tree-ssa-pre.o \
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
new file mode 100644
index 00000000000..dd7c5342d8b
--- /dev/null
+++ b/gcc/gimple-range-path.cc
@@ -0,0 +1,327 @@
+/* Basic block path solver.
+ Copyright (C) 2021 Free Software Foundation, Inc.
+ Contributed by Aldy Hernandez <al...@redhat.com>.
+
+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 "cfganal.h"
+#include "value-range.h"
+#include "gimple-range.h"
+#include "tree-pretty-print.h"
+#include "gimple-range-path.h"
+#include "ssa.h"
+
+// Internal construct to help facilitate debugging of solver.
+#define DEBUG_SOLVER (0 && dump_file)
+
+path_range_query::path_range_query (gimple_ranger &ranger)
+ : m_ranger (ranger)
+{
+ m_cache = new ssa_global_cache;
+ m_has_cache_entry = BITMAP_ALLOC (NULL);
+ m_path = NULL;
+}
+
+path_range_query::~path_range_query ()
+{
+ BITMAP_FREE (m_has_cache_entry);
+ delete m_cache;
+}
+
+// Mark cache entry for NAME as unused.
+
+void
+path_range_query::clear_cache (tree name)
+{
+ unsigned v = SSA_NAME_VERSION (name);
+ bitmap_clear_bit (m_has_cache_entry, v);
+}
+
+// If NAME has a cache entry, return it in R, and return TRUE.
+
+inline bool
+path_range_query::get_cache (irange &r, tree name)
+{
+ if (!gimple_range_ssa_p (name))
+ return get_global_range_query ()->range_of_expr (r, name);
+
+ unsigned v = SSA_NAME_VERSION (name);
+ if (bitmap_bit_p (m_has_cache_entry, v))
+ return m_cache->get_global_range (r, name);
+
+ return false;
+}
+
+// Set the cache entry for NAME to R.
+
+void
+path_range_query::set_cache (const irange &r, tree name)
+{
+ unsigned v = SSA_NAME_VERSION (name);
+ bitmap_set_bit (m_has_cache_entry, v);
+ m_cache->set_global_range (name, r);
+}
+
+void
+path_range_query::dump (FILE *dump_file)
+{
+ if (m_path->is_empty ())
+ return;
+
+ unsigned i;
+ bitmap_iterator bi;
+ extern void dump_ranger (FILE *, const vec<basic_block> &);
+
+ fprintf (dump_file, "Path is:\n");
+ dump_ranger (dump_file, *m_path);
+
+ fprintf (dump_file, "Imports:\n");
+ EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+ {
+ tree name = ssa_name (i);
+ print_generic_expr (dump_file, name, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+
+ m_cache->dump (dump_file);
+}
+
+void
+path_range_query::debug ()
+{
+ dump (stderr);
+}
+
+// Return the range of NAME at the end of the path being analyzed.
+
+bool
+path_range_query::range_of_expr (irange &r, tree name, gimple *stmt)
+{
+ if (!irange::supports_type_p (TREE_TYPE (name)))
+ return false;
+
+ if (get_cache (r, name))
+ return true;
+
+
+ basic_block bb = stmt ? gimple_bb (stmt) : exit_bb ();
+ if (stmt && range_defined_in_block (r, name, bb))
+ {
+ set_cache (r, name);
+ return true;
+ }
+
+ r.set_varying (TREE_TYPE (name));
+ return true;
+}
+
+// Return the range of STMT at the end of the path being analyzed.
+// Anything but the final conditional in a BB will return VARYING.
+
+bool
+path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
+{
+ tree type = gimple_expr_type (stmt);
+
+ if (!irange::supports_type_p (type))
+ return false;
+
+ if (gimple_code (stmt) == GIMPLE_COND && fold_range (r, stmt, this))
+ return true;
+
+ r.set_varying (type);
+ return true;
+}
+
+// Initialize the current path to PATH. The current block is set to
+// the entry block to the path.
+//
+// Note that the blocks are in reverse order, so the exit block is
+// path[0].
+
+void
+path_range_query::set_path (const vec<basic_block> &path)
+{
+ gcc_checking_assert (path.length () > 1);
+ m_path = &path;
+ m_pos = m_path->length () - 1;
+ bitmap_clear (m_has_cache_entry);
+}
+
+// Return the range of the result of PHI in R.
+
+void
+path_range_query::ssa_range_in_phi (irange &r, gphi *phi)
+{
+ tree name = gimple_phi_result (phi);
+ basic_block bb = gimple_bb (phi);
+
+ // We experimented with querying ranger's range_on_entry here, but
+ // the performance penalty was too high, for hardly any improvements.
+ if (at_entry ())
+ {
+ // Try fold just in case we can resolve simple things like PHI <5(99), 6(88)>.
+ if (!fold_range (r, phi, this))
+ r.set_varying (TREE_TYPE (name));
+
+ return;
+ }
+
+ basic_block prev = prev_bb ();
+ edge e_in = find_edge (prev, bb);
+ for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
+ if (e_in == gimple_phi_arg_edge (phi, i))
+ {
+ tree arg = gimple_phi_arg_def (phi, i);
+
+ if (!get_cache (r, arg))
+ r.set_varying (TREE_TYPE (name));
+
+ return;
+ }
+ gcc_unreachable ();
+}
+
+// If NAME is defined in BB, set R to the range of NAME, and return
+// TRUE. Otherwise, return FALSE.
+
+bool
+path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb)
+{
+ gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+ basic_block def_bb = gimple_bb (def_stmt);
+
+ if (def_bb != bb)
+ return false;
+
+ if (gimple_code (def_stmt) == GIMPLE_PHI)
+ ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
+ else if (!fold_range (r, def_stmt, this))
+ r.set_varying (TREE_TYPE (name));
+
+ if (DEBUG_SOLVER)
+ {
+ fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb->index);
+ print_generic_expr (dump_file, name, TDF_SLIM);
+ fprintf (dump_file, " is ");
+ r.dump (dump_file);
+ fprintf (dump_file, "\n");
+ }
+ return true;
+}
+
+// Precompute ranges defined in the current block, or ranges
+// that are exported on an edge to the next block.
+
+void
+path_range_query::precompute_ranges_in_block (basic_block bb)
+{
+ bitmap_iterator bi;
+ int_range_max r, cached_range;
+ unsigned i;
+
+ // Force recalculation of any names in the cache that are defined in
+ // this block. This can happen on interdependent SSA/phis in loops.
+ EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+ {
+ tree name = ssa_name (i);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+ basic_block def_bb = gimple_bb (def_stmt);
+
+ if (def_bb == bb)
+ clear_cache (name);
+ }
+
+ // Solve imports defined in this block.
+ EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+ {
+ tree name = ssa_name (i);
+
+ if (range_defined_in_block (r, name, bb))
+ set_cache (r, name);
+ }
+
+ if (at_exit ())
+ return;
+
+ // Solve imports that are exported to the next block.
+ edge e = find_edge (bb, next_bb ());
+ EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+ {
+ tree name = ssa_name (i);
+ gori_compute &g = m_ranger.gori ();
+ bitmap exports = g.exports (bb);
+
+ if (bitmap_bit_p (exports, i))
+ {
+ if (g.outgoing_edge_range_p (r, e, name, *this))
+ {
+ if (get_cache (cached_range, name))
+ r.intersect (cached_range);
+
+ set_cache (r, name);
+ if (DEBUG_SOLVER)
+ {
+ fprintf (dump_file, "outgoing_edge_range_p for ");
+ print_generic_expr (dump_file, name, TDF_SLIM);
+ fprintf (dump_file, " on edge %d->%d ",
+ e->src->index, e->dest->index);
+ fprintf (dump_file, "is ");
+ r.dump (dump_file);
+ fprintf (dump_file, "\n");
+ }
+ }
+ }
+ }
+}
+
+// Precompute the ranges for IMPORTS along PATH.
+//
+// IMPORTS are the set of SSA names, any of which could potentially
+// change the value of the final conditional in PATH.
+
+void
+path_range_query::precompute_ranges (const vec<basic_block> &path,
+ const bitmap_head *imports)
+{
+ set_path (path);
+ m_imports = imports;
+
+ if (DEBUG_SOLVER)
+ fprintf (dump_file, "path_range_query: precompute_ranges\n");
+
+ while (1)
+ {
+ basic_block bb = curr_bb ();
+
+ precompute_ranges_in_block (bb);
+
+ if (at_exit ())
+ break;
+
+ move_next ();
+ }
+
+ if (DEBUG_SOLVER)
+ dump (dump_file);
+}
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
new file mode 100644
index 00000000000..43f0ec80286
--- /dev/null
+++ b/gcc/gimple-range-path.h
@@ -0,0 +1,85 @@
+/* Header file for jump threading path solver.
+ Copyright (C) 2021 Free Software Foundation, Inc.
+ Contributed by Aldy Hernandez <al...@redhat.com>.
+
+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/>. */
+
+#ifndef GCC_TREE_SSA_THREADSOLVER_H
+#define GCC_TREE_SSA_THREADSOLVER_H
+
+// This class is a basic block path solver. Given a set of BBs
+// indicating a path through the CFG, range_of_expr and range_of_stmt
+// will calculate the range of an SSA or STMT as if the BBs in the
+// path would have been executed in order.
+//
+// Only SSA names passed in IMPORTS are precomputed, and can be
+// queried.
+//
+// Note that the blocks are in reverse order, thus the exit block is
+// path[0].
+
+class path_range_query : public range_query
+{
+public:
+ path_range_query (class gimple_ranger &ranger);
+ virtual ~path_range_query ();
+ void precompute_ranges (const vec<basic_block> &path,
+ const bitmap_head *imports);
+ bool range_of_expr (irange &r, tree name, gimple * = NULL) override;
+ bool range_of_stmt (irange &r, gimple *, tree name = NULL) override;
+ void dump (FILE *);
+ void debug ();
+
+private:
+ // Cache manipulation.
+ void set_cache (const irange &r, tree name);
+ bool get_cache (irange &r, tree name);
+ void clear_cache (tree name);
+
+ // Methods to precompute ranges for the given path.
+ bool range_defined_in_block (irange &, tree name, basic_block bb);
+ void precompute_ranges_in_block (basic_block bb);
+ void ssa_range_in_phi (irange &r, gphi *phi);
+
+ // Path navigation.
+ void set_path (const vec<basic_block> &);
+ basic_block entry_bb () { return (*m_path)[m_path->length () - 1]; }
+ basic_block exit_bb () { return (*m_path)[0]; }
+ basic_block curr_bb () { return (*m_path)[m_pos]; }
+ basic_block prev_bb () { return (*m_path)[m_pos + 1]; }
+ basic_block next_bb () { return (*m_path)[m_pos - 1]; }
+ bool at_entry () { return m_pos == m_path->length () - 1; }
+ bool at_exit () { return m_pos == 0; }
+ void move_next () { --m_pos; }
+
+ // Range cache for SSA names.
+ ssa_global_cache *m_cache;
+
+ // Set for each SSA that has an active entry in the cache.
+ bitmap m_has_cache_entry;
+
+ // Path being analyzed.
+ const vec<basic_block> *m_path;
+
+ // Current path position.
+ unsigned m_pos;
+
+ const bitmap_head *m_imports;
+ gimple_ranger &m_ranger;
+};
+
+#endif // GCC_TREE_SSA_THREADSOLVER_H
--
2.31.1
