commit b7501739f3b14ac7749aace93f636d021fd607f7
Author: Andrew MacLeod <amacleod@redhat.com>
Date: Mon May 9 15:35:14 2022 -0400
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.
@@ -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 \
@@ -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<gphi *> (s))
- return;
- if (gimple_code (s) == GIMPLE_ASM || gimple_clobber_p (s))
- return;
- if (is_a<gcall *> (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);
}
@@ -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 <bitmap> 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;
@@ -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);
}
}
@@ -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;
new file mode 100644
@@ -0,0 +1,310 @@
+/* Gimple range side effect implementation.
+ Copyright (C) 2022 Free Software Foundation, Inc.
+ Contributed by Andrew MacLeod <amacleod@redhat.com>.
+
+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
+<http://www.gnu.org/licenses/>. */
+
+#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<gphi *> (s))
+ return;
+
+ if (is_a<gcall *> (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));
+ }
+ }
+}
new file mode 100644
@@ -0,0 +1,82 @@
+/* Header file for gimple range side effects.
+ Copyright (C) 2022 Free Software Foundation, Inc.
+ Contributed by Andrew MacLeod <amacleod@redhat.com>.
+
+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
+<http://www.gnu.org/licenses/>. */
+
+#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 <exit_range_head> m_on_exit;
+ const irange &get_nonzero (tree name);
+ vec <irange *> 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
@@ -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;
@@ -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<tree> 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
@@ -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))
This patch replaces the old non-null processing mechanism in ranger with generic side-effect processing. The way it use to work: - The first time a query for non-nullness was made on an ssa-name, a quick pass over the immediate use lists was made. - This checked each use for triggering the non-null property, and if it did, a but was set in a sparse bitmap for that block. - This was considered to be true on exit from the block, so whenever a query for a range crossed a block boundry, the ~[0,0] range was applied to the current range as appropriate. How it works now. - There are 2 new classes in gimple-range-side-effect.h * side_effect_manager : maintains a list of "side-effect" ranges for each block. These are also considered to apply upon exit from a block in much the same way the bitmap use to work, except it isn't limited to non-null. * stmt_side_effects : This is the statement level list of side effects on a stmt. The side effect managed is maintained with rangers cache, and is utilized via GORI and ranger itself to apply any side effects that have been registered as appropriate. Its operation is relatively transparent, and you can forget it exists for the most part. When ranger is doing a DOM-walk, as in VRP/EVRP, whenever a stmt is 'finalized', any side effects are registered immediately in the on-entry cache for that block, and any subsequent uses within the block of that name will have the side effects registered. Any pure on-demand clients will only get that benefit on exit from the block. the stmt_side_effect class is a lightweight class that is constructed from a stmt. Once constructed, it becomes a simple list of names/ranges accessed via 3 methods, num(), name(), and range(). ie: stmt_side_effects se (stmt); for (unsigned x = 0; x < se.num (); x++) process (se.name (x), se.range (x)); To keep it lightweight, a small internal vector (currently 10 items) of side effects is maintained. The constructor for this class contains all the "smarts" for finding side effects There is also an option (controlled via a constructor flag) in ranger to continue using the on-demand mechanism of scanning the immediate uses lists with the side-effect manager, as some clients, such as threading, do not process every statement, but still want as accurate information as possible. Otherwise there is no following of imm-use chains anywhere. This patch uses this mechanism to replace the non-null processing, the following 2 patches implement other side effects as simple examples of how its used. The overhead of doing this generically is fairly low. 1% in EVRP and <0.5% everywhere else. Bootstraps on x86_64-pc-linux-gnu with no regressions. pushed. Andrew