| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
The path_range_query constructor that takes an edge is really a
convenience function for the loop-ch pass. It feels wrong to pollute
the API with such a specialized function that could be done with
a small inline function closer to its user.
As an added benefit, we remove one use of reset_path. The last
remaining one is the forward threader one.
Tested, thread-counted, and benchmarked on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::path_range_query):
Remove constructor that takes edge.
* gimple-range-path.h (class path_range_query): Same.
* tree-ssa-loop-ch.cc (edge_range_query): New.
(entry_loop_condition_is_static): Call edge_range_query.
|
|
These are a bunch of cleanups inspired by Richi's suggestion of making
path_range_query standalone, instead of having to call
compute_ranges() for each path.
I've made the ranger need explicit, and moved the responsibility for
its creation to the caller.
I've also investigated and documented why the forward threader needs its
own compute exit dependencies variant. I can't wait for it to go away
:-/.
I've also added constructors that take a path and dependencies, and
made compute_ranges() private. Unfortunately, reinstantiating
path_range_query in the forward threader caused a 14% performance
regression in DOM, because the old threader calls it over and over on
the same path to simplify statements (some of which not even in the
IL, but that's old news).
In the meantime, I've left the ability to reset a path, but this time
appropriately called reset_path().
Tested, benchmarked, and thread counted on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::path_range_query): Add
various constructors to take a path.
(path_range_query::~path_range_query): Remove m_alloced_ranger.
(path_range_query::range_on_path_entry): Adjust for m_ranger being
a reference.
(path_range_query::set_path): Rename to...
(path_range_query::reset_path): ...this and call compute_ranges.
(path_range_query::ssa_range_in_phi): Adjust for m_ranger
reference.
(path_range_query::range_defined_in_block): Same.
(path_range_query::compute_ranges_in_block): Same.
(path_range_query::adjust_for_non_null_uses): Same.
(path_range_query::compute_exit_dependencies): Use m_path instead
of argument.
(path_range_query::compute_ranges): Remove path argument.
(path_range_query::range_of_stmt): Adjust for m_ranger reference.
(path_range_query::compute_outgoing_relations): Same.
* gimple-range-path.h (class path_range_query): Add various
constructors.
Make compute_ranges and compute_exit_dependencies private.
Rename set_path to reset_path.
Make m_ranger a reference.
Remove m_alloced_ranger.
* tree-ssa-dom.cc (pass_dominator::execute): Adjust constructor to
path_range_query.
* tree-ssa-loop-ch.cc (entry_loop_condition_is_static): Take a
ranger and instantiate a new path_range_query every time.
(ch_base::copy_headers): Pass ranger instead of path_range_query.
* tree-ssa-threadbackward.cc (class back_threader): Remove m_solver.
(back_threader::~back_threader): Remove m_solver.
(back_threader::find_taken_edge_switch): Adjust for m_ranger
reference.
(back_threader::find_taken_edge_cond): Same.
(back_threader::dump): Remove m_solver.
(back_threader::back_threader): Move verify_marked_backedges
here from the path_range_query constructor.
* tree-ssa-threadedge.cc (hybrid_jt_simplifier::simplify): Move
some code from compute_ranges_from_state here.
(hybrid_jt_simplifier::compute_ranges_from_state): Rename...
(hybrid_jt_simplifier::compute_exit_dependencies): ...to this.
* tree-ssa-threadedge.h (class hybrid_jt_simplifier): Rename
compute_ranges_from_state to compute_exit_dependencies.
Remove m_path.
|
|
The purpose of this change is to disambiguate the imports name with
its use in GORI.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::import_p): Rename to...
(path_range_query::exit_dependency_p): ...this.
(path_range_query::dump): Rename imports to exit dependencies.
(path_range_query::compute_ranges_in_phis): Same.
(path_range_query::compute_ranges_in_block): Same.
(path_range_query::adjust_for_non_null_uses): Same.
(path_range_query::compute_ranges): Same.
(path_range_query::compute_phi_relations): Same.
(path_range_query::add_to_imports): Rename to...
(path_range_query::add_to_exit_dependencies): ...this.
(path_range_query::compute_imports): Rename to...
(path_range_query::compute_exit_dependencies): ...this.
* gimple-range-path.h (class path_range_query): Rename imports to
exit dependencies.
|
|
The following fixes the use of compute_imports from the backwards
threader which ends up accessing stale m_path from a previous
threading attempt. The fix is to pass in the path explicitely
(and not the exit), and initializing it with the exit around this
call from the backwards threader. That unfortunately exposed that
we rely on this broken behavior as the new testcase shows. The
missed threading can be restored by registering all relations
from conditions on the path during solving, for the testcase the
particular important case is for relations provided by the path
entry conditional.
I've verified that the GORI query for imported ranges on edges
is not restricted this way.
This regresses the new ssa-thread-19.c testcase which is exactly
a case for the other patch re-doing how we compute imports since
this misses imports for defs that are not on the dominating path
from the exit.
That's one of the cases this regresses (it also progresses a few
due to more or the correct relations added). Overall it
reduces the number of threads from 98649 to 98620 on my set of
cc1files. I think it's a reasonable intermediate step to find
a stable, less random ground to compare stats to.
* gimple-range-path.h (path_range_query::compute_imports):
Take path as argument, not the exit block.
* gimple-range-path.cc (path_range_query::compute_imports):
Likewise, and adjust, avoiding possibly stale m_path.
(path_range_query::compute_outgoing_relations): Register
relations for all conditionals.
* tree-ssa-threadbackward.cc (back_threader::find_paths):
Adjust.
* gcc.dg/tree-ssa/ssa-thread-18.c: New testcase.
* gcc.dg/tree-ssa/ssa-thread-19.c: Likewise, but XFAILed.
|
|
Finally, the meat of the work. Convert ranger and associated clients
to vrange.
Everything's relatively mechanical given the previous patches. I did
include a minor cleanup in the edge code. There's no need to check
that the type of the switch is an integer as non-integer switches are
invalid. I verified this with an appropriately coded assert.
Tested on x86-64 & ppc64le Linux.
gcc/ChangeLog:
* gimple-range-cache.cc (ssa_block_ranges::dump): Convert to vrange.
(sbr_vector::sbr_vector): Same.
(sbr_vector::grow): Same.
(sbr_vector::set_bb_range): Same.
(sbr_vector::get_bb_range): Same.
(sbr_sparse_bitmap::sbr_sparse_bitmap): Same.
(sbr_sparse_bitmap::set_bb_range): Same.
(sbr_sparse_bitmap::get_bb_range): Same.
(block_range_cache::set_bb_range): Same.
(block_range_cache::get_bb_range): Same.
(block_range_cache::dump): Same.
(ssa_global_cache::get_global_range): Same.
(ssa_global_cache::set_global_range): Same.
(ssa_global_cache::clear): Same.
(ssa_global_cache::dump): Same.
(ranger_cache::get_global_range): Same.
(ranger_cache::set_global_range): Same.
(ranger_cache::range_of_def): Same.
(ranger_cache::entry_range): Same.
(ranger_cache::exit_range): Same.
(ranger_cache::edge_range): Same.
(ranger_cache::range_of_expr): Same.
(ranger_cache::range_on_edge): Same.
(ranger_cache::block_range): Same.
(ranger_cache::propagate_cache): Same.
(ranger_cache::fill_block_cache): Same.
(ranger_cache::range_from_dom): Same.
* gimple-range-cache.h: Same.
* gimple-range-edge.cc (gimple_outgoing_range::get_edge_range):
Same.
(gimple_outgoing_range::switch_edge_range): Same.
(gimple_outgoing_range::edge_range_p): Same.
* gimple-range-edge.h: Same.
* gimple-range-fold.cc (fur_source::get_operand): Same.
(fur_source::get_phi_operand): Same.
(fur_edge::get_operand): Same.
(fur_edge::get_phi_operand): Same.
(fur_stmt::get_operand): Same.
(fur_stmt::get_phi_operand): Same.
(fur_list::fur_list): Same.
(fur_list::get_operand): Same.
(fur_list::get_phi_operand): Same.
(fold_range): Same.
(adjust_imagpart_expr): Same.
(adjust_realpart_expr): Same.
(gimple_range_adjustment): Same.
(fold_using_range::fold_stmt): Same.
(fold_using_range::range_of_range_op): Same.
(fold_using_range::range_of_address): Same.
(fold_using_range::range_of_phi): Same.
(fold_using_range::range_of_call): Same.
(fold_using_range::range_of_builtin_call): Same.
(fold_using_range::range_of_builtin_int_call): Same.
(fold_using_range::range_of_cond_expr): Same.
(fur_source::register_outgoing_edges): Same.
* gimple-range-fold.h (fold_range): Same.
(gimple_range_type): Same.
(gimple_range_ssa_p): Same.
* gimple-range-gori.cc (gimple_range_calc_op1): Same.
(gimple_range_calc_op2): Same.
(gori_compute::compute_operand_range_switch): Same.
(gori_compute::compute_operand_range): Same.
(gori_compute::logical_combine): Same.
(gori_compute::compute_logical_operands): Same.
(gori_compute::compute_operand1_range): Same.
(gori_compute::compute_operand2_range): Same.
(gori_compute::compute_operand1_and_operand2_range): Same.
(gori_compute::outgoing_edge_range_p): Same.
(gori_compute::condexpr_adjust): Same.
* gimple-range-gori.h (gimple_range_calc_op1): Same.
(gimple_range_calc_op2): Same.
* gimple-range-path.cc (path_range_query::get_cache): Same.
(path_range_query::set_cache): Same.
(path_range_query::range_on_path_entry): Same.
(path_range_query::internal_range_of_expr): Same.
(path_range_query::range_of_expr): Same.
(path_range_query::ssa_range_in_phi): Same.
(path_range_query::range_defined_in_block): Same.
(path_range_query::compute_ranges_in_phis): Same.
(path_range_query::compute_ranges_in_block): Same.
(path_range_query::add_to_imports): Same.
(path_range_query::range_of_stmt): Same.
* gimple-range-path.h: Same.
* gimple-range-infer.cc (gimple_infer_range::add_range): Same.
(gimple_infer_range::~side_effect_manager): Same.
(gimple_infer_range::get_nonzero): Same.
(gimple_infer_range::maybe_adjust_range): Same.
(gimple_infer_range::add_range): Same.
* gimple-range-infer.h: Same.
* gimple-range-tests.cc: Same.
* gimple-range-trace.cc (range_tracer::trailer): Same.
(debug_seed_ranger): Same.
* gimple-range-trace.h: Same.
* gimple-range.cc (gimple_ranger::range_of_expr): Same.
(gimple_ranger::range_on_entry): Same.
(gimple_ranger::range_on_exit): Same.
(gimple_ranger::range_on_edge): Same.
(gimple_ranger::fold_range_internal): Same.
(gimple_ranger::range_of_stmt): Same.
(gimple_ranger::prefill_name): Same.
(gimple_ranger::prefill_stmt_dependencies): Same.
(gimple_ranger::export_global_ranges): Same.
(gimple_ranger::dump_bb): Same.
* gimple-range.h: Same.
* gimple-ssa-warn-access.cc (check_nul_terminated_array): Same.
(memmodel_to_uhwi): Same.
* tree-ssa-loop-niter.cc (refine_value_range_using_guard): Same.
(determine_value_range): Same.
(record_nonwrapping_iv): Same.
(infer_loop_bounds_from_signedness): Same.
(scev_var_range_cant_overflow): Same.
* tree-ssa-threadedge.cc (hybrid_jt_simplifier::simplify): Same.
* value-query.cc (range_query::range_on_edge): Same.
(range_query::range_of_stmt): Same.
(range_query::value_of_expr): Same.
(range_query::value_on_edge): Same.
(range_query::value_of_stmt): Same.
(range_query::get_tree_range): Same.
(update_global_range): Same.
(get_range_global): Same.
(gimple_range_global): Same.
(global_range_query::range_of_expr): Same.
(range_query::query_relation): Same.
* value-query.h (gimple_range_global): Same.
(update_global_range): Same.
* vr-values.cc (vr_values::range_of_expr): Same.
(bounds_of_var_in_loop): Same.
(simplify_using_ranges::vrp_visit_cond_stmt): Same.
* vr-values.h (class vr_values): Same.
* tree-ssa-loop-unswitch.cc (unswitch_predicate): Same.
|
|
Replace the non-null procesing with a generic side effect implementation that
can handle arbitrary side effects.
* Makefile.in (OBJS): Add gimple-range-side-effect.o.
* gimple-range-cache.cc (non_null_ref::non_null_ref): Delete.
(non_null_ref::~non_null_ref): Delete.
(non_null_ref::set_nonnull): Delete.
(non_null_ref::non_null_deref_p): Delete.
(non_null_ref::process_name): Delete.
(ranger_cache::ranger_cache): Initialize m_exit object.
(ranger_cache::fill_block_cache): Use m_exit object intead of nonnull.
(ranger_cache::range_from_dom): Use side_effect class and m_exit object.
(ranger_cache::update_to_nonnull): Delete.
(non_null_loadstore): Delete.
(ranger_cache::block_apply_nonnull): Delete.
(ranger_cache::apply_side_effects): New.
* gimple-range-cache.h (class non_null_ref): Delete.
(non_null_ref::adjust_range): Delete.
(class ranger_cache): Adjust prototypes, add side effect manager.
* gimple-range-path.cc (path_range_query::range_defined_in_block): Use
side effect manager for queries.
(path_range_query::adjust_for_non_null_uses): Ditto.
* gimple-range-path.h (class path_range_query): Delete non_null_ref.
* gimple-range-side-effect.cc: New.
* gimple-range-side-effect.h: New.
* gimple-range.cc (gimple_ranger::gimple_ranger): Update contructor.
(gimple_ranger::range_of_expr): Check def block for override value.
(gimple_ranger::range_on_entry): Don't scan dominators for non-null.
(gimple_ranger::range_on_edge): Check for outgoing side-effects.
(gimple_ranger::register_side_effects): Call apply_side_effects.
(enable_ranger): Update contructor.
* gimple-range.h (class gimple_ranger): Update prototype.
(enable_ranger): Update prototype.
* tree-vrp.cc (execute_ranger_vrp): Invoke without immediate-use flag.
|
|
As discussed in PR103721, the problem here is that we are crossing a
backedge and causing us to use relations from a previous iteration of a
loop.
This handles the testcases in both PR103721 and PR104067 which are variants
of the same thing.
Tested on x86-64 Linux with the usual regstrap as well as verifying the
thread count before and after the patch. The number of threads is
reduced by a miniscule amount.
gcc/ChangeLog:
PR tree-optimization/103721
* gimple-range-path.cc
(path_range_query::relations_may_be_invalidated): New.
(path_range_query::compute_ranges_in_block): Reset relations if
they may be invalidated.
(path_range_query::maybe_register_phi_relation): Exit if relations
may be invalidated on incoming edge.
(path_range_query::compute_phi_relations): Pass incoming PHI edge
to maybe_register_phi_relation.
* gimple-range-path.h (relations_may_be_invalidated): New.
(maybe_register_phi_relation): Pass edge instead of tree.
* tree-ssa-threadbackward.cc (back_threader::back_threader):
Mark DFS edges.
* value-relation.cc (path_oracle::path_oracle): Call
mark_dfs_back_edges.
(path_oracle::register_relation): Add SSA names to m_registered
bitmap.
(path_oracle::reset_path): Clear m_registered bitmap.
* value-relation.h (path_oracle::set_root_oracle): New.
gcc/testsuite/ChangeLog:
* gcc.dg/pr103721-2.c: New test.
* gcc.dg/pr103721.c: New test.
|
|
|
|
We're using a temporary range cache while computing ranges for PHIs to
make sure the real cache doesn't get set until all PHIs are computed.
With the ltrans beast in LTO mode this causes undue overhead.
Since we already have a bitmap to indicate whether there's a cache
entry, we can avoid the extra cache object by clearing it while PHIs
are being calculated.
gcc/ChangeLog:
PR tree-optimization/103409
* gimple-range-path.cc (path_range_query::compute_ranges_in_phis):
Do all the work with just one ssa_global_cache.
* gimple-range-path.h: Remove m_tmp_phi_cache.
|
|
Revert the patch below, as it may slow down compilation with large CFGs.
commit 8acbd7bef6edbf537e3037174907029b530212f6
Author: Aldy Hernandez <aldyh@redhat.com>
Date: Wed Nov 24 09:43:36 2021 +0100
path solver: Compute ranges in path in gimple order.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::compute_ranges_defined): Remove.
(path_range_query::compute_ranges_in_block): Revert to bitmap order.
* gimple-range-path.h: Remove compute_ranges_defined.
|
|
Andrew's patch for this PR103254 papered over some underlying
performance issues in the path solver that I'd like to address.
We are currently solving the SSA's defined in the current block in
bitmap order, which amounts to random order for all purposes. This is
causing unnecessary recursion in gori. This patch changes the order
to gimple order, thus solving dependencies before uses.
There is no change in threadable paths with this change.
Tested on x86-64 & ppc64le Linux.
gcc/ChangeLog:
PR tree-optimization/103254
* gimple-range-path.cc (path_range_query::compute_ranges_defined): New
(path_range_query::compute_ranges_in_block): Move to
compute_ranges_defined.
* gimple-range-path.h (compute_ranges_defined): New.
|
|
After auditing the PHI range calculations, I'm not convinced we've
caught all the corner cases. They haven't shown up in the wild (yet),
but better safe than sorry.
We shouldn't write anything to the cache or trigger additional
lookups while calculating a PHI, as this may cause ordering problems.
We should resolve the PHI with either the cache as it stands, or by
asking for ranges on entry to the path. I've documented this.
There was one dubious case where we called fold_range in
ssa_range_in_phi, which mostly by luck wasn't triggering lookups,
because fold_range solves a PHI by calling range_on_edge, which is set
to pick up global ranges by default in path_range_query. This is
fragile, so I've rewritten the call to explicitly use cached or global
ranges.
Also, the cache should be avoided in ssa_range_in_phi when the arg is
defined in the PHI's block, as not doing so could create an ordering
problem. We have a similar check when calculating relations in PHIs.
Tested on x86-64 & ppc64le Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::internal_range_of_expr):
Remove useless code.
(path_range_query::ssa_defined_in_bb): New.
(path_range_query::ssa_range_in_phi): Avoid fold_range call that
could trigger additional lookups.
Do not use the cache for ARGs defined in this block.
(path_range_query::compute_ranges_in_block): Use ssa_defined_in_bb.
(path_range_query::maybe_register_phi_relation): Same.
(path_range_query::range_of_stmt): Adjust comment.
* gimple-range-path.h (ssa_defined_in_bb): New.
|
|
PHIs must be resolved simulatenously, otherwise we may not pick up the
ranges incoming to the block.
For example. If we put p3_7 in the cache before all PHIs have been
computed, we will pick up the wrong p3_7 value for p2_17:
# p3_7 = PHI <1(2), 0(5)>
# p2_17 = PHI <1(2), p3_7(5)>
This patch delays updating the cache until all PHIs have been
analyzed.
gcc/ChangeLog:
PR tree-optimization/103222
* gimple-range-path.cc (path_range_query::compute_ranges_in_phis):
New.
(path_range_query::compute_ranges_in_block): Call
compute_ranges_in_phis.
* gimple-range-path.h (path_range_query::compute_ranges_in_phis):
New.
gcc/testsuite/ChangeLog:
* gcc.dg/pr103222.c: New test.
|
|
There's no need for two constructors, when we can do it all with one
that defaults to the common behavior:
path_range_query (bool resolve = true, gimple_ranger *ranger = NULL);
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::path_range_query): Merge
ctors.
(path_range_query::import_p): Move from header file.
(path_range_query::~path_range_query): Adjust for combined ctors.
* gimple-range-path.h: Merge ctors.
(path_range_query::import_p): Move to .cc file.
|
|
All users of path_range_query are currently allocating a gimple_ranger
only to pass it to the query object. It's tidier to just do it from
path_range_query if no ranger was passed.
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::path_range_query): New
ctor without a ranger.
(path_range_query::~path_range_query): Free ranger if necessary.
(path_range_query::range_on_path_entry): Adjust m_ranger for pointer.
(path_range_query::ssa_range_in_phi): Same.
(path_range_query::compute_ranges_in_block): Same.
(path_range_query::compute_imports): Same.
(path_range_query::compute_ranges): Same.
(path_range_query::range_of_stmt): Same.
(path_range_query::compute_outgoing_relations): Same.
* gimple-range-path.h (class path_range_query): New ctor.
* tree-ssa-loop-ch.c (ch_base::copy_headers): Remove gimple_ranger
as path_range_query allocates one.
* tree-ssa-threadbackward.c (class back_threader): Remove m_ranger.
(back_threader::~back_threader): Same.
|
|
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.
|
|
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.
|
|
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 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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
gcc/ChangeLog:
* gimple-range-path.h (path_range_query::dump): Mark override.
|
|
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.
|
