Re: new interference graph builder.

[Kenneth Zadeck <zadeck at naturalbridge dot com>]

Seongbae Park (박성배, 朴成培) wrote:
> 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.
>   
As it turns out, i had been testing this on a two week old branch, when
i updated, it stopped working. I am looking into it.

> The register preference handling code (set_preference)
> probably can be converted to use dataflow
> but that can (and should) be done separately.
>   
I thought about this and did not do it for two reasons:

One of them is that there actually is not enough info in the df stuff to
do this. You need to be able to match a use in the insn with the set at
the top and for parallels this info is not there.

The second is that i assumed that vlad would kill this code.

kenny

> 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
>>>>