[AVR] Optimize int16 shift operation for shift amount greater than 8

[benshi001]

Summary

Skip operation on the lower byte in int16 logical left shift when
shift amount is greater than 8.

Skip operation on the higher byte in int16 logical & arithmetic
right shift when shift amount is greater than 8.

[aykevl]

Is there a reason why you introduced 3 new pseudo instructions? It seems to me that the existing 16-bit shift instructions (LSLWN, LSRWN, ASRWN) should already be able to support this.

[aykevl]

Ok, I think I see why you did it the way you did. Which makes sense given the current architecture.

I suspect shift lowering might be simpler when it is all done in the "expand pseudo instructions" pass instead of splitting it early in ISelLowering. But most of the logic is already in ISelLowering so it makes sense to keep it there, at least for now.

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

bool AVRExpandPseudo::expand<AVR::LSLWRd>(Block &MBB, BlockIt MBBI) {
 
   // SREG is always implicitly killed
   MIBHI->getOperand(4).setIsKill();
 
   MI.eraseFromParent();
   return true;
 }
 
+template <>
+bool AVRExpandPseudo::expand<AVR::LSLWHiRd>(Block &MBB, BlockIt MBBI) {
+  MachineInstr &MI = *MBBI;
+  Register DstLoReg, DstHiReg;
+  Register DstReg = MI.getOperand(0).getReg();
+  bool DstIsDead = MI.getOperand(0).isDead();
+  bool DstIsKill = MI.getOperand(1).isKill();
+  bool ImpIsDead = MI.getOperand(2).isDead();
+  TRI->splitReg(DstReg, DstLoReg, DstHiReg);
+
+  // add hireg, hireg <==> lsl hireg
+  auto MILSL =
+      buildMI(MBB, MBBI, AVR::ADDRdRr)
+          .addReg(DstHiReg, RegState::Define, getDeadRegState(DstIsDead))
+          .addReg(DstHiReg, getKillRegState(DstIsKill))
+          .addReg(DstHiReg, getKillRegState(DstIsKill));
+
+  if (ImpIsDead)
+    MILSL->getOperand(3).setIsDead();
+
+  MI.eraseFromParent();
+  return true;
+}
+
 bool AVRExpandPseudo::expandLSLW4Rd(Block &MBB, BlockIt MBBI) {
   MachineInstr &MI = *MBBI;
   Register DstLoReg, DstHiReg;
   Register DstReg = MI.getOperand(0).getReg();
   bool DstIsDead = MI.getOperand(0).isDead();
   bool DstIsKill = MI.getOperand(1).isKill();
   bool ImpIsDead = MI.getOperand(3).isDead();
   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
bool AVRExpandPseudo::expand<AVR::LSRWRd>(Block &MBB, BlockIt MBBI) {
 
   // SREG is always implicitly killed
   MIBLO->getOperand(3).setIsKill();
 
   MI.eraseFromParent();
   return true;
 }
 
+template <>
+bool AVRExpandPseudo::expand<AVR::LSRWLoRd>(Block &MBB, BlockIt MBBI) {
+  MachineInstr &MI = *MBBI;
+  Register DstLoReg, DstHiReg;
+  Register DstReg = MI.getOperand(0).getReg();
+  bool DstIsDead = MI.getOperand(0).isDead();
+  bool DstIsKill = MI.getOperand(1).isKill();
+  bool ImpIsDead = MI.getOperand(2).isDead();
+  TRI->splitReg(DstReg, DstLoReg, DstHiReg);
+
+  // lsr loreg
+  auto MILSR =
+      buildMI(MBB, MBBI, AVR::LSRRd)
+          .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstLoReg, getKillRegState(DstIsKill));
+
+  if (ImpIsDead)
+    MILSR->getOperand(2).setIsDead();
+
+  MI.eraseFromParent();
+  return true;
+}
+
 bool AVRExpandPseudo::expandLSRW4Rd(Block &MBB, BlockIt MBBI) {
   MachineInstr &MI = *MBBI;
   Register DstLoReg, DstHiReg;
   Register DstReg = MI.getOperand(0).getReg();
   bool DstIsDead = MI.getOperand(0).isDead();
   bool DstIsKill = MI.getOperand(1).isKill();
   bool ImpIsDead = MI.getOperand(3).isDead();
   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
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::ASRWLoRd>(Block &MBB, BlockIt MBBI) {
+  MachineInstr &MI = *MBBI;
+  Register DstLoReg, DstHiReg;
+  Register DstReg = MI.getOperand(0).getReg();
+  bool DstIsDead = MI.getOperand(0).isDead();
+  bool DstIsKill = MI.getOperand(1).isKill();
+  bool ImpIsDead = MI.getOperand(2).isDead();
+  TRI->splitReg(DstReg, DstLoReg, DstHiReg);
+
+  // asr loreg
+  auto MIASR =
+      buildMI(MBB, MBBI, AVR::ASRRd)
+          .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstLoReg, getKillRegState(DstIsKill));
+
+  if (ImpIsDead)
+    MIASR->getOperand(2).setIsDead();
+
+  MI.eraseFromParent();
+  return true;
+}
+
 bool AVRExpandPseudo::expandASRW8Rd(Block &MBB, BlockIt MBBI) {
   MachineInstr &MI = *MBBI;
   Register DstLoReg, DstHiReg;
   Register DstReg = MI.getOperand(0).getReg();
   bool DstIsDead = MI.getOperand(0).isDead();
   bool DstIsKill = MI.getOperand(1).isKill();
   bool ImpIsDead = MI.getOperand(3).isDead();
   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
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::LSLWHiRd);
+    EXPAND(AVR::LSRWLoRd);
+    EXPAND(AVR::ASRWLoRd);
     EXPAND(AVR::LSLWNRd);
     EXPAND(AVR::LSRWNRd);
     EXPAND(AVR::ASRWNRd);
     EXPAND(AVR::LSLBNRd);
     EXPAND(AVR::LSRBNRd);
     EXPAND(AVR::ASRBNRd);
     EXPAND(AVR::SEXT);
     EXPAND(AVR::ZEXT);

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.
   LSLBN,   ///< Byte logical shift left N bits.
   LSLWN,   ///< Word logical shift left N bits.
+  LSLHI,   ///< Higher 8-bit of word logical shift left.
   LSR,     ///< Logical shift right.
   LSRBN,   ///< Byte logical shift right N bits.
   LSRWN,   ///< Word logical shift right N bits.
+  LSRLO,   ///< Lower 8-bit of word logical shift right.
   ASR,     ///< Arithmetic shift right.
   ASRBN,   ///< Byte arithmetic shift right N bits.
   ASRWN,   ///< Word arithmetic shift right N bits.
+  ASRLO,   ///< Lower 8-bit of word arithmetic shift right.
   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 (4 <= ShiftAmount && ShiftAmount < 8)
         break;
       }
     else if (8 <= ShiftAmount && ShiftAmount < 12)
       switch (Op.getOpcode()) {
       case ISD::SHL:
         Victim = DAG.getNode(AVRISD::LSLWN, dl, VT, Victim,
                              DAG.getConstant(8, dl, VT));
         ShiftAmount -= 8;
+        // Only operate on the higher byte for remaining shift bits.
+        Opc8 = AVRISD::LSLHI;
         break;
       case ISD::SRL:
         Victim = DAG.getNode(AVRISD::LSRWN, dl, VT, Victim,
                              DAG.getConstant(8, dl, VT));
         ShiftAmount -= 8;
+        // Only operate on the lower byte for remaining shift bits.
+        Opc8 = AVRISD::LSRLO;
         break;
       case ISD::SRA:
         Victim = DAG.getNode(AVRISD::ASRWN, dl, VT, Victim,
                              DAG.getConstant(8, dl, VT));
         ShiftAmount -= 8;
+        // Only operate on the lower byte for remaining shift bits.
+        Opc8 = AVRISD::ASRLO;
         break;
       default:
         break;
       }
     else if (12 <= ShiftAmount)
       switch (Op.getOpcode()) {
       case ISD::SHL:
         Victim = DAG.getNode(AVRISD::LSLWN, dl, VT, Victim,
                              DAG.getConstant(12, dl, VT));
         ShiftAmount -= 12;
+        // Only operate on the higher byte for remaining shift bits.
+        Opc8 = AVRISD::LSLHI;
         break;
       case ISD::SRL:
         Victim = DAG.getNode(AVRISD::LSRWN, dl, VT, Victim,
                              DAG.getConstant(12, dl, VT));
         ShiftAmount -= 12;
+        // Only operate on the lower byte for remaining shift bits.
+        Opc8 = AVRISD::LSRLO;
+        break;
+      case ISD::SRA:
+        Victim = DAG.getNode(AVRISD::ASRWN, dl, VT, Victim,
+                             DAG.getConstant(8, dl, VT));
+        ShiftAmount -= 8;
+        // Only operate on the lower byte for remaining shift bits.
+        Opc8 = AVRISD::ASRLO;
         break;
       default:
         break;
       }
   }
 
   while (ShiftAmount--) {
     Victim = DAG.getNode(Opc8, dl, VT, 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 AVRlslhi : SDNode<"AVRISD::LSLHI", SDTIntUnaryOp>;
+def AVRlsrlo : SDNode<"AVRISD::LSRLO", SDTIntUnaryOp>;
+def AVRasrlo : SDNode<"AVRISD::ASRLO", SDTIntUnaryOp>;
 def AVRlslbn : SDNode<"AVRISD::LSLBN", SDTIntBinOp>;
 def AVRlsrbn : SDNode<"AVRISD::LSRBN", SDTIntBinOp>;
 def AVRasrbn : SDNode<"AVRISD::ASRBN", SDTIntBinOp>;
 def AVRlslwn : SDNode<"AVRISD::LSLWN", SDTIntBinOp>;
 def AVRlsrwn : SDNode<"AVRISD::LSRWN", SDTIntBinOp>;
 def AVRasrwn : SDNode<"AVRISD::ASRWN", SDTIntBinOp>;
 
 // Pseudo shift nodes for non-constant shift amounts.
def LSLWRd : Pseudo<(outs DREGS
                       (ins DREGS
                        : $src),
                       "lslw\t$rd",
                       [(set i16
                         : $rd, (AVRlsl i16
                                 : $src)),
                        (implicit SREG)]>;
 
+  def LSLWHiRd : Pseudo<(outs DREGS:$rd), (ins DREGS:$src), "lslwhi\t$rd",
+                        [(set i16:$rd, (AVRlslhi i16:$src)), (implicit SREG)]>;
+
   def LSLWNRd : Pseudo<(outs DLDREGS
                         : $rd),
                        (ins DREGS
                         : $src, imm16
                         : $bits),
                        "lslwn\t$rd, $bits", [
                          (set i16
                           : $rd, (AVRlslwn i16
def LSRWRd : Pseudo<(outs DREGS
                       (ins DREGS
                        : $src),
                       "lsrw\t$rd",
                       [(set i16
                         : $rd, (AVRlsr i16
                                 : $src)),
                        (implicit SREG)]>;
 
+  def LSRWLoRd : Pseudo<(outs DREGS:$rd), (ins DREGS:$src), "lsrwlo\t$rd",
+                        [(set i16:$rd, (AVRlsrlo i16:$src)), (implicit SREG)]>;
+
   def LSRWNRd : Pseudo<(outs DLDREGS
                         : $rd),
                        (ins DREGS
                         : $src, imm16
                         : $bits),
                        "lsrwn\t$rd, $bits", [
                          (set i16
                           : $rd, (AVRlsrwn i16
def ASRWRd : Pseudo<(outs DREGS
                       (ins DREGS
                        : $src),
                       "asrw\t$rd",
                       [(set i16
                         : $rd, (AVRasr i16
                                 : $src)),
                        (implicit SREG)]>;
 
+  def ASRWLoRd : Pseudo<(outs DREGS:$rd), (ins DREGS:$src), "asrwlo\t$rd",
+                        [(set i16:$rd, (AVRasrlo i16:$src)), (implicit SREG)]>;
+
   def ROLBRd : Pseudo<(outs GPR8
                        : $rd),
                       (ins GPR8
                        : $src),
                       "rolb\t$rd",
                       [(set i8
                         : $rd, (AVRrol i8
                                 : $src)),

llvm/test/CodeGen/AVR/shift.ll

; CHECK-NEXT:  ret
   %result = shl i16 %f, 6
   ret i16 %result
 }
 
 define i16 @lsl_i16_9(i16 %a) {
 ; CHECK-LABEL: lsl_i16_9
 ; CHECK:       mov r25, r24
 ; CHECK-NEXT:  clr r24
-; CHECK-NEXT:  lsl r24
-; CHECK-NEXT:  rol r25
+; CHECK-NEXT:  lsl r25
 ; CHECK-NEXT:  ret
   %result = shl i16 %a, 9
   ret i16 %result
 }
 
 define i16 @lsl_i16_13(i16 %a) {
 ; CHECK-LABEL: lsl_i16_13
 ; CHECK:       mov r25, r24
 ; CHECK-NEXT:  swap r25
 ; CHECK-NEXT:  andi r25, 240
 ; CHECK-NEXT:  clr r24
-; CHECK-NEXT:  lsl r24
-; CHECK-NEXT:  rol r25
+; CHECK-NEXT:  lsl r25
 ; CHECK-NEXT:  ret
   %result = shl i16 %a, 13
   ret i16 %result
 }
 
 define i16 @lsr_i16_5(i16 %a) {
 ; CHECK-LABEL: lsr_i16_5
 ; CHECK:       swap r25
; CHECK-NEXT: ret
   %result = lshr i16 %f, 6
   ret i16 %result
 }
 
 define i16 @lsr_i16_9(i16 %a) {
 ; CHECK-LABEL: lsr_i16_9
 ; CHECK:       mov r24, r25
 ; CHECK-NEXT:  clr r25
-; CHECK-NEXT:  lsr r25
-; CHECK-NEXT:  ror r24
+; CHECK-NEXT:  lsr r24
 ; CHECK-NEXT:  ret
   %result = lshr i16 %a, 9
   ret i16 %result
 }
 
 define i16 @lsr_i16_13(i16 %a) {
 ; CHECK-LABEL: lsr_i16_13
 ; CHECK:       mov r24, r25
 ; CHECK-NEXT:  swap r24
 ; CHECK-NEXT:  andi r24, 15
 ; CHECK-NEXT:  clr r25
-; CHECK-NEXT:  lsr r25
-; CHECK-NEXT:  ror r24
+; CHECK-NEXT:  lsr r24
 ; CHECK-NEXT:  ret
   %result = lshr i16 %a, 13
   ret i16 %result
 }
 
 define i16 @asr_i16_9(i16 %a) {
 ; CHECK-LABEL: asr_i16_9
 ; CHECK:       mov r24, r25
 ; CHECK-NEXT:  lsl r25
 ; CHECK-NEXT:  sbc r25, r25
-; CHECK-NEXT:  asr r25
-; CHECK-NEXT:  ror r24
+; CHECK-NEXT:  asr r24
 ; CHECK-NEXT:  ret
   %result = ashr i16 %a, 9
   ret i16 %result
 }
+
+define i16 @asr_i16_12(i16 %a) {
+; CHECK-LABEL: asr_i16_12
+; CHECK:       mov r24, r25
+; CHECK-NEXT:  lsl r25
+; CHECK-NEXT:  sbc r25, r25
+; CHECK-NEXT:  asr r24
+; CHECK-NEXT:  asr r24
+; CHECK-NEXT:  asr r24
+; CHECK-NEXT:  asr r24
+; CHECK-NEXT:  ret
+  %result = ashr i16 %a, 12
+  ret i16 %result
+}