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