From b7501739f3b14ac7749aace93f636d021fd607f7 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Mon, 9 May 2022 15:35:14 -0400 Subject: [PATCH] Add side effect infrastructure. 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. --- gcc/Makefile.in | 1 + gcc/gimple-range-cache.cc | 250 ++++++-------------------------- gcc/gimple-range-cache.h | 58 +------- gcc/gimple-range-path.cc | 6 +- gcc/gimple-range-path.h | 1 - gcc/gimple-range-side-effect.cc | 310 ++++++++++++++++++++++++++++++++++++++++ gcc/gimple-range-side-effect.h | 82 +++++++++++ gcc/gimple-range.cc | 27 ++-- gcc/gimple-range.h | 9 +- gcc/tree-vrp.cc | 2 +- 10 files changed, 464 insertions(+), 282 deletions(-) create mode 100644 gcc/gimple-range-side-effect.cc create mode 100644 gcc/gimple-range-side-effect.h diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 70f7d21..97e5450 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1410,6 +1410,7 @@ OBJS = \ gimple-range-edge.o \ gimple-range-fold.o \ gimple-range-gori.o \ + gimple-range-side-effect.o \ gimple-range-trace.o \ gimple-ssa-backprop.o \ gimple-ssa-evrp.o \ diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index d3cf8be..56f4577 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -38,120 +38,6 @@ along with GCC; see the file COPYING3. If not see #define DEBUG_RANGE_CACHE (dump_file \ && (param_ranger_debug & RANGER_DEBUG_CACHE)) -// During contructor, allocate the vector of ssa_names. - -non_null_ref::non_null_ref () -{ - m_nn.create (num_ssa_names); - m_nn.quick_grow_cleared (num_ssa_names); - bitmap_obstack_initialize (&m_bitmaps); -} - -// Free any bitmaps which were allocated,a swell as the vector itself. - -non_null_ref::~non_null_ref () -{ - bitmap_obstack_release (&m_bitmaps); - m_nn.release (); -} - -// This routine will update NAME in BB to be nonnull if it is not already. -// return TRUE if the update happens. - -bool -non_null_ref::set_nonnull (basic_block bb, tree name) -{ - gcc_checking_assert (gimple_range_ssa_p (name) - && POINTER_TYPE_P (TREE_TYPE (name))); - // Only process when its not already set. - if (non_null_deref_p (name, bb, false)) - return false; - bitmap_set_bit (m_nn[SSA_NAME_VERSION (name)], bb->index); - return true; -} - -// Return true if NAME has a non-null dereference in block bb. If this is the -// first query for NAME, calculate the summary first. -// If SEARCH_DOM is true, the search the dominator tree as well. - -bool -non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom) -{ - if (!POINTER_TYPE_P (TREE_TYPE (name))) - return false; - - unsigned v = SSA_NAME_VERSION (name); - if (v >= m_nn.length ()) - m_nn.safe_grow_cleared (num_ssa_names + 1); - - if (!m_nn[v]) - process_name (name); - - if (bitmap_bit_p (m_nn[v], bb->index)) - return true; - - // See if any dominator has set non-zero. - if (search_dom && dom_info_available_p (CDI_DOMINATORS)) - { - // Search back to the Def block, or the top, whichever is closer. - basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name)); - basic_block def_dom = def_bb - ? get_immediate_dominator (CDI_DOMINATORS, def_bb) - : NULL; - for ( ; - bb && bb != def_dom; - bb = get_immediate_dominator (CDI_DOMINATORS, bb)) - if (bitmap_bit_p (m_nn[v], bb->index)) - return true; - } - return false; -} - -// Allocate an populate the bitmap for NAME. An ON bit for a block -// index indicates there is a non-null reference in that block. In -// order to populate the bitmap, a quick run of all the immediate uses -// are made and the statement checked to see if a non-null dereference -// is made on that statement. - -void -non_null_ref::process_name (tree name) -{ - unsigned v = SSA_NAME_VERSION (name); - use_operand_p use_p; - imm_use_iterator iter; - bitmap b; - - // Only tracked for pointers. - if (!POINTER_TYPE_P (TREE_TYPE (name))) - return; - - // Already processed if a bitmap has been allocated. - if (m_nn[v]) - return; - - b = BITMAP_ALLOC (&m_bitmaps); - - // Loop over each immediate use and see if it implies a non-null value. - FOR_EACH_IMM_USE_FAST (use_p, iter, name) - { - gimple *s = USE_STMT (use_p); - unsigned index = gimple_bb (s)->index; - - // If bit is already set for this block, dont bother looking again. - if (bitmap_bit_p (b, index)) - continue; - - // If we can infer a nonnull range, then set the bit for this BB - if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name) - && infer_nonnull_range (s, name)) - bitmap_set_bit (b, index); - } - - m_nn[v] = b; -} - -// ------------------------------------------------------------------------- - // This class represents the API into a cache of ranges for an SSA_NAME. // Routines must be implemented to set, get, and query if a value is set. @@ -859,8 +745,9 @@ update_list::pop () // -------------------------------------------------------------------------- -ranger_cache::ranger_cache (int not_executable_flag) - : m_gori (not_executable_flag) +ranger_cache::ranger_cache (int not_executable_flag, bool use_imm_uses) + : m_gori (not_executable_flag), + m_exit (use_imm_uses) { m_workback.create (0); m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun)); @@ -1057,9 +944,9 @@ bool ranger_cache::edge_range (irange &r, edge e, tree name, enum rfd_mode mode) { exit_range (r, name, e->src, mode); - // If this is not an abnormal edge, check for a non-null exit. + // If this is not an abnormal edge, check for side effects on exit. if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0) - m_non_null.adjust_range (r, name, e->src, false); + m_exit.maybe_adjust_range (r, name, e->src); int_range_max er; if (m_gori.outgoing_edge_range_p (er, e, name, *this)) r.intersect (er); @@ -1364,12 +1251,12 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) } // Regardless of whether we have visited pred or not, if the - // pred has a non-null reference, revisit this block. + // pred has side_effects, revisit this block. // Don't search the DOM tree. - if (m_non_null.non_null_deref_p (name, pred, false)) + if (m_exit.has_range_p (name, pred)) { if (DEBUG_RANGE_CACHE) - fprintf (dump_file, "nonnull: update "); + fprintf (dump_file, "side effect: update "); m_update->add (node); } @@ -1429,8 +1316,9 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb, basic_block bb; basic_block prev_bb = start_bb; - // Flag if we encounter a block with non-null set. - bool non_null = false; + + // Track any side effects seen + int_range_max side_effect (TREE_TYPE (name)); // Range on entry to the DEF block should not be queried. gcc_checking_assert (start_bb != def_bb); @@ -1444,8 +1332,8 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb, bb; prev_bb = bb, bb = get_immediate_dominator (CDI_DOMINATORS, bb)) { - if (!non_null) - non_null |= m_non_null.non_null_deref_p (name, bb, false); + // Accumulate any block exit side effects. + m_exit.maybe_adjust_range (side_effect, name, bb); // This block has an outgoing range. if (m_gori.has_edge_range_p (name, bb)) @@ -1511,14 +1399,10 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb, if (m_gori.outgoing_edge_range_p (er, e, name, *this)) { r.intersect (er); - if (r.varying_p () && ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)) - { - if (m_non_null.non_null_deref_p (name, bb, false)) - { - gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name))); - r.set_nonzero (TREE_TYPE (name)); - } - } + // If this is a normal edge, apply any side effects. + if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0) + m_exit.maybe_adjust_range (r, name, bb); + if (DEBUG_RANGE_CACHE) { fprintf (dump_file, "CACHE: Adjusted edge range for %d->%d : ", @@ -1530,12 +1414,9 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb, } // Apply non-null if appropriate. - if (non_null && r.varying_p () - && !has_abnormal_call_or_eh_pred_edge_p (start_bb)) - { - gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name))); - r.set_nonzero (TREE_TYPE (name)); - } + if (!has_abnormal_call_or_eh_pred_edge_p (start_bb)) + r.intersect (side_effect); + if (DEBUG_RANGE_CACHE) { fprintf (dump_file, "CACHE: Range for DOM returns : "); @@ -1545,81 +1426,42 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb, return true; } -// This routine will update NAME in block BB to the nonnull state. -// It will then update the on-entry cache for this block to be non-null -// if it isn't already. +// This routine is used during a block walk to move the state of non-null for +// any operands on stmt S to nonnull. void -ranger_cache::update_to_nonnull (basic_block bb, tree name) +ranger_cache::apply_side_effects (gimple *s) { - tree type = TREE_TYPE (name); - if (gimple_range_ssa_p (name) && POINTER_TYPE_P (type)) - { - m_non_null.set_nonnull (bb, name); - // Update the on-entry cache for BB to be non-zero. Note this can set - // the on entry value in the DEF block, which can override the def. - int_range_max r; - exit_range (r, name, bb, RFD_READ_ONLY); - if (r.varying_p ()) - { - r.set_nonzero (type); - m_on_entry.set_bb_range (name, bb, r); - } - } -} + int_range_max r; + bool update = true; -// Adapted from infer_nonnull_range_by_dereference and check_loadstore -// to process nonnull ssa_name OP in S. DATA contains the ranger_cache. + basic_block bb = gimple_bb (s); + stmt_side_effects se(s); + if (se.num () == 0) + return; -static bool -non_null_loadstore (gimple *s, tree op, tree, void *data) -{ - if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF) + // Do not update the on-netry cache for block ending stmts. + if (stmt_ends_bb_p (s)) { - /* Some address spaces may legitimately dereference zero. */ - addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op)); - if (!targetm.addr_space.zero_address_valid (as)) - { - tree ssa = TREE_OPERAND (op, 0); - basic_block bb = gimple_bb (s); - ((ranger_cache *)data)->update_to_nonnull (bb, ssa); - } + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, gimple_bb (s)->succs) + if (!(e->flags & (EDGE_ABNORMAL|EDGE_EH))) + break; + if (e == NULL) + update = false; } - return false; -} - -// This routine is used during a block walk to move the state of non-null for -// any operands on stmt S to nonnull. -void -ranger_cache::block_apply_nonnull (gimple *s) -{ - if (!flag_delete_null_pointer_checks) - return; - if (is_a (s)) - return; - if (gimple_code (s) == GIMPLE_ASM || gimple_clobber_p (s)) - return; - if (is_a (s)) + for (unsigned x = 0; x < se.num (); x++) { - tree fntype = gimple_call_fntype (s); - bitmap nonnullargs = get_nonnull_args (fntype); - // Process any non-null arguments - if (nonnullargs) + tree name = se.name (x); + m_exit.add_range (name, bb, se.range (x)); + if (update) { - basic_block bb = gimple_bb (s); - for (unsigned i = 0; i < gimple_call_num_args (s); i++) - { - if (bitmap_empty_p (nonnullargs) || bitmap_bit_p (nonnullargs, i)) - { - tree op = gimple_call_arg (s, i); - update_to_nonnull (bb, op); - } - } - BITMAP_FREE (nonnullargs); + if (!m_on_entry.get_bb_range (r, name, bb)) + exit_range (r, name, bb, RFD_READ_ONLY); + if (r.intersect (se.range (x))) + m_on_entry.set_bb_range (name, bb, r); } - // Fallthru and walk load/store ops now. } - walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore, - non_null_loadstore); } diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 560403b..42aa41b 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -22,56 +22,7 @@ along with GCC; see the file COPYING3. If not see #define GCC_SSA_RANGE_CACHE_H #include "gimple-range-gori.h" - -// Class used to track non-null references of an SSA name. A vector -// of bitmaps indexed by SSA name is maintained. When indexed by -// basic block, an on-bit indicates there is a non-null dereference -// for that SSA in that block. - -class non_null_ref -{ -public: - non_null_ref (); - ~non_null_ref (); - bool non_null_deref_p (tree name, basic_block bb, bool search_dom = true); - bool adjust_range (irange &r, tree name, basic_block bb, - bool search_dom = true); - bool set_nonnull (basic_block bb, tree name); -private: - vec m_nn; - void process_name (tree name); - bitmap_obstack m_bitmaps; -}; - -// If NAME has a non-null dereference in block BB, adjust R with the -// non-zero information from non_null_deref_p, and return TRUE. If -// SEARCH_DOM is true, non_null_deref_p should search the dominator tree. - -inline bool -non_null_ref::adjust_range (irange &r, tree name, basic_block bb, - bool search_dom) -{ - // Non-call exceptions mean we could throw in the middle of the - // block, so just punt on those for now. - if (cfun->can_throw_non_call_exceptions) - return false; - // We only care about the null / non-null property of pointers. - if (!POINTER_TYPE_P (TREE_TYPE (name))) - return false; - if (r.undefined_p () || r.lower_bound () != 0 || r.upper_bound () == 0) - return false; - // Check if pointers have any non-null dereferences. - if (non_null_deref_p (name, bb, search_dom)) - { - // Remove zero from the range. - gcc_checking_assert (TYPE_UNSIGNED (TREE_TYPE (name))); - int_range<2> nz; - nz.set_nonzero (TREE_TYPE (name)); - r.intersect (nz); - return true; - } - return false; -} +#include "gimple-range-side-effect.h" // This class manages a vector of pointers to ssa_block ranges. It // provides the basis for the "range on entry" cache for all @@ -123,7 +74,7 @@ private: class ranger_cache : public range_query { public: - ranger_cache (int not_executable_flag); + ranger_cache (int not_executable_flag, bool use_imm_uses); ~ranger_cache (); virtual bool range_of_expr (irange &r, tree name, gimple *stmt); @@ -136,10 +87,9 @@ public: void propagate_updated_value (tree name, basic_block bb); - void block_apply_nonnull (gimple *s); - void update_to_nonnull (basic_block bb, tree name); - non_null_ref m_non_null; + void apply_side_effects (gimple *s); gori_compute m_gori; + side_effect_manager m_exit; void dump_bb (FILE *f, basic_block bb); virtual void dump (FILE *f) OVERRIDE; diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index ff39833..459d379 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -357,8 +357,8 @@ path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb) r.set_varying (TREE_TYPE (name)); } - if (bb) - m_non_null.adjust_range (r, name, bb, false); + if (bb && POINTER_TYPE_P (TREE_TYPE (name))) + m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); if (DEBUG_SOLVER && (bb || !r.varying_p ())) { @@ -528,7 +528,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) else r.set_varying (TREE_TYPE (name)); - if (m_non_null.adjust_range (r, name, bb, false)) + if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) set_cache (r, name); } } diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index 1820626..914983b 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -91,7 +91,6 @@ private: auto_bitmap m_imports; gimple_ranger *m_ranger; - non_null_ref m_non_null; // Current path position. unsigned m_pos; diff --git a/gcc/gimple-range-side-effect.cc b/gcc/gimple-range-side-effect.cc new file mode 100644 index 0000000..2c8c77d --- /dev/null +++ b/gcc/gimple-range-side-effect.cc @@ -0,0 +1,310 @@ +/* Gimple range side effect implementation. + Copyright (C) 2022 Free Software Foundation, Inc. + Contributed by Andrew MacLeod . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "insn-codes.h" +#include "tree.h" +#include "gimple.h" +#include "ssa.h" +#include "gimple-pretty-print.h" +#include "gimple-range.h" +#include "tree-cfg.h" +#include "target.h" +#include "attribs.h" +#include "gimple-iterator.h" +#include "gimple-walk.h" +#include "cfganal.h" + +// Adapted from infer_nonnull_range_by_dereference and check_loadstore +// to process nonnull ssa_name OP in S. DATA contains a pointer to a +// stmt side effects instance. + +static bool +non_null_loadstore (gimple *, tree op, tree, void *data) +{ + if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF) + { + /* Some address spaces may legitimately dereference zero. */ + addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op)); + if (!targetm.addr_space.zero_address_valid (as)) + { + tree ssa = TREE_OPERAND (op, 0); + ((stmt_side_effects *)data)->add_nonzero (ssa); + } + } + return false; +} + +// Add NAME and RANGE to the the side effect summary. + +void +stmt_side_effects::add_range (tree name, irange &range) +{ + m_names[num_args] = name; + m_ranges[num_args] = range; + if (num_args < size_limit - 1) + num_args++; +} + +// Add a nonzero range for NAME to the side effect summary. + +void +stmt_side_effects::add_nonzero (tree name) +{ + if (!gimple_range_ssa_p (name)) + return; + int_range<2> nz; + nz.set_nonzero (TREE_TYPE (name)); + add_range (name, nz); +} + +// Process S for side effects and fill in the summary list. +// This is the routine where new side effects should be added. + +stmt_side_effects::stmt_side_effects (gimple *s) +{ + num_args = 0; + + if (is_a (s)) + return; + + if (is_a (s) && flag_delete_null_pointer_checks) + { + tree fntype = gimple_call_fntype (s); + bitmap nonnullargs = get_nonnull_args (fntype); + // Process any non-null arguments + if (nonnullargs) + { + for (unsigned i = 0; i < gimple_call_num_args (s); i++) + { + if (bitmap_empty_p (nonnullargs) + || bitmap_bit_p (nonnullargs, i)) + { + tree op = gimple_call_arg (s, i); + if (POINTER_TYPE_P (TREE_TYPE (op))) + add_nonzero (op); + } + } + BITMAP_FREE (nonnullargs); + } + // Fallthru and walk load/store ops now. + } + + // Look for possible non-null values. + if (flag_delete_null_pointer_checks && gimple_code (s) != GIMPLE_ASM + && !gimple_clobber_p (s)) + walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore, + non_null_loadstore); + +} + +// ------------------------------------------------------------------------- + +// This class is an element in list of side effect ranges. + +class exit_range +{ +public: + tree name; + irange *range; + exit_range *next; +}; + +// If there is an element which matches SSA, return a pointer to the element. +// Otherwise return NULL. + +exit_range * +side_effect_manager::exit_range_head::find_ptr (tree ssa) +{ + // Return NULL if SSA is not in this list. + if (!m_names || !bitmap_bit_p (m_names, SSA_NAME_VERSION (ssa))) + return NULL; + for (exit_range *ptr = head; ptr != NULL; ptr = ptr->next) + if (ptr->name == ssa) + return ptr; + // Should be unreachable. + gcc_unreachable (); + return NULL; +} + +// Construct a side effects manager. DO_SEARCH indicates whether an immediate +// use scan should be made the first time a name is processed. This is for +// on-demand clients who may not visit every statement and may miss uses. + +side_effect_manager::side_effect_manager (bool do_search) +{ + bitmap_obstack_initialize (&m_bitmaps); + m_on_exit.create (0); + m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); + // m_seen == NULL indicates no scanning. Otherwise the bit indicates a + // scan has been performed on NAME. + if (do_search) + m_seen = BITMAP_ALLOC (&m_bitmaps); + else + m_seen = NULL; + obstack_init (&m_list_obstack); + // Non-zero elements are very common, so cache them for each ssa-name. + m_nonzero.create (0); + m_nonzero.safe_grow_cleared (num_ssa_names + 1); +} + +// Destruct a side effects manager. + +side_effect_manager::~side_effect_manager () +{ + m_nonzero.release (); + obstack_free (&m_list_obstack, NULL); + m_on_exit.release (); + bitmap_obstack_release (&m_bitmaps); +} + +// Return a non-zero range value of the appropriate type for NAME from +// the cache, creating it if necessary. + +const irange& +side_effect_manager::get_nonzero (tree name) +{ + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_nonzero.length ()) + m_nonzero.safe_grow_cleared (num_ssa_names + 20); + if (!m_nonzero[v]) + { + m_nonzero[v] = m_range_allocator.allocate (2); + m_nonzero[v]->set_nonzero (TREE_TYPE (name)); + } + return *(m_nonzero[v]); +} + +// Return TRUE if NAME has a side effect range in block BB. + +bool +side_effect_manager::has_range_p (tree name, basic_block bb) +{ + // Check if this is an immediate use search model. + if (m_seen && !bitmap_bit_p (m_seen, SSA_NAME_VERSION (name))) + register_all_uses (name); + + if (bb->index >= (int)m_on_exit.length ()) + return false; + if (!m_on_exit[bb->index].m_names) + return false; + if (!bitmap_bit_p (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name))) + return false; + return true; +} + +// Return TRUE if NAME has a side effect range in block BB, and adjust range R +// to include it. + +bool +side_effect_manager::maybe_adjust_range (irange &r, tree name, basic_block bb) +{ + if (!has_range_p (name, bb)) + return false; + exit_range *ptr = m_on_exit[bb->index].find_ptr (name); + gcc_checking_assert (ptr); + // Return true if this exit range changes R, otherwise false. + return r.intersect (*(ptr->range)); +} + +// Add range R as a side effect for NAME in block BB. + +void +side_effect_manager::add_range (tree name, basic_block bb, const irange &r) +{ + if (bb->index >= (int)m_on_exit.length ()) + m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); + + // Create the summary list bitmap if it doesn't exist. + if (!m_on_exit[bb->index].m_names) + m_on_exit[bb->index].m_names = BITMAP_ALLOC (&m_bitmaps); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " on-exit update "); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " in BB%d : ",bb->index); + r.dump (dump_file); + fprintf (dump_file, "\n"); + } + + // If NAME already has a range, intersect them and done. + exit_range *ptr = m_on_exit[bb->index].find_ptr (name); + if (ptr) + { + int_range_max cur = r; + // If no new info is added, just return. + if (!cur.intersect (*(ptr->range))) + return; + if (ptr->range->fits_p (cur)) + *(ptr->range) = cur; + else + ptr->range = m_range_allocator.allocate (cur); + return; + } + + // Otherwise create a record. + bitmap_set_bit (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name)); + ptr = (exit_range *)obstack_alloc (&m_list_obstack, sizeof (exit_range)); + ptr->range = m_range_allocator.allocate (r); + ptr->name = name; + ptr->next = m_on_exit[bb->index].head; + m_on_exit[bb->index].head = ptr; +} + +// Add a non-zero side effect for NAME in block BB. + +void +side_effect_manager::add_nonzero (tree name, basic_block bb) +{ + add_range (name, bb, get_nonzero (name)); +} + +// Follow immediate use chains and find all side effects for NAME. + +void +side_effect_manager::register_all_uses (tree name) +{ + gcc_checking_assert (m_seen); + + // Check if we've already processed this name. + unsigned v = SSA_NAME_VERSION (name); + if (bitmap_bit_p (m_seen, v)) + return; + bitmap_set_bit (m_seen, v); + + use_operand_p use_p; + imm_use_iterator iter; + + // Loop over each immediate use and see if it has a side effect. + FOR_EACH_IMM_USE_FAST (use_p, iter, name) + { + gimple *s = USE_STMT (use_p); + stmt_side_effects se (s); + for (unsigned x = 0; x < se.num (); x++) + { + if (name == se.name (x)) + add_range (name, gimple_bb (s), se.range (x)); + } + } +} diff --git a/gcc/gimple-range-side-effect.h b/gcc/gimple-range-side-effect.h new file mode 100644 index 0000000..848d94b --- /dev/null +++ b/gcc/gimple-range-side-effect.h @@ -0,0 +1,82 @@ +/* Header file for gimple range side effects. + Copyright (C) 2022 Free Software Foundation, Inc. + Contributed by Andrew MacLeod . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_GIMPLE_RANGE_SIDE_H +#define GCC_GIMPLE_RANGE_SIDE_H + +// This class manages an on-demand summary of side effects for a statement. +// It can be instantiated as required and provides a list of side effects. + +// New side effects should added in the constructor of this class. + +class stmt_side_effects +{ +public: + stmt_side_effects (gimple *s); + inline unsigned num () const { return num_args; } + inline tree name (unsigned index) const + { gcc_checking_assert (index < num_args); return m_names[index]; } + inline const irange& range (unsigned index) const + { gcc_checking_assert (index < num_args); return m_ranges[index]; } + void add_range (tree name, irange &range); + void add_nonzero (tree name); +private: + unsigned num_args; + static const int size_limit = 10; + tree m_names[size_limit]; + int_range<3> m_ranges[size_limit]; + inline void bump_index () { if (num_args < size_limit - 1) num_args++; } +}; + +// This class manages a list of side effect ranges for each basic block. +// As side effects are seen, they can be registered to a block and later +// queried. WHen constructed with a TRUE flag, immediate uses chains are +// followed the first time a name is referenced and block populated if +// thre are any side effects. + +class side_effect_manager +{ +public: + side_effect_manager (bool do_search); + ~side_effect_manager (); + void add_range (tree name, basic_block bb, const irange &r); + void add_nonzero (tree name, basic_block bb); + bool has_range_p (tree name, basic_block bb); + bool maybe_adjust_range (irange &r, tree name, basic_block bb); +private: + class exit_range_head + { + public: + bitmap m_names; // list of names with an outgoing range. + class exit_range *head; + int m_num_ranges; + exit_range *find_ptr (tree name); + }; + void register_all_uses (tree name); + vec m_on_exit; + const irange &get_nonzero (tree name); + vec m_nonzero; + bitmap m_seen; + bitmap_obstack m_bitmaps; + struct obstack m_list_obstack; + irange_allocator m_range_allocator; +}; + +#endif // GCC_GIMPLE_RANGE_SIDE_H diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 1fdee02..f5e9e77 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -37,9 +37,9 @@ along with GCC; see the file COPYING3. If not see #include "gimple-fold.h" #include "gimple-walk.h" -gimple_ranger::gimple_ranger () : +gimple_ranger::gimple_ranger (bool use_imm_uses) : non_executable_edge_flag (cfun), - m_cache (non_executable_edge_flag), + m_cache (non_executable_edge_flag, use_imm_uses), tracer (""), current_bb (NULL) { @@ -118,9 +118,11 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) // If name is defined in this block, try to get an range from S. if (def_stmt && gimple_bb (def_stmt) == bb) { - // Check for a definition override from a block walk. - if (!POINTER_TYPE_P (TREE_TYPE (expr)) - || !m_cache.block_range (r, bb, expr, false)) + // Declared in ths block, if it has a global set, check for an + // override from a block walk, otherwise calculate it. + if (m_cache.get_global_range (r, expr)) + m_cache.block_range (r, bb, expr, false); + else range_of_stmt (r, def_stmt, expr); } // Otherwise OP comes from outside this block, use range on entry. @@ -154,13 +156,6 @@ gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name) if (m_cache.block_range (entry_range, bb, name)) r.intersect (entry_range); - if (dom_info_available_p (CDI_DOMINATORS)) - { - basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); - if (dom_bb) - m_cache.m_non_null.adjust_range (r, name, dom_bb, true); - } - if (idx) tracer.trailer (idx, "range_on_entry", true, name, r); } @@ -237,7 +232,7 @@ gimple_ranger::range_on_edge (irange &r, edge e, tree name) range_on_exit (r, e->src, name); // If this is not an abnormal edge, check for a non-null exit . if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0) - m_cache.m_non_null.adjust_range (r, name, e->src, false); + m_cache.m_exit.maybe_adjust_range (r, name, e->src); gcc_checking_assert (r.undefined_p () || range_compatible_p (r.type(), TREE_TYPE (name))); @@ -480,7 +475,7 @@ gimple_ranger::register_side_effects (gimple *s) fputc ('\n', dump_file); } } - m_cache.block_apply_nonnull (s); + m_cache.apply_side_effects (s); } // This routine will export whatever global ranges are known to GCC @@ -625,12 +620,12 @@ gimple_ranger::debug () resources. */ gimple_ranger * -enable_ranger (struct function *fun) +enable_ranger (struct function *fun, bool use_imm_uses) { gimple_ranger *r; gcc_checking_assert (!fun->x_range_query); - r = new gimple_ranger; + r = new gimple_ranger (use_imm_uses); fun->x_range_query = r; return r; diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index 0733a53..ae6c402 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -46,7 +46,7 @@ along with GCC; see the file COPYING3. If not see class gimple_ranger : public range_query { public: - gimple_ranger (); + gimple_ranger (bool use_imm_uses = true); ~gimple_ranger (); virtual bool range_of_stmt (irange &r, gimple *, tree name = NULL) OVERRIDE; virtual bool range_of_expr (irange &r, tree name, gimple * = NULL) OVERRIDE; @@ -69,12 +69,15 @@ protected: range_tracer tracer; basic_block current_bb; vec m_stmt_list; + friend class path_range_query; }; /* Create a new ranger instance and associate it with a function. Each call must be paired with a call to disable_ranger to release - resources. */ -extern gimple_ranger *enable_ranger (struct function *); + resources. If USE_IMM_USES is true, pre-calculate sideffects like + non-null uses as required using the immediate use chains. */ +extern gimple_ranger *enable_ranger (struct function *m, + bool use_imm_uses = true); extern void disable_ranger (struct function *); #endif // GCC_GIMPLE_RANGE_H diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc index 8ba9ca7..77c1912 100644 --- a/gcc/tree-vrp.cc +++ b/gcc/tree-vrp.cc @@ -4345,7 +4345,7 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p) calculate_dominance_info (CDI_DOMINATORS); set_all_edges_as_executable (fun); - gimple_ranger *ranger = enable_ranger (fun); + gimple_ranger *ranger = enable_ranger (fun, false); rvrp_folder folder (ranger); folder.substitute_and_fold (); if (dump_file && (dump_flags & TDF_DETAILS)) -- 2.7.4