RE: [Patch,rtl Optimization]: Better register pressure estimate for Loop Invariant Code Motion.

[Ajit Kumar Agarwal <ajit.kumar.agarwal@xilinx.com>]

-----Original Message-----
From: Bernd Schmidt [mailto:bschmidt@redhat.com] 
Sent: Wednesday, December 09, 2015 7:34 PM
To: Ajit Kumar Agarwal; Richard Biener
Cc: Jeff Law; GCC Patches; Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala
Subject: Re: [Patch,rtl Optimization]: Better register pressure estimate for Loop Invariant Code Motion.

On 12/09/2015 12:22 PM, Ajit Kumar Agarwal wrote:
>
> This is because the available_regs = 6 and the regs_needed = 1 and 
> new_regs = 0 and the regs_used = 10.  As the reg_used that are based 
> on the Liveness given above is greater than the available_regs, then
 > it's candidate of spill and the estimate_register_pressure calculates  > the spill cost. This spill cost is greater than inv_cost and gain  > comes to be negative. The disables the loop invariant for the above  > testcase.

>>As far as I can tell this loop does not lead to a spill. Hence, failure of this testcase would suggest there is something wrong with your idea.

As far as I can see there is nothing wrong with the idea, the existing implementation of the calculation of available_regs results to 6 which is not the case for this
testcase. The estimate of regs_used based on the Liveness ( idea behind this patch)  is correct, but the incorrect estimate of the available_regs (6) results in the gain to be negative. 

>> +  FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)  {

>>Formatting.

>> +    /* Loop Liveness is based on the following proprties.

>>"properties"

I will incorporate the change.

>> +       we only require to calculate the set of objects that are live at
>> +       the birth or the header of the loop.
>> +       We don't need to calculate the live through the Loop considering
>> +       Live in and Live out of all the basic blocks of the Loop. This is
>> +       because the set of objects. That are live-in at the birth or header
>> +       of the loop will be live-in at every node in the Loop.
>> +       If a v live out at the header of the loop then the variable is live-in
>> +       at every node in the Loop. To prove this, Consider a Loop L with header
>> +       h such that The variable v defined at d is live-in at h. Since v is live
>> +       at h, d is not part of L. This follows from the dominance property, i.e.
>> +       h is strictly dominated by d. Furthermore, there exists a path from h to
>> +       a use of v which does not go through d. For every node of the loop, p,
>> +       since the loop is strongly connected Component of the CFG, there exists
>> +       a path, consisting only of nodes of L from p to h. Concatenating those
>> +       two paths prove that v is live-in and live-out Of p.  */

>>Please Refrain From Randomly Capitalizing Words, and please also fix the grammar ("set of objects. That are live-in"). These problems make this comment (and also your emails) >>extremely hard to read.

>>Partly for that reason, I can't quite make up my mind whether this patch makes things better or just different. The testcase failure makes me think it's probably not an improvement.

I'll correct it. I am seeing the gains for Mibench/EEMBC benchmarks for Microblaze target with this patch. I will run SPEC CPU 2000  benchmarks for i386 with this patch.

>> +    bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (loop->header));
>> +    bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_OUT 
>> + (loop->header));

>>Formatting.

I'll incorporate the change.

Thanks & Regards
Ajit

Bernd