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.
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(-)
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
