| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
If an SSA is defined in the current block, there is no need to query
range_on_path_entry for additional information.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::path_range_query):
Move debugging header...
(path_range_query::precompute_ranges): ...here.
(path_range_query::internal_range_of_expr): Do not call
range_on_path_entry if NAME is defined in the current block.
|
|
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::precompute_relations):
Hoist edge calculations before using EDGE_SUCC.
|
|
Cycling through equivalences to improve a range is nowhere near as
efficient as asking the ranger what the range on entry is.
Testing on a hybrid VRP threader, shows that this improves our VRP
threading benefit from 14.5% to 18.5% and our overall jump threads from
0.85% to 1.28%.
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::internal_range_of_expr):
Remove call to improve_range_with_equivs.
(path_range_query::improve_range_with_equivs): Remove
* gimple-range-path.h: Remove improve_range_with_equivs.
|
|
The default behavior for the path solver is to resort to VARYING when
the range for an unknown SSA is outside the given path. This is both
cheap and fast, but fails to get a significant amount of ranges that
traditionally the DOM and VRP threaders could get.
This patch uses the ranger to resolve any unknown names upon entry to
the path. It also uses equivalences to improve ranges.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::defined_outside_path):
New.
(path_range_query::range_on_path_entry): New.
(path_range_query::internal_range_of_expr): Resolve unknowns
with ranger.
(path_range_query::improve_range_with_equivs): New.
(path_range_query::ssa_range_in_phi): Resolve unknowns with
ranger.
* gimple-range-path.h (class path_range_query): Add
defined_outside_path, range_on_path_entry, and
improve_range_with_equivs.
|
|
The path solver takes an initial set of SSA names which are deemed
interesting. These are then solved along the path. Adding any copies
of said SSA names to the list of interesting names yields significantly
better results. This patch adds said copies to the already provided
list.
Currently this code is guarded by "m_resolve", which is the more
expensive mode, but it would be reasonable to make it available always,
especially since adding more imports usually has minimal impact on the
processing time. I will investigate and make it universally available
if this is indeed the case.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::add_to_imports): New.
(path_range_query::add_copies_to_imports): New.
(path_range_query::precompute_ranges): Call
add_copies_to_imports.
* gimple-range-path.h (class path_range_query): Add prototypes
for add_copies_to_imports and add_to_imports.
|
|
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::range_defined_in_block):
Remove useless code.
|
|
This patch adds relational support to the path solver. It uses a
path_oracle that keeps track of relations within a path which are
augmented by relations on entry to the path. With it, range_of_stmt,
range_of_expr, and friends can give relation aware answers.
gcc/ChangeLog:
* gimple-range-fold.h (class fur_source): Make oracle protected.
* gimple-range-path.cc (path_range_query::path_range_query): Add
resolve argument. Initialize oracle.
(path_range_query::~path_range_query): Delete oracle.
(path_range_query::range_of_stmt): Adapt to use relations.
(path_range_query::precompute_ranges): Pre-compute relations.
(class jt_fur_source): New
(jt_fur_source::jt_fur_source): New.
(jt_fur_source::register_relation): New.
(jt_fur_source::query_relation): New.
(path_range_query::precompute_relations): New.
(path_range_query::precompute_phi_relations): New.
* gimple-range-path.h (path_range_query): Add resolve argument.
Add oracle, precompute_relations, precompute_phi_relations.
* tree-ssa-threadbackward.c (back_threader::back_threader): Pass
resolve argument to solver.
|
|
There was an inline extern declaration for dump_ranger that was a bit of
a hack. I've removed it in favor of an actual prototype. There are
also some trivial changes to the dumping code in the path solver.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::path_range_query): Add
header.
(path_range_query::dump): Remove extern declaration of dump_ranger.
* gimple-range-trace.cc (dump_ranger): Add DEBUG_FUNCTION marker.
* gimple-range-trace.h (dump_ranger): Add prototype.
|
|
The motivation for this patch was enabling the use of global ranges in
the path solver, but this caused certain properties of loops being
destroyed which made subsequent loop optimizations to fail.
Consequently, this patch's mail goal is to disable jump threading
involving the latch until after loop optimizations have run.
As can be seen in the test adjustments, we mostly shift the threading
from the early threaders (ethread, thread[12] to the late threaders
thread[34]). I have nuked some of the early notes in the testcases
that came as part of the jump threader rewrite. They're mostly noise
now.
Note that we could probably relax some other restrictions in
profitable_path_p when loop optimizations have completed, but it would
require more testing, and I'm hesitant to touch more things than needed
at this point. I have added a reminder to the function to keep this
in mind.
Finally, perhaps as a follow-up, we should apply the same restrictions to
the forward threader. At some point I'd like to combine the cost models.
Tested on x86-64 Linux.
p.s. There is a thorough discussion involving the limitations of jump
threading involving loops here:
https://gcc.gnu.org/pipermail/gcc/2021-September/237247.html
gcc/ChangeLog:
* tree-pass.h (PROP_loop_opts_done): New.
* gimple-range-path.cc (path_range_query::internal_range_of_expr):
Intersect with global range.
* tree-ssa-loop.c (tree_ssa_loop_done): Set PROP_loop_opts_done.
* tree-ssa-threadbackward.c
(back_threader_profitability::profitable_path_p): Disable
threading through latches until after loop optimizations have run.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/ssa-dom-thread-2b.c: Adjust for disabling of
threading through latches.
* gcc.dg/tree-ssa/ssa-dom-thread-6.c: Same.
* gcc.dg/tree-ssa/ssa-dom-thread-7.c: Same.
Co-authored-by: Michael Matz <matz@suse.de>
|
|
The path solver's range_of_stmt() was handcuffed to only fold
GIMPLE_COND statements, since those were the only statements the
backward threader needed to resolve. However, there is no need for this
restriction, as the folding code is perfectly capable of folding any
statement.
This can be the case when trying to fold other statements in the final
block of a path (for instance, in the forward threader as it tries to
fold candidate statements along a path).
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::range_of_stmt): Remove
GIMPLE_COND special casing.
(path_range_query::range_defined_in_block): Use range_of_stmt
instead of calling fold_range directly.
|
|
Keeping track of unreachable calculations while traversing a path is
useful to determine edge reachability, among other things. We've been
doing this ad-hoc in the backwards threader, so this provides a cleaner
way of accessing the information.
This patch also makes it easier to compare different threading
implementations, in some upcoming work. For example, it's currently
difficult to gague how good we're doing compared to the forward threader,
because it can thread paths that are obviously unreachable. This
provides a way of discarding those paths.
Note that I've opted to keep unreachable_path_p() out-of-line, because I
have local changes that will enhance this method.
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::range_of_expr): Set
m_undefined_path when appropriate.
(path_range_query::internal_range_of_expr): Copy from range_of_expr.
(path_range_query::unreachable_path_p): New.
(path_range_query::precompute_ranges): Set m_undefined_path.
* gimple-range-path.h (path_range_query::unreachable_path_p): New.
(path_range_query::internal_range_of_expr): New.
* tree-ssa-threadbackward.c (back_threader::find_taken_edge_cond):
Use unreachable_path_p.
|
|
This patch improves ranges for pointers we are interested in a path, by
using the non-null class from the ranger. This allows us to thread more
paths with minimal effort.
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::range_defined_in_block):
Adjust for non-null.
(path_range_query::adjust_for_non_null_uses): New.
(path_range_query::precompute_ranges): Call
adjust_for_non_null_uses.
* gimple-range-path.h: Add m_non_null and
adjust_for_non_null_uses.
|
|
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::dump): Dump path
length.
(path_range_query::precompute_ranges): Dump entire path.
|
|
The function postfold_gcond_edges() registers relations coming out of a
GIMPLE_COND. With upcoming changes, we may be called with statements
not in the IL (for example, dummy statements created by the
forward threader). This patch avoids breakage by exiting if the
statement does not have a defining basic block. There is a similar
change to the path solver.
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-fold.cc (fold_using_range::postfold_gcond_edges):
Skip statements with no defining BB.
* gimple-range-path.cc (path_range_query::range_defined_in_block):
Do not get confused by statements with no defining BB.
|
|
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.
|
