[LLVMdev] [PATCH] Propagate DAG node ordering during legalization and instruction selection

Tue Apr 30 17:32:40 PDT 2013

On Tue, Apr 30, 2013 at 5:18 PM, Andrew Trick <atrick at apple.com> wrote:

>
> On Apr 30, 2013, at 11:00 AM, "Guo, Xiaoyi" <Xiaoyi.Guo at amd.com> wrote:
>
> Hi Eric,****
>
> Sorry I wasn’t clear. The problem happened in the “source” pre-RA
> scheduler, which relies on DAG node ordering to schedule the nodes.
>
>
> 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.
>
> I just really want pre-RA-sched=source to work as advertised.
>

We have been hit by this to varying degrees in the past.  The hard part a
lot of the time is just tracing through the SDAG transforms and finding
where the ordering information is being lost.  +1 for a simple, consistent,
well-maintained API.

The changes I implemented earlier were intended to minimize API churn to
LLVM to make it easier to merge.  I would love to see a more "finished"
solution, especially one that considers chains of operations being
generated during legalization!

>
> -Andy
>
>
> *From:* Eric Christopher [mailto:echristo at gmail.com <echristo at gmail.com>]
> *Sent:* Tuesday, April 30, 2013 12:54 AM
> *To:* Guo, Xiaoyi
> *Cc:* LLVM Developers Mailing List
> *Subject:* Re: [LLVMdev] [PATCH] Propagate DAG node ordering during
> legalization and instruction selection****
> ** **
> ** **
>
> ** **
> On Tue, Apr 30, 2013 at 12:48 AM, Guo, Xiaoyi <Xiaoyi.Guo at amd.com> wrote:*
> ***
> Hi,****
>  ****
> 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.****
>  ****
> ** **
> 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.****
> ** **
> -eric****
>  ****
>
> 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.****
>  ****
> 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.****
>  ****
> 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.****
>  ****
> Your feedback would be appreciated.****
>  ****
> Thanks,****
> Xiaoyi****
>
>
>
>     From: Andrew Trick <atrick at apple.com>
>
>     Subject: Re: [PATCH] Propagate DAG node ordering during legalization
> and instruction selection
>
>     Date: March 20, 2013 12:01:48 AM PDT
>
>     To: Justin Holewinski <justin.holewinski at gmail.com>
>
>     Cc: llvm-commits <llvm-commits at cs.uiuc.edu>****
>
>
>
>
>     On Mar 19, 2013, at 1:17 PM, Justin Holewinski <
> justin.holewinski at gmail.com> wrote:
>
>
>         Updated patch attached.
>
>
>         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.
>
>
>         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.
>
>
>
>     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.
>
>     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.
>
>     It's a big infrastructure project. But if you find any part of this
> plan will help you, progress toward that goal is welcome.
>
>     -Andy
>
>
>         On Tue, Mar 19, 2013 at 1:07 PM, Justin Holewinski <
> justin.holewinski at gmail.com> wrote:
>
>
>             On Tue, Mar 19, 2013 at 12:47 PM, Justin Holewinski <
> justin.holewinski at gmail.com> wrote:
>
>
>
>                 On Tue, Mar 19, 2013 at 2:26 AM, Evan Cheng <
> evan.cheng at apple.com> wrote:
>
>
>
>
>                     Sent from my iPad
>
>                     On Mar 18, 2013, at 2:02 PM, Justin Holewinski <
> justin.holewinski at gmail.com> wrote:
>
>
>
>                     Compile-time impact is negligible for a release build
> on the unit tests.  There is about an 8% impact with assertions enabled.
>
>
>                     Unit tests are much too small for measuring compile
> time. 8% for assertion build is massive. Why are there such large
> discrepancy?
>
>
>                 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
> ****
>  ****
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev****
>
> ** **
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>

-- 

Thanks,

Justin Holewinski
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130430/1bdb345e/attachment.html>