LLVM  10.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 
118 
119 /// Return the source operand of a potentially bitcasted value while optionally
120 /// checking if it has one use. If there is no bitcast or the one use check is
121 /// not met, return the input value itself.
122 static inline Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) {
123  if (auto *BitCast = dyn_cast<BitCastInst>(V))
124  if (!OneUseOnly || BitCast->hasOneUse())
125  return BitCast->getOperand(0);
126 
127  // V is not a bitcast or V has more than one use and OneUseOnly is true.
128  return V;
129 }
130 
131 /// Add one to a Constant
132 static inline Constant *AddOne(Constant *C) {
133  return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
134 }
135 
136 /// Subtract one from a Constant
137 static inline Constant *SubOne(Constant *C) {
138  return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
139 }
140 
141 /// Return true if the specified value is free to invert (apply ~ to).
142 /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses
143 /// is true, work under the assumption that the caller intends to remove all
144 /// uses of V and only keep uses of ~V.
145 ///
146 /// See also: canFreelyInvertAllUsersOf()
147 static inline bool isFreeToInvert(Value *V, bool WillInvertAllUses) {
148  // ~(~(X)) -> X.
149  if (match(V, m_Not(m_Value())))
150  return true;
151 
152  // Constants can be considered to be not'ed values.
153  if (match(V, m_AnyIntegralConstant()))
154  return true;
155 
156  // Compares can be inverted if all of their uses are being modified to use the
157  // ~V.
158  if (isa<CmpInst>(V))
159  return WillInvertAllUses;
160 
161  // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1
162  // - Constant) - A` if we are willing to invert all of the uses.
163  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
164  if (BO->getOpcode() == Instruction::Add ||
165  BO->getOpcode() == Instruction::Sub)
166  if (isa<Constant>(BO->getOperand(0)) || isa<Constant>(BO->getOperand(1)))
167  return WillInvertAllUses;
168 
169  // Selects with invertible operands are freely invertible
170  if (match(V, m_Select(m_Value(), m_Not(m_Value()), m_Not(m_Value()))))
171  return WillInvertAllUses;
172 
173  return false;
174 }
175 
176 /// Given i1 V, can every user of V be freely adapted if V is changed to !V ?
177 ///
178 /// See also: isFreeToInvert()
179 static inline bool canFreelyInvertAllUsersOf(Value *V, Value *IgnoredUser) {
180  // Look at every user of V.
181  for (User *U : V->users()) {
182  if (U == IgnoredUser)
183  continue; // Don't consider this user.
184 
185  auto *I = cast<Instruction>(U);
186  switch (I->getOpcode()) {
187  case Instruction::Select:
188  case Instruction::Br:
189  break; // Free to invert by swapping true/false values/destinations.
190  case Instruction::Xor: // Can invert 'xor' if it's a 'not', by ignoring it.
191  if (!match(I, m_Not(m_Value())))
192  return false; // Not a 'not'.
193  break;
194  default:
195  return false; // Don't know, likely not freely invertible.
196  }
197  // So far all users were free to invert...
198  }
199  return true; // Can freely invert all users!
200 }
201 
202 /// Some binary operators require special handling to avoid poison and undefined
203 /// behavior. If a constant vector has undef elements, replace those undefs with
204 /// identity constants if possible because those are always safe to execute.
205 /// If no identity constant exists, replace undef with some other safe constant.
207  BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant) {
208  assert(In->getType()->isVectorTy() && "Not expecting scalars here");
209 
210  Type *EltTy = In->getType()->getVectorElementType();
211  auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant);
212  if (!SafeC) {
213  // TODO: Should this be available as a constant utility function? It is
214  // similar to getBinOpAbsorber().
215  if (IsRHSConstant) {
216  switch (Opcode) {
217  case Instruction::SRem: // X % 1 = 0
218  case Instruction::URem: // X %u 1 = 0
219  SafeC = ConstantInt::get(EltTy, 1);
220  break;
221  case Instruction::FRem: // X % 1.0 (doesn't simplify, but it is safe)
222  SafeC = ConstantFP::get(EltTy, 1.0);
223  break;
224  default:
225  llvm_unreachable("Only rem opcodes have no identity constant for RHS");
226  }
227  } else {
228  switch (Opcode) {
229  case Instruction::Shl: // 0 << X = 0
230  case Instruction::LShr: // 0 >>u X = 0
231  case Instruction::AShr: // 0 >> X = 0
232  case Instruction::SDiv: // 0 / X = 0
233  case Instruction::UDiv: // 0 /u X = 0
234  case Instruction::SRem: // 0 % X = 0
235  case Instruction::URem: // 0 %u X = 0
236  case Instruction::Sub: // 0 - X (doesn't simplify, but it is safe)
237  case Instruction::FSub: // 0.0 - X (doesn't simplify, but it is safe)
238  case Instruction::FDiv: // 0.0 / X (doesn't simplify, but it is safe)
239  case Instruction::FRem: // 0.0 % X = 0
240  SafeC = Constant::getNullValue(EltTy);
241  break;
242  default:
243  llvm_unreachable("Expected to find identity constant for opcode");
244  }
245  }
246  }
247  assert(SafeC && "Must have safe constant for binop");
248  unsigned NumElts = In->getType()->getVectorNumElements();
249  SmallVector<Constant *, 16> Out(NumElts);
250  for (unsigned i = 0; i != NumElts; ++i) {
251  Constant *C = In->getAggregateElement(i);
252  Out[i] = isa<UndefValue>(C) ? SafeC : C;
253  }
254  return ConstantVector::get(Out);
255 }
256 
257 /// The core instruction combiner logic.
258 ///
259 /// This class provides both the logic to recursively visit instructions and
260 /// combine them.
262  : public InstVisitor<InstCombiner, Instruction *> {
263  // FIXME: These members shouldn't be public.
264 public:
265  /// A worklist of the instructions that need to be simplified.
267 
268  /// An IRBuilder that automatically inserts new instructions into the
269  /// worklist.
272 
273 private:
274  // Mode in which we are running the combiner.
275  const bool MinimizeSize;
276 
277  /// Enable combines that trigger rarely but are costly in compiletime.
278  const bool ExpensiveCombines;
279 
280  AliasAnalysis *AA;
281 
282  // Required analyses.
283  AssumptionCache &AC;
284  TargetLibraryInfo &TLI;
285  DominatorTree &DT;
286  const DataLayout &DL;
287  const SimplifyQuery SQ;
290  ProfileSummaryInfo *PSI;
291 
292  // Optional analyses. When non-null, these can both be used to do better
293  // combining and will be updated to reflect any changes.
294  LoopInfo *LI;
295 
296  bool MadeIRChange = false;
297 
298 public:
300  bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA,
303  ProfileSummaryInfo *PSI, const DataLayout &DL, LoopInfo *LI)
304  : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize),
305  ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT),
306  DL(DL), SQ(DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {}
307 
308  /// Run the combiner over the entire worklist until it is empty.
309  ///
310  /// \returns true if the IR is changed.
311  bool run();
312 
313  AssumptionCache &getAssumptionCache() const { return AC; }
314 
315  const DataLayout &getDataLayout() const { return DL; }
316 
317  DominatorTree &getDominatorTree() const { return DT; }
318 
319  LoopInfo *getLoopInfo() const { return LI; }
320 
321  TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; }
322 
323  // Visitation implementation - Implement instruction combining for different
324  // instruction types. The semantics are as follows:
325  // Return Value:
326  // null - No change was made
327  // I - Change was made, I is still valid, I may be dead though
328  // otherwise - Change was made, replace I with returned instruction
329  //
330  Instruction *visitFNeg(UnaryOperator &I);
331  Instruction *visitAdd(BinaryOperator &I);
332  Instruction *visitFAdd(BinaryOperator &I);
333  Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty);
334  Instruction *visitSub(BinaryOperator &I);
335  Instruction *visitFSub(BinaryOperator &I);
336  Instruction *visitMul(BinaryOperator &I);
337  Instruction *visitFMul(BinaryOperator &I);
338  Instruction *visitURem(BinaryOperator &I);
339  Instruction *visitSRem(BinaryOperator &I);
340  Instruction *visitFRem(BinaryOperator &I);
341  bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
342  Instruction *commonRemTransforms(BinaryOperator &I);
343  Instruction *commonIRemTransforms(BinaryOperator &I);
344  Instruction *commonDivTransforms(BinaryOperator &I);
345  Instruction *commonIDivTransforms(BinaryOperator &I);
346  Instruction *visitUDiv(BinaryOperator &I);
347  Instruction *visitSDiv(BinaryOperator &I);
348  Instruction *visitFDiv(BinaryOperator &I);
349  Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
350  Instruction *visitAnd(BinaryOperator &I);
351  Instruction *visitOr(BinaryOperator &I);
352  Instruction *visitXor(BinaryOperator &I);
353  Instruction *visitShl(BinaryOperator &I);
354  Instruction *visitAShr(BinaryOperator &I);
355  Instruction *visitLShr(BinaryOperator &I);
356  Instruction *commonShiftTransforms(BinaryOperator &I);
357  Instruction *visitFCmpInst(FCmpInst &I);
358  Instruction *visitICmpInst(ICmpInst &I);
359  Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
360  BinaryOperator &I);
361  Instruction *commonCastTransforms(CastInst &CI);
362  Instruction *commonPointerCastTransforms(CastInst &CI);
363  Instruction *visitTrunc(TruncInst &CI);
364  Instruction *visitZExt(ZExtInst &CI);
365  Instruction *visitSExt(SExtInst &CI);
366  Instruction *visitFPTrunc(FPTruncInst &CI);
367  Instruction *visitFPExt(CastInst &CI);
368  Instruction *visitFPToUI(FPToUIInst &FI);
369  Instruction *visitFPToSI(FPToSIInst &FI);
370  Instruction *visitUIToFP(CastInst &CI);
371  Instruction *visitSIToFP(CastInst &CI);
372  Instruction *visitPtrToInt(PtrToIntInst &CI);
373  Instruction *visitIntToPtr(IntToPtrInst &CI);
374  Instruction *visitBitCast(BitCastInst &CI);
375  Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
376  Instruction *FoldItoFPtoI(Instruction &FI);
377  Instruction *visitSelectInst(SelectInst &SI);
378  Instruction *visitCallInst(CallInst &CI);
379  Instruction *visitInvokeInst(InvokeInst &II);
380  Instruction *visitCallBrInst(CallBrInst &CBI);
381 
382  Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
383  Instruction *visitPHINode(PHINode &PN);
384  Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
385  Instruction *visitAllocaInst(AllocaInst &AI);
386  Instruction *visitAllocSite(Instruction &FI);
387  Instruction *visitFree(CallInst &FI);
388  Instruction *visitLoadInst(LoadInst &LI);
389  Instruction *visitStoreInst(StoreInst &SI);
390  Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
391  Instruction *visitBranchInst(BranchInst &BI);
392  Instruction *visitFenceInst(FenceInst &FI);
393  Instruction *visitSwitchInst(SwitchInst &SI);
394  Instruction *visitReturnInst(ReturnInst &RI);
395  Instruction *visitInsertValueInst(InsertValueInst &IV);
396  Instruction *visitInsertElementInst(InsertElementInst &IE);
397  Instruction *visitExtractElementInst(ExtractElementInst &EI);
398  Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
399  Instruction *visitExtractValueInst(ExtractValueInst &EV);
400  Instruction *visitLandingPadInst(LandingPadInst &LI);
401  Instruction *visitVAStartInst(VAStartInst &I);
402  Instruction *visitVACopyInst(VACopyInst &I);
403 
404  /// Specify what to return for unhandled instructions.
405  Instruction *visitInstruction(Instruction &I) { return nullptr; }
406 
407  /// True when DB dominates all uses of DI except UI.
408  /// UI must be in the same block as DI.
409  /// The routine checks that the DI parent and DB are different.
410  bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
411  const BasicBlock *DB) const;
412 
413  /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
414  bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
415  const unsigned SIOpd);
416 
417  /// Try to replace instruction \p I with value \p V which are pointers
418  /// in different address space.
419  /// \return true if successful.
420  bool replacePointer(Instruction &I, Value *V);
421 
422 private:
423  bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
424  bool shouldChangeType(Type *From, Type *To) const;
425  Value *dyn_castNegVal(Value *V) const;
426  Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
427  SmallVectorImpl<Value *> &NewIndices);
428 
429  /// Classify whether a cast is worth optimizing.
430  ///
431  /// This is a helper to decide whether the simplification of
432  /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
433  ///
434  /// \param CI The cast we are interested in.
435  ///
436  /// \return true if this cast actually results in any code being generated and
437  /// if it cannot already be eliminated by some other transformation.
438  bool shouldOptimizeCast(CastInst *CI);
439 
440  /// Try to optimize a sequence of instructions checking if an operation
441  /// on LHS and RHS overflows.
442  ///
443  /// If this overflow check is done via one of the overflow check intrinsics,
444  /// then CtxI has to be the call instruction calling that intrinsic. If this
445  /// overflow check is done by arithmetic followed by a compare, then CtxI has
446  /// to be the arithmetic instruction.
447  ///
448  /// If a simplification is possible, stores the simplified result of the
449  /// operation in OperationResult and result of the overflow check in
450  /// OverflowResult, and return true. If no simplification is possible,
451  /// returns false.
452  bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
453  Value *LHS, Value *RHS,
454  Instruction &CtxI, Value *&OperationResult,
456 
457  Instruction *visitCallBase(CallBase &Call);
458  Instruction *tryOptimizeCall(CallInst *CI);
459  bool transformConstExprCastCall(CallBase &Call);
460  Instruction *transformCallThroughTrampoline(CallBase &Call,
461  IntrinsicInst &Tramp);
462 
463  Value *simplifyMaskedLoad(IntrinsicInst &II);
464  Instruction *simplifyMaskedStore(IntrinsicInst &II);
465  Instruction *simplifyMaskedGather(IntrinsicInst &II);
466  Instruction *simplifyMaskedScatter(IntrinsicInst &II);
467 
468  /// Transform (zext icmp) to bitwise / integer operations in order to
469  /// eliminate it.
470  ///
471  /// \param ICI The icmp of the (zext icmp) pair we are interested in.
472  /// \parem CI The zext of the (zext icmp) pair we are interested in.
473  /// \param DoTransform Pass false to just test whether the given (zext icmp)
474  /// would be transformed. Pass true to actually perform the transformation.
475  ///
476  /// \return null if the transformation cannot be performed. If the
477  /// transformation can be performed the new instruction that replaces the
478  /// (zext icmp) pair will be returned (if \p DoTransform is false the
479  /// unmodified \p ICI will be returned in this case).
480  Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI,
481  bool DoTransform = true);
482 
483  Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
484 
485  bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
486  const Instruction &CxtI) const {
487  return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
489  }
490 
491  bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
492  const Instruction &CxtI) const {
493  return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
495  }
496 
497  bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
498  const Instruction &CxtI, bool IsSigned) const {
499  return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
500  : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
501  }
502 
503  bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
504  const Instruction &CxtI) const {
505  return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
507  }
508 
509  bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
510  const Instruction &CxtI) const {
511  return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
513  }
514 
515  bool willNotOverflowSub(const Value *LHS, const Value *RHS,
516  const Instruction &CxtI, bool IsSigned) const {
517  return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
518  : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
519  }
520 
521  bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
522  const Instruction &CxtI) const {
523  return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
525  }
526 
527  bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
528  const Instruction &CxtI) const {
529  return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
531  }
532 
533  bool willNotOverflowMul(const Value *LHS, const Value *RHS,
534  const Instruction &CxtI, bool IsSigned) const {
535  return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
536  : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
537  }
538 
539  bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
540  const Value *RHS, const Instruction &CxtI,
541  bool IsSigned) const {
542  switch (Opcode) {
543  case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
544  case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
545  case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
546  default: llvm_unreachable("Unexpected opcode for overflow query");
547  }
548  }
549 
550  Value *EmitGEPOffset(User *GEP);
551  Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
552  Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
553  Instruction *narrowBinOp(TruncInst &Trunc);
554  Instruction *narrowMaskedBinOp(BinaryOperator &And);
555  Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
556  Instruction *narrowRotate(TruncInst &Trunc);
557  Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
558 
559  /// Determine if a pair of casts can be replaced by a single cast.
560  ///
561  /// \param CI1 The first of a pair of casts.
562  /// \param CI2 The second of a pair of casts.
563  ///
564  /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
565  /// Instruction::CastOps value for a cast that can replace the pair, casting
566  /// CI1->getSrcTy() to CI2->getDstTy().
567  ///
568  /// \see CastInst::isEliminableCastPair
569  Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
570  const CastInst *CI2);
571 
572  Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
573  Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
574  Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &I);
575 
576  /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
577  /// NOTE: Unlike most of instcombine, this returns a Value which should
578  /// already be inserted into the function.
579  Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd);
580 
581  Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
582  bool JoinedByAnd, Instruction &CxtI);
583  Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
584  Value *getSelectCondition(Value *A, Value *B);
585 
586  Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
587 
588 public:
589  /// Inserts an instruction \p New before instruction \p Old
590  ///
591  /// Also adds the new instruction to the worklist and returns \p New so that
592  /// it is suitable for use as the return from the visitation patterns.
594  assert(New && !New->getParent() &&
595  "New instruction already inserted into a basic block!");
596  BasicBlock *BB = Old.getParent();
597  BB->getInstList().insert(Old.getIterator(), New); // Insert inst
598  Worklist.Add(New);
599  return New;
600  }
601 
602  /// Same as InsertNewInstBefore, but also sets the debug loc.
604  New->setDebugLoc(Old.getDebugLoc());
605  return InsertNewInstBefore(New, Old);
606  }
607 
608  /// A combiner-aware RAUW-like routine.
609  ///
610  /// This method is to be used when an instruction is found to be dead,
611  /// replaceable with another preexisting expression. Here we add all uses of
612  /// I to the worklist, replace all uses of I with the new value, then return
613  /// I, so that the inst combiner will know that I was modified.
615  // If there are no uses to replace, then we return nullptr to indicate that
616  // no changes were made to the program.
617  if (I.use_empty()) return nullptr;
618 
619  Worklist.AddUsersToWorkList(I); // Add all modified instrs to worklist.
620 
621  // If we are replacing the instruction with itself, this must be in a
622  // segment of unreachable code, so just clobber the instruction.
623  if (&I == V)
624  V = UndefValue::get(I.getType());
625 
626  LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
627  << " with " << *V << '\n');
628 
629  I.replaceAllUsesWith(V);
630  return &I;
631  }
632 
633  /// Creates a result tuple for an overflow intrinsic \p II with a given
634  /// \p Result and a constant \p Overflow value.
636  Constant *Overflow) {
637  Constant *V[] = {UndefValue::get(Result->getType()), Overflow};
638  StructType *ST = cast<StructType>(II->getType());
639  Constant *Struct = ConstantStruct::get(ST, V);
640  return InsertValueInst::Create(Struct, Result, 0);
641  }
642 
643  /// Create and insert the idiom we use to indicate a block is unreachable
644  /// without having to rewrite the CFG from within InstCombine.
646  auto &Ctx = InsertAt->getContext();
649  InsertAt);
650  }
651 
652 
653  /// Combiner aware instruction erasure.
654  ///
655  /// When dealing with an instruction that has side effects or produces a void
656  /// value, we can't rely on DCE to delete the instruction. Instead, visit
657  /// methods should return the value returned by this function.
659  LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
660  assert(I.use_empty() && "Cannot erase instruction that is used!");
661  salvageDebugInfo(I);
662 
663  // Make sure that we reprocess all operands now that we reduced their
664  // use counts.
665  if (I.getNumOperands() < 8) {
666  for (Use &Operand : I.operands())
667  if (auto *Inst = dyn_cast<Instruction>(Operand))
668  Worklist.Add(Inst);
669  }
670  Worklist.Remove(&I);
671  I.eraseFromParent();
672  MadeIRChange = true;
673  return nullptr; // Don't do anything with FI
674  }
675 
676  void computeKnownBits(const Value *V, KnownBits &Known,
677  unsigned Depth, const Instruction *CxtI) const {
678  llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
679  }
680 
681  KnownBits computeKnownBits(const Value *V, unsigned Depth,
682  const Instruction *CxtI) const {
683  return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
684  }
685 
686  bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
687  unsigned Depth = 0,
688  const Instruction *CxtI = nullptr) {
689  return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
690  }
691 
692  bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
693  const Instruction *CxtI = nullptr) const {
694  return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
695  }
696 
697  unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
698  const Instruction *CxtI = nullptr) const {
699  return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
700  }
701 
702  OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
703  const Value *RHS,
704  const Instruction *CxtI) const {
705  return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
706  }
707 
708  OverflowResult computeOverflowForSignedMul(const Value *LHS,
709  const Value *RHS,
710  const Instruction *CxtI) const {
711  return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
712  }
713 
714  OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
715  const Value *RHS,
716  const Instruction *CxtI) const {
717  return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
718  }
719 
720  OverflowResult computeOverflowForSignedAdd(const Value *LHS,
721  const Value *RHS,
722  const Instruction *CxtI) const {
723  return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
724  }
725 
726  OverflowResult computeOverflowForUnsignedSub(const Value *LHS,
727  const Value *RHS,
728  const Instruction *CxtI) const {
729  return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
730  }
731 
732  OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
733  const Instruction *CxtI) const {
734  return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
735  }
736 
737  OverflowResult computeOverflow(
738  Instruction::BinaryOps BinaryOp, bool IsSigned,
739  Value *LHS, Value *RHS, Instruction *CxtI) const;
740 
741  /// Maximum size of array considered when transforming.
743 
744 private:
745  /// Performs a few simplifications for operators which are associative
746  /// or commutative.
747  bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
748 
749  /// Tries to simplify binary operations which some other binary
750  /// operation distributes over.
751  ///
752  /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
753  /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
754  /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
755  /// value, or null if it didn't simplify.
756  Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
757 
758  /// Tries to simplify add operations using the definition of remainder.
759  ///
760  /// The definition of remainder is X % C = X - (X / C ) * C. The add
761  /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
762  /// X % (C0 * C1)
763  Value *SimplifyAddWithRemainder(BinaryOperator &I);
764 
765  // Binary Op helper for select operations where the expression can be
766  // efficiently reorganized.
767  Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
768  Value *RHS);
769 
770  /// This tries to simplify binary operations by factorizing out common terms
771  /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
772  Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
773  Value *, Value *, Value *);
774 
775  /// Match a select chain which produces one of three values based on whether
776  /// the LHS is less than, equal to, or greater than RHS respectively.
777  /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
778  /// Equal and Greater values are saved in the matching process and returned to
779  /// the caller.
780  bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
782  ConstantInt *&Greater);
783 
784  /// Attempts to replace V with a simpler value based on the demanded
785  /// bits.
786  Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
787  unsigned Depth, Instruction *CxtI);
788  bool SimplifyDemandedBits(Instruction *I, unsigned Op,
789  const APInt &DemandedMask, KnownBits &Known,
790  unsigned Depth = 0);
791 
792  /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
793  /// bits. It also tries to handle simplifications that can be done based on
794  /// DemandedMask, but without modifying the Instruction.
795  Value *SimplifyMultipleUseDemandedBits(Instruction *I,
796  const APInt &DemandedMask,
797  KnownBits &Known,
798  unsigned Depth, Instruction *CxtI);
799 
800  /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
801  /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
802  Value *simplifyShrShlDemandedBits(
803  Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
804  const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
805 
806  /// Tries to simplify operands to an integer instruction based on its
807  /// demanded bits.
808  bool SimplifyDemandedInstructionBits(Instruction &Inst);
809 
810  Value *simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II,
811  APInt DemandedElts,
812  int DmaskIdx = -1);
813 
814  Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
815  APInt &UndefElts, unsigned Depth = 0);
816 
817  /// Canonicalize the position of binops relative to shufflevector.
818  Instruction *foldVectorBinop(BinaryOperator &Inst);
819 
820  /// Given a binary operator, cast instruction, or select which has a PHI node
821  /// as operand #0, see if we can fold the instruction into the PHI (which is
822  /// only possible if all operands to the PHI are constants).
823  Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
824 
825  /// Given an instruction with a select as one operand and a constant as the
826  /// other operand, try to fold the binary operator into the select arguments.
827  /// This also works for Cast instructions, which obviously do not have a
828  /// second operand.
829  Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
830 
831  /// This is a convenience wrapper function for the above two functions.
832  Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
833 
834  Instruction *foldAddWithConstant(BinaryOperator &Add);
835 
836  /// Try to rotate an operation below a PHI node, using PHI nodes for
837  /// its operands.
838  Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
839  Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN);
840  Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN);
841  Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN);
842  Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN);
843 
844  /// If an integer typed PHI has only one use which is an IntToPtr operation,
845  /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
846  /// insert a new pointer typed PHI and replace the original one.
847  Instruction *FoldIntegerTypedPHI(PHINode &PN);
848 
849  /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
850  /// folded operation.
851  void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
852 
853  Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
855  Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
856  const Value *Other);
857  Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
858  GlobalVariable *GV, CmpInst &ICI,
859  ConstantInt *AndCst = nullptr);
860  Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
861  Constant *RHSC);
862  Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
863  ICmpInst::Predicate Pred);
864  Instruction *foldICmpWithCastOp(ICmpInst &ICI);
865 
866  Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
867  Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
868  Instruction *foldICmpWithConstant(ICmpInst &Cmp);
869  Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
870  Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
871  Instruction *foldICmpBinOp(ICmpInst &Cmp);
872  Instruction *foldICmpEquality(ICmpInst &Cmp);
873  Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
874  Instruction *foldICmpWithZero(ICmpInst &Cmp);
875 
876  Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
877  ConstantInt *C);
878  Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
879  const APInt &C);
880  Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
881  const APInt &C);
882  Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
883  const APInt &C);
884  Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
885  const APInt &C);
886  Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
887  const APInt &C);
888  Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
889  const APInt &C);
890  Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
891  const APInt &C);
892  Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
893  const APInt &C);
894  Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
895  const APInt &C);
896  Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
897  const APInt &C);
898  Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
899  const APInt &C);
900  Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
901  const APInt &C1);
902  Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
903  const APInt &C1, const APInt &C2);
904  Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
905  const APInt &C2);
906  Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
907  const APInt &C2);
908 
909  Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
910  BinaryOperator *BO,
911  const APInt &C);
912  Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
913  const APInt &C);
914  Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
915  const APInt &C);
916 
917  // Helpers of visitSelectInst().
918  Instruction *foldSelectExtConst(SelectInst &Sel);
919  Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
920  Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
921  Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
922  Value *A, Value *B, Instruction &Outer,
923  SelectPatternFlavor SPF2, Value *C);
924  Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
925 
926  Instruction *OptAndOp(BinaryOperator *Op, ConstantInt *OpRHS,
927  ConstantInt *AndRHS, BinaryOperator &TheAnd);
928 
929  Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
930  bool isSigned, bool Inside);
931  Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
932  bool mergeStoreIntoSuccessor(StoreInst &SI);
933 
934  /// Given an 'or' instruction, check to see if it is part of a bswap idiom.
935  /// If so, return the equivalent bswap intrinsic.
936  Instruction *matchBSwap(BinaryOperator &Or);
937 
938  Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
939  Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
940 
941  Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
942 
943  /// Returns a value X such that Val = X * Scale, or null if none.
944  ///
945  /// If the multiplication is known not to overflow then NoSignedWrap is set.
946  Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
947 };
948 
949 } // end namespace llvm
950 
951 #undef DEBUG_TYPE
952 
953 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
Type * getVectorElementType() const
Definition: Type.h:371
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:111
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:722
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
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
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:758
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:1600
This instruction constructs a fixed permutation of two input vectors.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:733
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:1100
This class represents a sign extension of integer types.
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
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:693
Hexagon Common GEP
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2246
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:229
This defines the Use class.
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
static bool isFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
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:2235
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.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:439
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Class to represent struct types.
Definition: DerivedTypes.h:233
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:739
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:245
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:544
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:875
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:732
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2323
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:1060
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:115
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:1431
#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:837
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:638
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:701
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:594
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:535
signed less or equal
Definition: InstrTypes.h:762
Class for arbitrary precision integers.
Definition: APInt.h:69
iterator_range< user_iterator > users()
Definition: Value.h:419
LoopInfo * getLoopInfo() const
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
static bool canFreelyInvertAllUsersOf(Value *V, Value *IgnoredUser)
Given i1 V, can every user of V be freely adapted if V is changed to !V ?
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match &#39;fneg X&#39; as &#39;fsub -0.0, X&#39;.
Definition: PatternMatch.h:771
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:756
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
llvm::Optional< std::pair< CmpInst::Predicate, Constant * > > getFlippedStrictnessPredicateAndConstant(CmpInst::Predicate Pred, Constant *C)
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:740
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:73
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.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
Definition: PatternMatch.h:322
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:737
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:342
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1095
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:760
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.