llvm/lib/Target/AVR/AVRShiftExpand.cpp

   1 //===- AVRShift.cpp - Shift Expansion Pass --------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file
  10 /// Expand non-8-bit and non-16-bit shift instructions (shl, lshr, ashr) to
  11 /// inline loops, just like avr-gcc. This must be done in IR because otherwise
  12 /// the type legalizer will turn 32-bit shifts into (non-existing) library calls
  13 /// such as __ashlsi3.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "AVR.h"
  18 #include "llvm/IR/IRBuilder.h"
  19 #include "llvm/IR/InstIterator.h"
  20
  21 using namespace llvm;
  22
  23 namespace {
  24
  25 class AVRShiftExpand : public FunctionPass {
  26 public:
  27   static char ID;
  28
  29   AVRShiftExpand() : FunctionPass(ID) {}
  30
  31   bool runOnFunction(Function &F) override;
  32
  33   StringRef getPassName() const override { return "AVR Shift Expansion"; }
  34
  35 private:
  36   void expand(BinaryOperator *BI);
  37 };
  38
  39 } // end of anonymous namespace
  40
  41 char AVRShiftExpand::ID = 0;
  42
  43 INITIALIZE_PASS(AVRShiftExpand, "avr-shift-expand", "AVR Shift Expansion",
  44                 false, false)
  45
  46 Pass *llvm::createAVRShiftExpandPass() { return new AVRShiftExpand(); }
  47
  48 bool AVRShiftExpand::runOnFunction(Function &F) {
  49   SmallVector<BinaryOperator *, 1> ShiftInsts;
  50   auto &Ctx = F.getContext();
  51   for (Instruction &I : instructions(F)) {
  52     if (!I.isShift())
  53       // Only expand shift instructions (shl, lshr, ashr).
  54       continue;
  55     if (I.getType() == Type::getInt8Ty(Ctx) || I.getType() == Type::getInt16Ty(Ctx))
  56       // Only expand non-8-bit and non-16-bit shifts, since those are expanded
  57       // directly during isel.
  58       continue;
  59     if (isa<ConstantInt>(I.getOperand(1)))
  60       // Only expand when the shift amount is not known.
  61       // Known shift amounts are (currently) better expanded inline.
  62       continue;
  63     ShiftInsts.push_back(cast<BinaryOperator>(&I));
  64   }
  65
  66   // The expanding itself needs to be done separately as expand() will remove
  67   // these instructions. Removing instructions while iterating over a basic
  68   // block is not a great idea.
  69   for (auto *I : ShiftInsts) {
  70     expand(I);
  71   }
  72
  73   // Return whether this function expanded any shift instructions.
  74   return ShiftInsts.size() > 0;
  75 }
  76
  77 void AVRShiftExpand::expand(BinaryOperator *BI) {
  78   auto &Ctx = BI->getContext();
  79   IRBuilder<> Builder(BI);
  80   Type *InputTy = cast<Instruction>(BI)->getType();
  81   Type *Int8Ty = Type::getInt8Ty(Ctx);
  82   Value *Int8Zero = ConstantInt::get(Int8Ty, 0);
  83
  84   // Split the current basic block at the point of the existing shift
  85   // instruction and insert a new basic block for the loop.
  86   BasicBlock *BB = BI->getParent();
  87   Function *F = BB->getParent();
  88   BasicBlock *EndBB = BB->splitBasicBlock(BI, "shift.done");
  89   BasicBlock *LoopBB = BasicBlock::Create(Ctx, "shift.loop", F, EndBB);
  90
  91   // Truncate the shift amount to i8, which is trivially lowered to a single
  92   // AVR register.
  93   Builder.SetInsertPoint(&BB->back());
  94   Value *ShiftAmount = Builder.CreateTrunc(BI->getOperand(1), Int8Ty);
  95
  96   // Replace the unconditional branch that splitBasicBlock created with a
  97   // conditional branch.
  98   Value *Cmp1 = Builder.CreateICmpEQ(ShiftAmount, Int8Zero);
  99   Builder.CreateCondBr(Cmp1, EndBB, LoopBB);
 100   BB->back().eraseFromParent();
 101
 102   // Create the loop body starting with PHI nodes.
 103   Builder.SetInsertPoint(LoopBB);
 104   PHINode *ShiftAmountPHI = Builder.CreatePHI(Int8Ty, 2);
 105   ShiftAmountPHI->addIncoming(ShiftAmount, BB);
 106   PHINode *ValuePHI = Builder.CreatePHI(InputTy, 2);
 107   ValuePHI->addIncoming(BI->getOperand(0), BB);
 108
 109   // Subtract the shift amount by one, as we're shifting one this loop
 110   // iteration.
 111   Value *ShiftAmountSub =
 112       Builder.CreateSub(ShiftAmountPHI, ConstantInt::get(Int8Ty, 1));
 113   ShiftAmountPHI->addIncoming(ShiftAmountSub, LoopBB);
 114
 115   // Emit the actual shift instruction. The difference is that this shift
 116   // instruction has a constant shift amount, which can be emitted inline
 117   // without a library call.
 118   Value *ValueShifted;
 119   switch (BI->getOpcode()) {
 120   case Instruction::Shl:
 121     ValueShifted = Builder.CreateShl(ValuePHI, ConstantInt::get(InputTy, 1));
 122     break;
 123   case Instruction::LShr:
 124     ValueShifted = Builder.CreateLShr(ValuePHI, ConstantInt::get(InputTy, 1));
 125     break;
 126   case Instruction::AShr:
 127     ValueShifted = Builder.CreateAShr(ValuePHI, ConstantInt::get(InputTy, 1));
 128     break;
 129   default:
 130     llvm_unreachable("asked to expand an instruction that is not a shift");
 131   }
 132   ValuePHI->addIncoming(ValueShifted, LoopBB);
 133
 134   // Branch to either the loop again (if there is more to shift) or to the
 135   // basic block after the loop (if all bits are shifted).
 136   Value *Cmp2 = Builder.CreateICmpEQ(ShiftAmountSub, Int8Zero);
 137   Builder.CreateCondBr(Cmp2, EndBB, LoopBB);
 138
 139   // Collect the resulting value. This is necessary in the IR but won't produce
 140   // any actual instructions.
 141   Builder.SetInsertPoint(BI);
 142   PHINode *Result = Builder.CreatePHI(InputTy, 2);
 143   Result->addIncoming(BI->getOperand(0), BB);
 144   Result->addIncoming(ValueShifted, LoopBB);
 145
 146   // Replace the original shift instruction.
 147   BI->replaceAllUsesWith(Result);
 148   BI->eraseFromParent();
 149 }