Hello Jeff: -----Original Message----- From: Jeff Law [mailto:l...@redhat.com] Sent: Tuesday, November 17, 2015 4:30 AM To: Ajit Kumar Agarwal; GCC Patches Cc: Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala Subject: Re: [RFC, Patch]: Optimized changes in the register used inside loop for LICM and IVOPTS.
On 11/16/2015 10:36 AM, Ajit Kumar Agarwal wrote: >> For Induction variable optimization on tree SSA representation, the >> register used logic is based on the number of phi nodes at the loop >> header to represent the liveness at the loop. Current Logic used >> only the number of phi nodes at the loop header. Changes are made to >> represent the phi operands also live at the loop. Thus number of phi >> operands also gets incremented in the number of registers used. >>But my question is why is the # of PHI operands useful here. You'd have a >>stronger argument if it was the number of unique operands in each PHI. >> While I don't doubt this patch improved things, I think it's just putting a >> band-aid over the problem. >>I think anything that just looks at PHIs or at register liveness at loop >>boundaries is inherently underestimating the register pressure implications >>of code motion from inside to outside a >>loop. >>If an object is pulled out of the loop, then it's going to conflict with >>nearly every object that births in the loop (because the object being moved >>now has to live throughout the loop). >>There's exceptions, but I doubt they >>matter in practice. The object is also going to conflict with anything else >>that is live through the loop. At least that's how it seems to me at first >>>>thought. >>So build the set of objects (SSA_NAMEs) that either birth or are live through >>the loop that have the same type class as the object we want to hoist out of >>the loop (scalar, floating point, >>vector). Use that set of objects to >>estimate register pressure. I agree with the above. To add up on the above, we only require to calculate the set of objects ( SSA_NAMES) 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 (SSA_NAMES) 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. On top of live-in at the birth or header of the loop as proven above, if we calculate the Live out of the exit block of the block and Live-in at the destination Edge of the exit block of the loops. This consider the liveness outside of the Loop. The above two cases forms the basis of better estimator for register pressure as far as LICM is concerned. If you agree with the above, I will implement add the above in the patch for register_used estimates for better estimate of register pressure for LICM. Thanks & Regards Ajit >>It won't be exact because some of those objects could end up coloring the >>same. BUt it's probably still considerably more accurate than what we have >>now. >>I suspect that would be a better estimator for register pressure as far as >>LICM is concerned. jeff
