list-td scheduler asserts on targets with implicitly defined registers

Project Infrastructure LLVM Dev List Archives
1

Hi,

I just switched to the 2.5 release branch and noticed that llc runs into the following assert in ScheduleDAGList::ScheduleNodeTopDown() using our custom backend:

    assert(!I->isAssignedRegDep() &&
           "The list-td scheduler doesn't yet support physreg dependencies!");

It turns out that the register dependency concerns the condition code register which is modeled as an implicitly defined register in the backend (the same happens for e.g. for X86 when explicitly giving the -pre-RA-sched=list-td option to llc).

My assumption is that the assert should exclude non-allocatable, implicitly defined registers, which is checked in the attatched patch1.
This works fine for me, however on X86 the EFLAGS register is not marked non-allocatable (patch2).
Is this intentional? Our backend handles condition codes pretty much like X86 and I remember I didn't get it to work without defining the allocation_order_end() function in RegisterInfo.td
Anyway, I have no idea if this solution is ok for the general case, maybe the implicit defs information should rather be put into the SDeps when they are created?

Regards,
Christian

patch2_X86eflagsAllocatable.patch (649 Bytes)

patch1_physregAlloc.patch (1.6 KB)

2

The best fix is to teach this scheduler how to deal with these dependencies. :slight_smile:

If you just want a check, I think it's easier to just check register class's copy cost. -1 means it's extremely expensive to copy registers in the particular register class.

Evan

3

The best fix is to teach this scheduler how to deal with these
dependencies. :slight_smile:

If you just want a check, I think it's easier to just check register
class's copy cost. -1 means it's extremely expensive to copy registers
in the particular register class.

Evan,
I am not sure what you mean by "if you just want a check" - I was trying to point out that for example the following very simple testcase makes llc -march=x86 -pre-RA-sched=list-td crash :

define i32 @cctest(i32 %a, i32 %b) nounwind readnone {
entry:
        %not. = icmp sge i32 %a, %b ; <i1> [#uses=1]
        %.0 = zext i1 %not. to i32 ; <i32> [#uses=1]
        ret i32 %.0
}

The assert() which triggers has been introduced since llvm 2.4.
So I assume that (at least for the time being) the assert condition has to be made less restrictive. I also assume that this is ok because the dependency is rather a 'flag' dependency than one to be resolved by the scheduler.
So the question would be if these assumptions are correct and if it is safe to exclude implicitly defined physreg dependencies from the assert the way I proposed. Furthermore, I was thinking that the exception should not apply on allocatable registers, since the scheduler propably really cannot handle such. When I realized that X86 EFLAGS is actually allocatable, I was wondering why, but there is certainly a reason...

Best regards,
Christian

4

The best fix is to teach this scheduler how to deal with these
dependencies. :slight_smile:

If you just want a check, I think it's easier to just check register
class's copy cost. -1 means it's extremely expensive to copy registers
in the particular register class.

Evan,
I am not sure what you mean by "if you just want a check" - I was trying to point out that for example the following very simple testcase makes llc -march=x86 -pre-RA-sched=list-td crash :

define i32 @cctest(i32 %a, i32 %b) nounwind readnone {
entry:
       %not. = icmp sge i32 %a, %b ; <i1> [#uses=1]
       %.0 = zext i1 %not. to i32 ; <i32> [#uses=1]
       ret i32 %.0
}

The assert() which triggers has been introduced since llvm 2.4.
So I assume that (at least for the time being) the assert condition has to be made less restrictive. I also assume that this is ok because the dependency is rather a 'flag' dependency than one to be resolved by the scheduler.
So the question would be if these assumptions are correct and if it is safe to exclude implicitly defined physreg dependencies from the assert the way I proposed. Furthermore, I was thinking that the exception should not apply on allocatable registers, since the scheduler propably really cannot handle such. When I realized that X86 EFLAGS is actually allocatable, I was wondering why, but there is certainly a reason...

I was saying that instead of checking whether the physical register is allocatable, you might want to check the CopyCost of the register class (assuming it belongs to only one) is a negative value. That indicates it's extremely expensive to copy the physical register.

I think marking EFLAGS non-allocatable is fine. But I don't think it's the right fix. For example, ESP is not allocatable but you can insert a pair of copies (ESP to vreg and then vreg to ESP) to handle the dependency.

Evan

5

The best fix is to teach this scheduler how to deal with these
dependencies. :slight_smile:

If you just want a check, I think it's easier to just check register
class's copy cost. -1 means it's extremely expensive to copy registers
in the particular register class.

Evan,
I am not sure what you mean by "if you just want a check" - I was trying to point out that for example the following very simple testcase makes llc -march=x86 -pre-RA-sched=list-td crash :

define i32 @cctest(i32 %a, i32 %b) nounwind readnone {
entry:
       %not. = icmp sge i32 %a, %b ; <i1> [#uses=1]
       %.0 = zext i1 %not. to i32 ; <i32> [#uses=1]
       ret i32 %.0
}

The assert() which triggers has been introduced since llvm 2.4.
So I assume that (at least for the time being) the assert condition has to be made less restrictive.

The assertion changes potential miscompilations to compiler aborts. It
triggers more often than strictly necessary; the above testcase would not
have been miscompiled, but slightly more complicated ones would be.

I also assume that this is ok because the dependency is rather a 'flag' dependency than one to be resolved by the scheduler.
So the question would be if these assumptions are correct and if it is safe to exclude implicitly defined physreg dependencies from the assert the way I proposed. Furthermore, I was thinking that the exception should not apply on allocatable registers, since the scheduler propably really cannot handle such. When I realized that X86 EFLAGS is actually allocatable, I was wondering why, but there is certainly a reason...

The basic situation is A defines a value in register R that's read by B, and C
clobbers R. Here, C can be scheduled before A and B, or after A and B, but
not in between. This can happen with allocatable registers as well as
non-allocatable ones. It also can't easily be modeled in a simple
dependency graph.

CodeGen used to handle this by always using "Flag" dependencies, which
effectively require that nothing be scheduled between A and B. This is
simple, and it worked with all the schedulers, however, it's over-restrictive.

A while ago, the list-burr scheduler was enhanced to support physical
register dependencies, and some things were changed to make use of
this, instead of using the Flag mechanism. Eventually, more things will be
converted over.

Patches to add physical register dependency tracking to the other
schedulers would be welcome.

Dan