[AVR] Optimize 16-bit int shift

[benshi001]

Summary

Logic left and right shifts get improved with shift amount 4 ~ 15.
Arithmetic right shift gets improved with shift amount 8-15.

[aykevl]

See my comment D89047#2366709.
I think this optimization would be implemented better in SelectionDAG instead of using pseudo-instructions. That would also make it possible to optimize things like (short)x << 12.

[benshi001]

In D90092#2366711, @aykevl wrote:

See my comment D89047#2366709.
I think this optimization would be implemented better in SelectionDAG instead of using pseudo-instructions. That would also make it possible to optimize things like (short)x << 12.

Thanks. I would try to improve my patch by

1. introducing AVRISD:LSL4/SLR4/ASR4/LSL12/SLR12/ASR12,
2. avoid using pseudo instructions.

The above ways can optimize most cases, except for shiftAmount = 3 and shiftAmount = 15. However I would like to handle these corner cases in another patch.

[benshi001]

In D90092#2366711, @aykevl wrote:

See my comment D89047#2366709.
I think this optimization would be implemented better in SelectionDAG instead of using pseudo-instructions. That would also make it possible to optimize things like (short)x << 12.

Could you please explain more about be implemented better in SelectionDAG instead of using pseudo-instructions ? I can not figure out a way using SelectionDAG. Because I think SelectionDAG requires data flow dependency and looks like a tree structure. But The mov/clr pair seems can not be put into a tree structure.

[benshi001]

Logic left and right shifts get improved with shift amount 4 ~ 15.
Arithmetic right shift gets improved with shift amount 8-15.

Though they are not in the best form as avr-gcc generates, current llvm code gets big improvement against itself.

I will continue to optimize 16-bit int shifts in future patches.

[benshi001]

ping

[dylanmckay]

Looks good to me. Indeed, it is sad this could not be implemented at a higher level but even as is it is a great optimization.

Thanks for the patch!

[aykevl]

I've been testing the llvm main branch and I found that this change introduces a miscompilation. I have not yet investigated what exactly is going wrong.

[aykevl]

I found at least one code sample that is miscompiled.

Code:

unsigned lsl(int a, int b, int c, int d, int e, int n) {
    return n << 4;
}

Compiles to:

lsl:                                    ; @lsl
        push    r14
        push    r15
        swap    r15
        swap    r14
        andi    r15, 240
        eor     r15, r14
        andi    r14, 240
        eor     r15, r14
        movw    r24, r14
        pop     r15
        pop     r14
        ret

However, andi r15, 240 is not valid. According to the ISA specification, the register operand of andi must be in the range r16-r31.

Compiler Explorer: https://godbolt.org/z/qb9PWP

[benshi001]

Thanks for reporting. I have submited a patch to fix that bug.
https://reviews.llvm.org/D96590

You are appreciated to review it.

In D90092#2557835, @aykevl wrote:

I found at least one code sample that is miscompiled.

Code:

unsigned lsl(int a, int b, int c, int d, int e, int n) {
    return n << 4;
}

Compiles to:

lsl:                                    ; @lsl
        push    r14
        push    r15
        swap    r15
        swap    r14
        andi    r15, 240
        eor     r15, r14
        andi    r14, 240
        eor     r15, r14
        movw    r24, r14
        pop     r15
        pop     r14
        ret

However, andi r15, 240 is not valid. According to the ISA specification, the register operand of andi must be in the range r16-r31.

Compiler Explorer: https://godbolt.org/z/qb9PWP

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::LSLW4Rd>(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);
+
+  // swap Rh
+  // swap Rl
+  buildMI(MBB, MBBI, AVR::SWAPRd)
+      .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstHiReg, getKillRegState(DstIsKill));
+  buildMI(MBB, MBBI, AVR::SWAPRd)
+      .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstLoReg, getKillRegState(DstIsKill));
+
+  // andi Rh, 0xf0
+  auto MI0 =
+      buildMI(MBB, MBBI, AVR::ANDIRdK)
+          .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstHiReg, getKillRegState(DstIsKill))
+          .addImm(0xf0);
+  // SREG is implicitly dead.
+  MI0->getOperand(3).setIsDead();
+
+  // eor Rh, Rl
+  auto MI1 =
+      buildMI(MBB, MBBI, AVR::EORRdRr)
+          .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstHiReg, getKillRegState(DstIsKill))
+          .addReg(DstLoReg, getKillRegState(DstIsKill));
+  // SREG is implicitly dead.
+  MI1->getOperand(3).setIsDead();
+
+  // andi Rl, 0xf0
+  auto MI2 =
+      buildMI(MBB, MBBI, AVR::ANDIRdK)
+          .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstLoReg, getKillRegState(DstIsKill))
+          .addImm(0xf0);
+  // SREG is implicitly dead.
+  MI2->getOperand(3).setIsDead();
+
+  // eor Rh, Rl
+  auto MI3 =
+      buildMI(MBB, MBBI, AVR::EORRdRr)
+          .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstHiReg, getKillRegState(DstIsKill))
+          .addReg(DstLoReg, getKillRegState(DstIsKill));
+  if (ImpIsDead)
+    MI3->getOperand(3).setIsDead();
+
+  MI.eraseFromParent();
+  return true;
+}
+
+template <>
+bool AVRExpandPseudo::expand<AVR::LSLW8Rd>(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);
+
+  // mov Rh, Rl
+  buildMI(MBB, MBBI, AVR::MOVRdRr)
+      .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstLoReg, getKillRegState(DstIsKill));
+
+  // clr Rl
+  auto MIBLO =
+      buildMI(MBB, MBBI, AVR::EORRdRr)
+          .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstLoReg, getKillRegState(DstIsKill))
+          .addReg(DstLoReg, getKillRegState(DstIsKill));
+  if (ImpIsDead)
+    MIBLO->getOperand(3).setIsDead();
+
+  MI.eraseFromParent();
+  return true;
+}
+
+template <>
+bool AVRExpandPseudo::expand<AVR::LSLW12Rd>(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);
+
+  // mov Rh, Rl
+  buildMI(MBB, MBBI, AVR::MOVRdRr)
+      .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstLoReg, getKillRegState(DstIsKill));
+
+  // swap Rh
+  buildMI(MBB, MBBI, AVR::SWAPRd)
+      .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstHiReg, getKillRegState(DstIsKill));
+
+  // andi Rh, 0xf0
+  auto MI0 =
+      buildMI(MBB, MBBI, AVR::ANDIRdK)
+          .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstHiReg, getKillRegState(DstIsKill))
+          .addImm(0xf0);
+  // SREG is implicitly dead.
+  MI0->getOperand(3).setIsDead();
+
+  // clr Rl
+  auto MI1 =
+      buildMI(MBB, MBBI, AVR::EORRdRr)
+          .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstLoReg, getKillRegState(DstIsKill))
+          .addReg(DstLoReg, getKillRegState(DstIsKill));
+  if (ImpIsDead)
+    MI1->getOperand(3).setIsDead();
+
+  MI.eraseFromParent();
+  return true;
+}
+
+template <>
 bool AVRExpandPseudo::expand<AVR::LSRWRd>(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();
   unsigned OpLo = AVR::RORRd;
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::LSRW4Rd>(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);
+
+  // swap Rh
+  // swap Rl
+  buildMI(MBB, MBBI, AVR::SWAPRd)
+      .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstHiReg, getKillRegState(DstIsKill));
+  buildMI(MBB, MBBI, AVR::SWAPRd)
+      .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstLoReg, getKillRegState(DstIsKill));
+
+  // andi Rl, 0xf
+  auto MI0 =
+      buildMI(MBB, MBBI, AVR::ANDIRdK)
+          .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstLoReg, getKillRegState(DstIsKill))
+          .addImm(0xf);
+  // SREG is implicitly dead.
+  MI0->getOperand(3).setIsDead();
+
+  // eor Rl, Rh
+  auto MI1 =
+      buildMI(MBB, MBBI, AVR::EORRdRr)
+          .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstLoReg, getKillRegState(DstIsKill))
+          .addReg(DstHiReg, getKillRegState(DstIsKill));
+  // SREG is implicitly dead.
+  MI1->getOperand(3).setIsDead();
+
+  // andi Rh, 0xf
+  auto MI2 =
+      buildMI(MBB, MBBI, AVR::ANDIRdK)
+          .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstHiReg, getKillRegState(DstIsKill))
+          .addImm(0xf);
+  // SREG is implicitly dead.
+  MI2->getOperand(3).setIsDead();
+
+  // eor Rl, Rh
+  auto MI3 =
+      buildMI(MBB, MBBI, AVR::EORRdRr)
+          .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstLoReg, getKillRegState(DstIsKill))
+          .addReg(DstHiReg, getKillRegState(DstIsKill));
+  if (ImpIsDead)
+    MI3->getOperand(3).setIsDead();
+
+  MI.eraseFromParent();
+  return true;
+}
+
+template <>
+bool AVRExpandPseudo::expand<AVR::LSRW8Rd>(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);
+
+  // Move upper byte to lower byte.
+  buildMI(MBB, MBBI, AVR::MOVRdRr)
+      .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstHiReg);
+
+  // Clear upper byte.
+  auto MIBHI =
+      buildMI(MBB, MBBI, AVR::EORRdRr)
+          .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstHiReg, getKillRegState(DstIsKill))
+          .addReg(DstHiReg, getKillRegState(DstIsKill));
+  if (ImpIsDead)
+    MIBHI->getOperand(3).setIsDead();
+
+  MI.eraseFromParent();
+  return true;
+}
+
+template <>
+bool AVRExpandPseudo::expand<AVR::LSRW12Rd>(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);
+
+  // Move upper byte to lower byte.
+  buildMI(MBB, MBBI, AVR::MOVRdRr)
+      .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstHiReg);
+
+  // swap Rl
+  buildMI(MBB, MBBI, AVR::SWAPRd)
+      .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstLoReg, getKillRegState(DstIsKill));
+
+  // andi Rl, 0xf
+  auto MI0 =
+      buildMI(MBB, MBBI, AVR::ANDIRdK)
+          .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstLoReg, getKillRegState(DstIsKill))
+          .addImm(0xf);
+  // SREG is implicitly dead.
+  MI0->getOperand(3).setIsDead();
+
+  // Clear upper byte.
+  auto MIBHI =
+      buildMI(MBB, MBBI, AVR::EORRdRr)
+          .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstHiReg, getKillRegState(DstIsKill))
+          .addReg(DstHiReg, getKillRegState(DstIsKill));
+  if (ImpIsDead)
+    MIBHI->getOperand(3).setIsDead();
+
+  MI.eraseFromParent();
+  return true;
+}
+
+template <>
 bool AVRExpandPseudo::expand<AVR::RORWRd>(Block &MBB, BlockIt MBBI) {
   llvm_unreachable("RORW unimplemented");
   return false;
 }
 
 template <>
 bool AVRExpandPseudo::expand<AVR::ROLWRd>(Block &MBB, BlockIt MBBI) {
   llvm_unreachable("ROLW unimplemented");
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::ASRW8Rd>(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);
+
+  // Move upper byte to lower byte.
+  buildMI(MBB, MBBI, AVR::MOVRdRr)
+      .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstHiReg, getKillRegState(DstIsKill));
+
+  // Move the sign bit to the C flag.
+  buildMI(MBB, MBBI, AVR::ADDRdRr).addReg(DstHiReg)
+      .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstHiReg, getKillRegState(DstIsKill));
+
+  // Set upper byte to 0 or -1.
+  auto MIBHI =
+      buildMI(MBB, MBBI, AVR::SBCRdRr)
+          .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstHiReg, getKillRegState(DstIsKill))
+          .addReg(DstHiReg, getKillRegState(DstIsKill));
+  if (ImpIsDead)
+    MIBHI->getOperand(3).setIsDead();
+
+  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
case AVR::LDDWRdYQ: //:FIXME: remove this once PR13375 gets fixed
     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::LSLW4Rd);
+    EXPAND(AVR::LSLW8Rd);
+    EXPAND(AVR::LSLW12Rd);
     EXPAND(AVR::LSRWRd);
+    EXPAND(AVR::LSRW4Rd);
+    EXPAND(AVR::LSRW8Rd);
+    EXPAND(AVR::LSRW12Rd);
     EXPAND(AVR::RORWRd);
     EXPAND(AVR::ROLWRd);
     EXPAND(AVR::ASRWRd);
+    EXPAND(AVR::ASRW8Rd);
     EXPAND(AVR::LSLB7Rd);
     EXPAND(AVR::LSRB7Rd);
     EXPAND(AVR::ASRB7Rd);
     EXPAND(AVR::SEXT);
     EXPAND(AVR::ZEXT);
     EXPAND(AVR::SPREAD);
     EXPAND(AVR::SPWRITE);
   }

llvm/lib/Target/AVR/AVRISelLowering.h

enum NodeType {
   RETI_FLAG,
   /// Represents an abstract call instruction,
   /// which includes a bunch of information.
   CALL,
   /// A wrapper node for TargetConstantPool,
   /// TargetExternalSymbol, and TargetGlobalAddress.
   WRAPPER,
   LSL,     ///< Logical shift left.
+  LSL4,    ///< Logical shift left 4 bits.
+  LSL8,    ///< Logical shift left 8 bits.
+  LSL12,   ///< Logical shift left 12 bits.
   LSR,     ///< Logical shift right.
+  LSR4,    ///< Logical shift right 4 bits.
+  LSR8,    ///< Logical shift right 8 bits.
+  LSR12,   ///< Logical shift right 12 bits.
   ASR,     ///< Arithmetic shift right.
+  ASR8,    ///< Arithmetic shift right 8 bits.
   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.

llvm/lib/Target/AVR/AVRISelLowering.cpp

case ISD::SRL:
     break;
   case ISD::SHL:
     Opc8 = AVRISD::LSL;
     break;
   default:
     llvm_unreachable("Invalid shift opcode");
   }
 
-  // Optimize int8 shifts.
+  // Optimize int8/int16 shifts.
   if (VT.getSizeInBits() == 8) {
     if (Op.getOpcode() == ISD::SHL && 4 <= ShiftAmount && ShiftAmount < 7) {
       // Optimize LSL when 4 <= ShiftAmount <= 6.
       Victim = DAG.getNode(AVRISD::SWAP, dl, VT, Victim);
       Victim =
           DAG.getNode(ISD::AND, dl, VT, Victim, DAG.getConstant(0xf0, dl, VT));
       ShiftAmount -= 4;
     } else if (Op.getOpcode() == ISD::SRL && 4 <= ShiftAmount &&
if (Op.getOpcode() == ISD::SHL && 4 <= ShiftAmount && 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;
     }
+  } else if (VT.getSizeInBits() == 16) {
+    if (4 <= ShiftAmount && ShiftAmount < 8)
+      switch (Op.getOpcode()) {
+      case ISD::SHL:
+        Victim = DAG.getNode(AVRISD::LSL4, dl, VT, Victim);
+        ShiftAmount -= 4;
+        break;
+      case ISD::SRL:
+        Victim = DAG.getNode(AVRISD::LSR4, dl, VT, Victim);
+        ShiftAmount -= 4;
+        break;
+      default:
+        break;
+      }
+    else if (8 <= ShiftAmount && ShiftAmount < 12)
+      switch (Op.getOpcode()) {
+      case ISD::SHL:
+        Victim = DAG.getNode(AVRISD::LSL8, dl, VT, Victim);
+        ShiftAmount -= 8;
+        break;
+      case ISD::SRL:
+        Victim = DAG.getNode(AVRISD::LSR8, dl, VT, Victim);
+        ShiftAmount -= 8;
+        break;
+      case ISD::SRA:
+        Victim = DAG.getNode(AVRISD::ASR8, dl, VT, Victim);
+        ShiftAmount -= 8;
+        break;
+      default:
+        break;
+      }
+    else if (12 <= ShiftAmount)
+      switch (Op.getOpcode()) {
+      case ISD::SHL:
+        Victim = DAG.getNode(AVRISD::LSL12, dl, VT, Victim);
+        ShiftAmount -= 12;
+        break;
+      case ISD::SRL:
+        Victim = DAG.getNode(AVRISD::LSR12, dl, VT, Victim);
+        ShiftAmount -= 12;
+        break;
+      default:
+        break;
+      }
   }
 
   while (ShiftAmount--) {
     Victim = DAG.getNode(Opc8, dl, VT, Victim);
   }
 
   return Victim;
 }

llvm/lib/Target/AVR/AVRInstrInfo.td

def AVRbrcond : SDNode<"AVRISD::BRCOND", SDT_AVRBrcond,
                        [SDNPHasChain, SDNPInGlue]>;
 def AVRcmp : SDNode<"AVRISD::CMP", SDT_AVRCmp, [SDNPOutGlue]>;
 def AVRcmpc : SDNode<"AVRISD::CMPC", SDT_AVRCmp, [SDNPInGlue, SDNPOutGlue]>;
 def AVRtst : SDNode<"AVRISD::TST", SDT_AVRTst, [SDNPOutGlue]>;
 def AVRselectcc: SDNode<"AVRISD::SELECT_CC", SDT_AVRSelectCC, [SDNPInGlue]>;
 
 // Shift nodes.
 def AVRlsl : SDNode<"AVRISD::LSL", SDTIntUnaryOp>;
+def AVRlsl4 : SDNode<"AVRISD::LSL4", SDTIntUnaryOp>;
+def AVRlsl8 : SDNode<"AVRISD::LSL8", SDTIntUnaryOp>;
+def AVRlsl12 : SDNode<"AVRISD::LSL12", SDTIntUnaryOp>;
 def AVRlsr : SDNode<"AVRISD::LSR", SDTIntUnaryOp>;
+def AVRlsr4 : SDNode<"AVRISD::LSR4", SDTIntUnaryOp>;
+def AVRlsr8 : SDNode<"AVRISD::LSR8", SDTIntUnaryOp>;
+def AVRlsr12 : SDNode<"AVRISD::LSR12", SDTIntUnaryOp>;
 def AVRrol : SDNode<"AVRISD::ROL", SDTIntUnaryOp>;
 def AVRror : SDNode<"AVRISD::ROR", SDTIntUnaryOp>;
 def AVRasr : SDNode<"AVRISD::ASR", SDTIntUnaryOp>;
+def AVRasr8 : SDNode<"AVRISD::ASR8", 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 LSLWRd : Pseudo<(outs DREGS:$rd),
                       "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 LSLW4Rd : Pseudo<(outs DREGS:$rd),
+                       (ins DREGS:$src),
+                       "lslw4\t$rd",
+                       [(set i16:$rd, (AVRlsl4 i16:$src)), (implicit SREG)]>;
+
+  def LSLW8Rd : Pseudo<(outs DREGS:$rd),
+                       (ins DREGS:$src),
+                       "lslw8\t$rd",
+                       [(set i16:$rd, (AVRlsl8 i16:$src)), (implicit SREG)]>;
+
+  def LSLW12Rd : Pseudo<(outs DREGS:$rd),
+                       (ins DREGS:$src),
+                       "lslw12\t$rd",
+                       [(set i16:$rd, (AVRlsl12 i16:$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 LSRW4Rd : Pseudo<(outs DREGS:$rd),
+                       (ins DREGS:$src),
+                       "lsrw4\t$rd",
+                       [(set i16:$rd, (AVRlsr4 i16:$src)), (implicit SREG)]>;
+
+  def LSRW8Rd : Pseudo<(outs DREGS:$rd),
+                       (ins DREGS:$src),
+                       "lsrw8\t$rd",
+                       [(set i16:$rd, (AVRlsr8 i16:$src)), (implicit SREG)]>;
+
+  def LSRW12Rd : Pseudo<(outs DREGS:$rd),
+                       (ins DREGS:$src),
+                       "lsrw12\t$rd",
+                       [(set i16:$rd, (AVRlsr12 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)]>;
 
+  def ASRW8Rd : Pseudo<(outs DREGS:$rd),
+                       (ins DREGS:$src),
+                       "asrw8\t$rd",
+                       [(set i16:$rd, (AVRasr8 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",
def : Pat<(store i8:$src, (i16 (AVRWrapper tglobaladdr:$dst))),
           (STSKRr tglobaladdr:$dst, i8:$src)>;
 def : Pat<(store i16:$src, (i16 (AVRWrapper tglobaladdr:$dst))),
           (STSWKRr tglobaladdr:$dst, i16:$src)>;
 
 // BlockAddress
 def : Pat<(i16 (AVRWrapper tblockaddress:$dst)),
           (LDIWRdK tblockaddress:$dst)>;
 
-// hi-reg truncation : trunc(int16 >> 8)
-//:FIXME: i think it's better to emit an extract subreg node in the DAG than
-// all this mess once we get optimal shift code
-// lol... I think so, too. [@agnat]
-def : Pat<(i8 (trunc (AVRlsr (AVRlsr (AVRlsr (AVRlsr (AVRlsr (AVRlsr (AVRlsr
-                     (AVRlsr DREGS:$src)))))))))),
+def : Pat<(i8 (trunc (AVRlsr8 DREGS:$src))),
           (EXTRACT_SUBREG DREGS:$src, sub_hi)>;
 
 // :FIXME: DAGCombiner produces an shl node after legalization from these seq:
 // BR_JT -> (mul x, 2) -> (shl x, 1)
 def : Pat<(shl i16:$src1, (i8 1)),
           (LSLWRd i16:$src1)>;
 
 // Lowering of 'tst' node to 'TST' instruction.

llvm/test/CodeGen/AVR/shift.ll

 
 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
 }
+
+define i16 @lsl_i16_5(i16 %a) {
+; CHECK-LABEL: lsl_i16_5
+; CHECK:       swap r25
+; CHECK-NEXT:  swap r24
+; CHECK-NEXT:  andi r25, 240
+; CHECK-NEXT:  eor r25, r24
+; CHECK-NEXT:  andi r24, 240
+; CHECK-NEXT:  eor r25, r24
+; CHECK-NEXT:  lsl r24
+; CHECK-NEXT:  rol r25
+; CHECK-NEXT:  ret
+  %result = shl i16 %a, 5
+  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:  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:  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:  swap r24
+; CHECK-NEXT:  andi r24, 15
+; CHECK-NEXT:  eor r24, r25
+; CHECK-NEXT:  andi r25, 15
+; CHECK-NEXT:  eor r24, r25
+; CHECK-NEXT:  lsr r25
+; CHECK-NEXT:  ror r24
+; CHECK-NEXT:  ret
+  %result = lshr i16 %a, 5
+  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:  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:  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:  ret
+  %result = ashr i16 %a, 9
+  ret i16 %result
+}