Re: Question about RTL code hoisting
On 03/25/10 10:19, Jie Zhang wrote: On 03/25/2010 11:22 PM, Jeff Law wrote: I never bothered to implement hoisting which touched hard regs -- I never thought the cost/benefit analysis made much sense. It's quite a bit more work to implement and code motion of hard regs is much more restricted than code motion involving just pseudos. Thanks Bernd and Jeff. This case is not common. I'm wondering how likely this kind of optimization pass will be accepted into GCC. If the code is clean and doesn't add significant compile-time overhead, it'd probably be accepted. Another way to fix it is teaching register allocator to allocate r0 to REG. But I guess it's more difficult. Well, the register allocator will already attempt to allocate REG to r0 -- when it sees a copy between a pseudo and a hard reg it will adjust its cost model appropriately to encourage the pseudo to be allocated to the hard reg (thus eliminating the copy). It's probably at least worth looking into why the pseudos in question aren't being assigned to the appropriate hard register to eliminate the copy. Another alternative would be to look at something like copy motion (see Morgan's text). I've always wondered if it was generally useful and what it's compile-time impact might be. Jeff
Re: Question about RTL code hoisting
On 03/25/2010 11:24 PM, Steven Bosscher wrote: On Thu, Mar 25, 2010 at 4:03 PM, Jie Zhang wrote: I just found that the current RTL code hoisting cannot optimize REG = ... if (cond) { r0 = REG; } else { r0 = REG; ... } to REG = ... r0 = REG; if (cond) { } else { ... } where REG is a pseudo register and r0 is a physical register. I have looked at the code of RTL hoisting pass. But I cannot find a simple way to extend it to deal with this case. Right, there are two issues: * HOIST doesn't handle hard registers * HOIST doesn't hoist reg-reg moves There is no easy way to add cost metrics to hoist reg-reg moves, and handling hard regs is an even bigger problem. What is the original code? I (well, by now: we) have patches in the works for GCC 4.6 that add code hoisting to GIMPLE (see PR23286), perhaps that solves this case for you. I'm not sure if I can make the test case public. I need to ask. I'm afraid gimple cannot help this. r0 is here because it's used for passing argument to callees. This issue is only exposed when expanded to RTL. And the hoisting pass is only enabled when -Os. So I'm going to implement another hoisting pass to do this optimization. Is it a good idea? To add duplicate functionality? No. I'm not going to add duplicate functionality. What I'm going to do is only handle "hard-reg = pseudo-reg" case. Does anyone know if there is an existing pass which should have handled or be able to be easily adapted to handle this case? Hoisting should handle it, bui Can you open a new PR and make it block PR33828, please? If I can publish the test case, yes. Or I have to rewrite a test case. -- Jie Zhang CodeSourcery (650) 331-3385 x735
Re: Question about RTL code hoisting
On 03/25/2010 11:22 PM, Jeff Law wrote: On 03/25/10 09:14, Bernd Schmidt wrote: On 03/25/2010 04:03 PM, Jie Zhang wrote: I just found that the current RTL code hoisting cannot optimize REG = ... if (cond) { r0 = REG; } else { r0 = REG; ... } to REG = ... r0 = REG; if (cond) { } else { ... } where REG is a pseudo register and r0 is a physical register. I have looked at the code of RTL hoisting pass. But I cannot find a simple way to extend it to deal with this case. And the hoisting pass is only enabled when -Os. So I'm going to implement another hoisting pass to do this optimization. Is it a good idea? Does anyone know if there is an existing pass which should have handled or be able to be easily adapted to handle this case? Thanks! Isn't this similar to crossjumping, except done in the other direction? Yes, though the implementation is completely different. Hoisting computes which blocks compute specific expressions, then determines if all paths from a point compute the same expression and if so, moves the multiple computations to a single location. cross jumping works by matching RTL bits at the end of blocks. I never bothered to implement hoisting which touched hard regs -- I never thought the cost/benefit analysis made much sense. It's quite a bit more work to implement and code motion of hard regs is much more restricted than code motion involving just pseudos. Thanks Bernd and Jeff. This case is not common. I'm wondering how likely this kind of optimization pass will be accepted into GCC. Another way to fix it is teaching register allocator to allocate r0 to REG. But I guess it's more difficult. Jie
Re: Question about RTL code hoisting
On Thu, Mar 25, 2010 at 4:03 PM, Jie Zhang wrote: > I just found that the current RTL code hoisting cannot optimize > > REG = ... > if (cond) > { > r0 = REG; > > } > else > { > r0 = REG; > ... > } > > to > > > REG = ... > r0 = REG; > if (cond) > { > > } > else > { > ... > } > > where REG is a pseudo register and r0 is a physical register. I have looked > at the code of RTL hoisting pass. But I cannot find a simple way to extend > it to deal with this case. Right, there are two issues: * HOIST doesn't handle hard registers * HOIST doesn't hoist reg-reg moves There is no easy way to add cost metrics to hoist reg-reg moves, and handling hard regs is an even bigger problem. What is the original code? I (well, by now: we) have patches in the works for GCC 4.6 that add code hoisting to GIMPLE (see PR23286), perhaps that solves this case for you. > And the hoisting pass is only enabled when -Os. > So I'm going to implement another hoisting pass to do this optimization. Is > it a good idea? To add duplicate functionality? No. > Does anyone know if there is an existing pass which should > have handled or be able to be easily adapted to handle this case? Hoisting should handle it, bui Can you open a new PR and make it block PR33828, please? Ciao! Steven
Re: Question about RTL code hoisting
On 03/25/10 09:14, Bernd Schmidt wrote: On 03/25/2010 04:03 PM, Jie Zhang wrote: I just found that the current RTL code hoisting cannot optimize REG = ... if (cond) { r0 = REG; } else { r0 = REG; ... } to REG = ... r0 = REG; if (cond) { } else { ... } where REG is a pseudo register and r0 is a physical register. I have looked at the code of RTL hoisting pass. But I cannot find a simple way to extend it to deal with this case. And the hoisting pass is only enabled when -Os. So I'm going to implement another hoisting pass to do this optimization. Is it a good idea? Does anyone know if there is an existing pass which should have handled or be able to be easily adapted to handle this case? Thanks! Isn't this similar to crossjumping, except done in the other direction? Yes, though the implementation is completely different. Hoisting computes which blocks compute specific expressions, then determines if all paths from a point compute the same expression and if so, moves the multiple computations to a single location. cross jumping works by matching RTL bits at the end of blocks. I never bothered to implement hoisting which touched hard regs -- I never thought the cost/benefit analysis made much sense. It's quite a bit more work to implement and code motion of hard regs is much more restricted than code motion involving just pseudos. jeff Bernd
Re: Question about RTL code hoisting
On Thu, Mar 25, 2010 at 4:14 PM, Bernd Schmidt wrote: > On 03/25/2010 04:03 PM, Jie Zhang wrote: >> I just found that the current RTL code hoisting cannot optimize >> >> REG = ... >> if (cond) >> { >> r0 = REG; >> >> } >> else >> { >> r0 = REG; >> ... >> } >> >> to >> >> >> REG = ... >> r0 = REG; >> if (cond) >> { >> >> } >> else >> { >> ... >> } >> >> where REG is a pseudo register and r0 is a physical register. I have >> looked at the code of RTL hoisting pass. But I cannot find a simple way >> to extend it to deal with this case. And the hoisting pass is only >> enabled when -Os. So I'm going to implement another hoisting pass to do >> this optimization. Is it a good idea? Does anyone know if there is an >> existing pass which should have handled or be able to be easily adapted >> to handle this case? Thanks! > > Isn't this similar to crossjumping, except done in the other direction? Yes. "head merging" if you will. I have a patch for this, and intend to submit it for GCC 4.6. Ciao! Steven
Re: Question about RTL code hoisting
On 03/25/2010 04:03 PM, Jie Zhang wrote: > I just found that the current RTL code hoisting cannot optimize > > REG = ... > if (cond) > { > r0 = REG; > > } > else > { > r0 = REG; > ... > } > > to > > > REG = ... > r0 = REG; > if (cond) > { > > } > else > { > ... > } > > where REG is a pseudo register and r0 is a physical register. I have > looked at the code of RTL hoisting pass. But I cannot find a simple way > to extend it to deal with this case. And the hoisting pass is only > enabled when -Os. So I'm going to implement another hoisting pass to do > this optimization. Is it a good idea? Does anyone know if there is an > existing pass which should have handled or be able to be easily adapted > to handle this case? Thanks! Isn't this similar to crossjumping, except done in the other direction? Bernd
Question about RTL code hoisting
I just found that the current RTL code hoisting cannot optimize REG = ... if (cond) { r0 = REG; } else { r0 = REG; ... } to REG = ... r0 = REG; if (cond) { } else { ... } where REG is a pseudo register and r0 is a physical register. I have looked at the code of RTL hoisting pass. But I cannot find a simple way to extend it to deal with this case. And the hoisting pass is only enabled when -Os. So I'm going to implement another hoisting pass to do this optimization. Is it a good idea? Does anyone know if there is an existing pass which should have handled or be able to be easily adapted to handle this case? Thanks! -- Jie Zhang CodeSourcery (650) 331-3385 x735