[AVR] Support left-rotations

[Patryk27]

Summary

Currently, trying to compile this code:

define i8 @test(i8 %0) {
start:
  %1 = call i8 @llvm.fshl.i8(i8 %0, i8 %0, i8 1)
  ret i8 %1
}

declare i8 @llvm.fshl.i8(i8, i8, i8)

./build/bin/llc -march=avr -mcpu=atmega32u4 test.ll

... will fail, saying:

LLVM ERROR: Cannot select: t9: i8 = ROL t2
  t2: i8,ch = CopyFromReg t0, Register:i8 %0
    t1: i8 = Register %0

(spotted in the wild at https://github.com/rust-lang/rust/issues/107261)

Curiously, fshl.u16 (and larger types) work, similarly as all fshrs,
which I think is related to the fact that ROLBRd is hard-coded to
require GPR8:$zero in AVRInstrInfo.td.

Now, I'm not really sure why it's been done this way and so I'm not 100%
sure my approach to solving this problem is correct as well - but
adjusting ROLBRd to work similarly as RORBRd seems to do the job.

Following the example from above, we now generate:

lsl r24
adc r24, r1

I've made sure the codegen is alright by cross-checking results using
simavr - I've checked following cases, having lhs as a variable:

• 8-bit left/right rotations where rhs is constant/variable,
• 16-bit left/right rotations where rhs is constant/variable,
• 32-bit left/right rotations where rhs is constant/variable,

... and they all yielded correct results when compared with Rust's
.rotate_left() and .rotate_right().

[benshi001]

Thanks. Could you please change your commit message to

[AVR] Fix incorrect operands of pseudo instruction 'ROLBRd'

Fixes https://github.com/llvm/llvm-project/issues/63098

This is the recommended form when committing to LLVM's repo.

[Patryk27]

I see you've already changed the commit message, so nothing more to do here, right? 🙂

[benshi001]

In D152063#4393727, @Patryk27 wrote:

I see you've already changed the commit message, so nothing more to do here, right? 🙂

Sure. Thanks!

[aykevl]

Sorry I only see this now, after it has been merged.

Curiously, fshl.u16 (and larger types) work, similarly as all fshrs, which I think is related to the fact that ROLBRd is hard-coded to require GPR8:$zero in AVRInstrInfo.td.

Now, I'm not really sure why it's been done this way and so I'm not 100% sure my approach to solving this problem is correct as well - but adjusting ROLBRd to work similarly as RORBRd seems to do the job.

There is a reason, namely that the instruction uses R1 and now doesn't say so in InstrInfo. I have added the use of R1 in D117426. With the use removed, interrupts may be miscompiled because R1 might not be saved/cleared/restored inside an interrupt when a ROLB pseudo instruction is used inside an interrupt.

In other words, the zero register dependency is required for correctness and this patch will lead to miscompilation in some edge cases.

Here is an example that miscompiles on current trunk: https://godbolt.org/z/6ha5rGqY3 (r1 is used but not saved/cleared).

llvm/test/CodeGen/AVR/pseudo/ROLBrd.mir

24–28

Why did you remove this test? I think it's useful (r1 vs r17).

[benshi001]

In D152063#4395330, @aykevl wrote:

Sorry I only see this now, after it has been merged.

Curiously, fshl.u16 (and larger types) work, similarly as all fshrs, which I think is related to the fact that ROLBRd is hard-coded to require GPR8:$zero in AVRInstrInfo.td.

Now, I'm not really sure why it's been done this way and so I'm not 100% sure my approach to solving this problem is correct as well - but adjusting ROLBRd to work similarly as RORBRd seems to do the job.

There is a reason, namely that the instruction uses R1 and now doesn't say so in InstrInfo. I have added the use of R1 in D117426. With the use removed, interrupts may be miscompiled because R1 might not be saved/cleared/restored inside an interrupt when a ROLB pseudo instruction is used inside an interrupt.

In other words, the zero register dependency is required for correctness and this patch will lead to miscompilation in some edge cases.

Here is an example that miscompiles on current trunk: https://godbolt.org/z/6ha5rGqY3 (r1 is used but not saved/cleared).

I have

1. made a fix, though inefficient, but correct
2. recover the test of avr-tiny.

I may need more time to find a proper fix to resolve both the crash and the incorrect generated ISR, but at least this solution is correct.

[benshi001]

In D152063#4395330, @aykevl wrote:

Sorry I only see this now, after it has been merged.

Curiously, fshl.u16 (and larger types) work, similarly as all fshrs, which I think is related to the fact that ROLBRd is hard-coded to require GPR8:$zero in AVRInstrInfo.td.

Now, I'm not really sure why it's been done this way and so I'm not 100% sure my approach to solving this problem is correct as well - but adjusting ROLBRd to work similarly as RORBRd seems to do the job.

There is a reason, namely that the instruction uses R1 and now doesn't say so in InstrInfo. I have added the use of R1 in D117426. With the use removed, interrupts may be miscompiled because R1 might not be saved/cleared/restored inside an interrupt when a ROLB pseudo instruction is used inside an interrupt.

In other words, the zero register dependency is required for correctness and this patch will lead to miscompilation in some edge cases.

Here is an example that miscompiles on current trunk: https://godbolt.org/z/6ha5rGqY3 (r1 is used but not saved/cleared).

Sorry I should merge it so quickly, at least wait for your review.

[Patryk27]

llvm/test/CodeGen/AVR/pseudo/ROLBrd.mir

24–28

I removed the second assertion since the zero-register is not an input for that instruction anymore - I guess using two-pass test with --check-prefix (once for r1 and once for r17) would be nice here, though

[aykevl]

In D152063#4398684, @benshi001 wrote:

Sorry I should merge it so quickly, at least wait for your review.

Don't worry - I haven't been very active lately on the AVR backend.
I have better organized my email now which is one reason why I am more likely to see these notifications. Maybe I'll get into AVR stuff again at some point - there are still a number of optimizations that I'd like to do :)

llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp

 //===-- AVRExpandPseudoInsts.cpp - Expand pseudo instructions -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 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.
 
+  const AVRSubtarget &STI = MBB.getParent()->getSubtarget<AVRSubtarget>();
+
   MachineInstr &MI = *MBBI;
   unsigned OpShift, OpCarry;
   Register DstReg = MI.getOperand(0).getReg();
-  Register ZeroReg = MI.getOperand(2).getReg();
+  Register ZeroReg = STI.getZeroRegister();
   bool DstIsDead = MI.getOperand(0).isDead();
   bool DstIsKill = MI.getOperand(1).isKill();
   OpShift = AVR::ADDRdRr;
   OpCarry = AVR::ADCRdRr;
 
   // add r16, r16
   // adc r16, r1
 

llvm/lib/Target/AVR/AVRISelLowering.cpp

 //===-- AVRISelLowering.cpp - AVR DAG Lowering Implementation -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 //  Custom Inserters
 //===----------------------------------------------------------------------===//
 
 MachineBasicBlock *AVRTargetLowering::insertShift(MachineInstr &MI,
                                                   MachineBasicBlock *BB) const {
   unsigned Opc;
   const TargetRegisterClass *RC;
   bool HasRepeatedOperand = false;
-  bool HasZeroOperand = false;
   MachineFunction *F = BB->getParent();
   MachineRegisterInfo &RI = F->getRegInfo();
   const TargetInstrInfo &TII = *Subtarget.getInstrInfo();
   DebugLoc dl = MI.getDebugLoc();
 
   switch (MI.getOpcode()) {
   default:
     llvm_unreachable("Invalid shift opcode!");
case AVR::Lsr8:
     break;
   case AVR::Lsr16:
     Opc = AVR::LSRWRd;
     RC = &AVR::DREGSRegClass;
     break;
   case AVR::Rol8:
     Opc = AVR::ROLBRd;
     RC = &AVR::GPR8RegClass;
-    HasZeroOperand = true;
     break;
   case AVR::Rol16:
     Opc = AVR::ROLWRd;
     RC = &AVR::DREGSRegClass;
     break;
   case AVR::Ror8:
     Opc = AVR::RORBRd;
     RC = &AVR::GPR8RegClass;
MachineBasicBlock *AVRTargetLowering::insertShift(MachineInstr &MI,
   // rjmp CheckBB
   BuildMI(BB, dl, TII.get(AVR::RJMPk)).addMBB(CheckBB);
 
   // LoopBB:
   // ShiftReg2 = shift ShiftReg
   auto ShiftMI = BuildMI(LoopBB, dl, TII.get(Opc), ShiftReg2).addReg(ShiftReg);
   if (HasRepeatedOperand)
     ShiftMI.addReg(ShiftReg);
-  if (HasZeroOperand)
-    ShiftMI.addReg(Subtarget.getZeroRegister());
 
   // CheckBB:
   // ShiftReg = phi [%SrcReg, BB], [%ShiftReg2, LoopBB]
   // ShiftAmt = phi [%N,      BB], [%ShiftAmt2, LoopBB]
   // DestReg  = phi [%SrcReg, BB], [%ShiftReg,  LoopBB]
   // ShiftAmt2 = ShiftAmt - 1;
   // if (ShiftAmt2 >= 0) goto LoopBB;
   BuildMI(CheckBB, dl, TII.get(AVR::PHI), ShiftReg)

llvm/lib/Target/AVR/AVRInstrInfo.td

def ASRWRd : Pseudo<(outs DREGS
                       [(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)]>;
 
-  let hasSideEffects=0 in
   def ROLBRd : Pseudo<(outs GPR8
                        : $rd),
-                      (ins GPR8:$src, GPR8:$zero),
+                      (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

llvm/test/CodeGen/AVR/pseudo/ROLBrd.mir

 body: |
   bb.0.entry:
     liveins: $r14
 
     ; CHECK-LABEL: test_rolbrd
 
     ; CHECK:      $r14 = ADDRdRr killed $r14, killed $r14, implicit-def $sreg
     ; CHECK-NEXT: $r14 = ADCRdRr $r14, $r1, implicit-def dead $sreg, implicit killed $sreg
-    $r14 = ROLBRd $r14, $r1, implicit-def $sreg
-
-    ; avrtiny variant
-    ; CHECK:      $r14 = ADDRdRr killed $r14, killed $r14, implicit-def $sreg
-    ; CHECK-NEXT: $r14 = ADCRdRr $r14, $r17, implicit-def dead $sreg, implicit killed $sreg
-    $r14 = ROLBRd $r14, $r17, implicit-def $sreg
+    $r14 = ROLBRd $r14, implicit-def $sreg
 ...

llvm/test/CodeGen/AVR/rotate.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py UTC_ARGS: --version 2
+; RUN: llc < %s -mtriple=avr | FileCheck %s
+
+define i8 @rotl8_1(i8 %x) {
+; CHECK-LABEL: rotl8_1:
+; CHECK:       ; %bb.0: ; %start
+; CHECK-NEXT:    lsl r24
+; CHECK-NEXT:    adc r24, r1
+; CHECK-NEXT:    ret
+start:
+  %0 = call i8 @llvm.fshl.i8(i8 %x, i8 %x, i8 1)
+  ret i8 %0
+}
+
+define i8 @rotl8_3(i8 %x) {
+; CHECK-LABEL: rotl8_3:
+; CHECK:       ; %bb.0: ; %start
+; CHECK-NEXT:    lsl r24
+; CHECK-NEXT:    adc r24, r1
+; CHECK-NEXT:    lsl r24
+; CHECK-NEXT:    adc r24, r1
+; CHECK-NEXT:    lsl r24
+; CHECK-NEXT:    adc r24, r1
+; CHECK-NEXT:    ret
+start:
+  %0 = call i8 @llvm.fshl.i8(i8 %x, i8 %x, i8 3)
+  ret i8 %0
+}
+
+define i8 @rotl8_dyn(i8 %x, i8 %y) {
+; CHECK-LABEL: rotl8_dyn:
+; CHECK:       ; %bb.0: ; %start
+; CHECK-NEXT:    andi r22, 7
+; CHECK-NEXT:    dec r22
+; CHECK-NEXT:    brmi .LBB2_2
+; CHECK-NEXT:  .LBB2_1: ; %start
+; CHECK-NEXT:    ; =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    lsl r24
+; CHECK-NEXT:    adc r24, r1
+; CHECK-NEXT:    dec r22
+; CHECK-NEXT:    brpl .LBB2_1
+; CHECK-NEXT:  .LBB2_2: ; %start
+; CHECK-NEXT:    ret
+start:
+  %0 = call i8 @llvm.fshl.i8(i8 %x, i8 %x, i8 %y)
+  ret i8 %0
+}
+
+define i8 @rotr8_1(i8 %x) {
+; CHECK-LABEL: rotr8_1:
+; CHECK:       ; %bb.0: ; %start
+; CHECK-NEXT:    bst r24, 0
+; CHECK-NEXT:    ror r24
+; CHECK-NEXT:    bld r24, 7
+; CHECK-NEXT:    ret
+start:
+  %0 = call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 1)
+  ret i8 %0
+}
+
+define i8 @rotr8_3(i8 %x) {
+; CHECK-LABEL: rotr8_3:
+; CHECK:       ; %bb.0: ; %start
+; CHECK-NEXT:    bst r24, 0
+; CHECK-NEXT:    ror r24
+; CHECK-NEXT:    bld r24, 7
+; CHECK-NEXT:    bst r24, 0
+; CHECK-NEXT:    ror r24
+; CHECK-NEXT:    bld r24, 7
+; CHECK-NEXT:    bst r24, 0
+; CHECK-NEXT:    ror r24
+; CHECK-NEXT:    bld r24, 7
+; CHECK-NEXT:    ret
+start:
+  %0 = call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 3)
+  ret i8 %0
+}
+
+define i8 @rotr8_dyn(i8 %x, i8 %y) {
+; CHECK-LABEL: rotr8_dyn:
+; CHECK:       ; %bb.0: ; %start
+; CHECK-NEXT:    andi r22, 7
+; CHECK-NEXT:    dec r22
+; CHECK-NEXT:    brmi .LBB5_2
+; CHECK-NEXT:  .LBB5_1: ; %start
+; CHECK-NEXT:    ; =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    bst r24, 0
+; CHECK-NEXT:    ror r24
+; CHECK-NEXT:    bld r24, 7
+; CHECK-NEXT:    dec r22
+; CHECK-NEXT:    brpl .LBB5_1
+; CHECK-NEXT:  .LBB5_2: ; %start
+; CHECK-NEXT:    ret
+start:
+  %0 = call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 %y)
+  ret i8 %0
+}
+
+define i16 @rotl16(i16 %x) {
+; CHECK-LABEL: rotl16:
+; CHECK:       ; %bb.0: ; %start
+; CHECK-NEXT:    mov r18, r24
+; CHECK-NEXT:    mov r19, r25
+; CHECK-NEXT:    lsl r18
+; CHECK-NEXT:    rol r19
+; CHECK-NEXT:    lsl r18
+; CHECK-NEXT:    rol r19
+; CHECK-NEXT:    mov r24, r25
+; CHECK-NEXT:    swap r24
+; CHECK-NEXT:    andi r24, 15
+; CHECK-NEXT:    clr r25
+; CHECK-NEXT:    lsr r24
+; CHECK-NEXT:    lsr r24
+; CHECK-NEXT:    or r24, r18
+; CHECK-NEXT:    or r25, r19
+; CHECK-NEXT:    ret
+start:
+  %0 = call i16 @llvm.fshl.i16(i16 %x, i16 %x, i16 2)
+  ret i16 %0
+}
+
+define i16 @rotr16(i16 %x) {
+; CHECK-LABEL: rotr16:
+; CHECK:       ; %bb.0: ; %start
+; CHECK-NEXT:    mov r18, r24
+; CHECK-NEXT:    mov r19, r25
+; CHECK-NEXT:    lsr r19
+; CHECK-NEXT:    ror r18
+; CHECK-NEXT:    lsr r19
+; CHECK-NEXT:    ror r18
+; CHECK-NEXT:    mov r25, r24
+; CHECK-NEXT:    swap r25
+; CHECK-NEXT:    andi r25, 240
+; CHECK-NEXT:    clr r24
+; CHECK-NEXT:    lsl r25
+; CHECK-NEXT:    lsl r25
+; CHECK-NEXT:    or r24, r18
+; CHECK-NEXT:    or r25, r19
+; CHECK-NEXT:    ret
+start:
+  %0 = call i16 @llvm.fshr.i16(i16 %x, i16 %x, i16 2)
+  ret i16 %0
+}
+
+define i32 @rotl32(i32 %x) {
+; CHECK-LABEL: rotl32:
+; CHECK:       ; %bb.0: ; %start
+; CHECK-NEXT:    mov r20, r22
+; CHECK-NEXT:    mov r21, r23
+; CHECK-NEXT:    lsl r20
+; CHECK-NEXT:    rol r21
+; CHECK-NEXT:    lsl r20
+; CHECK-NEXT:    rol r21
+; CHECK-NEXT:    mov r18, r24
+; CHECK-NEXT:    mov r19, r25
+; CHECK-NEXT:    mov r18, r19
+; CHECK-NEXT:    swap r18
+; CHECK-NEXT:    andi r18, 15
+; CHECK-NEXT:    clr r19
+; CHECK-NEXT:    lsr r18
+; CHECK-NEXT:    lsr r18
+; CHECK-NEXT:    or r18, r20
+; CHECK-NEXT:    or r19, r21
+; CHECK-NEXT:    lsl r24
+; CHECK-NEXT:    rol r25
+; CHECK-NEXT:    lsl r24
+; CHECK-NEXT:    rol r25
+; CHECK-NEXT:    mov r22, r23
+; CHECK-NEXT:    swap r22
+; CHECK-NEXT:    andi r22, 15
+; CHECK-NEXT:    clr r23
+; CHECK-NEXT:    lsr r22
+; CHECK-NEXT:    lsr r22
+; CHECK-NEXT:    or r24, r22
+; CHECK-NEXT:    or r25, r23
+; CHECK-NEXT:    mov r22, r18
+; CHECK-NEXT:    mov r23, r19
+; CHECK-NEXT:    ret
+start:
+  %0 = call i32 @llvm.fshl.i32(i32 %x, i32 %x, i32 2)
+  ret i32 %0
+}
+
+define i32 @rotr32(i32 %x) {
+; CHECK-LABEL: rotr32:
+; CHECK:       ; %bb.0: ; %start
+; CHECK-NEXT:    mov r20, r22
+; CHECK-NEXT:    mov r21, r23
+; CHECK-NEXT:    lsr r21
+; CHECK-NEXT:    ror r20
+; CHECK-NEXT:    lsr r21
+; CHECK-NEXT:    ror r20
+; CHECK-NEXT:    mov r18, r24
+; CHECK-NEXT:    mov r19, r25
+; CHECK-NEXT:    mov r19, r18
+; CHECK-NEXT:    swap r19
+; CHECK-NEXT:    andi r19, 240
+; CHECK-NEXT:    clr r18
+; CHECK-NEXT:    lsl r19
+; CHECK-NEXT:    lsl r19
+; CHECK-NEXT:    or r18, r20
+; CHECK-NEXT:    or r19, r21
+; CHECK-NEXT:    lsr r25
+; CHECK-NEXT:    ror r24
+; CHECK-NEXT:    lsr r25
+; CHECK-NEXT:    ror r24
+; CHECK-NEXT:    mov r23, r22
+; CHECK-NEXT:    swap r23
+; CHECK-NEXT:    andi r23, 240
+; CHECK-NEXT:    clr r22
+; CHECK-NEXT:    lsl r23
+; CHECK-NEXT:    lsl r23
+; CHECK-NEXT:    or r24, r22
+; CHECK-NEXT:    or r25, r23
+; CHECK-NEXT:    mov r22, r18
+; CHECK-NEXT:    mov r23, r19
+; CHECK-NEXT:    ret
+start:
+  %0 = call i32 @llvm.fshr.i32(i32 %x, i32 %x, i32 2)
+  ret i32 %0
+}
+
+declare i8 @llvm.fshl.i8(i8, i8, i8)
+declare i8 @llvm.fshr.i8(i8, i8, i8)
+
+declare i16 @llvm.fshl.i16(i16, i16, i16)
+declare i16 @llvm.fshr.i16(i16, i16, i16)
+
+declare i32 @llvm.fshl.i32(i32, i32, i32)
+declare i32 @llvm.fshr.i32(i32, i32, i32)