[RFC] Teaching SCC merging about unit local trees
Jan Hubicka
hubicka@ucw.cz
Wed Jul 9 09:09:00 GMT 2014
Richard,
>
> That is, have a tree_may_be_mergeable_p (), call it during the DFS
> walk storing it alongside the visited edges and thus obtain a result
> for each SCC, stream that as a flag (a special hash value is ugly,
> but well ... I guess it works). The important part is to make an SCC
> !tree_may_be_mergeable_p () if any of the outgoing edges from an SCC
> are !tree_may_be_mergeable_p (). You seem to miss this.
I would like to discuss this a bit more. tree_may_be_mergeable_p (t) is
actually !unit_local_tree_p (t) bellow. (no problem with either of the names)
I the flight I however played witht he variant detecting mergeable/unmergeable
trees within the SCC walk. It gets bit more complicated than the scc_hash version
bellow primarily because the scc_hash already know that some of the fields are
streamed but do not matter for merging. (you can have TRANSLATION_UNIT_DECL
that is unit local and it is context of a type that is mergeable).
It seems to me that going the route of special hash code "you won't merge me"
actually avoids duplicating this logic and works bit smoother downstream, too.
Honza
>
> Richard.
>
> > Richard.
> >
> >> Richard.
> >>
> >>>
> >>> Would something like this make sense? (I am not saying my definition of unit_local_tree_p
> >>> is most polished one :)
> >>>
> >>> I think next step could be to make anonymous types to bypass the canonical type
> >>> merging (i.e. simply save the chains as they comde from frontends forthose) and
> >>> then look into computing the type names in free lang data, using odr name hash instaed
> >>> of canonical type hash for those named types + link them to canonical type hash
> >>> entries and if we end up with unnamed type in canonical type hash, then make its
> >>> alias class to conflict with all the named types.
> >>>
> >>> Honza
> >>>
> >>> Index: lto-streamer-out.c
> >>> ===================================================================
> >>> --- lto-streamer-out.c (revision 211488)
> >>> +++ lto-streamer-out.c (working copy)
> >>> @@ -54,6 +54,47 @@ along with GCC; see the file COPYING3.
> >>> #include "cfgloop.h"
> >>> #include "builtins.h"
> >>>
> >>> +/* Return if T can never be shared across units. */
> >>> +static bool
> >>> +unit_local_tree_p (tree t)
> >>> +{
> >>> + switch (TREE_CODE (t))
> >>> + {
> >>> + case VAR_DECL:
> >>> + /* Automatic variables are always unit local. */
> >>> + if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)
> >>> + && !DECL_HARD_REGISTER (t))
> >>> + return true;
> >>> + /* ... fall through ... */
> >>> +
> >>> + case FUNCTION_DECL:
> >>> + /* Non-public declarations are alwyas local. */
> >>> + if (!TREE_PUBLIC (t))
> >>> + return true;
> >>> +
> >>> + /* Public definitions that would cause linker error if
> >>> + appeared in other unit. */
> >>> + if (TREE_PUBLIC (t)
> >>> + && !DECL_EXTERNAL (t)
> >>> + && !DECL_WEAK (t))
> >>> + return true;
> >>> + return false;
> >>> + case NAMESPACE_DECL:
> >>> + return !TREE_PUBLIC (t);
> >>> + case TRANSLATION_UNIT_DECL:
> >>> + return true;
> >>> + case PARM_DECL:
> >>> + case RESULT_DECL:
> >>> + case LABEL_DECL:
> >>> + case SSA_NAME:
> >>> + return true;
> >>> + default:
> >>> + if (TYPE_P (t)
> >>> + && type_in_anonymous_namespace_p (t))
> >>> + return true;
> >>> + return false;
> >>> + }
> >>> +}
> >>>
> >>> static void lto_write_tree (struct output_block*, tree, bool);
> >>>
> >>> @@ -686,7 +727,9 @@ DFS_write_tree_body (struct output_block
> >>> #undef DFS_follow_tree_edge
> >>> }
> >>>
> >>> -/* Return a hash value for the tree T. */
> >>> +/* Return a hash value for the tree T.
> >>> + If T is local to unit or refers anything local to unit, return 1.
> >>> + Otherwise return non-1. */
> >>>
> >>> static hashval_t
> >>> hash_tree (struct streamer_tree_cache_d *cache, tree t)
> >>> @@ -694,10 +737,19 @@ hash_tree (struct streamer_tree_cache_d
> >>> #define visit(SIBLING) \
> >>> do { \
> >>> unsigned ix; \
> >>> + hashval_t h; \
> >>> if (SIBLING && streamer_tree_cache_lookup (cache, SIBLING, &ix)) \
> >>> - v = iterative_hash_hashval_t (streamer_tree_cache_get_hash (cache, ix), v); \
> >>> + { \
> >>> + h = streamer_tree_cache_get_hash (cache, ix); \
> >>> + if (h == STREAMER_TREE_CACHE_HASH_LOCAL) \
> >>> + return STREAMER_TREE_CACHE_HASH_LOCAL; \
> >>> + v = iterative_hash_hashval_t (h, v); \
> >>> + } \
> >>> } while (0)
> >>>
> >>> + if (unit_local_tree_p (t))
> >>> + return STREAMER_TREE_CACHE_HASH_LOCAL;
> >>> +
> >>> /* Hash TS_BASE. */
> >>> enum tree_code code = TREE_CODE (t);
> >>> hashval_t v = iterative_hash_host_wide_int (code, 0);
> >>> @@ -911,7 +963,11 @@ hash_tree (struct streamer_tree_cache_d
> >>> hashval_t x;
> >>> unsigned ix;
> >>> if (streamer_tree_cache_lookup (cache, TREE_TYPE (t), &ix))
> >>> - x = streamer_tree_cache_get_hash (cache, ix);
> >>> + {
> >>> + x = streamer_tree_cache_get_hash (cache, ix);
> >>> + if (x == STREAMER_TREE_CACHE_HASH_LOCAL)
> >>> + return STREAMER_TREE_CACHE_HASH_LOCAL;
> >>> + }
> >>> else
> >>> x = hash_tree (cache, TREE_TYPE (t));
> >>> v = iterative_hash_hashval_t (x, v);
> >>> @@ -1101,7 +1157,7 @@ hash_tree (struct streamer_tree_cache_d
> >>> visit (OMP_CLAUSE_CHAIN (t));
> >>> }
> >>>
> >>> - return v;
> >>> + return v + (v == STREAMER_TREE_CACHE_HASH_LOCAL);
> >>>
> >>> #undef visit
> >>> }
> >>> @@ -1121,14 +1177,25 @@ scc_entry_compare (const void *p1_, cons
> >>> }
> >>>
> >>> /* Return a hash value for the SCC on the SCC stack from FIRST with
> >>> - size SIZE. */
> >>> + size SIZE.
> >>> + If STREAMER_TREE_CACHE_HASH_LOCAL is returned, we know the SCC will never
> >>> + get merged with other unit. */
> >>>
> >>> static hashval_t
> >>> hash_scc (struct streamer_tree_cache_d *cache, unsigned first, unsigned size)
> >>> {
> >>> /* Compute hash values for the SCC members. */
> >>> for (unsigned i = 0; i < size; ++i)
> >>> - sccstack[first+i].hash = hash_tree (cache, sccstack[first+i].t);
> >>> + {
> >>> + sccstack[first+i].hash = hash_tree (cache, sccstack[first+i].t);
> >>> + /* If any member of SCC is local, whole SCC is. */
> >>> + if (sccstack[first+i].hash == STREAMER_TREE_CACHE_HASH_LOCAL)
> >>> + {
> >>> + for (unsigned i = 0; i < size; ++i)
> >>> + sccstack[first+i].hash = STREAMER_TREE_CACHE_HASH_LOCAL;
> >>> + return STREAMER_TREE_CACHE_HASH_LOCAL;
> >>> + }
> >>> + }
> >>>
> >>> if (size == 1)
> >>> return sccstack[first].hash;
> >>> @@ -1161,7 +1228,7 @@ hash_scc (struct streamer_tree_cache_d *
> >>> sccstack[first+i].hash = tem[i];
> >>> scc_hash = iterative_hash_hashval_t (tem[i], scc_hash);
> >>> }
> >>> - return scc_hash;
> >>> + return scc_hash + (scc_hash == STREAMER_TREE_CACHE_HASH_LOCAL);
> >>> }
> >>>
> >>> /* DFS walk EXPR and stream SCCs of tree bodies if they are not
> >>> @@ -1242,26 +1309,29 @@ DFS_write_tree (struct output_block *ob,
> >>> scc_hash = hash_scc (ob->writer_cache, first, size);
> >>>
> >>> /* Put the entries with the least number of collisions first. */
> >>> - unsigned entry_start = 0;
> >>> - scc_entry_len = size + 1;
> >>> - for (unsigned i = 0; i < size;)
> >>> + if (scc_hash != STREAMER_TREE_CACHE_HASH_LOCAL)
> >>> {
> >>> - unsigned from = i;
> >>> - for (i = i + 1; i < size
> >>> - && (sccstack[first + i].hash
> >>> - == sccstack[first + from].hash); ++i)
> >>> - ;
> >>> - if (i - from < scc_entry_len)
> >>> + unsigned entry_start = 0;
> >>> + scc_entry_len = size + 1;
> >>> + for (unsigned i = 0; i < size;)
> >>> {
> >>> - scc_entry_len = i - from;
> >>> - entry_start = from;
> >>> + unsigned from = i;
> >>> + for (i = i + 1; i < size
> >>> + && (sccstack[first + i].hash
> >>> + == sccstack[first + from].hash); ++i)
> >>> + ;
> >>> + if (i - from < scc_entry_len)
> >>> + {
> >>> + scc_entry_len = i - from;
> >>> + entry_start = from;
> >>> + }
> >>> + }
> >>> + for (unsigned i = 0; i < scc_entry_len; ++i)
> >>> + {
> >>> + scc_entry tem = sccstack[first + i];
> >>> + sccstack[first + i] = sccstack[first + entry_start + i];
> >>> + sccstack[first + entry_start + i] = tem;
> >>> }
> >>> - }
> >>> - for (unsigned i = 0; i < scc_entry_len; ++i)
> >>> - {
> >>> - scc_entry tem = sccstack[first + i];
> >>> - sccstack[first + i] = sccstack[first + entry_start + i];
> >>> - sccstack[first + entry_start + i] = tem;
> >>> }
> >>> }
> >>>
> >>> @@ -1271,7 +1341,7 @@ DFS_write_tree (struct output_block *ob,
> >>> streamer_write_uhwi (ob, scc_hash);
> >>>
> >>> /* Write size-1 SCCs without wrapping them inside SCC bundles.
> >>> - All INTEGER_CSTs need to be handled this way as we need
> >>> + All INTEGER_CSTs need thiso be handled this way as we need
> >>> their type to materialize them. Also builtins are handled
> >>> this way.
> >>> ??? We still wrap these in LTO_tree_scc so at the
> >>> @@ -1291,6 +1361,8 @@ DFS_write_tree (struct output_block *ob,
> >>> tree t = sccstack[first+i].t;
> >>> bool exists_p = streamer_tree_cache_insert (ob->writer_cache,
> >>> t, hash, &ix);
> >>> + gcc_assert (scc_hash != STREAMER_TREE_CACHE_HASH_LOCAL
> >>> + || hash == STREAMER_TREE_CACHE_HASH_LOCAL);
> >>> gcc_assert (!exists_p);
> >>>
> >>> if (!lto_is_streamable (t))
> >>> Index: lto/lto.c
> >>> ===================================================================
> >>> --- lto/lto.c (revision 211488)
> >>> +++ lto/lto.c (working copy)
> >>> @@ -1896,7 +1897,7 @@ lto_read_decls (struct lto_file_decl_dat
> >>> continue;
> >>>
> >>> /* Try to unify the SCC with already existing ones. */
> >>> - if (!flag_ltrans
> >>> + if (!flag_ltrans && scc_hash != STREAMER_TREE_CACHE_HASH_LOCAL
> >>> && unify_scc (data_in->reader_cache, from,
> >>> len, scc_entry_len, scc_hash))
> >>> continue;
More information about the Gcc-patches
mailing list