LLVM  9.0.0svn
InstCombineInternal.h
Go to the documentation of this file.
1 //===- InstCombineInternal.h - InstCombine pass internals -------*- 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 //
9 /// \file
10 ///
11 /// This file provides internal interfaces used to implement the InstCombine.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
16 #define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
17 
18 #include "llvm/ADT/ArrayRef.h"
23 #include "llvm/IR/Argument.h"
24 #include "llvm/IR/BasicBlock.h"
25 #include "llvm/IR/Constant.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/IRBuilder.h"
29 #include "llvm/IR/InstVisitor.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/Intrinsics.h"
34 #include "llvm/IR/PatternMatch.h"
35 #include "llvm/IR/Use.h"
36 #include "llvm/IR/Value.h"
37 #include "llvm/Support/Casting.h"
38 #include "llvm/Support/Compiler.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/KnownBits.h"
44 #include <cassert>
45 #include <cstdint>
46 
47 #define DEBUG_TYPE "instcombine"
48 
49 using namespace llvm::PatternMatch;
50 
51 namespace llvm {
52 
53 class APInt;
54 class AssumptionCache;
55 class BlockFrequencyInfo;
56 class DataLayout;
57 class DominatorTree;
58 class GEPOperator;
59 class GlobalVariable;
60 class LoopInfo;
61 class OptimizationRemarkEmitter;
62 class ProfileSummaryInfo;
63 class TargetLibraryInfo;
64 class User;
65 
66 /// Assign a complexity or rank value to LLVM Values. This is used to reduce
67 /// the amount of pattern matching needed for compares and commutative
68 /// instructions. For example, if we have:
69 /// icmp ugt X, Constant
70 /// or
71 /// xor (add X, Constant), cast Z
72 ///
73 /// We do not have to consider the commuted variants of these patterns because
74 /// canonicalization based on complexity guarantees the above ordering.
75 ///
76 /// This routine maps IR values to various complexity ranks:
77 /// 0 -> undef
78 /// 1 -> Constants
79 /// 2 -> Other non-instructions
80 /// 3 -> Arguments
81 /// 4 -> Cast and (f)neg/not instructions
82 /// 5 -> Other instructions
83 static inline unsigned getComplexity(Value *V) {
84  if (isa<Instruction>(V)) {
85  if (isa<CastInst>(V) || match(V, m_Neg(m_Value())) ||
86  match(V, m_Not(m_Value())) || match(V, m_FNeg(m_Value())))
87  return 4;
88  return 5;
89  }
90  if (isa<Argument>(V))
91  return 3;
92  return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
93 }
94 
95 /// Predicate canonicalization reduces the number of patterns that need to be
96 /// matched by other transforms. For example, we may swap the operands of a
97 /// conditional branch or select to create a compare with a canonical (inverted)
98 /// predicate which is then more likely to be matched with other values.
99 static inline bool isCanonicalPredicate(CmpInst::Predicate Pred) {
100  switch (Pred) {
101  case CmpInst::ICMP_NE:
102  case CmpInst::ICMP_ULE:
103  case CmpInst::ICMP_SLE:
104  case CmpInst::ICMP_UGE:
105  case CmpInst::ICMP_SGE:
106  // TODO: There are 16 FCMP predicates. Should others be (not) canonical?
107  case CmpInst::FCMP_ONE:
108  case CmpInst::FCMP_OLE:
109  case CmpInst::FCMP_OGE:
110  return false;
111  default:
112  return true;
113  }
114 }
115 
116 /// Return the source operand of a potentially bitcasted value while optionally
117 /// checking if it has one use. If there is no bitcast or the one use check is
118 /// not met, return the input value itself.
119 static inline Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) {
120  if (auto *BitCast = dyn_cast<BitCastInst>(V))
121  if (!OneUseOnly || BitCast->hasOneUse())
122  return BitCast->getOperand(0);
123 
124  // V is not a bitcast or V has more than one use and OneUseOnly is true.
125  return V;
126 }
127 
128 /// Add one to a Constant
129 static inline Constant *AddOne(Constant *C) {
130  return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
131 }
132 
133 /// Subtract one from a Constant
134 static inline Constant *SubOne(Constant *C) {
135  return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
136 }
137 
138 /// Return true if the specified value is free to invert (apply ~ to).
139 /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses
140 /// is true, work under the assumption that the caller intends to remove all
141 /// uses of V and only keep uses of ~V.
142 static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) {
143  // ~(~(X)) -> X.
144  if (match(V, m_Not(m_Value())))
145  return true;
146 
147  // Constants can be considered to be not'ed values.
148  if (isa<ConstantInt>(V))
149  return true;
150 
151  // A vector of constant integers can be inverted easily.
152  if (V->getType()->isVectorTy() && isa<Constant>(V)) {
153  unsigned NumElts = V->getType()->getVectorNumElements();
154  for (unsigned i = 0; i != NumElts; ++i) {
155  Constant *Elt = cast<Constant>(V)->getAggregateElement(i);
156  if (!Elt)
157  return false;
158 
159  if (isa<UndefValue>(Elt))
160  continue;
161 
162  if (!isa<ConstantInt>(Elt))
163  return false;
164  }
165  return true;
166  }
167 
168  // Compares can be inverted if all of their uses are being modified to use the
169  // ~V.
170  if (isa<CmpInst>(V))
171  return WillInvertAllUses;
172 
173  // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1
174  // - Constant) - A` if we are willing to invert all of the uses.
175  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
176  if (BO->getOpcode() == Instruction::Add ||
177  BO->getOpcode() == Instruction::Sub)
178  if (isa<Constant>(BO->getOperand(0)) || isa<Constant>(BO->getOperand(1)))
179  return WillInvertAllUses;
180 
181  // Selects with invertible operands are freely invertible
182  if (match(V, m_Select(m_Value(), m_Not(m_Value()), m_Not(m_Value()))))
183  return WillInvertAllUses;
184 
185  return false;
186 }
187 
188 /// Specific patterns of overflow check idioms that we match.
196 
198 };
199 
200 /// Returns the OverflowCheckFlavor corresponding to a overflow_with_op
201 /// intrinsic.
202 static inline OverflowCheckFlavor
204  switch (ID) {
205  default:
206  return OCF_INVALID;
207  case Intrinsic::uadd_with_overflow:
208  return OCF_UNSIGNED_ADD;
209  case Intrinsic::sadd_with_overflow:
210  return OCF_SIGNED_ADD;
211  case Intrinsic::usub_with_overflow:
212  return OCF_UNSIGNED_SUB;
213  case Intrinsic::ssub_with_overflow:
214  return OCF_SIGNED_SUB;
215  case Intrinsic::umul_with_overflow:
216  return OCF_UNSIGNED_MUL;
217  case Intrinsic::smul_with_overflow:
218  return OCF_SIGNED_MUL;
219  }
220 }
221 
222 /// Some binary operators require special handling to avoid poison and undefined
223 /// behavior. If a constant vector has undef elements, replace those undefs with
224 /// identity constants if possible because those are always safe to execute.
225 /// If no identity constant exists, replace undef with some other safe constant.
227  BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant) {
228  assert(In->getType()->isVectorTy() && "Not expecting scalars here");
229 
230  Type *EltTy = In->getType()->getVectorElementType();
231  auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant);
232  if (!SafeC) {
233  // TODO: Should this be available as a constant utility function? It is
234  // similar to getBinOpAbsorber().
235  if (IsRHSConstant) {
236  switch (Opcode) {
237  case Instruction::SRem: // X % 1 = 0
238  case Instruction::URem: // X %u 1 = 0
239  SafeC = ConstantInt::get(EltTy, 1);
240  break;
241  case Instruction::FRem: // X % 1.0 (doesn't simplify, but it is safe)
242  SafeC = ConstantFP::get(EltTy, 1.0);
243  break;
244  default:
245  llvm_unreachable("Only rem opcodes have no identity constant for RHS");
246  }
247  } else {
248  switch (Opcode) {
249  case Instruction::Shl: // 0 << X = 0
250  case Instruction::LShr: // 0 >>u X = 0
251  case Instruction::AShr: // 0 >> X = 0
252  case Instruction::SDiv: // 0 / X = 0
253  case Instruction::UDiv: // 0 /u X = 0
254  case Instruction::SRem: // 0 % X = 0
255  case Instruction::URem: // 0 %u X = 0
256  case Instruction::Sub: // 0 - X (doesn't simplify, but it is safe)
257  case Instruction::FSub: // 0.0 - X (doesn't simplify, but it is safe)
258  case Instruction::FDiv: // 0.0 / X (doesn't simplify, but it is safe)
259  case Instruction::FRem: // 0.0 % X = 0
260  SafeC = Constant::getNullValue(EltTy);
261  break;
262  default:
263  llvm_unreachable("Expected to find identity constant for opcode");
264  }
265  }
266  }
267  assert(SafeC && "Must have safe constant for binop");
268  unsigned NumElts = In->getType()->getVectorNumElements();
269  SmallVector<Constant *, 16> Out(NumElts);
270  for (unsigned i = 0; i != NumElts; ++i) {
271  Constant *C = In->getAggregateElement(i);
272  Out[i] = isa<UndefValue>(C) ? SafeC : C;
273  }
274  return ConstantVector::get(Out);
275 }
276 
277 /// The core instruction combiner logic.
278 ///
279 /// This class provides both the logic to recursively visit instructions and
280 /// combine them.
282  : public InstVisitor<InstCombiner, Instruction *> {
283  // FIXME: These members shouldn't be public.
284 public:
285  /// A worklist of the instructions that need to be simplified.
287 
288  /// An IRBuilder that automatically inserts new instructions into the
289  /// worklist.
292 
293 private:
294  // Mode in which we are running the combiner.
295  const bool MinimizeSize;
296 
297  /// Enable combines that trigger rarely but are costly in compiletime.
298  const bool ExpensiveCombines;
299 
300  AliasAnalysis *AA;
301 
302  // Required analyses.
303  AssumptionCache &AC;
304  TargetLibraryInfo &TLI;
305  DominatorTree &DT;
306  const DataLayout &DL;
307  const SimplifyQuery SQ;
310  ProfileSummaryInfo *PSI;
311 
312  // Optional analyses. When non-null, these can both be used to do better
313  // combining and will be updated to reflect any changes.
314  LoopInfo *LI;
315 
316  bool MadeIRChange = false;
317 
318 public:
320  bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA,
323  ProfileSummaryInfo *PSI, const DataLayout &DL, LoopInfo *LI)
324  : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize),
325  ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT),
326  DL(DL), SQ(DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {}
327 
328  /// Run the combiner over the entire worklist until it is empty.
329  ///
330  /// \returns true if the IR is changed.
331  bool run();
332 
333  AssumptionCache &getAssumptionCache() const { return AC; }
334 
335  const DataLayout &getDataLayout() const { return DL; }
336 
337  DominatorTree &getDominatorTree() const { return DT; }
338 
339  LoopInfo *getLoopInfo() const { return LI; }
340 
341  TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; }
342 
343  // Visitation implementation - Implement instruction combining for different
344  // instruction types. The semantics are as follows:
345  // Return Value:
346  // null - No change was made
347  // I - Change was made, I is still valid, I may be dead though
348  // otherwise - Change was made, replace I with returned instruction
349  //
350  Instruction *visitAdd(BinaryOperator &I);
351  Instruction *visitFAdd(BinaryOperator &I);
352  Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty);
353  Instruction *visitSub(BinaryOperator &I);
354  Instruction *visitFSub(BinaryOperator &I);
355  Instruction *visitMul(BinaryOperator &I);
356  Instruction *visitFMul(BinaryOperator &I);
357  Instruction *visitURem(BinaryOperator &I);
358  Instruction *visitSRem(BinaryOperator &I);
359  Instruction *visitFRem(BinaryOperator &I);
360  bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
361  Instruction *commonRemTransforms(BinaryOperator &I);
362  Instruction *commonIRemTransforms(BinaryOperator &I);
363  Instruction *commonDivTransforms(BinaryOperator &I);
364  Instruction *commonIDivTransforms(BinaryOperator &I);
365  Instruction *visitUDiv(BinaryOperator &I);
366  Instruction *visitSDiv(BinaryOperator &I);
367  Instruction *visitFDiv(BinaryOperator &I);
368  Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
369  Instruction *visitAnd(BinaryOperator &I);
370  Instruction *visitOr(BinaryOperator &I);
371  Instruction *visitXor(BinaryOperator &I);
372  Instruction *visitShl(BinaryOperator &I);
373  Instruction *visitAShr(BinaryOperator &I);
374  Instruction *visitLShr(BinaryOperator &I);
375  Instruction *commonShiftTransforms(BinaryOperator &I);
376  Instruction *visitFCmpInst(FCmpInst &I);
377  Instruction *visitICmpInst(ICmpInst &I);
378  Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
379  BinaryOperator &I);
380  Instruction *commonCastTransforms(CastInst &CI);
381  Instruction *commonPointerCastTransforms(CastInst &CI);
382  Instruction *visitTrunc(TruncInst &CI);
383  Instruction *visitZExt(ZExtInst &CI);
384  Instruction *visitSExt(SExtInst &CI);
385  Instruction *visitFPTrunc(FPTruncInst &CI);
386  Instruction *visitFPExt(CastInst &CI);
387  Instruction *visitFPToUI(FPToUIInst &FI);
388  Instruction *visitFPToSI(FPToSIInst &FI);
389  Instruction *visitUIToFP(CastInst &CI);
390  Instruction *visitSIToFP(CastInst &CI);
391  Instruction *visitPtrToInt(PtrToIntInst &CI);
392  Instruction *visitIntToPtr(IntToPtrInst &CI);
393  Instruction *visitBitCast(BitCastInst &CI);
394  Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
395  Instruction *FoldItoFPtoI(Instruction &FI);
396  Instruction *visitSelectInst(SelectInst &SI);
397  Instruction *visitCallInst(CallInst &CI);
398  Instruction *visitInvokeInst(InvokeInst &II);
399  Instruction *visitCallBrInst(CallBrInst &CBI);
400 
401  Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
402  Instruction *visitPHINode(PHINode &PN);
403  Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
404  Instruction *visitAllocaInst(AllocaInst &AI);
405  Instruction *visitAllocSite(Instruction &FI);
406  Instruction *visitFree(CallInst &FI);
407  Instruction *visitLoadInst(LoadInst &LI);
408  Instruction *visitStoreInst(StoreInst &SI);
409  Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
410  Instruction *visitBranchInst(BranchInst &BI);
411  Instruction *visitFenceInst(FenceInst &FI);
412  Instruction *visitSwitchInst(SwitchInst &SI);
413  Instruction *visitReturnInst(ReturnInst &RI);
414  Instruction *visitInsertValueInst(InsertValueInst &IV);
415  Instruction *visitInsertElementInst(InsertElementInst &IE);
416  Instruction *visitExtractElementInst(ExtractElementInst &EI);
417  Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
418  Instruction *visitExtractValueInst(ExtractValueInst &EV);
419  Instruction *visitLandingPadInst(LandingPadInst &LI);
420  Instruction *visitVAStartInst(VAStartInst &I);
421  Instruction *visitVACopyInst(VACopyInst &I);
422 
423  /// Specify what to return for unhandled instructions.
424  Instruction *visitInstruction(Instruction &I) { return nullptr; }
425 
426  /// True when DB dominates all uses of DI except UI.
427  /// UI must be in the same block as DI.
428  /// The routine checks that the DI parent and DB are different.
429  bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
430  const BasicBlock *DB) const;
431 
432  /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
433  bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
434  const unsigned SIOpd);
435 
436  /// Try to replace instruction \p I with value \p V which are pointers
437  /// in different address space.
438  /// \return true if successful.
439  bool replacePointer(Instruction &I, Value *V);
440 
441 private:
442  bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
443  bool shouldChangeType(Type *From, Type *To) const;
444  Value *dyn_castNegVal(Value *V) const;
445  Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
446  SmallVectorImpl<Value *> &NewIndices);
447 
448  /// Classify whether a cast is worth optimizing.
449  ///
450  /// This is a helper to decide whether the simplification of
451  /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
452  ///
453  /// \param CI The cast we are interested in.
454  ///
455  /// \return true if this cast actually results in any code being generated and
456  /// if it cannot already be eliminated by some other transformation.
457  bool shouldOptimizeCast(CastInst *CI);
458 
459  /// Try to optimize a sequence of instructions checking if an operation
460  /// on LHS and RHS overflows.
461  ///
462  /// If this overflow check is done via one of the overflow check intrinsics,
463  /// then CtxI has to be the call instruction calling that intrinsic. If this
464  /// overflow check is done by arithmetic followed by a compare, then CtxI has
465  /// to be the arithmetic instruction.
466  ///
467  /// If a simplification is possible, stores the simplified result of the
468  /// operation in OperationResult and result of the overflow check in
469  /// OverflowResult, and return true. If no simplification is possible,
470  /// returns false.
471  bool OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS, Value *RHS,
472  Instruction &CtxI, Value *&OperationResult,
474 
475  Instruction *visitCallBase(CallBase &Call);
476  Instruction *tryOptimizeCall(CallInst *CI);
477  bool transformConstExprCastCall(CallBase &Call);
478  Instruction *transformCallThroughTrampoline(CallBase &Call,
479  IntrinsicInst &Tramp);
480 
481  Instruction *simplifyMaskedStore(IntrinsicInst &II);
482  Instruction *simplifyMaskedScatter(IntrinsicInst &II);
483 
484  /// Transform (zext icmp) to bitwise / integer operations in order to
485  /// eliminate it.
486  ///
487  /// \param ICI The icmp of the (zext icmp) pair we are interested in.
488  /// \parem CI The zext of the (zext icmp) pair we are interested in.
489  /// \param DoTransform Pass false to just test whether the given (zext icmp)
490  /// would be transformed. Pass true to actually perform the transformation.
491  ///
492  /// \return null if the transformation cannot be performed. If the
493  /// transformation can be performed the new instruction that replaces the
494  /// (zext icmp) pair will be returned (if \p DoTransform is false the
495  /// unmodified \p ICI will be returned in this case).
496  Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI,
497  bool DoTransform = true);
498 
499  Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
500 
501  bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
502  const Instruction &CxtI) const {
503  return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
505  }
506 
507  bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
508  const Instruction &CxtI) const {
509  return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
511  }
512 
513  bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
514  const Instruction &CxtI, bool IsSigned) const {
515  return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
516  : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
517  }
518 
519  bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
520  const Instruction &CxtI) const {
521  return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
523  }
524 
525  bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
526  const Instruction &CxtI) const {
527  return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
529  }
530 
531  bool willNotOverflowSub(const Value *LHS, const Value *RHS,
532  const Instruction &CxtI, bool IsSigned) const {
533  return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
534  : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
535  }
536 
537  bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
538  const Instruction &CxtI) const {
539  return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
541  }
542 
543  bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
544  const Instruction &CxtI) const {
545  return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
547  }
548 
549  bool willNotOverflowMul(const Value *LHS, const Value *RHS,
550  const Instruction &CxtI, bool IsSigned) const {
551  return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
552  : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
553  }
554 
555  bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
556  const Value *RHS, const Instruction &CxtI,
557  bool IsSigned) const {
558  switch (Opcode) {
559  case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
560  case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
561  case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
562  default: llvm_unreachable("Unexpected opcode for overflow query");
563  }
564  }
565 
566  Value *EmitGEPOffset(User *GEP);
567  Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
568  Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
569  Instruction *narrowBinOp(TruncInst &Trunc);
570  Instruction *narrowMaskedBinOp(BinaryOperator &And);
571  Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
572  Instruction *narrowRotate(TruncInst &Trunc);
573  Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
574 
575  /// Determine if a pair of casts can be replaced by a single cast.
576  ///
577  /// \param CI1 The first of a pair of casts.
578  /// \param CI2 The second of a pair of casts.
579  ///
580  /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
581  /// Instruction::CastOps value for a cast that can replace the pair, casting
582  /// CI1->getSrcTy() to CI2->getDstTy().
583  ///
584  /// \see CastInst::isEliminableCastPair
585  Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
586  const CastInst *CI2);
587 
588  Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
589  Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
590  Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS);
591 
592  /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
593  /// NOTE: Unlike most of instcombine, this returns a Value which should
594  /// already be inserted into the function.
595  Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd);
596 
597  Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
598  bool JoinedByAnd, Instruction &CxtI);
599  Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
600  Value *getSelectCondition(Value *A, Value *B);
601 
602  Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
603 
604 public:
605  /// Inserts an instruction \p New before instruction \p Old
606  ///
607  /// Also adds the new instruction to the worklist and returns \p New so that
608  /// it is suitable for use as the return from the visitation patterns.
610  assert(New && !New->getParent() &&
611  "New instruction already inserted into a basic block!");
612  BasicBlock *BB = Old.getParent();
613  BB->getInstList().insert(Old.getIterator(), New); // Insert inst
614  Worklist.Add(New);
615  return New;
616  }
617 
618  /// Same as InsertNewInstBefore, but also sets the debug loc.
620  New->setDebugLoc(Old.getDebugLoc());
621  return InsertNewInstBefore(New, Old);
622  }
623 
624  /// A combiner-aware RAUW-like routine.
625  ///
626  /// This method is to be used when an instruction is found to be dead,
627  /// replaceable with another preexisting expression. Here we add all uses of
628  /// I to the worklist, replace all uses of I with the new value, then return
629  /// I, so that the inst combiner will know that I was modified.
631  // If there are no uses to replace, then we return nullptr to indicate that
632  // no changes were made to the program.
633  if (I.use_empty()) return nullptr;
634 
635  Worklist.AddUsersToWorkList(I); // Add all modified instrs to worklist.
636 
637  // If we are replacing the instruction with itself, this must be in a
638  // segment of unreachable code, so just clobber the instruction.
639  if (&I == V)
640  V = UndefValue::get(I.getType());
641 
642  LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
643  << " with " << *V << '\n');
644 
645  I.replaceAllUsesWith(V);
646  return &I;
647  }
648 
649  /// Creates a result tuple for an overflow intrinsic \p II with a given
650  /// \p Result and a constant \p Overflow value.
652  Constant *Overflow) {
653  Constant *V[] = {UndefValue::get(Result->getType()), Overflow};
654  StructType *ST = cast<StructType>(II->getType());
655  Constant *Struct = ConstantStruct::get(ST, V);
656  return InsertValueInst::Create(Struct, Result, 0);
657  }
658 
659  /// Create and insert the idiom we use to indicate a block is unreachable
660  /// without having to rewrite the CFG from within InstCombine.
662  auto &Ctx = InsertAt->getContext();
665  InsertAt);
666  }
667 
668 
669  /// Combiner aware instruction erasure.
670  ///
671  /// When dealing with an instruction that has side effects or produces a void
672  /// value, we can't rely on DCE to delete the instruction. Instead, visit
673  /// methods should return the value returned by this function.
675  LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
676  assert(I.use_empty() && "Cannot erase instruction that is used!");
677  salvageDebugInfo(I);
678 
679  // Make sure that we reprocess all operands now that we reduced their
680  // use counts.
681  if (I.getNumOperands() < 8) {
682  for (Use &Operand : I.operands())
683  if (auto *Inst = dyn_cast<Instruction>(Operand))
684  Worklist.Add(Inst);
685  }
686  Worklist.Remove(&I);
687  I.eraseFromParent();
688  MadeIRChange = true;
689  return nullptr; // Don't do anything with FI
690  }
691 
692  void computeKnownBits(const Value *V, KnownBits &Known,
693  unsigned Depth, const Instruction *CxtI) const {
694  llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
695  }
696 
697  KnownBits computeKnownBits(const Value *V, unsigned Depth,
698  const Instruction *CxtI) const {
699  return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
700  }
701 
702  bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
703  unsigned Depth = 0,
704  const Instruction *CxtI = nullptr) {
705  return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
706  }
707 
708  bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
709  const Instruction *CxtI = nullptr) const {
710  return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
711  }
712 
713  unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
714  const Instruction *CxtI = nullptr) const {
715  return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
716  }
717 
718  OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
719  const Value *RHS,
720  const Instruction *CxtI) const {
721  return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
722  }
723 
724  OverflowResult computeOverflowForSignedMul(const Value *LHS,
725  const Value *RHS,
726  const Instruction *CxtI) const {
727  return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
728  }
729 
730  OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
731  const Value *RHS,
732  const Instruction *CxtI) const {
733  return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
734  }
735 
736  OverflowResult computeOverflowForSignedAdd(const Value *LHS,
737  const Value *RHS,
738  const Instruction *CxtI) const {
739  return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
740  }
741 
742  OverflowResult computeOverflowForUnsignedSub(const Value *LHS,
743  const Value *RHS,
744  const Instruction *CxtI) const {
745  return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
746  }
747 
748  OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
749  const Instruction *CxtI) const {
750  return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
751  }
752 
753  /// Maximum size of array considered when transforming.
755 
756 private:
757  /// Performs a few simplifications for operators which are associative
758  /// or commutative.
759  bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
760 
761  /// Tries to simplify binary operations which some other binary
762  /// operation distributes over.
763  ///
764  /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
765  /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
766  /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
767  /// value, or null if it didn't simplify.
768  Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
769 
770  /// Tries to simplify add operations using the definition of remainder.
771  ///
772  /// The definition of remainder is X % C = X - (X / C ) * C. The add
773  /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
774  /// X % (C0 * C1)
775  Value *SimplifyAddWithRemainder(BinaryOperator &I);
776 
777  // Binary Op helper for select operations where the expression can be
778  // efficiently reorganized.
779  Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
780  Value *RHS);
781 
782  /// This tries to simplify binary operations by factorizing out common terms
783  /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
784  Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
785  Value *, Value *, Value *);
786 
787  /// Match a select chain which produces one of three values based on whether
788  /// the LHS is less than, equal to, or greater than RHS respectively.
789  /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
790  /// Equal and Greater values are saved in the matching process and returned to
791  /// the caller.
792  bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
794  ConstantInt *&Greater);
795 
796  /// Attempts to replace V with a simpler value based on the demanded
797  /// bits.
798  Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
799  unsigned Depth, Instruction *CxtI);
800  bool SimplifyDemandedBits(Instruction *I, unsigned Op,
801  const APInt &DemandedMask, KnownBits &Known,
802  unsigned Depth = 0);
803 
804  /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
805  /// bits. It also tries to handle simplifications that can be done based on
806  /// DemandedMask, but without modifying the Instruction.
807  Value *SimplifyMultipleUseDemandedBits(Instruction *I,
808  const APInt &DemandedMask,
809  KnownBits &Known,
810  unsigned Depth, Instruction *CxtI);
811 
812  /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
813  /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
814  Value *simplifyShrShlDemandedBits(
815  Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
816  const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
817 
818  /// Tries to simplify operands to an integer instruction based on its
819  /// demanded bits.
820  bool SimplifyDemandedInstructionBits(Instruction &Inst);
821 
822  Value *simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II,
823  APInt DemandedElts,
824  int DmaskIdx = -1);
825 
826  Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
827  APInt &UndefElts, unsigned Depth = 0);
828 
829  /// Canonicalize the position of binops relative to shufflevector.
830  Instruction *foldVectorBinop(BinaryOperator &Inst);
831 
832  /// Given a binary operator, cast instruction, or select which has a PHI node
833  /// as operand #0, see if we can fold the instruction into the PHI (which is
834  /// only possible if all operands to the PHI are constants).
835  Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
836 
837  /// Given an instruction with a select as one operand and a constant as the
838  /// other operand, try to fold the binary operator into the select arguments.
839  /// This also works for Cast instructions, which obviously do not have a
840  /// second operand.
841  Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
842 
843  /// This is a convenience wrapper function for the above two functions.
844  Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
845 
846  Instruction *foldAddWithConstant(BinaryOperator &Add);
847 
848  /// Try to rotate an operation below a PHI node, using PHI nodes for
849  /// its operands.
850  Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
851  Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN);
852  Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN);
853  Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN);
854  Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN);
855 
856  /// If an integer typed PHI has only one use which is an IntToPtr operation,
857  /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
858  /// insert a new pointer typed PHI and replace the original one.
859  Instruction *FoldIntegerTypedPHI(PHINode &PN);
860 
861  /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
862  /// folded operation.
863  void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
864 
865  Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
867  Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
868  const Value *Other);
869  Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
870  GlobalVariable *GV, CmpInst &ICI,
871  ConstantInt *AndCst = nullptr);
872  Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
873  Constant *RHSC);
874  Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
875  ICmpInst::Predicate Pred);
876  Instruction *foldICmpWithCastAndCast(ICmpInst &ICI);
877 
878  Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
879  Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
880  Instruction *foldICmpWithConstant(ICmpInst &Cmp);
881  Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
882  Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
883  Instruction *foldICmpBinOp(ICmpInst &Cmp);
884  Instruction *foldICmpEquality(ICmpInst &Cmp);
885  Instruction *foldICmpWithZero(ICmpInst &Cmp);
886 
887  Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
888  ConstantInt *C);
889  Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
890  const APInt &C);
891  Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
892  const APInt &C);
893  Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
894  const APInt &C);
895  Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
896  const APInt &C);
897  Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
898  const APInt &C);
899  Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
900  const APInt &C);
901  Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
902  const APInt &C);
903  Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
904  const APInt &C);
905  Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
906  const APInt &C);
907  Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
908  const APInt &C);
909  Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
910  const APInt &C);
911  Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
912  const APInt &C1);
913  Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
914  const APInt &C1, const APInt &C2);
915  Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
916  const APInt &C2);
917  Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
918  const APInt &C2);
919 
920  Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
921  BinaryOperator *BO,
922  const APInt &C);
923  Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
924  const APInt &C);
925  Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
926  const APInt &C);
927 
928  // Helpers of visitSelectInst().
929  Instruction *foldSelectExtConst(SelectInst &Sel);
930  Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
931  Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
932  Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
933  Value *A, Value *B, Instruction &Outer,
934  SelectPatternFlavor SPF2, Value *C);
935  Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
936 
937  Instruction *OptAndOp(BinaryOperator *Op, ConstantInt *OpRHS,
938  ConstantInt *AndRHS, BinaryOperator &TheAnd);
939 
940  Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
941  bool isSigned, bool Inside);
942  Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
943  bool mergeStoreIntoSuccessor(StoreInst &SI);
944 
945  /// Given an 'or' instruction, check to see if it is part of a bswap idiom.
946  /// If so, return the equivalent bswap intrinsic.
947  Instruction *matchBSwap(BinaryOperator &Or);
948 
949  Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
950  Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
951 
952  Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
953 
954  /// Returns a value X such that Val = X * Scale, or null if none.
955  ///
956  /// If the multiplication is known not to overflow then NoSignedWrap is set.
957  Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
958 };
959 
960 } // end namespace llvm
961 
962 #undef DEBUG_TYPE
963 
964 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
Type * getVectorElementType() const
Definition: Type.h:370
Value * EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions=false)
Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from th...
Definition: Local.h:28
uint64_t CallInst * C
Return a value (possibly void), from a function.
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...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:636
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool IsFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
This instruction extracts a struct member or array element value from an aggregate value...
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
Base class for instruction visitors.
Definition: InstVisitor.h:80
static bool willNotOverflow(WithOverflowInst *WO, LazyValueInfo *LVI)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
An instruction for ordering other memory operations.
Definition: Instructions.h:454
This class represents zero extension of integer types.
Analysis providing profile information.
This class represents a function call, abstracting a target machine&#39;s calling convention.
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
unsigned less or equal
Definition: InstrTypes.h:672
void CreateNonTerminatorUnreachable(Instruction *InsertAt)
Create and insert the idiom we use to indicate a block is unreachable without having to rewrite the C...
void Remove(Instruction *I)
A cache of @llvm.assume calls within a function.
bool salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1603
This instruction constructs a fixed permutation of two input vectors.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:709
void Add(Instruction *I)
Add - Add the specified instruction to the worklist if it isn&#39;t already in it.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1014
This class represents a sign extension of integer types.
An instruction for reading from memory.
Definition: Instructions.h:167
uint64_t MaxArraySizeForCombine
Maximum size of array considered when transforming.
an instruction that atomically reads a memory location, combines it with another value, and then stores the result back.
Definition: Instructions.h:691
Hexagon Common GEP
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2258
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:229
static OverflowCheckFlavor IntrinsicIDToOverflowCheckFlavor(unsigned ID)
Returns the OverflowCheckFlavor corresponding to a overflow_with_op intrinsic.
This defines the Use class.
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:274
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2247
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
This class represents a conversion between pointers from one address space to another.
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
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. ...
This class represents the LLVM &#39;select&#39; instruction.
OverflowCheckFlavor
Specific patterns of overflow check idioms that we match.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:353
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Class to represent struct types.
Definition: DerivedTypes.h:232
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Instruction * eraseInstFromFunction(Instruction &I)
Combiner aware instruction erasure.
The core instruction combiner logic.
static Constant * AddOne(Constant *C)
Add one to a Constant.
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:653
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 &#39;V & Mask&#39; is known to be zero.
This class represents a cast from a pointer to an integer.
DominatorTree & getDominatorTree() const
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...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
This represents the llvm.va_start intrinsic.
static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)
Some binary operators require special handling to avoid poison and undefined behavior.
This instruction compares its operands according to the predicate given to the constructor.
This class represents a no-op cast from one type to another.
An instruction for storing to memory.
Definition: Instructions.h:320
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Instruction * visitInstruction(Instruction &I)
Specify what to return for unhandled instructions.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
This class represents a cast from floating point to signed integer.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
This class represents a truncation of integer types.
Class to represent pointers.
Definition: DerivedTypes.h:498
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:344
const DataLayout & getDataLayout() const
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:873
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
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...
This instruction inserts a single (scalar) element into a VectorType value.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:318
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
void AddUsersToWorkList(Instruction &I)
AddUsersToWorkList - When an instruction is simplified, add all users of the instruction to the work ...
Conditional or Unconditional Branch instruction.
This is an important base class in LLVM.
Definition: Constant.h:41
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:646
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2335
This class represents any memset intrinsic.
Instruction * CreateOverflowTuple(IntrinsicInst *II, Value *Result, Constant *Overflow)
Creates a result tuple for an overflow intrinsic II with a given Result and a constant Overflow value...
static Constant * get(StructType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:1053
op_range operands()
Definition: User.h:237
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library...
Definition: Compiler.h:107
self_iterator getIterator()
Definition: ilist_node.h:81
This class represents a cast from an integer to a pointer.
InstCombineWorklist - This is the worklist management logic for InstCombine.
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
InstCombiner(InstCombineWorklist &Worklist, BuilderTy &Builder, bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, const DataLayout &DL, LoopInfo *LI)
TargetLibraryInfo & getTargetLibraryInfo() const
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
InstCombineWorklist & Worklist
A worklist of the instructions that need to be simplified.
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:333
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
unsigned getNumOperands() const
Definition: User.h:191
static PointerType * getInt1PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:215
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
BlockVerifier::State From
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
SelectPatternFlavor
Specific patterns of select instructions we can match.
Provides information about what library functions are available for the current target.
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
This class represents a cast from floating point to unsigned integer.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
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:631
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:694
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:587
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a &#39;Neg&#39; as &#39;sub 0, V&#39;.
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:493
signed less or equal
Definition: InstrTypes.h:676
Class for arbitrary precision integers.
Definition: APInt.h:69
LoopInfo * getLoopInfo() const
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match &#39;fneg X&#39; as &#39;fsub -0.0, X&#39;.
Definition: PatternMatch.h:688
iterator insert(iterator where, pointer New)
Definition: ilist.h:226
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:321
OverflowResult
unsigned greater or equal
Definition: InstrTypes.h:670
KnownBits computeKnownBits(const Value *V, unsigned Depth, const Instruction *CxtI) const
static InsertValueInst * Create(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
#define I(x, y, z)
Definition: MD5.cpp:58
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:654
This instruction extracts a single (scalar) element from a VectorType value.
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
AssumptionCache & getAssumptionCache() const
Multiway switch.
This represents the llvm.va_copy intrinsic.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
This class represents a truncation of floating point types.
LLVM Value Representation.
Definition: Value.h:72
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
Invoke instruction.
IRTranslator LLVM IR MI
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:651
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
The optimization diagnostic interface.
bool use_empty() const
Definition: Value.h:322
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1088
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a &#39;Not&#39; as &#39;xor V, -1&#39; or &#39;xor -1, V&#39;.
signed greater or equal
Definition: InstrTypes.h:674
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
const BasicBlock * getParent() const
Definition: Instruction.h:66
an instruction to allocate memory on the stack
Definition: Instructions.h:59
This instruction inserts a struct field of array element value into an aggregate value.