[AVR] Expand large shifts early in IR

[aykevl]

Summary

This patch makes sure shift instructions such as this one:

%result = shl i32 %n, %amount

are expanded just before the IR to SelectionDAG conversion to a loop so that calls to non-existing library functions such as __ashlsi3 are avoided. The generated code is currently pretty bad but there's a lot of room for improvement: the shift itself can be done in just four instructions.

---

I have tested this patch locally with my set of compiler-rt based tests and all tests that previously passed still pass. The difference is that there is no __ashlsi3, __ashlsi3, or __lshrsi3 call anymore in the code.

[aykevl]

Oops I uploaded the wrong patch.

[benshi001]

llvm/lib/Target/AVR/AVRShiftExpand.cpp

53

can this line be simpilfied to

for (Instruction &I : instructions(F))

as in Transforms/IPO/Attributor.h ?

55–64

Is it better to combine all these conditions to only one if statement?

68–71

Is this line needed?

the following for-statement won't run if ShiftInsts.size() == 0

And we just return ShiftInsts.size() > 0 at the end.

93

Is it possible to generate a check about ShiftAmount>32, like that

  cmp ShiftAmount, 32
  brlt _labloop
  mov Rdst, 0
  ret
_labloop:
  the shift loop

However avr-gcc does not generate the check against 32.

llvm/test/CodeGen/AVR/shift-expand.ll

12

How about try to generate instruction serial with llvm/utils/update_llc_test_checks.py ? It already support AVR.

[aykevl]

llvm/lib/Target/AVR/AVRShiftExpand.cpp

53

Thank you! Yes, that looks a lot better.

55–64

I think keeping them separate is better for readability. Now every condition has a comment explaining why the condition needs to be checked.

68–71

I've modified the code accordingly. Either seems fine by me.

93

Shifts larger or equal to the bit width (>=32) are a poison value according to the LangRef. Therefore, in practice they should not occur. I believe they're undefined behavior according to the C standard.

llvm/test/CodeGen/AVR/shift-expand.ll

12

Good idea, I'll use update_test_checks.py.

Note that the output is IR, not AVR assembly. This is a pure IR level pass.

[aykevl]

• fix lint checks (hopefully)
• simplify pass a bit, with suggestions from @benshi001
• use update_test_checks.py for the test

[benshi001]

I am not sure such a specific pass is needed. Why __ashlsi3 is not called in other backends? Is there a config flag/option to prevent calling __ashlsi3 ?

[aykevl]

In D96677#2577490, @benshi001 wrote:

I am not sure such a specific pass is needed. Why __ashlsi3 is not called in other backends? Is there a config flag/option to prevent calling __ashlsi3 ?

Because most instruction sets do support 32-bit shifts but AVR does not. For example, it appears that the MSP430 has the same problem: https://reviews.llvm.org/D78663#2215170.

I've investigated whether there are any other options to this but I couldn't come up with any. The builtin calls are created inside SelectionDAG which converts non-constant shifts to library calls. Therefore, this pass converts non-constant shifts to constant shifts in a loop to match avr-gcc so that the resulting code does not contain any 32-bit non-constant shifts.

[benshi001]

In D96677#2577602, @aykevl wrote:

In D96677#2577490, @benshi001 wrote:

I am not sure such a specific pass is needed. Why __ashlsi3 is not called in other backends? Is there a config flag/option to prevent calling __ashlsi3 ?

Because most instruction sets do support 32-bit shifts but AVR does not. For example, it appears that the MSP430 has the same problem: https://reviews.llvm.org/D78663#2215170.

I've investigated whether there are any other options to this but I couldn't come up with any. The builtin calls are created inside SelectionDAG which converts non-constant shifts to library calls. Therefore, this pass converts non-constant shifts to constant shifts in a loop to match avr-gcc so that the resulting code does not contain any 32-bit non-constant shifts.

I see and I am OK with this solution. What about Dylan's opinion?

[aykevl]

• fix lint warnings

[aykevl]

• fixes so that shl i32 undef, undef doesn't crash

[dylanmckay]

This looks good to me, and, it is especially nice to remove the dependency on the nonexistent runtime lib functions which has been a big issue. Nice work

llvm/lib/Target/AVR/AVR.h

 #include "llvm/CodeGen/SelectionDAGNodes.h"
 #include "llvm/Target/TargetMachine.h"
 
 namespace llvm {
 
 class AVRTargetMachine;
 class FunctionPass;
 
+Pass *createAVRShiftExpandPass();
 FunctionPass *createAVRISelDag(AVRTargetMachine &TM,
                                CodeGenOpt::Level OptLevel);
 FunctionPass *createAVRExpandPseudoPass();
 FunctionPass *createAVRFrameAnalyzerPass();
 FunctionPass *createAVRRelaxMemPass();
 FunctionPass *createAVRDynAllocaSRPass();
 FunctionPass *createAVRBranchSelectionPass();
 
+void initializeAVRShiftExpandPass(PassRegistry &);
 void initializeAVRExpandPseudoPass(PassRegistry&);
 void initializeAVRRelaxMemPass(PassRegistry&);
 
 /// Contains the AVR backend.
 namespace AVR {
 
 /// An integer that identifies all of the supported AVR address spaces.
 enum AddressSpace { DataMemory, ProgramMemory };

llvm/lib/Target/AVR/AVRShiftExpand.cpp

+//===- AVRShift.cpp - Shift Expansion Pass --------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// Expand 32-bit shift instructions (shl, lshr, ashr) to inline loops, just
+/// like avr-gcc. This must be done in IR because otherwise the type legalizer
+/// will turn 32-bit shifts into (non-existing) library calls such as __ashlsi3.
+//
+//===----------------------------------------------------------------------===//
+
+#include "AVR.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstIterator.h"
+
+using namespace llvm;
+
+namespace {
+
+class AVRShiftExpand : public FunctionPass {
+public:
+  static char ID;
+
+  AVRShiftExpand() : FunctionPass(ID) {}
+
+  bool runOnFunction(Function &F) override;
+
+  StringRef getPassName() const override { return "AVR Shift Expansion"; }
+
+private:
+  void expand(BinaryOperator *BI);
+};
+
+} // end of anonymous namespace
+
+char AVRShiftExpand::ID = 0;
+
+INITIALIZE_PASS(AVRShiftExpand, "avr-shift-expand", "AVR Shift Expansion",
+                false, false)
+
+Pass *llvm::createAVRShiftExpandPass() { return new AVRShiftExpand(); }
+
+bool AVRShiftExpand::runOnFunction(Function &F) {
+  SmallVector<BinaryOperator *, 1> ShiftInsts;
+  auto &Ctx = F.getContext();
+  for (Instruction &I : instructions(F)) {
+    if (!I.isShift())
+      // Only expand shift instructions (shl, lshr, ashr).
+      continue;
+    if (I.getType() != Type::getInt32Ty(Ctx))
+      // Only expand plain i32 types.
+      continue;
+    if (isa<ConstantInt>(I.getOperand(1)))
+      // Only expand when the shift amount is not known.
+      // Known shift amounts are (currently) better expanded inline.
+      continue;
+    ShiftInsts.push_back(cast<BinaryOperator>(&I));
+  }
+
+  // The expanding itself needs to be done separately as expand() will remove
+  // these instructions. Removing instructions while iterating over a basic
+  // block is not a great idea.
+  for (auto *I : ShiftInsts) {
+    expand(I);
+  }
+
+  // Return whether this function expanded any shift instructions.
+  return ShiftInsts.size() > 0;
+}
+
+void AVRShiftExpand::expand(BinaryOperator *BI) {
+  auto &Ctx = BI->getContext();
+  IRBuilder<> Builder(BI);
+  Type *Int32Ty = Type::getInt32Ty(Ctx);
+  Type *Int8Ty = Type::getInt8Ty(Ctx);
+  Value *Int8Zero = ConstantInt::get(Int8Ty, 0);
+
+  // Split the current basic block at the point of the existing shift
+  // instruction and insert a new basic block for the loop.
+  BasicBlock *BB = BI->getParent();
+  Function *F = BB->getParent();
+  BasicBlock *EndBB = BB->splitBasicBlock(BI, "shift.done");
+  BasicBlock *LoopBB = BasicBlock::Create(Ctx, "shift.loop", F, EndBB);
+
+  // Truncate the shift amount to i8, which is trivially lowered to a single
+  // AVR register.
+  Builder.SetInsertPoint(&BB->back());
+  Value *ShiftAmount = Builder.CreateTrunc(BI->getOperand(1), Int8Ty);
+
+  // Replace the unconditional branch that splitBasicBlock created with a
+  // conditional branch.
+  Value *Cmp1 = Builder.CreateICmpEQ(ShiftAmount, Int8Zero);
+  Builder.CreateCondBr(Cmp1, EndBB, LoopBB);
+  BB->back().eraseFromParent();
+
+  // Create the loop body starting with PHI nodes.
+  Builder.SetInsertPoint(LoopBB);
+  PHINode *ShiftAmountPHI = Builder.CreatePHI(Int8Ty, 2);
+  ShiftAmountPHI->addIncoming(ShiftAmount, BB);
+  PHINode *ValuePHI = Builder.CreatePHI(Int32Ty, 2);
+  ValuePHI->addIncoming(BI->getOperand(0), BB);
+
+  // Subtract the shift amount by one, as we're shifting one this loop
+  // iteration.
+  Value *ShiftAmountSub =
+      Builder.CreateSub(ShiftAmountPHI, ConstantInt::get(Int8Ty, 1));
+  ShiftAmountPHI->addIncoming(ShiftAmountSub, LoopBB);
+
+  // Emit the actual shift instruction. The difference is that this shift
+  // instruction has a constant shift amount, which can be emitted inline
+  // without a library call.
+  Value *ValueShifted;
+  switch (BI->getOpcode()) {
+  case Instruction::Shl:
+    ValueShifted = Builder.CreateShl(ValuePHI, ConstantInt::get(Int32Ty, 1));
+    break;
+  case Instruction::LShr:
+    ValueShifted = Builder.CreateLShr(ValuePHI, ConstantInt::get(Int32Ty, 1));
+    break;
+  case Instruction::AShr:
+    ValueShifted = Builder.CreateAShr(ValuePHI, ConstantInt::get(Int32Ty, 1));
+    break;
+  default:
+    llvm_unreachable("asked to expand an instruction that is not a shift");
+  }
+  ValuePHI->addIncoming(ValueShifted, LoopBB);
+
+  // Branch to either the loop again (if there is more to shift) or to the
+  // basic block after the loop (if all bits are shifted).
+  Value *Cmp2 = Builder.CreateICmpEQ(ShiftAmountSub, Int8Zero);
+  Builder.CreateCondBr(Cmp2, EndBB, LoopBB);
+
+  // Collect the resulting value. This is necessary in the IR but won't produce
+  // any actual instructions.
+  Builder.SetInsertPoint(BI);
+  PHINode *Result = Builder.CreatePHI(Int32Ty, 2);
+  Result->addIncoming(BI->getOperand(0), BB);
+  Result->addIncoming(ValueShifted, LoopBB);
+
+  // Replace the original shift instruction.
+  BI->replaceAllUsesWith(Result);
+  BI->eraseFromParent();
+}

llvm/lib/Target/AVR/AVRTargetMachine.cpp

 public:
   AVRPassConfig(AVRTargetMachine &TM, PassManagerBase &PM)
       : TargetPassConfig(TM, PM) {}
 
   AVRTargetMachine &getAVRTargetMachine() const {
     return getTM<AVRTargetMachine>();
   }
 
+  void addIRPasses() override;
   bool addInstSelector() override;
   void addPreSched2() override;
   void addPreEmitPass() override;
   void addPreRegAlloc() override;
 };
 } // namespace
 
 TargetPassConfig *AVRTargetMachine::createPassConfig(PassManagerBase &PM) {
   return new AVRPassConfig(*this, PM);
 }
 
+void AVRPassConfig::addIRPasses() {
+  // Expand instructions like
+  //   %result = shl i32 %n, %amount
+  // to a loop so that library calls are avoided.
+  addPass(createAVRShiftExpandPass());
+
+  TargetPassConfig::addIRPasses();
+}
+
 extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeAVRTarget() {
   // Register the target.
   RegisterTargetMachine<AVRTargetMachine> X(getTheAVRTarget());
 
   auto &PR = *PassRegistry::getPassRegistry();
   initializeAVRExpandPseudoPass(PR);
   initializeAVRRelaxMemPass(PR);
+  initializeAVRShiftExpandPass(PR);
 }
 
 const AVRSubtarget *AVRTargetMachine::getSubtargetImpl() const {
   return &SubTarget;
 }
 
 const AVRSubtarget *AVRTargetMachine::getSubtargetImpl(const Function &) const {
   return &SubTarget;

llvm/lib/Target/AVR/CMakeLists.txt

add_llvm_target(AVRCodeGen
   AVRExpandPseudoInsts.cpp
   AVRFrameLowering.cpp
   AVRInstrInfo.cpp
   AVRISelDAGToDAG.cpp
   AVRISelLowering.cpp
   AVRMCInstLower.cpp
   AVRRelaxMemOperations.cpp
   AVRRegisterInfo.cpp
+  AVRShiftExpand.cpp
   AVRSubtarget.cpp
   AVRTargetMachine.cpp
   AVRTargetObjectFile.cpp
 
   DEPENDS
   intrinsics_gen
 
   LINK_COMPONENTS

llvm/test/CodeGen/AVR/shift-expand.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -avr-shift-expand -S %s -o - | FileCheck %s
+
+; The avr-shift-expand pass expands large shifts with a non-constant shift
+; amount to a loop. These loops avoid generating a (non-existing) builtin such
+; as __ashlsi3.
+
+target datalayout = "e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-a:8"
+target triple = "avr"
+
+define i32 @shl(i32 %value, i32 %amount) addrspace(1) {
+; CHECK-LABEL: @shl(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[AMOUNT:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[TMP2]], label [[SHIFT_DONE:%.*]], label [[SHIFT_LOOP:%.*]]
+; CHECK:       shift.loop:
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i8 [ [[TMP1]], [[TMP0:%.*]] ], [ [[TMP5:%.*]], [[SHIFT_LOOP]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i32 [ [[VALUE:%.*]], [[TMP0]] ], [ [[TMP6:%.*]], [[SHIFT_LOOP]] ]
+; CHECK-NEXT:    [[TMP5]] = sub i8 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP6]] = shl i32 [[TMP4]], 1
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i8 [[TMP5]], 0
+; CHECK-NEXT:    br i1 [[TMP7]], label [[SHIFT_DONE]], label [[SHIFT_LOOP]]
+; CHECK:       shift.done:
+; CHECK-NEXT:    [[TMP8:%.*]] = phi i32 [ [[VALUE]], [[TMP0]] ], [ [[TMP6]], [[SHIFT_LOOP]] ]
+; CHECK-NEXT:    ret i32 [[TMP8]]
+;
+  %result = shl i32 %value, %amount
+  ret i32 %result
+}
+
+define i32 @lshr(i32 %value, i32 %amount) addrspace(1) {
+; CHECK-LABEL: @lshr(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[AMOUNT:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[TMP2]], label [[SHIFT_DONE:%.*]], label [[SHIFT_LOOP:%.*]]
+; CHECK:       shift.loop:
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i8 [ [[TMP1]], [[TMP0:%.*]] ], [ [[TMP5:%.*]], [[SHIFT_LOOP]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i32 [ [[VALUE:%.*]], [[TMP0]] ], [ [[TMP6:%.*]], [[SHIFT_LOOP]] ]
+; CHECK-NEXT:    [[TMP5]] = sub i8 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP6]] = lshr i32 [[TMP4]], 1
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i8 [[TMP5]], 0
+; CHECK-NEXT:    br i1 [[TMP7]], label [[SHIFT_DONE]], label [[SHIFT_LOOP]]
+; CHECK:       shift.done:
+; CHECK-NEXT:    [[TMP8:%.*]] = phi i32 [ [[VALUE]], [[TMP0]] ], [ [[TMP6]], [[SHIFT_LOOP]] ]
+; CHECK-NEXT:    ret i32 [[TMP8]]
+;
+  %result = lshr i32 %value, %amount
+  ret i32 %result
+}
+
+define i32 @ashr(i32 %0, i32 %1) addrspace(1) {
+; CHECK-LABEL: @ashr(
+; CHECK-NEXT:    [[TMP3:%.*]] = trunc i32 [[TMP1:%.*]] to i8
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i8 [[TMP3]], 0
+; CHECK-NEXT:    br i1 [[TMP4]], label [[SHIFT_DONE:%.*]], label [[SHIFT_LOOP:%.*]]
+; CHECK:       shift.loop:
+; CHECK-NEXT:    [[TMP5:%.*]] = phi i8 [ [[TMP3]], [[TMP2:%.*]] ], [ [[TMP7:%.*]], [[SHIFT_LOOP]] ]
+; CHECK-NEXT:    [[TMP6:%.*]] = phi i32 [ [[TMP0:%.*]], [[TMP2]] ], [ [[TMP8:%.*]], [[SHIFT_LOOP]] ]
+; CHECK-NEXT:    [[TMP7]] = sub i8 [[TMP5]], 1
+; CHECK-NEXT:    [[TMP8]] = ashr i32 [[TMP6]], 1
+; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i8 [[TMP7]], 0
+; CHECK-NEXT:    br i1 [[TMP9]], label [[SHIFT_DONE]], label [[SHIFT_LOOP]]
+; CHECK:       shift.done:
+; CHECK-NEXT:    [[TMP10:%.*]] = phi i32 [ [[TMP0]], [[TMP2]] ], [ [[TMP8]], [[SHIFT_LOOP]] ]
+; CHECK-NEXT:    ret i32 [[TMP10]]
+;
+  %3 = ashr i32 %0, %1
+  ret i32 %3
+}
+
+; This function is not modified because it is not an i32.
+define i40 @shl40(i40 %value, i40 %amount) addrspace(1) {
+; CHECK-LABEL: @shl40(
+; CHECK-NEXT:    [[RESULT:%.*]] = shl i40 [[VALUE:%.*]], [[AMOUNT:%.*]]
+; CHECK-NEXT:    ret i40 [[RESULT]]
+;
+  %result = shl i40 %value, %amount
+  ret i40 %result
+}
+
+; This function isn't either, although perhaps it should.
+define i24 @shl24(i24 %value, i24 %amount) addrspace(1) {
+; CHECK-LABEL: @shl24(
+; CHECK-NEXT:    [[RESULT:%.*]] = shl i24 [[VALUE:%.*]], [[AMOUNT:%.*]]
+; CHECK-NEXT:    ret i24 [[RESULT]]
+;
+  %result = shl i24 %value, %amount
+  ret i24 %result
+}