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 } 148