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