Re: new interference graph builder.

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

All dataflow related parts are approved.
I don't think I can approve
parts of  ra.h, ra-conflicts.c and global.c changes
as some of those are not directly df-related
but they look ok to me.

The register preference handling code (set_preference)
probably can be converted to use dataflow
but that can (and should) be done separately.

Seongbae

On 8/26/07, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> Seongbae Park (박성배, 朴成培) wrote:
> > 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.
> >
> >
> I did everything you asked for except the paragraph above and retested
> on the three platforms.
>
> I also added a cleanup and removed df_has_eh_preds since this is the
> same as bb_has_eh_pred.
>
> 2007-08-26 Kenneth Zadeck <zadeck@naturalbridge.com>
>
> * ra-conflict.c: New file.
> * ra.h: 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.
> * df-scan.c (df_has_eh_preds): Removed.
> (df_bb_refs_collect, df_bb_refs_collect, df_bb_refs_collect,
> df_exit_block_uses_collect): Changed call from df_has_eh_preds to
> bb_has_eh_pred.
> * global.c (allocno, max_allocno, conflicts, allocno_row_words,
> reg_allocno, EXECUTE_IF_SET_IN_ALLOCNO_SET): Moved to ra.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, df_has_eh_preds): 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.
> (df_simulate_fixup_sets): Changed call from df_has_eh_preds to
> bb_has_eh_pred.
> * Makefile.in (ra-conflict.o, ra.h): New dependencies.
> * basic_block.h (bb_has_abnormal_pred): New function.
> * reload1.c (compute_use_by_pseudos): Change DF_RA_LIVE
> usage to DF_LIVE usage.
>
>
> > 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