On Fri, Mar 10, 2017 at 11:34 PM, Alexandre Oliva <aol...@redhat.com> wrote:
> On Mar 10, 2017, Alexandre Oliva <aol...@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
