LLVM  14.0.0git
HexagonGenExtract.cpp
Go to the documentation of this file.
1 //===- HexagonGenExtract.cpp ----------------------------------------------===//
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 #include "llvm/ADT/APInt.h"
10 #include "llvm/ADT/GraphTraits.h"
11 #include "llvm/IR/BasicBlock.h"
12 #include "llvm/IR/CFG.h"
13 #include "llvm/IR/Constants.h"
14 #include "llvm/IR/Dominators.h"
15 #include "llvm/IR/Function.h"
16 #include "llvm/IR/IRBuilder.h"
17 #include "llvm/IR/Instruction.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/IR/Intrinsics.h"
20 #include "llvm/IR/IntrinsicsHexagon.h"
21 #include "llvm/IR/PatternMatch.h"
22 #include "llvm/IR/Type.h"
23 #include "llvm/IR/Value.h"
24 #include "llvm/InitializePasses.h"
25 #include "llvm/Pass.h"
27 #include <algorithm>
28 #include <cstdint>
29 #include <iterator>
30 
31 using namespace llvm;
32 
33 static cl::opt<unsigned> ExtractCutoff("extract-cutoff", cl::init(~0U),
34  cl::Hidden, cl::desc("Cutoff for generating \"extract\""
35  " instructions"));
36 
37 // This prevents generating extract instructions that have the offset of 0.
38 // One of the reasons for "extract" is to put a sequence of bits in a regis-
39 // ter, starting at offset 0 (so that these bits can then be used by an
40 // "insert"). If the bits are already at offset 0, it is better not to gene-
41 // rate "extract", since logical bit operations can be merged into compound
42 // instructions (as opposed to "extract").
43 static cl::opt<bool> NoSR0("extract-nosr0", cl::init(true), cl::Hidden,
44  cl::desc("No extract instruction with offset 0"));
45 
46 static cl::opt<bool> NeedAnd("extract-needand", cl::init(true), cl::Hidden,
47  cl::desc("Require & in extract patterns"));
48 
49 namespace llvm {
50 
53 
54 } // end namespace llvm
55 
56 namespace {
57 
58  class HexagonGenExtract : public FunctionPass {
59  public:
60  static char ID;
61 
62  HexagonGenExtract() : FunctionPass(ID) {
64  }
65 
66  StringRef getPassName() const override {
67  return "Hexagon generate \"extract\" instructions";
68  }
69 
70  bool runOnFunction(Function &F) override;
71 
72  void getAnalysisUsage(AnalysisUsage &AU) const override {
76  }
77 
78  private:
79  bool visitBlock(BasicBlock *B);
80  bool convert(Instruction *In);
81 
82  unsigned ExtractCount = 0;
83  DominatorTree *DT;
84  };
85 
86 } // end anonymous namespace
87 
88 char HexagonGenExtract::ID = 0;
89 
90 INITIALIZE_PASS_BEGIN(HexagonGenExtract, "hextract", "Hexagon generate "
91  "\"extract\" instructions", false, false)
93 INITIALIZE_PASS_END(HexagonGenExtract, "hextract", "Hexagon generate "
95 
96 bool HexagonGenExtract::convert(Instruction *In) {
97  using namespace PatternMatch;
98 
99  Value *BF = nullptr;
100  ConstantInt *CSL = nullptr, *CSR = nullptr, *CM = nullptr;
101  BasicBlock *BB = In->getParent();
102  LLVMContext &Ctx = BB->getContext();
103  bool LogicalSR;
104 
105  // (and (shl (lshr x, #sr), #sl), #m)
106  LogicalSR = true;
107  bool Match = match(In, m_And(m_Shl(m_LShr(m_Value(BF), m_ConstantInt(CSR)),
108  m_ConstantInt(CSL)),
109  m_ConstantInt(CM)));
110 
111  if (!Match) {
112  // (and (shl (ashr x, #sr), #sl), #m)
113  LogicalSR = false;
115  m_ConstantInt(CSL)),
116  m_ConstantInt(CM)));
117  }
118  if (!Match) {
119  // (and (shl x, #sl), #m)
120  LogicalSR = true;
121  CSR = ConstantInt::get(Type::getInt32Ty(Ctx), 0);
122  Match = match(In, m_And(m_Shl(m_Value(BF), m_ConstantInt(CSL)),
123  m_ConstantInt(CM)));
124  if (Match && NoSR0)
125  return false;
126  }
127  if (!Match) {
128  // (and (lshr x, #sr), #m)
129  LogicalSR = true;
130  CSL = ConstantInt::get(Type::getInt32Ty(Ctx), 0);
132  m_ConstantInt(CM)));
133  }
134  if (!Match) {
135  // (and (ashr x, #sr), #m)
136  LogicalSR = false;
137  CSL = ConstantInt::get(Type::getInt32Ty(Ctx), 0);
139  m_ConstantInt(CM)));
140  }
141  if (!Match) {
142  CM = nullptr;
143  // (shl (lshr x, #sr), #sl)
144  LogicalSR = true;
146  m_ConstantInt(CSL)));
147  }
148  if (!Match) {
149  CM = nullptr;
150  // (shl (ashr x, #sr), #sl)
151  LogicalSR = false;
153  m_ConstantInt(CSL)));
154  }
155  if (!Match)
156  return false;
157 
158  Type *Ty = BF->getType();
159  if (!Ty->isIntegerTy())
160  return false;
161  unsigned BW = Ty->getPrimitiveSizeInBits();
162  if (BW != 32 && BW != 64)
163  return false;
164 
165  uint32_t SR = CSR->getZExtValue();
166  uint32_t SL = CSL->getZExtValue();
167 
168  if (!CM) {
169  // If there was no and, and the shift left did not remove all potential
170  // sign bits created by the shift right, then extractu cannot reproduce
171  // this value.
172  if (!LogicalSR && (SR > SL))
173  return false;
174  APInt A = APInt(BW, ~0ULL).lshr(SR).shl(SL);
175  CM = ConstantInt::get(Ctx, A);
176  }
177 
178  // CM is the shifted-left mask. Shift it back right to remove the zero
179  // bits on least-significant positions.
180  APInt M = CM->getValue().lshr(SL);
181  uint32_t T = M.countTrailingOnes();
182 
183  // During the shifts some of the bits will be lost. Calculate how many
184  // of the original value will remain after shift right and then left.
185  uint32_t U = BW - std::max(SL, SR);
186  // The width of the extracted field is the minimum of the original bits
187  // that remain after the shifts and the number of contiguous 1s in the mask.
188  uint32_t W = std::min(U, T);
189  if (W == 0 || W == 1)
190  return false;
191 
192  // Check if the extracted bits are contained within the mask that it is
193  // and-ed with. The extract operation will copy these bits, and so the
194  // mask cannot any holes in it that would clear any of the bits of the
195  // extracted field.
196  if (!LogicalSR) {
197  // If the shift right was arithmetic, it could have included some 1 bits.
198  // It is still ok to generate extract, but only if the mask eliminates
199  // those bits (i.e. M does not have any bits set beyond U).
200  APInt C = APInt::getHighBitsSet(BW, BW-U);
201  if (M.intersects(C) || !M.isMask(W))
202  return false;
203  } else {
204  // Check if M starts with a contiguous sequence of W times 1 bits. Get
205  // the low U bits of M (which eliminates the 0 bits shifted in on the
206  // left), and check if the result is APInt's "mask":
207  if (!M.getLoBits(U).isMask(W))
208  return false;
209  }
210 
211  IRBuilder<> IRB(In);
212  Intrinsic::ID IntId = (BW == 32) ? Intrinsic::hexagon_S2_extractu
213  : Intrinsic::hexagon_S2_extractup;
214  Module *Mod = BB->getParent()->getParent();
215  Function *ExtF = Intrinsic::getDeclaration(Mod, IntId);
216  Value *NewIn = IRB.CreateCall(ExtF, {BF, IRB.getInt32(W), IRB.getInt32(SR)});
217  if (SL != 0)
218  NewIn = IRB.CreateShl(NewIn, SL, CSL->getName());
219  In->replaceAllUsesWith(NewIn);
220  return true;
221 }
222 
223 bool HexagonGenExtract::visitBlock(BasicBlock *B) {
224  bool Changed = false;
225 
226  // Depth-first, bottom-up traversal.
227  for (auto *DTN : children<DomTreeNode*>(DT->getNode(B)))
228  Changed |= visitBlock(DTN->getBlock());
229 
230  // Allow limiting the number of generated extracts for debugging purposes.
231  bool HasCutoff = ExtractCutoff.getPosition();
232  unsigned Cutoff = ExtractCutoff;
233 
234  BasicBlock::iterator I = std::prev(B->end()), NextI, Begin = B->begin();
235  while (true) {
236  if (HasCutoff && (ExtractCount >= Cutoff))
237  return Changed;
238  bool Last = (I == Begin);
239  if (!Last)
240  NextI = std::prev(I);
241  Instruction *In = &*I;
242  bool Done = convert(In);
243  if (HasCutoff && Done)
244  ExtractCount++;
245  Changed |= Done;
246  if (Last)
247  break;
248  I = NextI;
249  }
250  return Changed;
251 }
252 
254  if (skipFunction(F))
255  return false;
256 
257  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
258  bool Changed;
259 
260  // Traverse the function bottom-up, to see super-expressions before their
261  // sub-expressions.
263  Changed = visitBlock(Entry);
264 
265  return Changed;
266 }
267 
269  return new HexagonGenExtract();
270 }
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
NoSR0
static cl::opt< bool > NoSR0("extract-nosr0", cl::init(true), cl::Hidden, cl::desc("No extract instruction with offset 0"))
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
ExtractCutoff
static cl::opt< unsigned > ExtractCutoff("extract-cutoff", cl::init(~0U), cl::Hidden, cl::desc("Cutoff for generating \"extract\"" " instructions"))
llvm::Intrinsic::getDeclaration
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1379
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
T
llvm::Function
Definition: Function.h:62
Pass.h
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1147
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:199
llvm::IRBuilder<>
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
APInt.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::PatternMatch::m_AShr
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1153
llvm::DiagnosticPredicateTy::Match
@ Match
llvm::APInt::lshr
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:804
llvm::createHexagonGenExtract
FunctionPass * createHexagonGenExtract()
Definition: HexagonGenExtract.cpp:268
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:241
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
GraphTraits.h
Instruction.h
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::PatternMatch::m_ConstantInt
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:145
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::PassRegistry
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
hextract
hextract
Definition: HexagonGenExtract.cpp:93
llvm::APInt::getHighBitsSet
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
Definition: APInt.h:279
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:925
PatternMatch.h
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:190
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(HexagonGenExtract, "hextract", "Hexagon generate " "\"extract\" instructions", false, false) INITIALIZE_PASS_END(HexagonGenExtract
llvm::tgtok::In
@ In
Definition: TGLexer.h:51
BasicBlock.h
llvm::cl::opt
Definition: CommandLine.h:1432
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::IRBuilderBase::getInt32
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:478
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1123
IRBuilder.h
llvm::IndexedInstrProf::HashT::Last
@ Last
extract
loop extract
Definition: LoopExtractor.cpp:97
llvm::initializeHexagonGenExtractPass
void initializeHexagonGenExtractPass(PassRegistry &)
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
uint32_t
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::ConstantInt::getZExtValue
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:142
NeedAnd
static cl::opt< bool > NeedAnd("extract-needand", cl::init(true), cl::Hidden, cl::desc("Require & in extract patterns"))
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
Function.h
Instructions.h
Dominators.h
llvm::IRBuilderBase::CreateShl
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1301
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
generate
We currently generate
Definition: README.txt:597
llvm::Pass::getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::APInt::shl
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:826
llvm::cl::desc
Definition: CommandLine.h:412
Mod
Module * Mod
Definition: PassBuilderBindings.cpp:54
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::PatternMatch::m_Shl
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1141
llvm::IRBuilderBase::CreateCall
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2395
llvm::Type::getPrimitiveSizeInBits
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:166
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37