[AVR] Fix codegen for rotate instructions

[dsprenkels]

Summary

This patch introduces the ROLBRd and RORBRd pseudo-instructions,
which implemenent the "traditional" rotate operations; instead of
the AVR rotate instructions that use the carry bit.

The code is not optimized at all. Especially when dealing with
loops of rotate instructions, this codegen should be improved some
day.

Related bug: 41358 https://bugs.llvm.org/show_bug.cgi?id=41358

Note: This is my first submitted patch.

[dylanmckay]

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

1275

This variable is called ZeroReg, and reading the code my inference is that the ZeroReg contains the register number of the zero-register, r1, which is a register that, according to the calling convention, is always guaranteed to contain the value 0.

I recommend either modifying the logic to use the dedicated zero register instead of a scavenged temporary, or renaming the variable from ZeroReg to something like TempRegWithZero.

1321

Same here re. dedicated zero register.

[dsprenkels]

Thank you for the feedback. I will try to update the patch code this weekend.

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

1275

When I wrote the patch I hadn't yet found that r1 is always zero. I will update the assembly to:

add r16, r16
adc r16, r1

1321

Here, I'd like the keep the variable's name TmpReg, as its value is not exactly zero after executing the intstructions.

[dsprenkels]

Updates:

• Use the temporary registers r1 and r0, instead of scavenging spare registers.
  • And update the test case.
• Add the definition const unsigned ZERO_REGISTER = AVR::R1 for future use.

[dylanmckay]

llvm/lib/Target/AVR/AVRInstrInfo.td

1682

What does the b stand for in the instruction mnemonics?

Perhaps it would make sense to rename the AVR ISD nodes (such as AVRrol and AVRror to AVRbrol AVRbror).

1687

This instruction is a right rotation, but the pattern matches on a left rotation AVRrol, which is also the exact same pattern as the other new instruction.

Should this be AVRror?

1699

The patterns for RORRd and co still exist. Should these be removed so that we never ISel them by default?

[dsprenkels]

llvm/lib/Target/AVR/AVRInstrInfo.td

1682

In this mnemonic, b stands for byte. Line 1689 defines the ROLWRd pseudo-instruction, so it makes sense to call this one ROLBRd.

Perhaps it would make sense to rename the AVR ISD nodes (such as AVRrol and AVRror to AVRbrol AVRbror).

I totally agree.

1687

Should this be AVRror?

Yes. I will fix this.

1699

That sounds like a good idea. The pattern, is that just the [(set i8:$rd, (AVRror i8:$src)), (implicit SREG)]> part?

[dsprenkels]

Removed the pattern for RORRd.

[dsprenkels]

llvm/lib/Target/AVR/AVRInstrInfo.td

1682

Perhaps it would make sense to rename the AVR ISD nodes (such as AVRrol and AVRror to AVRbrol AVRbror).

I totally agree.

I refrained from doing this. I am not really sure which instructions should get the b suffix. If we add the suffix to the rotate instructions, should we also add them to shift instructions, etc. I hope we could postpone this improvement to another patch.

[dylanmckay]

Approved, sorry for the super long turn around on this @dsprenkels, I wanted to get an simulated integration test passing before I landed this and I finally worked out all the kinks.

Nice patch, thanks for the hard work!

llvm/lib/Target/AVR/AVRInstrInfo.td

1682

Sounds good to me @dsprenkels

[dsprenkels]

Awesome. Thanks for reviewing!

I don't have any push permissions. Can you (or somebody else) commit this patch?

I will likely start on the renaming of the instructions next, (see

Perhaps it would make sense to rename the AVR ISD nodes (such as AVRrol and AVRror to AVRbrol AVRbror).

), and peephole optimization for shifts (using the swap instruction etc.).

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

private:
   typedef MachineBasicBlock Block;
   typedef Block::iterator BlockIt;
 
   const AVRRegisterInfo *TRI;
   const TargetInstrInfo *TII;
 
   /// The register to be used for temporary storage.
   const unsigned SCRATCH_REGISTER = AVR::R0;
+  /// The register that will always contain zero.
+  const unsigned ZERO_REGISTER = AVR::R1;
   /// The IO address of the status register.
   const unsigned SREG_ADDR = 0x3f;
 
   bool expandMBB(Block &MBB);
   bool expandMI(Block &MBB, BlockIt MBBI);
   template <unsigned OP> bool expand(Block &MBB, BlockIt MBBI);
 
   MachineInstrBuilder buildMI(Block &MBB, BlockIt MBBI, unsigned Opcode) {
bool AVRExpandPseudo::expand<AVR::POPWRd>(Block &MBB, BlockIt MBBI) {
   buildMI(MBB, MBBI, OpHi, DstHiReg).setMIFlags(Flags); // High
   buildMI(MBB, MBBI, OpLo, DstLoReg).setMIFlags(Flags); // Low
 
   MI.eraseFromParent();
   return true;
 }
 
 template <>
+bool AVRExpandPseudo::expand<AVR::ROLBRd>(Block &MBB, BlockIt MBBI) {
+  // In AVR, the rotate instructions behave quite unintuitively. They rotate
+  // bits through the carry bit in SREG, effectively rotating over 9 bits,
+  // instead of 8. This is useful when we are dealing with numbers over
+  // multiple registers, but when we actually need to rotate stuff, we have
+  // to explicitly add the carry bit.
+
+  MachineInstr &MI = *MBBI;
+  unsigned OpShift, OpCarry;
+  unsigned DstReg = MI.getOperand(0).getReg();
+  bool DstIsDead = MI.getOperand(0).isDead();
+  OpShift = AVR::ADDRdRr;
+  OpCarry = AVR::ADCRdRr;
+
+  // add r16, r16
+  // adc r16, r1
+
+  // Shift part
+  buildMI(MBB, MBBI, OpShift)
+    .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+    .addReg(DstReg)
+    .addReg(DstReg);
+
+  // Add the carry bit
+  auto MIB = buildMI(MBB, MBBI, OpCarry)
+    .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+    .addReg(DstReg)
+    .addReg(ZERO_REGISTER);
+
+  // SREG is always implicitly killed
+  MIB->getOperand(2).setIsKill();
+
+  MI.eraseFromParent();
+  return true;
+}
+
+template <>
+bool AVRExpandPseudo::expand<AVR::RORBRd>(Block &MBB, BlockIt MBBI) {
+  // In AVR, the rotate instructions behave quite unintuitively. They rotate
+  // bits through the carry bit in SREG, effectively rotating over 9 bits,
+  // instead of 8. This is useful when we are dealing with numbers over
+  // multiple registers, but when we actually need to rotate stuff, we have
+  // to explicitly add the carry bit.
+
+  MachineInstr &MI = *MBBI;
+  unsigned OpShiftOut, OpLoad, OpShiftIn, OpAdd;
+  unsigned DstReg = MI.getOperand(0).getReg();
+  bool DstIsDead = MI.getOperand(0).isDead();
+  OpShiftOut = AVR::LSRRd;
+  OpLoad = AVR::LDIRdK;
+  OpShiftIn = AVR::RORRd;
+  OpAdd = AVR::ORRdRr;
+
+  // lsr r16
+  // ldi r0, 0
+  // ror r0
+  // or r16, r17
+
+  // Shift out
+  buildMI(MBB, MBBI, OpShiftOut)
+    .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+    .addReg(DstReg);
+
+  // Put 0 in temporary register
+  buildMI(MBB, MBBI, OpLoad)
+    .addReg(SCRATCH_REGISTER, RegState::Define | getDeadRegState(true))
+    .addImm(0x00);
+
+  // Shift in
+  buildMI(MBB, MBBI, OpShiftIn)
+    .addReg(SCRATCH_REGISTER, RegState::Define | getDeadRegState(true))
+    .addReg(SCRATCH_REGISTER);
+
+  // Add the results together using an or-instruction
+  auto MIB = buildMI(MBB, MBBI, OpAdd)
+    .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+    .addReg(DstReg)
+    .addReg(SCRATCH_REGISTER);
+
+  // SREG is always implicitly killed
+  MIB->getOperand(2).setIsKill();
+
+  MI.eraseFromParent();
+  return true;
+}
+
+template <>
 bool AVRExpandPseudo::expand<AVR::LSLWRd>(Block &MBB, BlockIt MBBI) {
   MachineInstr &MI = *MBBI;
   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
   unsigned DstReg = MI.getOperand(0).getReg();
   bool DstIsDead = MI.getOperand(0).isDead();
   bool DstIsKill = MI.getOperand(1).isKill();
   bool ImpIsDead = MI.getOperand(2).isDead();
   OpLo = AVR::ADDRdRr; // ADD Rd, Rd <==> LSL Rd
case AVR::LDDWRdYQ: //:FIXME: remove this once PR13375 gets fixed
     EXPAND(AVR::STWPtrRr);
     EXPAND(AVR::STWPtrPiRr);
     EXPAND(AVR::STWPtrPdRr);
     EXPAND(AVR::STDWPtrQRr);
     EXPAND(AVR::INWRdA);
     EXPAND(AVR::OUTWARr);
     EXPAND(AVR::PUSHWRr);
     EXPAND(AVR::POPWRd);
+    EXPAND(AVR::ROLBRd);
+    EXPAND(AVR::RORBRd);
     EXPAND(AVR::LSLWRd);
     EXPAND(AVR::LSRWRd);
     EXPAND(AVR::RORWRd);
     EXPAND(AVR::ROLWRd);
     EXPAND(AVR::ASRWRd);
     EXPAND(AVR::SEXT);
     EXPAND(AVR::ZEXT);
     EXPAND(AVR::SPREAD);

llvm/lib/Target/AVR/AVRISelLowering.cpp

case AVR::Lsr8:
     Opc = AVR::LSRRd;
     RC = &AVR::GPR8RegClass;
     break;
   case AVR::Lsr16:
     Opc = AVR::LSRWRd;
     RC = &AVR::DREGSRegClass;
     break;
   case AVR::Rol8:
-    Opc = AVR::ADCRdRr; // ROL is an alias of ADC Rd, Rd
+    Opc = AVR::ROLBRd;
     RC = &AVR::GPR8RegClass;
-    HasRepeatedOperand = true;
     break;
   case AVR::Rol16:
     Opc = AVR::ROLWRd;
     RC = &AVR::DREGSRegClass;
     break;
   case AVR::Ror8:
-    Opc = AVR::RORRd;
+    Opc = AVR::RORBRd;
     RC = &AVR::GPR8RegClass;
     break;
   case AVR::Ror16:
     Opc = AVR::RORWRd;
     RC = &AVR::DREGSRegClass;
     break;
   }
 

llvm/lib/Target/AVR/AVRInstrInfo.td

def ASRWRd : Pseudo<(outs DREGS:$rd),
                       "asrw\t$rd",
                       [(set i16:$rd, (AVRasr i16:$src)), (implicit SREG)]>;
 
   // Bit rotate operations.
   let Uses = [SREG] in
   {
     // 8-bit ROL is an alias of ADC Rd, Rd
 
+    def ROLBRd : Pseudo<(outs GPR8:$rd),
+                        (ins GPR8:$src),
+                        "rolb\t$rd",
+                        [(set i8:$rd, (AVRrol i8:$src)), (implicit SREG)]>;
+
+    def RORBRd : Pseudo<(outs GPR8:$rd),
+                        (ins GPR8:$src),
+                        "rorb\t$rd",
+                        [(set i8:$rd, (AVRror i8:$src)), (implicit SREG)]>;
+
     def ROLWRd : Pseudo<(outs DREGS:$rd),
                         (ins DREGS:$src),
                         "rolw\t$rd",
                         [(set i16:$rd, (AVRrol i16:$src)), (implicit SREG)]>;
 
     def RORRd : FRd<0b1001,
                     0b0100111,
                     (outs GPR8:$rd),
                     (ins GPR8:$src),
                     "ror\t$rd",
-                    [(set i8:$rd, (AVRror i8:$src)), (implicit SREG)]>;
+                    []>;
 
     def RORWRd : Pseudo<(outs DREGS:$rd),
                         (ins DREGS:$src),
                         "rorw\t$rd",
                         [(set i16:$rd, (AVRror i16:$src)), (implicit SREG)]>;
   }
 }
 

llvm/test/CodeGen/AVR/rot.ll

 ; RUN: llc < %s -march=avr | FileCheck %s
 
 ; Bit rotation tests.
 
 ; CHECK-LABEL: rol8:
 define i8 @rol8(i8 %val, i8 %amt) {
   ; CHECK:      andi r22, 7
 
   ; CHECK-NEXT: cpi r22, 0
   ; CHECK-NEXT: breq LBB0_2
 
 ; CHECK-NEXT: LBB0_1:
-  ; CHECK-NEXT: rol r24
+  ; CHECK-NEXT: lsl r24
+  ; CHECK-NEXT: adc r24, r1
   ; CHECK-NEXT: subi r22, 1
   ; CHECK-NEXT: brne LBB0_1
 
 ; CHECK-NEXT:LBB0_2:
   ; CHECK-NEXT: ret
   %mod = urem i8 %amt, 8
 
   %inv = sub i8 8, %mod

 ; CHECK-LABEL: ror8:
 define i8 @ror8(i8 %val, i8 %amt) {
   ; CHECK:      andi r22, 7
 
   ; CHECK-NEXT: cpi r22, 0
   ; CHECK-NEXT: breq LBB1_2
 
 ; CHECK-NEXT: LBB1_1:
-  ; CHECK-NEXT: ror r24
+  ; CHECK-NEXT: lsr r24
+  ; CHECK-NEXT: ldi r0, 0
+  ; CHECK-NEXT: ror r0
+  ; CHECK-NEXT: or r24, r0
   ; CHECK-NEXT: subi r22, 1
   ; CHECK-NEXT: brne LBB1_1
 
 ; CHECK-NEXT:LBB1_2:
   ; CHECK-NEXT: ret
   %mod = urem i8 %amt, 8
 
   %inv = sub i8 8, %mod
   %parta = lshr i8 %val, %mod
   %partb = shl i8 %val, %inv
 
   %rotr = or i8 %parta, %partb
 
   ret i8 %rotr
 }