LLVM  9.0.0svn
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/PatternMatch.h"
21 #include "llvm/IR/Type.h"
22 #include "llvm/IR/Value.h"
23 #include "llvm/Pass.h"
25 #include <algorithm>
26 #include <cstdint>
27 #include <iterator>
28 
29 using namespace llvm;
30 
31 static cl::opt<unsigned> ExtractCutoff("extract-cutoff", cl::init(~0U),
32  cl::Hidden, cl::desc("Cutoff for generating \"extract\""
33  " instructions"));
34 
35 // This prevents generating extract instructions that have the offset of 0.
36 // One of the reasons for "extract" is to put a sequence of bits in a regis-
37 // ter, starting at offset 0 (so that these bits can then be used by an
38 // "insert"). If the bits are already at offset 0, it is better not to gene-
39 // rate "extract", since logical bit operations can be merged into compound
40 // instructions (as opposed to "extract").
41 static cl::opt<bool> NoSR0("extract-nosr0", cl::init(true), cl::Hidden,
42  cl::desc("No extract instruction with offset 0"));
43 
44 static cl::opt<bool> NeedAnd("extract-needand", cl::init(true), cl::Hidden,
45  cl::desc("Require & in extract patterns"));
46 
47 namespace llvm {
48 
51 
52 } // end namespace llvm
53 
54 namespace {
55 
56  class HexagonGenExtract : public FunctionPass {
57  public:
58  static char ID;
59 
60  HexagonGenExtract() : FunctionPass(ID) {
62  }
63 
64  StringRef getPassName() const override {
65  return "Hexagon generate \"extract\" instructions";
66  }
67 
68  bool runOnFunction(Function &F) override;
69 
70  void getAnalysisUsage(AnalysisUsage &AU) const override {
74  }
75 
76  private:
77  bool visitBlock(BasicBlock *B);
78  bool convert(Instruction *In);
79 
80  unsigned ExtractCount = 0;
81  DominatorTree *DT;
82  };
83 
84 } // end anonymous namespace
85 
86 char HexagonGenExtract::ID = 0;
87 
88 INITIALIZE_PASS_BEGIN(HexagonGenExtract, "hextract", "Hexagon generate "
89  "\"extract\" instructions", false, false)
91 INITIALIZE_PASS_END(HexagonGenExtract, "hextract", "Hexagon generate "
92  "\"extract\" instructions", false, false)
93 
94 bool HexagonGenExtract::convert(Instruction *In) {
95  using namespace PatternMatch;
96 
97  Value *BF = nullptr;
98  ConstantInt *CSL = nullptr, *CSR = nullptr, *CM = nullptr;
99  BasicBlock *BB = In->getParent();
100  LLVMContext &Ctx = BB->getContext();
101  bool LogicalSR;
102 
103  // (and (shl (lshr x, #sr), #sl), #m)
104  LogicalSR = true;
105  bool Match = match(In, m_And(m_Shl(m_LShr(m_Value(BF), m_ConstantInt(CSR)),
106  m_ConstantInt(CSL)),
107  m_ConstantInt(CM)));
108 
109  if (!Match) {
110  // (and (shl (ashr x, #sr), #sl), #m)
111  LogicalSR = false;
112  Match = match(In, m_And(m_Shl(m_AShr(m_Value(BF), m_ConstantInt(CSR)),
113  m_ConstantInt(CSL)),
114  m_ConstantInt(CM)));
115  }
116  if (!Match) {
117  // (and (shl x, #sl), #m)
118  LogicalSR = true;
119  CSR = ConstantInt::get(Type::getInt32Ty(Ctx), 0);
120  Match = match(In, m_And(m_Shl(m_Value(BF), m_ConstantInt(CSL)),
121  m_ConstantInt(CM)));
122  if (Match && NoSR0)
123  return false;
124  }
125  if (!Match) {
126  // (and (lshr x, #sr), #m)
127  LogicalSR = true;
128  CSL = ConstantInt::get(Type::getInt32Ty(Ctx), 0);
129  Match = match(In, m_And(m_LShr(m_Value(BF), m_ConstantInt(CSR)),
130  m_ConstantInt(CM)));
131  }
132  if (!Match) {
133  // (and (ashr x, #sr), #m)
134  LogicalSR = false;
135  CSL = ConstantInt::get(Type::getInt32Ty(Ctx), 0);
136  Match = match(In, m_And(m_AShr(m_Value(BF), m_ConstantInt(CSR)),
137  m_ConstantInt(CM)));
138  }
139  if (!Match) {
140  CM = nullptr;
141  // (shl (lshr x, #sr), #sl)
142  LogicalSR = true;
143  Match = match(In, m_Shl(m_LShr(m_Value(BF), m_ConstantInt(CSR)),
144  m_ConstantInt(CSL)));
145  }
146  if (!Match) {
147  CM = nullptr;
148  // (shl (ashr x, #sr), #sl)
149  LogicalSR = false;
150  Match = match(In, m_Shl(m_AShr(m_Value(BF), m_ConstantInt(CSR)),
151  m_ConstantInt(CSL)));
152  }
153  if (!Match)
154  return false;
155 
156  Type *Ty = BF->getType();
157  if (!Ty->isIntegerTy())
158  return false;
159  unsigned BW = Ty->getPrimitiveSizeInBits();
160  if (BW != 32 && BW != 64)
161  return false;
162 
163  uint32_t SR = CSR->getZExtValue();
164  uint32_t SL = CSL->getZExtValue();
165 
166  if (!CM) {
167  // If there was no and, and the shift left did not remove all potential
168  // sign bits created by the shift right, then extractu cannot reproduce
169  // this value.
170  if (!LogicalSR && (SR > SL))
171  return false;
172  APInt A = APInt(BW, ~0ULL).lshr(SR).shl(SL);
173  CM = ConstantInt::get(Ctx, A);
174  }
175 
176  // CM is the shifted-left mask. Shift it back right to remove the zero
177  // bits on least-significant positions.
178  APInt M = CM->getValue().lshr(SL);
180 
181  // During the shifts some of the bits will be lost. Calculate how many
182  // of the original value will remain after shift right and then left.
183  uint32_t U = BW - std::max(SL, SR);
184  // The width of the extracted field is the minimum of the original bits
185  // that remain after the shifts and the number of contiguous 1s in the mask.
186  uint32_t W = std::min(U, T);
187  if (W == 0)
188  return false;
189 
190  // Check if the extracted bits are contained within the mask that it is
191  // and-ed with. The extract operation will copy these bits, and so the
192  // mask cannot any holes in it that would clear any of the bits of the
193  // extracted field.
194  if (!LogicalSR) {
195  // If the shift right was arithmetic, it could have included some 1 bits.
196  // It is still ok to generate extract, but only if the mask eliminates
197  // those bits (i.e. M does not have any bits set beyond U).
198  APInt C = APInt::getHighBitsSet(BW, BW-U);
199  if (M.intersects(C) || !M.isMask(W))
200  return false;
201  } else {
202  // Check if M starts with a contiguous sequence of W times 1 bits. Get
203  // the low U bits of M (which eliminates the 0 bits shifted in on the
204  // left), and check if the result is APInt's "mask":
205  if (!M.getLoBits(U).isMask(W))
206  return false;
207  }
208 
209  IRBuilder<> IRB(In);
210  Intrinsic::ID IntId = (BW == 32) ? Intrinsic::hexagon_S2_extractu
211  : Intrinsic::hexagon_S2_extractup;
212  Module *Mod = BB->getParent()->getParent();
213  Value *ExtF = Intrinsic::getDeclaration(Mod, IntId);
214  Value *NewIn = IRB.CreateCall(ExtF, {BF, IRB.getInt32(W), IRB.getInt32(SR)});
215  if (SL != 0)
216  NewIn = IRB.CreateShl(NewIn, SL, CSL->getName());
217  In->replaceAllUsesWith(NewIn);
218  return true;
219 }
220 
221 bool HexagonGenExtract::visitBlock(BasicBlock *B) {
222  // Depth-first, bottom-up traversal.
223  for (auto *DTN : children<DomTreeNode*>(DT->getNode(B)))
224  visitBlock(DTN->getBlock());
225 
226  // Allow limiting the number of generated extracts for debugging purposes.
227  bool HasCutoff = ExtractCutoff.getPosition();
228  unsigned Cutoff = ExtractCutoff;
229 
230  bool Changed = false;
231  BasicBlock::iterator I = std::prev(B->end()), NextI, Begin = B->begin();
232  while (true) {
233  if (HasCutoff && (ExtractCount >= Cutoff))
234  return Changed;
235  bool Last = (I == Begin);
236  if (!Last)
237  NextI = std::prev(I);
238  Instruction *In = &*I;
239  bool Done = convert(In);
240  if (HasCutoff && Done)
241  ExtractCount++;
242  Changed |= Done;
243  if (Last)
244  break;
245  I = NextI;
246  }
247  return Changed;
248 }
249 
251  if (skipFunction(F))
252  return false;
253 
254  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
255  bool Changed;
256 
257  // Traverse the function bottom-up, to see super-expressions before their
258  // sub-expressions.
260  Changed = visitBlock(Entry);
261 
262  return Changed;
263 }
264 
266  return new HexagonGenExtract();
267 }
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:748
uint64_t CallInst * C
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
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...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
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:64
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:778
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:268
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
APInt getLoBits(unsigned numBits) const
Compute an APInt containing numBits lowbits from this APInt.
Definition: APInt.cpp:515
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:992
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:196
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:742
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:91
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:81
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
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:1019
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Get a value with high bits set.
Definition: APInt.h:635
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:422
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:772
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:148
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
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:494
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:766
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:970
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:83
iterator end()
Definition: BasicBlock.h:270
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:306
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:621
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:1645
Class for arbitrary precision integers.
Definition: APInt.h:69
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1102
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:1320
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:213
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1973
unsigned getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:114
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
LLVM Value Representation.
Definition: Value.h:72
FunctionPass * createHexagonGenExtract()
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
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:259
static cl::opt< bool > NoSR0("extract-nosr0", cl::init(true), cl::Hidden, cl::desc("No extract instruction with offset 0"))