<HTML><BODY style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><DIV><SPAN class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><BR class="Apple-interchange-newline"></SPAN> </DIV><BR><DIV><DIV>On Mar 25, 2007, at 2:21 AM, Chris Lattner wrote:</DIV><BR class="Apple-interchange-newline"><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">On Sat, 24 Mar 2007, Christopher Lamb wrote:</DIV> <BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">It seems to me that there is potential for doing some target independent loop<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">invariant optimizations in the back end, but prior to instruction selection.</DIV> </BLOCKQUOTE><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">I assume you mean after instruction selection?</DIV></BLOCKQUOTE><DIV><BR class="khtml-block-placeholder"></DIV><DIV>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.</DIV><BR><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV> <BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">For instance, I noticed that the loop invariant constant generated for a loop<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">bounds check is still stuck inside the loop. Likewise constant address<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">generated for globals accessed within a loop are generated on each iteration,<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">even though they are invariant.</DIV> </BLOCKQUOTE><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Yes, this is a known issue.<SPAN class="Apple-converted-space"> </SPAN>The plan is to implement a machine-code level<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">pass that hoists machine instrs out of loops after instruction selection<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">has been performed.<SPAN class="Apple-converted-space"> </SPAN>This is important, because isel is the pass that<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">exposes most of the issues that need hoisting (e.g. load immediate<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">instructions, etc).</DIV></BLOCKQUOTE><DIV><BR class="khtml-block-placeholder"></DIV><DIV>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?</DIV><BR><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV> <BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">I'm most familiar with LLVM's target interface and code gen and I'm not fully<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">up to speed on the optimization framework. Is there an existing optimization<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">pass that handles these cases that I've failed to properly enable or hook<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">into? Is there something that inherently prevents these from being target<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">independent optimizations, requiring a target specific opt pass? Is this<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">simply an optimization pass that hasn't been implemented yet, but is a good<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">idea?</DIV> </BLOCKQUOTE><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">The later.<SPAN class="Apple-converted-space"> </SPAN>On targets with few registers, LICM can be very bad.<SPAN class="Apple-converted-space"> </SPAN>Our plan<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">is to implement rematerialization in the register allocator to counteract<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">this.<SPAN class="Apple-converted-space"> </SPAN>In any case, I think that LICM should definitely be done, and<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">targets can choose to use it or not based on their register file, before<SPAN class="Apple-converted-space"> </SPAN></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">remat is done.</DIV></BLOCKQUOTE><DIV><BR class="khtml-block-placeholder"></DIV><DIV>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.</DIV><DIV><BR class="khtml-block-placeholder"></DIV></DIV><DIV><DIV><DIV>--</DIV><DIV>Christopher Lamb</DIV><DIV><A href="mailto:christopher.lamb@gmail.com">christopher.lamb@gmail.com</A></DIV></DIV><BR class="khtml-block-placeholder"></DIV><BR></BODY></HTML>