LLVM  13.0.0git
InstCombiner.h
Go to the documentation of this file.
1 //===- InstCombiner.h - InstCombine implementation --------------*- C++ -*-===//
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 /// \file
9 ///
10 /// This file provides the interface for the instcombine pass implementation.
11 /// The interface is used for generic transformations in this folder and
12 /// target specific combinations in the targets.
13 /// The visitor implementation is in \c InstCombinerImpl in
14 /// \c InstCombineInternal.h.
15 ///
16 //===----------------------------------------------------------------------===//
17 
18 #ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H
19 #define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H
20 
24 #include "llvm/IR/IRBuilder.h"
25 #include "llvm/IR/PatternMatch.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/KnownBits.h"
29 #include <cassert>
30 
31 #define DEBUG_TYPE "instcombine"
32 
33 namespace llvm {
34 
35 class AAResults;
36 class AssumptionCache;
37 class ProfileSummaryInfo;
38 class TargetLibraryInfo;
39 class TargetTransformInfo;
40 
41 /// The core instruction combiner logic.
42 ///
43 /// This class provides both the logic to recursively visit instructions and
44 /// combine them.
46  /// Only used to call target specific inst combining.
48 
49 public:
50  /// Maximum size of array considered when transforming.
51  uint64_t MaxArraySizeForCombine = 0;
52 
53  /// An IRBuilder that automatically inserts new instructions into the
54  /// worklist.
57 
58 protected:
59  /// A worklist of the instructions that need to be simplified.
61 
62  // Mode in which we are running the combiner.
63  const bool MinimizeSize;
64 
66 
67  // Required analyses.
71  const DataLayout &DL;
76 
77  // Optional analyses. When non-null, these can both be used to do better
78  // combining and will be updated to reflect any changes.
80 
81  bool MadeIRChange = false;
82 
83 public:
85  bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
89  const DataLayout &DL, LoopInfo *LI)
90  : TTI(TTI), Builder(Builder), Worklist(Worklist),
91  MinimizeSize(MinimizeSize), AA(AA), AC(AC), TLI(TLI), DT(DT), DL(DL),
92  SQ(DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {}
93 
94  virtual ~InstCombiner() {}
95 
96  /// Return the source operand of a potentially bitcasted value while
97  /// optionally checking if it has one use. If there is no bitcast or the one
98  /// use check is not met, return the input value itself.
99  static Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) {
100  if (auto *BitCast = dyn_cast<BitCastInst>(V))
101  if (!OneUseOnly || BitCast->hasOneUse())
102  return BitCast->getOperand(0);
103 
104  // V is not a bitcast or V has more than one use and OneUseOnly is true.
105  return V;
106  }
107 
108  /// Assign a complexity or rank value to LLVM Values. This is used to reduce
109  /// the amount of pattern matching needed for compares and commutative
110  /// instructions. For example, if we have:
111  /// icmp ugt X, Constant
112  /// or
113  /// xor (add X, Constant), cast Z
114  ///
115  /// We do not have to consider the commuted variants of these patterns because
116  /// canonicalization based on complexity guarantees the above ordering.
117  ///
118  /// This routine maps IR values to various complexity ranks:
119  /// 0 -> undef
120  /// 1 -> Constants
121  /// 2 -> Other non-instructions
122  /// 3 -> Arguments
123  /// 4 -> Cast and (f)neg/not instructions
124  /// 5 -> Other instructions
125  static unsigned getComplexity(Value *V) {
126  if (isa<Instruction>(V)) {
127  if (isa<CastInst>(V) || match(V, m_Neg(PatternMatch::m_Value())) ||
130  return 4;
131  return 5;
132  }
133  if (isa<Argument>(V))
134  return 3;
135  return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
136  }
137 
138  /// Predicate canonicalization reduces the number of patterns that need to be
139  /// matched by other transforms. For example, we may swap the operands of a
140  /// conditional branch or select to create a compare with a canonical
141  /// (inverted) predicate which is then more likely to be matched with other
142  /// values.
144  switch (Pred) {
145  case CmpInst::ICMP_NE:
146  case CmpInst::ICMP_ULE:
147  case CmpInst::ICMP_SLE:
148  case CmpInst::ICMP_UGE:
149  case CmpInst::ICMP_SGE:
150  // TODO: There are 16 FCMP predicates. Should others be (not) canonical?
151  case CmpInst::FCMP_ONE:
152  case CmpInst::FCMP_OLE:
153  case CmpInst::FCMP_OGE:
154  return false;
155  default:
156  return true;
157  }
158  }
159 
160  /// Given an exploded icmp instruction, return true if the comparison only
161  /// checks the sign bit. If it only checks the sign bit, set TrueIfSigned if
162  /// the result of the comparison is true when the input value is signed.
163  static bool isSignBitCheck(ICmpInst::Predicate Pred, const APInt &RHS,
164  bool &TrueIfSigned) {
165  switch (Pred) {
166  case ICmpInst::ICMP_SLT: // True if LHS s< 0
167  TrueIfSigned = true;
168  return RHS.isNullValue();
169  case ICmpInst::ICMP_SLE: // True if LHS s<= -1
170  TrueIfSigned = true;
171  return RHS.isAllOnesValue();
172  case ICmpInst::ICMP_SGT: // True if LHS s> -1
173  TrueIfSigned = false;
174  return RHS.isAllOnesValue();
175  case ICmpInst::ICMP_SGE: // True if LHS s>= 0
176  TrueIfSigned = false;
177  return RHS.isNullValue();
178  case ICmpInst::ICMP_UGT:
179  // True if LHS u> RHS and RHS == sign-bit-mask - 1
180  TrueIfSigned = true;
181  return RHS.isMaxSignedValue();
182  case ICmpInst::ICMP_UGE:
183  // True if LHS u>= RHS and RHS == sign-bit-mask (2^7, 2^15, 2^31, etc)
184  TrueIfSigned = true;
185  return RHS.isMinSignedValue();
186  case ICmpInst::ICMP_ULT:
187  // True if LHS u< RHS and RHS == sign-bit-mask (2^7, 2^15, 2^31, etc)
188  TrueIfSigned = false;
189  return RHS.isMinSignedValue();
190  case ICmpInst::ICMP_ULE:
191  // True if LHS u<= RHS and RHS == sign-bit-mask - 1
192  TrueIfSigned = false;
193  return RHS.isMaxSignedValue();
194  default:
195  return false;
196  }
197  }
198 
199  /// Add one to a Constant
200  static Constant *AddOne(Constant *C) {
201  return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
202  }
203 
204  /// Subtract one from a Constant
205  static Constant *SubOne(Constant *C) {
206  return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
207  }
208 
209  llvm::Optional<std::pair<
211  Constant *>> static getFlippedStrictnessPredicateAndConstant(CmpInst::
212  Predicate
213  Pred,
214  Constant *C);
215 
217  // a ? b : false and a ? true : b are the canonical form of logical and/or.
218  // This includes !a ? b : false and !a ? true : b. Absorbing the not into
219  // the select by swapping operands would break recognition of this pattern
220  // in other analyses, so don't do that.
222  PatternMatch::m_Value())) ||
225  }
226 
227  /// Return true if the specified value is free to invert (apply ~ to).
228  /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses
229  /// is true, work under the assumption that the caller intends to remove all
230  /// uses of V and only keep uses of ~V.
231  ///
232  /// See also: canFreelyInvertAllUsersOf()
233  static bool isFreeToInvert(Value *V, bool WillInvertAllUses) {
234  // ~(~(X)) -> X.
235  if (match(V, m_Not(PatternMatch::m_Value())))
236  return true;
237 
238  // Constants can be considered to be not'ed values.
240  return true;
241 
242  // Compares can be inverted if all of their uses are being modified to use
243  // the ~V.
244  if (isa<CmpInst>(V))
245  return WillInvertAllUses;
246 
247  // If `V` is of the form `A + Constant` then `-1 - V` can be folded into
248  // `(-1 - Constant) - A` if we are willing to invert all of the uses.
249  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
250  if (BO->getOpcode() == Instruction::Add ||
251  BO->getOpcode() == Instruction::Sub)
252  if (isa<Constant>(BO->getOperand(0)) ||
253  isa<Constant>(BO->getOperand(1)))
254  return WillInvertAllUses;
255 
256  // Selects with invertible operands are freely invertible
257  if (match(V,
260  return WillInvertAllUses;
261 
262  return false;
263  }
264 
265  /// Given i1 V, can every user of V be freely adapted if V is changed to !V ?
266  /// InstCombine's freelyInvertAllUsersOf() must be kept in sync with this fn.
267  ///
268  /// See also: isFreeToInvert()
269  static bool canFreelyInvertAllUsersOf(Value *V, Value *IgnoredUser) {
270  // Look at every user of V.
271  for (Use &U : V->uses()) {
272  if (U.getUser() == IgnoredUser)
273  continue; // Don't consider this user.
274 
275  auto *I = cast<Instruction>(U.getUser());
276  switch (I->getOpcode()) {
277  case Instruction::Select:
278  if (U.getOperandNo() != 0) // Only if the value is used as select cond.
279  return false;
280  if (shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(I)))
281  return false;
282  break;
283  case Instruction::Br:
284  assert(U.getOperandNo() == 0 && "Must be branching on that value.");
285  break; // Free to invert by swapping true/false values/destinations.
286  case Instruction::Xor: // Can invert 'xor' if it's a 'not', by ignoring
287  // it.
289  return false; // Not a 'not'.
290  break;
291  default:
292  return false; // Don't know, likely not freely invertible.
293  }
294  // So far all users were free to invert...
295  }
296  return true; // Can freely invert all users!
297  }
298 
299  /// Some binary operators require special handling to avoid poison and
300  /// undefined behavior. If a constant vector has undef elements, replace those
301  /// undefs with identity constants if possible because those are always safe
302  /// to execute. If no identity constant exists, replace undef with some other
303  /// safe constant.
304  static Constant *
306  bool IsRHSConstant) {
307  auto *InVTy = cast<FixedVectorType>(In->getType());
308 
309  Type *EltTy = InVTy->getElementType();
310  auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant);
311  if (!SafeC) {
312  // TODO: Should this be available as a constant utility function? It is
313  // similar to getBinOpAbsorber().
314  if (IsRHSConstant) {
315  switch (Opcode) {
316  case Instruction::SRem: // X % 1 = 0
317  case Instruction::URem: // X %u 1 = 0
318  SafeC = ConstantInt::get(EltTy, 1);
319  break;
320  case Instruction::FRem: // X % 1.0 (doesn't simplify, but it is safe)
321  SafeC = ConstantFP::get(EltTy, 1.0);
322  break;
323  default:
325  "Only rem opcodes have no identity constant for RHS");
326  }
327  } else {
328  switch (Opcode) {
329  case Instruction::Shl: // 0 << X = 0
330  case Instruction::LShr: // 0 >>u X = 0
331  case Instruction::AShr: // 0 >> X = 0
332  case Instruction::SDiv: // 0 / X = 0
333  case Instruction::UDiv: // 0 /u X = 0
334  case Instruction::SRem: // 0 % X = 0
335  case Instruction::URem: // 0 %u X = 0
336  case Instruction::Sub: // 0 - X (doesn't simplify, but it is safe)
337  case Instruction::FSub: // 0.0 - X (doesn't simplify, but it is safe)
338  case Instruction::FDiv: // 0.0 / X (doesn't simplify, but it is safe)
339  case Instruction::FRem: // 0.0 % X = 0
340  SafeC = Constant::getNullValue(EltTy);
341  break;
342  default:
343  llvm_unreachable("Expected to find identity constant for opcode");
344  }
345  }
346  }
347  assert(SafeC && "Must have safe constant for binop");
348  unsigned NumElts = InVTy->getNumElements();
349  SmallVector<Constant *, 16> Out(NumElts);
350  for (unsigned i = 0; i != NumElts; ++i) {
351  Constant *C = In->getAggregateElement(i);
352  Out[i] = isa<UndefValue>(C) ? SafeC : C;
353  }
354  return ConstantVector::get(Out);
355  }
356 
357  /// Create and insert the idiom we use to indicate a block is unreachable
358  /// without having to rewrite the CFG from within InstCombine.
360  auto &Ctx = InsertAt->getContext();
362  UndefValue::get(Type::getInt1PtrTy(Ctx)), InsertAt);
363  }
364 
365  void addToWorklist(Instruction *I) { Worklist.push(I); }
366 
367  AssumptionCache &getAssumptionCache() const { return AC; }
368  TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; }
369  DominatorTree &getDominatorTree() const { return DT; }
370  const DataLayout &getDataLayout() const { return DL; }
371  const SimplifyQuery &getSimplifyQuery() const { return SQ; }
373  return ORE;
374  }
376  ProfileSummaryInfo *getProfileSummaryInfo() const { return PSI; }
377  LoopInfo *getLoopInfo() const { return LI; }
378 
379  // Call target specific combiners
380  Optional<Instruction *> targetInstCombineIntrinsic(IntrinsicInst &II);
382  targetSimplifyDemandedUseBitsIntrinsic(IntrinsicInst &II, APInt DemandedMask,
383  KnownBits &Known,
384  bool &KnownBitsComputed);
385  Optional<Value *> targetSimplifyDemandedVectorEltsIntrinsic(
386  IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts,
387  APInt &UndefElts2, APInt &UndefElts3,
388  std::function<void(Instruction *, unsigned, APInt, APInt &)>
389  SimplifyAndSetOp);
390 
391  /// Inserts an instruction \p New before instruction \p Old
392  ///
393  /// Also adds the new instruction to the worklist and returns \p New so that
394  /// it is suitable for use as the return from the visitation patterns.
396  assert(New && !New->getParent() &&
397  "New instruction already inserted into a basic block!");
398  BasicBlock *BB = Old.getParent();
399  BB->getInstList().insert(Old.getIterator(), New); // Insert inst
400  Worklist.push(New);
401  return New;
402  }
403 
404  /// Same as InsertNewInstBefore, but also sets the debug loc.
406  New->setDebugLoc(Old.getDebugLoc());
407  return InsertNewInstBefore(New, Old);
408  }
409 
410  /// A combiner-aware RAUW-like routine.
411  ///
412  /// This method is to be used when an instruction is found to be dead,
413  /// replaceable with another preexisting expression. Here we add all uses of
414  /// I to the worklist, replace all uses of I with the new value, then return
415  /// I, so that the inst combiner will know that I was modified.
417  // If there are no uses to replace, then we return nullptr to indicate that
418  // no changes were made to the program.
419  if (I.use_empty())
420  return nullptr;
421 
422  Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist.
423 
424  // If we are replacing the instruction with itself, this must be in a
425  // segment of unreachable code, so just clobber the instruction.
426  if (&I == V)
427  V = UndefValue::get(I.getType());
428 
429  LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
430  << " with " << *V << '\n');
431 
432  I.replaceAllUsesWith(V);
433  return &I;
434  }
435 
436  /// Replace operand of instruction and add old operand to the worklist.
437  Instruction *replaceOperand(Instruction &I, unsigned OpNum, Value *V) {
438  Worklist.addValue(I.getOperand(OpNum));
439  I.setOperand(OpNum, V);
440  return &I;
441  }
442 
443  /// Replace use and add the previously used value to the worklist.
444  void replaceUse(Use &U, Value *NewValue) {
445  Worklist.addValue(U);
446  U = NewValue;
447  }
448 
449  /// Combiner aware instruction erasure.
450  ///
451  /// When dealing with an instruction that has side effects or produces a void
452  /// value, we can't rely on DCE to delete the instruction. Instead, visit
453  /// methods should return the value returned by this function.
454  virtual Instruction *eraseInstFromFunction(Instruction &I) = 0;
455 
456  void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
457  const Instruction *CxtI) const {
458  llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
459  }
460 
461  KnownBits computeKnownBits(const Value *V, unsigned Depth,
462  const Instruction *CxtI) const {
463  return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
464  }
465 
466  bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
467  unsigned Depth = 0,
468  const Instruction *CxtI = nullptr) {
469  return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
470  }
471 
472  bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
473  const Instruction *CxtI = nullptr) const {
474  return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
475  }
476 
477  unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
478  const Instruction *CxtI = nullptr) const {
479  return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
480  }
481 
483  const Value *RHS,
484  const Instruction *CxtI) const {
485  return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
486  }
487 
489  const Instruction *CxtI) const {
490  return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
491  }
492 
494  const Value *RHS,
495  const Instruction *CxtI) const {
496  return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
497  }
498 
500  const Instruction *CxtI) const {
501  return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
502  }
503 
505  const Value *RHS,
506  const Instruction *CxtI) const {
507  return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
508  }
509 
511  const Instruction *CxtI) const {
512  return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
513  }
514 
515  virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo,
516  const APInt &DemandedMask, KnownBits &Known,
517  unsigned Depth = 0) = 0;
518  virtual Value *
519  SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts,
520  unsigned Depth = 0,
521  bool AllowMultipleUsers = false) = 0;
522 };
523 
524 } // namespace llvm
525 
526 #undef DEBUG_TYPE
527 
528 #endif
i
i
Definition: README.txt:29
llvm::InstCombiner::SQ
const SimplifyQuery SQ
Definition: InstCombiner.h:72
llvm::APInt::isMaxSignedValue
bool isMaxSignedValue() const
Determine if this is the largest signed value.
Definition: APInt.h:433
llvm::InstCombiner::shouldAvoidAbsorbingNotIntoSelect
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
Definition: InstCombiner.h:216
llvm::InstCombiner::getTargetLibraryInfo
TargetLibraryInfo & getTargetLibraryInfo() const
Definition: InstCombiner.h:368
llvm
Definition: AllocatorList.h:23
llvm::MaskedValueIsZero
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if 'V & Mask' is known to be zero.
Definition: ValueTracking.cpp:359
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::InstCombiner::isFreeToInvert
static bool isFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
Definition: InstCombiner.h:233
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::InstCombiner::getDominatorTree
DominatorTree & getDominatorTree() const
Definition: InstCombiner.h:369
llvm::computeOverflowForUnsignedMul
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Definition: ValueTracking.cpp:4617
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
llvm::InstCombiner::computeOverflowForUnsignedMul
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:482
llvm::InstCombiner::ComputeNumSignBits
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:477
llvm::InstCombiner::TLI
TargetLibraryInfo & TLI
Definition: InstCombiner.h:69
TargetFolder.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::InstCombiner::Builder
BuilderTy & Builder
Definition: InstCombiner.h:56
llvm::InstCombiner::getBlockFrequencyInfo
BlockFrequencyInfo * getBlockFrequencyInfo() const
Definition: InstCombiner.h:375
llvm::CmpInst::FCMP_ONE
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:730
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:744
llvm::computeOverflowForUnsignedAdd
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Definition: ValueTracking.cpp:4673
llvm::InstCombiner::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:456
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::InstCombiner::computeOverflowForSignedMul
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:488
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:34
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:749
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::Optional
Definition: APInt.h:34
llvm::ComputeNumSignBits
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
Definition: ValueTracking.cpp:383
llvm::InstCombiner::addToWorklist
void addToWorklist(Instruction *I)
Definition: InstCombiner.h:365
llvm::InstCombiner::computeOverflowForUnsignedAdd
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:493
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:752
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
KnownBits.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::ConstantExpr::getSub
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2675
llvm::InstCombiner::replaceOperand
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
Definition: InstCombiner.h:437
llvm::computeOverflowForSignedSub
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:4772
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::PatternMatch::m_Select
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
Definition: PatternMatch.h:1467
llvm::computeOverflowForSignedAdd
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Definition: ValueTracking.cpp:5172
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::AAResults
Definition: AliasAnalysis.h:456
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::CmpInst::ICMP_ULE
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:748
llvm::InstCombiner::LI
LoopInfo * LI
Definition: InstCombiner.h:79
SI
@ SI
Definition: SIInstrInfo.cpp:7342
llvm::InstCombiner::isKnownToBeAPowerOfTwo
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
Definition: InstCombiner.h:466
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:389
llvm::InstCombiner::replaceUse
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
Definition: InstCombiner.h:444
llvm::InstCombiner::computeKnownBits
KnownBits computeKnownBits(const Value *V, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:461
llvm::PatternMatch::m_FNeg
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
Definition: PatternMatch.h:1058
llvm::InstCombiner::computeOverflowForSignedAdd
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:499
llvm::Instruction
Definition: Instruction.h:45
llvm::InstCombiner::ORE
OptimizationRemarkEmitter & ORE
Definition: InstCombiner.h:73
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1770
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:885
InstCombineWorklist.h
llvm::InstCombiner::getComplexity
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
Definition: InstCombiner.h:125
llvm::InstCombineWorklist
InstCombineWorklist - This is the worklist management logic for InstCombine.
Definition: InstCombineWorklist.h:27
PatternMatch.h
llvm::InstCombiner::~InstCombiner
virtual ~InstCombiner()
Definition: InstCombiner.h:94
llvm::Type::getInt1PtrTy
static PointerType * getInt1PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:252
llvm::InstCombiner::SubOne
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
Definition: InstCombiner.h:205
llvm::APInt::isAllOnesValue
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:402
llvm::OverflowResult
OverflowResult
Definition: ValueTracking.h:487
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::InstCombiner::MinimizeSize
const bool MinimizeSize
Definition: InstCombiner.h:63
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:712
llvm::InstCombiner::BFI
BlockFrequencyInfo * BFI
Definition: InstCombiner.h:74
llvm::InstCombineWorklist::push
void push(Instruction *I)
Push the instruction onto the worklist stack.
Definition: InstCombineWorklist.h:60
llvm::InstCombiner::getSafeVectorConstantForBinop
static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)
Some binary operators require special handling to avoid poison and undefined behavior.
Definition: InstCombiner.h:305
llvm::tgtok::In
@ In
Definition: TGLexer.h:51
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:303
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::InstCombiner::AC
AssumptionCache & AC
Definition: InstCombiner.h:68
llvm::ConstantExpr::getBinOpIdentity
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2786
llvm::InstCombiner::getAssumptionCache
AssumptionCache & getAssumptionCache() const
Definition: InstCombiner.h:367
llvm::InstCombiner::AddOne
static Constant * AddOne(Constant *C)
Add one to a Constant.
Definition: InstCombiner.h:200
llvm::InstCombiner::getDataLayout
const DataLayout & getDataLayout() const
Definition: InstCombiner.h:370
llvm::PatternMatch::m_LogicalOr
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
Definition: PatternMatch.h:2501
llvm::InstCombiner::isCanonicalPredicate
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
Definition: InstCombiner.h:143
llvm::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:4749
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::InstCombiner::AA
AAResults * AA
Definition: InstCombiner.h:65
llvm::InstCombiner::canFreelyInvertAllUsersOf
static bool canFreelyInvertAllUsersOf(Value *V, Value *IgnoredUser)
Given i1 V, can every user of V be freely adapted if V is changed to !V ? InstCombine's freelyInvertA...
Definition: InstCombiner.h:269
llvm::InstCombineWorklist::addValue
void addValue(Value *V)
Add value to the worklist if it is an instruction.
Definition: InstCombineWorklist.h:53
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:211
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CmpInst::FCMP_OGE
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:727
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:746
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1715
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:163
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::InstCombiner::InsertNewInstBefore
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
Definition: InstCombiner.h:395
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:649
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:71
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:751
llvm::LoopInfo
Definition: LoopInfo.h:1080
llvm::BinaryOperator
Definition: InstrTypes.h:190
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:747
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::InstCombiner::MaskedValueIsZero
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:472
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:940
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
LLVM_LIBRARY_VISIBILITY
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:131
llvm::InstCombiner::InsertNewInstWith
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
Definition: InstCombiner.h:405
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1354
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:419
llvm::InstCombiner::CreateNonTerminatorUnreachable
static void CreateNonTerminatorUnreachable(Instruction *InsertAt)
Create and insert the idiom we use to indicate a block is unreachable without having to rewrite the C...
Definition: InstCombiner.h:359
llvm::InstCombiner::replaceInstUsesWith
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombiner.h:416
llvm::InstCombiner::InstCombiner
InstCombiner(InstCombineWorklist &Worklist, BuilderTy &Builder, bool MinimizeSize, AAResults *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, const DataLayout &DL, LoopInfo *LI)
Definition: InstCombiner.h:84
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:163
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:347
llvm::KnownBits
Definition: KnownBits.h:23
llvm::APInt::isMinSignedValue
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:449
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::ConstantExpr::getAdd
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2664
llvm::InstCombiner::DL
const DataLayout & DL
Definition: InstCombiner.h:71
llvm::ConstantFP::get
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:932
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:207
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:750
llvm::computeOverflowForSignedMul
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Definition: ValueTracking.cpp:4631
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:184
llvm::InstCombiner
The core instruction combiner logic.
Definition: InstCombiner.h:45
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
llvm::APInt::isNullValue
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:412
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:768
llvm::InstCombiner::getLoopInfo
LoopInfo * getLoopInfo() const
Definition: InstCombiner.h:377
llvm::PatternMatch::m_AnyIntegralConstant
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
Definition: PatternMatch.h:436
llvm::InstCombiner::getOptimizationRemarkEmitter
OptimizationRemarkEmitter & getOptimizationRemarkEmitter() const
Definition: InstCombiner.h:372
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:365
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:745
llvm::InstCombiner::DT
DominatorTree & DT
Definition: InstCombiner.h:70
llvm::InstCombiner::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:504
llvm::InstCombiner::getSimplifyQuery
const SimplifyQuery & getSimplifyQuery() const
Definition: InstCombiner.h:371
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
InstructionSimplify.h
llvm::MIPatternMatch::m_Neg
BinaryOp_match< SpecificConstantMatch, SrcTy, TargetOpcode::G_SUB > m_Neg(const SrcTy &&Src)
Matches a register negated by a G_SUB.
Definition: MIPatternMatch.h:495
llvm::CmpInst::FCMP_OLE
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:729
llvm::InstCombiner::isSignBitCheck
static bool isSignBitCheck(ICmpInst::Predicate Pred, const APInt &RHS, bool &TrueIfSigned)
Given an exploded icmp instruction, return true if the comparison only checks the sign bit.
Definition: InstCombiner.h:163
llvm::InstCombineWorklist::pushUsersToWorkList
void pushUsersToWorkList(Instruction &I)
When an instruction is simplified, add all users of the instruction to the work lists because they mi...
Definition: InstCombineWorklist.h:108
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
llvm::MIPatternMatch::m_Not
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
Definition: MIPatternMatch.h:503
llvm::isKnownToBeAPowerOfTwo
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to have exactly one bit set when defined.
Definition: ValueTracking.cpp:295
llvm::InstCombiner::peekThroughBitcast
static Value * peekThroughBitcast(Value *V, bool OneUseOnly=false)
Return the source operand of a potentially bitcasted value while optionally checking if it has one us...
Definition: InstCombiner.h:99
llvm::InstCombiner::getProfileSummaryInfo
ProfileSummaryInfo * getProfileSummaryInfo() const
Definition: InstCombiner.h:376
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::PatternMatch::m_LogicalAnd
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
Definition: PatternMatch.h:2490
llvm::InstCombiner::computeOverflowForSignedSub
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:510
llvm::InstCombiner::PSI
ProfileSummaryInfo * PSI
Definition: InstCombiner.h:75
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::InstCombiner::Worklist
InstCombineWorklist & Worklist
A worklist of the instructions that need to be simplified.
Definition: InstCombiner.h:60