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