RFC: GLIBCXX_DEBUG ScheduleDAG Patch

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

RFC: GLIBCXX_DEBUG ScheduleDAG Patch

dag-7
Attached is a patch to fix a GLIBCXX_DEBUG error in ScheduleDAGRRList.

The problem is that calls to CapturePred may reprioritize elements in the
priority queue, violating streak weak ordering requirements.

To fix this, I introduced a reference wrapper for containers to obtain access
to the SUnitVec used by std::priority_queue.   When CapturePred runs, it
calls updateNode which does a std::make_heap on the underlying SUnitVec.
This restores the correct ordering.

I believe this should also make the scheduler run more like it is supposed to.
Previously, the priority queue ordering was incorrect so we weren't necessarly
scheduling correctly.

The container_reference_wrapper part may be controversial.  So I want to
get some opinions on this before I submit it.

Thanks.

                                           -Dave

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

ScheduleDAG.patch (8K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

Evan Cheng-2
Hi Dave,

This looks great to me!

My only concern is the potential compile time impact. Do you see any?  
Also, please update the license portion to match what Chris sent out a  
couple of days ago. I don't see any issue with bringing Boost code  
into llvm tree. However, does it make sense to move the license to the  
top of the file? Chris?

Evan

On Dec 17, 2007, at 10:17 AM, David Greene wrote:

> Attached is a patch to fix a GLIBCXX_DEBUG error in ScheduleDAGRRList.
>
> The problem is that calls to CapturePred may reprioritize elements  
> in the
> priority queue, violating streak weak ordering requirements.
>
> To fix this, I introduced a reference wrapper for containers to  
> obtain access
> to the SUnitVec used by std::priority_queue.   When CapturePred  
> runs, it
> calls updateNode which does a std::make_heap on the underlying  
> SUnitVec.
> This restores the correct ordering.
>
> I believe this should also make the scheduler run more like it is  
> supposed to.
> Previously, the priority queue ordering was incorrect so we weren't  
> necessarly
> scheduling correctly.
>
> The container_reference_wrapper part may be controversial.  So I  
> want to
> get some opinions on this before I submit it.
>
> Thanks.
>
>                                           -Dave
> <ScheduleDAG.patch>_______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

dag-7
On Monday 17 December 2007 13:39, Evan Cheng wrote:

> My only concern is the potential compile time impact. Do you see any?

I don't notice any, but then I'm not particularly looking for that either.  
I'll run some tests.

I also accidentally included some debugging code I added to track
down this prioritization problem (the queue dumping code).  I'll remove
that before I commit the change.

I'll wait for Chris' comments re: licensing.

                                                  -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

Chris Lattner
On Mon, 17 Dec 2007, David Greene wrote:
> On Monday 17 December 2007 13:39, Evan Cheng wrote:
>> My only concern is the potential compile time impact. Do you see any?
> I don't notice any, but then I'm not particularly looking for that either.
> I'll run some tests.

Thanks.  5% slowdowns are generally not noticable, but we care :)

> I also accidentally included some debugging code I added to track
> down this prioritization problem (the queue dumping code).  I'll remove
> that before I commit the change.
>
> I'll wait for Chris' comments re: licensing.

Re licensing, we have no problem slurping in boost code.  Please do make
it follow the LLVM standards (80 cols and a doxygen comment above each
class saying what it is for).  For an example of how to do the license,
see include/llvm/ADT/scoped_ptr.h.

Thanks for finding these bugs David!

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

dag-7
On Monday 17 December 2007 19:48, Chris Lattner wrote:
> On Mon, 17 Dec 2007, David Greene wrote:
> > On Monday 17 December 2007 13:39, Evan Cheng wrote:
> >> My only concern is the potential compile time impact. Do you see any?
> >
> > I don't notice any, but then I'm not particularly looking for that
> > either. I'll run some tests.
>
> Thanks.  5% slowdowns are generally not noticable, but we care :)

After some very simple testing, I see slowdowns of around 1.7%.  I assume
this is ok, but want to check.

> Re licensing, we have no problem slurping in boost code.  Please do make
> it follow the LLVM standards (80 cols and a doxygen comment above each
> class saying what it is for).  For an example of how to do the license,
> see include/llvm/ADT/scoped_ptr.h.

No problem.

                                       -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

Evan Cheng-2

On Dec 20, 2007, at 2:43 PM, David Greene wrote:

> On Monday 17 December 2007 19:48, Chris Lattner wrote:
>> On Mon, 17 Dec 2007, David Greene wrote:
>>> On Monday 17 December 2007 13:39, Evan Cheng wrote:
>>>> My only concern is the potential compile time impact. Do you see  
>>>> any?
>>>
>>> I don't notice any, but then I'm not particularly looking for that
>>> either. I'll run some tests.
>>
>> Thanks.  5% slowdowns are generally not noticable, but we care :)
>
> After some very simple testing, I see slowdowns of around 1.7%.  I  
> assume
> this is ok, but want to check.

Can you clarify? Is this 1.7% slowdown of scheduling time or overall  
codegen time? If it's the later, then it seems a bit too much. Also,  
please test it with all the MultiSource/Applications.

Thanks,

Evan

>
>> Re licensing, we have no problem slurping in boost code.  Please  
>> do make
>> it follow the LLVM standards (80 cols and a doxygen comment above  
>> each
>> class saying what it is for).  For an example of how to do the  
>> license,
>> see include/llvm/ADT/scoped_ptr.h.
>
> No problem.
>
>                                        -Dave
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

dag-7
On Saturday 22 December 2007 02:33, Evan Cheng wrote:

> > After some very simple testing, I see slowdowns of around 1.7%.  I
> > assume
> > this is ok, but want to check.
>
> Can you clarify? Is this 1.7% slowdown of scheduling time or overall
> codegen time? If it's the later, then it seems a bit too much. Also,
> please test it with all the MultiSource/Applications.

It's 1.7% overall.

Does the nightly test build provide compile-time information?  I see from
the Makefile that it uses -time-passes.  I assume the "Today's LLC compile"
header on the nightly page comes from that and reflects the compile time
for the test.

                                          -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

Evan Cheng-2

On Jan 2, 2008, at 12:44 PM, David Greene wrote:

> On Saturday 22 December 2007 02:33, Evan Cheng wrote:
>
>>> After some very simple testing, I see slowdowns of around 1.7%.  I
>>> assume
>>> this is ok, but want to check.
>>
>> Can you clarify? Is this 1.7% slowdown of scheduling time or overall
>> codegen time? If it's the later, then it seems a bit too much. Also,
>> please test it with all the MultiSource/Applications.
>
> It's 1.7% overall.

That seems somewhat steep. Can you see how much of the scheduling  
slow down there is?

>
> Does the nightly test build provide compile-time information?  I  
> see from
> the Makefile that it uses -time-passes.  I assume the "Today's LLC  
> compile"
> header on the nightly page comes from that and reflects the compile  
> time
> for the test.

The better way is to add a custom report for this. See  
TEST.llc.Makefile and TEST.llc.report under llvm-test as an example.  
You can do make TEST=llc to generate custom reports. If this change  
can somehow be optionally controlled, then you can set it as llcbeta  
option and write a custom report that compare the time spend in some  
particular passes (TEST.beta-compare is an example, but it comparesf  
number instructions).

The biggest problem is right now time spent in scheduling is lumped  
into "DAG->DAG Instruction Selection" time because it's part of the  
pass. It would be nice if we can somehow bring it out.

Evan

>
>                                           -Dave
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

dag-7
On Friday 04 January 2008 12:59, Evan Cheng wrote:

> On Jan 2, 2008, at 12:44 PM, David Greene wrote:
> > On Saturday 22 December 2007 02:33, Evan Cheng wrote:
> >>> After some very simple testing, I see slowdowns of around 1.7%.  I
> >>> assume
> >>> this is ok, but want to check.
> >>
> >> Can you clarify? Is this 1.7% slowdown of scheduling time or overall
> >> codegen time? If it's the later, then it seems a bit too much. Also,
> >> please test it with all the MultiSource/Applications.
> >
> > It's 1.7% overall.
>
> That seems somewhat steep. Can you see how much of the scheduling
> slow down there is?

I got some times from the nightly report, so this is overall compile time.

The worst slowdown is on timberwolfmc "llc compile" which has a 5%
slowdown.  The JIT slows down 6%.

Everything else looks to be 1% or less.  In some cases the times with
the change are better, probably because this change gets rid of the "pop
everything off and push it back on" way of recreating the heap.[

> The better way is to add a custom report for this. See
> TEST.llc.Makefile and TEST.llc.report under llvm-test as an example.
> You can do make TEST=llc to generate custom reports. If this change
> can somehow be optionally controlled, then you can set it as llcbeta
> option and write a custom report that compare the time spend in some
> particular passes (TEST.beta-compare is an example, but it comparesf
> number instructions).

I'll look at this.  But it would be nice to get this change (or something
similar) in ASAP.  The scheduler is just broken right now.  So either we
have a compiler with a slight slowdown in some cases or we have a
compiler that exhibits undefined behavior.

> The biggest problem is right now time spent in scheduling is lumped
> into "DAG->DAG Instruction Selection" time because it's part of the
> pass. It would be nice if we can somehow bring it out.

Dunno if I can dig that deeply into this right now.  I'll have to look at
what's involved here.

                                             -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

dag-7
In reply to this post by Evan Cheng-2
On Friday 04 January 2008 12:59, Evan Cheng wrote:

> The better way is to add a custom report for this. See
> TEST.llc.Makefile and TEST.llc.report under llvm-test as an example.

Oops, I don't see these files.  I just updated this morning.

                                         -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

Tanya Lattner-2

>> The better way is to add a custom report for this. See
>> TEST.llc.Makefile and TEST.llc.report under llvm-test as an example.
>
> Oops, I don't see these files.  I just updated this morning.

They are in the test-suite module (aka llvm-test).

-Tanya

>
>                                         -Dave
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

greened
On Monday 21 January 2008 03:54:22 pm Tanya M. Lattner wrote:
> >> The better way is to add a custom report for this. See
> >> TEST.llc.Makefile and TEST.llc.report under llvm-test as an example.
> >
> > Oops, I don't see these files.  I just updated this morning.
>
> They are in the test-suite module (aka llvm-test).

Yes, that's where I looked.  Strange.

                                             -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

dag-7
On Monday 21 January 2008 22:42, David A. Greene wrote:
> On Monday 21 January 2008 03:54:22 pm Tanya M. Lattner wrote:
> > >> The better way is to add a custom report for this. See
> > >> TEST.llc.Makefile and TEST.llc.report under llvm-test as an example.
> > >
> > > Oops, I don't see these files.  I just updated this morning.
> >
> > They are in the test-suite module (aka llvm-test).
>
> Yes, that's where I looked.  Strange.

Oops, I was looking in the build directory.  I found it now.

                                         -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

dag-7
In reply to this post by dag-7
On Monday 21 January 2008 10:41, David Greene wrote:

> > >> Can you clarify? Is this 1.7% slowdown of scheduling time or overall
> > >> codegen time? If it's the later, then it seems a bit too much. Also,
> > >> please test it with all the MultiSource/Applications.
> > >
> > > It's 1.7% overall.
> >
> > That seems somewhat steep. Can you see how much of the scheduling
> > slow down there is?
>
> I got some times from the nightly report, so this is overall compile time.
>
> The worst slowdown is on timberwolfmc "llc compile" which has a 5%
> slowdown.  The JIT slows down 6%.
>
> Everything else looks to be 1% or less.  In some cases the times with
> the change are better, probably because this change gets rid of the "pop
> everything off and push it back on" way of recreating the heap.[

Just want to send a ping on this.  This patch is still waiting to go in.  Is
the compile time hit too much?  Note that sometimes compile time
improves with this patch.

I'd like to get this in ASAP so I can start merging other things back to
upstream.

                                                      -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

Evan Cheng-2
Have you tested this on SPEC (especially spec2006)? JIT slow down of  
6% is really too steep a price to pay.

I'll test this patch when I find some time.

Evan

On Feb 4, 2008, at 9:31 AM, David Greene wrote:

> On Monday 21 January 2008 10:41, David Greene wrote:
>
>>>>> Can you clarify? Is this 1.7% slowdown of scheduling time or  
>>>>> overall
>>>>> codegen time? If it's the later, then it seems a bit too much.  
>>>>> Also,
>>>>> please test it with all the MultiSource/Applications.
>>>>
>>>> It's 1.7% overall.
>>>
>>> That seems somewhat steep. Can you see how much of the scheduling
>>> slow down there is?
>>
>> I got some times from the nightly report, so this is overall  
>> compile time.
>>
>> The worst slowdown is on timberwolfmc "llc compile" which has a 5%
>> slowdown.  The JIT slows down 6%.
>>
>> Everything else looks to be 1% or less.  In some cases the times with
>> the change are better, probably because this change gets rid of the  
>> "pop
>> everything off and push it back on" way of recreating the heap.[
>
> Just want to send a ping on this.  This patch is still waiting to go  
> in.  Is
> the compile time hit too much?  Note that sometimes compile time
> improves with this patch.
>
> I'd like to get this in ASAP so I can start merging other things  
> back to
> upstream.
>
>                                                      -Dave
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

Török Edwin
In reply to this post by dag-7
David Greene wrote:
> Just want to send a ping on this.  This patch is still waiting to go in.  Is
> the compile time hit too much?  Note that sometimes compile time
> improves with this patch.
>
> I'd like to get this in ASAP so I can start merging other things back to
> upstream.
>  
Please see bug #2155, I am seeing an additional testsuite failure with
ScheduleDAG patch.
I am not saying there is any problem with ScheduleDAG patch itself, it
may be just exposing a previously hidden bug.

[I tried to add you to the Cc: of the bugreport, but bugzilla didn't
find your email address]

Best regards,
--Edwin
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RFC: GLIBCXX_DEBUG ScheduleDAG Patch

dag-7
On Friday 14 March 2008 17:08, Török Edwin wrote:

> David Greene wrote:
> > Just want to send a ping on this.  This patch is still waiting to go in.
> > Is the compile time hit too much?  Note that sometimes compile time
> > improves with this patch.
> >
> > I'd like to get this in ASAP so I can start merging other things back to
> > upstream.
>
> Please see bug #2155, I am seeing an additional testsuite failure with
> ScheduleDAG patch.
> I am not saying there is any problem with ScheduleDAG patch itself, it
> may be just exposing a previously hidden bug.
>
> [I tried to add you to the Cc: of the bugreport, but bugzilla didn't
> find your email address]

This patch has been superseded by a patch from Roman Levenstein.
The backtrace in the bug doesn't give much help.  I have seen a few more
GLIBCXX_DEBUG failures as I've updated my owrking copy.  I've had
trouble running "make install" lately, though, so I haven't tested in a while.

                                           -Dave

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev