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