Fix removal of dead elements from PressureDiff

[ygribov]

Summary

Fix removal of dead elements from PressureDiff. This fixes https://bugs.llvm.org/show_bug.cgi?id=37252

I'm nervous that this might introduce some scheduling churn which will cause unrelated fails on bots.

[MatzeB]

Good catch, the fix looks good to me. I assume you built llvm will all (non-experimental) targets and tested them?

Independently of this patch it is worrying that this requires test changes. That means X86 schedules produce intermediate pressure sets with MaxPSets/16 different pressure sets inside...

[ygribov]

Good catch, the fix looks good to me. I assume you built llvm will all (non-experimental) targets and tested them?

Yes, I ran cmake with default settings so all default cores were built. One caveat is that testing was done on Windows (~27K tests, done according to instructions in https://llvm.org/docs/GettingStartedVS.html).

Independently of this patch it is worrying that this requires test changes. That means X86 schedules produce intermediate pressure sets with MaxPSets/16 different pressure sets inside...

Yes, here's what I'm getting for e.g. divrem8_ext.ll:

-		PressureChanges	0x0000000002663400 {{PSetID=2 UnitInc=1 }, {PSetID=11 UnitInc=1 }, {PSetID=12 UnitInc=1 }, {PSetID=13 ...}, ...}	llvm::PressureChange[16]
+		[0]	{PSetID=2 UnitInc=1 }	llvm::PressureChange      GR8_ABCD_L
+		[1]	{PSetID=11 UnitInc=1 }	llvm::PressureChange      GR32_TC
+		[2]	{PSetID=12 UnitInc=1 }	llvm::PressureChange      LOW32_ADDR_ACCESS_with_sub_32bit+GR64_NOREX_and_GR64_TCW64
+		[3]	{PSetID=13 UnitInc=1 }	llvm::PressureChange      GR64_NOREX_and_GR64_TC
+		[4]	{PSetID=14 UnitInc=1 }	llvm::PressureChange      LOW32_ADDR_ACCESS_with_sub_32bit+GR64_NOREX_and_GR64_TC
+		[5]	{PSetID=18 UnitInc=1 }	llvm::PressureChange      GR64_NOREX
+		[6]	{PSetID=19 UnitInc=1 }	llvm::PressureChange      GR64_TCW64
+		[7]	{PSetID=20 UnitInc=1 }	llvm::PressureChange      LOW32_ADDR_ACCESS_with_sub_32bit+GR64_TCW64
+		[8]	{PSetID=21 UnitInc=1 }	llvm::PressureChange      GR64_TC
+		[9]	{PSetID=22 UnitInc=1 }	llvm::PressureChange      LOW32_ADDR_ACCESS_with_sub_32bit+GR64_TC
+		[10]	{PSetID=23 UnitInc=1 }	llvm::PressureChange      GR64_TC+GR64_TCW64
+		[11]	{PSetID=25 UnitInc=-1 }	llvm::PressureChange      GR8+GR64_NOREX
+		[12]	{PSetID=26 UnitInc=-1 }	llvm::PressureChange      GR8+GR64_TCW64
+		[13]	{PSetID=28 UnitInc=-1 }	llvm::PressureChange      GR8+GR64_TC
+		[14]	{PSetID=30 UnitInc=-1 }	llvm::PressureChange      GR16
+		[15]	{PSetID=30 UnitInc=-1 }	llvm::PressureChange      GR16

As a side note the current limit of 16 elements may be too strict for some targets (e.g. it caused a lot of noise on our non-orthogonal architecture until I increased it significantly) so it may make sense to switch to dynamic array.

[ygribov]

Reopening (commit caused lit regressions).

[ygribov]

Meanwhile few more tests required changes.

llvm/trunk/lib/CodeGen/RegisterPressure.cpp

for (; PSetI.isValid(); ++PSetI) {
     unsigned NewUnitInc = I->getUnitInc() + Weight;
     if (NewUnitInc != 0) {
       I->setUnitInc(NewUnitInc);
     } else {
       // Remove entry
       PressureDiff::iterator J;
       for (J = std::next(I); J != E && J->isValid(); ++J, ++I)
         *I = *J;
-      if (J != E)
-        *I = *J;
+      *I = PressureChange();
     }
   }
 }
 
 /// Force liveness of registers.
 void RegPressureTracker::addLiveRegs(ArrayRef<RegisterMaskPair> Regs) {
   for (const RegisterMaskPair &P : Regs) {
     LaneBitmask PrevMask = LiveRegs.insert(P);

llvm/trunk/test/CodeGen/X86/divrem.ll

; X64-NEXT:    retq
   store i64 %t, i64* %q
   ret void
 }
 
 define void @si32(i32 %x, i32 %y, i32* %p, i32* %q) nounwind {
 ; X32-LABEL: si32:
 ; X32:       # %bb.0:
 ; X32-NEXT:    pushl %esi
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    cltd
 ; X32-NEXT:    idivl {{[0-9]+}}(%esp)
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; X32-NEXT:    movl %eax, (%esi)
 ; X32-NEXT:    movl %edx, (%ecx)
 ; X32-NEXT:    popl %esi
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: si32:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movq %rdx, %r8
; X64-NEXT:    retq
   store i32 %t, i32* %q
   ret void
 }
 
 define void @si16(i16 %x, i16 %y, i16* %p, i16* %q) nounwind {
 ; X32-LABEL: si16:
 ; X32:       # %bb.0:
 ; X32-NEXT:    pushl %esi
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; X32-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    cwtd
 ; X32-NEXT:    idivw {{[0-9]+}}(%esp)
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; X32-NEXT:    movw %ax, (%esi)
 ; X32-NEXT:    movw %dx, (%ecx)
 ; X32-NEXT:    popl %esi
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: si16:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movq %rdx, %r8
; X64-NEXT:    retq
   store i16 %t, i16* %q
   ret void
 }
 
 define void @si8(i8 %x, i8 %y, i8* %p, i8* %q) nounwind {
 ; X32-LABEL: si8:
 ; X32:       # %bb.0:
 ; X32-NEXT:    pushl %ebx
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X32-NEXT:    movb {{[0-9]+}}(%esp), %al
 ; X32-NEXT:    cbtw
 ; X32-NEXT:    idivb {{[0-9]+}}(%esp)
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X32-NEXT:    movsbl %ah, %ebx
 ; X32-NEXT:    movb %al, (%edx)
 ; X32-NEXT:    movb %bl, (%ecx)
 ; X32-NEXT:    popl %ebx
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: si8:
 ; X64:       # %bb.0:
; X64-NEXT:    retq
   store i64 %t, i64* %q
   ret void
 }
 
 define void @ui32(i32 %x, i32 %y, i32* %p, i32* %q) nounwind {
 ; X32-LABEL: ui32:
 ; X32:       # %bb.0:
 ; X32-NEXT:    pushl %esi
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    xorl %edx, %edx
 ; X32-NEXT:    divl {{[0-9]+}}(%esp)
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; X32-NEXT:    movl %eax, (%esi)
 ; X32-NEXT:    movl %edx, (%ecx)
 ; X32-NEXT:    popl %esi
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: ui32:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movq %rdx, %r8
; X64-NEXT:    retq
   store i32 %t, i32* %q
   ret void
 }
 
 define void @ui16(i16 %x, i16 %y, i16* %p, i16* %q) nounwind {
 ; X32-LABEL: ui16:
 ; X32:       # %bb.0:
 ; X32-NEXT:    pushl %esi
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; X32-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    xorl %edx, %edx
 ; X32-NEXT:    divw {{[0-9]+}}(%esp)
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; X32-NEXT:    movw %ax, (%esi)
 ; X32-NEXT:    movw %dx, (%ecx)
 ; X32-NEXT:    popl %esi
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: ui16:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movq %rdx, %r8
; X64-NEXT:    retq
   store i16 %t, i16* %q
   ret void
 }
 
 define void @ui8(i8 %x, i8 %y, i8* %p, i8* %q) nounwind {
 ; X32-LABEL: ui8:
 ; X32:       # %bb.0:
 ; X32-NEXT:    pushl %ebx
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X32-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    # kill: def $eax killed $eax def $ax
 ; X32-NEXT:    divb {{[0-9]+}}(%esp)
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X32-NEXT:    movzbl %ah, %ebx
 ; X32-NEXT:    movb %al, (%edx)
 ; X32-NEXT:    movb %bl, (%ecx)
 ; X32-NEXT:    popl %ebx
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: ui8:
 ; X64:       # %bb.0:

llvm/trunk/test/CodeGen/X86/divrem8_ext.ll

; X64-NEXT:    retq
   %1 = srem i8 %x, %y
   ret i8 %1
 }
 
 define i8 @test_srem_noext_ah(i8 %x, i8 %y) {
 ; X32-LABEL: test_srem_noext_ah:
 ; X32:       # %bb.0:
 ; X32-NEXT:    movb {{[0-9]+}}(%esp), %al
-; X32-NEXT:    movb {{[0-9]+}}(%esp), %cl
 ; X32-NEXT:    cbtw
+; X32-NEXT:    movb {{[0-9]+}}(%esp), %cl
 ; X32-NEXT:    idivb %cl
 ; X32-NEXT:    movsbl %ah, %eax
 ; X32-NEXT:    addb %cl, %al
 ; X32-NEXT:    # kill: def $al killed $al killed $eax
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: test_srem_noext_ah:
 ; X64:       # %bb.0:

llvm/trunk/test/CodeGen/X86/musttail-varargs.ll

 ; LINUX-NEXT:    movaps %xmm0, {{[-0-9]+}}(%r{{[sb]}}p) # 16-byte Spill
 ; LINUX-NEXT:    callq get_f
 ; LINUX-NEXT:    movq %rax, %r11
 ; LINUX-NEXT:    movq %r14, %rdi
 ; LINUX-NEXT:    movq %rbx, %rsi
 ; LINUX-NEXT:    movq %rbp, %rdx
 ; LINUX-NEXT:    movq %r13, %rcx
 ; LINUX-NEXT:    movq %r12, %r8
+; LINUX-NEXT:    movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
 ; LINUX-NEXT:    movq %r15, %r9
 ; LINUX-NEXT:    movaps {{[-0-9]+}}(%r{{[sb]}}p), %xmm0 # 16-byte Reload
 ; LINUX-NEXT:    movaps {{[-0-9]+}}(%r{{[sb]}}p), %xmm1 # 16-byte Reload
 ; LINUX-NEXT:    movaps {{[-0-9]+}}(%r{{[sb]}}p), %xmm2 # 16-byte Reload
 ; LINUX-NEXT:    movaps {{[-0-9]+}}(%r{{[sb]}}p), %xmm3 # 16-byte Reload
 ; LINUX-NEXT:    movaps {{[-0-9]+}}(%r{{[sb]}}p), %xmm4 # 16-byte Reload
 ; LINUX-NEXT:    movaps {{[-0-9]+}}(%r{{[sb]}}p), %xmm5 # 16-byte Reload
 ; LINUX-NEXT:    movaps {{[-0-9]+}}(%r{{[sb]}}p), %xmm6 # 16-byte Reload
 ; LINUX-NEXT:    movaps {{[-0-9]+}}(%r{{[sb]}}p), %xmm7 # 16-byte Reload
-; LINUX-NEXT:    movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
 ; LINUX-NEXT:    addq $360, %rsp # imm = 0x168
 ; LINUX-NEXT:    .cfi_def_cfa_offset 56
 ; LINUX-NEXT:    popq %rbx
 ; LINUX-NEXT:    .cfi_def_cfa_offset 48
 ; LINUX-NEXT:    popq %r12
 ; LINUX-NEXT:    .cfi_def_cfa_offset 40
 ; LINUX-NEXT:    popq %r13
 ; LINUX-NEXT:    .cfi_def_cfa_offset 32

 ; LINUX-X32-NEXT:    movaps %xmm0, {{[-0-9]+}}(%e{{[sb]}}p) # 16-byte Spill
 ; LINUX-X32-NEXT:    callq get_f
 ; LINUX-X32-NEXT:    movl %eax, %r11d
 ; LINUX-X32-NEXT:    movl %r14d, %edi
 ; LINUX-X32-NEXT:    movq %rbx, %rsi
 ; LINUX-X32-NEXT:    movq %rbp, %rdx
 ; LINUX-X32-NEXT:    movq %r13, %rcx
 ; LINUX-X32-NEXT:    movq %r12, %r8
+; LINUX-X32-NEXT:    movb {{[-0-9]+}}(%e{{[sb]}}p), %al # 1-byte Reload
 ; LINUX-X32-NEXT:    movq %r15, %r9
 ; LINUX-X32-NEXT:    movaps {{[-0-9]+}}(%e{{[sb]}}p), %xmm0 # 16-byte Reload
 ; LINUX-X32-NEXT:    movaps {{[-0-9]+}}(%e{{[sb]}}p), %xmm1 # 16-byte Reload
 ; LINUX-X32-NEXT:    movaps {{[-0-9]+}}(%e{{[sb]}}p), %xmm2 # 16-byte Reload
 ; LINUX-X32-NEXT:    movaps {{[-0-9]+}}(%e{{[sb]}}p), %xmm3 # 16-byte Reload
 ; LINUX-X32-NEXT:    movaps {{[-0-9]+}}(%e{{[sb]}}p), %xmm4 # 16-byte Reload
 ; LINUX-X32-NEXT:    movaps {{[-0-9]+}}(%e{{[sb]}}p), %xmm5 # 16-byte Reload
 ; LINUX-X32-NEXT:    movaps {{[-0-9]+}}(%e{{[sb]}}p), %xmm6 # 16-byte Reload
 ; LINUX-X32-NEXT:    movaps {{[-0-9]+}}(%e{{[sb]}}p), %xmm7 # 16-byte Reload
-; LINUX-X32-NEXT:    movb {{[-0-9]+}}(%e{{[sb]}}p), %al # 1-byte Reload
 ; LINUX-X32-NEXT:    addl $344, %esp # imm = 0x158
 ; LINUX-X32-NEXT:    .cfi_def_cfa_offset 56
 ; LINUX-X32-NEXT:    popq %rbx
 ; LINUX-X32-NEXT:    .cfi_def_cfa_offset 48
 ; LINUX-X32-NEXT:    popq %r12
 ; LINUX-X32-NEXT:    .cfi_def_cfa_offset 40
 ; LINUX-X32-NEXT:    popq %r13
 ; LINUX-X32-NEXT:    .cfi_def_cfa_offset 32

llvm/trunk/test/CodeGen/X86/pr38539.ll

 ; X64-NEXT:    pushq %rbx
 ; X64-NEXT:    .cfi_def_cfa_offset 32
 ; X64-NEXT:    subq $16, %rsp
 ; X64-NEXT:    .cfi_def_cfa_offset 48
 ; X64-NEXT:    .cfi_offset %rbx, -32
 ; X64-NEXT:    .cfi_offset %r14, -24
 ; X64-NEXT:    .cfi_offset %rbp, -16
 ; X64-NEXT:    movzbl {{[0-9]+}}(%rsp), %ebp
-; X64-NEXT:    movq %rbp, %rcx
-; X64-NEXT:    shlq $62, %rcx
-; X64-NEXT:    sarq $62, %rcx
 ; X64-NEXT:    movq (%rsp), %rbx
 ; X64-NEXT:    movb (%rax), %al
 ; X64-NEXT:    movzbl %al, %eax
 ; X64-NEXT:    # kill: def $eax killed $eax def $ax
 ; X64-NEXT:    divb (%rax)
 ; X64-NEXT:    movl %eax, %r14d
+; X64-NEXT:    movq %rbp, %rcx
+; X64-NEXT:    shlq $62, %rcx
+; X64-NEXT:    sarq $62, %rcx
 ; X64-NEXT:    xorl %edi, %edi
 ; X64-NEXT:    xorl %esi, %esi
 ; X64-NEXT:    movq %rbx, %rdx
 ; X64-NEXT:    callq __modti3
 ; X64-NEXT:    andl $3, %edx
 ; X64-NEXT:    testb %al, %al
 ; X64-NEXT:    setne (%rax)
 ; X64-NEXT:    cmpq %rax, %rbx

 ; X86-NEXT:    pushl %edi
 ; X86-NEXT:    pushl %esi
 ; X86-NEXT:    andl $-8, %esp
 ; X86-NEXT:    subl $48, %esp
 ; X86-NEXT:    .cfi_offset %esi, -20
 ; X86-NEXT:    .cfi_offset %edi, -16
 ; X86-NEXT:    .cfi_offset %ebx, -12
 ; X86-NEXT:    movzbl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    movl %esi, %ecx
-; X86-NEXT:    shll $30, %ecx
-; X86-NEXT:    movl %ecx, %edx
-; X86-NEXT:    sarl $30, %edx
-; X86-NEXT:    sarl $31, %ecx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ebx
 ; X86-NEXT:    movb (%eax), %al
 ; X86-NEXT:    movzbl %al, %eax
 ; X86-NEXT:    # kill: def $eax killed $eax def $ax
 ; X86-NEXT:    divb (%eax)
 ; X86-NEXT:    movb %al, {{[-0-9]+}}(%e{{[sb]}}p) # 1-byte Spill
-; X86-NEXT:    leal {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl %esi, %eax
+; X86-NEXT:    shll $30, %eax
+; X86-NEXT:    movl %eax, %ecx
+; X86-NEXT:    sarl $30, %ecx
+; X86-NEXT:    sarl $31, %eax
+; X86-NEXT:    leal {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    pushl %eax
 ; X86-NEXT:    pushl %ecx
-; X86-NEXT:    pushl %edx
 ; X86-NEXT:    pushl %ebx
 ; X86-NEXT:    pushl %edi
 ; X86-NEXT:    pushl $0
 ; X86-NEXT:    pushl $0
 ; X86-NEXT:    pushl $0
 ; X86-NEXT:    pushl $0
-; X86-NEXT:    pushl %eax
+; X86-NEXT:    pushl %edx
 ; X86-NEXT:    calll __modti3
 ; X86-NEXT:    addl $32, %esp
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    andl $3, %eax
 ; X86-NEXT:    xorl %ecx, %ecx
 ; X86-NEXT:    cmpl {{[0-9]+}}(%esp), %edi
 ; X86-NEXT:    sbbl {{[0-9]+}}(%esp), %ebx
 ; X86-NEXT:    sbbl %eax, %esi

 ; X86-NEXT:    pushl %edi
 ; X86-NEXT:    pushl %esi
 ; X86-NEXT:    andl $-8, %esp
 ; X86-NEXT:    subl $16, %esp
 ; X86-NEXT:    .cfi_offset %esi, -20
 ; X86-NEXT:    .cfi_offset %edi, -16
 ; X86-NEXT:    .cfi_offset %ebx, -12
 ; X86-NEXT:    movzbl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    movl %esi, %ecx
-; X86-NEXT:    shll $30, %ecx
-; X86-NEXT:    sarl $30, %ecx
 ; X86-NEXT:    movl (%esp), %edi
 ; X86-NEXT:    movb (%eax), %al
 ; X86-NEXT:    movzbl %al, %eax
 ; X86-NEXT:    # kill: def $eax killed $eax def $ax
 ; X86-NEXT:    divb (%eax)
 ; X86-NEXT:    movl %eax, %ebx
-; X86-NEXT:    pushl %ecx
+; X86-NEXT:    movl %esi, %eax
+; X86-NEXT:    shll $30, %eax
+; X86-NEXT:    sarl $30, %eax
+; X86-NEXT:    pushl %eax
 ; X86-NEXT:    pushl %edi
 ; X86-NEXT:    pushl $0
 ; X86-NEXT:    pushl $0
 ; X86-NEXT:    calll __moddi3
 ; X86-NEXT:    addl $16, %esp
 ; X86-NEXT:    andl $3, %edx
 ; X86-NEXT:    testb %al, %al
 ; X86-NEXT:    setne (%eax)