[PATCH, PR83327] Fix liveness analysis in lra for spilled-into hard regs

[Tom de Vries <Tom_deVries@mentor.com>]

[-- Attachment #1: Type: text/plain, Size: 5216 bytes --]

[ was: Re: patch to fix PR82353 ]

On 12/14/2017 06:01 PM, Vladimir Makarov wrote:
> 
> 
> On 12/13/2017 07:34 AM, Tom de Vries wrote:
>> On 10/16/2017 10:38 PM, Vladimir Makarov wrote:
>>> This is another version of the patch to fix
>>>
>>>     https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82353
>>>
>>> The patch was successfully bootstrapped on x86-64 with Go and Ada.
>>>
>>> Committed as rev. 253796.
>>
>> Hi Vladimir,
>>
>> AFAIU this bit of the patch makes sure that the flags register show up 
>> in the bb_livein of the bb in which it's used (and not defined before 
>> the use), but not in the bb_liveout of the predecessors of that bb.
>>
>> I wonder if that's a compile-speed optimization, or an oversight.
>>
> Hi, Tom.  It was just a minimal fix.  I prefer minimal fixes for LRA 
> because even for me it is hard to predict in many cases how the patch 
> will affect all the targets.  Therefore many LRA patches have a few 
> iterations before to be final.
> 

I see, thanks for the explanation.

> I remember that I had some serious problems in the past when I tried to 
> implement fixed hard reg liveness propagation in LRA.  It was long ago 
> so we could try it again.  If you send patch you mentioned to gcc 
> mailing list, I'll review and approve it.

Here it is. It applies cleanly to trunk (and to gcc-7-branch if you 
first backport r253796, the fix for PR82353).

I have not tested this on trunk sofar, only on the internal branch for 
gcn based on gcc 7.1 with the gcc testsuite, where it fixes a wrong-code 
bug in gcc.dg/vect/no-scevccp-outer-10.c and causes no regressions.

--------------------------------------------------------------------------

The problem on a minimal version of the test-case looks as follows:

I.

At ira, we have a def and use of 'reg:BI 605', the def in bb2 and the 
use in bb3:
...
(note 44 32 33 2 [bb 2] NOTE_INSN_BASIC_BLOCK)

    ...

(insn 269 54 64 2 (set (reg:BI 605)
         (le:BI (reg/v:SI 491 [ n ])
             (const_int 0 [0]))) 23 {cstoresi4}
      (nil))

    ....

(code_label 250 228 56 3 7 (nil) [1 uses])
(note 56 250 58 3 [bb 3] NOTE_INSN_BASIC_BLOCK)

    ...

(jump_insn 62 60 63 3 (set (pc)
         (if_then_else (ne:BI (reg:BI 605)
                 (const_int 0 [0]))
             (label_ref 242)
             (pc))) "no-scevccp-outer-10.c":19 21 {cjump}
      (int_list:REG_BR_PROB 1500 (nil))
  -> 242)
(note 63 62 66 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
...

And in lra, we decide to spill it into a hard register:
...
   Spill r605 into hr95
...

Resulting in this code:
...
(insn 385 386 64 2 (set (reg:BI 95 s95)
         (reg:BI 18 s18 [605])) 3 {*movbi}
      (nil))

   ...

(insn 404 60 405 3 (set (reg:BI 18 s18 [605])
         (reg:BI 95 s95)) "no-scevccp-outer-10.c":19 3 {*movbi}
      (nil))
...


II.

However, a bit later in lra we decide to assign r94,r95 to DImode pseudo 
833:
...
            Assign 94 to reload r833 (freq=60)
...

Resulting in this code:
...
(insn 629 378 390 2 (set (reg:DI 94 s94 [833])
         (plus:DI (reg/f:DI 16 s16)
             (const_int -8 [0xfffffffffffffff8]))) 35 {addptrdi3}
      (nil))
...

This clobbers the def of s95 in insn 385.


III.

Consequently, the insn is removed in the dce in the jump pass:
...
DCE: Deleting insn 385
deleting insn with uid = 385.
...

--------------------------------------------------------------------------

Analysis:

The decision to assign r94,r95 to DImode pseudo 833 happens because r95 
is not marked in the conflict_hard_regs of lra_reg_info[833] during 
liveness analysis.

There's code in make_hard_regno_born to set the reg in the 
conflict_hard_regs of live pseudos, but at the point that r95 becomes 
live, the r833 pseudo is not live.

Then there's code in mark_pseudo_live to set the hard_regs_live in the 
conflict_hard_regs of the pseudo, but at the point that r833 becomes 
live, r95 is not set in hard_regs_live, due to the fact that it's not 
set in df_get_live_out (bb2).

In other words, the root cause is that hard reg liveness propagation is 
not done.

--------------------------------------------------------------------------

Proposed Solution:

The patch addresses the problem, by:
- marking the hard regs that have been used in lra_spill in
   hard_regs_spilled_into
- using hard_regs_spilled_into in lra_create_live_ranges to
   make sure those registers are marked in the conflict_hard_regs
   of pseudos that overlap with the spill register usage

[ I've also tried an approach where I didn't use hard_regs_spilled_into, 
but tried to propagate all hard regs. I figured out that I needed to 
mask out eliminable_regset.  Also I needed to masked out 
lra_no_alloc_regs, but that could be due to gcn-specific problems 
(pointers take 2 hard regs), I'm not yet sure. Anyway, in the submitted 
patch I tried to avoid these problems and went for the more minimal 
approach. ]

In order to get the patch accepted for trunk, I think we need:
- bootstrap and reg-test on x86_64
- build and reg-test on mips (the only primary platform that has the
   spill_class hook enabled)

Any comments?

> But we need to be ready to 
> revert it if some problems occur again.
> 

Understood.

Thanks,
- Tom

[-- Attachment #2: 0001-Fix-liveness-analysis-in-lra-for-spilled-into-hard-regs.patch --]
[-- Type: text/x-patch, Size: 4428 bytes --]

Fix liveness analysis in lra for spilled-into hard regs

2017-12-12  Tom de Vries  <tom@codesourcery.com>

	PR rtl-optimization/83327
	* lra-int.h (hard_regs_spilled_into): Declare.
	* lra.c (hard_regs_spilled_into): Define.
	(init_reg_info): Init hard_regs_spilled_into.
	* lra-spills.c (assign_spill_hard_regs): Update hard_regs_spilled_into.
	* lra-lives.c (make_hard_regno_born, make_hard_regno_dead)
	(process_bb_lives): Handle hard_regs_spilled_into.
	(lra_create_live_ranges_1): Before doing liveness propagation, clear
	regs in all_hard_regs_bitmap if set in hard_regs_spilled_into.

---
 gcc/lra-int.h    |  2 ++
 gcc/lra-lives.c  | 28 ++++++++++++++++++++++++++--
 gcc/lra-spills.c |  2 ++
 gcc/lra.c        |  3 +++
 4 files changed, 33 insertions(+), 2 deletions(-)

diff --git a/gcc/lra-int.h b/gcc/lra-int.h
index 5a519b0..064961a 100644
--- a/gcc/lra-int.h
+++ b/gcc/lra-int.h
@@ -122,6 +122,8 @@ struct lra_reg
 /* References to the common info about each register.  */
 extern struct lra_reg *lra_reg_info;
 
+extern HARD_REG_SET hard_regs_spilled_into;
+
 /* Static info about each insn operand (common for all insns with the
    same ICODE).	 Warning: if the structure definition is changed, the
    initializer for debug_operand_data in lra.c should be changed
diff --git a/gcc/lra-lives.c b/gcc/lra-lives.c
index 03dfec2..85da626 100644
--- a/gcc/lra-lives.c
+++ b/gcc/lra-lives.c
@@ -245,7 +245,7 @@ make_hard_regno_born (int regno, bool check_pic_pseudo_p ATTRIBUTE_UNUSED)
 	|| i != REGNO (pic_offset_table_rtx))
 #endif
       SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
-  if (fixed_regs[regno])
+  if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
     bitmap_set_bit (bb_gen_pseudos, regno);
 }
 
@@ -259,7 +259,7 @@ make_hard_regno_dead (int regno)
     return;
   sparseset_set_bit (start_dying, regno);
   CLEAR_HARD_REG_BIT (hard_regs_live, regno);
-  if (fixed_regs[regno])
+  if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
     {
       bitmap_clear_bit (bb_gen_pseudos, regno);
       bitmap_set_bit (bb_killed_pseudos, regno);
@@ -1051,6 +1051,25 @@ process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
 	check_pseudos_live_through_calls (j, last_call_used_reg_set);
     }
 
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
+    {
+      if (!TEST_HARD_REG_BIT (hard_regs_live, i))
+	continue;
+
+      if (!TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
+	continue;
+
+      if (bitmap_bit_p (df_get_live_in (bb), i))
+	continue;
+
+      live_change_p = true;
+      if (lra_dump_file)
+	fprintf (lra_dump_file,
+		 "  hard reg r%d is added to live at bb%d start\n", i,
+		 bb->index);
+      bitmap_set_bit (df_get_live_in (bb), i);
+    }
+
   if (need_curr_point_incr)
     next_program_point (curr_point, freq);
 
@@ -1320,6 +1339,11 @@ lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
 	}
       /* As we did not change CFG since LRA start we can use
 	 DF-infrastructure solver to solve live data flow problem.  */
+      for (int i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
+	{
+	  if (TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
+	    bitmap_clear_bit (&all_hard_regs_bitmap, i);
+	}
       df_simple_dataflow
 	(DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
 	 live_trans_fun, &all_blocks,
diff --git a/gcc/lra-spills.c b/gcc/lra-spills.c
index af11b3d..ab13b21 100644
--- a/gcc/lra-spills.c
+++ b/gcc/lra-spills.c
@@ -291,6 +291,8 @@ assign_spill_hard_regs (int *pseudo_regnos, int n)
 	}
       if (lra_dump_file != NULL)
 	fprintf (lra_dump_file, "  Spill r%d into hr%d\n", regno, hard_regno);
+      add_to_hard_reg_set (&hard_regs_spilled_into,
+			   lra_reg_info[regno].biggest_mode, hard_regno);
       /* Update reserved_hard_regs.  */
       for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
 	for (p = r->start; p <= r->finish; p++)
diff --git a/gcc/lra.c b/gcc/lra.c
index fec2383..047e64f 100644
--- a/gcc/lra.c
+++ b/gcc/lra.c
@@ -1270,6 +1270,8 @@ static int reg_info_size;
 /* Common info about each register.  */
 struct lra_reg *lra_reg_info;
 
+HARD_REG_SET hard_regs_spilled_into;
+
 /* Last register value.	 */
 static int last_reg_value;
 
@@ -1319,6 +1321,7 @@ init_reg_info (void)
   for (i = 0; i < reg_info_size; i++)
     initialize_lra_reg_info_element (i);
   copy_vec.truncate (0);
+  CLEAR_HARD_REG_SET (hard_regs_spilled_into);
 }