patch to implement thread coloring in IRA

[Vladimir Makarov <vmakarov at redhat dot com>]

  The following patch improves coloring.  The order of pushing allocnos 
on the coloring stack from a bunch of colorable allocnos was always 
important for generated code performance.  LRA has a mechanism of 
allocating pseudos by threads.  Thread in LRA is a set of 
non-conflicting pseudos connected by moves (or by future reload insns).  
Allocating pseudos by threads in LRA permits to improve code by 
increasing chance of removing the move insns.

  So the same mechanism can be used for IRA.  The patch implements it.  
The difference is only that LRA forms thread statically before 
allocation sub-pass.  That is because the basic allocation are already 
done in IRA.  The statically thread forming works well for IRA too.  But 
even better results can be got by dynamically forming threads.  It means 
that we are forming threads during allocation and includes only 
colorable allocnos.

  The results of using threads in IRA is pretty good.  The average code 
size (text segment) of SPEC2000 is improved (by >0.1% for x86 SPECFP2000 
and > 0.3% for x86-64 SPECFP2000). The biggest code performance 
improvement (> 1%) is obtained on x86-64 SPECFP2000.  Performance tools 
report that additional code takes only about 0.05% additionally executed 
insns.

  The patch also removes 2 insn in code for PR59036

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59036

  Therefore I put the PR in changelog.

  The patch was successfully bootstrapped an tested on x86/x86-64.

  Committed as rev. 204752.

2013-11-13  Vladimir Makarov  <vmakarov@redhat.com>

    PR rtl-optimization/59036
        * ira-color.c (struct allocno_color_data): Add new members
        first_thread_allocno, next_thread_allocno, thread_freq.
        (sorted_copies): New static var.
        (allocnos_conflict_by_live_ranges_p, copy_freq_compare_func): Move
        up.
        (allocno_thread_conflict_p, merge_threads)
        (form_threads_from_copies, form_threads_from_bucket)
        (form_threads_from_colorable_allocno, init_allocno_threads): New
        functions.
        (bucket_allocno_compare_func): Add comparison by thread frequency
        and threads.
        (add_allocno_to_ordered_bucket): Rename to
        add_allocno_to_ordered_colorable_bucket.  Remove parameter.
        (push_only_colorable): Call form_threads_from_bucket.
        (color_pass): Call init_allocno_threads.  Use
        consideration_allocno_bitmap instead of coloring_allocno_bitmap
        for nuillify allocno color data.
        (ira_initiate_assign, ira_finish_assign): Allocate/free
        sorted_copies.
        (coalesce_allocnos): Use static sorted copies.

Attachment: thread.patch
Description: Text document