From e86fd6a17cdb26710d1f13c9a47a3878c76028f9 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 4 Nov 2020 12:59:15 -0500 Subject: [PATCH] Add Ranger temporal cache Add a timestamp to supplement the global range cache to detect when a value may become stale. gcc/ PR tree-optimization/97515 * gimple-range-cache.h (class ranger_cache): New prototypes plus temporal cache pointer. * gimple-range-cache.cc (struct range_timestamp): New. (class temporal_cache): New. (temporal_cache::temporal_cache): New. (temporal_cache::~temporal_cache): New. (temporal_cache::get_timestamp): New. (temporal_cache::set_dependency): New. (temporal_cache::temporal_value): New. (temporal_cache::current_p): New. (temporal_cache::set_timestamp): New. (temporal_cache::set_always_current): New. (ranger_cache::ranger_cache): Allocate the temporal cache. (ranger_cache::~ranger_cache): Free temporal cache. (ranger_cache::get_non_stale_global_range): New. (ranger_cache::set_global_range): Add a timestamp. (ranger_cache::register_dependency): New. Add timestamp dependency. * gimple-range.cc (gimple_ranger::range_of_range_op): Add operand dependencies. (gimple_ranger::range_of_phi): Ditto. (gimple_ranger::range_of_stmt): Check if global range is stale, and recalculate if so. gcc/testsuite/ * gcc.dg/pr97515.c: Check listing for folding of entire function. --- gcc/gimple-range-cache.cc | 174 +++++++++++++++++++++++++++++++++++++++++ gcc/gimple-range-cache.h | 3 + gcc/gimple-range.cc | 23 +++--- gcc/testsuite/gcc.dg/pr97515.c | 6 +- 4 files changed, 196 insertions(+), 10 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index cca9025..b01563c 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -478,6 +478,140 @@ ssa_global_cache::dump (FILE *f) // -------------------------------------------------------------------------- + +// This struct provides a timestamp for a global range calculation. +// it contains the time counter, as well as a limited number of ssa-names +// that it is dependent upon. If the timestamp for any of the dependent names +// Are newer, then this range could need updating. + +struct range_timestamp +{ + unsigned time; + unsigned ssa1; + unsigned ssa2; +}; + +// This class will manage the timestamps for each ssa_name. +// When a value is calcualted, its timestamp is set to the current time. +// The ssanames it is dependent on have already been calculated, so they will +// have older times. If one fo those values is ever calculated again, it +// will get a newer timestamp, and the "current_p" check will fail. + +class temporal_cache +{ +public: + temporal_cache (); + ~temporal_cache (); + bool current_p (tree name) const; + void set_timestamp (tree name); + void set_dependency (tree name, tree dep); + void set_always_current (tree name); +private: + unsigned temporal_value (unsigned ssa) const; + const range_timestamp *get_timestamp (unsigned ssa) const; + range_timestamp *get_timestamp (unsigned ssa); + + unsigned m_current_time; + vec m_timestamp; +}; + + +inline +temporal_cache::temporal_cache () +{ + m_current_time = 1; + m_timestamp.create (0); + m_timestamp.safe_grow_cleared (num_ssa_names); +} + +inline +temporal_cache::~temporal_cache () +{ + m_timestamp.release (); +} + +// Return a pointer to the timetamp for ssa-name at index SSA, if there is +// one, otherwise return NULL. + +inline const range_timestamp * +temporal_cache::get_timestamp (unsigned ssa) const +{ + if (ssa >= m_timestamp.length ()) + return NULL; + return &(m_timestamp[ssa]); +} + +// Return a reference to the timetamp for ssa-name at index SSA. If the index +// is past the end of the vector, extend the vector. + +inline range_timestamp * +temporal_cache::get_timestamp (unsigned ssa) +{ + if (ssa >= m_timestamp.length ()) + m_timestamp.safe_grow_cleared (num_ssa_names + 20); + return &(m_timestamp[ssa]); +} + +// This routine will fill NAME's next operand slot with DEP if DEP is a valid +// SSA_NAME and there is a free slot. + +inline void +temporal_cache::set_dependency (tree name, tree dep) +{ + if (dep && TREE_CODE (dep) == SSA_NAME) + { + gcc_checking_assert (get_timestamp (SSA_NAME_VERSION (name))); + range_timestamp& ts = *(get_timestamp (SSA_NAME_VERSION (name))); + if (!ts.ssa1) + ts.ssa1 = SSA_NAME_VERSION (dep); + else if (!ts.ssa2 && ts.ssa1 != SSA_NAME_VERSION (name)) + ts.ssa2 = SSA_NAME_VERSION (dep); + } +} + +// Return the timestamp value for SSA, or 0 if there isnt one. +inline unsigned +temporal_cache::temporal_value (unsigned ssa) const +{ + const range_timestamp *ts = get_timestamp (ssa); + return ts ? ts->time : 0; +} + +// Return TRUE if the timestampe for NAME is newer than any of its dependents. + +bool +temporal_cache::current_p (tree name) const +{ + const range_timestamp *ts = get_timestamp (SSA_NAME_VERSION (name)); + if (!ts || ts->time == 0) + return true; + // Any non-registered dependencies will have a value of 0 and thus be older. + // Return true if time is newer than either dependent. + return ts->time > temporal_value (ts->ssa1) + && ts->time > temporal_value (ts->ssa2); +} + +// This increments the global timer and sets the timestamp for NAME. + +inline void +temporal_cache::set_timestamp (tree name) +{ + gcc_checking_assert (get_timestamp (SSA_NAME_VERSION (name))); + get_timestamp (SSA_NAME_VERSION (name))->time = ++m_current_time; +} + +// Set the timestamp to 0, marking it as "always up to date". + +inline void +temporal_cache::set_always_current (tree name) +{ + gcc_checking_assert (get_timestamp (SSA_NAME_VERSION (name))); + get_timestamp (SSA_NAME_VERSION (name))->time = 0; +} + + +// -------------------------------------------------------------------------- + ranger_cache::ranger_cache (gimple_ranger &q) : query (q) { m_workback.create (0); @@ -488,10 +622,12 @@ ranger_cache::ranger_cache (gimple_ranger &q) : query (q) m_poor_value_list.create (0); m_poor_value_list.safe_grow_cleared (20); m_poor_value_list.truncate (0); + m_temporal = new temporal_cache; } ranger_cache::~ranger_cache () { + delete m_temporal; m_poor_value_list.release (); m_workback.release (); m_update_list.release (); @@ -529,6 +665,32 @@ ranger_cache::get_global_range (irange &r, tree name) const return m_globals.get_global_range (r, name); } +// Get the global range for NAME, and return in R if the value is not stale. +// If the range is set, but is stale, mark it current and return false. +// If it is not set pick up the legacy global value, mark it current, and +// return false. +// Note there is always a value returned in R. The return value indicates +// whether that value is an up-to-date calculated value or not.. + +bool +ranger_cache::get_non_stale_global_range (irange &r, tree name) +{ + if (m_globals.get_global_range (r, name)) + { + if (m_temporal->current_p (name)) + return true; + } + else + { + // Global has never been accessed, so pickup the legacy global value. + r = gimple_range_global (name); + m_globals.set_global_range (name, r); + } + // After a stale check failure, mark the value as always current until a + // new one is set. + m_temporal->set_always_current (name); + return false; +} // Set the global range of NAME to R. void @@ -546,6 +708,18 @@ ranger_cache::set_global_range (tree name, const irange &r) propagate_updated_value (name, bb); } + // Mark the value as up-to-date. + m_temporal->set_timestamp (name); +} + +// Register a dependency on DEP to name. If the timestamp for DEP is ever +// greateer than the timestamp for NAME, then it is newer and NAMEs value +// becomes stale. + +void +ranger_cache::register_dependency (tree name, tree dep) +{ + m_temporal->set_dependency (name, dep); } // Push a request for a new lookup in block BB of name. Return true if diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 0e84ab0..c5749fe 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -97,7 +97,9 @@ public: bool block_range (irange &r, basic_block bb, tree name, bool calc = true); bool get_global_range (irange &r, tree name) const; + bool get_non_stale_global_range (irange &r, tree name); void set_global_range (tree name, const irange &r); + void register_dependency (tree name, tree dep); non_null_ref m_non_null; @@ -106,6 +108,7 @@ public: private: ssa_global_cache m_globals; block_range_cache m_on_entry; + class temporal_cache *m_temporal; void add_to_update (basic_block bb); void fill_block_cache (tree name, basic_block bb, basic_block def_bb); void propagate_cache (tree name); diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 8fdcc31..ef65e00 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -415,12 +415,20 @@ bool gimple_ranger::range_of_range_op (irange &r, gimple *s) { int_range_max range1, range2; + tree lhs = gimple_get_lhs (s); tree type = gimple_expr_type (s); gcc_checking_assert (irange::supports_type_p (type)); tree op1 = gimple_range_operand1 (s); tree op2 = gimple_range_operand2 (s); + if (lhs) + { + // Register potential dependencies for stale value tracking. + m_cache.register_dependency (lhs, op1); + m_cache.register_dependency (lhs, op2); + } + if (range_of_non_trivial_assignment (r, s)) return true; @@ -501,6 +509,9 @@ gimple_ranger::range_of_phi (irange &r, gphi *phi) tree arg = gimple_phi_arg_def (phi, x); edge e = gimple_phi_arg_edge (phi, x); + // Register potential dependencies for stale value tracking. + m_cache.register_dependency (phi_def, arg); + range_on_edge (arg_range, e, arg); r.union_ (arg_range); // Once the value reaches varying, stop looking. @@ -1009,18 +1020,12 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) if (!gimple_range_ssa_p (name)) return false; - // If this STMT has already been processed, return that value. - if (m_cache.get_global_range (r, name)) + // Check if the stmt has already been processed, and is not stale. + if (m_cache.get_non_stale_global_range (r, name)) return true; - // Avoid infinite recursion by initializing global cache - int_range_max tmp = gimple_range_global (name); - m_cache.set_global_range (name, tmp); - + // Otherwise calculate a new value and save it. calc_stmt (r, s, name); - - if (is_a (s)) - r.intersect (tmp); m_cache.set_global_range (name, r); return true; } diff --git a/gcc/testsuite/gcc.dg/pr97515.c b/gcc/testsuite/gcc.dg/pr97515.c index 2b6185e..84f145a 100644 --- a/gcc/testsuite/gcc.dg/pr97515.c +++ b/gcc/testsuite/gcc.dg/pr97515.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2" } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ int e7 (int gg) @@ -19,3 +19,7 @@ e7 (int gg) return xe; } + +/* EVRP should be able to reduce this to a single goto. */ + +/* { dg-final { scan-tree-dump-times "goto" 1 "evrp" } } */ -- 2.7.4