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