On Mar 25, 2007, at 2:21 AM, Chris Lattner wrote:> On Sat, 24 Mar 2007, Christopher Lamb wrote: >> It seems to me that there is potential for doing some target >> independent loop >> invariant optimizations in the back end, but prior to instruction >> selection. > > I assume you mean after instruction selection?I assumed that to be target independent the pass would need to be before instruction selection, but I guess if the pass more like the basic block/ branch analysis that would make sense.> >> For instance, I noticed that the loop invariant constant generated >> for a loop >> bounds check is still stuck inside the loop. Likewise constant >> address >> generated for globals accessed within a loop are generated on each >> iteration, >> even though they are invariant. > > Yes, this is a known issue. The plan is to implement a machine- > code level > pass that hoists machine instrs out of loops after instruction > selection > has been performed. This is important, because isel is the pass that > exposes most of the issues that need hoisting (e.g. load immediate > instructions, etc).Isn't it possible to tell that certain DAG nodes are loop invariant prior to instruction selection, such as a constant or global address node?> >> I'm most familiar with LLVM's target interface and code gen and >> I'm not fully >> up to speed on the optimization framework. Is there an existing >> optimization >> pass that handles these cases that I've failed to properly enable >> or hook >> into? Is there something that inherently prevents these from being >> target >> independent optimizations, requiring a target specific opt pass? >> Is this >> simply an optimization pass that hasn't been implemented yet, but >> is a good >> idea? > > The later. On targets with few registers, LICM can be very bad. > Our plan > is to implement rematerialization in the register allocator to > counteract > this. In any case, I think that LICM should definitely be done, and > targets can choose to use it or not based on their register file, > before > remat is done.Is there more information (PR?) on the schedule for this work and who is involved? I may not be experienced enough to make much of a contribution yet, but I'd like to keep tabs on it. -- Christopher Lamb christopher.lamb at gmail.com -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070325/9f26fc81/attachment.html>
On 3/25/07, Christopher Lamb <christopher.lamb at gmail.com> wrote:> Isn't it possible to tell that certain DAG nodes are loop invariant prior to > instruction selection, such as a constant or global address node?Only in part. Selection of some nodes generates duplicate code in some backends and not others. A global that requires 2 instructions to load, as on alpha (where one of those instructions may sometimes be redundant with other loads of globals, but not always), may benfit from hoisting whereas on some architectures hoisting the load out may increase register pressure with little benefit (or the addressing is trivially folded into the load, etc). The current thinking is a LICM and CSE type pass needs to operate on machine code (in a target independent way) so that the particularities of each architecture are exposed (by virtue of having the machine code selected). There isn't also a way to remove duplicate instructions that are introduced as an artifact of the architecture in the DAG stage. DAG nodes are not a 1:1 mapping onto selected instructions. Andrew
On Sun, 25 Mar 2007, Christopher Lamb wrote:>> I assume you mean after instruction selection? > > I assumed that to be target independent the pass would need to be before > instruction selection, but I guess if the pass more like the basic block/ > branch analysis that would make sense.Right. We already have LICM that runs before isel. THe problem is that isel exposes new opportunities for LICM.>> Yes, this is a known issue. The plan is to implement a machine-code level >> pass that hoists machine instrs out of loops after instruction selection >> has been performed. This is important, because isel is the pass that >> exposes most of the issues that need hoisting (e.g. load immediate >> instructions, etc). > > Isn't it possible to tell that certain DAG nodes are loop invariant prior to > instruction selection, such as a constant or global address node?Yes. The problem is that selectiondags are currently only built per-basic block, so you can't do whole-function code motion xforms on them. In the long term, this is certainly something I want to fix. See Cliff Click's thesis for some of the things you can do with whole-function dags.>> targets can choose to use it or not based on their register file, before >> remat is done. > > Is there more information (PR?) on the schedule for this work and who is > involved? I may not be experienced enough to make much of a contribution yet, > but I'd like to keep tabs on it.We have very simple remat implemented, basically for instructions that have no input registers and define a single output register. We don't have any immediately-short-term plans to implement either machine code LICM or the rest of remat. In the medium term (6-18 months), I'd like to start a major redesign project for the register allocator. The goal would be to build a framework to handle standard techniques like shrink wrapping, live rangle splitting, remat, ra resched, etc. In the shorter term, there are still lots of other things that can be improved, on shorter time scales, for now we are focusing on those. -Chris -- http://nondot.org/sabre/ http://llvm.org/
On Sun, 25 Mar 2007, Andrew Lenharth wrote:> trivially folded into the load, etc). The current thinking is a LICM > and CSE type pass needs to operate on machine code (in a target > independent way) so that the particularities of each architecture are > exposed (by virtue of having the machine code selected). There isn't > also a way to remove duplicate instructions that are introduced as an > artifact of the architecture in the DAG stage. DAG nodes are not a > 1:1 mapping onto selected instructions.Andrew is right, but after the isel pass runs, there *should* be a 1-1 mapping between target dag nodes and machine instrs. I say "should", because we don't always have that at this point, but it is a goal going forward. -Chris -- http://nondot.org/sabre/ http://llvm.org/