[AVR] Optimize 8-bit int shift

[benshi001]

It is hard to use SelectionDAG instead of Pseudo instructions for this optimization.

Since for LSL7, the instr serial is

ROR Rx 
CLR Rx
ROR Rx

There is no dependancy between ROR and CLR, so DAG can not be created properly.

This patch is a supplement to https://reviews.llvm.org/D89047

[benshi001]

Now llvm-avr generates the same asm for 8-bit shifts when ShiftAmount = 1,2,3,4,5,6, 7.

[benshi001]

Now llvm-avr generates the same asm for 8-bit shifts as AVR-GCC does, when ShiftAmount = 1,2,3,4,5,6, 7.

[dylanmckay]

Nice work, approved.

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

bool AVRExpandPseudo::expand<AVR::ASRWRd>(Block &MBB, BlockIt MBBI) {
 
   // SREG is always implicitly killed
   MIBLO->getOperand(3).setIsKill();
 
   MI.eraseFromParent();
   return true;
 }
 
+template <>
+bool AVRExpandPseudo::expand<AVR::LSLB7Rd>(Block &MBB, BlockIt MBBI) {
+  MachineInstr &MI = *MBBI;
+  Register DstReg = MI.getOperand(0).getReg();
+  bool DstIsDead = MI.getOperand(0).isDead();
+  bool DstIsKill = MI.getOperand(1).isKill();
+  bool ImpIsDead = MI.getOperand(2).isDead();
+
+  // ror r24
+  // clr r24
+  // ror r24
+
+  buildMI(MBB, MBBI, AVR::RORRd)
+      .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstReg, getKillRegState(DstIsKill));
+
+  buildMI(MBB, MBBI, AVR::EORRdRr)
+      .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstReg, getKillRegState(DstIsKill))
+      .addReg(DstReg, getKillRegState(DstIsKill));
+
+  auto MIRRC =
+      buildMI(MBB, MBBI, AVR::RORRd)
+          .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstReg, getKillRegState(DstIsKill));
+
+  if (ImpIsDead)
+    MIRRC->getOperand(2).setIsDead();
+
+  // SREG is always implicitly killed
+  MIRRC->getOperand(3).setIsKill();
+
+  MI.eraseFromParent();
+  return true;
+}
+
+template <>
+bool AVRExpandPseudo::expand<AVR::LSRB7Rd>(Block &MBB, BlockIt MBBI) {
+  MachineInstr &MI = *MBBI;
+  Register DstReg = MI.getOperand(0).getReg();
+  bool DstIsDead = MI.getOperand(0).isDead();
+  bool DstIsKill = MI.getOperand(1).isKill();
+  bool ImpIsDead = MI.getOperand(2).isDead();
+
+  // rol r24
+  // clr r24
+  // rol r24
+
+  buildMI(MBB, MBBI, AVR::ADCRdRr)
+      .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstReg, getKillRegState(DstIsKill))
+      .addReg(DstReg, getKillRegState(DstIsKill));
+
+  buildMI(MBB, MBBI, AVR::EORRdRr)
+      .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstReg, getKillRegState(DstIsKill))
+      .addReg(DstReg, getKillRegState(DstIsKill));
+
+  auto MIRRC =
+      buildMI(MBB, MBBI, AVR::ADCRdRr)
+          .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstReg, getKillRegState(DstIsKill))
+          .addReg(DstReg, getKillRegState(DstIsKill));
+
+  if (ImpIsDead)
+    MIRRC->getOperand(3).setIsDead();
+
+  // SREG is always implicitly killed
+  MIRRC->getOperand(4).setIsKill();
+
+  MI.eraseFromParent();
+  return true;
+}
+
+template <>
+bool AVRExpandPseudo::expand<AVR::ASRB7Rd>(Block &MBB, BlockIt MBBI) {
+  MachineInstr &MI = *MBBI;
+  Register DstReg = MI.getOperand(0).getReg();
+  bool DstIsDead = MI.getOperand(0).isDead();
+  bool DstIsKill = MI.getOperand(1).isKill();
+  bool ImpIsDead = MI.getOperand(2).isDead();
+
+  // lsl r24
+  // sbc r24, r24
+
+  buildMI(MBB, MBBI, AVR::ADDRdRr)
+      .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstReg, getKillRegState(DstIsKill))
+      .addReg(DstReg, getKillRegState(DstIsKill));
+
+  auto MIRRC = buildMI(MBB, MBBI, AVR::SBCRdRr)
+      .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstReg, getKillRegState(DstIsKill))
+      .addReg(DstReg, getKillRegState(DstIsKill));
+
+  if (ImpIsDead)
+    MIRRC->getOperand(3).setIsDead();
+
+  // SREG is always implicitly killed
+  MIRRC->getOperand(4).setIsKill();
+
+  MI.eraseFromParent();
+  return true;
+}
+
 template <> bool AVRExpandPseudo::expand<AVR::SEXT>(Block &MBB, BlockIt MBBI) {
   MachineInstr &MI = *MBBI;
   Register DstLoReg, DstHiReg;
   // sext R17:R16, R17
   // mov     r16, r17
   // lsl     r17
   // sbc     r17, r17
   // sext R17:R16, R13
case AVR::LDDWRdYQ: //:FIXME: remove this once PR13375 gets fixed
     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::LSLB7Rd);
+    EXPAND(AVR::LSRB7Rd);
+    EXPAND(AVR::ASRB7Rd);
     EXPAND(AVR::SEXT);
     EXPAND(AVR::ZEXT);
     EXPAND(AVR::SPREAD);
     EXPAND(AVR::SPWRITE);
   }
 #undef EXPAND
   return false;
 }

llvm/lib/Target/AVR/AVRISelLowering.h

enum NodeType {
   /// which includes a bunch of information.
   CALL,
   /// A wrapper node for TargetConstantPool,
   /// TargetExternalSymbol, and TargetGlobalAddress.
   WRAPPER,
   LSL,     ///< Logical shift left.
   LSR,     ///< Logical shift right.
   ASR,     ///< Arithmetic shift right.
+  LSL7,    ///< Logical shift left 7 bits.
+  LSR7,    ///< Logical shift right 7 bits.
+  ASR7,    ///< Arithmetic shift right 7 bits.
   ROR,     ///< Bit rotate right.
   ROL,     ///< Bit rotate left.
   LSLLOOP, ///< A loop of single logical shift left instructions.
   LSRLOOP, ///< A loop of single logical shift right instructions.
   ROLLOOP, ///< A loop of single left bit rotate instructions.
   RORLOOP, ///< A loop of single right bit rotate instructions.
   ASRLOOP, ///< A loop of single arithmetic shift right instructions.
   /// AVR conditional branches. Operand 0 is the chain operand, operand 1

llvm/lib/Target/AVR/AVRISelLowering.cpp

if (Op.getOpcode() == ISD::SHL && 4 <= ShiftAmount && ShiftAmount < 7) {
       ShiftAmount -= 4;
     } else if (Op.getOpcode() == ISD::SRL && 4 <= ShiftAmount &&
                ShiftAmount < 7) {
       // Optimize LSR when 4 <= ShiftAmount <= 6.
       Victim = DAG.getNode(AVRISD::SWAP, dl, VT, Victim);
       Victim =
           DAG.getNode(ISD::AND, dl, VT, Victim, DAG.getConstant(0x0f, dl, VT));
       ShiftAmount -= 4;
+    } else if (Op.getOpcode() == ISD::SHL && ShiftAmount == 7) {
+      // Optimize LSL when ShiftAmount == 7.
+      Victim = DAG.getNode(AVRISD::LSL7, dl, VT, Victim);
+      ShiftAmount = 0;
+    } else if (Op.getOpcode() == ISD::SRL && ShiftAmount == 7) {
+      // Optimize LSR when ShiftAmount == 7.
+      Victim = DAG.getNode(AVRISD::LSR7, dl, VT, Victim);
+      ShiftAmount = 0;
+    } else if (Op.getOpcode() == ISD::SRA && ShiftAmount == 7) {
+      // Optimize ASR when ShiftAmount == 7.
+      Victim = DAG.getNode(AVRISD::ASR7, dl, VT, Victim);
+      ShiftAmount = 0;
     }
   }
 
   while (ShiftAmount--) {
     Victim = DAG.getNode(Opc8, dl, VT, Victim);
   }
 
   return Victim;

llvm/lib/Target/AVR/AVRInstrInfo.td

 def AVRselectcc: SDNode<"AVRISD::SELECT_CC", SDT_AVRSelectCC, [SDNPInGlue]>;
 
 // Shift nodes.
 def AVRlsl : SDNode<"AVRISD::LSL", SDTIntUnaryOp>;
 def AVRlsr : SDNode<"AVRISD::LSR", SDTIntUnaryOp>;
 def AVRrol : SDNode<"AVRISD::ROL", SDTIntUnaryOp>;
 def AVRror : SDNode<"AVRISD::ROR", SDTIntUnaryOp>;
 def AVRasr : SDNode<"AVRISD::ASR", SDTIntUnaryOp>;
+def AVRlsl7 : SDNode<"AVRISD::LSL7", SDTIntUnaryOp>;
+def AVRlsr7 : SDNode<"AVRISD::LSR7", SDTIntUnaryOp>;
+def AVRasr7 : SDNode<"AVRISD::ASR7", SDTIntUnaryOp>;
 
 // Pseudo shift nodes for non-constant shift amounts.
 def AVRlslLoop : SDNode<"AVRISD::LSLLOOP", SDTIntShiftOp>;
 def AVRlsrLoop : SDNode<"AVRISD::LSRLOOP", SDTIntShiftOp>;
 def AVRrolLoop : SDNode<"AVRISD::ROLLOOP", SDTIntShiftOp>;
 def AVRrorLoop : SDNode<"AVRISD::RORLOOP", SDTIntShiftOp>;
 def AVRasrLoop : SDNode<"AVRISD::ASRLOOP", SDTIntShiftOp>;
 

 {
   // 8-bit LSL is an alias of ADD Rd, Rd
 
   def LSLWRd : Pseudo<(outs DREGS:$rd),
                       (ins DREGS:$src),
                       "lslw\t$rd",
                       [(set i16:$rd, (AVRlsl i16:$src)), (implicit SREG)]>;
 
+  def LSLB7Rd : Pseudo<(outs GPR8:$rd),
+                       (ins GPR8:$src),
+                       "lslb7\t$rd",
+                       [(set i8:$rd, (AVRlsl7 i8:$src)), (implicit SREG)]>;
+
   def LSRRd : FRd<0b1001,
                   0b0100110,
                   (outs GPR8:$rd),
                   (ins GPR8:$src),
                   "lsr\t$rd",
                   [(set i8:$rd, (AVRlsr i8:$src)), (implicit SREG)]>;
 
+  def LSRB7Rd : Pseudo<(outs GPR8:$rd),
+                       (ins GPR8:$src),
+                       "lsrb7\t$rd",
+                       [(set i8:$rd, (AVRlsr7 i8:$src)), (implicit SREG)]>;
+
   def LSRWRd : Pseudo<(outs DREGS:$rd),
                       (ins DREGS:$src),
                       "lsrw\t$rd",
                       [(set i16:$rd, (AVRlsr i16:$src)), (implicit SREG)]>;
 
   def ASRRd : FRd<0b1001,
                   0b0100101,
                   (outs GPR8:$rd),
                   (ins GPR8:$src),
                   "asr\t$rd",
                   [(set i8:$rd, (AVRasr i8:$src)), (implicit SREG)]>;
 
+  def ASRB7Rd : Pseudo<(outs GPR8:$rd),
+                       (ins GPR8:$src),
+                       "asrb7\t$rd",
+                       [(set i8:$rd, (AVRasr7 i8:$src)), (implicit SREG)]>;
+
   def ASRWRd : Pseudo<(outs DREGS:$rd),
                       (ins DREGS:$src),
                       "asrw\t$rd",
                       [(set i16:$rd, (AVRasr i16:$src)), (implicit SREG)]>;
 
   // Bit rotate operations.
   let Uses = [SREG] in
   {

llvm/test/CodeGen/AVR/shift.ll

 ; CHECK-LABEL: lsr_i8_6:
 ; CHECK:       swap r24
 ; CHECK-NEXT:  andi r24, 15
 ; CHECK-NEXT:  lsr r24
 ; CHECK-NEXT:  lsr r24
   %res = lshr i8 %a, 6
   ret i8 %res
 }
+
+define i8 @lsl_i8_7(i8 %a) {
+; CHECK-LABEL: lsl_i8_7
+; CHECK:      ror r24
+; CHECK-NEXT: clr r24
+; CHECK-NEXT: ror r24
+  %result = shl i8 %a, 7
+  ret i8 %result
+}
+
+define i8 @lsr_i8_7(i8 %a) {
+; CHECK-LABEL: lsr_i8_7
+; CHECK:      rol r24
+; CHECK-NEXT: clr r24
+; CHECK-NEXT: rol r24
+  %result = lshr i8 %a, 7
+  ret i8 %result
+}
+
+define i8 @asr_i8_7(i8 %a) {
+; CHECK-LABEL: asr_i8_7
+; CHECK:      lsl r24
+; CHECK-NEXT: sbc r24, r24
+  %result = ashr i8 %a, 7
+  ret i8 %result
+}

llvm/test/CodeGen/AVR/smul-with-overflow.ll

 ; RUN: llc -mattr=avr6 < %s -march=avr | FileCheck %s
 
 define i1 @signed_multiplication_did_overflow(i8, i8) unnamed_addr {
 ; CHECK-LABEL: signed_multiplication_did_overflow:
 entry-block:
   %2 = tail call { i8, i1 } @llvm.smul.with.overflow.i8(i8 %0, i8 %1)
   %3 = extractvalue { i8, i1 } %2, 1
   ret i1 %3
 
 ; Multiply, fill the low byte with the sign of the low byte via
 ; arithmetic shifting, compare it to the high byte.
 ;
 ; CHECK: muls   r24, r22
 ; CHECK: mov    [[HIGH:r[0-9]+]], r1
 ; CHECK: mov    [[LOW:r[0-9]+]], r0
-; CHECK: asr    {{.*}}[[LOW]]
-; CHECK: asr    {{.*}}[[LOW]]
-; CHECK: asr    {{.*}}[[LOW]]
-; CHECK: asr    {{.*}}[[LOW]]
-; CHECK: asr    {{.*}}[[LOW]]
-; CHECK: asr    {{.*}}[[LOW]]
-; CHECK: asr    {{.*}}[[LOW]]
+; CHECK: lsl    {{.*}}[[LOW]]
+; CHECK: sbc    {{.*}}[[LOW]], {{.*}}[[LOW]]
 ; CHECK: ldi    [[RET:r[0-9]+]], 1
 ; CHECK: cp     {{.*}}[[HIGH]], {{.*}}[[LOW]]
 ; CHECK: brne   [[LABEL:.LBB[_0-9]+]]
 ; CHECK: ldi    {{.*}}[[RET]], 0
 ; CHECK: {{.*}}[[LABEL]]
 ; CHECK: ret
 }
 
 declare { i8, i1 } @llvm.smul.with.overflow.i8(i8, i8)