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