On 7/2/21 12:20 AM, Jeff Law wrote:
On 6/28/2021 10:21 AM, Aldy Hernandez wrote:
+// 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?
Whoops. This was a private construct used for debugging the solver.
I've changed it to:
+#define DEBUG_SOLVER (0 && dump_file)
+
+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?
Nope, that's it.
m_has_cache_entry is being freed here.
The m_path and m_imports parameters belong to the caller, and m_ranger
has a destructor of its own.
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 ;-)
Belongs to the caller. As per Martin's suggestion, it's now a const
reference to make this clearer. I forgot to repost after that change.
+
+// 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.
I was just following standard practice:
$ grep for\ .*gimple_phi_num_args *.c|wc -l
73
But if it's something you feel strongly about, I can change it.
+ 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?
It turns out this doesn't make a difference. We can recalculate in this
case, and it does not affect neither performance nor the number of
threads throughout my test harness. I've removed both instances.
+
+// 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.
I guess I can put that on my TODO list :).
This looks pretty reasonable to me. There's a few things to address
noted above, but it's close.
Attached is an updated patch.
Tested on x86-64 Linux with bootstrap, regtests, as well as our
callgrind benchmark suite. I also verified that the number of threading
opportunities was the same.
Aldy
>From e70ab3b9849db45176f4ab6ec5b1c25b9d30b58a Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <al...@redhat.com>
Date: Tue, 15 Jun 2021 12:20:43 +0200
Subject: [PATCH 1/2] 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.
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 | 306 ++++++++++++++++++++++++++++++++++++
gcc/tree-ssa-path-solver.h | 85 ++++++++++
3 files changed, 392 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..9dca2937ecc
--- /dev/null
+++ b/gcc/tree-ssa-path-solver.cc
@@ -0,0 +1,306 @@
+/* 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 (0 && dump_file)
+
+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;
+}
+
+// Mark cache entry for NAME as unused.
+
+void
+path_solver::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_solver::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_solver::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);
+}
+
+bool
+path_solver::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;
+
+ if (stmt && range_defined_in_block (r, name, gimple_bb (stmt)))
+ {
+ set_cache (r, name);
+ return true;
+ }
+
+ // Otherwise return varying.
+ r.set_varying (TREE_TYPE (name));
+ 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_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);
+}
+
+// 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)
+ 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_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 (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. The cache is
+// updated accordingly.
+
+void
+path_solver::precompute_ranges_in_block ()
+{
+ basic_block bb = curr_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_solver::precompute_ranges (const vec<basic_block> &path,
+ const bitmap_head *imports)
+{
+ set_path (path);
+ m_imports = imports;
+
+ if (DEBUG_SOLVER)
+ {
+ extern void debug (vec<basic_block> &);
+ extern void debug (const bitmap_head *);
+ fprintf (dump_file, "\nPATH is:\n");
+ debug (const_cast <vec<basic_block> &> (path));
+ fprintf (dump_file, "imports: ");
+ debug (imports);
+ }
+
+ while (1)
+ {
+ precompute_ranges_in_block ();
+ if (at_exit ())
+ break;
+ move_next ();
+ }
+}
+
+// Return the range of NAME as it would be seen at the end of the path
+// being analyzed.
+
+void
+path_solver::range_in_path (irange &r, tree name)
+{
+ basic_block bb = exit_bb ();
+
+ if (get_cache (r, name))
+ return;
+
+ if (range_defined_in_block (r, name, bb))
+ return;
+
+ // The path may not be deep enough to resolve NAME.
+ r.set_varying (TREE_TYPE (name));
+}
+
+// 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));
+}
diff --git a/gcc/tree-ssa-path-solver.h b/gcc/tree-ssa-path-solver.h
new file mode 100644
index 00000000000..90bcf389f66
--- /dev/null
+++ b/gcc/tree-ssa-path-solver.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_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 : private range_query
+{
+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 *);
+
+private:
+ bool range_of_expr (irange &r, tree name, gimple * = NULL) override;
+
+ // 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 ();
+ 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
