LLVM  13.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) {
191  Instruction *I = dyn_cast<Instruction>(V);
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);
204  ConstantInt *C = dyn_cast<ConstantInt>(Op1);
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 }
llvm::RecursivelyDeleteTriviallyDeadInstructions
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:487
llvm::bypassSlowDivision
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...
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Optional.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:111
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
llvm::IRBuilder<>
ValueTracking.h
Local.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
DenseMap.h
Module.h
llvm::BasicBlock::splitBasicBlock
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:375
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet< Instruction *, 4 >
STLExtras.h
KnownBits.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Instruction.h
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:876
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::all_of
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:1498
Constants.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:471
llvm::BitTracker
Definition: BitTracker.h:35
isSignedOp
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...
Definition: SelectionDAG.cpp:484
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction
Definition: Instruction.h:45
SmallPtrSet.h
llvm::None
const NoneType None
Definition: None.h:23
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:96
Type.h
BasicBlock.h
BypassSlowDivision.h
llvm::CallingConv::Fast
@ Fast
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:42
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2720
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::computeKnownBits
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...
Definition: ValueTracking.cpp:238
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:643
None.h
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::KnownBits
Definition: KnownBits.h:23
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:33
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:302
llvm::ConstantInt::getSigned
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.cpp:890
Casting.h
Function.h
llvm::pdb::PDB_BuiltinType::Long
@ Long
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:363
Instructions.h
BT
BitTracker BT
Definition: BitTracker.cpp:73
llvm::DivRemMapKey
Definition: BypassSlowDivision.h:30
llvm::IntegerType::getBitWidth
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:71
llvm::PHINode
Definition: Instructions.h:2572
DerivedTypes.h
llvm::IntegerType::get
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:269
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
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75