RFC: LRA for x86/x86-64 [7/9]

[Steven Bosscher]

On Tue, Oct 2, 2012 at 3:42 PM, Richard Sandiford
<rdsandiford@googlemail.com> wrote:
>
>> +/* Compress pseudo live ranges by removing program points where
>> +   nothing happens.  Complexity of many algorithms in LRA is linear
>> +   function of program points number.  To speed up the code we try to
>> +   minimize the number of the program points here.  */
>> +static void
>> +remove_some_program_points_and_update_live_ranges (void)
>
> Genuine question, but could we do this on the fly instead,
> by not incrementing curr_point if the current point had no value?
>
> I suppose the main complication would be checking cases where
> all births are recorded by extending the previous just-closed live
> range rather than starting a new one, in which case it's the previous
> point that needs to be reused.  Hmm...

It does seem to be something worth investigating further. Things like:

Compressing live ranges: from 1742579 to 554532 - 31%
Compressing live ranges: from 1742569 to 73069 - 4%

look extreme, but they're actually the norm. For the same test case
(PR54146 still) but looking only at functions with initially 1000-9999
program points, you get this picture:

Compressing live ranges: from 1766 to 705 - 39%
Compressing live ranges: from 1449 to 370 - 25%
Compressing live ranges: from 3939 to 1093 - 27%
Compressing live ranges: from 3939 to 1093 - 27%
Compressing live ranges: from 3939 to 1093 - 27%
Compressing live ranges: from 3939 to 1093 - 27%
Compressing live ranges: from 2464 to 676 - 27%
Compressing live ranges: from 1433 to 379 - 26%
Compressing live ranges: from 1261 to 348 - 27%
Compressing live ranges: from 2835 to 755 - 26%
Compressing live ranges: from 5426 to 1678 - 30%
Compressing live ranges: from 5227 to 1477 - 28%
Compressing live ranges: from 1845 to 467 - 25%
Compressing live ranges: from 4868 to 1378 - 28%
Compressing live ranges: from 4875 to 1388 - 28%
Compressing live ranges: from 4882 to 1384 - 28%
Compressing live ranges: from 5688 to 1714 - 30%
Compressing live ranges: from 4943 to 1310 - 26%
Compressing live ranges: from 2976 to 792 - 26%
Compressing live ranges: from 5463 to 1526 - 27%
Compressing live ranges: from 2854 to 730 - 25%
Compressing live ranges: from 1810 to 745 - 41%
Compressing live ranges: from 2771 to 904 - 32%
Compressing live ranges: from 4916 to 1429 - 29%
Compressing live ranges: from 6505 to 2238 - 34%
Compressing live ranges: from 6493 to 166 - 2%
Compressing live ranges: from 5498 to 1734 - 31%
Compressing live ranges: from 1810 to 745 - 41%
Compressing live ranges: from 5043 to 1420 - 28%
Compressing live ranges: from 3094 to 788 - 25%
Compressing live ranges: from 4563 to 1311 - 28%
Compressing live ranges: from 4557 to 158 - 3%
Compressing live ranges: from 1050 to 274 - 26%
Compressing live ranges: from 1602 to 434 - 27%
Compressing live ranges: from 2474 to 600 - 24%
Compressing live ranges: from 2718 to 866 - 31%
Compressing live ranges: from 2097 to 716 - 34%
Compressing live ranges: from 4152 to 1099 - 26%
Compressing live ranges: from 5065 to 1514 - 29%
Compressing live ranges: from 1236 to 359 - 29%
Compressing live ranges: from 1722 to 541 - 31%
Compressing live ranges: from 5186 to 1401 - 27%

Unfortunately the dump doesn't mention how many live ranges could be
merged thanks to the compression.

It'd also be good to understand why the compression ratios are so
small, and consistently around ~30%. Maybe curr_point includes things
it should ignore (DEBUG_INSNs, NOTEs, ...)?

Ciao!
Steven