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