shrink-wrap: Improve spread_components (PR85645)

In the testcase for PR85645 we do a pretty dumb placement of the
prologue/epilogue for the LR component: we place an epilogue for LR
before a control flow split where one of the branches clobbers LR
eventually, and the other does not.  The branch that does clobber it
will need a prologue again some time later.  Because saving and
restoring LR is a two step process---it needs to be moved via a GPR---
the backend emits CFI directives so that we get correct unwind
information.  But both regcprop and regrename do not properly handle
such CFI directives leading to ICEs.

Now, neither of the two branches needs to have LR restored at all,
because both of the branches end up in an infinite loop.

This patch makes spread_component return a boolean saying if anything
was changed, and if so, it is called again.  This obviously is finite
(there is a finite number of basic blocks, each with a finite number
of components, and spread_components can only assign more components
to a block, never less).  I also instrumented the code, and on a
bootstrap+regtest spread_components made changes a maximum of two
times.  Interestingly though it made changes on two iterations in
a third of the cases it did anything at all!


	PR rtl-optimization/85645
	* shrink-wrap.c (spread_components): Return a boolean saying if
	anything was changed.
	(try_shrink_wrapping_separate): Iterate spread_components until
	nothing changes anymore.

From-SVN: r260076

2 files changed, 30 insertions, 3 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 72e6768..1c81e4f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,6 +1,14 @@
 2018-05-09  Segher Boessenkool  <segher@kernel.crashing.org>
 
 	PR rtl-optimization/85645
+	* shrink-wrap.c (spread_components): Return a boolean saying if
+	anything was changed.
+	(try_shrink_wrapping_separate): Iterate spread_components until
+	nothing changes anymore.
+
+2018-05-09  Segher Boessenkool  <segher@kernel.crashing.org>
+
+	PR rtl-optimization/85645
 	* regrename.c (build_def_use): Also kill the chains that include the
 	destination of a REG_CFA_REGISTER note.
 
diff --git a/gcc/shrink-wrap.c b/gcc/shrink-wrap.c
index 6b47d4e..1ad7379 100644
--- a/gcc/shrink-wrap.c
+++ b/gcc/shrink-wrap.c
@@ -1253,8 +1253,9 @@ place_prologue_for_one_component (unsigned int which, basic_block head)
 /* Set HAS_COMPONENTS in every block to the maximum it can be set to without
    setting it on any path from entry to exit where it was not already set
    somewhere (or, for blocks that have no path to the exit, consider only
-   paths from the entry to the block itself).  */
-static void
+   paths from the entry to the block itself).  Return whether any changes
+   were made to some HAS_COMPONENTS.  */
+static bool
 spread_components (sbitmap components)
 {
   basic_block entry_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
@@ -1377,12 +1378,19 @@ spread_components (sbitmap components)
 
   /* Finally, mark everything not not needed both forwards and backwards.  */
 
+  bool did_changes = false;
+
   FOR_EACH_BB_FN (bb, cfun)
     {
+      bitmap_copy (old, SW (bb)->has_components);
+
       bitmap_and (SW (bb)->head_components, SW (bb)->head_components,
 		  SW (bb)->tail_components);
       bitmap_and_compl (SW (bb)->has_components, components,
 			SW (bb)->head_components);
+
+      if (!did_changes && !bitmap_equal_p (old, SW (bb)->has_components))
+	did_changes = true;
     }
 
   FOR_ALL_BB_FN (bb, cfun)
@@ -1394,6 +1402,8 @@ spread_components (sbitmap components)
 	  fprintf (dump_file, "\n");
 	}
     }
+
+  return did_changes;
 }
 
 /* If we cannot handle placing some component's prologues or epilogues where
@@ -1797,7 +1807,16 @@ try_shrink_wrapping_separate (basic_block first_bb)
   EXECUTE_IF_SET_IN_BITMAP (components, 0, j, sbi)
     place_prologue_for_one_component (j, first_bb);
 
-  spread_components (components);
+  /* Try to minimize the number of saves and restores.  Do this as long as
+     it changes anything.  This does not iterate more than a few times.  */
+  int spread_times = 0;
+  while (spread_components (components))
+    {
+      spread_times++;
+
+      if (dump_file)
+	fprintf (dump_file, "Now spread %d times.\n", spread_times);
+    }
 
   disqualify_problematic_components (components);