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