stabilize store merging

On Mar 10, 2017, Alexandre Oliva <aoliva@redhat.com> wrote:

> Now, if there's something you dislike about maps, we could make it a
> doubly-linked list, or maybe even a singly-linked list.

Scratch that, there's a use that may remove after a lookup by base_addr,
so a singly-linked list would require a linear walk of the list in this
case.  So, doubly-linked it is, which means...

> it costs just a pointer vs an int in the chains and an additional
> pointer over your suggestion, but it saves the shuffling and sorting.

... make it two pointers instead.


How's this?  Regstrapping now...  Ok if it passes?


Don't let pointer randomization change the order in which we process
store chains.  This may cause SSA_NAMEs to be released in different
order, and if they're reused later, they may cause differences in SSA
partitioning, leading to differences in expand, and ultimately to
different code.

bootstrap-debug-lean (-fcompare-debug) on i686-linux-gnu has failed in
haifa-sched.c since r245196 exposed the latent ordering problem in
store merging.  In this case, the IR differences (different SSA names
selected for copies in out-of-SSA, resulting in some off-by-one
differences in pseudos) were not significant enough to be visible in
the compiler output.


for  gcc/ChangeLog

	* gimple-ssa-store-merging.c (struct imm_store_chain_info):
	Add linked-list forward and backlinks.  Insert on
	construction, remove on destruction.
	(class pass_store_merging): Add m_stores_head field.
	(pass_store_merging::terminate_and_process_all_chains):
	Iterate over m_stores_head list.
	(pass_store_merging::terminate_all_aliasing_chains):
	Likewise.
	(pass_store_merging::execute): Check for debug stmts first.
	Push new chains onto the m_stores_head stack.
---
 gcc/gimple-ssa-store-merging.c |   65 ++++++++++++++++++++++++++++++----------
 1 file changed, 49 insertions(+), 16 deletions(-)

On Fri, Mar 10, 2017 at 11:34 PM, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Mar 10, 2017, Alexandre Oliva <aoliva@redhat.com> wrote:
>
>> Now, if there's something you dislike about maps, we could make it a
>> doubly-linked list, or maybe even a singly-linked list.

I indeed mis-matched std::map for hash_map but I also think we should
use GCCs own interfaces and STL uses are generally discouraged.

> Scratch that, there's a use that may remove after a lookup by base_addr,
> so a singly-linked list would require a linear walk of the list in this
> case.  So, doubly-linked it is, which means...
>
>> it costs just a pointer vs an int in the chains and an additional
>> pointer over your suggestion, but it saves the shuffling and sorting.
>
> ... make it two pointers instead.
>
>
> How's this?  Regstrapping now...  Ok if it passes?

Ok.

[now C++-ish the next/pnxp could be abstracted as a (templated) base class]

Thanks,
Richard.

> Don't let pointer randomization change the order in which we process
> store chains.  This may cause SSA_NAMEs to be released in different
> order, and if they're reused later, they may cause differences in SSA
> partitioning, leading to differences in expand, and ultimately to
> different code.
>
> bootstrap-debug-lean (-fcompare-debug) on i686-linux-gnu has failed in
> haifa-sched.c since r245196 exposed the latent ordering problem in
> store merging.  In this case, the IR differences (different SSA names
> selected for copies in out-of-SSA, resulting in some off-by-one
> differences in pseudos) were not significant enough to be visible in
> the compiler output.
>
>
> for  gcc/ChangeLog
>
>         * gimple-ssa-store-merging.c (struct imm_store_chain_info):
>         Add linked-list forward and backlinks.  Insert on
>         construction, remove on destruction.
>         (class pass_store_merging): Add m_stores_head field.
>         (pass_store_merging::terminate_and_process_all_chains):
>         Iterate over m_stores_head list.
>         (pass_store_merging::terminate_all_aliasing_chains):
>         Likewise.
>         (pass_store_merging::execute): Check for debug stmts first.
>         Push new chains onto the m_stores_head stack.
> ---
>  gcc/gimple-ssa-store-merging.c |   65 ++++++++++++++++++++++++++++++----------
>  1 file changed, 49 insertions(+), 16 deletions(-)
>
> diff --git a/gcc/gimple-ssa-store-merging.c b/gcc/gimple-ssa-store-merging.c
> index 17ac94a..5bdb459 100644
> --- a/gcc/gimple-ssa-store-merging.c
> +++ b/gcc/gimple-ssa-store-merging.c
> @@ -675,11 +675,34 @@ merged_store_group::apply_stores ()
>
>  struct imm_store_chain_info
>  {
> +  /* Doubly-linked list that imposes an order on chain processing.
> +     PNXP (prev's next pointer) points to the head of a list, or to
> +     the next field in the previous chain in the list.
> +     See pass_store_merging::m_stores_head for more rationale.  */
> +  imm_store_chain_info *next, **pnxp;
>    tree base_addr;
>    auto_vec<struct store_immediate_info *> m_store_info;
>    auto_vec<merged_store_group *> m_merged_store_groups;
>
> -  imm_store_chain_info (tree b_a) : base_addr (b_a) {}
> +  imm_store_chain_info (imm_store_chain_info *&inspt, tree b_a)
> +  : next (inspt), pnxp (&inspt), base_addr (b_a)
> +  {
> +    inspt = this;
> +    if (next)
> +      {
> +       gcc_checking_assert (pnxp == next->pnxp);
> +       next->pnxp = &next;
> +      }
> +  }
> +  ~imm_store_chain_info ()
> +  {
> +    *pnxp = next;
> +    if (next)
> +      {
> +       gcc_checking_assert (&next == next->pnxp);
> +       next->pnxp = pnxp;
> +      }
> +  }
>    bool terminate_and_process_chain ();
>    bool coalesce_immediate_stores ();
>    bool output_merged_store (merged_store_group *);
> @@ -718,6 +741,17 @@ public:
>  private:
>    hash_map<tree_operand_hash, struct imm_store_chain_info *> m_stores;
>
> +  /* Form a doubly-linked stack of the elements of m_stores, so that
> +     we can iterate over them in a predictable way.  Using this order
> +     avoids extraneous differences in the compiler output just because
> +     of tree pointer variations (e.g. different chains end up in
> +     different positions of m_stores, so they are handled in different
> +     orders, so they allocate or release SSA names in different
> +     orders, and when they get reused, subsequent passes end up
> +     getting different SSA names, which may ultimately change
> +     decisions when going out of SSA).  */
> +  imm_store_chain_info *m_stores_head;
> +
>    bool terminate_and_process_all_chains ();
>    bool terminate_all_aliasing_chains (imm_store_chain_info **,
>                                       bool, gimple *);
> @@ -730,11 +764,11 @@ private:
>  bool
>  pass_store_merging::terminate_and_process_all_chains ()
>  {
> -  hash_map<tree_operand_hash, struct imm_store_chain_info *>::iterator iter
> -    = m_stores.begin ();
>    bool ret = false;
> -  for (; iter != m_stores.end (); ++iter)
> -    ret |= terminate_and_release_chain ((*iter).second);
> +  while (m_stores_head)
> +    ret |= terminate_and_release_chain (m_stores_head);
> +  gcc_assert (m_stores.elements () == 0);
> +  gcc_assert (m_stores_head == NULL);
>
>    return ret;
>  }
> @@ -799,15 +833,14 @@ pass_store_merging::terminate_all_aliasing_chains (imm_store_chain_info
>         }
>      }
>
> -  hash_map<tree_operand_hash, struct imm_store_chain_info *>::iterator iter
> -    = m_stores.begin ();
> -
>    /* Check for aliasing with all other store chains.  */
> -  for (; iter != m_stores.end (); ++iter)
> +  for (imm_store_chain_info *next = m_stores_head, *cur = next; cur; cur = next)
>      {
> +      next = cur->next;
> +
>        /* We already checked all the stores in chain_info and terminated the
>          chain if necessary.  Skip it here.  */
> -      if (chain_info && (*chain_info) == (*iter).second)
> +      if (chain_info && (*chain_info) == cur)
>         continue;
>
>        /* We can't use the base object here as that does not reliably exist.
> @@ -815,11 +848,11 @@ pass_store_merging::terminate_all_aliasing_chains (imm_store_chain_info
>          minimum and maximum offset and the maximum size we could improve
>          things here).  */
>        ao_ref chain_ref;
> -      ao_ref_init_from_ptr_and_size (&chain_ref, (*iter).first, NULL_TREE);
> +      ao_ref_init_from_ptr_and_size (&chain_ref, cur->base_addr, NULL_TREE);
>        if (ref_maybe_used_by_stmt_p (stmt, &chain_ref)
>           || stmt_may_clobber_ref_p_1 (stmt, &chain_ref))
>         {
> -         terminate_and_release_chain ((*iter).second);
> +         terminate_and_release_chain (cur);
>           ret = true;
>         }
>      }
> @@ -1336,6 +1369,9 @@ pass_store_merging::execute (function *fun)
>         {
>           gimple *stmt = gsi_stmt (gsi);
>
> +         if (is_gimple_debug (stmt))
> +           continue;
> +
>           if (gimple_has_volatile_ops (stmt))
>             {
>               /* Terminate all chains.  */
> @@ -1346,9 +1382,6 @@ pass_store_merging::execute (function *fun)
>               continue;
>             }
>
> -         if (is_gimple_debug (stmt))
> -           continue;
> -
>           if (gimple_assign_single_p (stmt) && gimple_vdef (stmt)
>               && !stmt_can_throw_internal (stmt)
>               && lhs_valid_for_store_merging_p (gimple_assign_lhs (stmt)))
> @@ -1456,7 +1489,7 @@ pass_store_merging::execute (function *fun)
>                   terminate_all_aliasing_chains (chain_info, false, stmt);
>                   /* Start a new chain.  */
>                   struct imm_store_chain_info *new_chain
> -                   = new imm_store_chain_info (base_addr);
> +                   = new imm_store_chain_info (m_stores_head, base_addr);
>                   info = new store_immediate_info (bitsize, bitpos,
>                                                    stmt, 0);
>                   new_chain->m_store_info.safe_push (info);
>
>
> --
> Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
> You must be the change you wish to see in the world. -- Gandhi
> Be Free! -- http://FSFLA.org/   FSF Latin America board member
> Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer