<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Apr 30, 2013, at 11:00 AM, "Guo, Xiaoyi" <<a href="mailto:Xiaoyi.Guo@amd.com">Xiaoyi.Guo@amd.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div lang="EN-US" link="blue" vlink="purple" style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class="WordSection1" style="page: WordSection1;"><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Hi Eric,<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Sorry I wasn’t clear. The problem happened in the “source” pre-RA scheduler, which relies on DAG node ordering to schedule the nodes.</span></div></div></div></blockquote><div><br></div><div>In your case, Eric's suggestion was effectively "start implementing fast-isel". Which is not a bad idea if you want to reduce compile time and improve debug info.</div><div><br></div><div>I just really want pre-RA-sched=source to work as advertised.</div><div><br></div><div>-Andy</div><br><blockquote type="cite"><div lang="EN-US" link="blue" vlink="purple" style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class="WordSection1" style="page: WordSection1;"><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="color: rgb(31, 73, 125); font-family: Calibri, sans-serif; font-size: 11pt;"> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><b><span style="font-size: 10pt; font-family: Tahoma, sans-serif;">From:</span></b><span style="font-size: 10pt; font-family: Tahoma, sans-serif;"><span class="Apple-converted-space"> </span>Eric Christopher [<a href="mailto:echristo@gmail.com">mailto:echristo@gmail.com</a>]<span class="Apple-converted-space"> </span><br><b>Sent:</b><span class="Apple-converted-space"> </span>Tuesday, April 30, 2013 12:54 AM<br><b>To:</b><span class="Apple-converted-space"> </span>Guo, Xiaoyi<br><b>Cc:</b><span class="Apple-converted-space"> </span>LLVM Developers Mailing List<br><b>Subject:</b><span class="Apple-converted-space"> </span>Re: [LLVMdev] [PATCH] Propagate DAG node ordering during legalization and instruction selection<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div><div><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></p><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;">On Tue, Apr 30, 2013 at 12:48 AM, Guo, Xiaoyi <<a href="mailto:Xiaoyi.Guo@amd.com" target="_blank" style="color: purple; text-decoration: underline;">Xiaoyi.Guo@amd.com</a>> wrote:<o:p></o:p></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Hi,</span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">We’ve recently encountered a problem in our compiler where the line number in debug info jumps back and force even at O0. This is caused by DAG node ordering not being properly kept during legalization and instruction selection. There are still uncaught cases after applying the patch mentioned here.</span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span><o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;">Another option is checking how much, at O0, the fast instruction selector is falling back to the DAG - if you have one at least. Fast isel doesn't reorder to the degree that selection on the DAG does.<o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;">-eric<o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"> <o:p></o:p></div></div><blockquote style="border-style: none none none solid; border-left-color: rgb(204, 204, 204); border-left-width: 1pt; padding: 0in 0in 0in 6pt; margin-left: 4.8pt; margin-right: 0in;"><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">So I have decided to implement the approach suggested by Andy as below. i.e. maintain the node ordering as a field inside the DAG node and force anyone creating the DAG node to provide the ordering. When new DAG nodes are created inside DAG builder, DAG builder maintains the ordering of the current instruction being processed and provide that ordering to the DAG node creating routine. When new DAG nodes are created after DAG builder, e.g., during legalization, the original node’s ordering would be transferred to the new node.</span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Since it’s going to involve a lot of changes, I’d like to get feedback on the idea and the interface changes before I make changes to all the call sites.</span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Attached is a diff of the first batch of changes, which includes interface changes: a new wrapper class, new fields, interface changes to SelectionDAG::getXXX() functions.</span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Your feedback would be appreciated.</span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Thanks,</span><o:p></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Xiaoyi</span><o:p></o:p></div><div><p style="margin-right: 0in; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 10pt; font-family: Verdana, sans-serif;"><br><br> From: Andrew Trick <<a href="mailto:atrick@apple.com" target="_blank" style="color: purple; text-decoration: underline;">atrick@apple.com</a>><br> <br> Subject: Re: [PATCH] Propagate DAG node ordering during legalization and instruction selection<br> <br> Date: March 20, 2013 12:01:48 AM PDT<br> <br> To: Justin Holewinski <<a href="mailto:justin.holewinski@gmail.com" target="_blank" style="color: purple; text-decoration: underline;">justin.holewinski@gmail.com</a>><br> <br> Cc: llvm-commits <<a href="mailto:llvm-commits@cs.uiuc.edu" target="_blank" style="color: purple; text-decoration: underline;">llvm-commits@cs.uiuc.edu</a>></span><o:p></o:p></p><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><br> <br><br><br> On Mar 19, 2013, at 1:17 PM, Justin Holewinski <<a href="mailto:justin.holewinski@gmail.com" target="_blank" style="color: purple; text-decoration: underline;">justin.holewinski@gmail.com</a>> wrote:<br><br><br> Updated patch attached.<br> <br> <br> I've addressed the CSE during legalization issue. Now ordering is only propagated if the new node does not have an ordering (is zero), or has an ordering that is greater than the replaced node.<br> <br> <br> As for compile time, I think I may have had some other machine interference in the 8% figure. I can't reproduce that now, and both LLVM unit tests and LNT are not showing any statistically significant differences. I see some variation across runs in LNT, but it looks to be machine noise as I see both regressions and improvements in different benchmarks in different runs. I see +/- 0.5% in the unit tests, but that goes both ways. Both tests use release+asserts build.<br> <br><br><br> Your patch looks fine but doesn't go far enough. I'd like to add an IROrder field to SDNode (eventually we might be able to make it redundant with NodeId, although there would be temporary points at which nodes have to share an IROrder). That would remove any concerns about the compile-time of potentially frequent DenseMap lookup. But I really want to do it to help ensure that IROrder remains present and valid as a topological order. Then we don't need a "source order" scheduler at all, which would be really great. Just emit MIs for the selected nodes in place, and break some physreg interferences.<br><br> Ideally, anyone who creates an SDNode needs to track down the IROrder. Rather than propagating IROrder when we replace all uses, we would do it when we morph or CSE the node, similar to DebugLoc. Ensuring topological order is another aspect of the problem that can be dealt with later.<br><br> It's a big infrastructure project. But if you find any part of this plan will help you, progress toward that goal is welcome.<br><br> -Andy<br><br><br> On Tue, Mar 19, 2013 at 1:07 PM, Justin Holewinski <<a href="mailto:justin.holewinski@gmail.com" target="_blank" style="color: purple; text-decoration: underline;">justin.holewinski@gmail.com</a>> wrote:<br> <br><br> On Tue, Mar 19, 2013 at 12:47 PM, Justin Holewinski <<a href="mailto:justin.holewinski@gmail.com" target="_blank" style="color: purple; text-decoration: underline;">justin.holewinski@gmail.com</a>> wrote:<br> <br><br><br> On Tue, Mar 19, 2013 at 2:26 AM, Evan Cheng <<a href="mailto:evan.cheng@apple.com" target="_blank" style="color: purple; text-decoration: underline;">evan.cheng@apple.com</a>> wrote:<br> <br><br><br><br> Sent from my iPad<br><br> On Mar 18, 2013, at 2:02 PM, Justin Holewinski <<a href="mailto:justin.holewinski@gmail.com" target="_blank" style="color: purple; text-decoration: underline;">justin.holewinski@gmail.com</a>> wrote:<br> <br> <br><br> Compile-time impact is negligible for a release build on the unit tests. There is about an 8% impact with assertions enabled.<br><br><br> Unit tests are much too small for measuring compile time. 8% for assertion build is massive. Why are there such large discrepancy?<br><br><br> I've been trying to get measurements from LNT, but I'm getting too much run-to-run variation. A few benchmarks show significant changes (both positive and negative), but the affected benchmarks are diffe<o:p></o:p></div></div></div><table class="MsoNormalTable" border="0" cellspacing="3" cellpadding="0"><tbody><tr><td style="padding: 0.75pt;"></td></tr></tbody></table><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"> <o:p></o:p></div></div><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><br>_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu" style="color: purple; text-decoration: underline;">LLVMdev@cs.uiuc.edu</a><span class="Apple-converted-space"> </span> <span class="Apple-converted-space"> </span><a href="http://llvm.cs.uiuc.edu/" target="_blank" style="color: purple; text-decoration: underline;">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank" style="color: purple; text-decoration: underline;">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><o:p></o:p></p></blockquote></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div></div></div></div>_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></div></blockquote></div><br></body></html>