LLVM 19.0.0git
AVRShiftExpand.cpp
Go to the documentation of this file.
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"
20
21using namespace llvm;
22
23namespace {
24
25class AVRShiftExpand : public FunctionPass {
26public:
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
35private:
36 void expand(BinaryOperator *BI);
37};
38
39} // end of anonymous namespace
40
41char AVRShiftExpand::ID = 0;
42
43INITIALIZE_PASS(AVRShiftExpand, "avr-shift-expand", "AVR Shift Expansion",
44 false, false)
45
46Pass *llvm::createAVRShiftExpandPass() { return new AVRShiftExpand(); }
47
48bool AVRShiftExpand::runOnFunction(Function &F) {
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
77void 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}
Expand Atomic instructions
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:21
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:198
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:559
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:205
const Instruction & back() const
Definition: BasicBlock.h:454
BinaryOps getOpcode() const
Definition: InstrTypes.h:486
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2644
const BasicBlock * getParent() const
Definition: Instruction.h:152
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static IntegerType * getInt16Ty(LLVMContext &C)
static IntegerType * getInt8Ty(LLVMContext &C)
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1074
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Pass * createAVRShiftExpandPass()