From patchwork Wed Jun 16 15:58:09 2010
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: 0005-Search-all-dominated-blocks-for-expressions-to-hoist.patch
Date: Wed, 16 Jun 2010 05:58:09 -0000
From: Maxim Kuvyrkov <maxim@codesourcery.com>
X-Patchwork-Id: 55906
Message-Id: <4C18F491.2000406@codesourcery.com>
To: Jeff Law <law@redhat.com>, gcc-patches <gcc-patches@gcc.gnu.org>

Currently, code hoisting only checks immediately-dominated blocks for 
expressions to hoist.  I wonder if limiting the search for expressions 
is intentional.

This patch makes code hoisting search through all dominated blocks for 
expressions to hoist.

On one hand, hoisting expressions from all dominated blocks, not just 
the immediate dominees, provides significantly greater unification 
opportunities.  On the other hand, it can also substantially extend live 
ranges of pseudos, and increase register pressure.

Even considering the negatives, hoisting expressions from non-immediate 
dominees seems like the right choice to me.  Most expressions that can 
be moved several basic blocks up are constants, and IRA/reload should be 
able to rematerialize those under high register pressure.  On the 
flip-side, if an expression is complex, than it would be less costly to 
spill/restore it instead of calculating it in dominated blocks.

A compromise may be to limit the depth of search with a parameter.

OK to apply?

Thank you,


diff --git a/gcc/gcse.c b/gcc/gcse.c
index 45cab70..a7c7237 100644
--- a/gcc/gcse.c
+++ b/gcc/gcse.c
@@ -4327,7 +4327,8 @@ hoist_code (void)
       int found = 0;
       int insn_inserted_p;
 
-      domby = get_dominated_by (CDI_DOMINATORS, bb);
+      domby = get_all_dominated_blocks (CDI_DOMINATORS, bb);
+
       /* Examine each expression that is very busy at the exit of this
 	 block.  These are the potentially hoistable expressions.  */
       for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++)
@@ -4418,7 +4419,11 @@ hoist_code (void)
 		     it would be safe to compute it at the start of the
 		     dominated block.  Now we have to determine if the
 		     expression would reach the dominated block if it was
-		     placed at the end of BB.  */
+		     placed at the end of BB.
+		     Note: the fact that hoist_exprs has i-th bit set means
+		     that /some/, not necesserilly all, occurences from
+		     the dominated blocks can be hoisted to BB.  Here we check
+		     if a specific occurence can be hoisted to BB.  */
 		  if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
 		    {
 		      struct expr *expr = index_map[i];
@@ -4431,6 +4436,12 @@ hoist_code (void)
 			occr = occr->next;
 
 		      gcc_assert (occr);
+
+		      /* An occurence might've been already deleted
+			 while processing a dominator of BB.  */
+		      if (occr->deleted_p)
+			continue;
+
 		      insn = occr->insn;
 		      set = single_set (insn);
 		      gcc_assert (set);