[PR rtl-optimization/55604]: fix ICE in remove_some_program_points_and_update_live_ranges

[PR rtl-optimization/55604]: fix ICE in remove_some_program_points_and_update_live_ranges

[Aldy Hernandez]

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

This is a division by zero ICE.

In the testcase in the PR, both `n' and `lra_live_max_point' are zero. 
I have opted to inhibit the dump when lra_live_max_point is zero, but I 
can just as easily avoiding printing the percentage in this case.

Let me know what you prefer.

OK for trunk?

[-- Attachment #2: curr --]
[-- Type: text/plain, Size: 816 bytes --]

commit 6b366d44e7d30d3a24eda07fcb43fc20e2aa7102
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Wed Dec 5 12:06:01 2012 -0600

    	PR rtl-optimization/55604
    	* lra-lives.c
    	* (remove_some_program_points_and_update_live_ranges):
    	Avoiding division by zero when dumping live range compression.

diff --git a/gcc/lra-lives.c b/gcc/lra-lives.c
index c79b95b..46146ca 100644
--- a/gcc/lra-lives.c
+++ b/gcc/lra-lives.c
@@ -811,7 +811,7 @@ remove_some_program_points_and_update_live_ranges (void)
   sbitmap_free (born);
   sbitmap_free (dead);
   n++;
-  if (lra_dump_file != NULL)
+  if (lra_dump_file != NULL && lra_live_max_point)
     fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
 	     lra_live_max_point, n, 100 * n / lra_live_max_point);
   if (n < lra_live_max_point)

Re: [PR rtl-optimization/55604]: fix ICE in remove_some_program_points_and_update_live_ranges

[Aldy Hernandez]

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

On 12/05/12 12:13, Aldy Hernandez wrote:
> This is a division by zero ICE.
>
> In the testcase in the PR, both `n' and `lra_live_max_point' are zero. I
> have opted to inhibit the dump when lra_live_max_point is zero, but I
> can just as easily avoiding printing the percentage in this case.
>
> Let me know what you prefer.
>
> OK for trunk?

Errr, another ChangeLog oops.  Cut and paste error fixed.  Sorry.

[-- Attachment #2: curr --]
[-- Type: text/plain, Size: 809 bytes --]

commit fcb644db593ee78855a0fac1a76f11478a359d1d
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Wed Dec 5 12:06:01 2012 -0600

    	PR rtl-optimization/55604
    	* lra-lives.c (remove_some_program_points_and_update_live_ranges):
    	Avoiding division by zero when dumping live range compression.

diff --git a/gcc/lra-lives.c b/gcc/lra-lives.c
index c79b95b..46146ca 100644
--- a/gcc/lra-lives.c
+++ b/gcc/lra-lives.c
@@ -811,7 +811,7 @@ remove_some_program_points_and_update_live_ranges (void)
   sbitmap_free (born);
   sbitmap_free (dead);
   n++;
-  if (lra_dump_file != NULL)
+  if (lra_dump_file != NULL && lra_live_max_point)
     fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
 	     lra_live_max_point, n, 100 * n / lra_live_max_point);
   if (n < lra_live_max_point)

Re: [PR rtl-optimization/55604]: fix ICE in remove_some_program_points_and_update_live_ranges

[Steven Bosscher]

On Wed, Dec 5, 2012 at 7:13 PM, Aldy Hernandez wrote:
> This is a division by zero ICE.
>
> In the testcase in the PR, both `n' and `lra_live_max_point' are zero. I
> have opted to inhibit the dump when lra_live_max_point is zero, but I can
> just as easily avoiding printing the percentage in this case.

Test case?

Also, it'd be preferable if you can also update
remove_some_program_points_and_update_live_ranges in ira-lives.c -- it
seems to me that at some point we're going to want to merge the almost
identical functions from LRA and IRA but that gets harder if they
start diverging.

> Let me know what you prefer.

How can you end up with lra_live_max_point==0? AFAIU that can only
happen if you have no live ranges at all (no program points) or if
somehow the curr_point counter got messed up. The former case would
mean you shouldn't end up calling
remove_some_program_points_and_update_live_ranges to begin with (no
program points being there to remove), the latter case would be a bug.

I don't think this is the correct fix.

Ciao!
Steven

Re: [PR rtl-optimization/55604]: fix ICE in remove_some_program_points_and_update_live_ranges

[Vladimir Makarov]

On 12-12-05 1:13 PM, Aldy Hernandez wrote:
> This is a division by zero ICE.
>
> In the testcase in the PR, both `n' and `lra_live_max_point' are zero. 
> I have opted to inhibit the dump when lra_live_max_point is zero, but 
> I can just as easily avoiding printing the percentage in this case.
>
Interesting.  I never thought that is possible.
> Let me know what you prefer.
>
> OK for trunk?
Yes, it is ok if you add the testcase for GCC testsuite.  It would be 
nice if you add analogous code for 
ira-lives.c::remove_some_program_points_and_update_live_ranges too.

Re: [PR rtl-optimization/55604]: fix ICE in remove_some_program_points_and_update_live_ranges

[Steven Bosscher]

On Wed, Dec 5, 2012 at 7:47 PM, Vladimir Makarov wrote:
> On 12-12-05 1:13 PM, Aldy Hernandez wrote:
>>
>> This is a division by zero ICE.
>>
>> In the testcase in the PR, both `n' and `lra_live_max_point' are zero. I
>> have opted to inhibit the dump when lra_live_max_point is zero, but I can
>> just as easily avoiding printing the percentage in this case.
>>
> Interesting.  I never thought that is possible.
>
>> Let me know what you prefer.
>>
>> OK for trunk?
>
> Yes, it is ok if you add the testcase for GCC testsuite.

Eh, are you sure?

This means we enter remove_some_program_points_and_update_live_ranges
with lra_live_max_point==0 (it's updated _after_ compression so at the
point of the dump it's using the value on entry, _before_
compression). So we're doing things like:

  born = sbitmap_alloc (lra_live_max_point); // => sbitmap_alloc (0);
  dead = sbitmap_alloc (lra_live_max_point); // idem
  bitmap_clear (born); // clear a bitmap that doesn't really exit
  bitmap_clear (dead); // idem.
  max_regno = max_reg_num ();
  for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
    {  // walk all registers on looking for live ranges -- but there
can't be any
      for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
        {
          lra_assert (r->start <= r->finish);
          bitmap_set_bit (born, r->start);
          bitmap_set_bit (dead, r->finish);
        }
    }

etc.


That makes no sense...

The function that triggers this, has this RTL after IRA:

    1: NOTE_INSN_DELETED
    3: NOTE_INSN_BASIC_BLOCK 2
    2: NOTE_INSN_FUNCTION_BEG
    5: {r60:DI=frame:DI-0x10;clobber flags:CC;}
      REG_UNUSED flags:CC
      REG_EQUIV frame:DI-0x10
    6: dx:DI=r60:DI
      REG_DEAD r60:DI
      REG_EQUAL frame:DI-0x10
    7: si:SI=0x5
    8: di:DI=`*.LC0'
    9: ax:QI=0
   10: ax:SI=call [`printf'] argc:0
      REG_DEAD di:DI
      REG_DEAD si:SI
      REG_DEAD dx:DI
      REG_UNUSED ax:SI
   15: ax:SI=0
   18: use ax:SI

Note how there are no pseudos at all in the function. So why run LRA
on it at all?

How about the fix proposed below?

Ciao!
Steven


Index: lra-lives.c
===================================================================
--- lra-lives.c (revision 194226)
+++ lra-lives.c (working copy)
@@ -915,6 +915,7 @@ lra_create_live_ranges (bool all_p)
   basic_block bb;
   int i, hard_regno, max_regno = max_reg_num ();
   int curr_point;
+  bool have_referenced_pseudos = false;

   timevar_push (TV_LRA_CREATE_LIVE_RANGES);

@@ -947,10 +948,24 @@ lra_create_live_ranges (bool all_p)
       lra_reg_info[i].call_p = false;
 #endif
       if (i >= FIRST_PSEUDO_REGISTER
-         && lra_reg_info[i].nrefs != 0 && (hard_regno = reg_renumber[i]) >= 0)
-       lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
+         && lra_reg_info[i].nrefs != 0)
+       {
+         if ((hard_regno = reg_renumber[i]) >= 0)
+           lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
+         have_referenced_pseudos = true;
+       }
     }
   lra_free_copies ();
+
+  /* Under some circumstances, we can have functions without pseudo
+     registers.  For such functions, lra_live_max_point will be 0,
+     see e.g. PR55604, and there's nothing more to do for us here.  */
+  if (! have_referenced_pseudos)
+    {
+      timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
+      return;
+    }
+
   pseudos_live = sparseset_alloc (max_regno);
   pseudos_live_through_calls = sparseset_alloc (max_regno);
   pseudos_live_through_setjumps = sparseset_alloc (max_regno);
@@ -973,6 +988,7 @@ lra_create_live_ranges (bool all_p)
     }
   free (post_order_rev_cfg);
   lra_live_max_point = curr_point;
+  gcc_checking_assert (lra_live_max_point > 0);
   if (lra_dump_file != NULL)
     print_live_ranges (lra_dump_file);
   /* Clean up. */

Re: [PR rtl-optimization/55604]: fix ICE in remove_some_program_points_and_update_live_ranges

[Steven Bosscher]

On Wed, Dec 5, 2012 at 8:11 PM, Steven Bosscher  wrote:
> The function that triggers this, has this RTL after IRA:

At which point, of course, I wanted to show after substituting hard
regs for the pseudos, so that:

>
>     1: NOTE_INSN_DELETED
>     3: NOTE_INSN_BASIC_BLOCK 2
>     2: NOTE_INSN_FUNCTION_BEG
>     5: {r60:DI=frame:DI-0x10;clobber flags:CC;}
>       REG_UNUSED flags:CC
>       REG_EQUIV frame:DI-0x10
>     6: dx:DI=r60:DI
>       REG_DEAD r60:DI
>       REG_EQUAL frame:DI-0x10
>     7: si:SI=0x5
>     8: di:DI=`*.LC0'
>     9: ax:QI=0
>    10: ax:SI=call [`printf'] argc:0
>       REG_DEAD di:DI
>       REG_DEAD si:SI
>       REG_DEAD dx:DI
>       REG_UNUSED ax:SI
>    15: ax:SI=0
>    18: use ax:SI

becomes...

    3: NOTE_INSN_BASIC_BLOCK 2
    2: NOTE_INSN_FUNCTION_BEG
    5: NOTE_INSN_DELETED
    6: dx:DI=frame:DI
      REG_DEAD r60:DI
      REG_EQUAL frame:DI-0x10
    7: si:SI=0x5
    8: di:DI=`*.LC0'
    9: ax:QI=0
   10: ax:SI=call [`printf'] argc:0
      REG_DEAD di:DI
      REG_DEAD si:SI
      REG_DEAD dx:DI
      REG_UNUSED ax:SI
   15: ax:SI=0
   18: use ax:SI

on entry to lra_create_live_ranges().

> Note how there are no pseudos at all in the function.

(... apart from the REG_DEAD use of r60. Both IRA and LRA sometimes
leave REG_NOTEs referencing pseudos. I haven't figured out yet why.)

Ciao!
Steven

Re: [PR rtl-optimization/55604]: fix ICE in remove_some_program_points_and_update_live_ranges

[Vladimir Makarov]

On 12-12-05 2:11 PM, Steven Bosscher wrote:
> On Wed, Dec 5, 2012 at 7:47 PM, Vladimir Makarov wrote:
>> On 12-12-05 1:13 PM, Aldy Hernandez wrote:
>>> This is a division by zero ICE.
>>>
>>> In the testcase in the PR, both `n' and `lra_live_max_point' are zero. I
>>> have opted to inhibit the dump when lra_live_max_point is zero, but I can
>>> just as easily avoiding printing the percentage in this case.
>>>
>> Interesting.  I never thought that is possible.
>>
>>> Let me know what you prefer.
>>>
>>> OK for trunk?
>> Yes, it is ok if you add the testcase for GCC testsuite.
> Eh, are you sure?
>
> This means we enter remove_some_program_points_and_update_live_ranges
> with lra_live_max_point==0 (it's updated _after_ compression so at the
> point of the dump it's using the value on entry, _before_
> compression). So we're doing things like:
>
>    born = sbitmap_alloc (lra_live_max_point); // => sbitmap_alloc (0);
>    dead = sbitmap_alloc (lra_live_max_point); // idem
>    bitmap_clear (born); // clear a bitmap that doesn't really exit
>    bitmap_clear (dead); // idem.
>    max_regno = max_reg_num ();
>    for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
>      {  // walk all registers on looking for live ranges -- but there
> can't be any
>        for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
>          {
>            lra_assert (r->start <= r->finish);
>            bitmap_set_bit (born, r->start);
>            bitmap_set_bit (dead, r->finish);
>          }
>      }
>
> etc.
>
>
> That makes no sense...
>
> The function that triggers this, has this RTL after IRA:
>
>      1: NOTE_INSN_DELETED
>      3: NOTE_INSN_BASIC_BLOCK 2
>      2: NOTE_INSN_FUNCTION_BEG
>      5: {r60:DI=frame:DI-0x10;clobber flags:CC;}
>        REG_UNUSED flags:CC
>        REG_EQUIV frame:DI-0x10
>      6: dx:DI=r60:DI
>        REG_DEAD r60:DI
>        REG_EQUAL frame:DI-0x10
>      7: si:SI=0x5
>      8: di:DI=`*.LC0'
>      9: ax:QI=0
>     10: ax:SI=call [`printf'] argc:0
>        REG_DEAD di:DI
>        REG_DEAD si:SI
>        REG_DEAD dx:DI
>        REG_UNUSED ax:SI
>     15: ax:SI=0
>     18: use ax:SI
>
> Note how there are no pseudos at all in the function. So why run LRA
> on it at all?
The insn constraints could be not satisfied even if we have only hard 
registers.   So we need to run LRA in any case.
> How about the fix proposed below?
It could work too.  Either code is ok to me.  The testscase is very rare 
and can be achieved only for a small program.  So the code speed is not 
important.  I favor a bit your code as it does not change the code 
presented in IRA and LRA which might be unified someday.  So if you are 
ready to commit your patch before Aldy did it, please do it, Steven.


> Ciao!
> Steven
>
>
> Index: lra-lives.c
> ===================================================================
> --- lra-lives.c (revision 194226)
> +++ lra-lives.c (working copy)
> @@ -915,6 +915,7 @@ lra_create_live_ranges (bool all_p)
>     basic_block bb;
>     int i, hard_regno, max_regno = max_reg_num ();
>     int curr_point;
> +  bool have_referenced_pseudos = false;
>
>     timevar_push (TV_LRA_CREATE_LIVE_RANGES);
>
> @@ -947,10 +948,24 @@ lra_create_live_ranges (bool all_p)
>         lra_reg_info[i].call_p = false;
>   #endif
>         if (i >= FIRST_PSEUDO_REGISTER
> -         && lra_reg_info[i].nrefs != 0 && (hard_regno = reg_renumber[i]) >= 0)
> -       lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
> +         && lra_reg_info[i].nrefs != 0)
> +       {
> +         if ((hard_regno = reg_renumber[i]) >= 0)
> +           lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
> +         have_referenced_pseudos = true;
> +       }
>       }
>     lra_free_copies ();
> +
> +  /* Under some circumstances, we can have functions without pseudo
> +     registers.  For such functions, lra_live_max_point will be 0,
> +     see e.g. PR55604, and there's nothing more to do for us here.  */
> +  if (! have_referenced_pseudos)
> +    {
> +      timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
> +      return;
> +    }
> +
>     pseudos_live = sparseset_alloc (max_regno);
>     pseudos_live_through_calls = sparseset_alloc (max_regno);
>     pseudos_live_through_setjumps = sparseset_alloc (max_regno);
> @@ -973,6 +988,7 @@ lra_create_live_ranges (bool all_p)
>       }
>     free (post_order_rev_cfg);
>     lra_live_max_point = curr_point;
> +  gcc_checking_assert (lra_live_max_point > 0);
>     if (lra_dump_file != NULL)
>       print_live_ranges (lra_dump_file);
>     /* Clean up. */

Re: [PR rtl-optimization/55604]: fix ICE in remove_some_program_points_and_update_live_ranges

[Aldy Hernandez]

> It could work too.  Either code is ok to me.  The testscase is very rare
> and can be achieved only for a small program.  So the code speed is not
> important.  I favor a bit your code as it does not change the code
> presented in IRA and LRA which might be unified someday.  So if you are
> ready to commit your patch before Aldy did it, please do it, Steven.

Steven, go right ahead.  Let me know when you commit so I can close the PR.

Thanks.

Re: [PR rtl-optimization/55604]: fix ICE in remove_some_program_points_and_update_live_ranges

[Steven Bosscher]

On Wed, Dec 5, 2012 at 9:47 PM, Aldy Hernandez wrote:
> Steven, go right ahead.  Let me know when you commit so I can close the PR.

Thanks, committed as r194230 (patch) and r194231 (test case) after
bootstrap&test on x86_64-unknown-linux-gnu.

Ciao!
Steven

Re: [PR rtl-optimization/55604]: fix ICE in remove_some_program_points_and_update_live_ranges

[David Edelsohn]

On 12-12-05 1:13 PM, Aldy Hernandez wrote:

>> This is a division by zero ICE.

>> In the testcase in the PR, both `n' and `lra_live_max_point' are zero. I have opted to inhibit the dump when lra_live_max_point is zero, but I can just as easily avoiding printing the percentage in this case.

> Interesting. I never thought that is possible.

>> Let me know what you prefer.

>> OK for trunk?

> Yes, it is ok if you add the testcase for GCC testsuite. It would be nice if you add analogous code for ira-lives.c::remove_some_program_points_and_update_live_ranges too.

I agree with Steven, this patch seems to be fixing the symptom, not
the problem.  Please re-consider if Steven's patch is a better
solution.

Thanks, David