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