Re: new interference graph builder.

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

ra-conflict.c:528-530

You may want to add some comment explaining that you're adding
defs to live *temporarily* to ensure conflicts between defs
(cause it doesn't make sense to add defs to live during backward scan,
so at first it looks really weird).

ra-conflict.c:564-575

I think DF_REF_MAY_CLOBBER should kill the register here.
PARTIAL or CONDITIONAL don't kill but MAY_CLOBBER should.
i.e. We need to preserve a pseudo reg
even if it crosses PARTIAL def or CONDITIONAL def
but we don't need to if it crosses MAY_CLOBBER.
Hence, MAY_CLOBBERs actually kill the value.


ra-conflict.c:645-663

This code effectively treats CLOBBERs as early clobbers
for dying regs. I don't quite understand why this is necessary.
(c.f. the other two cases of early clobber and multiset case
are explained pretty well).

ra-conflict.c:665-667

The comment is (very slightly) misleading -
as early clobbers should not only interfere with dying registers
but also with all other live registers as well.
I believe the code is ok simply because
the interference with other live registers are already handled
(since presumably all early clobbers should be defs by definition).


ra-conflict.c:744-781

There's a subtle change from the current implementation -
in the existing global_conflicts,
#ifdef STACK_REGS part (+ call_used_regs part)
is guarded by EDGE_ABNORMAL
whereas the new code is under EDGE_EH (bb_has_eh_pred).
For blocks that have a ABNORMAL pred but no EH pred,
the new code will behave differently. Is this intended ?

Also, ideally, we should only need to iterate through
artificial def set that's DF_REF_AT_TOP here
i.e. if we want to treat stack regs not crossing eh boundary,
we should really add them to bb artificial def set as DF_REF_AT_TOP.
Likewise, call-used regs. On the other hand, such a cleanup
should be a separate patch if we ever do so, so I think this is ok.

My last question is the compile-time and run-time performance.
Do you have any measurement ?
(Let me know if you need any help in measuring the performance).
Thanks!

Seongbae

On 8/25/07, Seongbae Park (박성배, 朴成培) <seongbae.park@gmail.com> wrote:
> 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.
> >
> >
> >
> >
> >