From 7f359556a772e26eabf8d31e53aae1de6f2f200d Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 10 Dec 2020 14:59:14 -0500 Subject: [PATCH] Reduce memory requirements for ranger Calculate block exit info upfront, and then any SSA_NAME which is never used in an outgoing range calculation is a pure global and can bypass the on-entry cache. PR tree-optimization/98174 * gimple-range-cache.cc (ranger_cache::ssa_range_in_bb): Only push poor values to be examined if it isn't a pure global. (ranger_cache::block_range): Don't process pure globals. (ranger_cache::fill_block_cache): Adjust has_edge_range call. * gimple-range-gori.cc (gori_map::all_outgoing): New bitmap. (gori_map::gori_map): Allocate all_outgoing. (gori_map::is_export_p): No specified BB returns global context. (gori_map::calculate_gori): Accumulate each block into global. (gori_compute::gori_compute): Preprocess each block for exports. (gori_compute::has_edge_range_p): No edge returns global context. * gimple-range-gori.h (has_edge_range_p): Provide default parameter. --- gcc/gimple-range-cache.cc | 13 ++++++++++--- gcc/gimple-range-gori.cc | 27 ++++++++++++++++++++++++--- gcc/gimple-range-gori.h | 7 +++++-- 3 files changed, 39 insertions(+), 8 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index b01563c83f9..edebad45a50 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -779,8 +779,10 @@ ranger_cache::ssa_range_in_bb (irange &r, tree name, basic_block bb) // Look for the on-entry value of name in BB from the cache. else if (!m_on_entry.get_bb_range (r, name, bb)) { - // If it has no entry then mark this as a poor value. - if (push_poor_value (bb, name)) + // If it has no entry but should, then mark this as a poor value. + // Its not a poor value if it does not have *any* edge ranges, + // Then global range is as good as it gets. + if (has_edge_range_p (name) && push_poor_value (bb, name)) { if (DEBUG_RANGE_CACHE) { @@ -812,6 +814,11 @@ ranger_cache::block_range (irange &r, basic_block bb, tree name, bool calc) { gcc_checking_assert (gimple_range_ssa_p (name)); + // If there are no range calculations anywhere in the IL, global range + // applies everywhere, so don't bother caching it. + if (!has_edge_range_p (name)) + return false; + if (calc) { gimple *def_stmt = SSA_NAME_DEF_STMT (name); @@ -1072,7 +1079,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) { if (DEBUG_RANGE_CACHE) fprintf (dump_file, "has cache, "); - if (!r.undefined_p () || has_edge_range_p (e, name)) + if (!r.undefined_p () || has_edge_range_p (name, e)) { add_to_update (node); if (DEBUG_RANGE_CACHE) diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index af3609e414e..ac13718f7e6 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -229,17 +229,18 @@ public: gori_map (); ~gori_map (); - bool is_export_p (tree name, basic_block bb); + bool is_export_p (tree name, basic_block bb = NULL); bool def_chain_in_export_p (tree name, basic_block bb); + bitmap exports (basic_block bb); void dump (FILE *f); void dump (FILE *f, basic_block bb); private: bitmap_obstack m_bitmaps; vec m_outgoing; // BB: Outgoing ranges calculatable on edges + bitmap all_outgoing; // All outgoing ranges combined. void maybe_add_gori (tree name, basic_block bb); void calculate_gori (basic_block bb); - bitmap exports (basic_block bb); }; @@ -250,6 +251,7 @@ gori_map::gori_map () m_outgoing.create (0); m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun)); bitmap_obstack_initialize (&m_bitmaps); + all_outgoing = BITMAP_ALLOC (&m_bitmaps); } // Free any memory the GORI map allocated. @@ -276,6 +278,9 @@ gori_map::exports (basic_block bb) bool gori_map::is_export_p (tree name, basic_block bb) { + // If no BB is specified, test if it is exported anywhere in the IL. + if (!bb) + return bitmap_bit_p (all_outgoing, SSA_NAME_VERSION (name)); return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name)); } @@ -342,6 +347,8 @@ gori_map::calculate_gori (basic_block bb) name = gimple_range_ssa_p (gimple_switch_index (gs)); maybe_add_gori (name, gimple_bb (stmt)); } + // Add this bitmap to the aggregate list of all outgoing names. + bitmap_ior_into (all_outgoing, m_outgoing[bb->index]); } // Dump the table information for BB to file F. @@ -438,6 +445,16 @@ gori_compute::gori_compute () m_bool_zero = int_range<2> (boolean_false_node, boolean_false_node); m_bool_one = int_range<2> (boolean_true_node, boolean_true_node); m_gori_map = new gori_map; + unsigned x, lim = last_basic_block_for_fn (cfun); + // Calculate outgoing range info upfront. This will fully populate the + // all_outgoing bitmap which will help eliminate processing of names + // which never have their ranges adjusted. + for (x = 0; x < lim ; x++) + { + basic_block bb = BASIC_BLOCK_FOR_FN (cfun, x); + if (bb) + m_gori_map->exports (bb); + } } // Destruct a gori_compute_object. @@ -969,8 +986,12 @@ gori_compute::compute_operand1_and_operand2_range // Return TRUE if a range can be calcalated for NAME on edge E. bool -gori_compute::has_edge_range_p (edge e, tree name) +gori_compute::has_edge_range_p (tree name, edge e) { + // If no edge is specified, check if NAME is an export on any edge. + if (!e) + return m_gori_map->is_export_p (name); + return (m_gori_map->is_export_p (name, e->src) || m_gori_map->def_chain_in_export_p (name, e->src)); } diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index 8ef452bf433..6cbf532c435 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -29,10 +29,13 @@ along with GCC; see the file COPYING3. If not see // // There are 2 primary entry points: // -// has_edge_range_p (edge e, tree name) +// has_edge_range_p (tree name, edge e) // returns true if the outgoing edge *may* be able to produce range // information for ssa_name NAME on edge E. // FALSE is returned if this edge does not affect the range of NAME. +// if no edge is specified, return TRUE if name may have a value calculated +// on *ANY* edge that has been seen. FALSE indicates that the global value +// is applicable everywhere that has been processed. // // outgoing_edge_range_p (irange &range, edge e, tree name) // Actually does the calculation of RANGE for name on E @@ -68,7 +71,7 @@ public: gori_compute (); ~gori_compute (); bool outgoing_edge_range_p (irange &r, edge e, tree name); - bool has_edge_range_p (edge e, tree name); + bool has_edge_range_p (tree name, edge e = NULL); void dump (FILE *f); protected: virtual void ssa_range_in_bb (irange &r, tree name, basic_block bb); -- 2.30.2