[LLVMdev] Problems with instruction scheduling

[Andrew Trick]

> On May 22, 2015, at 8:39 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> ----- Original Message -----
>> From: "Paweł Bylica" <chfast at gmail.com>
>> To: "Hal Finkel" <hfinkel at anl.gov>
>> Cc: "LLVMdev" <llvmdev at cs.uiuc.edu>, "Jonas Paulsson" <jonas.paulsson at ericsson.com>
>> 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 < hfinkel at anl.gov > wrote:
>> 
>> 
>> ----- Original Message -----
>>> From: "Paweł Bylica" < chfast at gmail.com >
>>> To: "LLVMdev" < llvmdev at cs.uiuc.edu >
>>> 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 < chfast at gmail.com >
>>> 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
>>> LLVMdev at cs.uiuc.edu 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