Patchwork [PR,10474] Split live-ranges of function arguments to help shrink-wrapping

login
register
mail settings
Submitter Martin Jambor
Date Oct. 23, 2013, 4:46 p.m.
Message ID <20131023164630.GB22314@virgil.suse>
Download mbox | patch
Permalink /patch/285710/
State New
Headers show

Comments

Martin Jambor - Oct. 23, 2013, 4:46 p.m.
Hi,

On Mon, Oct 21, 2013 at 11:00:38PM -0400, Vladimir Makarov wrote:
> On 13-10-21 6:56 PM, Steven Bosscher wrote:
> >
> >+       {
> >+         bitmap_clear (&need_new);
> >+         bitmap_clear (&reachable);
> >+         return;
> >+       }
> >+
> >+      for (df_ref use = DF_REG_USE_CHAIN (REGNO(dest));
> >+          use;
> >+          use = DF_REF_NEXT_REG (use))
> >You're using DF in these places. But IRA and LRA don't work with DF.
> >After update_equiv_regs DF caches and liveness may be incorrect. You'd
> >have to add a df_analyze call but I'm not sure how that will interact
> >with IRA/LRA's own dataflow frameworks (e.g. w.r.t.
> >REG_DEAD/REG_UNUSED notes).
> >
> >
> Sorry, Martin.  I think Steven is right.  IRA/LRA (and reload pass)
> creates so many changes in RTL that DF infrastructure would slow
> down the compiler a lot and therefore df info is not updated during
> RA.

no need to be sorry, I absolutely anticipated comments and requests
for changes.

>  Your patch mostly uses a correct DF-info because there are few
> changes since updating is off.

I think the reason why it works is that find_moveable_pseudos, which
is called immediately before the function I'm adding, already calls
df_analyze.  I suppose it does not cause any trouble since the call is
there for quite a few months already.  Because find_moveable_pseudos
will never split registers which are defined by a set from a hard
register (because rtx_moveable_p returns false for a HARD_REGISTER_P),
the analysis results should still be perfectly up-to-date for the
purposes of my transformation.

So, do you think that this could be just made more explicit by moving
the call to df_analyze (and dominator calculation) out of
find_moveable_pseudos to ira() as in the (bootstrapped, tested) patch
below?

> You could move your optimization a bit up before df_clear_flags
> (DF_NO_INSN_RESCAN); or move this call right after your
> optimizations (possibly some minor df calls are needed too to
> restore live info for RA after your RTL changes).

I tried this but got dark glibc double free and segfault errors from
deep down in the call to df_analyze in find_moveable_pseudos, so I
quickly chickened out.  I will re-try (or even move the transformation
more up front) if you or Steven reject this attempt.

Thanks,

Martin


2013-10-23  Martin Jambor  <mjambor@suse.cz>

	PR rtl-optimization/10474
	* ira.c (find_moveable_pseudos): Do not calculate dominance info
	nor df analysis.
	(interesting_dest_for_shprep): New function.
	(split_live_ranges_for_shrink_wrap): Likewise.
	(ira): Calculate dominance info and df analysis. Call
	split_live_ranges_for_shrink_wrap.

testsuite/
	* gcc.dg/pr10474.c: New testcase.
	* gcc.dg/ira-shrinkwrap-prep-1.c: Likewise.
	* gcc.dg/ira-shrinkwrap-prep-2.c: Likewise.
Steven Bosscher - Oct. 23, 2013, 11:02 p.m.
On Wed, Oct 23, 2013 at 6:46 PM, Martin Jambor wrote:

>  /* Perform the second half of the transformation started in
> @@ -4522,7 +4704,15 @@ ira (FILE *f)
>       allocation because of -O0 usage or because the function is too
>       big.  */
>    if (ira_conflicts_p)
> -    find_moveable_pseudos ();
> +    {
> +      df_analyze ();
> +      calculate_dominance_info (CDI_DOMINATORS);
> +
> +      find_moveable_pseudos ();
> +      split_live_ranges_for_shrink_wrap ();
> +
> +      free_dominance_info (CDI_DOMINATORS);
> +    }
>

You probably want to add another df_analyze if
split_live_ranges_for_shrink_wrap makes code transformations. AFAIU
find_moveable_pseudos doesn't change global liveness but your
transformation might. IRA/LRA need up-to-date DF_LR results to compute
allocno live ranges.

Ciao!
Steven

Patch

diff --git a/gcc/ira.c b/gcc/ira.c
index 203fbff..0faea8f 100644
--- a/gcc/ira.c
+++ b/gcc/ira.c
@@ -3989,9 +3989,6 @@  find_moveable_pseudos (void)
   pseudo_replaced_reg.release ();
   pseudo_replaced_reg.safe_grow_cleared (max_regs);
 
-  df_analyze ();
-  calculate_dominance_info (CDI_DOMINATORS);
-
   i = 0;
   bitmap_initialize (&live, 0);
   bitmap_initialize (&used, 0);
@@ -4311,7 +4308,192 @@  find_moveable_pseudos (void)
   regstat_free_ri ();
   regstat_init_n_sets_and_refs ();
   regstat_compute_ri ();
-  free_dominance_info (CDI_DOMINATORS);
+}
+
+
+/* If insn is interesting for parameter range-splitting shring-wrapping
+   preparation, i.e. it is a single set from a hard register to a pseudo, which
+   is live at CALL_DOM, return the destination.  Otherwise return NULL.  */
+
+static rtx
+interesting_dest_for_shprep (rtx insn, basic_block call_dom)
+{
+  rtx set = single_set (insn);
+  if (!set)
+    return NULL;
+  rtx src = SET_SRC (set);
+  rtx dest = SET_DEST (set);
+  if (!REG_P (src) || !HARD_REGISTER_P (src)
+      || !REG_P (dest) || HARD_REGISTER_P (dest)
+      || (call_dom && !bitmap_bit_p (df_get_live_in (call_dom), REGNO (dest))))
+    return NULL;
+  return dest;
+}
+
+/* Split live ranges of pseudos that are loaded from hard registers in the
+   first BB in a BB that dominates all non-sibling call if such a BB can be
+   found and is not in a loop.  */
+
+static void
+split_live_ranges_for_shrink_wrap (void)
+{
+  basic_block bb, call_dom = NULL;
+  basic_block first = single_succ (ENTRY_BLOCK_PTR);
+  rtx insn, last_interesting_insn = NULL;
+  bitmap_head need_new, reachable;
+  vec<basic_block> queue;
+
+  if (!flag_shrink_wrap)
+    return;
+
+  bitmap_initialize (&need_new, 0);
+  bitmap_initialize (&reachable, 0);
+  queue.create (n_basic_blocks);
+
+  FOR_EACH_BB (bb)
+    FOR_BB_INSNS (bb, insn)
+      if (CALL_P (insn) && !SIBLING_CALL_P (insn))
+	{
+	  if (bb == first)
+	    {
+	      bitmap_clear (&need_new);
+	      bitmap_clear (&reachable);
+	      queue.release ();
+	      return;
+	    }
+
+	  bitmap_set_bit (&need_new, bb->index);
+	  bitmap_set_bit (&reachable, bb->index);
+	  queue.quick_push (bb);
+	  break;
+	}
+
+  if (queue.is_empty ())
+    {
+      bitmap_clear (&need_new);
+      bitmap_clear (&reachable);
+      queue.release ();
+      return;
+    }
+
+  while (!queue.is_empty ())
+    {
+      edge e;
+      edge_iterator ei;
+
+      bb = queue.pop ();
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	if (e->dest != EXIT_BLOCK_PTR
+	    && bitmap_set_bit (&reachable, e->dest->index))
+	  queue.quick_push (e->dest);
+    }
+  queue.release ();
+
+  FOR_BB_INSNS (first, insn)
+    {
+      rtx dest = interesting_dest_for_shprep (insn, NULL);
+      if (!dest)
+	continue;
+
+      if (DF_REG_DEF_COUNT (REGNO (dest)) > 1)
+	{
+	  bitmap_clear (&need_new);
+	  bitmap_clear (&reachable);
+	  return;
+	}
+
+      for (df_ref use = DF_REG_USE_CHAIN (REGNO(dest));
+	   use;
+	   use = DF_REF_NEXT_REG (use))
+	{
+	  if (NONDEBUG_INSN_P (DF_REF_INSN (use))
+	      && GET_CODE (DF_REF_REG (use)) == SUBREG)
+	    {
+	      /* This is necessary to avoid hitting an assert at
+		 postreload.c:2294 in libstc++ testcases on x86_64-linux.  I'm
+		 not really sure what the probblem actually is there.  */
+	      bitmap_clear (&need_new);
+	      bitmap_clear (&reachable);
+	      return;
+	    }
+
+	  int ubbi = DF_REF_BB (use)->index;
+	  if (bitmap_bit_p (&reachable, ubbi))
+	    bitmap_set_bit (&need_new, ubbi);
+	}
+      last_interesting_insn = insn;
+    }
+
+  bitmap_clear (&reachable);
+  if (!last_interesting_insn)
+    {
+      bitmap_clear (&need_new);
+      return;
+    }
+
+  call_dom = nearest_common_dominator_for_set (CDI_DOMINATORS, &need_new);
+  bitmap_clear (&need_new);
+  if (call_dom == first)
+    return;
+
+  loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
+  while (bb_loop_depth (call_dom) > 0)
+    call_dom = get_immediate_dominator (CDI_DOMINATORS, call_dom);
+  loop_optimizer_finalize ();
+
+  if (call_dom == first)
+    return;
+
+  calculate_dominance_info (CDI_POST_DOMINATORS);
+  if (dominated_by_p (CDI_POST_DOMINATORS, first, call_dom))
+    {
+      free_dominance_info (CDI_POST_DOMINATORS);
+      return;
+    }
+  free_dominance_info (CDI_POST_DOMINATORS);
+
+  if (dump_file)
+    fprintf (dump_file, "Will split live ranges of parameters at BB %i\n",
+	     call_dom->index);
+
+  FOR_BB_INSNS (first, insn)
+    {
+      rtx dest = interesting_dest_for_shprep (insn, call_dom);
+      if (!dest)
+	continue;
+
+      rtx newreg = NULL_RTX;
+      df_ref use, next;
+      for (use = DF_REG_USE_CHAIN (REGNO(dest)); use; use = next)
+	{
+	  rtx uin = DF_REF_INSN (use);
+	  next = DF_REF_NEXT_REG (use);
+
+	  basic_block ubb = BLOCK_FOR_INSN (uin);
+	  if (ubb == call_dom
+	      || dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
+	    {
+	      if (!newreg)
+		newreg = ira_create_new_reg (dest);
+	      validate_change (uin, DF_REF_LOC (use), newreg, true);
+	    }
+	}
+
+      if (newreg)
+	{
+	  rtx new_move = gen_move_insn (newreg, dest);
+	  emit_insn_after (new_move, bb_note (call_dom));
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "Split live-range of register ");
+	      print_rtl_single (dump_file, dest);
+	    }
+	}
+
+      if (insn == last_interesting_insn)
+	break;
+    }
+  apply_change_group ();
 }
 
 /* Perform the second half of the transformation started in
@@ -4522,7 +4704,15 @@  ira (FILE *f)
      allocation because of -O0 usage or because the function is too
      big.  */
   if (ira_conflicts_p)
-    find_moveable_pseudos ();
+    {
+      df_analyze ();
+      calculate_dominance_info (CDI_DOMINATORS);
+
+      find_moveable_pseudos ();
+      split_live_ranges_for_shrink_wrap ();
+
+      free_dominance_info (CDI_DOMINATORS);
+    }
 
   max_regno_before_ira = max_reg_num ();
   ira_setup_eliminable_regset (true);
diff --git a/gcc/testsuite/gcc.dg/ira-shrinkwrap-prep-1.c b/gcc/testsuite/gcc.dg/ira-shrinkwrap-prep-1.c
new file mode 100644
index 0000000..fe497c2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ira-shrinkwrap-prep-1.c
@@ -0,0 +1,31 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-rtl-ira -fdump-rtl-pro_and_epilogue"  } */
+
+int __attribute__((noinline, noclone))
+foo (int a)
+{
+  return a + 5;
+}
+
+static int g;
+
+int __attribute__((noinline, noclone))
+bar (int a)
+{
+  int r;
+
+  if (a)
+    {
+      r = foo (a);
+      g = r + a;
+    }
+  else
+    r = a+1;
+  return r;
+}
+
+/* { dg-final { scan-rtl-dump "Will split live ranges of parameters" "ira"  } } */
+/* { dg-final { scan-rtl-dump "Split live-range of register" "ira"  } } */
+/* { dg-final { scan-rtl-dump "Performing shrink-wrapping" "pro_and_epilogue"  } } */
+/* { dg-final { cleanup-rtl-dump "ira" } } */
+/* { dg-final { cleanup-rtl-dump "pro_and_epilogue" } } */
diff --git a/gcc/testsuite/gcc.dg/ira-shrinkwrap-prep-2.c b/gcc/testsuite/gcc.dg/ira-shrinkwrap-prep-2.c
new file mode 100644
index 0000000..872a757
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ira-shrinkwrap-prep-2.c
@@ -0,0 +1,36 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-rtl-ira -fdump-rtl-pro_and_epilogue"  } */
+
+int __attribute__((noinline, noclone))
+foo (int a)
+{
+  return a + 5;
+}
+
+static int g;
+
+int __attribute__((noinline, noclone))
+bar (int a)
+{
+  int r;
+
+  if (a)
+    {
+      r = a;
+      while (r < 500)
+	if (r % 2)
+	  r = foo (r);
+	else
+	  r = foo (r+1);
+      g = r + a;
+    }
+  else
+    r = g+1;
+  return r;
+}
+
+/* { dg-final { scan-rtl-dump "Will split live ranges of parameters" "ira"  } } */
+/* { dg-final { scan-rtl-dump "Split live-range of register" "ira"  } } */
+/* { dg-final { scan-rtl-dump "Performing shrink-wrapping" "pro_and_epilogue"  } } */
+/* { dg-final { cleanup-rtl-dump "ira" } } */
+/* { dg-final { cleanup-rtl-dump "pro_and_epilogue" } } */
diff --git a/gcc/testsuite/gcc.dg/pr10474.c b/gcc/testsuite/gcc.dg/pr10474.c
new file mode 100644
index 0000000..ee085c3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr10474.c
@@ -0,0 +1,16 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-rtl-pro_and_epilogue"  } */
+
+void f(int *i)
+{
+	if (!i)
+		return;
+	else
+	{
+		__builtin_printf("Hi");
+		*i=0;
+	}
+}
+
+/* { dg-final { scan-rtl-dump "Performing shrink-wrapping" "pro_and_epilogue"  } } */
+/* { dg-final { cleanup-rtl-dump "pro_and_epilogue" } } */