https://gcc.gnu.org/bugzilla/show_bug.cgi?id=116899
--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I've gathered some statistics using:
--- gcc/gimple-range-cache.h.jj 2024-07-02 15:07:55.231913151 +0200
+++ gcc/gimple-range-cache.h 2024-09-30 19:03:35.848466925 +0200
@@ -141,6 +141,7 @@ private:
bool edge_range (vrange &r, edge e, tree name, enum rfd_mode);
vec<basic_block> m_workback;
+ unsigned m_workback_init, m_workback_max;
class update_list *m_update;
};
--- gcc/gimple-range-cache.cc.jj 2024-08-10 10:47:48.154848100 +0200
+++ gcc/gimple-range-cache.cc 2024-09-30 19:07:03.103591896 +0200
@@ -1000,6 +1000,8 @@ ranger_cache::ranger_cache (int not_exec
m_workback.create (0);
m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun));
m_workback.truncate (0);
+ m_workback_init = last_basic_block_for_fn (cfun);
+ m_workback_max = 0;
m_temporal = new temporal_cache;
// If DOM info is available, spawn an oracle as well.
@@ -1027,6 +1029,9 @@ ranger_cache::~ranger_cache ()
destroy_relation_oracle ();
delete m_temporal;
m_workback.release ();
+FILE *f = fopen ("/tmp/rangercache", "a");
+fprintf (f, "%d %s %s %d/%d\n", (int) BITS_PER_WORD, main_input_filename ?
main_input_filename : "-", current_function_name (), m_workback_max,
m_workback_init);
+fclose (f);
}
// Dump the global caches to file F. if GORI_DUMP is true, dump the
@@ -1558,6 +1563,7 @@ ranger_cache::fill_block_cache (tree nam
// m_visited at the end will contain all the blocks that we needed to set
// the range_on_entry cache for.
m_workback.quick_push (bb);
+ m_workback_max = MAX (m_workback_max, m_workback.length ());
undefined.set_undefined ();
m_on_entry.set_bb_range (name, bb, undefined);
gcc_checking_assert (m_update->empty_p ());
@@ -1632,6 +1638,7 @@ ranger_cache::fill_block_cache (tree nam
gcc_checking_assert (!m_on_entry.bb_range_p (name, pred));
m_on_entry.set_bb_range (name, pred, undefined);
m_workback.quick_push (pred);
+ m_workback_max = MAX (m_workback_max, m_workback.length ());
}
}
@@ -1726,7 +1733,10 @@ ranger_cache::range_from_dom (vrange &r,
// This block has an outgoing range.
if (gori ().has_edge_range_p (name, bb))
- m_workback.quick_push (prev_bb);
+ {
+ m_workback.quick_push (prev_bb);
+ m_workback_max = MAX (m_workback_max, m_workback.length ());
+ }
else
{
// Normally join blocks don't carry any new range information on
@@ -1750,7 +1760,10 @@ ranger_cache::range_from_dom (vrange &r,
break;
}
if (all_dom)
- m_workback.quick_push (prev_bb);
+ {
+ m_workback.quick_push (prev_bb);
+ m_workback_max = MAX (m_workback_max, m_workback.length ());
+ }
}
}
>From the 305386 entries in /tmp/rangercache (not everything small, 64 entries
even have more than 10000 basic blocks, 535 entries have 1000-9999 basic
blocks, 11670 have 100-999 basic blocks) there was just one case where
m_workback had 11 entries as maximum, 3 with 10 entries as maximum, 56863 with
1-9 entries as maximum and 248519 with 0 entries maximum.
So, even the create (last_basic_block_for_fn (cfun)); seems to be very wasteful
to me, I'd think much better would be m_workback = vNULL; and using safe_push
instead of quick_push.
Yes, we'll quickly compare the m_alloc with m_num + 1 in 4 spots and have some
usually non-executed allocation code around, but we'll allocate only what is
really needed (and with the exponential growth won't be reallocating that much,
on the gathered samples in 81.3% won't allocate anything, in 18.4% allocate
once (4 elements), in 0.21% cases allocate and reallocate once and in 0.0085%
(26 cases in the samples) allocate and reallocate twice.