On 6/28/2021 10:21 AM, Aldy Hernandez wrote:
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.
The main API is:
// This class is a basic block path solver. Given a set of BBs
// indicating a path through the CFG, range_in_path() will return the
// range of an SSA 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_solver
{
public:
path_solver (gimple_ranger &ranger);
virtual ~path_solver ();
void precompute_ranges (const vec<basic_block> *path,
const bitmap_head *imports);
void range_in_path (irange &, tree name);
void range_in_path (irange &, gimple *);
};
gcc/ChangeLog:
* Makefile.in (OBJS): Add tree-ssa-path-solver.o.
* tree-ssa-path-solver.cc: New file.
* tree-ssa-path-solver.h: New file.
---
gcc/Makefile.in | 1 +
gcc/tree-ssa-path-solver.cc | 310 ++++++++++++++++++++++++++++++++++++
gcc/tree-ssa-path-solver.h | 85 ++++++++++
3 files changed, 396 insertions(+)
create mode 100644 gcc/tree-ssa-path-solver.cc
create mode 100644 gcc/tree-ssa-path-solver.h
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index ebf26442992..66cc5f9529e 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1644,6 +1644,7 @@ OBJS = \
tree-ssa-loop.o \
tree-ssa-math-opts.o \
tree-ssa-operands.o \
+ tree-ssa-path-solver.o \
tree-ssa-phiopt.o \
tree-ssa-phiprop.o \
tree-ssa-pre.o \
diff --git a/gcc/tree-ssa-path-solver.cc b/gcc/tree-ssa-path-solver.cc
new file mode 100644
index 00000000000..1e2c37cff78
--- /dev/null
+++ b/gcc/tree-ssa-path-solver.cc
@@ -0,0 +1,310 @@
+/* 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 "tree-ssa-path-solver.h"
+#include "ssa.h"
+
+// Internal construct to help facilitate debugging of solver.
+#define DEBUG_SOLVER getenv("DEBUG")
Shouldn't this really be a property of what pass is using the solver and
whether or not the appropriate dump flag is on for that pass?
+
+path_solver::path_solver (gimple_ranger &ranger)
+ : m_ranger (ranger)
+{
+ m_cache = new ssa_global_cache;
+ m_has_cache_entry = BITMAP_ALLOC (NULL);
+ m_path = NULL;
+}
+
+path_solver::~path_solver ()
+{
+ BITMAP_FREE (m_has_cache_entry);
+ delete m_cache;
+}
Do we need to clean up any other members in here? m_has_cache_entry,
m_path, m_imports, m_ranger?
path_solver::range_of_expr has a comment asking if the call to set_cache
is necessary. Can you resolve that one way or the other?
+// 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_solver::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);
+}
What's our position on ownership of PATH here? Can our caller delete
it? Can we modify it? Who releases it? I realize you may be
interfacing with some nonsense code I wrote eons ago ;-)
+
+// Return the range of the result of PHI in R.
+
+void
+path_solver::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 ())
+ {
+ 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)
It's probably not important in practice, but you're going to end up
calling gimple_phi_num_args every iteration of this loop. It's value
isn't generally subject to LICM.
+ 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));
+
+ // ?? Is this set_cache necessary?
Similar to the earlier instance. Can we get a resolution on whether
this is necessary or not?
+
+// If NAME is defined in BB, set R to the range of NAME, and return
+// TRUE. Otherwise, return FALSE.
+
+bool
+path_solver::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 (stderr, "range_defined_in_block (BB%d) for ", bb->index);
+ print_generic_expr (stderr, name, TDF_SLIM);
+ fprintf (stderr, " is ");
+ r.dump (stderr);
+ fprintf (stderr, "\n");
+ }
So see the earlier note. This should be doing into the appropriate pass
specific dump file rather than dumping to stderr based on the value of
an environment variable. Similarly for the other chunks of debugging bits.
+
+// 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.
This looks pretty reasonable to me. There's a few things to address
noted above, but it's close.
jeff
