[AVR] Remove unused register scavenger

[aykevl]

Summary

It was necessary in the past, but is not necessary anymore today. Instead, rely on the register allocator to allocate the correct registers.

The LPMW/ELPMW instruction can be modified to use an earlyclobber, which prevents it from using the Z register as an output register.

Also see: D131844

[benshi001]

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

751–752

Remove this comment line.

[benshi001]

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

792–793

I did not understand how this assert is guranteed for LPM/ELPM.

[benshi001]

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

792–793

Do we need a constraint like Constraints = "$src != $rd" in the definition of LPM/ELPM to gurantee that ?

[benshi001]

since https://reviews.llvm.org/D131844 is accepted, can we close this one ?

[aykevl]

No, I plan to update this PR so that it only includes the LPMW/ELPMW changes and to fix your review comments.

[aykevl]

• update after D131844

[aykevl]

llvm/lib/Target/AVR/AVRInstrInfo.td

1682

I tried $dst != $z but that led to a "ran out of registers during register allocation" assert. So I'm using @earlyclobber instead (even though it is slightly more conservative).

[benshi001]

LGTM. Thanks.

llvm/lib/Target/AVR/AVRInstrInfo.td

1682

I think @earlyclobber is fine.

[benshi001]

llvm/test/CodeGen/AVR/pseudo/ELPMWRdZ.mir

32

Are the last two lines necessary ? I think the front 3 lines are OK enough.

[aykevl]

Thank you!

llvm/test/CodeGen/AVR/pseudo/ELPMWRdZ.mir

32

Yes. This way the register allocator will try to use R31R30 for %3 to avoid a copy but because of the earlyclobber flag it is forced to pick a different register pair. Therefore, it's a way to test that the earlyclobber works.

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

 #include "AVR.h"
 #include "AVRInstrInfo.h"
 #include "AVRTargetMachine.h"
 #include "MCTargetDesc/AVRMCTargetDesc.h"
 
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/RegisterScavenging.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 
 using namespace llvm;
 
 #define AVR_EXPAND_PSEUDO_NAME "AVR pseudo instruction expansion pass"
 
 namespace {
 
private:
   bool expandASRW8Rd(Block &MBB, BlockIt MBBI);
   bool expandLSLW12Rd(Block &MBB, BlockIt MBBI);
   bool expandLSRW12Rd(Block &MBB, BlockIt MBBI);
   bool expandASRW14Rd(Block &MBB, BlockIt MBBI);
   bool expandASRW15Rd(Block &MBB, BlockIt MBBI);
 
   // Common implementation of LPMWRdZ and ELPMWRdZ.
   bool expandLPMWELPMW(Block &MBB, BlockIt MBBI, bool IsExt);
-
-  /// Scavenges a free GPR8 register for use.
-  Register scavengeGPR8(MachineInstr &MI);
 };
 
 char AVRExpandPseudo::ID = 0;
 
 bool AVRExpandPseudo::expandMBB(MachineBasicBlock &MBB) {
   bool Modified = false;
 
   BlockIt MBBI = MBB.begin(), E = MBB.end();
bool AVRExpandPseudo::expand<AVR::LDDWRdPtrQ>(Block &MBB, BlockIt MBBI) {
   bool SrcIsKill = MI.getOperand(1).isKill();
   unsigned OpLo = AVR::LDDRdPtrQ;
   unsigned OpHi = AVR::LDDRdPtrQ;
   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
 
   // Since we add 1 to the Imm value for the high byte below, and 63 is the
   // highest Imm value allowed for the instruction, 62 is the limit here.
   assert(Imm <= 62 && "Offset is out of range");
 
   // DstReg has an earlyclobber so the register allocator will allocate them in
   // separate registers.
   assert(DstReg != SrcReg && "Dst and Src registers are the same!");
 
   // Load low byte.
   buildMI(MBB, MBBI, OpLo)
       .addReg(DstLoReg, RegState::Define)
       .addReg(SrcReg)
       .addImm(Imm)
bool AVRExpandPseudo::expand<AVR::LDDWRdPtrQ>(Block &MBB, BlockIt MBBI) {
   MI.eraseFromParent();
   return true;
 }
 
 bool AVRExpandPseudo::expandLPMWELPMW(Block &MBB, BlockIt MBBI, bool IsExt) {
   MachineInstr &MI = *MBBI;
   Register DstLoReg, DstHiReg;
   Register DstReg = MI.getOperand(0).getReg();
-  Register TmpReg = 0; // 0 for no temporary register
   Register SrcReg = MI.getOperand(1).getReg();
   bool SrcIsKill = MI.getOperand(1).isKill();
   unsigned OpLo = IsExt ? AVR::ELPMRdZPi : AVR::LPMRdZPi;
   unsigned OpHi = IsExt ? AVR::ELPMRdZ : AVR::LPMRdZ;
   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
 
   // Set the I/O register RAMPZ for ELPM.
   if (IsExt) {
     const AVRSubtarget &STI = MBB.getParent()->getSubtarget<AVRSubtarget>();
     Register Bank = MI.getOperand(2).getReg();
     // out RAMPZ, rtmp
     buildMI(MBB, MBBI, AVR::OUTARr).addImm(STI.getIORegRAMPZ()).addReg(Bank);
   }
 
-  // Use a temporary register if src and dst registers are the same.
-  if (DstReg == SrcReg)
-    TmpReg = scavengeGPR8(MI);
-
-  Register CurDstLoReg = (DstReg == SrcReg) ? TmpReg : DstLoReg;
-  Register CurDstHiReg = (DstReg == SrcReg) ? TmpReg : DstHiReg;
+  // This is enforced by the @earlyclobber constraint.
+  assert(DstReg != SrcReg && "SrcReg and DstReg cannot be the same");
 
   // Load low byte.
   auto MIBLO = buildMI(MBB, MBBI, OpLo)
-                   .addReg(CurDstLoReg, RegState::Define)
+                   .addReg(DstLoReg, RegState::Define)
                    .addReg(SrcReg);
 
-  // Push low byte onto stack if necessary.
-  if (TmpReg)
-    buildMI(MBB, MBBI, AVR::PUSHRr).addReg(TmpReg);
-
   // Load high byte.
   auto MIBHI = buildMI(MBB, MBBI, OpHi)
-                   .addReg(CurDstHiReg, RegState::Define)
+                   .addReg(DstHiReg, RegState::Define)
                    .addReg(SrcReg, getKillRegState(SrcIsKill));
 
-  if (TmpReg) {
-    // Move the high byte into the final destination.
-    buildMI(MBB, MBBI, AVR::MOVRdRr, DstHiReg).addReg(TmpReg);
-
-    // Move the low byte from the scratch space into the final destination.
-    buildMI(MBB, MBBI, AVR::POPRd, DstLoReg);
-  }
-
   MIBLO.setMemRefs(MI.memoperands());
   MIBHI.setMemRefs(MI.memoperands());
 
   MI.eraseFromParent();
   return true;
 }
 
 template <>
bool AVRExpandPseudo::expandAtomicBinaryOp(unsigned Opcode, Block &MBB,
   });
 }
 
 bool AVRExpandPseudo::expandAtomicBinaryOp(unsigned Opcode, Block &MBB,
                                            BlockIt MBBI) {
   return expandAtomicBinaryOp(Opcode, MBB, MBBI, [](MachineInstr &MI) {});
 }
 
-Register AVRExpandPseudo::scavengeGPR8(MachineInstr &MI) {
-  MachineBasicBlock &MBB = *MI.getParent();
-  RegScavenger RS;
-
-  RS.enterBasicBlock(MBB);
-  RS.forward(MI);
-
-  BitVector Candidates =
-      TRI->getAllocatableSet(*MBB.getParent(), &AVR::GPR8RegClass);
-
-  // Exclude all the registers being used by the instruction.
-  for (MachineOperand &MO : MI.operands()) {
-    if (MO.isReg() && MO.getReg() != 0 && !MO.isDef() &&
-        !Register::isVirtualRegister(MO.getReg()))
-      Candidates.reset(MO.getReg());
-  }
-
-  BitVector Available = RS.getRegsAvailable(&AVR::GPR8RegClass);
-  Available &= Candidates;
-
-  signed Reg = Available.find_first();
-  assert(Reg != -1 && "ran out of registers");
-  return Reg;
-}
-
 template <>
 bool AVRExpandPseudo::expand<AVR::AtomicLoad8>(Block &MBB, BlockIt MBBI) {
   return expandAtomicBinaryOp(AVR::LDRdPtr, MBB, MBBI);
 }
 
 template <>
 bool AVRExpandPseudo::expand<AVR::AtomicLoad16>(Block &MBB, BlockIt MBBI) {
   return expandAtomicBinaryOp(AVR::LDWRdPtr, MBB, MBBI);

llvm/lib/Target/AVR/AVRInstrInfo.td

let Defs = [R31R30] in {
     def LPMRdZPi : FLPMX<0, 1,
                          (outs GPR8
                           : $rd),
                          (ins ZREG
                           : $z),
                          "lpm\t$rd, $z+", []>,
                    Requires<[HasLPMX]>;
 
+    let Constraints = "@earlyclobber $dst" in
     def LPMWRdZ : Pseudo<(outs DREGS
                           : $dst),
                          (ins ZREG
                           : $z),
                          "lpmw\t$dst, $z", []>,
                   Requires<[HasLPMX]>;
 
     def LPMWRdZPi : Pseudo<(outs DREGS
let mayLoad = 1, hasSideEffects = 0 in {
   }
 
   // These pseudos are combination of the OUT and ELPM instructions.
   let Defs = [R31R30], hasSideEffects = 1 in {
     def ELPMBRdZ : Pseudo<(outs GPR8:$dst), (ins ZREG:$z, LD8:$p),
                           "elpmb\t$dst, $z, $p", []>,
                    Requires<[HasELPMX]>;
 
+    let Constraints = "@earlyclobber $dst" in
     def ELPMWRdZ : Pseudo<(outs DREGS:$dst), (ins ZREG:$z, LD8:$p),
                           "elpmw\t$dst, $z, $p", []>,
                    Requires<[HasELPMX]>;
 
     def ELPMBRdZPi : Pseudo<(outs GPR8:$dst), (ins ZREG:$z, LD8:$p),
                             "elpmb\t$dst, $z+, $p", []>,
                      Requires<[HasELPMX]>;
 

llvm/test/CodeGen/AVR/elpm.ll

 ; CHECK:       ; %bb.0: ; %entry
 ; CHECK-NEXT:    lsl r22
 ; CHECK-NEXT:    rol r23
 ; CHECK-NEXT:    subi r22, -lo8(arr1)
 ; CHECK-NEXT:    sbci r23, -hi8(arr1)
 ; CHECK-NEXT:    movw r30, r22
 ; CHECK-NEXT:    ldi r18, 1
 ; CHECK-NEXT:    out 59, r18
-; CHECK-NEXT:    elpm r18, Z+
-; CHECK-NEXT:    elpm r19, Z
+; CHECK-NEXT:    elpm r20, Z+
+; CHECK-NEXT:    elpm r21, Z
 ; CHECK-NEXT:    lsl r24
 ; CHECK-NEXT:    rol r25
 ; CHECK-NEXT:    subi r24, -lo8(arr0)
 ; CHECK-NEXT:    sbci r25, -hi8(arr0)
 ; CHECK-NEXT:    movw r30, r24
 ; CHECK-NEXT:    lpm r24, Z+
 ; CHECK-NEXT:    lpm r25, Z
-; CHECK-NEXT:    sub r24, r18
-; CHECK-NEXT:    sbc r25, r19
+; CHECK-NEXT:    sub r24, r20
+; CHECK-NEXT:    sbc r25, r21
 ; CHECK-NEXT:    ret
 entry:
   %arrayidx = getelementptr inbounds [4 x i16], [4 x i16] addrspace(1)* @arr0, i16 0, i16 %a
   %0 = load i16, i16 addrspace(1)* %arrayidx, align 1
   %arrayidx1 = getelementptr inbounds [4 x i16], [4 x i16] addrspace(2)* @arr1, i16 0, i16 %b
   %1 = load i16, i16 addrspace(2)* %arrayidx1, align 1
   %sub = sub nsw i16 %0, %1
   ret i16 %sub
 }
 
 define i16 @foo2(i16 %a, i16 %b) {
 ; CHECK-LABEL: foo2:
 ; CHECK:       ; %bb.0: ; %entry
 ; CHECK-NEXT:    lsl r24
 ; CHECK-NEXT:    rol r25
 ; CHECK-NEXT:    subi r24, -lo8(arr2)
 ; CHECK-NEXT:    sbci r25, -hi8(arr2)
 ; CHECK-NEXT:    movw r30, r24
-; CHECK-NEXT:    ldi r24, 2
-; CHECK-NEXT:    out 59, r24
+; CHECK-NEXT:    ldi r18, 2
+; CHECK-NEXT:    out 59, r18
 ; CHECK-NEXT:    elpm r24, Z+
 ; CHECK-NEXT:    elpm r25, Z
 ; CHECK-NEXT:    lsl r22
 ; CHECK-NEXT:    rol r23
 ; CHECK-NEXT:    subi r22, -lo8(arr0)
 ; CHECK-NEXT:    sbci r23, -hi8(arr0)
 ; CHECK-NEXT:    movw r30, r22
 ; CHECK-NEXT:    lpm r18, Z+

 ; CHECK:       ; %bb.0: ; %entry
 ; CHECK-NEXT:    lsl r22
 ; CHECK-NEXT:    rol r23
 ; CHECK-NEXT:    subi r22, -lo8(arr1)
 ; CHECK-NEXT:    sbci r23, -hi8(arr1)
 ; CHECK-NEXT:    movw r30, r22
 ; CHECK-NEXT:    ldi r18, 1
 ; CHECK-NEXT:    out 59, r18
-; CHECK-NEXT:    elpm r18, Z+
-; CHECK-NEXT:    elpm r19, Z
+; CHECK-NEXT:    elpm r20, Z+
+; CHECK-NEXT:    elpm r21, Z
 ; CHECK-NEXT:    lsl r24
 ; CHECK-NEXT:    rol r25
 ; CHECK-NEXT:    subi r24, -lo8(arr2)
 ; CHECK-NEXT:    sbci r25, -hi8(arr2)
 ; CHECK-NEXT:    movw r30, r24
-; CHECK-NEXT:    ldi r24, 2
-; CHECK-NEXT:    out 59, r24
+; CHECK-NEXT:    ldi r18, 2
+; CHECK-NEXT:    out 59, r18
 ; CHECK-NEXT:    elpm r24, Z+
 ; CHECK-NEXT:    elpm r25, Z
-; CHECK-NEXT:    sub r24, r18
-; CHECK-NEXT:    sbc r25, r19
+; CHECK-NEXT:    sub r24, r20
+; CHECK-NEXT:    sbc r25, r21
 ; CHECK-NEXT:    ret
 entry:
   %arrayidx = getelementptr inbounds [4 x i16], [4 x i16] addrspace(3)* @arr2, i16 0, i16 %a
   %0 = load i16, i16 addrspace(3)* %arrayidx, align 1
   %arrayidx1 = getelementptr inbounds [4 x i16], [4 x i16] addrspace(2)* @arr1, i16 0, i16 %b
   %1 = load i16, i16 addrspace(2)* %arrayidx1, align 1
   %sub = sub nsw i16 %0, %1
   ret i16 %sub

llvm/test/CodeGen/AVR/pseudo/ELPMWRdZ.mir

+# RUN: llc -mcpu=atmega1284p -start-before=greedy %s -o - | FileCheck %s
+
+# This test checks the expansion of the 16-bit ELPM pseudo instruction and that
+# the register allocator won't use R31R30 as an output register (which would
+# lead to undefined behavior).
+
+--- |
+  target triple = "avr--"
+  define void @test_elpmwrdz() {
+  entry:
+    ret void
+  }
+...
+
+---
+name:            test_elpmwrdz
+tracksRegLiveness: true
+body: |
+  bb.0.entry:
+    liveins: $r31r30
+
+    ; CHECK-LABEL: test_elpmwrdz
+    ; CHECK:      elpm r24, Z+
+    ; CHECK-NEXT: elpm r25, Z
+    ; CHECK-NEXT: movw r30, r24
+
+    %1:zreg = COPY killed $r31r30
+    %2:ld8 = LDIRdK 1
+    %3:dregs = ELPMWRdZ %1, %2, implicit-def dead $r31r30
+    $r31r30 = COPY %3
+    RET implicit $r31r30
+...