| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
Imports are our nomenclature for external SSA names to a block that
are used to calculate the outgoing edges for said block. For example,
in the following snippet:
<bb 2> :
_1 = b_10 == block_11;
_2 = b_10 != -1;
_3 = _1 & _2;
if (_3 != 0)
goto <bb 3>; [INV]
else
goto <bb 5>; [INV]
...the imports to the block are b_10 and block_11 since they are both
needed to calculate _3.
The path solver takes a bitmap of imports in addition to the path
itself. This sets up the number of SSA names to be on the lookout
for, while resolving the final conditional.
Calculating these imports was initially done in the threader, since it
was the only user of the path solver. With new clients, it has become
obvious that populating the imports should be a task for the path
solver, so it can be shared among the clients.
This patch moves the import code to the solver, making both the solver
and the threader simpler in the process. This is because intent is
clearer and some duplicate code was removed.
This reshuffling had the net effect of giving us a handful of new
threads through my suite of .ii files (125). This was unexpected, but
welcome nevertheless. There is no performance difference in callgrind
over the same suite.
Regstrapped on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::add_copies_to_imports):
Rename to...
(path_range_query::compute_imports): ...this. Adapt it so it can
be passed the imports bitmap instead of working on m_imports.
(path_range_query::compute_ranges): Call compute_imports in all
cases unless an imports bitmap is passed.
* gimple-range-path.h (path_range_query::compute_imports): New.
(path_range_query::add_copies_to_imports): Remove.
* tree-ssa-threadbackward.c (back_threader::resolve_def): Remove.
(back_threader::find_paths_to_names): Inline resolve_def.
(back_threader::find_paths): Call compute_imports.
(back_threader::resolve_phi): Adjust comment.
|
|
Here are some enhancements to make it easier for other clients to use
the path solver.
First, I've made the imports to the solver optional since we can
calculate them ourselves. However, I've left the ability to set them,
since the backward threader adds a few SSA names in addition to the
default ones. As a follow-up I may move all the import set up code
from the threader to the solver, as the extra imports tend to improve
the behavior slightly.
Second, Richi suggested an entry point where you just feed the solver
an edge, which will be quite convenient for a subsequent patch adding
a client in the header copying pass. The required some shuffling,
since we'll be adding the blocks on the fly. There's now a vector
copy, but the impact will be minimal, since these are just 5-6 entries
at the most.
Tested on ppc64le Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::path_range_query): Do
not init m_path.
(path_range_query::dump): Change m_path uses to non-pointer.
(path_range_query::defined_outside_path): Same.
(path_range_query::set_path): Same.
(path_range_query::add_copies_to_imports): Same.
(path_range_query::range_of_stmt): Same.
(path_range_query::compute_outgoing_relations): Same.
(path_range_query::compute_ranges): Imports are now optional.
Implement overload that takes an edge.
* gimple-range-path.h (class path_range_query): Make imports
optional for compute_ranges. Add compute_ranges(edge) overload.
Make m_path an auto_vec instead of a pointer and adjust
accordingly.
|
|
This patch makes the path solver dumps a bit more consistent.
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::dump): Clean up.
(path_range_query::compute_ranges): Same.
* value-relation.cc (path_oracle::dump): Same.
|
|
I am returning a TDF_* flag to the queue of available entries as I am
unconvinced that we need to burn an entire flag for internal debugging
constructs, especially since we seem to be running out of them.
I've added a --param=threader-debug entry similar to the one we use for
ranger debugging. Currently this only affects the backward threader,
but since the DOM threader is an outlier and on the chopping block, I
avoided using the "backward" name.
Tested on x86-64 Linux.
gcc/ChangeLog:
* dumpfile.c (dump_options): Remove TDF_THREADING entry.
* dumpfile.h (enum dump_flag): Remove TDF_THREADING and adjust
remaining entries.
* flag-types.h (enum threader_debug): New.
* gimple-range-path.cc (DEBUG_SOLVER): Use param_threader_debug.
* params.opt: Add entry for --param=threader-debug=.
|
|
The problem here is an ordering issue with a path that starts
with 19->3:
<bb 3> [local count: 916928331]:
# value_20 = PHI <value_17(19), value_7(D)(17)>
# n_27 = PHI <n_16(19), 1(17)>
n_16 = n_27 + 4;
value_17 = value_20 / 10000;
if (value_20 > 42949672959999)
goto <bb 19>; [89.00%]
else
goto <bb 4>; [11.00%]
The problem here is that both value_17 and value_20 are in the set of
imports we must pre-calculate. The value_17 name occurs first in the
bitmap, so we try to resolve it first, which causes us to recursively
solve the value_20 range. We do so correctly and put them both in the
cache. However, when we try to solve value_20 from the bitmap, we
ignore that it already has a cached entry and try to resolve the PHI
with the wrong value of value_17:
# value_20 = PHI <value_17(19), value_7(D)(17)>
The right thing to do is to avoid recalculating definitions already
solved.
Regstrapped and checked for # threads before and after on x86-64 Linux.
gcc/ChangeLog:
PR tree-optimization/103120
* gimple-range-path.cc (path_range_query::range_defined_in_block):
Bail if there's a cache entry.
gcc/testsuite/ChangeLog:
* gcc.dg/pr103120.c: New test.
|
|
The range_of_expr method provides better caching than range_on_edge.
If we have a statement, we can just it and avoid the range_on_edge
dance. Plus we can use all the range_of_expr fanciness.
Tested on x86-64 and ppc64le Linux with the usual regstrap. I also
verified that the before and after number of threads was the same or
greater in a suite of .ii files from a bootstrap.
gcc/ChangeLog:
PR tree-optimization/102943
* gimple-range-path.cc (path_range_query::range_on_path_entry):
Prefer range_of_expr unless there are no statements in the BB.
|
|
We are currently calculating implicit PHI relations for all PHI
arguments. This creates unecessary work, as we only care about SSA
names in the import bitmap. Similarly for inter-path relationals. We
can avoid things not in the bitmap.
Tested on x86-64 and ppc64le Linux with the usual regstrap. I also
verified that the before and after number of threads was the same
in a suite of .ii files from a bootstrap.
gcc/ChangeLog:
PR tree-optimization/102943
* gimple-range-path.cc (path_range_query::compute_phi_relations):
Only compute relations for SSA names in the import list.
(path_range_query::compute_outgoing_relations): Same.
* gimple-range-path.h (path_range_query::import_p): New.
|
|
Every time we have a killing statement, we must also kill the relations
seen so far. This is similar to what we did for the equivs inherent in
PHIs along a path.
Tested on x86-64 and ppc64le Linux.
gcc/ChangeLog:
* gimple-range-path.cc
(path_range_query::range_defined_in_block): Call killing_def.
|
|
Enabling the fully resolving threader triggers various relation
ordering issues that have previously been dormant because the VRP
hybrid threader (forward threader based) never gives us long enough
paths for this to matter. The new threader spares no punches in
finding non-obvious paths, so getting the relations right is
paramount.
This patch fixes a couple oversights that have gone undetected.
First, some background. There are 3 types of relations along a path:
a) Relations inherent in a PHI.
b) Relations as a side-effect of evaluating a statement.
c) Outgoing relations between blocks in a path.
We must calculate these in their proper order, otherwise we can run
into ordering issues. The current ordering is wrong, as we
precalculate PHIs for _all_ blocks before anything else, and then
proceed to register the relations throughout the path. Also, we fail
to realize that a PHI whose argument is also defined in the PHIs block
cannot be registered as an equivalence without causing more ordering
issues.
This patch fixes all the problems described above. With it we get a
handful more net threads, but most importantly, we disallow some
threads that were wrong.
Tested on x86-64 and ppc64le Linux on the usual regstrap, plus by
comparing the different thread counts before and after this patch.
gcc/ChangeLog:
* gimple-range-fold.cc (fold_using_range::range_of_range_op): Dump
operands as well as relation.
* gimple-range-path.cc
(path_range_query::compute_ranges_in_block): Compute PHI relations
first. Compute outgoing relations at the end.
(path_range_query::compute_ranges): Remove call to compute_relations.
(path_range_query::compute_relations): Remove.
(path_range_query::maybe_register_phi_relation): New.
(path_range_query::compute_phi_relations): Abstract out
registering one PHI relation to...
(path_range_query::compute_outgoing_relations): ...here.
* gimple-range-path.h (class path_range_query): Remove
compute_relations.
Add maybe_register_phi_relation.
|
|
The equivalence oracle creates a new equiv set at each def point,
killing any incoming equivalences, however in the path sensitive
oracle we create brand new equivalences at each PHI:
BB4:
BB8:
x_5 = PHI <y_8(4)>
Here we note that x_5 == y_8 at the end of the path.
The current code is intersecting this new equivalence with previously
known equivalences coming into the path. This is incorrect, as this
is a new definition. This patch kills any known equivalence before we
register a new one.
This hasn't caused problems so far, but upcoming changes to the
pipeline has us threading more aggressively and triggering corner
cases where this causes incorrect code.
I have tested this patch with the usual regstrap cycle. I have also
hacked a compiler comparing the old and new behavior to see if we were
previously threading paths where the decision was made due to invalid
equivalences. Luckily, there were no such paths, but there were 22
paths in a set of .ii files where disregarding incoming relations
allowed us to thread the path. This is a miniscule improvement,
but we moved a handful of thredable paths earlier in the pipeline,
which is always good.
Tested on x86-64 Linux.
Co-authored-by: Andrew MacLeod <amacleod@redhat.com>
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::compute_phi_relations):
Kill any global relations we may know before registering a new
one.
* value-relation.cc (path_oracle::killing_def): New.
* value-relation.h (path_oracle::killing_def): New.
|
|
In the path solver, when requesting the range of an SSA for which we
know nothing, we ask the ranger for the range incoming to the path.
We do this by asking for all the incoming ranges to the path entry
block and unioning them.
The problem here is that we're asking for a range on path entry for an
SSA which *is* defined in the path, but for which we know nothing
about:
some_global.1_2 = some_global;
_3 = (char) some_global.1_2;
This request is causing us to ask for range_on_edge of _3 on the
incoming edges to the path. This is a bit of nonsensical request
because _3 isn't live on entry to the path, so ranger correctly
returns UNDEFINED. The proper thing is to avoid asking this in the
first place.
I have added a relevant assert, since it doesn't make sense to call
range_on_path_entry for SSAs defined within the path.
Tested on x86-64 Linux.
PR tree-optimization/102736
gcc/ChangeLog:
PR tree-optimization/102736
* gimple-range-path.cc (path_range_query::range_on_path_entry):
Assert that the requested range is defined outside the path.
(path_range_query::ssa_range_in_phi): Do not call
range_on_path_entry for SSA names that are defined within the
path.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/pr102736.c: New test.
|
|
The m_oracle field in the path solver was shadowing the base class.
This was causing subtle problems while calculating outgoing edges
between blocks, because the query object being passed did not have an
oracle set.
This should further improve our solving ability.
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::compute_ranges): Use
get_path_oracle.
* gimple-range-path.h (class path_range_query): Remove shadowed
m_oracle field.
(path_range_query::get_path_oracle): New.
|
|
In analyzing PR102511, it has become abundantly clear that we need
better debugging aids for the jump threader solver. Currently
debugging these issues is a nightmare if you're not intimately
familiar with the code. This patch attempts to improve this.
First, I'm enabling path solver dumps with TDF_THREADING. None of the
available TDF_* flags are a good match, and using TDF_DETAILS would blow
up the dump file, since both threaders continually call the solver to
try out candidates. This will allow dumping path solver details without
having to resort to hacking the source.
I am also dumping the current registered_jump_thread dbg counter used
by the registry, in the solver. That way narrowing down a problematic
thread can then be examined by -fdump-*-threading and looking at the
solver details surrounding the appropriate counter (which the dbgcnt
also dumps to the dump file).
You still need knowledge of the solver to debug these issues, but at
least now it's not entirely opaque.
Tested on x86-64 Linux.
gcc/ChangeLog:
* dbgcnt.c (dbg_cnt_counter): New.
* dbgcnt.h (dbg_cnt_counter): New.
* dumpfile.c (dump_options): Add entry for TDF_THREADING.
* dumpfile.h (enum dump_flag): Add TDF_THREADING.
* gimple-range-path.cc (DEBUG_SOLVER): Use TDF_THREADING.
* tree-ssa-threadupdate.c (dump_jump_thread_path): Dump out
debug counter.
|
|
The problem here is that the solver's code solving unknown SSAs on entry
to a path was returning UNDEFINED if there were no incoming edges to the
start of the path that were not the function entry block. This caused a
cascade of pain down stream.
Tested on x86-64 Linux.
PR tree-optimization/102511
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::range_on_path_entry):
Return VARYING when nothing found.
gcc/testsuite/ChangeLog:
* gcc.dg/pr102511.c: New test.
* gcc.dg/tree-ssa/ssa-dom-thread-14.c: Adjust.
|
|
These are some minor cleanups and renames that surfaced after the
hybrid_threader work.
gcc/ChangeLog:
* gimple-range-path.cc
(path_range_query::precompute_ranges_in_block): Rename to...
(path_range_query::compute_ranges_in_block): ...this.
(path_range_query::precompute_ranges): Rename to...
(path_range_query::compute_ranges): ...this.
(path_range_query::precompute_relations): Rename to...
(path_range_query::compute_relations): ...this.
(path_range_query::precompute_phi_relations): Rename to...
(path_range_query::compute_phi_relations): ...this.
* gimple-range-path.h: Rename precompute* to compute*.
* tree-ssa-threadbackward.c
(back_threader::find_taken_edge_switch): Same.
(back_threader::find_taken_edge_cond): Same.
* tree-ssa-threadedge.c
(hybrid_jt_simplifier::compute_ranges_from_state): Same.
(hybrid_jt_state::register_equivs_stmt): Inline...
* tree-ssa-threadedge.h: ...here.
|
|
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.
|
