aboutsummaryrefslogtreecommitdiff
path: root/gcc/gimple-range-cache.cc
AgeCommit message (Collapse)AuthorFilesLines
2024-01-03Update copyright years.Jakub Jelinek1-1/+1
2023-11-13gimple-range-cache: Fix ICEs when dumping details [PR111967]Jakub Jelinek1-5/+11
The following testcase ICEs when dumping details. When m_ssa_ranges vector is created, it is safe_grow_cleared (num_ssa_names), but when when some new SSA_NAME is added, we strangely grow it to num_ssa_names + 1 instead and later on the 3 argument dump method iterates from 1 to m_ssa_ranges.length () - 1 and uses ssa_name (x) on each; but because set_bb_range grew it one too much, ssa_name (m_ssa_ranges.length () - 1) might be after the end of the ssanames vector and ICE. The fix grows the vector consistently only to num_ssa_names, doesn't waste time checking m_ssa_ranges[0] because there is no ssa_names (0), it is always NULL, before using ssa_name (x) checks if we'll need it at all (we check later if m_ssa_ranges[x] is non-NULL, so we might check it earlier as well) and also in the last loop iterates until m_ssa_ranges.length () rather than num_ssa_names, I don't see a reason for the inconsistency and in theory some SSA_NAME could be added without set_bb_range called for it and the vector could be shorter than the ssanames vector. To actually fix the ICE, either the first hunk or the last 2 hunks would be enough, but I think it doesn't hurt to change all the spots. 2023-11-13 Jakub Jelinek <jakub@redhat.com> PR tree-optimization/111967 * gimple-range-cache.cc (block_range_cache::set_bb_range): Grow m_ssa_ranges to num_ssa_names rather than num_ssa_names + 1. (block_range_cache::dump): Iterate from 1 rather than 0. Don't use ssa_name (x) unless m_ssa_ranges[x] is non-NULL. Iterate to m_ssa_ranges.length () rather than num_ssa_names. * gcc.dg/tree-ssa/pr111967.c: New test.
2023-10-09Ensure float equivalences include + and - zero.Andrew MacLeod1-0/+3
A floating point equivalence may not properly reflect both signs of zero, so be pessimsitic and ensure both signs are included. PR tree-optimization/111694 gcc/ * gimple-range-cache.cc (ranger_cache::fill_block_cache): Adjust equivalence range. * value-relation.cc (adjust_equivalence_range): New. * value-relation.h (adjust_equivalence_range): New prototype. gcc/testsuite/ * gcc.dg/pr111694.c: New.
2023-09-20Tweak merge_range API.Andrew MacLeod1-24/+15
merge_range use to return TRUE if there was already a range. Now it returns TRUE if a new range is added, OR updates and existing range with a new value. FALSE is returned when the range already matches. * gimple-range-cache.cc (ssa_cache::merge_range): Change meaning of the return value. (ssa_cache::dump): Don't print GLOBAL RANGE header. (ssa_lazy_cache::merge_range): Adjust return value meaning. (ranger_cache::dump): Print GLOBAL RANGE header.
2023-07-28Add a merge_range to ssa_cache and use it. add empty_p and param tweaks.Andrew MacLeod1-0/+45
* gimple-range-cache.cc (ssa_cache::merge_range): New. (ssa_lazy_cache::merge_range): New. * gimple-range-cache.h (class ssa_cache): Adjust protoypes. (class ssa_lazy_cache): Ditto. * gimple-range.cc (assume_query::calculate_op): Use merge_range.
2023-05-24Make ssa_cache a range_query.Andrew MacLeod1-0/+14
By providing range_of_expr as a range_query, we can fold and do other interesting things using values from the global table. Make ranger's knonw globals available via const_query. * gimple-range-cache.cc (ssa_cache::range_of_expr): New. * gimple-range-cache.h (class ssa_cache): Inherit from range_query. (ranger_cache::const_query): New. * gimple-range.cc (gimple_ranger::const_query): New. * gimple-range.h (gimple_ranger::const_query): New prototype.
2023-05-24Make ssa_cache and ssa_lazy_cache virtual.Andrew MacLeod1-13/+30
Making them virtual allows us to interchangebly use the caches. * gimple-range-cache.cc (ssa_cache::dump): Use get_range. (ssa_cache::dump_range_query): Delete. (ssa_lazy_cache::dump_range_query): Delete. (ssa_lazy_cache::get_range): Move from header file. (ssa_lazy_cache::clear_range): ditto. (ssa_lazy_cache::clear): Ditto. * gimple-range-cache.h (class ssa_cache): Virtualize. (class ssa_lazy_cache): Inherit and virtualize.
2023-05-24Only update global value if it changes.Andrew MacLeod1-1/+9
Do not update and propagate a global value if it hasn't changed. PR tree-optimization/109695 * gimple-range-cache.cc (ranger_cache::get_global_range): Add changed param. * gimple-range-cache.h (ranger_cache::get_global_range): Ditto. * gimple-range.cc (gimple_ranger::range_of_stmt): Pass changed flag to set_global_range. (gimple_ranger::prefill_stmt_dependencies): Ditto.
2023-05-24Use negative values to reflect always_current in the temporal cache.Andrew MacLeod1-13/+30
Instead of using 0, use negative timestamps to reflect always_current state. If the value doesn't change, keep the timestamp rather than creating a new one and invalidating any dependencies. PR tree-optimization/109695 * gimple-range-cache.cc (temporal_cache::temporal_value): Return a positive int. (temporal_cache::current_p): Check always_current method. (temporal_cache::set_always_current): Add param and set value appropriately. (temporal_cache::always_current_p): New. (ranger_cache::get_global_range): Adjust. (ranger_cache::set_global_range): set always current first.
2023-05-24Choose better initial values for ranger.Andrew MacLeod1-1/+16
Instead of defaulting to VARYING, fold the stmt using just global ranges. PR tree-optimization/109695 * gimple-range-cache.cc (ranger_cache::get_global_range): Call fold_range with global query to choose an initial value.
2023-05-06Remove type from vrange_storage::equal_p.Aldy Hernandez1-1/+1
The equal_p method in vrange_storage is only used to compare ranges that are the same type. No sense passing the type if it can be determined from the range being compared. gcc/ChangeLog: * gimple-range-cache.cc (sbr_sparse_bitmap::set_bb_range): Do not pass type to vrange_storage::equal_p. * value-range-storage.cc (vrange_storage::equal_p): Remove type. (irange_storage::equal_p): Same. (frange_storage::equal_p): Same. * value-range-storage.h (class frange_storage): Same.
2023-05-01vrange_storage overhaulAldy Hernandez1-31/+30
[tl;dr: This is a rewrite of value-range-storage.* such that global ranges and the internal ranger cache can use the same efficient storage mechanism. It is optimized such that when wide_ints are dropped into irange, the copying back and forth from storage will be very fast, while being able to hold any number of sub-ranges dynamically allocated at run-time. This replaces the global storage mechanism which was limited to 6-subranges.] Previously we had a vrange allocator for use in the ranger cache. It worked with trees and could be used in place (fast), but it was not memory efficient. With the upcoming switch to wide_ints for irange, we can't afford to allocate ranges that can be used in place, because an irange will be significantly larger, as it will hold full wide_ints. We need a trailing_wide_int mechanism similar to what we use for global ranges, but fast enough to use in the ranger's cache. The global ranges had another allocation mechanism that was trailing_wide_int based. It was memory efficient but slow given the constant conversions from trees to wide_ints. This patch gets us the best of both worlds by providing a storage mechanism with a custom trailing wide int interface, while at the same time being fast enough to use in the ranger cache. We use a custom trailing wide_int mechanism but more flexible than trailing_wide_int, since the latter has compile-time fixed-sized wide_ints. The original TWI structure has the current length of each wide_int in a static portion preceeding the variable length: template <int N> struct GTY((user)) trailing_wide_ints { ... ... /* The current length of each number. that will, in turn, turn off TBAA on gimple, trees and RTL. */ struct {unsigned char len;} m_len[N]; /* The variable-length part of the structure, which always contains at least one HWI. Element I starts at index I * M_MAX_LEN. */ HOST_WIDE_INT m_val[1]; }; We need both m_len[] and m_val[] to be variable-length at run-time. In the previous incarnation of the storage mechanism the limitation of m_len[] being static meant that we were limited to whatever [N] could use up the unused bits in the TWI control world. In practice this meant we were limited to 6 sub-ranges. This worked fine for global ranges, but is a no go for our internal cache, where we must represent things exactly (ranges for switches, etc). The new implementation removes this restriction by making both m_len[] and m_val[] variable length. Also, rolling our own allows future optimization be using some of the leftover bits in the control world. Also, in preparation for the wide_int conversion, vrange_storage is now optimized to blast the bits directly into the ultimate irange instead of going through the irange API. So ultimately copying back and forth between the ranger cache and the storage mechanism is just a matter of copying a few bits for the control word, and copying an array of HOST_WIDE_INTs. These changes were heavily profiled, and yielded a good chunk of the overall speedup for the wide_int conversion. Finally, vrange_storage is now a first class structure with GTY markers and all, thus alleviating the void * hack in struct tree_ssa_name and friends. This removes a few warts in the API and looks cleaner overall. gcc/ChangeLog: * gimple-fold.cc (maybe_fold_comparisons_from_match_pd): Adjust for vrange_storage. * gimple-range-cache.cc (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::block_range_cache): Same. (ssa_global_cache::ssa_global_cache): Same. (ssa_global_cache::get_global_range): Same. (ssa_global_cache::set_global_range): Same. * gimple-range-cache.h: Same. * gimple-range-edge.cc (gimple_outgoing_range::gimple_outgoing_range): Same. (gimple_outgoing_range::switch_edge_range): Same. (gimple_outgoing_range::calc_switch_ranges): Same. * gimple-range-edge.h: Same. * gimple-range-infer.cc (infer_range_manager::infer_range_manager): Same. (infer_range_manager::get_nonzero): Same. (infer_range_manager::maybe_adjust_range): Same. (infer_range_manager::add_range): Same. * gimple-range-infer.h: Rename obstack_vrange_allocator to vrange_allocator. * tree-core.h (struct irange_storage_slot): Remove. (struct tree_ssa_name): Remove irange_info and frange_info. Make range_info a pointer to vrange_storage. * tree-ssanames.cc (range_info_fits_p): Adjust for vrange_storage. (range_info_alloc): Same. (range_info_free): Same. (range_info_get_range): Same. (range_info_set_range): Same. (get_nonzero_bits): Same. * value-query.cc (get_ssa_name_range_info): Same. * value-range-storage.cc (class vrange_internal_alloc): New. (class vrange_obstack_alloc): New. (class vrange_ggc_alloc): New. (vrange_allocator::vrange_allocator): New. (vrange_allocator::~vrange_allocator): New. (vrange_storage::alloc_slot): New. (vrange_allocator::alloc): New. (vrange_allocator::free): New. (vrange_allocator::clone): New. (vrange_allocator::clone_varying): New. (vrange_allocator::clone_undefined): New. (vrange_storage::alloc): New. (vrange_storage::set_vrange): Remove slot argument. (vrange_storage::get_vrange): Same. (vrange_storage::fits_p): Same. (vrange_storage::equal_p): New. (irange_storage::write_lengths_address): New. (irange_storage::lengths_address): New. (irange_storage_slot::alloc_slot): Remove. (irange_storage::alloc): New. (irange_storage_slot::irange_storage_slot): Remove. (irange_storage::irange_storage): New. (write_wide_int): New. (irange_storage_slot::set_irange): Remove. (irange_storage::set_irange): New. (read_wide_int): New. (irange_storage_slot::get_irange): Remove. (irange_storage::get_irange): New. (irange_storage_slot::size): Remove. (irange_storage::equal_p): New. (irange_storage_slot::num_wide_ints_needed): Remove. (irange_storage::size): New. (irange_storage_slot::fits_p): Remove. (irange_storage::fits_p): New. (irange_storage_slot::dump): Remove. (irange_storage::dump): New. (frange_storage_slot::alloc_slot): Remove. (frange_storage::alloc): New. (frange_storage_slot::set_frange): Remove. (frange_storage::set_frange): New. (frange_storage_slot::get_frange): Remove. (frange_storage::get_frange): New. (frange_storage_slot::fits_p): Remove. (frange_storage::equal_p): New. (frange_storage::fits_p): New. (ggc_vrange_allocator): New. (ggc_alloc_vrange_storage): New. * value-range-storage.h (class vrange_storage): Rewrite. (class irange_storage): Rewrite. (class frange_storage): Rewrite. (class obstack_vrange_allocator): Remove. (class ggc_vrange_allocator): Remove. (vrange_allocator::alloc_vrange): Remove. (vrange_allocator::alloc_irange): Remove. (vrange_allocator::alloc_frange): Remove. (ggc_alloc_vrange_storage): New. * value-range.h (class irange): Rename vrange_allocator to irange_storage. (class frange): Same.
2023-04-26Create a lazy ssa_cache.Andrew MacLeod1-3/+42
Sparsely used ssa caches can benefit from using a bitmap to determine if a name already has an entry. Utilize it in the path query and remove its private bitmap for tracking the same info. Also use it in the "assume" query class. PR tree-optimization/108697 * gimple-range-cache.cc (ssa_global_cache::clear_range): Do not clear the vector on an out of range query. (ssa_cache::dump): Use dump_range_query instead of get_range. (ssa_cache::dump_range_query): New. (ssa_lazy_cache::dump_range_query): New. (ssa_lazy_cache::set_range): New. * gimple-range-cache.h (ssa_cache::dump_range_query): New. (class ssa_lazy_cache): New. (ssa_lazy_cache::ssa_lazy_cache): New. (ssa_lazy_cache::~ssa_lazy_cache): New. (ssa_lazy_cache::get_range): New. (ssa_lazy_cache::clear_range): New. (ssa_lazy_cache::clear): New. (ssa_lazy_cache::dump): New. * gimple-range-path.cc (path_range_query::path_range_query): Do not allocate a ssa_cache object nor has_cache bitmap. (path_range_query::~path_range_query): Do not free objects. (path_range_query::clear_cache): Remove. (path_range_query::get_cache): Adjust. (path_range_query::set_cache): Remove. (path_range_query::dump): Don't call through a pointer. (path_range_query::internal_range_of_expr): Set cache directly. (path_range_query::reset_path): Clear cache directly. (path_range_query::ssa_range_in_phi): Fold with globals only. (path_range_query::compute_ranges_in_phis): Simply set range. (path_range_query::compute_ranges_in_block): Call cache directly. * gimple-range-path.h (class path_range_query): Replace bitmap and cache pointer with lazy cache object. * gimple-range.h (class assume_query): Use ssa_lazy_cache.
2023-04-26Rename ssa_global_cache to ssa_cache and add has_rangeAndrew MacLeod1-17/+28
This renames the ssa_global_cache to be ssa_cache. The original use was to function as a global cache, but its uses have expanded. Remove all mention of "global" from the class and methods. Also add a has_range method. * gimple-range-cache.cc (ssa_cache::ssa_cache): Rename. (ssa_cache::~ssa_cache): Rename. (ssa_cache::has_range): New. (ssa_cache::get_range): Rename. (ssa_cache::set_range): Rename. (ssa_cache::clear_range): Rename. (ssa_cache::clear): Rename. (ssa_cache::dump): Rename and use get_range. (ranger_cache::get_global_range): Use get_range and set_range. (ranger_cache::range_of_def): Use get_range. * gimple-range-cache.h (class ssa_cache): Rename class and methods. (class ranger_cache): Use ssa_cache. * gimple-range-path.cc (path_range_query::path_range_query): Use ssa_cache. (path_range_query::get_cache): Use get_range. (path_range_query::set_cache): Use set_range. * gimple-range-path.h (class path_range_query): Use ssa_cache. * gimple-range.cc (assume_query::assume_range_p): Use get_range. (assume_query::range_of_expr): Use get_range. (assume_query::assume_query): Use set_range. (assume_query::calculate_op): Use get_range and set_range. * gimple-range.h (class assume_query): Use ssa_cache.
2023-04-26Add sbr_lazy_vector and adjust (e)vrp sparse cacheAndrew MacLeod1-8/+64
Add a sparse vector class for cache and use if by default. Rename the evrp_* params to vrp_*, and add a param for small CFGS which use just the original basic vector. * gimple-range-cache.cc (sbr_vector::sbr_vector): Add parameter and local to optionally zero memory. (br_vector::grow): Only zero memory if flag is set. (class sbr_lazy_vector): New. (sbr_lazy_vector::sbr_lazy_vector): New. (sbr_lazy_vector::set_bb_range): New. (sbr_lazy_vector::get_bb_range): New. (sbr_lazy_vector::bb_range_p): New. (block_range_cache::set_bb_range): Check flags and Use sbr_lazy_vector. * gimple-range-gori.cc (gori_map::calculate_gori): Use param_vrp_switch_limit. (gori_compute::gori_compute): Use param_vrp_switch_limit. * params.opt (vrp_sparse_threshold): Rename from evrp_sparse_threshold. (vrp_switch_limit): Rename from evrp_switch_limit. (vrp_vector_threshold): New.
2023-04-13Ensure PHI equivalencies do not dominate the argument edge.Andrew MacLeod1-8/+1
When we create an equivalency between a PHI definition and an argument, ensure the definition does not dominate the incoming argument edge. PR tree-optimization/108139 PR tree-optimization/109462 * gimple-range-cache.cc (ranger_cache::fill_block_cache): Remove equivalency check for PHI nodes. * gimple-range-fold.cc (fold_using_range::range_of_phi): Ensure def does not dominate single-arg equivalency edges.
2023-04-12Don't use ANY PHI equivalences in range-on-entry.Andrew MacLeod1-1/+3
PR 108139 dissallows PHI equivalencies in the on-entry calculator, but it was only checking if the equivlaence was a PHI. In this case, NAME itself is a PHI with an equivlaence caused by an undefined value, so we also need to check that case. Unfortunately this un-fixes 101912. PR tree-optimization/109462 gcc/ * gimple-range-cache.cc (ranger_cache::fill_block_cache): Don't check for equivalences if NAME is a phi node. gcc/testsuite/ * gcc.dg/uninit-pr101912.c: XFAIL the warning.
2023-03-24Ranger cache dominator queries should ignore backedges.Andrew MacLeod1-0/+5
When querying dominators for cache values, ignore back edges in read-only mode. PR tree-optimization/109238 gcc/ * gimple-range-cache.cc (ranger_cache::resolve_dom): Ignore predecessors which this block dominates. gcc/testsuite/ * gcc.dg/pr109238.c: New.
2023-03-23ranger: Ranger meets aspellJakub Jelinek1-12/+12
I've noticed a comment typo in tree-vrp.cc and decided to quickly skim aspell -c on the ranger sources (with quick I on everything that looked ok or roughly ok). But not being a native English speaker, I could get stuff wrong. 2023-03-23 Jakub Jelinek <jakub@redhat.com> * value-range.cc (irange::irange_union, irange::intersect): Fix comment spelling bugs. * gimple-range-trace.cc (range_tracer::do_header): Likewise. * gimple-range-trace.h: Likewise. * gimple-range-edge.cc: Likewise. (gimple_outgoing_range_stmt_p, gimple_outgoing_range::switch_edge_range, gimple_outgoing_range::edge_range_p): Likewise. * gimple-range.cc (gimple_ranger::prefill_stmt_dependencies, gimple_ranger::fold_stmt, gimple_ranger::register_transitive_infer, assume_query::assume_query, assume_query::calculate_phi): Likewise. * gimple-range-edge.h: Likewise. * value-range.h (Value_Range::set, Value_Range::lower_bound, Value_Range::upper_bound, frange::set_undefined): Likewise. * gimple-range-gori.h (range_def_chain::depend, gori_map::m_outgoing, gori_compute): Likewise. * gimple-range-fold.h (fold_using_range): Likewise. * gimple-range-path.cc (path_range_query::compute_ranges_in_phis): Likewise. * gimple-range-gori.cc (range_def_chain::in_chain_p, range_def_chain::dump, gori_map::calculate_gori, gori_compute::compute_operand_range_switch, gori_compute::logical_combine, gori_compute::refine_using_relation, gori_compute::compute_operand1_range, gori_compute::may_recompute_p): Likewise. * gimple-range.h: Likewise. (enable_ranger): Likewise. * range-op.h (empty_range_varying): Likewise. * value-query.h (value_query): Likewise. * gimple-range-cache.cc (block_range_cache::set_bb_range, block_range_cache::dump, ssa_global_cache::clear_global_range, temporal_cache::temporal_value, temporal_cache::current_p, ranger_cache::range_of_def, ranger_cache::propagate_updated_value, ranger_cache::range_from_dom, ranger_cache::register_inferred_value): Likewise. * gimple-range-fold.cc (fur_edge::get_phi_operand, fur_stmt::get_operand, gimple_range_adjustment, fold_using_range::range_of_phi, fold_using_range::relation_fold_and_or): Likewise. * value-range-storage.h (irange_storage_slot::MAX_INTS): Likewise. * value-query.cc (range_query::value_of_expr, range_query::value_on_edge, range_query::query_relation): Likewise. * tree-vrp.cc (remove_unreachable::remove_and_update_globals, intersect_range_with_nonzero_bits): Likewise. * gimple-range-infer.cc (gimple_infer_range::check_assume_func, exit_range): Likewise. * value-relation.h: Likewise. (equiv_oracle, relation_trio::relation_trio, value_relation, value_relation::value_relation, pe_min): Likewise. * range-op-float.cc (range_operator_float::rv_fold, frange_arithmetic, foperator_unordered_equal::op1_range, foperator_div::rv_fold): Likewise. * gimple-range-op.cc (cfn_clz::fold_range): Likewise. * value-relation.cc (equiv_oracle::query_relation, equiv_oracle::register_equiv, equiv_oracle::add_equiv_to_block, value_relation::apply_transitive, relation_chain_head::find_relation, dom_oracle::query_relation, dom_oracle::find_relation_block, dom_oracle::find_relation_dom, path_oracle::register_equiv): Likewise. * range-op.cc (range_operator::wi_fold_in_parts_equiv, create_possibly_reversed_range, adjust_op1_for_overflow, operator_mult::wi_fold, operator_exact_divide::op1_range, operator_cast::lhs_op1_relation, operator_cast::fold_pair, operator_cast::fold_range, operator_abs::wi_fold, range_op_cast_tests, range_op_lshift_tests): Likewise.
2023-02-10Query rangers cache in readonly mode only from withinAndrew MacLeod1-2/+2
The change for 108356 allowed the cache to scan the dominator trees when it was attempting a lookup rather than using the local value. I inadvertantly changed the externbal interface to also do this, so all the GORI queries via range_on_edge of the cache could also do lookups. This triggered a quadratic, possible expoential time increase when the right conditions were presented. That being a cascading series of recomputaions on outgoing edge calucaltions that at then searched the dom tree instead of being a simple calcualtion using whats easily available. The fix is to use the internal API within the cache rather than the extrenal one that GORI uses. This leaves GORI computations to be resovled in linear time. PR tree-optimization/108687 gcc/ * gimple-range-cache.cc (ranger_cache::range_on_edge): Revert back to RFD_NONE mode for calculations. (ranger_cache::propagate_cache): Call the internal edge range API with RFD_READ_ONLY instead of changing the external routine.
2023-02-01Ranger cache - always use range_from_dom when updating.Andrew MacLeod1-1/+1
When updating an existing range, if we dont query the dom tree, we can get the global range instead of a proper range on some incoming edges which cause the range to not be refined properly. PR tree-optimization/108356 gcc/ * gimple-range-cache.cc (ranger_cache::range_on_edge): Always do a search of the DOM tree for a range. gcc/testsuite/ * gcc.dg/pr108356.c: New.
2023-01-02Update copyright years.Jakub Jelinek1-1/+1
2022-12-20Don't use PHI equivalences in range-on-entry.Andrew MacLeod1-0/+7
If there is only one argument to a PHI which is defined, an equivalency is created between the def and the argument. It is safe to consider the def equal to the argument, but it is dangerous to assume the argument is also equivalent to the def as there may be branches which change the range on the path to the PHI on that argument This patch avoid using that relation in range-on-entry calculations. PR tree-optimization/108139 gcc/ * gimple-range-cache.cc (ranger_cache::fill_block_cache): Do not use equivalences originating from PHIS. gcc/testsuite/ * gcc.dg/pr108139.c: New.
2022-11-07Add transitive inferred range processing.Andrew MacLeod1-14/+22
Rewalk statements at the end of a block to see if any inferred ranges affect earlier calculations and register those as inferred ranges. gcc/ PR tree-optimization/104530 * gimple-range-cache.cc (ranger_cache::register_inferred_value): New. Split from: (ranger_cache::apply_inferred_ranges): Move setting cache to separate function. * gimple-range-cache.h (register_inferred_value): New prototype. * gimple-range-infer.cc (infer_range_manager::has_range_p): New. * gimple-range-infer.h (has_range_p): New prototype. * gimple-range.cc (register_transitive_inferred_ranges): New. * gimple-range.h (register_transitive_inferred_ranges): New proto. * tree-vrp.cc (rvrp_folder::fold_stmt): Check for transitive inferred ranges at the end of the block before folding final stmt. gcc/testsuite/ * gcc.dg/pr104530.c: New.
2022-11-01Allow queries on exit block.Andrew MacLeod1-6/+10
Ranger was not allowing the exit block to be queried for range_on_entry or exit. This removes that restriction. * gimple-range-cache.cc (ranger_cache::fill_block_cache): Allow exit block to be specified. (ranger_cache::range_from_dom): If exit block is specified, use the immediate predecessor instead of the dominator to start. * gimple-range.cc (gimple_ranger::range_on_exit): Allow query for exit block.
2022-10-19Use Value_Range when applying inferred ranges.Andrew MacLeod1-1/+1
Applying an inferred range is using int_range_ma as the temporary rather than the general purpose Value_Range. This causes it to trap if we have a non-integral inferred range. * gimple-range-cache.cc (ranger_cache::range_from_dom): Use Value_Range not int_range_max.
2022-10-13propagate partial equivs in the cache.Andrew MacLeod1-6/+31
Adjust on-entry cache propagation to look for and propagate both full and partial equivalences. gcc/ PR tree-optimization/102540 PR tree-optimization/102872 * gimple-range-cache.cc (ranger_cache::fill_block_cache): Handle partial equivs. (ranger_cache::range_from_dom): Cleanup dump output. gcc/testsuite/ * gcc.dg/pr102540.c: New. * gcc.dg/pr102872.c: New.
2022-10-13Add equivalence iterator to relation oracle.Andrew MacLeod1-8/+2
Instead of looping over an exposed equivalence bitmap, provide iterators to loop over equivalences, partial equivalences, or both. * gimple-range-cache.cc (ranger_cache::fill_block_cache): Use iterator. * value-relation.cc (equiv_relation_iterator::equiv_relation_iterator): New. (equiv_relation_iterator::next): New. (equiv_relation_iterator::get_name): New. * value-relation.h (class relation_oracle): Privatize some methods. (class equiv_relation_iterator): New. (FOR_EACH_EQUIVALENCE): New. (FOR_EACH_PARTIAL_EQUIV): New. (FOR_EACH_PARTIAL_AND_FULL_EQUIV): New.
2022-08-02Check equivalencies when calculating range on entry.Andrew MacLeod1-1/+44
When propagating on-entry values in the cache, checking if any equivalence has a known value can improve results. No new calculations are made. Only queries via dominators which do not populate the cache are checked. PR tree-optimization/106474 gcc/ * gimple-range-cache.cc (ranger_cache::fill_block_cache): Query range of equivalences that may contribute to the range. gcc/testsuite/ * g++.dg/pr106474.C: New.
2022-07-24Convert some uses in ranger_cache and DOM to vrange.Aldy Hernandez1-3/+4
Here are a few conversions to type agnostic vrange I found while working on frange. Tested on x86-64 Linux. gcc/ChangeLog: * gimple-range-cache.cc (ranger_cache::edge_range): Convert to vrange. (ranger_cache::range_from_dom): Same. * tree-ssa-dom.cc (dom_opt_dom_walker::set_global_ranges_from_unreachable_edges): Same.
2022-07-19Resolve complicated join nodes in range_from_dom.Andrew MacLeod1-0/+26
Join nodes which carry outgoing ranges on incoming edges are uncommon, but can still be resolved by setting the dominator range, and then calculating incoming edges. Avoid doing so if one of the incoing edges is not dominated by the same dominator. * gimple-range-cache.cc (ranger_cache::range_from_dom): Check for incoming ranges on join nodes and add to worklist.
2022-07-19Remove recursion from range_from_dom.Andrew MacLeod1-37/+47
Avoid calling range_of_dom recursively by putting all nodes to be calculated on the worklist, and figure out which kind they are when removed from the list. * gimple-range-cache.cc (ranger_cache::resolve_dom): New. (ranger_cache::range_from_dom): Put all nodes to be calculated in the worklist and resolve after the dom walk. * gimple-range-cache.h (resolve_dom): New prototype.
2022-07-11Avoid calling range_from_dom when dominator is already resolved.Andrew MacLeod1-3/+4
range_from_dom makes a recursive call to resolve the immediate dominator when there are multiple incoming edges to a block. This is not necessary when the dominator already has an on-entry cache value. PR tree-optimization/106234 * gimple-range-cache.cc (ranger_cache::range_from_dom): Check dominator cache value before recursively resolving it.
2022-07-03Move range allocator code to value-range-storage.*Aldy Hernandez1-0/+1
Now that vrange_storage is in its own file, I think it's prudent to move all the vrange allocator code there since it's all related. The users of value-range.h do not need to know the implementation details of the storage facilities. Tested and benchmarked on x86-64 Linux. gcc/ChangeLog: * gimple-range-cache.cc: Include value-range-storage.h. * gimple-range-cache.h (class block_range_cache): Add "class" to m_range_allocator. * gimple-range-edge.cc (gimple_outgoing_range::gimple_outgoing_range): Allocate allocator. (gimple_outgoing_range::~gimple_outgoing_range): Free allocator. (gimple_outgoing_range::calc_switch_ranges): Dereference allocator. * gimple-range-edge.h: Add "class" to m_range_allocator. * gimple-range-infer.cc (infer_range_manager::infer_range_manager): Allocate allocator. (infer_range_manager::~infer_range_manager): Free allocator. (infer_range_manager::get_nonzero): Dereference allocator. (infer_range_manager::add_range): Same. * gimple-range-infer.h (class vrange_allocator): Add "class" to m_range_allocator. * value-range-storage.h (class vrange_allocator): Move from value-range.h. (class obstack_vrange_allocator): Same. (class ggc_vrange_allocator): Same. (vrange_allocator::alloc_vrange): Same. (vrange_allocator::alloc_irange): Same. * value-range.h (class vrange_allocator): Move to value-range-storage.h. (class obstack_vrange_allocator): Same. (class ggc_vrange_allocator): Same.
2022-06-30Implement ggc_vrange_allocator.Aldy Hernandez1-2/+2
This patch makes the vrange_allocator an abstract class, and uses it to implement the obstack allocator as well as a new GC allocator. The GC bits will be used to implement the vrange storage class for global ranges, which will be contributed in the next week or so. Tested and benchmarked on x86-64 Linux. gcc/ChangeLog: * gimple-range-cache.cc (block_range_cache::block_range_cache): Rename vrange_allocator to obstack_vrange_allocator. (ssa_global_cache::ssa_global_cache): Same. * gimple-range-edge.h (class gimple_outgoing_range): Same. * gimple-range-infer.h (class infer_range_manager): Same. * value-range.h (class vrange_allocator): Make abstract. (class obstack_vrange_allocator): Inherit from vrange_allocator. (class ggc_vrange_allocator): New.
2022-06-16Clear invariant bit for inferred ranges.Andrew MacLeod1-1/+6
The range of an invariant SSA (no outgoing edge range anywhere) is not tracked. If an inferred range is registered, remove the invariant flag. * gimple-range-cache.cc (ranger_cache::apply_inferred_ranges): If name was invaraint before, clear the invariant bit. * gimple-range-gori.cc (gori_map::set_range_invariant): Add a flag. * gimple-range-gori.h (gori_map::set_range_invariant): Adjust prototype.
2022-06-03Misc range temporary fixes.Aldy Hernandez1-1/+1
This fixes a couples places that were using int_range_max, but needed a generic temporary. Found while merging the frange work. Also, copying between range temporaries is actually useful :). Tested on x86-64 Linux. gcc/ChangeLog: * gimple-range-cache.cc (ranger_cache::range_from_dom): Use Value_Range. * gimple-range.cc (gimple_ranger::register_inferred_ranges): Same. * value-range.h (Value_Range::Value_Range): Implement copy constructor for Value_Range.
2022-06-01Convert ranger and clients to vrange.Aldy Hernandez1-65/+75
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.
2022-06-01Revamp irange_allocator to handle vranges.Aldy Hernandez1-26/+29
This patch revamps the range allocator to handle generic vrange's. I've cleaned it up somehow to make it obvious the various things you can allocate with it. I've also moved away from overloads into distinct names when appropriate. The various entry points are now: // Allocate a range of TYPE. vrange *alloc_vrange (tree type); // Allocate a memory block of BYTES. void *alloc (unsigned bytes); // Return a clone of SRC. template <typename T> T *clone (const T &src); It is now possible to allocate a clone of an irange, or any future range types: irange *i = allocator.clone <irange> (some_irange); frange *f = allocator.clone <frange> (some_frange); You can actually do so without the <>, but I find it clearer to specify the vrange type. So with it you can allocate a specific range type, or vrange, or a block of memory. I have rewritten the C style casts to C++ casts, since casts tend to be hints of problematic designs. With the C++ casts you can at least grep for them easier. Speak of which, the next patch, which converts ranger to vrange, will further clean this space by removing some unnecessary casts. Tested on x86-64 Linux and ppc64le Linux. * gimple-range-cache.cc (sbr_vector::sbr_vector): Adjust for vrange allocator. (sbr_vector::grow): Same. (sbr_vector::set_bb_range): Same. (sbr_sparse_bitmap::sbr_sparse_bitmap): Same. (sbr_sparse_bitmap::set_bb_range): Same. (block_range_cache::~block_range_cache): Same. (block_range_cache::set_bb_range): Same. (ssa_global_cache::ssa_global_cache): Same. (ssa_global_cache::~ssa_global_cache): Same. (ssa_global_cache::set_global_range): Same. * gimple-range-cache.h (block_range_cache): Same. (ssa_global_cache): Same. * gimple-range-edge.cc (gimple_outgoing_range::calc_switch_ranges): Same. * gimple-range-edge.h (gimple_outgoing_range): Same. * gimple-range-infer.cc (infer_range_manager::get_nonzero): Same. (infer_range_manager::add_range): Same. * gimple-range-infer.h (class infer_range_manager): Same. * value-range.h (class irange_allocator): Rename to... (class vrange_allocator): ...this. (irange_allocator::irange_allocator): New. (vrange_allocator::vrange_allocator): New. (irange_allocator::~irange_allocator): New. (vrange_allocator::~vrange_allocator): New. (irange_allocator::get_memory): Rename to... (vrange_allocator::alloc): ...this. (vrange_allocator::alloc_vrange): Rename from... (irange_allocator::allocate): ...this. (vrange_allocator::alloc_irange): New.
2022-05-25Tweak comments.Andrew MacLeod1-1/+1
Adjust some mispellings in comments. * gimple-range-cache.cc: Adjust comments. * gimple-range-infer.cc: Adjust comments. * gimple-range-infer.h: Adjust comments. * gimple-range.cc: Adjust comments.
2022-05-25Use infer instead of side-effect for ranges.Andrew MacLeod1-16/+16
Rename the files and classes to reflect the term infer rather than side-effect. * Makefile.in (OBJS): Use gimple-range-infer.o. * gimple-range-cache.cc (ranger_cache::fill_block_cache): Change msg. (ranger_cache::range_from_dom): Rename var side_effect to infer. (ranger_cache::apply_inferred_ranges): Rename from apply_side_effects. * gimple-range-cache.h: Include gimple-range-infer.h. (class ranger_cache): Adjust prototypes, use infer_range_manager. * gimple-range-infer.cc: Rename from gimple-range-side-effects.cc. (gimple_infer_range::*): Rename from stmt_side_effects. (infer_range_manager::*): Rename from side_effect_manager. * gimple-range-side-effect.cc: Rename. * gimple-range-side-effect.h: Rename. * gimple-range-infer.h: Rename from gimple-range-side-effects.h. (class gimple_infer_range): Rename from stmt_side_effects. (class infer_range_manager): Rename from side_effect_manager. * gimple-range.cc (gimple_ranger::register_inferred_ranges): Rename from register_side_effects. * gimple-range.h (register_inferred_ranges): Adjust prototype. * range-op.h: Adjust comment. * tree-vrp.cc (rvrp_folder::pre_fold_bb): Use register_inferred_ranges. (rvrp_folder::post_fold_bb): Use register_inferred_ranges.
2022-05-20Use "final" and "override" directly, rather than via macrosDavid Malcolm1-6/+6
As of GCC 11 onwards we have required a C++11 compiler, such as GCC 4.8 or later. On the assumption that any such compiler correctly implements "final" and "override", this patch updates the source tree to stop using the FINAL and OVERRIDE macros from ansidecl.h, in favor of simply using "final" and "override" directly. libcpp/ChangeLog: * lex.cc: Replace uses of "FINAL" and "OVERRIDE" with "final" and "override". gcc/analyzer/ChangeLog: * analyzer-pass.cc: Replace uses of "FINAL" and "OVERRIDE" with "final" and "override". * call-info.h: Likewise. * checker-path.h: Likewise. * constraint-manager.cc: Likewise. * diagnostic-manager.cc: Likewise. * engine.cc: Likewise. * exploded-graph.h: Likewise. * feasible-graph.h: Likewise. * pending-diagnostic.h: Likewise. * region-model-impl-calls.cc: Likewise. * region-model.cc: Likewise. * region-model.h: Likewise. * region.h: Likewise. * sm-file.cc: Likewise. * sm-malloc.cc: Likewise. * sm-pattern-test.cc: Likewise. * sm-sensitive.cc: Likewise. * sm-signal.cc: Likewise. * sm-taint.cc: Likewise. * state-purge.h: Likewise. * store.cc: Likewise. * store.h: Likewise. * supergraph.h: Likewise. * svalue.h: Likewise. * trimmed-graph.h: Likewise. * varargs.cc: Likewise. gcc/c-family/ChangeLog: * c-format.cc: Replace uses of "FINAL" and "OVERRIDE" with "final" and "override". * c-pretty-print.h: Likewise. gcc/cp/ChangeLog: * cxx-pretty-print.h: Replace uses of "FINAL" and "OVERRIDE" with "final" and "override". * error.cc: Likewise. gcc/jit/ChangeLog: * jit-playback.h: Replace uses of "FINAL" and "OVERRIDE" with "final" and "override". * jit-recording.cc: Likewise. * jit-recording.h: Likewise. gcc/ChangeLog: * config/aarch64/aarch64-sve-builtins-base.cc: Replace uses of "FINAL" and "OVERRIDE" with "final" and "override". * config/aarch64/aarch64-sve-builtins-functions.h: Likewise. * config/aarch64/aarch64-sve-builtins-shapes.cc: Likewise. * config/aarch64/aarch64-sve-builtins-sve2.cc: Likewise. * diagnostic-path.h: Likewise. * digraph.cc: Likewise. * gcc-rich-location.h: Likewise. * gimple-array-bounds.cc: Likewise. * gimple-loop-versioning.cc: Likewise. * gimple-range-cache.cc: Likewise. * gimple-range-cache.h: Likewise. * gimple-range-fold.cc: Likewise. * gimple-range-fold.h: Likewise. * gimple-range-tests.cc: Likewise. * gimple-range.h: Likewise. * gimple-ssa-evrp.cc: Likewise. * input.cc: Likewise. * json.h: Likewise. * read-rtl-function.cc: Likewise. * tree-complex.cc: Likewise. * tree-diagnostic-path.cc: Likewise. * tree-ssa-ccp.cc: Likewise. * tree-ssa-copy.cc: Likewise. * tree-vrp.cc: Likewise. * value-query.h: Likewise. * vr-values.h: Likewise. Signed-off-by: David Malcolm <dmalcolm@redhat.com>
2022-05-17Add side effect infrastructure.Andrew MacLeod1-204/+46
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.
2022-05-13Fix return value in ranger_cache::get_global_range.Andrew MacLeod1-1/+1
The "is_current" status is returned by parameter, but was being returned by the function as well instead of true if NAME had a global range, and FALSE if it did not. * gimple-range-cache.cc (ranger_cache::get_global_range): Return the had_global value instead.
2022-05-13Make range_from_dom more effective.Andrew MacLeod1-47/+88
Add modes to range_from_dom such that we can simply query, or adjust the cache and deal with multiple predecessor blocks. * gimple-range-cache.cc (ranger_cache::ranger_cache): Start with worlist truncated. (ranger_cache::entry_range): Add rfd_mode parameter. (ranger_cache::exit_range): Ditto. (ranger_cache::edge_range): New. Incorporate from range_on_edge. (ranger_cache::range_of_expr): Adjust call to entry_range. (ranger_cache::range_on_edge): Split to edge_range and call. (ranger_cache::fill_block_cache): Always invoke range_from_dom. (ranger_cache::range_from_dom): Make reentrant, add search mode, handle mutiple predecessors. (ranger_cache::update_to_nonnull): Adjust call to exit_range. * gimple-range-cache.h (ranger_cache): Add enum rfd_mode. Adjust prototypes.
2022-03-17Always use dominators in the cache when available.Andrew MacLeod1-28/+75
This patch adjusts range_from_dom to follow the dominator tree through the cache until value is found, then apply any outgoing ranges encountered along the way. This reduces the amount of cache storage required. PR tree-optimization/102943 * gimple-range-cache.cc (ranger_cache::range_from_dom): Find range via dominators and apply intermediary outgoing edge ranges.
2022-03-10tree-optimization/102943 - use tree form for sbr_sparse_bitmapRichard Biener1-7/+8
The following arranges to remove an indirection do the bitvector in sbr_sparse_bitmap by embedding bitmap_head instead of bitmap and using the tree form (since we only ever set/query individual aligned bit chunks). That shaves off 6 seconds from 70 seconds of the slowest 521.wrf_r LRANS unit build. 2022-03-10 Richard Biener <rguenther@suse.de> PR tree-optimization/102943 * gimple-range-cache.cc (sbr_sparse_bitmap::bitvec): Make a bitmap_head. (sbr_sparse_bitmap::sbr_sparse_bitmap): Adjust and switch to tree view. (sbr_sparse_bitmap::set_bb_range): Adjust. (sbr_sparse_bitmap::get_bb_range): Likewise.
2022-02-09Register non-null side effects properly.Andrew MacLeod1-34/+101
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.
2022-01-03Update copyright years.Jakub Jelinek1-1/+1
2021-12-06Use dominators to reduce cache-flling.Andrew MacLeod1-0/+73
Before walking the CFG and filling all cache entries, check if the same information is available in a dominator. * gimple-range-cache.cc (ranger_cache::fill_block_cache): Check for a range from dominators before filling the cache. (ranger_cache::range_from_dom): New. * gimple-range-cache.h (ranger_cache::range_from_dom): Add prototype.
generated by cgit v1.1 at 2025-08-07 09:27:54 +0000