LLVM  11.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 "
94  "\"extract\" instructions", false, false)
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;
114  Match = match(In, m_And(m_Shl(m_AShr(m_Value(BF), m_ConstantInt(CSR)),
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);
131  Match = match(In, m_And(m_LShr(m_Value(BF), m_ConstantInt(CSR)),
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);
138  Match = match(In, m_And(m_AShr(m_Value(BF), m_ConstantInt(CSR)),
139  m_ConstantInt(CM)));
140  }
141  if (!Match) {
142  CM = nullptr;
143  // (shl (lshr x, #sr), #sl)
144  LogicalSR = true;
145  Match = match(In, m_Shl(m_LShr(m_Value(BF), m_ConstantInt(CSR)),
146  m_ConstantInt(CSL)));
147  }
148  if (!Match) {
149  CM = nullptr;
150  // (shl (ashr x, #sr), #sl)
151  LogicalSR = false;
152  Match = match(In, m_Shl(m_AShr(m_Value(BF), m_ConstantInt(CSR)),
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);
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  // Depth-first, bottom-up traversal.
225  for (auto *DTN : children<DomTreeNode*>(DT->getNode(B)))
226  visitBlock(DTN->getBlock());
227 
228  // Allow limiting the number of generated extracts for debugging purposes.
229  bool HasCutoff = ExtractCutoff.getPosition();
230  unsigned Cutoff = ExtractCutoff;
231 
232  bool Changed = false;
233  BasicBlock::iterator I = std::prev(B->end()), NextI, Begin = B->begin();
234  while (true) {
235  if (HasCutoff && (ExtractCount >= Cutoff))
236  return Changed;
237  bool Last = (I == Begin);
238  if (!Last)
239  NextI = std::prev(I);
240  Instruction *In = &*I;
241  bool Done = convert(In);
242  if (HasCutoff && Done)
243  ExtractCount++;
244  Changed |= Done;
245  if (Last)
246  break;
247  I = NextI;
248  }
249  return Changed;
250 }
251 
253  if (skipFunction(F))
254  return false;
255 
256  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
257  bool Changed;
258 
259  // Traverse the function bottom-up, to see super-expressions before their
260  // sub-expressions.
262  Changed = visitBlock(Entry);
263 
264  return Changed;
265 }
266 
268  return new HexagonGenExtract();
269 }
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
uint64_t CallInst * C
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:67
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
F(f)
void initializeHexagonGenExtractPass(PassRegistry &)
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:289
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
APInt getLoBits(unsigned numBits) const
Compute an APInt containing numBits lowbits from this APInt.
Definition: APInt.cpp:572
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:1011
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:198
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2324
This file implements a class to represent arbitrary precision integral constant values and operations...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:92
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:486
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
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:1139
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Get a value with high bits set.
Definition: APInt.h:654
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:434
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
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
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:113
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isMask(unsigned numBits) const
Definition: APInt.h:499
Represent the analysis usage information of a pass.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:997
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:305
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:989
static cl::opt< unsigned > ExtractCutoff("extract-cutoff", cl::init(~0U), cl::Hidden, cl::desc("Cutoff for generating \xtract\ " instructions"))
Iterator for intrusive lists based on ilist_node.
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
iterator end()
Definition: BasicBlock.h:291
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:418
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:786
INITIALIZE_PASS_BEGIN(HexagonGenExtract, "hextract", "Hexagon generate " "\xtract\instructions", false, false) INITIALIZE_PASS_END(HexagonGenExtract
The access may modify the value stored in memory.
unsigned countTrailingOnes() const
Count the number of trailing one bits.
Definition: APInt.h:1706
Class for arbitrary precision integers.
Definition: APInt.h:69
loop extract
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static cl::opt< bool > NeedAnd("extract-needand", cl::init(true), cl::Hidden, cl::desc("Require & in extract patterns"))
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
Definition: APInt.h:1343
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:186
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:270
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#define I(x, y, z)
Definition: MD5.cpp:59
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1255
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
LLVM Value Representation.
Definition: Value.h:74
FunctionPass * createHexagonGenExtract()
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
inst_range instructions(Function *F)
Definition: InstIterator.h:133
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:261
static cl::opt< bool > NoSR0("extract-nosr0", cl::init(true), cl::Hidden, cl::desc("No extract instruction with offset 0"))
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)