When looking for a spill slot in reg scavenger, find one that matches RC

[kparzysz]

Summary

When looking for an available spill slot, the register scavenger would stop after finding the first one with no register assigned to it. That slot may have size and alignment that do not meet the requirements of the register that is to be spilled. Instead, find an available slot that is the closest in size and alignment to one that is needed to spill a register from RC.

[qcolombet]

lib/CodeGen/RegisterScavenging.cpp

414

Did you actually see cases where we should care?

I would rather return the first matching one and be done with the loop.

439

Given that we saw it can happen, I would go with a report_fatal_error.

test/CodeGen/Hexagon/reg-scavenger-valid-slot.ll

3

• Run opt instnamer on the input.
• Add check lines.
• Add a comment on what this test is exercising.

106

Could you make the test smaller, e.g., via using inline asm to clobber registers?
(You could also use mir input.)

[kparzysz]

lib/CodeGen/RegisterScavenging.cpp

414

On Hexagon we can reserve spill slots for vectors (64-byte size/alignment) and integer registers (4/8-byte size/alignment). I'm concerned that depending on the order of reservation we can end up using a vector slot for an integer register.

439

Will do.

test/CodeGen/Hexagon/reg-scavenger-valid-slot.ll

106

Let me see what I can do with inline asm. I haven't tried MIR with our backend so I'm not sure how much work it will be to get it to work.

[kparzysz]

test/CodeGen/Hexagon/reg-scavenger-valid-slot.ll

106

I need to keep enough registers live in a certain range. Turns out that vector register inputs and outputs are not yet implemented for inline-asm. I'll keep the code as is for now.

[kparzysz]

test/CodeGen/Hexagon/reg-scavenger-valid-slot.ll

106

What I mean is that our backend crashes in isel-lowering on inline-asm with vector inputs/outputs.

[kparzysz]

Added a comment in RegisterScavenging.cpp explaining the motivation for the search loop modification.
Replaced the llvm_unreachable with a report_fatal_error. The message includes register name and register class name.
Applied instnamer to the test, added check lines, and a comment explaining what is being tested.

[kparzysz]

Created a shorter testcase.

test/CodeGen/Hexagon/reg-scavenger-valid-slot.ll

101

I have fixed the inline-asm problem.

[kparzysz]

lib/CodeGen/RegisterScavenging.cpp

439–441

At the second thought---wouldn't it be better to keep the "unreachable"? report_fatal_error does not print the call stack.

[qcolombet]

lib/CodeGen/RegisterScavenging.cpp

414

What worries me is that we have a quadratic complexity here (#scavengedRegister x Scavenged.size()).
That being said, I guess it is pretty small in practice. Therefore, let us move on and we will adapt if it turns out to be a problem.

439–441

We could do both maybe.
The problem is that llvm_unreachable expands to nothing in release mode. Thus we may silently generate broken code or a crash somewhere else in the compiler.

[kparzysz]

llvm/trunk/lib/CodeGen/RegisterScavenging.cpp

445 ↗

(On Diff #57653)

I kept both.

[MatzeB]

llvm/trunk/lib/CodeGen/RegisterScavenging.cpp

445 ↗

(On Diff #57653)

This makes no sense. llvm_unreachable() is an indication that this case cannot happen and the compiler will actually optimize for this. There is a high chance it remove the report_fatal_error() in this case.
If you have an error that could actually be provoked by a user of the compiler (through inline assembly or similar) then report_fatal_error() is apropriate. If the problem can only be caused by a bug in llvm then llvm_unreachable() should be used.

[kparzysz]

llvm/trunk/lib/CodeGen/RegisterScavenging.cpp

445 ↗

(On Diff #57653)

With assertions enabled, llvm_unreachable is the more interesting way to terminate the program, since it will print the call stack. The report_fatal_error will never execute, which is fine. In the release mode, llvm_unreachable will expand to nothing (as per Quentin's earlier remark), but we still want the program to terminate with a meaningful message. It looks strange, but it was intentional.

lib/CodeGen/RegisterScavenging.cpp

unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
   unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
 
   // If we found an unused register there is no reason to spill it.
   if (!isRegUsed(SReg)) {
     DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
     return SReg;
   }
 
-  // Find an available scavenging slot.
-  unsigned SI;
-  for (SI = 0; SI < Scavenged.size(); ++SI)
-    if (Scavenged[SI].Reg == 0)
-      break;
+  // Find an available scavenging slot with size and alignment matching
+  // the requirements of the class RC.
+  MachineFunction &MF = *I->getParent()->getParent();
+  MachineFrameInfo &MFI = *MF.getFrameInfo();
+  unsigned NeedSize = RC->getSize();
+  unsigned NeedAlign = RC->getAlignment();
+
+  unsigned SI = Scavenged.size(), Diff = UINT_MAX;
+  for (unsigned I = 0; I < Scavenged.size(); ++I) {
+    if (Scavenged[I].Reg != 0)
+      continue;
+    // Verify that this slot is valid for this register.
+    int FI = Scavenged[I].FrameIndex;
+    unsigned S = MFI.getObjectSize(FI);
+    unsigned A = MFI.getObjectAlignment(FI);
+    if (NeedSize > S || NeedAlign > A)
+      continue;
+    // Avoid wasting slots with large size and/or large alignment. Pick one
+    // that is the best fit for this register class (in street metric).
+    unsigned D = (S-NeedSize) + (A-NeedAlign);
+    if (D < Diff) {
+      SI = I;
+      Diff = D;
+    }
+  }
 
   if (SI == Scavenged.size()) {
     // We need to scavenge a register but have no spill slot, the target
     // must know how to do it (if not, we'll assert below).
     Scavenged.push_back(ScavengedInfo());
   }
 
   // Avoid infinite regress
   Scavenged[SI].Reg = SReg;
 
   // If the target knows how to save/restore the register, let it do so;
   // otherwise, use the emergency stack spill slot.
   if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
     // Spill the scavenged register before I.
-    assert(Scavenged[SI].FrameIndex >= 0 &&
+    if (Scavenged[SI].FrameIndex < 0) {
+#ifndef NDEBUG
+      dbgs() << "Trying to spill " << PrintReg(SReg, TRI) << "\n";
+#endif
+      llvm_unreachable(
            "Cannot scavenge register without an emergency spill slot!");
+    }
     TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex,
                              RC, TRI);
     MachineBasicBlock::iterator II = std::prev(I);
 
     unsigned FIOperandNum = getFrameIndexOperandNum(II);
     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 
     // Restore the scavenged register before its use (or first terminator).
     TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex,

test/CodeGen/Hexagon/reg-scavenger-valid-slot.ll

+; RUN: llc -march=hexagon < %s
+; REQUIRES: asserts
+
+target triple = "hexagon"
+
+define i32 @foo(i32 %n, i32* readonly %pi, i32* nocapture %po, <16 x i32>* readonly %vi, <16 x i32>* nocapture %vo) #0 {
+entry:
+  br i1 undef, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  %incdec.ptr63 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi, i32 32
+  %incdec.ptr61 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi, i32 30
+  %incdec.ptr60 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi, i32 29
+  %0 = load <16 x i32>, <16 x i32>* %incdec.ptr60, align 64
+  %incdec.ptr59 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi, i32 28
+  %1 = load <16 x i32>, <16 x i32>* %incdec.ptr59, align 64
+  %incdec.ptr58 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi, i32 27
+  %2 = load <16 x i32>, <16 x i32>* %incdec.ptr58, align 64
+  %incdec.ptr57 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi, i32 26
+  %3 = load <16 x i32>, <16 x i32>* %incdec.ptr57, align 64
+  %incdec.ptr56 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi, i32 25
+  %4 = load <16 x i32>, <16 x i32>* %incdec.ptr56, align 64
+  %5 = load <16 x i32>, <16 x i32>* undef, align 64
+  %incdec.ptr40 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi, i32 9
+  %6 = load <16 x i32>, <16 x i32>* %incdec.ptr40, align 64
+  br i1 undef, label %for.end.loopexit.unr-lcssa, label %for.body.preheader.new
+
+for.body.preheader.new:                           ; preds = %for.body.preheader
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %for.body.preheader.new
+  %po.addr.0289 = phi i32* [ %po, %for.body.preheader.new ], [ %incdec.ptr64.7, %for.body ]
+  %vi.addr.0288 = phi <16 x i32>* [ %incdec.ptr63, %for.body.preheader.new ], [ %incdec.ptr67.7, %for.body ]
+  %vo.addr.0287 = phi <16 x i32>* [ %vo, %for.body.preheader.new ], [ %incdec.ptr66.7, %for.body ]
+  %v31.0.in286 = phi <16 x i32>* [ undef, %for.body.preheader.new ], [ %incdec.ptr67.6, %for.body ]
+  %v30.0285 = phi <16 x i32> [ zeroinitializer, %for.body.preheader.new ], [ %v31.0.7, %for.body ]
+  %v29.0284 = phi <16 x i32> [ %0, %for.body.preheader.new ], [ %v31.0.6, %for.body ]
+  %v28.0283 = phi <16 x i32> [ %1, %for.body.preheader.new ], [ undef, %for.body ]
+  %v27.0282 = phi <16 x i32> [ %2, %for.body.preheader.new ], [ %v31.0.4, %for.body ]
+  %v26.0281 = phi <16 x i32> [ %3, %for.body.preheader.new ], [ %v31.0.3, %for.body ]
+  %v25.0280 = phi <16 x i32> [ %4, %for.body.preheader.new ], [ undef, %for.body ]
+  %v23.0278 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v31.0, %for.body ]
+  %v22.0277 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v30.0285, %for.body ]
+  %v21.0276 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v29.0284, %for.body ]
+  %v20.0275 = phi <16 x i32> [ %5, %for.body.preheader.new ], [ %v28.0283, %for.body ]
+  %v19.0274 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v27.0282, %for.body ]
+  %v18.0273 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v26.0281, %for.body ]
+  %v17.0272 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v25.0280, %for.body ]
+  %v15.0270 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v23.0278, %for.body ]
+  %v14.0269 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v22.0277, %for.body ]
+  %v13.0268 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v21.0276, %for.body ]
+  %v12.0267 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v20.0275, %for.body ]
+  %v11.0266 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v19.0274, %for.body ]
+  %v10.0265 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v18.0273, %for.body ]
+  %v9.0264 = phi <16 x i32> [ %6, %for.body.preheader.new ], [ %v17.0272, %for.body ]
+  %v7.0262 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v15.0270, %for.body ]
+  %v6.0261 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v14.0269, %for.body ]
+  %v5.0260 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v13.0268, %for.body ]
+  %v4.0259 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v12.0267, %for.body ]
+  %v3.0258 = phi <16 x i32> [ undef, %for.body.preheader.new ], [ %v11.0266, %for.body ]
+  %niter = phi i32 [ undef, %for.body.preheader.new ], [ %niter.nsub.7, %for.body ]
+  %v31.0 = load <16 x i32>, <16 x i32>* %v31.0.in286, align 64
+  %incdec.ptr66.1 = getelementptr inbounds <16 x i32>, <16 x i32>* %vo.addr.0287, i32 2
+  store <16 x i32> undef, <16 x i32>* %incdec.ptr66.1, align 64
+  %incdec.ptr67.2 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi.addr.0288, i32 3
+  %v31.0.3 = load <16 x i32>, <16 x i32>* undef, align 64
+  %incdec.ptr64.3 = getelementptr inbounds i32, i32* %po.addr.0289, i32 4
+  %7 = tail call <512 x i1> @llvm.hexagon.V6.vgtw(<16 x i32> undef, <16 x i32> %v31.0)
+  %8 = tail call <512 x i1> @llvm.hexagon.V6.vgtw.xor(<512 x i1> %7, <16 x i32> %v15.0270, <16 x i32> %v31.0)
+  %9 = tail call <512 x i1> @llvm.hexagon.V6.vgtw.xor(<512 x i1> %8, <16 x i32> %v23.0278, <16 x i32> undef)
+  %10 = tail call <512 x i1> @llvm.hexagon.V6.vgtw.xor(<512 x i1> %9, <16 x i32> %v4.0259, <16 x i32> %v3.0258)
+  %11 = tail call <16 x i32> @llvm.hexagon.V6.vsubwnq(<512 x i1> %7, <16 x i32> %v3.0258, <16 x i32> %v5.0260)
+  %12 = tail call <16 x i32> @llvm.hexagon.V6.vaddwnq(<512 x i1> %8, <16 x i32> %11, <16 x i32> %v6.0261)
+  %13 = tail call <16 x i32> @llvm.hexagon.V6.vsubwnq(<512 x i1> %9, <16 x i32> %12, <16 x i32> %v7.0262)
+  %14 = tail call <16 x i32> @llvm.hexagon.V6.vaddwnq(<512 x i1> %10, <16 x i32> %13, <16 x i32> undef)
+  %incdec.ptr66.3 = getelementptr inbounds <16 x i32>, <16 x i32>* %vo.addr.0287, i32 4
+  store <16 x i32> %14, <16 x i32>* undef, align 64
+  %incdec.ptr67.3 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi.addr.0288, i32 4
+  %v31.0.4 = load <16 x i32>, <16 x i32>* %incdec.ptr67.2, align 64
+  %15 = tail call <16 x i32> @llvm.hexagon.V6.vaddwnq(<512 x i1> undef, <16 x i32> undef, <16 x i32> undef)
+  %16 = tail call <16 x i32> @llvm.hexagon.V6.vsubwnq(<512 x i1> undef, <16 x i32> %15, <16 x i32> %v9.0264)
+  %17 = tail call <16 x i32> @llvm.hexagon.V6.vaddwnq(<512 x i1> undef, <16 x i32> %16, <16 x i32> %v10.0265)
+  %incdec.ptr66.5 = getelementptr inbounds <16 x i32>, <16 x i32>* %vo.addr.0287, i32 6
+  store <16 x i32> %17, <16 x i32>* undef, align 64
+  %incdec.ptr67.5 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi.addr.0288, i32 6
+  %v31.0.6 = load <16 x i32>, <16 x i32>* undef, align 64
+  %incdec.ptr64.6 = getelementptr inbounds i32, i32* %po.addr.0289, i32 7
+  %18 = tail call <512 x i1> @llvm.hexagon.V6.vgtw(<16 x i32> undef, <16 x i32> %v31.0.3)
+  %19 = tail call <512 x i1> @llvm.hexagon.V6.vgtw.xor(<512 x i1> undef, <16 x i32> %v26.0281, <16 x i32> %v27.0282)
+  %20 = tail call <512 x i1> @llvm.hexagon.V6.vgtw.xor(<512 x i1> %19, <16 x i32> %v7.0262, <16 x i32> %v6.0261)
+  %21 = tail call <16 x i32> @llvm.hexagon.V6.vsubwnq(<512 x i1> %18, <16 x i32> %v6.0261, <16 x i32> undef)
+  %22 = tail call <16 x i32> @llvm.hexagon.V6.vaddwnq(<512 x i1> undef, <16 x i32> %21, <16 x i32> %v9.0264)
+  %23 = tail call <16 x i32> @llvm.hexagon.V6.vsubwnq(<512 x i1> %19, <16 x i32> %22, <16 x i32> %v10.0265)
+  %24 = tail call <16 x i32> @llvm.hexagon.V6.vaddwnq(<512 x i1> %20, <16 x i32> %23, <16 x i32> %v11.0266)
+  %incdec.ptr66.6 = getelementptr inbounds <16 x i32>, <16 x i32>* %vo.addr.0287, i32 7
+  store <16 x i32> %24, <16 x i32>* %incdec.ptr66.5, align 64
+  %incdec.ptr67.6 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi.addr.0288, i32 7
+  %v31.0.7 = load <16 x i32>, <16 x i32>* %incdec.ptr67.5, align 64
+  %incdec.ptr64.7 = getelementptr inbounds i32, i32* %po.addr.0289, i32 8
+  store i32 undef, i32* %incdec.ptr64.6, align 4
+  %incdec.ptr66.7 = getelementptr inbounds <16 x i32>, <16 x i32>* %vo.addr.0287, i32 8
+  store <16 x i32> undef, <16 x i32>* %incdec.ptr66.6, align 64
+  %incdec.ptr67.7 = getelementptr inbounds <16 x i32>, <16 x i32>* %vi.addr.0288, i32 8
+  %niter.nsub.7 = add i32 %niter, -8
+  %niter.ncmp.7 = icmp eq i32 %niter.nsub.7, 0
+  br i1 %niter.ncmp.7, label %for.end.loopexit.unr-lcssa, label %for.body
+
+for.end.loopexit.unr-lcssa:                       ; preds = %for.body, %for.body.preheader
+  br i1 undef, label %for.end, label %for.body.epil
+
+for.body.epil:                                    ; preds = %for.body.epil, %for.end.loopexit.unr-lcssa
+  br i1 undef, label %for.end, label %for.body.epil
+
+for.end:                                          ; preds = %for.body.epil, %for.end.loopexit.unr-lcssa, %entry
+  ret i32 0
+}
+
+declare <512 x i1> @llvm.hexagon.V6.vgtw(<16 x i32>, <16 x i32>) #1
+declare <512 x i1> @llvm.hexagon.V6.vgtw.xor(<512 x i1>, <16 x i32>, <16 x i32>) #1
+declare <16 x i32> @llvm.hexagon.V6.vsubwnq(<512 x i1>, <16 x i32>, <16 x i32>) #1
+declare <16 x i32> @llvm.hexagon.V6.vaddwnq(<512 x i1>, <16 x i32>, <16 x i32>) #1
+
+attributes #0 = { nounwind "target-cpu"="hexagonv60" "target-features"="+hvx,-hvx-double" }
+attributes #1 = { nounwind readnone }