| 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.
|
|
gcc/ChangeLog:
* gimple-range-path.cc
(path_range_query::compute_exit_dependencies): Use
gimple_range_ssa_names.
|
|
When we cross a backedge in the path solver, we reset the path
relations and nuke the root oracle. However, we forget to reset it
for the next path. This is causing us to miss threads because
subsequent paths will have no root oracle to use.
With this patch we get 201 more threads in the threadfull passes in my
.ii files and 118 more overall (DOM gets less because threadfull runs
before).
Normally, I'd recommend this for the GCC 12 branch, but considering
how sensitive other passes are to jump threading, and that there is no
PR associated with this, perhaps we should leave this out. Up to the
release maintainers of course.
gcc/ChangeLog:
* gimple-range-path.cc
(path_range_query::compute_ranges_in_block): Remove
set_root_oracle call.
(path_range_query::compute_ranges): Pass ranger oracle to
reset_path.
* value-relation.cc (path_oracle::reset_path): Set root oracle.
* value-relation.h (path_oracle::reset_path): Add root oracle
argument.
|
|
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.
|
|
I've noticed that range_on_path_entry does mightly complicated things
that don't make sense to me and the commentary might just be
out of date. For the sake of it I replaced it with range_on_entry
and statistics show we thread _more_ jumps with that, so better
not do magic there.
* gimple-range-path.cc (range_on_path_entry): Just
call range_on_entry.
|
|
This avoids going BBs outside of the path when adding def chains
to the set of imports. It also syncs the code with
range_def_chain::get_def_chain to not miss out on some imports
this function would identify.
* gimple-range-path.cc (path_range_query::compute_imports):
Restrict walking SSA defs to blocks inside the path. Track
the same operands as range_def_chain::get_def_chain does.
|
|
This revisits how we compute imports later used for the ranger path
query during backwards threading. The compute_imports function
of the path solver ends up pulling the SSA def chain of regular
stmts without limit and since it starts with just the gori imports
of the path exit it misses some interesting names to translate
during path discovery. In fact with a still empty path this
compute_imports function looks like not the correct tool.
The following instead implements what it does during the path discovery
and since we add the exit block we seed the initial imports and
interesting names from just the exit conditional. When we then
process interesting names (aka imports we did not yet see the definition
of) we prune local defs but add their uses in a similar way as
compute_imports would have done.
compute_imports also is lacking in its walking of the def chain
compared to range_def_chain::get_def_chain which for example
handles &_1->x specially through range_op_handler and
gimple_range_operand1, so the code copies this. A fix for
compute_imports will be done separately, also fixing the unbound
walk there.
The patch also properly unwinds m_imports during the path discovery
backtracking and from a debugging session I have verified the two
sets evolve as expected now while previously behaving slightly erratic.
Fortunately the m_imports set now also is shrunken significantly for
the PR69592 testcase (aka PR106514) so that there's overall speedup
when increasing --param max-jump-thread-duplication-stmts as
15 -> 30 -> 60 -> 120 from 1s -> 2s -> 13s -> 27s to with the patch
1s -> 2s -> 4s -> 8s.
This runs into a latent issue in X which doesn't seem to expect
any PHI nodes with a constant argument on an edge inside the path.
But we now have those as interesting, for example for the ICEing
g++.dg/torture/pr100925.C which just has sth like
if (i)
x = 1;
else
x = 5;
if (x == 1)
...
where we now have the path from if (i) to if (x) and the PHI for x
in the set of imports to consider for resolving x == 1 which IMHO
looks exactly like what we want. The path_range_query::ssa_range_in_phi
papers over the issue and drops the range to varying instead of
crashing. I didn't want to mess with this any further in this patch
(but I couldn't resist replacing the loop over PHI args with
PHI_ARG_DEF_FROM_EDGE, so mind the re-indenting).
PR tree-optimization/106514
* tree-ssa-threadbackward.cc (back_threader::find_paths_to_names):
Compute and unwind both m_imports and interesting on the fly during
path discovery.
(back_threader::find_paths): Compute the original m_imports
from just the SSA uses of the exit conditional. Drop
handling single_succ_to_potentially_threadable_block.
* gimple-range-path.cc (path_range_query::ssa_range_in_phi): Handle
constant PHI arguments without crashing. Use PHI_ARG_DEF_FROM_EDGE.
* gcc.dg/tree-ssa/ssa-thread-19.c: Un-XFAIL.
* gcc.dg/tree-ssa/ssa-thread-20.c: New testcase.
|
|
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.
|
|
compute_ranges_in_block loops over the import list and then checks the
same bit in exports. It is nmore efficent to loop over the intersection
of the 2 bitmaps.
PR tree-optimization/106514
* gimple-range-path.cc (path_range_query::compute_ranges_in_block):
Use EXECUTE_IF_AND_IN_BITMAP to loop over 2 bitmaps.
|
|
[I have conservatively assumed that both the loop-ch and loop-unswitch
passes, which also use the ranger, only support integers and pointers.
If the goal is to handle other types as well, irange::supports_p()
should be Value_Range::supports_type_p(), and any uses of
int_range_max should be converted to Value_Range. I can help in the
conversion if you'd like.]
As discussed, this patch disambiguates the use of supports_type_p
throughout, as what ranger supports is a totally different question
than what a given range variant (irange, frange, etc) supports.
Unfortunately we need both a static method and a virtual method, and
they can't be named the same. The uses are documented in the vrange
class:
+// To query what types ranger and the entire ecosystem can support,
+// use Value_Range::supports_type_p(tree type). This is a static
+// method available independently of any vrange object.
+//
+// To query what a given vrange variant can support, use:
+// irange::supports_p ()
+// frange::supports_p ()
+// etc
+//
+// To query what a range object can support, use:
+// void foo (vrange &v, irange &i, frange &f)
+// {
+// if (v.supports_type_p (type)) ...
+// if (i.supports_type_p (type)) ...
+// if (f.supports_type_p (type)) ...
+// }
The value_range_equiv::supports_p() method can be use to determine
what legacy VRP supports, as irange::supports_p() will no longer be
applicable in the evrp analyzer code base once irange and prange are
split.
Tested on x86-64 Linux.
gcc/ChangeLog:
* gimple-range-edge.cc (gimple_outgoing_range_stmt_p): Adjust for
an object level supports_type_p for irange and a static
Value_Range::supports_type_p.
* gimple-range-fold.cc (fold_using_range::range_of_range_op): Same.
(fold_using_range::range_of_address): Same.
(fold_using_range::range_of_builtin_call): Same.
* gimple-range-fold.h (gimple_range_type): Same.
(gimple_range_ssa_p): Same.
* gimple-range-path.cc (path_range_query::internal_range_of_expr):
Same.
(path_range_query::range_of_stmt): Same.
(path_range_query::add_to_imports): Same.
* gimple-range.cc (gimple_ranger::range_on_edge): Same.
(gimple_ranger::export_global_ranges): Same.
* gimple-ssa-evrp-analyze.cc
(evrp_range_analyzer::record_ranges_from_phis): Same.
* range-op.cc (range_operator::wi_fold): Same.
(range_operator::fold_range): Same.
* tree-ssa-loop-ch.cc (entry_loop_condition_is_static): Same.
* tree-ssa-loop-unswitch.cc (struct unswitch_predicate): Same.
(evaluate_control_stmt_using_entry_checks): Same.
* tree-ssa-threadedge.cc
(hybrid_jt_simplifier::compute_ranges_from_state): Same.
* tree-vrp.cc (supported_types_p): Same.
* value-query.cc (range_query::value_of_expr): Same.
(range_query::value_on_edge): Same.
(range_query::value_of_stmt): Same.
(range_query::get_tree_range): Same.
(get_range_global): Same.
(global_range_query::range_of_expr): Same.
* value-range-equiv.h (class value_range_equiv): Same.
* value-range.cc (irange::supports_type_p): Same.
(unsupported_range::supports_type_p): Same.
* value-range.h (enum value_range_discriminator): Same.
(Value_Range::init): Same.
(Value_Range::supports_type_p): Same.
(irange::supports_type_p): Same.
(irange::supports_p): Same.
(vrange::supports_type_p): Same.
(vrange_allocator::alloc_vrange): Same.
|
|
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.
|
|
Now that we have generic ranges, we need a way to define generic local
temporaries on the stack for intermediate calculations in the ranger
and elsewhere. We need temporaries analogous to int_range_max, but
for any of the supported types (currently just integers, but soon
integers, pointers, and floats).
The Value_Range object is such a temporary. It is designed to be
transparently used as a vrange. It shares vrange's abstract API, and
implicitly casts itself to a vrange when passed around.
The ultimate name will be value_range, but we need to remove legacy
first for that to happen. Until then, Value_Range will do.
Sample usage is as follows. Instead of:
extern void foo (vrange &);
int_range_max t;
t.set_nonzero (type);
foo (t);
one does:
Value_Range t (type);
t.set_nonzero (type);
foo (t);
You can also delay initialization, for use in loops for example:
Value_Range t;
...
t.set_type (type);
t.set_varying (type);
Creating an supported range type, will result in an unsupported_range
object being created, which will trap if anything but set_undefined()
and undefined_p() are called on it. There's no size penalty for the
unsupported_range, since its immutable and can be shared across
instances.
Since supports_type_p() is called at construction time for each
temporary, I've removed the non-zero check from this function, which
was mostly unneeded. I fixed the handful of callers that were
passing null types, and in the process sped things up a bit.
As more range types come about, the Value_Range class will be augmented
to support them by adding the relevant bits in the initialization
code, etc.
Tested on x86-64 & ppc64le Linux.
gcc/ChangeLog:
* gimple-range-fold.h (gimple_range_type): Check type before
calling supports_type_p.
* gimple-range-path.cc (path_range_query::range_of_stmt): Same.
* value-query.cc (range_query::get_tree_range): Same.
* value-range.cc (Value_Range::lower_bound): New.
(Value_Range::upper_bound): New.
(Value_Range::dump): New.
* value-range.h (class Value_Range): New.
(irange::supports_type_p): Do not check if type is non-zero.
|
|
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.
|
|
Re-using some common things like EQ_EXPR and other relationals made
certain things easier, but complicated debugging and added extra overhead
when accessing lookup tables. With forthcoming additional relation types,
it makes more sense to simple have a distinct relation kind.
* gimple-range-fold.cc (fold_using_range::range_of_phi): Use new VREL_*
enumerated values.
* gimple-range-path.cc (maybe_register_phi_relation): Ditto.
* range-op.cc (*::lhs_op1_relation): Return relation_kind, and use
new VREL enumerated values.
(*::lhs_op2_relation): Ditto.
(*::op1_op2_relation): Ditto.
(*::fold_range): Use new VREL enumerated values.
(minus_op1_op2_relation_effect): Ditto.
(range_relational_tests): Ditto.
* range-op.h (fold_range, op1_range, op2_range): Use VREL_VARYING.
(lhs_op1_relation, lhs_op2_relation, op1_op2_relation): Return
relation_kind.
(*_op1_op2_relation): Return relation_kind.
(relop_early_resolve): Use VREL_UNDEFINED.
* value-query.cc (range_query::query_relation): Use VREL_VARYING.
* value-relation.cc (VREL_LAST): Change enumerated value.
(vrel_range_assert): Delete.
(print_relation): Remove range assert.
(rr_negate_table): Adjust table to use new enumerated values..
(relation_negate): Remove range assert.
(rr_swap_table): Adjust.
(relation_swap): Remove range assert.
(rr_intersect_table): Adjust.
(relation_intersect): Remove range assert.
(rr_union_table): Adjust.
(relation_union): Remove range assert.
(rr_transitive_table): Adjust.
(relation_transitive): Remove range assert.
(equiv_oracle::query_relation): Use new VREL enumerated values.
(equiv_oracle::register_relation): Ditto.
(relation_oracle::register_stmt): Ditto.
(dom_oracle::set_one_relation): Ditto.
(dom_oracle::register_transitives): Ditto.
(dom_oracle::query_relation): Ditto.
(path_oracle::register_relation): Ditto.
(path_oracle::query_relation): Ditto.
* value-relation.h (enum relation_kind_t): New relation_kind.
(*_op1_op2_relation): Adjust prototypes.
|
|
This patch adjusts uses of nonnull to accurately reflect "somewhere in block".
It also adds the ability to register statement side effects within a block
for ranger which will apply for the rest of the block.
PR tree-optimization/104288
gcc/
* gimple-range-cache.cc (non_null_ref::set_nonnull): New.
(non_null_ref::adjust_range): Move to header.
(ranger_cache::range_of_def): Don't check non-null.
(ranger_cache::entry_range): Don't check non-null.
(ranger_cache::range_on_edge): Check for nonnull on normal edges.
(ranger_cache::update_to_nonnull): New.
(non_null_loadstore): New.
(ranger_cache::block_apply_nonnull): New.
* gimple-range-cache.h (class non_null_ref): Update prototypes.
(non_null_ref::adjust_range): Move to here and inline.
(class ranger_cache): Update prototypes.
* gimple-range-path.cc (path_range_query::range_defined_in_block): Do
not search dominators.
(path_range_query::adjust_for_non_null_uses): Ditto.
* gimple-range.cc (gimple_ranger::range_of_expr): Check on-entry for
def overrides. Do not check nonnull.
(gimple_ranger::range_on_entry): Check dominators for nonnull.
(gimple_ranger::range_on_edge): Check for nonnull on normal edges..
(gimple_ranger::register_side_effects): New.
* gimple-range.h (gimple_ranger::register_side_effects): New.
* tree-vrp.cc (rvrp_folder::fold_stmt): Call register_side_effects.
gcc/testsuite/
* gcc.dg/pr104288.c: New.
|
|
gcc/ChangeLog:
* cfganal.cc (verify_marked_backedges): New.
* cfganal.h (verify_marked_backedges): New.
* gimple-range-path.cc (path_range_query::path_range_query):
Verify freshness of back edges.
* tree-ssa-loop-ch.cc (ch_base::copy_headers): Call
mark_dfs_back_edges.
* tree-ssa-threadbackward.cc (back_threader::back_threader): Move
path_range_query construction after backedges have been
updated.
|
|
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.
|
|
In a follow-up patch I will be pruning the set of exported ranges
within blocks to avoid unnecessary work. In order to do this, all the
interesting SSA names must be in the internal import bitmap ahead of
time. I had already abstracted them out into compute_imports, but I
missed the boolean code. This fixes the oversight.
There's a net gain of 25 threadable paths, which is unexpected but
welcome.
Tested on x86-64 & ppc64le Linux.
gcc/ChangeLog:
PR tree-optimization/103254
* gimple-range-path.cc (path_range_query::compute_ranges): Move
exported boolean code...
(path_range_query::compute_imports): ...here.
|
|
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.
|
|
This has been a long time coming, but we weren't able to make the
change because of some unrelated regressions.
Tested on x86-64 & ppc64le Linux.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::internal_range_of_expr):
Default to global range if nothing found.
gcc/testsuite/ChangeLog:
* g++.dg/tree-ssa/pr31146-2.C: Add -fno-thread-jumps.
|
|
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.
|
|
PHIs must be resolved first while solving ranges in a block,
regardless of where they appear in the import bitmap. We went through
a similar exercise for the relational code, but missed these.
Tested on x86-64 & ppc64le Linux.
gcc/ChangeLog:
PR tree-optimization/103202
* gimple-range-path.cc
(path_range_query::compute_ranges_in_block): Solve PHI imports first.
|
|
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.
|
|
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.
|
