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