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