Patchwork [Version,2,RFA] Improving register pressure directed hoist

login
register
mail settings
Submitter Bin Cheng
Date Nov. 7, 2012, 9:05 p.m.
Message ID <008201cdbd2b$91850630$b48f1290$@cheng@arm.com>
Download mbox | patch
Permalink /patch/197806/
State New
Headers show

Comments

Bin Cheng - Nov. 7, 2012, 9:05 p.m.
> -----Original Message-----
> From: gcc-patches-owner@gcc.gnu.org [mailto:gcc-patches-owner@gcc.gnu.org]
On
> Behalf Of Bin Cheng
> Sent: Tuesday, November 06, 2012 9:04 PM
> To: 'Jeff Law'
> Cc: gcc-patches@gcc.gnu.org
> Subject: RE: [PATCH Version 2][RFA]Improving register pressure directed
hoist
> 
> 
> 
> > -----Original Message-----
> > From: Jeff Law [mailto:law@redhat.com]
> > Sent: Tuesday, November 06, 2012 4:51 AM
> > To: Bin Cheng
> > Cc: gcc-patches@gcc.gnu.org
> > Subject: Re: [PATCH Version 2][RFA]Improving register pressure
> > directed
> hoist
> >
> > On 11/02/2012 02:34 AM, Bin Cheng wrote:
> > >>
> > > Also I don't understand why the bogus patch can catch more hoist
> > > opportunities and improve code size, so please help if you have any
> > > idea about this.
> > Well, perturbing the code, particularly in a way which is supposed to
> change
> > the amount of register pressure is certainly going to affect the
> allocators
> > and reload.
> >
> > It shouldn't be that hard to look at results which differ between the
> > two patches and analyze why they're different.
> I will try to investigate this issue.
> 
> >
> > >
> > > 2012-11-02  Bin Cheng<bin.cheng@arm.com>
> > >
> > > 	* gcse.c: (struct bb_data): Add new fields, old_pressure, live_in
> > > 	and backup.
> > > 	(calculate_bb_reg_pressure): Initialize live_in and backup.
> > > 	(update_bb_reg_pressure): New.
> > > 	(should_hoist_expr_to_dom): Add new parameter from.
> > > 	Monitor the change of reg pressure and use it to drive hoisting.
> > > 	(hoist_code): Update LIVE and reg pressure information.
> > >
> > > gcc/testsuite/ChangeLog
> > > 2012-11-02  Bin Cheng<bin.cheng@arm.com>
> > >
> > > 	* gcc.dg/hoist-register-pressure-3.c: New test.
> > >
> > >
> > > +/* Update register pressure for BB when hoisting an expression from
> > > +   instruction FROM, if live ranges of inputs are shrunk.  Also
> > > +   maintain live_in information if live range of register referred
> > > +   in FROM is shrunk.
> > > +
> > > +   Return 0 if register pressure doesn't change, otherwise return
> > > +   the number by which register pressure is decreased.
> > > +
> > > +   NOTE: Register pressure won't be increased in this function.  */
> > > +
> > > +static int
> > > +update_bb_reg_pressure (basic_block bb, rtx from,
> > > +			enum reg_class pressure_class, int nregs) {
> > > +  rtx dreg, insn;
> > > +  basic_block succ_bb;
> > > +  df_ref *op, op_ref;
> > > +  edge succ;
> > > +  edge_iterator ei;
> > > +  int decreased_pressure = 0;
> > > +
> > > +  for (op = DF_INSN_USES (from); *op; op++)
> > > +    {
> > > +      dreg = DF_REF_REAL_REG (*op);
> > > +      /* The live range of register is shrunk only if it isn't:
> > > +	 1. referred on any path from the end of this block to EXIT, or
> > > +	 2. referred by insns other than FROM in this block.  */
> > > +      FOR_EACH_EDGE (succ, ei, bb->succs)
> > > +	{
> > > +	  succ_bb = succ->dest;
> > > +	  if (succ_bb == EXIT_BLOCK_PTR)
> > > +	    continue;
> > > +
> > > +	  if (bitmap_bit_p (BB_DATA (succ_bb)->live_in, REGNO (dreg)))
> > > +	    break;
> > > +	}
> > > +      if (succ != NULL)
> > > +	continue;
> > > +
> > > +      op_ref = DF_REG_USE_CHAIN (REGNO (dreg));
> > > +      for (; op_ref; op_ref = DF_REF_NEXT_REG (op_ref))
> > > +	{
> > > +	  if (!DF_REF_INSN_INFO (op_ref))
> > > +	    continue;
> > > +
> > > +	  insn = DF_REF_INSN (op_ref);
> > > +	  if (BLOCK_FOR_INSN (insn) == bb
> > > +	      && NONDEBUG_INSN_P (insn) && insn != from)
> > > +	    break;
> > > +	}
> > > +
> > > +      /* Decrease register pressure and update live_in information
for
> > > +	 this block.  */
> > > +      if (!op_ref)
> > > +	{
> > > +	  decreased_pressure += nregs;
> > > +	  BB_DATA (bb)->max_reg_pressure[pressure_class] -= nregs;
> > > +	  bitmap_clear_bit (BB_DATA (bb)->live_in, REGNO (dreg));
> > > +	}
> > > +    }
> > > +  return decreased_pressure;
> > So we're looking to see if any of the registers used in FROM are used
> after
> > from.  If none are used, then we decrease the register pressure by
> > nregs
> which
> > appears to be a property of the the registers *set* in FROM.
> >   Is seems like there's some inconsistency here.  Or have I
> > misunderstood something?
> >
> > I'm not sure how much it matters in practice, except perhaps for
> conversions
> > and the like where the source and destination operands are different
> modes.
> 
> Agreed, I missed the inconsistence of register_class/number between input
and
> output. I will fix this issue and measure the effect once I get back to
office.
> 

Hi Jeff,
I modified the patch updating reg_class/num of input registers, rather than
output register. The code size info collected shows no obvious change from
last patch.
Bootstrapped on x86, tested on x86-linux and arm-none-eabi/Thumb1. Is it OK?

Thanks


2012-11-08  Bin Cheng  <bin.cheng@arm.com>

	* gcse.c: (struct bb_data): Add new fields, old_pressure, live_in
	and backup.
	(calculate_bb_reg_pressure): Initialize live_in and backup.
	(update_bb_reg_pressure): New.
	(should_hoist_expr_to_dom): Add new parameter from.
	Monitor the change of reg pressure and use it to drive hoisting.
	(hoist_code): Update LIVE and reg pressure information.

gcc/testsuite/ChangeLog
2012-11-08  Bin Cheng  <bin.cheng@arm.com>

	* gcc.dg/hoist-register-pressure-3.c: New test.
Jeff Law - Nov. 9, 2012, 1:57 p.m.
On 11/07/2012 02:05 PM, Bin Cheng wrote:

> 2012-11-08  Bin Cheng  <bin.cheng@arm.com>
>
> 	* gcse.c: (struct bb_data): Add new fields, old_pressure, live_in
> 	and backup.
> 	(calculate_bb_reg_pressure): Initialize live_in and backup.
> 	(update_bb_reg_pressure): New.
> 	(should_hoist_expr_to_dom): Add new parameter from.
> 	Monitor the change of reg pressure and use it to drive hoisting.
> 	(hoist_code): Update LIVE and reg pressure information.
>
> gcc/testsuite/ChangeLog
> 2012-11-08  Bin Cheng  <bin.cheng@arm.com>
>
> 	* gcc.dg/hoist-register-pressure-3.c: New test.
Thanks for taking care of that inconsistency.  This is OK to install now.

Thanks,
jeff
Bin Cheng - Nov. 12, 2012, 2:25 a.m.
> -----Original Message-----
> From: Jeff Law [mailto:law@redhat.com]
> Sent: Friday, November 09, 2012 9:58 PM
> To: Bin Cheng
> Cc: gcc-patches@gcc.gnu.org
> Subject: Re: [PATCH Version 2][RFA]Improving register pressure directed
hoist
> 
> On 11/07/2012 02:05 PM, Bin Cheng wrote:
> 
> > 2012-11-08  Bin Cheng  <bin.cheng@arm.com>
> >
> > 	* gcse.c: (struct bb_data): Add new fields, old_pressure, live_in
> > 	and backup.
> > 	(calculate_bb_reg_pressure): Initialize live_in and backup.
> > 	(update_bb_reg_pressure): New.
> > 	(should_hoist_expr_to_dom): Add new parameter from.
> > 	Monitor the change of reg pressure and use it to drive hoisting.
> > 	(hoist_code): Update LIVE and reg pressure information.
> >
> > gcc/testsuite/ChangeLog
> > 2012-11-08  Bin Cheng  <bin.cheng@arm.com>
> >
> > 	* gcc.dg/hoist-register-pressure-3.c: New test.
> Thanks for taking care of that inconsistency.  This is OK to install now.

Hi Jeff & Jakub,
Thanks for reviewing.

I posted in the below message explaining that I want to include this patch
in GCC 4.8.
http://gcc.gnu.org/ml/gcc/2012-10/msg00471.html

Since it is approved now, I committed it as r193425 in TRUNK.

Thanks.

Patch

Index: gcc/testsuite/gcc.dg/hoist-register-pressure-3.c
===================================================================
--- gcc/testsuite/gcc.dg/hoist-register-pressure-3.c	(revision 0)
+++ gcc/testsuite/gcc.dg/hoist-register-pressure-3.c	(revision 0)
@@ -0,0 +1,32 @@ 
+/* { dg-options "-Os -fdump-rtl-hoist" }  */
+/* { dg-final { scan-rtl-dump "PRE/HOIST: end of bb .* copying expression" "hoist" } } */
+
+#define BUF 100
+int a[BUF];
+
+void com (int);
+void bar (int);
+
+int foo (int x, int y, int z)
+{
+  /* "x+y" won't be hoisted if "-fira-hoist-pressure" is disabled,
+     because its rtx_cost is too small.  */
+  if (z)
+    {
+      a[1] = a[0] + a[2] + a[3] + a[4] + a[5] + a[6];
+      a[2] = a[1] + a[3] + a[5] + a[5] + a[6] + a[7];
+      a[3] = a[2] + a[5] + a[7] + a[6] + a[7] + a[8];
+      a[4] = a[3] + a[7] + a[11] + a[7] + a[8] + a[9];
+      a[5] = a[5] + a[11] + a[13] + a[8] + a[9] + a[10];
+      a[6] = a[7] + a[13] + a[17] + a[9] + a[10] + a[11];
+      a[7] = a[11] + a[17] + a[19] + a[10] + a[11] + a[12];
+      com (x+y);
+    }
+  else
+    {
+      bar (x+y);
+    }
+
+  return 0;
+}
+
Index: gcc/gcse.c
===================================================================
--- gcc/gcse.c	(revision 193321)
+++ gcc/gcse.c	(working copy)
@@ -20,9 +20,6 @@  along with GCC; see the file COPYING3.  If not see
 
 /* TODO
    - reordering of memory allocation and freeing to be more space efficient
-   - simulate register pressure change of each basic block accurately during
-     hoist process.  But I doubt the benefit since most expressions hoisted
-     are constant or address, which usually won't reduce register pressure.
    - calc rough register pressure information and use the info to drive all
      kinds of code motion (including code hoisting) in a unified way.
 */
@@ -421,6 +418,15 @@  struct bb_data
   /* Maximal register pressure inside basic block for given register class
      (defined only for the pressure classes).  */
   int max_reg_pressure[N_REG_CLASSES];
+  /* Recorded register pressure of basic block before trying to hoist
+     an expression.  Will be used to restore the register pressure
+     if the expression should not be hoisted.  */
+  int old_pressure;
+  /* Recorded register live_in info of basic block during code hoisting
+     process.  BACKUP is used to record live_in info before trying to
+     hoist an expression, and will be used to restore LIVE_IN if the
+     expression should not be hoisted.  */
+  bitmap live_in, backup;
 };
 
 #define BB_DATA(bb) ((struct bb_data *) (bb)->aux)
@@ -481,8 +487,9 @@  static void compute_code_hoist_vbeinout (void);
 static void compute_code_hoist_data (void);
 static int should_hoist_expr_to_dom (basic_block, struct expr *, basic_block,
 				     sbitmap, int, int *, enum reg_class,
-				     int *, bitmap);
+				     int *, bitmap, rtx);
 static int hoist_code (void);
+static enum reg_class get_regno_pressure_class (int regno, int *nregs);
 static enum reg_class get_pressure_class_and_nregs (rtx insn, int *nregs);
 static int one_code_hoisting_pass (void);
 static rtx process_insert_insn (struct expr *);
@@ -2847,6 +2854,71 @@  compute_code_hoist_data (void)
     fprintf (dump_file, "\n");
 }
 
+/* Update register pressure for BB when hoisting an expression from
+   instruction FROM, if live ranges of inputs are shrunk.  Also
+   maintain live_in information if live range of register referred
+   in FROM is shrunk.
+   
+   Return 0 if register pressure doesn't change, otherwise return
+   the number by which register pressure is decreased.
+   
+   NOTE: Register pressure won't be increased in this function.  */
+
+static int
+update_bb_reg_pressure (basic_block bb, rtx from)
+{
+  rtx dreg, insn;
+  basic_block succ_bb;
+  df_ref *op, op_ref;
+  edge succ;
+  edge_iterator ei;
+  int decreased_pressure = 0;
+  int nregs;
+  enum reg_class pressure_class;
+  
+  for (op = DF_INSN_USES (from); *op; op++)
+    {
+      dreg = DF_REF_REAL_REG (*op);
+      /* The live range of register is shrunk only if it isn't:
+	 1. referred on any path from the end of this block to EXIT, or
+	 2. referred by insns other than FROM in this block.  */
+      FOR_EACH_EDGE (succ, ei, bb->succs)
+	{
+	  succ_bb = succ->dest;
+	  if (succ_bb == EXIT_BLOCK_PTR)
+	    continue;
+
+	  if (bitmap_bit_p (BB_DATA (succ_bb)->live_in, REGNO (dreg)))
+	    break;
+	}
+      if (succ != NULL)
+	continue;
+
+      op_ref = DF_REG_USE_CHAIN (REGNO (dreg));
+      for (; op_ref; op_ref = DF_REF_NEXT_REG (op_ref))
+	{
+	  if (!DF_REF_INSN_INFO (op_ref))
+	    continue;
+
+	  insn = DF_REF_INSN (op_ref);
+	  if (BLOCK_FOR_INSN (insn) == bb
+	      && NONDEBUG_INSN_P (insn) && insn != from)
+	    break;
+	}
+
+      pressure_class = get_regno_pressure_class (REGNO (dreg), &nregs);
+      /* Decrease register pressure and update live_in information for
+	 this block.  */
+      if (!op_ref && pressure_class != NO_REGS)
+	{
+	  decreased_pressure += nregs;
+	  BB_DATA (bb)->max_reg_pressure[pressure_class] -= nregs;
+	  bitmap_clear_bit (BB_DATA (bb)->live_in, REGNO (dreg));
+	}
+    }
+  return decreased_pressure;
+}
+
 /* Determine if the expression EXPR should be hoisted to EXPR_BB up in
    flow graph, if it can reach BB unimpared.  Stop the search if the
    expression would need to be moved more than DISTANCE instructions.
@@ -2863,6 +2935,8 @@  compute_code_hoist_data (void)
    HOISTED_BBS points to a bitmap indicating basic blocks through which
    EXPR is hoisted.
 
+   FROM is the instruction from which EXPR is hoisted.
+
    It's unclear exactly what Muchnick meant by "unimpared".  It seems
    to me that the expression must either be computed or transparent in
    *every* block in the path(s) from EXPR_BB to BB.  Any other definition
@@ -2877,28 +2951,54 @@  static int
 should_hoist_expr_to_dom (basic_block expr_bb, struct expr *expr,
 			  basic_block bb, sbitmap visited, int distance,
 			  int *bb_size, enum reg_class pressure_class,
-			  int *nregs, bitmap hoisted_bbs)
+			  int *nregs, bitmap hoisted_bbs, rtx from)
 {
   unsigned int i;
   edge pred;
   edge_iterator ei;
   sbitmap_iterator sbi;
   int visited_allocated_locally = 0;
+  int decreased_pressure = 0;
 
+  if (flag_ira_hoist_pressure)
+    {
+      /* Record old information of basic block BB when it is visited
+	 at the first time.  */
+      if (!bitmap_bit_p (hoisted_bbs, bb->index))
+	{
+	  struct bb_data *data = BB_DATA (bb);
+	  bitmap_copy (data->backup, data->live_in);
+	  data->old_pressure = data->max_reg_pressure[pressure_class];
+	}
+      decreased_pressure = update_bb_reg_pressure (bb, from);
+    }
   /* Terminate the search if distance, for which EXPR is allowed to move,
      is exhausted.  */
   if (distance > 0)
     {
-      /* Let EXPR be hoisted through basic block at no cost if the block
-	 has low register pressure.  An exception is constant expression,
-	 because hoisting constant expr aggressively results in worse code.
-	 The exception is made by the observation of CSiBE on ARM target,
-	 while it has no obvious effect on other targets like x86, x86_64,
-	 mips and powerpc.  */
-      if (!flag_ira_hoist_pressure
-	  || (BB_DATA (bb)->max_reg_pressure[pressure_class]
-		>= ira_class_hard_regs_num[pressure_class]
-	      || CONST_INT_P (expr->expr)))
+      if (flag_ira_hoist_pressure)
+	{
+	  /* Prefer to hoist EXPR if register pressure is decreased.  */
+	  if (decreased_pressure > *nregs)
+	    distance += bb_size[bb->index];
+	  /* Let EXPR be hoisted through basic block at no cost if one
+	     of following conditions is satisfied:
+
+	     1. The basic block has low register pressure.
+	     2. Register pressure won't be increases after hoisting EXPR.
+
+	     Constant expressions is handled conservatively, because
+	     hoisting constant expression aggressively results in worse
+	     code.  This decision is made by the observation of CSiBE
+	     on ARM target, while it has no obvious effect on other
+	     targets like x86, x86_64, mips and powerpc.  */
+	  else if (CONST_INT_P (expr->expr)
+		   || (BB_DATA (bb)->max_reg_pressure[pressure_class]
+			 >= ira_class_hard_regs_num[pressure_class]
+		       && decreased_pressure < *nregs))
+	    distance -= bb_size[bb->index];
+	}
+      else
 	distance -= bb_size[bb->index];
 
       if (distance <= 0)
@@ -2932,24 +3032,21 @@  should_hoist_expr_to_dom (basic_block expr_bb, str
 	  bitmap_set_bit (visited, pred_bb->index);
 	  if (! should_hoist_expr_to_dom (expr_bb, expr, pred_bb,
 					  visited, distance, bb_size,
-					  pressure_class, nregs, hoisted_bbs))
+					  pressure_class, nregs,
+					  hoisted_bbs, from))
 	    break;
 	}
     }
   if (visited_allocated_locally)
     {
       /* If EXPR can be hoisted to expr_bb, record basic blocks through
-	 which EXPR is hoisted in hoisted_bbs.  Also update register
-	 pressure for basic blocks newly added in hoisted_bbs.  */
+	 which EXPR is hoisted in hoisted_bbs.  */
       if (flag_ira_hoist_pressure && !pred)
 	{
+	  /* Record the basic block from which EXPR is hoisted.  */
+	  bitmap_set_bit (visited, bb->index);
 	  EXECUTE_IF_SET_IN_BITMAP (visited, 0, i, sbi)
-	    if (!bitmap_bit_p (hoisted_bbs, i))
-	      {
-		bitmap_set_bit (hoisted_bbs, i);
-		BB_DATA (BASIC_BLOCK (i))->max_reg_pressure[pressure_class]
-		    += *nregs;
-	      }
+	    bitmap_set_bit (hoisted_bbs, i);
 	}
       sbitmap_free (visited);
     }
@@ -2990,23 +3087,28 @@  find_occr_in_bb (struct occr *occr, basic_block bb
    from rtx cost of the corresponding expression and it's used to control
    how long the expression can be hoisted up in flow graph.  As the
    expression is hoisted up in flow graph, GCC decreases its DISTANCE
-   and stops the hoist if DISTANCE reaches 0.
+   and stops the hoist if DISTANCE reaches 0.  Code hoisting can decrease
+   register pressure if live ranges of inputs are shrunk.
 
    Option "-fira-hoist-pressure" implements register pressure directed
    hoist based on upper method.  The rationale is:
      1. Calculate register pressure for each basic block by reusing IRA
 	facility.
      2. When expression is hoisted through one basic block, GCC checks
-	register pressure of the basic block and decrease DISTANCE only
-	when the register pressure is high.  In other words, expression
-	will be hoisted through basic block with low register pressure
-	at no cost.
-     3. Update register pressure information for basic blocks through
- 	which expression is hoisted.
-	TODO: It is possible to have register pressure decreased because
-	of shrinked live ranges of input pseudo registers when hoisting
-	an expression.  For now, this effect is not simulated and we just
-	increase register pressure for hoisted expressions.  */
+	the change of live ranges for inputs/output.  The basic block's
+	register pressure will be increased because of extended live
+	range of output.  However, register pressure will be decreased
+	if the live ranges of inputs are shrunk.
+     3. After knowing how hoisting affects register pressure, GCC prefers
+	to hoist the expression if it can decrease register pressure, by
+	increasing DISTANCE of the corresponding expression.
+     4. If hoisting the expression increases register pressure, GCC checks
+	register pressure of the basic block and decrease DISTANCE only if
+	the register pressure is high.  In other words, expression will be
+	hoisted through at no cost if the basic block has low register
+	pressure.
+     5. Update register pressure information for basic blocks through
+	which expression is hoisted.  */
 
 static int
 hoist_code (void)
@@ -3163,7 +3265,7 @@  hoist_code (void)
 		  if (should_hoist_expr_to_dom (bb, expr, dominated, NULL,
 						max_distance, bb_size,
 						pressure_class,	&nregs,
-						hoisted_bbs))
+						hoisted_bbs, occr->insn))
 		    {
 		      hoistable++;
 		      VEC_safe_push (occr_t, heap,
@@ -3207,19 +3309,28 @@  hoist_code (void)
 	      if (flag_ira_hoist_pressure
 		  && !VEC_empty (occr_t, occrs_to_hoist))
 		{
-		  /* Update register pressure for basic block to which expr
-		     is hoisted.  */
+		  /* Increase register pressure of basic blocks to which
+		     expr is hoisted because of extended live range of
+		     output.  */
 		  data = BB_DATA (bb);
 		  data->max_reg_pressure[pressure_class] += nregs;
+		  EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs, 0, k, bi)
+		    {
+		      data = BB_DATA (BASIC_BLOCK (k));
+		      data->max_reg_pressure[pressure_class] += nregs;
+		    }
 		}
 	      else if (flag_ira_hoist_pressure)
 		{
-		  /* Restore register pressure of basic block recorded in
-		     hoisted_bbs when expr will not be hoisted.  */
+		  /* Restore register pressure and live_in info for basic
+		     blocks recorded in hoisted_bbs when expr will not be
+		     hoisted.  */
 		  EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs, 0, k, bi)
 		    {
 		      data = BB_DATA (BASIC_BLOCK (k));
-		      data->max_reg_pressure[pressure_class] -= nregs;
+		      bitmap_copy (data->live_in, data->backup);
+		      data->max_reg_pressure[pressure_class]
+			  = data->old_pressure;
 		    }
 		}
 
@@ -3382,7 +3493,10 @@  calculate_bb_reg_pressure (void)
   FOR_EACH_BB (bb)
     {
       curr_bb = bb;
-      bitmap_copy (curr_regs_live, DF_LR_OUT (bb));
+      BB_DATA (bb)->live_in = BITMAP_ALLOC (NULL);
+      BB_DATA (bb)->backup = BITMAP_ALLOC (NULL);
+      bitmap_copy (BB_DATA (bb)->live_in, df_get_live_in (bb));
+      bitmap_copy (curr_regs_live, df_get_live_out (bb));
       for (i = 0; i < ira_pressure_classes_num; i++)
 	curr_reg_pressure[ira_pressure_classes[i]] = 0;
       EXECUTE_IF_SET_IN_BITMAP (curr_regs_live, 0, j, bi)