LLVM  14.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 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.isZero();
169  case ICmpInst::ICMP_SLE: // True if LHS s<= -1
170  TrueIfSigned = true;
171  return RHS.isAllOnes();
172  case ICmpInst::ICMP_SGT: // True if LHS s> -1
173  TrueIfSigned = false;
174  return RHS.isAllOnes();
175  case ICmpInst::ICMP_SGE: // True if LHS s>= 0
176  TrueIfSigned = false;
177  return RHS.isZero();
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.
250  return WillInvertAllUses;
251 
252  // If `V` is of the form `Constant - A` then `-1 - V` can be folded into
253  // `A + (-1 - Constant)` if we are willing to invert all of the uses.
255  return WillInvertAllUses;
256 
257  // Selects with invertible operands are freely invertible
258  if (match(V,
261  return WillInvertAllUses;
262 
263  // Min/max may be in the form of intrinsics, so handle those identically
264  // to select patterns.
267  return WillInvertAllUses;
268 
269  return false;
270  }
271 
272  /// Given i1 V, can every user of V be freely adapted if V is changed to !V ?
273  /// InstCombine's freelyInvertAllUsersOf() must be kept in sync with this fn.
274  ///
275  /// See also: isFreeToInvert()
276  static bool canFreelyInvertAllUsersOf(Value *V, Value *IgnoredUser) {
277  // Look at every user of V.
278  for (Use &U : V->uses()) {
279  if (U.getUser() == IgnoredUser)
280  continue; // Don't consider this user.
281 
282  auto *I = cast<Instruction>(U.getUser());
283  switch (I->getOpcode()) {
284  case Instruction::Select:
285  if (U.getOperandNo() != 0) // Only if the value is used as select cond.
286  return false;
287  if (shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(I)))
288  return false;
289  break;
290  case Instruction::Br:
291  assert(U.getOperandNo() == 0 && "Must be branching on that value.");
292  break; // Free to invert by swapping true/false values/destinations.
293  case Instruction::Xor: // Can invert 'xor' if it's a 'not', by ignoring
294  // it.
296  return false; // Not a 'not'.
297  break;
298  default:
299  return false; // Don't know, likely not freely invertible.
300  }
301  // So far all users were free to invert...
302  }
303  return true; // Can freely invert all users!
304  }
305 
306  /// Some binary operators require special handling to avoid poison and
307  /// undefined behavior. If a constant vector has undef elements, replace those
308  /// undefs with identity constants if possible because those are always safe
309  /// to execute. If no identity constant exists, replace undef with some other
310  /// safe constant.
311  static Constant *
313  bool IsRHSConstant) {
314  auto *InVTy = cast<FixedVectorType>(In->getType());
315 
316  Type *EltTy = InVTy->getElementType();
317  auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant);
318  if (!SafeC) {
319  // TODO: Should this be available as a constant utility function? It is
320  // similar to getBinOpAbsorber().
321  if (IsRHSConstant) {
322  switch (Opcode) {
323  case Instruction::SRem: // X % 1 = 0
324  case Instruction::URem: // X %u 1 = 0
325  SafeC = ConstantInt::get(EltTy, 1);
326  break;
327  case Instruction::FRem: // X % 1.0 (doesn't simplify, but it is safe)
328  SafeC = ConstantFP::get(EltTy, 1.0);
329  break;
330  default:
332  "Only rem opcodes have no identity constant for RHS");
333  }
334  } else {
335  switch (Opcode) {
336  case Instruction::Shl: // 0 << X = 0
337  case Instruction::LShr: // 0 >>u X = 0
338  case Instruction::AShr: // 0 >> X = 0
339  case Instruction::SDiv: // 0 / X = 0
340  case Instruction::UDiv: // 0 /u X = 0
341  case Instruction::SRem: // 0 % X = 0
342  case Instruction::URem: // 0 %u X = 0
343  case Instruction::Sub: // 0 - X (doesn't simplify, but it is safe)
344  case Instruction::FSub: // 0.0 - X (doesn't simplify, but it is safe)
345  case Instruction::FDiv: // 0.0 / X (doesn't simplify, but it is safe)
346  case Instruction::FRem: // 0.0 % X = 0
347  SafeC = Constant::getNullValue(EltTy);
348  break;
349  default:
350  llvm_unreachable("Expected to find identity constant for opcode");
351  }
352  }
353  }
354  assert(SafeC && "Must have safe constant for binop");
355  unsigned NumElts = InVTy->getNumElements();
356  SmallVector<Constant *, 16> Out(NumElts);
357  for (unsigned i = 0; i != NumElts; ++i) {
358  Constant *C = In->getAggregateElement(i);
359  Out[i] = isa<UndefValue>(C) ? SafeC : C;
360  }
361  return ConstantVector::get(Out);
362  }
363 
364  void addToWorklist(Instruction *I) { Worklist.push(I); }
365 
366  AssumptionCache &getAssumptionCache() const { return AC; }
367  TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; }
368  DominatorTree &getDominatorTree() const { return DT; }
369  const DataLayout &getDataLayout() const { return DL; }
370  const SimplifyQuery &getSimplifyQuery() const { return SQ; }
372  return ORE;
373  }
375  ProfileSummaryInfo *getProfileSummaryInfo() const { return PSI; }
376  LoopInfo *getLoopInfo() const { return LI; }
377 
378  // Call target specific combiners
379  Optional<Instruction *> targetInstCombineIntrinsic(IntrinsicInst &II);
381  targetSimplifyDemandedUseBitsIntrinsic(IntrinsicInst &II, APInt DemandedMask,
382  KnownBits &Known,
383  bool &KnownBitsComputed);
384  Optional<Value *> targetSimplifyDemandedVectorEltsIntrinsic(
385  IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts,
386  APInt &UndefElts2, APInt &UndefElts3,
387  std::function<void(Instruction *, unsigned, APInt, APInt &)>
388  SimplifyAndSetOp);
389 
390  /// Inserts an instruction \p New before instruction \p Old
391  ///
392  /// Also adds the new instruction to the worklist and returns \p New so that
393  /// it is suitable for use as the return from the visitation patterns.
395  assert(New && !New->getParent() &&
396  "New instruction already inserted into a basic block!");
397  BasicBlock *BB = Old.getParent();
398  BB->getInstList().insert(Old.getIterator(), New); // Insert inst
399  Worklist.push(New);
400  return New;
401  }
402 
403  /// Same as InsertNewInstBefore, but also sets the debug loc.
405  New->setDebugLoc(Old.getDebugLoc());
406  return InsertNewInstBefore(New, Old);
407  }
408 
409  /// A combiner-aware RAUW-like routine.
410  ///
411  /// This method is to be used when an instruction is found to be dead,
412  /// replaceable with another preexisting expression. Here we add all uses of
413  /// I to the worklist, replace all uses of I with the new value, then return
414  /// I, so that the inst combiner will know that I was modified.
416  // If there are no uses to replace, then we return nullptr to indicate that
417  // no changes were made to the program.
418  if (I.use_empty())
419  return nullptr;
420 
421  Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist.
422 
423  // If we are replacing the instruction with itself, this must be in a
424  // segment of unreachable code, so just clobber the instruction.
425  if (&I == V)
426  V = UndefValue::get(I.getType());
427 
428  LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
429  << " with " << *V << '\n');
430 
431  I.replaceAllUsesWith(V);
432  return &I;
433  }
434 
435  /// Replace operand of instruction and add old operand to the worklist.
436  Instruction *replaceOperand(Instruction &I, unsigned OpNum, Value *V) {
437  Worklist.addValue(I.getOperand(OpNum));
438  I.setOperand(OpNum, V);
439  return &I;
440  }
441 
442  /// Replace use and add the previously used value to the worklist.
443  void replaceUse(Use &U, Value *NewValue) {
444  Worklist.addValue(U);
445  U = NewValue;
446  }
447 
448  /// Combiner aware instruction erasure.
449  ///
450  /// When dealing with an instruction that has side effects or produces a void
451  /// value, we can't rely on DCE to delete the instruction. Instead, visit
452  /// methods should return the value returned by this function.
453  virtual Instruction *eraseInstFromFunction(Instruction &I) = 0;
454 
455  void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
456  const Instruction *CxtI) const {
457  llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
458  }
459 
460  KnownBits computeKnownBits(const Value *V, unsigned Depth,
461  const Instruction *CxtI) const {
462  return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
463  }
464 
465  bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
466  unsigned Depth = 0,
467  const Instruction *CxtI = nullptr) {
468  return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
469  }
470 
471  bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
472  const Instruction *CxtI = nullptr) const {
473  return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
474  }
475 
476  unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
477  const Instruction *CxtI = nullptr) const {
478  return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
479  }
480 
482  const Value *RHS,
483  const Instruction *CxtI) const {
484  return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
485  }
486 
488  const Instruction *CxtI) const {
489  return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
490  }
491 
493  const Value *RHS,
494  const Instruction *CxtI) const {
495  return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
496  }
497 
499  const Instruction *CxtI) const {
500  return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
501  }
502 
504  const Value *RHS,
505  const Instruction *CxtI) const {
506  return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
507  }
508 
510  const Instruction *CxtI) const {
511  return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
512  }
513 
514  virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo,
515  const APInt &DemandedMask, KnownBits &Known,
516  unsigned Depth = 0) = 0;
517  virtual Value *
518  SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts,
519  unsigned Depth = 0,
520  bool AllowMultipleUsers = false) = 0;
521 };
522 
523 } // namespace llvm
524 
525 #undef DEBUG_TYPE
526 
527 #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:390
llvm::InstCombiner::shouldAvoidAbsorbingNotIntoSelect
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
Definition: InstCombiner.h:216
llvm::InstCombiner::getTargetLibraryInfo
TargetLibraryInfo & getTargetLibraryInfo() const
Definition: InstCombiner.h:367
llvm
This file implements support for optimizing divisions by a constant.
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:356
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:233
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:720
llvm::InstCombiner::getDominatorTree
DominatorTree & getDominatorTree() const
Definition: InstCombiner.h:368
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:4727
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
llvm::InstCombiner::computeOverflowForUnsignedMul
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:481
llvm::InstCombiner::ComputeNumSignBits
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:476
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::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1008
llvm::InstCombiner::getBlockFrequencyInfo
BlockFrequencyInfo * getBlockFrequencyInfo() const
Definition: InstCombiner.h:374
llvm::CmpInst::FCMP_ONE
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:728
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:742
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:4783
llvm::InstCombiner::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:455
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:487
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:747
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:380
llvm::InstCombiner::addToWorklist
void addToWorklist(Instruction *I)
Definition: InstCombiner.h:364
llvm::InstCombiner::computeOverflowForUnsignedAdd
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:492
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:750
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:101
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:163
llvm::ConstantExpr::getSub
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2701
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:436
llvm::computeOverflowForSignedSub
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:4882
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:1472
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:5291
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::AAResults
Definition: AliasAnalysis.h:508
llvm::APInt::isZero
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:359
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:746
llvm::InstCombiner::LI
LoopInfo * LI
Definition: InstCombiner.h:79
InstructionWorklist.h
llvm::InstCombiner::isKnownToBeAPowerOfTwo
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
Definition: InstCombiner.h:465
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:443
llvm::InstCombiner::computeKnownBits
KnownBits computeKnownBits(const Value *V, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:460
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:1892
llvm::PatternMatch::m_FNeg
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
Definition: PatternMatch.h:1063
llvm::InstCombiner::computeOverflowForSignedAdd
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:498
llvm::Instruction
Definition: Instruction.h:45
llvm::InstCombiner::ORE
OptimizationRemarkEmitter & ORE
Definition: InstCombiner.h:73
llvm::APInt::isAllOnes
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:347
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1796
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:925
llvm::InstCombiner::getComplexity
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
Definition: InstCombiner.h:125
PatternMatch.h
llvm::InstCombiner::~InstCombiner
virtual ~InstCombiner()
Definition: InstCombiner.h:94
llvm::InstCombiner::SubOne
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
Definition: InstCombiner.h:205
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:710
llvm::InstCombiner::BFI
BlockFrequencyInfo * BFI
Definition: InstCombiner.h:74
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:312
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:781
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:2812
llvm::InstCombiner::getAssumptionCache
AssumptionCache & getAssumptionCache() const
Definition: InstCombiner.h:366
llvm::InstCombiner::AddOne
static Constant * AddOne(Constant *C)
Add one to a Constant.
Definition: InstCombiner.h:200
uint64_t
llvm::InstCombiner::getDataLayout
const DataLayout & getDataLayout() const
Definition: InstCombiner.h:369
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:2522
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: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:4859
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:276
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:213
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:1020
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:725
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:84
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:744
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
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:394
llvm::InstCombiner::Worklist
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Definition: InstCombiner.h:60
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
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:749
llvm::LoopInfo
Definition: LoopInfo.h:1083
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:745
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::InstCombiner::MaskedValueIsZero
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:471
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:404
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1394
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:421
llvm::InstCombiner::replaceInstUsesWith
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombiner.h:415
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:348
llvm::KnownBits
Definition: KnownBits.h:23
llvm::APInt::isMinSignedValue
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:408
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:324
llvm::ConstantExpr::getAdd
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2690
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:972
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:221
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:748
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:4741
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::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:785
llvm::InstCombiner::getLoopInfo
LoopInfo * getLoopInfo() const
Definition: InstCombiner.h:376
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:371
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:370
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:743
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:503
llvm::InstCombiner::getSimplifyQuery
const SimplifyQuery & getSimplifyQuery() const
Definition: InstCombiner.h:370
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:583
llvm::CmpInst::FCMP_OLE
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:727
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:163
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:591
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:292
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:375
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:2504
llvm::InstCombiner::computeOverflowForSignedSub
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:509
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