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
23using namespace llvm;
24
25namespace {
26
27class AVRShiftExpandLegacy : public FunctionPass {
28public:
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
40char AVRShiftExpandLegacy::ID = 0;
41
42INITIALIZE_PASS(AVRShiftExpandLegacy, "avr-shift-expand", "AVR Shift Expansion",
43 false, false)
44
45Pass *llvm::createAVRShiftExpandLegacyPass() {
46 return new AVRShiftExpandLegacy();
47}
48
49static 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
123static 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
153bool AVRShiftExpandLegacy::runOnFunction(Function &F) {
154 return expandShiftsInFunction(F);
155}
156
157PreservedAnalyses AVRShiftExpandPass::run(Function &F,
158 FunctionAnalysisManager &FAM) {
159 return expandShiftsInFunction(F) ? PreservedAnalyses::none()
160 : PreservedAnalyses::all();
161}
162