LLVM  12.0.0git
BypassSlowDivision.cpp
Go to the documentation of this file.
1 //===- BypassSlowDivision.cpp - Bypass slow division ----------------------===//
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 // This file contains an optimization for div and rem on architectures that
10 // execute short instructions significantly faster than longer instructions.
11 // For example, on Intel Atom 32-bit divides are slow enough that during
12 // runtime it is profitable to check the value of the operands, and if they are
13 // positive and less than 256 use an unsigned 8-bit divide.
14 //
15 //===----------------------------------------------------------------------===//
16 
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/None.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/IR/BasicBlock.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/Function.h"
29 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/Instruction.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/Module.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/IR/Value.h"
35 #include "llvm/Support/Casting.h"
36 #include "llvm/Support/KnownBits.h"
37 #include <cassert>
38 #include <cstdint>
39 
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "bypass-slow-division"
43 
44 namespace {
45 
46  struct QuotRemPair {
47  Value *Quotient;
48  Value *Remainder;
49 
50  QuotRemPair(Value *InQuotient, Value *InRemainder)
51  : Quotient(InQuotient), Remainder(InRemainder) {}
52  };
53 
54  /// A quotient and remainder, plus a BB from which they logically "originate".
55  /// If you use Quotient or Remainder in a Phi node, you should use BB as its
56  /// corresponding predecessor.
57  struct QuotRemWithBB {
58  BasicBlock *BB = nullptr;
59  Value *Quotient = nullptr;
60  Value *Remainder = nullptr;
61  };
62 
63 using DivCacheTy = DenseMap<DivRemMapKey, QuotRemPair>;
64 using BypassWidthsTy = DenseMap<unsigned, unsigned>;
65 using VisitedSetTy = SmallPtrSet<Instruction *, 4>;
66 
67 enum ValueRange {
68  /// Operand definitely fits into BypassType. No runtime checks are needed.
69  VALRNG_KNOWN_SHORT,
70  /// A runtime check is required, as value range is unknown.
71  VALRNG_UNKNOWN,
72  /// Operand is unlikely to fit into BypassType. The bypassing should be
73  /// disabled.
74  VALRNG_LIKELY_LONG
75 };
76 
77 class FastDivInsertionTask {
78  bool IsValidTask = false;
79  Instruction *SlowDivOrRem = nullptr;
80  IntegerType *BypassType = nullptr;
81  BasicBlock *MainBB = nullptr;
82 
83  bool isHashLikeValue(Value *V, VisitedSetTy &Visited);
84  ValueRange getValueRange(Value *Op, VisitedSetTy &Visited);
85  QuotRemWithBB createSlowBB(BasicBlock *Successor);
86  QuotRemWithBB createFastBB(BasicBlock *Successor);
87  QuotRemPair createDivRemPhiNodes(QuotRemWithBB &LHS, QuotRemWithBB &RHS,
88  BasicBlock *PhiBB);
89  Value *insertOperandRuntimeCheck(Value *Op1, Value *Op2);
90  Optional<QuotRemPair> insertFastDivAndRem();
91 
92  bool isSignedOp() {
93  return SlowDivOrRem->getOpcode() == Instruction::SDiv ||
94  SlowDivOrRem->getOpcode() == Instruction::SRem;
95  }
96 
97  bool isDivisionOp() {
98  return SlowDivOrRem->getOpcode() == Instruction::SDiv ||
99  SlowDivOrRem->getOpcode() == Instruction::UDiv;
100  }
101 
102  Type *getSlowType() { return SlowDivOrRem->getType(); }
103 
104 public:
105  FastDivInsertionTask(Instruction *I, const BypassWidthsTy &BypassWidths);
106 
107  Value *getReplacement(DivCacheTy &Cache);
108 };
109 
110 } // end anonymous namespace
111 
112 FastDivInsertionTask::FastDivInsertionTask(Instruction *I,
113  const BypassWidthsTy &BypassWidths) {
114  switch (I->getOpcode()) {
115  case Instruction::UDiv:
116  case Instruction::SDiv:
117  case Instruction::URem:
118  case Instruction::SRem:
119  SlowDivOrRem = I;
120  break;
121  default:
122  // I is not a div/rem operation.
123  return;
124  }
125 
126  // Skip division on vector types. Only optimize integer instructions.
127  IntegerType *SlowType = dyn_cast<IntegerType>(SlowDivOrRem->getType());
128  if (!SlowType)
129  return;
130 
131  // Skip if this bitwidth is not bypassed.
132  auto BI = BypassWidths.find(SlowType->getBitWidth());
133  if (BI == BypassWidths.end())
134  return;
135 
136  // Get type for div/rem instruction with bypass bitwidth.
137  IntegerType *BT = IntegerType::get(I->getContext(), BI->second);
138  BypassType = BT;
139 
140  // The original basic block.
141  MainBB = I->getParent();
142 
143  // The instruction is indeed a slow div or rem operation.
144  IsValidTask = true;
145 }
146 
147 /// Reuses previously-computed dividend or remainder from the current BB if
148 /// operands and operation are identical. Otherwise calls insertFastDivAndRem to
149 /// perform the optimization and caches the resulting dividend and remainder.
150 /// If no replacement can be generated, nullptr is returned.
151 Value *FastDivInsertionTask::getReplacement(DivCacheTy &Cache) {
152  // First, make sure that the task is valid.
153  if (!IsValidTask)
154  return nullptr;
155 
156  // Then, look for a value in Cache.
157  Value *Dividend = SlowDivOrRem->getOperand(0);
158  Value *Divisor = SlowDivOrRem->getOperand(1);
159  DivRemMapKey Key(isSignedOp(), Dividend, Divisor);
160  auto CacheI = Cache.find(Key);
161 
162  if (CacheI == Cache.end()) {
163  // If previous instance does not exist, try to insert fast div.
164  Optional<QuotRemPair> OptResult = insertFastDivAndRem();
165  // Bail out if insertFastDivAndRem has failed.
166  if (!OptResult)
167  return nullptr;
168  CacheI = Cache.insert({Key, *OptResult}).first;
169  }
170 
171  QuotRemPair &Value = CacheI->second;
172  return isDivisionOp() ? Value.Quotient : Value.Remainder;
173 }
174 
175 /// Check if a value looks like a hash.
176 ///
177 /// The routine is expected to detect values computed using the most common hash
178 /// algorithms. Typically, hash computations end with one of the following
179 /// instructions:
180 ///
181 /// 1) MUL with a constant wider than BypassType
182 /// 2) XOR instruction
183 ///
184 /// And even if we are wrong and the value is not a hash, it is still quite
185 /// unlikely that such values will fit into BypassType.
186 ///
187 /// To detect string hash algorithms like FNV we have to look through PHI-nodes.
188 /// It is implemented as a depth-first search for values that look neither long
189 /// nor hash-like.
190 bool FastDivInsertionTask::isHashLikeValue(Value *V, VisitedSetTy &Visited) {
192  if (!I)
193  return false;
194 
195  switch (I->getOpcode()) {
196  case Instruction::Xor:
197  return true;
198  case Instruction::Mul: {
199  // After Constant Hoisting pass, long constants may be represented as
200  // bitcast instructions. As a result, some constants may look like an
201  // instruction at first, and an additional check is necessary to find out if
202  // an operand is actually a constant.
203  Value *Op1 = I->getOperand(1);
205  if (!C && isa<BitCastInst>(Op1))
206  C = dyn_cast<ConstantInt>(cast<BitCastInst>(Op1)->getOperand(0));
207  return C && C->getValue().getMinSignedBits() > BypassType->getBitWidth();
208  }
209  case Instruction::PHI:
210  // Stop IR traversal in case of a crazy input code. This limits recursion
211  // depth.
212  if (Visited.size() >= 16)
213  return false;
214  // Do not visit nodes that have been visited already. We return true because
215  // it means that we couldn't find any value that doesn't look hash-like.
216  if (!Visited.insert(I).second)
217  return true;
218  return llvm::all_of(cast<PHINode>(I)->incoming_values(), [&](Value *V) {
219  // Ignore undef values as they probably don't affect the division
220  // operands.
221  return getValueRange(V, Visited) == VALRNG_LIKELY_LONG ||
222  isa<UndefValue>(V);
223  });
224  default:
225  return false;
226  }
227 }
228 
229 /// Check if an integer value fits into our bypass type.
230 ValueRange FastDivInsertionTask::getValueRange(Value *V,
231  VisitedSetTy &Visited) {
232  unsigned ShortLen = BypassType->getBitWidth();
233  unsigned LongLen = V->getType()->getIntegerBitWidth();
234 
235  assert(LongLen > ShortLen && "Value type must be wider than BypassType");
236  unsigned HiBits = LongLen - ShortLen;
237 
238  const DataLayout &DL = SlowDivOrRem->getModule()->getDataLayout();
239  KnownBits Known(LongLen);
240 
241  computeKnownBits(V, Known, DL);
242 
243  if (Known.countMinLeadingZeros() >= HiBits)
244  return VALRNG_KNOWN_SHORT;
245 
246  if (Known.countMaxLeadingZeros() < HiBits)
247  return VALRNG_LIKELY_LONG;
248 
249  // Long integer divisions are often used in hashtable implementations. It's
250  // not worth bypassing such divisions because hash values are extremely
251  // unlikely to have enough leading zeros. The call below tries to detect
252  // values that are unlikely to fit BypassType (including hashes).
253  if (isHashLikeValue(V, Visited))
254  return VALRNG_LIKELY_LONG;
255 
256  return VALRNG_UNKNOWN;
257 }
258 
259 /// Add new basic block for slow div and rem operations and put it before
260 /// SuccessorBB.
261 QuotRemWithBB FastDivInsertionTask::createSlowBB(BasicBlock *SuccessorBB) {
262  QuotRemWithBB DivRemPair;
263  DivRemPair.BB = BasicBlock::Create(MainBB->getParent()->getContext(), "",
264  MainBB->getParent(), SuccessorBB);
265  IRBuilder<> Builder(DivRemPair.BB, DivRemPair.BB->begin());
266  Builder.SetCurrentDebugLocation(SlowDivOrRem->getDebugLoc());
267 
268  Value *Dividend = SlowDivOrRem->getOperand(0);
269  Value *Divisor = SlowDivOrRem->getOperand(1);
270 
271  if (isSignedOp()) {
272  DivRemPair.Quotient = Builder.CreateSDiv(Dividend, Divisor);
273  DivRemPair.Remainder = Builder.CreateSRem(Dividend, Divisor);
274  } else {
275  DivRemPair.Quotient = Builder.CreateUDiv(Dividend, Divisor);
276  DivRemPair.Remainder = Builder.CreateURem(Dividend, Divisor);
277  }
278 
279  Builder.CreateBr(SuccessorBB);
280  return DivRemPair;
281 }
282 
283 /// Add new basic block for fast div and rem operations and put it before
284 /// SuccessorBB.
285 QuotRemWithBB FastDivInsertionTask::createFastBB(BasicBlock *SuccessorBB) {
286  QuotRemWithBB DivRemPair;
287  DivRemPair.BB = BasicBlock::Create(MainBB->getParent()->getContext(), "",
288  MainBB->getParent(), SuccessorBB);
289  IRBuilder<> Builder(DivRemPair.BB, DivRemPair.BB->begin());
290  Builder.SetCurrentDebugLocation(SlowDivOrRem->getDebugLoc());
291 
292  Value *Dividend = SlowDivOrRem->getOperand(0);
293  Value *Divisor = SlowDivOrRem->getOperand(1);
294  Value *ShortDivisorV =
295  Builder.CreateCast(Instruction::Trunc, Divisor, BypassType);
296  Value *ShortDividendV =
297  Builder.CreateCast(Instruction::Trunc, Dividend, BypassType);
298 
299  // udiv/urem because this optimization only handles positive numbers.
300  Value *ShortQV = Builder.CreateUDiv(ShortDividendV, ShortDivisorV);
301  Value *ShortRV = Builder.CreateURem(ShortDividendV, ShortDivisorV);
302  DivRemPair.Quotient =
303  Builder.CreateCast(Instruction::ZExt, ShortQV, getSlowType());
304  DivRemPair.Remainder =
305  Builder.CreateCast(Instruction::ZExt, ShortRV, getSlowType());
306  Builder.CreateBr(SuccessorBB);
307 
308  return DivRemPair;
309 }
310 
311 /// Creates Phi nodes for result of Div and Rem.
312 QuotRemPair FastDivInsertionTask::createDivRemPhiNodes(QuotRemWithBB &LHS,
313  QuotRemWithBB &RHS,
314  BasicBlock *PhiBB) {
315  IRBuilder<> Builder(PhiBB, PhiBB->begin());
316  Builder.SetCurrentDebugLocation(SlowDivOrRem->getDebugLoc());
317  PHINode *QuoPhi = Builder.CreatePHI(getSlowType(), 2);
318  QuoPhi->addIncoming(LHS.Quotient, LHS.BB);
319  QuoPhi->addIncoming(RHS.Quotient, RHS.BB);
320  PHINode *RemPhi = Builder.CreatePHI(getSlowType(), 2);
321  RemPhi->addIncoming(LHS.Remainder, LHS.BB);
322  RemPhi->addIncoming(RHS.Remainder, RHS.BB);
323  return QuotRemPair(QuoPhi, RemPhi);
324 }
325 
326 /// Creates a runtime check to test whether both the divisor and dividend fit
327 /// into BypassType. The check is inserted at the end of MainBB. True return
328 /// value means that the operands fit. Either of the operands may be NULL if it
329 /// doesn't need a runtime check.
330 Value *FastDivInsertionTask::insertOperandRuntimeCheck(Value *Op1, Value *Op2) {
331  assert((Op1 || Op2) && "Nothing to check");
332  IRBuilder<> Builder(MainBB, MainBB->end());
333  Builder.SetCurrentDebugLocation(SlowDivOrRem->getDebugLoc());
334 
335  Value *OrV;
336  if (Op1 && Op2)
337  OrV = Builder.CreateOr(Op1, Op2);
338  else
339  OrV = Op1 ? Op1 : Op2;
340 
341  // BitMask is inverted to check if the operands are
342  // larger than the bypass type
343  uint64_t BitMask = ~BypassType->getBitMask();
344  Value *AndV = Builder.CreateAnd(OrV, BitMask);
345 
346  // Compare operand values
347  Value *ZeroV = ConstantInt::getSigned(getSlowType(), 0);
348  return Builder.CreateICmpEQ(AndV, ZeroV);
349 }
350 
351 /// Substitutes the div/rem instruction with code that checks the value of the
352 /// operands and uses a shorter-faster div/rem instruction when possible.
353 Optional<QuotRemPair> FastDivInsertionTask::insertFastDivAndRem() {
354  Value *Dividend = SlowDivOrRem->getOperand(0);
355  Value *Divisor = SlowDivOrRem->getOperand(1);
356 
357  VisitedSetTy SetL;
358  ValueRange DividendRange = getValueRange(Dividend, SetL);
359  if (DividendRange == VALRNG_LIKELY_LONG)
360  return None;
361 
362  VisitedSetTy SetR;
363  ValueRange DivisorRange = getValueRange(Divisor, SetR);
364  if (DivisorRange == VALRNG_LIKELY_LONG)
365  return None;
366 
367  bool DividendShort = (DividendRange == VALRNG_KNOWN_SHORT);
368  bool DivisorShort = (DivisorRange == VALRNG_KNOWN_SHORT);
369 
370  if (DividendShort && DivisorShort) {
371  // If both operands are known to be short then just replace the long
372  // division with a short one in-place. Since we're not introducing control
373  // flow in this case, narrowing the division is always a win, even if the
374  // divisor is a constant (and will later get replaced by a multiplication).
375 
376  IRBuilder<> Builder(SlowDivOrRem);
377  Value *TruncDividend = Builder.CreateTrunc(Dividend, BypassType);
378  Value *TruncDivisor = Builder.CreateTrunc(Divisor, BypassType);
379  Value *TruncDiv = Builder.CreateUDiv(TruncDividend, TruncDivisor);
380  Value *TruncRem = Builder.CreateURem(TruncDividend, TruncDivisor);
381  Value *ExtDiv = Builder.CreateZExt(TruncDiv, getSlowType());
382  Value *ExtRem = Builder.CreateZExt(TruncRem, getSlowType());
383  return QuotRemPair(ExtDiv, ExtRem);
384  }
385 
386  if (isa<ConstantInt>(Divisor)) {
387  // If the divisor is not a constant, DAGCombiner will convert it to a
388  // multiplication by a magic constant. It isn't clear if it is worth
389  // introducing control flow to get a narrower multiply.
390  return None;
391  }
392 
393  // After Constant Hoisting pass, long constants may be represented as
394  // bitcast instructions. As a result, some constants may look like an
395  // instruction at first, and an additional check is necessary to find out if
396  // an operand is actually a constant.
397  if (auto *BCI = dyn_cast<BitCastInst>(Divisor))
398  if (BCI->getParent() == SlowDivOrRem->getParent() &&
399  isa<ConstantInt>(BCI->getOperand(0)))
400  return None;
401 
402  IRBuilder<> Builder(MainBB, MainBB->end());
403  Builder.SetCurrentDebugLocation(SlowDivOrRem->getDebugLoc());
404 
405  if (DividendShort && !isSignedOp()) {
406  // If the division is unsigned and Dividend is known to be short, then
407  // either
408  // 1) Divisor is less or equal to Dividend, and the result can be computed
409  // with a short division.
410  // 2) Divisor is greater than Dividend. In this case, no division is needed
411  // at all: The quotient is 0 and the remainder is equal to Dividend.
412  //
413  // So instead of checking at runtime whether Divisor fits into BypassType,
414  // we emit a runtime check to differentiate between these two cases. This
415  // lets us entirely avoid a long div.
416 
417  // Split the basic block before the div/rem.
418  BasicBlock *SuccessorBB = MainBB->splitBasicBlock(SlowDivOrRem);
419  // Remove the unconditional branch from MainBB to SuccessorBB.
420  MainBB->getInstList().back().eraseFromParent();
421  QuotRemWithBB Long;
422  Long.BB = MainBB;
423  Long.Quotient = ConstantInt::get(getSlowType(), 0);
424  Long.Remainder = Dividend;
425  QuotRemWithBB Fast = createFastBB(SuccessorBB);
426  QuotRemPair Result = createDivRemPhiNodes(Fast, Long, SuccessorBB);
427  Value *CmpV = Builder.CreateICmpUGE(Dividend, Divisor);
428  Builder.CreateCondBr(CmpV, Fast.BB, SuccessorBB);
429  return Result;
430  } else {
431  // General case. Create both slow and fast div/rem pairs and choose one of
432  // them at runtime.
433 
434  // Split the basic block before the div/rem.
435  BasicBlock *SuccessorBB = MainBB->splitBasicBlock(SlowDivOrRem);
436  // Remove the unconditional branch from MainBB to SuccessorBB.
437  MainBB->getInstList().back().eraseFromParent();
438  QuotRemWithBB Fast = createFastBB(SuccessorBB);
439  QuotRemWithBB Slow = createSlowBB(SuccessorBB);
440  QuotRemPair Result = createDivRemPhiNodes(Fast, Slow, SuccessorBB);
441  Value *CmpV = insertOperandRuntimeCheck(DividendShort ? nullptr : Dividend,
442  DivisorShort ? nullptr : Divisor);
443  Builder.CreateCondBr(CmpV, Fast.BB, Slow.BB);
444  return Result;
445  }
446 }
447 
448 /// This optimization identifies DIV/REM instructions in a BB that can be
449 /// profitably bypassed and carried out with a shorter, faster divide.
451  const BypassWidthsTy &BypassWidths) {
452  DivCacheTy PerBBDivCache;
453 
454  bool MadeChange = false;
455  Instruction *Next = &*BB->begin();
456  while (Next != nullptr) {
457  // We may add instructions immediately after I, but we want to skip over
458  // them.
459  Instruction *I = Next;
460  Next = Next->getNextNode();
461 
462  // Ignore dead code to save time and avoid bugs.
463  if (I->hasNUses(0))
464  continue;
465 
466  FastDivInsertionTask Task(I, BypassWidths);
467  if (Value *Replacement = Task.getReplacement(PerBBDivCache)) {
468  I->replaceAllUsesWith(Replacement);
469  I->eraseFromParent();
470  MadeChange = true;
471  }
472  }
473 
474  // Above we eagerly create divs and rems, as pairs, so that we can efficiently
475  // create divrem machine instructions. Now erase any unused divs / rems so we
476  // don't leave extra instructions sitting around.
477  for (auto &KV : PerBBDivCache)
478  for (Value *V : {KV.second.Quotient, KV.second.Remainder})
480 
481  return MadeChange;
482 }
uint64_t CallInst * C
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:80
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
LLVM_NODISCARD std::enable_if_t< !is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition: Casting.h:334
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
This class represents lattice values for constants.
Definition: AllocatorList.h:23
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:826
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1491
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:289
bool bypassSlowDivision(BasicBlock *BB, const DenseMap< unsigned int, unsigned int > &BypassWidth)
This optimization identifies DIV instructions in a BB that can be profitably bypassed and carried out...
Key
PAL metadata keys.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:131
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:486
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:71
Value * getOperand(unsigned i) const
Definition: User.h:169
bool hasNUses(unsigned N) const
Return true if this Value has exactly N users.
Definition: Value.cpp:142
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1954
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
Class to represent integer types.
Definition: DerivedTypes.h:40
assume Assume Builder
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1958
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:354
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:254
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
Definition: KnownBits.h:217
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
Value * CreateURem(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1249
Module.h This file contains the declarations for the Module class.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:455
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
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.cpp:800
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:102
BitTracker BT
Definition: BitTracker.cpp:73
#define I(x, y, z)
Definition: MD5.cpp:59
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:392
static int isSignedOp(ISD::CondCode Opcode)
For an integer comparison, return 1 if the comparison is a signed operation and 2 if the result is an...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getMinSignedBits() const
Get the minimum bit size for this signed APInt.
Definition: APInt.h:1612
LLVM Value Representation.
Definition: Value.h:74
Value * CreateUDiv(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1221
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:187
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:42
const BasicBlock * getParent() const
Definition: Instruction.h:94
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL