[AVR] Optimize int16 airthmetic right shift for shift amount 7/14/15

[aykevl]

Can you please add some .mir tests? As an example, I have created one for ASRW7Rd and ASRW8Rd:

# RUN: llc -O0 -run-pass=avr-expand-pseudo %s -o - | FileCheck %s

--- |
  target triple = "avr--"
  define void @test() {
  entry:
    ret void
  }
...

---
name:            test
body: |
  bb.0.entry:
    liveins: $r15r14

    ; CHECK-LABEL: test

    ; CHECK:      $r14 = ADDRdRr $r14, $r14, implicit-def undef $sreg
    ; CHECK-NEXT: $r14 = MOVRdRr $r15
    ; CHECK-NEXT: $r14 = ADCRdRr $r14, $r14, implicit-def $sreg, implicit $sreg
    ; CHECK-NEXT: $r15 = SBCRdRr $r15, $r15, implicit-def $sreg, implicit killed $sreg
    $r15r14 = ASRWNRd $r15r14, 7, implicit-def $sreg

    ; CHECK:      $r14 = MOVRdRr $r15
    ; CHECK-NEXT: $r15 = ADDRdRr $r15, $r15, implicit-def $sreg
    ; CHECK-NEXT: $r15 = SBCRdRr $r15, $r15, implicit-def $sreg, implicit killed $sreg
    $r15r14 = ASRWNRd $r15r14, 8, implicit-def $sreg
...

Here you can easily see the register states (undef, dead, kill, etc).

Also, I have found that ASRWNRd has DLDREGS as the output register, but I think the whole range (DREGS) is supported? DLDREGS are only the upper wide register (R17r16 to r31r3). That's perhaps a missed optimization.

While running this test locally, I also found the following error which I haven't investigated yet but is probably due to an incorrect kill flag ($r20 = MOVRdRr killed $r21):

FAIL: LLVM :: CodeGen/AVR/sign-extension.ll (11 of 144)
******************** TEST 'LLVM :: CodeGen/AVR/sign-extension.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   llc -verify-machineinstrs -march=avr < /home/ayke/src/github.com/tinygo-org/tinygo/llvm-project.main/llvm/test/CodeGen/AVR/sign-extension.ll | /home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/FileCheck /home/ayke/src/github.com/tinygo-org/tinygo/llvm-project.main/llvm/test/CodeGen/AVR/sign-extension.ll
--
Exit Code: 2

Command Output (stderr):
--

# After AVR pseudo instruction expansion pass
# Machine code for function sign_extended_8_to_64: NoPHIs, TracksLiveness, NoVRegs, TiedOpsRewritten, TracksDebugUserValues
Function Live Ins: $r24

bb.0.entry-block:
  liveins: $r24
  $r18 = MOVRdRr $r24
  $r19 = MOVRdRr killed $r24
  $r19 = ADDRdRr $r19(tied-def 0), killed $r19, implicit-def $sreg
  $r19 = SBCRdRr killed $r19(tied-def 0), killed $r19, implicit-def dead $sreg, implicit killed $sreg
  $r20 = MOVRdRr $r18
  $r21 = MOVRdRr $r19
  $r21 = ADDRdRr killed $r21(tied-def 0), killed $r21, implicit-def undef $sreg
  $r21 = SBCRdRr killed $r21(tied-def 0), killed $r21, implicit-def dead $sreg, implicit killed $sreg
  $r20 = MOVRdRr killed $r21
  $r22 = MOVRdRr $r20
  $r23 = MOVRdRr $r21
  $r24 = MOVRdRr $r20
  $r25 = MOVRdRr $r21
  RET implicit $r19r18, implicit $r21r20, implicit killed $r23r22, implicit $r25r24, implicit $r1

# End machine code for function sign_extended_8_to_64.

*** Bad machine code: Using an undefined physical register ***
- function:    sign_extended_8_to_64
- basic block: %bb.0 entry-block (0x556ea4da46f0)
- instruction: $r23 = MOVRdRr $r21
- operand 1:   $r21

*** Bad machine code: Using an undefined physical register ***
- function:    sign_extended_8_to_64
- basic block: %bb.0 entry-block (0x556ea4da46f0)
- instruction: $r25 = MOVRdRr $r21
- operand 1:   $r21
LLVM ERROR: Found 2 machine code errors.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0.	Program arguments: llc -verify-machineinstrs -march=avr
1.	Running pass 'Function Pass Manager' on module '<stdin>'.
2.	Running pass 'Verify generated machine code' on function '@sign_extended_8_to_64'
 #0 0x0000556ea28279cf PrintStackTraceSignalHandler(void*) Signals.cpp:0:0
 #1 0x0000556ea282519e SignalHandler(int) Signals.cpp:0:0
 #2 0x00007ff051608730 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12730)
 #3 0x00007ff05113a7bb raise (/lib/x86_64-linux-gnu/libc.so.6+0x377bb)
 #4 0x00007ff051125535 abort (/lib/x86_64-linux-gnu/libc.so.6+0x22535)
 #5 0x0000556ea2768435 llvm::report_fatal_error(llvm::Twine const&, bool) (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x3f9c435)
 #6 0x0000556ea1b5f3e0 (anonymous namespace)::MachineVerifierPass::runOnMachineFunction(llvm::MachineFunction&) MachineVerifier.cpp:0:0
 #7 0x0000556ea1b5f40c (anonymous namespace)::MachineVerifierPass::runOnMachineFunction(llvm::MachineFunction&) MachineVerifier.cpp:0:0
 #8 0x0000556ea1a67420 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x329b420)
 #9 0x0000556ea1f215f0 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x37555f0)
#10 0x0000556ea1f21811 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x3755811)
#11 0x0000556ea1f222f5 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x37562f5)
#12 0x0000556ea0bac6bb compileModule(char**, llvm::LLVMContext&) llc.cpp:0:0
#13 0x0000556ea0bad69a main (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x23e169a)
#14 0x00007ff05112709b __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2409b)
#15 0x0000556ea0ba018a _start (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x23d418a)
FileCheck error: '<stdin>' is empty.
FileCheck command line:  /home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/FileCheck /home/ayke/src/github.com/tinygo-org/tinygo/llvm-project.main/llvm/test/CodeGen/AVR/sign-extension.ll

You can reproduce this with the following command:

llvm-build/bin/llc -verify-machineinstrs -march=avr < path/to/llvm/test/CodeGen/AVR/sign-extension.ll

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

1867

This register is always dead. It's overwritten (killed) by the mov instruction on the next line.

1868–1869

These two input operands are always killed: they are the last use of this input value.

1870–1871

You are setting the output operand SREG to undef? I don't think that's correct. AFAIK only input operands can be set to undef. Also, you are going to use the output of the SREG later, so I don't think it should be set to undef.

[aykevl]

(just so that this doesn't appear in my review queue anymore)

[benshi001]

In D115618#3248072, @aykevl wrote:

(just so that this doesn't appear in my review queue anymore)

Thanks for your suggestion. I have done

1. Add a new MIR test to show register state changes.
2. Corrent wrong register state when expanding the ASRW7/ASRW14/ASRW15 pseudo instructions.
3. Add -verify-machineinstrs option to the /llvm/test/CodeGen/AVR/sign-extension.ll
4. Change the register class of ASRWNRd from DLDREGS to DREGS.

[aykevl]

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

1872

You could use the following instead, which is a bit shorter (but has the same effect):

buildMI(MBB, MBBI, AVR::MOVRdRr, DstLoReg)
  .addReg(DstHiReg);

(The same change can be applied in other places in this patch).

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

private:
   template <typename Func>
   bool expandAtomicBinaryOp(unsigned Opcode, Block &MBB, BlockIt MBBI, Func f);
 
   bool expandAtomicBinaryOp(unsigned Opcode, Block &MBB, BlockIt MBBI);
 
   bool expandAtomicArithmeticOp(unsigned MemOpcode, unsigned ArithOpcode,
                                 Block &MBB, BlockIt MBBI);
 
-  /// Specific shift implementation.
+  /// Specific shift implementation for int8.
   bool expandLSLB7Rd(Block &MBB, BlockIt MBBI);
   bool expandLSRB7Rd(Block &MBB, BlockIt MBBI);
   bool expandASRB7Rd(Block &MBB, BlockIt MBBI);
+
+  /// Specific shift implementation for int16.
   bool expandLSLW4Rd(Block &MBB, BlockIt MBBI);
   bool expandLSRW4Rd(Block &MBB, BlockIt MBBI);
+  bool expandASRW7Rd(Block &MBB, BlockIt MBBI);
   bool expandLSLW8Rd(Block &MBB, BlockIt MBBI);
   bool expandLSRW8Rd(Block &MBB, BlockIt MBBI);
   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);
 
   /// Scavenges a free GPR8 register for use.
   Register scavengeGPR8(MachineInstr &MI);
 };
 
 char AVRExpandPseudo::ID = 0;
 
 bool AVRExpandPseudo::expandMBB(MachineBasicBlock &MBB) {
bool AVRExpandPseudo::expand<AVR::ASRWLoRd>(Block &MBB, BlockIt MBBI) {
 
   if (ImpIsDead)
     MIASR->getOperand(2).setIsDead();
 
   MI.eraseFromParent();
   return true;
 }
 
+bool AVRExpandPseudo::expandASRW7Rd(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);
+
+  // lsl r24
+  // mov r24,r25
+  // rol r24
+  // sbc r25,r25
+
+  // lsl r24 <=> add r24, r24
+  buildMI(MBB, MBBI, AVR::ADDRdRr)
+      .addReg(DstLoReg, RegState::Define, getDeadRegState(DstIsDead))
+      .addReg(DstLoReg, getKillRegState(DstIsKill))
+      .addReg(DstLoReg, getKillRegState(DstIsKill))
+      ->getOperand(3)
+      .setIsUndef(true);
+
+  // mov r24, r25
+  buildMI(MBB, MBBI, AVR::MOVRdRr)
+      .addReg(DstLoReg, RegState::Define, getDeadRegState(DstIsDead))
+      .addReg(DstHiReg, getKillRegState(DstIsKill));
+
+  // rol r24 <=> adc r24, r24
+  buildMI(MBB, MBBI, AVR::ADCRdRr)
+      .addReg(DstLoReg, RegState::Define, getDeadRegState(DstIsDead))
+      .addReg(DstLoReg, getKillRegState(DstIsKill))
+      .addReg(DstLoReg, getKillRegState(DstIsKill));
+
+  // sbc r25, r25
+  auto MISBC =
+      buildMI(MBB, MBBI, AVR::SBCRdRr)
+          .addReg(DstHiReg, RegState::Define, getDeadRegState(DstIsDead))
+          .addReg(DstHiReg, getKillRegState(DstIsKill))
+          .addReg(DstHiReg, getKillRegState(DstIsKill));
+
+  if (ImpIsDead)
+    MISBC->getOperand(3).setIsDead();
+
+  // SREG is always implicitly killed
+  MISBC->getOperand(4).setIsKill();
+
+  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);
bool AVRExpandPseudo::expandASRW8Rd(Block &MBB, BlockIt MBBI) {
   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();
 
+  // SREG is always implicitly killed
+  MIBHI->getOperand(4).setIsKill();
+
+  MI.eraseFromParent();
+  return true;
+}
+
+bool AVRExpandPseudo::expandASRW14Rd(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);
+
+  // lsl r25
+  // sbc r24, r24
+  // lsl r25
+  // mov r25, r24
+  // rol r24
+
+  // lsl r25 <=> add r25, r25
+  buildMI(MBB, MBBI, AVR::ADDRdRr)
+      .addReg(DstHiReg, RegState::Define, getDeadRegState(DstIsDead))
+      .addReg(DstHiReg, getKillRegState(DstIsKill))
+      .addReg(DstHiReg, getKillRegState(DstIsKill))
+      ->getOperand(3)
+      .setIsUndef(true);
+
+  // sbc r24, r24
+  buildMI(MBB, MBBI, AVR::SBCRdRr)
+      .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
+      .addReg(DstLoReg, getKillRegState(DstIsKill))
+      .addReg(DstLoReg, getKillRegState(DstIsKill));
+
+  // lsl r25 <=> add r25, r25
+  buildMI(MBB, MBBI, AVR::ADDRdRr)
+      .addReg(DstHiReg, RegState::Define, getDeadRegState(DstIsDead))
+      .addReg(DstHiReg, getKillRegState(DstIsKill))
+      .addReg(DstHiReg, getKillRegState(DstIsKill));
+
+  // mov r25, r24
+  buildMI(MBB, MBBI, AVR::MOVRdRr)
+      .addReg(DstHiReg, RegState::Define, getDeadRegState(DstIsDead))
+      .addReg(DstLoReg, getKillRegState(DstIsKill));
+
+  // rol r24 <=> adc r24, r24
+  auto MIROL =
+      buildMI(MBB, MBBI, AVR::ADCRdRr)
+          .addReg(DstLoReg, RegState::Define, getDeadRegState(DstIsDead))
+          .addReg(DstLoReg, getKillRegState(DstIsKill))
+          .addReg(DstLoReg, getKillRegState(DstIsKill));
+
+  if (ImpIsDead)
+    MIROL->getOperand(3).setIsDead();
+
+  // SREG is always implicitly killed
+  MIROL->getOperand(4).setIsKill();
+
+  MI.eraseFromParent();
+  return false;
+}
+
+bool AVRExpandPseudo::expandASRW15Rd(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);
+
+  // lsl r25
+  // sbc r25, r25
+  // mov r24, r25
+
+  // lsl r25 <=> add r25, r25
+  buildMI(MBB, MBBI, AVR::ADDRdRr)
+      .addReg(DstHiReg, RegState::Define, getDeadRegState(DstIsDead))
+      .addReg(DstHiReg, getKillRegState(DstIsKill))
+      .addReg(DstHiReg, getKillRegState(DstIsKill))
+      ->getOperand(3)
+      .setIsUndef(true);
+
+  // sbc r25, r25
+  auto MISBC =
+      buildMI(MBB, MBBI, AVR::SBCRdRr)
+          .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
+          .addReg(DstHiReg, getKillRegState(DstIsKill))
+          .addReg(DstHiReg, getKillRegState(DstIsKill));
+  if (ImpIsDead)
+    MISBC->getOperand(3).setIsDead();
+  // SREG is always implicitly killed
+  MISBC->getOperand(4).setIsKill();
+
+  // mov r24, r25
+  buildMI(MBB, MBBI, AVR::MOVRdRr)
+      .addReg(DstLoReg, RegState::Define, getDeadRegState(DstIsDead))
+      .addReg(DstHiReg, getKillRegState(DstIsKill));
+
   MI.eraseFromParent();
   return true;
 }
 
 template <>
 bool AVRExpandPseudo::expand<AVR::ASRWNRd>(Block &MBB, BlockIt MBBI) {
   MachineInstr &MI = *MBBI;
   unsigned Imm = MI.getOperand(2).getImm();
   switch (Imm) {
+  case 7:
+    return expandASRW7Rd(MBB, MBBI);
   case 8:
     return expandASRW8Rd(MBB, MBBI);
+  case 14:
+    return expandASRW14Rd(MBB, MBBI);
+  case 15:
+    return expandASRW15Rd(MBB, MBBI);
   default:
     llvm_unreachable("unimplemented asrwn");
     return false;
   }
 }
 
 bool AVRExpandPseudo::expandLSLB7Rd(Block &MBB, BlockIt MBBI) {
   MachineInstr &MI = *MBBI;

llvm/lib/Target/AVR/AVRISelLowering.cpp

if (Op.getOpcode() == ISD::SHL && 4 <= ShiftAmount && ShiftAmount < 7) {
       ShiftAmount = 0;
     } else if (Op.getOpcode() == ISD::SRA && ShiftAmount == 7) {
       // Optimize ASR when ShiftAmount == 7.
       Victim = DAG.getNode(AVRISD::ASRBN, dl, VT, Victim,
                            DAG.getConstant(7, dl, VT));
       ShiftAmount = 0;
     }
   } else if (VT.getSizeInBits() == 16) {
+    if (Op.getOpcode() == ISD::SRA)
+      // Special optimization for int16 arithmetic right shift.
+      switch (ShiftAmount) {
+      case 15:
+        Victim = DAG.getNode(AVRISD::ASRWN, dl, VT, Victim,
+                             DAG.getConstant(15, dl, VT));
+        ShiftAmount = 0;
+        break;
+      case 14:
+        Victim = DAG.getNode(AVRISD::ASRWN, dl, VT, Victim,
+                             DAG.getConstant(14, dl, VT));
+        ShiftAmount = 0;
+        break;
+      case 7:
+        Victim = DAG.getNode(AVRISD::ASRWN, dl, VT, Victim,
+                             DAG.getConstant(7, dl, VT));
+        ShiftAmount = 0;
+        break;
+      default:
+        break;
+      }
     if (4 <= ShiftAmount && ShiftAmount < 8)
       switch (Op.getOpcode()) {
       case ISD::SHL:
         Victim = DAG.getNode(AVRISD::LSLWN, dl, VT, Victim,
                              DAG.getConstant(4, dl, VT));
         ShiftAmount -= 4;
         break;
       case ISD::SRL:

llvm/test/CodeGen/AVR/shift.ll

 ; CHECK-NEXT:  andi r24, 15
 ; CHECK-NEXT:  clr r25
 ; CHECK-NEXT:  lsr r24
 ; CHECK-NEXT:  ret
   %result = lshr i16 %a, 13
   ret i16 %result
 }
 
+define i16 @asr_i16_7(i16 %a) {
+; CHECK-LABEL: asr_i16_7
+; CHECK:       lsl r24
+; CHECK-NEXT:  mov r24, r25
+; CHECK-NEXT:  rol r24
+; CHECK-NEXT:  sbc r25, r25
+; CHECK-NEXT:  ret
+  %result = ashr i16 %a, 7
+  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 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
 }
+
+define i16 @asr_i16_14(i16 %a) {
+; CHECK-LABEL: asr_i16_14
+; CHECK:      lsl r25
+; CHECK-NEXT: sbc r24, r24
+; CHECK-NEXT: lsl r25
+; CHECK-NEXT: mov r25, r24
+; CHECK-NEXT: rol r24
+; CHECK-NEXT: ret
+  %result = ashr i16 %a, 14
+  ret i16 %result
+}
+
+define i16 @asr_i16_15(i16 %a) {
+; CHECK-LABEL: asr_i16_15
+; CHECK:      lsl r25
+; CHECK-NEXT: sbc r25, r25
+; CHECK-NEXT: mov r24, r25
+; CHECK-NEXT: ret
+  %result = ashr i16 %a, 15
+  ret i16 %result
+}