Patch to fix PR83712

[Vladimir Makarov]

  This is one more try to fix PR83712:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83712

  The patch was successfully bootstrapped and tested on x86-64, i686, 
and ppc64.


  Committed as rev. 258504.

Index: ChangeLog
===
--- ChangeLog	(revision 258503)
+++ ChangeLog	(working copy)
@@ -1,3 +1,25 @@
+2018-03-13  Vladimir Makarov  
+
+	PR target/83712
+	* lra-assigns.c (find_all_spills_for): Ignore uninteresting
+	pseudos.
+	(assign_by_spills): Return a flag of reload assignment failure.
+	Do not process the reload assignment failures.  Do not spill other
+	reload pseudos if they has the same reg class.  Update n if
+	necessary.
+	(lra_assign): Add a return arg.  Set up from the result of
+	assign_by_spills call.
+	(find_reload_regno_insns, lra_split_hard_reg_for): New functions.
+	* lra-constraints.c (split_reg): Add a new arg.  Use it instead of
+	usage_insns if it is not NULL.
+	(spill_hard_reg_in_range): New function.
+	(split_if_necessary, inherit_in_ebb): Pass a new arg to split_reg.
+	* lra-int.h (spill_hard_reg_in_range, lra_split_hard_reg_for): New
+	function prototypes.
+	(lra_assign): Change prototype.
+	* lra.c (lra): Add code to deal with fails by splitting hard reg
+	live ranges.
+
 2018-03-01  Palmer Dabbelt  
 
 	* config/riscv/riscv.opt (mrelax): New option.
Index: lra-assigns.c
===
--- lra-assigns.c	(revision 258482)
+++ lra-assigns.c	(working copy)
@@ -1339,24 +1339,33 @@ find_all_spills_for (int regno)
 	   r2 = r2->start_next)
 	{
 	  if (live_pseudos_reg_renumber[r2->regno] >= 0
-		  && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
+		  && ! sparseset_bit_p (live_range_hard_reg_pseudos, r2->regno)
+		  && rclass_intersect_p[regno_allocno_class_array[r2->regno]]
+		  && ((int) r2->regno < lra_constraint_new_regno_start
+		  || bitmap_bit_p (_inheritance_pseudos, r2->regno)
+		  || bitmap_bit_p (_split_regs, r2->regno)
+		  || bitmap_bit_p (_optional_reload_pseudos, r2->regno)
+		  /* There is no sense to consider another reload
+			 pseudo if it has the same class.  */
+		  || regno_allocno_class_array[r2->regno] != rclass))
 		sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
 	}
 	}
 }
 }
 
-/* Assign hard registers to reload pseudos and other pseudos.  */
-static void
+/* Assign hard registers to reload pseudos and other pseudos.  Return
+   true if we was not able to assign hard registers to all reload
+   pseudos.  */
+static bool
 assign_by_spills (void)
 {
-  int i, n, nfails, iter, regno, hard_regno, cost;
+  int i, n, nfails, iter, regno, regno2, hard_regno, cost;
   rtx restore_rtx;
-  rtx_insn *insn;
   bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
   unsigned int u, conflict_regno;
   bitmap_iterator bi;
-  bool reload_p;
+  bool reload_p, fails_p = false;
   int max_regno = max_reg_num ();
 
   for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
@@ -1399,8 +1408,13 @@ assign_by_spills (void)
 	hard_regno = spill_for (regno, _spilled_pseudos, iter == 1);
 	  if (hard_regno < 0)
 	{
-	  if (reload_p)
+	  if (reload_p) {
+		/* Put unassigned reload pseudo first in the
+		   array.  */
+		regno2 = sorted_pseudos[nfails];
 		sorted_pseudos[nfails++] = regno;
+		sorted_pseudos[i] = regno2;
+	  }
 	}
 	  else
 	{
@@ -1415,61 +1429,9 @@ assign_by_spills (void)
 		bitmap_set_bit (_pseudo_bitmap, regno);
 	}
 	}
-  if (nfails == 0)
-	break;
-  if (iter > 0)
+  if (nfails == 0 || iter > 0)
 	{
-	  /* We did not assign hard regs to reload pseudos after two iterations.
-	 Either it's an asm and something is wrong with the constraints, or
-	 we have run out of spill registers; error out in either case.  */
-	  bool asm_p = false;
-	  bitmap_head failed_reload_insns;
-
-	  bitmap_initialize (_reload_insns, _obstack);
-	  for (i = 0; i < nfails; i++)
-	{
-	  regno = sorted_pseudos[i];
-	  bitmap_ior_into (_reload_insns,
-			   _reg_info[regno].insn_bitmap);
-	  /* Assign an arbitrary hard register of regno class to
-		 avoid further trouble with this insn.  */
-	  bitmap_clear_bit (_spilled_pseudos, regno);
-	  assign_hard_regno
-		(ira_class_hard_regs[regno_allocno_class_array[regno]][0],
-		 regno);
-	}
-	  EXECUTE_IF_SET_IN_BITMAP (_reload_insns, 0, u, bi)
-	{
-	  insn = lra_insn_recog_data[u]->insn;
-	  if (asm_noperands (PATTERN (insn)) >= 0)
-		{
-		  asm_p = true;
-		  error_for_asm (insn,
- "% operand has impossible constraints");
-		  /* Avoid further trouble with this insn.
-		 For asm goto, instead of fixing up all the edges
-		 just clear the template and clear input operands
-		 (asm goto doesn't have any output operands).  */
-		  if (JUMP_P (insn))
-		{
-		  rtx asm_op = extract_asm_operands 

Re: patch to fix PR83712

[Jeff Law]

On 03/10/2018 09:40 AM, Vladimir Makarov wrote:
> A few people reported that the patch broke i686.  I am going to work on
> the patch more.  Meanwhile I've reverted the patch.
Just a note, none of my other builds failed.  Though i686 probably
stresses the class-likely-spilled bits than any other.

jeff

Re: patch to fix PR83712

[Vladimir Makarov]

A few people reported that the patch broke i686.  I am going to work on 
the patch more.  Meanwhile I've reverted the patch.


On 03/09/2018 11:16 AM, Vladimir Makarov wrote:

The following patch fixes

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83712

It is another "cannot find a spill reg for reload" problem.  LRA has 
already a code splitting hard reg live ranges to avoid such problem.  
This code is in LRA inheritance pass.  Unfortunately, the code does 
splitting for small class pseudos only.  This PR is a more complicated 
code and it is hard to adapt the inheritance sub-pass to reliably 
solve such problems.


To fix the PR, I added a sub-pass which works in very rare cases after 
we already found that we have no hard regs for a reload pseudo.  It 
tries to split a hard reg live range for the pseudo. After that it 
tries again to assign a hard reg to the pseudo.  The patch changes 
LRA-subpass flow for this.  I hope that the patch will finally solved 
all such problems but I am not sure to be completely certain.


The patch was bootstrapped and tested on x86-64 and ppc64.

Committed as rev. 258390.

Re: patch to fix PR83712

[H.J. Lu]

On Fri, Mar 9, 2018 at 8:16 AM, Vladimir Makarov  wrote:
> The following patch fixes
>
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83712
>
> It is another "cannot find a spill reg for reload" problem.  LRA has already
> a code splitting hard reg live ranges to avoid such problem.  This code is
> in LRA inheritance pass.  Unfortunately, the code does splitting for small
> class pseudos only.  This PR is a more complicated code and it is hard to
> adapt the inheritance sub-pass to reliably solve such problems.
>
> To fix the PR, I added a sub-pass which works in very rare cases after we
> already found that we have no hard regs for a reload pseudo.  It tries to
> split a hard reg live range for the pseudo. After that it tries again to
> assign a hard reg to the pseudo.  The patch changes LRA-subpass flow for
> this.  I hope that the patch will finally solved all such problems but I am
> not sure to be completely certain.
>
> The patch was bootstrapped and tested on x86-64 and ppc64.
>
> Committed as rev. 258390.
>

This caused:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84806

-- 
H.J.

Re: patch to fix PR83712

[Jeff Law]

On 03/09/2018 09:16 AM, Vladimir Makarov wrote:
> The following patch fixes
> 
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83712
> 
> It is another "cannot find a spill reg for reload" problem.  LRA has
> already a code splitting hard reg live ranges to avoid such problem. 
> This code is in LRA inheritance pass.  Unfortunately, the code does
> splitting for small class pseudos only.  This PR is a more complicated
> code and it is hard to adapt the inheritance sub-pass to reliably solve
> such problems.
> 
> To fix the PR, I added a sub-pass which works in very rare cases after
> we already found that we have no hard regs for a reload pseudo.  It
> tries to split a hard reg live range for the pseudo. After that it tries
> again to assign a hard reg to the pseudo.  The patch changes LRA-subpass
> flow for this.  I hope that the patch will finally solved all such
> problems but I am not sure to be completely certain.
> 
> The patch was bootstrapped and tested on x86-64 and ppc64.
Thanks.  Once my builders pick up the change (a few hours) we'll have
wider test coverage.  I can also test the change against a closely
related regression BZ (I don't have the number handy, but it's a few
years old and is definitely related).

Jeff

patch to fix PR83712

[Vladimir Makarov]

The following patch fixes

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83712

It is another "cannot find a spill reg for reload" problem.  LRA has 
already a code splitting hard reg live ranges to avoid such problem.  
This code is in LRA inheritance pass.  Unfortunately, the code does 
splitting for small class pseudos only.  This PR is a more complicated 
code and it is hard to adapt the inheritance sub-pass to reliably solve 
such problems.


To fix the PR, I added a sub-pass which works in very rare cases after 
we already found that we have no hard regs for a reload pseudo.  It 
tries to split a hard reg live range for the pseudo. After that it tries 
again to assign a hard reg to the pseudo.  The patch changes LRA-subpass 
flow for this.  I hope that the patch will finally solved all such 
problems but I am not sure to be completely certain.


The patch was bootstrapped and tested on x86-64 and ppc64.

Committed as rev. 258390.

Index: ChangeLog
===
--- ChangeLog	(revision 258389)
+++ ChangeLog	(working copy)
@@ -1,3 +1,23 @@
+2018-03-09  Vladimir Makarov  
+
+	PR target/83712
+	* lra-assigns.c (assign_by_spills): Return a flag of reload
+	assignment failure.  Do not process the reload assignment
+	failures.  Do not spill other reload pseudos if they has the same
+	reg class.
+	(lra_assign): Add a return arg.  Set up from the result of
+	assign_by_spills call.
+	(find_reload_regno_insns, lra_split_hard_reg_for): New functions.
+	* lra-constraints.c (split_reg): Add a new arg.  Use it instead of
+	usage_insns if it is not NULL.
+	(spill_hard_reg_in_range): New function.
+	(split_if_necessary, inherit_in_ebb): Pass a new arg to split_reg.
+	* lra-int.h (spill_hard_reg_in_range, lra_split_hard_reg_for): New
+	function prototypes.
+	(lra_assign): Change prototype.
+	* lra.c (lra): Add code to deal with fails by splitting hard reg
+	live ranges.
+
 2018-03-09  Kyrylo Tkachov  
 
 	PR target/83193
Index: testsuite/ChangeLog
===
--- testsuite/ChangeLog	(revision 258389)
+++ testsuite/ChangeLog	(working copy)
@@ -1,3 +1,8 @@
+2018-03-09  Vladimir Makarov  
+
+	PR target/83712
+	* gcc.target/arm/pr83712.c: New.
+
 2018-03-09  Richard Biener  
 
 	PR tree-optimization/84775
Index: lra-int.h
===
--- lra-int.h	(revision 258389)
+++ lra-int.h	(working copy)
@@ -356,6 +356,7 @@ extern bool lra_constrain_insn (rtx_insn
 extern bool lra_constraints (bool);
 extern void lra_constraints_init (void);
 extern void lra_constraints_finish (void);
+extern bool spill_hard_reg_in_range (int, enum reg_class, rtx_insn *, rtx_insn *);
 extern void lra_inheritance (void);
 extern bool lra_undo_inheritance (void);
 
@@ -389,8 +390,8 @@ extern void lra_setup_reload_pseudo_pref
 extern int lra_assignment_iter;
 extern int lra_assignment_iter_after_spill;
 extern void lra_setup_reg_renumber (int, int, bool);
-extern bool lra_assign (void);
-
+extern bool lra_assign (bool &);
+extern void lra_split_hard_reg_for (void);
 
 /* lra-coalesce.c: */
 
Index: lra.c
===
--- lra.c	(revision 258389)
+++ lra.c	(working copy)
@@ -2460,38 +2460,53 @@ lra (FILE *f)
 	}
 	  if (live_p)
 	lra_clear_live_ranges ();
-	  /* We need live ranges for lra_assign -- so build them.  But
-	 don't remove dead insns or change global live info as we
-	 can undo inheritance transformations after inheritance
-	 pseudo assigning.  */
-	  lra_create_live_ranges (true, false);
-	  live_p = true;
-	  /* If we don't spill non-reload and non-inheritance pseudos,
-	 there is no sense to run memory-memory move coalescing.
-	 If inheritance pseudos were spilled, the memory-memory
-	 moves involving them will be removed by pass undoing
-	 inheritance.  */
-	  if (lra_simple_p)
-	lra_assign ();
-	  else
+	  bool fails_p;
+	  do
 	{
-	  bool spill_p = !lra_assign ();
-
-	  if (lra_undo_inheritance ())
-		live_p = false;
-	  if (spill_p)
+	  /* We need live ranges for lra_assign -- so build them.
+		 But don't remove dead insns or change global live
+		 info as we can undo inheritance transformations after
+		 inheritance pseudo assigning.  */
+	  lra_create_live_ranges (true, false);
+	  live_p = true;
+	  /* If we don't spill non-reload and non-inheritance
+		 pseudos, there is no sense to run memory-memory move
+		 coalescing.  If inheritance pseudos were spilled, the
+		 memory-memory moves involving them will be removed by
+		 pass undoing inheritance.  */
+	  if (lra_simple_p)
+		lra_assign (fails_p);
+	  else
 		{
-		  if (! live_p)
+		  bool spill_p = !lra_assign (fails_p);
+		  
+		  if (lra_undo_inheritance ())
+		live_p = false;
+		  if (spill_p