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 *visitFNeg(UnaryOperator &I);
351  Instruction *visitAdd(BinaryOperator &I);
352  Instruction *visitFAdd(BinaryOperator &I);
353  Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty);
354  Instruction *visitSub(BinaryOperator &I);
355  Instruction *visitFSub(BinaryOperator &I);
356  Instruction *visitMul(BinaryOperator &I);
357  Instruction *visitFMul(BinaryOperator &I);
358  Instruction *visitURem(BinaryOperator &I);
359  Instruction *visitSRem(BinaryOperator &I);
360  Instruction *visitFRem(BinaryOperator &I);
361  bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
362  Instruction *commonRemTransforms(BinaryOperator &I);
363  Instruction *commonIRemTransforms(BinaryOperator &I);
364  Instruction *commonDivTransforms(BinaryOperator &I);
365  Instruction *commonIDivTransforms(BinaryOperator &I);
366  Instruction *visitUDiv(BinaryOperator &I);
367  Instruction *visitSDiv(BinaryOperator &I);
368  Instruction *visitFDiv(BinaryOperator &I);
369  Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
370  Instruction *visitAnd(BinaryOperator &I);
371  Instruction *visitOr(BinaryOperator &I);
372  Instruction *visitXor(BinaryOperator &I);
373  Instruction *visitShl(BinaryOperator &I);
374  Instruction *visitAShr(BinaryOperator &I);
375  Instruction *visitLShr(BinaryOperator &I);
376  Instruction *commonShiftTransforms(BinaryOperator &I);
377  Instruction *visitFCmpInst(FCmpInst &I);
378  Instruction *visitICmpInst(ICmpInst &I);
379  Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
380  BinaryOperator &I);
381  Instruction *commonCastTransforms(CastInst &CI);
382  Instruction *commonPointerCastTransforms(CastInst &CI);
383  Instruction *visitTrunc(TruncInst &CI);
384  Instruction *visitZExt(ZExtInst &CI);
385  Instruction *visitSExt(SExtInst &CI);
386  Instruction *visitFPTrunc(FPTruncInst &CI);
387  Instruction *visitFPExt(CastInst &CI);
388  Instruction *visitFPToUI(FPToUIInst &FI);
389  Instruction *visitFPToSI(FPToSIInst &FI);
390  Instruction *visitUIToFP(CastInst &CI);
391  Instruction *visitSIToFP(CastInst &CI);
392  Instruction *visitPtrToInt(PtrToIntInst &CI);
393  Instruction *visitIntToPtr(IntToPtrInst &CI);
394  Instruction *visitBitCast(BitCastInst &CI);
395  Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
396  Instruction *FoldItoFPtoI(Instruction &FI);
397  Instruction *visitSelectInst(SelectInst &SI);
398  Instruction *visitCallInst(CallInst &CI);
399  Instruction *visitInvokeInst(InvokeInst &II);
400  Instruction *visitCallBrInst(CallBrInst &CBI);
401 
402  Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
403  Instruction *visitPHINode(PHINode &PN);
404  Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
405  Instruction *visitAllocaInst(AllocaInst &AI);
406  Instruction *visitAllocSite(Instruction &FI);
407  Instruction *visitFree(CallInst &FI);
408  Instruction *visitLoadInst(LoadInst &LI);
409  Instruction *visitStoreInst(StoreInst &SI);
410  Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
411  Instruction *visitBranchInst(BranchInst &BI);
412  Instruction *visitFenceInst(FenceInst &FI);
413  Instruction *visitSwitchInst(SwitchInst &SI);
414  Instruction *visitReturnInst(ReturnInst &RI);
415  Instruction *visitInsertValueInst(InsertValueInst &IV);
416  Instruction *visitInsertElementInst(InsertElementInst &IE);
417  Instruction *visitExtractElementInst(ExtractElementInst &EI);
418  Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
419  Instruction *visitExtractValueInst(ExtractValueInst &EV);
420  Instruction *visitLandingPadInst(LandingPadInst &LI);
421  Instruction *visitVAStartInst(VAStartInst &I);
422  Instruction *visitVACopyInst(VACopyInst &I);
423 
424  /// Specify what to return for unhandled instructions.
425  Instruction *visitInstruction(Instruction &I) { return nullptr; }
426 
427  /// True when DB dominates all uses of DI except UI.
428  /// UI must be in the same block as DI.
429  /// The routine checks that the DI parent and DB are different.
430  bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
431  const BasicBlock *DB) const;
432 
433  /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
434  bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
435  const unsigned SIOpd);
436 
437  /// Try to replace instruction \p I with value \p V which are pointers
438  /// in different address space.
439  /// \return true if successful.
440  bool replacePointer(Instruction &I, Value *V);
441 
442 private:
443  bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
444  bool shouldChangeType(Type *From, Type *To) const;
445  Value *dyn_castNegVal(Value *V) const;
446  Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
447  SmallVectorImpl<Value *> &NewIndices);
448 
449  /// Classify whether a cast is worth optimizing.
450  ///
451  /// This is a helper to decide whether the simplification of
452  /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
453  ///
454  /// \param CI The cast we are interested in.
455  ///
456  /// \return true if this cast actually results in any code being generated and
457  /// if it cannot already be eliminated by some other transformation.
458  bool shouldOptimizeCast(CastInst *CI);
459 
460  /// Try to optimize a sequence of instructions checking if an operation
461  /// on LHS and RHS overflows.
462  ///
463  /// If this overflow check is done via one of the overflow check intrinsics,
464  /// then CtxI has to be the call instruction calling that intrinsic. If this
465  /// overflow check is done by arithmetic followed by a compare, then CtxI has
466  /// to be the arithmetic instruction.
467  ///
468  /// If a simplification is possible, stores the simplified result of the
469  /// operation in OperationResult and result of the overflow check in
470  /// OverflowResult, and return true. If no simplification is possible,
471  /// returns false.
472  bool OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS, Value *RHS,
473  Instruction &CtxI, Value *&OperationResult,
475 
476  Instruction *visitCallBase(CallBase &Call);
477  Instruction *tryOptimizeCall(CallInst *CI);
478  bool transformConstExprCastCall(CallBase &Call);
479  Instruction *transformCallThroughTrampoline(CallBase &Call,
480  IntrinsicInst &Tramp);
481 
482  Value *simplifyMaskedLoad(IntrinsicInst &II);
483  Instruction *simplifyMaskedStore(IntrinsicInst &II);
484  Instruction *simplifyMaskedGather(IntrinsicInst &II);
485  Instruction *simplifyMaskedScatter(IntrinsicInst &II);
486 
487  /// Transform (zext icmp) to bitwise / integer operations in order to
488  /// eliminate it.
489  ///
490  /// \param ICI The icmp of the (zext icmp) pair we are interested in.
491  /// \parem CI The zext of the (zext icmp) pair we are interested in.
492  /// \param DoTransform Pass false to just test whether the given (zext icmp)
493  /// would be transformed. Pass true to actually perform the transformation.
494  ///
495  /// \return null if the transformation cannot be performed. If the
496  /// transformation can be performed the new instruction that replaces the
497  /// (zext icmp) pair will be returned (if \p DoTransform is false the
498  /// unmodified \p ICI will be returned in this case).
499  Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI,
500  bool DoTransform = true);
501 
502  Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
503 
504  bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
505  const Instruction &CxtI) const {
506  return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
508  }
509 
510  bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
511  const Instruction &CxtI) const {
512  return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
514  }
515 
516  bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
517  const Instruction &CxtI, bool IsSigned) const {
518  return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
519  : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
520  }
521 
522  bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
523  const Instruction &CxtI) const {
524  return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
526  }
527 
528  bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
529  const Instruction &CxtI) const {
530  return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
532  }
533 
534  bool willNotOverflowSub(const Value *LHS, const Value *RHS,
535  const Instruction &CxtI, bool IsSigned) const {
536  return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
537  : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
538  }
539 
540  bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
541  const Instruction &CxtI) const {
542  return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
544  }
545 
546  bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
547  const Instruction &CxtI) const {
548  return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
550  }
551 
552  bool willNotOverflowMul(const Value *LHS, const Value *RHS,
553  const Instruction &CxtI, bool IsSigned) const {
554  return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
555  : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
556  }
557 
558  bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
559  const Value *RHS, const Instruction &CxtI,
560  bool IsSigned) const {
561  switch (Opcode) {
562  case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
563  case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
564  case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
565  default: llvm_unreachable("Unexpected opcode for overflow query");
566  }
567  }
568 
569  Value *EmitGEPOffset(User *GEP);
570  Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
571  Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
572  Instruction *narrowBinOp(TruncInst &Trunc);
573  Instruction *narrowMaskedBinOp(BinaryOperator &And);
574  Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
575  Instruction *narrowRotate(TruncInst &Trunc);
576  Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
577 
578  /// Determine if a pair of casts can be replaced by a single cast.
579  ///
580  /// \param CI1 The first of a pair of casts.
581  /// \param CI2 The second of a pair of casts.
582  ///
583  /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
584  /// Instruction::CastOps value for a cast that can replace the pair, casting
585  /// CI1->getSrcTy() to CI2->getDstTy().
586  ///
587  /// \see CastInst::isEliminableCastPair
588  Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
589  const CastInst *CI2);
590 
591  Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
592  Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
593  Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS);
594 
595  /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
596  /// NOTE: Unlike most of instcombine, this returns a Value which should
597  /// already be inserted into the function.
598  Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd);
599 
600  Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
601  bool JoinedByAnd, Instruction &CxtI);
602  Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
603  Value *getSelectCondition(Value *A, Value *B);
604 
605  Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
606 
607 public:
608  /// Inserts an instruction \p New before instruction \p Old
609  ///
610  /// Also adds the new instruction to the worklist and returns \p New so that
611  /// it is suitable for use as the return from the visitation patterns.
613  assert(New && !New->getParent() &&
614  "New instruction already inserted into a basic block!");
615  BasicBlock *BB = Old.getParent();
616  BB->getInstList().insert(Old.getIterator(), New); // Insert inst
617  Worklist.Add(New);
618  return New;
619  }
620 
621  /// Same as InsertNewInstBefore, but also sets the debug loc.
623  New->setDebugLoc(Old.getDebugLoc());
624  return InsertNewInstBefore(New, Old);
625  }
626 
627  /// A combiner-aware RAUW-like routine.
628  ///
629  /// This method is to be used when an instruction is found to be dead,
630  /// replaceable with another preexisting expression. Here we add all uses of
631  /// I to the worklist, replace all uses of I with the new value, then return
632  /// I, so that the inst combiner will know that I was modified.
634  // If there are no uses to replace, then we return nullptr to indicate that
635  // no changes were made to the program.
636  if (I.use_empty()) return nullptr;
637 
638  Worklist.AddUsersToWorkList(I); // Add all modified instrs to worklist.
639 
640  // If we are replacing the instruction with itself, this must be in a
641  // segment of unreachable code, so just clobber the instruction.
642  if (&I == V)
643  V = UndefValue::get(I.getType());
644 
645  LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
646  << " with " << *V << '\n');
647 
648  I.replaceAllUsesWith(V);
649  return &I;
650  }
651 
652  /// Creates a result tuple for an overflow intrinsic \p II with a given
653  /// \p Result and a constant \p Overflow value.
655  Constant *Overflow) {
656  Constant *V[] = {UndefValue::get(Result->getType()), Overflow};
657  StructType *ST = cast<StructType>(II->getType());
658  Constant *Struct = ConstantStruct::get(ST, V);
659  return InsertValueInst::Create(Struct, Result, 0);
660  }
661 
662  /// Create and insert the idiom we use to indicate a block is unreachable
663  /// without having to rewrite the CFG from within InstCombine.
665  auto &Ctx = InsertAt->getContext();
668  InsertAt);
669  }
670 
671 
672  /// Combiner aware instruction erasure.
673  ///
674  /// When dealing with an instruction that has side effects or produces a void
675  /// value, we can't rely on DCE to delete the instruction. Instead, visit
676  /// methods should return the value returned by this function.
678  LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
679  assert(I.use_empty() && "Cannot erase instruction that is used!");
680  salvageDebugInfo(I);
681 
682  // Make sure that we reprocess all operands now that we reduced their
683  // use counts.
684  if (I.getNumOperands() < 8) {
685  for (Use &Operand : I.operands())
686  if (auto *Inst = dyn_cast<Instruction>(Operand))
687  Worklist.Add(Inst);
688  }
689  Worklist.Remove(&I);
690  I.eraseFromParent();
691  MadeIRChange = true;
692  return nullptr; // Don't do anything with FI
693  }
694 
695  void computeKnownBits(const Value *V, KnownBits &Known,
696  unsigned Depth, const Instruction *CxtI) const {
697  llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
698  }
699 
700  KnownBits computeKnownBits(const Value *V, unsigned Depth,
701  const Instruction *CxtI) const {
702  return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
703  }
704 
705  bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
706  unsigned Depth = 0,
707  const Instruction *CxtI = nullptr) {
708  return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
709  }
710 
711  bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
712  const Instruction *CxtI = nullptr) const {
713  return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
714  }
715 
716  unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
717  const Instruction *CxtI = nullptr) const {
718  return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
719  }
720 
721  OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
722  const Value *RHS,
723  const Instruction *CxtI) const {
724  return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
725  }
726 
727  OverflowResult computeOverflowForSignedMul(const Value *LHS,
728  const Value *RHS,
729  const Instruction *CxtI) const {
730  return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
731  }
732 
733  OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
734  const Value *RHS,
735  const Instruction *CxtI) const {
736  return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
737  }
738 
739  OverflowResult computeOverflowForSignedAdd(const Value *LHS,
740  const Value *RHS,
741  const Instruction *CxtI) const {
742  return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
743  }
744 
745  OverflowResult computeOverflowForUnsignedSub(const Value *LHS,
746  const Value *RHS,
747  const Instruction *CxtI) const {
748  return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
749  }
750 
751  OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
752  const Instruction *CxtI) const {
753  return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
754  }
755 
756  /// Maximum size of array considered when transforming.
758 
759 private:
760  /// Performs a few simplifications for operators which are associative
761  /// or commutative.
762  bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
763 
764  /// Tries to simplify binary operations which some other binary
765  /// operation distributes over.
766  ///
767  /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
768  /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
769  /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
770  /// value, or null if it didn't simplify.
771  Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
772 
773  /// Tries to simplify add operations using the definition of remainder.
774  ///
775  /// The definition of remainder is X % C = X - (X / C ) * C. The add
776  /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
777  /// X % (C0 * C1)
778  Value *SimplifyAddWithRemainder(BinaryOperator &I);
779 
780  // Binary Op helper for select operations where the expression can be
781  // efficiently reorganized.
782  Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
783  Value *RHS);
784 
785  /// This tries to simplify binary operations by factorizing out common terms
786  /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
787  Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
788  Value *, Value *, Value *);
789 
790  /// Match a select chain which produces one of three values based on whether
791  /// the LHS is less than, equal to, or greater than RHS respectively.
792  /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
793  /// Equal and Greater values are saved in the matching process and returned to
794  /// the caller.
795  bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
797  ConstantInt *&Greater);
798 
799  /// Attempts to replace V with a simpler value based on the demanded
800  /// bits.
801  Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
802  unsigned Depth, Instruction *CxtI);
803  bool SimplifyDemandedBits(Instruction *I, unsigned Op,
804  const APInt &DemandedMask, KnownBits &Known,
805  unsigned Depth = 0);
806 
807  /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
808  /// bits. It also tries to handle simplifications that can be done based on
809  /// DemandedMask, but without modifying the Instruction.
810  Value *SimplifyMultipleUseDemandedBits(Instruction *I,
811  const APInt &DemandedMask,
812  KnownBits &Known,
813  unsigned Depth, Instruction *CxtI);
814 
815  /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
816  /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
817  Value *simplifyShrShlDemandedBits(
818  Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
819  const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
820 
821  /// Tries to simplify operands to an integer instruction based on its
822  /// demanded bits.
823  bool SimplifyDemandedInstructionBits(Instruction &Inst);
824 
825  Value *simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II,
826  APInt DemandedElts,
827  int DmaskIdx = -1);
828 
829  Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
830  APInt &UndefElts, unsigned Depth = 0);
831 
832  /// Canonicalize the position of binops relative to shufflevector.
833  Instruction *foldVectorBinop(BinaryOperator &Inst);
834 
835  /// Given a binary operator, cast instruction, or select which has a PHI node
836  /// as operand #0, see if we can fold the instruction into the PHI (which is
837  /// only possible if all operands to the PHI are constants).
838  Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
839 
840  /// Given an instruction with a select as one operand and a constant as the
841  /// other operand, try to fold the binary operator into the select arguments.
842  /// This also works for Cast instructions, which obviously do not have a
843  /// second operand.
844  Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
845 
846  /// This is a convenience wrapper function for the above two functions.
847  Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
848 
849  Instruction *foldAddWithConstant(BinaryOperator &Add);
850 
851  /// Try to rotate an operation below a PHI node, using PHI nodes for
852  /// its operands.
853  Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
854  Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN);
855  Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN);
856  Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN);
857  Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN);
858 
859  /// If an integer typed PHI has only one use which is an IntToPtr operation,
860  /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
861  /// insert a new pointer typed PHI and replace the original one.
862  Instruction *FoldIntegerTypedPHI(PHINode &PN);
863 
864  /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
865  /// folded operation.
866  void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
867 
868  Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
870  Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
871  const Value *Other);
872  Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
873  GlobalVariable *GV, CmpInst &ICI,
874  ConstantInt *AndCst = nullptr);
875  Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
876  Constant *RHSC);
877  Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
878  ICmpInst::Predicate Pred);
879  Instruction *foldICmpWithCastAndCast(ICmpInst &ICI);
880 
881  Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
882  Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
883  Instruction *foldICmpWithConstant(ICmpInst &Cmp);
884  Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
885  Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
886  Instruction *foldICmpBinOp(ICmpInst &Cmp);
887  Instruction *foldICmpEquality(ICmpInst &Cmp);
888  Instruction *foldICmpWithZero(ICmpInst &Cmp);
889 
890  Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
891  ConstantInt *C);
892  Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
893  const APInt &C);
894  Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
895  const APInt &C);
896  Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
897  const APInt &C);
898  Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
899  const APInt &C);
900  Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
901  const APInt &C);
902  Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
903  const APInt &C);
904  Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
905  const APInt &C);
906  Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
907  const APInt &C);
908  Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
909  const APInt &C);
910  Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
911  const APInt &C);
912  Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
913  const APInt &C);
914  Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
915  const APInt &C1);
916  Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
917  const APInt &C1, const APInt &C2);
918  Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
919  const APInt &C2);
920  Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
921  const APInt &C2);
922 
923  Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
924  BinaryOperator *BO,
925  const APInt &C);
926  Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
927  const APInt &C);
928  Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
929  const APInt &C);
930 
931  // Helpers of visitSelectInst().
932  Instruction *foldSelectExtConst(SelectInst &Sel);
933  Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
934  Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
935  Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
936  Value *A, Value *B, Instruction &Outer,
937  SelectPatternFlavor SPF2, Value *C);
938  Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
939 
940  Instruction *OptAndOp(BinaryOperator *Op, ConstantInt *OpRHS,
941  ConstantInt *AndRHS, BinaryOperator &TheAnd);
942 
943  Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
944  bool isSigned, bool Inside);
945  Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
946  bool mergeStoreIntoSuccessor(StoreInst &SI);
947 
948  /// Given an 'or' instruction, check to see if it is part of a bswap idiom.
949  /// If so, return the equivalent bswap intrinsic.
950  Instruction *matchBSwap(BinaryOperator &Or);
951 
952  Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
953  Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
954 
955  Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
956 
957  /// Returns a value X such that Val = X * Scale, or null if none.
958  ///
959  /// If the multiplication is known not to overflow then NoSignedWrap is set.
960  Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
961 };
962 
963 } // end namespace llvm
964 
965 #undef DEBUG_TYPE
966 
967 #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:699
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:735
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:1624
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:1077
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:2239
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:2228
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:416
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:716
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:709
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2316
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:739
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:696
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:733
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:717
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:714
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:737
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.