[AVR] Optimize 32-bit shifts: shift by 4 bits

[aykevl]

Summary

This uses a complicated shift sequence that avr-gcc also uses, but
extended to work over any number of bytes and in both directions
(logical shift left and logical shift right). Unfortunately it can't be
used for an arithmetic shift right: I've tried to come up with a
sequence but couldn't.

[aykevl]

• rebase

[benshi001]

llvm/lib/Target/AVR/AVRISelLowering.cpp

1934

I have two concerns here:

1. It would be better to show a 4-byte shift example, other than a 2-byte one, since you are optimizating the previous one.

2. Your inline comments ; shift r1 and ; shift r0 are incorrect, actually the r1 is also modified by the last instruction. I think you only give the direct instruction sequence is OK enough.

1941

Use I than 'i' to be conform with other loops in this function.

1946

I think it would be better to change to if (i > 0).

1957

I think it would be better to change to if (i > 0).

1963

How about

size_t PrevIdx = ShiftLeft ? Idx - 1 : Idx + 1;
Regs[PrevIdx] = std::pair(R, 0);

llvm/test/CodeGen/AVR/shift32.ll

168

This looks really great!

[aykevl]

• apply review feedback

llvm/lib/Target/AVR/AVRISelLowering.cpp

1934

Yes, this isn't very clear. I have updated the explanation in a way that better explains what the code does.

1946

Hmm, somehow I missed this while rebasing. Fixed.

1957

Fixed.

1963

Not sure which one is clearer but seems good to me. Change applied.

llvm/lib/Target/AVR/AVRISelLowering.cpp

for (; ShiftAmt >= 8; ShiftAmt -= 8) {
       // Continue shifts with the leftover registers.
       Regs = Regs.drop_front(1);
     }
   }
 
   // The bigger shifts are already handled above.
   assert((ShiftAmt < 8) && "Unexpect shift amount");
 
+  // Shift by four bits, using a complicated swap/eor/andi/eor sequence.
+  // It only works for logical shifts because the bits shifted in are all
+  // zeroes.
+  // To shift a single byte right, it produces code like this:
+  //   swap r0
+  //   andi r0, 0x0f
+  // For a two-byte (16-bit) shift, it adds the following instructions to shift
+  // the upper byte into the lower byte:
+  //   swap r1
+  //   eor r0, r1
+  //   andi r1, 0x0f
+  //   eor r0, r1
+  // For bigger shifts, it repeats the above sequence. For example, for a 3-byte
+  // (24-bit) shift it adds:
+  //   swap r2
+  //   eor r1, r2
+  //   andi r2, 0x0f
+  //   eor r1, r2
+  if (!ArithmeticShift && ShiftAmt >= 4) {
+    Register Prev = 0;
+    for (size_t I = 0; I < Regs.size(); I++) {
+      size_t Idx = ShiftLeft ? I : Regs.size() - I - 1;
+      Register SwapReg = MRI.createVirtualRegister(&AVR::LD8RegClass);
+      BuildMI(*BB, MI, dl, TII.get(AVR::SWAPRd), SwapReg)
+          .addReg(Regs[Idx].first, 0, Regs[Idx].second);
+      if (I != 0) {
+        Register R = MRI.createVirtualRegister(&AVR::GPR8RegClass);
+        BuildMI(*BB, MI, dl, TII.get(AVR::EORRdRr), R)
+            .addReg(Prev)
+            .addReg(SwapReg);
+        Prev = R;
+      }
+      Register AndReg = MRI.createVirtualRegister(&AVR::LD8RegClass);
+      BuildMI(*BB, MI, dl, TII.get(AVR::ANDIRdK), AndReg)
+          .addReg(SwapReg)
+          .addImm(ShiftLeft ? 0xf0 : 0x0f);
+      if (I != 0) {
+        Register R = MRI.createVirtualRegister(&AVR::GPR8RegClass);
+        BuildMI(*BB, MI, dl, TII.get(AVR::EORRdRr), R)
+            .addReg(Prev)
+            .addReg(AndReg);
+        size_t PrevIdx = ShiftLeft ? Idx - 1 : Idx + 1;
+        Regs[PrevIdx] = std::pair(R, 0);
+      }
+      Prev = AndReg;
+      Regs[Idx] = std::pair(AndReg, 0);
+    }
+    ShiftAmt -= 4;
+  }
+
   // Shift by one. This is the fallback that always works, and the shift
   // operation that is used for 1, 2, and 3 bit shifts.
   while (ShiftLeft && ShiftAmt) {
     // Shift one to the left.
     for (ssize_t I = Regs.size() - 1; I >= 0; I--) {
       Register Out = MRI.createVirtualRegister(&AVR::GPR8RegClass);
       Register In = Regs[I].first;
       Register InSubreg = Regs[I].second;

llvm/test/CodeGen/AVR/shift32.ll

 ; CHECK-NEXT:    rol r23
 ; CHECK-NEXT:    rol r24
 ; CHECK-NEXT:    rol r25
 ; CHECK-NEXT:    ret
   %res = shl i32 %a, 2
   ret i32 %res
 }
 
+define i32 @shl_i32_4(i32 %a) {
+; CHECK-LABEL: shl_i32_4:
+; CHECK:       ; %bb.0:
+; CHECK-NEXT:    swap r25
+; CHECK-NEXT:    andi r25, 240
+; CHECK-NEXT:    swap r24
+; CHECK-NEXT:    eor r25, r24
+; CHECK-NEXT:    andi r24, 240
+; CHECK-NEXT:    eor r25, r24
+; CHECK-NEXT:    swap r23
+; CHECK-NEXT:    eor r24, r23
+; CHECK-NEXT:    andi r23, 240
+; CHECK-NEXT:    eor r24, r23
+; CHECK-NEXT:    swap r22
+; CHECK-NEXT:    eor r23, r22
+; CHECK-NEXT:    andi r22, 240
+; CHECK-NEXT:    eor r23, r22
+; CHECK-NEXT:    ret
+  %res = shl i32 %a, 4
+  ret i32 %res
+}
+
+; shift four bits and then shift one bit
+define i32 @shl_i32_5(i32 %a) {
+; CHECK-LABEL: shl_i32_5:
+; CHECK:       ; %bb.0:
+; CHECK-NEXT:    swap r25
+; CHECK-NEXT:    andi r25, 240
+; CHECK-NEXT:    swap r24
+; CHECK-NEXT:    eor r25, r24
+; CHECK-NEXT:    andi r24, 240
+; CHECK-NEXT:    eor r25, r24
+; CHECK-NEXT:    swap r23
+; CHECK-NEXT:    eor r24, r23
+; CHECK-NEXT:    andi r23, 240
+; CHECK-NEXT:    eor r24, r23
+; CHECK-NEXT:    swap r22
+; CHECK-NEXT:    eor r23, r22
+; CHECK-NEXT:    andi r22, 240
+; CHECK-NEXT:    eor r23, r22
+; CHECK-NEXT:    lsl r22
+; CHECK-NEXT:    rol r23
+; CHECK-NEXT:    rol r24
+; CHECK-NEXT:    rol r25
+; CHECK-NEXT:    ret
+  %res = shl i32 %a, 5
+  ret i32 %res
+}
+
 define i32 @shl_i32_8(i32 %a) {
 ; CHECK-LABEL: shl_i32_8:
 ; CHECK:       ; %bb.0:
 ; CHECK-NEXT:    mov r25, r24
 ; CHECK-NEXT:    mov r24, r23
 ; CHECK-NEXT:    mov r23, r22
 ; CHECK-NEXT:    mov r22, r1
 ; CHECK-NEXT:    ret

 ; CHECK-NEXT:    mov r24, r23
 ; CHECK-NEXT:    mov r23, r22
 ; CHECK-NEXT:    mov r22, r1
 ; CHECK-NEXT:    ret
   %res = shl i32 %a, 9
   ret i32 %res
 }
 
+; shift 3 of 4 registers and move the others around
+define i32 @shl_i32_12(i32 %a) {
+; CHECK-LABEL: shl_i32_12:
+; CHECK:       ; %bb.0:
+; CHECK-NEXT:    swap r24
+; CHECK-NEXT:    andi r24, 240
+; CHECK-NEXT:    swap r23
+; CHECK-NEXT:    eor r24, r23
+; CHECK-NEXT:    andi r23, 240
+; CHECK-NEXT:    eor r24, r23
+; CHECK-NEXT:    swap r22
+; CHECK-NEXT:    eor r23, r22
+; CHECK-NEXT:    andi r22, 240
+; CHECK-NEXT:    eor r23, r22
+; CHECK-NEXT:    mov r25, r24
+; CHECK-NEXT:    mov r24, r23
+; CHECK-NEXT:    mov r23, r22
+; CHECK-NEXT:    mov r22, r1
+; CHECK-NEXT:    ret
+  %res = shl i32 %a, 12
+  ret i32 %res
+}
+
 ; This is a special case: this shift is performed directly inside SelectionDAG
 ; instead of as a custom lowering like the other shift operations.
 define i32 @shl_i32_16(i32 %a) {
 ; CHECK-LABEL: shl_i32_16:
 ; CHECK:       ; %bb.0:
 ; CHECK-NEXT:    movw r24, r22
 ; CHECK-NEXT:    ldi r22, 0
 ; CHECK-NEXT:    ldi r23, 0

 ; CHECK-NEXT:    st Z, r24
 ; CHECK-NEXT:    std Z+1, r25
 ; CHECK-NEXT:    ret
   %res = shl i32 %a, 16
   store i32 %res, ptr %ptr
   ret void
 }
 
+; shift only the most significant byte and then move it
+define i32 @shl_i32_28(i32 %a) {
+; CHECK-LABEL: shl_i32_28:
+; CHECK:       ; %bb.0:
+; CHECK-NEXT:    swap r22
+; CHECK-NEXT:    andi r22, 240
+; CHECK-NEXT:    mov r25, r22
+; CHECK-NEXT:    mov r24, r1
+; CHECK-NEXT:    mov r23, r1
+; CHECK-NEXT:    mov r22, r1
+; CHECK-NEXT:    ret
+  %res = shl i32 %a, 28
+  ret i32 %res
+}
+
 define i32 @lshr_i32_1(i32 %a) {
 ; CHECK-LABEL: lshr_i32_1:
 ; CHECK:       ; %bb.0:
 ; CHECK-NEXT:    lsr r25
 ; CHECK-NEXT:    ror r24
 ; CHECK-NEXT:    ror r23
 ; CHECK-NEXT:    ror r22
 ; CHECK-NEXT:    ret

 ; CHECK-NEXT:    ror r24
 ; CHECK-NEXT:    ror r23
 ; CHECK-NEXT:    ror r22
 ; CHECK-NEXT:    ret
   %res = lshr i32 %a, 2
   ret i32 %res
 }
 
+define i32 @lshr_i32_4(i32 %a) {
+; CHECK-LABEL: lshr_i32_4:
+; CHECK:       ; %bb.0:
+; CHECK-NEXT:    swap r22
+; CHECK-NEXT:    andi r22, 15
+; CHECK-NEXT:    swap r23
+; CHECK-NEXT:    eor r22, r23
+; CHECK-NEXT:    andi r23, 15
+; CHECK-NEXT:    eor r22, r23
+; CHECK-NEXT:    swap r24
+; CHECK-NEXT:    eor r23, r24
+; CHECK-NEXT:    andi r24, 15
+; CHECK-NEXT:    eor r23, r24
+; CHECK-NEXT:    swap r25
+; CHECK-NEXT:    eor r24, r25
+; CHECK-NEXT:    andi r25, 15
+; CHECK-NEXT:    eor r24, r25
+; CHECK-NEXT:    ret
+  %res = lshr i32 %a, 4
+  ret i32 %res
+}
+
 define i32 @lshr_i32_8(i32 %a) {
 ; CHECK-LABEL: lshr_i32_8:
 ; CHECK:       ; %bb.0:
 ; CHECK-NEXT:    mov r19, r1
 ; CHECK-NEXT:    mov r18, r25
 ; CHECK-NEXT:    mov r25, r24
 ; CHECK-NEXT:    mov r24, r23
 ; CHECK-NEXT:    movw r22, r24

 ; CHECK-NEXT:    ror r24
 ; CHECK-NEXT:    ror r23
 ; CHECK-NEXT:    ror r22
 ; CHECK-NEXT:    ret
   %res = ashr i32 %a, 2
   ret i32 %res
 }
 
+; can't use the swap/andi/eor trick here
+define i32 @ashr_i32_4(i32 %a) {
+; CHECK-LABEL: ashr_i32_4:
+; CHECK:       ; %bb.0:
+; CHECK-NEXT:    asr r25
+; CHECK-NEXT:    ror r24
+; CHECK-NEXT:    ror r23
+; CHECK-NEXT:    ror r22
+; CHECK-NEXT:    asr r25
+; CHECK-NEXT:    ror r24
+; CHECK-NEXT:    ror r23
+; CHECK-NEXT:    ror r22
+; CHECK-NEXT:    asr r25
+; CHECK-NEXT:    ror r24
+; CHECK-NEXT:    ror r23
+; CHECK-NEXT:    ror r22
+; CHECK-NEXT:    asr r25
+; CHECK-NEXT:    ror r24
+; CHECK-NEXT:    ror r23
+; CHECK-NEXT:    ror r22
+; CHECK-NEXT:    ret
+  %res = ashr i32 %a, 4
+  ret i32 %res
+}
+
 ; TODO: this could be optimized to 4 movs, instead of 6.
 define i32 @ashr_i32_8(i32 %a) {
 ; CHECK-LABEL: ashr_i32_8:
 ; CHECK:       ; %bb.0:
 ; CHECK-NEXT:    mov r19, r25
 ; CHECK-NEXT:    lsl r19
 ; CHECK-NEXT:    sbc r19, r19
 ; CHECK-NEXT:    mov r18, r25