Re: [patch][lra] Improve initial program point density in lra-lives.c (was: Re: RFC: LRA for x86/x86-64 [7/9])

[Steven Bosscher <stevenb dot gcc at gmail dot com>]

On Thu, Oct 4, 2012 at 8:57 AM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> On Thu, Oct 4, 2012 at 5:30 AM, Vladimir Makarov <vmakarov@redhat.com> wrote:
>> I was going to look at this code too but I was interesting in generation of
>> less points and live ranges.  It is strange that in my profiles,
>> remove_some_program_points_and_update_live_ranges takes 0.6% of compiler
>> time on these huge tests.   So I was not interesting to speed up the
>> function and may be therefore you have no visible change in compilation
>> time.
>
> Right. The compression algorithm doesn't care much about the initial
> number of program points, only about the number of live ranges before
> and after compression. I had expected a bigger effect on the number of
> live ranges before compression.
>
> 0.6% sounds really very different from my timings. How much time does
> create_start_finish_chains take for you?
>
>
>> I don't object the idea of the patch.  I need some time to look at it (the
>> different results on a function is a bit scary for me) and check simulator
>> times on other tests.
>
> Understood.

BTW, it would be great if you can also look at this additional patch hunk:

@@ -994,8 +1044,8 @@ lra_create_live_ranges (bool all_p)
   curr_point = 0;
   point_freq_vec = VEC_alloc (int, heap, get_max_uid () * 2);
   lra_point_freq = VEC_address (int, point_freq_vec);
-  FOR_EACH_BB (bb)
-    process_bb_lives (bb);
+  FOR_EACH_BB_REVERSE (bb)
+    process_bb_lives (bb, curr_point);
   lra_live_max_point = curr_point;
   create_start_finish_chains ();
   if (lra_dump_file != NULL)

I think this should result in more live ranges being merged. Here's
why I think so, based on my far worse understanding of this code than
yours, so forgive me if I'm Completely Wrong :-)

process_bb_lives walks insns in the basic block from last to first, so
say you have a basic block chain 1->2->3, and each block has 4 insns,
then AFAIU the program points in block 1 will be [4,3,2,1], in block 2
it will be [8,7,6,5], and in block 3 it will be [12,11,10,9]. Say a
reg is used in block 3 at point 11, and set in block at point 3. Then
this reg will have a live range chain [3-1],[8-5],[12-11].

If you visit the basic blocks in reverse order, the program points
will be: 1:[12,11,10,9], 2:[8,7,6,5], 3:[4,3,2,1]. Now the same reg
will be set at point 11 and used at point 3, and the live range chain
will be just [11-3].

I'm experimenting with this extra hunk and report back here.

Ciao!
Steven