Problems with instruction scheduling

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ł

Any comments?

From: "Paweł Bylica" <chfast@gmail.com>
To: "LLVMdev" <llvmdev@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

From: “Paweł Bylica” <chfast@gmail.com>
To: “LLVMdev” <llvmdev@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.

  • Paweł

From: "Paweł Bylica" <chfast@gmail.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "LLVMdev" <llvmdev@cs.uiuc.edu>, "Jonas Paulsson" <jonas.paulsson@ericsson.com>
Sent: Friday, May 22, 2015 9:19:14 AM
Subject: Re: [LLVMdev] Problems with instruction scheduling

> From: "Paweł Bylica" < chfast@gmail.com >
> To: "LLVMdev" < llvmdev@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.

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

From: "Paweł Bylica" <chfast@gmail.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "LLVMdev" <llvmdev@cs.uiuc.edu>, "Jonas Paulsson" <jonas.paulsson@ericsson.com>
Sent: Friday, May 22, 2015 9:19:14 AM
Subject: Re: [LLVMdev] Problems with instruction scheduling

From: "Paweł Bylica" < chfast@gmail.com >
To: "LLVMdev" < llvmdev@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

From: “Paweł Bylica” <chfast@gmail.com>
To: “Hal Finkel” <hfinkel@anl.gov>
Cc: “LLVMdev” <llvmdev@cs.uiuc.edu>, “Jonas Paulsson” <jonas.paulsson@ericsson.com>
Sent: Friday, May 22, 2015 9:19:14 AM
Subject: Re: [LLVMdev] Problems with instruction scheduling

From: “Paweł Bylica” < chfast@gmail.com >
To: “LLVMdev” < llvmdev@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.

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.
http://reviews.llvm.org/D9993