Register Rematerialization In New Register Allocator

Mukta Punjani, Noida
Thu Jul 24 11:44:00 GMT 2003


Following are proposed areas in new-ra that would need remat handling code

1. For constructing remat computation sequence for pseudos -
   o df.h - struct ref(corresponding to each def) to be modified to hold the
remat insn sequence (in terms of the insn uids) for the def making up the
insn chain.
   o df.c - Call new function from df_ref_search_cached() to relate remat
insn uid sequence with each def.

2. Interference Graph Construction -
   o ra.h - struct web would require a new field similar to field in struct
df to hold remat sequence(in terms of insn uid 	chain) . Already an rtx
field "pattern" holds the remat insn for a constant src insn found to be
   o ra-build.c - Addition of remat handling in detect_remat_webs().
   o ra-build.c - Modify cost calculation of webs (as the remat pattern
would be more than a single insn) in 	determine_web_costs().

3. Spilling/Remat
   o ra-rewrite.c - In actual spill() before assign_stack_slots(), call a
new funnction to handle insns to be remat.
   o ra-rewrite.c - In rewrite_program()/rewrite_program2() add remat
   o ra-rewrite.c - In detect_web_parts_to_rebuild(), update webs/conflicts
due to remat insn addition.

More comments/suggestions awaited.

Best Regards,

>Performing remat in new-ra can be broadly segregated into
>o Remat information construction (i.e. storing which values 
>can be possibly
>remat including expressions) during data flow information 
>accumulation in
>df.c. Some sort of a marker for expressions can be attached 
>for remat values
>(and their recomputation sequence in case of remat expressions).
>o Remat in absence of spill cost - Identify cases where remat is either
>trivial(eg. constant/label loads being spilled) or spilling of 
>defs happens
>before its first use (in spill everywhere approach and in case of IR
>spilling if spill is before the first use point). Performing 
>remat would
>consist of moving the defining remat expressions immediately 
>before its use.
>o Reconstructing webs which are involved in remat for the next pass.
>Remat would obviously involve taking care of not increasing 
>the lifetime of
>the operand webs as noted by Michael. Most of the remat 
>relating to ever
>live values such as frame pointer etc, should not increase the 
>Other cases such as parameter registers being considered for 
>remat (till
>they are redefined) need to be checked for not increasing the lifetime.
>Does this look feasible..
>Awaiting your valuable comments.
>Best Regards,
>>On Tue, 1 Jul 2003, Mukta Punjani, Noida wrote:
>>> [... you want to remat arbitrary expressions ...]
>>> This is the particular area which I intend to incorporate 
>i.e. pseudo
>>> handling in case of remat. More comments welcome..
>>The problems with general expression are:
>> a as noted in the comment you posted, the incremental graph builder
>>   needs to be changed to deal with the changed layout of those webs,
>>   which are operands of the expressions.  I.e. they need to be
>>   reconstructed.  For that these webs simply need to be 
>marked when an
>>   dependent expression was rematerialized.
>> b At the point of rematerialization it needs to be prooved, that the
>>   operands of it 1) are still live and 2) contain the same value they
>>   had when that expression was first used.
>>   (1) is necessary to not extend the livetime of the operand webs.
>>   That's needed because the rematerialization itself was 
>only a result
>>   of high register pressure (mostly), so extending livetime 
>>of even more
>>   operands is contra productive.
>>   (2) is obviously necessary, if one doesn't want to deal 
>>with the whole
>>   machinery of lacy code motion, which we don't want.
>>An easy way to implement b (1 and 2) is to note, that between 
>>the uses of
>>a web, and the definitions of it, no definition of the to be
>>rematerialized expression occured.  This information is already partly
>>constructed during construction of the conflict graph.  It's thrown
>>away currently.  During adding the conflict edges one could 
>add code to
>>mark these, though.

More information about the Gcc mailing list