Problems with instruction scheduling

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

Problems with instruction scheduling

Paweł Bylica
Hi,

I'm trying to fix PR23405 - assert failure during instruction scheduling in llc. I have related but more generic questions.

Is there any higher level description of the algorithm used for instruction scheduling in this case? It is new area for me and I would love to see bigger picture.

My currently smallest test case contains 90 DAG nodes. I got it by manually reducing IR previously reduced by bugpoint. Is there a way to reduce it more, maybe on DAG level? Identifying the part of the DAG that causes the problem could be helpful.

- Paweł

_______________________________________________
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: Problems with instruction scheduling

Paweł Bylica
Any comments?

On Thu, May 21, 2015 at 4:05 PM Paweł Bylica <[hidden email]> wrote:
Hi,

I'm trying to fix PR23405 - assert failure during instruction scheduling in llc. I have related but more generic questions.

Is there any higher level description of the algorithm used for instruction scheduling in this case? It is new area for me and I would love to see bigger picture.

My currently smallest test case contains 90 DAG nodes. I got it by manually reducing IR previously reduced by bugpoint. Is there a way to reduce it more, maybe on DAG level? Identifying the part of the DAG that causes the problem could be helpful.

- Paweł

_______________________________________________
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: Problems with instruction scheduling

Hal Finkel
----- Original Message -----
> From: "Paweł Bylica" <[hidden email]>
> To: "LLVMdev" <[hidden email]>
> Sent: Friday, May 22, 2015 8:45:11 AM
> Subject: Re: [LLVMdev] Problems with instruction scheduling
>
>
>
> Any comments?

Not in particular, but I think we're pretty close to applying a rewrite by Jonas Paulsson (cc'd). If you can't find the discussions on the mailing list, please let us know.

 -Hal

>
>
> On Thu, May 21, 2015 at 4:05 PM Paweł Bylica < [hidden email] >
> wrote:
>
>
>
> Hi,
>
>
> I'm trying to fix PR23405 - assert failure during instruction
> scheduling in llc. I have related but more generic questions.
>
>
> Is there any higher level description of the algorithm used for
> instruction scheduling in this case? It is new area for me and I
> would love to see bigger picture.
>
>
> My currently smallest test case contains 90 DAG nodes. I got it by
> manually reducing IR previously reduced by bugpoint. Is there a way
> to reduce it more, maybe on DAG level? Identifying the part of the
> DAG that causes the problem could be helpful.
>
>
>
> - Paweł
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
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: Problems with instruction scheduling

Paweł Bylica
On Fri, May 22, 2015 at 4:09 PM Hal Finkel <[hidden email]> wrote:
----- Original Message -----
> From: "Paweł Bylica" <[hidden email]>
> To: "LLVMdev" <[hidden email]>
> Sent: Friday, May 22, 2015 8:45:11 AM
> Subject: Re: [LLVMdev] Problems with instruction scheduling
>
>
>
> Any comments?

Not in particular, but I think we're pretty close to applying a rewrite by Jonas Paulsson (cc'd). If you can't find the discussions on the mailing list, please let us know.

 -Hal

Thanks for the response.

Do you mean "ScheduleDAGInstrs::buildSchedGraph() rewritten" http://reviews.llvm.org/D8705 ? If yes it is not the same fragment of code. 

- Paweł
 
>
>
> On Thu, May 21, 2015 at 4:05 PM Paweł Bylica < [hidden email] >
> wrote:
>
>
>
> Hi,
>
>
> I'm trying to fix PR23405 - assert failure during instruction
> scheduling in llc. I have related but more generic questions.
>
>
> Is there any higher level description of the algorithm used for
> instruction scheduling in this case? It is new area for me and I
> would love to see bigger picture.
>
>
> My currently smallest test case contains 90 DAG nodes. I got it by
> manually reducing IR previously reduced by bugpoint. Is there a way
> to reduce it more, maybe on DAG level? Identifying the part of the
> DAG that causes the problem could be helpful.
>
>
>
> - Paweł
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
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: Problems with instruction scheduling

Hal Finkel
----- Original Message -----

> From: "Paweł Bylica" <[hidden email]>
> To: "Hal Finkel" <[hidden email]>
> Cc: "LLVMdev" <[hidden email]>, "Jonas Paulsson" <[hidden email]>
> Sent: Friday, May 22, 2015 9:19:14 AM
> Subject: Re: [LLVMdev] Problems with instruction scheduling
>
>
>
> On Fri, May 22, 2015 at 4:09 PM Hal Finkel < [hidden email] > wrote:
>
>
> ----- Original Message -----
> > From: "Paweł Bylica" < [hidden email] >
> > To: "LLVMdev" < [hidden email] >
> > Sent: Friday, May 22, 2015 8:45:11 AM
> > Subject: Re: [LLVMdev] Problems with instruction scheduling
> >
> >
> >
> > Any comments?
>
> Not in particular, but I think we're pretty close to applying a
> rewrite by Jonas Paulsson (cc'd). If you can't find the discussions
> on the mailing list, please let us know.
>
> -Hal
>
>
>
> Thanks for the response.
>
>
> Do you mean "ScheduleDAGInstrs::buildSchedGraph() rewritten"
> http://reviews.llvm.org/D8705 ? If yes it is not the same fragment
> of code.

Ah, I see. That bug deals with ScheduleDAGRRList.

Andy, I thought that with the transition to source-order SDAG scheduling (and using MI scheduling instead), we were going to essentially get rid of that code. Is that right?

 -Hal

>
>
> - Paweł
>
>
> >
> >
> > On Thu, May 21, 2015 at 4:05 PM Paweł Bylica < [hidden email] >
> > wrote:
> >
> >
> >
> > Hi,
> >
> >
> > I'm trying to fix PR23405 - assert failure during instruction
> > scheduling in llc. I have related but more generic questions.
> >
> >
> > Is there any higher level description of the algorithm used for
> > instruction scheduling in this case? It is new area for me and I
> > would love to see bigger picture.
> >
> >
> > My currently smallest test case contains 90 DAG nodes. I got it by
> > manually reducing IR previously reduced by bugpoint. Is there a way
> > to reduce it more, maybe on DAG level? Identifying the part of the
> > DAG that causes the problem could be helpful.
> >
> >
> >
> > - Paweł
> > _______________________________________________
> > LLVM Developers mailing list
> > [hidden email] http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>

--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
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: Problems with instruction scheduling

Andrew Trick

> On May 22, 2015, at 8:39 AM, Hal Finkel <[hidden email]> wrote:
>
> ----- Original Message -----
>> From: "Paweł Bylica" <[hidden email]>
>> To: "Hal Finkel" <[hidden email]>
>> Cc: "LLVMdev" <[hidden email]>, "Jonas Paulsson" <[hidden email]>
>> Sent: Friday, May 22, 2015 9:19:14 AM
>> Subject: Re: [LLVMdev] Problems with instruction scheduling
>>
>>
>>
>> On Fri, May 22, 2015 at 4:09 PM Hal Finkel < [hidden email] > wrote:
>>
>>
>> ----- Original Message -----
>>> From: "Paweł Bylica" < [hidden email] >
>>> To: "LLVMdev" < [hidden email] >
>>> Sent: Friday, May 22, 2015 8:45:11 AM
>>> Subject: Re: [LLVMdev] Problems with instruction scheduling
>>>
>>>
>>>
>>> Any comments?
>>
>> Not in particular, but I think we're pretty close to applying a
>> rewrite by Jonas Paulsson (cc'd). If you can't find the discussions
>> on the mailing list, please let us know.
>>
>> -Hal
>>
>>
>>
>> Thanks for the response.
>>
>>
>> Do you mean "ScheduleDAGInstrs::buildSchedGraph() rewritten"
>> http://reviews.llvm.org/D8705 ? If yes it is not the same fragment
>> of code.

It looks like I had a trivial request for code organization, otherwise that patch is probably fine. It’s unrelated to the thread though.

> Ah, I see. That bug deals with ScheduleDAGRRList.
>
> Andy, I thought that with the transition to source-order SDAG scheduling (and using MI scheduling instead), we were going to essentially get rid of that code. Is that right?


Right, Pawel’s bug is in SDAG scheduling. I would like this to go away, but the reality is that unless you use fast-isel, you still rely on this algorithm to serialize the DAG and resolve physical register interferences, usually when a flag-producing instruction like ADD or CMP feeds multiple uses, like ADC or CMOVE for example. There is some nasty backtracking happening to handle this full of rarely touched corner cases—it’s been problematic for a long time with larger-than-legal IR types.

I hoped most of these problems would go away with Pawel’s fix for PR22304. It looks like he’s hitting another one, and I haven’t had time to step through the scheduler trace. It’s just a matter of figuring out how that code gets stuck in a corner and can’t get out. I don’t have any special power for doing this, as I have to reparse the code each time I look at it. I will say that there should be a way for the code to get unstuck by spilling EFLAGS; see InsertCopiesAndMoveSuccs.

A workaround could be to disable select->cmov generation in certain situations (EmitLoweredSelect?).

Andy

> -Hal
>
>>
>>
>> - Paweł
>>
>>
>>>
>>>
>>> On Thu, May 21, 2015 at 4:05 PM Paweł Bylica < [hidden email] >
>>> wrote:
>>>
>>>
>>>
>>> Hi,
>>>
>>>
>>> I'm trying to fix PR23405 - assert failure during instruction
>>> scheduling in llc. I have related but more generic questions.
>>>
>>>
>>> Is there any higher level description of the algorithm used for
>>> instruction scheduling in this case? It is new area for me and I
>>> would love to see bigger picture.
>>>
>>>
>>> My currently smallest test case contains 90 DAG nodes. I got it by
>>> manually reducing IR previously reduced by bugpoint. Is there a way
>>> to reduce it more, maybe on DAG level? Identifying the part of the
>>> DAG that causes the problem could be helpful.
>>>
>>>
>>>
>>> - Paweł
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> [hidden email] http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>
>> --
>> Hal Finkel
>> Assistant Computational Scientist
>> Leadership Computing Facility
>> Argonne National Laboratory
>>
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory


_______________________________________________
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: Problems with instruction scheduling

Paweł Bylica
On Fri, May 22, 2015 at 9:13 PM Andrew Trick <[hidden email]> wrote:

> On May 22, 2015, at 8:39 AM, Hal Finkel <[hidden email]> wrote:
>
> ----- Original Message -----
>> From: "Paweł Bylica" <[hidden email]>
>> To: "Hal Finkel" <[hidden email]>
>> Cc: "LLVMdev" <[hidden email]>, "Jonas Paulsson" <[hidden email]>
>> Sent: Friday, May 22, 2015 9:19:14 AM
>> Subject: Re: [LLVMdev] Problems with instruction scheduling
>>
>>
>>
>> On Fri, May 22, 2015 at 4:09 PM Hal Finkel < [hidden email] > wrote:
>>
>>
>> ----- Original Message -----
>>> From: "Paweł Bylica" < [hidden email] >
>>> To: "LLVMdev" < [hidden email] >
>>> Sent: Friday, May 22, 2015 8:45:11 AM
>>> Subject: Re: [LLVMdev] Problems with instruction scheduling
>>>
>>>
>>>
>>> Any comments?
>>
>> Not in particular, but I think we're pretty close to applying a
>> rewrite by Jonas Paulsson (cc'd). If you can't find the discussions
>> on the mailing list, please let us know.
>>
>> -Hal
>>
>>
>>
>> Thanks for the response.
>>
>>
>> Do you mean "ScheduleDAGInstrs::buildSchedGraph() rewritten"
>> http://reviews.llvm.org/D8705 ? If yes it is not the same fragment
>> of code.

It looks like I had a trivial request for code organization, otherwise that patch is probably fine. It’s unrelated to the thread though.

> Ah, I see. That bug deals with ScheduleDAGRRList.
>
> Andy, I thought that with the transition to source-order SDAG scheduling (and using MI scheduling instead), we were going to essentially get rid of that code. Is that right?


Right, Pawel’s bug is in SDAG scheduling. I would like this to go away, but the reality is that unless you use fast-isel, you still rely on this algorithm to serialize the DAG and resolve physical register interferences, usually when a flag-producing instruction like ADD or CMP feeds multiple uses, like ADC or CMOVE for example. There is some nasty backtracking happening to handle this full of rarely touched corner cases—it’s been problematic for a long time with larger-than-legal IR types.

I hoped most of these problems would go away with Pawel’s fix for PR22304. It looks like he’s hitting another one, and I haven’t had time to step through the scheduler trace. It’s just a matter of figuring out how that code gets stuck in a corner and can’t get out. I don’t have any special power for doing this, as I have to reparse the code each time I look at it. I will say that there should be a way for the code to get unstuck by spilling EFLAGS; see InsertCopiesAndMoveSuccs.

I identified the cause of the problem. LiveRegGen entry is replaced at some point during unscheduling. And later LiveRegGen does not clear out as it should. I just turned off this replacement.
 
A workaround could be to disable select->cmov generation in certain situations (EmitLoweredSelect?).

Andy

> -Hal
>
>>
>>
>> - Paweł
>>
>>
>>>
>>>
>>> On Thu, May 21, 2015 at 4:05 PM Paweł Bylica < [hidden email] >
>>> wrote:
>>>
>>>
>>>
>>> Hi,
>>>
>>>
>>> I'm trying to fix PR23405 - assert failure during instruction
>>> scheduling in llc. I have related but more generic questions.
>>>
>>>
>>> Is there any higher level description of the algorithm used for
>>> instruction scheduling in this case? It is new area for me and I
>>> would love to see bigger picture.
>>>
>>>
>>> My currently smallest test case contains 90 DAG nodes. I got it by
>>> manually reducing IR previously reduced by bugpoint. Is there a way
>>> to reduce it more, maybe on DAG level? Identifying the part of the
>>> DAG that causes the problem could be helpful.
>>>
>>>
>>>
>>> - Paweł
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> [hidden email] http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>
>> --
>> Hal Finkel
>> Assistant Computational Scientist
>> Leadership Computing Facility
>> Argonne National Laboratory
>>
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory


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