LLVM  14.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 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 
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 
76  auto &Ctx = BI->getContext();
77  IRBuilder<> Builder(BI);
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 }
Int32Ty
IntegerType * Int32Ty
Definition: NVVMIntrRange.cpp:67
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
InstIterator.h
llvm::Function
Definition: Function.h:61
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::IRBuilder<>
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:201
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:203
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:393
llvm::Instruction
Definition: Instruction.h:45
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:900
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
expand
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:27
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2775
I
#define I(x, y, z)
Definition: MD5.cpp:59
IRBuilder.h
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::BinaryOperator
Definition: InstrTypes.h:189
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:520
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:978
INITIALIZE_PASS
INITIALIZE_PASS(AVRShiftExpand, "avr-shift-expand", "AVR Shift Expansion", false, false) Pass *llvm
Definition: AVRShiftExpand.cpp:42
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
AVR.h
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::PHINode
Definition: Instructions.h:2625
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::createAVRShiftExpandPass
Pass * createAVRShiftExpandPass()
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37