RegisterClassInfo: Fix CSR cache invalidation

[MatzeB]

Summary

RegisterClassInfo caches information like allocation orders and reuses it for multiple machine functions where possible. However the MCPhysReg *CalleeSavedRegs field used to test whether the set of callee saved registers changed did not work: After D28566 MachineRegisterInfo::getCalleeSavedRegs() can return dynamically computed CSR sets that are only valid while the MachineRegisterInfo object of the current function exists.

This changes the code to make a copy of the CSR list instead of keeping a possibly invalid pointer around.

[MatzeB]

Adding PowerPC and XCore test authors. I update the tests to match the new output, I'm not sure if they still test what they are intended to test. I would recommend rewriting the tests into .mir tests that run a single pass and do not depend on a particular register allocation if necessary!

[MatzeB]

For context: I found this while tweaking regalloc heuristics. Surprisingly this bug seems to have nearly no effect on most targets in practice. I suspect this is because calling conventions and CSR lists don't typically change for most targets and even if they did this only affected the allocation orders and things like eviction could restore the desired CSR usage.

[mtrofin]

llvm/lib/CodeGen/RegisterClassInfo.cpp

58

how about:

bool CSRChanged = true;

if (!Update) {
  CSRChanged = false;
  ...
}

[nigelp-xmos]

Thanks for the pointer to the XCore test. There are a couple of issues:

(1) An extra stack slot is being allocated, leaving a slot unused. A register is being saved in high memory (bottom of stack) instead of near SP, even though XCore useFPForScavengingIndex() returns false, to save near SP. A extra constant appears in the constant pool, holding this large offset.

(2) When I delete the first function (f), the second function (ScavengeSlots) generates the same code as before this patch. So there seems to be some kind of new dependency on previous state, previous functions.

So I will look into this a bit more. Do you know where state might be affecting code generation?

[MatzeB]

Do you know where state might be affecting code generation?

I fix one instance of this with this very diff! RegisterClassInfo::CalleeSavedRegs is maintained between functions and before this diff the code sometimes incorrectly decided to keep the RegisterClassInfo data around where it should have been invalidated and recomputed.

[nigelp-xmos]

A problem was revealed on XCore because in scavenging.ll CSR is different in the second function than the first: a different hard-coded list of registers, with the different register being the last entry. In the loop comparing CSR with LastCSR, the condition “CSR[I] == 0 || I >= LastSize” combines two cases. In the first case, you do indeed want to set change = (I != LastSize). But in the second case, the lists have different length, and the change flag should be true, even if I == LastSize. I guess I can't add a code comment because this is committed but my fix is:

if (CSR[I] == 0) {
  CSRChanged = I != LastSize;
  break;
}
if (I >= LastSize) {
  CSRChanged = true;
  break;
}

The XCore test now generates the same code it did before. I've done no other testing.

[nigelp-xmos]

@MatzeB Do you agree with the problem in the logic of this diff, that I reported above? The code:

if (CSR[I] == 0 || I >= LastSize) {
    CSRChanged = I != LastSize;
    break;
  }

is wrong in the case CSR[I] != 0 && I == LastSize, i.e. when an entry in the new list is beyond the length of the old list (all previous entries having matched). In that case, the lists are different, and code should set CSRChanged = true. But the committed code sets CSRChanged false.

This means that incorrect expected test results have now been committed in scavenging.ll.

[MatzeB]

@nigelp-xmos indeed I got that wrong here, sorry. Thanks for checking, putting up a fix now.

[MatzeB]

Fix is in D132606.

llvm/include/llvm/CodeGen/RegisterClassInfo.h

class RegisterClassInfo {
 
   // Tag changes whenever cached information needs to be recomputed. An RCInfo
   // entry is valid when its tag matches.
   unsigned Tag = 0;
 
   const MachineFunction *MF = nullptr;
   const TargetRegisterInfo *TRI = nullptr;
 
-  // Callee saved registers of last MF. Assumed to be valid until the next
-  // runOnFunction() call.
-  // Used only to determine if an update was made to CalleeSavedAliases.
-  const MCPhysReg *CalleeSavedRegs = nullptr;
+  // Callee saved registers of last MF.
+  // Used only to determine if an update for CalleeSavedAliases is necessary.
+  SmallVector<MCPhysReg, 16> LastCalleeSavedRegs;
 
   // Map register alias to the callee saved Register.
   SmallVector<MCPhysReg, 4> CalleeSavedAliases;
 
   // Indicate if a specified callee saved register be in the allocation order
   // exactly as written in the tablegen descriptions or listed later.
   BitVector IgnoreCSRForAllocOrder;
 

llvm/lib/CodeGen/RegisterClassInfo.cpp

void RegisterClassInfo::runOnMachineFunction(const MachineFunction &mf) {
 
   // Allocate new array the first time we see a new target.
   if (STI.getRegisterInfo() != TRI) {
     TRI = STI.getRegisterInfo();
     RegClass.reset(new RCInfo[TRI->getNumRegClasses()]);
     Update = true;
   }
 
-  // Does this MF have different CSRs?
-  assert(TRI && "no register info set");
+  // Test if CSRs have changed from the previous function.
+  const MachineRegisterInfo &MRI = MF->getRegInfo();
+  const MCPhysReg *CSR = MRI.getCalleeSavedRegs();
+  bool CSRChanged = true;
+  if (!Update) {
+    CSRChanged = false;
+    size_t LastSize = LastCalleeSavedRegs.size();
+    for (unsigned I = 0;; ++I) {
+      if (CSR[I] == 0 || I >= LastSize) {
+        CSRChanged = I != LastSize;
+        break;
+      }
+      if (CSR[I] != LastCalleeSavedRegs[I]) {
+        CSRChanged = true;
+        break;
+      }
+    }
+  }
 
   // Get the callee saved registers.
-  const MCPhysReg *CSR = MF->getRegInfo().getCalleeSavedRegs();
-  if (Update || CSR != CalleeSavedRegs) {
+  if (CSRChanged) {
+    LastCalleeSavedRegs.clear();
     // Build a CSRAlias map. Every CSR alias saves the last
     // overlapping CSR.
     CalleeSavedAliases.assign(TRI->getNumRegs(), 0);
-    for (const MCPhysReg *I = CSR; *I; ++I)
+    for (const MCPhysReg *I = CSR; *I; ++I) {
       for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI)
         CalleeSavedAliases[*AI] = *I;
+      LastCalleeSavedRegs.push_back(*I);
+    }
 
     Update = true;
   }
-  CalleeSavedRegs = CSR;
 
   // Even if CSR list is same, we could have had a different allocation order
   // if ignoreCSRForAllocationOrder is evaluated differently.
   BitVector CSRHintsForAllocOrder(TRI->getNumRegs());
   for (const MCPhysReg *I = CSR; *I; ++I)
     for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI)
       CSRHintsForAllocOrder[*AI] = STI.ignoreCSRForAllocationOrder(mf, *AI);
   if (IgnoreCSRForAllocOrder.size() != CSRHintsForAllocOrder.size() ||

llvm/test/CodeGen/PowerPC/pcrel-call-linkage-leaf.ll

entry:
   ret i32 %add
 }
 
 ; Increase register pressure enough to force the register allocator to
 ; make use of R2.
 define dso_local signext i32 @X2IsCallerSaved(i32 signext %a, i32 signext %b, i32 signext %c, i32 signext %d, i32 signext %e, i32 signext %f, i32 signext %g, i32 signext %h) local_unnamed_addr {
 ; CHECK-ALL-LABEL: X2IsCallerSaved:
 ; CHECK-S:         .localentry X2IsCallerSaved, 1
-; CHECK-P9-NOT:    .localentry
 ; CHECK-ALL:       # %bb.0: # %entry
 ; CHECK-S-NEXT:    std r29, -24(r1) # 8-byte Folded Spill
 ; CHECK-S-NEXT:    std r30, -16(r1) # 8-byte Folded Spill
 ; CHECK-S-NEXT:    add r11, r4, r3
 ; CHECK-S-NEXT:    sub r29, r8, r9
 ; CHECK-S-NEXT:    add r9, r10, r9
 ; CHECK-S-NEXT:    sub r10, r10, r3
 ; CHECK-S-NEXT:    mullw r3, r4, r3

llvm/test/CodeGen/XCore/scavenging.ll

entry:
   ret void
 }
 declare void @g(i32*, i32*)
 
 
 ; CHECK: .section .cp.rodata.cst4,"aMc",@progbits,4
 ; CHECK: .p2align  2
 ; CHECK: [[ARG5:.LCPI[0-9_]+]]:
-; CHECK: .long   100003
+; CHECK: .long   100002
 ; CHECK: [[INDEX0:.LCPI[0-9_]+]]:
-; CHECK: .long   80002
+; CHECK: .long   100004
 ; CHECK: [[INDEX1:.LCPI[0-9_]+]]:
-; CHECK: .long   81002
+; CHECK: .long   80002
 ; CHECK: [[INDEX2:.LCPI[0-9_]+]]:
-; CHECK: .long   82002
+; CHECK: .long   81002
 ; CHECK: [[INDEX3:.LCPI[0-9_]+]]:
-; CHECK: .long   83002
+; CHECK: .long   82002
 ; CHECK: [[INDEX4:.LCPI[0-9_]+]]:
+; CHECK: .long   83002
+; CHECK: [[INDEX5:.LCPI[0-9_]+]]:
 ; CHECK: .long   84002
 ; CHECK: .text
 ; !FP + large frame: spill SR+SR = entsp 2 + 100000
 ; CHECK-LABEL: ScavengeSlots:
 ; CHECK: entsp 65535
-; CHECK: extsp 34467
+; CHECK: extsp 34468
 ; scavenge r11
 ; CHECK: ldaw r11, sp[0]
 ; scavenge r4 using SR spill slot
 ; CHECK: stw r4, sp[1]
 ; CHECK: ldw r4, cp[[[ARG5]]]
 ; r11 used to load 5th argument
-; CHECK: ldw r11, r11[r4]
-; CHECK: ldaw r4, sp[0]
-; scavenge r5 using SR spill slot
-; CHECK: stw r5, sp[0]
-; CHECK: ldw r5, cp[[[INDEX0]]]
-; r4 & r5 used by InsertSPConstInst() to emit STW_l3r instruction.
-; CHECK: stw r0, r4[r5]
-; CHECK: ldaw r0, sp[0]
-; CHECK: ldw r5, cp[[[INDEX1]]]
-; CHECK: stw r1, r0[r5]
+; CHECK: stw r10, r11[r4]
+; CHECK: ldaw r10, sp[0]
+; CHECK: ldw r11, cp[[[INDEX0]]]
+; CHECK: ldw r10, r10[r11]
+; CHECK: ldaw r11, sp[0]
+; CHECK: ldw r4, cp[[[INDEX1]]]
+; CHECK: stw r0, r11[r4]
 ; CHECK: ldaw r0, sp[0]
-; CHECK: ldw r1, cp[[[INDEX2]]]
-; CHECK: stw r2, r0[r1]
+; CHECK: ldw r11, cp[[[INDEX2]]]
+; CHECK: stw r1, r0[r11]
 ; CHECK: ldaw r0, sp[0]
 ; CHECK: ldw r1, cp[[[INDEX3]]]
 ; CHECK: stw r3, r0[r1]
 ; CHECK: ldaw r0, sp[0]
-; CHECK: ldw r1, cp[[[INDEX4]]]
-; CHECK: stw r11, r0[r1]
+; CHECK: ldw r1, cp[[[INDEX5]]]
+; CHECK: stw r10, r0[r1]
+; CHECK: ldaw r10, sp[0]
+; CHECK: ldw r0, cp[[[ARG5]]]
+; CHECK: ldw r10, r10[r0]
 ; CHECK: ldaw sp, sp[65535]
 ; CHECK: ldw r4, sp[1]
-; CHECK: ldw r5, sp[0]
-; CHECK: retsp 34467
+; CHECK: retsp 34468
 define void @ScavengeSlots(i32 %r0, i32 %r1, i32 %r2, i32 %r3, i32 %r4) nounwind {
 entry:
   %Data = alloca [100000 x i32]
   %i0 = getelementptr inbounds [100000 x i32], [100000 x i32]* %Data, i32 0, i32 80000
   store volatile i32 %r0, i32* %i0
   %i1 = getelementptr inbounds [100000 x i32], [100000 x i32]* %Data, i32 0, i32 81000
   store volatile i32 %r1, i32* %i1
   %i2 = getelementptr inbounds [100000 x i32], [100000 x i32]* %Data, i32 0, i32 82000
   store volatile i32 %r2, i32* %i2
   %i3 = getelementptr inbounds [100000 x i32], [100000 x i32]* %Data, i32 0, i32 83000
   store volatile i32 %r3, i32* %i3
   %i4 = getelementptr inbounds [100000 x i32], [100000 x i32]* %Data, i32 0, i32 84000
   store volatile i32 %r4, i32* %i4
   ret void
 }