InstCombineInternal.h revision 314564 
1//===- InstCombineInternal.h - InstCombine pass internals -------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
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/Analysis/AliasAnalysis.h"
19#include "llvm/Analysis/AssumptionCache.h"
20#include "llvm/Analysis/LoopInfo.h"
21#include "llvm/Analysis/TargetFolder.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/IR/Dominators.h"
24#include "llvm/IR/IRBuilder.h"
25#include "llvm/IR/InstVisitor.h"
26#include "llvm/IR/IntrinsicInst.h"
27#include "llvm/IR/Operator.h"
28#include "llvm/IR/PatternMatch.h"
29#include "llvm/Pass.h"
30#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
31
32#define DEBUG_TYPE "instcombine"
33
34namespace llvm {
35class CallSite;
36class DataLayout;
37class DominatorTree;
38class TargetLibraryInfo;
39class DbgDeclareInst;
40class MemIntrinsic;
41class MemSetInst;
42
43/// \brief Assign a complexity or rank value to LLVM Values.
44///
45/// This routine maps IR values to various complexity ranks:
46///   0 -> undef
47///   1 -> Constants
48///   2 -> Other non-instructions
49///   3 -> Arguments
50///   3 -> Unary operations
51///   4 -> Other instructions
52static inline unsigned getComplexity(Value *V) {
53  if (isa<Instruction>(V)) {
54    if (BinaryOperator::isNeg(V) || BinaryOperator::isFNeg(V) ||
55        BinaryOperator::isNot(V))
56      return 3;
57    return 4;
58  }
59  if (isa<Argument>(V))
60    return 3;
61  return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
62}
63
64/// \brief Add one to a Constant
65static inline Constant *AddOne(Constant *C) {
66  return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
67}
68/// \brief Subtract one from a Constant
69static inline Constant *SubOne(Constant *C) {
70  return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
71}
72
73/// \brief Return true if the specified value is free to invert (apply ~ to).
74/// This happens in cases where the ~ can be eliminated.  If WillInvertAllUses
75/// is true, work under the assumption that the caller intends to remove all
76/// uses of V and only keep uses of ~V.
77///
78static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) {
79  // ~(~(X)) -> X.
80  if (BinaryOperator::isNot(V))
81    return true;
82
83  // Constants can be considered to be not'ed values.
84  if (isa<ConstantInt>(V))
85    return true;
86
87  // A vector of constant integers can be inverted easily.
88  Constant *CV;
89  if (V->getType()->isVectorTy() && match(V, PatternMatch::m_Constant(CV))) {
90    unsigned NumElts = V->getType()->getVectorNumElements();
91    for (unsigned i = 0; i != NumElts; ++i) {
92      Constant *Elt = CV->getAggregateElement(i);
93      if (!Elt)
94        return false;
95
96      if (isa<UndefValue>(Elt))
97        continue;
98
99      if (!isa<ConstantInt>(Elt))
100        return false;
101    }
102    return true;
103  }
104
105  // Compares can be inverted if all of their uses are being modified to use the
106  // ~V.
107  if (isa<CmpInst>(V))
108    return WillInvertAllUses;
109
110  // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1
111  // - Constant) - A` if we are willing to invert all of the uses.
112  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
113    if (BO->getOpcode() == Instruction::Add ||
114        BO->getOpcode() == Instruction::Sub)
115      if (isa<Constant>(BO->getOperand(0)) || isa<Constant>(BO->getOperand(1)))
116        return WillInvertAllUses;
117
118  return false;
119}
120
121
122/// \brief Specific patterns of overflow check idioms that we match.
123enum OverflowCheckFlavor {
124  OCF_UNSIGNED_ADD,
125  OCF_SIGNED_ADD,
126  OCF_UNSIGNED_SUB,
127  OCF_SIGNED_SUB,
128  OCF_UNSIGNED_MUL,
129  OCF_SIGNED_MUL,
130
131  OCF_INVALID
132};
133
134/// \brief Returns the OverflowCheckFlavor corresponding to a overflow_with_op
135/// intrinsic.
136static inline OverflowCheckFlavor
137IntrinsicIDToOverflowCheckFlavor(unsigned ID) {
138  switch (ID) {
139  default:
140    return OCF_INVALID;
141  case Intrinsic::uadd_with_overflow:
142    return OCF_UNSIGNED_ADD;
143  case Intrinsic::sadd_with_overflow:
144    return OCF_SIGNED_ADD;
145  case Intrinsic::usub_with_overflow:
146    return OCF_UNSIGNED_SUB;
147  case Intrinsic::ssub_with_overflow:
148    return OCF_SIGNED_SUB;
149  case Intrinsic::umul_with_overflow:
150    return OCF_UNSIGNED_MUL;
151  case Intrinsic::smul_with_overflow:
152    return OCF_SIGNED_MUL;
153  }
154}
155
156/// \brief The core instruction combiner logic.
157///
158/// This class provides both the logic to recursively visit instructions and
159/// combine them.
160class LLVM_LIBRARY_VISIBILITY InstCombiner
161    : public InstVisitor<InstCombiner, Instruction *> {
162  // FIXME: These members shouldn't be public.
163public:
164  /// \brief A worklist of the instructions that need to be simplified.
165  InstCombineWorklist &Worklist;
166
167  /// \brief An IRBuilder that automatically inserts new instructions into the
168  /// worklist.
169  typedef IRBuilder<TargetFolder, IRBuilderCallbackInserter> BuilderTy;
170  BuilderTy *Builder;
171
172private:
173  // Mode in which we are running the combiner.
174  const bool MinimizeSize;
175  /// Enable combines that trigger rarely but are costly in compiletime.
176  const bool ExpensiveCombines;
177
178  AliasAnalysis *AA;
179
180  // Required analyses.
181  AssumptionCache &AC;
182  TargetLibraryInfo &TLI;
183  DominatorTree &DT;
184  const DataLayout &DL;
185
186  // Optional analyses. When non-null, these can both be used to do better
187  // combining and will be updated to reflect any changes.
188  LoopInfo *LI;
189
190  bool MadeIRChange;
191
192public:
193  InstCombiner(InstCombineWorklist &Worklist, BuilderTy *Builder,
194               bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA,
195               AssumptionCache &AC, TargetLibraryInfo &TLI,
196               DominatorTree &DT, const DataLayout &DL, LoopInfo *LI)
197      : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize),
198        ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT),
199        DL(DL), LI(LI), MadeIRChange(false) {}
200
201  /// \brief Run the combiner over the entire worklist until it is empty.
202  ///
203  /// \returns true if the IR is changed.
204  bool run();
205
206  AssumptionCache &getAssumptionCache() const { return AC; }
207
208  const DataLayout &getDataLayout() const { return DL; }
209
210  DominatorTree &getDominatorTree() const { return DT; }
211
212  LoopInfo *getLoopInfo() const { return LI; }
213
214  TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; }
215
216  // Visitation implementation - Implement instruction combining for different
217  // instruction types.  The semantics are as follows:
218  // Return Value:
219  //    null        - No change was made
220  //     I          - Change was made, I is still valid, I may be dead though
221  //   otherwise    - Change was made, replace I with returned instruction
222  //
223  Instruction *visitAdd(BinaryOperator &I);
224  Instruction *visitFAdd(BinaryOperator &I);
225  Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty);
226  Instruction *visitSub(BinaryOperator &I);
227  Instruction *visitFSub(BinaryOperator &I);
228  Instruction *visitMul(BinaryOperator &I);
229  Value *foldFMulConst(Instruction *FMulOrDiv, Constant *C,
230                       Instruction *InsertBefore);
231  Instruction *visitFMul(BinaryOperator &I);
232  Instruction *visitURem(BinaryOperator &I);
233  Instruction *visitSRem(BinaryOperator &I);
234  Instruction *visitFRem(BinaryOperator &I);
235  bool SimplifyDivRemOfSelect(BinaryOperator &I);
236  Instruction *commonRemTransforms(BinaryOperator &I);
237  Instruction *commonIRemTransforms(BinaryOperator &I);
238  Instruction *commonDivTransforms(BinaryOperator &I);
239  Instruction *commonIDivTransforms(BinaryOperator &I);
240  Instruction *visitUDiv(BinaryOperator &I);
241  Instruction *visitSDiv(BinaryOperator &I);
242  Instruction *visitFDiv(BinaryOperator &I);
243  Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
244  Value *FoldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS);
245  Value *FoldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS);
246  Instruction *visitAnd(BinaryOperator &I);
247  Value *FoldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction *CxtI);
248  Value *FoldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS);
249  Instruction *FoldOrWithConstants(BinaryOperator &I, Value *Op, Value *A,
250                                   Value *B, Value *C);
251  Instruction *FoldXorWithConstants(BinaryOperator &I, Value *Op, Value *A,
252                                    Value *B, Value *C);
253  Instruction *visitOr(BinaryOperator &I);
254  Instruction *visitXor(BinaryOperator &I);
255  Instruction *visitShl(BinaryOperator &I);
256  Instruction *visitAShr(BinaryOperator &I);
257  Instruction *visitLShr(BinaryOperator &I);
258  Instruction *commonShiftTransforms(BinaryOperator &I);
259  Instruction *visitFCmpInst(FCmpInst &I);
260  Instruction *visitICmpInst(ICmpInst &I);
261  Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
262                                   BinaryOperator &I);
263  Instruction *commonCastTransforms(CastInst &CI);
264  Instruction *commonPointerCastTransforms(CastInst &CI);
265  Instruction *visitTrunc(TruncInst &CI);
266  Instruction *visitZExt(ZExtInst &CI);
267  Instruction *visitSExt(SExtInst &CI);
268  Instruction *visitFPTrunc(FPTruncInst &CI);
269  Instruction *visitFPExt(CastInst &CI);
270  Instruction *visitFPToUI(FPToUIInst &FI);
271  Instruction *visitFPToSI(FPToSIInst &FI);
272  Instruction *visitUIToFP(CastInst &CI);
273  Instruction *visitSIToFP(CastInst &CI);
274  Instruction *visitPtrToInt(PtrToIntInst &CI);
275  Instruction *visitIntToPtr(IntToPtrInst &CI);
276  Instruction *visitBitCast(BitCastInst &CI);
277  Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
278  Instruction *FoldItoFPtoI(Instruction &FI);
279  Instruction *visitSelectInst(SelectInst &SI);
280  Instruction *visitCallInst(CallInst &CI);
281  Instruction *visitInvokeInst(InvokeInst &II);
282
283  Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
284  Instruction *visitPHINode(PHINode &PN);
285  Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
286  Instruction *visitAllocaInst(AllocaInst &AI);
287  Instruction *visitAllocSite(Instruction &FI);
288  Instruction *visitFree(CallInst &FI);
289  Instruction *visitLoadInst(LoadInst &LI);
290  Instruction *visitStoreInst(StoreInst &SI);
291  Instruction *visitBranchInst(BranchInst &BI);
292  Instruction *visitSwitchInst(SwitchInst &SI);
293  Instruction *visitReturnInst(ReturnInst &RI);
294  Instruction *visitInsertValueInst(InsertValueInst &IV);
295  Instruction *visitInsertElementInst(InsertElementInst &IE);
296  Instruction *visitExtractElementInst(ExtractElementInst &EI);
297  Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
298  Instruction *visitExtractValueInst(ExtractValueInst &EV);
299  Instruction *visitLandingPadInst(LandingPadInst &LI);
300  Instruction *visitVAStartInst(VAStartInst &I);
301  Instruction *visitVACopyInst(VACopyInst &I);
302
303  /// Specify what to return for unhandled instructions.
304  Instruction *visitInstruction(Instruction &I) { return nullptr; }
305
306  /// True when DB dominates all uses of DI except UI.
307  /// UI must be in the same block as DI.
308  /// The routine checks that the DI parent and DB are different.
309  bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
310                        const BasicBlock *DB) const;
311
312  /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
313  bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
314                                 const unsigned SIOpd);
315
316private:
317  bool ShouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
318  bool ShouldChangeType(Type *From, Type *To) const;
319  Value *dyn_castNegVal(Value *V) const;
320  Value *dyn_castFNegVal(Value *V, bool NoSignedZero = false) const;
321  Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
322                            SmallVectorImpl<Value *> &NewIndices);
323
324  /// Classify whether a cast is worth optimizing.
325  ///
326  /// This is a helper to decide whether the simplification of
327  /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
328  ///
329  /// \param CI The cast we are interested in.
330  ///
331  /// \return true if this cast actually results in any code being generated and
332  /// if it cannot already be eliminated by some other transformation.
333  bool shouldOptimizeCast(CastInst *CI);
334
335  /// \brief Try to optimize a sequence of instructions checking if an operation
336  /// on LHS and RHS overflows.
337  ///
338  /// If this overflow check is done via one of the overflow check intrinsics,
339  /// then CtxI has to be the call instruction calling that intrinsic.  If this
340  /// overflow check is done by arithmetic followed by a compare, then CtxI has
341  /// to be the arithmetic instruction.
342  ///
343  /// If a simplification is possible, stores the simplified result of the
344  /// operation in OperationResult and result of the overflow check in
345  /// OverflowResult, and return true.  If no simplification is possible,
346  /// returns false.
347  bool OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS, Value *RHS,
348                             Instruction &CtxI, Value *&OperationResult,
349                             Constant *&OverflowResult);
350
351  Instruction *visitCallSite(CallSite CS);
352  Instruction *tryOptimizeCall(CallInst *CI);
353  bool transformConstExprCastCall(CallSite CS);
354  Instruction *transformCallThroughTrampoline(CallSite CS,
355                                              IntrinsicInst *Tramp);
356
357  /// Transform (zext icmp) to bitwise / integer operations in order to
358  /// eliminate it.
359  ///
360  /// \param ICI The icmp of the (zext icmp) pair we are interested in.
361  /// \parem CI The zext of the (zext icmp) pair we are interested in.
362  /// \param DoTransform Pass false to just test whether the given (zext icmp)
363  /// would be transformed. Pass true to actually perform the transformation.
364  ///
365  /// \return null if the transformation cannot be performed. If the
366  /// transformation can be performed the new instruction that replaces the
367  /// (zext icmp) pair will be returned (if \p DoTransform is false the
368  /// unmodified \p ICI will be returned in this case).
369  Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI,
370                                 bool DoTransform = true);
371
372  Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
373  bool WillNotOverflowSignedAdd(Value *LHS, Value *RHS, Instruction &CxtI);
374  bool WillNotOverflowSignedSub(Value *LHS, Value *RHS, Instruction &CxtI);
375  bool WillNotOverflowUnsignedSub(Value *LHS, Value *RHS, Instruction &CxtI);
376  bool WillNotOverflowSignedMul(Value *LHS, Value *RHS, Instruction &CxtI);
377  Value *EmitGEPOffset(User *GEP);
378  Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
379  Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask);
380  Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
381  Instruction *shrinkBitwiseLogic(TruncInst &Trunc);
382  Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
383
384  /// Determine if a pair of casts can be replaced by a single cast.
385  ///
386  /// \param CI1 The first of a pair of casts.
387  /// \param CI2 The second of a pair of casts.
388  ///
389  /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
390  /// Instruction::CastOps value for a cast that can replace the pair, casting
391  /// CI1->getSrcTy() to CI2->getDstTy().
392  ///
393  /// \see CastInst::isEliminableCastPair
394  Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
395                                            const CastInst *CI2);
396
397public:
398  /// \brief Inserts an instruction \p New before instruction \p Old
399  ///
400  /// Also adds the new instruction to the worklist and returns \p New so that
401  /// it is suitable for use as the return from the visitation patterns.
402  Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
403    assert(New && !New->getParent() &&
404           "New instruction already inserted into a basic block!");
405    BasicBlock *BB = Old.getParent();
406    BB->getInstList().insert(Old.getIterator(), New); // Insert inst
407    Worklist.Add(New);
408    return New;
409  }
410
411  /// \brief Same as InsertNewInstBefore, but also sets the debug loc.
412  Instruction *InsertNewInstWith(Instruction *New, Instruction &Old) {
413    New->setDebugLoc(Old.getDebugLoc());
414    return InsertNewInstBefore(New, Old);
415  }
416
417  /// \brief A combiner-aware RAUW-like routine.
418  ///
419  /// This method is to be used when an instruction is found to be dead,
420  /// replaceable with another preexisting expression. Here we add all uses of
421  /// I to the worklist, replace all uses of I with the new value, then return
422  /// I, so that the inst combiner will know that I was modified.
423  Instruction *replaceInstUsesWith(Instruction &I, Value *V) {
424    // If there are no uses to replace, then we return nullptr to indicate that
425    // no changes were made to the program.
426    if (I.use_empty()) return nullptr;
427
428    Worklist.AddUsersToWorkList(I); // Add all modified instrs to worklist.
429
430    // If we are replacing the instruction with itself, this must be in a
431    // segment of unreachable code, so just clobber the instruction.
432    if (&I == V)
433      V = UndefValue::get(I.getType());
434
435    DEBUG(dbgs() << "IC: Replacing " << I << "\n"
436                 << "    with " << *V << '\n');
437
438    I.replaceAllUsesWith(V);
439    return &I;
440  }
441
442  /// Creates a result tuple for an overflow intrinsic \p II with a given
443  /// \p Result and a constant \p Overflow value.
444  Instruction *CreateOverflowTuple(IntrinsicInst *II, Value *Result,
445                                   Constant *Overflow) {
446    Constant *V[] = {UndefValue::get(Result->getType()), Overflow};
447    StructType *ST = cast<StructType>(II->getType());
448    Constant *Struct = ConstantStruct::get(ST, V);
449    return InsertValueInst::Create(Struct, Result, 0);
450  }
451
452  /// \brief Combiner aware instruction erasure.
453  ///
454  /// When dealing with an instruction that has side effects or produces a void
455  /// value, we can't rely on DCE to delete the instruction. Instead, visit
456  /// methods should return the value returned by this function.
457  Instruction *eraseInstFromFunction(Instruction &I) {
458    DEBUG(dbgs() << "IC: ERASE " << I << '\n');
459
460    assert(I.use_empty() && "Cannot erase instruction that is used!");
461    // Make sure that we reprocess all operands now that we reduced their
462    // use counts.
463    if (I.getNumOperands() < 8) {
464      for (Use &Operand : I.operands())
465        if (auto *Inst = dyn_cast<Instruction>(Operand))
466          Worklist.Add(Inst);
467    }
468    Worklist.Remove(&I);
469    I.eraseFromParent();
470    MadeIRChange = true;
471    return nullptr; // Don't do anything with FI
472  }
473
474  void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
475                        unsigned Depth, Instruction *CxtI) const {
476    return llvm::computeKnownBits(V, KnownZero, KnownOne, DL, Depth, &AC, CxtI,
477                                  &DT);
478  }
479
480  bool MaskedValueIsZero(Value *V, const APInt &Mask, unsigned Depth = 0,
481                         Instruction *CxtI = nullptr) const {
482    return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
483  }
484  unsigned ComputeNumSignBits(Value *Op, unsigned Depth = 0,
485                              Instruction *CxtI = nullptr) const {
486    return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
487  }
488  void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
489                      unsigned Depth = 0, Instruction *CxtI = nullptr) const {
490    return llvm::ComputeSignBit(V, KnownZero, KnownOne, DL, Depth, &AC, CxtI,
491                                &DT);
492  }
493  OverflowResult computeOverflowForUnsignedMul(Value *LHS, Value *RHS,
494                                               const Instruction *CxtI) {
495    return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
496  }
497  OverflowResult computeOverflowForUnsignedAdd(Value *LHS, Value *RHS,
498                                               const Instruction *CxtI) {
499    return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
500  }
501
502private:
503  /// \brief Performs a few simplifications for operators which are associative
504  /// or commutative.
505  bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
506
507  /// \brief Tries to simplify binary operations which some other binary
508  /// operation distributes over.
509  ///
510  /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
511  /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
512  /// & (B | C) -> (A&B) | (A&C)" if this is a win).  Returns the simplified
513  /// value, or null if it didn't simplify.
514  Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
515
516  /// \brief Attempts to replace V with a simpler value based on the demanded
517  /// bits.
518  Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, APInt &KnownZero,
519                                 APInt &KnownOne, unsigned Depth,
520                                 Instruction *CxtI);
521  bool SimplifyDemandedBits(Use &U, const APInt &DemandedMask, APInt &KnownZero,
522                            APInt &KnownOne, unsigned Depth = 0);
523  /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
524  /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
525  Value *SimplifyShrShlDemandedBits(Instruction *Lsr, Instruction *Sftl,
526                                    const APInt &DemandedMask, APInt &KnownZero,
527                                    APInt &KnownOne);
528
529  /// \brief Tries to simplify operands to an integer instruction based on its
530  /// demanded bits.
531  bool SimplifyDemandedInstructionBits(Instruction &Inst);
532
533  Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
534                                    APInt &UndefElts, unsigned Depth = 0);
535
536  Value *SimplifyVectorOp(BinaryOperator &Inst);
537  Value *SimplifyBSwap(BinaryOperator &Inst);
538
539
540  /// Given a binary operator, cast instruction, or select which has a PHI node
541  /// as operand #0, see if we can fold the instruction into the PHI (which is
542  /// only possible if all operands to the PHI are constants).
543  Instruction *FoldOpIntoPhi(Instruction &I);
544
545  /// Given an instruction with a select as one operand and a constant as the
546  /// other operand, try to fold the binary operator into the select arguments.
547  /// This also works for Cast instructions, which obviously do not have a
548  /// second operand.
549  Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
550
551  /// This is a convenience wrapper function for the above two functions.
552  Instruction *foldOpWithConstantIntoOperand(Instruction &I);
553
554  /// \brief Try to rotate an operation below a PHI node, using PHI nodes for
555  /// its operands.
556  Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
557  Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN);
558  Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN);
559  Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN);
560  Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN);
561
562  /// Helper function for FoldPHIArgXIntoPHI() to get debug location for the
563  /// folded operation.
564  DebugLoc PHIArgMergedDebugLoc(PHINode &PN);
565
566  Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
567                           ICmpInst::Predicate Cond, Instruction &I);
568  Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
569                             const Value *Other);
570  Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
571                                            GlobalVariable *GV, CmpInst &ICI,
572                                            ConstantInt *AndCst = nullptr);
573  Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
574                                    Constant *RHSC);
575  Instruction *foldICmpAddOpConst(Instruction &ICI, Value *X, ConstantInt *CI,
576                                  ICmpInst::Predicate Pred);
577  Instruction *foldICmpWithCastAndCast(ICmpInst &ICI);
578
579  Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
580  Instruction *foldICmpWithConstant(ICmpInst &Cmp);
581  Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
582  Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
583  Instruction *foldICmpBinOp(ICmpInst &Cmp);
584  Instruction *foldICmpEquality(ICmpInst &Cmp);
585
586  Instruction *foldICmpTruncConstant(ICmpInst &Cmp, Instruction *Trunc,
587                                     const APInt *C);
588  Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
589                                   const APInt *C);
590  Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
591                                   const APInt *C);
592  Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
593                                  const APInt *C);
594  Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
595                                   const APInt *C);
596  Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
597                                   const APInt *C);
598  Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
599                                   const APInt *C);
600  Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
601                                    const APInt *C);
602  Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
603                                   const APInt *C);
604  Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
605                                   const APInt *C);
606  Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
607                                   const APInt *C);
608  Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
609                                     const APInt *C1);
610  Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
611                                const APInt *C1, const APInt *C2);
612  Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
613                                     const APInt &C2);
614  Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
615                                     const APInt &C2);
616
617  Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
618                                                 BinaryOperator *BO,
619                                                 const APInt *C);
620  Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, const APInt *C);
621
622  // Helpers of visitSelectInst().
623  Instruction *foldSelectExtConst(SelectInst &Sel);
624  Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
625  Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
626  Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
627                            Value *A, Value *B, Instruction &Outer,
628                            SelectPatternFlavor SPF2, Value *C);
629  Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
630
631  Instruction *OptAndOp(Instruction *Op, ConstantInt *OpRHS,
632                        ConstantInt *AndRHS, BinaryOperator &TheAnd);
633
634  Value *FoldLogicalPlusAnd(Value *LHS, Value *RHS, ConstantInt *Mask,
635                            bool isSub, Instruction &I);
636  Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
637                         bool isSigned, bool Inside);
638  Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
639  Instruction *MatchBSwap(BinaryOperator &I);
640  bool SimplifyStoreAtEndOfBlock(StoreInst &SI);
641  Instruction *SimplifyMemTransfer(MemIntrinsic *MI);
642  Instruction *SimplifyMemSet(MemSetInst *MI);
643
644  Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
645
646  /// \brief Returns a value X such that Val = X * Scale, or null if none.
647  ///
648  /// If the multiplication is known not to overflow then NoSignedWrap is set.
649  Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
650};
651
652} // end namespace llvm.
653
654#undef DEBUG_TYPE
655
656#endif
657