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