Re: new interference graph builder.

["Seongbae Park (박성배, 朴成培)" <seongbae dot park at gmail dot com>]

Thanks for doing this. I started reading the code
- I don't think I have the authority to approve the entire patch
but I'll do whatever I can.

regs.h:

Probably we want to move struct allocno and its related stuff
into a separate header (ra.h maybe?)
since they are register allocator implementation internal,
rather than interfaces other parts of the backend can use,
like most of the stuff in the existing regs.h are.

rtlanal.c:

Can you change subreg_nreg to call subreg_nreg_with_regno
with appropriate regno ?
Currently the code is largely duplicated.

The rest looks ok to me, other than ra-conflict.c which I'm still reviewing.

Seongbae

On 8/25/07, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> This patch replaces the code in global.c that builds the interference
> graph.  The new technique differs from the old technique in several ways:
>
> 1) The new technique uses the DF_LIVE problem, which is the intersection
> of the forwards live information and the backwards live information.
> This is the dataflow problem that the rest of the back end of the
> compiler uses.  The existing implementation is based on a custom problem
> (UREC) that was "converted" to use the df framework from
> global.c:make_accurate_live_analysis, but was still a bastard problem.
> A significant amount of this patch is the removal of the UREC dataflow
> problem.
>
> 2) The new formulation uses a backwards scan rather than a forwards
> scan.  This is the way that every other compiler in the world builds the
> interference graph, and for good reason.  There is no use of REG_DEAD or
> REG_UNUSED notes when building the graph.  By using a backwards scan
> this technique actually discovers fewer interferences:
>
> consider the case where a multiword reg gets mapped into a series of
> hard regs but only one of those hardregs is actually used.  In a
> forwards scan, any register live will interfere with ANY of those hard
> regs.  In a backwards scan, the uses cause regs to go live, so only the
> hard regs actually used will create interferences.
>
> There have been proposals to generate SUBREG_DEAD and SUBREG_UNUSED
> notes but the proper thing to do is a backwards scan.  It may be that
> the current reload/global stack is not up to taking advantage of this
> yet, but vlad has plans for replacing the ra, and hopefully the new one
> will be equipped to use this.
>
> 3) Early clobbers are handled more precisely.  In the UREC problem, used
> in the existing implementation, as well as
> global.c:make_accurate_live_analysis before the df commit, an early
> clobber forces any input reg that could be allocated to the
> early_clobbering output reg to be live, starting at the beginning of the
> basic block.  This is insane, especially when optimizations have been
> performed to try to make large basic blocks.
>
> The new implementation implements the exact definition of early
> clobber:  any input reg that dies in the insn and could be allocated to
> the same register as the early clobber output is made to interfere with
> that output.
>
> 4) The interference graph builder does not scan insns, it uses the
> df_scan information.
>
> 5) There is nothing like the call record_conflicts in the new code.
> Chaitin showed that this was useless 20 years ago.
>
> 6) The code that set the preferences has been moved into global itself
> since this will most likely die in vlad's new implementation.
>
> I put the new conflict builder in a new file ra-conflicts.c since this
> code is likely to survive vlad's new ra; it seemed like this would make
> that integration easier.
>
> This code has been bootstrapped and regression tested on ppc-32, x86-64,
> and ia-64.
>
> Is this OK to commit?
>
> Kenny
>
> 2007-08-25  Kenneth Zadeck <zadeck@naturalbridge.com>
>
>     * ra-conflict.c: New file.
>     * reload.c (push_reload, find_dummy_reload): Change DF_RA_LIVE
>     usage to DF_LIVE usage.
>     * rtlanal.c (subreg_nregs_with_regno): New function.
>     * regs.h (allocno, max_allocno, conflicts, allocno_row_words,
>     reg_allocno, EXECUTE_IF_SET_IN_ALLOCNO_SET): Moved from global.c
>     (conflicts): Changed to be HOST_BITS_PER_WIDE_INT.
>     * global.c (allocno, max_allocno, conflicts, allocno_row_words,
>     reg_allocno, EXECUTE_IF_SET_IN_ALLOCNO_SET): Moved to regs.h
>     (SET_ALLOCNO_LIVE, CLEAR_ALLOCNO_LIVE): Moved to ra-conflicts.c.
>     (regs_set, record_one_conflict, record_conflicts, mark_reg_store,
>     mark_reg_clobber, mark_reg_conflicts, mark_reg_death): Deleted.
>     (global_alloc): Turn off rescanning insns after call to
>     global_conflicts and added call to set_preferences.
>     (global_conflicts): Moved to ra-alloc.c.
>     (set_preferences_1, set_preferences): New function.
>     (mirror_conflicts): Changed types for various variables.
>     (mark_elimination): Change DF_RA_LIVE
>     usage to DF_LIVE usage.
>     * local-alloc.c (update_equiv_regs): Change DF_RA_LIVE
>     usage to DF_LIVE usage.
>     (rest_of_handle_local_alloc): Changed urec problem to live
>     problem and do not turn off df rescanning.
>     * df.h (DF_UREC, DF_UREC_BB_INFO, DF_LIVE_TOP, DF_RA_LIVE_IN,
>     DF_RA_LIVE_TOP, DF_RA_LIVE_OUT, df_urec_bb_info, df_urec,
>     df_urec_add_problem, df_urec_get_bb_info): Removed.
>     (DF_CHAIN, DF_NOTE, DF_CHAIN): Renumbered.
>     * init-regs.c (initialize_uninitialized_regs): Enhanced debugging
>     at -O1.
>     * rtl.h (subreg_nregs_with_regno): New function.
>     * df-problems.c: (df_get_live_out, df_get_live_in,
>     df_get_live_top): Removed reference to DF_RA_LIVE.
>     (df_lr_reset, df_lr_transfer_function, df_live_free_bb_info,
>     df_live_alloc, df_live_reset, df_live_local_finalize,
>     df_live_free): Make top set only if different from in set.
>     (df_lr_top_dump, df_live_top_dump): Only print top set if
>     different from in set.
>     (df_lr_bb_local_compute): Removed unnecessary check.
>     (df_urec_problem_data, df_urec_set_bb_info, df_urec_free_bb_info,
>     df_urec_alloc, df_urec_mark_reg_change, earlyclobber_regclass,
>     df_urec_check_earlyclobber, df_urec_mark_reg_use_for_earlyclobber,
>     df_urec_mark_reg_use_for_earlyclobber_1, df_urec_bb_local_compute,
>     df_urec_local_compute, df_urec_init, df_urec_local_finalize,
>     df_urec_confluence_n, df_urec_transfer_function, df_urec_free,
>     df_urec_top_dump, df_urec_bottom_dump, problem_UREC,
>     df_urec_add_problem): Removed.
>     * Makefile.in (ra-conflict.o): New dependencies.
>     * reload1.c (compute_use_by_pseudos): Change DF_RA_LIVE
>     usage to DF_LIVE usage.
>
>
>
>
>


-- 
#pragma ident "Seongbae Park, compiler, http://seongbae.blogspot.com";