From patchwork Wed Jun 16 15:56:54 2010
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: 0003-Improve-VBEout-computation.patch
Date: Wed, 16 Jun 2010 05:56:54 -0000
From: Maxim Kuvyrkov <maxim@codesourcery.com>
X-Patchwork-Id: 55903
Message-Id: <4C18F446.20508@codesourcery.com>
To: Jeff Law <law@redhat.com>, gcc-patches <gcc-patches@gcc.gnu.org>

Code hoisting algorithm from Muchnick, which is the one implemented in 
GCC, has a quirk in that it does include expressions calculated in basic 
block in its VBEout set.  This seems odd to me; if an expression is 
calculated in BB and is available at BB's end, then we do want to hoist 
expressions from BB's successors to the end of BB.  This patch 
implements this.

The patch also adds an open-ended comment which describes another 
possible improvement to the algorithm.

OK to apply?

Thank you,


diff --git a/gcc/gcse.c b/gcc/gcse.c
index 00f3841..74986a4 100644
--- a/gcc/gcse.c
+++ b/gcc/gcse.c
@@ -4171,13 +4171,52 @@ compute_code_hoist_vbeinout (void)
       FOR_EACH_BB_REVERSE (bb)
 	{
 	  if (bb->next_bb != EXIT_BLOCK_PTR)
-	    sbitmap_intersection_of_succs (hoist_vbeout[bb->index],
-					   hoist_vbein, bb->index);
+	    {
+	      /* ??? Code hoisting algorithm from Muchnick seems to be
+		 overly conservative in considering only those expressions
+		 that are calculated along every path from BB.
+		 E.g., it will not try to optimize the following case:
+
+		  2
+                  | \
+		  3* |
+	          | /
+		  4
+                 / \
+                5*  6
+
+		 ;; "*" marks basic blocks that calculate same expression
+		 ;; Ideally, all calculation would be moved to block 2.
+
+		 One way to improve the algorith can be to exclude
+		 certain edges from intersection of successors' hoist_vbein's.
+
+		 E.g., if a basic block has a fallthru edge that the control
+		 takes with >80% probability, then just copy hoist_vbein
+		 of the destination block to hoist_vbeout of BB.  */
+	      sbitmap_intersection_of_succs (hoist_vbeout[bb->index],
+					     hoist_vbein, bb->index);
+
+	      /* ??? Another quirk of Muchnick is that vbeout[BB] does not
+		 include expressions calculated in BB itself and available
+		 at its end.  Fix this.  */
+	      sbitmap_a_or_b (hoist_vbeout[bb->index],
+			      hoist_vbeout[bb->index], comp[bb->index]);
+	    }
 
 	  changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index],
 					      antloc[bb->index],
 					      hoist_vbeout[bb->index],
 					      transp[bb->index]);
+
+	  /* Enable if debugging VBE data flow problem.  */
+	  if (dump_file && 0)
+	    {
+	      fprintf (dump_file, "vbein (%d): ", bb->index);
+	      dump_sbitmap_file (dump_file, hoist_vbein[bb->index]);
+	      fprintf (dump_file, "vbeout(%d): ", bb->index);
+	      dump_sbitmap_file (dump_file, hoist_vbeout[bb->index]);
+	    }
 	}
 
       passes++;
@@ -4298,6 +4337,11 @@ hoist_code (void)
 	  if (TEST_BIT (hoist_vbeout[bb->index], i)
 	      && TEST_BIT (transpout[bb->index], i))
 	    {
+	      /* If an expression is computed in BB and is available at end of
+		 BB, hoist all occurences dominated by BB to BB.  */
+	      if (TEST_BIT (comp[bb->index], i))
+		hoistable++;
+
 	      /* We've found a potentially hoistable expression, now
 		 we look at every block BB dominates to see if it
 		 computes the expression.  */